On Tue, 2023-10-03 at 22:50 -0700, Alexei Starovoitov wrote:
> On Tue, Oct 3, 2023 at 7:57 PM Alexei Starovoitov
> <alexei.starovoitov@xxxxxxxxx> wrote:
> >
> > ok. discard that idea.
>
> Attached is a 3rd version of the same idea I argued earlier.
> Let normal DFS go as normal,
> do states_equal() on V which has 1 looping branch remain
> and all other explored.
> To achieve that when iter_next() is seen do parent->looping_states += 2;
>
> then when processing any children do parent->looping_states++;
> in the correct parent.
> Since there could be many intermediate states have to walk back
> parentage chain to increment correct parent.
> When the state reaches bpf_exit or safety, walk back
> the parentage chain and do looping_states--.
> The state is ok to use in states_equal() if looping_states==1.
But what if each next iteration spawns more than two looping states?
E.g. for the following example:
0. // full test attached as a patch
1. while (next(i)) {
2. if (random())
3. continue;
4. if (random())
5. continue;
6. if (random())
7. continue;
8. r0 += 0;
9. }
For me it bails out with the following message:
run_subtest:FAIL:unexpected_load_failure unexpected error: -28
....
The sequence of 8193 jumps is too complex.
processed 49161 insns (limit 1000000) max_states_per_insn 4 total_states 2735 peak_states 2735 mark_read 2
(I bumped insn complexity limit back to 1,000,000).
> With this patch all existing iter tests still pass,
> and all Ed's special tests pass or fail as needed.
> Ex: loop_state_deps1 is rejected with misaligned stack,
> loop1 loads with success, num_iter_bug fails with bad pointer.
Are you sure that correct version of the patch was shared?
I get the following log for loop_state_deps1:
run_subtest:FAIL:unexpected_load_success unexpected success: 0
from 21 to 22: safe
...
update_br2 80c0 branches=0/0
processed 75 insns (limit 1000000) max_states_per_insn 2 total_states 29 peak_states 29 mark_read 9
=============
#104/26 iters/loop_state_deps1:FAIL
The test case is marked as safe.
iter_precision_fixed_point{1,2} and num_iter_bug work as expected.
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 019c8dde5fa2..cf9041fac272 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -16821,7 +16821,7 @@ static int do_check(struct bpf_verifier_env *env)
insn = &insns[env->insn_idx];
class = BPF_CLASS(insn->code);
- if (++env->insn_processed > 1000) {//BPF_COMPLEXITY_LIMIT_INSNS) {
+ if (++env->insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) {
verbose(env,
"BPF program is too large. Processed %d insn\n",
env->insn_processed);
diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 9add71d79a3a..f08288c0b74a 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -991,4 +991,42 @@ int num_iter_bug(const void *ctx) {
return 0;
}
+SEC("?raw_tp")
+__success
+__naked int hydra1(void)
+{
+ asm volatile (
+ "r1 = r10;"
+ "r1 += -8;"
+ "r2 = 0;"
+ "r3 = 10;"
+ "call %[bpf_iter_num_new];"
+ "loop_%=:"
+ "r1 = r10;"
+ "r1 += -8;"
+ "call %[bpf_iter_num_next];"
+ "if r0 == 0 goto loop_end_%=;"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 != 42 goto loop_%=;"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 != 42 goto loop_%=;"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 != 42 goto loop_%=;"
+ "r0 += 0;"
+ "goto loop_%=;"
+ "loop_end_%=:"
+ "r1 = r10;"
+ "r1 += -8;"
+ "call %[bpf_iter_num_destroy];"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_get_prandom_u32),
+ __imm(bpf_iter_num_new),
+ __imm(bpf_iter_num_next),
+ __imm(bpf_iter_num_destroy)
+ : __clobber_all
+ );
+}
+
char _license[] SEC("license") = "GPL";
