Allocator.h revision 01cb1b665da03e2b74c0724f71751e912ec8c2be
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 136public: 137 typedef void (*DTorFunction)(void*); 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 /// Reset - like Reset(), but call DTorFunction for each allocated 147 /// object. This assumes that all objects allocated with this allocator 148 /// had the same size and alignment specified here. 149 void Reset(size_t Size, size_t Alignment, DTorFunction DTor); 150 151 /// Allocate - Allocate space at the specified alignment. 152 /// 153 void *Allocate(size_t Size, size_t Alignment); 154 155 /// Allocate space, but do not construct, one object. 156 /// 157 template <typename T> 158 T *Allocate() { 159 return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment)); 160 } 161 162 /// Allocate space for an array of objects. This does not construct the 163 /// objects though. 164 template <typename T> 165 T *Allocate(size_t Num) { 166 return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment)); 167 } 168 169 /// Allocate space for a specific count of elements and with a specified 170 /// alignment. 171 template <typename T> 172 T *Allocate(size_t Num, size_t Alignment) { 173 // Round EltSize up to the specified alignment. 174 size_t EltSize = (sizeof(T)+Alignment-1)&(-Alignment); 175 return static_cast<T*>(Allocate(Num * EltSize, Alignment)); 176 } 177 178 void Deallocate(const void * /*Ptr*/) {} 179 180 unsigned GetNumSlabs() const; 181 182 void PrintStats() const; 183}; 184 185} // end namespace llvm 186 187inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) { 188 struct S { 189 char c; 190#ifdef __GNUC__ 191 char x __attribute__((aligned)); 192#else 193 union { 194 double D; 195 long double LD; 196 long long L; 197 void *P; 198 } x; 199#endif 200 }; 201 return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size), 202 offsetof(S, x))); 203} 204 205#endif // LLVM_SUPPORT_ALLOCATOR_H 206