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

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 10/27/2011 03:59 PM, Mathieu Desnoyers wrote:
> > * 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...
> 
> The result is correct/the same, but it may introduce some confusions,
> because the reason I don't use cds_lfht_next_duplicate is
> "@node is not already in the list".
> (I didn't find that the result are the same then.)
> 
> Since the result are the same, I will respin it.

Great! I look forward to see the respinned patchset!

Thanks,

Mathieu

> 
> Thanks,
> Lai
> 
> > 
> > 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