• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #define DEBUG_TYPE "jit"
15 #include "llvm/ExecutionEngine/JITMemoryManager.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/ADT/Twine.h"
19 #include "llvm/GlobalValue.h"
20 #include "llvm/Support/Allocator.h"
21 #include "llvm/Support/Compiler.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/ErrorHandling.h"
24 #include "llvm/Support/raw_ostream.h"
25 #include "llvm/Support/Memory.h"
26 #include <vector>
27 #include <cassert>
28 #include <climits>
29 #include <cstring>
30 using namespace llvm;
31 
32 STATISTIC(NumSlabs, "Number of slabs of memory allocated by the JIT");
33 
~JITMemoryManager()34 JITMemoryManager::~JITMemoryManager() {}
35 
36 //===----------------------------------------------------------------------===//
37 // Memory Block Implementation.
38 //===----------------------------------------------------------------------===//
39 
40 namespace {
41   /// MemoryRangeHeader - For a range of memory, this is the header that we put
42   /// on the block of memory.  It is carefully crafted to be one word of memory.
43   /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader
44   /// which starts with this.
45   struct FreeRangeHeader;
46   struct MemoryRangeHeader {
47     /// ThisAllocated - This is true if this block is currently allocated.  If
48     /// not, this can be converted to a FreeRangeHeader.
49     unsigned ThisAllocated : 1;
50 
51     /// PrevAllocated - Keep track of whether the block immediately before us is
52     /// allocated.  If not, the word immediately before this header is the size
53     /// of the previous block.
54     unsigned PrevAllocated : 1;
55 
56     /// BlockSize - This is the size in bytes of this memory block,
57     /// including this header.
58     uintptr_t BlockSize : (sizeof(intptr_t)*CHAR_BIT - 2);
59 
60 
61     /// getBlockAfter - Return the memory block immediately after this one.
62     ///
getBlockAfter__anone29d22b10111::MemoryRangeHeader63     MemoryRangeHeader &getBlockAfter() const {
64       return *(MemoryRangeHeader*)((char*)this+BlockSize);
65     }
66 
67     /// getFreeBlockBefore - If the block before this one is free, return it,
68     /// otherwise return null.
getFreeBlockBefore__anone29d22b10111::MemoryRangeHeader69     FreeRangeHeader *getFreeBlockBefore() const {
70       if (PrevAllocated) return 0;
71       intptr_t PrevSize = ((intptr_t *)this)[-1];
72       return (FreeRangeHeader*)((char*)this-PrevSize);
73     }
74 
75     /// FreeBlock - Turn an allocated block into a free block, adjusting
76     /// bits in the object headers, and adding an end of region memory block.
77     FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList);
78 
79     /// TrimAllocationToSize - If this allocated block is significantly larger
80     /// than NewSize, split it into two pieces (where the former is NewSize
81     /// bytes, including the header), and add the new block to the free list.
82     FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList,
83                                           uint64_t NewSize);
84   };
85 
86   /// FreeRangeHeader - For a memory block that isn't already allocated, this
87   /// keeps track of the current block and has a pointer to the next free block.
88   /// Free blocks are kept on a circularly linked list.
89   struct FreeRangeHeader : public MemoryRangeHeader {
90     FreeRangeHeader *Prev;
91     FreeRangeHeader *Next;
92 
93     /// getMinBlockSize - Get the minimum size for a memory block.  Blocks
94     /// smaller than this size cannot be created.
getMinBlockSize__anone29d22b10111::FreeRangeHeader95     static unsigned getMinBlockSize() {
96       return sizeof(FreeRangeHeader)+sizeof(intptr_t);
97     }
98 
99     /// SetEndOfBlockSizeMarker - The word at the end of every free block is
100     /// known to be the size of the free block.  Set it for this block.
SetEndOfBlockSizeMarker__anone29d22b10111::FreeRangeHeader101     void SetEndOfBlockSizeMarker() {
102       void *EndOfBlock = (char*)this + BlockSize;
103       ((intptr_t *)EndOfBlock)[-1] = BlockSize;
104     }
105 
RemoveFromFreeList__anone29d22b10111::FreeRangeHeader106     FreeRangeHeader *RemoveFromFreeList() {
107       assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
108       Next->Prev = Prev;
109       return Prev->Next = Next;
110     }
111 
AddToFreeList__anone29d22b10111::FreeRangeHeader112     void AddToFreeList(FreeRangeHeader *FreeList) {
113       Next = FreeList;
114       Prev = FreeList->Prev;
115       Prev->Next = this;
116       Next->Prev = this;
117     }
118 
119     /// GrowBlock - The block after this block just got deallocated.  Merge it
120     /// into the current block.
121     void GrowBlock(uintptr_t NewSize);
122 
123     /// AllocateBlock - Mark this entire block allocated, updating freelists
124     /// etc.  This returns a pointer to the circular free-list.
125     FreeRangeHeader *AllocateBlock();
126   };
127 }
128 
129 
130 /// AllocateBlock - Mark this entire block allocated, updating freelists
131 /// etc.  This returns a pointer to the circular free-list.
AllocateBlock()132 FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
133   assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
134          "Cannot allocate an allocated block!");
135   // Mark this block allocated.
136   ThisAllocated = 1;
137   getBlockAfter().PrevAllocated = 1;
138 
139   // Remove it from the free list.
140   return RemoveFromFreeList();
141 }
142 
143 /// FreeBlock - Turn an allocated block into a free block, adjusting
144 /// bits in the object headers, and adding an end of region memory block.
145 /// If possible, coalesce this block with neighboring blocks.  Return the
146 /// FreeRangeHeader to allocate from.
FreeBlock(FreeRangeHeader * FreeList)147 FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) {
148   MemoryRangeHeader *FollowingBlock = &getBlockAfter();
149   assert(ThisAllocated && "This block is already free!");
150   assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
151 
152   FreeRangeHeader *FreeListToReturn = FreeList;
153 
154   // If the block after this one is free, merge it into this block.
155   if (!FollowingBlock->ThisAllocated) {
156     FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
157     // "FreeList" always needs to be a valid free block.  If we're about to
158     // coalesce with it, update our notion of what the free list is.
159     if (&FollowingFreeBlock == FreeList) {
160       FreeList = FollowingFreeBlock.Next;
161       FreeListToReturn = 0;
162       assert(&FollowingFreeBlock != FreeList && "No tombstone block?");
163     }
164     FollowingFreeBlock.RemoveFromFreeList();
165 
166     // Include the following block into this one.
167     BlockSize += FollowingFreeBlock.BlockSize;
168     FollowingBlock = &FollowingFreeBlock.getBlockAfter();
169 
170     // Tell the block after the block we are coalescing that this block is
171     // allocated.
172     FollowingBlock->PrevAllocated = 1;
173   }
174 
175   assert(FollowingBlock->ThisAllocated && "Missed coalescing?");
176 
177   if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
178     PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
179     return FreeListToReturn ? FreeListToReturn : PrevFreeBlock;
180   }
181 
182   // Otherwise, mark this block free.
183   FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
184   FollowingBlock->PrevAllocated = 0;
185   FreeBlock.ThisAllocated = 0;
186 
187   // Link this into the linked list of free blocks.
188   FreeBlock.AddToFreeList(FreeList);
189 
190   // Add a marker at the end of the block, indicating the size of this free
191   // block.
192   FreeBlock.SetEndOfBlockSizeMarker();
193   return FreeListToReturn ? FreeListToReturn : &FreeBlock;
194 }
195 
196 /// GrowBlock - The block after this block just got deallocated.  Merge it
197 /// into the current block.
GrowBlock(uintptr_t NewSize)198 void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
199   assert(NewSize > BlockSize && "Not growing block?");
200   BlockSize = NewSize;
201   SetEndOfBlockSizeMarker();
202   getBlockAfter().PrevAllocated = 0;
203 }
204 
205 /// TrimAllocationToSize - If this allocated block is significantly larger
206 /// than NewSize, split it into two pieces (where the former is NewSize
207 /// bytes, including the header), and add the new block to the free list.
208 FreeRangeHeader *MemoryRangeHeader::
TrimAllocationToSize(FreeRangeHeader * FreeList,uint64_t NewSize)209 TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
210   assert(ThisAllocated && getBlockAfter().PrevAllocated &&
211          "Cannot deallocate part of an allocated block!");
212 
213   // Don't allow blocks to be trimmed below minimum required size
214   NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize);
215 
216   // Round up size for alignment of header.
217   unsigned HeaderAlign = __alignof(FreeRangeHeader);
218   NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
219 
220   // Size is now the size of the block we will remove from the start of the
221   // current block.
222   assert(NewSize <= BlockSize &&
223          "Allocating more space from this block than exists!");
224 
225   // If splitting this block will cause the remainder to be too small, do not
226   // split the block.
227   if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
228     return FreeList;
229 
230   // Otherwise, we splice the required number of bytes out of this block, form
231   // a new block immediately after it, then mark this block allocated.
232   MemoryRangeHeader &FormerNextBlock = getBlockAfter();
233 
234   // Change the size of this block.
235   BlockSize = NewSize;
236 
237   // Get the new block we just sliced out and turn it into a free block.
238   FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
239   NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
240   NewNextBlock.ThisAllocated = 0;
241   NewNextBlock.PrevAllocated = 1;
242   NewNextBlock.SetEndOfBlockSizeMarker();
243   FormerNextBlock.PrevAllocated = 0;
244   NewNextBlock.AddToFreeList(FreeList);
245   return &NewNextBlock;
246 }
247 
248 //===----------------------------------------------------------------------===//
249 // Memory Block Implementation.
250 //===----------------------------------------------------------------------===//
251 
252 namespace {
253 
254   class DefaultJITMemoryManager;
255 
256   class JITSlabAllocator : public SlabAllocator {
257     DefaultJITMemoryManager &JMM;
258   public:
JITSlabAllocator(DefaultJITMemoryManager & jmm)259     JITSlabAllocator(DefaultJITMemoryManager &jmm) : JMM(jmm) { }
~JITSlabAllocator()260     virtual ~JITSlabAllocator() { }
261     virtual MemSlab *Allocate(size_t Size);
262     virtual void Deallocate(MemSlab *Slab);
263   };
264 
265   /// DefaultJITMemoryManager - Manage memory for the JIT code generation.
266   /// This splits a large block of MAP_NORESERVE'd memory into two
267   /// sections, one for function stubs, one for the functions themselves.  We
268   /// have to do this because we may need to emit a function stub while in the
269   /// middle of emitting a function, and we don't know how large the function we
270   /// are emitting is.
271   class DefaultJITMemoryManager : public JITMemoryManager {
272 
273     // Whether to poison freed memory.
274     bool PoisonMemory;
275 
276     /// LastSlab - This points to the last slab allocated and is used as the
277     /// NearBlock parameter to AllocateRWX so that we can attempt to lay out all
278     /// stubs, data, and code contiguously in memory.  In general, however, this
279     /// is not possible because the NearBlock parameter is ignored on Windows
280     /// platforms and even on Unix it works on a best-effort pasis.
281     sys::MemoryBlock LastSlab;
282 
283     // Memory slabs allocated by the JIT.  We refer to them as slabs so we don't
284     // confuse them with the blocks of memory described above.
285     std::vector<sys::MemoryBlock> CodeSlabs;
286     JITSlabAllocator BumpSlabAllocator;
287     BumpPtrAllocator StubAllocator;
288     BumpPtrAllocator DataAllocator;
289 
290     // Circular list of free blocks.
291     FreeRangeHeader *FreeMemoryList;
292 
293     // When emitting code into a memory block, this is the block.
294     MemoryRangeHeader *CurBlock;
295 
296     uint8_t *GOTBase;     // Target Specific reserved memory
297   public:
298     DefaultJITMemoryManager();
299     ~DefaultJITMemoryManager();
300 
301     /// allocateNewSlab - Allocates a new MemoryBlock and remembers it as the
302     /// last slab it allocated, so that subsequent allocations follow it.
303     sys::MemoryBlock allocateNewSlab(size_t size);
304 
305     /// DefaultCodeSlabSize - When we have to go map more memory, we allocate at
306     /// least this much unless more is requested.
307     static const size_t DefaultCodeSlabSize;
308 
309     /// DefaultSlabSize - Allocate data into slabs of this size unless we get
310     /// an allocation above SizeThreshold.
311     static const size_t DefaultSlabSize;
312 
313     /// DefaultSizeThreshold - For any allocation larger than this threshold, we
314     /// should allocate a separate slab.
315     static const size_t DefaultSizeThreshold;
316 
317     void AllocateGOT();
318 
319     // Testing methods.
320     virtual bool CheckInvariants(std::string &ErrorStr);
GetDefaultCodeSlabSize()321     size_t GetDefaultCodeSlabSize() { return DefaultCodeSlabSize; }
GetDefaultDataSlabSize()322     size_t GetDefaultDataSlabSize() { return DefaultSlabSize; }
GetDefaultStubSlabSize()323     size_t GetDefaultStubSlabSize() { return DefaultSlabSize; }
GetNumCodeSlabs()324     unsigned GetNumCodeSlabs() { return CodeSlabs.size(); }
GetNumDataSlabs()325     unsigned GetNumDataSlabs() { return DataAllocator.GetNumSlabs(); }
GetNumStubSlabs()326     unsigned GetNumStubSlabs() { return StubAllocator.GetNumSlabs(); }
327 
328     /// startFunctionBody - When a function starts, allocate a block of free
329     /// executable memory, returning a pointer to it and its actual size.
startFunctionBody(const Function * F,uintptr_t & ActualSize)330     uint8_t *startFunctionBody(const Function *F, uintptr_t &ActualSize) {
331 
332       FreeRangeHeader* candidateBlock = FreeMemoryList;
333       FreeRangeHeader* head = FreeMemoryList;
334       FreeRangeHeader* iter = head->Next;
335 
336       uintptr_t largest = candidateBlock->BlockSize;
337 
338       // Search for the largest free block
339       while (iter != head) {
340         if (iter->BlockSize > largest) {
341           largest = iter->BlockSize;
342           candidateBlock = iter;
343         }
344         iter = iter->Next;
345       }
346 
347       largest = largest - sizeof(MemoryRangeHeader);
348 
349       // If this block isn't big enough for the allocation desired, allocate
350       // another block of memory and add it to the free list.
351       if (largest < ActualSize ||
352           largest <= FreeRangeHeader::getMinBlockSize()) {
353         DEBUG(dbgs() << "JIT: Allocating another slab of memory for function.");
354         candidateBlock = allocateNewCodeSlab((size_t)ActualSize);
355       }
356 
357       // Select this candidate block for allocation
358       CurBlock = candidateBlock;
359 
360       // Allocate the entire memory block.
361       FreeMemoryList = candidateBlock->AllocateBlock();
362       ActualSize = CurBlock->BlockSize - sizeof(MemoryRangeHeader);
363       return (uint8_t *)(CurBlock + 1);
364     }
365 
366     /// allocateNewCodeSlab - Helper method to allocate a new slab of code
367     /// memory from the OS and add it to the free list.  Returns the new
368     /// FreeRangeHeader at the base of the slab.
allocateNewCodeSlab(size_t MinSize)369     FreeRangeHeader *allocateNewCodeSlab(size_t MinSize) {
370       // If the user needs at least MinSize free memory, then we account for
371       // two MemoryRangeHeaders: the one in the user's block, and the one at the
372       // end of the slab.
373       size_t PaddedMin = MinSize + 2 * sizeof(MemoryRangeHeader);
374       size_t SlabSize = std::max(DefaultCodeSlabSize, PaddedMin);
375       sys::MemoryBlock B = allocateNewSlab(SlabSize);
376       CodeSlabs.push_back(B);
377       char *MemBase = (char*)(B.base());
378 
379       // Put a tiny allocated block at the end of the memory chunk, so when
380       // FreeBlock calls getBlockAfter it doesn't fall off the end.
381       MemoryRangeHeader *EndBlock =
382           (MemoryRangeHeader*)(MemBase + B.size()) - 1;
383       EndBlock->ThisAllocated = 1;
384       EndBlock->PrevAllocated = 0;
385       EndBlock->BlockSize = sizeof(MemoryRangeHeader);
386 
387       // Start out with a vast new block of free memory.
388       FreeRangeHeader *NewBlock = (FreeRangeHeader*)MemBase;
389       NewBlock->ThisAllocated = 0;
390       // Make sure getFreeBlockBefore doesn't look into unmapped memory.
391       NewBlock->PrevAllocated = 1;
392       NewBlock->BlockSize = (uintptr_t)EndBlock - (uintptr_t)NewBlock;
393       NewBlock->SetEndOfBlockSizeMarker();
394       NewBlock->AddToFreeList(FreeMemoryList);
395 
396       assert(NewBlock->BlockSize - sizeof(MemoryRangeHeader) >= MinSize &&
397              "The block was too small!");
398       return NewBlock;
399     }
400 
401     /// endFunctionBody - The function F is now allocated, and takes the memory
402     /// in the range [FunctionStart,FunctionEnd).
endFunctionBody(const Function * F,uint8_t * FunctionStart,uint8_t * FunctionEnd)403     void endFunctionBody(const Function *F, uint8_t *FunctionStart,
404                          uint8_t *FunctionEnd) {
405       assert(FunctionEnd > FunctionStart);
406       assert(FunctionStart == (uint8_t *)(CurBlock+1) &&
407              "Mismatched function start/end!");
408 
409       uintptr_t BlockSize = FunctionEnd - (uint8_t *)CurBlock;
410 
411       // Release the memory at the end of this block that isn't needed.
412       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
413     }
414 
415     /// allocateSpace - Allocate a memory block of the given size.  This method
416     /// cannot be called between calls to startFunctionBody and endFunctionBody.
allocateSpace(intptr_t Size,unsigned Alignment)417     uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) {
418       CurBlock = FreeMemoryList;
419       FreeMemoryList = FreeMemoryList->AllocateBlock();
420 
421       uint8_t *result = (uint8_t *)(CurBlock + 1);
422 
423       if (Alignment == 0) Alignment = 1;
424       result = (uint8_t*)(((intptr_t)result+Alignment-1) &
425                ~(intptr_t)(Alignment-1));
426 
427       uintptr_t BlockSize = result + Size - (uint8_t *)CurBlock;
428       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
429 
430       return result;
431     }
432 
433     /// allocateStub - Allocate memory for a function stub.
allocateStub(const GlobalValue * F,unsigned StubSize,unsigned Alignment)434     uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize,
435                           unsigned Alignment) {
436       return (uint8_t*)StubAllocator.Allocate(StubSize, Alignment);
437     }
438 
439     /// allocateGlobal - Allocate memory for a global.
allocateGlobal(uintptr_t Size,unsigned Alignment)440     uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) {
441       return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
442     }
443 
444     /// startExceptionTable - Use startFunctionBody to allocate memory for the
445     /// function's exception table.
startExceptionTable(const Function * F,uintptr_t & ActualSize)446     uint8_t* startExceptionTable(const Function* F, uintptr_t &ActualSize) {
447       return startFunctionBody(F, ActualSize);
448     }
449 
450     /// endExceptionTable - The exception table of F is now allocated,
451     /// and takes the memory in the range [TableStart,TableEnd).
endExceptionTable(const Function * F,uint8_t * TableStart,uint8_t * TableEnd,uint8_t * FrameRegister)452     void endExceptionTable(const Function *F, uint8_t *TableStart,
453                            uint8_t *TableEnd, uint8_t* FrameRegister) {
454       assert(TableEnd > TableStart);
455       assert(TableStart == (uint8_t *)(CurBlock+1) &&
456              "Mismatched table start/end!");
457 
458       uintptr_t BlockSize = TableEnd - (uint8_t *)CurBlock;
459 
460       // Release the memory at the end of this block that isn't needed.
461       FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
462     }
463 
getGOTBase() const464     uint8_t *getGOTBase() const {
465       return GOTBase;
466     }
467 
deallocateBlock(void * Block)468     void deallocateBlock(void *Block) {
469       // Find the block that is allocated for this function.
470       MemoryRangeHeader *MemRange = static_cast<MemoryRangeHeader*>(Block) - 1;
471       assert(MemRange->ThisAllocated && "Block isn't allocated!");
472 
473       // Fill the buffer with garbage!
474       if (PoisonMemory) {
475         memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
476       }
477 
478       // Free the memory.
479       FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
480     }
481 
482     /// deallocateFunctionBody - Deallocate all memory for the specified
483     /// function body.
deallocateFunctionBody(void * Body)484     void deallocateFunctionBody(void *Body) {
485       if (Body) deallocateBlock(Body);
486     }
487 
488     /// deallocateExceptionTable - Deallocate memory for the specified
489     /// exception table.
deallocateExceptionTable(void * ET)490     void deallocateExceptionTable(void *ET) {
491       if (ET) deallocateBlock(ET);
492     }
493 
494     /// setMemoryWritable - When code generation is in progress,
495     /// the code pages may need permissions changed.
setMemoryWritable()496     void setMemoryWritable()
497     {
498       for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
499         sys::Memory::setWritable(CodeSlabs[i]);
500     }
501     /// setMemoryExecutable - When code generation is done and we're ready to
502     /// start execution, the code pages may need permissions changed.
setMemoryExecutable()503     void setMemoryExecutable()
504     {
505       for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
506         sys::Memory::setExecutable(CodeSlabs[i]);
507     }
508 
509     /// setPoisonMemory - Controls whether we write garbage over freed memory.
510     ///
setPoisonMemory(bool poison)511     void setPoisonMemory(bool poison) {
512       PoisonMemory = poison;
513     }
514   };
515 }
516 
Allocate(size_t Size)517 MemSlab *JITSlabAllocator::Allocate(size_t Size) {
518   sys::MemoryBlock B = JMM.allocateNewSlab(Size);
519   MemSlab *Slab = (MemSlab*)B.base();
520   Slab->Size = B.size();
521   Slab->NextPtr = 0;
522   return Slab;
523 }
524 
Deallocate(MemSlab * Slab)525 void JITSlabAllocator::Deallocate(MemSlab *Slab) {
526   sys::MemoryBlock B(Slab, Slab->Size);
527   sys::Memory::ReleaseRWX(B);
528 }
529 
DefaultJITMemoryManager()530 DefaultJITMemoryManager::DefaultJITMemoryManager()
531   :
532 #ifdef NDEBUG
533     PoisonMemory(false),
534 #else
535     PoisonMemory(true),
536 #endif
537     LastSlab(0, 0),
538     BumpSlabAllocator(*this),
539     StubAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator),
540     DataAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator) {
541 
542   // Allocate space for code.
543   sys::MemoryBlock MemBlock = allocateNewSlab(DefaultCodeSlabSize);
544   CodeSlabs.push_back(MemBlock);
545   uint8_t *MemBase = (uint8_t*)MemBlock.base();
546 
547   // We set up the memory chunk with 4 mem regions, like this:
548   //  [ START
549   //    [ Free      #0 ] -> Large space to allocate functions from.
550   //    [ Allocated #1 ] -> Tiny space to separate regions.
551   //    [ Free      #2 ] -> Tiny space so there is always at least 1 free block.
552   //    [ Allocated #3 ] -> Tiny space to prevent looking past end of block.
553   //  END ]
554   //
555   // The last three blocks are never deallocated or touched.
556 
557   // Add MemoryRangeHeader to the end of the memory region, indicating that
558   // the space after the block of memory is allocated.  This is block #3.
559   MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
560   Mem3->ThisAllocated = 1;
561   Mem3->PrevAllocated = 0;
562   Mem3->BlockSize     = sizeof(MemoryRangeHeader);
563 
564   /// Add a tiny free region so that the free list always has one entry.
565   FreeRangeHeader *Mem2 =
566     (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
567   Mem2->ThisAllocated = 0;
568   Mem2->PrevAllocated = 1;
569   Mem2->BlockSize     = FreeRangeHeader::getMinBlockSize();
570   Mem2->SetEndOfBlockSizeMarker();
571   Mem2->Prev = Mem2;   // Mem2 *is* the free list for now.
572   Mem2->Next = Mem2;
573 
574   /// Add a tiny allocated region so that Mem2 is never coalesced away.
575   MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
576   Mem1->ThisAllocated = 1;
577   Mem1->PrevAllocated = 0;
578   Mem1->BlockSize     = sizeof(MemoryRangeHeader);
579 
580   // Add a FreeRangeHeader to the start of the function body region, indicating
581   // that the space is free.  Mark the previous block allocated so we never look
582   // at it.
583   FreeRangeHeader *Mem0 = (FreeRangeHeader*)MemBase;
584   Mem0->ThisAllocated = 0;
585   Mem0->PrevAllocated = 1;
586   Mem0->BlockSize = (char*)Mem1-(char*)Mem0;
587   Mem0->SetEndOfBlockSizeMarker();
588   Mem0->AddToFreeList(Mem2);
589 
590   // Start out with the freelist pointing to Mem0.
591   FreeMemoryList = Mem0;
592 
593   GOTBase = NULL;
594 }
595 
AllocateGOT()596 void DefaultJITMemoryManager::AllocateGOT() {
597   assert(GOTBase == 0 && "Cannot allocate the got multiple times");
598   GOTBase = new uint8_t[sizeof(void*) * 8192];
599   HasGOT = true;
600 }
601 
~DefaultJITMemoryManager()602 DefaultJITMemoryManager::~DefaultJITMemoryManager() {
603   for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
604     sys::Memory::ReleaseRWX(CodeSlabs[i]);
605 
606   delete[] GOTBase;
607 }
608 
allocateNewSlab(size_t size)609 sys::MemoryBlock DefaultJITMemoryManager::allocateNewSlab(size_t size) {
610   // Allocate a new block close to the last one.
611   std::string ErrMsg;
612   sys::MemoryBlock *LastSlabPtr = LastSlab.base() ? &LastSlab : 0;
613   sys::MemoryBlock B = sys::Memory::AllocateRWX(size, LastSlabPtr, &ErrMsg);
614   if (B.base() == 0) {
615     report_fatal_error("Allocation failed when allocating new memory in the"
616                        " JIT\n" + Twine(ErrMsg));
617   }
618   LastSlab = B;
619   ++NumSlabs;
620   // Initialize the slab to garbage when debugging.
621   if (PoisonMemory) {
622     memset(B.base(), 0xCD, B.size());
623   }
624   return B;
625 }
626 
627 /// CheckInvariants - For testing only.  Return "" if all internal invariants
628 /// are preserved, and a helpful error message otherwise.  For free and
629 /// allocated blocks, make sure that adding BlockSize gives a valid block.
630 /// For free blocks, make sure they're in the free list and that their end of
631 /// block size marker is correct.  This function should return an error before
632 /// accessing bad memory.  This function is defined here instead of in
633 /// JITMemoryManagerTest.cpp so that we don't have to expose all of the
634 /// implementation details of DefaultJITMemoryManager.
CheckInvariants(std::string & ErrorStr)635 bool DefaultJITMemoryManager::CheckInvariants(std::string &ErrorStr) {
636   raw_string_ostream Err(ErrorStr);
637 
638   // Construct a the set of FreeRangeHeader pointers so we can query it
639   // efficiently.
640   llvm::SmallPtrSet<MemoryRangeHeader*, 16> FreeHdrSet;
641   FreeRangeHeader* FreeHead = FreeMemoryList;
642   FreeRangeHeader* FreeRange = FreeHead;
643 
644   do {
645     // Check that the free range pointer is in the blocks we've allocated.
646     bool Found = false;
647     for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
648          E = CodeSlabs.end(); I != E && !Found; ++I) {
649       char *Start = (char*)I->base();
650       char *End = Start + I->size();
651       Found = (Start <= (char*)FreeRange && (char*)FreeRange < End);
652     }
653     if (!Found) {
654       Err << "Corrupt free list; points to " << FreeRange;
655       return false;
656     }
657 
658     if (FreeRange->Next->Prev != FreeRange) {
659       Err << "Next and Prev pointers do not match.";
660       return false;
661     }
662 
663     // Otherwise, add it to the set.
664     FreeHdrSet.insert(FreeRange);
665     FreeRange = FreeRange->Next;
666   } while (FreeRange != FreeHead);
667 
668   // Go over each block, and look at each MemoryRangeHeader.
669   for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
670        E = CodeSlabs.end(); I != E; ++I) {
671     char *Start = (char*)I->base();
672     char *End = Start + I->size();
673 
674     // Check each memory range.
675     for (MemoryRangeHeader *Hdr = (MemoryRangeHeader*)Start, *LastHdr = NULL;
676          Start <= (char*)Hdr && (char*)Hdr < End;
677          Hdr = &Hdr->getBlockAfter()) {
678       if (Hdr->ThisAllocated == 0) {
679         // Check that this range is in the free list.
680         if (!FreeHdrSet.count(Hdr)) {
681           Err << "Found free header at " << Hdr << " that is not in free list.";
682           return false;
683         }
684 
685         // Now make sure the size marker at the end of the block is correct.
686         uintptr_t *Marker = ((uintptr_t*)&Hdr->getBlockAfter()) - 1;
687         if (!(Start <= (char*)Marker && (char*)Marker < End)) {
688           Err << "Block size in header points out of current MemoryBlock.";
689           return false;
690         }
691         if (Hdr->BlockSize != *Marker) {
692           Err << "End of block size marker (" << *Marker << ") "
693               << "and BlockSize (" << Hdr->BlockSize << ") don't match.";
694           return false;
695         }
696       }
697 
698       if (LastHdr && LastHdr->ThisAllocated != Hdr->PrevAllocated) {
699         Err << "Hdr->PrevAllocated (" << Hdr->PrevAllocated << ") != "
700             << "LastHdr->ThisAllocated (" << LastHdr->ThisAllocated << ")";
701         return false;
702       } else if (!LastHdr && !Hdr->PrevAllocated) {
703         Err << "The first header should have PrevAllocated true.";
704         return false;
705       }
706 
707       // Remember the last header.
708       LastHdr = Hdr;
709     }
710   }
711 
712   // All invariants are preserved.
713   return true;
714 }
715 
CreateDefaultMemManager()716 JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() {
717   return new DefaultJITMemoryManager();
718 }
719 
720 // Allocate memory for code in 512K slabs.
721 const size_t DefaultJITMemoryManager::DefaultCodeSlabSize = 512 * 1024;
722 
723 // Allocate globals and stubs in slabs of 64K.  (probably 16 pages)
724 const size_t DefaultJITMemoryManager::DefaultSlabSize = 64 * 1024;
725 
726 // Waste at most 16K at the end of each bump slab.  (probably 4 pages)
727 const size_t DefaultJITMemoryManager::DefaultSizeThreshold = 16 * 1024;
728