Skip to contentSkip to conversation

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

PATCH New Junchang Wang 2 participants 9 messages Jul 29, 2019 – Aug 1, 2019 5 messages not in the archive

lore
Share & tools
lore

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

#1 lore raw

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

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

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

In reply to a message not in the archive
---
 doc/examples/rculflist/Makefile                    |  24 +++++
 .../rculflist/Makefile.cds_lflist_delete_rcu       |  21 +++++
 .../rculflist/Makefile.cds_lflist_find_rcu         |  21 +++++
 .../rculflist/Makefile.cds_lflist_insert_rcu       |  21 +++++
 doc/examples/rculflist/cds_lflist_delete_rcu.c     | 101 +++++++++++++++++++++
 doc/examples/rculflist/cds_lflist_find_rcu.c       |  96 ++++++++++++++++++++
 doc/examples/rculflist/cds_lflist_insert_rcu.c     |  69 ++++++++++++++
 7 files changed, 353 insertions(+)
 create mode 100644 doc/examples/rculflist/Makefile
 create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_delete_rcu
 create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_find_rcu
 create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_insert_rcu
 create mode 100644 doc/examples/rculflist/cds_lflist_delete_rcu.c
 create mode 100644 doc/examples/rculflist/cds_lflist_find_rcu.c
 create mode 100644 doc/examples/rculflist/cds_lflist_insert_rcu.c
doc/examples/rculflist/Makefile new file +24 -0
new file mode 100644
index 0000000..b804b13
@@ -0,0 +1,24 @@
+# Copyright (C) 2013  Junchang Wang <[email protected]>
+#
+# THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
+# OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
+#
+# Permission is hereby granted to use or copy this program for any
+# purpose,  provided the above notices are retained on all copies.
+# Permission to modify the code and to distribute modified code is
+# granted, provided the above notices are retained, and a notice that
+# the code was modified is included with the above copyright notice.
+#
+# This makefile is purposefully kept simple to support GNU and BSD make.
+
+all:
+	$(AM_V_at)$(MAKE) -f Makefile.cds_lflist_insert_rcu
+	$(AM_V_at)$(MAKE) -f Makefile.cds_lflist_delete_rcu
+	$(AM_V_at)$(MAKE) -f Makefile.cds_lflist_find_rcu
+
+.PHONY: clean
+clean:
+	$(AM_V_at)$(MAKE) -f Makefile.cds_lflist_insert_rcu clean
+	$(AM_V_at)$(MAKE) -f Makefile.cds_lflist_delete_rcu clean
+	$(AM_V_at)$(MAKE) -f Makefile.cds_lflist_find_rcu clean
+
doc/examples/rculflist/Makefile.cds_lflist_delete_rcu new file +21 -0
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 +101 -0

101 lines not on this page · raw message

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

96 lines not on this page · raw message

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

69 lines not on this page · raw message

Signature · 1 line
1.8.3.1
#3 lore raw

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

In reply to a message not in the archive
---
 include/Makefile.am | 1 +
 include/urcu/cds.h  | 1 +
 2 files changed, 2 insertions(+)
include/Makefile.am +1 -0
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
1.8.3.1
#4 lore raw

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

In reply to a message not in the archive
---
 doc/cds-api.md | 7 +++++++
 1 file changed, 7 insertions(+)
doc/cds-api.md +7 -0
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
1.8.3.1

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

#6 lore raw
Quoted 1 line · ----- On Jul 29, 2019, at 9:35 AM, Junchang Wang [email protected] wrote:

Hi Junchang,

Thanks for submitting this! I've been on vacation for the past two weeks, hence the delay in reply.

A few points:

I think we should move the implementation of find/insert/delete to a .c file (rather than headers) because at least two of those functions are larger than 10 lines, and therefore don't fall under the "trivial" category.

I also notice that the implementation you propose is GPLv2+. Would you be willing to re-license your contribution under LGPLv2.1 or LGPLv2.1+ ? This is the license we use for the entire Userspace RCU library. liburcu is meant to be used by non-GPL/LGPL programs as well.

I'll wait until I get an answer from you on those points before digging further into the code.

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#7 lore raw

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

