netdev - Re: [PATCH] bpf: do not start from first bucket if elem is not found on a htab

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]

Date:   Mon, 1 Apr 2019 23:34:00 +0200
From:   Daniel Borkmann <daniel@...earbox.net>
To:     Brian Vazquez <brianvv.kernel@...il.com>,
        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: Re: [PATCH] bpf: do not start from first bucket if elem is not found
 on a htab

On 03/31/2019 08:41 AM, Brian Vazquez wrote:
> 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>

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.

> ---
>  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:
>