From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
To: Yonghong Song <yhs@fb.com>
Cc: Brian Vazquez <brianvv@google.com>,
"bpf@vger.kernel.org" <bpf@vger.kernel.org>,
"netdev@vger.kernel.org" <netdev@vger.kernel.org>,
Alexei Starovoitov <ast@fb.com>,
Daniel Borkmann <daniel@iogearbox.net>,
Kernel Team <Kernel-team@fb.com>
Subject: Re: [PATCH bpf-next 05/13] bpf: adding map batch processing support
Date: Thu, 29 Aug 2019 23:58:36 -0700 [thread overview]
Message-ID: <20190830065834.nppa6xxwdjenpey2@ast-mbp.dhcp.thefacebook.com> (raw)
In-Reply-To: <2581bf69-2e35-fb10-7b84-3869286f6c85@fb.com>
On Fri, Aug 30, 2019 at 06:39:48AM +0000, Yonghong Song wrote:
> >
> > The problem happens when you are trying to do batch lookup on a
> > hashmap and when executing bpf_map_get_next_key(map, key, next_key)
> > the key is removed, then that call will return the first key and you'd
> > start iterating the map from the beginning again and retrieve
> > duplicate information.
>
> Right. Maybe we can have another bpf_map_ops callback function
> like 'map_batch_get_next_key' which won't fall back to the
> first key if the 'key' is not available in the hash table?
The reason I picked this get_next_key behavior long ago
because I couldn't come up with a way to pick the next key consistently.
In the hash table the elements are not sorted.
If there are more than one element in the hash table bucket
they are added to the link list in sort-of random order.
If one out of N elems in the bucket are deleted which one should be
picked next?
select_bucket() picks the bucket.
if lookup_nulls_elem_raw() cannot find the element which one in
the link list is the "right one" to continue?
Iterating over hash table without duplicates when elements
are being added and removed in parallel is a hard problem to solve.
I think "best effort" is the right answer.
When users care about consistency they should use map-in-map.
next prev parent reply other threads:[~2019-08-30 6:58 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-08-29 6:45 [PATCH bpf-next 00/13] bpf: adding map batch processing support Yonghong Song
2019-08-29 6:45 ` [PATCH bpf-next 01/13] bpf: add bpf_map_value_size and bp_map_copy_value helper functions Yonghong Song
2019-08-29 22:04 ` Song Liu
2019-08-30 6:40 ` Yonghong Song
2019-08-29 6:45 ` [PATCH bpf-next 02/13] bpf: refactor map_update_elem() Yonghong Song
2019-08-29 23:37 ` Song Liu
2019-08-29 6:45 ` [PATCH bpf-next 03/13] bpf: refactor map_delete_elem() Yonghong Song
2019-08-29 23:39 ` Song Liu
2019-08-29 6:45 ` [PATCH bpf-next 04/13] bpf: refactor map_get_next_key() Yonghong Song
2019-08-29 23:39 ` Song Liu
2019-08-29 6:45 ` [PATCH bpf-next 05/13] bpf: adding map batch processing support Yonghong Song
2019-08-29 23:01 ` Brian Vazquez
2019-08-30 6:39 ` Yonghong Song
2019-08-30 6:58 ` Alexei Starovoitov [this message]
2019-08-29 6:45 ` [PATCH bpf-next 06/13] tools/bpf: sync uapi header bpf.h Yonghong Song
2019-08-29 6:45 ` [PATCH bpf-next 07/13] tools/bpf: implement libbpf API functions for map batch operations Yonghong Song
2019-08-29 6:45 ` [PATCH bpf-next 08/13] tools/bpf: add test for bpf_map_update_batch() Yonghong Song
2019-08-29 6:45 ` [PATCH bpf-next 09/13] tools/bpf: add test for bpf_map_lookup_batch() Yonghong Song
2019-08-29 6:45 ` [PATCH bpf-next 10/13] tools/bpf: add test for bpf_map_lookup_and_delete_batch() Yonghong Song
2019-08-29 6:45 ` [PATCH bpf-next 11/13] tools/bpf: add test for bpf_map_delete_batch() Yonghong Song
2019-08-29 6:45 ` [PATCH bpf-next 12/13] tools/bpf: add a multithreaded test for map batch operations Yonghong Song
2019-08-29 6:45 ` [PATCH bpf-next 13/13] tools/bpf: measure map batching perf Yonghong Song
2019-08-29 18:39 ` [PATCH bpf-next 00/13] bpf: adding map batch processing support Jakub Kicinski
2019-08-29 23:13 ` Brian Vazquez
2019-08-30 0:15 ` Jakub Kicinski
2019-08-30 20:15 ` Stanislav Fomichev
2019-08-30 20:55 ` Yonghong Song
2019-08-30 21:10 ` Jakub Kicinski
2019-08-30 22:24 ` Yonghong Song
2019-08-30 21:18 ` Stanislav Fomichev
2019-09-03 21:01 ` Alexei Starovoitov
2019-09-03 22:30 ` Stanislav Fomichev
2019-09-03 23:07 ` Brian Vazquez
2019-09-04 1:35 ` Alexei Starovoitov
2019-09-03 23:07 ` Yonghong Song
2019-08-30 7:25 ` Yonghong Song
2019-08-30 21:35 ` Jakub Kicinski
2019-08-30 22:38 ` Yonghong Song
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=20190830065834.nppa6xxwdjenpey2@ast-mbp.dhcp.thefacebook.com \
--to=alexei.starovoitov@gmail.com \
--cc=Kernel-team@fb.com \
--cc=ast@fb.com \
--cc=bpf@vger.kernel.org \
--cc=brianvv@google.com \
--cc=daniel@iogearbox.net \
--cc=netdev@vger.kernel.org \
--cc=yhs@fb.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;
as well as URLs for NNTP newsgroup(s).