xref: /aosp_15_r20/external/pigweed/pw_allocator/block/detailed_block_test.cc (revision 61c4878ac05f98d0ceed94b57d316916de578985) 
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/detailed_block.h"
16 
17 #include <array>
18 #include <cstdint>
19 #include <cstring>
20 
21 #include "lib/stdcompat/bit.h"
22 #include "pw_allocator/block/testing.h"
23 #include "pw_assert/check.h"
24 #include "pw_assert/internal/check_impl.h"
25 #include "pw_bytes/alignment.h"
26 #include "pw_bytes/span.h"
27 #include "pw_span/span.h"
28 #include "pw_status/status.h"
29 #include "pw_unit_test/framework.h"
30 
31 namespace {
32 
33 // Test fixtures.
34 using ::pw::allocator::Layout;
35 using ::pw::allocator::test::GetAlignedOffsetAfter;
36 using ::pw::allocator::test::GetOuterSize;
37 using ::pw::allocator::test::Preallocate;
38 using ::pw::allocator::test::Preallocation;
39 
40 using BlockResultPrev = pw::allocator::internal::GenericBlockResult::Prev;
41 using BlockResultNext = pw::allocator::internal::GenericBlockResult::Next;
42 
43 // The size of the memory region used in tests.
44 constexpr size_t kN = 1024;
45 
46 // The large alignment used in alignment-related tests.
47 constexpr size_t kAlign = 64;
48 
49 template <typename BlockType>
50 class BlockTest : public ::testing::Test {
51  protected:
52   // Some tests below need a block with a nonzero inner size to fit within
53   // alignment boundaries.
54   static_assert(kAlign > BlockType::kBlockOverhead + BlockType::kAlignment);
55 
56   alignas(BlockType::kAlignment) std::array<std::byte, kN> bytes_;
57 };
58 
59 // A block type with more overhead.
60 using LargeOffsetBlock = ::pw::allocator::DetailedBlock<uint64_t>;
61 
62 class LargeOffsetBlockTest : public BlockTest<LargeOffsetBlock> {
63  protected:
64   using BlockType = LargeOffsetBlock;
65 };
66 
67 // A block type with less overhead.
68 using SmallOffsetBlock = ::pw::allocator::DetailedBlock<uint16_t>;
69 
70 class SmallOffsetBlockTest : public BlockTest<SmallOffsetBlock> {
71  protected:
72   using BlockType = SmallOffsetBlock;
73 };
74 
75 /// Returns the smallest offset into the given memory region which can be
76 /// preceded by a valid block, and at which a block would have properly aligned
77 /// usable space of the given size.
78 ///
79 /// @pre ``bytes`` must not be smaller than the calculated offset plus
80 ///      ``layout.size()``.
81 template <typename BlockType>
GetFirstAlignedOffset(pw::ByteSpan bytes,Layout layout)82 size_t GetFirstAlignedOffset(pw::ByteSpan bytes, Layout layout) {
83   size_t min_block = BlockType::kBlockOverhead + 1;
84   size_t offset = GetAlignedOffsetAfter(
85       bytes.data(), layout.alignment(), min_block + BlockType::kBlockOverhead);
86   return min_block + offset;
87 }
88 
89 /// Returns the largest offset into the given memory region at which a block
90 /// would have properly aligned usable space of the given size.
91 ///
92 /// @pre ``bytes`` must not be smaller than the calculated offset plus
93 ///      ``layout.size()``.
94 template <typename BlockType>
GetLastAlignedOffset(pw::ByteSpan bytes,Layout layout)95 size_t GetLastAlignedOffset(pw::ByteSpan bytes, Layout layout) {
96   size_t min_offset = GetFirstAlignedOffset<BlockType>(bytes, layout);
97   return min_offset +
98          pw::AlignDown(bytes.subspan(min_offset).size() - layout.size(),
99                        layout.alignment());
100 }
101 
102 /// Iterates to each block reachable from the given one and asserts that it is
103 /// valid.
104 template <typename BlockType>
CheckAllReachableBlock(BlockType * block)105 void CheckAllReachableBlock(BlockType* block) {
106   // Rewind to start.
107   for (BlockType* prev = block->Prev(); prev != nullptr; prev = block->Prev()) {
108     block = prev;
109   }
110   for (; block != nullptr; block = block->Next()) {
111     ASSERT_TRUE(block->IsValid());
112   }
113 }
114 
115 // Macro to provide type-parameterized tests for the various block types above.
116 //
117 // Ideally, the unit tests below could just use `TYPED_TEST_P` and its
118 // asscoiated macros from GoogleTest, see
119 // https://github.com/google/googletest/blob/main/docs/advanced.md#type-parameterized-tests
120 //
121 // These macros are not supported by the light framework however, so this macro
122 // provides a custom implementation that works just for these types.
123 #define TEST_FOR_EACH_BLOCK_TYPE(TestCase) \
124   template <typename BlockType>            \
125   void TestCase(pw::ByteSpan bytes_);      \
126   TEST_F(LargeOffsetBlockTest, TestCase) { \
127     TestCase<LargeOffsetBlock>(bytes_);    \
128   }                                        \
129   TEST_F(SmallOffsetBlockTest, TestCase) { \
130     TestCase<SmallOffsetBlock>(bytes_);    \
131   }                                        \
132   template <typename BlockType>            \
133   void TestCase([[maybe_unused]] pw::ByteSpan bytes_)
134 
135 // Unit tests.
136 
TEST_FOR_EACH_BLOCK_TYPE(CanCreateSingleAlignedBlock)137 TEST_FOR_EACH_BLOCK_TYPE(CanCreateSingleAlignedBlock) {
138   auto result = BlockType::Init(bytes_);
139   ASSERT_EQ(result.status(), pw::OkStatus());
140   BlockType* block = *result;
141 
142   EXPECT_EQ(block->OuterSize(), kN);
143   EXPECT_EQ(block->InnerSize(), kN - BlockType::kBlockOverhead);
144   EXPECT_EQ(block->Prev(), nullptr);
145   EXPECT_EQ(block->Next(), nullptr);
146   EXPECT_TRUE(block->IsFree());
147   EXPECT_EQ(block->Next(), nullptr);
148   CheckAllReachableBlock(block);
149 }
150 
TEST_FOR_EACH_BLOCK_TYPE(CanCreateUnalignedSingleBlock)151 TEST_FOR_EACH_BLOCK_TYPE(CanCreateUnalignedSingleBlock) {
152   pw::ByteSpan aligned(bytes_);
153 
154   auto result = BlockType::Init(aligned.subspan(1));
155   EXPECT_EQ(result.status(), pw::OkStatus());
156 }
157 
TEST_FOR_EACH_BLOCK_TYPE(CannotCreateTooSmallBlock)158 TEST_FOR_EACH_BLOCK_TYPE(CannotCreateTooSmallBlock) {
159   std::array<std::byte, 2> bytes;
160   auto result = BlockType::Init(bytes);
161   EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
162 }
163 
TEST(BlockTest,CannotCreateTooLargeBlock)164 TEST(BlockTest, CannotCreateTooLargeBlock) {
165   std::array<std::byte, kN> bytes;
166   auto result = pw::allocator::DetailedBlock<uint8_t>::Init(bytes);
167   EXPECT_EQ(result.status(), pw::Status::OutOfRange());
168 }
169 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_Null)170 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_Null) {
171   constexpr Layout kLayout(1, 1);
172 
173   BlockType* block = nullptr;
174 
175   auto result = BlockType::AllocFirst(std::move(block), kLayout);
176   EXPECT_EQ(result.status(), pw::Status::InvalidArgument());
177   EXPECT_EQ(result.block(), nullptr);
178 }
179 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_ZeroSize)180 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_ZeroSize) {
181   constexpr Layout kLayout(0, 1);
182 
183   auto* block = Preallocate<BlockType>(
184       bytes_,
185       {
186           {Preallocation::kSizeRemaining, Preallocation::kFree},
187       });
188 
189   auto result = BlockType::AllocFirst(std::move(block), kLayout);
190   EXPECT_EQ(result.status(), pw::Status::InvalidArgument());
191   CheckAllReachableBlock(result.block());
192 }
193 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_Used)194 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_Used) {
195   constexpr Layout kLayout(1, 1);
196 
197   auto* block = Preallocate<BlockType>(
198       bytes_,
199       {
200           {Preallocation::kSizeRemaining, Preallocation::kUsed},
201       });
202 
203   auto result = BlockType::AllocFirst(std::move(block), kLayout);
204   EXPECT_EQ(result.status(), pw::Status::FailedPrecondition());
205   CheckAllReachableBlock(result.block());
206 }
207 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_TooSmall)208 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_TooSmall) {
209   constexpr Layout kLayout(256, kAlign);
210 
211   // Trim the buffer so that the layout does not fit.
212   pw::ByteSpan bytes = bytes_.subspan(
213       0, GetOuterSize<BlockType>(kLayout.size()) - BlockType::kAlignment);
214 
215   auto* block = Preallocate<BlockType>(
216       bytes,
217       {
218           {Preallocation::kSizeRemaining, Preallocation::kFree},
219       });
220   auto result = BlockType::AllocFirst(std::move(block), kLayout);
221   EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
222   CheckAllReachableBlock(result.block());
223 }
224 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_Exact_FirstBlock)225 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_Exact_FirstBlock) {
226   constexpr Layout kLayout(256, kAlign);
227 
228   // Trim the front of the buffer so that the first block is aligned.
229   size_t trim =
230       GetAlignedOffsetAfter(bytes_.data(), kAlign, BlockType::kBlockOverhead);
231   pw::ByteSpan bytes = bytes_.subspan(trim);
232 
233   // Leave enough space free for the requested block.
234   size_t available = GetOuterSize<BlockType>(kLayout.size());
235   auto* block = Preallocate<BlockType>(
236       bytes,
237       {
238           {available, Preallocation::kFree},
239           {Preallocation::kSizeRemaining, Preallocation::kUsed},
240       });
241 
242   // Allocate from the front of the block.
243   auto result = BlockType::AllocFirst(std::move(block), kLayout);
244   ASSERT_EQ(result.status(), pw::OkStatus());
245   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
246   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
247   block = result.block();
248 
249   EXPECT_GE(block->InnerSize(), kLayout.size());
250   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
251   EXPECT_EQ(addr % kAlign, 0U);
252   EXPECT_FALSE(block->IsFree());
253   CheckAllReachableBlock(block);
254 }
255 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_Exact_SubsequentBlock)256 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_Exact_SubsequentBlock) {
257   constexpr Layout kLayout(256, kAlign);
258 
259   // Preallocate a first block so that the next block is aligned.
260   size_t leading = GetFirstAlignedOffset<BlockType>(bytes_, kLayout);
261 
262   // Leave enough space free for the requested block.
263   size_t available = GetOuterSize<BlockType>(kLayout.size());
264 
265   auto* block = Preallocate<BlockType>(
266       bytes_,
267       {
268           {leading, Preallocation::kUsed},
269           {available, Preallocation::kFree},
270           {Preallocation::kSizeRemaining, Preallocation::kUsed},
271       });
272   block = block->Next();
273 
274   // Allocate from the front of the block.
275   auto result = BlockType::AllocFirst(std::move(block), kLayout);
276   ASSERT_EQ(result.status(), pw::OkStatus());
277   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
278   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
279   block = result.block();
280 
281   EXPECT_GE(block->InnerSize(), kLayout.size());
282   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
283   EXPECT_EQ(addr % kAlign, 0U);
284   EXPECT_FALSE(block->IsFree());
285   CheckAllReachableBlock(block);
286 }
287 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewNext_FirstBlock)288 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewNext_FirstBlock) {
289   constexpr Layout kLayout(256, kAlign);
290 
291   // Trim the front of the buffer so that the first block is aligned.
292   size_t trim =
293       GetAlignedOffsetAfter(bytes_.data(), kAlign, BlockType::kBlockOverhead);
294   pw::ByteSpan bytes = bytes_.subspan(trim);
295 
296   // Leave enough space free for the requested block and one more block.
297   size_t available =
298       GetOuterSize<BlockType>(kLayout.size()) + GetOuterSize<BlockType>(1);
299 
300   auto* block = Preallocate<BlockType>(
301       bytes,
302       {
303           {available, Preallocation::kFree},
304           {Preallocation::kSizeRemaining, Preallocation::kUsed},
305       });
306 
307   // Allocate from the front of the block.
308   auto result = BlockType::AllocFirst(std::move(block), kLayout);
309   ASSERT_EQ(result.status(), pw::OkStatus());
310   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
311   EXPECT_EQ(result.next(), BlockResultNext::kSplitNew);
312   block = result.block();
313 
314   EXPECT_GE(block->InnerSize(), kLayout.size());
315   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
316   EXPECT_EQ(addr % kAlign, 0U);
317   EXPECT_FALSE(block->IsFree());
318   CheckAllReachableBlock(block);
319 }
320 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewNext_SubsequentBlock)321 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewNext_SubsequentBlock) {
322   constexpr Layout kLayout(256, kAlign);
323 
324   // Preallocate a first block so that the next block is aligned.
325   size_t leading = GetFirstAlignedOffset<BlockType>(bytes_, kLayout);
326 
327   // Leave enough space free for the requested block and one more block.
328   size_t available =
329       GetOuterSize<BlockType>(kLayout.size()) + GetOuterSize<BlockType>(1);
330 
331   auto* block = Preallocate<BlockType>(
332       bytes_,
333       {
334           {leading, Preallocation::kUsed},
335           {available, Preallocation::kFree},
336           {Preallocation::kSizeRemaining, Preallocation::kUsed},
337       });
338   block = block->Next();
339 
340   // Allocate from the front of the block.
341   auto result = BlockType::AllocFirst(std::move(block), kLayout);
342   ASSERT_EQ(result.status(), pw::OkStatus());
343   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
344   EXPECT_EQ(result.next(), BlockResultNext::kSplitNew);
345   block = result.block();
346 
347   EXPECT_GE(block->InnerSize(), kLayout.size());
348   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
349   EXPECT_EQ(addr % kAlign, 0U);
350   EXPECT_FALSE(block->IsFree());
351   CheckAllReachableBlock(block);
352 }
353 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewPrev_FirstBlock)354 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewPrev_FirstBlock) {
355   constexpr Layout kLayout(256, kAlign);
356 
357   // Trim the front of the buffer so that there is room for a block before the
358   // first alignment boundary.
359   size_t trim =
360       GetAlignedOffsetAfter(bytes_.data(), kAlign, BlockType::kBlockOverhead) +
361       kAlign - GetOuterSize<BlockType>(1);
362   pw::ByteSpan bytes = bytes_.subspan(trim);
363 
364   // Leave enough space free for a block and the requested block.
365   size_t available =
366       GetOuterSize<BlockType>(1) + GetOuterSize<BlockType>(kLayout.size());
367 
368   auto* block = Preallocate<BlockType>(
369       bytes,
370       {
371           {available, Preallocation::kFree},
372           {Preallocation::kSizeRemaining, Preallocation::kUsed},
373       });
374 
375   // Allocate from the front of the block.
376   auto result = BlockType::AllocFirst(std::move(block), kLayout);
377   ASSERT_EQ(result.status(), pw::OkStatus());
378   EXPECT_EQ(result.prev(), BlockResultPrev::kSplitNew);
379   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
380   block = result.block();
381 
382   EXPECT_GE(block->InnerSize(), kLayout.size());
383   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
384   EXPECT_EQ(addr % kAlign, 0U);
385   EXPECT_FALSE(block->IsFree());
386   CheckAllReachableBlock(block);
387 }
388 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewPrev_SubsequentBlock)389 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewPrev_SubsequentBlock) {
390   constexpr Layout kLayout(256, kAlign);
391 
392   // Preallocate a first block with room for another block before the next
393   // alignment boundary.
394   size_t leading = GetFirstAlignedOffset<BlockType>(bytes_, kLayout) + kAlign -
395                    GetOuterSize<BlockType>(1);
396 
397   // Leave enough space free for a block and the requested block.
398   size_t available =
399       GetOuterSize<BlockType>(1) + GetOuterSize<BlockType>(kLayout.size());
400 
401   auto* block = Preallocate<BlockType>(
402       bytes_,
403       {
404           {leading, Preallocation::kUsed},
405           {available, Preallocation::kFree},
406           {Preallocation::kSizeRemaining, Preallocation::kUsed},
407       });
408   block = block->Next();
409 
410   // Allocate from the front of the block.
411   auto result = BlockType::AllocFirst(std::move(block), kLayout);
412   ASSERT_EQ(result.status(), pw::OkStatus());
413   EXPECT_EQ(result.prev(), BlockResultPrev::kSplitNew);
414   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
415   block = result.block();
416 
417   EXPECT_GE(block->InnerSize(), kLayout.size());
418   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
419   EXPECT_EQ(addr % kAlign, 0U);
420   EXPECT_FALSE(block->IsFree());
421   CheckAllReachableBlock(block);
422 }
423 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewPrevAndNewNext_FirstBlock)424 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewPrevAndNewNext_FirstBlock) {
425   constexpr Layout kLayout(256, kAlign);
426 
427   // Trim the front of the buffer so that there is room for a block before the
428   // first alignment boundary.
429   size_t trim =
430       GetAlignedOffsetAfter(bytes_.data(), kAlign, BlockType::kBlockOverhead) +
431       kAlign - GetOuterSize<BlockType>(1);
432   pw::ByteSpan bytes = bytes_.subspan(trim);
433 
434   // Leave enough space free for a block, the requested block, and one more
435   // block.
436   size_t available = GetOuterSize<BlockType>(1) +
437                      GetOuterSize<BlockType>(kLayout.size()) +
438                      GetOuterSize<BlockType>(1);
439 
440   auto* block = Preallocate<BlockType>(
441       bytes,
442       {
443           {available, Preallocation::kFree},
444           {Preallocation::kSizeRemaining, Preallocation::kUsed},
445       });
446 
447   // Allocate from the front of the block.
448   auto result = BlockType::AllocFirst(std::move(block), kLayout);
449   ASSERT_EQ(result.status(), pw::OkStatus());
450   EXPECT_EQ(result.prev(), BlockResultPrev::kSplitNew);
451   EXPECT_EQ(result.next(), BlockResultNext::kSplitNew);
452   block = result.block();
453 
454   EXPECT_GE(block->InnerSize(), kLayout.size());
455   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
456   EXPECT_EQ(addr % kAlign, 0U);
457   EXPECT_FALSE(block->IsFree());
458   CheckAllReachableBlock(block);
459 }
460 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewPrevAndNewNext_SubsequentBlock)461 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_NewPrevAndNewNext_SubsequentBlock) {
462   constexpr Layout kLayout(256, kAlign);
463 
464   // Preallocate a first block with room for another block before the next
465   // alignment boundary.
466   size_t leading = GetFirstAlignedOffset<BlockType>(bytes_, kLayout) + kAlign -
467                    GetOuterSize<BlockType>(1);
468 
469   // Leave enough space free for a block and the requested block and one more
470   // block.
471   size_t available = kAlign + GetOuterSize<BlockType>(kLayout.size());
472 
473   auto* block = Preallocate<BlockType>(
474       bytes_,
475       {
476           {leading, Preallocation::kUsed},
477           {available, Preallocation::kFree},
478           {Preallocation::kSizeRemaining, Preallocation::kUsed},
479       });
480   block = block->Next();
481 
482   auto result = BlockType::AllocFirst(std::move(block), kLayout);
483   ASSERT_EQ(result.status(), pw::OkStatus());
484   EXPECT_EQ(result.prev(), BlockResultPrev::kSplitNew);
485   EXPECT_EQ(result.next(), BlockResultNext::kSplitNew);
486   block = result.block();
487 
488   EXPECT_GE(block->InnerSize(), kLayout.size());
489   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
490   EXPECT_EQ(addr % kAlign, 0U);
491   EXPECT_FALSE(block->IsFree());
492   CheckAllReachableBlock(block);
493 }
494 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_ShiftToPrev_FirstBlock)495 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_ShiftToPrev_FirstBlock) {
496   constexpr Layout kLayout(256, kAlign);
497 
498   // Trim the front of the buffer so that there is `kAlignment` bytes before
499   // where the aligned block would start.
500   size_t trim =
501       GetAlignedOffsetAfter(bytes_.data(), kAlign, BlockType::kBlockOverhead) +
502       kAlign - BlockType::kAlignment;
503   pw::ByteSpan bytes = bytes_.subspan(trim);
504 
505   // Leave enough space free for the `kAlignment` bytes and the requested block.
506   size_t available =
507       BlockType::kAlignment + GetOuterSize<BlockType>(kLayout.size());
508 
509   auto* block = Preallocate<BlockType>(
510       bytes,
511       {
512           {available, Preallocation::kFree},
513           {Preallocation::kSizeRemaining, Preallocation::kUsed},
514       });
515 
516   // Attempt and fail to allocate from the front of the block.
517   auto result = BlockType::AllocFirst(std::move(block), kLayout);
518   EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
519   CheckAllReachableBlock(result.block());
520 }
521 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_ShiftToPrev_SubsequentBlock)522 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_ShiftToPrev_SubsequentBlock) {
523   constexpr Layout kLayout(256, kAlign);
524 
525   // Preallocate a first block so that there is `kAlignment` bytes before
526   // where the aligned block would start.
527   size_t leading = GetFirstAlignedOffset<BlockType>(bytes_, kLayout) + kAlign -
528                    BlockType::kAlignment;
529 
530   // Leave enough space free for the `kAlignment` bytes and the requested block.
531   size_t available =
532       BlockType::kAlignment + GetOuterSize<BlockType>(kLayout.size());
533 
534   auto* first = Preallocate<BlockType>(
535       bytes_,
536       {
537           {leading, Preallocation::kUsed},
538           {available, Preallocation::kFree},
539           {Preallocation::kSizeRemaining, Preallocation::kUsed},
540       });
541   BlockType* block = first->Next();
542 
543   // Allocate from the front of the block.
544   auto result = BlockType::AllocFirst(std::move(block), kLayout);
545   ASSERT_EQ(result.status(), pw::OkStatus());
546   EXPECT_EQ(result.prev(), BlockResultPrev::kResizedLarger);
547   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
548   block = result.block();
549 
550   // Verify the previous block was padded.
551   size_t old_requested_size = leading - BlockType::kBlockOverhead;
552   auto old_layout = first->RequestedLayout();
553   EXPECT_EQ(old_layout->size(), old_requested_size);
554 
555   // Resize the first block, and verify the padding is updated.
556   size_t new_requested_size = old_requested_size + 1;
557   result = first->Resize(new_requested_size);
558   ASSERT_EQ(result.status(), pw::OkStatus());
559   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
560   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
561   auto new_layout = first->RequestedLayout();
562   EXPECT_EQ(new_layout->size(), new_requested_size);
563 
564   EXPECT_GE(block->InnerSize(), kLayout.size());
565   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
566   EXPECT_EQ(addr % kAlign, 0U);
567   EXPECT_FALSE(block->IsFree());
568 
569   // Verify that freeing the subsequent block does not reclaim bytes that were
570   // resized.
571   result = BlockType::Free(std::move(block));
572   ASSERT_EQ(result.status(), pw::OkStatus());
573   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
574   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
575   CheckAllReachableBlock(first);
576 }
577 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_ShiftToPrevAndNewNext_FirstBlock)578 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocFirst_ShiftToPrevAndNewNext_FirstBlock) {
579   constexpr Layout kLayout(256, kAlign);
580 
581   // Trim the front of the buffer so that there is `kAlignment` bytes before
582   // where the aligned block would start.
583   size_t trim =
584       GetAlignedOffsetAfter(bytes_.data(), kAlign, BlockType::kBlockOverhead) +
585       kAlign - BlockType::kAlignment;
586   pw::ByteSpan bytes = bytes_.subspan(trim);
587 
588   // Leave enough space free for the `kAlignment` bytes, the requested block,
589   // and one more block.
590   size_t available = BlockType::kAlignment +
591                      GetOuterSize<BlockType>(kLayout.size()) +
592                      GetOuterSize<BlockType>(1);
593 
594   auto* block = Preallocate<BlockType>(
595       bytes,
596       {
597           {available, Preallocation::kFree},
598           {Preallocation::kSizeRemaining, Preallocation::kUsed},
599       });
600 
601   // Attempt and fail to allocate from the front of the block.
602   auto result = BlockType::AllocFirst(std::move(block), kLayout);
603   EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
604   CheckAllReachableBlock(result.block());
605 }
606 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_ShiftToPrevAndNewNext_SubsequentBlock)607 TEST_FOR_EACH_BLOCK_TYPE(CanAllocFirst_ShiftToPrevAndNewNext_SubsequentBlock) {
608   constexpr Layout kLayout(256, kAlign);
609 
610   // Preallocate a first block so that there is `kAlignment` bytes before
611   // where the aligned block would start.
612   size_t leading = GetFirstAlignedOffset<BlockType>(bytes_, kLayout) + kAlign -
613                    BlockType::kAlignment;
614 
615   // Leave enough space free for the `kAlignment` bytes, the requested block,
616   // and one more block.
617   size_t available = BlockType::kAlignment +
618                      GetOuterSize<BlockType>(kLayout.size()) +
619                      GetOuterSize<BlockType>(1);
620 
621   auto* block = Preallocate<BlockType>(
622       bytes_,
623       {
624           {leading, Preallocation::kUsed},
625           {available, Preallocation::kFree},
626           {Preallocation::kSizeRemaining, Preallocation::kUsed},
627       });
628   block = block->Next();
629 
630   // Allocate from the front of the block.
631   auto result = BlockType::AllocFirst(std::move(block), kLayout);
632   ASSERT_EQ(result.status(), pw::OkStatus());
633   EXPECT_EQ(result.prev(), BlockResultPrev::kResizedLarger);
634   EXPECT_EQ(result.next(), BlockResultNext::kSplitNew);
635   block = result.block();
636 
637   EXPECT_GE(block->InnerSize(), kLayout.size());
638   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
639   EXPECT_EQ(addr % kAlign, 0U);
640   EXPECT_FALSE(block->IsFree());
641   CheckAllReachableBlock(block);
642 }
643 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLast_Null)644 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLast_Null) {
645   constexpr Layout kLayout(1, 1);
646 
647   BlockType* block = nullptr;
648 
649   // Attempt and fail to allocate from the front of the block.
650   auto result = BlockType::AllocLast(std::move(block), kLayout);
651   EXPECT_EQ(result.status(), pw::Status::InvalidArgument());
652   EXPECT_EQ(result.block(), nullptr);
653 }
654 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLast_ZeroSize)655 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLast_ZeroSize) {
656   constexpr Layout kLayout(0, 1);
657 
658   auto* block = Preallocate<BlockType>(
659       bytes_,
660       {
661           {Preallocation::kSizeRemaining, Preallocation::kFree},
662       });
663 
664   // Check if we expect this to succeed.
665   auto can_alloc_last = block->CanAlloc(kLayout);
666   EXPECT_EQ(can_alloc_last.status(), pw::Status::InvalidArgument());
667 
668   // Attempt and fail to allocate from the front of the block.
669   auto result = BlockType::AllocLast(std::move(block), kLayout);
670   EXPECT_EQ(result.status(), pw::Status::InvalidArgument());
671   CheckAllReachableBlock(result.block());
672 }
673 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLast_Used)674 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLast_Used) {
675   constexpr Layout kLayout(1, 1);
676 
677   auto* block = Preallocate<BlockType>(
678       bytes_,
679       {
680           {Preallocation::kSizeRemaining, Preallocation::kUsed},
681       });
682 
683   // Check if we expect this to succeed.
684   auto can_alloc_last = block->CanAlloc(kLayout);
685   EXPECT_EQ(can_alloc_last.status(), pw::Status::FailedPrecondition());
686 
687   // Attempt and fail to allocate from the front of the block.
688   auto result = BlockType::AllocLast(std::move(block), kLayout);
689   EXPECT_EQ(result.status(), pw::Status::FailedPrecondition());
690   CheckAllReachableBlock(result.block());
691 }
692 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLast_TooSmall)693 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLast_TooSmall) {
694   constexpr Layout kLayout(256, kAlign);
695 
696   // Trim the buffer so that the layout does not fit.
697   pw::ByteSpan bytes = bytes_.subspan(
698       0, GetOuterSize<BlockType>(kLayout.size()) - BlockType::kAlignment);
699 
700   auto* block = Preallocate<BlockType>(
701       bytes,
702       {
703           {Preallocation::kSizeRemaining, Preallocation::kFree},
704       });
705 
706   // Check if we expect this to succeed.
707   auto can_alloc_last = block->CanAlloc(kLayout);
708   EXPECT_EQ(can_alloc_last.status(), pw::Status::ResourceExhausted());
709 
710   // Attempt and fail to allocate from the front of the block.
711   auto result = BlockType::AllocLast(std::move(block), kLayout);
712   EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
713   CheckAllReachableBlock(result.block());
714 }
715 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast_Exact_FirstBlock)716 TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast_Exact_FirstBlock) {
717   constexpr Layout kLayout(256, kAlign);
718 
719   // Trim the front of the buffer so that the first block is aligned.
720   size_t trim =
721       GetAlignedOffsetAfter(bytes_.data(), kAlign, BlockType::kBlockOverhead);
722   pw::ByteSpan bytes = bytes_.subspan(trim);
723 
724   // Leave enough space free for the requested block.
725   size_t available = GetOuterSize<BlockType>(kLayout.size());
726 
727   auto* block = Preallocate<BlockType>(
728       bytes,
729       {
730           {available, Preallocation::kFree},
731           {Preallocation::kSizeRemaining, Preallocation::kUsed},
732       });
733 
734   // Check if we expect this to succeed.
735   auto can_alloc_last = block->CanAlloc(kLayout);
736   ASSERT_EQ(can_alloc_last.status(), pw::OkStatus());
737   EXPECT_EQ(can_alloc_last.size(), 0U);
738 
739   // Allocate from the back of the block.
740   auto result = BlockType::AllocLast(std::move(block), kLayout);
741   ASSERT_EQ(result.status(), pw::OkStatus());
742   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
743   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
744   block = result.block();
745 
746   EXPECT_GE(block->InnerSize(), kLayout.size());
747   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
748   EXPECT_EQ(addr % kAlign, 0U);
749   EXPECT_FALSE(block->IsFree());
750   CheckAllReachableBlock(block);
751 }
752 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast_Exact_SubsequentBlock)753 TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast_Exact_SubsequentBlock) {
754   constexpr Layout kLayout(256, kAlign);
755 
756   // Preallocate a first block so that the next block is aligned.
757   size_t leading = GetFirstAlignedOffset<BlockType>(bytes_, kLayout);
758 
759   // Leave enough space free for the requested block.
760   size_t available = GetOuterSize<BlockType>(kLayout.size());
761 
762   auto* block = Preallocate<BlockType>(
763       bytes_,
764       {
765           {leading, Preallocation::kUsed},
766           {available, Preallocation::kFree},
767           {Preallocation::kSizeRemaining, Preallocation::kUsed},
768       });
769   block = block->Next();
770 
771   // Check if we expect this to succeed.
772   auto can_alloc_last = block->CanAlloc(kLayout);
773   ASSERT_EQ(can_alloc_last.status(), pw::OkStatus());
774   EXPECT_EQ(can_alloc_last.size(), 0U);
775 
776   // Allocate from the back of the block.
777   auto result = BlockType::AllocLast(std::move(block), kLayout);
778   ASSERT_EQ(result.status(), pw::OkStatus());
779   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
780   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
781   block = result.block();
782 
783   EXPECT_GE(block->InnerSize(), kLayout.size());
784   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
785   EXPECT_EQ(addr % kAlign, 0U);
786   EXPECT_FALSE(block->IsFree());
787   CheckAllReachableBlock(block);
788 }
789 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast_NewPrev_FirstBlock)790 TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast_NewPrev_FirstBlock) {
791   constexpr Layout kLayout(256, kAlign);
792 
793   // Trim the front of the buffer so that there is room for a block before the
794   // first alignment boundary.
795   size_t trim =
796       GetAlignedOffsetAfter(bytes_.data(), kAlign, BlockType::kBlockOverhead) +
797       kAlign - GetOuterSize<BlockType>(1);
798   pw::ByteSpan bytes = bytes_.subspan(trim);
799 
800   // Leave enough space free for a block and the requested block.
801   size_t available =
802       GetOuterSize<BlockType>(1) + GetOuterSize<BlockType>(kLayout.size());
803 
804   auto* block = Preallocate<BlockType>(
805       bytes,
806       {
807           {available, Preallocation::kFree},
808           {Preallocation::kSizeRemaining, Preallocation::kUsed},
809       });
810 
811   // Check if we expect this to succeed.
812   auto can_alloc_last = block->CanAlloc(kLayout);
813   ASSERT_EQ(can_alloc_last.status(), pw::OkStatus());
814   EXPECT_EQ(can_alloc_last.size(), GetOuterSize<BlockType>(1));
815 
816   // Allocate from the back of the block.
817   auto result = BlockType::AllocLast(std::move(block), kLayout);
818   ASSERT_EQ(result.status(), pw::OkStatus());
819   EXPECT_EQ(result.prev(), BlockResultPrev::kSplitNew);
820   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
821   block = result.block();
822 
823   EXPECT_GE(block->InnerSize(), kLayout.size());
824   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
825   EXPECT_EQ(addr % kAlign, 0U);
826   EXPECT_FALSE(block->IsFree());
827   CheckAllReachableBlock(block);
828 }
829 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast_NewPrev_SubsequentBlock)830 TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast_NewPrev_SubsequentBlock) {
831   constexpr Layout kLayout(256, kAlign);
832 
833   // Preallocate a first block with room for another block before the next
834   // alignment boundary.
835   size_t leading = GetFirstAlignedOffset<BlockType>(bytes_, kLayout) + kAlign -
836                    GetOuterSize<BlockType>(1);
837 
838   // Leave enough space free for a block and the requested block.
839   size_t available =
840       GetOuterSize<BlockType>(1) + GetOuterSize<BlockType>(kLayout.size());
841 
842   auto* block = Preallocate<BlockType>(
843       bytes_,
844       {
845           {leading, Preallocation::kUsed},
846           {available, Preallocation::kFree},
847           {Preallocation::kSizeRemaining, Preallocation::kUsed},
848       });
849   block = block->Next();
850 
851   // Check if we expect this to succeed.
852   auto can_alloc_last = block->CanAlloc(kLayout);
853   ASSERT_EQ(can_alloc_last.status(), pw::OkStatus());
854   EXPECT_EQ(can_alloc_last.size(), GetOuterSize<BlockType>(1));
855 
856   // Allocate from the back of the block.
857   auto result = BlockType::AllocLast(std::move(block), kLayout);
858   ASSERT_EQ(result.status(), pw::OkStatus());
859   EXPECT_EQ(result.prev(), BlockResultPrev::kSplitNew);
860   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
861   block = result.block();
862 
863   EXPECT_GE(block->InnerSize(), kLayout.size());
864   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
865   EXPECT_EQ(addr % kAlign, 0U);
866   EXPECT_FALSE(block->IsFree());
867   CheckAllReachableBlock(block);
868 }
869 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLast_ShiftToPrev_FirstBlock)870 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLast_ShiftToPrev_FirstBlock) {
871   constexpr Layout kLayout(256, kAlign);
872 
873   // Trim the front of the buffer so that there is `kAlignment` bytes before
874   // where the aligned block would start.
875   size_t trim =
876       GetAlignedOffsetAfter(bytes_.data(), kAlign, BlockType::kBlockOverhead) +
877       kAlign - BlockType::kAlignment;
878   pw::ByteSpan bytes = bytes_.subspan(trim);
879 
880   // Leave enough space free for the `kAlignment` bytes and the requested block.
881   size_t available =
882       BlockType::kAlignment + GetOuterSize<BlockType>(kLayout.size());
883 
884   auto* block = Preallocate<BlockType>(
885       bytes,
886       {
887           {available, Preallocation::kFree},
888           {Preallocation::kSizeRemaining, Preallocation::kUsed},
889       });
890 
891   // Check if we expect this to succeed.
892   auto can_alloc_last = block->CanAlloc(kLayout);
893   EXPECT_EQ(can_alloc_last.status(), pw::Status::ResourceExhausted());
894 
895   // Attempt and fail to allocate from the back of the block.
896   auto result = BlockType::AllocFirst(std::move(block), kLayout);
897   EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
898   CheckAllReachableBlock(result.block());
899 }
900 
TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast_ShiftToPrev_SubsequentBlock)901 TEST_FOR_EACH_BLOCK_TYPE(CanAllocLast_ShiftToPrev_SubsequentBlock) {
902   constexpr Layout kLayout(256, kAlign);
903 
904   // Preallocate a first block so that there is `kAlignment` bytes before
905   // where the aligned block would start.
906   size_t leading = GetFirstAlignedOffset<BlockType>(bytes_, kLayout) + kAlign -
907                    BlockType::kAlignment;
908 
909   // Leave enough space free for the `kAlignment` bytes and the requested block.
910   size_t available =
911       BlockType::kAlignment + GetOuterSize<BlockType>(kLayout.size());
912 
913   auto* block = Preallocate<BlockType>(
914       bytes_,
915       {
916           {leading, Preallocation::kUsed},
917           {available, Preallocation::kFree},
918           {Preallocation::kSizeRemaining, Preallocation::kUsed},
919       });
920   block = block->Next();
921 
922   // Check if we expect this to succeed.
923   auto can_alloc_last = block->CanAlloc(kLayout);
924   ASSERT_EQ(can_alloc_last.status(), pw::OkStatus());
925   EXPECT_EQ(can_alloc_last.size(), BlockType::kAlignment);
926 
927   // Allocate from the back of the block.
928   auto result = BlockType::AllocLast(std::move(block), kLayout);
929   ASSERT_EQ(result.status(), pw::OkStatus());
930   EXPECT_EQ(result.prev(), BlockResultPrev::kResizedLarger);
931   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
932   EXPECT_EQ(result.size(), BlockType::kAlignment);
933   block = result.block();
934 
935   EXPECT_GE(block->InnerSize(), kLayout.size());
936   auto addr = cpp20::bit_cast<uintptr_t>(block->UsableSpace());
937   EXPECT_EQ(addr % kAlign, 0U);
938   EXPECT_FALSE(block->IsFree());
939 
940   // Deallocate the block, and verify the bytes are reclaimed.
941   result = BlockType::Free(std::move(block));
942   ASSERT_EQ(result.status(), pw::OkStatus());
943   EXPECT_EQ(result.prev(), BlockResultPrev::kResizedSmaller);
944   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
945   EXPECT_EQ(result.size(), BlockType::kAlignment);
946 
947   CheckAllReachableBlock(result.block());
948 }
949 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastIfTooSmallForAlignment)950 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastIfTooSmallForAlignment) {
951   constexpr Layout kLayout(256, kAlign);
952   constexpr size_t kOuterSize = BlockType::kBlockOverhead + kLayout.size();
953 
954   // Make sure the block's usable space is not aligned.
955   size_t outer_size = GetFirstAlignedOffset<BlockType>(bytes_, kLayout) + 1;
956   auto* block = Preallocate<BlockType>(
957       bytes_,
958       {
959           {outer_size, Preallocation::kUsed},
960           {kOuterSize, Preallocation::kFree},
961           {Preallocation::kSizeRemaining, Preallocation::kUsed},
962       });
963   block = block->Next();
964 
965   // Cannot allocate without room to a split a block for alignment.
966   auto result = BlockType::AllocLast(std::move(block), kLayout);
967   EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
968   CheckAllReachableBlock(result.block());
969 }
970 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastFromNull)971 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastFromNull) {
972   BlockType* block = nullptr;
973   constexpr Layout kLayout(1, 1);
974   auto result = BlockType::AllocLast(std::move(block), kLayout);
975   EXPECT_EQ(result.status(), pw::Status::InvalidArgument());
976   EXPECT_EQ(result.block(), nullptr);
977 }
978 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastZeroSize)979 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastZeroSize) {
980   auto* block = Preallocate<BlockType>(
981       bytes_,
982       {
983           {Preallocation::kSizeRemaining, Preallocation::kFree},
984       });
985   constexpr Layout kLayout(0, 1);
986   auto result = BlockType::AllocLast(std::move(block), kLayout);
987   EXPECT_EQ(result.status(), pw::Status::InvalidArgument());
988   CheckAllReachableBlock(result.block());
989 }
990 
TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastFromUsed)991 TEST_FOR_EACH_BLOCK_TYPE(CannotAllocLastFromUsed) {
992   auto* block = Preallocate<BlockType>(
993       bytes_,
994       {
995           {Preallocation::kSizeRemaining, Preallocation::kUsed},
996       });
997   constexpr Layout kLayout(1, 1);
998   auto result = BlockType::AllocLast(std::move(block), kLayout);
999   EXPECT_EQ(result.status(), pw::Status::FailedPrecondition());
1000   CheckAllReachableBlock(result.block());
1001 }
1002 
TEST_FOR_EACH_BLOCK_TYPE(FreeingNullDoesNothing)1003 TEST_FOR_EACH_BLOCK_TYPE(FreeingNullDoesNothing) {
1004   BlockType* block = nullptr;
1005   auto result = BlockType::Free(std::move(block));
1006   EXPECT_EQ(result.status(), pw::Status::InvalidArgument());
1007 }
1008 
TEST_FOR_EACH_BLOCK_TYPE(FreeingFreeBlockDoesNothing)1009 TEST_FOR_EACH_BLOCK_TYPE(FreeingFreeBlockDoesNothing) {
1010   auto* block = Preallocate<BlockType>(
1011       bytes_,
1012       {
1013           {Preallocation::kSizeRemaining, Preallocation::kFree},
1014       });
1015   auto result = BlockType::Free(std::move(block));
1016   ASSERT_EQ(result.status(), pw::OkStatus());
1017   CheckAllReachableBlock(result.block());
1018 }
1019 
TEST_FOR_EACH_BLOCK_TYPE(CanFree)1020 TEST_FOR_EACH_BLOCK_TYPE(CanFree) {
1021   auto* block = Preallocate<BlockType>(
1022       bytes_,
1023       {
1024           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1025       });
1026 
1027   auto result = BlockType::Free(std::move(block));
1028   ASSERT_EQ(result.status(), pw::OkStatus());
1029   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
1030   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
1031 
1032   block = result.block();
1033   EXPECT_TRUE(block->IsFree());
1034   EXPECT_EQ(block->OuterSize(), kN);
1035   CheckAllReachableBlock(block);
1036 }
1037 
TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockWithoutMerging)1038 TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockWithoutMerging) {
1039   constexpr size_t kOuterSize = 256;
1040 
1041   auto* block = Preallocate<BlockType>(
1042       bytes_,
1043       {
1044           {kOuterSize, Preallocation::kUsed},
1045           {kOuterSize, Preallocation::kUsed},
1046           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1047       });
1048   block = block->Next();
1049   BlockType* next = block->Next();
1050   BlockType* prev = block->Prev();
1051 
1052   auto result = BlockType::Free(std::move(block));
1053   ASSERT_EQ(result.status(), pw::OkStatus());
1054   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
1055   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
1056 
1057   block = result.block();
1058   EXPECT_TRUE(block->IsFree());
1059   EXPECT_EQ(next, block->Next());
1060   EXPECT_EQ(prev, block->Prev());
1061   CheckAllReachableBlock(block);
1062 }
1063 
TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockAndMergeWithPrev)1064 TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockAndMergeWithPrev) {
1065   constexpr size_t kOuterSize = 256;
1066 
1067   auto* first = Preallocate<BlockType>(
1068       bytes_,
1069       {
1070           {kOuterSize, Preallocation::kFree},
1071           {kOuterSize, Preallocation::kUsed},
1072           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1073       });
1074   BlockType* block = first->Next();
1075   BlockType* next = block->Next();
1076 
1077   // Note that when merging with the previous free block, it is that previous
1078   // free block which is returned, and only the 'next' field indicates a merge.
1079   auto result = BlockType::Free(std::move(block));
1080   ASSERT_EQ(result.status(), pw::OkStatus());
1081   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
1082   EXPECT_EQ(result.next(), BlockResultNext::kMerged);
1083 
1084   block = result.block();
1085   EXPECT_EQ(block->Prev(), nullptr);
1086   EXPECT_EQ(block->Next(), next);
1087   CheckAllReachableBlock(block);
1088 }
1089 
TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockAndMergeWithNext)1090 TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockAndMergeWithNext) {
1091   constexpr size_t kOuterSize = 256;
1092 
1093   auto* first = Preallocate<BlockType>(
1094       bytes_,
1095       {
1096           {kOuterSize, Preallocation::kUsed},
1097           {kOuterSize, Preallocation::kUsed},
1098           {Preallocation::kSizeRemaining, Preallocation::kFree},
1099       });
1100   BlockType* block = first->Next();
1101   BlockType* prev = block->Prev();
1102 
1103   auto result = BlockType::Free(std::move(block));
1104   ASSERT_EQ(result.status(), pw::OkStatus());
1105   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
1106   EXPECT_EQ(result.next(), BlockResultNext::kMerged);
1107 
1108   block = result.block();
1109   EXPECT_TRUE(block->IsFree());
1110   EXPECT_EQ(block->Prev(), prev);
1111   EXPECT_EQ(block->Next(), nullptr);
1112   CheckAllReachableBlock(block);
1113 }
1114 
TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockAndMergeWithBoth)1115 TEST_FOR_EACH_BLOCK_TYPE(CanFreeBlockAndMergeWithBoth) {
1116   constexpr size_t kOuterSize = 128;
1117 
1118   auto* first = Preallocate<BlockType>(
1119       bytes_,
1120       {
1121           {kOuterSize, Preallocation::kFree},
1122           {kOuterSize, Preallocation::kUsed},
1123           {Preallocation::kSizeRemaining, Preallocation::kFree},
1124       });
1125   BlockType* block = first->Next();
1126 
1127   auto result = BlockType::Free(std::move(block));
1128   ASSERT_EQ(result.status(), pw::OkStatus());
1129   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
1130   EXPECT_EQ(result.next(), BlockResultNext::kMerged);
1131 
1132   block = result.block();
1133   EXPECT_EQ(block->Prev(), nullptr);
1134   EXPECT_EQ(block->Next(), nullptr);
1135   CheckAllReachableBlock(block);
1136 }
1137 
TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSameSize)1138 TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSameSize) {
1139   constexpr size_t kOuterSize = 256;
1140 
1141   auto* block = Preallocate<BlockType>(
1142       bytes_,
1143       {
1144           {kOuterSize, Preallocation::kUsed},
1145           {kOuterSize, Preallocation::kUsed},
1146           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1147       });
1148   block = block->Next();
1149 
1150   auto result = block->Resize(block->InnerSize());
1151   EXPECT_EQ(result.status(), pw::OkStatus());
1152   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
1153   EXPECT_EQ(result.next(), BlockResultNext::kUnchanged);
1154   CheckAllReachableBlock(block);
1155 }
1156 
TEST_FOR_EACH_BLOCK_TYPE(CannotResizeFreeBlock)1157 TEST_FOR_EACH_BLOCK_TYPE(CannotResizeFreeBlock) {
1158   constexpr size_t kOuterSize = 256;
1159 
1160   auto* block = Preallocate<BlockType>(
1161       bytes_,
1162       {
1163           {kOuterSize, Preallocation::kUsed},
1164           {kOuterSize, Preallocation::kFree},
1165           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1166       });
1167   block = block->Next();
1168 
1169   auto result = block->Resize(block->InnerSize());
1170   EXPECT_EQ(result.status(), pw::Status::FailedPrecondition());
1171   CheckAllReachableBlock(block);
1172 }
1173 
TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSmallerWithNextFree)1174 TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSmallerWithNextFree) {
1175   constexpr size_t kOuterSize = 256;
1176 
1177   auto* block = Preallocate<BlockType>(
1178       bytes_,
1179       {
1180           {kOuterSize, Preallocation::kUsed},
1181           {kOuterSize, Preallocation::kUsed},
1182           {Preallocation::kSizeRemaining, Preallocation::kFree},
1183       });
1184   block = block->Next();
1185   size_t next_inner_size = block->Next()->InnerSize();
1186 
1187   // Shrink by less than the minimum needed for a block. The extra should be
1188   // added to the subsequent block.
1189   size_t delta = BlockType::kBlockOverhead - BlockType::kAlignment;
1190   size_t new_inner_size = block->InnerSize() - delta;
1191   auto result = block->Resize(new_inner_size);
1192   EXPECT_EQ(result.status(), pw::OkStatus());
1193   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
1194   EXPECT_EQ(result.next(), BlockResultNext::kResized);
1195   EXPECT_EQ(block->InnerSize(), new_inner_size);
1196 
1197   BlockType* next = block->Next();
1198   EXPECT_TRUE(next->IsFree());
1199   EXPECT_EQ(next->InnerSize(), next_inner_size + delta);
1200   CheckAllReachableBlock(block);
1201 }
1202 
TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockLargerWithNextFree)1203 TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockLargerWithNextFree) {
1204   constexpr size_t kOuterSize = 256;
1205 
1206   auto* block = Preallocate<BlockType>(
1207       bytes_,
1208       {
1209           {kOuterSize, Preallocation::kUsed},
1210           {kOuterSize, Preallocation::kFree},
1211           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1212       });
1213   size_t next_inner_size = block->Next()->InnerSize();
1214 
1215   // Grow by less than the minimum needed for a block. The extra should be
1216   // added to the subsequent block.
1217   size_t delta = BlockType::kBlockOverhead;
1218   size_t new_inner_size = block->InnerSize() + delta;
1219   auto result = block->Resize(new_inner_size);
1220   EXPECT_EQ(result.status(), pw::OkStatus());
1221   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
1222   EXPECT_EQ(result.next(), BlockResultNext::kResized);
1223   EXPECT_EQ(block->InnerSize(), new_inner_size);
1224 
1225   BlockType* next = block->Next();
1226   EXPECT_TRUE(next->IsFree());
1227   EXPECT_EQ(next->InnerSize(), next_inner_size - delta);
1228   CheckAllReachableBlock(block);
1229 }
1230 
TEST_FOR_EACH_BLOCK_TYPE(CannotResizeBlockMuchLargerWithNextFree)1231 TEST_FOR_EACH_BLOCK_TYPE(CannotResizeBlockMuchLargerWithNextFree) {
1232   constexpr size_t kOuterSize = 256;
1233 
1234   auto* block = Preallocate<BlockType>(
1235       bytes_,
1236       {
1237           {kOuterSize, Preallocation::kUsed},
1238           {kOuterSize, Preallocation::kFree},
1239           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1240       });
1241 
1242   size_t new_inner_size = block->InnerSize() + kOuterSize + 1;
1243   auto result = block->Resize(new_inner_size);
1244   EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
1245   CheckAllReachableBlock(block);
1246 }
1247 
TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSmallerWithNextUsed)1248 TEST_FOR_EACH_BLOCK_TYPE(CanResizeBlockSmallerWithNextUsed) {
1249   constexpr Layout kLayout(256, kAlign);
1250   constexpr size_t kOuterSize = BlockType::kBlockOverhead + kLayout.size();
1251 
1252   auto* block = Preallocate<BlockType>(
1253       bytes_,
1254       {
1255           {kOuterSize, Preallocation::kUsed},
1256           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1257       });
1258 
1259   // Shrink the block.
1260   size_t delta = kLayout.size() / 2;
1261   size_t new_inner_size = block->InnerSize() - delta;
1262   auto result = block->Resize(new_inner_size);
1263   EXPECT_EQ(result.status(), pw::OkStatus());
1264   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
1265   EXPECT_EQ(result.next(), BlockResultNext::kSplitNew);
1266 
1267   BlockType* next = block->Next();
1268   EXPECT_TRUE(next->IsFree());
1269   EXPECT_EQ(next->OuterSize(), delta);
1270   CheckAllReachableBlock(block);
1271 }
1272 
TEST_FOR_EACH_BLOCK_TYPE(CannotResizeBlockLargerWithNextUsed)1273 TEST_FOR_EACH_BLOCK_TYPE(CannotResizeBlockLargerWithNextUsed) {
1274   constexpr size_t kOuterSize = 256;
1275 
1276   auto* block = Preallocate<BlockType>(
1277       bytes_,
1278       {
1279           {kOuterSize, Preallocation::kUsed},
1280           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1281       });
1282 
1283   size_t delta = BlockType::kBlockOverhead / 2;
1284   size_t new_inner_size = block->InnerSize() + delta;
1285   auto result = block->Resize(new_inner_size);
1286   EXPECT_EQ(result.status(), pw::Status::ResourceExhausted());
1287 }
1288 
TEST_FOR_EACH_BLOCK_TYPE(CanCheckValidBlock)1289 TEST_FOR_EACH_BLOCK_TYPE(CanCheckValidBlock) {
1290   constexpr size_t kOuterSize1 = 512;
1291   constexpr size_t kOuterSize2 = 256;
1292 
1293   auto* block = Preallocate<BlockType>(
1294       bytes_,
1295       {
1296           {kOuterSize1, Preallocation::kUsed},
1297           {kOuterSize2, Preallocation::kFree},
1298           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1299       });
1300   ASSERT_TRUE(block->IsValid());
1301 
1302   block = block->Next();
1303   ASSERT_TRUE(block->IsValid());
1304 
1305   block = block->Next();
1306   ASSERT_TRUE(block->IsValid());
1307 }
1308 
TEST_FOR_EACH_BLOCK_TYPE(CanCheckInvalidBlock)1309 TEST_FOR_EACH_BLOCK_TYPE(CanCheckInvalidBlock) {
1310   constexpr size_t kOuterSize1 = 128;
1311   constexpr size_t kOuterSize2 = 384;
1312 
1313   auto* block1 = Preallocate<BlockType>(
1314       bytes_,
1315       {
1316           {kOuterSize1, Preallocation::kUsed},
1317           {kOuterSize2, Preallocation::kFree},
1318           {Preallocation::kSizeRemaining, Preallocation::kUsed},
1319       });
1320   BlockType* block2 = block1->Next();
1321   BlockType* block3 = block2->Next();
1322 
1323   // Corrupt a Block header.
1324   // This must not touch memory outside the original region, or the test may
1325   // (correctly) abort when run with address sanitizer.
1326   // To remain as agostic to the internals of `Block` as possible, the test
1327   // copies a smaller block's header to a larger block, and ensure's the
1328   // contents of blocks are blank.
1329   std::memset(block1->UsableSpace(), 0, block1->InnerSize());
1330   std::memset(block2->UsableSpace(), 0, block2->InnerSize());
1331   std::memset(block3->UsableSpace(), 0, block3->InnerSize());
1332   EXPECT_TRUE(block1->IsValid());
1333   EXPECT_TRUE(block2->IsValid());
1334   EXPECT_TRUE(block3->IsValid());
1335   auto* src = cpp20::bit_cast<std::byte*>(block1);
1336   auto* dst = cpp20::bit_cast<std::byte*>(block2);
1337   std::memcpy(dst, src, sizeof(BlockType));
1338   EXPECT_FALSE(block1->IsValid());
1339   EXPECT_FALSE(block2->IsValid());
1340   EXPECT_FALSE(block3->IsValid());
1341 }
1342 
TEST_FOR_EACH_BLOCK_TYPE(CanCheckPoison)1343 TEST_FOR_EACH_BLOCK_TYPE(CanCheckPoison) {
1344   auto* block = Preallocate<BlockType>(
1345       bytes_,
1346       {
1347           {Preallocation::kSizeRemaining, Preallocation::kFree},
1348       });
1349 
1350   // Modify a byte in the middle of a free block.
1351   // Without poisoning, the modification is undetected.
1352   EXPECT_TRUE(block->IsFree());
1353   bytes_[kN / 2] = std::byte(0x7f);
1354   EXPECT_TRUE(block->IsValid());
1355 
1356   // Modify a byte in the middle of a free block.
1357   // With poisoning, the modification is detected.
1358   block->Poison();
1359   bytes_[kN / 2] = std::byte(0x7f);
1360   EXPECT_FALSE(block->IsValid());
1361 }
1362 
TEST_FOR_EACH_BLOCK_TYPE(CanGetBlockFromUsableSpace)1363 TEST_FOR_EACH_BLOCK_TYPE(CanGetBlockFromUsableSpace) {
1364   auto* block1 = Preallocate<BlockType>(
1365       bytes_,
1366       {
1367           {Preallocation::kSizeRemaining, Preallocation::kFree},
1368       });
1369 
1370   void* ptr = block1->UsableSpace();
1371   BlockType* block2 = BlockType::FromUsableSpace(ptr);
1372   EXPECT_EQ(block1, block2);
1373 }
1374 
TEST_FOR_EACH_BLOCK_TYPE(CanGetConstBlockFromUsableSpace)1375 TEST_FOR_EACH_BLOCK_TYPE(CanGetConstBlockFromUsableSpace) {
1376   const auto* block1 = Preallocate<BlockType>(
1377       bytes_,
1378       {
1379           {Preallocation::kSizeRemaining, Preallocation::kFree},
1380       });
1381 
1382   const void* ptr = block1->UsableSpace();
1383   const BlockType* block2 = BlockType::FromUsableSpace(ptr);
1384   EXPECT_EQ(block1, block2);
1385 }
1386 
TEST_FOR_EACH_BLOCK_TYPE(CanGetAlignmentFromUsedBlock)1387 TEST_FOR_EACH_BLOCK_TYPE(CanGetAlignmentFromUsedBlock) {
1388   constexpr Layout kLayout1(128, kAlign);
1389   constexpr Layout kLayout2(384, kAlign * 2);
1390 
1391   auto* block1 = Preallocate<BlockType>(
1392       bytes_,
1393       {
1394           {Preallocation::kSizeRemaining, Preallocation::kFree},
1395       });
1396 
1397   auto result = BlockType::AllocLast(std::move(block1), kLayout1);
1398   ASSERT_EQ(result.status(), pw::OkStatus());
1399   block1 = result.block();
1400 
1401   BlockType* block2 = block1->Prev();
1402   result = BlockType::AllocLast(std::move(block2), kLayout2);
1403   ASSERT_EQ(result.status(), pw::OkStatus());
1404   block2 = result.block();
1405 
1406   auto block1_layout = block1->RequestedLayout();
1407   auto block2_layout = block2->RequestedLayout();
1408   EXPECT_EQ(block1_layout->alignment(), kAlign);
1409   EXPECT_EQ(block2_layout->alignment(), kAlign * 2);
1410 }
1411 
TEST_FOR_EACH_BLOCK_TYPE(FreeBlocksHaveDefaultAlignment)1412 TEST_FOR_EACH_BLOCK_TYPE(FreeBlocksHaveDefaultAlignment) {
1413   constexpr Layout kLayout1(128, kAlign);
1414   constexpr Layout kLayout2(384, kAlign * 2);
1415 
1416   auto* block1 = Preallocate<BlockType>(
1417       bytes_,
1418       {
1419           {Preallocation::kSizeRemaining, Preallocation::kFree},
1420       });
1421 
1422   auto result = BlockType::AllocLast(std::move(block1), kLayout1);
1423   ASSERT_EQ(result.status(), pw::OkStatus());
1424   block1 = result.block();
1425 
1426   BlockType* block2 = block1->Prev();
1427   result = BlockType::AllocLast(std::move(block2), kLayout2);
1428   ASSERT_EQ(result.status(), pw::OkStatus());
1429 
1430   auto layout = block1->RequestedLayout();
1431   ASSERT_EQ(layout.status(), pw::OkStatus());
1432   EXPECT_EQ(layout->alignment(), kAlign);
1433 
1434   result = BlockType::Free(std::move(block1));
1435   ASSERT_EQ(result.status(), pw::OkStatus());
1436   EXPECT_EQ(result.prev(), BlockResultPrev::kUnchanged);
1437   EXPECT_EQ(result.next(), BlockResultNext::kMerged);
1438   block1 = result.block();
1439 
1440   layout = block1->RequestedLayout();
1441   EXPECT_EQ(layout.status(), pw::Status::FailedPrecondition());
1442 }
1443 
1444 }  // namespace
1445