LLVM API Documentation
00001 //===-- JITMemoryManager.cpp - Memory Allocator for JIT'd code ------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the DefaultJITMemoryManager class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #define DEBUG_TYPE "jit" 00015 #include "llvm/ExecutionEngine/JITMemoryManager.h" 00016 #include "llvm/ADT/SmallPtrSet.h" 00017 #include "llvm/ADT/Statistic.h" 00018 #include "llvm/GlobalValue.h" 00019 #include "llvm/Support/Allocator.h" 00020 #include "llvm/Support/Compiler.h" 00021 #include "llvm/Support/Debug.h" 00022 #include "llvm/Support/ErrorHandling.h" 00023 #include "llvm/Support/raw_ostream.h" 00024 #include "llvm/System/Memory.h" 00025 #include <map> 00026 #include <vector> 00027 #include <cassert> 00028 #include <climits> 00029 #include <cstdio> 00030 #include <cstdlib> 00031 #include <cstring> 00032 using namespace llvm; 00033 00034 STATISTIC(NumSlabs, "Number of slabs of memory allocated by the JIT"); 00035 00036 JITMemoryManager::~JITMemoryManager() {} 00037 00038 //===----------------------------------------------------------------------===// 00039 // Memory Block Implementation. 00040 //===----------------------------------------------------------------------===// 00041 00042 namespace { 00043 /// MemoryRangeHeader - For a range of memory, this is the header that we put 00044 /// on the block of memory. It is carefully crafted to be one word of memory. 00045 /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader 00046 /// which starts with this. 00047 struct FreeRangeHeader; 00048 struct MemoryRangeHeader { 00049 /// ThisAllocated - This is true if this block is currently allocated. If 00050 /// not, this can be converted to a FreeRangeHeader. 00051 unsigned ThisAllocated : 1; 00052 00053 /// PrevAllocated - Keep track of whether the block immediately before us is 00054 /// allocated. If not, the word immediately before this header is the size 00055 /// of the previous block. 00056 unsigned PrevAllocated : 1; 00057 00058 /// BlockSize - This is the size in bytes of this memory block, 00059 /// including this header. 00060 uintptr_t BlockSize : (sizeof(intptr_t)*CHAR_BIT - 2); 00061 00062 00063 /// getBlockAfter - Return the memory block immediately after this one. 00064 /// 00065 MemoryRangeHeader &getBlockAfter() const { 00066 return *(MemoryRangeHeader*)((char*)this+BlockSize); 00067 } 00068 00069 /// getFreeBlockBefore - If the block before this one is free, return it, 00070 /// otherwise return null. 00071 FreeRangeHeader *getFreeBlockBefore() const { 00072 if (PrevAllocated) return 0; 00073 intptr_t PrevSize = ((intptr_t *)this)[-1]; 00074 return (FreeRangeHeader*)((char*)this-PrevSize); 00075 } 00076 00077 /// FreeBlock - Turn an allocated block into a free block, adjusting 00078 /// bits in the object headers, and adding an end of region memory block. 00079 FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList); 00080 00081 /// TrimAllocationToSize - If this allocated block is significantly larger 00082 /// than NewSize, split it into two pieces (where the former is NewSize 00083 /// bytes, including the header), and add the new block to the free list. 00084 FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList, 00085 uint64_t NewSize); 00086 }; 00087 00088 /// FreeRangeHeader - For a memory block that isn't already allocated, this 00089 /// keeps track of the current block and has a pointer to the next free block. 00090 /// Free blocks are kept on a circularly linked list. 00091 struct FreeRangeHeader : public MemoryRangeHeader { 00092 FreeRangeHeader *Prev; 00093 FreeRangeHeader *Next; 00094 00095 /// getMinBlockSize - Get the minimum size for a memory block. Blocks 00096 /// smaller than this size cannot be created. 00097 static unsigned getMinBlockSize() { 00098 return sizeof(FreeRangeHeader)+sizeof(intptr_t); 00099 } 00100 00101 /// SetEndOfBlockSizeMarker - The word at the end of every free block is 00102 /// known to be the size of the free block. Set it for this block. 00103 void SetEndOfBlockSizeMarker() { 00104 void *EndOfBlock = (char*)this + BlockSize; 00105 ((intptr_t *)EndOfBlock)[-1] = BlockSize; 00106 } 00107 00108 FreeRangeHeader *RemoveFromFreeList() { 00109 assert(Next->Prev == this && Prev->Next == this && "Freelist broken!"); 00110 Next->Prev = Prev; 00111 return Prev->Next = Next; 00112 } 00113 00114 void AddToFreeList(FreeRangeHeader *FreeList) { 00115 Next = FreeList; 00116 Prev = FreeList->Prev; 00117 Prev->Next = this; 00118 Next->Prev = this; 00119 } 00120 00121 /// GrowBlock - The block after this block just got deallocated. Merge it 00122 /// into the current block. 00123 void GrowBlock(uintptr_t NewSize); 00124 00125 /// AllocateBlock - Mark this entire block allocated, updating freelists 00126 /// etc. This returns a pointer to the circular free-list. 00127 FreeRangeHeader *AllocateBlock(); 00128 }; 00129 } 00130 00131 00132 /// AllocateBlock - Mark this entire block allocated, updating freelists 00133 /// etc. This returns a pointer to the circular free-list. 00134 FreeRangeHeader *FreeRangeHeader::AllocateBlock() { 00135 assert(!ThisAllocated && !getBlockAfter().PrevAllocated && 00136 "Cannot allocate an allocated block!"); 00137 // Mark this block allocated. 00138 ThisAllocated = 1; 00139 getBlockAfter().PrevAllocated = 1; 00140 00141 // Remove it from the free list. 00142 return RemoveFromFreeList(); 00143 } 00144 00145 /// FreeBlock - Turn an allocated block into a free block, adjusting 00146 /// bits in the object headers, and adding an end of region memory block. 00147 /// If possible, coalesce this block with neighboring blocks. Return the 00148 /// FreeRangeHeader to allocate from. 00149 FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) { 00150 MemoryRangeHeader *FollowingBlock = &getBlockAfter(); 00151 assert(ThisAllocated && "This block is already free!"); 00152 assert(FollowingBlock->PrevAllocated && "Flags out of sync!"); 00153 00154 FreeRangeHeader *FreeListToReturn = FreeList; 00155 00156 // If the block after this one is free, merge it into this block. 00157 if (!FollowingBlock->ThisAllocated) { 00158 FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock; 00159 // "FreeList" always needs to be a valid free block. If we're about to 00160 // coalesce with it, update our notion of what the free list is. 00161 if (&FollowingFreeBlock == FreeList) { 00162 FreeList = FollowingFreeBlock.Next; 00163 FreeListToReturn = 0; 00164 assert(&FollowingFreeBlock != FreeList && "No tombstone block?"); 00165 } 00166 FollowingFreeBlock.RemoveFromFreeList(); 00167 00168 // Include the following block into this one. 00169 BlockSize += FollowingFreeBlock.BlockSize; 00170 FollowingBlock = &FollowingFreeBlock.getBlockAfter(); 00171 00172 // Tell the block after the block we are coalescing that this block is 00173 // allocated. 00174 FollowingBlock->PrevAllocated = 1; 00175 } 00176 00177 assert(FollowingBlock->ThisAllocated && "Missed coalescing?"); 00178 00179 if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) { 00180 PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize); 00181 return FreeListToReturn ? FreeListToReturn : PrevFreeBlock; 00182 } 00183 00184 // Otherwise, mark this block free. 00185 FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this; 00186 FollowingBlock->PrevAllocated = 0; 00187 FreeBlock.ThisAllocated = 0; 00188 00189 // Link this into the linked list of free blocks. 00190 FreeBlock.AddToFreeList(FreeList); 00191 00192 // Add a marker at the end of the block, indicating the size of this free 00193 // block. 00194 FreeBlock.SetEndOfBlockSizeMarker(); 00195 return FreeListToReturn ? FreeListToReturn : &FreeBlock; 00196 } 00197 00198 /// GrowBlock - The block after this block just got deallocated. Merge it 00199 /// into the current block. 00200 void FreeRangeHeader::GrowBlock(uintptr_t NewSize) { 00201 assert(NewSize > BlockSize && "Not growing block?"); 00202 BlockSize = NewSize; 00203 SetEndOfBlockSizeMarker(); 00204 getBlockAfter().PrevAllocated = 0; 00205 } 00206 00207 /// TrimAllocationToSize - If this allocated block is significantly larger 00208 /// than NewSize, split it into two pieces (where the former is NewSize 00209 /// bytes, including the header), and add the new block to the free list. 00210 FreeRangeHeader *MemoryRangeHeader:: 00211 TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) { 00212 assert(ThisAllocated && getBlockAfter().PrevAllocated && 00213 "Cannot deallocate part of an allocated block!"); 00214 00215 // Don't allow blocks to be trimmed below minimum required size 00216 NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize); 00217 00218 // Round up size for alignment of header. 00219 unsigned HeaderAlign = __alignof(FreeRangeHeader); 00220 NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1); 00221 00222 // Size is now the size of the block we will remove from the start of the 00223 // current block. 00224 assert(NewSize <= BlockSize && 00225 "Allocating more space from this block than exists!"); 00226 00227 // If splitting this block will cause the remainder to be too small, do not 00228 // split the block. 00229 if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize()) 00230 return FreeList; 00231 00232 // Otherwise, we splice the required number of bytes out of this block, form 00233 // a new block immediately after it, then mark this block allocated. 00234 MemoryRangeHeader &FormerNextBlock = getBlockAfter(); 00235 00236 // Change the size of this block. 00237 BlockSize = NewSize; 00238 00239 // Get the new block we just sliced out and turn it into a free block. 00240 FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter(); 00241 NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock; 00242 NewNextBlock.ThisAllocated = 0; 00243 NewNextBlock.PrevAllocated = 1; 00244 NewNextBlock.SetEndOfBlockSizeMarker(); 00245 FormerNextBlock.PrevAllocated = 0; 00246 NewNextBlock.AddToFreeList(FreeList); 00247 return &NewNextBlock; 00248 } 00249 00250 //===----------------------------------------------------------------------===// 00251 // Memory Block Implementation. 00252 //===----------------------------------------------------------------------===// 00253 00254 namespace { 00255 00256 class DefaultJITMemoryManager; 00257 00258 class JITSlabAllocator : public SlabAllocator { 00259 DefaultJITMemoryManager &JMM; 00260 public: 00261 JITSlabAllocator(DefaultJITMemoryManager &jmm) : JMM(jmm) { } 00262 virtual ~JITSlabAllocator() { } 00263 virtual MemSlab *Allocate(size_t Size); 00264 virtual void Deallocate(MemSlab *Slab); 00265 }; 00266 00267 /// DefaultJITMemoryManager - Manage memory for the JIT code generation. 00268 /// This splits a large block of MAP_NORESERVE'd memory into two 00269 /// sections, one for function stubs, one for the functions themselves. We 00270 /// have to do this because we may need to emit a function stub while in the 00271 /// middle of emitting a function, and we don't know how large the function we 00272 /// are emitting is. 00273 class DefaultJITMemoryManager : public JITMemoryManager { 00274 00275 // Whether to poison freed memory. 00276 bool PoisonMemory; 00277 00278 /// LastSlab - This points to the last slab allocated and is used as the 00279 /// NearBlock parameter to AllocateRWX so that we can attempt to lay out all 00280 /// stubs, data, and code contiguously in memory. In general, however, this 00281 /// is not possible because the NearBlock parameter is ignored on Windows 00282 /// platforms and even on Unix it works on a best-effort pasis. 00283 sys::MemoryBlock LastSlab; 00284 00285 // Memory slabs allocated by the JIT. We refer to them as slabs so we don't 00286 // confuse them with the blocks of memory descibed above. 00287 std::vector<sys::MemoryBlock> CodeSlabs; 00288 JITSlabAllocator BumpSlabAllocator; 00289 BumpPtrAllocator StubAllocator; 00290 BumpPtrAllocator DataAllocator; 00291 00292 // Circular list of free blocks. 00293 FreeRangeHeader *FreeMemoryList; 00294 00295 // When emitting code into a memory block, this is the block. 00296 MemoryRangeHeader *CurBlock; 00297 00298 uint8_t *GOTBase; // Target Specific reserved memory 00299 void *DlsymTable; // Stub external symbol information 00300 00301 std::map<const Function*, MemoryRangeHeader*> FunctionBlocks; 00302 std::map<const Function*, MemoryRangeHeader*> TableBlocks; 00303 public: 00304 DefaultJITMemoryManager(); 00305 ~DefaultJITMemoryManager(); 00306 00307 /// allocateNewSlab - Allocates a new MemoryBlock and remembers it as the 00308 /// last slab it allocated, so that subsequent allocations follow it. 00309 sys::MemoryBlock allocateNewSlab(size_t size); 00310 00311 /// DefaultCodeSlabSize - When we have to go map more memory, we allocate at 00312 /// least this much unless more is requested. 00313 static const size_t DefaultCodeSlabSize; 00314 00315 /// DefaultSlabSize - Allocate data into slabs of this size unless we get 00316 /// an allocation above SizeThreshold. 00317 static const size_t DefaultSlabSize; 00318 00319 /// DefaultSizeThreshold - For any allocation larger than this threshold, we 00320 /// should allocate a separate slab. 00321 static const size_t DefaultSizeThreshold; 00322 00323 void AllocateGOT(); 00324 void SetDlsymTable(void *); 00325 00326 // Testing methods. 00327 virtual bool CheckInvariants(std::string &ErrorStr); 00328 size_t GetDefaultCodeSlabSize() { return DefaultCodeSlabSize; } 00329 size_t GetDefaultDataSlabSize() { return DefaultSlabSize; } 00330 size_t GetDefaultStubSlabSize() { return DefaultSlabSize; } 00331 unsigned GetNumCodeSlabs() { return CodeSlabs.size(); } 00332 unsigned GetNumDataSlabs() { return DataAllocator.GetNumSlabs(); } 00333 unsigned GetNumStubSlabs() { return StubAllocator.GetNumSlabs(); } 00334 00335 /// startFunctionBody - When a function starts, allocate a block of free 00336 /// executable memory, returning a pointer to it and its actual size. 00337 uint8_t *startFunctionBody(const Function *F, uintptr_t &ActualSize) { 00338 00339 FreeRangeHeader* candidateBlock = FreeMemoryList; 00340 FreeRangeHeader* head = FreeMemoryList; 00341 FreeRangeHeader* iter = head->Next; 00342 00343 uintptr_t largest = candidateBlock->BlockSize; 00344 00345 // Search for the largest free block 00346 while (iter != head) { 00347 if (iter->BlockSize > largest) { 00348 largest = iter->BlockSize; 00349 candidateBlock = iter; 00350 } 00351 iter = iter->Next; 00352 } 00353 00354 largest = largest - sizeof(MemoryRangeHeader); 00355 00356 // If this block isn't big enough for the allocation desired, allocate 00357 // another block of memory and add it to the free list. 00358 if (largest < ActualSize || 00359 largest <= FreeRangeHeader::getMinBlockSize()) { 00360 DOUT << "JIT: Allocating another slab of memory for function."; 00361 candidateBlock = allocateNewCodeSlab((size_t)ActualSize); 00362 } 00363 00364 // Select this candidate block for allocation 00365 CurBlock = candidateBlock; 00366 00367 // Allocate the entire memory block. 00368 FreeMemoryList = candidateBlock->AllocateBlock(); 00369 ActualSize = CurBlock->BlockSize - sizeof(MemoryRangeHeader); 00370 return (uint8_t *)(CurBlock + 1); 00371 } 00372 00373 /// allocateNewCodeSlab - Helper method to allocate a new slab of code 00374 /// memory from the OS and add it to the free list. Returns the new 00375 /// FreeRangeHeader at the base of the slab. 00376 FreeRangeHeader *allocateNewCodeSlab(size_t MinSize) { 00377 // If the user needs at least MinSize free memory, then we account for 00378 // two MemoryRangeHeaders: the one in the user's block, and the one at the 00379 // end of the slab. 00380 size_t PaddedMin = MinSize + 2 * sizeof(MemoryRangeHeader); 00381 size_t SlabSize = std::max(DefaultCodeSlabSize, PaddedMin); 00382 sys::MemoryBlock B = allocateNewSlab(SlabSize); 00383 CodeSlabs.push_back(B); 00384 char *MemBase = (char*)(B.base()); 00385 00386 // Put a tiny allocated block at the end of the memory chunk, so when 00387 // FreeBlock calls getBlockAfter it doesn't fall off the end. 00388 MemoryRangeHeader *EndBlock = 00389 (MemoryRangeHeader*)(MemBase + B.size()) - 1; 00390 EndBlock->ThisAllocated = 1; 00391 EndBlock->PrevAllocated = 0; 00392 EndBlock->BlockSize = sizeof(MemoryRangeHeader); 00393 00394 // Start out with a vast new block of free memory. 00395 FreeRangeHeader *NewBlock = (FreeRangeHeader*)MemBase; 00396 NewBlock->ThisAllocated = 0; 00397 // Make sure getFreeBlockBefore doesn't look into unmapped memory. 00398 NewBlock->PrevAllocated = 1; 00399 NewBlock->BlockSize = (uintptr_t)EndBlock - (uintptr_t)NewBlock; 00400 NewBlock->SetEndOfBlockSizeMarker(); 00401 NewBlock->AddToFreeList(FreeMemoryList); 00402 00403 assert(NewBlock->BlockSize - sizeof(MemoryRangeHeader) >= MinSize && 00404 "The block was too small!"); 00405 return NewBlock; 00406 } 00407 00408 /// endFunctionBody - The function F is now allocated, and takes the memory 00409 /// in the range [FunctionStart,FunctionEnd). 00410 void endFunctionBody(const Function *F, uint8_t *FunctionStart, 00411 uint8_t *FunctionEnd) { 00412 assert(FunctionEnd > FunctionStart); 00413 assert(FunctionStart == (uint8_t *)(CurBlock+1) && 00414 "Mismatched function start/end!"); 00415 00416 uintptr_t BlockSize = FunctionEnd - (uint8_t *)CurBlock; 00417 FunctionBlocks[F] = CurBlock; 00418 00419 // Release the memory at the end of this block that isn't needed. 00420 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize); 00421 } 00422 00423 /// allocateSpace - Allocate a memory block of the given size. This method 00424 /// cannot be called between calls to startFunctionBody and endFunctionBody. 00425 uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) { 00426 CurBlock = FreeMemoryList; 00427 FreeMemoryList = FreeMemoryList->AllocateBlock(); 00428 00429 uint8_t *result = (uint8_t *)(CurBlock + 1); 00430 00431 if (Alignment == 0) Alignment = 1; 00432 result = (uint8_t*)(((intptr_t)result+Alignment-1) & 00433 ~(intptr_t)(Alignment-1)); 00434 00435 uintptr_t BlockSize = result + Size - (uint8_t *)CurBlock; 00436 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize); 00437 00438 return result; 00439 } 00440 00441 /// allocateStub - Allocate memory for a function stub. 00442 uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize, 00443 unsigned Alignment) { 00444 return (uint8_t*)StubAllocator.Allocate(StubSize, Alignment); 00445 } 00446 00447 /// allocateGlobal - Allocate memory for a global. 00448 uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) { 00449 return (uint8_t*)DataAllocator.Allocate(Size, Alignment); 00450 } 00451 00452 /// startExceptionTable - Use startFunctionBody to allocate memory for the 00453 /// function's exception table. 00454 uint8_t* startExceptionTable(const Function* F, uintptr_t &ActualSize) { 00455 return startFunctionBody(F, ActualSize); 00456 } 00457 00458 /// endExceptionTable - The exception table of F is now allocated, 00459 /// and takes the memory in the range [TableStart,TableEnd). 00460 void endExceptionTable(const Function *F, uint8_t *TableStart, 00461 uint8_t *TableEnd, uint8_t* FrameRegister) { 00462 assert(TableEnd > TableStart); 00463 assert(TableStart == (uint8_t *)(CurBlock+1) && 00464 "Mismatched table start/end!"); 00465 00466 uintptr_t BlockSize = TableEnd - (uint8_t *)CurBlock; 00467 TableBlocks[F] = CurBlock; 00468 00469 // Release the memory at the end of this block that isn't needed. 00470 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize); 00471 } 00472 00473 uint8_t *getGOTBase() const { 00474 return GOTBase; 00475 } 00476 00477 void *getDlsymTable() const { 00478 return DlsymTable; 00479 } 00480 00481 /// deallocateMemForFunction - Deallocate all memory for the specified 00482 /// function body. 00483 void deallocateMemForFunction(const Function *F) { 00484 std::map<const Function*, MemoryRangeHeader*>::iterator 00485 I = FunctionBlocks.find(F); 00486 if (I == FunctionBlocks.end()) return; 00487 00488 // Find the block that is allocated for this function. 00489 MemoryRangeHeader *MemRange = I->second; 00490 assert(MemRange->ThisAllocated && "Block isn't allocated!"); 00491 00492 // Fill the buffer with garbage! 00493 if (PoisonMemory) { 00494 memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange)); 00495 } 00496 00497 // Free the memory. 00498 FreeMemoryList = MemRange->FreeBlock(FreeMemoryList); 00499 00500 // Finally, remove this entry from FunctionBlocks. 00501 FunctionBlocks.erase(I); 00502 00503 I = TableBlocks.find(F); 00504 if (I == TableBlocks.end()) return; 00505 00506 // Find the block that is allocated for this function. 00507 MemRange = I->second; 00508 assert(MemRange->ThisAllocated && "Block isn't allocated!"); 00509 00510 // Fill the buffer with garbage! 00511 if (PoisonMemory) { 00512 memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange)); 00513 } 00514 00515 // Free the memory. 00516 FreeMemoryList = MemRange->FreeBlock(FreeMemoryList); 00517 00518 // Finally, remove this entry from TableBlocks. 00519 TableBlocks.erase(I); 00520 } 00521 00522 /// setMemoryWritable - When code generation is in progress, 00523 /// the code pages may need permissions changed. 00524 void setMemoryWritable() 00525 { 00526 for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i) 00527 sys::Memory::setWritable(CodeSlabs[i]); 00528 } 00529 /// setMemoryExecutable - When code generation is done and we're ready to 00530 /// start execution, the code pages may need permissions changed. 00531 void setMemoryExecutable() 00532 { 00533 for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i) 00534 sys::Memory::setExecutable(CodeSlabs[i]); 00535 } 00536 00537 /// setPoisonMemory - Controls whether we write garbage over freed memory. 00538 /// 00539 void setPoisonMemory(bool poison) { 00540 PoisonMemory = poison; 00541 } 00542 }; 00543 } 00544 00545 MemSlab *JITSlabAllocator::Allocate(size_t Size) { 00546 sys::MemoryBlock B = JMM.allocateNewSlab(Size); 00547 MemSlab *Slab = (MemSlab*)B.base(); 00548 Slab->Size = B.size(); 00549 Slab->NextPtr = 0; 00550 return Slab; 00551 } 00552 00553 void JITSlabAllocator::Deallocate(MemSlab *Slab) { 00554 sys::MemoryBlock B(Slab, Slab->Size); 00555 sys::Memory::ReleaseRWX(B); 00556 } 00557 00558 DefaultJITMemoryManager::DefaultJITMemoryManager() 00559 : LastSlab(0, 0), 00560 BumpSlabAllocator(*this), 00561 StubAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator), 00562 DataAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator) { 00563 00564 #ifdef NDEBUG 00565 PoisonMemory = false; 00566 #else 00567 PoisonMemory = true; 00568 #endif 00569 00570 // Allocate space for code. 00571 sys::MemoryBlock MemBlock = allocateNewSlab(DefaultCodeSlabSize); 00572 CodeSlabs.push_back(MemBlock); 00573 uint8_t *MemBase = (uint8_t*)MemBlock.base(); 00574 00575 // We set up the memory chunk with 4 mem regions, like this: 00576 // [ START 00577 // [ Free #0 ] -> Large space to allocate functions from. 00578 // [ Allocated #1 ] -> Tiny space to separate regions. 00579 // [ Free #2 ] -> Tiny space so there is always at least 1 free block. 00580 // [ Allocated #3 ] -> Tiny space to prevent looking past end of block. 00581 // END ] 00582 // 00583 // The last three blocks are never deallocated or touched. 00584 00585 // Add MemoryRangeHeader to the end of the memory region, indicating that 00586 // the space after the block of memory is allocated. This is block #3. 00587 MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1; 00588 Mem3->ThisAllocated = 1; 00589 Mem3->PrevAllocated = 0; 00590 Mem3->BlockSize = sizeof(MemoryRangeHeader); 00591 00592 /// Add a tiny free region so that the free list always has one entry. 00593 FreeRangeHeader *Mem2 = 00594 (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize()); 00595 Mem2->ThisAllocated = 0; 00596 Mem2->PrevAllocated = 1; 00597 Mem2->BlockSize = FreeRangeHeader::getMinBlockSize(); 00598 Mem2->SetEndOfBlockSizeMarker(); 00599 Mem2->Prev = Mem2; // Mem2 *is* the free list for now. 00600 Mem2->Next = Mem2; 00601 00602 /// Add a tiny allocated region so that Mem2 is never coalesced away. 00603 MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1; 00604 Mem1->ThisAllocated = 1; 00605 Mem1->PrevAllocated = 0; 00606 Mem1->BlockSize = sizeof(MemoryRangeHeader); 00607 00608 // Add a FreeRangeHeader to the start of the function body region, indicating 00609 // that the space is free. Mark the previous block allocated so we never look 00610 // at it. 00611 FreeRangeHeader *Mem0 = (FreeRangeHeader*)MemBase; 00612 Mem0->ThisAllocated = 0; 00613 Mem0->PrevAllocated = 1; 00614 Mem0->BlockSize = (char*)Mem1-(char*)Mem0; 00615 Mem0->SetEndOfBlockSizeMarker(); 00616 Mem0->AddToFreeList(Mem2); 00617 00618 // Start out with the freelist pointing to Mem0. 00619 FreeMemoryList = Mem0; 00620 00621 GOTBase = NULL; 00622 DlsymTable = NULL; 00623 } 00624 00625 void DefaultJITMemoryManager::AllocateGOT() { 00626 assert(GOTBase == 0 && "Cannot allocate the got multiple times"); 00627 GOTBase = new uint8_t[sizeof(void*) * 8192]; 00628 HasGOT = true; 00629 } 00630 00631 void DefaultJITMemoryManager::SetDlsymTable(void *ptr) { 00632 DlsymTable = ptr; 00633 } 00634 00635 DefaultJITMemoryManager::~DefaultJITMemoryManager() { 00636 for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i) 00637 sys::Memory::ReleaseRWX(CodeSlabs[i]); 00638 00639 delete[] GOTBase; 00640 } 00641 00642 sys::MemoryBlock DefaultJITMemoryManager::allocateNewSlab(size_t size) { 00643 // Allocate a new block close to the last one. 00644 std::string ErrMsg; 00645 sys::MemoryBlock *LastSlabPtr = LastSlab.base() ? &LastSlab : 0; 00646 sys::MemoryBlock B = sys::Memory::AllocateRWX(size, LastSlabPtr, &ErrMsg); 00647 if (B.base() == 0) { 00648 llvm_report_error("Allocation failed when allocating new memory in the" 00649 " JIT\n" + ErrMsg); 00650 } 00651 LastSlab = B; 00652 ++NumSlabs; 00653 // Initialize the slab to garbage when debugging. 00654 if (PoisonMemory) { 00655 memset(B.base(), 0xCD, B.size()); 00656 } 00657 return B; 00658 } 00659 00660 /// CheckInvariants - For testing only. Return "" if all internal invariants 00661 /// are preserved, and a helpful error message otherwise. For free and 00662 /// allocated blocks, make sure that adding BlockSize gives a valid block. 00663 /// For free blocks, make sure they're in the free list and that their end of 00664 /// block size marker is correct. This function should return an error before 00665 /// accessing bad memory. This function is defined here instead of in 00666 /// JITMemoryManagerTest.cpp so that we don't have to expose all of the 00667 /// implementation details of DefaultJITMemoryManager. 00668 bool DefaultJITMemoryManager::CheckInvariants(std::string &ErrorStr) { 00669 raw_string_ostream Err(ErrorStr); 00670 00671 // Construct a the set of FreeRangeHeader pointers so we can query it 00672 // efficiently. 00673 llvm::SmallPtrSet<MemoryRangeHeader*, 16> FreeHdrSet; 00674 FreeRangeHeader* FreeHead = FreeMemoryList; 00675 FreeRangeHeader* FreeRange = FreeHead; 00676 00677 do { 00678 // Check that the free range pointer is in the blocks we've allocated. 00679 bool Found = false; 00680 for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(), 00681 E = CodeSlabs.end(); I != E && !Found; ++I) { 00682 char *Start = (char*)I->base(); 00683 char *End = Start + I->size(); 00684 Found = (Start <= (char*)FreeRange && (char*)FreeRange < End); 00685 } 00686 if (!Found) { 00687 Err << "Corrupt free list; points to " << FreeRange; 00688 return false; 00689 } 00690 00691 if (FreeRange->Next->Prev != FreeRange) { 00692 Err << "Next and Prev pointers do not match."; 00693 return false; 00694 } 00695 00696 // Otherwise, add it to the set. 00697 FreeHdrSet.insert(FreeRange); 00698 FreeRange = FreeRange->Next; 00699 } while (FreeRange != FreeHead); 00700 00701 // Go over each block, and look at each MemoryRangeHeader. 00702 for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(), 00703 E = CodeSlabs.end(); I != E; ++I) { 00704 char *Start = (char*)I->base(); 00705 char *End = Start + I->size(); 00706 00707 // Check each memory range. 00708 for (MemoryRangeHeader *Hdr = (MemoryRangeHeader*)Start, *LastHdr = NULL; 00709 Start <= (char*)Hdr && (char*)Hdr < End; 00710 Hdr = &Hdr->getBlockAfter()) { 00711 if (Hdr->ThisAllocated == 0) { 00712 // Check that this range is in the free list. 00713 if (!FreeHdrSet.count(Hdr)) { 00714 Err << "Found free header at " << Hdr << " that is not in free list."; 00715 return false; 00716 } 00717 00718 // Now make sure the size marker at the end of the block is correct. 00719 uintptr_t *Marker = ((uintptr_t*)&Hdr->getBlockAfter()) - 1; 00720 if (!(Start <= (char*)Marker && (char*)Marker < End)) { 00721 Err << "Block size in header points out of current MemoryBlock."; 00722 return false; 00723 } 00724 if (Hdr->BlockSize != *Marker) { 00725 Err << "End of block size marker (" << *Marker << ") " 00726 << "and BlockSize (" << Hdr->BlockSize << ") don't match."; 00727 return false; 00728 } 00729 } 00730 00731 if (LastHdr && LastHdr->ThisAllocated != Hdr->PrevAllocated) { 00732 Err << "Hdr->PrevAllocated (" << Hdr->PrevAllocated << ") != " 00733 << "LastHdr->ThisAllocated (" << LastHdr->ThisAllocated << ")"; 00734 return false; 00735 } else if (!LastHdr && !Hdr->PrevAllocated) { 00736 Err << "The first header should have PrevAllocated true."; 00737 return false; 00738 } 00739 00740 // Remember the last header. 00741 LastHdr = Hdr; 00742 } 00743 } 00744 00745 // All invariants are preserved. 00746 return true; 00747 } 00748 00749 JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() { 00750 return new DefaultJITMemoryManager(); 00751 } 00752 00753 // Allocate memory for code in 512K slabs. 00754 const size_t DefaultJITMemoryManager::DefaultCodeSlabSize = 512 * 1024; 00755 00756 // Allocate globals and stubs in slabs of 64K. (probably 16 pages) 00757 const size_t DefaultJITMemoryManager::DefaultSlabSize = 64 * 1024; 00758 00759 // Waste at most 16K at the end of each bump slab. (probably 4 pages) 00760 const size_t DefaultJITMemoryManager::DefaultSizeThreshold = 16 * 1024;