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/metrics.h"
20 #include "pw_allocator/testing.h"
21 #include "pw_log/log.h"
22 #include "pw_metric/metric.h"
23 #include "pw_unit_test/framework.h"
24
25 namespace {
26
27 // Test fixtures.
28
29 using ::pw::allocator::Layout;
30 using ::pw::allocator::NoMetrics;
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 AllocatorType = ::pw::allocator::FirstFitBlockAllocator<uint32_t>;
48 using BlockType = AllocatorType::BlockType;
49
50 constexpr static size_t kCapacity = 256;
51 constexpr static pw::metric::Token kToken = 1U;
52
TrackingAllocatorTest()53 TrackingAllocatorTest() : ::testing::Test(), tracker_(kToken, *allocator_) {}
54
SetUp()55 void SetUp() override { allocator_->Init(allocator_.as_bytes()); }
56
TearDown()57 void TearDown() override {
58 for (auto* block : allocator_->blocks()) {
59 BlockType::Free(block);
60 }
61 allocator_->Reset();
62 }
63
64 pw::allocator::WithBuffer<AllocatorType, kCapacity, BlockType::kAlignment>
65 allocator_;
66 TrackingAllocatorForTest tracker_;
67 };
68
69 struct ExpectedValues {
70 uint32_t requested_bytes = 0;
71 uint32_t peak_requested_bytes = 0;
72 uint32_t cumulative_requested_bytes = 0;
73 uint32_t allocated_bytes = 0;
74 uint32_t peak_allocated_bytes = 0;
75 uint32_t cumulative_allocated_bytes = 0;
76 uint32_t num_allocations = 0;
77 uint32_t num_deallocations = 0;
78 uint32_t num_resizes = 0;
79 uint32_t num_reallocations = 0;
80 uint32_t num_failures = 0;
81 uint32_t unfulfilled_bytes = 0;
82
AddRequestedBytes__anon9ba642150111::ExpectedValues83 void AddRequestedBytes(uint32_t requested_bytes_) {
84 requested_bytes += requested_bytes_;
85 peak_requested_bytes = std::max(requested_bytes, peak_requested_bytes);
86 cumulative_requested_bytes += requested_bytes_;
87 }
88
AddAllocatedBytes__anon9ba642150111::ExpectedValues89 void AddAllocatedBytes(uint32_t allocated_bytes_) {
90 allocated_bytes += allocated_bytes_;
91 peak_allocated_bytes = std::max(allocated_bytes, peak_allocated_bytes);
92 cumulative_allocated_bytes += allocated_bytes_;
93 }
94
Check__anon9ba642150111::ExpectedValues95 void Check(const TestMetrics& metrics, int line) {
96 EXPECT_EQ(metrics.requested_bytes.value(), requested_bytes);
97 EXPECT_EQ(metrics.peak_requested_bytes.value(), peak_requested_bytes);
98 EXPECT_EQ(metrics.cumulative_requested_bytes.value(),
99 cumulative_requested_bytes);
100 EXPECT_EQ(metrics.allocated_bytes.value(), allocated_bytes);
101 EXPECT_EQ(metrics.peak_allocated_bytes.value(), peak_allocated_bytes);
102 EXPECT_EQ(metrics.cumulative_allocated_bytes.value(),
103 cumulative_allocated_bytes);
104 EXPECT_EQ(metrics.num_allocations.value(), num_allocations);
105 EXPECT_EQ(metrics.num_deallocations.value(), num_deallocations);
106 EXPECT_EQ(metrics.num_resizes.value(), num_resizes);
107 EXPECT_EQ(metrics.num_reallocations.value(), num_reallocations);
108 EXPECT_EQ(metrics.num_failures.value(), num_failures);
109 EXPECT_EQ(metrics.unfulfilled_bytes.value(), unfulfilled_bytes);
110 if (testing::Test::HasFailure()) {
111 PW_LOG_ERROR("Metrics comparison failed at line %d.", line);
112 }
113 }
114 };
115
116 #define EXPECT_METRICS_EQ(expected, metrics) expected.Check(metrics, __LINE__)
117
118 // Unit tests.
119
TEST_F(TrackingAllocatorTest,InitialValues)120 TEST_F(TrackingAllocatorTest, InitialValues) {
121 const TestMetrics& metrics = tracker_.metrics();
122 ExpectedValues expected; // Initially all 0.
123 EXPECT_METRICS_EQ(expected, metrics);
124 }
125
TEST_F(TrackingAllocatorTest,GetCapacity)126 TEST_F(TrackingAllocatorTest, GetCapacity) {
127 pw::StatusWithSize capacity = tracker_.GetCapacity();
128 EXPECT_EQ(capacity.status(), pw::OkStatus());
129 EXPECT_EQ(capacity.size(), kCapacity);
130 }
131
TEST_F(TrackingAllocatorTest,AddTrackingAllocatorAsChild)132 TEST_F(TrackingAllocatorTest, AddTrackingAllocatorAsChild) {
133 constexpr static pw::metric::Token kChildToken = 2U;
134 TrackingAllocator<NoMetrics> child(
135 kChildToken, tracker_, pw::allocator::kAddTrackingAllocatorAsChild);
136 pw::IntrusiveList<pw::metric::Group>& children =
137 tracker_.metric_group().children();
138 ASSERT_FALSE(children.empty());
139 EXPECT_EQ(children.size(), 1U);
140 EXPECT_EQ(&(children.front()), &(child.metric_group()));
141 }
142
TEST_F(TrackingAllocatorTest,AllocateDeallocate)143 TEST_F(TrackingAllocatorTest, AllocateDeallocate) {
144 const TestMetrics& metrics = tracker_.metrics();
145 ExpectedValues expected;
146
147 constexpr Layout layout1 = Layout::Of<uint32_t[2]>();
148 void* ptr1 = tracker_.Allocate(layout1);
149 size_t ptr1_allocated = tracker_.GetAllocatedLayout(ptr1)->size();
150 ASSERT_NE(ptr1, nullptr);
151 expected.AddRequestedBytes(layout1.size());
152 expected.AddAllocatedBytes(ptr1_allocated);
153 expected.num_allocations += 1;
154 EXPECT_METRICS_EQ(expected, metrics);
155
156 tracker_.Deallocate(ptr1);
157 expected.requested_bytes -= layout1.size();
158 expected.allocated_bytes -= ptr1_allocated;
159 expected.num_deallocations += 1;
160 EXPECT_METRICS_EQ(expected, metrics);
161 }
162
TEST_F(TrackingAllocatorTest,AllocateFailure)163 TEST_F(TrackingAllocatorTest, AllocateFailure) {
164 const TestMetrics& metrics = tracker_.metrics();
165 ExpectedValues expected;
166
167 constexpr Layout layout = Layout::Of<uint32_t[0x10000000U]>();
168 void* ptr = tracker_.Allocate(layout);
169 EXPECT_EQ(ptr, nullptr);
170 expected.num_failures += 1;
171 expected.unfulfilled_bytes += layout.size();
172 EXPECT_METRICS_EQ(expected, metrics);
173 }
174
TEST_F(TrackingAllocatorTest,AllocateDeallocateMultiple)175 TEST_F(TrackingAllocatorTest, AllocateDeallocateMultiple) {
176 const TestMetrics& metrics = tracker_.metrics();
177 ExpectedValues expected;
178
179 Layout layout1 = Layout::Of<uint32_t[3]>();
180 void* ptr1 = tracker_.Allocate(layout1);
181 ASSERT_NE(ptr1, nullptr);
182 size_t ptr1_allocated = tracker_.GetAllocatedLayout(ptr1)->size();
183 expected.AddRequestedBytes(layout1.size());
184 expected.AddAllocatedBytes(ptr1_allocated);
185 expected.num_allocations += 1;
186 EXPECT_METRICS_EQ(expected, metrics);
187
188 Layout layout2 = Layout::Of<uint32_t[2]>();
189 void* ptr2 = tracker_.Allocate(layout2);
190 ASSERT_NE(ptr2, nullptr);
191 size_t ptr2_allocated = tracker_.GetAllocatedLayout(ptr2)->size();
192 expected.AddRequestedBytes(layout2.size());
193 expected.AddAllocatedBytes(ptr2_allocated);
194 expected.num_allocations += 1;
195 EXPECT_METRICS_EQ(expected, metrics);
196
197 tracker_.Deallocate(ptr1);
198 expected.requested_bytes -= layout1.size();
199 expected.allocated_bytes -= ptr1_allocated;
200 expected.num_deallocations += 1;
201 EXPECT_METRICS_EQ(expected, metrics);
202
203 Layout layout3 = Layout::Of<uint32_t>();
204 void* ptr3 = tracker_.Allocate(layout3);
205 ASSERT_NE(ptr3, nullptr);
206 size_t ptr3_allocated = tracker_.GetAllocatedLayout(ptr3)->size();
207 expected.AddRequestedBytes(layout3.size());
208 expected.AddAllocatedBytes(ptr3_allocated);
209 expected.num_allocations += 1;
210 EXPECT_METRICS_EQ(expected, metrics);
211
212 tracker_.Deallocate(ptr3);
213 expected.requested_bytes -= layout3.size();
214 expected.allocated_bytes -= ptr3_allocated;
215 expected.num_deallocations += 1;
216 EXPECT_METRICS_EQ(expected, metrics);
217
218 tracker_.Deallocate(ptr2);
219 expected.requested_bytes -= layout2.size();
220 expected.allocated_bytes -= ptr2_allocated;
221 expected.num_deallocations += 1;
222 EXPECT_METRICS_EQ(expected, metrics);
223 }
224
TEST_F(TrackingAllocatorTest,ResizeLarger)225 TEST_F(TrackingAllocatorTest, ResizeLarger) {
226 const TestMetrics& metrics = tracker_.metrics();
227 ExpectedValues expected;
228
229 constexpr Layout layout1 = Layout::Of<uint32_t[3]>();
230 void* ptr = tracker_.Allocate(layout1);
231 size_t ptr_allocated1 = tracker_.GetAllocatedLayout(ptr)->size();
232 ASSERT_NE(ptr, nullptr);
233 expected.AddRequestedBytes(layout1.size());
234 expected.AddAllocatedBytes(ptr_allocated1);
235 expected.num_allocations += 1;
236 EXPECT_METRICS_EQ(expected, metrics);
237
238 constexpr size_t size2 = sizeof(uint32_t[5]);
239 EXPECT_TRUE(tracker_.Resize(ptr, size2));
240 size_t ptr_allocated2 = tracker_.GetAllocatedLayout(ptr)->size();
241 expected.AddRequestedBytes(size2 - layout1.size());
242 expected.AddAllocatedBytes(ptr_allocated2 - ptr_allocated1);
243 expected.num_resizes += 1;
244 EXPECT_METRICS_EQ(expected, metrics);
245
246 tracker_.Deallocate(ptr);
247 expected.requested_bytes -= size2;
248 expected.allocated_bytes -= ptr_allocated2;
249 expected.num_deallocations += 1;
250 EXPECT_METRICS_EQ(expected, metrics);
251 }
252
TEST_F(TrackingAllocatorTest,ResizeSmaller)253 TEST_F(TrackingAllocatorTest, ResizeSmaller) {
254 const TestMetrics& metrics = tracker_.metrics();
255 ExpectedValues expected;
256
257 constexpr Layout layout1 = Layout::Of<uint32_t[2]>();
258 void* ptr = tracker_.Allocate(layout1);
259 size_t ptr_allocated1 = tracker_.GetAllocatedLayout(ptr)->size();
260 ASSERT_NE(ptr, nullptr);
261 expected.AddRequestedBytes(layout1.size());
262 expected.AddAllocatedBytes(ptr_allocated1);
263 expected.num_allocations += 1;
264 EXPECT_METRICS_EQ(expected, metrics);
265
266 constexpr size_t size2 = sizeof(uint32_t[1]);
267 EXPECT_TRUE(tracker_.Resize(ptr, size2));
268 size_t ptr_allocated2 = tracker_.GetAllocatedLayout(ptr)->size();
269 expected.requested_bytes -= layout1.size() - size2;
270 expected.allocated_bytes -= ptr_allocated1 - ptr_allocated2;
271 expected.num_resizes += 1;
272 EXPECT_METRICS_EQ(expected, metrics);
273
274 tracker_.Deallocate(ptr);
275 expected.requested_bytes -= size2;
276 expected.allocated_bytes -= ptr_allocated2;
277 expected.num_deallocations += 1;
278 EXPECT_METRICS_EQ(expected, metrics);
279 }
280
TEST_F(TrackingAllocatorTest,ResizeFailure)281 TEST_F(TrackingAllocatorTest, ResizeFailure) {
282 const TestMetrics& metrics = tracker_.metrics();
283 ExpectedValues expected;
284
285 constexpr Layout layout = Layout::Of<uint32_t[4]>();
286 void* ptr1 = tracker_.Allocate(layout);
287 ASSERT_NE(ptr1, nullptr);
288 size_t ptr1_allocated = tracker_.GetAllocatedLayout(ptr1)->size();
289 expected.AddRequestedBytes(layout.size());
290 expected.AddAllocatedBytes(ptr1_allocated);
291 expected.num_allocations += 1;
292 EXPECT_METRICS_EQ(expected, metrics);
293
294 void* ptr2 = tracker_.Allocate(layout);
295 ASSERT_NE(ptr2, nullptr);
296 size_t ptr2_allocated = tracker_.GetAllocatedLayout(ptr2)->size();
297 expected.AddRequestedBytes(layout.size());
298 expected.AddAllocatedBytes(ptr2_allocated);
299 expected.num_allocations += 1;
300 EXPECT_METRICS_EQ(expected, metrics);
301
302 EXPECT_FALSE(tracker_.Resize(ptr1, layout.size() * 2));
303 expected.num_failures += 1;
304 expected.unfulfilled_bytes += layout.size() * 2;
305 EXPECT_METRICS_EQ(expected, metrics);
306 }
307
TEST_F(TrackingAllocatorTest,Reallocate)308 TEST_F(TrackingAllocatorTest, Reallocate) {
309 const TestMetrics& metrics = tracker_.metrics();
310 ExpectedValues expected;
311
312 constexpr Layout layout1 = Layout::Of<uint32_t[2]>();
313 void* ptr1 = tracker_.Allocate(layout1);
314 ASSERT_NE(ptr1, nullptr);
315 size_t ptr1_allocated = tracker_.GetAllocatedLayout(ptr1)->size();
316 expected.AddRequestedBytes(layout1.size());
317 expected.AddAllocatedBytes(ptr1_allocated);
318 expected.num_allocations += 1;
319 EXPECT_METRICS_EQ(expected, metrics);
320
321 // If `Reallocate` just resizes, no extra memory is allocated
322 constexpr Layout layout2 = Layout::Of<uint32_t[4]>();
323 void* ptr2 = tracker_.Reallocate(ptr1, layout2);
324 EXPECT_EQ(ptr2, ptr1);
325 size_t ptr2_allocated = tracker_.GetAllocatedLayout(ptr2)->size();
326 expected.AddRequestedBytes(layout2.size() - layout1.size());
327 expected.AddAllocatedBytes(ptr2_allocated - ptr1_allocated);
328 expected.num_reallocations += 1;
329 EXPECT_METRICS_EQ(expected, metrics);
330
331 // Make a second allocation to force reallocation.
332 constexpr Layout layout3 = layout1;
333 void* ptr3 = tracker_.Allocate(layout1);
334 ASSERT_NE(ptr3, nullptr);
335 size_t ptr3_allocated = tracker_.GetAllocatedLayout(ptr3)->size();
336 expected.AddRequestedBytes(layout3.size());
337 expected.AddAllocatedBytes(ptr3_allocated);
338 expected.num_allocations += 1;
339 EXPECT_METRICS_EQ(expected, metrics);
340
341 // If `Reallocate` must copy to a new location, it allocates before
342 // deallocating and results in higher peaks.
343 constexpr Layout layout4 = Layout::Of<uint32_t[8]>();
344 void* ptr4 = tracker_.Reallocate(ptr2, layout4);
345 EXPECT_NE(ptr4, ptr2);
346 size_t ptr4_allocated = tracker_.GetAllocatedLayout(ptr4)->size();
347 expected.AddRequestedBytes(layout4.size() - layout2.size());
348 expected.AddAllocatedBytes(ptr4_allocated);
349 expected.allocated_bytes -= ptr2_allocated;
350 expected.num_reallocations += 1;
351 EXPECT_METRICS_EQ(expected, metrics);
352
353 tracker_.Deallocate(ptr3);
354 expected.requested_bytes -= layout3.size();
355 expected.allocated_bytes -= ptr3_allocated;
356 expected.num_deallocations += 1;
357 EXPECT_METRICS_EQ(expected, metrics);
358
359 tracker_.Deallocate(ptr4);
360 expected.requested_bytes -= layout4.size();
361 expected.allocated_bytes -= ptr4_allocated;
362 expected.num_deallocations += 1;
363 EXPECT_METRICS_EQ(expected, metrics);
364 }
365
TEST_F(TrackingAllocatorTest,ReallocateFailure)366 TEST_F(TrackingAllocatorTest, ReallocateFailure) {
367 const TestMetrics& metrics = tracker_.metrics();
368 ExpectedValues expected;
369
370 constexpr Layout layout1 = Layout::Of<uint32_t[4]>();
371 void* ptr1 = tracker_.Allocate(layout1);
372 ASSERT_NE(ptr1, nullptr);
373 size_t ptr1_allocated = tracker_.GetAllocatedLayout(ptr1)->size();
374 expected.AddRequestedBytes(layout1.size());
375 expected.AddAllocatedBytes(ptr1_allocated);
376 expected.num_allocations += 1;
377 EXPECT_METRICS_EQ(expected, metrics);
378
379 constexpr Layout layout2 = Layout(0x10000000U, 1);
380 void* ptr2 = tracker_.Reallocate(ptr1, layout2);
381 EXPECT_EQ(ptr2, nullptr);
382 expected.num_failures += 1;
383 expected.unfulfilled_bytes += layout2.size();
384 EXPECT_METRICS_EQ(expected, metrics);
385 }
386
387 } // namespace
388