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 <email address hidden>
Acked-by: Paul E. McKenney <email address hidden>
CC: Lai Jiangshan <email address hidden>
CC: Stephen Hemminger <email address hidden>
readme: state correct GCC dependency for ARM
If you are trying to compile liburcu for ARM and get errors like:
/usr/local/include/urcu/uatomic/generic.h:180: undefined reference to
`__sync_add_and_fetch_4'
usr/local/lib/liburcu-common.so: undefined reference to
`__sync_lock_test_and_set_4'
/usr/local/lib/liburcu.so: undefined reference to
`__sync_or_and_fetch_4'
please upgrade your GCC to 4.4.
Signed-off-by: Mathieu Desnoyers <email address hidden>
