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

[Andrii Nakryiko <andrii.nakryiko@gmail.com>]

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?)? 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.

But given we are converging on having a new map, maybe let's do just a
Bloom filter map with the tweaks we discussed in this thread for
map_extra and max_entries?

>
> Probably would still be an improvement to add:
> static inline long bpf_bit_test(void *map, void *value, long flags)
> {
>     return bpf_map_peek_elem(map, value, flags);
> }
> to some header file.
>
> Or maybe bloomfilter and the loop can be a flavor of bitset map and
> done inside the helper to spare bpf programmers doing the manual loops.
> Or such loop could be another static inline function in a header file?