527 lines · cpp
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-exception6//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 17using LIBC_NAMESPACE::Block;18using LIBC_NAMESPACE::cpp::array;19using LIBC_NAMESPACE::cpp::bit_ceil;20using LIBC_NAMESPACE::cpp::byte;21using LIBC_NAMESPACE::cpp::span;22 23TEST(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 51TEST(LlvmLibcBlockTest, CanCreateUnalignedSingleBlock) {52 constexpr size_t kN = 1024;53 54 // Force alignment, so we can un-force it below55 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 70TEST(LlvmLibcBlockTest, CannotCreateTooSmallBlock) {71 array<byte, 2> bytes;72 auto result = Block::init(bytes);73 EXPECT_FALSE(result.has_value());74}75 76TEST(LlvmLibcBlockTest, CanSplitBlock) {77 constexpr size_t kN = 1024;78 79 // Choose a split position such that the next block's usable space is 51280 // bytes from this one's. This should be sufficient for any machine's81 // 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 107TEST(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 133TEST(LlvmLibcBlockTest, CanSplitMidBlock) {134 // split once, then split the original block again to ensure that the135 // 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 166TEST(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 178TEST(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 190TEST(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 203TEST(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 217TEST(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 234TEST(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 251TEST(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 265TEST(LlvmLibcBlockTest, CanMergeWithNextBlock) {266 // Do the three way merge from "CanSplitMidBlock", and let's267 // merge block 3 and 2268 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 293TEST(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 310TEST(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 327TEST(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 338TEST(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 351TEST(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 384TEST(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 412TEST(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 to423 // it. We want to explicitly test that the block will split into one before424 // 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 the432 // 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 449TEST(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 to465 // it. We want to explicitly test that the block will split into one before466 // 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 did475 // 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 482TEST(LlvmLibcBlockTest, CanRemergeBlockAllocations) {483 // Finally to ensure we made the split blocks correctly via allocate. We484 // 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 to502 // it. We want to explicitly test that the block will split into one before503 // 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