netdev - Re: [RFC PATCH bpf-next 03/12] bpf: Add bpf_rbtree

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: <CAP01T76vnejd27gaxW1oNiEhT96Yp0j1JEs8iXb13UW6ep5XJQ@mail.gmail.com>
Date: Tue, 22 Apr 2025 03:43:50 +0200
From: Kumar Kartikeya Dwivedi <memxor@...il.com>
To: Martin KaFai Lau <martin.lau@...ux.dev>
Cc: bpf@...r.kernel.org, Alexei Starovoitov <ast@...nel.org>, 
	Andrii Nakryiko <andrii@...nel.org>, Daniel Borkmann <daniel@...earbox.net>, netdev@...r.kernel.org, 
	kernel-team@...a.com, Amery Hung <ameryhung@...il.com>
Subject: Re: [RFC PATCH bpf-next 03/12] bpf: Add bpf_rbtree_{root,left,right} kfunc

On Sat, 19 Apr 2025 at 00:47, Martin KaFai Lau <martin.lau@...ux.dev> wrote:
>
> From: Martin KaFai Lau <martin.lau@...nel.org>
>
> In the kernel fq qdisc implementation, it requires to traverse a rbtree
> stored with the networking "flows".
>
> In the later bpf selftests prog, the much simplified logic that uses
> the bpf_rbtree_{root,left,right} to traverse the tree is like:
>
> struct fq_flow {
>         struct bpf_rb_node      fq_node;
>         struct bpf_rb_node      rate_node;
>         struct bpf_refcount     refcount;
>         unsigned long           sk_long;
> };
>
> struct fq_flow_root {
>         struct bpf_spin_lock lock;
>         struct bpf_rb_root root __contains(fq_flow, fq_node);
> };
>
> struct fq_flow *fq_classify(...)
> {
>         struct bpf_rb_node *tofree[FQ_GC_MAX];
>         struct fq_flow_root *root;
>         struct fq_flow *gc_f, *f;
>         struct bpf_rb_node *p;
>         int i, fcnt = 0;
>
>         /* ... */
>
>         f = NULL;
>         bpf_spin_lock(&root->lock);
>         p = bpf_rbtree_root(&root->root);
>         while (can_loop) {
>                 if (!p)
>                         break;
>
>                 gc_f = bpf_rb_entry(p, struct fq_flow, fq_node);
>                 if (gc_f->sk_long == sk_long) {
>                         f = bpf_refcount_acquire(gc_f);
>                         break;
>                 }
>
>                 /* To be removed from the rbtree */
>                 if (fcnt < FQ_GC_MAX && fq_gc_candidate(gc_f, jiffies_now))
>                         tofree[fcnt++] = p;
>
>                 if (gc_f->sk_long > sk_long)
>                         p = bpf_rbtree_left(&root->root, p);
>                 else
>                         p = bpf_rbtree_right(&root->root, p);
>         }
>
>         /* remove from the rbtree */
>         for (i = 0; i < fcnt; i++) {
>                 p = tofree[i];
>                 tofree[i] = bpf_rbtree_remove(&root->root, p);
>         }
>
>         bpf_spin_unlock(&root->lock);
>
>         /* bpf_obj_drop the fq_flow(s) that have just been removed
>          * from the rbtree.
>          */
>         for (i = 0; i < fcnt; i++) {
>                 p = tofree[i];
>                 if (p) {
>                         gc_f = bpf_rb_entry(p, struct fq_flow, fq_node);
>                         bpf_obj_drop(gc_f);
>                 }
>         }
>
>         return f;
>
> }
>
> The above simplified code needs to traverse the rbtree for two purposes,
> 1) find the flow with the desired sk_long value
> 2) while searching for the sk_long, collect flows that are
>    the fq_gc_candidate. They will be removed from the rbtree.
>
> This patch adds the bpf_rbtree_{root,left,right} kfunc to enable
> the rbtree traversal. The returned bpf_rb_node pointer will be a
> non-owning reference which is the same as the returned pointer
> of the exisiting bpf_rbtree_first kfunc.
>
> Signed-off-by: Martin KaFai Lau <martin.lau@...nel.org>
> ---

Acked-by: Kumar Kartikeya Dwivedi <memxor@...il.com>