bpf: do not start from first bucket if elem is not found on a htab
Subsystems (3)
PATCH 1/1 bpf: do not start from first bucket if elem is not found on a htab
From: Brian Vazquez <[email protected]>
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.
--- kernel/bpf/hashtab.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/bpf/hashtab.c +4 -2
@@ -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:
Signature · 1 line
2.21.0.392.gf8f6787159e-goog
Daniel Borkmann
maintainerQuoted 8 lines · Brian Vazquez
From: Brian Vazquez <[email protected]>
When you want to traverse an entire map using
BPF_MAP_GET_NEXT_KEYand 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.
Quoted 6 lines
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 <[email protected]>Signed-off-by Maciej Żenczykowski <[email protected]>
This breaks BPF selftest suite unfortunately:
# ./test_maps test_maps: test_maps.c:114: test_hashmap: Assertion `bpf_map_get_next_key(fd, &key, &next_key) == 0 && (next_key == first_key)' failed. Aborted
Some more background, situation is a bit tricky: pre 8fe45924387b ("bpf:map_get_next_key to return first key on NULL") there was no reliable way of getting to the start of a hash table, meaning it needed an 'invalid' key to return the first element for starting traversal which commit fixed by being able to pass in NULL. So some applications might still just rely on e.g. key of zero bytes (if guaranteed to not be used otherwise) to do just that. With this patch, we'd start out from anywhere in the hash table.
Quoted 33 lines
--- kernel/bpf/hashtab.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)kernel/bpf/hashtab.c +4
-2@@ -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:
Quoted 6 lines
This breaks BPF selftest suite unfortunately:
# ./test_maps test_maps: test_maps.c:114: test_hashmap: Assertion `bpf_map_get_next_key(fd, &key, &next_key) == 0 && (next_key == first_key)' failed. Aborted
Quoted 7 lines
Some more background, situation is a bit tricky: pre
8fe45924387b("bpf:map_get_next_keyto return first key on NULL") there was no reliable way of getting to the start of a hash table, meaning it needed an 'invalid' key to return the first element for starting traversal which commit fixed by being able to pass in NULL. So some applications might still just rely on e.g. key of zero bytes (if guaranteed to not be used otherwise) to do just that. With this patch, we'd start out from anywhere in the hash table.
sdf@ just mentioned this internally as well... I think we simply will need to add a flags field
with at least two options/flags:
- return error if key not found
- resume from bucket instead of beginning if key not found and while we're at it:
- return concatenated key+value instead of just key to save an immediate lookup on the returned key