Generic Data Structure Iterators
In numerous BPF programs, I've found myself needing to iterate over some in-kernel generic data structure i.e. list_head, hlist_head, rbtree, etc. The approach that I generally use to do this consists of using bpf_loop(), container_of(), and BPF_CORE_READ(). The end result of this approach is always rather messy as it's mostly implementation specific and bound to a specific in-kernel type i.e. mount, dentry, inode, etc.
Recently, I came across the newly added bpf_for_each() open-coded iterator, which could possibly help out a little with trivially performing such iterations within BPF programs. However, looking into the usage of this helper a little more, I realized that this too needs to be backed by the new kfunc iterator framework
i.e. bpf_iter_##type##_new(), bpf_iter_##type##_destroy(), bpf_iter_##type##_next(). So, in practice it seems like adopting this approach to solve this specific iterator problem would lead us into a situation where we'd be having to define iterator kfuncs for each in-kernel type and respective field.
Now having said this, I'm wondering whether anyone here has considered possibly solving this iterator based problem a little more generically? That is, by exposing a set of kfuncs that allow you to iterate over a list_head, hlist_head, rbtree, etc, independent of an underlying in-kernel type and similar to your *list_for_each*() based helpers that you'd typically find for each of these in-kernel generic data structures. If so, what were your findings when exploring this problem space?
/M
Song Liu
reviewerQuoted 1 line · Matt Bobrowski
[...]
Quoted 9 lines
Now having said this, I'm wondering whether anyone here has considered possibly solving this iterator based problem a little more generically? That is, by exposing a set of kfuncs that allow you to iterate over a
list_head,hlist_head, rbtree, etc, independent of an underlying in-kernel type and similar to your *list_for_each*() based helpers that you'd typically find for each of these in-kernel generic data structures. If so, what were your findings when exploring this problem space?
Here are my 2 cents on this:
BPF iterators are designed to be really safe. So it is necessary to handle locking/refcounting accurately in the helpers. AFAICT, it is hard to do something universal, like list_for_each(), and still be safe.
If we can accept failures (user space core dump, etc.), we can use kcore based solutions, such as crash and drgn.
Thanks,
Song
Quoted 20 lines · Matt Bobrowski
In numerous BPF programs, I've found myself needing to iterate over some in-kernel generic data structure i.e.
list_head,hlist_head, rbtree, etc. The approach that I generally use to do this consists of usingbpf_loop(),container_of(), andBPF_CORE_READ(). The end result of this approach is always rather messy as it's mostly implementation specific and bound to a specific in-kernel type i.e. mount, dentry, inode, etc.Recently, I came across the newly added
bpf_for_each()open-coded iterator, which could possibly help out a little with trivially performing such iterations within BPF programs. However, looking into the usage of this helper a little more, I realized that this too needs to be backed by the new kfunc iterator framework
i.e. bpf_iter_##type##_new(), bpf_iter_##type##_destroy(), bpf_iter_##type##_next(). So, in practice it seems like adopting this approach to solve this specific iterator problem would lead us into a situation where we'd be having to define iterator kfuncs for each in-kernel type and respective field.
Quoted 8 lines
Now having said this, I'm wondering whether anyone here has considered possibly solving this iterator based problem a little more generically? That is, by exposing a set of kfuncs that allow you to iterate over a
list_head,hlist_head, rbtree, etc, independent of an underlying in-kernel type and similar to your *list_for_each*() based helpers that you'd typically find for each of these in-kernel generic data structures. If so, what were your findings when exploring this problem space?
If you're looking for read-only (aka untrusted_ptr_to_btf_id) access you can iterate link lists and everything else already without modifying the kernel.
See list_for_each_entry() that is arena specific:
https://lore.kernel.org/bpf/[email protected]/
Same thing can be done today (no need to wait for arena)
to walk kernel link lists.
typeof and container_of would need to change to use bpf_core_cast. Then all pointers are untrusted and JIT-ed like inlined probe_read_kernel.
Kumar Kartikeya Dwivedi
maintainerQuoted 12 lines · Matt Bobrowski
[...]
Now having said this, I'm wondering whether anyone here has considered possibly solving this iterator based problem a little more generically? That is, by exposing a set of kfuncs that allow you to iterate over a
list_head,hlist_head, rbtree, etc, independent of an underlying in-kernel type and similar to your *list_for_each*() based helpers that you'd typically find for each of these in-kernel generic data structures. If so, what were your findings when exploring this problem space?
I think I agree with Song that it might be unavoidable to introduce separate kfuncs to iterate over separate types (due to locking/RCU requirements, and other minor reasons in how the iterator is supposed to be initialized).
I think you can use some C11 tricks to make this convenient when writing programs though.
It's a bit like how iterators work in C++ (the real implementation is behind the class methods begin, end, operator++), and a templated function could dispatch to the right ones by monomorphization on call with different types.
In C, you could use _Generic to dispatch to the right kfunc based on the type of the struct on the stack.
The only downside is that you need to keep updating the macro with each new iterator.
Here is a godbolt link demonstrating the idea of a range-for loop like in C++, copied out and simplified from a BPF program I have which is not public yet.
https://godbolt.org/z/TWjP636Pv
The idea that Alexei linked to (using a number iterator with high 1M limit to iterate over in-kernel untrusted/rdonly ptr_to_btf_id) can also be accommodated into this.
Quoted 2 lines
/M