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