| // Copyright 2019 The Dawn & Tint Authors | |
| // | |
| // 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 the copyright holder 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 THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT HOLDER OR 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 <vector> | |
| #include "dawn/native/BuddyAllocator.h" | |
| #include "gtest/gtest.h" | |
| namespace dawn::native { | |
| constexpr uint64_t BuddyAllocator::kInvalidOffset; | |
| // Verify the buddy allocator with a basic test. | |
| TEST(BuddyAllocatorTests, SingleBlock) { | |
| // After one 32 byte allocation: | |
| // | |
| // Level -------------------------------- | |
| // 0 32 | A | | |
| // -------------------------------- | |
| // | |
| constexpr uint64_t maxBlockSize = 32; | |
| BuddyAllocator allocator(maxBlockSize); | |
| // Check that we cannot allocate a oversized block. | |
| ASSERT_EQ(allocator.Allocate(maxBlockSize * 2), BuddyAllocator::kInvalidOffset); | |
| // Check that we cannot allocate a zero sized block. | |
| ASSERT_EQ(allocator.Allocate(0u), BuddyAllocator::kInvalidOffset); | |
| // Allocate the block. | |
| uint64_t blockOffset = allocator.Allocate(maxBlockSize); | |
| ASSERT_EQ(blockOffset, 0u); | |
| // Check that we are full. | |
| ASSERT_EQ(allocator.Allocate(maxBlockSize), BuddyAllocator::kInvalidOffset); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 0u); | |
| // Deallocate the block. | |
| allocator.Deallocate(blockOffset); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| } | |
| // Verify multiple allocations succeeds using a buddy allocator. | |
| TEST(BuddyAllocatorTests, MultipleBlocks) { | |
| // Fill every level in the allocator (order-n = 2^n) | |
| const uint64_t maxBlockSize = (1ull << 16); | |
| for (uint64_t order = 1; (1ull << order) <= maxBlockSize; order++) { | |
| BuddyAllocator allocator(maxBlockSize); | |
| uint64_t blockSize = (1ull << order); | |
| for (uint32_t blocki = 0; blocki < (maxBlockSize / blockSize); blocki++) { | |
| ASSERT_EQ(allocator.Allocate(blockSize), blockSize * blocki); | |
| } | |
| } | |
| } | |
| // Verify that a single allocation succeeds using a buddy allocator. | |
| TEST(BuddyAllocatorTests, SingleSplitBlock) { | |
| // After one 8 byte allocation: | |
| // | |
| // Level -------------------------------- | |
| // 0 32 | S | | |
| // -------------------------------- | |
| // 1 16 | S | F | S - split | |
| // -------------------------------- F - free | |
| // 2 8 | A | F | | | A - allocated | |
| // -------------------------------- | |
| // | |
| constexpr uint64_t maxBlockSize = 32; | |
| BuddyAllocator allocator(maxBlockSize); | |
| // Allocate block (splits two blocks). | |
| uint64_t blockOffset = allocator.Allocate(8); | |
| ASSERT_EQ(blockOffset, 0u); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u); | |
| // Deallocate block (merges two blocks). | |
| allocator.Deallocate(blockOffset); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| // Check that we cannot allocate a block that is oversized. | |
| ASSERT_EQ(allocator.Allocate(maxBlockSize * 2), BuddyAllocator::kInvalidOffset); | |
| // Re-allocate the largest block allowed after merging. | |
| blockOffset = allocator.Allocate(maxBlockSize); | |
| ASSERT_EQ(blockOffset, 0u); | |
| allocator.Deallocate(blockOffset); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| } | |
| // Verify that a multiple allocated blocks can be removed in the free-list. | |
| TEST(BuddyAllocatorTests, MultipleSplitBlocks) { | |
| // After four 16 byte allocations: | |
| // | |
| // Level -------------------------------- | |
| // 0 32 | S | | |
| // -------------------------------- | |
| // 1 16 | S | S | S - split | |
| // -------------------------------- F - free | |
| // 2 8 | Aa | Ab | Ac | Ad | A - allocated | |
| // -------------------------------- | |
| // | |
| constexpr uint64_t maxBlockSize = 32; | |
| BuddyAllocator allocator(maxBlockSize); | |
| // Populates the free-list with four blocks at Level2. | |
| // Allocate "a" block (two splits). | |
| constexpr uint64_t blockSizeInBytes = 8; | |
| uint64_t blockOffsetA = allocator.Allocate(blockSizeInBytes); | |
| ASSERT_EQ(blockOffsetA, 0u); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u); | |
| // Allocate "b" block. | |
| uint64_t blockOffsetB = allocator.Allocate(blockSizeInBytes); | |
| ASSERT_EQ(blockOffsetB, blockSizeInBytes); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| // Allocate "c" block (three splits). | |
| uint64_t blockOffsetC = allocator.Allocate(blockSizeInBytes); | |
| ASSERT_EQ(blockOffsetC, blockOffsetB + blockSizeInBytes); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| // Allocate "d" block. | |
| uint64_t blockOffsetD = allocator.Allocate(blockSizeInBytes); | |
| ASSERT_EQ(blockOffsetD, blockOffsetC + blockSizeInBytes); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 0u); | |
| // Deallocate "d" block. | |
| // FreeList[Level2] = [BlockD] -> x | |
| allocator.Deallocate(blockOffsetD); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| // Deallocate "b" block. | |
| // FreeList[Level2] = [BlockB] -> [BlockD] -> x | |
| allocator.Deallocate(blockOffsetB); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u); | |
| // Deallocate "c" block (one merges). | |
| // FreeList[Level1] = [BlockCD] -> x | |
| // FreeList[Level2] = [BlockB] -> x | |
| allocator.Deallocate(blockOffsetC); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u); | |
| // Deallocate "a" block (two merges). | |
| // FreeList[Level0] = [BlockABCD] -> x | |
| allocator.Deallocate(blockOffsetA); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| } | |
| // Verify the buddy allocator can handle allocations of various sizes. | |
| TEST(BuddyAllocatorTests, MultipleSplitBlockIncreasingSize) { | |
| // After four Level4-to-Level1 byte then one L4 block allocations: | |
| // | |
| // Level ----------------------------------------------------------------- | |
| // 0 512 | S | | |
| // ----------------------------------------------------------------- | |
| // 1 256 | S | A | | |
| // ----------------------------------------------------------------- | |
| // 2 128 | S | A | | | | |
| // ----------------------------------------------------------------- | |
| // 3 64 | S | A | | | | | | | | |
| // ----------------------------------------------------------------- | |
| // 4 32 | A | F | | | | | | | | | | | | | | | | |
| // ----------------------------------------------------------------- | |
| // | |
| constexpr uint64_t maxBlockSize = 512; | |
| BuddyAllocator allocator(maxBlockSize); | |
| ASSERT_EQ(allocator.Allocate(32), 0ull); | |
| ASSERT_EQ(allocator.Allocate(64), 64ull); | |
| ASSERT_EQ(allocator.Allocate(128), 128ull); | |
| ASSERT_EQ(allocator.Allocate(256), 256ull); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| // Fill in the last free block. | |
| ASSERT_EQ(allocator.Allocate(32), 32ull); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 0u); | |
| // Check if we're full. | |
| ASSERT_EQ(allocator.Allocate(32), BuddyAllocator::kInvalidOffset); | |
| } | |
| // Verify very small allocations using a larger allocator works correctly. | |
| TEST(BuddyAllocatorTests, MultipleSplitBlocksVariableSizes) { | |
| // After allocating four pairs of one 64 byte block and one 32 byte block. | |
| // | |
| // Level ----------------------------------------------------------------- | |
| // 0 512 | S | | |
| // ----------------------------------------------------------------- | |
| // 1 256 | S | S | | |
| // ----------------------------------------------------------------- | |
| // 2 128 | S | S | S | F | | |
| // ----------------------------------------------------------------- | |
| // 3 64 | A | S | A | A | S | A | | | | |
| // ----------------------------------------------------------------- | |
| // 4 32 | | | A | A | | | | | A | A | | | | | | | | |
| // ----------------------------------------------------------------- | |
| // | |
| constexpr uint64_t maxBlockSize = 512; | |
| BuddyAllocator allocator(maxBlockSize); | |
| ASSERT_EQ(allocator.Allocate(64), 0ull); | |
| ASSERT_EQ(allocator.Allocate(32), 64ull); | |
| ASSERT_EQ(allocator.Allocate(64), 128ull); | |
| ASSERT_EQ(allocator.Allocate(32), 96ull); | |
| ASSERT_EQ(allocator.Allocate(64), 192ull); | |
| ASSERT_EQ(allocator.Allocate(32), 256ull); | |
| ASSERT_EQ(allocator.Allocate(64), 320ull); | |
| ASSERT_EQ(allocator.Allocate(32), 288ull); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| } | |
| // Verify the buddy allocator can deal with bad fragmentation. | |
| TEST(BuddyAllocatorTests, MultipleSplitBlocksInterleaved) { | |
| // Allocate every leaf then de-allocate every other of those allocations. | |
| // | |
| // Level ----------------------------------------------------------------- | |
| // 0 512 | S | | |
| // ----------------------------------------------------------------- | |
| // 1 256 | S | S | | |
| // ----------------------------------------------------------------- | |
| // 2 128 | S | S | S | S | | |
| // ----------------------------------------------------------------- | |
| // 3 64 | S | S | S | S | S | S | S | S | | |
| // ----------------------------------------------------------------- | |
| // 4 32 | A | F | A | F | A | F | A | F | A | F | A | F | A | F | A | F | | |
| // ----------------------------------------------------------------- | |
| // | |
| constexpr uint64_t maxBlockSize = 512; | |
| BuddyAllocator allocator(maxBlockSize); | |
| // Allocate leaf blocks | |
| constexpr uint64_t minBlockSizeInBytes = 32; | |
| std::vector<uint64_t> blockOffsets; | |
| for (uint64_t i = 0; i < maxBlockSize / minBlockSizeInBytes; i++) { | |
| blockOffsets.push_back(allocator.Allocate(minBlockSizeInBytes)); | |
| } | |
| // Free every other leaf block. | |
| for (size_t count = 1; count < blockOffsets.size(); count += 2) { | |
| allocator.Deallocate(blockOffsets[count]); | |
| } | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 8u); | |
| } | |
| // Verify the buddy allocator can deal with multiple allocations with mixed alignments. | |
| TEST(BuddyAllocatorTests, SameSizeVariousAlignment) { | |
| // After two 8 byte allocations with 16 byte alignment then one 8 byte allocation with 8 | |
| // byte alignment. | |
| // | |
| // Level -------------------------------- | |
| // 0 32 | S | | |
| // -------------------------------- | |
| // 1 16 | S | S | S - split | |
| // -------------------------------- F - free | |
| // 2 8 | Aa | F | Ab | Ac | A - allocated | |
| // -------------------------------- | |
| // | |
| BuddyAllocator allocator(32); | |
| // Allocate Aa (two splits). | |
| ASSERT_EQ(allocator.Allocate(8, 16), 0u); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u); | |
| // Allocate Ab (skip Aa buddy due to alignment and perform another split). | |
| ASSERT_EQ(allocator.Allocate(8, 16), 16u); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u); | |
| // Check that we cannot fit another. | |
| ASSERT_EQ(allocator.Allocate(8, 16), BuddyAllocator::kInvalidOffset); | |
| // Allocate Ac (zero splits and Ab's buddy is now the first free block). | |
| ASSERT_EQ(allocator.Allocate(8, 8), 24u); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| } | |
| // Verify the buddy allocator can deal with multiple allocations with equal alignments. | |
| TEST(BuddyAllocatorTests, VariousSizeSameAlignment) { | |
| // After two 8 byte allocations with 4 byte alignment then one 16 byte allocation with 4 | |
| // byte alignment. | |
| // | |
| // Level -------------------------------- | |
| // 0 32 | S | | |
| // -------------------------------- | |
| // 1 16 | S | Ac | S - split | |
| // -------------------------------- F - free | |
| // 2 8 | Aa | Ab | | A - allocated | |
| // -------------------------------- | |
| // | |
| constexpr uint64_t maxBlockSize = 32; | |
| constexpr uint64_t alignment = 4; | |
| BuddyAllocator allocator(maxBlockSize); | |
| // Allocate block Aa (two splits) | |
| ASSERT_EQ(allocator.Allocate(8, alignment), 0u); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 2u); | |
| // Allocate block Ab (Aa's buddy) | |
| ASSERT_EQ(allocator.Allocate(8, alignment), 8u); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 1u); | |
| // Check that we can still allocate Ac. | |
| ASSERT_EQ(allocator.Allocate(16, alignment), 16ull); | |
| ASSERT_EQ(allocator.ComputeTotalNumOfFreeBlocksForTesting(), 0u); | |
| } | |
| } // namespace dawn::native |