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 <cstddef> 17 #include <limits> 18 19 #include "pw_allocator/block/poisonable.h" 20 #include "pw_allocator/config.h" 21 #include "pw_allocator/layout.h" 22 #include "pw_assert/assert.h" 23 #include "pw_bytes/alignment.h" 24 25 namespace pw::allocator::internal { 26 27 /// A container of free blocks. 28 /// 29 /// Allocators can use buckets to manage their free blocks. This may include 30 /// using buckets to sort free blocks based on their size, partitioning them 31 /// into several buckets, etc., for faster searching when allocating. Each 32 /// bucket may have a maximum block inner size set which indicates the largest 33 /// free block allowable in the bucket, or be unbounded. 34 /// 35 /// This class is a CRTP-style base class. The specific derived class includes 36 /// an intrusive container type from `pw_containers`. The usable space of free 37 /// blocks added to the bucket is used to store the intrusive item corresponding 38 /// to the container. 39 /// 40 /// This implies that a block must be large enough to hold the item type in 41 /// order to be added to a bucket. Since intrusive items can be part of at most 42 /// one container at any point in time, free blocks can be in at most ONE 43 /// bucket at any time. However, a sufficiently large block may be sequentially 44 /// added to more than one *type* of bucket. This can be useful for allocators 45 /// that may track blocks in more than one way, e.g. an allocator that caches 46 /// recently freed blocks. 47 /// 48 /// @tparam Derived Bucket type derived from this base class. 49 /// @tparam BlockType Type of free blocks that can be held in this bucket. 50 /// @tparam ItemType Intrusive `pw_containers` type. The usable space of 51 /// each free block in the bucket will hold an item of 52 /// this type. 53 template <typename Derived, typename BlockType_, typename ItemType_> 54 class BucketBase { 55 public: 56 using BlockType = BlockType_; 57 using ItemType = ItemType_; 58 BucketBase()59 constexpr BucketBase() { 60 if constexpr (is_poisonable_v<BlockType>) { 61 static_assert(BlockType::kPoisonOffset >= sizeof(ItemType), 62 "Block type does not reserve sufficient space for an item"); 63 } 64 } 65 66 /// Returns whether this buckets contains any free blocks. empty()67 constexpr bool empty() const { return derived()->items_.empty(); } 68 69 /// Returns the configured maximum inner size for blocks in this bucket. max_inner_size()70 constexpr size_t max_inner_size() const { return max_inner_size_; } 71 72 /// Sets the maximum inner size for blocks in this bucket. 73 /// 74 /// This can only be called when the bucket is empty. set_max_inner_size(size_t max_inner_size)75 constexpr void set_max_inner_size(size_t max_inner_size) { 76 PW_ASSERT(empty()); 77 max_inner_size_ = max_inner_size; 78 } 79 80 /// Adds a block to this bucket if the block can hold an item of the bucket's 81 /// `ItemType`, otherwise does nothing. 82 /// 83 /// @param block The block to be added. Add(BlockType & block)84 [[nodiscard]] bool Add(BlockType& block) { 85 if (block.InnerSize() < sizeof(ItemType)) { 86 return false; 87 } 88 if constexpr (PW_ALLOCATOR_STRICT_VALIDATION) { 89 PW_ASSERT(block.InnerSize() <= max_inner_size_); 90 PW_ASSERT(IsAlignedAs<ItemType>(block.UsableSpace())); 91 } 92 derived()->DoAdd(block); 93 return true; 94 } 95 96 /// Removes and returns a block if the bucket is not empty; otherwise returns 97 /// null. Exactly which block is returned depends on the specific bucket 98 /// implementation. RemoveAny()99 [[nodiscard]] BlockType* RemoveAny() { 100 return derived()->DoRemoveCompatible(Layout(1, 1)); 101 } 102 103 /// If the given `block` is in this bucket, removes it and returns true; 104 /// otherwise, returns false. 105 /// 106 /// @param block The block to be removed. Remove(BlockType & block)107 [[nodiscard]] bool Remove(BlockType& block) { 108 return block.InnerSize() >= sizeof(ItemType) && derived()->DoRemove(block); 109 } 110 111 /// Removes and returns a block that can be allocated with the given `layout`, 112 /// or null if no such block is present in the bucket. 113 /// 114 /// Bucket implementations must only return a block if 115 /// `block->CanAlloc(layout)` would succeed. 116 /// 117 /// @param layout Allocatable layout of the block to be removed. RemoveCompatible(Layout layout)118 [[nodiscard]] BlockType* RemoveCompatible(Layout layout) { 119 return derived()->DoRemoveCompatible(layout); 120 } 121 122 /// Removes all blocks from this bucket. Clear()123 void Clear() { derived()->items_.clear(); } 124 125 /// Returns an iterator the first element in a range whose successor satisfies 126 /// a given `predicate`. 127 /// 128 /// The returned iterator will be in the range (`before_first`, `last`), 129 /// and will be the element before `last` element satisfies the predicate. 130 /// 131 /// This is intended to act similar to `std::find_if` in order to return 132 /// iterators that can be used with sorted forward lists like 133 /// `std::forward_list<T>` or `pw::IntrusiveForwardList<T>. In particular, 134 /// methods like `insert_after` and `erase_after` need the iterator that 135 /// precedes a desired item. 136 template <typename Iterator, typename Predicate> FindPrevIf(Iterator before_first,Iterator last,Predicate predicate)137 static Iterator FindPrevIf(Iterator before_first, 138 Iterator last, 139 Predicate predicate) { 140 Iterator prev = before_first; 141 Iterator iter = prev; 142 ++iter; 143 for (; iter != last; ++iter) { 144 if (predicate(*iter)) { 145 break; 146 } 147 prev = iter; 148 } 149 return prev; 150 } 151 152 /// Returns a lambda that tests if the blocks storing an item can be allocated 153 /// with the given `layout`. 154 /// 155 /// This lambda can be used with `std::find_if` and `FindPrevIf`. MakeCanAllocPredicate(Layout layout)156 static auto MakeCanAllocPredicate(Layout layout) { 157 return [layout](ItemType& item) { 158 auto* block = BlockType::FromUsableSpace(&item); 159 return block->CanAlloc(layout).ok(); 160 }; 161 } 162 163 /// Returns the block storing the item pointed to by the provided `iter`, or 164 /// null if the iterator is the `last` iterator. 165 template <typename Iterator> GetBlockFromIterator(Iterator iter,Iterator last)166 constexpr BlockType* GetBlockFromIterator(Iterator iter, Iterator last) { 167 return iter != last ? BlockType::FromUsableSpace(&(*iter)) : nullptr; 168 } 169 170 /// Returns the block storing the item after the provided `prev` iterator, or 171 /// null if the iterator points to the element before the `last` iterator. 172 template <typename Iterator> GetBlockFromPrev(Iterator prev,Iterator last)173 constexpr BlockType* GetBlockFromPrev(Iterator prev, Iterator last) { 174 return GetBlockFromIterator(++prev, last); 175 } 176 177 protected: 178 /// Returns an existing item stored in a free block's usable space. 179 /// 180 /// The item is created when adding a block to a bucket, that is, in the 181 /// derived type's implementation of `DoAdd`. 182 /// 183 /// @pre the block must have been added to a bucket of type `Derived`. GetItemFrom(BlockType & block)184 static ItemType& GetItemFrom(BlockType& block) { 185 return *(std::launder(reinterpret_cast<ItemType*>(block.UsableSpace()))); 186 } 187 188 private: derived()189 constexpr Derived* derived() { return static_cast<Derived*>(this); } derived()190 constexpr const Derived* derived() const { 191 return static_cast<const Derived*>(this); 192 } 193 194 /// The maximum inner size of blocks in this bucket. 195 size_t max_inner_size_ = std::numeric_limits<size_t>::max(); 196 }; 197 198 } // namespace pw::allocator::internal 199