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 556