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

[Junchang Wang]

Hi Jonathan,

Thanks for letting me know. The patch isn't in a hurry, so it's good for me
to discuss this patch after Mathieu returns.


Thanks,
--Junchang

On Wed, Jul 10, 2019 at 11:14 PM Jonathan Rajotte-Julien <
jonathan.rajotte-julien at efficios.com> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.lttng.org/pipermail/lttng-dev/attachments/20190711/87ea782d/attachment.html>