src/dawn/native/BuddyAllocator.cpp - dawn - Git at Google

 // 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 "dawn/native/BuddyAllocator.h"

 #include "dawn/common/Assert.h"
 #include "dawn/common/Math.h"

 namespace dawn::native {

 BuddyAllocator::BuddyAllocator(uint64_t maxSize) : mMaxBlockSize(maxSize) {
     DAWN_ASSERT(IsPowerOfTwo(maxSize));

     mFreeLists.resize(Log2(mMaxBlockSize) + 1);

     // Insert the level0 free block.
     mRoot = new BuddyBlock(maxSize, /*offset*/ 0);
     mFreeLists[0] = {mRoot};
 }

 BuddyAllocator::~BuddyAllocator() {
     if (mRoot) {
         mFreeLists.clear();

         DeleteBlock(mRoot.ExtractAsDangling());
     }
 }

 uint64_t BuddyAllocator::ComputeTotalNumOfFreeBlocksForTesting() const {
     return ComputeNumOfFreeBlocks(mRoot);
 }

 uint64_t BuddyAllocator::ComputeNumOfFreeBlocks(BuddyBlock* block) const {
     if (block->mState == BlockState::Free) {
         return 1;
     } else if (block->mState == BlockState::Split) {
         return ComputeNumOfFreeBlocks(block->split.pLeft) +
                ComputeNumOfFreeBlocks(block->split.pLeft->pBuddy);
     }
     return 0;
 }

 uint32_t BuddyAllocator::ComputeLevelFromBlockSize(uint64_t blockSize) const {
     // Every level in the buddy system can be indexed by order-n where n = log2(blockSize).
     // However, mFreeList zero-indexed by level.
     // For example, blockSize=4 is Level1 if MAX_BLOCK is 8.
     return Log2(mMaxBlockSize) - Log2(blockSize);
 }

 uint64_t BuddyAllocator::GetNextFreeAlignedBlock(size_t allocationBlockLevel,
                                                  uint64_t alignment) const {
     DAWN_ASSERT(IsPowerOfTwo(alignment));
     // The current level is the level that corresponds to the allocation size. The free list may
     // not contain a block at that level until a larger one gets allocated (and splits).
     // Continue to go up the tree until such a larger block exists.
     //
     // Even if the block exists at the level, it cannot be used if it's offset is unaligned.
     // When the alignment is also a power-of-two, we simply use the next free block whose size
     // is greater than or equal to the alignment value.
     //
     //  After one 8-byte allocation:
     //
     //  Level          --------------------------------
     //      0       32 |               S              |
     //                 --------------------------------
     //      1       16 |       S       |       F2     |       S - split
     //                 --------------------------------       F - free
     //      2       8  |   Aa  |   F1  |              |       A - allocated
     //                 --------------------------------
     //
     //  Allocate(size=8, alignment=8) will be satisfied by using F1.
     //  Allocate(size=8, alignment=4) will be satified by using F1.
     //  Allocate(size=8, alignment=16) will be satisified by using F2.
     //
     for (size_t ii = 0; ii <= allocationBlockLevel; ++ii) {
         size_t currLevel = allocationBlockLevel - ii;
         BuddyBlock* freeBlock = mFreeLists[currLevel].head;
         if (freeBlock && (freeBlock->mOffset % alignment == 0)) {
             return currLevel;
         }
     }
     return kInvalidOffset;  // No free block exists at any level.
 }

 // Inserts existing free block into the free-list.
 // Called by allocate upon splitting to insert a child block into a free-list.
 // Note: Always insert into the head of the free-list. As when a larger free block at a lower
 // level was split, there were no smaller free blocks at a higher level to allocate.
 void BuddyAllocator::InsertFreeBlock(BuddyBlock* block, size_t level) {
     DAWN_ASSERT(block->mState == BlockState::Free);

     // Inserted block is now the front (no prev).
     block->free.pPrev = nullptr;

     // Old head is now the inserted block's next.
     block->free.pNext = mFreeLists[level].head;

     // Block already in HEAD position (ex. right child was inserted first).
     if (mFreeLists[level].head != nullptr) {
         // Old head's previous is the inserted block.
         mFreeLists[level].head->free.pPrev = block;
     }

     mFreeLists[level].head = block;
 }

 void BuddyAllocator::RemoveFreeBlock(BuddyBlock* block, size_t level) {
     DAWN_ASSERT(block->mState == BlockState::Free);

     if (mFreeLists[level].head == block) {
         // Block is in HEAD position.
         mFreeLists[level].head = mFreeLists[level].head->free.pNext;
     } else {
         // Block is after HEAD position.
         BuddyBlock* pPrev = block->free.pPrev;
         BuddyBlock* pNext = block->free.pNext;

         DAWN_ASSERT(pPrev != nullptr);
         DAWN_ASSERT(pPrev->mState == BlockState::Free);

         pPrev->free.pNext = pNext;

         if (pNext != nullptr) {
             DAWN_ASSERT(pNext->mState == BlockState::Free);
             pNext->free.pPrev = pPrev;
         }
     }
 }

 uint64_t BuddyAllocator::Allocate(uint64_t allocationSize, uint64_t alignment) {
     if (allocationSize == 0 || allocationSize > mMaxBlockSize) {
         return kInvalidOffset;
     }

     // Compute the level
     const uint32_t allocationSizeToLevel = ComputeLevelFromBlockSize(allocationSize);

     DAWN_ASSERT(allocationSizeToLevel < mFreeLists.size());

     uint64_t currBlockLevel = GetNextFreeAlignedBlock(allocationSizeToLevel, alignment);

     // Error when no free blocks exist (allocator is full)
     if (currBlockLevel == kInvalidOffset) {
         return kInvalidOffset;
     }

     // Split free blocks level-by-level.
     // Terminate when the current block level is equal to the computed level of the requested
     // allocation.
     BuddyBlock* currBlock = mFreeLists[currBlockLevel].head;

     for (; currBlockLevel < allocationSizeToLevel; currBlockLevel++) {
         DAWN_ASSERT(currBlock->mState == BlockState::Free);

         // Remove curr block (about to be split).
         RemoveFreeBlock(currBlock, currBlockLevel);

         // Create two free child blocks (the buddies).
         const uint64_t nextLevelSize = currBlock->mSize / 2;
         BuddyBlock* leftChildBlock = new BuddyBlock(nextLevelSize, currBlock->mOffset);
         BuddyBlock* rightChildBlock =
             new BuddyBlock(nextLevelSize, currBlock->mOffset + nextLevelSize);

         // Remember the parent to merge these back upon de-allocation.
         rightChildBlock->pParent = currBlock;
         leftChildBlock->pParent = currBlock;

         // Make them buddies.
         leftChildBlock->pBuddy = rightChildBlock;
         rightChildBlock->pBuddy = leftChildBlock;

         // Insert the children back into the free list into the next level.
         // The free list does not require a specific order. However, an order is specified as
         // it's ideal to allocate lower addresses first by having the leftmost child in HEAD.
         InsertFreeBlock(rightChildBlock, currBlockLevel + 1);
         InsertFreeBlock(leftChildBlock, currBlockLevel + 1);

         // Curr block is now split.
         currBlock->mState = BlockState::Split;
         currBlock->split.pLeft = leftChildBlock;

         // Decend down into the next level.
         currBlock = leftChildBlock;
     }

     // Remove curr block from free-list (now allocated).
     RemoveFreeBlock(currBlock, currBlockLevel);
     currBlock->mState = BlockState::Allocated;

     return currBlock->mOffset;
 }

 void BuddyAllocator::Deallocate(uint64_t offset) {
     BuddyBlock* curr = mRoot;

     // TODO(crbug.com/dawn/827): Optimize de-allocation.
     // Passing allocationSize directly will avoid the following level-by-level search;
     // however, it requires the size information to be stored outside the allocator.

     // Search for the free block node that corresponds to the block offset.
     size_t currBlockLevel = 0;
     while (curr->mState == BlockState::Split) {
         if (offset < curr->split.pLeft->pBuddy->mOffset) {
             curr = curr->split.pLeft;
         } else {
             curr = curr->split.pLeft->pBuddy;
         }

         currBlockLevel++;
     }

     DAWN_ASSERT(curr->mState == BlockState::Allocated);

     // Ensure the block is at the correct level
     DAWN_ASSERT(currBlockLevel == ComputeLevelFromBlockSize(curr->mSize));

     // Mark curr free so we can merge.
     curr->mState = BlockState::Free;

     // Merge the buddies (LevelN-to-Level0).
     while (currBlockLevel > 0 && curr->pBuddy->mState == BlockState::Free) {
         // Remove the buddy.
         RemoveFreeBlock(curr->pBuddy, currBlockLevel);

         BuddyBlock* parent = curr->pParent;

         // The buddies were inserted in a specific order but
         // could be deleted in any order.
         DeleteBlock(curr->pBuddy.ExtractAsDangling());
         DeleteBlock(curr);

         // Parent is now free.
         parent->mState = BlockState::Free;

         // Ascend up to the next level (parent block).
         curr = parent;
         currBlockLevel--;
     }

     InsertFreeBlock(curr, currBlockLevel);
 }

 // Helper which deletes a block in the tree recursively (post-order).
 void BuddyAllocator::DeleteBlock(BuddyBlock* block) {
     DAWN_ASSERT(block != nullptr);

     if (block->mState == BlockState::Split) {
         // Delete the pair in same order we inserted.
         DeleteBlock(block->split.pLeft->pBuddy.ExtractAsDangling());
         DeleteBlock(block->split.pLeft);
     }
     delete block;
 }

 }  // namespace dawn::native
	// 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 "dawn/native/BuddyAllocator.h"

	#include "dawn/common/Assert.h"
	#include "dawn/common/Math.h"

	namespace dawn::native {

	BuddyAllocator::BuddyAllocator(uint64_t maxSize) : mMaxBlockSize(maxSize) {
	DAWN_ASSERT(IsPowerOfTwo(maxSize));

	mFreeLists.resize(Log2(mMaxBlockSize) + 1);

	// Insert the level0 free block.
	mRoot = new BuddyBlock(maxSize, /offset/ 0);
	mFreeLists[0] = {mRoot};
	}

	BuddyAllocator::~BuddyAllocator() {
	if (mRoot) {
	mFreeLists.clear();

	DeleteBlock(mRoot.ExtractAsDangling());
	}
	}

	uint64_t BuddyAllocator::ComputeTotalNumOfFreeBlocksForTesting() const {
	return ComputeNumOfFreeBlocks(mRoot);
	}

	uint64_t BuddyAllocator::ComputeNumOfFreeBlocks(BuddyBlock* block) const {
	if (block->mState == BlockState::Free) {
	return 1;
	} else if (block->mState == BlockState::Split) {
	return ComputeNumOfFreeBlocks(block->split.pLeft) +
	ComputeNumOfFreeBlocks(block->split.pLeft->pBuddy);
	}
	return 0;
	}

	uint32_t BuddyAllocator::ComputeLevelFromBlockSize(uint64_t blockSize) const {
	// Every level in the buddy system can be indexed by order-n where n = log2(blockSize).
	// However, mFreeList zero-indexed by level.
	// For example, blockSize=4 is Level1 if MAX_BLOCK is 8.
	return Log2(mMaxBlockSize) - Log2(blockSize);
	}

	uint64_t BuddyAllocator::GetNextFreeAlignedBlock(size_t allocationBlockLevel,
	uint64_t alignment) const {
	DAWN_ASSERT(IsPowerOfTwo(alignment));
	// The current level is the level that corresponds to the allocation size. The free list may
	// not contain a block at that level until a larger one gets allocated (and splits).
	// Continue to go up the tree until such a larger block exists.
	//
	// Even if the block exists at the level, it cannot be used if it's offset is unaligned.
	// When the alignment is also a power-of-two, we simply use the next free block whose size
	// is greater than or equal to the alignment value.
	//
	// After one 8-byte allocation:
	//
	// Level --------------------------------
	// 0 32 \| S \|
	// --------------------------------
	// 1 16 \| S \| F2 \| S - split
	// -------------------------------- F - free
	// 2 8 \| Aa \| F1 \| \| A - allocated
	// --------------------------------
	//
	// Allocate(size=8, alignment=8) will be satisfied by using F1.
	// Allocate(size=8, alignment=4) will be satified by using F1.
	// Allocate(size=8, alignment=16) will be satisified by using F2.
	//
	for (size_t ii = 0; ii <= allocationBlockLevel; ++ii) {
	size_t currLevel = allocationBlockLevel - ii;
	BuddyBlock* freeBlock = mFreeLists[currLevel].head;
	if (freeBlock && (freeBlock->mOffset % alignment == 0)) {
	return currLevel;
	}
	}
	return kInvalidOffset; // No free block exists at any level.
	}

	// Inserts existing free block into the free-list.
	// Called by allocate upon splitting to insert a child block into a free-list.
	// Note: Always insert into the head of the free-list. As when a larger free block at a lower
	// level was split, there were no smaller free blocks at a higher level to allocate.
	void BuddyAllocator::InsertFreeBlock(BuddyBlock* block, size_t level) {
	DAWN_ASSERT(block->mState == BlockState::Free);

	// Inserted block is now the front (no prev).
	block->free.pPrev = nullptr;

	// Old head is now the inserted block's next.
	block->free.pNext = mFreeLists[level].head;

	// Block already in HEAD position (ex. right child was inserted first).
	if (mFreeLists[level].head != nullptr) {
	// Old head's previous is the inserted block.
	mFreeLists[level].head->free.pPrev = block;
	}

	mFreeLists[level].head = block;
	}

	void BuddyAllocator::RemoveFreeBlock(BuddyBlock* block, size_t level) {
	DAWN_ASSERT(block->mState == BlockState::Free);

	if (mFreeLists[level].head == block) {
	// Block is in HEAD position.
	mFreeLists[level].head = mFreeLists[level].head->free.pNext;
	} else {
	// Block is after HEAD position.
	BuddyBlock* pPrev = block->free.pPrev;
	BuddyBlock* pNext = block->free.pNext;

	DAWN_ASSERT(pPrev != nullptr);
	DAWN_ASSERT(pPrev->mState == BlockState::Free);

	pPrev->free.pNext = pNext;

	if (pNext != nullptr) {
	DAWN_ASSERT(pNext->mState == BlockState::Free);
	pNext->free.pPrev = pPrev;
	}
	}
	}

	uint64_t BuddyAllocator::Allocate(uint64_t allocationSize, uint64_t alignment) {
	if (allocationSize == 0 \|\| allocationSize > mMaxBlockSize) {
	return kInvalidOffset;
	}

	// Compute the level
	const uint32_t allocationSizeToLevel = ComputeLevelFromBlockSize(allocationSize);

	DAWN_ASSERT(allocationSizeToLevel < mFreeLists.size());

	uint64_t currBlockLevel = GetNextFreeAlignedBlock(allocationSizeToLevel, alignment);

	// Error when no free blocks exist (allocator is full)
	if (currBlockLevel == kInvalidOffset) {
	return kInvalidOffset;
	}

	// Split free blocks level-by-level.
	// Terminate when the current block level is equal to the computed level of the requested
	// allocation.
	BuddyBlock* currBlock = mFreeLists[currBlockLevel].head;

	for (; currBlockLevel < allocationSizeToLevel; currBlockLevel++) {
	DAWN_ASSERT(currBlock->mState == BlockState::Free);

	// Remove curr block (about to be split).
	RemoveFreeBlock(currBlock, currBlockLevel);

	// Create two free child blocks (the buddies).
	const uint64_t nextLevelSize = currBlock->mSize / 2;
	BuddyBlock* leftChildBlock = new BuddyBlock(nextLevelSize, currBlock->mOffset);
	BuddyBlock* rightChildBlock =
	new BuddyBlock(nextLevelSize, currBlock->mOffset + nextLevelSize);

	// Remember the parent to merge these back upon de-allocation.
	rightChildBlock->pParent = currBlock;
	leftChildBlock->pParent = currBlock;

	// Make them buddies.
	leftChildBlock->pBuddy = rightChildBlock;
	rightChildBlock->pBuddy = leftChildBlock;

	// Insert the children back into the free list into the next level.
	// The free list does not require a specific order. However, an order is specified as
	// it's ideal to allocate lower addresses first by having the leftmost child in HEAD.
	InsertFreeBlock(rightChildBlock, currBlockLevel + 1);
	InsertFreeBlock(leftChildBlock, currBlockLevel + 1);

	// Curr block is now split.
	currBlock->mState = BlockState::Split;
	currBlock->split.pLeft = leftChildBlock;

	// Decend down into the next level.
	currBlock = leftChildBlock;
	}

	// Remove curr block from free-list (now allocated).
	RemoveFreeBlock(currBlock, currBlockLevel);
	currBlock->mState = BlockState::Allocated;

	return currBlock->mOffset;
	}

	void BuddyAllocator::Deallocate(uint64_t offset) {
	BuddyBlock* curr = mRoot;

	// TODO(crbug.com/dawn/827): Optimize de-allocation.
	// Passing allocationSize directly will avoid the following level-by-level search;
	// however, it requires the size information to be stored outside the allocator.

	// Search for the free block node that corresponds to the block offset.
	size_t currBlockLevel = 0;
	while (curr->mState == BlockState::Split) {
	if (offset < curr->split.pLeft->pBuddy->mOffset) {
	curr = curr->split.pLeft;
	} else {
	curr = curr->split.pLeft->pBuddy;
	}

	currBlockLevel++;
	}

	DAWN_ASSERT(curr->mState == BlockState::Allocated);

	// Ensure the block is at the correct level
	DAWN_ASSERT(currBlockLevel == ComputeLevelFromBlockSize(curr->mSize));

	// Mark curr free so we can merge.
	curr->mState = BlockState::Free;

	// Merge the buddies (LevelN-to-Level0).
	while (currBlockLevel > 0 && curr->pBuddy->mState == BlockState::Free) {
	// Remove the buddy.
	RemoveFreeBlock(curr->pBuddy, currBlockLevel);

	BuddyBlock* parent = curr->pParent;

	// The buddies were inserted in a specific order but
	// could be deleted in any order.
	DeleteBlock(curr->pBuddy.ExtractAsDangling());
	DeleteBlock(curr);

	// Parent is now free.
	parent->mState = BlockState::Free;

	// Ascend up to the next level (parent block).
	curr = parent;
	currBlockLevel--;
	}

	InsertFreeBlock(curr, currBlockLevel);
	}

	// Helper which deletes a block in the tree recursively (post-order).
	void BuddyAllocator::DeleteBlock(BuddyBlock* block) {
	DAWN_ASSERT(block != nullptr);

	if (block->mState == BlockState::Split) {
	// Delete the pair in same order we inserted.
	DeleteBlock(block->split.pLeft->pBuddy.ExtractAsDangling());
	DeleteBlock(block->split.pLeft);
	}
	delete block;
	}

	} // namespace dawn::native