In reply to a message not in the archive
Quoted 10 lines · ----- On Jul 29, 2019, at 9:35 AM, Junchang Wang [email protected] wrote:

Hi Mathieu and the list,

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

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

One point worth mentioning: the rculfhash data structure (rcu lock-free hash table) already implements such list internally. You might want to have a look at it, and perhaps just lift out its implementation into a separate .c file and header file so we can expose its implementation publicly ?

Items are linked through the struct cds_lfht_node next field.

The struct cds_lfht_iter is used as a iterator on the list.

struct cds_lfht tbl_oder, tbl_chunk and tbl_mmap contain the linked lists heads for each memory allocation scheme.

I'm wondering why you need to re-implement a hash table though. What is missing from rculfhash to suit your needs ?

Thanks,

Mathieu

Quoted 65 lines

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

And we made the following two major improvements:
(1) Insert, Delete, and Find operations are protected by 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 variable of 8 bytes (typically sizeof(long)) for each node.

In the past two weeks, I found some bugs in the first version of the list in building a lock-free hash table on top it. So this is the second version which fixes the known issues. Please review this version, if possible. The major changes are as follows. Sorry for the inconvenience. Any suggestions and comments are warmly welcome.

v1 -> v2:
- Functions insert(), delete(), and find() return 0 in success, and return -Exxx otherwise.
- Fix a bug in function is_removed().

Cheers,
--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/rculflist/Makefile                    |  24 ++
.../rculflist/Makefile.cds_lflist_delete_rcu       |  21 ++
.../rculflist/Makefile.cds_lflist_find_rcu         |  21 ++
.../rculflist/Makefile.cds_lflist_insert_rcu       |  21 ++
doc/examples/rculflist/cds_lflist_delete_rcu.c     | 101 ++++++++
doc/examples/rculflist/cds_lflist_find_rcu.c       |  96 +++++++
doc/examples/rculflist/cds_lflist_insert_rcu.c     |  69 +++++
include/Makefile.am                                |   1 +
include/urcu/cds.h                                 |   1 +
include/urcu/rculflist.h                           | 284 +++++++++++++++++++++
11 files changed, 646 insertions(+)

create mode 100644 doc/examples/rculflist/Makefile
create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_delete_rcu create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_find_rcu create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_insert_rcu create mode 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

--
1.8.3.1

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

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

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

#9 lore raw

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

Quoted 19 lines · Mathieu Desnoyers
Quoted 10 lines · ----- On Jul 29, 2019, at 9:35 AM, Junchang Wang [email protected] wrote:

Hi Mathieu and the list,

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

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

One point worth mentioning: the rculfhash data structure (rcu lock-free hash table) already implements such list internally. You might want to have a look at it, and perhaps just lift out its implementation into a separate .c file and header file so we can expose its implementation publicly ?

Quoted 6 lines

Items are linked through the struct cds_lfht_node next field.

The struct cds_lfht_iter is used as a iterator on the list.

struct cds_lfht tbl_oder, tbl_chunk and tbl_mmap contain the linked lists heads for each memory allocation scheme.

Hi Mathieu,

Thanks for the note. I checked rculfhash today, and the list implementation within rculfhash is indeed quite similar to the one I'm working on. I will check to see if we can merge the two versions and provide an independent rculflist.

Quoted 4 lines

I'm wondering why you need to re-implement a hash table though. What is missing from rculfhash to suit your needs ?

The major reason is that I want a hash table that can change its hash function on-the-fly. Split-ordered list is not adequate because it can only increase/decrease the number of buckets. Besides, I doubt the reverse operation is always efficient on platforms where hardware cannot help reverse bit strings. Hence I'm working on the new hash table algorithm, which, of course, is built on top of the linked list we are working on :-).

Thanks,
--Junchang

Quoted 75 lines

Thanks,

Mathieu

Quoted 58 lines

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

And we made the following two major improvements:
(1) Insert, Delete, and Find operations are protected by 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 variable of 8 bytes (typically sizeof(long)) for each node.

In the past two weeks, I found some bugs in the first version of the list in building a lock-free hash table on top it. So this is the second version which fixes the known issues. Please review this version, if possible. The major changes are as follows. Sorry for the inconvenience. Any suggestions and comments are warmly welcome.

