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
