Line data Source code
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 "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 0 : static UBool U_CALLCONV unifiedcache_cleanup() {
33 0 : gCacheInitOnce.reset();
34 0 : if (gCache) {
35 0 : delete gCache;
36 0 : gCache = NULL;
37 : }
38 0 : if (gNoValue) {
39 0 : delete gNoValue;
40 0 : gNoValue = NULL;
41 : }
42 0 : return TRUE;
43 : }
44 : U_CDECL_END
45 :
46 :
47 : U_NAMESPACE_BEGIN
48 :
49 : U_CAPI int32_t U_EXPORT2
50 0 : ucache_hashKeys(const UHashTok key) {
51 0 : const CacheKeyBase *ckey = (const CacheKeyBase *) key.pointer;
52 0 : return ckey->hashCode();
53 : }
54 :
55 : U_CAPI UBool U_EXPORT2
56 0 : ucache_compareKeys(const UHashTok key1, const UHashTok key2) {
57 0 : const CacheKeyBase *p1 = (const CacheKeyBase *) key1.pointer;
58 0 : const CacheKeyBase *p2 = (const CacheKeyBase *) key2.pointer;
59 0 : return *p1 == *p2;
60 : }
61 :
62 : U_CAPI void U_EXPORT2
63 0 : ucache_deleteKey(void *obj) {
64 0 : CacheKeyBase *p = (CacheKeyBase *) obj;
65 0 : delete p;
66 0 : }
67 :
68 0 : CacheKeyBase::~CacheKeyBase() {
69 0 : }
70 :
71 0 : static void U_CALLCONV cacheInit(UErrorCode &status) {
72 0 : U_ASSERT(gCache == NULL);
73 : ucln_common_registerCleanup(
74 0 : UCLN_COMMON_UNIFIED_CACHE, unifiedcache_cleanup);
75 :
76 : // gNoValue must be created first to avoid assertion error in
77 : // cache constructor.
78 0 : gNoValue = new SharedObject();
79 0 : gCache = new UnifiedCache(status);
80 0 : if (gCache == NULL) {
81 0 : status = U_MEMORY_ALLOCATION_ERROR;
82 : }
83 0 : if (U_FAILURE(status)) {
84 0 : delete gCache;
85 0 : delete gNoValue;
86 0 : gCache = NULL;
87 0 : gNoValue = NULL;
88 0 : 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 0 : gNoValue->addSoftRef();
93 : }
94 :
95 0 : UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) {
96 0 : umtx_initOnce(gCacheInitOnce, &cacheInit, status);
97 0 : if (U_FAILURE(status)) {
98 0 : return NULL;
99 : }
100 0 : U_ASSERT(gCache != NULL);
101 0 : return gCache;
102 : }
103 :
104 0 : 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 0 : fAutoEvictedCount(0) {
111 0 : if (U_FAILURE(status)) {
112 0 : return;
113 : }
114 0 : U_ASSERT(gNoValue != NULL);
115 0 : fHashtable = uhash_open(
116 : &ucache_hashKeys,
117 : &ucache_compareKeys,
118 : NULL,
119 : &status);
120 0 : if (U_FAILURE(status)) {
121 0 : return;
122 : }
123 0 : uhash_setKeyDeleter(fHashtable, &ucache_deleteKey);
124 : }
125 :
126 0 : void UnifiedCache::setEvictionPolicy(
127 : int32_t count, int32_t percentageOfInUseItems, UErrorCode &status) {
128 0 : if (U_FAILURE(status)) {
129 0 : return;
130 : }
131 0 : if (count < 0 || percentageOfInUseItems < 0) {
132 0 : status = U_ILLEGAL_ARGUMENT_ERROR;
133 0 : return;
134 : }
135 0 : Mutex lock(&gCacheMutex);
136 0 : fMaxUnused = count;
137 0 : fMaxPercentageOfInUse = percentageOfInUseItems;
138 : }
139 :
140 0 : int32_t UnifiedCache::unusedCount() const {
141 0 : Mutex lock(&gCacheMutex);
142 0 : return uhash_count(fHashtable) - fItemsInUseCount;
143 : }
144 :
145 0 : int64_t UnifiedCache::autoEvictedCount() const {
146 0 : Mutex lock(&gCacheMutex);
147 0 : return fAutoEvictedCount;
148 : }
149 :
150 0 : int32_t UnifiedCache::keyCount() const {
151 0 : Mutex lock(&gCacheMutex);
152 0 : return uhash_count(fHashtable);
153 : }
154 :
155 0 : void UnifiedCache::flush() const {
156 0 : 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 0 : while (_flush(FALSE));
162 0 : }
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 0 : UnifiedCache::~UnifiedCache() {
212 : // Try our best to clean up first.
213 0 : 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 0 : Mutex lock(&gCacheMutex);
219 0 : _flush(TRUE);
220 : }
221 0 : uhash_close(fHashtable);
222 0 : }
223 :
224 : // Returns the next element in the cache round robin style.
225 : // On entry, gCacheMutex must be held.
226 : const UHashElement *
227 0 : UnifiedCache::_nextElement() const {
228 0 : const UHashElement *element = uhash_nextElement(fHashtable, &fEvictPos);
229 0 : if (element == NULL) {
230 0 : fEvictPos = UHASH_FIRST;
231 0 : return uhash_nextElement(fHashtable, &fEvictPos);
232 : }
233 0 : 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 0 : UBool UnifiedCache::_flush(UBool all) const {
243 0 : UBool result = FALSE;
244 0 : int32_t origSize = uhash_count(fHashtable);
245 0 : for (int32_t i = 0; i < origSize; ++i) {
246 0 : const UHashElement *element = _nextElement();
247 0 : if (all || _isEvictable(element)) {
248 : const SharedObject *sharedObject =
249 0 : (const SharedObject *) element->value.pointer;
250 0 : uhash_removeElement(fHashtable, element);
251 0 : sharedObject->removeSoftRef();
252 0 : result = TRUE;
253 : }
254 : }
255 0 : 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 0 : int32_t UnifiedCache::_computeCountOfItemsToEvict() const {
263 : int32_t maxPercentageOfInUseCount =
264 0 : fItemsInUseCount * fMaxPercentageOfInUse / 100;
265 0 : int32_t maxUnusedCount = fMaxUnused;
266 0 : if (maxUnusedCount < maxPercentageOfInUseCount) {
267 0 : maxUnusedCount = maxPercentageOfInUseCount;
268 : }
269 0 : 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 0 : void UnifiedCache::_runEvictionSlice() const {
277 0 : int32_t maxItemsToEvict = _computeCountOfItemsToEvict();
278 0 : if (maxItemsToEvict <= 0) {
279 0 : return;
280 : }
281 0 : for (int32_t i = 0; i < MAX_EVICT_ITERATIONS; ++i) {
282 0 : const UHashElement *element = _nextElement();
283 0 : if (_isEvictable(element)) {
284 : const SharedObject *sharedObject =
285 0 : (const SharedObject *) element->value.pointer;
286 0 : uhash_removeElement(fHashtable, element);
287 0 : sharedObject->removeSoftRef();
288 0 : ++fAutoEvictedCount;
289 0 : if (--maxItemsToEvict == 0) {
290 0 : 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 0 : void UnifiedCache::_putNew(
302 : const CacheKeyBase &key,
303 : const SharedObject *value,
304 : const UErrorCode creationStatus,
305 : UErrorCode &status) const {
306 0 : if (U_FAILURE(status)) {
307 0 : return;
308 : }
309 0 : CacheKeyBase *keyToAdopt = key.clone();
310 0 : if (keyToAdopt == NULL) {
311 0 : status = U_MEMORY_ALLOCATION_ERROR;
312 0 : return;
313 : }
314 0 : keyToAdopt->fCreationStatus = creationStatus;
315 0 : if (value->noSoftReferences()) {
316 0 : _registerMaster(keyToAdopt, value);
317 : }
318 0 : uhash_put(fHashtable, keyToAdopt, (void *) value, &status);
319 0 : if (U_SUCCESS(status)) {
320 0 : 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 0 : void UnifiedCache::_putIfAbsentAndGet(
334 : const CacheKeyBase &key,
335 : const SharedObject *&value,
336 : UErrorCode &status) const {
337 0 : Mutex lock(&gCacheMutex);
338 0 : const UHashElement *element = uhash_find(fHashtable, &key);
339 0 : if (element != NULL && !_inProgress(element)) {
340 0 : _fetch(element, value, status);
341 0 : return;
342 : }
343 0 : if (element == NULL) {
344 0 : UErrorCode putError = U_ZERO_ERROR;
345 : // best-effort basis only.
346 0 : _putNew(key, value, status, putError);
347 : } else {
348 0 : _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 0 : _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 0 : UBool UnifiedCache::_poll(
365 : const CacheKeyBase &key,
366 : const SharedObject *&value,
367 : UErrorCode &status) const {
368 0 : U_ASSERT(value == NULL);
369 0 : U_ASSERT(status == U_ZERO_ERROR);
370 0 : Mutex lock(&gCacheMutex);
371 0 : const UHashElement *element = uhash_find(fHashtable, &key);
372 0 : while (element != NULL && _inProgress(element)) {
373 0 : umtx_condWait(&gInProgressValueAddedCond, &gCacheMutex);
374 0 : element = uhash_find(fHashtable, &key);
375 : }
376 0 : if (element != NULL) {
377 0 : _fetch(element, value, status);
378 0 : return TRUE;
379 : }
380 0 : _putNew(key, gNoValue, U_ZERO_ERROR, status);
381 0 : 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 0 : void UnifiedCache::_get(
394 : const CacheKeyBase &key,
395 : const SharedObject *&value,
396 : const void *creationContext,
397 : UErrorCode &status) const {
398 0 : U_ASSERT(value == NULL);
399 0 : U_ASSERT(status == U_ZERO_ERROR);
400 0 : if (_poll(key, value, status)) {
401 0 : if (value == gNoValue) {
402 0 : SharedObject::clearPtr(value);
403 : }
404 0 : return;
405 : }
406 0 : if (U_FAILURE(status)) {
407 0 : return;
408 : }
409 0 : value = key.createObject(creationContext, status);
410 0 : U_ASSERT(value == NULL || value->hasHardReferences());
411 0 : U_ASSERT(value != NULL || status != U_ZERO_ERROR);
412 0 : if (value == NULL) {
413 0 : SharedObject::copyPtr(gNoValue, value);
414 : }
415 0 : _putIfAbsentAndGet(key, value, status);
416 0 : if (value == gNoValue) {
417 0 : SharedObject::clearPtr(value);
418 : }
419 : }
420 :
421 0 : void UnifiedCache::decrementItemsInUseWithLockingAndEviction() const {
422 0 : Mutex mutex(&gCacheMutex);
423 0 : decrementItemsInUse();
424 0 : _runEvictionSlice();
425 0 : }
426 :
427 0 : void UnifiedCache::incrementItemsInUse() const {
428 0 : ++fItemsInUseCount;
429 0 : }
430 :
431 0 : void UnifiedCache::decrementItemsInUse() const {
432 0 : --fItemsInUseCount;
433 0 : }
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 0 : void UnifiedCache::_registerMaster(
441 : const CacheKeyBase *theKey, const SharedObject *value) const {
442 0 : theKey->fIsMaster = TRUE;
443 0 : ++fItemsInUseCount;
444 0 : value->registerWithCache(this);
445 0 : }
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 0 : void UnifiedCache::_put(
454 : const UHashElement *element,
455 : const SharedObject *value,
456 : const UErrorCode status) const {
457 0 : U_ASSERT(_inProgress(element));
458 0 : const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
459 0 : const SharedObject *oldValue = (const SharedObject *) element->value.pointer;
460 0 : theKey->fCreationStatus = status;
461 0 : if (value->noSoftReferences()) {
462 0 : _registerMaster(theKey, value);
463 : }
464 0 : value->addSoftRef();
465 0 : UHashElement *ptr = const_cast<UHashElement *>(element);
466 0 : ptr->value.pointer = (void *) value;
467 0 : oldValue->removeSoftRef();
468 :
469 : // Tell waiting threads that we replace in-progress status with
470 : // an error.
471 0 : umtx_condBroadcast(&gInProgressValueAddedCond);
472 0 : }
473 :
474 : void
475 0 : UnifiedCache::copyPtr(const SharedObject *src, const SharedObject *&dest) {
476 0 : if(src != dest) {
477 0 : if(dest != NULL) {
478 0 : dest->removeRefWhileHoldingCacheLock();
479 : }
480 0 : dest = src;
481 0 : if(src != NULL) {
482 0 : src->addRefWhileHoldingCacheLock();
483 : }
484 : }
485 0 : }
486 :
487 : void
488 0 : UnifiedCache::clearPtr(const SharedObject *&ptr) {
489 0 : if (ptr != NULL) {
490 0 : ptr->removeRefWhileHoldingCacheLock();
491 0 : ptr = NULL;
492 : }
493 0 : }
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 0 : void UnifiedCache::_fetch(
504 : const UHashElement *element,
505 : const SharedObject *&value,
506 : UErrorCode &status) {
507 0 : const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
508 0 : 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 0 : UnifiedCache::copyPtr((const SharedObject *) element->value.pointer, value);
514 0 : }
515 :
516 : // Determine if given hash entry is in progress.
517 : // On entry, gCacheMutex must be held.
518 0 : UBool UnifiedCache::_inProgress(const UHashElement *element) {
519 0 : const SharedObject *value = NULL;
520 0 : UErrorCode status = U_ZERO_ERROR;
521 0 : _fetch(element, value, status);
522 0 : 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 0 : UnifiedCache::clearPtr(value);
528 0 : return result;
529 : }
530 :
531 : // Determine if given hash entry is in progress.
532 : // On entry, gCacheMutex must be held.
533 0 : UBool UnifiedCache::_inProgress(
534 : const SharedObject *theValue, UErrorCode creationStatus) {
535 0 : 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 0 : UBool UnifiedCache::_isEvictable(const UHashElement *element) {
541 0 : const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
542 : const SharedObject *theValue =
543 0 : (const SharedObject *) element->value.pointer;
544 :
545 : // Entries that are under construction are never evictable
546 0 : if (_inProgress(theValue, theKey->fCreationStatus)) {
547 0 : 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 0 : return (!theKey->fIsMaster || (theValue->getSoftRefCount() == 1 && theValue->noHardReferences()));
553 : }
554 :
555 : U_NAMESPACE_END
|
