JITMemoryManager.cpp [plain text]
#define DEBUG_TYPE "jit"
#include "llvm/ExecutionEngine/JITMemoryManager.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Config/config.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DynamicLibrary.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Memory.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <climits>
#include <cstring>
#include <vector>
#if defined(__linux__)
#if defined(HAVE_SYS_STAT_H)
#include <sys/stat.h>
#endif
#include <fcntl.h>
#include <unistd.h>
#endif
using namespace llvm;
STATISTIC(NumSlabs, "Number of slabs of memory allocated by the JIT");
JITMemoryManager::~JITMemoryManager() {}
namespace {
struct FreeRangeHeader;
struct MemoryRangeHeader {
unsigned ThisAllocated : 1;
unsigned PrevAllocated : 1;
uintptr_t BlockSize : (sizeof(intptr_t)*CHAR_BIT - 2);
MemoryRangeHeader &getBlockAfter() const {
return *reinterpret_cast<MemoryRangeHeader *>(
reinterpret_cast<char*>(
const_cast<MemoryRangeHeader *>(this))+BlockSize);
}
FreeRangeHeader *getFreeBlockBefore() const {
if (PrevAllocated) return 0;
intptr_t PrevSize = reinterpret_cast<intptr_t *>(
const_cast<MemoryRangeHeader *>(this))[-1];
return reinterpret_cast<FreeRangeHeader *>(
reinterpret_cast<char*>(
const_cast<MemoryRangeHeader *>(this))-PrevSize);
}
FreeRangeHeader *FreeBlock(FreeRangeHeader *FreeList);
FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList,
uint64_t NewSize);
};
struct FreeRangeHeader : public MemoryRangeHeader {
FreeRangeHeader *Prev;
FreeRangeHeader *Next;
static unsigned getMinBlockSize() {
return sizeof(FreeRangeHeader)+sizeof(intptr_t);
}
void SetEndOfBlockSizeMarker() {
void *EndOfBlock = (char*)this + BlockSize;
((intptr_t *)EndOfBlock)[-1] = BlockSize;
}
FreeRangeHeader *RemoveFromFreeList() {
assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
Next->Prev = Prev;
return Prev->Next = Next;
}
void AddToFreeList(FreeRangeHeader *FreeList) {
Next = FreeList;
Prev = FreeList->Prev;
Prev->Next = this;
Next->Prev = this;
}
void GrowBlock(uintptr_t NewSize);
FreeRangeHeader *AllocateBlock();
};
}
FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
"Cannot allocate an allocated block!");
ThisAllocated = 1;
getBlockAfter().PrevAllocated = 1;
return RemoveFromFreeList();
}
FreeRangeHeader *MemoryRangeHeader::FreeBlock(FreeRangeHeader *FreeList) {
MemoryRangeHeader *FollowingBlock = &getBlockAfter();
assert(ThisAllocated && "This block is already free!");
assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
FreeRangeHeader *FreeListToReturn = FreeList;
if (!FollowingBlock->ThisAllocated) {
FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
if (&FollowingFreeBlock == FreeList) {
FreeList = FollowingFreeBlock.Next;
FreeListToReturn = 0;
assert(&FollowingFreeBlock != FreeList && "No tombstone block?");
}
FollowingFreeBlock.RemoveFromFreeList();
BlockSize += FollowingFreeBlock.BlockSize;
FollowingBlock = &FollowingFreeBlock.getBlockAfter();
FollowingBlock->PrevAllocated = 1;
}
assert(FollowingBlock->ThisAllocated && "Missed coalescing?");
if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
return FreeListToReturn ? FreeListToReturn : PrevFreeBlock;
}
FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
FollowingBlock->PrevAllocated = 0;
FreeBlock.ThisAllocated = 0;
FreeBlock.AddToFreeList(FreeList);
FreeBlock.SetEndOfBlockSizeMarker();
return FreeListToReturn ? FreeListToReturn : &FreeBlock;
}
void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
assert(NewSize > BlockSize && "Not growing block?");
BlockSize = NewSize;
SetEndOfBlockSizeMarker();
getBlockAfter().PrevAllocated = 0;
}
FreeRangeHeader *MemoryRangeHeader::
TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
assert(ThisAllocated && getBlockAfter().PrevAllocated &&
"Cannot deallocate part of an allocated block!");
NewSize = std::max<uint64_t>(FreeRangeHeader::getMinBlockSize(), NewSize);
unsigned HeaderAlign = __alignof(FreeRangeHeader);
NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
assert(NewSize <= BlockSize &&
"Allocating more space from this block than exists!");
if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
return FreeList;
MemoryRangeHeader &FormerNextBlock = getBlockAfter();
BlockSize = NewSize;
FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
NewNextBlock.ThisAllocated = 0;
NewNextBlock.PrevAllocated = 1;
NewNextBlock.SetEndOfBlockSizeMarker();
FormerNextBlock.PrevAllocated = 0;
NewNextBlock.AddToFreeList(FreeList);
return &NewNextBlock;
}
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);
};
class DefaultJITMemoryManager : public JITMemoryManager {
bool PoisonMemory;
sys::MemoryBlock LastSlab;
std::vector<sys::MemoryBlock> CodeSlabs;
JITSlabAllocator BumpSlabAllocator;
BumpPtrAllocator StubAllocator;
BumpPtrAllocator DataAllocator;
FreeRangeHeader *FreeMemoryList;
MemoryRangeHeader *CurBlock;
uint8_t *GOTBase; public:
DefaultJITMemoryManager();
~DefaultJITMemoryManager();
sys::MemoryBlock allocateNewSlab(size_t size);
static const size_t DefaultCodeSlabSize;
static const size_t DefaultSlabSize;
static const size_t DefaultSizeThreshold;
virtual void *getPointerToNamedFunction(const std::string &Name,
bool AbortOnFailure = true);
void AllocateGOT();
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(); }
uint8_t *startFunctionBody(const Function *F, uintptr_t &ActualSize) {
FreeRangeHeader* candidateBlock = FreeMemoryList;
FreeRangeHeader* head = FreeMemoryList;
FreeRangeHeader* iter = head->Next;
uintptr_t largest = candidateBlock->BlockSize;
while (iter != head) {
if (iter->BlockSize > largest) {
largest = iter->BlockSize;
candidateBlock = iter;
}
iter = iter->Next;
}
largest = largest - sizeof(MemoryRangeHeader);
if (largest < ActualSize ||
largest <= FreeRangeHeader::getMinBlockSize()) {
DEBUG(dbgs() << "JIT: Allocating another slab of memory for function.");
candidateBlock = allocateNewCodeSlab((size_t)ActualSize);
}
CurBlock = candidateBlock;
FreeMemoryList = candidateBlock->AllocateBlock();
ActualSize = CurBlock->BlockSize - sizeof(MemoryRangeHeader);
return (uint8_t *)(CurBlock + 1);
}
FreeRangeHeader *allocateNewCodeSlab(size_t MinSize) {
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());
MemoryRangeHeader *EndBlock =
(MemoryRangeHeader*)(MemBase + B.size()) - 1;
EndBlock->ThisAllocated = 1;
EndBlock->PrevAllocated = 0;
EndBlock->BlockSize = sizeof(MemoryRangeHeader);
FreeRangeHeader *NewBlock = (FreeRangeHeader*)MemBase;
NewBlock->ThisAllocated = 0;
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;
}
void endFunctionBody(const Function *F, uint8_t *FunctionStart,
uint8_t *FunctionEnd) {
assert(FunctionEnd > FunctionStart);
assert(FunctionStart == (uint8_t *)(CurBlock+1) &&
"Mismatched function start/end!");
uintptr_t BlockSize = FunctionEnd - (uint8_t *)CurBlock;
FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
}
uint8_t *allocateSpace(intptr_t Size, unsigned Alignment) {
CurBlock = FreeMemoryList;
FreeMemoryList = FreeMemoryList->AllocateBlock();
uint8_t *result = (uint8_t *)(CurBlock + 1);
if (Alignment == 0) Alignment = 1;
result = (uint8_t*)(((intptr_t)result+Alignment-1) &
~(intptr_t)(Alignment-1));
uintptr_t BlockSize = result + Size - (uint8_t *)CurBlock;
FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
return result;
}
uint8_t *allocateStub(const GlobalValue* F, unsigned StubSize,
unsigned Alignment) {
return (uint8_t*)StubAllocator.Allocate(StubSize, Alignment);
}
uint8_t *allocateGlobal(uintptr_t Size, unsigned Alignment) {
return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
}
uint8_t *allocateCodeSection(uintptr_t Size, unsigned Alignment,
unsigned SectionID, StringRef SectionName) {
Size += sizeof(*CurBlock);
if (!Alignment)
Alignment = 16;
Size += Alignment - 1;
FreeRangeHeader* candidateBlock = FreeMemoryList;
FreeRangeHeader* head = FreeMemoryList;
FreeRangeHeader* iter = head->Next;
uintptr_t largest = candidateBlock->BlockSize;
while (iter != head) {
if (iter->BlockSize > largest) {
largest = iter->BlockSize;
candidateBlock = iter;
}
iter = iter->Next;
}
largest = largest - sizeof(MemoryRangeHeader);
if (largest < Size || largest <= FreeRangeHeader::getMinBlockSize()) {
DEBUG(dbgs() << "JIT: Allocating another slab of memory for function.");
candidateBlock = allocateNewCodeSlab((size_t)Size);
}
CurBlock = candidateBlock;
FreeMemoryList = candidateBlock->AllocateBlock();
FreeMemoryList = CurBlock->TrimAllocationToSize(FreeMemoryList, Size);
uintptr_t unalignedAddr = (uintptr_t)CurBlock + sizeof(*CurBlock);
return (uint8_t*)RoundUpToAlignment((uint64_t)unalignedAddr, Alignment);
}
uint8_t *allocateDataSection(uintptr_t Size, unsigned Alignment,
unsigned SectionID, StringRef SectionName,
bool IsReadOnly) {
return (uint8_t*)DataAllocator.Allocate(Size, Alignment);
}
bool finalizeMemory(std::string *ErrMsg) {
return false;
}
uint8_t *getGOTBase() const {
return GOTBase;
}
void deallocateBlock(void *Block) {
MemoryRangeHeader *MemRange = static_cast<MemoryRangeHeader*>(Block) - 1;
assert(MemRange->ThisAllocated && "Block isn't allocated!");
if (PoisonMemory) {
memset(MemRange+1, 0xCD, MemRange->BlockSize-sizeof(*MemRange));
}
FreeMemoryList = MemRange->FreeBlock(FreeMemoryList);
}
void deallocateFunctionBody(void *Body) {
if (Body) deallocateBlock(Body);
}
void setMemoryWritable()
{
for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
sys::Memory::setWritable(CodeSlabs[i]);
}
void setMemoryExecutable()
{
for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
sys::Memory::setExecutable(CodeSlabs[i]);
}
void setPoisonMemory(bool poison) {
PoisonMemory = poison;
}
};
}
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()
:
#ifdef NDEBUG
PoisonMemory(false),
#else
PoisonMemory(true),
#endif
LastSlab(0, 0),
BumpSlabAllocator(*this),
StubAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator),
DataAllocator(DefaultSlabSize, DefaultSizeThreshold, BumpSlabAllocator) {
sys::MemoryBlock MemBlock = allocateNewSlab(DefaultCodeSlabSize);
CodeSlabs.push_back(MemBlock);
uint8_t *MemBase = (uint8_t*)MemBlock.base();
MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
Mem3->ThisAllocated = 1;
Mem3->PrevAllocated = 0;
Mem3->BlockSize = sizeof(MemoryRangeHeader);
FreeRangeHeader *Mem2 =
(FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
Mem2->ThisAllocated = 0;
Mem2->PrevAllocated = 1;
Mem2->BlockSize = FreeRangeHeader::getMinBlockSize();
Mem2->SetEndOfBlockSizeMarker();
Mem2->Prev = Mem2; Mem2->Next = Mem2;
MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
Mem1->ThisAllocated = 1;
Mem1->PrevAllocated = 0;
Mem1->BlockSize = sizeof(MemoryRangeHeader);
FreeRangeHeader *Mem0 = (FreeRangeHeader*)MemBase;
Mem0->ThisAllocated = 0;
Mem0->PrevAllocated = 1;
Mem0->BlockSize = (char*)Mem1-(char*)Mem0;
Mem0->SetEndOfBlockSizeMarker();
Mem0->AddToFreeList(Mem2);
FreeMemoryList = Mem0;
GOTBase = NULL;
}
void DefaultJITMemoryManager::AllocateGOT() {
assert(GOTBase == 0 && "Cannot allocate the got multiple times");
GOTBase = new uint8_t[sizeof(void*) * 8192];
HasGOT = true;
}
DefaultJITMemoryManager::~DefaultJITMemoryManager() {
for (unsigned i = 0, e = CodeSlabs.size(); i != e; ++i)
sys::Memory::ReleaseRWX(CodeSlabs[i]);
delete[] GOTBase;
}
sys::MemoryBlock DefaultJITMemoryManager::allocateNewSlab(size_t size) {
std::string ErrMsg;
sys::MemoryBlock *LastSlabPtr = LastSlab.base() ? &LastSlab : 0;
sys::MemoryBlock B = sys::Memory::AllocateRWX(size, LastSlabPtr, &ErrMsg);
if (B.base() == 0) {
report_fatal_error("Allocation failed when allocating new memory in the"
" JIT\n" + Twine(ErrMsg));
}
LastSlab = B;
++NumSlabs;
if (PoisonMemory) {
memset(B.base(), 0xCD, B.size());
}
return B;
}
bool DefaultJITMemoryManager::CheckInvariants(std::string &ErrorStr) {
raw_string_ostream Err(ErrorStr);
llvm::SmallPtrSet<MemoryRangeHeader*, 16> FreeHdrSet;
FreeRangeHeader* FreeHead = FreeMemoryList;
FreeRangeHeader* FreeRange = FreeHead;
do {
bool Found = false;
for (std::vector<sys::MemoryBlock>::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;
}
FreeHdrSet.insert(FreeRange);
FreeRange = FreeRange->Next;
} while (FreeRange != FreeHead);
for (std::vector<sys::MemoryBlock>::iterator I = CodeSlabs.begin(),
E = CodeSlabs.end(); I != E; ++I) {
char *Start = (char*)I->base();
char *End = Start + I->size();
for (MemoryRangeHeader *Hdr = (MemoryRangeHeader*)Start, *LastHdr = NULL;
Start <= (char*)Hdr && (char*)Hdr < End;
Hdr = &Hdr->getBlockAfter()) {
if (Hdr->ThisAllocated == 0) {
if (!FreeHdrSet.count(Hdr)) {
Err << "Found free header at " << Hdr << " that is not in free list.";
return false;
}
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;
}
LastHdr = Hdr;
}
}
return true;
}
static std::vector<void (*)()> AtExitHandlers;
static void runAtExitHandlers() {
while (!AtExitHandlers.empty()) {
void (*Fn)() = AtExitHandlers.back();
AtExitHandlers.pop_back();
Fn();
}
}
#if defined(__linux__)
namespace {
class StatSymbols {
public:
StatSymbols() {
sys::DynamicLibrary::AddSymbol("stat", (void*)(intptr_t)stat);
sys::DynamicLibrary::AddSymbol("fstat", (void*)(intptr_t)fstat);
sys::DynamicLibrary::AddSymbol("lstat", (void*)(intptr_t)lstat);
sys::DynamicLibrary::AddSymbol("stat64", (void*)(intptr_t)stat64);
sys::DynamicLibrary::AddSymbol("\x1stat64", (void*)(intptr_t)stat64);
sys::DynamicLibrary::AddSymbol("\x1open64", (void*)(intptr_t)open64);
sys::DynamicLibrary::AddSymbol("\x1lseek64", (void*)(intptr_t)lseek64);
sys::DynamicLibrary::AddSymbol("fstat64", (void*)(intptr_t)fstat64);
sys::DynamicLibrary::AddSymbol("lstat64", (void*)(intptr_t)lstat64);
sys::DynamicLibrary::AddSymbol("atexit", (void*)(intptr_t)atexit);
sys::DynamicLibrary::AddSymbol("mknod", (void*)(intptr_t)mknod);
}
};
}
static StatSymbols initStatSymbols;
#endif // __linux__
static void jit_exit(int Status) {
runAtExitHandlers(); exit(Status);
}
static int jit_atexit(void (*Fn)()) {
AtExitHandlers.push_back(Fn); return 0; }
static int jit_noop() {
return 0;
}
void *DefaultJITMemoryManager::getPointerToNamedFunction(const std::string &Name,
bool AbortOnFailure) {
if (Name == "exit") return (void*)(intptr_t)&jit_exit;
if (Name == "atexit") return (void*)(intptr_t)&jit_atexit;
if (Name == "__main") return (void*)(intptr_t)&jit_noop;
const char *NameStr = Name.c_str();
if (NameStr[0] == 1) ++NameStr;
void *Ptr = sys::DynamicLibrary::SearchForAddressOfSymbol(NameStr);
if (Ptr) return Ptr;
if (NameStr[0] == '_') {
Ptr = sys::DynamicLibrary::SearchForAddressOfSymbol(NameStr+1);
if (Ptr) return Ptr;
}
#if defined(__APPLE__) && defined(__ppc__)
if (Name.size() > 9 && Name[Name.size()-9] == '$' &&
memcmp(&Name[Name.size()-8], "LDBLStub", 8) == 0) {
std::string Prefix = std::string(Name.begin(), Name.end()-9);
if (void *Ptr = getPointerToNamedFunction(Prefix+"$LDBL128", false))
return Ptr;
if (void *Ptr = getPointerToNamedFunction(Prefix, false))
return Ptr;
}
#endif
if (AbortOnFailure) {
report_fatal_error("Program used external function '"+Name+
"' which could not be resolved!");
}
return 0;
}
JITMemoryManager *JITMemoryManager::CreateDefaultMemManager() {
return new DefaultJITMemoryManager();
}
const size_t DefaultJITMemoryManager::DefaultCodeSlabSize = 512 * 1024;
const size_t DefaultJITMemoryManager::DefaultSlabSize = 64 * 1024;
const size_t DefaultJITMemoryManager::DefaultSizeThreshold = 16 * 1024;