X-Git-Url: https://git.saurik.com/apple/icu.git/blobdiff_plain/b331163bffd790ced0e88b73f44f86d49ccc48a5..cecc3f9394f261e71def48cf396d137687dbd0a7:/icuSources/common/unifiedcache.cpp diff --git a/icuSources/common/unifiedcache.cpp b/icuSources/common/unifiedcache.cpp index 32899af7..f0f660ed 100644 --- a/icuSources/common/unifiedcache.cpp +++ b/icuSources/common/unifiedcache.cpp @@ -1,26 +1,35 @@ +// © 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 // 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(); @@ -28,10 +37,6 @@ static UBool U_CALLCONV unifiedcache_cleanup() { delete gCache; gCache = NULL; } - if (gNoValue) { - delete gNoValue; - gNoValue = NULL; - } return TRUE; } U_CDECL_END @@ -66,26 +71,18 @@ static void U_CALLCONV cacheInit(UErrorCode &status) { 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; @@ -94,11 +91,27 @@ const UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) { 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, @@ -110,6 +123,30 @@ UnifiedCache::UnifiedCache(UErrorCode &status) { 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); @@ -122,7 +159,12 @@ void UnifiedCache::flush() const { // 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 @@ -156,14 +198,14 @@ void UnifiedCache::_dumpContents() const { (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()); } @@ -177,42 +219,82 @@ UnifiedCache::~UnifiedCache() { 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 { @@ -224,22 +306,18 @@ void UnifiedCache::_putNew( 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, @@ -254,20 +332,15 @@ void UnifiedCache::_putIfAbsentAndGet( 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, @@ -276,26 +349,29 @@ UBool UnifiedCache::_poll( 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, @@ -304,7 +380,7 @@ void UnifiedCache::_get( 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; @@ -313,67 +389,131 @@ void UnifiedCache::_get( 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(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(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