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