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

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

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.