On Thu, 12 Oct 2023 at 00:44, Andrii Nakryiko <andrii.nakryiko@xxxxxxxxx> wrote:
>
> 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.
Thanks for the report Andrii.
I'll take a look and send a patch to address this.
>
> 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
> >
