verify callbacks as if they are called unknown number of times

This change prepares syncookie_{tc,xdp} for update in callbakcs verification logic. To allow bpf_loop() verification converge when multiple callback itreations are considered:
- track offset inside TCP payload explicitly, not as a part of the pointer;
- make sure that offset does not exceed MAX_PACKET_OFF enforced by verifier;
- make sure that offset is tracked as unbound scalar between iterations, otherwise verifier won't be able infer that bpf_loop callback reaches identical states.

Signed-off-by Eduard Zingerman <[email protected]>

---
 .../selftests/bpf/progs/xdp_synproxy_kern.c   | 84 ++++++++++++-------
 1 file changed, 52 insertions(+), 32 deletions(-)

This change prepares strobemeta for update in callbakcs verification

logic. To allow bpf_loop() verification converge when multiple callback itreations are considered:

- track offset inside strobemeta_payload->payload directly as scalar value;
- at each iteration make sure that remaining strobemeta_payload->payload capacity is sufficient for execution of read_{map,str}_var functions;
- make sure that offset is tracked as unbound scalar between iterations, otherwise verifier won't be able infer that bpf_loop callback reaches identical states.

Signed-off-by Eduard Zingerman <[email protected]>

---
 .../testing/selftests/bpf/progs/strobemeta.h  | 78 ++++++++++++-------
 1 file changed, 48 insertions(+), 30 deletions(-)

Quoted 2 lines · Eduard Zingerman

This change prepares strobemeta for update in callbakcs verification

typo: callbacks

Quoted 2 lines

logic. To allow bpf_loop() verification converge when multiple callback itreations are considered:

typo: iterations

The patch a few patches from this one changes logic for callbacks handling. While previously callbacks were verified as a single function call, new scheme takes into account that callbacks could be executed unknown number of times.

This has dire implications for bpf_loop_bench:

    SEC("fentry/" SYS_PREFIX "sys_getpgid")
    int benchmark(void *ctx)
    {
            for (int i = 0; i < 1000; i++) {
                    bpf_loop(nr_loops, empty_callback, NULL, 0);
                    __sync_add_and_fetch(&hits, nr_loops);
            }
            return 0;
    }

W/o callbacks change for verifier it merely represents 1000 calls to empty_callback(). However, with callbacks change things become exponential:
- i=0: state exploring empty_callback is scheduled with i=0 (a);
- i=1: state exploring empty_callback is scheduled with i=1;
...
- i=999: state exploring empty_callback is scheduled with i=999;
- state (a) is popped from stack;
- i=1: state exploring empty_callback is scheduled with i=1;
...

Avoid this issue by rewriting outer loop as bpf_loop(). Unfortunately, this adds a function call to a loop at runtime, which negatively affects performance:

throughput latency
before: 149.919 ± 0.168 M ops/s, 6.670 ns/op
after : 137.040 ± 0.187 M ops/s, 7.297 ns/op

Signed-off-by Eduard Zingerman <[email protected]>

---
 tools/testing/selftests/bpf/progs/bpf_loop_bench.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

tools/testing/selftests/bpf/progs/bpf_loop_bench.c +8 -6

index 4ce76eb064c4..d461746fd3c1 100644
@@ -15,13 +15,16 @@ static int empty_callback(__u32 index, void *data)
        return 0;
 }
 
+static int outer_loop(__u32 index, void *data)
+{
+       bpf_loop(nr_loops, empty_callback, NULL, 0);
+       __sync_add_and_fetch(&hits, nr_loops);
+       return 0;
+}
+
 SEC("fentry/" SYS_PREFIX "sys_getpgid")
 int benchmark(void *ctx)
 {
-       for (int i = 0; i < 1000; i++) {
-               bpf_loop(nr_loops, empty_callback, NULL, 0);
-
-               __sync_add_and_fetch(&hits, nr_loops);
-       }
+       bpf_loop(1000, outer_loop, NULL, 0);
        return 0;
 }
--

2.42.0

Quoted 12 lines

This has dire implications for bpf_loop_bench:

    SEC("fentry/" SYS_PREFIX "sys_getpgid")
    int benchmark(void *ctx)
    {
            for (int i = 0; i < 1000; i++) {
                    bpf_loop(nr_loops, empty_callback, NULL, 0);
                    __sync_add_and_fetch(&hits, nr_loops);
            }
            return 0;
    }

Quoted 10 lines

W/o callbacks change for verifier it merely represents 1000 calls to empty_callback(). However, with callbacks change things become exponential:
- i=0: state exploring empty_callback is scheduled with i=0 (a);
- i=1: state exploring empty_callback is scheduled with i=1;
...
- i=999: state exploring empty_callback is scheduled with i=999;
- state (a) is popped from stack;
- i=1: state exploring empty_callback is scheduled with i=1;
...

would this still happen if you use an obfuscated zero initializer for i?

int zero = 0; /* global var */

...

for (i = zero; i < 1000; i++) {
     ...
}

The patch a few patches from this one changes logic for callbacks handling.

Quoted 3 lines · Eduard Zingerman

The patch a few patches from this one changes logic for callbacks handling.

That's a wordsmith level 10. I'm far below this level.
Could you please rephrase it? 'The next patch changes ...' or something?

Quoted 7 lines · Alexei Starovoitov

Quoted 3 lines · Eduard Zingerman

The patch a few patches from this one changes logic for callbacks handling.

That's a wordsmith level 10. I'm far below this level.
Could you please rephrase it? 'The next patch changes ...' or something?

This is patch #3, and actual changes are in patch #6, I can change it to:

A follow-up patch "bpf: verify callbacks as if they are called unknown number of times" changes logic for callbacks handling. While previously callbacks were verified as a single function call, new scheme takes into account that callbacks could be executed unknown number of times.
...

Would that work?

Quoted 9 lines

This is patch #3, and actual changes are in patch #6, I can change it to:

A follow-up patch "bpf: verify callbacks as if they are called unknown number of times" changes logic for callbacks handling. While previously callbacks were verified as a single function call, new scheme takes into account that callbacks could be executed unknown number of times.
...

