Re: [PATCH bpf-next v4 22/24] bpf: Introduce single ownership BPF linked list API

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

On Fri, Nov 04, 2022 at 11:26:39AM IST, Dave Marchevsky wrote:
> On 11/3/22 3:10 PM, Kumar Kartikeya Dwivedi wrote:
> > Add a linked list API for use in BPF programs, where it expects
> > protection from the bpf_spin_lock in the same allocation as the
> > bpf_list_head. Future patches will extend the same infrastructure to
> > have different flavors with varying protection domains and visibility
> > (e.g. percpu variant with local_t protection, usable in NMI progs).
> >
> > The following functions are added to kick things off:
> >
> > bpf_list_push_front
> > bpf_list_push_back
> > bpf_list_pop_front
> > bpf_list_pop_back
> >
> > The lock protecting the bpf_list_head needs to be taken for all
> > operations.
> >
> > Once a node has been added to the list, it's pointer changes to
> > PTR_UNTRUSTED. However, it is only released once the lock protecting the
> > list is unlocked. For such local kptrs with PTR_UNTRUSTED set but an
> > active ref_obj_id, it is still permitted to read and write to them as
> > long as the lock is held.
>
> I think "still permitted to ... write to them" is not accurate
> for this version of the series. In v2 you mentioned [0]:
>
> """
> I have switched things a bit to disallow stores, which is a bug right now in
> this set, because one can do this:
>
> push_front(head, &p->node);
> p2 = container_of(pop_front(head));
> // p2 == p
> bpf_obj_drop(p2);
> p->data = ...;
>
> One can always fully initialize the object _before_ inserting it into the list,
> in some cases that will be the requirement (like adding to RCU protected lists)
> for correctness.
> """
>
> I confirmed this is currently the case by moving data write after
> list_push in the selftest and running it:
>
> @@ -87,8 +87,8 @@ static __always_inline int list_push_pop(struct bpf_spin_lock *lock,
>         }
>
>         bpf_spin_lock(lock);
> -       f->data = 13;
>         bpf_list_push_front(head, &f->node);
> +       f->data = 13;
>         bpf_spin_unlock(lock);
>
> Got "only read is supported" from verifier.
> I think it's fine to punt on supporting writes for now and do it in followups.
>

Thanks for catching it, I'll fix up the commit message.

Also, just to manage the expectations I think enabling writes after pushing the
object won't be possible to make safe, unless the definition of "safe" is
twisted.

As shown in that example, we can reach a point where it has been freed but we
hold an untrusted pointer to it. Once it has been freed the object can be
reallocated and be in use again concurrently, possibly as a different type.

I was contemplating whether to simply drop this whole set_release_on_unlock
logic entirely. Not sure it's worth the added complexity, atleast for now. Once
you push you simply lose ownership of the object and any registers are
immediately killed.