Re: [PATCH v2 bpf-next 4/6] bpf: Simulate branches to prune based on range violations

Eduard Zingerman
2026-03-25T00:08:24Z

On Tue, 2026-03-24 at 19:59 -0400, Harishankar Vishwanathan wrote:

[...]

> > Also, it appears that tnum bounds checking functions are unnecessarily
> > restricted and should be implemented as follows:
> >
> > static bool const_tnum_out_of_sync_with_range_bounds(struct bpf_reg_state *reg)
> > {
> >
> > u64 tnum_umin = reg->var_off.value;
> > u64 tnum_umax = reg->var_off.value | reg->var_off.mask;
> > s64 tnum_smin = (s64)tnum_umin;
> > s64 tnum_smax = (s64)tnum_smax;
> >
> > // check that [tnum_umin, tnum_umax] and [reg->umin_value, reg->umax_value] intersect
> > // check that [tnum_smin, tnum_smax] and [reg->smin_value, reg->smax_value] intersect
> > return ...;
> > }
> >
> > Wdyt?
>
> I like the idea! If we do this, we should also rename the function to simply
> "tnum_range_mismatch" or something along those lines (as mentioned in
> the other thread),
> dropping the "const".
>
> Technically, the verifier should maintain the invariant that all domain
> pairs always have intersections. There are 10 domain pairs:
> u64_s64, u64_tnum, s64_tnum, u32_s32, u32_tnum, s32_tnum,
> u64_u32, u64_s32, u32_s64, s64_s32. We can have intersection checks
> for each of these pairs, or we can stick to the major ones, i.e. the top 6
> in this list.
>
> Checking for intersections was part of the original idea in the RFC
> for tnum_step()
> I had sent a while back [1], which was about detecting intersection between
> tnum and u64.
>
> Generally a simple check will be
> if (tmin > umax) || (tmax < umin) // no intersection
>
> The original idea in the RFC was to use tnum_step to make this check
> complete. Particularly, for cases like:
>
> t = x0x1 {1, 3, 9, 11}
> r = [4, 8] {4, 5, 6, 7, 8}
>
> The above check won't suffice. We can add the following check:
>
> if tnum_step(t, umin) > umax) // no intersection

Yes, this makes sense.

> Since tnum_step() has been upstreamed, maybe it is a good time to
> revisit the idea, and have a sound and complete intersection check?
> Or do you think that is overkill for this patch?
>
> Also, then, should this patch introduce domain checks for all 10 domain pairs?

I'd say we should check each and every but 10 sounds a bit scary.
Maybe do it in a straightforward way and see if it shows in perf
profile? Trying on a few large programs? …