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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <CAADnVQJTfUyxkZTZHgL8yqwu7VU2Ssbao8B_sw6Q16wJ1hVK7A@mail.gmail.com>
Date: Thu, 24 Apr 2025 17:13:45 -0700
From: Alexei Starovoitov <alexei.starovoitov@...il.com>
To: Martin KaFai Lau <martin.lau@...ux.dev>
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 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

> bpf_spin_lock(&root->lock);

have you considered "if (bpf_res_spin_lock(&root->lock))" ?
It can also protect rbtree and lists,
and allows arbitrary calls inside, so the algorithm
might be easier to implement?