[PATCH bpf-next 0/2] bpf: range_within() must check cnum ranges instead of min/max pairs

[PATCH bpf-next 0/2] bpf: range_within() must check cnum ranges instead of min/max pairs

[Eduard Zingerman]

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/fd376f47b9512daf669a87b23573f614ec146385.camel@gmail.com/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

[PATCH bpf-next 1/2] bpf: range_within() must check cnum ranges instead of min/max pairs

[Eduard Zingerman]

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/

Fixes: bbc631085503 ("bpf: replace min/max fields with struct cnum{32,64}")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/cnum.h   |  2 ++
 kernel/bpf/cnum_defs.h | 14 ++++++++++++++
 kernel/bpf/states.c    | 11 +++--------
 3 files changed, 19 insertions(+), 8 deletions(-)

diff --git a/include/linux/cnum.h b/include/linux/cnum.h
index a7259b105b45..49b7d0c7645d 100644
--- a/include/linux/cnum.h
+++ b/include/linux/cnum.h
@@ -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);
diff --git a/kernel/bpf/cnum_defs.h b/kernel/bpf/cnum_defs.h
index 3ebd8f723dbb..1f232138b6e9 100644
--- a/kernel/bpf/cnum_defs.h
+++ b/kernel/bpf/cnum_defs.h
@@ -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
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index a78ae891b743..bd9c22945050 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -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_s
 static 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

-- 
2.53.0

Re: [PATCH bpf-next 1/2] bpf: range_within() must check cnum ranges instead of min/max pairs

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 1932 bytes --]

> 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/
>
> 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?

> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>


---
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

Re: [PATCH bpf-next 1/2] bpf: range_within() must check cnum ranges instead of min/max pairs

[Alexei Starovoitov]

On Sun, Apr 26, 2026 at 12:20 AM <bot+bpf-ci@kernel.org> wrote:
>
> > 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/
> >
> > 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?

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".

[PATCH bpf-next 2/2] selftests/bpf: a test for proper cnums compare in is_state_visited()

[Eduard Zingerman]

Test 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.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../testing/selftests/bpf/progs/verifier_bounds.c  | 27 ++++++++++++++++++++++
 1 file changed, 27 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index 5dd243e653c9..a3e4c0945137 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -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)
+{
+	asm volatile ("							\
+	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";

-- 
2.53.0