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