[ltt-dev] RCU lock-free hash table updates

[Mathieu Desnoyers]

Hi everyone,

A little update following my presentation at Linux Plumbers Conference
2011 on the RCU lock-free hash table in development within the
userspace-rcu git tree (presentation slides available at
http://www.efficios.com/lpc2011-urcu). I created a new branch
(urcu/ht-shrink-help) that lets the lookup, add and remove operations
help the expand and shrink algorithms, thus getting closer to a
lock-free semantic that takes interaction between resize and updates
into account.

I also implemented some simplifications to the data structures (proposed
by Josh), where the top-level log(n) table is now allocated only once at
hash table creation, and only its size is updated, rather than using a
needlessly complex reallocation/delayed free scheme.

Finally, I managed to make the response of resize to drastic changes to
the flow of updates (e.g. an ongoing shrink, and suddenly all threads
start adding nodes instead of removing them) much better by checking if
the resize target changes between each order-of-two step of the resize
operation, cancelling the following shrink steps if they are not needed
anymore (same for expand cancellation). With the combination of the
"help" scheme (add, removal and lookups helping the resize) and this
opportunistic cancellation, the hash table supports being shrunk a size
1 bucket, followed by a storm of insertions coming from 8 cores, without
any problem. I'm currently stress-testing this code using an external
SIGUSR1 signal that changes the behavior between add/remove/random in
loops for hours/days to ensure it is solid.

The code is available at:

http://git.lttng.org/?p=userspace-rcu.git;a=tree;h=refs/heads/urcu/ht-shrink-help;hb=urcu/ht-shrink-help

files:
rculfhash.c
urcu/rculfhash.h
tests/test_urcu_hash.c (-A option to activate automatic resize)

Comments are welcome,

Best regards,

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com