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 "llvm/Support/Memory.h"
  21 #include <algorithm>
  22 #include <cassert>
  23 #include <cstddef>
  24 #include <cstdlib>
  25
  26 namespace llvm {
  27 template <typename T> struct ReferenceAdder {
  28   typedef T &result;
  29 };
  30 template <typename T> struct ReferenceAdder<T &> {
  31   typedef T result;
  32 };
  33
  34 class MallocAllocator {
  35 public:
  36   MallocAllocator() {}
  37   ~MallocAllocator() {}
  38
  39   void Reset() {}
  40
  41   void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
  42
  43   template <typename T> T *Allocate() {
  44     return static_cast<T *>(malloc(sizeof(T)));
  45   }
  46
  47   template <typename T> T *Allocate(size_t Num) {
  48     return static_cast<T *>(malloc(sizeof(T) * Num));
  49   }
  50
  51   void Deallocate(const void *Ptr) { free(const_cast<void *>(Ptr)); }
  52
  53   void PrintStats() const {}
  54 };
  55
  56 /// MemSlab - This structure lives at the beginning of every slab allocated by
  57 /// the bump allocator.
  58 class MemSlab {
  59 public:
  60   size_t Size;
  61   MemSlab *NextPtr;
  62 };
  63
  64 /// SlabAllocator - This class can be used to parameterize the underlying
  65 /// allocation strategy for the bump allocator.  In particular, this is used
  66 /// by the JIT to allocate contiguous swathes of executable memory.  The
  67 /// interface uses MemSlab's instead of void *'s so that the allocator
  68 /// doesn't have to remember the size of the pointer it allocated.
  69 class SlabAllocator {
  70 public:
  71   virtual ~SlabAllocator();
  72   virtual MemSlab *Allocate(size_t Size) = 0;
  73   virtual void Deallocate(MemSlab *Slab) = 0;
  74 };
  75
  76 /// MallocSlabAllocator - The default slab allocator for the bump allocator
  77 /// is an adapter class for MallocAllocator that just forwards the method
  78 /// calls and translates the arguments.
  79 class MallocSlabAllocator : public SlabAllocator {
  80   /// Allocator - The underlying allocator that we forward to.
  81   ///
  82   MallocAllocator Allocator;
  83
  84 public:
  85   MallocSlabAllocator() : Allocator() {}
  86   virtual ~MallocSlabAllocator();
  87   MemSlab *Allocate(size_t Size) override;
  88   void Deallocate(MemSlab *Slab) override;
  89 };
  90
  91 /// \brief Non-templated base class for the \c BumpPtrAllocatorImpl template.
  92 class BumpPtrAllocatorBase {
  93 public:
  94   void Deallocate(const void * /*Ptr*/) {}
  95   void PrintStats() const;
  96
  97   /// \brief Returns the total physical memory allocated by this allocator.
  98   size_t getTotalMemory() const;
  99
 100 protected:
 101   /// \brief The slab that we are currently allocating into.
 102   MemSlab *CurSlab;
 103
 104   /// \brief How many bytes we've allocated.
 105   ///
 106   /// Used so that we can compute how much space was wasted.
 107   size_t BytesAllocated;
 108
 109   BumpPtrAllocatorBase() : CurSlab(nullptr), BytesAllocated(0) {}
 110 };
 111
 112 /// \brief Allocate memory in an ever growing pool, as if by bump-pointer.
 113 ///
 114 /// This isn't strictly a bump-pointer allocator as it uses backing slabs of
 115 /// memory rather than relying on boundless contiguous heap. However, it has
 116 /// bump-pointer semantics in that is a monotonically growing pool of memory
 117 /// where every allocation is found by merely allocating the next N bytes in
 118 /// the slab, or the next N bytes in the next slab.
 119 ///
 120 /// Note that this also has a threshold for forcing allocations above a certain
 121 /// size into their own slab.
 122 template <size_t SlabSize = 4096, size_t SizeThreshold = SlabSize>
 123 class BumpPtrAllocatorImpl : public BumpPtrAllocatorBase {
 124   BumpPtrAllocatorImpl(const BumpPtrAllocatorImpl &) LLVM_DELETED_FUNCTION;
 125   void operator=(const BumpPtrAllocatorImpl &) LLVM_DELETED_FUNCTION;
 126
 127 public:
 128   static_assert(SizeThreshold <= SlabSize,
 129                 "The SizeThreshold must be at most the SlabSize to ensure "
 130                 "that objects larger than a slab go into their own memory "
 131                 "allocation.");
 132
 133   BumpPtrAllocatorImpl()
 134       : Allocator(DefaultSlabAllocator), NumSlabs(0) {}
 135   BumpPtrAllocatorImpl(SlabAllocator &Allocator)
 136       : Allocator(Allocator), NumSlabs(0) {}
 137   ~BumpPtrAllocatorImpl() { DeallocateSlabs(CurSlab); }
 138
 139   /// \brief Deallocate all but the current slab and reset the current pointer
 140   /// to the beginning of it, freeing all memory allocated so far.
 141   void Reset() {
 142     if (!CurSlab)
 143       return;
 144     DeallocateSlabs(CurSlab->NextPtr);
 145     CurSlab->NextPtr = nullptr;
 146     CurPtr = (char *)(CurSlab + 1);
 147     End = ((char *)CurSlab) + CurSlab->Size;
 148     BytesAllocated = 0;
 149   }
 150
 151   /// \brief Allocate space at the specified alignment.
 152   void *Allocate(size_t Size, size_t Alignment) {
 153     if (!CurSlab) // Start a new slab if we haven't allocated one already.
 154       StartNewSlab();
 155
 156     // Keep track of how many bytes we've allocated.
 157     BytesAllocated += Size;
 158
 159     // 0-byte alignment means 1-byte alignment.
 160     if (Alignment == 0)
 161       Alignment = 1;
 162
 163     // Allocate the aligned space, going forwards from CurPtr.
 164     char *Ptr = alignPtr(CurPtr, Alignment);
 165
 166     // Check if we can hold it.
 167     if (Ptr + Size <= End) {
 168       CurPtr = Ptr + Size;
 169       // Update the allocation point of this memory block in MemorySanitizer.
 170       // Without this, MemorySanitizer messages for values originated from here
 171       // will point to the allocation of the entire slab.
 172       __msan_allocated_memory(Ptr, Size);
 173       return Ptr;
 174     }
 175
 176     // If Size is really big, allocate a separate slab for it.
 177     size_t PaddedSize = Size + sizeof(MemSlab) + Alignment - 1;
 178     if (PaddedSize > SizeThreshold) {
 179       ++NumSlabs;
 180       MemSlab *NewSlab = Allocator.Allocate(PaddedSize);
 181
 182       // Put the new slab after the current slab, since we are not allocating
 183       // into it.
 184       NewSlab->NextPtr = CurSlab->NextPtr;
 185       CurSlab->NextPtr = NewSlab;
 186
 187       Ptr = alignPtr((char *)(NewSlab + 1), Alignment);
 188       assert((uintptr_t)Ptr + Size <= (uintptr_t)NewSlab + NewSlab->Size);
 189       __msan_allocated_memory(Ptr, Size);
 190       return Ptr;
 191     }
 192
 193     // Otherwise, start a new slab and try again.
 194     StartNewSlab();
 195     Ptr = alignPtr(CurPtr, Alignment);
 196     CurPtr = Ptr + Size;
 197     assert(CurPtr <= End && "Unable to allocate memory!");
 198     __msan_allocated_memory(Ptr, Size);
 199     return Ptr;
 200   }
 201
 202   /// \brief Allocate space for one object without constructing it.
 203   template <typename T> T *Allocate() {
 204     return static_cast<T *>(Allocate(sizeof(T), AlignOf<T>::Alignment));
 205   }
 206
 207   /// \brief Allocate space for an array of objects without constructing them.
 208   template <typename T> T *Allocate(size_t Num) {
 209     return static_cast<T *>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
 210   }
 211
 212   /// \brief Allocate space for an array of objects with the specified alignment
 213   /// and without constructing them.
 214   template <typename T> T *Allocate(size_t Num, size_t Alignment) {
 215     // Round EltSize up to the specified alignment.
 216     size_t EltSize = (sizeof(T) + Alignment - 1) & (-Alignment);
 217     return static_cast<T *>(Allocate(Num * EltSize, Alignment));
 218   }
 219
 220   size_t GetNumSlabs() const { return NumSlabs; }
 221
 222 private:
 223   /// \brief The default allocator used if one is not provided.
 224   MallocSlabAllocator DefaultSlabAllocator;
 225
 226   /// \brief The underlying allocator we use to get slabs of memory.
 227   ///
 228   /// This defaults to MallocSlabAllocator, which wraps malloc, but it could be
 229   /// changed to use a custom allocator.
 230   SlabAllocator &Allocator;
 231
 232   /// \brief The current pointer into the current slab.
 233   ///
 234   /// This points to the next free byte in the slab.
 235   char *CurPtr;
 236
 237   /// \brief The end of the current slab.
 238   char *End;
 239
 240   /// \brief How many slabs we've allocated.
 241   ///
 242   /// Used to scale the size of each slab and reduce the number of allocations
 243   /// for extremely heavy memory use scenarios.
 244   size_t NumSlabs;
 245
 246   /// \brief Allocate a new slab and move the bump pointers over into the new
 247   /// slab, modifying CurPtr and End.
 248   void StartNewSlab() {
 249     ++NumSlabs;
 250     // Scale the actual allocated slab size based on the number of slabs
 251     // allocated. Every 128 slabs allocated, we double the allocated size to
 252     // reduce allocation frequency, but saturate at multiplying the slab size by
 253     // 2^30.
 254     // FIXME: Currently, this count includes special slabs for objects above the
 255     // size threshold. That will be fixed in a subsequent commit to make the
 256     // growth even more predictable.
 257     size_t AllocatedSlabSize =
 258         SlabSize * ((size_t)1 << std::min<size_t>(30, NumSlabs / 128));
 259
 260     MemSlab *NewSlab = Allocator.Allocate(AllocatedSlabSize);
 261     NewSlab->NextPtr = CurSlab;
 262     CurSlab = NewSlab;
 263     CurPtr = (char *)(CurSlab + 1);
 264     End = ((char *)CurSlab) + CurSlab->Size;
 265   }
 266
 267   /// \brief Deallocate all memory slabs after and including this one.
 268   void DeallocateSlabs(MemSlab *Slab) {
 269     while (Slab) {
 270       MemSlab *NextSlab = Slab->NextPtr;
 271 #ifndef NDEBUG
 272       // Poison the memory so stale pointers crash sooner.  Note we must
 273       // preserve the Size and NextPtr fields at the beginning.
 274       sys::Memory::setRangeWritable(Slab + 1, Slab->Size - sizeof(MemSlab));
 275       memset(Slab + 1, 0xCD, Slab->Size - sizeof(MemSlab));
 276 #endif
 277       Allocator.Deallocate(Slab);
 278       Slab = NextSlab;
 279       --NumSlabs;
 280     }
 281   }
 282
 283   template <typename T> friend class SpecificBumpPtrAllocator;
 284 };
 285
 286 /// \brief The standard BumpPtrAllocator which just uses the default template
 287 /// paramaters.
 288 typedef BumpPtrAllocatorImpl<> BumpPtrAllocator;
 289
 290 /// \brief A BumpPtrAllocator that allows only elements of a specific type to be
 291 /// allocated.
 292 ///
 293 /// This allows calling the destructor in DestroyAll() and when the allocator is
 294 /// destroyed.
 295 template <typename T> class SpecificBumpPtrAllocator {
 296   BumpPtrAllocator Allocator;
 297
 298 public:
 299   SpecificBumpPtrAllocator() : Allocator() {}
 300   SpecificBumpPtrAllocator(SlabAllocator &allocator) : Allocator(allocator) {}
 301
 302   ~SpecificBumpPtrAllocator() { DestroyAll(); }
 303
 304   /// Call the destructor of each allocated object and deallocate all but the
 305   /// current slab and reset the current pointer to the beginning of it, freeing
 306   /// all memory allocated so far.
 307   void DestroyAll() {
 308     MemSlab *Slab = Allocator.CurSlab;
 309     while (Slab) {
 310       char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr
 311                                             : (char *)Slab + Slab->Size;
 312       for (char *Ptr = (char *)(Slab + 1); Ptr < End; Ptr += sizeof(T)) {
 313         Ptr = alignPtr(Ptr, alignOf<T>());
 314         if (Ptr + sizeof(T) <= End)
 315           reinterpret_cast<T *>(Ptr)->~T();
 316       }
 317       Slab = Slab->NextPtr;
 318     }
 319     Allocator.Reset();
 320   }
 321
 322   /// \brief Allocate space for an array of objects without constructing them.
 323   T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); }
 324 };
 325
 326 }  // end namespace llvm
 327
 328 template <size_t SlabSize, size_t SizeThreshold>
 329 void *
 330 operator new(size_t Size,
 331              llvm::BumpPtrAllocatorImpl<SlabSize, SizeThreshold> &Allocator) {
 332   struct S {
 333     char c;
 334     union {
 335       double D;
 336       long double LD;
 337       long long L;
 338       void *P;
 339     } x;
 340   };
 341   return Allocator.Allocate(
 342       Size, std::min((size_t)llvm::NextPowerOf2(Size), offsetof(S, x)));
 343 }
 344
 345 template <size_t SlabSize, size_t SizeThreshold>
 346 void operator delete(void *,
 347                      llvm::BumpPtrAllocatorImpl<SlabSize, SizeThreshold> &) {}
 348
 349 #endif // LLVM_SUPPORT_ALLOCATOR_H