From patchwork Mon Jul 29 13:35:28 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Junchang Wang X-Patchwork-Id: 3249473 From: junchangwang at gmail.com (Junchang Wang) Date: Mon, 29 Jul 2019 21:35:28 +0800 Subject: [lttng-dev] [PATCH v2 1/4] userspace-rcu: Add lock-free singly linked list rculflist In-Reply-To: <1564407331-25820-1-git-send-email-junchangwang@gmail.com> References: <1564407331-25820-1-git-send-email-junchangwang@gmail.com> Message-ID: <1564407331-25820-2-git-send-email-junchangwang@gmail.com> Signed-off-by: Junchang Wang --- include/urcu/rculflist.h | 284 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 284 insertions(+) create mode 100644 include/urcu/rculflist.h diff --git a/include/urcu/rculflist.h b/include/urcu/rculflist.h new file mode 100644 index 0000000..35c08aa --- /dev/null +++ b/include/urcu/rculflist.h @@ -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 +#include +#include +#include + +#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 */ From patchwork Mon Jul 29 13:35:29 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Junchang Wang X-Patchwork-Id: 3249474 From: junchangwang at gmail.com (Junchang Wang) Date: Mon, 29 Jul 2019 21:35:29 +0800 Subject: [lttng-dev] [PATCH v2 2/4] userspace-rcu: Add sample code of rculflist In-Reply-To: <1564407331-25820-1-git-send-email-junchangwang@gmail.com> References: <1564407331-25820-1-git-send-email-junchangwang@gmail.com> Message-ID: <1564407331-25820-3-git-send-email-junchangwang@gmail.com> Signed-off-by: Junchang Wang --- 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 diff --git a/doc/examples/rculflist/Makefile b/doc/examples/rculflist/Makefile new file mode 100644 index 0000000..b804b13 --- /dev/null +++ b/doc/examples/rculflist/Makefile @@ -0,0 +1,24 @@ +# Copyright (C) 2013 Junchang Wang +# +# 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 + diff --git a/doc/examples/rculflist/Makefile.cds_lflist_delete_rcu b/doc/examples/rculflist/Makefile.cds_lflist_delete_rcu new file mode 100644 index 0000000..09d1a55 --- /dev/null +++ b/doc/examples/rculflist/Makefile.cds_lflist_delete_rcu @@ -0,0 +1,21 @@ +# Copyright (C) 2013 Mathieu Desnoyers +# +# 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 diff --git a/doc/examples/rculflist/Makefile.cds_lflist_find_rcu b/doc/examples/rculflist/Makefile.cds_lflist_find_rcu new file mode 100644 index 0000000..77ad9b4 --- /dev/null +++ b/doc/examples/rculflist/Makefile.cds_lflist_find_rcu @@ -0,0 +1,21 @@ +# Copyright (C) 2013 Mathieu Desnoyers +# +# 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 diff --git a/doc/examples/rculflist/Makefile.cds_lflist_insert_rcu b/doc/examples/rculflist/Makefile.cds_lflist_insert_rcu new file mode 100644 index 0000000..cdde123 --- /dev/null +++ b/doc/examples/rculflist/Makefile.cds_lflist_insert_rcu @@ -0,0 +1,21 @@ +# Copyright (C) 2013 Mathieu Desnoyers +# +# 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 diff --git a/doc/examples/rculflist/cds_lflist_delete_rcu.c b/doc/examples/rculflist/cds_lflist_delete_rcu.c new file mode 100644 index 0000000..d5b1327 --- /dev/null +++ b/doc/examples/rculflist/cds_lflist_delete_rcu.c @@ -0,0 +1,101 @@ +/* + * Copyright (C) 2019 Junchang Wang + * + * 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 example shows how to delete a node from a linked-list safely against + * concurrent RCU traversals. + */ + +#include +#include + +#include /* RCU flavor */ +#include /* RCU lock-free linked list */ +#include /* For CAA_ARRAY_SIZE */ + +static void free_node(struct rcu_head *head) +{ + struct cds_lflist_node *node = + caa_container_of(head, struct cds_lflist_node, rcu_head); + + free(node); +} + +int main(int argc, char **argv) +{ + int values[] = { -5, 42, 36, 24, }; + struct cds_lflist_node * nodes[CAA_ARRAY_SIZE(values)]; + + struct cds_lflist_rcu mylist; /* List */ + unsigned int i; + int ret = 0; + + /* + * Each thread using RCU read-side needs to be explicitly + * registered. + */ + urcu_memb_register_thread(); + + cds_lflist_init_rcu(&mylist, NULL); + + /* + * Insert nodes. + */ + printf("Insert content:"); + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + struct cds_lflist_node *node; + + node = malloc(sizeof(*node)); + if (!node) { + ret = -1; + goto end; + } + + nodes[i] = node; + cds_lflist_node_init_rcu(node); + cds_lflist_node_set_key(node, values[i]); + /* + * Both insert and delete need to be called within RCU + * read-side critical section. + */ + urcu_memb_read_lock(); + assert(!cds_lflist_insert_rcu(&mylist, node)); + urcu_memb_read_unlock(); + printf(" %ld", node->key); + } + printf("\n"); + + /* + * Delete each node from the queue. + */ + printf("Delete content:"); + struct cds_lflist_snapshot ss; + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + struct cds_lflist_node *node = nodes[i]; + + /* + * Both insert and delete need to be called within RCU + * read-side critical section. + */ + urcu_memb_read_lock(); + assert(!cds_lflist_delete_rcu(&mylist, node->key, &ss)); + urcu_memb_read_unlock(); + + printf(" %ld", node->key); + urcu_memb_call_rcu(&node->rcu_head, free_node); + } + printf("\n"); + +end: + urcu_memb_unregister_thread(); + return ret; +} + diff --git a/doc/examples/rculflist/cds_lflist_find_rcu.c b/doc/examples/rculflist/cds_lflist_find_rcu.c new file mode 100644 index 0000000..bb465c1 --- /dev/null +++ b/doc/examples/rculflist/cds_lflist_find_rcu.c @@ -0,0 +1,96 @@ +/* + * Copyright (C) 2019 Junchang Wang + * + * 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 example shows how to safely search a key in the linked list. + */ + +#include +#include + +#include /* RCU flavor */ +#include /* RCU lock-free linked list */ +#include /* For CAA_ARRAY_SIZE */ + +int main(int argc, char **argv) +{ + int values[] = { -5, 42, 36, 24, }; + struct cds_lflist_node * nodes[CAA_ARRAY_SIZE(values)]; + + struct cds_lflist_rcu mylist; /* List */ + unsigned int i; + int ret = 0; + + /* + * Each thread using RCU read-side need to be explicitly + * registered. + */ + urcu_memb_register_thread(); + + cds_lflist_init_rcu(&mylist, NULL); + + /* + * Insert nodes. + */ + printf("Insert content:"); + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + struct cds_lflist_node *node; + + node = malloc(sizeof(*node)); + if (!node) { + ret = -1; + goto end; + } + + nodes[i] = node; + cds_lflist_node_init_rcu(node); + cds_lflist_node_set_key(node, values[i]); + /* + * Both insert and delete need to be called within RCU + * read-side critical section. + */ + urcu_memb_read_lock(); + assert(!cds_lflist_insert_rcu(&mylist, node)); + urcu_memb_read_unlock(); + printf(" %ld", node->key); + } + printf("\n"); + + /* + * Search each node from the queue. + */ + struct cds_lflist_snapshot ss; + long invalid_key = 0; + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + struct cds_lflist_node *node = nodes[i]; + + /* + * Function find needs to be called within RCU + * read-side critical section. + */ + urcu_memb_read_lock(); + assert(!cds_lflist_find_rcu(&mylist, node->key, &ss)); + urcu_memb_read_unlock(); + + invalid_key += node->key; + printf("Find content: %ld\n", node->key); + } + + urcu_memb_read_lock(); + assert(cds_lflist_find_rcu(&mylist, invalid_key, &ss) == -ENOENT); + urcu_memb_read_unlock(); + printf("Can't find content: %ld\n", invalid_key); + +end: + urcu_memb_unregister_thread(); + return ret; +} + diff --git a/doc/examples/rculflist/cds_lflist_insert_rcu.c b/doc/examples/rculflist/cds_lflist_insert_rcu.c new file mode 100644 index 0000000..252a25c --- /dev/null +++ b/doc/examples/rculflist/cds_lflist_insert_rcu.c @@ -0,0 +1,69 @@ +/* + * Copyright (C) 2019 Junchang Wang + * + * 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 example shows how to add into a linked-list safely against + * concurrent RCU traversals. + */ + +#include +#include + +#include /* RCU flavor */ +#include /* RCU lock-free linked list */ +#include /* For CAA_ARRAY_SIZE */ + +int main(int argc, char **argv) +{ + int values[] = { -5, 42, 36, 24, }; + struct cds_lflist_rcu mylist; /* List */ + unsigned int i; + int ret = 0; + + /* + * Each thread using RCU read-side needs to be explicitly + * registered. + */ + urcu_memb_register_thread(); + + cds_lflist_init_rcu(&mylist, NULL); + + /* + * Insert nodes. + */ + printf("Insert content:"); + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + struct cds_lflist_node *node; + + node = malloc(sizeof(*node)); + if (!node) { + ret = -1; + goto end; + } + + cds_lflist_node_init_rcu(node); + cds_lflist_node_set_key(node, values[i]); + /* + * Both insert and delete need to be called within RCU + * read-side critical section. + */ + urcu_memb_read_lock(); + assert(!cds_lflist_insert_rcu(&mylist, node)); + urcu_memb_read_unlock(); + printf(" %ld", node->key); + } + printf("\n"); + +end: + urcu_memb_unregister_thread(); + return ret; +} + From patchwork Mon Jul 29 13:35:30 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Junchang Wang X-Patchwork-Id: 3249475 From: junchangwang at gmail.com (Junchang Wang) Date: Mon, 29 Jul 2019 21:35:30 +0800 Subject: [lttng-dev] [PATCH v2 3/4] userspace-rcu: Update Makefile.am to include rculflist into the project In-Reply-To: <1564407331-25820-1-git-send-email-junchangwang@gmail.com> References: <1564407331-25820-1-git-send-email-junchangwang@gmail.com> Message-ID: <1564407331-25820-4-git-send-email-junchangwang@gmail.com> Signed-off-by: Junchang Wang --- include/Makefile.am | 1 + include/urcu/cds.h | 1 + 2 files changed, 2 insertions(+) diff --git a/include/Makefile.am b/include/Makefile.am index 34812d4..c4de329 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -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 \ diff --git a/include/urcu/cds.h b/include/urcu/cds.h index 78534bb..faa31ab 100644 --- a/include/urcu/cds.h +++ b/include/urcu/cds.h @@ -30,6 +30,7 @@ #include #include #include +#include #include #include #include From patchwork Mon Jul 29 13:35:31 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Junchang Wang X-Patchwork-Id: 3249476 From: junchangwang at gmail.com (Junchang Wang) Date: Mon, 29 Jul 2019 21:35:31 +0800 Subject: [lttng-dev] [PATCH v2 4/4] userspace-rcu: Add a brief description of rculflist in cds-api.md In-Reply-To: <1564407331-25820-1-git-send-email-junchangwang@gmail.com> References: <1564407331-25820-1-git-send-email-junchangwang@gmail.com> Message-ID: <1564407331-25820-5-git-send-email-junchangwang@gmail.com> Signed-off-by: Junchang Wang --- doc/cds-api.md | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/doc/cds-api.md b/doc/cds-api.md index 49a3c7c..577126a 100644 --- a/doc/cds-api.md +++ b/doc/cds-api.md @@ -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.