PoolAlloc.h 10.4 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
//
// Copyright (c) 2002-2010 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//

#ifndef _POOLALLOC_INCLUDED_
#define _POOLALLOC_INCLUDED_

#ifdef _DEBUG
#define GUARD_BLOCKS  // define to enable guard block sanity checking
#endif

//
// This header defines an allocator that can be used to efficiently
// allocate a large number of small requests for heap memory, with the 
// intention that they are not individually deallocated, but rather 
// collectively deallocated at one time.
//
// This simultaneously
//
// * Makes each individual allocation much more efficient; the
//     typical allocation is trivial.
// * Completely avoids the cost of doing individual deallocation.
// * Saves the trouble of tracking down and plugging a large class of leaks.
//
// Individual classes can use this allocator by supplying their own
// new and delete methods.
//
// STL containers can use this allocator by using the pool_allocator
// class as the allocator (second) template argument.
//

#include <stddef.h>
#include <string.h>
#include <vector>

// If we are using guard blocks, we must track each indivual
// allocation.  If we aren't using guard blocks, these
// never get instantiated, so won't have any impact.
// 

class TAllocation {
public:
    TAllocation(size_t size, unsigned char* mem, TAllocation* prev = 0) :
        size(size), mem(mem), prevAlloc(prev) {
        // Allocations are bracketed:
        //    [allocationHeader][initialGuardBlock][userData][finalGuardBlock]
        // This would be cleaner with if (guardBlockSize)..., but that
        // makes the compiler print warnings about 0 length memsets,
        // even with the if() protecting them.
#ifdef GUARD_BLOCKS
        memset(preGuard(), guardBlockBeginVal, guardBlockSize);
        memset(data(),      userDataFill,       size);
        memset(postGuard(), guardBlockEndVal,   guardBlockSize);
#endif
    }

    void check() const {
        checkGuardBlock(preGuard(),  guardBlockBeginVal, "before");
        checkGuardBlock(postGuard(), guardBlockEndVal,   "after");
    }

    void checkAllocList() const;

    // Return total size needed to accomodate user buffer of 'size',
    // plus our tracking data.
    inline static size_t allocationSize(size_t size) {
        return size + 2 * guardBlockSize + headerSize();
    }

    // Offset from surrounding buffer to get to user data buffer.
    inline static unsigned char* offsetAllocation(unsigned char* m) {
        return m + guardBlockSize + headerSize();
    }

private:
    void checkGuardBlock(unsigned char* blockMem, unsigned char val, const char* locText) const;

    // Find offsets to pre and post guard blocks, and user data buffer
    unsigned char* preGuard()  const { return mem + headerSize(); }
    unsigned char* data()      const { return preGuard() + guardBlockSize; }
    unsigned char* postGuard() const { return data() + size; }

    size_t size;                  // size of the user data area
    unsigned char* mem;           // beginning of our allocation (pts to header)
    TAllocation* prevAlloc;       // prior allocation in the chain

    // Support MSVC++ 6.0
    const static unsigned char guardBlockBeginVal;
    const static unsigned char guardBlockEndVal;
    const static unsigned char userDataFill;

    const static size_t guardBlockSize;
#ifdef GUARD_BLOCKS
    inline static size_t headerSize() { return sizeof(TAllocation); }
#else
    inline static size_t headerSize() { return 0; }
#endif
};

//
// There are several stacks.  One is to track the pushing and popping
// of the user, and not yet implemented.  The others are simply a 
// repositories of free pages or used pages.
//
// Page stacks are linked together with a simple header at the beginning
// of each allocation obtained from the underlying OS.  Multi-page allocations
// are returned to the OS.  Individual page allocations are kept for future
// re-use.
//
// The "page size" used is not, nor must it match, the underlying OS
// page size.  But, having it be about that size or equal to a set of 
// pages is likely most optimal.
//
class TPoolAllocator {
public:
    TPoolAllocator(bool global = false, int growthIncrement = 8*1024, int allocationAlignment = 16);

    //
    // Don't call the destructor just to free up the memory, call pop()
    //
    ~TPoolAllocator();

    //
    // Call push() to establish a new place to pop memory too.  Does not
    // have to be called to get things started.
    //
    void push();

    //
    // Call pop() to free all memory allocated since the last call to push(),
    // or if no last call to push, frees all memory since first allocation.
    //
    void pop();

    //
    // Call popAll() to free all memory allocated.
    //
    void popAll();

    //
    // Call allocate() to actually acquire memory.  Returns 0 if no memory
    // available, otherwise a properly aligned pointer to 'numBytes' of memory.
    //
    void* allocate(size_t numBytes);

    //
    // There is no deallocate.  The point of this class is that
    // deallocation can be skipped by the user of it, as the model
    // of use is to simultaneously deallocate everything at once
    // by calling pop(), and to not have to solve memory leak problems.
    //

protected:
    friend struct tHeader;
    
    struct tHeader {
        tHeader(tHeader* nextPage, size_t pageCount) :
160
161
            nextPage(nextPage),
            pageCount(pageCount)
162
#ifdef GUARD_BLOCKS
163
          , lastAllocation(0)
164
#endif
165
            { }
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266