Quoted 1 line

Would that work?

... or just drop it. The commit log typically describes only what's happening in this commit or links to prior commits. Future commit references are unusual.

On Fri, 2023-11-17 at 13:47 -0800, Alexei Starovoitov wrote:
[...]

Quoted 11 lines

Quoted 10 lines

This is patch #3, and actual changes are in patch #6, I can change it to:

A follow-up patch "bpf: verify callbacks as if they are called unknown number of times" changes logic for callbacks handling. While previously callbacks were verified as a single function call, new scheme takes into account that callbacks could be executed unknown number of times.
...

Would that work?

Quoted 3 lines

... or just drop it. The commit log typically describes only what's happening in this commit or links to prior commits. Future commit references are unusual.

But there needs to be some justification.
Since this is not a test, maybe move it after patch #6 and refer to a changes from a previous commit?

Split check_reg_arg() into two utility functions:
- check_reg_arg() operating on registers from current verifier state;
- __check_reg_arg() operating on a specific set of registers passed as a parameter;

The __check_reg_arg() function would be used by a follow-up change for callbacks handling.

Signed-off-by Eduard Zingerman <[email protected]>

---
 kernel/bpf/verifier.c | 19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)

Move code for simulated stack frame creation to a separate utility function. This function would be used in the follow-up change for callbacks handling.

Signed-off-by Eduard Zingerman <[email protected]>

---
 kernel/bpf/verifier.c | 87 +++++++++++++++++++++++++------------------
 1 file changed, 51 insertions(+), 36 deletions(-)

kernel/bpf/verifier.c +16 -5

index 0576fc1ddc4d..d9513fd58c7c 100644
@@ -9542,11 +9542,10 @@ static int set_callee_state(struct bpf_verifier_env *env,
                            struct bpf_func_state *caller,
                            struct bpf_func_state *callee, int insn_idx);
 
-static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
-                            int *insn_idx, int subprog,
-                            set_callee_state_fn set_callee_state_cb)
+static int setup_func_entry(struct bpf_verifier_env *env, int subprog, int callsite,
+                           set_callee_state_fn set_callee_state_cb,
+                           struct bpf_verifier_state *state)
 {
-       struct bpf_verifier_state *state = env->cur_state;
        struct bpf_func_state *caller, *callee;
        int err;
 

@@ -9556,13 +9555,56 @@ static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn
                return -E2BIG;
        }
 
-       caller = state->frame[state->curframe];
        if (state->frame[state->curframe + 1]) {
                verbose(env, "verifier bug. Frame %d already allocated\n",
                        state->curframe + 1);
                return -EFAULT;
        }
 
+       caller = state->frame[state->curframe];
+       callee = kzalloc(sizeof(*callee), GFP_KERNEL);
+       if (!callee)
+               return -ENOMEM;
+       state->frame[state->curframe + 1] = callee;
+
+       /* callee cannot access r0, r6 - r9 for reading and has to write
+        * into its own stack before reading from it.
+        * callee can read/write into caller's stack
+        */
+       init_func_state(env, callee,
+                       /* remember the callsite, it will be used by bpf_exit */
+                       callsite,

kernel/bpf/verifier.c +12 -0

+
+       /* only increment it after check_reg_arg() finished */
+       state->curframe++;
+
+       return 0;
+
+err_out:
+       free_func_state(callee);
+       state->frame[state->curframe + 1] = NULL;
+       return err;
+}
+

kernel/bpf/verifier.c static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 9586

Quoted 8 lines

kernel/bpf/verifier.c +8 -0

+       /* Transfer references to the callee */
+       err = copy_reference_state(callee, caller);
+       if (err)
+               goto err_out;
+
+       err = set_callee_state_cb(env, caller, callee, callsite);
+       if (err)
+               goto err_out;

given we are touching and moving this code, it might make sense to make it a bit more succinct with this pattern:

err = copy_reference_state(...);
err = err ?: set_callee_state_cb();
if (err)

    goto err_out;

Error handling is a bit less distracting this way.

Prior to this patch callbacks were handled as regular function calls, execution of callback body was modeled exactly once.
This patch updates callbacks handling logic as follows:
- introduces a function push_callback_call() that schedules callback body verification in env->head stack;
- updates prepare_func_exit() to reschedule callback body verification upon BPF_EXIT;
- as calls to bpf_*_iter_next(), calls to callback invoking functions are marked as checkpoints;
- is_state_visited() is updated to stop callback based iteration when some identical parent state is found.

Paths with callback function invoked zero times are now verified first, which leads to necessity to modify some selftests:
- the following negative tests required adding release/unlock/drop calls to avoid previously masked unrelated error reports:
- cb_refs.c:underflow_prog
- exceptions_fail.c:reject_rbtree_add_throw
- exceptions_fail.c:reject_with_cp_reference
- the following precision tracking selftests needed change in expected log trace:
- verifier_subprog_precision.c:callback_result_precise
(note: r0 precision is no longer propagated inside callback and
I think this is a correct behavior)
- verifier_subprog_precision.c:parent_callee_saved_reg_precise_with_callback
- verifier_subprog_precision.c:parent_stack_slot_precise_with_callback

Reported-by Andrew Werner <[email protected]>

Closes https://lore.kernel.org/bpf/CA+vRuzPChFNXmouzGG+wsy=6eMcfr1mFG0F3g7rbg-sedGKW3w@mail.gmail.com/ open here

Signed-off-by Eduard Zingerman <[email protected]>

---
 include/linux/bpf_verifier.h                  |   5 +
 kernel/bpf/verifier.c                         | 257 +++++++++++-------
 .../selftests/bpf/prog_tests/cb_refs.c        |   4 +-
 tools/testing/selftests/bpf/progs/cb_refs.c   |   1 +
 .../selftests/bpf/progs/exceptions_fail.c     |   2 +
 .../bpf/progs/verifier_subprog_precision.c    |  22 +-
 6 files changed, 183 insertions(+), 108 deletions(-)

kernel/bpf/verifier.c +2 -0

