From ea0c6724dc992a5358d6da3d50d9f60472d66d64 Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Tue, 22 Mar 2016 17:16:38 +0100 Subject: Handle aligned varargs allignment correctly For vararg handling, arguments of size bigger than 64 bit need to be handled 128bit aligned according to AMD calling conventions AMD64-ABI 3.5.7p5. To handle that case correctly, we do: 1) make sure that every argument is aligned correctly in an allocation for function arguments 2) the allocation itself is aligned correctly --- lib/Core/Executor.cpp | 66 +++++++++++++++++++++++++++++---------------------- 1 file changed, 37 insertions(+), 29 deletions(-) (limited to 'lib/Core/Executor.cpp') diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp index 709eb3a5..e349ff79 100644 --- a/lib/Core/Executor.cpp +++ b/lib/Core/Executor.cpp @@ -1293,13 +1293,13 @@ void Executor::executeCall(ExecutionState &state, KFunction *kf = kmodule->functionMap[f]; state.pushFrame(state.prevPC, kf); state.pc = kf->instructions; - + if (statsTracker) statsTracker->framePushed(state, &state.stack[state.stack.size()-2]); - + // TODO: support "byval" parameter attribute // TODO: support zeroext, signext, sret attributes - + unsigned callingArgs = arguments.size(); unsigned funcArgs = f->arg_size(); if (!f->isVarArg()) { @@ -1319,56 +1319,64 @@ void Executor::executeCall(ExecutionState &state, "user.err"); return; } - + StackFrame &sf = state.stack.back(); unsigned size = 0; + bool requires16ByteAlignment = false; for (unsigned i = funcArgs; i < callingArgs; i++) { // FIXME: This is really specific to the architecture, not the pointer - // size. This happens to work fir x86-32 and x86-64, however. + // size. This happens to work for x86-32 and x86-64, however. if (WordSize == Expr::Int32) { size += Expr::getMinBytesForWidth(arguments[i]->getWidth()); } else { Expr::Width argWidth = arguments[i]->getWidth(); - // AMD64-ABI 3.5.7p5: Step 7. Align l->overflow_arg_area upwards to a 16 - // byte boundary if alignment needed by type exceeds 8 byte boundary. + // AMD64-ABI 3.5.7p5: Step 7. Align l->overflow_arg_area upwards to a + // 16 byte boundary if alignment needed by type exceeds 8 byte + // boundary. // // Alignment requirements for scalar types is the same as their size if (argWidth > Expr::Int64) { size = llvm::RoundUpToAlignment(size, 16); + requires16ByteAlignment = true; } size += llvm::RoundUpToAlignment(argWidth, WordSize) / 8; } } - MemoryObject *mo = sf.varargs = memory->allocate(size, true, false, - state.prevPC->inst); - if (!mo) { + MemoryObject *mo = sf.varargs = + memory->allocate(size, true, false, state.prevPC->inst, + (requires16ByteAlignment ? 16 : 8)); + if (!mo && size) { terminateStateOnExecError(state, "out of memory (varargs)"); return; } - if ((WordSize == Expr::Int64) && (mo->address & 15)) { - // Both 64bit Linux/Glibc and 64bit MacOSX should align to 16 bytes. - klee_warning_once(0, "While allocating varargs: malloc did not align to 16 bytes."); - } + if (mo) { + if ((WordSize == Expr::Int64) && (mo->address & 15) && + requires16ByteAlignment) { + // Both 64bit Linux/Glibc and 64bit MacOSX should align to 16 bytes. + klee_warning_once( + 0, "While allocating varargs: malloc did not align to 16 bytes."); + } - ObjectState *os = bindObjectInState(state, mo, true); - unsigned offset = 0; - for (unsigned i = funcArgs; i < callingArgs; i++) { - // FIXME: This is really specific to the architecture, not the pointer - // size. This happens to work fir x86-32 and x86-64, however. - if (WordSize == Expr::Int32) { - os->write(offset, arguments[i]); - offset += Expr::getMinBytesForWidth(arguments[i]->getWidth()); - } else { - assert(WordSize == Expr::Int64 && "Unknown word size!"); + ObjectState *os = bindObjectInState(state, mo, true); + unsigned offset = 0; + for (unsigned i = funcArgs; i < callingArgs; i++) { + // FIXME: This is really specific to the architecture, not the pointer + // size. This happens to work for x86-32 and x86-64, however. + if (WordSize == Expr::Int32) { + os->write(offset, arguments[i]); + offset += Expr::getMinBytesForWidth(arguments[i]->getWidth()); + } else { + assert(WordSize == Expr::Int64 && "Unknown word size!"); - Expr::Width argWidth = arguments[i]->getWidth(); - if (argWidth > Expr::Int64) { - offset = llvm::RoundUpToAlignment(offset, 16); + Expr::Width argWidth = arguments[i]->getWidth(); + if (argWidth > Expr::Int64) { + offset = llvm::RoundUpToAlignment(offset, 16); + } + os->write(offset, arguments[i]); + offset += llvm::RoundUpToAlignment(argWidth, WordSize) / 8; } - os->write(offset, arguments[i]); - offset += llvm::RoundUpToAlignment(argWidth, WordSize) / 8; } } } -- cgit 1.4.1 From d06a14dc2ff22da34dbf566a2ad4626c88b0be17 Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Tue, 22 Mar 2016 17:50:28 +0100 Subject: Add deterministic allocation of memory Deterministic allocation provides an internal allocator which mmaps memory to a fixed static address. This way, same allocation is assured across different KLEE runs for the same application assuming a deterministic searcher. In addition, this patch provides following options: -allocate-determ: switch on/off deterministic allocation -allocate-determ-size: adjust preallocated memory -null-on-zero-malloc: returns null pointer in case a malloc of size 0 was requested. According to standard, also a non-null pointer can be returned (which happens with the default glibc malloc implementation) -allocation-space: space between allocations can be adjusted. KLEE is not able to detect out-of-bound accesses which are inside another but wrong object. Due the implementation of typical allocators adjacent mallocs have space in between for management purposes. This spaces helped KLEE to detect off-by-1/2 accesses. For higher numbers, the allocation space has to be increased. -allocate-determ-start-address: adjust deterministic start address. The addres has to be page aligned. KLEE fails if it cannot acquire this address --- lib/Core/AddressSpace.cpp | 2 + lib/Core/ExecutionState.cpp | 4 +- lib/Core/Executor.cpp | 17 ++++++-- lib/Core/MemoryManager.cpp | 100 ++++++++++++++++++++++++++++++++++++++++++-- lib/Core/MemoryManager.h | 11 ++++- lib/Core/StatsTracker.cpp | 2 +- 6 files changed, 124 insertions(+), 12 deletions(-) (limited to 'lib/Core/Executor.cpp') diff --git a/lib/Core/AddressSpace.cpp b/lib/Core/AddressSpace.cpp index 25418c13..811e52c3 100644 --- a/lib/Core/AddressSpace.cpp +++ b/lib/Core/AddressSpace.cpp @@ -58,6 +58,8 @@ bool AddressSpace::resolveOne(const ref &addr, if (const MemoryMap::value_type *res = objects.lookup_previous(&hack)) { const MemoryObject *mo = res->first; + // Check if the provided address is between start and end of the object + // [mo->address, mo->address + mo->size) or the object is a 0-sized object. if ((mo->size==0 && address==mo->address) || (address - mo->address < mo->size)) { result = *res; diff --git a/lib/Core/ExecutionState.cpp b/lib/Core/ExecutionState.cpp index 6aeaa833..30d20266 100644 --- a/lib/Core/ExecutionState.cpp +++ b/lib/Core/ExecutionState.cpp @@ -370,8 +370,8 @@ void ExecutionState::dumpStack(llvm::raw_ostream &out) const { out << ai->getName().str(); // XXX should go through function - ref value = sf.locals[sf.kf->getArgRegister(index++)].value; - if (isa(value)) + ref value = sf.locals[sf.kf->getArgRegister(index++)].value; + if (value.get() && isa(value)) out << "=" << value; } out << ")"; diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp index e349ff79..2f5bdb0c 100644 --- a/lib/Core/Executor.cpp +++ b/lib/Core/Executor.cpp @@ -1235,8 +1235,10 @@ void Executor::executeCall(ExecutionState &state, // ExecutionState::varargs case Intrinsic::vastart: { StackFrame &sf = state.stack.back(); - assert(sf.varargs && - "vastart called in function with no vararg object"); + + // varargs can be zero if no varargs were provided + if (!sf.varargs) + return; // FIXME: This is really specific to the architecture, not the pointer // size. This happens to work fir x86-32 and x86-64, however. @@ -2612,7 +2614,9 @@ void Executor::checkMemoryUsage() { // We need to avoid calling GetTotalMallocUsage() often because it // is O(elts on freelist). This is really bad since we start // to pummel the freelist once we hit the memory cap. - unsigned mbs = util::GetTotalMallocUsage() >> 20; + unsigned mbs = (util::GetTotalMallocUsage() >> 20) + + (memory->getUsedDeterministicSize() >> 20); + if (mbs > MaxMemory) { if (mbs > MaxMemory + 100) { // just guess at how many to kill @@ -3481,7 +3485,10 @@ void Executor::runFunctionAsMain(Function *f, if (++ai!=ae) { argvMO = memory->allocate((argc+1+envc+1+1) * NumPtrBytes, false, true, f->begin()->begin()); - + + if (!argvMO) + klee_error("Could not allocate memory for function arguments"); + arguments.push_back(argvMO->getBaseExpr()); if (++ai!=ae) { @@ -3521,6 +3528,8 @@ void Executor::runFunctionAsMain(Function *f, int j, len = strlen(s); MemoryObject *arg = memory->allocate(len+1, false, true, state->pc->inst); + if (!arg) + klee_error("Could not allocate memory for function arguments"); ObjectState *os = bindObjectInState(*state, arg, false); for (j=0; jwrite8(j, s[j]); diff --git a/lib/Core/MemoryManager.cpp b/lib/Core/MemoryManager.cpp index 02bbe678..560bb6f6 100644 --- a/lib/Core/MemoryManager.cpp +++ b/lib/Core/MemoryManager.cpp @@ -11,25 +11,84 @@ #include "Memory.h" #include "MemoryManager.h" -#include "klee/ExecutionState.h" #include "klee/Expr.h" -#include "klee/Solver.h" #include "klee/Internal/Support/ErrorHandling.h" #include "llvm/Support/CommandLine.h" +#include "llvm/Support/MathExtras.h" +#include using namespace klee; +namespace { +llvm::cl::opt DeterministicAllocation( + "allocate-determ", + llvm::cl::desc("Allocate memory deterministically(default=off)"), + llvm::cl::init(false)); + +llvm::cl::opt DeterministicAllocationSize( + "allocate-determ-size", + llvm::cl::desc( + "Preallocated memory for deterministic allocation in MB (default=100)"), + llvm::cl::init(100)); + +llvm::cl::opt + NullOnZeroMalloc("return-null-on-zero-malloc", + llvm::cl::desc("Returns NULL in case malloc(size) was " + "called with size 0 (default=off)."), + llvm::cl::init(false)); + +llvm::cl::opt RedZoneSpace( + "red-zone-space", + llvm::cl::desc("Set the amount of free space between allocations. This is " + "important to detect out-of-bound accesses (default=10)."), + llvm::cl::init(10)); + +llvm::cl::opt DeterministicStartAddress( + "allocate-determ-start-address", + llvm::cl::desc("Start address for deterministic allocation. Has to be page " + "aligned (default=0x7ff30000000)."), + llvm::cl::init(0x7ff30000000)); +} + /***/ +MemoryManager::MemoryManager(ArrayCache *_arrayCache) + : arrayCache(_arrayCache), deterministicSpace(0), + nextFreeSlot(0), + spaceSize(DeterministicAllocationSize.getValue() * 1024 * 1024) { + if (DeterministicAllocation) { + // Page boundary + void *expectedAddress = (void *)DeterministicStartAddress.getValue(); + + char *newSpace = + (char *)mmap(expectedAddress, spaceSize, PROT_READ | PROT_WRITE, + MAP_ANONYMOUS | MAP_PRIVATE, -1, 0); + + if (newSpace == MAP_FAILED) { + klee_error("Couldn't mmap() memory for deterministic allocations"); + } + if (expectedAddress != newSpace) { + klee_error("Could not allocate memory deterministically"); + } + + klee_message("Deterministic memory allocation starting from %p", + expectedAddress); + deterministicSpace = newSpace; + nextFreeSlot = newSpace; + } +} MemoryManager::~MemoryManager() { while (!objects.empty()) { MemoryObject *mo = *objects.begin(); - if (!mo->isFixed) + if (!mo->isFixed && !DeterministicAllocation) free((void *)mo->address); objects.erase(mo); delete mo; } + + if (DeterministicAllocation) + munmap(deterministicSpace, spaceSize); } MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, @@ -40,7 +99,34 @@ MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, klee_warning_once(0, "Large alloc: %lu bytes. KLEE may run out of memory.", size); + // Return NULL if size is zero, this is equal to error during allocation + if (NullOnZeroMalloc && size == 0) + return 0; + + if (!llvm::isPowerOf2_64(alignment)) { + klee_warning("Only alignment of power of two is supported"); + return 0; + } + uint64_t address = 0; + if (DeterministicAllocation) { + + address = llvm::RoundUpToAlignment((uint64_t)nextFreeSlot + alignment - 1, + alignment); + + // Handle the case of 0-sized allocations as 1-byte allocations. + // This way, we make sure we have this allocation between its own red zones + size_t alloc_size = std::max(size, (uint64_t)1); + if ((char *)address + alloc_size < deterministicSpace + spaceSize) { + nextFreeSlot = (char *)address + alloc_size + RedZoneSpace; + } else { + klee_warning_once( + 0, + "Couldn't allocate %lu bytes. Not enough deterministic space left.", + size); + address = 0; + } + } else { // Use malloc for the standard case if (alignment <= 8) address = (uint64_t)malloc(size); @@ -51,6 +137,8 @@ MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, address = 0; } } + } + if (!address) return 0; @@ -86,8 +174,12 @@ void MemoryManager::deallocate(const MemoryObject *mo) { void MemoryManager::markFreed(MemoryObject *mo) { if (objects.find(mo) != objects.end()) { - if (!mo->isFixed) + if (!mo->isFixed && !DeterministicAllocation) free((void *)mo->address); objects.erase(mo); } } + +size_t MemoryManager::getUsedDeterministicSize() { + return nextFreeSlot - deterministicSpace; +} diff --git a/lib/Core/MemoryManager.h b/lib/Core/MemoryManager.h index d80e44af..5c5d21ca 100644 --- a/lib/Core/MemoryManager.h +++ b/lib/Core/MemoryManager.h @@ -27,8 +27,12 @@ namespace klee { objects_ty objects; ArrayCache *const arrayCache; + char *deterministicSpace; + char *nextFreeSlot; + size_t spaceSize; + public: - MemoryManager(ArrayCache *arrayCache) : arrayCache(arrayCache) {} + MemoryManager(ArrayCache *arrayCache); ~MemoryManager(); /** @@ -42,6 +46,11 @@ namespace klee { void deallocate(const MemoryObject *mo); void markFreed(MemoryObject *mo); ArrayCache *getArrayCache() const { return arrayCache; } + + /* + * Returns the size used by deterministic allocation in bytes + */ + size_t getUsedDeterministicSize(); }; } // End klee namespace diff --git a/lib/Core/StatsTracker.cpp b/lib/Core/StatsTracker.cpp index 26890e50..97ed26ea 100644 --- a/lib/Core/StatsTracker.cpp +++ b/lib/Core/StatsTracker.cpp @@ -438,7 +438,7 @@ void StatsTracker::writeStatsLine() { << "," << numBranches << "," << util::getUserTime() << "," << executor.states.size() - << "," << util::GetTotalMallocUsage() + << "," << util::GetTotalMallocUsage() + executor.memory->getUsedDeterministicSize() << "," << stats::queries << "," << stats::queryConstructs << "," << 0 // was numObjects -- cgit 1.4.1