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 { typedef T& result; };
27 template <typename T> struct ReferenceAdder<T&> { typedef T result; };
29 class MallocAllocator {
36 void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
39 T *Allocate() { return static_cast<T*>(malloc(sizeof(T))); }
42 T *Allocate(size_t Num) {
43 return static_cast<T*>(malloc(sizeof(T)*Num));
46 void Deallocate(const void *Ptr) { free(const_cast<void*>(Ptr)); }
48 void PrintStats() const {}
51 /// MemSlab - This structure lives at the beginning of every slab allocated by
52 /// the bump allocator.
59 /// SlabAllocator - This class can be used to parameterize the underlying
60 /// allocation strategy for the bump allocator. In particular, this is used
61 /// by the JIT to allocate contiguous swathes of executable memory. The
62 /// interface uses MemSlab's instead of void *'s so that the allocator
63 /// doesn't have to remember the size of the pointer it allocated.
66 virtual ~SlabAllocator();
67 virtual MemSlab *Allocate(size_t Size) = 0;
68 virtual void Deallocate(MemSlab *Slab) = 0;
71 /// MallocSlabAllocator - The default slab allocator for the bump allocator
72 /// is an adapter class for MallocAllocator that just forwards the method
73 /// calls and translates the arguments.
74 class MallocSlabAllocator : public SlabAllocator {
75 /// Allocator - The underlying allocator that we forward to.
77 MallocAllocator Allocator;
80 MallocSlabAllocator() : Allocator() { }
81 virtual ~MallocSlabAllocator();
82 virtual MemSlab *Allocate(size_t Size) LLVM_OVERRIDE;
83 virtual void Deallocate(MemSlab *Slab) LLVM_OVERRIDE;
86 /// BumpPtrAllocator - This allocator is useful for containers that need
87 /// very simple memory allocation strategies. In particular, this just keeps
88 /// allocating memory, and never deletes it until the entire block is dead. This
89 /// makes allocation speedy, but must only be used when the trade-off is ok.
90 class BumpPtrAllocator {
91 BumpPtrAllocator(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
92 void operator=(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
94 /// SlabSize - Allocate data into slabs of this size unless we get an
95 /// allocation above SizeThreshold.
98 /// SizeThreshold - For any allocation larger than this threshold, we should
99 /// allocate a separate slab.
100 size_t SizeThreshold;
102 /// \brief the default allocator used if one is not provided
103 MallocSlabAllocator DefaultSlabAllocator;
105 /// Allocator - The underlying allocator we use to get slabs of memory. This
106 /// defaults to MallocSlabAllocator, which wraps malloc, but it could be
107 /// changed to use a custom allocator.
108 SlabAllocator &Allocator;
110 /// CurSlab - The slab that we are currently allocating into.
114 /// CurPtr - The current pointer into the current slab. This points to the
115 /// next free byte in the slab.
118 /// End - The end of the current slab.
122 /// BytesAllocated - This field tracks how many bytes we've allocated, so
123 /// that we can compute how much space was wasted.
124 size_t BytesAllocated;
126 /// AlignPtr - Align Ptr to Alignment bytes, rounding up. Alignment should
127 /// be a power of two. This method rounds up, so AlignPtr(7, 4) == 8 and
128 /// AlignPtr(8, 4) == 8.
129 static char *AlignPtr(char *Ptr, size_t Alignment);
131 /// StartNewSlab - Allocate a new slab and move the bump pointers over into
132 /// the new slab. Modifies CurPtr and End.
135 /// DeallocateSlabs - Deallocate all memory slabs after and including this
137 void DeallocateSlabs(MemSlab *Slab);
139 template<typename T> friend class SpecificBumpPtrAllocator;
141 BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096);
142 BumpPtrAllocator(size_t size, size_t threshold, SlabAllocator &allocator);
145 /// Reset - Deallocate all but the current slab and reset the current pointer
146 /// to the beginning of it, freeing all memory allocated so far.
149 /// Allocate - Allocate space at the specified alignment.
151 void *Allocate(size_t Size, size_t Alignment);
153 /// Allocate space, but do not construct, one object.
155 template <typename T>
157 return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment));
160 /// Allocate space for an array of objects. This does not construct the
162 template <typename T>
163 T *Allocate(size_t Num) {
164 return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
167 /// Allocate space for a specific count of elements and with a specified
169 template <typename T>
170 T *Allocate(size_t Num, size_t Alignment) {
171 // Round EltSize up to the specified alignment.
172 size_t EltSize = (sizeof(T)+Alignment-1)&(-Alignment);
173 return static_cast<T*>(Allocate(Num * EltSize, Alignment));
176 void Deallocate(const void * /*Ptr*/) {}
178 unsigned GetNumSlabs() const;
180 void PrintStats() const;
182 /// Compute the total physical memory allocated by this allocator.
183 size_t getTotalMemory() const;
186 /// SpecificBumpPtrAllocator - Same as BumpPtrAllocator but allows only
187 /// elements of one type to be allocated. This allows calling the destructor
188 /// in DestroyAll() and when the allocator is destroyed.
189 template <typename T>
190 class SpecificBumpPtrAllocator {
191 BumpPtrAllocator Allocator;
193 SpecificBumpPtrAllocator(size_t size = 4096, size_t threshold = 4096)
194 : Allocator(size, threshold) {}
195 SpecificBumpPtrAllocator(size_t size, size_t threshold,
196 SlabAllocator &allocator)
197 : Allocator(size, threshold, allocator) {}
199 ~SpecificBumpPtrAllocator() {
203 /// Call the destructor of each allocated object and deallocate all but the
204 /// current slab and reset the current pointer to the beginning of it, freeing
205 /// all memory allocated so far.
207 MemSlab *Slab = Allocator.CurSlab;
209 char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr :
210 (char *)Slab + Slab->Size;
211 for (char *Ptr = (char*)(Slab+1); Ptr < End; Ptr += sizeof(T)) {
212 Ptr = Allocator.AlignPtr(Ptr, alignOf<T>());
213 if (Ptr + sizeof(T) <= End)
214 reinterpret_cast<T*>(Ptr)->~T();
216 Slab = Slab->NextPtr;
221 /// Allocate space for a specific count of elements.
222 T *Allocate(size_t num = 1) {
223 return Allocator.Allocate<T>(num);
227 } // end namespace llvm
229 inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
239 return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
243 inline void operator delete(void *, llvm::BumpPtrAllocator &) {}
245 #endif // LLVM_SUPPORT_ALLOCATOR_H