On Thu, Sep 23, 2021 at 1:30 PM Alexei Starovoitov
<alexei.starovoitov@xxxxxxxxx> wrote:
>
> On Thu, Sep 23, 2021 at 12:42:33PM -0700, Martin KaFai Lau wrote:
> >
> > How to move it forward from here? Is it a must to keep the
> > bloomfilter-like map in pure bpf only and we should stop
> > the current work?
> >
> > or it is useful to have the kernel bloom filter that provides
> > a get-and-go usage and a consistent experience for user in
> > map-in-map which is the primary use case here. I don't think
> > this is necessarily blocking the custom bpf map effort also.
>
> I think map based and helper based bloom filter implementations
> are far from equivalent. There are pros and cons to both.
> For example the helper style doesn't have a good way
> of query/populate from the user space. If it's a single element
I thought about the use from user-space. I'd consider two ways of
doing that. One more complicated but with better performance, another
simpler but less performant (but in this case less performant is
equivalent to in-kernel implementation performance, or still better):
1. Have identical hash function implementation in user-space. In this
case Jenkins hash. Then memory-map contents and use exactly the same
bloom filter code to set the bits (as I said, once you have hash, it's
just a glorified bitset). This has the downside that if there is even
a single bit difference between hash produced by kernel and
user-space, you are screwed. But can't beat the performance because no
syscall overhead.
2. Use BPF_PROG_RUN command to execute custom program that would set
one or multiple provided values in the hashset. Just like we argued
for BPF timers, BPF program can be a custom "API" that would avoid
having separate user-space logic. Pass one or many values through a
global variable/array, BPF_PROG_RUN program that would iterate values,
calculate hashes, set bits. It actually should be faster than doing
BPF_MAP_UPDATE_ELEM syscall for each value. Next proposal will be to
add batched update support, of course, so I won't claim victory for
the performance argument here. :)
But yes, it needs a bit more (but simple) code, than if the kernel
just provided a Bloom filter map out of the box.
> array the user space would be forced to allocate huge buffers
> just to read/write single huge value_size.
> With multi element array it's sort-of easier.
> mmap-ing the array could help too,
> but in either case the user space would need to copy-paste jhash,
> which is GPL, and that might be more than just inconvenience.
>From include/linux/jhash.h: "You can use this free for any purpose.
It's in the public domain".
> We can try siphash in the bpf helper and give it a flag to choose
I did bpf_jhash_mem() just to demonstrate the approach quickly. I
think in practice I'd go for a more generic implementation where one
of the parameters is enum that specifies which supported hash
algorithm is used. It's easier to extend that:
u64 bpf_hash_mem(const void *data, u32 sz, u32 seed, enum bpf_hash_algo algo);
enum bpf_hash_algo {
XOR = 0,
JENKINS = 1,
MURMUR3 = 2,
...
}
Note the XOR case. If we specify it as "xor u64 values, where the last
<8 bytes are zero extended", it will come useful below for your
proposal.
> between hash implementations. That helps, but doesn't completely
> makes them equivalent.
I don't claim that implementing and using a custom Bloom filter will
be easier to use in all situations. I think the best we can strive for
is making it not much harder, and I think in this case it is. Of
course we can come up with a bunch of situations where doing it with
pure BPF isn't possible to do equivalently (like map-in-map with
dynamically sized bit size, well, sorry, BPF verifier can't validate
stuff like that). Dedicated BPF map or helper (as a general case, not
just this one) will pretty much always going to be easier to use just
because it's a dedicated and tailored API.
>
> As far as map based bloom filter I think it can combine bitset
> and bloomfilter features into one. delete_elem from user space
> can be mapped into pop() to clear bits.
> Some special value of nr_hashes could mean that no hashing
> is applied and 4 or 8 byte key gets modulo of max_entries
> and treated as a bit index. Both bpf prog and user space will
> have uniform access into such bitset. With nr_hashes >= 1
> it will become a bloom filter.
> In that sense may be max_entries should be specified in bits
> and the map is called bitset. With nr_hashes >= 1 the kernel
> would accept key_size > 8 and convert it to bloom filter
> peek/pop/push. In other words
> nr_hash == 0 bit_idx == key for set/read/clear
> nr_hashes >= 1 bit_idx[1..N] = hash(key, N) for set/read/clear.
> If we could teach the verifier to inline the bit lookup
> we potentially can get rid of bloomfilter loop inside the peek().
> Then the map would be true bitset without bloomfilter quirks.
> Even in such case it's not equivalent to bpf_hash(mem_ptr, size, flags) helper.
> Thoughts?
Sounds a bit complicated from end-user's perspective, tbh, but bitset
map (with generalization for bloom filter) sounds a bit more widely
useful. See above for the bpf_hash_algo proposal. If we allow to
specify nr_hashes and hash algorithm, then with XOR as defined above
and nr_hash = 1, you'll get just bitset behavior with not extra
restrictions on key size: you could have 1, 2, 4, 8 and more bytes
(where with more bytes it's some suboptimal bloom filter with one hash
function, not sure why you'd do that).
The biggest quirk is defining that XOR hashes in chunks of 8 bytes
(with zero-extending anything that is not a multiple of 8 bytes
length). We can do special "only 1, 2, 4, and 8 bytes are supported",
of course, but it will be special-cased internally. Not sure which one
is cleaner.
While writing this, another thought was to have a "NOOP" (or
"IDENTITY") hash, where we say that we treat bytes as one huge number.
Obviously then we truncate to the actual bitmap size, which just
basically means "use up to lower 8 bytes as a number". But it sucks
for big-endian, because to make it sane we'd need to take last "up to
8 bytes", which obviously sounds convoluted. So I don't know, just a
thought.
If we do the map, though, regardless if it's bitset or bloom
specifically. Maybe we should consider modeling as actual
bpf_map_lookup_elem(), where the key is a pointer to whatever we are
hashing and looking up? It makes much more sense, that's how people
model sets based on maps: key is the element you are looking up, value
is either true/false or meaningless (at least for me it felt much more
natural that you are looking up by key, not by value). In this case,
what if on successful lookup we return a pointer to some fixed
u8/u32/u64 location in the kernel, some dedicated static variable
shared between all maps. So NULL means "element is not in a set",
non-NULL means it is in the set. Ideally we'd prevent such element to
be written to, but it might be too hard to do that as just one
exception here, don't know.
