1 // Copyright 2023 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
15 #include "pw_allocator/test_harness.h"
16
17 #include <algorithm>
18 #include <climits>
19 #include <cstddef>
20 #include <cstdint>
21 #include <type_traits>
22
23 #include "lib/stdcompat/bit.h"
24 #include "pw_assert/assert.h"
25 #include "pw_assert/check.h"
26
27 namespace pw::allocator::test {
28 namespace {
29
30 // Helper to allow static_assert'ing in constexpr-if branches, e.g. that a
31 // visitor for a std::variant are exhaustive.
32 template <typename T>
not_reached(T &)33 constexpr bool not_reached(T&) {
34 return false;
35 }
36
37 } // namespace
38
AlignmentFromLShift(size_t lshift,size_t size)39 size_t AlignmentFromLShift(size_t lshift, size_t size) {
40 constexpr size_t max_bits = (sizeof(size) * CHAR_BIT) - 1;
41 size_t num_bits =
42 size == 0 ? 1 : std::min(size_t(cpp20::bit_width(size)), max_bits);
43 size_t alignment = 1U << (lshift % num_bits);
44 return std::max(alignment, alignof(TestHarness::Allocation));
45 }
46
GenerateRequests(size_t max_size,size_t num_requests)47 void TestHarness::GenerateRequests(size_t max_size, size_t num_requests) {
48 for (size_t i = 0; i < num_requests; ++i) {
49 GenerateRequest(max_size);
50 }
51 Reset();
52 }
53
GenerateRequest(size_t max_size)54 void TestHarness::GenerateRequest(size_t max_size) {
55 Request request;
56 size_t dealloc_threshold = 40;
57 if (available_.has_value()) {
58 // This corresponds to a fixed 10% chance to reallocate and a sliding
59 // scale between:
60 // * when empty, an 80% chance to allocate and a 10% chance to deallocate
61 // * when full, a 30% chance to allocate and a 60% chance to deallocate
62 dealloc_threshold = 80 - (allocated_ * 50) / available_.value();
63 }
64 do {
65 size_t request_type;
66 prng_->GetInt(request_type);
67 request_type %= 100;
68 if (request_type < dealloc_threshold) {
69 request = GenerateAllocationRequest(max_size);
70 } else if (request_type < 90) {
71 request = GenerateDeallocationRequest();
72 } else {
73 request = GenerateReallocationRequest(max_size);
74 }
75 } while (!HandleRequest(request));
76 }
77
GenerateAllocationRequest(size_t max_size)78 AllocationRequest TestHarness::GenerateAllocationRequest(size_t max_size) {
79 AllocationRequest request;
80 request.size = GenerateSize(max_size);
81 uint8_t lshift;
82 prng_->GetInt(lshift);
83 request.alignment = AlignmentFromLShift(lshift, request.size);
84 return request;
85 }
86
GenerateDeallocationRequest()87 DeallocationRequest TestHarness::GenerateDeallocationRequest() {
88 DeallocationRequest request;
89 prng_->GetInt(request.index);
90 return request;
91 }
92
GenerateReallocationRequest(size_t max_size)93 ReallocationRequest TestHarness::GenerateReallocationRequest(size_t max_size) {
94 ReallocationRequest request;
95 prng_->GetInt(request.index);
96 request.new_size = GenerateSize(max_size);
97 return request;
98 }
99
GenerateSize(size_t max_size)100 size_t TestHarness::GenerateSize(size_t max_size) {
101 static constexpr size_t kMinSize = sizeof(TestHarness::Allocation);
102 size_t size = 0;
103 if (max_size_.has_value()) {
104 max_size = std::min(max_size, max_size_.value());
105 }
106 if (max_size <= kMinSize) {
107 return kMinSize;
108 }
109 prng_->GetInt(size);
110 size %= max_size - kMinSize;
111 return kMinSize + size;
112 }
113
HandleRequests(const Vector<Request> & requests)114 void TestHarness::HandleRequests(const Vector<Request>& requests) {
115 for (const auto& request : requests) {
116 HandleRequest(request);
117 }
118 Reset();
119 }
120
HandleRequest(const Request & request)121 bool TestHarness::HandleRequest(const Request& request) {
122 if (allocator_ == nullptr) {
123 allocator_ = Init();
124 PW_DCHECK_NOTNULL(allocator_);
125 }
126 return std::visit(
127 [this](auto&& r) {
128 using T = std::decay_t<decltype(r)>;
129
130 if constexpr (std::is_same_v<T, AllocationRequest>) {
131 Layout layout(r.size, r.alignment);
132 BeforeAllocate(layout);
133 void* ptr = allocator_->Allocate(layout);
134 AfterAllocate(ptr);
135 if (ptr != nullptr) {
136 AddAllocation(ptr, layout);
137 max_size_.reset();
138 } else {
139 max_size_ = std::max(layout.size() / 2, size_t(1));
140 }
141 } else if constexpr (std::is_same_v<T, DeallocationRequest>) {
142 Allocation* old = RemoveAllocation(r.index);
143 if (old == nullptr) {
144 return false;
145 }
146 BeforeDeallocate(old);
147 allocator_->Deallocate(old);
148 AfterDeallocate();
149
150 } else if constexpr (std::is_same_v<T, ReallocationRequest>) {
151 Allocation* old = RemoveAllocation(r.index);
152 if (old == nullptr) {
153 return false;
154 }
155 Layout new_layout(r.new_size, old->layout.alignment());
156 BeforeReallocate(new_layout);
157 void* new_ptr = allocator_->Reallocate(old, new_layout);
158 AfterReallocate(new_ptr);
159 if (new_ptr == nullptr) {
160 AddAllocation(old, old->layout);
161 } else {
162 AddAllocation(new_ptr, new_layout);
163 }
164 } else {
165 static_assert(not_reached(r), "unsupported request type!");
166 }
167 return true;
168 },
169 request);
170 }
171
Reset()172 void TestHarness::Reset() {
173 if (allocator_ == nullptr) {
174 return;
175 }
176 while (!allocations_.empty()) {
177 allocator_->Deallocate(RemoveAllocation(0));
178 }
179 }
180
AddAllocation(void * ptr,Layout layout)181 void TestHarness::AddAllocation(void* ptr, Layout layout) {
182 constexpr Layout min_layout = Layout::Of<Allocation>();
183 if (layout.size() < min_layout.size() ||
184 layout.alignment() < min_layout.alignment()) {
185 // The harness should want to test small sizes and alignments, but it
186 // needs the layout to be at least `Layout::Of<Allocation>` in order
187 // to persist details about it. If either the size or alignment is too
188 // small, deallocate immediately.
189 BeforeDeallocate(ptr);
190 allocator_->Deallocate(ptr);
191 AfterDeallocate();
192 return;
193 }
194 auto* bytes = static_cast<std::byte*>(ptr);
195 auto* allocation = ::new (bytes) Allocation(layout);
196 allocations_.push_back(*allocation);
197 allocated_ += layout.size();
198 ++num_allocations_;
199 }
200
RemoveAllocation(size_t index)201 TestHarness::Allocation* TestHarness::RemoveAllocation(size_t index) {
202 // Move the target allocation to the back of the list.
203 if (num_allocations_ == 0) {
204 return nullptr;
205 }
206 index %= num_allocations_;
207 auto prev = allocations_.before_begin();
208 for (auto& allocation : allocations_) {
209 if (index == 0) {
210 PW_ASSERT(allocated_ >= allocation.layout.size());
211 allocated_ -= allocation.layout.size();
212 allocations_.erase_after(prev);
213 --num_allocations_;
214 return &allocation;
215 }
216 --index;
217 ++prev;
218 }
219 PW_CRASH("unreachable");
220 }
221
222 } // namespace pw::allocator::test
223