Pyrogenesis  trunk
allocator_policies.h
Go to the documentation of this file.
1 /* Copyright (C) 2020 Wildfire Games.
2  *
3  * Permission is hereby granted, free of charge, to any person obtaining
4  * a copy of this software and associated documentation files (the
5  * "Software"), to deal in the Software without restriction, including
6  * without limitation the rights to use, copy, modify, merge, publish,
7  * distribute, sublicense, and/or sell copies of the Software, and to
8  * permit persons to whom the Software is furnished to do so, subject to
9  * the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included
12  * in all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21  */
22 
23 /*
24  * policy class templates for allocators.
25  */
26 
27 #ifndef ALLOCATOR_POLICIES
28 #define ALLOCATOR_POLICIES
29 
30 #include "lib/alignment.h" // pageSize
33 
34 #include <cstring>
35 
36 namespace Allocators {
37 
38 
39 //-----------------------------------------------------------------------------
40 // Growth
41 
42 // O(N) allocations, O(1) wasted space.
43 template<size_t increment = g_PageSize>
45 {
46  size_t operator()(size_t oldSize) const
47  {
48  return oldSize + increment;
49  }
50 };
51 
52 // O(log r) allocations, O(N) wasted space. NB: the common choice of
53 // expansion factor r = 2 (e.g. in the GCC STL) prevents
54 // Storage_Reallocate from reusing previous memory blocks,
55 // thus constantly growing the heap and decreasing locality.
56 // Alexandrescu [C++ and Beyond 2010] recommends r < 33/25.
57 // we approximate this with a power of two divisor to allow shifting.
58 // C++ does allow reference-to-float template parameters, but
59 // integer arithmetic is expected to be faster.
60 // (Storage_Commit should use 2:1 because it is cheaper to
61 // compute and retains power-of-two sizes.)
62 template<size_t multiplier = 21, size_t divisor = 16>
64 {
65  size_t operator()(size_t oldSize) const
66  {
67  const size_t product = oldSize * multiplier;
68 
69  // detect overflow, but allow equality in case oldSize = 0,
70  // which isn't a problem because Storage_Commit::Expand
71  // raises it to requiredCapacity.
72  ASSERT(product >= oldSize);
73 
74  return product / divisor;
75  }
76 };
77 
78 
79 //-----------------------------------------------------------------------------
80 // Storage
81 
82 // a contiguous region of memory (not just an "array", because
83 // allocators such as Arena append variable-sized intervals).
84 //
85 // we don't store smart pointers because storage usually doesn't need
86 // to be copied, and ICC 11 sometimes wasn't able to inline Address().
87 struct Storage
88 {
89  // @return starting address (alignment depends on the allocator).
90  uintptr_t Address() const;
91 
92  // @return size [bytes] of currently accessible memory.
93  size_t Capacity() const;
94 
95  // @return largest possible capacity [bytes].
96  size_t MaxCapacity() const;
97 
98  // expand Capacity() to at least requiredCapacity (possibly more
99  // depending on GrowthPolicy).
100  // @param requiredCapacity > Capacity()
101  // @return false and leave Capacity() unchanged if expansion failed,
102  // which is guaranteed to happen if requiredCapacity > MaxCapacity().
103  bool Expand(size_t requiredCapacity);
104 };
105 
106 
107 // allocate once and refuse subsequent expansion.
108 template<class Allocator = Allocator_Aligned<> >
110 {
112 public:
113  Storage_Fixed(size_t size)
114  : maxCapacity(size)
115  , storage(allocator.allocate(maxCapacity))
116  {
117  }
118 
120  {
121  allocator.deallocate(storage, maxCapacity);
122  }
123 
124  uintptr_t Address() const
125  {
126  return uintptr_t(storage);
127  }
128 
129  size_t Capacity() const
130  {
131  return maxCapacity;
132  }
133 
134  size_t MaxCapacity() const
135  {
136  return maxCapacity;
137  }
138 
139  bool Expand(size_t UNUSED(requiredCapacity))
140  {
141  return false;
142  }
143 
144 private:
145  Allocator allocator;
146  size_t maxCapacity; // must be initialized before storage
147  void* storage;
148 };
149 
150 
151 // unlimited expansion by allocating larger storage and copying.
152 // (basically equivalent to std::vector, although Growth_Exponential
153 // is much more cache and allocator-friendly than the GCC STL)
154 template<class Allocator = Allocator_Heap, class GrowthPolicy = Growth_Exponential<> >
156 {
158 public:
159  Storage_Reallocate(size_t initialCapacity)
160  : capacity(initialCapacity)
161  , storage(allocator.allocate(initialCapacity))
162  {
163  }
164 
166  {
167  allocator.deallocate(storage, capacity);
168  }
169 
170  uintptr_t Address() const
171  {
172  return uintptr_t(storage);
173  }
174 
175  size_t Capacity() const
176  {
177  return capacity;
178  }
179 
180  size_t MaxCapacity() const
181  {
182  return std::numeric_limits<size_t>::max();
183  }
184 
185  bool Expand(size_t requiredCapacity)
186  {
187  size_t newCapacity = std::max(requiredCapacity, GrowthPolicy()(capacity));
188  void* newStorage = allocator.allocate(newCapacity);
189  if(!newStorage)
190  return false;
191  memcpy(newStorage, storage, capacity);
192  std::swap(capacity, newCapacity);
193  std::swap(storage, newStorage);
194  allocator.deallocate(newStorage, newCapacity); // free PREVIOUS storage
195  return true;
196  }
197 
198 private:
199  Allocator allocator;
200  size_t capacity; // must be initialized before storage
201  void* storage;
202 };
203 
204 
205 // expand up to the limit of the allocated address space by
206 // committing physical memory. this avoids copying and
207 // reduces wasted physical memory.
208 template<class Allocator = Allocator_AddressSpace<>, class GrowthPolicy = Growth_Exponential<2,1> >
210 {
212 public:
213  Storage_Commit(size_t maxCapacity_)
214  : maxCapacity(Align<g_PageSize>(maxCapacity_)) // see Expand
215  , storage(allocator.allocate(maxCapacity))
216  , capacity(0)
217  {
218  }
219 
221  {
222  allocator.deallocate(storage, maxCapacity);
223  }
224 
225  uintptr_t Address() const
226  {
227  return uintptr_t(storage);
228  }
229 
230  size_t Capacity() const
231  {
232  return capacity;
233  }
234 
235  size_t MaxCapacity() const
236  {
237  return maxCapacity;
238  }
239 
240  bool Expand(size_t requiredCapacity)
241  {
242  size_t newCapacity = std::max(requiredCapacity, GrowthPolicy()(capacity));
243  // reduce the number of expensive commits by accurately
244  // reflecting the actual capacity. this is safe because
245  // we also round up maxCapacity.
246  newCapacity = Align<g_PageSize>(newCapacity);
247  if(newCapacity > maxCapacity)
248  return false;
249  if(!vm::Commit(Address()+capacity, newCapacity-capacity))
250  return false;
251  capacity = newCapacity;
252  return true;
253  }
254 
255 private:
256  Allocator allocator;
257  size_t maxCapacity; // must be initialized before storage
258  void* storage;
259  size_t capacity;
260 };
261 
262 
263 // implicitly expand up to the limit of the allocated address space by
264 // committing physical memory when a page is first accessed.
265 // this is basically equivalent to Storage_Commit with Growth_Linear,
266 // except that there is no need to call Expand.
267 template<class Allocator = Allocator_AddressSpace<> >
269 {
271 public:
272  Storage_AutoCommit(size_t maxCapacity_)
273  : maxCapacity(Align<g_PageSize>(maxCapacity_)) // match user's expectation
274  , storage(allocator.allocate(maxCapacity))
275  {
277  }
278 
280  {
282  allocator.deallocate(storage, maxCapacity);
283  }
284 
285  uintptr_t Address() const
286  {
287  return uintptr_t(storage);
288  }
289 
290  size_t Capacity() const
291  {
292  return maxCapacity;
293  }
294 
295  size_t MaxCapacity() const
296  {
297  return maxCapacity;
298  }
299 
300  bool Expand(size_t UNUSED(requiredCapacity))
301  {
302  return false;
303  }
304 
305 private:
306  Allocator allocator;
307  size_t maxCapacity; // must be initialized before storage
308  void* storage;
309 };
310 
311 
312 // reserve and return a pointer to space at the end of storage,
313 // expanding it if need be.
314 // @param end total number of previously reserved bytes; will be
315 // increased by size if the allocation succeeds.
316 // @param size [bytes] to reserve.
317 // @return address of allocated space, or 0 if storage is full
318 // and cannot expand any further.
319 template<class Storage>
320 static inline uintptr_t StorageAppend(Storage& storage, size_t& end, size_t size)
321 {
322  size_t newEnd = end + size;
323  if(newEnd > storage.Capacity())
324  {
325  if(!storage.Expand(newEnd)) // NB: may change storage.Address()
326  return 0;
327  }
328 
329  std::swap(end, newEnd);
330  return storage.Address() + newEnd;
331 }
332 
333 
334 // invoke operator() on default-constructed instantiations of
335 // Functor for reasonable combinations of Storage and their parameters.
336 template<template<class Storage> class Functor>
337 static void ForEachStorage()
338 {
339  Functor<Storage_Fixed<Allocator_Heap> >()();
340  Functor<Storage_Fixed<Allocator_Aligned<> > >()();
341 
342  Functor<Storage_Reallocate<Allocator_Heap, Growth_Linear<> > >()();
343  Functor<Storage_Reallocate<Allocator_Heap, Growth_Exponential<> > >()();
344  Functor<Storage_Reallocate<Allocator_Aligned<>, Growth_Linear<> > >()();
345  Functor<Storage_Reallocate<Allocator_Aligned<>, Growth_Exponential<> > >()();
346 
347  Functor<Storage_Commit<Allocator_AddressSpace<>, Growth_Linear<> > >()();
348  Functor<Storage_Commit<Allocator_AddressSpace<>, Growth_Exponential<> > >()();
349 
350  Functor<Storage_AutoCommit<> >()();
351 }
352 
353 } // namespace Allocators
354 
355 #endif // #ifndef ALLOCATOR_POLICIES
#define NONCOPYABLE(className)
Indicates that a class is noncopyable (usually due to const or reference members, or because the clas...
Definition: code_annotation.h:227
void EndOnDemandCommits()
decrements the reference count begun by BeginOnDemandCommit and removes the page fault handler when i...
Definition: uvm.cpp:125
size_t operator()(size_t oldSize) const
Definition: allocator_policies.h:46
size_t Capacity() const
Definition: allocator_policies.h:290
Storage_AutoCommit(size_t maxCapacity_)
Definition: allocator_policies.h:272
uintptr_t Address() const
Definition: allocator_policies.h:285
#define UNUSED(param)
mark a function parameter as unused and avoid the corresponding compiler warning. ...
Definition: code_annotation.h:38
size_t Capacity() const
size_t MaxCapacity() const
Definition: allocator_policies.h:180
~Storage_Fixed()
Definition: allocator_policies.h:119
size_t Align(size_t n)
Definition: alignment.h:36
Definition: allocator_policies.h:63
size_t Capacity() const
Definition: allocator_policies.h:230
~Storage_Reallocate()
Definition: allocator_policies.h:165
static const size_t g_PageSize
Definition: alignment.h:91
#define ASSERT(expr)
same as ENSURE in debug mode, does nothing in release mode.
Definition: debug.h:318
Definition: allocator_policies.h:268
bool Expand(size_t requiredCapacity)
Definition: allocator_policies.h:44
bool Commit(uintptr_t address, size_t size, PageType pageType, int prot)
map physical memory to previously reserved address space.
Definition: uvm.cpp:59
static uintptr_t StorageAppend(Storage &storage, size_t &end, size_t size)
Definition: allocator_policies.h:320
size_t MaxCapacity() const
Definition: allocator_policies.h:235
uintptr_t Address() const
Definition: allocator_policies.h:124
Storage_Commit(size_t maxCapacity_)
Definition: allocator_policies.h:213
~Storage_Commit()
Definition: allocator_policies.h:220
static void ForEachStorage()
Definition: allocator_policies.h:337
Storage_Reallocate(size_t initialCapacity)
Definition: allocator_policies.h:159
size_t capacity
Definition: allocator_policies.h:259
uintptr_t Address() const
Definition: allocator_policies.h:170
size_t maxCapacity
Definition: allocator_policies.h:307
Definition: allocator_policies.h:209
uintptr_t Address() const
void * storage
Definition: allocator_policies.h:147
~Storage_AutoCommit()
Definition: allocator_policies.h:279
size_t Capacity() const
Definition: allocator_policies.h:129
uintptr_t Address() const
Definition: allocator_policies.h:225
size_t MaxCapacity() const
Definition: allocator_policies.h:134
size_t MaxCapacity() const
Definition: allocator_policies.h:295
void BeginOnDemandCommits()
install a handler that attempts to commit memory whenever a read/write page fault is encountered...
Definition: uvm.cpp:120
Allocator allocator
Definition: allocator_policies.h:306
Definition: allocator_policies.h:155
Definition: allocator_policies.h:36
Allocator allocator
Definition: allocator_policies.h:145
Storage_Fixed(size_t size)
Definition: allocator_policies.h:113
bool Expand(size_t requiredCapacity)
Definition: allocator_policies.h:139
size_t maxCapacity
Definition: allocator_policies.h:146
Allocator allocator
Definition: allocator_policies.h:256
size_t operator()(size_t oldSize) const
Definition: allocator_policies.h:65
bool Expand(size_t requiredCapacity)
Definition: allocator_policies.h:300
void * storage
Definition: allocator_policies.h:308
void * storage
Definition: allocator_policies.h:201
bool Expand(size_t requiredCapacity)
Definition: allocator_policies.h:240
Definition: allocator_policies.h:87
Allocator allocator
Definition: allocator_policies.h:199
bool Expand(size_t requiredCapacity)
Definition: allocator_policies.h:185
#define swap(a, i, j)
size_t maxCapacity
Definition: allocator_policies.h:257
void * storage
Definition: allocator_policies.h:258
size_t capacity
Definition: allocator_policies.h:200
Definition: allocator_policies.h:109
size_t Capacity() const
Definition: allocator_policies.h:175