From: Alexei Starovoitov A prerequisite of the removal of scalar ids. bpfj_proc_file_open of bpfjailer loads before and after the patch. Today it loads because of a scalar id, and scev.c has no replacement for that id in an irreducible loop: for (int i = BPFJ_MAX_POD_PER_PID - 1; i >= 0; --i) { if (i >= num_pods) { continue; } struct bpfj_pod __arena* pod = actor->pods[i]; That is role_gate.h. i lives on the stack (clang, -mcpu=v4): 171: r1 = *(u64 *)(r10 -40) 172: if w1 > 0x7 goto pc-10 173: r1 = *(u64 *)(r10 -40) 174: r1 <<= 3 The loop is entered at 163 and at 171: 'loop at 171, irreducible' in the level 2 log. scev.c does not support such a loop: nothing is known at its header, its body is not analyzed. The linked registers of a conditional jump, the live registers and stack slots that are a tested register + a constant on every path to the jump, are computed by scev.c. So the jump at 172 has none. Only the scalar id that r1 and fp-40 share bounds what insn 173 fills. The basic block is enough to see that r1 == fp-40 at 172: local value numbering. find_linked_regs_in_bb() visits the basic blocks of unsupported loops, see can_compute_loop_scev(), one by one. At the start of a basic block every live-in register and stack slot is a phi whose operands are not known: fp-40 is %fp-40.171=phi(?). Insn 171 copies that to r1. These expressions are for find_linked_regs() only, the level 2 log does not print them. The verifier adds edges that the CFG does not have: may_goto before a loop header, a subprog that is out of budget, see bpf_head_guard_target(). They lead out of all loops, so a basic block of a loop is entered at its first insn only. Two tests: a link within a basic block is found. What the fall-through predecessor computed is not used: it is not the only predecessor. Signed-off-by: Alexei Starovoitov --- kernel/bpf/scev.c | 52 ++++++++++++++++++- .../selftests/bpf/progs/verifier_scev.c | 13 +++++ 2 files changed, 63 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c index 2792217754be..db60585c00c8 100644 --- a/kernel/bpf/scev.c +++ b/kernel/bpf/scev.c @@ -56,7 +56,8 @@ enum expr_op { * An SSA name for a value that no expression describes: the def of the SCEV register 'reg' * - by the insn at 'idx'. An insn that may write defines too (may_def in liveness.c). A nested loop * defines at its header what it leaves. - * - by a phi before the insn at 'idx': a join point, a loop header. + * - by a phi before the insn at 'idx': a join point, a loop header, in an unsupported loop the + * start of a basic block. * Without its backedges and with nested loops collapsed the body of a loop is acyclic: an insn * executes at most once per iteration, so a def is one value per iteration. A name is unique within * the env of one loop. @@ -650,7 +651,8 @@ static bool expr_next(struct scev *scev, u32 *id, u32 *order) * %fp-8.8? insn 8 may write fp-8. The value is UNKNOWN, '?' without a def * %r8.7=phi(1, 2) the phi of r8 before insn 7 * %r0.7=phi(_) a phi of distinct OPAQUE values - * %r6.9=phi(?) a phi of distinct UNKNOWN values, or of more than 8 values + * %r6.9=phi(?) a phi of distinct UNKNOWN values, or of more than 8 values, or + * a live-in of a basic block * %r2.12=(+ x 4) insn 12 defines r2, see alu64_with_def() * %r2.25=phi((+ x 4)) two adds of one shape, each may have been converted to ALU32: * the phi is not (+ x 4) @@ -1996,6 +1998,49 @@ static int find_linked_regs(struct bpf_verifier_env *env, struct env *e, int h, return 0; } +/* + * for (..) { if (i >= n) ..; pod = actor->pods[i]; .. } + * with i on the stack is 'fill, test, fill again'. clang can emit an irreducible loop for it. + * Unsupported loops, see can_compute_loop_scev(), get local value numbering: a live-in of a basic + * block is a phi whose operands are not known, %r6.9=phi(?). + */ +static int find_linked_regs_in_bb(struct bpf_verifier_env *env) +{ + struct bpf_insn_aux_data *aux = env->insn_aux_data; + struct bpf_insn *insn = env->prog->insnsi; + bool bb_start = true; + int i, h, err = 0; + struct env *e; + u32 r; + + e = kzalloc(sizeof(*e), GFP_KERNEL_ACCOUNT); + if (!e) + return -ENOMEM; + for (i = 0; i < env->prog->len && !err; i += bpf_is_ldimm64(&insn[i]) ? 2 : 1) { + h = bpf_loop_at_index(env, i); + if (h < 0 || can_compute_loop_scev(aux[h].loop)) { + bb_start = true; + continue; + } + if (signal_pending(current)) + err = -EAGAIN; + cond_resched(); + for (r = 0; bb_start && r < REGS_NUM && !err; r++) { + e->reg2expr[r] = UNKNOWN_EXPR_ID; + if (reg_alive_at(env, r, i)) + err = replace_reg(env->scev, e, r, + expr_with_def(env->scev, UNKNOWN_EXPR_ID, + phi_def(i, r))); + } + err = err ?: find_linked_regs(env, e, -1, i); + err = err ?: transfer(env, e, i); + err = err ?: reset_scevs_at_indirect_writes(env, e, i); + bb_start = aux[i].bb_end || bpf_insn_successors(env, i)->cnt != 1; + } + kfree(e); + return err; +} + /* * Find the next SCEV register that is linked to @regno at the conditional jump at @insn_idx: on * every path to the jump *@linked_regno == @regno + *@delta (mod 2^*@bits). It is live there and of @@ -2715,6 +2760,9 @@ int bpf_compute_scev(struct bpf_verifier_env *env) if (err) return err; } + err = find_linked_regs_in_bb(env); + if (err) + return err; /* * Compute scevs from exprs collected on a previous step. Iterate instructions in diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c index 8ffbe7bbdb0a..49f9a976a44c 100644 --- a/tools/testing/selftests/bpf/progs/verifier_scev.c +++ b/tools/testing/selftests/bpf/progs/verifier_scev.c @@ -3423,6 +3423,19 @@ LINKED(linked_at_loop_header, VALID, LINKED(linked_at_loop_entry_only, __failure, LOOP_HEADER("r3 = r8; r2 = r8; r2 += 1; r2 += 1;", "r2 += 2; r3 += 1;")) +/* + * In an irreducible loop registers are linked within a basic block only. In the second test the + * fall-through predecessor of 'm' makes r2 a copy of r8. The other predecessor does not. + */ +LINKED(irreducible_loop, VALID, + "if r7 > 5 goto m_%=; l_%=: r7 += 1;" + "m_%=: r2 = r8; r2 += 1; r2 += 1; if r8 > 61 goto out_%=; r1 = r6; r1 += r2;" + "r0 = *(u8 *)(r1 + 0); if r7 < 10 goto l_%=;") +LINKED(irreducible_loop_fallthrough_pred, UNBOUND, + "r2 = r7; if r7 > 5 goto m_%=; l_%=: r7 += 1; r2 = r8;" + "m_%=: if r8 > 63 goto out_%=; r1 = r6; r1 += r2;" + "r0 = *(u8 *)(r1 + 0); if r7 < 10 goto l_%=;") + /* * No exit of the inner loop dominates its backedges: may_goto is added before its header. The prog * holds a reference, so may_goto goes to the exit of the outer loop: an edge that the verifier -- 2.55.0