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 "dual first-fit" allocation strategy split 21 /// between large and small allocations. 22 /// 23 /// In this strategy, the strategy includes a threshold value. Requests for 24 /// more than this threshold are handled similarly to `FirstFit`, while requests 25 /// for less than this threshold are handled similarly to `LastFit`. 26 /// 27 /// This algorithm approaches the performance of `FirstFit` and `LastFit` while 28 /// improving on those algorithms fragmentation. 29 template <typename OffsetType = uintptr_t, 30 size_t kPoisonInterval = 0, 31 size_t kAlign = alignof(OffsetType)> 32 class DualFirstFitBlockAllocator 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`. DualFirstFitBlockAllocator()39 constexpr DualFirstFitBlockAllocator() : 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`. DualFirstFitBlockAllocator(ByteSpan region,size_t threshold)47 DualFirstFitBlockAllocator(ByteSpan region, size_t threshold) 48 : Base(region), threshold_(threshold) {} 49 50 /// Sets the threshold value for which requests are considered "large". set_threshold(size_t threshold)51 void set_threshold(size_t threshold) { threshold_ = threshold; } 52 53 private: 54 /// @copydoc Allocator::Allocate ChooseBlock(Layout layout)55 BlockType* ChooseBlock(Layout layout) override { 56 if (layout.size() < threshold_) { 57 // Search backwards for the last block that can hold this allocation. 58 for (auto* block : Base::rblocks()) { 59 if (BlockType::AllocLast(block, layout).ok()) { 60 return block; 61 } 62 } 63 } else { 64 // Search forwards for the first block that can hold this allocation. 65 for (auto* block : Base::blocks()) { 66 if (BlockType::AllocFirst(block, layout).ok()) { 67 return block; 68 } 69 } 70 } 71 // No valid block found. 72 return nullptr; 73 } 74 75 size_t threshold_ = 0; 76 }; 77 78 } // namespace pw::allocator 79