+// © 2016 and later: Unicode, Inc. and others.
+// License & terms of use: http://www.unicode.org/copyright.html
/*
******************************************************************************
-* Copyright (C) 2014, International Business Machines Corporation and
-* others. All Rights Reserved.
+* Copyright (C) 2015, International Business Machines Corporation and
+* others. All Rights Reserved.
******************************************************************************
-*
-* File UNIFIEDCACHE.CPP
+*
+* File unifiedcache.cpp
******************************************************************************
*/
-#include "uhash.h"
#include "unifiedcache.h"
-#include "umutex.h"
+
+#include <algorithm> // For std::max()
+
#include "mutex.h"
#include "uassert.h"
+#include "uhash.h"
#include "ucln_cmn.h"
+#include "umutex.h"
static icu::UnifiedCache *gCache = NULL;
-static icu::SharedObject *gNoValue = NULL;
static UMutex gCacheMutex = U_MUTEX_INITIALIZER;
static UConditionVar gInProgressValueAddedCond = U_CONDITION_INITIALIZER;
static icu::UInitOnce gCacheInitOnce = U_INITONCE_INITIALIZER;
+static const int32_t MAX_EVICT_ITERATIONS = 10;
+static const int32_t DEFAULT_MAX_UNUSED = 1000;
+static const int32_t DEFAULT_PERCENTAGE_OF_IN_USE = 100;
+
+
U_CDECL_BEGIN
static UBool U_CALLCONV unifiedcache_cleanup() {
gCacheInitOnce.reset();
delete gCache;
gCache = NULL;
}
- if (gNoValue) {
- delete gNoValue;
- gNoValue = NULL;
- }
return TRUE;
}
U_CDECL_END
ucln_common_registerCleanup(
UCLN_COMMON_UNIFIED_CACHE, unifiedcache_cleanup);
- // gNoValue must be created first to avoid assertion error in
- // cache constructor.
- gNoValue = new SharedObject();
gCache = new UnifiedCache(status);
if (gCache == NULL) {
status = U_MEMORY_ALLOCATION_ERROR;
}
if (U_FAILURE(status)) {
delete gCache;
- delete gNoValue;
gCache = NULL;
- gNoValue = NULL;
return;
}
- // We add a softref because we want hash elements with gNoValue to be
- // elligible for purging but we don't ever want gNoValue to be deleted.
- gNoValue->addSoftRef();
}
-const UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) {
+UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) {
umtx_initOnce(gCacheInitOnce, &cacheInit, status);
if (U_FAILURE(status)) {
return NULL;
return gCache;
}
-UnifiedCache::UnifiedCache(UErrorCode &status) {
+UnifiedCache::UnifiedCache(UErrorCode &status) :
+ fHashtable(NULL),
+ fEvictPos(UHASH_FIRST),
+ fNumValuesTotal(0),
+ fNumValuesInUse(0),
+ fMaxUnused(DEFAULT_MAX_UNUSED),
+ fMaxPercentageOfInUse(DEFAULT_PERCENTAGE_OF_IN_USE),
+ fAutoEvictedCount(0),
+ fNoValue(nullptr) {
if (U_FAILURE(status)) {
return;
}
- U_ASSERT(gNoValue != NULL);
+ fNoValue = new SharedObject();
+ if (fNoValue == nullptr) {
+ status = U_MEMORY_ALLOCATION_ERROR;
+ return;
+ }
+ fNoValue->softRefCount = 1; // Add fake references to prevent fNoValue from being deleted
+ fNoValue->hardRefCount = 1; // when other references to it are removed.
+ fNoValue->cachePtr = this;
+
fHashtable = uhash_open(
&ucache_hashKeys,
&ucache_compareKeys,
uhash_setKeyDeleter(fHashtable, &ucache_deleteKey);
}
+void UnifiedCache::setEvictionPolicy(
+ int32_t count, int32_t percentageOfInUseItems, UErrorCode &status) {
+ if (U_FAILURE(status)) {
+ return;
+ }
+ if (count < 0 || percentageOfInUseItems < 0) {
+ status = U_ILLEGAL_ARGUMENT_ERROR;
+ return;
+ }
+ Mutex lock(&gCacheMutex);
+ fMaxUnused = count;
+ fMaxPercentageOfInUse = percentageOfInUseItems;
+}
+
+int32_t UnifiedCache::unusedCount() const {
+ Mutex lock(&gCacheMutex);
+ return uhash_count(fHashtable) - fNumValuesInUse;
+}
+
+int64_t UnifiedCache::autoEvictedCount() const {
+ Mutex lock(&gCacheMutex);
+ return fAutoEvictedCount;
+}
+
int32_t UnifiedCache::keyCount() const {
Mutex lock(&gCacheMutex);
return uhash_count(fHashtable);
// other cache items making those additional cache items eligible for
// flushing.
while (_flush(FALSE));
- umtx_condBroadcast(&gInProgressValueAddedCond);
+}
+
+void UnifiedCache::handleUnreferencedObject() const {
+ Mutex lock(&gCacheMutex);
+ --fNumValuesInUse;
+ _runEvictionSlice();
}
#ifdef UNIFIED_CACHE_DEBUG
(const SharedObject *) element->value.pointer;
const CacheKeyBase *key =
(const CacheKeyBase *) element->key.pointer;
- if (!sharedObject->allSoftReferences()) {
+ if (sharedObject->hasHardReferences()) {
++cnt;
fprintf(
stderr,
- "Unified Cache: Key '%s', error %d, value %p, total refcount %d, soft refcount %d\n",
+ "Unified Cache: Key '%s', error %d, value %p, total refcount %d, soft refcount %d\n",
key->writeDescription(buffer, 256),
key->creationStatus,
- sharedObject == gNoValue ? NULL :sharedObject,
+ sharedObject == fNoValue ? NULL :sharedObject,
sharedObject->getRefCount(),
sharedObject->getSoftRefCount());
}
flush();
{
// Now all that should be left in the cache are entries that refer to
- // each other and entries with hard references from outside the cache.
+ // each other and entries with hard references from outside the cache.
// Nothing we can do about these so proceed to wipe out the cache.
Mutex lock(&gCacheMutex);
_flush(TRUE);
}
uhash_close(fHashtable);
+ fHashtable = nullptr;
+ delete fNoValue;
+ fNoValue = nullptr;
+}
+
+const UHashElement *
+UnifiedCache::_nextElement() const {
+ const UHashElement *element = uhash_nextElement(fHashtable, &fEvictPos);
+ if (element == NULL) {
+ fEvictPos = UHASH_FIRST;
+ return uhash_nextElement(fHashtable, &fEvictPos);
+ }
+ return element;
}
-// Flushes the contents of the cache. If cache values hold references to other
-// cache values then _flush should be called in a loop until it returns FALSE.
-// On entry, gCacheMutex must be held.
-// On exit, those values with only soft references are flushed. If all is true
-// then every value is flushed even if hard references are held.
-// Returns TRUE if any value in cache was flushed or FALSE otherwise.
UBool UnifiedCache::_flush(UBool all) const {
UBool result = FALSE;
- int32_t pos = UHASH_FIRST;
- const UHashElement *element = uhash_nextElement(fHashtable, &pos);
- for (; element != NULL; element = uhash_nextElement(fHashtable, &pos)) {
- const SharedObject *sharedObject =
- (const SharedObject *) element->value.pointer;
- if (all || sharedObject->allSoftReferences()) {
+ int32_t origSize = uhash_count(fHashtable);
+ for (int32_t i = 0; i < origSize; ++i) {
+ const UHashElement *element = _nextElement();
+ if (element == nullptr) {
+ break;
+ }
+ if (all || _isEvictable(element)) {
+ const SharedObject *sharedObject =
+ (const SharedObject *) element->value.pointer;
+ U_ASSERT(sharedObject->cachePtr = this);
uhash_removeElement(fHashtable, element);
- sharedObject->removeSoftRef();
+ removeSoftRef(sharedObject); // Deletes the sharedObject when softRefCount goes to zero.
result = TRUE;
}
}
return result;
}
-// Places a new value and creationStatus in the cache for the given key.
-// On entry, gCacheMutex must be held. key must not exist in the cache.
-// On exit, value and creation status placed under key. Soft reference added
-// to value on successful add. On error sets status.
+int32_t UnifiedCache::_computeCountOfItemsToEvict() const {
+ int32_t totalItems = uhash_count(fHashtable);
+ int32_t evictableItems = totalItems - fNumValuesInUse;
+
+ int32_t unusedLimitByPercentage = fNumValuesInUse * fMaxPercentageOfInUse / 100;
+ int32_t unusedLimit = std::max(unusedLimitByPercentage, fMaxUnused);
+ int32_t countOfItemsToEvict = std::max(0, evictableItems - unusedLimit);
+ return countOfItemsToEvict;
+}
+
+void UnifiedCache::_runEvictionSlice() const {
+ int32_t maxItemsToEvict = _computeCountOfItemsToEvict();
+ if (maxItemsToEvict <= 0) {
+ return;
+ }
+ for (int32_t i = 0; i < MAX_EVICT_ITERATIONS; ++i) {
+ const UHashElement *element = _nextElement();
+ if (element == nullptr) {
+ break;
+ }
+ if (_isEvictable(element)) {
+ const SharedObject *sharedObject =
+ (const SharedObject *) element->value.pointer;
+ uhash_removeElement(fHashtable, element);
+ removeSoftRef(sharedObject); // Deletes sharedObject when SoftRefCount goes to zero.
+ ++fAutoEvictedCount;
+ if (--maxItemsToEvict == 0) {
+ break;
+ }
+ }
+ }
+}
+
void UnifiedCache::_putNew(
- const CacheKeyBase &key,
+ const CacheKeyBase &key,
const SharedObject *value,
const UErrorCode creationStatus,
UErrorCode &status) const {
status = U_MEMORY_ALLOCATION_ERROR;
return;
}
- keyToAdopt->creationStatus = creationStatus;
- uhash_put(fHashtable, keyToAdopt, (void *) value, &status);
+ keyToAdopt->fCreationStatus = creationStatus;
+ if (value->softRefCount == 0) {
+ _registerMaster(keyToAdopt, value);
+ }
+ void *oldValue = uhash_put(fHashtable, keyToAdopt, (void *) value, &status);
+ U_ASSERT(oldValue == nullptr);
+ (void)oldValue;
if (U_SUCCESS(status)) {
- value->addSoftRef();
+ value->softRefCount++;
}
}
-// Places value and status at key if there is no value at key or if cache
-// entry for key is in progress. Otherwise, it leaves the current value and
-// status there.
-// On entry. gCacheMutex must not be held. value must be
-// included in the reference count of the object to which it points.
-// On exit, value and status are changed to what was already in the cache if
-// something was there and not in progress. Otherwise, value and status are left
-// unchanged in which case they are placed in the cache on a best-effort basis.
-// Caller must call removeRef() on value.
void UnifiedCache::_putIfAbsentAndGet(
const CacheKeyBase &key,
const SharedObject *&value,
UErrorCode putError = U_ZERO_ERROR;
// best-effort basis only.
_putNew(key, value, status, putError);
- return;
+ } else {
+ _put(element, value, status);
}
- _put(element, value, status);
+ // Run an eviction slice. This will run even if we added a master entry
+ // which doesn't increase the unused count, but that is still o.k
+ _runEvictionSlice();
}
-// Attempts to fetch value and status for key from cache.
-// On entry, gCacheMutex must not be held value must be NULL and status must
-// be U_ZERO_ERROR.
-// On exit, either returns FALSE (In this
-// case caller should try to create the object) or returns TRUE with value
-// pointing to the fetched value and status set to fetched status. When
-// FALSE is returned status may be set to failure if an in progress hash
-// entry could not be made but value will remain unchanged. When TRUE is
-// returned, caler must call removeRef() on value.
+
UBool UnifiedCache::_poll(
const CacheKeyBase &key,
const SharedObject *&value,
U_ASSERT(status == U_ZERO_ERROR);
Mutex lock(&gCacheMutex);
const UHashElement *element = uhash_find(fHashtable, &key);
- while (element != NULL && _inProgress(element)) {
+
+ // If the hash table contains an inProgress placeholder entry for this key,
+ // this means that another thread is currently constructing the value object.
+ // Loop, waiting for that construction to complete.
+ while (element != NULL && _inProgress(element)) {
umtx_condWait(&gInProgressValueAddedCond, &gCacheMutex);
element = uhash_find(fHashtable, &key);
}
+
+ // If the hash table contains an entry for the key,
+ // fetch out the contents and return them.
if (element != NULL) {
- _fetch(element, value, status);
+ _fetch(element, value, status);
return TRUE;
}
- _putNew(key, gNoValue, U_ZERO_ERROR, status);
+
+ // The hash table contained nothing for this key.
+ // Insert an inProgress place holder value.
+ // Our caller will create the final value and update the hash table.
+ _putNew(key, fNoValue, U_ZERO_ERROR, status);
return FALSE;
}
-// Gets value out of cache.
-// On entry. gCacheMutex must not be held. value must be NULL. status
-// must be U_ZERO_ERROR.
-// On exit. value and status set to what is in cache at key or on cache
-// miss the key's createObject() is called and value and status are set to
-// the result of that. In this latter case, best effort is made to add the
-// value and status to the cache. value will be set to NULL instead of
-// gNoValue. Caller must call removeRef on value if non NULL.
void UnifiedCache::_get(
const CacheKeyBase &key,
const SharedObject *&value,
U_ASSERT(value == NULL);
U_ASSERT(status == U_ZERO_ERROR);
if (_poll(key, value, status)) {
- if (value == gNoValue) {
+ if (value == fNoValue) {
SharedObject::clearPtr(value);
}
return;
return;
}
value = key.createObject(creationContext, status);
- U_ASSERT(value == NULL || !value->allSoftReferences());
+ U_ASSERT(value == NULL || value->hasHardReferences());
U_ASSERT(value != NULL || status != U_ZERO_ERROR);
if (value == NULL) {
- SharedObject::copyPtr(gNoValue, value);
+ SharedObject::copyPtr(fNoValue, value);
}
_putIfAbsentAndGet(key, value, status);
- if (value == gNoValue) {
+ if (value == fNoValue) {
SharedObject::clearPtr(value);
}
}
-// Store a value and error in given hash entry.
-// On entry, gCacheMutex must be held. Hash entry element must be in progress.
-// value must be non NULL.
-// On Exit, soft reference added to value. value and status stored in hash
-// entry. Soft reference removed from previous stored value. Waiting
-// threads notified.
+void UnifiedCache::_registerMaster(
+ const CacheKeyBase *theKey, const SharedObject *value) const {
+ theKey->fIsMaster = true;
+ value->cachePtr = this;
+ ++fNumValuesTotal;
+ ++fNumValuesInUse;
+}
+
void UnifiedCache::_put(
- const UHashElement *element,
+ const UHashElement *element,
const SharedObject *value,
- const UErrorCode status) {
+ const UErrorCode status) const {
U_ASSERT(_inProgress(element));
const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
const SharedObject *oldValue = (const SharedObject *) element->value.pointer;
- theKey->creationStatus = status;
- value->addSoftRef();
+ theKey->fCreationStatus = status;
+ if (value->softRefCount == 0) {
+ _registerMaster(theKey, value);
+ }
+ value->softRefCount++;
UHashElement *ptr = const_cast<UHashElement *>(element);
ptr->value.pointer = (void *) value;
- oldValue->removeSoftRef();
+ U_ASSERT(oldValue == fNoValue);
+ removeSoftRef(oldValue);
// Tell waiting threads that we replace in-progress status with
// an error.
umtx_condBroadcast(&gInProgressValueAddedCond);
}
-// Fetch value and error code from a particular hash entry.
-// On entry, gCacheMutex must be held. value must be either NULL or must be
-// included in the ref count of the object to which it points.
-// On exit, value and status set to what is in the hash entry. Caller must
-// eventually call removeRef on value.
-// If hash entry is in progress, value will be set to gNoValue and status will
-// be set to U_ZERO_ERROR.
void UnifiedCache::_fetch(
const UHashElement *element,
const SharedObject *&value,
- UErrorCode &status) {
+ UErrorCode &status) const {
const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
- status = theKey->creationStatus;
- SharedObject::copyPtr(
- (const SharedObject *) element->value.pointer, value);
+ status = theKey->fCreationStatus;
+
+ // Since we have the cache lock, calling regular SharedObject add/removeRef
+ // could cause us to deadlock on ourselves since they may need to lock
+ // the cache mutex.
+ removeHardRef(value);
+ value = static_cast<const SharedObject *>(element->value.pointer);
+ addHardRef(value);
}
-
-// Determine if given hash entry is in progress.
-// On entry, gCacheMutex must be held.
-UBool UnifiedCache::_inProgress(const UHashElement *element) {
- const SharedObject *value = NULL;
+
+
+UBool UnifiedCache::_inProgress(const UHashElement* element) const {
UErrorCode status = U_ZERO_ERROR;
+ const SharedObject * value = NULL;
_fetch(element, value, status);
- UBool result = (value == gNoValue && status == U_ZERO_ERROR);
- SharedObject::clearPtr(value);
+ UBool result = _inProgress(value, status);
+ removeHardRef(value);
return result;
}
+UBool UnifiedCache::_inProgress(
+ const SharedObject* theValue, UErrorCode creationStatus) const {
+ return (theValue == fNoValue && creationStatus == U_ZERO_ERROR);
+}
+
+UBool UnifiedCache::_isEvictable(const UHashElement *element) const
+{
+ const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
+ const SharedObject *theValue =
+ (const SharedObject *) element->value.pointer;
+
+ // Entries that are under construction are never evictable
+ if (_inProgress(theValue, theKey->fCreationStatus)) {
+ return FALSE;
+ }
+
+ // We can evict entries that are either not a master or have just
+ // one reference (The one reference being from the cache itself).
+ return (!theKey->fIsMaster || (theValue->softRefCount == 1 && theValue->noHardReferences()));
+}
+
+void UnifiedCache::removeSoftRef(const SharedObject *value) const {
+ U_ASSERT(value->cachePtr == this);
+ U_ASSERT(value->softRefCount > 0);
+ if (--value->softRefCount == 0) {
+ --fNumValuesTotal;
+ if (value->noHardReferences()) {
+ delete value;
+ } else {
+ // This path only happens from flush(all). Which only happens from the
+ // UnifiedCache destructor. Nulling out value.cacheptr changes the behavior
+ // of value.removeRef(), causing the deletion to be done there.
+ value->cachePtr = nullptr;
+ }
+ }
+}
+
+int32_t UnifiedCache::removeHardRef(const SharedObject *value) const {
+ int refCount = 0;
+ if (value) {
+ refCount = umtx_atomic_dec(&value->hardRefCount);
+ U_ASSERT(refCount >= 0);
+ if (refCount == 0) {
+ --fNumValuesInUse;
+ }
+ }
+ return refCount;
+}
+
+int32_t UnifiedCache::addHardRef(const SharedObject *value) const {
+ int refCount = 0;
+ if (value) {
+ refCount = umtx_atomic_inc(&value->hardRefCount);
+ U_ASSERT(refCount >= 1);
+ if (refCount == 1) {
+ fNumValuesInUse++;
+ }
+ }
+ return refCount;
+}
+
U_NAMESPACE_END
projects / apple / icu.git / blobdiff