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(size_t min_size, 75 size_t desired_size, 76 bool needs_contiguous) final; 77 78 /// Allocates a contiguous buffer of exactly ``size`` bytes. 79 pw::Result<MultiBuf> InternalAllocateContiguous(size_t size) 80 PW_EXCLUSIVE_LOCKS_REQUIRED(lock_); 81 82 /// An unused block of memory in the allocator's data area. 83 /// 84 /// This describes a single contiguous chunk of memory in the allocator's data 85 /// area that is not yet tracked by a ``LinkedRegionTracker`` and therefore 86 /// not referenced by any ``Chunk``s. 87 struct FreeBlock final { 88 /// An ``iterator`` pointing just before this block. 89 /// This is meant for use with ``insert_after`` to add new elements 90 /// within the block. 91 IntrusiveList<internal::LinkedRegionTracker>::iterator iter; 92 93 /// The span of unused memory. 94 ByteSpan span; 95 }; 96 97 pw::Result<OwnedChunk> InsertRegion(const FreeBlock&) 98 PW_EXCLUSIVE_LOCKS_REQUIRED(lock_); 99 100 /// A description of the unused memory within this allocator's data area. 101 struct AvailableMemorySize final { 102 /// The total number of unused bytes. 103 size_t total; 104 /// The number of bytes in the largest contiguous unused section. 105 size_t contiguous; 106 }; 107 108 /// Returns information about the amount of unused memory within this 109 /// allocator's data area. 110 AvailableMemorySize GetAvailableMemorySize() 111 PW_EXCLUSIVE_LOCKS_REQUIRED(lock_); 112 113 /// Whether to continue or stop iterating. 114 enum class ControlFlow { 115 Continue, 116 Break, 117 }; 118 119 /// Iterates over each unused section of memory in the data area. 120 /// 121 /// @param[in] function A function which accepts ``const FreeBlock&`` and 122 /// returns ``ControlFlow``. This function will be invoked once for every 123 /// unused section of memory in the data area. 124 template <typename Fn> ForEachFreeBlock(Fn function)125 void ForEachFreeBlock(Fn function) PW_EXCLUSIVE_LOCKS_REQUIRED(lock_) { 126 std::byte* last_used_end = data_area_.data(); 127 // We need to track only the `prev_iter` in order to ensure that we don't 128 // miss any blocks that ``function`` inserts. 129 auto prev_iter = regions_.before_begin(); 130 while (true) { 131 // Compute ``cur_iter`` by incrementing ``prev_iter``. 132 auto cur_iter = prev_iter; 133 cur_iter++; 134 if (cur_iter == regions_.end()) { 135 break; 136 } 137 size_t unused = cur_iter->region_.data() - last_used_end; 138 if (unused != 0) { 139 ControlFlow cf = function({prev_iter, ByteSpan(last_used_end, unused)}); 140 if (cf == ControlFlow::Break) { 141 return; 142 } 143 } 144 last_used_end = cur_iter->region_.data() + cur_iter->region_.size(); 145 prev_iter = cur_iter; 146 } 147 size_t unused = (data_area_.data() + data_area_.size()) - last_used_end; 148 if (unused != 0) { 149 function({prev_iter, ByteSpan(last_used_end, unused)}); 150 } 151 } 152 153 pw::sync::InterruptSpinLock lock_; 154 IntrusiveList<internal::LinkedRegionTracker> regions_ PW_GUARDED_BY(lock_); 155 pw::allocator::Allocator& metadata_alloc_; 156 const ByteSpan data_area_; 157 158 friend class internal::LinkedRegionTracker; 159 }; 160 161 } // namespace pw::multibuf 162