[lttng-dev] [RFC 0/4] userspace-rcu: Add lock-free, ordered singly linked list rculflist

[Junchang Wang]

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