On Fri, Sep 24, 2021 at 04:12:11PM -0700, Andrii Nakryiko wrote:

quoted

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:

quoted

quoted

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.

quoted

quoted

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.