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 <array> 17 #include <cstddef> 18 19 #include "pw_allocator/allocator.h" 20 #include "pw_allocator/block/basic.h" 21 #include "pw_allocator/bucket/unordered.h" 22 #include "pw_bytes/span.h" 23 #include "pw_containers/vector.h" 24 #include "pw_status/try.h" 25 26 namespace pw::allocator { 27 namespace internal { 28 29 /// A specialized block used by the BuddyAllocator. 30 /// 31 /// Buddy blocks have outer sizes that are powers of two. When smaller blocks 32 /// are needed, a block is split into left and right halves of equal size. These 33 /// half-blocks are "buddies", and when both are freed they are merged back into 34 /// a single block. 35 class BuddyBlock : public BasicBlock<BuddyBlock> { 36 public: 37 BuddyBlock(size_t outer_size); 38 39 /// Simplified version of `Allocatable::CanAlloc`, as needed for 40 /// `UnorderedBucket::Remove`. 41 StatusWithSize CanAlloc(Layout layout) const; 42 43 /// Splits a block in half and returns the new block. 44 BuddyBlock* Split(); 45 46 /// Merges two blocks together. 47 static BuddyBlock* Merge(BuddyBlock*&& left, BuddyBlock*&& right); 48 49 private: 50 // `Basic` required methods. 51 using Basic = BasicBlock<BuddyBlock>; 52 friend Basic; DefaultAlignment()53 static constexpr size_t DefaultAlignment() { return 1; } BlockOverhead()54 static constexpr size_t BlockOverhead() { return sizeof(BuddyBlock); } MinInnerSize()55 static constexpr size_t MinInnerSize() { return sizeof(UnorderedItem); } OuterSizeUnchecked()56 constexpr size_t OuterSizeUnchecked() const { return 1U << outer_size_log2_; } 57 58 uint8_t outer_size_log2_; 59 }; 60 61 /// Size-independent buddy allocator. 62 /// 63 /// This allocator allocates blocks of memory whose sizes are powers of two. 64 /// See also https://en.wikipedia.org/wiki/Buddy_memory_allocation. 65 /// 66 /// Compared to `BuddyAllocator`, this implementation is size-agnostic with 67 /// respect to the number of buckets. 68 class GenericBuddyAllocator final { 69 public: 70 using BucketType = UnorderedBucket<BuddyBlock>; 71 72 static constexpr Capabilities kCapabilities = 73 kImplementsGetUsableLayout | kImplementsGetAllocatedLayout | 74 kImplementsGetCapacity | kImplementsRecognizes; 75 76 static constexpr size_t kDefaultMinOuterSize = 16; 77 static constexpr size_t kDefaultNumBuckets = 16; 78 79 /// Constructs a buddy allocator. 80 /// 81 /// @param[in] buckets Storage for buckets of free blocks. 82 /// @param[in] min_outer_size Outer size of the blocks in the first bucket. 83 GenericBuddyAllocator(span<BucketType> buckets, size_t min_outer_size); 84 85 /// Sets the memory used to allocate blocks. 86 void Init(ByteSpan region); 87 88 /// @copydoc Allocator::Allocate 89 void* Allocate(Layout layout); 90 91 /// @copydoc Deallocator::Deallocate 92 void Deallocate(void* ptr); 93 94 /// Returns the total capacity of this allocator. GetCapacity()95 size_t GetCapacity() const { return region_.size(); } 96 97 /// Returns the allocated layout for a given pointer. 98 Result<Layout> GetLayout(const void* ptr) const; 99 100 /// Ensures all allocations have been freed. Crashes with a diagnostic message 101 /// If any allocations remain outstanding. 102 void CrashIfAllocated(); 103 104 private: 105 span<BucketType> buckets_; 106 size_t min_outer_size_ = 0; 107 ByteSpan region_; 108 }; 109 110 } // namespace internal 111 112 /// Allocator that uses the buddy memory allocation algorithm. 113 /// 114 /// This allocator allocates blocks of memory whose sizes are powers of two. 115 /// This allows the allocator to satisfy requests to acquire and release memory 116 /// very quickly, at the possible cost of higher internal fragmentation. In 117 /// particular: 118 /// 119 /// * The maximum alignment for this allocator is `kMinInnerSize`. 120 /// * The minimum size of an allocation is `kMinInnerSize`. Less may be 121 /// requested, but it will be satisfied by a block of that inner size. 122 /// * The maximum size of an allocation is `kMinInnerSize << (kNumBuckets - 1)`. 123 /// 124 /// Use this allocator if you know the needed sizes are close to but less than 125 /// the block inner sizes and you need high allocator performance. 126 /// 127 /// @tparam kMinOuterSize Outer size of the smallest allocatable block. Must 128 /// be a power of two. All allocations will use at 129 /// least this much memory. 130 /// @tparam kNumBuckets Number of buckets. Must be at least 1. Each 131 /// additional bucket allows combining blocks into 132 /// larger blocks. 133 template <size_t kMinOuterSize_ = 134 internal::GenericBuddyAllocator::kDefaultMinOuterSize, 135 size_t kNumBuckets = 136 internal::GenericBuddyAllocator::kDefaultNumBuckets> 137 class BuddyAllocator : public Allocator { 138 public: 139 using BucketType = internal::GenericBuddyAllocator::BucketType; 140 141 static constexpr size_t kMinOuterSize = kMinOuterSize_; 142 143 static_assert((kMinOuterSize & (kMinOuterSize - 1)) == 0, 144 "kMinOuterSize must be a power of 2"); 145 146 /// Constructs an allocator. Callers must call `Init`. BuddyAllocator()147 BuddyAllocator() : impl_(buckets_, kMinOuterSize) {} 148 149 /// Constructs an allocator, and initializes it with the given memory region. 150 /// 151 /// @param[in] region Region of memory to use when satisfying allocation 152 /// requests. The region MUST be large enough to fit a 153 /// least one minimally-size `BuddyBlock`. BuddyAllocator(ByteSpan region)154 BuddyAllocator(ByteSpan region) : BuddyAllocator() { Init(region); } 155 156 /// Sets the memory region used by the allocator. 157 /// 158 /// @param[in] region Region of memory to use when satisfying allocation 159 /// requests. The region MUST be large enough to fit a 160 /// least one minimally-size `BuddyBlock`. Init(ByteSpan region)161 void Init(ByteSpan region) { impl_.Init(region); } 162 ~BuddyAllocator()163 ~BuddyAllocator() override { impl_.CrashIfAllocated(); } 164 165 private: 166 /// @copydoc Allocator::Allocate DoAllocate(Layout layout)167 void* DoAllocate(Layout layout) override { 168 // Reserve one byte to save the bucket index. 169 return impl_.Allocate(layout.Extend(1)); 170 } 171 172 /// @copydoc Deallocator::DoDeallocate DoDeallocate(void * ptr)173 void DoDeallocate(void* ptr) override { impl_.Deallocate(ptr); } 174 175 /// @copydoc Deallocator::GetInfo DoGetInfo(InfoType info_type,const void * ptr)176 Result<Layout> DoGetInfo(InfoType info_type, const void* ptr) const override { 177 switch (info_type) { 178 case InfoType::kUsableLayoutOf: { 179 Layout layout; 180 PW_TRY_ASSIGN(layout, impl_.GetLayout(ptr)); 181 return Layout(layout.size() - 1, layout.alignment()); 182 } 183 case InfoType::kAllocatedLayoutOf: 184 return impl_.GetLayout(ptr); 185 case InfoType::kCapacity: 186 return Layout(impl_.GetCapacity(), kMinOuterSize); 187 case InfoType::kRecognizes: { 188 Layout layout; 189 PW_TRY_ASSIGN(layout, impl_.GetLayout(ptr)); 190 return Layout(); 191 } 192 case InfoType::kRequestedLayoutOf: 193 default: 194 return Status::Unimplemented(); 195 } 196 } 197 198 std::array<BucketType, kNumBuckets> buckets_; 199 internal::GenericBuddyAllocator impl_; 200 }; 201 202 } // namespace pw::allocator 203