283 lines · cpp
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-exception6//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(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 interesting37 // 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(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 it60// again.61TEST(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.83TEST(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-sized105// we end up creating a slab for it.106TEST(AllocatorTest, TestZero) {107 BumpPtrAllocator Alloc;108 Alloc.setRedZoneSize(0); // else our arithmetic is all off109 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 the129// 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(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.143TEST(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.151TEST(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 the156 // slab, which would confuse any unsigned comparisons with the difference of157 // 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.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 the170 // 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 next176 // 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 the183 // next allocation should again get a slab with four times the size of the184 // 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.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 the197 // 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 size201 // 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 allocated206 // 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 211TEST(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 are224 // 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 no233// easy portable way to do this, so this is kind of a hack.234class MockSlabAllocator {235 static size_t LastSlabSize;236 237public:238 ~MockSlabAllocator() = default;239 240 void *Allocate(size_t Size, size_t /*Alignment*/) {241 // Allocate space for the alignment, the slab, and a void* that goes right242 // 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 263size_t MockSlabAllocator::LastSlabSize = 0;264 265// Allocate a large-ish block with a really large alignment so that the266// allocator will think that it has space, but after it does the alignment it267// will not.268TEST(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, but278 // rather a custom sized slab that is larger.279 EXPECT_GT(MockSlabAllocator::GetLastSlabSize(), 4096u);280}281 282} // anonymous namespace283