Home | History | Annotate | Download | only in Support 
      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 
     12 #include "gtest/gtest.h"
     13 #include <cstdlib>
     14 
     15 using namespace llvm;
     16 
     17 namespace {
     18 
     19 TEST(AllocatorTest, Basics) {
     20   BumpPtrAllocator Alloc;
     21   int *a = (int*)Alloc.Allocate(sizeof(int), 0);
     22   int *b = (int*)Alloc.Allocate(sizeof(int) * 10, 0);
     23   int *c = (int*)Alloc.Allocate(sizeof(int), 0);
     24   *a = 1;
     25   b[0] = 2;
     26   b[9] = 2;
     27   *c = 3;
     28   EXPECT_EQ(1, *a);
     29   EXPECT_EQ(2, b[0]);
     30   EXPECT_EQ(2, b[9]);
     31   EXPECT_EQ(3, *c);
     32   EXPECT_EQ(1U, Alloc.GetNumSlabs());
     33 }
     34 
     35 // Allocate enough bytes to create three slabs.
     36 TEST(AllocatorTest, ThreeSlabs) {
     37   BumpPtrAllocator Alloc(4096, 4096);
     38   Alloc.Allocate(3000, 0);
     39   EXPECT_EQ(1U, Alloc.GetNumSlabs());
     40   Alloc.Allocate(3000, 0);
     41   EXPECT_EQ(2U, Alloc.GetNumSlabs());
     42   Alloc.Allocate(3000, 0);
     43   EXPECT_EQ(3U, Alloc.GetNumSlabs());
     44 }
     45 
     46 // Allocate enough bytes to create two slabs, reset the allocator, and do it
     47 // again.
     48 TEST(AllocatorTest, TestReset) {
     49   BumpPtrAllocator Alloc(4096, 4096);
     50   Alloc.Allocate(3000, 0);
     51   EXPECT_EQ(1U, Alloc.GetNumSlabs());
     52   Alloc.Allocate(3000, 0);
     53   EXPECT_EQ(2U, Alloc.GetNumSlabs());
     54   Alloc.Reset();
     55   EXPECT_EQ(1U, Alloc.GetNumSlabs());
     56   Alloc.Allocate(3000, 0);
     57   EXPECT_EQ(1U, Alloc.GetNumSlabs());
     58   Alloc.Allocate(3000, 0);
     59   EXPECT_EQ(2U, Alloc.GetNumSlabs());
     60 }
     61 
     62 // Test some allocations at varying alignments.
     63 TEST(AllocatorTest, TestAlignment) {
     64   BumpPtrAllocator Alloc;
     65   uintptr_t a;
     66   a = (uintptr_t)Alloc.Allocate(1, 2);
     67   EXPECT_EQ(0U, a & 1);
     68   a = (uintptr_t)Alloc.Allocate(1, 4);
     69   EXPECT_EQ(0U, a & 3);
     70   a = (uintptr_t)Alloc.Allocate(1, 8);
     71   EXPECT_EQ(0U, a & 7);
     72   a = (uintptr_t)Alloc.Allocate(1, 16);
     73   EXPECT_EQ(0U, a & 15);
     74   a = (uintptr_t)Alloc.Allocate(1, 32);
     75   EXPECT_EQ(0U, a & 31);
     76   a = (uintptr_t)Alloc.Allocate(1, 64);
     77   EXPECT_EQ(0U, a & 63);
     78   a = (uintptr_t)Alloc.Allocate(1, 128);
     79   EXPECT_EQ(0U, a & 127);
     80 }
     81 
     82 // Test allocating just over the slab size.  This tests a bug where before the
     83 // allocator incorrectly calculated the buffer end pointer.
     84 TEST(AllocatorTest, TestOverflow) {
     85   BumpPtrAllocator Alloc(4096, 4096);
     86 
     87   // Fill the slab right up until the end pointer.
     88   Alloc.Allocate(4096 - sizeof(MemSlab), 0);
     89   EXPECT_EQ(1U, Alloc.GetNumSlabs());
     90 
     91   // If we don't allocate a new slab, then we will have overflowed.
     92   Alloc.Allocate(1, 0);
     93   EXPECT_EQ(2U, Alloc.GetNumSlabs());
     94 }
     95 
     96 // Test allocating with a size larger than the initial slab size.
     97 TEST(AllocatorTest, TestSmallSlabSize) {
     98   BumpPtrAllocator Alloc(128);
     99 
    100   Alloc.Allocate(200, 0);
    101   EXPECT_EQ(2U, Alloc.GetNumSlabs());
    102 }
    103 
    104 // Mock slab allocator that returns slabs aligned on 4096 bytes.  There is no
    105 // easy portable way to do this, so this is kind of a hack.
    106 class MockSlabAllocator : public SlabAllocator {
    107   MemSlab *LastSlab;
    108 
    109 public:
    110   virtual ~MockSlabAllocator() { }
    111 
    112   virtual MemSlab *Allocate(size_t Size) {
    113     // Allocate space for the alignment, the slab, and a void* that goes right
    114     // before the slab.
    115     size_t Alignment = 4096;
    116     void *MemBase = malloc(Size + Alignment - 1 + sizeof(void*));
    117 
    118     // Make the slab.
    119     MemSlab *Slab = (MemSlab*)(((uintptr_t)MemBase+sizeof(void*)+Alignment-1) &
    120                                ~(uintptr_t)(Alignment - 1));
    121     Slab->Size = Size;
    122     Slab->NextPtr = 0;
    123 
    124     // Hold a pointer to the base so we can free the whole malloced block.
    125     ((void**)Slab)[-1] = MemBase;
    126 
    127     LastSlab = Slab;
    128     return Slab;
    129   }
    130 
    131   virtual void Deallocate(MemSlab *Slab) {
    132     free(((void**)Slab)[-1]);
    133   }
    134 
    135   MemSlab *GetLastSlab() {
    136     return LastSlab;
    137   }
    138 };
    139 
    140 // Allocate a large-ish block with a really large alignment so that the
    141 // allocator will think that it has space, but after it does the alignment it
    142 // will not.
    143 TEST(AllocatorTest, TestBigAlignment) {
    144   MockSlabAllocator SlabAlloc;
    145   BumpPtrAllocator Alloc(4096, 4096, SlabAlloc);
    146   uintptr_t Ptr = (uintptr_t)Alloc.Allocate(3000, 2048);
    147   MemSlab *Slab = SlabAlloc.GetLastSlab();
    148   EXPECT_LE(Ptr + 3000, ((uintptr_t)Slab) + Slab->Size);
    149 }
    150 
    151 }  // anonymous namespace
    152