This document is for a version of USD that is under development. See this page for the current release.
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
pool.h
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
14#include "pxr/base/arch/hints.h"
18
19#include <tbb/concurrent_queue.h>
20
21#include <atomic>
22#include <thread>
23
24PXR_NAMESPACE_OPEN_SCOPE
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.
29template <class T>
30struct Sdf_FastThreadLocalBase
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.
58template <class Tag,
59 unsigned ElemSize,
60 unsigned RegionBits,
61 unsigned ElemsPerSpan=16384>
62class Sdf_Pool
63{
64 static_assert(ElemSize >= sizeof(uint32_t),
65 "ElemSize must be at least sizeof(uint32_t)");
66
67public:
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 {
88 ARCH_PRAGMA_PUSH
89 ARCH_PRAGMA_MAYBE_UNINITIALIZED
90 return Sdf_Pool::_GetPtr(value & RegionMask, value >> RegionBits);
91 ARCH_PRAGMA_POP
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
114private:
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
201public:
202 static inline Handle Allocate();
203 static inline void Free(Handle h);
204
205private:
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.
212 ARCH_PRAGMA_PUSH
213 ARCH_PRAGMA_UNDEFINED_VAR_TEMPLATE
214 return _regionStarts[region] + (index * ElemSize);
215 ARCH_PRAGMA_POP
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.
226 ARCH_PRAGMA_PUSH
227 ARCH_PRAGMA_UNDEFINED_VAR_TEMPLATE
228 uintptr_t start = (uintptr_t)_regionStarts[region];
229 ARCH_PRAGMA_POP
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;
263 SDF_API static TfStaticData<tbb::concurrent_queue<_FreeList>> _sharedFreeLists;
264};
265
266PXR_NAMESPACE_CLOSE_SCOPE
267
268#endif // PXR_USD_SDF_POOL_H
Low-level utilities for informing users of various internal and external diagnostic conditions.
Create or return a previously created object instance of global data.
Definition: staticData.h:96
Demangle C++ typenames generated by the typeid() facility.
Compiler hints.
STL namespace.
Pragmas for controlling compiler-specific behaviors.