Re: [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs

[Eduard Zingerman <eddyz87@gmail.com>]

On Tue, 2026-10-20 at 09:19 -0700, Vineet Gupta wrote:
> A 32-bit sign extension shares the source's low 32 bits too, filling the
> high half from bit 31:
>
>   r6 = ...              /* full 64-bit unknown */
>   r7 = (s32)r6          /* 32-bit sign-extending mov */
>   if w6 == -1 goto ...  /* taken: r6's low 32 bits are all ones */
>   ...                   /* r7 is -1, not deduced today */
>
> No constant k makes dst == (u32)(src + k) a sign extension, so this
> needs a third kind, BPF_REG_LINK_SEXT, driven by sext_32_to_64() where
> the zero-extending arm uses zext_32_to_64(). The enum already had room,
> so bpf_reg_state stays 80 bytes.
>
> Both work from the base's 32-bit range, which is what a 32-bit compare
> narrows; coerce_reg_to_size_sx() cannot serve, as it reads smin/smax,
> which straddle after such a compare. tnum_sext() is the counterpart to
> tnum_cast(), keeping the known low bits where a tnum_range() over the new
> bounds would not.
>
> sext_32_to_64() resets the register's base/step line; the comment there
> gives the arithmetic. Note it resets unconditionally, where
> coerce_reg_to_size_sx() and coerce_subreg_to_size_sx() return early when
> the extension is a provable no-op and keep the line. That costs a little
> precision in the same case here, which is not worth an extra branch on a
> path that has just rebuilt the value from the base.
>
> Unlike the zero-extending arm, the source's delta comes along. Both
> base + d and (u32)(base + d) have low half (base + d), so dst is
> (s32)(base + d) whichever the source was:
>
> 	w7 = w6;	/* BPF_REG_LINK_ZEXT, delta 0 */
> 	w7 += 5;	/* BPF_REG_LINK_ZEXT, delta 5 */
> 	r8 = (s32)r7;	/* BPF_REG_LINK_SEXT, delta 5 */
>
> keeps r8 tied to r6. sext_mov_inherits_delta pins it; without the
> inheritance the program is rejected. A self-mov can form a link here too,
> which is how a sign-extended int return lands.
>
> sync_linked_regs() needs no separate sext path: the differencing arm
> already copies the base and adds the delta difference, and which extension
> follows is just the member's kind. Where the base does fit 32 bits the
> reverse direction runs for both narrow kinds with the *zero* extension --
> the base is then below 2^32 and equal to the member's low half, whichever
> way the member filled its own high half.

The above paragraph is very hard to parse.
sync_linked_regs() does call sext_32_to_64().
Please re-read whatever comments and messages the machine generates.
For whatever reason the bias is towards a wall of text and complex
sentences. I do read those and it hurts. Asking my machine rewrite
your machine's text, such that I can understand it is very time consuming.

...

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index ce7016446936..dffcaa2e1392 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3763,7 +3763,7 @@ static void assign_scalar_id_before_mov(struct bpf_verifier_env *env,
>  	 * rY->id has special linked register already.
>  	 * Cleared it, since multiple rX += const are not supported.
>  	 */
> -	if (src_reg->link_kind)
> +	if (src_reg->link_kind && src_reg->link_kind != BPF_REG_LINK_SEXT)

Why is this rule relaxed only for SEXT?
Can it be relaxed for ZEXT/FULL as well?

>  		bpf_clear_scalar_id(src_reg);
>  	/*
>  	 * Ensure that src_reg has a valid ID that will be copied to
> @@ -6057,6 +6057,25 @@ static void zext_32_to_64(struct bpf_reg_state *reg)
>  	reg_set_urange64(reg, reg_u32_min(reg), reg_u32_max(reg));
>  }
>
> +/*
> + * The sign-extending counterpart. Signed bounds carry over directly because
> + * sign extension is monotonic over the signed 32-bit range.
> + */
> +static void sext_32_to_64(struct bpf_reg_state *reg)
> +{
> +	/*
> +	 * See comment at reg_step_check_unsigned(). Sign extension subtracts
> +	 * 2^32 from every value with bit 31 set, which preserves a residue
> +	 * mod step only when step divides 2^32, so the line cannot be kept.
> +	 * The zero-extending twin calls reg_step_check_unsigned(reg, 32) for
> +	 * the same reason; the unsigned form does not apply here because the
> +	 * result is not the low 32 bits but the low 32 bits moved.
> +	 */
> +	reg_step_reset(reg);
> +	reg->var_off = tnum_sext(reg->var_off, 4);
> +	reg_set_srange64(reg, reg_s32_min(reg), reg_s32_max(reg));
> +}
> +

Please use coerce_reg_to_size_sx(). You can improve it by doing:

  reg->var_off = tnum_sext(reg->var_off, 4);
  reg_set_srange64(reg, reg_s32_min(reg), reg_s32_max(reg));

>  /* truncate register to smaller size (in bytes)
>   * must be called with size < BPF_REG_SIZE
>   */
> @@ -17544,12 +17563,29 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
>  						return -EACCES;
>  					} else if (src_reg->type == SCALAR_VALUE) {
>  						bool no_sext;
> +						/*
> +						 * A 32-bit sign extension keeps the low 32
> +						 * bits, so dst shares them with whatever src
> +						 * shares them with. Both base + d and
> +						 * (u32)(base + d) have low half (base + d), so
> +						 * dst is (s32)(base + d) either way: inherit
> +						 * src's id and delta and record
> +						 * BPF_REG_LINK_SEXT.
> +						 */
> +						bool subreg_link =
> +							(insn->off >> 3) == 4 &&
                                                        ^^^^^^^^^^^^^^^^^^^^^
                                    please make this a bool variable is_sext32

> +							(src_reg != dst_reg || src_reg->id);
>
>  						no_sext = reg_umax(src_reg) < (1ULL << (insn->off - 1));
>  						if (no_sext)
>  							assign_scalar_id_before_mov(env, src_reg);
> +						else if (subreg_link && !src_reg->id &&
> +							 !tnum_is_const(src_reg->var_off))
> +							src_reg->id = ++env->id_gen;

I don't like how this code sidesteps assign_scalar_id_before_mov().

>  						*dst_reg = *src_reg;
> -						if (!no_sext)
> +						if (!no_sext && subreg_link && src_reg->id)
> +							dst_reg->link_kind = BPF_REG_LINK_SEXT;
> +						else if (!no_sext)
>  							bpf_clear_scalar_id(dst_reg);
>  						coerce_reg_to_size_sx(dst_reg, insn->off >> 3);
>  					} else {
> @@ -18485,17 +18521,29 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
>  		if (reg->id != known_reg->id)
>  			continue;
>  		/*
> -		 * A zero-extending link, spelled BPF_REG_LINK_ZEXT: the
> -		 * relation reg == (u32)(base + delta) does not invert once the
> -		 * base is wider than 32 bits, so the reverse direction is
> -		 * skipped.
> +		 * The reverse direction does not work for a narrow known_reg:
> +		 * it knows only its low 32 bits, which say nothing about a
> +		 * wider reg's high half. Neither (u32)(base + delta) nor
> +		 * (s32)(base + delta) inverts once the base is wider than 32
> +		 * bits.

Why is this "reverse direction"? what's "inverts"?

>  		 */
> -		if (known_reg->link_kind == BPF_REG_LINK_ZEXT &&
> +		if ((known_reg->link_kind == BPF_REG_LINK_ZEXT ||
> +		     known_reg->link_kind == BPF_REG_LINK_SEXT) &&
> +		    reg->link_kind != BPF_REG_LINK_ZEXT &&
> +		    reg->link_kind != BPF_REG_LINK_SEXT &&

On a second thought, it appears it would make sense to collapse FULL
and NONE into the same category. E.g. the above condition would become
known_reg->link_kind != FULL && reg->link_kind == FULL,
much clearer.

>  		    get_reg_width(reg) > 32)
>  			continue;
>  		/*
> -		 * Skip mixed 32/64-bit links: the delta relationship doesn't
> -		 * hold across different ALU widths.
> +		 * Skip a pair of differing kinds. Where BPF_REG_LINK_FULL meets
> +		 * a 32-bit kind the delta relationship genuinely does not hold:
> +		 * the deltas were added at different ALU widths.
> +		 * BPF_REG_LINK_ZEXT against BPF_REG_LINK_SEXT is not that case
> +		 * -- both are base + delta in the low 32 bits, so narrowing one
> +		 * really does narrow the other -- but that deduction is
> +		 * declined on purpose. It makes an int loop counter a fresh
> +		 * constant on every iteration, so no two iterations prune
> +		 * against each other and the program runs to the instruction
> +		 * limit. See sext_no_sync_from_zext_sibling.
>  		 */
>  		if (reg->link_kind && known_reg->link_kind &&
>  		    reg->link_kind != known_reg->link_kind)

Does this check skips propagation in the following case?

  w7 = w6              ; r6={NONE,0}, r7={ZEXT,0}
  r6 += 1              ; r6={FULL,1}
  if w6 != 5 goto ...

known_reg is r6 in this case, so:
ZEXT && FULL && ZEXT != FULL -> true, continue is hit.

...