v1 -> v2:
- Functions insert(), delete(), and find() return 0 in success, and return -Exxx otherwise.
- Fix a bug in function is_removed().

Cheers,
--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/rculflist/Makefile                    |  24 ++
.../rculflist/Makefile.cds_lflist_delete_rcu       |  21 ++
.../rculflist/Makefile.cds_lflist_find_rcu         |  21 ++
.../rculflist/Makefile.cds_lflist_insert_rcu       |  21 ++
doc/examples/rculflist/cds_lflist_delete_rcu.c     | 101 ++++++++
doc/examples/rculflist/cds_lflist_find_rcu.c       |  96 +++++++
doc/examples/rculflist/cds_lflist_insert_rcu.c     |  69 +++++
include/Makefile.am                                |   1 +
include/urcu/cds.h                                 |   1 +
include/urcu/rculflist.h                           | 284 +++++++++++++++++++++
11 files changed, 646 insertions(+)

create mode 100644 doc/examples/rculflist/Makefile
create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_delete_rcu create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_find_rcu create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_insert_rcu create mode 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

Quoted 7 lines

--
1.8.3.1

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

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): CABoNC821qnePU4Enrs8mSseVq-_Hp3Cehh93DO0+s=cKtDTZXQ@mail.gmail.com

#11 lore raw

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

Quoted 28 lines · ----- On Jul 30, 2019, at 9:34 AM, Junchang Wang [email protected] wrote:
Quoted 19 lines · Mathieu Desnoyers
Quoted 10 lines · ----- On Jul 29, 2019, at 9:35 AM, Junchang Wang [email protected] wrote:

Hi Mathieu and the list,

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

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

One point worth mentioning: the rculfhash data structure (rcu lock-free hash table) already implements such list internally. You might want to have a look at it, and perhaps just lift out its implementation into a separate .c file and header file so we can expose its implementation publicly ?

Quoted 6 lines

Items are linked through the struct cds_lfht_node next field.

The struct cds_lfht_iter is used as a iterator on the list.

struct cds_lfht tbl_oder, tbl_chunk and tbl_mmap contain the linked lists heads for each memory allocation scheme.

Quoted 6 lines

Hi Mathieu,

Thanks for the note. I checked rculfhash today, and the list implementation within rculfhash is indeed quite similar to the one I'm working on. I will check to see if we can merge the two versions and provide an independent rculflist.

Great!

Quoted 6 lines
Quoted 5 lines

I'm wondering why you need to re-implement a hash table though. What is missing from rculfhash to suit your needs ?

Quoted 7 lines

The major reason is that I want a hash table that can change its hash function on-the-fly. Split-ordered list is not adequate because it can only increase/decrease the number of buckets. Besides, I doubt the reverse operation is always efficient on platforms where hardware cannot help reverse bit strings. Hence I'm working on the new hash table algorithm, which, of course, is built on top of the linked list we are working on :-).

That makes a lot of sense. Re-hasing is indeed the main feature missing from rculfhash. I have ideas on how it could be introduced within the current split-ordered implementation with only small changes.

One possibility would be to create two lists (rather than one): the current list, and a second list that would be used when a re-hasing is performed. The old list would be used by readers while re-hashing is in progress, and add/del would take care of both lists when done concurrently with re-hashing. After re-hasing is complete, the old list would not be used anymore after a grace period has passed.

The cost of this approach is to have two next pointers per node (rather than one).

An alternative would be to add a temporary layer of indirection when the re-hasing is performed. The "next" pointer would actually point to an intermediate object which contains the chaining information for both the old and the new lists. This would save the cost of the additional next pointer within each node, at the expense of doing extra temporary memory allocation when doing the re-hashing.

I'd also be curious to see benchmarks of the bit-reversal compared to the rest of the operations needed for lookup, addition, and removal in a lock-free hash table for the main architectures that matter today. What architectures do you care about ?

I'm also curious to see what new hash table algorithm you have in mind!

Thanks,

Mathieu

Quoted 83 lines

Thanks,
--Junchang

Quoted 71 lines

Thanks,

Mathieu

Quoted 58 lines

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

And we made the following two major improvements:
(1) Insert, Delete, and Find operations are protected by 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 variable of 8 bytes (typically sizeof(long)) for each node.

