Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   =?UTF-8?q?Maciej=20=C5=BBenczykowski?= <zenczykowski@gmail.com>
To:     =?UTF-8?q?Maciej=20=C5=BBenczykowski?= <maze@google.com>,
        Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>
Cc:     Linux Network Development Mailing List <netdev@vger.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
        BPF Mailing List <bpf@vger.kernel.org>,
        "David S . Miller" <davem@davemloft.net>
Subject: [PATCH bpf-next] RFC: bpf hashmap - improve iteration in the presence of concurrent delete operations
Date:   Tue,  1 Feb 2022 10:35:14 -0800
Message-Id: <20220201183514.3235495-1-zenczykowski@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Precedence: bulk

From: Maciej Żenczykowski <maze@google.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@google.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