blob: ad63bc4cd66aa89784f6c6e410742255240130fe [file] [log] [blame]
//
// 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 COMPILER_TRANSLATOR_POOLALLOC_H_
#define COMPILER_TRANSLATOR_POOLALLOC_H_
#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.
//
// Catch unwanted allocations.
// TODO(jmadill): Remove this when we remove the global allocator.
void lock();
void unlock();
private:
size_t alignment; // all returned allocations will be aligned at
// this granularity, which will be a power of 2
size_t alignmentMask;
#if !defined(ANGLE_TRANSLATOR_DISABLE_POOL_ALLOC)
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 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 mStack; // stack of where to allocate from, to partition pool
int numCalls; // just an interesting statistic
size_t totalBytes; // just an interesting statistic
#else // !defined(ANGLE_TRANSLATOR_DISABLE_POOL_ALLOC)
std::vector<std::vector<void *>> mStack;
#endif
TPoolAllocator &operator=(const TPoolAllocator &); // dont allow assignment operator
TPoolAllocator(const TPoolAllocator &); // dont allow default copy constructor
bool mLocked;
};
//
// 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() {}
template <class Other>
pool_allocator(const pool_allocator<Other> &p)
{
}
template <class Other>
pool_allocator<T> &operator=(const pool_allocator<Other> &p)
{
return *this;
}
#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 true; }
bool operator!=(const pool_allocator &rhs) const { return false; }
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; }
TPoolAllocator &getAllocator() const { return *GetGlobalPoolAllocator(); }
};
#endif // COMPILER_TRANSLATOR_POOLALLOC_H_