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  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]
Date:   Sat, 30 Mar 2019 23:41:29 -0700
From:   Brian Vazquez <brianvv.kernel@...il.com>
To:     Brian Vazquez <brianvv@...gle.com>,
        Alexei Starovoitov <ast@...nel.org>,
        "David S . Miller" <davem@...emloft.net>
Cc:     Maciej ┼╗enczykowski <maze@...gle.com>,
        linux-kernel@...r.kernel.org, netdev@...r.kernel.org
Subject: [PATCH] bpf: do not start from first bucket if elem is not found on a htab

From: Brian Vazquez <brianvv@...gle.com>

When you want to traverse an entire map using BPF_MAP_GET_NEXT_KEY and
key provided is not present due to a deletion you will start iterating the
map from the beginning without noticing it. This patch changes the
starting bucket in those situations to the bucket where key was
suppossed to be.

Note that you can still get stuck in the same bucket but it is less
likely than getting stuck in a loop restarting from the beginning of
the entire map.

Signed-off-by: Brian Vazquez <brianvv@...gle.com>
Signed-off-by: Maciej ┼╗enczykowski <maze@...gle.com>
---
 kernel/bpf/hashtab.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index fed15cf94dca6..eea046d269f51 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -611,11 +611,14 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
 
 	hash = htab_map_hash(key, key_size, htab->hashrnd);
 
-	head = select_bucket(htab, hash);
+	/* keep track of current bucket */
+	i = hash & (htab->n_buckets - 1);
+	head = select_bucket(htab, i);
 
 	/* lookup the key */
 	l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);
 
+	/* this will start looking from bucket i */
 	if (!l)
 		goto find_first_elem;
 
@@ -630,7 +633,6 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
 	}
 
 	/* no more elements in this hash list, go to the next bucket */
-	i = hash & (htab->n_buckets - 1);
 	i++;
 
 find_first_elem:
-- 
2.21.0.392.gf8f6787159e-goog

Powered by blists - more mailing lists