* [PATCH bpf-next 0/2] bpf: support 32-bit linear scalar evolution
@ 2026-10-20 11:06 Eduard Zingerman
2026-10-20 11:06 ` [PATCH bpf-next 1/2] " Eduard Zingerman
` (2 more replies)
0 siblings, 3 replies; 9+ messages in thread
From: Eduard Zingerman @ 2026-10-20 11:06 UTC (permalink / raw)
To: bpf, ast; +Cc: andrii, daniel, kernel-team, yonghong.song, Eduard Zingerman
Support scalar evolution widening for loops like:
w0 = 0;
l: w0 += 1;
if w0 != 3 goto l;
exit;
Implementation details are covered in the first patch.
Veristat results follow. Program sets: cilium, meta, scx, selftests.
Tables: success in both runs; baseline Insns >= 5,000.
Ranked by percentage change, then instruction-count change, file,
program. Meta names are anonymized.
Top 50 wins are shown, there are no loses.
Histogram
---------
Total progs: 7994
Old success: 5665
New success: 5665
-100 .. -95 %: 21
-95 .. -85 %: 1
-85 .. -75 %: 4
-75 .. -70 %: 17
-70 .. -65 %: 10
-65 .. -55 %: 3
-50 .. -40 %: 2
-40 .. -30 %: 2
-25 .. -15 %: 2
-15 .. -10 %: 7
-10 .. -5 %: 32
-5 .. 0 %: 6
0 .. 5 %: 7887
Top wins (50)
-------------
File Program Insns (A) Insns (B) Insns (DIFF)
----------------------------- --------------------------------- --------- --------- -----------------
timer_start_delete_race.bpf.o start_timer 40007 28 -39979 (-99.93%)
timer_start_delete_race.bpf.o delete_elem 14003 11 -13992 (-99.92%)
verifier_bounds.bpf.o crossing_32_bit_signed_boundary_2 12330 20 -12310 (-99.84%)
access_map_in_map.bpf.o access_map_in_array 18457 35 -18422 (-99.81%)
access_map_in_map.bpf.o access_map_in_htab 18457 35 -18422 (-99.81%)
access_map_in_map.bpf.o sleepable_access_map_in_array 18457 35 -18422 (-99.81%)
access_map_in_map.bpf.o sleepable_access_map_in_htab 18457 35 -18422 (-99.81%)
firewall-09.bpf.o twfw_connect6 153638 320 -153318 (-99.79%)
firewall-09.bpf.o twfw_sendmsg6 153638 320 -153318 (-99.79%)
firewall-10.bpf.o twfw_connect4 102193 241 -101952 (-99.76%)
firewall-10.bpf.o twfw_sendmsg4 102193 241 -101952 (-99.76%)
firewall-10.bpf.o twfw_connect6 166183 397 -165786 (-99.76%)
firewall-10.bpf.o twfw_sendmsg6 166183 397 -165786 (-99.76%)
firewall-09.bpf.o twfw_connect4 76030 197 -75833 (-99.74%)
firewall-09.bpf.o twfw_sendmsg4 76030 197 -75833 (-99.74%)
linked_list.bpf.o clear_global_array_list 13071 57 -13014 (-99.56%)
rhash.bpf.o test_rhash_update_elements 7584 91 -7493 (-98.80%)
profiler-06.bpf.o on_perf_event 425953 94751 -331202 (-77.76%)
profiler-26.bpf.o handle_cu_mem_address_reserve 45724 12702 -33022 (-72.22%)
profiler-26.bpf.o handle_cu_mem_create 45724 12702 -33022 (-72.22%)
profiler-26.bpf.o handle_malloc 45724 12702 -33022 (-72.22%)
profiler-19.bpf.o sched_switch_offcpu 78210 21906 -56304 (-71.99%)
profiler-26.bpf.o handle_cu_mem_map 45922 12900 -33022 (-71.91%)
profiler-09.bpf.o on_custom_event_start 45973 12951 -33022 (-71.83%)
profiler-09.bpf.o trace_func_entry 45973 12951 -33022 (-71.83%)
profiler-19.bpf.o sched_waking 23153 6642 -16511 (-71.31%)
profiler-27.bpf.o handle_cuda_launch_exc 23176 6665 -16511 (-71.24%)
profiler-27.bpf.o handle_cuda_launch 23189 6678 -16511 (-71.20%)
profiler-12.bpf.o on_custom_event_begin 23396 6885 -16511 (-70.57%)
profiler-12.bpf.o on_custom_event_end 23400 6889 -16511 (-70.56%)
profiler-26.bpf.o handle_mtia_cached_alloc 46892 13870 -33022 (-70.42%)
profiler-26.bpf.o handle_mtia_allocate_enter 46953 13931 -33022 (-70.33%)
profiler-12.bpf.o sched_switch 40257 12105 -28152 (-69.93%)
profiler-26.bpf.o handle_pytorch_malloc 47245 14223 -33022 (-69.90%)
profiler-19.bpf.o oncpu 23689 7178 -16511 (-69.70%)
profiler-12.bpf.o on_task_enqueued 23734 7223 -16511 (-69.57%)
profiler-12.bpf.o sched_waking 23769 7258 -16511 (-69.46%)
profiler-12.bpf.o on_task_dequeued 23909 7398 -16511 (-69.06%)
profiler-12.bpf.o on_request_context_event 24000 7489 -16511 (-68.80%)
profiler-12.bpf.o on_pytorch_event 24001 7490 -16511 (-68.79%)
profiler-12.bpf.o on_task_stats 24083 7572 -16511 (-68.56%)
profiler-12.bpf.o oncpu 24187 7676 -16511 (-68.26%)
scx_rusty.bpf.o rusty_init 8784 3171 -5613 (-63.90%)
profiler-12.bpf.o get_crochet_walltime_stacks 50215 22063 -28152 (-56.06%)
security-sandbox-13.bpf.o kvm_die 5807 2967 -2840 (-48.91%)
profiler-24.bpf.o get_task_stacks 103742 64928 -38814 (-37.41%)
scheduler-01.bpf.o arena_alloc_mask 29208 25497 -3711 (-12.71%)
scheduler-03.bpf.o arena_alloc_mask 29208 25497 -3711 (-12.71%)
file-system-monitor-01.bpf.o file_lineage_lsm_file_free 20986 18354 -2632 (-12.54%)
file-system-monitor-01.bpf.o file_lineage_security_file_free 20986 18354 -2632 (-12.54%)
---
Eduard Zingerman (2):
bpf: support 32-bit linear scalar evolution
selftests/bpf: tests for 32-bit scalar evolution bounds computation
include/linux/bpf_verifier.h | 2 +-
kernel/bpf/scev.c | 364 +++++++++++++++------
kernel/bpf/verifier.c | 6 +-
tools/testing/selftests/bpf/progs/verifier_scev.c | 273 +++++++++++++++-
.../selftests/bpf/progs/verifier_stack_ptr.c | 2 +-
5 files changed, 536 insertions(+), 111 deletions(-)
---
base-commit: 25bb03f0a47b622b9025a1558bf2095ec1f55d26
change-id: 20261020-scev-32bit-0bcdd0fd6c34
^ permalink raw reply [flat|nested] 9+ messages in thread* [PATCH bpf-next 1/2] bpf: support 32-bit linear scalar evolution 2026-10-20 11:06 [PATCH bpf-next 0/2] bpf: support 32-bit linear scalar evolution Eduard Zingerman @ 2026-10-20 11:06 ` Eduard Zingerman 2026-10-20 11:35 ` bot+bpf-ci 2026-10-20 11:38 ` sashiko-bot 2026-10-20 11:06 ` [PATCH bpf-next 2/2] selftests/bpf: tests for 32-bit scalar evolution bounds computation Eduard Zingerman 2026-10-20 21:00 ` [PATCH bpf-next 0/2] bpf: support 32-bit linear scalar evolution patchwork-bot+netdevbpf 2 siblings, 2 replies; 9+ messages in thread From: Eduard Zingerman @ 2026-10-20 11:06 UTC (permalink / raw) To: bpf, ast; +Cc: andrii, daniel, kernel-team, yonghong.song, Eduard Zingerman Representation -------------- Represent ALU32 recurrences as: w0 += step -> (zext32 (linear r0 step)) Extend simplify() rules to maintain the above form for latch expressions. E.g. for a post-condition loop such as: w0 = 0; l: w0 += 1; if w0 != 3 goto l; exit; SCEV at header: (zext32 (linear r0 1)) Initial SCEV at latch: (zext32 (+ (zext32 (linear r0 1)) 1)) Simplified SCEV at latch: (zext32 (+ (zext32 (linear r0 1)) 1)) -> (zext32 (+ (linear r0 1) 1)) -> (zext32 (linear (+ r0 1) 1)) Iterations count computation ---------------------------- - Extract the main iteration-count logic from compute_max_iters() into compute_backedge_taken_count(). Reuse its 64-bit arithmetic after sign/zero extending the latch operands. - Reject the computed count if the predicted exit value falls outside signed/unsigned 32-bit range, e.g.: w0 = 0x7ffffffe; l: w0 += 1; if w0 s<= 0x7fffffff goto l; The 64-bit computation predicts an exit at S32_MAX + 1, but the 32-bit value wraps to S32_MIN and the comparison remains true. - Handle mixed 64-bit/32-bit comparisons/recurrences only when initial bounds and step fit in 32-bit ranges, e.g.: w0 = 0; r1 = 0x100000003 ll; l: w0 += 1; if r0 != r1 goto l; Truncating the bound to 32 bits would predict three header visits. However, `w0 += 1` keeps r0 within [0, U32_MAX], so it can never be equal to the 64-bit bound. Widened bounds computation -------------------------- - Update linear_bounds() to truncate the initially computed 64-bit range to 32 bits, then zero-extend it to obtain the 64-bit range of iteration values. Step computation needs to handle: - unsigned 32-bit wraparound; - entry and zero-extended iteration values disagreeing on base/step. - Union both ranges with the corresponding register ranges at entry, since the entry value need not be zero-extended. - Extend `struct bounds` to keep both {32,64}-bit ranges and pass both to bpf_set_reg_range(). A 64-bit range alone loses useful 32-bit information, e.g.: entry = 0, step = -1, two header visits r64: [0, U32_MAX] r32: [-1, 0] Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> --- include/linux/bpf_verifier.h | 2 +- kernel/bpf/scev.c | 364 +++++++++++++++------ kernel/bpf/verifier.c | 6 +- .../selftests/bpf/progs/verifier_stack_ptr.c | 2 +- 4 files changed, 264 insertions(+), 110 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 951a90458d18..903d972ffc9f 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -1885,7 +1885,7 @@ int bpf_compute_subprog_arg_access(struct bpf_verifier_env *env); bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a, const struct bpf_reg_state *reg_b); int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg, - struct cnum64 range, u16 base, u16 step); + struct cnum64 r64, struct cnum32 r32, u16 base, u16 step); bool bpf_reg_union_compatible(const struct bpf_reg_state *a, const struct bpf_reg_state *b); int bpf_reg_union(struct bpf_verifier_env *env, struct bpf_reg_state *acc, const struct bpf_reg_state *src); diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c index 48500d73105a..fea77772ca96 100644 --- a/kernel/bpf/scev.c +++ b/kernel/bpf/scev.c @@ -249,6 +249,14 @@ static bool is_linear(struct scev *scev, int id, u32 *base, u32 *slope) return is_binop(scev, LINEAR_SCEV, id, base, slope); } +static bool is_linear_or_linear32(struct scev *scev, int id, u32 *base, u32 *slope, bool *zext32) +{ + u32 t; + + *zext32 = is_zext32(scev, id, &t); + return is_linear(scev, *zext32 ? t : id, base, slope); +} + static bool is_opaque(struct scev *scev, int id) { return is_op(scev, id, OPAQUE); @@ -1464,7 +1472,7 @@ static int transform_expr(struct scev *scev, u32 root, void *priv, static int simplify(struct scev *scev, u32 id, void *priv) { - u32 l, r, base, slope; + int a, b, l, r, t, base, slope; s64 imm1, imm2; /* (+ (linear base slope) imm) -> (linear (+ base imm) slope) */ @@ -1483,13 +1491,24 @@ static int simplify(struct scev *scev, u32 id, void *priv) if (is_zext32(scev, id, &l) && is_imm(scev, l, &imm1)) return imm_expr(scev, (u64)(u32)imm1); + /* + * (zext32 (+ (zext32 $a) $b)) -> (zext32 (+ $a $b)) + * (zext32 (+ $a (zext32 $b))) -> (zext32 (+ $a $b)) + */ + if ((is_zext32(scev, id, &t) && is_add(scev, t, &l, &b) && is_zext32(scev, l, &a)) || + (is_zext32(scev, id, &t) && is_add(scev, t, &a, &r) && is_zext32(scev, r, &b))) { + t = expr2(scev, BPF_ADD, a, b); + t = expr1(scev, ZEXT32, t); + return t; + } + return id; } static int compute_header_scevs(struct bpf_verifier_env *env, struct env *header_env) { struct scev *scev = env->scev; - int l, r, id, ra, rb, ra_expr; + int l, r, t, id, ra, rb, ra_expr; s64 imm; /* @@ -1522,6 +1541,19 @@ static int compute_header_scevs(struct bpf_verifier_env *env, struct env *header header_env->reg2scev[ra] = id; continue; } + /* rA = (is_zext32 (+ rA IMM)) -> (is_zext32 (linear rA IMM)) */ + if (is_zext32(scev, ra_expr, &t) && + is_add(scev, t, &l, &r) && + is_reg(scev, l, &rb) && + is_imm(scev, r, &imm) && + ra == rb) { + id = expr2(scev, LINEAR_SCEV, l, r); + id = expr1(scev, ZEXT32, id); + if (id < 0) + return id; + header_env->reg2scev[ra] = id; + continue; + } /* rA = rA -> rA*/ if (is_reg(scev, ra_expr, &rb) && ra == rb) { header_env->reg2scev[ra] = ra_expr; @@ -1846,13 +1878,17 @@ static bool scev_reg_alive(struct bpf_verifier_env *env, struct bpf_verifier_sta * Linear latch represents a condition 'if <reg> <op> <loop invariant> goto <loop-header>', * where equation '<base> + i * <step> <op> <bound>' describes values taken by register <reg>, * 'i' is the loop iteration number, starting from 0. + * 'zext32' indicates the latch is for (zext32 (linear ...)) SCEV. + * 'jmp32' indicates that the latch is a JMP32 instruction. */ struct linear_latch { u32 insn_idx; u32 base_expr; u32 step_expr; u32 bound_expr; - u32 op; + u8 op; + bool zext32; + bool jmp32; }; static bool loop_invariant(struct scev *scev, u32 id) @@ -1878,10 +1914,8 @@ static int match_linear_latch(struct bpf_verifier_env *env, u32 t, l, r, op; int id; - /* 32-bit arithmetic is not handled yet */ - if (BPF_CLASS(insn->code) != BPF_JMP) - return false; op = BPF_OP(insn->code); + latch->jmp32 = BPF_CLASS(insn->code) == BPF_JMP32; /* Flip the condition if true branch jumps out of the loop. */ true_branch_tgt = latch_idx + bpf_jmp_offset(insn) + 1; true_branch_loop = bpf_loop_at_index(env, true_branch_tgt); @@ -1915,7 +1949,8 @@ static int match_linear_latch(struct bpf_verifier_env *env, * 'if <invariant> <op> <linear>' ⇔ * 'if <linear> <flip(op)> <invariant>'. */ - if (BPF_SRC(insn->code) == BPF_X && is_linear(scev, src_reg_scev, &l, &r)) { + if (BPF_SRC(insn->code) == BPF_X && + is_linear_or_linear32(scev, src_reg_scev, &l, &r, &latch->zext32)) { swap(dst_reg_scev, src_reg_scev); op = bpf_flip_opcode(op); } @@ -1928,7 +1963,8 @@ static int match_linear_latch(struct bpf_verifier_env *env, * - (linear (+ register imm) step) | * ^----------------------------' */ - if (!is_linear(scev, dst_reg_scev, &latch->base_expr, &latch->step_expr)) + if (!is_linear_or_linear32(scev, dst_reg_scev, + &latch->base_expr, &latch->step_expr, &latch->zext32)) return false; if (BPF_SRC(insn->code) == BPF_K) { @@ -2049,64 +2085,23 @@ static bool eval_expr(struct bpf_verifier_env *env, struct scev *scev, return false; } -/* - * Loop with post-condition: - * - * r0 = 0 - * l: ... r0 ∈ [0,1,2] header executed 3 times - * r0 += 1 r0 ∈ [0,1,2] - * ... r0 ∈ [1,2,3] - * if r0 != 3 goto l r0 ∈ [1,2,3] backedge taken 2 times - * ... r0 ∈ [3] - * - * SCEV at header: r0 = k - * SCEV at latch: r0 = 1 + k - * - * Loop with pre-condition: - * - * r0 = 0 - * l: ... r0 ∈ [0,1,2,3] header executed 4 times - * if r0 == 3 goto e r0 ∈ [0,1,2,3] backedge taken 3 times - * r0 += 1 r0 ∈ [0,1,2] - * ... r0 ∈ [1,2,3] - * goto l r0 ∈ [1,2,3] - * e: ... r0 ∈ [3] - * - * SCEV at header: r0 = k - * SCEV at latch: r0 = k - */ -static bool compute_max_iters(struct bpf_verifier_env *env, - struct bpf_func_state *st, - struct linear_latch *latch, - struct bpf_loop_iters *iters) +static bool is_signed_op(u8 op) { - struct bpf_insn_aux_data *aux = env->insn_aux_data; - struct bpf_loop *loop = aux[bpf_loop_at_index(env, latch->insn_idx)].loop; - struct scev *scev = env->scev; - struct scev_value initial_val, step_val, bound_val; - u64 rem, step, diff, bound, initial, backedge_taken_count; - u8 op = latch->op; - bool up, down; - - if (!eval_expr(env, scev, st, latch->base_expr, &initial_val) || - !eval_expr(env, scev, st, latch->step_expr, &step_val) || - !eval_expr(env, scev, st, latch->bound_expr, &bound_val)) - return false; - - if (step_val.ptr_reg >= 0) { - if (env->log.level & BPF_LOG_LEVEL2) { - bpf_log(&env->log, "scev: latch step is a pointer "); - log_scev_value(env, st, &step_val); - bpf_log(&env->log, "\n"); - } + switch (op) { + case BPF_JSLT: + case BPF_JSLE: + case BPF_JSGT: + case BPF_JSGE: + return true; + default: return false; } - if (!scev_value_compatible(env, st, &initial_val, &bound_val)) - return false; +} - initial = initial_val.value; - step = step_val.value; - bound = bound_val.value; +static bool compute_backedge_taken_count(u8 op, u64 initial, u64 step, u64 bound, u64 *result) +{ + u64 rem, diff, backedge_taken_count; + bool up, down; if (step == 0) return false; @@ -2217,6 +2212,115 @@ static bool compute_max_iters(struct bpf_verifier_env *env, return false; } + *result = backedge_taken_count; + return true; +} + +/* + * Loop with post-condition: + * + * r0 = 0 + * l: ... r0 ∈ [0,1,2] header executed 3 times + * r0 += 1 r0 ∈ [0,1,2] + * ... r0 ∈ [1,2,3] + * if r0 != 3 goto l r0 ∈ [1,2,3] backedge taken 2 times + * ... r0 ∈ [3] + * + * SCEV at header: r0 = k + * SCEV at latch: r0 = 1 + k + * + * Loop with pre-condition: + * + * r0 = 0 + * l: ... r0 ∈ [0,1,2,3] header executed 4 times + * if r0 == 3 goto e r0 ∈ [0,1,2,3] backedge taken 3 times + * r0 += 1 r0 ∈ [0,1,2] + * ... r0 ∈ [1,2,3] + * goto l r0 ∈ [1,2,3] + * e: ... r0 ∈ [3] + * + * SCEV at header: r0 = k + * SCEV at latch: r0 = k + */ +static bool compute_max_iters(struct bpf_verifier_env *env, + struct bpf_func_state *st, + struct linear_latch *latch, + struct bpf_loop_iters *iters) +{ + struct bpf_insn_aux_data *aux = env->insn_aux_data; + struct bpf_loop *loop = aux[bpf_loop_at_index(env, latch->insn_idx)].loop; + struct scev *scev = env->scev; + struct scev_value initial_val, step_val, bound_val; + u64 step, bound, initial, total_change, backedge_taken_count; + u8 op = latch->op; + + if (!eval_expr(env, scev, st, latch->base_expr, &initial_val) || + !eval_expr(env, scev, st, latch->step_expr, &step_val) || + !eval_expr(env, scev, st, latch->bound_expr, &bound_val)) + return false; + + if (step_val.ptr_reg >= 0) { + if (env->log.level & BPF_LOG_LEVEL2) { + bpf_log(&env->log, "scev: latch step is a pointer "); + log_scev_value(env, st, &step_val); + bpf_log(&env->log, "\n"); + } + return false; + } + if (!scev_value_compatible(env, st, &initial_val, &bound_val)) + return false; + + initial = initial_val.value; + step = step_val.value; + bound = bound_val.value; + + /* + * The code below only handles mixed 64-bit/32-bit comparisons/recurrences + * when initial bounds and step fit in 32-bit domain. + */ + if (latch->zext32 || latch->jmp32) { + /* + * With the above constraint doing `l: w0 += 1; if r0 s< 256 goto l;` + * is equivalent to `l: w0 += 1; if r0 < 256 goto l;` + */ + if (latch->jmp32 && is_signed_op(op)) { + initial = (s64)(s32)(u32)initial; + bound = (s64)(s32)(u32)bound; + step = (s64)(s32)(u32)step; + } else { + initial = (u32)initial; + bound = (u32)bound; + step = (s64)(s32)(u32)step; + } + } + if (latch->zext32 ^ latch->jmp32 && (initial != initial_val.value || + bound != bound_val.value || + step != step_val.value)) { + if (env->log.level & BPF_LOG_LEVEL2) + bpf_log(&env->log, + "scev: mixed-width latch has operands outside 32-bit ranges\n"); + return false; + } + + + if (!compute_backedge_taken_count(op, initial, step, bound, &backedge_taken_count)) + return false; + + if (latch->zext32 || latch->jmp32) { + /* + * compute_backedge_taken_count() guarantees that 'total_change' + * does not overflow in 64-bit domain. + */ + total_change = initial + step * backedge_taken_count; + if (latch->jmp32 && is_signed_op(op)) { + if ((s64)total_change < S32_MIN || (s64)total_change > S32_MAX) + return false; + } else { + if (total_change > U32_MAX) + return false; + } + } + /* * max_header_count is u32 and U32_MAX means "infinite", * check to avoid overflow below. @@ -2337,40 +2441,92 @@ static bool is_widenable_any(struct bpf_verifier_env *env, struct bpf_func_state } struct bounds { - struct cnum64 range; + struct cnum64 r64; + struct cnum32 r32; u16 base; u16 step; }; -static bool is_simple_linear(struct scev *scev, u32 id, u32 *base_reg, s64 *slope_imm) +static void log_bounds(struct bpf_verifier_env *env, const struct bounds *bounds) +{ + struct bpf_verifier_log *log = &env->log; + + bpf_verbose_snum(env, cnum64_smin(bounds->r64)); + bpf_log(log, ".."); + bpf_verbose_snum(env, cnum64_smax(bounds->r64)); + if (bounds->r32.size < U32_MAX) { + bpf_log(log, " (s32 "); + bpf_verbose_snum(env, cnum32_smin(bounds->r32)); + bpf_log(log, ".."); + bpf_verbose_snum(env, cnum32_smax(bounds->r32)); + bpf_log(log, ")"); + } + bpf_log(log, " step %u", bounds->step); +} + +struct linear_coefs { + u32 base_reg; + s64 slope; + bool zext32; +}; + +static bool is_simple_linear(struct scev *scev, u32 id, struct linear_coefs *out) { u32 base, slope; - return is_linear(scev, id, &base, &slope) && - is_reg(scev, base, base_reg) && - is_imm(scev, slope, slope_imm) && - *slope_imm <= S16_MAX && - *slope_imm >= S16_MIN && - *slope_imm != 0; + return is_linear_or_linear32(scev, id, &base, &slope, &out->zext32) && + is_reg(scev, base, &out->base_reg) && + is_imm(scev, slope, &out->slope) && + out->slope <= S16_MAX && + out->slope >= S16_MIN && + out->slope != 0; } -/* - * Compute the range an induction variable in `reg` spans over the loop. - * If the computation overflows s64 the range is unbounded, only the - * power-of-two alignment survives the wraparound. - */ -static void linear_bounds(struct bpf_reg_state *reg, u32 max_header_count, s64 slope, - struct bounds *out) +static struct cnum64 cnum64_zext32(struct cnum32 r32) +{ + return cnum64_from_urange(cnum32_umin(r32), cnum32_umax(r32)); +} + +/* Compute the range an induction variable in `reg` spans over the loop. */ +static void linear_bounds(struct bpf_reg_state *reg, u32 max_header_count, + struct linear_coefs *coefs, struct bounds *out) { + s64 slope = coefs->slope; s64 slope_abs = slope < 0 ? -slope : slope; s64 min_val = reg_smin(reg); s64 max_val = reg_smax(reg); + struct cnum64 r64; + struct cnum32 r32; s64 total_change; bool overflow; overflow = check_mul_overflow(slope, (s64)max_header_count - 1, &total_change) || (slope > 0 && check_add_overflow(max_val, total_change, &max_val)) || (slope < 0 && check_add_overflow(min_val, total_change, &min_val)); + r64 = overflow ? CNUM64_UNBOUNDED : cnum64_from_srange(min_val, max_val); + r32 = CNUM32_UNBOUNDED; + if (coefs->zext32) { + r32 = cnum32_from_cnum64(r64); + r64 = cnum64_zext32(r32); + /* + * 32-bit iteration overflow is equivalent to subtracting N * 2**32: + * (base + slope * k) % slope ≠ (base + slope * k - N * 2**32) % slope. + */ + overflow |= cnum32_contains(r32, 0) && cnum32_contains(r32, U32_MAX); + /* + * The entry and zero-extended values must agree on how they define `base`, + * otherwise `base + slope * k` would define different sets of points between + * the two. + */ + overflow |= imod(reg_smin(reg), slope_abs) != + imod(cnum64_smin(r64), slope_abs); + /* + * Full range is a union of a reg's value at loop entry, + * plus a range produced by 32-bit iteration. + */ + r64 = cnum64_union(reg->r64, r64); + r32 = cnum32_union(reg->r32, r32); + } /* * If the entry value is a single point the value set is 'v + slope * k', * so the step is |slope|. Otherwise, only the power-of-two alignment @@ -2378,12 +2534,13 @@ static void linear_bounds(struct bpf_reg_state *reg, u32 max_header_count, s64 s */ if (cnum64_is_const(reg->r64) && !overflow) { out->step = slope_abs; - out->base = imod(min_val, out->step); + out->base = imod(reg_smin(reg), out->step); } else { out->step = 1u << min_t(u32, tnum_alignment(reg->var_off), __ffs(slope_abs)); out->base = 0; } - out->range = overflow ? CNUM64_UNBOUNDED : cnum64_from_srange(min_val, max_val); + out->r64 = r64; + out->r32 = r32; } static int mark_expr_precise(struct bpf_verifier_env *env, struct bpf_func_state *st, u32 id, @@ -2419,16 +2576,16 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta struct scev *scev = env->scev; struct env *header_env; struct linear_latch latch, best; + struct linear_coefs coefs; struct bpf_backedge *backedge; struct bpf_loop_iters tmp; struct bpf_loop *loop; int insn_idx = st->insn_idx; bool found = false; int linear_latch; - u32 r, base_reg; int latch_idx; - s64 slope_imm; int err, j; + u32 r; if (!env->allow_uninit_stack) return 0; @@ -2542,8 +2699,7 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta r_scev = header_env->reg2scev[r]; reg = scev_reg_for_linear(cur_func, r); /* If SCEV for r is (linear <reg> <slope>) */ - if (is_simple_linear(scev, r_scev, &base_reg, &slope_imm) && - reg && is_widenable_reg_type(reg)) { + if (reg && is_simple_linear(scev, r_scev, &coefs) && is_widenable_reg_type(reg)) { /* Spills at varying offsets lose precision */ if (test_bit(r, loop->store_base_regs)) { spill_base = true; @@ -2639,10 +2795,10 @@ int bpf_widen_scev_regs(struct bpf_verifier_env *env, struct bpf_verifier_state struct scev *scev = env->scev; struct bpf_reg_state *reg; struct env *header_env; + struct linear_coefs coefs; struct bounds bounds; - u32 r, base_reg, r_expr, a, b; + u32 r, r_expr, a, b; int insn_idx = st->insn_idx; - s64 slope_imm; int err; for_each_set_bit(r, iters->precise_regs, REGS_NUM) { @@ -2662,23 +2818,21 @@ int bpf_widen_scev_regs(struct bpf_verifier_env *env, struct bpf_verifier_state r_expr = header_env->reg2scev[r]; /* If SCEV for r is (linear <reg> <slope>)*/ - if (is_simple_linear(scev, r_expr, &base_reg, &slope_imm) && - base_reg == r) { + if (is_simple_linear(scev, r_expr, &coefs) && coefs.base_reg == r) { err = scev_reg_for_write(env, cur_func, r, ®); if (err) return err; - linear_bounds(reg, iters->max_header_count, slope_imm, &bounds); + linear_bounds(reg, iters->max_header_count, &coefs, &bounds); if (log->level & BPF_LOG_LEVEL2) { bpf_log(log, "loop header at %d, widening ", insn_idx); log_reg(env, r); bpf_log(log, " to "); - bpf_verbose_snum(env, cnum64_smin(bounds.range)); - bpf_log(log, ".."); - bpf_verbose_snum(env, cnum64_smax(bounds.range)); - bpf_log(log, " step %u\n", bounds.step); + log_bounds(env, &bounds); + bpf_log(log, "\n"); } scratch_widened_reg_id(env, reg); - err = bpf_set_reg_range(env, reg, bounds.range, bounds.base, bounds.step); + err = bpf_set_reg_range(env, reg, bounds.r64, bounds.r32, + bounds.base, bounds.step); if (err) return err; mark_scev_reg_scratched(env, r); @@ -2712,10 +2866,10 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur struct bpf_verifier_log *log = &env->log; struct bpf_reg_state *reg, *entry_reg; struct scev *scev = env->scev; + struct linear_coefs coefs; struct env *header_env; struct bounds bounds; - u32 r, base_reg; - s64 slope_imm; + u32 r; int err; if (entry_state->curframe != cur_func_state->frameno) { @@ -2727,8 +2881,8 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur header_env = find_header_env(scev, insn_idx); for (r = 0; r < REGS_NUM; r++) { /* If SCEV for r is (linear <reg> <slope>)*/ - if (!is_simple_linear(scev, header_env->reg2scev[r], &base_reg, &slope_imm) || - base_reg != r) + if (!is_simple_linear(scev, header_env->reg2scev[r], &coefs) || + coefs.base_reg != r) continue; entry_reg = scev_reg_for_linear(entry_st, r); @@ -2737,9 +2891,10 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur is_unbound_scev_reg(env, entry_st, r)) continue; - linear_bounds(entry_reg, max_header_count, slope_imm, &bounds); - bounds.range = cnum64_intersect(reg->r64, bounds.range); - if (cnum64_is_empty(bounds.range)) { + linear_bounds(entry_reg, max_header_count, &coefs, &bounds); + bounds.r64 = cnum64_intersect(reg->r64, bounds.r64); + bounds.r32 = cnum32_intersect(reg->r32, bounds.r32); + if (cnum64_is_empty(bounds.r64)) { verifier_bug(env, "scev clamp produced empty range for r%d", r); return -EFAULT; } @@ -2747,13 +2902,12 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur bpf_log(log, "loop header at %d, clamping ", insn_idx); log_reg(env, r); bpf_log(log, " to "); - bpf_verbose_snum(env, cnum64_smin(bounds.range)); - bpf_log(log, ".."); - bpf_verbose_snum(env, cnum64_smax(bounds.range)); - bpf_log(log, " step %u\n", bounds.step); + log_bounds(env, &bounds); + bpf_log(log, "\n"); } scratch_widened_reg_id(env, reg); - err = bpf_set_reg_range(env, reg, bounds.range, bounds.base, bounds.step); + err = bpf_set_reg_range(env, reg, bounds.r64, bounds.r32, + bounds.base, bounds.step); if (err) return err; mark_scev_reg_scratched(env, r); diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index d13868846823..ea26da040ff9 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -17587,10 +17587,10 @@ bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a, } int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg, - struct cnum64 range, u16 base, u16 step) + struct cnum64 r64, struct cnum32 r32, u16 base, u16 step) { - reg->r64 = range; - reg->r32 = CNUM32_UNBOUNDED; + reg->r64 = r64; + reg->r32 = r32; reg->step = step; reg->base = base; reg->var_off = tnum_unknown; diff --git a/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c b/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c index 3e9d8fc606ae..7fa7bc207850 100644 --- a/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c +++ b/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c @@ -605,7 +605,7 @@ __msg("R7=fp(smin=smin32=-64,smax=smax32=-8") * back-edge state is clamped to the remaining iterations and pruned * at the header, because [-64, -16] is within the widened [-72, -16] */ -__msg("loop header at 3, clamping r7 to -64..-16 step 8") +__msg("loop header at 3, clamping r7 to -64..-16 (s32 -64..-8) step 8") __msg("from 5 to 3: safe") __msg("processed 9 insns") __naked void stack_ptr_subrange_in_loop(void) -- 2.53.0 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH bpf-next 1/2] bpf: support 32-bit linear scalar evolution 2026-10-20 11:06 ` [PATCH bpf-next 1/2] " Eduard Zingerman @ 2026-10-20 11:35 ` bot+bpf-ci 2026-10-20 21:00 ` Alexei Starovoitov 2026-10-20 11:38 ` sashiko-bot 1 sibling, 1 reply; 9+ messages in thread From: bot+bpf-ci @ 2026-10-20 11:35 UTC (permalink / raw) To: eddyz87, bpf, ast Cc: andrii, daniel, kernel-team, yonghong.song, eddyz87, ast, andrii, daniel, martin.lau, eddyz87, yonghong.song, mason, ihor.solodrai [-- Attachment #1: Type: text/plain, Size: 10741 bytes --] > bpf: support 32-bit linear scalar evolution TL;DR: - JMP32 pointer latches may give too-small iteration bounds, risking unsafe memory access - zext32 clamping may hit verifier_bug on an empty 32-bit range, or clamp pointers wrongly - verifier_scev selftest log breaks until a later patch > diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c > index 48500d73105a..fea77772ca96 100644 > --- a/kernel/bpf/scev.c > +++ b/kernel/bpf/scev.c [ ... ] > @@ -2217,6 +2212,115 @@ static bool compute_max_iters(struct bpf_verifier_env *env, [ ... ] > +static bool compute_max_iters(struct bpf_verifier_env *env, > + struct bpf_func_state *st, > + struct linear_latch *latch, > + struct bpf_loop_iters *iters) [ ... ] > + if (!scev_value_compatible(env, st, &initial_val, &bound_val)) > + return false; > + > + initial = initial_val.value; > + step = step_val.value; > + bound = bound_val.value; > + > + /* > + * The code below only handles mixed 64-bit/32-bit comparisons/recurrences > + * when initial bounds and step fit in 32-bit domain. > + */ > + if (latch->zext32 || latch->jmp32) { > + /* > + * With the above constraint doing `l: w0 += 1; if r0 s< 256 goto l;` > + * is equivalent to `l: w0 += 1; if r0 < 256 goto l;` > + */ > + if (latch->jmp32 && is_signed_op(op)) { > + initial = (s64)(s32)(u32)initial; > + bound = (s64)(s32)(u32)bound; > + step = (s64)(s32)(u32)step; > + } else { > + initial = (u32)initial; > + bound = (u32)bound; > + step = (s64)(s32)(u32)step; > + } > + } Can a JMP32 latch whose operands are pointers get through this code? Before this patch match_linear_latch() rejected every latch that was not BPF_JMP, but it now accepts BPF_JMP32, and compute_max_iters() never checks whether the latch operands are pointers. scev_value_compatible() still accepts two pointers with the same memory origin (PTR_TO_STACK in the same frame, PTR_TO_MAP_VALUE with the same id, PTR_TO_MEM/PTR_TO_BUF with the same id), and for those eval_expr() returns reg->var_off.value, which is the offset from the object and not the address. For 64-bit comparisons, comparing offsets is equivalent to comparing addresses because kernel addresses do not wrap. A JMP32 comparison is different, since at runtime it compares the low 32 bits of the absolute addresses, and those bits can wrap (unsigned) or cross the sign boundary (signed) anywhere inside an object. is_branch_taken() already says so for this exact case: /* * The low 32 bits of a valid pointer may well be zero, hence * nothing below applies to a 32-bit comparison. */ if (is_jmp32) return -1; The 32-bit handling here (truncate or sign-extend the operands, then range-check total_change) only reasons about the offset values. It cannot tell whether the low 32 bits of base+offset stay on one side of the wrap or sign boundary. For a pointer-vs-pointer JMP32 latch (allowed for privileged programs, since check_cond_jmp_op() only rejects pointer comparisons when !allow_ptr_leaks), can the computed max_header_count end up smaller than the real number of iterations? bpf_widen_scev_regs() and bpf_clamp_scev_regs() then bound the induction pointer's range with that count, and the memory access checks inside the loop depend on it being a true upper bound. Would it make sense to return false here when latch->jmp32 is set and either initial_val.ptr_reg or bound_val.ptr_reg is >= 0? zext32 latches cannot involve pointers, because ALU32 on pointers is rejected. [ ... ] > @@ -2542,8 +2699,7 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta > r_scev = header_env->reg2scev[r]; > reg = scev_reg_for_linear(cur_func, r); > /* If SCEV for r is (linear <reg> <slope>) */ > - if (is_simple_linear(scev, r_scev, &base_reg, &slope_imm) && > - reg && is_widenable_reg_type(reg)) { > + if (reg && is_simple_linear(scev, r_scev, &coefs) && is_widenable_reg_type(reg)) { Can this classify a register that holds a pointer at loop entry as a widenable linear induction variable? is_simple_linear() now also accepts (zext32 (linear rA imm)). The header SCEV for such a register comes from reg2expr == (zext32 (+ rA imm)), and the new simplify() rule also produces that form from 'wA = wA; wA += imm'. When allow_ptr_leaks is set, check_alu_op() handles a 32-bit MOV from a pointer by calling mark_reg_unknown(). The register is then SCALAR_VALUE at the backedge while it is still a pointer type at loop entry. is_widenable_reg_type() is only checked here, against the header-state register. bpf_clamp_scev_regs() skips only NOT_INIT entry registers and never checks that entry_reg->type matches reg->type, so linear_bounds() builds bounds from the entry pointer's offset range (reg->r64/var_off describe the offset for pointers, not the value): linear_bounds(entry_reg, max_header_count, &coefs, &bounds); bounds.r64 = cnum64_intersect(reg->r64, bounds.r64); Those bounds are intersected into the scalar register on every backedge, so the scalar is tracked with bounds that don't describe its runtime value. If the intersection is empty, the verifier_bug("scev clamp produced empty range") path fires instead. Before this patch a zext32 SCEV was never linear, so this register hit 'can't widen' and no clamping happened. This was traced from the code only, not from running a reproducer. Should the zext32 case require reg->type == SCALAR_VALUE in bpf_compute_loop_iters()/bpf_widen_scev_regs(), and should bpf_clamp_scev_regs() skip registers whose current type differs from entry_reg->type? [ ... ] > @@ -2737,9 +2891,10 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur > is_unbound_scev_reg(env, entry_st, r)) > continue; > > - linear_bounds(entry_reg, max_header_count, slope_imm, &bounds); > - bounds.range = cnum64_intersect(reg->r64, bounds.range); > - if (cnum64_is_empty(bounds.range)) { > + linear_bounds(entry_reg, max_header_count, &coefs, &bounds); > + bounds.r64 = cnum64_intersect(reg->r64, bounds.r64); > + bounds.r32 = cnum32_intersect(reg->r32, bounds.r32); > + if (cnum64_is_empty(bounds.r64)) { > verifier_bug(env, "scev clamp produced empty range for r%d", r); > return -EFAULT; > } Can bounds.r32 be empty here while bounds.r64 is not? Only the 64-bit intersection is checked for emptiness before both ranges are passed to bpf_set_reg_range(). For zext32 induction variables linear_bounds() sets bounds.r64 to cnum64_zext32(r32). When the 32-bit arc wraps through 0 that is the full [0, U32_MAX], so the 64-bit intersection with any zero-extended value is non-empty while the 32-bit intersection can still be empty. In that case bpf_set_reg_range() stores CNUM32_EMPTY in reg->r32 and reg_bounds_sync() returns early because range_bounds_violation() is true. reg_bounds_sanity_check() then fires: verifier_bug("REG INVARIANTS VIOLATION (bpf_set_reg_range): range bounds violation") verifier_bug() is a WARN_ONCE on CONFIG_DEBUG_KERNEL kernels. With BPF_F_TEST_REG_INVARIANTS the load fails with -EFAULT, and without it the register is reset to unbounded. This can be reached without a verifier bug. The verifier does not track the link between the latch IV and other IVs, so a branch in the loop body can narrow a non-latch IV to its exit value, and that state still reaches the backedge. Example (needs allow_uninit_stack, i.e. a privileged loader): 0: r1 = 0 1: w3 = -4 ; r3 = 0xfffffffc 2: w3 += 2 ; loop header 3: if w3 != 6 goto +1 4: r2 = 0 5: r1 += 1 6: if r1 != 5 goto -5 ; latch, max_header_count = 5 7: r0 = 0 8: exit Header values of w3 are 0xfffffffc, 0xfffffffe, 0, 2, 4. linear_bounds() gives r32 = {0xfffffffc, 8} and r64 = [0, U32_MAX]. On the first widened pass the body sees w3 in {0xfffffffe..6}. The fall-through of 'if w3 != 6' refines w3 to 6, so r64 = {6}. The widened r1 = [0,4] becomes [1,4] after the latch refinement, so the backedge is taken. At the header bpf_clamp_scev_regs() computes: cnum64_intersect({6}, [0, U32_MAX]) = {6} (passes the r64 check) cnum32_intersect({6}, {0xfffffffc..4}) = CNUM32_EMPTY and passes the empty r32 to bpf_set_reg_range(). Before this patch zext32 IVs were never widened or clamped (is_simple_linear() did not match zext32), and the clamp always passed CNUM32_UNBOUNDED for r32, so this program verified without any warning. Should cnum32_is_empty(bounds.r32) be checked alongside r64 here? The same infeasible-backedge pattern with a 64-bit IV (r3 += 2; if r3 != 10 goto +1) appears to reach the existing r64 check and fail with -EFAULT, so would treating an empty clamp intersection as an unreachable path, instead of calling verifier_bug(), be the better fix for both? > @@ -2747,13 +2902,12 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur > bpf_log(log, "loop header at %d, clamping ", insn_idx); > log_reg(env, r); > bpf_log(log, " to "); > - bpf_verbose_snum(env, cnum64_smin(bounds.range)); > - bpf_log(log, ".."); > - bpf_verbose_snum(env, cnum64_smax(bounds.range)); > - bpf_log(log, " step %u\n", bounds.step); > + log_bounds(env, &bounds); > + bpf_log(log, "\n"); > } Does this change the clamp log line for 64-bit IVs as well? For a non-zext IV, bounds.r32 starts as CNUM32_UNBOUNDED, so cnum32_intersect(reg->r32, bounds.r32) just returns the current reg->r32. When that range is bounded, log_bounds() now prints an extra " (s32 ..)" part. verifier_scev.c post_cond_jne_neg_step (r0 = 3; r0 += -1; if r0 != 0 goto) still expects: __msg("loop header at 1, clamping r0 to 1..2 step 1") The kernel now prints "loop header at 1, clamping r0 to 1..2 (s32 1..2) step 1", so that test fails at this commit. This patch updates verifier_stack_ptr.c for the new format but not verifier_scev.c. The expectation is changed later in the series, by commit a8fb69f8ae2e ("selftests/bpf: tests for 32-bit scalar evolution bounds computation"), to "clamping r0 to 1..2 (s32 1..2) step 1". Until then the series is not bisectable for test_progs -t verifier_scev. Could the verifier_scev.c update be folded into this patch? Related: for non-zext IVs the printed "(s32 ..)" range is the unclamped current r32, so it can be wider than the clamped 64-bit range, for example "clamping r7 to -64..-16 (s32 -64..-8)". Could that be misleading in the log? --- AI reviewed your patch. Please fix the bug or email reply why it's not a bug. See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md CI run summary: https://github.com/kernel-patches/bpf/actions/runs/39413885357 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH bpf-next 1/2] bpf: support 32-bit linear scalar evolution 2026-10-20 11:35 ` bot+bpf-ci @ 2026-10-20 21:00 ` Alexei Starovoitov 2026-10-20 21:06 ` Eduard Zingerman 0 siblings, 1 reply; 9+ messages in thread From: Alexei Starovoitov @ 2026-10-20 21:00 UTC (permalink / raw) To: bot+bpf-ci, eddyz87, bpf Cc: andrii, daniel, kernel-team, yonghong.song, martin.lau, mason, ihor.solodrai On Tue, Oct 20, 2026 at 04:35 AM bot+bpf-ci@kernel.org <bot+bpf-ci@kernel.org> wrote: >> + if (!scev_value_compatible(env, st, &initial_val, &bound_val)) >> + return false; > > For a pointer-vs-pointer JMP32 latch (allowed for privileged programs, since > check_cond_jmp_op() only rejects pointer comparisons when !allow_ptr_leaks), > can the computed max_header_count end up smaller than the real number of > iterations? bpf_widen_scev_regs() and bpf_clamp_scev_regs() then bound the > induction pointer's range with that count, and the memory access checks > inside the loop depend on it being a true upper bound. > > Would it make sense to return false here when latch->jmp32 is set and either > initial_val.ptr_reg or bound_val.ptr_reg is >= 0? zext32 latches cannot > involve pointers, because ALU32 on pointers is rejected. Yes. Seems like a real bug. r1 = map_value + 0, r2 = map_value + 56 l: r1 += 8; if w1 <= w2 goto l max_header_count is 8 and r1 is clamped to 0..56. If the low 32 bits of r2 are 0xfffffff8 then w1 wraps to 0 and the latch stays true, so r1 walks past the map value. pls fix in a followup. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH bpf-next 1/2] bpf: support 32-bit linear scalar evolution 2026-10-20 21:00 ` Alexei Starovoitov @ 2026-10-20 21:06 ` Eduard Zingerman 0 siblings, 0 replies; 9+ messages in thread From: Eduard Zingerman @ 2026-10-20 21:06 UTC (permalink / raw) To: Alexei Starovoitov, bot+bpf-ci, bpf Cc: andrii, daniel, kernel-team, yonghong.song, martin.lau, mason, ihor.solodrai On Tue, 2026-10-20 at 21:00 +0000, Alexei Starovoitov wrote: > On Tue, Oct 20, 2026 at 04:35 AM bot+bpf-ci@kernel.org <bot+bpf-ci@kernel.org> wrote: > > > + if (!scev_value_compatible(env, st, &initial_val, &bound_val)) > > > + return false; > > > > For a pointer-vs-pointer JMP32 latch (allowed for privileged programs, since > > check_cond_jmp_op() only rejects pointer comparisons when !allow_ptr_leaks), > > can the computed max_header_count end up smaller than the real number of > > iterations? bpf_widen_scev_regs() and bpf_clamp_scev_regs() then bound the > > induction pointer's range with that count, and the memory access checks > > inside the loop depend on it being a true upper bound. > > > > Would it make sense to return false here when latch->jmp32 is set and either > > initial_val.ptr_reg or bound_val.ptr_reg is >= 0? zext32 latches cannot > > involve pointers, because ALU32 on pointers is rejected. > > Yes. Seems like a real bug. > > r1 = map_value + 0, r2 = map_value + 56 > l: r1 += 8; if w1 <= w2 goto l > > max_header_count is 8 and r1 is clamped to 0..56. If the low 32 bits > of r2 are 0xfffffff8 then w1 wraps to 0 and the latch stays true, > so r1 walks past the map value. > > pls fix in a followup. Yes, and another complain about clamping and possibly dead states. I'll send follow up for pointers today. For clamping need to think a bit. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH bpf-next 1/2] bpf: support 32-bit linear scalar evolution 2026-10-20 11:06 ` [PATCH bpf-next 1/2] " Eduard Zingerman 2026-10-20 11:35 ` bot+bpf-ci @ 2026-10-20 11:38 ` sashiko-bot 1 sibling, 0 replies; 9+ messages in thread From: sashiko-bot @ 2026-10-20 11:38 UTC (permalink / raw) To: Eduard Zingerman, bpf Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider: - [Critical] bpf: 32-bit linear SCEV corrupts pointer and scalar bounds - [Critical] bpf: compute_max_iters() uses pointer offsets for 32-bit latches - [Medium] bpf: bpf_clamp_scev_regs() misses empty r32 check on clamping -- commit c93c9841341e0885c177c1612799cb18f92b0bfc Author: Eduard Zingerman <eddyz87@gmail.com> bpf: support 32-bit linear scalar evolution This commit extends BPF scalar evolution (SCEV) analysis to represent and compute iteration counts and widened bounds for 32-bit ALU recurrences and 32-bit conditional jumps. It also updates struct bounds and bpf_set_reg_range() to track both 32-bit and 64-bit circular number ranges. > diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c > index 48500d73105ac..fea77772ca967 100644 > --- a/kernel/bpf/scev.c > +++ b/kernel/bpf/scev.c [ ... ] > @@ -2217,6 +2212,115 @@ static bool compute_max_iters(struct bpf_verifier_env *env, > return false; > } > > + *result = backedge_taken_count; > + return true; > +} > + > +/* > + * Loop with post-condition: > + * > + * r0 = 0 > + * l: ... r0 ∈ [0,1,2] header executed 3 times > + * r0 += 1 r0 ∈ [0,1,2] > + * ... r0 ∈ [1,2,3] > + * if r0 != 3 goto l r0 ∈ [1,2,3] backedge taken 2 times > + * ... r0 ∈ [3] > + * > + * SCEV at header: r0 = k > + * SCEV at latch: r0 = 1 + k > + * > + * Loop with pre-condition: > + * > + * r0 = 0 > + * l: ... r0 ∈ [0,1,2,3] header executed 4 times > + * if r0 == 3 goto e r0 ∈ [0,1,2,3] backedge taken 3 times > + * r0 += 1 r0 ∈ [0,1,2] > + * ... r0 ∈ [1,2,3] > + * goto l r0 ∈ [1,2,3] > + * e: ... r0 ∈ [3] > + * > + * SCEV at header: r0 = k > + * SCEV at latch: r0 = k > + */ > +static bool compute_max_iters(struct bpf_verifier_env *env, > + struct bpf_func_state *st, > + struct linear_latch *latch, > + struct bpf_loop_iters *iters) > +{ > + struct bpf_insn_aux_data *aux = env->insn_aux_data; > + struct bpf_loop *loop = aux[bpf_loop_at_index(env, latch->insn_idx)].loop; > + struct scev *scev = env->scev; > + struct scev_value initial_val, step_val, bound_val; > + u64 step, bound, initial, total_change, backedge_taken_count; > + u8 op = latch->op; > + > + if (!eval_expr(env, scev, st, latch->base_expr, &initial_val) || > + !eval_expr(env, scev, st, latch->step_expr, &step_val) || > + !eval_expr(env, scev, st, latch->bound_expr, &bound_val)) > + return false; > + > + if (step_val.ptr_reg >= 0) { > + if (env->log.level & BPF_LOG_LEVEL2) { > + bpf_log(&env->log, "scev: latch step is a pointer "); > + log_scev_value(env, st, &step_val); > + bpf_log(&env->log, "\n"); > + } > + return false; > + } > + if (!scev_value_compatible(env, st, &initial_val, &bound_val)) > + return false; > + > + initial = initial_val.value; > + step = step_val.value; > + bound = bound_val.value; > + > + /* > + * The code below only handles mixed 64-bit/32-bit comparisons/recurrences > + * when initial bounds and step fit in 32-bit domain. > + */ > + if (latch->zext32 || latch->jmp32) { [Severity: Critical] Should compute_max_iters() reject pointer operands (initial_val.ptr_reg >= 0 or bound_val.ptr_reg >= 0) when latch->zext32 or latch->jmp32 is true? When eval_expr() evaluates a constant-offset pointer register, it sets result->value to reg->var_off.value (the offset relative to the runtime base address) and result->ptr_reg >= 0. If two registers r1 and r2 point to the same memory object (for example, PTR_TO_PACKET, PTR_TO_MAP_VALUE, or PTR_TO_STACK with r1 = base + 0 and r2 = base + 9), scev_value_compatible() succeeds. While comparing relative offsets works for 64-bit jumps and 64-bit pointer arithmetic because valid kernel objects do not cross 64-bit address space boundaries, a BPF_JMP32 latch (such as "if w1 < w2 goto l" with "r1 += 2") compares the low 32 bits of the runtime kernel addresses: (u32)(base + offset) or (s32)(base + offset). Because (u32)base is unknown at verification time and can sit near U32_MAX or S32_MAX, (u32)(base + initial + k * step) and (u32)(base + bound) can wrap around U32_MAX -> 0 or S32_MAX -> S32_MIN at runtime even when the relative offsets initial, bound, and total_change are small (e.g. if (u32)base == 0xfffffff6, then w2 == 0xffffffff and w1 wraps around U32_MAX on even values without terminating). Can this cause compute_max_iters() to compute an unsound max_header_count and widen pointer or scalar induction variables to incorrect bounds? > + /* > + * With the above constraint doing `l: w0 += 1; if r0 s< 256 goto l;` > + * is equivalent to `l: w0 += 1; if r0 < 256 goto l;` > + */ > + if (latch->jmp32 && is_signed_op(op)) { > + initial = (s64)(s32)(u32)initial; > + bound = (s64)(s32)(u32)bound; > + step = (s64)(s32)(u32)step; > + } else { > + initial = (u32)initial; > + bound = (u32)bound; > + step = (s64)(s32)(u32)step; > + } > + } [ ... ] > @@ -2542,8 +2699,7 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta > r_scev = header_env->reg2scev[r]; > reg = scev_reg_for_linear(cur_func, r); > /* If SCEV for r is (linear <reg> <slope>) */ > - if (is_simple_linear(scev, r_scev, &base_reg, &slope_imm) && > - reg && is_widenable_reg_type(reg)) { > + if (reg && is_simple_linear(scev, r_scev, &coefs) && is_widenable_reg_type(reg)) { [Severity: Critical] Can allowing coefs.zext32 on non-scalar registers corrupt pointer and scalar bounds during widening and clamping? In bpf_compute_loop_iters(), is_widenable_reg_type(reg) accepts pointer types such as PTR_TO_MAP_VALUE, PTR_TO_STACK, and PTR_TO_PACKET alongside SCALAR_VALUE, even when is_simple_linear() sets coefs.zext32 = true (for example, when a loop body executes "w7 += 8" on a register r7 holding a pointer at loop entry). This leads to two issues: 1. At loop entry, bpf_widen_scev_regs() calls linear_bounds() with coefs.zext32 = true on the pointer's relative offset while keeping reg->type as a pointer. For negative pointer offsets such as fp-64, cnum64_zext32() zero-extends the 32-bit offset to 0xffffffc0.. and unions it into reg->r64 on a PTR_TO_STACK register. For PTR_TO_MAP_VALUE at offset 0 (with 4 header visits and step 8), bpf_widen_scev_regs() widens r7 at the header to PTR_TO_MAP_VALUE with offset [0, 24]. 2. When do_check() verifies "w7 += 8" in the loop body with env->allow_ptr_leaks enabled, adjust_ptr_min_max_vals() rejects 32-bit pointer arithmetic via mark_reg_unknown() and scalar32_min_max_add(), turning r7 in cur_func_state into an unknown SCALAR_VALUE holding the low 32 bits of the runtime kernel pointer plus 8. When execution reaches the loop header along the backedge, bpf_clamp_scev_regs() computes linear_bounds() from entry_reg (which is still PTR_TO_MAP_VALUE with offset 0, yielding bounds [0, 24]) and intersects those pointer-offset bounds directly into reg (which is now SCALAR_VALUE) without checking that entry_reg and reg are scalars or have matching types. The verifier then treats scalar r7 as bounded to [0, 24] while at runtime it holds (u32)map_value_kaddr + 8. Should zext32 linear SCEVs be restricted to reg->type == SCALAR_VALUE (and should bpf_clamp_scev_regs() verify that entry_reg and reg have compatible types)? > /* Spills at varying offsets lose precision */ > if (test_bit(r, loop->store_base_regs)) { > spill_base = true; [ ... ] > @@ -2737,9 +2891,10 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur > is_unbound_scev_reg(env, entry_st, r)) > continue; > > - linear_bounds(entry_reg, max_header_count, slope_imm, &bounds); > - bounds.range = cnum64_intersect(reg->r64, bounds.range); > - if (cnum64_is_empty(bounds.range)) { > + linear_bounds(entry_reg, max_header_count, &coefs, &bounds); > + bounds.r64 = cnum64_intersect(reg->r64, bounds.r64); > + bounds.r32 = cnum32_intersect(reg->r32, bounds.r32); > + if (cnum64_is_empty(bounds.r64)) { > verifier_bug(env, "scev clamp produced empty range for r%d", r); > return -EFAULT; > } [Severity: Medium] Can bpf_clamp_scev_regs() pass an empty bounds.r32 to bpf_set_reg_range() and trigger a register invariants violation in reg_bounds_sanity_check()? In linear_bounds(), when coefs->zext32 is true and the 32-bit range wraps around 0 and U32_MAX (e.g. w1 = 0 at entry, step = -1, two header visits), bounds.r64 becomes [0, U32_MAX] while bounds.r32 is [-1, 0] (similarly, if entry_reg has non-zero upper 32 bits, bounds.r64 is wider than bounds.r32). If an in-loop branch refines reg on the backedge to a 32-bit value outside bounds.r32 (for example, w1 == -2, so reg->r64 is [0xfffffffe, 0xfffffffe] and reg->r32 is [-2, -2]), intersecting reg->r64 with [0, U32_MAX] produces a non-empty bounds.r64, whereas intersecting reg->r32 with [-1, 0] produces CNUM32_EMPTY. (A similar situation can occur when !coefs->zext32 leaves bounds.r32 as CNUM32_UNBOUNDED, and deduce_bounds_32_from_64() inside reg_bounds_sync() intersects reg->r32 with the 32-bit projection of bounds.r64.) Because bpf_clamp_scev_regs() only checks cnum64_is_empty(bounds.r64), it proceeds to bpf_set_reg_range(), where reg_bounds_sanity_check() flags cnum32_is_empty(reg->r32) as a range bounds violation. Should bpf_clamp_scev_regs() also check cnum32_is_empty(bounds.r32)? > @@ -2747,13 +2902,12 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur > bpf_log(log, "loop header at %d, clamping ", insn_idx); > log_reg(env, r); > bpf_log(log, " to "); > - bpf_verbose_snum(env, cnum64_smin(bounds.range)); > - bpf_log(log, ".."); > - bpf_verbose_snum(env, cnum64_smax(bounds.range)); > - bpf_log(log, " step %u\n", bounds.step); > + log_bounds(env, &bounds); > + bpf_log(log, "\n"); > } > scratch_widened_reg_id(env, reg); > - err = bpf_set_reg_range(env, reg, bounds.range, bounds.base, bounds.step); > + err = bpf_set_reg_range(env, reg, bounds.r64, bounds.r32, > + bounds.base, bounds.step); > if (err) > return err; > mark_scev_reg_scratched(env, r); [ ... ] > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index d138688468236..ea26da040ff96 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -17587,10 +17587,10 @@ bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a, > } > > int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg, > - struct cnum64 range, u16 base, u16 step) > + struct cnum64 r64, struct cnum32 r32, u16 base, u16 step) > { > - reg->r64 = range; > - reg->r32 = CNUM32_UNBOUNDED; > + reg->r64 = r64; > + reg->r32 = r32; > reg->step = step; > reg->base = base; > reg->var_off = tnum_unknown; [ ... ] 完美 Let me double-check that I didn't accidentally output any trailing characters or markdown. Wait—I have not output the final response yet! Let's output the clean plain-text report now, ending with a blank line.commit c93c9841341e0885c177c1612799cb18f92b0bfc Author: Eduard Zingerman <eddyz87@gmail.com> bpf: support 32-bit linear scalar evolution This commit extends BPF scalar evolution (SCEV) analysis to represent and compute iteration counts and widened bounds for 32-bit ALU recurrences and 32-bit conditional jumps. It also updates struct bounds and bpf_set_reg_range() to track both 32-bit and 64-bit circular number ranges. > diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c > index 48500d73105ac..fea77772ca967 100644 > --- a/kernel/bpf/scev.c > +++ b/kernel/bpf/scev.c [ ... ] > @@ -2217,6 +2212,115 @@ static bool compute_max_iters(struct bpf_verifier_env *env, > return false; > } > > + *result = backedge_taken_count; > + return true; > +} > + > +/* > + * Loop with post-condition: > + * > + * r0 = 0 > + * l: ... r0 ∈ [0,1,2] header executed 3 times > + * r0 += 1 r0 ∈ [0,1,2] > + * ... r0 ∈ [1,2,3] > + * if r0 != 3 goto l r0 ∈ [1,2,3] backedge taken 2 times > + * ... r0 ∈ [3] > + * > + * SCEV at header: r0 = k > + * SCEV at latch: r0 = 1 + k > + * > + * Loop with pre-condition: > + * > + * r0 = 0 > + * l: ... r0 ∈ [0,1,2,3] header executed 4 times > + * if r0 == 3 goto e r0 ∈ [0,1,2,3] backedge taken 3 times > + * r0 += 1 r0 ∈ [0,1,2] > + * ... r0 ∈ [1,2,3] > + * goto l r0 ∈ [1,2,3] > + * e: ... r0 ∈ [3] > + * > + * SCEV at header: r0 = k > + * SCEV at latch: r0 = k > + */ > +static bool compute_max_iters(struct bpf_verifier_env *env, > + struct bpf_func_state *st, > + struct linear_latch *latch, > + struct bpf_loop_iters *iters) > +{ > + struct bpf_insn_aux_data *aux = env->insn_aux_data; > + struct bpf_loop *loop = aux[bpf_loop_at_index(env, latch->insn_idx)].loop; > + struct scev *scev = env->scev; > + struct scev_value initial_val, step_val, bound_val; > + u64 step, bound, initial, total_change, backedge_taken_count; > + u8 op = latch->op; > + > + if (!eval_expr(env, scev, st, latch->base_expr, &initial_val) || > + !eval_expr(env, scev, st, latch->step_expr, &step_val) || > + !eval_expr(env, scev, st, latch->bound_expr, &bound_val)) > + return false; > + > + if (step_val.ptr_reg >= 0) { > + if (env->log.level & BPF_LOG_LEVEL2) { > + bpf_log(&env->log, "scev: latch step is a pointer "); > + log_scev_value(env, st, &step_val); > + bpf_log(&env->log, "\n"); > + } > + return false; > + } > + if (!scev_value_compatible(env, st, &initial_val, &bound_val)) > + return false; > + > + initial = initial_val.value; > + step = step_val.value; > + bound = bound_val.value; > + > + /* > + * The code below only handles mixed 64-bit/32-bit comparisons/recurrences > + * when initial bounds and step fit in 32-bit domain. > + */ > + if (latch->zext32 || latch->jmp32) { [Severity: Critical] Should compute_max_iters() reject pointer operands (initial_val.ptr_reg >= 0 or bound_val.ptr_reg >= 0) when latch->zext32 or latch->jmp32 is true? When eval_expr() evaluates a constant-offset pointer register, it sets result->value to reg->var_off.value (the offset relative to the runtime base address) and result->ptr_reg >= 0. If two registers r1 and r2 point to the same memory object (for example, PTR_TO_PACKET, PTR_TO_MAP_VALUE, or PTR_TO_STACK with r1 = base + 0 and r2 = base + 9), scev_value_compatible() succeeds. While comparing relative offsets works for 64-bit jumps and 64-bit pointer arithmetic because valid kernel objects do not cross 64-bit address space boundaries, a BPF_JMP32 latch (such as "if w1 < w2 goto l" with "r1 += 2") compares the low 32 bits of the runtime kernel addresses: (u32)(base + offset) or (s32)(base + offset). Because (u32)base is unknown at verification time and can sit near U32_MAX or S32_MAX, (u32)(base + initial + k * step) and (u32)(base + bound) can wrap around U32_MAX -> 0 or S32_MAX -> S32_MIN at runtime even when the relative offsets initial, bound, and total_change are small (e.g. if (u32)base == 0xfffffff6, then w2 == 0xffffffff and w1 wraps around U32_MAX on even values without terminating). Can this cause compute_max_iters() to compute an unsound max_header_count and widen pointer or scalar induction variables to incorrect bounds? > + /* > + * With the above constraint doing `l: w0 += 1; if r0 s< 256 goto l;` > + * is equivalent to `l: w0 += 1; if r0 < 256 goto l;` > + */ > + if (latch->jmp32 && is_signed_op(op)) { > + initial = (s64)(s32)(u32)initial; > + bound = (s64)(s32)(u32)bound; > + step = (s64)(s32)(u32)step; > + } else { > + initial = (u32)initial; > + bound = (u32)bound; > + step = (s64)(s32)(u32)step; > + } > + } [ ... ] > @@ -2542,8 +2699,7 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta > r_scev = header_env->reg2scev[r]; > reg = scev_reg_for_linear(cur_func, r); > /* If SCEV for r is (linear <reg> <slope>) */ > - if (is_simple_linear(scev, r_scev, &base_reg, &slope_imm) && > - reg && is_widenable_reg_type(reg)) { > + if (reg && is_simple_linear(scev, r_scev, &coefs) && is_widenable_reg_type(reg)) { [Severity: Critical] Can allowing coefs.zext32 on non-scalar registers corrupt pointer and scalar bounds during widening and clamping? In bpf_compute_loop_iters(), is_widenable_reg_type(reg) accepts pointer types such as PTR_TO_MAP_VALUE, PTR_TO_STACK, and PTR_TO_PACKET alongside SCALAR_VALUE, even when is_simple_linear() sets coefs.zext32 = true (for example, when a loop body executes "w7 += 8" on a register r7 holding a pointer at loop entry). This leads to two issues: 1. At loop entry, bpf_widen_scev_regs() calls linear_bounds() with coefs.zext32 = true on the pointer's relative offset while keeping reg->type as a pointer. For negative pointer offsets such as fp-64, cnum64_zext32() zero-extends the 32-bit offset to 0xffffffc0.. and unions it into reg->r64 on a PTR_TO_STACK register. For PTR_TO_MAP_VALUE at offset 0 (with 4 header visits and step 8), bpf_widen_scev_regs() widens r7 at the header to PTR_TO_MAP_VALUE with offset [0, 24]. 2. When do_check() verifies "w7 += 8" in the loop body with env->allow_ptr_leaks enabled, adjust_ptr_min_max_vals() rejects 32-bit pointer arithmetic via mark_reg_unknown() and scalar32_min_max_add(), turning r7 in cur_func_state into an unknown SCALAR_VALUE holding the low 32 bits of the runtime kernel pointer plus 8. When execution reaches the loop header along the backedge, bpf_clamp_scev_regs() computes linear_bounds() from entry_reg (which is still PTR_TO_MAP_VALUE with offset 0, yielding bounds [0, 24]) and intersects those pointer-offset bounds directly into reg (which is now SCALAR_VALUE) without checking that entry_reg and reg are scalars or have matching types. The verifier then treats scalar r7 as bounded to [0, 24] while at runtime it holds (u32)map_value_kaddr + 8. Should zext32 linear SCEVs be restricted to reg->type == SCALAR_VALUE (and should bpf_clamp_scev_regs() verify that entry_reg and reg have compatible types)? > /* Spills at varying offsets lose precision */ > if (test_bit(r, loop->store_base_regs)) { > spill_base = true; [ ... ] > @@ -2737,9 +2891,10 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur > is_unbound_scev_reg(env, entry_st, r)) > continue; > > - linear_bounds(entry_reg, max_header_count, slope_imm, &bounds); > - bounds.range = cnum64_intersect(reg->r64, bounds.range); > - if (cnum64_is_empty(bounds.range)) { > + linear_bounds(entry_reg, max_header_count, &coefs, &bounds); > + bounds.r64 = cnum64_intersect(reg->r64, bounds.r64); > + bounds.r32 = cnum32_intersect(reg->r32, bounds.r32); > + if (cnum64_is_empty(bounds.r64)) { > verifier_bug(env, "scev clamp produced empty range for r%d", r); > return -EFAULT; > } [Severity: Medium] Can bpf_clamp_scev_regs() pass an empty bounds.r32 to bpf_set_reg_range() and trigger a register invariants violation in reg_bounds_sanity_check()? In linear_bounds(), when coefs->zext32 is true and the 32-bit range wraps around 0 and U32_MAX (e.g. w1 = 0 at entry, step = -1, two header visits), bounds.r64 becomes [0, U32_MAX] while bounds.r32 is [-1, 0] (similarly, if entry_reg has non-zero upper 32 bits, bounds.r64 is wider than bounds.r32). If an in-loop branch refines reg on the backedge to a 32-bit value outside bounds.r32 (for example, w1 == -2, so reg->r64 is [0xfffffffe, 0xfffffffe] and reg->r32 is [-2, -2]), intersecting reg->r64 with [0, U32_MAX] produces a non-empty bounds.r64, whereas intersecting reg->r32 with [-1, 0] produces CNUM32_EMPTY. (A similar situation can occur when !coefs->zext32 leaves bounds.r32 as CNUM32_UNBOUNDED, and deduce_bounds_32_from_64() inside reg_bounds_sync() intersects reg->r32 with the 32-bit projection of bounds.r64.) Because bpf_clamp_scev_regs() only checks cnum64_is_empty(bounds.r64), it proceeds to bpf_set_reg_range(), where reg_bounds_sanity_check() flags cnum32_is_empty(reg->r32) as a range bounds violation. Should bpf_clamp_scev_regs() also check cnum32_is_empty(bounds.r32)? > @@ -2747,13 +2902,12 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur > bpf_log(log, "loop header at %d, clamping ", insn_idx); > log_reg(env, r); > bpf_log(log, " to "); > - bpf_verbose_snum(env, cnum64_smin(bounds.range)); > - bpf_log(log, ".."); > - bpf_verbose_snum(env, cnum64_smax(bounds.range)); > - bpf_log(log, " step %u\n", bounds.step); > + log_bounds(env, &bounds); > + bpf_log(log, "\n"); > } > scratch_widened_reg_id(env, reg); > - err = bpf_set_reg_range(env, reg, bounds.range, bounds.base, bounds.step); > + err = bpf_set_reg_range(env, reg, bounds.r64, bounds.r32, > + bounds.base, bounds.step); > if (err) > return err; > mark_scev_reg_scratched(env, r); [ ... ] > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index d138688468236..ea26da040ff96 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -17587,10 +17587,10 @@ bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a, > } > > int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg, > - struct cnum64 range, u16 base, u16 step) > + struct cnum64 r64, struct cnum32 r32, u16 base, u16 step) > { > - reg->r64 = range; > - reg->r32 = CNUM32_UNBOUNDED; > + reg->r64 = r64; > + reg->r32 = r32; > reg->step = step; > reg->base = base; > reg->var_off = tnum_unknown; [ ... ] -- Sashiko AI review · https://sashiko.dev/#/patchset/20261020-scev-32bit-v1-0-838f34f9f0cd@gmail.com?part=1 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH bpf-next 2/2] selftests/bpf: tests for 32-bit scalar evolution bounds computation 2026-10-20 11:06 [PATCH bpf-next 0/2] bpf: support 32-bit linear scalar evolution Eduard Zingerman 2026-10-20 11:06 ` [PATCH bpf-next 1/2] " Eduard Zingerman @ 2026-10-20 11:06 ` Eduard Zingerman 2026-10-20 11:35 ` bot+bpf-ci 2026-10-20 21:00 ` [PATCH bpf-next 0/2] bpf: support 32-bit linear scalar evolution patchwork-bot+netdevbpf 2 siblings, 1 reply; 9+ messages in thread From: Eduard Zingerman @ 2026-10-20 11:06 UTC (permalink / raw) To: bpf, ast; +Cc: andrii, daniel, kernel-team, yonghong.song, Eduard Zingerman The post32_* tests exercise scev.c:compute_max_iters(): - 32-bit to 64-bit operand extension and overflow handling. - <, <=, >, >=, s<, s<=, s>, s>=, != operations. - Checks exact boundary hits and overflow at S32_MIN, S32_MAX, and U32_MAX. The post_cond_jne32* tests exercise zero-extension logic in scev.c:linear_bounds(): - 32-bit unsigned wraparound. - Entry and zero-extended iteration values disagreeing on base/step, requiring the step to be reduced. - Widened bounds containing both the original entry value and the zero-extended iteration values. - Preserving step and base when that union crosses the signed 64-bit boundary. The post_cond_alu{32,64}_jmp{64,32} tests cover mixed-width recurrences and comparisons: - Declining to compute an iteration count when operands or the predicted exit fall outside the required 32-bit ranges. - Computing iteration counts and widened bounds for compatible mixed-width loops. Also add a basic pre-condition loop test. Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> --- tools/testing/selftests/bpf/progs/verifier_scev.c | 273 +++++++++++++++++++++- 1 file changed, 272 insertions(+), 1 deletion(-) diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c index 59c4b2864db0..661ce9ca8f93 100644 --- a/tools/testing/selftests/bpf/progs/verifier_scev.c +++ b/tools/testing/selftests/bpf/progs/verifier_scev.c @@ -3,6 +3,7 @@ #include <linux/bpf.h> #include <stdbool.h> +#include <stdint.h> #include <bpf/bpf_helpers.h> #include "../../../include/linux/filter.h" #include "bpf_misc.h" @@ -54,6 +55,12 @@ __naked void name(void) #define PRE__COND_TEST2(name, op, initial, step, bound, msg) \ PRE__COND_TEST(name, op, initial, step, bound, msg, LIMIT_ITERATIONS) +#define POST_COND_TEST32(name, op, initial, step, bound, msg) \ + COND_TEST(name, initial, step, bound, msg, \ + "1: r8 = %[step] ll;" LIMIT_ITERATIONS \ + "w6 += w8;" \ + "if w6 " op " w7 goto 1b;") + #define ITER_U64_MAX (~0ULL) #define ITER_S64_MAX ((1ULL << 63) - 1) #define ITER_S64_MIN (1ULL << 63) @@ -969,6 +976,42 @@ PRE__COND_TEST (pre_ne_step_min, "==", 0, ITER_S64_MIN, IT */ PRE__COND_TEST2(pre_lt_zero_step, ">=", 1, 0, 7, "can't compute iterations count") +/* + * Signed JMP32 comparisons sign-extend the initial value, bound and step. + * Encode negative operands as positive u32 constants so the conversion matters. + * post32_sgt also checks that an exit exactly at S32_MIN is accepted. + */ +/* name op initial step bound expected message */ +POST_COND_TEST32(post32_slt, "s<", -7u, 2, -1u, "header_count is [0..3] ") +POST_COND_TEST32(post32_sle, "s<=", -7u, 2, -1u, "header_count is [0..4] ") +POST_COND_TEST32(post32_sgt, "s>", (__u32)INT32_MIN + 6, -2u, (__u32)INT32_MIN, "header_count is [0..3] ") +POST_COND_TEST32(post32_sge, "s>=", -1u, -2u, -7u, "header_count is [0..4] ") + +/* + * When computing 32-bit iteration bounds, scev.c:compute_max_iters() does + * the computation in the 64-bit domain first. For unsigned JMP32 comparisons, + * it zero-extends the initial value and bound, but sign-extends the step. + * Hence pick negative 64-bit initial values and bounds, and encode negative + * steps as positive u32 constants, so both conversions affect the computation. + * post32_lt also checks that an exit exactly at U32_MAX is accepted. + */ +POST_COND_TEST32(post32_lt, "<", -7, 2, -1, "header_count is [0..3] ") +POST_COND_TEST32(post32_le, "<=", -9, 2, -3, "header_count is [0..4] ") +POST_COND_TEST32(post32_gt, ">", -1, -2u, -7, "header_count is [0..3] ") +POST_COND_TEST32(post32_ge, ">=", -1, -2u, -7, "header_count is [0..4] ") +POST_COND_TEST32(post32_ne, "!=", -1, -2u, -7, "header_count is [0..3] ") + +/* An exit exactly at S32_MAX is accepted as well. */ +POST_COND_TEST32(post32_slt_max, "s<", INT32_MAX - 6, 2, INT32_MAX, "header_count is [0..3] ") + +/* + * The first iteration fits in 32 bits, but the predicted exit overshoots the bound + * by one and wraps. + */ +POST_COND_TEST32(post32_slt_wrap, "s<", INT32_MAX - 3, 2, INT32_MAX, "can't compute iterations count") +POST_COND_TEST32(post32_sgt_wrap, "s>", (__u32)INT32_MIN + 3, -2u, (__u32)INT32_MIN, "can't compute iterations count") +POST_COND_TEST32(post32_lt_wrap, "<", -4, 2, -1, "can't compute iterations count") + SEC("xdp") __success __log_level(2) @@ -1549,7 +1592,7 @@ __msg_next(" r0=(+ r0 -1) / (linear (+ r0 -1) -1)") __msg("loop header at 1, header_count is 3 ") __msg("loop header at 1, widening r0 to 1..3 step 1") __msg("1: R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,var_off=(0x0; 0x3)) loop_stack=1") -__msg("loop header at 1, clamping r0 to 1..2 step 1") +__msg("loop header at 1, clamping r0 to 1..2 (s32 1..2) step 1") __msg("processed 5 insns") __naked void post_cond_jne_neg_step(void) { @@ -1591,6 +1634,234 @@ __naked void pre_cond_je1(void) " ::: __clobber_all); } +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg_next("scev at header 1:") +__msg_next(" r0=(zext32 (+ r0 1)) / (zext32 (linear r0 1))") +__msg_next(" scev at latch 2:") +__msg_next(" r0=(zext32 (+ r0 1)) / (zext32 (linear (+ r0 1) 1))") +__msg("loop header at 1, widening r0") +__msg("1: R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=2,{{.*}})") +__msg("1: (04) w0 += 1 ; R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,{{.*}})") +__msg("2: (56) if w0 != 0x3 goto pc-2") +__msg("3: (95) exit") +__msg("loop header at 1, clamping r0") +__msg("from 2 to 1: safe") +__msg("processed 5 insns") +__naked void post_cond_jne32(void) +{ + asm volatile (" \ + w0 = 0; \ +1: w0 += 1; \ + if w0 != 3 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* w0 ∈ {0xffffffff, 2, 5}, w0 % 3 ∈ {0, 2, 2} ⇒ step 3 can't be preserved */ +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("scev at header 1:") +__msg_next(" r0=(zext32 (+ r0 3)) / (zext32 (linear r0 3))") +__msg_next(" scev at latch 2:") +__msg_next(" r0=(zext32 (+ r0 3)) / (zext32 (linear (+ r0 3) 3))") +__msg("entering loop 1") +__msg_next("loop header at 1, header_count is 2") +__msg("loop header at 1, widening r0 to 0..0xffffffff (s32 -1..2) step 1") +__msg("1: R0=scalar(smin=0,smax=umax=0xffffffff,smin32=-1,smax32=2,{{.*}})") +__naked void post_cond_jne32_overflow(void) +{ + asm volatile (" \ + w0 = 0xffffffff; \ +1: w0 += 3; \ + if w0 != 5 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* + * w0 ∈ {0, 3, ..., 0xffffffff, 2, 5}, w0 % 3 ∈ {0, 0, ..., 0, 2, 2} + * ⇒ step 3 can't be preserved. + */ +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("loop header at 2, header_count is 1431655767") +__msg("loop header at 2, widening r0 to 0..0xffffffff step 1") +__naked void post_cond_jne32_full_range(void) +{ + asm volatile (" \ + w0 = 0; \ + w1 = 0; \ +1: w0 += 3; \ + w1 += 1; \ + if w1 != 1431655767 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* r0 ∈ {-6, 0xfffffff7, 0xfffffff4}, r0 % 3 ∈ {0, 1, 1} ⇒ step 3 can't be preserved. */ +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("loop header at 1, header_count is 2") +__msg("loop header at 1, widening r0 to -6..0xfffffffa (s32 -9..-6) step 1") +__naked void post_cond_jne32_base_mismatch(void) +{ + asm volatile (" \ + r0 = -6; \ +1: w0 += -3; \ + if w0 != -12 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* + * r0 ∈ {0, 0xffffffff, 0xfffffffe}, + * ⇒ the 64-bit header bounds are [0, U32_MAX], 32-bit header bounds are [-1, 0]. + */ +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("loop header at 1, header_count is 2") +__msg("loop header at 1, widening r0 to 0..0xffffffff (s32 -1..0) step 1") +__naked void post_cond_jne32_neg_step(void) +{ + asm volatile (" \ + w0 = 0; \ +1: w0 += -1; \ + if w0 != -2 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* + * r0 ∈ {S64_MIN + 1, 3, 5}, r0 % 2 ∈ {1, 1, 1} + * ⇒ step 2 and base 1 can be preserved. + */ +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("loop header at 2, header_count is 2") +__msg("loop header at 2, widening r0 to 0x8000000000000000..0x7fffffffffffffff (s32 1..3) step 2") +__msg("2: R0=scalar({{.*}}step=1+2)") +__naked void post_cond_jne32_signed_boundary(void) +{ + asm volatile (" \ + r0 = %[initial] ll; \ +1: w0 += 2; \ + if w0 != 5 goto 1b; \ + exit; \ +" : + : __imm_const(initial, ITER_S64_MIN + 1) + : __clobber_all); +} + +/* The pre-condition also visits the header with the terminating value 3. */ +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("loop header at 1, header_count is 4") +__msg("loop header at 1, widening r0 to 0..3 (s32 0..3) step 1") +__msg("loop header at 1, clamping r0") +__msg("4: R0=3") +__naked void pre_cond_je32(void) +{ + asm volatile (" \ + w0 = 0; \ +1: if w0 == 3 goto 2f; \ + w0 += 1; \ + goto 1b; \ +2: exit; \ +" ::: __clobber_all); +} + +/* ALU32 keeps r0 in [0, U32_MAX], so the 64-bit comparison never becomes false. */ +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("loop header at 4, can't compute iterations count") +__naked void post_cond_alu32_jmp64(void) +{ + asm volatile (" \ + w0 = 0; \ + r1 = 0x100000003 ll; \ + r9 = 0; \ +1: " + LIMIT_ITERATIONS + "w0 += 1; \ + if r0 != r1 goto 1b; \ +2: exit; \ +" ::: __clobber_all); +} + +/* The signed 32-bit comparison is always true, even when r0 exceeds INT32_MAX. */ +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("loop header at 2, can't compute iterations count") +__naked void post_cond_alu64_jmp32(void) +{ + asm volatile (" \ + r0 = %[initial]; \ + r9 = 0; \ +1: " + LIMIT_ITERATIONS + "r0 += 1; \ + if w0 s<= %[bound] goto 1b; \ +2: exit; \ +" : + : __imm_const(initial, INT32_MAX - 1), + __imm_const(bound, INT32_MAX) + : __clobber_all); +} + +/* ALU32 values above INT32_MAX remain positive in a signed 64-bit comparison. */ +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("loop header at 3, header_count is 3") +__msg("loop header at 3, widening r0 to 0xfffffffc..0xfffffffe (s32 -4..-2) step 1") +__naked void post_cond_alu32_jmp64_bounded(void) +{ + asm volatile (" \ + w0 = -4; \ + r1 = 0xffffffff ll; \ +1: w0 += 1; \ + if r0 s< r1 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* The negative 64-bit counter and its exit value fit in the signed 32-bit range. */ +SEC("xdp") +__success +__log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("loop header at 1, header_count is 3") +__msg("loop header at 1, widening r0 to -6..-2 step 2") +__naked void post_cond_alu64_jmp32_bounded(void) +{ + asm volatile (" \ + r0 = -6; \ +1: r0 += 2; \ + if w0 s< 0 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + SEC("xdp") __success __log_level(2) -- 2.53.0 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH bpf-next 2/2] selftests/bpf: tests for 32-bit scalar evolution bounds computation 2026-10-20 11:06 ` [PATCH bpf-next 2/2] selftests/bpf: tests for 32-bit scalar evolution bounds computation Eduard Zingerman @ 2026-10-20 11:35 ` bot+bpf-ci 0 siblings, 0 replies; 9+ messages in thread From: bot+bpf-ci @ 2026-10-20 11:35 UTC (permalink / raw) To: eddyz87, bpf, ast Cc: andrii, daniel, kernel-team, yonghong.song, eddyz87, ast, andrii, daniel, martin.lau, eddyz87, yonghong.song, mason, ihor.solodrai [-- Attachment #1: Type: text/plain, Size: 2397 bytes --] > selftests/bpf: tests for 32-bit scalar evolution bounds computation TL;DR: The post_cond_jne_neg_step log expectation update belongs in the earlier "support 32-bit linear scalar evolution" patch; as is, that selftest would fail at that commit, breaking bisectability. > diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c > --- a/tools/testing/selftests/bpf/progs/verifier_scev.c > +++ b/tools/testing/selftests/bpf/progs/verifier_scev.c [ ... ] > @@ -1549,7 +1592,7 @@ __msg_next(" r0=(+ r0 -1) / (linear (+ r0 -1) -1)") > __msg("loop header at 1, header_count is 3 ") > __msg("loop header at 1, widening r0 to 1..3 step 1") > __msg("1: R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,var_off=(0x0; 0x3)) loop_stack=1") > -__msg("loop header at 1, clamping r0 to 1..2 step 1") > +__msg("loop header at 1, clamping r0 to 1..2 (s32 1..2) step 1") > __msg("processed 5 insns") > __naked void post_cond_jne_neg_step(void) This expectation update is only needed because of the log format change in the preceding commit 7c8f85ad75e9 ("bpf: support 32-bit linear scalar evolution"). That commit added log_bounds(), which appends an s32 range whenever bounds->r32.size < U32_MAX: if (bounds->r32.size < U32_MAX) { bpf_log(log, " (s32 "); ... In bpf_clamp_scev_regs() the 32-bit bounds are always intersected with the register's current r32: bounds.r32 = cnum32_intersect(reg->r32, bounds.r32) For the 64-bit post_cond_jne_neg_step loop this gives 1..2, so the clamp line becomes "loop header at 1, clamping r0 to 1..2 (s32 1..2) step 1". At 7c8f85ad75e9, verifier_scev.c still expects: "loop header at 1, clamping r0 to 1..2 step 1" That string is not a substring of the new output, so verifier_scev/post_cond_jne_neg_step would fail at that commit. The same commit already updated the matching expectation in verifier_stack_ptr.c (stack_ptr_subrange_in_loop: "clamping r7 to -64..-16 (s32 -64..-8) step 8") but not this one. Should this one-line hunk move into 7c8f85ad75e9 so test_progs passes at every commit in the series? --- AI reviewed your patch. Please fix the bug or email reply why it's not a bug. See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md CI run summary: https://github.com/kernel-patches/bpf/actions/runs/39413885357 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH bpf-next 0/2] bpf: support 32-bit linear scalar evolution 2026-10-20 11:06 [PATCH bpf-next 0/2] bpf: support 32-bit linear scalar evolution Eduard Zingerman 2026-10-20 11:06 ` [PATCH bpf-next 1/2] " Eduard Zingerman 2026-10-20 11:06 ` [PATCH bpf-next 2/2] selftests/bpf: tests for 32-bit scalar evolution bounds computation Eduard Zingerman @ 2026-10-20 21:00 ` patchwork-bot+netdevbpf 2 siblings, 0 replies; 9+ messages in thread From: patchwork-bot+netdevbpf @ 2026-10-20 21:00 UTC (permalink / raw) To: Eduard Zingerman; +Cc: bpf, ast, andrii, daniel, kernel-team, yonghong.song Hello: This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <ast@kernel.org>: On Tue, 20 Oct 2026 04:06:25 -0700 you wrote: > Support scalar evolution widening for loops like: > > w0 = 0; > l: w0 += 1; > if w0 != 3 goto l; > exit; > > [...] Here is the summary with links: - [bpf-next,1/2] bpf: support 32-bit linear scalar evolution https://git.kernel.org/bpf/bpf-next/c/df4761bd441c - [bpf-next,2/2] selftests/bpf: tests for 32-bit scalar evolution bounds computation https://git.kernel.org/bpf/bpf-next/c/d4394fc6a1ed You are awesome, thank you! -- Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2026-10-20 21:07 UTC | newest] Thread overview: 9+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2026-10-20 11:06 [PATCH bpf-next 0/2] bpf: support 32-bit linear scalar evolution Eduard Zingerman 2026-10-20 11:06 ` [PATCH bpf-next 1/2] " Eduard Zingerman 2026-10-20 11:35 ` bot+bpf-ci 2026-10-20 21:00 ` Alexei Starovoitov 2026-10-20 21:06 ` Eduard Zingerman 2026-10-20 11:38 ` sashiko-bot 2026-10-20 11:06 ` [PATCH bpf-next 2/2] selftests/bpf: tests for 32-bit scalar evolution bounds computation Eduard Zingerman 2026-10-20 11:35 ` bot+bpf-ci 2026-10-20 21:00 ` [PATCH bpf-next 0/2] bpf: support 32-bit linear scalar evolution patchwork-bot+netdevbpf
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.