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
17 #include "mutex.h"
18 #include "uassert.h"
19 #include "uhash.h"
20 #include "ucln_cmn.h"
21 #include "umutex.h"
22
23 static icu::UnifiedCache *gCache = NULL;
24 static UMutex gCacheMutex = U_MUTEX_INITIALIZER;
25 static UConditionVar gInProgressValueAddedCond = U_CONDITION_INITIALIZER;
26 static icu::UInitOnce gCacheInitOnce = U_INITONCE_INITIALIZER;
27
28 static const int32_t MAX_EVICT_ITERATIONS = 10;
29 static const int32_t DEFAULT_MAX_UNUSED = 1000;
30 static const int32_t DEFAULT_PERCENTAGE_OF_IN_USE = 100;
31
32
33 U_CDECL_BEGIN
unifiedcache_cleanup()34 static UBool U_CALLCONV unifiedcache_cleanup() {
35 gCacheInitOnce.reset();
36 if (gCache) {
37 delete gCache;
38 gCache = NULL;
39 }
40 return TRUE;
41 }
42 U_CDECL_END
43
44
45 U_NAMESPACE_BEGIN
46
47 U_CAPI int32_t U_EXPORT2
ucache_hashKeys(const UHashTok key)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
ucache_compareKeys(const UHashTok key1,const UHashTok key2)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
ucache_deleteKey(void * obj)61 ucache_deleteKey(void *obj) {
62 CacheKeyBase *p = (CacheKeyBase *) obj;
63 delete p;
64 }
65
~CacheKeyBase()66 CacheKeyBase::~CacheKeyBase() {
67 }
68
cacheInit(UErrorCode & status)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 gCache = new UnifiedCache(status);
75 if (gCache == NULL) {
76 status = U_MEMORY_ALLOCATION_ERROR;
77 }
78 if (U_FAILURE(status)) {
79 delete gCache;
80 gCache = NULL;
81 return;
82 }
83 }
84
getInstance(UErrorCode & status)85 UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) {
86 umtx_initOnce(gCacheInitOnce, &cacheInit, status);
87 if (U_FAILURE(status)) {
88 return NULL;
89 }
90 U_ASSERT(gCache != NULL);
91 return gCache;
92 }
93
UnifiedCache(UErrorCode & status)94 UnifiedCache::UnifiedCache(UErrorCode &status) :
95 fHashtable(NULL),
96 fEvictPos(UHASH_FIRST),
97 fNumValuesTotal(0),
98 fNumValuesInUse(0),
99 fMaxUnused(DEFAULT_MAX_UNUSED),
100 fMaxPercentageOfInUse(DEFAULT_PERCENTAGE_OF_IN_USE),
101 fAutoEvictedCount(0),
102 fNoValue(nullptr) {
103 if (U_FAILURE(status)) {
104 return;
105 }
106 fNoValue = new SharedObject();
107 if (fNoValue == nullptr) {
108 status = U_MEMORY_ALLOCATION_ERROR;
109 return;
110 }
111 fNoValue->softRefCount = 1; // Add fake references to prevent fNoValue from being deleted
112 fNoValue->hardRefCount = 1; // when other references to it are removed.
113 fNoValue->cachePtr = this;
114
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
setEvictionPolicy(int32_t count,int32_t percentageOfInUseItems,UErrorCode & status)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
unusedCount() const140 int32_t UnifiedCache::unusedCount() const {
141 Mutex lock(&gCacheMutex);
142 return uhash_count(fHashtable) - fNumValuesInUse;
143 }
144
autoEvictedCount() const145 int64_t UnifiedCache::autoEvictedCount() const {
146 Mutex lock(&gCacheMutex);
147 return fAutoEvictedCount;
148 }
149
keyCount() const150 int32_t UnifiedCache::keyCount() const {
151 Mutex lock(&gCacheMutex);
152 return uhash_count(fHashtable);
153 }
154
flush() const155 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
handleUnreferencedObject() const164 void UnifiedCache::handleUnreferencedObject() const {
165 Mutex lock(&gCacheMutex);
166 --fNumValuesInUse;
167 _runEvictionSlice();
168 }
169
170 #ifdef UNIFIED_CACHE_DEBUG
171 #include <stdio.h>
172
dump()173 void UnifiedCache::dump() {
174 UErrorCode status = U_ZERO_ERROR;
175 const UnifiedCache *cache = getInstance(status);
176 if (U_FAILURE(status)) {
177 fprintf(stderr, "Unified Cache: Error fetching cache.\n");
178 return;
179 }
180 cache->dumpContents();
181 }
182
dumpContents() const183 void UnifiedCache::dumpContents() const {
184 Mutex lock(&gCacheMutex);
185 _dumpContents();
186 }
187
188 // Dumps content of cache.
189 // On entry, gCacheMutex must be held.
190 // On exit, cache contents dumped to stderr.
_dumpContents() const191 void UnifiedCache::_dumpContents() const {
192 int32_t pos = UHASH_FIRST;
193 const UHashElement *element = uhash_nextElement(fHashtable, &pos);
194 char buffer[256];
195 int32_t cnt = 0;
196 for (; element != NULL; element = uhash_nextElement(fHashtable, &pos)) {
197 const SharedObject *sharedObject =
198 (const SharedObject *) element->value.pointer;
199 const CacheKeyBase *key =
200 (const CacheKeyBase *) element->key.pointer;
201 if (sharedObject->hasHardReferences()) {
202 ++cnt;
203 fprintf(
204 stderr,
205 "Unified Cache: Key '%s', error %d, value %p, total refcount %d, soft refcount %d\n",
206 key->writeDescription(buffer, 256),
207 key->creationStatus,
208 sharedObject == fNoValue ? NULL :sharedObject,
209 sharedObject->getRefCount(),
210 sharedObject->getSoftRefCount());
211 }
212 }
213 fprintf(stderr, "Unified Cache: %d out of a total of %d still have hard references\n", cnt, uhash_count(fHashtable));
214 }
215 #endif
216
~UnifiedCache()217 UnifiedCache::~UnifiedCache() {
218 // Try our best to clean up first.
219 flush();
220 {
221 // Now all that should be left in the cache are entries that refer to
222 // each other and entries with hard references from outside the cache.
223 // Nothing we can do about these so proceed to wipe out the cache.
224 Mutex lock(&gCacheMutex);
225 _flush(TRUE);
226 }
227 uhash_close(fHashtable);
228 fHashtable = nullptr;
229 delete fNoValue;
230 fNoValue = nullptr;
231 }
232
233 const UHashElement *
_nextElement() const234 UnifiedCache::_nextElement() const {
235 const UHashElement *element = uhash_nextElement(fHashtable, &fEvictPos);
236 if (element == NULL) {
237 fEvictPos = UHASH_FIRST;
238 return uhash_nextElement(fHashtable, &fEvictPos);
239 }
240 return element;
241 }
242
_flush(UBool all) const243 UBool UnifiedCache::_flush(UBool all) const {
244 UBool result = FALSE;
245 int32_t origSize = uhash_count(fHashtable);
246 for (int32_t i = 0; i < origSize; ++i) {
247 const UHashElement *element = _nextElement();
248 if (element == nullptr) {
249 break;
250 }
251 if (all || _isEvictable(element)) {
252 const SharedObject *sharedObject =
253 (const SharedObject *) element->value.pointer;
254 U_ASSERT(sharedObject->cachePtr == this);
255 uhash_removeElement(fHashtable, element);
256 removeSoftRef(sharedObject); // Deletes the sharedObject when softRefCount goes to zero.
257 result = TRUE;
258 }
259 }
260 return result;
261 }
262
_computeCountOfItemsToEvict() const263 int32_t UnifiedCache::_computeCountOfItemsToEvict() const {
264 int32_t totalItems = uhash_count(fHashtable);
265 int32_t evictableItems = totalItems - fNumValuesInUse;
266
267 int32_t unusedLimitByPercentage = fNumValuesInUse * fMaxPercentageOfInUse / 100;
268 int32_t unusedLimit = std::max(unusedLimitByPercentage, fMaxUnused);
269 int32_t countOfItemsToEvict = std::max(0, evictableItems - unusedLimit);
270 return countOfItemsToEvict;
271 }
272
_runEvictionSlice() const273 void UnifiedCache::_runEvictionSlice() const {
274 int32_t maxItemsToEvict = _computeCountOfItemsToEvict();
275 if (maxItemsToEvict <= 0) {
276 return;
277 }
278 for (int32_t i = 0; i < MAX_EVICT_ITERATIONS; ++i) {
279 const UHashElement *element = _nextElement();
280 if (element == nullptr) {
281 break;
282 }
283 if (_isEvictable(element)) {
284 const SharedObject *sharedObject =
285 (const SharedObject *) element->value.pointer;
286 uhash_removeElement(fHashtable, element);
287 removeSoftRef(sharedObject); // Deletes sharedObject when SoftRefCount goes to zero.
288 ++fAutoEvictedCount;
289 if (--maxItemsToEvict == 0) {
290 break;
291 }
292 }
293 }
294 }
295
_putNew(const CacheKeyBase & key,const SharedObject * value,const UErrorCode creationStatus,UErrorCode & status) const296 void UnifiedCache::_putNew(
297 const CacheKeyBase &key,
298 const SharedObject *value,
299 const UErrorCode creationStatus,
300 UErrorCode &status) const {
301 if (U_FAILURE(status)) {
302 return;
303 }
304 CacheKeyBase *keyToAdopt = key.clone();
305 if (keyToAdopt == NULL) {
306 status = U_MEMORY_ALLOCATION_ERROR;
307 return;
308 }
309 keyToAdopt->fCreationStatus = creationStatus;
310 if (value->softRefCount == 0) {
311 _registerMaster(keyToAdopt, value);
312 }
313 void *oldValue = uhash_put(fHashtable, keyToAdopt, (void *) value, &status);
314 U_ASSERT(oldValue == nullptr);
315 (void)oldValue;
316 if (U_SUCCESS(status)) {
317 value->softRefCount++;
318 }
319 }
320
_putIfAbsentAndGet(const CacheKeyBase & key,const SharedObject * & value,UErrorCode & status) const321 void UnifiedCache::_putIfAbsentAndGet(
322 const CacheKeyBase &key,
323 const SharedObject *&value,
324 UErrorCode &status) const {
325 Mutex lock(&gCacheMutex);
326 const UHashElement *element = uhash_find(fHashtable, &key);
327 if (element != NULL && !_inProgress(element)) {
328 _fetch(element, value, status);
329 return;
330 }
331 if (element == NULL) {
332 UErrorCode putError = U_ZERO_ERROR;
333 // best-effort basis only.
334 _putNew(key, value, status, putError);
335 } else {
336 _put(element, value, status);
337 }
338 // Run an eviction slice. This will run even if we added a master entry
339 // which doesn't increase the unused count, but that is still o.k
340 _runEvictionSlice();
341 }
342
343
_poll(const CacheKeyBase & key,const SharedObject * & value,UErrorCode & status) const344 UBool UnifiedCache::_poll(
345 const CacheKeyBase &key,
346 const SharedObject *&value,
347 UErrorCode &status) const {
348 U_ASSERT(value == NULL);
349 U_ASSERT(status == U_ZERO_ERROR);
350 Mutex lock(&gCacheMutex);
351 const UHashElement *element = uhash_find(fHashtable, &key);
352
353 // If the hash table contains an inProgress placeholder entry for this key,
354 // this means that another thread is currently constructing the value object.
355 // Loop, waiting for that construction to complete.
356 while (element != NULL && _inProgress(element)) {
357 umtx_condWait(&gInProgressValueAddedCond, &gCacheMutex);
358 element = uhash_find(fHashtable, &key);
359 }
360
361 // If the hash table contains an entry for the key,
362 // fetch out the contents and return them.
363 if (element != NULL) {
364 _fetch(element, value, status);
365 return TRUE;
366 }
367
368 // The hash table contained nothing for this key.
369 // Insert an inProgress place holder value.
370 // Our caller will create the final value and update the hash table.
371 _putNew(key, fNoValue, U_ZERO_ERROR, status);
372 return FALSE;
373 }
374
_get(const CacheKeyBase & key,const SharedObject * & value,const void * creationContext,UErrorCode & status) const375 void UnifiedCache::_get(
376 const CacheKeyBase &key,
377 const SharedObject *&value,
378 const void *creationContext,
379 UErrorCode &status) const {
380 U_ASSERT(value == NULL);
381 U_ASSERT(status == U_ZERO_ERROR);
382 if (_poll(key, value, status)) {
383 if (value == fNoValue) {
384 SharedObject::clearPtr(value);
385 }
386 return;
387 }
388 if (U_FAILURE(status)) {
389 return;
390 }
391 value = key.createObject(creationContext, status);
392 U_ASSERT(value == NULL || value->hasHardReferences());
393 U_ASSERT(value != NULL || status != U_ZERO_ERROR);
394 if (value == NULL) {
395 SharedObject::copyPtr(fNoValue, value);
396 }
397 _putIfAbsentAndGet(key, value, status);
398 if (value == fNoValue) {
399 SharedObject::clearPtr(value);
400 }
401 }
402
_registerMaster(const CacheKeyBase * theKey,const SharedObject * value) const403 void UnifiedCache::_registerMaster(
404 const CacheKeyBase *theKey, const SharedObject *value) const {
405 theKey->fIsMaster = true;
406 value->cachePtr = this;
407 ++fNumValuesTotal;
408 ++fNumValuesInUse;
409 }
410
_put(const UHashElement * element,const SharedObject * value,const UErrorCode status) const411 void UnifiedCache::_put(
412 const UHashElement *element,
413 const SharedObject *value,
414 const UErrorCode status) const {
415 U_ASSERT(_inProgress(element));
416 const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
417 const SharedObject *oldValue = (const SharedObject *) element->value.pointer;
418 theKey->fCreationStatus = status;
419 if (value->softRefCount == 0) {
420 _registerMaster(theKey, value);
421 }
422 value->softRefCount++;
423 UHashElement *ptr = const_cast<UHashElement *>(element);
424 ptr->value.pointer = (void *) value;
425 U_ASSERT(oldValue == fNoValue);
426 removeSoftRef(oldValue);
427
428 // Tell waiting threads that we replace in-progress status with
429 // an error.
430 umtx_condBroadcast(&gInProgressValueAddedCond);
431 }
432
_fetch(const UHashElement * element,const SharedObject * & value,UErrorCode & status) const433 void UnifiedCache::_fetch(
434 const UHashElement *element,
435 const SharedObject *&value,
436 UErrorCode &status) const {
437 const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
438 status = theKey->fCreationStatus;
439
440 // Since we have the cache lock, calling regular SharedObject add/removeRef
441 // could cause us to deadlock on ourselves since they may need to lock
442 // the cache mutex.
443 removeHardRef(value);
444 value = static_cast<const SharedObject *>(element->value.pointer);
445 addHardRef(value);
446 }
447
448
_inProgress(const UHashElement * element) const449 UBool UnifiedCache::_inProgress(const UHashElement* element) const {
450 UErrorCode status = U_ZERO_ERROR;
451 const SharedObject * value = NULL;
452 _fetch(element, value, status);
453 UBool result = _inProgress(value, status);
454 removeHardRef(value);
455 return result;
456 }
457
_inProgress(const SharedObject * theValue,UErrorCode creationStatus) const458 UBool UnifiedCache::_inProgress(
459 const SharedObject* theValue, UErrorCode creationStatus) const {
460 return (theValue == fNoValue && creationStatus == U_ZERO_ERROR);
461 }
462
_isEvictable(const UHashElement * element) const463 UBool UnifiedCache::_isEvictable(const UHashElement *element) const
464 {
465 const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
466 const SharedObject *theValue =
467 (const SharedObject *) element->value.pointer;
468
469 // Entries that are under construction are never evictable
470 if (_inProgress(theValue, theKey->fCreationStatus)) {
471 return FALSE;
472 }
473
474 // We can evict entries that are either not a master or have just
475 // one reference (The one reference being from the cache itself).
476 return (!theKey->fIsMaster || (theValue->softRefCount == 1 && theValue->noHardReferences()));
477 }
478
removeSoftRef(const SharedObject * value) const479 void UnifiedCache::removeSoftRef(const SharedObject *value) const {
480 U_ASSERT(value->cachePtr == this);
481 U_ASSERT(value->softRefCount > 0);
482 if (--value->softRefCount == 0) {
483 --fNumValuesTotal;
484 if (value->noHardReferences()) {
485 delete value;
486 } else {
487 // This path only happens from flush(all). Which only happens from the
488 // UnifiedCache destructor. Nulling out value.cacheptr changes the behavior
489 // of value.removeRef(), causing the deletion to be done there.
490 value->cachePtr = nullptr;
491 }
492 }
493 }
494
removeHardRef(const SharedObject * value) const495 int32_t UnifiedCache::removeHardRef(const SharedObject *value) const {
496 int refCount = 0;
497 if (value) {
498 refCount = umtx_atomic_dec(&value->hardRefCount);
499 U_ASSERT(refCount >= 0);
500 if (refCount == 0) {
501 --fNumValuesInUse;
502 }
503 }
504 return refCount;
505 }
506
addHardRef(const SharedObject * value) const507 int32_t UnifiedCache::addHardRef(const SharedObject *value) const {
508 int refCount = 0;
509 if (value) {
510 refCount = umtx_atomic_inc(&value->hardRefCount);
511 U_ASSERT(refCount >= 1);
512 if (refCount == 1) {
513 fNumValuesInUse++;
514 }
515 }
516 return refCount;
517 }
518
519 U_NAMESPACE_END
520