[lttng-dev] [rp] [RFC] Readiness for URCU release with RCU lock-free hash table

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Sat, May 05, 2012 at 02:22:12PM -0400, Mathieu Desnoyers wrote:
> > * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
[...]
> > > Just to make sure I understand -- the reason that the "del" functions
> > > say "no memory barrier" instead of "acts like rcu_dereference()" is
> > > that the "del" functions don't return anything.
> > 
> > Hrm, you bring an interesting point. I think we should change the two
> > "rcu_dereference()" in _cds_lfht_del for "CMM_LOAD_SHARED()". The
> > difference between the two is that CMM_LOAD_SHARED() does not imply a
> > read barrier between the read and following uses of the data pointed to
> > by the pointer read.
> > 
> > Same thing for "cds_lfht_is_node_deleted": the rcu_dereference() should
> > be changed for a CMM_LOAD_SHARED(), because we never use the loaded
> > pointer as a pointer to other data. There are a few other locations
> > where the pointer is only used for its flags.
> > 
> > Here is what I propose:
> > 
> > diff --git a/rculfhash.c b/rculfhash.c
> > index b9f795f..6e27436 100644
> > --- a/rculfhash.c
> > +++ b/rculfhash.c
> > @@ -923,7 +923,7 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
> >  	bucket = lookup_bucket(ht, size, bit_reverse_ulong(old_node->reverse_hash));
> >  	_cds_lfht_gc_bucket(bucket, new_node);
> > 
> > -	assert(is_removed(rcu_dereference(old_node->next)));
> > +	assert(is_removed(CMM_LOAD_SHARED(old_node->next)));
> 
> This is good.
> 
> >  	return 0;
> >  }
> > 
> > @@ -1061,7 +1061,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
> >  	 * logical removal flag). Return -ENOENT if the node had
> >  	 * previously been removed.
> >  	 */
> > -	next = rcu_dereference(node->next);
> > +	next = CMM_LOAD_SHARED(node->next);
> >  	if (caa_unlikely(is_removed(next)))
> >  		return -ENOENT;
> >  	assert(!is_bucket(next));
> 
> As long as "next" is not dereferenced anywhere, this is good.  Which
> appears to be the case.
> 
> > @@ -1082,7 +1082,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
> >  	bucket = lookup_bucket(ht, size, bit_reverse_ulong(node->reverse_hash));
> >  	_cds_lfht_gc_bucket(bucket, node);
> > 
> > -	assert(is_removed(rcu_dereference(node->next)));
> > +	assert(is_removed(CMM_LOAD_SHARED(node->next)));
> 
> This one is fine as well.
> 
> >  	/*
> >  	 * Last phase: atomically exchange node->next with a version
> >  	 * having "REMOVAL_OWNER_FLAG" set. If the returned node->next
> > @@ -1510,7 +1510,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
> >  		}
> >  		node = clear_flag(next);
> >  	}
> > -	assert(!node || !is_bucket(rcu_dereference(node->next)));
> > +	assert(!node || !is_bucket(CMM_LOAD_SHARED(node->next)));
> 
> As is this one.
> 
> >  	iter->node = node;
> >  	iter->next = next;
> >  }
> > @@ -1543,7 +1543,7 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match,
> >  		}
> >  		node = clear_flag(next);
> >  	}
> > -	assert(!node || !is_bucket(rcu_dereference(node->next)));
> > +	assert(!node || !is_bucket(CMM_LOAD_SHARED(node->next)));
> 
> Same here.
> 
> >  	iter->node = node;
> >  	iter->next = next;
> >  }
> > @@ -1565,7 +1565,7 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
> >  		}
> >  		node = clear_flag(next);
> >  	}
> > -	assert(!node || !is_bucket(rcu_dereference(node->next)));
> > +	assert(!node || !is_bucket(CMM_LOAD_SHARED(node->next)));
> 
> And here.
> 
> >  	iter->node = node;
> >  	iter->next = next;
> >  }
> > @@ -1668,7 +1668,7 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node)
> > 
> >  int cds_lfht_is_node_deleted(struct cds_lfht_node *node)
> >  {
> > -	return is_removed(rcu_dereference(node->next));
> > +	return is_removed(CMM_LOAD_SHARED(node->next));
> 
> And also here.
> 
> >  }
> > 
> >  static
> > 
> > If it's ok for you, I will first commit this change, and then commit the
> > memory barrier documentation with your reviewed-by.
> 
> Looks good!

OK, this change is committed as:

commit a85eff522c253434a9c2b53d6c3a702842fb1d5d
Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
Date:   Mon May 7 11:18:14 2012 -0400

    rculfhash: replace unneeded rcu_dereference by CMM_LOAD_SHARED
    
    The difference between the two is that CMM_LOAD_SHARED() does not imply
    a read barrier between the read and following uses of the data pointed
    to by the pointer read.
    
    All sites that only use the pointer load for its bits (never
    dereference) don't need the read barrier implied by rcu_dereference.
    
    Reviewed-by: "Paul E. McKenney" <paulmck at linux.vnet.ibm.com>
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

Thanks,

Mathieu

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