LLVM API Documentation

JITMemoryManager.cpp

Go to the documentation of this file.
00001 //===-- JITMemoryManager.cpp - Memory Allocator for JIT'd code ------------===//
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 defines the DefaultJITMemoryManager class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #define DEBUG_TYPE "jit"
00015 #include "llvm/ExecutionEngine/JITMemoryManager.h"
00016 #include "llvm/ADT/SmallPtrSet.h"
00017 #include "llvm/ADT/Statistic.h"
00018 #include "llvm/GlobalValue.h"
00019 #include "llvm/Support/Allocator.h"
00020 #include "llvm/Support/Compiler.h"
00021 #include "llvm/Support/Debug.h"
00022 #include "llvm/Support/ErrorHandling.h"
00023 #include "llvm/Support/raw_ostream.h"
00024 #include "llvm/System/Memory.h"
00025 #include <map>
00026 #include <vector>
00027 #include <cassert>
00028 #include <climits>
00029 #include <cstdio>
00030 #include <cstdlib>
00031 #include <cstring>
00032 using namespace llvm;
00033 
00034 STATISTIC(NumSlabs, "Number of slabs of memory allocated by the JIT");
00035 
00036 JITMemoryManager::~JITMemoryManager() {}
00037 
00038 //===----------------------------------------------------------------------===//
00039 // Memory Block Implementation.
00040 //===----------------------------------------------------------------------===//
00041 
00042 namespace {
00043   /// MemoryRangeHeader - For a range of memory, this is the header that we put
00044   /// on the block of memory.  It is carefully crafted to be one word of memory.
00045   /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader
00046   /// which starts with this.
00047   struct FreeRangeHeader;
00048   struct MemoryRangeHeader {
00049     /// ThisAllocated - This is true if this block is currently allocated.  If
00050     /// not, this can be converted to a FreeRangeHeader.
00051     unsigned ThisAllocated : 1;
00052     
00053     /// PrevAllocated - Keep track of whether the block immediately before us is
00054     /// allocated.  If not, the word immediately before this header is the size
00055     /// of the previous block.
00056     unsigned PrevAllocated : 1;
00057     
00058     /// BlockSize - This is the size in bytes of this memory block,
00059     /// including this header.
00060     uintptr_t BlockSize : (sizeof(intptr_t)*CHAR_BIT - 2);
00061     
00062 
00063     /// getBlockAfter - Return the memory block immediately after this one.
00064     ///
00065     MemoryRangeHeader &getBlockAfter() const {
00066       return *(MemoryRangeHeader*)((char*)this+BlockSize);
00067     }
00068     
00069     /// getFreeBlockBefore - If the block before this one is free, return it,
00070     /// otherwise return null.
00071     FreeRangeHeader *getFreeBlockBefore() const {
00072       if (PrevAllocated) return 0;
00073       intptr_t PrevSize = ((intptr_t *)this)[-1];
00074       return (FreeRangeHeader*)((char*)this-PrevSize);
00075     }
00076     
00077     /// FreeBlock - Turn an allocated block into a free block, adjusting
00078     /// bits in the object headers, and adding an end of region memory block.
00079     FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList);
00080     
00081     /// TrimAllocationToSize - If this allocated block is significantly larger
00082     /// than NewSize, split it into two pieces (where the former is NewSize
00083     /// bytes, including the header), and add the new block to the free list.
00084     FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList, 
00085                                           uint64_t NewSize);
00086   };
00087 
00088   /// FreeRangeHeader - For a memory block that isn't already allocated, this
00089   /// keeps track of the current block and has a pointer to the next free block.
00090   /// Free blocks are kept on a circularly linked list.
00091   struct FreeRangeHeader : public MemoryRangeHeader {
00092     FreeRangeHeader *Prev;
00093     FreeRangeHeader *Next;
00094     
00095     /// getMinBlockSize - Get the minimum size for a memory block.  Blocks
00096     /// smaller than this size cannot be created.
00097     static unsigned getMinBlockSize() {
00098       return sizeof(FreeRangeHeader)+sizeof(intptr_t);
00099     }
00100     
00101     /// SetEndOfBlockSizeMarker - The word at the end of every free block is
00102     /// known to be the size of the free block.  Set it for this block.
00103     void SetEndOfBlockSizeMarker() {
00104       void *EndOfBlock = (char*)this + BlockSize;
00105       ((intptr_t *)EndOfBlock)[-1] = BlockSize;
00106     }
00107 
00108     FreeRangeHeader *RemoveFromFreeList() {
00109       assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
00110       Next->Prev = Prev;
00111       return Prev->Next = Next;
00112     }
00113     
00114     void AddToFreeList(FreeRangeHeader *FreeList) {
00115       Next = FreeList;
00116       Prev = FreeList->Prev;
00117       Prev->Next = this;
00118       Next->Prev = this;
00119     }
00120 
00121     /// GrowBlock - The block after this block just got deallocated.  Merge it
00122     /// into the current block.
00123     void GrowBlock(uintptr_t NewSize);
00124     
00125     /// AllocateBlock - Mark this entire block allocated, updating freelists
00126     /// etc.  This returns a pointer to the circular free-list.
00127     FreeRangeHeader *AllocateBlock();
00128   };
00129 }
00130 
00131 
00132 /// AllocateBlock - Mark this entire block allocated, updating freelists
00133 /// etc.  This returns a pointer to the circular free-list.
00134 FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
00135   assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
00136          "Cannot allocate an allocated block!");
00137   // Mark this block allocated.
00138   ThisAllocated = 1;
00139   getBlockAfter().PrevAllocated = 1;
00140  
00141   // Remove it from the free list.
00142   return RemoveFromFreeList();
00143 }
00144 
00145 /// FreeBlock - Turn an allocated block into a free block, adjusting
00146 /// bits in the object headers, and adding an end of region memory block.
00147 /// If possible, coalesce this block with neighboring blocks.  Return the
00148 /// FreeRangeHeader to allocate from.
00149 FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) {
00150   MemoryRangeHeader *FollowingBlock = &getBlockAfter();
00151   assert(ThisAllocated && "This block is already free!");
00152   assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
00153   
00154   FreeRangeHeader *FreeListToReturn = FreeList;
00155   
00156   // If the block after this one is free, merge it into this block.
00157   if (!FollowingBlock->ThisAllocated) {
00158     FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
00159     // "FreeList" always needs to be a valid free block.  If we're about to
00160     // coalesce with it, update our notion of what the free list is.
00161     if (&FollowingFreeBlock == FreeList) {
00162       FreeList = FollowingFreeBlock.Next;
00163       FreeListToReturn = 0;
00164       assert(&FollowingFreeBlock != FreeList && "No tombstone block?");
00165     }
00166     FollowingFreeBlock.RemoveFromFreeList();
00167     
00168     // Include the following block into this one.
00169     BlockSize += FollowingFreeBlock.BlockSize;
00170     FollowingBlock = &FollowingFreeBlock.getBlockAfter();
00171     
00172     // Tell the block after the block we are coalescing that this block is
00173     // allocated.
00174     FollowingBlock->PrevAllocated = 1;
00175   }
00176   
00177   assert(FollowingBlock->ThisAllocated && "Missed coalescing?");
00178   
00179   if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
00180     PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
00181     return FreeListToReturn ? FreeListToReturn : PrevFreeBlock;
00182   }
00183 
00184   // Otherwise, mark this block free.
00185   FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
00186   FollowingBlock->PrevAllocated = 0;
00187   FreeBlock.ThisAllocated = 0;
00188 
00189   // Link this into the linked list of free blocks.
00190   FreeBlock.AddToFreeList(FreeList);
00191 
00192   // Add a marker at the end of the block, indicating the size of this free
00193   // block.
00194   FreeBlock.SetEndOfBlockSizeMarker();
00195   return FreeListToReturn ? FreeListToReturn : &FreeBlock;
00196 }
00197 
00198 /// GrowBlock - The block after this block just got deallocated.  Merge it
00199 /// into the current block.
00200 void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
00201   assert(NewSize > BlockSize && "Not growing block?");
00202   BlockSize = NewSize;
00203   SetEndOfBlockSizeMarker();
00204   getBlockAfter().PrevAllocated = 0;
00205 }
00206 
00207 /// TrimAllocationToSize - If this allocated block is significantly larger
00208 /// than NewSize, split it into two pieces (where the former is NewSize
00209 /// bytes, including the header), and add the new block to the free list.
00210 FreeRangeHeader *MemoryRangeHeader::
00211 TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
00212   assert(ThisAllocated && getBlockAfter().PrevAllocated &&
00213          "Cannot deallocate part of an allocated block!");
00214 
00215   // Don't allow blocks to be trimmed below minimum required size
00216   NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize);
00217 
00218   // Round up size for alignment of header.
00219   unsigned HeaderAlign = __alignof(FreeRangeHeader);
00220   NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
00221   
00222   // Size is now the size of the block we will remove from the start of the
00223   // current block.
00224   assert(NewSize <= BlockSize &&
00225          "Allocating more space from this block than exists!");
00226   
00227   // If splitting this block will cause the remainder to be too small, do not
00228   // split the block.
00229   if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
00230     return FreeList;
00231   
00232   // Otherwise, we splice the required number of bytes out of this block, form
00233   // a new block immediately after it, then mark this block allocated.
00234   MemoryRangeHeader &FormerNextBlock = getBlockAfter();
00235   
00236   // Change the size of this block.
00237   BlockSize = NewSize;
00238   
00239   // Get the new block we just sliced out and turn it into a free block.
00240   FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
00241   NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
00242   NewNextBlock.ThisAllocated = 0;
00243   NewNextBlock.PrevAllocated = 1;
00244   NewNextBlock.SetEndOfBlockSizeMarker();
00245   FormerNextBlock.PrevAllocated = 0;
00246   NewNextBlock.AddToFreeList(FreeList);
00247   return &NewNextBlock;
00248 }
00249 
00250 //===----------------------------------------------------------------------===//
00251 // Memory Block Implementation.
00252 //===----------------------------------------------------------------------===//
00253 
00254 namespace {
00255 
00256   class DefaultJITMemoryManager;
00257 
00258   class JITSlabAllocator : public SlabAllocator {
00259     DefaultJITMemoryManager &JMM;
00260   public:
00261     JITSlabAllocator(DefaultJITMemoryManager &jmm) : JMM(jmm) { }
00262     virtual ~JITSlabAllocator() { }
00263     virtual MemSlab *Allocate(size_t Size);
00264     virtual void Deallocate(MemSlab *Slab);
00265   };
00266 
00267   /// DefaultJITMemoryManager - Manage memory for the JIT code generation.
00268   /// This splits a large block of MAP_NORESERVE'd memory into two
00269   /// sections, one for function stubs, one for the functions themselves.  We
00270   /// have to do this because we may need to emit a function stub while in the
00271   /// middle of emitting a function, and we don't know how large the function we
00272   /// are emitting is.
00273   class DefaultJITMemoryManager : public JITMemoryManager {
00274 
00275     // Whether to poison freed memory.
00276     bool PoisonMemory;
00277 
00278     /// LastSlab - This points to the last slab allocated and is used as the
00279     /// NearBlock parameter to AllocateRWX so that we can attempt to lay out all
00280     /// stubs, data, and code contiguously in memory.  In general, however, this
00281     /// is not possible because the NearBlock parameter is ignored on Windows
00282     /// platforms and even on Unix it works on a best-effort pasis.
00283     sys::MemoryBlock LastSlab;
00284 
00285     // Memory slabs allocated by the JIT.  We refer to them as slabs so we don't
00286     // confuse them with the blocks of memory descibed above.
00287     std::vector<sys::MemoryBlock> CodeSlabs;
00288     JITSlabAllocator BumpSlabAllocator;
00289     BumpPtrAllocator StubAllocator;
00290     BumpPtrAllocator DataAllocator;
00291 
00292     // Circular list of free blocks.
00293     FreeRangeHeader *FreeMemoryList;
00294 
00295     // When emitting code into a memory block, this is the block.
00296     MemoryRangeHeader *CurBlock;
00297 
00298     uint8_t *GOTBase;     // Target Specific reserved memory
00299     void *DlsymTable;     // Stub external symbol information
00300 
00301     std::map<const Function*, MemoryRangeHeader*> FunctionBlocks;
00302     std::map<const Function*, MemoryRangeHeader*> TableBlocks;
00303   public:
00304     DefaultJITMemoryManager();
00305     ~DefaultJITMemoryManager();
00306 
00307     /// allocateNewSlab - Allocates a new MemoryBlock and remembers it as the
00308     /// last slab it allocated, so that subsequent allocations follow it.
00309     sys::MemoryBlock allocateNewSlab(size_t size);
00310 
00311     /// DefaultCodeSlabSize - When we have to go map more memory, we allocate at
00312     /// least this much unless more is requested.
00313     static const size_t DefaultCodeSlabSize;
00314 
00315     /// DefaultSlabSize - Allocate data into slabs of this size unless we get
00316     /// an allocation above SizeThreshold.
00317     static const size_t DefaultSlabSize;
00318 
00319     /// DefaultSizeThreshold - For any allocation larger than this threshold, we
00320     /// should allocate a separate slab.
00321     static const size_t DefaultSizeThreshold;
00322 
00323     void AllocateGOT();
00324     void SetDlsymTable(void *);
00325 
00326     // Testing methods.
00327     virtual bool CheckInvariants(std::string &ErrorStr);
00328     size_t GetDefaultCodeSlabSize() { return DefaultCodeSlabSize; }
00329     size_t GetDefaultDataSlabSize() { return DefaultSlabSize; }
00330     size_t GetDefaultStubSlabSize() { return DefaultSlabSize; }
00331     unsigned GetNumCodeSlabs() { return CodeSlabs.size(); }
00332     unsigned GetNumDataSlabs() { return DataAllocator.GetNumSlabs(); }
00333     unsigned GetNumStubSlabs() { return StubAllocator.GetNumSlabs(); }
00334 
00335     /// startFunctionBody - When a function starts, allocate a block of free
00336     /// executable memory, returning a pointer to it and its actual size.
00337     uint8_t *startFunctionBody(const Function *F, uintptr_t &ActualSize) {
00338 
00339       FreeRangeHeader* candidateBlock = FreeMemoryList;
00340       FreeRangeHeader* head = FreeMemoryList;
00341       FreeRangeHeader* iter = head->Next;
00342 
00343       uintptr_t largest = candidateBlock->BlockSize;
00344 
00345       // Search for the largest free block
00346       while (iter != head) {
00347         if (iter->BlockSize > largest) {
00348           largest = iter->BlockSize;
00349           candidateBlock = iter;
00350         }
00351         iter = iter->Next;
00352       }
00353 
00354       largest = largest - sizeof(MemoryRangeHeader);
00355       
00356       // If this block isn't big enough for the allocation desired, allocate
00357       // another block of memory and add it to the free list.
00358       if (largest < ActualSize ||
00359           largest <= FreeRangeHeader::getMinBlockSize()) {
00360         DOUT << "JIT: Allocating another slab of memory for function.";
00361         candidateBlock = allocateNewCodeSlab((size_t)ActualSize);
00362       }
00363 
00364       // Select this candidate block for allocation
00365       CurBlock = candidateBlock;
00366 
00367       // Allocate the entire memory block.
00368       FreeMemoryList = candidateBlock->AllocateBlock();
00369       ActualSize = CurBlock->BlockSize - sizeof(MemoryRangeHeader);
00370       return (uint8_t *)(CurBlock + 1);
00371     }
00372 
00373     /// allocateNewCodeSlab - Helper method to allocate a new slab of code
00374     /// memory from the OS and add it to the free list.  Returns the new
00375     /// FreeRangeHeader at the base of the slab.
00376     FreeRangeHeader *allocateNewCodeSlab(size_t MinSize) {
00377       // If the user needs at least MinSize free memory, then we account for
00378       // two MemoryRangeHeaders: the one in the user's block, and the one at the
00379       // end of the slab.
00380       size_t PaddedMin = MinSize + 2 * sizeof(MemoryRangeHeader);
00381       size_t SlabSize = std::max(DefaultCodeSlabSize, PaddedMin);
00382       sys::MemoryBlock B = allocateNewSlab(SlabSize);
00383       CodeSlabs.push_back(B);
00384       char *MemBase = (char*)(B.base());
00385 
00386       // Put a tiny allocated block at the end of the memory chunk, so when
00387       // FreeBlock calls getBlockAfter it doesn't fall off the end.
00388       MemoryRangeHeader *EndBlock =
00389           (MemoryRangeHeader*)(MemBase + B.size()) - 1;
00390       EndBlock->ThisAllocated = 1;
00391       EndBlock->PrevAllocated = 0;
00392       EndBlock->BlockSize = sizeof(MemoryRangeHeader);
00393 
00394       // Start out with a vast new block of free memory.
00395       FreeRangeHeader *NewBlock = (FreeRangeHeader*)MemBase;
00396       NewBlock->ThisAllocated = 0;
00397       // Make sure getFreeBlockBefore doesn't look into unmapped memory.
00398       NewBlock->PrevAllocated = 1;
00399       NewBlock->BlockSize = (uintptr_t)EndBlock - (uintptr_t)NewBlock;
00400       NewBlock->SetEndOfBlockSizeMarker();
00401       NewBlock->AddToFreeList(FreeMemoryList);
00402 
00403       assert(NewBlock->BlockSize - sizeof(MemoryRangeHeader) >= MinSize &&
00404              "The block was too small!");
00405       return NewBlock;
00406     }
00407 
00408     /// endFunctionBody - The function F is now allocated, and takes the memory
00409     /// in the range [FunctionStart,FunctionEnd).
00410     void endFunctionBody(const Function *F, uint8_t *FunctionStart,
00411                          uint8_t *FunctionEnd) {
00412       assert(FunctionEnd > FunctionStart);
00413       assert(FunctionStart == (uint8_t *)(CurBlock+1) &&
00414              "Mismatched function start/end!");
00415 
00416       uintptr_t BlockSize = FunctionEnd - (uint8_t *)CurBlock;
00417       FunctionBlocks[F] = CurBlock;
00418 
00419       // Release the memory at the end of this block that isn't needed.
00420       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
00421     }
00422 
00423     /// allocateSpace - Allocate a memory block of the given size.  This method
00424     /// cannot be called between calls to startFunctionBody and endFunctionBody.
00425     uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) {
00426       CurBlock = FreeMemoryList;
00427       FreeMemoryList = FreeMemoryList->AllocateBlock();
00428 
00429       uint8_t *result = (uint8_t *)(CurBlock + 1);
00430 
00431       if (Alignment == 0) Alignment = 1;
00432       result = (uint8_t*)(((intptr_t)result+Alignment-1) &
00433                ~(intptr_t)(Alignment-1));
00434 
00435       uintptr_t BlockSize = result + Size - (uint8_t *)CurBlock;
00436       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
00437 
00438       return result;
00439     }
00440 
00441     /// allocateStub - Allocate memory for a function stub.
00442     uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize,
00443                           unsigned Alignment) {
00444       return (uint8_t*)StubAllocator.Allocate(StubSize, Alignment);
00445     }
00446 
00447     /// allocateGlobal - Allocate memory for a global.
00448     uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) {
00449       return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
00450     }
00451 
00452     /// startExceptionTable - Use startFunctionBody to allocate memory for the 
00453     /// function's exception table.
00454     uint8_t* startExceptionTable(const Function* F, uintptr_t &ActualSize) {
00455       return startFunctionBody(F, ActualSize);
00456     }
00457 
00458     /// endExceptionTable - The exception table of F is now allocated, 
00459     /// and takes the memory in the range [TableStart,TableEnd).
00460     void endExceptionTable(const Function *F, uint8_t *TableStart,
00461                            uint8_t *TableEnd, uint8_t* FrameRegister) {
00462       assert(TableEnd > TableStart);
00463       assert(TableStart == (uint8_t *)(CurBlock+1) &&
00464              "Mismatched table start/end!");
00465       
00466       uintptr_t BlockSize = TableEnd - (uint8_t *)CurBlock;
00467       TableBlocks[F] = CurBlock;
00468 
00469       // Release the memory at the end of this block that isn't needed.
00470       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
00471     }
00472     
00473     uint8_t *getGOTBase() const {
00474       return GOTBase;
00475     }
00476     
00477     void *getDlsymTable() const {
00478       return DlsymTable;
00479     }
00480     
00481     /// deallocateMemForFunction - Deallocate all memory for the specified
00482     /// function body.
00483     void deallocateMemForFunction(const Function *F) {
00484       std::map<const Function*, MemoryRangeHeader*>::iterator
00485         I = FunctionBlocks.find(F);
00486       if (I == FunctionBlocks.end()) return;
00487       
00488       // Find the block that is allocated for this function.
00489       MemoryRangeHeader *MemRange = I->second;
00490       assert(MemRange->ThisAllocated && "Block isn't allocated!");
00491 
00492       // Fill the buffer with garbage!
00493       if (PoisonMemory) {
00494         memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
00495       }
00496 
00497       // Free the memory.
00498       FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
00499       
00500       // Finally, remove this entry from FunctionBlocks.
00501       FunctionBlocks.erase(I);
00502       
00503       I = TableBlocks.find(F);
00504       if (I == TableBlocks.end()) return;
00505       
00506       // Find the block that is allocated for this function.
00507       MemRange = I->second;
00508       assert(MemRange->ThisAllocated && "Block isn't allocated!");
00509 
00510       // Fill the buffer with garbage!
00511       if (PoisonMemory) {
00512         memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
00513       }
00514 
00515       // Free the memory.
00516       FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
00517       
00518       // Finally, remove this entry from TableBlocks.
00519       TableBlocks.erase(I);
00520     }
00521 
00522     /// setMemoryWritable - When code generation is in progress,
00523     /// the code pages may need permissions changed.
00524     void setMemoryWritable()
00525     {
00526       for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
00527         sys::Memory::setWritable(CodeSlabs[i]);
00528     }
00529     /// setMemoryExecutable - When code generation is done and we're ready to
00530     /// start execution, the code pages may need permissions changed.
00531     void setMemoryExecutable()
00532     {
00533       for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
00534         sys::Memory::setExecutable(CodeSlabs[i]);
00535     }
00536 
00537     /// setPoisonMemory - Controls whether we write garbage over freed memory.
00538     ///
00539     void setPoisonMemory(bool poison) {
00540       PoisonMemory = poison;
00541     }
00542   };
00543 }
00544 
00545 MemSlab *JITSlabAllocator::Allocate(size_t Size) {
00546   sys::MemoryBlock B = JMM.allocateNewSlab(Size);
00547   MemSlab *Slab = (MemSlab*)B.base();
00548   Slab->Size = B.size();
00549   Slab->NextPtr = 0;
00550   return Slab;
00551 }
00552 
00553 void JITSlabAllocator::Deallocate(MemSlab *Slab) {
00554   sys::MemoryBlock B(Slab, Slab->Size);
00555   sys::Memory::ReleaseRWX(B);
00556 }
00557 
00558 DefaultJITMemoryManager::DefaultJITMemoryManager()
00559   : LastSlab(0, 0),
00560     BumpSlabAllocator(*this),
00561     StubAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator),
00562     DataAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator) {
00563 
00564 #ifdef NDEBUG
00565   PoisonMemory = false;
00566 #else
00567   PoisonMemory = true;
00568 #endif
00569 
00570   // Allocate space for code.
00571   sys::MemoryBlock MemBlock = allocateNewSlab(DefaultCodeSlabSize);
00572   CodeSlabs.push_back(MemBlock);
00573   uint8_t *MemBase = (uint8_t*)MemBlock.base();
00574 
00575   // We set up the memory chunk with 4 mem regions, like this:
00576   //  [ START
00577   //    [ Free      #0 ] -> Large space to allocate functions from.
00578   //    [ Allocated #1 ] -> Tiny space to separate regions.
00579   //    [ Free      #2 ] -> Tiny space so there is always at least 1 free block.
00580   //    [ Allocated #3 ] -> Tiny space to prevent looking past end of block.
00581   //  END ]
00582   //
00583   // The last three blocks are never deallocated or touched.
00584   
00585   // Add MemoryRangeHeader to the end of the memory region, indicating that
00586   // the space after the block of memory is allocated.  This is block #3.
00587   MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
00588   Mem3->ThisAllocated = 1;
00589   Mem3->PrevAllocated = 0;
00590   Mem3->BlockSize     = sizeof(MemoryRangeHeader);
00591   
00592   /// Add a tiny free region so that the free list always has one entry.
00593   FreeRangeHeader *Mem2 = 
00594     (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
00595   Mem2->ThisAllocated = 0;
00596   Mem2->PrevAllocated = 1;
00597   Mem2->BlockSize     = FreeRangeHeader::getMinBlockSize();
00598   Mem2->SetEndOfBlockSizeMarker();
00599   Mem2->Prev = Mem2;   // Mem2 *is* the free list for now.
00600   Mem2->Next = Mem2;
00601 
00602   /// Add a tiny allocated region so that Mem2 is never coalesced away.
00603   MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
00604   Mem1->ThisAllocated = 1;
00605   Mem1->PrevAllocated = 0;
00606   Mem1->BlockSize     = sizeof(MemoryRangeHeader);
00607   
00608   // Add a FreeRangeHeader to the start of the function body region, indicating
00609   // that the space is free.  Mark the previous block allocated so we never look
00610   // at it.
00611   FreeRangeHeader *Mem0 = (FreeRangeHeader*)MemBase;
00612   Mem0->ThisAllocated = 0;
00613   Mem0->PrevAllocated = 1;
00614   Mem0->BlockSize = (char*)Mem1-(char*)Mem0;
00615   Mem0->SetEndOfBlockSizeMarker();
00616   Mem0->AddToFreeList(Mem2);
00617   
00618   // Start out with the freelist pointing to Mem0.
00619   FreeMemoryList = Mem0;
00620 
00621   GOTBase = NULL;
00622   DlsymTable = NULL;
00623 }
00624 
00625 void DefaultJITMemoryManager::AllocateGOT() {
00626   assert(GOTBase == 0 && "Cannot allocate the got multiple times");
00627   GOTBase = new uint8_t[sizeof(void*) * 8192];
00628   HasGOT = true;
00629 }
00630 
00631 void DefaultJITMemoryManager::SetDlsymTable(void *ptr) {
00632   DlsymTable = ptr;
00633 }
00634 
00635 DefaultJITMemoryManager::~DefaultJITMemoryManager() {
00636   for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
00637     sys::Memory::ReleaseRWX(CodeSlabs[i]);
00638 
00639   delete[] GOTBase;
00640 }
00641 
00642 sys::MemoryBlock DefaultJITMemoryManager::allocateNewSlab(size_t size) {
00643   // Allocate a new block close to the last one.
00644   std::string ErrMsg;
00645   sys::MemoryBlock *LastSlabPtr = LastSlab.base() ? &LastSlab : 0;
00646   sys::MemoryBlock B = sys::Memory::AllocateRWX(size, LastSlabPtr, &ErrMsg);
00647   if (B.base() == 0) {
00648     llvm_report_error("Allocation failed when allocating new memory in the"
00649                       " JIT\n" + ErrMsg);
00650   }
00651   LastSlab = B;
00652   ++NumSlabs;
00653   // Initialize the slab to garbage when debugging.
00654   if (PoisonMemory) {
00655     memset(B.base(), 0xCD, B.size());
00656   }
00657   return B;
00658 }
00659 
00660 /// CheckInvariants - For testing only.  Return "" if all internal invariants
00661 /// are preserved, and a helpful error message otherwise.  For free and
00662 /// allocated blocks, make sure that adding BlockSize gives a valid block.
00663 /// For free blocks, make sure they're in the free list and that their end of
00664 /// block size marker is correct.  This function should return an error before
00665 /// accessing bad memory.  This function is defined here instead of in
00666 /// JITMemoryManagerTest.cpp so that we don't have to expose all of the
00667 /// implementation details of DefaultJITMemoryManager.
00668 bool DefaultJITMemoryManager::CheckInvariants(std::string &ErrorStr) {
00669   raw_string_ostream Err(ErrorStr);
00670 
00671   // Construct a the set of FreeRangeHeader pointers so we can query it
00672   // efficiently.
00673   llvm::SmallPtrSet<MemoryRangeHeader*, 16> FreeHdrSet;
00674   FreeRangeHeader* FreeHead = FreeMemoryList;
00675   FreeRangeHeader* FreeRange = FreeHead;
00676 
00677   do {
00678     // Check that the free range pointer is in the blocks we've allocated.
00679     bool Found = false;
00680     for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
00681          E = CodeSlabs.end(); I != E && !Found; ++I) {
00682       char *Start = (char*)I->base();
00683       char *End = Start + I->size();
00684       Found = (Start <= (char*)FreeRange && (char*)FreeRange < End);
00685     }
00686     if (!Found) {
00687       Err << "Corrupt free list; points to " << FreeRange;
00688       return false;
00689     }
00690 
00691     if (FreeRange->Next->Prev != FreeRange) {
00692       Err << "Next and Prev pointers do not match.";
00693       return false;
00694     }
00695 
00696     // Otherwise, add it to the set.
00697     FreeHdrSet.insert(FreeRange);
00698     FreeRange = FreeRange->Next;
00699   } while (FreeRange != FreeHead);
00700 
00701   // Go over each block, and look at each MemoryRangeHeader.
00702   for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
00703        E = CodeSlabs.end(); I != E; ++I) {
00704     char *Start = (char*)I->base();
00705     char *End = Start + I->size();
00706 
00707     // Check each memory range.
00708     for (MemoryRangeHeader *Hdr = (MemoryRangeHeader*)Start, *LastHdr = NULL;
00709          Start <= (char*)Hdr && (char*)Hdr < End;
00710          Hdr = &Hdr->getBlockAfter()) {
00711       if (Hdr->ThisAllocated == 0) {
00712         // Check that this range is in the free list.
00713         if (!FreeHdrSet.count(Hdr)) {
00714           Err << "Found free header at " << Hdr << " that is not in free list.";
00715           return false;
00716         }
00717 
00718         // Now make sure the size marker at the end of the block is correct.
00719         uintptr_t *Marker = ((uintptr_t*)&Hdr->getBlockAfter()) - 1;
00720         if (!(Start <= (char*)Marker && (char*)Marker < End)) {
00721           Err << "Block size in header points out of current MemoryBlock.";
00722           return false;
00723         }
00724         if (Hdr->BlockSize != *Marker) {
00725           Err << "End of block size marker (" << *Marker << ") "
00726               << "and BlockSize (" << Hdr->BlockSize << ") don't match.";
00727           return false;
00728         }
00729       }
00730 
00731       if (LastHdr && LastHdr->ThisAllocated != Hdr->PrevAllocated) {
00732         Err << "Hdr->PrevAllocated (" << Hdr->PrevAllocated << ") != "
00733             << "LastHdr->ThisAllocated (" << LastHdr->ThisAllocated << ")";
00734         return false;
00735       } else if (!LastHdr && !Hdr->PrevAllocated) {
00736         Err << "The first header should have PrevAllocated true.";
00737         return false;
00738       }
00739 
00740       // Remember the last header.
00741       LastHdr = Hdr;
00742     }
00743   }
00744 
00745   // All invariants are preserved.
00746   return true;
00747 }
00748 
00749 JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() {
00750   return new DefaultJITMemoryManager();
00751 }
00752 
00753 // Allocate memory for code in 512K slabs.
00754 const size_t DefaultJITMemoryManager::DefaultCodeSlabSize = 512 * 1024;
00755 
00756 // Allocate globals and stubs in slabs of 64K.  (probably 16 pages)
00757 const size_t DefaultJITMemoryManager::DefaultSlabSize = 64 * 1024;
00758 
00759 // Waste at most 16K at the end of each bump slab.  (probably 4 pages)
00760 const size_t DefaultJITMemoryManager::DefaultSizeThreshold = 16 * 1024;