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