bpf: track scalar equality across the low 32 bits
Subsystems (4)
v3 cover bpf: track scalar equality across the low 32 bits
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 -> 9and 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.1Two 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/[email protected]/
RFC:
https://lore.kernel.org/bpf/[email protected]/
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(-)
Signature · 1 line
2.53.0-Meta
PATCH v3 1/12 bpf: Keep the 32-bit range across a sign extension that cannot change it
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.
---
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(+)
kernel/bpf/verifier.c +22 -0
@@ -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 &®_s32_max (reg) <= field_smax) +return ; +/* See comment at reg_step_check_unsigned(). */ reg_step_reset (reg);
Signature · 1 line
2.53.0-Meta
PATCH v3 2/12 selftests/bpf: Cover sign extensions that cannot change the range
In reply to Vineet GuptaTwo 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.
---
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(+)
tools/testing/selftests/bpf/progs/verifier_movsx.c +55 -0
@@ -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) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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_")
Signature · 1 line
2.53.0-Meta
PATCH v3 3/12 bpf: Prepare linked scalars for relations narrower than 64 bits
In reply to Vineet GuptaTwo 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.
---
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(-)
include/linux/bpf_verifier.h +41 -9
@@ -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);
kernel/bpf/log.c +2 -2
@@ -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);
kernel/bpf/scev.c +1 -1
@@ -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 :
kernel/bpf/states.c +12 -26
@@ -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))
kernel/bpf/verifier.c +30 -32
201 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +22 -22
130 lines not on this page · raw message
Signature · 1 line
2.53.0-Meta
PATCH v3 4/12 bpf: Track low-32 scalar equality across zero-extending movs
In reply to Vineet GuptaLinked-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.
---
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(-)
include/linux/bpf_verifier.h +2 -1
@@ -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 ,
kernel/bpf/verifier.c +91 -21
165 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_bounds.c +1 -1
@@ -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 ) {
tools/testing/selftests/bpf/progs/verifier_reg_equal.c +7 -7
@@ -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 ) { asmvolatile (" \ 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; \ " :
Signature · 1 line
2.53.0-Meta
PATCH v3 5/12 selftests/bpf: Cover the low-32 link for zero-extending movs
In reply to Vineet GuptaTwelve 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.
---
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(+)
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +348 -0
@@ -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 ) +{ + asmvolatile (" \ +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 ) +{ + asmvolatile (" \ +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 voidzext_contradiction_keeps_range_sane (void) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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 ) +{ + asmvolatile (" \ +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 ) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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 ) +{ + asmvolatile (" \ +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 ) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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";
Signature · 1 line
2.53.0-Meta
PATCH v3 6/12 bpf: Track low-32 scalar equality across sign-extending movs
In reply to Vineet GuptaA 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.
---
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(-)
include/linux/bpf_verifier.h +2 -1
@@ -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 ,
include/linux/tnum.h +7 -0
@@ -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);
kernel/bpf/log.c +2 -0
@@ -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))
kernel/bpf/tnum.c +15 -0
@@ -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)
kernel/bpf/verifier.c +77 -12
135 lines not on this page · raw message
Signature · 1 line
2.53.0-Meta
PATCH v3 7/12 selftests/bpf: Cover the low-32 link for sign-extending movs
In reply to Vineet GuptaFourteen 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.
---
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(-)
tools/testing/selftests/bpf/progs/bpf_misc.h +8 -0
@@ -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) || \
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +409 -0
419 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_movsx.c +2 -6
@@ -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";
Signature · 1 line
2.53.0-Meta
PATCH v3 8/12 bpf: Recover the low 32 bits on the reverse link direction
In reply to Vineet GuptaA 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:
Quoted 3 lines
- if
known_regis 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.
---
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(-)
kernel/bpf/verifier.c +42 -16
@@ -18521,29 +18521,54 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sif (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
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +38 -9
77 lines not on this page · raw message
Signature · 1 line
2.53.0-Meta
PATCH v3 9/12 bpf: Track low-32 scalar equality across narrowing stack fills
In reply to Vineet GuptaA 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.
---
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(-)
kernel/bpf/verifier.c +49 -11
@@ -4223,7 +4223,8 @@ static void bpf_diag_stack_read_invalid(struct bpf_verifier_env *env, int off, istatic 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 bif (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]); } }
Signature · 1 line
2.53.0-Meta
PATCH v3 10/12 selftests/bpf: Cover the low-32 link for narrowing stack fills
In reply to Vineet GuptaEight 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.
---
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(-)
tools/testing/selftests/bpf/progs/bpf_misc.h +8 -0
@@ -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) || \
tools/testing/selftests/bpf/progs/verifier_ldsx.c +2 -6
@@ -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";
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +306 -0
324 lines not on this page · raw message
Signature · 1 line
2.53.0-Meta
PATCH v3 11/12 bpf: Track low-32 scalar equality across narrowing stack spills
In reply to Vineet GuptaA 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.
---
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(-)
kernel/bpf/verifier.c +36 -4
@@ -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 ];
tools/testing/selftests/bpf/progs/verifier_spill_fill.c +5 -1
@@ -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 )
Signature · 1 line
2.53.0-Meta
PATCH v3 12/12 selftests/bpf: Cover the low-32 link for narrowing stack spills
In reply to Vineet GuptaSix 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.
---
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(+)
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +181 -0
@@ -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 ) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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 ) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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 ) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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";
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for narrowing stack fills
In reply to Vineet GuptaThank 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() --
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 <[email protected]>
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.
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0
[ ... ]
Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0@@ -1494,6 +1591,215 @@ __naked void sext_drops_stale_step(void) : __clobber_all); }
[ ... ]
Quoted 18 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +18
-0+/* +* 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 ) +{
[ ... ]
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_drops_stale_step(void) · line 1805
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +5
-0+} +#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).
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=10
[email protected]
AI reviewRe: [PATCH bpf-next v3 12/12] [do not merge] selftests/bpf: Cover the low-32 link for narrowing stack spills
In reply to Vineet GuptaThank 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]…
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 <[email protected]>
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.
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0@@ -1217,6 +1217,128 @@ __naked void zext_fill_byte_forms_no_link(void) : __clobber_all); }
[ ... ]
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+/* +* 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 )
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void zext_fill_byte_forms_no_link(void) · line 1268
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+{ + 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.
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ if r2 == 0 goto 1f; \ + r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +
[ ... ]
Quoted 9 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +9
-0+/* +* 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 ) +{
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void zext_fill_byte_forms_no_link(void) · line 1332
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ 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()?
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +9
-0+ r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#ifdef CAN_USE_MOVSX
[ ... ]
Quoted 15 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +11
-0@@ -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 (" \
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_byte_fill_drops_sext_link(void) · line 1975
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ 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".
Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +8
-0+1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#endif /* CAN_USE_LDSX */ char _license[] SEC("license") = "GPL";
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=12
[email protected]
AI reviewRe: [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs
In reply to Vineet GuptaThank 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() --
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 <[email protected]>
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.
Quoted 4 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
Quoted 18 lines
kernel/bpf/verifier.c +14
-0@@ -18749,6 +18798,27 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sif (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
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18824
Quoted 10 lines
kernel/bpf/verifier.c +7
-0+* 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?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=4
[email protected]
AI reviewRe: [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills
In reply to Vineet GuptaThank 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 --
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 <[email protected]>
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.
Quoted 4 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
Quoted 29 lines
kernel/bpf/verifier.c +16
-4@@ -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
kernel/bpf/verifier.c static int check_stack_write_fixed_off(struct bpf_verifier_env *env, · line 3961
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* 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).
Quoted 12 lines
kernel/bpf/verifier.c +9
-0+ }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 ];
[ ... ]
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=11
[email protected]
AI reviewRe: [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for narrowing stack fills
In reply to Vineet GuptaTL;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…
Quoted 1 line
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.
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0
[ ... ]
Quoted 1 line
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0@@ -1494,6 +1591,215 @@ __naked void sext_drops_stale_step(void)
[ ... ]
Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +13
-0+/* +* 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=" )
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_drops_stale_step(void) · line 1740
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+__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?
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_drops_stale_step(void) · line 1747
Quoted 7 lines
+"
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +6
-0+#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
[email protected]
AI reviewRe: [PATCH bpf-next v3 05/12] selftests/bpf: Cover the low-32 link for zero-extending movs
In reply to Vineet GuptaTL;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
Quoted 1 line
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
Quoted 25 lines
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, underBPF_F_TEST_REG_INVARIANTSso the violation is a load failure rather than something only dmesg sees
Quoted 4 lines
Written in asm so the bytecode is the same whichever compiler built the suite.
Signed-off-by Vineet Gupta <[email protected]>
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"?
Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0
[ ... ]
Quoted 1 line
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0@@ -710,4 +710,352 @@ l_exit_%=: \
[ ... ]
Quoted 17 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +17
-0+/* +* 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 */ \
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l_exit_%=: \ · line 916
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ 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
[email protected]
AI reviewRe: [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction
In reply to Vineet GuptaTL;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…
Quoted 1 line
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)
Quoted 3 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
Quoted 35 lines
kernel/bpf/verifier.c +19
-7@@ -18785,29 +18785,54 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sif (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);
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18821
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+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.
Quoted 16 lines
kernel/bpf/verifier.c +5
-9/* * 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
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18574
Quoted 10 lines
kernel/bpf/verifier.c +7
-0+* 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
[email protected]
AI reviewRe: [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs
In reply to Vineet GuptaThank 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() --
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 <[email protected]>
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().
Quoted 4 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
Quoted 22 lines
kernel/bpf/verifier.c +18
-0@@ -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)); +}
[ ... ]
Quoted 19 lines
kernel/bpf/verifier.c +13
-2@@ -18795,9 +18843,26 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sscalar32_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
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18868
Quoted 10 lines
kernel/bpf/verifier.c +6
-0+* 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?
Quoted 3 lines
kernel/bpf/verifier.c +0
-0/* * Intersect rather than overwrite. A BPF_REG_LINK_ZEXT * link over a wide base does not propagate back, so the
[ ... ]
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=6
[email protected]
AI reviewRe: [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits
In reply to Vineet GuptaTL;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.
Quoted 1 line
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.
Quoted 44 lines
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 forBPF_ADD_CONST32as 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_CONST64becomesBPF_REG_LINK_FULLandBPF_ADD_CONST32becomesBPF_REG_LINK_ZEXTwith the exact same semantics as today. But this paves the way for a futureBPF_REG_LINK_SEXTin 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 onecheck_ids().With the kind out of ->id it also leaves the idmap key, so
regs_exact()and regsafe()'sexplore_alu_limitsarm 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 intobpf_verifier.hasbpf_clear_scalar_id().
Quoted 7 lines
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 <[email protected]>Signed-off-by Vineet Gupta <[email protected]>
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
[email protected]
AI reviewRe: [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs
In reply to Vineet GuptaTL;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…
Quoted 1 line
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.
Quoted 3 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
Quoted 22 lines
kernel/bpf/verifier.c +15
-2@@ -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) {
kernel/bpf/verifier.c static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, · line 17611
Quoted 10 lines
kernel/bpf/verifier.c +5
-1+/* 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
Re: [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for narrowing stack fills
In reply to [email protected]Quoted 15 lines · On 10/20/26 9:29 AM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Low] selftests/bpf: misplaced ifdef insext_byte_fill_drops_sext_link()--commit
0f3b5c981ef84ecf43731c167adb9d7addf744eb
Author: Vineet Gupta <[email protected]>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_LDSXmacro inbpf_misc.hto guard tests that use sign-extending loads.Quoted 1 line
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0
[snip...]
Quoted 12 lines
Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +11
-0+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 ) +{[ ... ]
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_drops_stale_step(void) · line 1805
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +5
-0+} +#endif /* CAN_USE_MOVSX */ + +#endif /* CAN_USE_LDSX */ + char _license[] SEC("license") = "GPL";[Severity: Low]
ShouldSEC("socket")and__success__log_level(2)onsext_byte_fill_drops_sext_link()be placed inside the #ifdefCAN_USE_MOVSXblock?
Indeed that bracketing came out weird.
Quoted 3 lines
In
tools/testing/selftests/bpf/progs/bpf_misc.h,CAN_USE_LDSXandCAN_USE_MOVSXcan be enabled independently via__BPF_FEATURE_LDSXand__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.
Quoted 1 line
(for example, with bpf-gcc -mldsx/-msmov flags).
Just for correctness, -mldsx doesn't exist for gcc, -msmov covers both.
Quoted 4 lines
If
CAN_USE_LDSXis defined whileCAN_USE_MOVSXis not defined, the body of the #ifdefCAN_USE_MOVSXblock is preprocessed out, leaving those attributes dangling so they attach to the following_licensedeclaration (or to any test function added after this block).
Indeed the attribute placement needs fixing.
Thx,
-Vineet
[email protected]
AI reviewRe: [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction
In reply to Vineet GuptaThank 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 --
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 <[email protected]>
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.
Quoted 39 lines
kernel/bpf/verifier.c +19
-7@@ -18785,29 +18785,54 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sif (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);
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18821
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+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)?
[ ... ]
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=8
Re: [PATCH bpf-next v3 05/12] selftests/bpf: Cover the low-32 link for zero-extending movs
In reply to [email protected]Quoted 45 lines · On 10/20/26 9:53 AM, [email protected] wrote:
Quoted 1 line
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 thirteenQuoted 25 lines
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, underBPF_F_TEST_REG_INVARIANTSso the violation is a load failure rather than something only dmesg seesQuoted 4 lines
Written in asm so the bytecode is the same whichever compiler built the suite.
Signed-off-by Vineet Gupta <[email protected]>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_reachableandzext_mov_breaks_linked_src.
Quoted 3 lines
The count looks like it was not updated when
zext_contradiction_keeps_range_sanewas added. It is the last bullet, but the third program in the file. Should "Twelve" be "Thirteen"?
Yes there was a last minute test update and this missed the update.
Quoted 65 lines
Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0[ ... ]
Quoted 1 line
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0@@ -710,4 +710,352 @@ l_exit_%=: \[ ... ]
Quoted 17 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +17
-0+/* +* 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 */ \tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l_exit_%=: \ · line 916
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ 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_FULLmember, 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_regagainst 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 thenzext_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.
Quoted 4 lines
zext_chain_drops_linkandzext_mov_breaks_linked_srcalso 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"?
Yes this is correct as well, I'll update the comments.
Thx,
-Vineet
Quoted 7 lines
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/39458500836
Re: [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction
In reply to [email protected]Quoted 46 lines · On 10/20/26 9:53 AM, [email protected] wrote:
Quoted 1 line
bpf: Recover the low 32 bits on the reverse link direction
TL;DR:
- Newsync_linked_regs()arm may intersect contradictory 32-bit ranges to empty, triggering verifier bug WARN or-EFAULTon valid programs; no prev restore
- Comment on width split is inaccurate (nit)Quoted 39 lines
kernel/bpf/verifier.c +23
-7@@ -18785,29 +18785,54 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sif (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);
Quoted 8 lines
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18557
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+ 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?
Yes, good catch.
Following test loads successfully and then prints the empty range warning.
call bpf_get_prandom_u32
r6 = r0
r6 <<= 32
call bpf_get_prandom_u32
r6 |= r0 /* r6 = full 64-bit unknown */ w7 = w6 /* r7 is the zero extension */ r8 = (s32)r6 /* r8 is the sign extension */ if w7 != 5 goto 1f /* new arm pins (u32)r6 to 5 */ if w8 != 6 goto 1f /* would pin it to 6 as well */ r9 = 0
r6 %= r9
1: r0 = 0
exit
Quoted 9 lines
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);
Quoted 6 lines
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 laterreg_bounds_sanity_check()would report it as a verifier bug. The new arm has no such fallback, soreg_bounds_sync()returns early on the empty r32, andtnum_intersect()of two contradicting constants gives an arbitrary const subreg.
v4 will give the new arm same prev/restore this code has.
Quoted 31 lines
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_kindcheck: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_BPFdelta 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] andget_reg_width()returns 64.cnum32_intersect({5,0},{6,0})returnsCNUM32_EMPTY. The "r0 = r6" mov then reachesreg_bounds_sanity_check(env, ..., "alu")at the end ofcheck_alu_op()with "range bounds violation", andverifier_bug()firesBPF_WARN_ONCE. That is a realWARN_ONCEunderCONFIG_DEBUG_KERNEL(and a panic withpanic_on_warn), and it logs "verifier bug: REG INVARIANTS VIOLATION". WithBPF_F_TEST_REG_INVARIANTS, whichtest_loadersets by default, the load fails with-EFAULT.
Quoted 4 lines
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.
Confirmed, that variant reaches empty range too. It exercises the two arms in sequence rather than this one twice.
FWIW, guarding only the new arm would have been enough for my first reproducer; it is this variant that shows both sites need the same post-condition. v4 routes both through one helper, which also takes the two gaps sashiko raised on 4/12 and 6/12: tnum_overlap() before tnum_intersect(), and a second range_bounds_violation() after reg_bounds_sync() rather than only before.
Quoted 32 lines
This is the case
zext_contradiction_keeps_range_sanewas written to pin for the differencing arm. Would saving prev = *reg before the intersection and restoring it onrange_bounds_violation(), as the differencing arm does, work here?No later commit in
bbd86cb1eea3..73fbac05c8bdtouchessync_linked_regs(). The following narrowing fill and spill patches (48dc0496cddb"bpf: Track low-32 scalar equality across narrowing stack fills" and3649346488fc"bpf:
Track low-32 scalar equality across narrowing stack spills") only add more ZEXT/SEXT links that can reach this arm.Quoted 21 lines
kernel/bpf/verifier.c +10
-9/* * 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
Quoted 8 lines
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18574
Quoted 5 lines
kernel/bpf/verifier.c +2
-0+* 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_FULLmeets 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?
Nope. The arm is gated on which side carries the 32-bit kind:
if ((known_reg->link_kind == BPF_REG_LINK_ZEXT || known_reg->link_kind == BPF_REG_LINK_SEXT) && ...
so a BPF_REG_LINK_FULL known_reg never reaches it.
Quoted 6 lines
The arm above only runs when
known_regis the ZEXT/SEXT side and reg is the NONE/FULL side. In the other direction,known_regFULL and reg SEXT, the pair always reaches this continue, and a SEXT member can be wide in theget_reg_width()sense, since negative (s32) values give a umax up toU64_MAX.
Quoted 7 lines
sext_no_sync_when_base_has_deltais 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_regreaches the arm above, and a FULLknown_regis skipped against any 32-bit member?
The comment now describes it by direction, and names that test.
Thx,
-Vineet
Quoted 5 lines
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/39458500836
Re: [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for narrowing stack fills
In reply to [email protected]Quoted 26 lines · On 10/20/26 9:52 AM, [email protected] wrote:
Quoted 1 line
selftests/bpf: Cover the low-32 link for narrowing stack fills
TL;DR: Test issue:
sext_fill_does_not_inherit_zext_linkappears never to put a zero-extending link on the stack slot, so it can't distinguish the newcheck_mem_access()condition from the old one; its comment and commit message look inaccurate.Quoted 20 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +16
-0+/* +* 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 (" \
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_drops_stale_step(void) · line 1740
Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +7
-0+ 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?
Sorry, it doesn't and nothing in this patch can, so it is dropped in v4.
Quoted 20 lines
The w7 = w6 above does give r7
BPF_REG_LINK_ZEXT, but the spill that follows clears it. Incheck_stack_write_fixed_off(), r7 fits in 32 bits, soassign_scalar_id_before_mov()runs beforesave_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, andcheck_mem_access()drops it through the existing !no_sext clear. Thelink_kind==BPF_REG_LINK_SEXTpart of the new condition never sees a ZEXT kind here.This leaves two problems.
First, the in-test comment looks wrong:
Quoted 8 lines
/* a copied link would print as R2=scalar(id=N+0,smin=... */
print_reg_state()prints +delta only whenlink_kindis 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:
Agreed. Pre-series the fill gets a plain id from assign_scalar_id_before_mov() and check_mem_access() drops it through the existing !no_sext clear, so R2 prints without an id either way and the assertion cannot separate them. The changelog said "the last two"; it is now "the last one", counting only sext_byte_fill_drops_sext_link.
Quoted 5 lines
That holds even after
3649346488fc("bpf: Track low-32 scalar equality across narrowing stack spills"), because the fill-sideassign_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.
Right.
Quoted 4 lines
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?
Neither: the test is dropped in v4.
Re-describing seems viable but is conceptually wrong. It pins a plain id dropped across a range-changing ldsx which is pre-existing behavior that this series does not touch, so doesn't make sense to introduce here. Reworking after "a ZEXT-carrying slot is reachable" might be better suited, but that is 11/12 and 12/12, which are tagged [do not merge]. 12/12's version has the same defect and is dropped too, so both go.
Thx,
-Vineet
Quoted 5 lines
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/39458500836
Re: [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs
In reply to [email protected]Quoted 32 lines · On 10/20/26 10:09 AM, [email protected] wrote:
Quoted 1 line
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.
Quoted 28 lines
kernel/bpf/verifier.c +19
-3@@ -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;
Quoted 8 lines
kernel/bpf/verifier.c static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, · line 17347
Quoted 4 lines
kernel/bpf/verifier.c +1
-0+ } }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?
Comment is wrong, fixed in v4.
Walking it through to confirm your reading: a 32-bit add on a register that has an id but no kind takes the else arm,
} else {
if (alu32)
dst_reg->link_kind = BPF_REG_LINK_ZEXT; else
dst_reg->link_kind = BPF_REG_LINK_FULL; dst_reg->delta = off;
}
so "w1 += 0" records exactly what the mov records, ZEXT with delta 0, and a following "w1 += 1" composes onto it.
The example the comment gives, "r1 += r3", is 64-bit, records BPF_REG_LINK_FULL, and is refused for being full link rather than for having spent a delta.
The behaviour is sound: (u32)((u32)(base + 0) + off) is (u32)(base + off) whichever instruction produced the zero. What is actually refused is a *second* delta, and that is what the comment now says.
Quoted 11 lines
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_kindgoes 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.
Quoted 7 lines
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?
Former. Composing is already capped at one so comment says second delta is refused.
Thx,
-Vineet
Quoted 7 lines
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/39458500836
Re: [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs
In reply to [email protected]Quoted 66 lines · On 10/20/26 9:57 AM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: empty range afterreg_bounds_sync()insync_linked_regs()--commit
ad01f18c15eb8cfa9a97b984758db9dd254aace2
Author: Vineet Gupta <[email protected]>bpf: Track low-32 scalar equality across sign-extending movs
This commit adds
BPF_REG_LINK_SEXTto track low-32 scalar equality across 32-bit sign-extending moves, usingsext_32_to_64()andtnum_sext()to propagate bounds insync_linked_regs().Quoted 4 lines
kernel/bpf/verifier.c +0
-0[ ... ]
Quoted 22 lines
kernel/bpf/verifier.c +18
-0@@ -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)); +}[ ... ]
Quoted 25 lines
kernel/bpf/verifier.c +18
-2@@ -18795,9 +18843,26 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sscalar32_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);
Quoted 8 lines
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18604
Quoted 4 lines
kernel/bpf/verifier.c +1
-0+ }/* * Intersect rather than overwrite. A BPF_REG_LINK_ZEXT * link over a wide base does not propagate back, so the [Severity: Medium]
Cansync_linked_regs()leave reg withCNUM64_EMPTYandCNUM32_EMPTYafterreg_bounds_sync(), triggering a register invariants violation on the next instruction that inspects the register?
Yes and actually two things:
- tnum_intersect() has no tnum_overlap() precheck, so two disagreeing known bits become a known 1 rather than a detected contradiction.
- range_bounds_violation() tests only cnum32/64_is_empty, and it runs *before* reg_bounds_sync(). A contradiction that only materialises inside the sync through __update_reg_bounds() or deduce_bounds_32_from_64() is therefore not caught by the restore that 4/12 added.
So the guard added in 4/12 is narrower than the problem it is named for.
The reproducer in your 4/12 report does not fire, though, and the log says why. Built as a socket filter on a patch-10 kernel it verifies clean, and the walk goes 0..7 then straight to 10:
5: R7=scalar(id=1+0,...,var_off=(0x4; 0x1))
6: (45) if r6 & 0x2 goto pc+1
6: R6=scalar(id=1,...,var_off=(0x4; 0xffffffff00000001)) 7: (05) goto pc+2
10: (b7) r0 = 0
The "r9 = 0; r7 %= r9" pair at 8 and 9 is never walked. r6's var_off has bit 1 known zero: value 0x4, and bit 1 is not in the mask, so "if r6 & 2" is resolved statically and the contradicting path is pruned.
r6 knows that because of 8/12 itself: its reverse arm pinned the base's low half from r7, which is why R6 carries smin32/umin32=4, smax32/umax32=5 and the low var_off (0x4; 0x1) by instruction 6. The same issue hid the original 4/12 bug, 8/12 keeps masking things rather than fixing them.
Rather than keep on chasing which reproducers survives patch 8's masking, v4 does what you suggested at the end of the 4/12 report: ask tnum_overlap() before tnum_intersect(), and check range_bounds_violation() after reg_bounds_sync() as well as before. Both arms now go through one helper:
static void sync_bounds_or_revert(struct bpf_reg_state *reg, const struct bpf_reg_state *prev) {
if (range_bounds_violation(reg)) {
*reg = *prev;
return;
}
reg_bounds_sync(reg);
if (range_bounds_violation(reg))
*reg = *prev;
}
Thx,
-Vineet
Quoted 71 lines
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 beforereg_bounds_sync(reg), andtnum_intersect()is called without checkingtnum_overlap(). When a contradiction occurs across domains (between r64, r32, andvar_off) rather than within r64 or r32 individually, the pre-syncrange_bounds_violation()check passes, andreg_bounds_sync(reg)then turns the cross-domain disjointness intoCNUM64_EMPTY/CNUM32_EMPTYwithout 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_offand r64/r32 viatnum_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 invar_off;sync_linked_regs()narrows r7 to [0, 3] withvar_off=TNUM(0, 3).
- Execute if w6 & 4 goto target. On the taken branch, r6 gets low-32var_off=TNUM(4, 0xfffffff3)and r32 = [-0x7ffffffc,0x7ffffff7].
- Insync_linked_regs()on r7,cnum64_intersect_with()andcnum32_intersect_with()both produce [0, 3] (non-empty), whiletnum_intersect()without atnum_overlap()check combinesTNUM(4, 0xfffffffffffffff3)andTNUM(0, 3)intoTNUM(4, 3)([4, 7]).
-range_bounds_violation(reg)is false beforereg_bounds_sync(reg), and__update_reg_bounds()insidereg_bounds_sync(reg)then intersects [0, 3] with [4, 7], leaving r7 withCNUM32_EMPTYandCNUM64_EMPTY.Should
sync_linked_regs()check !tnum_overlap(reg->var_off, prev.var_off) and also checkrange_bounds_violation(reg)afterreg_bounds_sync(reg)before committing the updated state?Quoted 3 lines
/*
* Intersect rather than overwrite. ABPF_REG_LINK_ZEXT
* link over a wide base does not propagate back, so the[ ... ]
Re: [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction
In reply to [email protected]Quoted 60 lines · On 10/20/26 10:20 AM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: missing contradiction check insync_linked_regs()reverse-direction arm --commit
651910c4895680e635057947cc88b56f4edbf401
Author: Vineet Gupta <[email protected]>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_ZEXTorBPF_REG_LINK_SEXT) back to a linked register wider than 32 bits.Quoted 46 lines
kernel/bpf/verifier.c +26
-7@@ -18785,29 +18785,54 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sif (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);
Quoted 8 lines
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18557
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+reg_bounds_sync (reg); + goto scratched; + }[Severity: Medium]
Can this reverse-direction arm leave reg with an empty range (CNUM32_EMPTYorCNUM64_EMPTY) or conflicting constant subreg bits when the low-32 bounds,var_off, or step progression of reg andknown_regcontradict on an unreachable path?
Yeah bpf-ci bot asked the same and that is answered separately. What you mentioned is 4 ways, let me reply each below.
Quoted 28 lines
In the sibling differencing arm further down in
sync_linked_regs(), the code saves prev = *reg before intersecting and restores *reg = prev ifrange_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)andtnum_intersect()are applied directly without saving prev or checking for contradictions. Ifreg->r32becomesCNUM32_EMPTY,reg_bounds_sync()exits early onrange_bounds_violation(reg), and even whencnum32_intersect_with()is non-empty,reg_bounds_sync()can still emptyreg->r32orreg->r64via__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, iftnum_subreg(reg->var_off)andtnum_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():
Quoted 7 lines
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.
Confirmed and this was the same as bpf-ci bot report.
Quoted 5 lines
2. Sign-extending mov (
BPF_REG_LINK_SEXT): if a wide r6 has its low 32 bitspinned 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].
Confirmed.
if w6 != 5 goto out /* wide r6 gets r32 = [5, 5] */ r7 = (s32)r6 /* SEXT */
if w7 != 8 goto out /* the new arm intersects [5,5] with [8,8] */
Note that since w6 is known to const 5, one would expect w7 to be a constant 5 as well:coerce_reg_to_size_sx() decides whether the extension is a no-op from reg_smin()/reg_smax(), the 64-bit pair, which is wide here. So it takes set_sext64_default_val() and r7 comes out [S32_MIN, S32_MAX], unknown, and both branches are walked.
Quoted 6 lines
3.
BPF_JSETfallthrough: inregs_refine_cond_op(), theBPF_JSET|BPF_Xfallthrough path calls__mark_reg_unbounded()before maskingvar_off. After w7 = w6; if w6 == 0 goto out; (wherer6->r32is [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].
Confirmed.
w7 = w6
if w6 == 0 goto out /* r6.r32 becomes [1, U32_MAX] */ if w7 & -1 goto out /* fallthrough refines r7 to 0 */ r9 = 0
r6 %= r9
All the 3 above are caught by the pre-sync check.
Quoted 5 lines
4. Step or tnum conflict inside
reg_bounds_sync(): if a wide r6 has step > 1 (for example step == 3) and w7 = w6 resetsr7->stepto 1 viazext_32_to_64(), narrowing w7 to a value inr6->r32that is not a multiple of 3 passescnum32_intersect_with()and then becomes empty in__update_bounds_from_step(r6)at the end ofreg_bounds_sync().
This one is special as this is the only route where the contradiction is not visible at the point of intersection: cnum32_intersect_with() passes, and the range only empties later in __update_bounds_from_step(). This led to the final fix in v4: check both before and after sync.
Thx,
-Vineet
Quoted 11 lines
When reg is left in this state, any subsequent instruction that checks it via
reg_bounds_sanity_check()triggersverifier_bug()("range bounds violation"), emitting aBPF_WARN_ONCE()and returning-EFAULTwhenBPF_F_TEST_REG_INVARIANTSis enabled.Should this arm save struct
bpf_reg_stateprev = *reg and restore *reg = prev if !tnum_overlap(tnum_subreg(reg->var_off),tnum_subreg(low.var_off)) or ifrange_bounds_violation(reg)is true afterreg_bounds_sync(reg)?[ ... ]
Re: [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills
In reply to [email protected]Quoted 53 lines · On 10/20/26 9:42 AM, [email protected] wrote:
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 <[email protected]>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 settinglink_kindtoBPF_REG_LINK_ZEXT.Quoted 4 lines
kernel/bpf/verifier.c +0
-0[ ... ]
Quoted 35 lines
kernel/bpf/verifier.c +22
-4@@ -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
Quoted 8 lines
kernel/bpf/verifier.c static int check_stack_write_fixed_off(struct bpf_verifier_env *env, · line 3942
Quoted 4 lines
kernel/bpf/verifier.c +4
-0+* 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 callingzext_32_to_64()onss->spilled_ptrcause a precision regression when the 4-byte slot is subsequently filled by a sign-extending load (ldsx)?
Yes precision regression and it also changes a verdict.
Say r6 is given [-16, 15], a small signed range straddling zero, spilled 4 bytes and filled back with ldsx. On a patch-10 kernel the program verifies; with 11/12 applied it is rejected, because the fill no longer knows r2 <= 15:
p10 sext_fill_keeps_small_signed_range success p10+11 sext_fill_keeps_small_signed_range failure ("div by zero")
Thx,
-Vineet
Quoted 34 lines
When spilling a scalar register whose signed range straddles zero (for example [-10, 10], where
reg_umax(reg)isU64_MAXandget_reg_width(reg)is 64) with a 4-byte store (*(u32 *)(r10 - 8) = rX),subreg_linkis true andzext_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()overwritesss->spilled_ptr.r64with [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()copiesss->spilled_ptrto the destination register andcheck_mem_access()callscoerce_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()inspectsreg_smin(reg)andreg_smax(reg)from r64 rather than r32, smax is0xffffffff(>= limit), so the early return no longer triggers andcoerce_reg_to_size_sx()falls through toset_sext64_default_val(), resetting both r64 and r32 to [S32_MIN,S32_MAX] (or the full S16/S8 range).
Re: [PATCH bpf-next v3 12/12] [do not merge] selftests/bpf: Cover the low-32 link for narrowing stack spills
In reply to [email protected]Quoted 42 lines · On 10/20/26 9:32 AM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [Medium] selftests/bpf: fill before narrow inzext_narrowing_spill_byte_no_link()
- [Medium] selftests/bpf: tautological test insext_fill_of_narrowing_spill_drops_zext()
- [Low] selftests/bpf: stale inline comment inzext_narrowing_spill_drops_link()--commit
a341902044eb0b749136bbae6f269759e4c0ffcd
Author: Vineet Gupta <[email protected]>selftests/bpf: Cover the low-32 link for narrowing stack spills
This patch adds six verifier selftests to
verifier_linked_scalars.cto test low-32 register linking behavior across narrowing stack spills and subsequent fills.Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0@@ -1217,6 +1217,128 @@ __naked void zext_fill_byte_forms_no_link(void) : __clobber_all); }[ ... ]
Quoted 17 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +17
-0+/* +* 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 */ \
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void zext_fill_byte_forms_no_link(void) · line 1268
Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +3
-0+ *(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 inzext_narrowing_spill_drops_link()left over from the earlier version of the test? Since the preceding fill into r2 dropsBPF_REG_LINK_ZEXT, narrowing w6 here does not propagate to r2.
Yes. It said the narrowing propagates to r2, which is the opposite of what the test is named for. Fixed.
Quoted 26 lines
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ if r2 == 0 goto 1f; \ + r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +[ ... ]
Quoted 14 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +14
-0+/* +* 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; \
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void zext_fill_byte_forms_no_link(void) · line 1332
Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +5
-0+ 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]
Doeszext_narrowing_spill_byte_no_link()actually test the size gate incheck_stack_write_fixed_off()?
No, fixed in v4.
The narrowing now happens while the value is still on the stack, before the fill, as you suggest and as zext_narrowing_spill_reaches_fill already does. As written, the fill had already dropped any link, so the test would have passed even if the 1-byte spill had formed one.
Quoted 47 lines
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 aBPF_REG_LINK_ZEXTslot 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()?Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +9
-0+ r0 /=0 ; \ +1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#ifdef CAN_USE_MOVSX [ ... ]
Quoted 20 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +16
-0@@ -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 */ \
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c __naked void sext_byte_fill_drops_sext_link(void) · line 1975
Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +5
-0+ *(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]
Cansext_fill_of_narrowing_spill_drops_zext()ever reach theis_ldsxlink clearing incheck_mem_access()withBPF_REG_LINK_ZEXTstill intact?
nope it can't: v4 drops the test.
Thx,
-Vineet
Quoted 51 lines
In
check_stack_write_fixed_off(), the 4-byte narrowing spill "*(u32 *)(r10 - 8) = r6" truncates fp-8 to 32 bits viazext_32_to_64(&ss->spilled_ptr)and setsBPF_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()callsassign_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 clearsBPF_REG_LINK_ZEXTand 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_ZEXTis already cleared by the normal 4-byte fill path (the same path tested byzext_narrowing_spill_drops_link()) before theis_ldsxhandling incheck_mem_access()runs.Additionally, even if r2 kept r6's ID and
BPF_REG_LINK_ZEXTpastcheck_mem_access(),coerce_reg_to_size_sx()restricts r2's 64-bit bounds to [S32_MIN,S32_MAX]. When "if w6 != -1 goto 1f" callssync_linked_regs(), rebuilding r2 withzext_32_to_64()yields0xffffffff, which is disjoint from [S32_MIN,S32_MAX], causingrange_bounds_violation()to revert r2 to its prior bounds and still hit "r0 /= 0".Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +8
-0+1: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} +#endif /* CAN_USE_LDSX */ char _license[] SEC("license") = "GPL";
Re: [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits
In reply to [email protected]Quoted 74 lines · On 10/20/26 10:08 AM, [email protected] wrote:
Quoted 1 line
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.Quoted 44 lines
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 forBPF_ADD_CONST32as 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_CONST64becomesBPF_REG_LINK_FULLandBPF_ADD_CONST32becomesBPF_REG_LINK_ZEXTwith the exact same semantics as today. But this paves the way for a futureBPF_REG_LINK_SEXTin 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 onecheck_ids().With the kind out of ->id it also leaves the idmap key, so
regs_exact()and regsafe()'sexplore_alu_limitsarm 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 intobpf_verifier.hasbpf_clear_scalar_id().Quoted 7 lines
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 <[email protected]>Signed-off-by Vineet Gupta <[email protected]>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 runcheck_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->Band A|flag->C|flag) and was accepted as exact.With the kind moved out of ->id, the same pair now maps
A->Band thenA->C, andcheck_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 throughregsafe(..., EXACT)from the infinite loop check inbpf_is_state_visited():
Quoted 6 lines
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?
Right. The example you mention is new.
Basically v2 had a patch of its own on this topic and it listed two cases
old {r1.id=A, r2.id=A+delta} vs cur {r1.id=B, r2.id=B} old {r2.id=A+delta32} vs cur {r2.id=B+delta64}
Both were same category: one register whose kind differs between old and cur, caught by the new rold->link_kind == rcur->link_kind line.
What you mention here is a different scenario:
old {r2.id=A, r3.id=A|BPF_ADD_CONST64}
cur {r2.id=B, r3.id=C|BPF_ADD_CONST64}
kinds match but it is still rejected, by check_ids().
v4 mentions both mechanisms.
Thx,
-Vineet
Quoted 5 lines
--
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/39458500836
Re: [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs
In reply to [email protected]Quoted 44 lines · On 10/20/26 9:39 AM, [email protected] wrote:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: empty or corrupted range after intersection insync_linked_regs()--commit
05d23d7192de1c6009703f8fbe1537ad78dda89e
Author: Vineet Gupta <[email protected]>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.Quoted 4 lines
kernel/bpf/verifier.c +0
-0[ ... ]
Quoted 23 lines
kernel/bpf/verifier.c +19
-0@@ -18749,6 +18798,27 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sif (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. +*/
Quoted 8 lines
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18560
Quoted 5 lines
kernel/bpf/verifier.c +2
-0+if (range_bounds_violation (reg)) + *reg = prev;reg_bounds_sync (reg); }if (e->is_reg)[Severity: Medium]
Can a contradiction invar_offor linear step still leave an empty range on reg, or corrupt reg into a bogus constant, aftersync_linked_regs()finishes?
Yes to both. I answered the shared half on 6/12 report: v4 route both arms with one helper which checks range bound both before and after the sync.
Quoted 41 lines
First,
tnum_intersect()inkernel/bpf/tnum.cassumes 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 tnumtnum_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_offand prev.var_off disagree on a known bit withouttnum_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 checkscnum32_is_empty(reg->r32)||cnum64_is_empty(reg->r64), and is only called beforereg_bounds_sync(reg). Any contradiction between the intersected r64/r32 ranges andvar_off(via__update_reg_bounds()) or base/step (via__update_bounds_from_step()) happens insidereg_bounds_sync(reg), after therange_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, sorange_bounds_violation(reg)is false. However,tnum_intersect()produces (0x6;0x1) ([6, 7]), andreg_bounds_sync(reg)then intersects [4, 5] with [6, 7], leavingreg->r64andreg->r32empty and triggering a verifier warning on a subsequent r7 %= r9 (with r9 = 0).
Quoted 4 lines
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)... calls___mark_reg_known(reg, 6), overwriting r7 == 4 with the contradicted constant r7 == 6.
This is not empty range, but wrong value.
Quoted 7 lines
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()verifytnum_overlap(reg->var_off, prev.var_off)before callingtnum_intersect(), and also checkrange_bounds_violation(reg)afterreg_bounds_sync(reg)to restore *reg = prev?
Yes to both.
Thx,
-Vineet
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 01/12] bpf: Keep the 32-bit range across a sign extension that cannot change it
In reply to Vineet GuptaOn Tue, 2026-10-20 at 09:18 -0700, Vineet Gupta wrote:
...
Quoted 8 lines
kernel/bpf/verifier.c +4
-0@@ -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 {
kernel/bpf/verifier.c static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size) · line 6209
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+/* 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.
The if (reg_umax(reg) < (1ULL << (num_bits - 1))) return check is no longer necessary, the new check below subsumes it.
Please drop it, otherwise commit lgtm.
Quoted 9 lines
kernel/bpf/verifier.c +6
-0+* 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 &®_s32_max (reg) <= field_smax) +return ; +/* See comment at reg_step_check_unsigned(). */ reg_step_reset (reg);
Re: [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits
In reply to Vineet GuptaQuoted 42 lines · 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 forBPF_ADD_CONST32as 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_CONST64becomesBPF_REG_LINK_FULLandBPF_ADD_CONST32becomesBPF_REG_LINK_ZEXTwith the exact same semantics as today. But this paves the way for a futureBPF_REG_LINK_SEXTin 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 onecheck_ids().With the kind out of ->id it also leaves the idmap key, so
regs_exact()and regsafe()'sexplore_alu_limitsarm 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 intobpf_verifier.hasbpf_clear_scalar_id().
Quoted 8 lines
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 <[email protected]>Signed-off-by Vineet Gupta <[email protected]>---
Nice refactoring.
...
kernel/bpf/log.c static void print_reg_state(struct bpf_verifier_env *env, · line 656
Quoted 13 lines
kernel/bpf/log.c +2
-2@@ -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);
Nit: it would be nice to see if the link is full or zext.
Quoted 19 lines
kernel/bpf/log.c +0
-0if (reg->parent_id)verbose_a ("parent_id=%d" , reg->parent_id);kernel/bpf/scev.c +1
-1@@ -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 :kernel/bpf/states.c +0
-0
...
Quoted 7 lines
kernel/bpf/states.c +2
-1@@ -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.
kernel/bpf/states.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 573
Quoted 10 lines
kernel/bpf/states.c +2
-2* * +------------------+-----------+------------------+---------------+ -* | | 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 | * +------------------+-----------+------------------+---------------+
Nit: "linked kind" -> "link_kind".
also, the table should show when link_kind equality is required.
...
Re: [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs
In reply to Vineet GuptaQuoted 75 lines · 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 whatBPF_ADD_CONST32became, 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 widthEvery 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 nextreg_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_sanecovers 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_overflowdump 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_strsearchallowing 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.
Quoted 7 lines
verifier_reg_equal's
subreg_equality_2becomes__success. It is the same link with a 64-bit compare on the member: "w2 < 9" bounds r3 over all 64 bits, not just its low half, because the zero-extending mov leaves nothing above them.Signed-off-by Vineet Gupta <[email protected]>---
Please revisit comments in this patch, maybe as a follow-up. They are too wordy and, at times, hard to comprehend.
...
Quoted 15 lines
kernel/bpf/verifier.c +11
-0@@ -18485,6 +18534,27 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sif (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,
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18557
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* so this path is unreachable. Say nothing rather than +* say it with an empty range: reg_bounds_sync() below +* refuses to touch one, and the first later +* reg_bounds_sanity_check() would report it as a +* verifier bug, which it is not. Keeping the wider +* pre-intersect state only costs precision on a path +* that cannot be taken. +*/ +if (range_bounds_violation (reg)) + *reg = prev;
I'm not a fan, tbh.
As a followup, I'd suggest a wider refactoring:
- get rid of is_scalar_branch_taken() (or most of it?)
- branch unconditionally;
- apply regs_refine_cond_op() for every branch;
- apply sync_linked_regs() for every branch;
- check if one of the branches is has registers with empty ranges and avoid exploring it.
Quoted 3 lines
kernel/bpf/verifier.c +0
-0reg_bounds_sync (reg); }if (e->is_reg)
...
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs
In reply to Vineet GuptaQuoted 38 lines · 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 bysext_32_to_64()where the zero-extending arm useszext_32_to_64(). The enum already had room, sobpf_reg_statestays 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 totnum_cast(), keeping the known low bits where atnum_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, wherecoerce_reg_to_size_sx()andcoerce_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_deltapins 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.
Quoted 6 lines
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.
The above paragraph is very hard to parse.sync_linked_regs() does call sext_32_to_64().
Please re-read whatever comments and messages the machine generates. For whatever reason the bias is towards a wall of text and complex sentences. I do read those and it hurts. Asking my machine rewrite your machine's text, such that I can understand it is very time consuming.
...
kernel/bpf/verifier.c static void assign_scalar_id_before_mov(struct bpf_verifier_env *env, · line 3766
Quoted 10 lines
kernel/bpf/verifier.c +1
-1@@ -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 )
Why is this rule relaxed only for SEXT?
Can it be relaxed for ZEXT/FULL as well?
Quoted 16 lines
kernel/bpf/verifier.c +9
-0bpf_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
kernel/bpf/verifier.c static void zext_32_to_64(struct bpf_reg_state *reg) · line 6078
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* 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)); +} +
Please use coerce_reg_to_size_sx(). You can improve it by doing:
reg->var_off = tnum_sext(reg->var_off, 4); reg_set_srange64(reg, reg_s32_min(reg), reg_s32_max(reg));
Quoted 8 lines
kernel/bpf/verifier.c +1
-0/* 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; +/*
kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 17576
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* 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 &&
^^^^^^^^^^^^^^^^^^^^^
please make this a bool variable is_sext32
kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 17584
Quoted 8 lines
kernel/bpf/verifier.c +4
-0+ (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;
I don't like how this code sidesteps assign_scalar_id_before_mov().
Quoted 11 lines
kernel/bpf/verifier.c +3
-1*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_sif (reg->id != known_reg->id)continue ;
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18528
Quoted 10 lines
kernel/bpf/verifier.c +5
-4/* -* 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.
Why is this "reverse direction"? what's "inverts"?
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18533
Quoted 6 lines
kernel/bpf/verifier.c +4
-1*/ - 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 &&
On a second thought, it appears it would make sense to collapse FULL and NONE into the same category. E.g. the above condition would become known_reg->link_kind != FULL && reg->link_kind == FULL, much clearer.
Quoted 8 lines
kernel/bpf/verifier.c +3
-2get_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.
kernel/bpf/verifier.c static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s · line 18549
Quoted 10 lines
kernel/bpf/verifier.c +7
-0+* 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)
Does this check skips propagation in the following case?
w7 = w6 ; r6={NONE,0}, r7={ZEXT,0}
r6 += 1 ; r6={FULL,1}
if w6 != 5 goto ...
known_reg is r6 in this case, so:
ZEXT && FULL && ZEXT != FULL -> true, continue is hit.
...
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 09/12] bpf: Track low-32 scalar equality across narrowing stack fills
In reply to Vineet GuptaQuoted 36 lines · 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()takesis_ldsxand setsBPF_REG_LINK_SEXTwhere that is known.check_mem_access()then keeps a sign-extending link across a 4-byte sign-extending load only:BPF_REG_LINK_SEXTmeans (s32)(base + delta) specifically, so an 8- or 16-bit ldsx is a relation the kind cannot express, the same way the ALU arm'ssubreg_linkis gated on (insn->off>> 3) == 4.Costs. A bisect lands one clang regression here --
big_alloc22956 -> 3095 insns, 157 -> 165 states -- but it is not this patch alone: it takes both this and the preceding reverse-direction patch, and neither movesbig_alloc2by 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
Quoted 6 lines
+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 <[email protected]>---
Please de-claude the comments.
...
Quoted 1 line
kernel/bpf/verifier.c +0
-0
...
Quoted 11 lines
kernel/bpf/verifier.c +7
-0@@ -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.
kernel/bpf/verifier.c static int check_stack_read_fixed_off(struct bpf_verifier_env *env, · line 4276
Quoted 10 lines
kernel/bpf/verifier.c +5
-2+*/ +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)))
This check can be simplified to 'env->bpf_capable && size == 4'.
Quoted 4 lines
kernel/bpf/verifier.c +0
-0/* Ensure stack slot has an ID to build a relation * with the destination register on fill. */ assign_scalar_id_before_mov (env, reg);
...
Quoted 10 lines
kernel/bpf/verifier.c +5
-1@@ -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
kernel/bpf/verifier.c static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b · line 7439
Quoted 10 lines
kernel/bpf/verifier.c +4
-1+* 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 ))
Please make this:
bool sext = reg_umax(®s[value_regno]) >= (1ULL << (size * BITS_PER_BYTE - 1));
bool sext32_link = ...;
if (sext && !sext32_link)
bpf_clear_scalar_id(®s[value_regno]);=> no giant comment necessary.
Quoted 3 lines
kernel/bpf/verifier.c +0
-0bpf_clear_scalar_id (®s[value_regno]); } }
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills
In reply to Vineet GuptaQuoted 25 lines · 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_ZEXTis 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 firstsync_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:
Quoted 6 lines
verdicts no change at all
total_insns102 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_states64 changed, 63 worse
I'd still prefer to keep things symmetric. Instruction budget should be less of a concert for 7.5, as far as I understand.
...
Re: [PATCH bpf-next v3 01/12] bpf: Keep the 32-bit range across a sign extension that cannot change it
In reply to Eduard ZingermanHi Eduard,
Thx for taking the time to review.
Quoted 17 lines · Eduard Zingerman
On Tue, 2026-10-20 at 09:18 -0700, Vineet Gupta wrote:
...
Quoted 13 lines
kernel/bpf/verifier.c +9
-0@@ -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 ; + } +
Quoted 8 lines
kernel/bpf/verifier.c static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size) · line 6209
Quoted 5 lines
kernel/bpf/verifier.c +5
-0+/* +* 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. The
if (reg_umax(reg) < (1ULL << (num_bits - 1))) returncheck is no longer necessary, the new check below subsumes it.
Please drop it, otherwise commit lgtm.
Agree. Dropped in v4.
Thx,
-Vineet
Quoted 10 lines
Quoted 10 lines
kernel/bpf/verifier.c +6
-0+* 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 &®_s32_max (reg) <= field_smax) +return ; +/* See comment at reg_step_check_unsigned(). */ reg_step_reset (reg);
Re: [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits
In reply to Eduard ZingermanQuoted 48 lines · Eduard Zingerman
Quoted 47 lines · 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 forBPF_ADD_CONST32as 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_CONST64becomesBPF_REG_LINK_FULLandBPF_ADD_CONST32becomesBPF_REG_LINK_ZEXTwith the exact same semantics as today. But this paves the way for a futureBPF_REG_LINK_SEXTin 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 onecheck_ids().With the kind out of ->id it also leaves the idmap key, so
regs_exact()and regsafe()'sexplore_alu_limitsarm 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 intobpf_verifier.hasbpf_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.
Quoted 6 lines
Quoted 3 lines
Suggested-by Eduard Zingerman <[email protected]>Signed-off-by Vineet Gupta <[email protected]>---
Nice refactoring.
Acked-by Eduard Zingerman <[email protected]>
Thx.
Quoted 16 lines
...
kernel/bpf/log.c static void print_reg_state(struct bpf_verifier_env *env, · line 656
Quoted 13 lines
kernel/bpf/log.c +2
-2@@ -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);Nit: it would be nice to see if the link is full or zext.
Done in v4.
Quoted 33 lines
Quoted 19 lines
kernel/bpf/log.c +0
-0if (reg->parent_id)verbose_a ("parent_id=%d" , reg->parent_id);kernel/bpf/scev.c +1
-1@@ -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 :kernel/bpf/states.c +0
-0...
Quoted 12 lines
kernel/bpf/states.c +3
-2@@ -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 | * |------------------+-----------+------------------+---------------|
Quoted 8 lines
kernel/bpf/states.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 573
Quoted 5 lines
kernel/bpf/states.c +1
-1* | 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 | * +------------------+-----------+------------------+---------------+ Nit: "linked kind" -> "
link_kind".
also, the table should show whenlink_kindequality is required.
...
Done as well. I'll carry the Ack.
Thx,
-Vineet