// Copyright (C) 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
******************************************************************************
* Copyright (C) 2015, International Business Machines Corporation and
* others. All Rights Reserved.
******************************************************************************
*
* File UNIFIEDCACHE.CPP
******************************************************************************
*/
#include "uhash.h"
#include "unifiedcache.h"
#include "umutex.h"
#include "mutex.h"
#include "uassert.h"
#include "ucln_cmn.h"
static icu::UnifiedCache *gCache = NULL;
static icu::SharedObject *gNoValue = NULL;
static UMutex gCacheMutex = U_MUTEX_INITIALIZER;
static UConditionVar gInProgressValueAddedCond = U_CONDITION_INITIALIZER;
static icu::UInitOnce gCacheInitOnce = U_INITONCE_INITIALIZER;
static const int32_t MAX_EVICT_ITERATIONS = 10;
static int32_t DEFAULT_MAX_UNUSED = 1000;
static int32_t DEFAULT_PERCENTAGE_OF_IN_USE = 100;
U_CDECL_BEGIN
static UBool U_CALLCONV unifiedcache_cleanup() {
gCacheInitOnce.reset();
if (gCache) {
delete gCache;
gCache = NULL;
}
if (gNoValue) {
delete gNoValue;
gNoValue = NULL;
}
return TRUE;
}
U_CDECL_END
U_NAMESPACE_BEGIN
U_CAPI int32_t U_EXPORT2
ucache_hashKeys(const UHashTok key) {
const CacheKeyBase *ckey = (const CacheKeyBase *) key.pointer;
return ckey->hashCode();
}
U_CAPI UBool U_EXPORT2
ucache_compareKeys(const UHashTok key1, const UHashTok key2) {
const CacheKeyBase *p1 = (const CacheKeyBase *) key1.pointer;
const CacheKeyBase *p2 = (const CacheKeyBase *) key2.pointer;
return *p1 == *p2;
}
U_CAPI void U_EXPORT2
ucache_deleteKey(void *obj) {
CacheKeyBase *p = (CacheKeyBase *) obj;
delete p;
}
CacheKeyBase::~CacheKeyBase() {
}
static void U_CALLCONV cacheInit(UErrorCode &status) {
U_ASSERT(gCache == NULL);
ucln_common_registerCleanup(
UCLN_COMMON_UNIFIED_CACHE, unifiedcache_cleanup);
// gNoValue must be created first to avoid assertion error in
// cache constructor.
gNoValue = new SharedObject();
gCache = new UnifiedCache(status);
if (gCache == NULL) {
status = U_MEMORY_ALLOCATION_ERROR;
}
if (U_FAILURE(status)) {
delete gCache;
delete gNoValue;
gCache = NULL;
gNoValue = NULL;
return;
}
// We add a softref because we want hash elements with gNoValue to be
// elligible for purging but we don't ever want gNoValue to be deleted.
gNoValue->addSoftRef();
}
UnifiedCache *UnifiedCache::getInstance(UErrorCode &status) {
umtx_initOnce(gCacheInitOnce, &cacheInit, status);
if (U_FAILURE(status)) {
return NULL;
}
U_ASSERT(gCache != NULL);
return gCache;
}
UnifiedCache::UnifiedCache(UErrorCode &status) :
fHashtable(NULL),
fEvictPos(UHASH_FIRST),
fItemsInUseCount(0),
fMaxUnused(DEFAULT_MAX_UNUSED),
fMaxPercentageOfInUse(DEFAULT_PERCENTAGE_OF_IN_USE),
fAutoEvictedCount(0) {
if (U_FAILURE(status)) {
return;
}
U_ASSERT(gNoValue != NULL);
fHashtable = uhash_open(
&ucache_hashKeys,
&ucache_compareKeys,
NULL,
&status);
if (U_FAILURE(status)) {
return;
}
uhash_setKeyDeleter(fHashtable, &ucache_deleteKey);
}
void UnifiedCache::setEvictionPolicy(
int32_t count, int32_t percentageOfInUseItems, UErrorCode &status) {
if (U_FAILURE(status)) {
return;
}
if (count < 0 || percentageOfInUseItems < 0) {
status = U_ILLEGAL_ARGUMENT_ERROR;
return;
}
Mutex lock(&gCacheMutex);
fMaxUnused = count;
fMaxPercentageOfInUse = percentageOfInUseItems;
}
int32_t UnifiedCache::unusedCount() const {
Mutex lock(&gCacheMutex);
return uhash_count(fHashtable) - fItemsInUseCount;
}
int64_t UnifiedCache::autoEvictedCount() const {
Mutex lock(&gCacheMutex);
return fAutoEvictedCount;
}
int32_t UnifiedCache::keyCount() const {
Mutex lock(&gCacheMutex);
return uhash_count(fHashtable);
}
void UnifiedCache::flush() const {
Mutex lock(&gCacheMutex);
// Use a loop in case cache items that are flushed held hard references to
// other cache items making those additional cache items eligible for
// flushing.
while (_flush(FALSE));
}
#ifdef UNIFIED_CACHE_DEBUG
#include <stdio.h>
void UnifiedCache::dump() {
UErrorCode status = U_ZERO_ERROR;
const UnifiedCache *cache = getInstance(status);
if (U_FAILURE(status)) {
fprintf(stderr, "Unified Cache: Error fetching cache.\n");
return;
}
cache->dumpContents();
}
void UnifiedCache::dumpContents() const {
Mutex lock(&gCacheMutex);
_dumpContents();
}
// Dumps content of cache.
// On entry, gCacheMutex must be held.
// On exit, cache contents dumped to stderr.
void UnifiedCache::_dumpContents() const {
int32_t pos = UHASH_FIRST;
const UHashElement *element = uhash_nextElement(fHashtable, &pos);
char buffer[256];
int32_t cnt = 0;
for (; element != NULL; element = uhash_nextElement(fHashtable, &pos)) {
const SharedObject *sharedObject =
(const SharedObject *) element->value.pointer;
const CacheKeyBase *key =
(const CacheKeyBase *) element->key.pointer;
if (sharedObject->hasHardReferences()) {
++cnt;
fprintf(
stderr,
"Unified Cache: Key '%s', error %d, value %p, total refcount %d, soft refcount %d\n",
key->writeDescription(buffer, 256),
key->creationStatus,
sharedObject == gNoValue ? NULL :sharedObject,
sharedObject->getRefCount(),
sharedObject->getSoftRefCount());
}
}
fprintf(stderr, "Unified Cache: %d out of a total of %d still have hard references\n", cnt, uhash_count(fHashtable));
}
#endif
UnifiedCache::~UnifiedCache() {
// Try our best to clean up first.
flush();
{
// Now all that should be left in the cache are entries that refer to
// each other and entries with hard references from outside the cache.
// Nothing we can do about these so proceed to wipe out the cache.
Mutex lock(&gCacheMutex);
_flush(TRUE);
}
uhash_close(fHashtable);
}
// Returns the next element in the cache round robin style.
// On entry, gCacheMutex must be held.
const UHashElement *
UnifiedCache::_nextElement() const {
const UHashElement *element = uhash_nextElement(fHashtable, &fEvictPos);
if (element == NULL) {
fEvictPos = UHASH_FIRST;
return uhash_nextElement(fHashtable, &fEvictPos);
}
return element;
}
// Flushes the contents of the cache. If cache values hold references to other
// cache values then _flush should be called in a loop until it returns FALSE.
// On entry, gCacheMutex must be held.
// On exit, those values with are evictable are flushed. If all is true
// then every value is flushed even if it is not evictable.
// Returns TRUE if any value in cache was flushed or FALSE otherwise.
UBool UnifiedCache::_flush(UBool all) const {
UBool result = FALSE;
int32_t origSize = uhash_count(fHashtable);
for (int32_t i = 0; i < origSize; ++i) {
const UHashElement *element = _nextElement();
if (all || _isEvictable(element)) {
const SharedObject *sharedObject =
(const SharedObject *) element->value.pointer;
uhash_removeElement(fHashtable, element);
sharedObject->removeSoftRef();
result = TRUE;
}
}
return result;
}
// Computes how many items should be evicted.
// On entry, gCacheMutex must be held.
// Returns number of items that should be evicted or a value <= 0 if no
// items need to be evicted.
int32_t UnifiedCache::_computeCountOfItemsToEvict() const {
int32_t maxPercentageOfInUseCount =
fItemsInUseCount * fMaxPercentageOfInUse / 100;
int32_t maxUnusedCount = fMaxUnused;
if (maxUnusedCount < maxPercentageOfInUseCount) {
maxUnusedCount = maxPercentageOfInUseCount;
}
return uhash_count(fHashtable) - fItemsInUseCount - maxUnusedCount;
}
// Run an eviction slice.
// On entry, gCacheMutex must be held.
// _runEvictionSlice runs a slice of the evict pipeline by examining the next
// 10 entries in the cache round robin style evicting them if they are eligible.
void UnifiedCache::_runEvictionSlice() const {
int32_t maxItemsToEvict = _computeCountOfItemsToEvict();
if (maxItemsToEvict <= 0) {
return;
}
for (int32_t i = 0; i < MAX_EVICT_ITERATIONS; ++i) {
const UHashElement *element = _nextElement();
if (_isEvictable(element)) {
const SharedObject *sharedObject =
(const SharedObject *) element->value.pointer;
uhash_removeElement(fHashtable, element);
sharedObject->removeSoftRef();
++fAutoEvictedCount;
if (--maxItemsToEvict == 0) {
break;
}
}
}
}
// Places a new value and creationStatus in the cache for the given key.
// On entry, gCacheMutex must be held. key must not exist in the cache.
// On exit, value and creation status placed under key. Soft reference added
// to value on successful add. On error sets status.
void UnifiedCache::_putNew(
const CacheKeyBase &key,
const SharedObject *value,
const UErrorCode creationStatus,
UErrorCode &status) const {
if (U_FAILURE(status)) {
return;
}
CacheKeyBase *keyToAdopt = key.clone();
if (keyToAdopt == NULL) {
status = U_MEMORY_ALLOCATION_ERROR;
return;
}
keyToAdopt->fCreationStatus = creationStatus;
if (value->noSoftReferences()) {
_registerMaster(keyToAdopt, value);
}
uhash_put(fHashtable, keyToAdopt, (void *) value, &status);
if (U_SUCCESS(status)) {
value->addSoftRef();
}
}
// Places value and status at key if there is no value at key or if cache
// entry for key is in progress. Otherwise, it leaves the current value and
// status there.
// On entry. gCacheMutex must not be held. value must be
// included in the reference count of the object to which it points.
// On exit, value and status are changed to what was already in the cache if
// something was there and not in progress. Otherwise, value and status are left
// unchanged in which case they are placed in the cache on a best-effort basis.
// Caller must call removeRef() on value.
void UnifiedCache::_putIfAbsentAndGet(
const CacheKeyBase &key,
const SharedObject *&value,
UErrorCode &status) const {
Mutex lock(&gCacheMutex);
const UHashElement *element = uhash_find(fHashtable, &key);
if (element != NULL && !_inProgress(element)) {
_fetch(element, value, status);
return;
}
if (element == NULL) {
UErrorCode putError = U_ZERO_ERROR;
// best-effort basis only.
_putNew(key, value, status, putError);
} else {
_put(element, value, status);
}
// Run an eviction slice. This will run even if we added a master entry
// which doesn't increase the unused count, but that is still o.k
_runEvictionSlice();
}
// Attempts to fetch value and status for key from cache.
// On entry, gCacheMutex must not be held value must be NULL and status must
// be U_ZERO_ERROR.
// On exit, either returns FALSE (In this
// case caller should try to create the object) or returns TRUE with value
// pointing to the fetched value and status set to fetched status. When
// FALSE is returned status may be set to failure if an in progress hash
// entry could not be made but value will remain unchanged. When TRUE is
// returned, caler must call removeRef() on value.
UBool UnifiedCache::_poll(
const CacheKeyBase &key,
const SharedObject *&value,
UErrorCode &status) const {
U_ASSERT(value == NULL);
U_ASSERT(status == U_ZERO_ERROR);
Mutex lock(&gCacheMutex);
const UHashElement *element = uhash_find(fHashtable, &key);
while (element != NULL && _inProgress(element)) {
umtx_condWait(&gInProgressValueAddedCond, &gCacheMutex);
element = uhash_find(fHashtable, &key);
}
if (element != NULL) {
_fetch(element, value, status);
return TRUE;
}
_putNew(key, gNoValue, U_ZERO_ERROR, status);
return FALSE;
}
// Gets value out of cache.
// On entry. gCacheMutex must not be held. value must be NULL. status
// must be U_ZERO_ERROR.
// On exit. value and status set to what is in cache at key or on cache
// miss the key's createObject() is called and value and status are set to
// the result of that. In this latter case, best effort is made to add the
// value and status to the cache. If createObject() fails to create a value,
// gNoValue is stored in cache, and value is set to NULL. Caller must call
// removeRef on value if non NULL.
void UnifiedCache::_get(
const CacheKeyBase &key,
const SharedObject *&value,
const void *creationContext,
UErrorCode &status) const {
U_ASSERT(value == NULL);
U_ASSERT(status == U_ZERO_ERROR);
if (_poll(key, value, status)) {
if (value == gNoValue) {
SharedObject::clearPtr(value);
}
return;
}
if (U_FAILURE(status)) {
return;
}
value = key.createObject(creationContext, status);
U_ASSERT(value == NULL || value->hasHardReferences());
U_ASSERT(value != NULL || status != U_ZERO_ERROR);
if (value == NULL) {
SharedObject::copyPtr(gNoValue, value);
}
_putIfAbsentAndGet(key, value, status);
if (value == gNoValue) {
SharedObject::clearPtr(value);
}
}
void UnifiedCache::decrementItemsInUseWithLockingAndEviction() const {
Mutex mutex(&gCacheMutex);
decrementItemsInUse();
_runEvictionSlice();
}
void UnifiedCache::incrementItemsInUse() const {
++fItemsInUseCount;
}
void UnifiedCache::decrementItemsInUse() const {
--fItemsInUseCount;
}
// Register a master cache entry.
// On entry, gCacheMutex must be held.
// On exit, items in use count incremented, entry is marked as a master
// entry, and value registered with cache so that subsequent calls to
// addRef() and removeRef() on it correctly updates items in use count
void UnifiedCache::_registerMaster(
const CacheKeyBase *theKey, const SharedObject *value) const {
theKey->fIsMaster = TRUE;
++fItemsInUseCount;
value->registerWithCache(this);
}
// Store a value and error in given hash entry.
// On entry, gCacheMutex must be held. Hash entry element must be in progress.
// value must be non NULL.
// On Exit, soft reference added to value. value and status stored in hash
// entry. Soft reference removed from previous stored value. Waiting
// threads notified.
void UnifiedCache::_put(
const UHashElement *element,
const SharedObject *value,
const UErrorCode status) const {
U_ASSERT(_inProgress(element));
const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
const SharedObject *oldValue = (const SharedObject *) element->value.pointer;
theKey->fCreationStatus = status;
if (value->noSoftReferences()) {
_registerMaster(theKey, value);
}
value->addSoftRef();
UHashElement *ptr = const_cast<UHashElement *>(element);
ptr->value.pointer = (void *) value;
oldValue->removeSoftRef();
// Tell waiting threads that we replace in-progress status with
// an error.
umtx_condBroadcast(&gInProgressValueAddedCond);
}
void
UnifiedCache::copyPtr(const SharedObject *src, const SharedObject *&dest) {
if(src != dest) {
if(dest != NULL) {
dest->removeRefWhileHoldingCacheLock();
}
dest = src;
if(src != NULL) {
src->addRefWhileHoldingCacheLock();
}
}
}
void
UnifiedCache::clearPtr(const SharedObject *&ptr) {
if (ptr != NULL) {
ptr->removeRefWhileHoldingCacheLock();
ptr = NULL;
}
}
// Fetch value and error code from a particular hash entry.
// On entry, gCacheMutex must be held. value must be either NULL or must be
// included in the ref count of the object to which it points.
// On exit, value and status set to what is in the hash entry. Caller must
// eventually call removeRef on value.
// If hash entry is in progress, value will be set to gNoValue and status will
// be set to U_ZERO_ERROR.
void UnifiedCache::_fetch(
const UHashElement *element,
const SharedObject *&value,
UErrorCode &status) {
const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
status = theKey->fCreationStatus;
// Since we have the cache lock, calling regular SharedObject methods
// could cause us to deadlock on ourselves since they may need to lock
// the cache mutex.
UnifiedCache::copyPtr((const SharedObject *) element->value.pointer, value);
}
// Determine if given hash entry is in progress.
// On entry, gCacheMutex must be held.
UBool UnifiedCache::_inProgress(const UHashElement *element) {
const SharedObject *value = NULL;
UErrorCode status = U_ZERO_ERROR;
_fetch(element, value, status);
UBool result = _inProgress(value, status);
// Since we have the cache lock, calling regular SharedObject methods
// could cause us to deadlock on ourselves since they may need to lock
// the cache mutex.
UnifiedCache::clearPtr(value);
return result;
}
// Determine if given hash entry is in progress.
// On entry, gCacheMutex must be held.
UBool UnifiedCache::_inProgress(
const SharedObject *theValue, UErrorCode creationStatus) {
return (theValue == gNoValue && creationStatus == U_ZERO_ERROR);
}
// Determine if given hash entry is eligible for eviction.
// On entry, gCacheMutex must be held.
UBool UnifiedCache::_isEvictable(const UHashElement *element) {
const CacheKeyBase *theKey = (const CacheKeyBase *) element->key.pointer;
const SharedObject *theValue =
(const SharedObject *) element->value.pointer;
// Entries that are under construction are never evictable
if (_inProgress(theValue, theKey->fCreationStatus)) {
return FALSE;
}
// We can evict entries that are either not a master or have just
// one reference (The one reference being from the cache itself).
return (!theKey->fIsMaster || (theValue->getSoftRefCount() == 1 && theValue->noHardReferences()));
}
U_NAMESPACE_END