1//===- llvm/unittest/Support/AllocatorTest.cpp - BumpPtrAllocator tests ---===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "llvm/Support/Allocator.h"
11#include "gtest/gtest.h"
12#include <cstdlib>
13
14using namespace llvm;
15
16namespace {
17
18TEST(AllocatorTest, Basics) {
19  BumpPtrAllocator Alloc;
20  int *a = (int*)Alloc.Allocate(sizeof(int), 1);
21  int *b = (int*)Alloc.Allocate(sizeof(int) * 10, 1);
22  int *c = (int*)Alloc.Allocate(sizeof(int), 1);
23  *a = 1;
24  b[0] = 2;
25  b[9] = 2;
26  *c = 3;
27  EXPECT_EQ(1, *a);
28  EXPECT_EQ(2, b[0]);
29  EXPECT_EQ(2, b[9]);
30  EXPECT_EQ(3, *c);
31  EXPECT_EQ(1U, Alloc.GetNumSlabs());
32
33  BumpPtrAllocator Alloc2 = std::move(Alloc);
34  EXPECT_EQ(0U, Alloc.GetNumSlabs());
35  EXPECT_EQ(1U, Alloc2.GetNumSlabs());
36
37  // Make sure the old pointers still work. These are especially interesting
38  // under ASan or Valgrind.
39  EXPECT_EQ(1, *a);
40  EXPECT_EQ(2, b[0]);
41  EXPECT_EQ(2, b[9]);
42  EXPECT_EQ(3, *c);
43
44  Alloc = std::move(Alloc2);
45  EXPECT_EQ(0U, Alloc2.GetNumSlabs());
46  EXPECT_EQ(1U, Alloc.GetNumSlabs());
47}
48
49// Allocate enough bytes to create three slabs.
50TEST(AllocatorTest, ThreeSlabs) {
51  BumpPtrAllocator Alloc;
52  Alloc.Allocate(3000, 1);
53  EXPECT_EQ(1U, Alloc.GetNumSlabs());
54  Alloc.Allocate(3000, 1);
55  EXPECT_EQ(2U, Alloc.GetNumSlabs());
56  Alloc.Allocate(3000, 1);
57  EXPECT_EQ(3U, Alloc.GetNumSlabs());
58}
59
60// Allocate enough bytes to create two slabs, reset the allocator, and do it
61// again.
62TEST(AllocatorTest, TestReset) {
63  BumpPtrAllocator Alloc;
64
65  // Allocate something larger than the SizeThreshold=4096.
66  (void)Alloc.Allocate(5000, 1);
67  Alloc.Reset();
68  // Calling Reset should free all CustomSizedSlabs.
69  EXPECT_EQ(0u, Alloc.GetNumSlabs());
70
71  Alloc.Allocate(3000, 1);
72  EXPECT_EQ(1U, Alloc.GetNumSlabs());
73  Alloc.Allocate(3000, 1);
74  EXPECT_EQ(2U, Alloc.GetNumSlabs());
75  Alloc.Reset();
76  EXPECT_EQ(1U, Alloc.GetNumSlabs());
77  Alloc.Allocate(3000, 1);
78  EXPECT_EQ(1U, Alloc.GetNumSlabs());
79  Alloc.Allocate(3000, 1);
80  EXPECT_EQ(2U, Alloc.GetNumSlabs());
81}
82
83// Test some allocations at varying alignments.
84TEST(AllocatorTest, TestAlignment) {
85  BumpPtrAllocator Alloc;
86  uintptr_t a;
87  a = (uintptr_t)Alloc.Allocate(1, 2);
88  EXPECT_EQ(0U, a & 1);
89  a = (uintptr_t)Alloc.Allocate(1, 4);
90  EXPECT_EQ(0U, a & 3);
91  a = (uintptr_t)Alloc.Allocate(1, 8);
92  EXPECT_EQ(0U, a & 7);
93  a = (uintptr_t)Alloc.Allocate(1, 16);
94  EXPECT_EQ(0U, a & 15);
95  a = (uintptr_t)Alloc.Allocate(1, 32);
96  EXPECT_EQ(0U, a & 31);
97  a = (uintptr_t)Alloc.Allocate(1, 64);
98  EXPECT_EQ(0U, a & 63);
99  a = (uintptr_t)Alloc.Allocate(1, 128);
100  EXPECT_EQ(0U, a & 127);
101}
102
103// Test allocating just over the slab size.  This tests a bug where before the
104// allocator incorrectly calculated the buffer end pointer.
105TEST(AllocatorTest, TestOverflow) {
106  BumpPtrAllocator Alloc;
107
108  // Fill the slab right up until the end pointer.
109  Alloc.Allocate(4096, 1);
110  EXPECT_EQ(1U, Alloc.GetNumSlabs());
111
112  // If we don't allocate a new slab, then we will have overflowed.
113  Alloc.Allocate(1, 1);
114  EXPECT_EQ(2U, Alloc.GetNumSlabs());
115}
116
117// Test allocating with a size larger than the initial slab size.
118TEST(AllocatorTest, TestSmallSlabSize) {
119  BumpPtrAllocator Alloc;
120
121  Alloc.Allocate(8000, 1);
122  EXPECT_EQ(1U, Alloc.GetNumSlabs());
123}
124
125// Test requesting alignment that goes past the end of the current slab.
126TEST(AllocatorTest, TestAlignmentPastSlab) {
127  BumpPtrAllocator Alloc;
128  Alloc.Allocate(4095, 1);
129
130  // Aligning the current slab pointer is likely to move it past the end of the
131  // slab, which would confuse any unsigned comparisons with the difference of
132  // the end pointer and the aligned pointer.
133  Alloc.Allocate(1024, 8192);
134
135  EXPECT_EQ(2U, Alloc.GetNumSlabs());
136}
137
138// Mock slab allocator that returns slabs aligned on 4096 bytes.  There is no
139// easy portable way to do this, so this is kind of a hack.
140class MockSlabAllocator {
141  static size_t LastSlabSize;
142
143public:
144  ~MockSlabAllocator() { }
145
146  void *Allocate(size_t Size, size_t /*Alignment*/) {
147    // Allocate space for the alignment, the slab, and a void* that goes right
148    // before the slab.
149    size_t Alignment = 4096;
150    void *MemBase = malloc(Size + Alignment - 1 + sizeof(void*));
151
152    // Find the slab start.
153    void *Slab = (void *)alignAddr((char*)MemBase + sizeof(void *), Alignment);
154
155    // Hold a pointer to the base so we can free the whole malloced block.
156    ((void**)Slab)[-1] = MemBase;
157
158    LastSlabSize = Size;
159    return Slab;
160  }
161
162  void Deallocate(void *Slab, size_t Size) {
163    free(((void**)Slab)[-1]);
164  }
165
166  static size_t GetLastSlabSize() { return LastSlabSize; }
167};
168
169size_t MockSlabAllocator::LastSlabSize = 0;
170
171// Allocate a large-ish block with a really large alignment so that the
172// allocator will think that it has space, but after it does the alignment it
173// will not.
174TEST(AllocatorTest, TestBigAlignment) {
175  BumpPtrAllocatorImpl<MockSlabAllocator> Alloc;
176
177  // First allocate a tiny bit to ensure we have to re-align things.
178  (void)Alloc.Allocate(1, 1);
179
180  // Now the big chunk with a big alignment.
181  (void)Alloc.Allocate(3000, 2048);
182
183  // We test that the last slab size is not the default 4096 byte slab, but
184  // rather a custom sized slab that is larger.
185  EXPECT_GT(MockSlabAllocator::GetLastSlabSize(), 4096u);
186}
187
188}  // anonymous namespace
189