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/bucket_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 constexpr size_t kMinChunkSize = 64;
25 constexpr size_t kNumBuckets = 4;
26
27 using ::pw::allocator::Layout;
28 using ::pw::allocator::test::Preallocation;
29 using BucketBlockAllocator =
30 ::pw::allocator::BucketBlockAllocator<uint16_t, kMinChunkSize, kNumBuckets>;
31 using BlockAllocatorTest =
32 ::pw::allocator::test::BlockAllocatorTest<BucketBlockAllocator>;
33
34 class BucketBlockAllocatorTest : public BlockAllocatorTest {
35 public:
BucketBlockAllocatorTest()36 BucketBlockAllocatorTest() : BlockAllocatorTest(allocator_) {}
37
38 private:
39 BucketBlockAllocator allocator_;
40 };
41
42 // Unit tests.
43
TEST_F(BucketBlockAllocatorTest,CanAutomaticallyInit)44 TEST_F(BucketBlockAllocatorTest, CanAutomaticallyInit) {
45 BucketBlockAllocator allocator(GetBytes());
46 CanAutomaticallyInit(allocator);
47 }
48
TEST_F(BucketBlockAllocatorTest,CanExplicitlyInit)49 TEST_F(BucketBlockAllocatorTest, CanExplicitlyInit) {
50 BucketBlockAllocator allocator;
51 CanExplicitlyInit(allocator);
52 }
53
TEST_F(BucketBlockAllocatorTest,GetCapacity)54 TEST_F(BucketBlockAllocatorTest, GetCapacity) { GetCapacity(); }
55
TEST_F(BucketBlockAllocatorTest,AllocateLarge)56 TEST_F(BucketBlockAllocatorTest, AllocateLarge) { AllocateLarge(); }
57
TEST_F(BucketBlockAllocatorTest,AllocateSmall)58 TEST_F(BucketBlockAllocatorTest, AllocateSmall) { AllocateSmall(); }
59
TEST_F(BucketBlockAllocatorTest,AllocateLargeAlignment)60 TEST_F(BucketBlockAllocatorTest, AllocateLargeAlignment) {
61 AllocateLargeAlignment();
62 }
63
TEST_F(BucketBlockAllocatorTest,AllocateAlignmentFailure)64 TEST_F(BucketBlockAllocatorTest, AllocateAlignmentFailure) {
65 AllocateAlignmentFailure();
66 }
67
TEST_F(BucketBlockAllocatorTest,AllocatesFromCompatibleBucket)68 TEST_F(BucketBlockAllocatorTest, AllocatesFromCompatibleBucket) {
69 // Bucket sizes are: [ 64, 128, 256 ]
70 // Start with everything allocated in order to recycle blocks into buckets.
71 auto& allocator = GetAllocator({
72 {kSmallerOuterSize, 0},
73 {63 + BlockType::kBlockOverhead, 1},
74 {kSmallerOuterSize, 2},
75 {128 + BlockType::kBlockOverhead, 3},
76 {kSmallerOuterSize, 4},
77 {255 + BlockType::kBlockOverhead, 5},
78 {kSmallerOuterSize, 6},
79 {257 + BlockType::kBlockOverhead, 7},
80 {Preallocation::kSizeRemaining, 8},
81 });
82
83 // Deallocate to fill buckets.
84 void* bucket0_ptr = Fetch(1);
85 Store(1, nullptr);
86 allocator.Deallocate(bucket0_ptr);
87
88 void* bucket1_ptr = Fetch(3);
89 Store(3, nullptr);
90 allocator.Deallocate(bucket1_ptr);
91
92 void* bucket2_ptr = Fetch(5);
93 Store(5, nullptr);
94 allocator.Deallocate(bucket2_ptr);
95
96 // Bucket 3 is the implicit, unbounded bucket.
97 void* bucket3_ptr = Fetch(7);
98 Store(7, nullptr);
99 allocator.Deallocate(bucket3_ptr);
100
101 // Allocate in a different order. The correct bucket should be picked for each
102 // allocation
103
104 // The allocation from bucket 2 splits a trailing block off the chunk.
105 Store(5, allocator.Allocate(Layout(129, 1)));
106 auto* block2 = BlockType::FromUsableSpace(bucket2_ptr);
107 EXPECT_FALSE(block2->Used());
108 EXPECT_EQ(Fetch(5), block2->Next()->UsableSpace());
109
110 // this allocation exactly matches the chunk size of bucket 1.
111 Store(3, allocator.Allocate(Layout(128, 1)));
112 EXPECT_EQ(Fetch(3), bucket1_ptr);
113
114 // 129 should start with bucket 2, then use bucket 3 since 2 is empty.
115 // The allocation from bucket 3 splits a trailing block off the chunk.
116 auto* block3 = BlockType::FromUsableSpace(bucket3_ptr);
117 Store(7, allocator.Allocate(Layout(129, 1)));
118 EXPECT_FALSE(block3->Used());
119 EXPECT_EQ(Fetch(7), block3->Next()->UsableSpace());
120
121 // The allocation from bucket 0 splits a trailing block off the chunk.
122 auto* block0 = BlockType::FromUsableSpace(bucket0_ptr);
123 Store(1, allocator.Allocate(Layout(32, 1)));
124 EXPECT_FALSE(block0->Used());
125 EXPECT_EQ(Fetch(1), block0->Next()->UsableSpace());
126 }
127
TEST_F(BucketBlockAllocatorTest,DeallocateNull)128 TEST_F(BucketBlockAllocatorTest, DeallocateNull) { DeallocateNull(); }
129
TEST_F(BucketBlockAllocatorTest,DeallocateShuffled)130 TEST_F(BucketBlockAllocatorTest, DeallocateShuffled) { DeallocateShuffled(); }
131
TEST_F(BucketBlockAllocatorTest,IterateOverBlocks)132 TEST_F(BucketBlockAllocatorTest, IterateOverBlocks) { IterateOverBlocks(); }
133
TEST_F(BucketBlockAllocatorTest,ResizeNull)134 TEST_F(BucketBlockAllocatorTest, ResizeNull) { ResizeNull(); }
135
TEST_F(BucketBlockAllocatorTest,ResizeLargeSame)136 TEST_F(BucketBlockAllocatorTest, ResizeLargeSame) { ResizeLargeSame(); }
137
TEST_F(BucketBlockAllocatorTest,ResizeLargeSmaller)138 TEST_F(BucketBlockAllocatorTest, ResizeLargeSmaller) { ResizeLargeSmaller(); }
139
TEST_F(BucketBlockAllocatorTest,ResizeLargeLarger)140 TEST_F(BucketBlockAllocatorTest, ResizeLargeLarger) { ResizeLargeLarger(); }
141
TEST_F(BucketBlockAllocatorTest,ResizeLargeLargerFailure)142 TEST_F(BucketBlockAllocatorTest, ResizeLargeLargerFailure) {
143 ResizeLargeLargerFailure();
144 }
145
TEST_F(BucketBlockAllocatorTest,ResizeSmallSame)146 TEST_F(BucketBlockAllocatorTest, ResizeSmallSame) { ResizeSmallSame(); }
147
TEST_F(BucketBlockAllocatorTest,ResizeSmallSmaller)148 TEST_F(BucketBlockAllocatorTest, ResizeSmallSmaller) { ResizeSmallSmaller(); }
149
TEST_F(BucketBlockAllocatorTest,ResizeSmallLarger)150 TEST_F(BucketBlockAllocatorTest, ResizeSmallLarger) { ResizeSmallLarger(); }
151
TEST_F(BucketBlockAllocatorTest,ResizeSmallLargerFailure)152 TEST_F(BucketBlockAllocatorTest, ResizeSmallLargerFailure) {
153 ResizeSmallLargerFailure();
154 }
155
TEST_F(BucketBlockAllocatorTest,CanMeasureFragmentation)156 TEST_F(BucketBlockAllocatorTest, CanMeasureFragmentation) {
157 CanMeasureFragmentation();
158 }
159
160 } // namespace
161