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 /// \file
  10 ///
  11 /// This file defines the MallocAllocator and BumpPtrAllocator interfaces. Both
  12 /// of these conform to an LLVM "Allocator" concept which consists of an
  13 /// Allocate method accepting a size and alignment, and a Deallocate accepting
  14 /// a pointer and size. Further, the LLVM "Allocator" concept has overloads of
  15 /// Allocate and Deallocate for setting size and alignment based on the final
  16 /// type. These overloads are typically provided by a base class template \c
  17 /// AllocatorBase.
  18 ///
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_SUPPORT_ALLOCATOR_H
  22 #define LLVM_SUPPORT_ALLOCATOR_H
  23
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/Support/AlignOf.h"
  26 #include "llvm/Support/DataTypes.h"
  27 #include "llvm/Support/MathExtras.h"
  28 #include "llvm/Support/Memory.h"
  29 #include <algorithm>
  30 #include <cassert>
  31 #include <cstddef>
  32 #include <cstdlib>
  33
  34 namespace llvm {
  35 template <typename T> struct ReferenceAdder {
  36   typedef T &result;
  37 };
  38 template <typename T> struct ReferenceAdder<T &> {
  39   typedef T result;
  40 };
  41
  42 /// \brief CRTP base class providing obvious overloads for the core \c
  43 /// Allocate() methods of LLVM-style allocators.
  44 ///
  45 /// This base class both documents the full public interface exposed by all
  46 /// LLVM-style allocators, and redirects all of the overloads to a single core
  47 /// set of methods which the derived class must define.
  48 template <typename DerivedT> class AllocatorBase {
  49 public:
  50   /// \brief Allocate \a Size bytes of \a Alignment aligned memory. This method
  51   /// must be implemented by \c DerivedT.
  52   void *Allocate(size_t Size, size_t Alignment) {
  53     static_assert(static_cast<void *(AllocatorBase::*)(size_t, size_t)>(
  54                       &AllocatorBase::Allocate) !=
  55                       static_cast<void *(DerivedT::*)(size_t, size_t)>(
  56                           &DerivedT::Allocate),
  57                   "Class derives from AllocatorBase without implementing the "
  58                   "core Allocate(size_t, size_t) overload!");
  59     return static_cast<DerivedT *>(this)->Allocate(Size, Alignment);
  60   }
  61
  62   /// \brief Allocate space for one object without constructing it.
  63   template <typename T> T *Allocate() {
  64     return static_cast<T *>(Allocate(sizeof(T), AlignOf<T>::Alignment));
  65   }
  66
  67   /// \brief Allocate space for an array of objects without constructing them.
  68   template <typename T> T *Allocate(size_t Num) {
  69     return static_cast<T *>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
  70   }
  71
  72   /// \brief Allocate space for an array of objects with the specified alignment
  73   /// and without constructing them.
  74   template <typename T> T *Allocate(size_t Num, size_t Alignment) {
  75     // Round EltSize up to the specified alignment.
  76     size_t EltSize = (sizeof(T) + Alignment - 1) & (-Alignment);
  77     return static_cast<T *>(Allocate(Num * EltSize, Alignment));
  78   }
  79 };
  80
  81 class MallocAllocator : public AllocatorBase<MallocAllocator> {
  82 public:
  83   MallocAllocator() {}
  84   ~MallocAllocator() {}
  85
  86   void Reset() {}
  87
  88   void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
  89
  90   // Pull in base class overloads.
  91   using AllocatorBase<MallocAllocator>::Allocate;
  92
  93   void Deallocate(const void *Ptr) { free(const_cast<void *>(Ptr)); }
  94
  95   void PrintStats() const {}
  96 };
  97
  98 /// MallocSlabAllocator - The default slab allocator for the bump allocator
  99 /// is an adapter class for MallocAllocator that just forwards the method
 100 /// calls and translates the arguments.
 101 class MallocSlabAllocator {
 102   /// Allocator - The underlying allocator that we forward to.
 103   ///
 104   MallocAllocator Allocator;
 105
 106 public:
 107   void *Allocate(size_t Size) { return Allocator.Allocate(Size, 0); }
 108   void Deallocate(void *Slab, size_t Size) { Allocator.Deallocate(Slab); }
 109 };
 110
 111 namespace detail {
 112
 113 // We call out to an external function to actually print the message as the
 114 // printing code uses Allocator.h in its implementation.
 115 void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated,
 116                                 size_t TotalMemory);
 117 } // End namespace detail.
 118
 119 /// \brief Allocate memory in an ever growing pool, as if by bump-pointer.
 120 ///
 121 /// This isn't strictly a bump-pointer allocator as it uses backing slabs of
 122 /// memory rather than relying on boundless contiguous heap. However, it has
 123 /// bump-pointer semantics in that is a monotonically growing pool of memory
 124 /// where every allocation is found by merely allocating the next N bytes in
 125 /// the slab, or the next N bytes in the next slab.
 126 ///
 127 /// Note that this also has a threshold for forcing allocations above a certain
 128 /// size into their own slab.
 129 ///
 130 /// The BumpPtrAllocatorImpl template defaults to using a MallocSlabAllocator
 131 /// object, which wraps malloc, to allocate memory, but it can be changed to
 132 /// use a custom allocator.
 133 template <typename AllocatorT = MallocSlabAllocator, size_t SlabSize = 4096,
 134           size_t SizeThreshold = SlabSize>
 135 class BumpPtrAllocatorImpl
 136     : public AllocatorBase<
 137           BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold>> {
 138   BumpPtrAllocatorImpl(const BumpPtrAllocatorImpl &) LLVM_DELETED_FUNCTION;
 139   void operator=(const BumpPtrAllocatorImpl &) LLVM_DELETED_FUNCTION;
 140
 141 public:
 142   static_assert(SizeThreshold <= SlabSize,
 143                 "The SizeThreshold must be at most the SlabSize to ensure "
 144                 "that objects larger than a slab go into their own memory "
 145                 "allocation.");
 146
 147   BumpPtrAllocatorImpl()
 148       : CurPtr(nullptr), End(nullptr), BytesAllocated(0), Allocator() {}
 149   template <typename T>
 150   BumpPtrAllocatorImpl(T &&Allocator)
 151       : CurPtr(nullptr), End(nullptr), BytesAllocated(0),
 152         Allocator(std::forward<T &&>(Allocator)) {}
 153   ~BumpPtrAllocatorImpl() {
 154     DeallocateSlabs(Slabs.begin(), Slabs.end());
 155     DeallocateCustomSizedSlabs();
 156   }
 157
 158   /// \brief Deallocate all but the current slab and reset the current pointer
 159   /// to the beginning of it, freeing all memory allocated so far.
 160   void Reset() {
 161     if (Slabs.empty())
 162       return;
 163
 164     // Reset the state.
 165     BytesAllocated = 0;
 166     CurPtr = (char *)Slabs.front();
 167     End = CurPtr + SlabSize;
 168
 169     // Deallocate all but the first slab, and all custome sized slabs.
 170     DeallocateSlabs(std::next(Slabs.begin()), Slabs.end());
 171     Slabs.erase(std::next(Slabs.begin()), Slabs.end());
 172     DeallocateCustomSizedSlabs();
 173     CustomSizedSlabs.clear();
 174   }
 175
 176   /// \brief Allocate space at the specified alignment.
 177   void *Allocate(size_t Size, size_t Alignment) {
 178     if (!CurPtr) // Start a new slab if we haven't allocated one already.
 179       StartNewSlab();
 180
 181     // Keep track of how many bytes we've allocated.
 182     BytesAllocated += Size;
 183
 184     // 0-byte alignment means 1-byte alignment.
 185     if (Alignment == 0)
 186       Alignment = 1;
 187
 188     // Allocate the aligned space, going forwards from CurPtr.
 189     char *Ptr = alignPtr(CurPtr, Alignment);
 190
 191     // Check if we can hold it.
 192     if (Ptr + Size <= End) {
 193       CurPtr = Ptr + Size;
 194       // Update the allocation point of this memory block in MemorySanitizer.
 195       // Without this, MemorySanitizer messages for values originated from here
 196       // will point to the allocation of the entire slab.
 197       __msan_allocated_memory(Ptr, Size);
 198       return Ptr;
 199     }
 200
 201     // If Size is really big, allocate a separate slab for it.
 202     size_t PaddedSize = Size + Alignment - 1;
 203     if (PaddedSize > SizeThreshold) {
 204       void *NewSlab = Allocator.Allocate(PaddedSize);
 205       CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize));
 206
 207       Ptr = alignPtr((char *)NewSlab, Alignment);
 208       assert((uintptr_t)Ptr + Size <= (uintptr_t)NewSlab + PaddedSize);
 209       __msan_allocated_memory(Ptr, Size);
 210       return Ptr;
 211     }
 212
 213     // Otherwise, start a new slab and try again.
 214     StartNewSlab();
 215     Ptr = alignPtr(CurPtr, Alignment);
 216     CurPtr = Ptr + Size;
 217     assert(CurPtr <= End && "Unable to allocate memory!");
 218     __msan_allocated_memory(Ptr, Size);
 219     return Ptr;
 220   }
 221
 222   // Pull in base class overloads.
 223   using AllocatorBase<BumpPtrAllocatorImpl>::Allocate;
 224
 225   void Deallocate(const void * /*Ptr*/) {}
 226
 227   size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); }
 228
 229   size_t getTotalMemory() const {
 230     size_t TotalMemory = 0;
 231     for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I)
 232       TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I));
 233     for (auto &PtrAndSize : CustomSizedSlabs)
 234       TotalMemory += PtrAndSize.second;
 235     return TotalMemory;
 236   }
 237
 238   void PrintStats() const {
 239     detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated,
 240                                        getTotalMemory());
 241   }
 242
 243 private:
 244   /// \brief The current pointer into the current slab.
 245   ///
 246   /// This points to the next free byte in the slab.
 247   char *CurPtr;
 248
 249   /// \brief The end of the current slab.
 250   char *End;
 251
 252   /// \brief The slabs allocated so far.
 253   SmallVector<void *, 4> Slabs;
 254
 255   /// \brief Custom-sized slabs allocated for too-large allocation requests.
 256   SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs;
 257
 258   /// \brief How many bytes we've allocated.
 259   ///
 260   /// Used so that we can compute how much space was wasted.
 261   size_t BytesAllocated;
 262
 263   /// \brief The allocator instance we use to get slabs of memory.
 264   AllocatorT Allocator;
 265
 266   static size_t computeSlabSize(unsigned SlabIdx) {
 267     // Scale the actual allocated slab size based on the number of slabs
 268     // allocated. Every 128 slabs allocated, we double the allocated size to
 269     // reduce allocation frequency, but saturate at multiplying the slab size by
 270     // 2^30.
 271     return SlabSize * ((size_t)1 << std::min<size_t>(30, SlabIdx / 128));
 272   }
 273
 274   /// \brief Allocate a new slab and move the bump pointers over into the new
 275   /// slab, modifying CurPtr and End.
 276   void StartNewSlab() {
 277     size_t AllocatedSlabSize = computeSlabSize(Slabs.size());
 278
 279     void *NewSlab = Allocator.Allocate(AllocatedSlabSize);
 280     Slabs.push_back(NewSlab);
 281     CurPtr = (char *)(NewSlab);
 282     End = ((char *)NewSlab) + AllocatedSlabSize;
 283   }
 284
 285   /// \brief Deallocate a sequence of slabs.
 286   void DeallocateSlabs(SmallVectorImpl<void *>::iterator I,
 287                        SmallVectorImpl<void *>::iterator E) {
 288     for (; I != E; ++I) {
 289       size_t AllocatedSlabSize =
 290           computeSlabSize(std::distance(Slabs.begin(), I));
 291 #ifndef NDEBUG
 292       // Poison the memory so stale pointers crash sooner.  Note we must
 293       // preserve the Size and NextPtr fields at the beginning.
 294       sys::Memory::setRangeWritable(*I, AllocatedSlabSize);
 295       memset(*I, 0xCD, AllocatedSlabSize);
 296 #endif
 297       Allocator.Deallocate(*I, AllocatedSlabSize);
 298     }
 299   }
 300
 301   /// \brief Deallocate all memory for custom sized slabs.
 302   void DeallocateCustomSizedSlabs() {
 303     for (auto &PtrAndSize : CustomSizedSlabs) {
 304       void *Ptr = PtrAndSize.first;
 305       size_t Size = PtrAndSize.second;
 306 #ifndef NDEBUG
 307       // Poison the memory so stale pointers crash sooner.  Note we must
 308       // preserve the Size and NextPtr fields at the beginning.
 309       sys::Memory::setRangeWritable(Ptr, Size);
 310       memset(Ptr, 0xCD, Size);
 311 #endif
 312       Allocator.Deallocate(Ptr, Size);
 313     }
 314   }
 315
 316   template <typename T> friend class SpecificBumpPtrAllocator;
 317 };
 318
 319 /// \brief The standard BumpPtrAllocator which just uses the default template
 320 /// paramaters.
 321 typedef BumpPtrAllocatorImpl<> BumpPtrAllocator;
 322
 323 /// \brief A BumpPtrAllocator that allows only elements of a specific type to be
 324 /// allocated.
 325 ///
 326 /// This allows calling the destructor in DestroyAll() and when the allocator is
 327 /// destroyed.
 328 template <typename T> class SpecificBumpPtrAllocator {
 329   BumpPtrAllocator Allocator;
 330
 331 public:
 332   SpecificBumpPtrAllocator() : Allocator() {}
 333
 334   ~SpecificBumpPtrAllocator() { DestroyAll(); }
 335
 336   /// Call the destructor of each allocated object and deallocate all but the
 337   /// current slab and reset the current pointer to the beginning of it, freeing
 338   /// all memory allocated so far.
 339   void DestroyAll() {
 340     auto DestroyElements = [](char *Begin, char *End) {
 341       assert(Begin == alignPtr(Begin, alignOf<T>()));
 342       for (char *Ptr = Begin; Ptr + sizeof(T) <= End; Ptr += sizeof(T))
 343         reinterpret_cast<T *>(Ptr)->~T();
 344     };
 345
 346     for (auto I = Allocator.Slabs.begin(), E = Allocator.Slabs.end(); I != E;
 347          ++I) {
 348       size_t AllocatedSlabSize = BumpPtrAllocator::computeSlabSize(
 349           std::distance(Allocator.Slabs.begin(), I));
 350       char *Begin = alignPtr((char *)*I, alignOf<T>());
 351       char *End = *I == Allocator.Slabs.back() ? Allocator.CurPtr
 352                                                : (char *)*I + AllocatedSlabSize;
 353
 354       DestroyElements(Begin, End);
 355     }
 356
 357     for (auto &PtrAndSize : Allocator.CustomSizedSlabs) {
 358       void *Ptr = PtrAndSize.first;
 359       size_t Size = PtrAndSize.second;
 360       DestroyElements(alignPtr((char *)Ptr, alignOf<T>()), (char *)Ptr + Size);
 361     }
 362
 363     Allocator.Reset();
 364   }
 365
 366   /// \brief Allocate space for an array of objects without constructing them.
 367   T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); }
 368
 369 private:
 370 };
 371
 372 }  // end namespace llvm
 373
 374 template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
 375 void *operator new(size_t Size,
 376                    llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize,
 377                                               SizeThreshold> &Allocator) {
 378   struct S {
 379     char c;
 380     union {
 381       double D;
 382       long double LD;
 383       long long L;
 384       void *P;
 385     } x;
 386   };
 387   return Allocator.Allocate(
 388       Size, std::min((size_t)llvm::NextPowerOf2(Size), offsetof(S, x)));
 389 }
 390
 391 template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
 392 void operator delete(
 393     void *, llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold> &) {
 394 }
 395
 396 #endif // LLVM_SUPPORT_ALLOCATOR_H