* [RFC 1/4] userspace-rcu: Add lock-free singly linked list rculflist
[not found] <1562729290-6437-1-git-send-email-junchangwang@gmail.com>
@ 2019-07-10 3:28 ` Junchang Wang
2019-07-10 3:28 ` [RFC 2/4] userspace-rcu: Add sample code of rculflist Junchang Wang
` (4 subsequent siblings)
5 siblings, 0 replies; 6+ messages in thread
From: Junchang Wang @ 2019-07-10 3:28 UTC (permalink / raw)
To: mathieu.desnoyers, lttng-dev; +Cc: paulmck
Signed-off-by: Junchang Wang <junchangwang@gmail.com>
---
include/urcu/rculflist.h | 279 +++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 279 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..69f6303
--- /dev/null
+++ b/include/urcu/rculflist.h
@@ -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 */
--
2.7.4
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [RFC 2/4] userspace-rcu: Add sample code of rculflist
[not found] <1562729290-6437-1-git-send-email-junchangwang@gmail.com>
2019-07-10 3:28 ` [RFC 1/4] userspace-rcu: Add lock-free singly linked list rculflist Junchang Wang
@ 2019-07-10 3:28 ` Junchang Wang
2019-07-10 3:28 ` [RFC 3/4] userspace-rcu: Update Makefile.am to include rculflist into the project Junchang Wang
` (3 subsequent siblings)
5 siblings, 0 replies; 6+ messages in thread
From: Junchang Wang @ 2019-07-10 3:28 UTC (permalink / raw)
To: mathieu.desnoyers, lttng-dev; +Cc: paulmck
Signed-off-by: Junchang Wang <junchangwang@gmail.com>
---
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
diff --git a/doc/examples/Makefile.am b/doc/examples/Makefile.am
index edf00eb..369d92e 100644
--- a/doc/examples/Makefile.am
+++ b/doc/examples/Makefile.am
@@ -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:
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 <mathieu.desnoyers@efficios.com>
+#
+# 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 <mathieu.desnoyers@efficios.com>
+#
+# 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 <mathieu.desnoyers@efficios.com>
+#
+# 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..bbfde61
--- /dev/null
+++ b/doc/examples/rculflist/cds_lflist_delete_rcu.c
@@ -0,0 +1,100 @@
+/*
+ * 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 <stdio.h>
+#include <stdlib.h>
+
+#include <urcu/urcu-memb.h> /* RCU flavor */
+#include <urcu/rculflist.h> /* RCU lock-free linked list */
+#include <urcu/compiler.h> /* 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();
+ 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:");
+ 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));
+ 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..b47c37f
--- /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 <stdio.h>
+#include <stdlib.h>
+
+#include <urcu/urcu-memb.h> /* RCU flavor */
+#include <urcu/rculflist.h> /* RCU lock-free linked list */
+#include <urcu/compiler.h> /* 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();
+ 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) );
+ 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..8d8129c
--- /dev/null
+++ b/doc/examples/rculflist/cds_lflist_insert_rcu.c
@@ -0,0 +1,66 @@
+/*
+ * 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 <stdio.h>
+#include <stdlib.h>
+
+#include <urcu/urcu-memb.h> /* RCU flavor */
+#include <urcu/rculflist.h> /* RCU lock-free linked list */
+#include <urcu/compiler.h> /* 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);
+
+ /*
+ * Enqueue nodes.
+ */
+ 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();
+ cds_lflist_insert_rcu(&mylist, node);
+ urcu_memb_read_unlock();
+ }
+
+end:
+ urcu_memb_unregister_thread();
+ return ret;
+}
+
--
2.7.4
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [RFC 3/4] userspace-rcu: Update Makefile.am to include rculflist into the project
[not found] <1562729290-6437-1-git-send-email-junchangwang@gmail.com>
2019-07-10 3:28 ` [RFC 1/4] userspace-rcu: Add lock-free singly linked list rculflist Junchang Wang
2019-07-10 3:28 ` [RFC 2/4] userspace-rcu: Add sample code of rculflist Junchang Wang
@ 2019-07-10 3:28 ` Junchang Wang
2019-07-10 3:28 ` [RFC 4/4] userspace-rcu: Add a brief description of rculflist in cds-api.md Junchang Wang
` (2 subsequent siblings)
5 siblings, 0 replies; 6+ messages in thread
From: Junchang Wang @ 2019-07-10 3:28 UTC (permalink / raw)
To: mathieu.desnoyers, lttng-dev; +Cc: paulmck
Signed-off-by: Junchang Wang <junchangwang@gmail.com>
---
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 <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>
--
2.7.4
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [RFC 4/4] userspace-rcu: Add a brief description of rculflist in cds-api.md
[not found] <1562729290-6437-1-git-send-email-junchangwang@gmail.com>
` (2 preceding siblings ...)
2019-07-10 3:28 ` [RFC 3/4] userspace-rcu: Update Makefile.am to include rculflist into the project Junchang Wang
@ 2019-07-10 3:28 ` Junchang Wang
2019-07-10 15:14 ` [RFC 0/4] userspace-rcu: Add lock-free, ordered singly linked list rculflist Jonathan Rajotte-Julien
[not found] ` <20190710151410.GB3812@joraj-alpa>
5 siblings, 0 replies; 6+ messages in thread
From: Junchang Wang @ 2019-07-10 3:28 UTC (permalink / raw)
To: mathieu.desnoyers, lttng-dev; +Cc: paulmck
Signed-off-by: Junchang Wang <junchangwang@gmail.com>
---
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.
--
2.7.4
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [RFC 0/4] userspace-rcu: Add lock-free, ordered singly linked list rculflist
[not found] <1562729290-6437-1-git-send-email-junchangwang@gmail.com>
` (3 preceding siblings ...)
2019-07-10 3:28 ` [RFC 4/4] userspace-rcu: Add a brief description of rculflist in cds-api.md Junchang Wang
@ 2019-07-10 15:14 ` Jonathan Rajotte-Julien
[not found] ` <20190710151410.GB3812@joraj-alpa>
5 siblings, 0 replies; 6+ messages in thread
From: Jonathan Rajotte-Julien @ 2019-07-10 15:14 UTC (permalink / raw)
To: Junchang Wang; +Cc: lttng-dev, paulmck
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@lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
--
Jonathan Rajotte-Julien
EfficiOS
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [RFC 0/4] userspace-rcu: Add lock-free, ordered singly linked list rculflist
[not found] ` <20190710151410.GB3812@joraj-alpa>
@ 2019-07-11 1:19 ` Junchang Wang
0 siblings, 0 replies; 6+ messages in thread
From: Junchang Wang @ 2019-07-11 1:19 UTC (permalink / raw)
To: Jonathan Rajotte-Julien; +Cc: lttng-dev, Paul McKenney
[-- Attachment #1.1: Type: text/plain, Size: 3944 bytes --]
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@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@lists.lttng.org
> > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>
> --
> Jonathan Rajotte-Julien
> EfficiOS
>
[-- Attachment #1.2: Type: text/html, Size: 5115 bytes --]
[-- Attachment #2: Type: text/plain, Size: 156 bytes --]
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2019-07-11 1:19 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <1562729290-6437-1-git-send-email-junchangwang@gmail.com>
2019-07-10 3:28 ` [RFC 1/4] userspace-rcu: Add lock-free singly linked list rculflist Junchang Wang
2019-07-10 3:28 ` [RFC 2/4] userspace-rcu: Add sample code of rculflist Junchang Wang
2019-07-10 3:28 ` [RFC 3/4] userspace-rcu: Update Makefile.am to include rculflist into the project Junchang Wang
2019-07-10 3:28 ` [RFC 4/4] userspace-rcu: Add a brief description of rculflist in cds-api.md Junchang Wang
2019-07-10 15:14 ` [RFC 0/4] userspace-rcu: Add lock-free, ordered singly linked list rculflist Jonathan Rajotte-Julien
[not found] ` <20190710151410.GB3812@joraj-alpa>
2019-07-11 1:19 ` Junchang Wang
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).