bpf_jhash_mem() and BPF Bloom filter implementation
Subsystems (3)
Andrii Nakryiko
maintainercover bpf_jhash_mem() and BPF Bloom filter implementation
This is a quick experiment on adding a hashing helper and buliding Bloom filter with pure BPF code with no extra kernel functionality (beyond generic hashing helper).
This is based on top of Joanne's series [0].
Patch 1 adds bpf_jhash_mem() helper. Patch 2 fixes existing benchmark to report valid and consistent benchmark results and reduce amount of overhead that stats counting itself causes. Patch 3 contains BPF-side implementation of Bloom filter based on global variables. Patch 4 completes the integration on user-space side. I split patch 3 and 4 to not distract from BPF-side changes.
Note that "Hashmap without bloom filter vs. hashmap with bloom filter" benchmark is still spending lots of time in just generating random values on BPF side, and it would be nice to optimize that and make it more reproducible to compare different implementations. But I ran out of steam for doing that, especially that I'm not sure this changes anything.
The same benchmark also checks only short 8-byte keys, which is a valid use case, but not the only probably one, so would be nice to have that extended as well.
For reference, here are full benchmark results comparing in-kernel Bloom filter and custom BPF-implemented Bloom filter. I shortened the set of different combinations tested to reduce amount of time to wait for results.
The results for "Hashmap without bloom filter vs. hashmap with bloom filter" are quite confusing, though. I spent a bit of time to try to find discrepancies. I confirmed that both implementations function correctly and match 100% of time in terms of positives/negatives. Pure Bloom filter reading benchmarks show a pretty small gap in performance with custom BPF implementation losing. The "Hashmap without bloom filter vs. hashmap with bloom filter" benchmark shows much bigger difference, though, which I wasn't able to completely explain, to be entirely honest.
It's probably worth spending some more time investigating this, but I ran out of self-alloted time for this.
Bloom filter map
================
# threads: 1, # hashes: 1
10,000 entries -
Total operations: 50.854 ± 0.134M/s (drops 0.000 ± 0.000M/s)
False positive rate: 31.36%
[CUSTOM] Total operations: 49.391 ± 0.123M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 31.37%
100,000 entries -
Total operations: 50.969 ± 0.049M/s (drops 0.000 ± 0.000M/s)
False positive rate: 24.04%
[CUSTOM] Total operations: 49.135 ± 1.579M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 24.04%
1,000,000 entries -
Total operations: 48.474 ± 1.619M/s (drops 0.000 ± 0.000M/s)
False positive rate: 27.50%
[CUSTOM] Total operations: 46.088 ± 0.776M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 27.50%
# threads: 1, # hashes: 310,000 entries -
Total operations: 25.136 ± 0.011M/s (drops 0.000 ± 0.000M/s)
False positive rate: 4.71%
[CUSTOM] Total operations: 24.115 ± 0.014M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 4.77%
100,000 entries -
Total operations: 25.045 ± 0.120M/s (drops 0.000 ± 0.000M/s)
False positive rate: 7.67%
[CUSTOM] Total operations: 23.028 ± 0.042M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 7.65%
1,000,000 entries -
Total operations: 18.712 ± 0.406M/s (drops 0.000 ± 0.000M/s)
False positive rate: 2.64%
[CUSTOM] Total operations: 18.100 ± 0.422M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 2.64%
# threads: 1, # hashes: 510,000 entries -
Total operations: 16.672 ± 0.011M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.32%
[CUSTOM] Total operations: 15.318 ± 0.014M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.32%
100,000 entries -
Total operations: 16.540 ± 0.121M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.78%
[CUSTOM] Total operations: 15.189 ± 0.045M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.78%
1,000,000 entries -
Total operations: 11.781 ± 0.192M/s (drops 0.000 ± 0.000M/s)
False positive rate: 1.79%
[CUSTOM] Total operations: 11.651 ± 0.012M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 1.79%
# threads: 1, # hashes: 1010,000 entries -
Total operations: 9.038 ± 0.052M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.00%
[CUSTOM] Total operations: 8.620 ± 0.008M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.00%
100,000 entries -
Total operations: 8.076 ± 0.027M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.01%
[CUSTOM] Total operations: 7.261 ± 0.007M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.01%
1,000,000 entries -
Total operations: 6.263 ± 0.041M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.03%
[CUSTOM] Total operations: 6.173 ± 0.013M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 0.03%
# threads: 4, # hashes: 110,000 entries -
Total operations: 203.453 ± 0.161M/s (drops 0.000 ± 0.000M/s)
False positive rate: 31.28%
[CUSTOM] Total operations: 197.959 ± 0.051M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 31.34%
100,000 entries -
Total operations: 203.887 ± 0.155M/s (drops 0.000 ± 0.000M/s)
False positive rate: 24.07%
[CUSTOM] Total operations: 197.476 ± 1.796M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 24.09%
1,000,000 entries -
Total operations: 189.259 ± 0.473M/s (drops 0.000 ± 0.000M/s)
False positive rate: 27.50%
[CUSTOM] Total operations: 185.157 ± 0.346M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 27.48%
# threads: 4, # hashes: 310,000 entries -
Total operations: 100.394 ± 0.062M/s (drops 0.000 ± 0.000M/s)
False positive rate: 4.76%
[CUSTOM] Total operations: 93.896 ± 0.104M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 4.75%
100,000 entries -
Total operations: 100.382 ± 0.155M/s (drops 0.000 ± 0.000M/s)
False positive rate: 7.62%
[CUSTOM] Total operations: 93.460 ± 0.145M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 7.65%
1,000,000 entries -
Total operations: 71.424 ± 0.710M/s (drops 0.000 ± 0.000M/s)
False positive rate: 2.65%
[CUSTOM] Total operations: 72.546 ± 0.228M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 2.65%
# threads: 4, # hashes: 510,000 entries -
Total operations: 66.652 ± 0.116M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.32%
[CUSTOM] Total operations: 60.790 ± 0.454M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.33%
100,000 entries -
Total operations: 66.401 ± 0.090M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.78%
[CUSTOM] Total operations: 61.066 ± 0.069M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.77%
1,000,000 entries -
Total operations: 48.299 ± 0.369M/s (drops 0.000 ± 0.000M/s)
False positive rate: 1.79%
[CUSTOM] Total operations: 47.401 ± 0.347M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 1.79%
# threads: 4, # hashes: 1010,000 entries -
Total operations: 36.273 ± 0.030M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.00%
[CUSTOM] Total operations: 34.464 ± 0.073M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.00%
100,000 entries -
Total operations: 32.525 ± 0.047M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.01%
[CUSTOM] Total operations: 29.516 ± 0.110M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.01%
1,000,000 entries -
Total operations: 25.515 ± 0.405M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.03%
[CUSTOM] Total operations: 24.566 ± 0.189M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 0.03%
# threads: 8, # hashes: 110,000 entries -
Total operations: 406.129 ± 2.262M/s (drops 0.000 ± 0.000M/s)
False positive rate: 31.45%
[CUSTOM] Total operations: 384.758 ± 0.379M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 31.24%
100,000 entries -
Total operations: 407.817 ± 0.793M/s (drops 0.000 ± 0.000M/s)
False positive rate: 24.05%
[CUSTOM] Total operations: 394.745 ± 1.302M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 24.05%
1,000,000 entries -
Total operations: 383.159 ± 0.289M/s (drops 0.000 ± 0.000M/s)
False positive rate: 27.49%
[CUSTOM] Total operations: 371.173 ± 0.454M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 27.49%
# threads: 8, # hashes: 310,000 entries -
Total operations: 201.079 ± 0.183M/s (drops 0.000 ± 0.000M/s)
False positive rate: 4.69%
[CUSTOM] Total operations: 187.658 ± 0.544M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 4.74%
100,000 entries -
Total operations: 199.826 ± 0.972M/s (drops 0.000 ± 0.000M/s)
False positive rate: 7.63%
[CUSTOM] Total operations: 185.415 ± 0.358M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 7.62%
1,000,000 entries -
Total operations: 148.589 ± 1.320M/s (drops 0.000 ± 0.000M/s)
False positive rate: 2.65%
[CUSTOM] Total operations: 142.591 ± 4.825M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 2.64%
# threads: 8, # hashes: 510,000 entries -
Total operations: 133.306 ± 0.468M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.32%
[CUSTOM] Total operations: 127.377 ± 0.271M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.32%
100,000 entries -
Total operations: 132.915 ± 0.364M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.78%
[CUSTOM] Total operations: 123.722 ± 3.169M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.77%
1,000,000 entries -
Total operations: 94.803 ± 3.240M/s (drops 0.000 ± 0.000M/s)
False positive rate: 1.79%
[CUSTOM] Total operations: 95.670 ± 2.624M/s (drops 0.000 ± 0.000M/s)
[CUSTOM] False positive rate: 1.79%
# threads: 8, # hashes: 1010,000 entries -
Total operations: 72.517 ± 0.083M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.00%
[CUSTOM] Total operations: 65.803 ± 0.069M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.00%
100,000 entries -
Total operations: 65.533 ± 0.148M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.01%
[CUSTOM] Total operations: 59.908 ± 2.841M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.01%
1,000,000 entries -
Total operations: 50.937 ± 0.105M/s (drops 0.000 ± 0.000M/s)
False positive rate: 0.03%
[CUSTOM] Total operations: 47.526 ± 1.044M/s (drops 0.000 ± 0.000M/s) [CUSTOM] False positive rate: 0.03%
Hashmap without bloom filter vs. hashmap with bloom filter (throughput, 8 threads)
==================================================================================
# hashes: 1
10,000 entries -
Hashmap without bloom filter: 123.919 ± 0.458M/s
Hashmap with bloom filter: 124.588 ± 0.450M/s
[CUSTOM] Hashmap with bloom filter: 106.838 ± 0.114M/s
100,000 entries -
Hashmap without bloom filter: 93.708 ± 0.715M/s
Hashmap with bloom filter: 131.686 ± 1.272M/s
[CUSTOM] Hashmap with bloom filter: 105.649 ± 0.278M/s
1,000,000 entries -
Hashmap without bloom filter: 40.040 ± 0.677M/s
Hashmap with bloom filter: 67.250 ± 0.506M/s
[CUSTOM] Hashmap with bloom filter: 58.356 ± 0.541M/s
# hashes: 3
10,000 entries -
Hashmap without bloom filter: 123.882 ± 0.077M/s
Hashmap with bloom filter: 152.423 ± 0.061M/s
[CUSTOM] Hashmap with bloom filter: 126.021 ± 0.115M/s
100,000 entries -
Hashmap without bloom filter: 94.291 ± 0.986M/s
Hashmap with bloom filter: 127.944 ± 0.825M/s
[CUSTOM] Hashmap with bloom filter: 106.943 ± 0.827M/s
1,000,000 entries -
Hashmap without bloom filter: 40.183 ± 0.382M/s
Hashmap with bloom filter: 125.224 ± 0.266M/s
[CUSTOM] Hashmap with bloom filter: 89.717 ± 0.158M/s
# hashes: 5
10,000 entries -
Hashmap without bloom filter: 120.510 ± 0.351M/s
Hashmap with bloom filter: 170.138 ± 0.088M/s
[CUSTOM] Hashmap with bloom filter: 136.006 ± 0.324M/s
100,000 entries -
Hashmap without bloom filter: 94.774 ± 0.191M/s
Hashmap with bloom filter: 145.559 ± 0.687M/s
[CUSTOM] Hashmap with bloom filter: 117.073 ± 0.382M/s
1,000,000 entries -
Hashmap without bloom filter: 40.004 ± 0.492M/s
Hashmap with bloom filter: 96.916 ± 0.148M/s
[CUSTOM] Hashmap with bloom filter: 78.485 ± 0.289M/s
# hashes: 10
10,000 entries -
Hashmap without bloom filter: 124.034 ± 0.245M/s
Hashmap with bloom filter: 169.757 ± 0.336M/s
[CUSTOM] Hashmap with bloom filter: 134.634 ± 0.276M/s
100,000 entries -
Hashmap without bloom filter: 94.872 ± 0.195M/s
Hashmap with bloom filter: 141.107 ± 0.780M/s
[CUSTOM] Hashmap with bloom filter: 109.279 ± 0.330M/s
1,000,000 entries -
Hashmap without bloom filter: 40.215 ± 0.396M/s
Hashmap with bloom filter: 98.084 ± 0.267M/s
[CUSTOM] Hashmap with bloom filter: 78.579 ± 0.046M/s[0] https://patchwork.kernel.org/project/netdevbpf/list/?series=550585&state=*
Andrii Nakryiko (4):
bpf: add bpf_jhash_mem BPF helper
selftests/bpf: fix and optimize bloom filter bench selftests/bpf: implement custom Bloom filter purely in BPF selftests/bpf: integrate custom Bloom filter impl into benchs
include/uapi/linux/bpf.h | 8 + kernel/bpf/helpers.c | 23 +++ tools/include/uapi/linux/bpf.h | 8 + tools/testing/selftests/bpf/Makefile | 2 +- tools/testing/selftests/bpf/bench.c | 6 + .../bpf/benchs/bench_bloom_filter_map.c | 153 +++++++++++++++++- .../bpf/benchs/run_bench_bloom_filter_map.sh | 22 +-- .../selftests/bpf/benchs/run_common.sh | 2 +- .../selftests/bpf/progs/bloom_filter_map.c | 125 ++++++++++++-- 9 files changed, 317 insertions(+), 32 deletions(-)
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerRFC PATCH 1/4 bpf: add bpf_jhash_mem BPF helper
Add BPF helper that allows to calculate jhash of arbitrary (initialized) memory slice.
--- include/uapi/linux/bpf.h | 8 ++++++++ kernel/bpf/helpers.c | 23 +++++++++++++++++++++++ tools/include/uapi/linux/bpf.h | 8 ++++++++ 3 files changed, 39 insertions(+)
include/uapi/linux/bpf.h +8 -0
@@ -4913,6 +4913,13 @@ union bpf_attr {* Return * The number of bytes written to the buffer, or a negative error * in case of failure. +* +* u64 bpf_jhash_mem(const void *data, u32 sz, u32 seed) +* Description +* Calculate jhash of a given memory slice. +* +* Return +* Calculated hash value. */ #define __BPF_FUNC_MAPPER (FN ) \ FN(unspec), \
@@ -5093,6 +5100,7 @@ union bpf_attr {FN (task_pt_regs), \FN (get_branch_snapshot), \FN (trace_vprintk), \ +FN (jhash_mem), \/* */ /* integer value in 'imm' field of BPF_CALL instruction selects which helper
kernel/bpf/helpers.c +23 -0
@@ -15,9 +15,30 @@#include <linux/pid_namespace.h> #include <linux/proc_ns.h> #include <linux/security.h> +#include <linux/jhash.h> #include "../../lib/kstrtox.h" +BPF_CALL_3(bpf_jhash_mem, const void *, data, u32, sz, u32, seed) +{ +if (unlikely ((uintptr_t )data %4 || sz %4 )) +return jhash (data, sz, seed); + +/* optimized 4-byte version */ +return jhash2 (data, sz /4 , seed); +} + + +static const struct bpf_func_proto bpf_jhash_mem_proto = { + .func = bpf_jhash_mem, + .gpl_only = false, + .ret_type =RET_INTEGER , + .arg1_type =ARG_PTR_TO_MEM , + .arg2_type =ARG_CONST_SIZE_OR_ZERO , + .arg3_type =ARG_ANYTHING , +}; + +/* If kernel subsystem is allowing eBPF programs to call this function, * inside its own verifier_ops->get_func_proto() callback it should return * bpf_map_lookup_elem_proto, so that verifier can properly check the arguments
@@ -1341,6 +1362,8 @@ const struct bpf_func_proto * bpf_base_func_proto(enum bpf_func_id func_id) {switch (func_id) { +case BPF_FUNC_jhash_mem: +return &bpf_jhash_mem_proto;case BPF_FUNC_map_lookup_elem:return &bpf_map_lookup_elem_proto;case BPF_FUNC_map_update_elem:
tools/include/uapi/linux/bpf.h +8 -0
@@ -4913,6 +4913,13 @@ union bpf_attr {* Return * The number of bytes written to the buffer, or a negative error * in case of failure. +* +* u64 bpf_jhash_mem(const void *data, u32 sz, u32 seed) +* Description +* Calculate jhash of a given memory slice. +* +* Return +* Calculated hash value. */ #define __BPF_FUNC_MAPPER (FN ) \ FN(unspec), \
@@ -5093,6 +5100,7 @@ union bpf_attr {FN (task_pt_regs), \FN (get_branch_snapshot), \FN (trace_vprintk), \ +FN (jhash_mem), \/* */ /* integer value in 'imm' field of BPF_CALL instruction selects which helper
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerRFC PATCH 2/4 selftests/bpf: fix and optimize bloom filter bench
In reply to Andrii NakryikoFix inconsistent and highly-variable measurement logic by using always increasing counters. Also reduce the amount of accounting by doing increment once after the entire loop. Also use rodata for bloom filter flag. And build bench files in optimized mode.
--- tools/testing/selftests/bpf/Makefile | 2 +- .../bpf/benchs/bench_bloom_filter_map.c | 32 +++++++++++++- .../selftests/bpf/progs/bloom_filter_map.c | 44 ++++++++++++++----- 3 files changed, 63 insertions(+), 15 deletions(-)
tools/testing/selftests/bpf/Makefile +1 -1
@@ -515,7 +515,7 @@ $(OUTPUT)/test_cpp: test_cpp.cpp $(OUTPUT)/test_core_extern.skel.h $(BPFOBJ) # Benchmark runner $(OUTPUT)/bench_%.o: benchs/bench_%.c bench.h $(BPFOBJ) $(call msg,CC,,$@) - $(Q)$(CC) $(CFLAGS) -c $(filter %.c,$^) $(LDLIBS) -o $@ + $(Q)$(CC) $(CFLAGS) -O2 -c $(filter %.c,$^) $(LDLIBS) -o $@ $(OUTPUT)/bench_rename.o: $(OUTPUT)/test_overhead.skel.h $(OUTPUT)/bench_trigger.o: $(OUTPUT)/trigger_bench.skel.h $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \
tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c +30 -2
@@ -248,7 +248,7 @@ static void hashmap_no_bloom_filter_setup(void) ctx.skel =setup_skeleton (); - ctx.skel->data->hashmap_use_bloom_filter = false; + ctx.skel->rodata->hashmap_use_bloom_filter = false;populate_maps ();
@@ -259,16 +259,26 @@ static void hashmap_no_bloom_filter_setup(void) } } +struct stat {__u32 stats[3 ]; }; +static void measure (struct bench_res *res) { +static long last_hits, last_drops, last_false_hits;long total_hits =0 , total_drops =0 , total_false_hits =0 ;unsigned int nr_cpus =bpf_num_possible_cpus (); +/* BPF_DECLARE_PERCPU(__u64, zeroed_values); BPF_DECLARE_PERCPU(__u64, false_hits); BPF_DECLARE_PERCPU(__u64, drops); BPF_DECLARE_PERCPU(__u64, hits); int err, i, percpu_array_fd; __u32 key; +*/ +int i; +int hit_key, drop_key, false_hit_key; + hit_key = ctx.skel->rodata->hit_key; + drop_key = ctx.skel->rodata->drop_key; + false_hit_key = ctx.skel->rodata->false_hit_key;if (ctx.skel->bss->error !=0 ) { fprintf(stderr, "error (%d) when searching the bloom filter\n",
@@ -276,6 +286,7 @@ static void measure(struct bench_res *res)exit (1 ); } +/* key = ctx.skel->rodata->hit_key; percpu_array_fd = bpf_map__fd(ctx.skel->maps.percpu_array); err = bpf_map_lookup_elem(percpu_array_fd, &key, hits);
@@ -300,20 +311,36 @@ static void measure(struct bench_res *res)-errno); exit(1); } +*/ for (i =0 ; i < nr_cpus; i++) { +struct stat *s = (void *)&ctx.skel->bss->percpu_stats[i]; + + total_hits += s->stats[hit_key]; + total_drops += s->stats[drop_key]; + total_false_hits += s->stats[false_hit_key]; +/* total_hits += bpf_percpu(hits, i); total_drops += bpf_percpu(drops, i); total_false_hits += bpf_percpu(false_hits, i); +*/ } + res->hits = total_hits - last_hits; + res->drops = total_drops - last_drops; + res->false_hits = total_false_hits - last_false_hits; + + last_hits = total_hits; + last_drops = total_drops; + last_false_hits = total_false_hits; + +/* res->hits = total_hits; res->drops = total_drops; res->false_hits = total_false_hits; memset(zeroed_values, 0, sizeof(zeroed_values)); -/* zero out the percpu array */ key = ctx.skel->rodata->hit_key; err = bpf_map_update_elem(percpu_array_fd, &key, zeroed_values, BPF_ANY); if (err) {
@@ -332,6 +359,7 @@ static void measure(struct bench_res *res)fprintf(stderr, "zeroing the percpu array failed: %d\n", -errno); exit(1); } +*/ }static void *consumer (void *input)
tools/testing/selftests/bpf/progs/bloom_filter_map.c +32 -12
112 lines not on this page · raw message
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerRFC PATCH 3/4 selftests/bpf: implement custom Bloom filter purely in BPF
In reply to Andrii NakryikoAnd integrate it into existing benchmarks (on BPF side). Posting this separately from user-space benchmark to emphasize how little code is necessary on BPF side to make this work.
--- .../selftests/bpf/progs/bloom_filter_map.c | 81 ++++++++++++++++++- 1 file changed, 80 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/progs/bloom_filter_map.c +80 -1
@@ -64,9 +64,43 @@ const __u32 drop_key = 1;const __u32 false_hit_key =2 ;const volatile bool hashmap_use_bloom_filter = true; +const volatile bool hashmap_use_custom_bloom_filter = false; + + +__u64 bloom_val =0 ; +static __u64 bloom_arr[256 *1024 ];/* enough for 1mln max_elems w/ 10 hash funcs */ +const volatile __u32 bloom_mask; +const volatile __u32 bloom_hash_cnt; +const volatile __u32 bloom_seed;int error =0 ; +static void bloom_add (const void *data,__u32 sz) +{ +__u32 i =0 , h; + +for (i =0 ; i < bloom_hash_cnt; i++) { + h =bpf_jhash_mem (data, sz, bloom_seed + i); +__sync_fetch_and_or (&bloom_arr[(h /64 ) & bloom_mask],1ULL << (h %64 )); + } +} + +bool bloom_contains (__u64 val) +{ +__u32 i =0 , h; +__u32 seed = bloom_seed, msk = bloom_mask; +__u64 v, *arr = bloom_arr; + +for (i = bloom_hash_cnt; i >0 ; i--) { + h =bpf_jhash_mem (&val,sizeof (val), seed); + v = arr[(h /64 ) & msk]; +if (!((v >> (h %64 )) &1 )) +return false; + seed++; + } +return true; +} + static __always_inline void log_result(__u32 key, __u32 val) {__u32 cpu =bpf_get_smp_processor_id ();
@@ -99,6 +133,20 @@ check_elem(struct bpf_map *map, __u32 *key, __u64 *val,return 0 ; } +static __u64 +check_elem_custom (struct bpf_map *map,__u32 *key,__u64 *val, +struct callback_ctx *data) +{ +if (!bloom_contains (*val)) { + error |=1 ; +return 1 ;/* stop the iteration */ + } + +log_result (hit_key,1 ); + +return 0 ; +} + SEC("fentry/__x64_sys_getpgid")int prog_bloom_filter (void *ctx) {
@@ -110,6 +158,26 @@ int prog_bloom_filter(void *ctx)return 0 ; } +SEC("fentry/__x64_sys_getpgid") +int prog_custom_bloom_filter (void *ctx) +{ +bpf_for_each_map_elem (&map_random_data, check_elem_custom,NULL ,0 ); + +return 0 ; +} + +__u32 bloom_err =0 ; +__u32 bloom_custom_hit =0 ; +__u32 bloom_noncustom_hit =0 ; + +SEC("fentry/__x64_sys_getpgid") +int prog_custom_bloom_filter_add (void *ctx) +{ +bloom_add (&bloom_val,sizeof (bloom_val)); + +return 0 ; +} + SEC("fentry/__x64_sys_getpgid")int prog_bloom_filter_inner_map (void *ctx) {
@@ -145,6 +213,15 @@ int prog_bloom_filter_hashmap_lookup(void *ctx) val.data32[0 ] =/*i; */ bpf_get_prandom_u32 (); val.data32[1 ] =/*i + 1;*/ bpf_get_prandom_u32 (); +if (hashmap_use_custom_bloom_filter) + { +if (!bloom_contains (val.data64)) { + hits++; +//custom_hit = true; +//__sync_fetch_and_add(&bloom_custom_hit, 1); +continue ; + } + }if (hashmap_use_bloom_filter) { err =bpf_map_peek_elem (&map_bloom_filter, &val);
@@ -160,11 +237,13 @@ int prog_bloom_filter_hashmap_lookup(void *ctx) } } +//bloom_err += (custom_hit != noncustom_hit); + result =bpf_map_lookup_elem (&hashmap, &val);if (result) { hits++; }else { -if (hashmap_use_bloom_filter) +if (hashmap_use_custom_bloom_filter || hashmap_use_bloom_filter) false_hits++; drops++; }
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerRFC PATCH 4/4 selftests/bpf: integrate custom Bloom filter impl into benchs
In reply to Andrii NakryikoAdd user-space integration parts.
--- tools/testing/selftests/bpf/bench.c | 6 + .../bpf/benchs/bench_bloom_filter_map.c | 121 +++++++++++++++++- .../bpf/benchs/run_bench_bloom_filter_map.sh | 22 ++-- .../selftests/bpf/benchs/run_common.sh | 2 +- 4 files changed, 135 insertions(+), 16 deletions(-)
tools/testing/selftests/bpf/bench.c +6 -0
@@ -363,9 +363,12 @@ extern const struct bench bench_rb_custom;extern const struct bench bench_pb_libbpf;extern const struct bench bench_pb_custom;extern const struct bench bench_bloom_filter_map; +extern const struct bench bench_custom_bloom_filter_map;extern const struct bench bench_bloom_filter_false_positive; +extern const struct bench bench_custom_bloom_filter_false_positive;extern const struct bench bench_hashmap_without_bloom_filter;extern const struct bench bench_hashmap_with_bloom_filter; +extern const struct bench bench_hashmap_with_custom_bloom_filter;static const struct bench *benchs[] = { &bench_count_global,
@@ -388,9 +391,12 @@ static const struct bench *benchs[] = { &bench_pb_libbpf, &bench_pb_custom, &bench_bloom_filter_map, + &bench_custom_bloom_filter_map, &bench_bloom_filter_false_positive, + &bench_custom_bloom_filter_false_positive, &bench_hashmap_without_bloom_filter, &bench_hashmap_with_bloom_filter, + &bench_hashmap_with_custom_bloom_filter, };static void setup_benchmark ()
tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c +115 -6
200 lines not on this page · raw message
tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh +13 -9
@@ -7,9 +7,9 @@ set -eufo pipefail header "Bloom filter map" for t in 1 4 8; do -for h in {1..10}; do +for h in 1 3 5 10; do subtitle "# threads: $t, # hashes: $h" - for e in 10000 50000 75000 100000 250000 500000 750000 1000000 2500000 5000000; do + for e in 10000 100000 1000000; do printf "%'d entries -\n" $e printf "\t" summarize "Total operations: " \
@@ -17,20 +17,21 @@ subtitle "# threads: $t, # hashes: $h" printf "\t" summarize_percentage "False positive rate: " \ "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e bloom-filter-false-positive)" + printf "\t" + summarize "[CUSTOM] Total operations: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e custom-bloom-filter-map)" + printf "\t" + summarize_percentage "[CUSTOM] False positive rate: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e custom-bloom-filter-false-positive)" done printf "\n" done done -header "Bloom filter map, multi-producer contention" -for t in 1 2 3 4 8 12 16 20 24 28 32 36 40 44 48 52; do - summarize "$t threads - " "$($RUN_BENCH -p $t bloom-filter-map)" -done - header "Hashmap without bloom filter vs. hashmap with bloom filter (throughput, 8 threads)" -for h in {1..10}; do +for h in 1 3 5 10; do subtitle "# hashes: $h" - for e in 10000 50000 75000 100000 250000 500000 750000 1000000 2500000 5000000; do + for e in 10000 100000 1000000; do printf "%'d entries -\n" $e printf "\t" summarize_total "Hashmap without bloom filter: " \
@@ -38,6 +39,9 @@ subtitle "# hashes: $h" printf "\t" summarize_total "Hashmap with bloom filter: " \ "$($RUN_BENCH --nr_hash_funcs $h --nr_entries $e -p 8 hashmap-with-bloom-filter)" + printf "\t" + summarize_total "[CUSTOM] Hashmap with bloom filter: " \ + "$($RUN_BENCH --nr_hash_funcs $h --nr_entries $e -p 8 hashmap-with-custom-bloom-filter)" done printf "\n" done
tools/testing/selftests/bpf/benchs/run_common.sh +1 -1
@@ -1,7 +1,7 @@ #!/bin/bash # SPDX-License-Identifier: GPL-2.0 -RUN_BENCH="sudo ./bench -w3 -d10 -a" +RUN_BENCH="sudo ./bench -w1 -d5 -a" function header() {
Signature · 1 line
2.30.2