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

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