* [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits
@ 2026-10-20 16:18 Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 01/12] bpf: Keep the 32-bit range across a sign extension that cannot change it Vineet Gupta
` (11 more replies)
0 siblings, 12 replies; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16:18 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 series was motivated by BPF_GCC tendency to generate sign-extensions
which the verifier effectively doesn't handle at all for the scalar linked
tracking.
This can prevent correct programs from loading such as the test below,
0: (61) r2 = *(u32 *)(r1 +24)
1: (bf) r0 = (s32)r2
2: (56) if w2 != 0x0 goto pc+10 ; R2=0
12: (95) exit
leads to following load failure:
At program exit the register R0 has smin=-2147483648 smax=2147483647
should have been in [0, 1]
The verifier currently tracks the full 64 bits or nothing (the alu32
handling is also full 64-bits with upper bits known to be zeroes).
The sign extension at insn 1 has no way to say "same low 32 bits, high half
from bit 31", so it doesn't link r0 and r2, hence the insn 2 branch can't
narrow r0.
A slightly complex scenario involving sign extension is where the source
is already linked (bpf_sockmap_map_iter_fd/copy):
31: (85) call bpf_map_delete_elem#3 ; R0=scalar()
32: (bf) r1 = r0 ; R0=scalar(id=4) R1=scalar(id=4)
33: (bf) r0 = (s32)r0 ; R0=scalar(smin=0xffffffff80000000,smax=0x7fffffff)
34: (16) if w1 == 0x0 goto pc+6 ; R0 unchanged
41: (95) exit
And a zero extension has the same gap, but usually it only costs precision.
This is captured in existing verifier_reg_equal.c:subreg_equality_2 (since
2023):
call %[bpf_ktime_get_ns]
r2 = r0 <-- unknown high bits
w3 = w2 <-- only low half shared, not recorded
if w2 < 9 goto l0_%= <-- narrows w2
exit
l0_%=:
if r3 < 9 goto l1_%= <-- this doesn't deduce
r0 -= r1 <-- illegal read reachable
l1_%=:
exit
This series, among others, also removes this restriction, making the test
pass now.
-__description("check w reg not equal if r reg upper32 bits not 0")
-__failure __msg("R1 !read_ok")
+__description("check w reg equal if r reg upper32 bits not 0")
+__success
And finally this series also handles narrowing stack fills: a 4-byte read
of a value spilled wider. Its mirror image, the narrowing stack spill,
is implemented here too (patch 11-12) but is not proposed, see
Testing: veristat sub-section below for reasoning.
Improvements
============
This series completely eliminates two class of verifier failures in
selftests built with BPF_GCC:
- all 19 instances of "should have been in [0, 1]"
- all 6 instances of "The sequence of 8193 jumps is too complex"
It unblocks existing subreg_equality_2.
How it is modelled
==================
Upstream currently relates two scalars using ->id which additionally
encodes add_const with a optional delta. Sign-extension requires a different
relationship which is low32 same only. This series generalizes the
existing mechanisms:
For an abstract scalar X, a register can be:
X + delta zext(X + delta) sext(X + delta)
The first is the existing add_const and other two are the new
functionality and also support the optional delta. The relationship now
looks like:
enum bpf_reg_link_kind {
BPF_REG_LINK_NONE = 0,
BPF_REG_LINK_FULL, /* all 64 bits shared */
BPF_REG_LINK_ZEXT, /* low 32 shared, high half zero */
BPF_REG_LINK_SEXT, /* low 32 shared, high half = bit 31 */
};
Four values fit the two bits add_const already had, so the encoding
costs no space: bpf_reg_state stays 80 bytes and bpf_func_state stays in
the 1K allocator bucket that commit a2052333e6f9 ("bpf: Bpf_func_state
size optimization") put it in.
Other details to be aware of
============================
- Sext with delta is supported.
- Semantics of BPF_ADD_CONST32 change: It used to be:
reg == base + delta, base known to fit u32
Now it is modelled as:
BPF_REG_LINK_ZEXT: reg == (u32)(base + delta), for ANY base width.
- Delta composing/stacking: is allowed now, albeit only once:
"w3 = w0; w3 -= 1" is now able to keep the regs linked
Composing further is deliberately not done, as it interferes with
state pruning in loops. On arena_strsearch, allowing any second delta
costs 1176 -> 1751 insns and 102 -> 133 states; allowing it onto a zero
delta produced by an add rather than by the mov still costs 1176 -> 1196.
- Propagating a delta backwards: patches 4 and 6 already do that for
base that fits 32-bits, for wide base, patch 8 does that for
completeness. It does fix the directed test zext_reverse_pins_low_half,
and the instrumented arm fires 78 times under bpf-gcc, 40 times under
clang, but no visible improvements.
Testing
=======
- kernel off bpf-next baseline of 26/10/16, commit d2141481a764 "(bpf: Free
the subprog jump tables once the CFG passes are done)"
- bpf-gcc (20261010, ga02e2004cb70).
Only patch 1-10 are used for testing as the last 2 are just for demonstration
(as asked for in v2), but not really production.
1. BPF_GCC built selftest changes:
before: 476 FAIL 6912 OK 749 SKIP
after: 450 FAIL 6985 OK 751 SKIP
bpf_ip_check_defrag FAIL -> OK
bpf_ip_check_defrag/v4 FAIL -> OK
bpf_ip_check_defrag/v6 FAIL -> OK
bpf_iter FAIL -> OK
bpf_iter/bpf_sockmap_map_iter_fd FAIL -> OK
bpf_iter/task_pid FAIL -> OK
bpf_iter/task_pidfd FAIL -> OK
bpf_iter/task_sleepable FAIL -> OK
bpf_iter/task_tid FAIL -> OK
bpf_sockmap_map_iter_fd FAIL -> OK
setget_sockopt FAIL -> OK
sock_addr/connect_unix: attach prog with wrong attach type FAIL -> OK
sock_addr/connect_unix: connect (stream) FAIL -> OK
sock_addr/connect_unix: connect deny (stream) FAIL -> OK
sock_addr/connect_unix: kernel_connect (dgram) FAIL -> OK
sock_addr/connect_unix: kernel_connect deny (dgram) FAIL -> OK
sock_addr/sendmsg_unix: attach prog with wrong attach type FAIL -> OK
sock_addr/sendmsg_unix: kernel_sendmsg deny (dgram) FAIL -> OK
sock_addr/sendmsg_unix: sendmsg (dgram) FAIL -> OK
sock_addr/sendmsg_unix: sendmsg deny (dgram) FAIL -> OK
sock_addr/sendmsg_unix: sock_sendmsg (dgram) FAIL -> OK (runs twice)
sock_addr/sendmsg_unix: sock_sendmsg deny (dgram) FAIL -> OK
sockmap_basic FAIL -> OK
sockmap_basic/sockhash copy FAIL -> OK
sockmap_basic/sockmap copy FAIL -> OK
2. veristat on selftests built off bpf-gcc, clang and a corpora of prebuilt
bpf objects.
bpf-gcc, 3314 programs verifying on both sides:
verdicts 12 pre-existing failure -> success
total_insns 4 changed, 2 worse, -16 overall: cond_break3 36 -> 48,
ksock_wq_start 207 -> 213, estab 2849 -> 2817, and the
series' own zext_contradiction_keeps_range_sane 11 -> 9
total_states 1 changed, 1 worse: cond_break3 4 -> 6
clang, 3520 programs verifying on both sides:
verdicts 1 pre-existing: subreg_equality_2
total_insns 3 changed, 1 worse, +126 overall: big_alloc2
2956 -> 3095, cond_break2 90 -> 79, and the series' own
zext_contradiction_keeps_range_sane 11 -> 9
total_states 2 changed, 1 worse: big_alloc2 157 -> 165,
cond_break2 10 -> 9
and an external corpus -- 441 objects from cilium, katran, fb and
sched_ext, 1467 programs verifying on both sides (increase test coverage
from selftest 5.4M insns and 15 progs above 50k insns to 25.2M insns and
131 progs over 50k insns).
verdicts no change
total_insns 12 changed, 10 worse, +7087 (+0.028%); two improve.
Worst is +1812 on test_file_open, 2470 -> 4282, in
bpfjailer .../lib-tests-bpf-open-open.bpf.o
total_states 9 changed, 7 worse, +242 (+0.026%); worst +155 on the
same program
3. Applying 11-12 on top of 1-10:
bpf-gcc nothing at all -- no program changes
clang one program changes, and it improves
external 102 changed, 63 worse, +84450 insns (+0.335%) and
+6257 states (+0.661%). Not a broad slowdown: the three
below carry 97% of it. Of the remaining 60, two are
+26.6% and +7.7%; the other 58 are under 1% each.
+89.7% +19784 rusty_enqueue 22053 -> 41837
scx_rusty.bpf.o
+57.2% +59616 test_file_open 104160 -> 163776
bpfjailer .../match-tests-...-file.bpf.o
+40.6% +2688 layered_enqueue 6626 -> 9314
scx_layered 1.0.11.1
Two notes for anyone re-running the above.
Four programs in the external corpus are named test_file_open. The one
at +57.2% here is in .../match-tests-...-file.bpf.o; the +1812 in
section 2 is a different and much smaller program in
.../lib-tests-...-open.bpf.o, which these two patches take the other
way, 4282 -> 2476.
And veristat's raw verdict-change counts are larger than the twelve in
section 2 -- 28 on bpf-gcc, 17 on clang -- because the corpus is built
from the series tree, so the series' own new tests read as
failure -> success too. zext_mov_breaks_linked_src goes the other way,
success -> failure: it is an intentional __failure test, and veristat
records "failure" for a program that does not load.
Patches
=======
1-2 fix a sign extension that cannot change the range but widens it
anyway, which is unrelated to the rest and was asked to go first
3 move the linked-scalar flags out of bpf_reg_state->id
4-5 zero-extending movs
6-7 sign-extending movs, including the inherited delta
8 the reverse direction, for a base wider than 32 bits
9-10 narrowing stack fills
11-12 [do not merge] narrowing stack spills
Patches 1-10 are what is proposed. 11-12 are posted because the relation
is the one asked for and implementing it was the only way to find out
what it costs; the answer is in 11's message and it is not worth it.
Changes since v2
================
- the kind moves out of bpf_reg_state->id into an enum of its own
(Eduard), replacing v2's add_const plus a separate subreg_sext
bool. bpf_reg_state stays 80 bytes. v2's 2/13 is squashed into the
patch that needs it (Alexei).
- the zero-extending link is ADD_CONST32 with a zero delta rather
than a kind of its own (Alexei), which drops the
dst_umax > U32_MAX guard -- the one pre-existing semantic this
series changes, described above.
- sign-extending movs carry a delta, which v2 did not support.
- 4/12 fixes a reachable WARNING found while preparing this revision:
the intersect step could leave an empty range behind. v2 never
showed it because its 8/13 happened to mask it.
- 9/12 reports its cost, which v2 did not: +6598 insns over six
external programs, with no verdict change.
- v2's 11/13 is dropped; the two spill patches are now [do not
merge], with the measurement behind that call in 11/12.
The per-patch changelogs under each --- have the rest.
v2:
https://lore.kernel.org/bpf/20260910164635.459558-1-vineet.gupta@linux.dev/
RFC:
https://lore.kernel.org/bpf/20260814231945.3884596-1-vineet.gupta@linux.dev/
Vineet Gupta (12):
bpf: Keep the 32-bit range across a sign extension that cannot change
it
selftests/bpf: Cover sign extensions that cannot change the range
bpf: Prepare linked scalars for relations narrower than 64 bits
bpf: Track low-32 scalar equality across zero-extending movs
selftests/bpf: Cover the low-32 link for zero-extending movs
bpf: Track low-32 scalar equality across sign-extending movs
selftests/bpf: Cover the low-32 link for sign-extending movs
bpf: Recover the low 32 bits on the reverse link direction
bpf: Track low-32 scalar equality across narrowing stack fills
selftests/bpf: Cover the low-32 link for narrowing stack fills
[do not merge] bpf: Track low-32 scalar equality across narrowing
stack spills
[do not merge] selftests/bpf: Cover the low-32 link for narrowing
stack spills
include/linux/bpf_verifier.h | 52 +-
include/linux/tnum.h | 7 +
kernel/bpf/log.c | 6 +-
kernel/bpf/scev.c | 2 +-
kernel/bpf/states.c | 38 +-
kernel/bpf/tnum.c | 15 +
kernel/bpf/verifier.c | 387 ++++-
tools/testing/selftests/bpf/progs/bpf_misc.h | 16 +
.../selftests/bpf/progs/verifier_bounds.c | 2 +-
.../selftests/bpf/progs/verifier_ldsx.c | 8 +-
.../bpf/progs/verifier_linked_scalars.c | 1323 ++++++++++++++++-
.../selftests/bpf/progs/verifier_movsx.c | 63 +-
.../selftests/bpf/progs/verifier_reg_equal.c | 14 +-
.../selftests/bpf/progs/verifier_spill_fill.c | 6 +-
14 files changed, 1787 insertions(+), 152 deletions(-)
--
2.53.0-Meta
^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 01/12] bpf: Keep the 32-bit range across a sign extension that cannot change it
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
@ 2026-10-20 16:18 ` Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 02/12] selftests/bpf: Cover sign extensions that cannot change the range Vineet Gupta
` (10 subsequent siblings)
11 siblings, 0 replies; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16:18 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 patch addresses the verifier deficiency where it would throw away
a good range whenever that range crossed zero.
| 1: (54) w0 &= 63 ; R0=scalar(smin32=0,smax32=63,...)
| 2: (14) w0 -= 63 ; R0=scalar(smin32=-63,smax32=0,...)
| 3: (bc) w0 = (s8)w0 ; R0=scalar(smin32=-128,smax32=127,...)
| 4: (c6) if w0 s< 0xffffffc1 goto pc+2
| ...
| 7: (34) w0 /= 0
| div by zero
[-63, 0] already fits an s8, so insn 3 cannot change any value in it, yet
the range comes out widened to [-128, 127]. The guard at insn 4 then
cannot be resolved and the div becomes reachable.
The issue is the following check in coerce_subreg_to_size_sx()
top_smax_value = ((u32)reg_s32_max(reg) >> num_bits) << num_bits;
top_smin_value = ((u32)reg_s32_min(reg) >> num_bits) << num_bits;
if (top_smax_value != top_smin_value)
goto out;
which doesn't fire when the range includes zero, since the top bits
differ. e.g. for [-63, 0]:
smin32 = -63: high bits all ones
smax32 = 0: high bits all zero
The cheap noop test above it does not catch this either -- it only looks
at reg_umax(), which a negative smin makes huge.
The 64-bit twin, coerce_reg_to_size_sx(), had the same gap and was given
an equivalent early return by commit 0892ef2a7ef3 ("bpf: Representation
for intervals with steps"). This patch does the same for the 32-bit path,
for the s8 and s16 widths it handles. It doesn't improve anything in
selftests or corpora of external objects -- the shape above only shows up
in the test the next patch adds -- but seems like the right thing to do
anyways.
Fixes: 8100928c8814 ("bpf: Support new sign-extension mov insns")
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 5/13.
- moved to the front: it is unrelated to the low-32 tracking (Alexei)
- narrowed to the 32-bit path. Commit 0892ef2a7ef3 ("bpf:
Representation for intervals with steps") has since given
coerce_reg_to_size_sx() an equivalent early return, so Fixes:
1f9a1ea821ff goes with that half.
- measured inert: 0 instruction and 0 state changes on both selftest
corpora and on 441 external objects.
kernel/bpf/verifier.c | 22 ++++++++++++++++++++++
1 file changed, 22 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 62f8951126ba..e1b41975a442 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6182,6 +6182,7 @@ static void set_sext32_default_val(struct bpf_reg_state *reg, int size)
static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size)
{
s32 init_s32_max, init_s32_min, s32_max, s32_min, u32_val;
+ s32 field_smin, field_smax;
u32 top_smax_value, top_smin_value;
u32 num_bits = size * 8;
@@ -6192,6 +6193,27 @@ static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size)
if (reg_umax(reg) < (1ULL << (num_bits - 1)))
return;
+ if (size == 1) {
+ field_smin = S8_MIN;
+ field_smax = S8_MAX;
+ } else {
+ /* size == 2 */
+ field_smin = S16_MIN;
+ field_smax = S16_MAX;
+ }
+
+ /*
+ * The range already fits the field, so (sN)v == v for every value the
+ * register can hold and the sign extension changes nothing. The test
+ * above misses this once the range straddles zero: it only looks at
+ * reg_umax(), which a negative smin makes huge.
+ *
+ * This has to precede reg_step_reset() below: the extension is a noop,
+ * so the base/step line still holds and there is nothing to discard.
+ */
+ if (reg_s32_min(reg) >= field_smin && reg_s32_max(reg) <= field_smax)
+ return;
+
/* See comment at reg_step_check_unsigned(). */
reg_step_reset(reg);
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 02/12] selftests/bpf: Cover sign extensions that cannot change the range
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 01/12] bpf: Keep the 32-bit range across a sign extension that cannot change it Vineet Gupta
@ 2026-10-20 16:18 ` Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits Vineet Gupta
` (9 subsequent siblings)
11 siblings, 0 replies; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16:18 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
Two programs, one per field width that coerce_subreg_to_size_sx() handles.
Each builds a 32-bit range that straddles zero but still fits the target
field, so the sign extension is a no-op: [-63, 0] for (s8) and [-4095, 0]
for (s16). The guard that follows can only be resolved statically if the
range survives, and it protects a div by zero, so a widened range is a
verification failure rather than a silently weaker test.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 6/13.
- moved with patch 1, and narrowed to the 32-bit mov to match it. The
ALU64 forms v2 tested now pass with or without the patch.
.../selftests/bpf/progs/verifier_movsx.c | 55 +++++++++++++++++++
1 file changed, 55 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_movsx.c b/tools/testing/selftests/bpf/progs/verifier_movsx.c
index 195b27a51224..3fcd03b7a547 100644
--- a/tools/testing/selftests/bpf/progs/verifier_movsx.c
+++ b/tools/testing/selftests/bpf/progs/verifier_movsx.c
@@ -202,6 +202,61 @@ l0_%=: \
: __clobber_all);
}
+/*
+ * A 32-bit range that already fits the field is unchanged by the sign
+ * extension. Both of these straddle zero, so reg_umax() is huge and the high
+ * bits of s32_min and s32_max differ: neither of the gates that predate
+ * testing the range against the field can keep it. The guard that follows can
+ * only be resolved statically if the range survives, and it protects a div by
+ * zero, so a widened range is a verification failure rather than a silently
+ * weaker test.
+ */
+SEC("socket")
+__description("MOV32SX, S8, negative range is preserved")
+__success __success_unpriv __retval(0)
+__naked void mov32sx_s8_negative_range(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ w0 &= 0x3f; \
+ w0 -= 0x3f; \
+ /* w0 is [-63, 0], already a valid s8 */ \
+ w0 = (s8)w0; \
+ if w0 s< -0x3f goto l0_%=; \
+ w0 = 0; \
+ exit; \
+l0_%=: \
+ /* unreachable unless the range was widened */ \
+ w0 /= 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+SEC("socket")
+__description("MOV32SX, S16, negative range is preserved")
+__success __success_unpriv __retval(0)
+__naked void mov32sx_s16_negative_range(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ w0 &= 0xfff; \
+ w0 -= 0xfff; \
+ /* w0 is [-4095, 0], already a valid s16 */ \
+ w0 = (s16)w0; \
+ if w0 s< -0xfff goto l0_%=; \
+ w0 = 0; \
+ exit; \
+l0_%=: \
+ /* unreachable unless the range was widened */ \
+ w0 /= 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
SEC("socket")
__description("MOV64SX, S16, R10 Sign Extension")
__failure __msg("R1 type=scalar expected=fp, pkt, pkt_meta, map_key, map_value, mem, ringbuf_mem, buf, trusted_ptr_")
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 01/12] bpf: Keep the 32-bit range across a sign extension that cannot change it Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 02/12] selftests/bpf: Cover sign extensions that cannot change the range Vineet Gupta
@ 2026-10-20 16:18 ` Vineet Gupta
2026-10-20 17:08 ` bot+bpf-ci
2026-10-20 16:18 ` [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs Vineet Gupta
` (8 subsequent siblings)
11 siblings, 1 reply; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16:18 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
Two scalars sharing an ->id are always related by full 64-bit equality
today: reg == base + delta over all 64 bits (this is true for
BPF_ADD_CONST32 as well, which implies upper bits to be all zero).
Sign-extension needs a genuinely low32 equal only relationship kind
with bit 31 supplying upper 32-bits.
Today the following 2 relationships exist
#define BPF_ADD_CONST64 (1U << 31)
#define BPF_ADD_CONST32 (1U << 30)
Model them differently as
enum bpf_reg_link_kind { BPF_REG_LINK_NONE, BPF_REG_LINK_FULL,
BPF_REG_LINK_ZEXT, BPF_REG_LINK_SEXT };
So BPF_ADD_CONST64 becomes BPF_REG_LINK_FULL and BPF_ADD_CONST32 becomes
BPF_REG_LINK_ZEXT with the exact same semantics as today. But this paves
the way for a future BPF_REG_LINK_SEXT in the same framework.
The implementation needs to change as well. Today the above 2 bits are
shoe-horned into ->id, needing masking and OR'ing to get ->id and kind
bits: with more types and bits needed, move them out into an enum
bitfield of its own. To avoid growing the storage (and stay within the
1K allocator bucket), borrow 2 bits out of ->map_uid, 31 -> 29, which is
still far more ids than a program can generate.
->id becomes a plain identifier, so check_scalar_ids() loses its "compare
the compound id, then the base id" dance in favour of one check_ids().
With the kind out of ->id it also leaves the idmap key, so regs_exact()
and regsafe()'s explore_alu_limits arm have to compare it explicitly.
One case changes behaviour -- old {r2.id=A+delta32} against
cur {r2.id=B+delta64} was accepted and is now rejected, correctly, since
alu32 and alu64 deltas diverge in sync_linked_regs().
Clearing a link is no longer just ->id = 0: any stale ->link_kind needs
to be cleared out as well. And given this needs to be done in the newly
added kernel/bpf/scev.c, it is moved into bpf_verifier.h as
bpf_clear_scalar_id().
The helper also zeroes ->delta, which the open-coded clear left behind.
Unlike ->id that field is inside the memcmp() prefix state comparison
uses, so a leftover value could keep two otherwise-identical states
apart; clearing it can only help pruning.
Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 1/13, with v2 2/13 folded in (Alexei: squash the [NFC] patch
into the one that needs it).
- [NFC] dropped from the subject. It is not: check_ids() pairs ids
rather than comparing them, so moving the kind out of ->id changes
which states match. The message works through the one case.
- new encoding, following Eduard's framing: enum bpf_reg_link_kind,
with NONE/FULL/ZEXT/SEXT in the two bits add_const already had,
replacing v2's add_const plus a separate subreg_sext bool.
bpf_reg_state stays 80 bytes.
- clear_scalar_id() exported as bpf_clear_scalar_id() for scev.c, which
was the last site clearing a scalar ->id by hand.
- regsafe()'s explore_alu_limits arm goes back to open-coding memcmp +
check_scalar_ids(); v2's switch to regs_exact() had quietly changed
which comparison that path used.
include/linux/bpf_verifier.h | 50 ++++++++++++---
kernel/bpf/log.c | 4 +-
kernel/bpf/scev.c | 2 +-
kernel/bpf/states.c | 38 ++++--------
kernel/bpf/verifier.c | 62 +++++++++----------
.../bpf/progs/verifier_linked_scalars.c | 44 ++++++-------
6 files changed, 108 insertions(+), 92 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 112ca1511da4..bb369b320334 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -50,6 +50,27 @@ enum bpf_iter_state {
BPF_ITER_STATE_DRAINED,
};
+/*
+ * Records how a register derives from the base of its ->id set. The kind
+ * says which bits are shared and how the rest are filled; ->delta says by
+ * how much, and is meaningful for every kind:
+ *
+ * BPF_REG_LINK_FULL: reg == base + delta
+ * BPF_REG_LINK_ZEXT: reg == (u32)(base + delta), base known to fit u32
+ * BPF_REG_LINK_SEXT: reg == (s32)(base + delta)
+ *
+ * r1 = r2; r1 and r3 are linked to r2: id == N
+ * r3 = r2;
+ * r1 += 10; r1 gets BPF_REG_LINK_FULL, delta 10
+ * w3 += 10; w3 gets BPF_REG_LINK_ZEXT, delta 10
+ */
+enum bpf_reg_link_kind {
+ BPF_REG_LINK_NONE = 0,
+ BPF_REG_LINK_FULL, /* all 64 bits shared */
+ BPF_REG_LINK_ZEXT, /* low 32 shared, high half zero */
+ BPF_REG_LINK_SEXT, /* low 32 shared, high half repeats bit 31 */
+};
+
struct bpf_reg_state {
/* Ordering of fields matters. See states_equal() */
enum bpf_reg_type type;
@@ -160,16 +181,9 @@ struct bpf_reg_state {
* to a specific instance of bpf_iter.
*/
/*
- * Upper bit of ID is used to remember relationship between "linked"
- * registers. Example:
+ * Registers sharing an ->id are "linked":
* r1 = r2; both will have r1->id == r2->id == N
- * r1 += 10; r1->id == N | BPF_ADD_CONST 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
*/
-#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.
@@ -184,11 +198,29 @@ struct bpf_reg_state {
* other registers. Kept outside the metadata union for ID remapping
* during state comparisons.
*/
- u32 map_uid:31;
+ u32 map_uid:29;
/* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
u32 precise:1;
+ /*
+ * How this register relates to the others sharing its ->id.
+ * Non-zero only if ->id is. Shares the word above so that
+ * bpf_reg_state stays 80 bytes.
+ */
+ enum bpf_reg_link_kind link_kind:2;
};
+/*
+ * Drop a scalar out of its ->id set. ->link_kind and ->delta are only
+ * meaningful next to an ->id, so all three have to go together; this is the
+ * only correct way to clear them.
+ */
+static inline void bpf_clear_scalar_id(struct bpf_reg_state *reg)
+{
+ reg->id = 0;
+ reg->delta = 0;
+ reg->link_kind = BPF_REG_LINK_NONE;
+}
+
static inline s64 reg_smin(const struct bpf_reg_state *reg)
{
return cnum64_smin(reg->r64);
diff --git a/kernel/bpf/log.c b/kernel/bpf/log.c
index 5432c0fc442b..a6f205653a9e 100644
--- a/kernel/bpf/log.c
+++ b/kernel/bpf/log.c
@@ -651,8 +651,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->link_kind)
verbose(env, "%+d", reg->delta);
if (reg->parent_id)
verbose_a("parent_id=%d", reg->parent_id);
diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
index 48500d73105a..f0aa314233c8 100644
--- a/kernel/bpf/scev.c
+++ b/kernel/bpf/scev.c
@@ -2285,7 +2285,7 @@ static void scratch_widened_reg_id(struct bpf_verifier_env *env, struct bpf_reg_
{
switch (base_type(reg->type)) {
case SCALAR_VALUE:
- reg->id = 0;
+ bpf_clear_scalar_id(reg);
break;
case PTR_TO_PACKET:
case PTR_TO_PACKET_META:
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index 953700822fa7..a1b90a31747a 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -391,13 +391,6 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
* and r7.id=0 (both independent), without temp IDs both would map old_id=X
* 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.
*/
static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
{
@@ -406,15 +399,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,
@@ -512,6 +497,7 @@ static bool regs_exact(const struct bpf_reg_state *rold,
struct bpf_idmap *idmap)
{
return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
+ rold->link_kind == rcur->link_kind &&
check_ids(rold->id, rcur->id, idmap) &&
check_ids(rold->parent_id, rcur->parent_id, idmap) &&
check_ids(rold->map_uid, rcur->map_uid, idmap);
@@ -566,6 +552,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
* logic and requires everything to be strict
*/
return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
+ rold->link_kind == rcur->link_kind &&
check_scalar_ids(rold->id, rcur->id, idmap);
}
if (!rold->precise && exact == NOT_EXACT)
@@ -574,13 +561,14 @@ 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 that the link kinds agree, along with any delta
+ * they carry.
*
* +------------------+-----------+------------------+---------------+
- * | | rold->id | rold + ADD_CONST | rold->id == 0 |
+ * | | rold->id | rold linked kind | rold->id == 0 |
* |------------------+-----------+------------------+---------------|
* | rcur->id | range,ids | false | range |
- * | rcur + ADD_CONST | false | range,ids,off | range |
+ * | rcur linked kind | false | range,ids,delta | range |
* | rcur->id == 0 | range,ids | false | range |
* +------------------+-----------+------------------+---------------+
*
@@ -610,17 +598,15 @@ 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
- * sync_linked_regs() (alu32 zero-extends, alu64 does not),
- * so pruning across different flag types is unsafe.
+ * The link kinds must match: alu32 and alu64 adds have different
+ * linking semantics in sync_linked_regs() (alu32 zero-extends,
+ * alu64 does not), so pruning across them is unsafe.
*/
- if (rold->id &&
- (rold->id & BPF_ADD_CONST) != (rcur->id & BPF_ADD_CONST))
+ if (rold->id && rold->link_kind != rcur->link_kind)
return false;
/* Both have offset linkage: offsets must match */
- if ((rold->id & BPF_ADD_CONST) && rold->delta != rcur->delta)
+ if (rold->link_kind && 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 e1b41975a442..609342940d1a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2060,6 +2060,7 @@ static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
reg->id = 0;
reg->parent_id = 0;
reg->map_uid = 0;
+ reg->link_kind = BPF_REG_LINK_NONE;
___mark_reg_known(reg, imm);
}
@@ -3752,12 +3753,6 @@ static bool __is_pointer_value(bool allow_ptr_leaks,
return is_pointer_regtype(reg->type);
}
-static void clear_scalar_id(struct bpf_reg_state *reg)
-{
- reg->id = 0;
- reg->delta = 0;
-}
-
static void assign_scalar_id_before_mov(struct bpf_verifier_env *env,
struct bpf_reg_state *src_reg)
{
@@ -3768,8 +3763,8 @@ 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)
- clear_scalar_id(src_reg);
+ if (src_reg->link_kind)
+ bpf_clear_scalar_id(src_reg);
/*
* Ensure that src_reg has a valid ID that will be copied to
* dst_reg and then will be used by sync_linked_regs() to
@@ -3921,7 +3916,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
save_register_state(env, state, spi, reg, size);
/* Break the relation on a narrowing spill. */
if (!reg_value_fits)
- clear_scalar_id(&ss->spilled_ptr);
+ bpf_clear_scalar_id(&ss->spilled_ptr);
} else if (!reg && !(off % BPF_REG_SIZE) && is_bpf_st_mem(insn) &&
env->bpf_capable) {
struct bpf_reg_state *tmp_reg = &env->fake_reg[0];
@@ -4278,7 +4273,7 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,
* coerce_reg_to_size will adjust the boundaries.
*/
if (get_reg_width(reg) > size * BITS_PER_BYTE)
- clear_scalar_id(&state->regs[dst_regno]);
+ bpf_clear_scalar_id(&state->regs[dst_regno]);
} else {
int spill_cnt = 0, zero_cnt = 0;
@@ -7385,7 +7380,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b
coerce_reg_to_size_sx(®s[value_regno], size);
if (!no_sext)
- clear_scalar_id(®s[value_regno]);
+ bpf_clear_scalar_id(®s[value_regno]);
}
}
@@ -16894,7 +16889,7 @@ static void scalar_byte_swap(struct bpf_reg_state *dst_reg, struct bpf_insn *ins
* any existing ties and avoid incorrect bounds propagation.
*/
if (need_bswap || insn->imm == 16 || insn->imm == 32)
- clear_scalar_id(dst_reg);
+ bpf_clear_scalar_id(dst_reg);
if (need_bswap) {
if (insn->imm == 16)
@@ -17333,18 +17328,18 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
off = -off;
}
- if (dst_reg->id & BPF_ADD_CONST) {
+ if (dst_reg->link_kind) {
/*
* If the register already went through rX += val
* we cannot accumulate another val into rx->off.
*/
clear_id:
- clear_scalar_id(dst_reg);
+ bpf_clear_scalar_id(dst_reg);
} else {
if (alu32)
- dst_reg->id |= BPF_ADD_CONST32;
+ dst_reg->link_kind = BPF_REG_LINK_ZEXT;
else
- dst_reg->id |= BPF_ADD_CONST64;
+ dst_reg->link_kind = BPF_REG_LINK_FULL;
dst_reg->delta = off;
}
} else {
@@ -17352,7 +17347,7 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
* Make sure ID is cleared otherwise dst_reg min/max could be
* incorrectly propagated into other registers by sync_linked_regs()
*/
- clear_scalar_id(dst_reg);
+ bpf_clear_scalar_id(dst_reg);
}
return 0;
}
@@ -17548,7 +17543,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
assign_scalar_id_before_mov(env, src_reg);
*dst_reg = *src_reg;
if (!no_sext)
- clear_scalar_id(dst_reg);
+ bpf_clear_scalar_id(dst_reg);
coerce_reg_to_size_sx(dst_reg, insn->off >> 3);
} else {
mark_reg_unknown(env, regs, insn->dst_reg);
@@ -17573,7 +17568,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
* propagated into src_reg by sync_linked_regs()
*/
if (!is_src_reg_u32)
- clear_scalar_id(dst_reg);
+ bpf_clear_scalar_id(dst_reg);
} else {
/* case: W1 = (s8, s16)W2 */
bool no_sext = reg_umax(src_reg) < (1ULL << (insn->off - 1));
@@ -17582,7 +17577,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
assign_scalar_id_before_mov(env, src_reg);
*dst_reg = *src_reg;
if (!no_sext)
- clear_scalar_id(dst_reg);
+ bpf_clear_scalar_id(dst_reg);
coerce_subreg_to_size_sx(dst_reg, insn->off >> 3);
}
} else {
@@ -18388,7 +18383,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);
@@ -18397,7 +18392,7 @@ static void __collect_linked_regs(struct linked_regs *reg_set, struct bpf_reg_st
e->is_reg = is_reg;
e->regno = spi_or_reg;
} else {
- clear_scalar_id(reg);
+ bpf_clear_scalar_id(reg);
}
}
@@ -18416,7 +18411,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];
@@ -18454,18 +18448,20 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
: &bpf_stack_slot(vstate->frame[e->frameno], 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->link_kind && known_reg->link_kind &&
+ reg->link_kind != known_reg->link_kind)
continue;
- if ((!(reg->id & BPF_ADD_CONST) && !(known_reg->id & BPF_ADD_CONST)) ||
+ if ((!reg->link_kind && !known_reg->link_kind) ||
reg->delta == known_reg->delta) {
*reg = *known_reg;
} else {
+ enum bpf_reg_link_kind saved_link_kind = reg->link_kind;
s32 saved_off = reg->delta;
u32 saved_id = reg->id;
@@ -18475,17 +18471,19 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
/* reg = known_reg; reg += delta */
*reg = *known_reg;
/*
- * Must preserve off and id, otherwise another sync_linked_regs()
- * will be incorrect.
+ * Must preserve off, id and link_kind, otherwise another
+ * sync_linked_regs() will be incorrect.
*/
reg->delta = saved_off;
reg->id = saved_id;
+ reg->link_kind = saved_link_kind;
scalar_step_add(reg, reg, &fake_reg);
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->link_kind == BPF_REG_LINK_ZEXT ||
+ known_reg->link_kind == BPF_REG_LINK_ZEXT)
zext_32_to_64(reg);
reg_bounds_sync(reg);
}
@@ -19582,7 +19580,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, ({
@@ -19590,8 +19588,8 @@ 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)
- clear_scalar_id(reg);
+ if (idset_cnt_get(idset, reg->id) == 1)
+ bpf_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..5a120fc7c1e7 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -349,8 +349,8 @@ 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() checks the linked target register (reg) for
+ * BPF_REG_LINK_ZEXT rather than the branch register (known_reg).
*/
SEC("socket")
__success
@@ -360,7 +360,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; /* BPF_REG_LINK_ZEXT delta */ \
r8 = 0xFFFFffff ll; \
if r6 < r8 goto l0_%=; \
/* r6 in [0xFFFFFFFF, 0xFFFFFFFF] */ \
@@ -381,7 +381,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_REG_LINK_ZEXT) and the other used alu64 (BPF_REG_LINK_FULL).
* The delta relationship doesn't hold across different ALU widths.
*/
SEC("socket")
@@ -392,13 +392,13 @@ __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; /* BPF_REG_LINK_ZEXT delta */ \
r8 = r6; /* linked: same id as r6 */ \
- r8 += 2; /* alu64: BPF_ADD_CONST64, delta = 2 */ \
+ r8 += 2; /* BPF_REG_LINK_FULL delta */ \
r9 = 0xFFFFffff ll; \
if r7 < r9 goto l0_%=; \
/* r7 = 0xFFFFFFFF */ \
- /* sync: known_reg=r7 (ADD_CONST32), reg=r8 (ADD_CONST64) */ \
+ /* sync: known_reg=r7 (BPF_REG_LINK_ZEXT), reg=r8 (BPF_REG_LINK_FULL) */ \
/* Without fix: r8 = zext(0xFFFFFFFF + 1) = 0 */ \
/* With fix: r8 stays [2, 0x100000001] (r8 >= 2) */ \
if r8 > 0 goto l1_%=; \
@@ -416,7 +416,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_REG_LINK_ZEXT from alu32, another BPF_REG_LINK_FULL from alu64).
*/
SEC("socket")
__failure __msg("div by zero")
@@ -431,11 +431,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_REG_LINK_ZEXT delta */\
goto l_merge_%=; \
l_pathb_%=: \
/* Path B: alu64 */ \
- r7 += 1; /* BPF_ADD_CONST64, delta = 1 */\
+ r7 += 1; /* BPF_REG_LINK_FULL delta */\
l_merge_%=: \
/* Merge point: regsafe() compares path B against cached path A. */ \
/* Narrow r6 to trigger sync_linked_regs for r7 */ \
@@ -593,7 +593,7 @@ l_exit_%=: \
}
/*
- * Test that stale delta from a cleared BPF_ADD_CONST does not leak
+ * Test that a stale delta from a cleared link does not leak
* through assign_scalar_id_before_mov() into a new id, causing
* sync_linked_regs() to compute an incorrect offset.
*/
@@ -605,10 +605,10 @@ __naked void scalars_stale_delta_from_cleared_id(void)
asm volatile (" \
call %[bpf_get_prandom_u32]; \
r6 = r0; /* r6 unknown, gets id A */ \
- r6 += 5; /* id A|ADD_CONST, delta 5 */ \
+ r6 += 5; /* id A, BPF_REG_LINK_FULL delta */ \
r6 ^= 0; /* id cleared; delta stays 5 */ \
r8 = r6; /* new id B, stale delta 5 */ \
- r8 += 3; /* id B|ADD_CONST, delta 3 */ \
+ r8 += 3; /* id B, BPF_REG_LINK_FULL delta */ \
r9 = r6; /* id B, stale delta 5 */ \
if r9 != 10 goto l_exit_%=; \
/* Bug: r8 = 10+(3-5) = 8; Fix: r8 = 10+(3-0) = 13 */ \
@@ -648,19 +648,19 @@ l_exit_%=: \
}
/*
- * Test that regsafe() verifies base_id consistency for BPF_ADD_CONST
- * linked scalars during state pruning.
+ * Test that regsafe() verifies id consistency for linked scalars
+ * during state pruning.
*
- * The false branch (explored first) links R3 to R2 via ADD_CONST.
- * The true branch (runtime path) links R3 to R4 (unrelated base_id).
+ * The false branch (explored first) links R3 to R2 via BPF_REG_LINK_FULL.
+ * The true branch (runtime path) links R3 to R4 (unrelated id).
* At the merge point, pruning must fail because the linkage topology
* differs.
*/
SEC("socket")
-__description("linked scalars: add_const base_id must be consistent for pruning")
+__description("linked scalars: add_const id must be consistent for pruning")
__failure __msg("invalid variable-offset")
__flag(BPF_F_TEST_STATE_FREQ)
-__naked void add_const_base_id_pruning(void)
+__naked void add_const_id_pruning(void)
{
asm volatile (" \
r1 = 0; \
@@ -675,7 +675,7 @@ __naked void add_const_base_id_pruning(void)
r2 = r0; \
r2 &= 0xff; /* R2 = scalar(id=A) [0,255] */ \
r3 = r2; /* R3 linked to R2 (id=A) */ \
- r3 += 10; /* R3 id=A|ADD_CONST, delta=10 */\
+ r3 += 10; /* BPF_REG_LINK_FULL delta */\
r6 = 0; \
goto l_merge_%=; \
\
@@ -687,12 +687,12 @@ l_true_%=: \
r4 = r0; \
r4 &= 0xff; /* R4 = scalar [0,255], id=0 */ \
r3 = r4; /* R3 linked to R4 (new id=C) */\
- r3 += 10; /* R3 id=C|ADD_CONST, delta=10 */\
+ r3 += 10; /* BPF_REG_LINK_FULL delta */\
r6 = 0; \
\
l_merge_%=: \
/* At merge, old R3 linked to R2, cur R3 linked to R4. */\
- /* Pruning must fail: base_ids A vs C inconsistent. */ \
+ /* Pruning must fail: ids A vs C inconsistent. */ \
if r2 >= 6 goto l_exit_%=; \
/* sync_linked_regs: R2<6 => R3<16 in old state. */ \
/* Without fix: R3 in [10,15] from incorrect pruning. */\
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (2 preceding siblings ...)
2026-10-20 16:18 ` [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits Vineet Gupta
@ 2026-10-20 16:18 ` Vineet Gupta
2026-10-20 16:39 ` sashiko-bot
2026-10-20 17:09 ` bot+bpf-ci
2026-10-20 16:19 ` [PATCH bpf-next v3 05/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
` (7 subsequent siblings)
11 siblings, 2 replies; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16:18 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
Linked-scalar equality is full-64-bit only, so a 32-bit mov from a source
with unknown high bits drops the relationship:
r6 = ... /* full 64-bit unknown */
w7 = w6 /* 32-bit zero-extending mov */
if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */
if w7 == 0 goto ... /* not deduced today */
Record it with the kind the previous patch already provides.
BPF_REG_LINK_ZEXT, which is what BPF_ADD_CONST32 became, says exactly
what the mov did:
dst == (u32)(src + 0)
However this changes the pre-existing semantics slightly:
today reg == base + delta, base known to fit u32
here reg == (u32)(base + delta), for any base width
Every link that forms today is over a narrow base, where the two
readings coincide, so nothing reachable now behaves differently; what is
new is that a wide base forms a link where it was previously refused
outright.
This is done by dropping the guard:
if (alu32 && (dst_umax > U32_MAX))
goto clear_id;
What the wide base costs is invertibility of the high half: dst pins
src's low 32 bits and says nothing about the rest. So sync_linked_regs()
drives such a link forwards only.
That also changes how a member is updated. Where the old code replaced
it with the base plus the delta difference, it now intersects the two: a
one-directional link leaves the member free to know more about itself
than the base does, and overwriting would discard that.
Intersecting can come out empty, when the two sides contradict -- the
link pins only the low 32 bits, so the verifier can walk a branch where
they disagree about the rest. Empty is the correct answer, and a bad
shape to leave behind: reg_bounds_sync() declines to touch an empty
range and the next reg_bounds_sanity_check() reports a verifier bug that
is not one. Keep the pre-intersect state instead. Without that,
w7 = w6; /* r7 == (u32)r6 */
if w7 != 5 goto out; /* r7 == 5 */
if r6 != 7 goto out; /* explored: r6 is wide and unknown */
r9 = 0;
r7 %= r9; /* validates r7 without recomputing it */
prints a REG INVARIANTS VIOLATION and a WARNING from an ordinary socket
filter. zext_contradiction_keeps_range_sane covers it, and discriminates
only here: the later reverse-direction patch makes "if r6 != 7"
statically false, so the branch is never walked at the tip.
The patch also allows delta composition, once. "w3 = w0; w3 -= 1" is
ordinary codegen, and until now the subtract threw the link away: the
mov gives every zero-extending link a kind, and the test that refuses a
second delta could not tell a link that has one from a link that merely
has a kind. Let the zero-extending link, and only it, compose a single
32-bit delta onto a delta of zero. The updated sub32_partial_overflow
dump is this case, its register now rendering as id=N-1.
Composing any further is refused deliberately. Deltas are compared for
equality, so a link that keeps accumulating them turns every value a
loop reaches into a state of its own: on arena_strsearch allowing a
second delta costs 1176 -> 1751 insns and 102 -> 133 states, and
allowing it onto a zero delta that an add produced rather than the mov
still costs 1176 -> 1196. Neither buys a verdict.
Forming a link re-bases a wide source, since
assign_scalar_id_before_mov() drops whatever link it carried; that costs
precision only.
verifier_reg_equal's subreg_equality_2 becomes __success. It is the same
link with a 64-bit compare on the member: "w2 < 9" bounds r3 over all 64
bits, not just its low half, because the zero-extending mov leaves
nothing above them.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 3/13.
- the zero-extending link is now ADD_CONST32 with delta 0, spelled
BPF_REG_LINK_ZEXT, rather than a kind of its own (Alexei). That
generalises the kind to "(u32)(base + delta), for any base width",
dropping the dst_umax > U32_MAX guard and making the link
one-directional. It is the one pre-existing semantic the series
changes; see the cover.
- a BPF_REG_LINK_ZEXT link may take one delta, so "w3 = w0; w3 -= 1"
keeps it where v2 dropped it. Composing further costs arena_strsearch
1176 -> 1751 insns for no verdict, so it is restricted to one.
- a second 32-bit mov now drops the link, where v2's separate kind kept
it.
- NEW IN THIS REVISION: the intersect step no longer leaves an empty
range behind when the two sides contradict. Without the guard that
printed a WARNING from an ordinary socket filter; patch 8 happened to
mask it, so the window was patches 4-7.
include/linux/bpf_verifier.h | 3 +-
kernel/bpf/verifier.c | 112 ++++++++++++++----
.../selftests/bpf/progs/verifier_bounds.c | 2 +-
.../selftests/bpf/progs/verifier_reg_equal.c | 14 +--
4 files changed, 101 insertions(+), 30 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index bb369b320334..081facac7b86 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -56,13 +56,14 @@ enum bpf_iter_state {
* how much, and is meaningful for every kind:
*
* BPF_REG_LINK_FULL: reg == base + delta
- * BPF_REG_LINK_ZEXT: reg == (u32)(base + delta), base known to fit u32
+ * BPF_REG_LINK_ZEXT: reg == (u32)(base + delta), for ANY base width
* BPF_REG_LINK_SEXT: reg == (s32)(base + delta)
*
* r1 = r2; r1 and r3 are linked to r2: id == N
* r3 = r2;
* r1 += 10; r1 gets BPF_REG_LINK_FULL, delta 10
* w3 += 10; w3 gets BPF_REG_LINK_ZEXT, delta 10
+ * w7 = w6; r7 gets BPF_REG_LINK_ZEXT, delta 0 (r6 may be wide)
*/
enum bpf_reg_link_kind {
BPF_REG_LINK_NONE = 0,
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 609342940d1a..ce7016446936 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -17287,13 +17287,6 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
verbose(env, "verifier internal error: no src_reg\n");
return -EFAULT;
}
- /*
- * For alu32 linked register tracking, we need to check dst_reg's
- * umax_value before the ALU operation. After adjust_scalar_min_max_vals(),
- * alu32 ops will have zero-extended the result, making umax_value <= U32_MAX.
- */
- u64 dst_umax = reg_umax(dst_reg);
-
err = adjust_scalar_min_max_vals(env, insn, dst_reg, *src_reg);
if (err)
return err;
@@ -17316,9 +17309,6 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
if (!alu32 && ((s64)val < S32_MIN || (s64)val > S32_MAX))
goto clear_id;
- if (alu32 && (dst_umax > U32_MAX))
- goto clear_id;
-
off = (s32)val;
if (BPF_OP(insn->code) == BPF_SUB) {
@@ -17330,11 +17320,28 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
if (dst_reg->link_kind) {
/*
- * If the register already went through rX += val
- * we cannot accumulate another val into rx->off.
+ * Only the zero-extending link the mov above records,
+ * BPF_REG_LINK_ZEXT with delta 0, can take a delta:
+ * (u32)((u32)(base + 0) + off) is (u32)(base + off).
+ * The add has to be 32-bit as well, since a 64-bit one
+ * parts company with the link once the low half wraps.
+ *
+ * Everything else still drops the link. A zero delta
+ * reached by an add rather than by the mov, say "r1 +=
+ * r3" with r3 known to be 0, has already spent its
+ * delta; composing onto it keeps a link alive across a
+ * loop's increments, and since the delta is compared
+ * for equality, every value the loop reaches becomes a
+ * state of its own and stops pruning.
*/
+ if (dst_reg->link_kind != BPF_REG_LINK_ZEXT || !alu32 ||
+ dst_reg->delta) {
+ /* also the target of the two gotos above */
clear_id:
- bpf_clear_scalar_id(dst_reg);
+ bpf_clear_scalar_id(dst_reg);
+ } else {
+ dst_reg->delta = off;
+ }
} else {
if (alu32)
dst_reg->link_kind = BPF_REG_LINK_ZEXT;
@@ -17559,16 +17566,43 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
} else if (src_reg->type == SCALAR_VALUE) {
if (insn->off == 0) {
bool is_src_reg_u32 = get_reg_width(src_reg) <= 32;
+ /*
+ * A wide src shares only its low 32 bits. A
+ * full link would let dst's [0, U32_MAX]
+ * propagate onto src's unknown high bits, so
+ * record a low-32-only link instead. A
+ * self-mov has nothing to link.
+ */
+ bool subreg_link = !is_src_reg_u32 &&
+ src_reg != dst_reg;
- if (is_src_reg_u32)
+ if (is_src_reg_u32 || 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)
+ if (subreg_link && src_reg->id) {
+ /*
+ * Keep src's delta. It is
+ * always zero here, since
+ * assign_scalar_id_before_mov()
+ * above has just dropped any
+ * kind src carried; the
+ * inheritance starts to matter
+ * once BPF_REG_LINK_SEXT is
+ * spared there, because dst is
+ * (u32)(base + delta) whatever
+ * kind src had --
+ * (u32)((s32)(base + d)) ==
+ * (u32)(base + d).
+ */
+ dst_reg->link_kind = BPF_REG_LINK_ZEXT;
+ } else if (!is_src_reg_u32) {
+ /*
+ * dst min/max could otherwise be
+ * propagated back into a src that
+ * is not in u32 range.
+ */
bpf_clear_scalar_id(dst_reg);
+ }
} else {
/* case: W1 = (s8, s16)W2 */
bool no_sext = reg_umax(src_reg) < (1ULL << (insn->off - 1));
@@ -18450,6 +18484,15 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
continue;
if (reg->id != known_reg->id)
continue;
+ /*
+ * A zero-extending link, spelled BPF_REG_LINK_ZEXT: the
+ * relation reg == (u32)(base + delta) does not invert once the
+ * base is wider than 32 bits, so the reverse direction is
+ * skipped.
+ */
+ if (known_reg->link_kind == BPF_REG_LINK_ZEXT &&
+ get_reg_width(reg) > 32)
+ continue;
/*
* Skip mixed 32/64-bit links: the delta relationship doesn't
* hold across different ALU widths.
@@ -18457,13 +18500,19 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
if (reg->link_kind && known_reg->link_kind &&
reg->link_kind != known_reg->link_kind)
continue;
- if ((!reg->link_kind && !known_reg->link_kind) ||
- reg->delta == known_reg->delta) {
+ /*
+ * Only an unlinked pair is a plain copy. Anything carrying a
+ * kind goes through the differencing arm below, which adds the
+ * delta difference (zero when the deltas match) and then
+ * applies the BPF_REG_LINK_ZEXT zero-extension.
+ */
+ if (!reg->link_kind && !known_reg->link_kind) {
*reg = *known_reg;
} else {
enum bpf_reg_link_kind saved_link_kind = reg->link_kind;
s32 saved_off = reg->delta;
u32 saved_id = reg->id;
+ struct bpf_reg_state prev = *reg;
fake_reg.type = SCALAR_VALUE;
__mark_reg_known(&fake_reg, (s64)reg->delta - (s64)known_reg->delta);
@@ -18485,6 +18534,27 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
if (reg->link_kind == BPF_REG_LINK_ZEXT ||
known_reg->link_kind == BPF_REG_LINK_ZEXT)
zext_32_to_64(reg);
+ /*
+ * Intersect rather than overwrite. A BPF_REG_LINK_ZEXT
+ * link over a wide base does not propagate back, so the
+ * base can be wider than what @reg has already proved
+ * about itself; replacing it would lose that.
+ */
+ cnum64_intersect_with(®->r64, prev.r64);
+ cnum32_intersect_with(®->r32, prev.r32);
+ reg->var_off = tnum_intersect(reg->var_off, prev.var_off);
+ /*
+ * An empty intersection means the two sides contradict,
+ * so this path is unreachable. Say nothing rather than
+ * say it with an empty range: reg_bounds_sync() below
+ * refuses to touch one, and the first later
+ * reg_bounds_sanity_check() would report it as a
+ * verifier bug, which it is not. Keeping the wider
+ * pre-intersect state only costs precision on a path
+ * that cannot be taken.
+ */
+ if (range_bounds_violation(reg))
+ *reg = prev;
reg_bounds_sync(reg);
}
if (e->is_reg)
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index df8d5309657e..ad346dec1150 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -1516,7 +1516,7 @@ __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))")
+__msg("3: (1c) w3 -= w2 {{.*}} R3=scalar(id={{[0-9]+}}-1,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_reg_equal.c b/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
index dc1d8c30fb0e..34214ec92670 100644
--- a/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
+++ b/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
@@ -31,23 +31,23 @@ l1_%=: exit; \
}
SEC("socket")
-__description("check w reg not equal if r reg upper32 bits not 0")
-__failure __msg("R1 !read_ok")
+__description("check w reg equal if r reg upper32 bits 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, so r3 does \
+ * not equal r2. It does share r2's low 32 bits \
+ * though, so w2 < 9 still bounds r3: the \
+ * zero-extending mov leaves nothing above them.\
*/ \
w3 = w2; \
if w2 < 9 goto l0_%=; \
exit; \
l0_%=: if r3 < 9 goto l1_%=; \
- /* r1 read is illegal at this point */ \
+ /* unreachable, so the r1 read is never made */ \
r0 -= r1; \
l1_%=: exit; \
" :
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 05/12] selftests/bpf: Cover the low-32 link for zero-extending movs
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (3 preceding siblings ...)
2026-10-20 16:18 ` [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs Vineet Gupta
@ 2026-10-20 16:19 ` Vineet Gupta
2026-10-20 16:53 ` bot+bpf-ci
2026-10-20 16:19 ` [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs Vineet Gupta
` (6 subsequent siblings)
11 siblings, 1 reply; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16: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
Twelve programs, one per decision the previous patch makes:
- zext_mov_narrow_src: narrowing the source reaches the destination
- zext_sync_makes_member_const: and over all 64 bits, since the member
is the zero-extension
- zext_narrow_dst_keeps_base: the reverse must not happen
- zext_u32_src_is_full_link: a provably-u32 source still propagates
- zext_self_mov_no_link: a self-mov mints no id
- zext_chain_drops_link: a second 32-bit mov drops the link
- zext_no_sync_between_mixed_kinds: differing kinds do not reach each
other, in either direction
- zext_no_sync_from_subreg_base: nor does a member reach a base whose
high half it knows nothing about
- zext_sync_between_two_subregs: two low-32 links on one base do
- zext_unlinked_path_stays_reachable: one unlinked path keeps the
guarded div reachable
- zext_mov_breaks_linked_src: forming the link drops the source's own
- zext_sync_keeps_narrower_member: narrowing the base does not widen a
member that already proved itself tighter
- zext_contradiction_keeps_range_sane: a contradiction leaves no empty
range behind, under BPF_F_TEST_REG_INVARIANTS so the violation is a
load failure rather than something only dmesg sees
Written in asm so the bytecode is the same whichever compiler built the
suite.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 4/13.
- renames and commentary follow patch 4; zext_chain_keeps_link becomes
zext_chain_drops_link, and two dump expectations change because the
link now renders as "%+d" rather than v2's ".lo32".
- new: zext_sync_makes_member_const, for the 64-bit constant a helper
argument depends on, which no other test asserted
- new: zext_sync_keeps_narrower_member
- new: zext_contradiction_keeps_range_sane, guarding patch 4's
empty-range fix. It discriminates at patches 4-7 and not at the tip,
where patch 8 prunes the branch; patch 4's message says so.
.../bpf/progs/verifier_linked_scalars.c | 348 ++++++++++++++++++
1 file changed, 348 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
index 5a120fc7c1e7..815160e56942 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -710,4 +710,352 @@ l_exit_%=: \
: __clobber_all);
}
+/*
+ * A 32-bit mov from a wide source shares only the low 32 bits. Narrowing the
+ * source must reach the destination through that link.
+ */
+SEC("socket")
+__success
+__naked void zext_mov_narrow_src(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ w7 = w6; /* forms the link */ \
+ if w6 != 0 goto 1f; /* narrows r6, propagates to r7 */ \
+ if w7 == 0 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Pinning the base's low 32 bits makes the member a known constant over all
+ * 64, not merely over its low half: the member is the zero-extension, so its
+ * high half is zero by construction. Checked with a 64-bit compare, which
+ * zext_mov_narrow_src above does not do. Code that needs a provable constant
+ * -- a helper argument such as bpf_rdonly_cast()'s btf_id, say -- depends on
+ * this and not on the 32-bit form.
+ */
+SEC("socket")
+__success
+__naked void zext_sync_makes_member_const(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ w7 = w6; /* forms the link */ \
+ if w6 != 0 goto 1f; /* narrows r6's low 32 to 0 */ \
+ if r7 == 0 goto 1f; /* r7 is 0 over all 64 bits */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A contradiction between the two sides must not leave an empty range behind.
+ * The branch really is dead -- (u32)7 is not 5 -- but an empty range is a
+ * shape nothing downstream handles.
+ *
+ * The mod by a known-zero divisor validates r7 without recomputing it, so an
+ * empty range would survive into the check; under BPF_F_TEST_REG_INVARIANTS
+ * that is a load failure, which is what __success asserts. A later patch
+ * prunes this branch, so the test pins this patch standing alone.
+ */
+SEC("socket")
+__success
+__flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void zext_contradiction_keeps_range_sane(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ w7 = w6; /* forms the link */ \
+ if w7 != 5 goto 1f; /* r7 == 5 */ \
+ if r6 != 7 goto 1f; /* r6 is wide, so this is explored */ \
+ r9 = 0; \
+ r7 %%= r9; /* validates r7 without touching it */ \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * The reverse does not hold: narrowing the low-32 link says nothing about the
+ * base's high bits, so r6 must stay unknown and the div stays reachable.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void zext_narrow_dst_keeps_base(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ w7 = w6; /* forms the link */ \
+ if r7 != 0 goto 1f; /* narrows r7, must not propagate to r6 */ \
+ if r6 == 0 goto 1f; /* taken only if r6 wrongly narrowed */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A provably-u32 source takes the full-equality path, not the low-32 one:
+ * narrowing the destination must reach the source.
+ */
+SEC("socket")
+__success
+__naked void zext_u32_src_is_full_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ w6 = w0; /* r6 provably u32 */ \
+ w7 = w6; /* full link, not low-32 */ \
+ if r7 > 10 goto 1f; /* narrows r7, propagates to r6 */ \
+ if r6 > 10 goto 2f; \
+ goto 1f; \
+2: \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A self-mov has nothing to link, so it must not mint an id for r6.
+ */
+SEC("socket")
+__success __log_level(2)
+/* an id would print as R6=scalar(id=N+0,smin=... */
+__msg("(bc) w6 = w6 {{.*}} R6=scalar(smin=0,")
+__naked void zext_self_mov_no_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 ^= 0; /* drop the id */ \
+ w6 = w6; /* forms no link */ \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A second 32-bit mov drops the link: assign_scalar_id_before_mov() clears
+ * any link kind on the source, and the zero-extending link is one, so
+ * narrowing the base no longer reaches the end of the chain. Same rule as
+ * scalars_double_add above -- a delta of zero is not special.
+ */
+SEC("socket")
+__failure
+__msg("div by zero")
+__naked void zext_chain_drops_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ w7 = w6; /* forms the link */ \
+ w8 = w7; /* the 2nd mov breaks the link */ \
+ if w6 != 0 goto 1f; /* narrows r6, does not reach r8 */ \
+ if w8 == 0 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Two members of one id set carrying different link kinds do not propagate
+ * to each other: r7 is (u32)base and r8 is base + 3, and the deltas were
+ * added at different ALU widths, so narrowing r8 says nothing about r7.
+ * sync_linked_regs() declines the pair on the kinds before the deltas are
+ * ever consulted. Note neither register is the base -- that is r6.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void zext_no_sync_between_mixed_kinds(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ w7 = w6; /* forms the link */ \
+ r8 = r6; \
+ r8 += 3; /* r8 is BPF_REG_LINK_FULL, r7 is BPF_REG_LINK_ZEXT */ \
+ if r8 != 3 goto 1f; /* must not propagate to r7 */ \
+ if w7 == 0 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * ... and here the low-32 link is the branch register, so the register
+ * carrying the delta must not be narrowed either.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void zext_no_sync_from_subreg_base(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ w7 = w6; /* forms the link */ \
+ r8 = r6; \
+ r8 += 3; /* delta on r8 */ \
+ if w7 != 0 goto 1f; /* must not propagate to r8 */ \
+ if r8 == 3 goto 1f; /* taken only if r8 wrongly narrowed */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Two low-32 links on the same base do propagate to each other: both are the
+ * zero-extension of the same low 32 bits.
+ */
+SEC("socket")
+__success
+__naked void zext_sync_between_two_subregs(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ w7 = w6; /* two links on one base */ \
+ w8 = w6; \
+ if w7 != 0 goto 1f; /* narrows r7, propagates to r8 */ \
+ if w8 == 0 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A narrowing of the base must not widen a member that has already proved
+ * itself tighter. The low-32 link does not propagate back to the base, so the
+ * base can be the wider of the two; rebuilding the member from it has to
+ * refine what the member knows rather than replace it.
+ */
+SEC("socket")
+__success
+__naked void zext_sync_keeps_narrower_member(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ w7 = w6; /* forms the link */ \
+ if w7 > 7 goto 1f; /* r7 low 32 bits in [0, 7] */ \
+ if r6 > 100 goto 1f; /* narrows the base, syncs to r7 */ \
+ if r7 <= 7 goto 1f; /* still provable if r7 kept [0, 7] */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Only one of the two paths links r7 to r8, so narrowing w8 reaches r7 on one
+ * and not the other, and the div stays reachable. This pins the outcome, not
+ * any one check: the two states differ in several ways, so no single
+ * regsafe() test is load-bearing here.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void zext_unlinked_path_stays_reachable(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 &= 1; \
+ if r6 >= 1 goto 2f; \
+ /* explored first: r7 is a low-32 link of r8 */ \
+ call %[bpf_get_prandom_u32]; \
+ r8 = r0; \
+ w7 = w8; /* forms the link */ \
+ goto 1f; \
+2: \
+ /* runtime path: r7 unrelated to r8 */ \
+ call %[bpf_get_prandom_u32]; \
+ r8 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ w7 = w0; /* no link here */ \
+1: \
+ if w8 != 0 goto 3f; /* propagates to r7 only if linked */ \
+ if w7 == 0 goto 3f; \
+ r0 /= 0; \
+3: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Forming the link calls assign_scalar_id_before_mov(), which drops whatever
+ * link the source already carries. That is what the narrow-source path has
+ * always done, so a wide source behaves the same: r5 stops tracking r6.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void zext_mov_breaks_linked_src(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r5 = r6; /* r5, r6 linked */ \
+ r5 += 3; /* r5 = base + 3 */ \
+ w7 = w5; /* breaks r5's delta link */ \
+ if r6 > 9 goto 1f; /* r6 in [0, 9] */ \
+ if r5 < 13 goto 1f; /* taken only if r5 still linked */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
char _license[] SEC("license") = "GPL";
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (4 preceding siblings ...)
2026-10-20 16:19 ` [PATCH bpf-next v3 05/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
@ 2026-10-20 16:19 ` Vineet Gupta
2026-10-20 16:57 ` sashiko-bot
2026-10-20 16:19 ` [PATCH bpf-next v3 07/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
` (5 subsequent siblings)
11 siblings, 1 reply; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16: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
A 32-bit sign extension shares the source's low 32 bits too, filling the
high half from bit 31:
r6 = ... /* full 64-bit unknown */
r7 = (s32)r6 /* 32-bit sign-extending mov */
if w6 == -1 goto ... /* taken: r6's low 32 bits are all ones */
... /* r7 is -1, not deduced today */
No constant k makes dst == (u32)(src + k) a sign extension, so this
needs a third kind, BPF_REG_LINK_SEXT, driven by sext_32_to_64() where
the zero-extending arm uses zext_32_to_64(). The enum already had room,
so bpf_reg_state stays 80 bytes.
Both work from the base's 32-bit range, which is what a 32-bit compare
narrows; coerce_reg_to_size_sx() cannot serve, as it reads smin/smax,
which straddle after such a compare. tnum_sext() is the counterpart to
tnum_cast(), keeping the known low bits where a tnum_range() over the new
bounds would not.
sext_32_to_64() resets the register's base/step line; the comment there
gives the arithmetic. Note it resets unconditionally, where
coerce_reg_to_size_sx() and coerce_subreg_to_size_sx() return early when
the extension is a provable no-op and keep the line. That costs a little
precision in the same case here, which is not worth an extra branch on a
path that has just rebuilt the value from the base.
Unlike the zero-extending arm, the source's delta comes along. Both
base + d and (u32)(base + d) have low half (base + d), so dst is
(s32)(base + d) whichever the source was:
w7 = w6; /* BPF_REG_LINK_ZEXT, delta 0 */
w7 += 5; /* BPF_REG_LINK_ZEXT, delta 5 */
r8 = (s32)r7; /* BPF_REG_LINK_SEXT, delta 5 */
keeps r8 tied to r6. sext_mov_inherits_delta pins it; without the
inheritance the program is rejected. A self-mov can form a link here too,
which is how a sign-extended int return lands.
sync_linked_regs() needs no separate sext path: the differencing arm
already copies the base and adds the delta difference, and which extension
follows is just the member's kind. Where the base does fit 32 bits the
reverse direction runs for both narrow kinds with the *zero* extension --
the base is then below 2^32 and equal to the member's low half, whichever
way the member filled its own high half.
One guard gains a new meaning. BPF_REG_LINK_ZEXT against
BPF_REG_LINK_SEXT is a sound deduction that is now declined on purpose:
bpf-gcc compiles "i += 1" for an int loop counter into exactly that
pair, and deducing the sign-extended half makes the counter a fresh
constant every iteration, so iters.c:iter_obfuscate_counter runs to the
1M instruction limit. sext_no_sync_from_zext_sibling pins it.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 7/13.
- SUBREG_SEXT becomes BPF_REG_LINK_SEXT, a value of the same two-bit
field, so the sign-extending link costs no space of its own, and v2's
separate reconstruction in sync_linked_regs() is gone.
- new capability: a sign-extending mov inherits the source's delta.
Nothing in the corpus builds the shape, so sext_mov_inherits_delta
covers it directly.
- assign_scalar_id_before_mov() now keeps a BPF_REG_LINK_SEXT source's
id. Without it bpf_iter_tasks/dump_task_sleepable hits the 8192-jump
limit under bpf-gcc.
- the mixed-kind guard also covers BPF_REG_LINK_ZEXT against
BPF_REG_LINK_SEXT. That deduction is sound and declined on purpose:
making it turns an int loop counter into a fresh constant each
iteration and iter_obfuscate_counter stops converging.
include/linux/bpf_verifier.h | 3 +-
include/linux/tnum.h | 7 +++
kernel/bpf/log.c | 2 +
kernel/bpf/tnum.c | 15 ++++++
kernel/bpf/verifier.c | 89 +++++++++++++++++++++++++++++++-----
5 files changed, 103 insertions(+), 13 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 081facac7b86..16e3d5a951b5 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -57,13 +57,14 @@ enum bpf_iter_state {
*
* BPF_REG_LINK_FULL: reg == base + delta
* BPF_REG_LINK_ZEXT: reg == (u32)(base + delta), for ANY base width
- * BPF_REG_LINK_SEXT: reg == (s32)(base + delta)
+ * BPF_REG_LINK_SEXT: reg == (s32)(base + delta), for ANY base width
*
* r1 = r2; r1 and r3 are linked to r2: id == N
* r3 = r2;
* r1 += 10; r1 gets BPF_REG_LINK_FULL, delta 10
* w3 += 10; w3 gets BPF_REG_LINK_ZEXT, delta 10
* w7 = w6; r7 gets BPF_REG_LINK_ZEXT, delta 0 (r6 may be wide)
+ * r8 = (s32)r7; r8 gets BPF_REG_LINK_SEXT, delta 0
*/
enum bpf_reg_link_kind {
BPF_REG_LINK_NONE = 0,
diff --git a/include/linux/tnum.h b/include/linux/tnum.h
index 16682248f963..0ad7ea0d4898 100644
--- a/include/linux/tnum.h
+++ b/include/linux/tnum.h
@@ -63,6 +63,13 @@ struct tnum tnum_union(struct tnum t1, struct tnum t2);
/* Return @a with all but the lowest @size bytes cleared */
struct tnum tnum_cast(struct tnum a, u8 size);
+/*
+ * Return the lowest @size bytes of @a sign-extended to 64 bits. @size must
+ * be 1, 2 or 4: tnum_cast() above cannot express a 64-bit field, and the
+ * shift here would be by 64 for @size 0.
+ */
+struct tnum tnum_sext(struct tnum a, u8 size);
+
/* Swap the bytes of a tnum */
struct tnum tnum_bswap16(struct tnum a);
struct tnum tnum_bswap32(struct tnum a);
diff --git a/kernel/bpf/log.c b/kernel/bpf/log.c
index a6f205653a9e..2286576ccfe6 100644
--- a/kernel/bpf/log.c
+++ b/kernel/bpf/log.c
@@ -654,6 +654,8 @@ static void print_reg_state(struct bpf_verifier_env *env,
verbose_a("id=%d", reg->id);
if (reg->link_kind)
verbose(env, "%+d", reg->delta);
+ if (reg->link_kind == BPF_REG_LINK_SEXT)
+ verbose(env, ".sx");
if (reg->parent_id)
verbose_a("parent_id=%d", reg->parent_id);
if (type_is_non_owning_ref(reg->type))
diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
index 1f620facd1b7..55d10d362eed 100644
--- a/kernel/bpf/tnum.c
+++ b/kernel/bpf/tnum.c
@@ -200,6 +200,21 @@ struct tnum tnum_cast(struct tnum a, u8 size)
return a;
}
+struct tnum tnum_sext(struct tnum a, u8 size)
+{
+ u8 shift = 64 - size * 8;
+
+ /*
+ * Shifting the field up to the top and back down arithmetically
+ * replicates its sign bit through the high half. Applying that to the
+ * mask as well carries over whether the sign was known: an unknown
+ * sign bit leaves every high bit unknown.
+ */
+ a = tnum_cast(a, size);
+ return TNUM((s64)(a.value << shift) >> shift,
+ (s64)(a.mask << shift) >> shift);
+}
+
bool tnum_is_aligned(struct tnum a, u64 size)
{
if (!size)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index ce7016446936..dffcaa2e1392 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3763,7 +3763,7 @@ static void assign_scalar_id_before_mov(struct bpf_verifier_env *env,
* rY->id has special linked register already.
* Cleared it, since multiple rX += const are not supported.
*/
- if (src_reg->link_kind)
+ if (src_reg->link_kind && src_reg->link_kind != BPF_REG_LINK_SEXT)
bpf_clear_scalar_id(src_reg);
/*
* Ensure that src_reg has a valid ID that will be copied to
@@ -6057,6 +6057,25 @@ static void zext_32_to_64(struct bpf_reg_state *reg)
reg_set_urange64(reg, reg_u32_min(reg), reg_u32_max(reg));
}
+/*
+ * The sign-extending counterpart. Signed bounds carry over directly because
+ * sign extension is monotonic over the signed 32-bit range.
+ */
+static void sext_32_to_64(struct bpf_reg_state *reg)
+{
+ /*
+ * See comment at reg_step_check_unsigned(). Sign extension subtracts
+ * 2^32 from every value with bit 31 set, which preserves a residue
+ * mod step only when step divides 2^32, so the line cannot be kept.
+ * The zero-extending twin calls reg_step_check_unsigned(reg, 32) for
+ * the same reason; the unsigned form does not apply here because the
+ * result is not the low 32 bits but the low 32 bits moved.
+ */
+ reg_step_reset(reg);
+ reg->var_off = tnum_sext(reg->var_off, 4);
+ reg_set_srange64(reg, reg_s32_min(reg), reg_s32_max(reg));
+}
+
/* truncate register to smaller size (in bytes)
* must be called with size < BPF_REG_SIZE
*/
@@ -17544,12 +17563,29 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
return -EACCES;
} else if (src_reg->type == SCALAR_VALUE) {
bool no_sext;
+ /*
+ * A 32-bit sign extension keeps the low 32
+ * bits, so dst shares them with whatever src
+ * shares them with. Both base + d and
+ * (u32)(base + d) have low half (base + d), so
+ * dst is (s32)(base + d) either way: inherit
+ * src's id and delta and record
+ * BPF_REG_LINK_SEXT.
+ */
+ bool subreg_link =
+ (insn->off >> 3) == 4 &&
+ (src_reg != dst_reg || src_reg->id);
no_sext = reg_umax(src_reg) < (1ULL << (insn->off - 1));
if (no_sext)
assign_scalar_id_before_mov(env, src_reg);
+ else if (subreg_link && !src_reg->id &&
+ !tnum_is_const(src_reg->var_off))
+ src_reg->id = ++env->id_gen;
*dst_reg = *src_reg;
- if (!no_sext)
+ if (!no_sext && subreg_link && src_reg->id)
+ dst_reg->link_kind = BPF_REG_LINK_SEXT;
+ else if (!no_sext)
bpf_clear_scalar_id(dst_reg);
coerce_reg_to_size_sx(dst_reg, insn->off >> 3);
} else {
@@ -18485,17 +18521,29 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
if (reg->id != known_reg->id)
continue;
/*
- * A zero-extending link, spelled BPF_REG_LINK_ZEXT: the
- * relation reg == (u32)(base + delta) does not invert once the
- * base is wider than 32 bits, so the reverse direction is
- * skipped.
+ * The reverse direction does not work for a narrow known_reg:
+ * it knows only its low 32 bits, which say nothing about a
+ * wider reg's high half. Neither (u32)(base + delta) nor
+ * (s32)(base + delta) inverts once the base is wider than 32
+ * bits.
*/
- if (known_reg->link_kind == BPF_REG_LINK_ZEXT &&
+ if ((known_reg->link_kind == BPF_REG_LINK_ZEXT ||
+ known_reg->link_kind == BPF_REG_LINK_SEXT) &&
+ reg->link_kind != BPF_REG_LINK_ZEXT &&
+ reg->link_kind != BPF_REG_LINK_SEXT &&
get_reg_width(reg) > 32)
continue;
/*
- * Skip mixed 32/64-bit links: the delta relationship doesn't
- * hold across different ALU widths.
+ * Skip a pair of differing kinds. Where BPF_REG_LINK_FULL meets
+ * a 32-bit kind the delta relationship genuinely does not hold:
+ * the deltas were added at different ALU widths.
+ * BPF_REG_LINK_ZEXT against BPF_REG_LINK_SEXT is not that case
+ * -- both are base + delta in the low 32 bits, so narrowing one
+ * really does narrow the other -- but that deduction is
+ * declined on purpose. It makes an int loop counter a fresh
+ * constant on every iteration, so no two iterations prune
+ * against each other and the program runs to the instruction
+ * limit. See sext_no_sync_from_zext_sibling.
*/
if (reg->link_kind && known_reg->link_kind &&
reg->link_kind != known_reg->link_kind)
@@ -18504,7 +18552,7 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
* Only an unlinked pair is a plain copy. Anything carrying a
* kind goes through the differencing arm below, which adds the
* delta difference (zero when the deltas match) and then
- * applies the BPF_REG_LINK_ZEXT zero-extension.
+ * re-applies whichever extension the kinds call for.
*/
if (!reg->link_kind && !known_reg->link_kind) {
*reg = *known_reg;
@@ -18531,9 +18579,26 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
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->link_kind == BPF_REG_LINK_ZEXT ||
- known_reg->link_kind == BPF_REG_LINK_ZEXT)
+ if (reg->link_kind == BPF_REG_LINK_SEXT) {
+ sext_32_to_64(reg);
+ } else if (reg->link_kind == BPF_REG_LINK_ZEXT ||
+ known_reg->link_kind == BPF_REG_LINK_ZEXT ||
+ known_reg->link_kind == BPF_REG_LINK_SEXT) {
+ /*
+ * Either @reg is itself the zero extension, or
+ * @reg has no 32-bit kind and @known_reg does
+ * -- the reverse direction, where the guard
+ * above has already proved @reg fits 32 bits.
+ * Then @reg is @known_reg's low half with
+ * nothing above it, whichever way @known_reg
+ * filled its own high half, so the zero
+ * extension is the reconstruction for both
+ * kinds. BPF_REG_LINK_FULL is not here on
+ * purpose: it relates all 64 bits and must not
+ * be truncated.
+ */
zext_32_to_64(reg);
+ }
/*
* Intersect rather than overwrite. A BPF_REG_LINK_ZEXT
* link over a wide base does not propagate back, so the
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 07/12] selftests/bpf: Cover the low-32 link for sign-extending movs
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (5 preceding siblings ...)
2026-10-20 16:19 ` [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs Vineet Gupta
@ 2026-10-20 16:19 ` Vineet Gupta
2026-10-20 16:19 ` [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction Vineet Gupta
` (4 subsequent siblings)
11 siblings, 0 replies; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16: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
Fourteen programs, mirroring the zero-extending set:
- sext_mov_inherits_delta: a source carrying a delta hands it to the
sign extension; without that the program is rejected
- sext_delta_survives_zext_mov: and survives a further zero-extending mov
- sext_mov_unlinked_src: a call return has no id, so the mov mints one.
This is the shape the failures that motivated the series take
- sext_value_survives_spill_across_call: narrowed, then spilled across a
call, and the value has to come back off the stack
- sext_mov_wide_src: what arrives is sign-extended, not zero-extended
- sext_self_mov_keeps_link: r0 = (s32)r0 on a linked register stays in
its set -- how a sign-extended int return lands
- sext_self_mov_no_link: the same mov on an unlinked register mints no id
- sext_no_sync_when_base_has_delta: a delta on the base stops propagation
- sext_no_sync_from_subreg_base: no reverse propagation from a wide base
- sext_narrow_base_keeps_high_values: and when the base is not wide, the
reverse runs with the *zero* extension. Rebuilding it the other way
dropped every value with bit 31 set
- sext_drops_stale_step: the base/step line does not survive the
reconstruction
- sext_no_sync_from_zext_sibling: the ZEXT/SEXT pair deliberately does
not reach itself; iter_obfuscate_counter depends on this
- sext_kinds_reach_different_values: one low half reaches -1 through a
sign extension and 0xffffffff through a zero extension
- sext_sync_keeps_narrower_member: a tighter member is not widened
The __success ones guard a div by zero that is unreachable only if the
propagation happened; the __failure ones leave it reachable, so an unsound
deduction shows up as an unexpected success.
The sign-extending mov is cpuv4, so the block sits behind CAN_USE_MOVSX,
following CAN_USE_GOTOL so bpf-gcc gets the coverage too. verifier_movsx.c
open-coded the same condition and uses the macro now.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 8/13.
- new: sext_mov_inherits_delta and sext_delta_survives_zext_mov, for
the delta patch 6 adds
- new: sext_mov_unlinked_src and sext_value_survives_spill_across_call,
the two shapes the failures that motivated the series take
- new: sext_narrow_base_keeps_high_values, sext_drops_stale_step and
sext_sync_keeps_narrower_member, pinning what the reverse direction
must get right for a narrow base
- new: sext_no_sync_from_zext_sibling. The shape is bpf-gcc codegen
clang does not emit, so without it a regression here is invisible
to CI.
- the block moves behind CAN_USE_MOVSX so bpf-gcc gets the coverage.
tools/testing/selftests/bpf/progs/bpf_misc.h | 8 +
.../bpf/progs/verifier_linked_scalars.c | 409 ++++++++++++++++++
.../selftests/bpf/progs/verifier_movsx.c | 8 +-
3 files changed, 419 insertions(+), 6 deletions(-)
diff --git a/tools/testing/selftests/bpf/progs/bpf_misc.h b/tools/testing/selftests/bpf/progs/bpf_misc.h
index d7f706c3bc4a..c5ffb36dfd74 100644
--- a/tools/testing/selftests/bpf/progs/bpf_misc.h
+++ b/tools/testing/selftests/bpf/progs/bpf_misc.h
@@ -285,6 +285,14 @@
#define CAN_USE_BPF_ST
#endif
+#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))
+#define CAN_USE_MOVSX
+#endif
+
#if __clang_major__ >= 18 && defined(ENABLE_ATOMICS_TESTS) && \
(defined(__TARGET_ARCH_arm64) || \
defined(__TARGET_ARCH_x86) || \
diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
index 815160e56942..9a33cc60e8cb 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -213,6 +213,40 @@ l0_%=: \
: __clobber_all);
}
+#ifdef CAN_USE_MOVSX
+/*
+ * A sign-extending mov reads only the low 32 bits, so it shares them with
+ * whatever its source shares them with -- including a delta the source
+ * picked up. Here r8 is (s32)(r6 + 5): narrowing r6 to 0xfffffffb makes
+ * (u32)(r6 + 5) zero, so r8 is zero and the divide is unreachable.
+ */
+SEC("socket")
+__success
+__retval(0)
+__naked void sext_mov_inherits_delta(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 <<= 32; \
+ call %[bpf_get_prandom_u32]; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ w7 = w6; /* BPF_REG_LINK_ZEXT, delta 0 */ \
+ w7 += 5; /* BPF_REG_LINK_ZEXT, delta 5 */ \
+ r8 = (s32)r7; /* BPF_REG_LINK_SEXT, delta 5 */ \
+ r1 = 0xfffffffb ll; \
+ if r6 != r1 goto l0_%=; /* (u32)(r6 + 5) == 0 */ \
+ if r8 == 0 goto l0_%=; \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+#endif /* CAN_USE_MOVSX */
+
/*
* Test that sync_linked_regs() correctly handles large offset differences.
* r1.off = S32_MIN, r2.off = 1, delta = S32_MIN - 1 requires 64-bit math.
@@ -1058,4 +1092,379 @@ __naked void zext_mov_breaks_linked_src(void)
: __clobber_all);
}
+#ifdef CAN_USE_MOVSX
+
+/*
+ * A BPF_REG_LINK_SEXT register carries a delta, so anything forming a low-32 link off
+ * it must inherit that delta rather than assume zero: r9 is (u32)(r6 + 5), not
+ * (u32)(r6 + 0). Resetting it recorded r9 == r6, and the verifier then read a
+ * constant the program never computes.
+ */
+SEC("socket")
+__success
+__naked void sext_delta_survives_zext_mov(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 <<= 32; \
+ call %[bpf_get_prandom_u32]; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ w7 = w6; /* BPF_REG_LINK_ZEXT, delta 0 */ \
+ w7 += 5; /* BPF_REG_LINK_ZEXT, delta 5 */ \
+ r8 = (s32)r7; /* BPF_REG_LINK_SEXT, delta 5 */ \
+ w9 = w8; /* must stay (u32)(r6 + 5) */ \
+ if r6 != 0 goto 1f; /* r6 == 0, so r9 == 5 */ \
+ if r9 == 5 goto 1f; /* always taken: r9 is 5 */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A 32-bit sign extension keeps the low 32 bits, so narrowing the source
+ * reaches the destination the same way it does for a zero extension. The high
+ * half follows the sign, so the value seen here is negative.
+ */
+SEC("socket")
+__success
+__naked void sext_mov_wide_src(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r7 = (s32)r6; /* forms the link */ \
+ if w6 != -1 goto 1f; /* narrows r6, propagates to r7 */ \
+ if r7 == -1 goto 1f; /* sign-extended, not 0xffffffff */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * The source need not already be in a set. A call return or a load has no
+ * id, so the sign-extending mov is what mints one -- which is the shape the
+ * failures that motivated this take, rather than a prior pairing.
+ */
+SEC("socket")
+__success
+__retval(0)
+__naked void sext_mov_unlinked_src(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r7 = (s32)r0; /* r0 has no id; mint one */ \
+ if w0 != -1 goto l0_%=; /* narrows r0, propagates to r7 */ \
+ if r7 == -1 goto l0_%=; /* sign-extended, not 0xffffffff */ \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * r0 = (s32)r0 is how a sign-extended int return lands. src and dst are the
+ * same register, but r0 is already linked, so there is a set for it to stay
+ * in and the narrowing still propagates.
+ */
+SEC("socket")
+__success
+__naked void sext_self_mov_keeps_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r7 = r6; /* r6, r7 linked */ \
+ r7 = (s32)r7; /* self-mov, keeps the id */ \
+ if w6 != -1 goto 1f; /* narrows r6, propagates to r7 */ \
+ if r7 == -1 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * The same self-mov on an unlinked register has nothing to link to, so it
+ * must not mint an id that would leave r6 describing itself.
+ */
+SEC("socket")
+__success __log_level(2)
+/* an id would print as R6=scalar(id=N+0.sx,smin=... */
+__msg("(bf) r6 = (s32)r6 {{.*}} R6=scalar(smin=")
+__naked void sext_self_mov_no_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 ^= 0; /* drop the id */ \
+ r6 = (s32)r6; /* forms no link */ \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * The shape a sign-extended return takes when it crosses a helper call: the
+ * branch narrows it first, then it is spilled. No link is needed past the
+ * spill -- r7 is already known by then -- but the value has to survive the
+ * round trip.
+ */
+SEC("socket")
+__success
+__retval(0)
+__naked void sext_value_survives_spill_across_call(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r7 = (s32)r6; /* sext link to r6 */ \
+ if w6 != -1 goto l0_%=; /* narrows r6, so r7 is -1 */ \
+ *(u64 *)(r10 - 8) = r7; /* spill the known value */ \
+ call %[bpf_get_prandom_u32]; \
+ r8 = *(u64 *)(r10 - 8); /* fill it back */ \
+ if r8 == -1 goto l0_%=; /* survived the round trip */ \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A delta on the branch register is not modelled together with a low-32
+ * link, so the propagation is skipped rather than guessed at.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void sext_no_sync_when_base_has_delta(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r7 = (s32)r6; /* forms the link */ \
+ r8 = r6; \
+ r8 += 3; /* delta on the branch reg */ \
+ if r8 != 3 goto 1f; /* must not propagate to r7 */ \
+ if r7 == 0 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * ... and with the link as the branch register the propagation must not run
+ * backwards: a BPF_REG_LINK_SEXT register knows nothing about the base's high half, so
+ * narrowing it must leave the rest of the set alone. Were the guard missing,
+ * r8 would be rebuilt as r7 + 3 == 2, treating r7 as if it were the base.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void sext_no_sync_from_subreg_base(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r7 = (s32)r6; /* forms the link */ \
+ r8 = r6; \
+ r8 += 3; /* delta on r8 */ \
+ if r7 != -1 goto 1f; /* must not propagate to r8 */ \
+ if r8 == 2 goto 1f; /* taken only if r8 wrongly narrowed */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Two different kinds can share one id: r2 is (u32)(r6 + 1) and r7 is
+ * (s32)(r6 + 1). Pinning r2 really does pin r7 -- the deltas are equal, so
+ * w2 == 1 means r7 == 1 -- but sync_linked_regs() skips any pair of
+ * differing kinds, and here that imprecision is load-bearing. bpf-gcc
+ * builds "i += 1" for an int loop counter into exactly this shape, and
+ * deducing r7 makes the counter a fresh constant on every iteration, so the
+ * state never converges and iters.c:iter_obfuscate_counter runs to the 1M
+ * instruction limit.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void sext_no_sync_from_zext_sibling(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 <<= 32; \
+ call %[bpf_get_prandom_u32]; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ r2 = r6; \
+ w2 += 1; /* r2 = (u32)(r6 + 1) */ \
+ r7 = (s32)r2; /* r7 = (s32)(r6 + 1) */ \
+ if w2 != 1 goto 1f; /* must not propagate to r7 */ \
+ if r7 == 1 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * The two link kinds rebuild the high half differently: the same low half
+ * reaches -1 through a sign extension and 0xffffffff through a zero
+ * extension, so only one path clears the guard. As above this checks the outcome -- the differing
+ * ranges keep the states apart on their own.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void sext_kinds_reach_different_values(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 &= 1; \
+ if r6 >= 1 goto 2f; \
+ /* explored first: r7 is a sign-extended link of r8 */ \
+ call %[bpf_get_prandom_u32]; \
+ r8 = r0; \
+ r7 = (s32)r8; \
+ goto 1f; \
+2: \
+ /* runtime path: r7 is a zero-extended link of r8 */ \
+ call %[bpf_get_prandom_u32]; \
+ r8 = r0; \
+ w7 = w8; \
+1: \
+ if w8 != -1 goto 3f; \
+ if r7 == -1 goto 3f; /* only the sign-extended path */ \
+ r0 /= 0; \
+3: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * The sign-extending counterpart: a narrowing of the base must not widen a
+ * member that already proved itself tighter.
+ */
+SEC("socket")
+__success
+__naked void sext_sync_keeps_narrower_member(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ r7 = (s32)r6; /* forms the link */ \
+ if w7 > 7 goto 1f; /* r7 low 32 bits in [0, 7] */ \
+ if r6 > 100 goto 1f; /* narrows the base, syncs to r7 */ \
+ if r7 <= 7 goto 1f; /* still provable if r7 kept [0, 7] */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * The reverse direction is only refused because the base is wider than 32
+ * bits. Narrow it first -- "w6 = w6" leaves r6 in [0, U32_MAX] -- and
+ * sync_linked_regs() does run, with r6 carrying no kind of its own and the
+ * member carrying BPF_REG_LINK_SEXT. The reconstruction there has to be the zero
+ * extension: r6 is below 2^32 and equal to the member's low half, so a
+ * signed compare on the member must not hand r6 the sign-extended value.
+ * Forgetting that dropped every r6 >= 2^31 from the range and made the
+ * guarded div provably dead.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void sext_narrow_base_keeps_high_values(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ w6 = w6; /* r6 in [0, U32_MAX] */ \
+ r7 = (s32)r6; /* forms the link */ \
+ r8 = 1; \
+ r8 <<= 31; /* 0x80000000 */ \
+ if r7 s> 100 goto 1f; /* r6 is [0,100] or >= 2^31 */ \
+ if r6 < r8 goto 1f; /* reachable: r6 may be >= 2^31 */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A base/step line does not survive the sign extension: the reconstruction
+ * subtracts 2^32, and 2^32 is not a multiple of 3. Keeping the line let
+ * __update_bounds_from_step() snap r7's bounds onto the wrong congruence
+ * class -- r6 = 0x80000007 is a multiple of 3, so r7 = -2147483641 is
+ * reachable, but the stale line excluded it.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void sext_drops_stale_step(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ w6 = w6; \
+ r6 *= 3; /* base 0, step 3 */ \
+ r7 = (s32)r6; /* forms the link */ \
+ r8 = 1; \
+ r8 <<= 31; \
+ r9 = r8; \
+ r9 += 7; \
+ if r6 < r8 goto 1f; \
+ if r6 > r9 goto 1f; /* r6 in [0x80000000, 0x80000007] */ \
+ if r7 != -2147483641 goto 1f; /* reachable: r6 == 0x80000007 */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+#endif /* CAN_USE_MOVSX */
+
char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/verifier_movsx.c b/tools/testing/selftests/bpf/progs/verifier_movsx.c
index 3fcd03b7a547..1d04a4369f81 100644
--- a/tools/testing/selftests/bpf/progs/verifier_movsx.c
+++ b/tools/testing/selftests/bpf/progs/verifier_movsx.c
@@ -4,11 +4,7 @@
#include <bpf/bpf_helpers.h>
#include "bpf_misc.h"
-#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))
+#ifdef CAN_USE_MOVSX
SEC("socket")
__description("MOV32SX, S8")
@@ -405,6 +401,6 @@ int dummy_test(void)
return 0;
}
-#endif
+#endif /* CAN_USE_MOVSX */
char _license[] SEC("license") = "GPL";
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (6 preceding siblings ...)
2026-10-20 16:19 ` [PATCH bpf-next v3 07/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
@ 2026-10-20 16:19 ` Vineet Gupta
2026-10-20 16:53 ` bot+bpf-ci
2026-10-20 17:20 ` sashiko-bot
2026-10-20 16:19 ` [PATCH bpf-next v3 09/12] bpf: Track low-32 scalar equality across narrowing stack fills Vineet Gupta
` (3 subsequent siblings)
11 siblings, 2 replies; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16: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
A low-32 link over a wide base drives sync_linked_regs() forwards only.
Narrowing the base reaches the members, but narrowing a member tells the
base nothing:
r6 = ... /* full 64-bit unknown */
w7 = w6;
w7 += 5;
if w7 != 15 goto ... /* so (u32)r6 == 10 */
if w6 == 10 goto ... /* not deduced */
That refusal is broader than it needs to be, in two ways.
It only applies to a *wide* base in the first place -- the guard is
scoped on get_reg_width(reg) > 32. A base that fits 32 bits is equal to
the member's low half, so a compare on the member pins it exactly, and
such a pair already falls through to the differencing arm. What the two
mov patches had to get right there is which extension rebuilds it, since
choosing wrong is unsound rather than merely imprecise.
And for a wide base it is only the *high* half that is unrecoverable.
Writing the two registers against the same abstract X, the member is
ext(X + d_member) and the base is X + d_base, so their low 32 bits are
(X + d) mod 2^32 and differ by the known constant d_member - d_base. The
member therefore pins the base's low half exactly; what it says nothing
about is everything above bit 31.
Eduard put it as a direction rather than a kind, on v2 03/13:
> - if known_reg is sext/zext -> sync to 'full' register recovers only
> lower 32-bits and keeps upper untouched (counting on cross-domain
> bounds sync logic).
So instead of skipping, add the delta difference to the member's 32-bit
range and intersect it into the base's r32 and tnum_subreg, leaving r64
and the upper tnum to reg_bounds_sync(). Never writing the high half
directly is what keeps this sound. Dropping the guard outright instead
makes scalars_alu32_basic and zext_narrow_dst_keeps_base verify, and both
must not; they still fail here.
It buys nothing today, and is proposed anyway. No verdict changes on any
of the three corpora, and on its own it costs nothing anywhere. The zero
is a result rather than a non-event: instrumenting the new arm to emit a
token, it fires 78 times under bpf-gcc and 40 under clang, so programs do
reach it and come out identical. zext_reverse_pins_low_half is a
__failure without the patch.
It does interact with the narrowing-fill patch that follows -- together
they cost big_alloc2 2956 -> 3095 insns where neither does alone -- which
that patch spells out, since a bisect lands the cost there.
Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: new in v3.
- answers Eduard's point on v2 03/13: the reverse direction recovers
the low half even though it cannot recover the high one. A base
that fits 32 bits was never refused -- the guard is scoped on
get_reg_width(reg) > 32 -- so this is the remaining case, a base
wider than 32 bits.
- proposed for merge, not tagged, and it buys nothing today -- no
verdict changes on any of the three corpora.
- costs nothing on its own. With the narrowing-fill patch that follows
it costs big_alloc2 2956 -> 3095 insns; neither produces that alone,
and a bisect lands it on the fill patch, which says so.
- the arm is instrumented to confirm it is reached rather than merely
silent: 78 firings under bpf-gcc, 40 under clang.
kernel/bpf/verifier.c | 58 ++++++++++++++-----
.../bpf/progs/verifier_linked_scalars.c | 47 ++++++++++++---
2 files changed, 80 insertions(+), 25 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index dffcaa2e1392..6b26487d4549 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -18521,29 +18521,54 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
if (reg->id != known_reg->id)
continue;
/*
- * The reverse direction does not work for a narrow known_reg:
- * it knows only its low 32 bits, which say nothing about a
- * wider reg's high half. Neither (u32)(base + delta) nor
- * (s32)(base + delta) inverts once the base is wider than 32
- * bits.
+ * The reverse direction, from a narrow known_reg to a wider
+ * reg, does not invert: neither (u32)(base + delta) nor
+ * (s32)(base + delta) says anything about the base's high
+ * half. It does still pin the low half, though -- both sides
+ * are (base + delta) mod 2^32, differing only by their deltas
+ * -- so recover that much and leave the high half alone.
*/
if ((known_reg->link_kind == BPF_REG_LINK_ZEXT ||
known_reg->link_kind == BPF_REG_LINK_SEXT) &&
reg->link_kind != BPF_REG_LINK_ZEXT &&
reg->link_kind != BPF_REG_LINK_SEXT &&
- get_reg_width(reg) > 32)
- continue;
+ get_reg_width(reg) > 32) {
+ /*
+ * Only @low's 32-bit half is meaningful: its var_off
+ * is advanced over all 64 bits while r64 and the
+ * base/step line are not, and nothing below reads
+ * either. It is a scratch value, not a register state.
+ */
+ struct bpf_reg_state low = *known_reg;
+ struct tnum low32;
+
+ fake_reg.type = SCALAR_VALUE;
+ __mark_reg_known(&fake_reg,
+ (s64)reg->delta - (s64)known_reg->delta);
+ scalar32_min_max_add(&low, &fake_reg);
+ low.var_off = tnum_add(low.var_off, fake_reg.var_off);
+
+ cnum32_intersect_with(®->r32, low.r32);
+ low32 = tnum_intersect(tnum_subreg(reg->var_off),
+ tnum_subreg(low.var_off));
+ reg->var_off = tnum_with_subreg(reg->var_off, low32);
+ reg_bounds_sync(reg);
+ goto scratched;
+ }
/*
* Skip a pair of differing kinds. Where BPF_REG_LINK_FULL meets
- * a 32-bit kind the delta relationship genuinely does not hold:
- * the deltas were added at different ALU widths.
- * BPF_REG_LINK_ZEXT against BPF_REG_LINK_SEXT is not that case
- * -- both are base + delta in the low 32 bits, so narrowing one
- * really does narrow the other -- but that deduction is
- * declined on purpose. It makes an int loop counter a fresh
- * constant on every iteration, so no two iterations prune
- * against each other and the program runs to the instruction
- * limit. See sext_no_sync_from_zext_sibling.
+ * a 32-bit kind the delta relationship does not hold over all
+ * 64 bits: the deltas were added at different ALU widths. For a
+ * wide member the low half still relates and the arm above has
+ * already recovered it; a member that fits 32 bits does not
+ * reach that arm and is skipped outright. BPF_REG_LINK_ZEXT
+ * against BPF_REG_LINK_SEXT is not that case -- both are base +
+ * delta in the low 32 bits, so narrowing one really does narrow
+ * the other -- but that deduction is declined on purpose. It
+ * makes an int loop counter a fresh constant on every
+ * iteration, so no two iterations prune against each other and
+ * the program runs to the instruction limit. See
+ * sext_no_sync_from_zext_sibling.
*/
if (reg->link_kind && known_reg->link_kind &&
reg->link_kind != known_reg->link_kind)
@@ -18622,6 +18647,7 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
*reg = prev;
reg_bounds_sync(reg);
}
+scratched:
if (e->is_reg)
mark_reg_scratched(env, e->regno);
else
diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
index 9a33cc60e8cb..69efe1381eca 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -247,6 +247,30 @@ l0_%=: \
}
#endif /* CAN_USE_MOVSX */
+SEC("socket")
+__success
+__retval(0)
+__naked void zext_reverse_pins_low_half(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 <<= 32; \
+ call %[bpf_get_prandom_u32]; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ w7 = w6; \
+ w7 += 5; /* r7 = (u32)(r6 + 5) */ \
+ if w7 != 15 goto l0_%=; /* so (u32)r6 == 10 */ \
+ if w6 == 10 goto l0_%=; \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
/*
* Test that sync_linked_regs() correctly handles large offset differences.
* r1.off = S32_MIN, r2.off = 1, delta = S32_MIN - 1 requires 64-bit math.
@@ -414,9 +438,11 @@ l0_%=: \
}
/*
- * Test that sync_linked_regs() skips propagation when one register used
- * alu32 (BPF_REG_LINK_ZEXT) and the other used alu64 (BPF_REG_LINK_FULL).
- * The delta relationship doesn't hold across different ALU widths.
+ * Test that sync_linked_regs() does not carry the delta relationship across
+ * registers that used different ALU widths: r7 used alu32 (BPF_REG_LINK_ZEXT) and r8
+ * alu64 (BPF_REG_LINK_FULL), so the relationship does not hold over all 64 bits. The
+ * low half is recovered -- r8 comes out exactly 0x100000000 -- which is why
+ * the div is still reachable and this is a __failure.
*/
SEC("socket")
__failure __msg("div by zero")
@@ -434,7 +460,7 @@ __naked void scalars_alu32_alu64_cross_type(void)
/* r7 = 0xFFFFFFFF */ \
/* sync: known_reg=r7 (BPF_REG_LINK_ZEXT), reg=r8 (BPF_REG_LINK_FULL) */ \
/* Without fix: r8 = zext(0xFFFFFFFF + 1) = 0 */ \
- /* With fix: r8 stays [2, 0x100000001] (r8 >= 2) */ \
+ /* With fix: r8 == 0x100000000, so still > 0 */ \
if r8 > 0 goto l1_%=; \
goto l0_%=; \
l1_%=: \
@@ -950,8 +976,10 @@ __naked void zext_no_sync_between_mixed_kinds(void)
}
/*
- * ... and here the low-32 link is the branch register, so the register
- * carrying the delta must not be narrowed either.
+ * ... and here the low-32 link is the branch register. Its low half does
+ * reach the register carrying the delta, but the high half must not: r8's
+ * low 32 bits become 3 while the rest stays unknown, so r8 == 3 is still
+ * not provable and the div stays reachable.
*/
SEC("socket")
__failure __msg("div by zero")
@@ -1276,9 +1304,10 @@ __naked void sext_no_sync_when_base_has_delta(void)
/*
* ... and with the link as the branch register the propagation must not run
- * backwards: a BPF_REG_LINK_SEXT register knows nothing about the base's high half, so
- * narrowing it must leave the rest of the set alone. Were the guard missing,
- * r8 would be rebuilt as r7 + 3 == 2, treating r7 as if it were the base.
+ * backwards over the high half: a BPF_REG_LINK_SEXT register knows nothing about the
+ * base's high bits. The low half is recovered, so r8's low 32 bits do become
+ * 2, but treating that as the whole value -- r8 == 2, as if r7 were the base
+ * -- must not happen.
*/
SEC("socket")
__failure __msg("div by zero")
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 09/12] bpf: Track low-32 scalar equality across narrowing stack fills
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (7 preceding siblings ...)
2026-10-20 16:19 ` [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction Vineet Gupta
@ 2026-10-20 16:19 ` Vineet Gupta
2026-10-20 16:19 ` [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
` (2 subsequent siblings)
11 siblings, 0 replies; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16: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
A 32-bit fill from a wider spilled scalar has the same shape as a 32-bit
mov from a wider source, and the relation was dropped rather than
recorded:
r6 = ... /* full 64-bit unknown */
*(u64 *)(r10 - 8) = r6; /* slot linked to r6 */
r2 = *(u32 *)(r10 - 8); /* narrowing fill */
if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */
if r2 == 0 goto ... /* not deduced today */
Record a low-32 link as the mov arm does. Stack slots are already
first-class members of an ->id set, so sync_linked_regs() and the
reconstruction helpers apply unchanged. A fill narrower than 32 bits has
no expressible relation and still drops it.
Which extension rebuilds the high half depends on the load, so
check_stack_read() takes is_ldsx and sets BPF_REG_LINK_SEXT where that
is known. check_mem_access() then keeps a sign-extending link across a
4-byte sign-extending load only: BPF_REG_LINK_SEXT means (s32)(base +
delta) specifically, so an 8- or 16-bit ldsx is a relation the kind
cannot express, the same way the ALU arm's subreg_link is gated on
(insn->off >> 3) == 4.
Costs. A bisect lands one clang regression here -- big_alloc2 2956 -> 3095
insns, 157 -> 165 states -- but it is not this patch alone: it takes both
this and the preceding reverse-direction patch, and neither moves
big_alloc2 by itself. The external corpus does move for this patch alone,
no verdict changes, six programs verifying in more instructions:
+1812 2470 -> 4282 test_file_open bpfjailer-lib-tests open
+1765 59556 -> 61321 twfw_connect4 tupperware-agent twfw_sock
+1765 59556 -> 61321 twfw_sendmsg4 same object
+752 5874 -> 6626 layered_enqueue scx_layered 1.0.11.1
+252 2512 -> 2764 bpfj_exec_execve exec_enforce
+252 2512 -> 2764 bpfj_exec_execveat same object
+6598 over 25.2M, or +0.026%, and +218 states. The shape is the familiar
one: a more precise recorded state has a smaller equivalence class and
prunes against fewer predecessors.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 9/13.
- renamed to the new encoding, and the fill inherits the slot's delta
rather than resetting it, matching patch 6
- a sign-extending load keeps a link only if it is a 4-byte
BPF_REG_LINK_SEXT. BPF_REG_LINK_ZEXT says the opposite of what the
load just did, and an 8- or 16-bit ldsx is a relation the kind cannot
express.
- measured cost, which v2 did not report: six external programs verify
in more instructions, +6598 aggregate (+0.026%), worst +1812 on
test_file_open. No verdict changes. Attributed to this patch by
building the patch-7 and patch-8 kernels separately.
kernel/bpf/verifier.c | 60 +++++++++++++++++++++++++++++++++++--------
1 file changed, 49 insertions(+), 11 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6b26487d4549..feefa5733fd7 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4223,7 +4223,8 @@ static void bpf_diag_stack_read_invalid(struct bpf_verifier_env *env, int off, i
static int check_stack_read_fixed_off(struct bpf_verifier_env *env,
/* func where src register points to */
struct bpf_func_state *reg_state,
- int off, int size, int dst_regno)
+ int off, int size, int dst_regno,
+ bool is_ldsx)
{
struct bpf_verifier_state *vstate = env->cur_state;
struct bpf_func_state *state = vstate->frame[vstate->curframe];
@@ -4258,22 +4259,52 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,
if (size <= spill_size &&
bpf_stack_narrow_access_ok(off, size, spill_size)) {
+ bool narrowing = get_reg_width(reg) > size * BITS_PER_BYTE;
+ /*
+ * A narrowing fill keeps only the slot's low 32 bits,
+ * so record a low-32 link rather than dropping the
+ * relation, as a 32-bit mov from a wide source does.
+ * Which link kind depends on how the load fills the high
+ * half, hence is_ldsx.
+ */
+ bool subreg_link = narrowing && size == 4;
+
if (dst_regno < 0)
return 0;
- if (env->bpf_capable && size == 4 && spill_size == 4 &&
- get_reg_width(reg) <= 32)
+ if (env->bpf_capable && size == 4 &&
+ (subreg_link || (spill_size == 4 && !narrowing)))
/* Ensure stack slot has an ID to build a relation
* with the destination register on fill.
*/
assign_scalar_id_before_mov(env, reg);
state->regs[dst_regno] = *reg;
- /* Break the relation on a narrowing fill.
- * coerce_reg_to_size will adjust the boundaries.
+ /*
+ * A fill that is not narrowing copies the slot's link
+ * kind verbatim, which a sign-extending load can
+ * contradict. check_mem_access() runs after this and
+ * drops any kind but BPF_REG_LINK_SEXT once it knows
+ * the extension was not a no-op.
*/
- if (get_reg_width(reg) > size * BITS_PER_BYTE)
+ if (subreg_link && reg->id) {
+ /*
+ * Keep the slot's delta: both
+ * (u32)(base + d) and (s32)(base + d)
+ * have low half base + d, so the fill
+ * inherits it rather than resetting it.
+ */
+ state->regs[dst_regno].link_kind =
+ is_ldsx ? BPF_REG_LINK_SEXT : BPF_REG_LINK_ZEXT;
+ } else if (narrowing) {
+ /*
+ * Nothing to relate: either the slot has
+ * no id to share, or the fill is narrower
+ * than the 32 bits a link can describe.
+ * coerce_reg_to_size adjusts the bounds.
+ */
bpf_clear_scalar_id(&state->regs[dst_regno]);
+ }
} else {
int spill_cnt = 0, zero_cnt = 0;
@@ -4439,7 +4470,7 @@ static int check_stack_read_var_off(struct bpf_verifier_env *env, struct bpf_reg
*/
static int check_stack_read(struct bpf_verifier_env *env,
struct bpf_reg_state *reg, argno_t ptr_argno, int off, int size,
- int dst_regno)
+ int dst_regno, bool is_ldsx)
{
struct bpf_func_state *state = bpf_func(env, reg);
int err;
@@ -4478,7 +4509,7 @@ static int check_stack_read(struct bpf_verifier_env *env,
if (!var_off) {
off += reg->var_off.value;
err = check_stack_read_fixed_off(env, state, off, size,
- dst_regno);
+ dst_regno, is_ldsx);
} else {
/* Variable offset stack reads need more conservative handling
* than fixed offset ones. Note that dst_regno >= 0 on this
@@ -7295,7 +7326,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b
if (t == BPF_READ)
err = check_stack_read(env, reg, argno, off, size,
- value_regno);
+ value_regno, is_ldsx);
else
err = check_stack_write(env, reg, off, size,
value_regno, insn_idx);
@@ -7392,13 +7423,20 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b
* Sign-extension can change the register value relative
* to a scalar it is linked with by id (e.g. a zero-
* extending fill of the same spilled stack slot), thus
- * drop the shared id in that case.
+ * drop the shared id in that case. Only a 4-byte
+ * BPF_REG_LINK_SEXT link survives: it says the high
+ * half is this very sign-extension. BPF_REG_LINK_ZEXT
+ * says the opposite and would be a lie about the value
+ * just produced, and an 8- or 16-bit sign extension is
+ * a relation BPF_REG_LINK_SEXT cannot express at all --
+ * it means (s32)(base + delta) specifically.
*/
bool no_sext = reg_umax(®s[value_regno]) <
(1ULL << (size * BITS_PER_BYTE - 1));
coerce_reg_to_size_sx(®s[value_regno], size);
- if (!no_sext)
+ if (!no_sext &&
+ !(size == 4 && regs[value_regno].link_kind == BPF_REG_LINK_SEXT))
bpf_clear_scalar_id(®s[value_regno]);
}
}
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for narrowing stack fills
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (8 preceding siblings ...)
2026-10-20 16:19 ` [PATCH bpf-next v3 09/12] bpf: Track low-32 scalar equality across narrowing stack fills Vineet Gupta
@ 2026-10-20 16:19 ` Vineet Gupta
2026-10-20 16:29 ` sashiko-bot
2026-10-20 16:52 ` bot+bpf-ci
2026-10-20 16:19 ` [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills Vineet Gupta
2026-10-20 16:19 ` [PATCH bpf-next v3 12/12] [do not merge] selftests/bpf: Cover the low-32 link for " Vineet Gupta
11 siblings, 2 replies; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16: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
Eight programs, following the mov set:
- zext_fill_narrow_from_wide_spill: narrowing the spilled value reaches
the filled register
- sext_fill_narrow_from_wide_spill: the same for a sign-extending fill
- sext_delta_survives_narrowing_fill: a slot carrying a delta hands it
to the fill, so r2 is (u32)(r6 + 5) and not (u32)r6
- zext_fill_full_width_keeps_full_link: a full-width fill stays a plain
64-bit equality
- zext_fill_byte_forms_no_link: a sub-word fill is below the model
- fill_kinds_reach_different_values: the same, for the two kinds off one
slot
- sext_fill_does_not_inherit_zext_link: a sign-extending fill must not
come away with the slot's zero-extending link
- sext_byte_fill_drops_sext_link: nor may an 8-bit ldsx keep a
sign-extending one
The first three pin the link itself: disabling link formation in the fill
arm makes all three fail. The last two pin the link-kind checks in
check_mem_access() and assert on the register dump rather than a guarded
branch, so they fail on the rule rather than a downstream effect.
The sign-extending fills are ldsx, so they sit under a new CAN_USE_LDSX
gate; verifier_ldsx.c open-coded the same condition and uses the macro
now. sext_byte_fill_drops_sext_link needs both gates, since the
BPF_REG_LINK_SEXT it tests is built with a movsx and only the fill is an
ldsx.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 10/13.
- new: sext_delta_survives_narrowing_fill, for the inherited delta
- new: sext_fill_does_not_inherit_zext_link and
sext_byte_fill_drops_sext_link, for the two kinds a sign-extending
load must not come away with. Both assert on the register dump
rather than a guarded branch.
- the sign-extending fills are ldsx, so they sit under a new
CAN_USE_LDSX gate; verifier_ldsx.c open-coded the same condition and
uses the macro now.
tools/testing/selftests/bpf/progs/bpf_misc.h | 8 +
.../selftests/bpf/progs/verifier_ldsx.c | 8 +-
.../bpf/progs/verifier_linked_scalars.c | 306 ++++++++++++++++++
3 files changed, 316 insertions(+), 6 deletions(-)
diff --git a/tools/testing/selftests/bpf/progs/bpf_misc.h b/tools/testing/selftests/bpf/progs/bpf_misc.h
index c5ffb36dfd74..ef0250a10cc7 100644
--- a/tools/testing/selftests/bpf/progs/bpf_misc.h
+++ b/tools/testing/selftests/bpf/progs/bpf_misc.h
@@ -293,6 +293,14 @@
#define CAN_USE_MOVSX
#endif
+#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_LDSX))
+#define CAN_USE_LDSX
+#endif
+
#if __clang_major__ >= 18 && defined(ENABLE_ATOMICS_TESTS) && \
(defined(__TARGET_ARCH_arm64) || \
defined(__TARGET_ARCH_x86) || \
diff --git a/tools/testing/selftests/bpf/progs/verifier_ldsx.c b/tools/testing/selftests/bpf/progs/verifier_ldsx.c
index 49e8cd4bb4f9..6c1553059101 100644
--- a/tools/testing/selftests/bpf/progs/verifier_ldsx.c
+++ b/tools/testing/selftests/bpf/progs/verifier_ldsx.c
@@ -5,11 +5,7 @@
#include "bpf_misc.h"
#include <bpf_arena_common.h>
-#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_LDSX))
+#ifdef CAN_USE_LDSX
SEC("socket")
__description("LDSX, S8")
@@ -464,6 +460,6 @@ int dummy_test(void)
return 0;
}
-#endif
+#endif /* CAN_USE_LDSX */
char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
index 69efe1381eca..ab78285153fb 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -245,6 +245,7 @@ l0_%=: \
: __imm(bpf_get_prandom_u32)
: __clobber_all);
}
+
#endif /* CAN_USE_MOVSX */
SEC("socket")
@@ -1120,6 +1121,102 @@ __naked void zext_mov_breaks_linked_src(void)
: __clobber_all);
}
+/*
+ * A narrowing fill keeps only the slot's low 32 bits, so a later narrowing of
+ * the spilled value must still reach the filled register. Same relation as a
+ * 32-bit mov from a wide source, with the stack slot as the base.
+ */
+SEC("socket")
+__success
+__naked void zext_fill_narrow_from_wide_spill(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ *(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \
+"
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+" r2 = *(u32 *)(r10 - 8); /* narrowing fill, forms the link */ \
+"
+#else
+" r2 = *(u32 *)(r10 - 4); \
+"
+#endif
+" if w6 != 0 goto 1f; /* narrows r6, propagates to r2 */ \
+ if r2 == 0 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A full-width fill of a wide slot is a plain 64-bit equality, not a low-32
+ * link, so it must keep propagating exactly as before.
+ */
+SEC("socket")
+__success
+__naked void zext_fill_full_width_keeps_full_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; \
+ *(u64 *)(r10 - 8) = r6; \
+ r2 = *(u64 *)(r10 - 8); /* no narrowing */ \
+ if r6 != 0 goto 1f; \
+ if r2 == 0 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A sub-word fill is below the low-32 model, so no link is formed and the
+ * relation is dropped as before.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void zext_fill_byte_forms_no_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; \
+ *(u64 *)(r10 - 8) = r6; \
+"
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+" r2 = *(u8 *)(r10 - 8); /* 1-byte fill: no link */ \
+"
+#else
+" r2 = *(u8 *)(r10 - 1); \
+"
+#endif
+" if w6 != 0 goto 1f; \
+ if r2 == 0 goto 1f; /* not deduced */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
#ifdef CAN_USE_MOVSX
/*
@@ -1494,6 +1591,215 @@ __naked void sext_drops_stale_step(void)
: __clobber_all);
}
+/*
+ * Same for a narrowing fill: the slot is (s32)(r6 + 5), so the filled register
+ * is (u32)(r6 + 5). Forcing the delta to 0 made the verifier believe r2 == r6.
+ */
+SEC("socket")
+__success
+__naked void sext_delta_survives_narrowing_fill(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 <<= 32; \
+ call %[bpf_get_prandom_u32]; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ w7 = w6; /* BPF_REG_LINK_ZEXT, delta 0 */ \
+ w7 += 5; /* BPF_REG_LINK_ZEXT, delta 5 */ \
+ r8 = (s32)r7; /* BPF_REG_LINK_SEXT, delta 5 */ \
+ *(u64 *)(r10 - 8) = r8; /* full spill keeps the link */ \
+"
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+" r2 = *(u32 *)(r10 - 8); /* narrowing fill inherits delta */ \
+"
+#else
+" r2 = *(u32 *)(r10 - 4); \
+"
+#endif
+" if r6 != 0 goto 1f; /* r6 == 0, so r2 == 5 */ \
+ if r2 == 5 goto 1f; /* always taken: r2 is 5 */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
#endif /* CAN_USE_MOVSX */
+#ifdef CAN_USE_LDSX
+
+/*
+ * The sign-extending counterpart: the filled register is the sign extension of
+ * the slot's low 32 bits, so a narrowing of those bits arrives sign-extended.
+ */
+SEC("socket")
+__success
+__naked void sext_fill_narrow_from_wide_spill(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ *(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ \
+"
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+" r2 = *(s32 *)(r10 - 8); /* narrowing sx fill */ \
+"
+#else
+" r2 = *(s32 *)(r10 - 4); \
+"
+#endif
+" if w6 != -1 goto 1f; /* narrows r6, propagates to r2 */ \
+ if r2 == -1 goto 1f; /* sign-extended, not 0xffffffff */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * The same, for the two link kinds off one slot.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void fill_kinds_reach_different_values(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 &= 1; \
+ call %[bpf_get_prandom_u32]; \
+ r8 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r8 |= r0; \
+ *(u64 *)(r10 - 8) = r8; \
+ if r6 >= 1 goto 2f; \
+"
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+" r2 = *(s32 *)(r10 - 8); /* sign-extending fill */ \
+"
+#else
+" r2 = *(s32 *)(r10 - 4); \
+"
+#endif
+" goto 1f; \
+2: \
+"
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+" r2 = *(u32 *)(r10 - 8); /* zero-extending fill */ \
+"
+#else
+" r2 = *(u32 *)(r10 - 4); \
+"
+#endif
+"1: \
+ if w8 != -1 goto 3f; \
+ if r2 == -1 goto 3f; /* only the sign-extending path */ \
+ r0 /= 0; \
+3: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A sign-extending fill must not come away with a zero-extending link. The
+ * slot below already fits 32 bits, so the fill is not narrowing and assigns
+ * no link kind of its own, and "state->regs[dst] = *reg" copies the slot's
+ * verbatim; check_mem_access() is what has to drop it, since it would leave
+ * r2 recording a zero-extension of a value it has just sign-extended.
+ * Asserted on the register dump rather than on a guarded branch, so it pins
+ * the rule itself and not a downstream effect.
+ */
+SEC("socket")
+__success __log_level(2)
+/* a copied link would print as R2=scalar(id=N+0,smin=... */
+__msg("(81) r2 = *(s32 *)(r10 {{.*}} R2=scalar(smin=")
+__naked void sext_fill_does_not_inherit_zext_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ w7 = w6; /* r7 = zext32(r6), fits 32 bits */ \
+ *(u64 *)(r10 - 8) = r7; \
+"
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+" r2 = *(s32 *)(r10 - 8); /* sign-extending, not narrowing */ \
+"
+#else
+" r2 = *(s32 *)(r10 - 4); \
+"
+#endif
+" r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * BPF_REG_LINK_SEXT says the register is (s32)(base + delta) -- a 32-bit sign
+ * extension specifically. An 8- or 16-bit ldsx is a different relation, so
+ * the exemption that keeps a sign-extending link across a sign-extending
+ * load has to be gated on the load width. Ungated, r2 below claims to be
+ * (s32)r6 when it is really (s8)((s32)r6).
+ */
+SEC("socket")
+__success __log_level(2)
+#ifdef CAN_USE_MOVSX
+/*
+ * Needs MOVSX as well as LDSX: the BPF_REG_LINK_SEXT under test is built with
+ * r7 = (s32)r6, and only the byte fill below is an ldsx.
+ */
+/* a surviving link would print as R2=scalar(id=N+0.sx,smin=... */
+__msg("(91) r2 = *(s8 *)(r10 {{.*}} R2=scalar(smin=")
+__naked void sext_byte_fill_drops_sext_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ r7 = (s32)r6; /* r7 = BPF_REG_LINK_SEXT, delta 0 */ \
+ if r7 > 255 goto 1f; /* r7 fits a byte */ \
+ *(u64 *)(r10 - 8) = r7; /* full spill keeps the link */ \
+"
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+" r2 = *(s8 *)(r10 - 8); /* 8-bit ldsx: no link survives */ \
+"
+#else
+" r2 = *(s8 *)(r10 - 1); \
+"
+#endif
+" r0 = r2; /* keep r2 live so the fill prints it */ \
+ r0 &= 1; \
+ exit; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+#endif /* CAN_USE_MOVSX */
+
+#endif /* CAN_USE_LDSX */
+
char _license[] SEC("license") = "GPL";
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (9 preceding siblings ...)
2026-10-20 16:19 ` [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
@ 2026-10-20 16:19 ` Vineet Gupta
2026-10-20 16:42 ` sashiko-bot
2026-10-20 16:19 ` [PATCH bpf-next v3 12/12] [do not merge] selftests/bpf: Cover the low-32 link for " Vineet Gupta
11 siblings, 1 reply; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16: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
A spill narrower than its source stores the source's low 32 bits, so the
slot is their zero-extension -- the mov relation, in the store direction:
r6 = ... /* full 64-bit unknown */
*(u32 *)(r10 - 8) = r6; /* slot holds r6's low 32 bits */
if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */
r2 = *(u32 *)(r10 - 8);
if r2 == 0 goto ... /* not deduced today */
A store never sign-extends, so BPF_REG_LINK_ZEXT is the only kind that
arises. save_register_state() copies the source whole, including bounds
for bits the store did not write, so the slot must be truncated before
the kind goes on it -- otherwise the first sync_linked_regs() intersects
the correctly rebuilt low half against those stale bounds and empties
the slot.
Only one order pays. sync_linked_regs() walks spilled slots, so narrowing
while the value is still on the stack narrows the slot and the fill copies
an already narrowed value. Filling first does not benefit: the fill is a
mov, and a mov drops a zero-extending link.
Posted, not proposed. This is the direction asked for, implemented and
measured, and the measurement says do not take it. Against the ten patches
before it, on 441 cilium/katran/fb/sched_ext objects, 1467 programs:
verdicts no change at all
total_insns 102 changed, 63 worse, +84,450 (+0.34%)
+59,616 (+57.2%) 104,160 -> 163,776 test_file_open
+19,784 (+89.7%) 22,053 -> 41,837 rusty_enqueue
+2,688 (+40.6%) 6,626 -> 9,314 layered_enqueue
total_states 64 changed, 63 worse
Nothing is gained for it, and both selftest corpora hide it completely --
bpf-gcc shows no changed program at all. Nothing in
tools/testing/selftests/bpf is shaped like a sched_ext scheduler.
The mechanism, from rusty_enqueue's verifier log at the patch before this
one and at this one. The walks are identical for 17,043 steps, then:
before 1969: (c7) r6 s>>= 32
1970: safe <- pruned here
after 1969: (c7) r6 s>>= 32
frame 0: propagating fp-24 <- not pruned
One slot accounts for all of it. fp-24 is written by a narrowing spill 354
times in the walk, and "propagating fp-24" goes 0 -> 1034 while the other
slots are unchanged. The slot itself goes from
fp-24=ppppscalar()
to
fp-24=ppppscalar(id=11+0,smin=0,smax=umax=0xffffffff,...)
An opaque scalar() matches every candidate state; one carrying an id, a
kind and a range that sync_linked_regs() narrows further on each compare
matches far fewer. Three things tighten at once: check_scalar_ids()
returns true unconditionally for old_id == 0 and the slot now has an id;
regsafe() gains two rejects that need a kind to be reachable; and
bpf_bt_sync_linked_regs() makes precision all-or-nothing across a set, so
marking any member precise now reaches the slot. rusty_enqueue uses the
value as an array index, which forces mark_chain_precision constantly.
That is the relation working as designed. Recording true information about
a slot necessarily narrows its equivalence class, and a narrower class
prunes against fewer predecessors. The narrowing-fill patch earlier in the
series is the half that pays: the fill is where the value is wanted, and
it is free on every corpus.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 12/13, now tagged [do not merge].
- v2's 11/13, "bpf: record what a narrowing spill actually stores", is
dropped: it cost big_alloc2 2956 -> 3095 insns for no verdict.
- v2's worked example had the fill before the narrowing, which is the
one order this link cannot serve. Replaced with the order that works.
- the slot is truncated to the bits the store actually wrote before
the kind goes on it, and inherits the source's delta.
- NOT PROPOSED FOR MERGE. Against the ten patches before it, on 441
cilium/katran/fb/sched_ext objects: 102 programs changed, 63 worse,
test_file_open +57% and rusty_enqueue +90%, for no verdict change
anywhere. Both selftest corpora hide this completely -- bpf-gcc
shows no changed program at all. The message carries the mechanism
from the verifier log.
kernel/bpf/verifier.c | 40 +++++++++++++++++--
.../selftests/bpf/progs/verifier_spill_fill.c | 6 ++-
2 files changed, 41 insertions(+), 5 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index feefa5733fd7..3607c032df5f 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -222,6 +222,7 @@ static inline bool in_sleepable_context(struct bpf_verifier_env *env);
static const char *non_sleepable_context_description(struct bpf_verifier_env *env);
static void scalar32_min_max_add(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg);
static void scalar_min_max_add(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg);
+static void zext_32_to_64(struct bpf_reg_state *reg);
static void bpf_map_ptr_store(struct bpf_insn_aux_data *aux,
struct bpf_map *map,
@@ -3908,15 +3909,46 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
mark_stack_slot_scratched(env, spi);
if (reg && !(off % BPF_REG_SIZE) && reg->type == SCALAR_VALUE && env->bpf_capable) {
bool reg_value_fits;
+ bool subreg_link;
reg_value_fits = get_reg_width(reg) <= BITS_PER_BYTE * size;
+ /*
+ * A narrowing spill stores the low 32 bits of the source, so
+ * the slot is their zero-extension: record a low-32 link
+ * rather than dropping the relation, as a 32-bit mov does.
+ * A store never sign-extends, so there is only one link kind here.
+ */
+ subreg_link = !reg_value_fits && size == 4;
+
/* Make sure that reg had an ID to build a relation on spill. */
- if (reg_value_fits)
+ if (reg_value_fits || subreg_link)
assign_scalar_id_before_mov(env, reg);
save_register_state(env, state, spi, reg, size);
- /* Break the relation on a narrowing spill. */
- if (!reg_value_fits)
- bpf_clear_scalar_id(&ss->spilled_ptr);
+ if (!reg_value_fits) {
+ if (subreg_link && reg->id) {
+ /*
+ * save_register_state() copies the source
+ * whole, but the store only wrote its low 32
+ * bits, so truncate to those before recording
+ * the kind: a slot asserting BPF_REG_LINK_ZEXT
+ * over the source's wider bounds is a register
+ * state that contradicts itself.
+ *
+ * Keep the source's delta, though: the slot
+ * holds (u32)(base + delta), so resetting it to
+ * 0 would record a relation off by that delta.
+ */
+ zext_32_to_64(&ss->spilled_ptr);
+ ss->spilled_ptr.link_kind = BPF_REG_LINK_ZEXT;
+ } else {
+ /*
+ * Nothing to relate: either the source has no
+ * id to share, or the store is narrower than
+ * the 32 bits a link can describe.
+ */
+ bpf_clear_scalar_id(&ss->spilled_ptr);
+ }
+ }
} else if (!reg && !(off % BPF_REG_SIZE) && is_bpf_st_mem(insn) &&
env->bpf_capable) {
struct bpf_reg_state *tmp_reg = &env->fake_reg[0];
diff --git a/tools/testing/selftests/bpf/progs/verifier_spill_fill.c b/tools/testing/selftests/bpf/progs/verifier_spill_fill.c
index 4d1374885f6d..081b0fe0d70a 100644
--- a/tools/testing/selftests/bpf/progs/verifier_spill_fill.c
+++ b/tools/testing/selftests/bpf/progs/verifier_spill_fill.c
@@ -464,7 +464,11 @@ l0_%=: r1 >>= 16; \
SEC("raw_tp")
__log_level(2)
__success
-__msg("fp-8=0m??scalar()")
+/*
+ * The 4-byte spill carries the low-32 link, and the slot is truncated to
+ * the bits the store wrote; the narrower spills do neither.
+ */
+__msg("fp-8=0m??scalar(id={{[0-9]+}}+0,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))")
__msg("fp-16=00mm??scalar()")
__msg("fp-24=00mm???scalar()")
__naked void spill_subregs_preserve_stack_zero(void)
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH bpf-next v3 12/12] [do not merge] selftests/bpf: Cover the low-32 link for narrowing stack spills
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
` (10 preceding siblings ...)
2026-10-20 16:19 ` [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills Vineet Gupta
@ 2026-10-20 16:19 ` Vineet Gupta
2026-10-20 16:32 ` sashiko-bot
11 siblings, 1 reply; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 16: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
Six programs:
- zext_narrowing_spill_reaches_fill: narrowing while the value is still
on the stack narrows the slot, and the fill copies an already narrowed
value. This is the order the link is for
- zext_narrowing_spill_drops_link: the other order does not pay, since
the fill is a mov and a mov drops a zero-extending link
- zext_narrowing_spill_truncates_slot: the slot must be truncated before
the kind goes on it, or the first sync empties it. Asserted on the
dump, since nothing downstream rejects an empty slot --
BPF_F_TEST_REG_INVARIANTS does not walk them
- zext_narrowing_spill_byte_no_link: a sub-word spill is below the model
- sext_delta_survives_narrowing_spill: a source carrying a delta hands
it to the slot
- sext_fill_of_narrowing_spill_drops_zext: a sign-extending fill of such
a slot must not come away with its zero-extending link
Posted with the patch above, which is not proposed for merge; these go or
stay with it.
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 13/13, now tagged [do not merge] with the patch above.
- zext_narrowing_spill_keeps_link becomes
zext_narrowing_spill_drops_link: a fill is a mov, and a mov drops
the link (patch 4)
- new: zext_narrowing_spill_reaches_fill, the first positive test for
the spill link, narrowing before the fill
- new: zext_narrowing_spill_truncates_slot,
sext_delta_survives_narrowing_spill and
sext_fill_of_narrowing_spill_drops_zext
.../bpf/progs/verifier_linked_scalars.c | 181 ++++++++++++++++++
1 file changed, 181 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
index ab78285153fb..8ade4836e1b2 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -1217,6 +1217,128 @@ __naked void zext_fill_byte_forms_no_link(void)
: __clobber_all);
}
+/*
+ * The link does reach a fill, provided the narrowing happens while the value
+ * is still on the stack: sync_linked_regs() walks spilled slots, so narrowing
+ * r6 narrows the slot and the fill copies an already narrowed value. This is
+ * the order the narrowing-spill link is for; the other order is below.
+ */
+SEC("socket")
+__success
+__naked void zext_narrowing_spill_reaches_fill(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ *(u32 *)(r10 - 8) = r6; /* narrowing spill, forms the link */ \
+ if w6 != 0 goto 1f; /* narrow r6 while it is on the stack */ \
+ r2 = *(u32 *)(r10 - 8); /* fill gets the narrowed value */ \
+ if r2 == 0 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A narrowing spill stores only the source's low 32 bits, so the slot is their
+ * zero-extension. Filling it back is a mov, though, and that drops the link
+ * for the same reason zext_chain_drops_link does, so a later narrowing of the
+ * source does not reach the filled register.
+ */
+SEC("socket")
+__failure
+__msg("div by zero")
+__naked void zext_narrowing_spill_drops_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ *(u32 *)(r10 - 8) = r6; /* narrowing spill, forms the link */ \
+ r2 = *(u32 *)(r10 - 8); /* fill it back */ \
+ if w6 != 0 goto 1f; /* narrows r6, propagates to r2 */ \
+ if r2 == 0 goto 1f; \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * save_register_state() copies the source register whole, so the slot of a
+ * narrowing spill arrives holding bounds for bits the store never wrote.
+ * Recording BPF_REG_LINK_ZEXT on top of those is a contradiction, and the first
+ * sync_linked_regs() runs straight into it: it rebuilds the slot's low half
+ * correctly and then intersects it against the stale wide bounds, which are
+ * disjoint from it, leaving the slot with an empty range. Nothing downstream
+ * notices -- not even BPF_F_TEST_REG_INVARIANTS, which does not walk stack
+ * slots -- so assert on the dump.
+ */
+SEC("socket")
+__success __log_level(2)
+/* untruncated, the slot kept r6's umin=0x100000000 and went empty on sync */
+__msg("*(u32 *)(r10 -8) = r6 {{.*}} fp-8={{.*}}smin=0,smax=umax=0xffffffff")
+__naked void zext_narrowing_spill_truncates_slot(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r7 = 1; \
+ r7 <<= 32; \
+ r6 |= r7; /* r6 >= 2^32, so the spill narrows */ \
+ *(u32 *)(r10 - 8) = r6; /* slot is (u32)r6 */ \
+ r8 = 1; \
+ r8 <<= 32; \
+ r8 += 5; \
+ if r6 > r8 goto 1f; /* narrows r6, syncs the slot */ \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A sub-word spill is below the low-32 model, so no link is formed there.
+ * The fill is a byte load too, so this pins the spill-side and fill-side
+ * size gates together rather than either on its own.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void zext_narrowing_spill_byte_no_link(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; \
+ *(u8 *)(r10 - 8) = r6; /* 1-byte spill: no link */ \
+ r2 = *(u8 *)(r10 - 8); \
+ if w6 != 0 goto 1f; \
+ if r2 == 0 goto 1f; /* not deduced */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
#ifdef CAN_USE_MOVSX
/*
@@ -1628,6 +1750,36 @@ __naked void sext_delta_survives_narrowing_fill(void)
: __clobber_all);
}
+/*
+ * And for a narrowing spill: the slot holds (u32)(r6 + 5). Recording delta 0
+ * there put the slot, and anything filled from it, 5 away from the truth.
+ */
+SEC("socket")
+__success
+__naked void sext_delta_survives_narrowing_spill(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r6 <<= 32; \
+ call %[bpf_get_prandom_u32]; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ w7 = w6; /* BPF_REG_LINK_ZEXT, delta 0 */ \
+ w7 += 5; /* BPF_REG_LINK_ZEXT, delta 5 */ \
+ r8 = (s32)r7; /* BPF_REG_LINK_SEXT, delta 5 */ \
+ *(u32 *)(r10 - 8) = r8; /* narrowing spill keeps delta */ \
+ if r6 != 0 goto 1f; /* narrow before the fill */ \
+ r2 = *(u32 *)(r10 - 8); /* r2 == 5, not 0 */ \
+ if r2 == 5 goto 1f; /* always taken: r2 is 5 */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
#endif /* CAN_USE_MOVSX */
#ifdef CAN_USE_LDSX
@@ -1800,6 +1952,35 @@ __naked void sext_byte_fill_drops_sext_link(void)
}
#endif /* CAN_USE_MOVSX */
+/*
+ * The same, with the zero-extending link coming from a narrowing spill rather
+ * than a mov. The spill truncated the slot to 32 bits, so the fill is not
+ * narrowing and assigns no link kind of its own; the slot's zero-extending
+ * one must not survive the sign-extending load.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__naked void sext_fill_of_narrowing_spill_drops_zext(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown */ \
+ *(u32 *)(r10 - 8) = r6; /* narrowing spill: slot is ZEXT */ \
+ r2 = *(s32 *)(r10 - 8); /* sign-extending, not narrowing */ \
+ if w6 != -1 goto 1f; /* slot low 32 bits are all ones */ \
+ if r2 s>= 0 goto 1f; /* taken only if r2 was rebuilt zext */ \
+ r0 /= 0; \
+1: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
#endif /* CAN_USE_LDSX */
char _license[] SEC("license") = "GPL";
--
2.53.0-Meta
^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for narrowing stack fills
2026-10-20 16:19 ` [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
@ 2026-10-20 16:29 ` sashiko-bot
2026-10-20 17:15 ` Vineet Gupta
2026-10-20 16:52 ` bot+bpf-ci
1 sibling, 1 reply; 25+ messages in thread
From: sashiko-bot @ 2026-10-20 16:29 UTC (permalink / raw)
To: Vineet Gupta; +Cc: bpf
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Low] selftests/bpf: misplaced ifdef in sext_byte_fill_drops_sext_link()
--
commit 0f3b5c981ef84ecf43731c167adb9d7addf744eb
Author: Vineet Gupta <vineet.gupta@linux.dev>
selftests/bpf: Cover the low-32 link for narrowing stack fills
This commit adds eight BPF verifier selftests covering low-32 scalar link
tracking across narrowing and sign-extending stack fills, and introduces a
CAN_USE_LDSX macro in bpf_misc.h to guard tests that use sign-extending
loads.
> diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
> index 69efe1381eca9..ab78285153fb1 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
[ ... ]
> @@ -1494,6 +1591,215 @@ __naked void sext_drops_stale_step(void)
> : __clobber_all);
> }
[ ... ]
> +/*
> + * BPF_REG_LINK_SEXT says the register is (s32)(base + delta) -- a 32-bit sign
> + * extension specifically. An 8- or 16-bit ldsx is a different relation, so
> + * the exemption that keeps a sign-extending link across a sign-extending
> + * load has to be gated on the load width. Ungated, r2 below claims to be
> + * (s32)r6 when it is really (s8)((s32)r6).
> + */
> +SEC("socket")
> +__success __log_level(2)
> +#ifdef CAN_USE_MOVSX
> +/*
> + * Needs MOVSX as well as LDSX: the BPF_REG_LINK_SEXT under test is built with
> + * r7 = (s32)r6, and only the byte fill below is an ldsx.
> + */
> +/* a surviving link would print as R2=scalar(id=N+0.sx,smin=... */
> +__msg("(91) r2 = *(s8 *)(r10 {{.*}} R2=scalar(smin=")
> +__naked void sext_byte_fill_drops_sext_link(void)
> +{
[ ... ]
> +}
> +#endif /* CAN_USE_MOVSX */
> +
> +#endif /* CAN_USE_LDSX */
> +
> char _license[] SEC("license") = "GPL";
[Severity: Low]
Should SEC("socket") and __success __log_level(2) on
sext_byte_fill_drops_sext_link() be placed inside the #ifdef CAN_USE_MOVSX
block?
In tools/testing/selftests/bpf/progs/bpf_misc.h, CAN_USE_LDSX and
CAN_USE_MOVSX can be enabled independently via __BPF_FEATURE_LDSX and
__BPF_FEATURE_MOVSX (for example, with bpf-gcc -mldsx/-msmov flags).
If CAN_USE_LDSX is defined while CAN_USE_MOVSX is not defined, the body of
the #ifdef CAN_USE_MOVSX block is preprocessed out, leaving those attributes
dangling so they attach to the following _license declaration (or to any test
function added after this block).
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261020161907.2115379-1-vineet.gupta@linux.dev?part=10
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 12/12] [do not merge] selftests/bpf: Cover the low-32 link for narrowing stack spills
2026-10-20 16:19 ` [PATCH bpf-next v3 12/12] [do not merge] selftests/bpf: Cover the low-32 link for " Vineet Gupta
@ 2026-10-20 16:32 ` sashiko-bot
0 siblings, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-20 16:32 UTC (permalink / raw)
To: Vineet Gupta; +Cc: bpf
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [Medium] selftests/bpf: fill before narrow in zext_narrowing_spill_byte_no_link()
- [Medium] selftests/bpf: tautological test in sext_fill_of_narrowing_spill_drops_zext()
- [Low] selftests/bpf: stale inline comment in zext_narrowing_spill_drops_link()
--
commit a341902044eb0b749136bbae6f269759e4c0ffcd
Author: Vineet Gupta <vineet.gupta@linux.dev>
selftests/bpf: Cover the low-32 link for narrowing stack spills
This patch adds six verifier selftests to verifier_linked_scalars.c to test
low-32 register linking behavior across narrowing stack spills and subsequent
fills.
> diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
> index ab78285153fb1..8ade4836e1b2f 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
> @@ -1217,6 +1217,128 @@ __naked void zext_fill_byte_forms_no_link(void)
> : __clobber_all);
> }
>
[ ... ]
> +/*
> + * A narrowing spill stores only the source's low 32 bits, so the slot is their
> + * zero-extension. Filling it back is a mov, though, and that drops the link
> + * for the same reason zext_chain_drops_link does, so a later narrowing of the
> + * source does not reach the filled register.
> + */
> +SEC("socket")
> +__failure
> +__msg("div by zero")
> +__naked void zext_narrowing_spill_drops_link(void)
> +{
> + asm volatile (" \
> + call %[bpf_get_prandom_u32]; \
> + r6 = r0; \
> + call %[bpf_get_prandom_u32]; \
> + r0 <<= 32; \
> + r6 |= r0; /* r6 = full 64-bit unknown */ \
> + *(u32 *)(r10 - 8) = r6; /* narrowing spill, forms the link */ \
> + r2 = *(u32 *)(r10 - 8); /* fill it back */ \
> + if w6 != 0 goto 1f; /* narrows r6, propagates to r2 */ \
[Severity: Low]
This isn't a bug, but is this inline comment in
zext_narrowing_spill_drops_link() left over from the earlier version of the
test? Since the preceding fill into r2 drops BPF_REG_LINK_ZEXT, narrowing w6
here does not propagate to r2.
> + if r2 == 0 goto 1f; \
> + r0 /= 0; \
> +1: \
> + r0 = 0; \
> + exit; \
> +" :
> + : __imm(bpf_get_prandom_u32)
> + : __clobber_all);
> +}
> +
[ ... ]
> +/*
> + * A sub-word spill is below the low-32 model, so no link is formed there.
> + * The fill is a byte load too, so this pins the spill-side and fill-side
> + * size gates together rather than either on its own.
> + */
> +SEC("socket")
> +__failure __msg("div by zero")
> +__naked void zext_narrowing_spill_byte_no_link(void)
> +{
> + asm volatile (" \
> + call %[bpf_get_prandom_u32]; \
> + r6 = r0; \
> + call %[bpf_get_prandom_u32]; \
> + r0 <<= 32; \
> + r6 |= r0; \
> + *(u8 *)(r10 - 8) = r6; /* 1-byte spill: no link */ \
> + r2 = *(u8 *)(r10 - 8); \
> + if w6 != 0 goto 1f; \
> + if r2 == 0 goto 1f; /* not deduced */ \
[Severity: Medium]
Does zext_narrowing_spill_byte_no_link() actually test the size gate in
check_stack_write_fixed_off()?
Here, r2 is filled from fp-8 before w6 is narrowed:
*(u8 *)(r10 - 8) = r6; /* 1-byte spill: no link */
r2 = *(u8 *)(r10 - 8);
if w6 != 0 goto 1f;
As demonstrated by zext_narrowing_spill_drops_link() above, filling a
BPF_REG_LINK_ZEXT slot into r2 before narrowing w6 drops the zero-extending
link on the fill, so narrowing w6 afterwards would not propagate to r2 even if
the 1-byte spill had formed a link.
Should the narrowing branch "if w6 != 0 goto 1f" happen while the value is
still on the stack before filling r2, matching the instruction order in
zext_narrowing_spill_reaches_fill()?
> + r0 /= 0; \
> +1: \
> + r0 = 0; \
> + exit; \
> +" :
> + : __imm(bpf_get_prandom_u32)
> + : __clobber_all);
> +}
> +
> #ifdef CAN_USE_MOVSX
[ ... ]
> @@ -1800,6 +1952,35 @@ __naked void sext_byte_fill_drops_sext_link(void)
> }
> #endif /* CAN_USE_MOVSX */
>
> +/*
> + * The same, with the zero-extending link coming from a narrowing spill rather
> + * than a mov. The spill truncated the slot to 32 bits, so the fill is not
> + * narrowing and assigns no link kind of its own; the slot's zero-extending
> + * one must not survive the sign-extending load.
> + */
> +SEC("socket")
> +__failure __msg("div by zero")
> +__naked void sext_fill_of_narrowing_spill_drops_zext(void)
> +{
> + asm volatile (" \
> + call %[bpf_get_prandom_u32]; \
> + r6 = r0; \
> + call %[bpf_get_prandom_u32]; \
> + r0 <<= 32; \
> + r6 |= r0; /* r6 = full 64-bit unknown */ \
> + *(u32 *)(r10 - 8) = r6; /* narrowing spill: slot is ZEXT */ \
> + r2 = *(s32 *)(r10 - 8); /* sign-extending, not narrowing */ \
> + if w6 != -1 goto 1f; /* slot low 32 bits are all ones */ \
> + if r2 s>= 0 goto 1f; /* taken only if r2 was rebuilt zext */ \
> + r0 /= 0; \
[Severity: Medium]
Can sext_fill_of_narrowing_spill_drops_zext() ever reach the is_ldsx link
clearing in check_mem_access() with BPF_REG_LINK_ZEXT still intact?
In check_stack_write_fixed_off(), the 4-byte narrowing spill
"*(u32 *)(r10 - 8) = r6" truncates fp-8 to 32 bits via
zext_32_to_64(&ss->spilled_ptr) and sets BPF_REG_LINK_ZEXT.
When "r2 = *(s32 *)(r10 - 8)" then runs in check_stack_read_fixed_off(),
get_reg_width(reg) is at most 32, so narrowing is false. Because size == 4,
spill_size == 4, and !narrowing all hold, check_stack_read_fixed_off() calls
assign_scalar_id_before_mov(env, reg) before copying *reg to
state->regs[dst_regno]:
kernel/bpf/verifier.c:check_stack_read_fixed_off() {
...
if (env->bpf_capable && size == 4 &&
(subreg_link || (spill_size == 4 && !narrowing)))
assign_scalar_id_before_mov(env, reg);
state->regs[dst_regno] = *reg;
...
}
And assign_scalar_id_before_mov() immediately clears BPF_REG_LINK_ZEXT and
assigns a fresh scalar ID unlinked from r6:
kernel/bpf/verifier.c:assign_scalar_id_before_mov() {
if (src_reg->link_kind && src_reg->link_kind != BPF_REG_LINK_SEXT)
bpf_clear_scalar_id(src_reg);
if (!src_reg->id && !tnum_is_const(src_reg->var_off))
src_reg->id = ++env->id_gen;
}
So BPF_REG_LINK_ZEXT is already cleared by the normal 4-byte fill path (the
same path tested by zext_narrowing_spill_drops_link()) before the is_ldsx
handling in check_mem_access() runs.
Additionally, even if r2 kept r6's ID and BPF_REG_LINK_ZEXT past
check_mem_access(), coerce_reg_to_size_sx() restricts r2's 64-bit bounds to
[S32_MIN, S32_MAX]. When "if w6 != -1 goto 1f" calls sync_linked_regs(),
rebuilding r2 with zext_32_to_64() yields 0xffffffff, which is disjoint from
[S32_MIN, S32_MAX], causing range_bounds_violation() to revert r2 to its prior
bounds and still hit "r0 /= 0".
> +1: \
> + r0 = 0; \
> + exit; \
> +" :
> + : __imm(bpf_get_prandom_u32)
> + : __clobber_all);
> +}
> +
> #endif /* CAN_USE_LDSX */
>
> char _license[] SEC("license") = "GPL";
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261020161907.2115379-1-vineet.gupta@linux.dev?part=12
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs
2026-10-20 16:18 ` [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs Vineet Gupta
@ 2026-10-20 16:39 ` sashiko-bot
2026-10-20 17:09 ` bot+bpf-ci
1 sibling, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-20 16:39 UTC (permalink / raw)
To: Vineet Gupta; +Cc: bpf
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: empty or corrupted range after intersection in sync_linked_regs()
--
commit 05d23d7192de1c6009703f8fbe1537ad78dda89e
Author: Vineet Gupta <vineet.gupta@linux.dev>
bpf: Track low-32 scalar equality across zero-extending movs
This commit extends linked-scalar tracking across zero-extending 32-bit moves
from wide 64-bit source registers using BPF_REG_LINK_ZEXT. Because a wide base
cannot be inverted across all 64 bits, sync_linked_regs() propagates bounds
forward only and intersects the derived bounds with the destination register's
existing state.
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index b9c20a5cc6d6f..6afd718ede647 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -18749,6 +18798,27 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
> if (reg->link_kind == BPF_REG_LINK_ZEXT ||
> known_reg->link_kind == BPF_REG_LINK_ZEXT)
> zext_32_to_64(reg);
> + /*
> + * Intersect rather than overwrite. A BPF_REG_LINK_ZEXT
> + * link over a wide base does not propagate back, so the
> + * base can be wider than what @reg has already proved
> + * about itself; replacing it would lose that.
> + */
> + cnum64_intersect_with(®->r64, prev.r64);
> + cnum32_intersect_with(®->r32, prev.r32);
> + reg->var_off = tnum_intersect(reg->var_off, prev.var_off);
> + /*
> + * An empty intersection means the two sides contradict,
> + * so this path is unreachable. Say nothing rather than
> + * say it with an empty range: reg_bounds_sync() below
> + * refuses to touch one, and the first later
> + * reg_bounds_sanity_check() would report it as a
> + * verifier bug, which it is not. Keeping the wider
> + * pre-intersect state only costs precision on a path
> + * that cannot be taken.
> + */
> + if (range_bounds_violation(reg))
> + *reg = prev;
> reg_bounds_sync(reg);
> }
> if (e->is_reg)
[Severity: Medium]
Can a contradiction in var_off or linear step still leave an empty range on
reg, or corrupt reg into a bogus constant, after sync_linked_regs() finishes?
First, tnum_intersect() in kernel/bpf/tnum.c assumes its arguments overlap:
/* Note that if a and b disagree - i.e. one has a 'known 1' where the other has
* a 'known 0' - this will return a 'known 1' for that bit.
*/
struct tnum tnum_intersect(struct tnum a, struct tnum b)
{
u64 v, mu;
v = a.value | b.value;
mu = a.mask & b.mask;
return TNUM(v & ~mu, mu);
}
When reg->var_off and prev.var_off disagree on a known bit without
tnum_overlap(reg->var_off, prev.var_off) being checked first, tnum_intersect()
turns the conflicting bit into a known 1.
Second, range_bounds_violation(reg) only checks cnum32_is_empty(reg->r32) ||
cnum64_is_empty(reg->r64), and is only called before reg_bounds_sync(reg). Any
contradiction between the intersected r64/r32 ranges and var_off (via
__update_reg_bounds()) or base/step (via __update_bounds_from_step()) happens
inside reg_bounds_sync(reg), after the range_bounds_violation(reg) check has
already passed.
For example, in a socket filter:
w7 = w6; /* r6 is unknown 64-bit; r7 gets BPF_REG_LINK_ZEXT */
if w7 < 4 goto out;
if w7 > 5 goto out;
if w7 & 2 goto out; /* r7: r64=[4, 5], var_off=(0x4; 0x1) */
if r6 & 2 goto l1;
At l1, r6 has var_off=(0x2; ~2ULL), so after zext_32_to_64(reg), reg has
r64=[2, U32_MAX] and var_off=(0x2; 0xfffffffd). Intersecting r64 and r32 with
prev produces [4, 5], which is non-empty, so range_bounds_violation(reg) is
false. However, tnum_intersect() produces (0x6; 0x1) ([6, 7]), and
reg_bounds_sync(reg) then intersects [4, 5] with [6, 7], leaving reg->r64 and
reg->r32 empty and triggering a verifier warning on a subsequent r7 %= r9 (with
r9 = 0).
Worse, if w7 was narrowed to a single constant 4 (r64=[4, 4],
var_off=(0x4; 0x0)) before "if r6 & 2 goto l1", tnum_intersect() fabricates
the constant var_off=(0x6; 0x0). Inside
reg_bounds_sync()->__update_reg_bounds()->__update_reg64_bounds():
cnum64_intersect_with(®->r64, cnum64_from_tnum(reg->var_off));
/* Check if u64 and tnum overlap in a single value */
tnum_next = tnum_step(reg->var_off, reg_umin(reg));
umin_in_tnum = (reg_umin(reg) & ~reg->var_off.mask) == reg->var_off.value;
tmax = reg->var_off.value | reg->var_off.mask;
if (umin_in_tnum && tnum_next > reg_umax(reg)) {
___mark_reg_known(reg, reg_umin(reg));
} else if (!umin_in_tnum && tnum_next == tmax) {
___mark_reg_known(reg, tmax);
}
cnum64_intersect_with() sets reg->r64 to CNUM64_EMPTY, where reg_umin(reg)
returns 0 and reg_umax(reg) returns U64_MAX. That satisfies !umin_in_tnum &&
tnum_next == tmax (6 == 6) and calls ___mark_reg_known(reg, 6), overwriting
r7 == 4 with the contradicted constant r7 == 6.
Even when tnum_overlap(reg->var_off, prev.var_off) holds, reg_bounds_sync(reg)
can still empty r64/r32 if the intersected cnum range and intersected tnum (or
base/step in __update_bounds_from_step()) have no common points.
Should sync_linked_regs() verify tnum_overlap(reg->var_off, prev.var_off)
before calling tnum_intersect(), and also check range_bounds_violation(reg)
after reg_bounds_sync(reg) to restore *reg = prev?
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261020161907.2115379-1-vineet.gupta@linux.dev?part=4
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills
2026-10-20 16:19 ` [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills Vineet Gupta
@ 2026-10-20 16:42 ` sashiko-bot
0 siblings, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-20 16:42 UTC (permalink / raw)
To: Vineet Gupta; +Cc: bpf
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: zext_32_to_64() on 4-byte spill loses signed bounds on ldsx fill
--
commit b63f0039bbb8ede3ae56c9d69df1283e246bde61
Author: Vineet Gupta <vineet.gupta@linux.dev>
bpf: Track low-32 scalar equality across narrowing stack spills
This patch tracks low-32 scalar equality across 4-byte narrowing stack
spills by assigning a scalar ID, truncating the spilled slot with
zext_32_to_64(), and setting link_kind to BPF_REG_LINK_ZEXT.
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 083b5bd70d3fa..de2a5c048a29a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -3927,15 +3928,46 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
> mark_stack_slot_scratched(env, spi);
> if (reg && !(off % BPF_REG_SIZE) && reg->type == SCALAR_VALUE && env->bpf_capable) {
> bool reg_value_fits;
> + bool subreg_link;
>
> reg_value_fits = get_reg_width(reg) <= BITS_PER_BYTE * size;
> + /*
> + * A narrowing spill stores the low 32 bits of the source, so
> + * the slot is their zero-extension: record a low-32 link
> + * rather than dropping the relation, as a 32-bit mov does.
> + * A store never sign-extends, so there is only one link kind here.
> + */
> + subreg_link = !reg_value_fits && size == 4;
> +
> /* Make sure that reg had an ID to build a relation on spill. */
> - if (reg_value_fits)
> + if (reg_value_fits || subreg_link)
> assign_scalar_id_before_mov(env, reg);
> save_register_state(env, state, spi, reg, size);
> - /* Break the relation on a narrowing spill. */
> - if (!reg_value_fits)
> - bpf_clear_scalar_id(&ss->spilled_ptr);
> + if (!reg_value_fits) {
> + if (subreg_link && reg->id) {
> + /*
> + * save_register_state() copies the source
> + * whole, but the store only wrote its low 32
> + * bits, so truncate to those before recording
> + * the kind: a slot asserting BPF_REG_LINK_ZEXT
> + * over the source's wider bounds is a register
> + * state that contradicts itself.
> + *
> + * Keep the source's delta, though: the slot
> + * holds (u32)(base + delta), so resetting it to
> + * 0 would record a relation off by that delta.
> + */
> + zext_32_to_64(&ss->spilled_ptr);
> + ss->spilled_ptr.link_kind = BPF_REG_LINK_ZEXT;
[Severity: Medium]
Does calling zext_32_to_64() on ss->spilled_ptr cause a precision
regression when the 4-byte slot is subsequently filled by a sign-extending
load (ldsx)?
When spilling a scalar register whose signed range straddles zero (for
example [-10, 10], where reg_umax(reg) is U64_MAX and get_reg_width(reg)
is 64) with a 4-byte store (*(u32 *)(r10 - 8) = rX), subreg_link is true
and zext_32_to_64(&ss->spilled_ptr) is called:
static void zext_32_to_64(struct bpf_reg_state *reg)
{
reg_step_check_unsigned(reg, 32);
reg->var_off = tnum_subreg(reg->var_off);
reg_set_urange64(reg, reg_u32_min(reg), reg_u32_max(reg));
}
Because r32 = [-10, 10] straddles zero in unsigned 32-bit arithmetic
(u32_min = 0, u32_max = 0xffffffff), zext_32_to_64() overwrites
ss->spilled_ptr.r64 with [0, 0xffffffff] while leaving [-10, 10] only in
r32.
If the slot is then reloaded with a sign-extending load (*(s32 *)(r10 - 8),
*(s16 *)(r10 - 8), or *(s8 *)(r10 - 8)), check_stack_read_fixed_off()
copies ss->spilled_ptr to the destination register and check_mem_access()
calls coerce_reg_to_size_sx():
static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)
{
...
/* If every value fits the signed N-bit range sign extension is a noop. */
if (reg_smin(reg) >= -limit && reg_smax(reg) < limit)
return;
Because coerce_reg_to_size_sx() inspects reg_smin(reg) and reg_smax(reg)
from r64 rather than r32, smax is 0xffffffff (>= limit), so the early
return no longer triggers and coerce_reg_to_size_sx() falls through to
set_sext64_default_val(), resetting both r64 and r32 to [S32_MIN, S32_MAX]
(or the full S16/S8 range).
> + } else {
> + /*
> + * Nothing to relate: either the source has no
> + * id to share, or the store is narrower than
> + * the 32 bits a link can describe.
> + */
> + bpf_clear_scalar_id(&ss->spilled_ptr);
> + }
> + }
> } else if (!reg && !(off % BPF_REG_SIZE) && is_bpf_st_mem(insn) &&
> env->bpf_capable) {
> struct bpf_reg_state *tmp_reg = &env->fake_reg[0];
[ ... ]
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261020161907.2115379-1-vineet.gupta@linux.dev?part=11
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for narrowing stack fills
2026-10-20 16:19 ` [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
2026-10-20 16:29 ` sashiko-bot
@ 2026-10-20 16:52 ` bot+bpf-ci
1 sibling, 0 replies; 25+ messages in thread
From: bot+bpf-ci @ 2026-10-20 16:52 UTC (permalink / raw)
To: vineet.gupta, 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, ast, andrii, daniel, martin.lau, eddyz87,
yonghong.song, mason, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 4456 bytes --]
> selftests/bpf: Cover the low-32 link for narrowing stack fills
TL;DR: Test issue: sext_fill_does_not_inherit_zext_link appears never to put a
zero-extending link on the stack slot, so it can't distinguish the new
check_mem_access() condition from the old one; its comment and commit message
look inaccurate.
> diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
> index 69efe1381eca..ab78285153fb 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
[ ... ]
> @@ -1494,6 +1591,215 @@ __naked void sext_drops_stale_step(void)
[ ... ]
> +/*
> + * A sign-extending fill must not come away with a zero-extending link. The
> + * slot below already fits 32 bits, so the fill is not narrowing and assigns
> + * no link kind of its own, and "state->regs[dst] = *reg" copies the slot's
> + * verbatim; check_mem_access() is what has to drop it, since it would leave
> + * r2 recording a zero-extension of a value it has just sign-extended.
> + * Asserted on the register dump rather than on a guarded branch, so it pins
> + * the rule itself and not a downstream effect.
> + */
> +SEC("socket")
> +__success __log_level(2)
> +/* a copied link would print as R2=scalar(id=N+0,smin=... */
> +__msg("(81) r2 = *(s32 *)(r10 {{.*}} R2=scalar(smin=")
> +__naked void sext_fill_does_not_inherit_zext_link(void)
> +{
> + asm volatile (" \
> + call %[bpf_get_prandom_u32]; \
> + r6 = r0; \
> + call %[bpf_get_prandom_u32]; \
> + r0 <<= 32; \
> + r6 |= r0; /* r6 = full 64-bit unknown */ \
> + w7 = w6; /* r7 = zext32(r6), fits 32 bits */ \
> + *(u64 *)(r10 - 8) = r7; \
Does this test ever put a zero-extending link on the slot?
The w7 = w6 above does give r7 BPF_REG_LINK_ZEXT, but the spill that follows
clears it. In check_stack_write_fixed_off(), r7 fits in 32 bits, so
assign_scalar_id_before_mov() runs before save_register_state():
if (src_reg->link_kind && src_reg->link_kind != BPF_REG_LINK_SEXT)
bpf_clear_scalar_id(src_reg);
...
if (!src_reg->id && !tnum_is_const(src_reg->var_off))
src_reg->id = ++env->id_gen;
The slot ends up with a fresh id and link_kind == BPF_REG_LINK_NONE. The
4-byte ldsx is not narrowing, so the fill copies a plain id, and
check_mem_access() drops it through the existing !no_sext clear. The
link_kind == BPF_REG_LINK_SEXT part of the new condition never sees a ZEXT
kind here.
This leaves two problems.
First, the in-test comment looks wrong:
/* a copied link would print as R2=scalar(id=N+0,smin=... */
print_reg_state() prints +delta only when link_kind is set, so a surviving
plain id would print as R2=scalar(id=N,smin=...
Second, the commit message says "The last two pin the link-kind checks in
check_mem_access()", but this test cannot tell the new check from the old
one. It passes with the pre-series:
if (!no_sext)
bpf_clear_scalar_id(...)
It also passes with a relaxed condition such as:
!(size == 4 && regs[value_regno].link_kind != BPF_REG_LINK_NONE)
which would let a ZEXT link survive a sign-extending fill.
At this commit no spill/fill sequence appears able to bring a
BPF_REG_LINK_ZEXT kind into the ldsx arm at all. Spills strip every non-SEXT
kind via assign_scalar_id_before_mov(), and a 4-byte fill of a 4-byte slot
does the same on the slot. A narrower fill goes through the narrowing arm
instead.
That holds even after 3649346488fc ("bpf: Track low-32 scalar equality across
narrowing stack spills"), because the fill-side
assign_scalar_id_before_mov(reg) clears the slot's new ZEXT kind before the
copy. No later commit in the range (3649346488fc, 73fbac05c8bd) changes this
test.
Should the comment, the test name and the commit message describe what is
actually pinned here (a plain id dropped across a range-changing 4-byte
ldsx)? Or should the test be reworked once a ZEXT-carrying slot is
reachable?
> +"
> +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
> +" r2 = *(s32 *)(r10 - 8); /* sign-extending, not narrowing */ \
> +"
> +#else
> +" r2 = *(s32 *)(r10 - 4); \
> +"
[ ... ]
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/39458500836
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 05/12] selftests/bpf: Cover the low-32 link for zero-extending movs
2026-10-20 16:19 ` [PATCH bpf-next v3 05/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
@ 2026-10-20 16:53 ` bot+bpf-ci
0 siblings, 0 replies; 25+ messages in thread
From: bot+bpf-ci @ 2026-10-20 16:53 UTC (permalink / raw)
To: vineet.gupta, 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, ast, andrii, daniel, martin.lau, eddyz87,
yonghong.song, mason, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 5759 bytes --]
> selftests/bpf: Cover the low-32 link for zero-extending movs
TL;DR:
- Selftest comment calls the mixed-kind no-sync case unsound, but the program
is safe; it is only lost precision
- Commit message says "Twelve" programs, but there are thirteen
> selftests/bpf: Cover the low-32 link for zero-extending movs
>
> Twelve programs, one per decision the previous patch makes:
>
> - zext_mov_narrow_src: narrowing the source reaches the destination
> - zext_sync_makes_member_const: and over all 64 bits, since the member
> is the zero-extension
> - zext_narrow_dst_keeps_base: the reverse must not happen
> - zext_u32_src_is_full_link: a provably-u32 source still propagates
> - zext_self_mov_no_link: a self-mov mints no id
> - zext_chain_drops_link: a second 32-bit mov drops the link
> - zext_no_sync_between_mixed_kinds: differing kinds do not reach each
> other, in either direction
> - zext_no_sync_from_subreg_base: nor does a member reach a base whose
> high half it knows nothing about
> - zext_sync_between_two_subregs: two low-32 links on one base do
> - zext_unlinked_path_stays_reachable: one unlinked path keeps the
> guarded div reachable
> - zext_mov_breaks_linked_src: forming the link drops the source's own
> - zext_sync_keeps_narrower_member: narrowing the base does not widen a
> member that already proved itself tighter
> - zext_contradiction_keeps_range_sane: a contradiction leaves no empty
> range behind, under BPF_F_TEST_REG_INVARIANTS so the violation is a
> load failure rather than something only dmesg sees
>
> Written in asm so the bytecode is the same whichever compiler built the
> suite.
>
> Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
The changelog says "Twelve programs", but the list below it has thirteen
bullets, and the patch adds thirteen programs:
zext_mov_narrow_src, zext_sync_makes_member_const,
zext_contradiction_keeps_range_sane, zext_narrow_dst_keeps_base,
zext_u32_src_is_full_link, zext_self_mov_no_link, zext_chain_drops_link,
zext_no_sync_between_mixed_kinds, zext_no_sync_from_subreg_base,
zext_sync_between_two_subregs, zext_sync_keeps_narrower_member,
zext_unlinked_path_stays_reachable and zext_mov_breaks_linked_src.
The count looks like it was not updated when
zext_contradiction_keeps_range_sane was added. It is the last bullet, but the
third program in the file. Should "Twelve" be "Thirteen"?
> diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
> --- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
[ ... ]
> @@ -710,4 +710,352 @@ l_exit_%=: \
[ ... ]
> +/*
> + * Two members of one id set carrying different link kinds do not propagate
> + * to each other: r7 is (u32)base and r8 is base + 3, and the deltas were
> + * added at different ALU widths, so narrowing r8 says nothing about r7.
> + * sync_linked_regs() declines the pair on the kinds before the deltas are
> + * ever consulted. Note neither register is the base -- that is r6.
> + */
> +SEC("socket")
> +__failure __msg("div by zero")
> +__naked void zext_no_sync_between_mixed_kinds(void)
> +{
> + asm volatile (" \
> + call %[bpf_get_prandom_u32]; \
> + r6 = r0; \
> + w7 = w6; /* forms the link */ \
> + r8 = r6; \
> + r8 += 3; /* r8 is BPF_REG_LINK_FULL, r7 is BPF_REG_LINK_ZEXT */ \
> + if r8 != 3 goto 1f; /* must not propagate to r7 */ \
> + if w7 == 0 goto 1f; \
> + r0 /= 0; \
> +1: \
> + r0 = 0; \
> + exit; \
> +" :
> + : __imm(bpf_get_prandom_u32)
> + : __clobber_all);
> +}
^^^^
This isn't a bug, but is the comment accurate for this direction? It says
narrowing r8 "says nothing about r7", and the asm comment says the narrowing
"must not propagate to r7".
r8 is a BPF_REG_LINK_FULL member, so r8 == r6 + 3 over all 64 bits. That
relation inverts exactly, so knowing r8 pins the base, and r7 == (u32)(r8 - 3)
follows.
In this program the fall-through of "if r8 != 3 goto 1f" forces r6 == 0, so
r7 == 0, "if w7 == 0 goto 1f" is always taken, and "r0 /= 0" cannot be reached
at runtime. The program is safe. The verifier rejects it only because
sync_linked_regs() skips every pair with differing kinds:
if (reg->link_kind && known_reg->link_kind &&
reg->link_kind != known_reg->link_kind)
continue;
That check exists for the other direction, a ZEXT known_reg against a FULL
member (scalars_alu32_alu64_cross_type), where the 32-bit wrap really does
break the relation. If the differencing arm ran for known=r8 (FULL, delta 3)
and reg=r7 (ZEXT, delta 0), it would compute r8 + (0 - 3) and then
zext_32_to_64(), which gives exactly (u32)(r8 - 3). That is sound.
So this test pins a deliberate loss of precision, not a soundness requirement,
but the comment presents it as unsound. The text is unchanged at the tip of
the series. Someone who later makes the verifier propagate FULL -> ZEXT will
see this test fail, and the comment will suggest the improvement is wrong.
zext_chain_drops_link and zext_mov_breaks_linked_src also reject runtime-safe
programs, but their comments say the link is dropped by rule. Could this one
be worded the same way, for example "sync_linked_regs() declines mixed kinds
even where, as here, the relation would hold"?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/39458500836
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction
2026-10-20 16:19 ` [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction Vineet Gupta
@ 2026-10-20 16:53 ` bot+bpf-ci
2026-10-20 17:20 ` sashiko-bot
1 sibling, 0 replies; 25+ messages in thread
From: bot+bpf-ci @ 2026-10-20 16:53 UTC (permalink / raw)
To: vineet.gupta, 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, ast, andrii, daniel, martin.lau, eddyz87,
yonghong.song, mason, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 8132 bytes --]
> bpf: Recover the low 32 bits on the reverse link direction
TL;DR:
- New sync_linked_regs() arm may intersect contradictory 32-bit ranges to
empty, triggering verifier bug WARN or -EFAULT on valid programs; no prev
restore
- Comment on width split is inaccurate (nit)
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -18785,29 +18785,54 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
> if (reg->id != known_reg->id)
> continue;
> /*
> - * The reverse direction does not work for a narrow known_reg:
> - * it knows only its low 32 bits, which say nothing about a
> - * wider reg's high half. Neither (u32)(base + delta) nor
> - * (s32)(base + delta) inverts once the base is wider than 32
> - * bits.
> + * The reverse direction, from a narrow known_reg to a wider
> + * reg, does not invert: neither (u32)(base + delta) nor
> + * (s32)(base + delta) says anything about the base's high
> + * half. It does still pin the low half, though -- both sides
> + * are (base + delta) mod 2^32, differing only by their deltas
> + * -- so recover that much and leave the high half alone.
> */
> if ((known_reg->link_kind == BPF_REG_LINK_ZEXT ||
> known_reg->link_kind == BPF_REG_LINK_SEXT) &&
> reg->link_kind != BPF_REG_LINK_ZEXT &&
> reg->link_kind != BPF_REG_LINK_SEXT &&
> - get_reg_width(reg) > 32)
> - continue;
> + get_reg_width(reg) > 32) {
> + /*
> + * Only @low's 32-bit half is meaningful: its var_off
> + * is advanced over all 64 bits while r64 and the
> + * base/step line are not, and nothing below reads
> + * either. It is a scratch value, not a register state.
> + */
> + struct bpf_reg_state low = *known_reg;
> + struct tnum low32;
> +
> + fake_reg.type = SCALAR_VALUE;
> + __mark_reg_known(&fake_reg,
> + (s64)reg->delta - (s64)known_reg->delta);
> + scalar32_min_max_add(&low, &fake_reg);
> + low.var_off = tnum_add(low.var_off, fake_reg.var_off);
> +
> + cnum32_intersect_with(®->r32, low.r32);
> + low32 = tnum_intersect(tnum_subreg(reg->var_off),
> + tnum_subreg(low.var_off));
> + reg->var_off = tnum_with_subreg(reg->var_off, low32);
> + reg_bounds_sync(reg);
> + goto scratched;
> + }
Can the cnum32_intersect_with(®->r32, low.r32) above produce an empty
range here?
The differencing arm further down in sync_linked_regs() saves prev and
guards against exactly that:
struct bpf_reg_state prev = *reg;
...
if (range_bounds_violation(reg))
*reg = prev;
reg_bounds_sync(reg);
Its comment explains that an empty intersection means the two sides
contradict, that reg_bounds_sync() refuses to touch an empty range, and that
the first later reg_bounds_sanity_check() would report it as a verifier bug.
The new arm has no such fallback, so reg_bounds_sync() returns early on the
empty r32, and tnum_intersect() of two contradicting constants gives an
arbitrary const subreg.
A contradiction looks reachable because the wide base can know more about
its low half than a ZEXT/SEXT member does. FULL against ZEXT/SEXT and ZEXT
against SEXT pairs are skipped by the link_kind check:
if (reg->link_kind && known_reg->link_kind &&
reg->link_kind != known_reg->link_kind)
continue;
but the base learns from every member: from a FULL one through the
differencing arm, and now from a ZEXT or SEXT one through this arm. For
example (cpuv4, no CAP_BPF delta needed):
call bpf_get_prandom_u32
r6 = r0 /* wide, id N */
w7 = w6 /* r7 ZEXT d0 */
r8 = (s32)r6 /* r8 SEXT d0 */
if w7 != 5 goto 1f /* new arm: r6.r32 = {5}; r8 skipped (SEXT/ZEXT) */
if w8 != 6 goto 1f /* r8 low half unknown -> both paths explored */
r0 = r6 /* fallthrough: new arm r6.r32 = {5} & {6} = EMPTY */
1: r0 = 0; exit
On the fallthrough of "if w8 != 6", r8.r32 is {6}. r6 is still wide, since
after the first sync its r64 is [5, 0xffffffff00000005] and get_reg_width()
returns 64. cnum32_intersect({5,0},{6,0}) returns CNUM32_EMPTY. The
"r0 = r6" mov then reaches reg_bounds_sanity_check(env, ..., "alu") at the
end of check_alu_op() with "range bounds violation", and verifier_bug()
fires BPF_WARN_ONCE. That is a real WARN_ONCE under CONFIG_DEBUG_KERNEL (and
a panic with panic_on_warn), and it logs "verifier bug: REG INVARIANTS
VIOLATION". With BPF_F_TEST_REG_INVARIANTS, which test_loader sets by
default, the load fails with -EFAULT.
The same thing happens with a FULL member in place of the SEXT one
(r8 = r6; r8 += 3; if w8 != 8 ...; if w7 != 6 ...), where both r6 and r8
end up with an empty r32. Before this patch the guard simply did continue
for these pairs, so the program verified cleanly.
This is the case zext_contradiction_keeps_range_sane was written to pin for
the differencing arm. Would saving prev = *reg before the intersection and
restoring it on range_bounds_violation(), as the differencing arm does, work
here?
No later commit in bbd86cb1eea3..73fbac05c8bd touches sync_linked_regs().
The following narrowing fill and spill patches (48dc0496cddb "bpf: Track
low-32 scalar equality across narrowing stack fills" and 3649346488fc "bpf:
Track low-32 scalar equality across narrowing stack spills") only add more
ZEXT/SEXT links that can reach this arm.
> /*
> * Skip a pair of differing kinds. Where BPF_REG_LINK_FULL meets
> - * a 32-bit kind the delta relationship genuinely does not hold:
> - * the deltas were added at different ALU widths.
> - * BPF_REG_LINK_ZEXT against BPF_REG_LINK_SEXT is not that case
> - * -- both are base + delta in the low 32 bits, so narrowing one
> - * really does narrow the other -- but that deduction is
> - * declined on purpose. It makes an int loop counter a fresh
> - * constant on every iteration, so no two iterations prune
> - * against each other and the program runs to the instruction
> - * limit. See sext_no_sync_from_zext_sibling.
> + * a 32-bit kind the delta relationship does not hold over all
> + * 64 bits: the deltas were added at different ALU widths. For a
> + * wide member the low half still relates and the arm above has
> + * already recovered it; a member that fits 32 bits does not
> + * reach that arm and is skipped outright. BPF_REG_LINK_ZEXT
> + * against BPF_REG_LINK_SEXT is not that case -- both are base +
> + * delta in the low 32 bits, so narrowing one really does narrow
> + * the other -- but that deduction is declined on purpose. It
> + * makes an int loop counter a fresh constant on every
> + * iteration, so no two iterations prune against each other and
> + * the program runs to the instruction limit. See
> + * sext_no_sync_from_zext_sibling.
> */
> if (reg->link_kind && known_reg->link_kind &&
> reg->link_kind != known_reg->link_kind)
This comment says that when BPF_REG_LINK_FULL meets a 32-bit kind, a wide
member has already been handled by the arm above and only a member that fits
32 bits is skipped. Is that split by member width accurate?
The arm above only runs when known_reg is the ZEXT/SEXT side and reg is the
NONE/FULL side. In the other direction, known_reg FULL and reg SEXT, the
pair always reaches this continue, and a SEXT member can be wide in the
get_reg_width() sense, since negative (s32) values give a umax up to
U64_MAX.
sext_no_sync_when_base_has_delta is exactly this case: r8 = r6 + 3 is FULL,
r7 = (s32)r6 is SEXT, and "if r8 != 3" narrows nothing in r7. The code
splits by which side is narrow (direction), not by member width.
Could the comment describe it by direction instead, i.e. only a narrow
known_reg reaches the arm above, and a FULL known_reg is skipped against any
32-bit member?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/39458500836
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs
2026-10-20 16:19 ` [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs Vineet Gupta
@ 2026-10-20 16:57 ` sashiko-bot
0 siblings, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-20 16:57 UTC (permalink / raw)
To: Vineet Gupta; +Cc: bpf
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: empty range after reg_bounds_sync() in sync_linked_regs()
--
commit ad01f18c15eb8cfa9a97b984758db9dd254aace2
Author: Vineet Gupta <vineet.gupta@linux.dev>
bpf: Track low-32 scalar equality across sign-extending movs
This commit adds BPF_REG_LINK_SEXT to track low-32 scalar equality across
32-bit sign-extending moves, using sext_32_to_64() and tnum_sext() to
propagate bounds in sync_linked_regs().
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 6afd718ede647..4621b476b206e 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -6090,6 +6090,25 @@ static void zext_32_to_64(struct bpf_reg_state *reg)
> reg_set_urange64(reg, reg_u32_min(reg), reg_u32_max(reg));
> }
>
> +/*
> + * The sign-extending counterpart. Signed bounds carry over directly because
> + * sign extension is monotonic over the signed 32-bit range.
> + */
> +static void sext_32_to_64(struct bpf_reg_state *reg)
> +{
> + /*
> + * See comment at reg_step_check_unsigned(). Sign extension subtracts
> + * 2^32 from every value with bit 31 set, which preserves a residue
> + * mod step only when step divides 2^32, so the line cannot be kept.
> + * The zero-extending twin calls reg_step_check_unsigned(reg, 32) for
> + * the same reason; the unsigned form does not apply here because the
> + * result is not the low 32 bits but the low 32 bits moved.
> + */
> + reg_step_reset(reg);
> + reg->var_off = tnum_sext(reg->var_off, 4);
> + reg_set_srange64(reg, reg_s32_min(reg), reg_s32_max(reg));
> +}
[ ... ]
> @@ -18795,9 +18843,26 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
> 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->link_kind == BPF_REG_LINK_ZEXT ||
> - known_reg->link_kind == BPF_REG_LINK_ZEXT)
> + if (reg->link_kind == BPF_REG_LINK_SEXT) {
> + sext_32_to_64(reg);
> + } else if (reg->link_kind == BPF_REG_LINK_ZEXT ||
> + known_reg->link_kind == BPF_REG_LINK_ZEXT ||
> + known_reg->link_kind == BPF_REG_LINK_SEXT) {
> + /*
> + * Either @reg is itself the zero extension, or
> + * @reg has no 32-bit kind and @known_reg does
> + * -- the reverse direction, where the guard
> + * above has already proved @reg fits 32 bits.
> + * Then @reg is @known_reg's low half with
> + * nothing above it, whichever way @known_reg
> + * filled its own high half, so the zero
> + * extension is the reconstruction for both
> + * kinds. BPF_REG_LINK_FULL is not here on
> + * purpose: it relates all 64 bits and must not
> + * be truncated.
> + */
> zext_32_to_64(reg);
> + }
> /*
> * Intersect rather than overwrite. A BPF_REG_LINK_ZEXT
> * link over a wide base does not propagate back, so the
[Severity: Medium]
Can sync_linked_regs() leave reg with CNUM64_EMPTY and CNUM32_EMPTY after
reg_bounds_sync(), triggering a register invariants violation on the next
instruction that inspects the register?
At the end of the differencing block in sync_linked_regs():
cnum64_intersect_with(®->r64, prev.r64);
cnum32_intersect_with(®->r32, prev.r32);
reg->var_off = tnum_intersect(reg->var_off, prev.var_off);
if (range_bounds_violation(reg))
*reg = prev;
reg_bounds_sync(reg);
range_bounds_violation(reg) is only checked before reg_bounds_sync(reg),
and tnum_intersect() is called without checking tnum_overlap(). When a
contradiction occurs across domains (between r64, r32, and var_off) rather
than within r64 or r32 individually, the pre-sync range_bounds_violation()
check passes, and reg_bounds_sync(reg) then turns the cross-domain
disjointness into CNUM64_EMPTY / CNUM32_EMPTY without restoring prev.
This can be triggered in two ways with BPF_REG_LINK_SEXT:
1. Cross-domain contradiction between r64 and r32 via sext_32_to_64():
Suppose r6 is a 64-bit unknown scalar and r7 = (s32)r6 links r7 to r6
with BPF_REG_LINK_SEXT.
- Narrow r7 with signed 64-bit jumps to [-0x7ffffff0, 0x7ffffff0], so
r7.r64 is [-0x7ffffff0, 0x7ffffff0] and r7.r32 is the arc
[0x80000010, 0x7ffffff0].
- Execute if w6 < 0x7ffffff0 goto out. Because [0x7ffffff0, 0xffffffff]
and [0x80000010, 0x7ffffff0] overlap in two disjoint arcs,
cnum32_intersect() over-approximates by keeping the smaller arc
[0x7ffffff0, 0xffffffff] for r6.r32 and r7.r32, while r7.r64 remains
[-0x7ffffff0, 0x7ffffff0].
- Execute if w6 != w8 goto out where w8 has r32 = [0x7ffffff8, 0x80000007].
- In sync_linked_regs() for r7, reg->r32 is [0x7ffffff8, 0x80000007],
which straddles S32_MAX / S32_MIN. sext_32_to_64(reg) sets reg->r64 to
[S32_MIN, S32_MAX].
- Intersecting reg->r64 with prev.r64 gives [-0x7ffffff0, 0x7ffffff0]
(non-empty) and intersecting reg->r32 with prev.r32 gives
[0x7ffffff8, 0x80000007] (non-empty).
- range_bounds_violation(reg) is false, so *reg = prev is skipped.
- reg_bounds_sync(reg) calls deduce_bounds_32_from_64(reg), which
intersects [0x7ffffff8, 0x80000007] with [0x80000010, 0x7ffffff0] and
leaves reg->r32 = CNUM32_EMPTY and reg->r64 = CNUM64_EMPTY.
2. Contradiction between var_off and r64/r32 via tnum_intersect():
Suppose r6 is a 64-bit unknown scalar, r7 = (s32)r6, and r7 is narrowed
to [-4, 3].
- Execute if w6 & 8 goto out. On the fallthrough branch,
regs_refine_cond_op() calls __mark_reg_unbounded(&r6) and clears bit 3
in var_off; sync_linked_regs() narrows r7 to [0, 3] with
var_off = TNUM(0, 3).
- Execute if w6 & 4 goto target. On the taken branch, r6 gets low-32
var_off = TNUM(4, 0xfffffff3) and r32 = [-0x7ffffffc, 0x7ffffff7].
- In sync_linked_regs() on r7, cnum64_intersect_with() and
cnum32_intersect_with() both produce [0, 3] (non-empty), while
tnum_intersect() without a tnum_overlap() check combines
TNUM(4, 0xfffffffffffffff3) and TNUM(0, 3) into TNUM(4, 3) ([4, 7]).
- range_bounds_violation(reg) is false before reg_bounds_sync(reg), and
__update_reg_bounds() inside reg_bounds_sync(reg) then intersects
[0, 3] with [4, 7], leaving r7 with CNUM32_EMPTY and CNUM64_EMPTY.
Should sync_linked_regs() check !tnum_overlap(reg->var_off, prev.var_off)
and also check range_bounds_violation(reg) after reg_bounds_sync(reg) before
committing the updated state?
> /*
> * Intersect rather than overwrite. A BPF_REG_LINK_ZEXT
> * link over a wide base does not propagate back, so the
[ ... ]
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261020161907.2115379-1-vineet.gupta@linux.dev?part=6
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits
2026-10-20 16:18 ` [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits Vineet Gupta
@ 2026-10-20 17:08 ` bot+bpf-ci
0 siblings, 0 replies; 25+ messages in thread
From: bot+bpf-ci @ 2026-10-20 17:08 UTC (permalink / raw)
To: vineet.gupta, 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, ast, andrii, daniel, martin.lau, eddyz87,
yonghong.song, mason, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 3905 bytes --]
> bpf: Prepare linked scalars for relations narrower than 64 bits
TL;DR: Commit message only: regs_exact() now also rejects states whose linked
scalars share a base id in old but not in cur, a stricter infinite-loop check
the changelog doesn't mention.
> bpf: Prepare linked scalars for relations narrower than 64 bits
>
> Two scalars sharing an ->id are always related by full 64-bit equality
> today: reg == base + delta over all 64 bits (this is true for
> BPF_ADD_CONST32 as well, which implies upper bits to be all zero).
> Sign-extension needs a genuinely low32 equal only relationship kind
> with bit 31 supplying upper 32-bits.
>
> Today the following 2 relationships exist
>
> #define BPF_ADD_CONST64 (1U << 31)
> #define BPF_ADD_CONST32 (1U << 30)
>
> Model them differently as
>
> enum bpf_reg_link_kind { BPF_REG_LINK_NONE, BPF_REG_LINK_FULL,
> BPF_REG_LINK_ZEXT, BPF_REG_LINK_SEXT };
>
> So BPF_ADD_CONST64 becomes BPF_REG_LINK_FULL and BPF_ADD_CONST32 becomes
> BPF_REG_LINK_ZEXT with the exact same semantics as today. But this paves
> the way for a future BPF_REG_LINK_SEXT in the same framework.
>
> The implementation needs to change as well. Today the above 2 bits are
> shoe-horned into ->id, needing masking and OR'ing to get ->id and kind
> bits: with more types and bits needed, move them out into an enum
> bitfield of its own. To avoid growing the storage (and stay within the
> 1K allocator bucket), borrow 2 bits out of ->map_uid, 31 -> 29, which is
> still far more ids than a program can generate.
>
> ->id becomes a plain identifier, so check_scalar_ids() loses its "compare
> the compound id, then the base id" dance in favour of one check_ids().
>
> With the kind out of ->id it also leaves the idmap key, so regs_exact()
> and regsafe()'s explore_alu_limits arm have to compare it explicitly.
>
> One case changes behaviour -- old {r2.id=A+delta32} against
> cur {r2.id=B+delta64} was accepted and is now rejected, correctly, since
> alu32 and alu64 deltas diverge in sync_linked_regs().
>
> Clearing a link is no longer just ->id = 0: any stale ->link_kind needs
> to be cleared out as well. And given this needs to be done in the newly
> added kernel/bpf/scev.c, it is moved into bpf_verifier.h as
> bpf_clear_scalar_id().
>
> The helper also zeroes ->delta, which the open-coded clear left behind.
> Unlike ->id that field is inside the memcmp() prefix state comparison
> uses, so a leftover value could keep two otherwise-identical states
> apart; clearing it can only help pruning.
>
> Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
> Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
The changelog lists only the delta32/delta64 mismatch as a case that changes
behaviour. Is that the only one?
regs_exact() also changes. It used to run check_ids() on the compound id,
so old {r2.id=A, r3.id=A|BPF_ADD_CONST64} against cur {r2.id=B,
r3.id=C|BPF_ADD_CONST64} built two independent idmap entries (A->B and
A|flag->C|flag) and was accepted as exact.
With the kind moved out of ->id, the same pair now maps A->B and then A->C,
and check_ids() rejects it:
return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
rold->link_kind == rcur->link_kind &&
check_ids(rold->id, rcur->id, idmap) && ...
regs_exact() is reached through regsafe(..., EXACT) from the infinite loop
check in bpf_is_state_visited():
states_equal(env, &sl->state, cur, EXACT)
so this is a stricter comparison than before.
Could the changelog also say that regs_exact() now enforces base-id
consistency for linked scalars, which the old compound-id idmap key did not?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/39458500836
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs
2026-10-20 16:18 ` [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs Vineet Gupta
2026-10-20 16:39 ` sashiko-bot
@ 2026-10-20 17:09 ` bot+bpf-ci
1 sibling, 0 replies; 25+ messages in thread
From: bot+bpf-ci @ 2026-10-20 17:09 UTC (permalink / raw)
To: vineet.gupta, 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, ast, andrii, daniel, martin.lau, eddyz87,
yonghong.song, mason, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 3081 bytes --]
> bpf: Track low-32 scalar equality across zero-extending movs
TL;DR: The comment and changelog claim a zero delta from an add is refused
composition, but a 32-bit add of known zero records the same link as the mov
and composes. Behaviour is sound; the explanation looks inaccurate.
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -17594,11 +17584,28 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
>
> if (dst_reg->link_kind) {
> /*
> - * If the register already went through rX += val
> - * we cannot accumulate another val into rx->off.
> + * Only the zero-extending link the mov above records,
> + * BPF_REG_LINK_ZEXT with delta 0, can take a delta:
> + * (u32)((u32)(base + 0) + off) is (u32)(base + off).
> + * The add has to be 32-bit as well, since a 64-bit one
> + * parts company with the link once the low half wraps.
> + *
> + * Everything else still drops the link. A zero delta
> + * reached by an add rather than by the mov, say "r1 +=
> + * r3" with r3 known to be 0, has already spent its
> + * delta; composing onto it keeps a link alive across a
> + * loop's increments, and since the delta is compared
> + * for equality, every value the loop reaches becomes a
> + * state of its own and stops pruning.
> */
> + if (dst_reg->link_kind != BPF_REG_LINK_ZEXT || !alu32 ||
> + dst_reg->delta) {
> + /* also the target of the two gotos above */
> clear_id:
> - bpf_clear_scalar_id(dst_reg);
> + bpf_clear_scalar_id(dst_reg);
> + } else {
> + dst_reg->delta = off;
> + }
> } else {
> if (alu32)
> dst_reg->link_kind = BPF_REG_LINK_ZEXT;
The comment says a zero delta "reached by an add rather than by the mov"
has already spent its delta, and the commit message says allowing
composition onto "a zero delta that an add produced rather than the mov
still costs 1176 -> 1196". Can this test actually tell the two apart?
A 32-bit add or sub of a known zero ("w1 += 0", "w1 -= 0", or "w1 += w3"
with w3 known to be 0) on a register that has an id but no link_kind goes
through the else arm quoted above and records:
dst_reg->link_kind = BPF_REG_LINK_ZEXT;
dst_reg->delta = off; /* off == 0 */
That is the same state the mov records, so a following "w1 += 1" passes the
"dst_reg->link_kind != BPF_REG_LINK_ZEXT || !alu32 || dst_reg->delta" test
and composes.
Only the 64-bit example from the comment ("r1 += r3", which records
BPF_REG_LINK_FULL) is actually refused.
The result is still sound, since (u32)((u32)(base + 0) + off) is
(u32)(base + off). Should the comment and the changelog limit the claim to
64-bit adds, or does the mov-produced link need to be made distinguishable
from the add-produced one?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/39458500836
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for narrowing stack fills
2026-10-20 16:29 ` sashiko-bot
@ 2026-10-20 17:15 ` Vineet Gupta
0 siblings, 0 replies; 25+ messages in thread
From: Vineet Gupta @ 2026-10-20 17:15 UTC (permalink / raw)
To: sashiko-reviews; +Cc: bpf
On 10/20/26 9:29 AM, sashiko-bot@kernel.org wrote:
> Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
> - [Low] selftests/bpf: misplaced ifdef in sext_byte_fill_drops_sext_link()
> --
>
> commit 0f3b5c981ef84ecf43731c167adb9d7addf744eb
> Author: Vineet Gupta <vineet.gupta@linux.dev>
>
> selftests/bpf: Cover the low-32 link for narrowing stack fills
>
> This commit adds eight BPF verifier selftests covering low-32 scalar link
> tracking across narrowing and sign-extending stack fills, and introduces a
> CAN_USE_LDSX macro in bpf_misc.h to guard tests that use sign-extending
> loads.
>
>> diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
[snip...]
>> +SEC("socket")
>> +__success __log_level(2)
>> +#ifdef CAN_USE_MOVSX
>> +/*
>> + * Needs MOVSX as well as LDSX: the BPF_REG_LINK_SEXT under test is built with
>> + * r7 = (s32)r6, and only the byte fill below is an ldsx.
>> + */
>> +/* a surviving link would print as R2=scalar(id=N+0.sx,smin=... */
>> +__msg("(91) r2 = *(s8 *)(r10 {{.*}} R2=scalar(smin=")
>> +__naked void sext_byte_fill_drops_sext_link(void)
>> +{
> [ ... ]
>> +}
>> +#endif /* CAN_USE_MOVSX */
>> +
>> +#endif /* CAN_USE_LDSX */
>> +
>> char _license[] SEC("license") = "GPL";
> [Severity: Low]
> Should SEC("socket") and __success __log_level(2) on
> sext_byte_fill_drops_sext_link() be placed inside the #ifdef CAN_USE_MOVSX
> block?
Indeed that bracketing came out weird.
> In tools/testing/selftests/bpf/progs/bpf_misc.h, CAN_USE_LDSX and
> CAN_USE_MOVSX can be enabled independently via __BPF_FEATURE_LDSX and
> __BPF_FEATURE_MOVSX
Independently meaning ? __BPF_FEATURE* are indeed compiler toggle
derived but the CAN_USE* additionally reflect whether arch JITs support
them so they are a combination of __BPF_FEATURE* and arch JIT support.
> (for example, with bpf-gcc -mldsx/-msmov flags).
Just for correctness, -mldsx doesn't exist for gcc, -msmov covers both.
> If CAN_USE_LDSX is defined while CAN_USE_MOVSX is not defined, the body of
> the #ifdef CAN_USE_MOVSX block is preprocessed out, leaving those attributes
> dangling so they attach to the following _license declaration (or to any test
> function added after this block).
Indeed the attribute placement needs fixing.
Thx,
-Vineet
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction
2026-10-20 16:19 ` [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction Vineet Gupta
2026-10-20 16:53 ` bot+bpf-ci
@ 2026-10-20 17:20 ` sashiko-bot
1 sibling, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-20 17:20 UTC (permalink / raw)
To: Vineet Gupta; +Cc: bpf
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: missing contradiction check in sync_linked_regs() reverse-direction arm
--
commit 651910c4895680e635057947cc88b56f4edbf401
Author: Vineet Gupta <vineet.gupta@linux.dev>
bpf: Recover the low 32 bits on the reverse link direction
This commit updates sync_linked_regs() in the BPF verifier to recover the low
32-bit bounds and subreg tnum when propagating from a narrow linked register
(BPF_REG_LINK_ZEXT or BPF_REG_LINK_SEXT) back to a linked register wider than
32 bits.
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 4621b476b206e..ac50252cec1f7 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -18785,29 +18785,54 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
> if (reg->id != known_reg->id)
> continue;
> /*
> - * The reverse direction does not work for a narrow known_reg:
> - * it knows only its low 32 bits, which say nothing about a
> - * wider reg's high half. Neither (u32)(base + delta) nor
> - * (s32)(base + delta) inverts once the base is wider than 32
> - * bits.
> + * The reverse direction, from a narrow known_reg to a wider
> + * reg, does not invert: neither (u32)(base + delta) nor
> + * (s32)(base + delta) says anything about the base's high
> + * half. It does still pin the low half, though -- both sides
> + * are (base + delta) mod 2^32, differing only by their deltas
> + * -- so recover that much and leave the high half alone.
> */
> if ((known_reg->link_kind == BPF_REG_LINK_ZEXT ||
> known_reg->link_kind == BPF_REG_LINK_SEXT) &&
> reg->link_kind != BPF_REG_LINK_ZEXT &&
> reg->link_kind != BPF_REG_LINK_SEXT &&
> - get_reg_width(reg) > 32)
> - continue;
> + get_reg_width(reg) > 32) {
> + /*
> + * Only @low's 32-bit half is meaningful: its var_off
> + * is advanced over all 64 bits while r64 and the
> + * base/step line are not, and nothing below reads
> + * either. It is a scratch value, not a register state.
> + */
> + struct bpf_reg_state low = *known_reg;
> + struct tnum low32;
> +
> + fake_reg.type = SCALAR_VALUE;
> + __mark_reg_known(&fake_reg,
> + (s64)reg->delta - (s64)known_reg->delta);
> + scalar32_min_max_add(&low, &fake_reg);
> + low.var_off = tnum_add(low.var_off, fake_reg.var_off);
> +
> + cnum32_intersect_with(®->r32, low.r32);
> + low32 = tnum_intersect(tnum_subreg(reg->var_off),
> + tnum_subreg(low.var_off));
> + reg->var_off = tnum_with_subreg(reg->var_off, low32);
> + reg_bounds_sync(reg);
> + goto scratched;
> + }
[Severity: Medium]
Can this reverse-direction arm leave reg with an empty range (CNUM32_EMPTY or
CNUM64_EMPTY) or conflicting constant subreg bits when the low-32 bounds,
var_off, or step progression of reg and known_reg contradict on an
unreachable path?
In the sibling differencing arm further down in sync_linked_regs(), the code
saves prev = *reg before intersecting and restores *reg = prev if
range_bounds_violation(reg) holds:
kernel/bpf/verifier.c:sync_linked_regs() {
...
cnum64_intersect_with(®->r64, prev.r64);
cnum32_intersect_with(®->r32, prev.r32);
reg->var_off = tnum_intersect(reg->var_off, prev.var_off);
if (range_bounds_violation(reg))
*reg = prev;
reg_bounds_sync(reg);
}
In the new arm above, cnum32_intersect_with(®->r32, low.r32) and
tnum_intersect() are applied directly without saving prev or checking for
contradictions. If reg->r32 becomes CNUM32_EMPTY, reg_bounds_sync() exits
early on range_bounds_violation(reg), and even when cnum32_intersect_with()
is non-empty, reg_bounds_sync() can still empty reg->r32 or reg->r64 via
__update_reg_bounds(), __reg_deduce_bounds(), or __update_bounds_from_step()
when the narrowed low 32 bits contradict reg's 64-bit bounds, subreg tnum, or
base/step progression. Similarly, if tnum_subreg(reg->var_off) and
tnum_subreg(low.var_off) do not overlap (!tnum_overlap()), tnum_intersect()
ORs conflicting constant bits together.
Contradictions can reach this arm in several ways during check_cond_jmp_op()
-> sync_linked_regs():
1. Mixed link kinds: if r6 is a wide unknown scalar (BPF_REG_LINK_NONE),
w7 = w6 (BPF_REG_LINK_ZEXT), and r8 = r6; r8 += 2 (BPF_REG_LINK_FULL),
narrowing r8 with if w8 != 7 goto out syncs r6->r32 to [5, 5] while
skipping r7 because r7->link_kind != r8->link_kind. A subsequent
if w7 != 9 goto out then enters the new arm for r6 and r8, intersecting
[5, 5] with [9, 9] and [7, 7] with [11, 11] to leave r6->r32 and r8->r32
as CNUM32_EMPTY.
2. Sign-extending mov (BPF_REG_LINK_SEXT): if a wide r6 has its low 32 bits
pinned by if w6 != 5 goto out (so r6->r32 is [5, 5]), r7 = (s32)r6 links
r7 with BPF_REG_LINK_SEXT while coerce_reg_to_size_sx() resets r7->r32 to
[S32_MIN, S32_MAX]. A following if w7 != 8 goto out enters the new arm
and intersects r6->r32 ([5, 5]) with [8, 8].
3. BPF_JSET fallthrough: in regs_refine_cond_op(), the BPF_JSET | BPF_X
fallthrough path calls __mark_reg_unbounded() before masking var_off.
After w7 = w6; if w6 == 0 goto out; (where r6->r32 is [1, U32_MAX]),
if w7 & -1 goto out refines r7 to 0 on fallthrough and syncs back to r6,
intersecting [1, U32_MAX] with [0, 0].
4. Step or tnum conflict inside reg_bounds_sync(): if a wide r6 has step > 1
(for example step == 3) and w7 = w6 resets r7->step to 1 via
zext_32_to_64(), narrowing w7 to a value in r6->r32 that is not a
multiple of 3 passes cnum32_intersect_with() and then becomes empty in
__update_bounds_from_step(r6) at the end of reg_bounds_sync().
When reg is left in this state, any subsequent instruction that checks it via
reg_bounds_sanity_check() triggers verifier_bug() ("range bounds violation"),
emitting a BPF_WARN_ONCE() and returning -EFAULT when
BPF_F_TEST_REG_INVARIANTS is enabled.
Should this arm save struct bpf_reg_state prev = *reg and restore *reg = prev
if !tnum_overlap(tnum_subreg(reg->var_off), tnum_subreg(low.var_off)) or if
range_bounds_violation(reg) is true after reg_bounds_sync(reg)?
[ ... ]
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261020161907.2115379-1-vineet.gupta@linux.dev?part=8
^ permalink raw reply [flat|nested] 25+ messages in thread
end of thread, other threads:[~2026-10-20 17:20 UTC | newest]
Thread overview: 25+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-10-20 16:18 [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 01/12] bpf: Keep the 32-bit range across a sign extension that cannot change it Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 02/12] selftests/bpf: Cover sign extensions that cannot change the range Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits Vineet Gupta
2026-10-20 17:08 ` bot+bpf-ci
2026-10-20 16:18 ` [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs Vineet Gupta
2026-10-20 16:39 ` sashiko-bot
2026-10-20 17:09 ` bot+bpf-ci
2026-10-20 16:19 ` [PATCH bpf-next v3 05/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
2026-10-20 16:53 ` bot+bpf-ci
2026-10-20 16:19 ` [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs Vineet Gupta
2026-10-20 16:57 ` sashiko-bot
2026-10-20 16:19 ` [PATCH bpf-next v3 07/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
2026-10-20 16:19 ` [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction Vineet Gupta
2026-10-20 16:53 ` bot+bpf-ci
2026-10-20 17:20 ` sashiko-bot
2026-10-20 16:19 ` [PATCH bpf-next v3 09/12] bpf: Track low-32 scalar equality across narrowing stack fills Vineet Gupta
2026-10-20 16:19 ` [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
2026-10-20 16:29 ` sashiko-bot
2026-10-20 17:15 ` Vineet Gupta
2026-10-20 16:52 ` bot+bpf-ci
2026-10-20 16:19 ` [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills Vineet Gupta
2026-10-20 16:42 ` sashiko-bot
2026-10-20 16:19 ` [PATCH bpf-next v3 12/12] [do not merge] selftests/bpf: Cover the low-32 link for " Vineet Gupta
2026-10-20 16:32 ` sashiko-bot
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.