Skip to contentSkip to conversation

bpf_jhash_mem() and BPF Bloom filter implementation

RFC PATCH New Andrii Nakryiko 1 participant 5 messages Sep 22, 2021

Subsystems (3)
lore
Share & tools
lore
author maintainer
#1 lore raw

RFC PATCH 1/4 bpf: add bpf_jhash_mem BPF helper

In reply to Andrii Nakryiko

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
index 2e3048488feb..7b17e46b0be2 100644
@@ -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
index 2c604ff8c7fb..00fb1b69595c 100644
@@ -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
index 2e3048488feb..7b17e46b0be2 100644
@@ -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
author maintainer
#2 lore raw

RFC PATCH 2/4 selftests/bpf: fix and optimize bloom filter bench

In reply to Andrii Nakryiko

Fix 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
index 5dbaf7f512fd..f36f49e4d0f2 100644
@@ -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
index 7adf80be7292..4f53cd9fb099 100644
@@ -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

author maintainer
#0 lore raw

cover 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: 3

10,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: 5

10,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: 10

10,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: 1

10,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: 3

10,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: 5

10,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: 10

10,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: 1

10,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: 3

10,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: 5

10,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: 10

10,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
author maintainer
#3 lore raw

RFC PATCH 3/4 selftests/bpf: implement custom Bloom filter purely in BPF

And 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
index 3ae2f9bb5968..ee7bbde1af45 100644
@@ -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
author maintainer
#4 lore raw

RFC PATCH 4/4 selftests/bpf: integrate custom Bloom filter impl into benchs

In reply to Andrii Nakryiko

Add 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
index 7da1589a9fe0..ab03b259b76f 100644
@@ -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
index 239c040b7aaa..ea2c2fff3f40 100755
@@ -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
index 9a16be78b180..961d25374150 100644
@@ -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