Allocator.h revision 263508
1213288Sdavidxu//===--- Allocator.h - Simple memory allocation abstraction -----*- C++ -*-===// 2213288Sdavidxu// 3213288Sdavidxu// The LLVM Compiler Infrastructure 4213288Sdavidxu// 5213288Sdavidxu// This file is distributed under the University of Illinois Open Source 6213288Sdavidxu// License. See LICENSE.TXT for details. 7213288Sdavidxu// 8213288Sdavidxu//===----------------------------------------------------------------------===// 9213288Sdavidxu// 10213288Sdavidxu// This file defines the MallocAllocator and BumpPtrAllocator interfaces. 11213288Sdavidxu// 12213288Sdavidxu//===----------------------------------------------------------------------===// 13213288Sdavidxu 14213288Sdavidxu#ifndef LLVM_SUPPORT_ALLOCATOR_H 15213288Sdavidxu#define LLVM_SUPPORT_ALLOCATOR_H 16213288Sdavidxu 17213288Sdavidxu#include "llvm/Support/AlignOf.h" 18213288Sdavidxu#include "llvm/Support/DataTypes.h" 19213288Sdavidxu#include "llvm/Support/MathExtras.h" 20213288Sdavidxu#include <algorithm> 21213288Sdavidxu#include <cassert> 22213288Sdavidxu#include <cstddef> 23213288Sdavidxu#include <cstdlib> 24213288Sdavidxu 25213288Sdavidxunamespace llvm { 26213288Sdavidxutemplate <typename T> struct ReferenceAdder { typedef T& result; }; 27213288Sdavidxutemplate <typename T> struct ReferenceAdder<T&> { typedef T result; }; 28213288Sdavidxu 29213288Sdavidxuclass MallocAllocator { 30213288Sdavidxupublic: 31213288Sdavidxu MallocAllocator() {} 32213288Sdavidxu ~MallocAllocator() {} 33213288Sdavidxu 34213288Sdavidxu void Reset() {} 35213288Sdavidxu 36213288Sdavidxu void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); } 37213288Sdavidxu 38213288Sdavidxu template <typename T> 39213288Sdavidxu T *Allocate() { return static_cast<T*>(malloc(sizeof(T))); } 40213288Sdavidxu 41213288Sdavidxu template <typename T> 42213288Sdavidxu T *Allocate(size_t Num) { 43213288Sdavidxu return static_cast<T*>(malloc(sizeof(T)*Num)); 44213288Sdavidxu } 45213288Sdavidxu 46213288Sdavidxu void Deallocate(const void *Ptr) { free(const_cast<void*>(Ptr)); } 47213288Sdavidxu 48213288Sdavidxu void PrintStats() const {} 49213288Sdavidxu}; 50213288Sdavidxu 51213288Sdavidxu/// MemSlab - This structure lives at the beginning of every slab allocated by 52213288Sdavidxu/// the bump allocator. 53213288Sdavidxuclass MemSlab { 54213288Sdavidxupublic: 55213288Sdavidxu size_t Size; 56213288Sdavidxu MemSlab *NextPtr; 57213288Sdavidxu}; 58213288Sdavidxu 59213288Sdavidxu/// SlabAllocator - This class can be used to parameterize the underlying 60213288Sdavidxu/// allocation strategy for the bump allocator. In particular, this is used 61213288Sdavidxu/// by the JIT to allocate contiguous swathes of executable memory. The 62213288Sdavidxu/// interface uses MemSlab's instead of void *'s so that the allocator 63213288Sdavidxu/// doesn't have to remember the size of the pointer it allocated. 64213288Sdavidxuclass SlabAllocator { 65213288Sdavidxupublic: 66213288Sdavidxu virtual ~SlabAllocator(); 67213288Sdavidxu virtual MemSlab *Allocate(size_t Size) = 0; 68213288Sdavidxu virtual void Deallocate(MemSlab *Slab) = 0; 69213288Sdavidxu}; 70213288Sdavidxu 71213288Sdavidxu/// MallocSlabAllocator - The default slab allocator for the bump allocator 72213288Sdavidxu/// is an adapter class for MallocAllocator that just forwards the method 73213288Sdavidxu/// calls and translates the arguments. 74213288Sdavidxuclass MallocSlabAllocator : public SlabAllocator { 75213288Sdavidxu /// Allocator - The underlying allocator that we forward to. 76213288Sdavidxu /// 77213288Sdavidxu MallocAllocator Allocator; 78213288Sdavidxu 79213288Sdavidxupublic: 80213288Sdavidxu MallocSlabAllocator() : Allocator() { } 81213288Sdavidxu virtual ~MallocSlabAllocator(); 82213288Sdavidxu virtual MemSlab *Allocate(size_t Size) LLVM_OVERRIDE; 83213288Sdavidxu virtual void Deallocate(MemSlab *Slab) LLVM_OVERRIDE; 84213288Sdavidxu}; 85213288Sdavidxu 86213288Sdavidxu/// BumpPtrAllocator - This allocator is useful for containers that need 87213288Sdavidxu/// very simple memory allocation strategies. In particular, this just keeps 88213288Sdavidxu/// allocating memory, and never deletes it until the entire block is dead. This 89213288Sdavidxu/// makes allocation speedy, but must only be used when the trade-off is ok. 90213288Sdavidxuclass BumpPtrAllocator { 91213288Sdavidxu BumpPtrAllocator(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION; 92213288Sdavidxu void operator=(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION; 93213288Sdavidxu 94213288Sdavidxu /// SlabSize - Allocate data into slabs of this size unless we get an 95213288Sdavidxu /// allocation above SizeThreshold. 96213288Sdavidxu size_t SlabSize; 97213288Sdavidxu 98213288Sdavidxu /// SizeThreshold - For any allocation larger than this threshold, we should 99213288Sdavidxu /// allocate a separate slab. 100213288Sdavidxu size_t SizeThreshold; 101213288Sdavidxu 102213288Sdavidxu /// \brief the default allocator used if one is not provided 103213288Sdavidxu MallocSlabAllocator DefaultSlabAllocator; 104213288Sdavidxu 105213288Sdavidxu /// Allocator - The underlying allocator we use to get slabs of memory. This 106213288Sdavidxu /// defaults to MallocSlabAllocator, which wraps malloc, but it could be 107213288Sdavidxu /// changed to use a custom allocator. 108213288Sdavidxu SlabAllocator &Allocator; 109213288Sdavidxu 110213288Sdavidxu /// CurSlab - The slab that we are currently allocating into. 111213288Sdavidxu /// 112213288Sdavidxu MemSlab *CurSlab; 113213288Sdavidxu 114213288Sdavidxu /// CurPtr - The current pointer into the current slab. This points to the 115213288Sdavidxu /// next free byte in the slab. 116213288Sdavidxu char *CurPtr; 117213288Sdavidxu 118213288Sdavidxu /// End - The end of the current slab. 119213288Sdavidxu /// 120213288Sdavidxu char *End; 121213288Sdavidxu 122213288Sdavidxu /// BytesAllocated - This field tracks how many bytes we've allocated, so 123213288Sdavidxu /// that we can compute how much space was wasted. 124213288Sdavidxu size_t BytesAllocated; 125213288Sdavidxu 126213288Sdavidxu /// AlignPtr - Align Ptr to Alignment bytes, rounding up. Alignment should 127213288Sdavidxu /// be a power of two. This method rounds up, so AlignPtr(7, 4) == 8 and 128213288Sdavidxu /// AlignPtr(8, 4) == 8. 129213288Sdavidxu static char *AlignPtr(char *Ptr, size_t Alignment); 130213288Sdavidxu 131213288Sdavidxu /// StartNewSlab - Allocate a new slab and move the bump pointers over into 132213288Sdavidxu /// the new slab. Modifies CurPtr and End. 133213288Sdavidxu void StartNewSlab(); 134213288Sdavidxu 135213288Sdavidxu /// DeallocateSlabs - Deallocate all memory slabs after and including this 136213288Sdavidxu /// one. 137213288Sdavidxu void DeallocateSlabs(MemSlab *Slab); 138213288Sdavidxu 139213288Sdavidxu template<typename T> friend class SpecificBumpPtrAllocator; 140213288Sdavidxupublic: 141213288Sdavidxu BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096); 142213288Sdavidxu BumpPtrAllocator(size_t size, size_t threshold, SlabAllocator &allocator); 143213288Sdavidxu ~BumpPtrAllocator(); 144213288Sdavidxu 145213288Sdavidxu /// Reset - Deallocate all but the current slab and reset the current pointer 146213288Sdavidxu /// to the beginning of it, freeing all memory allocated so far. 147213288Sdavidxu void Reset(); 148213288Sdavidxu 149213288Sdavidxu /// Allocate - Allocate space at the specified alignment. 150213288Sdavidxu /// 151213288Sdavidxu void *Allocate(size_t Size, size_t Alignment); 152213288Sdavidxu 153213288Sdavidxu /// Allocate space, but do not construct, one object. 154213288Sdavidxu /// 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