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