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

[Alexei Starovoitov <alexei.starovoitov@gmail.com>]

On Thu, Sep 23, 2021 at 12:42:33PM -0700, Martin KaFai Lau wrote:
> 
> 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?