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

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

On Thu, Sep 02, 2021 at 03:07:56PM -0700, Joanne Koong wrote:
[ ... ]
> > > But one high-level point I wanted to discuss was that bloom filter
> > > logic is actually simple enough to be implementable by pure BPF
> > > program logic. The only problematic part is generic hashing of a piece
> > > of memory. Regardless of implementing bloom filter as kernel-provided
> > > BPF map or implementing it with custom BPF program logic, having BPF
> > > helper for hashing a piece of memory seems extremely useful and very
> > > generic. I can't recall if we ever discussed adding such helpers, but
> > > maybe we should?
> > Aha started typing the same thing :)
> > 
> > Adding generic hash helper has been on my todo list and close to the top
> > now. The use case is hashing data from skb payloads and such from kprobe
> > and sockmap side. I'm happy to work on it as soon as possible if no one
> > else picks it up.
> > 
> > > It would be a really interesting experiment to implement the same
> > > logic in pure BPF logic and run it as another benchmark, along the
> > > Bloom filter map. BPF has both spinlock and atomic operation, so we
> > > can compare and contrast. We only miss hashing BPF helper.
> > 
> > I've find small seemingly unrelated changes cause the complexity limit
> > to explode. Usually we can work around it with code to get pruning
> > points and such, but its a bit ugly. Perhaps this means we need
> > to dive into details of why the complexity explodes, but I've not
> > got to it yet. The todo list is long.
> > 
> > > Being able to do this in pure BPF code has a bunch of advantages.
> > > Depending on specific application, users can decide to:
> > >    - speed up the operation by ditching spinlock or atomic operation,
> > > if the logic allows to lose some bit updates;
> > >    - decide on optimal size, which might not be a power of 2, depending
> > > on memory vs CPU trade of in any particular case;
> > >    - it's also possible to implement a more general Counting Bloom
> > > filter, all without modifying the kernel.
> > Also it means no call and if you build it on top of an array
> > map of size 1 its just a load. Could this be a performance win for
> > example a Bloom filter in XDP for DDOS? Maybe. Not sure if the program
> > would be complex enough a call might be in the noise. I don't know.
> > 
> > > We could go further, and start implementing other simple data
> > > structures relying on hashing, like HyperLogLog. And all with no
> > > kernel modifications. Map-in-map is no issue as well, because there is
> > > a choice of using either fixed global data arrays for maximum
> > > performance, or using BPF_MAP_TYPE_ARRAY maps that can go inside
> > > map-in-map.
> > We've been doing most of our array maps as single entry arrays
> > at this point and just calculating offsets directly in BPF. Same
> > for some simple hashing algorithms.
> > 
> > > Basically, regardless of having this map in the kernel or not, let's
> > > have a "universal" hashing function as a BPF helper as well.
> > > Thoughts?
> > I like it, but not the bloom filter expert here.
> 
> Ooh, I like your idea of comparing the performance of the bloom filter with
> a kernel-provided BPF map vs. custom BPF program logic using a
> hash helper, especially if a BPF hash helper is something useful that
> we want to add to the codebase in and of itself!
I think a hash helper will be useful in general but could it be a
separate experiment to try using it to implement some bpf maps (probably
a mix of an easy one and a little harder one) ?