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