Re: [PATCH v3 bpf-next 1/2] bpf: Relax precision marking in open coded iters and may_goto loop.

[Eduard Zingerman <eddyz87@gmail.com>]

On Tue, 2024-05-28 at 17:34 -0700, Alexei Starovoitov wrote:

[...]

> > I'm not sure how much of a deal-breaker this is, but proposed
> > heuristics precludes verification for the following program:
> 
> not quite.
> 
> >   char arr[10];
> > 
> >   SEC("socket")
> >   __success __flag(BPF_F_TEST_STATE_FREQ)
> >   int simple_loop(const void *ctx)
> >   {
> >         struct bpf_iter_num it;
> >         int *v, sum = 0, i = 0;
> > 
> >         bpf_iter_num_new(&it, 0, 10);
> >         while ((v = bpf_iter_num_next(&it))) {
> >                 if (i < 5)
> >                         sum += arr[i++];
> >         }
> >         bpf_iter_num_destroy(&it);
> >         return sum;
> >   }
> > 
> > The presence of the loop with bpf_iter_num creates a set of states
> > with non-null loop_header, which in turn switches-off predictions for
> > comparison operations inside the loop.
> 
> Is this a pseudo code ?

No, I tried this test with v3 of this patch and on master.
It passes on master and fails with v3.
(Full test in the end of the email, I run it as
 ./test_progs -vvv -a verifier_loops1/simple_loop).

> Because your guess at the reason for the verifier reject is not correct.
> It's signed stuff that is causing issues.
> s/int i/__u32 i/
> and this test is passing the verifier with just 143 insn processed.

I'm reading through verifier log, will get back shortly.

> > This looks like a bad a compose-ability of verifier features to me.
> 
> As with any heuristic there are two steps forward and one step back.
> The heuristic is trying to minimize the size of that step back.
> If you noticed in v1 and v2 I had to add 'if (!v) break;'
> to iter_pragma_unroll_loop().
> And it would have been ok this way.
> It is a step back for a corner case like iter_pragma_unroll_loop().
> Luckily this new algorithm in v3 doesn't need this if (!v) workaround
> anymore. So the step back is minimized.
> Is it still there? Absolutely. There is a chance that some working prog
> will stop working. (as with any verifier change).

Not sure I understand how 'if (!v) break;' is relevant.
The patch says:

+		ignore_pred = (get_loop_entry(this_branch) ||
+			       this_branch->may_goto_depth) &&
+				/* Gate widen_reg() logic */
+				env->bpf_capable;

get_loop_entry(this_branch) would return true for states inside a
'while' because of the bpf_iter_num_next() calls.
Hence, predictions for all conditionals inside the loop would be
ignored and also src/dst registers would be widened because comparison
is not JEQ/JNE.

[...]

> Just like i=zero is magical.
> All such magic has to go. The users should write normal C.

Noted.

---

diff --git a/tools/testing/selftests/bpf/progs/verifier_loops1.c b/tools/testing/selftests/bpf/progs/verifier_loops1.c
index e07b43b78fd2..1ebf0c829d5e 100644
--- a/tools/testing/selftests/bpf/progs/verifier_loops1.c
+++ b/tools/testing/selftests/bpf/progs/verifier_loops1.c
@@ -283,4 +283,22 @@ exit_%=:                                           \
        : __clobber_all);
 }
 
+char arr[10];
+
+SEC("socket")
+__success __flag(BPF_F_TEST_STATE_FREQ)
+int simple_loop(const void *ctx)
+{
+      struct bpf_iter_num it;
+      int *v, sum = 0, i = 0;
+
+      bpf_iter_num_new(&it, 0, 10);
+      while ((v = bpf_iter_num_next(&it))) {
+              if (i < 5)
+                      sum += arr[i++];
+      }
+      bpf_iter_num_destroy(&it);
+      return sum;
+}
+
 char _license[] SEC("license") = "GPL";