The Tor Browser / file revision

 //

 // 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(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) :

             nextPage(nextPage),

             pageCount(pageCount)

 #ifdef GUARD_BLOCKS

           , lastAllocation(0)

 #endif

             { }

         ~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);

     }

     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.

 //

 extern TPoolAllocator* GetGlobalPoolAllocator();

 extern void SetGlobalPoolAllocator(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(GetGlobalPoolAllocator()) { }

     pool_allocator(TPoolAllocator& a) : allocator(&a) { }

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

     template <class Other>

     pool_allocator<T>& operator=(const pool_allocator<Other>& p) {

       allocator = p.allocator;

       return *this;

     }

     template<class Other>

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

 #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

     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)));

     }

     void deallocate(pointer, size_type) {}

 #endif  // _RWSTD_ALLOCATOR

     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_