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"
27 JITMemoryManager::~JITMemoryManager() {}
29 //===----------------------------------------------------------------------===//
30 // Memory Block Implementation.
31 //===----------------------------------------------------------------------===//
34 /// MemoryRangeHeader - For a range of memory, this is the header that we put
35 /// on the block of memory. It is carefully crafted to be one word of memory.
36 /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader
37 /// which starts with this.
38 struct FreeRangeHeader;
39 struct MemoryRangeHeader {
40 /// ThisAllocated - This is true if this block is currently allocated. If
41 /// not, this can be converted to a FreeRangeHeader.
42 unsigned ThisAllocated : 1;
44 /// PrevAllocated - Keep track of whether the block immediately before us is
45 /// allocated. If not, the word immediately before this header is the size
46 /// of the previous block.
47 unsigned PrevAllocated : 1;
49 /// BlockSize - This is the size in bytes of this memory block,
50 /// including this header.
51 uintptr_t BlockSize : (sizeof(intptr_t)*8 - 2);
54 /// getBlockAfter - Return the memory block immediately after this one.
56 MemoryRangeHeader &getBlockAfter() const {
57 return *(MemoryRangeHeader*)((char*)this+BlockSize);
60 /// getFreeBlockBefore - If the block before this one is free, return it,
61 /// otherwise return null.
62 FreeRangeHeader *getFreeBlockBefore() const {
63 if (PrevAllocated) return 0;
64 intptr_t PrevSize = ((intptr_t *)this)[-1];
65 return (FreeRangeHeader*)((char*)this-PrevSize);
68 /// FreeBlock - Turn an allocated block into a free block, adjusting
69 /// bits in the object headers, and adding an end of region memory block.
70 FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList);
72 /// TrimAllocationToSize - If this allocated block is significantly larger
73 /// than NewSize, split it into two pieces (where the former is NewSize
74 /// bytes, including the header), and add the new block to the free list.
75 FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList,
79 /// FreeRangeHeader - For a memory block that isn't already allocated, this
80 /// keeps track of the current block and has a pointer to the next free block.
81 /// Free blocks are kept on a circularly linked list.
82 struct FreeRangeHeader : public MemoryRangeHeader {
83 FreeRangeHeader *Prev;
84 FreeRangeHeader *Next;
86 /// getMinBlockSize - Get the minimum size for a memory block. Blocks
87 /// smaller than this size cannot be created.
88 static unsigned getMinBlockSize() {
89 return sizeof(FreeRangeHeader)+sizeof(intptr_t);
92 /// SetEndOfBlockSizeMarker - The word at the end of every free block is
93 /// known to be the size of the free block. Set it for this block.
94 void SetEndOfBlockSizeMarker() {
95 void *EndOfBlock = (char*)this + BlockSize;
96 ((intptr_t *)EndOfBlock)[-1] = BlockSize;
99 FreeRangeHeader *RemoveFromFreeList() {
100 assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
102 return Prev->Next = Next;
105 void AddToFreeList(FreeRangeHeader *FreeList) {
107 Prev = FreeList->Prev;
112 /// GrowBlock - The block after this block just got deallocated. Merge it
113 /// into the current block.
114 void GrowBlock(uintptr_t NewSize);
116 /// AllocateBlock - Mark this entire block allocated, updating freelists
117 /// etc. This returns a pointer to the circular free-list.
118 FreeRangeHeader *AllocateBlock();
123 /// AllocateBlock - Mark this entire block allocated, updating freelists
124 /// etc. This returns a pointer to the circular free-list.
125 FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
126 assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
127 "Cannot allocate an allocated block!");
128 // Mark this block allocated.
130 getBlockAfter().PrevAllocated = 1;
132 // Remove it from the free list.
133 return RemoveFromFreeList();
136 /// FreeBlock - Turn an allocated block into a free block, adjusting
137 /// bits in the object headers, and adding an end of region memory block.
138 /// If possible, coalesce this block with neighboring blocks. Return the
139 /// FreeRangeHeader to allocate from.
140 FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) {
141 MemoryRangeHeader *FollowingBlock = &getBlockAfter();
142 assert(ThisAllocated && "This block is already allocated!");
143 assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
145 FreeRangeHeader *FreeListToReturn = FreeList;
147 // If the block after this one is free, merge it into this block.
148 if (!FollowingBlock->ThisAllocated) {
149 FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
150 // "FreeList" always needs to be a valid free block. If we're about to
151 // coalesce with it, update our notion of what the free list is.
152 if (&FollowingFreeBlock == FreeList) {
153 FreeList = FollowingFreeBlock.Next;
154 FreeListToReturn = 0;
155 assert(&FollowingFreeBlock != FreeList && "No tombstone block?");
157 FollowingFreeBlock.RemoveFromFreeList();
159 // Include the following block into this one.
160 BlockSize += FollowingFreeBlock.BlockSize;
161 FollowingBlock = &FollowingFreeBlock.getBlockAfter();
163 // Tell the block after the block we are coalescing that this block is
165 FollowingBlock->PrevAllocated = 1;
168 assert(FollowingBlock->ThisAllocated && "Missed coalescing?");
170 if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
171 PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
172 return FreeListToReturn ? FreeListToReturn : PrevFreeBlock;
175 // Otherwise, mark this block free.
176 FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
177 FollowingBlock->PrevAllocated = 0;
178 FreeBlock.ThisAllocated = 0;
180 // Link this into the linked list of free blocks.
181 FreeBlock.AddToFreeList(FreeList);
183 // Add a marker at the end of the block, indicating the size of this free
185 FreeBlock.SetEndOfBlockSizeMarker();
186 return FreeListToReturn ? FreeListToReturn : &FreeBlock;
189 /// GrowBlock - The block after this block just got deallocated. Merge it
190 /// into the current block.
191 void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
192 assert(NewSize > BlockSize && "Not growing block?");
194 SetEndOfBlockSizeMarker();
195 getBlockAfter().PrevAllocated = 0;
198 /// TrimAllocationToSize - If this allocated block is significantly larger
199 /// than NewSize, split it into two pieces (where the former is NewSize
200 /// bytes, including the header), and add the new block to the free list.
201 FreeRangeHeader *MemoryRangeHeader::
202 TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
203 assert(ThisAllocated && getBlockAfter().PrevAllocated &&
204 "Cannot deallocate part of an allocated block!");
206 // Don't allow blocks to be trimmed below minimum required size
207 NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize);
209 // Round up size for alignment of header.
210 unsigned HeaderAlign = __alignof(FreeRangeHeader);
211 NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
213 // Size is now the size of the block we will remove from the start of the
215 assert(NewSize <= BlockSize &&
216 "Allocating more space from this block than exists!");
218 // If splitting this block will cause the remainder to be too small, do not
220 if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
223 // Otherwise, we splice the required number of bytes out of this block, form
224 // a new block immediately after it, then mark this block allocated.
225 MemoryRangeHeader &FormerNextBlock = getBlockAfter();
227 // Change the size of this block.
230 // Get the new block we just sliced out and turn it into a free block.
231 FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
232 NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
233 NewNextBlock.ThisAllocated = 0;
234 NewNextBlock.PrevAllocated = 1;
235 NewNextBlock.SetEndOfBlockSizeMarker();
236 FormerNextBlock.PrevAllocated = 0;
237 NewNextBlock.AddToFreeList(FreeList);
238 return &NewNextBlock;
241 //===----------------------------------------------------------------------===//
242 // Memory Block Implementation.
243 //===----------------------------------------------------------------------===//
246 /// DefaultJITMemoryManager - Manage memory for the JIT code generation.
247 /// This splits a large block of MAP_NORESERVE'd memory into two
248 /// sections, one for function stubs, one for the functions themselves. We
249 /// have to do this because we may need to emit a function stub while in the
250 /// middle of emitting a function, and we don't know how large the function we
252 class VISIBILITY_HIDDEN DefaultJITMemoryManager : public JITMemoryManager {
253 std::vector<sys::MemoryBlock> Blocks; // Memory blocks allocated by the JIT
254 FreeRangeHeader *FreeMemoryList; // Circular list of free blocks.
256 // When emitting code into a memory block, this is the block.
257 MemoryRangeHeader *CurBlock;
259 unsigned char *CurStubPtr, *StubBase;
260 unsigned char *GOTBase; // Target Specific reserved memory
261 void *DlsymTable; // Stub external symbol information
263 // Centralize memory block allocation.
264 sys::MemoryBlock getNewMemoryBlock(unsigned size);
266 std::map<const Function*, MemoryRangeHeader*> FunctionBlocks;
267 std::map<const Function*, MemoryRangeHeader*> TableBlocks;
269 DefaultJITMemoryManager();
270 ~DefaultJITMemoryManager();
273 void SetDlsymTable(void *);
275 unsigned char *allocateStub(const GlobalValue* F, unsigned StubSize,
278 /// startFunctionBody - When a function starts, allocate a block of free
279 /// executable memory, returning a pointer to it and its actual size.
280 unsigned char *startFunctionBody(const Function *F, uintptr_t &ActualSize) {
281 CurBlock = FreeMemoryList;
283 // Allocate the entire memory block.
284 FreeMemoryList = FreeMemoryList->AllocateBlock();
285 ActualSize = CurBlock->BlockSize-sizeof(MemoryRangeHeader);
286 return (unsigned char *)(CurBlock+1);
289 /// endFunctionBody - The function F is now allocated, and takes the memory
290 /// in the range [FunctionStart,FunctionEnd).
291 void endFunctionBody(const Function *F, unsigned char *FunctionStart,
292 unsigned char *FunctionEnd) {
293 assert(FunctionEnd > FunctionStart);
294 assert(FunctionStart == (unsigned char *)(CurBlock+1) &&
295 "Mismatched function start/end!");
297 uintptr_t BlockSize = FunctionEnd - (unsigned char *)CurBlock;
298 FunctionBlocks[F] = CurBlock;
300 // Release the memory at the end of this block that isn't needed.
301 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
304 /// allocateSpace - Allocate a memory block of the given size.
305 unsigned char *allocateSpace(intptr_t Size, unsigned Alignment) {
306 CurBlock = FreeMemoryList;
307 FreeMemoryList = FreeMemoryList->AllocateBlock();
309 unsigned char *result = (unsigned char *)CurBlock+1;
311 if (Alignment == 0) Alignment = 1;
312 result = (unsigned char*)(((intptr_t)result+Alignment-1) &
313 ~(intptr_t)(Alignment-1));
315 uintptr_t BlockSize = result + Size - (unsigned char *)CurBlock;
316 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
321 /// startExceptionTable - Use startFunctionBody to allocate memory for the
322 /// function's exception table.
323 unsigned char* startExceptionTable(const Function* F,
324 uintptr_t &ActualSize) {
325 return startFunctionBody(F, ActualSize);
328 /// endExceptionTable - The exception table of F is now allocated,
329 /// and takes the memory in the range [TableStart,TableEnd).
330 void endExceptionTable(const Function *F, unsigned char *TableStart,
331 unsigned char *TableEnd,
332 unsigned char* FrameRegister) {
333 assert(TableEnd > TableStart);
334 assert(TableStart == (unsigned char *)(CurBlock+1) &&
335 "Mismatched table start/end!");
337 uintptr_t BlockSize = TableEnd - (unsigned char *)CurBlock;
338 TableBlocks[F] = CurBlock;
340 // Release the memory at the end of this block that isn't needed.
341 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
344 unsigned char *getGOTBase() const {
348 void *getDlsymTable() const {
352 /// deallocateMemForFunction - Deallocate all memory for the specified
354 void deallocateMemForFunction(const Function *F) {
355 std::map<const Function*, MemoryRangeHeader*>::iterator
356 I = FunctionBlocks.find(F);
357 if (I == FunctionBlocks.end()) return;
359 // Find the block that is allocated for this function.
360 MemoryRangeHeader *MemRange = I->second;
361 assert(MemRange->ThisAllocated && "Block isn't allocated!");
363 // Fill the buffer with garbage!
365 memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
369 FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
371 // Finally, remove this entry from FunctionBlocks.
372 FunctionBlocks.erase(I);
374 I = TableBlocks.find(F);
375 if (I == TableBlocks.end()) return;
377 // Find the block that is allocated for this function.
378 MemRange = I->second;
379 assert(MemRange->ThisAllocated && "Block isn't allocated!");
381 // Fill the buffer with garbage!
383 memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
387 FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
389 // Finally, remove this entry from TableBlocks.
390 TableBlocks.erase(I);
393 /// setMemoryWritable - When code generation is in progress,
394 /// the code pages may need permissions changed.
395 void setMemoryWritable(void)
397 for (unsigned i = 0, e = Blocks.size(); i != e; ++i)
398 sys::Memory::setWritable(Blocks[i]);
400 /// setMemoryExecutable - When code generation is done and we're ready to
401 /// start execution, the code pages may need permissions changed.
402 void setMemoryExecutable(void)
404 for (unsigned i = 0, e = Blocks.size(); i != e; ++i)
405 sys::Memory::setExecutable(Blocks[i]);
410 DefaultJITMemoryManager::DefaultJITMemoryManager() {
411 // Allocate a 16M block of memory for functions.
412 #if defined(__APPLE__) && defined(__arm__)
413 sys::MemoryBlock MemBlock = getNewMemoryBlock(4 << 20);
415 sys::MemoryBlock MemBlock = getNewMemoryBlock(16 << 20);
418 unsigned char *MemBase = static_cast<unsigned char*>(MemBlock.base());
420 // Allocate stubs backwards from the base, allocate functions forward
423 CurStubPtr = MemBase + 512*1024; // Use 512k for stubs, working backwards.
425 // We set up the memory chunk with 4 mem regions, like this:
427 // [ Free #0 ] -> Large space to allocate functions from.
428 // [ Allocated #1 ] -> Tiny space to separate regions.
429 // [ Free #2 ] -> Tiny space so there is always at least 1 free block.
430 // [ Allocated #3 ] -> Tiny space to prevent looking past end of block.
433 // The last three blocks are never deallocated or touched.
435 // Add MemoryRangeHeader to the end of the memory region, indicating that
436 // the space after the block of memory is allocated. This is block #3.
437 MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
438 Mem3->ThisAllocated = 1;
439 Mem3->PrevAllocated = 0;
442 /// Add a tiny free region so that the free list always has one entry.
443 FreeRangeHeader *Mem2 =
444 (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
445 Mem2->ThisAllocated = 0;
446 Mem2->PrevAllocated = 1;
447 Mem2->BlockSize = FreeRangeHeader::getMinBlockSize();
448 Mem2->SetEndOfBlockSizeMarker();
449 Mem2->Prev = Mem2; // Mem2 *is* the free list for now.
452 /// Add a tiny allocated region so that Mem2 is never coalesced away.
453 MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
454 Mem1->ThisAllocated = 1;
455 Mem1->PrevAllocated = 0;
456 Mem1->BlockSize = (char*)Mem2 - (char*)Mem1;
458 // Add a FreeRangeHeader to the start of the function body region, indicating
459 // that the space is free. Mark the previous block allocated so we never look
461 FreeRangeHeader *Mem0 = (FreeRangeHeader*)CurStubPtr;
462 Mem0->ThisAllocated = 0;
463 Mem0->PrevAllocated = 1;
464 Mem0->BlockSize = (char*)Mem1-(char*)Mem0;
465 Mem0->SetEndOfBlockSizeMarker();
466 Mem0->AddToFreeList(Mem2);
468 // Start out with the freelist pointing to Mem0.
469 FreeMemoryList = Mem0;
475 void DefaultJITMemoryManager::AllocateGOT() {
476 assert(GOTBase == 0 && "Cannot allocate the got multiple times");
477 GOTBase = new unsigned char[sizeof(void*) * 8192];
481 void DefaultJITMemoryManager::SetDlsymTable(void *ptr) {
485 DefaultJITMemoryManager::~DefaultJITMemoryManager() {
486 for (unsigned i = 0, e = Blocks.size(); i != e; ++i)
487 sys::Memory::ReleaseRWX(Blocks[i]);
493 unsigned char *DefaultJITMemoryManager::allocateStub(const GlobalValue* F,
495 unsigned Alignment) {
496 CurStubPtr -= StubSize;
497 CurStubPtr = (unsigned char*)(((intptr_t)CurStubPtr) &
498 ~(intptr_t)(Alignment-1));
499 if (CurStubPtr < StubBase) {
500 // FIXME: allocate a new block
501 fprintf(stderr, "JIT ran out of memory for function stubs!\n");
507 sys::MemoryBlock DefaultJITMemoryManager::getNewMemoryBlock(unsigned size) {
508 // Allocate a new block close to the last one.
509 const sys::MemoryBlock *BOld = Blocks.empty() ? 0 : &Blocks.front();
511 sys::MemoryBlock B = sys::Memory::AllocateRWX(size, BOld, &ErrMsg);
514 "Allocation failed when allocating new memory in the JIT\n%s\n",
523 JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() {
524 return new DefaultJITMemoryManager();