Home | History | Annotate | Download | only in Support
      1 //===--- Allocator.h - Simple memory allocation abstraction -----*- C++ -*-===//
      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 // This file defines the MallocAllocator and BumpPtrAllocator interfaces.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #ifndef LLVM_SUPPORT_ALLOCATOR_H
     15 #define LLVM_SUPPORT_ALLOCATOR_H
     16 
     17 #include "llvm/Support/AlignOf.h"
     18 #include "llvm/Support/DataTypes.h"
     19 #include "llvm/Support/MathExtras.h"
     20 #include <algorithm>
     21 #include <cassert>
     22 #include <cstddef>
     23 #include <cstdlib>
     24 
     25 namespace llvm {
     26 template <typename T> struct ReferenceAdder { typedef T& result; };
     27 template <typename T> struct ReferenceAdder<T&> { typedef T result; };
     28 
     29 class MallocAllocator {
     30 public:
     31   MallocAllocator() {}
     32   ~MallocAllocator() {}
     33 
     34   void Reset() {}
     35 
     36   void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
     37 
     38   template <typename T>
     39   T *Allocate() { return static_cast<T*>(malloc(sizeof(T))); }
     40 
     41   template <typename T>
     42   T *Allocate(size_t Num) {
     43     return static_cast<T*>(malloc(sizeof(T)*Num));
     44   }
     45 
     46   void Deallocate(const void *Ptr) { free(const_cast<void*>(Ptr)); }
     47 
     48   void PrintStats() const {}
     49 };
     50 
     51 /// MemSlab - This structure lives at the beginning of every slab allocated by
     52 /// the bump allocator.
     53 class MemSlab {
     54 public:
     55   size_t Size;
     56   MemSlab *NextPtr;
     57 };
     58 
     59 /// SlabAllocator - This class can be used to parameterize the underlying
     60 /// allocation strategy for the bump allocator.  In particular, this is used
     61 /// by the JIT to allocate contiguous swathes of executable memory.  The
     62 /// interface uses MemSlab's instead of void *'s so that the allocator
     63 /// doesn't have to remember the size of the pointer it allocated.
     64 class SlabAllocator {
     65 public:
     66   virtual ~SlabAllocator();
     67   virtual MemSlab *Allocate(size_t Size) = 0;
     68   virtual void Deallocate(MemSlab *Slab) = 0;
     69 };
     70 
     71 /// MallocSlabAllocator - The default slab allocator for the bump allocator
     72 /// is an adapter class for MallocAllocator that just forwards the method
     73 /// calls and translates the arguments.
     74 class MallocSlabAllocator : public SlabAllocator {
     75   /// Allocator - The underlying allocator that we forward to.
     76   ///
     77   MallocAllocator Allocator;
     78 
     79 public:
     80   MallocSlabAllocator() : Allocator() { }
     81   virtual ~MallocSlabAllocator();
     82   virtual MemSlab *Allocate(size_t Size) LLVM_OVERRIDE;
     83   virtual void Deallocate(MemSlab *Slab) LLVM_OVERRIDE;
     84 };
     85 
     86 /// BumpPtrAllocator - This allocator is useful for containers that need
     87 /// very simple memory allocation strategies.  In particular, this just keeps
     88 /// allocating memory, and never deletes it until the entire block is dead. This
     89 /// makes allocation speedy, but must only be used when the trade-off is ok.
     90 class BumpPtrAllocator {
     91   BumpPtrAllocator(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
     92   void operator=(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
     93 
     94   /// SlabSize - Allocate data into slabs of this size unless we get an
     95   /// allocation above SizeThreshold.
     96   size_t SlabSize;
     97 
     98   /// SizeThreshold - For any allocation larger than this threshold, we should
     99   /// allocate a separate slab.
    100   size_t SizeThreshold;
    101 
    102   /// Allocator - The underlying allocator we use to get slabs of memory.  This
    103   /// defaults to MallocSlabAllocator, which wraps malloc, but it could be
    104   /// changed to use a custom allocator.
    105   SlabAllocator &Allocator;
    106 
    107   /// CurSlab - The slab that we are currently allocating into.
    108   ///
    109   MemSlab *CurSlab;
    110 
    111   /// CurPtr - The current pointer into the current slab.  This points to the
    112   /// next free byte in the slab.
    113   char *CurPtr;
    114 
    115   /// End - The end of the current slab.
    116   ///
    117   char *End;
    118 
    119   /// BytesAllocated - This field tracks how many bytes we've allocated, so
    120   /// that we can compute how much space was wasted.
    121   size_t BytesAllocated;
    122 
    123   /// AlignPtr - Align Ptr to Alignment bytes, rounding up.  Alignment should
    124   /// be a power of two.  This method rounds up, so AlignPtr(7, 4) == 8 and
    125   /// AlignPtr(8, 4) == 8.
    126   static char *AlignPtr(char *Ptr, size_t Alignment);
    127 
    128   /// StartNewSlab - Allocate a new slab and move the bump pointers over into
    129   /// the new slab.  Modifies CurPtr and End.
    130   void StartNewSlab();
    131 
    132   /// DeallocateSlabs - Deallocate all memory slabs after and including this
    133   /// one.
    134   void DeallocateSlabs(MemSlab *Slab);
    135 
    136   static MallocSlabAllocator DefaultSlabAllocator;
    137 
    138   template<typename T> friend class SpecificBumpPtrAllocator;
    139 public:
    140   BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096,
    141                    SlabAllocator &allocator = DefaultSlabAllocator);
    142   ~BumpPtrAllocator();
    143 
    144   /// Reset - Deallocate all but the current slab and reset the current pointer
    145   /// to the beginning of it, freeing all memory allocated so far.
    146   void Reset();
    147 
    148   /// Allocate - Allocate space at the specified alignment.
    149   ///
    150   void *Allocate(size_t Size, size_t Alignment);
    151 
    152   /// Allocate space, but do not construct, one object.
    153   ///
    154   template <typename T>
    155   T *Allocate() {
    156     return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment));
    157   }
    158 
    159   /// Allocate space for an array of objects.  This does not construct the
    160   /// objects though.
    161   template <typename T>
    162   T *Allocate(size_t Num) {
    163     return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
    164   }
    165 
    166   /// Allocate space for a specific count of elements and with a specified
    167   /// alignment.
    168   template <typename T>
    169   T *Allocate(size_t Num, size_t Alignment) {
    170     // Round EltSize up to the specified alignment.
    171     size_t EltSize = (sizeof(T)+Alignment-1)&(-Alignment);
    172     return static_cast<T*>(Allocate(Num * EltSize, Alignment));
    173   }
    174 
    175   void Deallocate(const void * /*Ptr*/) {}
    176 
    177   unsigned GetNumSlabs() const;
    178 
    179   void PrintStats() const;
    180 
    181   /// Compute the total physical memory allocated by this allocator.
    182   size_t getTotalMemory() const;
    183 };
    184 
    185 /// SpecificBumpPtrAllocator - Same as BumpPtrAllocator but allows only
    186 /// elements of one type to be allocated. This allows calling the destructor
    187 /// in DestroyAll() and when the allocator is destroyed.
    188 template <typename T>
    189 class SpecificBumpPtrAllocator {
    190   BumpPtrAllocator Allocator;
    191 public:
    192   SpecificBumpPtrAllocator(size_t size = 4096, size_t threshold = 4096,
    193               SlabAllocator &allocator = BumpPtrAllocator::DefaultSlabAllocator)
    194     : Allocator(size, threshold, allocator) {}
    195 
    196   ~SpecificBumpPtrAllocator() {
    197     DestroyAll();
    198   }
    199 
    200   /// Call the destructor of each allocated object and deallocate all but the
    201   /// current slab and reset the current pointer to the beginning of it, freeing
    202   /// all memory allocated so far.
    203   void DestroyAll() {
    204     MemSlab *Slab = Allocator.CurSlab;
    205     while (Slab) {
    206       char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr :
    207                                               (char *)Slab + Slab->Size;
    208       for (char *Ptr = (char*)(Slab+1); Ptr < End; Ptr += sizeof(T)) {
    209         Ptr = Allocator.AlignPtr(Ptr, alignOf<T>());
    210         if (Ptr + sizeof(T) <= End)
    211           reinterpret_cast<T*>(Ptr)->~T();
    212       }
    213       Slab = Slab->NextPtr;
    214     }
    215     Allocator.Reset();
    216   }
    217 
    218   /// Allocate space for a specific count of elements.
    219   T *Allocate(size_t num = 1) {
    220     return Allocator.Allocate<T>(num);
    221   }
    222 };
    223 
    224 }  // end namespace llvm
    225 
    226 inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
    227   struct S {
    228     char c;
    229     union {
    230       double D;
    231       long double LD;
    232       long long L;
    233       void *P;
    234     } x;
    235   };
    236   return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
    237                                            offsetof(S, x)));
    238 }
    239 
    240 inline void operator delete(void *, llvm::BumpPtrAllocator &) {}
    241 
    242 #endif // LLVM_SUPPORT_ALLOCATOR_H
    243