| // |
| // 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 |