LLVM  7.0.0svn
Allocator.h
Go to the documentation of this file.
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/Compiler.h"
28 #include <algorithm>
29 #include <cassert>
30 #include <cstddef>
31 #include <cstdint>
32 #include <cstdlib>
33 #include <iterator>
34 #include <type_traits>
35 #include <utility>
36 
37 namespace llvm {
38 
39 /// \brief CRTP base class providing obvious overloads for the core \c
40 /// Allocate() methods of LLVM-style allocators.
41 ///
42 /// This base class both documents the full public interface exposed by all
43 /// LLVM-style allocators, and redirects all of the overloads to a single core
44 /// set of methods which the derived class must define.
45 template <typename DerivedT> class AllocatorBase {
46 public:
47  /// \brief Allocate \a Size bytes of \a Alignment aligned memory. This method
48  /// must be implemented by \c DerivedT.
49  void *Allocate(size_t Size, size_t Alignment) {
50 #ifdef __clang__
51  static_assert(static_cast<void *(AllocatorBase::*)(size_t, size_t)>(
53  static_cast<void *(DerivedT::*)(size_t, size_t)>(
54  &DerivedT::Allocate),
55  "Class derives from AllocatorBase without implementing the "
56  "core Allocate(size_t, size_t) overload!");
57 #endif
58  return static_cast<DerivedT *>(this)->Allocate(Size, Alignment);
59  }
60 
61  /// \brief Deallocate \a Ptr to \a Size bytes of memory allocated by this
62  /// allocator.
63  void Deallocate(const void *Ptr, size_t Size) {
64 #ifdef __clang__
65  static_assert(static_cast<void (AllocatorBase::*)(const void *, size_t)>(
67  static_cast<void (DerivedT::*)(const void *, size_t)>(
68  &DerivedT::Deallocate),
69  "Class derives from AllocatorBase without implementing the "
70  "core Deallocate(void *) overload!");
71 #endif
72  return static_cast<DerivedT *>(this)->Deallocate(Ptr, Size);
73  }
74 
75  // The rest of these methods are helpers that redirect to one of the above
76  // core methods.
77 
78  /// \brief Allocate space for a sequence of objects without constructing them.
79  template <typename T> T *Allocate(size_t Num = 1) {
80  return static_cast<T *>(Allocate(Num * sizeof(T), alignof(T)));
81  }
82 
83  /// \brief Deallocate space for a sequence of objects without constructing them.
84  template <typename T>
85  typename std::enable_if<
86  !std::is_same<typename std::remove_cv<T>::type, void>::value, void>::type
87  Deallocate(T *Ptr, size_t Num = 1) {
88  Deallocate(static_cast<const void *>(Ptr), Num * sizeof(T));
89  }
90 };
91 
92 class MallocAllocator : public AllocatorBase<MallocAllocator> {
93 public:
94  void Reset() {}
95 
97  size_t /*Alignment*/) {
98  void* memPtr = malloc(Size);
99  if (memPtr == nullptr)
100  report_bad_alloc_error("Allocation in MallocAllocator failed.");
101 
102  return memPtr;
103  }
104 
105  // Pull in base class overloads.
107 
108  void Deallocate(const void *Ptr, size_t /*Size*/) {
109  free(const_cast<void *>(Ptr));
110  }
111 
112  // Pull in base class overloads.
114 
115  void PrintStats() const {}
116 };
117 
118 namespace detail {
119 
120 // We call out to an external function to actually print the message as the
121 // printing code uses Allocator.h in its implementation.
122 void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated,
123  size_t TotalMemory);
124 
125 } // end namespace detail
126 
127 /// \brief Allocate memory in an ever growing pool, as if by bump-pointer.
128 ///
129 /// This isn't strictly a bump-pointer allocator as it uses backing slabs of
130 /// memory rather than relying on a boundless contiguous heap. However, it has
131 /// bump-pointer semantics in that it is a monotonically growing pool of memory
132 /// where every allocation is found by merely allocating the next N bytes in
133 /// the slab, or the next N bytes in the next slab.
134 ///
135 /// Note that this also has a threshold for forcing allocations above a certain
136 /// size into their own slab.
137 ///
138 /// The BumpPtrAllocatorImpl template defaults to using a MallocAllocator
139 /// object, which wraps malloc, to allocate memory, but it can be changed to
140 /// use a custom allocator.
141 template <typename AllocatorT = MallocAllocator, size_t SlabSize = 4096,
142  size_t SizeThreshold = SlabSize>
144  : public AllocatorBase<
145  BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold>> {
146 public:
147  static_assert(SizeThreshold <= SlabSize,
148  "The SizeThreshold must be at most the SlabSize to ensure "
149  "that objects larger than a slab go into their own memory "
150  "allocation.");
151 
152  BumpPtrAllocatorImpl() = default;
153 
154  template <typename T>
156  : Allocator(std::forward<T &&>(Allocator)) {}
157 
158  // Manually implement a move constructor as we must clear the old allocator's
159  // slabs as a matter of correctness.
161  : CurPtr(Old.CurPtr), End(Old.End), Slabs(std::move(Old.Slabs)),
162  CustomSizedSlabs(std::move(Old.CustomSizedSlabs)),
163  BytesAllocated(Old.BytesAllocated), RedZoneSize(Old.RedZoneSize),
164  Allocator(std::move(Old.Allocator)) {
165  Old.CurPtr = Old.End = nullptr;
166  Old.BytesAllocated = 0;
167  Old.Slabs.clear();
168  Old.CustomSizedSlabs.clear();
169  }
170 
172  DeallocateSlabs(Slabs.begin(), Slabs.end());
173  DeallocateCustomSizedSlabs();
174  }
175 
177  DeallocateSlabs(Slabs.begin(), Slabs.end());
178  DeallocateCustomSizedSlabs();
179 
180  CurPtr = RHS.CurPtr;
181  End = RHS.End;
182  BytesAllocated = RHS.BytesAllocated;
183  RedZoneSize = RHS.RedZoneSize;
184  Slabs = std::move(RHS.Slabs);
185  CustomSizedSlabs = std::move(RHS.CustomSizedSlabs);
186  Allocator = std::move(RHS.Allocator);
187 
188  RHS.CurPtr = RHS.End = nullptr;
189  RHS.BytesAllocated = 0;
190  RHS.Slabs.clear();
191  RHS.CustomSizedSlabs.clear();
192  return *this;
193  }
194 
195  /// \brief Deallocate all but the current slab and reset the current pointer
196  /// to the beginning of it, freeing all memory allocated so far.
197  void Reset() {
198  // Deallocate all but the first slab, and deallocate all custom-sized slabs.
199  DeallocateCustomSizedSlabs();
200  CustomSizedSlabs.clear();
201 
202  if (Slabs.empty())
203  return;
204 
205  // Reset the state.
206  BytesAllocated = 0;
207  CurPtr = (char *)Slabs.front();
208  End = CurPtr + SlabSize;
209 
210  __asan_poison_memory_region(*Slabs.begin(), computeSlabSize(0));
211  DeallocateSlabs(std::next(Slabs.begin()), Slabs.end());
212  Slabs.erase(std::next(Slabs.begin()), Slabs.end());
213  }
214 
215  /// \brief Allocate space at the specified alignment.
217  Allocate(size_t Size, size_t Alignment) {
218  assert(Alignment > 0 && "0-byte alignnment is not allowed. Use 1 instead.");
219 
220  // Keep track of how many bytes we've allocated.
221  BytesAllocated += Size;
222 
223  size_t Adjustment = alignmentAdjustment(CurPtr, Alignment);
224  assert(Adjustment + Size >= Size && "Adjustment + Size must not overflow");
225 
226  size_t SizeToAllocate = Size;
227 #if LLVM_ADDRESS_SANITIZER_BUILD
228  // Add trailing bytes as a "red zone" under ASan.
229  SizeToAllocate += RedZoneSize;
230 #endif
231 
232  // Check if we have enough space.
233  if (Adjustment + SizeToAllocate <= size_t(End - CurPtr)) {
234  char *AlignedPtr = CurPtr + Adjustment;
235  CurPtr = AlignedPtr + SizeToAllocate;
236  // Update the allocation point of this memory block in MemorySanitizer.
237  // Without this, MemorySanitizer messages for values originated from here
238  // will point to the allocation of the entire slab.
239  __msan_allocated_memory(AlignedPtr, Size);
240  // Similarly, tell ASan about this space.
241  __asan_unpoison_memory_region(AlignedPtr, Size);
242  return AlignedPtr;
243  }
244 
245  // If Size is really big, allocate a separate slab for it.
246  size_t PaddedSize = SizeToAllocate + Alignment - 1;
247  if (PaddedSize > SizeThreshold) {
248  void *NewSlab = Allocator.Allocate(PaddedSize, 0);
249  // We own the new slab and don't want anyone reading anyting other than
250  // pieces returned from this method. So poison the whole slab.
251  __asan_poison_memory_region(NewSlab, PaddedSize);
252  CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize));
253 
254  uintptr_t AlignedAddr = alignAddr(NewSlab, Alignment);
255  assert(AlignedAddr + Size <= (uintptr_t)NewSlab + PaddedSize);
256  char *AlignedPtr = (char*)AlignedAddr;
257  __msan_allocated_memory(AlignedPtr, Size);
258  __asan_unpoison_memory_region(AlignedPtr, Size);
259  return AlignedPtr;
260  }
261 
262  // Otherwise, start a new slab and try again.
263  StartNewSlab();
264  uintptr_t AlignedAddr = alignAddr(CurPtr, Alignment);
265  assert(AlignedAddr + SizeToAllocate <= (uintptr_t)End &&
266  "Unable to allocate memory!");
267  char *AlignedPtr = (char*)AlignedAddr;
268  CurPtr = AlignedPtr + SizeToAllocate;
269  __msan_allocated_memory(AlignedPtr, Size);
270  __asan_unpoison_memory_region(AlignedPtr, Size);
271  return AlignedPtr;
272  }
273 
274  // Pull in base class overloads.
276 
277  // Bump pointer allocators are expected to never free their storage; and
278  // clients expect pointers to remain valid for non-dereferencing uses even
279  // after deallocation.
280  void Deallocate(const void *Ptr, size_t Size) {
281  __asan_poison_memory_region(Ptr, Size);
282  }
283 
284  // Pull in base class overloads.
286 
287  size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); }
288 
289  size_t getTotalMemory() const {
290  size_t TotalMemory = 0;
291  for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I)
292  TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I));
293  for (auto &PtrAndSize : CustomSizedSlabs)
294  TotalMemory += PtrAndSize.second;
295  return TotalMemory;
296  }
297 
298  size_t getBytesAllocated() const { return BytesAllocated; }
299 
300  void setRedZoneSize(size_t NewSize) {
301  RedZoneSize = NewSize;
302  }
303 
304  void PrintStats() const {
305  detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated,
306  getTotalMemory());
307  }
308 
309 private:
310  /// \brief The current pointer into the current slab.
311  ///
312  /// This points to the next free byte in the slab.
313  char *CurPtr = nullptr;
314 
315  /// \brief The end of the current slab.
316  char *End = nullptr;
317 
318  /// \brief The slabs allocated so far.
320 
321  /// \brief Custom-sized slabs allocated for too-large allocation requests.
322  SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs;
323 
324  /// \brief How many bytes we've allocated.
325  ///
326  /// Used so that we can compute how much space was wasted.
327  size_t BytesAllocated = 0;
328 
329  /// \brief The number of bytes to put between allocations when running under
330  /// a sanitizer.
331  size_t RedZoneSize = 1;
332 
333  /// \brief The allocator instance we use to get slabs of memory.
334  AllocatorT Allocator;
335 
336  static size_t computeSlabSize(unsigned SlabIdx) {
337  // Scale the actual allocated slab size based on the number of slabs
338  // allocated. Every 128 slabs allocated, we double the allocated size to
339  // reduce allocation frequency, but saturate at multiplying the slab size by
340  // 2^30.
341  return SlabSize * ((size_t)1 << std::min<size_t>(30, SlabIdx / 128));
342  }
343 
344  /// \brief Allocate a new slab and move the bump pointers over into the new
345  /// slab, modifying CurPtr and End.
346  void StartNewSlab() {
347  size_t AllocatedSlabSize = computeSlabSize(Slabs.size());
348 
349  void *NewSlab = Allocator.Allocate(AllocatedSlabSize, 0);
350  // We own the new slab and don't want anyone reading anything other than
351  // pieces returned from this method. So poison the whole slab.
352  __asan_poison_memory_region(NewSlab, AllocatedSlabSize);
353 
354  Slabs.push_back(NewSlab);
355  CurPtr = (char *)(NewSlab);
356  End = ((char *)NewSlab) + AllocatedSlabSize;
357  }
358 
359  /// \brief Deallocate a sequence of slabs.
360  void DeallocateSlabs(SmallVectorImpl<void *>::iterator I,
362  for (; I != E; ++I) {
363  size_t AllocatedSlabSize =
364  computeSlabSize(std::distance(Slabs.begin(), I));
365  Allocator.Deallocate(*I, AllocatedSlabSize);
366  }
367  }
368 
369  /// \brief Deallocate all memory for custom sized slabs.
370  void DeallocateCustomSizedSlabs() {
371  for (auto &PtrAndSize : CustomSizedSlabs) {
372  void *Ptr = PtrAndSize.first;
373  size_t Size = PtrAndSize.second;
374  Allocator.Deallocate(Ptr, Size);
375  }
376  }
377 
378  template <typename T> friend class SpecificBumpPtrAllocator;
379 };
380 
381 /// \brief The standard BumpPtrAllocator which just uses the default template
382 /// parameters.
384 
385 /// \brief A BumpPtrAllocator that allows only elements of a specific type to be
386 /// allocated.
387 ///
388 /// This allows calling the destructor in DestroyAll() and when the allocator is
389 /// destroyed.
390 template <typename T> class SpecificBumpPtrAllocator {
391  BumpPtrAllocator Allocator;
392 
393 public:
395  // Because SpecificBumpPtrAllocator walks the memory to call destructors,
396  // it can't have red zones between allocations.
397  Allocator.setRedZoneSize(0);
398  }
400  : Allocator(std::move(Old.Allocator)) {}
401  ~SpecificBumpPtrAllocator() { DestroyAll(); }
402 
404  Allocator = std::move(RHS.Allocator);
405  return *this;
406  }
407 
408  /// Call the destructor of each allocated object and deallocate all but the
409  /// current slab and reset the current pointer to the beginning of it, freeing
410  /// all memory allocated so far.
411  void DestroyAll() {
412  auto DestroyElements = [](char *Begin, char *End) {
413  assert(Begin == (char *)alignAddr(Begin, alignof(T)));
414  for (char *Ptr = Begin; Ptr + sizeof(T) <= End; Ptr += sizeof(T))
415  reinterpret_cast<T *>(Ptr)->~T();
416  };
417 
418  for (auto I = Allocator.Slabs.begin(), E = Allocator.Slabs.end(); I != E;
419  ++I) {
420  size_t AllocatedSlabSize = BumpPtrAllocator::computeSlabSize(
421  std::distance(Allocator.Slabs.begin(), I));
422  char *Begin = (char *)alignAddr(*I, alignof(T));
423  char *End = *I == Allocator.Slabs.back() ? Allocator.CurPtr
424  : (char *)*I + AllocatedSlabSize;
425 
426  DestroyElements(Begin, End);
427  }
428 
429  for (auto &PtrAndSize : Allocator.CustomSizedSlabs) {
430  void *Ptr = PtrAndSize.first;
431  size_t Size = PtrAndSize.second;
432  DestroyElements((char *)alignAddr(Ptr, alignof(T)), (char *)Ptr + Size);
433  }
434 
435  Allocator.Reset();
436  }
437 
438  /// \brief Allocate space for an array of objects without constructing them.
439  T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); }
440 };
441 
442 } // end namespace llvm
443 
444 template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
445 void *operator new(size_t Size,
446  llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize,
447  SizeThreshold> &Allocator) {
448  struct S {
449  char c;
450  union {
451  double D;
452  long double LD;
453  long long L;
454  void *P;
455  } x;
456  };
457  return Allocator.Allocate(
458  Size, std::min((size_t)llvm::NextPowerOf2(Size), offsetof(S, x)));
459 }
460 
461 template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
462 void operator delete(
464 }
465 
466 #endif // LLVM_SUPPORT_ALLOCATOR_H
void push_back(const T &Elt)
Definition: SmallVector.h:212
#define __msan_allocated_memory(p, size)
Definition: Compiler.h:376
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
void Deallocate(const void *Ptr, size_t Size)
Deallocate Ptr to Size bytes of memory allocated by this allocator.
Definition: Allocator.h:63
void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated, size_t TotalMemory)
Definition: Allocator.cpp:21
void * Allocate(size_t Size, size_t Alignment)
Allocate Size bytes of Alignment aligned memory.
Definition: Allocator.h:49
void PrintStats() const
Definition: Allocator.h:115
Definition: BitVector.h:920
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it...
Definition: Allocator.h:197
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
BumpPtrAllocatorImpl & operator=(BumpPtrAllocatorImpl &&RHS)
Definition: Allocator.h:176
void Deallocate(const void *Ptr, size_t Size)
Definition: Allocator.h:280
#define T
void DestroyAll()
Call the destructor of each allocated object and deallocate all but the current slab and reset the cu...
Definition: Allocator.h:411
size_t getBytesAllocated() const
Definition: Allocator.h:298
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:383
#define P(N)
#define __asan_unpoison_memory_region(p, size)
Definition: Compiler.h:388
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:143
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
size_t alignmentAdjustment(const void *Ptr, size_t Alignment)
Returns the necessary adjustment for aligning Ptr to Alignment bytes, rounding up.
Definition: MathExtras.h:626
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, size_t Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:217
static const unsigned End
void Deallocate(const void *Ptr, size_t)
Definition: Allocator.h:108
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
Definition: Allocator.h:439
void setRedZoneSize(size_t NewSize)
Definition: Allocator.h:300
#define LLVM_ATTRIBUTE_RETURNS_NONNULL
Definition: Compiler.h:214
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:632
SpecificBumpPtrAllocator & operator=(SpecificBumpPtrAllocator &&RHS)
Definition: Allocator.h:403
void report_bad_alloc_error(const char *Reason, bool GenCrashDiag=true)
Reports a bad alloc error, calling any user defined bad alloc error handler.
Basic Register Allocator
SpecificBumpPtrAllocator(SpecificBumpPtrAllocator &&Old)
Definition: Allocator.h:399
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:390
size_t GetNumSlabs() const
Definition: Allocator.h:287
#define LLVM_ATTRIBUTE_RETURNS_NOALIAS
LLVM_ATTRIBUTE_RETURNS_NOALIAS Used to mark a function as returning a pointer that does not alias any...
Definition: Compiler.h:224
uintptr_t alignAddr(const void *Addr, size_t Alignment)
Aligns Addr to Alignment bytes, rounding up.
Definition: MathExtras.h:615
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, size_t)
Definition: Allocator.h:96
T * Allocate(size_t Num=1)
Allocate space for a sequence of objects without constructing them.
Definition: Allocator.h:79
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
#define I(x, y, z)
Definition: MD5.cpp:58
std::enable_if< !std::is_same< typename std::remove_cv< T >::type, void >::value, void >::type Deallocate(T *Ptr, size_t Num=1)
Deallocate space for a sequence of objects without constructing them.
Definition: Allocator.h:87
size_t getTotalMemory() const
Definition: Allocator.h:289
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define __asan_poison_memory_region(p, size)
Definition: Compiler.h:387
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
BumpPtrAllocatorImpl(T &&Allocator)
Definition: Allocator.h:155
BumpPtrAllocatorImpl(BumpPtrAllocatorImpl &&Old)
Definition: Allocator.h:160
CRTP base class providing obvious overloads for the core Allocate() methods of LLVM-style allocators...
Definition: Allocator.h:45