From: Andrii Nakryiko <email@example.com>
To: Joanne Koong <firstname.lastname@example.org>
Cc: bpf <email@example.com>, Andrii Nakryiko <firstname.lastname@example.org>,
Alexei Starovoitov <email@example.com>,
Daniel Borkmann <firstname.lastname@example.org>, Martin Lau <email@example.com>,
Kernel Team <Kernelfirstname.lastname@example.org>
Subject: Re: [PATCH v6 bpf-next 1/5] bpf: Add bloom filter map implementation
Date: Thu, 28 Oct 2021 17:44:12 -0700 [thread overview]
Message-ID: <CAEf4BzZDqn54MScowT+mwn-eqG2Y6e9sFd0u8isOoe3gXJ4ZhA@mail.gmail.com> (raw)
On Thu, Oct 28, 2021 at 5:15 PM Joanne Koong <email@example.com> wrote:
> On 10/28/21 11:15 AM, Andrii Nakryiko wrote:
> > On Wed, Oct 27, 2021 at 4:45 PM Joanne Koong <firstname.lastname@example.org> wrote:
> >> This patch adds the kernel-side changes for the implementation of
> >> a bpf bloom filter map.
> >> The bloom filter map supports peek (determining whether an element
> >> is present in the map) and push (adding an element to the map)
> >> operations.These operations are exposed to userspace applications
> >> through the already existing syscalls in the following way:
> >> BPF_MAP_LOOKUP_ELEM -> peek
> >> BPF_MAP_UPDATE_ELEM -> push
> >> The bloom filter map does not have keys, only values. In light of
> >> this, the bloom filter map's API matches that of queue stack maps:
> >> user applications use BPF_MAP_LOOKUP_ELEM/BPF_MAP_UPDATE_ELEM
> >> which correspond internally to bpf_map_peek_elem/bpf_map_push_elem,
> >> and bpf programs must use the bpf_map_peek_elem and bpf_map_push_elem
> >> APIs to query or add an element to the bloom filter map. When the
> >> bloom filter map is created, it must be created with a key_size of 0.
> >> For updates, the user will pass in the element to add to the map
> >> as the value, with a NULL key. For lookups, the user will pass in the
> >> element to query in the map as the value, with a NULL key. In the
> >> verifier layer, this requires us to modify the argument type of
> >> a bloom filter's BPF_FUNC_map_peek_elem call to ARG_PTR_TO_MAP_VALUE;
> >> as well, in the syscall layer, we need to copy over the user value
> >> so that in bpf_map_peek_elem, we know which specific value to query.
> >> A few things to please take note of:
> >> * If there are any concurrent lookups + updates, the user is
> >> responsible for synchronizing this to ensure no false negative lookups
> >> occur.
> >> * The number of hashes to use for the bloom filter is configurable from
> >> userspace. If no number is specified, the default used will be 5 hash
> >> functions. The benchmarks later in this patchset can help compare the
> >> performance of using different number of hashes on different entry
> >> sizes. In general, using more hashes decreases both the false positive
> >> rate and the speed of a lookup.
> >> * Deleting an element in the bloom filter map is not supported.
> >> * The bloom filter map may be used as an inner map.
> >> * The "max_entries" size that is specified at map creation time is used
> >> to approximate a reasonable bitmap size for the bloom filter, and is not
> >> otherwise strictly enforced. If the user wishes to insert more entries
> >> into the bloom filter than "max_entries", they may do so but they should
> >> be aware that this may lead to a higher false positive rate.
> >> Signed-off-by: Joanne Koong <email@example.com>
> >> ---
> > Don't forget to keep received Acks between revisions.
> > Acked-by: Andrii Nakryiko <firstname.lastname@example.org>
> Can you elaborate a little on how to keep received Acks between revisions?
> Should I copy and paste the "Acked-by: Andrii Nakryiko <email@example.com>"
Yes, it's all manual. See  for an example.
> line into the commit message for the patch? Or should this information be
> in the subject line of the email for the patch? Or in the patchset series'
> cover letter? Thanks!
> >> include/linux/bpf.h | 1 +
> >> include/linux/bpf_types.h | 1 +
> >> include/uapi/linux/bpf.h | 9 ++
> >> kernel/bpf/Makefile | 2 +-
> >> kernel/bpf/bloom_filter.c | 195 +++++++++++++++++++++++++++++++++
> >> kernel/bpf/syscall.c | 24 +++-
> >> kernel/bpf/verifier.c | 19 +++-
> >> tools/include/uapi/linux/bpf.h | 9 ++
> >> 8 files changed, 253 insertions(+), 7 deletions(-)
> >> create mode 100644 kernel/bpf/bloom_filter.c
> > [...]
next prev parent reply other threads:[~2021-10-29 0:44 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-10-27 23:44 [PATCH v6 bpf-next 0/5] Implement bloom filter map Joanne Koong
2021-10-27 23:45 ` [PATCH v6 bpf-next 1/5] bpf: Add bloom filter map implementation Joanne Koong
2021-10-28 18:15 ` Andrii Nakryiko
2021-10-29 0:15 ` Joanne Koong
2021-10-29 0:44 ` Andrii Nakryiko [this message]
2021-10-28 20:35 ` Alexei Starovoitov
2021-10-28 21:14 ` Martin KaFai Lau
2021-10-29 3:17 ` Joanne Koong
2021-10-29 4:49 ` Martin KaFai Lau
[not found] ` <firstname.lastname@example.org>
2021-10-29 6:40 ` Martin KaFai Lau
2021-10-27 23:45 ` [PATCH v6 bpf-next 2/5] libbpf: Add "map_extra" as a per-map-type extra flag Joanne Koong
2021-10-28 18:14 ` Andrii Nakryiko
2021-10-27 23:45 ` [PATCH v6 bpf-next 3/5] selftests/bpf: Add bloom filter map test cases Joanne Koong
2021-10-28 18:16 ` Andrii Nakryiko
2021-10-27 23:45 ` [PATCH v6 bpf-next 4/5] bpf/benchs: Add benchmark tests for bloom filter throughput + false positive Joanne Koong
2021-10-28 18:26 ` Andrii Nakryiko
2021-10-27 23:45 ` [PATCH v6 bpf-next 5/5] bpf/benchs: Add benchmarks for comparing hashmap lookups w/ vs. w/out bloom filter Joanne Koong
2021-10-28 22:10 ` [PATCH v6 bpf-next 0/5] Implement bloom filter map Martin KaFai Lau
2021-10-28 23:05 ` Alexei Starovoitov
2021-10-29 0:23 ` Joanne Koong
2021-10-29 0:30 ` Alexei Starovoitov
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:
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
* 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).