Source code

Revision control

Copy as Markdown

Other Tools

//
// Copyright 2019 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.
//
// PoolAlloc.cpp:
// Implements the class methods for PoolAllocator and Allocation classes.
//
#include "common/PoolAlloc.h"
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include "common/angleutils.h"
#include "common/debug.h"
#include "common/mathutil.h"
#include "common/platform.h"
#include "common/tls.h"
namespace angle
{
// If we are using guard blocks, we must track each individual allocation. If we aren't using guard
// blocks, these never get instantiated, so won't have any impact.
class Allocation
{
public:
Allocation(size_t size, unsigned char *mem, Allocation *prev = 0)
: mSize(size), mMem(mem), mPrevAlloc(prev)
{
// Allocations are bracketed:
//
// [allocationHeader][initialGuardBlock][userData][finalGuardBlock]
//
// This would be cleaner with if (kGuardBlockSize)..., but that makes the compiler print
// warnings about 0 length memsets, even with the if() protecting them.
#if defined(ANGLE_POOL_ALLOC_GUARD_BLOCKS)
memset(preGuard(), kGuardBlockBeginVal, kGuardBlockSize);
memset(data(), kUserDataFill, mSize);
memset(postGuard(), kGuardBlockEndVal, kGuardBlockSize);
#endif
}
void checkAllocList() const;
static size_t AlignedHeaderSize(uint8_t *allocationBasePtr, size_t alignment)
{
// Make sure that the data offset after the header is aligned to the given alignment.
size_t base = reinterpret_cast<size_t>(allocationBasePtr);
return rx::roundUpPow2(base + kGuardBlockSize + HeaderSize(), alignment) - base;
}
// Return total size needed to accommodate user buffer of 'size',
// plus our tracking data and any necessary alignments.
static size_t AllocationSize(uint8_t *allocationBasePtr,
size_t size,
size_t alignment,
size_t *preAllocationPaddingOut)
{
// The allocation will be laid out as such:
//
// Aligned to |alignment|
// ^
// preAllocationPaddingOut |
// ___^___ |
// / \ |
// <padding>[header][guard][data][guard]
// \___________ __________/
// V
// dataOffset
//
// Note that alignment is at least as much as a pointer alignment, so the pointers in the
// header are also necessarily aligned appropriately.
//
size_t dataOffset = AlignedHeaderSize(allocationBasePtr, alignment);
*preAllocationPaddingOut = dataOffset - HeaderSize() - kGuardBlockSize;
return dataOffset + size + kGuardBlockSize;
}
// Given memory pointing to |header|, returns |data|.
static uint8_t *GetDataPointer(uint8_t *memory, size_t alignment)
{
uint8_t *alignedPtr = memory + kGuardBlockSize + HeaderSize();
// |memory| must be aligned already such that user data is aligned to |alignment|.
ASSERT((reinterpret_cast<uintptr_t>(alignedPtr) & (alignment - 1)) == 0);
return alignedPtr;
}
private:
void checkGuardBlock(unsigned char *blockMem, unsigned char val, const char *locText) const;
void checkAlloc() const
{
checkGuardBlock(preGuard(), kGuardBlockBeginVal, "before");
checkGuardBlock(postGuard(), kGuardBlockEndVal, "after");
}
// Find offsets to pre and post guard blocks, and user data buffer
unsigned char *preGuard() const { return mMem + HeaderSize(); }
unsigned char *data() const { return preGuard() + kGuardBlockSize; }
unsigned char *postGuard() const { return data() + mSize; }
size_t mSize; // size of the user data area
unsigned char *mMem; // beginning of our allocation (points to header)
Allocation *mPrevAlloc; // prior allocation in the chain
static constexpr unsigned char kGuardBlockBeginVal = 0xfb;
static constexpr unsigned char kGuardBlockEndVal = 0xfe;
static constexpr unsigned char kUserDataFill = 0xcd;
#if defined(ANGLE_POOL_ALLOC_GUARD_BLOCKS)
static constexpr size_t kGuardBlockSize = 16;
static constexpr size_t HeaderSize() { return sizeof(Allocation); }
#else
static constexpr size_t kGuardBlockSize = 0;
static constexpr size_t HeaderSize() { return 0; }
#endif
};
#if !defined(ANGLE_DISABLE_POOL_ALLOC)
class PageHeader
{
public:
PageHeader(PageHeader *nextPage, size_t pageCount)
: nextPage(nextPage),
pageCount(pageCount)
# if defined(ANGLE_POOL_ALLOC_GUARD_BLOCKS)
,
lastAllocation(nullptr)
# endif
{}
~PageHeader()
{
# if defined(ANGLE_POOL_ALLOC_GUARD_BLOCKS)
if (lastAllocation)
{
lastAllocation->checkAllocList();
}
# endif
}
PageHeader *nextPage;
size_t pageCount;
# if defined(ANGLE_POOL_ALLOC_GUARD_BLOCKS)
Allocation *lastAllocation;
# endif
};
#endif
//
// Implement the functionality of the PoolAllocator class, which
// is documented in PoolAlloc.h.
//
PoolAllocator::PoolAllocator(int growthIncrement, int allocationAlignment)
: mAlignment(allocationAlignment),
#if !defined(ANGLE_DISABLE_POOL_ALLOC)
mPageSize(growthIncrement),
mFreeList(nullptr),
mInUseList(nullptr),
mNumCalls(0),
mTotalBytes(0),
#endif
mLocked(false)
{
initialize(growthIncrement, allocationAlignment);
}
void PoolAllocator::initialize(int pageSize, int alignment)
{
mAlignment = alignment;
#if !defined(ANGLE_DISABLE_POOL_ALLOC)
mPageSize = pageSize;
mPageHeaderSkip = sizeof(PageHeader);
// Alignment == 1 is a special fast-path where fastAllocate() is enabled
if (mAlignment != 1)
{
#endif
// Adjust mAlignment to be at least pointer aligned and
// power of 2.
//
size_t minAlign = sizeof(void *);
if (mAlignment < minAlign)
{
mAlignment = minAlign;
}
mAlignment = gl::ceilPow2(static_cast<unsigned int>(mAlignment));
#if !defined(ANGLE_DISABLE_POOL_ALLOC)
}
//
// Don't allow page sizes we know are smaller than all common
// OS page sizes.
//
if (mPageSize < 4 * 1024)
{
mPageSize = 4 * 1024;
}
//
// A large mCurrentPageOffset indicates a new page needs to
// be obtained to allocate memory.
//
mCurrentPageOffset = mPageSize;
#else // !defined(ANGLE_DISABLE_POOL_ALLOC)
mStack.push_back({});
#endif
}
PoolAllocator::~PoolAllocator()
{
#if !defined(ANGLE_DISABLE_POOL_ALLOC)
while (mInUseList)
{
PageHeader *next = mInUseList->nextPage;
mInUseList->~PageHeader();
delete[] reinterpret_cast<char *>(mInUseList);
mInUseList = next;
}
// We should not check the guard blocks
// here, because we did it already when the block was
// placed into the free list.
//
while (mFreeList)
{
PageHeader *next = mFreeList->nextPage;
delete[] reinterpret_cast<char *>(mFreeList);
mFreeList = next;
}
#else // !defined(ANGLE_DISABLE_POOL_ALLOC)
for (auto &allocs : mStack)
{
for (auto alloc : allocs)
{
free(alloc);
}
}
mStack.clear();
#endif
}
//
// Check a single guard block for damage
//
void Allocation::checkGuardBlock(unsigned char *blockMem,
unsigned char val,
const char *locText) const
{
#if defined(ANGLE_POOL_ALLOC_GUARD_BLOCKS)
for (size_t x = 0; x < kGuardBlockSize; x++)
{
if (blockMem[x] != val)
{
char assertMsg[80];
// We don't print the assert message. It's here just to be helpful.
snprintf(assertMsg, sizeof(assertMsg),
"PoolAlloc: Damage %s %zu byte allocation at 0x%p\n", locText, mSize, data());
assert(0 && "PoolAlloc: Damage in guard block");
}
}
#endif
}
void PoolAllocator::push()
{
#if !defined(ANGLE_DISABLE_POOL_ALLOC)
AllocState state = {mCurrentPageOffset, mInUseList};
mStack.push_back(state);
//
// Indicate there is no current page to allocate from.
//
mCurrentPageOffset = mPageSize;
#else // !defined(ANGLE_DISABLE_POOL_ALLOC)
mStack.push_back({});
#endif
}
// Do a mass-deallocation of all the individual allocations that have occurred since the last
// push(), or since the last pop(), or since the object's creation.
//
// The deallocated pages are saved for future allocations.
void PoolAllocator::pop()
{
if (mStack.size() < 1)
{
return;
}
#if !defined(ANGLE_DISABLE_POOL_ALLOC)
PageHeader *page = mStack.back().page;
mCurrentPageOffset = mStack.back().offset;
while (mInUseList != page)
{
// invoke destructor to free allocation list
mInUseList->~PageHeader();
PageHeader *nextInUse = mInUseList->nextPage;
if (mInUseList->pageCount > 1)
{
delete[] reinterpret_cast<char *>(mInUseList);
}
else
{
mInUseList->nextPage = mFreeList;
mFreeList = mInUseList;
}
mInUseList = nextInUse;
}
mStack.pop_back();
#else // !defined(ANGLE_DISABLE_POOL_ALLOC)
for (auto &alloc : mStack.back())
{
free(alloc);
}
mStack.pop_back();
#endif
}
//
// Do a mass-deallocation of all the individual allocations
// that have occurred.
//
void PoolAllocator::popAll()
{
while (mStack.size() > 0)
pop();
}
void *PoolAllocator::allocate(size_t numBytes)
{
ASSERT(!mLocked);
#if !defined(ANGLE_DISABLE_POOL_ALLOC)
//
// Just keep some interesting statistics.
//
++mNumCalls;
mTotalBytes += numBytes;
uint8_t *currentPagePtr = reinterpret_cast<uint8_t *>(mInUseList) + mCurrentPageOffset;
size_t preAllocationPadding = 0;
size_t allocationSize =
Allocation::AllocationSize(currentPagePtr, numBytes, mAlignment, &preAllocationPadding);
// Integer overflow is unexpected.
ASSERT(allocationSize >= numBytes);
// Do the allocation, most likely case first, for efficiency.
if (allocationSize <= mPageSize - mCurrentPageOffset)
{
// There is enough room to allocate from the current page at mCurrentPageOffset.
uint8_t *memory = currentPagePtr + preAllocationPadding;
mCurrentPageOffset += allocationSize;
return initializeAllocation(memory, numBytes);
}
if (allocationSize > mPageSize - mPageHeaderSkip)
{
// If the allocation is larger than a whole page, do a multi-page allocation. These are not
// mixed with the others. The OS is efficient in allocating and freeing multiple pages.
// We don't know what the alignment of the new allocated memory will be, so conservatively
// allocate enough memory for up to alignment extra bytes being needed.
allocationSize = Allocation::AllocationSize(reinterpret_cast<uint8_t *>(mPageHeaderSkip),
numBytes, mAlignment, &preAllocationPadding);
size_t numBytesToAlloc = allocationSize + mPageHeaderSkip + mAlignment;
// Integer overflow is unexpected.
ASSERT(numBytesToAlloc >= allocationSize);
PageHeader *memory = reinterpret_cast<PageHeader *>(::new char[numBytesToAlloc]);
if (memory == nullptr)
{
return nullptr;
}
// Use placement-new to initialize header
new (memory) PageHeader(mInUseList, (numBytesToAlloc + mPageSize - 1) / mPageSize);
mInUseList = memory;
// Make next allocation come from a new page
mCurrentPageOffset = mPageSize;
// Now that we actually have the pointer, make sure the data pointer will be aligned.
currentPagePtr = reinterpret_cast<uint8_t *>(memory) + mPageHeaderSkip;
Allocation::AllocationSize(currentPagePtr, numBytes, mAlignment, &preAllocationPadding);
return initializeAllocation(currentPagePtr + preAllocationPadding, numBytes);
}
uint8_t *newPageAddr = allocateNewPage(numBytes);
return initializeAllocation(newPageAddr, numBytes);
#else // !defined(ANGLE_DISABLE_POOL_ALLOC)
void *alloc = malloc(numBytes + mAlignment - 1);
mStack.back().push_back(alloc);
intptr_t intAlloc = reinterpret_cast<intptr_t>(alloc);
intAlloc = rx::roundUpPow2<intptr_t>(intAlloc, mAlignment);
return reinterpret_cast<void *>(intAlloc);
#endif
}
#if !defined(ANGLE_DISABLE_POOL_ALLOC)
uint8_t *PoolAllocator::allocateNewPage(size_t numBytes)
{
// Need a simple page to allocate from. Pick a page from the free list, if any. Otherwise need
// to make the allocation.
PageHeader *memory;
if (mFreeList)
{
memory = mFreeList;
mFreeList = mFreeList->nextPage;
}
else
{
memory = reinterpret_cast<PageHeader *>(::new char[mPageSize]);
if (memory == nullptr)
{
return nullptr;
}
}
// Use placement-new to initialize header
new (memory) PageHeader(mInUseList, 1);
mInUseList = memory;
// Leave room for the page header.
mCurrentPageOffset = mPageHeaderSkip;
uint8_t *currentPagePtr = reinterpret_cast<uint8_t *>(mInUseList) + mCurrentPageOffset;
size_t preAllocationPadding = 0;
size_t allocationSize =
Allocation::AllocationSize(currentPagePtr, numBytes, mAlignment, &preAllocationPadding);
mCurrentPageOffset += allocationSize;
// The new allocation is made after the page header and any alignment required before it.
return reinterpret_cast<uint8_t *>(mInUseList) + mPageHeaderSkip + preAllocationPadding;
}
void *PoolAllocator::initializeAllocation(uint8_t *memory, size_t numBytes)
{
# if defined(ANGLE_POOL_ALLOC_GUARD_BLOCKS)
new (memory) Allocation(numBytes, memory, mInUseList->lastAllocation);
mInUseList->lastAllocation = reinterpret_cast<Allocation *>(memory);
# endif
return Allocation::GetDataPointer(memory, mAlignment);
}
#endif
void PoolAllocator::lock()
{
ASSERT(!mLocked);
mLocked = true;
}
void PoolAllocator::unlock()
{
ASSERT(mLocked);
mLocked = false;
}
//
// Check all allocations in a list for damage by calling check on each.
//
void Allocation::checkAllocList() const
{
for (const Allocation *alloc = this; alloc != nullptr; alloc = alloc->mPrevAlloc)
{
alloc->checkAlloc();
}
}
} // namespace angle