On Thu, Nov 17, 2022 at 5:57 PM Kumar Kartikeya Dwivedi
<memxor@xxxxxxxxx> wrote:
>
> Include various tests covering the success and failure cases. Also, run
> the success cases at runtime to verify correctness of linked list
> manipulation routines, in addition to ensuring successful verification.
>
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@xxxxxxxxx>
> ---
> tools/testing/selftests/bpf/DENYLIST.aarch64 | 1 +
> tools/testing/selftests/bpf/DENYLIST.s390x | 1 +
> .../selftests/bpf/prog_tests/linked_list.c | 255 ++++++++
> .../testing/selftests/bpf/progs/linked_list.c | 370 +++++++++++
> .../testing/selftests/bpf/progs/linked_list.h | 56 ++
> .../selftests/bpf/progs/linked_list_fail.c | 581 ++++++++++++++++++
> 6 files changed, 1264 insertions(+)
> create mode 100644 tools/testing/selftests/bpf/prog_tests/linked_list.c
> create mode 100644 tools/testing/selftests/bpf/progs/linked_list.c
> create mode 100644 tools/testing/selftests/bpf/progs/linked_list.h
> create mode 100644 tools/testing/selftests/bpf/progs/linked_list_fail.c
>
> diff --git a/tools/testing/selftests/bpf/DENYLIST.aarch64 b/tools/testing/selftests/bpf/DENYLIST.aarch64
> index 09416d5d2e33..affc5aebbf0f 100644
> --- a/tools/testing/selftests/bpf/DENYLIST.aarch64
> +++ b/tools/testing/selftests/bpf/DENYLIST.aarch64
> @@ -38,6 +38,7 @@ kprobe_multi_test/skel_api # kprobe_multi__attach unexpect
> ksyms_module/libbpf # 'bpf_testmod_ksym_percpu': not found in kernel BTF
> ksyms_module/lskel # test_ksyms_module_lskel__open_and_load unexpected error: -2
> libbpf_get_fd_by_id_opts # test_libbpf_get_fd_by_id_opts__attach unexpected error: -524 (errno 524)
> +linked_list
> lookup_key # test_lookup_key__attach unexpected error: -524 (errno 524)
> lru_bug # lru_bug__attach unexpected error: -524 (errno 524)
> modify_return # modify_return__attach failed unexpected error: -524 (errno 524)
> diff --git a/tools/testing/selftests/bpf/DENYLIST.s390x b/tools/testing/selftests/bpf/DENYLIST.s390x
> index be4e3d47ea3e..072243af93b0 100644
> --- a/tools/testing/selftests/bpf/DENYLIST.s390x
> +++ b/tools/testing/selftests/bpf/DENYLIST.s390x
> @@ -33,6 +33,7 @@ ksyms_module # test_ksyms_module__open_and_load unex
> ksyms_module_libbpf # JIT does not support calling kernel function (kfunc)
> ksyms_module_lskel # test_ksyms_module_lskel__open_and_load unexpected error: -9 (?)
> libbpf_get_fd_by_id_opts # failed to attach: ERROR: strerror_r(-524)=22 (trampoline)
> +linked_list # JIT does not support calling kernel function (kfunc)
> lookup_key # JIT does not support calling kernel function (kfunc)
> lru_bug # prog 'printk': failed to auto-attach: -524
> map_kptr # failed to open_and_load program: -524 (trampoline)
> diff --git a/tools/testing/selftests/bpf/prog_tests/linked_list.c b/tools/testing/selftests/bpf/prog_tests/linked_list.c
> new file mode 100644
> index 000000000000..41e588807321
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/linked_list.c
> @@ -0,0 +1,255 @@
> +// SPDX-License-Identifier: GPL-2.0
> +#include <test_progs.h>
> +#include <network_helpers.h>
> +
> +#include "linked_list.skel.h"
> +#include "linked_list_fail.skel.h"
> +
> +static char log_buf[1024 * 1024];
> +
> +static struct {
> + const char *prog_name;
> + const char *err_msg;
> +} linked_list_fail_tests[] = {
> +#define TEST(test, off) \
> + { #test "_missing_lock_push_front", \
> + "bpf_spin_lock at off=" #off " must be held for bpf_list_head" }, \
> + { #test "_missing_lock_push_back", \
> + "bpf_spin_lock at off=" #off " must be held for bpf_list_head" }, \
> + { #test "_missing_lock_pop_front", \
> + "bpf_spin_lock at off=" #off " must be held for bpf_list_head" }, \
> + { #test "_missing_lock_pop_back", \
> + "bpf_spin_lock at off=" #off " must be held for bpf_list_head" },
> + TEST(kptr, 32)
> + TEST(global, 16)
> + TEST(map, 0)
> + TEST(inner_map, 0)
> +#undef TEST
> +#define TEST(test, op) \
> + { #test "_kptr_incorrect_lock_" #op, \
> + "held lock and object are not in the same allocation\n" \
> + "bpf_spin_lock at off=32 must be held for bpf_list_head" }, \
> + { #test "_global_incorrect_lock_" #op, \
> + "held lock and object are not in the same allocation\n" \
> + "bpf_spin_lock at off=16 must be held for bpf_list_head" }, \
> + { #test "_map_incorrect_lock_" #op, \
> + "held lock and object are not in the same allocation\n" \
> + "bpf_spin_lock at off=0 must be held for bpf_list_head" }, \
> + { #test "_inner_map_incorrect_lock_" #op, \
> + "held lock and object are not in the same allocation\n" \
> + "bpf_spin_lock at off=0 must be held for bpf_list_head" },
> + TEST(kptr, push_front)
> + TEST(kptr, push_back)
> + TEST(kptr, pop_front)
> + TEST(kptr, pop_back)
> + TEST(global, push_front)
> + TEST(global, push_back)
> + TEST(global, pop_front)
> + TEST(global, pop_back)
> + TEST(map, push_front)
> + TEST(map, push_back)
> + TEST(map, pop_front)
> + TEST(map, pop_back)
> + TEST(inner_map, push_front)
> + TEST(inner_map, push_back)
> + TEST(inner_map, pop_front)
> + TEST(inner_map, pop_back)
> +#undef TEST
> + { "map_compat_kprobe", "tracing progs cannot use bpf_list_head yet" },
> + { "map_compat_kretprobe", "tracing progs cannot use bpf_list_head yet" },
> + { "map_compat_tp", "tracing progs cannot use bpf_list_head yet" },
> + { "map_compat_perf", "tracing progs cannot use bpf_list_head yet" },
> + { "map_compat_raw_tp", "tracing progs cannot use bpf_list_head yet" },
> + { "map_compat_raw_tp_w", "tracing progs cannot use bpf_list_head yet" },
> + { "obj_type_id_oor", "local type ID argument must be in range [0, U32_MAX]" },
> + { "obj_new_no_composite", "bpf_obj_new type ID argument must be of a struct" },
> + { "obj_new_no_struct", "bpf_obj_new type ID argument must be of a struct" },
> + { "obj_drop_non_zero_off", "R1 must have zero offset when passed to release func" },
> + { "new_null_ret", "R0 invalid mem access 'ptr_or_null_'" },
> + { "obj_new_acq", "Unreleased reference id=" },
> + { "use_after_drop", "invalid mem access 'scalar'" },
> + { "ptr_walk_scalar", "type=scalar expected=percpu_ptr_" },
> + { "direct_read_lock", "direct access to bpf_spin_lock is disallowed" },
> + { "direct_write_lock", "direct access to bpf_spin_lock is disallowed" },
> + { "direct_read_head", "direct access to bpf_list_head is disallowed" },
> + { "direct_write_head", "direct access to bpf_list_head is disallowed" },
> + { "direct_read_node", "direct access to bpf_list_node is disallowed" },
> + { "direct_write_node", "direct access to bpf_list_node is disallowed" },
> + { "write_after_push_front", "only read is supported" },
> + { "write_after_push_back", "only read is supported" },
> + { "use_after_unlock_push_front", "invalid mem access 'scalar'" },
> + { "use_after_unlock_push_back", "invalid mem access 'scalar'" },
> + { "double_push_front", "arg#1 expected pointer to allocated object" },
> + { "double_push_back", "arg#1 expected pointer to allocated object" },
> + { "no_node_value_type", "bpf_list_node not found at offset=0" },
> + { "incorrect_value_type",
> + "operation on bpf_list_head expects arg#1 bpf_list_node at offset=0 in struct foo, "
> + "but arg is at offset=0 in struct bar" },
> + { "incorrect_node_var_off", "variable ptr_ access var_off=(0x0; 0xffffffff) disallowed" },
> + { "incorrect_node_off1", "bpf_list_node not found at offset=1" },
> + { "incorrect_node_off2", "arg#1 offset=40, but expected bpf_list_node at offset=0 in struct foo" },
> + { "no_head_type", "bpf_list_head not found at offset=0" },
> + { "incorrect_head_var_off1", "R1 doesn't have constant offset" },
> + { "incorrect_head_var_off2", "variable ptr_ access var_off=(0x0; 0xffffffff) disallowed" },
> + { "incorrect_head_off1", "bpf_list_head not found at offset=17" },
> + { "incorrect_head_off2", "bpf_list_head not found at offset=1" },
> + { "pop_front_off",
> + "15: (bf) r1 = r6 ; R1_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=40,imm=0) "
> + "R6_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=40,imm=0) refs=2,4\n"
> + "16: (85) call bpf_this_cpu_ptr#154\nR1 type=ptr_or_null_ expected=percpu_ptr_" },
> + { "pop_back_off",
> + "15: (bf) r1 = r6 ; R1_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=40,imm=0) "
> + "R6_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=40,imm=0) refs=2,4\n"
> + "16: (85) call bpf_this_cpu_ptr#154\nR1 type=ptr_or_null_ expected=percpu_ptr_" },
> +};
> +
Hey Kumar,
pop_front_off/pop_back_off validation seems to rely on exact register
usage (r6 in this case) generated by the compiler, while the test
itself is written in C, so really nothing is guaranteed. And that's
exactly what seems to happen to me locally, as in my case compiler
chose to use r7 in this particular spot (see logs below).
Can you please take a look and try to make it more robust? Ideally we
should probably rewrite BPF program to use inline assembly if we are
to check the exact instruction index and registers.
Here are error logs:
test_linked_list_fail_prog:PASS:linked_list_fail__open_opts 0 nsec
test_linked_list_fail_prog:PASS:bpf_object__find_program_by_name 0 nsec
libbpf: prog 'pop_front_off': BPF program load failed: Permission denied
libbpf: prog 'pop_front_off': failed to load: -13
libbpf: failed to load object 'linked_list_fail'
libbpf: failed to load BPF skeleton 'linked_list_fail': -13
test_linked_list_fail_prog:PASS:linked_list_fail__load must fail 0 nsec
test_linked_list_fail_prog:FAIL:expected error message unexpected error: -13
Expected: 15: (bf) r1 = r6 ;
R1_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0)
R6_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0) refs=2,4
16: (85) call bpf_this_cpu_ptr#154
R1 type=ptr_or_null_ expected=percpu_ptr_
Verifier: reg type unsupported for arg#0 function pop_front_off#173
0: R1=ctx(off=0,imm=0) R10=fp0
; p = bpf_obj_new(typeof(*p));
0: (18) r1 = 0xae ; R1_w=174
2: (b7) r2 = 0 ; R2_w=0
3: (85) call bpf_obj_new_impl#25364 ;
R0_w=ptr_or_null_(id=2,ref_obj_id=2,off=0,imm=0) refs=2
; if (!p)
4: (15) if r0 == 0x0 goto pc+12 ;
R0_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0) refs=2
; bpf_spin_lock(&p->lock);
5: (bf) r6 = r0 ;
R0_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0)
R6_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0) refs=2
6: (07) r6 += 16 ;
R6_w=ptr_(id=2,ref_obj_id=2,off=16,imm=0) refs=2
; bpf_spin_lock(&p->lock);
7: (bf) r1 = r6 ;
R1_w=ptr_(id=2,ref_obj_id=2,off=16,imm=0)
R6_w=ptr_(id=2,ref_obj_id=2,off=16,imm=0) refs=2
8: (bf) r7 = r0 ;
R0_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0)
R7_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0) refs=2
9: (85) call bpf_spin_lock#93 ; refs=2
; n = op(&p->head);
10: (bf) r1 = r7 ;
R1_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0)
R7=ptr_(id=2,ref_obj_id=2,off=0,imm=0) refs=2
11: (85) call bpf_list_pop_front#25345 ;
R0_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0) refs=2,4
12: (bf) r7 = r0 ;
R0_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0)
R7_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0) refs=2,4
; bpf_spin_unlock(&p->lock);
13: (bf) r1 = r6 ;
R1_w=ptr_(id=2,ref_obj_id=2,off=16,imm=0)
R6=ptr_(id=2,ref_obj_id=2,off=16,imm=0) refs=2,4
14: (85) call bpf_spin_unlock#94 ; refs=2,4
; bpf_this_cpu_ptr(n);
15: (bf) r1 = r7 ;
R1_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0)
R7_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0) refs=2,4
16: (85) call bpf_this_cpu_ptr#154
R1 type=ptr_or_null_ expected=percpu_ptr_, percpu_rcu_ptr_, percpu_trusted_ptr_
processed 16 insns (limit 1000000) max_states_per_insn 0 total_states
1 peak_states 1 mark_read 1
#126/115 linked_list/pop_front_off:FAIL
test_linked_list_fail_prog:PASS:linked_list_fail__open_opts 0 nsec
test_linked_list_fail_prog:PASS:bpf_object__find_program_by_name 0 nsec
libbpf: prog 'pop_back_off': BPF program load failed: Permission denied
libbpf: prog 'pop_back_off': failed to load: -13
libbpf: failed to load object 'linked_list_fail'
libbpf: failed to load BPF skeleton 'linked_list_fail': -13
test_linked_list_fail_prog:PASS:linked_list_fail__load must fail 0 nsec
test_linked_list_fail_prog:FAIL:expected error message unexpected error: -13
Expected: 15: (bf) r1 = r6 ;
R1_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0)
R6_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0) refs=2,4
16: (85) call bpf_this_cpu_ptr#154
R1 type=ptr_or_null_ expected=percpu_ptr_
Verifier: reg type unsupported for arg#0 function pop_back_off#176
0: R1=ctx(off=0,imm=0) R10=fp0
; p = bpf_obj_new(typeof(*p));
0: (18) r1 = 0xae ; R1_w=174
2: (b7) r2 = 0 ; R2_w=0
3: (85) call bpf_obj_new_impl#25364 ;
R0_w=ptr_or_null_(id=2,ref_obj_id=2,off=0,imm=0) refs=2
; if (!p)
4: (15) if r0 == 0x0 goto pc+12 ;
R0_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0) refs=2
; bpf_spin_lock(&p->lock);
5: (bf) r6 = r0 ;
R0_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0)
R6_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0) refs=2
6: (07) r6 += 16 ;
R6_w=ptr_(id=2,ref_obj_id=2,off=16,imm=0) refs=2
; bpf_spin_lock(&p->lock);
7: (bf) r1 = r6 ;
R1_w=ptr_(id=2,ref_obj_id=2,off=16,imm=0)
R6_w=ptr_(id=2,ref_obj_id=2,off=16,imm=0) refs=2
8: (bf) r7 = r0 ;
R0_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0)
R7_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0) refs=2
9: (85) call bpf_spin_lock#93 ; refs=2
; n = op(&p->head);
10: (bf) r1 = r7 ;
R1_w=ptr_(id=2,ref_obj_id=2,off=0,imm=0)
R7=ptr_(id=2,ref_obj_id=2,off=0,imm=0) refs=2
11: (85) call bpf_list_pop_back#25344 ;
R0_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0) refs=2,4
12: (bf) r7 = r0 ;
R0_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0)
R7_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0) refs=2,4
; bpf_spin_unlock(&p->lock);
13: (bf) r1 = r6 ;
R1_w=ptr_(id=2,ref_obj_id=2,off=16,imm=0)
R6=ptr_(id=2,ref_obj_id=2,off=16,imm=0) refs=2,4
14: (85) call bpf_spin_unlock#94 ; refs=2,4
; bpf_this_cpu_ptr(n);
15: (bf) r1 = r7 ;
R1_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0)
R7_w=ptr_or_null_foo(id=4,ref_obj_id=4,off=48,imm=0) refs=2,4
16: (85) call bpf_this_cpu_ptr#154
R1 type=ptr_or_null_ expected=percpu_ptr_, percpu_rcu_ptr_, percpu_trusted_ptr_
processed 16 insns (limit 1000000) max_states_per_insn 0 total_states
1 peak_states 1 mark_read 1
#126/116 linked_list/pop_back_off:FAIL
Thanks!
[...]
> +
> +static __always_inline
> +int pop_ptr_off(void *(*op)(void *head))
> +{
> + struct {
> + struct bpf_list_head head __contains(foo, node2);
> + struct bpf_spin_lock lock;
> + } *p;
> + struct bpf_list_node *n;
> +
> + p = bpf_obj_new(typeof(*p));
> + if (!p)
> + return 0;
> + bpf_spin_lock(&p->lock);
> + n = op(&p->head);
> + bpf_spin_unlock(&p->lock);
> +
> + bpf_this_cpu_ptr(n);
> + return 0;
> +}
> +
> +SEC("?tc")
> +int pop_front_off(void *ctx)
> +{
> + return pop_ptr_off((void *)bpf_list_pop_front);
> +}
> +
> +SEC("?tc")
> +int pop_back_off(void *ctx)
> +{
> + return pop_ptr_off((void *)bpf_list_pop_back);
> +}
> +
> +char _license[] SEC("license") = "GPL";
> --
> 2.38.1
>
