linux-kernel - [PATCH bpf-next 1/3] rculist: add hlist_nulls_replace

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 for Android: free password hash cracker in your pocket

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

Message-ID: <20250204082848.13471-2-hotforest@gmail.com>
Date: Tue,  4 Feb 2025 16:28:46 +0800
From: Hou Tao <hotforest@...il.com>
To: bpf@...r.kernel.org,
	rcu@...r.kernel.org
Cc: linux-kernel@...r.kernel.org,
	Alexei Starovoitov <ast@...nel.org>,
	Daniel Borkmann <daniel@...earbox.net>,
	Andrii Nakryiko <andrii@...nel.org>,
	Martin KaFai Lau <martin.lau@...ux.dev>,
	Eduard Zingerman <eddyz87@...il.com>,
	Song Liu <song@...nel.org>,
	Yonghong Song <yonghong.song@...ux.dev>,
	John Fastabend <john.fastabend@...il.com>,
	KP Singh <kpsingh@...nel.org>,
	Stanislav Fomichev <sdf@...ichev.me>,
	Hao Luo <haoluo@...gle.com>,
	Jiri Olsa <jolsa@...nel.org>,
	"Paul E . McKenney" <paulmck@...nel.org>,
	houtao1@...wei.com,
	hotforest@...il.com
Subject: [PATCH bpf-next 1/3] rculist: add hlist_nulls_replace_rcu() helper

Add hlist_nulls_replace_rcu() to replace an existing element in the hash
list. For the concurrent list traversal, the replace is atomic, it will
find either the old element or the new element.

Signed-off-by: Hou Tao <hotforest@...il.com>
---
 include/linux/rculist_nulls.h | 42 +++++++++++++++++++++++++++++++++++
 1 file changed, 42 insertions(+)

diff --git a/include/linux/rculist_nulls.h b/include/linux/rculist_nulls.h
index 89186c499dd4..795071fda6ad 100644
--- a/include/linux/rculist_nulls.h
+++ b/include/linux/rculist_nulls.h
@@ -52,6 +52,14 @@ static inline void hlist_nulls_del_init_rcu(struct hlist_nulls_node *n)
 #define hlist_nulls_next_rcu(node) \
 	(*((struct hlist_nulls_node __rcu __force **)&(node)->next))
 
+
+/**
+ * hlist_nulls_pprev_rcu - returns the element of the list before @node.
+ * @node: element of the list.
+ */
+#define hlist_nulls_pprev_rcu(node) \
+	(*((struct hlist_nulls_node __rcu __force **)(node)->pprev))
+
 /**
  * hlist_nulls_del_rcu - deletes entry from hash list without re-initialization
  * @n: the element to delete from the hash list.
@@ -145,6 +153,40 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
 	}
 }
 
+/**
+ * hlist_nulls_replace_rcu - replace an element in hash list
+ * @n: new element to add
+ * @o: old element to replace
+ *
+ * Description:
+ * Replace an existing element in a hash list with a new one,
+ * while permitting racing traversals.
+ *
+ * The caller must take whatever precautions are necessary
+ * (such as holding appropriate locks) to avoid racing
+ * with another list-mutation primitive, such as hlist_nulls_add_head_rcu()
+ * or hlist_nulls_del_rcu(), running on this same list.
+ * However, it is perfectly legal to run concurrently with
+ * the _rcu list-traversal primitives, such as
+ * hlist_nulls_for_each_entry_rcu(), used to prevent memory-consistency
+ * problems on Alpha CPUs.  Regardless of the type of CPU, the
+ * list-traversal primitive must be guarded by rcu_read_lock().
+ */
+static inline void hlist_nulls_replace_rcu(struct hlist_nulls_node *n,
+					   struct hlist_nulls_node *o)
+{
+	struct hlist_nulls_node *next = o->next;
+	struct hlist_nulls_node **pprev = o->pprev;
+
+	WRITE_ONCE(n->next, next);
+	WRITE_ONCE(n->pprev, pprev);
+	rcu_assign_pointer(hlist_nulls_pprev_rcu(o), n);
+
+	if (!is_a_nulls(next))
+		WRITE_ONCE(next->pprev, &n->next);
+	WRITE_ONCE(o->pprev, LIST_POISON2);
+}
+
 /* after that hlist_nulls_del will work */
 static inline void hlist_nulls_add_fake(struct hlist_nulls_node *n)
 {
-- 
2.48.1