Allocator.cpp revision 207618
11638Srgrimes//===--- Allocator.cpp - Simple memory allocation abstraction -------------===// 21638Srgrimes// 31638Srgrimes// The LLVM Compiler Infrastructure 41638Srgrimes// 51638Srgrimes// This file is distributed under the University of Illinois Open Source 61638Srgrimes// License. See LICENSE.TXT for details. 71638Srgrimes// 81638Srgrimes//===----------------------------------------------------------------------===// 91638Srgrimes// 101638Srgrimes// This file implements the BumpPtrAllocator interface. 111638Srgrimes// 121638Srgrimes//===----------------------------------------------------------------------===// 131638Srgrimes 141638Srgrimes#include "llvm/Support/Allocator.h" 151638Srgrimes#include "llvm/System/DataTypes.h" 161638Srgrimes#include "llvm/Support/Recycler.h" 171638Srgrimes#include "llvm/Support/raw_ostream.h" 181638Srgrimes#include "llvm/System/Memory.h" 191638Srgrimes#include <cstring> 201638Srgrimes 211638Srgrimesnamespace llvm { 221638Srgrimes 231638SrgrimesBumpPtrAllocator::BumpPtrAllocator(size_t size, size_t threshold, 241638Srgrimes SlabAllocator &allocator) 251638Srgrimes : SlabSize(size), SizeThreshold(threshold), Allocator(allocator), 261638Srgrimes CurSlab(0), BytesAllocated(0) { } 271638Srgrimes 281638SrgrimesBumpPtrAllocator::~BumpPtrAllocator() { 291638Srgrimes DeallocateSlabs(CurSlab); 301638Srgrimes} 311638Srgrimes 321638Srgrimes/// AlignPtr - Align Ptr to Alignment bytes, rounding up. Alignment should 33215334Sdougb/// be a power of two. This method rounds up, so AlignPtr(7, 4) == 8 and 341638Srgrimes/// AlignPtr(8, 4) == 8. 351638Srgrimeschar *BumpPtrAllocator::AlignPtr(char *Ptr, size_t Alignment) { 361638Srgrimes assert(Alignment && (Alignment & (Alignment - 1)) == 0 && 371638Srgrimes "Alignment is not a power of two!"); 381638Srgrimes 391638Srgrimes // Do the alignment. 401638Srgrimes return (char*)(((uintptr_t)Ptr + Alignment - 1) & 411638Srgrimes ~(uintptr_t)(Alignment - 1)); 421638Srgrimes} 431638Srgrimes 441638Srgrimes/// StartNewSlab - Allocate a new slab and move the bump pointers over into 451638Srgrimes/// the new slab. Modifies CurPtr and End. 461638Srgrimesvoid BumpPtrAllocator::StartNewSlab() { 471638Srgrimes MemSlab *NewSlab = Allocator.Allocate(SlabSize); 481638Srgrimes NewSlab->NextPtr = CurSlab; 491638Srgrimes CurSlab = NewSlab; 501638Srgrimes CurPtr = (char*)(CurSlab + 1); 511638Srgrimes End = ((char*)CurSlab) + CurSlab->Size; 521638Srgrimes} 531638Srgrimes 541638Srgrimes/// DeallocateSlabs - Deallocate all memory slabs after and including this 551638Srgrimes/// one. 561638Srgrimesvoid BumpPtrAllocator::DeallocateSlabs(MemSlab *Slab) { 571638Srgrimes while (Slab) { 581638Srgrimes MemSlab *NextSlab = Slab->NextPtr; 591638Srgrimes#ifndef NDEBUG 601638Srgrimes // Poison the memory so stale pointers crash sooner. Note we must 611638Srgrimes // preserve the Size and NextPtr fields at the beginning. 621638Srgrimes sys::Memory::setRangeWritable(Slab + 1, Slab->Size - sizeof(MemSlab)); 631638Srgrimes memset(Slab + 1, 0xCD, Slab->Size - sizeof(MemSlab)); 641638Srgrimes#endif 651638Srgrimes Allocator.Deallocate(Slab); 661638Srgrimes Slab = NextSlab; 671638Srgrimes } 681638Srgrimes} 691638Srgrimes 701638Srgrimes/// Reset - Deallocate all but the current slab and reset the current pointer 711638Srgrimes/// to the beginning of it, freeing all memory allocated so far. 721638Srgrimesvoid BumpPtrAllocator::Reset() { 731638Srgrimes if (!CurSlab) 741638Srgrimes return; 751638Srgrimes DeallocateSlabs(CurSlab->NextPtr); 761638Srgrimes CurSlab->NextPtr = 0; 771638Srgrimes CurPtr = (char*)(CurSlab + 1); 781638Srgrimes End = ((char*)CurSlab) + CurSlab->Size; 791638Srgrimes} 801638Srgrimes 811638Srgrimes/// Allocate - Allocate space at the specified alignment. 821638Srgrimes/// 831638Srgrimesvoid *BumpPtrAllocator::Allocate(size_t Size, size_t Alignment) { 841638Srgrimes if (!CurSlab) // Start a new slab if we haven't allocated one already. 851638Srgrimes StartNewSlab(); 861638Srgrimes 871638Srgrimes // Keep track of how many bytes we've allocated. 881638Srgrimes BytesAllocated += Size; 891638Srgrimes 901638Srgrimes // 0-byte alignment means 1-byte alignment. 911638Srgrimes if (Alignment == 0) Alignment = 1; 921638Srgrimes 931638Srgrimes // Allocate the aligned space, going forwards from CurPtr. 941638Srgrimes char *Ptr = AlignPtr(CurPtr, Alignment); 951638Srgrimes 961638Srgrimes // Check if we can hold it. 971638Srgrimes if (Ptr + Size <= End) { 981638Srgrimes CurPtr = Ptr + Size; 991638Srgrimes return Ptr; 1001638Srgrimes } 1011638Srgrimes 1021638Srgrimes // If Size is really big, allocate a separate slab for it. 1031638Srgrimes size_t PaddedSize = Size + sizeof(MemSlab) + Alignment - 1; 1041638Srgrimes if (PaddedSize > SizeThreshold) { 1051638Srgrimes MemSlab *NewSlab = Allocator.Allocate(PaddedSize); 1061638Srgrimes 1071638Srgrimes // Put the new slab after the current slab, since we are not allocating 1081638Srgrimes // into it. 1091638Srgrimes NewSlab->NextPtr = CurSlab->NextPtr; 1101638Srgrimes CurSlab->NextPtr = NewSlab; 1111638Srgrimes 1121638Srgrimes Ptr = AlignPtr((char*)(NewSlab + 1), Alignment); 1131638Srgrimes assert((uintptr_t)Ptr + Size <= (uintptr_t)NewSlab + NewSlab->Size); 1141638Srgrimes return Ptr; 1151638Srgrimes } 1161638Srgrimes 1171638Srgrimes // Otherwise, start a new slab and try again. 1181638Srgrimes StartNewSlab(); 1191638Srgrimes Ptr = AlignPtr(CurPtr, Alignment); 1201638Srgrimes CurPtr = Ptr + Size; 1211638Srgrimes assert(CurPtr <= End && "Unable to allocate memory!"); 1221638Srgrimes return Ptr; 1231638Srgrimes} 1241638Srgrimes 1251638Srgrimesunsigned BumpPtrAllocator::GetNumSlabs() const { 1261638Srgrimes unsigned NumSlabs = 0; 1271638Srgrimes for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 1281638Srgrimes ++NumSlabs; 1291638Srgrimes } 1301638Srgrimes return NumSlabs; 1311638Srgrimes} 1321638Srgrimes 1331638Srgrimesvoid BumpPtrAllocator::PrintStats() const { 1341638Srgrimes unsigned NumSlabs = 0; 1351638Srgrimes size_t TotalMemory = 0; 1361638Srgrimes for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 1371638Srgrimes TotalMemory += Slab->Size; 1381638Srgrimes ++NumSlabs; 1391638Srgrimes } 1401638Srgrimes 1411638Srgrimes errs() << "\nNumber of memory regions: " << NumSlabs << '\n' 1421638Srgrimes << "Bytes used: " << BytesAllocated << '\n' 1431638Srgrimes << "Bytes allocated: " << TotalMemory << '\n' 1441638Srgrimes << "Bytes wasted: " << (TotalMemory - BytesAllocated) 1451638Srgrimes << " (includes alignment, etc)\n"; 1461638Srgrimes} 1471638Srgrimes 1481638SrgrimesMallocSlabAllocator BumpPtrAllocator::DefaultSlabAllocator = 1491638Srgrimes MallocSlabAllocator(); 1501638Srgrimes 1511638SrgrimesSlabAllocator::~SlabAllocator() { } 1521638Srgrimes 1531638SrgrimesMallocSlabAllocator::~MallocSlabAllocator() { } 1541638Srgrimes 155215334SdougbMemSlab *MallocSlabAllocator::Allocate(size_t Size) { 1561638Srgrimes MemSlab *Slab = (MemSlab*)Allocator.Allocate(Size, 0); 1571638Srgrimes Slab->Size = Size; 1581638Srgrimes Slab->NextPtr = 0; 159215334Sdougb return Slab; 1601638Srgrimes} 1611638Srgrimes 1621638Srgrimesvoid MallocSlabAllocator::Deallocate(MemSlab *Slab) { 1631638Srgrimes Allocator.Deallocate(Slab); 1641638Srgrimes} 1651638Srgrimes 1661638Srgrimesvoid PrintRecyclerStats(size_t Size, 1671638Srgrimes size_t Align, 1681638Srgrimes size_t FreeListSize) { 1691638Srgrimes errs() << "Recycler element size: " << Size << '\n' 1701638Srgrimes << "Recycler element alignment: " << Align << '\n' 1711638Srgrimes << "Number of elements free for recycling: " << FreeListSize << '\n'; 1721638Srgrimes} 1731638Srgrimes 1741638Srgrimes} 1751638Srgrimes