arangodb · KVS85 · Jun 28, 2021 · Jun 23, 2021 · Jun 24, 2021 · Jun 25, 2021
diff --git a/CHANGELOG b/CHANGELOG
@@ -1,6 +1,10 @@
 devel
 -----
 
+* Fixed DEVSUP-799: unique vertex getter may point to invalid memory after being
+  resetted, resulting in undefined behavior for traversals returning unique
+  vertices from inner FOR loops.
+
 * For cluster AQL queries, let the coordinator determine the query id to be 
   used on DB servers. This allows the coordinator to roll back AQL query setup
   requests via the query id. Previously, the DB servers each generated a local

diff --git a/arangod/Cluster/ClusterTraverser.cpp b/arangod/Cluster/ClusterTraverser.cpp
@@ -83,10 +83,14 @@ void ClusterTraverser::setStartVertex(std::string const& vid) {
 }
 
 void ClusterTraverser::clear() {
-  traverserCache()->clear();
-
+  _vertexGetter->clear();
   _vertices.clear();
   _verticesToFetch.clear();
+
+#ifdef ARANGODB_ENABLE_MAINTAINER_MODE
+  TRI_ASSERT(!_vertexGetter->pointsIntoTraverserCache());
+#endif
+  traverserCache()->clear();
 }
 
 bool ClusterTraverser::getVertex(VPackSlice edge, arangodb::traverser::EnumeratedPath& path) {

diff --git a/arangod/Graph/SingleServerTraverser.cpp b/arangod/Graph/SingleServerTraverser.cpp
@@ -72,7 +72,13 @@ void SingleServerTraverser::setStartVertex(std::string const& vid) {
   _done = false;
 }
 
-void SingleServerTraverser::clear() { traverserCache()->clear(); }
+void SingleServerTraverser::clear() {
+  _vertexGetter->clear();
+#ifdef ARANGODB_ENABLE_MAINTAINER_MODE
+  TRI_ASSERT(!_vertexGetter->pointsIntoTraverserCache());
+#endif
+  traverserCache()->clear();
+}
 
 bool SingleServerTraverser::getVertex(VPackSlice edge, arangodb::traverser::EnumeratedPath& path) {
   return _vertexGetter->getVertex(edge, path);

diff --git a/arangod/Graph/Traverser.cpp b/arangod/Graph/Traverser.cpp
@@ -74,6 +74,15 @@ bool Traverser::VertexGetter::getSingleVertex(arangodb::velocypack::Slice edge,
 
 void Traverser::VertexGetter::reset(arangodb::velocypack::StringRef const&) {}
 
+// nothing to do
+void Traverser::VertexGetter::clear() {}
+
+#ifdef ARANGODB_ENABLE_MAINTAINER_MODE
+bool Traverser::VertexGetter::pointsIntoTraverserCache() const noexcept {
+  return false;
+}
+#endif
+
 bool Traverser::VertexGetter::getVertex(arangodb::velocypack::StringRef vertex, size_t depth) {
   return _traverser->vertexMatchesConditions(vertex, depth);
 }
@@ -136,6 +145,19 @@ bool Traverser::UniqueVertexGetter::getSingleVertex(arangodb::velocypack::Slice
   return true;
 }
 
+void Traverser::UniqueVertexGetter::clear() {
+  // we must make sure that we clear _returnedVertices, not only for
+  // correctness, but also because it may point into memory that is
+  // going to be freed after this call.
+  _returnedVertices.clear();
+}
+
+#ifdef ARANGODB_ENABLE_MAINTAINER_MODE
+bool Traverser::UniqueVertexGetter::pointsIntoTraverserCache() const noexcept {
+  return !_returnedVertices.empty();
+}
+#endif
+
 void Traverser::UniqueVertexGetter::reset(arangodb::velocypack::StringRef const& startVertex) {
   _returnedVertices.clear();
   // The startVertex always counts as visited!

diff --git a/arangod/Graph/Traverser.h b/arangod/Graph/Traverser.h
@@ -133,6 +133,12 @@ class Traverser {
 
     virtual void reset(arangodb::velocypack::StringRef const&);
 
+    virtual void clear();
+
+#ifdef ARANGODB_ENABLE_MAINTAINER_MODE
+    virtual bool pointsIntoTraverserCache() const noexcept;
+#endif
+
    protected:
     Traverser* _traverser;
   };
@@ -158,6 +164,12 @@ class Traverser {
 
     void reset(arangodb::velocypack::StringRef const&) override;
 
+    void clear() override;
+
+#ifdef ARANGODB_ENABLE_MAINTAINER_MODE
+    bool pointsIntoTraverserCache() const noexcept override;
+#endif
+
    private:
     std::unordered_set<arangodb::velocypack::StringRef> _returnedVertices;
   };

diff --git a/arangod/Graph/TraverserCache.cpp b/arangod/Graph/TraverserCache.cpp
@@ -89,9 +89,9 @@ TraverserCache::~TraverserCache() {
 void TraverserCache::clear() {
   _query.resourceMonitor().decreaseMemoryUsage(_persistedStrings.size() * ::costPerPersistedString);
 
-  _stringHeap.clear();
   _persistedStrings.clear();
   _mmdr.clear();
+  _stringHeap.clear();
 }
 
 VPackSlice TraverserCache::lookupToken(EdgeDocumentToken const& idToken) {

diff --git a/tests/js/server/aql/aql-graph-traverser.js b/tests/js/server/aql/aql-graph-traverser.js
@@ -3301,6 +3301,44 @@ function subQuerySuite() {
       cleanup();
     },
 
+    testUniqueVertexGetterMemoryIssue: function () {
+      // test case: UniqueVertexGetter keeps track of which vertices
+      // were already visited. the vertex id tracked pointed to memory
+      // which was allocated only temporarily and that became invalid
+      // once TraverserCache::clear() got called.
+      let query = `WITH ${vn} FOR i IN 1..3 FOR v, e, p IN 1..3 OUTBOUND '${vertex.A}' ${en} OPTIONS { uniqueVertices: 'global', bfs: true } SORT v._key RETURN v._key`;
+      let result = db._query(query).toArray();
+      assertEqual([ 
+        "B", "B", "B", 
+        "B1", "B1", "B1", 
+        "B2", "B2", "B2", 
+        "B3", "B3", "B3", 
+        "B4", "B4", "B4", 
+        "B5", "B5", "B5", 
+        "C", "C", "C", 
+        "C1", "C1", "C1", 
+        "C2", "C2", "C2", 
+        "C3", "C3", "C3", 
+        "C4", "C4", "C4", 
+        "C5", "C5", "C5", 
+        "D", "D", "D", 
+        "D1", "D1", "D1", 
+        "D2", "D2", "D2", 
+        "D3", "D3", "D3", 
+        "D4", "D4", "D4", 
+        "D5", "D5", "D5" 
+      ], result);
+
+      // while we are here, try a different query as well
+      query = `WITH ${vn} FOR i IN 1..3 LET sub = (FOR v, e, p IN 1..3 OUTBOUND '${vertex.A}' ${en} OPTIONS { uniqueVertices: 'global', bfs: true } SORT v._key RETURN v._key) RETURN sub`;
+      result = db._query(query).toArray();
+      assertEqual([ 
+        [ "B", "B1", "B2", "B3", "B4", "B5", "C", "C1", "C2", "C3", "C4", "C5", "D", "D1", "D2", "D3", "D4", "D5" ], 
+        [ "B", "B1", "B2", "B3", "B4", "B5", "C", "C1", "C2", "C3", "C4", "C5", "D", "D1", "D2", "D3", "D4", "D5" ], 
+        [ "B", "B1", "B2", "B3", "B4", "B5", "C", "C1", "C2", "C3", "C4", "C5", "D", "D1", "D2", "D3", "D4", "D5" ] 
+      ], result);
+    },
+
     // The test is that the traversal in subquery has more then LIMIT many
     // results. In case of a bug the cursor of the traversal is reused for the second
     // iteration as well and does not reset.