Re: [RFC bpf-next 3/6] bpf: support low-32 subreg scalar linking for zero-extending movs

[Eduard Zingerman <eddyz87@gmail.com>]

On Fri, 2026-08-14 at 16:19 -0700, Vineet Gupta wrote:
> Problem
> =======
> Currently register equality tracking and propagation only works for full
> 64-bits (with additional constant offset). It is missing the
> relationship: "these two regs share only their low 32-bits".
> 
> An illustrative snippet:
> 
> >  r6 = ...                    /* full 64-bit unknown */
> >  w7 = w6                     /* 32-bit zero-extend mov from wide src */
> >  if w6 != 0 goto .Lxx        /* branch not taken, src narrowed */
> >  if w7 == 0 goto .Lok   <-- missing
> 
> It works if the register is narrow to begin with, e.g.
> >  r6 = *(u32 *)(...)
> 
> Rephrased in verifier speak:
> 
> The linked-scalar equality relation sync_linked_regs() maintains is full
> 64-bit only; there is no subregister (low-32) equality link.
> A 32-bit mov (w1 = w2) is therefore either promoted to a full-64-bit link
> when the source is provably u32, or the link is dropped entirely when the
> wider source has unknown high bits. A later narrowing of the source to its
> low 32 bits never reaches dst, causing safe programs to be rejected. Note that
> the ADD_CONST32 machinery only applies to += const offset, not to equality.
> 
> This was seen with bpf-gcc codegen that tends to reuse "w0 = idx" for
> "return 0" on an idx==0 path, for bpf_loop callbacks.
> 
> Solution
> ========
>  - Introduce a low-32-only link, BPF_FLAG_SUBREG_ZEXT, added to BPF_FLAG_LINK.
>  - For a wide-source 32-bit mov, mark dst with BPF_FLAG_SUBREG_ZEXT instead
>    of clearing it (when src carries a scalar id).
>  - On a later low-32 narrowing sync_linked_regs() re-derives such a register as
>    the zero-extension of the base's low 32 bits: it copies the base (keeping its
>    precise low-32 tnum) and re-applies zext_32_to_64() -- the same helper the
>    32-bit mov used -- which is sound even when the source has unknown high bits.
>    This is applied only when neither side carries an ADD_CONST delta (the
>    combined subreg+delta case is not modeled).
>  - Sites that group a subreg-linked register by its scalar id compare ->id
>    directly: no masking is needed, since BPF_FLAG_SUBREG_ZEXT lives in
>    ->flags.
> 
> The reconstruction copies the base wholesale, so it must put back the fields
> that identify reg rather than known_reg -- ->id and, now, the link flag. This
> mirrors what the ADD_CONST arm below already does ("Must preserve off and id,
> otherwise another sync_linked_regs() will be incorrect"). Dropping the flag
> while keeping the ->id would be worse than losing the link: the register would
> claim a full 64-bit equality with a base whose high bits are unknown, and the
> next sync driven by it would copy a narrowed low-32 value straight onto the
> base's high half.
> 
> The link_flags_match() helper added by the previous patch is widened from
> BPF_FLAG_ADD_CONST to BPF_FLAG_LINK, so regs_exact() -- and through it
> states_maybe_looping() -- discriminates the new flavour as well. regsafe()
> additionally checks it early, before the explore_alu_limits and !precise
> short-circuits, which the helper's call site below them does not cover.
> 
> Note: the sync_linked_regs() reconstruction is wrapped in an extra block that
> looks redundant here. It is a placeholder for the sign-extension counterpart
> patch, which turns it into the else arm of an if/else on the link flavour;
> keeping it now avoids re-indenting the whole body there.
> 
> Results
> =======
> Improves verifier tracking (seen in the next selftest).
> selftest runs:
>  - clang: no new regressions (-mcpu=v3 and v4)
>  - bpf-gcc: no new regressions; the measurable selftest pass improvements
>    come with the sign-extension counterpart patch.
> 
> Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
> ---

As a general comment, please make the commit messages and comments
less verbose.

...

> diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
> index d3105b9a9965..ef71999c4695 100644
> --- a/kernel/bpf/states.c
> +++ b/kernel/bpf/states.c
> @@ -490,6 +490,9 @@ static int clean_verifier_state(struct bpf_verifier_env *env,
>   *
>   * Only meaningful when rold carries an id: the flags are only ever set
>   * together with one, so rold->id == 0 implies none of them is set.
> + *
> + * BPF_FLAG_LINK covers every flavour, so this widens automatically as new
> + * ones are added.
>   */
>  static bool link_flags_match(const struct bpf_reg_state *rold,
>  			     const struct bpf_reg_state *rcur)
> @@ -497,7 +500,7 @@ static bool link_flags_match(const struct bpf_reg_state *rold,
>  	if (!rold->id)
>  		return true;
>  
> -	return (rold->flags & BPF_FLAG_ADD_CONST) == (rcur->flags & BPF_FLAG_ADD_CONST);
> +	return (rold->flags & BPF_FLAG_LINK) == (rcur->flags & BPF_FLAG_LINK);
>  }
>  
>  static bool regs_exact(const struct bpf_reg_state *rold,
> @@ -554,6 +557,24 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
>  
>  	switch (base_type(rold->type)) {
>  	case SCALAR_VALUE:
> +		/*
> +		 * A low-32-bit-only link has different sync_linked_regs()
> +		 * semantics than a full/ADD_CONST equality. check_scalar_ids()
> +		 * only ever sees the plain ->id and never looks at ->flags, so a
> +		 * mismatch must be rejected explicitly.
> +		 * Check it here, before the explore_alu_limits and !precise
> +		 * short-circuits below (neither of which tests it). Note the
> +		 * pre-existing BPF_FLAG_ADD_CONST check sits after those
> +		 * short-circuits instead. The argument for checking early
> +		 * applies to it equally, but moving it makes regsafe() stricter
> +		 * on a path that predates this series, which is a pruning change
> +		 * that wants measuring on its own; it is deliberately left
> +		 * alone here.
> +		 */
> +		if (rold->id &&
> +		    (rold->flags & BPF_FLAG_SUBREG_ZEXT) != (rcur->flags & BPF_FLAG_SUBREG_ZEXT))
> +			return false;
> +

Why is this check here? Isn't it covered by the changes in link_flags_match()?

>  		if (env->explore_alu_limits) {
>  			/* explore_alu_limits disables tnum_in() and range_within()
>  			 * logic and requires everything to be strict
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 93e69116ca9e..8a802d49d0a4 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

...

> @@ -15076,15 +15076,42 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
>  					if (insn->off == 0) {
>  						bool is_src_reg_u32 = get_reg_width(src_reg) <= 32;
>  
> -						if (is_src_reg_u32)
> +						/*
> +						 * *dst_reg = *src_reg below copies src's id into dst, a
> +						 * full 64-bit equality link. That is only sound when src
> +						 * fits in u32: a 32-bit mov zero-extends dst, so for a
> +						 * wider src the link would let sync_linked_regs()
> +						 * propagate dst's [0, U32_MAX] range back onto src's
> +						 * unknown high bits. For a wide src drop the full link
> +						 * and form a low-32-only BPF_FLAG_SUBREG_ZEXT link instead, so a
> +						 * later narrowing of src's low 32 bits still reaches dst.
> +						 *
> +						 * wide_subreg_link gates that low-32 link and excludes:
> +						 *  - a self-mov (w6 = w6): src == dst, nothing to link;
> +						 *    forming one would only mint an id and a spurious
> +						 *    self-link (inert in sync_linked_regs()).
> +						 *  - an ADD_CONST-linked src (rX = base + K):
> +						 *    assign_scalar_id_before_mov() would clear its
> +						 *    base+delta link, and a combined subreg+delta link
> +						 *    isn't modeled anyway (sync_linked_regs() skips it).
> +						 * In both cases src is left untouched and dst is cleared,
> +						 * as before this feature.
> +						 */
> +						bool wide_subreg_link = !is_src_reg_u32 &&
> +							src_reg != dst_reg &&
> +							!(src_reg->flags & BPF_FLAG_ADD_CONST);

Why checking `!(src_reg->flags & BPF_FLAG_ADD_CONST)`?
assign_scalar_id_before_mov resets() src_reg->flags and assigns
a fresh src_reg->id when `src_reg->flags & BPF_FLAG_ADD_CONST`.
The existing code already breaks ADD_CONST32 relationship for src
on mov, let's be symmetric here unless there is a good reason not to.

By the way, does assign_scalar_id_before_mov() need to handle
BPF_FLAG_SUBREG_ZEXT? It appears that it is fine to share id
if `src_reg->flags & BPF_FLAG_SUBREG_ZEXT`,
would be nice to drop a (short) comment there.

> +
> +						if (is_src_reg_u32 || wide_subreg_link)
>  							assign_scalar_id_before_mov(env, src_reg);
>  						*dst_reg = *src_reg;
> -						/* Make sure ID is cleared if src_reg is not in u32
> -						 * range otherwise dst_reg min/max could be incorrectly
> -						 * propagated into src_reg by sync_linked_regs()
> -						 */
> -						if (!is_src_reg_u32)
> -							clear_scalar_id(dst_reg);
> +						if (!is_src_reg_u32) {
> +							if (wide_subreg_link && src_reg->id) {
> +								/* ->id already copied above */
> +								dst_reg->flags |= BPF_FLAG_SUBREG_ZEXT;
> +							} else {
> +								clear_scalar_id(dst_reg);
> +							}
> +						}

Nit: I'd avoid excessive indentation:

						if (wide_subreg_link && src_reg->id)
							dst_reg->flags |= BPF_FLAG_SUBREG_ZEXT;
						else if (!is_src_reg_u32)
							clear_scalar_id(dst_reg);


>  					} else {
>  						/* case: W1 = (s8, s16)W2 */
>  						bool no_sext = reg_umax(src_reg) < (1ULL << (insn->off - 1));
> @@ -15953,6 +15980,52 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
>  			continue;
>  		if (reg->id != known_reg->id)
>  			continue;
> +		/*
> +		 * A low-32 linked register shares only the base's low 32 bits;
> +		 * the flag says how its high bits are derived. For
> +		 * BPF_FLAG_SUBREG_ZEXT they are zero (32-bit zero-extending mov).
> +		 * Rebuild it from known_reg's low 32 bits accordingly, but only
> +		 * when neither side carries an ADD_CONST delta -- with a delta
> +		 * the low bits differ from the base by that delta and the combined
> +		 * subreg+ADD_CONST reconstruction isn't modeled here, so leave reg
> +		 * unchanged (sound, just less precise).
> +		 */
> +		if (reg->flags & BPF_FLAG_SUBREG_ZEXT) {
> +			if (!((reg->flags | known_reg->flags) & BPF_FLAG_ADD_CONST)) {
> +				{
> +					u32 saved_id = reg->id;

Right above this hunk reg->id == known_reg->id relationship is already
established, why is saved_id necessary?

> +					u8 saved_subreg = reg->flags & BPF_FLAG_SUBREG_ZEXT;
> +
> +					/*
> +					 * reg = zext32(known_reg): its low 32 bits come from
> +					 * the base and its high 32 are zero. Rather than
> +					 * rebuild the value by hand, copy the base (keeping
> +					 * its precise low-32 tnum) and re-clear the high half
> +					 * with the same zext_32_to_64() the 32-bit
> +					 * zero-extending mov used -- the zero high half is a
> +					 * fallout of it, so no dedicated reconstruction is
> +					 * needed.
> +					 */
> +					*reg = *known_reg;
> +					reg->id = saved_id;
> +					reg->flags = (reg->flags & ~BPF_FLAG_SUBREG_ZEXT) | saved_subreg;

This would look much simpler with bitfields.

> +					zext_32_to_64(reg);
> +					reg_bounds_sync(reg);
> +				}
> +				if (e->is_reg)
> +					mark_reg_scratched(env, e->regno);
> +				else
> +					mark_stack_slot_scratched(env, e->spi);
> +			}
> +			continue;
> +		}
> +		/*
> +		 * Dest-driven direction (known_reg is subreg-linked, reg is not):
> +		 * copying known_reg's low-32-only state into a full register would
> +		 * be unsound, so leave reg unchanged.
> +		 */
> +		if (known_reg->flags & BPF_FLAG_SUBREG_ZEXT)
> +			continue;
>  		/*
>  		 * Skip mixed 32/64-bit links: the delta relationship doesn't
>  		 * hold across different ALU widths.