1 files changed, 487 insertions, 0 deletions
diff --git a/gfx/angle/checkout/src/common/PoolAlloc.cpp b/gfx/angle/checkout/src/common/PoolAlloc.cpp
new file mode 100644
index 0000000000..eef033ca04
--- /dev/null
+++ b/gfx/angle/checkout/src/common/PoolAlloc.cpp
@@ -0,0 +1,487 @@
+//
+// 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