LLVM API Documentation
00001 //===--- Allocator.cpp - Simple memory allocation abstraction -------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the BumpPtrAllocator interface. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/Support/Allocator.h" 00015 #include "llvm/Support/DataTypes.h" 00016 #include "llvm/Support/Recycler.h" 00017 #include "llvm/Support/raw_ostream.h" 00018 #include "llvm/System/Memory.h" 00019 #include <cstring> 00020 00021 namespace llvm { 00022 00023 BumpPtrAllocator::BumpPtrAllocator(size_t size, size_t threshold, 00024 SlabAllocator &allocator) 00025 : SlabSize(size), SizeThreshold(threshold), Allocator(allocator), 00026 CurSlab(0), BytesAllocated(0) { 00027 StartNewSlab(); 00028 } 00029 00030 BumpPtrAllocator::~BumpPtrAllocator() { 00031 DeallocateSlabs(CurSlab); 00032 } 00033 00034 /// AlignPtr - Align Ptr to Alignment bytes, rounding up. Alignment should 00035 /// be a power of two. This method rounds up, so AlignPtr(7, 4) == 8 and 00036 /// AlignPtr(8, 4) == 8. 00037 char *BumpPtrAllocator::AlignPtr(char *Ptr, size_t Alignment) { 00038 assert(Alignment && (Alignment & (Alignment - 1)) == 0 && 00039 "Alignment is not a power of two!"); 00040 00041 // Do the alignment. 00042 return (char*)(((uintptr_t)Ptr + Alignment - 1) & 00043 ~(uintptr_t)(Alignment - 1)); 00044 } 00045 00046 /// StartNewSlab - Allocate a new slab and move the bump pointers over into 00047 /// the new slab. Modifies CurPtr and End. 00048 void BumpPtrAllocator::StartNewSlab() { 00049 MemSlab *NewSlab = Allocator.Allocate(SlabSize); 00050 NewSlab->NextPtr = CurSlab; 00051 CurSlab = NewSlab; 00052 CurPtr = (char*)(CurSlab + 1); 00053 End = ((char*)CurSlab) + CurSlab->Size; 00054 } 00055 00056 /// DeallocateSlabs - Deallocate all memory slabs after and including this 00057 /// one. 00058 void BumpPtrAllocator::DeallocateSlabs(MemSlab *Slab) { 00059 while (Slab) { 00060 MemSlab *NextSlab = Slab->NextPtr; 00061 #ifndef NDEBUG 00062 // Poison the memory so stale pointers crash sooner. Note we must 00063 // preserve the Size and NextPtr fields at the beginning. 00064 sys::Memory::setRangeWritable(Slab + 1, Slab->Size - sizeof(MemSlab)); 00065 memset(Slab + 1, 0xCD, Slab->Size - sizeof(MemSlab)); 00066 #endif 00067 Allocator.Deallocate(Slab); 00068 Slab = NextSlab; 00069 } 00070 } 00071 00072 /// Reset - Deallocate all but the current slab and reset the current pointer 00073 /// to the beginning of it, freeing all memory allocated so far. 00074 void BumpPtrAllocator::Reset() { 00075 DeallocateSlabs(CurSlab->NextPtr); 00076 CurSlab->NextPtr = 0; 00077 CurPtr = (char*)(CurSlab + 1); 00078 End = ((char*)CurSlab) + CurSlab->Size; 00079 } 00080 00081 /// Allocate - Allocate space at the specified alignment. 00082 /// 00083 void *BumpPtrAllocator::Allocate(size_t Size, size_t Alignment) { 00084 // Keep track of how many bytes we've allocated. 00085 BytesAllocated += Size; 00086 00087 // 0-byte alignment means 1-byte alignment. 00088 if (Alignment == 0) Alignment = 1; 00089 00090 // Allocate the aligned space, going forwards from CurPtr. 00091 char *Ptr = AlignPtr(CurPtr, Alignment); 00092 00093 // Check if we can hold it. 00094 if (Ptr + Size <= End) { 00095 CurPtr = Ptr + Size; 00096 return Ptr; 00097 } 00098 00099 // If Size is really big, allocate a separate slab for it. 00100 size_t PaddedSize = Size + sizeof(MemSlab) + Alignment - 1; 00101 if (PaddedSize > SizeThreshold) { 00102 MemSlab *NewSlab = Allocator.Allocate(PaddedSize); 00103 00104 // Put the new slab after the current slab, since we are not allocating 00105 // into it. 00106 NewSlab->NextPtr = CurSlab->NextPtr; 00107 CurSlab->NextPtr = NewSlab; 00108 00109 Ptr = AlignPtr((char*)(NewSlab + 1), Alignment); 00110 assert((uintptr_t)Ptr + Size <= (uintptr_t)NewSlab + NewSlab->Size); 00111 return Ptr; 00112 } 00113 00114 // Otherwise, start a new slab and try again. 00115 StartNewSlab(); 00116 Ptr = AlignPtr(CurPtr, Alignment); 00117 CurPtr = Ptr + Size; 00118 assert(CurPtr <= End && "Unable to allocate memory!"); 00119 return Ptr; 00120 } 00121 00122 unsigned BumpPtrAllocator::GetNumSlabs() const { 00123 unsigned NumSlabs = 0; 00124 for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 00125 ++NumSlabs; 00126 } 00127 return NumSlabs; 00128 } 00129 00130 void BumpPtrAllocator::PrintStats() const { 00131 unsigned NumSlabs = 0; 00132 size_t TotalMemory = 0; 00133 for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 00134 TotalMemory += Slab->Size; 00135 ++NumSlabs; 00136 } 00137 00138 errs() << "\nNumber of memory regions: " << NumSlabs << '\n' 00139 << "Bytes used: " << BytesAllocated << '\n' 00140 << "Bytes allocated: " << TotalMemory << '\n' 00141 << "Bytes wasted: " << (TotalMemory - BytesAllocated) 00142 << " (includes alignment, etc)\n"; 00143 } 00144 00145 MallocSlabAllocator BumpPtrAllocator::DefaultSlabAllocator = 00146 MallocSlabAllocator(); 00147 00148 SlabAllocator::~SlabAllocator() { } 00149 00150 MallocSlabAllocator::~MallocSlabAllocator() { } 00151 00152 MemSlab *MallocSlabAllocator::Allocate(size_t Size) { 00153 MemSlab *Slab = (MemSlab*)Allocator.Allocate(Size, 0); 00154 Slab->Size = Size; 00155 Slab->NextPtr = 0; 00156 return Slab; 00157 } 00158 00159 void MallocSlabAllocator::Deallocate(MemSlab *Slab) { 00160 Allocator.Deallocate(Slab); 00161 } 00162 00163 void PrintRecyclerStats(size_t Size, 00164 size_t Align, 00165 size_t FreeListSize) { 00166 errs() << "Recycler element size: " << Size << '\n' 00167 << "Recycler element alignment: " << Align << '\n' 00168 << "Number of elements free for recycling: " << FreeListSize << '\n'; 00169 } 00170 00171 }