+static bool is_callback_iter_next(struct bpf_verifier_env *env, int insn_idx);
+
 /* For given verifier state backtrack_insn() is called from the last insn to
  * the first insn. Its purpose is to compute a bitmask of registers and
  * stack slots that needs precision in the parent verifier state.

kernel/bpf/verifier.c +0 -0

                        /* callback-calling helper or kfunc call, which means
                         * we are exiting from subprog, but unlike the subprog
                         * call handling above, we shouldn't propagate

kernel/bpf/verifier.c +9 -0

+               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+                                        set_rbtree_add_callback_state);
+               if (err) {
+                       verbose(env, "kfunc %s#%d failed callback verification\n",
+                               func_name, meta.func_id);
+                       return err;
+               }
+       }
+

tools/testing/selftests/bpf/prog_tests/cb_refs.c +2 -0

        struct bpf_program *prog;
        struct cb_refs *skel;
        int i;
 
        for (i = 0; i < ARRAY_SIZE(cb_refs_tests); i++) {
+               if (!test__start_subtest(cb_refs_tests[i].prog_name))
+                       continue;
                LIBBPF_OPTS(bpf_test_run_opts, run_opts,
                        .data_in = &pkt_v4,
                        .data_size_in = sizeof(pkt_v4),

tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +0 -0

index db6b3143338b..ead358679fe2 100644
@@ -120,14 +120,12 @@ __naked int global_subprog_result_precise(void)
 SEC("?raw_tp")
 __success __log_level(2)
 __msg("14: (0f) r1 += r6")

tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +0 -0

 __naked int callback_result_precise(void)
 {
        asm volatile (

Quoted 8 lines

kernel/bpf/verifier.c +2 -0

+static bool is_callback_iter_next(struct bpf_verifier_env *env, int insn_idx);
+
 /* For given verifier state backtrack_insn() is called from the last insn to
  * the first insn. Its purpose is to compute a bitmask of registers and
  * stack slots that needs precision in the parent verifier state.

@@ -4030,10 +4044,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                                        return -EFAULT;
                                return 0;

kernel/bpf/verifier.c static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx, · line 4047

Quoted 6 lines

kernel/bpf/verifier.c +1 -4

                        }
-               } else if ((bpf_helper_call(insn) &&
-                           is_callback_calling_function(insn->imm) &&
-                           !is_async_callback_calling_function(insn->imm)) ||
-                          (bpf_pseudo_kfunc_call(insn) && is_callback_calling_kfunc(insn->imm))) {
+               } else if (is_sync_callback_calling_insn(insn) && idx != subseq_idx - 1) {

can you leave a comment why we need idx != subseq_idx - 1 check?

Quoted 3 lines

kernel/bpf/verifier.c +0 -0

                        /* callback-calling helper or kfunc call, which means
                         * we are exiting from subprog, but unlike the subprog
                         * call handling above, we shouldn't propagate

[...]

Quoted 4 lines

kernel/bpf/verifier.c +0 -0

@@ -12176,6 +12216,21 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
                return -EACCES;
        }
 

kernel/bpf/verifier.c static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, · line 12224

Quoted 6 lines

kernel/bpf/verifier.c +6 -0

+       /* Check the arguments */
+       err = check_kfunc_args(env, &meta, insn_idx);
+       if (err < 0)
+               return err;
+
+       if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) {

can't we use is_sync_callback_calling_kfunc() here?

Quoted 9 lines

kernel/bpf/verifier.c +9 -0

+               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+                                        set_rbtree_add_callback_state);
+               if (err) {
+                       verbose(env, "kfunc %s#%d failed callback verification\n",
+                               func_name, meta.func_id);
+                       return err;
+               }
+       }
+

Quoted 4 lines

tools/testing/selftests/bpf/prog_tests/cb_refs.c +0 -0

index 3bff680de16c..b5aa168889c1 100644

tools/testing/selftests/bpf/prog_tests/cb_refs.c void test_cb_refs(void) · line 24

Quoted 6 lines

tools/testing/selftests/bpf/prog_tests/cb_refs.c +1 -1

@@ -21,12 +21,14 @@ void test_cb_refs(void)
 {
        LIBBPF_OPTS(bpf_object_open_opts, opts, .kernel_log_buf = log_buf,
                                                .kernel_log_size = sizeof(log_buf),
-                                               .kernel_log_level = 1);
+                                               .kernel_log_level = 1 | 2 | 4);

nit: 1 is redundant if 2 is specified, so just 2 | 4 ?

Quoted 14 lines

tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +1 -1

index db6b3143338b..ead358679fe2 100644
@@ -120,14 +120,12 @@ __naked int global_subprog_result_precise(void)
 SEC("?raw_tp")
 __success __log_level(2)
 __msg("14: (0f) r1 += r6")
-__msg("mark_precise: frame0: last_idx 14 first_idx 10")
+__msg("mark_precise: frame0: last_idx 14 first_idx 9")
 __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
 __msg("mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4")
 __msg("mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4")
 __msg("mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0")

tools/testing/selftests/bpf/progs/verifier_subprog_precision.c __naked int global_subprog_result_precise(void) · line 128

Quoted 4 lines

tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +1 -3

-__msg("mark_precise: frame0: parent state regs=r0 stack=:")
-__msg("mark_precise: frame0: last_idx 18 first_idx 0")
-__msg("mark_precise: frame0: regs=r0 stack= before 18: (95) exit")
+__msg("mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop")

you are right that r0 returned from bpf_loop is not r0 returned from bpf_loop's callback, but we still have to go through callback instructions, right?

so you removed few __msg() from subprog
instruction history because it was too long a history or what? I'd actually keep those but update that in subprog we don't need r0 to be precise, that will make this test even clearer

Quoted 1 line

tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +0 -0

 __naked int callback_result_precise(void)

On Fri, 2023-11-17 at 11:46 -0500, Andrii Nakryiko wrote:
[...]

Quoted 8 lines

Quoted 8 lines

kernel/bpf/verifier.c +2 -0

