ICU-57132.0.1.tar.gz

[apple/icu.git] / icuSources / common / unifiedcache.cpp

diff --git a/icuSources/common/unifiedcache.cpp b/icuSources/common/unifiedcache.cpp
index 32899af73e944aed618cd344567fb101435f4acb..5b429790c2dcfa956ae6d9ded9d477fbb51a61ac 100644 (file)
--- a/icuSources/common/unifiedcache.cpp
+++ b/icuSources/common/unifiedcache.cpp
@@ -1,6 +1,6 @@
 /*
 ******************************************************************************
 /*
 ******************************************************************************

-* Copyright (C) 2014, International Business Machines Corporation and         
+* Copyright (C) 2015, International Business Machines Corporation and         

 * others. All Rights Reserved.                                                
 ******************************************************************************
 *                                                                             
 * others. All Rights Reserved.                                                
 ******************************************************************************
 *                                                                             


@@ -20,6 +20,11 @@ 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 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() {
 
 U_CDECL_BEGIN
 static UBool U_CALLCONV unifiedcache_cleanup() {


@@ -85,7 +90,7 @@ static void U_CALLCONV cacheInit(UErrorCode &status) {
     gNoValue->addSoftRef();
 }
 
     gNoValue->addSoftRef();
 }
 

-const UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) {
+UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) {

     umtx_initOnce(gCacheInitOnce, &cacheInit, status);
     if (U_FAILURE(status)) {
         return NULL;
     umtx_initOnce(gCacheInitOnce, &cacheInit, status);
     if (U_FAILURE(status)) {
         return NULL;


@@ -94,7 +99,13 @@ const UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) {
     return gCache;
 }
 
     return gCache;
 }
 

-UnifiedCache::UnifiedCache(UErrorCode &status) {
+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;
     }
     if (U_FAILURE(status)) {
         return;
     }


@@ -110,6 +121,30 @@ UnifiedCache::UnifiedCache(UErrorCode &status) {
     uhash_setKeyDeleter(fHashtable, &ucache_deleteKey);
 }
 
     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);
 int32_t UnifiedCache::keyCount() const {
     Mutex lock(&gCacheMutex);
     return uhash_count(fHashtable);


@@ -122,7 +157,6 @@ void UnifiedCache::flush() const {
     // other cache items making those additional cache items eligible for
     // flushing.
     while (_flush(FALSE));
     // other cache items making those additional cache items eligible for
     // flushing.
     while (_flush(FALSE));

-    umtx_condBroadcast(&gInProgressValueAddedCond);

 }
 
 #ifdef UNIFIED_CACHE_DEBUG
 }
 
 #ifdef UNIFIED_CACHE_DEBUG


@@ -156,7 +190,7 @@ void UnifiedCache::_dumpContents() const {
                 (const SharedObject *) element->value.pointer;
         const CacheKeyBase *key =
                 (const CacheKeyBase *) element->key.pointer;
                 (const SharedObject *) element->value.pointer;
         const CacheKeyBase *key =
                 (const CacheKeyBase *) element->key.pointer;

-        if (!sharedObject->allSoftReferences()) {
+        if (sharedObject->hasHardReferences()) {

             ++cnt;
             fprintf(
                     stderr,
             ++cnt;
             fprintf(
                     stderr,


@@ -185,20 +219,32 @@ UnifiedCache::~UnifiedCache() {
     uhash_close(fHashtable);
 }
 
     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.
 // 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.
+// 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;
 // 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 (all || _isEvictable(element)) {
+            const SharedObject *sharedObject =
+                    (const SharedObject *) element->value.pointer;

             uhash_removeElement(fHashtable, element);
             sharedObject->removeSoftRef();
             result = TRUE;
             uhash_removeElement(fHashtable, element);
             sharedObject->removeSoftRef();
             result = TRUE;


@@ -207,6 +253,45 @@ UBool UnifiedCache::_flush(UBool all) const {
     return result;
 }
 
     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
 // 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


@@ -224,7 +309,10 @@ void UnifiedCache::_putNew(
         status = U_MEMORY_ALLOCATION_ERROR;
         return;
     }
         status = U_MEMORY_ALLOCATION_ERROR;
         return;
     }

-    keyToAdopt->creationStatus = creationStatus;
+    keyToAdopt->fCreationStatus = creationStatus;
+    if (value->noSoftReferences()) {
+        _registerMaster(keyToAdopt, value);
+    }

     uhash_put(fHashtable, keyToAdopt, (void *) value, &status);
     if (U_SUCCESS(status)) {
         value->addSoftRef();
     uhash_put(fHashtable, keyToAdopt, (void *) value, &status);
     if (U_SUCCESS(status)) {
         value->addSoftRef();


@@ -254,9 +342,12 @@ void UnifiedCache::_putIfAbsentAndGet(
         UErrorCode putError = U_ZERO_ERROR;
         // best-effort basis only.
         _putNew(key, value, status, putError);
         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.
 }
 
 // Attempts to fetch value and status for key from cache.


@@ -294,8 +385,9 @@ UBool UnifiedCache::_poll(
 // 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
 // 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.
+// 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,
 void UnifiedCache::_get(
         const CacheKeyBase &key,
         const SharedObject *&value,


@@ -313,7 +405,7 @@ void UnifiedCache::_get(
         return;
     }
     value = key.createObject(creationContext, status);
         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);
     U_ASSERT(value != NULL || status != U_ZERO_ERROR);
     if (value == NULL) {
         SharedObject::copyPtr(gNoValue, value);


@@ -324,6 +416,32 @@ void UnifiedCache::_get(
     }
 }
 
     }
 }
 

+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.
 // 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.


@@ -333,11 +451,14 @@ void UnifiedCache::_get(
 void UnifiedCache::_put(
         const UHashElement *element, 
         const SharedObject *value,
 void UnifiedCache::_put(
         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;
     U_ASSERT(_inProgress(element));
     const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
     const SharedObject *oldValue = (const SharedObject *) element->value.pointer;

-    theKey->creationStatus = status;
+    theKey->fCreationStatus = status;
+    if (value->noSoftReferences()) {
+        _registerMaster(theKey, value);
+    }

     value->addSoftRef();
     UHashElement *ptr = const_cast<UHashElement *>(element);
     ptr->value.pointer = (void *) value;
     value->addSoftRef();
     UHashElement *ptr = const_cast<UHashElement *>(element);
     ptr->value.pointer = (void *) value;


@@ -348,6 +469,28 @@ void UnifiedCache::_put(
     umtx_condBroadcast(&gInProgressValueAddedCond);
 }
 
     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.
 // 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.


@@ -360,20 +503,51 @@ void UnifiedCache::_fetch(
         const SharedObject *&value,
         UErrorCode &status) {
     const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
         const SharedObject *&value,
         UErrorCode &status) {
     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 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);
 // 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 = (value == gNoValue && status == U_ZERO_ERROR);
-    SharedObject::clearPtr(value);
+    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;
 }
 
     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
 U_NAMESPACE_END