JITMemoryManager.cpp revision 8907b4ba479bbfbe630a4c3abab32c7d49749a48
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> 19using namespace llvm; 20 21 22JITMemoryManager::~JITMemoryManager() {} 23 24//===----------------------------------------------------------------------===// 25// Memory Block Implementation. 26//===----------------------------------------------------------------------===// 27 28namespace { 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. 120FreeRangeHeader *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. 135FreeRangeHeader *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. 186void 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. 196FreeRangeHeader *MemoryRangeHeader:: 197TrimAllocationToSize(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 237namespace { 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 321DefaultJITMemoryManager::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 381void 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 388DefaultJITMemoryManager::~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 396unsigned 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 409sys::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 425JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() { 426 return new DefaultJITMemoryManager(); 427} 428