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

[Eduard Zingerman <eddyz87@gmail.com>]

On Sat, 2026-09-26 at 14:34 +0000, sashiko-bot@kernel.org wrote:
> 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).

I'll add `|| cnum64_srange_overflow(in)` to the entry condition.

> 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.

> > +}