Re: [syzbot] [bpf?] WARNING in reg_bounds_sanity_check

[Eduard Zingerman <eddyz87@gmail.com>]

On Fri, 2025-07-04 at 10:26 -0700, Eduard Zingerman wrote:
> On Fri, 2025-07-04 at 19:14 +0200, Paul Chaignon wrote:
> > On Thu, Jul 03, 2025 at 11:54:27AM -0700, Eduard Zingerman wrote:

[...]

> > > I think is_branch_taken() modification should not be too complicated.
> > > For JSET it only checks tnum, but does not take ranges into account.
> > > Reasoning about ranges is something along the lines:
> > > - for unsigned range a = b & CONST -> a is in [b_min & CONST, b_max & CONST];
> > > - for signed ranged same thing, but consider two unsigned sub-ranges;
> > > - for non CONST cases, I think same reasoning can apply, but more
> > >   min/max combinations need to be explored.
> > > - then check if zero is a member or 'a' range.
> > > 
> > > Wdyt?
> > 
> > I might be missing something, but I'm not sure that works. For the
> > unsigned range, if we have b & 0x2 with b in [2; 10], then we'd end up
> > with a in [2; 2] and would conclude that the jump is never taken. But
> > b=8 proves us wrong.
> 
> I see, what is really needed is an 'or' joined mask of all 'b' values.
> I need to think how that can be obtained (or approximated).

I think the mask can be computed as in or_range() function at the
bottom of the email. This gives the following algorithm, if only
unsigned range is considered:

- assume prediction is needed for "if a & b goto ..."
- bits that may be set in 'a' are or_range(a_min, a_max)
- bits that may be set in 'b' are or_range(b_min, b_max)
- if computed bit masks intersect: both branches are possible
- otherwise only false branch is possible.

Wdyt?

[...]

---

#include <stdint.h>
#include <stdio.h>

static uint64_t or_range(uint64_t lo, uint64_t hi)
{
  uint64_t m;
  uint32_t i;

  m = hi;
  i = 0;
  while (lo != hi) {
    m |= 1lu << i;
    lo >>= 1;
    hi >>= 1;
    i++;
  }
  return m;
}

static uint64_t or_range_simple(uint64_t lo, uint64_t hi)
{
  uint64_t m = 0;
  uint64_t v = 0;

  for (v = lo; v <= hi; v++)
    m |= v;
  return m;
}

int main(int argc, char *argv[])
{
  int max = 0x1000;
  for (int lo = 0; lo < max; lo++) {
    for (int hi = lo; hi < max; hi++) {
      uint64_t expected = or_range_simple(lo, hi);
      uint64_t result = or_range(lo, hi);

      if (expected != result) {
        printf("mismatch: %x..%x -> expecting %lx, result %lx\n",
               lo, hi, expected, result);
        return 1;
      }
    }
  }
  printf("all ok\n");
  return 0;
}