From: Yonghong Song <yhs@fb.com>
To: Alexei Starovoitov <alexei.starovoitov@gmail.com>,
Lorenz Bauer <lmb@cloudflare.com>
Cc: "bpf@vger.kernel.org" <bpf@vger.kernel.org>,
"ast@kernel.org" <ast@kernel.org>,
"daniel@iogearbox.net" <daniel@iogearbox.net>,
"joe@wand.net.nz" <joe@wand.net.nz>
Subject: Re: [PATCH bpf] bpf: improve htab_map_get_next_key behaviour during races
Date: Fri, 18 Oct 2019 20:56:58 +0000 [thread overview]
Message-ID: <28216dce-037e-036c-2716-16f898b91a27@fb.com> (raw)
In-Reply-To: <20191018160357.rq7twrwywpuc4xax@ast-mbp>
On 10/18/19 9:03 AM, Alexei Starovoitov wrote:
> On Fri, Oct 18, 2019 at 02:43:11PM +0100, Lorenz Bauer wrote:
>> To iterate a BPF map, userspace must use MAP_GET_NEXT_KEY and provide
>> the last retrieved key. The code then scans the hash table bucket
>> for the key and returns the key of the next item.
>>
>> This presents a problem if the last retrieved key isn't present in the
>> hash table anymore, e.g. due to concurrent deletion. It's not possible
>> to ascertain the location of a key in a given bucket, so there isn't
>> really a correct answer. The implementation currently returns the
>> first key in the first bucket. This guarantees that we never skip an
>> existing key. However, it means that a user space program iterating
>> a heavily modified map may never reach the end of the hash table,
>> forever restarting at the beginning.
>>
>> Fixing this outright is rather involved. However, we can improve slightly
>> by never revisiting earlier buckets. Instead of the first key in the
>> first bucket we return the first key in the "current" bucket. This
>> doesn't eliminate the problem, but makes it less likely to occur.
>>
>> Prior to commit 8fe45924387b ("bpf: map_get_next_key to return first key on NULL")
>> passing a non-existent key to MAP_GET_NEXT_KEY was the only way to
>> find the first key. Hence there is a small chance that there is code that
>> will be broken by this change.
>
> It is 100% chance that it will break older bcc tools that were written
> before NULL was possible argument for get_next_key.
The referenced bcc code is in below:
https://github.com/iovisor/bcc/blob/master/src/cc/libbpf.c#L301-L330
> Please see Yonghong's patches for batched map lookup.
This is my RFC patch.
https://lore.kernel.org/bpf/20190906225434.3635421-1-yhs@fb.com/T/#t
I have not got time to finish it as a proper patch set yet.
But hopefully soon can find some time to work on this.
> That's the proper way to solve your problem.
>
prev parent reply other threads:[~2019-10-18 20:57 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-10-18 13:43 [PATCH bpf] bpf: improve htab_map_get_next_key behaviour during races Lorenz Bauer
2019-10-18 16:03 ` Alexei Starovoitov
2019-10-18 20:56 ` Yonghong Song [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=28216dce-037e-036c-2716-16f898b91a27@fb.com \
--to=yhs@fb.com \
--cc=alexei.starovoitov@gmail.com \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=joe@wand.net.nz \
--cc=lmb@cloudflare.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox