[MCJIT] Revert partial RuntimeDyldELF cleanup that was prematurely committed in
[oota-llvm.git] / 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
36 /// \brief CRTP base class providing obvious overloads for the core \c
37 /// Allocate() methods of LLVM-style allocators.
38 ///
39 /// This base class both documents the full public interface exposed by all
40 /// LLVM-style allocators, and redirects all of the overloads to a single core
41 /// set of methods which the derived class must define.
42 template <typename DerivedT> class AllocatorBase {
43 public:
44   /// \brief Allocate \a Size bytes of \a Alignment aligned memory. This method
45   /// must be implemented by \c DerivedT.
46   void *Allocate(size_t Size, size_t Alignment) {
47 #ifdef __clang__
48     static_assert(static_cast<void *(AllocatorBase::*)(size_t, size_t)>(
49                       &AllocatorBase::Allocate) !=
50                       static_cast<void *(DerivedT::*)(size_t, size_t)>(
51                           &DerivedT::Allocate),
52                   "Class derives from AllocatorBase without implementing the "
53                   "core Allocate(size_t, size_t) overload!");
54 #endif
55     return static_cast<DerivedT *>(this)->Allocate(Size, Alignment);
56   }
57
58   /// \brief Deallocate \a Ptr to \a Size bytes of memory allocated by this
59   /// allocator.
60   void Deallocate(const void *Ptr, size_t Size) {
61 #ifdef __clang__
62     static_assert(static_cast<void (AllocatorBase::*)(const void *, size_t)>(
63                       &AllocatorBase::Deallocate) !=
64                       static_cast<void (DerivedT::*)(const void *, size_t)>(
65                           &DerivedT::Deallocate),
66                   "Class derives from AllocatorBase without implementing the "
67                   "core Deallocate(void *) overload!");
68 #endif
69     return static_cast<DerivedT *>(this)->Deallocate(Ptr, Size);
70   }
71
72   // The rest of these methods are helpers that redirect to one of the above
73   // core methods.
74
75   /// \brief Allocate space for a sequence of objects without constructing them.
76   template <typename T> T *Allocate(size_t Num = 1) {
77     return static_cast<T *>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
78   }
79
80   /// \brief Deallocate space for a sequence of objects without constructing them.
81   template <typename T>
82   typename std::enable_if<
83       !std::is_same<typename std::remove_cv<T>::type, void>::value, void>::type
84   Deallocate(T *Ptr, size_t Num = 1) {
85     Deallocate(static_cast<const void *>(Ptr), Num * sizeof(T));
86   }
87 };
88
89 class MallocAllocator : public AllocatorBase<MallocAllocator> {
90 public:
91   void Reset() {}
92
93   LLVM_ATTRIBUTE_RETURNS_NONNULL void *Allocate(size_t Size,
94                                                 size_t /*Alignment*/) {
95     return malloc(Size);
96   }
97
98   // Pull in base class overloads.
99   using AllocatorBase<MallocAllocator>::Allocate;
100
101   void Deallocate(const void *Ptr, size_t /*Size*/) {
102     free(const_cast<void *>(Ptr));
103   }
104
105   // Pull in base class overloads.
106   using AllocatorBase<MallocAllocator>::Deallocate;
107
108   void PrintStats() const {}
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 MallocAllocator
131 /// object, which wraps malloc, to allocate memory, but it can be changed to
132 /// use a custom allocator.
133 template <typename AllocatorT = MallocAllocator, size_t SlabSize = 4096,
134           size_t SizeThreshold = SlabSize>
135 class BumpPtrAllocatorImpl
136     : public AllocatorBase<
137           BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold>> {
138 public:
139   static_assert(SizeThreshold <= SlabSize,
140                 "The SizeThreshold must be at most the SlabSize to ensure "
141                 "that objects larger than a slab go into their own memory "
142                 "allocation.");
143
144   BumpPtrAllocatorImpl()
145       : CurPtr(nullptr), End(nullptr), BytesAllocated(0), Allocator() {}
146   template <typename T>
147   BumpPtrAllocatorImpl(T &&Allocator)
148       : CurPtr(nullptr), End(nullptr), BytesAllocated(0),
149         Allocator(std::forward<T &&>(Allocator)) {}
150
151   // Manually implement a move constructor as we must clear the old allocators
152   // slabs as a matter of correctness.
153   BumpPtrAllocatorImpl(BumpPtrAllocatorImpl &&Old)
154       : CurPtr(Old.CurPtr), End(Old.End), Slabs(std::move(Old.Slabs)),
155         CustomSizedSlabs(std::move(Old.CustomSizedSlabs)),
156         BytesAllocated(Old.BytesAllocated),
157         Allocator(std::move(Old.Allocator)) {
158     Old.CurPtr = Old.End = nullptr;
159     Old.BytesAllocated = 0;
160     Old.Slabs.clear();
161     Old.CustomSizedSlabs.clear();
162   }
163
164   ~BumpPtrAllocatorImpl() {
165     DeallocateSlabs(Slabs.begin(), Slabs.end());
166     DeallocateCustomSizedSlabs();
167   }
168
169   BumpPtrAllocatorImpl &operator=(BumpPtrAllocatorImpl &&RHS) {
170     DeallocateSlabs(Slabs.begin(), Slabs.end());
171     DeallocateCustomSizedSlabs();
172
173     CurPtr = RHS.CurPtr;
174     End = RHS.End;
175     BytesAllocated = RHS.BytesAllocated;
176     Slabs = std::move(RHS.Slabs);
177     CustomSizedSlabs = std::move(RHS.CustomSizedSlabs);
178     Allocator = std::move(RHS.Allocator);
179
180     RHS.CurPtr = RHS.End = nullptr;
181     RHS.BytesAllocated = 0;
182     RHS.Slabs.clear();
183     RHS.CustomSizedSlabs.clear();
184     return *this;
185   }
186
187   /// \brief Deallocate all but the current slab and reset the current pointer
188   /// to the beginning of it, freeing all memory allocated so far.
189   void Reset() {
190     if (Slabs.empty())
191       return;
192
193     // Reset the state.
194     BytesAllocated = 0;
195     CurPtr = (char *)Slabs.front();
196     End = CurPtr + SlabSize;
197
198     // Deallocate all but the first slab, and all custome sized slabs.
199     DeallocateSlabs(std::next(Slabs.begin()), Slabs.end());
200     Slabs.erase(std::next(Slabs.begin()), Slabs.end());
201     DeallocateCustomSizedSlabs();
202     CustomSizedSlabs.clear();
203   }
204
205   /// \brief Allocate space at the specified alignment.
206   LLVM_ATTRIBUTE_RETURNS_NONNULL void *Allocate(size_t Size, size_t Alignment) {
207     assert(Alignment > 0 && "0-byte alignnment is not allowed. Use 1 instead.");
208
209     // Keep track of how many bytes we've allocated.
210     BytesAllocated += Size;
211
212     // Allocate the aligned space, going forwards from CurPtr.
213     uintptr_t AlignedAddr = alignAddr(CurPtr, Alignment);
214
215     // Check if we can hold it.
216     if (AlignedAddr + Size <= (uintptr_t)End) {
217       char *AlignedPtr = (char*)AlignedAddr;
218       CurPtr = AlignedPtr + Size;
219       // Update the allocation point of this memory block in MemorySanitizer.
220       // Without this, MemorySanitizer messages for values originated from here
221       // will point to the allocation of the entire slab.
222       __msan_allocated_memory(AlignedPtr, Size);
223       return AlignedPtr;
224     }
225
226     // If Size is really big, allocate a separate slab for it.
227     size_t PaddedSize = Size + Alignment - 1;
228     if (PaddedSize > SizeThreshold) {
229       void *NewSlab = Allocator.Allocate(PaddedSize, 0);
230       CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize));
231
232       uintptr_t AlignedAddr = alignAddr(NewSlab, Alignment);
233       assert(AlignedAddr + Size <= (uintptr_t)NewSlab + PaddedSize);
234       char *AlignedPtr = (char*)AlignedAddr;
235       __msan_allocated_memory(AlignedPtr, Size);
236       return AlignedPtr;
237     }
238
239     // Otherwise, start a new slab and try again.
240     StartNewSlab();
241     AlignedAddr = alignAddr(CurPtr, Alignment);
242     assert(AlignedAddr + Size <= (uintptr_t)End &&
243            "Unable to allocate memory!");
244     char *AlignedPtr = (char*)AlignedAddr;
245     CurPtr = AlignedPtr + Size;
246     __msan_allocated_memory(AlignedPtr, Size);
247     return AlignedPtr;
248   }
249
250   // Pull in base class overloads.
251   using AllocatorBase<BumpPtrAllocatorImpl>::Allocate;
252
253   void Deallocate(const void * /*Ptr*/, size_t /*Size*/) {}
254
255   // Pull in base class overloads.
256   using AllocatorBase<BumpPtrAllocatorImpl>::Deallocate;
257
258   size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); }
259
260   size_t getTotalMemory() const {
261     size_t TotalMemory = 0;
262     for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I)
263       TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I));
264     for (auto &PtrAndSize : CustomSizedSlabs)
265       TotalMemory += PtrAndSize.second;
266     return TotalMemory;
267   }
268
269   void PrintStats() const {
270     detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated,
271                                        getTotalMemory());
272   }
273
274 private:
275   /// \brief The current pointer into the current slab.
276   ///
277   /// This points to the next free byte in the slab.
278   char *CurPtr;
279
280   /// \brief The end of the current slab.
281   char *End;
282
283   /// \brief The slabs allocated so far.
284   SmallVector<void *, 4> Slabs;
285
286   /// \brief Custom-sized slabs allocated for too-large allocation requests.
287   SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs;
288
289   /// \brief How many bytes we've allocated.
290   ///
291   /// Used so that we can compute how much space was wasted.
292   size_t BytesAllocated;
293
294   /// \brief The allocator instance we use to get slabs of memory.
295   AllocatorT Allocator;
296
297   static size_t computeSlabSize(unsigned SlabIdx) {
298     // Scale the actual allocated slab size based on the number of slabs
299     // allocated. Every 128 slabs allocated, we double the allocated size to
300     // reduce allocation frequency, but saturate at multiplying the slab size by
301     // 2^30.
302     return SlabSize * ((size_t)1 << std::min<size_t>(30, SlabIdx / 128));
303   }
304
305   /// \brief Allocate a new slab and move the bump pointers over into the new
306   /// slab, modifying CurPtr and End.
307   void StartNewSlab() {
308     size_t AllocatedSlabSize = computeSlabSize(Slabs.size());
309
310     void *NewSlab = Allocator.Allocate(AllocatedSlabSize, 0);
311     Slabs.push_back(NewSlab);
312     CurPtr = (char *)(NewSlab);
313     End = ((char *)NewSlab) + AllocatedSlabSize;
314   }
315
316   /// \brief Deallocate a sequence of slabs.
317   void DeallocateSlabs(SmallVectorImpl<void *>::iterator I,
318                        SmallVectorImpl<void *>::iterator E) {
319     for (; I != E; ++I) {
320       size_t AllocatedSlabSize =
321           computeSlabSize(std::distance(Slabs.begin(), I));
322 #ifndef NDEBUG
323       // Poison the memory so stale pointers crash sooner.  Note we must
324       // preserve the Size and NextPtr fields at the beginning.
325       if (AllocatedSlabSize != 0) {
326         sys::Memory::setRangeWritable(*I, AllocatedSlabSize);
327         memset(*I, 0xCD, AllocatedSlabSize);
328       }
329 #endif
330       Allocator.Deallocate(*I, AllocatedSlabSize);
331     }
332   }
333
334   /// \brief Deallocate all memory for custom sized slabs.
335   void DeallocateCustomSizedSlabs() {
336     for (auto &PtrAndSize : CustomSizedSlabs) {
337       void *Ptr = PtrAndSize.first;
338       size_t Size = PtrAndSize.second;
339 #ifndef NDEBUG
340       // Poison the memory so stale pointers crash sooner.  Note we must
341       // preserve the Size and NextPtr fields at the beginning.
342       sys::Memory::setRangeWritable(Ptr, Size);
343       memset(Ptr, 0xCD, Size);
344 #endif
345       Allocator.Deallocate(Ptr, Size);
346     }
347   }
348
349   template <typename T> friend class SpecificBumpPtrAllocator;
350 };
351
352 /// \brief The standard BumpPtrAllocator which just uses the default template
353 /// paramaters.
354 typedef BumpPtrAllocatorImpl<> BumpPtrAllocator;
355
356 /// \brief A BumpPtrAllocator that allows only elements of a specific type to be
357 /// allocated.
358 ///
359 /// This allows calling the destructor in DestroyAll() and when the allocator is
360 /// destroyed.
361 template <typename T> class SpecificBumpPtrAllocator {
362   BumpPtrAllocator Allocator;
363
364 public:
365   SpecificBumpPtrAllocator() : Allocator() {}
366   SpecificBumpPtrAllocator(SpecificBumpPtrAllocator &&Old)
367       : Allocator(std::move(Old.Allocator)) {}
368   ~SpecificBumpPtrAllocator() { DestroyAll(); }
369
370   SpecificBumpPtrAllocator &operator=(SpecificBumpPtrAllocator &&RHS) {
371     Allocator = std::move(RHS.Allocator);
372     return *this;
373   }
374
375   /// Call the destructor of each allocated object and deallocate all but the
376   /// current slab and reset the current pointer to the beginning of it, freeing
377   /// all memory allocated so far.
378   void DestroyAll() {
379     auto DestroyElements = [](char *Begin, char *End) {
380       assert(Begin == (char*)alignAddr(Begin, alignOf<T>()));
381       for (char *Ptr = Begin; Ptr + sizeof(T) <= End; Ptr += sizeof(T))
382         reinterpret_cast<T *>(Ptr)->~T();
383     };
384
385     for (auto I = Allocator.Slabs.begin(), E = Allocator.Slabs.end(); I != E;
386          ++I) {
387       size_t AllocatedSlabSize = BumpPtrAllocator::computeSlabSize(
388           std::distance(Allocator.Slabs.begin(), I));
389       char *Begin = (char*)alignAddr(*I, alignOf<T>());
390       char *End = *I == Allocator.Slabs.back() ? Allocator.CurPtr
391                                                : (char *)*I + AllocatedSlabSize;
392
393       DestroyElements(Begin, End);
394     }
395
396     for (auto &PtrAndSize : Allocator.CustomSizedSlabs) {
397       void *Ptr = PtrAndSize.first;
398       size_t Size = PtrAndSize.second;
399       DestroyElements((char*)alignAddr(Ptr, alignOf<T>()), (char *)Ptr + Size);
400     }
401
402     Allocator.Reset();
403   }
404
405   /// \brief Allocate space for an array of objects without constructing them.
406   T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); }
407 };
408
409 }  // end namespace llvm
410
411 template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
412 void *operator new(size_t Size,
413                    llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize,
414                                               SizeThreshold> &Allocator) {
415   struct S {
416     char c;
417     union {
418       double D;
419       long double LD;
420       long long L;
421       void *P;
422     } x;
423   };
424   return Allocator.Allocate(
425       Size, std::min((size_t)llvm::NextPowerOf2(Size), offsetof(S, x)));
426 }
427
428 template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
429 void operator delete(
430     void *, llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold> &) {
431 }
432
433 #endif // LLVM_SUPPORT_ALLOCATOR_H