1 // Copyright 2025 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/allocatable.h" 20 #include "pw_allocator/block/basic.h" 21 #include "pw_allocator/block/contiguous.h" 22 #include "pw_allocator/block/iterable.h" 23 #include "pw_allocator/bucket/fast_sorted.h" 24 #include "pw_bytes/span.h" 25 26 namespace pw::allocator { 27 28 /// CRTP-style base class for block implementations with limited code size and 29 /// memory overhead. 30 /// 31 /// This implementation encodes its metadata in a header consisting of only two 32 /// firelds of type `T`. It implements only the block mix-ins necessary to be 33 /// used with a `BlockAllocator`. 34 /// 35 /// @tparam Derived Block implementation derived from this class. 36 /// @tparam T Field type used to store metadara. 37 /// @tparam kShift Encoded sizes are left shifted by this amount to 38 /// produce actual sizes. A larger value allows a larger 39 /// maximum addressable size, at the cost of a larger 40 /// minimum allocatable size. 41 template <typename Derived, typename T, size_t kShift = 0> 42 struct SmallBlockBase : public BasicBlock<Derived>, 43 public ContiguousBlock<Derived>, 44 public IterableBlock<Derived>, 45 public AllocatableBlock<Derived> { 46 protected: SmallBlockBaseSmallBlockBase47 constexpr explicit SmallBlockBase(size_t outer_size) 48 : prev_and_free_(1U), 49 next_and_last_(static_cast<T>(outer_size >> kShift) | 1U) {} 50 51 private: 52 using Basic = BasicBlock<Derived>; 53 using Contiguous = ContiguousBlock<Derived>; 54 using Allocatable = AllocatableBlock<Derived>; 55 56 // `Basic` required methods. 57 friend Basic; 58 DefaultAlignmentSmallBlockBase59 static constexpr size_t DefaultAlignment() { 60 return std::max(alignof(GenericFastSortedItem), size_t(2u) << kShift); 61 } BlockOverheadSmallBlockBase62 static constexpr size_t BlockOverhead() { return sizeof(Derived); } MaxAddressableSizeSmallBlockBase63 static constexpr size_t MaxAddressableSize() { 64 return size_t(std::numeric_limits<T>::max()) << kShift; 65 } AsBlockSmallBlockBase66 static inline Derived* AsBlock(ByteSpan bytes) { 67 return ::new (bytes.data()) Derived(bytes.size()); 68 } MinInnerSizeSmallBlockBase69 static constexpr size_t MinInnerSize() { return std::max(2U, 1U << kShift); } ReservedWhenFreeSmallBlockBase70 static constexpr size_t ReservedWhenFree() { 71 return sizeof(GenericFastSortedItem); 72 } OuterSizeUncheckedSmallBlockBase73 size_t OuterSizeUnchecked() const { return (next_and_last_ & ~1U) << kShift; } 74 75 // `Basic` overrides. DoCheckInvariantsSmallBlockBase76 bool DoCheckInvariants(bool strict) const { 77 return Basic::DoCheckInvariants(strict) && 78 Contiguous::DoCheckInvariants(strict); 79 } 80 81 // `Contiguous` required methods. 82 friend Contiguous; 83 IsLastUncheckedSmallBlockBase84 constexpr bool IsLastUnchecked() const { return (next_and_last_ & 1U) != 0; } 85 SetNextSmallBlockBase86 constexpr void SetNext(size_t outer_size, Derived* next) { 87 auto packed_size = static_cast<T>(outer_size >> kShift); 88 if (next == nullptr) { 89 next_and_last_ = packed_size | 1U; 90 } else { 91 next_and_last_ = packed_size; 92 next->prev_and_free_ = packed_size | (next->prev_and_free_ & 1U); 93 } 94 } 95 PrevOuterSizeUncheckedSmallBlockBase96 constexpr size_t PrevOuterSizeUnchecked() const { 97 return (prev_and_free_ & ~1U) << kShift; 98 } 99 100 // `Allocatable` required methods. 101 friend Allocatable; 102 IsFreeUncheckedSmallBlockBase103 constexpr bool IsFreeUnchecked() const { return (prev_and_free_ & 1U) != 0; } 104 SetFreeSmallBlockBase105 constexpr void SetFree(bool is_free) { 106 prev_and_free_ = (prev_and_free_ & ~1U) | (is_free ? 1U : 0U); 107 } 108 109 T prev_and_free_; 110 T next_and_last_; 111 }; 112 113 } // namespace pw::allocator 114