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 {
  27   typedef T &result;
  28 };
  29 template <typename T> struct ReferenceAdder<T &> {
  30   typedef T result;
  31 };
  32
  33 class MallocAllocator {
  34 public:
  35   MallocAllocator() {}
  36   ~MallocAllocator() {}
  37
  38   void Reset() {}
  39
  40   void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
  41
  42   template <typename T> T *Allocate() {
  43     return static_cast<T *>(malloc(sizeof(T)));
  44   }
  45
  46   template <typename T> T *Allocate(size_t Num) {
  47     return static_cast<T *>(malloc(sizeof(T) * Num));
  48   }
  49
  50   void Deallocate(const void *Ptr) { free(const_cast<void *>(Ptr)); }
  51
  52   void PrintStats() const {}
  53 };
  54
  55 /// MemSlab - This structure lives at the beginning of every slab allocated by
  56 /// the bump allocator.
  57 class MemSlab {
  58 public:
  59   size_t Size;
  60   MemSlab *NextPtr;
  61 };
  62
  63 /// SlabAllocator - This class can be used to parameterize the underlying
  64 /// allocation strategy for the bump allocator.  In particular, this is used
  65 /// by the JIT to allocate contiguous swathes of executable memory.  The
  66 /// interface uses MemSlab's instead of void *'s so that the allocator
  67 /// doesn't have to remember the size of the pointer it allocated.
  68 class SlabAllocator {
  69 public:
  70   virtual ~SlabAllocator();
  71   virtual MemSlab *Allocate(size_t Size) = 0;
  72   virtual void Deallocate(MemSlab *Slab) = 0;
  73 };
  74
  75 /// MallocSlabAllocator - The default slab allocator for the bump allocator
  76 /// is an adapter class for MallocAllocator that just forwards the method
  77 /// calls and translates the arguments.
  78 class MallocSlabAllocator : public SlabAllocator {
  79   /// Allocator - The underlying allocator that we forward to.
  80   ///
  81   MallocAllocator Allocator;
  82
  83 public:
  84   MallocSlabAllocator() : Allocator() {}
  85   virtual ~MallocSlabAllocator();
  86   MemSlab *Allocate(size_t Size) override;
  87   void Deallocate(MemSlab *Slab) override;
  88 };
  89
  90 /// \brief Allocate memory in an ever growing pool, as if by bump-pointer.
  91 ///
  92 /// This isn't strictly a bump-pointer allocator as it uses backing slabs of
  93 /// memory rather than relying on boundless contiguous heap. However, it has
  94 /// bump-pointer semantics in that is a monotonically growing pool of memory
  95 /// where every allocation is found by merely allocating the next N bytes in
  96 /// the slab, or the next N bytes in the next slab.
  97 ///
  98 /// Note that this also has a threshold for forcing allocations above a certain
  99 /// size into their own slab.
 100 class BumpPtrAllocator {
 101   BumpPtrAllocator(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
 102   void operator=(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
 103
 104 public:
 105   BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096);
 106   BumpPtrAllocator(size_t size, size_t threshold, SlabAllocator &allocator);
 107   ~BumpPtrAllocator();
 108
 109   /// \brief Deallocate all but the current slab and reset the current pointer
 110   /// to the beginning of it, freeing all memory allocated so far.
 111   void Reset();
 112
 113   /// \brief Allocate space at the specified alignment.
 114   void *Allocate(size_t Size, size_t Alignment);
 115
 116   /// \brief Allocate space for one object without constructing it.
 117   template <typename T> T *Allocate() {
 118     return static_cast<T *>(Allocate(sizeof(T), AlignOf<T>::Alignment));
 119   }
 120
 121   /// \brief Allocate space for an array of objects without constructing them.
 122   template <typename T> T *Allocate(size_t Num) {
 123     return static_cast<T *>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
 124   }
 125
 126   /// \brief Allocate space for an array of objects with the specified alignment
 127   /// and without constructing them.
 128   template <typename T> T *Allocate(size_t Num, size_t Alignment) {
 129     // Round EltSize up to the specified alignment.
 130     size_t EltSize = (sizeof(T) + Alignment - 1) & (-Alignment);
 131     return static_cast<T *>(Allocate(Num * EltSize, Alignment));
 132   }
 133
 134   void Deallocate(const void * /*Ptr*/) {}
 135
 136   size_t GetNumSlabs() const { return NumSlabs; }
 137
 138   void PrintStats() const;
 139
 140   /// \brief Returns the total physical memory allocated by this allocator.
 141   size_t getTotalMemory() const;
 142
 143 private:
 144   /// \brief Allocate at least this many bytes of memory in a slab.
 145   size_t SlabSize;
 146
 147   /// \brief Threshold above which allocations to go into a dedicated slab.
 148   size_t SizeThreshold;
 149
 150   /// \brief The default allocator used if one is not provided.
 151   MallocSlabAllocator DefaultSlabAllocator;
 152
 153   /// \brief The underlying allocator we use to get slabs of memory.
 154   ///
 155   /// This defaults to MallocSlabAllocator, which wraps malloc, but it could be
 156   /// changed to use a custom allocator.
 157   SlabAllocator &Allocator;
 158
 159   /// \brief The slab that we are currently allocating into.
 160   MemSlab *CurSlab;
 161
 162   /// \brief The current pointer into the current slab.
 163   ///
 164   /// This points to the next free byte in the slab.
 165   char *CurPtr;
 166
 167   /// \brief The end of the current slab.
 168   char *End;
 169
 170   /// \brief How many bytes we've allocated.
 171   ///
 172   /// Used so that we can compute how much space was wasted.
 173   size_t BytesAllocated;
 174
 175   /// \brief How many slabs we've allocated.
 176   ///
 177   /// Used to scale the size of each slab and reduce the number of allocations
 178   /// for extremely heavy memory use scenarios.
 179   size_t NumSlabs;
 180
 181   /// \brief Allocate a new slab and move the bump pointers over into the new
 182   /// slab, modifying CurPtr and End.
 183   void StartNewSlab();
 184
 185   /// \brief Deallocate all memory slabs after and including this one.
 186   void DeallocateSlabs(MemSlab *Slab);
 187
 188   template <typename T> friend class SpecificBumpPtrAllocator;
 189 };
 190
 191 /// \brief A BumpPtrAllocator that allows only elements of a specific type to be
 192 /// allocated.
 193 ///
 194 /// This allows calling the destructor in DestroyAll() and when the allocator is
 195 /// destroyed.
 196 template <typename T> class SpecificBumpPtrAllocator {
 197   BumpPtrAllocator Allocator;
 198
 199 public:
 200   SpecificBumpPtrAllocator(size_t size = 4096, size_t threshold = 4096)
 201       : Allocator(size, threshold) {}
 202   SpecificBumpPtrAllocator(size_t size, size_t threshold,
 203                            SlabAllocator &allocator)
 204       : Allocator(size, threshold, allocator) {}
 205
 206   ~SpecificBumpPtrAllocator() { DestroyAll(); }
 207
 208   /// Call the destructor of each allocated object and deallocate all but the
 209   /// current slab and reset the current pointer to the beginning of it, freeing
 210   /// all memory allocated so far.
 211   void DestroyAll() {
 212     MemSlab *Slab = Allocator.CurSlab;
 213     while (Slab) {
 214       char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr
 215                                             : (char *)Slab + Slab->Size;
 216       for (char *Ptr = (char *)(Slab + 1); Ptr < End; Ptr += sizeof(T)) {
 217         Ptr = alignPtr(Ptr, alignOf<T>());
 218         if (Ptr + sizeof(T) <= End)
 219           reinterpret_cast<T *>(Ptr)->~T();
 220       }
 221       Slab = Slab->NextPtr;
 222     }
 223     Allocator.Reset();
 224   }
 225
 226   /// \brief Allocate space for an array of objects without constructing them.
 227   T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); }
 228 };
 229
 230 }  // end namespace llvm
 231
 232 inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
 233   struct S {
 234     char c;
 235     union {
 236       double D;
 237       long double LD;
 238       long long L;
 239       void *P;
 240     } x;
 241   };
 242   return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
 243                                            offsetof(S, x)));
 244 }
 245
 246 inline void operator delete(void *, llvm::BumpPtrAllocator &) {}
 247
 248 #endif // LLVM_SUPPORT_ALLOCATOR_H