On 9/2/21 5:56 PM, Martin KaFai Lau wrote:
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.
After thinking through this some more, I'm curious to hear your thoughts,
Andrii and John, on how the bitmap would be allocated. From what I
understand, we do not currently support dynamic memory allocations
in bpf programs. Assuming the optimal number of bits the user wants
to use for their bitmap follows something like
num_entries * num_hash_functions / ln(2), I think the bitmap would
have to be dynamically allocated in the bpf program since it'd be too
large to store on the stack, unless there's some other way I'm not seeing?
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.
The one issue I've found writing a hash logic is its a bit tricky
to get the verifier to consume it. Especially when the hash is nested
inside a for loop and sometimes a couple for loops so you end up with
things like,
for (i = 0; i < someTlvs; i++) {
for (j = 0; j < someKeys; i++) {
...
bpf_hash(someValue)
...
}
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.
Out of curiosity, why would this helper have trouble in the verifier?
From a quick glance, it seems like the implementation for it would
be pretty similar to how bpf_get_prandom_u32() is implemented
(except where the arguments for the hash helper would take in a
void* data (ARG_PTR_TO_MEM), the size of the data buffer, and
the seed)? I'm a bit new to bpf, so there's a good chance I might be
completely overlooking something here :)
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) ?
I agree, I think the hash helper implementation should be its own separate
patchset orthogonal to this one.
