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_multibuf/simple_allocator.h"
16
17 #include "gtest/gtest.h"
18 #include "pw_allocator/null_allocator.h"
19 #include "pw_allocator/testing.h"
20
21 namespace pw::multibuf {
22 namespace {
23
24 using ::pw::allocator::test::AllocatorForTest;
25
26 constexpr size_t kArbitraryBufferSize = 1024;
27 constexpr size_t kArbitraryMetaSize = 1024;
28
29 // For the tests that test alignment...
30 constexpr size_t kAlignment = 8;
31 static_assert(kArbitraryBufferSize % kAlignment == 0);
32
TEST(SimpleAllocator,AllocateWholeDataAreaSizeSucceeds)33 TEST(SimpleAllocator, AllocateWholeDataAreaSizeSucceeds) {
34 std::array<std::byte, kArbitraryBufferSize> data_area;
35 AllocatorForTest<kArbitraryMetaSize> meta_alloc;
36 SimpleAllocator simple_allocator(data_area, meta_alloc);
37 std::optional<MultiBuf> buf = simple_allocator.Allocate(kArbitraryBufferSize);
38 ASSERT_TRUE(buf.has_value());
39 EXPECT_EQ(buf->size(), kArbitraryBufferSize);
40 }
41
TEST(SimpleAllocator,AllocateContiguousWholeDataAreaSizeSucceeds)42 TEST(SimpleAllocator, AllocateContiguousWholeDataAreaSizeSucceeds) {
43 std::array<std::byte, kArbitraryBufferSize> data_area;
44 AllocatorForTest<kArbitraryMetaSize> meta_alloc;
45 SimpleAllocator simple_allocator(data_area, meta_alloc);
46 std::optional<MultiBuf> buf =
47 simple_allocator.AllocateContiguous(kArbitraryBufferSize);
48 ASSERT_TRUE(buf.has_value());
49 EXPECT_EQ(buf->Chunks().size(), 1U);
50 EXPECT_EQ(buf->size(), kArbitraryBufferSize);
51 }
52
TEST(SimpleAllocator,AllocateContiguousHalfDataAreaSizeTwiceSucceeds)53 TEST(SimpleAllocator, AllocateContiguousHalfDataAreaSizeTwiceSucceeds) {
54 std::array<std::byte, kArbitraryBufferSize> data_area;
55 AllocatorForTest<kArbitraryMetaSize> meta_alloc;
56 SimpleAllocator simple_allocator(data_area, meta_alloc);
57 std::optional<MultiBuf> buf =
58 simple_allocator.AllocateContiguous(kArbitraryBufferSize / 2);
59 ASSERT_TRUE(buf.has_value());
60 EXPECT_EQ(buf->Chunks().size(), 1U);
61 EXPECT_EQ(buf->size(), kArbitraryBufferSize / 2);
62
63 std::optional<MultiBuf> buf2 =
64 simple_allocator.AllocateContiguous(kArbitraryBufferSize / 2);
65 ASSERT_TRUE(buf2.has_value());
66 EXPECT_EQ(buf2->Chunks().size(), 1U);
67 EXPECT_EQ(buf2->size(), kArbitraryBufferSize / 2);
68 }
69
TEST(SimpleAllocator,AllocateTooLargeReturnsNullopt)70 TEST(SimpleAllocator, AllocateTooLargeReturnsNullopt) {
71 std::array<std::byte, kArbitraryBufferSize> data_area;
72 AllocatorForTest<kArbitraryMetaSize> meta_alloc;
73 SimpleAllocator simple_allocator(data_area, meta_alloc);
74 std::optional<MultiBuf> buf =
75 simple_allocator.Allocate(kArbitraryBufferSize + 1);
76 EXPECT_FALSE(buf.has_value());
77 std::optional<MultiBuf> contiguous_buf =
78 simple_allocator.Allocate(kArbitraryBufferSize + 1);
79 EXPECT_FALSE(contiguous_buf.has_value());
80 }
81
TEST(SimpleAllocator,AllocateZeroWithNoMetadataOrDataReturnsEmptyMultiBuf)82 TEST(SimpleAllocator, AllocateZeroWithNoMetadataOrDataReturnsEmptyMultiBuf) {
83 std::array<std::byte, 0> data_area;
84 pw::allocator::NullAllocator meta_alloc;
85 SimpleAllocator simple_allocator(data_area, meta_alloc);
86 std::optional<MultiBuf> buf = simple_allocator.Allocate(0);
87 ASSERT_TRUE(buf.has_value());
88 EXPECT_EQ(buf->size(), 0U);
89 }
90
TEST(SimpleAllocator,AllocateWithNoMetadataRoomReturnsNullopt)91 TEST(SimpleAllocator, AllocateWithNoMetadataRoomReturnsNullopt) {
92 std::array<std::byte, kArbitraryBufferSize> data_area;
93 pw::allocator::NullAllocator meta_alloc;
94 SimpleAllocator simple_allocator(data_area, meta_alloc);
95 std::optional<MultiBuf> buf = simple_allocator.Allocate(1);
96 EXPECT_FALSE(buf.has_value());
97 }
98
TEST(SimpleAllocator,SecondLargeAllocationFailsUntilFirstAllocationReleased)99 TEST(SimpleAllocator, SecondLargeAllocationFailsUntilFirstAllocationReleased) {
100 std::array<std::byte, kArbitraryBufferSize> data_area;
101 AllocatorForTest<kArbitraryMetaSize> meta_alloc;
102 SimpleAllocator simple_allocator(data_area, meta_alloc);
103 const size_t alloc_size = kArbitraryBufferSize / 2 + 1;
104 std::optional<MultiBuf> buf = simple_allocator.Allocate(alloc_size);
105 ASSERT_TRUE(buf.has_value());
106 EXPECT_EQ(buf->size(), alloc_size);
107 EXPECT_FALSE(simple_allocator.Allocate(alloc_size).has_value());
108 // Release the first buffer
109 buf = std::nullopt;
110 EXPECT_TRUE(simple_allocator.Allocate(alloc_size).has_value());
111 }
112
TEST(SimpleAllocator,AllocateSkipsMiddleAllocations)113 TEST(SimpleAllocator, AllocateSkipsMiddleAllocations) {
114 std::array<std::byte, kArbitraryBufferSize> data_area;
115 AllocatorForTest<kArbitraryMetaSize> meta_alloc;
116 SimpleAllocator simple_allocator(data_area, meta_alloc);
117 const size_t alloc_size = kArbitraryBufferSize / 3;
118 std::optional<MultiBuf> buf1 = simple_allocator.Allocate(alloc_size);
119 std::optional<MultiBuf> buf2 = simple_allocator.Allocate(alloc_size);
120 std::optional<MultiBuf> buf3 = simple_allocator.Allocate(alloc_size);
121 EXPECT_TRUE(buf1.has_value());
122 EXPECT_TRUE(buf2.has_value());
123 EXPECT_TRUE(buf3.has_value());
124 buf1 = std::nullopt;
125 buf3 = std::nullopt;
126 // Now `buf2` holds the middle third of data_area
127 std::optional<MultiBuf> split = simple_allocator.Allocate(alloc_size * 2);
128 ASSERT_TRUE(split.has_value());
129 EXPECT_EQ(split->size(), alloc_size * 2);
130 EXPECT_EQ(split->Chunks().size(), 2U);
131 }
132
TEST(SimpleAllocator,FailedAllocationDoesNotHoldOntoChunks)133 TEST(SimpleAllocator, FailedAllocationDoesNotHoldOntoChunks) {
134 std::array<std::byte, kArbitraryBufferSize> data_area;
135 AllocatorForTest<kArbitraryMetaSize> meta_alloc;
136 SimpleAllocator simple_allocator(data_area, meta_alloc);
137 const size_t alloc_size = kArbitraryBufferSize / 2;
138 std::optional<MultiBuf> buf1 = simple_allocator.Allocate(alloc_size);
139 std::optional<MultiBuf> buf2 = simple_allocator.Allocate(alloc_size);
140 EXPECT_TRUE(buf1.has_value());
141 EXPECT_TRUE(buf2.has_value());
142 buf1 = std::nullopt;
143 // When this allocation is attempted, it will initially create a chunk for
144 // the first empty region prior to failing.
145 EXPECT_FALSE(simple_allocator.Allocate(kArbitraryBufferSize).has_value());
146 buf2 = std::nullopt;
147 // Ensure that all chunk holds are released by attempting an allocation.
148 EXPECT_TRUE(simple_allocator.Allocate(kArbitraryBufferSize).has_value());
149 }
150
TEST(SimpleAllocator,AllocatorReturnsAlignedChunks)151 TEST(SimpleAllocator, AllocatorReturnsAlignedChunks) {
152 alignas(kAlignment) std::array<std::byte, kArbitraryBufferSize> data_area;
153 AllocatorForTest<kArbitraryMetaSize> meta_alloc;
154 SimpleAllocator simple_allocator(data_area, meta_alloc, kAlignment);
155 std::optional<MultiBuf> buf1 = simple_allocator.Allocate(5);
156
157 {
158 EXPECT_TRUE(buf1);
159 EXPECT_EQ(buf1->Chunks().size(), 1u);
160 const auto first_chunk = buf1->Chunks().begin();
161 EXPECT_EQ(first_chunk->size(), 5u);
162 EXPECT_EQ(reinterpret_cast<uintptr_t>(first_chunk->data()) % kAlignment,
163 0u);
164 }
165
166 std::optional<MultiBuf> buf2 = simple_allocator.Allocate(3);
167
168 {
169 EXPECT_TRUE(buf2);
170 EXPECT_EQ(buf2->Chunks().size(), 1u);
171 const auto first_chunk = buf2->Chunks().begin();
172 EXPECT_EQ(first_chunk->size(), 3u);
173 EXPECT_EQ(reinterpret_cast<uintptr_t>(first_chunk->data()) % kAlignment,
174 0u);
175 }
176 }
177
TEST(SimpleAllocator,MultipleChunksAreAllAligned)178 TEST(SimpleAllocator, MultipleChunksAreAllAligned) {
179 alignas(kAlignment) std::array<std::byte, kArbitraryBufferSize> data_area;
180 // Use a large metadata arena so that we're not limited by its size.
181 AllocatorForTest<1024 * 1024> meta_alloc;
182 SimpleAllocator simple_allocator(data_area, meta_alloc, kAlignment);
183 std::vector<MultiBuf> bufs_to_keep, bufs_to_free;
184
185 // Keep allocating buffers until we fail, alternating betweens ones we want to
186 // keep and ones we will free.
187 for (;;) {
188 std::optional<MultiBuf> buf = simple_allocator.Allocate(5);
189 if (!buf) {
190 break;
191 }
192 bufs_to_keep.push_back(*std::move(buf));
193 buf = simple_allocator.Allocate(5);
194 if (!buf) {
195 break;
196 }
197 bufs_to_free.push_back(*std::move(buf));
198 }
199
200 const size_t free_bufs = bufs_to_free.size();
201 EXPECT_GT(free_bufs, 0u);
202
203 // Free bufs_to_free which should leave us with lots of fragmentation.
204 bufs_to_free.clear();
205
206 // We should be able to allocate `free_bufs * kAlignment` because every buffer
207 // we freed should have been rounded up to the alignment.
208 std::optional<MultiBuf> buf =
209 simple_allocator.Allocate(free_bufs * kAlignment);
210 EXPECT_TRUE(buf);
211
212 // Check that all chunks of the returned buffer are aligned.
213 size_t total_size = 0;
214 for (const Chunk& chunk : buf->Chunks()) {
215 EXPECT_EQ(reinterpret_cast<uintptr_t>(chunk.data()) % kAlignment, 0u);
216 total_size += chunk.size();
217 }
218
219 EXPECT_EQ(total_size, free_bufs * kAlignment);
220 }
221
TEST(SimpleAllocator,ContiguousChunksAreAligned)222 TEST(SimpleAllocator, ContiguousChunksAreAligned) {
223 alignas(kAlignment) std::array<std::byte, kArbitraryBufferSize> data_area;
224 AllocatorForTest<kArbitraryMetaSize> meta_alloc;
225 SimpleAllocator simple_allocator(data_area, meta_alloc, kAlignment);
226
227 // First create some fragmentation.
228 std::optional<MultiBuf> buf1 = simple_allocator.Allocate(5);
229 EXPECT_TRUE(buf1);
230 std::optional<MultiBuf> buf2 = simple_allocator.Allocate(5);
231 EXPECT_TRUE(buf1);
232 std::optional<MultiBuf> buf3 = simple_allocator.Allocate(5);
233 EXPECT_TRUE(buf1);
234 std::optional<MultiBuf> buf4 = simple_allocator.Allocate(5);
235 EXPECT_TRUE(buf1);
236 std::optional<MultiBuf> buf5 = simple_allocator.Allocate(5);
237 EXPECT_TRUE(buf1);
238 std::optional<MultiBuf> buf6 = simple_allocator.Allocate(5);
239 EXPECT_TRUE(buf1);
240
241 buf2.reset();
242 buf4.reset();
243 buf5.reset();
244
245 // Now allocate some contiguous buffers.
246 std::optional<MultiBuf> buf7 = simple_allocator.AllocateContiguous(11);
247
248 {
249 EXPECT_TRUE(buf7);
250 EXPECT_EQ(buf7->Chunks().size(), 1u);
251 const auto first_chunk = buf7->Chunks().begin();
252 EXPECT_EQ(first_chunk->size(), 11u);
253 EXPECT_EQ(reinterpret_cast<uintptr_t>(first_chunk->data()) % kAlignment,
254 0u);
255 }
256
257 std::optional<MultiBuf> buf8 = simple_allocator.AllocateContiguous(3);
258
259 {
260 EXPECT_TRUE(buf8);
261 EXPECT_EQ(buf8->Chunks().size(), 1u);
262 const auto first_chunk = buf8->Chunks().begin();
263 EXPECT_EQ(first_chunk->size(), 3u);
264 EXPECT_EQ(reinterpret_cast<uintptr_t>(first_chunk->data()) % kAlignment,
265 0u);
266 }
267 }
268
269 } // namespace
270 } // namespace pw::multibuf
271