Cleanup: Re-organise source dir Re-organise the sources, add a top level "src" and "include" dir and move relevant files. Disable autotools automated includes and define them manually. This fixes problems with collision of header names with system headers. Include the autoconf config.h in the default includes and remove it where it's explicitely included. Remove _GNU_SOURCE defines since it's detected at configure for platforms that requires it and added to the config.h. Signed-off-by: Michael Jeanson <mjeanson@efficios.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
rculfhash: Documentation: clarify need for grace period before "re-using" Grace period must be waited for in case a node removed from the hash table is re-used, similarly to the reclaim use-case. Reported-by: Luke K D'Alessandro <ldalessa@indiana.edu> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Fix undefined NULL pointer arithmetic Clang 3.3 with -O2 optimisations is especially picky about arithmetic on NULL pointers. This undefined behavior is turned into optimized out NULL checks by clang 3.3. Fix the undefined behavior by checking against the pointer directly, without going back and forth around NULL with pointer arithmetic. Reported-by: Zifei Tong <soariez@gmail.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
rculfhash: document implied memory barriers We choose to provide full memory barriers before and after successful hash table update operations. Eventually, new API with weaker semantic can be added, but let's make the basic API as fool-proof as possible. Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Reviewed-by: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
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: use node instead of iter argument for deletion Using a node instead of an iterator as argument for deletion allows passing a node pointer (that would have been looked up from another data structure, thus not using the iterator) as argument for deletion. Deletion still returns -ENOENT if asked to delete the NULL node. This simplifies the caller usage. Suggested-by: Lai Jiangshan <laijs@cn.fujitsu.com> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
rculfhash: number of logically removed nodes should not appear in API This is an implementation artefact that should not appear in the API. So only count the non-removed nodes. Print a debug message showing the number of logically removed nodes instead within the count nodes function. Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
rculfhash: Relax atomicity guarantees required by removal operation The atomicity guarantees for the removal operation do not need to be as strict as a cmpxchg. Use a uatomic_set followed by a xchg on a newly introduced "REMOVAL_OWNER_FLAG" to perform removal. Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>