[ltt-dev] [PATCH 6/6 respin] 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(), because it does need.

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

diff --git a/rculfhash.c b/rculfhash.c
index 851bbef..65e1dab 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -897,22 +897,38 @@ void _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 (unique_ret
 			    && !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)) {
-				unique_ret->node = clear_flag(iter);
-				unique_ret->next = next;
+			    && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash) {
+				struct cds_lfht_iter d_iter = {.node = node, .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(ht, &d_iter);
+				if (!d_iter.node)
+					goto insert;
+
+				*unique_ret = d_iter;
 				return;
 			}
+
 			/* 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