On Tue, Nov 19, 2024 at 4:22 AM Matt Bobrowski <mattbobrowski@xxxxxxxxxx> wrote: > > Hi, > > Currently, we have BPF kfuncs which allow BPF programs to add and > remove elements from a BPF linked list. However, we're currently > missing other simple capabilities, like being able to iterate over the > elements within the BPF linked lists. What is our current appetite > with regards to adding new BPF kfuncs that support this kind of > capability to BPF linked lists? What kind of kfuncs do you have in mind for link lists ? So far the only user of bpf_rbtree is sched-ext. It was used in one scheduler and the experience was painful. There is a chance that we will remove rbtree and link list support from the verifier to reduce complexity. So new link list kfuncs may be ok, but potentially not for too long. > I know that we're now somewhat advocating for using BPF arenas > whenever and wherever possible, especially when it comes to building > out and supporting more complicated data structures in BPF. However, > IMO BPF linked lists still have their place. Specifically, and as of > now, I'd argue that the BPF linked list implementation could be > considered more memory efficient when compared to a BPF arena backed > linked list implementation. This is purely due to the fact that the > BPF linked list implementation can perform more constrained memory > allocations for elements via bpf_obj_new_impl() based on the demand, > whereas for a BPF arena based implementation a BPF program needs to > allocate memory upfront in terms of the number of pages (modulo the > fact that not all pages for the BPF arena will necessarily be reserved > upfront). The fact that allocations are performed in terms of > multiples of PAGE_SIZE can lead to unnecessary memory wastage. I don't follow this logic. bpf_mem_alloc is relying on slab that relies on page alloc. So either arena or bpf_ma allocates a page at a time. So from that pov the cost is the same. But in practice bpf_ma needs extra 8 bytes for every allocation whereas arena allocs don't have this overhead. Right now arena allocs need to be sleepable and that is a severe limitation for tracing use cases. We're working on lifting that. Once that happens allocs in arena will be more usable than bpf_ma. kptr-s in arena is another required feature. There were few proposals. So it will be done as well. Eventually. So new link list kfuncs are ok, but might get removed in the future.
