xref: /aosp_15_r20/external/pigweed/pw_allocator/tracking_allocator_test.cc (revision 61c4878ac05f98d0ceed94b57d316916de578985)
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