From: Joanne Koong <joannekoong@fb.com>
To: <bpf@vger.kernel.org>
Cc: Joanne Koong <joannekoong@fb.com>
Subject: [PATCH bpf-next 0/5] Implement bloom filter map
Date: Tue, 31 Aug 2021 15:50:00 -0700 [thread overview]
Message-ID: <20210831225005.2762202-1-joannekoong@fb.com> (raw)
This patchset adds a new kind of bpf map: the bloom filter map.
Bloom filters are a space-efficient probabilistic data structure
used to quickly test whether an element exists in a set.
In a bloom filter, false positives are possible whereas false
negatives are not.
This patchset includes benchmarks for a configurable number of hashes and
entries in the bloom filter. The benchmarks roughly show that on average,
using 3 hash functions is one of the most optimal choices. When comparing
hashmap lookups using 3 hashes in the bloom filter vs. hashmap lookups not
using a bloom filter, lookups using the bloom filter are roughly 15% faster
for 50k entries, 25% faster for 100k entries, 180% faster for 500k entries,
and 200% faster for 1 million entries.
Joanne Koong (5):
bpf: Add bloom filter map implementation
libbpf: Allow the number of hashes in bloom filter maps to be
configurable
selftests/bpf: Add bloom filter map test cases
bpf/benchs: Add benchmark test for bloom filter maps
bpf/benchs: Add benchmarks for comparing hashmap lookups with vs.
without bloom filter
include/linux/bpf.h | 3 +-
include/linux/bpf_types.h | 1 +
include/uapi/linux/bpf.h | 3 +
kernel/bpf/Makefile | 2 +-
kernel/bpf/bloom_filter.c | 171 ++++++++
kernel/bpf/syscall.c | 20 +-
kernel/bpf/verifier.c | 19 +-
tools/include/uapi/linux/bpf.h | 3 +
tools/lib/bpf/bpf.c | 2 +
tools/lib/bpf/bpf.h | 1 +
tools/lib/bpf/libbpf.c | 32 +-
tools/lib/bpf/libbpf.h | 3 +
tools/lib/bpf/libbpf.map | 2 +
tools/lib/bpf/libbpf_internal.h | 4 +-
tools/testing/selftests/bpf/Makefile | 4 +-
tools/testing/selftests/bpf/bench.c | 57 ++-
tools/testing/selftests/bpf/bench.h | 3 +
.../bpf/benchs/bench_bloom_filter_map.c | 383 ++++++++++++++++++
.../bpf/benchs/run_bench_bloom_filter_map.sh | 43 ++
.../bpf/benchs/run_bench_ringbufs.sh | 30 +-
.../selftests/bpf/benchs/run_common.sh | 60 +++
.../bpf/prog_tests/bloom_filter_map.c | 123 ++++++
.../selftests/bpf/progs/bloom_filter_map.c | 123 ++++++
23 files changed, 1048 insertions(+), 44 deletions(-)
create mode 100644 kernel/bpf/bloom_filter.c
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
create mode 100644 tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c
create mode 100644 tools/testing/selftests/bpf/progs/bloom_filter_map.c
--
2.30.2
next reply other threads:[~2021-08-31 22:50 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-08-31 22:50 Joanne Koong [this message]
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
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=20210831225005.2762202-1-joannekoong@fb.com \
--to=joannekoong@fb.com \
--cc=bpf@vger.kernel.org \
/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).