Skip to contentSkip to conversation

userspace-rcu: Add lock-free singly linked list rculflist

RFC Superseded Junchang Wang 2 participants 6 messages Jul 10, 2019 – Jul 11, 2019 2 messages not in the archive

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw

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

---
 include/urcu/rculflist.h | 279 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 279 insertions(+)
 create mode 100644 include/urcu/rculflist.h
include/urcu/rculflist.h new file +279 -0
new file mode 100644
index 0000000..69f6303
@@ -0,0 +1,279 @@
+/*
+ * rculflist.c
+ *
+ * Userspace RCU library - Lock-Free ordered, singly-linked list
+ *
+ * Copyright (c) 2019 Junchang Wang
+ * Copyright (c) 2019 Paul E. McKenney
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you can access it online at
+ * http://www.gnu.org/licenses/gpl-2.0.html.
+ *
+ *
+ * Based on the following research paper:
+ * - Maged M. Michael. High performance dynamic lock-free hash tables
+ *   and list-based sets. In Proceedings of the fourteenth annual ACM
+ *   symposium on Parallel algorithms and architectures, ACM Press,
+ *   (2002), 73-82.
+ *
+ * Some specificities of this Lock-free linked list implementation:
+ * - The original algorithm prevents the ABA problem by adding a tag field
+ *   in each hash-table node, whereas this implementation addresses this
+ *   issue by using the RCU mechanism.
+ */
+
+#ifndef _URCU_RCULFLIST_H
+#define _URCU_RCULFLIST_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <urcu/uatomic.h>
+#include <urcu-pointer.h>
+#include <urcu-call-rcu.h>
+
+#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
+#define READ_ONCE(x) \
+            ({ typeof(x) ___x = ACCESS_ONCE(x); ___x; })
+#define WRITE_ONCE(x, val) ({ ACCESS_ONCE(x) = (val); })
+
+/*
+ * lflist uses the least-significant 1 bit to indicate if a node has been
+ * logically removed.
+ */
+#define REMOVED_FLAG 	(1UL << 0)
+#define FLAGS_MASK 	((1UL << 1) - 1)
+
+/*
+ * Define the structure of list node and related functions.
+ */
+struct cds_lflist_node {
+	struct rcu_head rcu_head;
+	unsigned long key;
+	struct cds_lflist_node *next; /* (pointer | xxx_FLAG) */
+} __attribute__((aligned(8)));
+
+static inline
+unsigned long get_flag(struct cds_lflist_node *ptr)
+{
+	return (unsigned long)((uintptr_t)ptr & FLAGS_MASK);
+}
+
+static inline
+struct cds_lflist_node * get_ptr(struct cds_lflist_node *ptr)
+{
+	return (struct cds_lflist_node *)((uintptr_t)ptr & ~FLAGS_MASK);
+}
+
+static inline
+struct cds_lflist_node * set_flag(struct cds_lflist_node *ptr,
+                                      unsigned long mask)
+{
+	return (struct cds_lflist_node *)
+                    (((uintptr_t)ptr & ~FLAGS_MASK) | mask);
+}
+
+static inline
+int is_removed(struct cds_lflist_node *ptr)
+{
+	return (uintptr_t)ptr & REMOVED_FLAG;
+}
+
+void cds_lflist_node_init_rcu(struct cds_lflist_node *node)
+{
+	node->next = NULL;
+	node->key = 0UL;
+}
+
+void cds_lflist_node_set_key(struct cds_lflist_node *node, unsigned long key)
+{
+	node->key = key;
+}
+
+/*
+ * Struct cds_lflist_snapshot and its helper functions.
+ * Before invoking cds_lflist_find_rcu, the caller must first allocates
+ * an instance of struct cds_lflist_snapshot and passs the pointer
+ * to cds_lflist_find_rcu. By its completion, cds_lflist_find_rcu
+ * guarantees that (1) cur points to the node that contains the
+ * lowest key value that is greater than or equal to the input key
+ * and (2) prev is the predecessor pointer of cur.
+ */
+struct cds_lflist_snapshot {
+	struct cds_lflist_node **prev;
+	struct cds_lflist_node *cur;
+	struct cds_lflist_node *next;
+};
+
+static inline
+void set_snapshot(struct cds_lflist_snapshot *ssp,struct cds_lflist_node **prev,
+		     struct cds_lflist_node *cur, struct cds_lflist_node *next)
+{
+	ssp->prev = prev;
+	ssp->cur = get_ptr(cur);
+	ssp->next = get_ptr(next);
+}
+
+/*
+ * Define the struct of lock-free list and its helper functions.
+ */
+struct cds_lflist_rcu {
+	struct cds_lflist_node *head;
+	void (*delete_node)(struct cds_lflist_node *);
+};
+
+int cds_lflist_init_rcu(struct cds_lflist_rcu *list,
+		        void (*node_free)(struct cds_lflist_node *))
+{
+	list->head = NULL;
+	list->delete_node = node_free;
+	return 0;
+}
+
+/*
+ * Function cds_lflist_find_rcu() returns true(1) if a node with a matching key
+ * was found in the list, or returns false(0) otherwise.
+ * No matter if find_rcu() returns 1 or 0, by its completion, it guarantees
+ * that *ssp* points to the snapshot of a segment of the list. Within the
+ * snapshot, field *cur* points to the node that contains the lowest key value
+ * greater than or equal to the input key, and *prev* is the predecessor
+ * pointer of *cur*. Note that this function guarantees that the REMOVED_FLAG
+ * of the *cur* node has not been set.
+ */
+int cds_lflist_find_rcu(struct cds_lflist_rcu *list, unsigned long key,
+                            struct cds_lflist_snapshot *ssp)
+{
+	/* Local variables to record the snapshot */
+	struct cds_lflist_node **prev, *cur, *next;
+
+	struct cds_lflist_node *cur_ptr;
+	struct cds_lflist_node *next_ptr;
+	unsigned long cur_key;
+
+try_again:
+	prev = &list->head;
+	cur = READ_ONCE(*prev);
+	cur_ptr = get_ptr(cur);
+
+	for (;;) {
+		if (cur_ptr == NULL) {
+			/* Have reached the end of the list. */
+			set_snapshot(ssp, prev, NULL, NULL);
+			return 0;
+		}
+		cur_key = READ_ONCE(cur_ptr->key);
+		next = READ_ONCE(cur_ptr->next);
+		next_ptr = get_ptr(next);
+
+		/* If a new node has been added before cur, go to retry. */
+		if (READ_ONCE(*prev) != cur_ptr)
+			goto try_again;
+		if (!is_removed(next)) {
+			if (cur_key >= key) {
+				/* The key value of node cur_ptr is equal to
+				 * or larger than the input key value. */
+				set_snapshot(ssp, prev, cur, next);
+				return cur_key == key;
+			}
+			prev = &cur_ptr->next;
+		} else {
+			/* If the node cur_ptr has been logically deleted,
+			 * try to physically delete it. */
+			if (uatomic_cmpxchg(prev, cur_ptr, next_ptr) == cur_ptr){
+				/* Some applications (e.g., hashtorture) manages
+				 * (destroy) nodes by themselves. For these cases,
+				 * list->delete_node is initialized to NULL.  */
+				if(list->delete_node)
+					list->delete_node(cur_ptr);
+			} else {
+				/* One of other threads has physically delete
+				 * the node. Retry. */
+				goto try_again;
+			}
+		}
+		cur = next;
+		cur_ptr = get_ptr(cur);
+	}
+}
+
+/*
+ * Function cds_lflist_insert_rcu returns 0 if a node with a matching key
+ * is found in the list. Otherwise, this function inserts
+ * the new node before the node ss.cur and returns 1.
+ */
+int cds_lflist_insert_rcu(struct cds_lflist_rcu *list,
+                              struct cds_lflist_node *node)
+{
+	unsigned long key = node->key;
+	struct cds_lflist_snapshot ss;
+
+	for (;;) {
+		if (cds_lflist_find_rcu(list, key, &ss))
+			return 0;
+		node->next = set_flag(ss.cur, 0UL);
+		if (uatomic_cmpxchg(ss.prev, set_flag(ss.cur, 0UL),
+				set_flag(node,0UL)) == set_flag(ss.cur, 0UL)) {
+			return 1;
+		}
+	}
+}
+
+/*
+ * Function cds_lflist_delete_rcu returns 0 if the key is not found in the list.
+ * Otherwise, the key value of the node pointed to by ss.cur must be equal to
+ * the input key. The function deletes the node by (1) marking the node pointed
+ * to by ss.cur as deleted, and (2) swinging prev->next to point to next.
+ */
+int cds_lflist_delete_rcu(struct cds_lflist_rcu *list, unsigned long key)
+{
+	/* Local variables to record the snapshot */
+	struct cds_lflist_node *cur, *next;
+	struct cds_lflist_snapshot ss;
+
+	for (;;) {
+		if (!cds_lflist_find_rcu(list, key, &ss))
+			return 0;
+		cur = ss.cur;
+		next = ss.next;
+
+		/* The node to be deleted is pointed to by ss.cur.
+		 * We first logically deleted it by setting its REMOVED_FLAG.
+		 */
+		if (uatomic_cmpxchg(&cur->next, set_flag(next, 0UL),
+				set_flag(next, 1UL)) != set_flag(next, 0UL))
+			continue;
+		/* If node pointed to by ss.cur has been logically deleted,
+		 * try to physically delete it.
+		 */
+		if (uatomic_cmpxchg(ss.prev, set_flag(cur, 0UL),
+				set_flag(next, 0UL)) == set_flag(cur, 0UL)) {
+			/* Some applications (e.g., hashtorture) manages
+			 * (destroy) nodes by themselves. For these cases,
+			 * list->delete_node is initialized to NULL.  */
+			if (list->delete_node)
+				list->delete_node(cur);
+		} else {
+			/* Physical deletion failed. Retry.  */
+			cds_lflist_find_rcu(list, key, &ss);
+		}
+		return 1;
+	}
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /*_URCU_RCULFLIST_H */
Signature · 1 line
2.7.4
#2 lore raw

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

In reply to a message not in the archive

---

For the three Makefiles, I just copied, pasted, and updated slightly, so I didn't change the copyright information.

 doc/examples/Makefile.am                           |  13 ++-
 .../rculflist/Makefile.cds_lflist_delete_rcu       |  21 +++++
 .../rculflist/Makefile.cds_lflist_find_rcu         |  21 +++++
 .../rculflist/Makefile.cds_lflist_insert_rcu       |  21 +++++
 doc/examples/rculflist/cds_lflist_delete_rcu.c     | 100 +++++++++++++++++++++
 doc/examples/rculflist/cds_lflist_find_rcu.c       |  96 ++++++++++++++++++++
 doc/examples/rculflist/cds_lflist_insert_rcu.c     |  66 ++++++++++++++
 7 files changed, 337 insertions(+), 1 deletion(-)
 create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_delete_rcu
 create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_find_rcu
 create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_insert_rcu
 create mode 100644 doc/examples/rculflist/cds_lflist_delete_rcu.c
 create mode 100644 doc/examples/rculflist/cds_lflist_find_rcu.c
 create mode 100644 doc/examples/rculflist/cds_lflist_insert_rcu.c
doc/examples/Makefile.am +12 -1
index edf00eb..369d92e 100644
@@ -111,13 +111,24 @@ dist_doc_examples_rculfhash_DATA = \
 	rculfhash/cds_lfht_lookup.c \
 	rculfhash/cds_lfht_for_each_entry_duplicate.c
 
+doc_examples_rculflistdir = ${doc_examplesdir}/rculflist
+
+dist_doc_examples_rculflist_DATA = \
+	rculflist/Makefile \
+	rculflist/Makefile.cds_lflist_insert_rcu \
+	rculflist/Makefile.cds_lflist_delete_rcu \
+	rculflist/Makefile.cds_lflist_find_rcu \
+	rculflist/cds_lflist_insert_rcu.c \
+	rculflist/cds_lflist_delete_rcu.c \
+	rculflist/cds_lflist_find_rcu.c
+
 if NO_SHARED
 # Don't build examples if shared libraries support was explicitly
 # disabled.
 else
 
 SUBDIRS_PROXY = hlist list urcu-flavors wfcqueue rculfqueue \
-	wfstack lfstack rculfhash
+	wfstack lfstack rculfhash rculflist
 
 # Copies are for VPATH build support.
 all-local:
doc/examples/rculflist/Makefile.cds_lflist_delete_rcu new file +21 -0
new file mode 100644
index 0000000..09d1a55
@@ -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
new file mode 100644
index 0000000..77ad9b4
@@ -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
new file mode 100644
index 0000000..cdde123
@@ -0,0 +1,21 @@
+# Copyright (C) 2013  Mathieu Desnoyers <[email protected]>
+#
+# THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
+# OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
+#
+# Permission is hereby granted to use or copy this program for any
+# purpose,  provided the above notices are retained on all copies.
+# Permission to modify the code and to distribute modified code is
+# granted, provided the above notices are retained, and a notice that
+# the code was modified is included with the above copyright notice.
+#
+# This makefile is purposefully kept simple to support GNU and BSD make.
+
+EXAMPLE_NAME = cds_lflist_insert_rcu
+
+SOURCES = $(EXAMPLE_NAME).c
+OBJECTS = $(EXAMPLE_NAME).o
+BINARY = $(EXAMPLE_NAME)
+LIBS = -lurcu
+
+include ../Makefile.examples.template
doc/examples/rculflist/cds_lflist_delete_rcu.c new file +100 -0

100 lines not on this page · raw message

doc/examples/rculflist/cds_lflist_find_rcu.c new file +96 -0

96 lines not on this page · raw message

doc/examples/rculflist/cds_lflist_insert_rcu.c new file +66 -0

66 lines not on this page · raw message

Signature · 1 line
2.7.4
#3 lore raw

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

In reply to a message not in the archive
---
 include/Makefile.am | 1 +
 include/urcu/cds.h  | 1 +
 2 files changed, 2 insertions(+)
include/Makefile.am +1 -0
index 34812d4..c4de329 100644
@@ -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
index 78534bb..faa31ab 100644
@@ -30,6 +30,7 @@
 #include <urcu/rculfqueue.h>
 #include <urcu/rculfstack.h>
 #include <urcu/rculfhash.h>
+#include <urcu/rculflist.h>
 #include <urcu/wfqueue.h>
 #include <urcu/wfcqueue.h>
 #include <urcu/wfstack.h>
Signature · 1 line
2.7.4
#4 lore raw

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

In reply to a message not in the archive
---
 doc/cds-api.md | 7 +++++++
 1 file changed, 7 insertions(+)
doc/cds-api.md +7 -0
index 49a3c7c..577126a 100644
@@ -82,3 +82,10 @@ are supported. Provides "uniquify add" and "replace add"
 operations, along with associated read-side traversal uniqueness
 guarantees. Automatic hash table resize based on number of
 elements is supported. See the API for more details.
+
+
+### `urcu/rculflist.h`
+
+Ordered singly linked list with lock-free insert, delete and find operations.
+This list relies on RCU for existence guarantees and ABA-problem prevention.
+It is useful for implementing hash tables.
Signature · 1 line
2.7.4
#5 lore raw

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

In reply to a message not in the archive

Hi Junchang,

Thanks for contributing to URCU.

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

Cheers

Quoted 66 lines · Junchang Wang

Hi Mathieu and the list,

I'm recently using userspace-rcu to build lock-free data structures. Thanks for sharing this excellent project!

In building a hash table, I am looking for an ordered singly linked list that is lock-free. It seems such a list is missing in userspace-rcu. I discussed this with Paul in the mailing list of perfbook, and he kindly suggested me to submit my implementation to userspace-rcu. So here is the RFC. Any comments and suggestions are warmly welcome.

This singly linked list is based on the following research paper:
- Maged M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, ACM Press, (2002), 73-82.

And this implementation has the following unique features:
(1) Insert, Delete, and Find operations are protected by 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
Signature · 6 lines
2.7.4

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Signature · 2 lines
Jonathan Rajotte-Julien
EfficiOS

A message that is not in the archive (sent off-list or not yet received): 20190710151410.GB3812@joraj-alpa

#7 lore raw

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

Hi Jonathan,

Thanks for letting me know. The patch isn't in a hurry, so it's good for me to discuss this patch after Mathieu returns.

Thanks,
--Junchang

Quoted 77 lines · Jonathan Rajotte-Julien

Hi Junchang,

Thanks for contributing to URCU.

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

Cheers

Quoted 3 lines · Junchang Wang

Hi Mathieu and the list,

I'm recently using userspace-rcu to build lock-free data structures.

Thanks for

Quoted 14 lines

sharing this excellent project!

In building a hash table, I am looking for an ordered singly linked list that is lock-free. It seems such a list is missing in userspace-rcu. I discussed this with Paul in the mailing list of perfbook, and he kindly suggested me to submit my implementation to userspace-rcu. So here is the RFC. Any comments and suggestions are warmly welcome.

This singly linked list is based on the following research paper:
- Maged M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, ACM Press, (2002), 73-82.

Quoted 3 lines

And this implementation has the following unique features:
(1) Insert, Delete, and Find operations are protected by RCU read_lock, such that the existence guarantees are provided by the RCU

mechanism,

Quoted 1 line

and that no special memory management schemes (e.g., hazard

pointers)

Quoted 18 lines

is required anymore.
(2) The use of the RCU mechanism can naturally prevent the ABA problem, such that no flag field is required in this implementation. Hence, we save a long integer (typically 8 bytes) for each node.

This is my first patch to this mailing list, so please let me know if I messed anything up. Any comments and suggestions are warmly welcome.

Thanks,
--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

Quoted 11 lines
 doc/cds-api.md                                     |   7 +
 doc/examples/Makefile.am                           |  13 +-
 .../rculflist/Makefile.cds_lflist_delete_rcu       |  21 ++
 .../rculflist/Makefile.cds_lflist_find_rcu         |  21 ++
 .../rculflist/Makefile.cds_lflist_insert_rcu       |  21 ++
 doc/examples/rculflist/cds_lflist_delete_rcu.c     | 100 ++++++++
 doc/examples/rculflist/cds_lflist_find_rcu.c       |  96 +++++++
 doc/examples/rculflist/cds_lflist_insert_rcu.c     |  66 +++++
 include/Makefile.am                                |   1 +
 include/urcu/cds.h                                 |   1 +
 include/urcu/rculflist.h                           | 279

+++++++++++++++++++++

Quoted 12 lines
 11 files changed, 625 insertions(+), 1 deletion(-)
 create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_delete_rcu
 create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_find_rcu
 create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_insert_rcu
 create mode 100644 doc/examples/rculflist/cds_lflist_delete_rcu.c
 create mode 100644 doc/examples/rculflist/cds_lflist_find_rcu.c
 create mode 100644 doc/examples/rculflist/cds_lflist_insert_rcu.c
 create mode 100644 include/urcu/rculflist.h

--
2.7.4

Quoted 9 lines
Quoted 4 lines

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

--
Jonathan Rajotte-Julien
EfficiOS

_______________________________________________
lttng-dev mailing list
[email protected]
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev