linux-kernel - [PATCH bpf-next] RFC: bpf hashmap - improve iteration in the presence of concurrent delete operations

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: <20220201183514.3235495-1-zenczykowski@gmail.com>
Date:   Tue,  1 Feb 2022 10:35:14 -0800
From:   Maciej Żenczykowski <zenczykowski@...il.com>
To:     Maciej Żenczykowski <maze@...gle.com>,
        Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>
Cc:     Linux Network Development Mailing List <netdev@...r.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        BPF Mailing List <bpf@...r.kernel.org>,
        "David S . Miller" <davem@...emloft.net>
Subject: [PATCH bpf-next] RFC: bpf hashmap - improve iteration in the presence of concurrent delete operations

From: Maciej Żenczykowski <maze@...gle.com>

by resuming from the bucket the key would be in if it still existed

Note: AFAICT this an API change that would require some sort of guard...

bpf map iteration was added all the way back in v3.18-rc4-939-g0f8e4bd8a1fc
but behaviour of find first key with NULL was only done in v4.11-rc7-2042-g8fe45924387b
(before that you'd get EFAULT)

this means previously find first key was done by calling with a non existing key
(AFAICT this was hoping to get lucky, since if your non existing key actually existed,
it wouldn't actually iterate right, since you couldn't guarantee your magic value was
the first one)

ie. do we need a BPF_MAP_GET_NEXT_KEY2 or a sysctl? some other approach?

Not-Signed-off-by-Yet: Maciej Żenczykowski <maze@...gle.com>
---
 kernel/bpf/hashtab.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index d29af9988f37..0d61a9a54279 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -780,7 +780,7 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
 	key_size = map->key_size;
 
 	if (!key)
-		goto find_first_elem;
+		goto find_first_elem_this_bucket;
 
 	hash = htab_map_hash(key, key_size, htab->hashrnd);
 
@@ -790,7 +790,7 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
 	l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);
 
 	if (!l)
-		goto find_first_elem;
+		goto find_first_elem_next_bucket;
 
 	/* key was found, get next key in the same bucket */
 	next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_next_rcu(&l->hash_node)),
@@ -802,11 +802,12 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
 		return 0;
 	}
 
+find_first_elem_next_bucket:
 	/* no more elements in this hash list, go to the next bucket */
 	i = hash & (htab->n_buckets - 1);
 	i++;
 
-find_first_elem:
+find_first_elem_this_bucket:
 	/* iterate over buckets */
 	for (; i < htab->n_buckets; i++) {
 		head = select_bucket(htab, i);
-- 
2.35.0.rc2.247.g8bbb082509-goog