Hi Mathieu and the list, I'm recently using userspace-rcu to build lock-free data structures. Thanks for sharing this excellent project!
In building a hash table, I am looking for an ordered singly linked list that is lock-free. It seems such a list is missing in userspace-rcu. I discussed this with Paul in the mailing list of perfbook, and he kindly suggested me to submit my implementation to userspace-rcu. So here is the RFC. Any comments and suggestions are warmly welcome. This singly linked list is based on the following research paper: - Maged M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, ACM Press, (2002), 73-82. And this implementation has the following unique features: (1) Insert, Delete, and Find operations are protected by RCU read_lock, such that the existence guarantees are provided by the RCU mechanism, and that no special memory management schemes (e.g., hazard pointers) is required anymore. (2) The use of the RCU mechanism can naturally prevent the ABA problem, such that no flag field is required in this implementation. Hence, we save a long integer (typically 8 bytes) for each node. This is my first patch to this mailing list, so please let me know if I messed anything up. Any comments and suggestions are warmly welcome. Thanks, --Junchang Junchang Wang (4): userspace-rcu: Add lock-free singly linked list rculflist userspace-rcu: Add sample code of rculflist userspace-rcu: Update Makefile.am to include rculflist into the project userspace-rcu: Add a brief description of rculflist in cds-api.md doc/cds-api.md | 7 + doc/examples/Makefile.am | 13 +- .../rculflist/Makefile.cds_lflist_delete_rcu | 21 ++ .../rculflist/Makefile.cds_lflist_find_rcu | 21 ++ .../rculflist/Makefile.cds_lflist_insert_rcu | 21 ++ doc/examples/rculflist/cds_lflist_delete_rcu.c | 100 ++++++++ doc/examples/rculflist/cds_lflist_find_rcu.c | 96 +++++++ doc/examples/rculflist/cds_lflist_insert_rcu.c | 66 +++++ include/Makefile.am | 1 + include/urcu/cds.h | 1 + include/urcu/rculflist.h | 279 +++++++++++++++++++++ 11 files changed, 625 insertions(+), 1 deletion(-) create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_delete_rcu create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_find_rcu create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_insert_rcu create mode 100644 doc/examples/rculflist/cds_lflist_delete_rcu.c create mode 100644 doc/examples/rculflist/cds_lflist_find_rcu.c create mode 100644 doc/examples/rculflist/cds_lflist_insert_rcu.c create mode 100644 include/urcu/rculflist.h -- 2.7.4 _______________________________________________ lttng-dev mailing list lttng-dev@lists.lttng.org https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev