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/best_fit.h"
16
17 #include "pw_allocator/best_fit_block_allocator.h"
18 #include "pw_allocator/block_allocator_testing.h"
19 #include "pw_allocator/buffer.h"
20 #include "pw_unit_test/framework.h"
21
22 namespace {
23
24 // Test fixtures.
25
26 using ::pw::allocator::Layout;
27 using ::pw::allocator::test::BlockAllocatorTest;
28 using ::pw::allocator::test::Preallocation;
29 using BlockType = ::pw::allocator::BestFitBlock<uint16_t>;
30 using BestFitAllocator = ::pw::allocator::BestFitAllocator<BlockType>;
31
32 class BestFitAllocatorTest : public BlockAllocatorTest<BestFitAllocator> {
33 public:
BestFitAllocatorTest()34 BestFitAllocatorTest() : BlockAllocatorTest(allocator_) {}
35
36 private:
37 BestFitAllocator allocator_;
38 };
39
40 // Unit tests.
41
TEST_F(BestFitAllocatorTest,AutomaticallyInit)42 TEST_F(BestFitAllocatorTest, AutomaticallyInit) {
43 BestFitAllocator allocator(GetBytes());
44 AutomaticallyInit(allocator);
45 }
46
TEST_F(BestFitAllocatorTest,ExplicitlyInit)47 TEST_F(BestFitAllocatorTest, ExplicitlyInit) {
48 BestFitAllocator allocator;
49 ExplicitlyInit(allocator);
50 }
51
TEST_F(BestFitAllocatorTest,GetCapacity)52 TEST_F(BestFitAllocatorTest, GetCapacity) { GetCapacity(); }
53
TEST_F(BestFitAllocatorTest,AllocateLarge)54 TEST_F(BestFitAllocatorTest, AllocateLarge) { AllocateLarge(); }
55
TEST_F(BestFitAllocatorTest,AllocateSmall)56 TEST_F(BestFitAllocatorTest, AllocateSmall) { AllocateSmall(); }
57
TEST_F(BestFitAllocatorTest,AllocateLargeAlignment)58 TEST_F(BestFitAllocatorTest, AllocateLargeAlignment) {
59 AllocateLargeAlignment();
60 }
61
TEST_F(BestFitAllocatorTest,AllocateAlignmentFailure)62 TEST_F(BestFitAllocatorTest, AllocateAlignmentFailure) {
63 AllocateAlignmentFailure();
64 }
65
TEST_F(BestFitAllocatorTest,AllocatesBestCompatible)66 TEST_F(BestFitAllocatorTest, AllocatesBestCompatible) {
67 auto& allocator = GetAllocator({
68 {kLargeOuterSize, Preallocation::kFree},
69 {kSmallerOuterSize, Preallocation::kUsed},
70 {kSmallOuterSize, Preallocation::kFree},
71 {kSmallerOuterSize, Preallocation::kUsed},
72 {kLargerOuterSize, Preallocation::kFree},
73 {Preallocation::kSizeRemaining, Preallocation::kUsed},
74 });
75
76 void* ptr1 = allocator.Allocate(Layout(kSmallInnerSize, 1));
77 EXPECT_LT(Fetch(1), ptr1);
78 EXPECT_LT(ptr1, Fetch(3));
79
80 void* ptr2 = allocator.Allocate(Layout(kSmallInnerSize, 1));
81 EXPECT_LT(ptr2, Fetch(1));
82
83 // A second small block fits in the leftovers of the first "Large" block.
84 void* ptr3 = allocator.Allocate(Layout(kSmallInnerSize, 1));
85 EXPECT_LT(ptr3, Fetch(1));
86
87 allocator.Deallocate(ptr1);
88 allocator.Deallocate(ptr2);
89 allocator.Deallocate(ptr3);
90 }
91
TEST_F(BestFitAllocatorTest,DeallocateNull)92 TEST_F(BestFitAllocatorTest, DeallocateNull) { DeallocateNull(); }
93
TEST_F(BestFitAllocatorTest,DeallocateShuffled)94 TEST_F(BestFitAllocatorTest, DeallocateShuffled) { DeallocateShuffled(); }
95
TEST_F(BestFitAllocatorTest,IterateOverBlocks)96 TEST_F(BestFitAllocatorTest, IterateOverBlocks) { IterateOverBlocks(); }
97
TEST_F(BestFitAllocatorTest,ResizeNull)98 TEST_F(BestFitAllocatorTest, ResizeNull) { ResizeNull(); }
99
TEST_F(BestFitAllocatorTest,ResizeLargeSame)100 TEST_F(BestFitAllocatorTest, ResizeLargeSame) { ResizeLargeSame(); }
101
TEST_F(BestFitAllocatorTest,ResizeLargeSmaller)102 TEST_F(BestFitAllocatorTest, ResizeLargeSmaller) { ResizeLargeSmaller(); }
103
TEST_F(BestFitAllocatorTest,ResizeLargeLarger)104 TEST_F(BestFitAllocatorTest, ResizeLargeLarger) { ResizeLargeLarger(); }
105
TEST_F(BestFitAllocatorTest,ResizeLargeLargerFailure)106 TEST_F(BestFitAllocatorTest, ResizeLargeLargerFailure) {
107 ResizeLargeLargerFailure();
108 }
109
TEST_F(BestFitAllocatorTest,ResizeSmallSame)110 TEST_F(BestFitAllocatorTest, ResizeSmallSame) { ResizeSmallSame(); }
111
TEST_F(BestFitAllocatorTest,ResizeSmallSmaller)112 TEST_F(BestFitAllocatorTest, ResizeSmallSmaller) { ResizeSmallSmaller(); }
113
TEST_F(BestFitAllocatorTest,ResizeSmallLarger)114 TEST_F(BestFitAllocatorTest, ResizeSmallLarger) { ResizeSmallLarger(); }
115
TEST_F(BestFitAllocatorTest,ResizeSmallLargerFailure)116 TEST_F(BestFitAllocatorTest, ResizeSmallLargerFailure) {
117 ResizeSmallLargerFailure();
118 }
119
TEST_F(BestFitAllocatorTest,MeasureFragmentation)120 TEST_F(BestFitAllocatorTest, MeasureFragmentation) { MeasureFragmentation(); }
121
TEST_F(BestFitAllocatorTest,PoisonPeriodically)122 TEST_F(BestFitAllocatorTest, PoisonPeriodically) { PoisonPeriodically(); }
123
124 // TODO(b/376730645): Remove this test when the legacy alias is deprecated.
125 using BestFitBlockAllocator = ::pw::allocator::BestFitBlockAllocator<uint16_t>;
126 class BestFitBlockAllocatorTest
127 : public BlockAllocatorTest<BestFitBlockAllocator> {
128 public:
BestFitBlockAllocatorTest()129 BestFitBlockAllocatorTest() : BlockAllocatorTest(allocator_) {}
130
131 private:
132 BestFitBlockAllocator allocator_;
133 };
TEST_F(BestFitBlockAllocatorTest,AllocatesBestCompatible)134 TEST_F(BestFitBlockAllocatorTest, AllocatesBestCompatible) {
135 auto& allocator = GetAllocator({
136 {kLargeOuterSize, Preallocation::kFree},
137 {kSmallerOuterSize, Preallocation::kUsed},
138 {kSmallOuterSize, Preallocation::kFree},
139 {kSmallerOuterSize, Preallocation::kUsed},
140 {kLargerOuterSize, Preallocation::kFree},
141 {Preallocation::kSizeRemaining, Preallocation::kUsed},
142 });
143
144 void* ptr1 = allocator.Allocate(Layout(kSmallInnerSize, 1));
145 EXPECT_LT(Fetch(1), ptr1);
146 EXPECT_LT(ptr1, Fetch(3));
147
148 void* ptr2 = allocator.Allocate(Layout(kSmallInnerSize, 1));
149 EXPECT_LT(ptr2, Fetch(1));
150
151 // A second small block fits in the leftovers of the first "Large" block.
152 void* ptr3 = allocator.Allocate(Layout(kSmallInnerSize, 1));
153 EXPECT_LT(ptr3, Fetch(1));
154
155 allocator.Deallocate(ptr1);
156 allocator.Deallocate(ptr2);
157 allocator.Deallocate(ptr3);
158 }
159
160 // Fuzz tests.
161
162 using ::pw::allocator::test::BlockAlignedBuffer;
163 using ::pw::allocator::test::BlockAllocatorFuzzer;
164 using ::pw::allocator::test::DefaultArbitraryRequests;
165 using ::pw::allocator::test::Request;
166
DoesNotCorruptBlocks(const pw::Vector<Request> & requests)167 void DoesNotCorruptBlocks(const pw::Vector<Request>& requests) {
168 static BlockAlignedBuffer<BlockType> buffer;
169 static BestFitAllocator allocator(buffer.as_span());
170 static BlockAllocatorFuzzer fuzzer(allocator);
171 fuzzer.DoesNotCorruptBlocks(requests);
172 }
173
174 FUZZ_TEST(BestFitAllocatorFuzzTest, DoesNotCorruptBlocks)
175 .WithDomains(DefaultArbitraryRequests());
176
177 } // namespace
178