[RFC 1/4] userspace-rcu: Add lock-free singly linked list rculflist

[RFC 1/4] userspace-rcu: Add lock-free singly linked list rculflist

[Junchang Wang]

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

[RFC 2/4] userspace-rcu: Add sample code of rculflist

[Junchang Wang]

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

[RFC 3/4] userspace-rcu: Update Makefile.am to include rculflist into the project

[Junchang Wang]

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

[RFC 4/4] userspace-rcu: Add a brief description of rculflist in cds-api.md

[Junchang Wang]

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

Re: [RFC 0/4] userspace-rcu: Add lock-free, ordered singly linked list rculflist

[Jonathan Rajotte-Julien]

Hi Junchang,

Thanks for contributing to URCU.

I just wanted to let you know that Mathieu is currently on vacation for ~2 weeks
so do not expect much feedback until his return.

Cheers

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

Re: [RFC 0/4] userspace-rcu: Add lock-free, ordered singly linked list rculflist

[Junchang Wang]

[-- 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