1//===- llvm/unittest/Support/AllocatorTest.cpp - BumpPtrAllocator tests ---===//
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 "llvm/Support/Allocator.h"
10#include "gtest/gtest.h"
11#include <cstdlib>
12
13using namespace llvm;
14
15namespace {
16
17TEST(AllocatorTest, Basics) {
18 BumpPtrAllocator Alloc;
19 int *a = (int*)Alloc.Allocate(Size: sizeof(int), Alignment: alignof(int));
20 int *b = (int*)Alloc.Allocate(Size: sizeof(int) * 10, Alignment: alignof(int));
21 int *c = (int*)Alloc.Allocate(Size: sizeof(int), Alignment: alignof(int));
22 *a = 1;
23 b[0] = 2;
24 b[9] = 2;
25 *c = 3;
26 EXPECT_EQ(1, *a);
27 EXPECT_EQ(2, b[0]);
28 EXPECT_EQ(2, b[9]);
29 EXPECT_EQ(3, *c);
30 EXPECT_EQ(1U, Alloc.GetNumSlabs());
31
32 BumpPtrAllocator Alloc2 = std::move(Alloc);
33 EXPECT_EQ(0U, Alloc.GetNumSlabs());
34 EXPECT_EQ(1U, Alloc2.GetNumSlabs());
35
36 // Make sure the old pointers still work. These are especially interesting
37 // under ASan or Valgrind.
38 EXPECT_EQ(1, *a);
39 EXPECT_EQ(2, b[0]);
40 EXPECT_EQ(2, b[9]);
41 EXPECT_EQ(3, *c);
42
43 Alloc = std::move(Alloc2);
44 EXPECT_EQ(0U, Alloc2.GetNumSlabs());
45 EXPECT_EQ(1U, Alloc.GetNumSlabs());
46}
47
48// Allocate enough bytes to create three slabs.
49TEST(AllocatorTest, ThreeSlabs) {
50 BumpPtrAllocator Alloc;
51 Alloc.Allocate(Size: 3000, Alignment: 1);
52 EXPECT_EQ(1U, Alloc.GetNumSlabs());
53 Alloc.Allocate(Size: 3000, Alignment: 1);
54 EXPECT_EQ(2U, Alloc.GetNumSlabs());
55 Alloc.Allocate(Size: 3000, Alignment: 1);
56 EXPECT_EQ(3U, Alloc.GetNumSlabs());
57}
58
59// Allocate enough bytes to create two slabs, reset the allocator, and do it
60// again.
61TEST(AllocatorTest, TestReset) {
62 BumpPtrAllocator Alloc;
63
64 // Allocate something larger than the SizeThreshold=4096.
65 (void)Alloc.Allocate(Size: 5000, Alignment: 1);
66 Alloc.Reset();
67 // Calling Reset should free all CustomSizedSlabs.
68 EXPECT_EQ(0u, Alloc.GetNumSlabs());
69
70 Alloc.Allocate(Size: 3000, Alignment: 1);
71 EXPECT_EQ(1U, Alloc.GetNumSlabs());
72 Alloc.Allocate(Size: 3000, Alignment: 1);
73 EXPECT_EQ(2U, Alloc.GetNumSlabs());
74 Alloc.Reset();
75 EXPECT_EQ(1U, Alloc.GetNumSlabs());
76 Alloc.Allocate(Size: 3000, Alignment: 1);
77 EXPECT_EQ(1U, Alloc.GetNumSlabs());
78 Alloc.Allocate(Size: 3000, Alignment: 1);
79 EXPECT_EQ(2U, Alloc.GetNumSlabs());
80}
81
82// Test some allocations at varying alignments.
83TEST(AllocatorTest, TestAlignment) {
84 BumpPtrAllocator Alloc;
85 uintptr_t a;
86 a = (uintptr_t)Alloc.Allocate(Size: 1, Alignment: 2);
87 EXPECT_EQ(0U, a & 1);
88 a = (uintptr_t)Alloc.Allocate(Size: 1, Alignment: 4);
89 EXPECT_EQ(0U, a & 3);
90 a = (uintptr_t)Alloc.Allocate(Size: 1, Alignment: 8);
91 EXPECT_EQ(0U, a & 7);
92 a = (uintptr_t)Alloc.Allocate(Size: 1, Alignment: 16);
93 EXPECT_EQ(0U, a & 15);
94 a = (uintptr_t)Alloc.Allocate(Size: 1, Alignment: 32);
95 EXPECT_EQ(0U, a & 31);
96 a = (uintptr_t)Alloc.Allocate(Size: 1, Alignment: 64);
97 EXPECT_EQ(0U, a & 63);
98 a = (uintptr_t)Alloc.Allocate(Size: 1, Alignment: 128);
99 EXPECT_EQ(0U, a & 127);
100}
101
102// Test zero-sized allocations.
103// In general we don't need to allocate memory for these.
104// However Allocate never returns null, so if the first allocation is zero-sized
105// we end up creating a slab for it.
106TEST(AllocatorTest, TestZero) {
107 BumpPtrAllocator Alloc;
108 Alloc.setRedZoneSize(0); // else our arithmetic is all off
109 EXPECT_EQ(0u, Alloc.GetNumSlabs());
110 EXPECT_EQ(0u, Alloc.getBytesAllocated());
111
112 void *Empty = Alloc.Allocate(Size: 0, Alignment: 1);
113 EXPECT_NE(Empty, nullptr) << "Allocate is __attribute__((returns_nonnull))";
114 EXPECT_EQ(1u, Alloc.GetNumSlabs()) << "Allocated a slab to point to";
115 EXPECT_EQ(0u, Alloc.getBytesAllocated());
116
117 void *Large = Alloc.Allocate(Size: 4096, Alignment: 1);
118 EXPECT_EQ(1u, Alloc.GetNumSlabs());
119 EXPECT_EQ(4096u, Alloc.getBytesAllocated());
120 EXPECT_EQ(Empty, Large);
121
122 void *Empty2 = Alloc.Allocate(Size: 0, Alignment: 1);
123 EXPECT_NE(Empty2, nullptr);
124 EXPECT_EQ(1u, Alloc.GetNumSlabs());
125 EXPECT_EQ(4096u, Alloc.getBytesAllocated());
126}
127
128// Test allocating just over the slab size. This tests a bug where before the
129// allocator incorrectly calculated the buffer end pointer.
130TEST(AllocatorTest, TestOverflow) {
131 BumpPtrAllocator Alloc;
132
133 // Fill the slab right up until the end pointer.
134 Alloc.Allocate(Size: 4096, Alignment: 1);
135 EXPECT_EQ(1U, Alloc.GetNumSlabs());
136
137 // If we don't allocate a new slab, then we will have overflowed.
138 Alloc.Allocate(Size: 1, Alignment: 1);
139 EXPECT_EQ(2U, Alloc.GetNumSlabs());
140}
141
142// Test allocating with a size larger than the initial slab size.
143TEST(AllocatorTest, TestSmallSlabSize) {
144 BumpPtrAllocator Alloc;
145
146 Alloc.Allocate(Size: 8000, Alignment: 1);
147 EXPECT_EQ(1U, Alloc.GetNumSlabs());
148}
149
150// Test requesting alignment that goes past the end of the current slab.
151TEST(AllocatorTest, TestAlignmentPastSlab) {
152 BumpPtrAllocator Alloc;
153 Alloc.Allocate(Size: 4095, Alignment: 1);
154
155 // Aligning the current slab pointer is likely to move it past the end of the
156 // slab, which would confuse any unsigned comparisons with the difference of
157 // the end pointer and the aligned pointer.
158 Alloc.Allocate(Size: 1024, Alignment: 8192);
159
160 EXPECT_EQ(2U, Alloc.GetNumSlabs());
161}
162
163// Test allocating with a decreased growth delay.
164TEST(AllocatorTest, TestFasterSlabGrowthDelay) {
165 const size_t SlabSize = 4096;
166 // Decrease the growth delay to double the slab size every slab.
167 const size_t GrowthDelay = 1;
168 BumpPtrAllocatorImpl<MallocAllocator, SlabSize, SlabSize, GrowthDelay> Alloc;
169 // Disable the red zone for this test. The additional bytes allocated for the
170 // red zone would change the allocation numbers we check below.
171 Alloc.setRedZoneSize(0);
172
173 Alloc.Allocate(Size: SlabSize, Alignment: 1);
174 EXPECT_EQ(SlabSize, Alloc.getTotalMemory());
175 // We hit our growth delay with the previous allocation so the next
176 // allocation should get a twice as large slab.
177 Alloc.Allocate(Size: SlabSize, Alignment: 1);
178 EXPECT_EQ(SlabSize * 3, Alloc.getTotalMemory());
179 Alloc.Allocate(Size: SlabSize, Alignment: 1);
180 EXPECT_EQ(SlabSize * 3, Alloc.getTotalMemory());
181
182 // Both slabs are full again and hit the growth delay again, so the
183 // next allocation should again get a slab with four times the size of the
184 // original slab size. In total we now should have a memory size of:
185 // 1 + 2 + 4 * SlabSize.
186 Alloc.Allocate(Size: SlabSize, Alignment: 1);
187 EXPECT_EQ(SlabSize * 7, Alloc.getTotalMemory());
188}
189
190// Test allocating with a increased growth delay.
191TEST(AllocatorTest, TestSlowerSlabGrowthDelay) {
192 const size_t SlabSize = 16;
193 // Increase the growth delay to only double the slab size every 256 slabs.
194 const size_t GrowthDelay = 256;
195 BumpPtrAllocatorImpl<MallocAllocator, SlabSize, SlabSize, GrowthDelay> Alloc;
196 // Disable the red zone for this test. The additional bytes allocated for the
197 // red zone would change the allocation numbers we check below.
198 Alloc.setRedZoneSize(0);
199
200 // Allocate 256 slabs. We should keep getting slabs with the original size
201 // as we haven't hit our growth delay on the last allocation.
202 for (std::size_t i = 0; i < GrowthDelay; ++i)
203 Alloc.Allocate(Size: SlabSize, Alignment: 1);
204 EXPECT_EQ(SlabSize * GrowthDelay, Alloc.getTotalMemory());
205 // Allocate another slab. This time we should get another slab allocated
206 // that is twice as large as the normal slab size.
207 Alloc.Allocate(Size: SlabSize, Alignment: 1);
208 EXPECT_EQ(SlabSize * GrowthDelay + SlabSize * 2, Alloc.getTotalMemory());
209}
210
211// Mock slab allocator that returns slabs aligned on 4096 bytes. There is no
212// easy portable way to do this, so this is kind of a hack.
213class MockSlabAllocator {
214 static size_t LastSlabSize;
215
216public:
217 ~MockSlabAllocator() { }
218
219 void *Allocate(size_t Size, size_t /*Alignment*/) {
220 // Allocate space for the alignment, the slab, and a void* that goes right
221 // before the slab.
222 Align Alignment(4096);
223 void *MemBase = safe_malloc(Sz: Size + Alignment.value() - 1 + sizeof(void *));
224
225 // Find the slab start.
226 void *Slab = (void *)alignAddr(Addr: (char*)MemBase + sizeof(void *), Alignment);
227
228 // Hold a pointer to the base so we can free the whole malloced block.
229 ((void**)Slab)[-1] = MemBase;
230
231 LastSlabSize = Size;
232 return Slab;
233 }
234
235 void Deallocate(void *Slab, size_t /*Size*/, size_t /*Alignment*/) {
236 free(ptr: ((void**)Slab)[-1]);
237 }
238
239 static size_t GetLastSlabSize() { return LastSlabSize; }
240};
241
242size_t MockSlabAllocator::LastSlabSize = 0;
243
244// Allocate a large-ish block with a really large alignment so that the
245// allocator will think that it has space, but after it does the alignment it
246// will not.
247TEST(AllocatorTest, TestBigAlignment) {
248 BumpPtrAllocatorImpl<MockSlabAllocator> Alloc;
249
250 // First allocate a tiny bit to ensure we have to re-align things.
251 (void)Alloc.Allocate(Size: 1, Alignment: 1);
252
253 // Now the big chunk with a big alignment.
254 (void)Alloc.Allocate(Size: 3000, Alignment: 2048);
255
256 // We test that the last slab size is not the default 4096 byte slab, but
257 // rather a custom sized slab that is larger.
258 EXPECT_GT(MockSlabAllocator::GetLastSlabSize(), 4096u);
259}
260
261} // anonymous namespace
262

source code of llvm/unittests/Support/AllocatorTest.cpp