From: Vineet Gupta <vineet.gupta@linux.dev>
To: ast@kernel.org, daniel@iogearbox.net, andrii@kernel.org,
eddyz87@gmail.com, memxor@gmail.com
Cc: martin.lau@linux.dev, song@kernel.org, yonghong.song@linux.dev,
jolsa@kernel.org, emil@etsalapatis.com, ihor.solodrai@linux.dev,
john.fastabend@gmail.com, shuah@kernel.org, bpf@vger.kernel.org,
linux-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org,
Vineet Gupta <vineet.gupta@linux.dev>
Subject: [PATCH bpf-next v3 00/12] bpf: track scalar equality across the low 32 bits
Date: Tue, 20 Oct 2026 09:18:55 -0700 [thread overview]
Message-ID: <20261020161907.2115379-1-vineet.gupta@linux.dev> (raw)
This series was motivated by BPF_GCC tendency to generate sign-extensions
which the verifier effectively doesn't handle at all for the scalar linked
tracking.
This can prevent correct programs from loading such as the test below,
0: (61) r2 = *(u32 *)(r1 +24)
1: (bf) r0 = (s32)r2
2: (56) if w2 != 0x0 goto pc+10 ; R2=0
12: (95) exit
leads to following load failure:
At program exit the register R0 has smin=-2147483648 smax=2147483647
should have been in [0, 1]
The verifier currently tracks the full 64 bits or nothing (the alu32
handling is also full 64-bits with upper bits known to be zeroes).
The sign extension at insn 1 has no way to say "same low 32 bits, high half
from bit 31", so it doesn't link r0 and r2, hence the insn 2 branch can't
narrow r0.
A slightly complex scenario involving sign extension is where the source
is already linked (bpf_sockmap_map_iter_fd/copy):
31: (85) call bpf_map_delete_elem#3 ; R0=scalar()
32: (bf) r1 = r0 ; R0=scalar(id=4) R1=scalar(id=4)
33: (bf) r0 = (s32)r0 ; R0=scalar(smin=0xffffffff80000000,smax=0x7fffffff)
34: (16) if w1 == 0x0 goto pc+6 ; R0 unchanged
41: (95) exit
And a zero extension has the same gap, but usually it only costs precision.
This is captured in existing verifier_reg_equal.c:subreg_equality_2 (since
2023):
call %[bpf_ktime_get_ns]
r2 = r0 <-- unknown high bits
w3 = w2 <-- only low half shared, not recorded
if w2 < 9 goto l0_%= <-- narrows w2
exit
l0_%=:
if r3 < 9 goto l1_%= <-- this doesn't deduce
r0 -= r1 <-- illegal read reachable
l1_%=:
exit
This series, among others, also removes this restriction, making the test
pass now.
-__description("check w reg not equal if r reg upper32 bits not 0")
-__failure __msg("R1 !read_ok")
+__description("check w reg equal if r reg upper32 bits not 0")
+__success
And finally this series also handles narrowing stack fills: a 4-byte read
of a value spilled wider. Its mirror image, the narrowing stack spill,
is implemented here too (patch 11-12) but is not proposed, see
Testing: veristat sub-section below for reasoning.
Improvements
============
This series completely eliminates two class of verifier failures in
selftests built with BPF_GCC:
- all 19 instances of "should have been in [0, 1]"
- all 6 instances of "The sequence of 8193 jumps is too complex"
It unblocks existing subreg_equality_2.
How it is modelled
==================
Upstream currently relates two scalars using ->id which additionally
encodes add_const with a optional delta. Sign-extension requires a different
relationship which is low32 same only. This series generalizes the
existing mechanisms:
For an abstract scalar X, a register can be:
X + delta zext(X + delta) sext(X + delta)
The first is the existing add_const and other two are the new
functionality and also support the optional delta. The relationship now
looks like:
enum bpf_reg_link_kind {
BPF_REG_LINK_NONE = 0,
BPF_REG_LINK_FULL, /* all 64 bits shared */
BPF_REG_LINK_ZEXT, /* low 32 shared, high half zero */
BPF_REG_LINK_SEXT, /* low 32 shared, high half = bit 31 */
};
Four values fit the two bits add_const already had, so the encoding
costs no space: bpf_reg_state stays 80 bytes and bpf_func_state stays in
the 1K allocator bucket that commit a2052333e6f9 ("bpf: Bpf_func_state
size optimization") put it in.
Other details to be aware of
============================
- Sext with delta is supported.
- Semantics of BPF_ADD_CONST32 change: It used to be:
reg == base + delta, base known to fit u32
Now it is modelled as:
BPF_REG_LINK_ZEXT: reg == (u32)(base + delta), for ANY base width.
- Delta composing/stacking: is allowed now, albeit only once:
"w3 = w0; w3 -= 1" is now able to keep the regs linked
Composing further is deliberately not done, as it interferes with
state pruning in loops. On arena_strsearch, allowing any second delta
costs 1176 -> 1751 insns and 102 -> 133 states; allowing it onto a zero
delta produced by an add rather than by the mov still costs 1176 -> 1196.
- Propagating a delta backwards: patches 4 and 6 already do that for
base that fits 32-bits, for wide base, patch 8 does that for
completeness. It does fix the directed test zext_reverse_pins_low_half,
and the instrumented arm fires 78 times under bpf-gcc, 40 times under
clang, but no visible improvements.
Testing
=======
- kernel off bpf-next baseline of 26/10/16, commit d2141481a764 "(bpf: Free
the subprog jump tables once the CFG passes are done)"
- bpf-gcc (20261010, ga02e2004cb70).
Only patch 1-10 are used for testing as the last 2 are just for demonstration
(as asked for in v2), but not really production.
1. BPF_GCC built selftest changes:
before: 476 FAIL 6912 OK 749 SKIP
after: 450 FAIL 6985 OK 751 SKIP
bpf_ip_check_defrag FAIL -> OK
bpf_ip_check_defrag/v4 FAIL -> OK
bpf_ip_check_defrag/v6 FAIL -> OK
bpf_iter FAIL -> OK
bpf_iter/bpf_sockmap_map_iter_fd FAIL -> OK
bpf_iter/task_pid FAIL -> OK
bpf_iter/task_pidfd FAIL -> OK
bpf_iter/task_sleepable FAIL -> OK
bpf_iter/task_tid FAIL -> OK
bpf_sockmap_map_iter_fd FAIL -> OK
setget_sockopt FAIL -> OK
sock_addr/connect_unix: attach prog with wrong attach type FAIL -> OK
sock_addr/connect_unix: connect (stream) FAIL -> OK
sock_addr/connect_unix: connect deny (stream) FAIL -> OK
sock_addr/connect_unix: kernel_connect (dgram) FAIL -> OK
sock_addr/connect_unix: kernel_connect deny (dgram) FAIL -> OK
sock_addr/sendmsg_unix: attach prog with wrong attach type FAIL -> OK
sock_addr/sendmsg_unix: kernel_sendmsg deny (dgram) FAIL -> OK
sock_addr/sendmsg_unix: sendmsg (dgram) FAIL -> OK
sock_addr/sendmsg_unix: sendmsg deny (dgram) FAIL -> OK
sock_addr/sendmsg_unix: sock_sendmsg (dgram) FAIL -> OK (runs twice)
sock_addr/sendmsg_unix: sock_sendmsg deny (dgram) FAIL -> OK
sockmap_basic FAIL -> OK
sockmap_basic/sockhash copy FAIL -> OK
sockmap_basic/sockmap copy FAIL -> OK
2. veristat on selftests built off bpf-gcc, clang and a corpora of prebuilt
bpf objects.
bpf-gcc, 3314 programs verifying on both sides:
verdicts 12 pre-existing failure -> success
total_insns 4 changed, 2 worse, -16 overall: cond_break3 36 -> 48,
ksock_wq_start 207 -> 213, estab 2849 -> 2817, and the
series' own zext_contradiction_keeps_range_sane 11 -> 9
total_states 1 changed, 1 worse: cond_break3 4 -> 6
clang, 3520 programs verifying on both sides:
verdicts 1 pre-existing: subreg_equality_2
total_insns 3 changed, 1 worse, +126 overall: big_alloc2
2956 -> 3095, cond_break2 90 -> 79, and the series' own
zext_contradiction_keeps_range_sane 11 -> 9
total_states 2 changed, 1 worse: big_alloc2 157 -> 165,
cond_break2 10 -> 9
and an external corpus -- 441 objects from cilium, katran, fb and
sched_ext, 1467 programs verifying on both sides (increase test coverage
from selftest 5.4M insns and 15 progs above 50k insns to 25.2M insns and
131 progs over 50k insns).
verdicts no change
total_insns 12 changed, 10 worse, +7087 (+0.028%); two improve.
Worst is +1812 on test_file_open, 2470 -> 4282, in
bpfjailer .../lib-tests-bpf-open-open.bpf.o
total_states 9 changed, 7 worse, +242 (+0.026%); worst +155 on the
same program
3. Applying 11-12 on top of 1-10:
bpf-gcc nothing at all -- no program changes
clang one program changes, and it improves
external 102 changed, 63 worse, +84450 insns (+0.335%) and
+6257 states (+0.661%). Not a broad slowdown: the three
below carry 97% of it. Of the remaining 60, two are
+26.6% and +7.7%; the other 58 are under 1% each.
+89.7% +19784 rusty_enqueue 22053 -> 41837
scx_rusty.bpf.o
+57.2% +59616 test_file_open 104160 -> 163776
bpfjailer .../match-tests-...-file.bpf.o
+40.6% +2688 layered_enqueue 6626 -> 9314
scx_layered 1.0.11.1
Two notes for anyone re-running the above.
Four programs in the external corpus are named test_file_open. The one
at +57.2% here is in .../match-tests-...-file.bpf.o; the +1812 in
section 2 is a different and much smaller program in
.../lib-tests-...-open.bpf.o, which these two patches take the other
way, 4282 -> 2476.
And veristat's raw verdict-change counts are larger than the twelve in
section 2 -- 28 on bpf-gcc, 17 on clang -- because the corpus is built
from the series tree, so the series' own new tests read as
failure -> success too. zext_mov_breaks_linked_src goes the other way,
success -> failure: it is an intentional __failure test, and veristat
records "failure" for a program that does not load.
Patches
=======
1-2 fix a sign extension that cannot change the range but widens it
anyway, which is unrelated to the rest and was asked to go first
3 move the linked-scalar flags out of bpf_reg_state->id
4-5 zero-extending movs
6-7 sign-extending movs, including the inherited delta
8 the reverse direction, for a base wider than 32 bits
9-10 narrowing stack fills
11-12 [do not merge] narrowing stack spills
Patches 1-10 are what is proposed. 11-12 are posted because the relation
is the one asked for and implementing it was the only way to find out
what it costs; the answer is in 11's message and it is not worth it.
Changes since v2
================
- the kind moves out of bpf_reg_state->id into an enum of its own
(Eduard), replacing v2's add_const plus a separate subreg_sext
bool. bpf_reg_state stays 80 bytes. v2's 2/13 is squashed into the
patch that needs it (Alexei).
- the zero-extending link is ADD_CONST32 with a zero delta rather
than a kind of its own (Alexei), which drops the
dst_umax > U32_MAX guard -- the one pre-existing semantic this
series changes, described above.
- sign-extending movs carry a delta, which v2 did not support.
- 4/12 fixes a reachable WARNING found while preparing this revision:
the intersect step could leave an empty range behind. v2 never
showed it because its 8/13 happened to mask it.
- 9/12 reports its cost, which v2 did not: +6598 insns over six
external programs, with no verdict change.
- v2's 11/13 is dropped; the two spill patches are now [do not
merge], with the measurement behind that call in 11/12.
The per-patch changelogs under each --- have the rest.
v2:
https://lore.kernel.org/bpf/20260910164635.459558-1-vineet.gupta@linux.dev/
RFC:
https://lore.kernel.org/bpf/20260814231945.3884596-1-vineet.gupta@linux.dev/
Vineet Gupta (12):
bpf: Keep the 32-bit range across a sign extension that cannot change
it
selftests/bpf: Cover sign extensions that cannot change the range
bpf: Prepare linked scalars for relations narrower than 64 bits
bpf: Track low-32 scalar equality across zero-extending movs
selftests/bpf: Cover the low-32 link for zero-extending movs
bpf: Track low-32 scalar equality across sign-extending movs
selftests/bpf: Cover the low-32 link for sign-extending movs
bpf: Recover the low 32 bits on the reverse link direction
bpf: Track low-32 scalar equality across narrowing stack fills
selftests/bpf: Cover the low-32 link for narrowing stack fills
[do not merge] bpf: Track low-32 scalar equality across narrowing
stack spills
[do not merge] selftests/bpf: Cover the low-32 link for narrowing
stack spills
include/linux/bpf_verifier.h | 52 +-
include/linux/tnum.h | 7 +
kernel/bpf/log.c | 6 +-
kernel/bpf/scev.c | 2 +-
kernel/bpf/states.c | 38 +-
kernel/bpf/tnum.c | 15 +
kernel/bpf/verifier.c | 387 ++++-
tools/testing/selftests/bpf/progs/bpf_misc.h | 16 +
.../selftests/bpf/progs/verifier_bounds.c | 2 +-
.../selftests/bpf/progs/verifier_ldsx.c | 8 +-
.../bpf/progs/verifier_linked_scalars.c | 1323 ++++++++++++++++-
.../selftests/bpf/progs/verifier_movsx.c | 63 +-
.../selftests/bpf/progs/verifier_reg_equal.c | 14 +-
.../selftests/bpf/progs/verifier_spill_fill.c | 6 +-
14 files changed, 1787 insertions(+), 152 deletions(-)
--
2.53.0-Meta
next reply other threads:[~2026-10-20 16:19 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-10-20 16:18 Vineet Gupta [this message]
2026-10-20 16:18 ` [PATCH bpf-next v3 01/12] bpf: Keep the 32-bit range across a sign extension that cannot change it Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 02/12] selftests/bpf: Cover sign extensions that cannot change the range Vineet Gupta
2026-10-20 16:18 ` [PATCH bpf-next v3 03/12] bpf: Prepare linked scalars for relations narrower than 64 bits Vineet Gupta
2026-10-20 17:08 ` bot+bpf-ci
2026-10-20 16:18 ` [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs Vineet Gupta
2026-10-20 17:09 ` bot+bpf-ci
2026-10-20 16:19 ` [PATCH bpf-next v3 05/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
2026-10-20 16:53 ` bot+bpf-ci
2026-10-20 16:19 ` [PATCH bpf-next v3 06/12] bpf: Track low-32 scalar equality across sign-extending movs Vineet Gupta
2026-10-20 16:19 ` [PATCH bpf-next v3 07/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
2026-10-20 16:19 ` [PATCH bpf-next v3 08/12] bpf: Recover the low 32 bits on the reverse link direction Vineet Gupta
2026-10-20 16:53 ` bot+bpf-ci
2026-10-20 16:19 ` [PATCH bpf-next v3 09/12] bpf: Track low-32 scalar equality across narrowing stack fills Vineet Gupta
2026-10-20 16:19 ` [PATCH bpf-next v3 10/12] selftests/bpf: Cover the low-32 link for " Vineet Gupta
2026-10-20 16:52 ` bot+bpf-ci
2026-10-20 16:19 ` [PATCH bpf-next v3 11/12] [do not merge] bpf: Track low-32 scalar equality across narrowing stack spills Vineet Gupta
2026-10-20 16:19 ` [PATCH bpf-next v3 12/12] [do not merge] selftests/bpf: Cover the low-32 link for " Vineet Gupta
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261020161907.2115379-1-vineet.gupta@linux.dev \
--to=vineet.gupta@linux.dev \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=eddyz87@gmail.com \
--cc=emil@etsalapatis.com \
--cc=ihor.solodrai@linux.dev \
--cc=john.fastabend@gmail.com \
--cc=jolsa@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-kselftest@vger.kernel.org \
--cc=martin.lau@linux.dev \
--cc=memxor@gmail.com \
--cc=shuah@kernel.org \
--cc=song@kernel.org \
--cc=yonghong.song@linux.dev \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®