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

[Jonathan Rajotte-Julien]

Hi Junchang,

Thanks for contributing to URCU.

I just wanted to let you know that Mathieu is currently on vacation for ~2 weeks
so do not expect much feedback until his return.

Cheers

On Wed, Jul 10, 2019 at 11:28:06AM +0800, Junchang Wang wrote:
> 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 at lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

-- 
Jonathan Rajotte-Julien
EfficiOS