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