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

[Alexei Starovoitov <alexei.starovoitov@gmail.com>]

On Mon, Sep 27, 2021 at 05:36:00PM -0700, Andrii Nakryiko wrote:
> On Mon, Sep 27, 2021 at 4:51 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Mon, Sep 27, 2021 at 02:14:09PM -0700, Andrii Nakryiko wrote:
> > > On Mon, Sep 27, 2021 at 9:41 AM Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > >
> > > > On Fri, Sep 24, 2021 at 04:12:11PM -0700, Andrii Nakryiko wrote:
> > > > >
> > > > > That's not what I proposed. So let's say somewhere in the kernel we
> > > > > have this variable:
> > > > >
> > > > > static int bpf_bloom_exists = 1;
> > > > >
> > > > > Now, for bpf_map_lookup_elem() helper we pass data as key pointer. If
> > > > > all its hashed bits are set in Bloom filter (it "exists"), we return
> > > > > &bpf_bloom_exists. So it's not a NULL pointer.
> > > >
> > > > imo that's too much of a hack.
> > >
> > > too bad, because this feels pretty natural in BPF code:
> > >
> > > int my_key = 1234;
> > >
> > > if (bpf_map_lookup_elem(&my_bloom_filter, &my_key)) {
> > >     /* handle "maybe exists" */
> > > } else {
> > >     /* handle "definitely doesn't exist" */
> > > }
> >
> > I don't think it fits bitset map.
> > In the bitset the value is zero or one. It always exist.
> > If bloomfilter is not a special map and instead implemented on top of
> > generic bitset with a plain loop in a bpf program then
> > push -> bit_set
> > pop -> bit_clear
> > peek -> bit_test
> > would be a better fit for bitset map.
> >
> > bpf_map_pop_elem() and peek_elem() don't have 'flags' argument.
> > In most cases that would be a blocker,
> > but in this case we can add:
> > .arg3_type      = ARG_ANYTHING
> > and ignore it in case of stack/queue.
> > While bitset could use the flags as an additional seed into the hash.
> > So to do a bloomfilter the bpf prog would do:
> > for (i = 0; i < 5; i++)
> >    if (bpf_map_peek_elem(map, &value, conver_i_to_seed(i)))
> 
> I think I'm getting lost in the whole unified bitset + bloom filter
> design, tbh. In this case, why would you pass the seed to peek()? And
> what is value here? Is that the value (N bytes) or the bit index (4
> bytes?)? 

The full N byte value, of course.
The pure index has the same downsides as hashing helper:
- hard to make kernel and user space produce the same hash in all cases
- inability to dynamically change max_entries in a clean way

> I assumed that once we have a hashing helper and a bitset
> map, you'd use that and seed to calculate bit index. But now I'm
> confused about what this peek operation is doing. I'm sorry if I'm
> just slow.
> 
> Overall, I think I agree with Joanne that a separate dedicated Bloom
> filter map will have simpler and better usability. This bitset + bloom
> filter generalization seems to just create unnecessary confusion. I
> don't feel the need for bitset map even more than I didn't feel the
> need for Bloom filter, given it's even simpler data structure and is
> totally implementable on either global var array or
> BPF_MAP_TYPE_ARRAY, if map-in-map and dynamic sizing in mandatory.

Not really. For two reasons:
- inner array with N 8-byte elements is a slow workaround.
map_lookup is not inlined for inner arrays because max_entries will
be different.
- doing the same hash in user space and the kernel is hard.
For example, iproute2 is using socket(AF_ALG) to compute the same hash
(program tag) as the kernel.
Copy-paste of kernel jhash.h is not possible due to GPL,
but, as you pointed out, it's public domain, so user space would
need to search a public domain, reimplement jhash and then
make sure that it produces the same hash as the kernel.
All these trade offs point out the need for dedicated map type
(either generalized bitset or true bloomfilter) that does the hashing
and can change its size.