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
