lib/ExecutionEngine/JIT/JITMemoryManager.cpp

   1 //===-- JITMemoryManager.cpp - Memory Allocator for JIT'd code ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source 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/Support/Compiler.h"
  16 #include "llvm/System/Memory.h"
  17 #include <map>
  18 #include <vector>
  19 using namespace llvm;
  20
  21
  22 JITMemoryManager::~JITMemoryManager() {}
  23
  24 //===----------------------------------------------------------------------===//
  25 // Memory Block Implementation.
  26 //===----------------------------------------------------------------------===//
  27
  28 namespace {
  29   /// MemoryRangeHeader - For a range of memory, this is the header that we put
  30   /// on the block of memory.  It is carefully crafted to be one word of memory.
  31   /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader
  32   /// which starts with this.
  33   struct FreeRangeHeader;
  34   struct MemoryRangeHeader {
  35     /// ThisAllocated - This is true if this block is currently allocated.  If
  36     /// not, this can be converted to a FreeRangeHeader.
  37     unsigned ThisAllocated : 1;
  38
  39     /// PrevAllocated - Keep track of whether the block immediately before us is
  40     /// allocated.  If not, the word immediately before this header is the size
  41     /// of the previous block.
  42     unsigned PrevAllocated : 1;
  43
  44     /// BlockSize - This is the size in bytes of this memory block,
  45     /// including this header.
  46     uintptr_t BlockSize : (sizeof(intptr_t)*8 - 2);
  47
  48
  49     /// getBlockAfter - Return the memory block immediately after this one.
  50     ///
  51     MemoryRangeHeader &getBlockAfter() const {
  52       return *(MemoryRangeHeader*)((char*)this+BlockSize);
  53     }
  54
  55     /// getFreeBlockBefore - If the block before this one is free, return it,
  56     /// otherwise return null.
  57     FreeRangeHeader *getFreeBlockBefore() const {
  58       if (PrevAllocated) return 0;
  59       intptr_t PrevSize = ((intptr_t *)this)[-1];
  60       return (FreeRangeHeader*)((char*)this-PrevSize);
  61     }
  62
  63     /// FreeBlock - Turn an allocated block into a free block, adjusting
  64     /// bits in the object headers, and adding an end of region memory block.
  65     FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList);
  66
  67     /// TrimAllocationToSize - If this allocated block is significantly larger
  68     /// than NewSize, split it into two pieces (where the former is NewSize
  69     /// bytes, including the header), and add the new block to the free list.
  70     FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList,
  71                                           uint64_t NewSize);
  72   };
  73
  74   /// FreeRangeHeader - For a memory block that isn't already allocated, this
  75   /// keeps track of the current block and has a pointer to the next free block.
  76   /// Free blocks are kept on a circularly linked list.
  77   struct FreeRangeHeader : public MemoryRangeHeader {
  78     FreeRangeHeader *Prev;
  79     FreeRangeHeader *Next;
  80
  81     /// getMinBlockSize - Get the minimum size for a memory block.  Blocks
  82     /// smaller than this size cannot be created.
  83     static unsigned getMinBlockSize() {
  84       return sizeof(FreeRangeHeader)+sizeof(intptr_t);
  85     }
  86
  87     /// SetEndOfBlockSizeMarker - The word at the end of every free block is
  88     /// known to be the size of the free block.  Set it for this block.
  89     void SetEndOfBlockSizeMarker() {
  90       void *EndOfBlock = (char*)this + BlockSize;
  91       ((intptr_t *)EndOfBlock)[-1] = BlockSize;
  92     }
  93
  94     FreeRangeHeader *RemoveFromFreeList() {
  95       assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
  96       Next->Prev = Prev;
  97       return Prev->Next = Next;
  98     }
  99
 100     void AddToFreeList(FreeRangeHeader *FreeList) {
 101       Next = FreeList;
 102       Prev = FreeList->Prev;
 103       Prev->Next = this;
 104       Next->Prev = this;
 105     }
 106
 107     /// GrowBlock - The block after this block just got deallocated.  Merge it
 108     /// into the current block.
 109     void GrowBlock(uintptr_t NewSize);
 110
 111     /// AllocateBlock - Mark this entire block allocated, updating freelists
 112     /// etc.  This returns a pointer to the circular free-list.
 113     FreeRangeHeader *AllocateBlock();
 114   };
 115 }
 116
 117
 118 /// AllocateBlock - Mark this entire block allocated, updating freelists
 119 /// etc.  This returns a pointer to the circular free-list.
 120 FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
 121   assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
 122          "Cannot allocate an allocated block!");
 123   // Mark this block allocated.
 124   ThisAllocated = 1;
 125   getBlockAfter().PrevAllocated = 1;
 126
 127   // Remove it from the free list.
 128   return RemoveFromFreeList();
 129 }
 130
 131 /// FreeBlock - Turn an allocated block into a free block, adjusting
 132 /// bits in the object headers, and adding an end of region memory block.
 133 /// If possible, coalesce this block with neighboring blocks.  Return the
 134 /// FreeRangeHeader to allocate from.
 135 FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) {
 136   MemoryRangeHeader *FollowingBlock = &getBlockAfter();
 137   assert(ThisAllocated && "This block is already allocated!");
 138   assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
 139
 140   FreeRangeHeader *FreeListToReturn = FreeList;
 141
 142   // If the block after this one is free, merge it into this block.
 143   if (!FollowingBlock->ThisAllocated) {
 144     FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
 145     // "FreeList" always needs to be a valid free block.  If we're about to
 146     // coalesce with it, update our notion of what the free list is.
 147     if (&FollowingFreeBlock == FreeList) {
 148       FreeList = FollowingFreeBlock.Next;
 149       FreeListToReturn = 0;
 150       assert(&FollowingFreeBlock != FreeList && "No tombstone block?");
 151     }
 152     FollowingFreeBlock.RemoveFromFreeList();
 153
 154     // Include the following block into this one.
 155     BlockSize += FollowingFreeBlock.BlockSize;
 156     FollowingBlock = &FollowingFreeBlock.getBlockAfter();
 157
 158     // Tell the block after the block we are coalescing that this block is
 159     // allocated.
 160     FollowingBlock->PrevAllocated = 1;
 161   }
 162
 163   assert(FollowingBlock->ThisAllocated && "Missed coalescing?");
 164
 165   if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
 166     PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
 167     return FreeListToReturn ? FreeListToReturn : PrevFreeBlock;
 168   }
 169
 170   // Otherwise, mark this block free.
 171   FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
 172   FollowingBlock->PrevAllocated = 0;
 173   FreeBlock.ThisAllocated = 0;
 174
 175   // Link this into the linked list of free blocks.
 176   FreeBlock.AddToFreeList(FreeList);
 177
 178   // Add a marker at the end of the block, indicating the size of this free
 179   // block.
 180   FreeBlock.SetEndOfBlockSizeMarker();
 181   return FreeListToReturn ? FreeListToReturn : &FreeBlock;
 182 }
 183
 184 /// GrowBlock - The block after this block just got deallocated.  Merge it
 185 /// into the current block.
 186 void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
 187   assert(NewSize > BlockSize && "Not growing block?");
 188   BlockSize = NewSize;
 189   SetEndOfBlockSizeMarker();
 190   getBlockAfter().PrevAllocated = 0;
 191 }
 192
 193 /// TrimAllocationToSize - If this allocated block is significantly larger
 194 /// than NewSize, split it into two pieces (where the former is NewSize
 195 /// bytes, including the header), and add the new block to the free list.
 196 FreeRangeHeader *MemoryRangeHeader::
 197 TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
 198   assert(ThisAllocated && getBlockAfter().PrevAllocated &&
 199          "Cannot deallocate part of an allocated block!");
 200
 201   // Round up size for alignment of header.
 202   unsigned HeaderAlign = __alignof(FreeRangeHeader);
 203   NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
 204
 205   // Size is now the size of the block we will remove from the start of the
 206   // current block.
 207   assert(NewSize <= BlockSize &&
 208          "Allocating more space from this block than exists!");
 209
 210   // If splitting this block will cause the remainder to be too small, do not
 211   // split the block.
 212   if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
 213     return FreeList;
 214
 215   // Otherwise, we splice the required number of bytes out of this block, form
 216   // a new block immediately after it, then mark this block allocated.
 217   MemoryRangeHeader &FormerNextBlock = getBlockAfter();
 218
 219   // Change the size of this block.
 220   BlockSize = NewSize;
 221
 222   // Get the new block we just sliced out and turn it into a free block.
 223   FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
 224   NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
 225   NewNextBlock.ThisAllocated = 0;
 226   NewNextBlock.PrevAllocated = 1;
 227   NewNextBlock.SetEndOfBlockSizeMarker();
 228   FormerNextBlock.PrevAllocated = 0;
 229   NewNextBlock.AddToFreeList(FreeList);
 230   return &NewNextBlock;
 231 }
 232
 233 //===----------------------------------------------------------------------===//
 234 // Memory Block Implementation.
 235 //===----------------------------------------------------------------------===//
 236
 237 namespace {
 238   /// DefaultJITMemoryManager - Manage memory for the JIT code generation.
 239   /// This splits a large block of MAP_NORESERVE'd memory into two
 240   /// sections, one for function stubs, one for the functions themselves.  We
 241   /// have to do this because we may need to emit a function stub while in the
 242   /// middle of emitting a function, and we don't know how large the function we
 243   /// are emitting is.
 244   class VISIBILITY_HIDDEN DefaultJITMemoryManager : public JITMemoryManager {
 245     std::vector<sys::MemoryBlock> Blocks; // Memory blocks allocated by the JIT
 246     FreeRangeHeader *FreeMemoryList;      // Circular list of free blocks.
 247
 248     // When emitting code into a memory block, this is the block.
 249     MemoryRangeHeader *CurBlock;
 250
 251     unsigned char *CurStubPtr, *StubBase;
 252     unsigned char *GOTBase;      // Target Specific reserved memory
 253
 254     // Centralize memory block allocation.
 255     sys::MemoryBlock getNewMemoryBlock(unsigned size);
 256
 257     std::map<const Function*, MemoryRangeHeader*> FunctionBlocks;
 258   public:
 259     DefaultJITMemoryManager();
 260     ~DefaultJITMemoryManager();
 261
 262     void AllocateGOT();
 263
 264     unsigned char *allocateStub(unsigned StubSize, unsigned Alignment);
 265
 266     /// startFunctionBody - When a function starts, allocate a block of free
 267     /// executable memory, returning a pointer to it and its actual size.
 268     unsigned char *startFunctionBody(const Function *F, uintptr_t &ActualSize) {
 269       CurBlock = FreeMemoryList;
 270
 271       // Allocate the entire memory block.
 272       FreeMemoryList = FreeMemoryList->AllocateBlock();
 273       ActualSize = CurBlock->BlockSize-sizeof(MemoryRangeHeader);
 274       return (unsigned char *)(CurBlock+1);
 275     }
 276
 277     /// endFunctionBody - The function F is now allocated, and takes the memory
 278     /// in the range [FunctionStart,FunctionEnd).
 279     void endFunctionBody(const Function *F, unsigned char *FunctionStart,
 280                          unsigned char *FunctionEnd) {
 281       assert(FunctionEnd > FunctionStart);
 282       assert(FunctionStart == (unsigned char *)(CurBlock+1) &&
 283              "Mismatched function start/end!");
 284
 285       uintptr_t BlockSize = FunctionEnd - (unsigned char *)CurBlock;
 286       FunctionBlocks[F] = CurBlock;
 287
 288       // Release the memory at the end of this block that isn't needed.
 289       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
 290     }
 291
 292     unsigned char *getGOTBase() const {
 293       return GOTBase;
 294     }
 295
 296     /// deallocateMemForFunction - Deallocate all memory for the specified
 297     /// function body.
 298     void deallocateMemForFunction(const Function *F) {
 299       std::map<const Function*, MemoryRangeHeader*>::iterator
 300         I = FunctionBlocks.find(F);
 301       if (I == FunctionBlocks.end()) return;
 302
 303       // Find the block that is allocated for this function.
 304       MemoryRangeHeader *MemRange = I->second;
 305       assert(MemRange->ThisAllocated && "Block isn't allocated!");
 306
 307       // Fill the buffer with garbage!
 308 #ifndef NDEBUG
 309       memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
 310 #endif
 311
 312       // Free the memory.
 313       FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
 314
 315       // Finally, remove this entry from FunctionBlocks.
 316       FunctionBlocks.erase(I);
 317     }
 318   };
 319 }
 320
 321 DefaultJITMemoryManager::DefaultJITMemoryManager() {
 322   // Allocate a 16M block of memory for functions.
 323   sys::MemoryBlock MemBlock = getNewMemoryBlock(16 << 20);
 324
 325   unsigned char *MemBase = reinterpret_cast<unsigned char*>(MemBlock.base());
 326
 327   // Allocate stubs backwards from the base, allocate functions forward
 328   // from the base.
 329   StubBase   = MemBase;
 330   CurStubPtr = MemBase + 512*1024; // Use 512k for stubs, working backwards.
 331
 332   // We set up the memory chunk with 4 mem regions, like this:
 333   //  [ START
 334   //    [ Free      #0 ] -> Large space to allocate functions from.
 335   //    [ Allocated #1 ] -> Tiny space to separate regions.
 336   //    [ Free      #2 ] -> Tiny space so there is always at least 1 free block.
 337   //    [ Allocated #3 ] -> Tiny space to prevent looking past end of block.
 338   //  END ]
 339   //
 340   // The last three blocks are never deallocated or touched.
 341
 342   // Add MemoryRangeHeader to the end of the memory region, indicating that
 343   // the space after the block of memory is allocated.  This is block #3.
 344   MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
 345   Mem3->ThisAllocated = 1;
 346   Mem3->PrevAllocated = 0;
 347   Mem3->BlockSize     = 0;
 348
 349   /// Add a tiny free region so that the free list always has one entry.
 350   FreeRangeHeader *Mem2 =
 351     (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
 352   Mem2->ThisAllocated = 0;
 353   Mem2->PrevAllocated = 1;
 354   Mem2->BlockSize     = FreeRangeHeader::getMinBlockSize();
 355   Mem2->SetEndOfBlockSizeMarker();
 356   Mem2->Prev = Mem2;   // Mem2 *is* the free list for now.
 357   Mem2->Next = Mem2;
 358
 359   /// Add a tiny allocated region so that Mem2 is never coalesced away.
 360   MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
 361   Mem1->ThisAllocated = 1;
 362   Mem1->PrevAllocated = 0;
 363   Mem1->BlockSize     = (char*)Mem2 - (char*)Mem1;
 364
 365   // Add a FreeRangeHeader to the start of the function body region, indicating
 366   // that the space is free.  Mark the previous block allocated so we never look
 367   // at it.
 368   FreeRangeHeader *Mem0 = (FreeRangeHeader*)CurStubPtr;
 369   Mem0->ThisAllocated = 0;
 370   Mem0->PrevAllocated = 1;
 371   Mem0->BlockSize = (char*)Mem1-(char*)Mem0;
 372   Mem0->SetEndOfBlockSizeMarker();
 373   Mem0->AddToFreeList(Mem2);
 374
 375   // Start out with the freelist pointing to Mem0.
 376   FreeMemoryList = Mem0;
 377
 378   GOTBase = NULL;
 379 }
 380
 381 void DefaultJITMemoryManager::AllocateGOT() {
 382   assert(GOTBase == 0 && "Cannot allocate the got multiple times");
 383   GOTBase = new unsigned char[sizeof(void*) * 8192];
 384   HasGOT = true;
 385 }
 386
 387
 388 DefaultJITMemoryManager::~DefaultJITMemoryManager() {
 389   for (unsigned i = 0, e = Blocks.size(); i != e; ++i)
 390     sys::Memory::ReleaseRWX(Blocks[i]);
 391
 392   delete[] GOTBase;
 393   Blocks.clear();
 394 }
 395
 396 unsigned char *DefaultJITMemoryManager::allocateStub(unsigned StubSize,
 397                                                      unsigned Alignment) {
 398   CurStubPtr -= StubSize;
 399   CurStubPtr = (unsigned char*)(((intptr_t)CurStubPtr) &
 400                                 ~(intptr_t)(Alignment-1));
 401   if (CurStubPtr < StubBase) {
 402     // FIXME: allocate a new block
 403     fprintf(stderr, "JIT ran out of memory for function stubs!\n");
 404     abort();
 405   }
 406   return CurStubPtr;
 407 }
 408
 409 sys::MemoryBlock DefaultJITMemoryManager::getNewMemoryBlock(unsigned size) {
 410   // Allocate a new block close to the last one.
 411   const sys::MemoryBlock *BOld = Blocks.empty() ? 0 : &Blocks.front();
 412   std::string ErrMsg;
 413   sys::MemoryBlock B = sys::Memory::AllocateRWX(size, BOld, &ErrMsg);
 414   if (B.base() == 0) {
 415     fprintf(stderr,
 416             "Allocation failed when allocating new memory in the JIT\n%s\n",
 417             ErrMsg.c_str());
 418     abort();
 419   }
 420   Blocks.push_back(B);
 421   return B;
 422 }
 423
 424
 425 JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() {
 426   return new DefaultJITMemoryManager();
 427 }