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