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(sizeof(int), alignof(int)); 20 int *b = (int*)Alloc.Allocate(sizeof(int) * 10, alignof(int)); 21 int *c = (int*)Alloc.Allocate(sizeof(int), 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(3000, 1); 52 EXPECT_EQ(1U, Alloc.GetNumSlabs()); 53 Alloc.Allocate(3000, 1); 54 EXPECT_EQ(2U, Alloc.GetNumSlabs()); 55 Alloc.Allocate(3000, 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(5000, 1); 66 Alloc.Reset(); 67 // Calling Reset should free all CustomSizedSlabs. 68 EXPECT_EQ(0u, Alloc.GetNumSlabs()); 69 70 Alloc.Allocate(3000, 1); 71 EXPECT_EQ(1U, Alloc.GetNumSlabs()); 72 Alloc.Allocate(3000, 1); 73 EXPECT_EQ(2U, Alloc.GetNumSlabs()); 74 Alloc.Reset(); 75 EXPECT_EQ(1U, Alloc.GetNumSlabs()); 76 Alloc.Allocate(3000, 1); 77 EXPECT_EQ(1U, Alloc.GetNumSlabs()); 78 Alloc.Allocate(3000, 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(1, 2); 87 EXPECT_EQ(0U, a & 1); 88 a = (uintptr_t)Alloc.Allocate(1, 4); 89 EXPECT_EQ(0U, a & 3); 90 a = (uintptr_t)Alloc.Allocate(1, 8); 91 EXPECT_EQ(0U, a & 7); 92 a = (uintptr_t)Alloc.Allocate(1, 16); 93 EXPECT_EQ(0U, a & 15); 94 a = (uintptr_t)Alloc.Allocate(1, 32); 95 EXPECT_EQ(0U, a & 31); 96 a = (uintptr_t)Alloc.Allocate(1, 64); 97 EXPECT_EQ(0U, a & 63); 98 a = (uintptr_t)Alloc.Allocate(1, 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(0, 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(4096, 1); 118 EXPECT_EQ(1u, Alloc.GetNumSlabs()); 119 EXPECT_EQ(4096u, Alloc.getBytesAllocated()); 120 EXPECT_EQ(Empty, Large); 121 122 void *Empty2 = Alloc.Allocate(0, 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(4096, 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(1, 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(8000, 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(4095, 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(1024, 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(SlabSize, 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(SlabSize, 1); 178 EXPECT_EQ(SlabSize * 3, Alloc.getTotalMemory()); 179 Alloc.Allocate(SlabSize, 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(SlabSize, 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(SlabSize, 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(SlabSize, 1); 208 EXPECT_EQ(SlabSize * GrowthDelay + SlabSize * 2, Alloc.getTotalMemory()); 209 } 210 211 TEST(AllocatorTest, TestIdentifyObject) { 212 BumpPtrAllocator Alloc; 213 214 uint64_t *a = (uint64_t *)Alloc.Allocate(sizeof(uint64_t), alignof(uint64_t)); 215 std::optional<int64_t> maybe_a_belongs = Alloc.identifyObject(a); 216 EXPECT_TRUE(maybe_a_belongs.has_value()); 217 EXPECT_TRUE(*maybe_a_belongs >= 0); 218 219 uint64_t *b = nullptr; 220 std::optional<int64_t> maybe_b_belongs = Alloc.identifyObject(b); 221 EXPECT_FALSE(maybe_b_belongs); 222 223 // The default slab size is 4096 (or 512 uint64_t values). Custom slabs are 224 // allocated when the requested size is larger than the slab size. 225 uint64_t *c = 226 (uint64_t *)Alloc.Allocate(sizeof(uint64_t) * 1024, alignof(uint64_t)); 227 std::optional<int64_t> maybe_c_belongs = Alloc.identifyObject(c); 228 EXPECT_TRUE(maybe_c_belongs.has_value()); 229 EXPECT_TRUE(*maybe_c_belongs < 0); 230 } 231 232 // Mock slab allocator that returns slabs aligned on 4096 bytes. There is no 233 // easy portable way to do this, so this is kind of a hack. 234 class MockSlabAllocator { 235 static size_t LastSlabSize; 236 237 public: 238 ~MockSlabAllocator() { } 239 240 void *Allocate(size_t Size, size_t /*Alignment*/) { 241 // Allocate space for the alignment, the slab, and a void* that goes right 242 // before the slab. 243 Align Alignment(4096); 244 void *MemBase = safe_malloc(Size + Alignment.value() - 1 + sizeof(void *)); 245 246 // Find the slab start. 247 void *Slab = (void *)alignAddr((char*)MemBase + sizeof(void *), Alignment); 248 249 // Hold a pointer to the base so we can free the whole malloced block. 250 ((void**)Slab)[-1] = MemBase; 251 252 LastSlabSize = Size; 253 return Slab; 254 } 255 256 void Deallocate(void *Slab, size_t /*Size*/, size_t /*Alignment*/) { 257 free(((void**)Slab)[-1]); 258 } 259 260 static size_t GetLastSlabSize() { return LastSlabSize; } 261 }; 262 263 size_t MockSlabAllocator::LastSlabSize = 0; 264 265 // Allocate a large-ish block with a really large alignment so that the 266 // allocator will think that it has space, but after it does the alignment it 267 // will not. 268 TEST(AllocatorTest, TestBigAlignment) { 269 BumpPtrAllocatorImpl<MockSlabAllocator> Alloc; 270 271 // First allocate a tiny bit to ensure we have to re-align things. 272 (void)Alloc.Allocate(1, 1); 273 274 // Now the big chunk with a big alignment. 275 (void)Alloc.Allocate(3000, 2048); 276 277 // We test that the last slab size is not the default 4096 byte slab, but 278 // rather a custom sized slab that is larger. 279 EXPECT_GT(MockSlabAllocator::GetLastSlabSize(), 4096u); 280 } 281 282 } // anonymous namespace 283