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