1 // Copyright 2024 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://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, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <array> 17 #include <cstdint> 18 #include <utility> 19 20 #include "pw_allocator/block/detailed_block.h" 21 #include "pw_allocator/block_allocator.h" 22 #include "pw_allocator/bucket/unordered.h" 23 #include "pw_assert/check.h" 24 #include "pw_status/try.h" 25 26 namespace pw::allocator { 27 28 /// Alias for a default block type that is compatible with 29 /// `BucketAllocator`. 30 template <typename OffsetType = uintptr_t> 31 using BucketBlock = DetailedBlock<OffsetType, UnorderedItem>; 32 33 /// Block allocator that uses sized buckets of free blocks. 34 /// 35 /// In this strategy, the allocator handles an allocation request by starting 36 /// with the bucket with the smallest size that is larger than the requested 37 /// size. It tries to allocate using the blocks in that block, if any, before 38 /// trying the bucket with the next largest size. 39 /// 40 /// On deallocation, blocks are placed in the bucket of the smallest size that 41 /// is larger than usable space of the block being freed. 42 /// 43 /// The last bucket always has an unbounded size. 44 /// 45 /// As an example, assume that the allocator is configured with a minimum block 46 /// inner size of 64 and 5 buckets. The internal state may look like the 47 /// following: 48 /// 49 /// @code{.unparsed} 50 /// bucket[0] (64B) --> block[12B] --> block[42B] --> block[64B] --> NULL 51 /// bucket[1] (128B) --> block[65B] --> block[72B] --> NULL 52 /// bucket[2] (256B) --> NULL 53 /// bucket[3] (512B) --> block[312B] --> block[512B] --> block[416B] --> NULL 54 /// bucket[4] (implicit) --> block[1024B] --> block[513B] --> NULL 55 /// @endcode 56 template <typename BlockType = BucketBlock<>, 57 size_t kMinInnerSize = 32, 58 size_t kNumBuckets = 5> 59 class BucketAllocator : public BlockAllocator<BlockType> { 60 private: 61 using Base = BlockAllocator<BlockType>; 62 63 public: 64 /// Constexpr constructor. Callers must explicitly call `Init`. BucketAllocator()65 constexpr BucketAllocator() { 66 size_t max_inner_size = kMinInnerSize; 67 for (auto& bucket : span(buckets_.data(), kNumBuckets - 1)) { 68 bucket.set_max_inner_size(max_inner_size); 69 max_inner_size <<= 1; 70 } 71 } 72 73 /// Non-constexpr constructor that automatically calls `Init`. 74 /// 75 /// @param[in] region Region of memory to use when satisfying allocation 76 /// requests. The region MUST be large enough to fit an 77 /// aligned block with overhead. It MUST NOT be larger 78 /// than what is addressable by `OffsetType`. BucketAllocator(ByteSpan region)79 explicit BucketAllocator(ByteSpan region) : BucketAllocator() { 80 Base::Init(region); 81 } 82 ~BucketAllocator()83 ~BucketAllocator() override { 84 for (auto& bucket : buckets_) { 85 bucket.Clear(); 86 } 87 } 88 89 private: 90 /// @copydoc BlockAllocator::ChooseBlock ChooseBlock(Layout layout)91 BlockResult<BlockType> ChooseBlock(Layout layout) override { 92 for (auto& bucket : buckets_) { 93 if (layout.size() <= bucket.max_inner_size()) { 94 BlockType* block = bucket.RemoveCompatible(layout); 95 if (block != nullptr) { 96 return BlockType::AllocFirst(std::move(block), layout); 97 } 98 } 99 } 100 return BlockResult<BlockType>(nullptr, Status::NotFound()); 101 } 102 103 /// @copydoc BlockAllocator::ReserveBlock ReserveBlock(BlockType & block)104 void ReserveBlock(BlockType& block) override { 105 for (auto& bucket : buckets_) { 106 if (block.InnerSize() <= bucket.max_inner_size()) { 107 std::ignore = bucket.Remove(block); 108 break; 109 } 110 } 111 } 112 113 /// @copydoc BlockAllocator::RecycleBlock RecycleBlock(BlockType & block)114 void RecycleBlock(BlockType& block) override { 115 for (auto& bucket : buckets_) { 116 if (block.InnerSize() <= bucket.max_inner_size()) { 117 std::ignore = bucket.Add(block); 118 break; 119 } 120 } 121 } 122 123 std::array<UnorderedBucket<BlockType>, kNumBuckets> buckets_; 124 }; 125 126 } // namespace pw::allocator 127