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

[Dave Marchevsky <davemarchevsky@meta.com>]

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.

  [0]: https://lore.kernel.org/bpf/20221025190033.bqjr7466o7pdd3wo@apollo/

> 
> bpf_list_pop_front and bpf_list_pop_back delete the first or last item
> of the list respectively, and return pointer to the element at the
> list_node offset. The user can then use container_of style macro to get
> the actual entry type. The verifier however statically knows the actual
> type, so the safety properties are still preserved.
> 
> With these additions, programs can now manage their own linked lists and
> store their objects in them.
> 
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> ---

[...]

will comment on rest of patch in separate msg