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 <cstddef> 17 #include <limits> 18 19 #include "pw_allocator/block/detailed_block.h" 20 #include "pw_allocator/block_allocator.h" 21 #include "pw_allocator/bucket/fast_sorted.h" 22 #include "pw_allocator/bucket/sorted.h" 23 #include "pw_allocator/config.h" 24 25 namespace pw::allocator { 26 27 /// Alias for a default block type that is compatible with `FirstFitAllocator`. 28 template <typename OffsetType> 29 using BestFitBlock = DetailedBlock<OffsetType, GenericFastSortedItem>; 30 31 /// Block allocator that uses a "best-fit" allocation strategy. 32 /// 33 /// In this strategy, the allocator handles an allocation request by looking at 34 /// all unused blocks and finding the smallest one which can satisfy the 35 /// request. 36 /// 37 /// This algorithm may make better use of available memory by wasting less on 38 /// unused fragments, but may also lead to worse fragmentation as those 39 /// fragments are more likely to be too small to be useful to other requests. 40 template <typename BlockType = BestFitBlock<uintptr_t>> 41 class BestFitAllocator : public BlockAllocator<BlockType> { 42 public: 43 using Base = BlockAllocator<BlockType>; 44 45 /// Constexpr constructor. Callers must explicitly call `Init`. 46 constexpr BestFitAllocator() = default; 47 48 /// Non-constexpr constructor that automatically calls `Init`. 49 /// 50 /// @param[in] region Region of memory to use when satisfying allocation 51 /// requests. The region MUST be valid as an argument 52 /// to `BlockType::Init`. BestFitAllocator(ByteSpan region)53 BestFitAllocator(ByteSpan region) { Base::Init(region); } 54 55 private: 56 /// @copydoc BlockAllocator::ChooseBlock ChooseBlock(Layout layout)57 BlockResult<BlockType> ChooseBlock(Layout layout) override { 58 // The small bucket is slower; skip it if we can. 59 BlockType* block = nullptr; 60 if (layout.size() <= sizeof(SortedItem)) { 61 block = small_bucket_.RemoveCompatible(layout); 62 if (block != nullptr) { 63 return BlockType::AllocFirst(std::move(block), layout); 64 } 65 } 66 block = large_bucket_.RemoveCompatible(layout); 67 if (block != nullptr) { 68 return BlockType::AllocFirst(std::move(block), layout); 69 } 70 return BlockResult<BlockType>(nullptr, Status::NotFound()); 71 } 72 73 /// @copydoc BlockAllocator::ReserveBlock ReserveBlock(BlockType & block)74 void ReserveBlock(BlockType& block) override { 75 // The small bucket is slower; skip it if we can. 76 if (!large_bucket_.Remove(block)) { 77 std::ignore = small_bucket_.Remove(block); 78 } 79 } 80 81 /// @copydoc BlockAllocator::RecycleBlock RecycleBlock(BlockType & block)82 void RecycleBlock(BlockType& block) override { 83 if (block.InnerSize() <= sizeof(SortedItem)) { 84 std::ignore = small_bucket_.Add(block); 85 } else { 86 std::ignore = large_bucket_.Add(block); 87 } 88 } 89 90 ForwardSortedBucket<BlockType> small_bucket_; 91 FastSortedBucket<BlockType> large_bucket_; 92 }; 93 94 } // namespace pw::allocator 95