18f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner//===- llvm/unittest/Support/AllocatorTest.cpp - BumpPtrAllocator tests ---===// 28f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// 38f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// The LLVM Compiler Infrastructure 48f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// 58f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// This file is distributed under the University of Illinois Open Source 68f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// License. See LICENSE.TXT for details. 78f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// 88f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner//===----------------------------------------------------------------------===// 98f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 108f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner#include "llvm/Support/Allocator.h" 118f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner#include "gtest/gtest.h" 127d509134dcec17f6094032196b21af5c67943f0fReid Kleckner#include <cstdlib> 138f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 148f51a62b41a425f7fe262ff20cee835129ecc072Reid Klecknerusing namespace llvm; 158f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 168f51a62b41a425f7fe262ff20cee835129ecc072Reid Klecknernamespace { 178f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 188f51a62b41a425f7fe262ff20cee835129ecc072Reid KlecknerTEST(AllocatorTest, Basics) { 198f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner BumpPtrAllocator Alloc; 208f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner int *a = (int*)Alloc.Allocate(sizeof(int), 0); 218f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner int *b = (int*)Alloc.Allocate(sizeof(int) * 10, 0); 228f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner int *c = (int*)Alloc.Allocate(sizeof(int), 0); 238f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner *a = 1; 248f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner b[0] = 2; 258f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner b[9] = 2; 268f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner *c = 3; 278f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(1, *a); 288f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(2, b[0]); 298f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(2, b[9]); 308f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(3, *c); 318f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(1U, Alloc.GetNumSlabs()); 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BumpPtrAllocator Alloc2 = std::move(Alloc); 34dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(0U, Alloc.GetNumSlabs()); 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(1U, Alloc2.GetNumSlabs()); 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Make sure the old pointers still work. These are especially interesting 38dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // under ASan or Valgrind. 39dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(1, *a); 40dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(2, b[0]); 41dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(2, b[9]); 42dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(3, *c); 43dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 44dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Alloc = std::move(Alloc2); 45dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(0U, Alloc2.GetNumSlabs()); 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_EQ(1U, Alloc.GetNumSlabs()); 478f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} 488f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 498f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// Allocate enough bytes to create three slabs. 508f51a62b41a425f7fe262ff20cee835129ecc072Reid KlecknerTEST(AllocatorTest, ThreeSlabs) { 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BumpPtrAllocator Alloc; 528f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Alloc.Allocate(3000, 0); 538f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(1U, Alloc.GetNumSlabs()); 548f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Alloc.Allocate(3000, 0); 558f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(2U, Alloc.GetNumSlabs()); 568f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Alloc.Allocate(3000, 0); 578f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(3U, Alloc.GetNumSlabs()); 588f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} 598f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 608f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// Allocate enough bytes to create two slabs, reset the allocator, and do it 618f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// again. 628f51a62b41a425f7fe262ff20cee835129ecc072Reid KlecknerTEST(AllocatorTest, TestReset) { 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BumpPtrAllocator Alloc; 648f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Alloc.Allocate(3000, 0); 658f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(1U, Alloc.GetNumSlabs()); 668f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Alloc.Allocate(3000, 0); 678f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(2U, Alloc.GetNumSlabs()); 688f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Alloc.Reset(); 698f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(1U, Alloc.GetNumSlabs()); 708f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Alloc.Allocate(3000, 0); 718f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(1U, Alloc.GetNumSlabs()); 728f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Alloc.Allocate(3000, 0); 738f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(2U, Alloc.GetNumSlabs()); 748f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} 758f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 768f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// Test some allocations at varying alignments. 778f51a62b41a425f7fe262ff20cee835129ecc072Reid KlecknerTEST(AllocatorTest, TestAlignment) { 788f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner BumpPtrAllocator Alloc; 798f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner uintptr_t a; 808f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner a = (uintptr_t)Alloc.Allocate(1, 2); 818f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(0U, a & 1); 828f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner a = (uintptr_t)Alloc.Allocate(1, 4); 838f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(0U, a & 3); 848f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner a = (uintptr_t)Alloc.Allocate(1, 8); 858f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(0U, a & 7); 868f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner a = (uintptr_t)Alloc.Allocate(1, 16); 878f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(0U, a & 15); 888f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner a = (uintptr_t)Alloc.Allocate(1, 32); 898f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(0U, a & 31); 908f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner a = (uintptr_t)Alloc.Allocate(1, 64); 918f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(0U, a & 63); 928f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner a = (uintptr_t)Alloc.Allocate(1, 128); 938f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(0U, a & 127); 948f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} 958f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 968f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// Test allocating just over the slab size. This tests a bug where before the 978f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner// allocator incorrectly calculated the buffer end pointer. 988f51a62b41a425f7fe262ff20cee835129ecc072Reid KlecknerTEST(AllocatorTest, TestOverflow) { 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BumpPtrAllocator Alloc; 1008f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1018f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // Fill the slab right up until the end pointer. 102dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Alloc.Allocate(4096, 0); 1038f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(1U, Alloc.GetNumSlabs()); 1048f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 10585f1968138839156c4bad3f7d186a7cb4dc4e57fDan Gohman // If we don't allocate a new slab, then we will have overflowed. 1068f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Alloc.Allocate(1, 0); 1078f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner EXPECT_EQ(2U, Alloc.GetNumSlabs()); 1088f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} 1098f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 110680458275fd6c05ce3683d86483eff1254d0df80Argyrios Kyrtzidis// Test allocating with a size larger than the initial slab size. 111680458275fd6c05ce3683d86483eff1254d0df80Argyrios KyrtzidisTEST(AllocatorTest, TestSmallSlabSize) { 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BumpPtrAllocator Alloc; 113680458275fd6c05ce3683d86483eff1254d0df80Argyrios Kyrtzidis 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Alloc.Allocate(8000, 0); 11597e910ecff5ed8b653a07fb1d014dab772931c0bBenjamin Kramer EXPECT_EQ(2U, Alloc.GetNumSlabs()); 116680458275fd6c05ce3683d86483eff1254d0df80Argyrios Kyrtzidis} 117680458275fd6c05ce3683d86483eff1254d0df80Argyrios Kyrtzidis 1187d509134dcec17f6094032196b21af5c67943f0fReid Kleckner// Mock slab allocator that returns slabs aligned on 4096 bytes. There is no 1197d509134dcec17f6094032196b21af5c67943f0fReid Kleckner// easy portable way to do this, so this is kind of a hack. 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesclass MockSlabAllocator { 121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static size_t LastSlabSize; 1227d509134dcec17f6094032196b21af5c67943f0fReid Kleckner 1237d509134dcec17f6094032196b21af5c67943f0fReid Klecknerpublic: 124dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ~MockSlabAllocator() { } 1257d509134dcec17f6094032196b21af5c67943f0fReid Kleckner 126dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void *Allocate(size_t Size, size_t /*Alignment*/) { 1277d509134dcec17f6094032196b21af5c67943f0fReid Kleckner // Allocate space for the alignment, the slab, and a void* that goes right 1287d509134dcec17f6094032196b21af5c67943f0fReid Kleckner // before the slab. 1297d509134dcec17f6094032196b21af5c67943f0fReid Kleckner size_t Alignment = 4096; 1307d509134dcec17f6094032196b21af5c67943f0fReid Kleckner void *MemBase = malloc(Size + Alignment - 1 + sizeof(void*)); 1317d509134dcec17f6094032196b21af5c67943f0fReid Kleckner 132dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Find the slab start. 133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void *Slab = alignPtr((char *)MemBase + sizeof(void *), Alignment); 1347d509134dcec17f6094032196b21af5c67943f0fReid Kleckner 1357d509134dcec17f6094032196b21af5c67943f0fReid Kleckner // Hold a pointer to the base so we can free the whole malloced block. 1367d509134dcec17f6094032196b21af5c67943f0fReid Kleckner ((void**)Slab)[-1] = MemBase; 1377d509134dcec17f6094032196b21af5c67943f0fReid Kleckner 138dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LastSlabSize = Size; 1397d509134dcec17f6094032196b21af5c67943f0fReid Kleckner return Slab; 1407d509134dcec17f6094032196b21af5c67943f0fReid Kleckner } 1417d509134dcec17f6094032196b21af5c67943f0fReid Kleckner 142dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void Deallocate(void *Slab, size_t Size) { 1437d509134dcec17f6094032196b21af5c67943f0fReid Kleckner free(((void**)Slab)[-1]); 1447d509134dcec17f6094032196b21af5c67943f0fReid Kleckner } 1457d509134dcec17f6094032196b21af5c67943f0fReid Kleckner 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static size_t GetLastSlabSize() { return LastSlabSize; } 1477d509134dcec17f6094032196b21af5c67943f0fReid Kleckner}; 1487d509134dcec17f6094032196b21af5c67943f0fReid Kleckner 149dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinessize_t MockSlabAllocator::LastSlabSize = 0; 150dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1517d509134dcec17f6094032196b21af5c67943f0fReid Kleckner// Allocate a large-ish block with a really large alignment so that the 1527d509134dcec17f6094032196b21af5c67943f0fReid Kleckner// allocator will think that it has space, but after it does the alignment it 1537d509134dcec17f6094032196b21af5c67943f0fReid Kleckner// will not. 1547d509134dcec17f6094032196b21af5c67943f0fReid KlecknerTEST(AllocatorTest, TestBigAlignment) { 155dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BumpPtrAllocatorImpl<MockSlabAllocator> Alloc; 156dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 157dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // First allocate a tiny bit to ensure we have to re-align things. 158dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (void)Alloc.Allocate(1, 0); 159dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 160dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Now the big chunk with a big alignment. 161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (void)Alloc.Allocate(3000, 2048); 162dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // We test that the last slab size is not the default 4096 byte slab, but 164dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // rather a custom sized slab that is larger. 165dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EXPECT_GT(MockSlabAllocator::GetLastSlabSize(), 4096u); 1667d509134dcec17f6094032196b21af5c67943f0fReid Kleckner} 1677d509134dcec17f6094032196b21af5c67943f0fReid Kleckner 1688f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} // anonymous namespace 169