// 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