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 <array>
18 #include <cstdint>
19 #include <cstring>
20
21 #include "pw_span/span.h"
22 #include "pw_unit_test/framework.h"
23
24 namespace {
25
26 // Test fixtures.
27 using ::pw::allocator::Layout;
28 using LargeOffsetBlock = ::pw::allocator::Block<uint64_t>;
29 using SmallOffsetBlock = ::pw::allocator::Block<uint16_t>;
30 using PoisonedBlock = ::pw::allocator::Block<uint32_t, alignof(uint32_t), true>;
31
32 // Macro to provide type-parameterized tests for the various block types above.
33 //
34 // Ideally, the unit tests below could just use `TYPED_TEST_P` and its
35 // asscoiated macros from GoogleTest, see
36 // https://github.com/google/googletest/blob/main/docs/advanced.md#type-parameterized-tests
37 //
38 // These macros are not supported by the light framework however, so this macro
39 // provides a custom implementation that works just for these types.
40 #define TEST_FOR_EACH_BLOCK_TYPE(TestCase) \
41 template <typename BlockType> \
42 void TestCase(); \
43 TEST(LargeOffsetBlockTest, TestCase) { TestCase<LargeOffsetBlock>(); } \
44 TEST(SmallOffsetBlockTest, TestCase) { TestCase<SmallOffsetBlock>(); } \
45 TEST(PoisonedBlockTest, TestCase) { TestCase<PoisonedBlock>(); } \
46 template <typename BlockType> \
47 void TestCase()
48
49 // Unit tests.
50
TEST_FOR_EACH_BLOCK_TYPE(CanCreateSingleAlignedBlock)51 TEST_FOR_EACH_BLOCK_TYPE(CanCreateSingleAlignedBlock) {
52 constexpr size_t kN = 1024;
53 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
54
55 auto result = BlockType::Init(bytes);
56 ASSERT_EQ(result.status(), pw::OkStatus());
57 BlockType* block = *result;
58
59 EXPECT_EQ(block->OuterSize(), kN);
60 EXPECT_EQ(block->InnerSize(), kN - BlockType::kBlockOverhead);
61 EXPECT_EQ(block->Prev(), nullptr);
62 EXPECT_EQ(block->Next(), nullptr);
63 EXPECT_FALSE(block->Used());
64 EXPECT_TRUE(block->Last());
65 }
66
TEST_FOR_EACH_BLOCK_TYPE(CanCreateUnalignedSingleBlock)67 TEST_FOR_EACH_BLOCK_TYPE(CanCreateUnalignedSingleBlock) {
68 constexpr size_t kN = 1024;
69
70 // Force alignment, so we can un-force it below
71 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
72 pw::ByteSpan aligned(bytes);
73
74 auto result = BlockType::Init(aligned.subspan(1));
75 EXPECT_EQ(result.status(), pw::OkStatus());
76 }
77
TEST_FOR_EACH_BLOCK_TYPE(CannotCreateTooSmallBlock)78 TEST_FOR_EACH_BLOCK_TYPE(CannotCreateTooSmallBlock) {
79 std::array<std::byte, 2> bytes;
80 auto result = BlockType::Init(bytes);
81 EXPECT_FALSE(result.ok());
82 EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
83 }
84
TEST(BlockTest,CannotCreateTooLargeBlock)85 TEST(BlockTest, CannotCreateTooLargeBlock) {
86 using BlockType = ::pw::allocator::Block<uint8_t>;
87 constexpr size_t kN = 1024;
88
89 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
90 pw::Result<BlockType*> result = BlockType::Init(bytes);
91 EXPECT_EQ(result.status(), pw::Status::OutOfRange());
92 }
93
TEST_FOR_EACH_BLOCK_TYPE(CanSplitBlock)94 TEST_FOR_EACH_BLOCK_TYPE(CanSplitBlock) {
95 constexpr size_t kN = 1024;
96 constexpr size_t kSplitN = 512;
97
98 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
99 auto result = BlockType::Init(bytes);
100 ASSERT_EQ(result.status(), pw::OkStatus());
101 auto* block1 = *result;
102
103 result = BlockType::Split(block1, kSplitN);
104 ASSERT_EQ(result.status(), pw::OkStatus());
105
106 auto* block2 = *result;
107
108 EXPECT_EQ(block1->InnerSize(), kSplitN);
109 EXPECT_EQ(block1->OuterSize(), kSplitN + BlockType::kBlockOverhead);
110 EXPECT_FALSE(block1->Last());
111
112 EXPECT_EQ(block2->OuterSize(), kN - kSplitN - BlockType::kBlockOverhead);
113 EXPECT_FALSE(block2->Used());
114 EXPECT_TRUE(block2->Last());
115
116 EXPECT_EQ(block1->Next(), block2);
117 EXPECT_EQ(block2->Prev(), block1);
118 }
119
TEST_FOR_EACH_BLOCK_TYPE(CanSplitBlockUnaligned)120 TEST_FOR_EACH_BLOCK_TYPE(CanSplitBlockUnaligned) {
121 constexpr size_t kN = 1024;
122
123 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
124 auto result = BlockType::Init(bytes);
125 ASSERT_EQ(result.status(), pw::OkStatus());
126 BlockType* block1 = *result;
127
128 // We should split at sizeof(BlockType) + kSplitN bytes. Then
129 // we need to round that up to an alignof(BlockType) boundary.
130 constexpr size_t kSplitN = 513;
131 uintptr_t split_addr = reinterpret_cast<uintptr_t>(block1) + kSplitN;
132 split_addr += alignof(BlockType) - (split_addr % alignof(BlockType));
133 uintptr_t split_len = split_addr - (uintptr_t)&bytes;
134
135 result = BlockType::Split(block1, kSplitN);
136 ASSERT_EQ(result.status(), pw::OkStatus());
137 BlockType* block2 = *result;
138
139 EXPECT_EQ(block1->InnerSize(), split_len);
140 EXPECT_EQ(block1->OuterSize(), split_len + BlockType::kBlockOverhead);
141
142 EXPECT_EQ(block2->OuterSize(), kN - block1->OuterSize());
143 EXPECT_FALSE(block2->Used());
144
145 EXPECT_EQ(block1->Next(), block2);
146 EXPECT_EQ(block2->Prev(), block1);
147 }
148
TEST_FOR_EACH_BLOCK_TYPE(CanSplitMidBlock)149 TEST_FOR_EACH_BLOCK_TYPE(CanSplitMidBlock) {
150 // Split once, then split the original block again to ensure that the
151 // pointers get rewired properly.
152 // I.e.
153 // [[ BLOCK 1 ]]
154 // block1->Split()
155 // [[ BLOCK1 ]][[ BLOCK2 ]]
156 // block1->Split()
157 // [[ BLOCK1 ]][[ BLOCK3 ]][[ BLOCK2 ]]
158
159 constexpr size_t kN = 1024;
160 constexpr size_t kSplit1 = 512;
161 constexpr size_t kSplit2 = 256;
162
163 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
164 auto result = BlockType::Init(bytes);
165 ASSERT_EQ(result.status(), pw::OkStatus());
166 BlockType* block1 = *result;
167
168 result = BlockType::Split(block1, kSplit1);
169 ASSERT_EQ(result.status(), pw::OkStatus());
170 BlockType* block2 = *result;
171
172 result = BlockType::Split(block1, kSplit2);
173 ASSERT_EQ(result.status(), pw::OkStatus());
174 BlockType* block3 = *result;
175
176 EXPECT_EQ(block1->Next(), block3);
177 EXPECT_EQ(block3->Prev(), block1);
178 EXPECT_EQ(block3->Next(), block2);
179 EXPECT_EQ(block2->Prev(), block3);
180 }
181
TEST_FOR_EACH_BLOCK_TYPE(CannotSplitTooSmallBlock)182 TEST_FOR_EACH_BLOCK_TYPE(CannotSplitTooSmallBlock) {
183 constexpr size_t kN = 64;
184 constexpr size_t kSplitN = kN + 1;
185
186 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
187 auto result = BlockType::Init(bytes);
188 ASSERT_EQ(result.status(), pw::OkStatus());
189 BlockType* block = *result;
190
191 result = BlockType::Split(block, kSplitN);
192 EXPECT_EQ(result.status(), pw::Status::OutOfRange());
193 }
194
TEST_FOR_EACH_BLOCK_TYPE(CannotSplitBlockWithoutHeaderSpace)195 TEST_FOR_EACH_BLOCK_TYPE(CannotSplitBlockWithoutHeaderSpace) {
196 constexpr size_t kN = 1024;
197 constexpr size_t kSplitN = kN - BlockType::kBlockOverhead - 1;
198
199 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
200 auto result = BlockType::Init(bytes);
201 ASSERT_EQ(result.status(), pw::OkStatus());
202 BlockType* block = *result;
203
204 result = BlockType::Split(block, kSplitN);
205 EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
206 }
207
TEST_FOR_EACH_BLOCK_TYPE(CannotSplitNull)208 TEST_FOR_EACH_BLOCK_TYPE(CannotSplitNull) {
209 BlockType* block = nullptr;
210 auto result = BlockType::Split(block, 1);
211 EXPECT_EQ(result.status(), pw::Status::InvalidArgument());
212 }
213
TEST_FOR_EACH_BLOCK_TYPE(CannotMakeBlockLargerInSplit)214 TEST_FOR_EACH_BLOCK_TYPE(CannotMakeBlockLargerInSplit) {
215 // Ensure that we can't ask for more space than the block actually has...
216 constexpr size_t kN = 1024;
217
218 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
219 auto result = BlockType::Init(bytes);
220 ASSERT_EQ(result.status(), pw::OkStatus());
221 BlockType* block = *result;
222
223 result = BlockType::Split(block, block->InnerSize() + 1);
224 EXPECT_EQ(result.status(), pw::Status::OutOfRange());
225 }
226
TEST_FOR_EACH_BLOCK_TYPE(CannotMakeSecondBlockLargerInSplit)227 TEST_FOR_EACH_BLOCK_TYPE(CannotMakeSecondBlockLargerInSplit) {
228 // Ensure that the second block in split is at least of the size of header.
229 constexpr size_t kN = 1024;
230
231 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
232 auto result = BlockType::Init(bytes);
233 ASSERT_EQ(result.status(), pw::OkStatus());
234 BlockType* block = *result;
235
236 result = BlockType::Split(block,
237 block->InnerSize() - BlockType::kBlockOverhead + 1);
238 EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
239 }
240
TEST_FOR_EACH_BLOCK_TYPE(CanMakeZeroSizeFirstBlock)241 TEST_FOR_EACH_BLOCK_TYPE(CanMakeZeroSizeFirstBlock) {
242 // This block does support splitting with zero payload size.
243 constexpr size_t kN = 1024;
244
245 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
246 auto result = BlockType::Init(bytes);
247 ASSERT_EQ(result.status(), pw::OkStatus());
248 BlockType* block = *result;
249
250 result = BlockType::Split(block, 0);
251 ASSERT_EQ(result.status(), pw::OkStatus());
252 EXPECT_EQ(block->InnerSize(), static_cast<size_t>(0));
253 }
254
TEST_FOR_EACH_BLOCK_TYPE(CanMakeZeroSizeSecondBlock)255 TEST_FOR_EACH_BLOCK_TYPE(CanMakeZeroSizeSecondBlock) {
256 // Likewise, the split block can be zero-width.
257 constexpr size_t kN = 1024;
258
259 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
260 auto result = BlockType::Init(bytes);
261 ASSERT_EQ(result.status(), pw::OkStatus());
262 BlockType* block1 = *result;
263
264 result =
265 BlockType::Split(block1, block1->InnerSize() - BlockType::kBlockOverhead);
266 ASSERT_EQ(result.status(), pw::OkStatus());
267 BlockType* block2 = *result;
268
269 EXPECT_EQ(block2->InnerSize(), static_cast<size_t>(0));
270 }
271
TEST_FOR_EACH_BLOCK_TYPE(CanMarkBlockUsed)272 TEST_FOR_EACH_BLOCK_TYPE(CanMarkBlockUsed) {
273 constexpr size_t kN = 1024;
274
275 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
276 auto result = BlockType::Init(bytes);
277 ASSERT_EQ(result.status(), pw::OkStatus());
278 BlockType* block = *result;
279
280 block->MarkUsed();
281 EXPECT_TRUE(block->Used());
282
283 // Size should be unaffected.
284 EXPECT_EQ(block->OuterSize(), kN);
285
286 block->MarkFree();
287 EXPECT_FALSE(block->Used());
288 }
289
TEST_FOR_EACH_BLOCK_TYPE(CannotSplitUsedBlock)290 TEST_FOR_EACH_BLOCK_TYPE(CannotSplitUsedBlock) {
291 constexpr size_t kN = 1024;
292 constexpr size_t kSplitN = 512;
293
294 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
295 auto result = BlockType::Init(bytes);
296 ASSERT_EQ(result.status(), pw::OkStatus());
297 BlockType* block = *result;
298
299 block->MarkUsed();
300 result = BlockType::Split(block, kSplitN);
301 EXPECT_EQ(result.status(), pw::Status::FailedPrecondition());
302 }
303
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirstFromAlignedBlock)304 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirstFromAlignedBlock) {
305 constexpr size_t kN = 1024;
306 constexpr size_t kSize = 256;
307 constexpr size_t kAlign = 32;
308
309 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
310 auto result = BlockType::Init(bytes);
311 ASSERT_EQ(result.status(), pw::OkStatus());
312 BlockType* block = *result;
313
314 // Make sure the block's usable space is aligned.
315 auto addr = reinterpret_cast<uintptr_t>(block->UsableSpace());
316 size_t pad_outer_size = pw::AlignUp(addr, kAlign) - addr;
317 if (pad_outer_size != 0) {
318 while (pad_outer_size < BlockType::kBlockOverhead) {
319 pad_outer_size += kAlign;
320 }
321 result =
322 BlockType::Split(block, pad_outer_size - BlockType::kBlockOverhead);
323 EXPECT_EQ(result.status(), pw::OkStatus());
324 block = *result;
325 }
326
327 // Allocate from the front of the block.
328 BlockType* prev = block->Prev();
329 Layout layout(kSize, kAlign);
330 EXPECT_EQ(BlockType::AllocFirst(block, layout), pw::OkStatus());
331 EXPECT_EQ(block->InnerSize(), kSize);
332 addr = reinterpret_cast<uintptr_t>(block->UsableSpace());
333 EXPECT_EQ(addr % kAlign, 0U);
334 EXPECT_TRUE(block->Used());
335
336 // No new padding block was allocated.
337 EXPECT_EQ(prev, block->Prev());
338
339 // Extra was split from the end of the block.
340 EXPECT_FALSE(block->Last());
341 }
342
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirstFromUnalignedBlock)343 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirstFromUnalignedBlock) {
344 constexpr size_t kN = 1024;
345 constexpr size_t kSize = 256;
346 constexpr size_t kAlign = 32;
347
348 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
349 auto result = BlockType::Init(bytes);
350 ASSERT_EQ(result.status(), pw::OkStatus());
351 BlockType* block = *result;
352
353 // Make sure the block's usable space is not aligned.
354 auto addr = reinterpret_cast<uintptr_t>(block->UsableSpace());
355 size_t pad_inner_size = pw::AlignUp(addr, kAlign) - addr + (kAlign / 2);
356 if (pad_inner_size < BlockType::kBlockOverhead) {
357 pad_inner_size += kAlign;
358 }
359 pad_inner_size -= BlockType::kBlockOverhead;
360 result = BlockType::Split(block, pad_inner_size);
361 EXPECT_EQ(result.status(), pw::OkStatus());
362 block = *result;
363
364 BlockType* prev = block->Prev();
365 prev->MarkUsed();
366 size_t prev_inner_size = prev->InnerSize();
367
368 // Allocate from the front of the block.
369 Layout layout(kSize, kAlign);
370 EXPECT_EQ(BlockType::AllocFirst(block, layout), pw::OkStatus());
371 EXPECT_EQ(block->InnerSize(), kSize);
372 addr = reinterpret_cast<uintptr_t>(block->UsableSpace());
373 EXPECT_EQ(addr % kAlign, 0U);
374 EXPECT_TRUE(block->Used());
375
376 if (!block->Prev()->Used()) {
377 // Either a new free block was added...
378 EXPECT_LT(prev, block->Prev());
379 } else {
380 /// ...or less than a minimum block was added to the previous block.
381 EXPECT_NE(prev_inner_size, prev->InnerSize());
382 EXPECT_LT(prev->InnerSize() - prev_inner_size, BlockType::kBlockOverhead);
383 }
384
385 // Extra was split from the end of the block.
386 EXPECT_FALSE(block->Last());
387 }
388
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirstTooSmallBlock)389 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirstTooSmallBlock) {
390 constexpr size_t kN = 1024;
391 constexpr size_t kAlign = 32;
392
393 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
394 auto result = BlockType::Init(bytes);
395 ASSERT_EQ(result.status(), pw::OkStatus());
396 BlockType* block = *result;
397
398 // Make sure the block's usable space is not aligned.
399 auto addr = reinterpret_cast<uintptr_t>(block->UsableSpace());
400 size_t pad_inner_size = pw::AlignUp(addr, kAlign) - addr + (kAlign / 2);
401 if (pad_inner_size < BlockType::kBlockOverhead) {
402 pad_inner_size += kAlign;
403 }
404 pad_inner_size -= BlockType::kBlockOverhead;
405 result = BlockType::Split(block, pad_inner_size);
406 EXPECT_EQ(result.status(), pw::OkStatus());
407 block = *result;
408
409 // Cannot allocate without room to a split a block for alignment.
410 Layout layout(block->InnerSize(), kAlign);
411 EXPECT_EQ(BlockType::AllocFirst(block, layout), pw::Status::OutOfRange());
412 }
413
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirstFromNull)414 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirstFromNull) {
415 BlockType* block = nullptr;
416 Layout layout(1, 1);
417 EXPECT_EQ(BlockType::AllocFirst(block, layout),
418 pw::Status::InvalidArgument());
419 }
420
TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast)421 TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast) {
422 constexpr size_t kN = 1024;
423 constexpr size_t kSize = 256;
424 constexpr size_t kAlign = 32;
425
426 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
427 auto result = BlockType::Init(bytes);
428 ASSERT_EQ(result.status(), pw::OkStatus());
429 BlockType* block = *result;
430
431 // Allocate from the back of the block.
432 Layout layout(kSize, kAlign);
433 EXPECT_EQ(BlockType::AllocLast(block, layout), pw::OkStatus());
434 EXPECT_GE(block->InnerSize(), kSize);
435 auto addr = reinterpret_cast<uintptr_t>(block->UsableSpace());
436 EXPECT_EQ(addr % kAlign, 0U);
437 EXPECT_TRUE(block->Used());
438
439 // Extra was split from the front of the block.
440 EXPECT_FALSE(block->Prev()->Used());
441 EXPECT_TRUE(block->Last());
442 }
443
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastFromTooSmallBlock)444 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastFromTooSmallBlock) {
445 constexpr size_t kN = 1024;
446 constexpr size_t kAlign = 32;
447
448 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
449 auto result = BlockType::Init(bytes);
450 ASSERT_EQ(result.status(), pw::OkStatus());
451 BlockType* block = *result;
452
453 // Make sure the block's usable space is not aligned.
454 auto addr = reinterpret_cast<uintptr_t>(block->UsableSpace());
455 size_t pad_inner_size = pw::AlignUp(addr, kAlign) - addr + (kAlign / 2);
456 if (pad_inner_size < BlockType::kBlockOverhead) {
457 pad_inner_size += kAlign;
458 }
459 pad_inner_size -= BlockType::kBlockOverhead;
460 result = BlockType::Split(block, pad_inner_size);
461 EXPECT_EQ(result.status(), pw::OkStatus());
462 block = *result;
463
464 // Cannot allocate without room to a split a block for alignment.
465 Layout layout(block->InnerSize(), kAlign);
466 EXPECT_EQ(BlockType::AllocLast(block, layout),
467 pw::Status::ResourceExhausted());
468 }
469
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastFromNull)470 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastFromNull) {
471 BlockType* block = nullptr;
472 Layout layout(1, 1);
473 EXPECT_EQ(BlockType::AllocLast(block, layout), pw::Status::InvalidArgument());
474 }
475
TEST_FOR_EACH_BLOCK_TYPE(CanMergeWithNextBlock)476 TEST_FOR_EACH_BLOCK_TYPE(CanMergeWithNextBlock) {
477 // Do the three way merge from "CanSplitMidBlock", and let's
478 // merge block 3 and 2
479 constexpr size_t kN = 1024;
480 constexpr size_t kSplit1 = 512;
481 constexpr size_t kSplit2 = 256;
482
483 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
484 auto result = BlockType::Init(bytes);
485 ASSERT_EQ(result.status(), pw::OkStatus());
486 BlockType* block1 = *result;
487
488 result = BlockType::Split(block1, kSplit1);
489 ASSERT_EQ(result.status(), pw::OkStatus());
490
491 result = BlockType::Split(block1, kSplit2);
492 ASSERT_EQ(result.status(), pw::OkStatus());
493 BlockType* block3 = *result;
494
495 EXPECT_EQ(BlockType::MergeNext(block3), pw::OkStatus());
496
497 EXPECT_EQ(block1->Next(), block3);
498 EXPECT_EQ(block3->Prev(), block1);
499 EXPECT_EQ(block1->InnerSize(), kSplit2);
500 EXPECT_EQ(block3->OuterSize(), kN - block1->OuterSize());
501 }
502
TEST_FOR_EACH_BLOCK_TYPE(CannotMergeWithFirstOrLastBlock)503 TEST_FOR_EACH_BLOCK_TYPE(CannotMergeWithFirstOrLastBlock) {
504 constexpr size_t kN = 1024;
505 constexpr size_t kSplitN = 512;
506
507 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
508 auto result = BlockType::Init(bytes);
509 ASSERT_EQ(result.status(), pw::OkStatus());
510 BlockType* block1 = *result;
511
512 // Do a split, just to check that the checks on Next/Prev are different...
513 result = BlockType::Split(block1, kSplitN);
514 ASSERT_EQ(result.status(), pw::OkStatus());
515 BlockType* block2 = *result;
516
517 EXPECT_EQ(BlockType::MergeNext(block2), pw::Status::OutOfRange());
518 }
519
TEST_FOR_EACH_BLOCK_TYPE(CannotMergeNull)520 TEST_FOR_EACH_BLOCK_TYPE(CannotMergeNull) {
521 BlockType* block = nullptr;
522 EXPECT_EQ(BlockType::MergeNext(block), pw::Status::InvalidArgument());
523 }
524
TEST_FOR_EACH_BLOCK_TYPE(CannotMergeUsedBlock)525 TEST_FOR_EACH_BLOCK_TYPE(CannotMergeUsedBlock) {
526 constexpr size_t kN = 1024;
527 constexpr size_t kSplitN = 512;
528
529 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
530 auto result = BlockType::Init(bytes);
531 ASSERT_EQ(result.status(), pw::OkStatus());
532 BlockType* block = *result;
533
534 // Do a split, just to check that the checks on Next/Prev are different...
535 result = BlockType::Split(block, kSplitN);
536 ASSERT_EQ(result.status(), pw::OkStatus());
537
538 block->MarkUsed();
539 EXPECT_EQ(BlockType::MergeNext(block), pw::Status::FailedPrecondition());
540 }
541
TEST_FOR_EACH_BLOCK_TYPE(CanFreeSingleBlock)542 TEST_FOR_EACH_BLOCK_TYPE(CanFreeSingleBlock) {
543 constexpr size_t kN = 1024;
544 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
545
546 auto result = BlockType::Init(bytes);
547 ASSERT_EQ(result.status(), pw::OkStatus());
548 BlockType* block = *result;
549
550 block->MarkUsed();
551 BlockType::Free(block);
552 EXPECT_FALSE(block->Used());
553 EXPECT_EQ(block->OuterSize(), kN);
554 }
555
TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockWithoutMerging)556 TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockWithoutMerging) {
557 constexpr size_t kN = 1024;
558 constexpr size_t kSplit1 = 512;
559 constexpr size_t kSplit2 = 256;
560
561 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
562 auto result = BlockType::Init(bytes);
563 ASSERT_EQ(result.status(), pw::OkStatus());
564 BlockType* block1 = *result;
565
566 result = BlockType::Split(block1, kSplit1);
567 ASSERT_EQ(result.status(), pw::OkStatus());
568 BlockType* block2 = *result;
569
570 result = BlockType::Split(block2, kSplit2);
571 ASSERT_EQ(result.status(), pw::OkStatus());
572 BlockType* block3 = *result;
573
574 block1->MarkUsed();
575 block2->MarkUsed();
576 block3->MarkUsed();
577
578 BlockType::Free(block2);
579 EXPECT_FALSE(block2->Used());
580 EXPECT_NE(block2->Prev(), nullptr);
581 EXPECT_FALSE(block2->Last());
582 }
583
TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockAndMergeWithPrev)584 TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockAndMergeWithPrev) {
585 constexpr size_t kN = 1024;
586 constexpr size_t kSplit1 = 512;
587 constexpr size_t kSplit2 = 256;
588
589 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
590 auto result = BlockType::Init(bytes);
591 ASSERT_EQ(result.status(), pw::OkStatus());
592 BlockType* block1 = *result;
593
594 result = BlockType::Split(block1, kSplit1);
595 ASSERT_EQ(result.status(), pw::OkStatus());
596 BlockType* block2 = *result;
597
598 result = BlockType::Split(block2, kSplit2);
599 ASSERT_EQ(result.status(), pw::OkStatus());
600 BlockType* block3 = *result;
601
602 block2->MarkUsed();
603 block3->MarkUsed();
604
605 BlockType::Free(block2);
606 EXPECT_FALSE(block2->Used());
607 EXPECT_EQ(block2->Prev(), nullptr);
608 EXPECT_FALSE(block2->Last());
609 }
610
TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockAndMergeWithNext)611 TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockAndMergeWithNext) {
612 constexpr size_t kN = 1024;
613 constexpr size_t kSplit1 = 512;
614 constexpr size_t kSplit2 = 256;
615
616 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
617 auto result = BlockType::Init(bytes);
618 ASSERT_EQ(result.status(), pw::OkStatus());
619 BlockType* block1 = *result;
620
621 result = BlockType::Split(block1, kSplit1);
622 ASSERT_EQ(result.status(), pw::OkStatus());
623 BlockType* block2 = *result;
624
625 result = BlockType::Split(block2, kSplit2);
626 ASSERT_EQ(result.status(), pw::OkStatus());
627
628 block1->MarkUsed();
629 block2->MarkUsed();
630
631 BlockType::Free(block2);
632 EXPECT_FALSE(block2->Used());
633 EXPECT_NE(block2->Prev(), nullptr);
634 EXPECT_TRUE(block2->Last());
635 }
636
TEST_FOR_EACH_BLOCK_TYPE(CanFreeUsedBlockAndMergeWithBoth)637 TEST_FOR_EACH_BLOCK_TYPE(CanFreeUsedBlockAndMergeWithBoth) {
638 constexpr size_t kN = 1024;
639 constexpr size_t kSplit1 = 512;
640 constexpr size_t kSplit2 = 256;
641
642 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
643 auto result = BlockType::Init(bytes);
644 ASSERT_EQ(result.status(), pw::OkStatus());
645 BlockType* block1 = *result;
646
647 result = BlockType::Split(block1, kSplit1);
648 ASSERT_EQ(result.status(), pw::OkStatus());
649 BlockType* block2 = *result;
650
651 result = BlockType::Split(block2, kSplit2);
652 ASSERT_EQ(result.status(), pw::OkStatus());
653
654 block2->MarkUsed();
655
656 BlockType::Free(block2);
657 EXPECT_FALSE(block2->Used());
658 EXPECT_EQ(block2->Prev(), nullptr);
659 EXPECT_TRUE(block2->Last());
660 }
661
TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSameSize)662 TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSameSize) {
663 constexpr size_t kN = 1024;
664
665 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
666 auto result = BlockType::Init(bytes);
667 ASSERT_EQ(result.status(), pw::OkStatus());
668 BlockType* block = *result;
669
670 block->MarkUsed();
671 EXPECT_EQ(BlockType::Resize(block, block->InnerSize()), pw::OkStatus());
672 }
673
TEST_FOR_EACH_BLOCK_TYPE(CannotResizeFreeBlock)674 TEST_FOR_EACH_BLOCK_TYPE(CannotResizeFreeBlock) {
675 constexpr size_t kN = 1024;
676
677 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
678 auto result = BlockType::Init(bytes);
679 ASSERT_EQ(result.status(), pw::OkStatus());
680 BlockType* block = *result;
681
682 EXPECT_EQ(BlockType::Resize(block, block->InnerSize()),
683 pw::Status::FailedPrecondition());
684 }
685
TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSmallerWithNextFree)686 TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSmallerWithNextFree) {
687 constexpr size_t kN = 1024;
688 constexpr size_t kSplit1 = 512;
689
690 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
691 auto result = BlockType::Init(bytes);
692 ASSERT_EQ(result.status(), pw::OkStatus());
693 BlockType* block1 = *result;
694
695 result = BlockType::Split(block1, kSplit1);
696 ASSERT_EQ(result.status(), pw::OkStatus());
697 BlockType* block2 = *result;
698
699 block1->MarkUsed();
700 size_t block2_inner_size = block2->InnerSize();
701
702 // Shrink by less than the minimum needed for a block. The extra should be
703 // added to the subsequent block.
704 size_t delta = BlockType::kBlockOverhead - BlockType::kAlignment;
705 size_t new_inner_size = block1->InnerSize() - delta;
706 EXPECT_EQ(BlockType::Resize(block1, new_inner_size), pw::OkStatus());
707 EXPECT_EQ(block1->InnerSize(), new_inner_size);
708
709 block2 = block1->Next();
710 EXPECT_GE(block2->InnerSize(), block2_inner_size + delta);
711 }
712
TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockLargerWithNextFree)713 TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockLargerWithNextFree) {
714 constexpr size_t kN = 1024;
715 constexpr size_t kSplit1 = 512;
716
717 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
718 auto result = BlockType::Init(bytes);
719 ASSERT_EQ(result.status(), pw::OkStatus());
720 BlockType* block1 = *result;
721
722 result = BlockType::Split(block1, kSplit1);
723 ASSERT_EQ(result.status(), pw::OkStatus());
724 BlockType* block2 = *result;
725
726 block1->MarkUsed();
727 size_t block2_inner_size = block2->InnerSize();
728
729 // Grow by less than the minimum needed for a block. The extra should be
730 // added to the subsequent block.
731 size_t delta = BlockType::kBlockOverhead - BlockType::kAlignment;
732 size_t new_inner_size = block1->InnerSize() + delta;
733 EXPECT_EQ(BlockType::Resize(block1, new_inner_size), pw::OkStatus());
734 EXPECT_EQ(block1->InnerSize(), new_inner_size);
735
736 block2 = block1->Next();
737 EXPECT_GE(block2->InnerSize(), block2_inner_size - delta);
738 }
739
TEST_FOR_EACH_BLOCK_TYPE(CannotResizeBlockMuchLargerWithNextFree)740 TEST_FOR_EACH_BLOCK_TYPE(CannotResizeBlockMuchLargerWithNextFree) {
741 constexpr size_t kN = 1024;
742 constexpr size_t kSplit1 = 512;
743 constexpr size_t kSplit2 = 256;
744
745 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
746 auto result = BlockType::Init(bytes);
747 ASSERT_EQ(result.status(), pw::OkStatus());
748 BlockType* block1 = *result;
749
750 result = BlockType::Split(block1, kSplit1);
751 ASSERT_EQ(result.status(), pw::OkStatus());
752 BlockType* block2 = *result;
753
754 result = BlockType::Split(block2, kSplit2);
755 ASSERT_EQ(result.status(), pw::OkStatus());
756 BlockType* block3 = *result;
757
758 block1->MarkUsed();
759 block3->MarkUsed();
760
761 size_t new_inner_size = block1->InnerSize() + block2->OuterSize() + 1;
762 EXPECT_EQ(BlockType::Resize(block1, new_inner_size),
763 pw::Status::OutOfRange());
764 }
765
TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSmallerWithNextUsed)766 TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSmallerWithNextUsed) {
767 constexpr size_t kN = 1024;
768 constexpr size_t kSplit1 = 512;
769
770 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
771 auto result = BlockType::Init(bytes);
772 ASSERT_EQ(result.status(), pw::OkStatus());
773 BlockType* block1 = *result;
774
775 result = BlockType::Split(block1, kSplit1);
776 ASSERT_EQ(result.status(), pw::OkStatus());
777 BlockType* block2 = *result;
778
779 block1->MarkUsed();
780 block2->MarkUsed();
781
782 // Shrink the block.
783 size_t delta = kSplit1 / 2;
784 size_t new_inner_size = block1->InnerSize() - delta;
785 EXPECT_EQ(BlockType::Resize(block1, new_inner_size), pw::OkStatus());
786 EXPECT_EQ(block1->InnerSize(), new_inner_size);
787
788 block2 = block1->Next();
789 EXPECT_EQ(block2->OuterSize(), delta);
790 }
791
TEST_FOR_EACH_BLOCK_TYPE(CannotResizeBlockLargerWithNextUsed)792 TEST_FOR_EACH_BLOCK_TYPE(CannotResizeBlockLargerWithNextUsed) {
793 constexpr size_t kN = 1024;
794 constexpr size_t kSplit1 = 512;
795
796 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
797 auto result = BlockType::Init(bytes);
798 ASSERT_EQ(result.status(), pw::OkStatus());
799 BlockType* block1 = *result;
800
801 result = BlockType::Split(block1, kSplit1);
802 ASSERT_EQ(result.status(), pw::OkStatus());
803 BlockType* block2 = *result;
804
805 block1->MarkUsed();
806 block2->MarkUsed();
807
808 size_t delta = BlockType::kBlockOverhead / 2;
809 size_t new_inner_size = block1->InnerSize() + delta;
810 EXPECT_EQ(BlockType::Resize(block1, new_inner_size),
811 pw::Status::OutOfRange());
812 }
813
TEST_FOR_EACH_BLOCK_TYPE(CannotResizeFromTooNull)814 TEST_FOR_EACH_BLOCK_TYPE(CannotResizeFromTooNull) {
815 BlockType* block = nullptr;
816 EXPECT_EQ(BlockType::Resize(block, 1), pw::Status::InvalidArgument());
817 }
818
TEST_FOR_EACH_BLOCK_TYPE(CanCheckValidBlock)819 TEST_FOR_EACH_BLOCK_TYPE(CanCheckValidBlock) {
820 constexpr size_t kN = 1024;
821 constexpr size_t kSplit1 = 512;
822 constexpr size_t kSplit2 = 256;
823
824 alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes;
825 auto result = BlockType::Init(bytes);
826 ASSERT_EQ(result.status(), pw::OkStatus());
827 BlockType* block1 = *result;
828
829 result = BlockType::Split(block1, kSplit1);
830 ASSERT_EQ(result.status(), pw::OkStatus());
831 BlockType* block2 = *result;
832
833 result = BlockType::Split(block2, kSplit2);
834 ASSERT_EQ(result.status(), pw::OkStatus());
835 BlockType* block3 = *result;
836
837 EXPECT_TRUE(block1->IsValid());
838 block1->CrashIfInvalid();
839
840 EXPECT_TRUE(block2->IsValid());
841 block2->CrashIfInvalid();
842
843 EXPECT_TRUE(block3->IsValid());
844 block3->CrashIfInvalid();
845 }
846
TEST_FOR_EACH_BLOCK_TYPE(CanCheckInvalidBlock)847 TEST_FOR_EACH_BLOCK_TYPE(CanCheckInvalidBlock) {
848 constexpr size_t kN = 1024;
849 constexpr size_t kSplit1 = 128;
850 constexpr size_t kSplit2 = 384;
851 constexpr size_t kSplit3 = 256;
852
853 std::array<std::byte, kN> bytes{};
854 auto result = BlockType::Init(bytes);
855 ASSERT_EQ(result.status(), pw::OkStatus());
856 BlockType* block1 = *result;
857
858 result = BlockType::Split(block1, kSplit1);
859 ASSERT_EQ(result.status(), pw::OkStatus());
860 BlockType* block2 = *result;
861
862 result = BlockType::Split(block2, kSplit2);
863 ASSERT_EQ(result.status(), pw::OkStatus());
864 BlockType* block3 = *result;
865
866 result = BlockType::Split(block3, kSplit3);
867 ASSERT_EQ(result.status(), pw::OkStatus());
868
869 // Corrupt a Block header.
870 // This must not touch memory outside the original region, or the test may
871 // (correctly) abort when run with address sanitizer.
872 // To remain as agostic to the internals of `Block` as possible, the test
873 // copies a smaller block's header to a larger block.
874 EXPECT_TRUE(block1->IsValid());
875 EXPECT_TRUE(block2->IsValid());
876 EXPECT_TRUE(block3->IsValid());
877 auto* src = reinterpret_cast<std::byte*>(block1);
878 auto* dst = reinterpret_cast<std::byte*>(block2);
879 std::memcpy(dst, src, sizeof(BlockType));
880 EXPECT_FALSE(block1->IsValid());
881 EXPECT_FALSE(block2->IsValid());
882 EXPECT_FALSE(block3->IsValid());
883 }
884
TEST(PoisonedBlockTest,CanCheckPoison)885 TEST(PoisonedBlockTest, CanCheckPoison) {
886 constexpr size_t kN = 1024;
887 // constexpr size_t kSplit1 = 512;
888 std::array<std::byte, kN> bytes{};
889 auto result = PoisonedBlock::Init(bytes);
890 ASSERT_EQ(result.status(), pw::OkStatus());
891 PoisonedBlock* block = *result;
892
893 // Modify a byte in the middle of a free block.
894 // Without poisoning, the modification is undetected.
895 EXPECT_FALSE(block->Used());
896 bytes[kN / 2] = std::byte(0x7f);
897 EXPECT_TRUE(block->IsValid());
898
899 // Modify a byte in the middle of a free block.
900 // With poisoning, the modification is detected.
901 block->Poison();
902 bytes[kN / 2] = std::byte(0x7f);
903 EXPECT_FALSE(block->IsValid());
904 }
905
TEST_FOR_EACH_BLOCK_TYPE(CanGetBlockFromUsableSpace)906 TEST_FOR_EACH_BLOCK_TYPE(CanGetBlockFromUsableSpace) {
907 constexpr size_t kN = 1024;
908
909 std::array<std::byte, kN> bytes{};
910 auto result = BlockType::Init(bytes);
911 ASSERT_EQ(result.status(), pw::OkStatus());
912 BlockType* block1 = *result;
913
914 void* ptr = block1->UsableSpace();
915 BlockType* block2 = BlockType::FromUsableSpace(ptr);
916 EXPECT_EQ(block1, block2);
917 }
918
TEST_FOR_EACH_BLOCK_TYPE(CanGetConstBlockFromUsableSpace)919 TEST_FOR_EACH_BLOCK_TYPE(CanGetConstBlockFromUsableSpace) {
920 constexpr size_t kN = 1024;
921
922 std::array<std::byte, kN> bytes{};
923 auto result = BlockType::Init(bytes);
924 ASSERT_EQ(result.status(), pw::OkStatus());
925 const BlockType* block1 = *result;
926
927 const void* ptr = block1->UsableSpace();
928 const BlockType* block2 = BlockType::FromUsableSpace(ptr);
929 EXPECT_EQ(block1, block2);
930 }
931
TEST_FOR_EACH_BLOCK_TYPE(CanGetAlignmentFromUsedBlock)932 TEST_FOR_EACH_BLOCK_TYPE(CanGetAlignmentFromUsedBlock) {
933 constexpr size_t kN = 1024;
934 constexpr size_t kSplit1 = 128;
935 constexpr size_t kSplit2 = 512;
936 constexpr size_t kAlign = 32;
937
938 std::array<std::byte, kN> bytes{};
939 auto result = BlockType::Init(bytes);
940 ASSERT_EQ(result.status(), pw::OkStatus());
941 BlockType* block1 = *result;
942
943 Layout layout1(kSplit1, kAlign);
944 EXPECT_EQ(BlockType::AllocFirst(block1, layout1), pw::OkStatus());
945
946 Layout layout2(kSplit2, kAlign * 2);
947 BlockType* block2 = block1->Next();
948 EXPECT_EQ(BlockType::AllocFirst(block2, layout2), pw::OkStatus());
949
950 EXPECT_EQ(block1->Alignment(), kAlign);
951 EXPECT_EQ(block2->Alignment(), kAlign * 2);
952 }
953
TEST_FOR_EACH_BLOCK_TYPE(FreeBlockAlignmentIsAlwaysOne)954 TEST_FOR_EACH_BLOCK_TYPE(FreeBlockAlignmentIsAlwaysOne) {
955 constexpr size_t kN = 1024;
956 constexpr size_t kSplit1 = 128;
957 constexpr size_t kAlign = 32;
958
959 std::array<std::byte, kN> bytes{};
960 auto result = BlockType::Init(bytes);
961 ASSERT_EQ(result.status(), pw::OkStatus());
962 BlockType* block1 = *result;
963
964 Layout layout(kSplit1, kAlign);
965 EXPECT_EQ(BlockType::AllocFirst(block1, layout), pw::OkStatus());
966 block1->MarkFree();
967 EXPECT_EQ(block1->Alignment(), 1U);
968 }
969
970 } // namespace
971