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