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 <vector>
  27 #include <cassert>
  28 #include <climits>
  29 #include <cstring>
  30 using namespace llvm;
  31
  32 STATISTIC(NumSlabs, "Number of slabs of memory allocated by the JIT");
  33
  34 JITMemoryManager::~JITMemoryManager() {}
  35
  36 //===----------------------------------------------------------------------===//
  37 // Memory Block Implementation.
  38 //===----------------------------------------------------------------------===//
  39
  40 namespace {
  41   /// MemoryRangeHeader - For a range of memory, this is the header that we put
  42   /// on the block of memory.  It is carefully crafted to be one word of memory.
  43   /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader
  44   /// which starts with this.
  45   struct FreeRangeHeader;
  46   struct MemoryRangeHeader {
  47     /// ThisAllocated - This is true if this block is currently allocated.  If
  48     /// not, this can be converted to a FreeRangeHeader.
  49     unsigned ThisAllocated : 1;
  50
  51     /// PrevAllocated - Keep track of whether the block immediately before us is
  52     /// allocated.  If not, the word immediately before this header is the size
  53     /// of the previous block.
  54     unsigned PrevAllocated : 1;
  55
  56     /// BlockSize - This is the size in bytes of this memory block,
  57     /// including this header.
  58     uintptr_t BlockSize : (sizeof(intptr_t)*CHAR_BIT - 2);
  59
  60
  61     /// getBlockAfter - Return the memory block immediately after this one.
  62     ///
  63     MemoryRangeHeader &getBlockAfter() const {
  64       return *(MemoryRangeHeader*)((char*)this+BlockSize);
  65     }
  66
  67     /// getFreeBlockBefore - If the block before this one is free, return it,
  68     /// otherwise return null.
  69     FreeRangeHeader *getFreeBlockBefore() const {
  70       if (PrevAllocated) return 0;
  71       intptr_t PrevSize = ((intptr_t *)this)[-1];
  72       return (FreeRangeHeader*)((char*)this-PrevSize);
  73     }
  74
  75     /// FreeBlock - Turn an allocated block into a free block, adjusting
  76     /// bits in the object headers, and adding an end of region memory block.
  77     FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList);
  78
  79     /// TrimAllocationToSize - If this allocated block is significantly larger
  80     /// than NewSize, split it into two pieces (where the former is NewSize
  81     /// bytes, including the header), and add the new block to the free list.
  82     FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList,
  83                                           uint64_t NewSize);
  84   };
  85
  86   /// FreeRangeHeader - For a memory block that isn't already allocated, this
  87   /// keeps track of the current block and has a pointer to the next free block.
  88   /// Free blocks are kept on a circularly linked list.
  89   struct FreeRangeHeader : public MemoryRangeHeader {
  90     FreeRangeHeader *Prev;
  91     FreeRangeHeader *Next;
  92
  93     /// getMinBlockSize - Get the minimum size for a memory block.  Blocks
  94     /// smaller than this size cannot be created.
  95     static unsigned getMinBlockSize() {
  96       return sizeof(FreeRangeHeader)+sizeof(intptr_t);
  97     }
  98
  99     /// SetEndOfBlockSizeMarker - The word at the end of every free block is
 100     /// known to be the size of the free block.  Set it for this block.
 101     void SetEndOfBlockSizeMarker() {
 102       void *EndOfBlock = (char*)this + BlockSize;
 103       ((intptr_t *)EndOfBlock)[-1] = BlockSize;
 104     }
 105
 106     FreeRangeHeader *RemoveFromFreeList() {
 107       assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
 108       Next->Prev = Prev;
 109       return Prev->Next = Next;
 110     }
 111
 112     void AddToFreeList(FreeRangeHeader *FreeList) {
 113       Next = FreeList;
 114       Prev = FreeList->Prev;
 115       Prev->Next = this;
 116       Next->Prev = this;
 117     }
 118
 119     /// GrowBlock - The block after this block just got deallocated.  Merge it
 120     /// into the current block.
 121     void GrowBlock(uintptr_t NewSize);
 122
 123     /// AllocateBlock - Mark this entire block allocated, updating freelists
 124     /// etc.  This returns a pointer to the circular free-list.
 125     FreeRangeHeader *AllocateBlock();
 126   };
 127 }
 128
 129
 130 /// AllocateBlock - Mark this entire block allocated, updating freelists
 131 /// etc.  This returns a pointer to the circular free-list.
 132 FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
 133   assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
 134          "Cannot allocate an allocated block!");
 135   // Mark this block allocated.
 136   ThisAllocated = 1;
 137   getBlockAfter().PrevAllocated = 1;
 138
 139   // Remove it from the free list.
 140   return RemoveFromFreeList();
 141 }
 142
 143 /// FreeBlock - Turn an allocated block into a free block, adjusting
 144 /// bits in the object headers, and adding an end of region memory block.
 145 /// If possible, coalesce this block with neighboring blocks.  Return the
 146 /// FreeRangeHeader to allocate from.
 147 FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) {
 148   MemoryRangeHeader *FollowingBlock = &getBlockAfter();
 149   assert(ThisAllocated && "This block is already free!");
 150   assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
 151
 152   FreeRangeHeader *FreeListToReturn = FreeList;
 153
 154   // If the block after this one is free, merge it into this block.
 155   if (!FollowingBlock->ThisAllocated) {
 156     FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
 157     // "FreeList" always needs to be a valid free block.  If we're about to
 158     // coalesce with it, update our notion of what the free list is.
 159     if (&FollowingFreeBlock == FreeList) {
 160       FreeList = FollowingFreeBlock.Next;
 161       FreeListToReturn = 0;
 162       assert(&FollowingFreeBlock != FreeList && "No tombstone block?");
 163     }
 164     FollowingFreeBlock.RemoveFromFreeList();
 165
 166     // Include the following block into this one.
 167     BlockSize += FollowingFreeBlock.BlockSize;
 168     FollowingBlock = &FollowingFreeBlock.getBlockAfter();
 169
 170     // Tell the block after the block we are coalescing that this block is
 171     // allocated.
 172     FollowingBlock->PrevAllocated = 1;
 173   }
 174
 175   assert(FollowingBlock->ThisAllocated && "Missed coalescing?");
 176
 177   if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
 178     PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
 179     return FreeListToReturn ? FreeListToReturn : PrevFreeBlock;
 180   }
 181
 182   // Otherwise, mark this block free.
 183   FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
 184   FollowingBlock->PrevAllocated = 0;
 185   FreeBlock.ThisAllocated = 0;
 186
 187   // Link this into the linked list of free blocks.
 188   FreeBlock.AddToFreeList(FreeList);
 189
 190   // Add a marker at the end of the block, indicating the size of this free
 191   // block.
 192   FreeBlock.SetEndOfBlockSizeMarker();
 193   return FreeListToReturn ? FreeListToReturn : &FreeBlock;
 194 }
 195
 196 /// GrowBlock - The block after this block just got deallocated.  Merge it
 197 /// into the current block.
 198 void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
 199   assert(NewSize > BlockSize && "Not growing block?");
 200   BlockSize = NewSize;
 201   SetEndOfBlockSizeMarker();
 202   getBlockAfter().PrevAllocated = 0;
 203 }
 204
 205 /// TrimAllocationToSize - If this allocated block is significantly larger
 206 /// than NewSize, split it into two pieces (where the former is NewSize
 207 /// bytes, including the header), and add the new block to the free list.
 208 FreeRangeHeader *MemoryRangeHeader::
 209 TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
 210   assert(ThisAllocated && getBlockAfter().PrevAllocated &&
 211          "Cannot deallocate part of an allocated block!");
 212
 213   // Don't allow blocks to be trimmed below minimum required size
 214   NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize);
 215
 216   // Round up size for alignment of header.
 217   unsigned HeaderAlign = __alignof(FreeRangeHeader);
 218   NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
 219
 220   // Size is now the size of the block we will remove from the start of the
 221   // current block.
 222   assert(NewSize <= BlockSize &&
 223          "Allocating more space from this block than exists!");
 224
 225   // If splitting this block will cause the remainder to be too small, do not
 226   // split the block.
 227   if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
 228     return FreeList;
 229
 230   // Otherwise, we splice the required number of bytes out of this block, form
 231   // a new block immediately after it, then mark this block allocated.
 232   MemoryRangeHeader &FormerNextBlock = getBlockAfter();
 233
 234   // Change the size of this block.
 235   BlockSize = NewSize;
 236
 237   // Get the new block we just sliced out and turn it into a free block.
 238   FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
 239   NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
 240   NewNextBlock.ThisAllocated = 0;
 241   NewNextBlock.PrevAllocated = 1;
 242   NewNextBlock.SetEndOfBlockSizeMarker();
 243   FormerNextBlock.PrevAllocated = 0;
 244   NewNextBlock.AddToFreeList(FreeList);
 245   return &NewNextBlock;
 246 }
 247
 248 //===----------------------------------------------------------------------===//
 249 // Memory Block Implementation.
 250 //===----------------------------------------------------------------------===//
 251
 252 namespace {
 253
 254   class DefaultJITMemoryManager;
 255
 256   class JITSlabAllocator : public SlabAllocator {
 257     DefaultJITMemoryManager &JMM;
 258   public:
 259     JITSlabAllocator(DefaultJITMemoryManager &jmm) : JMM(jmm) { }
 260     virtual ~JITSlabAllocator() { }
 261     virtual MemSlab *Allocate(size_t Size);
 262     virtual void Deallocate(MemSlab *Slab);
 263   };
 264
 265   /// DefaultJITMemoryManager - Manage memory for the JIT code generation.
 266   /// This splits a large block of MAP_NORESERVE'd memory into two
 267   /// sections, one for function stubs, one for the functions themselves.  We
 268   /// have to do this because we may need to emit a function stub while in the
 269   /// middle of emitting a function, and we don't know how large the function we
 270   /// are emitting is.
 271   class DefaultJITMemoryManager : public JITMemoryManager {
 272
 273     // Whether to poison freed memory.
 274     bool PoisonMemory;
 275
 276     /// LastSlab - This points to the last slab allocated and is used as the
 277     /// NearBlock parameter to AllocateRWX so that we can attempt to lay out all
 278     /// stubs, data, and code contiguously in memory.  In general, however, this
 279     /// is not possible because the NearBlock parameter is ignored on Windows
 280     /// platforms and even on Unix it works on a best-effort pasis.
 281     sys::MemoryBlock LastSlab;
 282
 283     // Memory slabs allocated by the JIT.  We refer to them as slabs so we don't
 284     // confuse them with the blocks of memory described above.
 285     std::vector<sys::MemoryBlock> CodeSlabs;
 286     JITSlabAllocator BumpSlabAllocator;
 287     BumpPtrAllocator StubAllocator;
 288     BumpPtrAllocator DataAllocator;
 289
 290     // Circular list of free blocks.
 291     FreeRangeHeader *FreeMemoryList;
 292
 293     // When emitting code into a memory block, this is the block.
 294     MemoryRangeHeader *CurBlock;
 295
 296     uint8_t *GOTBase;     // Target Specific reserved memory
 297   public:
 298     DefaultJITMemoryManager();
 299     ~DefaultJITMemoryManager();
 300
 301     /// allocateNewSlab - Allocates a new MemoryBlock and remembers it as the
 302     /// last slab it allocated, so that subsequent allocations follow it.
 303     sys::MemoryBlock allocateNewSlab(size_t size);
 304
 305     /// DefaultCodeSlabSize - When we have to go map more memory, we allocate at
 306     /// least this much unless more is requested.
 307     static const size_t DefaultCodeSlabSize;
 308
 309     /// DefaultSlabSize - Allocate data into slabs of this size unless we get
 310     /// an allocation above SizeThreshold.
 311     static const size_t DefaultSlabSize;
 312
 313     /// DefaultSizeThreshold - For any allocation larger than this threshold, we
 314     /// should allocate a separate slab.
 315     static const size_t DefaultSizeThreshold;
 316
 317     void AllocateGOT();
 318
 319     // Testing methods.
 320     virtual bool CheckInvariants(std::string &ErrorStr);
 321     size_t GetDefaultCodeSlabSize() { return DefaultCodeSlabSize; }
 322     size_t GetDefaultDataSlabSize() { return DefaultSlabSize; }
 323     size_t GetDefaultStubSlabSize() { return DefaultSlabSize; }
 324     unsigned GetNumCodeSlabs() { return CodeSlabs.size(); }
 325     unsigned GetNumDataSlabs() { return DataAllocator.GetNumSlabs(); }
 326     unsigned GetNumStubSlabs() { return StubAllocator.GetNumSlabs(); }
 327
 328     /// startFunctionBody - When a function starts, allocate a block of free
 329     /// executable memory, returning a pointer to it and its actual size.
 330     uint8_t *startFunctionBody(const Function *F, uintptr_t &ActualSize) {
 331
 332       FreeRangeHeader* candidateBlock = FreeMemoryList;
 333       FreeRangeHeader* head = FreeMemoryList;
 334       FreeRangeHeader* iter = head->Next;
 335
 336       uintptr_t largest = candidateBlock->BlockSize;
 337
 338       // Search for the largest free block
 339       while (iter != head) {
 340         if (iter->BlockSize > largest) {
 341           largest = iter->BlockSize;
 342           candidateBlock = iter;
 343         }
 344         iter = iter->Next;
 345       }
 346
 347       largest = largest - sizeof(MemoryRangeHeader);
 348
 349       // If this block isn't big enough for the allocation desired, allocate
 350       // another block of memory and add it to the free list.
 351       if (largest < ActualSize ||
 352           largest <= FreeRangeHeader::getMinBlockSize()) {
 353         DEBUG(dbgs() << "JIT: Allocating another slab of memory for function.");
 354         candidateBlock = allocateNewCodeSlab((size_t)ActualSize);
 355       }
 356
 357       // Select this candidate block for allocation
 358       CurBlock = candidateBlock;
 359
 360       // Allocate the entire memory block.
 361       FreeMemoryList = candidateBlock->AllocateBlock();
 362       ActualSize = CurBlock->BlockSize - sizeof(MemoryRangeHeader);
 363       return (uint8_t *)(CurBlock + 1);
 364     }
 365
 366     /// allocateNewCodeSlab - Helper method to allocate a new slab of code
 367     /// memory from the OS and add it to the free list.  Returns the new
 368     /// FreeRangeHeader at the base of the slab.
 369     FreeRangeHeader *allocateNewCodeSlab(size_t MinSize) {
 370       // If the user needs at least MinSize free memory, then we account for
 371       // two MemoryRangeHeaders: the one in the user's block, and the one at the
 372       // end of the slab.
 373       size_t PaddedMin = MinSize + 2 * sizeof(MemoryRangeHeader);
 374       size_t SlabSize = std::max(DefaultCodeSlabSize, PaddedMin);
 375       sys::MemoryBlock B = allocateNewSlab(SlabSize);
 376       CodeSlabs.push_back(B);
 377       char *MemBase = (char*)(B.base());
 378
 379       // Put a tiny allocated block at the end of the memory chunk, so when
 380       // FreeBlock calls getBlockAfter it doesn't fall off the end.
 381       MemoryRangeHeader *EndBlock =
 382           (MemoryRangeHeader*)(MemBase + B.size()) - 1;
 383       EndBlock->ThisAllocated = 1;
 384       EndBlock->PrevAllocated = 0;
 385       EndBlock->BlockSize = sizeof(MemoryRangeHeader);
 386
 387       // Start out with a vast new block of free memory.
 388       FreeRangeHeader *NewBlock = (FreeRangeHeader*)MemBase;
 389       NewBlock->ThisAllocated = 0;
 390       // Make sure getFreeBlockBefore doesn't look into unmapped memory.
 391       NewBlock->PrevAllocated = 1;
 392       NewBlock->BlockSize = (uintptr_t)EndBlock - (uintptr_t)NewBlock;
 393       NewBlock->SetEndOfBlockSizeMarker();
 394       NewBlock->AddToFreeList(FreeMemoryList);
 395
 396       assert(NewBlock->BlockSize - sizeof(MemoryRangeHeader) >= MinSize &&
 397              "The block was too small!");
 398       return NewBlock;
 399     }
 400
 401     /// endFunctionBody - The function F is now allocated, and takes the memory
 402     /// in the range [FunctionStart,FunctionEnd).
 403     void endFunctionBody(const Function *F, uint8_t *FunctionStart,
 404                          uint8_t *FunctionEnd) {
 405       assert(FunctionEnd > FunctionStart);
 406       assert(FunctionStart == (uint8_t *)(CurBlock+1) &&
 407              "Mismatched function start/end!");
 408
 409       uintptr_t BlockSize = FunctionEnd - (uint8_t *)CurBlock;
 410
 411       // Release the memory at the end of this block that isn't needed.
 412       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
 413     }
 414
 415     /// allocateSpace - Allocate a memory block of the given size.  This method
 416     /// cannot be called between calls to startFunctionBody and endFunctionBody.
 417     uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) {
 418       CurBlock = FreeMemoryList;
 419       FreeMemoryList = FreeMemoryList->AllocateBlock();
 420
 421       uint8_t *result = (uint8_t *)(CurBlock + 1);
 422
 423       if (Alignment == 0) Alignment = 1;
 424       result = (uint8_t*)(((intptr_t)result+Alignment-1) &
 425                ~(intptr_t)(Alignment-1));
 426
 427       uintptr_t BlockSize = result + Size - (uint8_t *)CurBlock;
 428       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
 429
 430       return result;
 431     }
 432
 433     /// allocateStub - Allocate memory for a function stub.
 434     uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize,
 435                           unsigned Alignment) {
 436       return (uint8_t*)StubAllocator.Allocate(StubSize, Alignment);
 437     }
 438
 439     /// allocateGlobal - Allocate memory for a global.
 440     uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) {
 441       return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
 442     }
 443
 444     /// allocateCodeSection - Allocate memory for a code section.
 445     uint8_t *allocateCodeSection(uintptr_t Size, unsigned Alignment,
 446                                  unsigned SectionID) {
 447       // FIXME: Alignement handling.
 448       FreeRangeHeader* candidateBlock = FreeMemoryList;
 449       FreeRangeHeader* head = FreeMemoryList;
 450       FreeRangeHeader* iter = head->Next;
 451
 452       uintptr_t largest = candidateBlock->BlockSize;
 453
 454       // Search for the largest free block.
 455       while (iter != head) {
 456         if (iter->BlockSize > largest) {
 457           largest = iter->BlockSize;
 458           candidateBlock = iter;
 459         }
 460         iter = iter->Next;
 461       }
 462
 463       largest = largest - sizeof(MemoryRangeHeader);
 464
 465       // If this block isn't big enough for the allocation desired, allocate
 466       // another block of memory and add it to the free list.
 467       if (largest < Size || largest <= FreeRangeHeader::getMinBlockSize()) {
 468         DEBUG(dbgs() << "JIT: Allocating another slab of memory for function.");
 469         candidateBlock = allocateNewCodeSlab((size_t)Size);
 470       }
 471
 472       // Select this candidate block for allocation
 473       CurBlock = candidateBlock;
 474
 475       // Allocate the entire memory block.
 476       FreeMemoryList = candidateBlock->AllocateBlock();
 477       // Release the memory at the end of this block that isn't needed.
 478       FreeMemoryList = CurBlock->TrimAllocationToSize(FreeMemoryList, Size);
 479       return (uint8_t *)(CurBlock + 1);
 480     }
 481
 482     /// allocateDataSection - Allocate memory for a data section.
 483     uint8_t *allocateDataSection(uintptr_t Size, unsigned Alignment,
 484                                  unsigned SectionID) {
 485       return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
 486     }
 487
 488     /// startExceptionTable - Use startFunctionBody to allocate memory for the
 489     /// function's exception table.
 490     uint8_t* startExceptionTable(const Function* F, uintptr_t &ActualSize) {
 491       return startFunctionBody(F, ActualSize);
 492     }
 493
 494     /// endExceptionTable - The exception table of F is now allocated,
 495     /// and takes the memory in the range [TableStart,TableEnd).
 496     void endExceptionTable(const Function *F, uint8_t *TableStart,
 497                            uint8_t *TableEnd, uint8_t* FrameRegister) {
 498       assert(TableEnd > TableStart);
 499       assert(TableStart == (uint8_t *)(CurBlock+1) &&
 500              "Mismatched table start/end!");
 501
 502       uintptr_t BlockSize = TableEnd - (uint8_t *)CurBlock;
 503
 504       // Release the memory at the end of this block that isn't needed.
 505       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
 506     }
 507
 508     uint8_t *getGOTBase() const {
 509       return GOTBase;
 510     }
 511
 512     void deallocateBlock(void *Block) {
 513       // Find the block that is allocated for this function.
 514       MemoryRangeHeader *MemRange = static_cast<MemoryRangeHeader*>(Block) - 1;
 515       assert(MemRange->ThisAllocated && "Block isn't allocated!");
 516
 517       // Fill the buffer with garbage!
 518       if (PoisonMemory) {
 519         memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
 520       }
 521
 522       // Free the memory.
 523       FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
 524     }
 525
 526     /// deallocateFunctionBody - Deallocate all memory for the specified
 527     /// function body.
 528     void deallocateFunctionBody(void *Body) {
 529       if (Body) deallocateBlock(Body);
 530     }
 531
 532     /// deallocateExceptionTable - Deallocate memory for the specified
 533     /// exception table.
 534     void deallocateExceptionTable(void *ET) {
 535       if (ET) deallocateBlock(ET);
 536     }
 537
 538     /// setMemoryWritable - When code generation is in progress,
 539     /// the code pages may need permissions changed.
 540     void setMemoryWritable()
 541     {
 542       for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
 543         sys::Memory::setWritable(CodeSlabs[i]);
 544     }
 545     /// setMemoryExecutable - When code generation is done and we're ready to
 546     /// start execution, the code pages may need permissions changed.
 547     void setMemoryExecutable()
 548     {
 549       for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
 550         sys::Memory::setExecutable(CodeSlabs[i]);
 551     }
 552
 553     /// setPoisonMemory - Controls whether we write garbage over freed memory.
 554     ///
 555     void setPoisonMemory(bool poison) {
 556       PoisonMemory = poison;
 557     }
 558   };
 559 }
 560
 561 MemSlab *JITSlabAllocator::Allocate(size_t Size) {
 562   sys::MemoryBlock B = JMM.allocateNewSlab(Size);
 563   MemSlab *Slab = (MemSlab*)B.base();
 564   Slab->Size = B.size();
 565   Slab->NextPtr = 0;
 566   return Slab;
 567 }
 568
 569 void JITSlabAllocator::Deallocate(MemSlab *Slab) {
 570   sys::MemoryBlock B(Slab, Slab->Size);
 571   sys::Memory::ReleaseRWX(B);
 572 }
 573
 574 DefaultJITMemoryManager::DefaultJITMemoryManager()
 575   :
 576 #ifdef NDEBUG
 577     PoisonMemory(false),
 578 #else
 579     PoisonMemory(true),
 580 #endif
 581     LastSlab(0, 0),
 582     BumpSlabAllocator(*this),
 583     StubAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator),
 584     DataAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator) {
 585
 586   // Allocate space for code.
 587   sys::MemoryBlock MemBlock = allocateNewSlab(DefaultCodeSlabSize);
 588   CodeSlabs.push_back(MemBlock);
 589   uint8_t *MemBase = (uint8_t*)MemBlock.base();
 590
 591   // We set up the memory chunk with 4 mem regions, like this:
 592   //  [ START
 593   //    [ Free      #0 ] -> Large space to allocate functions from.
 594   //    [ Allocated #1 ] -> Tiny space to separate regions.
 595   //    [ Free      #2 ] -> Tiny space so there is always at least 1 free block.
 596   //    [ Allocated #3 ] -> Tiny space to prevent looking past end of block.
 597   //  END ]
 598   //
 599   // The last three blocks are never deallocated or touched.
 600
 601   // Add MemoryRangeHeader to the end of the memory region, indicating that
 602   // the space after the block of memory is allocated.  This is block #3.
 603   MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
 604   Mem3->ThisAllocated = 1;
 605   Mem3->PrevAllocated = 0;
 606   Mem3->BlockSize     = sizeof(MemoryRangeHeader);
 607
 608   /// Add a tiny free region so that the free list always has one entry.
 609   FreeRangeHeader *Mem2 =
 610     (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
 611   Mem2->ThisAllocated = 0;
 612   Mem2->PrevAllocated = 1;
 613   Mem2->BlockSize     = FreeRangeHeader::getMinBlockSize();
 614   Mem2->SetEndOfBlockSizeMarker();
 615   Mem2->Prev = Mem2;   // Mem2 *is* the free list for now.
 616   Mem2->Next = Mem2;
 617
 618   /// Add a tiny allocated region so that Mem2 is never coalesced away.
 619   MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
 620   Mem1->ThisAllocated = 1;
 621   Mem1->PrevAllocated = 0;
 622   Mem1->BlockSize     = sizeof(MemoryRangeHeader);
 623
 624   // Add a FreeRangeHeader to the start of the function body region, indicating
 625   // that the space is free.  Mark the previous block allocated so we never look
 626   // at it.
 627   FreeRangeHeader *Mem0 = (FreeRangeHeader*)MemBase;
 628   Mem0->ThisAllocated = 0;
 629   Mem0->PrevAllocated = 1;
 630   Mem0->BlockSize = (char*)Mem1-(char*)Mem0;
 631   Mem0->SetEndOfBlockSizeMarker();
 632   Mem0->AddToFreeList(Mem2);
 633
 634   // Start out with the freelist pointing to Mem0.
 635   FreeMemoryList = Mem0;
 636
 637   GOTBase = NULL;
 638 }
 639
 640 void DefaultJITMemoryManager::AllocateGOT() {
 641   assert(GOTBase == 0 && "Cannot allocate the got multiple times");
 642   GOTBase = new uint8_t[sizeof(void*) * 8192];
 643   HasGOT = true;
 644 }
 645
 646 DefaultJITMemoryManager::~DefaultJITMemoryManager() {
 647   for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
 648     sys::Memory::ReleaseRWX(CodeSlabs[i]);
 649
 650   delete[] GOTBase;
 651 }
 652
 653 sys::MemoryBlock DefaultJITMemoryManager::allocateNewSlab(size_t size) {
 654   // Allocate a new block close to the last one.
 655   std::string ErrMsg;
 656   sys::MemoryBlock *LastSlabPtr = LastSlab.base() ? &LastSlab : 0;
 657   sys::MemoryBlock B = sys::Memory::AllocateRWX(size, LastSlabPtr, &ErrMsg);
 658   if (B.base() == 0) {
 659     report_fatal_error("Allocation failed when allocating new memory in the"
 660                        " JIT\n" + Twine(ErrMsg));
 661   }
 662   LastSlab = B;
 663   ++NumSlabs;
 664   // Initialize the slab to garbage when debugging.
 665   if (PoisonMemory) {
 666     memset(B.base(), 0xCD, B.size());
 667   }
 668   return B;
 669 }
 670
 671 /// CheckInvariants - For testing only.  Return "" if all internal invariants
 672 /// are preserved, and a helpful error message otherwise.  For free and
 673 /// allocated blocks, make sure that adding BlockSize gives a valid block.
 674 /// For free blocks, make sure they're in the free list and that their end of
 675 /// block size marker is correct.  This function should return an error before
 676 /// accessing bad memory.  This function is defined here instead of in
 677 /// JITMemoryManagerTest.cpp so that we don't have to expose all of the
 678 /// implementation details of DefaultJITMemoryManager.
 679 bool DefaultJITMemoryManager::CheckInvariants(std::string &ErrorStr) {
 680   raw_string_ostream Err(ErrorStr);
 681
 682   // Construct a the set of FreeRangeHeader pointers so we can query it
 683   // efficiently.
 684   llvm::SmallPtrSet<MemoryRangeHeader*, 16> FreeHdrSet;
 685   FreeRangeHeader* FreeHead = FreeMemoryList;
 686   FreeRangeHeader* FreeRange = FreeHead;
 687
 688   do {
 689     // Check that the free range pointer is in the blocks we've allocated.
 690     bool Found = false;
 691     for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
 692          E = CodeSlabs.end(); I != E && !Found; ++I) {
 693       char *Start = (char*)I->base();
 694       char *End = Start + I->size();
 695       Found = (Start <= (char*)FreeRange && (char*)FreeRange < End);
 696     }
 697     if (!Found) {
 698       Err << "Corrupt free list; points to " << FreeRange;
 699       return false;
 700     }
 701
 702     if (FreeRange->Next->Prev != FreeRange) {
 703       Err << "Next and Prev pointers do not match.";
 704       return false;
 705     }
 706
 707     // Otherwise, add it to the set.
 708     FreeHdrSet.insert(FreeRange);
 709     FreeRange = FreeRange->Next;
 710   } while (FreeRange != FreeHead);
 711
 712   // Go over each block, and look at each MemoryRangeHeader.
 713   for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
 714        E = CodeSlabs.end(); I != E; ++I) {
 715     char *Start = (char*)I->base();
 716     char *End = Start + I->size();
 717
 718     // Check each memory range.
 719     for (MemoryRangeHeader *Hdr = (MemoryRangeHeader*)Start, *LastHdr = NULL;
 720          Start <= (char*)Hdr && (char*)Hdr < End;
 721          Hdr = &Hdr->getBlockAfter()) {
 722       if (Hdr->ThisAllocated == 0) {
 723         // Check that this range is in the free list.
 724         if (!FreeHdrSet.count(Hdr)) {
 725           Err << "Found free header at " << Hdr << " that is not in free list.";
 726           return false;
 727         }
 728
 729         // Now make sure the size marker at the end of the block is correct.
 730         uintptr_t *Marker = ((uintptr_t*)&Hdr->getBlockAfter()) - 1;
 731         if (!(Start <= (char*)Marker && (char*)Marker < End)) {
 732           Err << "Block size in header points out of current MemoryBlock.";
 733           return false;
 734         }
 735         if (Hdr->BlockSize != *Marker) {
 736           Err << "End of block size marker (" << *Marker << ") "
 737               << "and BlockSize (" << Hdr->BlockSize << ") don't match.";
 738           return false;
 739         }
 740       }
 741
 742       if (LastHdr && LastHdr->ThisAllocated != Hdr->PrevAllocated) {
 743         Err << "Hdr->PrevAllocated (" << Hdr->PrevAllocated << ") != "
 744             << "LastHdr->ThisAllocated (" << LastHdr->ThisAllocated << ")";
 745         return false;
 746       } else if (!LastHdr && !Hdr->PrevAllocated) {
 747         Err << "The first header should have PrevAllocated true.";
 748         return false;
 749       }
 750
 751       // Remember the last header.
 752       LastHdr = Hdr;
 753     }
 754   }
 755
 756   // All invariants are preserved.
 757   return true;
 758 }
 759
 760 JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() {
 761   return new DefaultJITMemoryManager();
 762 }
 763
 764 // Allocate memory for code in 512K slabs.
 765 const size_t DefaultJITMemoryManager::DefaultCodeSlabSize = 512 * 1024;
 766
 767 // Allocate globals and stubs in slabs of 64K.  (probably 16 pages)
 768 const size_t DefaultJITMemoryManager::DefaultSlabSize = 64 * 1024;
 769
 770 // Waste at most 16K at the end of each bump slab.  (probably 4 pages)
 771 const size_t DefaultJITMemoryManager::DefaultSizeThreshold = 16 * 1024;