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 <cstddef>
17 #include <cstdint>
18 #include <new>
19 #include <type_traits>
20
21 #include "lib/stdcompat/bit.h"
22 #include "pw_allocator/hardening.h"
23 #include "pw_bytes/alignment.h"
24 #include "pw_result/result.h"
25 #include "pw_status/status.h"
26
27 namespace pw::allocator {
28 namespace internal {
29
30 /// Helper type that copies const-qualifers between types.
31 template <typename From, typename To>
32 struct CopyConst {
33 using type = std::conditional_t<std::is_const_v<From>,
34 std::add_const_t<To>,
35 std::remove_const_t<To>>;
36 };
37
38 template <typename From, typename To>
39 using copy_const_t = typename CopyConst<From, To>::type;
40
41 template <typename From, typename To>
42 using copy_const_ptr_t =
43 std::add_pointer_t<typename CopyConst<std::remove_pointer_t<From>,
44 std::remove_pointer_t<To>>::type>;
45
46 // Trivial base class for trait support.
47 struct BasicBase {};
48
49 } // namespace internal
50
51 /// Base mix-in for block implementations.
52 ///
53 /// This CRTP-style type can be combined with block mix-in types. Block mix-ins
54 /// are stateless and trivially constructible. Mix-ins require the derived class
55 /// to implement methods to access and modify state, such has how to return a
56 /// block's size or a pointer to its usable memory.
57 ///
58 /// The mix-ins also follow the NVI pattern. This allows mix-ins to layer
59 /// behavior for a particular method. For example, the implementation of
60 /// `AllocFirst` in `AlignableBlock` handles allocation with larger than default
61 /// alignment requirements, and delegates to `AllocatableBlock` for other
62 /// requests. The derived type provided by the concrete block implementation can
63 /// implement the public method that delegates to the correct mix-in.
64 /// Overridable methods are named `Do...`.
65 ///
66 /// These mix-ins guarantee a number of invariants hold at the beginning and end
67 /// of each regular public API call. Each mix-in can enforce invariants by
68 /// overriding `DoCheckInvariants`. The concrete block implementation should
69 /// override the same method by calling each of the relevant mix-in methods.
70 /// Calling a public API method within an implementation of `DoCheckInvariants`
71 /// will lead to infinite recursion. To avoid this, mix-ins provide and/or
72 /// require versions of methods named `...Unchecked` that skip checking
73 /// invariants. These should only be used within the context of
74 /// `DoCheckInvariants` or other `...Unchecked` methods.
75 ///
76 /// This mix-in requires its derived type provide the following symbols:
77 ///
78 /// - static constexpr size_t DefaultAlignment()
79 /// - Returns the alignment of the block type. Must be a power of two.
80 /// - static constexpr size_t BlockOverhead()
81 /// - Returns the size of the metadata at the start of a block, before its
82 /// usable space.
83 /// - static constexpr size_t MaxAddressableSize()
84 /// - Size of the largest region that can be addressed by a block.
85 /// - static constexpr size_t MinInnerSize()
86 /// - Returns the minimum inner size of a block. Can be 1 unless the usable
87 /// space is used to track blocks when they are free.
88 /// - static Derived* AsBlock(BytesSpan)
89 /// - Instantiates and returns a block for the given region of memory.
90 /// - size_t OuterSizeUnchecked() const
91 /// - Returns the size of the block. Must be multiple of `kAlignment`.
92 template <typename Derived>
93 class BasicBlock : public internal::BasicBase {
94 public:
95 static constexpr size_t kAlignment = Derived::DefaultAlignment();
96 static constexpr size_t kBlockOverhead =
97 AlignUp(Derived::BlockOverhead(), kAlignment);
98 static constexpr size_t kMinOuterSize =
99 kBlockOverhead + AlignUp(Derived::MinInnerSize(), kAlignment);
100
101 ~BasicBlock() = default;
102
103 // No copy or move.
104 BasicBlock(const BasicBlock& other) = delete;
105 BasicBlock& operator=(const BasicBlock& other) = delete;
106
107 /// @brief Creates the first block for a given memory region.
108 ///
109 /// @returns @rst
110 ///
111 /// .. pw-status-codes::
112 ///
113 /// OK: Returns a block representing the region.
114 ///
115 /// INVALID_ARGUMENT: The region is null.
116 ///
117 /// RESOURCE_EXHAUSTED: The region is too small for a block.
118 ///
119 /// OUT_OF_RANGE: The region is larger than `kMaxAddressableSize`.
120 ///
121 /// @endrst
122 static constexpr Result<Derived*> Init(ByteSpan region);
123
124 /// @returns A pointer to a `Block`, given a pointer to the start of the
125 /// usable space inside the block.
126 ///
127 /// This is the inverse of `UsableSpace()`.
128 ///
129 /// @warning This method does not do any checking; passing a random
130 /// pointer will return a non-null pointer.
131 template <typename Ptr>
132 static constexpr internal::copy_const_ptr_t<Ptr, Derived*> FromUsableSpace(
133 Ptr usable_space);
134
135 /// @returns A pointer to the usable space inside this block.
136 constexpr std::byte* UsableSpace();
137 constexpr const std::byte* UsableSpace() const;
UsableSpaceUnchecked()138 constexpr std::byte* UsableSpaceUnchecked() {
139 return UsableSpaceUncheckedImpl(this);
140 }
UsableSpaceUnchecked()141 constexpr const std::byte* UsableSpaceUnchecked() const {
142 return UsableSpaceUncheckedImpl(this);
143 }
144
145 /// @returns The outer size of a block from the corresponding inner size.
146 static constexpr size_t OuterSizeFromInnerSize(size_t inner_size);
147
148 /// @returns The inner size of a block from the corresponding outer size.
149 static constexpr size_t InnerSizeFromOuterSize(size_t outer_size);
150
151 /// @returns The total size of the block in bytes, including the header.
152 constexpr size_t OuterSize() const;
153
154 /// @returns The number of usable bytes inside the block.
155 constexpr size_t InnerSize() const;
156 constexpr size_t InnerSizeUnchecked() const;
157
158 /// @return whether a block is valid.
159 constexpr bool IsValid() const;
160
161 /// Like `IsValid`, but crashes if invalid.
162 constexpr bool CheckInvariants() const;
163
164 protected:
165 constexpr BasicBlock() = default;
166
167 /// Checks that the various block conditions that should always be true are
168 /// indeed true.
169 ///
170 /// Triggers a fatal error if `strict` is true.
171 constexpr bool DoCheckInvariants(bool strict) const;
172
173 private:
derived()174 constexpr const Derived* derived() const {
175 return static_cast<const Derived*>(this);
176 }
177
178 /// Static version of `UsableSpace` that preserves constness.
179 template <typename Ptr>
180 static constexpr internal::copy_const_ptr_t<Ptr, std::byte*>
181 UsableSpaceUncheckedImpl(Ptr block);
182 };
183
184 /// Trait type that allows interrogating whether a type is a block.
185 ///
186 template <typename T>
187 struct is_block : std::is_base_of<internal::BasicBase, T> {};
188
189 /// Helper variable template for `is_block<T>::value`.
190 template <typename T>
191 constexpr bool is_block_v = is_block<T>::value;
192
193 namespace internal {
194
195 /// Crashes with an error message about the given block being misaligned if
196 /// `is_aligned` is false.
197 void CheckMisaligned(const void* block, bool is_aligned);
198
199 } // namespace internal
200
201 // Template method implementations.
202
203 template <typename Derived>
Init(ByteSpan region)204 constexpr Result<Derived*> BasicBlock<Derived>::Init(ByteSpan region) {
205 region = GetAlignedSubspan(region, Derived::kAlignment);
206 if (region.size() <= Derived::kBlockOverhead) {
207 return Status::ResourceExhausted();
208 }
209 if (region.size() > Derived::MaxAddressableSize()) {
210 return Status::OutOfRange();
211 }
212 auto* block = Derived::AsBlock(region);
213 if constexpr (Hardening::kIncludesDebugChecks) {
214 block->CheckInvariants();
215 }
216 return block;
217 }
218
219 template <typename Derived>
220 template <typename Ptr>
221 constexpr internal::copy_const_ptr_t<Ptr, Derived*>
FromUsableSpace(Ptr usable_space)222 BasicBlock<Derived>::FromUsableSpace(Ptr usable_space) {
223 using BlockPtr = internal::copy_const_ptr_t<Ptr, Derived*>;
224 auto addr = cpp20::bit_cast<uintptr_t>(usable_space);
225 Hardening::Decrement(addr, kBlockOverhead);
226 auto* block = std::launder(reinterpret_cast<BlockPtr>(addr));
227 if constexpr (Hardening::kIncludesBasicChecks) {
228 block->CheckInvariants();
229 }
230 return block;
231 }
232
233 template <typename Derived>
UsableSpace()234 constexpr std::byte* BasicBlock<Derived>::UsableSpace() {
235 if constexpr (Hardening::kIncludesDebugChecks) {
236 CheckInvariants();
237 }
238 return UsableSpaceUnchecked();
239 }
240
241 template <typename Derived>
UsableSpace()242 constexpr const std::byte* BasicBlock<Derived>::UsableSpace() const {
243 if constexpr (Hardening::kIncludesDebugChecks) {
244 CheckInvariants();
245 }
246 return UsableSpaceUnchecked();
247 }
248
249 template <typename Derived>
250 template <typename Ptr>
251 constexpr internal::copy_const_ptr_t<Ptr, std::byte*>
UsableSpaceUncheckedImpl(Ptr block)252 BasicBlock<Derived>::UsableSpaceUncheckedImpl(Ptr block) {
253 using BytePtr = internal::copy_const_ptr_t<Derived, std::byte*>;
254 auto addr = cpp20::bit_cast<uintptr_t>(block);
255 Hardening::Increment(addr, kBlockOverhead);
256 return cpp20::bit_cast<BytePtr>(addr);
257 }
258
259 template <typename Derived>
OuterSizeFromInnerSize(size_t inner_size)260 constexpr size_t BasicBlock<Derived>::OuterSizeFromInnerSize(
261 size_t inner_size) {
262 size_t outer_size = inner_size;
263 Hardening::Increment(outer_size, kBlockOverhead);
264 return outer_size;
265 }
266
267 template <typename Derived>
InnerSizeFromOuterSize(size_t outer_size)268 constexpr size_t BasicBlock<Derived>::InnerSizeFromOuterSize(
269 size_t outer_size) {
270 size_t inner_size = outer_size;
271 Hardening::Decrement(inner_size, kBlockOverhead);
272 return inner_size;
273 }
274
275 template <typename Derived>
OuterSize()276 constexpr size_t BasicBlock<Derived>::OuterSize() const {
277 if constexpr (Hardening::kIncludesDebugChecks) {
278 CheckInvariants();
279 }
280 return derived()->OuterSizeUnchecked();
281 }
282
283 template <typename Derived>
InnerSize()284 constexpr size_t BasicBlock<Derived>::InnerSize() const {
285 if constexpr (Hardening::kIncludesDebugChecks) {
286 CheckInvariants();
287 }
288 return InnerSizeUnchecked();
289 }
290
291 template <typename Derived>
InnerSizeUnchecked()292 constexpr size_t BasicBlock<Derived>::InnerSizeUnchecked() const {
293 return InnerSizeFromOuterSize(derived()->OuterSizeUnchecked());
294 }
295
296 template <typename Derived>
IsValid()297 constexpr bool BasicBlock<Derived>::IsValid() const {
298 return derived()->DoCheckInvariants(/*strict=*/false);
299 }
300
301 template <typename Derived>
CheckInvariants()302 constexpr bool BasicBlock<Derived>::CheckInvariants() const {
303 return derived()->DoCheckInvariants(/*strict=*/true);
304 }
305
306 template <typename Derived>
DoCheckInvariants(bool strict)307 constexpr bool BasicBlock<Derived>::DoCheckInvariants(bool strict) const {
308 bool is_aligned = (cpp20::bit_cast<uintptr_t>(this) % kAlignment) == 0;
309 if constexpr (Hardening::kIncludesDebugChecks) {
310 internal::CheckMisaligned(this, is_aligned || !strict);
311 }
312 return is_aligned;
313 }
314
315 } // namespace pw::allocator
316