libc/test/src/__support/freelist_heap_test.cpp

   1 //===-- Unittests for freelist_heap ---------------------------------------===//
   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
   9 #include "src/__support/CPP/span.h"
  10 #include "src/__support/freelist_heap.h"
  11 #include "src/__support/macros/config.h"
  12 #include "src/string/memcmp.h"
  13 #include "src/string/memcpy.h"
  14 #include "test/UnitTest/Test.h"
  15
  16 using LIBC_NAMESPACE::Block;
  17 using LIBC_NAMESPACE::freelist_heap;
  18 using LIBC_NAMESPACE::FreeListHeap;
  19 using LIBC_NAMESPACE::FreeListHeapBuffer;
  20 using LIBC_NAMESPACE::cpp::byte;
  21 using LIBC_NAMESPACE::cpp::span;
  22
  23 // Similar to `LlvmLibcBlockTest` in block_test.cpp, we'd like to run the same
  24 // tests independently for different parameters. In this case, we'd like to test
  25 // functionality for a `FreeListHeap` and the global `freelist_heap` which was
  26 // constinit'd. Functionally, it should operate the same if the FreeListHeap
  27 // were initialized locally at runtime or at compile-time.
  28 //
  29 // Note that calls to `allocate` for each test case here don't always explicitly
  30 // `free` them afterwards, so when testing the global allocator, allocations
  31 // made in tests leak and aren't free'd. This is fine for the purposes of this
  32 // test file.
  33 #define TEST_FOR_EACH_ALLOCATOR(TestCase, BufferSize)                          \
  34   class LlvmLibcFreeListHeapTest##TestCase                                     \
  35       : public LIBC_NAMESPACE::testing::Test {                                 \
  36   public:                                                                      \
  37     FreeListHeapBuffer<BufferSize> fake_global_buffer;                         \
  38     void SetUp() override {                                                    \
  39       freelist_heap =                                                          \
  40           new (&fake_global_buffer) FreeListHeapBuffer<BufferSize>;            \
  41     }                                                                          \
  42     void RunTest(FreeListHeap &allocator, [[maybe_unused]] size_t N);          \
  43   };                                                                           \
  44   TEST_F(LlvmLibcFreeListHeapTest##TestCase, TestCase) {                       \
  45     alignas(Block) byte buf[BufferSize] = {byte(0)};                           \
  46     FreeListHeap allocator(buf);                                               \
  47     RunTest(allocator, BufferSize);                                            \
  48     RunTest(*freelist_heap, freelist_heap->region().size());                   \
  49   }                                                                            \
  50   void LlvmLibcFreeListHeapTest##TestCase::RunTest(FreeListHeap &allocator,    \
  51                                                    size_t N)
  52
  53 TEST_FOR_EACH_ALLOCATOR(CanAllocate, 2048) {
  54   constexpr size_t ALLOC_SIZE = 512;
  55
  56   void *ptr = allocator.allocate(ALLOC_SIZE);
  57
  58   ASSERT_NE(ptr, static_cast<void *>(nullptr));
  59 }
  60
  61 TEST_FOR_EACH_ALLOCATOR(AllocationsDontOverlap, 2048) {
  62   constexpr size_t ALLOC_SIZE = 512;
  63
  64   void *ptr1 = allocator.allocate(ALLOC_SIZE);
  65   void *ptr2 = allocator.allocate(ALLOC_SIZE);
  66
  67   ASSERT_NE(ptr1, static_cast<void *>(nullptr));
  68   ASSERT_NE(ptr2, static_cast<void *>(nullptr));
  69
  70   uintptr_t ptr1_start = reinterpret_cast<uintptr_t>(ptr1);
  71   uintptr_t ptr1_end = ptr1_start + ALLOC_SIZE;
  72   uintptr_t ptr2_start = reinterpret_cast<uintptr_t>(ptr2);
  73
  74   EXPECT_GT(ptr2_start, ptr1_end);
  75 }
  76
  77 TEST_FOR_EACH_ALLOCATOR(CanFreeAndRealloc, 2048) {
  78   // There's not really a nice way to test that free works, apart from to try
  79   // and get that value back again.
  80   constexpr size_t ALLOC_SIZE = 512;
  81
  82   void *ptr1 = allocator.allocate(ALLOC_SIZE);
  83   allocator.free(ptr1);
  84   void *ptr2 = allocator.allocate(ALLOC_SIZE);
  85
  86   EXPECT_EQ(ptr1, ptr2);
  87 }
  88
  89 TEST_FOR_EACH_ALLOCATOR(ReturnsNullWhenAllocationTooLarge, 2048) {
  90   EXPECT_EQ(allocator.allocate(N), static_cast<void *>(nullptr));
  91 }
  92
  93 // NOTE: This doesn't use TEST_FOR_EACH_ALLOCATOR because the first `allocate`
  94 // here will likely actually return a nullptr since the same global allocator
  95 // is used for other test cases and we don't explicitly free them.
  96 TEST(LlvmLibcFreeListHeap, ReturnsNullWhenFull) {
  97   constexpr size_t N = 2048;
  98   alignas(Block) byte buf[N] = {byte(0)};
  99
 100   FreeListHeap allocator(buf);
 101
 102   // Use aligned_allocate so we don't need to worry about ensuring the `buf`
 103   // being aligned to max_align_t.
 104   EXPECT_NE(allocator.aligned_allocate(1, N - 2 * Block::BLOCK_OVERHEAD),
 105             static_cast<void *>(nullptr));
 106   EXPECT_EQ(allocator.allocate(1), static_cast<void *>(nullptr));
 107 }
 108
 109 TEST_FOR_EACH_ALLOCATOR(ReturnedPointersAreAligned, 2048) {
 110   void *ptr1 = allocator.allocate(1);
 111
 112   // Should be aligned to native pointer alignment
 113   uintptr_t ptr1_start = reinterpret_cast<uintptr_t>(ptr1);
 114   size_t alignment = alignof(void *);
 115
 116   EXPECT_EQ(ptr1_start % alignment, static_cast<size_t>(0));
 117
 118   void *ptr2 = allocator.allocate(1);
 119   uintptr_t ptr2_start = reinterpret_cast<uintptr_t>(ptr2);
 120
 121   EXPECT_EQ(ptr2_start % alignment, static_cast<size_t>(0));
 122 }
 123
 124 TEST_FOR_EACH_ALLOCATOR(CanRealloc, 2048) {
 125   constexpr size_t ALLOC_SIZE = 512;
 126   constexpr size_t kNewAllocSize = 768;
 127
 128   void *ptr1 = allocator.allocate(ALLOC_SIZE);
 129   void *ptr2 = allocator.realloc(ptr1, kNewAllocSize);
 130
 131   ASSERT_NE(ptr1, static_cast<void *>(nullptr));
 132   ASSERT_NE(ptr2, static_cast<void *>(nullptr));
 133 }
 134
 135 TEST_FOR_EACH_ALLOCATOR(ReallocHasSameContent, 2048) {
 136   constexpr size_t ALLOC_SIZE = sizeof(int);
 137   constexpr size_t kNewAllocSize = sizeof(int) * 2;
 138   // Data inside the allocated block.
 139   byte data1[ALLOC_SIZE];
 140   // Data inside the reallocated block.
 141   byte data2[ALLOC_SIZE];
 142
 143   int *ptr1 = reinterpret_cast<int *>(allocator.allocate(ALLOC_SIZE));
 144   *ptr1 = 42;
 145   LIBC_NAMESPACE::memcpy(data1, ptr1, ALLOC_SIZE);
 146   int *ptr2 = reinterpret_cast<int *>(allocator.realloc(ptr1, kNewAllocSize));
 147   LIBC_NAMESPACE::memcpy(data2, ptr2, ALLOC_SIZE);
 148
 149   ASSERT_NE(ptr1, static_cast<int *>(nullptr));
 150   ASSERT_NE(ptr2, static_cast<int *>(nullptr));
 151   // Verify that data inside the allocated and reallocated chunks are the same.
 152   EXPECT_EQ(LIBC_NAMESPACE::memcmp(data1, data2, ALLOC_SIZE), 0);
 153 }
 154
 155 TEST_FOR_EACH_ALLOCATOR(ReturnsNullReallocFreedPointer, 2048) {
 156   constexpr size_t ALLOC_SIZE = 512;
 157   constexpr size_t kNewAllocSize = 256;
 158
 159   void *ptr1 = allocator.allocate(ALLOC_SIZE);
 160   allocator.free(ptr1);
 161   void *ptr2 = allocator.realloc(ptr1, kNewAllocSize);
 162
 163   EXPECT_EQ(static_cast<void *>(nullptr), ptr2);
 164 }
 165
 166 TEST_FOR_EACH_ALLOCATOR(ReallocSmallerSize, 2048) {
 167   constexpr size_t ALLOC_SIZE = 512;
 168   constexpr size_t kNewAllocSize = 256;
 169
 170   void *ptr1 = allocator.allocate(ALLOC_SIZE);
 171   void *ptr2 = allocator.realloc(ptr1, kNewAllocSize);
 172
 173   // For smaller sizes, realloc will not shrink the block.
 174   EXPECT_EQ(ptr1, ptr2);
 175 }
 176
 177 TEST_FOR_EACH_ALLOCATOR(ReallocTooLarge, 2048) {
 178   constexpr size_t ALLOC_SIZE = 512;
 179   size_t kNewAllocSize = N * 2; // Large enough to fail.
 180
 181   void *ptr1 = allocator.allocate(ALLOC_SIZE);
 182   void *ptr2 = allocator.realloc(ptr1, kNewAllocSize);
 183
 184   // realloc() will not invalidate the original pointer if realloc() fails
 185   EXPECT_NE(static_cast<void *>(nullptr), ptr1);
 186   EXPECT_EQ(static_cast<void *>(nullptr), ptr2);
 187 }
 188
 189 TEST_FOR_EACH_ALLOCATOR(CanCalloc, 2048) {
 190   constexpr size_t ALLOC_SIZE = 128;
 191   constexpr size_t NUM = 4;
 192   constexpr int size = NUM * ALLOC_SIZE;
 193   constexpr byte zero{0};
 194
 195   byte *ptr1 = reinterpret_cast<byte *>(allocator.calloc(NUM, ALLOC_SIZE));
 196
 197   // calloc'd content is zero.
 198   for (int i = 0; i < size; i++) {
 199     EXPECT_EQ(ptr1[i], zero);
 200   }
 201 }
 202
 203 TEST_FOR_EACH_ALLOCATOR(CanCallocWeirdSize, 2048) {
 204   constexpr size_t ALLOC_SIZE = 143;
 205   constexpr size_t NUM = 3;
 206   constexpr int size = NUM * ALLOC_SIZE;
 207   constexpr byte zero{0};
 208
 209   byte *ptr1 = reinterpret_cast<byte *>(allocator.calloc(NUM, ALLOC_SIZE));
 210
 211   // calloc'd content is zero.
 212   for (int i = 0; i < size; i++) {
 213     EXPECT_EQ(ptr1[i], zero);
 214   }
 215 }
 216
 217 TEST_FOR_EACH_ALLOCATOR(CallocTooLarge, 2048) {
 218   size_t ALLOC_SIZE = N + 1;
 219   EXPECT_EQ(allocator.calloc(1, ALLOC_SIZE), static_cast<void *>(nullptr));
 220 }
 221
 222 TEST_FOR_EACH_ALLOCATOR(AllocateZero, 2048) {
 223   void *ptr = allocator.allocate(0);
 224   ASSERT_EQ(ptr, static_cast<void *>(nullptr));
 225 }
 226
 227 TEST_FOR_EACH_ALLOCATOR(AlignedAlloc, 2048) {
 228   constexpr size_t ALIGNMENTS[] = {1, 2, 4, 8, 16, 32, 64, 128, 256};
 229   constexpr size_t SIZE_SCALES[] = {1, 2, 3, 4, 5};
 230
 231   for (size_t alignment : ALIGNMENTS) {
 232     for (size_t scale : SIZE_SCALES) {
 233       size_t size = alignment * scale;
 234       void *ptr = allocator.aligned_allocate(alignment, size);
 235       EXPECT_NE(ptr, static_cast<void *>(nullptr));
 236       EXPECT_EQ(reinterpret_cast<uintptr_t>(ptr) % alignment, size_t(0));
 237       allocator.free(ptr);
 238     }
 239   }
 240 }
 241
 242 // This test is not part of the TEST_FOR_EACH_ALLOCATOR since we want to
 243 // explicitly ensure that the buffer can still return aligned allocations even
 244 // if the underlying buffer is at most aligned to the Block alignment. This
 245 // is so we can check that we can still get aligned allocations even if the
 246 // underlying buffer is not aligned to the alignments we request.
 247 TEST(LlvmLibcFreeListHeap, AlignedAllocOnlyBlockAligned) {
 248   constexpr size_t BUFFER_SIZE = 4096;
 249   constexpr size_t BUFFER_ALIGNMENT = alignof(Block) * 2;
 250   alignas(BUFFER_ALIGNMENT) byte buf[BUFFER_SIZE] = {byte(0)};
 251
 252   // Ensure the underlying buffer is at most aligned to the block type.
 253   FreeListHeap allocator(span<byte>(buf).subspan(alignof(Block)));
 254
 255   constexpr size_t ALIGNMENTS[] = {1, 2, 4, 8, 16, 32, 64, 128, 256};
 256   constexpr size_t SIZE_SCALES[] = {1, 2, 3, 4, 5};
 257
 258   for (size_t alignment : ALIGNMENTS) {
 259     for (size_t scale : SIZE_SCALES) {
 260       size_t size = alignment * scale;
 261       void *ptr = allocator.aligned_allocate(alignment, size);
 262       EXPECT_NE(ptr, static_cast<void *>(nullptr));
 263       EXPECT_EQ(reinterpret_cast<uintptr_t>(ptr) % alignment, size_t(0));
 264       allocator.free(ptr);
 265     }
 266   }
 267 }
 268
 269 TEST_FOR_EACH_ALLOCATOR(InvalidAlignedAllocAlignment, 2048) {
 270   // Must be a power of 2.
 271   constexpr size_t ALIGNMENTS[] = {4, 8, 16, 32, 64, 128, 256};
 272   for (size_t alignment : ALIGNMENTS) {
 273     void *ptr = allocator.aligned_allocate(alignment - 1, alignment - 1);
 274     EXPECT_EQ(ptr, static_cast<void *>(nullptr));
 275   }
 276
 277   // Size must be a multiple of alignment
 278   for (size_t alignment : ALIGNMENTS) {
 279     void *ptr = allocator.aligned_allocate(alignment, alignment + 1);
 280     EXPECT_EQ(ptr, static_cast<void *>(nullptr));
 281   }
 282
 283   // Don't accept zero size.
 284   void *ptr = allocator.aligned_allocate(1, 0);
 285   EXPECT_EQ(ptr, static_cast<void *>(nullptr));
 286
 287   // Don't accept zero alignment.
 288   ptr = allocator.aligned_allocate(0, 8);
 289   EXPECT_EQ(ptr, static_cast<void *>(nullptr));
 290 }