linux-kernel - Re: [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-prev] [day] [month] [year] [list]

Message-ID: <20220201214317.fbqhpgewlhqvegob@kafai-mbp.dhcp.thefacebook.com>
Date:   Tue, 1 Feb 2022 13:43:17 -0800
From:   Martin KaFai Lau <kafai@...com>
To:     Maciej Żenczykowski <zenczykowski@...il.com>
CC:     Maciej Żenczykowski <maze@...gle.com>,
        Brian Vazquez <brianvv@...gle.com>, Yonghong Song <yhs@...com>,
        Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        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: Re: [PATCH bpf-next] RFC: bpf hashmap - improve iteration in the
 presence of concurrent delete operations

On Tue, Feb 01, 2022 at 10:35:14AM -0800, Maciej Żenczykowski wrote:
> 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?
BPF_MAP_LOOKUP_BATCH has already been added to lookup in batches of buckets,
so the next bpf_map_lookup_batch will start from the beginning of
the next bucket.  Here is the details:

https://lore.kernel.org/bpf/20200115184308.162644-6-brianvv@google.com/#t