+static bool is_callback_iter_next(struct bpf_verifier_env *env, int insn_idx);
+
 /* For given verifier state backtrack_insn() is called from the last insn to
  * the first insn. Its purpose is to compute a bitmask of registers and
  * stack slots that needs precision in the parent verifier state.

@@ -4030,10 +4044,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
                                        return -EFAULT;
                                return 0;

Quoted 8 lines

kernel/bpf/verifier.c static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx, · line 4047

Quoted 6 lines

kernel/bpf/verifier.c +1 -4

                        }
-               } else if ((bpf_helper_call(insn) &&
-                           is_callback_calling_function(insn->imm) &&
-                           !is_async_callback_calling_function(insn->imm)) ||
-                          (bpf_pseudo_kfunc_call(insn) && is_callback_calling_kfunc(insn->imm))) {
+               } else if (is_sync_callback_calling_insn(insn) && idx != subseq_idx - 1) {

can you leave a comment why we need idx != subseq_idx - 1 check?

This check is needed to make sure that we on the arc from callback return to callback calling function, I'll extend the comment below.

Quoted 11 lines

Quoted 4 lines

kernel/bpf/verifier.c +0 -0

                        /* callback-calling helper or kfunc call, which means
                         * we are exiting from subprog, but unlike the subprog
                         * call handling above, we shouldn't propagate

[...]

Quoted 4 lines

kernel/bpf/verifier.c +0 -0

@@ -12176,6 +12216,21 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
                return -EACCES;
        }
 

Quoted 8 lines

kernel/bpf/verifier.c static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, · line 12224

Quoted 6 lines

kernel/bpf/verifier.c +6 -0

+       /* Check the arguments */
+       err = check_kfunc_args(env, &meta, insn_idx);
+       if (err < 0)
+               return err;
+
+       if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) {

can't we use is_sync_callback_calling_kfunc() here?

No, because it uses 'set_rbtree_add_callback_state' as a parameter, specific to rbtree_add, not just any kfunc.

Quoted 9 lines

Quoted 9 lines

kernel/bpf/verifier.c +9 -0

+               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+                                        set_rbtree_add_callback_state);
+               if (err) {
+                       verbose(env, "kfunc %s#%d failed callback verification\n",
+                               func_name, meta.func_id);
+                       return err;
+               }
+       }
+

[...]

Quoted 4 lines

Quoted 4 lines

tools/testing/selftests/bpf/prog_tests/cb_refs.c +0 -0

index 3bff680de16c..b5aa168889c1 100644

Quoted 8 lines

tools/testing/selftests/bpf/prog_tests/cb_refs.c void test_cb_refs(void) · line 24

Quoted 6 lines

tools/testing/selftests/bpf/prog_tests/cb_refs.c +1 -1

@@ -21,12 +21,14 @@ void test_cb_refs(void)
 {
        LIBBPF_OPTS(bpf_object_open_opts, opts, .kernel_log_buf = log_buf,
                                                .kernel_log_size = sizeof(log_buf),
-                                               .kernel_log_level = 1);
+                                               .kernel_log_level = 1 | 2 | 4);

nit: 1 is redundant if 2 is specified, so just 2 | 4 ?

This is a leftover, sorry, I'll remove changes to cb_refs.c.

[...]

Quoted 14 lines

Quoted 14 lines

tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +1 -1

index db6b3143338b..ead358679fe2 100644
@@ -120,14 +120,12 @@ __naked int global_subprog_result_precise(void)
 SEC("?raw_tp")
 __success __log_level(2)
 __msg("14: (0f) r1 += r6")
-__msg("mark_precise: frame0: last_idx 14 first_idx 10")
+__msg("mark_precise: frame0: last_idx 14 first_idx 9")
 __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
 __msg("mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4")
 __msg("mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4")
 __msg("mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0")

Quoted 8 lines

tools/testing/selftests/bpf/progs/verifier_subprog_precision.c __naked int global_subprog_result_precise(void) · line 128

Quoted 4 lines

tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +1 -3

-__msg("mark_precise: frame0: parent state regs=r0 stack=:")
-__msg("mark_precise: frame0: last_idx 18 first_idx 0")
-__msg("mark_precise: frame0: regs=r0 stack= before 18: (95) exit")
+__msg("mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop")

you are right that r0 returned from bpf_loop is not r0 returned from bpf_loop's callback, but we still have to go through callback instructions, right?

Should we? We are looking to make r0 precise, but what are the rules for propagating that across callback boundary?

For bpf_loop() and for bpf_for_each_map_elem() that would be marking r0 inside callback as precise, but in general that is callback specific.

In a separate discussion with you and Alexei you mentioned that you are going to send a patch-set that would force all r0 precise on exit, which would cover current situation. Imo, it would make sense to wait for that patch-set, as it would be simpler than changes in backtrack_insn(), wdyt?

Quoted 7 lines

so you removed few __msg() from subprog
instruction history because it was too long a history or what? I'd actually keep those but update that in subprog we don't need r0 to be precise, that will make this test even clearer

Quoted 1 line

tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +0 -0

 __naked int callback_result_precise(void)

Here is relevant log fragment:

14: (0f) r1 += r6
mark_precise: frame0: last_idx 14 first_idx 9 subseq_idx -1
mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7
mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4
mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4
mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0
mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop#181
15: R1_w=map_value(off=0,ks=4,vs=16,smin=smin32=0,smax=umax=smax32=umax32=12,var_off=(0x0; 0xc))

    R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=12,var_off=(0x0; 0xc))
15: (61) r0 = *(u32 *)(r1 +0)         ; R0_w=scalar(smin=0,smax=umax=4294967295,var_off=(0x0; 0xffffffff))
                                        R1_w=map_value(off=0,ks=4,vs=16,smin=smin32=0,smax=umax=smax32=umax32=12,var_off=(0x0; 0xc))

16: (95) exit

Quoted 6 lines

Quoted 3 lines

you are right that r0 returned from bpf_loop is not r0 returned from bpf_loop's callback, but we still have to go through callback instructions, right?

