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 | |
13 | using namespace llvm; |
14 | |
15 | namespace { |
16 | |
17 | TEST(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. |
49 | TEST(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. |
61 | TEST(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. |
83 | TEST(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. |
106 | TEST(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. |
130 | TEST(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. |
143 | TEST(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. |
151 | TEST(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. |
164 | TEST(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. |
191 | TEST(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. |
213 | class MockSlabAllocator { |
214 | static size_t LastSlabSize; |
215 | |
216 | public: |
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 | |
242 | size_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. |
247 | TEST(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 | |