linux-kernel - [PATCH bpf-next 2/3] bpf: Overwrite the element in hash map atomically

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: <20250204082848.13471-3-hotforest@gmail.com>
Date: Tue,  4 Feb 2025 16:28:47 +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 2/3] bpf: Overwrite the element in hash map atomically

Currently, the update of existing element in hash map involves two
steps:
1) insert the new element at the head of the hash list
2) remove the old element

It is possible that the concurrent lookup operation may fail to find
either the old element or the new element if the lookup operation starts
before the addition and continues after the removal.

Therefore, replacing the two-step update with an atomic update. After
the change, the update will be atomic in the perspective of the lookup
operation: it will either find the old element or the new element.

Signed-off-by: Hou Tao <hotforest@...il.com>
---
 kernel/bpf/hashtab.c | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 4a9eeb7aef85..a28b11ce74c6 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -1179,12 +1179,14 @@ static long htab_map_update_elem(struct bpf_map *map, void *key, void *value,
 		goto err;
 	}
 
-	/* add new element to the head of the list, so that
-	 * concurrent search will find it before old elem
-	 */
-	hlist_nulls_add_head_rcu(&l_new->hash_node, head);
-	if (l_old) {
-		hlist_nulls_del_rcu(&l_old->hash_node);
+	if (!l_old) {
+		hlist_nulls_add_head_rcu(&l_new->hash_node, head);
+	} else {
+		/* Replace the old element atomically, so that
+		 * concurrent search will find either the new element or
+		 * the old element.
+		 */
+		hlist_nulls_replace_rcu(&l_new->hash_node, &l_old->hash_node);
 
 		/* l_old has already been stashed in htab->extra_elems, free
 		 * its special fields before it is available for reuse. Also
-- 
2.48.1