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

[Mathieu Desnoyers]

----- On Jul 29, 2019, at 9:35 AM, Junchang Wang junchangwang at gmail.com 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.

One point worth mentioning: the rculfhash data structure (rcu lock-free hash
table) already implements such list internally. You might want to have a look
at it, and perhaps just lift out its implementation into a separate .c file
and header file so we can expose its implementation publicly ?

Items are linked through the struct cds_lfht_node next field.

The struct cds_lfht_iter is used as a iterator on the list.

struct cds_lfht tbl_oder, tbl_chunk and tbl_mmap contain the
linked lists heads for each memory allocation scheme.

I'm wondering why you need to re-implement a hash table though. What is
missing from rculfhash to suit your needs ?

Thanks,

Mathieu


> 
> 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 we made the following two major improvements:
> (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 variable of 8 bytes (typically sizeof(long)) for each node.
> 
> In the past two weeks, I found some bugs in the first version of the
> list in building a lock-free hash table on top it. So this is the second
> version which fixes the known issues. Please review this version, if
> possible. The major changes are as follows. Sorry for the inconvenience.
> Any suggestions and comments are warmly welcome.
> 
> v1 -> v2:
>  - Functions insert(), delete(), and find() return 0 in success, and
>    return -Exxx otherwise.
>  - Fix a bug in function is_removed().
> 
> Cheers,
> --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/rculflist/Makefile                    |  24 ++
> .../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     | 101 ++++++++
> doc/examples/rculflist/cds_lflist_find_rcu.c       |  96 +++++++
> doc/examples/rculflist/cds_lflist_insert_rcu.c     |  69 +++++
> include/Makefile.am                                |   1 +
> include/urcu/cds.h                                 |   1 +
> include/urcu/rculflist.h                           | 284 +++++++++++++++++++++
> 11 files changed, 646 insertions(+)
> create mode 100644 doc/examples/rculflist/Makefile
> 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
> 
> --
> 1.8.3.1
> 
> _______________________________________________
> lttng-dev mailing list
> lttng-dev at lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com