1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#pragma once
4
5#include <stack>
6#include <assert.h>
7
8#include "Prerequisites/BsTypes.h"
9#include "Prerequisites/BsStdHeaders.h"
10
11#include "Threading/BsThreading.h"
12
13namespace bs
14{
15 /** @addtogroup Internal-Utility
16 * @{
17 */
18
19 /** @addtogroup Memory-Internal
20 * @{
21 */
22
23 /**
24 * Describes a memory stack of a certain block capacity. See MemStack for more information.
25 *
26 * @tparam BlockCapacity Minimum size of a block. Larger blocks mean less memory allocations, but also potentially
27 * more wasted memory. If an allocation requests more bytes than BlockCapacity, first largest
28 * multiple is used instead.
29 */
30 template <int BlockCapacity = 1024 * 1024>
31 class MemStackInternal
32 {
33 private:
34 /**
35 * A single block of memory of BlockCapacity size. A pointer to the first free address is stored, and a remaining
36 * size.
37 */
38 class MemBlock
39 {
40 public:
41 MemBlock(UINT32 size) :mSize(size) { }
42
43 ~MemBlock() = default;
44
45 /**
46 * Returns the first free address and increments the free pointer. Caller needs to ensure the remaining block
47 * size is adequate before calling.
48 */
49 UINT8* alloc(UINT32 amount)
50 {
51 UINT8* freePtr = &mData[mFreePtr];
52 mFreePtr += amount;
53
54 return freePtr;
55 }
56
57 /**
58 * Deallocates the provided pointer. Deallocation must happen in opposite order from allocation otherwise
59 * corruption will occur.
60 *
61 * @note Pointer to @p data isn't actually needed, but is provided for debug purposes in order to more
62 * easily track out-of-order deallocations.
63 */
64 void dealloc(UINT8* data, UINT32 amount)
65 {
66 mFreePtr -= amount;
67 assert((&mData[mFreePtr]) == data && "Out of order stack deallocation detected. Deallocations need to happen in order opposite of allocations.");
68 }
69
70 UINT8* mData = nullptr;
71 UINT32 mFreePtr = 0;
72 UINT32 mSize = 0;
73 MemBlock* mNextBlock = nullptr;
74 MemBlock* mPrevBlock = nullptr;
75 };
76
77 public:
78 MemStackInternal()
79 {
80 mFreeBlock = allocBlock(BlockCapacity);
81 }
82
83 ~MemStackInternal()
84 {
85 assert(mFreeBlock->mFreePtr == 0 && "Not all blocks were released before shutting down the stack allocator.");
86
87 MemBlock* curBlock = mFreeBlock;
88 while (curBlock != nullptr)
89 {
90 MemBlock* nextBlock = curBlock->mNextBlock;
91 deallocBlock(curBlock);
92
93 curBlock = nextBlock;
94 }
95 }
96
97 /**
98 * Allocates the given amount of memory on the stack.
99 *
100 * @param[in] amount The amount to allocate in bytes.
101 *
102 * @note
103 * Allocates the memory in the currently active block if it is large enough, otherwise a new block is allocated.
104 * If the allocation is larger than default block size a separate block will be allocated only for that allocation,
105 * making it essentially a slower heap allocator.
106 * @note
107 * Each allocation comes with a 4 byte overhead.
108 */
109 UINT8* alloc(UINT32 amount)
110 {
111 amount += sizeof(UINT32);
112
113 UINT32 freeMem = mFreeBlock->mSize - mFreeBlock->mFreePtr;
114 if(amount > freeMem)
115 allocBlock(amount);
116
117 UINT8* data = mFreeBlock->alloc(amount);
118
119 UINT32* storedSize = reinterpret_cast<UINT32*>(data);
120 *storedSize = amount;
121
122 return data + sizeof(UINT32);
123 }
124
125 /** Deallocates the given memory. Data must be deallocated in opposite order then when it was allocated. */
126 void dealloc(UINT8* data)
127 {
128 data -= sizeof(UINT32);
129
130 UINT32* storedSize = reinterpret_cast<UINT32*>(data);
131 mFreeBlock->dealloc(data, *storedSize);
132
133 if (mFreeBlock->mFreePtr == 0)
134 {
135 MemBlock* emptyBlock = mFreeBlock;
136
137 if (emptyBlock->mPrevBlock != nullptr)
138 mFreeBlock = emptyBlock->mPrevBlock;
139
140 // Merge with next block
141 if (emptyBlock->mNextBlock != nullptr)
142 {
143 UINT32 totalSize = emptyBlock->mSize + emptyBlock->mNextBlock->mSize;
144
145 if (emptyBlock->mPrevBlock != nullptr)
146 emptyBlock->mPrevBlock->mNextBlock = nullptr;
147 else
148 mFreeBlock = nullptr;
149
150 deallocBlock(emptyBlock->mNextBlock);
151 deallocBlock(emptyBlock);
152
153 allocBlock(totalSize);
154 }
155 }
156 }
157
158 private:
159 MemBlock* mFreeBlock = nullptr;
160
161 /**
162 * Allocates a new block of memory using a heap allocator. Block will never be smaller than BlockCapacity no matter
163 * the @p wantedSize.
164 */
165 MemBlock* allocBlock(UINT32 wantedSize)
166 {
167 UINT32 blockSize = BlockCapacity;
168 if(wantedSize > blockSize)
169 blockSize = wantedSize;
170
171 MemBlock* newBlock = nullptr;
172 MemBlock* curBlock = mFreeBlock;
173
174 while (curBlock != nullptr)
175 {
176 MemBlock* nextBlock = curBlock->mNextBlock;
177 if (nextBlock != nullptr && nextBlock->mSize >= blockSize)
178 {
179 newBlock = nextBlock;
180 break;
181 }
182
183 curBlock = nextBlock;
184 }
185
186 if (newBlock == nullptr)
187 {
188 UINT8* data = (UINT8*)reinterpret_cast<UINT8*>(bs_alloc(blockSize + sizeof(MemBlock)));
189 newBlock = new (data)MemBlock(blockSize);
190 data += sizeof(MemBlock);
191
192 newBlock->mData = data;
193 newBlock->mPrevBlock = mFreeBlock;
194
195 if (mFreeBlock != nullptr)
196 {
197 if(mFreeBlock->mNextBlock != nullptr)
198 mFreeBlock->mNextBlock->mPrevBlock = newBlock;
199
200 newBlock->mNextBlock = mFreeBlock->mNextBlock;
201 mFreeBlock->mNextBlock = newBlock;
202 }
203 }
204
205 mFreeBlock = newBlock;
206 return newBlock;
207 }
208
209 /** Deallocates a block of memory. */
210 void deallocBlock(MemBlock* block)
211 {
212 block->~MemBlock();
213 bs_free(block);
214 }
215 };
216
217 /**
218 * One of the fastest, but also very limiting type of allocator. All deallocations must happen in opposite order from
219 * allocations.
220 *
221 * @note
222 * It's mostly useful when you need to allocate something temporarily on the heap, usually something that gets
223 * allocated and freed within the same method.
224 * @note
225 * Each allocation comes with a pretty hefty 4 byte memory overhead, so don't use it for small allocations.
226 * @note
227 * Thread safe. But you cannot allocate on one thread and deallocate on another. Threads will keep
228 * separate stacks internally. Make sure to call beginThread()/endThread() for any thread this stack is used on.
229 */
230 class MemStack
231 {
232 public:
233 /**
234 * Sets up the stack with the currently active thread. You need to call this on any thread before doing any
235 * allocations or deallocations.
236 */
237 static BS_UTILITY_EXPORT void beginThread();
238
239 /**
240 * Cleans up the stack for the current thread. You may not perform any allocations or deallocations after this is
241 * called, unless you call beginThread again.
242 */
243 static BS_UTILITY_EXPORT void endThread();
244
245 /** @copydoc MemStackInternal::alloc() */
246 static BS_UTILITY_EXPORT UINT8* alloc(UINT32 amount);
247
248 /** @copydoc MemStackInternal::dealloc() */
249 static BS_UTILITY_EXPORT void deallocLast(UINT8* data);
250
251 private:
252 static BS_THREADLOCAL MemStackInternal<1024 * 1024>* ThreadMemStack;
253 };
254
255 /** @} */
256 /** @} */
257
258 /** @addtogroup Memory
259 * @{
260 */
261
262 /** @copydoc MemStackInternal::alloc() */
263 inline void* bs_stack_alloc(UINT32 amount)
264 {
265 return (void*)MemStack::alloc(amount);
266 }
267
268 /**
269 * Allocates enough memory to hold the specified type, on the stack, but does not initialize the object.
270 *
271 * @see MemStackInternal::alloc()
272 */
273 template<class T>
274 T* bs_stack_alloc()
275 {
276 return (T*)MemStack::alloc(sizeof(T));
277 }
278
279 /**
280 * Allocates enough memory to hold N objects of the specified type, on the stack, but does not initialize the objects.
281 *
282 * @param[in] amount Number of entries of the requested type to allocate.
283 *
284 * @see MemStackInternal::alloc()
285 */
286 template<class T>
287 T* bs_stack_alloc(UINT32 amount)
288 {
289 return (T*)MemStack::alloc(sizeof(T) * amount);
290 }
291
292 /**
293 * Allocates enough memory to hold the specified type, on the stack, and constructs the object.
294 *
295 * @see MemStackInternal::alloc()
296 */
297 template<class T>
298 T* bs_stack_new(UINT32 count = 0)
299 {
300 T* data = bs_stack_alloc<T>(count);
301
302 for(unsigned int i = 0; i < count; i++)
303 new ((void*)&data[i]) T;
304
305 return data;
306 }
307
308 /**
309 * Allocates enough memory to hold the specified type, on the stack, and constructs the object.
310 *
311 * @see MemStackInternal::alloc()
312 */
313 template<class T, class... Args>
314 T* bs_stack_new(Args &&...args, UINT32 count = 0)
315 {
316 T* data = bs_stack_alloc<T>(count);
317
318 for(unsigned int i = 0; i < count; i++)
319 new ((void*)&data[i]) T(std::forward<Args>(args)...);
320
321 return data;
322 }
323
324 /**
325 * Destructs and deallocates last allocated entry currently located on stack.
326 *
327 * @see MemStackInternal::dealloc()
328 */
329 template<class T>
330 void bs_stack_delete(T* data)
331 {
332 data->~T();
333
334 MemStack::deallocLast((UINT8*)data);
335 }
336
337 /**
338 * Destructs an array of objects and deallocates last allocated entry currently located on stack.
339 *
340 * @see MemStackInternal::dealloc()
341 */
342 template<class T>
343 void bs_stack_delete(T* data, UINT32 count)
344 {
345 for(unsigned int i = 0; i < count; i++)
346 data[i].~T();
347
348 MemStack::deallocLast((UINT8*)data);
349 }
350
351 inline void bs_stack_delete(void* data, UINT32 count)
352 {
353 MemStack::deallocLast((UINT8*)data);
354 }
355
356 /** @copydoc MemStackInternal::dealloc() */
357 inline void bs_stack_free(void* data)
358 {
359 return MemStack::deallocLast((UINT8*)data);
360 }
361
362 /**
363 * An object used to transparently clean up a stack allocation when it's no longer in scope. Make sure to take great
364 * care not to free non-managed stack allocations out of order or to free the stack allocation managed by this object!
365 */
366 template<typename T>
367 struct StackMemory
368 {
369 /*
370 * Provide implicit conversion to the allocated buffer so that users of this code can "pretend" this object is a
371 * pointer to the stack buffer that they wanted.
372 */
373 constexpr operator T*() const & noexcept
374 {
375 return mPtr;
376 }
377
378 /*
379 * This ensures that the result of bs_managed_stack_alloc() doesn't get passed to a function call as a temporary,
380 * or immediately assigned as a T*. Instead, the user of this class is forced to deal with this class as itself,
381 * when handling the return value of bs_managed_stack_alloc() preventing an immediate (and erroneous) call to
382 * bs_stack_free().
383 */
384 constexpr operator T*() const && noexcept = delete;
385
386 explicit constexpr StackMemory(T* p, size_t count = 1)
387 : mPtr(p), mCount(count)
388 { }
389
390 /** Needed until c++17 */
391 StackMemory(StackMemory && other)
392 : mPtr(std::exchange(other.mPtr, nullptr))
393 , mCount(std::exchange(other.mCount, 0))
394 { }
395
396 StackMemory(StackMemory const&) = delete;
397 StackMemory& operator=(StackMemory &&) = delete;
398 StackMemory& operator=(StackMemory const&) = delete;
399
400 /** Frees the stack allocation. */
401 ~StackMemory()
402 {
403 if(mPtr != nullptr)
404 {
405 if(mCount >= 1)
406 bs_stack_delete(mPtr, (UINT32)mCount);
407 else
408 bs_stack_free(mPtr);
409 }
410 }
411
412 private:
413 T* mPtr = nullptr;
414 size_t mCount = 0;
415 };
416
417 /**
418 * Same as bs_stack_alloc() except the returned object takes care of automatically cleaning up when it goes out of
419 * scope.
420 */
421 inline StackMemory<void> bs_managed_stack_alloc(UINT32 amount)
422 {
423 return StackMemory<void>(bs_stack_alloc(amount));
424 }
425
426 /**
427 * Same as bs_stack_alloc() except the returned object takes care of automatically cleaning up when it goes out of
428 * scope.
429 */
430 template<class T>
431 StackMemory<T> bs_managed_stack_alloc()
432 {
433 return StackMemory<T>(bs_stack_alloc<T>());
434 }
435
436 /**
437 * Same as bs_stack_alloc() except the returned object takes care of automatically cleaning up when it goes out of
438 * scope.
439 */
440 template<class T>
441 StackMemory<T> bs_managed_stack_alloc(UINT32 amount)
442 {
443 return StackMemory<T>(bs_stack_alloc<T>(amount));
444 }
445
446 /**
447 * Same as bs_stack_new() except the returned object takes care of automatically cleaning up when it goes out of
448 * scope.
449 */
450 template<class T>
451 StackMemory<T> bs_managed_stack_new(size_t count = 1)
452 {
453 return StackMemory<T>(bs_stack_new<T>(count), count);
454 }
455
456 /**
457 * Same as bs_stack_new() except the returned object takes care of automatically cleaning up when it goes out of
458 * scope.
459 */
460 template<class T, class... Args>
461 StackMemory<T> bs_managed_stack_new(Args && ... args, size_t count = 1)
462 {
463 return StackMemory<T>(bs_stack_new<T>(std::forward<Args>(args)..., count), count);
464 }
465
466 /** @} */
467 /** @addtogroup Internal-Utility
468 * @{
469 */
470
471 /** @addtogroup Memory-Internal
472 * @{
473 */
474
475 /**
476 * Allows use of a stack allocator by using normal new/delete/free/dealloc operators.
477 *
478 * @see MemStack
479 */
480 class StackAlloc
481 { };
482
483 /**
484 * Specialized memory allocator implementations that allows use of a stack allocator in normal new/delete/free/dealloc
485 * operators.
486 *
487 * @see MemStack
488 */
489 template<>
490 class MemoryAllocator<StackAlloc> : public MemoryAllocatorBase
491 {
492 public:
493 static void* allocate(size_t bytes)
494 {
495 return bs_stack_alloc((UINT32)bytes);
496 }
497
498 static void free(void* ptr)
499 {
500 bs_stack_free(ptr);
501 }
502 };
503
504 /** @} */
505 /** @} */
506}
507