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   /// \brief Allocate at least this many bytes of memory in a slab.
 105   size_t SlabSize;
 106
 107   /// \brief Threshold above which allocations to go into a dedicated slab.
 108   size_t SizeThreshold;
 109
 110   /// \brief The default allocator used if one is not provided.
 111   MallocSlabAllocator DefaultSlabAllocator;
 112
 113   /// \brief The underlying allocator we use to get slabs of memory.
 114   ///
 115   /// This defaults to MallocSlabAllocator, which wraps malloc, but it could be
 116   /// changed to use a custom allocator.
 117   SlabAllocator &Allocator;
 118
 119   /// \brief The slab that we are currently allocating into.
 120   MemSlab *CurSlab;
 121
 122   /// \brief The current pointer into the current slab.
 123   ///
 124   /// This points to the next free byte in the slab.
 125   char *CurPtr;
 126
 127   /// \brief The end of the current slab.
 128   char *End;
 129
 130   /// \brief How many bytes we've allocated.
 131   ///
 132   /// Used so that we can compute how much space was wasted.
 133   size_t BytesAllocated;
 134
 135   /// \brief How many slabs we've allocated.
 136   ///
 137   /// Used to scale the size of each slab and reduce the number of allocations
 138   /// for extremely heavy memory use scenarios.
 139   size_t NumSlabs;
 140
 141   /// \brief Allocate a new slab and move the bump pointers over into the new
 142   /// slab, modifying CurPtr and End.
 143   void StartNewSlab();
 144
 145   /// \brief Deallocate all memory slabs after and including this one.
 146   void DeallocateSlabs(MemSlab *Slab);
 147
 148   template <typename T> friend class SpecificBumpPtrAllocator;
 149
 150 public:
 151   BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096);
 152   BumpPtrAllocator(size_t size, size_t threshold, SlabAllocator &allocator);
 153   ~BumpPtrAllocator();
 154
 155   /// \brief Deallocate all but the current slab and reset the current pointer
 156   /// to the beginning of it, freeing all memory allocated so far.
 157   void Reset();
 158
 159   /// \brief Allocate space at the specified alignment.
 160   void *Allocate(size_t Size, size_t Alignment);
 161
 162   /// \brief Allocate space for one object without constructing it.
 163   template <typename T> T *Allocate() {
 164     return static_cast<T *>(Allocate(sizeof(T), AlignOf<T>::Alignment));
 165   }
 166
 167   /// \brief Allocate space for an array of objects without constructing them.
 168   template <typename T> T *Allocate(size_t Num) {
 169     return static_cast<T *>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
 170   }
 171
 172   /// \brief Allocate space for an array of objects with the specified alignment
 173   /// and without constructing them.
 174   template <typename T> T *Allocate(size_t Num, size_t Alignment) {
 175     // Round EltSize up to the specified alignment.
 176     size_t EltSize = (sizeof(T) + Alignment - 1) & (-Alignment);
 177     return static_cast<T *>(Allocate(Num * EltSize, Alignment));
 178   }
 179
 180   void Deallocate(const void * /*Ptr*/) {}
 181
 182   size_t GetNumSlabs() const { return NumSlabs; }
 183
 184   void PrintStats() const;
 185
 186   /// \brief Returns the total physical memory allocated by this allocator.
 187   size_t getTotalMemory() const;
 188 };
 189
 190 /// \brief A BumpPtrAllocator that allows only elements of a specific type to be
 191 /// allocated.
 192 ///
 193 /// This allows calling the destructor in DestroyAll() and when the allocator is
 194 /// destroyed.
 195 template <typename T> class SpecificBumpPtrAllocator {
 196   BumpPtrAllocator Allocator;
 197
 198 public:
 199   SpecificBumpPtrAllocator(size_t size = 4096, size_t threshold = 4096)
 200       : Allocator(size, threshold) {}
 201   SpecificBumpPtrAllocator(size_t size, size_t threshold,
 202                            SlabAllocator &allocator)
 203       : Allocator(size, threshold, allocator) {}
 204
 205   ~SpecificBumpPtrAllocator() { DestroyAll(); }
 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 = 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) { return Allocator.Allocate<T>(num); }
 227 };
 228
 229 }  // end namespace llvm
 230
 231 inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
 232   struct S {
 233     char c;
 234     union {
 235       double D;
 236       long double LD;
 237       long long L;
 238       void *P;
 239     } x;
 240   };
 241   return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
 242                                            offsetof(S, x)));
 243 }
 244
 245 inline void operator delete(void *, llvm::BumpPtrAllocator &) {}
 246
 247 #endif // LLVM_SUPPORT_ALLOCATOR_H