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";
