1 //===-- Unittests for a block of memory -------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 #include <stddef.h> 9 10 #include "src/__support/CPP/array.h" 11 #include "src/__support/CPP/bit.h" 12 #include "src/__support/CPP/span.h" 13 #include "src/__support/block.h" 14 #include "src/string/memcpy.h" 15 #include "test/UnitTest/Test.h" 16 17 using LIBC_NAMESPACE::Block; 18 using LIBC_NAMESPACE::cpp::array; 19 using LIBC_NAMESPACE::cpp::bit_ceil; 20 using LIBC_NAMESPACE::cpp::byte; 21 using LIBC_NAMESPACE::cpp::span; 22 23 TEST(LlvmLibcBlockTest, CanCreateSingleAlignedBlock) { 24 constexpr size_t kN = 1024; 25 alignas(max_align_t) array<byte, kN> bytes; 26 27 auto result = Block::init(bytes); 28 ASSERT_TRUE(result.has_value()); 29 Block *block = *result; 30 31 EXPECT_EQ(reinterpret_cast<uintptr_t>(block) % alignof(Block), size_t{0}); 32 EXPECT_TRUE(block->is_usable_space_aligned(alignof(max_align_t))); 33 34 Block *last = block->next(); 35 ASSERT_NE(last, static_cast<Block *>(nullptr)); 36 EXPECT_EQ(reinterpret_cast<uintptr_t>(last) % alignof(Block), size_t{0}); 37 38 EXPECT_EQ(last->outer_size(), sizeof(Block)); 39 EXPECT_EQ(last->prev_free(), block); 40 EXPECT_TRUE(last->used()); 41 42 size_t block_outer_size = 43 reinterpret_cast<uintptr_t>(last) - reinterpret_cast<uintptr_t>(block); 44 EXPECT_EQ(block->outer_size(), block_outer_size); 45 EXPECT_EQ(block->inner_size(), 46 block_outer_size - sizeof(Block) + Block::PREV_FIELD_SIZE); 47 EXPECT_EQ(block->prev_free(), static_cast<Block *>(nullptr)); 48 EXPECT_FALSE(block->used()); 49 } 50 51 TEST(LlvmLibcBlockTest, CanCreateUnalignedSingleBlock) { 52 constexpr size_t kN = 1024; 53 54 // Force alignment, so we can un-force it below 55 alignas(max_align_t) array<byte, kN> bytes; 56 span<byte> aligned(bytes); 57 58 auto result = Block::init(aligned.subspan(1)); 59 EXPECT_TRUE(result.has_value()); 60 61 Block *block = *result; 62 EXPECT_EQ(reinterpret_cast<uintptr_t>(block) % alignof(Block), size_t{0}); 63 EXPECT_TRUE(block->is_usable_space_aligned(alignof(max_align_t))); 64 65 Block *last = block->next(); 66 ASSERT_NE(last, static_cast<Block *>(nullptr)); 67 EXPECT_EQ(reinterpret_cast<uintptr_t>(last) % alignof(Block), size_t{0}); 68 } 69 70 TEST(LlvmLibcBlockTest, CannotCreateTooSmallBlock) { 71 array<byte, 2> bytes; 72 auto result = Block::init(bytes); 73 EXPECT_FALSE(result.has_value()); 74 } 75 76 TEST(LlvmLibcBlockTest, CanSplitBlock) { 77 constexpr size_t kN = 1024; 78 79 // Choose a split position such that the next block's usable space is 512 80 // bytes from this one's. This should be sufficient for any machine's 81 // alignment. 82 const size_t kSplitN = Block::inner_size(512); 83 84 array<byte, kN> bytes; 85 auto result = Block::init(bytes); 86 ASSERT_TRUE(result.has_value()); 87 auto *block1 = *result; 88 size_t orig_size = block1->outer_size(); 89 90 result = block1->split(kSplitN); 91 ASSERT_TRUE(result.has_value()); 92 auto *block2 = *result; 93 94 EXPECT_EQ(block1->inner_size(), kSplitN); 95 EXPECT_EQ(block1->outer_size(), 96 kSplitN - Block::PREV_FIELD_SIZE + sizeof(Block)); 97 98 EXPECT_EQ(block2->outer_size(), orig_size - block1->outer_size()); 99 EXPECT_FALSE(block2->used()); 100 EXPECT_EQ(reinterpret_cast<uintptr_t>(block2) % alignof(Block), size_t{0}); 101 EXPECT_TRUE(block2->is_usable_space_aligned(alignof(max_align_t))); 102 103 EXPECT_EQ(block1->next(), block2); 104 EXPECT_EQ(block2->prev_free(), block1); 105 } 106 107 TEST(LlvmLibcBlockTest, CanSplitBlockUnaligned) { 108 constexpr size_t kN = 1024; 109 110 array<byte, kN> bytes; 111 auto result = Block::init(bytes); 112 ASSERT_TRUE(result.has_value()); 113 Block *block1 = *result; 114 size_t orig_size = block1->outer_size(); 115 116 constexpr size_t kSplitN = 513; 117 118 result = block1->split(kSplitN); 119 ASSERT_TRUE(result.has_value()); 120 Block *block2 = *result; 121 122 EXPECT_GE(block1->inner_size(), kSplitN); 123 124 EXPECT_EQ(block2->outer_size(), orig_size - block1->outer_size()); 125 EXPECT_FALSE(block2->used()); 126 EXPECT_EQ(reinterpret_cast<uintptr_t>(block2) % alignof(Block), size_t{0}); 127 EXPECT_TRUE(block2->is_usable_space_aligned(alignof(max_align_t))); 128 129 EXPECT_EQ(block1->next(), block2); 130 EXPECT_EQ(block2->prev_free(), block1); 131 } 132 133 TEST(LlvmLibcBlockTest, CanSplitMidBlock) { 134 // split once, then split the original block again to ensure that the 135 // pointers get rewired properly. 136 // I.e. 137 // [[ BLOCK 1 ]] 138 // block1->split() 139 // [[ BLOCK1 ]][[ BLOCK2 ]] 140 // block1->split() 141 // [[ BLOCK1 ]][[ BLOCK3 ]][[ BLOCK2 ]] 142 143 constexpr size_t kN = 1024; 144 constexpr size_t kSplit1 = 512; 145 constexpr size_t kSplit2 = 256; 146 147 array<byte, kN> bytes; 148 auto result = Block::init(bytes); 149 ASSERT_TRUE(result.has_value()); 150 Block *block1 = *result; 151 152 result = block1->split(kSplit1); 153 ASSERT_TRUE(result.has_value()); 154 Block *block2 = *result; 155 156 result = block1->split(kSplit2); 157 ASSERT_TRUE(result.has_value()); 158 Block *block3 = *result; 159 160 EXPECT_EQ(block1->next(), block3); 161 EXPECT_EQ(block3->prev_free(), block1); 162 EXPECT_EQ(block3->next(), block2); 163 EXPECT_EQ(block2->prev_free(), block3); 164 } 165 166 TEST(LlvmLibcBlockTest, CannotSplitTooSmallBlock) { 167 constexpr size_t kN = 64; 168 169 array<byte, kN> bytes; 170 auto result = Block::init(bytes); 171 ASSERT_TRUE(result.has_value()); 172 Block *block = *result; 173 174 result = block->split(block->inner_size() + 1); 175 ASSERT_FALSE(result.has_value()); 176 } 177 178 TEST(LlvmLibcBlockTest, CannotSplitBlockWithoutHeaderSpace) { 179 constexpr size_t kN = 1024; 180 181 array<byte, kN> bytes; 182 auto result = Block::init(bytes); 183 ASSERT_TRUE(result.has_value()); 184 Block *block = *result; 185 186 result = block->split(block->inner_size() - sizeof(Block) + 1); 187 ASSERT_FALSE(result.has_value()); 188 } 189 190 TEST(LlvmLibcBlockTest, CannotMakeBlockLargerInSplit) { 191 // Ensure that we can't ask for more space than the block actually has... 192 constexpr size_t kN = 1024; 193 194 array<byte, kN> bytes; 195 auto result = Block::init(bytes); 196 ASSERT_TRUE(result.has_value()); 197 Block *block = *result; 198 199 result = block->split(block->inner_size() + 1); 200 ASSERT_FALSE(result.has_value()); 201 } 202 203 TEST(LlvmLibcBlockTest, CanMakeMinimalSizeFirstBlock) { 204 // This block does support splitting with minimal payload size. 205 constexpr size_t kN = 1024; 206 207 array<byte, kN> bytes; 208 auto result = Block::init(bytes); 209 ASSERT_TRUE(result.has_value()); 210 Block *block = *result; 211 212 result = block->split(0); 213 ASSERT_TRUE(result.has_value()); 214 EXPECT_LE(block->outer_size(), sizeof(Block) + alignof(max_align_t)); 215 } 216 217 TEST(LlvmLibcBlockTest, CanMakeMinimalSizeSecondBlock) { 218 // Likewise, the split block can be minimal-width. 219 constexpr size_t kN = 1024; 220 221 array<byte, kN> bytes; 222 auto result = Block::init(bytes); 223 ASSERT_TRUE(result.has_value()); 224 Block *block1 = *result; 225 226 result = block1->split(Block::prev_possible_block_start( 227 reinterpret_cast<uintptr_t>(block1->next())) - 228 reinterpret_cast<uintptr_t>(block1->usable_space()) + 229 Block::PREV_FIELD_SIZE); 230 ASSERT_TRUE(result.has_value()); 231 EXPECT_LE((*result)->outer_size(), sizeof(Block) + alignof(max_align_t)); 232 } 233 234 TEST(LlvmLibcBlockTest, CanMarkBlockUsed) { 235 constexpr size_t kN = 1024; 236 237 array<byte, kN> bytes; 238 auto result = Block::init(bytes); 239 ASSERT_TRUE(result.has_value()); 240 Block *block = *result; 241 size_t orig_size = block->outer_size(); 242 243 block->mark_used(); 244 EXPECT_TRUE(block->used()); 245 EXPECT_EQ(block->outer_size(), orig_size); 246 247 block->mark_free(); 248 EXPECT_FALSE(block->used()); 249 } 250 251 TEST(LlvmLibcBlockTest, CannotSplitUsedBlock) { 252 constexpr size_t kN = 1024; 253 constexpr size_t kSplitN = 512; 254 255 array<byte, kN> bytes; 256 auto result = Block::init(bytes); 257 ASSERT_TRUE(result.has_value()); 258 Block *block = *result; 259 260 block->mark_used(); 261 result = block->split(kSplitN); 262 ASSERT_FALSE(result.has_value()); 263 } 264 265 TEST(LlvmLibcBlockTest, CanMergeWithNextBlock) { 266 // Do the three way merge from "CanSplitMidBlock", and let's 267 // merge block 3 and 2 268 constexpr size_t kN = 1024; 269 constexpr size_t kSplit1 = 512; 270 constexpr size_t kSplit2 = 256; 271 array<byte, kN> bytes; 272 auto result = Block::init(bytes); 273 ASSERT_TRUE(result.has_value()); 274 Block *block1 = *result; 275 size_t total_size = block1->outer_size(); 276 277 result = block1->split(kSplit1); 278 ASSERT_TRUE(result.has_value()); 279 280 result = block1->split(kSplit2); 281 size_t block1_size = block1->outer_size(); 282 ASSERT_TRUE(result.has_value()); 283 Block *block3 = *result; 284 285 EXPECT_TRUE(block3->merge_next()); 286 287 EXPECT_EQ(block1->next(), block3); 288 EXPECT_EQ(block3->prev_free(), block1); 289 EXPECT_EQ(block1->outer_size(), block1_size); 290 EXPECT_EQ(block3->outer_size(), total_size - block1->outer_size()); 291 } 292 293 TEST(LlvmLibcBlockTest, CannotMergeWithFirstOrLastBlock) { 294 constexpr size_t kN = 1024; 295 constexpr size_t kSplitN = 512; 296 297 array<byte, kN> bytes; 298 auto result = Block::init(bytes); 299 ASSERT_TRUE(result.has_value()); 300 Block *block1 = *result; 301 302 // Do a split, just to check that the checks on next/prev are different... 303 result = block1->split(kSplitN); 304 ASSERT_TRUE(result.has_value()); 305 Block *block2 = *result; 306 307 EXPECT_FALSE(block2->merge_next()); 308 } 309 310 TEST(LlvmLibcBlockTest, CannotMergeUsedBlock) { 311 constexpr size_t kN = 1024; 312 constexpr size_t kSplitN = 512; 313 314 array<byte, kN> bytes; 315 auto result = Block::init(bytes); 316 ASSERT_TRUE(result.has_value()); 317 Block *block = *result; 318 319 // Do a split, just to check that the checks on next/prev are different... 320 result = block->split(kSplitN); 321 ASSERT_TRUE(result.has_value()); 322 323 block->mark_used(); 324 EXPECT_FALSE(block->merge_next()); 325 } 326 327 TEST(LlvmLibcBlockTest, CanGetBlockFromUsableSpace) { 328 array<byte, 1024> bytes; 329 auto result = Block::init(bytes); 330 ASSERT_TRUE(result.has_value()); 331 Block *block1 = *result; 332 333 void *ptr = block1->usable_space(); 334 Block *block2 = Block::from_usable_space(ptr); 335 EXPECT_EQ(block1, block2); 336 } 337 338 TEST(LlvmLibcBlockTest, CanGetConstBlockFromUsableSpace) { 339 constexpr size_t kN = 1024; 340 341 array<byte, kN> bytes{}; 342 auto result = Block::init(bytes); 343 ASSERT_TRUE(result.has_value()); 344 const Block *block1 = *result; 345 346 const void *ptr = block1->usable_space(); 347 const Block *block2 = Block::from_usable_space(ptr); 348 EXPECT_EQ(block1, block2); 349 } 350 351 TEST(LlvmLibcBlockTest, Allocate) { 352 constexpr size_t kN = 1024; 353 354 // Ensure we can allocate everything up to the block size within this block. 355 for (size_t i = 0; i < kN; ++i) { 356 array<byte, kN> bytes; 357 auto result = Block::init(bytes); 358 ASSERT_TRUE(result.has_value()); 359 Block *block = *result; 360 361 if (i > block->inner_size()) 362 continue; 363 364 auto info = Block::allocate(block, alignof(max_align_t), i); 365 EXPECT_NE(info.block, static_cast<Block *>(nullptr)); 366 } 367 368 // Ensure we can allocate a byte at every guaranteeable alignment. 369 for (size_t i = 1; i < kN / alignof(max_align_t); ++i) { 370 array<byte, kN> bytes; 371 auto result = Block::init(bytes); 372 ASSERT_TRUE(result.has_value()); 373 Block *block = *result; 374 375 size_t alignment = i * alignof(max_align_t); 376 if (Block::min_size_for_allocation(alignment, 1) > block->inner_size()) 377 continue; 378 379 auto info = Block::allocate(block, alignment, 1); 380 EXPECT_NE(info.block, static_cast<Block *>(nullptr)); 381 } 382 } 383 384 TEST(LlvmLibcBlockTest, AllocateAlreadyAligned) { 385 constexpr size_t kN = 1024; 386 387 array<byte, kN> bytes; 388 auto result = Block::init(bytes); 389 ASSERT_TRUE(result.has_value()); 390 Block *block = *result; 391 uintptr_t orig_end = reinterpret_cast<uintptr_t>(block) + block->outer_size(); 392 393 constexpr size_t SIZE = Block::PREV_FIELD_SIZE + 1; 394 395 auto [aligned_block, prev, next] = 396 Block::allocate(block, alignof(max_align_t), SIZE); 397 398 // Since this is already aligned, there should be no previous block. 399 EXPECT_EQ(prev, static_cast<Block *>(nullptr)); 400 401 // Ensure we the block is aligned and large enough. 402 EXPECT_NE(aligned_block, static_cast<Block *>(nullptr)); 403 EXPECT_TRUE(aligned_block->is_usable_space_aligned(alignof(max_align_t))); 404 EXPECT_GE(aligned_block->inner_size(), SIZE); 405 406 // Check the next block. 407 EXPECT_NE(next, static_cast<Block *>(nullptr)); 408 EXPECT_EQ(aligned_block->next(), next); 409 EXPECT_EQ(reinterpret_cast<uintptr_t>(next) + next->outer_size(), orig_end); 410 } 411 412 TEST(LlvmLibcBlockTest, AllocateNeedsAlignment) { 413 constexpr size_t kN = 1024; 414 415 array<byte, kN> bytes; 416 auto result = Block::init(bytes); 417 ASSERT_TRUE(result.has_value()); 418 Block *block = *result; 419 420 uintptr_t orig_end = reinterpret_cast<uintptr_t>(block) + block->outer_size(); 421 422 // Now pick an alignment such that the usable space is not already aligned to 423 // it. We want to explicitly test that the block will split into one before 424 // it. 425 size_t alignment = alignof(max_align_t); 426 while (block->is_usable_space_aligned(alignment)) 427 alignment += alignof(max_align_t); 428 429 auto [aligned_block, prev, next] = Block::allocate(block, alignment, 10); 430 431 // Check the previous block was created appropriately. Since this block is the 432 // first block, a new one should be made before this. 433 EXPECT_NE(prev, static_cast<Block *>(nullptr)); 434 EXPECT_EQ(aligned_block->prev_free(), prev); 435 EXPECT_EQ(prev->next(), aligned_block); 436 EXPECT_EQ(prev->outer_size(), reinterpret_cast<uintptr_t>(aligned_block) - 437 reinterpret_cast<uintptr_t>(prev)); 438 439 // Ensure we the block is aligned and the size we expect. 440 EXPECT_NE(next, static_cast<Block *>(nullptr)); 441 EXPECT_TRUE(aligned_block->is_usable_space_aligned(alignment)); 442 443 // Check the next block. 444 EXPECT_NE(next, static_cast<Block *>(nullptr)); 445 EXPECT_EQ(aligned_block->next(), next); 446 EXPECT_EQ(reinterpret_cast<uintptr_t>(next) + next->outer_size(), orig_end); 447 } 448 449 TEST(LlvmLibcBlockTest, PreviousBlockMergedIfNotFirst) { 450 constexpr size_t kN = 1024; 451 452 array<byte, kN> bytes; 453 auto result = Block::init(bytes); 454 ASSERT_TRUE(result.has_value()); 455 Block *block = *result; 456 457 // Split the block roughly halfway and work on the second half. 458 auto result2 = block->split(kN / 2); 459 ASSERT_TRUE(result2.has_value()); 460 Block *newblock = *result2; 461 ASSERT_EQ(newblock->prev_free(), block); 462 size_t old_prev_size = block->outer_size(); 463 464 // Now pick an alignment such that the usable space is not already aligned to 465 // it. We want to explicitly test that the block will split into one before 466 // it. 467 size_t alignment = alignof(max_align_t); 468 while (newblock->is_usable_space_aligned(alignment)) 469 alignment += alignof(max_align_t); 470 471 // Ensure we can allocate in the new block. 472 auto [aligned_block, prev, next] = Block::allocate(newblock, alignment, 1); 473 474 // Now there should be no new previous block. Instead, the padding we did 475 // create should be merged into the original previous block. 476 EXPECT_EQ(prev, static_cast<Block *>(nullptr)); 477 EXPECT_EQ(aligned_block->prev_free(), block); 478 EXPECT_EQ(block->next(), aligned_block); 479 EXPECT_GT(block->outer_size(), old_prev_size); 480 } 481 482 TEST(LlvmLibcBlockTest, CanRemergeBlockAllocations) { 483 // Finally to ensure we made the split blocks correctly via allocate. We 484 // should be able to reconstruct the original block from the blocklets. 485 // 486 // This is the same setup as with the `AllocateNeedsAlignment` test case. 487 constexpr size_t kN = 1024; 488 489 array<byte, kN> bytes; 490 auto result = Block::init(bytes); 491 ASSERT_TRUE(result.has_value()); 492 Block *block = *result; 493 494 Block *orig_block = block; 495 size_t orig_size = orig_block->outer_size(); 496 497 Block *last = block->next(); 498 499 ASSERT_EQ(block->prev_free(), static_cast<Block *>(nullptr)); 500 501 // Now pick an alignment such that the usable space is not already aligned to 502 // it. We want to explicitly test that the block will split into one before 503 // it. 504 size_t alignment = alignof(max_align_t); 505 while (block->is_usable_space_aligned(alignment)) 506 alignment += alignof(max_align_t); 507 508 auto [aligned_block, prev, next] = Block::allocate(block, alignment, 1); 509 510 // Check we have the appropriate blocks. 511 ASSERT_NE(prev, static_cast<Block *>(nullptr)); 512 ASSERT_EQ(aligned_block->prev_free(), prev); 513 EXPECT_NE(next, static_cast<Block *>(nullptr)); 514 EXPECT_EQ(aligned_block->next(), next); 515 EXPECT_EQ(next->next(), last); 516 517 // Now check for successful merges. 518 EXPECT_TRUE(prev->merge_next()); 519 EXPECT_EQ(prev->next(), next); 520 EXPECT_TRUE(prev->merge_next()); 521 EXPECT_EQ(prev->next(), last); 522 523 // We should have the original buffer. 524 EXPECT_EQ(prev, orig_block); 525 EXPECT_EQ(prev->outer_size(), orig_size); 526 } 527