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