| /* | |
| ****************************************************************************** | |
| * Copyright (C) 2015, International Business Machines Corporation and | |
| * others. All Rights Reserved. | |
| ****************************************************************************** | |
| * | |
| * File UNIFIEDCACHE.CPP | |
| ****************************************************************************** | |
| */ | |
| #include "starboard/client_porting/poem/assert_poem.h" | |
| #include "starboard/client_porting/poem/string_poem.h" | |
| #include "uhash.h" | |
| #include "unifiedcache.h" | |
| #include "umutex.h" | |
| #include "mutex.h" | |
| #include "uassert.h" | |
| #include "ucln_cmn.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 int32_t DEFAULT_MAX_UNUSED = 1000; | |
| static int32_t DEFAULT_PERCENTAGE_OF_IN_USE = 100; | |
| U_CDECL_BEGIN | |
| static UBool U_CALLCONV unifiedcache_cleanup() { | |
| gCacheInitOnce.reset(); | |
| if (gCache) { | |
| delete gCache; | |
| gCache = NULL; | |
| } | |
| if (gNoValue) { | |
| delete gNoValue; | |
| gNoValue = NULL; | |
| } | |
| return TRUE; | |
| } | |
| U_CDECL_END | |
| U_NAMESPACE_BEGIN | |
| U_CAPI int32_t U_EXPORT2 | |
| ucache_hashKeys(const UHashTok key) { | |
| const CacheKeyBase *ckey = (const CacheKeyBase *) key.pointer; | |
| return ckey->hashCode(); | |
| } | |
| U_CAPI UBool U_EXPORT2 | |
| ucache_compareKeys(const UHashTok key1, const UHashTok key2) { | |
| const CacheKeyBase *p1 = (const CacheKeyBase *) key1.pointer; | |
| const CacheKeyBase *p2 = (const CacheKeyBase *) key2.pointer; | |
| return *p1 == *p2; | |
| } | |
| U_CAPI void U_EXPORT2 | |
| ucache_deleteKey(void *obj) { | |
| CacheKeyBase *p = (CacheKeyBase *) obj; | |
| delete p; | |
| } | |
| CacheKeyBase::~CacheKeyBase() { | |
| } | |
| static void U_CALLCONV cacheInit(UErrorCode &status) { | |
| U_ASSERT(gCache == NULL); | |
| 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(); | |
| } | |
| UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) { | |
| umtx_initOnce(gCacheInitOnce, &cacheInit, status); | |
| if (U_FAILURE(status)) { | |
| return NULL; | |
| } | |
| U_ASSERT(gCache != NULL); | |
| return gCache; | |
| } | |
| UnifiedCache::UnifiedCache(UErrorCode &status) : | |
| fHashtable(NULL), | |
| fEvictPos(UHASH_FIRST), | |
| fItemsInUseCount(0), | |
| fMaxUnused(DEFAULT_MAX_UNUSED), | |
| fMaxPercentageOfInUse(DEFAULT_PERCENTAGE_OF_IN_USE), | |
| fAutoEvictedCount(0) { | |
| if (U_FAILURE(status)) { | |
| return; | |
| } | |
| U_ASSERT(gNoValue != NULL); | |
| fHashtable = uhash_open( | |
| &ucache_hashKeys, | |
| &ucache_compareKeys, | |
| NULL, | |
| &status); | |
| if (U_FAILURE(status)) { | |
| return; | |
| } | |
| 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) - fItemsInUseCount; | |
| } | |
| int64_t UnifiedCache::autoEvictedCount() const { | |
| Mutex lock(&gCacheMutex); | |
| return fAutoEvictedCount; | |
| } | |
| int32_t UnifiedCache::keyCount() const { | |
| Mutex lock(&gCacheMutex); | |
| return uhash_count(fHashtable); | |
| } | |
| void UnifiedCache::flush() const { | |
| Mutex lock(&gCacheMutex); | |
| // Use a loop in case cache items that are flushed held hard references to | |
| // other cache items making those additional cache items eligible for | |
| // flushing. | |
| while (_flush(FALSE)); | |
| } | |
| #ifdef UNIFIED_CACHE_DEBUG | |
| #include <stdio.h> | |
| void UnifiedCache::dump() { | |
| UErrorCode status = U_ZERO_ERROR; | |
| const UnifiedCache *cache = getInstance(status); | |
| if (U_FAILURE(status)) { | |
| fprintf(stderr, "Unified Cache: Error fetching cache.\n"); | |
| return; | |
| } | |
| cache->dumpContents(); | |
| } | |
| void UnifiedCache::dumpContents() const { | |
| Mutex lock(&gCacheMutex); | |
| _dumpContents(); | |
| } | |
| // Dumps content of cache. | |
| // On entry, gCacheMutex must be held. | |
| // On exit, cache contents dumped to stderr. | |
| void UnifiedCache::_dumpContents() const { | |
| int32_t pos = UHASH_FIRST; | |
| const UHashElement *element = uhash_nextElement(fHashtable, &pos); | |
| char buffer[256]; | |
| int32_t cnt = 0; | |
| for (; element != NULL; element = uhash_nextElement(fHashtable, &pos)) { | |
| const SharedObject *sharedObject = | |
| (const SharedObject *) element->value.pointer; | |
| const CacheKeyBase *key = | |
| (const CacheKeyBase *) element->key.pointer; | |
| if (sharedObject->hasHardReferences()) { | |
| ++cnt; | |
| fprintf( | |
| stderr, | |
| "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->getRefCount(), | |
| sharedObject->getSoftRefCount()); | |
| } | |
| } | |
| fprintf(stderr, "Unified Cache: %d out of a total of %d still have hard references\n", cnt, uhash_count(fHashtable)); | |
| } | |
| #endif | |
| UnifiedCache::~UnifiedCache() { | |
| // Try our best to clean up first. | |
| 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. | |
| // Nothing we can do about these so proceed to wipe out the cache. | |
| Mutex lock(&gCacheMutex); | |
| _flush(TRUE); | |
| } | |
| uhash_close(fHashtable); | |
| } | |
| // Returns the next element in the cache round robin style. | |
| // On entry, gCacheMutex must be held. | |
| 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 are evictable are flushed. If all is true | |
| // then every value is flushed even if it is not evictable. | |
| // Returns TRUE if any value in cache was flushed or FALSE otherwise. | |
| UBool UnifiedCache::_flush(UBool all) const { | |
| UBool result = FALSE; | |
| int32_t origSize = uhash_count(fHashtable); | |
| for (int32_t i = 0; i < origSize; ++i) { | |
| const UHashElement *element = _nextElement(); | |
| if (all || _isEvictable(element)) { | |
| const SharedObject *sharedObject = | |
| (const SharedObject *) element->value.pointer; | |
| uhash_removeElement(fHashtable, element); | |
| sharedObject->removeSoftRef(); | |
| result = TRUE; | |
| } | |
| } | |
| return result; | |
| } | |
| // Computes how many items should be evicted. | |
| // On entry, gCacheMutex must be held. | |
| // Returns number of items that should be evicted or a value <= 0 if no | |
| // items need to be evicted. | |
| int32_t UnifiedCache::_computeCountOfItemsToEvict() const { | |
| int32_t maxPercentageOfInUseCount = | |
| fItemsInUseCount * fMaxPercentageOfInUse / 100; | |
| int32_t maxUnusedCount = fMaxUnused; | |
| if (maxUnusedCount < maxPercentageOfInUseCount) { | |
| maxUnusedCount = maxPercentageOfInUseCount; | |
| } | |
| return uhash_count(fHashtable) - fItemsInUseCount - maxUnusedCount; | |
| } | |
| // Run an eviction slice. | |
| // On entry, gCacheMutex must be held. | |
| // _runEvictionSlice runs a slice of the evict pipeline by examining the next | |
| // 10 entries in the cache round robin style evicting them if they are eligible. | |
| 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 (_isEvictable(element)) { | |
| const SharedObject *sharedObject = | |
| (const SharedObject *) element->value.pointer; | |
| uhash_removeElement(fHashtable, element); | |
| sharedObject->removeSoftRef(); | |
| ++fAutoEvictedCount; | |
| if (--maxItemsToEvict == 0) { | |
| break; | |
| } | |
| } | |
| } | |
| } | |
| // 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. | |
| void UnifiedCache::_putNew( | |
| const CacheKeyBase &key, | |
| const SharedObject *value, | |
| const UErrorCode creationStatus, | |
| UErrorCode &status) const { | |
| if (U_FAILURE(status)) { | |
| return; | |
| } | |
| CacheKeyBase *keyToAdopt = key.clone(); | |
| if (keyToAdopt == NULL) { | |
| status = U_MEMORY_ALLOCATION_ERROR; | |
| return; | |
| } | |
| keyToAdopt->fCreationStatus = creationStatus; | |
| if (value->noSoftReferences()) { | |
| _registerMaster(keyToAdopt, value); | |
| } | |
| uhash_put(fHashtable, keyToAdopt, (void *) value, &status); | |
| if (U_SUCCESS(status)) { | |
| value->addSoftRef(); | |
| } | |
| } | |
| // 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 &status) const { | |
| Mutex lock(&gCacheMutex); | |
| const UHashElement *element = uhash_find(fHashtable, &key); | |
| if (element != NULL && !_inProgress(element)) { | |
| _fetch(element, value, status); | |
| return; | |
| } | |
| if (element == NULL) { | |
| UErrorCode putError = U_ZERO_ERROR; | |
| // best-effort basis only. | |
| _putNew(key, value, status, putError); | |
| } else { | |
| _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, | |
| UErrorCode &status) const { | |
| U_ASSERT(value == NULL); | |
| U_ASSERT(status == U_ZERO_ERROR); | |
| Mutex lock(&gCacheMutex); | |
| const UHashElement *element = uhash_find(fHashtable, &key); | |
| while (element != NULL && _inProgress(element)) { | |
| umtx_condWait(&gInProgressValueAddedCond, &gCacheMutex); | |
| element = uhash_find(fHashtable, &key); | |
| } | |
| if (element != NULL) { | |
| _fetch(element, value, status); | |
| return TRUE; | |
| } | |
| _putNew(key, gNoValue, 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. If createObject() fails to create a value, | |
| // gNoValue is stored in cache, and value is set to NULL. Caller must call | |
| // removeRef on value if non NULL. | |
| void UnifiedCache::_get( | |
| const CacheKeyBase &key, | |
| const SharedObject *&value, | |
| const void *creationContext, | |
| UErrorCode &status) const { | |
| U_ASSERT(value == NULL); | |
| U_ASSERT(status == U_ZERO_ERROR); | |
| if (_poll(key, value, status)) { | |
| if (value == gNoValue) { | |
| SharedObject::clearPtr(value); | |
| } | |
| return; | |
| } | |
| if (U_FAILURE(status)) { | |
| return; | |
| } | |
| value = key.createObject(creationContext, status); | |
| U_ASSERT(value == NULL || value->hasHardReferences()); | |
| U_ASSERT(value != NULL || status != U_ZERO_ERROR); | |
| if (value == NULL) { | |
| SharedObject::copyPtr(gNoValue, value); | |
| } | |
| _putIfAbsentAndGet(key, value, status); | |
| if (value == gNoValue) { | |
| SharedObject::clearPtr(value); | |
| } | |
| } | |
| void UnifiedCache::decrementItemsInUseWithLockingAndEviction() const { | |
| Mutex mutex(&gCacheMutex); | |
| decrementItemsInUse(); | |
| _runEvictionSlice(); | |
| } | |
| void UnifiedCache::incrementItemsInUse() const { | |
| ++fItemsInUseCount; | |
| } | |
| void UnifiedCache::decrementItemsInUse() const { | |
| --fItemsInUseCount; | |
| } | |
| // Register a master cache entry. | |
| // On entry, gCacheMutex must be held. | |
| // On exit, items in use count incremented, entry is marked as a master | |
| // entry, and value registered with cache so that subsequent calls to | |
| // addRef() and removeRef() on it correctly updates items in use count | |
| void UnifiedCache::_registerMaster( | |
| const CacheKeyBase *theKey, const SharedObject *value) const { | |
| theKey->fIsMaster = TRUE; | |
| ++fItemsInUseCount; | |
| value->registerWithCache(this); | |
| } | |
| // 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::_put( | |
| const UHashElement *element, | |
| const SharedObject *value, | |
| 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->fCreationStatus = status; | |
| if (value->noSoftReferences()) { | |
| _registerMaster(theKey, value); | |
| } | |
| value->addSoftRef(); | |
| UHashElement *ptr = const_cast<UHashElement *>(element); | |
| ptr->value.pointer = (void *) value; | |
| oldValue->removeSoftRef(); | |
| // Tell waiting threads that we replace in-progress status with | |
| // an error. | |
| umtx_condBroadcast(&gInProgressValueAddedCond); | |
| } | |
| void | |
| UnifiedCache::copyPtr(const SharedObject *src, const SharedObject *&dest) { | |
| if(src != dest) { | |
| if(dest != NULL) { | |
| dest->removeRefWhileHoldingCacheLock(); | |
| } | |
| dest = src; | |
| if(src != NULL) { | |
| src->addRefWhileHoldingCacheLock(); | |
| } | |
| } | |
| } | |
| void | |
| UnifiedCache::clearPtr(const SharedObject *&ptr) { | |
| if (ptr != NULL) { | |
| ptr->removeRefWhileHoldingCacheLock(); | |
| ptr = NULL; | |
| } | |
| } | |
| // 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) { | |
| const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer; | |
| status = theKey->fCreationStatus; | |
| // Since we have the cache lock, calling regular SharedObject methods | |
| // could cause us to deadlock on ourselves since they may need to lock | |
| // the cache mutex. | |
| UnifiedCache::copyPtr((const SharedObject *) element->value.pointer, 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; | |
| UErrorCode status = U_ZERO_ERROR; | |
| _fetch(element, value, status); | |
| UBool result = _inProgress(value, status); | |
| // Since we have the cache lock, calling regular SharedObject methods | |
| // could cause us to deadlock on ourselves since they may need to lock | |
| // the cache mutex. | |
| UnifiedCache::clearPtr(value); | |
| return result; | |
| } | |
| // Determine if given hash entry is in progress. | |
| // On entry, gCacheMutex must be held. | |
| UBool UnifiedCache::_inProgress( | |
| const SharedObject *theValue, UErrorCode creationStatus) { | |
| return (theValue == gNoValue && creationStatus == U_ZERO_ERROR); | |
| } | |
| // Determine if given hash entry is eligible for eviction. | |
| // On entry, gCacheMutex must be held. | |
| UBool UnifiedCache::_isEvictable(const UHashElement *element) { | |
| 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->getSoftRefCount() == 1 && theValue->noHardReferences())); | |
| } | |
| U_NAMESPACE_END |