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