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
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 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
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 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
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 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
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'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
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 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
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 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
482TEST(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

source code of libc/test/src/__support/block_test.cpp