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 <[email protected]> > ---
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 <[email protected]> ... > @@ -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(®->r64, prev.r64); > + cnum32_intersect_with(®->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) ...
