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 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 byte buf[N]; 99 100 FreeListHeap allocator(buf); 101 102 bool went_null = false; 103 for (size_t i = 0; i < N; i++) { 104 if (!allocator.allocate(1)) { 105 went_null = true; 106 break; 107 } 108 } 109 EXPECT_TRUE(went_null); 110 EXPECT_EQ(allocator.allocate(1), static_cast<void *>(nullptr)); 111 } 112 113 TEST_FOR_EACH_ALLOCATOR(ReturnedPointersAreAligned, 2048) { 114 void *ptr1 = allocator.allocate(1); 115 116 uintptr_t ptr1_start = reinterpret_cast<uintptr_t>(ptr1); 117 EXPECT_EQ(ptr1_start % alignof(max_align_t), static_cast<size_t>(0)); 118 119 void *ptr2 = allocator.allocate(1); 120 uintptr_t ptr2_start = reinterpret_cast<uintptr_t>(ptr2); 121 122 EXPECT_EQ(ptr2_start % alignof(max_align_t), static_cast<size_t>(0)); 123 } 124 125 TEST_FOR_EACH_ALLOCATOR(CanRealloc, 2048) { 126 constexpr size_t ALLOC_SIZE = 512; 127 constexpr size_t kNewAllocSize = 768; 128 129 void *ptr1 = allocator.allocate(ALLOC_SIZE); 130 void *ptr2 = allocator.realloc(ptr1, kNewAllocSize); 131 132 ASSERT_NE(ptr1, static_cast<void *>(nullptr)); 133 ASSERT_NE(ptr2, static_cast<void *>(nullptr)); 134 } 135 136 TEST_FOR_EACH_ALLOCATOR(ReallocHasSameContent, 2048) { 137 constexpr size_t ALLOC_SIZE = sizeof(int); 138 constexpr size_t kNewAllocSize = sizeof(int) * 2; 139 // Data inside the allocated block. 140 byte data1[ALLOC_SIZE]; 141 // Data inside the reallocated block. 142 byte data2[ALLOC_SIZE]; 143 144 int *ptr1 = reinterpret_cast<int *>(allocator.allocate(ALLOC_SIZE)); 145 *ptr1 = 42; 146 LIBC_NAMESPACE::memcpy(data1, ptr1, ALLOC_SIZE); 147 int *ptr2 = reinterpret_cast<int *>(allocator.realloc(ptr1, kNewAllocSize)); 148 LIBC_NAMESPACE::memcpy(data2, ptr2, ALLOC_SIZE); 149 150 ASSERT_NE(ptr1, static_cast<int *>(nullptr)); 151 ASSERT_NE(ptr2, static_cast<int *>(nullptr)); 152 // Verify that data inside the allocated and reallocated chunks are the same. 153 EXPECT_EQ(LIBC_NAMESPACE::memcmp(data1, data2, ALLOC_SIZE), 0); 154 } 155 156 TEST_FOR_EACH_ALLOCATOR(ReturnsNullReallocFreedPointer, 2048) { 157 constexpr size_t ALLOC_SIZE = 512; 158 constexpr size_t kNewAllocSize = 256; 159 160 void *ptr1 = allocator.allocate(ALLOC_SIZE); 161 allocator.free(ptr1); 162 void *ptr2 = allocator.realloc(ptr1, kNewAllocSize); 163 164 EXPECT_EQ(static_cast<void *>(nullptr), ptr2); 165 } 166 167 TEST_FOR_EACH_ALLOCATOR(ReallocSmallerSize, 2048) { 168 constexpr size_t ALLOC_SIZE = 512; 169 constexpr size_t kNewAllocSize = 256; 170 171 void *ptr1 = allocator.allocate(ALLOC_SIZE); 172 void *ptr2 = allocator.realloc(ptr1, kNewAllocSize); 173 174 // For smaller sizes, realloc will not shrink the block. 175 EXPECT_EQ(ptr1, ptr2); 176 } 177 178 TEST_FOR_EACH_ALLOCATOR(ReallocTooLarge, 2048) { 179 constexpr size_t ALLOC_SIZE = 512; 180 size_t kNewAllocSize = N * 2; // Large enough to fail. 181 182 void *ptr1 = allocator.allocate(ALLOC_SIZE); 183 void *ptr2 = allocator.realloc(ptr1, kNewAllocSize); 184 185 // realloc() will not invalidate the original pointer if realloc() fails 186 EXPECT_NE(static_cast<void *>(nullptr), ptr1); 187 EXPECT_EQ(static_cast<void *>(nullptr), ptr2); 188 } 189 190 TEST_FOR_EACH_ALLOCATOR(CanCalloc, 2048) { 191 constexpr size_t ALLOC_SIZE = 128; 192 constexpr size_t NUM = 4; 193 constexpr int size = NUM * ALLOC_SIZE; 194 constexpr byte zero{0}; 195 196 byte *ptr1 = reinterpret_cast<byte *>(allocator.calloc(NUM, ALLOC_SIZE)); 197 198 // calloc'd content is zero. 199 for (int i = 0; i < size; i++) { 200 EXPECT_EQ(ptr1[i], zero); 201 } 202 } 203 204 TEST_FOR_EACH_ALLOCATOR(CanCallocWeirdSize, 2048) { 205 constexpr size_t ALLOC_SIZE = 143; 206 constexpr size_t NUM = 3; 207 constexpr int size = NUM * ALLOC_SIZE; 208 constexpr byte zero{0}; 209 210 byte *ptr1 = reinterpret_cast<byte *>(allocator.calloc(NUM, ALLOC_SIZE)); 211 212 // calloc'd content is zero. 213 for (int i = 0; i < size; i++) { 214 EXPECT_EQ(ptr1[i], zero); 215 } 216 } 217 218 TEST_FOR_EACH_ALLOCATOR(CallocTooLarge, 2048) { 219 size_t ALLOC_SIZE = N + 1; 220 EXPECT_EQ(allocator.calloc(1, ALLOC_SIZE), static_cast<void *>(nullptr)); 221 } 222 223 TEST_FOR_EACH_ALLOCATOR(AllocateZero, 2048) { 224 void *ptr = allocator.allocate(0); 225 ASSERT_EQ(ptr, static_cast<void *>(nullptr)); 226 } 227 228 TEST_FOR_EACH_ALLOCATOR(AlignedAlloc, 2048) { 229 constexpr size_t ALIGNMENTS[] = {1, 2, 4, 8, 16, 32, 64, 128, 256}; 230 constexpr size_t SIZE_SCALES[] = {1, 2, 3, 4, 5}; 231 232 for (size_t alignment : ALIGNMENTS) { 233 for (size_t scale : SIZE_SCALES) { 234 size_t size = alignment * scale; 235 void *ptr = allocator.aligned_allocate(alignment, size); 236 EXPECT_NE(ptr, static_cast<void *>(nullptr)); 237 EXPECT_EQ(reinterpret_cast<uintptr_t>(ptr) % alignment, size_t(0)); 238 allocator.free(ptr); 239 } 240 } 241 } 242 243 // This test is not part of the TEST_FOR_EACH_ALLOCATOR since we want to 244 // explicitly ensure that the buffer can still return aligned allocations even 245 // if the underlying buffer is unaligned. This is so we can check that we can 246 // still get aligned allocations even if the underlying buffer is not aligned to 247 // the alignments we request. 248 TEST(LlvmLibcFreeListHeap, AlignedAllocUnalignedBuffer) { 249 byte buf[4096] = {byte(0)}; 250 251 // Ensure the underlying buffer is poorly aligned. 252 FreeListHeap allocator(span<byte>(buf).subspan(1)); 253 254 constexpr size_t ALIGNMENTS[] = {1, 2, 4, 8, 16, 32, 64, 128, 256}; 255 constexpr size_t SIZE_SCALES[] = {1, 2, 3, 4, 5}; 256 257 for (size_t alignment : ALIGNMENTS) { 258 for (size_t scale : SIZE_SCALES) { 259 size_t size = alignment * scale; 260 void *ptr = allocator.aligned_allocate(alignment, size); 261 EXPECT_NE(ptr, static_cast<void *>(nullptr)); 262 EXPECT_EQ(reinterpret_cast<uintptr_t>(ptr) % alignment, size_t(0)); 263 allocator.free(ptr); 264 } 265 } 266 } 267 268 TEST_FOR_EACH_ALLOCATOR(InvalidAlignedAllocAlignment, 2048) { 269 // Must be a power of 2. 270 constexpr size_t ALIGNMENTS[] = {4, 8, 16, 32, 64, 128, 256}; 271 for (size_t alignment : ALIGNMENTS) { 272 void *ptr = allocator.aligned_allocate(alignment - 1, alignment - 1); 273 EXPECT_EQ(ptr, static_cast<void *>(nullptr)); 274 } 275 276 // Size must be a multiple of alignment 277 for (size_t alignment : ALIGNMENTS) { 278 void *ptr = allocator.aligned_allocate(alignment, alignment + 1); 279 EXPECT_EQ(ptr, static_cast<void *>(nullptr)); 280 } 281 282 // Don't accept zero size. 283 void *ptr = allocator.aligned_allocate(1, 0); 284 EXPECT_EQ(ptr, static_cast<void *>(nullptr)); 285 286 // Don't accept zero alignment. 287 ptr = allocator.aligned_allocate(0, 8); 288 EXPECT_EQ(ptr, static_cast<void *>(nullptr)); 289 } 290