Message ID | 1562729290-6437-1-git-send-email-junchangwang@gmail.com |
---|---|
Headers |
From: junchangwang at gmail.com (Junchang Wang) Date: Wed, 10 Jul 2019 11:28:06 +0800 Subject: [lttng-dev] [RFC 0/4] userspace-rcu: Add lock-free, ordered singly linked list rculflist Message-ID: <1562729290-6437-1-git-send-email-junchangwang@gmail.com> |
Series |
userspace-rcu: Add lock-free, ordered singly linked list rculflist
|
|
Message
Junchang Wang
July 10, 2019, 3:28 a.m. UTC
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
Comments
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
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>