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?
