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