On Fri, 20 Oct 2023 at 02:15, Andrii Nakryiko <andrii.nakryiko@xxxxxxxxx> wrote:
>
> 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?
>
Hi Andrii, sorry for the delay. The fix should be relatively simple,
we just need to check whether the offset on the returned pointer is
48.
I have posted a fix here, PTAL. Thanks.
https://lore.kernel.org/bpf/20231020144839.2734006-1-memxor@xxxxxxxxx
