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 #include "pw_allocator/tracking_allocator.h"
15
16 #include <cstdint>
17
18 #include "pw_allocator/allocator.h"
19 #include "pw_allocator/first_fit.h"
20 #include "pw_allocator/metrics.h"
21 #include "pw_allocator/testing.h"
22 #include "pw_log/log.h"
23 #include "pw_metric/metric.h"
24 #include "pw_unit_test/framework.h"
25
26 namespace {
27
28 // Test fixtures.
29
30 using ::pw::allocator::Layout;
31 using ::pw::allocator::TrackingAllocator;
32 using TestMetrics = ::pw::allocator::internal::AllMetrics;
33
34 class TrackingAllocatorForTest : public TrackingAllocator<TestMetrics> {
35 public:
TrackingAllocatorForTest(pw::metric::Token token,pw::Allocator & allocator)36 TrackingAllocatorForTest(pw::metric::Token token, pw::Allocator& allocator)
37 : TrackingAllocator<TestMetrics>(token, allocator) {}
38
39 // Expose the protected allocated ``Layout`` method for test purposes.
GetAllocatedLayout(const void * ptr) const40 pw::Result<Layout> GetAllocatedLayout(const void* ptr) const {
41 return TrackingAllocator<TestMetrics>::GetAllocatedLayout(ptr);
42 }
43 };
44
45 class TrackingAllocatorTest : public ::testing::Test {
46 protected:
47 using BlockType = ::pw::allocator::FirstFitBlock<uint32_t>;
48 using AllocatorType = ::pw::allocator::FirstFitAllocator<BlockType>;
49 static_assert(sizeof(uintptr_t) >= BlockType::kAlignment);
50
51 constexpr static size_t kCapacity = 256;
52 constexpr static pw::metric::Token kToken = 1U;
53
TrackingAllocatorTest()54 TrackingAllocatorTest() : ::testing::Test(), tracker_(kToken, *allocator_) {}
55
SetUp()56 void SetUp() override { allocator_->Init(allocator_.as_bytes()); }
57
TearDown()58 void TearDown() override {
59 pw::allocator::test::FreeAll<BlockType>(allocator_->blocks());
60 allocator_->Reset();
61 }
62
63 pw::allocator::WithBuffer<AllocatorType, kCapacity, BlockType::kAlignment>
64 allocator_;
65 TrackingAllocatorForTest tracker_;
66 };
67
68 struct ExpectedValues {
69 uint32_t requested_bytes = 0;
70 uint32_t peak_requested_bytes = 0;
71 uint32_t cumulative_requested_bytes = 0;
72 uint32_t allocated_bytes = 0;
73 uint32_t peak_allocated_bytes = 0;
74 uint32_t cumulative_allocated_bytes = 0;
75 uint32_t num_allocations = 0;
76 uint32_t num_deallocations = 0;
77 uint32_t num_resizes = 0;
78 uint32_t num_reallocations = 0;
79 uint32_t num_failures = 0;
80 uint32_t unfulfilled_bytes = 0;
81
AddRequestedBytes__anon1e9826b70111::ExpectedValues82 void AddRequestedBytes(uint32_t requested_bytes_) {
83 requested_bytes += requested_bytes_;
84 peak_requested_bytes = std::max(requested_bytes, peak_requested_bytes);
85 cumulative_requested_bytes += requested_bytes_;
86 }
87
AddAllocatedBytes__anon1e9826b70111::ExpectedValues88 void AddAllocatedBytes(uint32_t allocated_bytes_) {
89 allocated_bytes += allocated_bytes_;
90 peak_allocated_bytes = std::max(allocated_bytes, peak_allocated_bytes);
91 cumulative_allocated_bytes += allocated_bytes_;
92 }
93
Check__anon1e9826b70111::ExpectedValues94 void Check(const TestMetrics& metrics, int line) {
95 EXPECT_EQ(metrics.requested_bytes.value(), requested_bytes);
96 EXPECT_EQ(metrics.peak_requested_bytes.value(), peak_requested_bytes);
97 EXPECT_EQ(metrics.cumulative_requested_bytes.value(),
98 cumulative_requested_bytes);
99 EXPECT_EQ(metrics.allocated_bytes.value(), allocated_bytes);
100 EXPECT_EQ(metrics.peak_allocated_bytes.value(), peak_allocated_bytes);
101 EXPECT_EQ(metrics.cumulative_allocated_bytes.value(),
102 cumulative_allocated_bytes);
103 EXPECT_EQ(metrics.num_allocations.value(), num_allocations);
104 EXPECT_EQ(metrics.num_deallocations.value(), num_deallocations);
105 EXPECT_EQ(metrics.num_resizes.value(), num_resizes);
106 EXPECT_EQ(metrics.num_reallocations.value(), num_reallocations);
107 EXPECT_EQ(metrics.num_failures.value(), num_failures);
108 EXPECT_EQ(metrics.unfulfilled_bytes.value(), unfulfilled_bytes);
109 if (testing::Test::HasFailure()) {
110 PW_LOG_ERROR("Metrics comparison failed at line %d.", line);
111 }
112 }
113 };
114
115 #define EXPECT_METRICS_EQ(expected, metrics) expected.Check(metrics, __LINE__)
116
117 // Unit tests.
118
TEST_F(TrackingAllocatorTest,InitialValues)119 TEST_F(TrackingAllocatorTest, InitialValues) {
120 const TestMetrics& metrics = tracker_.metrics();
121 ExpectedValues expected; // Initially all 0.
122 EXPECT_METRICS_EQ(expected, metrics);
123 }
124
TEST_F(TrackingAllocatorTest,GetCapacity)125 TEST_F(TrackingAllocatorTest, GetCapacity) {
126 pw::StatusWithSize capacity = tracker_.GetCapacity();
127 EXPECT_EQ(capacity.status(), pw::OkStatus());
128 EXPECT_EQ(capacity.size(), kCapacity);
129 }
130
TEST_F(TrackingAllocatorTest,AddTrackingAllocatorAsChild)131 TEST_F(TrackingAllocatorTest, AddTrackingAllocatorAsChild) {
132 constexpr static pw::metric::Token kChildToken = 2U;
133 TrackingAllocator<::pw::allocator::NoMetrics> child(
134 kChildToken, tracker_, pw::allocator::kAddTrackingAllocatorAsChild);
135 pw::IntrusiveList<pw::metric::Group>& children =
136 tracker_.metric_group().children();
137 ASSERT_FALSE(children.empty());
138 EXPECT_EQ(children.size(), 1U);
139 EXPECT_EQ(&(children.front()), &(child.metric_group()));
140 }
141
TEST_F(TrackingAllocatorTest,AllocateDeallocate)142 TEST_F(TrackingAllocatorTest, AllocateDeallocate) {
143 const TestMetrics& metrics = tracker_.metrics();
144 ExpectedValues expected;
145
146 constexpr Layout layout1 = Layout::Of<uintptr_t[2]>();
147 void* ptr1 = tracker_.Allocate(layout1);
148 size_t ptr1_allocated = tracker_.GetAllocatedLayout(ptr1)->size();
149 ASSERT_NE(ptr1, nullptr);
150 expected.AddRequestedBytes(layout1.size());
151 expected.AddAllocatedBytes(ptr1_allocated);
152 expected.num_allocations += 1;
153 EXPECT_METRICS_EQ(expected, metrics);
154
155 tracker_.Deallocate(ptr1);
156 expected.requested_bytes -= layout1.size();
157 expected.allocated_bytes -= ptr1_allocated;
158 expected.num_deallocations += 1;
159 EXPECT_METRICS_EQ(expected, metrics);
160 }
161
TEST_F(TrackingAllocatorTest,AllocateFailure)162 TEST_F(TrackingAllocatorTest, AllocateFailure) {
163 const TestMetrics& metrics = tracker_.metrics();
164 ExpectedValues expected;
165
166 constexpr Layout layout = Layout::Of<uintptr_t[0x1000000U]>();
167 void* ptr = tracker_.Allocate(layout);
168 EXPECT_EQ(ptr, nullptr);
169 expected.num_failures += 1;
170 expected.unfulfilled_bytes += layout.size();
171 EXPECT_METRICS_EQ(expected, metrics);
172 }
173
TEST_F(TrackingAllocatorTest,AllocateDeallocateMultiple)174 TEST_F(TrackingAllocatorTest, AllocateDeallocateMultiple) {
175 const TestMetrics& metrics = tracker_.metrics();
176 ExpectedValues expected;
177
178 Layout layout1 = Layout::Of<uintptr_t[3]>();
179 void* ptr1 = tracker_.Allocate(layout1);
180 ASSERT_NE(ptr1, nullptr);
181 size_t ptr1_allocated = tracker_.GetAllocatedLayout(ptr1)->size();
182 expected.AddRequestedBytes(layout1.size());
183 expected.AddAllocatedBytes(ptr1_allocated);
184 expected.num_allocations += 1;
185 EXPECT_METRICS_EQ(expected, metrics);
186
187 Layout layout2 = Layout::Of<uintptr_t[2]>();
188 void* ptr2 = tracker_.Allocate(layout2);
189 ASSERT_NE(ptr2, nullptr);
190 size_t ptr2_allocated = tracker_.GetAllocatedLayout(ptr2)->size();
191 expected.AddRequestedBytes(layout2.size());
192 expected.AddAllocatedBytes(ptr2_allocated);
193 expected.num_allocations += 1;
194 EXPECT_METRICS_EQ(expected, metrics);
195
196 tracker_.Deallocate(ptr1);
197 expected.requested_bytes -= layout1.size();
198 expected.allocated_bytes -= ptr1_allocated;
199 expected.num_deallocations += 1;
200 EXPECT_METRICS_EQ(expected, metrics);
201
202 Layout layout3 = Layout::Of<uintptr_t>();
203 void* ptr3 = tracker_.Allocate(layout3);
204 ASSERT_NE(ptr3, nullptr);
205 size_t ptr3_allocated = tracker_.GetAllocatedLayout(ptr3)->size();
206 expected.AddRequestedBytes(layout3.size());
207 expected.AddAllocatedBytes(ptr3_allocated);
208 expected.num_allocations += 1;
209 EXPECT_METRICS_EQ(expected, metrics);
210
211 tracker_.Deallocate(ptr3);
212 expected.requested_bytes -= layout3.size();
213 expected.allocated_bytes -= ptr3_allocated;
214 expected.num_deallocations += 1;
215 EXPECT_METRICS_EQ(expected, metrics);
216
217 tracker_.Deallocate(ptr2);
218 expected.requested_bytes -= layout2.size();
219 expected.allocated_bytes -= ptr2_allocated;
220 expected.num_deallocations += 1;
221 EXPECT_METRICS_EQ(expected, metrics);
222 }
223
TEST_F(TrackingAllocatorTest,ResizeLarger)224 TEST_F(TrackingAllocatorTest, ResizeLarger) {
225 const TestMetrics& metrics = tracker_.metrics();
226 ExpectedValues expected;
227
228 constexpr Layout layout1 = Layout::Of<uintptr_t[3]>();
229 void* ptr = tracker_.Allocate(layout1);
230 size_t ptr_allocated1 = tracker_.GetAllocatedLayout(ptr)->size();
231 ASSERT_NE(ptr, nullptr);
232 expected.AddRequestedBytes(layout1.size());
233 expected.AddAllocatedBytes(ptr_allocated1);
234 expected.num_allocations += 1;
235 EXPECT_METRICS_EQ(expected, metrics);
236
237 constexpr size_t size2 = sizeof(uintptr_t[5]);
238 EXPECT_TRUE(tracker_.Resize(ptr, size2));
239 size_t ptr_allocated2 = tracker_.GetAllocatedLayout(ptr)->size();
240 expected.AddRequestedBytes(size2 - layout1.size());
241 expected.AddAllocatedBytes(ptr_allocated2 - ptr_allocated1);
242 expected.num_resizes += 1;
243 EXPECT_METRICS_EQ(expected, metrics);
244
245 tracker_.Deallocate(ptr);
246 expected.requested_bytes -= size2;
247 expected.allocated_bytes -= ptr_allocated2;
248 expected.num_deallocations += 1;
249 EXPECT_METRICS_EQ(expected, metrics);
250 }
251
TEST_F(TrackingAllocatorTest,ResizeSmaller)252 TEST_F(TrackingAllocatorTest, ResizeSmaller) {
253 const TestMetrics& metrics = tracker_.metrics();
254 ExpectedValues expected;
255
256 constexpr Layout layout1 = Layout::Of<uintptr_t[2]>();
257 void* ptr = tracker_.Allocate(layout1);
258 size_t ptr_allocated1 = tracker_.GetAllocatedLayout(ptr)->size();
259 ASSERT_NE(ptr, nullptr);
260 expected.AddRequestedBytes(layout1.size());
261 expected.AddAllocatedBytes(ptr_allocated1);
262 expected.num_allocations += 1;
263 EXPECT_METRICS_EQ(expected, metrics);
264
265 constexpr size_t size2 = sizeof(uintptr_t[1]);
266 EXPECT_TRUE(tracker_.Resize(ptr, size2));
267 size_t ptr_allocated2 = tracker_.GetAllocatedLayout(ptr)->size();
268 expected.requested_bytes -= layout1.size() - size2;
269 expected.allocated_bytes -= ptr_allocated1 - ptr_allocated2;
270 expected.num_resizes += 1;
271 EXPECT_METRICS_EQ(expected, metrics);
272
273 tracker_.Deallocate(ptr);
274 expected.requested_bytes -= size2;
275 expected.allocated_bytes -= ptr_allocated2;
276 expected.num_deallocations += 1;
277 EXPECT_METRICS_EQ(expected, metrics);
278 }
279
TEST_F(TrackingAllocatorTest,ResizeFailure)280 TEST_F(TrackingAllocatorTest, ResizeFailure) {
281 const TestMetrics& metrics = tracker_.metrics();
282 ExpectedValues expected;
283
284 constexpr Layout layout = Layout::Of<uintptr_t[4]>();
285 void* ptr1 = tracker_.Allocate(layout);
286 ASSERT_NE(ptr1, nullptr);
287 size_t ptr1_allocated = tracker_.GetAllocatedLayout(ptr1)->size();
288 expected.AddRequestedBytes(layout.size());
289 expected.AddAllocatedBytes(ptr1_allocated);
290 expected.num_allocations += 1;
291 EXPECT_METRICS_EQ(expected, metrics);
292
293 void* ptr2 = tracker_.Allocate(layout);
294 ASSERT_NE(ptr2, nullptr);
295 size_t ptr2_allocated = tracker_.GetAllocatedLayout(ptr2)->size();
296 expected.AddRequestedBytes(layout.size());
297 expected.AddAllocatedBytes(ptr2_allocated);
298 expected.num_allocations += 1;
299 EXPECT_METRICS_EQ(expected, metrics);
300
301 EXPECT_FALSE(tracker_.Resize(ptr1, layout.size() * 2));
302 expected.num_failures += 1;
303 expected.unfulfilled_bytes += layout.size() * 2;
304 EXPECT_METRICS_EQ(expected, metrics);
305 }
306
TEST_F(TrackingAllocatorTest,Reallocate)307 TEST_F(TrackingAllocatorTest, Reallocate) {
308 const TestMetrics& metrics = tracker_.metrics();
309 ExpectedValues expected;
310
311 constexpr Layout layout1 = Layout::Of<uintptr_t[2]>();
312 void* ptr1 = tracker_.Allocate(layout1);
313 ASSERT_NE(ptr1, nullptr);
314 size_t ptr1_allocated = tracker_.GetAllocatedLayout(ptr1)->size();
315 expected.AddRequestedBytes(layout1.size());
316 expected.AddAllocatedBytes(ptr1_allocated);
317 expected.num_allocations += 1;
318 EXPECT_METRICS_EQ(expected, metrics);
319
320 // If `Reallocate` just resizes, no extra memory is allocated
321 constexpr Layout layout2 = Layout::Of<uintptr_t[4]>();
322 void* ptr2 = tracker_.Reallocate(ptr1, layout2);
323 EXPECT_EQ(ptr2, ptr1);
324 size_t ptr2_allocated = tracker_.GetAllocatedLayout(ptr2)->size();
325 expected.AddRequestedBytes(layout2.size() - layout1.size());
326 expected.AddAllocatedBytes(ptr2_allocated - ptr1_allocated);
327 expected.num_reallocations += 1;
328 EXPECT_METRICS_EQ(expected, metrics);
329
330 // Make a second allocation to force reallocation.
331 constexpr Layout layout3 = layout1;
332 void* ptr3 = tracker_.Allocate(layout1);
333 ASSERT_NE(ptr3, nullptr);
334 size_t ptr3_allocated = tracker_.GetAllocatedLayout(ptr3)->size();
335 expected.AddRequestedBytes(layout3.size());
336 expected.AddAllocatedBytes(ptr3_allocated);
337 expected.num_allocations += 1;
338 EXPECT_METRICS_EQ(expected, metrics);
339
340 // If `Reallocate` must copy to a new location, it allocates before
341 // deallocating and results in higher peaks.
342 constexpr Layout layout4 = Layout::Of<uintptr_t[8]>();
343 void* ptr4 = tracker_.Reallocate(ptr2, layout4);
344 EXPECT_NE(ptr4, ptr2);
345 size_t ptr4_allocated = tracker_.GetAllocatedLayout(ptr4)->size();
346 expected.AddRequestedBytes(layout4.size() - layout2.size());
347 expected.AddAllocatedBytes(ptr4_allocated);
348 expected.allocated_bytes -= ptr2_allocated;
349 expected.num_reallocations += 1;
350 EXPECT_METRICS_EQ(expected, metrics);
351
352 tracker_.Deallocate(ptr3);
353 expected.requested_bytes -= layout3.size();
354 expected.allocated_bytes -= ptr3_allocated;
355 expected.num_deallocations += 1;
356 EXPECT_METRICS_EQ(expected, metrics);
357
358 tracker_.Deallocate(ptr4);
359 expected.requested_bytes -= layout4.size();
360 expected.allocated_bytes -= ptr4_allocated;
361 expected.num_deallocations += 1;
362 EXPECT_METRICS_EQ(expected, metrics);
363 }
364
TEST_F(TrackingAllocatorTest,ReallocateFailure)365 TEST_F(TrackingAllocatorTest, ReallocateFailure) {
366 const TestMetrics& metrics = tracker_.metrics();
367 ExpectedValues expected;
368
369 constexpr Layout layout1 = Layout::Of<uintptr_t[4]>();
370 void* ptr1 = tracker_.Allocate(layout1);
371 ASSERT_NE(ptr1, nullptr);
372 size_t ptr1_allocated = tracker_.GetAllocatedLayout(ptr1)->size();
373 expected.AddRequestedBytes(layout1.size());
374 expected.AddAllocatedBytes(ptr1_allocated);
375 expected.num_allocations += 1;
376 EXPECT_METRICS_EQ(expected, metrics);
377
378 constexpr Layout layout2 = Layout(0x10000000U, 1);
379 void* ptr2 = tracker_.Reallocate(ptr1, layout2);
380 EXPECT_EQ(ptr2, nullptr);
381 expected.num_failures += 1;
382 expected.unfulfilled_bytes += layout2.size();
383 EXPECT_METRICS_EQ(expected, metrics);
384 }
385
TEST_F(TrackingAllocatorTest,CorrectlyAccountsForShiftedBytes)386 TEST_F(TrackingAllocatorTest, CorrectlyAccountsForShiftedBytes) {
387 const TestMetrics& metrics = tracker_.metrics();
388 ExpectedValues expected;
389
390 // Find an alignment greater than two block headers.
391 size_t alignment = 1;
392 while (alignment <= (BlockType::kBlockOverhead * 2)) {
393 alignment *= 2;
394 }
395
396 // Allocate one block to align the usable space of the following block.
397 Layout layout1(alignment - BlockType::kBlockOverhead, alignment);
398 void* ptr1 = tracker_.Allocate(layout1);
399 ASSERT_NE(ptr1, nullptr);
400 auto* block1 = BlockType::FromUsableSpace(ptr1);
401 size_t ptr1_allocated = block1->OuterSize();
402 expected.AddRequestedBytes(layout1.size());
403 expected.AddAllocatedBytes(ptr1_allocated);
404 expected.num_allocations += 1;
405 EXPECT_METRICS_EQ(expected, metrics);
406
407 // Allocate a second block that ends two block headers from an alignment
408 // boundary.
409 Layout layout2(alignment - (BlockType::kBlockOverhead * 2), alignment);
410 void* ptr2 = tracker_.Allocate(layout2);
411 ASSERT_NE(ptr2, nullptr);
412 auto* block2 = BlockType::FromUsableSpace(ptr2);
413 EXPECT_EQ(block2->InnerSize(), layout2.size());
414 size_t ptr2_allocated = block2->OuterSize();
415 expected.AddRequestedBytes(layout2.size());
416 expected.AddAllocatedBytes(ptr2_allocated);
417 expected.num_allocations += 1;
418 EXPECT_METRICS_EQ(expected, metrics);
419
420 // Allocate a third block to prevent the second block from being coalesced.
421 // The extra bytes should be appended to the second block.
422 Layout layout3(1, alignment);
423 void* ptr3 = tracker_.Allocate(layout3);
424 ASSERT_NE(ptr3, nullptr);
425 auto* block3 = BlockType::FromUsableSpace(ptr3);
426 size_t ptr3_allocated = block3->OuterSize();
427 size_t shifted = block2->OuterSize() - ptr2_allocated;
428 expected.AddRequestedBytes(layout3.size());
429 expected.AddAllocatedBytes(ptr3_allocated + shifted);
430 expected.num_allocations += 1;
431 EXPECT_METRICS_EQ(expected, metrics);
432
433 // Free the second block, which is larger than when it was allocated.
434 tracker_.Deallocate(ptr2);
435 expected.requested_bytes -= layout2.size();
436 expected.allocated_bytes -= ptr2_allocated + shifted;
437 expected.num_deallocations += 1;
438 EXPECT_METRICS_EQ(expected, metrics);
439
440 // Allocate the second block again. The trailing space should be appended.
441 ptr2 = tracker_.Allocate(layout2);
442 ASSERT_NE(ptr2, nullptr);
443 block2 = BlockType::FromUsableSpace(ptr2);
444 EXPECT_EQ(block2->OuterSize(), ptr2_allocated + shifted);
445 expected.AddRequestedBytes(layout2.size());
446 expected.AddAllocatedBytes(ptr2_allocated + shifted);
447 expected.num_allocations += 1;
448 EXPECT_METRICS_EQ(expected, metrics);
449
450 // Free the third block, which should reclaim space from the second block.
451 tracker_.Deallocate(ptr3);
452 expected.requested_bytes -= layout3.size();
453 expected.allocated_bytes -= ptr3_allocated + shifted;
454 expected.num_deallocations += 1;
455 EXPECT_METRICS_EQ(expected, metrics);
456
457 // Free the second block, which is now smaller than when it was allocated.
458 tracker_.Deallocate(ptr2);
459 expected.requested_bytes -= layout2.size();
460 expected.allocated_bytes -= ptr2_allocated;
461 expected.num_deallocations += 1;
462 EXPECT_METRICS_EQ(expected, metrics);
463 }
464
465 } // namespace
466