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/MemoryManager.h | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'lib/Core/MemoryManager.h') diff --git a/lib/Core/MemoryManager.h b/lib/Core/MemoryManager.h index 01683443..d80e44af 100644 --- a/lib/Core/MemoryManager.h +++ b/lib/Core/MemoryManager.h @@ -31,8 +31,12 @@ namespace klee { MemoryManager(ArrayCache *arrayCache) : 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); + 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); -- 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/MemoryManager.h') 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 From 05a0962a50fede85aae254667d5dac1586744eb3 Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Tue, 24 May 2016 15:13:31 +0200 Subject: Clang-formated MemoryManager --- lib/Core/MemoryManager.cpp | 26 ++++++++--------- lib/Core/MemoryManager.h | 70 +++++++++++++++++++++++----------------------- 2 files changed, 46 insertions(+), 50 deletions(-) (limited to 'lib/Core/MemoryManager.h') diff --git a/lib/Core/MemoryManager.cpp b/lib/Core/MemoryManager.cpp index 560bb6f6..004ce090 100644 --- a/lib/Core/MemoryManager.cpp +++ b/lib/Core/MemoryManager.cpp @@ -53,8 +53,7 @@ llvm::cl::opt DeterministicStartAddress( /***/ MemoryManager::MemoryManager(ArrayCache *_arrayCache) - : arrayCache(_arrayCache), deterministicSpace(0), - nextFreeSlot(0), + : arrayCache(_arrayCache), deterministicSpace(0), nextFreeSlot(0), spaceSize(DeterministicAllocationSize.getValue() * 1024 * 1024) { if (DeterministicAllocation) { // Page boundary @@ -78,7 +77,7 @@ MemoryManager::MemoryManager(ArrayCache *_arrayCache) } } -MemoryManager::~MemoryManager() { +MemoryManager::~MemoryManager() { while (!objects.empty()) { MemoryObject *mo = *objects.begin(); if (!mo->isFixed && !DeterministicAllocation) @@ -95,7 +94,7 @@ MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, bool isGlobal, const llvm::Value *allocSite, size_t alignment) { - if (size>10*1024*1024) + if (size > 10 * 1024 * 1024) klee_warning_once(0, "Large alloc: %lu bytes. KLEE may run out of memory.", size); @@ -141,7 +140,7 @@ MemoryObject *MemoryManager::allocate(uint64_t size, bool isLocal, if (!address) return 0; - + ++stats::allocations; MemoryObject *res = new MemoryObject(address, size, isLocal, isGlobal, false, allocSite, this); @@ -152,28 +151,25 @@ 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 (objects.find(mo) != objects.end()) { if (!mo->isFixed && !DeterministicAllocation) free((void *)mo->address); objects.erase(mo); diff --git a/lib/Core/MemoryManager.h b/lib/Core/MemoryManager.h index 5c5d21ca..fc77b476 100644 --- a/lib/Core/MemoryManager.h +++ b/lib/Core/MemoryManager.h @@ -14,44 +14,44 @@ #include namespace llvm { - class Value; +class Value; } namespace klee { - class MemoryObject; - class ArrayCache; - - class MemoryManager { - private: - typedef std::set 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(); - }; +class MemoryObject; +class ArrayCache; + +class MemoryManager { +private: + typedef std::set 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 -- cgit 1.4.1