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

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

On Wed, Sep 22, 2021 at 6:28 PM Martin KaFai Lau <kafai@fb.com> wrote:
>
> On Wed, Sep 22, 2021 at 04:07:52PM -0700, Andrii Nakryiko wrote:
> > > > Please see my RFC ([0]). I don't think there is much to coordinate. It
> > > > could be purely BPF-side code, or BPF + user-space initialization
> > > > code, depending on the need. It's a simple and beautiful algorithm,
> > > > which BPF is powerful enough to implement customly and easily.
> > > >
> > > >   [0] https://lore.kernel.org/bpf/20210922203224.912809-1-andrii@kernel.org/T/#t
> > > In practice, the bloom filter will be populated only once by the userspace.
> > >
> > > The future update will be done by map-in-map to replace the whole bloom filter.
> > > May be with more max_entries with more nr_hashes.  May be fewer
> > > max_entries with fewer nr_hashes.
> > >
> > > Currently, the continuous running bpf prog using this bloom filter does
> > > not need to worry about any change in the newer bloom filter
> > > configure/setup.
> > >
> > > I wonder how that may look like in the custom bpf bloom filter in the
> > > bench prog for the map-in-map usage.
> >
> > You'd have to use BPF_MAP_TYPE_ARRAY for the map-in-map use case.
> Right, another map is needed.  When the user space generates
> a new bloom filter as inner map, it is likely that it has different
> number of entries, so the map size is different.
>
> The old and new inner array map need to at least have the same value_size,
> so an one element array with different value_size will not work.
>
> The inner array map with BPF_F_INNER_MAP can have different max_entries
> but then there is no inline code lookup generation.  It may not be too
> bad to call it multiple times to lookup a value considering the
> array_map_lookup_elem will still be directly called without retpoline.

All true, of course, due to generic BPF limitations. In practice, I'd
decide what's the maximum size of the bloom filter I'd need and use
that as an inner map definition. If I understand correctly, there is
going to be only one "active" Bloom filter map and it's generally not
that big (few megabytes covers tons of "max_entries"), so I'd just
work with maximum expected size.

If I absolutely needed variable-sized filters, I'd consider doing a
multi-element array as you suggested, but I'd expect lower
performance, as you mentioned.

> The next part is how to learn those "const volatile __u32 bloom_*;"
> values of the new inner map.  I think the max_entires can be obtained
> by map_ptr->max_entries.   Other vars (e.g. hash_cnt and seed) can
> be used as non-const global, allow the update, and a brief moment of
> inconsistence may be fine.

For single-element array with fixed value_size I'd put those in first 8 bytes:

struct my_bloom {
    __u32 msk;
    __u32 seed;
    __u64 data[];
}

For multi-element BPF_MAP_TYPE_ARRAY I'd put a mask and seed into elem[0].

I'd expect that hash_cnt would be just hard-coded, because as I
mentioned before, it determines the probability of false positive,
which is what end-users probably care about the most and set upfront,
at least they should be coming at this from the perspective "1% of
false positives is acceptable" rather than "hmm... 3 hash functions is
probably acceptable", no? But if not, first two elements would be
taken.

>
> It all sounds doable but all these small need-to-pay-attention
> things add up.

Of course, there is always a tension between "make it simple and
provide a dedicated BPF helper/BPF map" and "let users implement it on
their own". I'm saying I'm not convinced that it has to be the former
in this case. Bloom filter is just a glorified bit set, once you have
a hashing helper. I don't think we've added BPF_MAP_TYPE_BITSET yet,
though it probably would be pretty useful in some cases, just like the
Bloom filter. Similarly, we don't have BPF_MAP_TYPE_HASHSET in
addition to BPF_MAP_TYPE_HASHMAP. I've seen many cases where HASHMAP
is used as HASHSET, yet we didn't have a dedicated map for that
either. I'm just curious where we draw the line between what should be
added to the kernel for BPF, if there are reasonable ways to avoid
that.