linux-kernel - [PATCH/RFC] llist: add llist_[add|del_first]

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <20171218154651.777fb889c34259799bef3024@gmail.com>
Date:   Mon, 18 Dec 2017 15:46:51 +0100
From:   Vitaly Wool <vitalywool@...il.com>
To:     linux-kernel@...r.kernel.org, Huang Ying <ying.huang@...el.com>
Cc:     Oleksiy.Avramchenko@...y.com
Subject: [PATCH/RFC] llist: add llist_[add|del_first]_exclusive

It sometimes is necessary to be able to be able to use llist in
the following manner:
	if (node_unlisted(node))
		llst_add(node, list);
i. e. only add a node to the list if it's not already on a list.

This is not possible without taking locks because otherwise there's
an obvious race between the check and the addition. This patch adds
the routine to add a node only if it is not on any list that is
lockless and race free as long as there's only one consumer.

That is, llist_add_exclusive would only add a node if it's not
already on a list, and llist_del_first_exclusive will delete the
first node off the list and mark it as not being on any list.

Signed-off-by: Vitaly Wool <vitaly.vul@...y.com>
---
 include/linux/llist.h | 25 +++++++++++++++++++++++++
 lib/llist.c           | 29 +++++++++++++++++++++++++++++
 2 files changed, 54 insertions(+)

diff --git a/include/linux/llist.h b/include/linux/llist.h
index 85abc29..5c60e9e 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -74,6 +74,10 @@ struct llist_node {
 #define LLIST_HEAD_INIT(name)	{ NULL }
 #define LLIST_HEAD(name)	struct llist_head name = LLIST_HEAD_INIT(name)
 
+#define LLIST_NODE_UNLISTED	((void *)(-1L))
+#define LLIST_NODE_INIT(name)	{ LLIST_NODE_UNLISTED }
+#define LLIST_NODE(name)	struct llist_node name = LLIST_NODE_INIT(name)
+
 /**
  * init_llist_head - initialize lock-less list head
  * @head:	the head for your lock-less list
@@ -238,4 +242,25 @@ extern struct llist_node *llist_del_first(struct llist_head *head);
 
 struct llist_node *llist_reverse_order(struct llist_node *head);
 
+/**
+ * llist_del_first_exclusive - delete the first entry of lock-less list
+ * 			       and make sure its ->next is NULL
+ * @head:	the head for your lock-less list
+ *
+ * If list is empty, return NULL, otherwise, return the first entry
+ * deleted, this is the newest added one.
+ *
+ */
+static inline struct llist_node *llist_del_first_exclusive(
+				struct llist_head *head)
+{
+	struct llist_node *node = llist_del_first(head);
+
+	if (READ_ONCE(node))
+		smp_store_release(&node->next, LLIST_NODE_UNLISTED);
+	return node;
+}
+
+extern bool llist_add_exclusive(struct llist_node *, struct llist_head *);
+
 #endif /* LLIST_H */
diff --git a/lib/llist.c b/lib/llist.c
index 7062e93..c85fa6b 100644
--- a/lib/llist.c
+++ b/lib/llist.c
@@ -102,3 +102,32 @@ struct llist_node *llist_reverse_order(struct llist_node *head)
 	return new_head;
 }
 EXPORT_SYMBOL_GPL(llist_reverse_order);
+
+/**
+ * llist_add_exclusive - add a node only if its ->next is NULL
+ * @node:	the node to be added
+ * @head:	the head for your lock-less list
+ *
+ * Return true if the node was added, or false otherwise.
+ */
+bool llist_add_exclusive(struct llist_node *node, struct llist_head *head)
+{
+	struct llist_node *next = LLIST_NODE_UNLISTED;
+	struct llist_node *entry, *new_next;
+
+	/*
+	 * if new_next is next (== LLIST_NODE_UNLISTED) on the first run, we
+	 * get exclusive access to this node as long as others use
+	 * llist_add_safe too.
+	 * Then false can be returned no more and we'll loop until we get the
+	 * stuff right.
+	 */
+	do {
+		entry = READ_ONCE(head->first);
+		if ((new_next = cmpxchg(&node->next, next, entry)) != next)
+			return false;
+		next = entry;
+	} while (cmpxchg(&head->first, entry, node) != entry);
+	return true;
+}
+EXPORT_SYMBOL_GPL(llist_add_exclusive);
-- 
2.7.4