netdev - Re: [RFC Patch v6 1/5] bpf: Introduce rbtree map

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: <CAP01T77f74ppZbn=qrJvz6suvAGR-4rcryXN1J_AcEp8LHe8sg@mail.gmail.com>
Date:   Tue, 11 Oct 2022 20:49:03 +0530
From:   Kumar Kartikeya Dwivedi <memxor@...il.com>
To:     Cong Wang <xiyou.wangcong@...il.com>
Cc:     netdev@...r.kernel.org, yangpeihao@...u.edu.cn, toke@...hat.com,
        jhs@...atatu.com, jiri@...nulli.us, bpf@...r.kernel.org,
        sdf@...gle.com, Cong Wang <cong.wang@...edance.com>,
        davemarchevsky@...com
Subject: Re: [RFC Patch v6 1/5] bpf: Introduce rbtree map

On Wed, 5 Oct 2022 at 22:53, Cong Wang <xiyou.wangcong@...il.com> wrote:
>
> From: Cong Wang <cong.wang@...edance.com>
>
> Insert:
> bpf_map_update(&map, &key, &val, flag);
>
> Delete a specific key-val pair:
> bpf_map_delete_elem(&map, &key);
>
> Pop the minimum one:
> bpf_map_pop(&map, &val);
>
> Lookup:
> val = bpf_map_lookup_elem(&map, &key);
>
> Iterator:
> bpf_for_each_map_elem(&map, callback, key, val);
>
> Signed-off-by: Cong Wang <cong.wang@...edance.com>
> ---

Instead of a dedicated BPF map and using kptr inside the map value, we
should probably lift Dave's series [0] adding the rbtree, and allow
linking sk_buff ctx directly into it. It would require recognising the
rb_node in sk_buff (or __sk_buff shadow struct) as a valid bpf_rb_node
similar to those in user allocated types. Overall it would be a much
better approach IMO and avoid having different rbtree implementations.
We would probably follow a similar approach for xdp_frame as well.

It can also be a union of bpf_rb_node, bpf_list_node, etc. Since the
type can only be in only one collection at once it would allow it to
be linked into different types of structures without wasting any
space.

[0]: https://lore.kernel.org/bpf/20220830172759.4069786-1-davemarchevsky@fb.com