In the past two weeks, I found some bugs in the first version of the list in building a lock-free hash table on top it. So this is the second version which fixes the known issues. Please review this version, if possible. The major changes are as follows. Sorry for the inconvenience. Any suggestions and comments are warmly welcome.

v1 -> v2:
- Functions insert(), delete(), and find() return 0 in success, and return -Exxx otherwise.
- Fix a bug in function is_removed().

Cheers,
--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/rculflist/Makefile                    |  24 ++
.../rculflist/Makefile.cds_lflist_delete_rcu       |  21 ++
.../rculflist/Makefile.cds_lflist_find_rcu         |  21 ++
.../rculflist/Makefile.cds_lflist_insert_rcu       |  21 ++
doc/examples/rculflist/cds_lflist_delete_rcu.c     | 101 ++++++++
doc/examples/rculflist/cds_lflist_find_rcu.c       |  96 +++++++
doc/examples/rculflist/cds_lflist_insert_rcu.c     |  69 +++++
include/Makefile.am                                |   1 +
include/urcu/cds.h                                 |   1 +
include/urcu/rculflist.h                           | 284 +++++++++++++++++++++
11 files changed, 646 insertions(+)

create mode 100644 doc/examples/rculflist/Makefile
create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_delete_rcu create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_find_rcu create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_insert_rcu create mode 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

Quoted 7 lines

--
1.8.3.1

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

Quoted 4 lines

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

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

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

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

#13 lore raw

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

Hi Mathieu,

Thanks a lot for the feedback. Please see below,

Quoted 2 lines · Mathieu Desnoyers

----- On Jul 30, 2019, at 9:34 AM, Junchang Wang [email protected]

Quoted 5 lines · wrote:
Quoted 5 lines
Quoted 2 lines · Mathieu Desnoyers

----- On Jul 29, 2019, at 9:35 AM, Junchang Wang [email protected]

Quoted 4 lines · wrote:
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

Hi Mathieu and the list,

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

Thanks for

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

sharing this excellent project!

In building a hash table, I am looking for an ordered singly linked

list

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

that is lock-free. It seems such a list is missing in userspace-rcu.

I

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

discussed this with Paul in the mailing list of perfbook, and he

kindly

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

suggested me to submit my implementation to userspace-rcu. So here

is the

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 1 line

RFC. Any comments and suggestions are warmly welcome.

One point worth mentioning: the rculfhash data structure (rcu

lock-free hash

Quoted 1 line
Quoted 1 line
Quoted 1 line

table) already implements such list internally. You might want to have

a look

Quoted 1 line
Quoted 1 line
Quoted 1 line

at it, and perhaps just lift out its implementation into a separate .c

file

Quoted 43 lines
Quoted 9 lines
Quoted 8 lines

and header file so we can expose its implementation publicly ?

Items are linked through the struct cds_lfht_node next field.

The struct cds_lfht_iter is used as a iterator on the list.

struct cds_lfht tbl_oder, tbl_chunk and tbl_mmap contain the linked lists heads for each memory allocation scheme.

Quoted 6 lines

Hi Mathieu,

Thanks for the note. I checked rculfhash today, and the list implementation within rculfhash is indeed quite similar to the one I'm working on. I will check to see if we can merge the two versions and provide an independent rculflist.

Great!

Quoted 6 lines
Quoted 5 lines

I'm wondering why you need to re-implement a hash table though. What is missing from rculfhash to suit your needs ?

Quoted 7 lines

The major reason is that I want a hash table that can change its hash function on-the-fly. Split-ordered list is not adequate because it can only increase/decrease the number of buckets. Besides, I doubt the reverse operation is always efficient on platforms where hardware cannot help reverse bit strings. Hence I'm working on the new hash table algorithm, which, of course, is built on top of the linked list we are working on :-).

That makes a lot of sense. Re-hasing is indeed the main feature missing from rculfhash. I have ideas on how it could be introduced within the current split-ordered implementation with only small changes.

One possibility would be to create two lists (rather than one): the current list, and a second list that would be used when a re-hasing is performed. The old list would be used by readers while re-hashing is in progress, and add/del would take care of both lists when done concurrently with re-hashing. After re-hasing is complete, the old list would not be used anymore after a grace period has passed.

