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 "pw_allocator/block_allocator_base.h" 17 18 namespace pw::allocator { 19 20 /// Block allocator that uses a "best-fit" allocation strategy. 21 /// 22 /// In this strategy, the allocator handles an allocation request by looking at 23 /// all unused blocks and finding the smallest one which can satisfy the 24 /// request. 25 /// 26 /// This algorithm may make better use of available memory by wasting less on 27 /// unused fragments, but may also lead to worse fragmentation as those 28 /// fragments are more likely to be too small to be useful to other requests. 29 template <typename OffsetType = uintptr_t, 30 size_t kPoisonInterval = 0, 31 size_t kAlign = alignof(OffsetType)> 32 class BestFitBlockAllocator 33 : public BlockAllocator<OffsetType, kPoisonInterval, kAlign> { 34 public: 35 using Base = BlockAllocator<OffsetType, kPoisonInterval, kAlign>; 36 using BlockType = typename Base::BlockType; 37 38 /// Constexpr constructor. Callers must explicitly call `Init`. BestFitBlockAllocator()39 constexpr BestFitBlockAllocator() : Base() {} 40 41 /// Non-constexpr constructor that automatically calls `Init`. 42 /// 43 /// @param[in] region Region of memory to use when satisfying allocation 44 /// requests. The region MUST be large enough to fit an 45 /// aligned block with overhead. It MUST NOT be larger 46 /// than what is addressable by `OffsetType`. BestFitBlockAllocator(ByteSpan region)47 explicit BestFitBlockAllocator(ByteSpan region) : Base(region) {} 48 49 private: 50 /// @copydoc Allocator::Allocate ChooseBlock(Layout layout)51 BlockType* ChooseBlock(Layout layout) override { 52 // Search backwards for the smallest block that can hold this allocation. 53 BlockType* best = nullptr; 54 for (auto* block : Base::rblocks()) { 55 if (!block->CanAllocLast(layout).ok()) { 56 continue; 57 } 58 if (best == nullptr || block->OuterSize() < best->OuterSize()) { 59 best = block; 60 } 61 } 62 if (best != nullptr && BlockType::AllocLast(best, layout).ok()) { 63 return best; 64 } 65 return nullptr; 66 } 67 }; 68 69 } // namespace pw::allocator 70