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/ADT/Twine.h"
00019 #include "llvm/Config/config.h"
00020 #include "llvm/IR/GlobalValue.h"
00021 #include "llvm/Support/Allocator.h"
00022 #include "llvm/Support/Compiler.h"
00023 #include "llvm/Support/Debug.h"
00024 #include "llvm/Support/DynamicLibrary.h"
00025 #include "llvm/Support/ErrorHandling.h"
00026 #include "llvm/Support/Memory.h"
00027 #include "llvm/Support/raw_ostream.h"
00028 #include <cassert>
00029 #include <climits>
00030 #include <cstring>
00031 #include <vector>
00032 
00033 #if defined(__linux__)
00034 #if defined(HAVE_SYS_STAT_H)
00035 #include <sys/stat.h>
00036 #endif
00037 #include <fcntl.h>
00038 #include <unistd.h>
00039 #endif
00040 
00041 using namespace llvm;
00042 
00043 STATISTIC(NumSlabs, "Number of slabs of memory allocated by the JIT");
00044 
00045 JITMemoryManager::~JITMemoryManager() {}
00046 
00047 //===----------------------------------------------------------------------===//
00048 // Memory Block Implementation.
00049 //===----------------------------------------------------------------------===//
00050 
00051 namespace {
00052   /// MemoryRangeHeader - For a range of memory, this is the header that we put
00053   /// on the block of memory.  It is carefully crafted to be one word of memory.
00054   /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader
00055   /// which starts with this.
00056   struct FreeRangeHeader;
00057   struct MemoryRangeHeader {
00058     /// ThisAllocated - This is true if this block is currently allocated.  If
00059     /// not, this can be converted to a FreeRangeHeader.
00060     unsigned ThisAllocated : 1;
00061 
00062     /// PrevAllocated - Keep track of whether the block immediately before us is
00063     /// allocated.  If not, the word immediately before this header is the size
00064     /// of the previous block.
00065     unsigned PrevAllocated : 1;
00066 
00067     /// BlockSize - This is the size in bytes of this memory block,
00068     /// including this header.
00069     uintptr_t BlockSize : (sizeof(intptr_t)*CHAR_BIT - 2);
00070 
00071 
00072     /// getBlockAfter - Return the memory block immediately after this one.
00073     ///
00074     MemoryRangeHeader &getBlockAfter() const {
00075       return *reinterpret_cast<MemoryRangeHeader *>(
00076                 reinterpret_cast<char*>(
00077                   const_cast<MemoryRangeHeader *>(this))+BlockSize);
00078     }
00079 
00080     /// getFreeBlockBefore - If the block before this one is free, return it,
00081     /// otherwise return null.
00082     FreeRangeHeader *getFreeBlockBefore() const {
00083       if (PrevAllocated) return 0;
00084       intptr_t PrevSize = reinterpret_cast<intptr_t *>(
00085                             const_cast<MemoryRangeHeader *>(this))[-1];
00086       return reinterpret_cast<FreeRangeHeader *>(
00087                reinterpret_cast<char*>(
00088                  const_cast<MemoryRangeHeader *>(this))-PrevSize);
00089     }
00090 
00091     /// FreeBlock - Turn an allocated block into a free block, adjusting
00092     /// bits in the object headers, and adding an end of region memory block.
00093     FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList);
00094 
00095     /// TrimAllocationToSize - If this allocated block is significantly larger
00096     /// than NewSize, split it into two pieces (where the former is NewSize
00097     /// bytes, including the header), and add the new block to the free list.
00098     FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList,
00099                                           uint64_t NewSize);
00100   };
00101 
00102   /// FreeRangeHeader - For a memory block that isn't already allocated, this
00103   /// keeps track of the current block and has a pointer to the next free block.
00104   /// Free blocks are kept on a circularly linked list.
00105   struct FreeRangeHeader : public MemoryRangeHeader {
00106     FreeRangeHeader *Prev;
00107     FreeRangeHeader *Next;
00108 
00109     /// getMinBlockSize - Get the minimum size for a memory block.  Blocks
00110     /// smaller than this size cannot be created.
00111     static unsigned getMinBlockSize() {
00112       return sizeof(FreeRangeHeader)+sizeof(intptr_t);
00113     }
00114 
00115     /// SetEndOfBlockSizeMarker - The word at the end of every free block is
00116     /// known to be the size of the free block.  Set it for this block.
00117     void SetEndOfBlockSizeMarker() {
00118       void *EndOfBlock = (char*)this + BlockSize;
00119       ((intptr_t *)EndOfBlock)[-1] = BlockSize;
00120     }
00121 
00122     FreeRangeHeader *RemoveFromFreeList() {
00123       assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
00124       Next->Prev = Prev;
00125       return Prev->Next = Next;
00126     }
00127 
00128     void AddToFreeList(FreeRangeHeader *FreeList) {
00129       Next = FreeList;
00130       Prev = FreeList->Prev;
00131       Prev->Next = this;
00132       Next->Prev = this;
00133     }
00134 
00135     /// GrowBlock - The block after this block just got deallocated.  Merge it
00136     /// into the current block.
00137     void GrowBlock(uintptr_t NewSize);
00138 
00139     /// AllocateBlock - Mark this entire block allocated, updating freelists
00140     /// etc.  This returns a pointer to the circular free-list.
00141     FreeRangeHeader *AllocateBlock();
00142   };
00143 }
00144 
00145 
00146 /// AllocateBlock - Mark this entire block allocated, updating freelists
00147 /// etc.  This returns a pointer to the circular free-list.
00148 FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
00149   assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
00150          "Cannot allocate an allocated block!");
00151   // Mark this block allocated.
00152   ThisAllocated = 1;
00153   getBlockAfter().PrevAllocated = 1;
00154 
00155   // Remove it from the free list.
00156   return RemoveFromFreeList();
00157 }
00158 
00159 /// FreeBlock - Turn an allocated block into a free block, adjusting
00160 /// bits in the object headers, and adding an end of region memory block.
00161 /// If possible, coalesce this block with neighboring blocks.  Return the
00162 /// FreeRangeHeader to allocate from.
00163 FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) {
00164   MemoryRangeHeader *FollowingBlock = &getBlockAfter();
00165   assert(ThisAllocated && "This block is already free!");
00166   assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
00167 
00168   FreeRangeHeader *FreeListToReturn = FreeList;
00169 
00170   // If the block after this one is free, merge it into this block.
00171   if (!FollowingBlock->ThisAllocated) {
00172     FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
00173     // "FreeList" always needs to be a valid free block.  If we're about to
00174     // coalesce with it, update our notion of what the free list is.
00175     if (&FollowingFreeBlock == FreeList) {
00176       FreeList = FollowingFreeBlock.Next;
00177       FreeListToReturn = 0;
00178       assert(&FollowingFreeBlock != FreeList && "No tombstone block?");
00179     }
00180     FollowingFreeBlock.RemoveFromFreeList();
00181 
00182     // Include the following block into this one.
00183     BlockSize += FollowingFreeBlock.BlockSize;
00184     FollowingBlock = &FollowingFreeBlock.getBlockAfter();
00185 
00186     // Tell the block after the block we are coalescing that this block is
00187     // allocated.
00188     FollowingBlock->PrevAllocated = 1;
00189   }
00190 
00191   assert(FollowingBlock->ThisAllocated && "Missed coalescing?");
00192 
00193   if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
00194     PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
00195     return FreeListToReturn ? FreeListToReturn : PrevFreeBlock;
00196   }
00197 
00198   // Otherwise, mark this block free.
00199   FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
00200   FollowingBlock->PrevAllocated = 0;
00201   FreeBlock.ThisAllocated = 0;
00202 
00203   // Link this into the linked list of free blocks.
00204   FreeBlock.AddToFreeList(FreeList);
00205 
00206   // Add a marker at the end of the block, indicating the size of this free
00207   // block.
00208   FreeBlock.SetEndOfBlockSizeMarker();
00209   return FreeListToReturn ? FreeListToReturn : &FreeBlock;
00210 }
00211 
00212 /// GrowBlock - The block after this block just got deallocated.  Merge it
00213 /// into the current block.
00214 void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
00215   assert(NewSize > BlockSize && "Not growing block?");
00216   BlockSize = NewSize;
00217   SetEndOfBlockSizeMarker();
00218   getBlockAfter().PrevAllocated = 0;
00219 }
00220 
00221 /// TrimAllocationToSize - If this allocated block is significantly larger
00222 /// than NewSize, split it into two pieces (where the former is NewSize
00223 /// bytes, including the header), and add the new block to the free list.
00224 FreeRangeHeader *MemoryRangeHeader::
00225 TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
00226   assert(ThisAllocated && getBlockAfter().PrevAllocated &&
00227          "Cannot deallocate part of an allocated block!");
00228 
00229   // Don't allow blocks to be trimmed below minimum required size
00230   NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize);
00231 
00232   // Round up size for alignment of header.
00233   unsigned HeaderAlign = __alignof(FreeRangeHeader);
00234   NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
00235 
00236   // Size is now the size of the block we will remove from the start of the
00237   // current block.
00238   assert(NewSize <= BlockSize &&
00239          "Allocating more space from this block than exists!");
00240 
00241   // If splitting this block will cause the remainder to be too small, do not
00242   // split the block.
00243   if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
00244     return FreeList;
00245 
00246   // Otherwise, we splice the required number of bytes out of this block, form
00247   // a new block immediately after it, then mark this block allocated.
00248   MemoryRangeHeader &FormerNextBlock = getBlockAfter();
00249 
00250   // Change the size of this block.
00251   BlockSize = NewSize;
00252 
00253   // Get the new block we just sliced out and turn it into a free block.
00254   FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
00255   NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
00256   NewNextBlock.ThisAllocated = 0;
00257   NewNextBlock.PrevAllocated = 1;
00258   NewNextBlock.SetEndOfBlockSizeMarker();
00259   FormerNextBlock.PrevAllocated = 0;
00260   NewNextBlock.AddToFreeList(FreeList);
00261   return &NewNextBlock;
00262 }
00263 
00264 //===----------------------------------------------------------------------===//
00265 // Memory Block Implementation.
00266 //===----------------------------------------------------------------------===//
00267 
00268 namespace {
00269 
00270   class DefaultJITMemoryManager;
00271 
00272   class JITAllocator {
00273     DefaultJITMemoryManager &JMM;
00274   public:
00275     JITAllocator(DefaultJITMemoryManager &jmm) : JMM(jmm) { }
00276     void *Allocate(size_t Size, size_t /*Alignment*/);
00277     void Deallocate(void *Slab, size_t Size);
00278   };
00279 
00280   /// DefaultJITMemoryManager - Manage memory for the JIT code generation.
00281   /// This splits a large block of MAP_NORESERVE'd memory into two
00282   /// sections, one for function stubs, one for the functions themselves.  We
00283   /// have to do this because we may need to emit a function stub while in the
00284   /// middle of emitting a function, and we don't know how large the function we
00285   /// are emitting is.
00286   class DefaultJITMemoryManager : public JITMemoryManager {
00287   public:
00288     /// DefaultCodeSlabSize - When we have to go map more memory, we allocate at
00289     /// least this much unless more is requested. Currently, in 512k slabs.
00290     static const size_t DefaultCodeSlabSize = 512 * 1024;
00291 
00292     /// DefaultSlabSize - Allocate globals and stubs into slabs of 64K (probably
00293     /// 16 pages) unless we get an allocation above SizeThreshold.
00294     static const size_t DefaultSlabSize = 64 * 1024;
00295 
00296     /// DefaultSizeThreshold - For any allocation larger than 16K (probably
00297     /// 4 pages), we should allocate a separate slab to avoid wasted space at
00298     /// the end of a normal slab.
00299     static const size_t DefaultSizeThreshold = 16 * 1024;
00300 
00301   private:
00302     // Whether to poison freed memory.
00303     bool PoisonMemory;
00304 
00305     /// LastSlab - This points to the last slab allocated and is used as the
00306     /// NearBlock parameter to AllocateRWX so that we can attempt to lay out all
00307     /// stubs, data, and code contiguously in memory.  In general, however, this
00308     /// is not possible because the NearBlock parameter is ignored on Windows
00309     /// platforms and even on Unix it works on a best-effort pasis.
00310     sys::MemoryBlock LastSlab;
00311 
00312     // Memory slabs allocated by the JIT.  We refer to them as slabs so we don't
00313     // confuse them with the blocks of memory described above.
00314     std::vector<sys::MemoryBlock> CodeSlabs;
00315     BumpPtrAllocatorImpl<JITAllocator, DefaultSlabSize,
00316                          DefaultSizeThreshold> StubAllocator;
00317     BumpPtrAllocatorImpl<JITAllocator, DefaultSlabSize,
00318                          DefaultSizeThreshold> DataAllocator;
00319 
00320     // Circular list of free blocks.
00321     FreeRangeHeader *FreeMemoryList;
00322 
00323     // When emitting code into a memory block, this is the block.
00324     MemoryRangeHeader *CurBlock;
00325 
00326     uint8_t *GOTBase;     // Target Specific reserved memory
00327   public:
00328     DefaultJITMemoryManager();
00329     ~DefaultJITMemoryManager();
00330 
00331     /// allocateNewSlab - Allocates a new MemoryBlock and remembers it as the
00332     /// last slab it allocated, so that subsequent allocations follow it.
00333     sys::MemoryBlock allocateNewSlab(size_t size);
00334 
00335     /// getPointerToNamedFunction - This method returns the address of the
00336     /// specified function by using the dlsym function call.
00337     void *getPointerToNamedFunction(const std::string &Name,
00338                                     bool AbortOnFailure = true) override;
00339 
00340     void AllocateGOT() override;
00341 
00342     // Testing methods.
00343     bool CheckInvariants(std::string &ErrorStr) override;
00344     size_t GetDefaultCodeSlabSize() override { return DefaultCodeSlabSize; }
00345     size_t GetDefaultDataSlabSize() override { return DefaultSlabSize; }
00346     size_t GetDefaultStubSlabSize() override { return DefaultSlabSize; }
00347     unsigned GetNumCodeSlabs() override { return CodeSlabs.size(); }
00348     unsigned GetNumDataSlabs() override { return DataAllocator.GetNumSlabs(); }
00349     unsigned GetNumStubSlabs() override { return StubAllocator.GetNumSlabs(); }
00350 
00351     /// startFunctionBody - When a function starts, allocate a block of free
00352     /// executable memory, returning a pointer to it and its actual size.
00353     uint8_t *startFunctionBody(const Function *F,
00354                                uintptr_t &ActualSize) override {
00355 
00356       FreeRangeHeader* candidateBlock = FreeMemoryList;
00357       FreeRangeHeader* head = FreeMemoryList;
00358       FreeRangeHeader* iter = head->Next;
00359 
00360       uintptr_t largest = candidateBlock->BlockSize;
00361 
00362       // Search for the largest free block
00363       while (iter != head) {
00364         if (iter->BlockSize > largest) {
00365           largest = iter->BlockSize;
00366           candidateBlock = iter;
00367         }
00368         iter = iter->Next;
00369       }
00370 
00371       largest = largest - sizeof(MemoryRangeHeader);
00372 
00373       // If this block isn't big enough for the allocation desired, allocate
00374       // another block of memory and add it to the free list.
00375       if (largest < ActualSize ||
00376           largest <= FreeRangeHeader::getMinBlockSize()) {
00377         DEBUG(dbgs() << "JIT: Allocating another slab of memory for function.");
00378         candidateBlock = allocateNewCodeSlab((size_t)ActualSize);
00379       }
00380 
00381       // Select this candidate block for allocation
00382       CurBlock = candidateBlock;
00383 
00384       // Allocate the entire memory block.
00385       FreeMemoryList = candidateBlock->AllocateBlock();
00386       ActualSize = CurBlock->BlockSize - sizeof(MemoryRangeHeader);
00387       return (uint8_t *)(CurBlock + 1);
00388     }
00389 
00390     /// allocateNewCodeSlab - Helper method to allocate a new slab of code
00391     /// memory from the OS and add it to the free list.  Returns the new
00392     /// FreeRangeHeader at the base of the slab.
00393     FreeRangeHeader *allocateNewCodeSlab(size_t MinSize) {
00394       // If the user needs at least MinSize free memory, then we account for
00395       // two MemoryRangeHeaders: the one in the user's block, and the one at the
00396       // end of the slab.
00397       size_t PaddedMin = MinSize + 2 * sizeof(MemoryRangeHeader);
00398       size_t SlabSize = std::max(DefaultCodeSlabSize, PaddedMin);
00399       sys::MemoryBlock B = allocateNewSlab(SlabSize);
00400       CodeSlabs.push_back(B);
00401       char *MemBase = (char*)(B.base());
00402 
00403       // Put a tiny allocated block at the end of the memory chunk, so when
00404       // FreeBlock calls getBlockAfter it doesn't fall off the end.
00405       MemoryRangeHeader *EndBlock =
00406           (MemoryRangeHeader*)(MemBase + B.size()) - 1;
00407       EndBlock->ThisAllocated = 1;
00408       EndBlock->PrevAllocated = 0;
00409       EndBlock->BlockSize = sizeof(MemoryRangeHeader);
00410 
00411       // Start out with a vast new block of free memory.
00412       FreeRangeHeader *NewBlock = (FreeRangeHeader*)MemBase;
00413       NewBlock->ThisAllocated = 0;
00414       // Make sure getFreeBlockBefore doesn't look into unmapped memory.
00415       NewBlock->PrevAllocated = 1;
00416       NewBlock->BlockSize = (uintptr_t)EndBlock - (uintptr_t)NewBlock;
00417       NewBlock->SetEndOfBlockSizeMarker();
00418       NewBlock->AddToFreeList(FreeMemoryList);
00419 
00420       assert(NewBlock->BlockSize - sizeof(MemoryRangeHeader) >= MinSize &&
00421              "The block was too small!");
00422       return NewBlock;
00423     }
00424 
00425     /// endFunctionBody - The function F is now allocated, and takes the memory
00426     /// in the range [FunctionStart,FunctionEnd).
00427     void endFunctionBody(const Function *F, uint8_t *FunctionStart,
00428                          uint8_t *FunctionEnd) override {
00429       assert(FunctionEnd > FunctionStart);
00430       assert(FunctionStart == (uint8_t *)(CurBlock+1) &&
00431              "Mismatched function start/end!");
00432 
00433       uintptr_t BlockSize = FunctionEnd - (uint8_t *)CurBlock;
00434 
00435       // Release the memory at the end of this block that isn't needed.
00436       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
00437     }
00438 
00439     /// allocateSpace - Allocate a memory block of the given size.  This method
00440     /// cannot be called between calls to startFunctionBody and endFunctionBody.
00441     uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) override {
00442       CurBlock = FreeMemoryList;
00443       FreeMemoryList = FreeMemoryList->AllocateBlock();
00444 
00445       uint8_t *result = (uint8_t *)(CurBlock + 1);
00446 
00447       if (Alignment == 0) Alignment = 1;
00448       result = (uint8_t*)(((intptr_t)result+Alignment-1) &
00449                ~(intptr_t)(Alignment-1));
00450 
00451       uintptr_t BlockSize = result + Size - (uint8_t *)CurBlock;
00452       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
00453 
00454       return result;
00455     }
00456 
00457     /// allocateStub - Allocate memory for a function stub.
00458     uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize,
00459                           unsigned Alignment) override {
00460       return (uint8_t*)StubAllocator.Allocate(StubSize, Alignment);
00461     }
00462 
00463     /// allocateGlobal - Allocate memory for a global.
00464     uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) override {
00465       return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
00466     }
00467 
00468     /// allocateCodeSection - Allocate memory for a code section.
00469     uint8_t *allocateCodeSection(uintptr_t Size, unsigned Alignment,
00470                                  unsigned SectionID,
00471                                  StringRef SectionName) override {
00472       // Grow the required block size to account for the block header
00473       Size += sizeof(*CurBlock);
00474 
00475       // Alignment handling.
00476       if (!Alignment)
00477         Alignment = 16;
00478       Size += Alignment - 1;
00479 
00480       FreeRangeHeader* candidateBlock = FreeMemoryList;
00481       FreeRangeHeader* head = FreeMemoryList;
00482       FreeRangeHeader* iter = head->Next;
00483 
00484       uintptr_t largest = candidateBlock->BlockSize;
00485 
00486       // Search for the largest free block.
00487       while (iter != head) {
00488         if (iter->BlockSize > largest) {
00489           largest = iter->BlockSize;
00490           candidateBlock = iter;
00491         }
00492         iter = iter->Next;
00493       }
00494 
00495       largest = largest - sizeof(MemoryRangeHeader);
00496 
00497       // If this block isn't big enough for the allocation desired, allocate
00498       // another block of memory and add it to the free list.
00499       if (largest < Size || largest <= FreeRangeHeader::getMinBlockSize()) {
00500         DEBUG(dbgs() << "JIT: Allocating another slab of memory for function.");
00501         candidateBlock = allocateNewCodeSlab((size_t)Size);
00502       }
00503 
00504       // Select this candidate block for allocation
00505       CurBlock = candidateBlock;
00506 
00507       // Allocate the entire memory block.
00508       FreeMemoryList = candidateBlock->AllocateBlock();
00509       // Release the memory at the end of this block that isn't needed.
00510       FreeMemoryList = CurBlock->TrimAllocationToSize(FreeMemoryList, Size);
00511       uintptr_t unalignedAddr = (uintptr_t)CurBlock + sizeof(*CurBlock);
00512       return (uint8_t*)RoundUpToAlignment((uint64_t)unalignedAddr, Alignment);
00513     }
00514 
00515     /// allocateDataSection - Allocate memory for a data section.
00516     uint8_t *allocateDataSection(uintptr_t Size, unsigned Alignment,
00517                                  unsigned SectionID, StringRef SectionName,
00518                                  bool IsReadOnly) override {
00519       return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
00520     }
00521 
00522     bool finalizeMemory(std::string *ErrMsg) override {
00523       return false;
00524     }
00525 
00526     uint8_t *getGOTBase() const override {
00527       return GOTBase;
00528     }
00529 
00530     void deallocateBlock(void *Block) {
00531       // Find the block that is allocated for this function.
00532       MemoryRangeHeader *MemRange = static_cast<MemoryRangeHeader*>(Block) - 1;
00533       assert(MemRange->ThisAllocated && "Block isn't allocated!");
00534 
00535       // Fill the buffer with garbage!
00536       if (PoisonMemory) {
00537         memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
00538       }
00539 
00540       // Free the memory.
00541       FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
00542     }
00543 
00544     /// deallocateFunctionBody - Deallocate all memory for the specified
00545     /// function body.
00546     void deallocateFunctionBody(void *Body) override {
00547       if (Body) deallocateBlock(Body);
00548     }
00549 
00550     /// setMemoryWritable - When code generation is in progress,
00551     /// the code pages may need permissions changed.
00552     void setMemoryWritable() override {
00553       for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
00554         sys::Memory::setWritable(CodeSlabs[i]);
00555     }
00556     /// setMemoryExecutable - When code generation is done and we're ready to
00557     /// start execution, the code pages may need permissions changed.
00558     void setMemoryExecutable() override {
00559       for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
00560         sys::Memory::setExecutable(CodeSlabs[i]);
00561     }
00562 
00563     /// setPoisonMemory - Controls whether we write garbage over freed memory.
00564     ///
00565     void setPoisonMemory(bool poison) override {
00566       PoisonMemory = poison;
00567     }
00568   };
00569 }
00570 
00571 void *JITAllocator::Allocate(size_t Size, size_t /*Alignment*/) {
00572   sys::MemoryBlock B = JMM.allocateNewSlab(Size);
00573   return B.base();
00574 }
00575 
00576 void JITAllocator::Deallocate(void *Slab, size_t Size) {
00577   sys::MemoryBlock B(Slab, Size);
00578   sys::Memory::ReleaseRWX(B);
00579 }
00580 
00581 DefaultJITMemoryManager::DefaultJITMemoryManager()
00582     :
00583 #ifdef NDEBUG
00584       PoisonMemory(false),
00585 #else
00586       PoisonMemory(true),
00587 #endif
00588       LastSlab(0, 0), StubAllocator(*this), DataAllocator(*this) {
00589 
00590   // Allocate space for code.
00591   sys::MemoryBlock MemBlock = allocateNewSlab(DefaultCodeSlabSize);
00592   CodeSlabs.push_back(MemBlock);
00593   uint8_t *MemBase = (uint8_t*)MemBlock.base();
00594 
00595   // We set up the memory chunk with 4 mem regions, like this:
00596   //  [ START
00597   //    [ Free      #0 ] -> Large space to allocate functions from.
00598   //    [ Allocated #1 ] -> Tiny space to separate regions.
00599   //    [ Free      #2 ] -> Tiny space so there is always at least 1 free block.
00600   //    [ Allocated #3 ] -> Tiny space to prevent looking past end of block.
00601   //  END ]
00602   //
00603   // The last three blocks are never deallocated or touched.
00604 
00605   // Add MemoryRangeHeader to the end of the memory region, indicating that
00606   // the space after the block of memory is allocated.  This is block #3.
00607   MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
00608   Mem3->ThisAllocated = 1;
00609   Mem3->PrevAllocated = 0;
00610   Mem3->BlockSize     = sizeof(MemoryRangeHeader);
00611 
00612   /// Add a tiny free region so that the free list always has one entry.
00613   FreeRangeHeader *Mem2 =
00614     (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
00615   Mem2->ThisAllocated = 0;
00616   Mem2->PrevAllocated = 1;
00617   Mem2->BlockSize     = FreeRangeHeader::getMinBlockSize();
00618   Mem2->SetEndOfBlockSizeMarker();
00619   Mem2->Prev = Mem2;   // Mem2 *is* the free list for now.
00620   Mem2->Next = Mem2;
00621 
00622   /// Add a tiny allocated region so that Mem2 is never coalesced away.
00623   MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
00624   Mem1->ThisAllocated = 1;
00625   Mem1->PrevAllocated = 0;
00626   Mem1->BlockSize     = sizeof(MemoryRangeHeader);
00627 
00628   // Add a FreeRangeHeader to the start of the function body region, indicating
00629   // that the space is free.  Mark the previous block allocated so we never look
00630   // at it.
00631   FreeRangeHeader *Mem0 = (FreeRangeHeader*)MemBase;
00632   Mem0->ThisAllocated = 0;
00633   Mem0->PrevAllocated = 1;
00634   Mem0->BlockSize = (char*)Mem1-(char*)Mem0;
00635   Mem0->SetEndOfBlockSizeMarker();
00636   Mem0->AddToFreeList(Mem2);
00637 
00638   // Start out with the freelist pointing to Mem0.
00639   FreeMemoryList = Mem0;
00640 
00641   GOTBase = NULL;
00642 }
00643 
00644 void DefaultJITMemoryManager::AllocateGOT() {
00645   assert(GOTBase == 0 && "Cannot allocate the got multiple times");
00646   GOTBase = new uint8_t[sizeof(void*) * 8192];
00647   HasGOT = true;
00648 }
00649 
00650 DefaultJITMemoryManager::~DefaultJITMemoryManager() {
00651   for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
00652     sys::Memory::ReleaseRWX(CodeSlabs[i]);
00653 
00654   delete[] GOTBase;
00655 }
00656 
00657 sys::MemoryBlock DefaultJITMemoryManager::allocateNewSlab(size_t size) {
00658   // Allocate a new block close to the last one.
00659   std::string ErrMsg;
00660   sys::MemoryBlock *LastSlabPtr = LastSlab.base() ? &LastSlab : 0;
00661   sys::MemoryBlock B = sys::Memory::AllocateRWX(size, LastSlabPtr, &ErrMsg);
00662   if (B.base() == 0) {
00663     report_fatal_error("Allocation failed when allocating new memory in the"
00664                        " JIT\n" + Twine(ErrMsg));
00665   }
00666   LastSlab = B;
00667   ++NumSlabs;
00668   // Initialize the slab to garbage when debugging.
00669   if (PoisonMemory) {
00670     memset(B.base(), 0xCD, B.size());
00671   }
00672   return B;
00673 }
00674 
00675 /// CheckInvariants - For testing only.  Return "" if all internal invariants
00676 /// are preserved, and a helpful error message otherwise.  For free and
00677 /// allocated blocks, make sure that adding BlockSize gives a valid block.
00678 /// For free blocks, make sure they're in the free list and that their end of
00679 /// block size marker is correct.  This function should return an error before
00680 /// accessing bad memory.  This function is defined here instead of in
00681 /// JITMemoryManagerTest.cpp so that we don't have to expose all of the
00682 /// implementation details of DefaultJITMemoryManager.
00683 bool DefaultJITMemoryManager::CheckInvariants(std::string &ErrorStr) {
00684   raw_string_ostream Err(ErrorStr);
00685 
00686   // Construct a the set of FreeRangeHeader pointers so we can query it
00687   // efficiently.
00688   llvm::SmallPtrSet<MemoryRangeHeader*, 16> FreeHdrSet;
00689   FreeRangeHeader* FreeHead = FreeMemoryList;
00690   FreeRangeHeader* FreeRange = FreeHead;
00691 
00692   do {
00693     // Check that the free range pointer is in the blocks we've allocated.
00694     bool Found = false;
00695     for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
00696          E = CodeSlabs.end(); I != E && !Found; ++I) {
00697       char *Start = (char*)I->base();
00698       char *End = Start + I->size();
00699       Found = (Start <= (char*)FreeRange && (char*)FreeRange < End);
00700     }
00701     if (!Found) {
00702       Err << "Corrupt free list; points to " << FreeRange;
00703       return false;
00704     }
00705 
00706     if (FreeRange->Next->Prev != FreeRange) {
00707       Err << "Next and Prev pointers do not match.";
00708       return false;
00709     }
00710 
00711     // Otherwise, add it to the set.
00712     FreeHdrSet.insert(FreeRange);
00713     FreeRange = FreeRange->Next;
00714   } while (FreeRange != FreeHead);
00715 
00716   // Go over each block, and look at each MemoryRangeHeader.
00717   for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
00718        E = CodeSlabs.end(); I != E; ++I) {
00719     char *Start = (char*)I->base();
00720     char *End = Start + I->size();
00721 
00722     // Check each memory range.
00723     for (MemoryRangeHeader *Hdr = (MemoryRangeHeader*)Start, *LastHdr = NULL;
00724          Start <= (char*)Hdr && (char*)Hdr < End;
00725          Hdr = &Hdr->getBlockAfter()) {
00726       if (Hdr->ThisAllocated == 0) {
00727         // Check that this range is in the free list.
00728         if (!FreeHdrSet.count(Hdr)) {
00729           Err << "Found free header at " << Hdr << " that is not in free list.";
00730           return false;
00731         }
00732 
00733         // Now make sure the size marker at the end of the block is correct.
00734         uintptr_t *Marker = ((uintptr_t*)&Hdr->getBlockAfter()) - 1;
00735         if (!(Start <= (char*)Marker && (char*)Marker < End)) {
00736           Err << "Block size in header points out of current MemoryBlock.";
00737           return false;
00738         }
00739         if (Hdr->BlockSize != *Marker) {
00740           Err << "End of block size marker (" << *Marker << ") "
00741               << "and BlockSize (" << Hdr->BlockSize << ") don't match.";
00742           return false;
00743         }
00744       }
00745 
00746       if (LastHdr && LastHdr->ThisAllocated != Hdr->PrevAllocated) {
00747         Err << "Hdr->PrevAllocated (" << Hdr->PrevAllocated << ") != "
00748             << "LastHdr->ThisAllocated (" << LastHdr->ThisAllocated << ")";
00749         return false;
00750       } else if (!LastHdr && !Hdr->PrevAllocated) {
00751         Err << "The first header should have PrevAllocated true.";
00752         return false;
00753       }
00754 
00755       // Remember the last header.
00756       LastHdr = Hdr;
00757     }
00758   }
00759 
00760   // All invariants are preserved.
00761   return true;
00762 }
00763 
00764 //===----------------------------------------------------------------------===//
00765 // getPointerToNamedFunction() implementation.
00766 //===----------------------------------------------------------------------===//
00767 
00768 // AtExitHandlers - List of functions to call when the program exits,
00769 // registered with the atexit() library function.
00770 static std::vector<void (*)()> AtExitHandlers;
00771 
00772 /// runAtExitHandlers - Run any functions registered by the program's
00773 /// calls to atexit(3), which we intercept and store in
00774 /// AtExitHandlers.
00775 ///
00776 static void runAtExitHandlers() {
00777   while (!AtExitHandlers.empty()) {
00778     void (*Fn)() = AtExitHandlers.back();
00779     AtExitHandlers.pop_back();
00780     Fn();
00781   }
00782 }
00783 
00784 //===----------------------------------------------------------------------===//
00785 // Function stubs that are invoked instead of certain library calls
00786 //
00787 // Force the following functions to be linked in to anything that uses the
00788 // JIT. This is a hack designed to work around the all-too-clever Glibc
00789 // strategy of making these functions work differently when inlined vs. when
00790 // not inlined, and hiding their real definitions in a separate archive file
00791 // that the dynamic linker can't see. For more info, search for
00792 // 'libc_nonshared.a' on Google, or read http://llvm.org/PR274.
00793 #if defined(__linux__) && defined(__GLIBC__)
00794 /* stat functions are redirecting to __xstat with a version number.  On x86-64
00795  * linking with libc_nonshared.a and -Wl,--export-dynamic doesn't make 'stat'
00796  * available as an exported symbol, so we have to add it explicitly.
00797  */
00798 namespace {
00799 class StatSymbols {
00800 public:
00801   StatSymbols() {
00802     sys::DynamicLibrary::AddSymbol("stat", (void*)(intptr_t)stat);
00803     sys::DynamicLibrary::AddSymbol("fstat", (void*)(intptr_t)fstat);
00804     sys::DynamicLibrary::AddSymbol("lstat", (void*)(intptr_t)lstat);
00805     sys::DynamicLibrary::AddSymbol("stat64", (void*)(intptr_t)stat64);
00806     sys::DynamicLibrary::AddSymbol("\x1stat64", (void*)(intptr_t)stat64);
00807     sys::DynamicLibrary::AddSymbol("\x1open64", (void*)(intptr_t)open64);
00808     sys::DynamicLibrary::AddSymbol("\x1lseek64", (void*)(intptr_t)lseek64);
00809     sys::DynamicLibrary::AddSymbol("fstat64", (void*)(intptr_t)fstat64);
00810     sys::DynamicLibrary::AddSymbol("lstat64", (void*)(intptr_t)lstat64);
00811     sys::DynamicLibrary::AddSymbol("atexit", (void*)(intptr_t)atexit);
00812     sys::DynamicLibrary::AddSymbol("mknod", (void*)(intptr_t)mknod);
00813   }
00814 };
00815 }
00816 static StatSymbols initStatSymbols;
00817 #endif // __linux__
00818 
00819 // jit_exit - Used to intercept the "exit" library call.
00820 static void jit_exit(int Status) {
00821   runAtExitHandlers();   // Run atexit handlers...
00822   exit(Status);
00823 }
00824 
00825 // jit_atexit - Used to intercept the "atexit" library call.
00826 static int jit_atexit(void (*Fn)()) {
00827   AtExitHandlers.push_back(Fn);    // Take note of atexit handler...
00828   return 0;  // Always successful
00829 }
00830 
00831 static int jit_noop() {
00832   return 0;
00833 }
00834 
00835 //===----------------------------------------------------------------------===//
00836 //
00837 /// getPointerToNamedFunction - This method returns the address of the specified
00838 /// function by using the dynamic loader interface.  As such it is only useful
00839 /// for resolving library symbols, not code generated symbols.
00840 ///
00841 void *DefaultJITMemoryManager::getPointerToNamedFunction(const std::string &Name,
00842                                                          bool AbortOnFailure) {
00843   // Check to see if this is one of the functions we want to intercept.  Note,
00844   // we cast to intptr_t here to silence a -pedantic warning that complains
00845   // about casting a function pointer to a normal pointer.
00846   if (Name == "exit") return (void*)(intptr_t)&jit_exit;
00847   if (Name == "atexit") return (void*)(intptr_t)&jit_atexit;
00848 
00849   // We should not invoke parent's ctors/dtors from generated main()!
00850   // On Mingw and Cygwin, the symbol __main is resolved to
00851   // callee's(eg. tools/lli) one, to invoke wrong duplicated ctors
00852   // (and register wrong callee's dtors with atexit(3)).
00853   // We expect ExecutionEngine::runStaticConstructorsDestructors()
00854   // is called before ExecutionEngine::runFunctionAsMain() is called.
00855   if (Name == "__main") return (void*)(intptr_t)&jit_noop;
00856 
00857   const char *NameStr = Name.c_str();
00858   // If this is an asm specifier, skip the sentinal.
00859   if (NameStr[0] == 1) ++NameStr;
00860 
00861   // If it's an external function, look it up in the process image...
00862   void *Ptr = sys::DynamicLibrary::SearchForAddressOfSymbol(NameStr);
00863   if (Ptr) return Ptr;
00864 
00865   // If it wasn't found and if it starts with an underscore ('_') character,
00866   // try again without the underscore.
00867   if (NameStr[0] == '_') {
00868     Ptr = sys::DynamicLibrary::SearchForAddressOfSymbol(NameStr+1);
00869     if (Ptr) return Ptr;
00870   }
00871 
00872   // Darwin/PPC adds $LDBLStub suffixes to various symbols like printf.  These
00873   // are references to hidden visibility symbols that dlsym cannot resolve.
00874   // If we have one of these, strip off $LDBLStub and try again.
00875 #if defined(__APPLE__) && defined(__ppc__)
00876   if (Name.size() > 9 && Name[Name.size()-9] == '$' &&
00877       memcmp(&Name[Name.size()-8], "LDBLStub", 8) == 0) {
00878     // First try turning $LDBLStub into $LDBL128. If that fails, strip it off.
00879     // This mirrors logic in libSystemStubs.a.
00880     std::string Prefix = std::string(Name.begin(), Name.end()-9);
00881     if (void *Ptr = getPointerToNamedFunction(Prefix+"$LDBL128", false))
00882       return Ptr;
00883     if (void *Ptr = getPointerToNamedFunction(Prefix, false))
00884       return Ptr;
00885   }
00886 #endif
00887 
00888   if (AbortOnFailure) {
00889     report_fatal_error("Program used external function '"+Name+
00890                       "' which could not be resolved!");
00891   }
00892   return 0;
00893 }
00894 
00895 
00896 
00897 JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() {
00898   return new DefaultJITMemoryManager();
00899 }
00900 
00901 const size_t DefaultJITMemoryManager::DefaultCodeSlabSize;
00902 const size_t DefaultJITMemoryManager::DefaultSlabSize;
00903 const size_t DefaultJITMemoryManager::DefaultSizeThreshold;