1 // Copyright 2020 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/block.h"
16
17 #include <cstring>
18 #include <span>
19
20 #include "gtest/gtest.h"
21
22 using std::byte;
23
24 namespace pw::allocator {
25
TEST(Block,CanCreateSingleBlock)26 TEST(Block, CanCreateSingleBlock) {
27 constexpr size_t kN = 200;
28 alignas(Block*) byte bytes[kN];
29
30 Block* block = nullptr;
31 auto status = Block::Init(std::span(bytes, kN), &block);
32
33 ASSERT_EQ(status, OkStatus());
34 EXPECT_EQ(block->OuterSize(), kN);
35 EXPECT_EQ(block->InnerSize(),
36 kN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
37 EXPECT_EQ(block->Prev(), nullptr);
38 EXPECT_EQ(block->Next(), (Block*)((uintptr_t)block + kN));
39 EXPECT_EQ(block->Used(), false);
40 EXPECT_EQ(block->Last(), true);
41 }
42
TEST(Block,CannotCreateUnalignedSingleBlock)43 TEST(Block, CannotCreateUnalignedSingleBlock) {
44 constexpr size_t kN = 1024;
45
46 // Force alignment, so we can un-force it below
47 alignas(Block*) byte bytes[kN];
48 byte* byte_ptr = bytes;
49
50 Block* block = nullptr;
51 auto status = Block::Init(std::span(byte_ptr + 1, kN - 1), &block);
52
53 EXPECT_EQ(status, Status::InvalidArgument());
54 }
55
TEST(Block,CannotCreateTooSmallBlock)56 TEST(Block, CannotCreateTooSmallBlock) {
57 constexpr size_t kN = 2;
58 alignas(Block*) byte bytes[kN];
59 Block* block = nullptr;
60 auto status = Block::Init(std::span(bytes, kN), &block);
61
62 EXPECT_EQ(status, Status::InvalidArgument());
63 }
64
TEST(Block,CanSplitBlock)65 TEST(Block, CanSplitBlock) {
66 constexpr size_t kN = 1024;
67 constexpr size_t kSplitN = 512;
68 alignas(Block*) byte bytes[kN];
69
70 Block* block = nullptr;
71 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
72
73 Block* next_block = nullptr;
74 auto status = block->Split(kSplitN, &next_block);
75
76 ASSERT_EQ(status, OkStatus());
77 EXPECT_EQ(block->InnerSize(), kSplitN);
78 EXPECT_EQ(block->OuterSize(),
79 kSplitN + sizeof(Block) + 2 * PW_ALLOCATOR_POISON_OFFSET);
80 EXPECT_EQ(block->Last(), false);
81
82 EXPECT_EQ(next_block->OuterSize(),
83 kN - kSplitN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
84 EXPECT_EQ(next_block->Used(), false);
85 EXPECT_EQ(next_block->Last(), true);
86
87 EXPECT_EQ(block->Next(), next_block);
88 EXPECT_EQ(next_block->Prev(), block);
89 }
90
TEST(Block,CanSplitBlockUnaligned)91 TEST(Block, CanSplitBlockUnaligned) {
92 constexpr size_t kN = 1024;
93 constexpr size_t kSplitN = 513;
94
95 alignas(Block*) byte bytes[kN];
96
97 // We should split at sizeof(Block) + kSplitN bytes. Then
98 // we need to round that up to an alignof(Block*) boundary.
99 uintptr_t split_addr = ((uintptr_t)&bytes) + kSplitN;
100 split_addr += alignof(Block*) - (split_addr % alignof(Block*));
101 uintptr_t split_len = split_addr - (uintptr_t)&bytes;
102
103 Block* block = nullptr;
104 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
105
106 Block* next_block = nullptr;
107 auto status = block->Split(kSplitN, &next_block);
108
109 ASSERT_EQ(status, OkStatus());
110 EXPECT_EQ(block->InnerSize(), split_len);
111 EXPECT_EQ(block->OuterSize(),
112 split_len + sizeof(Block) + 2 * PW_ALLOCATOR_POISON_OFFSET);
113 EXPECT_EQ(next_block->OuterSize(),
114 kN - split_len - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
115 EXPECT_EQ(next_block->Used(), false);
116 EXPECT_EQ(block->Next(), next_block);
117 EXPECT_EQ(next_block->Prev(), block);
118 }
119
TEST(Block,CanSplitMidBlock)120 TEST(Block, CanSplitMidBlock) {
121 // Split once, then split the original block again to ensure that the
122 // pointers get rewired properly.
123 // I.e.
124 // [[ BLOCK 1 ]]
125 // block1->Split()
126 // [[ BLOCK1 ]][[ BLOCK2 ]]
127 // block1->Split()
128 // [[ BLOCK1 ]][[ BLOCK3 ]][[ BLOCK2 ]]
129
130 constexpr size_t kN = 1024;
131 constexpr size_t kSplit1 = 512;
132 constexpr size_t kSplit2 = 256;
133 alignas(Block*) byte bytes[kN];
134
135 Block* block = nullptr;
136 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
137
138 Block* block2 = nullptr;
139 block->Split(kSplit1, &block2)
140 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
141
142 Block* block3 = nullptr;
143 block->Split(kSplit2, &block3)
144 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
145
146 EXPECT_EQ(block->Next(), block3);
147 EXPECT_EQ(block3->Next(), block2);
148 EXPECT_EQ(block2->Prev(), block3);
149 EXPECT_EQ(block3->Prev(), block);
150 }
151
TEST(Block,CannotSplitBlockWithoutHeaderSpace)152 TEST(Block, CannotSplitBlockWithoutHeaderSpace) {
153 constexpr size_t kN = 1024;
154 constexpr size_t kSplitN =
155 kN - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET - 1;
156 alignas(Block*) byte bytes[kN];
157
158 Block* block = nullptr;
159 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
160
161 Block* next_block = nullptr;
162 auto status = block->Split(kSplitN, &next_block);
163
164 EXPECT_EQ(status, Status::ResourceExhausted());
165 EXPECT_EQ(next_block, nullptr);
166 }
167
TEST(Block,MustProvideNextBlockPointer)168 TEST(Block, MustProvideNextBlockPointer) {
169 constexpr size_t kN = 1024;
170 constexpr size_t kSplitN = kN - sizeof(Block) - 1;
171 alignas(Block*) byte bytes[kN];
172
173 Block* block = nullptr;
174 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
175
176 auto status = block->Split(kSplitN, nullptr);
177 EXPECT_EQ(status, Status::InvalidArgument());
178 }
179
TEST(Block,CannotMakeBlockLargerInSplit)180 TEST(Block, CannotMakeBlockLargerInSplit) {
181 // Ensure that we can't ask for more space than the block actually has...
182 constexpr size_t kN = 1024;
183 alignas(Block*) byte bytes[kN];
184
185 Block* block = nullptr;
186 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
187
188 Block* next_block = nullptr;
189 auto status = block->Split(block->InnerSize() + 1, &next_block);
190
191 EXPECT_EQ(status, Status::OutOfRange());
192 }
193
TEST(Block,CannotMakeSecondBlockLargerInSplit)194 TEST(Block, CannotMakeSecondBlockLargerInSplit) {
195 // Ensure that the second block in split is at least of the size of header.
196 constexpr size_t kN = 1024;
197 alignas(Block*) byte bytes[kN];
198
199 Block* block = nullptr;
200 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
201
202 Block* next_block = nullptr;
203 auto status = block->Split(
204 block->InnerSize() - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET + 1,
205 &next_block);
206
207 ASSERT_EQ(status, Status::ResourceExhausted());
208 EXPECT_EQ(next_block, nullptr);
209 }
210
TEST(Block,CanMakeZeroSizeFirstBlock)211 TEST(Block, CanMakeZeroSizeFirstBlock) {
212 // This block does support splitting with zero payload size.
213 constexpr size_t kN = 1024;
214 alignas(Block*) byte bytes[kN];
215
216 Block* block = nullptr;
217 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
218
219 Block* next_block = nullptr;
220 auto status = block->Split(0, &next_block);
221
222 ASSERT_EQ(status, OkStatus());
223 EXPECT_EQ(block->InnerSize(), static_cast<size_t>(0));
224 }
225
TEST(Block,CanMakeZeroSizeSecondBlock)226 TEST(Block, CanMakeZeroSizeSecondBlock) {
227 // Likewise, the split block can be zero-width.
228 constexpr size_t kN = 1024;
229 alignas(Block*) byte bytes[kN];
230
231 Block* block = nullptr;
232 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
233
234 Block* next_block = nullptr;
235 auto status = block->Split(
236 block->InnerSize() - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET,
237 &next_block);
238
239 ASSERT_EQ(status, OkStatus());
240 EXPECT_EQ(next_block->InnerSize(), static_cast<size_t>(0));
241 }
242
TEST(Block,CanMarkBlockUsed)243 TEST(Block, CanMarkBlockUsed) {
244 constexpr size_t kN = 1024;
245 alignas(Block*) byte bytes[kN];
246
247 Block* block = nullptr;
248 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
249
250 block->MarkUsed();
251 EXPECT_EQ(block->Used(), true);
252
253 // Mark used packs that data into the next pointer. Check that it's still
254 // valid
255 EXPECT_EQ(block->Next(), (Block*)((uintptr_t)block + kN));
256
257 block->MarkFree();
258 EXPECT_EQ(block->Used(), false);
259 }
260
TEST(Block,CannotSplitUsedBlock)261 TEST(Block, CannotSplitUsedBlock) {
262 constexpr size_t kN = 1024;
263 alignas(Block*) byte bytes[kN];
264
265 Block* block = nullptr;
266 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
267
268 block->MarkUsed();
269
270 Block* next_block = nullptr;
271 auto status = block->Split(512, &next_block);
272 EXPECT_EQ(status, Status::FailedPrecondition());
273 }
274
TEST(Block,CanMergeWithNextBlock)275 TEST(Block, CanMergeWithNextBlock) {
276 // Do the three way merge from "CanSplitMidBlock", and let's
277 // merge block 3 and 2
278 constexpr size_t kN = 1024;
279 constexpr size_t kSplit1 = 512;
280 constexpr size_t kSplit2 = 256;
281 alignas(Block*) byte bytes[kN];
282
283 Block* block = nullptr;
284 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
285
286 Block* block2 = nullptr;
287 block->Split(kSplit1, &block2)
288 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
289
290 Block* block3 = nullptr;
291 block->Split(kSplit2, &block3)
292 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
293
294 EXPECT_EQ(block3->MergeNext(), OkStatus());
295
296 EXPECT_EQ(block->Next(), block3);
297 EXPECT_EQ(block3->Prev(), block);
298 EXPECT_EQ(block->InnerSize(), kSplit2);
299
300 // The resulting "right hand" block should have an outer size of 1024 - 256 -
301 // sizeof(Block) - 2*PW_ALLOCATOR_POISON_OFFSET, which accounts for the first
302 // block.
303 EXPECT_EQ(block3->OuterSize(),
304 kN - kSplit2 - sizeof(Block) - 2 * PW_ALLOCATOR_POISON_OFFSET);
305 }
306
TEST(Block,CannotMergeWithFirstOrLastBlock)307 TEST(Block, CannotMergeWithFirstOrLastBlock) {
308 constexpr size_t kN = 1024;
309 alignas(Block*) byte bytes[kN];
310
311 // Do a split, just to check that the checks on Next/Prev are
312 // different...
313 Block* block = nullptr;
314 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
315
316 Block* next_block = nullptr;
317 block->Split(512, &next_block)
318 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
319
320 EXPECT_EQ(next_block->MergeNext(), Status::OutOfRange());
321 EXPECT_EQ(block->MergePrev(), Status::OutOfRange());
322 }
323
TEST(Block,CannotMergeUsedBlock)324 TEST(Block, CannotMergeUsedBlock) {
325 constexpr size_t kN = 1024;
326 alignas(Block*) byte bytes[kN];
327
328 // Do a split, just to check that the checks on Next/Prev are
329 // different...
330 Block* block = nullptr;
331 EXPECT_EQ(Block::Init(std::span(bytes, kN), &block), OkStatus());
332
333 Block* next_block = nullptr;
334 block->Split(512, &next_block)
335 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
336
337 block->MarkUsed();
338 EXPECT_EQ(block->MergeNext(), Status::FailedPrecondition());
339 EXPECT_EQ(next_block->MergePrev(), Status::FailedPrecondition());
340 }
341
TEST(Block,CanCheckValidBlock)342 TEST(Block, CanCheckValidBlock) {
343 constexpr size_t kN = 1024;
344 alignas(Block*) byte bytes[kN];
345
346 Block* first_block = nullptr;
347 EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus());
348
349 Block* second_block = nullptr;
350 first_block->Split(512, &second_block)
351 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
352
353 Block* third_block = nullptr;
354 second_block->Split(256, &third_block)
355 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
356
357 EXPECT_EQ(first_block->IsValid(), true);
358 EXPECT_EQ(second_block->IsValid(), true);
359 EXPECT_EQ(third_block->IsValid(), true);
360 }
361
TEST(Block,CanCheckInalidBlock)362 TEST(Block, CanCheckInalidBlock) {
363 constexpr size_t kN = 1024;
364 alignas(Block*) byte bytes[kN];
365
366 Block* first_block = nullptr;
367 EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus());
368
369 Block* second_block = nullptr;
370 first_block->Split(512, &second_block)
371 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
372
373 Block* third_block = nullptr;
374 second_block->Split(256, &third_block)
375 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
376
377 Block* fourth_block = nullptr;
378 third_block->Split(128, &fourth_block)
379 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
380
381 std::byte* next_ptr = reinterpret_cast<std::byte*>(first_block);
382 memcpy(next_ptr, second_block, sizeof(void*));
383 EXPECT_EQ(first_block->IsValid(), false);
384 EXPECT_EQ(second_block->IsValid(), false);
385 EXPECT_EQ(third_block->IsValid(), true);
386 EXPECT_EQ(fourth_block->IsValid(), true);
387
388 #if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
389 std::byte fault_poison[PW_ALLOCATOR_POISON_OFFSET] = {std::byte(0)};
390 std::byte* front_poison =
391 reinterpret_cast<std::byte*>(third_block) + sizeof(*third_block);
392 memcpy(front_poison, fault_poison, PW_ALLOCATOR_POISON_OFFSET);
393 EXPECT_EQ(third_block->IsValid(), false);
394
395 std::byte* end_poison =
396 reinterpret_cast<std::byte*>(fourth_block) + sizeof(*fourth_block);
397 memcpy(end_poison, fault_poison, PW_ALLOCATOR_POISON_OFFSET);
398 EXPECT_EQ(fourth_block->IsValid(), false);
399 #endif // PW_ALLOCATOR_POISON_ENABLE
400 }
401
TEST(Block,CanPoisonBlock)402 TEST(Block, CanPoisonBlock) {
403 #if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
404 constexpr size_t kN = 1024;
405 alignas(Block*) byte bytes[kN];
406
407 Block* first_block = nullptr;
408 EXPECT_EQ(Block::Init(std::span(bytes, kN), &first_block), OkStatus());
409
410 Block* second_block = nullptr;
411 first_block->Split(512, &second_block)
412 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
413
414 Block* third_block = nullptr;
415 second_block->Split(256, &third_block)
416 .IgnoreError(); // TODO(pwbug/387): Handle Status properly
417
418 EXPECT_EQ(first_block->IsValid(), true);
419 EXPECT_EQ(second_block->IsValid(), true);
420 EXPECT_EQ(third_block->IsValid(), true);
421 #endif // PW_ALLOCATOR_POISON_ENABLE
422 }
423
424 } // namespace pw::allocator
425