From: Alexei Starovoitov for (i = 0; i < 64; i++) { if (have) sum += t->pid; t = v->task; /* __kptr: a task or NULL */ have = t && t->prio > 100; } t is loaded anew in each iteration. The first iteration of such a loop is verified on its own, and the states that return to the loop head stand for the other iterations. There have becomes [0, 1], also next to t == NULL: R2 invalid mem access 'scalar' for (i = 0; i < 64; i++) { sum += a[cur]; /* u8 a[16] */ cur = order[i]; /* static const u8 order[64] */ } cur is order[0] after the first iteration and a byte after the next one: R4 unbounded memory access, make sure to bounds check any such access Both load if the verifier goes through the iterations one by one: have goes with t, each order[i] is a constant. It did so before the first iteration was kept apart, and it still does for what a call returns. Do the same for what is loaded and then looked at: t is the base of a load, cur is an offset. A stack slot that the loop fills and that is only copied later is no reason for a walk. test_rbtree_remove_many_noalloc() of libarena is walked again: 22060 -> 27699 insns. Fixes: df9b13a441c9 ("bpf: Keep the first iteration of a counted loop apart") Signed-off-by: Alexei Starovoitov --- kernel/bpf/scev.c | 9 +++++---- kernel/bpf/verifier.c | 2 +- 2 files changed, 6 insertions(+), 5 deletions(-) diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c index 5415fcf9df2f..2a7d0c59f73b 100644 --- a/kernel/bpf/scev.c +++ b/kernel/bpf/scev.c @@ -3749,13 +3749,14 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta } /* * What is loaded from memory or returned by a call in every iteration is the same - * kind of thing in all of them. One iteration tells what. There is nothing more - * to find out when iterations are looked at one by one. But for what goes with it: - * a call returns NULL and a flag is set. So a walk comes first for a call. + * kind of thing in all of them. One iteration tells what. A walk through the + * iterations tells more: what goes with it, like a flag that is set if it's not + * NULL, and each number of a table in .rodata. So a walk comes first. What is + * loaded is often a leftover in a stack slot: not if nothing looks at it. */ if (expr_is_fresh(env, header_env->reg2expr[r], &call)) { __set_bit(r, iters->fresh_regs); - if (!call) + if (!call && !bpf_flow_is_needed(env, insn_idx, r)) continue; } else { __set_bit(r, iters->forget_regs); diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 09a44723bb2e..479c52cc2f56 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -21636,7 +21636,7 @@ int bpf_flow_loop_enter(struct bpf_verifier_env *env, bool *backedge, bool *drop entry->entry_state = entry_state; entry->terminates = true; /* - * idx = 0; for (i = 0; i < 100; i++) idx = table[idx]; + * idx = 0; for (i = 0; i < 100000; i++) idx = table[idx]; * What the loop makes of idx is not known before its body is looked at, and what idx is * at the entry goes with i == 0 only. So the state goes through the first iteration as * it is. The state that comes back to the head has idx in 0..255. -- 2.55.0