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/ADT/ArrayRef.h"
18 #include "llvm/ADT/StringRef.h"
19 #include "llvm/Support/AlignOf.h"
20 #include "llvm/Support/DataTypes.h"
21 #include "llvm/Support/MathExtras.h"
28 template <typename T> struct ReferenceAdder { typedef T& result; };
29 template <typename T> struct ReferenceAdder<T&> { typedef T result; };
31 class MallocAllocator {
38 void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
41 T *Allocate() { return static_cast<T*>(malloc(sizeof(T))); }
44 T *Allocate(size_t Num) {
45 return static_cast<T*>(malloc(sizeof(T)*Num));
48 void Deallocate(const void *Ptr) { free(const_cast<void*>(Ptr)); }
50 void PrintStats() const {}
53 /// MemSlab - This structure lives at the beginning of every slab allocated by
54 /// the bump allocator.
61 /// SlabAllocator - This class can be used to parameterize the underlying
62 /// allocation strategy for the bump allocator. In particular, this is used
63 /// by the JIT to allocate contiguous swathes of executable memory. The
64 /// interface uses MemSlab's instead of void *'s so that the allocator
65 /// doesn't have to remember the size of the pointer it allocated.
68 virtual ~SlabAllocator();
69 virtual MemSlab *Allocate(size_t Size) = 0;
70 virtual void Deallocate(MemSlab *Slab) = 0;
73 /// MallocSlabAllocator - The default slab allocator for the bump allocator
74 /// is an adapter class for MallocAllocator that just forwards the method
75 /// calls and translates the arguments.
76 class MallocSlabAllocator : public SlabAllocator {
77 /// Allocator - The underlying allocator that we forward to.
79 MallocAllocator Allocator;
82 MallocSlabAllocator() : Allocator() { }
83 virtual ~MallocSlabAllocator();
84 virtual MemSlab *Allocate(size_t Size) LLVM_OVERRIDE;
85 virtual void Deallocate(MemSlab *Slab) LLVM_OVERRIDE;
88 /// BumpPtrAllocator - This allocator is useful for containers that need
89 /// very simple memory allocation strategies. In particular, this just keeps
90 /// allocating memory, and never deletes it until the entire block is dead. This
91 /// makes allocation speedy, but must only be used when the trade-off is ok.
92 class BumpPtrAllocator {
93 BumpPtrAllocator(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
94 void operator=(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
96 /// SlabSize - Allocate data into slabs of this size unless we get an
97 /// allocation above SizeThreshold.
100 /// SizeThreshold - For any allocation larger than this threshold, we should
101 /// allocate a separate slab.
102 size_t SizeThreshold;
104 /// \brief the default allocator used if one is not provided
105 MallocSlabAllocator DefaultSlabAllocator;
107 /// Allocator - The underlying allocator we use to get slabs of memory. This
108 /// defaults to MallocSlabAllocator, which wraps malloc, but it could be
109 /// changed to use a custom allocator.
110 SlabAllocator &Allocator;
112 /// CurSlab - The slab that we are currently allocating into.
116 /// CurPtr - The current pointer into the current slab. This points to the
117 /// next free byte in the slab.
120 /// End - The end of the current slab.
124 /// BytesAllocated - This field tracks how many bytes we've allocated, so
125 /// that we can compute how much space was wasted.
126 size_t BytesAllocated;
128 /// AlignPtr - Align Ptr to Alignment bytes, rounding up. Alignment should
129 /// be a power of two. This method rounds up, so AlignPtr(7, 4) == 8 and
130 /// AlignPtr(8, 4) == 8.
131 static char *AlignPtr(char *Ptr, size_t Alignment);
133 /// StartNewSlab - Allocate a new slab and move the bump pointers over into
134 /// the new slab. Modifies CurPtr and End.
137 /// DeallocateSlabs - Deallocate all memory slabs after and including this
139 void DeallocateSlabs(MemSlab *Slab);
141 template<typename T> friend class SpecificBumpPtrAllocator;
143 BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096);
144 BumpPtrAllocator(size_t size, size_t threshold, SlabAllocator &allocator);
147 /// Reset - Deallocate all but the current slab and reset the current pointer
148 /// to the beginning of it, freeing all memory allocated so far.
151 /// Allocate - Allocate space at the specified alignment.
153 void *Allocate(size_t Size, size_t Alignment);
155 /// Allocate space, but do not construct, one object.
157 template <typename T>
159 return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment));
162 /// Allocate space for an array of objects. This does not construct the
164 template <typename T>
165 T *Allocate(size_t Num) {
166 return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
169 /// Allocate space for a specific count of elements and with a specified
171 template <typename T>
172 T *Allocate(size_t Num, size_t Alignment) {
173 // Round EltSize up to the specified alignment.
174 size_t EltSize = (sizeof(T)+Alignment-1)&(-Alignment);
175 return static_cast<T*>(Allocate(Num * EltSize, Alignment));
178 void Deallocate(const void * /*Ptr*/) {}
180 unsigned GetNumSlabs() const;
182 void PrintStats() const;
185 /// Allocate space and copy content into it.
186 void *allocateCopy(const void *Src, size_t Size, size_t Alignment=1) {
187 void *P = Allocate(Size, Alignment);
188 memcpy(P, Src, Size);
192 /// Allocate space for an array of type T, and use std::copy()
193 /// to copy the array contents.
194 template <typename T>
195 typename enable_if<isPodLike<T>, T*>::type
196 allocateCopy(const T Src[], size_t Num) {
197 T *P = Allocate<T>(Num);
198 std::copy(Src, &Src[Num], P);
202 /// Copy a StringRef by allocating copy in BumpPtrAllocator.
203 StringRef allocateCopy(StringRef Str) {
204 size_t Length = Str.size();
205 char *P = allocateCopy<char>(Str.data(), Length);
206 return StringRef(P, Length);
209 /// Copy a ArrayRef<T> by allocating copy in BumpPtrAllocator.
210 template <typename T>
211 typename enable_if<isPodLike<T>, ArrayRef<T> >::type
212 allocateCopy(ArrayRef<T> Src) {
213 size_t Length = Src.size();
214 T *P = allocateCopy<T>(Src.data(), Length);
215 return makeArrayRef(P, Length);
218 /// Compute the total physical memory allocated by this allocator.
219 size_t getTotalMemory() const;
222 /// SpecificBumpPtrAllocator - Same as BumpPtrAllocator but allows only
223 /// elements of one type to be allocated. This allows calling the destructor
224 /// in DestroyAll() and when the allocator is destroyed.
225 template <typename T>
226 class SpecificBumpPtrAllocator {
227 BumpPtrAllocator Allocator;
229 SpecificBumpPtrAllocator(size_t size = 4096, size_t threshold = 4096)
230 : Allocator(size, threshold) {}
231 SpecificBumpPtrAllocator(size_t size, size_t threshold,
232 SlabAllocator &allocator)
233 : Allocator(size, threshold, allocator) {}
235 ~SpecificBumpPtrAllocator() {
239 /// Call the destructor of each allocated object and deallocate all but the
240 /// current slab and reset the current pointer to the beginning of it, freeing
241 /// all memory allocated so far.
243 MemSlab *Slab = Allocator.CurSlab;
245 char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr :
246 (char *)Slab + Slab->Size;
247 for (char *Ptr = (char*)(Slab+1); Ptr < End; Ptr += sizeof(T)) {
248 Ptr = Allocator.AlignPtr(Ptr, alignOf<T>());
249 if (Ptr + sizeof(T) <= End)
250 reinterpret_cast<T*>(Ptr)->~T();
252 Slab = Slab->NextPtr;
257 /// Allocate space for a specific count of elements.
258 T *Allocate(size_t num = 1) {
259 return Allocator.Allocate<T>(num);
263 } // end namespace llvm
265 inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
275 return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
279 inline void operator delete(void *, llvm::BumpPtrAllocator &) {}
281 #endif // LLVM_SUPPORT_ALLOCATOR_H