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

[Mathieu Desnoyers]

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.

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