From 4b3a356493dfe6e40beb897d25d5a55c5951084e Mon Sep 17 00:00:00 2001 From: Reid Kleckner Date: Thu, 23 Jul 2009 21:46:56 +0000 Subject: [PATCH] Re-committing r76828 with the JIT memory manager changes now that the build bots like the BumpPtrAllocator changes. llvm-svn: 76902 --- .../llvm/ExecutionEngine/JITMemoryManager.h | 69 +++- llvm/include/llvm/System/Memory.h | 9 +- llvm/lib/ExecutionEngine/JIT/JITEmitter.cpp | 51 ++- llvm/lib/ExecutionEngine/JIT/JITMemoryManager.cpp | 364 +++++++++++++++------ llvm/lib/System/Unix/Memory.inc | 7 +- llvm/lib/System/Win32/Memory.inc | 7 +- llvm/tools/lli/lli.cpp | 3 - .../ExecutionEngine/JIT/JITMemoryManagerTest.cpp | 276 ++++++++++++++++ 8 files changed, 661 insertions(+), 125 deletions(-) diff --git a/llvm/include/llvm/ExecutionEngine/JITMemoryManager.h b/llvm/include/llvm/ExecutionEngine/JITMemoryManager.h index 02ec1c3..4539011 100644 --- a/llvm/include/llvm/ExecutionEngine/JITMemoryManager.h +++ b/llvm/include/llvm/ExecutionEngine/JITMemoryManager.h @@ -15,9 +15,12 @@ #define LLVM_EXECUTION_ENGINE_JIT_MEMMANAGER_H #include "llvm/Support/DataTypes.h" +#include namespace llvm { + class Function; + class GlobalValue; /// JITMemoryManager - This interface is used by the JIT to allocate and manage /// memory for the code generated by the JIT. This can be reimplemented by @@ -88,16 +91,19 @@ public: //===--------------------------------------------------------------------===// // Main Allocation Functions //===--------------------------------------------------------------------===// - - /// startFunctionBody - When we start JITing a function, the JIT calls this + + /// startFunctionBody - When we start JITing a function, the JIT calls this /// method to allocate a block of free RWX memory, which returns a pointer to - /// it. The JIT doesn't know ahead of time how much space it will need to - /// emit the function, so it doesn't pass in the size. Instead, this method - /// is required to pass back a "valid size". The JIT will be careful to not - /// write more than the returned ActualSize bytes of memory. - virtual uint8_t *startFunctionBody(const Function *F, + /// it. If the JIT wants to request a block of memory of at least a certain + /// size, it passes that value as ActualSize, and this method returns a block + /// with at least that much space. If the JIT doesn't know ahead of time how + /// much space it will need to emit the function, it passes 0 for the + /// ActualSize. In either case, this method is required to pass back the size + /// of the allocated block through ActualSize. The JIT will be careful to + /// not write more than the returned ActualSize bytes of memory. + virtual uint8_t *startFunctionBody(const Function *F, uintptr_t &ActualSize) = 0; - + /// allocateStub - This method is called by the JIT to allocate space for a /// function stub (used to handle limited branch displacements) while it is /// JIT compiling a function. For example, if foo calls bar, and if bar @@ -118,10 +124,12 @@ public: virtual void endFunctionBody(const Function *F, uint8_t *FunctionStart, uint8_t *FunctionEnd) = 0; - /// allocateSpace - Allocate a memory block of the given size. + /// allocateSpace - Allocate a memory block of the given size. This method + /// cannot be called between calls to startFunctionBody and endFunctionBody. virtual uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) = 0; /// allocateGlobal - Allocate memory for a global. + /// virtual uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) = 0; /// deallocateMemForFunction - Free JIT memory for the specified function. @@ -137,6 +145,49 @@ public: /// the exception table. virtual void endExceptionTable(const Function *F, uint8_t *TableStart, uint8_t *TableEnd, uint8_t* FrameRegister) = 0; + + /// CheckInvariants - For testing only. Return true if all internal + /// invariants are preserved, or return false and set ErrorStr to a helpful + /// error message. + virtual bool CheckInvariants(std::string &ErrorStr) { + return true; + } + + /// GetDefaultCodeSlabSize - For testing only. Returns DefaultCodeSlabSize + /// from DefaultJITMemoryManager. + virtual size_t GetDefaultCodeSlabSize() { + return 0; + } + + /// GetDefaultDataSlabSize - For testing only. Returns DefaultCodeSlabSize + /// from DefaultJITMemoryManager. + virtual size_t GetDefaultDataSlabSize() { + return 0; + } + + /// GetDefaultStubSlabSize - For testing only. Returns DefaultCodeSlabSize + /// from DefaultJITMemoryManager. + virtual size_t GetDefaultStubSlabSize() { + return 0; + } + + /// GetNumCodeSlabs - For testing only. Returns the number of MemoryBlocks + /// allocated for code. + virtual unsigned GetNumCodeSlabs() { + return 0; + } + + /// GetNumDataSlabs - For testing only. Returns the number of MemoryBlocks + /// allocated for data. + virtual unsigned GetNumDataSlabs() { + return 0; + } + + /// GetNumStubSlabs - For testing only. Returns the number of MemoryBlocks + /// allocated for function stubs. + virtual unsigned GetNumStubSlabs() { + return 0; + } }; } // end namespace llvm. diff --git a/llvm/include/llvm/System/Memory.h b/llvm/include/llvm/System/Memory.h index 136dc8a..d6300db 100644 --- a/llvm/include/llvm/System/Memory.h +++ b/llvm/include/llvm/System/Memory.h @@ -14,6 +14,7 @@ #ifndef LLVM_SYSTEM_MEMORY_H #define LLVM_SYSTEM_MEMORY_H +#include "llvm/Support/DataTypes.h" #include namespace llvm { @@ -26,11 +27,13 @@ namespace sys { /// @brief Memory block abstraction. class MemoryBlock { public: + MemoryBlock() { } + MemoryBlock(void *addr, size_t size) : Address(addr), Size(size) { } void *base() const { return Address; } - unsigned size() const { return Size; } + size_t size() const { return Size; } private: void *Address; ///< Address of first byte of memory area - unsigned Size; ///< Size, in bytes of the memory area + size_t Size; ///< Size, in bytes of the memory area friend class Memory; }; @@ -50,7 +53,7 @@ namespace sys { /// a null memory block and fills in *ErrMsg. /// /// @brief Allocate Read/Write/Execute memory. - static MemoryBlock AllocateRWX(unsigned NumBytes, + static MemoryBlock AllocateRWX(size_t NumBytes, const MemoryBlock *NearBlock, std::string *ErrMsg = 0); diff --git a/llvm/lib/ExecutionEngine/JIT/JITEmitter.cpp b/llvm/lib/ExecutionEngine/JIT/JITEmitter.cpp index ce52273..246a0ce 100644 --- a/llvm/lib/ExecutionEngine/JIT/JITEmitter.cpp +++ b/llvm/lib/ExecutionEngine/JIT/JITEmitter.cpp @@ -51,6 +51,7 @@ using namespace llvm; STATISTIC(NumBytes, "Number of bytes of machine code compiled"); STATISTIC(NumRelos, "Number of relocations applied"); +STATISTIC(NumRetries, "Number of retries with more memory"); static JIT *TheJIT = 0; @@ -425,6 +426,12 @@ namespace { // save BufferBegin/BufferEnd/CurBufferPtr here. uint8_t *SavedBufferBegin, *SavedBufferEnd, *SavedCurBufferPtr; + // When reattempting to JIT a function after running out of space, we store + // the estimated size of the function we're trying to JIT here, so we can + // ask the memory manager for at least this much space. When we + // successfully emit the function, we reset this back to zero. + uintptr_t SizeEstimate; + /// Relocations - These are the relocations that the function needs, as /// emitted. std::vector Relocations; @@ -496,7 +503,8 @@ namespace { DebugLocTuple PrevDLT; public: - JITEmitter(JIT &jit, JITMemoryManager *JMM) : Resolver(jit), CurFn(0) { + JITEmitter(JIT &jit, JITMemoryManager *JMM) + : SizeEstimate(0), Resolver(jit), CurFn(0) { MemMgr = JMM ? JMM : JITMemoryManager::CreateDefaultMemManager(); if (jit.getJITInfo().needsGOT()) { MemMgr->AllocateGOT(); @@ -561,9 +569,14 @@ namespace { return MBBLocations[MBB->getNumber()]; } + /// retryWithMoreMemory - Log a retry and deallocate all memory for the + /// given function. Increase the minimum allocation size so that we get + /// more memory next time. + void retryWithMoreMemory(MachineFunction &F); + /// deallocateMemForFunction - Deallocate all memory for the specified /// function body. - void deallocateMemForFunction(Function *F); + void deallocateMemForFunction(const Function *F); /// AddStubToCurrentFunction - Mark the current function being JIT'd as /// using the stub at the specified address. Allows @@ -925,6 +938,9 @@ void JITEmitter::startFunction(MachineFunction &F) { // previously allocated. ActualSize += GetSizeOfGlobalsInBytes(F); DOUT << "JIT: ActualSize after globals " << ActualSize << "\n"; + } else if (SizeEstimate > 0) { + // SizeEstimate will be non-zero on reallocation attempts. + ActualSize = SizeEstimate; } BufferBegin = CurBufferPtr = MemMgr->startFunctionBody(F.getFunction(), @@ -949,12 +965,15 @@ void JITEmitter::startFunction(MachineFunction &F) { bool JITEmitter::finishFunction(MachineFunction &F) { if (CurBufferPtr == BufferEnd) { - // FIXME: Allocate more space, then try again. - llvm_report_error("JIT: Ran out of space for generated machine code!"); + // We must call endFunctionBody before retrying, because + // deallocateMemForFunction requires it. + MemMgr->endFunctionBody(F.getFunction(), BufferBegin, CurBufferPtr); + retryWithMoreMemory(F); + return true; } - + emitJumpTableInfo(F.getJumpTableInfo()); - + // FnStart is the start of the text, not the start of the constant pool and // other per-function data. uint8_t *FnStart = @@ -1045,8 +1064,12 @@ bool JITEmitter::finishFunction(MachineFunction &F) { MemMgr->endFunctionBody(F.getFunction(), BufferBegin, CurBufferPtr); if (CurBufferPtr == BufferEnd) { - // FIXME: Allocate more space, then try again. - llvm_report_error("JIT: Ran out of space for generated machine code!"); + retryWithMoreMemory(F); + return true; + } else { + // Now that we've succeeded in emitting the function, reset the + // SizeEstimate back down to zero. + SizeEstimate = 0; } BufferBegin = CurBufferPtr = 0; @@ -1131,9 +1154,19 @@ bool JITEmitter::finishFunction(MachineFunction &F) { return false; } +void JITEmitter::retryWithMoreMemory(MachineFunction &F) { + DOUT << "JIT: Ran out of space for native code. Reattempting.\n"; + Relocations.clear(); // Clear the old relocations or we'll reapply them. + ConstPoolAddresses.clear(); + ++NumRetries; + deallocateMemForFunction(F.getFunction()); + // Try again with at least twice as much free space. + SizeEstimate = (uintptr_t)(2 * (BufferEnd - BufferBegin)); +} + /// deallocateMemForFunction - Deallocate all memory for the specified /// function body. Also drop any references the function has to stubs. -void JITEmitter::deallocateMemForFunction(Function *F) { +void JITEmitter::deallocateMemForFunction(const Function *F) { MemMgr->deallocateMemForFunction(F); // If the function did not reference any stubs, return. diff --git a/llvm/lib/ExecutionEngine/JIT/JITMemoryManager.cpp b/llvm/lib/ExecutionEngine/JIT/JITMemoryManager.cpp index 253c001..2d64fcf 100644 --- a/llvm/lib/ExecutionEngine/JIT/JITMemoryManager.cpp +++ b/llvm/lib/ExecutionEngine/JIT/JITMemoryManager.cpp @@ -11,10 +11,16 @@ // //===----------------------------------------------------------------------===// -#include "llvm/GlobalValue.h" +#define DEBUG_TYPE "jit" #include "llvm/ExecutionEngine/JITMemoryManager.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/GlobalValue.h" +#include "llvm/Support/Allocator.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/System/Memory.h" #include #include @@ -25,6 +31,7 @@ #include using namespace llvm; +STATISTIC(NumSlabs, "Number of slabs of memory allocated by the JIT"); JITMemoryManager::~JITMemoryManager() {} @@ -141,7 +148,7 @@ FreeRangeHeader *FreeRangeHeader::AllocateBlock() { /// FreeRangeHeader to allocate from. FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) { MemoryRangeHeader *FollowingBlock = &getBlockAfter(); - assert(ThisAllocated && "This block is already allocated!"); + assert(ThisAllocated && "This block is already free!"); assert(FollowingBlock->PrevAllocated && "Flags out of sync!"); FreeRangeHeader *FreeListToReturn = FreeList; @@ -244,70 +251,157 @@ TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) { // Memory Block Implementation. //===----------------------------------------------------------------------===// -namespace { +namespace { + + class DefaultJITMemoryManager; + + class JITSlabAllocator : public SlabAllocator { + DefaultJITMemoryManager &JMM; + public: + JITSlabAllocator(DefaultJITMemoryManager &jmm) : JMM(jmm) { } + virtual ~JITSlabAllocator() { } + virtual MemSlab *Allocate(size_t Size); + virtual void Deallocate(MemSlab *Slab); + }; + /// DefaultJITMemoryManager - Manage memory for the JIT code generation. /// This splits a large block of MAP_NORESERVE'd memory into two /// sections, one for function stubs, one for the functions themselves. We /// have to do this because we may need to emit a function stub while in the /// middle of emitting a function, and we don't know how large the function we /// are emitting is. - class VISIBILITY_HIDDEN DefaultJITMemoryManager : public JITMemoryManager { - bool PoisonMemory; // Whether to poison freed memory. + class DefaultJITMemoryManager : public JITMemoryManager { + + // Whether to poison freed memory. + bool PoisonMemory; + + /// LastSlab - This points to the last slab allocated and is used as the + /// NearBlock parameter to AllocateRWX so that we can attempt to lay out all + /// stubs, data, and code contiguously in memory. In general, however, this + /// is not possible because the NearBlock parameter is ignored on Windows + /// platforms and even on Unix it works on a best-effort pasis. + sys::MemoryBlock LastSlab; + + // Memory slabs allocated by the JIT. We refer to them as slabs so we don't + // confuse them with the blocks of memory descibed above. + std::vector CodeSlabs; + JITSlabAllocator BumpSlabAllocator; + BumpPtrAllocator StubAllocator; + BumpPtrAllocator DataAllocator; + + // Circular list of free blocks. + FreeRangeHeader *FreeMemoryList; - std::vector Blocks; // Memory blocks allocated by the JIT - FreeRangeHeader *FreeMemoryList; // Circular list of free blocks. - // When emitting code into a memory block, this is the block. MemoryRangeHeader *CurBlock; - - uint8_t *CurStubPtr, *StubBase; - uint8_t *CurGlobalPtr, *GlobalEnd; + uint8_t *GOTBase; // Target Specific reserved memory void *DlsymTable; // Stub external symbol information - // Centralize memory block allocation. - sys::MemoryBlock getNewMemoryBlock(unsigned size); - std::map FunctionBlocks; std::map TableBlocks; public: DefaultJITMemoryManager(); ~DefaultJITMemoryManager(); + /// allocateNewSlab - Allocates a new MemoryBlock and remembers it as the + /// last slab it allocated, so that subsequent allocations follow it. + sys::MemoryBlock allocateNewSlab(size_t size); + + /// DefaultCodeSlabSize - When we have to go map more memory, we allocate at + /// least this much unless more is requested. + static const size_t DefaultCodeSlabSize; + + /// DefaultSlabSize - Allocate data into slabs of this size unless we get + /// an allocation above SizeThreshold. + static const size_t DefaultSlabSize; + + /// DefaultSizeThreshold - For any allocation larger than this threshold, we + /// should allocate a separate slab. + static const size_t DefaultSizeThreshold; + void AllocateGOT(); void SetDlsymTable(void *); - - uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize, - unsigned Alignment); - + + // Testing methods. + virtual bool CheckInvariants(std::string &ErrorStr); + size_t GetDefaultCodeSlabSize() { return DefaultCodeSlabSize; } + size_t GetDefaultDataSlabSize() { return DefaultSlabSize; } + size_t GetDefaultStubSlabSize() { return DefaultSlabSize; } + unsigned GetNumCodeSlabs() { return CodeSlabs.size(); } + unsigned GetNumDataSlabs() { return DataAllocator.GetNumSlabs(); } + unsigned GetNumStubSlabs() { return StubAllocator.GetNumSlabs(); } + /// startFunctionBody - When a function starts, allocate a block of free /// executable memory, returning a pointer to it and its actual size. uint8_t *startFunctionBody(const Function *F, uintptr_t &ActualSize) { - + FreeRangeHeader* candidateBlock = FreeMemoryList; FreeRangeHeader* head = FreeMemoryList; FreeRangeHeader* iter = head->Next; uintptr_t largest = candidateBlock->BlockSize; - + // Search for the largest free block while (iter != head) { - if (iter->BlockSize > largest) { - largest = iter->BlockSize; - candidateBlock = iter; - } - iter = iter->Next; + if (iter->BlockSize > largest) { + largest = iter->BlockSize; + candidateBlock = iter; + } + iter = iter->Next; } - + + // If this block isn't big enough for the allocation desired, allocate + // another block of memory and add it to the free list. + if (largest - sizeof(MemoryRangeHeader) < ActualSize) { + DOUT << "JIT: Allocating another slab of memory for function."; + candidateBlock = allocateNewCodeSlab((size_t)ActualSize); + } + // Select this candidate block for allocation CurBlock = candidateBlock; // Allocate the entire memory block. FreeMemoryList = candidateBlock->AllocateBlock(); - ActualSize = CurBlock->BlockSize-sizeof(MemoryRangeHeader); - return (uint8_t *)(CurBlock+1); + ActualSize = CurBlock->BlockSize - sizeof(MemoryRangeHeader); + return (uint8_t *)(CurBlock + 1); } - + + /// allocateNewCodeSlab - Helper method to allocate a new slab of code + /// memory from the OS and add it to the free list. Returns the new + /// FreeRangeHeader at the base of the slab. + FreeRangeHeader *allocateNewCodeSlab(size_t MinSize) { + // If the user needs at least MinSize free memory, then we account for + // two MemoryRangeHeaders: the one in the user's block, and the one at the + // end of the slab. + size_t PaddedMin = MinSize + 2 * sizeof(MemoryRangeHeader); + size_t SlabSize = std::max(DefaultCodeSlabSize, PaddedMin); + sys::MemoryBlock B = allocateNewSlab(SlabSize); + CodeSlabs.push_back(B); + char *MemBase = (char*)(B.base()); + + // Put a tiny allocated block at the end of the memory chunk, so when + // FreeBlock calls getBlockAfter it doesn't fall off the end. + MemoryRangeHeader *EndBlock = + (MemoryRangeHeader*)(MemBase + B.size()) - 1; + EndBlock->ThisAllocated = 1; + EndBlock->PrevAllocated = 0; + EndBlock->BlockSize = sizeof(MemoryRangeHeader); + + // Start out with a vast new block of free memory. + FreeRangeHeader *NewBlock = (FreeRangeHeader*)MemBase; + NewBlock->ThisAllocated = 0; + // Make sure getFreeBlockBefore doesn't look into unmapped memory. + NewBlock->PrevAllocated = 1; + NewBlock->BlockSize = (uintptr_t)EndBlock - (uintptr_t)NewBlock; + NewBlock->SetEndOfBlockSizeMarker(); + NewBlock->AddToFreeList(FreeMemoryList); + + assert(NewBlock->BlockSize - sizeof(MemoryRangeHeader) >= MinSize && + "The block was too small!"); + return NewBlock; + } + /// endFunctionBody - The function F is now allocated, and takes the memory /// in the range [FunctionStart,FunctionEnd). void endFunctionBody(const Function *F, uint8_t *FunctionStart, @@ -323,7 +417,8 @@ namespace { FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize); } - /// allocateSpace - Allocate a memory block of the given size. + /// allocateSpace - Allocate a memory block of the given size. This method + /// cannot be called between calls to startFunctionBody and endFunctionBody. uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) { CurBlock = FreeMemoryList; FreeMemoryList = FreeMemoryList->AllocateBlock(); @@ -340,27 +435,15 @@ namespace { return result; } - /// allocateGlobal - Allocate memory for a global. Unlike allocateSpace, - /// this method does not touch the current block and can be called at any - /// time. - uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) { - uint8_t *Result = CurGlobalPtr; - - // Align the pointer. - if (Alignment == 0) Alignment = 1; - Result = (uint8_t*)(((uintptr_t)Result + Alignment-1) & - ~(uintptr_t)(Alignment-1)); - - // Move the current global pointer forward. - CurGlobalPtr += Result - CurGlobalPtr + Size; - - // Check for overflow. - if (CurGlobalPtr > GlobalEnd) { - // FIXME: Allocate more memory. - llvm_report_error("JIT ran out of memory for globals!"); - } + /// allocateStub - Allocate memory for a function stub. + uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize, + unsigned Alignment) { + return (uint8_t*)StubAllocator.Allocate(StubSize, Alignment); + } - return Result; + /// allocateGlobal - Allocate memory for a global. + uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) { + return (uint8_t*)DataAllocator.Allocate(Size, Alignment); } /// startExceptionTable - Use startFunctionBody to allocate memory for the @@ -437,15 +520,15 @@ namespace { /// the code pages may need permissions changed. void setMemoryWritable(void) { - for (unsigned i = 0, e = Blocks.size(); i != e; ++i) - sys::Memory::setWritable(Blocks[i]); + for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i) + sys::Memory::setWritable(CodeSlabs[i]); } /// setMemoryExecutable - When code generation is done and we're ready to /// start execution, the code pages may need permissions changed. void setMemoryExecutable(void) { - for (unsigned i = 0, e = Blocks.size(); i != e; ++i) - sys::Memory::setExecutable(Blocks[i]); + for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i) + sys::Memory::setExecutable(CodeSlabs[i]); } /// setPoisonMemory - Controls whether we write garbage over freed memory. @@ -456,28 +539,35 @@ namespace { }; } -DefaultJITMemoryManager::DefaultJITMemoryManager() { +MemSlab *JITSlabAllocator::Allocate(size_t Size) { + sys::MemoryBlock B = JMM.allocateNewSlab(Size); + MemSlab *Slab = (MemSlab*)B.base(); + Slab->Size = B.size(); + Slab->NextPtr = 0; + return Slab; +} + +void JITSlabAllocator::Deallocate(MemSlab *Slab) { + sys::MemoryBlock B(Slab, Slab->Size); + sys::Memory::ReleaseRWX(B); +} + +DefaultJITMemoryManager::DefaultJITMemoryManager() + : LastSlab(0, 0), + BumpSlabAllocator(*this), + StubAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator), + DataAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator) { + #ifdef NDEBUG - PoisonMemory = true; -#else PoisonMemory = false; -#endif - - // Allocate a 16M block of memory for functions. -#if defined(__APPLE__) && defined(__arm__) - sys::MemoryBlock MemBlock = getNewMemoryBlock(4 << 20); #else - sys::MemoryBlock MemBlock = getNewMemoryBlock(16 << 20); + PoisonMemory = true; #endif - uint8_t *MemBase = static_cast(MemBlock.base()); - - // Allocate stubs backwards to the base, globals forward from the stubs, and - // functions forward after globals. - StubBase = MemBase; - CurStubPtr = MemBase + 512*1024; // Use 512k for stubs, working backwards. - CurGlobalPtr = CurStubPtr; // Use 2M for globals, working forwards. - GlobalEnd = CurGlobalPtr + 2*1024*1024; + // Allocate space for code. + sys::MemoryBlock MemBlock = allocateNewSlab(DefaultCodeSlabSize); + CodeSlabs.push_back(MemBlock); + uint8_t *MemBase = (uint8_t*)MemBlock.base(); // We set up the memory chunk with 4 mem regions, like this: // [ START @@ -494,7 +584,7 @@ DefaultJITMemoryManager::DefaultJITMemoryManager() { MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1; Mem3->ThisAllocated = 1; Mem3->PrevAllocated = 0; - Mem3->BlockSize = 0; + Mem3->BlockSize = sizeof(MemoryRangeHeader); /// Add a tiny free region so that the free list always has one entry. FreeRangeHeader *Mem2 = @@ -510,12 +600,12 @@ DefaultJITMemoryManager::DefaultJITMemoryManager() { MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1; Mem1->ThisAllocated = 1; Mem1->PrevAllocated = 0; - Mem1->BlockSize = (char*)Mem2 - (char*)Mem1; + Mem1->BlockSize = sizeof(MemoryRangeHeader); // Add a FreeRangeHeader to the start of the function body region, indicating // that the space is free. Mark the previous block allocated so we never look // at it. - FreeRangeHeader *Mem0 = (FreeRangeHeader*)GlobalEnd; + FreeRangeHeader *Mem0 = (FreeRangeHeader*)MemBase; Mem0->ThisAllocated = 0; Mem0->PrevAllocated = 1; Mem0->BlockSize = (char*)Mem1-(char*)Mem0; @@ -540,40 +630,124 @@ void DefaultJITMemoryManager::SetDlsymTable(void *ptr) { } DefaultJITMemoryManager::~DefaultJITMemoryManager() { - for (unsigned i = 0, e = Blocks.size(); i != e; ++i) - sys::Memory::ReleaseRWX(Blocks[i]); - - delete[] GOTBase; - Blocks.clear(); -} + for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i) + sys::Memory::ReleaseRWX(CodeSlabs[i]); -uint8_t *DefaultJITMemoryManager::allocateStub(const GlobalValue* F, - unsigned StubSize, - unsigned Alignment) { - CurStubPtr -= StubSize; - CurStubPtr = (uint8_t*)(((intptr_t)CurStubPtr) & - ~(intptr_t)(Alignment-1)); - if (CurStubPtr < StubBase) { - // FIXME: allocate a new block - llvm_report_error("JIT ran out of memory for function stubs!"); - } - return CurStubPtr; + delete[] GOTBase; } -sys::MemoryBlock DefaultJITMemoryManager::getNewMemoryBlock(unsigned size) { +sys::MemoryBlock DefaultJITMemoryManager::allocateNewSlab(size_t size) { // Allocate a new block close to the last one. - const sys::MemoryBlock *BOld = Blocks.empty() ? 0 : &Blocks.back(); std::string ErrMsg; - sys::MemoryBlock B = sys::Memory::AllocateRWX(size, BOld, &ErrMsg); + sys::MemoryBlock *LastSlabPtr = LastSlab.base() ? &LastSlab : 0; + sys::MemoryBlock B = sys::Memory::AllocateRWX(size, LastSlabPtr, &ErrMsg); if (B.base() == 0) { llvm_report_error("Allocation failed when allocating new memory in the" " JIT\n" + ErrMsg); } - Blocks.push_back(B); + LastSlab = B; + ++NumSlabs; return B; } +/// CheckInvariants - For testing only. Return "" if all internal invariants +/// are preserved, and a helpful error message otherwise. For free and +/// allocated blocks, make sure that adding BlockSize gives a valid block. +/// For free blocks, make sure they're in the free list and that their end of +/// block size marker is correct. This function should return an error before +/// accessing bad memory. This function is defined here instead of in +/// JITMemoryManagerTest.cpp so that we don't have to expose all of the +/// implementation details of DefaultJITMemoryManager. +bool DefaultJITMemoryManager::CheckInvariants(std::string &ErrorStr) { + raw_string_ostream Err(ErrorStr); + + // Construct a the set of FreeRangeHeader pointers so we can query it + // efficiently. + llvm::SmallPtrSet FreeHdrSet; + FreeRangeHeader* FreeHead = FreeMemoryList; + FreeRangeHeader* FreeRange = FreeHead; + + do { + // Check that the free range pointer is in the blocks we've allocated. + bool Found = false; + for (std::vector::iterator I = CodeSlabs.begin(), + E = CodeSlabs.end(); I != E && !Found; ++I) { + char *Start = (char*)I->base(); + char *End = Start + I->size(); + Found = (Start <= (char*)FreeRange && (char*)FreeRange < End); + } + if (!Found) { + Err << "Corrupt free list; points to " << FreeRange; + return false; + } + + if (FreeRange->Next->Prev != FreeRange) { + Err << "Next and Prev pointers do not match."; + return false; + } + + // Otherwise, add it to the set. + FreeHdrSet.insert(FreeRange); + FreeRange = FreeRange->Next; + } while (FreeRange != FreeHead); + + // Go over each block, and look at each MemoryRangeHeader. + for (std::vector::iterator I = CodeSlabs.begin(), + E = CodeSlabs.end(); I != E; ++I) { + char *Start = (char*)I->base(); + char *End = Start + I->size(); + + // Check each memory range. + for (MemoryRangeHeader *Hdr = (MemoryRangeHeader*)Start, *LastHdr = NULL; + Start <= (char*)Hdr && (char*)Hdr < End; + Hdr = &Hdr->getBlockAfter()) { + if (Hdr->ThisAllocated == 0) { + // Check that this range is in the free list. + if (!FreeHdrSet.count(Hdr)) { + Err << "Found free header at " << Hdr << " that is not in free list."; + return false; + } + + // Now make sure the size marker at the end of the block is correct. + uintptr_t *Marker = ((uintptr_t*)&Hdr->getBlockAfter()) - 1; + if (!(Start <= (char*)Marker && (char*)Marker < End)) { + Err << "Block size in header points out of current MemoryBlock."; + return false; + } + if (Hdr->BlockSize != *Marker) { + Err << "End of block size marker (" << *Marker << ") " + << "and BlockSize (" << Hdr->BlockSize << ") don't match."; + return false; + } + } + + if (LastHdr && LastHdr->ThisAllocated != Hdr->PrevAllocated) { + Err << "Hdr->PrevAllocated (" << Hdr->PrevAllocated << ") != " + << "LastHdr->ThisAllocated (" << LastHdr->ThisAllocated << ")"; + return false; + } else if (!LastHdr && !Hdr->PrevAllocated) { + Err << "The first header should have PrevAllocated true."; + return false; + } + + // Remember the last header. + LastHdr = Hdr; + } + } + + // All invariants are preserved. + return true; +} JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() { return new DefaultJITMemoryManager(); } + +// Allocate memory for code in 512K slabs. +const size_t DefaultJITMemoryManager::DefaultCodeSlabSize = 512 * 1024; + +// Allocate globals and stubs in slabs of 64K. (probably 16 pages) +const size_t DefaultJITMemoryManager::DefaultSlabSize = 64 * 1024; + +// Waste at most 16K at the end of each bump slab. (probably 4 pages) +const size_t DefaultJITMemoryManager::DefaultSizeThreshold = 16 * 1024; diff --git a/llvm/lib/System/Unix/Memory.inc b/llvm/lib/System/Unix/Memory.inc index b7a7013..a80f56f 100644 --- a/llvm/lib/System/Unix/Memory.inc +++ b/llvm/lib/System/Unix/Memory.inc @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "Unix.h" +#include "llvm/Support/DataTypes.h" #include "llvm/System/Process.h" #ifdef HAVE_SYS_MMAN_H @@ -28,12 +29,12 @@ /// is very OS specific. /// llvm::sys::MemoryBlock -llvm::sys::Memory::AllocateRWX(unsigned NumBytes, const MemoryBlock* NearBlock, +llvm::sys::Memory::AllocateRWX(size_t NumBytes, const MemoryBlock* NearBlock, std::string *ErrMsg) { if (NumBytes == 0) return MemoryBlock(); - unsigned pageSize = Process::GetPageSize(); - unsigned NumPages = (NumBytes+pageSize-1)/pageSize; + size_t pageSize = Process::GetPageSize(); + size_t NumPages = (NumBytes+pageSize-1)/pageSize; int fd = -1; #ifdef NEED_DEV_ZERO_FOR_MMAP diff --git a/llvm/lib/System/Win32/Memory.inc b/llvm/lib/System/Win32/Memory.inc index 5e5cf7a..7611ecd 100644 --- a/llvm/lib/System/Win32/Memory.inc +++ b/llvm/lib/System/Win32/Memory.inc @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #include "Win32.h" +#include "llvm/Support/DataTypes.h" #include "llvm/System/Process.h" namespace llvm { @@ -23,13 +24,13 @@ using namespace sys; //=== and must not be UNIX code //===----------------------------------------------------------------------===// -MemoryBlock Memory::AllocateRWX(unsigned NumBytes, +MemoryBlock Memory::AllocateRWX(size_t NumBytes, const MemoryBlock *NearBlock, std::string *ErrMsg) { if (NumBytes == 0) return MemoryBlock(); - static const long pageSize = Process::GetPageSize(); - unsigned NumPages = (NumBytes+pageSize-1)/pageSize; + static const size_t pageSize = Process::GetPageSize(); + size_t NumPages = (NumBytes+pageSize-1)/pageSize; //FIXME: support NearBlock if ever needed on Win64. diff --git a/llvm/tools/lli/lli.cpp b/llvm/tools/lli/lli.cpp index 0337703..f9d86d7 100644 --- a/llvm/tools/lli/lli.cpp +++ b/llvm/tools/lli/lli.cpp @@ -136,9 +136,6 @@ int main(int argc, char **argv, char * const *envp) { builder.setEngineKind(ForceInterpreter ? EngineKind::Interpreter : EngineKind::JIT); - // FIXME: Don't allocate GVs with code once the JIT because smarter about - // memory management. - builder.setAllocateGVsWithCode(true); // If we are supposed to override the target triple, do so now. if (!TargetTriple.empty()) diff --git a/llvm/unittests/ExecutionEngine/JIT/JITMemoryManagerTest.cpp b/llvm/unittests/ExecutionEngine/JIT/JITMemoryManagerTest.cpp index e69de29..f9b3a03 100644 --- a/llvm/unittests/ExecutionEngine/JIT/JITMemoryManagerTest.cpp +++ b/llvm/unittests/ExecutionEngine/JIT/JITMemoryManagerTest.cpp @@ -0,0 +1,276 @@ +//===- JITMemoryManagerTest.cpp - Unit tests for the JIT memory manager ---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "gtest/gtest.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ExecutionEngine/JITMemoryManager.h" +#include "llvm/DerivedTypes.h" +#include "llvm/Function.h" +#include "llvm/GlobalValue.h" + +using namespace llvm; + +namespace { + +Function *makeFakeFunction() { + std::vector params; + const FunctionType *FTy = FunctionType::get(Type::VoidTy, params, false); + return Function::Create(FTy, GlobalValue::ExternalLinkage); +} + +// Allocate three simple functions that fit in the initial slab. This exercises +// the code in the case that we don't have to allocate more memory to store the +// function bodies. +TEST(JITMemoryManagerTest, NoAllocations) { + OwningPtr MemMgr( + JITMemoryManager::CreateDefaultMemManager()); + uintptr_t size; + uint8_t *start; + std::string Error; + + // Allocate the functions. + OwningPtr F1(makeFakeFunction()); + size = 1024; + start = MemMgr->startFunctionBody(F1.get(), size); + memset(start, 0xFF, 1024); + MemMgr->endFunctionBody(F1.get(), start, start + 1024); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + + OwningPtr F2(makeFakeFunction()); + size = 1024; + start = MemMgr->startFunctionBody(F2.get(), size); + memset(start, 0xFF, 1024); + MemMgr->endFunctionBody(F2.get(), start, start + 1024); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + + OwningPtr F3(makeFakeFunction()); + size = 1024; + start = MemMgr->startFunctionBody(F3.get(), size); + memset(start, 0xFF, 1024); + MemMgr->endFunctionBody(F3.get(), start, start + 1024); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + + // Deallocate them out of order, in case that matters. + MemMgr->deallocateMemForFunction(F2.get()); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + MemMgr->deallocateMemForFunction(F1.get()); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + MemMgr->deallocateMemForFunction(F3.get()); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; +} + +// Make three large functions that take up most of the space in the slab. Then +// try allocating three smaller functions that don't require additional slabs. +TEST(JITMemoryManagerTest, TestCodeAllocation) { + OwningPtr MemMgr( + JITMemoryManager::CreateDefaultMemManager()); + uintptr_t size; + uint8_t *start; + std::string Error; + + // Big functions are a little less than the largest block size. + const uintptr_t smallFuncSize = 1024; + const uintptr_t bigFuncSize = (MemMgr->GetDefaultCodeSlabSize() - + smallFuncSize * 2); + + // Allocate big functions + OwningPtr F1(makeFakeFunction()); + size = bigFuncSize; + start = MemMgr->startFunctionBody(F1.get(), size); + ASSERT_LE(bigFuncSize, size); + memset(start, 0xFF, bigFuncSize); + MemMgr->endFunctionBody(F1.get(), start, start + bigFuncSize); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + + OwningPtr F2(makeFakeFunction()); + size = bigFuncSize; + start = MemMgr->startFunctionBody(F2.get(), size); + ASSERT_LE(bigFuncSize, size); + memset(start, 0xFF, bigFuncSize); + MemMgr->endFunctionBody(F2.get(), start, start + bigFuncSize); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + + OwningPtr F3(makeFakeFunction()); + size = bigFuncSize; + start = MemMgr->startFunctionBody(F3.get(), size); + ASSERT_LE(bigFuncSize, size); + memset(start, 0xFF, bigFuncSize); + MemMgr->endFunctionBody(F3.get(), start, start + bigFuncSize); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + + // Check that each large function took it's own slab. + EXPECT_EQ(3U, MemMgr->GetNumCodeSlabs()); + + // Allocate small functions + OwningPtr F4(makeFakeFunction()); + size = smallFuncSize; + start = MemMgr->startFunctionBody(F4.get(), size); + ASSERT_LE(smallFuncSize, size); + memset(start, 0xFF, smallFuncSize); + MemMgr->endFunctionBody(F4.get(), start, start + smallFuncSize); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + + OwningPtr F5(makeFakeFunction()); + size = smallFuncSize; + start = MemMgr->startFunctionBody(F5.get(), size); + ASSERT_LE(smallFuncSize, size); + memset(start, 0xFF, smallFuncSize); + MemMgr->endFunctionBody(F5.get(), start, start + smallFuncSize); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + + OwningPtr F6(makeFakeFunction()); + size = smallFuncSize; + start = MemMgr->startFunctionBody(F6.get(), size); + ASSERT_LE(smallFuncSize, size); + memset(start, 0xFF, smallFuncSize); + MemMgr->endFunctionBody(F6.get(), start, start + smallFuncSize); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + + // Check that the small functions didn't allocate any new slabs. + EXPECT_EQ(3U, MemMgr->GetNumCodeSlabs()); + + // Deallocate them out of order, in case that matters. + MemMgr->deallocateMemForFunction(F2.get()); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + MemMgr->deallocateMemForFunction(F1.get()); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + MemMgr->deallocateMemForFunction(F4.get()); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + MemMgr->deallocateMemForFunction(F3.get()); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + MemMgr->deallocateMemForFunction(F5.get()); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; + MemMgr->deallocateMemForFunction(F6.get()); + EXPECT_TRUE(MemMgr->CheckInvariants(Error)) << Error; +} + +// Allocate five global ints of varying widths and alignment, and check their +// alignment and overlap. +TEST(JITMemoryManagerTest, TestSmallGlobalInts) { + OwningPtr MemMgr( + JITMemoryManager::CreateDefaultMemManager()); + uint8_t *a = (uint8_t *)MemMgr->allocateGlobal(8, 0); + uint16_t *b = (uint16_t*)MemMgr->allocateGlobal(16, 2); + uint32_t *c = (uint32_t*)MemMgr->allocateGlobal(32, 4); + uint64_t *d = (uint64_t*)MemMgr->allocateGlobal(64, 8); + + // Check the alignment. + EXPECT_EQ(0U, ((uintptr_t)b) & 0x1); + EXPECT_EQ(0U, ((uintptr_t)c) & 0x3); + EXPECT_EQ(0U, ((uintptr_t)d) & 0x7); + + // Initialize them each one at a time and make sure they don't overlap. + *a = 0xff; + *b = 0U; + *c = 0U; + *d = 0U; + EXPECT_EQ(0xffU, *a); + EXPECT_EQ(0U, *b); + EXPECT_EQ(0U, *c); + EXPECT_EQ(0U, *d); + *a = 0U; + *b = 0xffffU; + EXPECT_EQ(0U, *a); + EXPECT_EQ(0xffffU, *b); + EXPECT_EQ(0U, *c); + EXPECT_EQ(0U, *d); + *b = 0U; + *c = 0xffffffffU; + EXPECT_EQ(0U, *a); + EXPECT_EQ(0U, *b); + EXPECT_EQ(0xffffffffU, *c); + EXPECT_EQ(0U, *d); + *c = 0U; + *d = 0xffffffffffffffffU; + EXPECT_EQ(0U, *a); + EXPECT_EQ(0U, *b); + EXPECT_EQ(0U, *c); + EXPECT_EQ(0xffffffffffffffffU, *d); + + // Make sure we didn't allocate any extra slabs for this tiny amount of data. + EXPECT_EQ(1U, MemMgr->GetNumDataSlabs()); +} + +// Allocate a small global, a big global, and a third global, and make sure we +// only use two slabs for that. +TEST(JITMemoryManagerTest, TestLargeGlobalArray) { + OwningPtr MemMgr( + JITMemoryManager::CreateDefaultMemManager()); + size_t Size = 4 * MemMgr->GetDefaultDataSlabSize(); + uint64_t *a = (uint64_t*)MemMgr->allocateGlobal(64, 8); + uint8_t *g = MemMgr->allocateGlobal(Size, 8); + uint64_t *b = (uint64_t*)MemMgr->allocateGlobal(64, 8); + + // Check the alignment. + EXPECT_EQ(0U, ((uintptr_t)a) & 0x7); + EXPECT_EQ(0U, ((uintptr_t)g) & 0x7); + EXPECT_EQ(0U, ((uintptr_t)b) & 0x7); + + // Initialize them to make sure we don't segfault and make sure they don't + // overlap. + memset(a, 0x1, 8); + memset(g, 0x2, Size); + memset(b, 0x3, 8); + EXPECT_EQ(0x0101010101010101U, *a); + // Just check the edges. + EXPECT_EQ(0x02U, g[0]); + EXPECT_EQ(0x02U, g[Size - 1]); + EXPECT_EQ(0x0303030303030303U, *b); + + // Check the number of slabs. + EXPECT_EQ(2U, MemMgr->GetNumDataSlabs()); +} + +// Allocate lots of medium globals so that we can test moving the bump allocator +// to a new slab. +TEST(JITMemoryManagerTest, TestManyGlobals) { + OwningPtr MemMgr( + JITMemoryManager::CreateDefaultMemManager()); + size_t SlabSize = MemMgr->GetDefaultDataSlabSize(); + size_t Size = 128; + int Iters = (SlabSize / Size) + 1; + + // We should start with one slab. + EXPECT_EQ(1U, MemMgr->GetNumDataSlabs()); + + // After allocating a bunch of globals, we should have two. + for (int I = 0; I < Iters; ++I) + MemMgr->allocateGlobal(Size, 8); + EXPECT_EQ(2U, MemMgr->GetNumDataSlabs()); + + // And after much more, we should have three. + for (int I = 0; I < Iters; ++I) + MemMgr->allocateGlobal(Size, 8); + EXPECT_EQ(3U, MemMgr->GetNumDataSlabs()); +} + +// Allocate lots of function stubs so that we can test moving the stub bump +// allocator to a new slab. +TEST(JITMemoryManagerTest, TestManyStubs) { + OwningPtr MemMgr( + JITMemoryManager::CreateDefaultMemManager()); + size_t SlabSize = MemMgr->GetDefaultStubSlabSize(); + size_t Size = 128; + int Iters = (SlabSize / Size) + 1; + + // We should start with one slab. + EXPECT_EQ(1U, MemMgr->GetNumStubSlabs()); + + // After allocating a bunch of stubs, we should have two. + for (int I = 0; I < Iters; ++I) + MemMgr->allocateStub(NULL, Size, 8); + EXPECT_EQ(2U, MemMgr->GetNumStubSlabs()); + + // And after much more, we should have three. + for (int I = 0; I < Iters; ++I) + MemMgr->allocateStub(NULL, Size, 8); + EXPECT_EQ(3U, MemMgr->GetNumStubSlabs()); +} + +} -- 2.7.4