Should we? We are looking to make r0 precise, but what are the rules for propagating that across callback boundary?

rules are that r0 in parent frame stays marked as precise, then when we go into child (subprog) frame, we clear r0 *for that frame*,

So I assume this is the case where bpf_loop callback is not executed at all, right? What I'm asking is to keep log expectation where callback *is* executed once, so that we can validate that r0 in the caller is not propagated to callback through callback_calling helpers (like bpf_loop).

A set of test cases to check behavior of callback handling logic, check if verifier catches the following situations:
- program not safe on second callback iteration;
- program not safe on zero callback iterations;
- infinite loop inside a callback.

Verify that callback logic works for bpf_loop, bpf_for_each_map_elem, bpf_user_ringbuf_drain, bpf_find_vma.

Signed-off-by Eduard Zingerman <[email protected]>

---
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../bpf/progs/verifier_iterating_callbacks.c  | 147 ++++++++++++++++++
 2 files changed, 149 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c

Callbacks are similar to open coded iterators, so add imprecise widening logic for callback body processing. This makes callback based loops behave identically to open coded iterators, e.g. allowing to verify programs like below:

  struct ctx { u32 i; };
  int cb(u32 idx, struct ctx* ctx)
  {
          ++ctx->i;
          return 0;
  }
  ...
  struct ctx ctx = { .i = 0 };
  bpf_loop(100, cb, &ctx, 0);
  ...

Signed-off-by Eduard Zingerman <[email protected]>

---
 kernel/bpf/verifier.c | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

A test case to verify that imprecise scalars widening is applied to callback bodies on repetative iteration.

Signed-off-by Eduard Zingerman <[email protected]>

---
 .../bpf/progs/verifier_iterating_callbacks.c  | 20 +++++++++++++++++++
 1 file changed, 20 insertions(+)

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +8 -0

index fa9429f77a81..598c1e984b26 100644
@@ -25,6 +25,7 @@ struct buf_context {
 
 struct num_context {
        __u64 i;
+       __u64 j;
 };
 
 __u8 choice_arr[2] = { 0, 1 };

@@ -69,6 +70,25 @@ int unsafe_on_zero_iter(void *unused)
        return choice_arr[loop_ctx.i];
 }
 
+static int widening_cb(__u32 idx, struct num_context *ctx)
+{
+       ++ctx->i;
+       return 0;
+}
+
+SEC("?raw_tp")

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +2 -1

+}
+
 static int loop_detection_cb(__u32 idx, struct num_context *ctx)
 {
        for (;;) {}
--

2.42.0

Quoted 3 lines · Eduard Zingerman

A test case to verify that imprecise scalars widening is applied to callback bodies on repetative iteration.

typo: repetitive? repeating? successive? subsequent?

Quoted 12 lines

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +12 -0

+static int widening_cb(__u32 idx, struct num_context *ctx)
+{
+       ++ctx->i;
+       return 0;
+}
+
+SEC("?raw_tp")
+__success
+int widening(void *unused)
+{
+       struct num_context loop_ctx = { .i = 0, .j = 1 };
+

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c int unsafe_on_zero_iter(void *unused) · line 89

Quoted 5 lines

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +5 -0

+       bpf_loop(100, widening_cb, &loop_ctx, 0);
+       /* loop_ctx.j is not changed during callback iteration,
+        * verifier should not apply widening to it.
+        */
+       return choice_arr[loop_ctx.j];

would the test be a bit more interesting if you use loop_ctx.i here? return choice_arr[loop_ctx.i & 1]; ?

Quoted 3 lines

(quoted diff) +2 -0

+}
+

Quoted 6 lines · Andrii Nakryiko

Quoted 3 lines · Eduard Zingerman

A test case to verify that imprecise scalars widening is applied to callback bodies on repetative iteration.

typo: repetitive? repeating? successive? subsequent?

I'll configure spell-checking, I promise.

[...]

Quoted 12 lines

Quoted 12 lines

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +12 -0

+static int widening_cb(__u32 idx, struct num_context *ctx)
+{
+       ++ctx->i;
+       return 0;
+}
+
+SEC("?raw_tp")
+__success
+int widening(void *unused)
+{
+       struct num_context loop_ctx = { .i = 0, .j = 1 };
+

Quoted 8 lines

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c int unsafe_on_zero_iter(void *unused) · line 89

Quoted 5 lines

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +5 -0

+       bpf_loop(100, widening_cb, &loop_ctx, 0);
+       /* loop_ctx.j is not changed during callback iteration,
+        * verifier should not apply widening to it.
+        */
+       return choice_arr[loop_ctx.j];

would the test be a bit more interesting if you use loop_ctx.i here? return choice_arr[loop_ctx.i & 1]; ?

It would force precision for 'loop_ctx.i', precise values are not widened.

Quoted 4 lines

Quoted 4 lines

(quoted diff) +2 -0

+}
+

In some cases verifier can't infer convergence of the bpf_loop() iteration. E.g. for the following program:

    static int cb(__u32 idx, struct num_context* ctx)
    {
        ctx->i++;
        return 0;
    }

    SEC("?raw_tp")
    int prog(void *_)
    {
        struct num_context ctx = { .i = 0 };
        __u8 choice_arr[2] = { 0, 1 };

        bpf_loop(2, cb, &ctx, 0);
        return choice_arr[ctx.i];
    }

Each 'cb' simulation would eventually return to 'prog' and reach 'return choice_arr[ctx.i]' statement. At which point ctx.i would be marked precise, thus forcing verifier to track multitude of separate states with {.i=0}, {.i=1}, ... at bpf_loop() callback entry.

This commit allows "brute force" handling for such cases by limiting number of callback body simulations using 'umax' value of the first bpf_loop() parameter.

For this, extend bpf_func_state with 'callback_depth' field. Increment this field when callback visiting state is pushed to states traversal stack. For frame #N it's 'callback_depth' field counts how many times callback with frame depth N+1 had been executed. Use bpf_func_state specifically to allow independent tracking of callback depths when multiple nested bpf_loop() calls are present.

Signed-off-by Eduard Zingerman <[email protected]>

---
 include/linux/bpf_verifier.h |  9 +++++++++
 kernel/bpf/verifier.c        | 12 ++++++++++--
 2 files changed, 19 insertions(+), 2 deletions(-)

include/linux/bpf_verifier.h +9 -0

index 0ffb479c72d8..302f9c310de7 100644
@@ -301,6 +301,15 @@ struct bpf_func_state {
        struct tnum callback_ret_range;
        bool in_async_callback_fn;
        bool in_exception_callback_fn;
+       /* For callback calling functions that limit number of possible
+        * callback executions (e.g. bpf_loop) keeps track of current
+        * simulated iteration number. When non-zero either:
+        * - current frame has a child frame, in such case it's callsite points
+        *   to callback calling function;
+        * - current frame is a topmost frame, in such case callback has just
+        *   returned and env->insn_idx points to callback calling function.
+        */
+       u32 callback_depth;
 
        /* The following fields should be last. See copy_func_state() */
        int acquired_refs;

kernel/bpf/verifier.c +2 -0

index 5b8c0ebcb4f6..474af277ea54 100644
@@ -9680,6 +9680,8 @@ static int push_callback_call(struct bpf_verifier_env *env, struct bpf_insn *ins
                return err;
 
        callback_state->callback_iter_depth++;
+       callback_state->frame[callback_state->curframe - 1]->callback_depth++;
+       caller->callback_depth = 0;
        return 0;
 }
 

kernel/bpf/verifier.c +4 -1

+                       err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+                                                set_loop_callback_state);
+               else
+                       cur_func(env)->callback_depth = 0;
                break;
        case BPF_FUNC_dynptr_from_mem:
                if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
--

2.42.0

Quoted 8 lines

kernel/bpf/verifier.c +2 -2

@@ -10479,8 +10481,14 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
                break;
        case BPF_FUNC_loop:
                update_loop_inline_state(env, meta.subprogno);
-               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
-                                        set_loop_callback_state);
+               if (env->log.level & BPF_LOG_LEVEL2)
+                       verbose(env, "frame%d callback_depth=%u\n",

kernel/bpf/verifier.c static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 10487

Quoted 2 lines

kernel/bpf/verifier.c +2 -0

+                               env->cur_state->curframe, cur_func(env)->callback_depth);
+               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)

