Generic Data Structure Iterators

Generic Data Structure Iterators

[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
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

Re: Generic Data Structure Iterators

[Song Liu]

On Mon, Feb 12, 2024 at 12:48 PM Matt Bobrowski
<mattbobrowski@google.com> wrote:
>
[...]
>
> 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

Re: Generic Data Structure Iterators

[Alexei Starovoitov]

On Mon, Feb 12, 2024 at 12:48 PM Matt Bobrowski
<mattbobrowski@google.com> wrote:
>
> 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?

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/20240209040608.98927-19-alexei.starovoitov@gmail.com/
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.

Re: Generic Data Structure Iterators

[Kumar Kartikeya Dwivedi]

On Mon, 12 Feb 2024 at 21:48, Matt Bobrowski <mattbobrowski@google.com> wrote:
>
> [...]
>
> 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.

> /M
>