[lttng-dev] [rp] [RFC PATCH] RCU lock-free hash table: implement cds_lfht_is_node_deleted()

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Mon, Feb 20, 2012 at 11:17:09PM -0500, Mathieu Desnoyers wrote:
> > Some thoughts on how to use the RCU lock-free hash table brought me to
> > figure out that using the lock-free hash table along with a per-node
> > mutex is a quite interesting way to deal with lookup vs teardown
> > coherency.
> > 
> > A per-node lock can be used to protect concurrent modifications of an
> > entry from one another, as well as concurrent read vs modification. In
> > addition, if we ensure that each reader/updater of the node checks if
> > the node has been removed right after taking the mutex, and if we
> > perform the node removal from the hash table with the per-node mutex
> > held, we can ensure that readers/updaters will never access unlinked
> > data.
> > 
> > struct mynode {
> > 	pthread_mutex_t mutex;
> > 	struct cds_lfht node;
> > }
> > 
> > CPU A (lookup destroy and free)           CPU B (lookup and read/modify)
> > 
> >                                           rcu_read_lock()
> >                                           mynode = caa_container_of(
> >                                                 cds_lfht_lookup(...), ...);
> >                                           mutex_lock(&mynode->mutex);
> >                                           if (cds_lfht_is_node_deleted(
> > 							&mynode->node))
> >                                                goto unlock;
> > 
> >                                           read/modify structure....
> > 
> >                                         unlock:
> >                                           mutex_unlock(&mynode->mutex);
> >                                           rcu_read_unlock()
> > 
> > rcu_read_lock()
> > mynode = caa_container_of(
> >         cds_lfht_lookup(...), ...);
> > 
> > mutex_lock(&mynode->mutex);
> > 
> > cds_lfht_del(ht, &mynode->node);
> > 
> > - perform extra teardown operations
> >   with side-effects, for which call_rcu
> >   delay is not appropriate
> > 
> > mutex_unlock(&mynode->mutex);
> > rcu_read_unlock()
> > call_rcu(free, mynode);
> > 
> > To perform this efficiently, we need an API function to return whether
> > the node previously looked-up has been deleted since then.
> 
> My first thought was that the user can do this with a flag, but it does
> seem to make sense to leverage the pointer markings that you carrry!
> 
> Acked-by: Paul E. McKenney <paulmck at linux.vnet.ibm.com>

OK, merged and pushed into urcu/ht-shrink branch.

Thanks!

Mathieu

> 
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > CC: Lai Jiangshan <laijs at cn.fujitsu.com>
> > CC: Paul E. McKenney <paulmck at linux.vnet.ibm.com>
> > CC: Stephen Hemminger <shemminger at vyatta.com>
> > ---
> >  rculfhash.c      |    5 +++++
> >  urcu/rculfhash.h |   14 ++++++++++++++
> >  2 files changed, 19 insertions(+)
> > 
> > Index: userspace-rcu/rculfhash.c
> > ===================================================================
> > --- userspace-rcu.orig/rculfhash.c
> > +++ userspace-rcu/rculfhash.c
> > @@ -1553,6 +1553,11 @@ int cds_lfht_del(struct cds_lfht *ht, st
> >  	return ret;
> >  }
> > 
> > +int cds_lfht_is_node_deleted(struct cds_lfht_node *node)
> > +{
> > +	return is_removed(rcu_dereference(node->next));
> > +}
> > +
> >  static
> >  int cds_lfht_delete_bucket(struct cds_lfht *ht)
> >  {
> > Index: userspace-rcu/urcu/rculfhash.h
> > ===================================================================
> > --- userspace-rcu.orig/urcu/rculfhash.h
> > +++ userspace-rcu/urcu/rculfhash.h
> > @@ -381,6 +381,20 @@ int cds_lfht_replace(struct cds_lfht *ht
> >  int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node);
> > 
> >  /*
> > + * cds_lfht_is_node_deleted - query if a node is removed from hash table.
> > + *
> > + * Return non-zero if the node is deleted from the hash table, 0
> > + * otherwise.
> > + * Node can be looked up with cds_lfht_lookup and cds_lfht_next,
> > + * followed by use of cds_lfht_iter_get_node.
> > + * RCU read-side lock must be held between lookup and call to this
> > + * function.
> > + * Call with rcu_read_lock held.
> > + * Threads calling this API need to be registered RCU read-side threads.
> > + */
> > +int cds_lfht_is_node_deleted(struct cds_lfht_node *node);
> > +
> > +/*
> >   * cds_lfht_resize - Force a hash table resize
> >   * @ht: the hash table.
> >   * @new_size: update to this hash table size.
> > 
> > -- 
> > Mathieu Desnoyers
> > Operating System Efficiency R&D Consultant
> > EfficiOS Inc.
> > http://www.efficios.com
> > 
> > _______________________________________________
> > rp mailing list
> > rp at svcs.cs.pdx.edu
> > http://svcs.cs.pdx.edu/mailman/listinfo/rp
> > 
> 
> 
> _______________________________________________
> lttng-dev mailing list
> lttng-dev at lists.lttng.org
> http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

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