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 "last-fit" allocation strategy. 21 /// 22 /// In this strategy, the allocator handles an allocation request by starting at 23 /// the end of the range of blocks and looking for the last one which can 24 /// satisfy the request. 25 /// 26 /// This strategy may result in slightly better fragmentation than the 27 /// corresponding "first-fit" strategy, since even with alignment it will result 28 /// in at most one unused fragment before the allocated block. 29 template <typename OffsetType = uintptr_t, 30 size_t kPoisonInterval = 0, 31 size_t kAlign = alignof(OffsetType)> 32 class LastFitBlockAllocator 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`. LastFitBlockAllocator()39 constexpr LastFitBlockAllocator() : 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`. LastFitBlockAllocator(ByteSpan region)47 explicit LastFitBlockAllocator(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 last block that can hold this allocation. 53 for (auto* block : Base::rblocks()) { 54 if (BlockType::AllocLast(block, layout).ok()) { 55 return block; 56 } 57 } 58 return nullptr; 59 } 60 }; 61 62 } // namespace pw::allocator 63