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