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

[Eduard Zingerman]

On Tue, 2026-10-20 at 09:18 -0700, Vineet Gupta wrote:
> Linked-scalar equality is full-64-bit only, so a 32-bit mov from a source
> with unknown high bits drops the relationship:
> 
>   r6 = ...              /* full 64-bit unknown */
>   w7 = w6               /* 32-bit zero-extending mov */
>   if w6 != 0 goto ...   /* not taken: r6's low 32 bits are 0 */
>   if w7 == 0 goto ...   /* not deduced today */
> 
> Record it with the kind the previous patch already provides.
> BPF_REG_LINK_ZEXT, which is what BPF_ADD_CONST32 became, says exactly
> what the mov did:
> 
> 	dst == (u32)(src + 0)
> 
> However this changes the pre-existing semantics slightly:
> 
> 	today    reg == base + delta, base known to fit u32
> 	here     reg == (u32)(base + delta), for any base width
> 
> Every link that forms today is over a narrow base, where the two
> readings coincide, so nothing reachable now behaves differently; what is
> new is that a wide base forms a link where it was previously refused
> outright.
> 
> This is done by dropping the guard:
> 
> 	if (alu32 && (dst_umax > U32_MAX))
> 		goto clear_id;
> 
> What the wide base costs is invertibility of the high half: dst pins
> src's low 32 bits and says nothing about the rest. So sync_linked_regs()
> drives such a link forwards only.
> 
> That also changes how a member is updated. Where the old code replaced
> it with the base plus the delta difference, it now intersects the two: a
> one-directional link leaves the member free to know more about itself
> than the base does, and overwriting would discard that.
> 
> Intersecting can come out empty, when the two sides contradict -- the
> link pins only the low 32 bits, so the verifier can walk a branch where
> they disagree about the rest. Empty is the correct answer, and a bad
> shape to leave behind: reg_bounds_sync() declines to touch an empty
> range and the next reg_bounds_sanity_check() reports a verifier bug that
> is not one. Keep the pre-intersect state instead. Without that,
> 
> 	w7 = w6;		/* r7 == (u32)r6 */
> 	if w7 != 5 goto out;	/* r7 == 5 */
> 	if r6 != 7 goto out;	/* explored: r6 is wide and unknown */
> 	r9 = 0;
> 	r7 %= r9;		/* validates r7 without recomputing it */
> 
> prints a REG INVARIANTS VIOLATION and a WARNING from an ordinary socket
> filter. zext_contradiction_keeps_range_sane covers it, and discriminates
> only here: the later reverse-direction patch makes "if r6 != 7"
> statically false, so the branch is never walked at the tip.
> 
> The patch also allows delta composition, once. "w3 = w0; w3 -= 1" is
> ordinary codegen, and until now the subtract threw the link away: the
> mov gives every zero-extending link a kind, and the test that refuses a
> second delta could not tell a link that has one from a link that merely
> has a kind. Let the zero-extending link, and only it, compose a single
> 32-bit delta onto a delta of zero. The updated sub32_partial_overflow
> dump is this case, its register now rendering as id=N-1.
> 
> Composing any further is refused deliberately. Deltas are compared for
> equality, so a link that keeps accumulating them turns every value a
> loop reaches into a state of its own: on arena_strsearch allowing a
> second delta costs 1176 -> 1751 insns and 102 -> 133 states, and
> allowing it onto a zero delta that an add produced rather than the mov
> still costs 1176 -> 1196. Neither buys a verdict.
> 
> Forming a link re-bases a wide source, since
> assign_scalar_id_before_mov() drops whatever link it carried; that costs
> precision only.
> 
> verifier_reg_equal's subreg_equality_2 becomes __success. It is the same
> link with a 64-bit compare on the member: "w2 < 9" bounds r3 over all 64
> bits, not just its low half, because the zero-extending mov leaves
> nothing above them.
> 
> Signed-off-by: Vineet Gupta <vineet.gupta@xxxxxxxxx>
> ---

Please revisit comments in this patch, maybe as a follow-up.
They are too wordy and, at times, hard to comprehend.

Acked-by: Eduard Zingerman <eddyz87@xxxxxxxxx>

...

> @@ -18485,6 +18534,27 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
>  			if (reg->link_kind == BPF_REG_LINK_ZEXT ||
>  			    known_reg->link_kind == BPF_REG_LINK_ZEXT)
>  				zext_32_to_64(reg);
> +			/*
> +			 * Intersect rather than overwrite. A BPF_REG_LINK_ZEXT
> +			 * link over a wide base does not propagate back, so the
> +			 * base can be wider than what @reg has already proved
> +			 * about itself; replacing it would lose that.
> +			 */
> +			cnum64_intersect_with(&reg->r64, prev.r64);
> +			cnum32_intersect_with(&reg->r32, prev.r32);
> +			reg->var_off = tnum_intersect(reg->var_off, prev.var_off);
> +			/*
> +			 * An empty intersection means the two sides contradict,
> +			 * so this path is unreachable. Say nothing rather than
> +			 * say it with an empty range: reg_bounds_sync() below
> +			 * refuses to touch one, and the first later
> +			 * reg_bounds_sanity_check() would report it as a
> +			 * verifier bug, which it is not. Keeping the wider
> +			 * pre-intersect state only costs precision on a path
> +			 * that cannot be taken.
> +			 */
> +			if (range_bounds_violation(reg))
> +				*reg = prev;

I'm not a fan, tbh.
As a followup, I'd suggest a wider refactoring:
- get rid of is_scalar_branch_taken() (or most of it?)
- branch unconditionally;
- apply regs_refine_cond_op() for every branch;
- apply sync_linked_regs() for every branch;
- check if one of the branches is has registers with empty ranges and
  avoid exploring it.

>  			reg_bounds_sync(reg);
>  		}
>  		if (e->is_reg)

...