linux-kernel - [RFC PATCH 1/3] llist: add list_add_iff_not_on

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-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20250429061211.1295443-2-shakeel.butt@linux.dev>
Date: Mon, 28 Apr 2025 23:12:07 -0700
From: Shakeel Butt <shakeel.butt@...ux.dev>
To: Tejun Heo <tj@...nel.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Alexei Starovoitov <ast@...nel.org>
Cc: Johannes Weiner <hannes@...xchg.org>,
	Michal Hocko <mhocko@...nel.org>,
	Roman Gushchin <roman.gushchin@...ux.dev>,
	Muchun Song <muchun.song@...ux.dev>,
	Yosry Ahmed <yosry.ahmed@...ux.dev>,
	Michal Koutný <mkoutny@...e.com>,
	Vlastimil Babka <vbabka@...e.cz>,
	Sebastian Andrzej Siewior <bigeasy@...utronix.de>,
	JP Kobryn <inwardvessel@...il.com>,
	bpf@...r.kernel.org,
	linux-mm@...ck.org,
	cgroups@...r.kernel.org,
	linux-kernel@...r.kernel.org,
	Meta kernel team <kernel-team@...a.com>
Subject: [RFC PATCH 1/3] llist: add list_add_iff_not_on_list()

As the name implies, list_add_iff_not_on_list() adds the given node to
the given only if the node is not on any list. Many CPUs can call this
concurrently on the same node and only one of them will succeed.

This is also useful to be used by different contexts like task, irq and
nmi. In the case of failure either the node as already present on some
list or the caller can lost the race to add the given node to a list.
That node will eventually be added to a list by the winner.

Signed-off-by: Shakeel Butt <shakeel.butt@...ux.dev>
---
 include/linux/llist.h |  3 +++
 lib/llist.c           | 30 ++++++++++++++++++++++++++++++
 2 files changed, 33 insertions(+)

diff --git a/include/linux/llist.h b/include/linux/llist.h
index 2c982ff7475a..030cfec8778b 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -236,6 +236,9 @@ static inline bool __llist_add_batch(struct llist_node *new_first,
 	return new_last->next == NULL;
 }
 
+extern bool llist_add_iff_not_on_list(struct llist_node *new,
+				      struct llist_head *head);
+
 /**
  * llist_add - add a new entry
  * @new:	new entry to be added
diff --git a/lib/llist.c b/lib/llist.c
index f21d0cfbbaaa..9d743164720f 100644
--- a/lib/llist.c
+++ b/lib/llist.c
@@ -36,6 +36,36 @@ bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
 }
 EXPORT_SYMBOL_GPL(llist_add_batch);
 
+/**
+ * llist_add_iff_not_on_list - add an entry if it is not on list
+ * @new:	entry to be added
+ * @head:	the head for your lock-less list
+ *
+ * Adds the given entry to the given list only if the entry is not on any list.
+ * This is useful for cases where multiple CPUs tries to add the same node to
+ * the list or multiple contexts (process, irq or nmi) may add the same node to
+ * the list.
+ *
+ * Return true only if the caller has successfully added the given node to the
+ * list. Returns false if entry is already on some list or if another inserter
+ * wins the race to eventually add the given node to the list.
+ */
+bool llist_add_iff_not_on_list(struct llist_node *new, struct llist_head *head)
+{
+	struct llist_node *first = READ_ONCE(head->first);
+
+	if (llist_on_list(new))
+		return false;
+
+	if (cmpxchg(&new->next, new, first) != new)
+		return false;
+
+	while (!try_cmpxchg(&head->first, &first, new))
+		new->next = first;
+	return true;
+}
+EXPORT_SYMBOL_GPL(llist_add_iff_not_on_list);
+
 /**
  * llist_del_first - delete the first entry of lock-less list
  * @head:	the head for your lock-less list
-- 
2.47.1