From df55172add00a2b1b33b6c09f1f83f858d452f89 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 21 Feb 2012 19:06:52 -0500 Subject: [PATCH] RCU lock-free hash table: implement cds_lfht_is_node_deleted() 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 Acked-by: Paul E. McKenney CC: Lai Jiangshan CC: Stephen Hemminger --- rculfhash.c | 5 +++++ urcu/rculfhash.h | 14 ++++++++++++++ 2 files changed, 19 insertions(+) diff --git a/rculfhash.c b/rculfhash.c index b114e0c..9436605 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -1553,6 +1553,11 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node) 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) { diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h index 96dc5a0..8baf31d 100644 --- a/urcu/rculfhash.h +++ b/urcu/rculfhash.h @@ -380,6 +380,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. -- 2.34.1