1193323Sed//===--- Allocator.cpp - Simple memory allocation abstraction -------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the BumpPtrAllocator interface. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#include "llvm/Support/Allocator.h" 15252723Sdim#include "llvm/Support/Compiler.h" 16218893Sdim#include "llvm/Support/DataTypes.h" 17252723Sdim#include "llvm/Support/Memory.h" 18193323Sed#include "llvm/Support/Recycler.h" 19198090Srdivacky#include "llvm/Support/raw_ostream.h" 20198090Srdivacky#include <cstring> 21193323Sed 22198090Srdivackynamespace llvm { 23193323Sed 24198090SrdivackyBumpPtrAllocator::BumpPtrAllocator(size_t size, size_t threshold, 25198090Srdivacky SlabAllocator &allocator) 26235633Sdim : SlabSize(size), SizeThreshold(std::min(size, threshold)), 27235633Sdim Allocator(allocator), CurSlab(0), BytesAllocated(0) { } 28193323Sed 29263509SdimBumpPtrAllocator::BumpPtrAllocator(size_t size, size_t threshold) 30263509Sdim : SlabSize(size), SizeThreshold(std::min(size, threshold)), 31263509Sdim Allocator(DefaultSlabAllocator), CurSlab(0), BytesAllocated(0) { } 32263509Sdim 33198090SrdivackyBumpPtrAllocator::~BumpPtrAllocator() { 34198090Srdivacky DeallocateSlabs(CurSlab); 35198090Srdivacky} 36193323Sed 37198090Srdivacky/// AlignPtr - Align Ptr to Alignment bytes, rounding up. Alignment should 38198090Srdivacky/// be a power of two. This method rounds up, so AlignPtr(7, 4) == 8 and 39198090Srdivacky/// AlignPtr(8, 4) == 8. 40198090Srdivackychar *BumpPtrAllocator::AlignPtr(char *Ptr, size_t Alignment) { 41198090Srdivacky assert(Alignment && (Alignment & (Alignment - 1)) == 0 && 42198090Srdivacky "Alignment is not a power of two!"); 43193323Sed 44198090Srdivacky // Do the alignment. 45198090Srdivacky return (char*)(((uintptr_t)Ptr + Alignment - 1) & 46198090Srdivacky ~(uintptr_t)(Alignment - 1)); 47193323Sed} 48193323Sed 49198090Srdivacky/// StartNewSlab - Allocate a new slab and move the bump pointers over into 50198090Srdivacky/// the new slab. Modifies CurPtr and End. 51198090Srdivackyvoid BumpPtrAllocator::StartNewSlab() { 52218893Sdim // If we allocated a big number of slabs already it's likely that we're going 53218893Sdim // to allocate more. Increase slab size to reduce mallocs and possibly memory 54218893Sdim // overhead. The factors are chosen conservatively to avoid overallocation. 55218893Sdim if (BytesAllocated >= SlabSize * 128) 56218893Sdim SlabSize *= 2; 57218893Sdim 58198090Srdivacky MemSlab *NewSlab = Allocator.Allocate(SlabSize); 59198090Srdivacky NewSlab->NextPtr = CurSlab; 60198090Srdivacky CurSlab = NewSlab; 61198090Srdivacky CurPtr = (char*)(CurSlab + 1); 62198090Srdivacky End = ((char*)CurSlab) + CurSlab->Size; 63193323Sed} 64193323Sed 65198090Srdivacky/// DeallocateSlabs - Deallocate all memory slabs after and including this 66198090Srdivacky/// one. 67198090Srdivackyvoid BumpPtrAllocator::DeallocateSlabs(MemSlab *Slab) { 68198090Srdivacky while (Slab) { 69198090Srdivacky MemSlab *NextSlab = Slab->NextPtr; 70198090Srdivacky#ifndef NDEBUG 71198090Srdivacky // Poison the memory so stale pointers crash sooner. Note we must 72198090Srdivacky // preserve the Size and NextPtr fields at the beginning. 73198090Srdivacky sys::Memory::setRangeWritable(Slab + 1, Slab->Size - sizeof(MemSlab)); 74198090Srdivacky memset(Slab + 1, 0xCD, Slab->Size - sizeof(MemSlab)); 75198090Srdivacky#endif 76198090Srdivacky Allocator.Deallocate(Slab); 77198090Srdivacky Slab = NextSlab; 78198090Srdivacky } 79193323Sed} 80193323Sed 81198090Srdivacky/// Reset - Deallocate all but the current slab and reset the current pointer 82198090Srdivacky/// to the beginning of it, freeing all memory allocated so far. 83193323Sedvoid BumpPtrAllocator::Reset() { 84207618Srdivacky if (!CurSlab) 85207618Srdivacky return; 86198090Srdivacky DeallocateSlabs(CurSlab->NextPtr); 87198090Srdivacky CurSlab->NextPtr = 0; 88198090Srdivacky CurPtr = (char*)(CurSlab + 1); 89198090Srdivacky End = ((char*)CurSlab) + CurSlab->Size; 90252723Sdim BytesAllocated = 0; 91193323Sed} 92193323Sed 93198090Srdivacky/// Allocate - Allocate space at the specified alignment. 94198090Srdivacky/// 95198090Srdivackyvoid *BumpPtrAllocator::Allocate(size_t Size, size_t Alignment) { 96207618Srdivacky if (!CurSlab) // Start a new slab if we haven't allocated one already. 97207618Srdivacky StartNewSlab(); 98207618Srdivacky 99198090Srdivacky // Keep track of how many bytes we've allocated. 100198090Srdivacky BytesAllocated += Size; 101198090Srdivacky 102198090Srdivacky // 0-byte alignment means 1-byte alignment. 103198090Srdivacky if (Alignment == 0) Alignment = 1; 104198090Srdivacky 105198090Srdivacky // Allocate the aligned space, going forwards from CurPtr. 106198090Srdivacky char *Ptr = AlignPtr(CurPtr, Alignment); 107198090Srdivacky 108198090Srdivacky // Check if we can hold it. 109198090Srdivacky if (Ptr + Size <= End) { 110198090Srdivacky CurPtr = Ptr + Size; 111252723Sdim // Update the allocation point of this memory block in MemorySanitizer. 112252723Sdim // Without this, MemorySanitizer messages for values originated from here 113252723Sdim // will point to the allocation of the entire slab. 114252723Sdim __msan_allocated_memory(Ptr, Size); 115198090Srdivacky return Ptr; 116198090Srdivacky } 117198090Srdivacky 118198090Srdivacky // If Size is really big, allocate a separate slab for it. 119198090Srdivacky size_t PaddedSize = Size + sizeof(MemSlab) + Alignment - 1; 120198090Srdivacky if (PaddedSize > SizeThreshold) { 121198090Srdivacky MemSlab *NewSlab = Allocator.Allocate(PaddedSize); 122198090Srdivacky 123198090Srdivacky // Put the new slab after the current slab, since we are not allocating 124198090Srdivacky // into it. 125198090Srdivacky NewSlab->NextPtr = CurSlab->NextPtr; 126198090Srdivacky CurSlab->NextPtr = NewSlab; 127198090Srdivacky 128198090Srdivacky Ptr = AlignPtr((char*)(NewSlab + 1), Alignment); 129198090Srdivacky assert((uintptr_t)Ptr + Size <= (uintptr_t)NewSlab + NewSlab->Size); 130252723Sdim __msan_allocated_memory(Ptr, Size); 131198090Srdivacky return Ptr; 132198090Srdivacky } 133198090Srdivacky 134198090Srdivacky // Otherwise, start a new slab and try again. 135198090Srdivacky StartNewSlab(); 136198090Srdivacky Ptr = AlignPtr(CurPtr, Alignment); 137198090Srdivacky CurPtr = Ptr + Size; 138198090Srdivacky assert(CurPtr <= End && "Unable to allocate memory!"); 139252723Sdim __msan_allocated_memory(Ptr, Size); 140193323Sed return Ptr; 141193323Sed} 142193323Sed 143198090Srdivackyunsigned BumpPtrAllocator::GetNumSlabs() const { 144198090Srdivacky unsigned NumSlabs = 0; 145198090Srdivacky for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 146198090Srdivacky ++NumSlabs; 147198090Srdivacky } 148198090Srdivacky return NumSlabs; 149198090Srdivacky} 150198090Srdivacky 151221345Sdimsize_t BumpPtrAllocator::getTotalMemory() const { 152221345Sdim size_t TotalMemory = 0; 153221345Sdim for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 154221345Sdim TotalMemory += Slab->Size; 155221345Sdim } 156221345Sdim return TotalMemory; 157221345Sdim} 158221345Sdim 159193323Sedvoid BumpPtrAllocator::PrintStats() const { 160198090Srdivacky unsigned NumSlabs = 0; 161198090Srdivacky size_t TotalMemory = 0; 162198090Srdivacky for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 163198090Srdivacky TotalMemory += Slab->Size; 164198090Srdivacky ++NumSlabs; 165198090Srdivacky } 166193323Sed 167198090Srdivacky errs() << "\nNumber of memory regions: " << NumSlabs << '\n' 168198090Srdivacky << "Bytes used: " << BytesAllocated << '\n' 169198090Srdivacky << "Bytes allocated: " << TotalMemory << '\n' 170198090Srdivacky << "Bytes wasted: " << (TotalMemory - BytesAllocated) 171198090Srdivacky << " (includes alignment, etc)\n"; 172193323Sed} 173193323Sed 174198090SrdivackySlabAllocator::~SlabAllocator() { } 175198090Srdivacky 176198090SrdivackyMallocSlabAllocator::~MallocSlabAllocator() { } 177198090Srdivacky 178198090SrdivackyMemSlab *MallocSlabAllocator::Allocate(size_t Size) { 179198090Srdivacky MemSlab *Slab = (MemSlab*)Allocator.Allocate(Size, 0); 180198090Srdivacky Slab->Size = Size; 181198090Srdivacky Slab->NextPtr = 0; 182198090Srdivacky return Slab; 183193323Sed} 184198090Srdivacky 185198090Srdivackyvoid MallocSlabAllocator::Deallocate(MemSlab *Slab) { 186198090Srdivacky Allocator.Deallocate(Slab); 187198090Srdivacky} 188198090Srdivacky 189198090Srdivackyvoid PrintRecyclerStats(size_t Size, 190198090Srdivacky size_t Align, 191198090Srdivacky size_t FreeListSize) { 192198090Srdivacky errs() << "Recycler element size: " << Size << '\n' 193198090Srdivacky << "Recycler element alignment: " << Align << '\n' 194198090Srdivacky << "Number of elements free for recycling: " << FreeListSize << '\n'; 195198090Srdivacky} 196198090Srdivacky 197198090Srdivacky} 198