Implement bloom filter map
Subsystems (5)
v3 cover Implement bloom filter map
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. For a brief overview about how bloom filters work,
https://en.wikipedia.org/wiki/Bloom_filter
may be helpful.
One example use-case is an application leveraging a bloom filter map to determine whether a computationally expensive hashmap lookup can be avoided. If the element was not found in the bloom filter map, the hashmap lookup can be skipped.
This patchset includes benchmarks for testing the performance of the bloom filter for different entry sizes and different number of hash functions used, as well as comparisons for hashmap lookups with vs. without the bloom filter.
v2 -> v3:
* Add libbpf changes for supporting nr_hash_funcs, instead of passing the number of hash functions through map_flags.
* Separate the hashing logic in kernel/bpf/bloom_filter.c into a helper function
v1 -> v2:
* Remove libbpf changes, and pass the number of hash functions through map_flags instead.
* Default to using 5 hash functions if no number of hash functions is specified.
* Use set_bit instead of spinlocks in the bloom filter bitmap. This improved the speed significantly. For example, using 5 hash functions with 100k entries, there was roughly a 35% speed increase.
* Use jhash2 (instead of jhash) for u32-aligned value sizes. This increased the speed by roughly 5 to 15%. When using jhash2 on value sizes non-u32 aligned (truncating any remainder bits), there was not a noticeable difference.
* Add test for using the bloom filter as an inner map.
* Reran the benchmarks, updated the commit messages to correspond to the new results.
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_types.h | 1 + include/uapi/linux/bpf.h | 6 +- kernel/bpf/Makefile | 2 +- kernel/bpf/bloom_filter.c | 185 +++++++++ kernel/bpf/syscall.c | 14 +- kernel/bpf/verifier.c | 19 +- tools/include/uapi/linux/bpf.h | 6 +- tools/lib/bpf/bpf.c | 2 + tools/lib/bpf/bpf.h | 1 + tools/lib/bpf/libbpf.c | 32 +- tools/lib/bpf/libbpf.h | 2 + tools/lib/bpf/libbpf.map | 1 + 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 | 384 ++++++++++++++++++ .../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 | 177 ++++++++ .../selftests/bpf/progs/bloom_filter_map.c | 157 +++++++ 22 files changed, 1142 insertions(+), 48 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
Signature · 1 line
2.30.2
PATCH v3 1/5 bpf: Add bloom filter map implementation
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 should never be.
This patch adds a bloom filter map for bpf programs. The bloom filter map supports peek (determining whether an element is present in the map) and push (adding an element to the map) operations.These operations are exposed to userspace applications through the already existing syscalls in the following way:
BPF_MAP_LOOKUP_ELEM -> peekBPF_MAP_UPDATE_ELEM -> push
The bloom filter map does not have keys, only values. In light of this, the bloom filter map's API matches that of queue stack maps:
user applications use BPF_MAP_LOOKUP_ELEM/BPF_MAP_UPDATE_ELEM which correspond internally to bpf_map_peek_elem/bpf_map_push_elem, and bpf programs must use the bpf_map_peek_elem and bpf_map_push_elem APIs to query or add an element to the bloom filter map. When the bloom filter map is created, it must be created with a key_size of 0.
For updates, the user will pass in the element to add to the map as the value, with a NULL key. For lookups, the user will pass in the element to query in the map as the value. In the verifier layer, this requires us to modify the argument type of a bloom filter's BPF_FUNC_map_peek_elem call to ARG_PTR_TO_MAP_VALUE; as well, in the syscall layer, we need to copy over the user value so that in bpf_map_peek_elem, we know which specific value to query.
A few things to please take note of:
* If there are any concurrent lookups + updates, the user is
responsible for synchronizing this to ensure no false negative lookups occur.
* The number of hashes to use for the bloom filter is configurable from
userspace. If no number is specified, the default used will be 5 hash functions. The benchmarks later in this patchset can help compare the performance of using different number of hashes on different entry sizes. In general, using more hashes decreases the speed of a lookup, but increases the false positive rate of an element being detected in the bloom filter.
* Deleting an element in the bloom filter map is not supported.
* The bloom filter map may be used as an inner map.
* The "max_entries" size that is specified at map creation time is used to
approximate a reasonable bitmap size for the bloom filter, and is not otherwise strictly enforced. If the user wishes to insert more entries into the bloom filter than "max_entries", they may do so but they should be aware that this may lead to a higher false positive rate.
--- include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 1 + kernel/bpf/Makefile | 2 +- kernel/bpf/bloom_filter.c | 185 +++++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 14 ++- kernel/bpf/verifier.c | 19 +++- tools/include/uapi/linux/bpf.h | 1 + 7 files changed, 217 insertions(+), 6 deletions(-) create mode 100644 kernel/bpf/bloom_filter.c
include/linux/bpf_types.h +1 -0
@@ -125,6 +125,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_STACK, stack_map_ops) BPF_MAP_TYPE(BPF_MAP_TYPE_STRUCT_OPS, bpf_struct_ops_map_ops)#endif BPF_MAP_TYPE(BPF_MAP_TYPE_RINGBUF, ringbuf_map_ops) +BPF_MAP_TYPE(BPF_MAP_TYPE_BLOOM_FILTER, bloom_filter_map_ops) BPF_LINK_TYPE(BPF_LINK_TYPE_RAW_TRACEPOINT, raw_tracepoint)BPF_LINK_TYPE (BPF_LINK_TYPE_TRACING , tracing)
include/uapi/linux/bpf.h +1 -0
@@ -906,6 +906,7 @@ enum bpf_map_type {BPF_MAP_TYPE_RINGBUF ,BPF_MAP_TYPE_INODE_STORAGE ,BPF_MAP_TYPE_TASK_STORAGE , + BPF_MAP_TYPE_BLOOM_FILTER, };/* Note that tracing related programs such as
kernel/bpf/Makefile +1 -1
@@ -7,7 +7,7 @@ endif CFLAGS_core.o += $(call cc-disable-warning, override-init) $(cflags-nogcse-yy) obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o bpf_iter.o map_iter.o task_iter.o prog_iter.o -obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o +obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o obj-$(CONFIG_BPF_SYSCALL) += bpf_local_storage.o bpf_task_storage.o obj-${CONFIG_BPF_LSM} += bpf_inode_storage.o
kernel/bpf/bloom_filter.c new file +185 -0
185 lines not on this page · raw message
kernel/bpf/syscall.c +12 -2
@@ -199,7 +199,8 @@ static int bpf_map_update_value(struct bpf_map *map, struct fd f, void *key, err =bpf_fd_reuseport_array_update_elem (map, key, value, flags); }else if (map->map_type ==BPF_MAP_TYPE_QUEUE || - map->map_type ==BPF_MAP_TYPE_STACK ) { + map->map_type ==BPF_MAP_TYPE_STACK || + map->map_type ==BPF_MAP_TYPE_BLOOM_FILTER ) { err = map->ops->map_push_elem (map, value, flags); }else {rcu_read_lock ();
@@ -238,7 +239,8 @@ static int bpf_map_copy_value(struct bpf_map *map, void *key, void *value, }else if (map->map_type ==BPF_MAP_TYPE_REUSEPORT_SOCKARRAY ) { err =bpf_fd_reuseport_array_lookup_elem (map, key, value); }else if (map->map_type ==BPF_MAP_TYPE_QUEUE || - map->map_type ==BPF_MAP_TYPE_STACK ) { + map->map_type ==BPF_MAP_TYPE_STACK || + map->map_type ==BPF_MAP_TYPE_BLOOM_FILTER ) { err = map->ops->map_peek_elem (map, value); }else if (map->map_type ==BPF_MAP_TYPE_STRUCT_OPS ) {/* struct_ops map requires directly updating "value" */
@@ -1080,6 +1082,14 @@ static int map_lookup_elem(union bpf_attr *attr)if (!value) goto free_key; +if (map->map_type ==BPF_MAP_TYPE_BLOOM_FILTER ) { +if (copy_from_user (value, uvalue, value_size)) + err = -EFAULT ; +else + err =bpf_map_copy_value (map, key, value, attr->flags); + goto free_value; + } + err =bpf_map_copy_value (map, key, value, attr->flags);if (err) goto free_value;
kernel/bpf/verifier.c +16 -3
@@ -4813,7 +4813,10 @@ static int resolve_map_arg_type(struct bpf_verifier_env *env,return -EINVAL ; }break ; - +case BPF_MAP_TYPE_BLOOM_FILTER : +if (meta->func_id == BPF_FUNC_map_peek_elem) + *arg_type =ARG_PTR_TO_MAP_VALUE ; +break ;default :break ; }
@@ -5388,6 +5391,11 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env, func_id != BPF_FUNC_task_storage_delete) goto error;break ; +case BPF_MAP_TYPE_BLOOM_FILTER : +if (func_id != BPF_FUNC_map_push_elem && + func_id != BPF_FUNC_map_peek_elem) + goto error; +break ;default :break ; }
@@ -5455,13 +5463,18 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env, map->map_type != BPF_MAP_TYPE_SOCKHASH) goto error;break ; -case BPF_FUNC_map_peek_elem:case BPF_FUNC_map_pop_elem: -case BPF_FUNC_map_push_elem:if (map->map_type !=BPF_MAP_TYPE_QUEUE && map->map_type !=BPF_MAP_TYPE_STACK ) goto error;break ; +case BPF_FUNC_map_push_elem: +case BPF_FUNC_map_peek_elem: +if (map->map_type !=BPF_MAP_TYPE_QUEUE && + map->map_type !=BPF_MAP_TYPE_STACK && + map->map_type !=BPF_MAP_TYPE_BLOOM_FILTER ) + goto error; +break ;case BPF_FUNC_sk_storage_get:case BPF_FUNC_sk_storage_delete:if (map->map_type !=BPF_MAP_TYPE_SK_STORAGE )
tools/include/uapi/linux/bpf.h +1 -0
@@ -906,6 +906,7 @@ enum bpf_map_type {BPF_MAP_TYPE_RINGBUF ,BPF_MAP_TYPE_INODE_STORAGE ,BPF_MAP_TYPE_TASK_STORAGE , + BPF_MAP_TYPE_BLOOM_FILTER, };/* Note that tracing related programs such as
Signature · 1 line
2.30.2
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 51 lines · Joanne Koong
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 should never be.
This patch adds a bloom filter map for bpf programs. The bloom filter map supports peek (determining whether an element is present in the map) and push (adding an element to the map) operations.These operations are exposed to userspace applications through the already existing syscalls in the following way:
BPF_MAP_LOOKUP_ELEM-> peekBPF_MAP_UPDATE_ELEM-> pushThe bloom filter map does not have keys, only values. In light of this, the bloom filter map's API matches that of queue stack maps:
user applications use BPF_MAP_LOOKUP_ELEM/BPF_MAP_UPDATE_ELEM which correspond internally to bpf_map_peek_elem/bpf_map_push_elem, and bpf programs must use thebpf_map_peek_elemandbpf_map_push_elemAPIs to query or add an element to the bloom filter map. When the bloom filter map is created, it must be created with akey_sizeof 0.For updates, the user will pass in the element to add to the map as the value, with a NULL key. For lookups, the user will pass in the element to query in the map as the value. In the verifier layer, this requires us to modify the argument type of a bloom filter's
BPF_FUNC_map_peek_elemcall toARG_PTR_TO_MAP_VALUE; as well, in the syscall layer, we need to copy over the user value so that inbpf_map_peek_elem, we know which specific value to query.A few things to please take note of:
* If there are any concurrent lookups + updates, the user is
responsible for synchronizing this to ensure no false negative lookups occur.
* The number of hashes to use for the bloom filter is configurable from
userspace. If no number is specified, the default used will be 5 hash functions. The benchmarks later in this patchset can help compare the performance of using different number of hashes on different entry sizes. In general, using more hashes decreases the speed of a lookup, but increases the false positive rate of an element being detected in the bloom filter.
* Deleting an element in the bloom filter map is not supported.
* The bloom filter map may be used as an inner map.
* The "max_entries" size that is specified at map creation time is used to
approximate a reasonable bitmap size for the bloom filter, and is not otherwise strictly enforced. If the user wishes to insert more entries into the bloom filter than "max_entries", they may do so but they should be aware that this may lead to a higher false positive rate.Signed-off-by Joanne Koong <[email protected]>
Quoted 11 lines
--- include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 1 + kernel/bpf/Makefile | 2 +- kernel/bpf/bloom_filter.c | 185 +++++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 14 ++- kernel/bpf/verifier.c | 19 +++- tools/include/uapi/linux/bpf.h | 1 + 7 files changed, 217 insertions(+), 6 deletions(-) create mode 100644 kernel/bpf/bloom_filter.c
See some stylistic nitpicking below (and not a nitpicking about BTF).
But I just wanted to say that I'm a bit amazed by how much special casing this BLOOM_FILTER map requires in syscall.c and verifier.c. I still believe that starting with a BPF helper for hashing would be a better approach, but oh well.
[...]
kernel/bpf/bloom_filter.c line 37
Quoted 11 lines
kernel/bpf/bloom_filter.c new file +11
-0+ +static inline u32 hash (struct bpf_bloom_filter *bloom_filter,void *value, +u64 value_size,u32 index) +{ +if (bloom_filter->aligned_u32_count) +return jhash2 (value, bloom_filter->aligned_u32_count, + bloom_filter->hash_seed + index) & + bloom_filter->bit_array_mask; + +return jhash (value, value_size, bloom_filter->hash_seed + index) & + bloom_filter->bit_array_mask;
stylistic nit, but this feels way to dense text-wise, this seems easier to follow
u32 h;
if (bloom_filter->aligned_u32_count)
h = jhash2(...);
else
h = jhash(...);return h & bloom_filter->bit_array_mask;
WDYT?
kernel/bpf/bloom_filter.c line 49
Quoted 12 lines
kernel/bpf/bloom_filter.c new file +12
-0+} + +static int bloom_filter_map_peek_elem (struct bpf_map *map,void *value) +{ +struct bpf_bloom_filter *bloom_filter = + container_of(map, struct bpf_bloom_filter, map); +u32 i; + +for (i =0 ; i < bloom_filter->nr_hash_funcs; i++) { +if (!test_bit (hash (bloom_filter, value, map->value_size, i), + bloom_filter->bit_array)) +return -ENOENT ;
same here, I think the hash calculation deserves a separate statement and a local variable
Quoted 5 lines
kernel/bpf/bloom_filter.c new file +5
-0+ } + +return 0 ; +} +
[...]
Quoted 11 lines
kernel/bpf/bloom_filter.c new file +11
-0+static void bloom_filter_map_free (struct bpf_map *map) +{ +struct bpf_bloom_filter *bloom_filter = + container_of(map, struct bpf_bloom_filter, map); + +bpf_map_area_free (bloom_filter); +} + +static int bloom_filter_map_push_elem (struct bpf_map *map,void *value, +u64 flags) +{
kernel/bpf/bloom_filter.c line 142
Quoted 10 lines
kernel/bpf/bloom_filter.c new file +10
-0+struct bpf_bloom_filter *bloom_filter = + container_of(map, struct bpf_bloom_filter, map); +u32 i; + +if (flags !=BPF_ANY ) +return -EINVAL ; + +for (i =0 ; i < bloom_filter->nr_hash_funcs; i++) +set_bit (hash (bloom_filter, value, map->value_size, i), + bloom_filter->bit_array);
same as above about hash() call on separate line
Quoted 30 lines
kernel/bpf/bloom_filter.c new file +30
-0+ +return 0 ; +} + +static void *bloom_filter_map_lookup_elem (struct bpf_map *map,void *key) +{ +/* The eBPF program should use map_peek_elem instead */ +return ERR_PTR (-EINVAL ); +} + +static int bloom_filter_map_update_elem (struct bpf_map *map,void *key, +void *value,u64 flags) +{ +/* The eBPF program should use map_push_elem instead */ +return -EINVAL ; +} + +static int bloom_filter_map_delete_elem (struct bpf_map *map,void *key) +{ +return -EOPNOTSUPP ; +} + +static int bloom_filter_map_get_next_key (struct bpf_map *map,void *key, +void *next_key) +{ +return -EOPNOTSUPP ; +} + +static int bloom_filter_map_btf_id; +const struct bpf_map_ops bloom_filter_map_ops = {
kernel/bpf/bloom_filter.c line 182
Quoted 10 lines
kernel/bpf/bloom_filter.c new file +10
-0+ .map_meta_equal = bpf_map_meta_equal, + .map_alloc = bloom_filter_map_alloc, + .map_free = bloom_filter_map_free, + .map_push_elem = bloom_filter_map_push_elem, + .map_peek_elem = bloom_filter_map_peek_elem, + .map_lookup_elem = bloom_filter_map_lookup_elem, + .map_update_elem = bloom_filter_map_update_elem, + .map_delete_elem = bloom_filter_map_delete_elem, + .map_get_next_key = bloom_filter_map_get_next_key, + .map_check_btf = map_check_no_btf,
can you please implement basically a no-op callback here to allow specifying btf_value_id, there is no good reason to restrict this new map to not allow BTF type being specified for its value
Quoted 3 lines
kernel/bpf/bloom_filter.c new file +3
-0+ .map_btf_name = "bpf_bloom_filter", + .map_btf_id = &bloom_filter_map_btf_id, +};
[...]
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 62 lines · Andrii Nakryiko
Quoted 59 lines · Joanne Koong
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 should never be.
This patch adds a bloom filter map for bpf programs. The bloom filter map supports peek (determining whether an element is present in the map) and push (adding an element to the map) operations.These operations are exposed to userspace applications through the already existing syscalls in the following way:
BPF_MAP_LOOKUP_ELEM-> peekBPF_MAP_UPDATE_ELEM-> pushThe bloom filter map does not have keys, only values. In light of this, the bloom filter map's API matches that of queue stack maps:
user applications use BPF_MAP_LOOKUP_ELEM/BPF_MAP_UPDATE_ELEM which correspond internally to bpf_map_peek_elem/bpf_map_push_elem, and bpf programs must use thebpf_map_peek_elemandbpf_map_push_elemAPIs to query or add an element to the bloom filter map. When the bloom filter map is created, it must be created with akey_sizeof 0.For updates, the user will pass in the element to add to the map as the value, with a NULL key. For lookups, the user will pass in the element to query in the map as the value. In the verifier layer, this requires us to modify the argument type of a bloom filter's
BPF_FUNC_map_peek_elemcall toARG_PTR_TO_MAP_VALUE; as well, in the syscall layer, we need to copy over the user value so that inbpf_map_peek_elem, we know which specific value to query.A few things to please take note of:
* If there are any concurrent lookups + updates, the user is
responsible for synchronizing this to ensure no false negative lookups occur.
* The number of hashes to use for the bloom filter is configurable from
userspace. If no number is specified, the default used will be 5 hash functions. The benchmarks later in this patchset can help compare the performance of using different number of hashes on different entry sizes. In general, using more hashes decreases the speed of a lookup, but increases the false positive rate of an element being detected in the bloom filter.
* Deleting an element in the bloom filter map is not supported.
* The bloom filter map may be used as an inner map.
* The "max_entries" size that is specified at map creation time is used to
approximate a reasonable bitmap size for the bloom filter, and is not otherwise strictly enforced. If the user wishes to insert more entries into the bloom filter than "max_entries", they may do so but they should be aware that this may lead to a higher false positive rate.Signed-off-by Joanne Koong <[email protected]>--- include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 1 + kernel/bpf/Makefile | 2 +- kernel/bpf/bloom_filter.c | 185 +++++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 14 ++- kernel/bpf/verifier.c | 19 +++- tools/include/uapi/linux/bpf.h | 1 + 7 files changed, 217 insertions(+), 6 deletions(-)Quoted 2 lines
create mode 100644
kernel/bpf/bloom_filter.c
Quoted 8 lines
See some stylistic nitpicking below (and not a nitpicking about BTF).
But I just wanted to say that I'm a bit amazed by how much special casing this
BLOOM_FILTERmap requires insyscall.candverifier.c. I still believe that starting with a BPF helper for hashing would be a better approach, but oh well.[...]
I liked your comment on v1 regarding using a BPF helper and I agree with the benefits you outlined. I'm curious to see what the performance differences between that approach and this one end up being, if any. I plan to test out the BPF helper approach in a few weeks, and if the performance is comparable or better, I am definitely open to reverting this code and just going with the BPF helper approach :)
Quoted 16 lines
kernel/bpf/bloom_filter.c line 37
Quoted 11 lines
kernel/bpf/bloom_filter.c new file +11
-0+ +static inline u32 hash (struct bpf_bloom_filter *bloom_filter,void *value, +u64 value_size,u32 index) +{ +if (bloom_filter->aligned_u32_count) +return jhash2 (value, bloom_filter->aligned_u32_count, + bloom_filter->hash_seed + index) & + bloom_filter->bit_array_mask; + +return jhash (value, value_size, bloom_filter->hash_seed + index) & + bloom_filter->bit_array_mask;stylistic nit, but this feels way to dense text-wise, this seems easier to follow
u32 h;
Quoted 7 lines
if (
bloom_filter->aligned_u32_count)h = jhash2(...); else h = jhash(...);return h &
bloom_filter->bit_array_mask;WDYT?
I think this sounds great! I will make these changes for v4.
Quoted 80 lines
kernel/bpf/bloom_filter.c line 49
Quoted 12 lines
kernel/bpf/bloom_filter.c new file +12
-0+} + +static int bloom_filter_map_peek_elem (struct bpf_map *map,void *value) +{ +struct bpf_bloom_filter *bloom_filter = + container_of(map, struct bpf_bloom_filter, map); +u32 i; + +for (i =0 ; i < bloom_filter->nr_hash_funcs; i++) { +if (!test_bit (hash (bloom_filter, value, map->value_size, i), + bloom_filter->bit_array)) +return -ENOENT ;same here, I think the hash calculation deserves a separate statement and a local variable
Quoted 5 lines
kernel/bpf/bloom_filter.c new file +5
-0+ } + +return 0 ; +} +[...]
Quoted 11 lines
kernel/bpf/bloom_filter.c new file +11
-0+static void bloom_filter_map_free (struct bpf_map *map) +{ +struct bpf_bloom_filter *bloom_filter = + container_of(map, struct bpf_bloom_filter, map); + +bpf_map_area_free (bloom_filter); +} + +static int bloom_filter_map_push_elem (struct bpf_map *map,void *value, +u64 flags) +{kernel/bpf/bloom_filter.c line 142
Quoted 10 lines
kernel/bpf/bloom_filter.c new file +10
-0+struct bpf_bloom_filter *bloom_filter = + container_of(map, struct bpf_bloom_filter, map); +u32 i; + +if (flags !=BPF_ANY ) +return -EINVAL ; + +for (i =0 ; i < bloom_filter->nr_hash_funcs; i++) +set_bit (hash (bloom_filter, value, map->value_size, i), + bloom_filter->bit_array);same as above about
hash()call on separate lineQuoted 35 lines
kernel/bpf/bloom_filter.c new file +35
-0+ +return 0 ; +} + +static void *bloom_filter_map_lookup_elem (struct bpf_map *map,void *key) +{ +/* The eBPF program should use map_peek_elem instead */ +return ERR_PTR (-EINVAL ); +} + +static int bloom_filter_map_update_elem (struct bpf_map *map,void *key, +void *value,u64 flags) +{ +/* The eBPF program should use map_push_elem instead */ +return -EINVAL ; +} + +static int bloom_filter_map_delete_elem (struct bpf_map *map,void *key) +{ +return -EOPNOTSUPP ; +} + +static int bloom_filter_map_get_next_key (struct bpf_map *map,void *key, +void *next_key) +{ +return -EOPNOTSUPP ; +} + +static int bloom_filter_map_btf_id; +const struct bpf_map_ops bloom_filter_map_ops = { + .map_meta_equal = bpf_map_meta_equal, + .map_alloc = bloom_filter_map_alloc, + .map_free = bloom_filter_map_free, + .map_push_elem = bloom_filter_map_push_elem, + .map_peek_elem = bloom_filter_map_peek_elem,
Quoted 8 lines
kernel/bpf/bloom_filter.c line 182
Quoted 5 lines
kernel/bpf/bloom_filter.c new file +5
-0+ .map_lookup_elem = bloom_filter_map_lookup_elem, + .map_update_elem = bloom_filter_map_update_elem, + .map_delete_elem = bloom_filter_map_delete_elem, + .map_get_next_key = bloom_filter_map_get_next_key, + .map_check_btf = map_check_no_btf,can you please implement basically a no-op callback here to allow specifying
btf_value_id, there is no good reason to restrict this new map to not allow BTF type being specified for its value
Sounds great, will add this in v4.
Quoted 4 lines
Quoted 3 lines
kernel/bpf/bloom_filter.c new file +3
-0+ .map_btf_name = "bpf_bloom_filter", + .map_btf_id = &bloom_filter_map_btf_id, +};[...]
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 71 lines · Joanne Koong
Quoted 69 lines · Andrii Nakryiko
Quoted 59 lines · Joanne Koong
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 should never be.
This patch adds a bloom filter map for bpf programs. The bloom filter map supports peek (determining whether an element is present in the map) and push (adding an element to the map) operations.These operations are exposed to userspace applications through the already existing syscalls in the following way:
BPF_MAP_LOOKUP_ELEM-> peekBPF_MAP_UPDATE_ELEM-> pushThe bloom filter map does not have keys, only values. In light of this, the bloom filter map's API matches that of queue stack maps:
user applications use BPF_MAP_LOOKUP_ELEM/BPF_MAP_UPDATE_ELEM which correspond internally to bpf_map_peek_elem/bpf_map_push_elem, and bpf programs must use thebpf_map_peek_elemandbpf_map_push_elemAPIs to query or add an element to the bloom filter map. When the bloom filter map is created, it must be created with akey_sizeof 0.For updates, the user will pass in the element to add to the map as the value, with a NULL key. For lookups, the user will pass in the element to query in the map as the value. In the verifier layer, this requires us to modify the argument type of a bloom filter's
BPF_FUNC_map_peek_elemcall toARG_PTR_TO_MAP_VALUE; as well, in the syscall layer, we need to copy over the user value so that inbpf_map_peek_elem, we know which specific value to query.A few things to please take note of:
* If there are any concurrent lookups + updates, the user is
responsible for synchronizing this to ensure no false negative lookups occur.
* The number of hashes to use for the bloom filter is configurable from
userspace. If no number is specified, the default used will be 5 hash functions. The benchmarks later in this patchset can help compare the performance of using different number of hashes on different entry sizes. In general, using more hashes decreases the speed of a lookup, but increases the false positive rate of an element being detected in the bloom filter.
* Deleting an element in the bloom filter map is not supported.
* The bloom filter map may be used as an inner map.
* The "max_entries" size that is specified at map creation time is used to
approximate a reasonable bitmap size for the bloom filter, and is not otherwise strictly enforced. If the user wishes to insert more entries into the bloom filter than "max_entries", they may do so but they should be aware that this may lead to a higher false positive rate.Signed-off-by Joanne Koong <[email protected]>--- include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 1 + kernel/bpf/Makefile | 2 +- kernel/bpf/bloom_filter.c | 185 +++++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 14 ++- kernel/bpf/verifier.c | 19 +++- tools/include/uapi/linux/bpf.h | 1 + 7 files changed, 217 insertions(+), 6 deletions(-)Quoted 2 lines
create mode 100644
kernel/bpf/bloom_filter.cSee some stylistic nitpicking below (and not a nitpicking about BTF).
But I just wanted to say that I'm a bit amazed by how much special casing this
BLOOM_FILTERmap requires insyscall.candverifier.c. I still believe that starting with a BPF helper for hashing would be a better approach, but oh well.
Quoted 6 lines
Quoted 1 line
[...]
I liked your comment on v1 regarding using a BPF helper and I agree with the benefits you outlined. I'm curious to see what the performance differences between that approach and this one end up being, if any. I plan to test out the BPF helper approach in a few weeks, and if the performance is comparable or better, I am definitely open to reverting this code and just going with the BPF helper approach :)
Reverting won't be an option and I don't think it is necessary.
Agree that a generic hash helper is in general useful. It may be useful in hashing the skb also. The bpf prog only implementation could have more flexibility in configuring roundup to pow2 or not, how to hash, how many hashes, nr of bits ...etc. In the mean time, the bpf prog and user space need to co-ordinate more and worry about more things, e.g. how to reuse a bloom filter with different nr_hashes, nr_bits, handle synchronization...etc.
It is useful to have a default implementation in the kernel for some useful maps like this one that works for most common cases and the bpf user can just use it as get-and-go like all other common bpf maps do.
imo, the verifier/syscall change here is quite minimal also and it is mostly riding on top of the existing BPF_MAP_TYPE_STACK.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 79 lines · Martin KaFai Lau
Quoted 71 lines · Joanne Koong
Quoted 69 lines · Andrii Nakryiko
Quoted 59 lines · Joanne Koong
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 should never be.
This patch adds a bloom filter map for bpf programs. The bloom filter map supports peek (determining whether an element is present in the map) and push (adding an element to the map) operations.These operations are exposed to userspace applications through the already existing syscalls in the following way:
BPF_MAP_LOOKUP_ELEM-> peekBPF_MAP_UPDATE_ELEM-> pushThe bloom filter map does not have keys, only values. In light of this, the bloom filter map's API matches that of queue stack maps:
user applications use BPF_MAP_LOOKUP_ELEM/BPF_MAP_UPDATE_ELEM which correspond internally to bpf_map_peek_elem/bpf_map_push_elem, and bpf programs must use thebpf_map_peek_elemandbpf_map_push_elemAPIs to query or add an element to the bloom filter map. When the bloom filter map is created, it must be created with akey_sizeof 0.For updates, the user will pass in the element to add to the map as the value, with a NULL key. For lookups, the user will pass in the element to query in the map as the value. In the verifier layer, this requires us to modify the argument type of a bloom filter's
BPF_FUNC_map_peek_elemcall toARG_PTR_TO_MAP_VALUE; as well, in the syscall layer, we need to copy over the user value so that inbpf_map_peek_elem, we know which specific value to query.A few things to please take note of:
* If there are any concurrent lookups + updates, the user is
responsible for synchronizing this to ensure no false negative lookups occur.
* The number of hashes to use for the bloom filter is configurable from
userspace. If no number is specified, the default used will be 5 hash functions. The benchmarks later in this patchset can help compare the performance of using different number of hashes on different entry sizes. In general, using more hashes decreases the speed of a lookup, but increases the false positive rate of an element being detected in the bloom filter.
* Deleting an element in the bloom filter map is not supported.
* The bloom filter map may be used as an inner map.
* The "max_entries" size that is specified at map creation time is used to
approximate a reasonable bitmap size for the bloom filter, and is not otherwise strictly enforced. If the user wishes to insert more entries into the bloom filter than "max_entries", they may do so but they should be aware that this may lead to a higher false positive rate.Signed-off-by Joanne Koong <[email protected]>--- include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 1 + kernel/bpf/Makefile | 2 +- kernel/bpf/bloom_filter.c | 185 +++++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 14 ++- kernel/bpf/verifier.c | 19 +++- tools/include/uapi/linux/bpf.h | 1 + 7 files changed, 217 insertions(+), 6 deletions(-)Quoted 2 lines
create mode 100644
kernel/bpf/bloom_filter.cSee some stylistic nitpicking below (and not a nitpicking about BTF).
But I just wanted to say that I'm a bit amazed by how much special casing this
BLOOM_FILTERmap requires insyscall.candverifier.c. I still believe that starting with a BPF helper for hashing would be a better approach, but oh well.Quoted 6 lines
Quoted 1 line
[...]
I liked your comment on v1 regarding using a BPF helper and I agree with the benefits you outlined. I'm curious to see what the performance differences between that approach and this one end up being, if any. I plan to test out the BPF helper approach in a few weeks, and if the performance is comparable or better, I am definitely open to reverting this code and just going with the BPF helper approach :)
Quoted 6 lines
Reverting won't be an option and I don't think it is necessary.
Agree that a generic hash helper is in general useful. It may be useful in hashing the skb also. The bpf prog only implementation could have more flexibility in configuring roundup to pow2 or not, how to hash, how many hashes, nr of bits ...etc. In the mean time, the bpf prog and
Exactly. If I know better how many bits I need, I'll have to reverse engineer kernel's heuristic to provide such max_entries values to arrive at the desired amount of memory that Bloom filter will be using.
Quoted 3 lines
user space need to co-ordinate more and worry about more things, e.g. how to reuse a bloom filter with different
nr_hashes,nr_bits, handle synchronization...etc.
Please see my RFC ([0]). I don't think there is much to coordinate. It could be purely BPF-side code, or BPF + user-space initialization code, depending on the need. It's a simple and beautiful algorithm, which BPF is powerful enough to implement customly and easily.
[0] https://lore.kernel.org/bpf/[email protected]/T/#t
Quoted 5 lines
It is useful to have a default implementation in the kernel for some useful maps like this one that works for most common cases and the bpf user can just use it as get-and-go like all other common bpf maps do.
I disagree with the premise that Bloom filter is a common and generally useful data structure, tbh. It has its nice niche applications, but its semantics isn't applicable generally, which is why I hesitate to claim that this should live in kernel.
Quoted 3 lines
imo, the verifier/syscall change here is quite minimal also and it is mostly riding on top of the existing
BPF_MAP_TYPE_STACK.
Not exactly true, it adds quite a bit of new custom pieces. But it's subjective so there is no point in arguing.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 9 lines · Andrii Nakryiko
Quoted 4 lines
Agree that a generic hash helper is in general useful. It may be useful in hashing the skb also. The bpf prog only implementation could have more flexibility in configuring roundup to pow2 or not, how to hash, how many hashes, nr of bits ...etc. In the mean time, the bpf prog and
Exactly. If I know better how many bits I need, I'll have to reverse engineer kernel's heuristic to provide such
max_entriesvalues to arrive at the desired amount of memory that Bloom filter will be using.
Good point. I don't think it needs to guess. The formula is stable and publicly known also. The formula comment from kernel/bpf/bloom_filter.c should be moved to the include/uapi/linux/bpf.h.
Quoted 10 lines
Quoted 3 lines
user space need to co-ordinate more and worry about more things, e.g. how to reuse a bloom filter with different
nr_hashes,nr_bits, handle synchronization...etc.Please see my RFC ([0]). I don't think there is much to coordinate. It could be purely BPF-side code, or BPF + user-space initialization code, depending on the need. It's a simple and beautiful algorithm, which BPF is powerful enough to implement customly and easily.
In practice, the bloom filter will be populated only once by the userspace.
The future update will be done by map-in-map to replace the whole bloom filter. May be with more max_entries with more nr_hashes. May be fewer max_entries with fewer nr_hashes.
Currently, the continuous running bpf prog using this bloom filter does not need to worry about any change in the newer bloom filter configure/setup.
I wonder how that may look like in the custom bpf bloom filter in the bench prog for the map-in-map usage.
Quoted 11 lines
Quoted 6 lines
It is useful to have a default implementation in the kernel for some useful maps like this one that works for most common cases and the bpf user can just use it as get-and-go like all other common bpf maps do.
I disagree with the premise that Bloom filter is a common and generally useful data structure, tbh. It has its nice niche applications, but its semantics isn't applicable generally, which is why I hesitate to claim that this should live in kernel.
I don't agree the application is nice niche. I have encountered this many times when bumping into networking usecase discussion and not necessary limited to security usage also. Yes, it is not a link-list like data structure but its usage is very common.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 7 lines · Martin KaFai Lau
Quoted 5 lines · Andrii Nakryiko
Quoted 4 lines
Agree that a generic hash helper is in general useful. It may be useful in hashing the skb also. The bpf prog only implementation could have more flexibility in configuring roundup to pow2 or not, how to hash, how many hashes, nr of bits ...etc. In the mean time, the bpf prog and
Quoted 7 lines
Quoted 4 lines
Exactly. If I know better how many bits I need, I'll have to reverse engineer kernel's heuristic to provide such
max_entriesvalues to arrive at the desired amount of memory that Bloom filter will be using.Good point. I don't think it needs to guess. The formula is stable and publicly known also. The formula comment from
kernel/bpf/bloom_filter.cshould be moved to theinclude/uapi/linux/bpf.h.
By guessing I mean you'd need to invert the formula to calculate the necessary max_entries you'd need just to size bloom filter to the desired size. At which point max_entries won't really mean much.
Also the whole "let's choose 5 as number of hash functions" approach seems pretty arbitrary and not explained. How was this chosen? Based on one very particular benchmark? How can we tell it's good for most use cases? How did we arrive at 5 and not 3 or 4?
Looking at [0], there are many ways to go about sizing Bloom filter. 5 hash functions, assuming the wikipedia formula we are using (N * K * ln(2)), and according to "This means that for a given false positive probability ε, the length of a Bloom filter m is proportionate to the number of elements being filtered n and the required number of hash functions only depends on the target false positive probability ε." (from [1]) and corresponding formula, gives a false positive probability or around 3%, if my math is right. Did we state those 3% anywhere and how we arrived at them?
But there are multiple parameters involved in this decision, they are interconnected, and different subsets of them might be driving user's choice:
- number of expected unique elements;
- number of bits allocated;
- acceptable false positive rate;
- number of hash functions.
What if I want a false positive probability of 1%, or maybe 10%, or 0.1%, but not 3%? What if I'm concerned about memory usage and rather save some memory at the expense of more false positives? Or calling too many hash functions is prohibitive, but I can allocate more memory to reduce the chance of hash collisions. There are many ways to slice this cat. Kernel implementation makes *some* assumptions with little justification and explanation. It's opinionated in one place (M * N * ln(2)), but leaves it up to the user to make sense of what number of functions it needs (K = -log2(eps)). Feels quite unusual and underspecified for the kernel data structure. It would be probably good to provide a bit of guidance in map description, I suppose.
Anyways, I've spent way too much time on this. It was fun, but I'll shut up and go do something else.
[0] https://en.wikipedia.org/wiki/Bloom_filter
[1] https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of_hash_functions
Quoted 17 lines
Quoted 11 lines
Quoted 4 lines
user space need to co-ordinate more and worry about more things, e.g. how to reuse a bloom filter with different
nr_hashes,nr_bits, handle synchronization...etc.Please see my RFC ([0]). I don't think there is much to coordinate. It could be purely BPF-side code, or BPF + user-space initialization code, depending on the need. It's a simple and beautiful algorithm, which BPF is powerful enough to implement customly and easily.
In practice, the bloom filter will be populated only once by the userspace.
The future update will be done by map-in-map to replace the whole bloom filter. May be with more
max_entrieswith morenr_hashes. May be fewermax_entrieswith fewernr_hashes.
Quoted 6 lines
Currently, the continuous running bpf prog using this bloom filter does not need to worry about any change in the newer bloom filter configure/setup.
I wonder how that may look like in the custom bpf bloom filter in the bench prog for the map-in-map usage.
You'd have to use BPF_MAP_TYPE_ARRAY for the map-in-map use case.
Quoted 16 lines
Quoted 8 lines
Quoted 7 lines
It is useful to have a default implementation in the kernel for some useful maps like this one that works for most common cases and the bpf user can just use it as get-and-go like all other common bpf maps do.
Quoted 4 lines
I disagree with the premise that Bloom filter is a common and generally useful data structure, tbh. It has its nice niche applications, but its semantics isn't applicable generally, which is why I hesitate to claim that this should live in kernel.
I don't agree the application is nice niche. I have encountered this many times when bumping into networking usecase discussion and not necessary limited to security usage also. Yes, it is not a link-list like data structure but its usage is very common.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 12 lines · Andrii Nakryiko
Quoted 12 lines
Quoted 6 lines
Please see my RFC ([0]). I don't think there is much to coordinate. It could be purely BPF-side code, or BPF + user-space initialization code, depending on the need. It's a simple and beautiful algorithm, which BPF is powerful enough to implement customly and easily.
In practice, the bloom filter will be populated only once by the userspace.
The future update will be done by map-in-map to replace the whole bloom filter. May be with more
max_entrieswith morenr_hashes. May be fewermax_entrieswith fewernr_hashes.
Quoted 8 lines
Quoted 6 lines
Currently, the continuous running bpf prog using this bloom filter does not need to worry about any change in the newer bloom filter configure/setup.
I wonder how that may look like in the custom bpf bloom filter in the bench prog for the map-in-map usage.
You'd have to use
BPF_MAP_TYPE_ARRAYfor the map-in-map use case.
Right, another map is needed. When the user space generates a new bloom filter as inner map, it is likely that it has different number of entries, so the map size is different.
The old and new inner array map need to at least have the same value_size, so an one element array with different value_size will not work.
The inner array map with BPF_F_INNER_MAP can have different max_entries but then there is no inline code lookup generation. It may not be too bad to call it multiple times to lookup a value considering the array_map_lookup_elem will still be directly called without retpoline. The next part is how to learn those "const volatile __u32 bloom_*;" values of the new inner map. I think the max_entires can be obtained
by map_ptr->max_entries. Other vars (e.g. hash_cnt and seed) can
be used as non-const global, allow the update, and a brief moment of inconsistence may be fine.
It all sounds doable but all these small need-to-pay-attention things add up.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 26 lines · Martin KaFai Lau
Quoted 12 lines · Andrii Nakryiko
Quoted 12 lines
Quoted 6 lines
Please see my RFC ([0]). I don't think there is much to coordinate. It could be purely BPF-side code, or BPF + user-space initialization code, depending on the need. It's a simple and beautiful algorithm, which BPF is powerful enough to implement customly and easily.
In practice, the bloom filter will be populated only once by the userspace.
The future update will be done by map-in-map to replace the whole bloom filter. May be with more
max_entrieswith morenr_hashes. May be fewermax_entrieswith fewernr_hashes.Quoted 8 lines
Quoted 6 lines
Currently, the continuous running bpf prog using this bloom filter does not need to worry about any change in the newer bloom filter configure/setup.
I wonder how that may look like in the custom bpf bloom filter in the bench prog for the map-in-map usage.
You'd have to use
BPF_MAP_TYPE_ARRAYfor the map-in-map use case.Right, another map is needed. When the user space generates a new bloom filter as inner map, it is likely that it has different number of entries, so the map size is different.
Quoted 7 lines
The old and new inner array map need to at least have the same
value_size, so an one element array with differentvalue_sizewill not work.The inner array map with
BPF_F_INNER_MAPcan have differentmax_entriesbut then there is no inline code lookup generation. It may not be too bad to call it multiple times to lookup a value considering thearray_map_lookup_elemwill still be directly called without retpoline.
All true, of course, due to generic BPF limitations. In practice, I'd decide what's the maximum size of the bloom filter I'd need and use that as an inner map definition. If I understand correctly, there is going to be only one "active" Bloom filter map and it's generally not that big (few megabytes covers tons of "max_entries"), so I'd just work with maximum expected size.
If I absolutely needed variable-sized filters, I'd consider doing a multi-element array as you suggested, but I'd expect lower performance, as you mentioned.
Quoted 5 lines
The next part is how to learn those "const volatile
__u32bloom_*;" values of the new inner map. I think themax_entirescan be obtained
bymap_ptr->max_entries. Other vars (e.g.hash_cntand seed) can
be used as non-const global, allow the update, and a brief moment of inconsistence may be fine.
For single-element array with fixed value_size I'd put those in first 8 bytes:
struct my_bloom {
__u32 msk;
__u32 seed;
__u64 data[];
}For multi-element BPF_MAP_TYPE_ARRAY I'd put a mask and seed into elem[0].
I'd expect that hash_cnt would be just hard-coded, because as I mentioned before, it determines the probability of false positive, which is what end-users probably care about the most and set upfront, at least they should be coming at this from the perspective "1% of false positives is acceptable" rather than "hmm... 3 hash functions is probably acceptable", no? But if not, first two elements would be taken.
Quoted 3 lines
It all sounds doable but all these small need-to-pay-attention things add up.
Of course, there is always a tension between "make it simple and provide a dedicated BPF helper/BPF map" and "let users implement it on their own". I'm saying I'm not convinced that it has to be the former in this case. Bloom filter is just a glorified bit set, once you have a hashing helper. I don't think we've added BPF_MAP_TYPE_BITSET yet, though it probably would be pretty useful in some cases, just like the Bloom filter. Similarly, we don't have BPF_MAP_TYPE_HASHSET in addition to BPF_MAP_TYPE_HASHMAP. I've seen many cases where HASHMAP is used as HASHSET, yet we didn't have a dedicated map for that either. I'm just curious where we draw the line between what should be added to the kernel for BPF, if there are reasonable ways to avoid that.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 35 lines · Andrii Nakryiko
Quoted 26 lines · Martin KaFai Lau
Quoted 12 lines · Andrii Nakryiko
Quoted 12 lines
Quoted 6 lines
Please see my RFC ([0]). I don't think there is much to coordinate. It could be purely BPF-side code, or BPF + user-space initialization code, depending on the need. It's a simple and beautiful algorithm, which BPF is powerful enough to implement customly and easily.
In practice, the bloom filter will be populated only once by the userspace.
The future update will be done by map-in-map to replace the whole bloom filter. May be with more
max_entrieswith morenr_hashes. May be fewermax_entrieswith fewernr_hashes.Quoted 8 lines
Quoted 6 lines
Currently, the continuous running bpf prog using this bloom filter does not need to worry about any change in the newer bloom filter configure/setup.
I wonder how that may look like in the custom bpf bloom filter in the bench prog for the map-in-map usage.
You'd have to use
BPF_MAP_TYPE_ARRAYfor the map-in-map use case.Right, another map is needed. When the user space generates a new bloom filter as inner map, it is likely that it has different number of entries, so the map size is different.
Quoted 7 lines
The old and new inner array map need to at least have the same
value_size, so an one element array with differentvalue_sizewill not work.The inner array map with
BPF_F_INNER_MAPcan have differentmax_entriesbut then there is no inline code lookup generation. It may not be too bad to call it multiple times to lookup a value considering thearray_map_lookup_elemwill still be directly called without retpoline.
Quoted 6 lines
All true, of course, due to generic BPF limitations. In practice, I'd decide what's the maximum size of the bloom filter I'd need and use that as an inner map definition. If I understand correctly, there is going to be only one "active" Bloom filter map and it's generally not that big (few megabytes covers tons of "
max_entries"), so I'd just work with maximum expected size.
A constant size defeats the configurability/flexibility mem usage argument for the custom bpf map.
Quoted 4 lines
If I absolutely needed variable-sized filters, I'd consider doing a multi-element array as you suggested, but I'd expect lower performance, as you mentioned.
yep. I also expect it will be worse and it reduces the benefit of using bloom filter.
Quoted 8 lines
Quoted 5 lines
The next part is how to learn those "const volatile
__u32bloom_*;" values of the new inner map. I think themax_entirescan be obtained
bymap_ptr->max_entries. Other vars (e.g.hash_cntand seed) can
be used as non-const global, allow the update, and a brief moment of inconsistence may be fine.For single-element array with fixed
value_sizeI'd put those in first 8 bytes:
Quoted 7 lines
struct my_bloom { __u32 msk; __u32 seed; __u64 data[]; }For multi-element
BPF_MAP_TYPE_ARRAYI'd put a mask and seed into elem[0].
Yes, it is the thing that came to my mind also but I was very hesitant even to mention this one extra thing to remind the user that he/she needs to do to avoid potential false negative during the map switching and the user expects it will not happen for bloom filter once the map is fully populated.
Quoted 7 lines
I'd expect that
hash_cntwould be just hard-coded, because as I mentioned before, it determines the probability of false positive, which is what end-users probably care about the most and set upfront, at least they should be coming at this from the perspective "1% of false positives is acceptable" rather than "hmm... 3 hash functions is probably acceptable", no? But if not, first two elements would be taken.
I am not sure a constant hashes/false-positive-rate is always the use case also. but yes, another element in the arraymap will be needed.
Quoted 15 lines
Quoted 2 lines
It all sounds doable but all these small need-to-pay-attention things add up.
Of course, there is always a tension between "make it simple and provide a dedicated BPF helper/BPF map" and "let users implement it on their own". I'm saying I'm not convinced that it has to be the former in this case. Bloom filter is just a glorified bit set, once you have a hashing helper. I don't think we've added
BPF_MAP_TYPE_BITSETyet, though it probably would be pretty useful in some cases, just like the Bloom filter. Similarly, we don't haveBPF_MAP_TYPE_HASHSETin addition toBPF_MAP_TYPE_HASHMAP. I've seen many cases where HASHMAP is used as HASHSET, yet we didn't have a dedicated map for that either. I'm just curious where we draw the line between what should be added to the kernel for BPF, if there are reasonable ways to avoid that.
I think it is pretty clear on the ups and downs on both arguments in terms of performance and configurability and map-in-map.
How to move it forward from here? Is it a must to keep the bloomfilter-like map in pure bpf only and we should stop the current work?
or it is useful to have the kernel bloom filter that provides a get-and-go usage and a consistent experience for user in map-in-map which is the primary use case here. I don't think this is necessarily blocking the custom bpf map effort also.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 9 lines · Martin KaFai Lau
How to move it forward from here? Is it a must to keep the bloomfilter-like map in pure bpf only and we should stop the current work?
or it is useful to have the kernel bloom filter that provides a get-and-go usage and a consistent experience for user in map-in-map which is the primary use case here. I don't think this is necessarily blocking the custom bpf map effort also.
I think map based and helper based bloom filter implementations are far from equivalent. There are pros and cons to both. For example the helper style doesn't have a good way
of query/populate from the user space. If it's a single element array the user space would be forced to allocate huge buffers just to read/write single huge value_size.
With multi element array it's sort-of easier.
mmap-ing the array could help too,
but in either case the user space would need to copy-paste jhash, which is GPL, and that might be more than just inconvenience. We can try siphash in the bpf helper and give it a flag to choose between hash implementations. That helps, but doesn't completely makes them equivalent.
As far as map based bloom filter I think it can combine bitset
and bloomfilter features into one. delete_elem from user space
can be mapped into pop() to clear bits.
Some special value of nr_hashes could mean that no hashing
is applied and 4 or 8 byte key gets modulo of max_entries
and treated as a bit index. Both bpf prog and user space will
have uniform access into such bitset. With nr_hashes >= 1
it will become a bloom filter.
In that sense may be max_entries should be specified in bits
and the map is called bitset. With nr_hashes >= 1 the kernel
would accept key_size > 8 and convert it to bloom filter peek/pop/push. In other wordsnr_hash == 0 bit_idx == key for set/read/clearnr_hashes >= 1 bit_idx[1..N] = hash(key, N) for set/read/clear.
If we could teach the verifier to inline the bit lookup
we potentially can get rid of bloomfilter loop inside the peek(). Then the map would be true bitset without bloomfilter quirks.
Even in such case it's not equivalent to bpf_hash(mem_ptr, size, flags) helper. Thoughts?
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 12 lines · Alexei Starovoitov
Quoted 9 lines · Martin KaFai Lau
How to move it forward from here? Is it a must to keep the bloomfilter-like map in pure bpf only and we should stop the current work?
or it is useful to have the kernel bloom filter that provides a get-and-go usage and a consistent experience for user in map-in-map which is the primary use case here. I don't think this is necessarily blocking the custom bpf map effort also.
Quoted 4 lines
I think map based and helper based bloom filter implementations are far from equivalent. There are pros and cons to both. For example the helper style doesn't have a good way of query/populate from the user space. If it's a single element
I thought about the use from user-space. I'd consider two ways of doing that. One more complicated but with better performance, another simpler but less performant (but in this case less performant is equivalent to in-kernel implementation performance, or still better):
1. Have identical hash function implementation in user-space. In this case Jenkins hash. Then memory-map contents and use exactly the same bloom filter code to set the bits (as I said, once you have hash, it's just a glorified bitset). This has the downside that if there is even a single bit difference between hash produced by kernel and user-space, you are screwed. But can't beat the performance because no syscall overhead.
2. Use BPF_PROG_RUN command to execute custom program that would set one or multiple provided values in the hashset. Just like we argued for BPF timers, BPF program can be a custom "API" that would avoid having separate user-space logic. Pass one or many values through a global variable/array, BPF_PROG_RUN program that would iterate values, calculate hashes, set bits. It actually should be faster than doing BPF_MAP_UPDATE_ELEM syscall for each value. Next proposal will be to add batched update support, of course, so I won't claim victory for the performance argument here. :)
But yes, it needs a bit more (but simple) code, than if the kernel just provided a Bloom filter map out of the box.
Quoted 6 lines
array the user space would be forced to allocate huge buffers just to read/write single huge
value_size.
With multi element array it's sort-of easier.
mmap-ing the array could help too,
but in either case the user space would need to copy-paste jhash, which is GPL, and that might be more than just inconvenience.
From include/linux/jhash.h: "You can use this free for any purpose. It's in the public domain".
Quoted 1 line
We can try siphash in the bpf helper and give it a flag to choose
I did bpf_jhash_mem() just to demonstrate the approach quickly. I think in practice I'd go for a more generic implementation where one of the parameters is enum that specifies which supported hash algorithm is used. It's easier to extend that:
u64 bpf_hash_mem(const void *data, u32 sz, u32 seed, enum bpf_hash_algo algo);
enum bpf_hash_algo {
XOR = 0,
JENKINS = 1,
MURMUR3 = 2,
...
}
Note the XOR case. If we specify it as "xor u64 values, where the last <8 bytes are zero extended", it will come useful below for your proposal.
Quoted 2 lines
between hash implementations. That helps, but doesn't completely makes them equivalent.
I don't claim that implementing and using a custom Bloom filter will be easier to use in all situations. I think the best we can strive for is making it not much harder, and I think in this case it is. Of course we can come up with a bunch of situations where doing it with pure BPF isn't possible to do equivalently (like map-in-map with dynamically sized bit size, well, sorry, BPF verifier can't validate stuff like that). Dedicated BPF map or helper (as a general case, not just this one) will pretty much always going to be easier to use just because it's a dedicated and tailored API.
Quoted 12 lines
As far as map based bloom filter I think it can combine bitset and bloomfilter features into one.
delete_elemfrom user space can be mapped intopop()to clear bits.
Some special value ofnr_hashescould mean that no hashing is applied and 4 or 8 byte key gets modulo ofmax_entriesand treated as a bit index. Both bpf prog and user space will have uniform access into such bitset. Withnr_hashes>= 1 it will become a bloom filter.
In that sense may bemax_entriesshould be specified in bits and the map is called bitset. Withnr_hashes>= 1 the kernel would acceptkey_size> 8 and convert it to bloom filter
Quoted 8 lines
peek/pop/push. In other words
nr_hash== 0bit_idx== key for set/read/clearnr_hashes>= 1 bit_idx[1..N] =hash(key, N)for set/read/clear.
If we could teach the verifier to inline the bit lookup
we potentially can get rid of bloomfilter loop inside thepeek(). Then the map would be true bitset without bloomfilter quirks.
Even in such case it's not equivalent tobpf_hash(mem_ptr, size, flags)helper. Thoughts?
Sounds a bit complicated from end-user's perspective, tbh, but bitset map (with generalization for bloom filter) sounds a bit more widely useful. See above for the bpf_hash_algo proposal. If we allow to specify nr_hashes and hash algorithm, then with XOR as defined above and nr_hash = 1, you'll get just bitset behavior with not extra restrictions on key size: you could have 1, 2, 4, 8 and more bytes (where with more bytes it's some suboptimal bloom filter with one hash function, not sure why you'd do that).
The biggest quirk is defining that XOR hashes in chunks of 8 bytes (with zero-extending anything that is not a multiple of 8 bytes length). We can do special "only 1, 2, 4, and 8 bytes are supported", of course, but it will be special-cased internally. Not sure which one is cleaner.
While writing this, another thought was to have a "NOOP" (or "IDENTITY") hash, where we say that we treat bytes as one huge number. Obviously then we truncate to the actual bitmap size, which just basically means "use up to lower 8 bytes as a number". But it sucks for big-endian, because to make it sane we'd need to take last "up to 8 bytes", which obviously sounds convoluted. So I don't know, just a thought.
If we do the map, though, regardless if it's bitset or bloom specifically. Maybe we should consider modeling as actual bpf_map_lookup_elem(), where the key is a pointer to whatever we are hashing and looking up? It makes much more sense, that's how people model sets based on maps: key is the element you are looking up, value is either true/false or meaningless (at least for me it felt much more natural that you are looking up by key, not by value). In this case, what if on successful lookup we return a pointer to some fixed u8/u32/u64 location in the kernel, some dedicated static variable shared between all maps. So NULL means "element is not in a set", non-NULL means it is in the set. Ideally we'd prevent such element to be written to, but it might be too hard to do that as just one exception here, don't know.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 72 lines · Andrii Nakryiko
Quoted 5 lines · Alexei Starovoitov
Quoted 4 lines · Martin KaFai Lau
How to move it forward from here? Is it a must to keep the bloomfilter-like map in pure bpf only and we should stop the current work?
Quoted 8 lines
Quoted 4 lines
or it is useful to have the kernel bloom filter that provides a get-and-go usage and a consistent experience for user in map-in-map which is the primary use case here. I don't think this is necessarily blocking the custom bpf map effort also.
I think map based and helper based bloom filter implementations are far from equivalent. There are pros and cons to both. For example the helper style doesn't have a good way of query/populate from the user space. If it's a single element
I thought about the use from user-space. I'd consider two ways of doing that. One more complicated but with better performance, another simpler but less performant (but in this case less performant is equivalent to in-kernel implementation performance, or still better):
1. Have identical hash function implementation in user-space. In this case Jenkins hash. Then memory-map contents and use exactly the same bloom filter code to set the bits (as I said, once you have hash, it's just a glorified bitset). This has the downside that if there is even a single bit difference between hash produced by kernel and user-space, you are screwed. But can't beat the performance because no syscall overhead.
2. Use
BPF_PROG_RUNcommand to execute custom program that would set one or multiple provided values in the hashset. Just like we argued for BPF timers, BPF program can be a custom "API" that would avoid having separate user-space logic. Pass one or many values through a global variable/array,BPF_PROG_RUNprogram that would iterate values, calculate hashes, set bits. It actually should be faster than doingBPF_MAP_UPDATE_ELEMsyscall for each value. Next proposal will be to add batched update support, of course, so I won't claim victory for the performance argument here. :)But yes, it needs a bit more (but simple) code, than if the kernel just provided a Bloom filter map out of the box.
Quoted 6 lines
array the user space would be forced to allocate huge buffers just to read/write single huge
value_size.
With multi element array it's sort-of easier.
mmap-ing the array could help too,
but in either case the user space would need to copy-paste jhash, which is GPL, and that might be more than just inconvenience.From
include/linux/jhash.h: "You can use this free for any purpose.
It's in the public domain".Quoted 1 line
We can try siphash in the bpf helper and give it a flag to choose
I did
bpf_jhash_mem()just to demonstrate the approach quickly. I think in practice I'd go for a more generic implementation where one of the parameters is enum that specifies which supported hash algorithm is used. It's easier to extend that:u64
bpf_hash_mem(const void *data, u32 sz, u32 seed, enum bpf_hash_algo algo);enum bpf_hash_algo { XOR = 0, JENKINS = 1, MURMUR3 = 2, ... }Note the XOR case. If we specify it as "xor u64 values, where the last <8 bytes are zero extended", it will come useful below for your proposal.
Quoted 2 lines
between hash implementations. That helps, but doesn't completely makes them equivalent.
Quoted 10 lines
I don't claim that implementing and using a custom Bloom filter will be easier to use in all situations. I think the best we can strive for is making it not much harder, and I think in this case it is. Of course we can come up with a bunch of situations where doing it with pure BPF isn't possible to do equivalently (like map-in-map with dynamically sized bit size, well, sorry, BPF verifier can't validate stuff like that). Dedicated BPF map or helper (as a general case, not just this one) will pretty much always going to be easier to use just because it's a dedicated and tailored API.
To me, it seems like we get the best of both worlds by using both of these two ideas for the bloom filter. For developers who would like
to use a general bloom filter without having to do any extra implementation work or having to understand how bloom filters are implemented, they could use the custom bloom filter map with minimal effort. For developers who would like to customize their bloom filter to something more specific or fine-tuned, they could use craft their own bloom filter in an ebpf program. To me, these two directions don't seem mutually exclusive.
Quoted 11 lines
Quoted 11 lines
As far as map based bloom filter I think it can combine bitset and bloomfilter features into one.
delete_elemfrom user space can be mapped intopop()to clear bits.
Some special value ofnr_hashescould mean that no hashing is applied and 4 or 8 byte key gets modulo ofmax_entriesand treated as a bit index. Both bpf prog and user space will have uniform access into such bitset. Withnr_hashes>= 1 it will become a bloom filter.
In that sense may bemax_entriesshould be specified in bits and the map is called bitset. Withnr_hashes>= 1 the kernel would acceptkey_size> 8 and convert it to bloom filter
Quoted 8 lines
Quoted 8 lines
peek/pop/push. In other words
nr_hash== 0bit_idx== key for set/read/clearnr_hashes>= 1 bit_idx[1..N] =hash(key, N)for set/read/clear.
If we could teach the verifier to inline the bit lookup
we potentially can get rid of bloomfilter loop inside thepeek(). Then the map would be true bitset without bloomfilter quirks.
Even in such case it's not equivalent tobpf_hash(mem_ptr, size, flags)helper. Thoughts?
This is an interesting suggestion; to me, it seems like the APIs and code would be more straightforward if the bitset and the bloom filter were separate maps. With having max_entries be specified in bits, I think this also relies on the user to make an educated call on the optimal number of bits to use for their bloom filter, instead of passing in the number of entries they expect to have and having the bit size automatically calculated according to a mathematically optimized equation. I am open to this idea though.
Quoted 23 lines
Sounds a bit complicated from end-user's perspective, tbh, but bitset map (with generalization for bloom filter) sounds a bit more widely useful. See above for the
bpf_hash_algoproposal. If we allow to specifynr_hashesand hash algorithm, then with XOR as defined above andnr_hash= 1, you'll get just bitset behavior with not extra restrictions on key size: you could have 1, 2, 4, 8 and more bytes (where with more bytes it's some suboptimal bloom filter with one hash function, not sure why you'd do that).The biggest quirk is defining that XOR hashes in chunks of 8 bytes (with zero-extending anything that is not a multiple of 8 bytes length). We can do special "only 1, 2, 4, and 8 bytes are supported", of course, but it will be special-cased internally. Not sure which one is cleaner.
While writing this, another thought was to have a "NOOP" (or "IDENTITY") hash, where we say that we treat bytes as one huge number. Obviously then we truncate to the actual bitmap size, which just basically means "use up to lower 8 bytes as a number". But it sucks for big-endian, because to make it sane we'd need to take last "up to 8 bytes", which obviously sounds convoluted. So I don't know, just a thought.
Quoted 11 lines
If we do the map, though, regardless if it's bitset or bloom specifically. Maybe we should consider modeling as actual
bpf_map_lookup_elem(), where the key is a pointer to whatever we are hashing and looking up? It makes much more sense, that's how people model sets based on maps: key is the element you are looking up, value is either true/false or meaningless (at least for me it felt much more natural that you are looking up by key, not by value). In this case, what if on successful lookup we return a pointer to some fixed u8/u32/u64 location in the kernel, some dedicated static variable shared between all maps. So NULL means "element is not in a set", non-NULL means it is in the set.
I think this would then also require that the bpf_map_update_elem() API from the userspace side would have to pass in a valid memory address for the "value". I understand what you're saying though about it feeling more natural
that the "key" is the element here; I agree but there doesn't seem to be a clean way of doing this - I think maybe one viable approach would be allowing map_update_elem to pass in a NULL value in the kernel if the map is a non-associative map, and refactoring the push_elem/peek_elem API so that the element can represent either the key or the value.
Quoted 3 lines
Ideally we'd prevent such element to
be written to, but it might be too hard to do that as just one exception here, don't know.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 6 lines · Joanne Koong
Quoted 6 lines
Quoted 6 lines
As far as map based bloom filter I think it can combine bitset and bloomfilter features into one.
delete_elemfrom user space can be mapped intopop()to clear bits.
Some special value ofnr_hashescould mean that no hashing is applied and 4 or 8 byte key gets modulo ofmax_entriesand treated as a bit index. Both bpf prog and user space will
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
have uniform access into such bitset. With
nr_hashes>= 1 it will become a bloom filter.
In that sense may bemax_entriesshould be specified in bits and the map is called bitset. Withnr_hashes>= 1 the kernel would acceptkey_size> 8 and convert it to bloom filter peek/pop/push. In other wordsnr_hash== 0bit_idx== key for set/read/clearnr_hashes>= 1 bit_idx[1..N] =hash(key, N)for set/read/clear.
I like this bitset+nr_hash semantic, then max_entries logcially follows the number of bits.
Quoted 11 lines
Quoted 11 lines
If we do the map, though, regardless if it's bitset or bloom specifically. Maybe we should consider modeling as actual
bpf_map_lookup_elem(), where the key is a pointer to whatever we are hashing and looking up? It makes much more sense, that's how people model sets based on maps: key is the element you are looking up, value is either true/false or meaningless (at least for me it felt much more natural that you are looking up by key, not by value). In this case, what if on successful lookup we return a pointer to some fixed u8/u32/u64 location in the kernel, some dedicated static variable shared between all maps. So NULL means "element is not in a set", non-NULL means it is in the set.
Quoted 11 lines
I think this would then also require that the
bpf_map_update_elem()API from
the userspace side would have to pass in a valid memory address for the
"value". I understand what you're saying though about it feeling more natural that the "key" is the element here; I agree but there doesn't seem to be a
clean way of doing this - I think maybe one viable approach would be allowingmap_update_elemto pass in a NULL value in the kernel if the map is a non-associative map, and refactoring the push_elem/peek_elem API so that the element can represent either the key or the value.Quoted 3 lines
Ideally we'd prevent such element to
be written to, but it might be too hard to do that as just one exception here, don't know.
I don't mind key or value also. With nr_hash == 0 and key is the bit_idx, it may be more correct to say that bit is indeed 0/1 instead of returning the bit_idx back.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
In reply to Joanne KoongQuoted 85 lines · Joanne Koong
Quoted 72 lines · Andrii Nakryiko
Quoted 5 lines · Alexei Starovoitov
Quoted 4 lines · Martin KaFai Lau
How to move it forward from here? Is it a must to keep the bloomfilter-like map in pure bpf only and we should stop the current work?
Quoted 8 lines
Quoted 4 lines
or it is useful to have the kernel bloom filter that provides a get-and-go usage and a consistent experience for user in map-in-map which is the primary use case here. I don't think this is necessarily blocking the custom bpf map effort also.
I think map based and helper based bloom filter implementations are far from equivalent. There are pros and cons to both. For example the helper style doesn't have a good way of query/populate from the user space. If it's a single element
I thought about the use from user-space. I'd consider two ways of doing that. One more complicated but with better performance, another simpler but less performant (but in this case less performant is equivalent to in-kernel implementation performance, or still better):
1. Have identical hash function implementation in user-space. In this case Jenkins hash. Then memory-map contents and use exactly the same bloom filter code to set the bits (as I said, once you have hash, it's just a glorified bitset). This has the downside that if there is even a single bit difference between hash produced by kernel and user-space, you are screwed. But can't beat the performance because no syscall overhead.
2. Use
BPF_PROG_RUNcommand to execute custom program that would set one or multiple provided values in the hashset. Just like we argued for BPF timers, BPF program can be a custom "API" that would avoid having separate user-space logic. Pass one or many values through a global variable/array,BPF_PROG_RUNprogram that would iterate values, calculate hashes, set bits. It actually should be faster than doingBPF_MAP_UPDATE_ELEMsyscall for each value. Next proposal will be to add batched update support, of course, so I won't claim victory for the performance argument here. :)But yes, it needs a bit more (but simple) code, than if the kernel just provided a Bloom filter map out of the box.
Quoted 6 lines
array the user space would be forced to allocate huge buffers just to read/write single huge
value_size.
With multi element array it's sort-of easier.
mmap-ing the array could help too,
but in either case the user space would need to copy-paste jhash, which is GPL, and that might be more than just inconvenience.From
include/linux/jhash.h: "You can use this free for any purpose.
It's in the public domain".Quoted 1 line
We can try siphash in the bpf helper and give it a flag to choose
I did
bpf_jhash_mem()just to demonstrate the approach quickly. I think in practice I'd go for a more generic implementation where one of the parameters is enum that specifies which supported hash algorithm is used. It's easier to extend that:u64
bpf_hash_mem(const void *data, u32 sz, u32 seed, enum bpf_hash_algo algo);enum bpf_hash_algo { XOR = 0, JENKINS = 1, MURMUR3 = 2, ... }Note the XOR case. If we specify it as "xor u64 values, where the last <8 bytes are zero extended", it will come useful below for your proposal.
Quoted 2 lines
between hash implementations. That helps, but doesn't completely makes them equivalent.
Quoted 10 lines
I don't claim that implementing and using a custom Bloom filter will be easier to use in all situations. I think the best we can strive for is making it not much harder, and I think in this case it is. Of course we can come up with a bunch of situations where doing it with pure BPF isn't possible to do equivalently (like map-in-map with dynamically sized bit size, well, sorry, BPF verifier can't validate stuff like that). Dedicated BPF map or helper (as a general case, not just this one) will pretty much always going to be easier to use just because it's a dedicated and tailored API.
Quoted 9 lines
To me, it seems like we get the best of both worlds by using both of these two ideas for the bloom filter. For developers who would like to use a general bloom filter without having to do any extra implementation work
or having to understand how bloom filters are implemented, they could use the custom bloom filter map with minimal effort. For developers who would like to customize their bloom filter to something more specific or fine-tuned, they could use craft their own bloom filter in an ebpf program. To me, these two directions don't seem mutually exclusive.
They are not mutually exclusive, of course, but adding stuff to the kernel has its maintenance costs.
Quoted 20 lines
Quoted 12 lines
Quoted 12 lines
As far as map based bloom filter I think it can combine bitset and bloomfilter features into one.
delete_elemfrom user space can be mapped intopop()to clear bits.
Some special value ofnr_hashescould mean that no hashing is applied and 4 or 8 byte key gets modulo ofmax_entriesand treated as a bit index. Both bpf prog and user space will have uniform access into such bitset. Withnr_hashes>= 1 it will become a bloom filter.
In that sense may bemax_entriesshould be specified in bits and the map is called bitset. Withnr_hashes>= 1 the kernel would acceptkey_size> 8 and convert it to bloom filterQuoted 8 lines
Quoted 8 lines
peek/pop/push. In other words
nr_hash== 0bit_idx== key for set/read/clearnr_hashes>= 1 bit_idx[1..N] =hash(key, N)for set/read/clear.
If we could teach the verifier to inline the bit lookup
we potentially can get rid of bloomfilter loop inside thepeek(). Then the map would be true bitset without bloomfilter quirks.
Even in such case it's not equivalent tobpf_hash(mem_ptr, size, flags)helper. Thoughts?
Quoted 12 lines
This is an interesting suggestion; to me, it seems like the APIs and code would be
more straightforward if the bitset and the bloom filter were separate maps. With havingmax_entriesbe specified in bits, I think this also relies on the
user to make an educated call on the optimal number of bits to use for their bloom
filter, instead of passing in the number of entries they expect to have and having the
bit size automatically calculated according to a mathematically optimized equation.
I am open to this idea though.
We can provide a macro that will calculate mathematically optimized value based on desired number of unique entries and hash functions. E.g.:
#define BPF_BLOOM_FILTER_BYTE_SZ(nr_uniq_entries, nr_hash_funcs) (nr_uniq_entires * nr_hash_funcs / 5 * 7 / 8)
Kernel code can round up to closest power-of-two internally to make this simpler. So if users don't care or don't know, they'll use BPF_BPLOOM_FILTER_BYTE_SZ() macro, but if they know better, they'll just specify desired amount of bytes.
Quoted 35 lines
Quoted 24 lines
Sounds a bit complicated from end-user's perspective, tbh, but bitset map (with generalization for bloom filter) sounds a bit more widely useful. See above for the
bpf_hash_algoproposal. If we allow to specifynr_hashesand hash algorithm, then with XOR as defined above andnr_hash= 1, you'll get just bitset behavior with not extra restrictions on key size: you could have 1, 2, 4, 8 and more bytes (where with more bytes it's some suboptimal bloom filter with one hash function, not sure why you'd do that).The biggest quirk is defining that XOR hashes in chunks of 8 bytes (with zero-extending anything that is not a multiple of 8 bytes length). We can do special "only 1, 2, 4, and 8 bytes are supported", of course, but it will be special-cased internally. Not sure which one is cleaner.
While writing this, another thought was to have a "NOOP" (or "IDENTITY") hash, where we say that we treat bytes as one huge number. Obviously then we truncate to the actual bitmap size, which just basically means "use up to lower 8 bytes as a number". But it sucks for big-endian, because to make it sane we'd need to take last "up to 8 bytes", which obviously sounds convoluted. So I don't know, just a thought.
Quoted 11 lines
If we do the map, though, regardless if it's bitset or bloom specifically. Maybe we should consider modeling as actual
bpf_map_lookup_elem(), where the key is a pointer to whatever we are hashing and looking up? It makes much more sense, that's how people model sets based on maps: key is the element you are looking up, value is either true/false or meaningless (at least for me it felt much more natural that you are looking up by key, not by value). In this case, what if on successful lookup we return a pointer to some fixed u8/u32/u64 location in the kernel, some dedicated static variable shared between all maps. So NULL means "element is not in a set", non-NULL means it is in the set.
Quoted 12 lines
I think this would then also require that the
bpf_map_update_elem()API from the userspace side would have to pass in a valid memory address for the "value".
I understand what you're saying though about it feeling more natural that the "key" is the element here; I agree but there doesn't seem to be a clean way
of doing this - I think maybe one viable approach would be allowingmap_update_elem
to pass in a NULL value in the kernel if the map is a non-associative map, and refactoring the
push_elem/peek_elem API so that the element can represent either the key or the value.
Yeah, we can allow value to be NULL (and key non-NULL). But why push/peek if we are talking about using standard lookup_elem/update_elem (and maybe even delete_elem which will reset bits to 0)?
Quoted 3 lines
Quoted 3 lines
Ideally we'd prevent such element to
be written to, but it might be too hard to do that as just one exception here, don't know.
BTW, that nr_hash_funcs field in UAPI and in libbpf was still bothering me. I'd feel better if we generalize this to future map needs and make it generic. How about adding "u32 map_extra;" field to UAPI (as a new field, so it's available for all maps, including map-in-maps). The meaning of that field would be per-map-type extra flags/values/etc. In this case we can define that map_extra for BLOOM_FILTER it would encode number of hash functions. If we ok adding hash function enum that I proposed for bpf_hash_mem() helper, we can also include that into map_extra. We can reserve lower N bits for number of hash functions and then next few bits would be reserved for hash algo enum.
So then you'd define map (in libbpf syntax) pretty naturally as:
struct {
__uint(type, BPF_MAP_TYPE_BLOOM_FILTER); /* or BITSET, don't know
which way this is going */
....
__uint(map_extra, BPF_HASH_SHA256 | 3); /* 3 x SHA256 hash functions */
} my_bloom_filter SEC(".maps");BPF_HASH_SHA256 would be defined as something like 0x{1,2,4,etc}0, leaving lower 4 bits for nr_hash_funcs.
And then I'd have no problem supporting map_extra field for any map definition, with bpf_map__map_extra() and bpf_map__set_map_extra() getter/setter.
map_flags is different in that it's partially shared by all map types (e.g., BPF_F_RDONLY_PROG, BPF_F_INNER_MAP, BPF_F_NUMA_NODE can be specified for lots of different types).
Naming is obviously up for discussion.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 132 lines · Andrii Nakryiko
On Thu, Sep 23, 2021 at 3:28 PM Joanne Koong <[email protected]> wrote:
Quoted 82 lines · Andrii Nakryiko
Quoted 72 lines
Quoted 5 lines · Alexei Starovoitov
Quoted 4 lines · Martin KaFai Lau
How to move it forward from here? Is it a must to keep the bloomfilter-like map in pure bpf only and we should stop the current work?
Quoted 8 lines
Quoted 4 lines
or it is useful to have the kernel bloom filter that provides a get-and-go usage and a consistent experience for user in map-in-map which is the primary use case here. I don't think this is necessarily blocking the custom bpf map effort also.
I think map based and helper based bloom filter implementations are far from equivalent. There are pros and cons to both. For example the helper style doesn't have a good way of query/populate from the user space. If it's a single element
I thought about the use from user-space. I'd consider two ways of doing that. One more complicated but with better performance, another simpler but less performant (but in this case less performant is equivalent to in-kernel implementation performance, or still better):
1. Have identical hash function implementation in user-space. In this case Jenkins hash. Then memory-map contents and use exactly the same bloom filter code to set the bits (as I said, once you have hash, it's just a glorified bitset). This has the downside that if there is even a single bit difference between hash produced by kernel and user-space, you are screwed. But can't beat the performance because no syscall overhead.
2. Use
BPF_PROG_RUNcommand to execute custom program that would set one or multiple provided values in the hashset. Just like we argued for BPF timers, BPF program can be a custom "API" that would avoid having separate user-space logic. Pass one or many values through a global variable/array,BPF_PROG_RUNprogram that would iterate values, calculate hashes, set bits. It actually should be faster than doingBPF_MAP_UPDATE_ELEMsyscall for each value. Next proposal will be to add batched update support, of course, so I won't claim victory for the performance argument here. :)But yes, it needs a bit more (but simple) code, than if the kernel just provided a Bloom filter map out of the box.
Quoted 6 lines
array the user space would be forced to allocate huge buffers just to read/write single huge
value_size.
With multi element array it's sort-of easier.
mmap-ing the array could help too,
but in either case the user space would need to copy-paste jhash, which is GPL, and that might be more than just inconvenience.From
include/linux/jhash.h: "You can use this free for any purpose.
It's in the public domain".Quoted 1 line
We can try siphash in the bpf helper and give it a flag to choose
I did
bpf_jhash_mem()just to demonstrate the approach quickly. I think in practice I'd go for a more generic implementation where one of the parameters is enum that specifies which supported hash algorithm is used. It's easier to extend that:u64
bpf_hash_mem(const void *data, u32 sz, u32 seed, enum bpf_hash_algo algo);enum bpf_hash_algo { XOR = 0, JENKINS = 1, MURMUR3 = 2, ... }Note the XOR case. If we specify it as "xor u64 values, where the last <8 bytes are zero extended", it will come useful below for your proposal.
Quoted 2 lines
between hash implementations. That helps, but doesn't completely makes them equivalent.
Quoted 10 lines
I don't claim that implementing and using a custom Bloom filter will be easier to use in all situations. I think the best we can strive for is making it not much harder, and I think in this case it is. Of course we can come up with a bunch of situations where doing it with pure BPF isn't possible to do equivalently (like map-in-map with dynamically sized bit size, well, sorry, BPF verifier can't validate stuff like that). Dedicated BPF map or helper (as a general case, not just this one) will pretty much always going to be easier to use just because it's a dedicated and tailored API.
Quoted 9 lines
To me, it seems like we get the best of both worlds by using both of these two ideas for the bloom filter. For developers who would like to use a general bloom filter without having to do any extra implementation work
or having to understand how bloom filters are implemented, they could use the custom bloom filter map with minimal effort. For developers who would like to customize their bloom filter to something more specific or fine-tuned, they could use craft their own bloom filter in an ebpf program. To me, these two directions don't seem mutually exclusive.They are not mutually exclusive, of course, but adding stuff to the kernel has its maintenance costs.
Quoted 19 lines
Quoted 11 lines
Quoted 11 lines
As far as map based bloom filter I think it can combine bitset and bloomfilter features into one.
delete_elemfrom user space can be mapped intopop()to clear bits.
Some special value ofnr_hashescould mean that no hashing is applied and 4 or 8 byte key gets modulo ofmax_entriesand treated as a bit index. Both bpf prog and user space will have uniform access into such bitset. Withnr_hashes>= 1 it will become a bloom filter.
In that sense may bemax_entriesshould be specified in bits and the map is called bitset. Withnr_hashes>= 1 the kernel would acceptkey_size> 8 and convert it to bloom filterQuoted 8 lines
Quoted 8 lines
peek/pop/push. In other words
nr_hash== 0bit_idx== key for set/read/clearnr_hashes>= 1 bit_idx[1..N] =hash(key, N)for set/read/clear.
If we could teach the verifier to inline the bit lookup
we potentially can get rid of bloomfilter loop inside thepeek(). Then the map would be true bitset without bloomfilter quirks.
Even in such case it's not equivalent tobpf_hash(mem_ptr, size, flags)helper. Thoughts?Quoted 12 lines
This is an interesting suggestion; to me, it seems like the APIs and code would be
more straightforward if the bitset and the bloom filter were separate maps. With havingmax_entriesbe specified in bits, I think this also relies on the
user to make an educated call on the optimal number of bits to use for their bloom
filter, instead of passing in the number of entries they expect to have and having the
bit size automatically calculated according to a mathematically optimized equation.
I am open to this idea though.We can provide a macro that will calculate mathematically optimized value based on desired number of unique entries and hash functions. E.g.:
Quoted 7 lines
#define
BPF_BLOOM_FILTER_BYTE_SZ(nr_uniq_entries, nr_hash_funcs)(nr_uniq_entires*nr_hash_funcs/ 5 * 7 / 8)Kernel code can round up to closest power-of-two internally to make this simpler. So if users don't care or don't know, they'll use
BPF_BPLOOM_FILTER_BYTE_SZ()macro, but if they know better, they'll just specify desired amount of bytes.
Sounds great!
Quoted 46 lines
Quoted 34 lines
Quoted 23 lines
Sounds a bit complicated from end-user's perspective, tbh, but bitset map (with generalization for bloom filter) sounds a bit more widely useful. See above for the
bpf_hash_algoproposal. If we allow to specifynr_hashesand hash algorithm, then with XOR as defined above andnr_hash= 1, you'll get just bitset behavior with not extra restrictions on key size: you could have 1, 2, 4, 8 and more bytes (where with more bytes it's some suboptimal bloom filter with one hash function, not sure why you'd do that).The biggest quirk is defining that XOR hashes in chunks of 8 bytes (with zero-extending anything that is not a multiple of 8 bytes length). We can do special "only 1, 2, 4, and 8 bytes are supported", of course, but it will be special-cased internally. Not sure which one is cleaner.
While writing this, another thought was to have a "NOOP" (or "IDENTITY") hash, where we say that we treat bytes as one huge number. Obviously then we truncate to the actual bitmap size, which just basically means "use up to lower 8 bytes as a number". But it sucks for big-endian, because to make it sane we'd need to take last "up to 8 bytes", which obviously sounds convoluted. So I don't know, just a thought.
Quoted 11 lines
If we do the map, though, regardless if it's bitset or bloom specifically. Maybe we should consider modeling as actual
bpf_map_lookup_elem(), where the key is a pointer to whatever we are hashing and looking up? It makes much more sense, that's how people model sets based on maps: key is the element you are looking up, value is either true/false or meaningless (at least for me it felt much more natural that you are looking up by key, not by value). In this case, what if on successful lookup we return a pointer to some fixed u8/u32/u64 location in the kernel, some dedicated static variable shared between all maps. So NULL means "element is not in a set", non-NULL means it is in the set.Quoted 12 lines
I think this would then also require that the
bpf_map_update_elem()API from the userspace side would have to pass in a valid memory address for the "value".
I understand what you're saying though about it feeling more natural that the "key" is the element here; I agree but there doesn't seem to be a clean way
of doing this - I think maybe one viable approach would be allowingmap_update_elem
to pass in a NULL value in the kernel if the map is a non-associative map, and refactoring the
push_elem/peek_elem API so that the element can represent either the key or the value.
Quoted 4 lines
Yeah, we can allow value to be NULL (and key non-NULL). But why push/peek if we are talking about using standard lookup_elem/update_elem (and maybe even
delete_elemwhich will reset bits to 0)?
In the syscall layer where we handle lookup_elem, we call map->ops->map_lookup_elem and expect that the ptr we get back is a ptr to the value associated with the key (and if the ptr is NULL we treat that as an error).
Instead of adding special-casing for bloom filter maps to treat a NULL ptr value as something that's okay, it seems cleaner to repurpose peek to be the API we use for all non-associative map types.
Quoted 31 lines
Quoted 3 lines
Quoted 3 lines
Ideally we'd prevent such element to
be written to, but it might be too hard to do that as just one exception here, don't know.BTW, that
nr_hash_funcsfield in UAPI and in libbpf was still bothering me. I'd feel better if we generalize this to future map needs and make it generic. How about adding "u32map_extra;" field to UAPI (as a new field, so it's available for all maps, including map-in-maps). The meaning of that field would be per-map-type extra flags/values/etc. In this case we can define thatmap_extraforBLOOM_FILTERit would encode number of hash functions. If we ok adding hash function enum that I proposed forbpf_hash_mem()helper, we can also include that intomap_extra. We can reserve lower N bits for number of hash functions and then next few bits would be reserved for hash algo enum.So then you'd define map (in libbpf syntax) pretty naturally as:
struct {
__uint(type, BPF_MAP_TYPE_BLOOM_FILTER); /* or BITSET, don't know
which way this is going */.... __uint(map_extra, BPF_HASH_SHA256 | 3); /* 3 x SHA256 hash functions */ } my_bloom_filter SEC(".maps");
BPF_HASH_SHA256would be defined as something like 0x{1,2,4,etc}0, leaving lower 4 bits fornr_hash_funcs.And then I'd have no problem supporting
map_extrafield for any map definition, withbpf_map__map_extra()andbpf_map__set_map_extra()getter/setter.
Quoted 5 lines
map_flagsis different in that it's partially shared by all map types (e.g.,BPF_F_RDONLY_PROG,BPF_F_INNER_MAP,BPF_F_NUMA_NODEcan be specified for lots of different types).Naming is obviously up for discussion.
I love this idea!
To make sure we're all aligned on the direction of this, for v4 I'm going to make the following changes:
* Make the map a bitset + bloom filter map, depending on how many hashes are passed in
* Write tests for the bitset functionality of the map
* Change nr_hashes to a more generic "u32 map_extra"
* Incorporate some of Andrii's changes to the benchmarks for accounting + measuring
* Add more documentation regarding the optimal bitmap size equation "nr_unique_entries * nr_hash_funcs / 5 * 7 / 8" to clear up any confusion
Thanks for the discussion on this, Martin, Andrii, and Alexei!
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 57 lines · Joanne Koong
Quoted 54 lines · Andrii Nakryiko
On Thu, Sep 23, 2021 at 3:28 PM Joanne Koong <[email protected]> wrote:
Quoted 51 lines · Andrii Nakryiko
Quoted 51 lines
Quoted 5 lines · Alexei Starovoitov
Quoted 4 lines · Martin KaFai Lau
How to move it forward from here? Is it a must to keep the bloomfilter-like map in pure bpf only and we should stop the current work?
Quoted 8 lines
Quoted 4 lines
or it is useful to have the kernel bloom filter that provides a get-and-go usage and a consistent experience for user in map-in-map which is the primary use case here. I don't think this is necessarily blocking the custom bpf map effort also.
I think map based and helper based bloom filter implementations are far from equivalent. There are pros and cons to both. For example the helper style doesn't have a good way of query/populate from the user space. If it's a single element
I thought about the use from user-space. I'd consider two ways of doing that. One more complicated but with better performance, another simpler but less performant (but in this case less performant is equivalent to in-kernel implementation performance, or still better):
1. Have identical hash function implementation in user-space. In this case Jenkins hash. Then memory-map contents and use exactly the same bloom filter code to set the bits (as I said, once you have hash, it's just a glorified bitset). This has the downside that if there is even a single bit difference between hash produced by kernel and user-space, you are screwed. But can't beat the performance because no syscall overhead.
2. Use
BPF_PROG_RUNcommand to execute custom program that would set one or multiple provided values in the hashset. Just like we argued for BPF timers, BPF program can be a custom "API" that would avoid having separate user-space logic. Pass one or many values through a global variable/array,BPF_PROG_RUNprogram that would iterate values, calculate hashes, set bits. It actually should be faster than doingBPF_MAP_UPDATE_ELEMsyscall for each value. Next proposal will be to add batched update support, of course, so I won't claim victory for the performance argument here. :)But yes, it needs a bit more (but simple) code, than if the kernel just provided a Bloom filter map out of the box.
Quoted 6 lines
array the user space would be forced to allocate huge buffers just to read/write single huge
value_size.
With multi element array it's sort-of easier.
mmap-ing the array could help too,
but in either case the user space would need to copy-paste jhash, which is GPL, and that might be more than just inconvenience.From
include/linux/jhash.h: "You can use this free for any purpose.
It's in the public domain".Quoted 1 line
We can try siphash in the bpf helper and give it a flag to choose
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
I did
bpf_jhash_mem()just to demonstrate the approach quickly. I think in practice I'd go for a more generic implementation where one of the parameters is enum that specifies which supported hash algorithm is used. It's easier to extend that:u64
bpf_hash_mem(const void *data, u32 sz, u32 seed, enum bpf_hash_algo algo);enum
bpf_hash_algo{
btw, once we have this for Bloom filter and BPF helper, we should consider adding support for that to STACK_TRACE map (we've seen a considerable amount of hash collisions in practice), so letting users choose a hash function would be great for it. I'd use the proposed map_extra for that as well. It's obviously all besides the Bloom filter discussion, just point out to not forget later.
Quoted 134 lines
Quoted 70 lines
Quoted 23 lines
Quoted 13 lines
XOR = 0, JENKINS = 1, MURMUR3 = 2, ... }Note the XOR case. If we specify it as "xor u64 values, where the last <8 bytes are zero extended", it will come useful below for your proposal.
Quoted 2 lines
between hash implementations. That helps, but doesn't completely makes them equivalent.
Quoted 10 lines
I don't claim that implementing and using a custom Bloom filter will be easier to use in all situations. I think the best we can strive for is making it not much harder, and I think in this case it is. Of course we can come up with a bunch of situations where doing it with pure BPF isn't possible to do equivalently (like map-in-map with dynamically sized bit size, well, sorry, BPF verifier can't validate stuff like that). Dedicated BPF map or helper (as a general case, not just this one) will pretty much always going to be easier to use just because it's a dedicated and tailored API.
Quoted 9 lines
To me, it seems like we get the best of both worlds by using both of these two ideas for the bloom filter. For developers who would like to use a general bloom filter without having to do any extra implementation work
or having to understand how bloom filters are implemented, they could use the custom bloom filter map with minimal effort. For developers who would like to customize their bloom filter to something more specific or fine-tuned, they could use craft their own bloom filter in an ebpf program. To me, these two directions don't seem mutually exclusive.They are not mutually exclusive, of course, but adding stuff to the kernel has its maintenance costs.
Quoted 19 lines
Quoted 11 lines
Quoted 11 lines
As far as map based bloom filter I think it can combine bitset and bloomfilter features into one.
delete_elemfrom user space can be mapped intopop()to clear bits.
Some special value ofnr_hashescould mean that no hashing is applied and 4 or 8 byte key gets modulo ofmax_entriesand treated as a bit index. Both bpf prog and user space will have uniform access into such bitset. Withnr_hashes>= 1 it will become a bloom filter.
In that sense may bemax_entriesshould be specified in bits and the map is called bitset. Withnr_hashes>= 1 the kernel would acceptkey_size> 8 and convert it to bloom filterQuoted 8 lines
Quoted 8 lines
peek/pop/push. In other words
nr_hash== 0bit_idx== key for set/read/clearnr_hashes>= 1 bit_idx[1..N] =hash(key, N)for set/read/clear.
If we could teach the verifier to inline the bit lookup
we potentially can get rid of bloomfilter loop inside thepeek(). Then the map would be true bitset without bloomfilter quirks.
Even in such case it's not equivalent tobpf_hash(mem_ptr, size, flags)helper. Thoughts?Quoted 12 lines
This is an interesting suggestion; to me, it seems like the APIs and code would be
more straightforward if the bitset and the bloom filter were separate maps. With havingmax_entriesbe specified in bits, I think this also relies on the
user to make an educated call on the optimal number of bits to use for their bloom
filter, instead of passing in the number of entries they expect to have and having the
bit size automatically calculated according to a mathematically optimized equation.
I am open to this idea though.We can provide a macro that will calculate mathematically optimized value based on desired number of unique entries and hash functions. E.g.:
Quoted 7 lines
#define
BPF_BLOOM_FILTER_BYTE_SZ(nr_uniq_entries, nr_hash_funcs)(nr_uniq_entires*nr_hash_funcs/ 5 * 7 / 8)Kernel code can round up to closest power-of-two internally to make this simpler. So if users don't care or don't know, they'll use
BPF_BPLOOM_FILTER_BYTE_SZ()macro, but if they know better, they'll just specify desired amount of bytes.Sounds great!
Quoted 46 lines
Quoted 34 lines
Quoted 23 lines
Sounds a bit complicated from end-user's perspective, tbh, but bitset map (with generalization for bloom filter) sounds a bit more widely useful. See above for the
bpf_hash_algoproposal. If we allow to specifynr_hashesand hash algorithm, then with XOR as defined above andnr_hash= 1, you'll get just bitset behavior with not extra restrictions on key size: you could have 1, 2, 4, 8 and more bytes (where with more bytes it's some suboptimal bloom filter with one hash function, not sure why you'd do that).The biggest quirk is defining that XOR hashes in chunks of 8 bytes (with zero-extending anything that is not a multiple of 8 bytes length). We can do special "only 1, 2, 4, and 8 bytes are supported", of course, but it will be special-cased internally. Not sure which one is cleaner.
While writing this, another thought was to have a "NOOP" (or "IDENTITY") hash, where we say that we treat bytes as one huge number. Obviously then we truncate to the actual bitmap size, which just basically means "use up to lower 8 bytes as a number". But it sucks for big-endian, because to make it sane we'd need to take last "up to 8 bytes", which obviously sounds convoluted. So I don't know, just a thought.
Quoted 11 lines
If we do the map, though, regardless if it's bitset or bloom specifically. Maybe we should consider modeling as actual
bpf_map_lookup_elem(), where the key is a pointer to whatever we are hashing and looking up? It makes much more sense, that's how people model sets based on maps: key is the element you are looking up, value is either true/false or meaningless (at least for me it felt much more natural that you are looking up by key, not by value). In this case, what if on successful lookup we return a pointer to some fixed u8/u32/u64 location in the kernel, some dedicated static variable shared between all maps. So NULL means "element is not in a set", non-NULL means it is in the set.Quoted 12 lines
I think this would then also require that the
bpf_map_update_elem()API from the userspace side would have to pass in a valid memory address for the "value".
I understand what you're saying though about it feeling more natural that the "key" is the element here; I agree but there doesn't seem to be a clean way
of doing this - I think maybe one viable approach would be allowingmap_update_elem
to pass in a NULL value in the kernel if the map is a non-associative map, and refactoring the
push_elem/peek_elem API so that the element can represent either the key or the value.Quoted 4 lines
Yeah, we can allow value to be NULL (and key non-NULL). But why push/peek if we are talking about using standard lookup_elem/update_elem (and maybe even
delete_elemwhich will reset bits to 0)?In the syscall layer where we handle
lookup_elem, we callmap->ops->map_lookup_elem
and expect that the ptr we get back is a ptr to the value associated with the key
(and if the ptr is NULL we treat that as an error).
Quoted 5 lines
Instead of adding special-casing for bloom filter maps to treat a NULL ptr value
as something that's okay, it seems cleaner to repurpose peek to be the API we use for
all non-associative map types.
That's not what I proposed. So let's say somewhere in the kernel we have this variable:
static int bpf_bloom_exists = 1;
Now, for bpf_map_lookup_elem() helper we pass data as key pointer. If all its hashed bits are set in Bloom filter (it "exists"), we return &bpf_bloom_exists. So it's not a NULL pointer.
Now, despite returning a valid pointer, it would be good to prevent reading/writing from/to it in a valid BPF program. I'm hoping it is as easy as just seetting map->value_size = 0 during map creation. But worst case, we can let BPF program just overwrite that 1 with whatever they want. It doesn't matter because the contract is that bpf_map_lookup_elem() returns non-NULL for "exists" and NULL otherwise.
Now, for MAP_LOOKUP_ELEM command on user-space side. I'd say the contract should be 0 return code on "exists" (and nothing is written to value pointer, perhaps even disallow to specify the non-NULL value pointer altogether); -ENOENT, otherwise. Again, worst-case we can specify that "value_size" is 1 or 4 bytes and write 1 to it.
Does it make sense?
BTW, for STACK/QUEUE maps, I'm not clear why we had to add map_peek_elem/map_pop_elem/map_push_elem operations, to be honest. They could have been pretty reasonably mapped to map_lookup_elem (peek is non-destructive lookup), map_lookup_elem + some flag (pop is lookup, but destructive, so flag allows "destruction"), and map_update_elem (for push). map_delete_elem would be pop for when value can be ignored.
That's to say that I don't consider STACK/QUEUE maps as good examples, it's rather a counter-example of maps that barely anyone is using, yet it just adds clutter to BPF internals.
Quoted 37 lines
Quoted 31 lines
Quoted 3 lines
Quoted 3 lines
Ideally we'd prevent such element to
be written to, but it might be too hard to do that as just one exception here, don't know.BTW, that
nr_hash_funcsfield in UAPI and in libbpf was still bothering me. I'd feel better if we generalize this to future map needs and make it generic. How about adding "u32map_extra;" field to UAPI (as a new field, so it's available for all maps, including map-in-maps). The meaning of that field would be per-map-type extra flags/values/etc. In this case we can define thatmap_extraforBLOOM_FILTERit would encode number of hash functions. If we ok adding hash function enum that I proposed forbpf_hash_mem()helper, we can also include that intomap_extra. We can reserve lower N bits for number of hash functions and then next few bits would be reserved for hash algo enum.So then you'd define map (in libbpf syntax) pretty naturally as:
struct {
__uint(type, BPF_MAP_TYPE_BLOOM_FILTER); /* or BITSET, don't know
which way this is going */.... __uint(map_extra, BPF_HASH_SHA256 | 3); /* 3 x SHA256 hash functions */ } my_bloom_filter SEC(".maps");
BPF_HASH_SHA256would be defined as something like 0x{1,2,4,etc}0, leaving lower 4 bits fornr_hash_funcs.And then I'd have no problem supporting
map_extrafield for any map definition, withbpf_map__map_extra()andbpf_map__set_map_extra()getter/setter.Quoted 5 lines
map_flagsis different in that it's partially shared by all map types (e.g.,BPF_F_RDONLY_PROG,BPF_F_INNER_MAP,BPF_F_NUMA_NODEcan be specified for lots of different types).Naming is obviously up for discussion.
Quoted 8 lines
I love this idea!
To make sure we're all aligned on the direction of this, for v4 I'm going to make
the following changes:
* Make the map a bitset + bloom filter map, depending on how many hashes are passed in
I'm not sure we are all on the same page on the exact encoding and what to do about the bitset case (do we restrict keys to 1, 4, 8 bytes? or we go with "noop" (or xor?) hash function? or?...) Would be good to hear from Alexei and Martin to not waste your time iterating on this. The rest looks good to me.
Quoted 2 lines
* Write tests for the bitset functionality of the map
* Changenr_hashesto a more generic "u32map_extra"
yep, with this being generic I think it's good to have bpf_map__set_map_extra() and bpf_map__map_extra() APIs in libbpf as well.
Quoted 2 lines
* Incorporate some of Andrii's changes to the benchmarks for accounting + measuring
would be nice to have in-kernel updates benchmark, if it's not too much work
for existing lookup benchmarks, bpf_get_prandom_u32() seems to take a nontrivial amount of time, I'd recommend pre-generating a bunch of random data during preparation phase, and then for each BPF program invocation call bpf_get_prandom_u32() just once (before 512 iterations of the loop) to determine the starting position p. Then just use pregenerated data from rand_data[(p + i) % TOTAL_RAND_DATA_CNT].
Quoted 6 lines
* Add more documentation regarding the optimal bitmap size equation "
nr_unique_entries*nr_hash_funcs/ 5 * 7 / 8" to clear up any confusionThanks for the discussion on this, Martin, Andrii, and Alexei!
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 9 lines · Andrii Nakryiko
That's not what I proposed. So let's say somewhere in the kernel we have this variable:
static int
bpf_bloom_exists= 1;Now, for
bpf_map_lookup_elem()helper we pass data as key pointer. If all its hashed bits are set in Bloom filter (it "exists"), we return&bpf_bloom_exists. So it's not a NULL pointer.
imo that's too much of a hack.
Quoted 25 lines
Now, despite returning a valid pointer, it would be good to prevent reading/writing from/to it in a valid BPF program. I'm hoping it is as easy as just seetting
map->value_size= 0 during map creation. But worst case, we can let BPF program just overwrite that 1 with whatever they want. It doesn't matter because the contract is thatbpf_map_lookup_elem()returns non-NULL for "exists" and NULL otherwise.Now, for
MAP_LOOKUP_ELEMcommand on user-space side. I'd say the contract should be 0 return code on "exists" (and nothing is written to value pointer, perhaps even disallow to specify the non-NULL value pointer altogether);-ENOENT, otherwise. Again, worst-case we can specify that "value_size" is 1 or 4 bytes and write 1 to it.Does it make sense?
BTW, for STACK/QUEUE maps, I'm not clear why we had to add map_peek_elem/map_pop_elem/map_push_elem operations, to be honest. They could have been pretty reasonably mapped to
map_lookup_elem(peek is non-destructive lookup),map_lookup_elem+ some flag (pop is lookup, but destructive, so flag allows "destruction"), andmap_update_elem(for push).map_delete_elemwould be pop for when value can be ignored.
Quoted 3 lines
That's to say that I don't consider STACK/QUEUE maps as good examples, it's rather a counter-example of maps that barely anyone is using, yet it just adds clutter to BPF internals.
Repurposing lookup/update ops for stack/queue and forcing bpf progs to pass dummy key would have looked quite ugly. peek/pop/push have one pointer. That pointer points to value. For bitset we have single pointer as well.
So it makes perfect sense to reuse push/pop/peek and keep bitset as a value from the verifier side.bpf_helper_defs.h could have static inline functions:
bool bpf_bitset_clear(map, key);
bool bpf_bitset_set(map, key);
bool bpf_bitset_test(map, key);
But they will map to FUNC_map_pop_elem/push/peek as func ids and will be seen as values from the verifier pov.
The bpf progs might think of them as keys, but they will be value_size. The bitset creation could use key_size as an input, but internally set it as value_size.
Not sure whether such internal vs uapi remaping will not lead to confusion and bugs though.
I agree that key as an input to bitset_clear/set/test make more sense, but the verifier needs value_size to plug into peek/pop infra.
I don't think it's worth to extend ops with yet another 3 callbacks and have clean ARG_PTR_TO_UNINIT_MAP_KEY there.
That is probably too much clutter.
I think
bool bpf_bitset_clear(map, value);
bool bpf_bitset_set(map, value);
bool bpf_bitset_test(map, value);
doesn't look too bad either.
At least this way the bit set map_create op will use value_size and keep it as value_size. The bpf prog won't be confusing. That's my preference, so far.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 6 lines · Alexei Starovoitov
Quoted 4 lines · Andrii Nakryiko
That's not what I proposed. So let's say somewhere in the kernel we have this variable:
Quoted 7 lines
Quoted 5 lines
static int
bpf_bloom_exists= 1;Now, for
bpf_map_lookup_elem()helper we pass data as key pointer. If all its hashed bits are set in Bloom filter (it "exists"), we return&bpf_bloom_exists. So it's not a NULL pointer.imo that's too much of a hack.
too bad, because this feels pretty natural in BPF code:
int my_key = 1234;
if (bpf_map_lookup_elem(&my_bloom_filter, &my_key)) {
/* handle "maybe exists" */
} else {
/* handle "definitely doesn't exist" */
}With map->value_size == 0 verifier should be able to ensure that whatever non-NULL pointer is returned isn't readable/writable. We might need to fix some BPF verifier internals if that's not supported yet, I haven't checked thoroughly.
Quoted 26 lines
Quoted 26 lines
Now, despite returning a valid pointer, it would be good to prevent reading/writing from/to it in a valid BPF program. I'm hoping it is as easy as just seetting
map->value_size= 0 during map creation. But worst case, we can let BPF program just overwrite that 1 with whatever they want. It doesn't matter because the contract is thatbpf_map_lookup_elem()returns non-NULL for "exists" and NULL otherwise.Now, for
MAP_LOOKUP_ELEMcommand on user-space side. I'd say the contract should be 0 return code on "exists" (and nothing is written to value pointer, perhaps even disallow to specify the non-NULL value pointer altogether);-ENOENT, otherwise. Again, worst-case we can specify that "value_size" is 1 or 4 bytes and write 1 to it.Does it make sense?
BTW, for STACK/QUEUE maps, I'm not clear why we had to add map_peek_elem/map_pop_elem/map_push_elem operations, to be honest. They could have been pretty reasonably mapped to
map_lookup_elem(peek is non-destructive lookup),map_lookup_elem+ some flag (pop is lookup, but destructive, so flag allows "destruction"), andmap_update_elem(for push).map_delete_elemwould be pop for when value can be ignored.
Quoted 6 lines
Quoted 3 lines
That's to say that I don't consider STACK/QUEUE maps as good examples, it's rather a counter-example of maps that barely anyone is using, yet it just adds clutter to BPF internals.
Repurposing lookup/update ops for stack/queue and forcing bpf progs to pass dummy key would have looked quite ugly.
The idea was to pass non-NULL *key* pointer. For bpf_map_update_elem() you'd pass non-NULL key and NULL value. But it's fine, we have peek/pop/push now, might as well use them. From user-space side it's still mapped to LOOKUP/UPDATE/DELETE commands, right? BTW, seems like we have LOOKUP_AND_DELETE command as well which is implemented for STACK/QUEUE maps, but not BLOOM_FILTER. I guess for consistency we'd have to implement that one for user-space as well?
Quoted 4 lines
peek/pop/push have one pointer. That pointer points to value. For bitset we have single pointer as well.
So it makes perfect sense to reuse push/pop/peek and keep bitset as a value from the verifier side.
Ok.
Quoted 5 lines
bpf_helper_defs.hcould have static inline functions:
boolbpf_bitset_clear(map, key);
boolbpf_bitset_set(map, key);
boolbpf_bitset_test(map, key);
Quoted 8 lines
But they will map to FUNC_map_pop_elem/push/peek as func ids and will be seen as values from the verifier pov.
The bpf progs might think of them as keys, but they will be
value_size. The bitset creation could usekey_sizeas an input, but internally set it asvalue_size.
Not sure whether such internal vs uapi remaping will not lead to confusion and bugs though.
I think it will and I wouldn't do it.
Quoted 2 lines
I agree that key as an input to bitset_clear/set/test make more sense, but the verifier needs
value_sizeto plug into peek/pop infra.
Which is why I initially proposed to not use peek/pop infra and instead do lookup/update/delete, but if a NULL value pointer passed into bpf_map_update_elem() disqualifies this, then it's fine. But I didn't ask to repurpose peek/pop for working with key pointers.
Quoted 13 lines
I don't think it's worth to extend ops with yet another 3 callbacks and have clean
ARG_PTR_TO_UNINIT_MAP_KEYthere.
That is probably too much clutter.I think
boolbpf_bitset_clear(map, value);
boolbpf_bitset_set(map, value);
boolbpf_bitset_test(map, value);
doesn't look too bad either.
At least this way the bit setmap_createop will usevalue_sizeand keep it asvalue_size. The bpf prog won't be confusing. That's my preference, so far.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 18 lines · Andrii Nakryiko
Quoted 6 lines · Alexei Starovoitov
Quoted 4 lines · Andrii Nakryiko
That's not what I proposed. So let's say somewhere in the kernel we have this variable:
Quoted 7 lines
Quoted 5 lines
static int
bpf_bloom_exists= 1;Now, for
bpf_map_lookup_elem()helper we pass data as key pointer. If all its hashed bits are set in Bloom filter (it "exists"), we return&bpf_bloom_exists. So it's not a NULL pointer.imo that's too much of a hack.
too bad, because this feels pretty natural in BPF code:
Quoted 7 lines
int
my_key= 1234;if (bpf_map_lookup_elem(&my_bloom_filter, &my_key)) { /* handle "maybe exists" */ } else { /* handle "definitely doesn't exist" */ }
I don't think it fits bitset map.
In the bitset the value is zero or one. It always exist. If bloomfilter is not a special map and instead implemented on top of generic bitset with a plain loop in a bpf program then push -> bit_set
pop -> bit_clear
peek -> bit_test
would be a better fit for bitset map.
bpf_map_pop_elem() and peek_elem() don't have 'flags' argument. In most cases that would be a blocker,
but in this case we can add:
.arg3_type = ARG_ANYTHING
and ignore it in case of stack/queue.
While bitset could use the flags as an additional seed into the hash. So to do a bloomfilter the bpf prog would do:
for (i = 0; i < 5; i++)
if (bpf_map_peek_elem(map, &value, conver_i_to_seed(i)))
Probably would still be an improvement to add:
static inline long bpf_bit_test(void *map, void *value, long flags)
{
return bpf_map_peek_elem(map, value, flags);
}to some header file.
Or maybe bloomfilter and the loop can be a flavor of bitset map and done inside the helper to spare bpf programmers doing the manual loops. Or such loop could be another static inline function in a header file?
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 37 lines · Alexei Starovoitov
Quoted 18 lines · Andrii Nakryiko
Quoted 6 lines · Alexei Starovoitov
Quoted 4 lines · Andrii Nakryiko
That's not what I proposed. So let's say somewhere in the kernel we have this variable:
Quoted 7 lines
Quoted 5 lines
static int
bpf_bloom_exists= 1;Now, for
bpf_map_lookup_elem()helper we pass data as key pointer. If all its hashed bits are set in Bloom filter (it "exists"), we return&bpf_bloom_exists. So it's not a NULL pointer.imo that's too much of a hack.
too bad, because this feels pretty natural in BPF code:
Quoted 7 lines
int
my_key= 1234;if (bpf_map_lookup_elem(&my_bloom_filter, &my_key)) { /* handle "maybe exists" */ } else { /* handle "definitely doesn't exist" */ }I don't think it fits bitset map.
In the bitset the value is zero or one. It always exist. If bloomfilter is not a special map and instead implemented on top of generic bitset with a plain loop in a bpf program then push ->bit_set
pop ->bit_clear
peek ->bit_test
would be a better fit for bitset map.
Quoted 9 lines
bpf_map_pop_elem()andpeek_elem()don't have 'flags' argument. In most cases that would be a blocker,
but in this case we can add:
.arg3_type =ARG_ANYTHING
and ignore it in case of stack/queue.
While bitset could use the flags as an additional seed into the hash. So to do a bloomfilter the bpf prog would do:
for (i = 0; i < 5; i++)
if (bpf_map_peek_elem(map, &value, conver_i_to_seed(i)))
I think I'm getting lost in the whole unified bitset + bloom filter design, tbh. In this case, why would you pass the seed to peek()? And what is value here? Is that the value (N bytes) or the bit index (4 bytes?)? I assumed that once we have a hashing helper and a bitset map, you'd use that and seed to calculate bit index. But now I'm confused about what this peek operation is doing. I'm sorry if I'm just slow.
Overall, I think I agree with Joanne that a separate dedicated Bloom filter map will have simpler and better usability. This bitset + bloom filter generalization seems to just create unnecessary confusion. I don't feel the need for bitset map even more than I didn't feel the need for Bloom filter, given it's even simpler data structure and is totally implementable on either global var array or BPF_MAP_TYPE_ARRAY, if map-in-map and dynamic sizing in mandatory.
But given we are converging on having a new map, maybe let's do just a Bloom filter map with the tweaks we discussed in this thread for map_extra and max_entries?
Quoted 11 lines
Probably would still be an improvement to add:
static inline longbpf_bit_test(void *map, void *value, long flags){ return bpf_map_peek_elem(map, value, flags); }to some header file.
Or maybe bloomfilter and the loop can be a flavor of bitset map and done inside the helper to spare bpf programmers doing the manual loops. Or such loop could be another static inline function in a header file?
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 49 lines · Andrii Nakryiko
Quoted 37 lines · Alexei Starovoitov
Quoted 18 lines · Andrii Nakryiko
Quoted 6 lines · Alexei Starovoitov
Quoted 4 lines · Andrii Nakryiko
That's not what I proposed. So let's say somewhere in the kernel we have this variable:
Quoted 7 lines
Quoted 5 lines
static int
bpf_bloom_exists= 1;Now, for
bpf_map_lookup_elem()helper we pass data as key pointer. If all its hashed bits are set in Bloom filter (it "exists"), we return&bpf_bloom_exists. So it's not a NULL pointer.imo that's too much of a hack.
too bad, because this feels pretty natural in BPF code:
Quoted 7 lines
int
my_key= 1234;if (bpf_map_lookup_elem(&my_bloom_filter, &my_key)) { /* handle "maybe exists" */ } else { /* handle "definitely doesn't exist" */ }I don't think it fits bitset map.
In the bitset the value is zero or one. It always exist. If bloomfilter is not a special map and instead implemented on top of generic bitset with a plain loop in a bpf program then push ->bit_set
pop ->bit_clear
peek ->bit_test
would be a better fit for bitset map.Quoted 9 lines
bpf_map_pop_elem()andpeek_elem()don't have 'flags' argument. In most cases that would be a blocker,
but in this case we can add:
.arg3_type =ARG_ANYTHING
and ignore it in case of stack/queue.
While bitset could use the flags as an additional seed into the hash. So to do a bloomfilter the bpf prog would do:
for (i = 0; i < 5; i++)
if (bpf_map_peek_elem(map, &value, conver_i_to_seed(i)))
Quoted 4 lines
I think I'm getting lost in the whole unified bitset + bloom filter design, tbh. In this case, why would you pass the seed to
peek()? And what is value here? Is that the value (N bytes) or the bit index (4 bytes?)?
The full N byte value, of course.
The pure index has the same downsides as hashing helper:
- hard to make kernel and user space produce the same hash in all cases
- inability to dynamically change max_entries in a clean way
Quoted 5 lines
I assumed that once we have a hashing helper and a bitset map, you'd use that and seed to calculate bit index. But now I'm confused about what this peek operation is doing. I'm sorry if I'm just slow.
Quoted 7 lines
Overall, I think I agree with Joanne that a separate dedicated Bloom filter map will have simpler and better usability. This bitset + bloom filter generalization seems to just create unnecessary confusion. I don't feel the need for bitset map even more than I didn't feel the need for Bloom filter, given it's even simpler data structure and is totally implementable on either global var array or
BPF_MAP_TYPE_ARRAY, if map-in-map and dynamic sizing in mandatory.
Not really. For two reasons:
- inner array with N 8-byte elements is a slow workaround. map_lookup is not inlined for inner arrays because max_entries will be different.
- doing the same hash in user space and the kernel is hard. For example, iproute2 is using socket(AF_ALG) to compute the same hash (program tag) as the kernel.
Copy-paste of kernel jhash.h is not possible due to GPL, but, as you pointed out, it's public domain, so user space would need to search a public domain, reimplement jhash and then make sure that it produces the same hash as the kernel.
All these trade offs point out the need for dedicated map type (either generalized bitset or true bloomfilter) that does the hashing and can change its size.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 29 lines · Joanne Koong
Quoted 18 lines · Alexei Starovoitov
Quoted 17 lines · Andrii Nakryiko
Quoted 15 lines · Alexei Starovoitov
Quoted 14 lines · Andrii Nakryiko
Quoted 10 lines · Alexei Starovoitov
Quoted 8 lines · Andrii Nakryiko
That's not what I proposed. So let's say somewhere in the kernel we have this variable:
static int
bpf_bloom_exists= 1;Now, for
bpf_map_lookup_elem()helper we pass data as key pointer. If all its hashed bits are set in Bloom filter (it "exists"), we return&bpf_bloom_exists. So it's not a NULL pointer.imo that's too much of a hack.
too bad, because this feels pretty natural in BPF code:
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
int
my_key= 1234;if (bpf_map_lookup_elem(&my_bloom_filter, &my_key)) { /* handle "maybe exists" */ } else { /* handle "definitely doesn't exist" */ }
Quoted 4 lines
To summarize this, Andrii it seems like you are proposing two possibilities for passing the ptr to the data as the key:
1. Have the value be NULL (
value_size= 0)
Yeah, this was my biggest hope (except value is non-NULL, it's just zero-sized so not readable/writable), but that's academic at this point, see below.
Quoted 20 lines
2. Have the value be
value_size= 1 byte orvalue_size= 4 bytes in a worst-case scenarioFor #1 where the
value_sizeis 0 and we return something like&bpf_bloom_exists
forbpf_map_lookup_elem()where the key is found, this would still require us to do
the following in the syscall layer elsewhere:a) In the syscall layer in
map_lookup_elem, add code that will allowvalue_sizesof
0. This would require another change inbpf_map_copy_valuewhere we have to also check that if thevalue_sizeis 0, then we shouldn't copy the resulting ptr
of thebpf_map_lookup_elemcall to the value ptr (the value ptr isn't allocated sincevalue_sizeis 0).
Quoted 9 lines
b) In
map_update_elem, add code that allows the user to pass in a NULL / zero-size
value. Currently, there exists only support for passing in a NULL/zero-size key
(which was added for stack/queue maps that pass in NULL keys); we'd have to add
in the equivalent for NULL/zero-size values. We'd also have to modify the verifier
to allowbpf_map_update_elemfor NULL values (ARG_PTR_TO_UNINIT_MAP_KEY).
This "UNINIT_MAP_KEY" part is confusing me because we are talking about *NULL value* (so neither uninitialized nor a key), so I must be missing something important here. I thought it would be ARG_PTR_TO_MAP_VALUE_OR_NULL, but it does suck that other map types would then be allowed NULL where they don't expect to get NULL, I agree.
Quoted 12 lines
For #2, from the user-side for
bpf_map_update_elem, this now means the user would have to always pass in some dummy 1-byte or 4-byte value since thevalue_sizeis no longer 0. This seems like a hacky APIRepurposing peek/push/pop (in the scenario where
value_size= 0) would avoid thebpf_map_copy_valuechange in #1a altogether, which was the primary reason for
suggesting it.
Quoted 7 lines
The approach taken in this patchset (where we have the key as NULL, and the value
as the ptr to the data) avoids the need to add that infrastructure outlined above
for allowing NULL values, since it just rides on top of the changes that were added to the
stack/queue map that allows NULL keys.
So overall, I agree that all the above will be an unnecessary complication for relatively little gain. Just go with peek/pop/push.
Quoted 19 lines
Quoted 19 lines
Quoted 19 lines
Quoted 19 lines
I don't think it fits bitset map.
In the bitset the value is zero or one. It always exist. If bloomfilter is not a special map and instead implemented on top of generic bitset with a plain loop in a bpf program then push ->bit_set
pop ->bit_clear
peek ->bit_test
would be a better fit for bitset map.
bpf_map_pop_elem()andpeek_elem()don't have 'flags' argument. In most cases that would be a blocker,
but in this case we can add:
.arg3_type =ARG_ANYTHING
and ignore it in case of stack/queue.
While bitset could use the flags as an additional seed into the hash. So to do a bloomfilter the bpf prog would do:
for (i = 0; i < 5; i++)if (bpf_map_peek_elem(map, &value, conver_i_to_seed(i)))
Quoted 7 lines
Quoted 4 lines
Quoted 4 lines
I think I'm getting lost in the whole unified bitset + bloom filter design, tbh. In this case, why would you pass the seed to
peek()? And what is value here? Is that the value (N bytes) or the bit index (4 bytes?)?In that example where seed is passed to
peek(), the context is the hypothetical scenario where the bloom filter is implemented on top of a generic bitset.
But then why does *bitset* do the hashing on behalf of the user, that's the confusing bit. But I'll reply to Alexei's email in just a sec.
Quoted 33 lines
Quoted 17 lines
The full N byte value, of course.
The pure index has the same downsides as hashing helper:
- hard to make kernel and user space produce the same hash in all cases
- inability to dynamically changemax_entriesin a clean wayQuoted 5 lines
I assumed that once we have a hashing helper and a bitset map, you'd use that and seed to calculate bit index. But now I'm confused about what this peek operation is doing. I'm sorry if I'm just slow.
Quoted 7 lines
Overall, I think I agree with Joanne that a separate dedicated Bloom filter map will have simpler and better usability. This bitset + bloom filter generalization seems to just create unnecessary confusion. I don't feel the need for bitset map even more than I didn't feel the need for Bloom filter, given it's even simpler data structure and is totally implementable on either global var array or
BPF_MAP_TYPE_ARRAY, if map-in-map and dynamic sizing in mandatory.Quoted 14 lines
Not really. For two reasons:
- inner array with N 8-byte elements is a slow workaround.map_lookupis not inlined for inner arrays becausemax_entrieswill be different.
- doing the same hash in user space and the kernel is hard. For example, iproute2 is usingsocket(AF_ALG)to compute the same hash (program tag) as the kernel.
Copy-paste of kerneljhash.his not possible due to GPL, but, as you pointed out, it's public domain, so user space would need to search a public domain, reimplement jhash and then make sure that it produces the same hash as the kernel.
All these trade offs point out the need for dedicated map type (either generalized bitset or true bloomfilter) that does the hashing and can change its size.
Quoted 6 lines
To ensure we are all aligned on this conversation, here is in more detail what I am intending for the v4 map changes:
* A bitset map that also internally functions as a bloom filter ifnr_hashes> 0 (wherenr_hashesis denoted through themap_extraflags).max_entrieswill be the requested size of the bitset.Key_sizeshould always be 0.
ok, makes sense. max_entries is the number of bytes or bits? Not sure which is better (bytes is more consistent with other uses and allows for bigger bitset/filter, but bits might be more natural for bitset), just bringing this up as it's unclear.
Quoted 5 lines
* Add the convenience helpers
boolbpf_bitset_clear(map, value);
boolbpf_bitset_set(map, value);
boolbpf_bitset_test(map, value);
It maps one to one to bpf_map_pop_elem(), bpf_map_push_elem(), and bpf_map_peek_elem(), right? The signatures for pop and peek are *identical* (map + value), while push has also extra flags (not a big deal, we have 0 flags in a lot of helpers). So I don't see much value for this (and it actually will be more confusing when bitset is really a bloom filter :) ).
Quoted 4 lines
In the case where
nr_hashes== 0 (straight bitset):
* For simplicity,value_sizefor the bitmap should always be a u32. This denotes which index of the bitmap to set/check/clear
SGTM.
Quoted 5 lines
In the case where
nr_hashes> 0 (bloom filter):
* The value size can be whatever
* Clear/delete is not supported
Sounds good as well.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 64 lines · Andrii Nakryiko
Quoted 27 lines · Joanne Koong
Quoted 18 lines · Alexei Starovoitov
Quoted 17 lines · Andrii Nakryiko
Quoted 15 lines · Alexei Starovoitov
Quoted 14 lines · Andrii Nakryiko
Quoted 10 lines · Alexei Starovoitov
Quoted 8 lines · Andrii Nakryiko
That's not what I proposed. So let's say somewhere in the kernel we have this variable:
static int
bpf_bloom_exists= 1;Now, for
bpf_map_lookup_elem()helper we pass data as key pointer. If all its hashed bits are set in Bloom filter (it "exists"), we return&bpf_bloom_exists. So it's not a NULL pointer.imo that's too much of a hack.
too bad, because this feels pretty natural in BPF code:
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
int
my_key= 1234;if (bpf_map_lookup_elem(&my_bloom_filter, &my_key)) { /* handle "maybe exists" */ } else { /* handle "definitely doesn't exist" */ }Quoted 4 lines
To summarize this, Andrii it seems like you are proposing two possibilities for passing the ptr to the data as the key:
1. Have the value be NULL (
value_size= 0)Yeah, this was my biggest hope (except value is non-NULL, it's just zero-sized so not readable/writable), but that's academic at this point, see below.
Quoted 19 lines
2. Have the value be
value_size= 1 byte orvalue_size= 4 bytes in a worst-case scenarioFor #1 where the
value_sizeis 0 and we return something like&bpf_bloom_exists
forbpf_map_lookup_elem()where the key is found, this would still require us to do
the following in the syscall layer elsewhere:a) In the syscall layer in
map_lookup_elem, add code that will allowvalue_sizesof
0. This would require another change inbpf_map_copy_valuewhere we have to also check that if thevalue_sizeis 0, then we shouldn't copy the resulting ptr
of thebpf_map_lookup_elemcall to the value ptr (the value ptr isn't allocated sincevalue_sizeis 0).Quoted 9 lines
b) In
map_update_elem, add code that allows the user to pass in a NULL / zero-size
value. Currently, there exists only support for passing in a NULL/zero-size key
(which was added for stack/queue maps that pass in NULL keys); we'd have to add
in the equivalent for NULL/zero-size values. We'd also have to modify the verifier
to allowbpf_map_update_elemfor NULL values (ARG_PTR_TO_UNINIT_MAP_KEY).
Quoted 6 lines
This "
UNINIT_MAP_KEY" part is confusing me because we are talking about *NULL value* (so neither uninitialized nor a key), so I must be missing something important here. I thought it would beARG_PTR_TO_MAP_VALUE_OR_NULL, but it does suck that other map types would then be allowed NULL where they don't expect to get NULL, I agree.
You're right, this would just be changed to ARG_PTR_TO_MAP_VALUE_OR_NULL; I mis-pasted ARG_PTR_TO_UNINIT_MAP_KEY from a previous draft. Sorry if that caused confusion.
Quoted 87 lines
Quoted 10 lines
For #2, from the user-side for
bpf_map_update_elem, this now means the user would have to always pass in some dummy 1-byte or 4-byte value since thevalue_sizeis no longer 0. This seems like a hacky APIRepurposing peek/push/pop (in the scenario where
value_size= 0) would avoid thebpf_map_copy_valuechange in #1a altogether, which was the primary reason for
suggesting it.Quoted 7 lines
The approach taken in this patchset (where we have the key as NULL, and the value
as the ptr to the data) avoids the need to add that infrastructure outlined above
for allowing NULL values, since it just rides on top of the changes that were added to the
stack/queue map that allows NULL keys.So overall, I agree that all the above will be an unnecessary complication for relatively little gain. Just go with peek/pop/push.
Quoted 18 lines
Quoted 18 lines
Quoted 18 lines
Quoted 18 lines
I don't think it fits bitset map.
In the bitset the value is zero or one. It always exist. If bloomfilter is not a special map and instead implemented on top of generic bitset with a plain loop in a bpf program then push ->bit_set
pop ->bit_clear
peek ->bit_test
would be a better fit for bitset map.
bpf_map_pop_elem()andpeek_elem()don't have 'flags' argument. In most cases that would be a blocker,
but in this case we can add:
.arg3_type =ARG_ANYTHING
and ignore it in case of stack/queue.
While bitset could use the flags as an additional seed into the hash. So to do a bloomfilter the bpf prog would do:
for (i = 0; i < 5; i++)if (bpf_map_peek_elem(map, &value, conver_i_to_seed(i)))Quoted 7 lines
Quoted 4 lines
Quoted 4 lines
I think I'm getting lost in the whole unified bitset + bloom filter design, tbh. In this case, why would you pass the seed to
peek()? And what is value here? Is that the value (N bytes) or the bit index (4 bytes?)?In that example where seed is passed to
peek(), the context is the hypothetical scenario where the bloom filter is implemented on top of a generic bitset.But then why does *bitset* do the hashing on behalf of the user, that's the confusing bit. But I'll reply to Alexei's email in just a sec.
Quoted 32 lines
Quoted 17 lines
The full N byte value, of course.
The pure index has the same downsides as hashing helper:
- hard to make kernel and user space produce the same hash in all cases
- inability to dynamically changemax_entriesin a clean wayQuoted 5 lines
I assumed that once we have a hashing helper and a bitset map, you'd use that and seed to calculate bit index. But now I'm confused about what this peek operation is doing. I'm sorry if I'm just slow.
Quoted 7 lines
Overall, I think I agree with Joanne that a separate dedicated Bloom filter map will have simpler and better usability. This bitset + bloom filter generalization seems to just create unnecessary confusion. I don't feel the need for bitset map even more than I didn't feel the need for Bloom filter, given it's even simpler data structure and is totally implementable on either global var array or
BPF_MAP_TYPE_ARRAY, if map-in-map and dynamic sizing in mandatory.Quoted 14 lines
Not really. For two reasons:
- inner array with N 8-byte elements is a slow workaround.map_lookupis not inlined for inner arrays becausemax_entrieswill be different.
- doing the same hash in user space and the kernel is hard. For example, iproute2 is usingsocket(AF_ALG)to compute the same hash (program tag) as the kernel.
Copy-paste of kerneljhash.his not possible due to GPL, but, as you pointed out, it's public domain, so user space would need to search a public domain, reimplement jhash and then make sure that it produces the same hash as the kernel.
All these trade offs point out the need for dedicated map type (either generalized bitset or true bloomfilter) that does the hashing and can change its size.Quoted 6 lines
To ensure we are all aligned on this conversation, here is in more detail what I am intending for the v4 map changes:
* A bitset map that also internally functions as a bloom filter ifnr_hashes> 0 (wherenr_hashesis denoted through themap_extraflags).max_entrieswill be the requested size of the bitset.Key_sizeshould always be 0.
Quoted 5 lines
ok, makes sense.
max_entriesis the number of bytes or bits? Not sure which is better (bytes is more consistent with other uses and allows for bigger bitset/filter, but bits might be more natural for bitset), just bringing this up as it's unclear.
I think number of bits would be more ergonomic for the user in the context of the bitset map. Especially since they will be operating at the granularity of the bit anyways for setting/clearing/checking a specified bit.
Quoted 11 lines
Quoted 5 lines
* Add the convenience helpers
boolbpf_bitset_clear(map, value);
boolbpf_bitset_set(map, value);
boolbpf_bitset_test(map, value);It maps one to one to
bpf_map_pop_elem(),bpf_map_push_elem(), andbpf_map_peek_elem(), right? The signatures for pop and peek are *identical* (map + value), while push has also extra flags (not a big deal, we have 0 flags in a lot of helpers). So I don't see much value for this (and it actually will be more confusing when bitset is really a bloom filter :) ).
Makes sense! I will not add these convenience helpers in v4
Quoted 10 lines
Quoted 3 lines
In the case where
nr_hashes== 0 (straight bitset):
* For simplicity,value_sizefor the bitmap should always be a u32. This denotes which index of the bitmap to set/check/clearSGTM.
Quoted 4 lines
In the case where
nr_hashes> 0 (bloom filter):
* The value size can be whatever
* Clear/delete is not supportedSounds good as well.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
In reply to Alexei StarovoitovQuoted 56 lines · Alexei Starovoitov
Quoted 49 lines · Andrii Nakryiko
Quoted 37 lines · Alexei Starovoitov
Quoted 18 lines · Andrii Nakryiko
Quoted 6 lines · Alexei Starovoitov
Quoted 4 lines · Andrii Nakryiko
That's not what I proposed. So let's say somewhere in the kernel we have this variable:
Quoted 7 lines
Quoted 5 lines
static int
bpf_bloom_exists= 1;Now, for
bpf_map_lookup_elem()helper we pass data as key pointer. If all its hashed bits are set in Bloom filter (it "exists"), we return&bpf_bloom_exists. So it's not a NULL pointer.imo that's too much of a hack.
too bad, because this feels pretty natural in BPF code:
Quoted 7 lines
int
my_key= 1234;if (bpf_map_lookup_elem(&my_bloom_filter, &my_key)) { /* handle "maybe exists" */ } else { /* handle "definitely doesn't exist" */ }I don't think it fits bitset map.
In the bitset the value is zero or one. It always exist. If bloomfilter is not a special map and instead implemented on top of generic bitset with a plain loop in a bpf program then push ->bit_set
pop ->bit_clear
peek ->bit_test
would be a better fit for bitset map.Quoted 9 lines
bpf_map_pop_elem()andpeek_elem()don't have 'flags' argument. In most cases that would be a blocker,
but in this case we can add:
.arg3_type =ARG_ANYTHING
and ignore it in case of stack/queue.
While bitset could use the flags as an additional seed into the hash. So to do a bloomfilter the bpf prog would do:
for (i = 0; i < 5; i++)
if (bpf_map_peek_elem(map, &value, conver_i_to_seed(i)))Quoted 4 lines
I think I'm getting lost in the whole unified bitset + bloom filter design, tbh. In this case, why would you pass the seed to
peek()? And what is value here? Is that the value (N bytes) or the bit index (4 bytes?)?
Quoted 4 lines
The full N byte value, of course.
The pure index has the same downsides as hashing helper:
- hard to make kernel and user space produce the same hash in all cases
- inability to dynamically changemax_entriesin a clean way
Here's the confusing part. If the map is performing hashing, then why would we do explicit 5 iteration instead of the map (bloom filter) just doing it internally in one go (faster and simpler). But if it is a bitset (and so we have to do 5 iterations to implement Bloom filter logic), then it is quite unconventional for the bitset data structure to perform the hashing of a value. The only upside of this hybrid one-bit-at-a-time-but-with-hashing-included approach would be more freedom in choosing the hashing seed for each individual bit. But that hasn't come up as a limitation in the discussion at all, which made me wonder what we are optimizing here for.
Quoted 14 lines
Quoted 6 lines
I assumed that once we have a hashing helper and a bitset map, you'd use that and seed to calculate bit index. But now I'm confused about what this peek operation is doing. I'm sorry if I'm just slow.
Quoted 7 lines
Overall, I think I agree with Joanne that a separate dedicated Bloom filter map will have simpler and better usability. This bitset + bloom filter generalization seems to just create unnecessary confusion. I don't feel the need for bitset map even more than I didn't feel the need for Bloom filter, given it's even simpler data structure and is totally implementable on either global var array or
BPF_MAP_TYPE_ARRAY, if map-in-map and dynamic sizing in mandatory.
Quoted 4 lines
Not really. For two reasons:
- inner array with N 8-byte elements is a slow workaround.map_lookupis not inlined for inner arrays becausemax_entrieswill be different.
If we are talking about bit set data structure (not Bloom filter), then elementary operation is setting/resetting *one bit*. For that, looking up an 8-byte element and setting a bit in it is just as efficient as having a dedicated bpf_map_push_elem(). Keep in mind, I'm talking about pure bitset logic here. Once you add N hashes (and thus we start talking about Bloom filter, not a bit set), then you get N helper calls vs just 1 for bloom filter logic.
So for Bloom filter you get performance advantage from a dedicated map (due to having just 1 helper call to do N hashing operations). For pure bitset, there seems to be little benefit at all because it is basically ARRAY. For pure bitset of a fixed size, doing it on a global var array is faster (no helper overhead). For map-in-map case with known or unknown size, ARRAY is equivalent to BITSET map (one helper call + setting 1 bit through returned pointer).
But the nr_hashes == 0 special casing for pure bitset works fine as well.
Quoted 4 lines
- doing the same hash in user space and the kernel is hard. For example, iproute2 is using
socket(AF_ALG)to compute the same hash (program tag) as the kernel.
Copy-paste of kerneljhash.his not possible due to GPL,
I haven't found SPDX header or any mention of GPL in include/linux/jhash.h, so I assumed someone can just copy paste the code (given the references to public domain). Seems like that's not the case? Just curious about implications, license-wise, if there is no SPDX? Is it still considered GPL?
Quoted 6 lines
but, as you pointed out, it's public domain, so user space would need to search a public domain, reimplement jhash and then make sure that it produces the same hash as the kernel. All these trade offs point out the need for dedicated map type (either generalized bitset or true bloomfilter) that does the hashing and can change its size.
Sure, we've converged on that already. I was confused by the above example of an explicit loop + bpf_map_peek_elem with hashing.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 5 lines · Andrii Nakryiko
So for Bloom filter you get performance advantage from a dedicated map (due to having just 1 helper call to do N hashing operations). For pure bitset, there seems to be little benefit at all because it is basically ARRAY.
I brought up bitset only as an idea to make bloomfilter map a bit more generic and was looking for feedback whether to call the new map "bitset that allows bloomfilter operations" or call it "bloomfilter that simplifies to bitset" with nr_hashes=0.
It sounds that using bloomfilter as a base name fits better.
Quoted 5 lines
I haven't found SPDX header or any mention of GPL in
include/linux/jhash.h, so I assumed someone can just copy paste the code (given the references to public domain). Seems like that's not the case? Just curious about implications, license-wise, if there is no SPDX? Is it still considered GPL?
I believe so. Every project that copy pasted jhash from the kernel add SPDX gpl-2 to its source.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
Quoted 11 lines · Alexei Starovoitov
Quoted 4 lines · Andrii Nakryiko
So for Bloom filter you get performance advantage from a dedicated map (due to having just 1 helper call to do N hashing operations). For pure bitset, there seems to be little benefit at all because it is basically ARRAY.
I brought up bitset only as an idea to make bloomfilter map a bit more generic and was looking for feedback whether to call the new map "bitset that allows bloomfilter operations" or call it "bloomfilter that simplifies to bitset" with nr_hashes=0.
It sounds that using bloomfilter as a base name fits better.
I am in favor of calling the new map "bitset that allows bloom filter operations" and having the map be BPF_MAP_TYPE_BITSET everywhere.
To me that is more intuitive since the bloom filter is based on top of a bitset. And I think more people will generally be using bitsets than the bloom filter. Additionally, for users who don't know or care what a bloom filter is, they might skip this map type altogether and not realize it also can be used as a bitset.
Quoted 7 lines
Quoted 5 lines
I haven't found SPDX header or any mention of GPL in
include/linux/jhash.h, so I assumed someone can just copy paste the code (given the references to public domain). Seems like that's not the case? Just curious about implications, license-wise, if there is no SPDX? Is it still considered GPL?I believe so. Every project that copy pasted jhash from the kernel add SPDX gpl-2 to its source.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
In reply to Andrii NakryikoQuoted 11 lines · Andrii Nakryiko
Quoted 5 lines
To make sure we're all aligned on the direction of this, for v4 I'm going to make
the following changes:
* Make the map a bitset + bloom filter map, depending on how many hashes are passed inI'm not sure we are all on the same page on the exact encoding and what to do about the bitset case (do we restrict keys to 1, 4, 8 bytes? or we go with "noop" (or xor?) hash function? or?...) Would be good to hear from Alexei and Martin to not waste your time iterating on this. The rest looks good to me.
I would prefer the earlier definition on nr_hashes:
Quoted 1 line
Quoted 1 line
Quoted 1 line
nr_hash== 0bit_idx== key for set/read/clear
With nr_hash == 0, the value (or key) is the position of a bit. Since it is the position of a bit, it is easier to understand if the value is some integers, either __u8,__u16,__u32, or __u64, so I don't see a need on noop.
As the position of a bit, I would even limit the value_size either to be sizeof(__u32) or sizeof(__u64) for this case to keep it simple.
Quoted 1 line
Quoted 1 line
Quoted 1 line
nr_hashes>= 1 bit_idx[1..N] =hash(key, N)for set/read/clear.
With nr_hashes != 0 (let say nr_hashes == N), the value (or key) is hashed N number of times to set N bits. I don't see a need
to limit any non-zero value_size or XOR must be used with nr_hashes == 1. Some hashes may need special handling for non 4-bytes or non 8-bytes value_size but if possible that should be something internal to the kernel implementation instead of limiting what value_size can be hashed.
Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation
In reply to Joanne KoongQuoted 73 lines · Joanne Koong
Quoted 62 lines · Andrii Nakryiko
Quoted 59 lines · Joanne Koong
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 should never be.
This patch adds a bloom filter map for bpf programs. The bloom filter map supports peek (determining whether an element is present in the map) and push (adding an element to the map) operations.These operations are exposed to userspace applications through the already existing syscalls in the following way:
BPF_MAP_LOOKUP_ELEM-> peekBPF_MAP_UPDATE_ELEM-> pushThe bloom filter map does not have keys, only values. In light of this, the bloom filter map's API matches that of queue stack maps:
user applications use BPF_MAP_LOOKUP_ELEM/BPF_MAP_UPDATE_ELEM which correspond internally to bpf_map_peek_elem/bpf_map_push_elem, and bpf programs must use thebpf_map_peek_elemandbpf_map_push_elemAPIs to query or add an element to the bloom filter map. When the bloom filter map is created, it must be created with akey_sizeof 0.For updates, the user will pass in the element to add to the map as the value, with a NULL key. For lookups, the user will pass in the element to query in the map as the value. In the verifier layer, this requires us to modify the argument type of a bloom filter's
BPF_FUNC_map_peek_elemcall toARG_PTR_TO_MAP_VALUE; as well, in the syscall layer, we need to copy over the user value so that inbpf_map_peek_elem, we know which specific value to query.A few things to please take note of:
* If there are any concurrent lookups + updates, the user is
responsible for synchronizing this to ensure no false negative lookups occur.
* The number of hashes to use for the bloom filter is configurable from
userspace. If no number is specified, the default used will be 5 hash functions. The benchmarks later in this patchset can help compare the performance of using different number of hashes on different entry sizes. In general, using more hashes decreases the speed of a lookup, but increases the false positive rate of an element being detected in the bloom filter.
* Deleting an element in the bloom filter map is not supported.
* The bloom filter map may be used as an inner map.
* The "max_entries" size that is specified at map creation time is used to
approximate a reasonable bitmap size for the bloom filter, and is not otherwise strictly enforced. If the user wishes to insert more entries into the bloom filter than "max_entries", they may do so but they should be aware that this may lead to a higher false positive rate.Signed-off-by Joanne Koong <[email protected]>--- include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 1 + kernel/bpf/Makefile | 2 +- kernel/bpf/bloom_filter.c | 185 +++++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 14 ++- kernel/bpf/verifier.c | 19 +++- tools/include/uapi/linux/bpf.h | 1 + 7 files changed, 217 insertions(+), 6 deletions(-)Quoted 2 lines
create mode 100644
kernel/bpf/bloom_filter.cQuoted 8 lines
See some stylistic nitpicking below (and not a nitpicking about BTF).
But I just wanted to say that I'm a bit amazed by how much special casing this
BLOOM_FILTERmap requires insyscall.candverifier.c. I still believe that starting with a BPF helper for hashing would be a better approach, but oh well.[...]
Quoted 9 lines
I liked your comment on v1 regarding using a BPF helper and I agree with the benefits
you outlined. I'm curious to see what the performance differences between that approach
and this one end up being, if any. I plan to test out the BPF helper approach in a few weeks,
and if the performance is comparable or better, I am definitely open to reverting this code
and just going with the BPF helper approach :)
I got curious myself yesterday and spent the evening trying this out. There is slight performance regression in pure bloom filter querying performance. More confusingly, with such a small difference in bloom filter performance, there is a much more noticeable difference in the hybrid bloom+hashmap benchmark. I don't know how to explain the difference. It might be just the multiplying effect of small perf differences due to subsequent hashmap lookup. TBH, we are talking about millions of operations per second, and I don't think in practice it will matter much. It's like XDP microbenchmarks, where as soon as you start doing something useful that overhead trumps whatever small overhead BPF/XDP/bloom filter causes. But I'm not going to argue about that here :)
I just sent and RFC patch set to demonstrate the approach and compare with your results. They are not in Patchworks yet, but they are on lore for those following along ([0]).
While doing that I found a problem with the way you implemented benchmark measuring. I've also optimized few stats collecting parts. Please take a look at the RFC. If anything, it would be good to incorporate those fixes.
It would also be good to add benchmark that test keys bigger than 8 bytes, as mentioned before. I haven't found that in your benchmark. Also, they way benchmark is implemented right now, it spends lots of (measured) time doing stuff like generating random values on the fly. There is also no control over the ratio of hits and misses. It feels like the benchmark is over-optimizing for happy case of bloom filter having a true negative and thus proceeding very fast. There are barely any hits at all (they don't even register in the benchmark).
It also turned out that you don't benchmark updating Bloom filter from BPF program side. Was that intentional or you anticipate that in practice that won't be necessary? I was curious to compare those results because the rely on BPF atomics, but I didn't go all the way to add them.
[0] https://lore.kernel.org/bpf/[email protected]/T/#t
Quoted 16 lines
Quoted 16 lines
kernel/bpf/bloom_filter.c line 37
Quoted 11 lines
kernel/bpf/bloom_filter.c new file +11
-0+ +static inline u32 hash (struct bpf_bloom_filter *bloom_filter,void *value, +u64 value_size,u32 index) +{ +if (bloom_filter->aligned_u32_count) +return jhash2 (value, bloom_filter->aligned_u32_count, + bloom_filter->hash_seed + index) & + bloom_filter->bit_array_mask; + +return jhash (value, value_size, bloom_filter->hash_seed + index) & + bloom_filter->bit_array_mask;stylistic nit, but this feels way to dense text-wise, this seems easier to follow
u32 h;
Quoted 8 lines
Quoted 7 lines
if (
bloom_filter->aligned_u32_count)h = jhash2(...); else h = jhash(...);return h &
bloom_filter->bit_array_mask;WDYT?
I think this sounds great! I will make these changes for v4.
great
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
(quoted diff) +2
-0+} +
[...]
Quoted 16 lines
Quoted 8 lines
Quoted 8 lines
kernel/bpf/bloom_filter.c new file +8
-0+ +static int bloom_filter_map_btf_id; +const struct bpf_map_ops bloom_filter_map_ops = { + .map_meta_equal = bpf_map_meta_equal, + .map_alloc = bloom_filter_map_alloc, + .map_free = bloom_filter_map_free, + .map_push_elem = bloom_filter_map_push_elem, + .map_peek_elem = bloom_filter_map_peek_elem,Quoted 8 lines
kernel/bpf/bloom_filter.c line 182
Quoted 5 lines
kernel/bpf/bloom_filter.c new file +5
-0+ .map_lookup_elem = bloom_filter_map_lookup_elem, + .map_update_elem = bloom_filter_map_update_elem, + .map_delete_elem = bloom_filter_map_delete_elem, + .map_get_next_key = bloom_filter_map_get_next_key, + .map_check_btf = map_check_no_btf,can you please implement basically a no-op callback here to allow specifying
btf_value_id, there is no good reason to restrict this new map to not allow BTF type being specified for its value
Quoted 1 line
Sounds great, will add this in v4.
cool, we should try to support BTF for all new maps
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines
kernel/bpf/bloom_filter.c new file +3
-0+ .map_btf_name = "bpf_bloom_filter", + .map_btf_id = &bloom_filter_map_btf_id, +};[...]
PATCH v3 2/5 libbpf: Allow the number of hashes in bloom filter maps to be configurable
In reply to Joanne KoongThis patch adds the libbpf infrastructure that will allow the user to specify a configurable number of hash functions to use for the bloom filter map.
Please note that this patch does not enforce that a pinned bloom filter map may only be reused if the number of hash functions is the same. If they are not the same, the number of hash functions used will be the one that was set for the pinned map.
--- include/uapi/linux/bpf.h | 5 ++++- tools/include/uapi/linux/bpf.h | 5 ++++- tools/lib/bpf/bpf.c | 2 ++ tools/lib/bpf/bpf.h | 1 + tools/lib/bpf/libbpf.c | 32 +++++++++++++++++++++++++++----- tools/lib/bpf/libbpf.h | 2 ++ tools/lib/bpf/libbpf.map | 1 + tools/lib/bpf/libbpf_internal.h | 4 +++- 8 files changed, 44 insertions(+), 8 deletions(-)
include/uapi/linux/bpf.h +4 -1
@@ -1262,7 +1262,10 @@ union bpf_attr {__u32 map_flags;/* BPF_MAP_CREATE related * flags defined above. */ -__u32 inner_map_fd;/* fd pointing to the inner map */ +union { +__u32 inner_map_fd;/* fd pointing to the inner map */ +__u32 nr_hash_funcs;/* or number of hash functions */ + };__u32 numa_node;/* numa node (effective only if * BPF_F_NUMA_NODE is set). */
tools/include/uapi/linux/bpf.h +4 -1
@@ -1262,7 +1262,10 @@ union bpf_attr {__u32 map_flags;/* BPF_MAP_CREATE related * flags defined above. */ -__u32 inner_map_fd;/* fd pointing to the inner map */ +union { +__u32 inner_map_fd;/* fd pointing to the inner map */ +__u32 nr_hash_funcs;/* or number of hash functions */ + };__u32 numa_node;/* numa node (effective only if * BPF_F_NUMA_NODE is set). */
tools/lib/bpf/bpf.c +2 -0
@@ -100,6 +100,8 @@ int bpf_create_map_xattr(const struct bpf_create_map_attr *create_attr)if (attr.map_type ==BPF_MAP_TYPE_STRUCT_OPS ) attr.btf_vmlinux_value_type_id = create_attr->btf_vmlinux_value_type_id; +else if (attr.map_type ==BPF_MAP_TYPE_BLOOM_FILTER ) + attr.nr_hash_funcs = create_attr->nr_hash_funcs;else attr.inner_map_fd = create_attr->inner_map_fd;
tools/lib/bpf/bpf.h +1 -0
@@ -49,6 +49,7 @@ struct bpf_create_map_attr {union {__u32 inner_map_fd;__u32 btf_vmlinux_value_type_id; +__u32 nr_hash_funcs; }; };
tools/lib/bpf/libbpf.c +27 -5
@@ -378,6 +378,7 @@ struct bpf_map {char *pin_path;bool pinned;bool reused; +__u32 nr_hash_funcs; };enum extern_type {
@@ -1291,6 +1292,11 @@ static bool bpf_map_type__is_map_in_map(enum bpf_map_type type)return false; } +static inline bool bpf_map__is_bloom_filter (const struct bpf_map *map) +{ +return map->def.type ==BPF_MAP_TYPE_BLOOM_FILTER ; +} +int bpf_object__section_size (const struct bpf_object *obj,const char *name,__u32 *size) {
@@ -2238,6 +2244,10 @@ int parse_btf_map_def(const char *map_name, struct btf *btf, } map_def->pinning = val; map_def->parts |=MAP_DEF_PINNING ; + }else if (strcmp (name,"nr_hash_funcs" ) ==0 ) { +if (!get_map_field_int (map_name, btf, m, &map_def->nr_hash_funcs)) +return -EINVAL ; + map_def->parts |=MAP_DEF_NR_HASH_FUNCS ; }else {if (strict) {pr_warn ("map '%s': unknown field '%s'.\n" , map_name, name);
@@ -2266,6 +2276,7 @@ static void fill_map_from_def(struct bpf_map *map, const struct btf_map_def *def map->numa_node = def->numa_node; map->btf_key_type_id = def->key_type_id; map->btf_value_type_id = def->value_type_id; + map->nr_hash_funcs = def->nr_hash_funcs;if (def->parts &MAP_DEF_MAP_TYPE )pr_debug ("map '%s': found type = %u.\n" , map->name, def->map_type);
@@ -2290,6 +2301,8 @@ static void fill_map_from_def(struct bpf_map *map, const struct btf_map_def *defpr_debug ("map '%s': found pinning = %u.\n" , map->name, def->pinning);if (def->parts &MAP_DEF_NUMA_NODE )pr_debug ("map '%s': found numa_node = %u.\n" , map->name, def->numa_node); +if (def->parts &MAP_DEF_NR_HASH_FUNCS ) +pr_debug ("map '%s': found nr_hash_funcs = %u.\n" , map->name, def->nr_hash_funcs);if (def->parts &MAP_DEF_INNER_MAP )pr_debug ("map '%s': found inner map definition.\n" , map->name);
@@ -4616,10 +4629,6 @@ static int bpf_object__create_map(struct bpf_object *obj, struct bpf_map *map, b create_attr.max_entries = def->max_entries; } -if (bpf_map__is_struct_ops (map)) - create_attr.btf_vmlinux_value_type_id = - map->btf_vmlinux_value_type_id; - create_attr.btf_fd =0 ; create_attr.btf_key_type_id =0 ; create_attr.btf_value_type_id =0 ;
@@ -4629,7 +4638,12 @@ static int bpf_object__create_map(struct bpf_object *obj, struct bpf_map *map, b create_attr.btf_value_type_id = map->btf_value_type_id; } -if (bpf_map_type__is_map_in_map (def->type)) { +if (bpf_map__is_struct_ops (map)) { + create_attr.btf_vmlinux_value_type_id = + map->btf_vmlinux_value_type_id; + }else if (bpf_map__is_bloom_filter (map)) { + create_attr.nr_hash_funcs = map->nr_hash_funcs; + }else if (bpf_map_type__is_map_in_map (def->type)) {if (map->inner_map) { err =bpf_object__create_map (obj, map->inner_map, true);if (err) {
@@ -8610,6 +8624,14 @@ int bpf_map__set_value_size(struct bpf_map *map, __u32 size)return 0 ; } +int bpf_map__set_nr_hash_funcs (struct bpf_map *map,__u32 nr_hash_funcs) +{ +if (map->fd >=0 ) +return libbpf_err (-EBUSY ); + map->nr_hash_funcs = nr_hash_funcs; +return 0 ; +} +__u32 bpf_map__btf_key_type_id (const struct bpf_map *map) {return map ? map->btf_key_type_id :0 ;
tools/lib/bpf/libbpf.h +2 -0
@@ -550,6 +550,8 @@ LIBBPF_API __u32 bpf_map__btf_value_type_id(const struct bpf_map *map);/* get/set map if_index */ LIBBPF_API __u32 bpf_map__ifindex(const struct bpf_map *map); LIBBPF_API int bpf_map__set_ifindex(struct bpf_map *map, __u32 ifindex); +/* set nr_hash_funcs */ +LIBBPF_API int bpf_map__set_nr_hash_funcs(struct bpf_map *map, __u32 nr_hash_funcs);typedef void (*bpf_map_clear_priv_t )(struct bpf_map *,void *); LIBBPF_API int bpf_map__set_priv(struct bpf_map *map, void *priv,
tools/lib/bpf/libbpf.map +1 -0
@@ -385,6 +385,7 @@ LIBBPF_0.5.0 { btf__load_vmlinux_btf; btf_dump__dump_type_data; libbpf_set_strict_mode; + bpf_map__set_nr_hash_funcs; } LIBBPF_0.4.0; LIBBPF_0.6.0 {
tools/lib/bpf/libbpf_internal.h +3 -1
@@ -186,8 +186,9 @@ enum map_def_parts {MAP_DEF_NUMA_NODE =0x080 ,MAP_DEF_PINNING =0x100 ,MAP_DEF_INNER_MAP =0x200 , +MAP_DEF_NR_HASH_FUNCS =0x400 , - MAP_DEF_ALL = 0x3ff, /* combination of all above */ + MAP_DEF_ALL = 0x7ff, /* combination of all above */ }; struct btf_map_def {
@@ -201,6 +202,7 @@ struct btf_map_def {__u32 map_flags;__u32 numa_node;__u32 pinning; +__u32 nr_hash_funcs; }; int parse_btf_map_def(const char *map_name, struct btf *btf,
Signature · 1 line
2.30.2
Re: [PATCH v3 bpf-next 2/5] libbpf: Allow the number of hashes in bloom filter maps to be configurable
Quoted 211 lines · Joanne Koong
This patch adds the libbpf infrastructure that will allow the user to specify a configurable number of hash functions to use for the bloom filter map.
Please note that this patch does not enforce that a pinned bloom filter map may only be reused if the number of hash functions is the same. If they are not the same, the number of hash functions used will be the one that was set for the pinned map.
Signed-off-by Joanne Koong <[email protected]>--- include/uapi/linux/bpf.h | 5 ++++- tools/include/uapi/linux/bpf.h | 5 ++++- tools/lib/bpf/bpf.c | 2 ++ tools/lib/bpf/bpf.h | 1 + tools/lib/bpf/libbpf.c | 32 +++++++++++++++++++++++++++----- tools/lib/bpf/libbpf.h | 2 ++ tools/lib/bpf/libbpf.map | 1 + tools/lib/bpf/libbpf_internal.h | 4 +++- 8 files changed, 44 insertions(+), 8 deletions(-)include/uapi/linux/bpf.h +4
-1@@ -1262,7 +1262,10 @@ union bpf_attr {__u32 map_flags;/* BPF_MAP_CREATE related * flags defined above. */ -__u32 inner_map_fd;/* fd pointing to the inner map */ +union { +__u32 inner_map_fd;/* fd pointing to the inner map */ +__u32 nr_hash_funcs;/* or number of hash functions */ + };__u32 numa_node;/* numa node (effective only if * BPF_F_NUMA_NODE is set). */ tools/include/uapi/linux/bpf.h +4
-1@@ -1262,7 +1262,10 @@ union bpf_attr {__u32 map_flags;/* BPF_MAP_CREATE related * flags defined above. */ -__u32 inner_map_fd;/* fd pointing to the inner map */ +union { +__u32 inner_map_fd;/* fd pointing to the inner map */ +__u32 nr_hash_funcs;/* or number of hash functions */ + };__u32 numa_node;/* numa node (effective only if * BPF_F_NUMA_NODE is set). */ tools/lib/bpf/bpf.c +2
-0@@ -100,6 +100,8 @@ int bpf_create_map_xattr(const struct bpf_create_map_attr *create_attr)if (attr.map_type ==BPF_MAP_TYPE_STRUCT_OPS ) attr.btf_vmlinux_value_type_id = create_attr->btf_vmlinux_value_type_id; +else if (attr.map_type ==BPF_MAP_TYPE_BLOOM_FILTER ) + attr.nr_hash_funcs = create_attr->nr_hash_funcs;else attr.inner_map_fd = create_attr->inner_map_fd;tools/lib/bpf/bpf.h +1
-0@@ -49,6 +49,7 @@ struct bpf_create_map_attr {union {__u32 inner_map_fd;__u32 btf_vmlinux_value_type_id; +__u32 nr_hash_funcs; }; };tools/lib/bpf/libbpf.c +27
-5@@ -378,6 +378,7 @@ struct bpf_map {char *pin_path;bool pinned;bool reused; +__u32 nr_hash_funcs; };enum extern_type {@@ -1291,6 +1292,11 @@ static bool bpf_map_type__is_map_in_map(enum bpf_map_type type)return false; } +static inline bool bpf_map__is_bloom_filter (const struct bpf_map *map) +{ +return map->def.type ==BPF_MAP_TYPE_BLOOM_FILTER ; +} +int bpf_object__section_size (const struct bpf_object *obj,const char *name,__u32 *size) {@@ -2238,6 +2244,10 @@ int parse_btf_map_def(const char *map_name, struct btf *btf, } map_def->pinning = val; map_def->parts |=MAP_DEF_PINNING ; + }else if (strcmp (name,"nr_hash_funcs" ) ==0 ) { +if (!get_map_field_int (map_name, btf, m, &map_def->nr_hash_funcs)) +return -EINVAL ; + map_def->parts |=MAP_DEF_NR_HASH_FUNCS ; }else {if (strict) {pr_warn ("map '%s': unknown field '%s'.\n" , map_name, name);@@ -2266,6 +2276,7 @@ static void fill_map_from_def(struct bpf_map *map, const struct btf_map_def *def map->numa_node = def->numa_node; map->btf_key_type_id = def->key_type_id; map->btf_value_type_id = def->value_type_id; + map->nr_hash_funcs = def->nr_hash_funcs;if (def->parts &MAP_DEF_MAP_TYPE )pr_debug ("map '%s': found type = %u.\n" , map->name, def->map_type);@@ -2290,6 +2301,8 @@ static void fill_map_from_def(struct bpf_map *map, const struct btf_map_def *defpr_debug ("map '%s': found pinning = %u.\n" , map->name, def->pinning);if (def->parts &MAP_DEF_NUMA_NODE )pr_debug ("map '%s': found numa_node = %u.\n" , map->name, def->numa_node); +if (def->parts &MAP_DEF_NR_HASH_FUNCS ) +pr_debug ("map '%s': found nr_hash_funcs = %u.\n" , map->name, def->nr_hash_funcs);if (def->parts &MAP_DEF_INNER_MAP )pr_debug ("map '%s': found inner map definition.\n" , map->name);@@ -4616,10 +4629,6 @@ static int bpf_object__create_map(struct bpf_object *obj, struct bpf_map *map, b create_attr.max_entries = def->max_entries; } -if (bpf_map__is_struct_ops (map)) - create_attr.btf_vmlinux_value_type_id = - map->btf_vmlinux_value_type_id; - create_attr.btf_fd =0 ; create_attr.btf_key_type_id =0 ; create_attr.btf_value_type_id =0 ;@@ -4629,7 +4638,12 @@ static int bpf_object__create_map(struct bpf_object *obj, struct bpf_map *map, b create_attr.btf_value_type_id = map->btf_value_type_id; } -if (bpf_map_type__is_map_in_map (def->type)) { +if (bpf_map__is_struct_ops (map)) { + create_attr.btf_vmlinux_value_type_id = + map->btf_vmlinux_value_type_id; + }else if (bpf_map__is_bloom_filter (map)) { + create_attr.nr_hash_funcs = map->nr_hash_funcs; + }else if (bpf_map_type__is_map_in_map (def->type)) {if (map->inner_map) { err =bpf_object__create_map (obj, map->inner_map, true);if (err) {@@ -8610,6 +8624,14 @@ int bpf_map__set_value_size(struct bpf_map *map, __u32 size)return 0 ; } +int bpf_map__set_nr_hash_funcs (struct bpf_map *map,__u32 nr_hash_funcs) +{ +if (map->fd >=0 ) +return libbpf_err (-EBUSY ); + map->nr_hash_funcs = nr_hash_funcs; +return 0 ; +} +__u32 bpf_map__btf_key_type_id (const struct bpf_map *map) {return map ? map->btf_key_type_id :0 ;tools/lib/bpf/libbpf.h +2
-0@@ -550,6 +550,8 @@ LIBBPF_API __u32 bpf_map__btf_value_type_id(const struct bpf_map *map);/* get/set map if_index */ LIBBPF_API __u32 bpf_map__ifindex(const struct bpf_map *map); LIBBPF_API int bpf_map__set_ifindex(struct bpf_map *map, __u32 ifindex); +/* set nr_hash_funcs */ +LIBBPF_API int bpf_map__set_nr_hash_funcs(struct bpf_map *map, __u32 nr_hash_funcs);typedef void (*bpf_map_clear_priv_t )(struct bpf_map *,void *); LIBBPF_API int bpf_map__set_priv(struct bpf_map *map, void *priv,tools/lib/bpf/libbpf.map +1
-0@@ -385,6 +385,7 @@ LIBBPF_0.5.0 { btf__load_vmlinux_btf; btf_dump__dump_type_data; libbpf_set_strict_mode; + bpf_map__set_nr_hash_funcs; } LIBBPF_0.4.0; LIBBPF_0.6.0 {tools/lib/bpf/libbpf_internal.h +2
-1@@ -186,8 +186,9 @@ enum map_def_parts {MAP_DEF_NUMA_NODE =0x080 ,MAP_DEF_PINNING =0x100 ,MAP_DEF_INNER_MAP =0x200 , +MAP_DEF_NR_HASH_FUNCS =0x400 , - MAP_DEF_ALL = 0x3ff, /* combination of all above */ + MAP_DEF_ALL = 0x7ff, /* combination of all above */ }; struct btf_map_def {
tools/lib/bpf/libbpf_internal.h struct btf_map_def { · line 207
Quoted 6 lines
tools/lib/bpf/libbpf_internal.h +1
-0@@ -201,6 +202,7 @@ struct btf_map_def {__u32 map_flags;__u32 numa_node;__u32 pinning; +__u32 nr_hash_funcs; };
I just realized that Andrii's comment on v1 stated that btf_map_def is fixed indefinitely.
This implies that for bloom filter maps where the number of hash functions needs to be set, we will not be able to use the BTF-defined format and will instead need to use the older map definition that uses bpf_map_def. Is my understanding of this correct? If so, I will go ahead and fix this for v4.
Quoted 1 line
tools/lib/bpf/libbpf_internal.h +0
-0int parse_btf_map_def(const char *map_name, struct btf *btf,
Re: [PATCH v3 bpf-next 2/5] libbpf: Allow the number of hashes in bloom filter maps to be configurable
Quoted 24 lines · Joanne Koong
Quoted 21 lines · Joanne Koong
This patch adds the libbpf infrastructure that will allow the user to specify a configurable number of hash functions to use for the bloom filter map.
Please note that this patch does not enforce that a pinned bloom filter map may only be reused if the number of hash functions is the same. If they are not the same, the number of hash functions used will be the one that was set for the pinned map.
Signed-off-by Joanne Koong <[email protected]>--- include/uapi/linux/bpf.h | 5 ++++- tools/include/uapi/linux/bpf.h | 5 ++++- tools/lib/bpf/bpf.c | 2 ++ tools/lib/bpf/bpf.h | 1 + tools/lib/bpf/libbpf.c | 32 +++++++++++++++++++++++++++----- tools/lib/bpf/libbpf.h | 2 ++ tools/lib/bpf/libbpf.map | 1 + tools/lib/bpf/libbpf_internal.h | 4 +++- 8 files changed, 44 insertions(+), 8 deletions(-)
[...]
Quoted 13 lines
tools/lib/bpf/libbpf_internal.h struct btf_map_def { · line 207
Quoted 9 lines
struct btf_map_def {tools/lib/bpf/libbpf_internal.h +1
-0@@ -201,6 +202,7 @@ struct btf_map_def {__u32 map_flags;__u32 numa_node;__u32 pinning; +__u32 nr_hash_funcs; };I just realized that Andrii's comment on v1 stated that
btf_map_defis fixed indefinitely.
Quoted 7 lines
This implies that for bloom filter maps where the number of hash functions needs to be set,
we will not be able to use the BTF-defined format and will instead need to use the older
map definition that usesbpf_map_def. Is my understanding of this correct? If so, I will go
ahead and fix this for v4.
You are confusing bpf_map_def (which is part of the public libbpf API, even if to-be-deprecated) and btf_map_def, which is only libbpf-internal. So it's ok to modify that struct.
Quoted 2 lines
Quoted 2 lines
tools/lib/bpf/libbpf_internal.h +0
-0int parse_btf_map_def(const char *map_name, struct btf *btf,
Re: [PATCH v3 bpf-next 2/5] libbpf: Allow the number of hashes in bloom filter maps to be configurable
In reply to Joanne KoongQuoted 44 lines · Joanne Koong
This patch adds the libbpf infrastructure that will allow the user to specify a configurable number of hash functions to use for the bloom filter map.
Please note that this patch does not enforce that a pinned bloom filter map may only be reused if the number of hash functions is the same. If they are not the same, the number of hash functions used will be the one that was set for the pinned map.
Signed-off-by Joanne Koong <[email protected]>--- include/uapi/linux/bpf.h | 5 ++++- tools/include/uapi/linux/bpf.h | 5 ++++- tools/lib/bpf/bpf.c | 2 ++ tools/lib/bpf/bpf.h | 1 + tools/lib/bpf/libbpf.c | 32 +++++++++++++++++++++++++++----- tools/lib/bpf/libbpf.h | 2 ++ tools/lib/bpf/libbpf.map | 1 + tools/lib/bpf/libbpf_internal.h | 4 +++- 8 files changed, 44 insertions(+), 8 deletions(-)include/uapi/linux/bpf.h +4
-1@@ -1262,7 +1262,10 @@ union bpf_attr {__u32 map_flags;/* BPF_MAP_CREATE related * flags defined above. */ -__u32 inner_map_fd;/* fd pointing to the inner map */ +union { +__u32 inner_map_fd;/* fd pointing to the inner map */ +__u32 nr_hash_funcs;/* or number of hash functions */ + };__u32 numa_node;/* numa node (effective only if * BPF_F_NUMA_NODE is set). */ tools/include/uapi/linux/bpf.h +0
-0@@ -1262,7 +1262,10 @@ union bpf_attr {__u32 map_flags;/* BPF_MAP_CREATE related
tools/include/uapi/linux/bpf.h union bpf_attr { · line 1271
Quoted 10 lines
tools/include/uapi/linux/bpf.h +4
-1* flags defined above. */ -__u32 inner_map_fd;/* fd pointing to the inner map */ +union { +__u32 inner_map_fd;/* fd pointing to the inner map */ +__u32 nr_hash_funcs;/* or number of hash functions */ + };__u32 numa_node;/* numa node (effective only if * BPF_F_NUMA_NODE is set). */
these changes should be part of patch 1, otherwise patch 1 leaves kernel in non-compilable state and breaks bisection
Quoted 30 lines
tools/lib/bpf/bpf.c +2
-0@@ -100,6 +100,8 @@ int bpf_create_map_xattr(const struct bpf_create_map_attr *create_attr)if (attr.map_type ==BPF_MAP_TYPE_STRUCT_OPS ) attr.btf_vmlinux_value_type_id = create_attr->btf_vmlinux_value_type_id; +else if (attr.map_type ==BPF_MAP_TYPE_BLOOM_FILTER ) + attr.nr_hash_funcs = create_attr->nr_hash_funcs;else attr.inner_map_fd = create_attr->inner_map_fd;tools/lib/bpf/bpf.h +1
-0@@ -49,6 +49,7 @@ struct bpf_create_map_attr {union {__u32 inner_map_fd;__u32 btf_vmlinux_value_type_id; +__u32 nr_hash_funcs; }; };tools/lib/bpf/libbpf.c +0
-0
tools/lib/bpf/libbpf.c struct bpf_map { · line 381
Quoted 4 lines
tools/lib/bpf/libbpf.c +1
-0@@ -378,6 +378,7 @@ struct bpf_map {char *pin_path;bool pinned;bool reused; +__u32 nr_hash_funcs;
nit: please keep it next to inner_map_fd field
tools/lib/bpf/libbpf.c static bool bpf_map_type__is_map_in_map(enum bpf_map_type type) · line 1298
Quoted 11 lines
tools/lib/bpf/libbpf.c +4
-0};enum extern_type {@@ -1291,6 +1292,11 @@ static bool bpf_map_type__is_map_in_map(enum bpf_map_type type)return false; } +static inline bool bpf_map__is_bloom_filter (const struct bpf_map *map) +{ +return map->def.type ==BPF_MAP_TYPE_BLOOM_FILTER ; +}
this is used in only one place, it's ok to just open-code it
Quoted 4 lines
tools/lib/bpf/libbpf.c +1
-0+int bpf_object__section_size (const struct bpf_object *obj,const char *name,__u32 *size) {
[...]
tools/lib/bpf/libbpf.c int bpf_map__set_value_size(struct bpf_map *map, __u32 size) · line 8630
Quoted 8 lines
tools/lib/bpf/libbpf.c +4
-0@@ -8610,6 +8624,14 @@ int bpf_map__set_value_size(struct bpf_map *map, __u32 size)return 0 ; } +int bpf_map__set_nr_hash_funcs (struct bpf_map *map,__u32 nr_hash_funcs) +{ +if (map->fd >=0 ) +return libbpf_err (-EBUSY );
should we disallow this for anything but BLOOM_FILTER?
Quoted 12 lines
tools/lib/bpf/libbpf.c +4
-0+ map->nr_hash_funcs = nr_hash_funcs; +return 0 ; +} +__u32 bpf_map__btf_key_type_id (const struct bpf_map *map) {return map ? map->btf_key_type_id :0 ;tools/lib/bpf/libbpf.h +0
-0
tools/lib/bpf/libbpf.h LIBBPF_API __u32 bpf_map__btf_value_type_id(const struct bpf_map *map); · line 554
Quoted 5 lines
tools/lib/bpf/libbpf.h +2
-0@@ -550,6 +550,8 @@ LIBBPF_API __u32 bpf_map__btf_value_type_id(const struct bpf_map *map);/* get/set map if_index */ LIBBPF_API __u32 bpf_map__ifindex(const struct bpf_map *map); LIBBPF_API int bpf_map__set_ifindex(struct bpf_map *map, __u32 ifindex); +/* set nr_hash_funcs */ +LIBBPF_API int bpf_map__set_nr_hash_funcs(struct bpf_map *map, __u32 nr_hash_funcs);
Let's not add this setter at all right now. Let's allow setting this from BPF source code only in BTF map definition. It's unlikely anyone would be setting the number of hash functions dynamically and I just hate the idea of this one-off setter just for one specific map type. We can always add it later if there really will be a need for that.
Quoted 3 lines
tools/lib/bpf/libbpf.h +0
-0typedef void (*bpf_map_clear_priv_t )(struct bpf_map *,void *); LIBBPF_API int bpf_map__set_priv(struct bpf_map *map, void *priv,
[...]
PATCH v3 3/5 selftests/bpf: Add bloom filter map test cases
In reply to Joanne KoongThis patch adds test cases for bpf bloom filter maps. They include tests checking against invalid operations by userspace, tests for using the bloom filter map as an inner map, and a bpf program that queries the bloom filter map for values added by a userspace program.
--- .../bpf/prog_tests/bloom_filter_map.c | 177 ++++++++++++++++++ .../selftests/bpf/progs/bloom_filter_map.c | 83 ++++++++ 2 files changed, 260 insertions(+) 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
tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c new file +177 -0
@@ -0,0 +1,177 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include <sys/syscall.h> +#include <test_progs.h> +#include "bloom_filter_map.skel.h" + +static void test_bloom_filter_map_fail (void ) +{ +struct bpf_create_map_attr xattr = { + .name ="bloom_filter_map" , + .map_type =BPF_MAP_TYPE_BLOOM_FILTER , + .max_entries =100 , + .value_size =sizeof (__u32), + .nr_hash_funcs =3 , + }; +__u32 value; +int fd, err; + +/* Invalid key size */ + xattr.key_size =4 ; + fd =bpf_create_map_xattr (&xattr); +if (!ASSERT_LT (fd,0 ,"bpf_create_map bloom filter invalid key size" )) +close (fd); + xattr.key_size =0 ; + +/* Invalid value size */ + xattr.value_size =0 ; + fd =bpf_create_map_xattr (&xattr); +if (!ASSERT_LT (fd,0 ,"bpf_create_map bloom filter invalid value size" )) +close (fd); + xattr.value_size =sizeof (__u32); + +/* Invalid max entries size */ + xattr.max_entries =0 ; + fd =bpf_create_map_xattr (&xattr); +if (!ASSERT_LT (fd,0 ,"bpf_create_map bloom filter invalid max entries size" )) +close (fd); + xattr.max_entries =100 ; + +/* Bloom filter maps do not support BPF_F_NO_PREALLOC */ + xattr.map_flags =BPF_F_NO_PREALLOC ; + fd =bpf_create_map_xattr (&xattr); +if (!ASSERT_LT (fd,0 ,"bpf_create_map bloom filter invalid flags" )) +close (fd); + xattr.map_flags =0 ; + + fd =bpf_create_map_xattr (&xattr); +if (!ASSERT_GE (fd,0 ,"bpf_create_map bloom filter" )) +return ; + +/* Test invalid flags */ + err =bpf_map_update_elem (fd,NULL , &value,-1 ); +ASSERT_EQ (err, -EINVAL ,"bpf_map_update_elem bloom filter invalid flags" ); + + err =bpf_map_update_elem (fd,NULL , &value,BPF_EXIST ); +ASSERT_EQ (err, -EINVAL ,"bpf_map_update_elem bloom filter invalid flags" ); + + err =bpf_map_update_elem (fd,NULL , &value,BPF_F_LOCK ); +ASSERT_EQ (err, -EINVAL ,"bpf_map_update_elem bloom filter invalid flags" ); + + err =bpf_map_update_elem (fd,NULL , &value,BPF_NOEXIST ); +ASSERT_EQ (err, -EINVAL ,"bpf_map_update_elem bloom filter invalid flags" ); + + err =bpf_map_update_elem (fd,NULL , &value,10000 ); +ASSERT_EQ (err, -EINVAL ,"bpf_map_update_elem bloom filter invalid flags" ); + +close (fd); +} + +static void bloom_filter_map (struct bloom_filter_map *skel) +{ +const int map_size =bpf_map__max_entries (skel->maps.map_random_data); +int err, map_random_data_fd, map_bloom_filter_fd, i; +__u64 val; +struct bpf_link *link; + + map_random_data_fd =bpf_map__fd (skel->maps.map_random_data); + map_bloom_filter_fd =bpf_map__fd (skel->maps.map_bloom_filter); + +/* Generate random values and add them to the maps */ +for (i =0 ; i < map_size; i++) { + val =rand (); + err =bpf_map_update_elem (map_random_data_fd, &i, &val,BPF_ANY ); +if (!ASSERT_OK (err,"Add random value to map_random_data" )) +continue ; + + err =bpf_map_update_elem (map_bloom_filter_fd,NULL , &val,0 ); +if (!ASSERT_OK (err,"Add random value to map_bloom_filter" )) +return ; + } + + link =bpf_program__attach (skel->progs.prog_bloom_filter); +if (!ASSERT_OK_PTR (link,"link" )) +return ; + +syscall (SYS_getpgid); + +ASSERT_EQ (skel->bss->error,0 ,"error" ); + +bpf_link__destroy (link); +} + +static void bloom_filter_inner_map (struct bloom_filter_map *skel) +{ +const int map_size =bpf_map__max_entries (skel->maps.map_random_data); +int outer_map_fd, inner_map_fd, map_random_data_fd, err, i, key =0 ; +struct bpf_create_map_attr xattr = { + .name ="bloom_filter_inner_map" , + .map_type =BPF_MAP_TYPE_BLOOM_FILTER , + .max_entries = map_size, + .value_size =sizeof (__u64), + }; +struct bpf_link *link; +__u64 val; + +/* Create a bloom filter map that will be used as the inner map */ + inner_map_fd =bpf_create_map_xattr (&xattr); +if (!ASSERT_GE (inner_map_fd,0 ,"bpf_create_map bloom filter map as inner map" )) +return ; + +/* Generate random values and add them to the maps */ + map_random_data_fd =bpf_map__fd (skel->maps.map_random_data); +for (i =0 ; i < map_size; i++) { + val =rand (); + err =bpf_map_update_elem (map_random_data_fd, &i, &val,BPF_ANY ); +if (!ASSERT_OK (err,"Add random value to map_random_data" )) +continue ; + + err =bpf_map_update_elem (inner_map_fd,NULL , &val,0 ); +if (!ASSERT_OK (err,"Add random value to inner_map_fd" )) + goto done; + } + + outer_map_fd =bpf_map__fd (skel->maps.outer_map); +/* Add the bloom filter map to the outer map */ + err =bpf_map_update_elem (outer_map_fd, &key, &inner_map_fd,0 ); +if (!ASSERT_OK (err,"Add bloom filter map to outer map" )) + goto done; + +/* Attach the bloom_filter_inner_map prog */ + link =bpf_program__attach (skel->progs.prog_bloom_filter_inner_map); +if (!ASSERT_OK_PTR (link,"link" )) + goto delete_inner_map; + +syscall (SYS_getpgid); + +ASSERT_EQ (skel->bss->error,0 ,"error" ); + +bpf_link__destroy (link); + +delete_inner_map: +/* Ensure the inner bloom filter map can be deleted */ + err =bpf_map_delete_elem (outer_map_fd, &key); +ASSERT_OK (err,"Delete inner bloom filter map" ); + +done: +close (inner_map_fd); +} + +void test_bloom_filter_map (void ) +{ +struct bloom_filter_map *skel; + +test_bloom_filter_map_fail (); + + skel =bloom_filter_map__open_and_load (); +if (!ASSERT_OK_PTR (skel,"bloom_filter_map__open_and_load" )) + goto cleanup; + +bloom_filter_map (skel); + +bloom_filter_inner_map (skel); + +cleanup: +bloom_filter_map__destroy (skel); +}
tools/testing/selftests/bpf/progs/bloom_filter_map.c new file +83 -0
83 lines not on this page · raw message
Signature · 1 line
2.30.2
PATCH v3 4/5 bpf/benchs: Add benchmark test for bloom filter maps
In reply to Joanne KoongThis 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%
--- 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 | 345 ++++++++++++++++++ .../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, 538 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
tools/testing/selftests/bpf/Makefile +3 -1
@@ -520,13 +520,15 @@ $(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 \ $(OUTPUT)/perfbuf_bench.skel.h +$(OUTPUT)/bench_bloom_filter_map.o: $(OUTPUT)/bloom_filter_map.skel.h $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm $(OUTPUT)/bench: $(OUTPUT)/bench.o $(OUTPUT)/testing_helpers.o \ $(OUTPUT)/bench_count.o \ $(OUTPUT)/bench_rename.o \ $(OUTPUT)/bench_trigger.o \ - $(OUTPUT)/bench_ringbufs.o + $(OUTPUT)/bench_ringbufs.o \ + $(OUTPUT)/bench_bloom_filter_map.o $(call msg,BINARY,,$@) $(Q)$(CC) $(LDFLAGS) -o $@ $(filter %.a %.o,$^) $(LDLIBS)
tools/testing/selftests/bpf/bench.c +35 -0
@@ -51,6 +51,35 @@ void setup_libbpf()fprintf (stderr,"failed to increase RLIMIT_MEMLOCK: %d" , err); } +void false_hits_report_progress (int iter,struct bench_res *res,long delta_ns) +{ +long total = res->false_hits + res->hits + res->drops; + +printf ("Iter %3d (%7.3lfus): " , + iter, (delta_ns -1000000000 ) /1000.0 ); + +printf ("%ld false hits of %ld total operations. Percentage = %2.2f %%\n" , + res->false_hits, total, ((float )res->false_hits / total) *100 ); +} + +void false_hits_report_final (struct bench_res res[],int res_cnt) +{ +long total_hits =0 , total_drops =0 , total_false_hits =0 , total_ops =0 ; +int i; + +for (i =0 ; i < res_cnt; i++) { + total_hits += res[i].hits; + total_false_hits += res[i].false_hits; + total_drops += res[i].drops; + } + total_ops = total_hits + total_false_hits + total_drops; + +printf ("Summary: %ld false hits of %ld total operations. " , + total_false_hits, total_ops); +printf ("Percentage = %2.2f %%\n" , + ((float )total_false_hits / total_ops) *100 ); +} +void hits_drops_report_progress (int iter,struct bench_res *res,long delta_ns) {double hits_per_sec, drops_per_sec;
@@ -132,9 +161,11 @@ static const struct argp_option opts[] = { };extern struct argp bench_ringbufs_argp; +extern struct argp bench_bloom_filter_map_argp;static const struct argp_child bench_parsers[] = { { &bench_ringbufs_argp,0 ,"Ring buffers benchmark" ,0 }, + { &bench_bloom_filter_map_argp,0 ,"Bloom filter map benchmark" ,0 }, {}, };
@@ -323,6 +354,8 @@ extern const struct bench bench_rb_libbpf;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_bloom_filter_false_positive;static const struct bench *benchs[] = { &bench_count_global,
@@ -344,6 +377,8 @@ static const struct bench *benchs[] = { &bench_rb_custom, &bench_pb_libbpf, &bench_pb_custom, + &bench_bloom_filter_map, + &bench_bloom_filter_false_positive, };static void setup_benchmark ()
tools/testing/selftests/bpf/bench.h +3 -0
@@ -33,6 +33,7 @@ struct env {struct bench_res {long hits;long drops; +long false_hits; };struct bench {
@@ -56,6 +57,8 @@ extern const struct bench *bench;void setup_libbpf ();void hits_drops_report_progress (int iter,struct bench_res *res,long delta_ns);void hits_drops_report_final (struct bench_res res[],int res_cnt); +void false_hits_report_progress (int iter,struct bench_res *res,long delta_ns); +void false_hits_report_final (struct bench_res res[],int res_cnt);static inline __u64 get_time_ns () {struct timespec t;
tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c new file +345 -0
345 lines not on this page · raw message
tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh new file +28 -0
@@ -0,0 +1,28 @@ +#!/bin/bash +# SPDX-License-Identifier: GPL-2.0 + +source ./benchs/run_common.sh + +set -eufo pipefail + +header "Bloom filter map" +for t in 1 4 8; do +for h in {1..10}; do +subtitle "# threads: $t, # hashes: $h" + for e in 10000 50000 75000 100000 250000 500000 750000 1000000 2500000 5000000; do + printf "%'d entries -\n" $e + printf "\t" + summarize "Total operations: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e bloom-filter-map)" + printf "\t" + summarize_percentage "False positive rate: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e 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
tools/testing/selftests/bpf/benchs/run_bench_ringbufs.sh +2 -28
@@ -1,34 +1,8 @@ #!/bin/bash -set -eufo pipefail - -RUN_BENCH="sudo ./bench -w3 -d10 -a" - -function hits() -{ - echo "$*" | sed -E "s/.*hits\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/" -} - -function drops() -{ - echo "$*" | sed -E "s/.*drops\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/" -} +source ./benchs/run_common.sh -function header() -{ - local len=${#1} - - printf "\n%s\n" "$1" - for i in $(seq 1 $len); do printf '='; done - printf '\n' -} - -function summarize() -{ - bench="$1" - summary=$(echo $2 | tail -n1) - printf "%-20s %s (drops %s)\n" "$bench" "$(hits $summary)" "$(drops $summary)" -} +set -eufo pipefail header "Single-producer, parallel producer" for b in rb-libbpf rb-custom pb-libbpf pb-custom; do
tools/testing/selftests/bpf/benchs/run_common.sh new file +48 -0
48 lines not on this page · raw message
tools/testing/selftests/bpf/progs/bloom_filter_map.c +74 -0
98 lines not on this page · raw message
Signature · 1 line
2.30.2
PATCH v3 5/5 bpf/benchs: Add benchmarks for comparing hashmap lookups with vs. without bloom filter
In reply to Joanne KoongThis patch adds benchmark tests for comparing the performance of hashmap lookups without the bloom filter vs. hashmap lookups with the bloom filter.
Checking the bloom filter first for whether the element exists should overall enable a higher throughput for hashmap lookups, since if the element does not exist in the bloom filter, we can avoid a costly lookup in the hashmap.
On average, using 5 hash functions in the bloom filter tended to perform the best across the widest range of different entry sizes. The benchmark results using 5 hash functions (running on 8 threads on a machine with one numa node, and taking the average of 3 runs) were roughly as follows:
value_size = 4 bytes -
10k entries: 30% faster 50k entries: 50% faster 100k entries: 55% faster 500k entres: 80% faster 1 million entries: 120% faster 5 million entries: 135% faster
value_size = 8 bytes -
10k entries: 35% faster 50k entries: 55% faster 100k entries: 70% faster 500k entres: 110% faster 1 million entries: 215% faster 5 million entries: 215% faster
value_size = 16 bytes -
10k entries: 5% slower 50k entries: 25% faster 100k entries: 35% faster 500k entres: 105% faster 1 million entries: 130% faster 5 million entries: 105% faster
value_size = 40 bytes -
10k entries: 5% slower 50k entries: 10% faster 100k entries: 20% faster 500k entres: 45% faster 1 million entries: 60% faster 5 million entries: 75% faster
--- tools/testing/selftests/bpf/bench.c | 22 ++++++++--- .../bpf/benchs/bench_bloom_filter_map.c | 39 +++++++++++++++++++ .../bpf/benchs/run_bench_bloom_filter_map.sh | 15 +++++++ .../selftests/bpf/benchs/run_common.sh | 12 ++++++ 4 files changed, 83 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/bench.c +17 -5
@@ -92,20 +92,21 @@ void hits_drops_report_progress(int iter, struct bench_res *res, long delta_ns)printf ("Iter %3d (%7.3lfus): " , iter, (delta_ns -1000000000 ) /1000.0 ); -printf ("hits %8.3lfM/s (%7.3lfM/prod), drops %8.3lfM/s\n" , - hits_per_sec, hits_per_prod, drops_per_sec); +printf ("hits %8.3lfM/s (%7.3lfM/prod), drops %8.3lfM/s, total operations %8.3lfM/s\n" , + hits_per_sec, hits_per_prod, drops_per_sec, hits_per_sec + drops_per_sec); }void hits_drops_report_final (struct bench_res res[],int res_cnt) {int i; -double hits_mean =0.0 , drops_mean =0.0 ; -double hits_stddev =0.0 , drops_stddev =0.0 ; +double hits_mean =0.0 , drops_mean =0.0 , total_ops_mean =0.0 ; +double hits_stddev =0.0 , drops_stddev =0.0 , total_ops_stddev =0.0 ;for (i =0 ; i < res_cnt; i++) { hits_mean += res[i].hits /1000000.0 / (0.0 + res_cnt); drops_mean += res[i].drops /1000000.0 / (0.0 + res_cnt); } + total_ops_mean = hits_mean + drops_mean;if (res_cnt >1 ) {for (i =0 ; i < res_cnt; i++) {
@@ -115,14 +116,21 @@ void hits_drops_report_final(struct bench_res res[], int res_cnt) drops_stddev += (drops_mean - res[i].drops /1000000.0 ) * (drops_mean - res[i].drops /1000000.0 ) / (res_cnt -1.0 ); + total_ops_stddev += (total_ops_mean - + (res[i].hits + res[i].drops) /1000000.0 ) * + (total_ops_mean - (res[i].hits + res[i].drops) /1000000.0 ) + / (res_cnt -1.0 ); } hits_stddev =sqrt (hits_stddev); drops_stddev =sqrt (drops_stddev); + total_ops_stddev =sqrt (total_ops_stddev); }printf ("Summary: hits %8.3lf \u00B1 %5.3lfM/s (%7.3lfM/prod), " , hits_mean, hits_stddev, hits_mean / env.producer_cnt); -printf ("drops %8.3lf \u00B1 %5.3lfM/s\n" , +printf ("drops %8.3lf \u00B1 %5.3lfM/s, " , drops_mean, drops_stddev); +printf ("total operations %8.3lf \u00B1 %5.3lfM/s\n" , + total_ops_mean, total_ops_stddev); }const char *argp_program_version ="benchmark" ;
@@ -356,6 +364,8 @@ 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_bloom_filter_false_positive; +extern const struct bench bench_hashmap_without_bloom_filter; +extern const struct bench bench_hashmap_with_bloom_filter;static const struct bench *benchs[] = { &bench_count_global,
@@ -379,6 +389,8 @@ static const struct bench *benchs[] = { &bench_pb_custom, &bench_bloom_filter_map, &bench_bloom_filter_false_positive, + &bench_hashmap_without_bloom_filter, + &bench_hashmap_with_bloom_filter, };static void setup_benchmark ()
tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c +39 -0
@@ -242,6 +242,23 @@ static void hashmap_lookup_setup(void) } } +static void hashmap_no_bloom_filter_setup (void ) +{ +struct bpf_link *link; + + ctx.skel =setup_skeleton (); + + ctx.skel->data->hashmap_use_bloom_filter = false; + +populate_maps (); + + link =bpf_program__attach (ctx.skel->progs.prog_bloom_filter_hashmap_lookup); +if (!link) { +fprintf (stderr,"failed to attach program!\n" ); +exit (1 ); + } +} +static void measure (struct bench_res *res) {long total_hits =0 , total_drops =0 , total_false_hits =0 ;
@@ -343,3 +360,25 @@ const struct bench bench_bloom_filter_false_positive = { .report_progress = false_hits_report_progress, .report_final = false_hits_report_final, }; + +const struct bench bench_hashmap_without_bloom_filter = { + .name ="hashmap-without-bloom-filter" , + .validate = validate, + .setup = hashmap_no_bloom_filter_setup, + .producer_thread = producer, + .consumer_thread = consumer, + .measure = measure, + .report_progress = hits_drops_report_progress, + .report_final = hits_drops_report_final, +}; + +const struct bench bench_hashmap_with_bloom_filter = { + .name ="hashmap-with-bloom-filter" , + .validate = validate, + .setup = hashmap_lookup_setup, + .producer_thread = producer, + .consumer_thread = consumer, + .measure = measure, + .report_progress = hits_drops_report_progress, + .report_final = hits_drops_report_final, +};
tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh +15 -0
@@ -26,3 +26,18 @@ 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 +subtitle "# hashes: $h" + for e in 10000 50000 75000 100000 250000 500000 750000 1000000 2500000 5000000; do + printf "%'d entries -\n" $e + printf "\t" + summarize_total "Hashmap without bloom filter: " \ + "$($RUN_BENCH --nr_hash_funcs $h --nr_entries $e -p 8 hashmap-without-bloom-filter)" + printf "\t" + summarize_total "Hashmap with bloom filter: " \ + "$($RUN_BENCH --nr_hash_funcs $h --nr_entries $e -p 8 hashmap-with-bloom-filter)" + done + printf "\n" +done
tools/testing/selftests/bpf/benchs/run_common.sh +12 -0
@@ -33,6 +33,11 @@ function percentage() echo "$*" | sed -E "s/.*Percentage\s=\s+([0-9]+\.[0-9]+).*/\1/" } +function total() +{ + echo "$*" | sed -E "s/.*total operations\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/" +} + function summarize() { bench="$1"
@@ -46,3 +51,10 @@ function summarize_percentage() summary=$(echo $2 | tail -n1) printf "%-20s %s%%\n" "$bench" "$(percentage $summary)" } + +function summarize_total() +{ + bench="$1" + summary=$(echo $2 | tail -n1) + printf "%-20s %s\n" "$bench" "$(total $summary)" +}
Signature · 1 line
2.30.2