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