From 973e5e1b7837176071749d727e37bdfe9e3c4f0e Mon Sep 17 00:00:00 2001
From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Date: Wed, 21 Sep 2011 09:24:17 -0400
Subject: [PATCH] rculfhash: output approximation of number of nodes in
 counting

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 rculfhash.c            | 29 ++++++++++++++++++++++++++---
 tests/test_urcu_hash.c | 42 ++++++++++++++++++++++++++++++++++++++----
 urcu/rculfhash.h       |  4 +++-
 3 files changed, 67 insertions(+), 8 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index 6045f59..93c2d78 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -1446,13 +1446,25 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr)
 }
 
 void cds_lfht_count_nodes(struct cds_lfht *ht,
+		unsigned long *approx_before,
 		unsigned long *count,
-		unsigned long *removed)
+		unsigned long *removed,
+		unsigned long *approx_after)
 {
 	struct cds_lfht_node *node, *next;
 	struct _cds_lfht_node *lookup;
 	unsigned long nr_dummy = 0;
 
+	*approx_before = uatomic_read(&ht->count);
+	if (nr_cpus_mask >= 0) {
+		int i;
+
+		for (i = 0; i < nr_cpus_mask + 1; i++) {
+			*approx_before += uatomic_read(&ht->percpu_count[i].add);
+			*approx_before -= uatomic_read(&ht->percpu_count[i].del);
+		}
+	}
+
 	*count = 0;
 	*removed = 0;
 
@@ -1462,8 +1474,10 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
 	do {
 		next = rcu_dereference(node->p.next);
 		if (is_removed(next)) {
-			assert(!is_dummy(next));
-			(*removed)++;
+			if (!is_dummy(next))
+				(*removed)++;
+			else
+				(nr_dummy)++;
 		} else if (!is_dummy(next))
 			(*count)++;
 		else
@@ -1471,6 +1485,15 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
 		node = clear_flag(next);
 	} while (!is_end(node));
 	dbg_printf("number of dummy nodes: %lu\n", nr_dummy);
+	*approx_after = uatomic_read(&ht->count);
+	if (nr_cpus_mask >= 0) {
+		int i;
+
+		for (i = 0; i < nr_cpus_mask + 1; i++) {
+			*approx_after += uatomic_read(&ht->percpu_count[i].add);
+			*approx_after -= uatomic_read(&ht->percpu_count[i].del);
+		}
+	}
 }
 
 /* called with resize mutex held */
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index b68db49..1e1cf47 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -194,6 +194,26 @@ void sigusr1_handler(int signo)
 	}
 }
 
+static
+void sigusr2_handler(int signo)
+{
+	unsigned long count, removed, approx_before, approx_after;
+
+	/* Accounting */
+	printf("Counting nodes... ");
+	fflush(stdout);
+	cds_lfht_count_nodes(test_ht, &approx_before, &count, &removed,
+			&approx_after);
+	printf("done.\n");
+	printf("Approximation before node accounting: %lu nodes.\n",
+		approx_before);
+	printf("Accounting of nodes in the hash table: "
+		"%lu nodes + %lu logically removed.\n",
+		count, removed);
+	printf("Approximation after node accounting: %lu nodes.\n",
+		approx_after);
+}
+
 /*
  * returns 0 if test should end.
  */
@@ -623,7 +643,7 @@ int main(int argc, char **argv)
 	struct wr_count *count_writer;
 	unsigned long long tot_reads = 0, tot_writes = 0,
 		tot_add = 0, tot_add_exist = 0, tot_remove = 0;
-	unsigned long count, removed;
+	unsigned long count, removed, approx_before, approx_after;
 	int i, a, ret;
 	struct sigaction act;
 	unsigned int remain;
@@ -765,6 +785,13 @@ int main(int argc, char **argv)
 		perror("sigaction");
 		return -1;
 	}
+	act.sa_handler = sigusr2_handler;
+	act.sa_flags = SA_RESTART;
+	ret = sigaction(SIGUSR2, &act, NULL);
+	if (ret == -1) {
+		perror("sigaction");
+		return -1;
+	}
 
 	printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
 		duration, nr_readers, nr_writers);
@@ -846,11 +873,18 @@ int main(int argc, char **argv)
 	}
 	printf("Counting nodes... ");
 	fflush(stdout);
-	cds_lfht_count_nodes(test_ht, &count, &removed);
+	cds_lfht_count_nodes(test_ht, &approx_before, &count, &removed,
+		&approx_after);
 	printf("done.\n");
-	if (count || removed)
+	if (count || removed) {
+		printf("Approximation before node accounting: %lu nodes.\n",
+			approx_before);
 		printf("WARNING: nodes left in the hash table upon destroy: "
-			"%lu nodes + %lu logically removed.\n", count, removed);
+			"%lu nodes + %lu logically removed.\n",
+			count, removed);
+		printf("Approximation after node accounting: %lu nodes.\n",
+			approx_after);
+	}
 	ret = cds_lfht_destroy(test_ht, NULL);
 
 	if (ret)
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 1f30710..1c1f03b 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -165,8 +165,10 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr);
  * Call with rcu_read_lock held.
  */
 void cds_lfht_count_nodes(struct cds_lfht *ht,
+		unsigned long *approx_before,
 		unsigned long *count,
-		unsigned long *removed);
+		unsigned long *removed,
+		unsigned long *approx_after);
 
 /*
  * cds_lfht_lookup - lookup a node by key.
-- 
2.34.1