include/llvm/Support/Allocator.h

   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   MemSlab *Allocate(size_t Size) override;
  83   void Deallocate(MemSlab *Slab) override;
  84 };
  85
  86 /// \brief Allocate memory in an ever growing pool, as if by bump-pointer.
  87 ///
  88 /// This isn't strictly a bump-pointer allocator as it uses backing slabs of
  89 /// memory rather than relying on boundless contiguous heap. However, it has
  90 /// bump-pointer semantics in that is a monotonically growing pool of memory
  91 /// where every allocation is found by merely allocating the next N bytes in
  92 /// the slab, or the next N bytes in the next slab.
  93 ///
  94 /// Note that this also has a threshold for forcing allocations above a certain
  95 /// size into their own slab.
  96 class BumpPtrAllocator {
  97   BumpPtrAllocator(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
  98   void operator=(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
  99
 100   /// \brief Allocate at least this many bytes of memory in a slab.
 101   size_t SlabSize;
 102
 103   /// \brief Threshold above which allocations to go into a dedicated slab.
 104   size_t SizeThreshold;
 105
 106   /// \brief The default allocator used if one is not provided.
 107   MallocSlabAllocator DefaultSlabAllocator;
 108
 109   /// \brief The underlying allocator we use to get slabs of memory.
 110   ///
 111   /// This defaults to MallocSlabAllocator, which wraps malloc, but it could be
 112   /// changed to use a custom allocator.
 113   SlabAllocator &Allocator;
 114
 115   /// \brief The slab that we are currently allocating into.
 116   MemSlab *CurSlab;
 117
 118   /// \brief The current pointer into the current slab.
 119   ///
 120   /// This points to the next free byte in the slab.
 121   char *CurPtr;
 122
 123   /// \brief The end of the current slab.
 124   char *End;
 125
 126   /// \brief How many bytes we've allocated.
 127   ///
 128   /// Used so that we can compute how much space was wasted.
 129   size_t BytesAllocated;
 130
 131   /// \brief Aligns \c Ptr to \c Alignment bytes, rounding up.
 132   ///
 133   /// Alignment should be a power of two.  This method rounds up, so
 134   /// AlignPtr(7, 4) == 8 and AlignPtr(8, 4) == 8.
 135   static char *AlignPtr(char *Ptr, size_t Alignment);
 136
 137   /// \brief Allocate a new slab and move the bump pointers over into the new
 138   /// slab, modifying CurPtr and End.
 139   void StartNewSlab();
 140
 141   /// \brief Deallocate all memory slabs after and including this one.
 142   void DeallocateSlabs(MemSlab *Slab);
 143
 144   template<typename T> friend class SpecificBumpPtrAllocator;
 145 public:
 146   BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096);
 147   BumpPtrAllocator(size_t size, size_t threshold, SlabAllocator &allocator);
 148   ~BumpPtrAllocator();
 149
 150   /// \brief Deallocate all but the current slab and reset the current pointer
 151   /// to the beginning of it, freeing all memory allocated so far.
 152   void Reset();
 153
 154   /// \brief Allocate space at the specified alignment.
 155   void *Allocate(size_t Size, size_t Alignment);
 156
 157   /// \brief Allocate space for one object without constructing it.
 158   template <typename T>
 159   T *Allocate() {
 160     return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment));
 161   }
 162
 163   /// \brief Allocate space for an array of objects without constructing them.
 164   template <typename T>
 165   T *Allocate(size_t Num) {
 166     return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
 167   }
 168
 169   /// \brief Allocate space for an array of objects with the specified alignment
 170   /// and without constructing them.
 171   template <typename T>
 172   T *Allocate(size_t Num, size_t Alignment) {
 173     // Round EltSize up to the specified alignment.
 174     size_t EltSize = (sizeof(T)+Alignment-1)&(-Alignment);
 175     return static_cast<T*>(Allocate(Num * EltSize, Alignment));
 176   }
 177
 178   void Deallocate(const void * /*Ptr*/) {}
 179
 180   unsigned GetNumSlabs() const;
 181
 182   void PrintStats() const;
 183
 184   /// \brief Returns the total physical memory allocated by this allocator.
 185   size_t getTotalMemory() const;
 186 };
 187
 188 /// \brief A BumpPtrAllocator that allows only elements of a specific type to be
 189 /// allocated.
 190 ///
 191 /// This allows calling the destructor in DestroyAll() and when the allocator is
 192 /// destroyed.
 193 template <typename T>
 194 class SpecificBumpPtrAllocator {
 195   BumpPtrAllocator Allocator;
 196 public:
 197   SpecificBumpPtrAllocator(size_t size = 4096, size_t threshold = 4096)
 198     : Allocator(size, threshold) {}
 199   SpecificBumpPtrAllocator(size_t size, size_t threshold,
 200                            SlabAllocator &allocator)
 201     : Allocator(size, threshold, allocator) {}
 202
 203   ~SpecificBumpPtrAllocator() {
 204     DestroyAll();
 205   }
 206
 207   /// Call the destructor of each allocated object and deallocate all but the
 208   /// current slab and reset the current pointer to the beginning of it, freeing
 209   /// all memory allocated so far.
 210   void DestroyAll() {
 211     MemSlab *Slab = Allocator.CurSlab;
 212     while (Slab) {
 213       char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr :
 214                                               (char *)Slab + Slab->Size;
 215       for (char *Ptr = (char*)(Slab+1); Ptr < End; Ptr += sizeof(T)) {
 216         Ptr = Allocator.AlignPtr(Ptr, alignOf<T>());
 217         if (Ptr + sizeof(T) <= End)
 218           reinterpret_cast<T*>(Ptr)->~T();
 219       }
 220       Slab = Slab->NextPtr;
 221     }
 222     Allocator.Reset();
 223   }
 224
 225   /// \brief Allocate space for an array of objects without constructing them.
 226   T *Allocate(size_t num = 1) {
 227     return Allocator.Allocate<T>(num);
 228   }
 229 };
 230
 231 }  // end namespace llvm
 232
 233 inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
 234   struct S {
 235     char c;
 236     union {
 237       double D;
 238       long double LD;
 239       long long L;
 240       void *P;
 241     } x;
 242   };
 243   return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
 244                                            offsetof(S, x)));
 245 }
 246
 247 inline void operator delete(void *, llvm::BumpPtrAllocator &) {}
 248
 249 #endif // LLVM_SUPPORT_ALLOCATOR_H