From: Alexei Starovoitov #pragma clang loop unroll_count(3) for (i = 0; i < 250; i++) { if (!bpf_get_prandom_u32()) break; out[i] = bpf_get_prandom_u32(); } is rejected with 'invalid access to map value, value_size=1000 off=1000 size=4'. 250 is 83 * 3 + 1. The compiler makes a loop of three copies of the body and leaves it behind the first copy in iteration 84: l: ...; *(u32 *)(r6 - 4) = w0; if r7 == 251 goto out; ...; *(u32 *)(r6 + 0) = w0; ...; *(u32 *)(r6 + 4) = w0; r6 += 12; r7 += 3; goto l; The loop is counted. At its head r6 gets the offsets of all 84 iterations: 4 to 1000. The jump narrows r7, which it tests. It says nothing about r6: the two stores behind it are checked with an offset that they never see. A state that goes on in the loop behind the jump that counts is not in the last iteration. Give the range of one iteration less to what is linear at the jump: r6 is 4 to 988. Only for a jump that leaves the loop itself. An edge that leaves by way of a flag stays in the loop for a while, with the last iteration: no shorter range behind a jump that has such an edge. Signed-off-by: Alexei Starovoitov --- include/linux/bpf_verifier.h | 5 ++- kernel/bpf/scev.c | 59 ++++++++++++++++++++++++++++++++---- kernel/bpf/verifier.c | 9 ++++-- 3 files changed, 64 insertions(+), 9 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 85404ef790ef..61f133e4d72f 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -365,6 +365,8 @@ struct bpf_loop_iters { */ int iv_reg; struct cnum64 iv_range; + /* a jump that counts: it leaves the loop in the last iteration, if not before. Or -1 */ + int count_insn; /* a pointer to the stack that stores go through moves in the loop */ bool spill_base; }; @@ -426,6 +428,7 @@ struct loop_stack_entry { u32 walk_patience; int iv_reg; struct cnum64 iv_range; + int count_insn; }; /* The state is in a walk on patience, which may not get to the end of the loop */ @@ -2216,6 +2219,6 @@ int bpf_widen_scev_regs(struct bpf_verifier_env *env, struct bpf_verifier_state struct bpf_verifier_state *loop_entry, struct bpf_loop_iters *iters, bool back); int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *st, u32 insn_idx, - const struct loop_stack_entry *entry); + const struct loop_stack_entry *entry, bool behind); #endif /* _LINUX_BPF_VERIFIER_H */ diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c index 06f485853df1..4ce8ad5d5a27 100644 --- a/kernel/bpf/scev.c +++ b/kernel/bpf/scev.c @@ -3470,6 +3470,13 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta return 0; } + /* + * It leaves the loop itself: a flag does that later. If one edge does the one and the + * other edge the other, the last iteration goes on behind the jump as well. + */ + iters->count_insn = bpf_jump_leaves_loop(env, insn_idx, first.insn_idx) && + aux[first.insn_idx].edge_leaves != 3 ? first.insn_idx : -1; + if (iters->max_header_count == 0) { if (log->level & BPF_LOG_LEVEL2) bpf_log(log, "loop header at %d, 0 iterations count\n", insn_idx); @@ -3822,12 +3829,31 @@ int bpf_widen_scev_regs(struct bpf_verifier_env *env, struct bpf_verifier_state return 1; } +/* (linear (+ rX imm) slope): the iteration has added a constant to rX so far */ +static bool is_moved_linear(struct scev *scev, u32 id, struct linear_coefs *out, s64 *moved) +{ + u32 base, slope, l, r; + + out->spill32 = false; + return is_linear_or_linear32(scev, id, &base, &slope, &out->zext32) && !out->zext32 && + is_add(scev, base, &l, &r) && is_reg(scev, l, &out->base_reg) && + is_imm(scev, r, moved) && is_simple_slope(scev, slope, &out->slope); +} + +/* + * The state came back to the head of a counted loop. Or, with @behind, it goes on in the loop + * behind the jump that counts. That jump leaves the loop in the last iteration, so this is + * not the last one: + * for (i = 0; ; i++, p += 8) { if (i == 4) break; *p = 0; } + * At the head p is up to 32 bytes from where it was, at the store up to 24. The jump tells that + * about i only. It holds for all that is linear at the jump. + */ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur_func_state, u32 insn_idx, - const struct loop_stack_entry *entry) + const struct loop_stack_entry *entry, bool behind) { struct bpf_verifier_state *entry_state = entry->entry_state; struct bpf_func_state *entry_st = entry_state->frame[entry_state->curframe]; - u32 max_header_count = entry->max_header_count; + u32 max_header_count = entry->max_header_count - behind; struct bpf_verifier_log *log = &env->log; struct bpf_reg_state *reg, *entry_reg; struct scev *scev = env->scev; @@ -3835,6 +3861,7 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur struct env *header_env; struct bounds bounds; u32 r, r_scev; + s64 moved; int err; if (entry_state->curframe != cur_func_state->frameno) { @@ -3843,16 +3870,21 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur return -EFAULT; } - header_env = find_header_env(scev, insn_idx); + header_env = find_loop_env(scev, insn_idx, behind ? entry->count_insn : insn_idx); + if (!max_header_count) + return 0; for (r = 0; r < REGS_NUM; r++) { r_scev = header_env->reg2scev[r]; + moved = 0; entry_reg = spill32_counter(scev, entry_st, r_scev, r, &coefs); reg = spill32_counter(scev, cur_func_state, r_scev, r, &coefs); if (entry_reg && reg) goto clamp; /* If SCEV for r is (linear )*/ - if (!is_simple_linear(scev, r_scev, &coefs) || coefs.base_reg != r) + if ((!is_simple_linear(scev, r_scev, &coefs) && + !(behind && is_moved_linear(scev, r_scev, &coefs, &moved))) || + coefs.base_reg != r) continue; entry_reg = scev_reg_for_linear(entry_st, r); @@ -3878,8 +3910,22 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur continue; clamp: linear_bounds(entry_reg, max_header_count, &coefs, &bounds); - if (r == entry->iv_reg) + if (r == entry->iv_reg && !moved) iv_bounds(&bounds, entry->iv_range); + if (moved) { + bounds.r64 = cnum64_add(bounds.r64, cnum64_from_srange(moved, moved)); + bounds.base = imod(bounds.base + moved, bounds.step); + } + if (behind) { + /* jumps on the way may have told more */ + bounds.r64 = cnum64_intersect(bounds.r64, reg->r64); + bounds.r32 = cnum32_intersect(bounds.r32, reg->r32); + if (type_is_pkt_pointer(reg->type) || cnum64_is_empty(bounds.r64) || + cnum32_is_empty(bounds.r32) || + (cnum64_is_subset(bounds.r64, reg->r64) && + cnum32_is_subset(bounds.r32, reg->r32))) + continue; + } if (log->level & BPF_LOG_LEVEL2) { bpf_log(log, "loop header at %d, clamping ", insn_idx); log_reg(env, r); @@ -3887,7 +3933,8 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur log_bounds(env, &bounds); bpf_log(log, "\n"); } - scratch_widened_reg_id(env, reg); + if (!behind) + scratch_widened_reg_id(env, reg); /* * The range of a packet pointer goes together with its id and with the offsets * that it had in the compare with pkt_end. Both are replaced here. What holds for diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index fa7aa8218218..afb5b9dd18b4 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -21329,7 +21329,7 @@ static int maybe_clamp_scev_regs(struct bpf_verifier_env *env) if (!entry->terminates) return 0; - return bpf_clamp_scev_regs(env, frame, env->insn_idx, entry); + return bpf_clamp_scev_regs(env, frame, env->insn_idx, entry, false); } /* @@ -21501,8 +21501,12 @@ int bpf_flow_loop_enter(struct bpf_verifier_env *env, bool *backedge, bool *drop return 0; entry = &frame->loop_stack[frame->loop_stack_cnt - 1]; - if (env->insn_idx != entry->loop_id) + if (env->insn_idx != entry->loop_id) { + /* the jump that counts didn't leave the loop */ + if (entry->entry_state && !entry->apart && cur->last_insn_idx == entry->count_insn) + return bpf_clamp_scev_regs(env, frame, entry->loop_id, entry, true); return 0; + } /* * No edge goes from a call to itself: the call goes on with one function of a set, see @@ -21623,6 +21627,7 @@ int bpf_flow_loop_enter(struct bpf_verifier_env *env, bool *backedge, bool *drop entry->max_header_count = iters.max_header_count; entry->iv_reg = iters.iv_reg; entry->iv_range = iters.iv_range; + entry->count_insn = iters.count_insn; entry->entry_state = entry_state; entry->terminates = true; /* -- 2.55.0