* [RFC bpf-next 0/6] bpf: track scalar equality across the low 32 bits
@ 2026-08-14 23:19 Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 1/6] bpf: turn bpf_reg_state->precise into a flags field [NFC] Vineet Gupta
` (5 more replies)
0 siblings, 6 replies; 7+ messages in thread
From: Vineet Gupta @ 2026-08-14 23:19 UTC (permalink / raw)
To: ast, daniel, andrii, eddyz87, memxor
Cc: martin.lau, song, yonghong.song, jolsa, emil, ihor.solodrai,
john.fastabend, shuah, bpf, linux-kernel, linux-kselftest,
Vineet Gupta
The verifier's linked-scalar machinery tracks register equality only for the
full 64 bits (optionally with a constant delta). There is no way to record
"these two registers share just their low 32 bits", so a 32-bit mov from a
source with unknown high bits has to drop the relationship entirely, and a
later narrowing of the source never reaches the destination:
| r6 = ... /* full 64-bit unknown */
| w7 = w6 /* 32-bit zero-extending mov */
| if w6 != 0 goto .Lxx /* not taken: r6's low 32 bits are 0 */
| if w7 == 0 goto .Lok <-- not deduced today
The same gap exists for the 32-bit sign extension and was the
motivation for this patchset.
| 0: (61) r2 = *(u32 *)(r1 +24)
| 1: (bf) r0 = (s32)r2
| 2: (56) if w2 != 0x0 goto pc+10 ; R2=0 (branch taken)
| ...
| 12: (95) exit
This matters more with bpf-gcc than clang: gcc emits far more sign extensions,
and the resulting rejections are real which show up in three ways
- callback exit codes rejected with "R0 ... should have been in [0, 1]"
- the errno-or-zero return pattern (verify_pkcs7_sig and many lsm.s progs)
where a value clamped to [-4095, 0] is re-widened to [S32_MIN, S32_MAX]
- and loops whose induction variable is sign-extended each iteration failing
with "The sequence of 8193 jumps is too complex".
This series adds a low-32-only equality link in two flavours: the high half
is either zero (zero-extending mov) or the sign-extension of the low field
(32-bit sign extension) and teaches sync_linked_regs() to rebuild the
destination accordingly.
1-2 NFC prep. Turn ->precise into a u8 flags field, then move the existing
linked-scalar flags out of the top bits of ->id into it. ->id becomes a
plain 32-bit identifier with no masking anywhere, which collapses
check_scalar_ids() to a single check_ids(). Because ->flags sits past
every memcmp() window used for state comparison, patch 2 also adds
link_flags_match() and calls it from regs_exact(), restoring the
discrimination the compound-id key used to provide for free.
3-4 The zero-extending flavour, BPF_FLAG_SUBREG_ZEXT, plus tests.
5-6 The sign-extending flavour, BPF_FLAG_SUBREG_SEXT, plus tests.
Sent as RFC mainly for the design questions below; the code is in shape.
Notes and open questions
========================
- An earlier version detected loop headers to decide when forming an in-loop
link was safe, but using Eduard's in works SCEV loop-analysis. However the
conclusion was that was not the right problem/solution as the ensuing issue
could be triggered in current codebase (w/o this series with a little tweak
of the test:
- regsafe() now checks the low-32 link flavour *above* the explore_alu_limits
and !precise short-circuits, while the pre-existing BPF_FLAG_ADD_CONST check
sits below them. The argument for checking early applies to both. Moving the
ADD_CONST one makes regsafe() stricter on a path that predates this series --
a pruning change worth measuring separately -- so it is left alone and the
asymmetry is called out in a comment. Opinions welcome.
- reconstruct_sext32() rebuilds var_off with tnum_range() over the low-32
signed bounds, so known bits that the range does not imply are lost. The
zero-extending arm keeps the base's exact low-32 tnum. Sound but asymmetric;
a follow-up could derive the tnum from tnum_subreg(src->var_off) instead.
- Only the 32-bit sign extension forms a link. (s8)/(s16) do not, so the flag
alone carries the width and no extra field is needed. They are not seen in
codegen so far.
Testing
=======
Baseline: bpf-next:
2026-08-14 f2aaa6215910 riscv, bpf: Fix missing sign-ext for signed 1-byte and 2-byte kfunc args
Full selftest runs with bpf-gcc and clang (-mcpu=v4).
- clang: no regressions (no improvements either)
- bpf-gcc:
Before: Summary: 635/5362 PASSED, 7786 SKIPPED, 115/412 FAILED
After : Summary: 644/5439 PASSED, 8506 SKIPPED, 106/350 FAILED
The measurable pass improvements come with the sign-extension patch;
the zero-extension one is groundwork plus its own test.
+ "... should have been in [0, 1], [-4095, 0]"
All 21 instances gone
+ of "The sequence of 8193 jumps is too complex."
Down from 7 to 3
+ One regression vs. baseline: iters/iter_obfuscate_counter:FAIL
It is now runaway to 1M, root-cause has been analysed and something
to do with with bpf-gcc's branch codegen and costing.
For completeness, full diff of bpf-gcc run vs. bpf-next baseline
1. Existing tests OK now
> #25/1 bpf_ip_check_defrag/v4:OK
> #25/2 bpf_ip_check_defrag/v6:OK
> #25 bpf_ip_check_defrag:OK
> #26/5 bpf_iter/task_tid:OK
> #26/6 bpf_iter/task_pid:OK
> #26/7 bpf_iter/task_pidfd:OK
> #26/8 bpf_iter/task_sleepable:OK
> #26/14 bpf_iter/tcp4:OK
> #26/15 bpf_iter/tcp6:OK
> #26/16 bpf_iter/udp4:OK
> #26/17 bpf_iter/udp6:OK
> #26/25 bpf_iter/bpf_hash_map:OK
> #26/37 bpf_iter/ksym:OK
> #26/38 bpf_iter/bpf_sockmap_map_iter_fd:OK
> #36 bpf_sockmap_map_iter_fd:OK
> #82/8 cgroup_xattr/read_cgroupfs_xattr:OK
> #82 cgroup_xattr:OK
> #112/2 dynptr/test_dynptr_data:OK
> #112/3 dynptr/test_dynptr_copy:OK
> #112/4 dynptr/test_dynptr_copy_xdp:OK
> #112/5 dynptr/test_dynptr_memset_zero:OK
> #112/6 dynptr/test_dynptr_memset_notzero:OK
> #112/7 dynptr/test_dynptr_memset_zero_offset:OK
> #112/8 dynptr/test_dynptr_memset_zero_adjusted:OK
> #112/9 dynptr/test_dynptr_memset_overflow:OK
> #112/10 dynptr/test_dynptr_memset_overflow_offset:OK
> #112/11 dynptr/test_dynptr_memset_readonly:OK
> #112/12 dynptr/test_dynptr_memset_xdp_chunks:OK
> #112/13 dynptr/test_ringbuf:OK
> #112/14 dynptr/test_skb_readonly:OK
> #112/15 dynptr/test_dynptr_skb_data:OK
> #112/16 dynptr/test_dynptr_skb_meta_data:OK
> #112/17 dynptr/test_dynptr_skb_meta_flags:OK
> #112/18 dynptr/test_adjust:OK
> #112/19 dynptr/test_adjust_err:OK
> #112/20 dynptr/test_zero_size_dynptr:OK
> #112/21 dynptr/test_dynptr_is_null:OK
> #112/22 dynptr/test_dynptr_is_rdonly:OK
> #112/23 dynptr/test_dynptr_clone:OK
> #112/25 dynptr/test_dynptr_skb_strcmp:OK
> #112/27 dynptr/test_probe_read_user_dynptr:OK
> #112/28 dynptr/test_probe_read_kernel_dynptr:OK
> #112/29 dynptr/test_probe_read_user_str_dynptr:OK
> #112/30 dynptr/test_probe_read_kernel_str_dynptr:OK
> #112/31 dynptr/test_copy_from_user_dynptr:OK
> #112/32 dynptr/test_copy_from_user_str_dynptr:OK
> #112/33 dynptr/test_copy_from_user_task_dynptr:OK
> #112/34 dynptr/test_copy_from_user_task_str_dynptr:OK
> #117 exe_ctx:OK
> #239/9 mem_rdonly_untrusted/mixed_mem_type:OK
> #239 mem_rdonly_untrusted:OK
> #418 setget_sockopt:OK
> #441/7 sockmap_basic/sockmap copy:OK
> #441/8 sockmap_basic/sockhash copy:OK
> #441 sockmap_basic:OK
> #605/16 verifier_global_ptr_args/anything_to_untrusted_mem:OK
> #605 verifier_global_ptr_args:OK
> #614/1 verifier_iterating_callbacks/unsafe_on_2nd_iter:OK
> #721/1 verify_pkcs7_sig/pkcs7_sig_from_map:OK
2. New tests added pass
> #622/25 verifier_linked_scalars/subreg_eq_zext_mov_narrow:OK
> #622/26 verifier_linked_scalars/zext_mov_keeps_add_const_src:OK
> #622/27 verifier_linked_scalars/zext_dest_driven_does_not_narrow_base:OK
> #622/28 verifier_linked_scalars/sext_linked_low_narrow_to_zero:OK
> #622/29 verifier_linked_scalars/sext_linked_separate_dest_narrow_to_zero:OK
> #622/30 verifier_linked_scalars/sext_narrow_branch_on_source:OK
> #622/31 verifier_linked_scalars/sext_narrow_copied_back:OK
> #622/32 verifier_linked_scalars/sext_narrow_inplace_pre_copy:OK
> #622/33 verifier_linked_scalars/sext_narrow_spill_fill:OK
> #622/34 verifier_linked_scalars/sext_resext_preserves_range:OK
> #622/35 verifier_linked_scalars/sext_in_loop_converges:OK
> #622/36 verifier_linked_scalars/sext_in_loop_separate_dest_index:OK
> #622/37 verifier_linked_scalars/zext_mov_from_sext_src_zero_extends:OK
> #622/38 verifier_linked_scalars/sext_mov_keeps_add_const_src:OK
> #622/39 verifier_linked_scalars/sext_dest_driven_does_not_narrow_base:OK
3. Regression
< #171/47 iters/iter_obfuscate_counter:OK
Vineet Gupta (6):
bpf: turn bpf_reg_state->precise into a flags field [NFC]
bpf: move the linked-scalar flags into bpf_reg_state->flags [NFC]
bpf: support low-32 subreg scalar linking for zero-extending movs
selftests/bpf: cover low-32 subreg-equal link for zero-extending movs
bpf: support low-32 subreg scalar linking for sign-extending movs
selftests/bpf: cover 32-bit sign-extension low-32 links
include/linux/bpf_verifier.h | 51 +-
kernel/bpf/backtrack.c | 22 +-
kernel/bpf/log.c | 6 +-
kernel/bpf/states.c | 106 +++-
kernel/bpf/verifier.c | 226 ++++++-
.../selftests/bpf/progs/verifier_bounds.c | 10 +-
.../bpf/progs/verifier_linked_scalars.c | 550 +++++++++++++++++-
.../selftests/bpf/progs/verifier_reg_equal.c | 16 +-
8 files changed, 890 insertions(+), 97 deletions(-)
--
2.53.0-Meta
^ permalink raw reply [flat|nested] 7+ messages in thread
* [RFC bpf-next 1/6] bpf: turn bpf_reg_state->precise into a flags field [NFC]
2026-08-14 23:19 [RFC bpf-next 0/6] bpf: track scalar equality across the low 32 bits Vineet Gupta
@ 2026-08-14 23:19 ` Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 2/6] bpf: move the linked-scalar flags into bpf_reg_state->flags [NFC] Vineet Gupta
` (4 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Vineet Gupta @ 2026-08-14 23:19 UTC (permalink / raw)
To: ast, daniel, andrii, eddyz87, memxor
Cc: martin.lau, song, yonghong.song, jolsa, emil, ihor.solodrai,
john.fastabend, shuah, bpf, linux-kernel, linux-kselftest,
Vineet Gupta
bpf_reg_state carries a single bool, ->precise. Other per-register boolean
properties exist (and more are coming), so convert the bool into a u8,
call it flags and give the property a name.
- bool precise;
+#define BPF_FLAG_PRECISE (1U << 7)
+ u8 flags;
Both occupy 1 byte at the same offset, so the struct layout is unchanged.
->precise was the last field, after ->frameno, and ->flags takes exactly
that slot, so the memcmp()/offsetof() based comparisons are unaffected:
every one of them stops at offsetof(id), offsetof(var_off) or
offsetof(frameno), i.e. at or before the field either way.
That tail position is not an accident -- it is where fields live that are
compared semantically rather than byte-wise. ->precise is never memcmp()ed;
regsafe() tests it explicitly, and an imprecise old scalar is a wildcard:
if (!reg_is_precise(rold) && exact == NOT_EXACT)
return true;
PRECISE also takes bit 7 rather than bit 0, because it is the odd one out
among the flags that will share this byte: the others describe how a register
relates to its ->id set and are cleared as a group, while PRECISE belongs to
the register alone and must survive that clearing. Growing the rest up from
bit 0 keeps a clear-the-link-bits mask from reaching it by construction.
Reads go through a helper, since they are the common case and read better.
Set and clear stay open-coded as the usual reg->flags |= / &= ~ bit ops.
No functional change intended.
Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
include/linux/bpf_verifier.h | 18 ++++++++++++++++--
kernel/bpf/backtrack.c | 22 +++++++++++-----------
kernel/bpf/log.c | 2 +-
kernel/bpf/states.c | 10 +++++-----
kernel/bpf/verifier.c | 14 +++++++++-----
5 files changed, 42 insertions(+), 24 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 27b43fda9b17..ebab483fc7f2 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -162,10 +162,24 @@ struct bpf_reg_state {
* pointing to bpf_func_state.
*/
u32 frameno;
- /* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
- bool precise;
+ /*
+ * Register state flags.
+ * BPF_FLAG_PRECISE: if unset, and this is a SCALAR_VALUE, then
+ * min/max/tnum don't affect safety.
+ *
+ * PRECISE is a property of this register alone, so it is placed at bit 7,
+ * apart from the link flags, which grow up from bit 0 and are cleared as
+ * a group -- a clear-the-link-bits mask can then never reach it.
+ */
+#define BPF_FLAG_PRECISE (1U << 7)
+ u8 flags;
};
+static inline bool reg_is_precise(const struct bpf_reg_state *reg)
+{
+ return reg->flags & BPF_FLAG_PRECISE;
+}
+
static inline s64 reg_smin(const struct bpf_reg_state *reg)
{
return cnum64_smin(reg->r64);
diff --git a/kernel/bpf/backtrack.c b/kernel/bpf/backtrack.c
index a2b18a9f1694..400c69152ed2 100644
--- a/kernel/bpf/backtrack.c
+++ b/kernel/bpf/backtrack.c
@@ -675,9 +675,9 @@ void bpf_mark_all_scalars_precise(struct bpf_verifier_env *env,
func = st->frame[i];
for (j = 0; j < BPF_REG_FP; j++) {
reg = &func->regs[j];
- if (reg->type != SCALAR_VALUE || reg->precise)
+ if (reg->type != SCALAR_VALUE || reg_is_precise(reg))
continue;
- reg->precise = true;
+ reg->flags |= BPF_FLAG_PRECISE;
if (env->log.level & BPF_LOG_LEVEL2) {
verbose(env, "force_precise: frame%d: forcing r%d to be precise\n",
i, j);
@@ -687,9 +687,9 @@ void bpf_mark_all_scalars_precise(struct bpf_verifier_env *env,
if (!bpf_is_spilled_reg(&func->stack[j]))
continue;
reg = &func->stack[j].spilled_ptr;
- if (reg->type != SCALAR_VALUE || reg->precise)
+ if (reg->type != SCALAR_VALUE || reg_is_precise(reg))
continue;
- reg->precise = true;
+ reg->flags |= BPF_FLAG_PRECISE;
if (env->log.level & BPF_LOG_LEVEL2) {
verbose(env, "force_precise: frame%d: forcing fp%d to be precise\n",
i, -(j + 1) * 8);
@@ -851,7 +851,7 @@ int bpf_mark_chain_precision(struct bpf_verifier_env *env,
reg = &st->frame[0]->regs[i];
bt_clear_reg(bt, i);
if (reg->type == SCALAR_VALUE) {
- reg->precise = true;
+ reg->flags |= BPF_FLAG_PRECISE;
*changed = true;
}
}
@@ -912,10 +912,10 @@ int bpf_mark_chain_precision(struct bpf_verifier_env *env,
bt_clear_frame_reg(bt, fr, i);
continue;
}
- if (reg->precise) {
+ if (reg_is_precise(reg)) {
bt_clear_frame_reg(bt, fr, i);
} else {
- reg->precise = true;
+ reg->flags |= BPF_FLAG_PRECISE;
*changed = true;
}
}
@@ -932,10 +932,10 @@ int bpf_mark_chain_precision(struct bpf_verifier_env *env,
continue;
}
reg = &func->stack[i].spilled_ptr;
- if (reg->precise) {
+ if (reg_is_precise(reg)) {
bt_clear_frame_slot(bt, fr, i);
} else {
- reg->precise = true;
+ reg->flags |= BPF_FLAG_PRECISE;
*changed = true;
}
}
@@ -943,10 +943,10 @@ int bpf_mark_chain_precision(struct bpf_verifier_env *env,
if (!bt_is_frame_stack_arg_slot_set(bt, fr, i))
continue;
reg = &func->stack_arg_regs[i];
- if (reg->type != SCALAR_VALUE || reg->precise) {
+ if (reg->type != SCALAR_VALUE || reg_is_precise(reg)) {
bt_clear_frame_stack_arg_slot(bt, fr, i);
} else {
- reg->precise = true;
+ reg->flags |= BPF_FLAG_PRECISE;
*changed = true;
}
}
diff --git a/kernel/bpf/log.c b/kernel/bpf/log.c
index b740fa73ee26..9a4445d492c9 100644
--- a/kernel/bpf/log.c
+++ b/kernel/bpf/log.c
@@ -640,7 +640,7 @@ static void print_reg_state(struct bpf_verifier_env *env,
const char *sep = "";
t = reg->type;
- if (t == SCALAR_VALUE && reg->precise)
+ if (t == SCALAR_VALUE && reg_is_precise(reg))
verbose(env, "P");
if (t == SCALAR_VALUE && tnum_is_const(reg->var_off)) {
verbose_snum(env, reg->var_off.value);
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index 4e6aafad33bd..f7a0314fa106 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -548,7 +548,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
check_scalar_ids(rold->id, rcur->id, idmap);
}
- if (!rold->precise && exact == NOT_EXACT)
+ if (!reg_is_precise(rold) && exact == NOT_EXACT)
return true;
/*
* Linked register tracking uses rold->id to detect relationships.
@@ -1034,7 +1034,7 @@ static int propagate_precision(struct bpf_verifier_env *env,
first = true;
for (i = 0; i < BPF_REG_FP; i++, state_reg++) {
if (state_reg->type != SCALAR_VALUE ||
- !state_reg->precise)
+ !reg_is_precise(state_reg))
continue;
if (env->log.level & BPF_LOG_LEVEL2) {
if (first)
@@ -1051,7 +1051,7 @@ static int propagate_precision(struct bpf_verifier_env *env,
continue;
state_reg = &state->stack[i].spilled_ptr;
if (state_reg->type != SCALAR_VALUE ||
- !state_reg->precise)
+ !reg_is_precise(state_reg))
continue;
if (env->log.level & BPF_LOG_LEVEL2) {
if (first)
@@ -1223,7 +1223,7 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
reg = &func->regs[j];
if (reg->type != SCALAR_VALUE)
continue;
- reg->precise = false;
+ reg->flags &= ~BPF_FLAG_PRECISE;
}
for (j = 0; j < func->allocated_stack / BPF_REG_SIZE; j++) {
if (!bpf_is_spilled_reg(&func->stack[j]))
@@ -1231,7 +1231,7 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
reg = &func->stack[j].spilled_ptr;
if (reg->type != SCALAR_VALUE)
continue;
- reg->precise = false;
+ reg->flags &= ~BPF_FLAG_PRECISE;
}
}
}
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6ac1afced20b..8925749d636e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1830,7 +1830,9 @@ static void __mark_reg_const_zero(const struct bpf_verifier_env *env, struct bpf
/* all scalars are assumed imprecise initially (unless unprivileged,
* in which case everything is forced to be precise)
*/
- reg->precise = !env->bpf_capable;
+ reg->flags &= ~BPF_FLAG_PRECISE;
+ if (!env->bpf_capable)
+ reg->flags |= BPF_FLAG_PRECISE;
}
static void mark_reg_known_zero(struct bpf_verifier_env *env,
@@ -2139,13 +2141,14 @@ void bpf_mark_reg_unknown_imprecise(struct bpf_reg_state *reg)
}
/* Mark a register as having a completely unknown (scalar) value,
- * initialize .precise as true when not bpf capable.
+ * set BPF_FLAG_PRECISE when not bpf capable.
*/
static void __mark_reg_unknown(const struct bpf_verifier_env *env,
struct bpf_reg_state *reg)
{
bpf_mark_reg_unknown_imprecise(reg);
- reg->precise = !env->bpf_capable;
+ if (!env->bpf_capable)
+ reg->flags |= BPF_FLAG_PRECISE;
}
static void mark_reg_unknown(struct bpf_verifier_env *env,
@@ -7506,7 +7509,8 @@ static void maybe_widen_reg(struct bpf_verifier_env *env,
return;
if (rold->type != rcur->type)
return;
- if (rold->precise || rcur->precise || scalars_exact_for_widen(rold, rcur))
+ if (reg_is_precise(rold) || reg_is_precise(rcur) ||
+ scalars_exact_for_widen(rold, rcur))
return;
__mark_reg_unknown(env, rcur);
}
@@ -14876,7 +14880,7 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
return err;
return adjust_ptr_min_max_vals(env, insn,
dst_reg, src_reg);
- } else if (dst_reg->precise) {
+ } else if (reg_is_precise(dst_reg)) {
/* if dst_reg is precise, src_reg should be precise as well */
err = mark_chain_precision(env, insn->src_reg);
if (err)
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [RFC bpf-next 2/6] bpf: move the linked-scalar flags into bpf_reg_state->flags [NFC]
2026-08-14 23:19 [RFC bpf-next 0/6] bpf: track scalar equality across the low 32 bits Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 1/6] bpf: turn bpf_reg_state->precise into a flags field [NFC] Vineet Gupta
@ 2026-08-14 23:19 ` Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 3/6] bpf: support low-32 subreg scalar linking for zero-extending movs Vineet Gupta
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Vineet Gupta @ 2026-08-14 23:19 UTC (permalink / raw)
To: ast, daniel, andrii, eddyz87, memxor
Cc: martin.lau, song, yonghong.song, jolsa, emil, ihor.solodrai,
john.fastabend, shuah, bpf, linux-kernel, linux-kselftest,
Vineet Gupta
bpf_reg_state->id is an overloaded container for:
- "id" corresponding to "linked" registers
- linkage type flags
This was fine so far, however new linkage types are coming so better to
separate them:
- checking for "id" doesn't need masking out flags: this is both
cleaner and future-proof
- makes ->id full 32-bits
The best part is no additional space needed as it piggybacks on the
previous patch creating a flags field.
The cleanup of check_scalar_ids() alone is worth this:
- Its two-level "check the compound id, then check the base id" dance
existed only because the flag was part of the key. With a plain id there
is one key and a single check_ids() suffices; the flag and delta equality
that regsafe() already enforces cover the rest.
However, ->flags now sits past the end of every memcmp() window used for
state comparison (they stop at offsetof(id), offsetof(var_off) or
offsetof(frameno)), and check_ids() only ever sees the plain ->id. While the
flags lived in the top bits of ->id they were compared for free -- byte-wise
by states_maybe_looping(), and as part of the compound key by regs_exact().
Now they have to be compared explicitly, so add a helper and call it from
both places that compare a scalar identity:
static bool link_flags_match(rold, rcur)
{
if (!rold->id)
return true;
return (rold->flags & BPF_FLAG_ADD_CONST) ==
(rcur->flags & BPF_FLAG_ADD_CONST);
}
regsafe() keeps its check in the same spot, now expressed via the helper, so
its behaviour is unchanged. regs_exact() gains the check it lost; that is the
one place this patch is not bit-identical to the old compound-key behaviour,
but it restores the discrimination the compound key provided rather than
adding new strictness. states_maybe_looping() is covered through
states_equal(EXACT), which routes to regs_exact().
The helper is the single point to extend when further link flavours are added.
Two more places need care now that these flags share a byte with
BPF_FLAG_PRECISE:
- clear_scalar_id() and __mark_reg_known() clear only the ADD_CONST bits, not
the whole byte, so the precise marking survives as before.
- sync_linked_regs() does "*reg = *known_reg" and then restores the fields
that identify reg rather than known_reg. Only the ADD_CONST bits belong to
that set (they used to live in ->id); BPF_FLAG_PRECISE must keep coming
from known_reg, as it did when it was a separate bool. So the save/restore
is masked to BPF_FLAG_ADD_CONST rather than covering ->flags wholesale.
No functional change intended.
Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
include/linux/bpf_verifier.h | 18 +++---
kernel/bpf/log.c | 4 +-
kernel/bpf/states.c | 64 ++++++++++++-------
kernel/bpf/verifier.c | 27 ++++----
.../bpf/progs/verifier_linked_scalars.c | 23 +++----
5 files changed, 81 insertions(+), 55 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index ebab483fc7f2..2b03fdba9acf 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -136,16 +136,13 @@ struct bpf_reg_state {
* to a specific instance of bpf_iter.
*/
/*
- * Upper bit of ID is used to remember relationship between "linked"
- * registers. Example:
+ * ->id identifies a set of "linked" registers; how a given member
+ * relates to the others is recorded in ->flags. Example:
* r1 = r2; both will have r1->id == r2->id == N
- * r1 += 10; r1->id == N | BPF_ADD_CONST and r1->delta == 10
+ * r1 += 10; r1 gets BPF_FLAG_ADD_CONST64 and r1->delta == 10
* r3 = r2; both will have r3->id == r2->id == N
- * w3 += 10; r3->id == N | BPF_ADD_CONST32 and r3->delta == 10
+ * w3 += 10; r3 gets BPF_FLAG_ADD_CONST32 and r3->delta == 10
*/
-#define BPF_ADD_CONST64 (1U << 31)
-#define BPF_ADD_CONST32 (1U << 30)
-#define BPF_ADD_CONST (BPF_ADD_CONST64 | BPF_ADD_CONST32)
u32 id;
/*
* Tracks the parent object this register was derived from.
@@ -166,11 +163,16 @@ struct bpf_reg_state {
* Register state flags.
* BPF_FLAG_PRECISE: if unset, and this is a SCALAR_VALUE, then
* min/max/tnum don't affect safety.
- *
* PRECISE is a property of this register alone, so it is placed at bit 7,
* apart from the link flags, which grow up from bit 0 and are cleared as
* a group -- a clear-the-link-bits mask can then never reach it.
+ *
+ * BPF_FLAG_ADD_CONST{32,64}: this register is (base + ->delta) within
+ * its ->id set, computed with a 32- or 64-bit ALU add.
*/
+#define BPF_FLAG_ADD_CONST32 (1U << 0)
+#define BPF_FLAG_ADD_CONST64 (1U << 1)
+#define BPF_FLAG_ADD_CONST (BPF_FLAG_ADD_CONST32 | BPF_FLAG_ADD_CONST64)
#define BPF_FLAG_PRECISE (1U << 7)
u8 flags;
};
diff --git a/kernel/bpf/log.c b/kernel/bpf/log.c
index 9a4445d492c9..775b91f806ac 100644
--- a/kernel/bpf/log.c
+++ b/kernel/bpf/log.c
@@ -662,8 +662,8 @@ static void print_reg_state(struct bpf_verifier_env *env,
verbose(env, "%s", btf_type_name(reg->btf, reg->btf_id));
verbose(env, "(");
if (reg->id)
- verbose_a("id=%d", reg->id & ~BPF_ADD_CONST);
- if (reg->id & BPF_ADD_CONST)
+ verbose_a("id=%d", reg->id);
+ if (reg->flags & BPF_FLAG_ADD_CONST)
verbose(env, "%+d", reg->delta);
if (reg->parent_id)
verbose_a("parent_id=%d", reg->parent_id);
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index f7a0314fa106..d3105b9a9965 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -370,12 +370,12 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
* to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map
* X->temp2, but X is already mapped to temp1, so the check fails correctly.
*
- * When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the
- * base id (flag stripped) must both map consistently. Example: old has
- * r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag
- * (r3 derived from unrelated r4). Without the base check, idmap gets two
- * independent entries A->B and A|flag->C|flag, missing that A->C conflicts
- * with A->B. The base ID cross-check catches this.
+ * ->id is a plain identifier -- the ADD_CONST relationship lives in
+ * ->flags -- so there is no compound (base | flag) key to unpack here.
+ * Registers sharing a base id go through one idmap entry, which is what
+ * catches e.g. old r2.id=A, r3.id=A (r3 = r2 + delta) against cur r2.id=B,
+ * r3.id=C: A->B and A->C conflict. Matching ->flags and ->delta are checked
+ * by the caller in regsafe().
*/
static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
{
@@ -384,15 +384,7 @@ static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen;
- if (!check_ids(old_id, cur_id, idmap))
- return false;
- if (old_id & BPF_ADD_CONST) {
- old_id &= ~BPF_ADD_CONST;
- cur_id &= ~BPF_ADD_CONST;
- if (!check_ids(old_id, cur_id, idmap))
- return false;
- }
- return true;
+ return check_ids(old_id, cur_id, idmap);
}
static void __clean_func_state(struct bpf_verifier_env *env,
@@ -488,11 +480,32 @@ static int clean_verifier_state(struct bpf_verifier_env *env,
return 0;
}
+/*
+ * Do rold and rcur describe the same relationship to their ->id set?
+ *
+ * The link flags live in ->flags, which sits past the end of every memcmp()
+ * window used for state comparison, and check_ids() only ever sees the plain
+ * ->id. So unlike when these bits rode along in the top of ->id, they have to
+ * be compared explicitly everywhere ->id is.
+ *
+ * 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.
+ */
+static bool link_flags_match(const struct bpf_reg_state *rold,
+ const struct bpf_reg_state *rcur)
+{
+ if (!rold->id)
+ return true;
+
+ return (rold->flags & BPF_FLAG_ADD_CONST) == (rcur->flags & BPF_FLAG_ADD_CONST);
+}
+
static bool regs_exact(const struct bpf_reg_state *rold,
const struct bpf_reg_state *rcur,
struct bpf_idmap *idmap)
{
return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
+ link_flags_match(rold, rcur) &&
check_ids(rold->id, rcur->id, idmap) &&
check_ids(rold->parent_id, rcur->parent_id, idmap);
}
@@ -554,7 +567,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
* Linked register tracking uses rold->id to detect relationships.
* When rold->id == 0, the register is independent and any linking
* in rcur only adds constraints. When rold->id != 0, we must verify
- * id mapping and (for BPF_ADD_CONST) offset consistency.
+ * id mapping and (for BPF_FLAG_ADD_CONST) offset consistency.
*
* +------------------+-----------+------------------+---------------+
* | | rold->id | rold + ADD_CONST | rold->id == 0 |
@@ -590,17 +603,24 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
*/
/*
- * ADD_CONST flags must match exactly: BPF_ADD_CONST32 and
- * BPF_ADD_CONST64 have different linking semantics in
+ * ADD_CONST flags must match exactly: BPF_FLAG_ADD_CONST32 and
+ * BPF_FLAG_ADD_CONST64 have different linking semantics in
* sync_linked_regs() (alu32 zero-extends, alu64 does not),
* so pruning across different flag types is unsafe.
*/
- if (rold->id &&
- (rold->id & BPF_ADD_CONST) != (rcur->id & BPF_ADD_CONST))
+ if (!link_flags_match(rold, rcur))
return false;
- /* Both have offset linkage: offsets must match */
- if ((rold->id & BPF_ADD_CONST) && rold->delta != rcur->delta)
+ /*
+ * Both have offset linkage: offsets must match. The rold->id
+ * test is redundant today -- BPF_FLAG_ADD_CONST is only ever set
+ * together with an id -- but it used to be structural, because
+ * the flag lived in the id itself. Keep it explicit so the
+ * invariant does not rest on every ->id = 0 site remembering to
+ * clear ->flags too.
+ */
+ if (rold->id && (rold->flags & BPF_FLAG_ADD_CONST) &&
+ rold->delta != rcur->delta)
return false;
if (!check_scalar_ids(rold->id, rcur->id, idmap))
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8925749d636e..93e69116ca9e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1806,6 +1806,7 @@ static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
reg->id = 0;
reg->parent_id = 0;
+ reg->flags &= ~BPF_FLAG_ADD_CONST;
___mark_reg_known(reg, imm);
}
@@ -3308,6 +3309,7 @@ static void clear_scalar_id(struct bpf_reg_state *reg)
{
reg->id = 0;
reg->delta = 0;
+ reg->flags &= ~BPF_FLAG_ADD_CONST;
}
static void assign_scalar_id_before_mov(struct bpf_verifier_env *env,
@@ -3320,7 +3322,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->id & BPF_ADD_CONST)
+ if (src_reg->flags & BPF_FLAG_ADD_CONST)
clear_scalar_id(src_reg);
/*
* Ensure that src_reg has a valid ID that will be copied to
@@ -14950,7 +14952,7 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
off = -off;
}
- if (dst_reg->id & BPF_ADD_CONST) {
+ if (dst_reg->flags & BPF_FLAG_ADD_CONST) {
/*
* If the register already went through rX += val
* we cannot accumulate another val into rx->off.
@@ -14959,9 +14961,9 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
clear_scalar_id(dst_reg);
} else {
if (alu32)
- dst_reg->id |= BPF_ADD_CONST32;
+ dst_reg->flags |= BPF_FLAG_ADD_CONST32;
else
- dst_reg->id |= BPF_ADD_CONST64;
+ dst_reg->flags |= BPF_FLAG_ADD_CONST64;
dst_reg->delta = off;
}
} else {
@@ -15886,7 +15888,7 @@ static void __collect_linked_regs(struct linked_regs *reg_set, struct bpf_reg_st
{
struct linked_reg *e;
- if (reg->type != SCALAR_VALUE || (reg->id & ~BPF_ADD_CONST) != id)
+ if (reg->type != SCALAR_VALUE || reg->id != id)
return;
e = linked_regs_push(reg_set);
@@ -15914,7 +15916,6 @@ static void collect_linked_regs(struct bpf_verifier_env *env,
u16 live_regs;
int i, j;
- id = id & ~BPF_ADD_CONST;
for (i = vstate->curframe; i >= 0; i--) {
live_regs = aux[bpf_frame_insn_idx(vstate, i)].live_regs_before;
func = vstate->frame[i];
@@ -15950,18 +15951,19 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
: &vstate->frame[e->frameno]->stack[e->spi].spilled_ptr;
if (reg->type != SCALAR_VALUE || reg == known_reg)
continue;
- if ((reg->id & ~BPF_ADD_CONST) != (known_reg->id & ~BPF_ADD_CONST))
+ if (reg->id != known_reg->id)
continue;
/*
* Skip mixed 32/64-bit links: the delta relationship doesn't
* hold across different ALU widths.
*/
- if (((reg->id ^ known_reg->id) & BPF_ADD_CONST) == BPF_ADD_CONST)
+ if (((reg->flags ^ known_reg->flags) & BPF_FLAG_ADD_CONST) == BPF_FLAG_ADD_CONST)
continue;
- if ((!(reg->id & BPF_ADD_CONST) && !(known_reg->id & BPF_ADD_CONST)) ||
+ if ((!(reg->flags & BPF_FLAG_ADD_CONST) && !(known_reg->flags & BPF_FLAG_ADD_CONST)) ||
reg->delta == known_reg->delta) {
*reg = *known_reg;
} else {
+ u8 saved_add_const = reg->flags & BPF_FLAG_ADD_CONST;
s32 saved_off = reg->delta;
u32 saved_id = reg->id;
@@ -15976,11 +15978,12 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
*/
reg->delta = saved_off;
reg->id = saved_id;
+ reg->flags = (reg->flags & ~BPF_FLAG_ADD_CONST) | saved_add_const;
scalar32_min_max_add(reg, &fake_reg);
scalar_min_max_add(reg, &fake_reg);
reg->var_off = tnum_add(reg->var_off, fake_reg.var_off);
- if ((reg->id | known_reg->id) & BPF_ADD_CONST32)
+ if ((reg->flags | known_reg->flags) & BPF_FLAG_ADD_CONST32)
zext_32_to_64(reg);
reg_bounds_sync(reg);
}
@@ -17007,7 +17010,7 @@ void bpf_clear_singular_ids(struct bpf_verifier_env *env,
continue;
if (!reg->id)
continue;
- idset_cnt_inc(idset, reg->id & ~BPF_ADD_CONST);
+ idset_cnt_inc(idset, reg->id);
}));
bpf_for_each_reg_in_vstate(st, func, reg, ({
@@ -17015,7 +17018,7 @@ void bpf_clear_singular_ids(struct bpf_verifier_env *env,
continue;
if (!reg->id)
continue;
- if (idset_cnt_get(idset, reg->id & ~BPF_ADD_CONST) == 1)
+ if (idset_cnt_get(idset, reg->id) == 1)
clear_scalar_id(reg);
}));
}
diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
index d571fbfc86a3..c80747c16bcf 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -349,8 +349,9 @@ l0_%=: \
}
/*
- * Test that sync_linked_regs() checks reg->id (the linked target register)
- * for BPF_ADD_CONST32 rather than known_reg->id (the branch register).
+ * Test that sync_linked_regs() consults reg->flags (the linked target
+ * register) for BPF_FLAG_ADD_CONST32, not just known_reg->flags (the branch
+ * register): the gate is (reg->flags | known_reg->flags).
*/
SEC("socket")
__success
@@ -360,7 +361,7 @@ __naked void scalars_alu32_zext_linked_reg(void)
call %[bpf_get_prandom_u32]; \
w6 = w0; /* r6 in [0, 0xFFFFFFFF] */ \
r7 = r6; /* linked: same id as r6 */ \
- w7 += 1; /* alu32: r7.id |= BPF_ADD_CONST32 */ \
+ w7 += 1; /* alu32: r7.flags |= BPF_FLAG_ADD_CONST32 */ \
r8 = 0xFFFFffff ll; \
if r6 < r8 goto l0_%=; \
/* r6 in [0xFFFFFFFF, 0xFFFFFFFF] */ \
@@ -381,7 +382,7 @@ l0_%=: \
/*
* Test that sync_linked_regs() skips propagation when one register used
- * alu32 (BPF_ADD_CONST32) and the other used alu64 (BPF_ADD_CONST64).
+ * alu32 (BPF_FLAG_ADD_CONST32) and the other used alu64 (BPF_FLAG_ADD_CONST64).
* The delta relationship doesn't hold across different ALU widths.
*/
SEC("socket")
@@ -392,9 +393,9 @@ __naked void scalars_alu32_alu64_cross_type(void)
call %[bpf_get_prandom_u32]; \
w6 = w0; /* r6 in [0, 0xFFFFFFFF] */ \
r7 = r6; /* linked: same id as r6 */ \
- w7 += 1; /* alu32: BPF_ADD_CONST32, delta = 1 */ \
+ w7 += 1; /* alu32: BPF_FLAG_ADD_CONST32, delta = 1 */ \
r8 = r6; /* linked: same id as r6 */ \
- r8 += 2; /* alu64: BPF_ADD_CONST64, delta = 2 */ \
+ r8 += 2; /* alu64: BPF_FLAG_ADD_CONST64, delta = 2 */ \
r9 = 0xFFFFffff ll; \
if r7 < r9 goto l0_%=; \
/* r7 = 0xFFFFFFFF */ \
@@ -416,7 +417,7 @@ l0_%=: \
/*
* Test that regsafe() prevents pruning when two paths reach the same program
* point with linked registers carrying different ADD_CONST flags (one
- * BPF_ADD_CONST32 from alu32, another BPF_ADD_CONST64 from alu64).
+ * BPF_FLAG_ADD_CONST32 from alu32, another BPF_FLAG_ADD_CONST64 from alu64).
*/
SEC("socket")
__failure __msg("div by zero")
@@ -431,11 +432,11 @@ __naked void scalars_alu32_alu64_regsafe_pruning(void)
call %[bpf_get_prandom_u32]; \
if r0 > 0 goto l_pathb_%=; \
/* Path A: alu32 */ \
- w7 += 1; /* BPF_ADD_CONST32, delta = 1 */\
+ w7 += 1; /* BPF_FLAG_ADD_CONST32, delta = 1 */\
goto l_merge_%=; \
l_pathb_%=: \
/* Path B: alu64 */ \
- r7 += 1; /* BPF_ADD_CONST64, delta = 1 */\
+ r7 += 1; /* BPF_FLAG_ADD_CONST64, delta = 1 */\
l_merge_%=: \
/* Merge point: regsafe() compares path B against cached path A. */ \
/* Narrow r6 to trigger sync_linked_regs for r7 */ \
@@ -593,7 +594,7 @@ l_exit_%=: \
}
/*
- * Test that stale delta from a cleared BPF_ADD_CONST does not leak
+ * Test that stale delta from a cleared BPF_FLAG_ADD_CONST does not leak
* through assign_scalar_id_before_mov() into a new id, causing
* sync_linked_regs() to compute an incorrect offset.
*/
@@ -648,7 +649,7 @@ l_exit_%=: \
}
/*
- * Test that regsafe() verifies base_id consistency for BPF_ADD_CONST
+ * Test that regsafe() verifies base_id consistency for BPF_FLAG_ADD_CONST
* linked scalars during state pruning.
*
* The false branch (explored first) links R3 to R2 via ADD_CONST.
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [RFC bpf-next 3/6] bpf: support low-32 subreg scalar linking for zero-extending movs
2026-08-14 23:19 [RFC bpf-next 0/6] bpf: track scalar equality across the low 32 bits Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 1/6] bpf: turn bpf_reg_state->precise into a flags field [NFC] Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 2/6] bpf: move the linked-scalar flags into bpf_reg_state->flags [NFC] Vineet Gupta
@ 2026-08-14 23:19 ` Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 4/6] selftests/bpf: cover low-32 subreg-equal link " Vineet Gupta
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Vineet Gupta @ 2026-08-14 23:19 UTC (permalink / raw)
To: ast, daniel, andrii, eddyz87, memxor
Cc: martin.lau, song, yonghong.song, jolsa, emil, ihor.solodrai,
john.fastabend, shuah, bpf, linux-kernel, linux-kselftest,
Vineet Gupta
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>
---
include/linux/bpf_verifier.h | 10 ++++
kernel/bpf/states.c | 23 ++++++++-
kernel/bpf/verifier.c | 91 ++++++++++++++++++++++++++++++++----
3 files changed, 114 insertions(+), 10 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 2b03fdba9acf..a4cba5c5099e 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -169,10 +169,20 @@ struct bpf_reg_state {
*
* BPF_FLAG_ADD_CONST{32,64}: this register is (base + ->delta) within
* its ->id set, computed with a 32- or 64-bit ALU add.
+ * BPF_FLAG_SUBREG_ZEXT: low-32-bit-only equality (as opposed to the
+ * full equality implied by a bare shared ->id): this register shares
+ * only the base's low 32 bits, and its high bits are zero (32-bit
+ * zero-extending mov).
+ * sync_linked_regs() propagates the low 32-bit subrange and rebuilds
+ * the high half accordingly, so this is sound even when the base has
+ * unknown high bits.
*/
#define BPF_FLAG_ADD_CONST32 (1U << 0)
#define BPF_FLAG_ADD_CONST64 (1U << 1)
#define BPF_FLAG_ADD_CONST (BPF_FLAG_ADD_CONST32 | BPF_FLAG_ADD_CONST64)
+#define BPF_FLAG_SUBREG_ZEXT (1U << 2)
+/* Every flag describing how this register relates to its ->id set. */
+#define BPF_FLAG_LINK (BPF_FLAG_ADD_CONST | BPF_FLAG_SUBREG_ZEXT)
#define BPF_FLAG_PRECISE (1U << 7)
u8 flags;
};
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;
+
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
@@ -1806,7 +1806,7 @@ static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
reg->id = 0;
reg->parent_id = 0;
- reg->flags &= ~BPF_FLAG_ADD_CONST;
+ reg->flags &= ~BPF_FLAG_LINK;
___mark_reg_known(reg, imm);
}
@@ -3309,7 +3309,7 @@ static void clear_scalar_id(struct bpf_reg_state *reg)
{
reg->id = 0;
reg->delta = 0;
- reg->flags &= ~BPF_FLAG_ADD_CONST;
+ reg->flags &= ~BPF_FLAG_LINK;
}
static void assign_scalar_id_before_mov(struct bpf_verifier_env *env,
@@ -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);
+
+ 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);
+ }
+ }
} 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;
+ 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;
+ 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.
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [RFC bpf-next 4/6] selftests/bpf: cover low-32 subreg-equal link for zero-extending movs
2026-08-14 23:19 [RFC bpf-next 0/6] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (2 preceding siblings ...)
2026-08-14 23:19 ` [RFC bpf-next 3/6] bpf: support low-32 subreg scalar linking for zero-extending movs Vineet Gupta
@ 2026-08-14 23:19 ` Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 5/6] bpf: support low-32 subreg scalar linking for sign-extending movs Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 6/6] selftests/bpf: cover 32-bit sign-extension low-32 links Vineet Gupta
5 siblings, 0 replies; 7+ messages in thread
From: Vineet Gupta @ 2026-08-14 23:19 UTC (permalink / raw)
To: ast, daniel, andrii, eddyz87, memxor
Cc: martin.lau, song, yonghong.song, jolsa, emil, ihor.solodrai,
john.fastabend, shuah, bpf, linux-kernel, linux-kselftest,
Vineet Gupta
Add subreg_eq_zext_mov_narrow: a wide-source "w7 = w6" followed by "if w6 == 0"
must narrow w7 to 0 via the low-32 BPF_FLAG_SUBREG_ZEXT link.
Update two tests for the new, more precise behaviour:
- verifier_reg_equal/subreg_equality_2 now loads: with the low-32 link,
"w2 < 9" narrows r3 to [0, 8], so the illegal r1 read is unreachable and the
program is safe.
- verifier_bounds 32-bit subtraction partial overflow: R3 now carries an id
from the link (bounds unchanged), so __msg gains an "id=" match. It is
required rather than optional: the id is deterministic here, and an
optional match would still pass if the link were ever dropped again.
Also covers the dest-driven direction, which the other tests do not: they all
narrow the base and check the linked register.
zext_dest_driven_does_not_narrow_base narrows the LINKED register instead and
requires that the wide base is NOT narrowed -- the "known_reg is
subreg-linked" continue in sync_linked_regs().
It is a __failure test: the div must stay reachable. This is also the shape
that catches a lost BPF_FLAG_SUBREG_ZEXT, since dropping the flag while the
shared ->id survives makes the pair look like a full 64-bit equality and
bypasses that guard.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
.../selftests/bpf/progs/verifier_bounds.c | 10 +-
.../bpf/progs/verifier_linked_scalars.c | 115 ++++++++++++++++++
.../selftests/bpf/progs/verifier_reg_equal.c | 16 +--
3 files changed, 133 insertions(+), 8 deletions(-)
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index 1a273e416fed..6169a61269b2 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -1516,7 +1516,15 @@ __naked void sub32_full_overflow(void)
SEC("socket")
__description("32-bit subtraction, partial overflow, result in unbounded u32 bounds")
__success __log_level(2)
-__msg("3: (1c) w3 -= w2 {{.*}} R3=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))")
+/*
+ * w3 = w0 forms a low-32 BPF_FLAG_SUBREG_ZEXT link, so R3 carries an id here
+ * where it did not before; the bounds are unchanged. The id is deterministic
+ * (raw asm, same bytecode in every flavour) so require it rather than making
+ * it optional -- otherwise the assertion would still pass if the link were
+ * dropped again. The delta suffix is left general: log.c prints ->delta
+ * directly after the id with no separator when BPF_FLAG_ADD_CONST is set.
+ */
+__msg("3: (1c) w3 -= w2 {{.*}} R3=scalar(id={{[0-9]+([+-][0-9]+)?}},smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))")
__retval(0)
__naked void sub32_partial_overflow(void)
{
diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
index c80747c16bcf..2cc6f9e45aff 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -711,4 +711,119 @@ l_exit_%=: \
: __clobber_all);
}
+/*
+ * A 32-bit zero-extending mov (w7 = w6) from a source with unknown high bits
+ * shares only the low 32 bits (w7.lo == w6.lo, w7.hi == 0). A later narrowing of
+ * the source's low 32 bits must propagate to the destination via the
+ * BPF_FLAG_SUBREG_ZEXT (low-32-only) link. This is the pattern bpf-gcc emits when it
+ * reuses "w0 = idx" for "return 0" on the idx==0 path of a callback.
+ */
+SEC("socket")
+__success
+__naked void subreg_eq_zext_mov_narrow(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; /* r6 = 64-bit unknown (helper ret is unbounded) */ \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; /* r0 = unknown high bits */ \
+ r6 |= r0; /* still 64-bit unknown; makes it explicit */ \
+ w7 = w6; /* 32-bit zero-extend mov, wide src */ \
+ if w6 != 0 goto l_out_%=; /* w6 low == 0 on fall-through */ \
+ /* w7 = zext32(w6 low) must be 0 here */ \
+ if w7 == 0 goto l_out_%=; /* provably 0 iff linked */ \
+ r0 /= 0; /* reached only if w7 not deduced 0 */ \
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A 32-bit zero-extending mov (w7 = w5) whose SOURCE is a wide ADD_CONST-linked
+ * register (r5 = base + K) must NOT disturb that source. Forming the low-32
+ * BPF_FLAG_SUBREG_ZEXT link on the destination would need assign_scalar_id_before_mov()
+ * on the source, which clears its base+delta link -- and a combined
+ * subreg+delta link isn't modeled anyway (sync_linked_regs() skips it). So for a
+ * wide ADD_CONST src the mov leaves the source's link intact and just clears the
+ * destination.
+ *
+ * Here r5 = r6 + 3 (ADD_CONST, wide). After the mov, narrowing the base r6 must
+ * still reach r5 through the preserved link: r6 in [0, 10] => r5 in [3, 13], so
+ * the guarded div-by-zero is unreachable. Had the mov cleared r5's link (calling
+ * assign_scalar_id_before_mov() unconditionally), r5 would stay unbounded and the
+ * div would be reachable (rejected).
+ *
+ * Note this is a no-regression guard rather than coverage of the new link:
+ * before this feature the wide-source path also left the source untouched, so
+ * the test passes either way. What it pins is the choice not to call
+ * assign_scalar_id_before_mov() unconditionally.
+ *
+ * Written in asm so the bytecode is identical regardless of the host BPF compiler.
+ */
+SEC("socket")
+__success
+__naked void zext_mov_keeps_add_const_src(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; /* r6 low = unknown u32 */ \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown (base) */ \
+ r5 = r6; /* r5, r6 linked (shared id) */ \
+ r5 += 3; /* r5 = base + 3: ADD_CONST, still wide */ \
+ w7 = w5; /* 32-bit zext mov, wide ADD_CONST src */ \
+ if r6 > 10 goto l_out_%=;/* r6 in [0, 10] */ \
+ /* r5 = r6 + 3 must be in [3, 13] here (needs the kept link) */ \
+ if r5 > 13 goto l_err_%=;/* taken only if r5 not narrowed */ \
+ goto l_out_%=; \
+l_err_%=: \
+ r0 /= 0; /* reachable iff r5's link was cleared */ \
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Dest-driven direction, zero-extend flavour: narrowing the LINKED register
+ * must not narrow the wide base.
+ *
+ * w7 = w6 shares only r6's low 32 bits; r7's high half is zero, r6's is
+ * unknown. Learning r7 == 0 therefore says nothing about r6, and
+ * sync_linked_regs() must not copy r7's state onto it. Rejected iff the base
+ * is left alone.
+ *
+ * This is the shape that catches a lost BPF_FLAG_SUBREG_ZEXT: if the flag is
+ * dropped while the shared ->id survives, the pair looks like a full 64-bit
+ * equality, the dest-driven guard is bypassed and r6 wrongly becomes 0.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void zext_dest_driven_does_not_narrow_base(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; /* r6 low = unknown u32 */ \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown (base) */ \
+ w7 = w6; /* low-32 ZEXT link */ \
+ if r7 != 0 goto l_out_%=;/* r7 == 0: low 32 bits are 0 */ \
+ if r6 != 0 goto l_out_%=;/* r6 may still have high bits set */ \
+ r0 /= 0; /* must stay reachable */ \
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/verifier_reg_equal.c b/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
index dc1d8c30fb0e..e6fbbfaeedcb 100644
--- a/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
+++ b/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
@@ -31,23 +31,25 @@ l1_%=: exit; \
}
SEC("socket")
-__description("check w reg not equal if r reg upper32 bits not 0")
-__failure __msg("R1 !read_ok")
+__description("w reg shares r reg low32 via subreg link even if upper32 not 0")
+__success
__naked void subreg_equality_2(void)
{
asm volatile (" \
call %[bpf_ktime_get_ns]; \
r2 = r0; \
- /* Upper 4-bytes of r2 may not be 0, thus insn \
- * w3 = w2 should not propagate reg id, and \
- * w2 < 9 comparison should not propagate \
- * the range for r3 either. \
+ /* Upper 4-bytes of r2 may not be 0. w3 = w2 is a 32-bit \
+ * zero-extending mov, so w3 shares only r2 low 32 bits \
+ * (a BPF_FLAG_SUBREG_ZEXT link) and its high bits are zero. The \
+ * w2 < 9 comparison then narrows r3 to [0, 8] via the link, \
+ * so if r3 < 9 is always taken and the illegal r1 read below \
+ * is unreachable. \
*/ \
w3 = w2; \
if w2 < 9 goto l0_%=; \
exit; \
l0_%=: if r3 < 9 goto l1_%=; \
- /* r1 read is illegal at this point */ \
+ /* unreachable: r3 is provably < 9 */ \
r0 -= r1; \
l1_%=: exit; \
" :
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [RFC bpf-next 5/6] bpf: support low-32 subreg scalar linking for sign-extending movs
2026-08-14 23:19 [RFC bpf-next 0/6] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (3 preceding siblings ...)
2026-08-14 23:19 ` [RFC bpf-next 4/6] selftests/bpf: cover low-32 subreg-equal link " Vineet Gupta
@ 2026-08-14 23:19 ` Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 6/6] selftests/bpf: cover 32-bit sign-extension low-32 links Vineet Gupta
5 siblings, 0 replies; 7+ messages in thread
From: Vineet Gupta @ 2026-08-14 23:19 UTC (permalink / raw)
To: ast, daniel, andrii, eddyz87, memxor
Cc: martin.lau, song, yonghong.song, jolsa, emil, ihor.solodrai,
john.fastabend, shuah, bpf, linux-kernel, linux-kselftest,
Vineet Gupta
This is the sign-extension counterpart to the prior zero-extension movs
change, and the original motivation for the series: bpf-gcc codegen tends to
generate many more sign-extensions than clang, some of which the verifier
already understands and some of which it does not.
A 32-bit sign extension (r0 = (s32)r0) preserves the source's low 32 bits and
sets the high bits to their sign-extension. When the sign bit is not provably
zero the verifier clears the destination's scalar id, so a later narrowing of
the low 32 bits (e.g. "if w1 == 0") never reaches the sign-extended register and
safe programs are rejected.
Three patterns hit this under bpf-gcc, and not under clang, which emits very
few sign extensions even for -mcpu=v4 builds.
1. callback exit-code checks that reject "R0 ... should have been in [0, 1]".
| 0: (61) r2 = *(u32 *)(r1 +24)
| 1: (bf) r0 = (s32)r2
| 2: (56) if w2 != 0x0 goto pc+10 ; R2=0 (branch taken)
| 12: (95) exit
2. the errno-or-zero return, where a value clamped to [-4095, 0] is
sign-extended again on "return ret" and coerce_reg_to_size_sx() then widens
it back to [S32_MIN, S32_MAX] (verify_pkcs7_sig and many lsm.s progs)
| 63: (85) call bpf_verify_pkcs7_signature#88154
| ...
| 69: (c5) if r0 s< 0xfffff001 goto pc+1 ; R0=scalar(id=7,smin=smin32=-4095,smax=0x7fffffff)
| 70: (d5) if r0 s<= 0x0 goto pc+1 72:
| 72: (bf) r0 = (s32)r0 ; R0=scalar(smin=0xffffffff80000000,smax=0x7fffffff)
| 73: (95) exit
3. loops whose induction variable is sign-extended every iteration, which
without a link never converge: "The sequence of 8193 jumps is too complex".
Solution
========
Reuse the low-32-only link added for zero-extending movs, with a second
flavour flag:
- for a wide-source 32-bit sign extension, mark dst with BPF_FLAG_SUBREG_SEXT
so its high bits are known to be the sign-extension of the low field. Only
32-bit sign extension is tracked -- (s8)/(s16) do not form a link (not seen
in codegen so far) -- so the flag alone carries the width and no extra field
is needed.
- the flag tells sync_linked_regs() how to rebuild the high half:
reconstruct_sext32() for the sign extension, versus the plain
zero-extension BPF_FLAG_SUBREG_ZEXT uses.
- reconstruct_sext32() rebuilds such a register from the base's low 32 bits,
driven both at the sign-extend site (to keep an already-narrowed range, the
errno case) and from sync_linked_regs() on a later low-32 narrowing.
- as with the zero-extend link this applies only when neither side carries an
ADD_CONST delta (the combined subreg+delta case is not modeled).
- also as with that link, no link is formed when src itself carries an
ADD_CONST delta: forming one calls assign_scalar_id_before_mov(), which
would clear src's base+delta relationship. The zero-extend arm's other
exclusion, a self-mov, deliberately does NOT carry over -- r0 = (s32)r0 is
the motivating case here. The no_sext path is unaffected: it already
called assign_scalar_id_before_mov() before this series, so an ADD_CONST
src was cleared there already.
- regsafe() extends its existing low-32 link check to cover both flavours,
so the two are not pruned across each other:
if (rold->id &&
(rold->flags & BPF_FLAG_SUBREG) != (rcur->flags & BPF_FLAG_SUBREG))
The rold->id gate comes from the zero-extend patch and carries over
unchanged. It matters for convergence here: these flags are only ever set
together with an ->id, so rold->id == 0 implies neither is set, and the
gate admits exactly "old knows no low-32 relationship, cur does" -- cur is
then strictly more constrained than old, the safe direction for pruning,
while the reverse is still rejected. Without it a register that first
acquires a sext link inside a loop would never match its pre-loop state and
verification would run to the 1M instruction limit (cond_break*, iters/*,
verifier_bits_iter/* and the sext_in_loop_converges case added next).
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
include/linux/bpf_verifier.h | 9 ++-
kernel/bpf/states.c | 13 ++++-
kernel/bpf/verifier.c | 110 +++++++++++++++++++++++++++++++----
3 files changed, 120 insertions(+), 12 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index a4cba5c5099e..67ef54d70116 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -173,6 +173,10 @@ struct bpf_reg_state {
* full equality implied by a bare shared ->id): this register shares
* only the base's low 32 bits, and its high bits are zero (32-bit
* zero-extending mov).
+ * BPF_FLAG_SUBREG_SEXT is the same for a 32-bit sign extension
+ * (r0 = (s32)r0); the two differ in how the high half is rebuilt.
+ * Only 32-bit sign extension is tracked -- (s8)/(s16) do not form a
+ * link -- so the flag alone carries the width.
* sync_linked_regs() propagates the low 32-bit subrange and rebuilds
* the high half accordingly, so this is sound even when the base has
* unknown high bits.
@@ -181,8 +185,11 @@ struct bpf_reg_state {
#define BPF_FLAG_ADD_CONST64 (1U << 1)
#define BPF_FLAG_ADD_CONST (BPF_FLAG_ADD_CONST32 | BPF_FLAG_ADD_CONST64)
#define BPF_FLAG_SUBREG_ZEXT (1U << 2)
+#define BPF_FLAG_SUBREG_SEXT (1U << 3)
+/* A low-32-only link, of either flavour. */
+#define BPF_FLAG_SUBREG (BPF_FLAG_SUBREG_ZEXT | BPF_FLAG_SUBREG_SEXT)
/* Every flag describing how this register relates to its ->id set. */
-#define BPF_FLAG_LINK (BPF_FLAG_ADD_CONST | BPF_FLAG_SUBREG_ZEXT)
+#define BPF_FLAG_LINK (BPF_FLAG_ADD_CONST | BPF_FLAG_SUBREG)
#define BPF_FLAG_PRECISE (1U << 7)
u8 flags;
};
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index ef71999c4695..6aaedde6e9d1 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -562,6 +562,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
* 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.
+ * The two flavours also differ from each other, in how the high
+ * half is rebuilt (zero-extension vs reconstruct_sext32()).
* 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
@@ -570,9 +572,18 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
* on a path that predates this series, which is a pruning change
* that wants measuring on its own; it is deliberately left
* alone here.
+ *
+ * Only demand a match when the old state carries a link at all.
+ * These flags are only ever set together with an ->id, so
+ * rold->id == 0 implies none is set, and the only case this
+ * admits is "old knows no low-32 relationship, cur does" -- cur
+ * is then strictly more constrained than old, which is the safe
+ * direction for pruning. The reverse is still rejected. Without
+ * this a register that first acquires a link inside a loop would
+ * never match its pre-loop state and pruning would not converge.
*/
if (rold->id &&
- (rold->flags & BPF_FLAG_SUBREG_ZEXT) != (rcur->flags & BPF_FLAG_SUBREG_ZEXT))
+ (rold->flags & BPF_FLAG_SUBREG) != (rcur->flags & BPF_FLAG_SUBREG))
return false;
if (env->explore_alu_limits) {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8a802d49d0a4..45cb67dc3999 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14976,6 +14976,8 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
return 0;
}
+static void reconstruct_sext32(struct bpf_reg_state *reg, struct bpf_reg_state *src);
+
/* check validity of 32-bit and 64-bit arithmetic operations */
static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
{
@@ -15052,15 +15054,65 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
insn->src_reg);
return -EACCES;
} else if (src_reg->type == SCALAR_VALUE) {
+ int sz = insn->off >> 3;
bool no_sext;
+ bool subreg_link;
no_sext = reg_umax(src_reg) < (1ULL << (insn->off - 1));
- if (no_sext)
+ /*
+ * When no_sext, dst == src exactly, so link them
+ * (existing behavior). When !no_sext for a 32-bit sign
+ * extension the low 32 bits are still identical (sext
+ * preserves them), so form a BPF_FLAG_SUBREG_SEXT
+ * link: a later narrowing of the low 32 bits
+ * propagates here, and sync_linked_regs() rebuilds
+ * the high half via reconstruct_sext32().
+ *
+ * An ADD_CONST-linked src is excluded for the same
+ * reason as in the zero-extending arm below:
+ * assign_scalar_id_before_mov() would clear its
+ * base+delta link, and a combined subreg+delta link
+ * isn't modeled anyway. Unlike that arm a self-mov is
+ * NOT excluded -- r0 = (s32)r0 is the case this is
+ * here for.
+ */
+ subreg_link = (sz == 4) &&
+ !(src_reg->flags & BPF_FLAG_ADD_CONST);
+
+ if (no_sext || subreg_link)
assign_scalar_id_before_mov(env, src_reg);
*dst_reg = *src_reg;
- if (!no_sext)
- clear_scalar_id(dst_reg);
- coerce_reg_to_size_sx(dst_reg, insn->off >> 3);
+ if (!no_sext) {
+ if (subreg_link && src_reg->id) {
+ /* ->id already copied above */
+ dst_reg->flags = (dst_reg->flags & ~BPF_FLAG_SUBREG) |
+ BPF_FLAG_SUBREG_SEXT;
+ } else {
+ clear_scalar_id(dst_reg);
+ }
+ }
+ /*
+ * coerce_reg_to_size_sx() falls back to the full sext
+ * range when smin/smax straddle the sign boundary (e.g.
+ * an errno-or-zero value clamped to [-4095, 0]). For a
+ * register tracked as the sign-extension of its low 32
+ * bits the high half IS that sign-extension, so rebuild
+ * the tighter 64-bit range from the low bounds, taken
+ * from a snapshot because coerce overwrites them.
+ *
+ * Gated on sz == 4, not on the flag alone: an (s8)/(s16)
+ * mov whose src is already SEXT-linked copies the flag
+ * across in the *dst_reg = *src_reg above, and a 32-bit
+ * reconstruction must not run for a narrower operation.
+ */
+ if (sz == 4 && (dst_reg->flags & BPF_FLAG_SUBREG_SEXT)) {
+ struct bpf_reg_state sext_src = *dst_reg;
+
+ coerce_reg_to_size_sx(dst_reg, sz);
+ reconstruct_sext32(dst_reg, &sext_src);
+ } else {
+ coerce_reg_to_size_sx(dst_reg, sz);
+ }
} else {
mark_reg_unknown(env, regs, insn->dst_reg);
}
@@ -15107,7 +15159,15 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
if (!is_src_reg_u32) {
if (wide_subreg_link && src_reg->id) {
/* ->id already copied above */
- dst_reg->flags |= BPF_FLAG_SUBREG_ZEXT;
+ /*
+ * Zero-extension: high bits are 0, not a
+ * sign-extension of the low field. Drop any
+ * SUBREG_SEXT copied from a sext-linked src
+ * so sync_linked_regs() rebuilds dst by
+ * zero-extension, not reconstruct_sext32().
+ */
+ dst_reg->flags = (dst_reg->flags & ~BPF_FLAG_SUBREG) |
+ BPF_FLAG_SUBREG_ZEXT;
} else {
clear_scalar_id(dst_reg);
}
@@ -15961,6 +16021,32 @@ static void collect_linked_regs(struct bpf_verifier_env *env,
}
}
+/*
+ * Set @reg to the sign-extension of the low 32 bits currently held by @src.
+ * A BPF_FLAG_SUBREG_SEXT-linked register came from a 32-bit sign
+ * extension (r0 = (s32)r0): it shares @src's low 32 bits and its high bits are
+ * the sign-extension of that low field. Only the value fields are written;
+ * @reg's linkage fields (id, delta, flags) are left intact by
+ * the caller (___mark_reg_known touches only var_off/r64/r32). Callers must
+ * ensure no ADD_CONST delta is involved (see sync_linked_regs()).
+ */
+static void reconstruct_sext32(struct bpf_reg_state *reg, struct bpf_reg_state *src)
+{
+ s32 s32min = reg_s32_min(src);
+ s32 s32max = reg_s32_max(src);
+
+ if (s32min == s32max) {
+ /* Low 32 bits are constant -> the whole value is the sext constant. */
+ ___mark_reg_known(reg, (u64)(s64)s32min);
+ } else {
+ /* Sign-extension is monotonic over the signed-32 range. */
+ reg_set_srange64(reg, (s64)s32min, (s64)s32max);
+ reg_set_srange32(reg, s32min, s32max);
+ reg->var_off = tnum_range((u64)(s64)s32min, (u64)(s64)s32max);
+ reg_bounds_sync(reg);
+ }
+}
+
/* For all R in linked_regs, copy known_reg range into R
* if R->id == known_reg->id.
*/
@@ -15984,17 +16070,21 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
* 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).
+ * For BPF_FLAG_SUBREG_SEXT they are the sign-extension of the low
+ * field (32-bit sign extension).
* 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 & BPF_FLAG_SUBREG) {
if (!((reg->flags | known_reg->flags) & BPF_FLAG_ADD_CONST)) {
- {
+ if (reg->flags & BPF_FLAG_SUBREG_SEXT) {
+ reconstruct_sext32(reg, known_reg);
+ } else {
u32 saved_id = reg->id;
- u8 saved_subreg = reg->flags & BPF_FLAG_SUBREG_ZEXT;
+ u8 saved_subreg = reg->flags & BPF_FLAG_SUBREG;
/*
* reg = zext32(known_reg): its low 32 bits come from
@@ -16008,7 +16098,7 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
*/
*reg = *known_reg;
reg->id = saved_id;
- reg->flags = (reg->flags & ~BPF_FLAG_SUBREG_ZEXT) | saved_subreg;
+ reg->flags = (reg->flags & ~BPF_FLAG_SUBREG) | saved_subreg;
zext_32_to_64(reg);
reg_bounds_sync(reg);
}
@@ -16024,7 +16114,7 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
* 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)
+ if (known_reg->flags & BPF_FLAG_SUBREG)
continue;
/*
* Skip mixed 32/64-bit links: the delta relationship doesn't
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [RFC bpf-next 6/6] selftests/bpf: cover 32-bit sign-extension low-32 links
2026-08-14 23:19 [RFC bpf-next 0/6] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (4 preceding siblings ...)
2026-08-14 23:19 ` [RFC bpf-next 5/6] bpf: support low-32 subreg scalar linking for sign-extending movs Vineet Gupta
@ 2026-08-14 23:19 ` Vineet Gupta
5 siblings, 0 replies; 7+ messages in thread
From: Vineet Gupta @ 2026-08-14 23:19 UTC (permalink / raw)
To: ast, daniel, andrii, eddyz87, memxor
Cc: martin.lau, song, yonghong.song, jolsa, emil, ihor.solodrai,
john.fastabend, shuah, bpf, linux-kernel, linux-kselftest,
Vineet Gupta
Tests for the BPF_FLAG_SUBREG_SEXT link, mostly built with the
div-by-zero-guard idiom: the div is unreachable iff the verifier deduces the
sign-extended register is 0, so a missed deduction turns __success into a
"div by zero" rejection.
Deduction through the link:
- sext_linked_low_narrow_to_zero, sext_linked_separate_dest_narrow_to_zero:
in-place and dst != src sign extension narrowed to 0 via the source's low
32 bits. The separate-dest case runs with BPF_F_TEST_STATE_FREQ so the
link has to survive state cleaning.
- sext_narrow_{branch_on_source,copied_back,inplace_pre_copy,spill_fill}:
variants derived from real "R0 ... should have been in [0, 1]" exit
rejections -- branch on source vs dest, copy-back, spill/fill across a
call.
- sext_resext_preserves_range: a redundant re-sext of a value clamped to
[-4095, 0] must keep the tight range (the errno-or-zero return pattern).
In-loop behaviour:
- sext_in_loop_converges: convergence regression test, reproducing the
bytecode bpf-gcc emits for a cond_break loop -- a counter incremented with
an ALU32 add (zero-extending the high half) then sign-extended in place
every iteration. Forming the link refreshes the linked scalar id and
BPF_FLAG_SUBREG_SEXT each iteration, so the loop-carried state never
repeats. It converges only because regsafe() demands a matching low-32
link just when the old state already has one: ~9 insns with that, versus
a load failure at 1,000,001 insns without.
- sext_in_loop_separate_dest_index: the companion case, a fresh in-loop temp
(a bounds-checked array index) that is dead across the back-edge. The link
is formed here too -- there is no liveness or loop-carried exclusion, the
gate is just (sz == 4) -- but because the temp is not loop-carried the link
costs nothing in convergence and simply buys precision: the narrowing
reaches it.
Interaction with the zero-extending link:
- zext_mov_from_sext_src_zero_extends: a 32-bit zero-extending mov (w2 = w1)
whose source is sign-extended (r1 = (s32)r6) must still zero-extend, i.e.
its link must be BPF_FLAG_SUBREG_ZEXT and must not inherit
BPF_FLAG_SUBREG_SEXT from the source. Otherwise sync_linked_regs() rebuilds
the destination with reconstruct_sext32() on a later low-32 narrowing,
computing a negative value for what is really a large positive
zero-extended one. After "if w6 s>= 0" falls through, r6's low 32 bits have
bit 31 set, so the zero-extended r2 is strictly positive and the guarded
div is reachable only on a mis-reconstruction.
Two more cases the earlier tests did not reach:
- sext_mov_keeps_add_const_src: mirror of zext_mov_keeps_add_const_src. A
sext whose source carries an ADD_CONST delta must not destroy that link.
Fails without the ADD_CONST source exclusion in the previous patch.
- sext_dest_driven_does_not_narrow_base: narrows the LINKED register and
requires the wide base is NOT narrowed, i.e. the "known_reg is
subreg-linked" continue in sync_linked_regs(). A __failure test -- the
div must stay reachable. Companion to the zero-extend version added by
the zero-extend selftest patch.
All are written in asm so the bytecode is identical regardless of the host
BPF compiler.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
.../bpf/progs/verifier_linked_scalars.c | 412 ++++++++++++++++++
1 file changed, 412 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
index 2cc6f9e45aff..ff71e168d4cc 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -826,4 +826,416 @@ l_out_%=: \
: __clobber_all);
}
+/*
+ * The tests below use the cpuv4 32-bit sign extension (r0 = (s32)r0), so they
+ * need a compiler that can emit it and a JIT that can run it. Same gate as
+ * verifier_movsx.c, except the compiler clause also accepts bpf-gcc, which
+ * does not define __clang_major__ but does define __BPF_FEATURE_MOVSX.
+ *
+ * The tests above do not need cpuv4, so the guard starts here rather than
+ * covering the whole file.
+ */
+#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \
+ (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) || \
+ defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \
+ defined(__TARGET_ARCH_loongarch)) && \
+ (__clang_major__ >= 18 || defined(__BPF_FEATURE_MOVSX))
+
+/*
+ * Sign-extension linked-register tracking, in-place narrow-to-zero.
+ *
+ * r1 = r0 ties r0,r1 with a shared id. r0 = (s32)r0 sign-extends r0's low 32
+ * bits; the helper return is a full 64-bit unknown so the sign bit isn't
+ * provably 0, and r0 keeps a BPF_FLAG_SUBREG_SEXT link to r1. On the w1 == 0
+ * fall-through, r1's low 32 bits are 0; r0's low 32 bits equal r1's and r0's
+ * upper bits are the sign-extension of that (0) -- so r0 == 0.
+ *
+ * The guarded div-by-zero is unreachable iff the verifier deduces r0 == 0.
+ */
+SEC("socket")
+__success
+__naked void sext_linked_low_narrow_to_zero(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r1 = r0; /* r1 == r0, shared id */ \
+ r0 = (s32)r0; /* r0 = sext32(r0) */ \
+ if w1 != 0 goto l0_%=; /* fall-through: w1 == 0 */ \
+ /* want deduced here: r0 == 0 */ \
+ if r0 == 0 goto l0_%=; /* always taken iff r0==0 known */ \
+ r0 /= 0; /* unreachable iff r0==0 deduced */ \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Separate-dest sign-extension: r3 = (s32)r2 (dst != src). r2,r3 share a base
+ * id (r3 with BPF_FLAG_SUBREG_SEXT). On the w2 == 0 fall-through, r2's low 32 bits are
+ * 0, so r3 = sext32(0) = 0 and the guarded div-by-zero is unreachable.
+ *
+ * Runs with BPF_F_TEST_STATE_FREQ to force checkpointing between the sext and
+ * the branch: the sext linkage (BPF_FLAG_SUBREG_SEXT) must survive state
+ * cleaning so sync_linked_regs() can still reconstruct r3. bpf_clear_singular_ids()
+ * strips the link flags when counting base ids; otherwise r3's compound id looks
+ * singular and gets cleared, and r3 stays wide.
+ */
+SEC("socket")
+__success
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void sext_linked_separate_dest_narrow_to_zero(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r2 = r0; /* r2,(r0) linked, id N */ \
+ r3 = (s32)r2; /* r3 = sext32(r2): SEXT link base N */ \
+ if w2 != 0 goto l0_%=; /* fall-through: w2 == 0 */ \
+ /* want deduced here: r3 == 0 */ \
+ if r3 == 0 goto l0_%=; /* always taken iff r3==0 known */ \
+ r0 /= 0; /* unreachable iff r3==0 deduced */ \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Coverage derived from real "R0 ... should have been in [0, 1]" exit
+ * rejections. Each sign-extends a value, then a branch proves its low 32 bits
+ * are 0 so the sext result must be 0. Expressed with the div-by-zero idiom (same
+ * deduced range the return-code check reads): the div is unreachable iff the
+ * verifier deduces the sext register is 0.
+ */
+
+/* 1: branch on the SOURCE reg; separate dest (value stands in for a u32 load). */
+SEC("socket")
+__success
+__naked void sext_narrow_branch_on_source(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r2 = r0; /* r2 = value (proxy for u32 load) */ \
+ r0 = (s32)r2; /* r0 = sext32(r2) */ \
+ if w2 != 0 goto l0_%=; /* w2 != 0: r0 unknown, skip */ \
+ if r0 == 0 goto l0_%=; /* w2 == 0: r0 must be 0 */ \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/* 2: sext into r7, prove via w0, then copy r7 back into r0. */
+SEC("socket")
+__success
+__naked void sext_narrow_copied_back(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r7 = (s32)r0; /* r7 = sext32(r0) */ \
+ if w0 != 0 goto l0_%=; /* w0 != 0: skip */ \
+ r0 = r7; /* w0 == 0: r0 = r7 (must be 0) */ \
+ if r0 == 0 goto l0_%=; \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/* 3: in-place sext; branch on the pre-sext copy r1 (== direction). */
+SEC("socket")
+__success
+__naked void sext_narrow_inplace_pre_copy(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r1 = r0; /* pre-sext copy, linked */ \
+ r0 = (s32)r0; /* in-place sext32 */ \
+ if w1 == 0 goto l_chk_%=;/* w1 == 0: r0 must be 0 */ \
+ goto l0_%=; /* w1 != 0: nothing to check */ \
+l_chk_%=: \
+ if r0 == 0 goto l0_%=; \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/* 4: sext, prove via w0, spill to stack across a call, reload, use. */
+SEC("socket")
+__success
+__naked void sext_narrow_spill_fill(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r9 = (s32)r0; /* r9 = sext32(r0) */ \
+ if w0 != 0 goto l0_%=; /* w0 != 0: skip */ \
+ /* w0 == 0: r9 must be 0 */ \
+ *(u64 *)(r10 - 8) = r9; /* spill r9 */ \
+ call %[bpf_get_prandom_u32];/* clobbers r0-r5 */ \
+ r5 = *(u64 *)(r10 - 8); /* reload -> must be 0 */ \
+ if r5 == 0 goto l0_%=; \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A redundant 32-bit sign-extension of an already-narrowed value must preserve
+ * the range. This is the errno-or-zero return pattern (set_if_not_errno_or_zero()
+ * followed by "return ret" on an int): the value is clamped to [-4095, 0] and
+ * then sign-extended again, e.g. verify_pkcs7_sig / many lsm.s progs under
+ * bpf-gcc. coerce_reg_to_size_sx() bails to the full [S32_MIN, S32_MAX] range
+ * when the range straddles the sign boundary (smin<0, smax>=0), so without the
+ * sext-self reconstruction the final "r0 = (s32)r0" widens [-4095, 0] back to
+ * the full range and the program is rejected. Knowing the high half is the
+ * sign-extension of the low 32 bits lets the verifier rebuild the tight range.
+ */
+SEC("socket")
+__success
+__naked void sext_resext_preserves_range(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r0 = (s32)r0; /* r0 = [S32_MIN, S32_MAX] */ \
+ if r0 s> 0 goto l_out_%=; /* r0 <= 0 */ \
+ if r0 s< -4095 goto l_out_%=; /* r0 in [-4095, 0] */ \
+ r0 = (s32)r0; /* redundant re-sext (pkcs7 pattern) */ \
+ if r0 s>= -4095 goto l_lo_ok_%=;/* must hold if range kept */ \
+ r0 /= 0; /* reached only if lower bound lost */ \
+l_lo_ok_%=: \
+ if r0 s<= 0 goto l_out_%=; /* must hold if range kept */ \
+ r0 /= 0; /* reached only if upper bound lost */ \
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A 32-bit sign-extension INSIDE a loop must verify and converge. This is the
+ * bytecode pattern bpf-gcc emits for a cond_break loop (see cond_break4): a
+ * counter is incremented with an ALU32 add (which zero-extends the high half)
+ * and then sign-extended in place every iteration.
+ *
+ * The verifier links dst<->src on a sign-extension. Doing that for a sext on a
+ * register carried across the loop back-edge mints/refreshes the linked scalar
+ * id and its BPF_FLAG_SUBREG_SEXT metadata each iteration; combined with the
+ * ALU32 add's BPF_FLAG_ADD_CONST delta the loop-carried state never repeats, so state
+ * pruning can't converge and verification runs to the 1M instruction limit.
+ *
+ * The regsafe() guard on the low-32 link flags is what prevents this: it only demands a
+ * match when the OLD state already carries a link (rold->id), so a register that
+ * first picks up a sext link inside the loop can still match its pre-loop state.
+ * Without that guard the loop-carried r2 never matches and the load fails at
+ * 1,000,001 insns, i.e. this __success flips to a load failure -- so this is the
+ * regression test for it. (See sext_in_loop_separate_dest_index for the
+ * companion case, a fresh in-loop temp that keeps its link for precision.)
+ *
+ * The pattern is written in asm so the bytecode is identical regardless of the
+ * host BPF compiler.
+ */
+SEC("socket")
+__success
+__naked void sext_in_loop_converges(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r2 = r0; /* r2 = 64-bit unknown (helper ret) */ \
+l_body_%=: \
+ .byte 0xe5; /* may_goto l_exit (loop bound) */ \
+ .byte 0; \
+ .short 3; \
+ .long 0; \
+ w2 += 1; /* ALU32 add: low += 1, high = 0 */ \
+ r2 = (s32)r2; /* in-place in-loop sign-extend */ \
+ goto l_body_%=; \
+l_exit_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A separate-destination 32-bit sign extension INSIDE a loop keeps its low-32
+ * link, so a later bounds check on the source narrows the sign-extended
+ * destination too. This is the bytecode a bpf-gcc build emits for array indexing
+ * in a bpf_for loop -- a fresh 32-bit index load, a separate "r1 = (s32)r0",
+ * then a bounds check on the index (verifier_global_subprogs' syscall_array_bpf_for).
+ *
+ * Both in-loop cases form the link -- subreg_link is just (sz == 4), with no
+ * liveness or loop-carried exclusion. What differs is what the link buys. Here
+ * the destination is a fresh temp, dead across the back-edge, so the link is
+ * pure precision: "if w0 > 99" narrows r1 to [0, 99] and the guarded
+ * div-by-zero is unreachable. In sext_in_loop_converges the target is the
+ * loop-carried counter, so the link is re-formed every iteration and the
+ * question is convergence instead -- answered by the regsafe() rold->id guard,
+ * not by declining to link.
+ *
+ * Written in asm so the bytecode is identical regardless of the host BPF
+ * compiler.
+ */
+SEC("socket")
+__success
+__naked void sext_in_loop_separate_dest_index(void)
+{
+ asm volatile (" \
+l_body_%=: \
+ .byte 0xe5; /* may_goto l_exit (loop bound) */ \
+ .byte 0; \
+ .short 7; \
+ .long 0; \
+ call %[bpf_get_prandom_u32];/* r0 = fresh u32 each iter */ \
+ r1 = (s32)r0; /* in-loop separate-dest sext */ \
+ if w0 > 0x63 goto l_body_%=;/* fall-through: w0 <= 99 */ \
+ /* want r1 = sext32(r0 low) == [0, 99] here (needs the link) */ \
+ if r1 > 0x63 goto l_err_%=;/* taken unless r1 narrowed */ \
+ goto l_body_%=; \
+l_err_%=: \
+ r0 /= 0; /* reachable iff r1 not narrowed */ \
+ goto l_body_%=; \
+l_exit_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A 32-bit zero-extending mov (w2 = w1) whose SOURCE is a sign-extended register
+ * must still zero-extend: dst's high bits are 0, not the sign-extension of the
+ * low field. Regression test for the zext link clearing BPF_FLAG_SUBREG_SEXT (otherwise
+ * dst would inherit SUBREG_SEXT from the sext'd source, and sync_linked_regs()
+ * would later rebuild it with reconstruct_sext32() -- computing a negative value
+ * for what is actually a large positive zero-extended one).
+ *
+ * r1 = (s32)r6 makes r1 a sext-linked wide source; w2 = w1 forms the zext link.
+ * After "if w6 s>= 0" falls through, r6's low 32 bits have bit 31 set, so the
+ * zero-extended r2 must be in [0x80000000, 0xffffffff]. Two guards assert that
+ * whole range, so the test needs the feature present, not merely the absence of
+ * the sext-leak bug: "r2 s< 0" catches the leak (r2 rebuilt negative), and
+ * "w2 s>= 0" catches the low-32 link being absent entirely (r2 not narrowed to
+ * the high half, so bit 31 is not known set). Either makes the div reachable.
+ */
+SEC("socket")
+__success
+__naked void zext_mov_from_sext_src_zero_extends(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; /* r6 low = unknown u32 (callee-saved) */ \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown (width 64) */ \
+ r1 = (s32)r6; /* r1 = sext32(r6 low): SUBREG_SEXT, wide */ \
+ w2 = w1; /* zext mov from sext-linked wide src */ \
+ if w6 s>= 0 goto l_out_%=;/* fall-through: r6 low has bit 31 set */ \
+ /* r2 = zext32(r6 low) must be in [0x80000000, 0xffffffff]: */ \
+ if r2 s< 0 goto l_err_%=;/* sext leak: r2 wrongly negative */ \
+ if w2 s>= 0 goto l_err_%=;/* link absent: r2 low bit 31 not known set */ \
+ goto l_out_%=; \
+l_err_%=: \
+ r0 /= 0; /* r2 not proven in [0x80000000, 0xffffffff] */ \
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Mirror of zext_mov_keeps_add_const_src for the sign-extending mov: a sext
+ * whose source carries an ADD_CONST delta must not destroy that link.
+ *
+ * Forming a low-32 link calls assign_scalar_id_before_mov(), which clears an
+ * ADD_CONST src, so the sext arm excludes such a source exactly as the zext
+ * arm does. Without that exclusion r5 loses its base+delta relationship to r6
+ * here, "if r6 > 10" no longer narrows r5, and the guarded div becomes
+ * reachable.
+ */
+SEC("socket")
+__success
+__naked void sext_mov_keeps_add_const_src(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; /* r6 low = unknown u32 */ \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown (base) */ \
+ r5 = r6; /* r5, r6 linked (shared id) */ \
+ r5 += 3; /* r5 = base + 3: ADD_CONST, still wide */ \
+ r7 = (s32)r5; /* 32-bit sext mov, ADD_CONST src */ \
+ if r6 > 10 goto l_out_%=;/* r6 in [0, 10] */ \
+ /* r5 = r6 + 3 must be in [3, 13] here (needs the kept link) */ \
+ if r5 > 13 goto l_err_%=;/* taken only if r5 not narrowed */ \
+ goto l_out_%=; \
+l_err_%=: \
+ r0 /= 0; /* reachable iff r5's link was cleared */ \
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Dest-driven direction, sign-extend flavour: narrowing the LINKED register
+ * must not narrow the wide base.
+ *
+ * r7 = (s32)r6 shares only r6's low 32 bits. Learning r7 == 0 says nothing
+ * about r6's high half, so sync_linked_regs() must leave r6 alone -- that is
+ * the "known_reg is subreg-linked" continue. If it ever propagated, r6 would
+ * be known 0 here and the div would be treated as unreachable, so the program
+ * must be REJECTED.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void sext_dest_driven_does_not_narrow_base(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; /* r6 low = unknown u32 */ \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown (base) */ \
+ r7 = (s32)r6; /* low-32 SEXT link */ \
+ if r7 != 0 goto l_out_%=;/* r7 == 0: low 32 bits are 0 */ \
+ if r6 != 0 goto l_out_%=;/* r6 may still have high bits set */ \
+ r0 /= 0; /* must stay reachable */ \
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+#endif /* cpuv4 sign extension */
+
char _license[] SEC("license") = "GPL";
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 7+ messages in thread
end of thread, other threads:[~2026-08-14 23:20 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-08-14 23:19 [RFC bpf-next 0/6] bpf: track scalar equality across the low 32 bits Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 1/6] bpf: turn bpf_reg_state->precise into a flags field [NFC] Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 2/6] bpf: move the linked-scalar flags into bpf_reg_state->flags [NFC] Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 3/6] bpf: support low-32 subreg scalar linking for zero-extending movs Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 4/6] selftests/bpf: cover low-32 subreg-equal link " Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 5/6] bpf: support low-32 subreg scalar linking for sign-extending movs Vineet Gupta
2026-08-14 23:19 ` [RFC bpf-next 6/6] selftests/bpf: cover 32-bit sign-extension low-32 links Vineet Gupta
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox