* [PATCH bpf-next 0/4] bpf: precision tracking tests
@ 2019-08-23 5:52 Alexei Starovoitov
2019-08-23 5:52 ` [PATCH bpf-next 1/4] bpf: introduce verifier internal test flag Alexei Starovoitov
` (4 more replies)
0 siblings, 5 replies; 12+ messages in thread
From: Alexei Starovoitov @ 2019-08-23 5:52 UTC (permalink / raw)
To: davem; +Cc: daniel, netdev, bpf, kernel-team
Add few additional tests for precision tracking in the verifier.
Alexei Starovoitov (4):
bpf: introduce verifier internal test flag
tools/bpf: sync bpf.h
selftests/bpf: verifier precise tests
selftests/bpf: add precision tracking test
include/linux/bpf_verifier.h | 1 +
include/uapi/linux/bpf.h | 3 +
kernel/bpf/syscall.c | 1 +
kernel/bpf/verifier.c | 5 +-
tools/include/uapi/linux/bpf.h | 3 +
tools/testing/selftests/bpf/test_verifier.c | 68 +++++++--
.../testing/selftests/bpf/verifier/precise.c | 142 ++++++++++++++++++
7 files changed, 211 insertions(+), 12 deletions(-)
create mode 100644 tools/testing/selftests/bpf/verifier/precise.c
--
2.20.0
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH bpf-next 1/4] bpf: introduce verifier internal test flag 2019-08-23 5:52 [PATCH bpf-next 0/4] bpf: precision tracking tests Alexei Starovoitov @ 2019-08-23 5:52 ` Alexei Starovoitov 2019-08-26 5:09 ` Song Liu 2019-08-23 5:52 ` [PATCH bpf-next 2/4] tools/bpf: sync bpf.h Alexei Starovoitov ` (3 subsequent siblings) 4 siblings, 1 reply; 12+ messages in thread From: Alexei Starovoitov @ 2019-08-23 5:52 UTC (permalink / raw) To: davem; +Cc: daniel, netdev, bpf, kernel-team Introduce BPF_F_TEST_STATE_FREQ flag to stress test parentage chain and state pruning. Signed-off-by: Alexei Starovoitov <ast@kernel.org> --- include/linux/bpf_verifier.h | 1 + include/uapi/linux/bpf.h | 3 +++ kernel/bpf/syscall.c | 1 + kernel/bpf/verifier.c | 5 ++++- 4 files changed, 9 insertions(+), 1 deletion(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 5fe99f322b1c..26a6d58ca78c 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -355,6 +355,7 @@ struct bpf_verifier_env { struct bpf_verifier_stack_elem *head; /* stack of verifier states to be processed */ int stack_size; /* number of states to be processed */ bool strict_alignment; /* perform strict pointer alignment checks */ + bool test_state_freq; /* test verifier with different pruning frequency */ struct bpf_verifier_state *cur_state; /* current verifier state */ struct bpf_verifier_state_list **explored_states; /* search pruning optimization */ struct bpf_verifier_state_list *free_list; diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h index b5889257cc33..5d2fb183ee2d 100644 --- a/include/uapi/linux/bpf.h +++ b/include/uapi/linux/bpf.h @@ -285,6 +285,9 @@ enum bpf_attach_type { */ #define BPF_F_TEST_RND_HI32 (1U << 2) +/* The verifier internal test flag. Behavior is undefined */ +#define BPF_F_TEST_STATE_FREQ (1U << 3) + /* When BPF ldimm64's insn[0].src_reg != 0 then this can have * two extensions: * diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c index c0f62fd67c6b..ca60eafa6922 100644 --- a/kernel/bpf/syscall.c +++ b/kernel/bpf/syscall.c @@ -1629,6 +1629,7 @@ static int bpf_prog_load(union bpf_attr *attr, union bpf_attr __user *uattr) if (attr->prog_flags & ~(BPF_F_STRICT_ALIGNMENT | BPF_F_ANY_ALIGNMENT | + BPF_F_TEST_STATE_FREQ | BPF_F_TEST_RND_HI32)) return -EINVAL; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 16d66bd7af09..3fb50757e812 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -7223,7 +7223,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) struct bpf_verifier_state_list *sl, **pprev; struct bpf_verifier_state *cur = env->cur_state, *new; int i, j, err, states_cnt = 0; - bool add_new_state = false; + bool add_new_state = env->test_state_freq ? true : false; cur->last_insn_idx = env->prev_insn_idx; if (!env->insn_aux_data[insn_idx].prune_point) @@ -9263,6 +9263,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, env->allow_ptr_leaks = is_priv; + if (is_priv) + env->test_state_freq = attr->prog_flags & BPF_F_TEST_STATE_FREQ; + ret = replace_map_fd_with_map_ptr(env); if (ret < 0) goto skip_full_check; -- 2.20.0 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH bpf-next 1/4] bpf: introduce verifier internal test flag 2019-08-23 5:52 ` [PATCH bpf-next 1/4] bpf: introduce verifier internal test flag Alexei Starovoitov @ 2019-08-26 5:09 ` Song Liu 0 siblings, 0 replies; 12+ messages in thread From: Song Liu @ 2019-08-26 5:09 UTC (permalink / raw) To: Alexei Starovoitov Cc: David S . Miller, Daniel Borkmann, Networking, bpf, Kernel Team On Fri, Aug 23, 2019 at 2:59 AM Alexei Starovoitov <ast@kernel.org> wrote: > > Introduce BPF_F_TEST_STATE_FREQ flag to stress test parentage chain > and state pruning. > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> Acked-by: Song Liu <songliubraving@fb.com> > --- > include/linux/bpf_verifier.h | 1 + > include/uapi/linux/bpf.h | 3 +++ > kernel/bpf/syscall.c | 1 + > kernel/bpf/verifier.c | 5 ++++- > 4 files changed, 9 insertions(+), 1 deletion(-) > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h > index 5fe99f322b1c..26a6d58ca78c 100644 > --- a/include/linux/bpf_verifier.h > +++ b/include/linux/bpf_verifier.h > @@ -355,6 +355,7 @@ struct bpf_verifier_env { > struct bpf_verifier_stack_elem *head; /* stack of verifier states to be processed */ > int stack_size; /* number of states to be processed */ > bool strict_alignment; /* perform strict pointer alignment checks */ > + bool test_state_freq; /* test verifier with different pruning frequency */ > struct bpf_verifier_state *cur_state; /* current verifier state */ > struct bpf_verifier_state_list **explored_states; /* search pruning optimization */ > struct bpf_verifier_state_list *free_list; > diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h > index b5889257cc33..5d2fb183ee2d 100644 > --- a/include/uapi/linux/bpf.h > +++ b/include/uapi/linux/bpf.h > @@ -285,6 +285,9 @@ enum bpf_attach_type { > */ > #define BPF_F_TEST_RND_HI32 (1U << 2) > > +/* The verifier internal test flag. Behavior is undefined */ > +#define BPF_F_TEST_STATE_FREQ (1U << 3) > + > /* When BPF ldimm64's insn[0].src_reg != 0 then this can have > * two extensions: > * > diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c > index c0f62fd67c6b..ca60eafa6922 100644 > --- a/kernel/bpf/syscall.c > +++ b/kernel/bpf/syscall.c > @@ -1629,6 +1629,7 @@ static int bpf_prog_load(union bpf_attr *attr, union bpf_attr __user *uattr) > > if (attr->prog_flags & ~(BPF_F_STRICT_ALIGNMENT | > BPF_F_ANY_ALIGNMENT | > + BPF_F_TEST_STATE_FREQ | > BPF_F_TEST_RND_HI32)) > return -EINVAL; > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 16d66bd7af09..3fb50757e812 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -7223,7 +7223,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) > struct bpf_verifier_state_list *sl, **pprev; > struct bpf_verifier_state *cur = env->cur_state, *new; > int i, j, err, states_cnt = 0; > - bool add_new_state = false; > + bool add_new_state = env->test_state_freq ? true : false; > > cur->last_insn_idx = env->prev_insn_idx; > if (!env->insn_aux_data[insn_idx].prune_point) > @@ -9263,6 +9263,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, > > env->allow_ptr_leaks = is_priv; > > + if (is_priv) > + env->test_state_freq = attr->prog_flags & BPF_F_TEST_STATE_FREQ; > + > ret = replace_map_fd_with_map_ptr(env); > if (ret < 0) > goto skip_full_check; > -- > 2.20.0 > ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH bpf-next 2/4] tools/bpf: sync bpf.h 2019-08-23 5:52 [PATCH bpf-next 0/4] bpf: precision tracking tests Alexei Starovoitov 2019-08-23 5:52 ` [PATCH bpf-next 1/4] bpf: introduce verifier internal test flag Alexei Starovoitov @ 2019-08-23 5:52 ` Alexei Starovoitov 2019-08-26 5:10 ` Song Liu 2019-08-23 5:52 ` [PATCH bpf-next 3/4] selftests/bpf: verifier precise tests Alexei Starovoitov ` (2 subsequent siblings) 4 siblings, 1 reply; 12+ messages in thread From: Alexei Starovoitov @ 2019-08-23 5:52 UTC (permalink / raw) To: davem; +Cc: daniel, netdev, bpf, kernel-team sync bpf.h from kernel/ to tools/ Signed-off-by: Alexei Starovoitov <ast@kernel.org> --- tools/include/uapi/linux/bpf.h | 3 +++ 1 file changed, 3 insertions(+) diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h index b5889257cc33..5d2fb183ee2d 100644 --- a/tools/include/uapi/linux/bpf.h +++ b/tools/include/uapi/linux/bpf.h @@ -285,6 +285,9 @@ enum bpf_attach_type { */ #define BPF_F_TEST_RND_HI32 (1U << 2) +/* The verifier internal test flag. Behavior is undefined */ +#define BPF_F_TEST_STATE_FREQ (1U << 3) + /* When BPF ldimm64's insn[0].src_reg != 0 then this can have * two extensions: * -- 2.20.0 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH bpf-next 2/4] tools/bpf: sync bpf.h 2019-08-23 5:52 ` [PATCH bpf-next 2/4] tools/bpf: sync bpf.h Alexei Starovoitov @ 2019-08-26 5:10 ` Song Liu 0 siblings, 0 replies; 12+ messages in thread From: Song Liu @ 2019-08-26 5:10 UTC (permalink / raw) To: Alexei Starovoitov Cc: David S . Miller, Daniel Borkmann, Networking, bpf, Kernel Team On Fri, Aug 23, 2019 at 2:59 AM Alexei Starovoitov <ast@kernel.org> wrote: > > sync bpf.h from kernel/ to tools/ > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> Acked-by: Song Liu <songliubraving@fb.com> ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH bpf-next 3/4] selftests/bpf: verifier precise tests 2019-08-23 5:52 [PATCH bpf-next 0/4] bpf: precision tracking tests Alexei Starovoitov 2019-08-23 5:52 ` [PATCH bpf-next 1/4] bpf: introduce verifier internal test flag Alexei Starovoitov 2019-08-23 5:52 ` [PATCH bpf-next 2/4] tools/bpf: sync bpf.h Alexei Starovoitov @ 2019-08-23 5:52 ` Alexei Starovoitov 2019-08-26 5:22 ` Song Liu 2019-08-23 5:52 ` [PATCH bpf-next 4/4] selftests/bpf: add precision tracking test Alexei Starovoitov 2019-08-27 22:43 ` [PATCH bpf-next 0/4] bpf: precision tracking tests Daniel Borkmann 4 siblings, 1 reply; 12+ messages in thread From: Alexei Starovoitov @ 2019-08-23 5:52 UTC (permalink / raw) To: davem; +Cc: daniel, netdev, bpf, kernel-team Use BPF_F_TEST_STATE_FREQ flag to check that precision tracking works as expected by comparing every step it takes. Signed-off-by: Alexei Starovoitov <ast@kernel.org> --- tools/testing/selftests/bpf/test_verifier.c | 68 ++++++++-- .../testing/selftests/bpf/verifier/precise.c | 117 ++++++++++++++++++ 2 files changed, 174 insertions(+), 11 deletions(-) create mode 100644 tools/testing/selftests/bpf/verifier/precise.c diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c index 44e2d640b088..d27fd929abb9 100644 --- a/tools/testing/selftests/bpf/test_verifier.c +++ b/tools/testing/selftests/bpf/test_verifier.c @@ -61,6 +61,7 @@ #define UNPRIV_SYSCTL "kernel/unprivileged_bpf_disabled" static bool unpriv_disabled = false; static int skips; +static bool verbose = false; struct bpf_test { const char *descr; @@ -92,7 +93,8 @@ struct bpf_test { enum { UNDEF, ACCEPT, - REJECT + REJECT, + VERBOSE_ACCEPT, } result, result_unpriv; enum bpf_prog_type prog_type; uint8_t flags; @@ -859,6 +861,36 @@ static int do_prog_test_run(int fd_prog, bool unpriv, uint32_t expected_val, return 0; } +static bool cmp_str_seq(const char *log, const char *exp) +{ + char needle[80]; + const char *p, *q; + int len; + + do { + p = strchr(exp, '\t'); + if (!p) + p = exp + strlen(exp); + + len = p - exp; + if (len >= sizeof(needle) || !len) { + printf("FAIL\nTestcase bug\n"); + return false; + } + strncpy(needle, exp, len); + needle[len] = 0; + q = strstr(log, needle); + if (!q) { + printf("FAIL\nUnexpected verifier log in successful load!\n" + "EXP: %s\nRES:\n", needle); + return false; + } + log = q + len; + exp = p + 1; + } while (*p); + return true; +} + static void do_test_single(struct bpf_test *test, bool unpriv, int *passes, int *errors) { @@ -897,14 +929,20 @@ static void do_test_single(struct bpf_test *test, bool unpriv, pflags |= BPF_F_STRICT_ALIGNMENT; if (test->flags & F_NEEDS_EFFICIENT_UNALIGNED_ACCESS) pflags |= BPF_F_ANY_ALIGNMENT; + if (test->flags & ~3) + pflags |= test->flags; + expected_ret = unpriv && test->result_unpriv != UNDEF ? + test->result_unpriv : test->result; + expected_err = unpriv && test->errstr_unpriv ? + test->errstr_unpriv : test->errstr; memset(&attr, 0, sizeof(attr)); attr.prog_type = prog_type; attr.expected_attach_type = test->expected_attach_type; attr.insns = prog; attr.insns_cnt = prog_len; attr.license = "GPL"; - attr.log_level = 4; + attr.log_level = verbose || expected_ret == VERBOSE_ACCEPT ? 1 : 4; attr.prog_flags = pflags; fd_prog = bpf_load_program_xattr(&attr, bpf_vlog, sizeof(bpf_vlog)); @@ -914,14 +952,9 @@ static void do_test_single(struct bpf_test *test, bool unpriv, goto close_fds; } - expected_ret = unpriv && test->result_unpriv != UNDEF ? - test->result_unpriv : test->result; - expected_err = unpriv && test->errstr_unpriv ? - test->errstr_unpriv : test->errstr; - alignment_prevented_execution = 0; - if (expected_ret == ACCEPT) { + if (expected_ret == ACCEPT || expected_ret == VERBOSE_ACCEPT) { if (fd_prog < 0) { printf("FAIL\nFailed to load prog '%s'!\n", strerror(errno)); @@ -932,6 +965,9 @@ static void do_test_single(struct bpf_test *test, bool unpriv, (test->flags & F_NEEDS_EFFICIENT_UNALIGNED_ACCESS)) alignment_prevented_execution = 1; #endif + if (expected_ret == VERBOSE_ACCEPT && !cmp_str_seq(bpf_vlog, expected_err)) { + goto fail_log; + } } else { if (fd_prog >= 0) { printf("FAIL\nUnexpected success to load!\n"); @@ -957,6 +993,9 @@ static void do_test_single(struct bpf_test *test, bool unpriv, } } + if (verbose) + printf(", verifier log:\n%s", bpf_vlog); + run_errs = 0; run_successes = 0; if (!alignment_prevented_execution && fd_prog >= 0) { @@ -1097,17 +1136,24 @@ int main(int argc, char **argv) { unsigned int from = 0, to = ARRAY_SIZE(tests); bool unpriv = !is_admin(); + int arg = 1; + + if (argc > 1 && strcmp(argv[1], "-v") == 0) { + arg++; + verbose = true; + argc--; + } if (argc == 3) { - unsigned int l = atoi(argv[argc - 2]); - unsigned int u = atoi(argv[argc - 1]); + unsigned int l = atoi(argv[arg]); + unsigned int u = atoi(argv[arg + 1]); if (l < to && u < to) { from = l; to = u + 1; } } else if (argc == 2) { - unsigned int t = atoi(argv[argc - 1]); + unsigned int t = atoi(argv[arg]); if (t < to) { from = t; diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c new file mode 100644 index 000000000000..a20953c23721 --- /dev/null +++ b/tools/testing/selftests/bpf/verifier/precise.c @@ -0,0 +1,117 @@ +{ + "precise: test 1", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 1), + BPF_LD_MAP_FD(BPF_REG_6, 0), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), + BPF_ST_MEM(BPF_DW, BPF_REG_FP, -8, 0), + BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), + BPF_EXIT_INSN(), + + BPF_MOV64_REG(BPF_REG_9, BPF_REG_0), + + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), + BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), + BPF_EXIT_INSN(), + + BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), + + BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_8), /* map_value_ptr -= map_value_ptr */ + BPF_MOV64_REG(BPF_REG_2, BPF_REG_9), + BPF_JMP_IMM(BPF_JLT, BPF_REG_2, 8, 1), + BPF_EXIT_INSN(), + + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1), /* R2=inv(umin=1, umax=8) */ + BPF_MOV64_REG(BPF_REG_1, BPF_REG_FP), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -8), + BPF_MOV64_IMM(BPF_REG_3, 0), + BPF_EMIT_CALL(BPF_FUNC_probe_read), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .fixup_map_array_48b = { 1 }, + .result = VERBOSE_ACCEPT, + .errstr = + "26: (85) call bpf_probe_read#4\ + last_idx 26 first_idx 20\ + regs=4 stack=0 before 25\ + regs=4 stack=0 before 24\ + regs=4 stack=0 before 23\ + regs=4 stack=0 before 22\ + regs=4 stack=0 before 20\ + parent didn't have regs=4 stack=0 marks\ + last_idx 19 first_idx 10\ + regs=4 stack=0 before 19\ + regs=200 stack=0 before 18\ + regs=300 stack=0 before 17\ + regs=201 stack=0 before 15\ + regs=201 stack=0 before 14\ + regs=200 stack=0 before 13\ + regs=200 stack=0 before 12\ + regs=200 stack=0 before 11\ + regs=200 stack=0 before 10\ + parent already had regs=0 stack=0 marks", +}, +{ + "precise: test 2", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 1), + BPF_LD_MAP_FD(BPF_REG_6, 0), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), + BPF_ST_MEM(BPF_DW, BPF_REG_FP, -8, 0), + BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), + BPF_EXIT_INSN(), + + BPF_MOV64_REG(BPF_REG_9, BPF_REG_0), + + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), + BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), + BPF_EXIT_INSN(), + + BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), + + BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_8), /* map_value_ptr -= map_value_ptr */ + BPF_MOV64_REG(BPF_REG_2, BPF_REG_9), + BPF_JMP_IMM(BPF_JLT, BPF_REG_2, 8, 1), + BPF_EXIT_INSN(), + + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1), /* R2=inv(umin=1, umax=8) */ + BPF_MOV64_REG(BPF_REG_1, BPF_REG_FP), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -8), + BPF_MOV64_IMM(BPF_REG_3, 0), + BPF_EMIT_CALL(BPF_FUNC_probe_read), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .fixup_map_array_48b = { 1 }, + .result = VERBOSE_ACCEPT, + .flags = BPF_F_TEST_STATE_FREQ, + .errstr = + "26: (85) call bpf_probe_read#4\ + last_idx 26 first_idx 22\ + regs=4 stack=0 before 25\ + regs=4 stack=0 before 24\ + regs=4 stack=0 before 23\ + regs=4 stack=0 before 22\ + parent didn't have regs=4 stack=0 marks\ + last_idx 20 first_idx 20\ + regs=4 stack=0 before 20\ + parent didn't have regs=4 stack=0 marks\ + last_idx 19 first_idx 17\ + regs=4 stack=0 before 19\ + regs=200 stack=0 before 18\ + regs=300 stack=0 before 17\ + parent already had regs=0 stack=0 marks", +}, -- 2.20.0 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH bpf-next 3/4] selftests/bpf: verifier precise tests 2019-08-23 5:52 ` [PATCH bpf-next 3/4] selftests/bpf: verifier precise tests Alexei Starovoitov @ 2019-08-26 5:22 ` Song Liu 2019-08-26 22:47 ` Alexei Starovoitov 0 siblings, 1 reply; 12+ messages in thread From: Song Liu @ 2019-08-26 5:22 UTC (permalink / raw) To: Alexei Starovoitov Cc: David S . Miller, Daniel Borkmann, Networking, bpf, Kernel Team On Fri, Aug 23, 2019 at 2:59 AM Alexei Starovoitov <ast@kernel.org> wrote: > > Use BPF_F_TEST_STATE_FREQ flag to check that precision > tracking works as expected by comparing every step it takes. > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> > --- > tools/testing/selftests/bpf/test_verifier.c | 68 ++++++++-- > .../testing/selftests/bpf/verifier/precise.c | 117 ++++++++++++++++++ > 2 files changed, 174 insertions(+), 11 deletions(-) > create mode 100644 tools/testing/selftests/bpf/verifier/precise.c > > diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c > index 44e2d640b088..d27fd929abb9 100644 > --- a/tools/testing/selftests/bpf/test_verifier.c > +++ b/tools/testing/selftests/bpf/test_verifier.c > @@ -61,6 +61,7 @@ > #define UNPRIV_SYSCTL "kernel/unprivileged_bpf_disabled" > static bool unpriv_disabled = false; > static int skips; > +static bool verbose = false; > > struct bpf_test { > const char *descr; > @@ -92,7 +93,8 @@ struct bpf_test { > enum { > UNDEF, > ACCEPT, > - REJECT > + REJECT, > + VERBOSE_ACCEPT, > } result, result_unpriv; > enum bpf_prog_type prog_type; > uint8_t flags; > @@ -859,6 +861,36 @@ static int do_prog_test_run(int fd_prog, bool unpriv, uint32_t expected_val, > return 0; > } > > +static bool cmp_str_seq(const char *log, const char *exp) Maybe call it str_str_seq()? > +{ > + char needle[80]; > + const char *p, *q; > + int len; > + > + do { > + p = strchr(exp, '\t'); > + if (!p) > + p = exp + strlen(exp); > + > + len = p - exp; > + if (len >= sizeof(needle) || !len) { > + printf("FAIL\nTestcase bug\n"); > + return false; > + } > + strncpy(needle, exp, len); > + needle[len] = 0; > + q = strstr(log, needle); > + if (!q) { > + printf("FAIL\nUnexpected verifier log in successful load!\n" > + "EXP: %s\nRES:\n", needle); > + return false; > + } > + log = q + len; > + exp = p + 1; > + } while (*p); > + return true; > +} > + > static void do_test_single(struct bpf_test *test, bool unpriv, > int *passes, int *errors) > { > @@ -897,14 +929,20 @@ static void do_test_single(struct bpf_test *test, bool unpriv, > pflags |= BPF_F_STRICT_ALIGNMENT; > if (test->flags & F_NEEDS_EFFICIENT_UNALIGNED_ACCESS) > pflags |= BPF_F_ANY_ALIGNMENT; > + if (test->flags & ~3) > + pflags |= test->flags; ^^^^^^ why do we need these two lines? > > + expected_ret = unpriv && test->result_unpriv != UNDEF ? > + test->result_unpriv : test->result; > + expected_err = unpriv && test->errstr_unpriv ? > + test->errstr_unpriv : test->errstr; > memset(&attr, 0, sizeof(attr)); > attr.prog_type = prog_type; > attr.expected_attach_type = test->expected_attach_type; > attr.insns = prog; > attr.insns_cnt = prog_len; > attr.license = "GPL"; > - attr.log_level = 4; > + attr.log_level = verbose || expected_ret == VERBOSE_ACCEPT ? 1 : 4; > attr.prog_flags = pflags; > > fd_prog = bpf_load_program_xattr(&attr, bpf_vlog, sizeof(bpf_vlog)); > @@ -914,14 +952,9 @@ static void do_test_single(struct bpf_test *test, bool unpriv, > goto close_fds; > } > > - expected_ret = unpriv && test->result_unpriv != UNDEF ? > - test->result_unpriv : test->result; > - expected_err = unpriv && test->errstr_unpriv ? > - test->errstr_unpriv : test->errstr; > - > alignment_prevented_execution = 0; > > - if (expected_ret == ACCEPT) { > + if (expected_ret == ACCEPT || expected_ret == VERBOSE_ACCEPT) { > if (fd_prog < 0) { > printf("FAIL\nFailed to load prog '%s'!\n", > strerror(errno)); > @@ -932,6 +965,9 @@ static void do_test_single(struct bpf_test *test, bool unpriv, > (test->flags & F_NEEDS_EFFICIENT_UNALIGNED_ACCESS)) > alignment_prevented_execution = 1; > #endif > + if (expected_ret == VERBOSE_ACCEPT && !cmp_str_seq(bpf_vlog, expected_err)) { > + goto fail_log; > + } > } else { > if (fd_prog >= 0) { > printf("FAIL\nUnexpected success to load!\n"); > @@ -957,6 +993,9 @@ static void do_test_single(struct bpf_test *test, bool unpriv, > } > } > > + if (verbose) > + printf(", verifier log:\n%s", bpf_vlog); > + > run_errs = 0; > run_successes = 0; > if (!alignment_prevented_execution && fd_prog >= 0) { > @@ -1097,17 +1136,24 @@ int main(int argc, char **argv) > { > unsigned int from = 0, to = ARRAY_SIZE(tests); > bool unpriv = !is_admin(); > + int arg = 1; > + > + if (argc > 1 && strcmp(argv[1], "-v") == 0) { > + arg++; > + verbose = true; > + argc--; > + } > > if (argc == 3) { > - unsigned int l = atoi(argv[argc - 2]); > - unsigned int u = atoi(argv[argc - 1]); > + unsigned int l = atoi(argv[arg]); > + unsigned int u = atoi(argv[arg + 1]); > > if (l < to && u < to) { > from = l; > to = u + 1; > } > } else if (argc == 2) { > - unsigned int t = atoi(argv[argc - 1]); > + unsigned int t = atoi(argv[arg]); > > if (t < to) { > from = t; > diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c > new file mode 100644 > index 000000000000..a20953c23721 > --- /dev/null > +++ b/tools/testing/selftests/bpf/verifier/precise.c > @@ -0,0 +1,117 @@ > +{ > + "precise: test 1", > + .insns = { > + BPF_MOV64_IMM(BPF_REG_0, 1), > + BPF_LD_MAP_FD(BPF_REG_6, 0), > + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), > + BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), > + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), > + BPF_ST_MEM(BPF_DW, BPF_REG_FP, -8, 0), > + BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), > + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), > + BPF_EXIT_INSN(), > + > + BPF_MOV64_REG(BPF_REG_9, BPF_REG_0), > + > + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), > + BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), > + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), > + BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), > + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), > + BPF_EXIT_INSN(), > + > + BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), > + > + BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_8), /* map_value_ptr -= map_value_ptr */ > + BPF_MOV64_REG(BPF_REG_2, BPF_REG_9), > + BPF_JMP_IMM(BPF_JLT, BPF_REG_2, 8, 1), > + BPF_EXIT_INSN(), > + > + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1), /* R2=inv(umin=1, umax=8) */ > + BPF_MOV64_REG(BPF_REG_1, BPF_REG_FP), > + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -8), > + BPF_MOV64_IMM(BPF_REG_3, 0), > + BPF_EMIT_CALL(BPF_FUNC_probe_read), > + BPF_EXIT_INSN(), > + }, > + .prog_type = BPF_PROG_TYPE_TRACEPOINT, > + .fixup_map_array_48b = { 1 }, > + .result = VERBOSE_ACCEPT, > + .errstr = > + "26: (85) call bpf_probe_read#4\ > + last_idx 26 first_idx 20\ > + regs=4 stack=0 before 25\ > + regs=4 stack=0 before 24\ > + regs=4 stack=0 before 23\ > + regs=4 stack=0 before 22\ > + regs=4 stack=0 before 20\ > + parent didn't have regs=4 stack=0 marks\ > + last_idx 19 first_idx 10\ > + regs=4 stack=0 before 19\ > + regs=200 stack=0 before 18\ > + regs=300 stack=0 before 17\ > + regs=201 stack=0 before 15\ > + regs=201 stack=0 before 14\ > + regs=200 stack=0 before 13\ > + regs=200 stack=0 before 12\ > + regs=200 stack=0 before 11\ > + regs=200 stack=0 before 10\ > + parent already had regs=0 stack=0 marks", > +}, > +{ > + "precise: test 2", > + .insns = { > + BPF_MOV64_IMM(BPF_REG_0, 1), > + BPF_LD_MAP_FD(BPF_REG_6, 0), > + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), > + BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), > + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), > + BPF_ST_MEM(BPF_DW, BPF_REG_FP, -8, 0), > + BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), > + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), > + BPF_EXIT_INSN(), > + > + BPF_MOV64_REG(BPF_REG_9, BPF_REG_0), > + > + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), > + BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), > + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), > + BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), > + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), > + BPF_EXIT_INSN(), > + > + BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), > + > + BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_8), /* map_value_ptr -= map_value_ptr */ > + BPF_MOV64_REG(BPF_REG_2, BPF_REG_9), > + BPF_JMP_IMM(BPF_JLT, BPF_REG_2, 8, 1), > + BPF_EXIT_INSN(), > + > + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1), /* R2=inv(umin=1, umax=8) */ > + BPF_MOV64_REG(BPF_REG_1, BPF_REG_FP), > + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -8), > + BPF_MOV64_IMM(BPF_REG_3, 0), > + BPF_EMIT_CALL(BPF_FUNC_probe_read), > + BPF_EXIT_INSN(), > + }, > + .prog_type = BPF_PROG_TYPE_TRACEPOINT, > + .fixup_map_array_48b = { 1 }, > + .result = VERBOSE_ACCEPT, > + .flags = BPF_F_TEST_STATE_FREQ, > + .errstr = > + "26: (85) call bpf_probe_read#4\ > + last_idx 26 first_idx 22\ > + regs=4 stack=0 before 25\ > + regs=4 stack=0 before 24\ > + regs=4 stack=0 before 23\ > + regs=4 stack=0 before 22\ > + parent didn't have regs=4 stack=0 marks\ > + last_idx 20 first_idx 20\ > + regs=4 stack=0 before 20\ > + parent didn't have regs=4 stack=0 marks\ > + last_idx 19 first_idx 17\ > + regs=4 stack=0 before 19\ > + regs=200 stack=0 before 18\ > + regs=300 stack=0 before 17\ > + parent already had regs=0 stack=0 marks", > +}, > -- > 2.20.0 > ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH bpf-next 3/4] selftests/bpf: verifier precise tests 2019-08-26 5:22 ` Song Liu @ 2019-08-26 22:47 ` Alexei Starovoitov 2019-08-26 22:51 ` Song Liu 0 siblings, 1 reply; 12+ messages in thread From: Alexei Starovoitov @ 2019-08-26 22:47 UTC (permalink / raw) To: Song Liu Cc: Alexei Starovoitov, David S . Miller, Daniel Borkmann, Networking, bpf, Kernel Team On Sun, Aug 25, 2019 at 10:22:13PM -0700, Song Liu wrote: > On Fri, Aug 23, 2019 at 2:59 AM Alexei Starovoitov <ast@kernel.org> wrote: > > > > Use BPF_F_TEST_STATE_FREQ flag to check that precision > > tracking works as expected by comparing every step it takes. > > > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> > > > > +static bool cmp_str_seq(const char *log, const char *exp) > > Maybe call it str_str_seq()? imo cmp*() returns the result of comparison. Which is either boolean or -1,0,1. Whereas str*() should return the address, index, or offset. Hence I used cmp_ prefix here. > > static void do_test_single(struct bpf_test *test, bool unpriv, > > int *passes, int *errors) > > { > > @@ -897,14 +929,20 @@ static void do_test_single(struct bpf_test *test, bool unpriv, > > pflags |= BPF_F_STRICT_ALIGNMENT; > > if (test->flags & F_NEEDS_EFFICIENT_UNALIGNED_ACCESS) > > pflags |= BPF_F_ANY_ALIGNMENT; > > + if (test->flags & ~3) > > + pflags |= test->flags; > ^^^^^^ why do we need these two lines? To pass flags from test into attr.prog_flags. Older F_NEEDS_* and F_LOAD_* may use some cleanup and can be removed, but it would be a different patch. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH bpf-next 3/4] selftests/bpf: verifier precise tests 2019-08-26 22:47 ` Alexei Starovoitov @ 2019-08-26 22:51 ` Song Liu 0 siblings, 0 replies; 12+ messages in thread From: Song Liu @ 2019-08-26 22:51 UTC (permalink / raw) To: Alexei Starovoitov Cc: Song Liu, Alexei Starovoitov, David S . Miller, Daniel Borkmann, Networking, bpf, Kernel Team > On Aug 26, 2019, at 3:47 PM, Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote: > > On Sun, Aug 25, 2019 at 10:22:13PM -0700, Song Liu wrote: >> On Fri, Aug 23, 2019 at 2:59 AM Alexei Starovoitov <ast@kernel.org> wrote: >>> >>> Use BPF_F_TEST_STATE_FREQ flag to check that precision >>> tracking works as expected by comparing every step it takes. >>> >>> Signed-off-by: Alexei Starovoitov <ast@kernel.org> >>> >>> +static bool cmp_str_seq(const char *log, const char *exp) >> >> Maybe call it str_str_seq()? > > imo cmp*() returns the result of comparison. > Which is either boolean or -1,0,1. > Whereas str*() should return the address, index, or offset. > Hence I used cmp_ prefix here. Good point. I didn't think about this. > >>> static void do_test_single(struct bpf_test *test, bool unpriv, >>> int *passes, int *errors) >>> { >>> @@ -897,14 +929,20 @@ static void do_test_single(struct bpf_test *test, bool unpriv, >>> pflags |= BPF_F_STRICT_ALIGNMENT; >>> if (test->flags & F_NEEDS_EFFICIENT_UNALIGNED_ACCESS) >>> pflags |= BPF_F_ANY_ALIGNMENT; >>> + if (test->flags & ~3) >>> + pflags |= test->flags; >> ^^^^^^ why do we need these two lines? > > To pass flags from test into attr.prog_flags. > Older F_NEEDS_* and F_LOAD_* may use some cleanup and can be removed, > but it would be a different patch. Sounds good. Acked-by: Song Liu <songliubraving@fb.com> Thanks! ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH bpf-next 4/4] selftests/bpf: add precision tracking test 2019-08-23 5:52 [PATCH bpf-next 0/4] bpf: precision tracking tests Alexei Starovoitov ` (2 preceding siblings ...) 2019-08-23 5:52 ` [PATCH bpf-next 3/4] selftests/bpf: verifier precise tests Alexei Starovoitov @ 2019-08-23 5:52 ` Alexei Starovoitov 2019-08-26 5:33 ` Song Liu 2019-08-27 22:43 ` [PATCH bpf-next 0/4] bpf: precision tracking tests Daniel Borkmann 4 siblings, 1 reply; 12+ messages in thread From: Alexei Starovoitov @ 2019-08-23 5:52 UTC (permalink / raw) To: davem; +Cc: daniel, netdev, bpf, kernel-team Copy-paste of existing test "calls: cross frame pruning - liveness propagation" but ran with different parentage chain heuristic which stresses different path in precision tracking logic. Signed-off-by: Alexei Starovoitov <ast@kernel.org> --- This test will be failing without this fix https://patchwork.ozlabs.org/patch/1151172/ --- .../testing/selftests/bpf/verifier/precise.c | 25 +++++++++++++++++++ 1 file changed, 25 insertions(+) diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c index a20953c23721..a455a4a71f11 100644 --- a/tools/testing/selftests/bpf/verifier/precise.c +++ b/tools/testing/selftests/bpf/verifier/precise.c @@ -115,3 +115,28 @@ regs=300 stack=0 before 17\ parent already had regs=0 stack=0 marks", }, +{ + "precise: cross frame pruning", + .insns = { + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32), + BPF_MOV64_IMM(BPF_REG_8, 0), + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), + BPF_MOV64_IMM(BPF_REG_8, 1), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32), + BPF_MOV64_IMM(BPF_REG_9, 0), + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), + BPF_MOV64_IMM(BPF_REG_9, 1), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_0), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 4), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_8, 1, 1), + BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_2, 0), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 0), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_XDP, + .flags = BPF_F_TEST_STATE_FREQ, + .errstr = "!read_ok", + .result = REJECT, +}, -- 2.20.0 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH bpf-next 4/4] selftests/bpf: add precision tracking test 2019-08-23 5:52 ` [PATCH bpf-next 4/4] selftests/bpf: add precision tracking test Alexei Starovoitov @ 2019-08-26 5:33 ` Song Liu 0 siblings, 0 replies; 12+ messages in thread From: Song Liu @ 2019-08-26 5:33 UTC (permalink / raw) To: Alexei Starovoitov Cc: David S . Miller, Daniel Borkmann, Networking, bpf, Kernel Team On Fri, Aug 23, 2019 at 3:00 AM Alexei Starovoitov <ast@kernel.org> wrote: > > Copy-paste of existing test > "calls: cross frame pruning - liveness propagation" > but ran with different parentage chain heuristic > which stresses different path in precision tracking logic. > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> Acked-by: Song Liu <songliubraving@fb.com> > ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH bpf-next 0/4] bpf: precision tracking tests 2019-08-23 5:52 [PATCH bpf-next 0/4] bpf: precision tracking tests Alexei Starovoitov ` (3 preceding siblings ...) 2019-08-23 5:52 ` [PATCH bpf-next 4/4] selftests/bpf: add precision tracking test Alexei Starovoitov @ 2019-08-27 22:43 ` Daniel Borkmann 4 siblings, 0 replies; 12+ messages in thread From: Daniel Borkmann @ 2019-08-27 22:43 UTC (permalink / raw) To: Alexei Starovoitov, davem; +Cc: netdev, bpf, kernel-team On 8/23/19 7:52 AM, Alexei Starovoitov wrote: > Add few additional tests for precision tracking in the verifier. > > Alexei Starovoitov (4): > bpf: introduce verifier internal test flag > tools/bpf: sync bpf.h > selftests/bpf: verifier precise tests > selftests/bpf: add precision tracking test > > include/linux/bpf_verifier.h | 1 + > include/uapi/linux/bpf.h | 3 + > kernel/bpf/syscall.c | 1 + > kernel/bpf/verifier.c | 5 +- > tools/include/uapi/linux/bpf.h | 3 + > tools/testing/selftests/bpf/test_verifier.c | 68 +++++++-- > .../testing/selftests/bpf/verifier/precise.c | 142 ++++++++++++++++++ > 7 files changed, 211 insertions(+), 12 deletions(-) > create mode 100644 tools/testing/selftests/bpf/verifier/precise.c > Applied, thanks! ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2019-08-27 22:43 UTC | newest] Thread overview: 12+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2019-08-23 5:52 [PATCH bpf-next 0/4] bpf: precision tracking tests Alexei Starovoitov 2019-08-23 5:52 ` [PATCH bpf-next 1/4] bpf: introduce verifier internal test flag Alexei Starovoitov 2019-08-26 5:09 ` Song Liu 2019-08-23 5:52 ` [PATCH bpf-next 2/4] tools/bpf: sync bpf.h Alexei Starovoitov 2019-08-26 5:10 ` Song Liu 2019-08-23 5:52 ` [PATCH bpf-next 3/4] selftests/bpf: verifier precise tests Alexei Starovoitov 2019-08-26 5:22 ` Song Liu 2019-08-26 22:47 ` Alexei Starovoitov 2019-08-26 22:51 ` Song Liu 2019-08-23 5:52 ` [PATCH bpf-next 4/4] selftests/bpf: add precision tracking test Alexei Starovoitov 2019-08-26 5:33 ` Song Liu 2019-08-27 22:43 ` [PATCH bpf-next 0/4] bpf: precision tracking tests Daniel Borkmann
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.