• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //
2 // Copyright (C) 2002-2005  3Dlabs Inc. Ltd.
3 // Copyright (C) 2012-2013 LunarG, Inc.
4 //
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions
9 // are met:
10 //
11 //    Redistributions of source code must retain the above copyright
12 //    notice, this list of conditions and the following disclaimer.
13 //
14 //    Redistributions in binary form must reproduce the above
15 //    copyright notice, this list of conditions and the following
16 //    disclaimer in the documentation and/or other materials provided
17 //    with the distribution.
18 //
19 //    Neither the name of 3Dlabs Inc. Ltd. nor the names of its
20 //    contributors may be used to endorse or promote products derived
21 //    from this software without specific prior written permission.
22 //
23 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27 // COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 // POSSIBILITY OF SUCH DAMAGE.
35 //
36 
37 #ifndef _POOLALLOC_INCLUDED_
38 #define _POOLALLOC_INCLUDED_
39 
40 #ifdef _DEBUG
41 #  define GUARD_BLOCKS  // define to enable guard block sanity checking
42 #endif
43 
44 //
45 // This header defines an allocator that can be used to efficiently
46 // allocate a large number of small requests for heap memory, with the
47 // intention that they are not individually deallocated, but rather
48 // collectively deallocated at one time.
49 //
50 // This simultaneously
51 //
52 // * Makes each individual allocation much more efficient; the
53 //     typical allocation is trivial.
54 // * Completely avoids the cost of doing individual deallocation.
55 // * Saves the trouble of tracking down and plugging a large class of leaks.
56 //
57 // Individual classes can use this allocator by supplying their own
58 // new and delete methods.
59 //
60 // STL containers can use this allocator by using the pool_allocator
61 // class as the allocator (second) template argument.
62 //
63 
64 #include <cstddef>
65 #include <cstring>
66 #include <vector>
67 
68 namespace glslang {
69 
70 // If we are using guard blocks, we must track each individual
71 // allocation.  If we aren't using guard blocks, these
72 // never get instantiated, so won't have any impact.
73 //
74 
75 class TAllocation {
76 public:
77     TAllocation(size_t size, unsigned char* mem, TAllocation* prev = 0) :
size(size)78         size(size), mem(mem), prevAlloc(prev) {
79         // Allocations are bracketed:
80         //    [allocationHeader][initialGuardBlock][userData][finalGuardBlock]
81         // This would be cleaner with if (guardBlockSize)..., but that
82         // makes the compiler print warnings about 0 length memsets,
83         // even with the if() protecting them.
84 #       ifdef GUARD_BLOCKS
85             memset(preGuard(),  guardBlockBeginVal, guardBlockSize);
86             memset(data(),      userDataFill,       size);
87             memset(postGuard(), guardBlockEndVal,   guardBlockSize);
88 #       endif
89     }
90 
check()91     void check() const {
92         checkGuardBlock(preGuard(),  guardBlockBeginVal, "before");
93         checkGuardBlock(postGuard(), guardBlockEndVal,   "after");
94     }
95 
96     void checkAllocList() const;
97 
98     // Return total size needed to accommodate user buffer of 'size',
99     // plus our tracking data.
allocationSize(size_t size)100     inline static size_t allocationSize(size_t size) {
101         return size + 2 * guardBlockSize + headerSize();
102     }
103 
104     // Offset from surrounding buffer to get to user data buffer.
offsetAllocation(unsigned char * m)105     inline static unsigned char* offsetAllocation(unsigned char* m) {
106         return m + guardBlockSize + headerSize();
107     }
108 
109 private:
110     void checkGuardBlock(unsigned char* blockMem, unsigned char val, const char* locText) const;
111 
112     // Find offsets to pre and post guard blocks, and user data buffer
preGuard()113     unsigned char* preGuard()  const { return mem + headerSize(); }
data()114     unsigned char* data()      const { return preGuard() + guardBlockSize; }
postGuard()115     unsigned char* postGuard() const { return data() + size; }
116 
117     size_t size;                  // size of the user data area
118     unsigned char* mem;           // beginning of our allocation (pts to header)
119     TAllocation* prevAlloc;       // prior allocation in the chain
120 
121     const static unsigned char guardBlockBeginVal;
122     const static unsigned char guardBlockEndVal;
123     const static unsigned char userDataFill;
124 
125     const static size_t guardBlockSize;
126 #   ifdef GUARD_BLOCKS
headerSize()127     inline static size_t headerSize() { return sizeof(TAllocation); }
128 #   else
headerSize()129     inline static size_t headerSize() { return 0; }
130 #   endif
131 };
132 
133 //
134 // There are several stacks.  One is to track the pushing and popping
135 // of the user, and not yet implemented.  The others are simply a
136 // repositories of free pages or used pages.
137 //
138 // Page stacks are linked together with a simple header at the beginning
139 // of each allocation obtained from the underlying OS.  Multi-page allocations
140 // are returned to the OS.  Individual page allocations are kept for future
141 // re-use.
142 //
143 // The "page size" used is not, nor must it match, the underlying OS
144 // page size.  But, having it be about that size or equal to a set of
145 // pages is likely most optimal.
146 //
147 class TPoolAllocator {
148 public:
149     TPoolAllocator(int growthIncrement = 8*1024, int allocationAlignment = 16);
150 
151     //
152     // Don't call the destructor just to free up the memory, call pop()
153     //
154     ~TPoolAllocator();
155 
156     //
157     // Call push() to establish a new place to pop memory too.  Does not
158     // have to be called to get things started.
159     //
160     void push();
161 
162     //
163     // Call pop() to free all memory allocated since the last call to push(),
164     // or if no last call to push, frees all memory since first allocation.
165     //
166     void pop();
167 
168     //
169     // Call popAll() to free all memory allocated.
170     //
171     void popAll();
172 
173     //
174     // Call allocate() to actually acquire memory.  Returns 0 if no memory
175     // available, otherwise a properly aligned pointer to 'numBytes' of memory.
176     //
177     void* allocate(size_t numBytes);
178 
179     //
180     // There is no deallocate.  The point of this class is that
181     // deallocation can be skipped by the user of it, as the model
182     // of use is to simultaneously deallocate everything at once
183     // by calling pop(), and to not have to solve memory leak problems.
184     //
185 
186 protected:
187     friend struct tHeader;
188 
189     struct tHeader {
tHeadertHeader190         tHeader(tHeader* nextPage, size_t pageCount) :
191 #ifdef GUARD_BLOCKS
192         lastAllocation(0),
193 #endif
194         nextPage(nextPage), pageCount(pageCount) { }
195 
~tHeadertHeader196         ~tHeader() {
197 #ifdef GUARD_BLOCKS
198             if (lastAllocation)
199                 lastAllocation->checkAllocList();
200 #endif
201         }
202 
203 #ifdef GUARD_BLOCKS
204         TAllocation* lastAllocation;
205 #endif
206         tHeader* nextPage;
207         size_t pageCount;
208     };
209 
210     struct tAllocState {
211         size_t offset;
212         tHeader* page;
213     };
214     typedef std::vector<tAllocState> tAllocStack;
215 
216     // Track allocations if and only if we're using guard blocks
217 #ifndef GUARD_BLOCKS
initializeAllocation(tHeader *,unsigned char * memory,size_t)218     void* initializeAllocation(tHeader*, unsigned char* memory, size_t) {
219 #else
220     void* initializeAllocation(tHeader* block, unsigned char* memory, size_t numBytes) {
221         new(memory) TAllocation(numBytes, memory, block->lastAllocation);
222         block->lastAllocation = reinterpret_cast<TAllocation*>(memory);
223 #endif
224 
225         // This is optimized entirely away if GUARD_BLOCKS is not defined.
226         return TAllocation::offsetAllocation(memory);
227     }
228 
229     size_t pageSize;        // granularity of allocation from the OS
230     size_t alignment;       // all returned allocations will be aligned at
231                             //      this granularity, which will be a power of 2
232     size_t alignmentMask;
233     size_t headerSkip;      // amount of memory to skip to make room for the
234                             //      header (basically, size of header, rounded
235                             //      up to make it aligned
236     size_t currentPageOffset;  // next offset in top of inUseList to allocate from
237     tHeader* freeList;      // list of popped memory
238     tHeader* inUseList;     // list of all memory currently being used
239     tAllocStack stack;      // stack of where to allocate from, to partition pool
240 
241     int numCalls;           // just an interesting statistic
242     size_t totalBytes;      // just an interesting statistic
243 private:
244     TPoolAllocator& operator=(const TPoolAllocator&);  // don't allow assignment operator
245     TPoolAllocator(const TPoolAllocator&);  // don't allow default copy constructor
246 };
247 
248 //
249 // There could potentially be many pools with pops happening at
250 // different times.  But a simple use is to have a global pop
251 // with everyone using the same global allocator.
252 //
253 extern TPoolAllocator& GetThreadPoolAllocator();
254 void SetThreadPoolAllocator(TPoolAllocator* poolAllocator);
255 
256 //
257 // This STL compatible allocator is intended to be used as the allocator
258 // parameter to templatized STL containers, like vector and map.
259 //
260 // It will use the pools for allocation, and not
261 // do any deallocation, but will still do destruction.
262 //
263 template<class T>
264 class pool_allocator {
265 public:
266     typedef size_t size_type;
267     typedef ptrdiff_t difference_type;
268     typedef T *pointer;
269     typedef const T *const_pointer;
270     typedef T& reference;
271     typedef const T& const_reference;
272     typedef T value_type;
273     template<class Other>
274         struct rebind {
275             typedef pool_allocator<Other> other;
276         };
address(reference x)277     pointer address(reference x) const { return &x; }
address(const_reference x)278     const_pointer address(const_reference x) const { return &x; }
279 
pool_allocator()280     pool_allocator() : allocator(GetThreadPoolAllocator()) { }
pool_allocator(TPoolAllocator & a)281     pool_allocator(TPoolAllocator& a) : allocator(a) { }
pool_allocator(const pool_allocator<T> & p)282     pool_allocator(const pool_allocator<T>& p) : allocator(p.allocator) { }
283 
284     template<class Other>
pool_allocator(const pool_allocator<Other> & p)285         pool_allocator(const pool_allocator<Other>& p) : allocator(p.getAllocator()) { }
286 
allocate(size_type n)287     pointer allocate(size_type n) {
288         return reinterpret_cast<pointer>(getAllocator().allocate(n * sizeof(T))); }
allocate(size_type n,const void *)289     pointer allocate(size_type n, const void*) {
290         return reinterpret_cast<pointer>(getAllocator().allocate(n * sizeof(T))); }
291 
deallocate(void *,size_type)292     void deallocate(void*, size_type) { }
deallocate(pointer,size_type)293     void deallocate(pointer, size_type) { }
294 
_Charalloc(size_t n)295     pointer _Charalloc(size_t n) {
296         return reinterpret_cast<pointer>(getAllocator().allocate(n)); }
297 
construct(pointer p,const T & val)298     void construct(pointer p, const T& val) { new ((void *)p) T(val); }
destroy(pointer p)299     void destroy(pointer p) { p->T::~T(); }
300 
301     bool operator==(const pool_allocator& rhs) const { return &getAllocator() == &rhs.getAllocator(); }
302     bool operator!=(const pool_allocator& rhs) const { return &getAllocator() != &rhs.getAllocator(); }
303 
max_size()304     size_type max_size() const { return static_cast<size_type>(-1) / sizeof(T); }
max_size(int size)305     size_type max_size(int size) const { return static_cast<size_type>(-1) / size; }
306 
setAllocator(TPoolAllocator * a)307     void setAllocator(TPoolAllocator* a) { allocator = *a; }
getAllocator()308     TPoolAllocator& getAllocator() const { return allocator; }
309 
310 protected:
311     pool_allocator& operator=(const pool_allocator&) { return *this; }
312     TPoolAllocator& allocator;
313 };
314 
315 } // end namespace glslang
316 
317 #endif // _POOLALLOC_INCLUDED_
318