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
15 #include "pw_allocator/synchronized_allocator.h"
16
17 #include <cstddef>
18 #include <cstdint>
19 #include <limits>
20
21 #include "pw_allocator/test_harness.h"
22 #include "pw_allocator/testing.h"
23 #include "pw_containers/vector.h"
24 #include "pw_status/status_with_size.h"
25 #include "pw_sync/binary_semaphore.h"
26 #include "pw_sync/interrupt_spin_lock.h"
27 #include "pw_sync/mutex.h"
28 #include "pw_thread/test_thread_context.h"
29 #include "pw_thread/thread.h"
30 #include "pw_thread/thread_core.h"
31 #include "pw_thread/yield.h"
32 #include "pw_unit_test/framework.h"
33
34 // TODO: https://pwbug.dev/365161669 - Express joinability as a build-system
35 // constraint.
36 #if PW_THREAD_JOINING_ENABLED
37
38 namespace {
39
40 // Test fixtures.
41
42 static constexpr size_t kCapacity = 8192;
43 static constexpr size_t kMaxSize = 512;
44 static constexpr size_t kNumAllocations = 128;
45 static constexpr size_t kSize = 64;
46 static constexpr size_t kAlignment = 4;
47 static constexpr size_t kBackgroundRequests = 8;
48
49 using ::pw::allocator::Layout;
50 using ::pw::allocator::SynchronizedAllocator;
51 using ::pw::allocator::test::TestHarness;
52 using AllocatorForTest = ::pw::allocator::test::AllocatorForTest<kCapacity>;
53
54 struct Allocation {
55 void* ptr;
56 Layout layout;
57
58 /// Fills a valid allocation with a pattern of data.
Paint__anon3d303b040111::Allocation59 void Paint() {
60 if (ptr != nullptr) {
61 auto* u8 = static_cast<uint8_t*>(ptr);
62 for (size_t i = 0; i < layout.size(); ++i) {
63 u8[i] = static_cast<uint8_t>(i & 0xFF);
64 }
65 }
66 }
67
68 /// Checks that a valid allocation has been properly `Paint`ed. Returns the
69 /// first index where the expected pattern doesn't match, e.g. where memory
70 /// has been corrupted, or `layout.size()` if the memory is all correct.
Inspect__anon3d303b040111::Allocation71 size_t Inspect() const {
72 if (ptr != nullptr) {
73 auto* u8 = static_cast<uint8_t*>(ptr);
74 for (size_t i = 0; i < layout.size(); ++i) {
75 if (u8[i] != (i & 0xFF)) {
76 return i;
77 }
78 }
79 }
80 return layout.size();
81 }
82 };
83
84 /// Test fixture that manages a background allocation thread.
85 class Background final {
86 public:
Background(pw::Allocator & allocator)87 Background(pw::Allocator& allocator)
88 : Background(allocator, 1, std::numeric_limits<size_t>::max()) {}
89
Background(pw::Allocator & allocator,uint64_t seed,size_t iterations)90 Background(pw::Allocator& allocator, uint64_t seed, size_t iterations)
91 : background_(allocator, seed, iterations) {
92 background_thread_ =
93 pw::Thread(context_.options(), [this] { background_.Run(); });
94 }
95
~Background()96 ~Background() {
97 background_.Stop();
98 Await();
99 }
100
Await()101 void Await() {
102 background_.Await();
103 if (background_thread_.joinable()) {
104 background_thread_.join();
105 }
106 }
107
108 private:
109 /// Thread body that uses a test harness to perform random sequences of
110 /// allocations on a synchronous allocator.
111 class BackgroundThread {
112 public:
BackgroundThread(pw::Allocator & allocator,uint64_t seed,size_t iterations)113 BackgroundThread(pw::Allocator& allocator, uint64_t seed, size_t iterations)
114 : iterations_(iterations) {
115 test_harness_.set_allocator(&allocator);
116 test_harness_.set_prng_seed(seed);
117 }
118
Run()119 void Run() {
120 for (size_t i = 0; i < iterations_ && !semaphore_.try_acquire(); ++i) {
121 test_harness_.GenerateRequests(kMaxSize, kBackgroundRequests);
122 pw::this_thread::yield();
123 }
124 semaphore_.release();
125 }
126
Stop()127 void Stop() { semaphore_.release(); }
128
Await()129 void Await() {
130 semaphore_.acquire();
131 semaphore_.release();
132 }
133
134 private:
135 TestHarness test_harness_;
136 pw::sync::BinarySemaphore semaphore_;
137 size_t iterations_;
138 } background_;
139
140 pw::thread::test::TestThreadContext context_;
141 pw::Thread background_thread_;
142 };
143
144 // Unit tests.
145
146 // The tests below manipulate dynamically allocated memory while a background
147 // thread simultaneously exercises the allocator. Allocations, queries and
148 // resizes may fail, but memory must not be corrupted and the test must not
149 // deadlock.
150
151 template <typename LockType>
TestGetCapacity()152 void TestGetCapacity() {
153 AllocatorForTest allocator;
154 SynchronizedAllocator<LockType> synchronized(allocator);
155 Background background(synchronized);
156
157 pw::StatusWithSize capacity = synchronized.GetCapacity();
158 EXPECT_EQ(capacity.status(), pw::OkStatus());
159 EXPECT_EQ(capacity.size(), kCapacity);
160 }
161
TEST(SynchronizedAllocatorTest,GetCapacitySpinLock)162 TEST(SynchronizedAllocatorTest, GetCapacitySpinLock) {
163 TestGetCapacity<pw::sync::InterruptSpinLock>();
164 }
165
TEST(SynchronizedAllocatorTest,GetCapacityMutex)166 TEST(SynchronizedAllocatorTest, GetCapacityMutex) {
167 TestGetCapacity<pw::sync::Mutex>();
168 }
169
170 template <typename LockType>
TestAllocate()171 void TestAllocate() {
172 AllocatorForTest allocator;
173 SynchronizedAllocator<LockType> synchronized(allocator);
174 Background background(synchronized);
175
176 pw::Vector<Allocation, kNumAllocations> allocations;
177 while (!allocations.full()) {
178 Layout layout(kSize, kAlignment);
179 void* ptr = synchronized.Allocate(layout);
180 Allocation allocation{ptr, layout};
181 allocation.Paint();
182 allocations.push_back(allocation);
183 pw::this_thread::yield();
184 }
185
186 for (const auto& allocation : allocations) {
187 EXPECT_EQ(allocation.Inspect(), allocation.layout.size());
188 synchronized.Deallocate(allocation.ptr);
189 }
190 }
191
TEST(SynchronizedAllocatorTest,AllocateDeallocateInterruptSpinLock)192 TEST(SynchronizedAllocatorTest, AllocateDeallocateInterruptSpinLock) {
193 TestAllocate<pw::sync::InterruptSpinLock>();
194 }
195
TEST(SynchronizedAllocatorTest,AllocateDeallocateMutex)196 TEST(SynchronizedAllocatorTest, AllocateDeallocateMutex) {
197 TestAllocate<pw::sync::Mutex>();
198 }
199
200 template <typename LockType>
TestResize()201 void TestResize() {
202 AllocatorForTest allocator;
203 SynchronizedAllocator<LockType> synchronized(allocator);
204 Background background(synchronized);
205
206 pw::Vector<Allocation, kNumAllocations> allocations;
207 while (!allocations.full()) {
208 Layout layout(kSize, kAlignment);
209 void* ptr = synchronized.Allocate(layout);
210 Allocation allocation{ptr, layout};
211 allocation.Paint();
212 allocations.push_back(allocation);
213 pw::this_thread::yield();
214 }
215
216 // First, resize them smaller.
217 for (auto& allocation : allocations) {
218 EXPECT_EQ(allocation.Inspect(), allocation.layout.size());
219 size_t new_size = allocation.layout.size() / 2;
220 if (!synchronized.Resize(allocation.ptr, new_size)) {
221 continue;
222 }
223 allocation.layout = Layout(new_size, allocation.layout.alignment());
224 allocation.Paint();
225 pw::this_thread::yield();
226 }
227
228 // Then, resize them back to their original size.
229 for (auto& allocation : allocations) {
230 EXPECT_EQ(allocation.Inspect(), allocation.layout.size());
231 size_t old_size = allocation.layout.size() * 2;
232 if (!synchronized.Resize(allocation.ptr, old_size)) {
233 continue;
234 }
235 allocation.layout = Layout(old_size, allocation.layout.alignment());
236 allocation.Paint();
237 pw::this_thread::yield();
238 }
239 }
240
TEST(SynchronizedAllocatorTest,ResizeInterruptSpinLock)241 TEST(SynchronizedAllocatorTest, ResizeInterruptSpinLock) {
242 TestResize<pw::sync::InterruptSpinLock>();
243 }
244
TEST(SynchronizedAllocatorTest,ResizeMutex)245 TEST(SynchronizedAllocatorTest, ResizeMutex) { TestResize<pw::sync::Mutex>(); }
246
247 template <typename LockType>
TestReallocate()248 void TestReallocate() {
249 AllocatorForTest allocator;
250 SynchronizedAllocator<LockType> synchronized(allocator);
251 Background background(synchronized);
252
253 pw::Vector<Allocation, kNumAllocations> allocations;
254 while (!allocations.full()) {
255 Layout layout(kSize, kAlignment);
256 void* ptr = synchronized.Allocate(layout);
257 Allocation allocation{ptr, layout};
258 allocation.Paint();
259 allocations.push_back(allocation);
260 pw::this_thread::yield();
261 }
262
263 for (auto& allocation : allocations) {
264 EXPECT_EQ(allocation.Inspect(), allocation.layout.size());
265 Layout new_layout = allocation.layout.Extend(1);
266 void* new_ptr = synchronized.Reallocate(allocation.ptr, new_layout);
267 if (new_ptr == nullptr) {
268 continue;
269 }
270 allocation.ptr = new_ptr;
271 allocation.layout = new_layout;
272 allocation.Paint();
273 pw::this_thread::yield();
274 }
275 }
276
TEST(SynchronizedAllocatorTest,ReallocateInterruptSpinLock)277 TEST(SynchronizedAllocatorTest, ReallocateInterruptSpinLock) {
278 TestReallocate<pw::sync::InterruptSpinLock>();
279 }
280
TEST(SynchronizedAllocatorTest,ReallocateMutex)281 TEST(SynchronizedAllocatorTest, ReallocateMutex) {
282 TestReallocate<pw::sync::Mutex>();
283 }
284
285 template <typename LockType>
TestGenerateRequests()286 void TestGenerateRequests() {
287 constexpr size_t kNumIterations = 10000;
288 AllocatorForTest allocator;
289 SynchronizedAllocator<LockType> synchronized(allocator);
290 Background background1(synchronized, 1, kNumIterations);
291 Background background2(synchronized, 2, kNumIterations);
292 background1.Await();
293 background2.Await();
294 }
295
TEST(SynchronizedAllocatorTest,GenerateRequestsSpinLock)296 TEST(SynchronizedAllocatorTest, GenerateRequestsSpinLock) {
297 TestGenerateRequests<pw::sync::InterruptSpinLock>();
298 }
299
TEST(SynchronizedAllocatorTest,GenerateRequestsMutex)300 TEST(SynchronizedAllocatorTest, GenerateRequestsMutex) {
301 TestGenerateRequests<pw::sync::Mutex>();
302 }
303
304 } // namespace
305
306 #endif // PW_THREAD_JOINING_ENABLED
307