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 <optional> 17 18 #include "pw_async2/dispatcher.h" 19 #include "pw_multibuf/multibuf.h" 20 #include "pw_result/result.h" 21 #include "pw_sync/interrupt_spin_lock.h" 22 23 namespace pw::multibuf { 24 25 namespace internal { 26 class AllocationWaiter; 27 } // namespace internal 28 29 class MultiBufAllocationFuture; 30 31 /// Interface for allocating ``MultiBuf`` objects. 32 /// 33 /// A ``MultiBufAllocator`` differs from a regular ``pw::allocator::Allocator`` 34 /// in that they may provide support for: 35 /// - Asynchronous allocation. 36 /// - Non-contiguous buffer allocation. 37 /// - Internal header/footer reservation. 38 /// - Size-range allocation. 39 /// 40 /// In order to accomplish this, they return ``MultiBuf`` objects rather than 41 /// arbitrary pieces of memory. 42 /// 43 /// Additionally, ``MultiBufAllocator`` implementations may choose to store 44 /// their allocation metadata separately from the data itself. This allows for 45 /// things like allocation headers to be kept out of restricted DMA-capable or 46 /// shared-memory regions. 47 /// 48 /// NOTE: ``MultiBufAllocator``s *must* outlive any futures created from them. 49 class MultiBufAllocator { 50 public: 51 MultiBufAllocator() = default; 52 53 /// ```MultiBufAllocator`` is not copyable or movable. 54 MultiBufAllocator(MultiBufAllocator&) = delete; 55 MultiBufAllocator& operator=(MultiBufAllocator&) = delete; 56 MultiBufAllocator(MultiBufAllocator&&) = delete; 57 MultiBufAllocator& operator=(MultiBufAllocator&&) = delete; 58 ~MultiBufAllocator()59 virtual ~MultiBufAllocator() {} 60 61 //////////////// 62 // -- Sync -- // 63 //////////////// 64 65 /// Attempts to allocate a ``MultiBuf`` of exactly ``size`` bytes. 66 /// 67 /// Memory allocated by an arbitrary ``MultiBufAllocator`` does not provide 68 /// any alignment requirments, preferring instead to allow the allocator 69 /// maximum flexibility for placing regions (especially discontiguous 70 /// regions). 71 /// 72 /// @retval ``MultiBuf`` if the allocation was successful. 73 /// @retval ``nullopt_t`` if the memory is not currently available. 74 std::optional<MultiBuf> Allocate(size_t size); 75 76 /// Attempts to allocate a ``MultiBuf`` of at least ``min_size`` bytes and at 77 /// most ``desired_size`` bytes. 78 /// 79 /// Memory allocated by an arbitrary ``MultiBufAllocator`` does not provide 80 /// any alignment requirments, preferring instead to allow the allocator 81 /// maximum flexibility for placing regions (especially discontiguous 82 /// regions). 83 /// 84 /// @retval ``MultiBuf`` if the allocation was successful. 85 /// @retval ``nullopt_t`` if the memory is not currently available. 86 std::optional<MultiBuf> Allocate(size_t min_size, size_t desired_size); 87 88 /// Attempts to allocate a contiguous ``MultiBuf`` of exactly ``size`` 89 /// bytes. 90 /// 91 /// Memory allocated by an arbitrary ``MultiBufAllocator`` does not provide 92 /// any alignment requirments, preferring instead to allow the allocator 93 /// maximum flexibility for placing regions (especially discontiguous 94 /// regions). 95 /// 96 /// @retval ``MultiBuf`` with a single ``Chunk`` if the allocation was 97 /// successful. 98 /// @retval ``nullopt_t`` if the memory is not currently available. 99 std::optional<MultiBuf> AllocateContiguous(size_t size); 100 101 /// Attempts to allocate a contiguous ``MultiBuf`` of at least ``min_size`` 102 /// bytes and at most ``desired_size`` bytes. 103 /// 104 /// Memory allocated by an arbitrary ``MultiBufAllocator`` does not provide 105 /// any alignment requirments, preferring instead to allow the allocator 106 /// maximum flexibility for placing regions (especially discontiguous 107 /// regions). 108 /// 109 /// @retval ``MultiBuf`` with a single ``Chunk`` if the allocation was 110 /// successful. 111 /// @retval ``nullopt_t`` if the memory is not currently available. 112 std::optional<MultiBuf> AllocateContiguous(size_t min_size, 113 size_t desired_size); 114 115 ///////////////// 116 // -- Async -- // 117 ///////////////// 118 119 /// Asynchronously allocates a ``MultiBuf`` of exactly ``size`` bytes. 120 /// 121 /// Memory allocated by an arbitrary ``MultiBufAllocator`` does not provide 122 /// any alignment requirments, preferring instead to allow the allocator 123 /// maximum flexibility for placing regions (especially discontiguous 124 /// regions). 125 /// 126 /// @retval A ``MultiBufAllocationFuture`` which will yield a ``MultiBuf`` 127 /// when one is available. 128 MultiBufAllocationFuture AllocateAsync(size_t size); 129 130 /// Asynchronously allocates a ``MultiBuf`` of at least 131 /// ``min_size`` bytes and at most ``desired_size` bytes. 132 /// 133 /// Memory allocated by an arbitrary ``MultiBufAllocator`` does not provide 134 /// any alignment requirments, preferring instead to allow the allocator 135 /// maximum flexibility for placing regions (especially discontiguous 136 /// regions). 137 /// 138 /// @retval A ``MultiBufAllocationFuture`` which will yield a ``MultiBuf`` 139 /// when one is available. 140 MultiBufAllocationFuture AllocateAsync(size_t min_size, size_t desired_size); 141 142 /// Asynchronously allocates a contiguous ``MultiBuf`` of exactly ``size`` 143 /// bytes. 144 /// 145 /// Memory allocated by an arbitrary ``MultiBufAllocator`` does not provide 146 /// any alignment requirments, preferring instead to allow the allocator 147 /// maximum flexibility for placing regions (especially discontiguous 148 /// regions). 149 /// 150 /// @retval A ``MultiBufAllocationFuture`` which will yield an ``MultiBuf`` 151 /// consisting of a single ``Chunk`` when one is available. 152 MultiBufAllocationFuture AllocateContiguousAsync(size_t size); 153 154 /// Asynchronously allocates an ``OwnedChunk`` of at least 155 /// ``min_size`` bytes and at most ``desired_size`` bytes. 156 /// 157 /// @retval A ``MultiBufAllocationFuture`` which will yield an ``MultiBuf`` 158 /// consisting of a single ``Chunk`` when one is available. 159 MultiBufAllocationFuture AllocateContiguousAsync(size_t min_size, 160 size_t desired_size); 161 162 protected: 163 /// Awakens callers asynchronously waiting for allocations of at most 164 /// ``size_available`` bytes or at most ``contiguous_size_available`` 165 /// contiguous bytes. 166 /// 167 /// This function should be invoked by implementations of 168 /// ``MultiBufAllocator`` when more memory becomes available to allocate. 169 void MoreMemoryAvailable(size_t size_available, 170 size_t contiguous_size_available); 171 172 private: 173 friend class MultiBufAllocationFuture; 174 friend class internal::AllocationWaiter; 175 176 /// Attempts to allocate a ``MultiBuf`` of at least ``min_size`` bytes and at 177 /// most ``desired_size`` bytes. 178 /// 179 /// @returns @rst 180 /// 181 /// .. pw-status-codes:: 182 /// 183 /// OK: Returns the buffer if the allocation was successful. 184 /// 185 /// RESOURCE_EXHAUSTED: Insufficient memory is available currently. 186 /// 187 /// OUT_OF_RANGE: This amount of memory will not become possible to 188 /// allocate in the future, or this allocator is unable to signal via 189 /// ``MoreMemoryAvailable`` (this will result in asynchronous allocations 190 /// failing immediately on OOM). 191 /// 192 /// @endrst 193 virtual pw::Result<MultiBuf> DoAllocate(size_t min_size, 194 size_t desired_size, 195 bool needs_contiguous) = 0; 196 197 void AddWaiter(internal::AllocationWaiter*) PW_LOCKS_EXCLUDED(lock_); 198 void AddWaiterLocked(internal::AllocationWaiter*) 199 PW_EXCLUSIVE_LOCKS_REQUIRED(lock_); 200 void RemoveWaiter(internal::AllocationWaiter*) PW_LOCKS_EXCLUDED(lock_); 201 void RemoveWaiterLocked(internal::AllocationWaiter*) 202 PW_EXCLUSIVE_LOCKS_REQUIRED(lock_); 203 204 sync::InterruptSpinLock lock_; 205 internal::AllocationWaiter* first_waiter_ PW_GUARDED_BY(lock_) = nullptr; 206 }; 207 208 namespace internal { 209 210 /// An object used to receive notifications once a certain amount of memory 211 /// becomes available within a ``MultiBufAllocator``. 212 /// 213 /// When attempting to allocate memory from a ``MultiBufAllocator``, 214 /// allocations may fail due to currently-insufficient memory. 215 /// If this happens, the caller may want to wait for the memory to become 216 /// available in the future. 217 /// 218 /// AllocationWaiter stores the requirements of the allocation along with 219 /// a ``Waker`` object. When the associated ``MultiBufAllocator`` regains 220 /// sufficient memory in order to allow the allocation to proceed 221 /// (triggered by a call to ``MoreMemoryAvailable``) the ``MultiBufAllocator`` 222 /// will wake any ``AllocationWaiter`` that may now be able to succeed. 223 class AllocationWaiter { 224 public: 225 /// Creates a new ``AllocationWaiter`` which waits for ``min_size`` bytes to 226 /// come available in ``allocator``. AllocationWaiter(MultiBufAllocator & allocator,size_t min_size,size_t desired_size,bool needs_contiguous)227 AllocationWaiter(MultiBufAllocator& allocator, 228 size_t min_size, 229 size_t desired_size, 230 bool needs_contiguous) 231 : allocator_(&allocator), 232 waker_(), 233 next_(nullptr), 234 min_size_(min_size), 235 desired_size_(desired_size), 236 needs_contiguous_(needs_contiguous) {} 237 238 AllocationWaiter(AllocationWaiter&&); 239 AllocationWaiter& operator=(AllocationWaiter&&); 240 ~AllocationWaiter(); 241 242 /// Returns whether or not an allocation should be attempted. 243 /// 244 /// Allocations should be attempted when the waiter is first created, then 245 /// once each time the ``AllocationWaiter`` is notified that sufficient 246 /// bytes have become available. ShouldAttemptAllocate()247 bool ShouldAttemptAllocate() const { return waker_.IsEmpty(); } 248 249 /// Un-registers the current ``Waker``. ClearWaker()250 void ClearWaker() { waker_.Clear(); } 251 252 /// Sets a new ``Waker`` to receive wakeups when this ``AllocationWaiter`` is 253 /// awoken. SetWaker(async2::Waker && waker)254 void SetWaker(async2::Waker&& waker) { waker_ = std::move(waker); } 255 256 /// Returns the ``allocator`` associated with this ``AllocationWaiter``. allocator()257 MultiBufAllocator& allocator() { return *allocator_; } 258 259 /// Returns the ``min_size`` this ``AllocationWaiter`` is waiting for. min_size()260 size_t min_size() const { return min_size_; } 261 262 /// Returns the ``desired_size`` this ``AllocationWaiter`` is hoping for. desired_size()263 size_t desired_size() const { return desired_size_; } 264 265 /// Return whether this ``AllocationWaker`` is waiting for contiguous 266 /// sections of memory only. needs_contiguous()267 size_t needs_contiguous() const { return needs_contiguous_; } 268 269 private: 270 friend class ::pw::multibuf::MultiBufAllocator; 271 272 // The allocator this waiter is tied to. 273 // 274 // This must only be mutated in either the constructor, move constructor, 275 // or move assignment, and only after removing this waiter from the 276 // ``allocator_``'s list so that the ``allocator_`` does not try to access the 277 // waiter. 278 MultiBufAllocator* allocator_; 279 280 // The waker to wake when a suitably-sized allocation becomes available. 281 // The ``Waker`` class is thread-safe, so mutations to this value can occur 282 // without additional synchronization. 283 async2::Waker waker_; 284 285 // Pointer to the next ``AllocationWaiter`` waiting for an allocation from 286 // ``allocator_``. 287 AllocationWaiter* next_ PW_GUARDED_BY(allocator_->lock_); 288 289 // The properties of the kind of allocation being waited for. 290 // 291 // These values must only be mutated in either the constructor, move 292 // constructor, or move assignment, and only after removing this waiter from 293 // the ``allocator_``'s list so that the ``allocator_`` does not try to access 294 // them while they are being mutated. 295 size_t min_size_; 296 size_t desired_size_; 297 bool needs_contiguous_; 298 }; 299 300 } // namespace internal 301 302 /// An object that asynchronously yields a ``MultiBuf`` when ``Pend``ed. 303 /// 304 /// See ``pw::async2`` for details on ``Pend`` and how it is used to build 305 /// asynchronous tasks. 306 class MultiBufAllocationFuture { 307 public: MultiBufAllocationFuture(MultiBufAllocator & allocator,size_t min_size,size_t desired_size,bool needs_contiguous)308 MultiBufAllocationFuture(MultiBufAllocator& allocator, 309 size_t min_size, 310 size_t desired_size, 311 bool needs_contiguous) 312 : waiter_(allocator, min_size, desired_size, needs_contiguous) {} 313 async2::Poll<std::optional<MultiBuf>> Pend(async2::Context& cx); min_size()314 size_t min_size() const { return waiter_.min_size(); } desired_size()315 size_t desired_size() const { return waiter_.desired_size(); } needs_contiguous()316 bool needs_contiguous() const { return waiter_.needs_contiguous(); } 317 318 private: 319 friend class MultiBufAllocator; 320 internal::AllocationWaiter waiter_; 321 322 async2::Poll<std::optional<MultiBuf>> TryAllocate(); 323 }; 324 325 } // namespace pw::multibuf 326