Fix memory leaks of ``Array`` objects detected by ASan.

Some of these leaks were introduced by the factory constructor for Array
objects (f049ff3bc04daead8c3bb9f06e89e71e2054c82a) but a few others have
been around for far longer.

This leak was fixed by introducing a ``ArrayCache`` object which has two
purposes

* Retains ownership of all created ``Array`` objects and destroys them when
  the ``ArrayCache`` destructor is called.
* Mimic the caching behaviour for symbolic arrays that was introduced
  by f049ff3bc04daead8c3bb9f06e89e71e2054c82a where arrays with the same
  name and size get "uniqued".

The Executor now maintains a ``arrayCache`` member that it uses and
passes by pointer to objects that need to construct ``Array`` objects (i.e.
``ObjectState``). This way when the Executor is destroyed all the
``Array`` objects get freed which seems like the right time to do this.

For Kleaver the ``ParserImpl`` has a ``TheArrayCache`` member that is
used for building ``Array`` objects. This means that the Parser must
live as long as the built expressions will be used otherwise we will
have a use after free. I'm not sure this is the right design choice.
It might be better to transfer ownership of the ``Array`` objects to
the root ``Decl`` returned by the parser.

13 files changed, 190 insertions, 90 deletions

diff --git a/include/klee/Expr.h b/include/klee/Expr.h
index c5a110f8..731aa446 100644
--- a/include/klee/Expr.h
+++ b/include/klee/Expr.h
@@ -32,6 +32,7 @@ namespace llvm {
 namespace klee {
 
 class Array;
+class ArrayCache;
 class ConstantExpr;
 class ObjectState;
 
@@ -619,21 +620,10 @@ public:
 private:
   unsigned hashValue;
 
-
-  /// The symbolic array singleton map is necessary to allow sharing
-  /// of Arrays across states, essentially performing a (limited) form
-  /// of alpha renaming.  Some Solvers use maps such as < const *Array,
-  /// std::vector<unsigned> >.  This causes problems because stored
-  /// answers can't be easily recovered.  Even worse, in read
-  /// expressions, such as (read array 32), array is a pointer, and
-  /// cached solutions are missed because the two Array instances
-  /// aren't recognized as the same.
-  static std::map < unsigned, std::vector < const Array * > * > symbolicArraySingletonMap;
-
-  // This shouldn't be allowed since it is a singleton class
+  // FIXME: Make =delete when we switch to C++11
   Array(const Array& array);
 
-  // This shouldn't be allowed since it is a singleton class
+  // FIXME: Make =delete when we switch to C++11
   Array& operator =(const Array& array);
 
   ~Array();
@@ -675,20 +665,7 @@ public:
   /// ComputeHash must take into account the name, the size, the domain, and the range
   unsigned computeHash();
   unsigned hash() const { return hashValue; }
-
-  /*
-   * Fairly simple idea.  Symbolic arrays have constant values of size
-   * 0, while concrete arrays have constant values of size > 0.
-   * Therefore, on each call, an array is created and, if it is
-   * concrete, it is simply returned.  If instead it is symbolic, then
-   * a map is checked to see if it was created before, so there is
-   * only a single instance floating out there.
-   */
-  static const Array * CreateArray(const std::string &_name, uint64_t _size,
-				   const ref<ConstantExpr> *constantValuesBegin = 0,
-				   const ref<ConstantExpr> *constantValuesEnd = 0,
-				   Expr::Width _domain = Expr::Int32,
-				   Expr::Width _range = Expr::Int8);
+  friend class ArrayCache;
 };
 
 /// Class representing a complete list of updates into an array.
diff --git a/include/klee/util/ArrayCache.h b/include/klee/util/ArrayCache.h
new file mode 100644
index 00000000..3dd88a11
--- /dev/null
+++ b/include/klee/util/ArrayCache.h
@@ -0,0 +1,89 @@
+//===-- ArrayCache.h --------------------------------------------*- C++ -*-===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef KLEE_ARRAY_CACHE_H
+#define KLEE_ARRAY_CACHE_H
+
+#include "klee/Expr.h"
+
+// FIXME: Remove this hack when we switch to C++11
+#ifdef _LIBCPP_VERSION
+#include <unordered_set>
+#define unordered_set std::unordered_set
+#else
+#include <tr1/unordered_set>
+#define unordered_set std::tr1::unordered_set
+#endif
+
+#include <string>
+#include <vector>
+
+namespace klee {
+
+// FIXME: This is copied from ``klee/util/ArrayExprHash.h``.
+// We can't include it here becaues the includes are messed up
+// in that file.
+struct EquivArrayHashFn {
+  unsigned operator()(const Array *array) const {
+    return (array ? array->hash() : 0);
+  }
+};
+
+struct EquivArrayCmpFn {
+  bool operator()(const Array *array1, const Array *array2) const {
+    if (array1 == NULL || array2 == NULL)
+      return false;
+    return (array1->size == array2->size) && (array1->name == array2->name);
+  }
+};
+
+/// Provides an interface for creating and destroying Array objects.
+class ArrayCache {
+public:
+  ArrayCache() {}
+  ~ArrayCache();
+  /// Create an Array object.
+  //
+  /// Symbolic Arrays are cached so that only one instance exists. This
+  /// provides a limited form of "alpha-renaming". Constant arrays are not
+  /// cached.
+  ///
+  /// This class retains ownership of Array object so that upon destruction
+  /// of this object all allocated Array objects are deleted.
+  ///
+  /// \param _name The name of the array
+  /// \param _size The size of the array in bytes
+  /// \param constantValuesBegin A pointer to the beginning of a block of
+  //         memory that constains a ``ref<ConstantExpr>`` (i.e. concrete values
+  //         for the //array). This should be NULL for symbolic arrays.
+  /// for symbolic arrays.
+  /// \param constantValuesEnd A pointer +1 pass the end of a block of memory
+  ///        that contains a ``ref<ConstantExpr>``. This should be NULL for a
+  ///        symbolic array.
+  /// \param _domain The size of the domain (i.e. the bitvector used to index
+  /// the array)
+  /// \param _range The size of range (i.e. the bitvector that is indexed to)
+  const Array *CreateArray(const std::string &_name, uint64_t _size,
+                           const ref<ConstantExpr> *constantValuesBegin = 0,
+                           const ref<ConstantExpr> *constantValuesEnd = 0,
+                           Expr::Width _domain = Expr::Int32,
+                           Expr::Width _range = Expr::Int8);
+
+private:
+  typedef unordered_set<const Array *, klee::EquivArrayHashFn,
+                        klee::EquivArrayCmpFn> ArrayHashMap;
+  ArrayHashMap cachedSymbolicArrays;
+  typedef std::vector<const Array *> ArrayPtrVec;
+  ArrayPtrVec concreteArrays;
+};
+}
+
+#undef unordered_set
+
+#endif /* KLEE_ARRAY_CACHE__H */
diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp
index 0b34c357..4a21be3e 100644
--- a/lib/Core/Executor.cpp
+++ b/lib/Core/Executor.cpp
@@ -337,7 +337,7 @@ Executor::Executor(const InterpreterOptions &opts,
   
   this->solver = new TimingSolver(solver, EqualitySubstitution);
 
-  memory = new MemoryManager();
+  memory = new MemoryManager(&arrayCache);
 }
 
 
@@ -2918,8 +2918,9 @@ ref<Expr> Executor::replaceReadWithSymbolic(ExecutionState &state,
   // and return it.
   
   static unsigned id;
-  const Array *array = Array::CreateArray("rrws_arr" + llvm::utostr(++id),
-					  Expr::getMinBytesForWidth(e->getWidth()));
+  const Array *array =
+      arrayCache.CreateArray("rrws_arr" + llvm::utostr(++id),
+                             Expr::getMinBytesForWidth(e->getWidth()));
   ref<Expr> res = Expr::createTempRead(array, e->getWidth());
   ref<Expr> eq = NotOptimizedExpr::create(EqExpr::create(e, res));
   llvm::errs() << "Making symbolic: " << eq << "\n";
@@ -3257,7 +3258,7 @@ void Executor::executeMakeSymbolic(ExecutionState &state,
     while (!state.arrayNames.insert(uniqueName).second) {
       uniqueName = name + "_" + llvm::utostr(++id);
     }
-    const Array *array = Array::CreateArray(uniqueName, mo->size);
+    const Array *array = arrayCache.CreateArray(uniqueName, mo->size);
     bindObjectInState(state, mo, false, array);
     state.addSymbolic(mo, array);
     
@@ -3415,8 +3416,8 @@ void Executor::runFunctionAsMain(Function *f,
 
   // hack to clear memory objects
   delete memory;
-  memory = new MemoryManager();
-  
+  memory = new MemoryManager(NULL);
+
   globalObjects.clear();
   globalAddresses.clear();
 
diff --git a/lib/Core/Executor.h b/lib/Core/Executor.h
index 523b3648..919d2124 100644
--- a/lib/Core/Executor.h
+++ b/lib/Core/Executor.h
@@ -20,6 +20,7 @@
 #include "klee/Internal/Module/Cell.h"
 #include "klee/Internal/Module/KInstruction.h"
 #include "klee/Internal/Module/KModule.h"
+#include "klee/util/ArrayCache.h"
 
 #include "llvm/ADT/Twine.h"
 
@@ -177,7 +178,10 @@ private:
 
   /// The maximum time to allow for a single core solver query.
   /// (e.g. for a single STP query)
-  double coreSolverTimeout; 
+  double coreSolverTimeout;
+
+  /// Assumes ownership of the created array objects
+  ArrayCache arrayCache;
 
   llvm::Function* getTargetFunction(llvm::Value *calledVal,
                                     ExecutionState &state);
diff --git a/lib/Core/Memory.cpp b/lib/Core/Memory.cpp
index 12ca7104..72f0a1fb 100644
--- a/lib/Core/Memory.cpp
+++ b/lib/Core/Memory.cpp
@@ -14,6 +14,7 @@
 #include "klee/Solver.h"
 #include "klee/util/BitArray.h"
 #include "klee/Internal/Support/ErrorHandling.h"
+#include "klee/util/ArrayCache.h"
 
 #include "ObjectHolder.h"
 #include "MemoryManager.h"
@@ -110,9 +111,9 @@ ObjectState::ObjectState(const MemoryObject *mo)
     readOnly(false) {
   mo->refCount++;
   if (!UseConstantArrays) {
-    // FIXME: Leaked.
     static unsigned id = 0;
-    const Array *array = Array::CreateArray("tmp_arr" + llvm::utostr(++id), size);
+    const Array *array =
+        getArrayCache()->CreateArray("tmp_arr" + llvm::utostr(++id), size);
     updates = UpdateList(array, 0);
   }
   memset(concreteStore, 0, size);
@@ -176,6 +177,11 @@ ObjectState::~ObjectState() {
   }
 }
 
+ArrayCache *ObjectState::getArrayCache() const {
+  assert(object && "object was NULL");
+  return object->parent->getArrayCache();
+}
+
 /***/
 
 const UpdateList &ObjectState::getUpdates() const {
@@ -215,15 +221,10 @@ const UpdateList &ObjectState::getUpdates() const {
       Contents[Index->getZExtValue()] = Value;
     }
 
-    // FIXME: We should unique these, there is no good reason to create multiple
-    // ones.
-
-    // Start a new update list.
-    // FIXME: Leaked.
     static unsigned id = 0;
-    const Array *array = Array::CreateArray("const_arr" + llvm::utostr(++id), size,
-					    &Contents[0],
-					    &Contents[0] + Contents.size());
+    const Array *array = getArrayCache()->CreateArray(
+        "const_arr" + llvm::utostr(++id), size, &Contents[0],
+        &Contents[0] + Contents.size());
     updates = UpdateList(array, 0);
 
     // Apply the remaining (non-constant) writes.
diff --git a/lib/Core/Memory.h b/lib/Core/Memory.h
index 637f8772..d08bfb0c 100644
--- a/lib/Core/Memory.h
+++ b/lib/Core/Memory.h
@@ -27,6 +27,7 @@ namespace klee {
 class BitArray;
 class MemoryManager;
 class Solver;
+class ArrayCache;
 
 class MemoryObject {
   friend class STPBuilder;
@@ -234,6 +235,7 @@ private:
   void setKnownSymbolic(unsigned offset, Expr *value);
 
   void print();
+  ArrayCache *getArrayCache() const;
 };
   
 } // End klee namespace
diff --git a/lib/Core/MemoryManager.h b/lib/Core/MemoryManager.h
index f398db62..01683443 100644
--- a/lib/Core/MemoryManager.h
+++ b/lib/Core/MemoryManager.h
@@ -19,14 +19,16 @@ namespace llvm {
 
 namespace klee {
   class MemoryObject;
+  class ArrayCache;
 
   class MemoryManager {
   private:
     typedef std::set<MemoryObject*> objects_ty;
     objects_ty objects;
+    ArrayCache *const arrayCache;
 
   public:
-    MemoryManager() {}
+    MemoryManager(ArrayCache *arrayCache) : arrayCache(arrayCache) {}
     ~MemoryManager();
 
     MemoryObject *allocate(uint64_t size, bool isLocal, bool isGlobal,
@@ -35,6 +37,7 @@ namespace klee {
                                 const llvm::Value *allocSite);
     void deallocate(const MemoryObject *mo);
     void markFreed(MemoryObject *mo);
+    ArrayCache *getArrayCache() const { return arrayCache; }
   };
 
 } // End klee namespace
diff --git a/lib/Expr/ArrayCache.cpp b/lib/Expr/ArrayCache.cpp
new file mode 100644
index 00000000..b669f237
--- /dev/null
+++ b/lib/Expr/ArrayCache.cpp
@@ -0,0 +1,47 @@
+#include "klee/util/ArrayCache.h"
+
+namespace klee {
+
+ArrayCache::~ArrayCache() {
+  // Free Allocated Array objects
+  for (ArrayHashMap::iterator ai = cachedSymbolicArrays.begin(),
+                              e = cachedSymbolicArrays.end();
+       ai != e; ++ai) {
+    delete *ai;
+  }
+  for (ArrayPtrVec::iterator ai = concreteArrays.begin(),
+                             e = concreteArrays.end();
+       ai != e; ++ai) {
+    delete *ai;
+  }
+}
+
+const Array *
+ArrayCache::CreateArray(const std::string &_name, uint64_t _size,
+                        const ref<ConstantExpr> *constantValuesBegin,
+                        const ref<ConstantExpr> *constantValuesEnd,
+                        Expr::Width _domain, Expr::Width _range) {
+
+  const Array *array = new Array(_name, _size, constantValuesBegin,
+                                 constantValuesEnd, _domain, _range);
+  if (array->isSymbolicArray()) {
+    std::pair<ArrayHashMap::const_iterator, bool> success =
+        cachedSymbolicArrays.insert(array);
+    if (success.second) {
+      // Cache miss
+      return array;
+    }
+    // Cache hit
+    delete array;
+    array = *(success.first);
+    assert(array->isSymbolicArray() &&
+           "Cached symbolic array is no longer symbolic");
+    return array;
+  } else {
+    // Treat every constant array as distinct so we never cache them
+    assert(array->isConstantArray());
+    concreteArrays.push_back(array); // For deletion later
+    return array;
+  }
+}
+}
diff --git a/lib/Expr/Expr.cpp b/lib/Expr/Expr.cpp
index baa85663..2c64aff4 100644
--- a/lib/Expr/Expr.cpp
+++ b/lib/Expr/Expr.cpp
@@ -494,41 +494,6 @@ unsigned Array::computeHash() {
   hashValue = res;
   return hashValue; 
 }
-
-std::map<unsigned, std::vector<const Array *> *> Array::symbolicArraySingletonMap;
-
-const Array * Array::CreateArray(const std::string &_name, uint64_t _size,
-                                 const ref<ConstantExpr> *constantValuesBegin,
-                                 const ref<ConstantExpr> *constantValuesEnd,
-                                 Expr::Width _domain,
-				 Expr::Width _range) {
-
-  const Array * array = new Array(_name, _size, constantValuesBegin, constantValuesEnd, _domain,_range);
-  if (array->constantValues.size() == 0) { // symbolic array
-    unsigned hash = array->hash();
-    std::vector<const Array *> * bucket = Array::symbolicArraySingletonMap[hash];
-    if (bucket){
-      for (std::vector<const Array*>::const_iterator it = bucket->begin();
-	   it != bucket->end(); it ++){
-        const Array* prospect = *it;
-	if (prospect->size == array->size && prospect->name == array->name){
-    	  delete array;
-    	  return prospect;
-    	}
-      }
-      bucket->push_back(array);
-      return array;
-    } else {
-      bucket = new std::vector<const Array *>();
-      bucket->push_back(array);
-      Array::symbolicArraySingletonMap[hash] = bucket;
-      return array;
-    }
-  } else { // concrete array
-    return array;
-  }
-}
-
 /***/
 
 ref<Expr> ReadExpr::create(const UpdateList &ul, ref<Expr> index) {
diff --git a/lib/Expr/Parser.cpp b/lib/Expr/Parser.cpp
index 23a292fa..854f6d52 100644
--- a/lib/Expr/Parser.cpp
+++ b/lib/Expr/Parser.cpp
@@ -16,6 +16,7 @@
 #include "klee/ExprBuilder.h"
 #include "klee/Solver.h"
 #include "klee/util/ExprPPrinter.h"
+#include "klee/util/ArrayCache.h"
 
 #include "llvm/ADT/APInt.h"
 #include "llvm/Support/MemoryBuffer.h"
@@ -109,6 +110,7 @@ namespace {
     const std::string Filename;
     const MemoryBuffer *TheMemoryBuffer;
     ExprBuilder *Builder;
+    ArrayCache TheArrayCache;
 
     Lexer TheLexer;
     unsigned MaxErrors;
@@ -521,10 +523,10 @@ DeclResult ParserImpl::ParseArrayDecl() {
   const Identifier *Label = GetOrCreateIdentifier(Name);
   const Array *Root;
   if (!Values.empty())
-    Root = Array::CreateArray(Label->Name, Size.get(),
-			      &Values[0], &Values[0] + Values.size());
+    Root = TheArrayCache.CreateArray(Label->Name, Size.get(), &Values[0],
+                                     &Values[0] + Values.size());
   else
-    Root = Array::CreateArray(Label->Name, Size.get());
+    Root = TheArrayCache.CreateArray(Label->Name, Size.get());
   ArrayDecl *AD = new ArrayDecl(Label, Size.get(), 
                                 DomainType.get(), RangeType.get(), Root);
 
@@ -1306,7 +1308,9 @@ VersionResult ParserImpl::ParseVersionSpecifier() {
   VersionResult Res = ParseVersion();
   // Define update list to avoid use-of-undef errors.
   if (!Res.isValid()) {
-    Res = VersionResult(true, UpdateList(Array::CreateArray("", 0), NULL));
+    // FIXME: I'm not sure if this is right. Do we need a unique array here?
+    Res =
+        VersionResult(true, UpdateList(TheArrayCache.CreateArray("", 0), NULL));
   }
   
   if (Label)
diff --git a/unittests/Expr/ExprTest.cpp b/unittests/Expr/ExprTest.cpp
index d05eb7ec..25129d8e 100644
--- a/unittests/Expr/ExprTest.cpp
+++ b/unittests/Expr/ExprTest.cpp
@@ -11,6 +11,7 @@
 #include "gtest/gtest.h"
 
 #include "klee/Expr.h"
+#include "klee/util/ArrayCache.h"
 
 using namespace klee;
 
@@ -29,9 +30,10 @@ TEST(ExprTest, BasicConstruction) {
 }
 
 TEST(ExprTest, ConcatExtract) {
-  const Array *array = Array::CreateArray("arr0", 256);
+  ArrayCache ac;
+  const Array *array = ac.CreateArray("arr0", 256);
   ref<Expr> read8 = Expr::createTempRead(array, 8);
-  const Array *array2 = Array::CreateArray("arr1", 256);
+  const Array *array2 = ac.CreateArray("arr1", 256);
   ref<Expr> read8_2 = Expr::createTempRead(array2, 8);
   ref<Expr> c100 = getConstant(100, 8);
 
@@ -81,10 +83,11 @@ TEST(ExprTest, ConcatExtract) {
 }
 
 TEST(ExprTest, ExtractConcat) {
-  const Array *array = Array::CreateArray("arr2", 256);
+  ArrayCache ac;
+  const Array *array = ac.CreateArray("arr2", 256);
   ref<Expr> read64 = Expr::createTempRead(array, 64);
 
-  const Array *array2 = Array::CreateArray("arr3", 256);
+  const Array *array2 = ac.CreateArray("arr3", 256);
   ref<Expr> read8_2 = Expr::createTempRead(array2, 8);
   
   ref<Expr> extract1 = ExtractExpr::create(read64, 36, 4);
diff --git a/unittests/Solver/SolverTest.cpp b/unittests/Solver/SolverTest.cpp
index d9aa9b56..16bd3ce4 100644
--- a/unittests/Solver/SolverTest.cpp
+++ b/unittests/Solver/SolverTest.cpp
@@ -13,6 +13,7 @@
 #include "klee/Constraints.h"
 #include "klee/Expr.h"
 #include "klee/Solver.h"
+#include "klee/util/ArrayCache.h"
 #include "llvm/ADT/StringExtras.h"
 
 using namespace klee;
@@ -32,6 +33,10 @@ ref<Expr> getConstant(int value, Expr::Width width) {
   return ConstantExpr::create(trunc, width);
 }
 
+// We have to have the cache globally scopped (and not in ``testOperation``)
+// because the Solver (i.e. in STP's case the STPBuilder) holds on to pointers
+// to allocated Arrays.
+ArrayCache ac;
 
 template<class T>
 void testOperation(Solver &solver,
@@ -46,7 +51,7 @@ void testOperation(Solver &solver,
 
     unsigned size = Expr::getMinBytesForWidth(operandWidth);
     static uint64_t id = 0;
-    const Array *array = Array::CreateArray("arr" + llvm::utostr(++id), size);
+    const Array *array = ac.CreateArray("arr" + llvm::utostr(++id), size);
     symbolicArgs.push_back(Expr::CreateArg(Expr::createTempRead(array, 
                                                                 operandWidth)));
   }
diff --git a/utils/sanitizers/lsan.txt b/utils/sanitizers/lsan.txt
index 93826a7d..836d60c1 100644
--- a/utils/sanitizers/lsan.txt
+++ b/utils/sanitizers/lsan.txt
@@ -11,7 +11,6 @@ leak:tools/kleaver/main.cpp
 leak:lib/Expr/Parser.cpp
 
 # These are bad, these definitely need fixing
-leak:klee::Array::CreateArray
 leak:klee::ConstantExpr::alloc
 leak:klee::ConcatExpr::alloc
 leak:klee::ReadExpr::alloc