urcu:urcu/ht-shrink

Last commit made on 2012-02-22
Get this branch:
git clone -b urcu/ht-shrink https://git.launchpad.net/urcu

Branch merges

Branch information

Name:
urcu/ht-shrink
Repository:
lp:urcu

Recent commits

df55172... by Mathieu Desnoyers on 2012-02-22

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>

f8fc437... by Mathieu Desnoyers on 2012-01-09

Merge branch 'master' into urcu/ht-shrink

657e7f8... by David Goulet on 2012-01-09

Fix autoconf futex check

The check was always returning true.

Signed-off-by: David Goulet <email address hidden>
Signed-off-by: Mathieu Desnoyers <email address hidden>

ec5e2d1... by Mathieu Desnoyers on 2012-01-07

configure.ac: Use AC_LANG_SOURCE for if else macros

Ref. http://www.flameeyes.eu/autotools-mythbuster/forwardporting/autoconf.html
"Noteworthy changes in autoconf version 2.66 through 2.68"

Signed-off-by: Mathieu Desnoyers <email address hidden>

a641253... by Alex Mont on 2012-01-06

Refresh autoconf files

Use portable shell macros wherever possible.
All functionality should remain the same.

Signed-off-by: Alexandre Montplaisir <email address hidden>
Signed-off-by: Mathieu Desnoyers <email address hidden>

5b5c598... by Alex Mont on 2012-01-06

Update gitignore

Signed-off-by: Alexandre Montplaisir <email address hidden>
Signed-off-by: Mathieu Desnoyers <email address hidden>

79d5479... by Mathieu Desnoyers on 2011-12-29

Merge branch 'master' into urcu/ht-shrink

c9582f1... by Mathieu Desnoyers on 2011-12-29

rculfhash: add comment about hash seed randomness within test program

Signed-off-by: Mathieu Desnoyers <email address hidden>

d68d00f... by Gerlando Falauto <email address hidden> on 2011-12-21

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>

91a75cc... by Mathieu Desnoyers on 2011-12-21

rculfhash: remove an invocation of bit_reverse_ulong() when adding

Suggested-by: Lai Jiangshan <email address hidden>
Signed-off-by: Mathieu Desnoyers <email address hidden>