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.H - The ICU Unified cache.
10******************************************************************************
11*/
12
13#ifndef __UNIFIED_CACHE_H__
14#define __UNIFIED_CACHE_H__
15
16#include "utypeinfo.h" // for 'typeid' to work
17
18#include "unicode/uobject.h"
19#include "unicode/locid.h"
20#include "sharedobject.h"
21#include "unicode/unistr.h"
22#include "cstring.h"
23#include "ustr_imp.h"
24
25struct UHashtable;
26struct UHashElement;
27
28U_NAMESPACE_BEGIN
29
30class UnifiedCache;
31
32/**
33 * A base class for all cache keys.
34 */
35class U_COMMON_API CacheKeyBase : public UObject {
36 public:
37 CacheKeyBase() : fCreationStatus(U_ZERO_ERROR), fIsPrimary(false) {}
38
39 /**
40 * Copy constructor. Needed to support cloning.
41 */
42 CacheKeyBase(const CacheKeyBase &other)
43 : UObject(other), fCreationStatus(other.fCreationStatus), fIsPrimary(false) { }
44 virtual ~CacheKeyBase();
45
46 /**
47 * Returns the hash code for this object.
48 */
49 virtual int32_t hashCode() const = 0;
50
51 /**
52 * Clones this object polymorphically. Caller owns returned value.
53 */
54 virtual CacheKeyBase *clone() const = 0;
55
56 /**
57 * Create a new object for this key. Called by cache on cache miss.
58 * createObject must add a reference to the object it returns. Note
59 * that getting an object from the cache and returning it without calling
60 * removeRef on it satisfies this requirement. It can also return nullptr
61 * and set status to an error.
62 *
63 * @param creationContext the context in which the object is being
64 * created. May be nullptr.
65 * @param status Implementations can return a failure here.
66 * In addition, implementations may return a
67 * non nullptr object and set a warning status.
68 */
69 virtual const SharedObject *createObject(
70 const void *creationContext, UErrorCode &status) const = 0;
71
72 /**
73 * Writes a description of this key to buffer and returns buffer. Written
74 * description is nullptr terminated.
75 */
76 virtual char *writeDescription(char *buffer, int32_t bufSize) const = 0;
77
78 friend inline bool operator==(const CacheKeyBase& lhs,
79 const CacheKeyBase& rhs) {
80 return lhs.equals(rhs);
81 }
82
83 friend inline bool operator!=(const CacheKeyBase& lhs,
84 const CacheKeyBase& rhs) {
85 return !lhs.equals(rhs);
86 }
87
88 protected:
89 virtual bool equals(const CacheKeyBase& other) const = 0;
90
91 private:
92 mutable UErrorCode fCreationStatus;
93 mutable UBool fIsPrimary;
94 friend class UnifiedCache;
95};
96
97
98
99/**
100 * Templated version of CacheKeyBase.
101 * A key of type LocaleCacheKey<T> maps to a value of type T.
102 */
103template<typename T>
104class CacheKey : public CacheKeyBase {
105 public:
106 virtual ~CacheKey() { }
107 /**
108 * The template parameter, T, determines the hash code returned.
109 */
110 virtual int32_t hashCode() const override {
111 const char *s = typeid(T).name();
112 return ustr_hashCharsN(s, static_cast<int32_t>(uprv_strlen(s)));
113 }
114
115 /**
116 * Use the value type, T, as the description.
117 */
118 virtual char *writeDescription(char *buffer, int32_t bufLen) const override {
119 const char *s = typeid(T).name();
120 uprv_strncpy(buffer, s, bufLen);
121 buffer[bufLen - 1] = 0;
122 return buffer;
123 }
124
125 protected:
126 /**
127 * Two objects are equal if they are of the same type.
128 */
129 virtual bool equals(const CacheKeyBase &other) const override {
130 return this == &other || typeid(*this) == typeid(other);
131 }
132};
133
134/**
135 * Cache key based on locale.
136 * A key of type LocaleCacheKey<T> maps to a value of type T.
137 */
138template<typename T>
139class LocaleCacheKey : public CacheKey<T> {
140 protected:
141 Locale fLoc;
142 virtual bool equals(const CacheKeyBase &other) const override {
143 if (!CacheKey<T>::equals(other)) {
144 return false;
145 }
146 // We know this and other are of same class because equals() on
147 // CacheKey returned true.
148 return operator==(static_cast<const LocaleCacheKey<T> &>(other));
149 }
150 public:
151 LocaleCacheKey(const Locale &loc) : fLoc(loc) {}
152 LocaleCacheKey(const LocaleCacheKey<T> &other)
153 : CacheKey<T>(other), fLoc(other.fLoc) { }
154 virtual ~LocaleCacheKey() { }
155 virtual int32_t hashCode() const override {
156 return (int32_t)(37u * (uint32_t)CacheKey<T>::hashCode() + (uint32_t)fLoc.hashCode());
157 }
158 inline bool operator == (const LocaleCacheKey<T> &other) const {
159 return fLoc == other.fLoc;
160 }
161 virtual CacheKeyBase *clone() const override {
162 return new LocaleCacheKey<T>(*this);
163 }
164 virtual const T *createObject(
165 const void *creationContext, UErrorCode &status) const override;
166 /**
167 * Use the locale id as the description.
168 */
169 virtual char *writeDescription(char *buffer, int32_t bufLen) const override {
170 const char *s = fLoc.getName();
171 uprv_strncpy(buffer, s, bufLen);
172 buffer[bufLen - 1] = 0;
173 return buffer;
174 }
175
176};
177
178/**
179 * The unified cache. A singleton type.
180 * Design doc here:
181 * https://docs.google.com/document/d/1RwGQJs4N4tawNbf809iYDRCvXoMKqDJihxzYt1ysmd8/edit?usp=sharing
182 */
183class U_COMMON_API UnifiedCache : public UnifiedCacheBase {
184 public:
185 /**
186 * @internal
187 * Do not call directly. Instead use UnifiedCache::getInstance() as
188 * there should be only one UnifiedCache in an application.
189 */
190 UnifiedCache(UErrorCode &status);
191
192 /**
193 * Return a pointer to the global cache instance.
194 */
195 static UnifiedCache *getInstance(UErrorCode &status);
196
197 /**
198 * Fetches a value from the cache by key. Equivalent to
199 * get(key, nullptr, ptr, status);
200 */
201 template<typename T>
202 void get(
203 const CacheKey<T>& key,
204 const T *&ptr,
205 UErrorCode &status) const {
206 get(key, nullptr, ptr, status);
207 }
208
209 /**
210 * Fetches value from the cache by key.
211 *
212 * @param key the cache key.
213 * @param creationContext passed verbatim to createObject method of key
214 * @param ptr On entry, ptr must be nullptr or be included if
215 * the reference count of the object it points
216 * to. On exit, ptr points to the fetched object
217 * from the cache or is left unchanged on
218 * failure. Caller must call removeRef on ptr
219 * if set to a non nullptr value.
220 * @param status Any error returned here. May be set to a
221 * warning value even if ptr is set.
222 */
223 template<typename T>
224 void get(
225 const CacheKey<T>& key,
226 const void *creationContext,
227 const T *&ptr,
228 UErrorCode &status) const {
229 if (U_FAILURE(status)) {
230 return;
231 }
232 UErrorCode creationStatus = U_ZERO_ERROR;
233 const SharedObject *value = nullptr;
234 _get(key, value, creationContext, creationStatus);
235 const T *tvalue = (const T *) value;
236 if (U_SUCCESS(creationStatus)) {
237 SharedObject::copyPtr(tvalue, ptr);
238 }
239 SharedObject::clearPtr(tvalue);
240 // Take care not to overwrite a warning status passed in with
241 // another warning or U_ZERO_ERROR.
242 if (status == U_ZERO_ERROR || U_FAILURE(creationStatus)) {
243 status = creationStatus;
244 }
245 }
246
247#ifdef UNIFIED_CACHE_DEBUG
248 /**
249 * Dumps the contents of this cache to standard error. Used for testing of
250 * cache only.
251 */
252 void dumpContents() const;
253#endif
254
255 /**
256 * Convenience method to get a value of type T from cache for a
257 * particular locale with creationContext == nullptr.
258 * @param loc the locale
259 * @param ptr On entry, must be nullptr or included in the ref count
260 * of the object to which it points.
261 * On exit, fetched value stored here or is left
262 * unchanged on failure. Caller must call removeRef on
263 * ptr if set to a non nullptr value.
264 * @param status Any error returned here. May be set to a
265 * warning value even if ptr is set.
266 */
267 template<typename T>
268 static void getByLocale(
269 const Locale &loc, const T *&ptr, UErrorCode &status) {
270 const UnifiedCache *cache = getInstance(status);
271 if (U_FAILURE(status)) {
272 return;
273 }
274 cache->get(LocaleCacheKey<T>(loc), ptr, status);
275 }
276
277#ifdef UNIFIED_CACHE_DEBUG
278 /**
279 * Dumps the cache contents to stderr. For testing only.
280 */
281 static void dump();
282#endif
283
284 /**
285 * Returns the number of keys in this cache. For testing only.
286 */
287 int32_t keyCount() const;
288
289 /**
290 * Removes any values from cache that are not referenced outside
291 * the cache.
292 */
293 void flush() const;
294
295 /**
296 * Configures at what point eviction of unused entries will begin.
297 * Eviction is triggered whenever the number of evictable keys exceeds
298 * BOTH count AND (number of in-use items) * (percentageOfInUseItems / 100).
299 * Once the number of unused entries drops below one of these,
300 * eviction ceases. Because eviction happens incrementally,
301 * the actual unused entry count may exceed both these numbers
302 * from time to time.
303 *
304 * A cache entry is defined as unused if it is not essential to guarantee
305 * that for a given key X, the cache returns the same reference to the
306 * same value as long as the client already holds a reference to that
307 * value.
308 *
309 * If this method is never called, the default settings are 1000 and 100%.
310 *
311 * Although this method is thread-safe, it is designed to be called at
312 * application startup. If it is called in the middle of execution, it
313 * will have no immediate effect on the cache. However over time, the
314 * cache will perform eviction slices in an attempt to honor the new
315 * settings.
316 *
317 * If a client already holds references to many different unique values
318 * in the cache such that the number of those unique values far exceeds
319 * "count" then the cache may not be able to maintain this maximum.
320 * However, if this happens, the cache still guarantees that the number of
321 * unused entries will remain only a small percentage of the total cache
322 * size.
323 *
324 * If the parameters passed are negative, setEvctionPolicy sets status to
325 * U_ILLEGAL_ARGUMENT_ERROR.
326 */
327 void setEvictionPolicy(
328 int32_t count, int32_t percentageOfInUseItems, UErrorCode &status);
329
330
331 /**
332 * Returns how many entries have been auto evicted during the lifetime
333 * of this cache. This only includes auto evicted entries, not
334 * entries evicted because of a call to flush().
335 */
336 int64_t autoEvictedCount() const;
337
338 /**
339 * Returns the unused entry count in this cache. For testing only,
340 * Regular clients will not need this.
341 */
342 int32_t unusedCount() const;
343
344 virtual void handleUnreferencedObject() const override;
345 virtual ~UnifiedCache();
346
347 private:
348 UHashtable *fHashtable;
349 mutable int32_t fEvictPos;
350 mutable int32_t fNumValuesTotal;
351 mutable int32_t fNumValuesInUse;
352 int32_t fMaxUnused;
353 int32_t fMaxPercentageOfInUse;
354 mutable int64_t fAutoEvictedCount;
355 SharedObject *fNoValue;
356
357 UnifiedCache(const UnifiedCache &other) = delete;
358 UnifiedCache &operator=(const UnifiedCache &other) = delete;
359
360 /**
361 * Flushes the contents of the cache. If cache values hold references to other
362 * cache values then _flush should be called in a loop until it returns false.
363 *
364 * On entry, gCacheMutex must be held.
365 * On exit, those values with are evictable are flushed.
366 *
367 * @param all if false flush evictable items only, which are those with no external
368 * references, plus those that can be safely recreated.<br>
369 * if true, flush all elements. Any values (sharedObjects) with remaining
370 * hard (external) references are not deleted, but are detached from
371 * the cache, so that a subsequent removeRefs can delete them.
372 * _flush is not thread safe when all is true.
373 * @return true if any value in cache was flushed or false otherwise.
374 */
375 UBool _flush(UBool all) const;
376
377 /**
378 * Gets value out of cache.
379 * On entry. gCacheMutex must not be held. value must be nullptr. status
380 * must be U_ZERO_ERROR.
381 * On exit. value and status set to what is in cache at key or on cache
382 * miss the key's createObject() is called and value and status are set to
383 * the result of that. In this latter case, best effort is made to add the
384 * value and status to the cache. If createObject() fails to create a value,
385 * fNoValue is stored in cache, and value is set to nullptr. Caller must call
386 * removeRef on value if non nullptr.
387 */
388 void _get(
389 const CacheKeyBase &key,
390 const SharedObject *&value,
391 const void *creationContext,
392 UErrorCode &status) const;
393
394 /**
395 * Attempts to fetch value and status for key from cache.
396 * On entry, gCacheMutex must not be held value must be nullptr and status must
397 * be U_ZERO_ERROR.
398 * On exit, either returns false (In this
399 * case caller should try to create the object) or returns true with value
400 * pointing to the fetched value and status set to fetched status. When
401 * false is returned status may be set to failure if an in progress hash
402 * entry could not be made but value will remain unchanged. When true is
403 * returned, caller must call removeRef() on value.
404 */
405 UBool _poll(
406 const CacheKeyBase &key,
407 const SharedObject *&value,
408 UErrorCode &status) const;
409
410 /**
411 * Places a new value and creationStatus in the cache for the given key.
412 * On entry, gCacheMutex must be held. key must not exist in the cache.
413 * On exit, value and creation status placed under key. Soft reference added
414 * to value on successful add. On error sets status.
415 */
416 void _putNew(
417 const CacheKeyBase &key,
418 const SharedObject *value,
419 const UErrorCode creationStatus,
420 UErrorCode &status) const;
421
422 /**
423 * Places value and status at key if there is no value at key or if cache
424 * entry for key is in progress. Otherwise, it leaves the current value and
425 * status there.
426 *
427 * On entry. gCacheMutex must not be held. Value must be
428 * included in the reference count of the object to which it points.
429 *
430 * On exit, value and status are changed to what was already in the cache if
431 * something was there and not in progress. Otherwise, value and status are left
432 * unchanged in which case they are placed in the cache on a best-effort basis.
433 * Caller must call removeRef() on value.
434 */
435 void _putIfAbsentAndGet(
436 const CacheKeyBase &key,
437 const SharedObject *&value,
438 UErrorCode &status) const;
439
440 /**
441 * Returns the next element in the cache round robin style.
442 * Returns nullptr if the cache is empty.
443 * On entry, gCacheMutex must be held.
444 */
445 const UHashElement *_nextElement() const;
446
447 /**
448 * Return the number of cache items that would need to be evicted
449 * to bring usage into conformance with eviction policy.
450 *
451 * An item corresponds to an entry in the hash table, a hash table element.
452 *
453 * On entry, gCacheMutex must be held.
454 */
455 int32_t _computeCountOfItemsToEvict() const;
456
457 /**
458 * Run an eviction slice.
459 * On entry, gCacheMutex must be held.
460 * _runEvictionSlice runs a slice of the evict pipeline by examining the next
461 * 10 entries in the cache round robin style evicting them if they are eligible.
462 */
463 void _runEvictionSlice() const;
464
465 /**
466 * Register a primary cache entry. A primary key is the first key to create
467 * a given SharedObject value. Subsequent keys whose create function
468 * produce references to an already existing SharedObject are not primary -
469 * they can be evicted and subsequently recreated.
470 *
471 * On entry, gCacheMutex must be held.
472 * On exit, items in use count incremented, entry is marked as a primary
473 * entry, and value registered with cache so that subsequent calls to
474 * addRef() and removeRef() on it correctly interact with the cache.
475 */
476 void _registerPrimary(const CacheKeyBase *theKey, const SharedObject *value) const;
477
478 /**
479 * Store a value and creation error status in given hash entry.
480 * On entry, gCacheMutex must be held. Hash entry element must be in progress.
481 * value must be non nullptr.
482 * On Exit, soft reference added to value. value and status stored in hash
483 * entry. Soft reference removed from previous stored value. Waiting
484 * threads notified.
485 */
486 void _put(
487 const UHashElement *element,
488 const SharedObject *value,
489 const UErrorCode status) const;
490 /**
491 * Remove a soft reference, and delete the SharedObject if no references remain.
492 * To be used from within the UnifiedCache implementation only.
493 * gCacheMutex must be held by caller.
494 * @param value the SharedObject to be acted on.
495 */
496 void removeSoftRef(const SharedObject *value) const;
497
498 /**
499 * Increment the hard reference count of the given SharedObject.
500 * gCacheMutex must be held by the caller.
501 * Update numValuesEvictable on transitions between zero and one reference.
502 *
503 * @param value The SharedObject to be referenced.
504 * @return the hard reference count after the addition.
505 */
506 int32_t addHardRef(const SharedObject *value) const;
507
508 /**
509 * Decrement the hard reference count of the given SharedObject.
510 * gCacheMutex must be held by the caller.
511 * Update numValuesEvictable on transitions between one and zero reference.
512 *
513 * @param value The SharedObject to be referenced.
514 * @return the hard reference count after the removal.
515 */
516 int32_t removeHardRef(const SharedObject *value) const;
517
518
519#ifdef UNIFIED_CACHE_DEBUG
520 void _dumpContents() const;
521#endif
522
523 /**
524 * Fetch value and error code from a particular hash entry.
525 * On entry, gCacheMutex must be held. value must be either nullptr or must be
526 * included in the ref count of the object to which it points.
527 * On exit, value and status set to what is in the hash entry. Caller must
528 * eventually call removeRef on value.
529 * If hash entry is in progress, value will be set to gNoValue and status will
530 * be set to U_ZERO_ERROR.
531 */
532 void _fetch(const UHashElement *element, const SharedObject *&value,
533 UErrorCode &status) const;
534
535 /**
536 * Determine if given hash entry is in progress.
537 * On entry, gCacheMutex must be held.
538 */
539 UBool _inProgress(const UHashElement *element) const;
540
541 /**
542 * Determine if given hash entry is in progress.
543 * On entry, gCacheMutex must be held.
544 */
545 UBool _inProgress(const SharedObject *theValue, UErrorCode creationStatus) const;
546
547 /**
548 * Determine if given hash entry is eligible for eviction.
549 * On entry, gCacheMutex must be held.
550 */
551 UBool _isEvictable(const UHashElement *element) const;
552};
553
554U_NAMESPACE_END
555
556#endif
557