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