Re: [PATCH bpf-next 29/37] bpf: Count '!=' across 0 in 32 bits and loops that go down

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [Medium] bpf: 64-bit JLT/JLE on 32-bit counter in compute_max_iters() lacks jmp32
- [Medium] bpf: compute_max_iters() zeroes bound_val before checking konst
- [Low] bpf: compute_max_iters() misses downward BPF_JLE when initial equals bound
--

commit 08a1779026bb125181a7c2d2c0167baa7768249b
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Count '!=' across 0 in 32 bits and loops that go down

This commit teaches BPF scalar evolution to compute iteration counts for
32-bitBPF_JNE loops that cross zero and for downward loops tested with
unsigned BPF_JLT or BPF_JLE latches by rewriting the latter to signed
BPF_JSGE comparisons against zero.

> diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
> index 9ddaae03ac351..70d15449eebe1 100644
> --- a/kernel/bpf/scev.c
> +++ b/kernel/bpf/scev.c
> @@ -2738,8 +2738,9 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
>  	struct scev *scev = env->scev;
>  	struct scev_value initial_val, step_val, bound_val;
>  	u64 step, bound, initial, total_change, backedge_taken_count;
> -	bool konst;
> +	struct linear_latch counted;
>  	u8 op = latch->op;
> +	bool konst, sign32 = latch->jmp32 && is_signed_op(op);
>  
>  	iters->iv_reg = -1;
>  
> @@ -2761,6 +2762,23 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
>  
>  	if (!scev_value_is_const(&step_val))
>  		return false;
> +	/*
> +	 * 'i >= 0 && i < 128' is one unsigned test. A counter that goes down stays below 128.
> +	 * The loop ends when it gets below 0. A 64-bit jump compares all 64 bits of the bound.
> +	 * The latch of the caller stays as it is: same_latch() compares what the prog tests.
> +	 */
> +	if ((op == BPF_JLT || op == BPF_JLE) && initial_val.ptr_reg < 0 &&
> +	    (latch->jmp32 || latch->zext32 ?
> +	     (s32)step_val.umin < 0 && initial_val.u32_min < bound_val.u32_max &&
> +	     (latch->jmp32 ? bound_val.u32_max : bound_val.umax) <= S32_MAX :
> +	     (s64)step_val.umin < 0 && initial_val.umin < bound_val.umax &&
> +	     bound_val.umax <= S64_MAX)) {

[Severity: Low]
In compute_max_iters() in kernel/bpf/scev.c, both BPF_JLT and BPF_JLE are
checked with strict inequality between the minimum initial value and maximum
bound (initial_val.u32_min < bound_val.u32_max or
initial_val.umin < bound_val.umax).

When op == BPF_JLE and a downward counter starts at a value equal to the
bound (initial_val.u32_min == bound_val.u32_max or
initial_val.umin == bound_val.umax), this condition evaluates to false and
the latch is not rewritten to BPF_JSGE. Downward BPF_JLE is then rejected by
compute_backedge_taken_count() and compute_backedge_taken_max().

Should the comparison allow equality when op == BPF_JLE?

> +		counted = *latch;
> +		latch = &counted;
> +		op = latch->op = BPF_JSGE;
> +		bound_val = (struct scev_value){ .ptr_reg = -1 };
> +		sign32 = true;
> +	}

[Severity: Medium]
When a 64-bit unsigned BPF_JLT or BPF_JLE jump tests a 32-bit downward
counter (latch->zext32 is true and latch->jmp32 is false) with
bound_val.umax <= S32_MAX, compute_max_iters() in kernel/bpf/scev.c rewrites
counted.op to BPF_JSGE with bound_val = 0 and sets sign32 = true, but leaves
counted.jmp32 as false.

When compute_max_iters() subsequently calls compute_backedge_taken_max() or
latch_false_until(), both pass latch to latch_domain() with sign = true,
latch->jmp32 = false, and latch->zext32 = true:

kernel/bpf/scev.c:latch_domain() {
	...
	bias = sign ? 1ULL << 63 : 0;
	d->bmin = (sign ? (u64)bound->smin : bound->umin) ^ bias;
	d->bmax = (sign ? (u64)bound->smax : bound->umax) ^ bias;
	if (latch->zext32) {
		/* zero extended, so it is not negative */
		d->imin = initial->u32_min ^ bias;
		d->imax = initial->u32_max ^ bias;
		d->lo = bias;
		d->hi = bias + U32_MAX;
		return;
	}
}

Because bound is 0, latch_domain() sets d->bmin = bias and d->lo = bias, and
uses u32_min/u32_max instead of s32_min/s32_max.

In the non-constant case (!konst), compute_backedge_taken_max() then checks:

	case BPF_JGE:
	case BPF_JSGE:
		if (!down ||
		    check_add_overflow(div64_u64(d.imax - d.bmin, step), 1, &cnt) ||
		    d.bmin < d.lo || step > d.bmin - d.lo)
			return false;

Since d.bmin - d.lo is 0 and step >= 1, step > d.bmin - d.lo is always true
and compute_backedge_taken_max() unconditionally returns false.

In the constant case (konst), latch_false_until() computes
div64_u64(d.imin - d.lo, -step), which evaluates to initial_val.u32_min / -step
(i.e. backedge_taken_count - 1, the distance to 0 rather than the distance to
S32_MIN), causing bpf_compute_loop_iters() to reject multi-backedge loops
when another backedge has a different latch.

Should counted.jmp32 also be set to latch->jmp32 || latch->zext32 when
rewriting the latch to BPF_JSGE?

>  	konst = scev_value_is_const(&initial_val) && scev_value_is_const(&bound_val);

[Severity: Medium]
In compute_max_iters() in kernel/bpf/scev.c, bound_val is overwritten with
zero before konst is computed from scev_value_is_const(&initial_val) &&
scev_value_is_const(&bound_val).

If a downward BPF_JLT or BPF_JLE loop has a constant initial_val and a
non-constant range bound_val (for example initial_val = 10 and
bound_val in [5, 20]), scev_value_is_const(&bound_val) checks the overwritten
zero bound_val and evaluates konst to true.

As a result, compute_max_iters() skips compute_backedge_taken_max() (leaving
iters->iv_reg as -1) and sets:

	iters->min_header_count = konst && loop->exits_cnt == 1 ? iters->max_header_count : 0;

This sets min_header_count to max_header_count even when the original
bound_val range includes values at or below initial_val that cause the loop
to exit on the first iteration. It also forces mixed-width latches
(!latch->zext32 && latch->jmp32) with non-zero upper 32 bits in initial_val
onto the constant path where they are rejected.

Should konst be evaluated before bound_val is overwritten?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261103234104.208239-1-alexei.starovoitov@gmail.com?part=29