userspace-rcu: Add lock-free singly linked list rculflist
A message that is not in the archive (sent off-list or not yet received): [email protected]
RFC 1/4 userspace-rcu: Add lock-free singly linked list rculflist
--- include/urcu/rculflist.h | 279 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 279 insertions(+) create mode 100644 include/urcu/rculflist.h
include/urcu/rculflist.h new file +279 -0
@@ -0,0 +1,279 @@ +/* +* rculflist.c +* +* Userspace RCU library - Lock-Free ordered, singly-linked list +* +* Copyright (c) 2019 Junchang Wang +* Copyright (c) 2019 Paul E. McKenney +* +* This program is free software; you can redistribute it and/or modify +* it under the terms of the GNU General Public License as published by +* the Free Software Foundation; either version 2 of the License, or +* (at your option) any later version. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, you can access it online at +* http://www.gnu.org/licenses/gpl-2.0.html. +* +* +* 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. +* +* Some specificities of this Lock-free linked list implementation: +* - The original algorithm prevents the ABA problem by adding a tag field +* in each hash-table node, whereas this implementation addresses this +* issue by using the RCU mechanism. +*/ + +#ifndef _URCU_RCULFLIST_H +#define _URCU_RCULFLIST_H + +#ifdef __cplusplus +extern "C" { +#endif + +#include <urcu/uatomic.h> +#include <urcu-pointer.h> +#include <urcu-call-rcu.h> + +#define ACCESS_ONCE (x) (*(volatile typeof(x) *)&(x)) +#define READ_ONCE (x) \ + ({ typeof(x) ___x = ACCESS_ONCE(x); ___x; }) +#define WRITE_ONCE (x, val) ({ ACCESS_ONCE(x) = (val); }) + +/* +* lflist uses the least-significant 1 bit to indicate if a node has been +* logically removed. +*/ +#define REMOVED_FLAG (1UL << 0) +#define FLAGS_MASK ((1UL << 1) - 1) + +/* +* Define the structure of list node and related functions. +*/ +struct cds_lflist_node { +struct rcu_head rcu_head; +unsigned long key; +struct cds_lflist_node *next;/* (pointer | xxx_FLAG) */ +} __attribute__((aligned (8 ))); + +static inline +unsigned long get_flag (struct cds_lflist_node *ptr) +{ +return (unsigned long )((uintptr_t )ptr &FLAGS_MASK ); +} + +static inline +struct cds_lflist_node *get_ptr (struct cds_lflist_node *ptr) +{ +return (struct cds_lflist_node *)((uintptr_t )ptr & ~FLAGS_MASK ); +} + +static inline +struct cds_lflist_node *set_flag (struct cds_lflist_node *ptr, +unsigned long mask) +{ +return (struct cds_lflist_node *) + (((uintptr_t )ptr & ~FLAGS_MASK ) | mask); +} + +static inline +int is_removed (struct cds_lflist_node *ptr) +{ +return (uintptr_t )ptr &REMOVED_FLAG ; +} + +void cds_lflist_node_init_rcu (struct cds_lflist_node *node) +{ + node->next =NULL ; + node->key =0UL ; +} + +void cds_lflist_node_set_key (struct cds_lflist_node *node,unsigned long key) +{ + node->key = key; +} + +/* +* Struct cds_lflist_snapshot and its helper functions. +* Before invoking cds_lflist_find_rcu, the caller must first allocates +* an instance of struct cds_lflist_snapshot and passs the pointer +* to cds_lflist_find_rcu. By its completion, cds_lflist_find_rcu +* guarantees that (1) cur points to the node that contains the +* lowest key value that is greater than or equal to the input key +* and (2) prev is the predecessor pointer of cur. +*/ +struct cds_lflist_snapshot { +struct cds_lflist_node **prev; +struct cds_lflist_node *cur; +struct cds_lflist_node *next; +}; + +static inline +void set_snapshot (struct cds_lflist_snapshot *ssp,struct cds_lflist_node **prev, +struct cds_lflist_node *cur,struct cds_lflist_node *next) +{ + ssp->prev = prev; + ssp->cur =get_ptr (cur); + ssp->next =get_ptr (next); +} + +/* +* Define the struct of lock-free list and its helper functions. +*/ +struct cds_lflist_rcu { +struct cds_lflist_node *head; +void (*delete_node)(struct cds_lflist_node *); +}; + +int cds_lflist_init_rcu (struct cds_lflist_rcu *list, +void (*node_free)(struct cds_lflist_node *)) +{ + list->head =NULL ; + list->delete_node = node_free; +return 0 ; +} + +/* +* Function cds_lflist_find_rcu() returns true(1) if a node with a matching key +* was found in the list, or returns false(0) otherwise. +* No matter if find_rcu() returns 1 or 0, by its completion, it guarantees +* that *ssp* points to the snapshot of a segment of the list. Within the +* snapshot, field *cur* points to the node that contains the lowest key value +* greater than or equal to the input key, and *prev* is the predecessor +* pointer of *cur*. Note that this function guarantees that the REMOVED_FLAG +* of the *cur* node has not been set. +*/ +int cds_lflist_find_rcu (struct cds_lflist_rcu *list,unsigned long key, +struct cds_lflist_snapshot *ssp) +{ +/* Local variables to record the snapshot */ +struct cds_lflist_node **prev, *cur, *next; + +struct cds_lflist_node *cur_ptr; +struct cds_lflist_node *next_ptr; +unsigned long cur_key; + +try_again: + prev = &list->head; + cur =READ_ONCE (*prev); + cur_ptr =get_ptr (cur); + +for (;;) { +if (cur_ptr ==NULL ) { +/* Have reached the end of the list. */ +set_snapshot (ssp, prev,NULL ,NULL ); +return 0 ; + } + cur_key =READ_ONCE (cur_ptr->key); + next =READ_ONCE (cur_ptr->next); + next_ptr =get_ptr (next); + +/* If a new node has been added before cur, go to retry. */ +if (READ_ONCE (*prev) != cur_ptr) + goto try_again; +if (!is_removed (next)) { +if (cur_key >= key) { +/* The key value of node cur_ptr is equal to +* or larger than the input key value. */ +set_snapshot (ssp, prev, cur, next); +return cur_key == key; + } + prev = &cur_ptr->next; + }else { +/* If the node cur_ptr has been logically deleted, +* try to physically delete it. */ +if (uatomic_cmpxchg (prev, cur_ptr, next_ptr) == cur_ptr){ +/* Some applications (e.g., hashtorture) manages +* (destroy) nodes by themselves. For these cases, +* list->delete_node is initialized to NULL. */ +if (list->delete_node) + list->delete_node (cur_ptr); + }else { +/* One of other threads has physically delete +* the node. Retry. */ + goto try_again; + } + } + cur = next; + cur_ptr =get_ptr (cur); + } +} + +/* +* Function cds_lflist_insert_rcu returns 0 if a node with a matching key +* is found in the list. Otherwise, this function inserts +* the new node before the node ss.cur and returns 1. +*/ +int cds_lflist_insert_rcu (struct cds_lflist_rcu *list, +struct cds_lflist_node *node) +{ +unsigned long key = node->key; +struct cds_lflist_snapshot ss; + +for (;;) { +if (cds_lflist_find_rcu (list, key, &ss)) +return 0 ; + node->next =set_flag (ss.cur,0UL ); +if (uatomic_cmpxchg (ss.prev,set_flag (ss.cur,0UL ), +set_flag (node,0UL )) ==set_flag (ss.cur,0UL )) { +return 1 ; + } + } +} + +/* +* Function cds_lflist_delete_rcu returns 0 if the key is not found in the list. +* Otherwise, the key value of the node pointed to by ss.cur must be equal to +* the input key. The function deletes the node by (1) marking the node pointed +* to by ss.cur as deleted, and (2) swinging prev->next to point to next. +*/ +int cds_lflist_delete_rcu (struct cds_lflist_rcu *list,unsigned long key) +{ +/* Local variables to record the snapshot */ +struct cds_lflist_node *cur, *next; +struct cds_lflist_snapshot ss; + +for (;;) { +if (!cds_lflist_find_rcu (list, key, &ss)) +return 0 ; + cur = ss.cur; + next = ss.next; + +/* The node to be deleted is pointed to by ss.cur. +* We first logically deleted it by setting its REMOVED_FLAG. +*/ +if (uatomic_cmpxchg (&cur->next,set_flag (next,0UL ), +set_flag (next,1UL )) !=set_flag (next,0UL )) +continue ; +/* If node pointed to by ss.cur has been logically deleted, +* try to physically delete it. +*/ +if (uatomic_cmpxchg (ss.prev,set_flag (cur,0UL ), +set_flag (next,0UL )) ==set_flag (cur,0UL )) { +/* Some applications (e.g., hashtorture) manages +* (destroy) nodes by themselves. For these cases, +* list->delete_node is initialized to NULL. */ +if (list->delete_node) + list->delete_node (cur); + }else { +/* Physical deletion failed. Retry. */ +cds_lflist_find_rcu (list, key, &ss); + } +return 1 ; + } +} + +#ifdef __cplusplus +} +#endif + +#endif /*_URCU_RCULFLIST_H */
Signature · 1 line
2.7.4
RFC 2/4 userspace-rcu: Add sample code of rculflist
In reply to a message not in the archive---
For the three Makefiles, I just copied, pasted, and updated slightly, so I didn't change the copyright information.
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 ++++++++++++++ 7 files changed, 337 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
doc/examples/Makefile.am +12 -1
@@ -111,13 +111,24 @@ dist_doc_examples_rculfhash_DATA = \ rculfhash/cds_lfht_lookup.c \ rculfhash/cds_lfht_for_each_entry_duplicate.c +doc_examples_rculflistdir = ${doc_examplesdir}/rculflist + +dist_doc_examples_rculflist_DATA = \ + rculflist/Makefile \ + rculflist/Makefile.cds_lflist_insert_rcu \ + rculflist/Makefile.cds_lflist_delete_rcu \ + rculflist/Makefile.cds_lflist_find_rcu \ + rculflist/cds_lflist_insert_rcu.c \ + rculflist/cds_lflist_delete_rcu.c \ + rculflist/cds_lflist_find_rcu.c + if NO_SHARED # Don't build examples if shared libraries support was explicitly # disabled. else SUBDIRS_PROXY = hlist list urcu-flavors wfcqueue rculfqueue \ - wfstack lfstack rculfhash + wfstack lfstack rculfhash rculflist # Copies are for VPATH build support. all-local:
doc/examples/rculflist/Makefile.cds_lflist_delete_rcu new file +21 -0
@@ -0,0 +1,21 @@ +# Copyright (C) 2013 Mathieu Desnoyers <[email protected]> +# +# THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED +# OR IMPLIED. ANY USE IS AT YOUR OWN RISK. +# +# Permission is hereby granted to use or copy this program for any +# purpose, provided the above notices are retained on all copies. +# Permission to modify the code and to distribute modified code is +# granted, provided the above notices are retained, and a notice that +# the code was modified is included with the above copyright notice. +# +# This makefile is purposefully kept simple to support GNU and BSD make. + +EXAMPLE_NAME = cds_lflist_delete_rcu + +SOURCES = $(EXAMPLE_NAME).c +OBJECTS = $(EXAMPLE_NAME).o +BINARY = $(EXAMPLE_NAME) +LIBS = -lurcu + +include ../Makefile.examples.template
doc/examples/rculflist/Makefile.cds_lflist_find_rcu new file +21 -0
@@ -0,0 +1,21 @@ +# Copyright (C) 2013 Mathieu Desnoyers <[email protected]> +# +# THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED +# OR IMPLIED. ANY USE IS AT YOUR OWN RISK. +# +# Permission is hereby granted to use or copy this program for any +# purpose, provided the above notices are retained on all copies. +# Permission to modify the code and to distribute modified code is +# granted, provided the above notices are retained, and a notice that +# the code was modified is included with the above copyright notice. +# +# This makefile is purposefully kept simple to support GNU and BSD make. + +EXAMPLE_NAME = cds_lflist_find_rcu + +SOURCES = $(EXAMPLE_NAME).c +OBJECTS = $(EXAMPLE_NAME).o +BINARY = $(EXAMPLE_NAME) +LIBS = -lurcu + +include ../Makefile.examples.template
doc/examples/rculflist/Makefile.cds_lflist_insert_rcu new file +21 -0
@@ -0,0 +1,21 @@ +# Copyright (C) 2013 Mathieu Desnoyers <[email protected]> +# +# THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED +# OR IMPLIED. ANY USE IS AT YOUR OWN RISK. +# +# Permission is hereby granted to use or copy this program for any +# purpose, provided the above notices are retained on all copies. +# Permission to modify the code and to distribute modified code is +# granted, provided the above notices are retained, and a notice that +# the code was modified is included with the above copyright notice. +# +# This makefile is purposefully kept simple to support GNU and BSD make. + +EXAMPLE_NAME = cds_lflist_insert_rcu + +SOURCES = $(EXAMPLE_NAME).c +OBJECTS = $(EXAMPLE_NAME).o +BINARY = $(EXAMPLE_NAME) +LIBS = -lurcu + +include ../Makefile.examples.template
doc/examples/rculflist/cds_lflist_delete_rcu.c new file +100 -0
100 lines not on this page · raw message
doc/examples/rculflist/cds_lflist_find_rcu.c new file +96 -0
96 lines not on this page · raw message
doc/examples/rculflist/cds_lflist_insert_rcu.c new file +66 -0
66 lines not on this page · raw message
Signature · 1 line
2.7.4
RFC 3/4 userspace-rcu: Update Makefile.am to include rculflist into the project
In reply to a message not in the archive--- include/Makefile.am | 1 + include/urcu/cds.h | 1 + 2 files changed, 2 insertions(+)
include/Makefile.am +1 -0
@@ -2,6 +2,7 @@ nobase_dist_include_HEADERS = urcu/compiler.h urcu/hlist.h urcu/list.h \ urcu/rculist.h urcu/rcuhlist.h urcu/system.h urcu/futex.h \ urcu/uatomic/generic.h urcu/arch/generic.h urcu/wfstack.h \ urcu/wfqueue.h urcu/rculfstack.h urcu/rculfqueue.h \ + urcu/rculflist.h \ urcu/ref.h urcu/cds.h urcu/urcu_ref.h urcu/urcu-futex.h \ urcu/uatomic_arch.h urcu/rculfhash.h urcu/wfcqueue.h \ urcu/lfstack.h urcu/syscall-compat.h \
include/urcu/cds.h +1 -0
@@ -30,6 +30,7 @@#include <urcu/rculfqueue.h> #include <urcu/rculfstack.h> #include <urcu/rculfhash.h> +#include <urcu/rculflist.h> #include <urcu/wfqueue.h> #include <urcu/wfcqueue.h> #include <urcu/wfstack.h>
Signature · 1 line
2.7.4
RFC 4/4 userspace-rcu: Add a brief description of rculflist in cds-api.md
In reply to a message not in the archive--- doc/cds-api.md | 7 +++++++ 1 file changed, 7 insertions(+)
doc/cds-api.md +7 -0
@@ -82,3 +82,10 @@ are supported. Provides "uniquify add" and "replace add" operations, along with associated read-side traversal uniqueness guarantees. Automatic hash table resize based on number of elements is supported. See the API for more details. + + +### `urcu/rculflist.h` + +Ordered singly linked list with lock-free insert, delete and find operations. +This list relies on RCU for existence guarantees and ABA-problem prevention. +It is useful for implementing hash tables.
Signature · 1 line
2.7.4
Re: [RFC 0/4] userspace-rcu: Add lock-free, ordered singly linked list rculflist
In reply to a message not in the archiveHi 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
Quoted 66 lines · 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 RCUread_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,
--JunchangJunchang 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.mddoc/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.hSignature · 6 lines
2.7.4 _______________________________________________ lttng-dev mailing list [email protected] https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Signature · 2 lines
Jonathan Rajotte-Julien EfficiOS
A message that is not in the archive (sent off-list or not yet received): 20190710151410.GB3812@joraj-alpa
Re: [RFC 0/4] userspace-rcu: Add lock-free, ordered singly linked list rculflist
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
Quoted 77 lines · 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
Quoted 3 lines · Junchang Wang
Hi Mathieu and the list,
I'm recently using userspace-rcu to build lock-free data structures.
Thanks for
Quoted 14 lines
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.Quoted 3 lines
And this implementation has the following unique features:
(1) Insert, Delete, and Find operations are protected by RCUread_lock, such that the existence guarantees are provided by the RCUmechanism,
Quoted 1 line
and that no special memory management schemes (e.g., hazard
pointers)
Quoted 18 lines
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,
--JunchangJunchang 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.mdQuoted 11 lines
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+++++++++++++++++++++
Quoted 12 lines
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
Quoted 9 lines
Quoted 4 lines
_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev--
Jonathan Rajotte-Julien
EfficiOS
_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev