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/dual_first_fit_block_allocator.h"
16
17 #include "pw_allocator/block_allocator_testing.h"
18 #include "pw_unit_test/framework.h"
19
20 namespace {
21
22 // Test fixtures.
23
24 using ::pw::allocator::Layout;
25 using ::pw::allocator::test::Preallocation;
26 using DualFirstFitBlockAllocator =
27 ::pw::allocator::DualFirstFitBlockAllocator<uint16_t>;
28 using BlockAllocatorTest =
29 ::pw::allocator::test::BlockAllocatorTest<DualFirstFitBlockAllocator>;
30
31 // Minimum size of a "large" allocation; allocation less than this size are
32 // considered "small" when using the DualFirstFit strategy.
33 static constexpr size_t kDualFitThreshold =
34 BlockAllocatorTest::kSmallInnerSize * 2;
35
36 class DualFirstFitBlockAllocatorTest : public BlockAllocatorTest {
37 public:
DualFirstFitBlockAllocatorTest()38 DualFirstFitBlockAllocatorTest() : BlockAllocatorTest(allocator_) {}
39
40 private:
41 DualFirstFitBlockAllocator allocator_;
42 };
43
44 // Unit tests.
45
TEST_F(DualFirstFitBlockAllocatorTest,CanAutomaticallyInit)46 TEST_F(DualFirstFitBlockAllocatorTest, CanAutomaticallyInit) {
47 DualFirstFitBlockAllocator allocator(GetBytes(), kDualFitThreshold);
48 CanAutomaticallyInit(allocator);
49 }
50
TEST_F(DualFirstFitBlockAllocatorTest,CanExplicitlyInit)51 TEST_F(DualFirstFitBlockAllocatorTest, CanExplicitlyInit) {
52 DualFirstFitBlockAllocator allocator;
53 CanExplicitlyInit(allocator);
54 }
55
TEST_F(DualFirstFitBlockAllocatorTest,GetCapacity)56 TEST_F(DualFirstFitBlockAllocatorTest, GetCapacity) { GetCapacity(); }
57
TEST_F(DualFirstFitBlockAllocatorTest,AllocateLarge)58 TEST_F(DualFirstFitBlockAllocatorTest, AllocateLarge) { AllocateLarge(); }
59
TEST_F(DualFirstFitBlockAllocatorTest,AllocateSmall)60 TEST_F(DualFirstFitBlockAllocatorTest, AllocateSmall) { AllocateSmall(); }
61
TEST_F(DualFirstFitBlockAllocatorTest,AllocateLargeAlignment)62 TEST_F(DualFirstFitBlockAllocatorTest, AllocateLargeAlignment) {
63 AllocateLargeAlignment();
64 }
65
TEST_F(DualFirstFitBlockAllocatorTest,AllocateAlignmentFailure)66 TEST_F(DualFirstFitBlockAllocatorTest, AllocateAlignmentFailure) {
67 AllocateAlignmentFailure();
68 }
69
TEST_F(DualFirstFitBlockAllocatorTest,AllocatesUsingThreshold)70 TEST_F(DualFirstFitBlockAllocatorTest, AllocatesUsingThreshold) {
71 auto& allocator = GetAllocator({
72 {kLargeOuterSize, Preallocation::kIndexFree},
73 {kSmallerOuterSize, 1},
74 {kSmallOuterSize, Preallocation::kIndexFree},
75 {Preallocation::kSizeRemaining, 3},
76 {kLargeOuterSize, Preallocation::kIndexFree},
77 {kSmallerOuterSize, 5},
78 {kSmallOuterSize, Preallocation::kIndexFree},
79 });
80 auto& dual_first_fit_block_allocator =
81 static_cast<DualFirstFitBlockAllocator&>(allocator);
82 dual_first_fit_block_allocator.set_threshold(kDualFitThreshold);
83
84 Store(0, allocator.Allocate(Layout(kLargeInnerSize, 1)));
85 EXPECT_EQ(NextAfter(0), Fetch(1));
86 Store(4, allocator.Allocate(Layout(kLargeInnerSize, 1)));
87 EXPECT_EQ(NextAfter(3), Fetch(4));
88 EXPECT_EQ(NextAfter(4), Fetch(5));
89 Store(6, allocator.Allocate(Layout(kSmallInnerSize, 1)));
90 EXPECT_EQ(NextAfter(5), Fetch(6));
91 EXPECT_EQ(NextAfter(6), Fetch(7));
92 Store(2, allocator.Allocate(Layout(kSmallInnerSize, 1)));
93 EXPECT_EQ(NextAfter(1), Fetch(2));
94 EXPECT_EQ(NextAfter(2), Fetch(3));
95 }
96
TEST_F(DualFirstFitBlockAllocatorTest,DeallocateNull)97 TEST_F(DualFirstFitBlockAllocatorTest, DeallocateNull) { DeallocateNull(); }
98
TEST_F(DualFirstFitBlockAllocatorTest,DeallocateShuffled)99 TEST_F(DualFirstFitBlockAllocatorTest, DeallocateShuffled) {
100 DeallocateShuffled();
101 }
102
TEST_F(DualFirstFitBlockAllocatorTest,IterateOverBlocks)103 TEST_F(DualFirstFitBlockAllocatorTest, IterateOverBlocks) {
104 IterateOverBlocks();
105 }
106
TEST_F(DualFirstFitBlockAllocatorTest,ResizeNull)107 TEST_F(DualFirstFitBlockAllocatorTest, ResizeNull) { ResizeNull(); }
108
TEST_F(DualFirstFitBlockAllocatorTest,ResizeLargeSame)109 TEST_F(DualFirstFitBlockAllocatorTest, ResizeLargeSame) { ResizeLargeSame(); }
110
TEST_F(DualFirstFitBlockAllocatorTest,ResizeLargeSmaller)111 TEST_F(DualFirstFitBlockAllocatorTest, ResizeLargeSmaller) {
112 ResizeLargeSmaller();
113 }
114
TEST_F(DualFirstFitBlockAllocatorTest,ResizeLargeLarger)115 TEST_F(DualFirstFitBlockAllocatorTest, ResizeLargeLarger) {
116 ResizeLargeLarger();
117 }
118
TEST_F(DualFirstFitBlockAllocatorTest,ResizeLargeLargerFailure)119 TEST_F(DualFirstFitBlockAllocatorTest, ResizeLargeLargerFailure) {
120 ResizeLargeLargerFailure();
121 }
122
TEST_F(DualFirstFitBlockAllocatorTest,ResizeSmallSame)123 TEST_F(DualFirstFitBlockAllocatorTest, ResizeSmallSame) { ResizeSmallSame(); }
124
TEST_F(DualFirstFitBlockAllocatorTest,ResizeSmallSmaller)125 TEST_F(DualFirstFitBlockAllocatorTest, ResizeSmallSmaller) {
126 ResizeSmallSmaller();
127 }
128
TEST_F(DualFirstFitBlockAllocatorTest,ResizeSmallLarger)129 TEST_F(DualFirstFitBlockAllocatorTest, ResizeSmallLarger) {
130 ResizeSmallLarger();
131 }
132
TEST_F(DualFirstFitBlockAllocatorTest,ResizeSmallLargerFailure)133 TEST_F(DualFirstFitBlockAllocatorTest, ResizeSmallLargerFailure) {
134 ResizeSmallLargerFailure();
135 }
136
TEST_F(DualFirstFitBlockAllocatorTest,ResizeLargeSmallerAcrossThreshold)137 TEST_F(DualFirstFitBlockAllocatorTest, ResizeLargeSmallerAcrossThreshold) {
138 auto& allocator = GetAllocator({{kDualFitThreshold * 2, 0}});
139 // Shrinking succeeds, and the pointer is unchanged even though it is now
140 // below the threshold.
141 size_t new_size = kDualFitThreshold / 2;
142 ASSERT_TRUE(allocator.Resize(Fetch(0), new_size));
143 UseMemory(Fetch(0), kDualFitThreshold / 2);
144 }
145
TEST_F(DualFirstFitBlockAllocatorTest,ResizeSmallLargerAcrossThreshold)146 TEST_F(DualFirstFitBlockAllocatorTest, ResizeSmallLargerAcrossThreshold) {
147 auto& allocator = GetAllocator({
148 {Preallocation::kSizeRemaining, Preallocation::kIndexNext},
149 {kDualFitThreshold / 2, 1},
150 {kDualFitThreshold * 2, Preallocation::kIndexFree},
151 });
152 // Growing succeeds, and the pointer is unchanged even though it is now
153 // above the threshold.
154 size_t new_size = kDualFitThreshold * 2;
155 ASSERT_TRUE(allocator.Resize(Fetch(1), new_size));
156 UseMemory(Fetch(1), kDualFitThreshold * 2);
157 }
158
TEST_F(DualFirstFitBlockAllocatorTest,CanMeasureFragmentation)159 TEST_F(DualFirstFitBlockAllocatorTest, CanMeasureFragmentation) {
160 CanMeasureFragmentation();
161 }
162
163 } // namespace
164