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