Pigweed
C/C++ API Reference
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
Loading...
Searching...
No Matches
contiguous.h
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_allocator/hardening.h"
19#include "pw_bytes/span.h"
20
21namespace pw::allocator {
22namespace internal {
23
24// Trivial base class for trait support.
26
27} // namespace internal
28
44template <typename Derived>
46 protected:
47 constexpr explicit ContiguousBlock() {
48 // Assert within a function, since `Derived` is not complete when this type
49 // is defined.
50 static_assert(
51 is_block_v<Derived>,
52 "Types derived from ContiguousBlock must also derive from BasicBlock");
53 }
54
55 public:
58 constexpr Derived* Prev() const;
59
62 constexpr Derived* Next() const;
63
64 protected:
74 constexpr Derived* DoSplitFirst(size_t new_inner_size);
75
85 constexpr Derived* DoSplitLast(size_t new_inner_size);
86
93 constexpr void DoMergeNext();
94
96 constexpr bool DoCheckInvariants(bool strict) const;
97
98 private:
99 constexpr Derived* derived() { return static_cast<Derived*>(this); }
100 constexpr const Derived* derived() const {
101 return static_cast<const Derived*>(this);
102 }
103
105 constexpr Derived* PrevUnchecked() const;
106
108 constexpr Derived* NextUnchecked() const;
109
119 static constexpr Derived* Split(Derived*& block, size_t new_inner_size);
120
121 // PoisonableBlock calls DoSplitFirst, DoSplitLast, and DoMergeNext
122 template <typename>
123 friend class PoisonableBlock;
124};
125
127template <typename BlockType>
128struct is_contiguous : std::is_base_of<internal::ContiguousBase, BlockType> {};
129
131template <typename BlockType>
132constexpr bool is_contiguous_v = is_contiguous<BlockType>::value;
133
134namespace internal {
135
139
142void CheckNextMisaligned(const void* block,
143 const void* next,
144 bool next_is_aligned);
145
148void CheckNextPrevMismatched(const void* block,
149 const void* next,
150 const void* next_prev,
151 bool next_prev_matches);
152
155void CheckPrevMisaligned(const void* block,
156 const void* prev,
157 bool prev_is_aligned);
158
161void CheckPrevNextMismatched(const void* block,
162 const void* prev,
163 const void* prev_next,
164 bool prev_next_matches);
165
166} // namespace internal
167
168// Template method implementations.
169
170template <typename Derived>
171constexpr Derived* ContiguousBlock<Derived>::Prev() const {
172 if constexpr (Hardening::kIncludesDebugChecks) {
173 derived()->CheckInvariants();
174 }
175 return PrevUnchecked();
176}
177
178template <typename Derived>
179constexpr Derived* ContiguousBlock<Derived>::PrevUnchecked() const {
180 size_t prev_outer_size = derived()->PrevOuterSizeUnchecked();
181 if (prev_outer_size == 0) {
182 return nullptr;
183 }
184 auto addr = cpp20::bit_cast<uintptr_t>(this);
185 Hardening::Decrement(addr, prev_outer_size);
186 return std::launder(reinterpret_cast<Derived*>(addr));
187}
188
189template <typename Derived>
190constexpr Derived* ContiguousBlock<Derived>::Next() const {
191 if constexpr (Hardening::kIncludesDebugChecks) {
192 derived()->CheckInvariants();
193 }
194 return NextUnchecked();
195}
196
197template <typename Derived>
198constexpr Derived* ContiguousBlock<Derived>::NextUnchecked() const {
199 if (derived()->IsLastUnchecked()) {
200 return nullptr;
201 }
202 size_t outer_size = derived()->OuterSizeUnchecked();
203 auto addr = cpp20::bit_cast<uintptr_t>(this);
204 Hardening::Increment(addr, outer_size);
205 return std::launder(reinterpret_cast<Derived*>(addr));
206}
207
208template <typename Derived>
210 size_t new_inner_size) {
211 Derived* next = derived()->Next();
212 size_t new_outer_size = Derived::kBlockOverhead + new_inner_size;
213 ByteSpan bytes(derived()->UsableSpace(), derived()->InnerSize());
214 bytes = bytes.subspan(new_inner_size);
215 auto* trailing = Derived::AsBlock(bytes);
216 derived()->SetNext(new_outer_size, trailing);
217 trailing->SetNext(bytes.size(), next);
218 return trailing;
219}
220
221template <typename Derived>
223 size_t new_inner_size) {
224 size_t new_outer_size = Derived::kBlockOverhead + new_inner_size;
225 return DoSplitFirst(derived()->InnerSize() - new_outer_size);
226}
227
228template <typename Derived>
230 Derived* next = derived()->Next();
231 if (next != nullptr) {
232 size_t outer_size = derived()->OuterSize() + next->OuterSize();
233 derived()->SetNext(outer_size, next->Next());
234 }
235}
236
237template <typename Derived>
238constexpr bool ContiguousBlock<Derived>::DoCheckInvariants(bool strict) const {
239 bool valid = true;
240
241 Derived* next = derived()->NextUnchecked();
242 if (next != nullptr) {
243 valid &= (cpp20::bit_cast<uintptr_t>(next) % Derived::kAlignment) == 0;
244 if constexpr (Hardening::kIncludesDebugChecks) {
245 internal::CheckNextMisaligned(this, next, valid || !strict);
246 }
247
248 Derived* next_prev = next->PrevUnchecked();
249 valid &= this == next_prev;
250 if constexpr (Hardening::kIncludesDebugChecks) {
251 internal::CheckNextPrevMismatched(
252 this, next, next_prev, valid || !strict);
253 }
254 }
255
256 Derived* prev = derived()->PrevUnchecked();
257 if (prev != nullptr) {
258 valid &= (cpp20::bit_cast<uintptr_t>(prev) % Derived::kAlignment) == 0;
259 if constexpr (Hardening::kIncludesDebugChecks) {
260 internal::CheckPrevMisaligned(this, prev, valid || !strict);
261 }
262
263 Derived* prev_next = prev->NextUnchecked();
264 valid &= this == prev_next;
265 if constexpr (Hardening::kIncludesDebugChecks) {
266 internal::CheckPrevNextMismatched(
267 this, prev, prev_next, valid || !strict);
268 }
269 }
270
271 return valid;
272}
273
274} // namespace pw::allocator
Definition: contiguous.h:45
constexpr Derived * Prev() const
Definition: contiguous.h:171
constexpr bool DoCheckInvariants(bool strict) const
Performs the ContiguousBlock invariant checks.
Definition: contiguous.h:238
constexpr Derived * Next() const
Definition: contiguous.h:190
constexpr void DoMergeNext()
Definition: contiguous.h:229
constexpr Derived * DoSplitLast(size_t new_inner_size)
Definition: contiguous.h:222
constexpr Derived * DoSplitFirst(size_t new_inner_size)
Definition: contiguous.h:209
Definition: contiguous.h:25
Trait type that allow interrogating a block as to whether it is contiguous.
Definition: contiguous.h:128