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 "pw_allocator/allocator.h" 17 #include "pw_containers/intrusive_list.h" 18 #include "pw_multibuf/allocator.h" 19 #include "pw_multibuf/multibuf.h" 20 21 namespace pw::multibuf { 22 23 class SimpleAllocator; 24 25 namespace internal { 26 27 /// A ``ChunkRegionTracker`` for the allocated regions within a 28 /// ``SimpleAllocator``'s data area. 29 class LinkedRegionTracker final 30 : public ChunkRegionTracker, 31 public IntrusiveList<LinkedRegionTracker>::Item { 32 public: LinkedRegionTracker(SimpleAllocator & parent,ByteSpan region)33 LinkedRegionTracker(SimpleAllocator& parent, ByteSpan region) 34 : parent_(parent), region_(region) {} 35 ~LinkedRegionTracker() final; 36 37 // LinkedRegionTracker is not copyable nor movable. 38 LinkedRegionTracker(const LinkedRegionTracker&) = delete; 39 LinkedRegionTracker& operator=(const LinkedRegionTracker&) = delete; 40 LinkedRegionTracker(LinkedRegionTracker&&) = delete; 41 LinkedRegionTracker& operator=(LinkedRegionTracker&&) = delete; 42 43 protected: 44 void Destroy() final; Region()45 ByteSpan Region() const final { return region_; } 46 void* AllocateChunkClass() final; 47 void DeallocateChunkClass(void*) final; 48 49 private: 50 SimpleAllocator& parent_; 51 const ByteSpan region_; 52 53 friend class ::pw::multibuf::SimpleAllocator; 54 }; 55 56 } // namespace internal 57 58 /// A simple first-fit ``MultiBufAllocator``. 59 class SimpleAllocator : public MultiBufAllocator { 60 public: 61 /// Creates a new ``SimpleAllocator``. 62 /// 63 /// @param[in] data_area The region to use for storing chunk memory. 64 /// 65 /// @param[in] metadata_alloc The allocator to use for metadata tracking 66 /// the in-use regions. This allocator *must* be thread-safe if the resulting 67 /// buffers may travel to another thread. ``SynchronizedAllocator`` can be 68 /// used to create a thread-safe allocator from a non-thread-safe allocator. 69 /// 70 /// @param[in] alignment The alignment to use. All chunks allocated 71 /// by this allocator will start aligned with the specified alignment. The 72 /// alignment can change if the prefix Chunk methods are used. The supplied 73 /// `data_area` *must* be aligned (both start and end) to the specified 74 /// alignment. Defaults to 1. 75 SimpleAllocator(ByteSpan data_area, 76 pw::allocator::Allocator& metadata_alloc, 77 size_t alignment = 1); 78 79 private: 80 pw::Result<MultiBuf> DoAllocate( 81 size_t min_size, 82 size_t desired_size, 83 ContiguityRequirement contiguity_requirement) final; 84 DoGetBackingCapacity()85 std::optional<size_t> DoGetBackingCapacity() final { 86 return data_area_.size(); 87 } 88 89 /// Allocates a contiguous buffer of exactly ``size`` bytes. 90 pw::Result<MultiBuf> InternalAllocateContiguous(size_t size) 91 PW_EXCLUSIVE_LOCKS_REQUIRED(lock_); 92 93 /// An unused block of memory in the allocator's data area. 94 /// 95 /// This describes a single contiguous chunk of memory in the allocator's data 96 /// area that is not yet tracked by a ``LinkedRegionTracker`` and therefore 97 /// not referenced by any ``Chunk``s. 98 struct FreeBlock final { 99 /// An ``iterator`` pointing just before this block. 100 /// This is meant for use with ``insert_after`` to add new elements 101 /// within the block. 102 IntrusiveList<internal::LinkedRegionTracker>::iterator iter; 103 104 /// The span of unused memory. 105 ByteSpan span; 106 }; 107 108 pw::Result<OwnedChunk> InsertRegion(const FreeBlock&) 109 PW_EXCLUSIVE_LOCKS_REQUIRED(lock_); 110 111 /// A description of the unused memory within this allocator's data area. 112 struct AvailableMemorySize final { 113 /// The total number of unused bytes. 114 size_t total; 115 /// The number of bytes in the largest contiguous unused section. 116 size_t contiguous; 117 }; 118 119 /// Returns information about the amount of unused memory within this 120 /// allocator's data area. 121 AvailableMemorySize GetAvailableMemorySize() 122 PW_EXCLUSIVE_LOCKS_REQUIRED(lock_); 123 124 /// Whether to continue or stop iterating. 125 enum class ControlFlow { 126 Continue, 127 Break, 128 }; 129 130 /// Iterates over each unused section of memory in the data area. 131 /// 132 /// @param[in] function A function which accepts ``const FreeBlock&`` and 133 /// returns ``ControlFlow``. This function will be invoked once for every 134 /// unused section of memory in the data area. 135 template <typename Fn> ForEachFreeBlock(Fn function)136 void ForEachFreeBlock(Fn function) PW_EXCLUSIVE_LOCKS_REQUIRED(lock_) { 137 std::byte* last_used_end = data_area_.data(); 138 // We need to track only the `prev_iter` in order to ensure that we don't 139 // miss any blocks that ``function`` inserts. 140 auto prev_iter = regions_.before_begin(); 141 while (true) { 142 // Compute ``cur_iter`` by incrementing ``prev_iter``. 143 auto cur_iter = prev_iter; 144 cur_iter++; 145 if (cur_iter == regions_.end()) { 146 break; 147 } 148 size_t unused = cur_iter->region_.data() - last_used_end; 149 if (unused != 0) { 150 ControlFlow cf = function({prev_iter, ByteSpan(last_used_end, unused)}); 151 if (cf == ControlFlow::Break) { 152 return; 153 } 154 } 155 last_used_end = cur_iter->region_.data() + cur_iter->region_.size(); 156 prev_iter = cur_iter; 157 } 158 size_t unused = (data_area_.data() + data_area_.size()) - last_used_end; 159 if (unused != 0) { 160 function({prev_iter, ByteSpan(last_used_end, unused)}); 161 } 162 } 163 164 pw::sync::Mutex lock_; 165 IntrusiveList<internal::LinkedRegionTracker> regions_ PW_GUARDED_BY(lock_); 166 pw::allocator::Allocator& metadata_alloc_; 167 const ByteSpan data_area_; 168 const size_t alignment_; 169 170 friend class internal::LinkedRegionTracker; 171 }; 172 173 } // namespace pw::multibuf 174