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/DataTypes.h" 19#include "llvm/Support/MathExtras.h" 20#include <algorithm> 21#include <cassert> 22#include <cstddef> 23#include <cstdlib> 24 25namespace llvm { 26template <typename T> struct ReferenceAdder { typedef T& result; }; 27template <typename T> struct ReferenceAdder<T&> { typedef T result; }; 28 29class MallocAllocator { 30public: 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. 53class MemSlab { 54public: 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. 64class SlabAllocator { 65public: 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. 74class MallocSlabAllocator : public SlabAllocator { 75 /// Allocator - The underlying allocator that we forward to. 76 /// 77 MallocAllocator Allocator; 78 79public: 80 MallocSlabAllocator() : Allocator() { } 81 virtual ~MallocSlabAllocator(); 82 virtual MemSlab *Allocate(size_t Size) LLVM_OVERRIDE; 83 virtual void Deallocate(MemSlab *Slab) LLVM_OVERRIDE; 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. 90class BumpPtrAllocator { 91 BumpPtrAllocator(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION; 92 void operator=(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION; 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 /// \brief the default allocator used if one is not provided 103 MallocSlabAllocator DefaultSlabAllocator; 104 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; 109 110 /// CurSlab - The slab that we are currently allocating into. 111 /// 112 MemSlab *CurSlab; 113 114 /// CurPtr - The current pointer into the current slab. This points to the 115 /// next free byte in the slab. 116 char *CurPtr; 117 118 /// End - The end of the current slab. 119 /// 120 char *End; 121 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; 125 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); 130 131 /// StartNewSlab - Allocate a new slab and move the bump pointers over into 132 /// the new slab. Modifies CurPtr and End. 133 void StartNewSlab(); 134 135 /// DeallocateSlabs - Deallocate all memory slabs after and including this 136 /// one. 137 void DeallocateSlabs(MemSlab *Slab); 138 139 template<typename T> friend class SpecificBumpPtrAllocator; 140public: 141 BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096); 142 BumpPtrAllocator(size_t size, size_t threshold, SlabAllocator &allocator); 143 ~BumpPtrAllocator(); 144 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. 147 void Reset(); 148 149 /// Allocate - Allocate space at the specified alignment. 150 /// 151 void *Allocate(size_t Size, size_t Alignment); 152 153 /// Allocate space, but do not construct, one object. 154 /// 155 template <typename T> 156 T *Allocate() { 157 return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment)); 158 } 159 160 /// Allocate space for an array of objects. This does not construct the 161 /// objects though. 162 template <typename T> 163 T *Allocate(size_t Num) { 164 return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment)); 165 } 166 167 /// Allocate space for a specific count of elements and with a specified 168 /// alignment. 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)); 174 } 175 176 void Deallocate(const void * /*Ptr*/) {} 177 178 unsigned GetNumSlabs() const; 179 180 void PrintStats() const; 181 182 /// Compute the total physical memory allocated by this allocator. 183 size_t getTotalMemory() const; 184}; 185 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. 189template <typename T> 190class SpecificBumpPtrAllocator { 191 BumpPtrAllocator Allocator; 192public: 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) {} 198 199 ~SpecificBumpPtrAllocator() { 200 DestroyAll(); 201 } 202 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. 206 void DestroyAll() { 207 MemSlab *Slab = Allocator.CurSlab; 208 while (Slab) { 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(); 215 } 216 Slab = Slab->NextPtr; 217 } 218 Allocator.Reset(); 219 } 220 221 /// Allocate space for a specific count of elements. 222 T *Allocate(size_t num = 1) { 223 return Allocator.Allocate<T>(num); 224 } 225}; 226 227} // end namespace llvm 228 229inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) { 230 struct S { 231 char c; 232 union { 233 double D; 234 long double LD; 235 long long L; 236 void *P; 237 } x; 238 }; 239 return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size), 240 offsetof(S, x))); 241} 242 243inline void operator delete(void *, llvm::BumpPtrAllocator &) {} 244 245#endif // LLVM_SUPPORT_ALLOCATOR_H 246