From: Andrii Nakryiko <andrii.nakryiko@gmail.com>
To: Joanne Koong <joannekoong@fb.com>
Cc: bpf <bpf@vger.kernel.org>
Subject: Re: [PATCH bpf-next 4/5] bpf/benchs: Add benchmark test for bloom filter maps
Date: Wed, 1 Sep 2021 20:35:10 -0700 [thread overview]
Message-ID: <CAEf4BzbMAogriaief+EOhVXXbon2y=KmN_JaYcMk_LVj3tCk1w@mail.gmail.com> (raw)
In-Reply-To: <20210831225005.2762202-5-joannekoong@fb.com>
On Tue, Aug 31, 2021 at 3:52 PM Joanne Koong <joannekoong@fb.com> wrote:
>
> This patch adds benchmark tests for the throughput and false positive
> rate of bloom filter map lookups for a given number of entries and a
> given number of hash functions.
>
> These benchmarks show that as the number of hash functions increases,
> the throughput and the false positive rate of the bloom filter map
> decreases. From the benchmark data, the approximate average
> false-positive rates are roughly as follows:
>
> 1 hash function = ~30%
> 2 hash functions = ~15%
> 3 hash functions = ~5%
> 4 hash functions = ~2.5%
> 5 hash functions = ~1%
> 6 hash functions = 0.5%
> 7 hash functions = ~0.35%
> 8 hash functions = ~0.15%
> 9 hash functions = ~0.1%
> 10 hash functions = ~0%
>
> Signed-off-by: Joanne Koong <joannekoong@fb.com>
> ---
> tools/testing/selftests/bpf/Makefile | 4 +-
> tools/testing/selftests/bpf/bench.c | 35 ++
> tools/testing/selftests/bpf/bench.h | 3 +
> .../bpf/benchs/bench_bloom_filter_map.c | 344 ++++++++++++++++++
> .../bpf/benchs/run_bench_bloom_filter_map.sh | 28 ++
> .../bpf/benchs/run_bench_ringbufs.sh | 30 +-
> .../selftests/bpf/benchs/run_common.sh | 48 +++
> .../selftests/bpf/progs/bloom_filter_map.c | 74 ++++
> 8 files changed, 537 insertions(+), 29 deletions(-)
> create mode 100644 tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c
> create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh
> create mode 100644 tools/testing/selftests/bpf/benchs/run_common.sh
>
[...]
> diff --git a/tools/testing/selftests/bpf/progs/bloom_filter_map.c b/tools/testing/selftests/bpf/progs/bloom_filter_map.c
> index 2d9c43a30246..1b139689219e 100644
> --- a/tools/testing/selftests/bpf/progs/bloom_filter_map.c
> +++ b/tools/testing/selftests/bpf/progs/bloom_filter_map.c
> @@ -1,7 +1,9 @@
> // SPDX-License-Identifier: GPL-3.0
> /* Copyright (c) 2021 Facebook */
>
> +#include <errno.h>
> #include <linux/bpf.h>
> +#include <stdbool.h>
> #include <bpf/bpf_helpers.h>
>
> char _license[] SEC("license") = "GPL";
> @@ -23,8 +25,38 @@ struct {
> __uint(nr_hashes, 2);
> } map_bloom_filter SEC(".maps");
>
> +/* Tracks the number of hits, drops, and false hits */
> +struct {
> + __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
> + __uint(max_entries, 3);
> + __type(key, __u32);
> + __type(value, __u64);
> +} percpu_array SEC(".maps");
> +
> +struct {
> + __uint(type, BPF_MAP_TYPE_HASH);
> + __uint(max_entries, 1000);
> + __type(key, __u64);
> + __type(value, __u64);
> +} hashmap SEC(".maps");
> +
> +const __u32 hit_key = 0;
> +const __u32 drop_key = 1;
> +const __u32 false_hit_key = 2;
> +
> +bool hashmap_use_bloom_filter = true;
> +
> int error = 0;
>
> +static __always_inline void log_result(__u32 key)
> +{
> + __u64 *count;
> +
> + count = bpf_map_lookup_elem(&percpu_array, &key);
> + if (count)
> + *count += 1;
it will be actually more performant to have a global array with some
fixed number of elements (e.g., 256, to support up to 256 CPUs), one
for each CPU, instead of BPF_MAP_TYPE_PERCPU_ARRAY. Don't know how
much impact that has on benchmark, but doing one extra per-cpu map
lookup for each Bloom filter lookup might be a significant portion of
spent CPU.
> +}
> +
> static __u64
> check_elem(struct bpf_map *map, __u32 *key, __u64 *val,
> void *data)
> @@ -37,6 +69,8 @@ check_elem(struct bpf_map *map, __u32 *key, __u64 *val,
> return 1; /* stop the iteration */
> }
>
> + log_result(hit_key);
> +
> return 0;
> }
>
> @@ -47,3 +81,43 @@ int prog_bloom_filter(void *ctx)
>
> return 0;
> }
> +
> +SEC("fentry/__x64_sys_getpgid")
> +int prog_bloom_filter_hashmap_lookup(void *ctx)
> +{
> + __u64 *result;
> + int i, err;
> +
> + union {
> + __u64 data64;
> + __u32 data32[2];
> + } val;
> +
> + for (i = 0; i < 512; i++) {
> + val.data32[0] = bpf_get_prandom_u32();
> + val.data32[1] = bpf_get_prandom_u32();
> +
> + if (hashmap_use_bloom_filter) {
> + err = bpf_map_peek_elem(&map_bloom_filter, &val);
> + if (err) {
> + if (err != -ENOENT) {
> + error |= 2;
> + return 0;
> + }
> + log_result(drop_key);
> + continue;
> + }
> + }
> +
> + result = bpf_map_lookup_elem(&hashmap, &val);
> + if (result) {
> + log_result(hit_key);
> + } else {
> + if (hashmap_use_bloom_filter)
> + log_result(false_hit_key);
> + log_result(drop_key);
> + }
> + }
> +
> + return 0;
> +}
> --
> 2.30.2
>
next prev parent reply other threads:[~2021-09-02 3:35 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-08-31 22:50 [PATCH bpf-next 0/5] Implement bloom filter map Joanne Koong
2021-08-31 22:50 ` [PATCH bpf-next 1/5] bpf: Add bloom filter map implementation Joanne Koong
2021-09-01 2:55 ` Alexei Starovoitov
2021-09-02 19:11 ` Joanne Koong
2021-09-02 1:44 ` Andrii Nakryiko
2021-09-02 5:11 ` John Fastabend
2021-09-02 6:16 ` Martin KaFai Lau
2021-09-02 22:07 ` Joanne Koong
2021-09-03 0:56 ` Martin KaFai Lau
2021-09-03 7:13 ` Joanne Koong
2021-09-03 17:19 ` Andrii Nakryiko
2021-09-03 17:22 ` John Fastabend
2021-09-08 19:10 ` Joanne Koong
2021-09-02 3:16 ` John Fastabend
2021-09-02 3:28 ` Andrii Nakryiko
2021-09-02 4:40 ` John Fastabend
2021-08-31 22:50 ` [PATCH bpf-next 2/5] libbpf: Allow the number of hashes in bloom filter maps to be configurable Joanne Koong
2021-09-02 3:30 ` Andrii Nakryiko
2021-08-31 22:50 ` [PATCH bpf-next 3/5] selftests/bpf: Add bloom filter map test cases Joanne Koong
2021-09-01 2:55 ` Alexei Starovoitov
2021-08-31 22:50 ` [PATCH bpf-next 4/5] bpf/benchs: Add benchmark test for bloom filter maps Joanne Koong
2021-09-02 3:35 ` Andrii Nakryiko [this message]
2021-08-31 22:50 ` [PATCH bpf-next 5/5] bpf/benchs: Add benchmarks for comparing hashmap lookups with vs. without bloom filter Joanne Koong
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='CAEf4BzbMAogriaief+EOhVXXbon2y=KmN_JaYcMk_LVj3tCk1w@mail.gmail.com' \
--to=andrii.nakryiko@gmail.com \
--cc=bpf@vger.kernel.org \
--cc=joannekoong@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).