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