On Wed, Oct 11, 2023 at 4:02 PM Kumar Kartikeya Dwivedi
<memxor@xxxxxxxxx> wrote:
>
> 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.
Friendly ping! Did you get a chance to look at 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
> > >
