diff options
Diffstat (limited to 'lib/Core/Executor.cpp')
| -rw-r--r-- | lib/Core/Executor.cpp | 291 |
1 files changed, 198 insertions, 93 deletions
diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp index 49b022f8..acd02c67 100644 --- a/lib/Core/Executor.cpp +++ b/lib/Core/Executor.cpp @@ -89,6 +89,10 @@ #include "llvm/IR/CallSite.h" #endif +#ifdef HAVE_ZLIB_H +#include "klee/Internal/Support/CompressionStream.h" +#endif + #include <cassert> #include <algorithm> #include <iomanip> @@ -158,6 +162,11 @@ namespace { "[inst_id]"), clEnumValEnd), llvm::cl::CommaSeparated); +#ifdef HAVE_ZLIB_H + cl::opt<bool> DebugCompressInstructions( + "debug-compress-instructions", cl::init(false), + cl::desc("Compress the logged instructions in gzip format.")); +#endif cl::opt<bool> DebugCheckForImpliedValues("debug-check-for-implied-values"); @@ -332,6 +341,10 @@ Executor::Executor(const InterpreterOptions &opts, InterpreterHandler *ih) std::string debug_file_name = interpreterHandler->getOutputFilename("instructions.txt"); std::string ErrorInfo; +#ifdef HAVE_ZLIB_H + if (!DebugCompressInstructions) { +#endif + #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 5) debugInstFile = new llvm::raw_fd_ostream(debug_file_name.c_str(), ErrorInfo, llvm::sys::fs::OpenFlags::F_Text), @@ -339,6 +352,16 @@ Executor::Executor(const InterpreterOptions &opts, InterpreterHandler *ih) debugInstFile = new llvm::raw_fd_ostream(debug_file_name.c_str(), ErrorInfo); #endif +#ifdef HAVE_ZLIB_H + } else { + debugInstFile = new compressed_fd_ostream( + (debug_file_name + ".gz").c_str(), ErrorInfo); + } +#endif + if (ErrorInfo != "") { + klee_error("Could not open file %s : %s", debug_file_name.c_str(), + ErrorInfo.c_str()); + } } } @@ -364,7 +387,7 @@ const Module *Executor::setModule(llvm::Module *module, kmodule->prepare(opts, interpreterHandler); specialFunctionHandler->bind(); - if (StatsTracker::useStatistics()) { + if (StatsTracker::useStatistics() || userSearcherRequiresMD2U()) { statsTracker = new StatsTracker(*this, interpreterHandler->getOutputFilename("assembly.ll"), @@ -539,7 +562,13 @@ void Executor::initializeGlobals(ExecutionState &state) { // hack where we check the object file information. LLVM_TYPE_Q Type *ty = i->getType()->getElementType(); - uint64_t size = kmodule->targetData->getTypeStoreSize(ty); + uint64_t size = 0; + if (ty->isSized()) { + size = kmodule->targetData->getTypeStoreSize(ty); + } else { + klee_warning("Type for %.*s is not sized", (int)i->getName().size(), + i->getName().data()); + } // XXX - DWD - hardcode some things until we decide how to fix. #ifndef WINDOWS @@ -553,9 +582,8 @@ void Executor::initializeGlobals(ExecutionState &state) { #endif if (size == 0) { - llvm::errs() << "Unable to find size for global variable: " - << i->getName() - << " (use will result in out of bounds access)\n"; + klee_warning("Unable to find size for global variable: %.*s (use will result in out of bounds access)", + (int)i->getName().size(), i->getName().data()); } MemoryObject *mo = memory->allocate(size, false, true, i); @@ -642,7 +670,7 @@ void Executor::branch(ExecutionState &state, for (unsigned i=1; i<N; ++i) { ExecutionState *es = result[theRNG.getInt32() % i]; ExecutionState *ns = es->branch(); - addedStates.insert(ns); + addedStates.push_back(ns); result.push_back(ns); es->ptreeNode->data = 0; std::pair<PTree::Node*,PTree::Node*> res = @@ -860,7 +888,7 @@ Executor::fork(ExecutionState ¤t, ref<Expr> condition, bool isInternal) { ++stats::forks; falseState = trueState->branch(); - addedStates.insert(falseState); + addedStates.push_back(falseState); if (RandomizeFork && theRNG.getBool()) std::swap(trueState, falseState); @@ -1212,8 +1240,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. @@ -1270,13 +1300,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()) { @@ -1296,56 +1326,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; } } } @@ -1586,58 +1624,108 @@ void Executor::executeInstruction(ExecutionState &state, KInstruction *ki) { #endif transferToBasicBlock(si->getSuccessor(index), si->getParent(), state); } else { - std::map<BasicBlock*, ref<Expr> > targets; - ref<Expr> isDefault = ConstantExpr::alloc(1, Expr::Bool); -#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 1) - for (SwitchInst::CaseIt i = si->case_begin(), e = si->case_end(); - i != e; ++i) { + // Handle possible different branch targets + + // We have the following assumptions: + // - each case value is mutual exclusive to all other values including the + // default value + // - order of case branches is based on the order of the expressions of + // the scase values, still default is handled last + std::vector<BasicBlock *> bbOrder; + std::map<BasicBlock *, ref<Expr> > branchTargets; + + std::map<ref<Expr>, BasicBlock *> expressionOrder; + + // Iterate through all non-default cases and order them by expressions +#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 1) + for (SwitchInst::CaseIt i = si->case_begin(), e = si->case_end(); i != e; + ++i) { ref<Expr> value = evalConstant(i.getCaseValue()); #else - for (unsigned i=1, cases = si->getNumCases(); i<cases; ++i) { + for (unsigned i = 1, cases = si->getNumCases(); i < cases; ++i) { ref<Expr> value = evalConstant(si->getCaseValue(i)); #endif - ref<Expr> match = EqExpr::create(cond, value); - isDefault = AndExpr::create(isDefault, Expr::createIsZero(match)); + +#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 1) + BasicBlock *caseSuccessor = i.getCaseSuccessor(); +#else + BasicBlock *caseSuccessor = si->getSuccessor(i); +#endif + expressionOrder.insert(std::make_pair(value, caseSuccessor)); + } + + // Track default branch values + ref<Expr> defaultValue = ConstantExpr::alloc(1, Expr::Bool); + + // iterate through all non-default cases but in order of the expressions + for (std::map<ref<Expr>, BasicBlock *>::iterator + it = expressionOrder.begin(), + itE = expressionOrder.end(); + it != itE; ++it) { + ref<Expr> match = EqExpr::create(cond, it->first); + + // Make sure that the default value does not contain this target's value + defaultValue = AndExpr::create(defaultValue, Expr::createIsZero(match)); + + // Check if control flow could take this case bool result; bool success = solver->mayBeTrue(state, match, result); assert(success && "FIXME: Unhandled solver failure"); (void) success; if (result) { -#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 1) - BasicBlock *caseSuccessor = i.getCaseSuccessor(); -#else - BasicBlock *caseSuccessor = si->getSuccessor(i); -#endif - std::map<BasicBlock*, ref<Expr> >::iterator it = - targets.insert(std::make_pair(caseSuccessor, - ConstantExpr::alloc(0, Expr::Bool))).first; - - it->second = OrExpr::create(match, it->second); + BasicBlock *caseSuccessor = it->second; + + // Handle the case that a basic block might be the target of multiple + // switch cases. + // Currently we generate an expression containing all switch-case + // values for the same target basic block. We spare us forking too + // many times but we generate more complex condition expressions + // TODO Add option to allow to choose between those behaviors + std::pair<std::map<BasicBlock *, ref<Expr> >::iterator, bool> res = + branchTargets.insert(std::make_pair( + caseSuccessor, ConstantExpr::alloc(0, Expr::Bool))); + + res.first->second = OrExpr::create(match, res.first->second); + + // Only add basic blocks which have not been target of a branch yet + if (res.second) { + bbOrder.push_back(caseSuccessor); + } } } + + // Check if control could take the default case bool res; - bool success = solver->mayBeTrue(state, isDefault, res); + bool success = solver->mayBeTrue(state, defaultValue, res); assert(success && "FIXME: Unhandled solver failure"); (void) success; - if (res) - targets.insert(std::make_pair(si->getDefaultDest(), isDefault)); - + if (res) { + std::pair<std::map<BasicBlock *, ref<Expr> >::iterator, bool> ret = + branchTargets.insert( + std::make_pair(si->getDefaultDest(), defaultValue)); + if (ret.second) { + bbOrder.push_back(si->getDefaultDest()); + } + } + + // Fork the current state with each state having one of the possible + // successors of this switch std::vector< ref<Expr> > conditions; - for (std::map<BasicBlock*, ref<Expr> >::iterator it = - targets.begin(), ie = targets.end(); - it != ie; ++it) - conditions.push_back(it->second); - + for (std::vector<BasicBlock *>::iterator it = bbOrder.begin(), + ie = bbOrder.end(); + it != ie; ++it) { + conditions.push_back(branchTargets[*it]); + } std::vector<ExecutionState*> branches; branch(state, conditions, branches); - + std::vector<ExecutionState*>::iterator bit = branches.begin(); - for (std::map<BasicBlock*, ref<Expr> >::iterator it = - targets.begin(), ie = targets.end(); + for (std::vector<BasicBlock *>::iterator it = bbOrder.begin(), + ie = bbOrder.end(); it != ie; ++it) { ExecutionState *es = *bit; if (es) - transferToBasicBlock(it->first, bb, *es); + transferToBasicBlock(*it, bb, *es); ++bit; } } @@ -2444,9 +2532,9 @@ void Executor::updateStates(ExecutionState *current) { states.insert(addedStates.begin(), addedStates.end()); addedStates.clear(); - - for (std::set<ExecutionState*>::iterator - it = removedStates.begin(), ie = removedStates.end(); + + for (std::vector<ExecutionState *>::iterator it = removedStates.begin(), + ie = removedStates.end(); it != ie; ++it) { ExecutionState *es = *it; std::set<ExecutionState*>::iterator it2 = states.find(es); @@ -2531,7 +2619,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 @@ -2557,6 +2647,20 @@ void Executor::checkMemoryUsage() { } } +void Executor::doDumpStates() { + if (!DumpStatesOnHalt || states.empty()) + return; + klee_message("halting execution, dumping remaining states"); + for (std::set<ExecutionState *>::iterator it = states.begin(), + ie = states.end(); + it != ie; ++it) { + ExecutionState &state = **it; + stepInstruction(state); // keep stats rolling + terminateStateEarly(state, "Execution halting."); + } + updateStates(0); +} + void Executor::run(ExecutionState &initialState) { bindModuleConstants(); @@ -2577,7 +2681,10 @@ void Executor::run(ExecutionState &initialState) { double lastTime, startTime = lastTime = util::getWallTime(); ExecutionState *lastState = 0; while (!seedMap.empty()) { - if (haltExecution) goto dump; + if (haltExecution) { + doDumpStates(); + return; + } std::map<ExecutionState*, std::vector<SeedInfo> >::iterator it = seedMap.upper_bound(lastState); @@ -2626,13 +2733,16 @@ void Executor::run(ExecutionState &initialState) { (*it)->weight = 1.; } - if (OnlySeed) - goto dump; + if (OnlySeed) { + doDumpStates(); + return; + } } searcher = constructUserSearcher(*this); - searcher->update(0, states, std::set<ExecutionState*>()); + std::vector<ExecutionState *> newStates(states.begin(), states.end()); + searcher->update(0, newStates, std::vector<ExecutionState *>()); while (!states.empty() && !haltExecution) { ExecutionState &state = searcher->selectState(); @@ -2649,19 +2759,8 @@ void Executor::run(ExecutionState &initialState) { delete searcher; searcher = 0; - - dump: - if (DumpStatesOnHalt && !states.empty()) { - klee_message("halting execution, dumping remaining states"); - for (std::set<ExecutionState*>::iterator - it = states.begin(), ie = states.end(); - it != ie; ++it) { - ExecutionState &state = **it; - stepInstruction(state); // keep stats rolling - terminateStateEarly(state, "Execution halting."); - } - updateStates(0); - } + + doDumpStates(); } std::string Executor::getAddressInfo(ExecutionState &state, @@ -2722,11 +2821,12 @@ void Executor::terminateState(ExecutionState &state) { interpreterHandler->incPathsExplored(); - std::set<ExecutionState*>::iterator it = addedStates.find(&state); + std::vector<ExecutionState *>::iterator it = + std::find(addedStates.begin(), addedStates.end(), &state); if (it==addedStates.end()) { state.pc = state.prevPC; - removedStates.insert(&state); + removedStates.push_back(&state); } else { // never reached searcher, just delete immediately std::map< ExecutionState*, std::vector<SeedInfo> >::iterator it3 = @@ -3390,7 +3490,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) { @@ -3430,6 +3533,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]); |