Re: [RFC PATCH bpf-next 05/11] bpf: Add bpf_spin_lock member to rbtree

[Alexei Starovoitov <alexei.starovoitov@gmail.com>]

On Wed, Aug 10, 2022 at 2:47 PM Kumar Kartikeya Dwivedi
<memxor@gmail.com> wrote:
>
> Just to continue brainstorming: Comments on this?
>
> Instead of a rbtree map, you have a struct bpf_rbtree global variable
> which works like a rbtree. To associate a lock with multiple
> bpf_rbtree, you do clang style thread safety annotation in the bpf
> program:
>
> #define __guarded_by(lock) __attribute__((btf_type_tag("guarded_by:" #lock))
>
> struct bpf_spin_lock shared_lock;
> struct bpf_rbtree rbtree1 __guarded_by(shared_lock);
> struct bpf_rbtree rbtree2 __guarded_by(shared_lock);
>
> guarded_by tag is mandatory for the rbtree. Verifier ensures
> shared_lock spin lock is held whenever rbtree1 or rbtree2 is being
> accessed, and whitelists add/remove helpers inside the critical
> section.

We've been discussing exactly btf_type_tag annotation
to associate rbtree with a lock :)
Thanks for bringing it up as well.
Great that we're aligned.

> I don't think associating locks to rbtree dynamically is a hard
> requirement for your use case? But if you need that, you may probably
> also allocate sets of rbtree that are part of the same lock "class"
> dynamically using bpf_kptr_alloc, and do similar annotation for the
> struct being allocated.
> struct rbtree_set {
>   struct bpf_spin_lock lock;
>   struct bpf_rbtree rbtree1 __guarded_by(lock);
>   struct bpf_rbtree rbtree2 __guarded_by(lock);
> };
> struct rbtree_set *s = bpf_kptr_alloc(sizeof(*s), btf_local_type_id(*s));
> // Just stash the pointer somewhere with kptr_xchg
> On bpf_kptr_free, the verifier knows this is not a "trivial" struct,
> so inserts destructor calls for bpf_rbtree fields during program
> fixup.
>
> The main insight is that lock and rbtree are part of the same
> allocation (map value for global case, ptr_to_btf_id for dynamic case)
> so the locked state can be bound to the reg state in the verifier.

It works nicely in the static case, but ffwd a bit.
We might need an rbtree of rbtrees.
Pretty much like map-in-map that we have today for hash tables.

And the rbtree_node might be a part of an rbtree while
being chained into a separate link list.

We need a lock to protect operations on both rbtree and link list.
Then we might need to create an rbtree dynamically for each cgroup.
And store a pointer to rb_root in cgroup local storage.
Maybe allocating a lock + rb_root + linklist_head as one
allocation will not be too restrictive.

> Then we can also make this new rbtree API use kfuncs instead of UAPI
> helpers, to get some field experience before baking it in.

+1 to that.

> Any opinions? Any brainos or deficiencies in the scheme above?

It would be great if we can do the lock checks statically.
Dynamic locks means that rbtree_add/erase and in the future
link list insert/remove might fail which is horrible from
programmer perspective.
We've been thinking about the "abort" concept for such cases.
When helpers detect an unsafe condition like correct lock is not
taken, they can abort execution of itself, the bpf program
and prevent the program from executing in the future.
Conceptually it sounds great and will solve all kinds of ugliness,
but it's not clear yet how to implement such abort mechanism
which would mean stack unwind and calling of destructors for kptr-s,
refcnt decrements for acquired objects like sockets, etc.