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 allocating just over the slab size. This tests a bug where before the 103 // allocator incorrectly calculated the buffer end pointer. 104 TEST(AllocatorTest, TestOverflow) { 105 BumpPtrAllocator Alloc; 106 107 // Fill the slab right up until the end pointer. 108 Alloc.Allocate(4096, 1); 109 EXPECT_EQ(1U, Alloc.GetNumSlabs()); 110 111 // If we don't allocate a new slab, then we will have overflowed. 112 Alloc.Allocate(1, 1); 113 EXPECT_EQ(2U, Alloc.GetNumSlabs()); 114 } 115 116 // Test allocating with a size larger than the initial slab size. 117 TEST(AllocatorTest, TestSmallSlabSize) { 118 BumpPtrAllocator Alloc; 119 120 Alloc.Allocate(8000, 1); 121 EXPECT_EQ(1U, Alloc.GetNumSlabs()); 122 } 123 124 // Test requesting alignment that goes past the end of the current slab. 125 TEST(AllocatorTest, TestAlignmentPastSlab) { 126 BumpPtrAllocator Alloc; 127 Alloc.Allocate(4095, 1); 128 129 // Aligning the current slab pointer is likely to move it past the end of the 130 // slab, which would confuse any unsigned comparisons with the difference of 131 // the end pointer and the aligned pointer. 132 Alloc.Allocate(1024, 8192); 133 134 EXPECT_EQ(2U, Alloc.GetNumSlabs()); 135 } 136 137 // Mock slab allocator that returns slabs aligned on 4096 bytes. There is no 138 // easy portable way to do this, so this is kind of a hack. 139 class MockSlabAllocator { 140 static size_t LastSlabSize; 141 142 public: 143 ~MockSlabAllocator() { } 144 145 void *Allocate(size_t Size, size_t /*Alignment*/) { 146 // Allocate space for the alignment, the slab, and a void* that goes right 147 // before the slab. 148 Align Alignment(4096); 149 void *MemBase = safe_malloc(Size + Alignment.value() - 1 + sizeof(void *)); 150 151 // Find the slab start. 152 void *Slab = (void *)alignAddr((char*)MemBase + sizeof(void *), Alignment); 153 154 // Hold a pointer to the base so we can free the whole malloced block. 155 ((void**)Slab)[-1] = MemBase; 156 157 LastSlabSize = Size; 158 return Slab; 159 } 160 161 void Deallocate(void *Slab, size_t Size) { 162 free(((void**)Slab)[-1]); 163 } 164 165 static size_t GetLastSlabSize() { return LastSlabSize; } 166 }; 167 168 size_t MockSlabAllocator::LastSlabSize = 0; 169 170 // Allocate a large-ish block with a really large alignment so that the 171 // allocator will think that it has space, but after it does the alignment it 172 // will not. 173 TEST(AllocatorTest, TestBigAlignment) { 174 BumpPtrAllocatorImpl<MockSlabAllocator> Alloc; 175 176 // First allocate a tiny bit to ensure we have to re-align things. 177 (void)Alloc.Allocate(1, 1); 178 179 // Now the big chunk with a big alignment. 180 (void)Alloc.Allocate(3000, 2048); 181 182 // We test that the last slab size is not the default 4096 byte slab, but 183 // rather a custom sized slab that is larger. 184 EXPECT_GT(MockSlabAllocator::GetLastSlabSize(), 4096u); 185 } 186 187 } // anonymous namespace 188