icuSources/common/unifiedcache.cpp

   1 /*
   2 ******************************************************************************
   3 * Copyright (C) 2015, International Business Machines Corporation and
   4 * others. All Rights Reserved.
   5 ******************************************************************************
   6 *
   7 * File UNIFIEDCACHE.CPP
   8 ******************************************************************************
   9 */
  10
  11 #include "uhash.h"
  12 #include "unifiedcache.h"
  13 #include "umutex.h"
  14 #include "mutex.h"
  15 #include "uassert.h"
  16 #include "ucln_cmn.h"
  17
  18 static icu::UnifiedCache *gCache = NULL;
  19 static icu::SharedObject *gNoValue = NULL;
  20 static UMutex gCacheMutex = U_MUTEX_INITIALIZER;
  21 static UConditionVar gInProgressValueAddedCond = U_CONDITION_INITIALIZER;
  22 static icu::UInitOnce gCacheInitOnce = U_INITONCE_INITIALIZER;
  23 static const int32_t MAX_EVICT_ITERATIONS = 10;
  24
  25 static int32_t DEFAULT_MAX_UNUSED = 1000;
  26 static int32_t DEFAULT_PERCENTAGE_OF_IN_USE = 100;
  27
  28
  29 U_CDECL_BEGIN
  30 static UBool U_CALLCONV unifiedcache_cleanup() {
  31     gCacheInitOnce.reset();
  32     if (gCache) {
  33         delete gCache;
  34         gCache = NULL;
  35     }
  36     if (gNoValue) {
  37         delete gNoValue;
  38         gNoValue = NULL;
  39     }
  40     return TRUE;
  41 }
  42 U_CDECL_END
  43
  44
  45 U_NAMESPACE_BEGIN
  46
  47 U_CAPI int32_t U_EXPORT2
  48 ucache_hashKeys(const UHashTok key) {
  49     const CacheKeyBase *ckey = (const CacheKeyBase *) key.pointer;
  50     return ckey->hashCode();
  51 }
  52
  53 U_CAPI UBool U_EXPORT2
  54 ucache_compareKeys(const UHashTok key1, const UHashTok key2) {
  55     const CacheKeyBase *p1 = (const CacheKeyBase *) key1.pointer;
  56     const CacheKeyBase *p2 = (const CacheKeyBase *) key2.pointer;
  57     return *p1 == *p2;
  58 }
  59
  60 U_CAPI void U_EXPORT2
  61 ucache_deleteKey(void *obj) {
  62     CacheKeyBase *p = (CacheKeyBase *) obj;
  63     delete p;
  64 }
  65
  66 CacheKeyBase::~CacheKeyBase() {
  67 }
  68
  69 static void U_CALLCONV cacheInit(UErrorCode &status) {
  70     U_ASSERT(gCache == NULL);
  71     ucln_common_registerCleanup(
  72             UCLN_COMMON_UNIFIED_CACHE, unifiedcache_cleanup);
  73
  74     // gNoValue must be created first to avoid assertion error in
  75     // cache constructor.
  76     gNoValue = new SharedObject();
  77     gCache = new UnifiedCache(status);
  78     if (gCache == NULL) {
  79         status = U_MEMORY_ALLOCATION_ERROR;
  80     }
  81     if (U_FAILURE(status)) {
  82         delete gCache;
  83         delete gNoValue;
  84         gCache = NULL;
  85         gNoValue = NULL;
  86         return;
  87     }
  88     // We add a softref because we want hash elements with gNoValue to be
  89     // elligible for purging but we don't ever want gNoValue to be deleted.
  90     gNoValue->addSoftRef();
  91 }
  92
  93 UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) {
  94     umtx_initOnce(gCacheInitOnce, &cacheInit, status);
  95     if (U_FAILURE(status)) {
  96         return NULL;
  97     }
  98     U_ASSERT(gCache != NULL);
  99     return gCache;
 100 }
 101
 102 UnifiedCache::UnifiedCache(UErrorCode &status) :
 103         fHashtable(NULL),
 104         fEvictPos(UHASH_FIRST),
 105         fItemsInUseCount(0),
 106         fMaxUnused(DEFAULT_MAX_UNUSED),
 107         fMaxPercentageOfInUse(DEFAULT_PERCENTAGE_OF_IN_USE),
 108         fAutoEvictedCount(0) {
 109     if (U_FAILURE(status)) {
 110         return;
 111     }
 112     U_ASSERT(gNoValue != NULL);
 113     fHashtable = uhash_open(
 114             &ucache_hashKeys,
 115             &ucache_compareKeys,
 116             NULL,
 117             &status);
 118     if (U_FAILURE(status)) {
 119         return;
 120     }
 121     uhash_setKeyDeleter(fHashtable, &ucache_deleteKey);
 122 }
 123
 124 void UnifiedCache::setEvictionPolicy(
 125         int32_t count, int32_t percentageOfInUseItems, UErrorCode &status) {
 126     if (U_FAILURE(status)) {
 127         return;
 128     }
 129     if (count < 0 || percentageOfInUseItems < 0) {
 130         status = U_ILLEGAL_ARGUMENT_ERROR;
 131         return;
 132     }
 133     Mutex lock(&gCacheMutex);
 134     fMaxUnused = count;
 135     fMaxPercentageOfInUse = percentageOfInUseItems;
 136 }
 137
 138 int32_t UnifiedCache::unusedCount() const {
 139     Mutex lock(&gCacheMutex);
 140     return uhash_count(fHashtable) - fItemsInUseCount;
 141 }
 142
 143 int64_t UnifiedCache::autoEvictedCount() const {
 144     Mutex lock(&gCacheMutex);
 145     return fAutoEvictedCount;
 146 }
 147
 148 int32_t UnifiedCache::keyCount() const {
 149     Mutex lock(&gCacheMutex);
 150     return uhash_count(fHashtable);
 151 }
 152
 153 void UnifiedCache::flush() const {
 154     Mutex lock(&gCacheMutex);
 155
 156     // Use a loop in case cache items that are flushed held hard references to
 157     // other cache items making those additional cache items eligible for
 158     // flushing.
 159     while (_flush(FALSE));
 160 }
 161
 162 #ifdef UNIFIED_CACHE_DEBUG
 163 #include <stdio.h>
 164
 165 void UnifiedCache::dump() {
 166     UErrorCode status = U_ZERO_ERROR;
 167     const UnifiedCache *cache = getInstance(status);
 168     if (U_FAILURE(status)) {
 169         fprintf(stderr, "Unified Cache: Error fetching cache.\n");
 170         return;
 171     }
 172     cache->dumpContents();
 173 }
 174
 175 void UnifiedCache::dumpContents() const {
 176     Mutex lock(&gCacheMutex);
 177     _dumpContents();
 178 }
 179
 180 // Dumps content of cache.
 181 // On entry, gCacheMutex must be held.
 182 // On exit, cache contents dumped to stderr.
 183 void UnifiedCache::_dumpContents() const {
 184     int32_t pos = UHASH_FIRST;
 185     const UHashElement *element = uhash_nextElement(fHashtable, &pos);
 186     char buffer[256];
 187     int32_t cnt = 0;
 188     for (; element != NULL; element = uhash_nextElement(fHashtable, &pos)) {
 189         const SharedObject *sharedObject =
 190                 (const SharedObject *) element->value.pointer;
 191         const CacheKeyBase *key =
 192                 (const CacheKeyBase *) element->key.pointer;
 193         if (sharedObject->hasHardReferences()) {
 194             ++cnt;
 195             fprintf(
 196                     stderr,
 197                     "Unified Cache: Key '%s', error %d, value %p, total refcount %d, soft refcount %d\n",
 198                     key->writeDescription(buffer, 256),
 199                     key->creationStatus,
 200                     sharedObject == gNoValue ? NULL :sharedObject,
 201                     sharedObject->getRefCount(),
 202                     sharedObject->getSoftRefCount());
 203         }
 204     }
 205     fprintf(stderr, "Unified Cache: %d out of a total of %d still have hard references\n", cnt, uhash_count(fHashtable));
 206 }
 207 #endif
 208
 209 UnifiedCache::~UnifiedCache() {
 210     // Try our best to clean up first.
 211     flush();
 212     {
 213         // Now all that should be left in the cache are entries that refer to
 214         // each other and entries with hard references from outside the cache.
 215         // Nothing we can do about these so proceed to wipe out the cache.
 216         Mutex lock(&gCacheMutex);
 217         _flush(TRUE);
 218     }
 219     uhash_close(fHashtable);
 220 }
 221
 222 // Returns the next element in the cache round robin style.
 223 // On entry, gCacheMutex must be held.
 224 const UHashElement *
 225 UnifiedCache::_nextElement() const {
 226     const UHashElement *element = uhash_nextElement(fHashtable, &fEvictPos);
 227     if (element == NULL) {
 228         fEvictPos = UHASH_FIRST;
 229         return uhash_nextElement(fHashtable, &fEvictPos);
 230     }
 231     return element;
 232 }
 233
 234 // Flushes the contents of the cache. If cache values hold references to other
 235 // cache values then _flush should be called in a loop until it returns FALSE.
 236 // On entry, gCacheMutex must be held.
 237 // On exit, those values with are evictable are flushed. If all is true
 238 // then every value is flushed even if it is not evictable.
 239 // Returns TRUE if any value in cache was flushed or FALSE otherwise.
 240 UBool UnifiedCache::_flush(UBool all) const {
 241     UBool result = FALSE;
 242     int32_t origSize = uhash_count(fHashtable);
 243     for (int32_t i = 0; i < origSize; ++i) {
 244         const UHashElement *element = _nextElement();
 245         if (all || _isEvictable(element)) {
 246             const SharedObject *sharedObject =
 247                     (const SharedObject *) element->value.pointer;
 248             uhash_removeElement(fHashtable, element);
 249             sharedObject->removeSoftRef();
 250             result = TRUE;
 251         }
 252     }
 253     return result;
 254 }
 255
 256 // Computes how many items should be evicted.
 257 // On entry, gCacheMutex must be held.
 258 // Returns number of items that should be evicted or a value <= 0 if no
 259 // items need to be evicted.
 260 int32_t UnifiedCache::_computeCountOfItemsToEvict() const {
 261     int32_t maxPercentageOfInUseCount =
 262             fItemsInUseCount * fMaxPercentageOfInUse / 100;
 263     int32_t maxUnusedCount = fMaxUnused;
 264     if (maxUnusedCount < maxPercentageOfInUseCount) {
 265         maxUnusedCount = maxPercentageOfInUseCount;
 266     }
 267     return uhash_count(fHashtable) - fItemsInUseCount - maxUnusedCount;
 268 }
 269
 270 // Run an eviction slice.
 271 // On entry, gCacheMutex must be held.
 272 // _runEvictionSlice runs a slice of the evict pipeline by examining the next
 273 // 10 entries in the cache round robin style evicting them if they are eligible.
 274 void UnifiedCache::_runEvictionSlice() const {
 275     int32_t maxItemsToEvict = _computeCountOfItemsToEvict();
 276     if (maxItemsToEvict <= 0) {
 277         return;
 278     }
 279     for (int32_t i = 0; i < MAX_EVICT_ITERATIONS; ++i) {
 280         const UHashElement *element = _nextElement();
 281         if (_isEvictable(element)) {
 282             const SharedObject *sharedObject =
 283                     (const SharedObject *) element->value.pointer;
 284             uhash_removeElement(fHashtable, element);
 285             sharedObject->removeSoftRef();
 286             ++fAutoEvictedCount;
 287             if (--maxItemsToEvict == 0) {
 288                 break;
 289             }
 290         }
 291     }
 292 }
 293
 294
 295 // Places a new value and creationStatus in the cache for the given key.
 296 // On entry, gCacheMutex must be held. key must not exist in the cache.
 297 // On exit, value and creation status placed under key. Soft reference added
 298 // to value on successful add. On error sets status.
 299 void UnifiedCache::_putNew(
 300         const CacheKeyBase &key,
 301         const SharedObject *value,
 302         const UErrorCode creationStatus,
 303         UErrorCode &status) const {
 304     if (U_FAILURE(status)) {
 305         return;
 306     }
 307     CacheKeyBase *keyToAdopt = key.clone();
 308     if (keyToAdopt == NULL) {
 309         status = U_MEMORY_ALLOCATION_ERROR;
 310         return;
 311     }
 312     keyToAdopt->fCreationStatus = creationStatus;
 313     if (value->noSoftReferences()) {
 314         _registerMaster(keyToAdopt, value);
 315     }
 316     uhash_put(fHashtable, keyToAdopt, (void *) value, &status);
 317     if (U_SUCCESS(status)) {
 318         value->addSoftRef();
 319     }
 320 }
 321
 322 // Places value and status at key if there is no value at key or if cache
 323 // entry for key is in progress. Otherwise, it leaves the current value and
 324 // status there.
 325 // On entry. gCacheMutex must not be held. value must be
 326 // included in the reference count of the object to which it points.
 327 // On exit, value and status are changed to what was already in the cache if
 328 // something was there and not in progress. Otherwise, value and status are left
 329 // unchanged in which case they are placed in the cache on a best-effort basis.
 330 // Caller must call removeRef() on value.
 331 void UnifiedCache::_putIfAbsentAndGet(
 332         const CacheKeyBase &key,
 333         const SharedObject *&value,
 334         UErrorCode &status) const {
 335     Mutex lock(&gCacheMutex);
 336     const UHashElement *element = uhash_find(fHashtable, &key);
 337     if (element != NULL && !_inProgress(element)) {
 338         _fetch(element, value, status);
 339         return;
 340     }
 341     if (element == NULL) {
 342         UErrorCode putError = U_ZERO_ERROR;
 343         // best-effort basis only.
 344         _putNew(key, value, status, putError);
 345     } else {
 346         _put(element, value, status);
 347     }
 348     // Run an eviction slice. This will run even if we added a master entry
 349     // which doesn't increase the unused count, but that is still o.k
 350     _runEvictionSlice();
 351 }
 352
 353 // Attempts to fetch value and status for key from cache.
 354 // On entry, gCacheMutex must not be held value must be NULL and status must
 355 // be U_ZERO_ERROR.
 356 // On exit, either returns FALSE (In this
 357 // case caller should try to create the object) or returns TRUE with value
 358 // pointing to the fetched value and status set to fetched status. When
 359 // FALSE is returned status may be set to failure if an in progress hash
 360 // entry could not be made but value will remain unchanged. When TRUE is
 361 // returned, caler must call removeRef() on value.
 362 UBool UnifiedCache::_poll(
 363         const CacheKeyBase &key,
 364         const SharedObject *&value,
 365         UErrorCode &status) const {
 366     U_ASSERT(value == NULL);
 367     U_ASSERT(status == U_ZERO_ERROR);
 368     Mutex lock(&gCacheMutex);
 369     const UHashElement *element = uhash_find(fHashtable, &key);
 370     while (element != NULL && _inProgress(element)) {
 371         umtx_condWait(&gInProgressValueAddedCond, &gCacheMutex);
 372         element = uhash_find(fHashtable, &key);
 373     }
 374     if (element != NULL) {
 375         _fetch(element, value, status);
 376         return TRUE;
 377     }
 378     _putNew(key, gNoValue, U_ZERO_ERROR, status);
 379     return FALSE;
 380 }
 381
 382 // Gets value out of cache.
 383 // On entry. gCacheMutex must not be held. value must be NULL. status
 384 // must be U_ZERO_ERROR.
 385 // On exit. value and status set to what is in cache at key or on cache
 386 // miss the key's createObject() is called and value and status are set to
 387 // the result of that. In this latter case, best effort is made to add the
 388 // value and status to the cache. If createObject() fails to create a value,
 389 // gNoValue is stored in cache, and value is set to NULL. Caller must call
 390 // removeRef on value if non NULL.
 391 void UnifiedCache::_get(
 392         const CacheKeyBase &key,
 393         const SharedObject *&value,
 394         const void *creationContext,
 395         UErrorCode &status) const {
 396     U_ASSERT(value == NULL);
 397     U_ASSERT(status == U_ZERO_ERROR);
 398     if (_poll(key, value, status)) {
 399         if (value == gNoValue) {
 400             SharedObject::clearPtr(value);
 401         }
 402         return;
 403     }
 404     if (U_FAILURE(status)) {
 405         return;
 406     }
 407     value = key.createObject(creationContext, status);
 408     U_ASSERT(value == NULL || value->hasHardReferences());
 409     U_ASSERT(value != NULL || status != U_ZERO_ERROR);
 410     if (value == NULL) {
 411         SharedObject::copyPtr(gNoValue, value);
 412     }
 413     _putIfAbsentAndGet(key, value, status);
 414     if (value == gNoValue) {
 415         SharedObject::clearPtr(value);
 416     }
 417 }
 418
 419 void UnifiedCache::decrementItemsInUseWithLockingAndEviction() const {
 420     Mutex mutex(&gCacheMutex);
 421     decrementItemsInUse();
 422     _runEvictionSlice();
 423 }
 424
 425 void UnifiedCache::incrementItemsInUse() const {
 426     ++fItemsInUseCount;
 427 }
 428
 429 void UnifiedCache::decrementItemsInUse() const {
 430     --fItemsInUseCount;
 431 }
 432
 433 // Register a master cache entry.
 434 // On entry, gCacheMutex must be held.
 435 // On exit, items in use count incremented, entry is marked as a master
 436 // entry, and value registered with cache so that subsequent calls to
 437 // addRef() and removeRef() on it correctly updates items in use count
 438 void UnifiedCache::_registerMaster(
 439         const CacheKeyBase *theKey, const SharedObject *value) const {
 440     theKey->fIsMaster = TRUE;
 441     ++fItemsInUseCount;
 442     value->registerWithCache(this);
 443 }
 444
 445 // Store a value and error in given hash entry.
 446 // On entry, gCacheMutex must be held. Hash entry element must be in progress.
 447 // value must be non NULL.
 448 // On Exit, soft reference added to value. value and status stored in hash
 449 // entry. Soft reference removed from previous stored value. Waiting
 450 // threads notified.
 451 void UnifiedCache::_put(
 452         const UHashElement *element,
 453         const SharedObject *value,
 454         const UErrorCode status) const {
 455     U_ASSERT(_inProgress(element));
 456     const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
 457     const SharedObject *oldValue = (const SharedObject *) element->value.pointer;
 458     theKey->fCreationStatus = status;
 459     if (value->noSoftReferences()) {
 460         _registerMaster(theKey, value);
 461     }
 462     value->addSoftRef();
 463     UHashElement *ptr = const_cast<UHashElement *>(element);
 464     ptr->value.pointer = (void *) value;
 465     oldValue->removeSoftRef();
 466
 467     // Tell waiting threads that we replace in-progress status with
 468     // an error.
 469     umtx_condBroadcast(&gInProgressValueAddedCond);
 470 }
 471
 472 void
 473 UnifiedCache::copyPtr(const SharedObject *src, const SharedObject *&dest) {
 474     if(src != dest) {
 475         if(dest != NULL) {
 476             dest->removeRefWhileHoldingCacheLock();
 477         }
 478         dest = src;
 479         if(src != NULL) {
 480             src->addRefWhileHoldingCacheLock();
 481         }
 482     }
 483 }
 484
 485 void
 486 UnifiedCache::clearPtr(const SharedObject *&ptr) {
 487     if (ptr != NULL) {
 488         ptr->removeRefWhileHoldingCacheLock();
 489         ptr = NULL;
 490     }
 491 }
 492
 493
 494 // Fetch value and error code from a particular hash entry.
 495 // On entry, gCacheMutex must be held. value must be either NULL or must be
 496 // included in the ref count of the object to which it points.
 497 // On exit, value and status set to what is in the hash entry. Caller must
 498 // eventually call removeRef on value.
 499 // If hash entry is in progress, value will be set to gNoValue and status will
 500 // be set to U_ZERO_ERROR.
 501 void UnifiedCache::_fetch(
 502         const UHashElement *element,
 503         const SharedObject *&value,
 504         UErrorCode &status) {
 505     const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
 506     status = theKey->fCreationStatus;
 507
 508     // Since we have the cache lock, calling regular SharedObject methods
 509     // could cause us to deadlock on ourselves since they may need to lock
 510     // the cache mutex.
 511     UnifiedCache::copyPtr((const SharedObject *) element->value.pointer, value);
 512 }
 513
 514 // Determine if given hash entry is in progress.
 515 // On entry, gCacheMutex must be held.
 516 UBool UnifiedCache::_inProgress(const UHashElement *element) {
 517     const SharedObject *value = NULL;
 518     UErrorCode status = U_ZERO_ERROR;
 519     _fetch(element, value, status);
 520     UBool result = _inProgress(value, status);
 521
 522     // Since we have the cache lock, calling regular SharedObject methods
 523     // could cause us to deadlock on ourselves since they may need to lock
 524     // the cache mutex.
 525     UnifiedCache::clearPtr(value);
 526     return result;
 527 }
 528
 529 // Determine if given hash entry is in progress.
 530 // On entry, gCacheMutex must be held.
 531 UBool UnifiedCache::_inProgress(
 532         const SharedObject *theValue, UErrorCode creationStatus) {
 533     return (theValue == gNoValue && creationStatus == U_ZERO_ERROR);
 534 }
 535
 536 // Determine if given hash entry is eligible for eviction.
 537 // On entry, gCacheMutex must be held.
 538 UBool UnifiedCache::_isEvictable(const UHashElement *element) {
 539     const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
 540     const SharedObject *theValue =
 541             (const SharedObject *) element->value.pointer;
 542
 543     // Entries that are under construction are never evictable
 544     if (_inProgress(theValue, theKey->fCreationStatus)) {
 545         return FALSE;
 546     }
 547
 548     // We can evict entries that are either not a master or have just
 549     // one reference (The one reference being from the cache itself).
 550     return (!theKey->fIsMaster || (theValue->getSoftRefCount() == 1 && theValue->noHardReferences()));
 551 }
 552
 553 U_NAMESPACE_END