diff options
| -rw-r--r-- | lib/Core/AddressSpace.cpp | 2 | ||||
| -rw-r--r-- | lib/Core/ExecutionState.cpp | 4 | ||||
| -rw-r--r-- | lib/Core/Executor.cpp | 83 | ||||
| -rw-r--r-- | lib/Core/MemoryManager.cpp | 144 | ||||
| -rw-r--r-- | lib/Core/MemoryManager.h | 57 | ||||
| -rw-r--r-- | lib/Core/StatsTracker.cpp | 2 |
6 files changed, 212 insertions, 80 deletions
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<ConstantExpr> &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<Expr> value = sf.locals[sf.kf->getArgRegister(index++)].value; - if (isa<ConstantExpr>(value)) + ref<Expr> value = sf.locals[sf.kf->getArgRegister(index++)].value; + if (value.get() && isa<ConstantExpr>(value)) out << "=" << value; } out << ")"; diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp index 709eb3a5..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. @@ -1293,13 +1295,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 +1321,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; } } } @@ -2604,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 @@ -3473,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) { @@ -3513,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; j<len+1; j++) os->write8(j, s[j]); diff --git a/lib/Core/MemoryManager.cpp b/lib/Core/MemoryManager.cpp index 7c76d480..004ce090 100644 --- a/lib/Core/MemoryManager.cpp +++ b/lib/Core/MemoryManager.cpp @@ -11,37 +11,136 @@ #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 <sys/mman.h> using namespace klee; +namespace { +llvm::cl::opt<bool> DeterministicAllocation( + "allocate-determ", + llvm::cl::desc("Allocate memory deterministically(default=off)"), + llvm::cl::init(false)); + +llvm::cl::opt<unsigned> DeterministicAllocationSize( + "allocate-determ-size", + llvm::cl::desc( + "Preallocated memory for deterministic allocation in MB (default=100)"), + llvm::cl::init(100)); + +llvm::cl::opt<bool> + 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<unsigned> 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<uint64_t> 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); -MemoryManager::~MemoryManager() { + 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, +MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, bool isGlobal, - const llvm::Value *allocSite) { - if (size>10*1024*1024) - klee_warning_once(0, "Large alloc: %u bytes. KLEE may run out of memory.", (unsigned) size); - - uint64_t address = (uint64_t) (unsigned long) malloc((unsigned) size); + const llvm::Value *allocSite, + size_t alignment) { + if (size > 10 * 1024 * 1024) + 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); + else { + int res = posix_memalign((void **)&address, alignment, size); + if (res < 0) { + klee_warning("Allocating aligned memory failed."); + address = 0; + } + } + } + if (!address) return 0; - + ++stats::allocations; MemoryObject *res = new MemoryObject(address, size, isLocal, isGlobal, false, allocSite, this); @@ -52,30 +151,31 @@ MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, MemoryObject *MemoryManager::allocateFixed(uint64_t address, uint64_t size, const llvm::Value *allocSite) { #ifndef NDEBUG - for (objects_ty::iterator it = objects.begin(), ie = objects.end(); - it != ie; ++it) { + for (objects_ty::iterator it = objects.begin(), ie = objects.end(); it != ie; + ++it) { MemoryObject *mo = *it; - if (address+size > mo->address && address < mo->address+mo->size) + if (address + size > mo->address && address < mo->address + mo->size) klee_error("Trying to allocate an overlapping object"); } #endif ++stats::allocations; - MemoryObject *res = new MemoryObject(address, size, false, true, true, - allocSite, this); + MemoryObject *res = + new MemoryObject(address, size, false, true, true, allocSite, this); objects.insert(res); return res; } -void MemoryManager::deallocate(const MemoryObject *mo) { - assert(0); -} +void MemoryManager::deallocate(const MemoryObject *mo) { assert(0); } void MemoryManager::markFreed(MemoryObject *mo) { - if (objects.find(mo) != objects.end()) - { - if (!mo->isFixed) + if (objects.find(mo) != objects.end()) { + 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 01683443..fc77b476 100644 --- a/lib/Core/MemoryManager.h +++ b/lib/Core/MemoryManager.h @@ -14,31 +14,44 @@ #include <stdint.h> namespace llvm { - class Value; +class Value; } namespace klee { - class MemoryObject; - class ArrayCache; - - class MemoryManager { - private: - typedef std::set<MemoryObject*> objects_ty; - objects_ty objects; - ArrayCache *const arrayCache; - - public: - MemoryManager(ArrayCache *arrayCache) : arrayCache(arrayCache) {} - ~MemoryManager(); - - MemoryObject *allocate(uint64_t size, bool isLocal, bool isGlobal, - const llvm::Value *allocSite); - MemoryObject *allocateFixed(uint64_t address, uint64_t size, - const llvm::Value *allocSite); - void deallocate(const MemoryObject *mo); - void markFreed(MemoryObject *mo); - ArrayCache *getArrayCache() const { return arrayCache; } - }; +class MemoryObject; +class ArrayCache; + +class MemoryManager { +private: + typedef std::set<MemoryObject *> objects_ty; + objects_ty objects; + ArrayCache *const arrayCache; + + char *deterministicSpace; + char *nextFreeSlot; + size_t spaceSize; + +public: + MemoryManager(ArrayCache *arrayCache); + ~MemoryManager(); + + /** + * Returns memory object which contains a handle to real virtual process + * memory. + */ + MemoryObject *allocate(uint64_t size, bool isLocal, bool isGlobal, + const llvm::Value *allocSite, size_t alignment = 8); + MemoryObject *allocateFixed(uint64_t address, uint64_t size, + const llvm::Value *allocSite); + 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 |