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

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> 
> 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.
> 
> 

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.

Few comments about the code below,

> 
> 
> 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);

Why did we need to split cds_lfht_next_duplicate at all ?

Could we simply pass a:

  struct cds_lfht_iter d_iter = { .node = node, .iter = iter };

  cds_lfht_next_duplicate(ht, &d_iter);

without splitting it ?

I am probably missing something here...

Thanks,

Mathieu

> +				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
> 

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