On Thu, Sep 23, 2021 at 03:28:01PM -0700, Joanne Koong wrote: > > > 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. I like this bitset+nr_hash semantic, then max_entries logcially follows the number of bits. > > If we do the map, though, regardless if it's bitset or bloom > > specifically. Maybe we should consider modeling as actual > > bpf_map_lookup_elem(), where the key is a pointer to whatever we are > > hashing and looking up? It makes much more sense, that's how people > > model sets based on maps: key is the element you are looking up, value > > is either true/false or meaningless (at least for me it felt much more > > natural that you are looking up by key, not by value). In this case, > > what if on successful lookup we return a pointer to some fixed > > u8/u32/u64 location in the kernel, some dedicated static variable > > shared between all maps. So NULL means "element is not in a set", > > non-NULL means it is in the set. > I think this would then also require that the bpf_map_update_elem() API from > the userspace side would have to pass in a valid memory address for the > "value". I understand what you're saying though about it feeling more natural > that the "key" is the element here; I agree but there doesn't seem to be a > clean way of doing this - I think maybe one viable approach would be allowing > map_update_elem to pass in a NULL value in the kernel if the map is a non-associative map, > and refactoring the push_elem/peek_elem API so that the element can represent either the key or > the value. > > Ideally we'd prevent such element to > > be written to, but it might be too hard to do that as just one > > exception here, don't know. I don't mind key or value also. With nr_hash == 0 and key is the bit_idx, it may be more correct to say that bit is indeed 0/1 instead of returning the bit_idx back.
