Re: [PATCH v6 bpf-next 0/5] Implement bloom filter map

[Martin KaFai Lau <kafai@fb.com>]

On Wed, Oct 27, 2021 at 04:44:59PM -0700, Joanne Koong wrote:
> 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.
> 
> A high level overview of this patchset is as follows:
> 1/5 - kernel changes for adding bloom filter map
> 2/5 - libbpf changes for adding map_extra flags
> 3/5 - tests for the bloom filter map
> 4/5 - benchmarks for bloom filter lookup/update throughput and false positive
> rate
> 5/5 - benchmarks for how hashmap lookups perform with vs. without the bloom
> filter
> 
> v5 -> v6:
> * in 1/5: remove "inline" from the hash function, add check in syscall to
> fail out in cases where map_extra is not 0 for non-bloom-filter maps,
> fix alignment matching issues, move "map_extra flags" comments to inside
> the bpf_attr struct, add bpf_map_info map_extra changes here, add map_extra
> assignment in bpf_map_get_info_by_fd, change hash value_size to u32 instead of
> a u64
> * in 2/5: remove bpf_map_info map_extra changes, remove TODO comment about
> extending BTF arrays to cover u64s, cast to unsigned long long for %llx when
> printing out map_extra flags
> * in 3/5: use __type(value, ...) instead of __uint(value_size, ...) for values
> and keys
> * in 4/5: fix wrong bounds for the index when iterating through random values,
> update commit message to include update+lookup benchmark results for 8 byte
> and 64-byte value sizes, remove explicit global bool initializaton to false
> for hashmap_use_bloom and count_false_hits variables
Thanks!  Only have minor comments in patch 1.  belated
Acked-by: Martin KaFai Lau <kafai@fb.com>