| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <1313503666-13726-2-git-send-email-schnhrr@cs.tu-berlin.de>
Date: Tue, 16 Aug 2011 16:07:45 +0200
From: Jan H. Schönherr <schnhrr@...tu-berlin.de>
To: Ingo Molnar <mingo@...e.hu>, Peter Zijlstra <peterz@...radead.org>
Cc: Paul Turner <pjt@...gle.com>, Dipankar Sarma <dipankar@...ibm.com>,
"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
linux-kernel@...r.kernel.org,
Jan H. Schönherr <schnhrr@...tu-berlin.de>
Subject: [PATCH v3 1/2] rcu: More rcu-variants for list manipulation
From: Jan H. Schönherr <schnhrr@...tu-berlin.de>
This commit introduces __list_link() and some more *_rcu variants of some
list manipulation functions:
* __list_link()
Takes two list elements and link them via their next/prev pointers.
* __list_link_rcu()
RCU-aware counterpart to __list_link().
* __list_splice_rcu(), list_splice_tail_init_rcu()
RCU-aware non-blocking splicing.
The existing rcu-splice function allows concurrent readers on the
list to be spliced that are not from the destination list. Therefore,
it has to block to get these readers off the list before the splicing
can be done. The new functions forbid this and can, thus, work without
blocking.
Signed-off-by: Jan H. Schönherr <schnhrr@...tu-berlin.de>
---
Changes since v2:
- merged __list_link() from a dropped patch
- dropped list_add_tail_nobackref() again
Changes since v1:
- added comments
- added list_add_tail_nobackref()
---
include/linux/list.h | 12 +++++++
include/linux/rculist.h | 74 +++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 86 insertions(+), 0 deletions(-)
diff --git a/include/linux/list.h b/include/linux/list.h
index cc6d2aa..0a7b057 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -21,6 +21,18 @@
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
+/*
+ * Link two list entries by making the prev/next entries
+ * point to each other.
+ *
+ * This is only for internal list manipulation.
+ */
+static inline void __list_link(struct list_head *prev, struct list_head *next)
+{
+ next->prev = prev;
+ prev->next = next;
+}
+
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
diff --git a/include/linux/rculist.h b/include/linux/rculist.h
index d079290..a9be1e0 100644
--- a/include/linux/rculist.h
+++ b/include/linux/rculist.h
@@ -25,6 +25,29 @@
#define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
/*
+ * Link two list entries by making the prev/next entries
+ * point to each other.
+ *
+ * The next pointer of @prev is assigned RCU-aware. So, this
+ * function is primarily intended to publish new nodes starting
+ * at @next within the RCU-protected list @prev.
+ *
+ * This is only for internal list manipulation, when everything
+ * else, i. e. a link from the nodes given by @next back to the
+ * list of @prev, is already set up.
+ *
+ * Concurrent readers are basically allowed, concurrent writers
+ * are forbidden.
+ */
+static inline void __list_link_rcu(struct list_head *prev,
+ struct list_head *next)
+{
+ rcu_assign_pointer(list_next_rcu(prev), next);
+ next->prev = prev;
+}
+
+
+/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
@@ -158,6 +181,57 @@ static inline void list_replace_rcu(struct list_head *old,
old->prev = LIST_POISON2;
}
+/*
+ * Low level function for splicing.
+ *
+ * @prev and @next must point into the same RCU-protected list.
+ *
+ * All elements between (not including) @prev and @next are replaced
+ * by the nodes given by @list.
+ *
+ * It is safe to have concurrent readers of the @prev/@...t list
+ * on any of the referenced nodes. There must be no reader not
+ * from @prev/@...t within @list.
+ * There must be no concurrent writers on @list or @prev/@...t.
+ *
+ * This is only for internal list manipulation. If elements of
+ * @prev/@...t are deleted, their prev-pointers are not poisoned.
+ */
+static inline void __list_splice_rcu(struct list_head *list,
+ struct list_head *prev,
+ struct list_head *next)
+{
+ /* Prepare link back to @prev/@...t */
+ __list_link(list->prev, next);
+
+ /*
+ * Publish new nodes, implicitly deleting everything between
+ * @prev and @next.
+ */
+ __list_link_rcu(prev, list->next);
+}
+
+/**
+ * list_splice_tail_init_rcu - splice a list into a RCU-protected list
+ * @list: the list to be spliced
+ * @head: the RCU-protected list to splice into
+ *
+ * The contents of @list are inserted before @head. After completion
+ * @list is empty.
+ *
+ * It is safe to have concurrent readers of @head. There must be no
+ * concurrent readers not from @head on @list.
+ * There must be no concurrent writers on @list or @head.
+ */
+static inline void list_splice_tail_init_rcu(struct list_head *list,
+ struct list_head *head)
+{
+ if (!list_empty(list)) {
+ __list_splice_rcu(list, head->prev, head);
+ INIT_LIST_HEAD(list);
+ }
+}
+
/**
* list_splice_init_rcu - splice an RCU-protected list into an existing list.
* @list: the RCU-protected list to splice
--
1.7.6
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists