Allocator.cpp revision 208954
1//===--- Allocator.cpp - Simple memory allocation abstraction -------------===// 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 implements the BumpPtrAllocator interface. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/Support/Allocator.h" 15#include "llvm/System/DataTypes.h" 16#include "llvm/Support/Recycler.h" 17#include "llvm/Support/raw_ostream.h" 18#include "llvm/System/Memory.h" 19#include <cstring> 20 21namespace llvm { 22 23BumpPtrAllocator::BumpPtrAllocator(size_t size, size_t threshold, 24 SlabAllocator &allocator) 25 : SlabSize(size), SizeThreshold(threshold), Allocator(allocator), 26 CurSlab(0), BytesAllocated(0) { } 27 28BumpPtrAllocator::~BumpPtrAllocator() { 29 DeallocateSlabs(CurSlab); 30} 31 32/// AlignPtr - Align Ptr to Alignment bytes, rounding up. Alignment should 33/// be a power of two. This method rounds up, so AlignPtr(7, 4) == 8 and 34/// AlignPtr(8, 4) == 8. 35char *BumpPtrAllocator::AlignPtr(char *Ptr, size_t Alignment) { 36 assert(Alignment && (Alignment & (Alignment - 1)) == 0 && 37 "Alignment is not a power of two!"); 38 39 // Do the alignment. 40 return (char*)(((uintptr_t)Ptr + Alignment - 1) & 41 ~(uintptr_t)(Alignment - 1)); 42} 43 44/// StartNewSlab - Allocate a new slab and move the bump pointers over into 45/// the new slab. Modifies CurPtr and End. 46void BumpPtrAllocator::StartNewSlab() { 47 MemSlab *NewSlab = Allocator.Allocate(SlabSize); 48 NewSlab->NextPtr = CurSlab; 49 CurSlab = NewSlab; 50 CurPtr = (char*)(CurSlab + 1); 51 End = ((char*)CurSlab) + CurSlab->Size; 52} 53 54/// DeallocateSlabs - Deallocate all memory slabs after and including this 55/// one. 56void BumpPtrAllocator::DeallocateSlabs(MemSlab *Slab) { 57 while (Slab) { 58 MemSlab *NextSlab = Slab->NextPtr; 59#ifndef NDEBUG 60 // Poison the memory so stale pointers crash sooner. Note we must 61 // preserve the Size and NextPtr fields at the beginning. 62 sys::Memory::setRangeWritable(Slab + 1, Slab->Size - sizeof(MemSlab)); 63 memset(Slab + 1, 0xCD, Slab->Size - sizeof(MemSlab)); 64#endif 65 Allocator.Deallocate(Slab); 66 Slab = NextSlab; 67 } 68} 69 70/// Reset - Deallocate all but the current slab and reset the current pointer 71/// to the beginning of it, freeing all memory allocated so far. 72void BumpPtrAllocator::Reset() { 73 if (!CurSlab) 74 return; 75 DeallocateSlabs(CurSlab->NextPtr); 76 CurSlab->NextPtr = 0; 77 CurPtr = (char*)(CurSlab + 1); 78 End = ((char*)CurSlab) + CurSlab->Size; 79} 80 81/// Allocate - Allocate space at the specified alignment. 82/// 83void *BumpPtrAllocator::Allocate(size_t Size, size_t Alignment) { 84 if (!CurSlab) // Start a new slab if we haven't allocated one already. 85 StartNewSlab(); 86 87 // Keep track of how many bytes we've allocated. 88 BytesAllocated += Size; 89 90 // 0-byte alignment means 1-byte alignment. 91 if (Alignment == 0) Alignment = 1; 92 93 // Allocate the aligned space, going forwards from CurPtr. 94 char *Ptr = AlignPtr(CurPtr, Alignment); 95 96 // Check if we can hold it. 97 if (Ptr + Size <= End) { 98 CurPtr = Ptr + Size; 99 return Ptr; 100 } 101 102 // If Size is really big, allocate a separate slab for it. 103 size_t PaddedSize = Size + sizeof(MemSlab) + Alignment - 1; 104 if (PaddedSize > SizeThreshold) { 105 MemSlab *NewSlab = Allocator.Allocate(PaddedSize); 106 107 // Put the new slab after the current slab, since we are not allocating 108 // into it. 109 NewSlab->NextPtr = CurSlab->NextPtr; 110 CurSlab->NextPtr = NewSlab; 111 112 Ptr = AlignPtr((char*)(NewSlab + 1), Alignment); 113 assert((uintptr_t)Ptr + Size <= (uintptr_t)NewSlab + NewSlab->Size); 114 return Ptr; 115 } 116 117 // Otherwise, start a new slab and try again. 118 StartNewSlab(); 119 Ptr = AlignPtr(CurPtr, Alignment); 120 CurPtr = Ptr + Size; 121 assert(CurPtr <= End && "Unable to allocate memory!"); 122 return Ptr; 123} 124 125unsigned BumpPtrAllocator::GetNumSlabs() const { 126 unsigned NumSlabs = 0; 127 for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 128 ++NumSlabs; 129 } 130 return NumSlabs; 131} 132 133void BumpPtrAllocator::PrintStats() const { 134 unsigned NumSlabs = 0; 135 size_t TotalMemory = 0; 136 for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 137 TotalMemory += Slab->Size; 138 ++NumSlabs; 139 } 140 141 errs() << "\nNumber of memory regions: " << NumSlabs << '\n' 142 << "Bytes used: " << BytesAllocated << '\n' 143 << "Bytes allocated: " << TotalMemory << '\n' 144 << "Bytes wasted: " << (TotalMemory - BytesAllocated) 145 << " (includes alignment, etc)\n"; 146} 147 148MallocSlabAllocator BumpPtrAllocator::DefaultSlabAllocator = 149 MallocSlabAllocator(); 150 151SlabAllocator::~SlabAllocator() { } 152 153MallocSlabAllocator::~MallocSlabAllocator() { } 154 155MemSlab *MallocSlabAllocator::Allocate(size_t Size) { 156 MemSlab *Slab = (MemSlab*)Allocator.Allocate(Size, 0); 157 Slab->Size = Size; 158 Slab->NextPtr = 0; 159 return Slab; 160} 161 162void MallocSlabAllocator::Deallocate(MemSlab *Slab) { 163 Allocator.Deallocate(Slab); 164} 165 166void PrintRecyclerStats(size_t Size, 167 size_t Align, 168 size_t FreeListSize) { 169 errs() << "Recycler element size: " << Size << '\n' 170 << "Recycler element alignment: " << Align << '\n' 171 << "Number of elements free for recycling: " << FreeListSize << '\n'; 172} 173 174} 175