I haven't had time to look at the patch set properly yet and I'm not sure if I'll have time today. But one thing that I randomly realized is that if you are taking umax_value into account then this BPF_REG_1 has to be precise, so please make sure to mark_chain_precision() on it first.

In some cases verifier can't infer convergence of the bpf_loop() iteration. E.g. for the following program:

    static int cb(__u32 idx, struct num_context* ctx)
    {
        ctx->i++;
        return 0;
    }

    SEC("?raw_tp")
    int prog(void *_)
    {
        struct num_context ctx = { .i = 0 };
        __u8 choice_arr[2] = { 0, 1 };

        bpf_loop(2, cb, &ctx, 0);
        return choice_arr[ctx.i];
    }

Each 'cb' simulation would eventually return to 'prog' and reach 'return choice_arr[ctx.i]' statement. At which point ctx.i would be marked precise, thus forcing verifier to track multitude of separate states with {.i=0}, {.i=1}, ... at bpf_loop() callback entry.

This commit allows "brute force" handling for such cases by limiting number of callback body simulations using 'umax' value of the first bpf_loop() parameter.

For this, extend bpf_func_state with 'callback_depth' field. Increment this field when callback visiting state is pushed to states traversal stack. For frame #N it's 'callback_depth' field counts how many times callback with frame depth N+1 had been executed. Use bpf_func_state specifically to allow independent tracking of callback depths when multiple nested bpf_loop() calls are present.

Signed-off-by Eduard Zingerman <[email protected]>

---
 include/linux/bpf_verifier.h |  9 +++++++++
 kernel/bpf/verifier.c        | 12 ++++++++++--
 2 files changed, 19 insertions(+), 2 deletions(-)

include/linux/bpf_verifier.h +9 -0

index 0ffb479c72d8..302f9c310de7 100644
@@ -301,6 +301,15 @@ struct bpf_func_state {
        struct tnum callback_ret_range;
        bool in_async_callback_fn;
        bool in_exception_callback_fn;
+       /* For callback calling functions that limit number of possible
+        * callback executions (e.g. bpf_loop) keeps track of current
+        * simulated iteration number. When non-zero either:
+        * - current frame has a child frame, in such case it's callsite points
+        *   to callback calling function;
+        * - current frame is a topmost frame, in such case callback has just
+        *   returned and env->insn_idx points to callback calling function.
+        */
+       u32 callback_depth;
 
        /* The following fields should be last. See copy_func_state() */
        int acquired_refs;

kernel/bpf/verifier.c +2 -0

index 5b8c0ebcb4f6..474af277ea54 100644
@@ -9680,6 +9680,8 @@ static int push_callback_call(struct bpf_verifier_env *env, struct bpf_insn *ins
                return err;
 
        callback_state->callback_iter_depth++;
+       callback_state->frame[callback_state->curframe - 1]->callback_depth++;
+       caller->callback_depth = 0;
        return 0;
 }
 

kernel/bpf/verifier.c +0 -1

                break;
        case BPF_FUNC_dynptr_from_mem:
                if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
--

2.42.0

Quoted 5 lines

kernel/bpf/verifier.c +0 -1

@@ -10479,8 +10481,14 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
                break;
        case BPF_FUNC_loop:
                update_loop_inline_state(env, meta.subprogno);
-               err = push_callback_call(env, insn, insn_idx, meta.subprogno,

kernel/bpf/verifier.c static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 10486

Quoted 4 lines

kernel/bpf/verifier.c +3 -1

-                                        set_loop_callback_state);
+               if (env->log.level & BPF_LOG_LEVEL2)
+                       verbose(env, "frame%d callback_depth=%u\n",
+                               env->cur_state->curframe, cur_func(env)->callback_depth);

btw, is this a debugging leftover or intentional? If the latter, why is it done only for bpf_loop()? Maybe push_callback_call() be a better place for it?

kernel/bpf/verifier.c static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 10491

Quoted 6 lines

kernel/bpf/verifier.c +5 -0

+               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
+                       err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+                                                set_loop_callback_state);
+               else
+                       cur_func(env)->callback_depth = 0;

