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