michael@0: //
michael@0: // Copyright (c) 2002-2010 The ANGLE Project Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: //
michael@0: 
michael@0: #ifndef _POOLALLOC_INCLUDED_
michael@0: #define _POOLALLOC_INCLUDED_
michael@0: 
michael@0: #ifdef _DEBUG
michael@0: #define GUARD_BLOCKS  // define to enable guard block sanity checking
michael@0: #endif
michael@0: 
michael@0: //
michael@0: // This header defines an allocator that can be used to efficiently
michael@0: // allocate a large number of small requests for heap memory, with the 
michael@0: // intention that they are not individually deallocated, but rather 
michael@0: // collectively deallocated at one time.
michael@0: //
michael@0: // This simultaneously
michael@0: //
michael@0: // * Makes each individual allocation much more efficient; the
michael@0: //     typical allocation is trivial.
michael@0: // * Completely avoids the cost of doing individual deallocation.
michael@0: // * Saves the trouble of tracking down and plugging a large class of leaks.
michael@0: //
michael@0: // Individual classes can use this allocator by supplying their own
michael@0: // new and delete methods.
michael@0: //
michael@0: // STL containers can use this allocator by using the pool_allocator
michael@0: // class as the allocator (second) template argument.
michael@0: //
michael@0: 
michael@0: #include <stddef.h>
michael@0: #include <string.h>
michael@0: #include <vector>
michael@0: 
michael@0: // If we are using guard blocks, we must track each indivual
michael@0: // allocation.  If we aren't using guard blocks, these
michael@0: // never get instantiated, so won't have any impact.
michael@0: // 
michael@0: 
michael@0: class TAllocation {
michael@0: public:
michael@0:     TAllocation(size_t size, unsigned char* mem, TAllocation* prev = 0) :
michael@0:         size(size), mem(mem), prevAlloc(prev) {
michael@0:         // Allocations are bracketed:
michael@0:         //    [allocationHeader][initialGuardBlock][userData][finalGuardBlock]
michael@0:         // This would be cleaner with if (guardBlockSize)..., but that
michael@0:         // makes the compiler print warnings about 0 length memsets,
michael@0:         // even with the if() protecting them.
michael@0: #ifdef GUARD_BLOCKS
michael@0:         memset(preGuard(), guardBlockBeginVal, guardBlockSize);
michael@0:         memset(data(),      userDataFill,       size);
michael@0:         memset(postGuard(), guardBlockEndVal,   guardBlockSize);
michael@0: #endif
michael@0:     }
michael@0: 
michael@0:     void check() const {
michael@0:         checkGuardBlock(preGuard(),  guardBlockBeginVal, "before");
michael@0:         checkGuardBlock(postGuard(), guardBlockEndVal,   "after");
michael@0:     }
michael@0: 
michael@0:     void checkAllocList() const;
michael@0: 
michael@0:     // Return total size needed to accomodate user buffer of 'size',
michael@0:     // plus our tracking data.
michael@0:     inline static size_t allocationSize(size_t size) {
michael@0:         return size + 2 * guardBlockSize + headerSize();
michael@0:     }
michael@0: 
michael@0:     // Offset from surrounding buffer to get to user data buffer.
michael@0:     inline static unsigned char* offsetAllocation(unsigned char* m) {
michael@0:         return m + guardBlockSize + headerSize();
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     void checkGuardBlock(unsigned char* blockMem, unsigned char val, const char* locText) const;
michael@0: 
michael@0:     // Find offsets to pre and post guard blocks, and user data buffer
michael@0:     unsigned char* preGuard()  const { return mem + headerSize(); }
michael@0:     unsigned char* data()      const { return preGuard() + guardBlockSize; }
michael@0:     unsigned char* postGuard() const { return data() + size; }
michael@0: 
michael@0:     size_t size;                  // size of the user data area
michael@0:     unsigned char* mem;           // beginning of our allocation (pts to header)
michael@0:     TAllocation* prevAlloc;       // prior allocation in the chain
michael@0: 
michael@0:     // Support MSVC++ 6.0
michael@0:     const static unsigned char guardBlockBeginVal;
michael@0:     const static unsigned char guardBlockEndVal;
michael@0:     const static unsigned char userDataFill;
michael@0: 
michael@0:     const static size_t guardBlockSize;
michael@0: #ifdef GUARD_BLOCKS
michael@0:     inline static size_t headerSize() { return sizeof(TAllocation); }
michael@0: #else
michael@0:     inline static size_t headerSize() { return 0; }
michael@0: #endif
michael@0: };
michael@0: 
michael@0: //
michael@0: // There are several stacks.  One is to track the pushing and popping
michael@0: // of the user, and not yet implemented.  The others are simply a 
michael@0: // repositories of free pages or used pages.
michael@0: //
michael@0: // Page stacks are linked together with a simple header at the beginning
michael@0: // of each allocation obtained from the underlying OS.  Multi-page allocations
michael@0: // are returned to the OS.  Individual page allocations are kept for future
michael@0: // re-use.
michael@0: //
michael@0: // The "page size" used is not, nor must it match, the underlying OS
michael@0: // page size.  But, having it be about that size or equal to a set of 
michael@0: // pages is likely most optimal.
michael@0: //
michael@0: class TPoolAllocator {
michael@0: public:
michael@0:     TPoolAllocator(int growthIncrement = 8*1024, int allocationAlignment = 16);
michael@0: 
michael@0:     //
michael@0:     // Don't call the destructor just to free up the memory, call pop()
michael@0:     //
michael@0:     ~TPoolAllocator();
michael@0: 
michael@0:     //
michael@0:     // Call push() to establish a new place to pop memory too.  Does not
michael@0:     // have to be called to get things started.
michael@0:     //
michael@0:     void push();
michael@0: 
michael@0:     //
michael@0:     // Call pop() to free all memory allocated since the last call to push(),
michael@0:     // or if no last call to push, frees all memory since first allocation.
michael@0:     //
michael@0:     void pop();
michael@0: 
michael@0:     //
michael@0:     // Call popAll() to free all memory allocated.
michael@0:     //
michael@0:     void popAll();
michael@0: 
michael@0:     //
michael@0:     // Call allocate() to actually acquire memory.  Returns 0 if no memory
michael@0:     // available, otherwise a properly aligned pointer to 'numBytes' of memory.
michael@0:     //
michael@0:     void* allocate(size_t numBytes);
michael@0: 
michael@0:     //
michael@0:     // There is no deallocate.  The point of this class is that
michael@0:     // deallocation can be skipped by the user of it, as the model
michael@0:     // of use is to simultaneously deallocate everything at once
michael@0:     // by calling pop(), and to not have to solve memory leak problems.
michael@0:     //
michael@0: 
michael@0: protected:
michael@0:     friend struct tHeader;
michael@0:     
michael@0:     struct tHeader {
michael@0:         tHeader(tHeader* nextPage, size_t pageCount) :
michael@0:             nextPage(nextPage),
michael@0:             pageCount(pageCount)
michael@0: #ifdef GUARD_BLOCKS
michael@0:           , lastAllocation(0)
michael@0: #endif
michael@0:             { }
michael@0: 
michael@0:         ~tHeader() {
michael@0: #ifdef GUARD_BLOCKS
michael@0:             if (lastAllocation)
michael@0:                 lastAllocation->checkAllocList();
michael@0: #endif
michael@0:         }
michael@0: 
michael@0:         tHeader* nextPage;
michael@0:         size_t pageCount;
michael@0: #ifdef GUARD_BLOCKS
michael@0:         TAllocation* lastAllocation;
michael@0: #endif
michael@0:     };
michael@0: 
michael@0:     struct tAllocState {
michael@0:         size_t offset;
michael@0:         tHeader* page;
michael@0:     };
michael@0:     typedef std::vector<tAllocState> tAllocStack;
michael@0: 
michael@0:     // Track allocations if and only if we're using guard blocks
michael@0:     void* initializeAllocation(tHeader* block, unsigned char* memory, size_t numBytes) {
michael@0: #ifdef GUARD_BLOCKS
michael@0:         new(memory) TAllocation(numBytes, memory, block->lastAllocation);
michael@0:         block->lastAllocation = reinterpret_cast<TAllocation*>(memory);
michael@0: #endif
michael@0:         // This is optimized entirely away if GUARD_BLOCKS is not defined.
michael@0:         return TAllocation::offsetAllocation(memory);
michael@0:     }
michael@0: 
michael@0:     size_t pageSize;        // granularity of allocation from the OS
michael@0:     size_t alignment;       // all returned allocations will be aligned at 
michael@0:                             // this granularity, which will be a power of 2
michael@0:     size_t alignmentMask;
michael@0:     size_t headerSkip;      // amount of memory to skip to make room for the
michael@0:                             //      header (basically, size of header, rounded
michael@0:                             //      up to make it aligned
michael@0:     size_t currentPageOffset;  // next offset in top of inUseList to allocate from
michael@0:     tHeader* freeList;      // list of popped memory
michael@0:     tHeader* inUseList;     // list of all memory currently being used
michael@0:     tAllocStack stack;      // stack of where to allocate from, to partition pool
michael@0: 
michael@0:     int numCalls;           // just an interesting statistic
michael@0:     size_t totalBytes;      // just an interesting statistic
michael@0: private:
michael@0:     TPoolAllocator& operator=(const TPoolAllocator&);  // dont allow assignment operator
michael@0:     TPoolAllocator(const TPoolAllocator&);  // dont allow default copy constructor
michael@0: };
michael@0: 
michael@0: 
michael@0: //
michael@0: // There could potentially be many pools with pops happening at
michael@0: // different times.  But a simple use is to have a global pop
michael@0: // with everyone using the same global allocator.
michael@0: //
michael@0: extern TPoolAllocator* GetGlobalPoolAllocator();
michael@0: extern void SetGlobalPoolAllocator(TPoolAllocator* poolAllocator);
michael@0: 
michael@0: //
michael@0: // This STL compatible allocator is intended to be used as the allocator
michael@0: // parameter to templatized STL containers, like vector and map.
michael@0: //
michael@0: // It will use the pools for allocation, and not
michael@0: // do any deallocation, but will still do destruction.
michael@0: //
michael@0: template<class T>
michael@0: class pool_allocator {
michael@0: public:
michael@0:     typedef size_t size_type;
michael@0:     typedef ptrdiff_t difference_type;
michael@0:     typedef T* pointer;
michael@0:     typedef const T* const_pointer;
michael@0:     typedef T& reference;
michael@0:     typedef const T& const_reference;
michael@0:     typedef T value_type;
michael@0: 
michael@0:     template<class Other> 
michael@0:     struct rebind {
michael@0:         typedef pool_allocator<Other> other;
michael@0:     };
michael@0:     pointer address(reference x) const { return &x; }
michael@0:     const_pointer address(const_reference x) const { return &x; }
michael@0: 
michael@0:     pool_allocator() : allocator(GetGlobalPoolAllocator()) { }
michael@0:     pool_allocator(TPoolAllocator& a) : allocator(&a) { }
michael@0:     pool_allocator(const pool_allocator<T>& p) : allocator(p.allocator) { }
michael@0: 
michael@0:     template <class Other>
michael@0:     pool_allocator<T>& operator=(const pool_allocator<Other>& p) {
michael@0:       allocator = p.allocator;
michael@0:       return *this;
michael@0:     }
michael@0: 
michael@0:     template<class Other>
michael@0:     pool_allocator(const pool_allocator<Other>& p) : allocator(&p.getAllocator()) { }
michael@0: 
michael@0: #if defined(__SUNPRO_CC) && !defined(_RWSTD_ALLOCATOR)
michael@0:     // libCStd on some platforms have a different allocate/deallocate interface.
michael@0:     // Caller pre-bakes sizeof(T) into 'n' which is the number of bytes to be
michael@0:     // allocated, not the number of elements.
michael@0:     void* allocate(size_type n) { 
michael@0:         return getAllocator().allocate(n);
michael@0:     }
michael@0:     void* allocate(size_type n, const void*) {
michael@0:         return getAllocator().allocate(n);
michael@0:     }
michael@0:     void deallocate(void*, size_type) {}
michael@0: #else
michael@0:     pointer allocate(size_type n) { 
michael@0:         return reinterpret_cast<pointer>(getAllocator().allocate(n * sizeof(T)));
michael@0:     }
michael@0:     pointer allocate(size_type n, const void*) { 
michael@0:         return reinterpret_cast<pointer>(getAllocator().allocate(n * sizeof(T)));
michael@0:     }
michael@0:     void deallocate(pointer, size_type) {}
michael@0: #endif  // _RWSTD_ALLOCATOR
michael@0: 
michael@0:     void construct(pointer p, const T& val) { new ((void *)p) T(val); }
michael@0:     void destroy(pointer p) { p->T::~T(); }
michael@0: 
michael@0:     bool operator==(const pool_allocator& rhs) const { return &getAllocator() == &rhs.getAllocator(); }
michael@0:     bool operator!=(const pool_allocator& rhs) const { return &getAllocator() != &rhs.getAllocator(); }
michael@0: 
michael@0:     size_type max_size() const { return static_cast<size_type>(-1) / sizeof(T); }
michael@0:     size_type max_size(int size) const { return static_cast<size_type>(-1) / size; }
michael@0: 
michael@0:     void setAllocator(TPoolAllocator* a) { allocator = a; }
michael@0:     TPoolAllocator& getAllocator() const { return *allocator; }
michael@0: 
michael@0: protected:
michael@0:     TPoolAllocator* allocator;
michael@0: };
michael@0: 
michael@0: #endif // _POOLALLOC_INCLUDED_