Line data Source code
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
31 : #include "lib/allocators/stateless_allocators.h"
32 : #include "lib/allocators/freelist.h"
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>
44 : struct Growth_Linear
45 : {
46 0 : size_t operator()(size_t oldSize) const
47 : {
48 0 : 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>
63 : struct Growth_Exponential
64 : {
65 0 : size_t operator()(size_t oldSize) const
66 : {
67 0 : 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 0 : ASSERT(product >= oldSize);
73 :
74 0 : 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<> >
109 : class Storage_Fixed
110 : {
111 : NONCOPYABLE(Storage_Fixed);
112 : public:
113 0 : Storage_Fixed(size_t size)
114 : : maxCapacity(size)
115 0 : , storage(allocator.allocate(maxCapacity))
116 : {
117 0 : }
118 :
119 0 : ~Storage_Fixed()
120 : {
121 0 : allocator.deallocate(storage, maxCapacity);
122 0 : }
123 :
124 0 : uintptr_t Address() const
125 : {
126 0 : return uintptr_t(storage);
127 : }
128 :
129 0 : size_t Capacity() const
130 : {
131 0 : return maxCapacity;
132 : }
133 :
134 0 : size_t MaxCapacity() const
135 : {
136 0 : return maxCapacity;
137 : }
138 :
139 0 : bool Expand(size_t UNUSED(requiredCapacity))
140 : {
141 0 : 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<> >
155 : class Storage_Reallocate
156 : {
157 : NONCOPYABLE(Storage_Reallocate);
158 : public:
159 0 : Storage_Reallocate(size_t initialCapacity)
160 : : capacity(initialCapacity)
161 0 : , storage(allocator.allocate(initialCapacity))
162 : {
163 0 : }
164 :
165 0 : ~Storage_Reallocate()
166 : {
167 0 : allocator.deallocate(storage, capacity);
168 0 : }
169 :
170 0 : uintptr_t Address() const
171 : {
172 0 : return uintptr_t(storage);
173 : }
174 :
175 0 : size_t Capacity() const
176 : {
177 0 : return capacity;
178 : }
179 :
180 0 : size_t MaxCapacity() const
181 : {
182 0 : return std::numeric_limits<size_t>::max();
183 : }
184 :
185 0 : bool Expand(size_t requiredCapacity)
186 : {
187 0 : size_t newCapacity = std::max(requiredCapacity, GrowthPolicy()(capacity));
188 0 : void* newStorage = allocator.allocate(newCapacity);
189 0 : if(!newStorage)
190 0 : return false;
191 0 : memcpy(newStorage, storage, capacity);
192 0 : std::swap(capacity, newCapacity);
193 0 : std::swap(storage, newStorage);
194 0 : allocator.deallocate(newStorage, newCapacity); // free PREVIOUS storage
195 0 : 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> >
209 : class Storage_Commit
210 : {
211 : NONCOPYABLE(Storage_Commit);
212 : public:
213 0 : Storage_Commit(size_t maxCapacity_)
214 0 : : maxCapacity(Align<g_PageSize>(maxCapacity_)) // see Expand
215 : , storage(allocator.allocate(maxCapacity))
216 0 : , capacity(0)
217 : {
218 0 : }
219 :
220 0 : ~Storage_Commit()
221 : {
222 0 : allocator.deallocate(storage, maxCapacity);
223 0 : }
224 :
225 0 : uintptr_t Address() const
226 : {
227 0 : return uintptr_t(storage);
228 : }
229 :
230 0 : size_t Capacity() const
231 : {
232 0 : return capacity;
233 : }
234 :
235 0 : size_t MaxCapacity() const
236 : {
237 0 : return maxCapacity;
238 : }
239 :
240 0 : bool Expand(size_t requiredCapacity)
241 : {
242 0 : 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 0 : newCapacity = Align<g_PageSize>(newCapacity);
247 0 : if(newCapacity > maxCapacity)
248 0 : return false;
249 0 : if(!vm::Commit(Address()+capacity, newCapacity-capacity))
250 0 : return false;
251 0 : capacity = newCapacity;
252 0 : 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<> >
268 : class Storage_AutoCommit
269 : {
270 : NONCOPYABLE(Storage_AutoCommit);
271 : public:
272 0 : Storage_AutoCommit(size_t maxCapacity_)
273 0 : : maxCapacity(Align<g_PageSize>(maxCapacity_)) // match user's expectation
274 0 : , storage(allocator.allocate(maxCapacity))
275 : {
276 0 : vm::BeginOnDemandCommits();
277 0 : }
278 :
279 0 : ~Storage_AutoCommit()
280 : {
281 0 : vm::EndOnDemandCommits();
282 0 : allocator.deallocate(storage, maxCapacity);
283 0 : }
284 :
285 0 : uintptr_t Address() const
286 : {
287 0 : return uintptr_t(storage);
288 : }
289 :
290 0 : size_t Capacity() const
291 : {
292 0 : return maxCapacity;
293 : }
294 :
295 0 : size_t MaxCapacity() const
296 : {
297 0 : return maxCapacity;
298 : }
299 :
300 0 : bool Expand(size_t UNUSED(requiredCapacity))
301 : {
302 0 : 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 0 : static inline uintptr_t StorageAppend(Storage& storage, size_t& end, size_t size)
321 : {
322 0 : size_t newEnd = end + size;
323 0 : if(newEnd > storage.Capacity())
324 : {
325 0 : if(!storage.Expand(newEnd)) // NB: may change storage.Address()
326 0 : return 0;
327 : }
328 :
329 0 : std::swap(end, newEnd);
330 0 : 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 0 : static void ForEachStorage()
338 : {
339 0 : Functor<Storage_Fixed<Allocator_Heap> >()();
340 0 : Functor<Storage_Fixed<Allocator_Aligned<> > >()();
341 :
342 0 : Functor<Storage_Reallocate<Allocator_Heap, Growth_Linear<> > >()();
343 0 : Functor<Storage_Reallocate<Allocator_Heap, Growth_Exponential<> > >()();
344 0 : Functor<Storage_Reallocate<Allocator_Aligned<>, Growth_Linear<> > >()();
345 0 : Functor<Storage_Reallocate<Allocator_Aligned<>, Growth_Exponential<> > >()();
346 :
347 0 : Functor<Storage_Commit<Allocator_AddressSpace<>, Growth_Linear<> > >()();
348 0 : Functor<Storage_Commit<Allocator_AddressSpace<>, Growth_Exponential<> > >()();
349 :
350 0 : Functor<Storage_AutoCommit<> >()();
351 0 : }
352 :
353 : } // namespace Allocators
354 :
355 : #endif // #ifndef ALLOCATOR_POLICIES
|
