blob: 80cb999a90ac8651c81dfc7a19dfd3351e9acf7d [file] [log] [blame]
Chris Lattner8907b4b2007-12-05 23:39:57 +00001//===-- JITMemoryManager.cpp - Memory Allocator for JIT'd code ------------===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Chris Lattner8907b4b2007-12-05 23:39:57 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the DefaultJITMemoryManager class.
11//
12//===----------------------------------------------------------------------===//
13
Reid Kleckner10b4fc52009-07-23 21:46:56 +000014#define DEBUG_TYPE "jit"
Reid Kleckner4bf37062009-07-23 01:40:54 +000015#include "llvm/ExecutionEngine/JITMemoryManager.h"
Reid Kleckner10b4fc52009-07-23 21:46:56 +000016#include "llvm/ADT/SmallPtrSet.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/GlobalValue.h"
19#include "llvm/Support/Allocator.h"
Chris Lattner8907b4b2007-12-05 23:39:57 +000020#include "llvm/Support/Compiler.h"
Reid Kleckner10b4fc52009-07-23 21:46:56 +000021#include "llvm/Support/Debug.h"
Torok Edwin7d696d82009-07-11 13:10:19 +000022#include "llvm/Support/ErrorHandling.h"
Reid Kleckner10b4fc52009-07-23 21:46:56 +000023#include "llvm/Support/raw_ostream.h"
Chris Lattner8907b4b2007-12-05 23:39:57 +000024#include "llvm/System/Memory.h"
25#include <map>
26#include <vector>
Chuck Rose III3012ac62007-12-06 02:03:01 +000027#include <cassert>
Dan Gohmande551f92009-04-01 18:45:54 +000028#include <climits>
Duncan Sands4520dd22008-10-08 07:23:46 +000029#include <cstdio>
Anton Korobeynikovae9f3a32008-02-20 11:08:44 +000030#include <cstdlib>
31#include <cstring>
Chris Lattner8907b4b2007-12-05 23:39:57 +000032using namespace llvm;
33
Reid Kleckner10b4fc52009-07-23 21:46:56 +000034STATISTIC(NumSlabs, "Number of slabs of memory allocated by the JIT");
Chris Lattner8907b4b2007-12-05 23:39:57 +000035
36JITMemoryManager::~JITMemoryManager() {}
37
38//===----------------------------------------------------------------------===//
39// Memory Block Implementation.
40//===----------------------------------------------------------------------===//
41
42namespace {
43 /// MemoryRangeHeader - For a range of memory, this is the header that we put
44 /// on the block of memory. It is carefully crafted to be one word of memory.
45 /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader
46 /// which starts with this.
47 struct FreeRangeHeader;
48 struct MemoryRangeHeader {
49 /// ThisAllocated - This is true if this block is currently allocated. If
50 /// not, this can be converted to a FreeRangeHeader.
51 unsigned ThisAllocated : 1;
Eric Christopher5cf0aed2009-11-12 01:06:08 +000052
Chris Lattner8907b4b2007-12-05 23:39:57 +000053 /// PrevAllocated - Keep track of whether the block immediately before us is
54 /// allocated. If not, the word immediately before this header is the size
55 /// of the previous block.
56 unsigned PrevAllocated : 1;
Eric Christopher5cf0aed2009-11-12 01:06:08 +000057
Chris Lattner8907b4b2007-12-05 23:39:57 +000058 /// BlockSize - This is the size in bytes of this memory block,
59 /// including this header.
Dan Gohmande551f92009-04-01 18:45:54 +000060 uintptr_t BlockSize : (sizeof(intptr_t)*CHAR_BIT - 2);
Eric Christopher5cf0aed2009-11-12 01:06:08 +000061
Chris Lattner8907b4b2007-12-05 23:39:57 +000062
63 /// getBlockAfter - Return the memory block immediately after this one.
64 ///
65 MemoryRangeHeader &getBlockAfter() const {
66 return *(MemoryRangeHeader*)((char*)this+BlockSize);
67 }
Eric Christopher5cf0aed2009-11-12 01:06:08 +000068
Chris Lattner8907b4b2007-12-05 23:39:57 +000069 /// getFreeBlockBefore - If the block before this one is free, return it,
70 /// otherwise return null.
71 FreeRangeHeader *getFreeBlockBefore() const {
72 if (PrevAllocated) return 0;
73 intptr_t PrevSize = ((intptr_t *)this)[-1];
74 return (FreeRangeHeader*)((char*)this-PrevSize);
75 }
Eric Christopher5cf0aed2009-11-12 01:06:08 +000076
Chris Lattner8907b4b2007-12-05 23:39:57 +000077 /// FreeBlock - Turn an allocated block into a free block, adjusting
78 /// bits in the object headers, and adding an end of region memory block.
79 FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList);
Eric Christopher5cf0aed2009-11-12 01:06:08 +000080
Chris Lattner8907b4b2007-12-05 23:39:57 +000081 /// TrimAllocationToSize - If this allocated block is significantly larger
82 /// than NewSize, split it into two pieces (where the former is NewSize
83 /// bytes, including the header), and add the new block to the free list.
Eric Christopher5cf0aed2009-11-12 01:06:08 +000084 FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList,
Chris Lattner8907b4b2007-12-05 23:39:57 +000085 uint64_t NewSize);
86 };
87
88 /// FreeRangeHeader - For a memory block that isn't already allocated, this
89 /// keeps track of the current block and has a pointer to the next free block.
90 /// Free blocks are kept on a circularly linked list.
91 struct FreeRangeHeader : public MemoryRangeHeader {
92 FreeRangeHeader *Prev;
93 FreeRangeHeader *Next;
Eric Christopher5cf0aed2009-11-12 01:06:08 +000094
Chris Lattner8907b4b2007-12-05 23:39:57 +000095 /// getMinBlockSize - Get the minimum size for a memory block. Blocks
96 /// smaller than this size cannot be created.
97 static unsigned getMinBlockSize() {
98 return sizeof(FreeRangeHeader)+sizeof(intptr_t);
99 }
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000100
Chris Lattner8907b4b2007-12-05 23:39:57 +0000101 /// SetEndOfBlockSizeMarker - The word at the end of every free block is
102 /// known to be the size of the free block. Set it for this block.
103 void SetEndOfBlockSizeMarker() {
104 void *EndOfBlock = (char*)this + BlockSize;
105 ((intptr_t *)EndOfBlock)[-1] = BlockSize;
106 }
107
108 FreeRangeHeader *RemoveFromFreeList() {
109 assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
110 Next->Prev = Prev;
111 return Prev->Next = Next;
112 }
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000113
Chris Lattner8907b4b2007-12-05 23:39:57 +0000114 void AddToFreeList(FreeRangeHeader *FreeList) {
115 Next = FreeList;
116 Prev = FreeList->Prev;
117 Prev->Next = this;
118 Next->Prev = this;
119 }
120
121 /// GrowBlock - The block after this block just got deallocated. Merge it
122 /// into the current block.
123 void GrowBlock(uintptr_t NewSize);
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000124
Chris Lattner8907b4b2007-12-05 23:39:57 +0000125 /// AllocateBlock - Mark this entire block allocated, updating freelists
126 /// etc. This returns a pointer to the circular free-list.
127 FreeRangeHeader *AllocateBlock();
128 };
129}
130
131
132/// AllocateBlock - Mark this entire block allocated, updating freelists
133/// etc. This returns a pointer to the circular free-list.
134FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
135 assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
136 "Cannot allocate an allocated block!");
137 // Mark this block allocated.
138 ThisAllocated = 1;
139 getBlockAfter().PrevAllocated = 1;
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000140
Chris Lattner8907b4b2007-12-05 23:39:57 +0000141 // Remove it from the free list.
142 return RemoveFromFreeList();
143}
144
145/// FreeBlock - Turn an allocated block into a free block, adjusting
146/// bits in the object headers, and adding an end of region memory block.
147/// If possible, coalesce this block with neighboring blocks. Return the
148/// FreeRangeHeader to allocate from.
149FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) {
150 MemoryRangeHeader *FollowingBlock = &getBlockAfter();
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000151 assert(ThisAllocated && "This block is already free!");
Chris Lattner8907b4b2007-12-05 23:39:57 +0000152 assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000153
Chris Lattner8907b4b2007-12-05 23:39:57 +0000154 FreeRangeHeader *FreeListToReturn = FreeList;
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000155
Chris Lattner8907b4b2007-12-05 23:39:57 +0000156 // If the block after this one is free, merge it into this block.
157 if (!FollowingBlock->ThisAllocated) {
158 FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
159 // "FreeList" always needs to be a valid free block. If we're about to
160 // coalesce with it, update our notion of what the free list is.
161 if (&FollowingFreeBlock == FreeList) {
162 FreeList = FollowingFreeBlock.Next;
163 FreeListToReturn = 0;
164 assert(&FollowingFreeBlock != FreeList && "No tombstone block?");
165 }
166 FollowingFreeBlock.RemoveFromFreeList();
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000167
Chris Lattner8907b4b2007-12-05 23:39:57 +0000168 // Include the following block into this one.
169 BlockSize += FollowingFreeBlock.BlockSize;
170 FollowingBlock = &FollowingFreeBlock.getBlockAfter();
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000171
Chris Lattner8907b4b2007-12-05 23:39:57 +0000172 // Tell the block after the block we are coalescing that this block is
173 // allocated.
174 FollowingBlock->PrevAllocated = 1;
175 }
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000176
Chris Lattner8907b4b2007-12-05 23:39:57 +0000177 assert(FollowingBlock->ThisAllocated && "Missed coalescing?");
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000178
Chris Lattner8907b4b2007-12-05 23:39:57 +0000179 if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
180 PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
181 return FreeListToReturn ? FreeListToReturn : PrevFreeBlock;
182 }
183
184 // Otherwise, mark this block free.
185 FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
186 FollowingBlock->PrevAllocated = 0;
187 FreeBlock.ThisAllocated = 0;
188
189 // Link this into the linked list of free blocks.
190 FreeBlock.AddToFreeList(FreeList);
191
192 // Add a marker at the end of the block, indicating the size of this free
193 // block.
194 FreeBlock.SetEndOfBlockSizeMarker();
195 return FreeListToReturn ? FreeListToReturn : &FreeBlock;
196}
197
198/// GrowBlock - The block after this block just got deallocated. Merge it
199/// into the current block.
200void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
201 assert(NewSize > BlockSize && "Not growing block?");
202 BlockSize = NewSize;
203 SetEndOfBlockSizeMarker();
204 getBlockAfter().PrevAllocated = 0;
205}
206
207/// TrimAllocationToSize - If this allocated block is significantly larger
208/// than NewSize, split it into two pieces (where the former is NewSize
209/// bytes, including the header), and add the new block to the free list.
210FreeRangeHeader *MemoryRangeHeader::
211TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
212 assert(ThisAllocated && getBlockAfter().PrevAllocated &&
213 "Cannot deallocate part of an allocated block!");
214
Evan Cheng60b75f42008-07-29 07:38:32 +0000215 // Don't allow blocks to be trimmed below minimum required size
216 NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize);
217
Chris Lattner8907b4b2007-12-05 23:39:57 +0000218 // Round up size for alignment of header.
219 unsigned HeaderAlign = __alignof(FreeRangeHeader);
220 NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000221
Chris Lattner8907b4b2007-12-05 23:39:57 +0000222 // Size is now the size of the block we will remove from the start of the
223 // current block.
224 assert(NewSize <= BlockSize &&
225 "Allocating more space from this block than exists!");
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000226
Chris Lattner8907b4b2007-12-05 23:39:57 +0000227 // If splitting this block will cause the remainder to be too small, do not
228 // split the block.
229 if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
230 return FreeList;
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000231
Chris Lattner8907b4b2007-12-05 23:39:57 +0000232 // Otherwise, we splice the required number of bytes out of this block, form
233 // a new block immediately after it, then mark this block allocated.
234 MemoryRangeHeader &FormerNextBlock = getBlockAfter();
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000235
Chris Lattner8907b4b2007-12-05 23:39:57 +0000236 // Change the size of this block.
237 BlockSize = NewSize;
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000238
Chris Lattner8907b4b2007-12-05 23:39:57 +0000239 // Get the new block we just sliced out and turn it into a free block.
240 FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
241 NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
242 NewNextBlock.ThisAllocated = 0;
243 NewNextBlock.PrevAllocated = 1;
244 NewNextBlock.SetEndOfBlockSizeMarker();
245 FormerNextBlock.PrevAllocated = 0;
246 NewNextBlock.AddToFreeList(FreeList);
247 return &NewNextBlock;
248}
249
250//===----------------------------------------------------------------------===//
251// Memory Block Implementation.
252//===----------------------------------------------------------------------===//
253
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000254namespace {
255
256 class DefaultJITMemoryManager;
257
258 class JITSlabAllocator : public SlabAllocator {
259 DefaultJITMemoryManager &JMM;
260 public:
261 JITSlabAllocator(DefaultJITMemoryManager &jmm) : JMM(jmm) { }
262 virtual ~JITSlabAllocator() { }
263 virtual MemSlab *Allocate(size_t Size);
264 virtual void Deallocate(MemSlab *Slab);
265 };
266
Chris Lattner8907b4b2007-12-05 23:39:57 +0000267 /// DefaultJITMemoryManager - Manage memory for the JIT code generation.
268 /// This splits a large block of MAP_NORESERVE'd memory into two
269 /// sections, one for function stubs, one for the functions themselves. We
270 /// have to do this because we may need to emit a function stub while in the
271 /// middle of emitting a function, and we don't know how large the function we
272 /// are emitting is.
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000273 class DefaultJITMemoryManager : public JITMemoryManager {
Jeffrey Yasskin489393d2009-07-08 21:59:57 +0000274
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000275 // Whether to poison freed memory.
276 bool PoisonMemory;
277
278 /// LastSlab - This points to the last slab allocated and is used as the
279 /// NearBlock parameter to AllocateRWX so that we can attempt to lay out all
280 /// stubs, data, and code contiguously in memory. In general, however, this
281 /// is not possible because the NearBlock parameter is ignored on Windows
282 /// platforms and even on Unix it works on a best-effort pasis.
283 sys::MemoryBlock LastSlab;
284
285 // Memory slabs allocated by the JIT. We refer to them as slabs so we don't
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000286 // confuse them with the blocks of memory described above.
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000287 std::vector<sys::MemoryBlock> CodeSlabs;
288 JITSlabAllocator BumpSlabAllocator;
289 BumpPtrAllocator StubAllocator;
290 BumpPtrAllocator DataAllocator;
291
292 // Circular list of free blocks.
293 FreeRangeHeader *FreeMemoryList;
294
Chris Lattner8907b4b2007-12-05 23:39:57 +0000295 // When emitting code into a memory block, this is the block.
296 MemoryRangeHeader *CurBlock;
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000297
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000298 uint8_t *GOTBase; // Target Specific reserved memory
Chris Lattner8907b4b2007-12-05 23:39:57 +0000299 public:
300 DefaultJITMemoryManager();
301 ~DefaultJITMemoryManager();
302
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000303 /// allocateNewSlab - Allocates a new MemoryBlock and remembers it as the
304 /// last slab it allocated, so that subsequent allocations follow it.
305 sys::MemoryBlock allocateNewSlab(size_t size);
306
307 /// DefaultCodeSlabSize - When we have to go map more memory, we allocate at
308 /// least this much unless more is requested.
309 static const size_t DefaultCodeSlabSize;
310
311 /// DefaultSlabSize - Allocate data into slabs of this size unless we get
312 /// an allocation above SizeThreshold.
313 static const size_t DefaultSlabSize;
314
315 /// DefaultSizeThreshold - For any allocation larger than this threshold, we
316 /// should allocate a separate slab.
317 static const size_t DefaultSizeThreshold;
318
Chris Lattner8907b4b2007-12-05 23:39:57 +0000319 void AllocateGOT();
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000320
321 // Testing methods.
322 virtual bool CheckInvariants(std::string &ErrorStr);
323 size_t GetDefaultCodeSlabSize() { return DefaultCodeSlabSize; }
324 size_t GetDefaultDataSlabSize() { return DefaultSlabSize; }
325 size_t GetDefaultStubSlabSize() { return DefaultSlabSize; }
326 unsigned GetNumCodeSlabs() { return CodeSlabs.size(); }
327 unsigned GetNumDataSlabs() { return DataAllocator.GetNumSlabs(); }
328 unsigned GetNumStubSlabs() { return StubAllocator.GetNumSlabs(); }
329
Chris Lattner8907b4b2007-12-05 23:39:57 +0000330 /// startFunctionBody - When a function starts, allocate a block of free
331 /// executable memory, returning a pointer to it and its actual size.
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000332 uint8_t *startFunctionBody(const Function *F, uintptr_t &ActualSize) {
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000333
Chris Lattner96c96b42009-03-09 21:34:10 +0000334 FreeRangeHeader* candidateBlock = FreeMemoryList;
335 FreeRangeHeader* head = FreeMemoryList;
336 FreeRangeHeader* iter = head->Next;
337
338 uintptr_t largest = candidateBlock->BlockSize;
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000339
Chris Lattner96c96b42009-03-09 21:34:10 +0000340 // Search for the largest free block
341 while (iter != head) {
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000342 if (iter->BlockSize > largest) {
343 largest = iter->BlockSize;
344 candidateBlock = iter;
345 }
346 iter = iter->Next;
Chris Lattner96c96b42009-03-09 21:34:10 +0000347 }
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000348
Nicolas Geoffray1b10d792009-07-29 22:55:02 +0000349 largest = largest - sizeof(MemoryRangeHeader);
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000350
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000351 // If this block isn't big enough for the allocation desired, allocate
352 // another block of memory and add it to the free list.
Nicolas Geoffray1b10d792009-07-29 22:55:02 +0000353 if (largest < ActualSize ||
354 largest <= FreeRangeHeader::getMinBlockSize()) {
Chris Lattnerbbbfa992009-08-23 06:35:02 +0000355 DEBUG(errs() << "JIT: Allocating another slab of memory for function.");
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000356 candidateBlock = allocateNewCodeSlab((size_t)ActualSize);
357 }
358
Chris Lattner96c96b42009-03-09 21:34:10 +0000359 // Select this candidate block for allocation
360 CurBlock = candidateBlock;
361
Chris Lattner8907b4b2007-12-05 23:39:57 +0000362 // Allocate the entire memory block.
Chris Lattner96c96b42009-03-09 21:34:10 +0000363 FreeMemoryList = candidateBlock->AllocateBlock();
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000364 ActualSize = CurBlock->BlockSize - sizeof(MemoryRangeHeader);
365 return (uint8_t *)(CurBlock + 1);
Chris Lattner8907b4b2007-12-05 23:39:57 +0000366 }
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000367
368 /// allocateNewCodeSlab - Helper method to allocate a new slab of code
369 /// memory from the OS and add it to the free list. Returns the new
370 /// FreeRangeHeader at the base of the slab.
371 FreeRangeHeader *allocateNewCodeSlab(size_t MinSize) {
372 // If the user needs at least MinSize free memory, then we account for
373 // two MemoryRangeHeaders: the one in the user's block, and the one at the
374 // end of the slab.
375 size_t PaddedMin = MinSize + 2 * sizeof(MemoryRangeHeader);
376 size_t SlabSize = std::max(DefaultCodeSlabSize, PaddedMin);
377 sys::MemoryBlock B = allocateNewSlab(SlabSize);
378 CodeSlabs.push_back(B);
379 char *MemBase = (char*)(B.base());
380
381 // Put a tiny allocated block at the end of the memory chunk, so when
382 // FreeBlock calls getBlockAfter it doesn't fall off the end.
383 MemoryRangeHeader *EndBlock =
384 (MemoryRangeHeader*)(MemBase + B.size()) - 1;
385 EndBlock->ThisAllocated = 1;
386 EndBlock->PrevAllocated = 0;
387 EndBlock->BlockSize = sizeof(MemoryRangeHeader);
388
389 // Start out with a vast new block of free memory.
390 FreeRangeHeader *NewBlock = (FreeRangeHeader*)MemBase;
391 NewBlock->ThisAllocated = 0;
392 // Make sure getFreeBlockBefore doesn't look into unmapped memory.
393 NewBlock->PrevAllocated = 1;
394 NewBlock->BlockSize = (uintptr_t)EndBlock - (uintptr_t)NewBlock;
395 NewBlock->SetEndOfBlockSizeMarker();
396 NewBlock->AddToFreeList(FreeMemoryList);
397
398 assert(NewBlock->BlockSize - sizeof(MemoryRangeHeader) >= MinSize &&
399 "The block was too small!");
400 return NewBlock;
401 }
402
Chris Lattner8907b4b2007-12-05 23:39:57 +0000403 /// endFunctionBody - The function F is now allocated, and takes the memory
404 /// in the range [FunctionStart,FunctionEnd).
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000405 void endFunctionBody(const Function *F, uint8_t *FunctionStart,
406 uint8_t *FunctionEnd) {
Chris Lattner8907b4b2007-12-05 23:39:57 +0000407 assert(FunctionEnd > FunctionStart);
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000408 assert(FunctionStart == (uint8_t *)(CurBlock+1) &&
Chris Lattner8907b4b2007-12-05 23:39:57 +0000409 "Mismatched function start/end!");
Dale Johannesendd947ea2008-08-07 01:30:15 +0000410
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000411 uintptr_t BlockSize = FunctionEnd - (uint8_t *)CurBlock;
Chris Lattner8907b4b2007-12-05 23:39:57 +0000412
413 // Release the memory at the end of this block that isn't needed.
414 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
415 }
Nuno Lopescef75272008-10-21 11:42:16 +0000416
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000417 /// allocateSpace - Allocate a memory block of the given size. This method
418 /// cannot be called between calls to startFunctionBody and endFunctionBody.
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000419 uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) {
Nuno Lopescef75272008-10-21 11:42:16 +0000420 CurBlock = FreeMemoryList;
421 FreeMemoryList = FreeMemoryList->AllocateBlock();
422
Jeffrey Yasskin489393d2009-07-08 21:59:57 +0000423 uint8_t *result = (uint8_t *)(CurBlock + 1);
Nuno Lopescef75272008-10-21 11:42:16 +0000424
425 if (Alignment == 0) Alignment = 1;
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000426 result = (uint8_t*)(((intptr_t)result+Alignment-1) &
Nuno Lopescef75272008-10-21 11:42:16 +0000427 ~(intptr_t)(Alignment-1));
428
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000429 uintptr_t BlockSize = result + Size - (uint8_t *)CurBlock;
Nuno Lopescef75272008-10-21 11:42:16 +0000430 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
431
432 return result;
433 }
434
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000435 /// allocateStub - Allocate memory for a function stub.
436 uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize,
437 unsigned Alignment) {
438 return (uint8_t*)StubAllocator.Allocate(StubSize, Alignment);
439 }
440
441 /// allocateGlobal - Allocate memory for a global.
Jeffrey Yasskin489393d2009-07-08 21:59:57 +0000442 uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) {
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000443 return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
Jeffrey Yasskin489393d2009-07-08 21:59:57 +0000444 }
445
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000446 /// startExceptionTable - Use startFunctionBody to allocate memory for the
Nicolas Geoffrayafe6c2b2008-02-13 18:39:37 +0000447 /// function's exception table.
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000448 uint8_t* startExceptionTable(const Function* F, uintptr_t &ActualSize) {
Nicolas Geoffrayafe6c2b2008-02-13 18:39:37 +0000449 return startFunctionBody(F, ActualSize);
450 }
451
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000452 /// endExceptionTable - The exception table of F is now allocated,
Nicolas Geoffrayafe6c2b2008-02-13 18:39:37 +0000453 /// and takes the memory in the range [TableStart,TableEnd).
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000454 void endExceptionTable(const Function *F, uint8_t *TableStart,
455 uint8_t *TableEnd, uint8_t* FrameRegister) {
Nicolas Geoffrayafe6c2b2008-02-13 18:39:37 +0000456 assert(TableEnd > TableStart);
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000457 assert(TableStart == (uint8_t *)(CurBlock+1) &&
Nicolas Geoffrayafe6c2b2008-02-13 18:39:37 +0000458 "Mismatched table start/end!");
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000459
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000460 uintptr_t BlockSize = TableEnd - (uint8_t *)CurBlock;
Nicolas Geoffrayafe6c2b2008-02-13 18:39:37 +0000461
462 // Release the memory at the end of this block that isn't needed.
463 FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
464 }
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000465
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000466 uint8_t *getGOTBase() const {
Chris Lattner8907b4b2007-12-05 23:39:57 +0000467 return GOTBase;
468 }
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000469
Jeffrey Yasskin1e861322009-10-20 18:13:21 +0000470 void deallocateBlock(void *Block) {
471 // Find the block that is allocated for this function.
472 MemoryRangeHeader *MemRange = static_cast<MemoryRangeHeader*>(Block) - 1;
473 assert(MemRange->ThisAllocated && "Block isn't allocated!");
474
475 // Fill the buffer with garbage!
476 if (PoisonMemory) {
477 memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
478 }
479
480 // Free the memory.
481 FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
482 }
483
484 /// deallocateFunctionBody - Deallocate all memory for the specified
Chris Lattner8907b4b2007-12-05 23:39:57 +0000485 /// function body.
Jeffrey Yasskin1e861322009-10-20 18:13:21 +0000486 void deallocateFunctionBody(void *Body) {
Nicolas Geoffray71e0b7c2009-10-22 14:35:57 +0000487 if (Body) deallocateBlock(Body);
Jeffrey Yasskin1e861322009-10-20 18:13:21 +0000488 }
Jeffrey Yasskin489393d2009-07-08 21:59:57 +0000489
Jeffrey Yasskin1e861322009-10-20 18:13:21 +0000490 /// deallocateExceptionTable - Deallocate memory for the specified
491 /// exception table.
492 void deallocateExceptionTable(void *ET) {
Nicolas Geoffray71e0b7c2009-10-22 14:35:57 +0000493 if (ET) deallocateBlock(ET);
Chris Lattner8907b4b2007-12-05 23:39:57 +0000494 }
Jim Grosbachcce6c292008-10-03 16:17:20 +0000495
496 /// setMemoryWritable - When code generation is in progress,
497 /// the code pages may need permissions changed.
Dan Gohmana9ad0412009-08-12 22:10:57 +0000498 void setMemoryWritable()
Jim Grosbachcce6c292008-10-03 16:17:20 +0000499 {
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000500 for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
501 sys::Memory::setWritable(CodeSlabs[i]);
Jim Grosbachcce6c292008-10-03 16:17:20 +0000502 }
503 /// setMemoryExecutable - When code generation is done and we're ready to
504 /// start execution, the code pages may need permissions changed.
Dan Gohmana9ad0412009-08-12 22:10:57 +0000505 void setMemoryExecutable()
Jim Grosbachcce6c292008-10-03 16:17:20 +0000506 {
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000507 for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
508 sys::Memory::setExecutable(CodeSlabs[i]);
Jim Grosbachcce6c292008-10-03 16:17:20 +0000509 }
Jeffrey Yasskin489393d2009-07-08 21:59:57 +0000510
511 /// setPoisonMemory - Controls whether we write garbage over freed memory.
512 ///
513 void setPoisonMemory(bool poison) {
514 PoisonMemory = poison;
515 }
Chris Lattner8907b4b2007-12-05 23:39:57 +0000516 };
517}
518
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000519MemSlab *JITSlabAllocator::Allocate(size_t Size) {
520 sys::MemoryBlock B = JMM.allocateNewSlab(Size);
521 MemSlab *Slab = (MemSlab*)B.base();
522 Slab->Size = B.size();
523 Slab->NextPtr = 0;
524 return Slab;
525}
526
527void JITSlabAllocator::Deallocate(MemSlab *Slab) {
528 sys::MemoryBlock B(Slab, Slab->Size);
529 sys::Memory::ReleaseRWX(B);
530}
531
532DefaultJITMemoryManager::DefaultJITMemoryManager()
Dan Gohman5b78d502009-08-27 01:25:57 +0000533 :
534#ifdef NDEBUG
535 PoisonMemory(false),
536#else
537 PoisonMemory(true),
538#endif
539 LastSlab(0, 0),
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000540 BumpSlabAllocator(*this),
541 StubAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator),
542 DataAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator) {
543
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000544 // Allocate space for code.
545 sys::MemoryBlock MemBlock = allocateNewSlab(DefaultCodeSlabSize);
546 CodeSlabs.push_back(MemBlock);
547 uint8_t *MemBase = (uint8_t*)MemBlock.base();
Jeffrey Yasskin489393d2009-07-08 21:59:57 +0000548
Chris Lattner8907b4b2007-12-05 23:39:57 +0000549 // We set up the memory chunk with 4 mem regions, like this:
550 // [ START
551 // [ Free #0 ] -> Large space to allocate functions from.
552 // [ Allocated #1 ] -> Tiny space to separate regions.
553 // [ Free #2 ] -> Tiny space so there is always at least 1 free block.
554 // [ Allocated #3 ] -> Tiny space to prevent looking past end of block.
555 // END ]
556 //
557 // The last three blocks are never deallocated or touched.
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000558
Chris Lattner8907b4b2007-12-05 23:39:57 +0000559 // Add MemoryRangeHeader to the end of the memory region, indicating that
560 // the space after the block of memory is allocated. This is block #3.
561 MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
562 Mem3->ThisAllocated = 1;
563 Mem3->PrevAllocated = 0;
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000564 Mem3->BlockSize = sizeof(MemoryRangeHeader);
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000565
Chris Lattner8907b4b2007-12-05 23:39:57 +0000566 /// Add a tiny free region so that the free list always has one entry.
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000567 FreeRangeHeader *Mem2 =
Chris Lattner8907b4b2007-12-05 23:39:57 +0000568 (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
569 Mem2->ThisAllocated = 0;
570 Mem2->PrevAllocated = 1;
571 Mem2->BlockSize = FreeRangeHeader::getMinBlockSize();
572 Mem2->SetEndOfBlockSizeMarker();
573 Mem2->Prev = Mem2; // Mem2 *is* the free list for now.
574 Mem2->Next = Mem2;
575
576 /// Add a tiny allocated region so that Mem2 is never coalesced away.
577 MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
578 Mem1->ThisAllocated = 1;
579 Mem1->PrevAllocated = 0;
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000580 Mem1->BlockSize = sizeof(MemoryRangeHeader);
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000581
Chris Lattner8907b4b2007-12-05 23:39:57 +0000582 // Add a FreeRangeHeader to the start of the function body region, indicating
583 // that the space is free. Mark the previous block allocated so we never look
584 // at it.
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000585 FreeRangeHeader *Mem0 = (FreeRangeHeader*)MemBase;
Chris Lattner8907b4b2007-12-05 23:39:57 +0000586 Mem0->ThisAllocated = 0;
587 Mem0->PrevAllocated = 1;
588 Mem0->BlockSize = (char*)Mem1-(char*)Mem0;
589 Mem0->SetEndOfBlockSizeMarker();
590 Mem0->AddToFreeList(Mem2);
Eric Christopher5cf0aed2009-11-12 01:06:08 +0000591
Chris Lattner8907b4b2007-12-05 23:39:57 +0000592 // Start out with the freelist pointing to Mem0.
593 FreeMemoryList = Mem0;
594
595 GOTBase = NULL;
596}
597
598void DefaultJITMemoryManager::AllocateGOT() {
599 assert(GOTBase == 0 && "Cannot allocate the got multiple times");
Bruno Cardoso Lopes186c6702009-06-04 00:15:51 +0000600 GOTBase = new uint8_t[sizeof(void*) * 8192];
Chris Lattner8907b4b2007-12-05 23:39:57 +0000601 HasGOT = true;
602}
603
Chris Lattner8907b4b2007-12-05 23:39:57 +0000604DefaultJITMemoryManager::~DefaultJITMemoryManager() {
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000605 for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
606 sys::Memory::ReleaseRWX(CodeSlabs[i]);
607
Chris Lattner8907b4b2007-12-05 23:39:57 +0000608 delete[] GOTBase;
Chris Lattner8907b4b2007-12-05 23:39:57 +0000609}
610
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000611sys::MemoryBlock DefaultJITMemoryManager::allocateNewSlab(size_t size) {
Chris Lattner8907b4b2007-12-05 23:39:57 +0000612 // Allocate a new block close to the last one.
Chris Lattner8907b4b2007-12-05 23:39:57 +0000613 std::string ErrMsg;
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000614 sys::MemoryBlock *LastSlabPtr = LastSlab.base() ? &LastSlab : 0;
615 sys::MemoryBlock B = sys::Memory::AllocateRWX(size, LastSlabPtr, &ErrMsg);
Chris Lattner8907b4b2007-12-05 23:39:57 +0000616 if (B.base() == 0) {
Torok Edwin7d696d82009-07-11 13:10:19 +0000617 llvm_report_error("Allocation failed when allocating new memory in the"
618 " JIT\n" + ErrMsg);
Chris Lattner8907b4b2007-12-05 23:39:57 +0000619 }
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000620 LastSlab = B;
621 ++NumSlabs;
Reid Kleckner01248e62009-08-21 21:03:57 +0000622 // Initialize the slab to garbage when debugging.
623 if (PoisonMemory) {
624 memset(B.base(), 0xCD, B.size());
625 }
Chris Lattner8907b4b2007-12-05 23:39:57 +0000626 return B;
627}
628
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000629/// CheckInvariants - For testing only. Return "" if all internal invariants
630/// are preserved, and a helpful error message otherwise. For free and
631/// allocated blocks, make sure that adding BlockSize gives a valid block.
632/// For free blocks, make sure they're in the free list and that their end of
633/// block size marker is correct. This function should return an error before
634/// accessing bad memory. This function is defined here instead of in
635/// JITMemoryManagerTest.cpp so that we don't have to expose all of the
636/// implementation details of DefaultJITMemoryManager.
637bool DefaultJITMemoryManager::CheckInvariants(std::string &ErrorStr) {
638 raw_string_ostream Err(ErrorStr);
639
640 // Construct a the set of FreeRangeHeader pointers so we can query it
641 // efficiently.
642 llvm::SmallPtrSet<MemoryRangeHeader*, 16> FreeHdrSet;
643 FreeRangeHeader* FreeHead = FreeMemoryList;
644 FreeRangeHeader* FreeRange = FreeHead;
645
646 do {
647 // Check that the free range pointer is in the blocks we've allocated.
648 bool Found = false;
649 for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
650 E = CodeSlabs.end(); I != E && !Found; ++I) {
651 char *Start = (char*)I->base();
652 char *End = Start + I->size();
653 Found = (Start <= (char*)FreeRange && (char*)FreeRange < End);
654 }
655 if (!Found) {
656 Err << "Corrupt free list; points to " << FreeRange;
657 return false;
658 }
659
660 if (FreeRange->Next->Prev != FreeRange) {
661 Err << "Next and Prev pointers do not match.";
662 return false;
663 }
664
665 // Otherwise, add it to the set.
666 FreeHdrSet.insert(FreeRange);
667 FreeRange = FreeRange->Next;
668 } while (FreeRange != FreeHead);
669
670 // Go over each block, and look at each MemoryRangeHeader.
671 for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
672 E = CodeSlabs.end(); I != E; ++I) {
673 char *Start = (char*)I->base();
674 char *End = Start + I->size();
675
676 // Check each memory range.
677 for (MemoryRangeHeader *Hdr = (MemoryRangeHeader*)Start, *LastHdr = NULL;
678 Start <= (char*)Hdr && (char*)Hdr < End;
679 Hdr = &Hdr->getBlockAfter()) {
680 if (Hdr->ThisAllocated == 0) {
681 // Check that this range is in the free list.
682 if (!FreeHdrSet.count(Hdr)) {
683 Err << "Found free header at " << Hdr << " that is not in free list.";
684 return false;
685 }
686
687 // Now make sure the size marker at the end of the block is correct.
688 uintptr_t *Marker = ((uintptr_t*)&Hdr->getBlockAfter()) - 1;
689 if (!(Start <= (char*)Marker && (char*)Marker < End)) {
690 Err << "Block size in header points out of current MemoryBlock.";
691 return false;
692 }
693 if (Hdr->BlockSize != *Marker) {
694 Err << "End of block size marker (" << *Marker << ") "
695 << "and BlockSize (" << Hdr->BlockSize << ") don't match.";
696 return false;
697 }
698 }
699
700 if (LastHdr && LastHdr->ThisAllocated != Hdr->PrevAllocated) {
701 Err << "Hdr->PrevAllocated (" << Hdr->PrevAllocated << ") != "
702 << "LastHdr->ThisAllocated (" << LastHdr->ThisAllocated << ")";
703 return false;
704 } else if (!LastHdr && !Hdr->PrevAllocated) {
705 Err << "The first header should have PrevAllocated true.";
706 return false;
707 }
708
709 // Remember the last header.
710 LastHdr = Hdr;
711 }
712 }
713
714 // All invariants are preserved.
715 return true;
716}
Chris Lattner8907b4b2007-12-05 23:39:57 +0000717
718JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() {
719 return new DefaultJITMemoryManager();
720}
Reid Kleckner10b4fc52009-07-23 21:46:56 +0000721
722// Allocate memory for code in 512K slabs.
723const size_t DefaultJITMemoryManager::DefaultCodeSlabSize = 512 * 1024;
724
725// Allocate globals and stubs in slabs of 64K. (probably 16 pages)
726const size_t DefaultJITMemoryManager::DefaultSlabSize = 64 * 1024;
727
728// Waste at most 16K at the end of each bump slab. (probably 4 pages)
729const size_t DefaultJITMemoryManager::DefaultSizeThreshold = 16 * 1024;