userspace-rcu: Add lock-free singly linked list rculflist
PATCH v2 1/4 userspace-rcu: Add lock-free singly linked list rculflist
In reply to a message not in the archive--- include/urcu/rculflist.h | 284 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 284 insertions(+) create mode 100644 include/urcu/rculflist.h
include/urcu/rculflist.h new file +284 -0
@@ -0,0 +1,284 @@ +/* +* rculflist.c +* +* Userspace RCU library - Lock-Free and 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 <errno.h> +#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 reserves the least-significant 2 bits to record control information. +* Currently, it only uses the least-significant 1 bit to indicate if a node +* has been logically removed. +*/ +#define RESERVED_BITS_LEN (2) +#define REMOVED_FLAG (1UL << 0) +#define FLAGS_MASK ((1UL << RESERVED_BITS_LEN) - 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 (CAA_CACHE_LINE_SIZE ))); + +static +unsigned long get_flag (struct cds_lflist_node *ptr) +{ +return (unsigned long )((uintptr_t )ptr &FLAGS_MASK ); +} + +static +struct cds_lflist_node *get_ptr (struct cds_lflist_node *ptr) +{ +return (struct cds_lflist_node *)((uintptr_t )ptr & ~FLAGS_MASK ); +} + +static +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 +int is_removed (struct cds_lflist_node *ptr) +{ +return ((uintptr_t )ptr &FLAGS_MASK ) !=0 ; +} + +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 success(0) if the node with +* a matching key was found in the list, or returns failure(-Exxx) otherwise. +* No matter if find_rcu() returns success or failure, 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*. +*/ +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 =rcu_dereference (*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 -ENOENT ; + } + cur_key = cur_ptr->key; + next = 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_ptr, next); +if (cur_key == key) +return 0 ; +else +return -ENOENT ; + } + 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 =rcu_dereference (next); + cur_ptr =get_ptr (cur); + } +} + +/* +* Function cds_lflist_insert_rcu returns -EINVAL 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 0. +*/ +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 -EINVAL ; +rcu_assign_pointer (node->next,set_flag (ss.cur,get_flag (node->next))); +if (uatomic_cmpxchg (ss.prev,set_flag (ss.cur,0UL ), +set_flag (node,0UL )) ==set_flag (ss.cur,0UL )) { +return 0 ; + } + } +} + +/* +* Function cds_lflist_delete_rcu returns -EINVAL if the key is not found. +* 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, +struct cds_lflist_snapshot *ss) +{ +/* Local variables to record the snapshot */ +struct cds_lflist_node *cur, *next; + +for (;;) { +if (cds_lflist_find_rcu (list, key, ss)) +return -EINVAL ; + cur =READ_ONCE (ss->cur); + next =READ_ONCE (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,REMOVED_FLAG )) !=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 0 ; + } +} + +#ifdef __cplusplus +} +#endif + +#endif /*_URCU_RCULFLIST_H */
Signature · 1 line
1.8.3.1
PATCH v2 2/4 userspace-rcu: Add sample code of rculflist
In reply to a message not in the archive--- 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 ++++++++++++++ 7 files changed, 353 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
doc/examples/rculflist/Makefile new file +24 -0
@@ -0,0 +1,24 @@ +# Copyright (C) 2013 Junchang Wang <[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. + +all: + $(AM_V_at)$(MAKE) -f Makefile.cds_lflist_insert_rcu + $(AM_V_at)$(MAKE) -f Makefile.cds_lflist_delete_rcu + $(AM_V_at)$(MAKE) -f Makefile.cds_lflist_find_rcu + +.PHONY: clean +clean: + $(AM_V_at)$(MAKE) -f Makefile.cds_lflist_insert_rcu clean + $(AM_V_at)$(MAKE) -f Makefile.cds_lflist_delete_rcu clean + $(AM_V_at)$(MAKE) -f Makefile.cds_lflist_find_rcu clean +
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 +101 -0
101 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 +69 -0
69 lines not on this page · raw message
Signature · 1 line
1.8.3.1
PATCH v2 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
1.8.3.1
PATCH v2 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
1.8.3.1
Quoted 1 line · ----- On Jul 29, 2019, at 9:35 AM, Junchang Wang [email protected] wrote:
Signed-off-by Junchang Wang <[email protected]>
Hi Junchang,
Thanks for submitting this! I've been on vacation for the past two weeks, hence the delay in reply.
A few points:
I think we should move the implementation of find/insert/delete to a .c file (rather than headers) because at least two of those functions are larger than 10 lines, and therefore don't fall under the "trivial" category.
I also notice that the implementation you propose is GPLv2+. Would you be willing to re-license your contribution under LGPLv2.1 or LGPLv2.1+ ? This is the license we use for the entire Userspace RCU library. liburcu is meant to be used by non-GPL/LGPL programs as well.
I'll wait until I get an answer from you on those points before digging further into the code.
Thanks,
Mathieu
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Re: [PATCH v2 0/4] userspace-rcu: Add lock-free, ordered singly linked list
In reply to a message not in the archiveQuoted 10 lines · ----- On Jul 29, 2019, at 9:35 AM, Junchang Wang [email protected] 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
Quoted 65 lines
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 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 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:
- Functionsinsert(),delete(), andfind()return 0 in success, and return -Exxx otherwise.
- Fix a bug in functionis_removed().Cheers,
--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/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 100644doc/examples/rculflist/cds_lflist_delete_rcu.ccreate mode 100644doc/examples/rculflist/cds_lflist_find_rcu.ccreate mode 100644doc/examples/rculflist/cds_lflist_insert_rcu.ccreate mode 100644include/urcu/rculflist.h--
1.8.3.1_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Re: [PATCH v2 0/4] userspace-rcu: Add lock-free, ordered singly linked list
In reply to a message not in the archiveQuoted 19 lines · Mathieu Desnoyers
Quoted 10 lines · ----- On Jul 29, 2019, at 9:35 AM, Junchang Wang [email protected] 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 ?
Quoted 6 lines
Items are linked through the struct
cds_lfht_nodenext field.The struct
cds_lfht_iteris used as a iterator on the list.struct
cds_lfhttbl_oder,tbl_chunkandtbl_mmapcontain the linked lists heads for each memory allocation scheme.
Hi Mathieu,
Thanks for the note. I checked rculfhash today, and the list implementation within rculfhash is indeed quite similar to the one I'm working on. I will check to see if we can merge the two versions and provide an independent rculflist.
Quoted 4 lines
I'm wondering why you need to re-implement a hash table though. What is missing from rculfhash to suit your needs ?
The major reason is that I want a hash table that can change its hash function on-the-fly. Split-ordered list is not adequate because it can only increase/decrease the number of buckets. Besides, I doubt the reverse operation is always efficient on platforms where hardware cannot help reverse bit strings. Hence I'm working on the new hash table algorithm, which, of course, is built on top of the linked list we are working on :-).
Thanks,
--Junchang
Quoted 75 lines
Thanks,
Mathieu
Quoted 58 lines
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 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 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:
- Functionsinsert(),delete(), andfind()return 0 in success, and return -Exxx otherwise.
- Fix a bug in functionis_removed().Cheers,
--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/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 100644doc/examples/rculflist/cds_lflist_delete_rcu.ccreate mode 100644doc/examples/rculflist/cds_lflist_find_rcu.ccreate mode 100644doc/examples/rculflist/cds_lflist_insert_rcu.ccreate mode 100644include/urcu/rculflist.hQuoted 7 lines
--
1.8.3.1_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
Re: [PATCH v2 0/4] userspace-rcu: Add lock-free, ordered singly linked list
In reply to a message not in the archiveQuoted 28 lines · ----- On Jul 30, 2019, at 9:34 AM, Junchang Wang [email protected] wrote:
Quoted 19 lines · Mathieu Desnoyers
Quoted 10 lines · ----- On Jul 29, 2019, at 9:35 AM, Junchang Wang [email protected] 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 ?
Quoted 6 lines
Items are linked through the struct
cds_lfht_nodenext field.The struct
cds_lfht_iteris used as a iterator on the list.struct
cds_lfhttbl_oder,tbl_chunkandtbl_mmapcontain the linked lists heads for each memory allocation scheme.
Quoted 6 lines
Hi Mathieu,
Thanks for the note. I checked rculfhash today, and the list implementation within rculfhash is indeed quite similar to the one I'm working on. I will check to see if we can merge the two versions and provide an independent rculflist.
Great!
Quoted 6 lines
Quoted 5 lines
I'm wondering why you need to re-implement a hash table though. What is missing from rculfhash to suit your needs ?
Quoted 7 lines
The major reason is that I want a hash table that can change its hash function on-the-fly. Split-ordered list is not adequate because it can only increase/decrease the number of buckets. Besides, I doubt the reverse operation is always efficient on platforms where hardware cannot help reverse bit strings. Hence I'm working on the new hash table algorithm, which, of course, is built on top of the linked list we are working on :-).
That makes a lot of sense. Re-hasing is indeed the main feature missing from rculfhash. I have ideas on how it could be introduced within the current split-ordered implementation with only small changes.
One possibility would be to create two lists (rather than one): the current list, and a second list that would be used when a re-hasing is performed. The old list would be used by readers while re-hashing is in progress, and add/del would take care of both lists when done concurrently with re-hashing. After re-hasing is complete, the old list would not be used anymore after a grace period has passed.
The cost of this approach is to have two next pointers per node (rather than one).
An alternative would be to add a temporary layer of indirection when the re-hasing is performed. The "next" pointer would actually point to an intermediate object which contains the chaining information for both the old and the new lists. This would save the cost of the additional next pointer within each node, at the expense of doing extra temporary memory allocation when doing the re-hashing.
I'd also be curious to see benchmarks of the bit-reversal compared to the rest of the operations needed for lookup, addition, and removal in a lock-free hash table for the main architectures that matter today. What architectures do you care about ?
I'm also curious to see what new hash table algorithm you have in mind!
Thanks,
Mathieu
Quoted 83 lines
Thanks,
--JunchangQuoted 71 lines
Thanks,
Mathieu
Quoted 58 lines
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 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 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:
- Functionsinsert(),delete(), andfind()return 0 in success, and return -Exxx otherwise.
- Fix a bug in functionis_removed().Cheers,
--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/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 100644doc/examples/rculflist/cds_lflist_delete_rcu.ccreate mode 100644doc/examples/rculflist/cds_lflist_find_rcu.ccreate mode 100644doc/examples/rculflist/cds_lflist_insert_rcu.ccreate mode 100644include/urcu/rculflist.hQuoted 7 lines
--
1.8.3.1_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-devQuoted 4 lines
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Re: [PATCH v2 0/4] userspace-rcu: Add lock-free, ordered singly linked list
In reply to a message not in the archiveHi Mathieu,
Thanks a lot for the feedback. Please see below,
Quoted 2 lines · Mathieu Desnoyers
----- On Jul 30, 2019, at 9:34 AM, Junchang Wang [email protected]
Quoted 5 lines · wrote:
Quoted 5 lines
Quoted 2 lines · Mathieu Desnoyers
----- On Jul 29, 2019, at 9:35 AM, Junchang Wang [email protected]
Quoted 4 lines · wrote:
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
Hi Mathieu and the list,
I'm recently using userspace-rcu to build lock-free data structures.
Thanks for
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
sharing this excellent project!
In building a hash table, I am looking for an ordered singly linked
list
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
that is lock-free. It seems such a list is missing in userspace-rcu.
I
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
discussed this with Paul in the mailing list of perfbook, and he
kindly
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
suggested me to submit my implementation to userspace-rcu. So here
is the
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 1 line
RFC. Any comments and suggestions are warmly welcome.
One point worth mentioning: the rculfhash data structure (rcu
lock-free hash
Quoted 1 line
Quoted 1 line
Quoted 1 line
table) already implements such list internally. You might want to have
a look
Quoted 1 line
Quoted 1 line
Quoted 1 line
at it, and perhaps just lift out its implementation into a separate .c
file
Quoted 43 lines
Quoted 9 lines
Quoted 8 lines
and header file so we can expose its implementation publicly ?
Items are linked through the struct
cds_lfht_nodenext field.The struct
cds_lfht_iteris used as a iterator on the list.struct
cds_lfhttbl_oder,tbl_chunkandtbl_mmapcontain the linked lists heads for each memory allocation scheme.Quoted 6 lines
Hi Mathieu,
Thanks for the note. I checked rculfhash today, and the list implementation within rculfhash is indeed quite similar to the one I'm working on. I will check to see if we can merge the two versions and provide an independent rculflist.
Great!
Quoted 6 lines
Quoted 5 lines
I'm wondering why you need to re-implement a hash table though. What is missing from rculfhash to suit your needs ?
Quoted 7 lines
The major reason is that I want a hash table that can change its hash function on-the-fly. Split-ordered list is not adequate because it can only increase/decrease the number of buckets. Besides, I doubt the reverse operation is always efficient on platforms where hardware cannot help reverse bit strings. Hence I'm working on the new hash table algorithm, which, of course, is built on top of the linked list we are working on :-).
That makes a lot of sense. Re-hasing is indeed the main feature missing from rculfhash. I have ideas on how it could be introduced within the current split-ordered implementation with only small changes.
One possibility would be to create two lists (rather than one): the current list, and a second list that would be used when a re-hasing is performed. The old list would be used by readers while re-hashing is in progress, and add/del would take care of both lists when done concurrently with re-hashing. After re-hasing is complete, the old list would not be used anymore after a grace period has passed.
Quoted 2 lines
The cost of this approach is to have two next pointers per node (rather than one).
Agree. And we need to customize a linked list to allow each node to contain two next pointers, before the hash table algorithm can use the list.
Quoted 8 lines
An alternative would be to add a temporary layer of indirection when the re-hasing is performed. The "next" pointer would actually point to an intermediate object which contains the chaining information for both the old and the new lists. This would save the cost of the additional next pointer within each node, at the expense of doing extra temporary memory allocation when doing the re-hashing.
Great suggestion! One benefit is that we may reuse a lock-free linked list without any modifications. If I understand correctly, the overall memory consumption with this approach is slightly larger than that of the previous one, because, in rehashing, each node has one intermediate node followed. Is that right?
Quoted 5 lines
I'd also be curious to see benchmarks of the bit-reversal compared to the rest of the operations needed for lookup, addition, and removal in a lock-free hash table for the main architectures that matter today. What architectures do you care about ?
Would be very happy to take a look at this and let you know the results soon. BTW, I was thinking that some architectures (e.g., x86) could have special instructions to help us accelerate the bit-reversal. Unfortunately, I searched on google today and can't find the exact instruction to do this. The most related instructions I found was at
https://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets . Do you know the x86 instructions that can reverse bit strings? Thanks.
Quoted 2 lines
I'm also curious to see what new hash table algorithm you have in mind!
I will write down the algorithm and send it to you soon.
Thanks,
--Junchang
Quoted 23 lines
Thanks,
Mathieu
Quoted 18 lines
Thanks,
--JunchangQuoted 14 lines
Thanks,
Mathieu
Quoted 9 lines
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,
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
such that the existence guarantees are provided by the RCU
mechanism,
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
and that no special memory management schemes (e.g., hazard
pointers)
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
is required anymore.
(2) The use of the RCU mechanism can naturally prevent the ABA
problem,
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
such that no flag field is required in this implementation.
Hence,
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
we save a variable of 8 bytes (typically sizeof(long)) for each
node.
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
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
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
version which fixes the known issues. Please review this version, if possible. The major changes are as follows. Sorry for the
inconvenience.
Quoted 17 lines
Quoted 17 lines
Quoted 17 lines
Quoted 17 lines
Any suggestions and comments are warmly welcome.
v1 -> v2:
- Functionsinsert(),delete(), andfind()return 0 in success, and return -Exxx otherwise.
- Fix a bug in functionis_removed().Cheers,
--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.md
Quoted 11 lines
Quoted 11 lines
Quoted 11 lines
Quoted 11 lines
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
+++++++++++++++++++++
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
11 files changed, 646 insertions(+)create mode 100644 doc/examples/rculflist/Makefile create mode 100644
doc/examples/rculflist/Makefile.cds_lflist_delete_rcu
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
create mode 100644
doc/examples/rculflist/Makefile.cds_lflist_find_rcu
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
create mode 100644
doc/examples/rculflist/Makefile.cds_lflist_insert_rcu
Quoted 22 lines
Quoted 13 lines
Quoted 13 lines
Quoted 12 lines
create mode 100644
doc/examples/rculflist/cds_lflist_delete_rcu.ccreate mode 100644doc/examples/rculflist/cds_lflist_find_rcu.ccreate mode 100644doc/examples/rculflist/cds_lflist_insert_rcu.ccreate mode 100644include/urcu/rculflist.h--
1.8.3.1_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-devQuoted 8 lines
Quoted 4 lines
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Quoted 4 lines
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev