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 <algorithm>
17 #include <cstddef>
18 #include <cstdint>
19 #include <cstring>
20
21 #include "lib/stdcompat/bit.h"
22 #include "pw_allocator/block/contiguous.h"
23 #include "pw_allocator/config.h"
24
25 namespace pw::allocator {
26 namespace internal {
27
28 // Trivial base class for trait support.
29 struct PoisonableBase {};
30
31 } // namespace internal
32
33 /// Mix-in for blocks that can be poisoned.
34 ///
35 /// A poisoned block's usable space contains pattern of data whose integrity can
36 /// be checked later for modification.
37 ///
38 /// Block mix-ins are stateless and trivially constructible. See `BasicBlock`
39 /// for details on how mix-ins can be combined to implement blocks.
40 ///
41 /// This mix-in requires its derived type also derive from `ContiguousBlock` and
42 /// provide the following method:
43 ///
44 /// - static consextpr size_t ReservedWhenFree()
45 /// - Indicates how many bytes should not be poisoned.
46 /// - bool IsPoisoned() const
47 /// - Returns whether the block is poisoned.
48 /// - void SetPoisoned(bool)
49 /// - Sets whether the block is poisoned.
50 template <typename Derived>
51 class PoisonableBlock : public internal::PoisonableBase {
52 protected:
PoisonableBlock()53 constexpr explicit PoisonableBlock() {
54 // Assert within a function, since `Derived` is not complete when this type
55 // is defined.
56 static_assert(is_contiguous_v<Derived>,
57 "Types derived from PoisonableBlock must also derive from "
58 "ContiguousBlock");
59 }
60
61 public:
62 static constexpr size_t kPoisonOffset = Derived::ReservedWhenFree();
63
64 /// Returns the value written to a block's usable space when poisoning.
GetPoisonWord()65 constexpr uintptr_t GetPoisonWord() const {
66 return derived()->DoGetPoisonWord();
67 }
68
69 /// Returns whether this block has been poisoned.
70 inline bool IsPoisoned() const;
71
72 /// Poisons the block's usable space.
73 ///
74 /// This method does nothing if the block is not free. The decision to poison
75 /// a block is delegated to the allocator to allow for more nuanced strategies
76 /// than simply all or nothing. For example, an allocator may want to balance
77 /// security and performance by only poisoning every n-th free block.
78 void Poison();
79
80 protected:
DoGetPoisonWord()81 constexpr uintptr_t DoGetPoisonWord() const {
82 // Hex dump looks like "defaced code is bad".
83 return static_cast<uintptr_t>(0xAD5bE10DDCCEFADEULL);
84 }
85
86 /// @copydoc ContiguousBlock::DoSplitFirst
87 Derived* DoSplitFirst(size_t new_inner_size);
88
89 /// @copydoc ContiguousBlock::DoSplitLast
90 Derived* DoSplitLast(size_t new_inner_size);
91
92 /// @copydoc ContiguousBlock::DoMergeNext
93 void DoMergeNext();
94
95 /// @copydoc BasicBlock::CheckInvariants
96 bool DoCheckInvariants(bool crash_on_failure) const;
97
98 /// Clears the poisoned state if a block is not free.
99 inline void SetFree(bool is_free);
100
101 private:
derived()102 constexpr Derived* derived() { return static_cast<Derived*>(this); }
derived()103 constexpr const Derived* derived() const {
104 return static_cast<const Derived*>(this);
105 }
106
107 /// Returns a pointer that can be used as an iterator to the poisonable
108 /// region.
PoisonableBegin()109 constexpr uintptr_t* PoisonableBegin() const {
110 auto addr = cpp20::bit_cast<uintptr_t>(derived()->UsableSpaceUnchecked());
111 addr = AlignUp(addr + kPoisonOffset, sizeof(uintptr_t*));
112 return cpp20::bit_cast<uintptr_t*>(addr);
113 }
114
115 /// Returns a pointer that can be used as a past-the-end iterator to the
116 /// poisonable region.
PoisonableEnd()117 constexpr uintptr_t* PoisonableEnd() const {
118 auto addr = cpp20::bit_cast<uintptr_t>(derived()->UsableSpaceUnchecked());
119 addr =
120 AlignDown(addr + derived()->InnerSizeUnchecked(), sizeof(uintptr_t*));
121 return cpp20::bit_cast<uintptr_t*>(addr);
122 }
123 };
124
125 /// Trait type that allow interrogating a block as to whether it is poisonable.
126 template <typename BlockType>
127 struct is_poisonable : std::is_base_of<internal::PoisonableBase, BlockType> {};
128
129 /// Helper variable template for `is_poisonable<BlockType>::value`.
130 template <typename BlockType>
131 inline constexpr bool is_poisonable_v = is_poisonable<BlockType>::value;
132
133 namespace internal {
134
135 /// Functions to crash with an error message describing which block invariant
136 /// has been violated. These functions are implemented independent of any
137 /// template parameters to allow it to use `PW_CHECK`.
138 void CrashPoisonCorrupted(uintptr_t addr);
139 void CrashPoisonedWhileInUse(uintptr_t addr);
140
141 } // namespace internal
142
143 // Template method implementations.
144
145 template <typename Derived>
IsPoisoned()146 bool PoisonableBlock<Derived>::IsPoisoned() const {
147 derived()->CheckInvariantsIfStrict();
148 return derived()->IsPoisonedUnchecked();
149 }
150
151 template <typename Derived>
Poison()152 void PoisonableBlock<Derived>::Poison() {
153 derived()->CheckInvariantsIfStrict();
154 auto* begin = PoisonableBegin();
155 auto* end = PoisonableEnd();
156 if (begin < end) {
157 std::fill(begin, end, derived()->GetPoisonWord());
158 derived()->SetPoisoned(true);
159 }
160 derived()->CheckInvariantsIfStrict();
161 }
162
163 template <typename Derived>
DoSplitFirst(size_t new_inner_size)164 Derived* PoisonableBlock<Derived>::DoSplitFirst(size_t new_inner_size) {
165 bool should_poison = derived()->IsPoisoned();
166 derived()->SetPoisoned(false);
167 Derived* trailing =
168 derived()->ContiguousBlock<Derived>::DoSplitFirst(new_inner_size);
169 if (should_poison) {
170 trailing->SetPoisoned(true);
171 }
172 return trailing;
173 }
174
175 template <typename Derived>
DoSplitLast(size_t new_inner_size)176 Derived* PoisonableBlock<Derived>::DoSplitLast(size_t new_inner_size) {
177 bool should_poison = derived()->IsPoisoned();
178 derived()->SetPoisoned(false);
179 Derived* trailing =
180 derived()->ContiguousBlock<Derived>::DoSplitLast(new_inner_size);
181 if (should_poison) {
182 derived()->SetPoisoned(true);
183 }
184 return trailing;
185 }
186
187 template <typename Derived>
DoMergeNext()188 void PoisonableBlock<Derived>::DoMergeNext() {
189 // Repoisoning is handle by the `BlockAllocator::DoDeallocate`.
190 derived()->SetPoisoned(false);
191 derived()->ContiguousBlock<Derived>::DoMergeNext();
192 }
193
194 template <typename Derived>
DoCheckInvariants(bool crash_on_failure)195 bool PoisonableBlock<Derived>::DoCheckInvariants(bool crash_on_failure) const {
196 auto addr = cpp20::bit_cast<uintptr_t>(this);
197 if (!derived()->IsPoisonedUnchecked()) {
198 return true;
199 }
200 if (!derived()->IsFreeUnchecked()) {
201 if (crash_on_failure) {
202 internal::CrashPoisonedWhileInUse(addr);
203 }
204 return false;
205 }
206 auto* begin = PoisonableBegin();
207 auto* end = PoisonableEnd();
208 if (begin >= end) {
209 return true;
210 }
211 bool poison_intact = std::all_of(
212 begin, end, [this](uintptr_t word) { return word == GetPoisonWord(); });
213 if (!poison_intact) {
214 if (crash_on_failure) {
215 internal::CrashPoisonCorrupted(addr);
216 }
217 return false;
218 }
219 return true;
220 }
221
222 template <typename Derived>
SetFree(bool is_free)223 void PoisonableBlock<Derived>::SetFree(bool is_free) {
224 if (!is_free) {
225 derived()->SetPoisoned(false);
226 }
227 }
228
229 } // namespace pw::allocator
230