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 // Mock slab allocator that returns slabs aligned on 4096 bytes.  There is no
     97 // easy portable way to do this, so this is kind of a hack.
     98 class MockSlabAllocator : public SlabAllocator {
     99   MemSlab *LastSlab;
    100 
    101 public:
    102   virtual ~MockSlabAllocator() { }
    103 
    104   virtual MemSlab *Allocate(size_t Size) {
    105     // Allocate space for the alignment, the slab, and a void* that goes right
    106     // before the slab.
    107     size_t Alignment = 4096;
    108     void *MemBase = malloc(Size + Alignment - 1 + sizeof(void*));
    109 
    110     // Make the slab.
    111     MemSlab *Slab = (MemSlab*)(((uintptr_t)MemBase+sizeof(void*)+Alignment-1) &
    112                                ~(uintptr_t)(Alignment - 1));
    113     Slab->Size = Size;
    114     Slab->NextPtr = 0;
    115 
    116     // Hold a pointer to the base so we can free the whole malloced block.
    117     ((void**)Slab)[-1] = MemBase;
    118 
    119     LastSlab = Slab;
    120     return Slab;
    121   }
    122 
    123   virtual void Deallocate(MemSlab *Slab) {
    124     free(((void**)Slab)[-1]);
    125   }
    126 
    127   MemSlab *GetLastSlab() {
    128     return LastSlab;
    129   }
    130 };
    131 
    132 // Allocate a large-ish block with a really large alignment so that the
    133 // allocator will think that it has space, but after it does the alignment it
    134 // will not.
    135 TEST(AllocatorTest, TestBigAlignment) {
    136   MockSlabAllocator SlabAlloc;
    137   BumpPtrAllocator Alloc(4096, 4096, SlabAlloc);
    138   uintptr_t Ptr = (uintptr_t)Alloc.Allocate(3000, 2048);
    139   MemSlab *Slab = SlabAlloc.GetLastSlab();
    140   EXPECT_LE(Ptr + 3000, ((uintptr_t)Slab) + Slab->Size);
    141 }
    142 
    143 }  // anonymous namespace
    144