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 <limits> 17 18 #include "pw_allocator/block/detailed_block.h" 19 #include "pw_allocator/block_allocator.h" 20 #include "pw_allocator/bucket/sequenced.h" 21 22 namespace pw::allocator { 23 24 /// Alias for a default block type that is compatible with `FirstFitAllocator`. 25 template <typename OffsetType> 26 using FirstFitBlock = DetailedBlock<OffsetType, SequencedItem>; 27 28 /// Block allocator that uses a "first-fit" allocation strategy split 29 /// between large and small allocations. 30 /// 31 /// In this strategy, the allocator handles an allocation request by starting at 32 /// the beginning of the range of blocks and looking for the first one which can 33 /// satisfy the request. 34 /// 35 /// Optionally, callers may set a "threshold" value. If set, requests smaller 36 /// than the threshold are satisfied using the *last* compatible block. This 37 /// separates large and small requests and can reduce overall fragmentation. 38 template <typename BlockType = FirstFitBlock<uintptr_t>> 39 class FirstFitAllocator : public BlockAllocator<BlockType> { 40 public: 41 using Base = BlockAllocator<BlockType>; 42 43 /// Constexpr constructor. Callers must explicitly call `Init`. 44 constexpr FirstFitAllocator() = default; 45 46 /// Non-constexpr constructor that automatically calls `Init`. 47 /// 48 /// @param[in] region Region of memory to use when satisfying allocation 49 /// requests. The region MUST be valid as an argument 50 /// to `BlockType::Init`. FirstFitAllocator(ByteSpan region)51 FirstFitAllocator(ByteSpan region) { Base::Init(region); } 52 53 /// Non-constexpr constructor that automatically calls `Init`. 54 /// 55 /// @param[in] region Region of memory to use when satisfying allocation 56 /// requests. The region MUST be valid as an argument 57 /// to `BlockType::Init`. 58 /// @param[in] threshold Value for which requests are considered "large". FirstFitAllocator(ByteSpan region,size_t threshold)59 FirstFitAllocator(ByteSpan region, size_t threshold) { 60 Base::Init(region); 61 bucket_.set_threshold(threshold); 62 } 63 64 /// Sets the threshold value for which requests are considered "large". set_threshold(size_t threshold)65 void set_threshold(size_t threshold) { bucket_.set_threshold(threshold); } 66 67 private: 68 /// @copydoc BlockAllocator::ChooseBlock ChooseBlock(Layout layout)69 BlockResult<BlockType> ChooseBlock(Layout layout) override { 70 if (BlockType* block = bucket_.RemoveCompatible(layout); block != nullptr) { 71 return BlockType::AllocFirst(std::move(block), layout); 72 } 73 return BlockResult<BlockType>(nullptr, Status::NotFound()); 74 } 75 76 /// @copydoc BlockAllocator::ReserveBlock ReserveBlock(BlockType & block)77 void ReserveBlock(BlockType& block) override { 78 std::ignore = bucket_.Remove(block); 79 } 80 81 /// @copydoc BlockAllocator::RecycleBlock RecycleBlock(BlockType & block)82 void RecycleBlock(BlockType& block) override { 83 std::ignore = bucket_.Add(block); 84 } 85 86 SequencedBucket<BlockType> bucket_; 87 size_t threshold_ = 0; 88 }; 89 90 } // namespace pw::allocator 91