Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs

[Eduard Zingerman <eddyz87@gmail.com>]

On Wed, 2026-09-16 at 17:30 -0700, Alexei Starovoitov wrote:
> On Wed, Sep 16, 2026 at 5:08 PM Vineet Gupta <vineet.gupta@linux.dev> wrote:
> > 
> > It ended up with full testsuite run parity - after 4 incremental patches.
> > But the pattern of all those patches was adding some predicate /
> > special-casing to reg->add_const
> > 
> > hunk 1
> > 
> > -       if (src_reg->add_const)
> > +       if (src_reg->add_const && src_reg->delta)
> 
> why? It should not.
> My point is that zero is not special.
> It should be handled within the current framework.
> All these extra hunks are not correct.
> ADD_CONST_32 logic should work for delta == 0 just like
> it works for delta == 1.

After thinking about it some more, I agree that having an orthogonal
encoding would be nice. However, it appears that the split should be
somewhat different:

  struct bpf_reg_state {
    ...
    s32 delta;
    u32 id;
    enum id_link_kind { full, zext, sext } link_kind;
    ...
  }

Where:
- id == 0 => no id link
- full => all 64-bits of the register are identical to
          all 64-bits of a scalar value `id' (let's call it X).
          ∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
- zext => lower 32-bits of the register are identical to
          lower 32-bits of a scalar value X,
          upper 32-bits of the register are null.
          ∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
- sext => lower 32-bits of the register are identical to
          lower 32-bits of a scalar value X,
          upper 32-bits of the register are either 0 or 1,
          depending on the bit 31 value.
          ∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)

The reason for such subdivision is that:

  (X + delta) % 32 == X % 32 + delta % 32 == X % 32 + delta iff delta < 2^32

Meaning that a non-zero delta can still be used to infer the state of
the lower 32-bits, e.g.:
- if  r1 = (X + delta) % 32
- and r2 = X
- and there is a comparison `if r1 < 42 goto ...`

This comparison adds constraints on lower bits of r1,
and it is correct to transfer these constraints to lower bits of r2
by subtracting delta from r1 and using lower bits of the result.