From 32e962577d2d8a09fb09d4be2ddf96b82ae447c6 Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Tue, 20 Oct 2026 04:06:26 -0700 Subject: bpf: Support 32-bit linear scalar evolution 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 Signed-off-by: Alexei Starovoitov Link: https://patch.msgid.link/20261020-scev-32bit-v1-1-838f34f9f0cd@gmail.com --- include/linux/bpf_verifier.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/linux') diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 6606b341351e..5926f13ff43c 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -1896,7 +1896,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); -- cgit v1.2.3