1 // © 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 "unifiedcache.h"
14
15 #include <algorithm> // For std::max()
16 #ifndef __wasi__
17 #include <mutex>
18 #endif
19
20 #include "uassert.h"
21 #include "uhash.h"
22 #include "ucln_cmn.h"
23
24 static icu::UnifiedCache *gCache = NULL;
25 #ifndef __wasi__
26 static std::mutex *gCacheMutex = nullptr;
27 static std::condition_variable *gInProgressValueAddedCond;
28 #endif
29 static icu::UInitOnce gCacheInitOnce = U_INITONCE_INITIALIZER;
30
31 static const int32_t MAX_EVICT_ITERATIONS = 10;
32 static const int32_t DEFAULT_MAX_UNUSED = 1000;
33 static const int32_t DEFAULT_PERCENTAGE_OF_IN_USE = 100;
34
35
36 U_CDECL_BEGIN
unifiedcache_cleanup()37 static UBool U_CALLCONV unifiedcache_cleanup() {
38 gCacheInitOnce.reset();
39 delete gCache;
40 gCache = nullptr;
41 #ifndef __wasi__
42 gCacheMutex->~mutex();
43 gCacheMutex = nullptr;
44 gInProgressValueAddedCond->~condition_variable();
45 gInProgressValueAddedCond = nullptr;
46 #endif
47 return TRUE;
48 }
49 U_CDECL_END
50
51
52 U_NAMESPACE_BEGIN
53
54 U_CAPI int32_t U_EXPORT2
ucache_hashKeys(const UHashTok key)55 ucache_hashKeys(const UHashTok key) {
56 const CacheKeyBase *ckey = (const CacheKeyBase *) key.pointer;
57 return ckey->hashCode();
58 }
59
60 U_CAPI UBool U_EXPORT2
ucache_compareKeys(const UHashTok key1,const UHashTok key2)61 ucache_compareKeys(const UHashTok key1, const UHashTok key2) {
62 const CacheKeyBase *p1 = (const CacheKeyBase *) key1.pointer;
63 const CacheKeyBase *p2 = (const CacheKeyBase *) key2.pointer;
64 return *p1 == *p2;
65 }
66
67 U_CAPI void U_EXPORT2
ucache_deleteKey(void * obj)68 ucache_deleteKey(void *obj) {
69 CacheKeyBase *p = (CacheKeyBase *) obj;
70 delete p;
71 }
72
~CacheKeyBase()73 CacheKeyBase::~CacheKeyBase() {
74 }
75
cacheInit(UErrorCode & status)76 static void U_CALLCONV cacheInit(UErrorCode &status) {
77 U_ASSERT(gCache == NULL);
78 ucln_common_registerCleanup(
79 UCLN_COMMON_UNIFIED_CACHE, unifiedcache_cleanup);
80
81 #ifndef __wasi__
82 gCacheMutex = STATIC_NEW(std::mutex);
83 gInProgressValueAddedCond = STATIC_NEW(std::condition_variable);
84 #endif
85 gCache = new UnifiedCache(status);
86 if (gCache == NULL) {
87 status = U_MEMORY_ALLOCATION_ERROR;
88 }
89 if (U_FAILURE(status)) {
90 delete gCache;
91 gCache = NULL;
92 return;
93 }
94 }
95
getInstance(UErrorCode & status)96 UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) {
97 umtx_initOnce(gCacheInitOnce, &cacheInit, status);
98 if (U_FAILURE(status)) {
99 return NULL;
100 }
101 U_ASSERT(gCache != NULL);
102 return gCache;
103 }
104
UnifiedCache(UErrorCode & status)105 UnifiedCache::UnifiedCache(UErrorCode &status) :
106 fHashtable(NULL),
107 fEvictPos(UHASH_FIRST),
108 fNumValuesTotal(0),
109 fNumValuesInUse(0),
110 fMaxUnused(DEFAULT_MAX_UNUSED),
111 fMaxPercentageOfInUse(DEFAULT_PERCENTAGE_OF_IN_USE),
112 fAutoEvictedCount(0),
113 fNoValue(nullptr) {
114 if (U_FAILURE(status)) {
115 return;
116 }
117 fNoValue = new SharedObject();
118 if (fNoValue == nullptr) {
119 status = U_MEMORY_ALLOCATION_ERROR;
120 return;
121 }
122 fNoValue->softRefCount = 1; // Add fake references to prevent fNoValue from being deleted
123 fNoValue->hardRefCount = 1; // when other references to it are removed.
124 fNoValue->cachePtr = this;
125
126 fHashtable = uhash_open(
127 &ucache_hashKeys,
128 &ucache_compareKeys,
129 NULL,
130 &status);
131 if (U_FAILURE(status)) {
132 return;
133 }
134 uhash_setKeyDeleter(fHashtable, &ucache_deleteKey);
135 }
136
setEvictionPolicy(int32_t count,int32_t percentageOfInUseItems,UErrorCode & status)137 void UnifiedCache::setEvictionPolicy(
138 int32_t count, int32_t percentageOfInUseItems, UErrorCode &status) {
139 if (U_FAILURE(status)) {
140 return;
141 }
142 if (count < 0 || percentageOfInUseItems < 0) {
143 status = U_ILLEGAL_ARGUMENT_ERROR;
144 return;
145 }
146 #ifndef __wasi__
147 std::lock_guard<std::mutex> lock(*gCacheMutex);
148 #endif
149 fMaxUnused = count;
150 fMaxPercentageOfInUse = percentageOfInUseItems;
151 }
152
unusedCount() const153 int32_t UnifiedCache::unusedCount() const {
154 #ifndef __wasi__
155 std::lock_guard<std::mutex> lock(*gCacheMutex);
156 #endif
157 return uhash_count(fHashtable) - fNumValuesInUse;
158 }
159
autoEvictedCount() const160 int64_t UnifiedCache::autoEvictedCount() const {
161 #ifndef __wasi__
162 std::lock_guard<std::mutex> lock(*gCacheMutex);
163 #endif
164 return fAutoEvictedCount;
165 }
166
keyCount() const167 int32_t UnifiedCache::keyCount() const {
168 #ifndef __wasi__
169 std::lock_guard<std::mutex> lock(*gCacheMutex);
170 #endif
171 return uhash_count(fHashtable);
172 }
173
flush() const174 void UnifiedCache::flush() const {
175 #ifndef __wasi__
176 std::lock_guard<std::mutex> lock(*gCacheMutex);
177 #endif
178
179 // Use a loop in case cache items that are flushed held hard references to
180 // other cache items making those additional cache items eligible for
181 // flushing.
182 while (_flush(FALSE));
183 }
184
handleUnreferencedObject() const185 void UnifiedCache::handleUnreferencedObject() const {
186 #ifndef __wasi__
187 std::lock_guard<std::mutex> lock(*gCacheMutex);
188 #endif
189 --fNumValuesInUse;
190 _runEvictionSlice();
191 }
192
193 #ifdef UNIFIED_CACHE_DEBUG
194 #include <stdio.h>
195
dump()196 void UnifiedCache::dump() {
197 UErrorCode status = U_ZERO_ERROR;
198 const UnifiedCache *cache = getInstance(status);
199 if (U_FAILURE(status)) {
200 fprintf(stderr, "Unified Cache: Error fetching cache.\n");
201 return;
202 }
203 cache->dumpContents();
204 }
205
dumpContents() const206 void UnifiedCache::dumpContents() const {
207 #ifndef __wasi__
208 std::lock_guard<std::mutex> lock(*gCacheMutex);
209 #endif
210 _dumpContents();
211 }
212
213 // Dumps content of cache.
214 // On entry, gCacheMutex must be held.
215 // On exit, cache contents dumped to stderr.
_dumpContents() const216 void UnifiedCache::_dumpContents() const {
217 int32_t pos = UHASH_FIRST;
218 const UHashElement *element = uhash_nextElement(fHashtable, &pos);
219 char buffer[256];
220 int32_t cnt = 0;
221 for (; element != NULL; element = uhash_nextElement(fHashtable, &pos)) {
222 const SharedObject *sharedObject =
223 (const SharedObject *) element->value.pointer;
224 const CacheKeyBase *key =
225 (const CacheKeyBase *) element->key.pointer;
226 if (sharedObject->hasHardReferences()) {
227 ++cnt;
228 fprintf(
229 stderr,
230 "Unified Cache: Key '%s', error %d, value %p, total refcount %d, soft refcount %d\n",
231 key->writeDescription(buffer, 256),
232 key->creationStatus,
233 sharedObject == fNoValue ? NULL :sharedObject,
234 sharedObject->getRefCount(),
235 sharedObject->getSoftRefCount());
236 }
237 }
238 fprintf(stderr, "Unified Cache: %d out of a total of %d still have hard references\n", cnt, uhash_count(fHashtable));
239 }
240 #endif
241
~UnifiedCache()242 UnifiedCache::~UnifiedCache() {
243 // Try our best to clean up first.
244 flush();
245 {
246 // Now all that should be left in the cache are entries that refer to
247 // each other and entries with hard references from outside the cache.
248 // Nothing we can do about these so proceed to wipe out the cache.
249 #ifndef __wasi__
250 std::lock_guard<std::mutex> lock(*gCacheMutex);
251 #endif
252 _flush(TRUE);
253 }
254 uhash_close(fHashtable);
255 fHashtable = nullptr;
256 delete fNoValue;
257 fNoValue = nullptr;
258 }
259
260 const UHashElement *
_nextElement() const261 UnifiedCache::_nextElement() const {
262 const UHashElement *element = uhash_nextElement(fHashtable, &fEvictPos);
263 if (element == NULL) {
264 fEvictPos = UHASH_FIRST;
265 return uhash_nextElement(fHashtable, &fEvictPos);
266 }
267 return element;
268 }
269
_flush(UBool all) const270 UBool UnifiedCache::_flush(UBool all) const {
271 UBool result = FALSE;
272 int32_t origSize = uhash_count(fHashtable);
273 for (int32_t i = 0; i < origSize; ++i) {
274 const UHashElement *element = _nextElement();
275 if (element == nullptr) {
276 break;
277 }
278 if (all || _isEvictable(element)) {
279 const SharedObject *sharedObject =
280 (const SharedObject *) element->value.pointer;
281 U_ASSERT(sharedObject->cachePtr == this);
282 uhash_removeElement(fHashtable, element);
283 removeSoftRef(sharedObject); // Deletes the sharedObject when softRefCount goes to zero.
284 result = TRUE;
285 }
286 }
287 return result;
288 }
289
_computeCountOfItemsToEvict() const290 int32_t UnifiedCache::_computeCountOfItemsToEvict() const {
291 int32_t totalItems = uhash_count(fHashtable);
292 int32_t evictableItems = totalItems - fNumValuesInUse;
293
294 int32_t unusedLimitByPercentage = fNumValuesInUse * fMaxPercentageOfInUse / 100;
295 int32_t unusedLimit = std::max(unusedLimitByPercentage, fMaxUnused);
296 int32_t countOfItemsToEvict = std::max(0, evictableItems - unusedLimit);
297 return countOfItemsToEvict;
298 }
299
_runEvictionSlice() const300 void UnifiedCache::_runEvictionSlice() const {
301 int32_t maxItemsToEvict = _computeCountOfItemsToEvict();
302 if (maxItemsToEvict <= 0) {
303 return;
304 }
305 for (int32_t i = 0; i < MAX_EVICT_ITERATIONS; ++i) {
306 const UHashElement *element = _nextElement();
307 if (element == nullptr) {
308 break;
309 }
310 if (_isEvictable(element)) {
311 const SharedObject *sharedObject =
312 (const SharedObject *) element->value.pointer;
313 uhash_removeElement(fHashtable, element);
314 removeSoftRef(sharedObject); // Deletes sharedObject when SoftRefCount goes to zero.
315 ++fAutoEvictedCount;
316 if (--maxItemsToEvict == 0) {
317 break;
318 }
319 }
320 }
321 }
322
_putNew(const CacheKeyBase & key,const SharedObject * value,const UErrorCode creationStatus,UErrorCode & status) const323 void UnifiedCache::_putNew(
324 const CacheKeyBase &key,
325 const SharedObject *value,
326 const UErrorCode creationStatus,
327 UErrorCode &status) const {
328 if (U_FAILURE(status)) {
329 return;
330 }
331 CacheKeyBase *keyToAdopt = key.clone();
332 if (keyToAdopt == NULL) {
333 status = U_MEMORY_ALLOCATION_ERROR;
334 return;
335 }
336 keyToAdopt->fCreationStatus = creationStatus;
337 if (value->softRefCount == 0) {
338 _registerPrimary(keyToAdopt, value);
339 }
340 void *oldValue = uhash_put(fHashtable, keyToAdopt, (void *) value, &status);
341 U_ASSERT(oldValue == nullptr);
342 (void)oldValue;
343 if (U_SUCCESS(status)) {
344 value->softRefCount++;
345 }
346 }
347
_putIfAbsentAndGet(const CacheKeyBase & key,const SharedObject * & value,UErrorCode & status) const348 void UnifiedCache::_putIfAbsentAndGet(
349 const CacheKeyBase &key,
350 const SharedObject *&value,
351 UErrorCode &status) const {
352 #ifndef __wasi__
353 std::lock_guard<std::mutex> lock(*gCacheMutex);
354 #endif
355 const UHashElement *element = uhash_find(fHashtable, &key);
356 if (element != NULL && !_inProgress(element)) {
357 _fetch(element, value, status);
358 return;
359 }
360 if (element == NULL) {
361 UErrorCode putError = U_ZERO_ERROR;
362 // best-effort basis only.
363 _putNew(key, value, status, putError);
364 } else {
365 _put(element, value, status);
366 }
367 // Run an eviction slice. This will run even if we added a primary entry
368 // which doesn't increase the unused count, but that is still o.k
369 _runEvictionSlice();
370 }
371
372
_poll(const CacheKeyBase & key,const SharedObject * & value,UErrorCode & status) const373 UBool UnifiedCache::_poll(
374 const CacheKeyBase &key,
375 const SharedObject *&value,
376 UErrorCode &status) const {
377 U_ASSERT(value == NULL);
378 U_ASSERT(status == U_ZERO_ERROR);
379 #ifndef __wasi__
380 std::unique_lock<std::mutex> lock(*gCacheMutex);
381 #endif
382 const UHashElement *element = uhash_find(fHashtable, &key);
383
384 // If the hash table contains an inProgress placeholder entry for this key,
385 // this means that another thread is currently constructing the value object.
386 // Loop, waiting for that construction to complete.
387 while (element != NULL && _inProgress(element)) {
388 #ifndef __wasi__
389 gInProgressValueAddedCond->wait(lock);
390 #endif
391 element = uhash_find(fHashtable, &key);
392 }
393
394 // If the hash table contains an entry for the key,
395 // fetch out the contents and return them.
396 if (element != NULL) {
397 _fetch(element, value, status);
398 return TRUE;
399 }
400
401 // The hash table contained nothing for this key.
402 // Insert an inProgress place holder value.
403 // Our caller will create the final value and update the hash table.
404 _putNew(key, fNoValue, U_ZERO_ERROR, status);
405 return FALSE;
406 }
407
_get(const CacheKeyBase & key,const SharedObject * & value,const void * creationContext,UErrorCode & status) const408 void UnifiedCache::_get(
409 const CacheKeyBase &key,
410 const SharedObject *&value,
411 const void *creationContext,
412 UErrorCode &status) const {
413 U_ASSERT(value == NULL);
414 U_ASSERT(status == U_ZERO_ERROR);
415 if (_poll(key, value, status)) {
416 if (value == fNoValue) {
417 SharedObject::clearPtr(value);
418 }
419 return;
420 }
421 if (U_FAILURE(status)) {
422 return;
423 }
424 value = key.createObject(creationContext, status);
425 U_ASSERT(value == NULL || value->hasHardReferences());
426 U_ASSERT(value != NULL || status != U_ZERO_ERROR);
427 if (value == NULL) {
428 SharedObject::copyPtr(fNoValue, value);
429 }
430 _putIfAbsentAndGet(key, value, status);
431 if (value == fNoValue) {
432 SharedObject::clearPtr(value);
433 }
434 }
435
_registerPrimary(const CacheKeyBase * theKey,const SharedObject * value) const436 void UnifiedCache::_registerPrimary(
437 const CacheKeyBase *theKey, const SharedObject *value) const {
438 theKey->fIsPrimary = true;
439 value->cachePtr = this;
440 ++fNumValuesTotal;
441 ++fNumValuesInUse;
442 }
443
_put(const UHashElement * element,const SharedObject * value,const UErrorCode status) const444 void UnifiedCache::_put(
445 const UHashElement *element,
446 const SharedObject *value,
447 const UErrorCode status) const {
448 U_ASSERT(_inProgress(element));
449 const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
450 const SharedObject *oldValue = (const SharedObject *) element->value.pointer;
451 theKey->fCreationStatus = status;
452 if (value->softRefCount == 0) {
453 _registerPrimary(theKey, value);
454 }
455 value->softRefCount++;
456 UHashElement *ptr = const_cast<UHashElement *>(element);
457 ptr->value.pointer = (void *) value;
458 U_ASSERT(oldValue == fNoValue);
459 removeSoftRef(oldValue);
460
461 #ifndef __wasi__
462 // Tell waiting threads that we replace in-progress status with
463 // an error.
464 gInProgressValueAddedCond->notify_all();
465 #endif
466 }
467
_fetch(const UHashElement * element,const SharedObject * & value,UErrorCode & status) const468 void UnifiedCache::_fetch(
469 const UHashElement *element,
470 const SharedObject *&value,
471 UErrorCode &status) const {
472 const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
473 status = theKey->fCreationStatus;
474
475 // Since we have the cache lock, calling regular SharedObject add/removeRef
476 // could cause us to deadlock on ourselves since they may need to lock
477 // the cache mutex.
478 removeHardRef(value);
479 value = static_cast<const SharedObject *>(element->value.pointer);
480 addHardRef(value);
481 }
482
483
_inProgress(const UHashElement * element) const484 UBool UnifiedCache::_inProgress(const UHashElement* element) const {
485 UErrorCode status = U_ZERO_ERROR;
486 const SharedObject * value = NULL;
487 _fetch(element, value, status);
488 UBool result = _inProgress(value, status);
489 removeHardRef(value);
490 return result;
491 }
492
_inProgress(const SharedObject * theValue,UErrorCode creationStatus) const493 UBool UnifiedCache::_inProgress(
494 const SharedObject* theValue, UErrorCode creationStatus) const {
495 return (theValue == fNoValue && creationStatus == U_ZERO_ERROR);
496 }
497
_isEvictable(const UHashElement * element) const498 UBool UnifiedCache::_isEvictable(const UHashElement *element) const
499 {
500 const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
501 const SharedObject *theValue =
502 (const SharedObject *) element->value.pointer;
503
504 // Entries that are under construction are never evictable
505 if (_inProgress(theValue, theKey->fCreationStatus)) {
506 return FALSE;
507 }
508
509 // We can evict entries that are either not a primary or have just
510 // one reference (The one reference being from the cache itself).
511 return (!theKey->fIsPrimary || (theValue->softRefCount == 1 && theValue->noHardReferences()));
512 }
513
removeSoftRef(const SharedObject * value) const514 void UnifiedCache::removeSoftRef(const SharedObject *value) const {
515 U_ASSERT(value->cachePtr == this);
516 U_ASSERT(value->softRefCount > 0);
517 if (--value->softRefCount == 0) {
518 --fNumValuesTotal;
519 if (value->noHardReferences()) {
520 delete value;
521 } else {
522 // This path only happens from flush(all). Which only happens from the
523 // UnifiedCache destructor. Nulling out value.cacheptr changes the behavior
524 // of value.removeRef(), causing the deletion to be done there.
525 value->cachePtr = nullptr;
526 }
527 }
528 }
529
removeHardRef(const SharedObject * value) const530 int32_t UnifiedCache::removeHardRef(const SharedObject *value) const {
531 int refCount = 0;
532 if (value) {
533 refCount = umtx_atomic_dec(&value->hardRefCount);
534 U_ASSERT(refCount >= 0);
535 if (refCount == 0) {
536 --fNumValuesInUse;
537 }
538 }
539 return refCount;
540 }
541
addHardRef(const SharedObject * value) const542 int32_t UnifiedCache::addHardRef(const SharedObject *value) const {
543 int refCount = 0;
544 if (value) {
545 refCount = umtx_atomic_inc(&value->hardRefCount);
546 U_ASSERT(refCount >= 1);
547 if (refCount == 1) {
548 fNumValuesInUse++;
549 }
550 }
551 return refCount;
552 }
553
554 U_NAMESPACE_END
555