On 8/31/21 7:55 PM, Alexei Starovoitov wrote:
On Tue, Aug 31, 2021 at 03:50:01PM -0700, Joanne Koong wrote:
+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, hash;
+
+ for (i = 0; i < bloom_filter->map.nr_hashes; i++) {
+ hash = jhash(value, map->value_size, bloom_filter->hash_seed + i) &
+ bloom_filter->bit_array_mask;
+ if (!test_bit(hash, bloom_filter->bit_array))
+ return -ENOENT;
+ }
I'm curious what bloom filter theory says about n-hashes > 1
concurrent access with updates in terms of false negative?
Two concurrent updates race is protected by spin_lock,
but what about peek and update?
The update might set one bit, but not the other.
That shouldn't trigger false negative lookup, right?
For cases where there is a concurrent peek and update, the user is
responsible for
synchronizing these operations if they want to ensure that the peek will
always return
true while the update is occurring.
I will add this to the commit message.
Is bloom filter supported as inner map?
Hash and lru maps are often used as inner maps.
The lookups from them would be pre-filtered by bloom filter
map that would have to be (in some cases) inner map.
I suspect one bloom filter for all inner maps might be
reasonable workaround in some cases too.
The delete is not supported in bloom filter, of course.
Would be good to mention it in the commit log.
Since there is no delete the users would likely need
to replace the whole bloom filter. So map-in-map would
become necessary.
Do you think 'clear-all' operation might be useful for bloom filter?
It feels that if map-in-map is supported then clear-all is probably
not that useful, since atomic replacement and delete of the map
would work better. 'clear-all' will have issues with
lookup, since it cannot be done in parallel.
Would be good to document all these ideas and restrictions.
The bloom filter is supported as an inner map. I will include a test for
this and add it to v2
(and document this in the commit message in v2)
Could you collect 'perf annotate' data for the above performance
critical loop?
I wonder whether using jhash2 and forcing u32 value size could speed it up.
Probably not, but would be good to check, since restricting value_size
later would be problematic due to backward compatibility.
The recommended nr_hashes=3 was computed with value_size=8, right?
I wonder whether nr_hashes would be different for value_size=16 and =4
which are ipv6/ipv4 addresses and value_size = 40
an approximation of networking n-tuple.
Great suggestions! I will do all of these you mentioned, after I
incorporate the edits for v2,
and report back with the results.
+static struct bpf_map *bloom_filter_map_alloc(union bpf_attr *attr)
+{
+ int numa_node = bpf_map_attr_numa_node(attr);
+ u32 nr_bits, bit_array_bytes, bit_array_mask;
+ struct bpf_bloom_filter *bloom_filter;
+
+ if (!bpf_capable())
+ return ERR_PTR(-EPERM);
+
+ if (attr->key_size != 0 || attr->value_size == 0 || attr->max_entries == 0 ||
+ attr->nr_hashes == 0 || attr->map_flags & ~BLOOM_FILTER_CREATE_FLAG_MASK ||
Would it make sense to default to nr_hashes=3 if zero is passed?
This way the libbpf changes for nr_hashes will become 'optional'.
Most users wouldn't have to specify it explicitly.
I like this idea - it'll make the API more friendly to use as well for
people who
might not be acquainted with bloom filters :)
Overall looks great!
Performance numbers are impressive.
