Re: [PATCH bpf-next v4 1/5] bpf: Add bitset map with bloom filter capabilities

[Joanne Koong <joannekoong@fb.com>]

On 10/12/21 5:48 AM, Toke Høiland-Jørgensen wrote:

> Andrii Nakryiko <andrii.nakryiko@gmail.com> writes:
>
>>> The 'find first set' operation is a single instruction on common
>>> architectures, so it's an efficient way of finding the first non-empty
>>> bucket if you index them in a bitmap; sch_qfq uses this, for instance.
>> There is also extremely useful popcnt() instruction, would be great to
>> have that as well. There is also fls() (find largest set bit), it is
>> used extensively throughout the kernel. If we'd like to take this ad
>> absurdum, there are a lot of useful operations defined in
>> include/linux/bitops.h and include/linux/bitmap.h, I'm pretty sure one
>> can come up with a use case for every one of those.
>>
>> The question is whether we should bloat the kernel with such
>> helpers/operations?
> I agree, all of those are interesting bitwise operations that would be
> useful to expose to BPF. But if we're not going to "bloat the kernel"
> with them, what should we do? Introduce new BPF instructions?
>
>> I'd love to hear specific arguments in favor of dedicated BITSET,
>> though.
> Mainly the above; given the right instructions, I totally buy your
> assertion that one can build a bitmap using regular BPF arrays...
>
> -Toke
I have the same opinion as Toke here - the most compelling reason I
see for the bitset map to be supported by the kernel is so we can
support a wider set of bit operations that wouldn't be available
strictly through bpf.

I'm also open to adding the bloom filter map and then in the
future, if/when there is a need for the bitset map, adding that as a
separate map. In that case, we could have the bitset map take in
both key and value where key = the bitset index and value = 0 or 1.