Re: [RFC PATCH bpf-next 12/12] selftests/bpf: A bpf fq implementation similar to the kernel sch_fq

[Martin KaFai Lau <martin.lau@linux.dev>]

On 4/24/25 5:13 PM, Alexei Starovoitov wrote:
> On Fri, Apr 18, 2025 at 3:47 PM Martin KaFai Lau <martin.lau@linux.dev> wrote:
>>
>> From: Martin KaFai Lau <martin.lau@kernel.org>
>>
>> This patch adds a fuller fq qdisc implementation that is comparable
>> to the kernel fq implementation. The code is mostly borrowed
>> from the sch_fq.c before the WRR addition. The WRR should be
>> doable as a followup.
>>
>> Some highlights:
>> * The current struct_ops does not support the qdisc_priv() concept.
>>    qdisc_priv() is the additional private data allocated by the
>>    qdisc subsystem at the end of a struct_ops object.
>>
>>    The patch is using a map-in-map approach to do the qdisc_priv.
>>    The outer map is an arraymap. When a qdisc instance starts,
>>    it grabs an available index (idx) in the ".init" ops.
>>    This idx will be the key to lookup the outer arraymap.
>>
>>    The inner map will then serve as the qdisc_priv which is
>>    the 'struct fq_sched_data'
>>
>> * Each qdisc instance has a hash table of rbtrees. This patch
>>    also uses map-in-map to do this. The outer arraymap's key is the
>>    qdisc "idx". The inner map is the array of bpf_rb_root.
>>
>> * With bpf_rbtree_{root,left,right} and bpf_list_{front,back},
>>    the fq_classify/enqueue/dequeue should be more recognizable when
>>    comparing with the sch_fq.c. Like, searching the flow and doing gc.
>>
>> * Most of the code deviation from sch_fq.c is because of
>>    the lock requirement and the refcount requirement.
> 
> This is a very impressive bpf prog.
> Quite amazing what qdisc-bpf can do.
> 
> Few questions:
> 
>> bpf_probe_read_kernel(&sk_long
> 
> Will the following work ?
> *bpf_core_cast(skb->sk, long)
> 
> or if verifier needs struct type (I don't recall)
> struct long_wrap {
>    long l;
> };
> bpf_core_cast(skb->sk, struct long_wrap)->l

Ah. I didn't think about bpf_core_cast.

As you suspected, adding "struct long_wrap" to the kernel works.

The verifier enforces the bpf_rdonly_cast return type must be a pointer to a 
struct. Thus, a plain "long" pointer won't work. btf_struct_access() will need 
some changes to support long pointer. I haven't checked other places yet.

> 
>> bpf_spin_lock(&root->lock);
> 
> have you considered "if (bpf_res_spin_lock(&root->lock))" ?

No but mostly because I started this set a little earlier, so it was not in my 
mind. Thanks for the suggestion.

> It can also protect rbtree and lists,
> and allows arbitrary calls inside, so the algorithm
> might be easier to implement?

Yes, it will make the implementation easier. e.g. it can call bpf_obj_{drop,new} 
without releasing the lock. It is a huge plus. I will use the res_spin_lock in 
the next revision.

Thanks for the review!