Re: [PATCH bpf-next 08/36] bpf: add cnum64_intersect_linear()

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: cnum64_intersect_linear over-expands intervals that wrap the signed boundary
--

commit 07e53bba30487c590757dc2ec233d2811a607b9a
Author: Eduard Zingerman <eddyz87@gmail.com>

bpf: add cnum64_intersect_linear()

This commit introduces cnum64_intersect_linear() to intersect a cnum64
interval with integers congruent to 'base' modulo 'step'. It tightens the
interval using signed bounds to keep residues consistent. This is a building
block for tracking scalar registers with values known to lie on a line.

> diff --git a/kernel/bpf/cnum.c b/kernel/bpf/cnum.c
> index 86142cb2aee5f..2bff2c7e0cdf5 100644
> --- a/kernel/bpf/cnum.c
> +++ b/kernel/bpf/cnum.c
[ ... ]
> @@ -118,3 +119,38 @@ struct cnum64 cnum64_cnum32_intersect(struct cnum64 a, struct cnum32 b)
>  	}
>  	return t;
>  }
> +
> +/* Intersect 'in' with the set of integers defined by equation 'base + step * k'. */
> +struct cnum64 cnum64_intersect_linear(struct cnum64 in, u16 base, u16 step)
> +{
> +	s64 smin = cnum64_smin(in);
> +	s64 smax = cnum64_smax(in);
> +	s64 lo, hi;
> +	u16 d;
> +
> +	if (step <= 1 || cnum64_is_empty(in))
> +		return in;
> +	/*
> +	 * Round smin up to the next value congruent to 'base' modulo 'step',
> +	 * i.e. increase smin by d = (base - smin) mod step:
> +	 *
> +	 *                 |<---- d ---->|
> +	 *     |-----------|=============|...
> +	 * base+step*k    smin       base+step*(k+1)
> +	 */
> +	d = imod(base - imod(smin, step), step);
> +	if ((u64)smax - (u64)smin < d)
> +		return CNUM64_EMPTY;
> +	lo = smin + d;
> +	/*
> +	 * Round smax down to the previous value congruent to 'base' modulo 'step',
> +	 * i.e. decrease smax by d = (smax - base) mod step:
> +	 *
> +	 *     |<--- d --->|
> +	 *  ...|===========|-------------|
> +	 * base+step*k    smax       base+step*(k+1)
> +	 */
> +	d = imod(imod(smax, step) - base, step);
> +	hi = smax - d;
> +	return cnum64_from_srange(lo, hi);

[Severity: Medium]
Does this code improperly expand intervals that wrap the signed boundary?

For such intervals, cnum64_smin() returns S64_MIN and cnum64_smax() returns
S64_MAX. The function then calculates 'lo' near S64_MIN and 'hi' near
S64_MAX, returning cnum64_from_srange(lo, hi).

This replaces a potentially small wrapping interval with a massive contiguous
range spanning nearly the entire 64-bit space, violating the intersection
property (A ∩ B ⊆ A). While this over-approximation is sound, it could cause
the verifier to lose precision and falsely reject valid BPF programs.

> +}

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260926-scev-minimal-rebase-v1-0-c8e5ab5ba79f@gmail.com?part=8