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 _______________________________________________ ltt-dev mailing list [email protected] http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
