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