I guess it's actually a bit more interesting to know that we stopped iterating because umax is reached. But I'm actually not sure whether we should be adding these logs at all, though I don't have a strong preference.

On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
[...]

Quoted 5 lines

Quoted 5 lines

kernel/bpf/verifier.c +0 -1

@@ -10479,8 +10481,14 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
                break;
        case BPF_FUNC_loop:
                update_loop_inline_state(env, meta.subprogno);
-               err = push_callback_call(env, insn, insn_idx, meta.subprogno,

Quoted 8 lines

kernel/bpf/verifier.c static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 10486

Quoted 4 lines

kernel/bpf/verifier.c +3 -1

-                                        set_loop_callback_state);
+               if (env->log.level & BPF_LOG_LEVEL2)
+                       verbose(env, "frame%d callback_depth=%u\n",
+                               env->cur_state->curframe, cur_func(env)->callback_depth);

btw, is this a debugging leftover or intentional? If the latter, why is it done only for bpf_loop()? Maybe push_callback_call() be a better place for it?

Intentional...

Quoted 11 lines

kernel/bpf/verifier.c static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 10491

Quoted 6 lines

kernel/bpf/verifier.c +5 -0

+               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
+                       err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+                                                set_loop_callback_state);
+               else
+                       cur_func(env)->callback_depth = 0;

I guess it's actually a bit more interesting to know that we stopped iterating because umax is reached. But I'm actually not sure whether we should be adding these logs at all, though I don't have a strong preference.

... it is not obvious to infer current depth looking at the log, so I think something should be printed. Note about stopped iteration sounds good, and it could be placed here, not in the push_callback_call(), e.g.:

               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
                       err = push_callback_call(env, insn, insn_idx, meta.subprogno,
                                                set_loop_callback_state);
               else {
                       cur_func(env)->callback_depth = 0;
                       if (env->log.level & BPF_LOG_LEVEL2)
                               verbose(env, "bpf_loop iteration limit reached\n");
               }

wdyt?

Add an ability to specify messages that should not be found in the test verifier log. Similar to LLVM's FileCheck tool for the following test specification:

    __success
    __msg("a")
    __not_msg("b")
    __msg("c")
    void foo(...) { ... }

- message "a" is expected to be in the log;
- message "b" is not expected after message "a" (but could be present before "a");
- message "c" is expected to be in the log after message "a".

Signed-off-by Eduard Zingerman <[email protected]>

---
 tools/testing/selftests/bpf/progs/bpf_misc.h |  9 +++
 tools/testing/selftests/bpf/test_loader.c    | 82 ++++++++++++++------
 2 files changed, 68 insertions(+), 23 deletions(-)

tools/testing/selftests/bpf/progs/bpf_misc.h +0 -0

index 799fff4995d8..f24fcda6fc0b 100644

tools/testing/selftests/bpf/progs/bpf_misc.h +0 -0

  *
  * __success         Expect program load success in privileged mode.
  * __success_unpriv  Expect program load success in unprivileged mode.

tools/testing/selftests/bpf/progs/bpf_misc.h +0 -0

 #define __failure_unpriv       __attribute__((btf_decl_tag("comment:test_expect_failure_unpriv")))
 #define __success_unpriv       __attribute__((btf_decl_tag("comment:test_expect_success_unpriv")))
 #define __log_level(lvl)       __attribute__((btf_decl_tag("comment:test_log_level="#lvl)))

tools/testing/selftests/bpf/test_loader.c +0 -0

index 37ffa57f28a1..def16d9aeae2 100644

        if (!tmp) {
                ASSERT_FAIL("failed to realloc memory for messages\n");
                return -ENOMEM;
        }
        subspec->expect_msgs = tmp;

tools/testing/selftests/bpf/test_loader.c +3 -1

-       subspec->expect_msgs[subspec->expect_msg_cnt++] = msg;
+       subspec->expect_msgs[cnt].str = msg;
+       subspec->expect_msgs[cnt].expected = expected;
+       subspec->expect_msg_cnt++;
 
        return 0;
 }

I think this implementation has an undesired surprising behavior. Imagine you have a log like this:

A
C
D
B

And you specify

__msg("A")
__nomsg("B")
__msg("C")
__msg("D")
__msg("B")

Log matches the spec, right? But your implementation will eagerly reject it.

I think you can implement more coherent behavior if you only strstr() __msg() specs, skipping __nomsg() first. But on each __msg one, if successful, you go back and validate that there are no matches for all __nomsg() specs that you skipped, taking into account matched positions for current __msg() and last __msg() (or the start of the log, of course).

Not sure if I explained clearly, but the idea is to postpone __nomsg() until we anchor ourselves between two __msg()s. And beginning/end of verifier log are two other anchoring positions.

On Fri, 2023-11-17 at 11:45 -0500, Andrii Nakryiko wrote:
[...]

Quoted 26 lines

I think this implementation has an undesired surprising behavior. Imagine you have a log like this:

A
C
D
B

And you specify

__msg("A")
__nomsg("B")
__msg("C")
__msg("D")
__msg("B")

Log matches the spec, right? But your implementation will eagerly reject it.

I think you can implement more coherent behavior if you only strstr() __msg() specs, skipping __nomsg() first. But on each __msg one, if successful, you go back and validate that there are no matches for all __nomsg() specs that you skipped, taking into account matched positions for current __msg() and last __msg() (or the start of the log, of course).

Quoted 3 lines

Not sure if I explained clearly, but the idea is to postpone __nomsg() until we anchor ourselves between two __msg()s. And beginning/end of verifier log are two other anchoring positions.

Yes, makes total sense, thank you for spotting it. I can fix this and submit this patch as an unrelated change or just drop it, what would you prefer?

