contrib/llvm/lib/ExecutionEngine/JIT/JITMemoryManager.cpp

   1 //===-- JITMemoryManager.cpp - Memory Allocator for JIT'd code ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the DefaultJITMemoryManager class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "jit"
  15 #include "llvm/ExecutionEngine/JITMemoryManager.h"
  16 #include "llvm/ADT/SmallPtrSet.h"
  17 #include "llvm/ADT/Statistic.h"
  18 #include "llvm/ADT/Twine.h"
  19 #include "llvm/Config/config.h"
  20 #include "llvm/IR/GlobalValue.h"
  21 #include "llvm/Support/Allocator.h"
  22 #include "llvm/Support/Compiler.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/DynamicLibrary.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26 #include "llvm/Support/Memory.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include <cassert>
  29 #include <climits>
  30 #include <cstring>
  31 #include <vector>
  32
  33 #if defined(__linux__)
  34 #if defined(HAVE_SYS_STAT_H)
  35 #include <sys/stat.h>
  36 #endif
  37 #include <fcntl.h>
  38 #include <unistd.h>
  39 #endif
  40
  41 using namespace llvm;
  42
  43 STATISTIC(NumSlabs, "Number of slabs of memory allocated by the JIT");
  44
  45 JITMemoryManager::~JITMemoryManager() {}
  46
  47 //===----------------------------------------------------------------------===//
  48 // Memory Block Implementation.
  49 //===----------------------------------------------------------------------===//
  50
  51 namespace {
  52   /// MemoryRangeHeader - For a range of memory, this is the header that we put
  53   /// on the block of memory.  It is carefully crafted to be one word of memory.
  54   /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader
  55   /// which starts with this.
  56   struct FreeRangeHeader;
  57   struct MemoryRangeHeader {
  58     /// ThisAllocated - This is true if this block is currently allocated.  If
  59     /// not, this can be converted to a FreeRangeHeader.
  60     unsigned ThisAllocated : 1;
  61
  62     /// PrevAllocated - Keep track of whether the block immediately before us is
  63     /// allocated.  If not, the word immediately before this header is the size
  64     /// of the previous block.
  65     unsigned PrevAllocated : 1;
  66
  67     /// BlockSize - This is the size in bytes of this memory block,
  68     /// including this header.
  69     uintptr_t BlockSize : (sizeof(intptr_t)*CHAR_BIT - 2);
  70
  71
  72     /// getBlockAfter - Return the memory block immediately after this one.
  73     ///
  74     MemoryRangeHeader &getBlockAfter() const {
  75       return *reinterpret_cast<MemoryRangeHeader *>(
  76                 reinterpret_cast<char*>(
  77                   const_cast<MemoryRangeHeader *>(this))+BlockSize);
  78     }
  79
  80     /// getFreeBlockBefore - If the block before this one is free, return it,
  81     /// otherwise return null.
  82     FreeRangeHeader *getFreeBlockBefore() const {
  83       if (PrevAllocated) return 0;
  84       intptr_t PrevSize = reinterpret_cast<intptr_t *>(
  85                             const_cast<MemoryRangeHeader *>(this))[-1];
  86       return reinterpret_cast<FreeRangeHeader *>(
  87                reinterpret_cast<char*>(
  88                  const_cast<MemoryRangeHeader *>(this))-PrevSize);
  89     }
  90
  91     /// FreeBlock - Turn an allocated block into a free block, adjusting
  92     /// bits in the object headers, and adding an end of region memory block.
  93     FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList);
  94
  95     /// TrimAllocationToSize - If this allocated block is significantly larger
  96     /// than NewSize, split it into two pieces (where the former is NewSize
  97     /// bytes, including the header), and add the new block to the free list.
  98     FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList,
  99                                           uint64_t NewSize);
 100   };
 101
 102   /// FreeRangeHeader - For a memory block that isn't already allocated, this
 103   /// keeps track of the current block and has a pointer to the next free block.
 104   /// Free blocks are kept on a circularly linked list.
 105   struct FreeRangeHeader : public MemoryRangeHeader {
 106     FreeRangeHeader *Prev;
 107     FreeRangeHeader *Next;
 108
 109     /// getMinBlockSize - Get the minimum size for a memory block.  Blocks
 110     /// smaller than this size cannot be created.
 111     static unsigned getMinBlockSize() {
 112       return sizeof(FreeRangeHeader)+sizeof(intptr_t);
 113     }
 114
 115     /// SetEndOfBlockSizeMarker - The word at the end of every free block is
 116     /// known to be the size of the free block.  Set it for this block.
 117     void SetEndOfBlockSizeMarker() {
 118       void *EndOfBlock = (char*)this + BlockSize;
 119       ((intptr_t *)EndOfBlock)[-1] = BlockSize;
 120     }
 121
 122     FreeRangeHeader *RemoveFromFreeList() {
 123       assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
 124       Next->Prev = Prev;
 125       return Prev->Next = Next;
 126     }
 127
 128     void AddToFreeList(FreeRangeHeader *FreeList) {
 129       Next = FreeList;
 130       Prev = FreeList->Prev;
 131       Prev->Next = this;
 132       Next->Prev = this;
 133     }
 134
 135     /// GrowBlock - The block after this block just got deallocated.  Merge it
 136     /// into the current block.
 137     void GrowBlock(uintptr_t NewSize);
 138
 139     /// AllocateBlock - Mark this entire block allocated, updating freelists
 140     /// etc.  This returns a pointer to the circular free-list.
 141     FreeRangeHeader *AllocateBlock();
 142   };
 143 }
 144
 145
 146 /// AllocateBlock - Mark this entire block allocated, updating freelists
 147 /// etc.  This returns a pointer to the circular free-list.
 148 FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
 149   assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
 150          "Cannot allocate an allocated block!");
 151   // Mark this block allocated.
 152   ThisAllocated = 1;
 153   getBlockAfter().PrevAllocated = 1;
 154
 155   // Remove it from the free list.
 156   return RemoveFromFreeList();
 157 }
 158
 159 /// FreeBlock - Turn an allocated block into a free block, adjusting
 160 /// bits in the object headers, and adding an end of region memory block.
 161 /// If possible, coalesce this block with neighboring blocks.  Return the
 162 /// FreeRangeHeader to allocate from.
 163 FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) {
 164   MemoryRangeHeader *FollowingBlock = &getBlockAfter();
 165   assert(ThisAllocated && "This block is already free!");
 166   assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
 167
 168   FreeRangeHeader *FreeListToReturn = FreeList;
 169
 170   // If the block after this one is free, merge it into this block.
 171   if (!FollowingBlock->ThisAllocated) {
 172     FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
 173     // "FreeList" always needs to be a valid free block.  If we're about to
 174     // coalesce with it, update our notion of what the free list is.
 175     if (&FollowingFreeBlock == FreeList) {
 176       FreeList = FollowingFreeBlock.Next;
 177       FreeListToReturn = 0;
 178       assert(&FollowingFreeBlock != FreeList && "No tombstone block?");
 179     }
 180     FollowingFreeBlock.RemoveFromFreeList();
 181
 182     // Include the following block into this one.
 183     BlockSize += FollowingFreeBlock.BlockSize;
 184     FollowingBlock = &FollowingFreeBlock.getBlockAfter();
 185
 186     // Tell the block after the block we are coalescing that this block is
 187     // allocated.
 188     FollowingBlock->PrevAllocated = 1;
 189   }
 190
 191   assert(FollowingBlock->ThisAllocated && "Missed coalescing?");
 192
 193   if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
 194     PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
 195     return FreeListToReturn ? FreeListToReturn : PrevFreeBlock;
 196   }
 197
 198   // Otherwise, mark this block free.
 199   FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
 200   FollowingBlock->PrevAllocated = 0;
 201   FreeBlock.ThisAllocated = 0;
 202
 203   // Link this into the linked list of free blocks.
 204   FreeBlock.AddToFreeList(FreeList);
 205
 206   // Add a marker at the end of the block, indicating the size of this free
 207   // block.
 208   FreeBlock.SetEndOfBlockSizeMarker();
 209   return FreeListToReturn ? FreeListToReturn : &FreeBlock;
 210 }
 211
 212 /// GrowBlock - The block after this block just got deallocated.  Merge it
 213 /// into the current block.
 214 void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
 215   assert(NewSize > BlockSize && "Not growing block?");
 216   BlockSize = NewSize;
 217   SetEndOfBlockSizeMarker();
 218   getBlockAfter().PrevAllocated = 0;
 219 }
 220
 221 /// TrimAllocationToSize - If this allocated block is significantly larger
 222 /// than NewSize, split it into two pieces (where the former is NewSize
 223 /// bytes, including the header), and add the new block to the free list.
 224 FreeRangeHeader *MemoryRangeHeader::
 225 TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
 226   assert(ThisAllocated && getBlockAfter().PrevAllocated &&
 227          "Cannot deallocate part of an allocated block!");
 228
 229   // Don't allow blocks to be trimmed below minimum required size
 230   NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize);
 231
 232   // Round up size for alignment of header.
 233   unsigned HeaderAlign = __alignof(FreeRangeHeader);
 234   NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
 235
 236   // Size is now the size of the block we will remove from the start of the
 237   // current block.
 238   assert(NewSize <= BlockSize &&
 239          "Allocating more space from this block than exists!");
 240
 241   // If splitting this block will cause the remainder to be too small, do not
 242   // split the block.
 243   if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
 244     return FreeList;
 245
 246   // Otherwise, we splice the required number of bytes out of this block, form
 247   // a new block immediately after it, then mark this block allocated.
 248   MemoryRangeHeader &FormerNextBlock = getBlockAfter();
 249
 250   // Change the size of this block.
 251   BlockSize = NewSize;
 252
 253   // Get the new block we just sliced out and turn it into a free block.
 254   FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
 255   NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
 256   NewNextBlock.ThisAllocated = 0;
 257   NewNextBlock.PrevAllocated = 1;
 258   NewNextBlock.SetEndOfBlockSizeMarker();
 259   FormerNextBlock.PrevAllocated = 0;
 260   NewNextBlock.AddToFreeList(FreeList);
 261   return &NewNextBlock;
 262 }
 263
 264 //===----------------------------------------------------------------------===//
 265 // Memory Block Implementation.
 266 //===----------------------------------------------------------------------===//
 267
 268 namespace {
 269
 270   class DefaultJITMemoryManager;
 271
 272   class JITSlabAllocator : public SlabAllocator {
 273     DefaultJITMemoryManager &JMM;
 274   public:
 275     JITSlabAllocator(DefaultJITMemoryManager &jmm) : JMM(jmm) { }
 276     virtual ~JITSlabAllocator() { }
 277     virtual MemSlab *Allocate(size_t Size);
 278     virtual void Deallocate(MemSlab *Slab);
 279   };
 280
 281   /// DefaultJITMemoryManager - Manage memory for the JIT code generation.
 282   /// This splits a large block of MAP_NORESERVE'd memory into two
 283   /// sections, one for function stubs, one for the functions themselves.  We
 284   /// have to do this because we may need to emit a function stub while in the
 285   /// middle of emitting a function, and we don't know how large the function we
 286   /// are emitting is.
 287   class DefaultJITMemoryManager : public JITMemoryManager {
 288
 289     // Whether to poison freed memory.
 290     bool PoisonMemory;
 291
 292     /// LastSlab - This points to the last slab allocated and is used as the
 293     /// NearBlock parameter to AllocateRWX so that we can attempt to lay out all
 294     /// stubs, data, and code contiguously in memory.  In general, however, this
 295     /// is not possible because the NearBlock parameter is ignored on Windows
 296     /// platforms and even on Unix it works on a best-effort pasis.
 297     sys::MemoryBlock LastSlab;
 298
 299     // Memory slabs allocated by the JIT.  We refer to them as slabs so we don't
 300     // confuse them with the blocks of memory described above.
 301     std::vector<sys::MemoryBlock> CodeSlabs;
 302     JITSlabAllocator BumpSlabAllocator;
 303     BumpPtrAllocator StubAllocator;
 304     BumpPtrAllocator DataAllocator;
 305
 306     // Circular list of free blocks.
 307     FreeRangeHeader *FreeMemoryList;
 308
 309     // When emitting code into a memory block, this is the block.
 310     MemoryRangeHeader *CurBlock;
 311
 312     uint8_t *GOTBase;     // Target Specific reserved memory
 313   public:
 314     DefaultJITMemoryManager();
 315     ~DefaultJITMemoryManager();
 316
 317     /// allocateNewSlab - Allocates a new MemoryBlock and remembers it as the
 318     /// last slab it allocated, so that subsequent allocations follow it.
 319     sys::MemoryBlock allocateNewSlab(size_t size);
 320
 321     /// DefaultCodeSlabSize - When we have to go map more memory, we allocate at
 322     /// least this much unless more is requested.
 323     static const size_t DefaultCodeSlabSize;
 324
 325     /// DefaultSlabSize - Allocate data into slabs of this size unless we get
 326     /// an allocation above SizeThreshold.
 327     static const size_t DefaultSlabSize;
 328
 329     /// DefaultSizeThreshold - For any allocation larger than this threshold, we
 330     /// should allocate a separate slab.
 331     static const size_t DefaultSizeThreshold;
 332
 333     /// getPointerToNamedFunction - This method returns the address of the
 334     /// specified function by using the dlsym function call.
 335     virtual void *getPointerToNamedFunction(const std::string &Name,
 336                                             bool AbortOnFailure = true);
 337
 338     void AllocateGOT();
 339
 340     // Testing methods.
 341     virtual bool CheckInvariants(std::string &ErrorStr);
 342     size_t GetDefaultCodeSlabSize() { return DefaultCodeSlabSize; }
 343     size_t GetDefaultDataSlabSize() { return DefaultSlabSize; }
 344     size_t GetDefaultStubSlabSize() { return DefaultSlabSize; }
 345     unsigned GetNumCodeSlabs() { return CodeSlabs.size(); }
 346     unsigned GetNumDataSlabs() { return DataAllocator.GetNumSlabs(); }
 347     unsigned GetNumStubSlabs() { return StubAllocator.GetNumSlabs(); }
 348
 349     /// startFunctionBody - When a function starts, allocate a block of free
 350     /// executable memory, returning a pointer to it and its actual size.
 351     uint8_t *startFunctionBody(const Function *F, uintptr_t &ActualSize) {
 352
 353       FreeRangeHeader* candidateBlock = FreeMemoryList;
 354       FreeRangeHeader* head = FreeMemoryList;
 355       FreeRangeHeader* iter = head->Next;
 356
 357       uintptr_t largest = candidateBlock->BlockSize;
 358
 359       // Search for the largest free block
 360       while (iter != head) {
 361         if (iter->BlockSize > largest) {
 362           largest = iter->BlockSize;
 363           candidateBlock = iter;
 364         }
 365         iter = iter->Next;
 366       }
 367
 368       largest = largest - sizeof(MemoryRangeHeader);
 369
 370       // If this block isn't big enough for the allocation desired, allocate
 371       // another block of memory and add it to the free list.
 372       if (largest < ActualSize ||
 373           largest <= FreeRangeHeader::getMinBlockSize()) {
 374         DEBUG(dbgs() << "JIT: Allocating another slab of memory for function.");
 375         candidateBlock = allocateNewCodeSlab((size_t)ActualSize);
 376       }
 377
 378       // Select this candidate block for allocation
 379       CurBlock = candidateBlock;
 380
 381       // Allocate the entire memory block.
 382       FreeMemoryList = candidateBlock->AllocateBlock();
 383       ActualSize = CurBlock->BlockSize - sizeof(MemoryRangeHeader);
 384       return (uint8_t *)(CurBlock + 1);
 385     }
 386
 387     /// allocateNewCodeSlab - Helper method to allocate a new slab of code
 388     /// memory from the OS and add it to the free list.  Returns the new
 389     /// FreeRangeHeader at the base of the slab.
 390     FreeRangeHeader *allocateNewCodeSlab(size_t MinSize) {
 391       // If the user needs at least MinSize free memory, then we account for
 392       // two MemoryRangeHeaders: the one in the user's block, and the one at the
 393       // end of the slab.
 394       size_t PaddedMin = MinSize + 2 * sizeof(MemoryRangeHeader);
 395       size_t SlabSize = std::max(DefaultCodeSlabSize, PaddedMin);
 396       sys::MemoryBlock B = allocateNewSlab(SlabSize);
 397       CodeSlabs.push_back(B);
 398       char *MemBase = (char*)(B.base());
 399
 400       // Put a tiny allocated block at the end of the memory chunk, so when
 401       // FreeBlock calls getBlockAfter it doesn't fall off the end.
 402       MemoryRangeHeader *EndBlock =
 403           (MemoryRangeHeader*)(MemBase + B.size()) - 1;
 404       EndBlock->ThisAllocated = 1;
 405       EndBlock->PrevAllocated = 0;
 406       EndBlock->BlockSize = sizeof(MemoryRangeHeader);
 407
 408       // Start out with a vast new block of free memory.
 409       FreeRangeHeader *NewBlock = (FreeRangeHeader*)MemBase;
 410       NewBlock->ThisAllocated = 0;
 411       // Make sure getFreeBlockBefore doesn't look into unmapped memory.
 412       NewBlock->PrevAllocated = 1;
 413       NewBlock->BlockSize = (uintptr_t)EndBlock - (uintptr_t)NewBlock;
 414       NewBlock->SetEndOfBlockSizeMarker();
 415       NewBlock->AddToFreeList(FreeMemoryList);
 416
 417       assert(NewBlock->BlockSize - sizeof(MemoryRangeHeader) >= MinSize &&
 418              "The block was too small!");
 419       return NewBlock;
 420     }
 421
 422     /// endFunctionBody - The function F is now allocated, and takes the memory
 423     /// in the range [FunctionStart,FunctionEnd).
 424     void endFunctionBody(const Function *F, uint8_t *FunctionStart,
 425                          uint8_t *FunctionEnd) {
 426       assert(FunctionEnd > FunctionStart);
 427       assert(FunctionStart == (uint8_t *)(CurBlock+1) &&
 428              "Mismatched function start/end!");
 429
 430       uintptr_t BlockSize = FunctionEnd - (uint8_t *)CurBlock;
 431
 432       // Release the memory at the end of this block that isn't needed.
 433       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
 434     }
 435
 436     /// allocateSpace - Allocate a memory block of the given size.  This method
 437     /// cannot be called between calls to startFunctionBody and endFunctionBody.
 438     uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) {
 439       CurBlock = FreeMemoryList;
 440       FreeMemoryList = FreeMemoryList->AllocateBlock();
 441
 442       uint8_t *result = (uint8_t *)(CurBlock + 1);
 443
 444       if (Alignment == 0) Alignment = 1;
 445       result = (uint8_t*)(((intptr_t)result+Alignment-1) &
 446                ~(intptr_t)(Alignment-1));
 447
 448       uintptr_t BlockSize = result + Size - (uint8_t *)CurBlock;
 449       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
 450
 451       return result;
 452     }
 453
 454     /// allocateStub - Allocate memory for a function stub.
 455     uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize,
 456                           unsigned Alignment) {
 457       return (uint8_t*)StubAllocator.Allocate(StubSize, Alignment);
 458     }
 459
 460     /// allocateGlobal - Allocate memory for a global.
 461     uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) {
 462       return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
 463     }
 464
 465     /// allocateCodeSection - Allocate memory for a code section.
 466     uint8_t *allocateCodeSection(uintptr_t Size, unsigned Alignment,
 467                                  unsigned SectionID, StringRef SectionName) {
 468       // Grow the required block size to account for the block header
 469       Size += sizeof(*CurBlock);
 470
 471       // Alignment handling.
 472       if (!Alignment)
 473         Alignment = 16;
 474       Size += Alignment - 1;
 475
 476       FreeRangeHeader* candidateBlock = FreeMemoryList;
 477       FreeRangeHeader* head = FreeMemoryList;
 478       FreeRangeHeader* iter = head->Next;
 479
 480       uintptr_t largest = candidateBlock->BlockSize;
 481
 482       // Search for the largest free block.
 483       while (iter != head) {
 484         if (iter->BlockSize > largest) {
 485           largest = iter->BlockSize;
 486           candidateBlock = iter;
 487         }
 488         iter = iter->Next;
 489       }
 490
 491       largest = largest - sizeof(MemoryRangeHeader);
 492
 493       // If this block isn't big enough for the allocation desired, allocate
 494       // another block of memory and add it to the free list.
 495       if (largest < Size || largest <= FreeRangeHeader::getMinBlockSize()) {
 496         DEBUG(dbgs() << "JIT: Allocating another slab of memory for function.");
 497         candidateBlock = allocateNewCodeSlab((size_t)Size);
 498       }
 499
 500       // Select this candidate block for allocation
 501       CurBlock = candidateBlock;
 502
 503       // Allocate the entire memory block.
 504       FreeMemoryList = candidateBlock->AllocateBlock();
 505       // Release the memory at the end of this block that isn't needed.
 506       FreeMemoryList = CurBlock->TrimAllocationToSize(FreeMemoryList, Size);
 507       uintptr_t unalignedAddr = (uintptr_t)CurBlock + sizeof(*CurBlock);
 508       return (uint8_t*)RoundUpToAlignment((uint64_t)unalignedAddr, Alignment);
 509     }
 510
 511     /// allocateDataSection - Allocate memory for a data section.
 512     uint8_t *allocateDataSection(uintptr_t Size, unsigned Alignment,
 513                                  unsigned SectionID, StringRef SectionName,
 514                                  bool IsReadOnly) {
 515       return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
 516     }
 517
 518     bool finalizeMemory(std::string *ErrMsg) {
 519       return false;
 520     }
 521
 522     uint8_t *getGOTBase() const {
 523       return GOTBase;
 524     }
 525
 526     void deallocateBlock(void *Block) {
 527       // Find the block that is allocated for this function.
 528       MemoryRangeHeader *MemRange = static_cast<MemoryRangeHeader*>(Block) - 1;
 529       assert(MemRange->ThisAllocated && "Block isn't allocated!");
 530
 531       // Fill the buffer with garbage!
 532       if (PoisonMemory) {
 533         memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
 534       }
 535
 536       // Free the memory.
 537       FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
 538     }
 539
 540     /// deallocateFunctionBody - Deallocate all memory for the specified
 541     /// function body.
 542     void deallocateFunctionBody(void *Body) {
 543       if (Body) deallocateBlock(Body);
 544     }
 545
 546     /// setMemoryWritable - When code generation is in progress,
 547     /// the code pages may need permissions changed.
 548     void setMemoryWritable()
 549     {
 550       for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
 551         sys::Memory::setWritable(CodeSlabs[i]);
 552     }
 553     /// setMemoryExecutable - When code generation is done and we're ready to
 554     /// start execution, the code pages may need permissions changed.
 555     void setMemoryExecutable()
 556     {
 557       for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
 558         sys::Memory::setExecutable(CodeSlabs[i]);
 559     }
 560
 561     /// setPoisonMemory - Controls whether we write garbage over freed memory.
 562     ///
 563     void setPoisonMemory(bool poison) {
 564       PoisonMemory = poison;
 565     }
 566   };
 567 }
 568
 569 MemSlab *JITSlabAllocator::Allocate(size_t Size) {
 570   sys::MemoryBlock B = JMM.allocateNewSlab(Size);
 571   MemSlab *Slab = (MemSlab*)B.base();
 572   Slab->Size = B.size();
 573   Slab->NextPtr = 0;
 574   return Slab;
 575 }
 576
 577 void JITSlabAllocator::Deallocate(MemSlab *Slab) {
 578   sys::MemoryBlock B(Slab, Slab->Size);
 579   sys::Memory::ReleaseRWX(B);
 580 }
 581
 582 DefaultJITMemoryManager::DefaultJITMemoryManager()
 583   :
 584 #ifdef NDEBUG
 585     PoisonMemory(false),
 586 #else
 587     PoisonMemory(true),
 588 #endif
 589     LastSlab(0, 0),
 590     BumpSlabAllocator(*this),
 591     StubAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator),
 592     DataAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator) {
 593
 594   // Allocate space for code.
 595   sys::MemoryBlock MemBlock = allocateNewSlab(DefaultCodeSlabSize);
 596   CodeSlabs.push_back(MemBlock);
 597   uint8_t *MemBase = (uint8_t*)MemBlock.base();
 598
 599   // We set up the memory chunk with 4 mem regions, like this:
 600   //  [ START
 601   //    [ Free      #0 ] -> Large space to allocate functions from.
 602   //    [ Allocated #1 ] -> Tiny space to separate regions.
 603   //    [ Free      #2 ] -> Tiny space so there is always at least 1 free block.
 604   //    [ Allocated #3 ] -> Tiny space to prevent looking past end of block.
 605   //  END ]
 606   //
 607   // The last three blocks are never deallocated or touched.
 608
 609   // Add MemoryRangeHeader to the end of the memory region, indicating that
 610   // the space after the block of memory is allocated.  This is block #3.
 611   MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
 612   Mem3->ThisAllocated = 1;
 613   Mem3->PrevAllocated = 0;
 614   Mem3->BlockSize     = sizeof(MemoryRangeHeader);
 615
 616   /// Add a tiny free region so that the free list always has one entry.
 617   FreeRangeHeader *Mem2 =
 618     (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
 619   Mem2->ThisAllocated = 0;
 620   Mem2->PrevAllocated = 1;
 621   Mem2->BlockSize     = FreeRangeHeader::getMinBlockSize();
 622   Mem2->SetEndOfBlockSizeMarker();
 623   Mem2->Prev = Mem2;   // Mem2 *is* the free list for now.
 624   Mem2->Next = Mem2;
 625
 626   /// Add a tiny allocated region so that Mem2 is never coalesced away.
 627   MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
 628   Mem1->ThisAllocated = 1;
 629   Mem1->PrevAllocated = 0;
 630   Mem1->BlockSize     = sizeof(MemoryRangeHeader);
 631
 632   // Add a FreeRangeHeader to the start of the function body region, indicating
 633   // that the space is free.  Mark the previous block allocated so we never look
 634   // at it.
 635   FreeRangeHeader *Mem0 = (FreeRangeHeader*)MemBase;
 636   Mem0->ThisAllocated = 0;
 637   Mem0->PrevAllocated = 1;
 638   Mem0->BlockSize = (char*)Mem1-(char*)Mem0;
 639   Mem0->SetEndOfBlockSizeMarker();
 640   Mem0->AddToFreeList(Mem2);
 641
 642   // Start out with the freelist pointing to Mem0.
 643   FreeMemoryList = Mem0;
 644
 645   GOTBase = NULL;
 646 }
 647
 648 void DefaultJITMemoryManager::AllocateGOT() {
 649   assert(GOTBase == 0 && "Cannot allocate the got multiple times");
 650   GOTBase = new uint8_t[sizeof(void*) * 8192];
 651   HasGOT = true;
 652 }
 653
 654 DefaultJITMemoryManager::~DefaultJITMemoryManager() {
 655   for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
 656     sys::Memory::ReleaseRWX(CodeSlabs[i]);
 657
 658   delete[] GOTBase;
 659 }
 660
 661 sys::MemoryBlock DefaultJITMemoryManager::allocateNewSlab(size_t size) {
 662   // Allocate a new block close to the last one.
 663   std::string ErrMsg;
 664   sys::MemoryBlock *LastSlabPtr = LastSlab.base() ? &LastSlab : 0;
 665   sys::MemoryBlock B = sys::Memory::AllocateRWX(size, LastSlabPtr, &ErrMsg);
 666   if (B.base() == 0) {
 667     report_fatal_error("Allocation failed when allocating new memory in the"
 668                        " JIT\n" + Twine(ErrMsg));
 669   }
 670   LastSlab = B;
 671   ++NumSlabs;
 672   // Initialize the slab to garbage when debugging.
 673   if (PoisonMemory) {
 674     memset(B.base(), 0xCD, B.size());
 675   }
 676   return B;
 677 }
 678
 679 /// CheckInvariants - For testing only.  Return "" if all internal invariants
 680 /// are preserved, and a helpful error message otherwise.  For free and
 681 /// allocated blocks, make sure that adding BlockSize gives a valid block.
 682 /// For free blocks, make sure they're in the free list and that their end of
 683 /// block size marker is correct.  This function should return an error before
 684 /// accessing bad memory.  This function is defined here instead of in
 685 /// JITMemoryManagerTest.cpp so that we don't have to expose all of the
 686 /// implementation details of DefaultJITMemoryManager.
 687 bool DefaultJITMemoryManager::CheckInvariants(std::string &ErrorStr) {
 688   raw_string_ostream Err(ErrorStr);
 689
 690   // Construct a the set of FreeRangeHeader pointers so we can query it
 691   // efficiently.
 692   llvm::SmallPtrSet<MemoryRangeHeader*, 16> FreeHdrSet;
 693   FreeRangeHeader* FreeHead = FreeMemoryList;
 694   FreeRangeHeader* FreeRange = FreeHead;
 695
 696   do {
 697     // Check that the free range pointer is in the blocks we've allocated.
 698     bool Found = false;
 699     for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
 700          E = CodeSlabs.end(); I != E && !Found; ++I) {
 701       char *Start = (char*)I->base();
 702       char *End = Start + I->size();
 703       Found = (Start <= (char*)FreeRange && (char*)FreeRange < End);
 704     }
 705     if (!Found) {
 706       Err << "Corrupt free list; points to " << FreeRange;
 707       return false;
 708     }
 709
 710     if (FreeRange->Next->Prev != FreeRange) {
 711       Err << "Next and Prev pointers do not match.";
 712       return false;
 713     }
 714
 715     // Otherwise, add it to the set.
 716     FreeHdrSet.insert(FreeRange);
 717     FreeRange = FreeRange->Next;
 718   } while (FreeRange != FreeHead);
 719
 720   // Go over each block, and look at each MemoryRangeHeader.
 721   for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
 722        E = CodeSlabs.end(); I != E; ++I) {
 723     char *Start = (char*)I->base();
 724     char *End = Start + I->size();
 725
 726     // Check each memory range.
 727     for (MemoryRangeHeader *Hdr = (MemoryRangeHeader*)Start, *LastHdr = NULL;
 728          Start <= (char*)Hdr && (char*)Hdr < End;
 729          Hdr = &Hdr->getBlockAfter()) {
 730       if (Hdr->ThisAllocated == 0) {
 731         // Check that this range is in the free list.
 732         if (!FreeHdrSet.count(Hdr)) {
 733           Err << "Found free header at " << Hdr << " that is not in free list.";
 734           return false;
 735         }
 736
 737         // Now make sure the size marker at the end of the block is correct.
 738         uintptr_t *Marker = ((uintptr_t*)&Hdr->getBlockAfter()) - 1;
 739         if (!(Start <= (char*)Marker && (char*)Marker < End)) {
 740           Err << "Block size in header points out of current MemoryBlock.";
 741           return false;
 742         }
 743         if (Hdr->BlockSize != *Marker) {
 744           Err << "End of block size marker (" << *Marker << ") "
 745               << "and BlockSize (" << Hdr->BlockSize << ") don't match.";
 746           return false;
 747         }
 748       }
 749
 750       if (LastHdr && LastHdr->ThisAllocated != Hdr->PrevAllocated) {
 751         Err << "Hdr->PrevAllocated (" << Hdr->PrevAllocated << ") != "
 752             << "LastHdr->ThisAllocated (" << LastHdr->ThisAllocated << ")";
 753         return false;
 754       } else if (!LastHdr && !Hdr->PrevAllocated) {
 755         Err << "The first header should have PrevAllocated true.";
 756         return false;
 757       }
 758
 759       // Remember the last header.
 760       LastHdr = Hdr;
 761     }
 762   }
 763
 764   // All invariants are preserved.
 765   return true;
 766 }
 767
 768 //===----------------------------------------------------------------------===//
 769 // getPointerToNamedFunction() implementation.
 770 //===----------------------------------------------------------------------===//
 771
 772 // AtExitHandlers - List of functions to call when the program exits,
 773 // registered with the atexit() library function.
 774 static std::vector<void (*)()> AtExitHandlers;
 775
 776 /// runAtExitHandlers - Run any functions registered by the program's
 777 /// calls to atexit(3), which we intercept and store in
 778 /// AtExitHandlers.
 779 ///
 780 static void runAtExitHandlers() {
 781   while (!AtExitHandlers.empty()) {
 782     void (*Fn)() = AtExitHandlers.back();
 783     AtExitHandlers.pop_back();
 784     Fn();
 785   }
 786 }
 787
 788 //===----------------------------------------------------------------------===//
 789 // Function stubs that are invoked instead of certain library calls
 790 //
 791 // Force the following functions to be linked in to anything that uses the
 792 // JIT. This is a hack designed to work around the all-too-clever Glibc
 793 // strategy of making these functions work differently when inlined vs. when
 794 // not inlined, and hiding their real definitions in a separate archive file
 795 // that the dynamic linker can't see. For more info, search for
 796 // 'libc_nonshared.a' on Google, or read http://llvm.org/PR274.
 797 #if defined(__linux__) && defined(__GLIBC__)
 798 /* stat functions are redirecting to __xstat with a version number.  On x86-64
 799  * linking with libc_nonshared.a and -Wl,--export-dynamic doesn't make 'stat'
 800  * available as an exported symbol, so we have to add it explicitly.
 801  */
 802 namespace {
 803 class StatSymbols {
 804 public:
 805   StatSymbols() {
 806     sys::DynamicLibrary::AddSymbol("stat", (void*)(intptr_t)stat);
 807     sys::DynamicLibrary::AddSymbol("fstat", (void*)(intptr_t)fstat);
 808     sys::DynamicLibrary::AddSymbol("lstat", (void*)(intptr_t)lstat);
 809     sys::DynamicLibrary::AddSymbol("stat64", (void*)(intptr_t)stat64);
 810     sys::DynamicLibrary::AddSymbol("\x1stat64", (void*)(intptr_t)stat64);
 811     sys::DynamicLibrary::AddSymbol("\x1open64", (void*)(intptr_t)open64);
 812     sys::DynamicLibrary::AddSymbol("\x1lseek64", (void*)(intptr_t)lseek64);
 813     sys::DynamicLibrary::AddSymbol("fstat64", (void*)(intptr_t)fstat64);
 814     sys::DynamicLibrary::AddSymbol("lstat64", (void*)(intptr_t)lstat64);
 815     sys::DynamicLibrary::AddSymbol("atexit", (void*)(intptr_t)atexit);
 816     sys::DynamicLibrary::AddSymbol("mknod", (void*)(intptr_t)mknod);
 817   }
 818 };
 819 }
 820 static StatSymbols initStatSymbols;
 821 #endif // __linux__
 822
 823 // jit_exit - Used to intercept the "exit" library call.
 824 static void jit_exit(int Status) {
 825   runAtExitHandlers();   // Run atexit handlers...
 826   exit(Status);
 827 }
 828
 829 // jit_atexit - Used to intercept the "atexit" library call.
 830 static int jit_atexit(void (*Fn)()) {
 831   AtExitHandlers.push_back(Fn);    // Take note of atexit handler...
 832   return 0;  // Always successful
 833 }
 834
 835 static int jit_noop() {
 836   return 0;
 837 }
 838
 839 //===----------------------------------------------------------------------===//
 840 //
 841 /// getPointerToNamedFunction - This method returns the address of the specified
 842 /// function by using the dynamic loader interface.  As such it is only useful
 843 /// for resolving library symbols, not code generated symbols.
 844 ///
 845 void *DefaultJITMemoryManager::getPointerToNamedFunction(const std::string &Name,
 846                                                          bool AbortOnFailure) {
 847   // Check to see if this is one of the functions we want to intercept.  Note,
 848   // we cast to intptr_t here to silence a -pedantic warning that complains
 849   // about casting a function pointer to a normal pointer.
 850   if (Name == "exit") return (void*)(intptr_t)&jit_exit;
 851   if (Name == "atexit") return (void*)(intptr_t)&jit_atexit;
 852
 853   // We should not invoke parent's ctors/dtors from generated main()!
 854   // On Mingw and Cygwin, the symbol __main is resolved to
 855   // callee's(eg. tools/lli) one, to invoke wrong duplicated ctors
 856   // (and register wrong callee's dtors with atexit(3)).
 857   // We expect ExecutionEngine::runStaticConstructorsDestructors()
 858   // is called before ExecutionEngine::runFunctionAsMain() is called.
 859   if (Name == "__main") return (void*)(intptr_t)&jit_noop;
 860
 861   const char *NameStr = Name.c_str();
 862   // If this is an asm specifier, skip the sentinal.
 863   if (NameStr[0] == 1) ++NameStr;
 864
 865   // If it's an external function, look it up in the process image...
 866   void *Ptr = sys::DynamicLibrary::SearchForAddressOfSymbol(NameStr);
 867   if (Ptr) return Ptr;
 868
 869   // If it wasn't found and if it starts with an underscore ('_') character,
 870   // try again without the underscore.
 871   if (NameStr[0] == '_') {
 872     Ptr = sys::DynamicLibrary::SearchForAddressOfSymbol(NameStr+1);
 873     if (Ptr) return Ptr;
 874   }
 875
 876   // Darwin/PPC adds $LDBLStub suffixes to various symbols like printf.  These
 877   // are references to hidden visibility symbols that dlsym cannot resolve.
 878   // If we have one of these, strip off $LDBLStub and try again.
 879 #if defined(__APPLE__) && defined(__ppc__)
 880   if (Name.size() > 9 && Name[Name.size()-9] == '$' &&
 881       memcmp(&Name[Name.size()-8], "LDBLStub", 8) == 0) {
 882     // First try turning $LDBLStub into $LDBL128. If that fails, strip it off.
 883     // This mirrors logic in libSystemStubs.a.
 884     std::string Prefix = std::string(Name.begin(), Name.end()-9);
 885     if (void *Ptr = getPointerToNamedFunction(Prefix+"$LDBL128", false))
 886       return Ptr;
 887     if (void *Ptr = getPointerToNamedFunction(Prefix, false))
 888       return Ptr;
 889   }
 890 #endif
 891
 892   if (AbortOnFailure) {
 893     report_fatal_error("Program used external function '"+Name+
 894                       "' which could not be resolved!");
 895   }
 896   return 0;
 897 }
 898
 899
 900
 901 JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() {
 902   return new DefaultJITMemoryManager();
 903 }
 904
 905 // Allocate memory for code in 512K slabs.
 906 const size_t DefaultJITMemoryManager::DefaultCodeSlabSize = 512 * 1024;
 907
 908 // Allocate globals and stubs in slabs of 64K.  (probably 16 pages)
 909 const size_t DefaultJITMemoryManager::DefaultSlabSize = 64 * 1024;
 910
 911 // Waste at most 16K at the end of each bump slab.  (probably 4 pages)
 912 const size_t DefaultJITMemoryManager::DefaultSizeThreshold = 16 * 1024;