Coverage Report

Created: 2024-04-24 06:23

/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