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