selftests/bpf: Add rbtree selftests
authorDave Marchevsky <davemarchevsky@fb.com>
Tue, 14 Feb 2023 00:40:16 +0000 (16:40 -0800)
committerAlexei Starovoitov <ast@kernel.org>
Tue, 14 Feb 2023 03:40:53 +0000 (19:40 -0800)
commit215249f6adc0359e3546829e7ee622b5e309b0ad
tree300b11a30ed51090ee2d0f05841567556ff2e4d4
parentc834df847ee60eeb678171eb0f1e59f611c62a99
selftests/bpf: Add rbtree selftests

This patch adds selftests exercising the logic changed/added in the
previous patches in the series. A variety of successful and unsuccessful
rbtree usages are validated:

Success:
  * Add some nodes, let map_value bpf_rbtree_root destructor clean them
    up
  * Add some nodes, remove one using the non-owning ref leftover by
    successful rbtree_add() call
  * Add some nodes, remove one using the non-owning ref returned by
    rbtree_first() call

Failure:
  * BTF where bpf_rb_root owns bpf_list_node should fail to load
  * BTF where node of type X is added to tree containing nodes of type Y
    should fail to load
  * No calling rbtree api functions in 'less' callback for rbtree_add
  * No releasing lock in 'less' callback for rbtree_add
  * No removing a node which hasn't been added to any tree
  * No adding a node which has already been added to a tree
  * No escaping of non-owning references past their lock's
    critical section
  * No escaping of non-owning references past other invalidation points
    (rbtree_remove)

These tests mostly focus on rbtree-specific additions, but some of the
failure cases revalidate scenarios common to both linked_list and rbtree
which are covered in the former's tests. Better to be a bit redundant in
case linked_list and rbtree semantics deviate over time.

Signed-off-by: Dave Marchevsky <davemarchevsky@fb.com>
Link: https://lore.kernel.org/r/20230214004017.2534011-8-davemarchevsky@fb.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
tools/testing/selftests/bpf/prog_tests/rbtree.c [new file with mode: 0644]
tools/testing/selftests/bpf/progs/rbtree.c [new file with mode: 0644]
tools/testing/selftests/bpf/progs/rbtree_btf_fail__add_wrong_type.c [new file with mode: 0644]
tools/testing/selftests/bpf/progs/rbtree_btf_fail__wrong_node_type.c [new file with mode: 0644]
tools/testing/selftests/bpf/progs/rbtree_fail.c [new file with mode: 0644]