On 10/12/21 4:25 PM, Zvi Effron wrote:
On Tue, Oct 12, 2021 at 3:47 PM Joanne Koong <joannekoong@xxxxxx> wrote:
On 10/12/21 5:48 AM, Toke Høiland-Jørgensen wrote:
Andrii Nakryiko <andrii.nakryiko@xxxxxxxxx> 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.
Do we need a new map type to support those extra bit operations?
If we're not implementing them as helpers (or instructions), then I don't see
how the new map type helps bring those operations to eBPF.
If we are implementing them as helpers, do we need a new map type to do that?
Can't we make helpers that operate on data instead of a map?
I'm presuming the bitset data would reside in the ARRAY map (to cover
map-in-map use cases, and to bypass verifier out-of-bounds issues
that would (or might, not 100% sure) arise from indexing into a global
array).
I think the cleanest way then to support a large amount of special case
bit operations would be to have one bpf helper function which takes in a
map and a "flags" where "flags" indicates which type of special-case bit
operation to do. We could, if we wanted to, use the ARRAY map for this,
but to me it seems cleaner and safer to have the map be a separate BITSET
map where we can make guarantees about the map (eg bitset size can be
enforced to reject out of bounds indices)
If the bitset data could reside in a global array in the bpf program, then I
agree - it seems like we could just make a helper function that takes in
an ARG_PTR_TO_MEM where we pass the data in as a ptr, instead of needing
a map.
A map feels like a pretty heavy-weight way to expose these operations to me. It
requires user-space to create the map just so eBPF programs can use the
operations. This feels, to me, like it mixes the "persistent storage"
capability of maps with the bit operations goal being discussed. Making helpers
that operate on data would allow persistent storage in a map if that's where
the data lives, but also using the operations on non-persistent data if
desired.
--Zvi
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.
