Skip to contentSkip to conversation

Implement bloom filter map

PATCH Superseded Joanne Koong 4 participants 37 messages Sep 21, 2021 – Sep 29, 2021 1 message not in the archive

Subsystems (5)
Kselftest BPF BPF selftests BPF core +1 more subsystems

v3 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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 -> peek
BPF_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
index 9c81724e4b98..c4424ac2fa02 100644
@@ -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
index 6fc59d61937a..fec9fcfe0629 100644
@@ -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
index 7f33098ca63f..cf6ca339f3cd 100644
@@ -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
index 4e50c0bfdb7d..9865b5b1e667 100644
@@ -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
index e76b55917905..fd2b7f9dccae 100644
@@ -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
index 6fc59d61937a..fec9fcfe0629 100644
@@ -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
#2 lore raw

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 -> peek
BPF_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.

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,
+};

[...]

#3 lore raw

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 -> peek
BPF_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(-)
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_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.

[...]

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 line

Quoted 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,
+};

[...]

#4 lore raw

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 -> peek
BPF_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(-)
Quoted 2 lines

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.

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.

#5 lore raw

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 -> peek
BPF_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(-)
Quoted 2 lines

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.

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.

#6 lore raw

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_entries values 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.

[0] https://lore.kernel.org/bpf/[email protected]/T/#t

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.

#7 lore raw

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_entries values 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.

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.

[0] https://lore.kernel.org/bpf/[email protected]/T/#t

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.

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.

#8 lore raw

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.

[0] https://lore.kernel.org/bpf/[email protected]/T/#t

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.

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_ARRAY for 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.

#9 lore raw

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.

[0] https://lore.kernel.org/bpf/[email protected]/T/#t

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.

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_ARRAY for 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 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.

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 __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.

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.

#10 lore raw

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.

[0] https://lore.kernel.org/bpf/[email protected]/T/#t

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.

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_ARRAY for 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 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.

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 __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.

For single-element array with fixed value_size I'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_ARRAY I'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_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.

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_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.

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.

#11 lore raw

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 words
nr_hash == 0 bit_idx == key for set/read/clear
nr_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?

#12 lore raw

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_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

Quoted 8 lines

peek/pop/push. In other words
nr_hash == 0 bit_idx == key for set/read/clear
nr_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?

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.

#13 lore raw

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_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.

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_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

Quoted 8 lines
Quoted 8 lines

peek/pop/push. In other words
nr_hash == 0 bit_idx == key for set/read/clear
nr_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?

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_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.

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.

#14 lore raw

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_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

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 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 words
nr_hash == 0 bit_idx == key for set/read/clear nr_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 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.

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.

#15 lore raw

Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation

In reply to Joanne Koong
Quoted 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_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.

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_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

Quoted 8 lines
Quoted 8 lines

peek/pop/push. In other words
nr_hash == 0 bit_idx == key for set/read/clear
nr_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?

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 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.

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_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.

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 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.

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.

#16 lore raw

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_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.

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_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

Quoted 8 lines
Quoted 8 lines

peek/pop/push. In other words
nr_hash == 0 bit_idx == key for set/read/clear
nr_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?

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 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.

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_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.

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 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 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_elem which 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_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.

Quoted 5 lines

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.

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!

#17 lore raw

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_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

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_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

Quoted 8 lines
Quoted 8 lines

peek/pop/push. In other words
nr_hash == 0 bit_idx == key for set/read/clear
nr_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?

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 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.

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_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.

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 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 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_elem which 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).

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_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.

Quoted 5 lines

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.

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
* Change nr_hashes to a more generic "u32 map_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 confusion

Thanks for the discussion on this, Martin, Andrii, and Alexei!

#18 lore raw

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 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.

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.

#19 lore raw

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 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.

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.h could have static inline functions:
bool bpf_bitset_clear(map, key);
bool bpf_bitset_set(map, key);
bool bpf_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 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 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_size to 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_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.

#20 lore raw

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?

#21 lore raw

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() 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)))

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 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?

#22 lore raw

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() 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)))

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]

#24 lore raw

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 or value_size = 4 bytes in a worst-case scenario

For #1 where the value_size is 0 and we return something like &bpf_bloom_exists
for bpf_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 allow value_sizes of
0. This would require another change in bpf_map_copy_value where we have to also check that if the value_size is 0, then we shouldn't copy the resulting ptr
of the bpf_map_lookup_elem call to the value ptr (the value ptr isn't allocated since
value_size is 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 allow bpf_map_update_elem for 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 the value_size is no longer 0. This seems like a hacky API

Repurposing peek/push/pop (in the scenario where value_size = 0) would avoid the
bpf_map_copy_value change 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() 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)))
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 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.

Quoted 14 lines

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.

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 if nr_hashes > 0 (where nr_hashes is denoted through the map_extra flags). max_entries will be the requested size of the bitset. Key_size should 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
bool bpf_bitset_clear(map, value);
bool bpf_bitset_set(map, value);
bool bpf_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_size for 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.

#25 lore raw

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 or value_size = 4 bytes in a worst-case scenario

