1// tPool.h 
2// 
3// Memory management pools. These are significantly faster than standard memory allocators. All pool implementations 
4// found here must not call new or delete. The reason for this is to allow a user of the pool to overload operator new. 
5// We would get into an infinite loop if we called new from inside the pool implementation. 
6// 
7// Copyright (c) 2004-2006, 2017 Tristan Grimmer. 
8// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
9// granted, provided that the above copyright notice and this permission notice appear in all copies. 
10// 
11// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
12// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
13// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
14// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
15// PERFORMANCE OF THIS SOFTWARE. 
16 
17#pragma once 
18#include <thread> 
19#include <mutex> 
20#include "Foundation/tAssert.h" 
21#include "Foundation/tList.h" 
22#include "Foundation/tMemory.h" 
23namespace tMem 
24{ 
25 
26 
27// Define MEMORY_ALLOCATOR_CHECK for cursory sanity checking of pool pointers. 
28// Define MEMORY_ALLOCATOR_CHECK and MEMORY_ALLOCATOR__DEEP_CHECK for slower but more thorough sanity checking of pool pointers. 
29// #define MEMORY_ALLOCATOR_CHECK 
30// #define MEMORY_ALLOCATOR__DEEP_CHECK 
31 
32 
33// Abstract base class for all types of memory allocators. By having the Malloc and Free calls be virtual, a call to an 
34// operator new that passes in the memory pool to use can simply pass in a tAllocator pointer, allowing different types 
35// of memory pools without adding complexity to the implementation of new. The overloaded new can just call Malloc. The 
36// same reasoning holds for delete and free. 
37class tAllocator 
38{ 
39public: 
40 tAllocator() : Constructed(true), NumAllocations(0) { } 
41 virtual ~tAllocator() { Constructed = false; } 
42 virtual void* Malloc(int numBytes) = 0; 
43 virtual void Free(void*) = 0; 
44 int GetNumAllocations() const { return NumAllocations; } 
45 
46 // This variable is to keep track of whether the allocator object is initialized. If the allocator is static and 
47 // we are overriding operator new, we don't know when the allocator is constructed or destructed. This can cause the 
48 // allocator to be destructed before global objects that have been allocated from it get destructed. 
49 // 
50 // Static initialization guarantees Constructed is false. Any Malloc calls before construction will return nullptr 
51 // allowing us to fall back to std malloc. In the allocator destructor we can set Constructed to false but do not 
52 // free the allocator memory unless NumAllocations == 0. Any other allocator free calls can now check if Constructed 
53 // is false and free the allocator memory if NumAllocations is 0. 
54 // 
55 // The other option is to simply not use custom allocators before main at all. You could add initialize and shutdown 
56 // calls at the beginning and end of main. Even then, something like a static tString would initialize using 
57 // non-allocator memory, but could be reassigned during main (using allocator memory), so we'd still need to keep 
58 // the pool around after main for when the static destructor is called. In any case, if the allocator is used before 
59 // main by being statically constructed we need deallocations to work after the destructor may have been called. 
60 bool Constructed; 
61 int NumAllocations; 
62}; 
63 
64 
65// tFastPool gives you O(1) malloc and free at the expense of some wasted memory. tFastPool is a slot-based pool. It 
66// implements a block of slots, each slot big enough for a single item. Initially the free pointer points to the first 
67// slot, and the first 4 bytes of each slot point to the next slot. A malloc simply returns the free pointer and then 
68// points the free pointer to the next slot. If you run out of slots a new expansion block is created and initialized. 
69class tFastPool : public tAllocator 
70{ 
71public: 
72 tFastPool 
73 ( 
74 // This is the max item size in bytes. 
75 int slotSize, 
76 int initialSlotsInBlock = 256, 
77 
78 // If slotsPerExpansionBlock is zero, Malloc will fail (return 0) once all initial slots are used up. 
79 int slotsPerExpansionBlock = 128, 
80 
81 // Faster if you don't need threadsafeness. If pool is threadSafe, all pool function calls will be too. 
82 bool threadSafe = true 
83 ); 
84 ~tFastPool(); 
85 
86 // Allocates some memory. If numBytes is over slotSize it will return nullptr. If slotsPerExpansionBlock is set to 0 
87 // and all initial slots are used, it will return nullptr. This can be handy if you want to fall-back onto regular 
88 // memory allocation when dealing with variable sized objects like strings. Extraneous large mallocs can be dealt 
89 // with by a different strategy while you still get the speed benefit for all of the smaller mallocs. Calling 
90 // without an argument will return memory at least slotSize big. 
91 void* Malloc(int numBytes = 0) override; 
92 
93 // Deallocates the passed in memory. 
94 void Free(void*) override; 
95 
96 int GetSlotSize() const { return SlotSize; } 
97 int GetNumExpansionBlocks() const { return Blocks.GetNumItems() - 1; } 
98 int GetTotalPoolSize() const { return SlotSize * (GetNumExpansionBlocks()*SlotsPerExpansionBlock + SlotsInitialBlock); } 
99 
100private: 
101 void GrowPool(); 
102 
103 // Sanity checking functions. These are slow. 
104 #ifdef MEMORY_ALLOCATOR_CHECK 
105 void SanityCheckSlotValid(void* slot); 
106 void SanityCheckSlotFreeable(void* slot); 
107 #endif 
108 
109 struct SlotBlock : public tLink<SlotBlock> 
110 { 
111 void Init(int slotSizeInBytes, int numSlots); 
112 void Shutdown() { if (Slots) tFree(Slots); Slots = nullptr; } 
113 
114 int SlotSize; 
115 int NumSlots; 
116 uint8* Slots; 
117 }; 
118 
119 // A tList does not call new or delete and so we can use it without risking an infinite loop. 
120 tList<SlotBlock> Blocks; 
121 
122 // FreeSlot may be nullptr. This happens when we've run out of room in the currently allocated blocks. 
123 uint8* FreeSlot; 
124 int SlotSize; 
125 int SlotsInitialBlock; 
126 int SlotsPerExpansionBlock; 
127 
128 bool ThreadSafe; 
129 std::mutex PoolMutex; // Only used if ThreadSafe is true. 
130}; 
131 
132 
133} 
134 
135 
136// Implementation below this line. 
137 
138 
139inline void* tMem::tFastPool::Malloc(int numBytes) 
140{ 
141 // This can happen for a statically allocated pool that has yet to be constructed. It is safe to call Malloc on 
142 // such an object but nullptr is returned, allowing caller to fall back to tMalloc or something. 
143 if (!Constructed) 
144 return nullptr; 
145 
146 // The caller can fall-back on regular tMalloc if nullptr is returned. 
147 if (int(numBytes) > SlotSize) 
148 return nullptr; 
149 
150 if (ThreadSafe) 
151 PoolMutex.lock(); 
152 
153 // If the slot pointer is nullptr we need to grow the pool by adding another block. This will automatically set 
154 // FreeSlot to non-zero. 
155 if (!FreeSlot) 
156 { 
157 if (SlotsPerExpansionBlock > 0) 
158 { 
159 GrowPool(); 
160 } 
161 else 
162 { 
163 if (ThreadSafe) 
164 PoolMutex.unlock(); 
165 return nullptr; 
166 } 
167 } 
168 
169 // Free pointer to next free pointer. 
170 void* freeSlot = (void*)FreeSlot; 
171 
172 #ifdef MEMORY_ALLOCATOR_CHECK 
173 if (*((uint8**)FreeSlot)) 
174 SanityCheckSlotValid(*((uint8**)FreeSlot)); 
175 #endif 
176 
177 FreeSlot = *((uint8**)FreeSlot); 
178 NumAllocations++; 
179 
180 if (ThreadSafe) 
181 PoolMutex.unlock(); 
182 
183 return freeSlot; 
184} 
185 
186 
187inline void tMem::tFastPool::Free(void* slot) 
188{ 
189 #ifdef MEMORY_ALLOCATOR_CHECK 
190 SanityCheckSlotFreeable(slot); 
191 #endif 
192 
193 // This isn't delete. Zero is not allowed. 
194 tAssert(slot); 
195 
196 if (ThreadSafe) 
197 PoolMutex.lock(); 
198 
199 *((uint8**)slot) = FreeSlot; 
200 FreeSlot = (uint8*)slot; 
201 
202 NumAllocations--; 
203 
204 // If Constructed is false and NumAllocations is 0 we free the pool memory. 
205 if (!Constructed && (NumAllocations == 0)) 
206 { 
207 while (SlotBlock* block = Blocks.Remove()) 
208 { 
209 block->Shutdown(); 
210 tFree(block); 
211 } 
212 } 
213 
214 if (ThreadSafe) 
215 PoolMutex.unlock(); 
216} 
217