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.
