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