| /* |
| * Copyright (C) 2011-2018 Apple Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. Neither the name of Apple Inc. ("Apple") nor the names of |
| * its contributors may be used to endorse or promote products derived |
| * from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
| * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
| * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY |
| * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
| * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
| * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "config.h" |
| #include <stdarg.h> |
| #include <wtf/MetaAllocator.h> |
| #include <wtf/Vector.h> |
| |
| #if OS(WINDOWS) |
| #undef small |
| #endif |
| |
| namespace TestWebKitAPI { |
| |
| using namespace WTF; |
| |
| class MetaAllocatorTest: public testing::Test { |
| public: |
| enum SanityCheckMode { RunSanityCheck, DontRunSanityCheck }; |
| |
| enum HeapGrowthMode { DontGrowHeap, ForTestDemandAllocCoalesce, ForTestDemandAllocDontCoalesce }; |
| |
| HeapGrowthMode currentHeapGrowthMode; |
| size_t allowAllocatePages; |
| size_t requestedNumPages; |
| |
| class SimpleTestAllocator: public MetaAllocator { |
| public: |
| SimpleTestAllocator(MetaAllocatorTest* parent) |
| : MetaAllocator(32) |
| , m_parent(parent) |
| { |
| addFreshFreeSpace(reinterpret_cast<void*>(basePage * pageSize()), defaultPagesInHeap * pageSize()); |
| } |
| |
| virtual ~SimpleTestAllocator() |
| { |
| EXPECT_TRUE(!m_parent->allocatorDestroyed); |
| m_parent->allocatorDestroyed = true; |
| } |
| |
| virtual FreeSpacePtr allocateNewSpace(size_t& numPages) |
| { |
| switch (m_parent->currentHeapGrowthMode) { |
| case DontGrowHeap: |
| return nullptr; |
| |
| case ForTestDemandAllocCoalesce: |
| case ForTestDemandAllocDontCoalesce: { |
| EXPECT_TRUE(m_parent->allowAllocatePages); |
| EXPECT_TRUE(m_parent->allowAllocatePages >= numPages); |
| m_parent->requestedNumPages = numPages; |
| numPages = m_parent->allowAllocatePages; |
| |
| unsigned offset; |
| if (m_parent->currentHeapGrowthMode == ForTestDemandAllocCoalesce) |
| offset = 0; |
| else |
| offset = 1; |
| |
| void* result = reinterpret_cast<void*>((basePage + defaultPagesInHeap + offset) * pageSize()); |
| |
| m_parent->allowAllocatePages = 0; |
| m_parent->currentHeapGrowthMode = DontGrowHeap; |
| |
| for (size_t counter = 0; counter < numPages + offset; ++counter) { |
| m_parent->pageMap->append(false); |
| for (unsigned byteCounter = 0; byteCounter < pageSize(); ++byteCounter) |
| m_parent->memoryMap->append(false); |
| } |
| |
| m_parent->additionalPagesInHeap += numPages; |
| |
| return FreeSpacePtr(result); |
| } |
| |
| default: |
| CRASH(); |
| return nullptr; |
| } |
| } |
| |
| virtual void notifyNeedPage(void* page, size_t count) |
| { |
| // the page should be both free and unmapped. |
| for (size_t i = 0; i < count; ++i) |
| EXPECT_TRUE(!m_parent->pageState(reinterpret_cast<uintptr_t>(page) / pageSize() + i)); |
| for (uintptr_t address = reinterpret_cast<uintptr_t>(page); address < reinterpret_cast<uintptr_t>(page) + pageSize() * count; ++address) |
| EXPECT_TRUE(!m_parent->byteState(reinterpret_cast<void*>(address))); |
| for (size_t i = 0; i < count; ++i) |
| m_parent->pageState(reinterpret_cast<uintptr_t>(page) / pageSize() + i) = true; |
| } |
| |
| virtual void notifyPageIsFree(void* page, size_t count) |
| { |
| // the page should be free of objects at this point, but it should still |
| // be mapped. |
| for (size_t i = 0; i < count; ++i) |
| EXPECT_TRUE(m_parent->pageState(reinterpret_cast<uintptr_t>(page) / pageSize() + i)); |
| for (uintptr_t address = reinterpret_cast<uintptr_t>(page); address < reinterpret_cast<uintptr_t>(page) + pageSize() * count; ++address) |
| EXPECT_TRUE(!m_parent->byteState(reinterpret_cast<void*>(address))); |
| for (size_t i = 0; i < count; ++i) |
| m_parent->pageState(reinterpret_cast<uintptr_t>(page) / pageSize() + i) = false; |
| } |
| |
| private: |
| MetaAllocatorTest* m_parent; |
| }; |
| |
| static const unsigned basePage = 1; |
| static const unsigned defaultPagesInHeap = 100; |
| |
| unsigned additionalPagesInHeap; |
| |
| Vector<bool, 0>* memoryMap; |
| Vector<bool, 0>* pageMap; |
| bool allocatorDestroyed; |
| |
| SimpleTestAllocator* allocator; |
| |
| virtual void SetUp() |
| { |
| memoryMap = new Vector<bool, 0>(); |
| pageMap = new Vector<bool, 0>(); |
| |
| for (unsigned page = basePage; page < basePage + defaultPagesInHeap; ++page) { |
| pageMap->append(false); |
| for (unsigned byteInPage = 0; byteInPage < pageSize(); ++byteInPage) |
| memoryMap->append(false); |
| } |
| |
| allocatorDestroyed = false; |
| |
| currentHeapGrowthMode = DontGrowHeap; |
| allowAllocatePages = 0; |
| additionalPagesInHeap = 0; |
| requestedNumPages = 0; |
| |
| allocator = new SimpleTestAllocator(this); |
| } |
| |
| virtual void TearDown() |
| { |
| EXPECT_TRUE(currentHeapGrowthMode == DontGrowHeap); |
| EXPECT_EQ(allowAllocatePages, static_cast<size_t>(0)); |
| EXPECT_EQ(requestedNumPages, static_cast<size_t>(0)); |
| |
| // memory should be free. |
| for (unsigned page = basePage; page < basePage + defaultPagesInHeap; ++page) { |
| EXPECT_TRUE(!pageState(page)); |
| for (unsigned byteInPage = 0; byteInPage < pageSize(); ++byteInPage) |
| EXPECT_TRUE(!byteState(page * pageSize() + byteInPage)); |
| } |
| |
| // NOTE: this automatically tests that the allocator did not leak |
| // memory, so long as these tests are running with !defined(NDEBUG). |
| // See MetaAllocator::m_mallocBalance. |
| delete allocator; |
| |
| EXPECT_TRUE(allocatorDestroyed); |
| |
| delete memoryMap; |
| delete pageMap; |
| } |
| |
| MetaAllocatorHandle* allocate(size_t sizeInBytes, SanityCheckMode sanityCheckMode = RunSanityCheck) |
| { |
| MetaAllocatorHandle* handle = allocator->allocate(sizeInBytes, 0).leakRef(); |
| EXPECT_TRUE(handle); |
| EXPECT_EQ(handle->sizeInBytes(), sizeInBytes); |
| |
| uintptr_t startByte = handle->start().untaggedPtr<uintptr_t>(); |
| uintptr_t endByte = handle->end().untaggedPtr<uintptr_t>(); |
| for (uintptr_t currentByte = startByte; currentByte < endByte; ++currentByte) { |
| EXPECT_TRUE(!byteState(currentByte)); |
| byteState(currentByte) = true; |
| EXPECT_TRUE(pageState(currentByte / pageSize())); |
| } |
| |
| if (sanityCheckMode == RunSanityCheck) |
| sanityCheck(); |
| |
| return handle; |
| } |
| |
| void free(MetaAllocatorHandle* handle, SanityCheckMode sanityCheckMode = RunSanityCheck) |
| { |
| EXPECT_TRUE(handle); |
| |
| notifyFree(handle->start().untaggedPtr(), handle->sizeInBytes()); |
| handle->deref(); |
| |
| if (sanityCheckMode == RunSanityCheck) |
| sanityCheck(); |
| } |
| |
| void notifyFree(void* start, size_t sizeInBytes) |
| { |
| uintptr_t startByte = reinterpret_cast<uintptr_t>(start); |
| uintptr_t endByte = startByte + sizeInBytes; |
| for (uintptr_t currentByte = startByte; currentByte < endByte; ++currentByte) { |
| EXPECT_TRUE(byteState(currentByte)); |
| byteState(currentByte) = false; |
| } |
| } |
| |
| void sanityCheck() |
| { |
| #ifndef NDEBUG |
| EXPECT_EQ(allocator->bytesReserved() - allocator->bytesAllocated(), allocator->debugFreeSpaceSize()); |
| #endif |
| EXPECT_EQ(allocator->bytesReserved(), (defaultPagesInHeap + additionalPagesInHeap) * pageSize()); |
| EXPECT_EQ(allocator->bytesAllocated(), bytesAllocated()); |
| EXPECT_EQ(allocator->bytesCommitted(), bytesCommitted()); |
| } |
| |
| void confirm(MetaAllocatorHandle* handle) |
| { |
| uintptr_t startByte = handle->start().untaggedPtr<uintptr_t>(); |
| confirm(startByte, startByte + handle->sizeInBytes(), true); |
| } |
| |
| void confirmHighWatermark(MetaAllocatorHandle* handle) |
| { |
| confirm(handle->end().untaggedPtr<uintptr_t>(), (basePage + defaultPagesInHeap) * pageSize(), false); |
| } |
| |
| void confirm(uintptr_t startByte, uintptr_t endByte, bool value) |
| { |
| for (uintptr_t currentByte = startByte; currentByte < endByte; ++currentByte) { |
| EXPECT_EQ(byteState(currentByte), value); |
| if (value) |
| EXPECT_TRUE(pageState(currentByte / pageSize())); |
| } |
| if (!value) { |
| uintptr_t firstFreePage = (startByte + pageSize() - 1) / pageSize(); |
| uintptr_t lastFreePage = (endByte - pageSize()) / pageSize(); |
| for (uintptr_t currentPage = firstFreePage; currentPage <= lastFreePage; ++currentPage) |
| EXPECT_TRUE(!pageState(currentPage)); |
| } |
| } |
| |
| size_t bytesAllocated() |
| { |
| size_t result = 0; |
| for (unsigned index = 0; index < memoryMap->size(); ++index) { |
| if (memoryMap->at(index)) |
| result++; |
| } |
| return result; |
| } |
| |
| size_t bytesCommitted() |
| { |
| size_t result = 0; |
| for (unsigned index = 0; index < pageMap->size(); ++index) { |
| if (pageMap->at(index)) |
| result++; |
| } |
| return result * pageSize(); |
| } |
| |
| bool& byteState(void* address) |
| { |
| return byteState(reinterpret_cast<uintptr_t>(address)); |
| } |
| |
| bool& byteState(uintptr_t address) |
| { |
| uintptr_t byteIndex = address - basePage * pageSize(); |
| return memoryMap->at(byteIndex); |
| } |
| |
| bool& pageState(uintptr_t page) |
| { |
| uintptr_t pageIndex = page - basePage; |
| return pageMap->at(pageIndex); |
| } |
| |
| // Test helpers |
| |
| void testOneAlloc(size_t size) |
| { |
| // Tests the most basic behavior: allocate one thing and free it. Also |
| // verifies that the state of pages is correct. |
| |
| MetaAllocatorHandle* handle = allocate(size); |
| EXPECT_EQ(handle->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| EXPECT_EQ(handle->sizeInBytes(), size); |
| EXPECT_TRUE(pageState(basePage)); |
| |
| confirm(handle); |
| confirmHighWatermark(handle); |
| |
| free(handle); |
| } |
| |
| void testRepeatAllocFree(size_t firstSize, ...) |
| { |
| // Tests right-coalescing by repeatedly allocating and freeing. The idea |
| // is that if you allocate something and then free it, then the heap should |
| // look identical to what it was before the allocation due to a right-coalesce |
| // of the freed chunk and the already-free memory, and so subsequent |
| // allocations should behave the same as the first one. |
| |
| MetaAllocatorHandle* handle = allocate(firstSize); |
| EXPECT_EQ(handle->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| EXPECT_EQ(handle->sizeInBytes(), firstSize); |
| |
| confirm(handle); |
| confirmHighWatermark(handle); |
| |
| free(handle); |
| |
| va_list argList; |
| va_start(argList, firstSize); |
| while (size_t sizeInBytes = va_arg(argList, int)) { |
| handle = allocate(sizeInBytes); |
| EXPECT_EQ(handle->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| EXPECT_EQ(handle->sizeInBytes(), sizeInBytes); |
| |
| confirm(handle); |
| confirmHighWatermark(handle); |
| |
| free(handle); |
| } |
| va_end(argList); |
| } |
| |
| void testSimpleFullCoalesce(size_t firstSize, size_t secondSize, size_t thirdSize) |
| { |
| // Allocates something of size firstSize, then something of size secondSize, and then |
| // frees the first allocation, and then the second, and then attempts to allocate the |
| // third, asserting that it allocated at the base address of the heap. |
| |
| // Note that this test may cause right-allocation, which will cause the test to fail. |
| // Thus the correct way of running this test is to ensure that secondSize is |
| // picked in such a way that it never straddles a page. |
| |
| MetaAllocatorHandle* firstHandle = allocate(firstSize); |
| EXPECT_EQ(firstHandle->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| EXPECT_EQ(firstHandle->sizeInBytes(), firstSize); |
| |
| confirm(firstHandle); |
| confirmHighWatermark(firstHandle); |
| |
| MetaAllocatorHandle* secondHandle = allocate(secondSize); |
| EXPECT_EQ(secondHandle->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize() + firstSize)); |
| EXPECT_EQ(secondHandle->sizeInBytes(), secondSize); |
| |
| confirm(firstHandle); |
| confirm(secondHandle); |
| confirmHighWatermark(secondHandle); |
| |
| free(firstHandle); |
| |
| confirm(secondHandle); |
| confirmHighWatermark(secondHandle); |
| |
| free(secondHandle); |
| |
| confirm(basePage * pageSize(), (basePage + defaultPagesInHeap) * pageSize(), false); |
| |
| MetaAllocatorHandle* thirdHandle = allocate(thirdSize); |
| EXPECT_EQ(thirdHandle->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| EXPECT_EQ(thirdHandle->sizeInBytes(), thirdSize); |
| |
| confirm(thirdHandle); |
| confirmHighWatermark(thirdHandle); |
| |
| free(thirdHandle); |
| } |
| |
| enum class TestFIFOAllocMode { FillAtEnd, EagerFill }; |
| void testFIFOAlloc(TestFIFOAllocMode mode, ...) |
| { |
| // This will test the simple case of no-coalesce (freeing the left-most |
| // chunk in memory when the chunk to the right of it is allocated) and |
| // fully exercise left-coalescing and full-coalescing. In EagerFill |
| // mode, this also tests perfect-fit allocation and no-coalescing free. |
| |
| size_t totalSize = 0; |
| |
| Vector<MetaAllocatorHandle*, 0> handles; |
| |
| va_list argList; |
| va_start(argList, mode); |
| while (size_t sizeInBytes = va_arg(argList, int)) { |
| MetaAllocatorHandle* handle = allocate(sizeInBytes); |
| EXPECT_EQ(handle->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize() + totalSize)); |
| EXPECT_EQ(handle->sizeInBytes(), sizeInBytes); |
| |
| confirm(handle); |
| confirmHighWatermark(handle); |
| |
| handles.append(handle); |
| totalSize += sizeInBytes; |
| } |
| va_end(argList); |
| |
| for (unsigned index = 0; index < handles.size(); ++index) |
| confirm(handles.at(index)); |
| |
| size_t sizeSoFar = 0; |
| for (unsigned index = 0; index < handles.size(); ++index) { |
| sizeSoFar += handles.at(index)->sizeInBytes(); |
| free(handles.at(index)); |
| if (mode == TestFIFOAllocMode::EagerFill) { |
| MetaAllocatorHandle* handle = allocate(sizeSoFar); |
| EXPECT_EQ(handle->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| EXPECT_EQ(handle->sizeInBytes(), sizeSoFar); |
| |
| confirm(basePage * pageSize(), basePage * pageSize() + totalSize, true); |
| if (index < handles.size() - 1) |
| confirmHighWatermark(handles.last()); |
| else |
| confirmHighWatermark(handle); |
| |
| free(handle); |
| |
| confirm(basePage * pageSize(), basePage * pageSize() + sizeSoFar, false); |
| } |
| } |
| |
| ASSERT(sizeSoFar == totalSize); |
| |
| confirm(basePage * pageSize(), (basePage + defaultPagesInHeap) * pageSize(), false); |
| |
| if (mode == TestFIFOAllocMode::FillAtEnd) { |
| MetaAllocatorHandle* finalHandle = allocate(totalSize); |
| EXPECT_EQ(finalHandle->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| EXPECT_EQ(finalHandle->sizeInBytes(), totalSize); |
| |
| confirm(finalHandle); |
| confirmHighWatermark(finalHandle); |
| |
| free(finalHandle); |
| } |
| } |
| |
| void testFillHeap(size_t sizeInBytes, size_t numAllocations) |
| { |
| Vector<MetaAllocatorHandle*, 0> handles; |
| |
| for (size_t index = 0; index < numAllocations; ++index) |
| handles.append(allocate(sizeInBytes, DontRunSanityCheck)); |
| |
| sanityCheck(); |
| |
| EXPECT_TRUE(!allocator->allocate(sizeInBytes, 0)); |
| |
| for (size_t index = 0; index < numAllocations; ++index) |
| free(handles.at(index), DontRunSanityCheck); |
| |
| sanityCheck(); |
| } |
| |
| void testRightAllocation(size_t firstLeftSize, size_t firstRightSize, size_t secondLeftSize, size_t secondRightSize) |
| { |
| MetaAllocatorHandle* firstLeft = allocate(firstLeftSize); |
| EXPECT_EQ(firstLeft->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| |
| MetaAllocatorHandle* firstRight = allocate(firstRightSize); |
| EXPECT_EQ(firstRight->end().untaggedPtr(), reinterpret_cast<void*>((basePage + defaultPagesInHeap) * pageSize())); |
| |
| MetaAllocatorHandle* secondLeft = allocate(secondLeftSize); |
| EXPECT_EQ(secondLeft->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize() + firstLeft->sizeInBytes())); |
| |
| MetaAllocatorHandle* secondRight = allocate(secondRightSize); |
| EXPECT_EQ(secondRight->end().untaggedPtr(), reinterpret_cast<void*>((basePage + defaultPagesInHeap) * pageSize() - firstRight->sizeInBytes())); |
| |
| free(firstLeft); |
| free(firstRight); |
| free(secondLeft); |
| free(secondRight); |
| |
| MetaAllocatorHandle* final = allocate(defaultPagesInHeap * pageSize()); |
| EXPECT_EQ(final->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| |
| free(final); |
| } |
| |
| void testBestFit(size_t firstSize, size_t step, unsigned numSlots, SanityCheckMode sanityCheckMode) |
| { |
| Vector<MetaAllocatorHandle*, 0> handlesToFree; |
| Vector<MetaAllocatorHandle*, 0> handles; |
| Vector<void*, 0> locations; |
| |
| size_t size = firstSize; |
| for (unsigned index = 0; index < numSlots; ++index) { |
| MetaAllocatorHandle* toFree = allocate(size, sanityCheckMode); |
| if (!handles.isEmpty()) { |
| while (toFree->start().untaggedPtr() != handles.last()->end().untaggedPtr()) { |
| handlesToFree.append(toFree); |
| toFree = allocate(size, sanityCheckMode); |
| } |
| } |
| |
| MetaAllocatorHandle* fragger = allocate(32, sanityCheckMode); |
| EXPECT_EQ(fragger->start().untaggedPtr(), toFree->end().untaggedPtr()); |
| |
| locations.append(toFree->start().untaggedPtr()); |
| |
| handlesToFree.append(toFree); |
| handles.append(fragger); |
| |
| size += step; |
| } |
| |
| ASSERT(locations.size() == numSlots); |
| |
| for (unsigned index = 0; index < handlesToFree.size(); ++index) |
| free(handlesToFree.at(index), sanityCheckMode); |
| |
| size = firstSize; |
| for (unsigned index = 0; index < numSlots; ++index) { |
| MetaAllocatorHandle* bestFit = allocate(size - 32, sanityCheckMode); |
| |
| EXPECT_TRUE(bestFit->start().untaggedPtr() == locations.at(index) |
| || bestFit->end().untaggedPtr() == reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(locations.at(index)) + size)); |
| |
| MetaAllocatorHandle* small = allocate(32, sanityCheckMode); |
| if (bestFit->start().untaggedPtr() == locations.at(index)) |
| EXPECT_EQ(small->start().untaggedPtr(), bestFit->end().untaggedPtr()); |
| else |
| EXPECT_EQ(small->end().untaggedPtr(), bestFit->start().untaggedPtr()); |
| |
| free(bestFit, sanityCheckMode); |
| free(small, sanityCheckMode); |
| |
| size += step; |
| } |
| |
| for (unsigned index = 0; index < numSlots; ++index) |
| free(handles.at(index), sanityCheckMode); |
| |
| MetaAllocatorHandle* final = allocate(defaultPagesInHeap * pageSize(), sanityCheckMode); |
| EXPECT_EQ(final->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| |
| free(final, sanityCheckMode); |
| } |
| |
| void testShrink(size_t firstSize, size_t secondSize) |
| { |
| // Allocate the thing that will be shrunk |
| MetaAllocatorHandle* handle = allocate(firstSize); |
| |
| // Shrink it, and make sure that our state reflects the shrinkage. |
| notifyFree(reinterpret_cast<void*>(handle->start().untaggedPtr<uintptr_t>() + secondSize), firstSize - secondSize); |
| |
| handle->shrink(secondSize); |
| EXPECT_EQ(handle->sizeInBytes(), secondSize); |
| |
| sanityCheck(); |
| |
| // Assert that the heap is not empty. |
| EXPECT_TRUE(!allocator->allocate(defaultPagesInHeap * pageSize(), 0)); |
| |
| // Allocate the remainder of the heap. |
| MetaAllocatorHandle* remainder = allocate(defaultPagesInHeap * pageSize() - secondSize); |
| EXPECT_EQ(remainder->start().untaggedPtr(), handle->end().untaggedPtr()); |
| |
| free(remainder); |
| free(handle); |
| |
| // Assert that the heap is empty and finish up. |
| MetaAllocatorHandle* final = allocate(defaultPagesInHeap * pageSize()); |
| EXPECT_EQ(final->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| |
| free(final); |
| } |
| |
| void testDemandAllocCoalesce(size_t firstSize, size_t numPages, size_t secondSize) |
| { |
| EXPECT_TRUE(!allocator->allocate((defaultPagesInHeap + numPages) * pageSize(), 0)); |
| |
| MetaAllocatorHandle* firstHandle = allocate(firstSize); |
| |
| EXPECT_TRUE(!allocator->allocate(secondSize, 0)); |
| EXPECT_TRUE(!allocator->allocate((defaultPagesInHeap + numPages) * pageSize(), 0)); |
| |
| currentHeapGrowthMode = ForTestDemandAllocCoalesce; |
| allowAllocatePages = numPages; |
| |
| MetaAllocatorHandle* secondHandle = allocate(secondSize); |
| |
| EXPECT_TRUE(currentHeapGrowthMode == DontGrowHeap); |
| EXPECT_EQ(allowAllocatePages, static_cast<size_t>(0)); |
| EXPECT_EQ(requestedNumPages, (secondSize + pageSize() - 1) / pageSize()); |
| EXPECT_EQ(secondHandle->start().untaggedPtr(), reinterpret_cast<void*>((basePage + defaultPagesInHeap) * pageSize())); |
| |
| requestedNumPages = 0; |
| |
| free(firstHandle); |
| free(secondHandle); |
| |
| free(allocate((defaultPagesInHeap + numPages) * pageSize())); |
| } |
| |
| void testDemandAllocDontCoalesce(size_t firstSize, size_t numPages, size_t secondSize) |
| { |
| free(allocate(firstSize)); |
| free(allocate(defaultPagesInHeap * pageSize())); |
| EXPECT_TRUE(!allocator->allocate((defaultPagesInHeap + numPages) * pageSize(), 0)); |
| |
| MetaAllocatorHandle* firstHandle = allocate(firstSize); |
| |
| EXPECT_TRUE(!allocator->allocate(secondSize, 0)); |
| EXPECT_TRUE(!allocator->allocate((defaultPagesInHeap + numPages) * pageSize(), 0)); |
| |
| currentHeapGrowthMode = ForTestDemandAllocDontCoalesce; |
| allowAllocatePages = numPages; |
| |
| MetaAllocatorHandle* secondHandle = allocate(secondSize); |
| |
| EXPECT_TRUE(currentHeapGrowthMode == DontGrowHeap); |
| EXPECT_EQ(allowAllocatePages, static_cast<size_t>(0)); |
| EXPECT_EQ(requestedNumPages, (secondSize + pageSize() - 1) / pageSize()); |
| EXPECT_EQ(secondHandle->start().untaggedPtr(), reinterpret_cast<void*>((basePage + defaultPagesInHeap + 1) * pageSize())); |
| |
| requestedNumPages = 0; |
| |
| EXPECT_TRUE(!allocator->allocate((defaultPagesInHeap + numPages) * pageSize(), 0)); |
| |
| free(firstHandle); |
| free(secondHandle); |
| |
| EXPECT_TRUE(!allocator->allocate((defaultPagesInHeap + numPages) * pageSize(), 0)); |
| |
| firstHandle = allocate(firstSize); |
| secondHandle = allocate(secondSize); |
| EXPECT_EQ(firstHandle->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| EXPECT_EQ(secondHandle->start().untaggedPtr(), reinterpret_cast<void*>((basePage + defaultPagesInHeap + 1) * pageSize())); |
| free(firstHandle); |
| free(secondHandle); |
| } |
| }; |
| |
| TEST_F(MetaAllocatorTest, Empty) |
| { |
| // Tests that creating and destroying an allocator works. |
| } |
| |
| TEST_F(MetaAllocatorTest, AllocZero) |
| { |
| // Tests that allocating a zero-length block returns 0 and |
| // does not change anything in memory. |
| |
| ASSERT(!allocator->allocate(0, 0)); |
| |
| MetaAllocatorHandle* final = allocate(defaultPagesInHeap * pageSize()); |
| EXPECT_EQ(final->start().untaggedPtr(), reinterpret_cast<void*>(basePage * pageSize())); |
| free(final); |
| } |
| |
| TEST_F(MetaAllocatorTest, OneAlloc32) |
| { |
| testOneAlloc(32); |
| } |
| |
| TEST_F(MetaAllocatorTest, OneAlloc64) |
| { |
| testOneAlloc(64); |
| } |
| |
| TEST_F(MetaAllocatorTest, OneAllocTwoPages) |
| { |
| testOneAlloc(pageSize() * 2); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFree32Twice) |
| { |
| testRepeatAllocFree(32, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFree32Then64) |
| { |
| testRepeatAllocFree(32, 64, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFree64Then32) |
| { |
| testRepeatAllocFree(64, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFree32TwiceThen64) |
| { |
| testRepeatAllocFree(32, 32, 64, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFree32Then64Twice) |
| { |
| testRepeatAllocFree(32, 64, 64, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFree64Then32Then64) |
| { |
| testRepeatAllocFree(64, 32, 64, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFree32Thrice) |
| { |
| testRepeatAllocFree(32, 32, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFree32Then64Then32) |
| { |
| testRepeatAllocFree(32, 32, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFree64Then32Twice) |
| { |
| testRepeatAllocFree(64, 32, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFreeTwoPagesThen32) |
| { |
| testRepeatAllocFree(static_cast<int>(pageSize() * 2), 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFree32ThenTwoPages) |
| { |
| testRepeatAllocFree(32, static_cast<int>(pageSize() * 2), 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFreePageThenTwoPages) |
| { |
| testRepeatAllocFree(static_cast<int>(pageSize()), static_cast<int>(pageSize() * 2), 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, RepeatAllocFreeTwoPagesThenPage) |
| { |
| testRepeatAllocFree(static_cast<int>(pageSize() * 2), static_cast<int>(pageSize()), 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, SimpleFullCoalesce32Plus32Then128) |
| { |
| testSimpleFullCoalesce(32, 32, 128); |
| } |
| |
| TEST_F(MetaAllocatorTest, SimpleFullCoalesce32Plus64Then128) |
| { |
| testSimpleFullCoalesce(32, 64, 128); |
| } |
| |
| TEST_F(MetaAllocatorTest, SimpleFullCoalesce64Plus32Then128) |
| { |
| testSimpleFullCoalesce(64, 32, 128); |
| } |
| |
| TEST_F(MetaAllocatorTest, SimpleFullCoalesce32PlusPageLess32ThenPage) |
| { |
| testSimpleFullCoalesce(32, pageSize() - 32, pageSize()); |
| } |
| |
| TEST_F(MetaAllocatorTest, SimpleFullCoalesce32PlusPageLess32ThenTwoPages) |
| { |
| testSimpleFullCoalesce(32, pageSize() - 32, pageSize() * 2); |
| } |
| |
| TEST_F(MetaAllocatorTest, SimpleFullCoalescePagePlus32ThenTwoPages) |
| { |
| testSimpleFullCoalesce(pageSize(), 32, pageSize() * 2); |
| } |
| |
| TEST_F(MetaAllocatorTest, SimpleFullCoalescePagePlusPageThenTwoPages) |
| { |
| testSimpleFullCoalesce(pageSize(), pageSize(), pageSize() * 2); |
| } |
| |
| TEST_F(MetaAllocatorTest, FIFOAllocFillAtEnd32Twice) |
| { |
| testFIFOAlloc(TestFIFOAllocMode::FillAtEnd, 32, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, FIFOAllocFillAtEnd32Thrice) |
| { |
| testFIFOAlloc(TestFIFOAllocMode::FillAtEnd, 32, 32, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, FIFOAllocFillAtEnd32FourTimes) |
| { |
| testFIFOAlloc(TestFIFOAllocMode::FillAtEnd, 32, 32, 32, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, FIFOAllocFillAtEndPageLess32Then32ThenPageLess64Then64) |
| { |
| testFIFOAlloc(TestFIFOAllocMode::FillAtEnd, static_cast<int>(pageSize() - 32), 32, static_cast<int>(pageSize() - 64), 64, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, FIFOAllocEagerFill32Twice) |
| { |
| testFIFOAlloc(TestFIFOAllocMode::EagerFill, 32, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, FIFOAllocEagerFill32Thrice) |
| { |
| testFIFOAlloc(TestFIFOAllocMode::EagerFill, 32, 32, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, FIFOAllocEagerFill32FourTimes) |
| { |
| testFIFOAlloc(TestFIFOAllocMode::EagerFill, 32, 32, 32, 32, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, FIFOAllocEagerFillPageLess32Then32ThenPageLess64Then64) |
| { |
| testFIFOAlloc(TestFIFOAllocMode::EagerFill, static_cast<int>(pageSize() - 32), 32, static_cast<int>(pageSize() - 64), 64, 0); |
| } |
| |
| TEST_F(MetaAllocatorTest, FillHeap32) |
| { |
| testFillHeap(32, defaultPagesInHeap * pageSize() / 32); |
| } |
| |
| TEST_F(MetaAllocatorTest, FillHeapPage) |
| { |
| testFillHeap(pageSize(), defaultPagesInHeap); |
| } |
| |
| TEST_F(MetaAllocatorTest, FillHeapTwoPages) |
| { |
| testFillHeap(pageSize() * 2, defaultPagesInHeap / 2); |
| } |
| |
| TEST_F(MetaAllocatorTest, RightAllocation32ThenPageThen32ThenPage) |
| { |
| testRightAllocation(32, pageSize(), 32, pageSize()); |
| } |
| |
| TEST_F(MetaAllocatorTest, RightAllocationQuarterPageThenPageThenQuarterPageThenPage) |
| { |
| testRightAllocation(pageSize() / 4, pageSize(), pageSize() / 4, pageSize()); |
| } |
| |
| TEST_F(MetaAllocatorTest, BestFit64Plus64Thrice) |
| { |
| testBestFit(64, 64, 3, RunSanityCheck); |
| } |
| |
| TEST_F(MetaAllocatorTest, BestFit64Plus64TenTimes) |
| { |
| testBestFit(64, 64, 10, DontRunSanityCheck); |
| } |
| |
| TEST_F(MetaAllocatorTest, BestFit64Plus64HundredTimes) |
| { |
| testBestFit(64, 64, 100, DontRunSanityCheck); |
| } |
| |
| TEST_F(MetaAllocatorTest, BestFit96Plus64Thrice) |
| { |
| testBestFit(96, 64, 3, RunSanityCheck); |
| } |
| |
| TEST_F(MetaAllocatorTest, BestFit96Plus64TenTimes) |
| { |
| testBestFit(96, 64, 10, DontRunSanityCheck); |
| } |
| |
| TEST_F(MetaAllocatorTest, BestFit96Plus64HundredTimes) |
| { |
| testBestFit(96, 64, 100, DontRunSanityCheck); |
| } |
| |
| TEST_F(MetaAllocatorTest, BestFit96Plus96Thrice) |
| { |
| testBestFit(96, 96, 3, RunSanityCheck); |
| } |
| |
| TEST_F(MetaAllocatorTest, BestFit96Plus96TenTimes) |
| { |
| testBestFit(96, 96, 10, DontRunSanityCheck); |
| } |
| |
| TEST_F(MetaAllocatorTest, BestFit96Plus96EightyTimes) |
| { |
| testBestFit(96, 96, 80, DontRunSanityCheck); |
| } |
| |
| TEST_F(MetaAllocatorTest, Shrink64To32) |
| { |
| testShrink(64, 32); |
| } |
| |
| TEST_F(MetaAllocatorTest, ShrinkPageTo32) |
| { |
| testShrink(pageSize(), 32); |
| } |
| |
| TEST_F(MetaAllocatorTest, ShrinkPageToPageLess32) |
| { |
| testShrink(pageSize(), pageSize() - 32); |
| } |
| |
| TEST_F(MetaAllocatorTest, ShrinkTwoPagesTo32) |
| { |
| testShrink(pageSize() * 2, 32); |
| } |
| |
| TEST_F(MetaAllocatorTest, ShrinkTwoPagesToPagePlus32) |
| { |
| testShrink(pageSize() * 2, pageSize() + 32); |
| } |
| |
| TEST_F(MetaAllocatorTest, ShrinkTwoPagesToPage) |
| { |
| testShrink(pageSize() * 2, pageSize()); |
| } |
| |
| TEST_F(MetaAllocatorTest, ShrinkTwoPagesToPageLess32) |
| { |
| testShrink(pageSize() * 2, pageSize() - 32); |
| } |
| |
| TEST_F(MetaAllocatorTest, ShrinkTwoPagesToTwoPagesLess32) |
| { |
| testShrink(pageSize() * 2, pageSize() * 2 - 32); |
| } |
| |
| TEST_F(MetaAllocatorTest, DemandAllocCoalescePageThenDoubleHeap) |
| { |
| testDemandAllocCoalesce(pageSize(), defaultPagesInHeap, defaultPagesInHeap * pageSize()); |
| } |
| |
| TEST_F(MetaAllocatorTest, DemandAllocCoalescePageThenTripleHeap) |
| { |
| testDemandAllocCoalesce(pageSize(), defaultPagesInHeap * 2, defaultPagesInHeap * pageSize()); |
| } |
| |
| TEST_F(MetaAllocatorTest, DemandAllocDontCoalescePageThenDoubleHeap) |
| { |
| testDemandAllocDontCoalesce(pageSize(), defaultPagesInHeap, defaultPagesInHeap * pageSize()); |
| } |
| |
| } // namespace TestWebKitAPI |
| |
| #if USE(POINTER_PROFILING) |
| |
| namespace WTF { |
| |
| const char* tagForPtr(const void*) { return "<unknown>"; } |
| const char* ptrTagName(PtrTag) { return "<unknown>"; } |
| |
| } // namespace WTF |
| |
| #endif // USE(POINTER_PROFILING) |
