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