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