xref: /llvm-project/libc/test/src/__support/block_test.cpp (revision 5db28679da38bee65feb55b803a23aceee568f44)
1f77ade0aSPiJoules //===-- Unittests for a block of memory -------------------------*- C++ -*-===//
2f77ade0aSPiJoules //
3f77ade0aSPiJoules // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4f77ade0aSPiJoules // See https://llvm.org/LICENSE.txt for license information.
5f77ade0aSPiJoules // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6f77ade0aSPiJoules //
7f77ade0aSPiJoules //===----------------------------------------------------------------------===//
8f77ade0aSPiJoules #include <stddef.h>
9f77ade0aSPiJoules 
10f77ade0aSPiJoules #include "src/__support/CPP/array.h"
113eebeb7eSPiJoules #include "src/__support/CPP/bit.h"
12f77ade0aSPiJoules #include "src/__support/CPP/span.h"
13f77ade0aSPiJoules #include "src/__support/block.h"
14f77ade0aSPiJoules #include "src/string/memcpy.h"
15f77ade0aSPiJoules #include "test/UnitTest/Test.h"
16f77ade0aSPiJoules 
17d121d71fSDaniel Thornburgh using LIBC_NAMESPACE::Block;
18f77ade0aSPiJoules using LIBC_NAMESPACE::cpp::array;
193eebeb7eSPiJoules using LIBC_NAMESPACE::cpp::bit_ceil;
20f77ade0aSPiJoules using LIBC_NAMESPACE::cpp::byte;
21f77ade0aSPiJoules using LIBC_NAMESPACE::cpp::span;
22f77ade0aSPiJoules 
23d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanCreateSingleAlignedBlock) {
24f77ade0aSPiJoules   constexpr size_t kN = 1024;
25cd92aedfSDaniel Thornburgh   alignas(max_align_t) array<byte, kN> bytes;
26f77ade0aSPiJoules 
27d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
28f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
29d121d71fSDaniel Thornburgh   Block *block = *result;
30f77ade0aSPiJoules 
3160de7dc8SDaniel Thornburgh   EXPECT_EQ(reinterpret_cast<uintptr_t>(block) % alignof(Block), size_t{0});
3260de7dc8SDaniel Thornburgh   EXPECT_TRUE(block->is_usable_space_aligned(alignof(max_align_t)));
3360de7dc8SDaniel Thornburgh 
34d121d71fSDaniel Thornburgh   Block *last = block->next();
35d121d71fSDaniel Thornburgh   ASSERT_NE(last, static_cast<Block *>(nullptr));
3660de7dc8SDaniel Thornburgh   EXPECT_EQ(reinterpret_cast<uintptr_t>(last) % alignof(Block), size_t{0});
3760de7dc8SDaniel Thornburgh 
3860de7dc8SDaniel Thornburgh   EXPECT_EQ(last->outer_size(), sizeof(Block));
398866fa15SDaniel Thornburgh   EXPECT_EQ(last->prev_free(), block);
408866fa15SDaniel Thornburgh   EXPECT_TRUE(last->used());
418866fa15SDaniel Thornburgh 
4260de7dc8SDaniel Thornburgh   size_t block_outer_size =
4360de7dc8SDaniel Thornburgh       reinterpret_cast<uintptr_t>(last) - reinterpret_cast<uintptr_t>(block);
4460de7dc8SDaniel Thornburgh   EXPECT_EQ(block->outer_size(), block_outer_size);
4560de7dc8SDaniel Thornburgh   EXPECT_EQ(block->inner_size(),
46859b4f19SDaniel Thornburgh             block_outer_size - sizeof(Block) + Block::PREV_FIELD_SIZE);
47d121d71fSDaniel Thornburgh   EXPECT_EQ(block->prev_free(), static_cast<Block *>(nullptr));
48f77ade0aSPiJoules   EXPECT_FALSE(block->used());
49f77ade0aSPiJoules }
50f77ade0aSPiJoules 
51d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanCreateUnalignedSingleBlock) {
52f77ade0aSPiJoules   constexpr size_t kN = 1024;
53f77ade0aSPiJoules 
54f77ade0aSPiJoules   // Force alignment, so we can un-force it below
55cd92aedfSDaniel Thornburgh   alignas(max_align_t) array<byte, kN> bytes;
56f77ade0aSPiJoules   span<byte> aligned(bytes);
57f77ade0aSPiJoules 
58d121d71fSDaniel Thornburgh   auto result = Block::init(aligned.subspan(1));
59f77ade0aSPiJoules   EXPECT_TRUE(result.has_value());
6060de7dc8SDaniel Thornburgh 
6160de7dc8SDaniel Thornburgh   Block *block = *result;
6260de7dc8SDaniel Thornburgh   EXPECT_EQ(reinterpret_cast<uintptr_t>(block) % alignof(Block), size_t{0});
6360de7dc8SDaniel Thornburgh   EXPECT_TRUE(block->is_usable_space_aligned(alignof(max_align_t)));
6460de7dc8SDaniel Thornburgh 
6560de7dc8SDaniel Thornburgh   Block *last = block->next();
6660de7dc8SDaniel Thornburgh   ASSERT_NE(last, static_cast<Block *>(nullptr));
6760de7dc8SDaniel Thornburgh   EXPECT_EQ(reinterpret_cast<uintptr_t>(last) % alignof(Block), size_t{0});
68f77ade0aSPiJoules }
69f77ade0aSPiJoules 
70d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CannotCreateTooSmallBlock) {
71f77ade0aSPiJoules   array<byte, 2> bytes;
72d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
73f77ade0aSPiJoules   EXPECT_FALSE(result.has_value());
74f77ade0aSPiJoules }
75f77ade0aSPiJoules 
76d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanSplitBlock) {
77f77ade0aSPiJoules   constexpr size_t kN = 1024;
78*5db28679SDaniel Thornburgh 
79*5db28679SDaniel Thornburgh   // Choose a split position such that the next block's usable space is 512
80*5db28679SDaniel Thornburgh   // bytes from this one's. This should be sufficient for any machine's
81*5db28679SDaniel Thornburgh   // alignment.
82*5db28679SDaniel Thornburgh   const size_t kSplitN = Block::inner_size(512);
83f77ade0aSPiJoules 
8460de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
85d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
86f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
87f77ade0aSPiJoules   auto *block1 = *result;
888866fa15SDaniel Thornburgh   size_t orig_size = block1->outer_size();
89f77ade0aSPiJoules 
903c210740SDaniel Thornburgh   result = block1->split(kSplitN);
91f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
92f77ade0aSPiJoules   auto *block2 = *result;
93f77ade0aSPiJoules 
94f77ade0aSPiJoules   EXPECT_EQ(block1->inner_size(), kSplitN);
95859b4f19SDaniel Thornburgh   EXPECT_EQ(block1->outer_size(),
96859b4f19SDaniel Thornburgh             kSplitN - Block::PREV_FIELD_SIZE + sizeof(Block));
97f77ade0aSPiJoules 
988866fa15SDaniel Thornburgh   EXPECT_EQ(block2->outer_size(), orig_size - block1->outer_size());
99f77ade0aSPiJoules   EXPECT_FALSE(block2->used());
10060de7dc8SDaniel Thornburgh   EXPECT_EQ(reinterpret_cast<uintptr_t>(block2) % alignof(Block), size_t{0});
10160de7dc8SDaniel Thornburgh   EXPECT_TRUE(block2->is_usable_space_aligned(alignof(max_align_t)));
102f77ade0aSPiJoules 
103f77ade0aSPiJoules   EXPECT_EQ(block1->next(), block2);
1048866fa15SDaniel Thornburgh   EXPECT_EQ(block2->prev_free(), block1);
105f77ade0aSPiJoules }
106f77ade0aSPiJoules 
107d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanSplitBlockUnaligned) {
108f77ade0aSPiJoules   constexpr size_t kN = 1024;
109f77ade0aSPiJoules 
11060de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
111d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
112f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
113d121d71fSDaniel Thornburgh   Block *block1 = *result;
1148866fa15SDaniel Thornburgh   size_t orig_size = block1->outer_size();
115f77ade0aSPiJoules 
116f77ade0aSPiJoules   constexpr size_t kSplitN = 513;
117f77ade0aSPiJoules 
1183c210740SDaniel Thornburgh   result = block1->split(kSplitN);
119f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
120d121d71fSDaniel Thornburgh   Block *block2 = *result;
121f77ade0aSPiJoules 
12260de7dc8SDaniel Thornburgh   EXPECT_GE(block1->inner_size(), kSplitN);
123f77ade0aSPiJoules 
1248866fa15SDaniel Thornburgh   EXPECT_EQ(block2->outer_size(), orig_size - block1->outer_size());
125f77ade0aSPiJoules   EXPECT_FALSE(block2->used());
12660de7dc8SDaniel Thornburgh   EXPECT_EQ(reinterpret_cast<uintptr_t>(block2) % alignof(Block), size_t{0});
12760de7dc8SDaniel Thornburgh   EXPECT_TRUE(block2->is_usable_space_aligned(alignof(max_align_t)));
128f77ade0aSPiJoules 
129f77ade0aSPiJoules   EXPECT_EQ(block1->next(), block2);
1308866fa15SDaniel Thornburgh   EXPECT_EQ(block2->prev_free(), block1);
131f77ade0aSPiJoules }
132f77ade0aSPiJoules 
133d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanSplitMidBlock) {
134f77ade0aSPiJoules   // split once, then split the original block again to ensure that the
135f77ade0aSPiJoules   // pointers get rewired properly.
136f77ade0aSPiJoules   // I.e.
137f77ade0aSPiJoules   // [[             BLOCK 1            ]]
138f77ade0aSPiJoules   // block1->split()
139f77ade0aSPiJoules   // [[       BLOCK1       ]][[ BLOCK2 ]]
140f77ade0aSPiJoules   // block1->split()
141f77ade0aSPiJoules   // [[ BLOCK1 ]][[ BLOCK3 ]][[ BLOCK2 ]]
142f77ade0aSPiJoules 
143f77ade0aSPiJoules   constexpr size_t kN = 1024;
144f77ade0aSPiJoules   constexpr size_t kSplit1 = 512;
145f77ade0aSPiJoules   constexpr size_t kSplit2 = 256;
146f77ade0aSPiJoules 
14760de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
148d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
149f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
150d121d71fSDaniel Thornburgh   Block *block1 = *result;
151f77ade0aSPiJoules 
1523c210740SDaniel Thornburgh   result = block1->split(kSplit1);
153f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
154d121d71fSDaniel Thornburgh   Block *block2 = *result;
155f77ade0aSPiJoules 
1563c210740SDaniel Thornburgh   result = block1->split(kSplit2);
157f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
158d121d71fSDaniel Thornburgh   Block *block3 = *result;
159f77ade0aSPiJoules 
160f77ade0aSPiJoules   EXPECT_EQ(block1->next(), block3);
1618866fa15SDaniel Thornburgh   EXPECT_EQ(block3->prev_free(), block1);
162f77ade0aSPiJoules   EXPECT_EQ(block3->next(), block2);
1638866fa15SDaniel Thornburgh   EXPECT_EQ(block2->prev_free(), block3);
164f77ade0aSPiJoules }
165f77ade0aSPiJoules 
166d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CannotSplitTooSmallBlock) {
167f77ade0aSPiJoules   constexpr size_t kN = 64;
168f77ade0aSPiJoules 
16960de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
170d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
171f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
172d121d71fSDaniel Thornburgh   Block *block = *result;
173f77ade0aSPiJoules 
1743c210740SDaniel Thornburgh   result = block->split(block->inner_size() + 1);
175f77ade0aSPiJoules   ASSERT_FALSE(result.has_value());
176f77ade0aSPiJoules }
177f77ade0aSPiJoules 
17860de7dc8SDaniel Thornburgh TEST(LlvmLibcBlockTest, CannotSplitBlockWithoutHeaderSpace) {
179f77ade0aSPiJoules   constexpr size_t kN = 1024;
180f77ade0aSPiJoules 
18160de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
182d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
183f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
184d121d71fSDaniel Thornburgh   Block *block = *result;
185f77ade0aSPiJoules 
18660de7dc8SDaniel Thornburgh   result = block->split(block->inner_size() - sizeof(Block) + 1);
18760de7dc8SDaniel Thornburgh   ASSERT_FALSE(result.has_value());
18860de7dc8SDaniel Thornburgh }
18960de7dc8SDaniel Thornburgh 
19060de7dc8SDaniel Thornburgh TEST(LlvmLibcBlockTest, CannotMakeBlockLargerInSplit) {
19160de7dc8SDaniel Thornburgh   // Ensure that we can't ask for more space than the block actually has...
19260de7dc8SDaniel Thornburgh   constexpr size_t kN = 1024;
19360de7dc8SDaniel Thornburgh 
19460de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
19560de7dc8SDaniel Thornburgh   auto result = Block::init(bytes);
19660de7dc8SDaniel Thornburgh   ASSERT_TRUE(result.has_value());
19760de7dc8SDaniel Thornburgh   Block *block = *result;
19860de7dc8SDaniel Thornburgh 
19960de7dc8SDaniel Thornburgh   result = block->split(block->inner_size() + 1);
200f77ade0aSPiJoules   ASSERT_FALSE(result.has_value());
201f77ade0aSPiJoules }
202f77ade0aSPiJoules 
203d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanMakeMinimalSizeFirstBlock) {
2048866fa15SDaniel Thornburgh   // This block does support splitting with minimal payload size.
205f77ade0aSPiJoules   constexpr size_t kN = 1024;
2068866fa15SDaniel Thornburgh 
20760de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
208d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
2098866fa15SDaniel Thornburgh   ASSERT_TRUE(result.has_value());
210d121d71fSDaniel Thornburgh   Block *block = *result;
2118866fa15SDaniel Thornburgh 
21260de7dc8SDaniel Thornburgh   result = block->split(0);
2138866fa15SDaniel Thornburgh   ASSERT_TRUE(result.has_value());
21460de7dc8SDaniel Thornburgh   EXPECT_LE(block->outer_size(), sizeof(Block) + alignof(max_align_t));
2158866fa15SDaniel Thornburgh }
2168866fa15SDaniel Thornburgh 
217d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanMakeMinimalSizeSecondBlock) {
2188866fa15SDaniel Thornburgh   // Likewise, the split block can be minimal-width.
2198866fa15SDaniel Thornburgh   constexpr size_t kN = 1024;
220f77ade0aSPiJoules 
22160de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
222d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
223f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
224d121d71fSDaniel Thornburgh   Block *block1 = *result;
225f77ade0aSPiJoules 
22660de7dc8SDaniel Thornburgh   result = block1->split(Block::prev_possible_block_start(
22760de7dc8SDaniel Thornburgh                              reinterpret_cast<uintptr_t>(block1->next())) -
22860de7dc8SDaniel Thornburgh                          reinterpret_cast<uintptr_t>(block1->usable_space()) +
229859b4f19SDaniel Thornburgh                          Block::PREV_FIELD_SIZE);
230f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
23160de7dc8SDaniel Thornburgh   EXPECT_LE((*result)->outer_size(), sizeof(Block) + alignof(max_align_t));
232f77ade0aSPiJoules }
233f77ade0aSPiJoules 
234d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanMarkBlockUsed) {
235f77ade0aSPiJoules   constexpr size_t kN = 1024;
236f77ade0aSPiJoules 
23760de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
238d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
239f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
240d121d71fSDaniel Thornburgh   Block *block = *result;
2418866fa15SDaniel Thornburgh   size_t orig_size = block->outer_size();
242f77ade0aSPiJoules 
243f77ade0aSPiJoules   block->mark_used();
244f77ade0aSPiJoules   EXPECT_TRUE(block->used());
2458866fa15SDaniel Thornburgh   EXPECT_EQ(block->outer_size(), orig_size);
246f77ade0aSPiJoules 
247f77ade0aSPiJoules   block->mark_free();
248f77ade0aSPiJoules   EXPECT_FALSE(block->used());
249f77ade0aSPiJoules }
250f77ade0aSPiJoules 
251d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CannotSplitUsedBlock) {
252f77ade0aSPiJoules   constexpr size_t kN = 1024;
253f77ade0aSPiJoules   constexpr size_t kSplitN = 512;
254f77ade0aSPiJoules 
25560de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
256d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
257f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
258d121d71fSDaniel Thornburgh   Block *block = *result;
259f77ade0aSPiJoules 
260f77ade0aSPiJoules   block->mark_used();
2613c210740SDaniel Thornburgh   result = block->split(kSplitN);
262f77ade0aSPiJoules   ASSERT_FALSE(result.has_value());
263f77ade0aSPiJoules }
264f77ade0aSPiJoules 
265d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanMergeWithNextBlock) {
266f77ade0aSPiJoules   // Do the three way merge from "CanSplitMidBlock", and let's
267f77ade0aSPiJoules   // merge block 3 and 2
268f77ade0aSPiJoules   constexpr size_t kN = 1024;
26960de7dc8SDaniel Thornburgh   constexpr size_t kSplit1 = 512;
27060de7dc8SDaniel Thornburgh   constexpr size_t kSplit2 = 256;
27160de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
272d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
273f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
274d121d71fSDaniel Thornburgh   Block *block1 = *result;
27560de7dc8SDaniel Thornburgh   size_t total_size = block1->outer_size();
276f77ade0aSPiJoules 
2773c210740SDaniel Thornburgh   result = block1->split(kSplit1);
278f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
279f77ade0aSPiJoules 
2803c210740SDaniel Thornburgh   result = block1->split(kSplit2);
28160de7dc8SDaniel Thornburgh   size_t block1_size = block1->outer_size();
282f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
283d121d71fSDaniel Thornburgh   Block *block3 = *result;
284f77ade0aSPiJoules 
2853c210740SDaniel Thornburgh   EXPECT_TRUE(block3->merge_next());
286f77ade0aSPiJoules 
287f77ade0aSPiJoules   EXPECT_EQ(block1->next(), block3);
2888866fa15SDaniel Thornburgh   EXPECT_EQ(block3->prev_free(), block1);
28960de7dc8SDaniel Thornburgh   EXPECT_EQ(block1->outer_size(), block1_size);
29060de7dc8SDaniel Thornburgh   EXPECT_EQ(block3->outer_size(), total_size - block1->outer_size());
291f77ade0aSPiJoules }
292f77ade0aSPiJoules 
293d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CannotMergeWithFirstOrLastBlock) {
294f77ade0aSPiJoules   constexpr size_t kN = 1024;
295f77ade0aSPiJoules   constexpr size_t kSplitN = 512;
296f77ade0aSPiJoules 
29760de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
298d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
299f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
300d121d71fSDaniel Thornburgh   Block *block1 = *result;
301f77ade0aSPiJoules 
302f77ade0aSPiJoules   // Do a split, just to check that the checks on next/prev are different...
3033c210740SDaniel Thornburgh   result = block1->split(kSplitN);
304f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
305d121d71fSDaniel Thornburgh   Block *block2 = *result;
306f77ade0aSPiJoules 
3073c210740SDaniel Thornburgh   EXPECT_FALSE(block2->merge_next());
308f77ade0aSPiJoules }
309f77ade0aSPiJoules 
310d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CannotMergeUsedBlock) {
311f77ade0aSPiJoules   constexpr size_t kN = 1024;
312f77ade0aSPiJoules   constexpr size_t kSplitN = 512;
313f77ade0aSPiJoules 
31460de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
315d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
316f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
317d121d71fSDaniel Thornburgh   Block *block = *result;
318f77ade0aSPiJoules 
319f77ade0aSPiJoules   // Do a split, just to check that the checks on next/prev are different...
3203c210740SDaniel Thornburgh   result = block->split(kSplitN);
321f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
322f77ade0aSPiJoules 
323f77ade0aSPiJoules   block->mark_used();
3243c210740SDaniel Thornburgh   EXPECT_FALSE(block->merge_next());
325f77ade0aSPiJoules }
326f77ade0aSPiJoules 
327d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanGetBlockFromUsableSpace) {
32860de7dc8SDaniel Thornburgh   array<byte, 1024> bytes;
329d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
330f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
331d121d71fSDaniel Thornburgh   Block *block1 = *result;
332f77ade0aSPiJoules 
333f77ade0aSPiJoules   void *ptr = block1->usable_space();
334d121d71fSDaniel Thornburgh   Block *block2 = Block::from_usable_space(ptr);
335f77ade0aSPiJoules   EXPECT_EQ(block1, block2);
336f77ade0aSPiJoules }
337f77ade0aSPiJoules 
338d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanGetConstBlockFromUsableSpace) {
339f77ade0aSPiJoules   constexpr size_t kN = 1024;
340f77ade0aSPiJoules 
341f77ade0aSPiJoules   array<byte, kN> bytes{};
342d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
343f77ade0aSPiJoules   ASSERT_TRUE(result.has_value());
344d121d71fSDaniel Thornburgh   const Block *block1 = *result;
345f77ade0aSPiJoules 
346f77ade0aSPiJoules   const void *ptr = block1->usable_space();
347d121d71fSDaniel Thornburgh   const Block *block2 = Block::from_usable_space(ptr);
348f77ade0aSPiJoules   EXPECT_EQ(block1, block2);
349f77ade0aSPiJoules }
3503eebeb7eSPiJoules 
35160de7dc8SDaniel Thornburgh TEST(LlvmLibcBlockTest, Allocate) {
35260de7dc8SDaniel Thornburgh   constexpr size_t kN = 1024;
3533eebeb7eSPiJoules 
3543eebeb7eSPiJoules   // Ensure we can allocate everything up to the block size within this block.
35560de7dc8SDaniel Thornburgh   for (size_t i = 0; i < kN; ++i) {
35660de7dc8SDaniel Thornburgh     array<byte, kN> bytes;
357d121d71fSDaniel Thornburgh     auto result = Block::init(bytes);
3583eebeb7eSPiJoules     ASSERT_TRUE(result.has_value());
359d121d71fSDaniel Thornburgh     Block *block = *result;
3603eebeb7eSPiJoules 
36160de7dc8SDaniel Thornburgh     if (i > block->inner_size())
36260de7dc8SDaniel Thornburgh       continue;
3633eebeb7eSPiJoules 
36460de7dc8SDaniel Thornburgh     auto info = Block::allocate(block, alignof(max_align_t), i);
365d121d71fSDaniel Thornburgh     EXPECT_NE(info.block, static_cast<Block *>(nullptr));
3663eebeb7eSPiJoules   }
3673eebeb7eSPiJoules 
36860de7dc8SDaniel Thornburgh   // Ensure we can allocate a byte at every guaranteeable alignment.
36960de7dc8SDaniel Thornburgh   for (size_t i = 1; i < kN / alignof(max_align_t); ++i) {
37060de7dc8SDaniel Thornburgh     array<byte, kN> bytes;
371d121d71fSDaniel Thornburgh     auto result = Block::init(bytes);
3723eebeb7eSPiJoules     ASSERT_TRUE(result.has_value());
373d121d71fSDaniel Thornburgh     Block *block = *result;
3743eebeb7eSPiJoules 
37560de7dc8SDaniel Thornburgh     size_t alignment = i * alignof(max_align_t);
37660de7dc8SDaniel Thornburgh     if (Block::min_size_for_allocation(alignment, 1) > block->inner_size())
37760de7dc8SDaniel Thornburgh       continue;
37860de7dc8SDaniel Thornburgh 
37960de7dc8SDaniel Thornburgh     auto info = Block::allocate(block, alignment, 1);
380d121d71fSDaniel Thornburgh     EXPECT_NE(info.block, static_cast<Block *>(nullptr));
3813eebeb7eSPiJoules   }
38260de7dc8SDaniel Thornburgh }
3833eebeb7eSPiJoules 
384d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, AllocateAlreadyAligned) {
3853eebeb7eSPiJoules   constexpr size_t kN = 1024;
3863eebeb7eSPiJoules 
38760de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
388d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
3893eebeb7eSPiJoules   ASSERT_TRUE(result.has_value());
390d121d71fSDaniel Thornburgh   Block *block = *result;
39160de7dc8SDaniel Thornburgh   uintptr_t orig_end = reinterpret_cast<uintptr_t>(block) + block->outer_size();
3923eebeb7eSPiJoules 
393859b4f19SDaniel Thornburgh   constexpr size_t SIZE = Block::PREV_FIELD_SIZE + 1;
3943eebeb7eSPiJoules 
3953eebeb7eSPiJoules   auto [aligned_block, prev, next] =
39660de7dc8SDaniel Thornburgh       Block::allocate(block, alignof(max_align_t), SIZE);
3973eebeb7eSPiJoules 
3983eebeb7eSPiJoules   // Since this is already aligned, there should be no previous block.
399d121d71fSDaniel Thornburgh   EXPECT_EQ(prev, static_cast<Block *>(nullptr));
4003eebeb7eSPiJoules 
40160de7dc8SDaniel Thornburgh   // Ensure we the block is aligned and large enough.
402d121d71fSDaniel Thornburgh   EXPECT_NE(aligned_block, static_cast<Block *>(nullptr));
40360de7dc8SDaniel Thornburgh   EXPECT_TRUE(aligned_block->is_usable_space_aligned(alignof(max_align_t)));
40460de7dc8SDaniel Thornburgh   EXPECT_GE(aligned_block->inner_size(), SIZE);
4053eebeb7eSPiJoules 
4063eebeb7eSPiJoules   // Check the next block.
407d121d71fSDaniel Thornburgh   EXPECT_NE(next, static_cast<Block *>(nullptr));
4083eebeb7eSPiJoules   EXPECT_EQ(aligned_block->next(), next);
40960de7dc8SDaniel Thornburgh   EXPECT_EQ(reinterpret_cast<uintptr_t>(next) + next->outer_size(), orig_end);
4103eebeb7eSPiJoules }
4113eebeb7eSPiJoules 
412d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, AllocateNeedsAlignment) {
4133eebeb7eSPiJoules   constexpr size_t kN = 1024;
4143eebeb7eSPiJoules 
41560de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
416d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
4173eebeb7eSPiJoules   ASSERT_TRUE(result.has_value());
418d121d71fSDaniel Thornburgh   Block *block = *result;
4193eebeb7eSPiJoules 
42060de7dc8SDaniel Thornburgh   uintptr_t orig_end = reinterpret_cast<uintptr_t>(block) + block->outer_size();
4213eebeb7eSPiJoules 
4223eebeb7eSPiJoules   // Now pick an alignment such that the usable space is not already aligned to
4233eebeb7eSPiJoules   // it. We want to explicitly test that the block will split into one before
4243eebeb7eSPiJoules   // it.
42560de7dc8SDaniel Thornburgh   size_t alignment = alignof(max_align_t);
42660de7dc8SDaniel Thornburgh   while (block->is_usable_space_aligned(alignment))
42760de7dc8SDaniel Thornburgh     alignment += alignof(max_align_t);
4283eebeb7eSPiJoules 
42960de7dc8SDaniel Thornburgh   auto [aligned_block, prev, next] = Block::allocate(block, alignment, 10);
4303eebeb7eSPiJoules 
4313eebeb7eSPiJoules   // Check the previous block was created appropriately. Since this block is the
4323eebeb7eSPiJoules   // first block, a new one should be made before this.
433d121d71fSDaniel Thornburgh   EXPECT_NE(prev, static_cast<Block *>(nullptr));
4348866fa15SDaniel Thornburgh   EXPECT_EQ(aligned_block->prev_free(), prev);
4353eebeb7eSPiJoules   EXPECT_EQ(prev->next(), aligned_block);
4363eebeb7eSPiJoules   EXPECT_EQ(prev->outer_size(), reinterpret_cast<uintptr_t>(aligned_block) -
4373eebeb7eSPiJoules                                     reinterpret_cast<uintptr_t>(prev));
4383eebeb7eSPiJoules 
4393eebeb7eSPiJoules   // Ensure we the block is aligned and the size we expect.
440d121d71fSDaniel Thornburgh   EXPECT_NE(next, static_cast<Block *>(nullptr));
44160de7dc8SDaniel Thornburgh   EXPECT_TRUE(aligned_block->is_usable_space_aligned(alignment));
4423eebeb7eSPiJoules 
4433eebeb7eSPiJoules   // Check the next block.
444d121d71fSDaniel Thornburgh   EXPECT_NE(next, static_cast<Block *>(nullptr));
4453eebeb7eSPiJoules   EXPECT_EQ(aligned_block->next(), next);
44660de7dc8SDaniel Thornburgh   EXPECT_EQ(reinterpret_cast<uintptr_t>(next) + next->outer_size(), orig_end);
4473eebeb7eSPiJoules }
4483eebeb7eSPiJoules 
449d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, PreviousBlockMergedIfNotFirst) {
4503eebeb7eSPiJoules   constexpr size_t kN = 1024;
4513eebeb7eSPiJoules 
45260de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
453d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
4543eebeb7eSPiJoules   ASSERT_TRUE(result.has_value());
455d121d71fSDaniel Thornburgh   Block *block = *result;
4563eebeb7eSPiJoules 
4573eebeb7eSPiJoules   // Split the block roughly halfway and work on the second half.
4583c210740SDaniel Thornburgh   auto result2 = block->split(kN / 2);
4593eebeb7eSPiJoules   ASSERT_TRUE(result2.has_value());
460d121d71fSDaniel Thornburgh   Block *newblock = *result2;
4618866fa15SDaniel Thornburgh   ASSERT_EQ(newblock->prev_free(), block);
4623eebeb7eSPiJoules   size_t old_prev_size = block->outer_size();
4633eebeb7eSPiJoules 
4643eebeb7eSPiJoules   // Now pick an alignment such that the usable space is not already aligned to
4653eebeb7eSPiJoules   // it. We want to explicitly test that the block will split into one before
4663eebeb7eSPiJoules   // it.
46760de7dc8SDaniel Thornburgh   size_t alignment = alignof(max_align_t);
46860de7dc8SDaniel Thornburgh   while (newblock->is_usable_space_aligned(alignment))
46960de7dc8SDaniel Thornburgh     alignment += alignof(max_align_t);
4703eebeb7eSPiJoules 
4713eebeb7eSPiJoules   // Ensure we can allocate in the new block.
47260de7dc8SDaniel Thornburgh   auto [aligned_block, prev, next] = Block::allocate(newblock, alignment, 1);
4733eebeb7eSPiJoules 
4743eebeb7eSPiJoules   // Now there should be no new previous block. Instead, the padding we did
4753eebeb7eSPiJoules   // create should be merged into the original previous block.
476d121d71fSDaniel Thornburgh   EXPECT_EQ(prev, static_cast<Block *>(nullptr));
4778866fa15SDaniel Thornburgh   EXPECT_EQ(aligned_block->prev_free(), block);
4783eebeb7eSPiJoules   EXPECT_EQ(block->next(), aligned_block);
4793eebeb7eSPiJoules   EXPECT_GT(block->outer_size(), old_prev_size);
4803eebeb7eSPiJoules }
4813eebeb7eSPiJoules 
482d121d71fSDaniel Thornburgh TEST(LlvmLibcBlockTest, CanRemergeBlockAllocations) {
4833eebeb7eSPiJoules   // Finally to ensure we made the split blocks correctly via allocate. We
4843eebeb7eSPiJoules   // should be able to reconstruct the original block from the blocklets.
4853eebeb7eSPiJoules   //
4863eebeb7eSPiJoules   // This is the same setup as with the `AllocateNeedsAlignment` test case.
4873eebeb7eSPiJoules   constexpr size_t kN = 1024;
4883eebeb7eSPiJoules 
48960de7dc8SDaniel Thornburgh   array<byte, kN> bytes;
490d121d71fSDaniel Thornburgh   auto result = Block::init(bytes);
4913eebeb7eSPiJoules   ASSERT_TRUE(result.has_value());
492d121d71fSDaniel Thornburgh   Block *block = *result;
49360de7dc8SDaniel Thornburgh 
49460de7dc8SDaniel Thornburgh   Block *orig_block = block;
49560de7dc8SDaniel Thornburgh   size_t orig_size = orig_block->outer_size();
49660de7dc8SDaniel Thornburgh 
497d121d71fSDaniel Thornburgh   Block *last = block->next();
4983eebeb7eSPiJoules 
499d121d71fSDaniel Thornburgh   ASSERT_EQ(block->prev_free(), static_cast<Block *>(nullptr));
5003eebeb7eSPiJoules 
5013eebeb7eSPiJoules   // Now pick an alignment such that the usable space is not already aligned to
5023eebeb7eSPiJoules   // it. We want to explicitly test that the block will split into one before
5033eebeb7eSPiJoules   // it.
50460de7dc8SDaniel Thornburgh   size_t alignment = alignof(max_align_t);
50560de7dc8SDaniel Thornburgh   while (block->is_usable_space_aligned(alignment))
50660de7dc8SDaniel Thornburgh     alignment += alignof(max_align_t);
5073eebeb7eSPiJoules 
50860de7dc8SDaniel Thornburgh   auto [aligned_block, prev, next] = Block::allocate(block, alignment, 1);
5093eebeb7eSPiJoules 
5103eebeb7eSPiJoules   // Check we have the appropriate blocks.
511d121d71fSDaniel Thornburgh   ASSERT_NE(prev, static_cast<Block *>(nullptr));
5128866fa15SDaniel Thornburgh   ASSERT_EQ(aligned_block->prev_free(), prev);
513d121d71fSDaniel Thornburgh   EXPECT_NE(next, static_cast<Block *>(nullptr));
5143eebeb7eSPiJoules   EXPECT_EQ(aligned_block->next(), next);
5158866fa15SDaniel Thornburgh   EXPECT_EQ(next->next(), last);
5163eebeb7eSPiJoules 
5173eebeb7eSPiJoules   // Now check for successful merges.
5183c210740SDaniel Thornburgh   EXPECT_TRUE(prev->merge_next());
5193eebeb7eSPiJoules   EXPECT_EQ(prev->next(), next);
5203c210740SDaniel Thornburgh   EXPECT_TRUE(prev->merge_next());
5218866fa15SDaniel Thornburgh   EXPECT_EQ(prev->next(), last);
5223eebeb7eSPiJoules 
5233eebeb7eSPiJoules   // We should have the original buffer.
52460de7dc8SDaniel Thornburgh   EXPECT_EQ(prev, orig_block);
52560de7dc8SDaniel Thornburgh   EXPECT_EQ(prev->outer_size(), orig_size);
5263eebeb7eSPiJoules }
527