JITMemoryManager.cpp revision 60b75f462e1044a031fbd75a8dcb45cb3de29177
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 // Don't allow blocks to be trimmed below minimum required size 206 NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize); 207 208 // Round up size for alignment of header. 209 unsigned HeaderAlign = __alignof(FreeRangeHeader); 210 NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1); 211 212 // Size is now the size of the block we will remove from the start of the 213 // current block. 214 assert(NewSize <= BlockSize && 215 "Allocating more space from this block than exists!"); 216 217 // If splitting this block will cause the remainder to be too small, do not 218 // split the block. 219 if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize()) 220 return FreeList; 221 222 // Otherwise, we splice the required number of bytes out of this block, form 223 // a new block immediately after it, then mark this block allocated. 224 MemoryRangeHeader &FormerNextBlock = getBlockAfter(); 225 226 // Change the size of this block. 227 BlockSize = NewSize; 228 229 // Get the new block we just sliced out and turn it into a free block. 230 FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter(); 231 NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock; 232 NewNextBlock.ThisAllocated = 0; 233 NewNextBlock.PrevAllocated = 1; 234 NewNextBlock.SetEndOfBlockSizeMarker(); 235 FormerNextBlock.PrevAllocated = 0; 236 NewNextBlock.AddToFreeList(FreeList); 237 return &NewNextBlock; 238} 239 240//===----------------------------------------------------------------------===// 241// Memory Block Implementation. 242//===----------------------------------------------------------------------===// 243 244namespace { 245 /// DefaultJITMemoryManager - Manage memory for the JIT code generation. 246 /// This splits a large block of MAP_NORESERVE'd memory into two 247 /// sections, one for function stubs, one for the functions themselves. We 248 /// have to do this because we may need to emit a function stub while in the 249 /// middle of emitting a function, and we don't know how large the function we 250 /// are emitting is. 251 class VISIBILITY_HIDDEN DefaultJITMemoryManager : public JITMemoryManager { 252 std::vector<sys::MemoryBlock> Blocks; // Memory blocks allocated by the JIT 253 FreeRangeHeader *FreeMemoryList; // Circular list of free blocks. 254 255 // When emitting code into a memory block, this is the block. 256 MemoryRangeHeader *CurBlock; 257 258 unsigned char *CurStubPtr, *StubBase; 259 unsigned char *GOTBase; // Target Specific reserved memory 260 261 // Centralize memory block allocation. 262 sys::MemoryBlock getNewMemoryBlock(unsigned size); 263 264 std::map<const Function*, MemoryRangeHeader*> FunctionBlocks; 265 std::map<const Function*, MemoryRangeHeader*> TableBlocks; 266 public: 267 DefaultJITMemoryManager(); 268 ~DefaultJITMemoryManager(); 269 270 void AllocateGOT(); 271 272 unsigned char *allocateStub(const GlobalValue* F, unsigned StubSize, 273 unsigned Alignment); 274 275 /// startFunctionBody - When a function starts, allocate a block of free 276 /// executable memory, returning a pointer to it and its actual size. 277 unsigned char *startFunctionBody(const Function *F, uintptr_t &ActualSize) { 278 CurBlock = FreeMemoryList; 279 280 // Allocate the entire memory block. 281 FreeMemoryList = FreeMemoryList->AllocateBlock(); 282 ActualSize = CurBlock->BlockSize-sizeof(MemoryRangeHeader); 283 return (unsigned char *)(CurBlock+1); 284 } 285 286 /// endFunctionBody - The function F is now allocated, and takes the memory 287 /// in the range [FunctionStart,FunctionEnd). 288 void endFunctionBody(const Function *F, unsigned char *FunctionStart, 289 unsigned char *FunctionEnd) { 290 assert(FunctionEnd > FunctionStart); 291 assert(FunctionStart == (unsigned char *)(CurBlock+1) && 292 "Mismatched function start/end!"); 293 294 uintptr_t BlockSize = FunctionEnd - (unsigned char *)CurBlock; 295 FunctionBlocks[F] = CurBlock; 296 297 // Release the memory at the end of this block that isn't needed. 298 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize); 299 } 300 301 /// startExceptionTable - Use startFunctionBody to allocate memory for the 302 /// function's exception table. 303 unsigned char* startExceptionTable(const Function* F, 304 uintptr_t &ActualSize) { 305 return startFunctionBody(F, ActualSize); 306 } 307 308 /// endExceptionTable - The exception table of F is now allocated, 309 /// and takes the memory in the range [TableStart,TableEnd). 310 void endExceptionTable(const Function *F, unsigned char *TableStart, 311 unsigned char *TableEnd, 312 unsigned char* FrameRegister) { 313 assert(TableEnd > TableStart); 314 assert(TableStart == (unsigned char *)(CurBlock+1) && 315 "Mismatched table start/end!"); 316 317 uintptr_t BlockSize = TableEnd - (unsigned char *)CurBlock; 318 TableBlocks[F] = CurBlock; 319 320 // Release the memory at the end of this block that isn't needed. 321 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize); 322 } 323 324 unsigned char *getGOTBase() const { 325 return GOTBase; 326 } 327 328 /// deallocateMemForFunction - Deallocate all memory for the specified 329 /// function body. 330 void deallocateMemForFunction(const Function *F) { 331 std::map<const Function*, MemoryRangeHeader*>::iterator 332 I = FunctionBlocks.find(F); 333 if (I == FunctionBlocks.end()) return; 334 335 // Find the block that is allocated for this function. 336 MemoryRangeHeader *MemRange = I->second; 337 assert(MemRange->ThisAllocated && "Block isn't allocated!"); 338 339 // Fill the buffer with garbage! 340#ifndef NDEBUG 341 memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange)); 342#endif 343 344 // Free the memory. 345 FreeMemoryList = MemRange->FreeBlock(FreeMemoryList); 346 347 // Finally, remove this entry from FunctionBlocks. 348 FunctionBlocks.erase(I); 349 350 I = TableBlocks.find(F); 351 if (I == TableBlocks.end()) return; 352 353 // Find the block that is allocated for this function. 354 MemRange = I->second; 355 assert(MemRange->ThisAllocated && "Block isn't allocated!"); 356 357 // Fill the buffer with garbage! 358#ifndef NDEBUG 359 memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange)); 360#endif 361 362 // Free the memory. 363 FreeMemoryList = MemRange->FreeBlock(FreeMemoryList); 364 365 // Finally, remove this entry from TableBlocks. 366 TableBlocks.erase(I); 367 } 368 }; 369} 370 371DefaultJITMemoryManager::DefaultJITMemoryManager() { 372 // Allocate a 16M block of memory for functions. 373 sys::MemoryBlock MemBlock = getNewMemoryBlock(16 << 20); 374 375 unsigned char *MemBase = static_cast<unsigned char*>(MemBlock.base()); 376 377 // Allocate stubs backwards from the base, allocate functions forward 378 // from the base. 379 StubBase = MemBase; 380 CurStubPtr = MemBase + 512*1024; // Use 512k for stubs, working backwards. 381 382 // We set up the memory chunk with 4 mem regions, like this: 383 // [ START 384 // [ Free #0 ] -> Large space to allocate functions from. 385 // [ Allocated #1 ] -> Tiny space to separate regions. 386 // [ Free #2 ] -> Tiny space so there is always at least 1 free block. 387 // [ Allocated #3 ] -> Tiny space to prevent looking past end of block. 388 // END ] 389 // 390 // The last three blocks are never deallocated or touched. 391 392 // Add MemoryRangeHeader to the end of the memory region, indicating that 393 // the space after the block of memory is allocated. This is block #3. 394 MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1; 395 Mem3->ThisAllocated = 1; 396 Mem3->PrevAllocated = 0; 397 Mem3->BlockSize = 0; 398 399 /// Add a tiny free region so that the free list always has one entry. 400 FreeRangeHeader *Mem2 = 401 (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize()); 402 Mem2->ThisAllocated = 0; 403 Mem2->PrevAllocated = 1; 404 Mem2->BlockSize = FreeRangeHeader::getMinBlockSize(); 405 Mem2->SetEndOfBlockSizeMarker(); 406 Mem2->Prev = Mem2; // Mem2 *is* the free list for now. 407 Mem2->Next = Mem2; 408 409 /// Add a tiny allocated region so that Mem2 is never coalesced away. 410 MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1; 411 Mem1->ThisAllocated = 1; 412 Mem1->PrevAllocated = 0; 413 Mem1->BlockSize = (char*)Mem2 - (char*)Mem1; 414 415 // Add a FreeRangeHeader to the start of the function body region, indicating 416 // that the space is free. Mark the previous block allocated so we never look 417 // at it. 418 FreeRangeHeader *Mem0 = (FreeRangeHeader*)CurStubPtr; 419 Mem0->ThisAllocated = 0; 420 Mem0->PrevAllocated = 1; 421 Mem0->BlockSize = (char*)Mem1-(char*)Mem0; 422 Mem0->SetEndOfBlockSizeMarker(); 423 Mem0->AddToFreeList(Mem2); 424 425 // Start out with the freelist pointing to Mem0. 426 FreeMemoryList = Mem0; 427 428 GOTBase = NULL; 429} 430 431void DefaultJITMemoryManager::AllocateGOT() { 432 assert(GOTBase == 0 && "Cannot allocate the got multiple times"); 433 GOTBase = new unsigned char[sizeof(void*) * 8192]; 434 HasGOT = true; 435} 436 437 438DefaultJITMemoryManager::~DefaultJITMemoryManager() { 439 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) 440 sys::Memory::ReleaseRWX(Blocks[i]); 441 442 delete[] GOTBase; 443 Blocks.clear(); 444} 445 446unsigned char *DefaultJITMemoryManager::allocateStub(const GlobalValue* F, 447 unsigned StubSize, 448 unsigned Alignment) { 449 CurStubPtr -= StubSize; 450 CurStubPtr = (unsigned char*)(((intptr_t)CurStubPtr) & 451 ~(intptr_t)(Alignment-1)); 452 if (CurStubPtr < StubBase) { 453 // FIXME: allocate a new block 454 fprintf(stderr, "JIT ran out of memory for function stubs!\n"); 455 abort(); 456 } 457 return CurStubPtr; 458} 459 460sys::MemoryBlock DefaultJITMemoryManager::getNewMemoryBlock(unsigned size) { 461 // Allocate a new block close to the last one. 462 const sys::MemoryBlock *BOld = Blocks.empty() ? 0 : &Blocks.front(); 463 std::string ErrMsg; 464 sys::MemoryBlock B = sys::Memory::AllocateRWX(size, BOld, &ErrMsg); 465 if (B.base() == 0) { 466 fprintf(stderr, 467 "Allocation failed when allocating new memory in the JIT\n%s\n", 468 ErrMsg.c_str()); 469 abort(); 470 } 471 Blocks.push_back(B); 472 return B; 473} 474 475 476JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() { 477 return new DefaultJITMemoryManager(); 478} 479