        ~tHeader() {
#ifdef GUARD_BLOCKS
            if (lastAllocation)
                lastAllocation->checkAllocList();
#endif
        }

        tHeader* nextPage;
        size_t pageCount;
#ifdef GUARD_BLOCKS
        TAllocation* lastAllocation;
#endif
    };

    struct tAllocState {
        size_t offset;
        tHeader* page;
    };
    typedef std::vector<tAllocState> tAllocStack;

    // Track allocations if and only if we're using guard blocks
    void* initializeAllocation(tHeader* block, unsigned char* memory, size_t numBytes) {
#ifdef GUARD_BLOCKS
        new(memory) TAllocation(numBytes, memory, block->lastAllocation);
        block->lastAllocation = reinterpret_cast<TAllocation*>(memory);
#endif
        // This is optimized entirely away if GUARD_BLOCKS is not defined.
        return TAllocation::offsetAllocation(memory);
    }

    bool global;            // should be true if this object is globally scoped
    size_t pageSize;        // granularity of allocation from the OS
    size_t alignment;       // all returned allocations will be aligned at 
                            // this granularity, which will be a power of 2
    size_t alignmentMask;
    size_t headerSkip;      // amount of memory to skip to make room for the
                            //      header (basically, size of header, rounded
                            //      up to make it aligned
    size_t currentPageOffset;  // next offset in top of inUseList to allocate from
    tHeader* freeList;      // list of popped memory
    tHeader* inUseList;     // list of all memory currently being used
    tAllocStack stack;      // stack of where to allocate from, to partition pool

    int numCalls;           // just an interesting statistic
    size_t totalBytes;      // just an interesting statistic
private:
    TPoolAllocator& operator=(const TPoolAllocator&);  // dont allow assignment operator
    TPoolAllocator(const TPoolAllocator&);  // dont allow default copy constructor
};


//
// There could potentially be many pools with pops happening at
// different times.  But a simple use is to have a global pop
// with everyone using the same global allocator.
//
typedef TPoolAllocator* PoolAllocatorPointer;
extern TPoolAllocator& GetGlobalPoolAllocator();
#define GlobalPoolAllocator GetGlobalPoolAllocator()


struct TThreadGlobalPools
{
    TPoolAllocator* globalPoolAllocator;
};

void SetGlobalPoolAllocatorPtr(TPoolAllocator* poolAllocator);

//
// This STL compatible allocator is intended to be used as the allocator
// parameter to templatized STL containers, like vector and map.
//
// It will use the pools for allocation, and not
// do any deallocation, but will still do destruction.
//
template<class T>
class pool_allocator {
public:
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;

    template<class Other> 
    struct rebind {
        typedef pool_allocator<Other> other;
    };
    pointer address(reference x) const { return &x; }
    const_pointer address(const_reference x) const { return &x; }

    pool_allocator() : allocator(GlobalPoolAllocator) { }
    pool_allocator(TPoolAllocator& a) : allocator(a) { }
    pool_allocator(const pool_allocator<T>& p) : allocator(p.allocator) { }

    template<class Other>
    pool_allocator(const pool_allocator<Other>& p) : allocator(p.getAllocator()) { }

267
268
269
270
271
272
273
274
275
276
277
278
#if defined(__SUNPRO_CC) && !defined(_RWSTD_ALLOCATOR)
    // libCStd on some platforms have a different allocate/deallocate interface.
    // Caller pre-bakes sizeof(T) into 'n' which is the number of bytes to be
    // allocated, not the number of elements.
    void* allocate(size_type n) { 
        return getAllocator().allocate(n);
    }
    void* allocate(size_type n, const void*) {
        return getAllocator().allocate(n);
    }
    void deallocate(void*, size_type) {}
#else
279
280
281
282
283
284
    pointer allocate(size_type n) { 
        return reinterpret_cast<pointer>(getAllocator().allocate(n * sizeof(T)));
    }
    pointer allocate(size_type n, const void*) { 
        return reinterpret_cast<pointer>(getAllocator().allocate(n * sizeof(T)));
    }
285
286
    void deallocate(pointer, size_type) {}
#endif  // _RWSTD_ALLOCATOR
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304

    void construct(pointer p, const T& val) { new ((void *)p) T(val); }
    void destroy(pointer p) { p->T::~T(); }

    bool operator==(const pool_allocator& rhs) const { return &getAllocator() == &rhs.getAllocator(); }
    bool operator!=(const pool_allocator& rhs) const { return &getAllocator() != &rhs.getAllocator(); }

    size_type max_size() const { return static_cast<size_type>(-1) / sizeof(T); }
    size_type max_size(int size) const { return static_cast<size_type>(-1) / size; }

    void setAllocator(TPoolAllocator* a) { allocator = *a; }
    TPoolAllocator& getAllocator() const { return allocator; }

protected:
    TPoolAllocator& allocator;
};

#endif // _POOLALLOC_INCLUDED_