bpf: range_within() must check cnum ranges instead of min/max pairs
Subsystems (3)
Eduard Zingerman
maintainercover bpf: range_within() must check cnum ranges instead of min/max pairs
This is a follow-up for series [1].is_state_visited() should check cnum's subset relations using cnum-based operations, not min/max projections. See patch #1 for detailed explanation and patch #2 for an example of buggy program accepted by verifier w/o this fix.
Updated veristat performance numbers compared to master before [1] merge follow. Measurements done for the same set of selftests/ sched_ext/meta/cilium programs as in [1].
Net increase: 98K insn 88 programs
Net decrease: -282K insn 52 programs
Raw stats filtered as -f insns_pct>1 -f !insns<10000:
========= selftests: master vs experiment =========
File Program Insns (A) Insns (B) Insns (DIFF) ---- ------- --------- --------- ------------
Total progs: 4665 total_insns diff min: -0.44% total_insns diff max: 52.94% total_insns abs max old: 837,487 total_insns abs max new: 837,487 -5 .. 0 %: 8 0 .. 5 %: 4652 5 .. 15 %: 1 40 .. 50 %: 3 50 .. 55 %: 1
========= scx: master vs experiment =========
File Program Insns (A) Insns (B) Insns (DIFF) ----------------- --------------- --------- --------- ---------------- scx_layered.bpf.o layered_enqueue 13718 14402 +684 (+4.99%) scx_rusty.bpf.o rusty_enqueue 39842 22053 -17789 (-44.65%) scx_rusty.bpf.o rusty_stopping 37738 19949 -17789 (-47.14%) scx_wd40.bpf.o wd40_stopping 37729 19880 -17849 (-47.31%)
Total progs: 376 total_insns diff min: -47.31% total_insns diff max: 19.61% total_insns abs max old: 233,669 total_insns abs max new: 233,696 -50 .. -40 %: 3 -5 .. 0 %: 3 0 .. 5 %: 367 5 .. 15 %: 2 15 .. 20 %: 1
========= meta: master vs experiment =========
File Program Insns (A) Insns (B) Insns (DIFF) -------------------------------------- ------------------- --------- --------- ---------------- <sandbox> test_file_open 88771 104160 +15389 (+17.34%) <profiler> on_perf_event 48056 54544 +6488 (+13.50%) <profiler> on_tracepoint_event 48059 54547 +6488 (+13.50%) <profiler> on_perf_event 48056 54544 +6488 (+13.50%) <profiler> on_tracepoint_event 48059 54547 +6488 (+13.50%) <profiler> on_alloc 50445 56933 +6488 (+12.86%) <profiler> on_free 50251 56739 +6488 (+12.91%) <profiler> on_perf_event 48056 54544 +6488 (+13.50%) <profiler> on_tracepoint_event 48059 54547 +6488 (+13.50%) <profiler> future_iter_resume 50114 56602 +6488 (+12.95%) <profiler> on_py_event 50042 56530 +6488 (+12.97%) scx_layered_bpf_skel_genskel-bpf.bpf.o layered_enqueue 13287 13963 +676 (+5.09%) scx_layered_bpf_skel_genskel-bpf.bpf.o layered_enqueue 13269 13945 +676 (+5.09%) scx_layered_bpf_skel_genskel-bpf.bpf.o layered_enqueue 13269 13945 +676 (+5.09%) <firewall> ..._egress 222327 164648 -57679 (-25.94%) <firewall> ..._tc_eg 222839 164772 -58067 (-26.06%) <firewall> ..._egress 222327 164648 -57679 (-25.94%) <firewall> ..._tc_eg 222839 164772 -58067 (-26.06%)
Total progs: 1540 total_insns diff min: -26.06% total_insns diff max: 37.25% total_insns abs max old: 666,036 total_insns abs max new: 666,036 -30 .. -20 %: 4 -5 .. 0 %: 10 0 .. 5 %: 1494 5 .. 10 %: 10 10 .. 15 %: 13 15 .. 25 %: 5 35 .. 40 %: 4
========= cilium: master vs experiment =========
File Program Insns (A) Insns (B) Insns (DIFF) --------------- --------------------------------- --------- --------- --------------- bpf_host.o tail_handle_ipv4_cont_from_host 20962 26024 +5062 (+24.15%) bpf_host.o tail_handle_ipv6_cont_from_host 17036 18672 +1636 (+9.60%) bpf_host.o tail_nodeport_nat_ingress_ipv4 20080 19858 -222 (-1.11%) bpf_lxc.o tail_nodeport_nat_ingress_ipv4 10697 10510 -187 (-1.75%) bpf_overlay.o tail_handle_inter_cluster_revsnat 11099 10857 -242 (-2.18%) bpf_overlay.o tail_nodeport_nat_ingress_ipv4 11951 11768 -183 (-1.53%) bpf_wireguard.o tail_nodeport_nat_ingress_ipv4 11993 11811 -182 (-1.52%)
Total progs: 134 total_insns diff min: -3.32% total_insns diff max: 24.15% total_insns abs max old: 152,012 total_insns abs max new: 152,012 -5 .. 0 %: 12 0 .. 5 %: 120 5 .. 15 %: 1 20 .. 25 %: 1
[1] https://lore.kernel.org/bpf/[email protected]/T/
---
Eduard Zingerman (2):
bpf: range_within() must check cnum ranges instead of min/max pairs selftests/bpf: a test for proper cnums compare in is_state_visited()
include/linux/cnum.h | 2 ++ kernel/bpf/cnum_defs.h | 14 +++++++++++ kernel/bpf/states.c | 11 +++------ .../testing/selftests/bpf/progs/verifier_bounds.c | 27 ++++++++++++++++++++++ 4 files changed, 46 insertions(+), 8 deletions(-)
---
base-commit: 6c60b2dd5a7889a583389e95e79689191206f86f
change-id: 20260425-cnum-range-within-4a755ba81e93
Eduard Zingerman
maintainerPATCH 1/2 bpf: range_within() must check cnum ranges instead of min/max pairs
states.c:range_within() must be updated to properly check if cnum-based range in an old state is a superset of a range in the cur state. Currently it makes the decision using min/max accessors:
reg_umin(old) <= reg_umin(cur) <= reg_umax(old)
This is wrong for cnums that cross both UT_MAX/0 and ST_MAX/ST_MIN boundaries. Consider cnum32{base=0x7FFFFFF0, size=0x80000020}, which represents values [0x7FFFFFF0, ..., U32_MAX, 0, ..., 0x10]. Its projections are u32_min/max=0/U32_MAX, s32_min/max=S32_MIN/MAX. A register with range [0x100, 0x200] (which lies entirely in the gap of the wrapping range) would pass the min/max check despite having no overlap with the actual cnum arc.
This commit replaces min/max comparison with cnum{32,64}_is_subset() operation. The operation implementation is verified using cbmc model checker in [1].
[1] https://github.com/eddyz87/cnum-verif/
--- include/linux/cnum.h | 2 ++ kernel/bpf/cnum_defs.h | 14 ++++++++++++++ kernel/bpf/states.c | 11 +++-------- 3 files changed, 19 insertions(+), 8 deletions(-)
include/linux/cnum.h +2 -0
@@ -48,6 +48,7 @@ bool cnum32_is_const(struct cnum32 cnum);bool cnum32_is_empty (struct cnum32 cnum);struct cnum32 cnum32_add (struct cnum32 a,struct cnum32 b);struct cnum32 cnum32_negate (struct cnum32 a); +bool cnum32_is_subset (struct cnum32 outer,struct cnum32 inner);/* Same as cnum32 but for 64-bit ranges */ struct cnum64 {
@@ -73,6 +74,7 @@ bool cnum64_is_const(struct cnum64 cnum);bool cnum64_is_empty (struct cnum64 cnum);struct cnum64 cnum64_add (struct cnum64 a,struct cnum64 b);struct cnum64 cnum64_negate (struct cnum64 a); +bool cnum64_is_subset (struct cnum64 outer,struct cnum64 inner);struct cnum32 cnum32_from_cnum64 (struct cnum64 cnum);struct cnum64 cnum64_cnum32_intersect (struct cnum64 a,struct cnum32 b);
kernel/bpf/cnum_defs.h +14 -0
@@ -220,6 +220,20 @@ bool FN(is_const)(struct cnum_t cnum)return cnum.size ==0 ; } +bool FN (is_subset )(struct cnum_t bigger,struct cnum_t smaller) +{ +if (FN (is_empty (smaller))) +return true; +if (FN (is_empty (bigger))) +return false; +/* rotate both arcs such that 'bigger' starts at origin, hence does not overflow */ + smaller.base -= bigger.base; + bigger.base =0 ; +if (FN (urange_overflow)(smaller) && bigger.size <UT_MAX ) +return false; +return smaller.base + smaller.size <= bigger.size; +} +#undef EMPTY#undef cnum_t#undef ut
kernel/bpf/states.c +3 -8
@@ -2,6 +2,7 @@/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ #include <linux/bpf.h> #include <linux/bpf_verifier.h> +#include <linux/cnum.h> #include <linux/filter.h> #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)
@@ -301,14 +302,8 @@ int bpf_update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_sstatic bool range_within (const struct bpf_reg_state *old,const struct bpf_reg_state *cur) { -return reg_umin (old) <=reg_umin (cur) && -reg_umax (old) >=reg_umax (cur) && -reg_smin (old) <=reg_smin (cur) && -reg_smax (old) >=reg_smax (cur) && -reg_u32_min (old) <=reg_u32_min (cur) && -reg_u32_max (old) >=reg_u32_max (cur) && -reg_s32_min (old) <=reg_s32_min (cur) && -reg_s32_max (old) >=reg_s32_max (cur); +return cnum64_is_subset (old->r64, cur->r64) && +cnum32_is_subset (old->r32, cur->r32); }/* If in the old state two registers had the same id, then they need to have
Signature · 1 line
2.53.0
[email protected]
AI reviewThe Fixes tag points to commit bbc631085503, but that commit exists in bpf-next/master and is not in the ancestry of the current branch (patch-series.local). The current branch is based on a grafted…
Quoted 16 lines
bpf:
range_within()must check cnum ranges instead of min/max pairsstates.c:range_within() must be updated to properly check if cnum-based range in an old state is a superset of a range in the cur state. Currently it makes the decision using min/max accessors:
reg_umin(old)<=reg_umin(cur)<=reg_umax(old)This is wrong for cnums that cross both UT_MAX/0 and ST_MAX/ST_MIN boundaries. Consider cnum32{base=0x7FFFFFF0, size=0x80000020}, which represents values [
0x7FFFFFF0, ...,U32_MAX, 0, ...,0x10]. Its projections are u32_min/max=0/U32_MAX, s32_min/max=S32_MIN/MAX. A register with range [0x100,0x200] (which lies entirely in the gap of the wrapping range) would pass the min/max check despite having no overlap with the actual cnum arc.
Quoted 7 lines
This commit replaces min/max comparison with cnum{32,64}_is_subset() operation. The operation implementation is verified using cbmc model checker in [1].
[1] https://github.com/eddyz87/cnum-verif/
Fixes bbc631085503 ("bpf: replace min/max fields with struct cnum{32,64}")
The Fixes tag points to commit bbc631085503, but that commit exists in bpf-next/master and is not in the ancestry of the current branch (patch-series.local). The current branch is based on a grafted commit e06021ed87b0 that contains the same cnum-based code with the same bug.
While the Fixes tag is semantically correct (the bug was introduced when min/max fields were replaced with cnum structures), the referenced commit is unreachable from this branch. Should the Fixes tag reference the grafted commit instead, or is this patch intended for a different branch?
Quoted 1 line
Signed-off-by Eduard Zingerman <[email protected]>
---
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/24942703368
Quoted 30 lines · On Sun, Apr 26, 2026 at 12:20 AM <[email protected]> wrote:
Quoted 17 lines
bpf:
range_within()must check cnum ranges instead of min/max pairsstates.c:range_within() must be updated to properly check if cnum-based range in an old state is a superset of a range in the cur state. Currently it makes the decision using min/max accessors:
reg_umin(old)<=reg_umin(cur)<=reg_umax(old)This is wrong for cnums that cross both UT_MAX/0 and ST_MAX/ST_MIN boundaries. Consider cnum32{base=0x7FFFFFF0, size=0x80000020}, which represents values [
0x7FFFFFF0, ...,U32_MAX, 0, ...,0x10]. Its projections are u32_min/max=0/U32_MAX, s32_min/max=S32_MIN/MAX. A register with range [0x100,0x200] (which lies entirely in the gap of the wrapping range) would pass the min/max check despite having no overlap with the actual cnum arc.Quoted 7 lines
This commit replaces min/max comparison with cnum{32,64}_is_subset() operation. The operation implementation is verified using cbmc model checker in [1].
[1] https://github.com/eddyz87/cnum-verif/
Fixes bbc631085503 ("bpf: replace min/max fields with struct cnum{32,64}")The Fixes tag points to commit
bbc631085503, but that commit exists in bpf-next/master and is not in the ancestry of the current branch (patch-series.local). The current branch is based on a grafted commite06021ed87b0that contains the same cnum-based code with the same bug.
Quoted 4 lines
While the Fixes tag is semantically correct (the bug was introduced when min/max fields were replaced with cnum structures), the referenced commit is unreachable from this branch. Should the Fixes tag reference the grafted commit instead, or is this patch intended for a different branch?
AI is being confused.
These patches were applied.
ALL,
please periodically 'git pull' bpf-next to see what was applied.
pw-bot was unreliable in the past and got very spotty recently.
I think it misses every other applied patch.
Maintainers don't have capacity to send manual emails with "Applied. Thanks".
Eduard Zingerman
maintainerPATCH 2/2 selftests/bpf: a test for proper cnums compare in is_state_visited()
In reply to Eduard ZingermanTest case demonstrating a bug in cnum comparison logic fixed by previous commit. A pruning point is reached with r6 in two states:
1. 32-bit range of [0x7FFFFFF0, U32_MAX] ∪ [0, 0x10]
2. 32-bit range of [0x100, 0x200]
At pruning point the buggy is_state_visited() logic would assume that would assume range (2) to be a subset of (1) and fail to explore the path performing division by zero.
--- .../testing/selftests/bpf/progs/verifier_bounds.c | 27 ++++++++++++++++++++++ 1 file changed, 27 insertions(+)
tools/testing/selftests/bpf/progs/verifier_bounds.c +27 -0
@@ -2267,4 +2267,31 @@ __naked void deduce64_from_32_wrapping_32bit(void) : __clobber_all); } +/* Check that range_within() compares cnum ranges, not min/max projections. */ +SEC("socket") +__failure __msg("div by zero") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void range_within_cnum_cross_both_boundaries(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r1 = 0x80000020; \ +if r0 > r1 goto 1f; \ +r0 += 0x7FFFFFF0; /* PATH 1 */ \ +goto 2f; \ +1: call %[bpf_get_prandom_u32]; /* PATH 2 */ \ +if r0 < 0x100 goto 3f; \ +if r0 > 0x200 goto 3f; \ +2: /* PATH 1: r0 ∈ [0x7FFFFFF0, U32_MAX] ∪ [0, 0x10] */ \ +/* PATH 2: r0 ∈ [0x100, 0x200] */ \ +if r0 != 0x100 goto 3f; /* True only on PATH 2 */ \ +r0 /= 0; \ +3: exit; \ +" + :: __imm(bpf_map_lookup_elem), +__imm_addr (map_hash_8b), +__imm (bpf_get_prandom_u32) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.53.0