[ltt-dev] [PATCH 03/11] Move replace code out from _cds_lfht_add()
Mathieu Desnoyers
mathieu.desnoyers at efficios.com
Thu Oct 27 04:02:44 EDT 2011
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Hi, Mathieu,
>
> Does any path need to be resent/respinned in previous round?
> Don't forgot the two patches followed by this round.
Hi Lai,
Please see the individual patch reply. I specified which were merged,
and which need to be resent/explained.
Thanks!
Mathieu
>
> Thank,
> Lai
>
> On 10/27/2011 12:31 PM, Mathieu Desnoyers wrote:
> > I merged a significantly re-worked version of this patch. Thanks for
> > pointing out that the replacement could re-use the uniquify code path!
> >
> > Mathieu
> >
> > commit 83beee94416bdffdec505bc33cfd79859f6aa243
> > Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > Date: Thu Oct 27 06:30:49 2011 +0200
> >
> > Move replace code out from _cds_lfht_add()
> >
> > Original patch from Lai Jiangshan, reworked significantly to keep the
> > iterator semantic, where a "next" node is never re-read after being
> > looked up within a RCU read-side critical section after it has been
> > validated.
> >
> > Although strictly speaking the "replace" code re-checks that the next
> > node is not logically removed with a cmpxchg, I prefer to ensure that
> > all lookup paths behave similarly. It will make it easier to track
> > behavior later on if they all follow the same rules.
> >
> > Reported-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 be995df..b9c184f 100644
> > --- a/rculfhash.c
> > +++ b/rculfhash.c
> > @@ -262,17 +262,12 @@ struct partition_resize_work {
> > unsigned long start, unsigned long len);
> > };
> >
> > -enum add_mode {
> > - ADD_DEFAULT = 0,
> > - ADD_UNIQUE = 1,
> > - ADD_REPLACE = 2,
> > -};
> > -
> > static
> > -struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> > - unsigned long size,
> > - struct cds_lfht_node *node,
> > - enum add_mode mode, int dummy);
> > +void _cds_lfht_add(struct cds_lfht *ht,
> > + unsigned long size,
> > + struct cds_lfht_node *node,
> > + struct cds_lfht_iter *unique_ret,
> > + int dummy);
> >
> > /*
> > * Algorithm to reverse bits in a word by lookup table, extended to
> > @@ -855,11 +850,16 @@ end:
> > }
> > }
> >
> > +/*
> > + * A non-NULL unique_ret pointer uses the "add unique" (or uniquify) add
> > + * mode. A NULL unique_ret allows creation of duplicate keys.
> > + */
> > static
> > -struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> > - unsigned long size,
> > - struct cds_lfht_node *node,
> > - enum add_mode mode, int dummy)
> > +void _cds_lfht_add(struct cds_lfht *ht,
> > + unsigned long size,
> > + struct cds_lfht_node *node,
> > + struct cds_lfht_iter *unique_ret,
> > + int dummy)
> > {
> > struct cds_lfht_node *iter_prev, *iter, *next, *new_node, *new_next,
> > *return_node;
> > @@ -869,8 +869,9 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> > assert(!is_removed(node));
> > if (!size) {
> > assert(dummy);
> > + assert(!unique_ret);
> > node->p.next = flag_dummy(get_end());
> > - return node; /* Initial first add (head) */
> > + return; /* Initial first add (head) */
> > }
> > lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.reverse_hash));
> > for (;;) {
> > @@ -895,16 +896,15 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> > next = rcu_dereference(clear_flag(iter)->p.next);
> > if (unlikely(is_removed(next)))
> > goto gc_node;
> > - if ((mode == ADD_UNIQUE || mode == ADD_REPLACE)
> > + 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)) {
> > - if (mode == ADD_UNIQUE)
> > - return clear_flag(iter);
> > - else /* mode == ADD_REPLACE */
> > - goto replace;
> > + unique_ret->node = clear_flag(iter);
> > + unique_ret->next = next;
> > + return;
> > }
> > /* Only account for identical reverse hash once */
> > if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash
> > @@ -931,23 +931,10 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> > new_node) != iter) {
> > continue; /* retry */
> > } else {
> > - if (mode == ADD_REPLACE)
> > - return_node = NULL;
> > - else /* ADD_DEFAULT and ADD_UNIQUE */
> > - return_node = node;
> > + return_node = node;
> > goto end;
> > }
> >
> > - replace:
> > -
> > - if (!_cds_lfht_replace(ht, size, clear_flag(iter), next,
> > - node)) {
> > - return_node = clear_flag(iter);
> > - goto end; /* gc already done */
> > - } else {
> > - continue; /* retry */
> > - }
> > -
> > gc_node:
> > assert(!is_removed(iter));
> > if (is_dummy(iter))
> > @@ -958,7 +945,10 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> > /* retry */
> > }
> > end:
> > - return return_node;
> > + if (unique_ret) {
> > + unique_ret->node = return_node;
> > + /* unique_ret->next left unset, never used. */
> > + }
> > }
> >
> > static
> > @@ -1094,8 +1084,8 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
> > i, j, !i ? 0 : (1UL << (i - 1)) + j);
> > new_node->p.reverse_hash =
> > bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j);
> > - (void) _cds_lfht_add(ht, !i ? 0 : (1UL << (i - 1)),
> > - new_node, ADD_DEFAULT, 1);
> > + _cds_lfht_add(ht, !i ? 0 : (1UL << (i - 1)),
> > + new_node, NULL, 1);
> > }
> > ht->cds_lfht_rcu_read_unlock();
> > }
> > @@ -1437,7 +1427,7 @@ void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node)
> > node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
> >
> > size = rcu_dereference(ht->t.size);
> > - (void) _cds_lfht_add(ht, size, node, ADD_DEFAULT, 0);
> > + _cds_lfht_add(ht, size, node, NULL, 0);
> > ht_count_add(ht, size);
> > }
> >
> > @@ -1445,32 +1435,38 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
> > struct cds_lfht_node *node)
> > {
> > unsigned long hash, size;
> > - struct cds_lfht_node *ret;
> > + struct cds_lfht_iter iter;
> >
> > hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
> > node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
> >
> > size = rcu_dereference(ht->t.size);
> > - ret = _cds_lfht_add(ht, size, node, ADD_UNIQUE, 0);
> > - if (ret == node)
> > + _cds_lfht_add(ht, size, node, &iter, 0);
> > + if (iter.node == node)
> > ht_count_add(ht, size);
> > - return ret;
> > + return iter.node;
> > }
> >
> > struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
> > struct cds_lfht_node *node)
> > {
> > unsigned long hash, size;
> > - struct cds_lfht_node *ret;
> > + struct cds_lfht_iter iter;
> >
> > hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
> > node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash);
> >
> > size = rcu_dereference(ht->t.size);
> > - ret = _cds_lfht_add(ht, size, node, ADD_REPLACE, 0);
> > - if (ret == NULL)
> > - ht_count_add(ht, size);
> > - return ret;
> > + for (;;) {
> > + _cds_lfht_add(ht, size, node, &iter, 0);
> > + if (iter.node == node) {
> > + ht_count_add(ht, size);
> > + return NULL;
> > + }
> > +
> > + if (!_cds_lfht_replace(ht, size, iter.node, iter.next, node))
> > + return iter.node;
> > + }
> > }
> >
> > int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter,
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
More information about the lttng-dev
mailing list