1 // Copyright 2016 The SwiftShader Authors. All Rights Reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef _POOLALLOC_INCLUDED_ 16 #define _POOLALLOC_INCLUDED_ 17 18 #ifdef _DEBUG 19 #define GUARD_BLOCKS // define to enable guard block sanity checking 20 #endif 21 22 // 23 // This header defines an allocator that can be used to efficiently 24 // allocate a large number of small requests for heap memory, with the 25 // intention that they are not individually deallocated, but rather 26 // collectively deallocated at one time. 27 // 28 // This simultaneously 29 // 30 // * Makes each individual allocation much more efficient; the 31 // typical allocation is trivial. 32 // * Completely avoids the cost of doing individual deallocation. 33 // * Saves the trouble of tracking down and plugging a large class of leaks. 34 // 35 // Individual classes can use this allocator by supplying their own 36 // new and delete methods. 37 // 38 // STL containers can use this allocator by using the pool_allocator 39 // class as the allocator (second) template argument. 40 // 41 42 #include <stddef.h> 43 #include <string.h> 44 #include <vector> 45 46 // If we are using guard blocks, we must track each indivual 47 // allocation. If we aren't using guard blocks, these 48 // never get instantiated, so won't have any impact. 49 // 50 51 class TAllocation { 52 public: 53 TAllocation(size_t size, unsigned char* mem, TAllocation* prev = 0) : size(size)54 size(size), mem(mem), prevAlloc(prev) { 55 // Allocations are bracketed: 56 // [allocationHeader][initialGuardBlock][userData][finalGuardBlock] 57 // This would be cleaner with if (guardBlockSize)..., but that 58 // makes the compiler print warnings about 0 length memsets, 59 // even with the if() protecting them. 60 #ifdef GUARD_BLOCKS 61 memset(preGuard(), guardBlockBeginVal, guardBlockSize); 62 memset(data(), userDataFill, size); 63 memset(postGuard(), guardBlockEndVal, guardBlockSize); 64 #endif 65 } 66 check()67 void check() const { 68 checkGuardBlock(preGuard(), guardBlockBeginVal, "before"); 69 checkGuardBlock(postGuard(), guardBlockEndVal, "after"); 70 } 71 72 void checkAllocList() const; 73 74 // Return total size needed to accomodate user buffer of 'size', 75 // plus our tracking data. allocationSize(size_t size)76 inline static size_t allocationSize(size_t size) { 77 return size + 2 * guardBlockSize + headerSize(); 78 } 79 80 // Offset from surrounding buffer to get to user data buffer. offsetAllocation(unsigned char * m)81 inline static unsigned char* offsetAllocation(unsigned char* m) { 82 return m + guardBlockSize + headerSize(); 83 } 84 85 private: 86 void checkGuardBlock(unsigned char* blockMem, unsigned char val, const char* locText) const; 87 88 // Find offsets to pre and post guard blocks, and user data buffer preGuard()89 unsigned char* preGuard() const { return mem + headerSize(); } data()90 unsigned char* data() const { return preGuard() + guardBlockSize; } postGuard()91 unsigned char* postGuard() const { return data() + size; } 92 93 size_t size; // size of the user data area 94 unsigned char* mem; // beginning of our allocation (pts to header) 95 TAllocation* prevAlloc; // prior allocation in the chain 96 97 // Support MSVC++ 6.0 98 const static unsigned char guardBlockBeginVal; 99 const static unsigned char guardBlockEndVal; 100 const static unsigned char userDataFill; 101 102 const static size_t guardBlockSize; 103 #ifdef GUARD_BLOCKS headerSize()104 inline static size_t headerSize() { return sizeof(TAllocation); } 105 #else headerSize()106 inline static size_t headerSize() { return 0; } 107 #endif 108 }; 109 110 // 111 // There are several stacks. One is to track the pushing and popping 112 // of the user, and not yet implemented. The others are simply a 113 // repositories of free pages or used pages. 114 // 115 // Page stacks are linked together with a simple header at the beginning 116 // of each allocation obtained from the underlying OS. Multi-page allocations 117 // are returned to the OS. Individual page allocations are kept for future 118 // re-use. 119 // 120 // The "page size" used is not, nor must it match, the underlying OS 121 // page size. But, having it be about that size or equal to a set of 122 // pages is likely most optimal. 123 // 124 class TPoolAllocator { 125 public: 126 TPoolAllocator(int growthIncrement = 8*1024, int allocationAlignment = 16); 127 128 // 129 // Don't call the destructor just to free up the memory, call pop() 130 // 131 ~TPoolAllocator(); 132 133 // 134 // Call push() to establish a new place to pop memory too. Does not 135 // have to be called to get things started. 136 // 137 void push(); 138 139 // 140 // Call pop() to free all memory allocated since the last call to push(), 141 // or if no last call to push, frees all memory since first allocation. 142 // 143 void pop(); 144 145 // 146 // Call popAll() to free all memory allocated. 147 // 148 void popAll(); 149 150 // 151 // Call allocate() to actually acquire memory. Returns 0 if no memory 152 // available, otherwise a properly aligned pointer to 'numBytes' of memory. 153 // 154 void* allocate(size_t numBytes); 155 156 // 157 // There is no deallocate. The point of this class is that 158 // deallocation can be skipped by the user of it, as the model 159 // of use is to simultaneously deallocate everything at once 160 // by calling pop(), and to not have to solve memory leak problems. 161 // 162 163 protected: 164 friend struct tHeader; 165 166 struct tHeader { tHeadertHeader167 tHeader(tHeader* nextPage, size_t pageCount) : 168 nextPage(nextPage), 169 pageCount(pageCount) 170 #ifdef GUARD_BLOCKS 171 , lastAllocation(0) 172 #endif 173 { } 174 ~tHeadertHeader175 ~tHeader() { 176 #ifdef GUARD_BLOCKS 177 if (lastAllocation) 178 lastAllocation->checkAllocList(); 179 #endif 180 } 181 182 tHeader* nextPage; 183 size_t pageCount; 184 #ifdef GUARD_BLOCKS 185 TAllocation* lastAllocation; 186 #endif 187 }; 188 189 struct tAllocState { 190 size_t offset; 191 tHeader* page; 192 }; 193 typedef std::vector<tAllocState> tAllocStack; 194 195 // Track allocations if and only if we're using guard blocks initializeAllocation(tHeader * block,unsigned char * memory,size_t numBytes)196 void* initializeAllocation(tHeader* block, unsigned char* memory, size_t numBytes) { 197 #ifdef GUARD_BLOCKS 198 new(memory) TAllocation(numBytes, memory, block->lastAllocation); 199 block->lastAllocation = reinterpret_cast<TAllocation*>(memory); 200 #endif 201 // This is optimized entirely away if GUARD_BLOCKS is not defined. 202 return TAllocation::offsetAllocation(memory); 203 } 204 205 size_t pageSize; // granularity of allocation from the OS 206 size_t alignment; // all returned allocations will be aligned at 207 // this granularity, which will be a power of 2 208 size_t alignmentMask; 209 size_t headerSkip; // amount of memory to skip to make room for the 210 // header (basically, size of header, rounded 211 // up to make it aligned 212 size_t currentPageOffset; // next offset in top of inUseList to allocate from 213 tHeader* freeList; // list of popped memory 214 tHeader* inUseList; // list of all memory currently being used 215 tAllocStack stack; // stack of where to allocate from, to partition pool 216 217 int numCalls; // just an interesting statistic 218 size_t totalBytes; // just an interesting statistic 219 private: 220 TPoolAllocator& operator=(const TPoolAllocator&); // dont allow assignment operator 221 TPoolAllocator(const TPoolAllocator&); // dont allow default copy constructor 222 }; 223 224 225 // 226 // There could potentially be many pools with pops happening at 227 // different times. But a simple use is to have a global pop 228 // with everyone using the same global allocator. 229 // 230 extern TPoolAllocator* GetGlobalPoolAllocator(); 231 extern void SetGlobalPoolAllocator(TPoolAllocator* poolAllocator); 232 233 // 234 // This STL compatible allocator is intended to be used as the allocator 235 // parameter to templatized STL containers, like vector and map. 236 // 237 // It will use the pools for allocation, and not 238 // do any deallocation, but will still do destruction. 239 // 240 template<class T> 241 class pool_allocator { 242 public: 243 typedef size_t size_type; 244 typedef ptrdiff_t difference_type; 245 typedef T* pointer; 246 typedef const T* const_pointer; 247 typedef T& reference; 248 typedef const T& const_reference; 249 typedef T value_type; 250 251 template<class Other> 252 struct rebind { 253 typedef pool_allocator<Other> other; 254 }; address(reference x)255 pointer address(reference x) const { return &x; } address(const_reference x)256 const_pointer address(const_reference x) const { return &x; } 257 pool_allocator()258 pool_allocator() : allocator(GetGlobalPoolAllocator()) { } pool_allocator(TPoolAllocator & a)259 pool_allocator(TPoolAllocator& a) : allocator(&a) { } pool_allocator(const pool_allocator<T> & p)260 pool_allocator(const pool_allocator<T>& p) : allocator(p.allocator) { } 261 262 template <class Other> 263 pool_allocator<T>& operator=(const pool_allocator<Other>& p) { 264 allocator = p.allocator; 265 return *this; 266 } 267 268 template<class Other> pool_allocator(const pool_allocator<Other> & p)269 pool_allocator(const pool_allocator<Other>& p) : allocator(&p.getAllocator()) { } 270 271 #if defined(__SUNPRO_CC) && !defined(_RWSTD_ALLOCATOR) 272 // libCStd on some platforms have a different allocate/deallocate interface. 273 // Caller pre-bakes sizeof(T) into 'n' which is the number of bytes to be 274 // allocated, not the number of elements. allocate(size_type n)275 void* allocate(size_type n) { 276 return getAllocator().allocate(n); 277 } allocate(size_type n,const void *)278 void* allocate(size_type n, const void*) { 279 return getAllocator().allocate(n); 280 } deallocate(void *,size_type)281 void deallocate(void*, size_type) {} 282 #else allocate(size_type n)283 pointer allocate(size_type n) { 284 return reinterpret_cast<pointer>(getAllocator().allocate(n * sizeof(T))); 285 } allocate(size_type n,const void *)286 pointer allocate(size_type n, const void*) { 287 return reinterpret_cast<pointer>(getAllocator().allocate(n * sizeof(T))); 288 } deallocate(pointer,size_type)289 void deallocate(pointer, size_type) {} 290 #endif // _RWSTD_ALLOCATOR 291 construct(pointer p,const T & val)292 void construct(pointer p, const T& val) { new ((void *)p) T(val); } destroy(pointer p)293 void destroy(pointer p) { p->T::~T(); } 294 295 bool operator==(const pool_allocator& rhs) const { return &getAllocator() == &rhs.getAllocator(); } 296 bool operator!=(const pool_allocator& rhs) const { return &getAllocator() != &rhs.getAllocator(); } 297 max_size()298 size_type max_size() const { return static_cast<size_type>(-1) / sizeof(T); } max_size(int size)299 size_type max_size(int size) const { return static_cast<size_type>(-1) / size; } 300 setAllocator(TPoolAllocator * a)301 void setAllocator(TPoolAllocator *a) { allocator = a; } getAllocator()302 TPoolAllocator& getAllocator() const { return *allocator; } 303 304 protected: 305 TPoolAllocator *allocator; 306 }; 307 308 #endif // _POOLALLOC_INCLUDED_ 309