/src/icu/source/common/unifiedcache.h
Line | Count | Source (jump to first uncovered line) |
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 | | |
25 | | struct UHashtable; |
26 | | struct UHashElement; |
27 | | |
28 | | U_NAMESPACE_BEGIN |
29 | | |
30 | | class UnifiedCache; |
31 | | |
32 | | /** |
33 | | * A base class for all cache keys. |
34 | | */ |
35 | | class U_COMMON_API CacheKeyBase : public UObject { |
36 | | public: |
37 | 0 | CacheKeyBase() : fCreationStatus(U_ZERO_ERROR), fIsPrimary(false) {} |
38 | | |
39 | | /** |
40 | | * Copy constructor. Needed to support cloning. |
41 | | */ |
42 | | CacheKeyBase(const CacheKeyBase &other) |
43 | 0 | : 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 NULL |
61 | | * and set status to an error. |
62 | | * |
63 | | * @param creationContext the context in which the object is being |
64 | | * created. May be NULL. |
65 | | * @param status Implementations can return a failure here. |
66 | | * In addition, implementations may return a |
67 | | * non NULL 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 NULL terminated. |
75 | | */ |
76 | | virtual char *writeDescription(char *buffer, int32_t bufSize) const = 0; |
77 | | |
78 | | friend inline bool operator==(const CacheKeyBase& lhs, |
79 | 0 | const CacheKeyBase& rhs) { |
80 | 0 | return lhs.equals(rhs); |
81 | 0 | } |
82 | | |
83 | | friend inline bool operator!=(const CacheKeyBase& lhs, |
84 | 0 | const CacheKeyBase& rhs) { |
85 | 0 | return !lhs.equals(rhs); |
86 | 0 | } |
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 | | */ |
103 | | template<typename T> |
104 | | class CacheKey : public CacheKeyBase { |
105 | | public: |
106 | | virtual ~CacheKey() { } |
107 | | /** |
108 | | * The template parameter, T, determines the hash code returned. |
109 | | */ |
110 | 0 | virtual int32_t hashCode() const override { |
111 | 0 | const char *s = typeid(T).name(); |
112 | 0 | return ustr_hashCharsN(s, static_cast<int32_t>(uprv_strlen(s))); |
113 | 0 | } |
114 | | |
115 | | /** |
116 | | * Use the value type, T, as the description. |
117 | | */ |
118 | 0 | virtual char *writeDescription(char *buffer, int32_t bufLen) const override { |
119 | 0 | const char *s = typeid(T).name(); |
120 | 0 | uprv_strncpy(buffer, s, bufLen); |
121 | 0 | buffer[bufLen - 1] = 0; |
122 | 0 | return buffer; |
123 | 0 | } |
124 | | |
125 | | protected: |
126 | | /** |
127 | | * Two objects are equal if they are of the same type. |
128 | | */ |
129 | 0 | virtual bool equals(const CacheKeyBase &other) const override { |
130 | 0 | return this == &other || typeid(*this) == typeid(other); |
131 | 0 | } |
132 | | }; |
133 | | |
134 | | /** |
135 | | * Cache key based on locale. |
136 | | * A key of type LocaleCacheKey<T> maps to a value of type T. |
137 | | */ |
138 | | template<typename T> |
139 | | class LocaleCacheKey : public CacheKey<T> { |
140 | | protected: |
141 | | Locale fLoc; |
142 | 0 | virtual bool equals(const CacheKeyBase &other) const override { |
143 | 0 | if (!CacheKey<T>::equals(other)) { |
144 | 0 | return false; |
145 | 0 | } |
146 | | // We know this and other are of same class because equals() on |
147 | | // CacheKey returned true. |
148 | 0 | return operator==(static_cast<const LocaleCacheKey<T> &>(other)); |
149 | 0 | } |
150 | | public: |
151 | 0 | LocaleCacheKey(const Locale &loc) : fLoc(loc) {} |
152 | | LocaleCacheKey(const LocaleCacheKey<T> &other) |
153 | 0 | : CacheKey<T>(other), fLoc(other.fLoc) { } |
154 | 0 | virtual ~LocaleCacheKey() { } |
155 | 0 | virtual int32_t hashCode() const override { |
156 | 0 | return (int32_t)(37u * (uint32_t)CacheKey<T>::hashCode() + (uint32_t)fLoc.hashCode()); |
157 | 0 | } |
158 | 0 | inline bool operator == (const LocaleCacheKey<T> &other) const { |
159 | 0 | return fLoc == other.fLoc; |
160 | 0 | } |
161 | 0 | virtual CacheKeyBase *clone() const override { |
162 | 0 | return new LocaleCacheKey<T>(*this); |
163 | 0 | } |
164 | | virtual const T *createObject( |
165 | | const void *creationContext, UErrorCode &status) const override; |
166 | | /** |
167 | | * Use the locale id as the description. |
168 | | */ |
169 | 0 | virtual char *writeDescription(char *buffer, int32_t bufLen) const override { |
170 | 0 | const char *s = fLoc.getName(); |
171 | 0 | uprv_strncpy(buffer, s, bufLen); |
172 | 0 | buffer[bufLen - 1] = 0; |
173 | 0 | return buffer; |
174 | 0 | } |
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 | | */ |
183 | | class 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, NULL, 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, NULL, 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 NULL 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 NULL 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 | 0 | UErrorCode &status) const { |
229 | 0 | if (U_FAILURE(status)) { |
230 | 0 | return; |
231 | 0 | } |
232 | 0 | UErrorCode creationStatus = U_ZERO_ERROR; |
233 | 0 | const SharedObject *value = NULL; |
234 | 0 | _get(key, value, creationContext, creationStatus); |
235 | 0 | const T *tvalue = (const T *) value; |
236 | 0 | if (U_SUCCESS(creationStatus)) { |
237 | 0 | SharedObject::copyPtr(tvalue, ptr); |
238 | 0 | } |
239 | 0 | SharedObject::clearPtr(tvalue); |
240 | | // Take care not to overwrite a warning status passed in with |
241 | | // another warning or U_ZERO_ERROR. |
242 | 0 | if (status == U_ZERO_ERROR || U_FAILURE(creationStatus)) { |
243 | 0 | status = creationStatus; |
244 | 0 | } |
245 | 0 | } |
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 == NULL. |
258 | | * @param loc the locale |
259 | | * @param ptr On entry, must be NULL 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 NULL 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); |
358 | | UnifiedCache &operator=(const UnifiedCache &other); |
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 NULL. 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 NULL. Caller must call |
386 | | * removeRef on value if non NULL. |
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 NULL 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 NULL. |
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 NULL 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 | | |
554 | | U_NAMESPACE_END |
555 | | |
556 | | #endif |