1 //===-- JITMemoryManager.cpp - Memory Allocator for JIT'd code ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the DefaultJITMemoryManager class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/GlobalValue.h"
15 #include "llvm/ExecutionEngine/JITMemoryManager.h"
16 #include "llvm/Support/Compiler.h"
17 #include "llvm/System/Memory.h"
28 JITMemoryManager::~JITMemoryManager() {}
30 //===----------------------------------------------------------------------===//
31 // Memory Block Implementation.
32 //===----------------------------------------------------------------------===//
35 /// MemoryRangeHeader - For a range of memory, this is the header that we put
36 /// on the block of memory. It is carefully crafted to be one word of memory.
37 /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader
38 /// which starts with this.
39 struct FreeRangeHeader;
40 struct MemoryRangeHeader {
41 /// ThisAllocated - This is true if this block is currently allocated. If
42 /// not, this can be converted to a FreeRangeHeader.
43 unsigned ThisAllocated : 1;
45 /// PrevAllocated - Keep track of whether the block immediately before us is
46 /// allocated. If not, the word immediately before this header is the size
47 /// of the previous block.
48 unsigned PrevAllocated : 1;
50 /// BlockSize - This is the size in bytes of this memory block,
51 /// including this header.
52 uintptr_t BlockSize : (sizeof(intptr_t)*CHAR_BIT - 2);
55 /// getBlockAfter - Return the memory block immediately after this one.
57 MemoryRangeHeader &getBlockAfter() const {
58 return *(MemoryRangeHeader*)((char*)this+BlockSize);
61 /// getFreeBlockBefore - If the block before this one is free, return it,
62 /// otherwise return null.
63 FreeRangeHeader *getFreeBlockBefore() const {
64 if (PrevAllocated) return 0;
65 intptr_t PrevSize = ((intptr_t *)this)[-1];
66 return (FreeRangeHeader*)((char*)this-PrevSize);
69 /// FreeBlock - Turn an allocated block into a free block, adjusting
70 /// bits in the object headers, and adding an end of region memory block.
71 FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList);
73 /// TrimAllocationToSize - If this allocated block is significantly larger
74 /// than NewSize, split it into two pieces (where the former is NewSize
75 /// bytes, including the header), and add the new block to the free list.
76 FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList,
80 /// FreeRangeHeader - For a memory block that isn't already allocated, this
81 /// keeps track of the current block and has a pointer to the next free block.
82 /// Free blocks are kept on a circularly linked list.
83 struct FreeRangeHeader : public MemoryRangeHeader {
84 FreeRangeHeader *Prev;
85 FreeRangeHeader *Next;
87 /// getMinBlockSize - Get the minimum size for a memory block. Blocks
88 /// smaller than this size cannot be created.
89 static unsigned getMinBlockSize() {
90 return sizeof(FreeRangeHeader)+sizeof(intptr_t);
93 /// SetEndOfBlockSizeMarker - The word at the end of every free block is
94 /// known to be the size of the free block. Set it for this block.
95 void SetEndOfBlockSizeMarker() {
96 void *EndOfBlock = (char*)this + BlockSize;
97 ((intptr_t *)EndOfBlock)[-1] = BlockSize;
100 FreeRangeHeader *RemoveFromFreeList() {
101 assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
103 return Prev->Next = Next;
106 void AddToFreeList(FreeRangeHeader *FreeList) {
108 Prev = FreeList->Prev;
113 /// GrowBlock - The block after this block just got deallocated. Merge it
114 /// into the current block.
115 void GrowBlock(uintptr_t NewSize);
117 /// AllocateBlock - Mark this entire block allocated, updating freelists
118 /// etc. This returns a pointer to the circular free-list.
119 FreeRangeHeader *AllocateBlock();
124 /// AllocateBlock - Mark this entire block allocated, updating freelists
125 /// etc. This returns a pointer to the circular free-list.
126 FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
127 assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
128 "Cannot allocate an allocated block!");
129 // Mark this block allocated.
131 getBlockAfter().PrevAllocated = 1;
133 // Remove it from the free list.
134 return RemoveFromFreeList();
137 /// FreeBlock - Turn an allocated block into a free block, adjusting
138 /// bits in the object headers, and adding an end of region memory block.
139 /// If possible, coalesce this block with neighboring blocks. Return the
140 /// FreeRangeHeader to allocate from.
141 FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) {
142 MemoryRangeHeader *FollowingBlock = &getBlockAfter();
143 assert(ThisAllocated && "This block is already allocated!");
144 assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
146 FreeRangeHeader *FreeListToReturn = FreeList;
148 // If the block after this one is free, merge it into this block.
149 if (!FollowingBlock->ThisAllocated) {
150 FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
151 // "FreeList" always needs to be a valid free block. If we're about to
152 // coalesce with it, update our notion of what the free list is.
153 if (&FollowingFreeBlock == FreeList) {
154 FreeList = FollowingFreeBlock.Next;
155 FreeListToReturn = 0;
156 assert(&FollowingFreeBlock != FreeList && "No tombstone block?");
158 FollowingFreeBlock.RemoveFromFreeList();
160 // Include the following block into this one.
161 BlockSize += FollowingFreeBlock.BlockSize;
162 FollowingBlock = &FollowingFreeBlock.getBlockAfter();
164 // Tell the block after the block we are coalescing that this block is
166 FollowingBlock->PrevAllocated = 1;
169 assert(FollowingBlock->ThisAllocated && "Missed coalescing?");
171 if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
172 PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
173 return FreeListToReturn ? FreeListToReturn : PrevFreeBlock;
176 // Otherwise, mark this block free.
177 FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
178 FollowingBlock->PrevAllocated = 0;
179 FreeBlock.ThisAllocated = 0;
181 // Link this into the linked list of free blocks.
182 FreeBlock.AddToFreeList(FreeList);
184 // Add a marker at the end of the block, indicating the size of this free
186 FreeBlock.SetEndOfBlockSizeMarker();
187 return FreeListToReturn ? FreeListToReturn : &FreeBlock;
190 /// GrowBlock - The block after this block just got deallocated. Merge it
191 /// into the current block.
192 void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
193 assert(NewSize > BlockSize && "Not growing block?");
195 SetEndOfBlockSizeMarker();
196 getBlockAfter().PrevAllocated = 0;
199 /// TrimAllocationToSize - If this allocated block is significantly larger
200 /// than NewSize, split it into two pieces (where the former is NewSize
201 /// bytes, including the header), and add the new block to the free list.
202 FreeRangeHeader *MemoryRangeHeader::
203 TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
204 assert(ThisAllocated && getBlockAfter().PrevAllocated &&
205 "Cannot deallocate part of an allocated block!");
207 // Don't allow blocks to be trimmed below minimum required size
208 NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize);
210 // Round up size for alignment of header.
211 unsigned HeaderAlign = __alignof(FreeRangeHeader);
212 NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
214 // Size is now the size of the block we will remove from the start of the
216 assert(NewSize <= BlockSize &&
217 "Allocating more space from this block than exists!");
219 // If splitting this block will cause the remainder to be too small, do not
221 if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
224 // Otherwise, we splice the required number of bytes out of this block, form
225 // a new block immediately after it, then mark this block allocated.
226 MemoryRangeHeader &FormerNextBlock = getBlockAfter();
228 // Change the size of this block.
231 // Get the new block we just sliced out and turn it into a free block.
232 FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
233 NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
234 NewNextBlock.ThisAllocated = 0;
235 NewNextBlock.PrevAllocated = 1;
236 NewNextBlock.SetEndOfBlockSizeMarker();
237 FormerNextBlock.PrevAllocated = 0;
238 NewNextBlock.AddToFreeList(FreeList);
239 return &NewNextBlock;
242 //===----------------------------------------------------------------------===//
243 // Memory Block Implementation.
244 //===----------------------------------------------------------------------===//
247 /// DefaultJITMemoryManager - Manage memory for the JIT code generation.
248 /// This splits a large block of MAP_NORESERVE'd memory into two
249 /// sections, one for function stubs, one for the functions themselves. We
250 /// have to do this because we may need to emit a function stub while in the
251 /// middle of emitting a function, and we don't know how large the function we
253 class VISIBILITY_HIDDEN DefaultJITMemoryManager : public JITMemoryManager {
254 std::vector<sys::MemoryBlock> Blocks; // Memory blocks allocated by the JIT
255 FreeRangeHeader *FreeMemoryList; // Circular list of free blocks.
257 // When emitting code into a memory block, this is the block.
258 MemoryRangeHeader *CurBlock;
260 uint8_t *CurStubPtr, *StubBase;
261 uint8_t *GOTBase; // Target Specific reserved memory
262 void *DlsymTable; // Stub external symbol information
264 // Centralize memory block allocation.
265 sys::MemoryBlock getNewMemoryBlock(unsigned size);
267 std::map<const Function*, MemoryRangeHeader*> FunctionBlocks;
268 std::map<const Function*, MemoryRangeHeader*> TableBlocks;
270 DefaultJITMemoryManager();
271 ~DefaultJITMemoryManager();
274 void SetDlsymTable(void *);
276 uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize,
279 /// startFunctionBody - When a function starts, allocate a block of free
280 /// executable memory, returning a pointer to it and its actual size.
281 uint8_t *startFunctionBody(const Function *F, uintptr_t &ActualSize) {
283 FreeRangeHeader* candidateBlock = FreeMemoryList;
284 FreeRangeHeader* head = FreeMemoryList;
285 FreeRangeHeader* iter = head->Next;
287 uintptr_t largest = candidateBlock->BlockSize;
289 // Search for the largest free block
290 while (iter != head) {
291 if (iter->BlockSize > largest) {
292 largest = iter->BlockSize;
293 candidateBlock = iter;
298 // Select this candidate block for allocation
299 CurBlock = candidateBlock;
301 // Allocate the entire memory block.
302 FreeMemoryList = candidateBlock->AllocateBlock();
303 ActualSize = CurBlock->BlockSize-sizeof(MemoryRangeHeader);
304 return (uint8_t *)(CurBlock+1);
307 /// endFunctionBody - The function F is now allocated, and takes the memory
308 /// in the range [FunctionStart,FunctionEnd).
309 void endFunctionBody(const Function *F, uint8_t *FunctionStart,
310 uint8_t *FunctionEnd) {
311 assert(FunctionEnd > FunctionStart);
312 assert(FunctionStart == (uint8_t *)(CurBlock+1) &&
313 "Mismatched function start/end!");
315 uintptr_t BlockSize = FunctionEnd - (uint8_t *)CurBlock;
316 FunctionBlocks[F] = CurBlock;
318 // Release the memory at the end of this block that isn't needed.
319 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
322 /// allocateSpace - Allocate a memory block of the given size.
323 uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) {
324 CurBlock = FreeMemoryList;
325 FreeMemoryList = FreeMemoryList->AllocateBlock();
327 uint8_t *result = (uint8_t *)CurBlock+1;
329 if (Alignment == 0) Alignment = 1;
330 result = (uint8_t*)(((intptr_t)result+Alignment-1) &
331 ~(intptr_t)(Alignment-1));
333 uintptr_t BlockSize = result + Size - (uint8_t *)CurBlock;
334 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
339 /// startExceptionTable - Use startFunctionBody to allocate memory for the
340 /// function's exception table.
341 uint8_t* startExceptionTable(const Function* F, uintptr_t &ActualSize) {
342 return startFunctionBody(F, ActualSize);
345 /// endExceptionTable - The exception table of F is now allocated,
346 /// and takes the memory in the range [TableStart,TableEnd).
347 void endExceptionTable(const Function *F, uint8_t *TableStart,
348 uint8_t *TableEnd, uint8_t* FrameRegister) {
349 assert(TableEnd > TableStart);
350 assert(TableStart == (uint8_t *)(CurBlock+1) &&
351 "Mismatched table start/end!");
353 uintptr_t BlockSize = TableEnd - (uint8_t *)CurBlock;
354 TableBlocks[F] = CurBlock;
356 // Release the memory at the end of this block that isn't needed.
357 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
360 uint8_t *getGOTBase() const {
364 void *getDlsymTable() const {
368 /// deallocateMemForFunction - Deallocate all memory for the specified
370 void deallocateMemForFunction(const Function *F) {
371 std::map<const Function*, MemoryRangeHeader*>::iterator
372 I = FunctionBlocks.find(F);
373 if (I == FunctionBlocks.end()) return;
375 // Find the block that is allocated for this function.
376 MemoryRangeHeader *MemRange = I->second;
377 assert(MemRange->ThisAllocated && "Block isn't allocated!");
379 // Fill the buffer with garbage!
381 memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
385 FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
387 // Finally, remove this entry from FunctionBlocks.
388 FunctionBlocks.erase(I);
390 I = TableBlocks.find(F);
391 if (I == TableBlocks.end()) return;
393 // Find the block that is allocated for this function.
394 MemRange = I->second;
395 assert(MemRange->ThisAllocated && "Block isn't allocated!");
397 // Fill the buffer with garbage!
399 memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
403 FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
405 // Finally, remove this entry from TableBlocks.
406 TableBlocks.erase(I);
409 /// setMemoryWritable - When code generation is in progress,
410 /// the code pages may need permissions changed.
411 void setMemoryWritable(void)
413 for (unsigned i = 0, e = Blocks.size(); i != e; ++i)
414 sys::Memory::setWritable(Blocks[i]);
416 /// setMemoryExecutable - When code generation is done and we're ready to
417 /// start execution, the code pages may need permissions changed.
418 void setMemoryExecutable(void)
420 for (unsigned i = 0, e = Blocks.size(); i != e; ++i)
421 sys::Memory::setExecutable(Blocks[i]);
426 DefaultJITMemoryManager::DefaultJITMemoryManager() {
427 // Allocate a 16M block of memory for functions.
428 #if defined(__APPLE__) && defined(__arm__)
429 sys::MemoryBlock MemBlock = getNewMemoryBlock(4 << 20);
431 sys::MemoryBlock MemBlock = getNewMemoryBlock(16 << 20);
434 uint8_t *MemBase = static_cast<uint8_t*>(MemBlock.base());
436 // Allocate stubs backwards from the base, allocate functions forward
439 CurStubPtr = MemBase + 512*1024; // Use 512k for stubs, working backwards.
441 // We set up the memory chunk with 4 mem regions, like this:
443 // [ Free #0 ] -> Large space to allocate functions from.
444 // [ Allocated #1 ] -> Tiny space to separate regions.
445 // [ Free #2 ] -> Tiny space so there is always at least 1 free block.
446 // [ Allocated #3 ] -> Tiny space to prevent looking past end of block.
449 // The last three blocks are never deallocated or touched.
451 // Add MemoryRangeHeader to the end of the memory region, indicating that
452 // the space after the block of memory is allocated. This is block #3.
453 MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
454 Mem3->ThisAllocated = 1;
455 Mem3->PrevAllocated = 0;
458 /// Add a tiny free region so that the free list always has one entry.
459 FreeRangeHeader *Mem2 =
460 (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
461 Mem2->ThisAllocated = 0;
462 Mem2->PrevAllocated = 1;
463 Mem2->BlockSize = FreeRangeHeader::getMinBlockSize();
464 Mem2->SetEndOfBlockSizeMarker();
465 Mem2->Prev = Mem2; // Mem2 *is* the free list for now.
468 /// Add a tiny allocated region so that Mem2 is never coalesced away.
469 MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
470 Mem1->ThisAllocated = 1;
471 Mem1->PrevAllocated = 0;
472 Mem1->BlockSize = (char*)Mem2 - (char*)Mem1;
474 // Add a FreeRangeHeader to the start of the function body region, indicating
475 // that the space is free. Mark the previous block allocated so we never look
477 FreeRangeHeader *Mem0 = (FreeRangeHeader*)CurStubPtr;
478 Mem0->ThisAllocated = 0;
479 Mem0->PrevAllocated = 1;
480 Mem0->BlockSize = (char*)Mem1-(char*)Mem0;
481 Mem0->SetEndOfBlockSizeMarker();
482 Mem0->AddToFreeList(Mem2);
484 // Start out with the freelist pointing to Mem0.
485 FreeMemoryList = Mem0;
491 void DefaultJITMemoryManager::AllocateGOT() {
492 assert(GOTBase == 0 && "Cannot allocate the got multiple times");
493 GOTBase = new uint8_t[sizeof(void*) * 8192];
497 void DefaultJITMemoryManager::SetDlsymTable(void *ptr) {
501 DefaultJITMemoryManager::~DefaultJITMemoryManager() {
502 for (unsigned i = 0, e = Blocks.size(); i != e; ++i)
503 sys::Memory::ReleaseRWX(Blocks[i]);
509 uint8_t *DefaultJITMemoryManager::allocateStub(const GlobalValue* F,
511 unsigned Alignment) {
512 CurStubPtr -= StubSize;
513 CurStubPtr = (uint8_t*)(((intptr_t)CurStubPtr) &
514 ~(intptr_t)(Alignment-1));
515 if (CurStubPtr < StubBase) {
516 // FIXME: allocate a new block
517 fprintf(stderr, "JIT ran out of memory for function stubs!\n");
523 sys::MemoryBlock DefaultJITMemoryManager::getNewMemoryBlock(unsigned size) {
524 // Allocate a new block close to the last one.
525 const sys::MemoryBlock *BOld = Blocks.empty() ? 0 : &Blocks.front();
527 sys::MemoryBlock B = sys::Memory::AllocateRWX(size, BOld, &ErrMsg);
530 "Allocation failed when allocating new memory in the JIT\n%s\n",
539 JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() {
540 return new DefaultJITMemoryManager();