1193323Sed//===--- Allocator.h - Simple memory allocation abstraction -----*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the MallocAllocator and BumpPtrAllocator interfaces. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#ifndef LLVM_SUPPORT_ALLOCATOR_H 15193323Sed#define LLVM_SUPPORT_ALLOCATOR_H 16193323Sed 17193323Sed#include "llvm/Support/AlignOf.h" 18249423Sdim#include "llvm/Support/DataTypes.h" 19205407Srdivacky#include "llvm/Support/MathExtras.h" 20205407Srdivacky#include <algorithm> 21198090Srdivacky#include <cassert> 22249423Sdim#include <cstddef> 23193323Sed#include <cstdlib> 24193323Sed 25193323Sednamespace llvm { 26218893Sdimtemplate <typename T> struct ReferenceAdder { typedef T& result; }; 27218893Sdimtemplate <typename T> struct ReferenceAdder<T&> { typedef T result; }; 28193323Sed 29193323Sedclass MallocAllocator { 30193323Sedpublic: 31193323Sed MallocAllocator() {} 32193323Sed ~MallocAllocator() {} 33193323Sed 34193323Sed void Reset() {} 35193323Sed 36193323Sed void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); } 37193323Sed 38193323Sed template <typename T> 39193323Sed T *Allocate() { return static_cast<T*>(malloc(sizeof(T))); } 40193323Sed 41193323Sed template <typename T> 42193323Sed T *Allocate(size_t Num) { 43193323Sed return static_cast<T*>(malloc(sizeof(T)*Num)); 44193323Sed } 45193323Sed 46193323Sed void Deallocate(const void *Ptr) { free(const_cast<void*>(Ptr)); } 47193323Sed 48193323Sed void PrintStats() const {} 49193323Sed}; 50193323Sed 51198090Srdivacky/// MemSlab - This structure lives at the beginning of every slab allocated by 52198090Srdivacky/// the bump allocator. 53198090Srdivackyclass MemSlab { 54198090Srdivackypublic: 55198090Srdivacky size_t Size; 56198090Srdivacky MemSlab *NextPtr; 57198090Srdivacky}; 58198090Srdivacky 59198090Srdivacky/// SlabAllocator - This class can be used to parameterize the underlying 60198090Srdivacky/// allocation strategy for the bump allocator. In particular, this is used 61198090Srdivacky/// by the JIT to allocate contiguous swathes of executable memory. The 62198090Srdivacky/// interface uses MemSlab's instead of void *'s so that the allocator 63198090Srdivacky/// doesn't have to remember the size of the pointer it allocated. 64198090Srdivackyclass SlabAllocator { 65198090Srdivackypublic: 66198090Srdivacky virtual ~SlabAllocator(); 67198090Srdivacky virtual MemSlab *Allocate(size_t Size) = 0; 68198090Srdivacky virtual void Deallocate(MemSlab *Slab) = 0; 69198090Srdivacky}; 70198090Srdivacky 71198090Srdivacky/// MallocSlabAllocator - The default slab allocator for the bump allocator 72198090Srdivacky/// is an adapter class for MallocAllocator that just forwards the method 73198090Srdivacky/// calls and translates the arguments. 74198090Srdivackyclass MallocSlabAllocator : public SlabAllocator { 75198090Srdivacky /// Allocator - The underlying allocator that we forward to. 76198090Srdivacky /// 77198090Srdivacky MallocAllocator Allocator; 78198090Srdivacky 79198090Srdivackypublic: 80198090Srdivacky MallocSlabAllocator() : Allocator() { } 81198090Srdivacky virtual ~MallocSlabAllocator(); 82243830Sdim virtual MemSlab *Allocate(size_t Size) LLVM_OVERRIDE; 83243830Sdim virtual void Deallocate(MemSlab *Slab) LLVM_OVERRIDE; 84198090Srdivacky}; 85198090Srdivacky 86198090Srdivacky/// BumpPtrAllocator - This allocator is useful for containers that need 87198090Srdivacky/// very simple memory allocation strategies. In particular, this just keeps 88193323Sed/// allocating memory, and never deletes it until the entire block is dead. This 89193323Sed/// makes allocation speedy, but must only be used when the trade-off is ok. 90193323Sedclass BumpPtrAllocator { 91243830Sdim BumpPtrAllocator(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION; 92243830Sdim void operator=(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION; 93193323Sed 94198090Srdivacky /// SlabSize - Allocate data into slabs of this size unless we get an 95198090Srdivacky /// allocation above SizeThreshold. 96198090Srdivacky size_t SlabSize; 97198090Srdivacky 98198090Srdivacky /// SizeThreshold - For any allocation larger than this threshold, we should 99198090Srdivacky /// allocate a separate slab. 100198090Srdivacky size_t SizeThreshold; 101198090Srdivacky 102263508Sdim /// \brief the default allocator used if one is not provided 103263508Sdim MallocSlabAllocator DefaultSlabAllocator; 104263508Sdim 105198090Srdivacky /// Allocator - The underlying allocator we use to get slabs of memory. This 106198090Srdivacky /// defaults to MallocSlabAllocator, which wraps malloc, but it could be 107198090Srdivacky /// changed to use a custom allocator. 108198090Srdivacky SlabAllocator &Allocator; 109198090Srdivacky 110198090Srdivacky /// CurSlab - The slab that we are currently allocating into. 111198090Srdivacky /// 112198090Srdivacky MemSlab *CurSlab; 113198090Srdivacky 114198090Srdivacky /// CurPtr - The current pointer into the current slab. This points to the 115198090Srdivacky /// next free byte in the slab. 116198090Srdivacky char *CurPtr; 117198090Srdivacky 118198090Srdivacky /// End - The end of the current slab. 119198090Srdivacky /// 120198090Srdivacky char *End; 121198090Srdivacky 122198090Srdivacky /// BytesAllocated - This field tracks how many bytes we've allocated, so 123198090Srdivacky /// that we can compute how much space was wasted. 124198090Srdivacky size_t BytesAllocated; 125198090Srdivacky 126198090Srdivacky /// AlignPtr - Align Ptr to Alignment bytes, rounding up. Alignment should 127198090Srdivacky /// be a power of two. This method rounds up, so AlignPtr(7, 4) == 8 and 128198090Srdivacky /// AlignPtr(8, 4) == 8. 129198090Srdivacky static char *AlignPtr(char *Ptr, size_t Alignment); 130198090Srdivacky 131198090Srdivacky /// StartNewSlab - Allocate a new slab and move the bump pointers over into 132198090Srdivacky /// the new slab. Modifies CurPtr and End. 133198090Srdivacky void StartNewSlab(); 134198090Srdivacky 135198090Srdivacky /// DeallocateSlabs - Deallocate all memory slabs after and including this 136198090Srdivacky /// one. 137198090Srdivacky void DeallocateSlabs(MemSlab *Slab); 138198090Srdivacky 139206083Srdivacky template<typename T> friend class SpecificBumpPtrAllocator; 140193323Sedpublic: 141263508Sdim BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096); 142263508Sdim BumpPtrAllocator(size_t size, size_t threshold, SlabAllocator &allocator); 143193323Sed ~BumpPtrAllocator(); 144193323Sed 145198090Srdivacky /// Reset - Deallocate all but the current slab and reset the current pointer 146198090Srdivacky /// to the beginning of it, freeing all memory allocated so far. 147193323Sed void Reset(); 148193323Sed 149198090Srdivacky /// Allocate - Allocate space at the specified alignment. 150198090Srdivacky /// 151193323Sed void *Allocate(size_t Size, size_t Alignment); 152193323Sed 153193323Sed /// Allocate space, but do not construct, one object. 154193323Sed /// 155193323Sed template <typename T> 156193323Sed T *Allocate() { 157193323Sed return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment)); 158193323Sed } 159193323Sed 160193323Sed /// Allocate space for an array of objects. This does not construct the 161193323Sed /// objects though. 162193323Sed template <typename T> 163193323Sed T *Allocate(size_t Num) { 164193323Sed return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment)); 165193323Sed } 166193323Sed 167193323Sed /// Allocate space for a specific count of elements and with a specified 168193323Sed /// alignment. 169193323Sed template <typename T> 170193323Sed T *Allocate(size_t Num, size_t Alignment) { 171193323Sed // Round EltSize up to the specified alignment. 172193323Sed size_t EltSize = (sizeof(T)+Alignment-1)&(-Alignment); 173193323Sed return static_cast<T*>(Allocate(Num * EltSize, Alignment)); 174193323Sed } 175193323Sed 176193323Sed void Deallocate(const void * /*Ptr*/) {} 177193323Sed 178198090Srdivacky unsigned GetNumSlabs() const; 179198090Srdivacky 180193323Sed void PrintStats() const; 181221345Sdim 182221345Sdim /// Compute the total physical memory allocated by this allocator. 183221345Sdim size_t getTotalMemory() const; 184193323Sed}; 185193323Sed 186206083Srdivacky/// SpecificBumpPtrAllocator - Same as BumpPtrAllocator but allows only 187206083Srdivacky/// elements of one type to be allocated. This allows calling the destructor 188206083Srdivacky/// in DestroyAll() and when the allocator is destroyed. 189206083Srdivackytemplate <typename T> 190206083Srdivackyclass SpecificBumpPtrAllocator { 191206083Srdivacky BumpPtrAllocator Allocator; 192206083Srdivackypublic: 193263508Sdim SpecificBumpPtrAllocator(size_t size = 4096, size_t threshold = 4096) 194263508Sdim : Allocator(size, threshold) {} 195263508Sdim SpecificBumpPtrAllocator(size_t size, size_t threshold, 196263508Sdim SlabAllocator &allocator) 197206083Srdivacky : Allocator(size, threshold, allocator) {} 198206083Srdivacky 199206083Srdivacky ~SpecificBumpPtrAllocator() { 200206083Srdivacky DestroyAll(); 201206083Srdivacky } 202206083Srdivacky 203206083Srdivacky /// Call the destructor of each allocated object and deallocate all but the 204206083Srdivacky /// current slab and reset the current pointer to the beginning of it, freeing 205206083Srdivacky /// all memory allocated so far. 206206083Srdivacky void DestroyAll() { 207206083Srdivacky MemSlab *Slab = Allocator.CurSlab; 208206083Srdivacky while (Slab) { 209206083Srdivacky char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr : 210206083Srdivacky (char *)Slab + Slab->Size; 211206124Srdivacky for (char *Ptr = (char*)(Slab+1); Ptr < End; Ptr += sizeof(T)) { 212218893Sdim Ptr = Allocator.AlignPtr(Ptr, alignOf<T>()); 213206274Srdivacky if (Ptr + sizeof(T) <= End) 214206083Srdivacky reinterpret_cast<T*>(Ptr)->~T(); 215206083Srdivacky } 216206083Srdivacky Slab = Slab->NextPtr; 217206083Srdivacky } 218206083Srdivacky Allocator.Reset(); 219206083Srdivacky } 220206083Srdivacky 221206083Srdivacky /// Allocate space for a specific count of elements. 222206083Srdivacky T *Allocate(size_t num = 1) { 223206083Srdivacky return Allocator.Allocate<T>(num); 224206083Srdivacky } 225206083Srdivacky}; 226206083Srdivacky 227193323Sed} // end namespace llvm 228193323Sed 229205407Srdivackyinline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) { 230205407Srdivacky struct S { 231205407Srdivacky char c; 232205407Srdivacky union { 233205407Srdivacky double D; 234205407Srdivacky long double LD; 235205407Srdivacky long long L; 236205407Srdivacky void *P; 237205407Srdivacky } x; 238205407Srdivacky }; 239205407Srdivacky return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size), 240205407Srdivacky offsetof(S, x))); 241205407Srdivacky} 242205407Srdivacky 243207618Srdivackyinline void operator delete(void *, llvm::BumpPtrAllocator &) {} 244207618Srdivacky 245198090Srdivacky#endif // LLVM_SUPPORT_ALLOCATOR_H 246