RCU lock-free hash table: implement cds_lfht_is_node_deleted() urcu/ht-shrink
authorMathieu Desnoyers <mathieu.desnoyers@efficios.com>
Wed, 22 Feb 2012 00:06:52 +0000 (19:06 -0500)
committerMathieu Desnoyers <mathieu.desnoyers@efficios.com>
Wed, 22 Feb 2012 00:06:52 +0000 (19:06 -0500)
commitdf55172add00a2b1b33b6c09f1f83f858d452f89
tree6237bcbf9eef48a4cd7734014990d86f711f257a
parentf8fc437722856fefd5d415405d5ce8d79e8b6e96
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 <mathieu.desnoyers@efficios.com>
Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
CC: Lai Jiangshan <laijs@cn.fujitsu.com>
CC: Stephen Hemminger <shemminger@vyatta.com>
rculfhash.c
urcu/rculfhash.h
This page took 0.025492 seconds and 4 git commands to generate.