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_alignment/alignment.h" 20 #include "pw_allocator/allocator.h" 21 #include "pw_allocator/bucket.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 /// Size-independent buddy allocator. 30 /// 31 /// This allocator allocates chunks of memory whose sizes are powers of two. 32 /// See also https://en.wikipedia.org/wiki/Buddy_memory_allocation. 33 /// 34 /// Compared to `BuddyAllocator`, this implementation is size-agnostic with 35 /// respect to the number of buckets. 36 class GenericBuddyAllocator final { 37 public: 38 static constexpr Capabilities kCapabilities = 39 kImplementsGetUsableLayout | kImplementsGetAllocatedLayout | 40 kImplementsGetCapacity | kImplementsRecognizes; 41 42 /// Constructs a buddy allocator. 43 /// 44 /// @param[in] buckets Storage for buckets of free chunks. 45 /// @param[in] min_chunk_size Size of the chunks in the first bucket. 46 GenericBuddyAllocator(span<Bucket> buckets, size_t min_chunk_size); 47 48 /// Sets the memory used to allocate chunks. 49 void Init(ByteSpan region); 50 51 /// @copydoc Allocator::Allocate 52 void* Allocate(Layout layout); 53 54 /// @copydoc Deallocator::Deallocate 55 void Deallocate(void* ptr); 56 57 /// Returns the total capacity of this allocator. GetCapacity()58 size_t GetCapacity() const { return region_.size(); } 59 60 /// Returns the allocated layout for a given pointer. 61 Result<Layout> GetLayout(const void* ptr) const; 62 63 /// Ensures all allocations have been freed. Crashes with a diagnostic message 64 /// If any allocations remain outstanding. 65 void CrashIfAllocated(); 66 67 private: 68 span<Bucket> buckets_; 69 ByteSpan region_; 70 }; 71 72 } // namespace internal 73 74 /// Allocator that uses the buddy memory allocation algorithm. 75 /// 76 /// This allocator allocates chunks of memory whose sizes are powers of two. 77 /// This allows the allocator to satisfy requests to acquire and release memory 78 /// very quickly, at the possible cost of higher internal fragmentation. In 79 /// particular: 80 /// 81 /// * The maximum alignment for this allocator is `kMinChunkSize`. 82 /// * The minimum size of an allocation is `kMinChunkSize`. Less may be 83 /// requested, but it will be satisfied by a minimal chunk. 84 /// * The maximum size of an allocation is `kMinChunkSize << (kNumBuckets - 1)`. 85 /// 86 /// Use this allocator if you know the needed sizes are close to but less than 87 /// chunk sizes and you need high allocator performance. 88 /// 89 /// @tparam kMinChunkSize Size of the smallest allocatable chunk. Must be a 90 /// a power of two. All allocations will use at least 91 /// this much memory. 92 /// @tparam kNumBuckets Number of buckets. Must be at least 1. Each 93 /// additional bucket allows combining chunks into 94 /// larger chunks. 95 template <size_t kMinChunkSize, size_t kNumBuckets> 96 class BuddyAllocator : public Allocator { 97 public: 98 static_assert((kMinChunkSize & (kMinChunkSize - 1)) == 0, 99 "kMinChunkSize must be a power of 2"); 100 101 /// Constructs an allocator. Callers must call `Init`. BuddyAllocator()102 BuddyAllocator() : impl_(buckets_, kMinChunkSize) {} 103 104 /// Constructs an allocator, and initializes it with the given memory region. 105 /// 106 /// @param[in] region Region of memory to use when satisfying allocation 107 /// requests. The region MUST be large enough to fit a 108 /// least one minimally-size chunk aligned to the size of 109 /// the chunk. BuddyAllocator(ByteSpan region)110 BuddyAllocator(ByteSpan region) : BuddyAllocator() { Init(region); } 111 112 /// Sets the memory region used by the allocator. 113 /// 114 /// @param[in] region Region of memory to use when satisfying allocation 115 /// requests. The region MUST be large enough to fit a 116 /// least one minimally-size chunk aligned to the size of 117 /// the chunk. Init(ByteSpan region)118 void Init(ByteSpan region) { impl_.Init(region); } 119 ~BuddyAllocator()120 ~BuddyAllocator() override { impl_.CrashIfAllocated(); } 121 122 private: 123 /// @copydoc Allocator::Allocate DoAllocate(Layout layout)124 void* DoAllocate(Layout layout) override { 125 // Reserve one byte to save the bucket index. 126 return impl_.Allocate(layout.Extend(1)); 127 } 128 129 /// @copydoc Deallocator::DoDeallocate DoDeallocate(void * ptr)130 void DoDeallocate(void* ptr) override { impl_.Deallocate(ptr); } 131 132 /// @copydoc Deallocator::GetInfo DoGetInfo(InfoType info_type,const void * ptr)133 Result<Layout> DoGetInfo(InfoType info_type, const void* ptr) const override { 134 switch (info_type) { 135 case InfoType::kUsableLayoutOf: { 136 Layout layout; 137 PW_TRY_ASSIGN(layout, impl_.GetLayout(ptr)); 138 return Layout(layout.size() - 1, layout.alignment()); 139 } 140 case InfoType::kAllocatedLayoutOf: 141 return impl_.GetLayout(ptr); 142 case InfoType::kCapacity: 143 return Layout(impl_.GetCapacity(), kMinChunkSize); 144 case InfoType::kRecognizes: { 145 Layout layout; 146 PW_TRY_ASSIGN(layout, impl_.GetLayout(ptr)); 147 return Layout(); 148 } 149 case InfoType::kRequestedLayoutOf: 150 default: 151 return Status::Unimplemented(); 152 } 153 } 154 155 std::array<internal::Bucket, kNumBuckets> buckets_; 156 internal::GenericBuddyAllocator impl_; 157 }; 158 159 } // namespace pw::allocator 160