For #1 where the value_size is 0 and we return something like &bpf_bloom_exists
for bpf_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 allow value_sizes of
0. This would require another change in bpf_map_copy_value where we have to also check that if the value_size is 0, then we shouldn't copy the resulting ptr
of the bpf_map_lookup_elem call to the value ptr (the value ptr isn't allocated since
value_size is 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 allow bpf_map_update_elem for 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 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.

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 the value_size is no longer 0. This seems like a hacky API

Repurposing peek/push/pop (in the scenario where value_size = 0) would avoid the
bpf_map_copy_value change 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() 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)))
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 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.

Quoted 14 lines

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.

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 if nr_hashes > 0 (where nr_hashes is denoted through the map_extra flags). max_entries will be the requested size of the bitset. Key_size should always be 0.

Quoted 5 lines

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.

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
bool bpf_bitset_clear(map, value);
bool bpf_bitset_set(map, value);
bool bpf_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 :) ).

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_size for the bitmap should always be a u32. This denotes which index of the bitmap to set/check/clear

SGTM.

Quoted 4 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.

#26 lore raw

Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation

In reply to Alexei Starovoitov
Quoted 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() 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)))

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 change max_entries in 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_lookup is not inlined for inner arrays because max_entries will 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 kernel jhash.h is 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.

#27 lore raw

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.

#28 lore raw

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.

#29 lore raw

Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation

In reply to Andrii Nakryiko
Quoted 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 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.

I would prefer the earlier definition on nr_hashes:

Quoted 1 line
Quoted 1 line
Quoted 1 line

nr_hash == 0 bit_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.

#30 lore raw

Re: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation

In reply to Joanne Koong
Quoted 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 -> peek
BPF_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(-)
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_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.

[...]

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,
+};

[...]

#31 lore raw

PATCH v3 2/5 libbpf: Allow the number of hashes in bloom filter maps to be configurable

In reply to 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.

---
 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
index fec9fcfe0629..2e3048488feb 100644
@@ -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
index fec9fcfe0629..2e3048488feb 100644
@@ -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
index 2401fad090c5..8a9dd4f6d6c8 100644
@@ -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
index 6fffb3cdf39b..1194b6f01572 100644
@@ -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
index da65a1666a5e..e51e68a07aaf 100644
@@ -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 *def
 		pr_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
index d0bedd673273..5c441744f766 100644
@@ -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
index 9e649cf9e771..ee0e1e7648f4 100644
@@ -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
index ceb0c98979bc..95dbbeba231f 100644
@@ -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
#32 lore raw

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.

---
  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
index fec9fcfe0629..2e3048488feb 100644
@@ -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
index fec9fcfe0629..2e3048488feb 100644
@@ -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
index 2401fad090c5..8a9dd4f6d6c8 100644
@@ -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
index 6fffb3cdf39b..1194b6f01572 100644
@@ -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
index da65a1666a5e..e51e68a07aaf 100644
@@ -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 *def
  		pr_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
index d0bedd673273..5c441744f766 100644
@@ -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
index 9e649cf9e771..ee0e1e7648f4 100644
@@ -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
index ceb0c98979bc..95dbbeba231f 100644
@@ -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 -0
  int parse_btf_map_def(const char *map_name, struct btf *btf,
#33 lore raw

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.

---
  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_def is 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 uses bpf_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 -0
  int parse_btf_map_def(const char *map_name, struct btf *btf,
#34 lore raw

Re: [PATCH v3 bpf-next 2/5] libbpf: Allow the number of hashes in bloom filter maps to be configurable

In reply to Joanne Koong
Quoted 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.

---
 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
index fec9fcfe0629..2e3048488feb 100644
@@ -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
index fec9fcfe0629..2e3048488feb 100644
@@ -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
index 2401fad090c5..8a9dd4f6d6c8 100644
@@ -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
index 6fffb3cdf39b..1194b6f01572 100644
@@ -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
index da65a1666a5e..e51e68a07aaf 100644

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
index d0bedd673273..5c441744f766 100644

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 -0
 typedef void (*bpf_map_clear_priv_t)(struct bpf_map *, void *);
 LIBBPF_API int bpf_map__set_priv(struct bpf_map *map, void *priv,

[...]

#35 lore raw

PATCH v3 3/5 selftests/bpf: Add bloom filter map test cases

In reply to Joanne Koong

This 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
new file mode 100644
index 000000000000..134705d74a66
@@ -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
#36 lore raw

PATCH v3 4/5 bpf/benchs: Add benchmark test for bloom filter maps

In reply to Joanne Koong

This 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
index 326ea75ce99e..5dbaf7f512fd 100644
@@ -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
index 6ea15b93a2f8..0bcbdb4405a3 100644
@@ -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
index c1f48a473b02..624c6b11501f 100644
@@ -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
new file mode 100755
index 000000000000..0dbbd85937e3
@@ -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
index af4aa04caba6..ada028aa9007 100755
@@ -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
#37 lore raw

PATCH v3 5/5 bpf/benchs: Add benchmarks for comparing hashmap lookups with vs. without bloom filter

In reply to Joanne Koong

This 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
index 0bcbdb4405a3..7da1589a9fe0 100644
@@ -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
index 8b4cd9a52a88..7adf80be7292 100644
@@ -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
index 0dbbd85937e3..239c040b7aaa 100755
@@ -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
index 670f23b037c4..9a16be78b180 100644
@@ -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