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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <33e512c1-fc06-4ef9-b607-eff3c58a5d8d@linux.dev>
Date: Fri, 25 Apr 2025 16:50:06 -0700
From: Martin KaFai Lau <martin.lau@...ux.dev>
To: Alexei Starovoitov <alexei.starovoitov@...il.com>
Cc: bpf <bpf@...r.kernel.org>, Alexei Starovoitov <ast@...nel.org>,
 Andrii Nakryiko <andrii@...nel.org>, Daniel Borkmann <daniel@...earbox.net>,
 Network Development <netdev@...r.kernel.org>,
 Kernel Team <kernel-team@...a.com>, Amery Hung <ameryhung@...il.com>
Subject: Re: [RFC PATCH bpf-next 12/12] selftests/bpf: A bpf fq implementation
 similar to the kernel sch_fq

On 4/24/25 5:13 PM, Alexei Starovoitov wrote:
> On Fri, Apr 18, 2025 at 3:47 PM Martin KaFai Lau <martin.lau@...ux.dev> wrote:
>>
>> From: Martin KaFai Lau <martin.lau@...nel.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!