Re: [PATCH bpf-next v3 0/4] bpf: replace min/max fields with struct cnum{32,64}

[Eduard Zingerman <eddyz87@gmail.com>]

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

On Sat, 2026-04-25 at 03:05 -0700, Eduard Zingerman wrote:
> On Fri, 2026-04-24 at 15:52 -0700, Eduard Zingerman wrote:
> > This RFC replaces s64, u64, s32, u32 scalar range domains tracked by
> > verifier by a pair of circular numbers (cnums): one for 64-bit domain
> > and another for 32-bit domain. Each cnum represents a range as a
> > single arc on the circular number line, from which signed and unsigned
> > bounds are derived on demand. See also wrapped intervals
> > representation as in [1].
> > 
> > The use of such representation simplifies arithmetic and conditions
> > handling in verifier.c and allows to express 32 <-> 64 bit deductions
> > in a more mathematically rigorous way.
> > 
> > [1] https://jorgenavas.github.io/papers/ACM-TOPLAS-wrapped.pdf
> 
> Uh-oh. range_within() needs an update.
> 
> [...]

The fix is as in the attachment, the tests are still passing, but the
stats had changed a bit. I'll send the fix formally later on Saturday.

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
Old success: 2924
New success: 2926
total_insns diff min:   -0.44%
total_insns diff max:   52.94%
0 -> value: 0
value -> 0: 0
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
Old success: 351
New success: 351
total_insns diff min:  -47.31%
total_insns diff max:   19.61%
0 -> value: 0
value -> 0: 0
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
Old success: 1464
New success: 1464
total_insns diff min:  -26.06%
total_insns diff max:   37.25%
0 -> value: 0
value -> 0: 0
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
Old success: 134
New success: 134
total_insns diff min:   -3.32%
total_insns diff max:   24.15%
0 -> value: 0
value -> 0: 0
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

[-- Attachment #2: range-within-fix.patch --]
[-- Type: text/x-patch, Size: 1725 bytes --]

diff --git a/kernel/bpf/cnum_defs.h b/kernel/bpf/cnum_defs.h
index 3ebd8f723dbb..af1f13c58903 100644
--- a/kernel/bpf/cnum_defs.h
+++ b/kernel/bpf/cnum_defs.h
@@ -220,6 +220,17 @@ bool FN(is_const)(struct cnum_t cnum)
 	return cnum.size == 0;
 }
 
+bool FN(is_within)(struct cnum_t outer, struct cnum_t inner)
+{
+        if (FN(is_empty)(outer) || FN(is_empty(inner)))
+		return false;
+	if (outer.size == UT_MAX)
+		return true;
+	inner.base -= outer.base;
+	outer.base = 0;
+	return !FN(urange_overflow)(inner) && inner.base + inner.size <= outer.size;
+}
+
 #undef EMPTY
 #undef cnum_t
 #undef ut
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index a78ae891b743..e06c07981945 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -1,5 +1,6 @@
 // SPDX-License-Identifier: GPL-2.0-only
 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
+#include "linux/cnum.h"
 #include <linux/bpf.h>
 #include <linux/bpf_verifier.h>
 #include <linux/filter.h>
@@ -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_within(old->r64, cur->r64) &&
+	       cnum32_is_within(old->r32, cur->r32);
 }
 
 /* If in the old state two registers had the same id, then they need to have