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 "first-fit" allocation strategy. 21 /// 22 /// In this strategy, the allocator handles an allocation request by starting at 23 /// the beginning of the range of blocks and looking for the first one which can 24 /// satisfy the request. 25 /// 26 /// This strategy may result in slightly worse fragmentation than the 27 /// corresponding "last-fit" strategy, since the alignment may result in unused 28 /// fragments both before and after an allocated block. 29 template <typename OffsetType = uintptr_t, 30 size_t kPoisonInterval = 0, 31 size_t kAlign = alignof(OffsetType)> 32 class FirstFitBlockAllocator 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`. FirstFitBlockAllocator()39 constexpr FirstFitBlockAllocator() : 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`. FirstFitBlockAllocator(ByteSpan region)47 explicit FirstFitBlockAllocator(ByteSpan region) : Base(region) {} 48 49 private: 50 /// @copydoc Allocator::Allocate ChooseBlock(Layout layout)51 BlockType* ChooseBlock(Layout layout) override { 52 // Search forwards for the first block that can hold this allocation. 53 for (auto* block : Base::blocks()) { 54 block->CrashIfInvalid(); 55 if (BlockType::AllocFirst(block, layout).ok()) { 56 return block; 57 } 58 } 59 return nullptr; 60 } 61 }; 62 63 } // namespace pw::allocator 64