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

[Mathieu Desnoyers]

Merged as:

commit 238cc06e5728e3a642d4d22bd4fc199cfd265110
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date:   Fri Oct 28 06:23:40 2011 +0200

    rculfhash: fix uniquely add vs cds_lfht_next observation semantic
    
    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.
    
    [ Note by Mathieu Desnoyers:
    
    I agree that your semantic fix is needed for ensuring that cds_lfht_next
    is semantically correct with add_unique semantic.
    
    Just a note: the most important lookup/get next API semantic in my view
    is the lookup + cds_lfht_next_duplicate, which is the typical use case
    for looking up and node and getting all the duplicate keys.
    
    Ideally, we want both get_next and get_next_duplicate to provide the
    correct semantic.
    
    I think the reason your fix here seems to work and not break the
    behavior of cds_lfht_next_duplicate is because you only put nodes added
    with add_unique at the beginning of the same-hash-value-chain. It's a
    good thing that you don't try doing this for other add mode (allowing
    duplicates), because cds_lfht_next_duplicate requires duplicate nodes to
    be next one to another. And you patch keeps this behavior.
    
    ]
    
    Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

diff --git a/rculfhash.c b/rculfhash.c
index 18a3cb8..b67acc8 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -894,22 +894,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))

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com