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

6 files changed, 124 insertions, 12 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 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; j<len+1; j++)
           os->write8(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 <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);
+
+    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