LLVM API Documentation

Allocator.cpp

Go to the documentation of this file.
00001 //===--- Allocator.cpp - Simple memory allocation abstraction -------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the BumpPtrAllocator interface.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Support/Allocator.h"
00015 #include "llvm/Support/DataTypes.h"
00016 #include "llvm/Support/Recycler.h"
00017 #include "llvm/Support/raw_ostream.h"
00018 #include "llvm/System/Memory.h"
00019 #include <cstring>
00020 
00021 namespace llvm {
00022 
00023 BumpPtrAllocator::BumpPtrAllocator(size_t size, size_t threshold,
00024                                    SlabAllocator &allocator)
00025     : SlabSize(size), SizeThreshold(threshold), Allocator(allocator),
00026       CurSlab(0), BytesAllocated(0) {
00027   StartNewSlab();
00028 }
00029 
00030 BumpPtrAllocator::~BumpPtrAllocator() {
00031   DeallocateSlabs(CurSlab);
00032 }
00033 
00034 /// AlignPtr - Align Ptr to Alignment bytes, rounding up.  Alignment should
00035 /// be a power of two.  This method rounds up, so AlignPtr(7, 4) == 8 and
00036 /// AlignPtr(8, 4) == 8.
00037 char *BumpPtrAllocator::AlignPtr(char *Ptr, size_t Alignment) {
00038   assert(Alignment && (Alignment & (Alignment - 1)) == 0 &&
00039          "Alignment is not a power of two!");
00040 
00041   // Do the alignment.
00042   return (char*)(((uintptr_t)Ptr + Alignment - 1) &
00043                  ~(uintptr_t)(Alignment - 1));
00044 }
00045 
00046 /// StartNewSlab - Allocate a new slab and move the bump pointers over into
00047 /// the new slab.  Modifies CurPtr and End.
00048 void BumpPtrAllocator::StartNewSlab() {
00049   MemSlab *NewSlab = Allocator.Allocate(SlabSize);
00050   NewSlab->NextPtr = CurSlab;
00051   CurSlab = NewSlab;
00052   CurPtr = (char*)(CurSlab + 1);
00053   End = ((char*)CurSlab) + CurSlab->Size;
00054 }
00055 
00056 /// DeallocateSlabs - Deallocate all memory slabs after and including this
00057 /// one.
00058 void BumpPtrAllocator::DeallocateSlabs(MemSlab *Slab) {
00059   while (Slab) {
00060     MemSlab *NextSlab = Slab->NextPtr;
00061 #ifndef NDEBUG
00062     // Poison the memory so stale pointers crash sooner.  Note we must
00063     // preserve the Size and NextPtr fields at the beginning.
00064     sys::Memory::setRangeWritable(Slab + 1, Slab->Size - sizeof(MemSlab));
00065     memset(Slab + 1, 0xCD, Slab->Size - sizeof(MemSlab));
00066 #endif
00067     Allocator.Deallocate(Slab);
00068     Slab = NextSlab;
00069   }
00070 }
00071 
00072 /// Reset - Deallocate all but the current slab and reset the current pointer
00073 /// to the beginning of it, freeing all memory allocated so far.
00074 void BumpPtrAllocator::Reset() {
00075   DeallocateSlabs(CurSlab->NextPtr);
00076   CurSlab->NextPtr = 0;
00077   CurPtr = (char*)(CurSlab + 1);
00078   End = ((char*)CurSlab) + CurSlab->Size;
00079 }
00080 
00081 /// Allocate - Allocate space at the specified alignment.
00082 ///
00083 void *BumpPtrAllocator::Allocate(size_t Size, size_t Alignment) {
00084   // Keep track of how many bytes we've allocated.
00085   BytesAllocated += Size;
00086 
00087   // 0-byte alignment means 1-byte alignment.
00088   if (Alignment == 0) Alignment = 1;
00089 
00090   // Allocate the aligned space, going forwards from CurPtr.
00091   char *Ptr = AlignPtr(CurPtr, Alignment);
00092 
00093   // Check if we can hold it.
00094   if (Ptr + Size <= End) {
00095     CurPtr = Ptr + Size;
00096     return Ptr;
00097   }
00098 
00099   // If Size is really big, allocate a separate slab for it.
00100   size_t PaddedSize = Size + sizeof(MemSlab) + Alignment - 1;
00101   if (PaddedSize > SizeThreshold) {
00102     MemSlab *NewSlab = Allocator.Allocate(PaddedSize);
00103 
00104     // Put the new slab after the current slab, since we are not allocating
00105     // into it.
00106     NewSlab->NextPtr = CurSlab->NextPtr;
00107     CurSlab->NextPtr = NewSlab;
00108 
00109     Ptr = AlignPtr((char*)(NewSlab + 1), Alignment);
00110     assert((uintptr_t)Ptr + Size <= (uintptr_t)NewSlab + NewSlab->Size);
00111     return Ptr;
00112   }
00113 
00114   // Otherwise, start a new slab and try again.
00115   StartNewSlab();
00116   Ptr = AlignPtr(CurPtr, Alignment);
00117   CurPtr = Ptr + Size;
00118   assert(CurPtr <= End && "Unable to allocate memory!");
00119   return Ptr;
00120 }
00121 
00122 unsigned BumpPtrAllocator::GetNumSlabs() const {
00123   unsigned NumSlabs = 0;
00124   for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) {
00125     ++NumSlabs;
00126   }
00127   return NumSlabs;
00128 }
00129 
00130 void BumpPtrAllocator::PrintStats() const {
00131   unsigned NumSlabs = 0;
00132   size_t TotalMemory = 0;
00133   for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) {
00134     TotalMemory += Slab->Size;
00135     ++NumSlabs;
00136   }
00137 
00138   errs() << "\nNumber of memory regions: " << NumSlabs << '\n'
00139          << "Bytes used: " << BytesAllocated << '\n'
00140          << "Bytes allocated: " << TotalMemory << '\n'
00141          << "Bytes wasted: " << (TotalMemory - BytesAllocated)
00142          << " (includes alignment, etc)\n";
00143 }
00144 
00145 MallocSlabAllocator BumpPtrAllocator::DefaultSlabAllocator =
00146   MallocSlabAllocator();
00147 
00148 SlabAllocator::~SlabAllocator() { }
00149 
00150 MallocSlabAllocator::~MallocSlabAllocator() { }
00151 
00152 MemSlab *MallocSlabAllocator::Allocate(size_t Size) {
00153   MemSlab *Slab = (MemSlab*)Allocator.Allocate(Size, 0);
00154   Slab->Size = Size;
00155   Slab->NextPtr = 0;
00156   return Slab;
00157 }
00158 
00159 void MallocSlabAllocator::Deallocate(MemSlab *Slab) {
00160   Allocator.Deallocate(Slab);
00161 }
00162 
00163 void PrintRecyclerStats(size_t Size,
00164                         size_t Align,
00165                         size_t FreeListSize) {
00166   errs() << "Recycler element size: " << Size << '\n'
00167          << "Recycler element alignment: " << Align << '\n'
00168          << "Number of elements free for recycling: " << FreeListSize << '\n';
00169 }
00170 
00171 }