HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
pool.h
Go to the documentation of this file.
1 //
2 // Copyright 2019 Pixar
3 //
4 // Licensed under the terms set forth in the LICENSE.txt file available at
5 // https://openusd.org/license.
6 //
7 #ifndef PXR_USD_SDF_POOL_H
8 #define PXR_USD_SDF_POOL_H
9 
10 #include "pxr/pxr.h"
11 #include "pxr/usd/sdf/api.h"
12 
13 #include "pxr/base/arch/demangle.h"
14 #include "pxr/base/arch/hints.h"
15 #include "pxr/base/arch/pragmas.h"
16 #include "pxr/base/tf/diagnostic.h"
17 #include "pxr/base/tf/staticData.h"
18 
19 #include <tbb/concurrent_queue.h>
20 
21 #include <atomic>
22 #include <thread>
23 
25 
26 // A helper struct for thread_local that uses nullptr initialization as a
27 // sentinel to prevent guard variable use from being invoked after first
28 // initialization.
29 template <class T>
31 {
32  static T &Get() {
33  static thread_local T *theTPtr = nullptr;
34  if (ARCH_LIKELY(theTPtr)) {
35  return *theTPtr;
36  }
37  static thread_local T theT;
38  T *p = &theT;
39  theTPtr = p;
40  return *p;
41  }
42 };
43 
44 // Fixed-size scalable pool allocator with 32-bit "handles" returned. Reserves
45 // virtual memory in big regions. It's optimized for per-thread allocations,
46 // and intended to be used for SdfPath. The Tag template argument just serves
47 // as to distinguish one pool instantiation from another with otherwise
48 // equivalent template arguments. The ElemSize argument is the size of an
49 // allocated element in bytes. It must be at least 4 bytes. The RegionBits
50 // argument determines how many contiguous "chunks" of virtual memory the pool
51 // will use. A good number for this is 8, meaning we'll have at most 256
52 // "regions" or "chunks" of contiguous virtual memory, each 2^24 times ElemSize
53 // bytes in size. To allocate from reserved chunks, each thread acquires a span
54 // to hold ElemsPerSpan elements from the range, then uses that to dole out
55 // individual allocations. When freed, allocations are placed on a thread-local
56 // free list, and eventually shared back for use by other threads when the free
57 // list gets large.
58 template <class Tag,
59  unsigned ElemSize,
60  unsigned RegionBits,
61  unsigned ElemsPerSpan=16384>
62 class Sdf_Pool
63 {
64  static_assert(ElemSize >= sizeof(uint32_t),
65  "ElemSize must be at least sizeof(uint32_t)");
66 
67 public:
68  // Number of pool elements per region.
69  static constexpr uint64_t ElemsPerRegion = 1ull << (32-RegionBits);
70 
71  // Maximum index of an element in a region.
72  static constexpr uint32_t MaxIndex = ElemsPerRegion - 1;
73 
74  // Mask to extract region number from a handle value.
75  static constexpr uint32_t RegionMask = ((1 << RegionBits)-1);
76 
77  friend struct Handle;
78  // A Handle refers to an item in the pool. It just wraps around a uint32_t
79  // that represents the item's index and the item's region.
80  struct Handle {
81  constexpr Handle() noexcept = default;
82  constexpr Handle(std::nullptr_t) noexcept : value(0) {}
83  Handle(unsigned region, uint32_t index)
84  : value((index << RegionBits) | region) {}
85  Handle &operator=(Handle const &) = default;
86  Handle &operator=(std::nullptr_t) { return *this = Handle(); }
87  inline char *GetPtr() const noexcept {
90  return Sdf_Pool::_GetPtr(value & RegionMask, value >> RegionBits);
92  }
93  static inline Handle GetHandle(char const *ptr) noexcept {
94  return Sdf_Pool::_GetHandle(ptr);
95  }
96  explicit operator bool() const {
97  return value != 0;
98  }
99  inline bool operator ==(Handle const &r) const noexcept {
100  return value == r.value;
101  }
102  inline bool operator !=(Handle const &r) const noexcept {
103  return value != r.value;
104  }
105  inline bool operator <(Handle const &r) const noexcept {
106  return value < r.value;
107  }
108  inline void swap(Handle &r) noexcept {
109  std::swap(value, r.value);
110  }
111  uint32_t value = 0;
112  };
113 
114 private:
115  // We maintain per-thread free lists of pool items.
116  struct _FreeList {
117  inline void Pop() {
118  char *p = head.GetPtr();
119  Handle *hp = reinterpret_cast<Handle *>(p);
120  head = *hp;
121  --size;
122  }
123  inline void Push(Handle h) {
124  ++size;
125  char *p = h.GetPtr();
126  Handle *hp = reinterpret_cast<Handle *>(p);
127  *hp = head;
128  head = h;
129  }
130  Handle head;
131  size_t size = 0;
132  };
133 
134  // A pool span represents a "chunk" of new pool space that threads allocate
135  // from when their free lists are empty. When both the free list and the
136  // pool span are exhausted, a thread will look for a shared free list, or
137  // will obtain a new chunk of pool space to use.
138  struct _PoolSpan {
139  size_t size() const { return endIndex - beginIndex; }
140  inline Handle Alloc() {
141  return Handle(region, beginIndex++);
142  }
143  inline bool empty() const {
144  return beginIndex == endIndex;
145  }
146  unsigned region;
147  uint32_t beginIndex;
148  uint32_t endIndex;
149  };
150 
151  struct _PerThreadData {
152  // Local free-list of elems returned to the pool.
153  _FreeList freeList;
154  // Contiguous range of reserved but as-yet-unalloc'd space.
155  _PoolSpan span;
156  };
157 
158  // The region state structure represents the global state of the pool. This
159  // is a pool-global structure that is used to reserve new spans of pool data
160  // by threads when needed. See the Reserve() member, and the _ReserveSpan()
161  // function that does most of the state manipulation.
162  struct _RegionState {
163  static constexpr uint32_t LockedState = ~0;
164 
165  _RegionState() = default;
166  constexpr _RegionState(unsigned region, uint32_t index)
167  : _state((index << RegionBits) | region) {}
168 
169  // Make a new state that reserves up to \p num elements. There must be
170  // space left remaining.
171  inline _RegionState Reserve(unsigned num) const;
172 
173  static constexpr _RegionState GetInitState() {
174  return _RegionState(0, 0);
175  }
176 
177  static constexpr _RegionState GetLockedState() {
178  return _RegionState(LockedState, LockedState);
179  }
180 
181  constexpr bool operator==(_RegionState other) const {
182  return _state == other._state;
183  }
184 
185  uint32_t GetIndex() const {
186  return _state >> RegionBits;
187  }
188 
189  unsigned GetRegion() const {
190  return _state & RegionMask;
191  }
192 
193  bool IsLocked() const {
194  return _state == LockedState;
195  }
196 
197  // low RegionBits bits are region id, rest are index.
198  uint32_t _state;
199  };
200 
201 public:
202  static inline Handle Allocate();
203  static inline void Free(Handle h);
204 
205 private:
206 
207  // Given a region id and index, form the pointer into the pool.
208  static inline char *_GetPtr(unsigned region, uint32_t index) {
209  // Suppress undefined-var-template warnings from clang; _regionStarts
210  // is expected to be instantiated in another translation unit via
211  // the SDF_INSTANTIATE_POOL macro.
214  return _regionStarts[region] + (index * ElemSize);
216  }
217 
218  // Given a pointer into the pool, produce its corresponding Handle. Don't
219  // do this unless you really have to, it has to do a bit of a search.
220  static inline Handle _GetHandle(char const *ptr) {
221  if (ptr) {
222  for (unsigned region = 1; region != NumRegions+1; ++region) {
223  // Suppress undefined-var-template warnings from clang; _regionStarts
224  // is expected to be instantiated in another translation unit via
225  // the SDF_INSTANTIATE_POOL macro.
228  uintptr_t start = (uintptr_t)_regionStarts[region];
230 
231  // We rely on modular arithmetic so that if ptr is less than
232  // start, the diff will be larger than ElemsPerRegion*ElemSize.
233  uintptr_t diff = (uintptr_t)ptr - start;
234  if (diff < (uintptr_t)(ElemsPerRegion*ElemSize)) {
235  return Handle(
236  region, static_cast<uint32_t>(diff / ElemSize));
237  }
238  }
239  }
240  return nullptr;
241  }
242 
243  // Try to take a shared free list.
244  static bool _TakeSharedFreeList(_FreeList &out) {
245  return _sharedFreeLists->try_pop(out);
246  }
247 
248  // Give a free list to be shared by other threads.
249  static void _ShareFreeList(_FreeList &in) {
250  _sharedFreeLists->push(in);
251  in = {};
252  }
253 
254  // Reserve a new span of pool space.
255  static inline void _ReserveSpan(_PoolSpan &out);
256 
257  static constexpr int NumRegions = 1 << RegionBits;
258 
259  using _ThreadData = Sdf_FastThreadLocalBase<_PerThreadData>;
260  SDF_API static _ThreadData _threadData;
261  SDF_API static char *_regionStarts[NumRegions+1];
262  SDF_API static std::atomic<_RegionState> _regionState;
264 };
265 
267 
268 #endif // PXR_USD_SDF_POOL_H
#define ARCH_LIKELY(x)
Definition: hints.h:29
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1699
uint128_t uintptr_t
Definition: format.h:479
GLuint start
Definition: glcorearb.h:475
GLsizei const GLfloat * value
Definition: glcorearb.h:824
constexpr Handle(std::nullptr_t) noexcept
Definition: pool.h:82
static Handle Allocate()
#define ARCH_PRAGMA_POP
Definition: pragmas.h:159
static constexpr uint32_t RegionMask
Definition: pool.h:75
OutGridT const XformOp bool bool
constexpr auto in(type t, int set) -> bool
Definition: core.h:611
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
bool operator!=(Handle const &r) const noexcept
Definition: pool.h:102
#define ARCH_PRAGMA_PUSH
Definition: pragmas.h:155
#define ARCH_PRAGMA_UNDEFINED_VAR_TEMPLATE
Definition: pragmas.h:251
#define SDF_API
Definition: api.h:23
GLsizeiptr size
Definition: glcorearb.h:664
GLfloat GLfloat GLfloat GLfloat h
Definition: glcorearb.h:2002
void swap(Handle &r) noexcept
Definition: pool.h:108
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1425
#define ARCH_PRAGMA_MAYBE_UNINITIALIZED
Definition: pragmas.h:175
char * GetPtr() const noexcept
Definition: pool.h:87
bool operator==(Handle const &r) const noexcept
Definition: pool.h:99
GLuint index
Definition: glcorearb.h:786
auto ptr(T p) -> const void *
Definition: format.h:4331
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:74
static T & Get()
Definition: pool.h:32
static Handle GetHandle(char const *ptr) noexcept
Definition: pool.h:93
bool operator<(Handle const &r) const noexcept
Definition: pool.h:105
GLboolean r
Definition: glcorearb.h:1222
constexpr Handle() noexcept=default
friend struct Handle
Definition: pool.h:77
Handle & operator=(std::nullptr_t)
Definition: pool.h:86
constexpr int GetIndex()
Definition: types.h:211
Handle & operator=(Handle const &)=default
Definition: pool.h:62
static constexpr uint64_t ElemsPerRegion
Definition: pool.h:69
static void Free(Handle h)
GLenum GLenum GLsizei void GLsizei void void * span
Definition: glad.h:5135
static constexpr uint32_t MaxIndex
Definition: pool.h:72
Handle(unsigned region, uint32_t index)
Definition: pool.h:83