[ltt-dev] [PATCH 2/2] rculfhash: fix uniquely add bug

[Lai Jiangshan]

Is it a bug?

It depends.

Current code(a combination of add_replace and add_unique)
does never generate duplicated keys, but it only
guarantees snapshot semantic: If we take a snapshot of the
hash table, we can observe that there are no duplicated keys
in the snapshot.

But this definition don't work in practice, we don't take snapshot
before observe, we actually observe them one by one.
Example:

cds_lfht_lookup(&iter);
while (should_end(&iter)) {
	do_something_with(&iter);
	cds_lfht_next(&iter);
}

In the old code, we may do_something_with/observe 2 duplicate nodes
in this practice!

Here is an identical-hash-value node chain with no duplicated keys
-->[p1]-->[p2]-->[p3]-->[p4]-->

Now thread 1 is the observing thread, it is travelling and do
something with the nodes. thread 2 deletes [p1], thread 3
add_unique [p1'] with the same key as [p1]

thread 1		thread 2	thread 3
---------------------------------------------------
do something with [p1]
do something with [p2]
			delete [p1]
					uniquely add [p1']
	(-->[p2]-->[p3]-->[p4]-->[p1']-->)
do something with [p3]
do something with [p4]
do something with [p1']
---------------------------------------------------

Now, thread 1 unexpectly handles the same key twice.
It is BUG!

If we just provide snapshot semantic, it is not useful.

So we need to provide more strict add_replace/add_unique semantic.
1) no duplicated keys should ever be observable in the table(snapshot semantic)
2) no duplicated keys should ever be observed by forward iteration in the table.

The fix:
To provide forward-iteration-observation semantic, I ensure the new inserted
node(add_unique/add_replace) is inserted as the first node of
the identical-hash-value node chain.

A little another behavior is changed in this patch, we will no do gc in
__cds_lfht_next_duplicate_node(), because it does need.




Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c |   31 ++++++++++++++++++++++++++-----
 1 files changed, 26 insertions(+), 5 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index 6ba3971..72a444d 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -833,6 +833,10 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
 	return 0;
 }
 
+static void
+__cds_lfht_next_duplicate_node(struct cds_lfht *ht, struct cds_lfht_iter *iter,
+	struct cds_lfht_node *node);
+
 static
 struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
 				unsigned long size,
@@ -862,20 +866,37 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
 				goto insert;
 			if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash))
 				goto insert;
+
 			/* dummy node is the first node of the identical-hash-value chain */
 			if (dummy && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash)
 				goto insert;
+
 			next = rcu_dereference(clear_flag(iter)->p.next);
 			if (unlikely(is_removed(next)))
 				goto gc_node;
+
+			/* uniquely add */
 			if ((mode == ADD_UNIQUE)
 			    && !is_dummy(next)
-			    && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash
-			    && !ht->compare_fct(node->key, node->key_len,
-						clear_flag(iter)->key,
-						clear_flag(iter)->key_len)) {
-				return clear_flag(iter);
+			    && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash) {
+				struct cds_lfht_iter d_iter = {.next = iter,};
+
+				/*
+				 * uniquely adding inserts the node as the first
+				 * node of the identical-hash-value node chain.
+				 *
+				 * This semantic ensures no duplicated keys
+				 * should ever be observable in the table
+				 * (including observe one node by one node
+				 * by forward iterations)
+				 */
+				__cds_lfht_next_duplicate_node(ht, &d_iter, node);
+				if (!d_iter.node)
+					goto insert;
+
+				return d_iter.node;
 			}
+
 			/* Only account for identical reverse hash once */
 			if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash
 			    && !is_dummy(next))
-- 
1.7.4.4