Quoted 2 lines

The cost of this approach is to have two next pointers per node (rather than one).

Agree. And we need to customize a linked list to allow each node to contain two next pointers, before the hash table algorithm can use the list.

Quoted 8 lines

An alternative would be to add a temporary layer of indirection when the re-hasing is performed. The "next" pointer would actually point to an intermediate object which contains the chaining information for both the old and the new lists. This would save the cost of the additional next pointer within each node, at the expense of doing extra temporary memory allocation when doing the re-hashing.

Great suggestion! One benefit is that we may reuse a lock-free linked list without any modifications. If I understand correctly, the overall memory consumption with this approach is slightly larger than that of the previous one, because, in rehashing, each node has one intermediate node followed. Is that right?

Quoted 5 lines

I'd also be curious to see benchmarks of the bit-reversal compared to the rest of the operations needed for lookup, addition, and removal in a lock-free hash table for the main architectures that matter today. What architectures do you care about ?

Would be very happy to take a look at this and let you know the results soon. BTW, I was thinking that some architectures (e.g., x86) could have special instructions to help us accelerate the bit-reversal. Unfortunately, I searched on google today and can't find the exact instruction to do this. The most related instructions I found was at
https://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets . Do you know the x86 instructions that can reverse bit strings? Thanks.

Quoted 2 lines

I'm also curious to see what new hash table algorithm you have in mind!

I will write down the algorithm and send it to you soon.

Thanks,
--Junchang

Quoted 23 lines

Thanks,

Mathieu

Quoted 18 lines

Thanks,
--Junchang

Quoted 14 lines

Thanks,

Mathieu

Quoted 9 lines

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

And we made the following two major improvements:
(1) Insert, Delete, and Find operations are protected by RCU

read_lock,

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

such that the existence guarantees are provided by the RCU

mechanism,

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

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

pointers)

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

is required anymore.
(2) The use of the RCU mechanism can naturally prevent the ABA

problem,

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

such that no flag field is required in this implementation.

Hence,

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

we save a variable of 8 bytes (typically sizeof(long)) for each

node.

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

In the past two weeks, I found some bugs in the first version of the list in building a lock-free hash table on top it. So this is the

second

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

version which fixes the known issues. Please review this version, if possible. The major changes are as follows. Sorry for the

inconvenience.

Quoted 17 lines
Quoted 17 lines
Quoted 17 lines
Quoted 17 lines

Any suggestions and comments are warmly welcome.

v1 -> v2:
- Functions insert(), delete(), and find() return 0 in success, and return -Exxx otherwise.
- Fix a bug in function is_removed().

Cheers,
--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
Quoted 11 lines
Quoted 11 lines
Quoted 11 lines
doc/cds-api.md                                     |   7 +
doc/examples/rculflist/Makefile                    |  24 ++
.../rculflist/Makefile.cds_lflist_delete_rcu       |  21 ++
.../rculflist/Makefile.cds_lflist_find_rcu         |  21 ++
.../rculflist/Makefile.cds_lflist_insert_rcu       |  21 ++
doc/examples/rculflist/cds_lflist_delete_rcu.c     | 101 ++++++++
doc/examples/rculflist/cds_lflist_find_rcu.c       |  96 +++++++
doc/examples/rculflist/cds_lflist_insert_rcu.c     |  69 +++++
include/Makefile.am                                |   1 +
include/urcu/cds.h                                 |   1 +
include/urcu/rculflist.h                           | 284

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

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
11 files changed, 646 insertions(+)

create mode 100644 doc/examples/rculflist/Makefile create mode 100644

doc/examples/rculflist/Makefile.cds_lflist_delete_rcu

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

create mode 100644

doc/examples/rculflist/Makefile.cds_lflist_find_rcu

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

create mode 100644

doc/examples/rculflist/Makefile.cds_lflist_insert_rcu

Quoted 22 lines
Quoted 13 lines
Quoted 13 lines
Quoted 12 lines

create mode 100644 doc/examples/rculflist/cds_lflist_delete_rcu.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

--
1.8.3.1

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

Quoted 8 lines
Quoted 4 lines

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

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

Quoted 4 lines

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

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