source/common/unifiedcache.cpp

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