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 size_t BumpPtrAllocator::getTotalMemory() const { 140 size_t TotalMemory = 0; 141 for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 142 TotalMemory += Slab->Size; 143 } 144 return TotalMemory; 145 } 146 147 void BumpPtrAllocator::PrintStats() const { 148 unsigned NumSlabs = 0; 149 size_t TotalMemory = 0; 150 for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 151 TotalMemory += Slab->Size; 152 ++NumSlabs; 153 } 154 155 errs() << "\nNumber of memory regions: " << NumSlabs << '\n' 156 << "Bytes used: " << BytesAllocated << '\n' 157 << "Bytes allocated: " << TotalMemory << '\n' 158 << "Bytes wasted: " << (TotalMemory - BytesAllocated) 159 << " (includes alignment, etc)\n"; 160 } 161 162 MallocSlabAllocator BumpPtrAllocator::DefaultSlabAllocator = 163 MallocSlabAllocator(); 164 165 SlabAllocator::~SlabAllocator() { } 166 167 MallocSlabAllocator::~MallocSlabAllocator() { } 168 169 MemSlab *MallocSlabAllocator::Allocate(size_t Size) { 170 MemSlab *Slab = (MemSlab*)Allocator.Allocate(Size, 0); 171 Slab->Size = Size; 172 Slab->NextPtr = 0; 173 return Slab; 174 } 175 176 void MallocSlabAllocator::Deallocate(MemSlab *Slab) { 177 Allocator.Deallocate(Slab); 178 } 179 180 void PrintRecyclerStats(size_t Size, 181 size_t Align, 182 size_t FreeListSize) { 183 errs() << "Recycler element size: " << Size << '\n' 184 << "Recycler element alignment: " << Align << '\n' 185 << "Number of elements free for recycling: " << FreeListSize << '\n'; 186 } 187 188 } 189
