• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 //
10 // This file defines the MallocAllocator and BumpPtrAllocator interfaces.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_SUPPORT_ALLOCATOR_H
15 #define LLVM_SUPPORT_ALLOCATOR_H
16 
17 #include "llvm/Support/AlignOf.h"
18 #include "llvm/Support/MathExtras.h"
19 #include "llvm/Support/DataTypes.h"
20 #include <algorithm>
21 #include <cassert>
22 #include <cstdlib>
23 #include <cstddef>
24 
25 namespace llvm {
26 template <typename T> struct ReferenceAdder { typedef T& result; };
27 template <typename T> struct ReferenceAdder<T&> { typedef T result; };
28 
29 class MallocAllocator {
30 public:
31   MallocAllocator() {}
32   ~MallocAllocator() {}
33 
34   void Reset() {}
35 
36   void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
37 
38   template <typename T>
39   T *Allocate() { return static_cast<T*>(malloc(sizeof(T))); }
40 
41   template <typename T>
42   T *Allocate(size_t Num) {
43     return static_cast<T*>(malloc(sizeof(T)*Num));
44   }
45 
46   void Deallocate(const void *Ptr) { free(const_cast<void*>(Ptr)); }
47 
48   void PrintStats() const {}
49 };
50 
51 /// MemSlab - This structure lives at the beginning of every slab allocated by
52 /// the bump allocator.
53 class MemSlab {
54 public:
55   size_t Size;
56   MemSlab *NextPtr;
57 };
58 
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.
64 class SlabAllocator {
65 public:
66   virtual ~SlabAllocator();
67   virtual MemSlab *Allocate(size_t Size) = 0;
68   virtual void Deallocate(MemSlab *Slab) = 0;
69 };
70 
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.
76   ///
77   MallocAllocator Allocator;
78 
79 public:
80   MallocSlabAllocator() : Allocator() { }
81   virtual ~MallocSlabAllocator();
82   virtual MemSlab *Allocate(size_t Size);
83   virtual void Deallocate(MemSlab *Slab);
84 };
85 
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 &); // do not implement
92   void operator=(const BumpPtrAllocator &);   // do not implement
93 
94   /// SlabSize - Allocate data into slabs of this size unless we get an
95   /// allocation above SizeThreshold.
96   size_t SlabSize;
97 
98   /// SizeThreshold - For any allocation larger than this threshold, we should
99   /// allocate a separate slab.
100   size_t SizeThreshold;
101 
102   /// Allocator - The underlying allocator we use to get slabs of memory.  This
103   /// defaults to MallocSlabAllocator, which wraps malloc, but it could be
104   /// changed to use a custom allocator.
105   SlabAllocator &Allocator;
106 
107   /// CurSlab - The slab that we are currently allocating into.
108   ///
109   MemSlab *CurSlab;
110 
111   /// CurPtr - The current pointer into the current slab.  This points to the
112   /// next free byte in the slab.
113   char *CurPtr;
114 
115   /// End - The end of the current slab.
116   ///
117   char *End;
118 
119   /// BytesAllocated - This field tracks how many bytes we've allocated, so
120   /// that we can compute how much space was wasted.
121   size_t BytesAllocated;
122 
123   /// AlignPtr - Align Ptr to Alignment bytes, rounding up.  Alignment should
124   /// be a power of two.  This method rounds up, so AlignPtr(7, 4) == 8 and
125   /// AlignPtr(8, 4) == 8.
126   static char *AlignPtr(char *Ptr, size_t Alignment);
127 
128   /// StartNewSlab - Allocate a new slab and move the bump pointers over into
129   /// the new slab.  Modifies CurPtr and End.
130   void StartNewSlab();
131 
132   /// DeallocateSlabs - Deallocate all memory slabs after and including this
133   /// one.
134   void DeallocateSlabs(MemSlab *Slab);
135 
136   static MallocSlabAllocator DefaultSlabAllocator;
137 
138   template<typename T> friend class SpecificBumpPtrAllocator;
139 public:
140   BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096,
141                    SlabAllocator &allocator = DefaultSlabAllocator);
142   ~BumpPtrAllocator();
143 
144   /// Reset - Deallocate all but the current slab and reset the current pointer
145   /// to the beginning of it, freeing all memory allocated so far.
146   void Reset();
147 
148   /// Allocate - Allocate space at the specified alignment.
149   ///
150   void *Allocate(size_t Size, size_t Alignment);
151 
152   /// Allocate space, but do not construct, one object.
153   ///
154   template <typename T>
155   T *Allocate() {
156     return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment));
157   }
158 
159   /// Allocate space for an array of objects.  This does not construct the
160   /// objects though.
161   template <typename T>
162   T *Allocate(size_t Num) {
163     return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
164   }
165 
166   /// Allocate space for a specific count of elements and with a specified
167   /// alignment.
168   template <typename T>
169   T *Allocate(size_t Num, size_t Alignment) {
170     // Round EltSize up to the specified alignment.
171     size_t EltSize = (sizeof(T)+Alignment-1)&(-Alignment);
172     return static_cast<T*>(Allocate(Num * EltSize, Alignment));
173   }
174 
175   void Deallocate(const void * /*Ptr*/) {}
176 
177   unsigned GetNumSlabs() const;
178 
179   void PrintStats() const;
180 
181   /// Compute the total physical memory allocated by this allocator.
182   size_t getTotalMemory() const;
183 };
184 
185 /// SpecificBumpPtrAllocator - Same as BumpPtrAllocator but allows only
186 /// elements of one type to be allocated. This allows calling the destructor
187 /// in DestroyAll() and when the allocator is destroyed.
188 template <typename T>
189 class SpecificBumpPtrAllocator {
190   BumpPtrAllocator Allocator;
191 public:
192   SpecificBumpPtrAllocator(size_t size = 4096, size_t threshold = 4096,
193               SlabAllocator &allocator = BumpPtrAllocator::DefaultSlabAllocator)
194     : Allocator(size, threshold, allocator) {}
195 
196   ~SpecificBumpPtrAllocator() {
197     DestroyAll();
198   }
199 
200   /// Call the destructor of each allocated object and deallocate all but the
201   /// current slab and reset the current pointer to the beginning of it, freeing
202   /// all memory allocated so far.
203   void DestroyAll() {
204     MemSlab *Slab = Allocator.CurSlab;
205     while (Slab) {
206       char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr :
207                                               (char *)Slab + Slab->Size;
208       for (char *Ptr = (char*)(Slab+1); Ptr < End; Ptr += sizeof(T)) {
209         Ptr = Allocator.AlignPtr(Ptr, alignOf<T>());
210         if (Ptr + sizeof(T) <= End)
211           reinterpret_cast<T*>(Ptr)->~T();
212       }
213       Slab = Slab->NextPtr;
214     }
215     Allocator.Reset();
216   }
217 
218   /// Allocate space for a specific count of elements.
219   T *Allocate(size_t num = 1) {
220     return Allocator.Allocate<T>(num);
221   }
222 };
223 
224 }  // end namespace llvm
225 
226 inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
227   struct S {
228     char c;
229     union {
230       double D;
231       long double LD;
232       long long L;
233       void *P;
234     } x;
235   };
236   return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
237                                            offsetof(S, x)));
238 }
239 
240 inline void operator delete(void *, llvm::BumpPtrAllocator &) {}
241 
242 #endif // LLVM_SUPPORT_ALLOCATOR_H
243