bpf: Add bpf_rbtree_{add,remove,first} kfuncs
authorDave Marchevsky <davemarchevsky@fb.com>
Tue, 14 Feb 2023 00:40:11 +0000 (16:40 -0800)
committerAlexei Starovoitov <ast@kernel.org>
Tue, 14 Feb 2023 03:40:48 +0000 (19:40 -0800)
commitbd1279ae8a691d7ec75852c6d0a22139afb034a4
tree85ff3f66c5e5a3e8e47a719328e08bdc7f3c6940
parent9c395c1b99bd23f74bc628fa000480c49593d17f
bpf: Add bpf_rbtree_{add,remove,first} kfuncs

This patch adds implementations of bpf_rbtree_{add,remove,first}
and teaches verifier about their BTF_IDs as well as those of
bpf_rb_{root,node}.

All three kfuncs have some nonstandard component to their verification
that needs to be addressed in future patches before programs can
properly use them:

  * bpf_rbtree_add:     Takes 'less' callback, need to verify it

  * bpf_rbtree_first:   Returns ptr_to_node_type(off=rb_node_off) instead
                        of ptr_to_rb_node(off=0). Return value ref is
non-owning.

  * bpf_rbtree_remove:  Returns ptr_to_node_type(off=rb_node_off) instead
                        of ptr_to_rb_node(off=0). 2nd arg (node) is a
non-owning reference.

Signed-off-by: Dave Marchevsky <davemarchevsky@fb.com>
Link: https://lore.kernel.org/r/20230214004017.2534011-3-davemarchevsky@fb.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
kernel/bpf/helpers.c
kernel/bpf/verifier.c