* [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
2026-10-20 11:06 ` [PATCH bpf-next 2/2] selftests/bpf: tests for 32-bit scalar evolution bounds computation Eduard Zingerman
0 siblings, 2 replies; 6+ 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] 6+ 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
1 sibling, 2 replies; 6+ 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] 6+ 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
1 sibling, 1 reply; 6+ 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] 6+ 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; 6+ 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] 6+ 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; 6+ 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] 6+ 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; 6+ 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] 6+ messages in thread
end of thread, other threads:[~2026-10-20 11:38 UTC | newest]
Thread overview: 6+ 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 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
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.