1 // Copyright 2019 The Dawn Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef DAWNNATIVE_BUDDYALLOCATOR_H_ 16 #define DAWNNATIVE_BUDDYALLOCATOR_H_ 17 18 #include <cstddef> 19 #include <cstdint> 20 #include <limits> 21 #include <vector> 22 23 namespace dawn_native { 24 25 // Buddy allocator uses the buddy memory allocation technique to satisfy an allocation request. 26 // Memory is split into halves until just large enough to fit to the request. This 27 // requires the allocation size to be a power-of-two value. The allocator "allocates" a block by 28 // returning the starting offset whose size is guaranteed to be greater than or equal to the 29 // allocation size. To deallocate, the same offset is used to find the corresponding block. 30 // 31 // Internally, it manages a free list to track free blocks in a full binary tree. 32 // Every index in the free list corresponds to a level in the tree. That level also determines 33 // the size of the block to be used to satisfy the request. The first level (index=0) represents 34 // the root whose size is also called the max block size. 35 // 36 class BuddyAllocator { 37 public: 38 BuddyAllocator(uint64_t maxSize); 39 ~BuddyAllocator(); 40 41 // Required methods. 42 uint64_t Allocate(uint64_t allocationSize, uint64_t alignment = 1); 43 void Deallocate(uint64_t offset); 44 45 // For testing purposes only. 46 uint64_t ComputeTotalNumOfFreeBlocksForTesting() const; 47 48 static constexpr uint64_t kInvalidOffset = std::numeric_limits<uint64_t>::max(); 49 50 private: 51 uint32_t ComputeLevelFromBlockSize(uint64_t blockSize) const; 52 uint64_t GetNextFreeAlignedBlock(size_t allocationBlockLevel, uint64_t alignment) const; 53 54 enum class BlockState { Free, Split, Allocated }; 55 56 struct BuddyBlock { BuddyBlockBuddyBlock57 BuddyBlock(uint64_t size, uint64_t offset) 58 : mOffset(offset), mSize(size), mState(BlockState::Free) { 59 free.pPrev = nullptr; 60 free.pNext = nullptr; 61 } 62 63 uint64_t mOffset; 64 uint64_t mSize; 65 66 // Pointer to this block's buddy, iff parent is split. 67 // Used to quickly merge buddy blocks upon de-allocate. 68 BuddyBlock* pBuddy = nullptr; 69 BuddyBlock* pParent = nullptr; 70 71 // Track whether this block has been split or not. 72 BlockState mState; 73 74 struct FreeLinks { 75 BuddyBlock* pPrev; 76 BuddyBlock* pNext; 77 }; 78 79 struct SplitLink { 80 BuddyBlock* pLeft; 81 }; 82 83 union { 84 // Used upon allocation. 85 // Avoids searching for the next free block. 86 FreeLinks free; 87 88 // Used upon de-allocation. 89 // Had this block split upon allocation, it and it's buddy is to be deleted. 90 SplitLink split; 91 }; 92 }; 93 94 void InsertFreeBlock(BuddyBlock* block, size_t level); 95 void RemoveFreeBlock(BuddyBlock* block, size_t level); 96 void DeleteBlock(BuddyBlock* block); 97 98 uint64_t ComputeNumOfFreeBlocks(BuddyBlock* block) const; 99 100 // Keep track the head and tail (for faster insertion/removal). 101 struct BlockList { 102 BuddyBlock* head = nullptr; // First free block in level. 103 // TODO(crbug.com/dawn/827): Track the tail. 104 }; 105 106 BuddyBlock* mRoot = nullptr; // Used to deallocate non-free blocks. 107 108 uint64_t mMaxBlockSize = 0; 109 110 // List of linked-lists of free blocks where the index is a level that 111 // corresponds to a power-of-two sized block. 112 std::vector<BlockList> mFreeLists; 113 }; 114 115 } // namespace dawn_native 116 117 #endif // DAWNNATIVE_BUDDYALLOCATOR_H_ 118