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 "lib/stdcompat/bit.h"
17 #include "pw_allocator/block/basic.h"
18 #include "pw_bytes/span.h"
19 #include "pw_result/result.h"
20 #include "pw_status/status.h"
21
22 namespace pw::allocator {
23 namespace internal {
24
25 // Trivial base class for trait support.
26 struct ContiguousBase {};
27
28 } // namespace internal
29
30 /// Mix-in for blocks that collectively represent a contiguous region of memory.
31 ///
32 /// Contiguous blocks can be split into smaller blocks and merged when adjacent.
33 ///
34 /// Block mix-ins are stateless and trivially constructible. See `BasicBlock`
35 /// for details on how mix-ins can be combined to implement blocks.
36 ///
37 /// This mix-in requires its derived type also derive from `BasicBlock`, and
38 /// provide the following symbols:
39 ///
40 /// - static constexpr size_t MaxAddressableSize()
41 /// - Size of the largest region that can be addressed by a block.
42 /// - static Derived* AsBlock(BytesSpan)
43 /// - Instantiates and returns a block for the given region of memory.
44 /// - size_t PrevOuterSizeUnchecked() const
45 /// - Returns the outer size of the previous block, if any, or zero. Must be
46 /// multiple of `kAlignment`.
47 /// - bool IsLastUnchecked() const
48 /// - Returns whether this block is the last block.
49 template <typename Derived>
50 class ContiguousBlock : public internal::ContiguousBase {
51 protected:
ContiguousBlock()52 constexpr explicit ContiguousBlock() {
53 // Assert within a function, since `Derived` is not complete when this type
54 // is defined.
55 static_assert(
56 is_block_v<Derived>,
57 "Types derived from ContiguousBlock must also derive from BasicBlock");
58 }
59
60 public:
61 static constexpr size_t kMaxAddressableSize = Derived::MaxAddressableSize();
62
63 /// @brief Creates the first block for a given memory region.
64 ///
65 /// @returns @rst
66 ///
67 /// .. pw-status-codes::
68 ///
69 /// OK: Returns a block representing the region.
70 ///
71 /// INVALID_ARGUMENT: The region is null.
72 ///
73 /// RESOURCE_EXHAUSTED: The region is too small for a block.
74 ///
75 /// OUT_OF_RANGE: The region is larger than `kMaxAddressableSize`.
76 ///
77 /// @endrst
78 static Result<Derived*> Init(ByteSpan region);
79
80 /// @returns the block immediately before this one, or null if this is the
81 /// first block.
82 inline Derived* Prev() const;
83
84 /// @returns the block immediately after this one, or null if this is the last
85 /// block.
86 inline Derived* Next() const;
87
88 protected:
89 /// Split a block into two smaller blocks.
90 ///
91 /// This method splits a block into a leading block of the given
92 /// `new_inner_size` and a trailing block, and returns the trailing space as a
93 /// new block.
94 ///
95 /// @pre The block must not be in use.
96 /// @pre The block must have enough usable space for the requested size.
97 /// @pre The space remaining after a split can hold a new block.
98 Derived* DoSplitFirst(size_t new_inner_size);
99
100 /// Split a block into two smaller blocks.
101 ///
102 /// This method splits a block into a leading block and a trailing block of
103 /// the given `new_inner_size`, and returns the trailing space is returned as
104 /// a new block.
105 ///
106 /// @pre The block must not be in use.
107 /// @pre The block must have enough usable space for the requested size.
108 /// @pre The space remaining after a split can hold a new block.
109 Derived* DoSplitLast(size_t new_inner_size);
110
111 /// Merges this block with next block.
112 ///
113 /// This method is static in order to consume and replace the given block
114 /// pointer with a pointer to the new, larger block.
115 ///
116 /// @pre The blocks must not be in use.
117 void DoMergeNext();
118
119 /// Performs the ContiguousBlock invariant checks.
120 bool DoCheckInvariants(bool crash_on_failure) const;
121
122 private:
derived()123 constexpr Derived* derived() { return static_cast<Derived*>(this); }
derived()124 constexpr const Derived* derived() const {
125 return static_cast<const Derived*>(this);
126 }
127
128 /// @copydoc Prev
129 Derived* PrevUnchecked() const;
130
131 /// @copydoc Next
132 Derived* NextUnchecked() const;
133
134 /// Split a block into two smaller blocks.
135 ///
136 /// This method is static in order to consume and replace the given block
137 /// pointer with a pointer to the new, smaller block with an inner size of
138 /// `new_inner_size` The remaining space will be returned as a new block.
139 ///
140 /// @pre The block must not be in use.
141 /// @pre The block must have enough usable space for the requested size.
142 /// @pre The space remaining after a split can hold a new block.
143 static Derived* Split(Derived*& block, size_t new_inner_size);
144
145 /// Consumes the block and returns as a span of bytes.
146 static ByteSpan AsBytes(Derived*&& block);
147
148 // PoisonableBlock calls DoSplitFirst, DoSplitLast, and DoMergeNext
149 template <typename>
150 friend class PoisonableBlock;
151 };
152
153 /// Trait type that allow interrogating a block as to whether it is contiguous.
154 template <typename BlockType>
155 struct is_contiguous : std::is_base_of<internal::ContiguousBase, BlockType> {};
156
157 /// Helper variable template for `is_contiguous<BlockType>::value`.
158 template <typename BlockType>
159 inline constexpr bool is_contiguous_v = is_contiguous<BlockType>::value;
160
161 namespace internal {
162
163 /// Functions to crash with an error message describing which block invariant
164 /// has been violated. These functions are implemented independent of any
165 /// template parameters to allow them to use `PW_CHECK`.
166 void CrashNextMisaligned(uintptr_t addr, uintptr_t next);
167 void CrashNextPrevMismatched(uintptr_t addr,
168 uintptr_t next,
169 uintptr_t next_prev);
170 void CrashPrevMisaligned(uintptr_t addr, uintptr_t prev);
171 void CrashPrevNextMismatched(uintptr_t addr,
172 uintptr_t prev,
173 uintptr_t prev_next);
174
175 } // namespace internal
176
177 // Template method implementations.
178
179 template <typename Derived>
Init(ByteSpan region)180 Result<Derived*> ContiguousBlock<Derived>::Init(ByteSpan region) {
181 region = GetAlignedSubspan(region, Derived::kAlignment);
182 if (region.size() <= Derived::kBlockOverhead) {
183 return Status::ResourceExhausted();
184 }
185 if (region.size() > Derived::MaxAddressableSize()) {
186 return Status::OutOfRange();
187 }
188 auto* block = Derived::AsBlock(region);
189 block->CheckInvariantsIfStrict();
190 return block;
191 }
192
193 template <typename Derived>
Prev()194 Derived* ContiguousBlock<Derived>::Prev() const {
195 derived()->CheckInvariantsIfStrict();
196 return PrevUnchecked();
197 }
198
199 template <typename Derived>
PrevUnchecked()200 Derived* ContiguousBlock<Derived>::PrevUnchecked() const {
201 size_t prev_outer_size = derived()->PrevOuterSizeUnchecked();
202 if (prev_outer_size == 0) {
203 return nullptr;
204 }
205 auto addr = cpp20::bit_cast<uintptr_t>(this);
206 PW_ASSERT(!PW_SUB_OVERFLOW(addr, prev_outer_size, &addr));
207 return std::launder(reinterpret_cast<Derived*>(addr));
208 }
209
210 template <typename Derived>
Next()211 Derived* ContiguousBlock<Derived>::Next() const {
212 derived()->CheckInvariantsIfStrict();
213 return NextUnchecked();
214 }
215
216 template <typename Derived>
NextUnchecked()217 Derived* ContiguousBlock<Derived>::NextUnchecked() const {
218 if (derived()->IsLastUnchecked()) {
219 return nullptr;
220 }
221 size_t outer_size = derived()->OuterSizeUnchecked();
222 auto addr = cpp20::bit_cast<uintptr_t>(this);
223 PW_ASSERT(!PW_ADD_OVERFLOW(addr, outer_size, &addr));
224 return std::launder(reinterpret_cast<Derived*>(addr));
225 }
226
227 template <typename Derived>
DoSplitFirst(size_t new_inner_size)228 Derived* ContiguousBlock<Derived>::DoSplitFirst(size_t new_inner_size) {
229 Derived* next = derived()->Next();
230 size_t new_outer_size = Derived::kBlockOverhead + new_inner_size;
231 ByteSpan bytes(derived()->UsableSpace(), derived()->InnerSize());
232 bytes = bytes.subspan(new_inner_size);
233 auto* trailing = Derived::AsBlock(bytes);
234 derived()->SetNext(new_outer_size, trailing);
235 trailing->SetNext(bytes.size(), next);
236 return trailing;
237 }
238
239 template <typename Derived>
DoSplitLast(size_t new_inner_size)240 Derived* ContiguousBlock<Derived>::DoSplitLast(size_t new_inner_size) {
241 size_t new_outer_size = Derived::kBlockOverhead + new_inner_size;
242 return DoSplitFirst(derived()->InnerSize() - new_outer_size);
243 }
244
245 template <typename Derived>
DoMergeNext()246 void ContiguousBlock<Derived>::DoMergeNext() {
247 Derived* next = derived()->Next();
248 if (next != nullptr) {
249 size_t outer_size = derived()->OuterSize() + next->OuterSize();
250 derived()->SetNext(outer_size, next->Next());
251 }
252 }
253
254 template <typename Derived>
DoCheckInvariants(bool crash_on_failure)255 bool ContiguousBlock<Derived>::DoCheckInvariants(bool crash_on_failure) const {
256 auto addr = cpp20::bit_cast<uintptr_t>(this);
257 Derived* next = derived()->NextUnchecked();
258 if (next != nullptr) {
259 auto next_addr = cpp20::bit_cast<uintptr_t>(next);
260 if (next_addr % Derived::kAlignment != 0) {
261 if (crash_on_failure) {
262 internal::CrashNextMisaligned(addr, next_addr);
263 }
264 return false;
265 }
266 Derived* next_prev = next->PrevUnchecked();
267 if (this != next_prev) {
268 if (crash_on_failure) {
269 auto next_prev_addr = cpp20::bit_cast<uintptr_t>(next_prev);
270 internal::CrashNextPrevMismatched(addr, next_addr, next_prev_addr);
271 }
272 return false;
273 }
274 }
275 Derived* prev = derived()->PrevUnchecked();
276 if (prev != nullptr) {
277 auto prev_addr = cpp20::bit_cast<uintptr_t>(prev);
278 if (prev_addr % Derived::kAlignment != 0) {
279 if (crash_on_failure) {
280 internal::CrashPrevMisaligned(addr, prev_addr);
281 }
282 return false;
283 }
284 Derived* prev_next = prev->NextUnchecked();
285 auto prev_next_addr = cpp20::bit_cast<uintptr_t>(prev_next);
286 if (this != prev_next) {
287 if (crash_on_failure) {
288 internal::CrashPrevNextMismatched(addr, prev_addr, prev_next_addr);
289 }
290 return false;
291 }
292 }
293 return true;
294 }
295
296 } // namespace pw::allocator
297