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/first_fit.h"
16
17 #include <cstdint>
18
19 #include "pw_allocator/block/detailed_block.h"
20 #include "pw_allocator/block_allocator_testing.h"
21 #include "pw_allocator/buffer.h"
22 #include "pw_allocator/dual_first_fit_block_allocator.h"
23 #include "pw_allocator/first_fit_block_allocator.h"
24 #include "pw_allocator/last_fit_block_allocator.h"
25 #include "pw_unit_test/framework.h"
26
27 namespace {
28
29 using ::pw::allocator::Layout;
30 using ::pw::allocator::test::Preallocation;
31 using BlockType = ::pw::allocator::FirstFitBlock<uint16_t>;
32 using FirstFitAllocator = ::pw::allocator::FirstFitAllocator<BlockType>;
33 using ::pw::allocator::test::BlockAllocatorTest;
34
35 // Minimum size of a "large" allocation; allocation less than this size are
36 // considered "small" when using the "dual first fit" strategy.
37 static constexpr size_t kThreshold =
38 BlockAllocatorTest<FirstFitAllocator>::kSmallInnerSize * 2;
39
40 class FirstFitAllocatorTest : public BlockAllocatorTest<FirstFitAllocator> {
41 public:
FirstFitAllocatorTest()42 FirstFitAllocatorTest() : BlockAllocatorTest(allocator_) {}
43
44 private:
45 FirstFitAllocator allocator_;
46 };
47
TEST_F(FirstFitAllocatorTest,AutomaticallyInit)48 TEST_F(FirstFitAllocatorTest, AutomaticallyInit) {
49 FirstFitAllocator allocator(GetBytes());
50 AutomaticallyInit(allocator);
51 }
52
TEST_F(FirstFitAllocatorTest,ExplicitlyInit)53 TEST_F(FirstFitAllocatorTest, ExplicitlyInit) {
54 FirstFitAllocator allocator;
55 ExplicitlyInit(allocator);
56 }
57
TEST_F(FirstFitAllocatorTest,GetCapacity)58 TEST_F(FirstFitAllocatorTest, GetCapacity) { GetCapacity(); }
59
TEST_F(FirstFitAllocatorTest,AllocateLarge)60 TEST_F(FirstFitAllocatorTest, AllocateLarge) { AllocateLarge(); }
61
TEST_F(FirstFitAllocatorTest,AllocateSmall)62 TEST_F(FirstFitAllocatorTest, AllocateSmall) { AllocateSmall(); }
63
TEST_F(FirstFitAllocatorTest,AllocateLargeAlignment)64 TEST_F(FirstFitAllocatorTest, AllocateLargeAlignment) {
65 AllocateLargeAlignment();
66 }
67
TEST_F(FirstFitAllocatorTest,AllocateAlignmentFailure)68 TEST_F(FirstFitAllocatorTest, AllocateAlignmentFailure) {
69 AllocateAlignmentFailure();
70 }
71
TEST_F(FirstFitAllocatorTest,AllocatesZeroThreshold)72 TEST_F(FirstFitAllocatorTest, AllocatesZeroThreshold) {
73 FirstFitAllocator& allocator = GetAllocator({
74 {kSmallOuterSize, Preallocation::kFree},
75 {kSmallerOuterSize, Preallocation::kUsed},
76 {kSmallOuterSize, Preallocation::kFree},
77 {kSmallerOuterSize, Preallocation::kUsed},
78 {kLargeOuterSize, Preallocation::kFree},
79 {Preallocation::kSizeRemaining, Preallocation::kUsed},
80 });
81
82 Store(0, allocator.Allocate(Layout(kSmallInnerSize, 1)));
83 EXPECT_EQ(NextAfter(0), Fetch(1));
84 Store(4, allocator.Allocate(Layout(kLargeInnerSize, 1)));
85 EXPECT_EQ(NextAfter(3), Fetch(4));
86 EXPECT_EQ(NextAfter(4), Fetch(5));
87 }
88
TEST_F(FirstFitAllocatorTest,AllocatesMaxThreshold)89 TEST_F(FirstFitAllocatorTest, AllocatesMaxThreshold) {
90 FirstFitAllocator& allocator = GetAllocator({
91 {kLargeOuterSize, Preallocation::kFree},
92 {kSmallerOuterSize, Preallocation::kUsed},
93 {kSmallOuterSize, Preallocation::kFree},
94 {kSmallerOuterSize, Preallocation::kUsed},
95 {kSmallOuterSize, Preallocation::kFree},
96 {Preallocation::kSizeRemaining, Preallocation::kUsed},
97 });
98 allocator.set_threshold(std::numeric_limits<size_t>::max());
99
100 Store(0, allocator.Allocate(Layout(kLargeInnerSize, 1)));
101 EXPECT_EQ(NextAfter(0), Fetch(1));
102 Store(4, allocator.Allocate(Layout(kSmallInnerSize, 1)));
103 EXPECT_EQ(NextAfter(3), Fetch(4));
104 EXPECT_EQ(NextAfter(4), Fetch(5));
105 }
106
TEST_F(FirstFitAllocatorTest,AllocatesUsingThreshold)107 TEST_F(FirstFitAllocatorTest, AllocatesUsingThreshold) {
108 FirstFitAllocator& allocator = GetAllocator({
109 {kLargeOuterSize, Preallocation::kFree},
110 {kSmallerOuterSize, Preallocation::kUsed},
111 {kSmallOuterSize, Preallocation::kFree},
112 {Preallocation::kSizeRemaining, Preallocation::kUsed},
113 {kLargeOuterSize, Preallocation::kFree},
114 {kSmallerOuterSize, Preallocation::kUsed},
115 {kSmallOuterSize, Preallocation::kFree},
116 });
117 allocator.set_threshold(kThreshold);
118
119 Store(0, allocator.Allocate(Layout(kLargeInnerSize, 1)));
120 EXPECT_EQ(NextAfter(0), Fetch(1));
121 Store(4, allocator.Allocate(Layout(kLargeInnerSize, 1)));
122 EXPECT_EQ(NextAfter(3), Fetch(4));
123 EXPECT_EQ(NextAfter(4), Fetch(5));
124 Store(6, allocator.Allocate(Layout(kSmallInnerSize, 1)));
125 EXPECT_EQ(NextAfter(5), Fetch(6));
126 EXPECT_EQ(NextAfter(6), Fetch(7));
127 Store(2, allocator.Allocate(Layout(kSmallInnerSize, 1)));
128 EXPECT_EQ(NextAfter(1), Fetch(2));
129 EXPECT_EQ(NextAfter(2), Fetch(3));
130 }
131
TEST_F(FirstFitAllocatorTest,AllocatesFromCorrectEnd)132 TEST_F(FirstFitAllocatorTest, AllocatesFromCorrectEnd) {
133 FirstFitAllocator allocator(GetBytes());
134 allocator.set_threshold(kThreshold);
135
136 void* ptr1 = allocator.Allocate(Layout(kSmallInnerSize, 1));
137 ASSERT_NE(ptr1, nullptr);
138
139 void* ptr2 = allocator.Allocate(Layout(kLargeInnerSize, 1));
140 ASSERT_NE(ptr2, nullptr);
141
142 auto* block_a = BlockType::FromUsableSpace(ptr2);
143 auto* block_b = block_a->Next();
144 auto* block_c = BlockType::FromUsableSpace(ptr1);
145
146 ASSERT_NE(block_b, nullptr);
147 EXPECT_TRUE(block_b->IsFree());
148 EXPECT_EQ(block_b->Next(), block_c);
149
150 allocator.Deallocate(ptr1);
151 allocator.Deallocate(ptr2);
152 }
153
TEST_F(FirstFitAllocatorTest,DeallocateNull)154 TEST_F(FirstFitAllocatorTest, DeallocateNull) { DeallocateNull(); }
155
TEST_F(FirstFitAllocatorTest,DeallocateShuffled)156 TEST_F(FirstFitAllocatorTest, DeallocateShuffled) { DeallocateShuffled(); }
157
TEST_F(FirstFitAllocatorTest,IterateOverBlocks)158 TEST_F(FirstFitAllocatorTest, IterateOverBlocks) { IterateOverBlocks(); }
159
TEST_F(FirstFitAllocatorTest,ResizeNull)160 TEST_F(FirstFitAllocatorTest, ResizeNull) { ResizeNull(); }
161
TEST_F(FirstFitAllocatorTest,ResizeLargeSame)162 TEST_F(FirstFitAllocatorTest, ResizeLargeSame) { ResizeLargeSame(); }
163
TEST_F(FirstFitAllocatorTest,ResizeLargeSmaller)164 TEST_F(FirstFitAllocatorTest, ResizeLargeSmaller) { ResizeLargeSmaller(); }
165
TEST_F(FirstFitAllocatorTest,ResizeLargeLarger)166 TEST_F(FirstFitAllocatorTest, ResizeLargeLarger) { ResizeLargeLarger(); }
167
TEST_F(FirstFitAllocatorTest,ResizeLargeLargerFailure)168 TEST_F(FirstFitAllocatorTest, ResizeLargeLargerFailure) {
169 ResizeLargeLargerFailure();
170 }
171
TEST_F(FirstFitAllocatorTest,ResizeSmallSame)172 TEST_F(FirstFitAllocatorTest, ResizeSmallSame) { ResizeSmallSame(); }
173
TEST_F(FirstFitAllocatorTest,ResizeSmallSmaller)174 TEST_F(FirstFitAllocatorTest, ResizeSmallSmaller) { ResizeSmallSmaller(); }
175
TEST_F(FirstFitAllocatorTest,ResizeSmallLarger)176 TEST_F(FirstFitAllocatorTest, ResizeSmallLarger) { ResizeSmallLarger(); }
177
TEST_F(FirstFitAllocatorTest,ResizeSmallLargerFailure)178 TEST_F(FirstFitAllocatorTest, ResizeSmallLargerFailure) {
179 ResizeSmallLargerFailure();
180 }
181
TEST_F(FirstFitAllocatorTest,ResizeLargeSmallerAcrossThreshold)182 TEST_F(FirstFitAllocatorTest, ResizeLargeSmallerAcrossThreshold) {
183 FirstFitAllocator& allocator = GetAllocator({
184 {kThreshold * 2, Preallocation::kUsed},
185 {Preallocation::kSizeRemaining, Preallocation::kFree},
186 });
187 allocator.set_threshold(kThreshold);
188
189 // Shrinking succeeds, and the pointer is unchanged even though it is now
190 // below the threshold.
191 size_t new_size = kThreshold / 2;
192 ASSERT_TRUE(allocator.Resize(Fetch(0), new_size));
193 UseMemory(Fetch(0), kThreshold / 2);
194 }
195
TEST_F(FirstFitAllocatorTest,ResizeSmallLargerAcrossThreshold)196 TEST_F(FirstFitAllocatorTest, ResizeSmallLargerAcrossThreshold) {
197 FirstFitAllocator& allocator = GetAllocator({
198 {Preallocation::kSizeRemaining, Preallocation::kUsed},
199 {kThreshold / 2, Preallocation::kUsed},
200 {kThreshold * 2, Preallocation::kFree},
201 });
202 allocator.set_threshold(kThreshold);
203
204 // Growing succeeds, and the pointer is unchanged even though it is now
205 // above the threshold.
206 size_t new_size = kThreshold * 2;
207 ASSERT_TRUE(allocator.Resize(Fetch(1), new_size));
208 UseMemory(Fetch(1), kThreshold * 2);
209 }
210
TEST_F(FirstFitAllocatorTest,MeasureFragmentation)211 TEST_F(FirstFitAllocatorTest, MeasureFragmentation) { MeasureFragmentation(); }
212
TEST_F(FirstFitAllocatorTest,PoisonPeriodically)213 TEST_F(FirstFitAllocatorTest, PoisonPeriodically) { PoisonPeriodically(); }
214
215 // TODO(b/376730645): Remove this test when the legacy alias is deprecated.
216 using DualFirstFitBlockAllocator =
217 ::pw::allocator::DualFirstFitBlockAllocator<uint16_t>;
218 class DualFirstFitBlockAllocatorTest
219 : public BlockAllocatorTest<DualFirstFitBlockAllocator> {
220 public:
DualFirstFitBlockAllocatorTest()221 DualFirstFitBlockAllocatorTest() : BlockAllocatorTest(allocator_) {}
222
223 private:
224 DualFirstFitBlockAllocator allocator_;
225 };
TEST_F(DualFirstFitBlockAllocatorTest,AllocatesUsingThreshold)226 TEST_F(DualFirstFitBlockAllocatorTest, AllocatesUsingThreshold) {
227 auto& allocator = GetAllocator({
228 {kLargeOuterSize, Preallocation::kFree},
229 {kSmallerOuterSize, Preallocation::kUsed},
230 {kSmallOuterSize, Preallocation::kFree},
231 {Preallocation::kSizeRemaining, Preallocation::kUsed},
232 {kLargeOuterSize, Preallocation::kFree},
233 {kSmallerOuterSize, Preallocation::kUsed},
234 {kSmallOuterSize, Preallocation::kFree},
235 });
236 allocator.set_threshold(kThreshold);
237
238 Store(0, allocator.Allocate(Layout(kLargeInnerSize, 1)));
239 EXPECT_EQ(NextAfter(0), Fetch(1));
240 Store(4, allocator.Allocate(Layout(kLargeInnerSize, 1)));
241 EXPECT_EQ(NextAfter(3), Fetch(4));
242 EXPECT_EQ(NextAfter(4), Fetch(5));
243 Store(6, allocator.Allocate(Layout(kSmallInnerSize, 1)));
244 EXPECT_EQ(NextAfter(5), Fetch(6));
245 EXPECT_EQ(NextAfter(6), Fetch(7));
246 Store(2, allocator.Allocate(Layout(kSmallInnerSize, 1)));
247 EXPECT_EQ(NextAfter(1), Fetch(2));
248 EXPECT_EQ(NextAfter(2), Fetch(3));
249 }
250
251 // TODO(b/376730645): Remove this test when the legacy alias is deprecated.
252 using FirstFitBlockAllocator =
253 ::pw::allocator::FirstFitBlockAllocator<uint16_t>;
254 class FirstFitBlockAllocatorTest
255 : public BlockAllocatorTest<FirstFitBlockAllocator> {
256 public:
FirstFitBlockAllocatorTest()257 FirstFitBlockAllocatorTest() : BlockAllocatorTest(allocator_) {}
258
259 private:
260 FirstFitBlockAllocator allocator_;
261 };
TEST_F(FirstFitBlockAllocatorTest,AllocatesFirstCompatible)262 TEST_F(FirstFitBlockAllocatorTest, AllocatesFirstCompatible) {
263 auto& allocator = GetAllocator({
264 {kSmallOuterSize, Preallocation::kFree},
265 {kSmallerOuterSize, Preallocation::kUsed},
266 {kSmallOuterSize, Preallocation::kFree},
267 {kSmallerOuterSize, Preallocation::kUsed},
268 {kLargeOuterSize, Preallocation::kFree},
269 {Preallocation::kSizeRemaining, Preallocation::kUsed},
270 });
271
272 Store(0, allocator.Allocate(Layout(kSmallInnerSize, 1)));
273 EXPECT_EQ(NextAfter(0), Fetch(1));
274 Store(4, allocator.Allocate(Layout(kLargeInnerSize, 1)));
275 EXPECT_EQ(NextAfter(3), Fetch(4));
276 EXPECT_EQ(NextAfter(4), Fetch(5));
277 }
278
279 // TODO(b/376730645): Remove this test when the legacy alias is deprecated.
280 using LastFitBlockAllocator = ::pw::allocator::LastFitBlockAllocator<uint16_t>;
281 class LastFitBlockAllocatorTest
282 : public BlockAllocatorTest<LastFitBlockAllocator> {
283 public:
LastFitBlockAllocatorTest()284 LastFitBlockAllocatorTest() : BlockAllocatorTest(allocator_) {}
285
286 private:
287 LastFitBlockAllocator allocator_;
288 };
TEST_F(LastFitBlockAllocatorTest,AllocatesLastCompatible)289 TEST_F(LastFitBlockAllocatorTest, AllocatesLastCompatible) {
290 auto& allocator = GetAllocator({
291 {kLargeOuterSize, Preallocation::kFree},
292 {kSmallerOuterSize, Preallocation::kUsed},
293 {kSmallOuterSize, Preallocation::kFree},
294 {kSmallerOuterSize, Preallocation::kUsed},
295 {kSmallOuterSize, Preallocation::kFree},
296 {Preallocation::kSizeRemaining, Preallocation::kUsed},
297 });
298
299 Store(0, allocator.Allocate(Layout(kLargeInnerSize, 1)));
300 EXPECT_EQ(NextAfter(0), Fetch(1));
301 Store(4, allocator.Allocate(Layout(kSmallInnerSize, 1)));
302 EXPECT_EQ(NextAfter(3), Fetch(4));
303 EXPECT_EQ(NextAfter(4), Fetch(5));
304 }
305
306 // Fuzz tests.
307
308 using ::pw::allocator::test::BlockAlignedBuffer;
309 using ::pw::allocator::test::BlockAllocatorFuzzer;
310 using ::pw::allocator::test::DefaultArbitraryRequests;
311 using ::pw::allocator::test::Request;
312
DoesNotCorruptBlocks(const pw::Vector<Request> & requests)313 void DoesNotCorruptBlocks(const pw::Vector<Request>& requests) {
314 static BlockAlignedBuffer<BlockType> buffer;
315 static FirstFitAllocator allocator(buffer.as_span());
316 static BlockAllocatorFuzzer fuzzer(allocator);
317 fuzzer.DoesNotCorruptBlocks(requests);
318 }
319
320 FUZZ_TEST(FirstFitAllocatorFuzzTest, DoesNotCorruptBlocks)
321 .WithDomains(DefaultArbitraryRequests());
322
WorksWithAnyThreshold(const pw::Vector<Request> & requests,size_t threshold)323 void WorksWithAnyThreshold(const pw::Vector<Request>& requests,
324 size_t threshold) {
325 static BlockAlignedBuffer<BlockType> buffer;
326 FirstFitAllocator allocator(buffer.as_span(), threshold);
327 BlockAllocatorFuzzer fuzzer(allocator);
328 fuzzer.DoesNotCorruptBlocks(requests);
329 }
330
331 FUZZ_TEST(FirstFitAllocatorFuzzTest, WorksWithAnyThreshold)
332 .WithDomains(DefaultArbitraryRequests(), fuzztest::Arbitrary<size_t>());
333
334 } // namespace
335