HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_ThreadSafeCache.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_ThreadSafeCache.h ( UT Library, C++ )
7  *
8  * COMMENTS: A fast, thread-safe cache to be used for high-performance
9  * applications.
10  */
11 
12 #ifndef __UT_ThreadSafeCache__
13 #define __UT_ThreadSafeCache__
14 
15 #include "UT_API.h"
16 #include <map>
17 #include <SYS/SYS_AtomicInt.h>
18 #include <SYS/SYS_MemoryOrder.h>
19 #include <SYS/SYS_Types.h>
20 #include "UT_LockUtil.h"
21 #include "UT_Lock.h"
22 #include "UT_StopWatch.h"
23 
24 //#define ITEM_TIMING
25 
26 // Explicit instantiations are provided for:
27 // - UT_Lock
28 // - UT_RecursiveSpinLock
29 template <class Lock>
31 public:
32  class unsafe_traverser;
33 
34  // A cache item stub. You must implement a subclass to provide
35  // allocation and deallocation routines.
37  {
38  public:
40  : myPrev(0), myNext(0), myMemory(0)
41  , myRefCount(0), myTimeStamp(0)
42  , myAllocated(false) {}
43  virtual ~UT_CacheItem() { UT_ASSERT(!getRefCount()); }
44 
45  // Return a string to be used in diagnostic messages about
46  // different cache types.
47  virtual const char *getItemType() const = 0;
48 
49  // Retrieve the amount of memory consumed by the cache item
50  int64 getMemoryUsage() const { return myMemory; }
51 
52  protected:
53  // Allocate an item and return the total amount of memory consumed
54  // by the cache item in bytes.
55  virtual int64 allocate(void *parms) = 0;
56 
57  // Deallocate the item and free associated memory.
58  virtual void deallocate(void *user_data) = 0;
59 
60  private:
61  /// NOTE: Code seems to rely on getRefCount() using
62  /// SYS_MEMORY_ORDER_SEQ_CST, not just SYS_MEMORY_ORDER_LOAD.
63  /// With SYS_MEMORY_ORDER_LOAD, the unit test fails
64  /// about 2.7% of the time.
65  int getRefCount() const { return myRefCount.load(SYS_MEMORY_ORDER_SEQ_CST); }
66  int incRefCount() { return myRefCount.add(1); }
67  int decRefCount() { return myRefCount.add(-1); }
68 
69  bool isInCache() const { return myNext; }
70 
71  // Unlink the item, leaving the existing next/prev unchanged (clear
72  // them with clearLinks()).
73  void unlink()
74  {
75  myPrev->myNext = myNext;
76  myNext->myPrev = myPrev;
77  }
78  // Set links to 0
79  void clearLinks()
80  {
81  myPrev = 0;
82  myNext = 0;
83  }
84  // Insert the item before the given item
85  void link(UT_CacheItem *before)
86  {
87  // NOTE: Although isInCache() is called from
88  // unlocked code, and it only checks whether
89  // myNext is non-NULL, nothing after that depends
90  // on the other values set in this function, so
91  // the other values here don't need to be set
92  // first.
93 
94  myNext = before;
95  myPrev = before->myPrev;
96 
97  before->myPrev->myNext = this;
98  before->myPrev = this;
99  }
100  // Link to ourselves - for a circular list of size 1
101  void selfLink()
102  {
103  myNext = this;
104  myPrev = this;
105  }
106 
107  private:
108  // Force the compiler to read/write myNext and myPrev when
109  // indicated, instead of saving temporary values or reordering
110  // the access. myNext is used to determine if this is cached,
111  // which could be changed by another thread, so is important
112  // to re-read each time.
113  UT_CacheItem *volatile myNext;
114  UT_CacheItem *volatile myPrev;
115 
116  // NOTE: Even myMemory and myTimeStamp must be volatile, because
117  // they get read before locking, then read again after locking,
118  // possibly having been written by another thread in between.
119  volatile int64 myMemory;
120  volatile uint64 myTimeStamp;
121 #ifdef ITEM_TIMING
122  double myAllocationTime;
123 #endif
124  SYS_AtomicInt32 myRefCount;
125 
126  // Force the compiler to read/write myAllocated when
127  // indicated, instead of saving temporary values or reordering
128  // the access. myAllocated could be changed by another thread,
129  // upon allocating or deallocating, so is important to re-read
130  // each time.
131  volatile bool myAllocated;
132 
133  friend class UT_ThreadSafeCache;
135  };
136 
137 public:
138  // The destroy flag controls whether the cache will clean up its
139  // allocated items on destruction.
140  UT_ThreadSafeCache(bool destroy = true);
142 
143  // Set cache size in megabytes
144  void setMaxMemory(int64 size_mb, bool prune = false);
145  // Set cache size in bytes
146  void setMaxMemoryBytes(int64 size_bytes, bool prune = false);
148  { return myMemoryLimit; }
149 
150  // Get total cache memory usage in bytes, including all allocated item
151  // memory.
152  int64 getMemoryUsage() const { return myMemoryUsed; }
153 
154  // Get number of cached items
155  int64 entries() const { return myEntries; }
156 
157  // Set user data that is passed to allocate()/deallocate()
158  void setUserData(void *data) { myUserData = data; }
159 
160  // Control whether we evict items when memory limit is used. Default is
161  // true.
162  void setCheckMemoryLimit(bool check)
163  { myCheckMemoryLimit = check; }
164  bool getCheckMemoryLimit() const
165  { return myCheckMemoryLimit; }
166 
167  // Access an item in the cache. If the item is not already in the
168  // cache, it will be inserted at the head. Calling this operation
169  // acquires an access lock that must be released with release(). parms
170  // will be passed directly to the allocate() operation.
171  void access(UT_CacheItem *item, void *parms = 0)
172  {
173  item->incRefCount();
174 
175  // This prevents the memory load in item->isInCache() from occurring
176  // before the store in item->incRefCount(), which is necessary for
177  // the reasons outlined in freeItem(). Basically, item could be
178  // deallocated after calling item->incRefCount(), but only if
179  // item->incRefCount() occurs after item->isInCache() becomes false.
180  // Thus, so long as item->isInCache() is read after
181  // item->incRefCount(), it won't get a stale true value, which would
182  // have falsely indicated that allocation isn't necessary.
183  SYSmemoryFence();
184 
185  // Before moving items in the cache, check
186  // whether the head has been moved a
187  // sufficient number of times to make it
188  // useful to move the item back to the head
189  // of the cache. This way, if the same set
190  // of items are always referenced we never
191  // need to modify the cache.
192  if (item->isInCache() && isNearHead(item))
193  {
194  return;
195  }
196 
197  // Now, reorder the item in the cache
198  accessLockedReorder(item, parms);
199  }
200 
201  // Release the access lock on an item. For every call to access()
202  // there must be a corresponding call to release().
203  void release(UT_CacheItem *item)
204  {
205  if (!item->decRefCount() && !item->isInCache())
206  freeItem(item);
207  }
208 
209  // Release the access lock and remove an item from the cache, if there
210  // are no more references.
211  void releaseAndDeallocate(UT_CacheItem *item)
212  {
213  if (!item->decRefCount())
214  freeItem(item);
215  }
216 
217  // Deallocates and removes an item from the cache. This is not
218  // thread-safe while anything has a reference to the item.
219  void freeItem(UT_CacheItem *item);
220 
221  // Clear all entries from the cache.
222  void freeAllItems();
223 
224  // Prune entries from the cache until we hit the given memory usage
225  void pruneItems(int64 memory_limit);
226 
227  // Prints fault statistics categorized by item type
228  void dumpStats(const char *name) const;
229 
231  {
232  public:
234  : myCurr(NULL)
235  , myHead(NULL)
236  {}
238  : myCurr(src.myCurr)
239  , myHead(src.myHead)
240  {}
242 
243  const UT_CacheItem *get() const { return myCurr; }
244  int operator==(const unsafe_traverser &cmp) const
245  { return myCurr == cmp.myCurr; }
246  int operator!=(const unsafe_traverser &cmp) const
247  { return myCurr != cmp.myCurr; }
248  bool atEnd() const
249  { return !myCurr; }
250  void rewind()
251  { myCurr = myHead; }
253  {
254  if (myCurr && myCurr->myNext != myHead)
255  myCurr = myCurr->myNext;
256  else
257  myCurr = NULL;
258  return *this;
259  }
261  {
262  myCurr = src.myCurr;
263  myHead = src.myHead;
264  return *this;
265  }
266  private:
268  : myCurr(head)
269  , myHead(head)
270  {}
271  const UT_CacheItem *myCurr, *myHead;
272  friend class UT_ThreadSafeCache;
273  };
274 
275  unsafe_traverser unsafe_begin() const
276  { return unsafe_traverser(myHead); }
277  unsafe_traverser unsafe_end() const
278  { return unsafe_traverser(); }
279 
280 private:
281  /// Reorder the list due to access - requires locking
282  void accessLockedReorder(UT_CacheItem *item, void *parms);
283 
284  void pruneItemsNoLock(int64 memory_limit);
285  void addToCache(UT_CacheItem *item);
286  void removeFromCache(UT_CacheItem *item);
287  void allocateItem(UT_CacheItem *item, void *parms)
288  {
289  if (!item->myAllocated)
290  {
292  lock(myObjLock, item);
293  if (!item->myAllocated)
294  {
295 #ifdef ITEM_TIMING
296  UT_StopWatch timer;
297  timer.start();
298 #endif
299  item->myMemory = item->allocate(
300  parms ? parms : myUserData);
301 
302  // Ensure that the data allocated are written out
303  // to main memory before setting myAllocated to true,
304  // else something could read myAllocated, see that it's
305  // true, read an out-of-date data pointer, probably still
306  // NULL, and crash dereferencing it.
307  SYSstoreFence();
308 
309  item->myAllocated = true;
310 
311  // NOTE: The automatic unlock will do a second SYSstoreFence,
312  // ensuring that myAllocated will be true before the
313  // lock is released.
314 
315 #ifdef ITEM_TIMING
316  item->myAllocationTime = timer.lap();
317 #endif
318  }
319  }
320 
321  // Ensure that code in the calling function doesn't
322  // speculatively read data from item before the read of
323  // item->myAllocated above. Without it, what could happen is:
324  // 0) item->myAllocated starts false, and some subclass member,
325  // p, starts NULL.
326  // 1) This thread (in the calling function after this call)
327  // speculatively reads p, getting NULL.
328  // 2) Another thread sets p to a valid address, and does a store
329  // fence, to ensure it's written out.
330  // 3) The other thread sets myAllocated to true.
331  // 4) The other thread unlocks, doing a store fence just before
332  // unlocking, to ensure myAllocated is written out.
333  // 5) This thread (at the top of this function) reads myAllocated,
334  // getting true.
335  // 6) The calling function already has a value for p, and myAllocated
336  // is true, so it dereferences p, and crashes.
337  SYSloadFence();
338  }
339 
340  // Heuristic to decide when an item is close to the head. Items can
341  // only be moved when this method returns false.
342  bool isNearHead(const UT_CacheItem *item) const
343  { return myHeadTime - item->myTimeStamp <=
344  myQuarterEntries; }
345 
346 private:
347 
348  typedef typename Lock::Scope LockScope;
349 
350  // This class keeps track of fault statistics for a given type of item
351  // in the cache.
352  class FaultStats {
353  public:
354  FaultStats()
355  : myFaults(0)
356  , myTotalMemory(0)
357  , myTotalTime(0) {}
358 
359  public:
360  int64 myFaults;
361  int64 myTotalMemory;
362  double myTotalTime;
363  };
364 
365  typedef std::map<const char *, FaultStats> FaultMap;
366 
367  UT_ObjLockType<Lock> myObjLock;
368  Lock myThreadLock;
369  UT_CacheItem *myHead;
370  int64 myMemoryLimit;
371  int64 myMemoryUsed;
372  int64 myEntries;
373  int64 myQuarterEntries;
374  FaultMap myFaultMap;
375  uint64 myHeadTime;
376  void *myUserData;
377  bool myDestroy;
378  bool myCheckMemoryLimit;
379 };
380 
381 /// This can be used as a unified cache for a process. The cache will not
382 /// destroy any items left in the cache when the process exits.
384 {
385 public:
386  static UT_ThreadSafeCache<UT_Lock> &get() { return theCache; }
387 
388  /// Set the amount of memory to be used by the cache, in MB
389  static void setMaxMemory(int size_mb)
390  {
391  theCache.setMaxMemory(size_mb);
392  theMemorySet = true;
393  }
394 
395  /// Check whether the memory limit has been set
396  static bool isMaxMemorySet()
397  { return theMemorySet; }
398 
400  { return theCache.getMemoryUsage(); }
401 
402 private:
403  static UT_ThreadSafeCache<UT_Lock> theCache;
404  static bool theMemorySet;
405 };
406 
407 /// Scoped accessor object for accessing unified cache items.
408 template<typename T>
410 {
411 public:
412  /// Default initializer. Can be used to initialize the accessor to a cache
413  /// item right away. Otherwise call @c reset to set the item to access.
414  UT_UnifiedCacheAccessor(T *item = 0, void *parm = 0)
415  {
416  access(item, parm);
417  }
418 
419  /// Release the currently accessed cache item, if any.
421  {
422  release();
423  }
424 
425  /// Returns @c true if no item is being accessed.
426  bool empty() const { return myItem == 0; }
427 
428  /// Returns the current item being accessed
429  T *item() const { return myItem; }
430 
431  /// Indirection operator for the current item being accessed. It is the
432  /// caller's responsibility to ensure that the item is valid, e.g. by
433  /// calling @c empty on it first.
434  T *operator->() const { return myItem; }
435 
436  /// Reset the currently accessed cached item to a new item. If the item
437  /// given is the same as the one currently being accessed, this call is a
438  /// no-op, even if a new @c param value is given. Reset the item to @c
439  /// nullptr and back to the wanted item if a change in @c parm value is
440  /// required.
441  void reset(T *item, void *parm = 0)
442  {
443  if (myItem != item)
444  {
445  release();
446  access(item, parm);
447  }
448  }
449 
450 private:
451  void access(T *item, void *parm)
452  {
453  myItem = item;
454  if (myItem)
455  UT_UnifiedCache::get().access(item, parm);
456  }
457  void release()
458  {
459  if (myItem)
460  {
461  UT_UnifiedCache::get().release(myItem);
462  myItem = 0;
463  }
464  }
465 
466  T *myItem;
467 };
468 
469 #endif
void reset(T *item, void *parm=0)
T * item() const
Returns the current item being accessed.
static void setMaxMemory(int size_mb)
Set the amount of memory to be used by the cache, in MB.
fpreal64 lap() const
int64 getMemoryUsage() const
void setCheckMemoryLimit(bool check)
void access(UT_CacheItem *item, void *parms=0)
#define SYSloadFence()
#define UT_API
Definition: UT_API.h:13
void setMaxMemoryBytes(int64 size_bytes, bool prune=false)
unsafe_traverser unsafe_begin() const
~UT_UnifiedCacheAccessor()
Release the currently accessed cache item, if any.
long long int64
Definition: SYS_Types.h:107
unsigned long long uint64
Definition: SYS_Types.h:108
void release(UT_CacheItem *item)
void releaseAndDeallocate(UT_CacheItem *item)
GLuint GLint GLboolean GLint GLenum access
Definition: glcorearb.h:2221
void setUserData(void *data)
bool getCheckMemoryLimit() const
#define SYSstoreFence()
void pruneItems(int64 memory_limit)
static bool isMaxMemorySet()
Check whether the memory limit has been set.
int operator!=(const unsafe_traverser &cmp) const
GLboolean * data
Definition: glcorearb.h:130
GLuint const GLchar * name
Definition: glcorearb.h:785
int64 entries() const
int cmp(T a, T b)
Definition: ImathFun.h:119
unsafe_traverser unsafe_end() const
int operator==(const unsafe_traverser &cmp) const
const unsafe_traverser & operator=(const unsafe_traverser &src)
unsafe_traverser(const unsafe_traverser &src)
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:126
#define SYSmemoryFence()
Scoped accessor object for accessing unified cache items.
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:361
static UT_ThreadSafeCache< UT_Lock > & get()
static int64 getMemoryUsage()
void dumpStats(const char *name) const
int64 getMaxMemoryBytes() const
void setMaxMemory(int64 size_mb, bool prune=false)
UT_UnifiedCacheAccessor(T *item=0, void *parm=0)
GLenum src
Definition: glcorearb.h:1792
bool empty() const
Returns true if no item is being accessed.
void freeItem(UT_CacheItem *item)