1 //===--- Allocator.h - Simple memory allocation abstraction -----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the MallocAllocator and BumpPtrAllocator interfaces.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_SUPPORT_ALLOCATOR_H
15 #define LLVM_SUPPORT_ALLOCATOR_H
17 #include "llvm/Support/AlignOf.h"
18 #include "llvm/Support/DataTypes.h"
19 #include "llvm/Support/MathExtras.h"
26 template <typename T> struct ReferenceAdder {
29 template <typename T> struct ReferenceAdder<T &> {
33 class MallocAllocator {
40 void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
42 template <typename T> T *Allocate() {
43 return static_cast<T *>(malloc(sizeof(T)));
46 template <typename T> T *Allocate(size_t Num) {
47 return static_cast<T *>(malloc(sizeof(T) * Num));
50 void Deallocate(const void *Ptr) { free(const_cast<void *>(Ptr)); }
52 void PrintStats() const {}
55 /// MemSlab - This structure lives at the beginning of every slab allocated by
56 /// the bump allocator.
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.
70 virtual ~SlabAllocator();
71 virtual MemSlab *Allocate(size_t Size) = 0;
72 virtual void Deallocate(MemSlab *Slab) = 0;
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.
81 MallocAllocator Allocator;
84 MallocSlabAllocator() : Allocator() {}
85 virtual ~MallocSlabAllocator();
86 MemSlab *Allocate(size_t Size) override;
87 void Deallocate(MemSlab *Slab) override;
90 /// \brief Allocate memory in an ever growing pool, as if by bump-pointer.
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.
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;
104 /// \brief Allocate at least this many bytes of memory in a slab.
107 /// \brief Threshold above which allocations to go into a dedicated slab.
108 size_t SizeThreshold;
110 /// \brief The default allocator used if one is not provided.
111 MallocSlabAllocator DefaultSlabAllocator;
113 /// \brief The underlying allocator we use to get slabs of memory.
115 /// This defaults to MallocSlabAllocator, which wraps malloc, but it could be
116 /// changed to use a custom allocator.
117 SlabAllocator &Allocator;
119 /// \brief The slab that we are currently allocating into.
122 /// \brief The current pointer into the current slab.
124 /// This points to the next free byte in the slab.
127 /// \brief The end of the current slab.
130 /// \brief How many bytes we've allocated.
132 /// Used so that we can compute how much space was wasted.
133 size_t BytesAllocated;
135 /// \brief Aligns \c Ptr to \c Alignment bytes, rounding up.
137 /// Alignment should be a power of two. This method rounds up, so
138 /// AlignPtr(7, 4) == 8 and AlignPtr(8, 4) == 8.
139 static char *AlignPtr(char *Ptr, size_t Alignment);
141 /// \brief Allocate a new slab and move the bump pointers over into the new
142 /// slab, modifying CurPtr and End.
145 /// \brief Deallocate all memory slabs after and including this one.
146 void DeallocateSlabs(MemSlab *Slab);
148 template <typename T> friend class SpecificBumpPtrAllocator;
151 BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096);
152 BumpPtrAllocator(size_t size, size_t threshold, SlabAllocator &allocator);
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.
159 /// \brief Allocate space at the specified alignment.
160 void *Allocate(size_t Size, size_t Alignment);
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));
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));
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));
180 void Deallocate(const void * /*Ptr*/) {}
182 unsigned GetNumSlabs() const;
184 void PrintStats() const;
186 /// \brief Returns the total physical memory allocated by this allocator.
187 size_t getTotalMemory() const;
190 /// \brief A BumpPtrAllocator that allows only elements of a specific type to be
193 /// This allows calling the destructor in DestroyAll() and when the allocator is
195 template <typename T> class SpecificBumpPtrAllocator {
196 BumpPtrAllocator Allocator;
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) {}
205 ~SpecificBumpPtrAllocator() { DestroyAll(); }
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.
211 MemSlab *Slab = Allocator.CurSlab;
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 = Allocator.AlignPtr(Ptr, alignOf<T>());
217 if (Ptr + sizeof(T) <= End)
218 reinterpret_cast<T *>(Ptr)->~T();
220 Slab = Slab->NextPtr;
225 /// \brief Allocate space for an array of objects without constructing them.
226 T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); }
229 } // end namespace llvm
231 inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
241 return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
245 inline void operator delete(void *, llvm::BumpPtrAllocator &) {}
247 #endif // LLVM_SUPPORT_ALLOCATOR_H