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

Eduard Zingerman
2026-04-25T11:48:07Z

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