Quoted 15 lines

Quoted 15 lines

I think this implementation has an undesired surprising behavior. Imagine you have a log like this:

A
C
D
B

And you specify

__msg("A")
__nomsg("B")
__msg("C")
__msg("D")
__msg("B")

I think it's useful in general, I believe I had few cases where this would be helpful. So submitting separately makes sense. But I think this patch set doesn't need it if we can validate logic in last patch without relying on this feature.

On Fri, 2023-11-17 at 15:31 -0500, Andrii Nakryiko wrote:
[...]

Quoted 15 lines

Quoted 15 lines

Quoted 15 lines

I think this implementation has an undesired surprising behavior. Imagine you have a log like this:

A
C
D
B

And you specify

__msg("A")
__nomsg("B")
__msg("C")
__msg("D")
__msg("B")

[...]

Quoted 4 lines

I think it's useful in general, I believe I had few cases where this would be helpful. So submitting separately makes sense. But I think this patch set doesn't need it if we can validate logic in last patch without relying on this feature.

Ok, will do it separately. While at it can also add two more features:
- __msg_next, again mimicking FileCheck [0], which would require match to be on a line subsequent to previous match;
- __msg_re, with support for regular expressions (using [1]).

[0] https://llvm.org/docs/CommandGuide/FileCheck.html
[1] https://www.gnu.org/software/libc/manual/html_node/Regular-Expressions.html

Check that even if bpf_loop() callback simulation does not converge to a specific state, verification could proceed via "brute force" simulation of maximal number of callback calls.

Signed-off-by Eduard Zingerman <[email protected]>

---
 .../bpf/progs/verifier_iterating_callbacks.c  | 67 +++++++++++++++++++
 1 file changed, 67 insertions(+)

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +47 -0

index 598c1e984b26..da10ce57da5e 100644
@@ -164,4 +164,71 @@ int unsafe_find_vma(void *unused)
        return choice_arr[loop_ctx.i];
 }
 
+static int iter_limit_cb(__u32 idx, struct num_context *ctx)
+{
+       ctx->i++;
+       return 0;
+}
+
+SEC("?raw_tp")
+__success
+int bpf_loop_iter_limit_ok(void *unused)
+{
+       struct num_context ctx = { .i = 0 };
+
+       bpf_loop(1, iter_limit_cb, &ctx, 0);
+       return choice_arr[ctx.i];
+}
+
+SEC("?raw_tp")
+__failure __msg("invalid access to map value, value_size=2 off=2 size=1")
+int bpf_loop_iter_limit_overflow(void *unused)
+{
+       struct num_context ctx = { .i = 0 };
+
+       bpf_loop(2, iter_limit_cb, &ctx, 0);
+       return choice_arr[ctx.i];
+}
+
+static int iter_limit_level2a_cb(__u32 idx, struct num_context *ctx)
+{
+       ctx->i += 100;
+       return 0;
+}
+
+static int iter_limit_level2b_cb(__u32 idx, struct num_context *ctx)
+{
+       ctx->i += 10;
+       return 0;
+}
+
+static int iter_limit_level1_cb(__u32 idx, struct num_context *ctx)
+{
+       ctx->i += 1;
+       bpf_loop(1, iter_limit_level2a_cb, ctx, 0);
+       bpf_loop(1, iter_limit_level2b_cb, ctx, 0);
+       return 0;
+}
+
+SEC("?raw_tp")

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +10 -1

+int bpf_loop_iter_limit_nested(void *unused)
+{
+       struct num_context ctx = { .i = 0 };
+
+       bpf_loop(1, iter_limit_level1_cb, &ctx, 0);
+       ctx.i *= 1000;
+       bpf_loop(1, iter_limit_level1_cb, &ctx, 0);
+       return choice_arr[ctx.i % 2];
+}
+
 char _license[] SEC("license") = "GPL";
--

2.42.0

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c int unsafe_find_vma(void *unused) · line 223

Quoted 11 lines

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +11 -0

+SEC("?raw_tp")
+__success __log_level(2)
+/* Check that last verified exit from the program visited each
+ * callback expected number of times: one visit per callback for each
+ * top level bpf_loop call.
+ */
+__msg("r1 = *(u64 *)(r10 -16)       ; R1_w=111111 R10=fp0 fp-16=111111")
+/* Ensure that read above is the last one by checking that there are
+ * no more reads for ctx.i.
+ */
+__not_msg("r1 = *(u64 *)(r10 -16)      ; R1_w=")

can't you enforce that we don't go above 111111 just by making sure to use r1 - 111111 + 1 as an index into choice_arr()?

We can then simplify the patch set by dropping __not_msg() parts (and can add them separately).

On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
[...]

Quoted 15 lines

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c int unsafe_find_vma(void *unused) · line 223

Quoted 11 lines

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +11 -0

+SEC("?raw_tp")
+__success __log_level(2)
+/* Check that last verified exit from the program visited each
+ * callback expected number of times: one visit per callback for each
+ * top level bpf_loop call.
+ */
+__msg("r1 = *(u64 *)(r10 -16)       ; R1_w=111111 R10=fp0 fp-16=111111")
+/* Ensure that read above is the last one by checking that there are
+ * no more reads for ctx.i.
+ */
+__not_msg("r1 = *(u64 *)(r10 -16)      ; R1_w=")

can't you enforce that we don't go above 111111 just by making sure to use r1 - 111111 + 1 as an index into choice_arr()?

Quoted 2 lines

We can then simplify the patch set by dropping __not_msg() parts (and can add them separately).

Well, r1 could be 0 as well, so idx would be out of bounds. But I like the idea, it is possible to check that r1 is either 00000, 100000, ..., 111111 and do something unsafe otherwise.

Thank you. I'll drop __not_msg() then.

Quoted 3 lines

Well, r1 could be 0 as well, so idx would be out of bounds. But I like the idea, it is possible to check that r1 is either 00000, 100000, ..., 111111 and do something unsafe otherwise.

then why not return choice_arr[r <= 111111 ? (r & 1) : -1]; or something along those lines?