From cba02d09ec724def40975240290a30a78d33db8a Mon Sep 17 00:00:00 2001
From: Andreas Stöckel <astoecke@techfak.uni-bielefeld.de>
Date: Sun, 2 Nov 2014 22:58:55 +0000
Subject: fixed gc sweep rooting detection, added new gc unit test

git-svn-id: file:///var/local/svn/basicwriter@92 daaaf23c-2e50-4459-9457-1e69db5a47bf
---
 src/core/dom/Node.cpp      | 50 ++++++++++++++++++++++++----------------------
 test/core/dom/NodeTest.cpp | 46 ++++++++++++++++++++++++++++++++++++++----
 2 files changed, 68 insertions(+), 28 deletions(-)

diff --git a/src/core/dom/Node.cpp b/src/core/dom/Node.cpp
index 627ee74..ad114bf 100644
--- a/src/core/dom/Node.cpp
+++ b/src/core/dom/Node.cpp
@@ -207,16 +207,15 @@ void NodeManager::delRef(Node *tar, Node *src, bool all)
 		if (dTar->refInCount() == 0) {
 			delNode(tar, dTar);
 		} else if (dTar->rootRefCount == 0) {
+			// Call the tracing garbage collector if the number of marked nodes
+			// is larger than the threshold value and this function was not
+			// called from inside the delNode function
 			marked.insert(tar);
+			if (marked.size() >= threshold) {
+				sweep();
+			}
 		}
 	}
-
-	// Call the tracing garbage collector if the number of marked nodes is
-	// larger than the threshold value and this function was not called from
-	// inside the delNode function
-	if (deletionRecursionDepth == 0 && marked.size() >= threshold) {
-		sweep();
-	}
 }
 
 void NodeManager::delNode(Node *n, NodeDescriptor *descr)
@@ -236,21 +235,21 @@ void NodeManager::delNode(Node *n, NodeDescriptor *descr)
 		}
 	}
 
-	// Perform the actual deletion if the recursion level is zero
-	if (deletionRecursionDepth == 0) {
-		purgeDeleted();
-	}
+	purgeDeleted();
 }
 
 void NodeManager::purgeDeleted()
 {
-	ScopedIncrement incr{deletionRecursionDepth};
-	for (Node *n : deleted) {
-		marked.erase(n);
-		nodes.erase(n);
-		delete n;
+	// Perform the actual deletion if the recursion level is zero
+	if (deletionRecursionDepth == 0 && !deleted.empty()) {
+		ScopedIncrement incr{deletionRecursionDepth};
+		for (Node *n : deleted) {
+			marked.erase(n);
+			nodes.erase(n);
+			delete n;
+		}
+		deleted.clear();
 	}
-	deleted.clear();
 }
 
 void NodeManager::sweep()
@@ -263,8 +262,8 @@ void NodeManager::sweep()
 	while (!marked.empty()) {
 		// Repeat until all nodes in the "marked" list have been visited
 		while (!marked.empty()) {
-			// Increment the deletionRecursionDepth counter to prevent deletion of nodes
-			// while sweep is running
+			// Increment the deletionRecursionDepth counter to prevent deletion
+			// of nodes while sweep is running
 			ScopedIncrement incr{deletionRecursionDepth};
 			// Fetch the next node in the "marked" list and remove it
 			Node *curNode = *(marked.begin());
@@ -286,14 +285,20 @@ void NodeManager::sweep()
 					continue;
 				}
 
+				// If this node is rooted, the complete visited subgraph is
+				// rooted
+				if (descr->rootRefCount > 0) {
+					isReachable = true;
+					break;
+				}
+
 				// Iterate over all nodes leading to the current one
 				for (auto &src : descr->refIn) {
 					Node *srcNode = src.first;
 
 					// Abort if the node is nullptr or already in the reachable
 					// list
-					if (srcNode == nullptr ||
-					    reachable.find(srcNode) != reachable.end()) {
+					if (reachable.find(srcNode) != reachable.end()) {
 						isReachable = true;
 						break;
 					} else if (visited.find(srcNode) == visited.end()) {
@@ -316,9 +321,6 @@ void NodeManager::sweep()
 			}
 		}
 
-		// Decrement deletionRecursionDepth
-		deletionRecursionDepth--;
-
 		// Now purge all nodes marked for deletion
 		purgeDeleted();
 	}
diff --git a/test/core/dom/NodeTest.cpp b/test/core/dom/NodeTest.cpp
index fa7b804..3338db6 100644
--- a/test/core/dom/NodeTest.cpp
+++ b/test/core/dom/NodeTest.cpp
@@ -178,10 +178,7 @@ public:
 
 	~TestNode() override { alive = false; }
 
-	void addRef(BaseHandle<Node> h)
-	{
-		refs.push_back(acquire(h));
-	}
+	void addRef(BaseHandle<Node> h) { refs.push_back(acquire(h)); }
 };
 
 TEST(NodeManager, linearDependencies)
@@ -251,6 +248,47 @@ TEST(NodeManager, cyclicDependencies)
 	}
 }
 
+TEST(NodeManager, doubleRooted)
+{
+	std::array<bool, 4> a;
+	a.fill(false);
+
+	NodeManager mgr(1);
+	{
+		TestNode *n1, *n2;
+		n1 = new TestNode(mgr, a[1]);
+		n2 = new TestNode(mgr, a[2]);
+
+		{
+			RootedHandle<TestNode> hr1{new TestNode(mgr, a[0])};
+			{
+				RootedHandle<TestNode> hr2{new TestNode(mgr, a[3])};
+
+				// All nodes must have set their "alive" flag to true
+				for (bool v : a) {
+					ASSERT_TRUE(v);
+				}
+
+				// Create cyclical dependency between n2 and n1
+				n1->addRef(n2);
+				n2->addRef(n1);
+
+				// Reference n1 and n2 in the rooted nodes
+				hr1->addRef(n1);
+				hr2->addRef(n2);
+			}
+
+			// hr2 is dead, all other nodes are still alive
+			ASSERT_FALSE(a[3]);
+			ASSERT_TRUE(a[0] && a[1] && a[2]);
+		}
+
+		// All nodes are dead
+		for (bool v : a) {
+			ASSERT_FALSE(v);
+		}
+	}
+}
 }
 }
 
-- 
cgit v1.2.3