Merge pull request #363 from MartinNowack/feat_determ_allocator

Add support for deterministic allocation

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