xref: /llvm-project/libc/test/src/__support/block_test.cpp (revision 5db28679da38bee65feb55b803a23aceee568f44)
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