On Fri, 1 Mar 2024 at 20:28, Amery Hung <ameryhung@xxxxxxxxx> wrote:
>
> On Fri, Mar 1, 2024 at 7:06 AM Kumar Kartikeya Dwivedi <memxor@xxxxxxxxx> wrote:
> >
> > On Fri, 1 Mar 2024 at 16:01, Amery Hung <ameryhung@xxxxxxxxx> wrote:
> > >
> > > On Fri, Mar 1, 2024 at 6:08 AM Toke Høiland-Jørgensen <toke@xxxxxxxxxx> wrote:
> > > >
> > > > Amery Hung <ameryhung@xxxxxxxxx> writes:
> > > >
> > > > > On Wed, Feb 28, 2024 at 6:36 AM Toke Høiland-Jørgensen <toke@xxxxxxxxxx> wrote:
> > > > >>
> > > > >> Kumar Kartikeya Dwivedi <memxor@xxxxxxxxx> writes:
> > > > >>
> > > > >> > On Mon, 26 Feb 2024 at 19:04, Amery Hung <ameryhung@xxxxxxxxx> wrote:
> > > > >> >>
> > > > >> >> Hi all,
> > > > >> >>
> > > > >> >> I would like to discuss bpf qdisc in the BPF track. As we now try to
> > > > >> >> support bpf qdisc using struct_ops, we found some limitations of
> > > > >> >> bpf/struct_ops. While some have been discussed briefly on the mailing
> > > > >> >> list, we can discuss in more detail to make struct_ops a more
> > > > >> >> generic/palatable approach to replace kernel functions.
> > > > >> >>
> > > > >> >> In addition, I would like to discuss supporting adding kernel objects
> > > > >> >> to bpf_list/rbtree, which may have performance benefits in some
> > > > >> >> applications and can improve the programming experience. The current
> > > > >> >> bpf fq in the RFC has a 6% throughput loss compared to the native
> > > > >> >> counterpart due to memory allocation in enqueue() to store skb kptr.
> > > > >> >> With a POC I wrote that allows adding skb to bpf_list, the throughput
> > > > >> >> becomes comparable. We can discuss the approach and other potential
> > > > >> >> use cases.
> > > > >> >>
> > > > >> >
> > > > >> > When discussing this with Toke (Cc'd) long ago for the XDP queueing
> > > > >> > patch set, we discussed the same thing, in that the sk_buff already
> > > > >> > has space for a list or rbnode due to it getting queued in other
> > > > >> > layers (TCP OoO queue, qdiscs, etc.) so it would make sense to teach
> > > > >> > the verifier that it is a valid bpf_list_node and bpf_rb_node and
> > > > >> > allow inserting it as an element into a BPF list or rbtree. Back then
> > > > >> > we didn't add that as the posting only used the PIFO map.
> > > > >> >
> > > > >> > I think not only sk_buff, you can do a similar thing with xdp_buff as
> > > > >> > well.
> > > > >>
> > > > >> Yeah, I agree that allowing skbs to be inserted directly into a BPF
> > > > >> rbtree would make a lot of sense if it can be done safely. I am less
> > > > >> sure about xdp_frames, mostly for performance reasons, but if it does
> > > > >> turn out to be useful whichever mechanism we add for skbs should be
> > > > >> fairly straight forward to reuse.
> > > > >>
> > > > >> > The verifier side changes should be fairly minimal, just allowing the
> > > > >> > use of a known kernel type as the contained object in a list or
> > > > >> > rbtree, and the field pointing to this allowlisted list or rbnode.
> > > > >>
> > > > >> I think one additional concern here is how we ensure that an skb has
> > > > >> been correctly removed from any rbtrees it sits in before it is being
> > > > >> transmitted to another part of the stack?
> > > > >
> > > > > I think one solution is to disallow shared ownership of skb in
> > > > > multiple lists or rbtrees. That is, users should not be able to
> > > > > acquire the reference of an skb from the ctx more than once in
> > > > > ".enqueue" or using bpf_refcount_acquire().
> > > >
> > > > Can the verifier enforce this, even across multiple enqueue/dequeue
> > > > calls? Not sure if acquiring a refcount ensures that the rbtree entry
> > > > has been cleared?
> > > >
> > > > Basically, I'm worried about a dequeue() op that does something like:
> > > >
> > > > skb = rbtree_head();
> > > > // skb->rbnode is not cleared
> > > > return skb; // stack will keep processing it
> > > >
> > > > I'm a little fuzzy on how the bpf rbtree stuff works, though, so maybe
> > > > the verifier is already ensuring that a node cannot be read from a tree
> > > > without being properly cleared from it?
> > > >
> > >
> > > I see what you are saying now, and thanks Kumar for the clarification!
> > >
> > > I was thinking about how to prevent an skb from being added to lists
> > > and rbtrees at the same time, since list and rbnode share the same
> > > space. Hence the suggestion.
> > >
> >
> > In BPF qdisc programs, you could teach the verifier that the skb has
> > reference semantics (ref_obj_id > 0),
> > in such a case once you push it into a list or rbtree, the program
> > will lose ownership of the skb and all pointers same as the skb will
> > be marked invalid.
> > You could use some peek helper to look at it, but will never have an
> > skb with program ownership until you pop it back from a list or
> > rbtree.
> >
>
> This part makes sense. In the enqueue() op of bpf qdisc, I use a kfunc
> to acquire an skb kptr (ref_obj_id > 0) from the skb in ctx for now.
> Martin suggested tracking reads from ctx and assigning ref_obj_id.
>
> However, either way, if users can do this multiple times in one
> enqueue() call like below, they can acquire multiple references to the
> same skb and put them on different lists/rbtrees. This is what I'd
> like to avoid.
>
> SEC("struct_ops/bpf_fifo_enqueue")
> int BPF_PROG(bpf_fifo_enqueue, struct sk_buff *skb, struct Qdisc *sch,
> struct bpf_sk_buff_ptr *to_free)
> {
> ...
> skb_kptr_a = bpf_skb_acquire(skb);
> skb_kptr_b = bpf_skb_acquire(skb);
Yeah, this acquire kfunc is the root cause. That basically is a sign
that 'multiple references are ok' even though that's not the case.
It would have been the least intrusive way to allow skb kptrs, but it
wouldn't work well to enforce unique ownership of the skb.
Instead of this, we could teach the verifier that a struct ops
argument can be an acquired pointer being passed as a parameter to the
BPF program.
Then, on entry into the program, it would have a reference state
created for it and the corresponding ref_obj_id be assigned to that
when loading it from ctx.
When the reference state goes away, loading it again from ctx will
just mark it as an unknown scalar or return an error.
Then, you can only push the skb into a list or rbtree once.
>
> bpf_list_push_back(&list_1, skb_kptr_a->bpf_list);
> bpf_list_push_back(&list_2, skb_kptr_b->bpf_list);
> ...
>
> Thanks,
> Amery
>
> > In the XDP queueing series, we taught the verifier to have reference
> > semantics for xdp_md in the dequeue program, and then return such a
> > pointer from the program back to the kernel.
> > The changes to allow PTR_TO_PACKET accesses were also fairly simple,
> > the verifier just needs to know that comparison of data, data_end can
> > only be done for pkt pointers coming from the same xdp_md (as there
> > can be multiple in the same program at a time).
