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