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

[Paul E. McKenney]

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>

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