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

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

On Fri, Sep 24, 2021 at 04:12:11PM -0700, Andrii Nakryiko wrote:
> > 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:

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

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