BPF List
 help / color / mirror / Atom feed
* [PATCH bpf-next 00/37] bpf: More precision, more counted loops, larger limits
@ 2026-11-03 23:40 Alexei Starovoitov
  2026-11-03 23:40 ` [PATCH bpf-next 01/37] bpf: Keep the range of a packet pointer when a number >= 0 is added Alexei Starovoitov
                   ` (37 more replies)
  0 siblings, 38 replies; 49+ messages in thread
From: Alexei Starovoitov @ 2026-11-03 23:40 UTC (permalink / raw)
  To: bpf; +Cc: daniel, andrii, eddyz87, memxor

From: Alexei Starovoitov <ast@kernel.org>

This series lets the verifier of today accept more of the code that
compilers make. The main pass does not change: it follows each path of
a prog and prunes, as before.

  precision   A packet pointer keeps its range when the prog adds a scalar
              that is not negative. A shift, a division and a remainder by
              a range have bounds.
  loops       Scalar evolution counts more forms of 'for' and 'while', and
              it has a formula for more of the registers that a loop
              changes. The verifier verifies such a loop one time.
  subprogs    The verifier takes the arguments of a static subprog from
              its code and not from BTF. A trampoline on such a subprog
              keeps what the code takes, or the attach is refused.
  limits      24 arguments of a static subprog, 1024 subprogs.

The patches
===========

  patches  1-2    a packet pointer keeps its range when the prog adds
                  a scalar >= 0
  patches  3-5    trampolines on static subprogs that BTF does not describe
  patches  6-7    stack arguments of a static subprog from its code
  patches  8-21   scalar evolution counts more loops: partial spills,
                  a bound in .rodata, ARG_ANYTHING, sums of constants,
                  ranges, more registers with a formula, over 256 exits
  patches 22-25   a 32-bit counter on the stack, several back edges
  patches 26-27   bounds for a shift, a division and a remainder by a range
  patches 28-31   more forms of the jump that counts a loop
  patch   32      more targets of a call through a table of functions
  patches 33-35   24 arguments of static subprogs
  patches 36-37   1024 subprogs

The tests of a patch are in the patch behind it, or in the last patch of
its group. Patches 32 and 36 raise a limit and have no test of their own.
Patches 3, 4 and 8 are fixes.

Precision
=========

  if (pkt + 54 > pkt_end || off > 38)
          return 0;
  *(u64 *)(pkt + off)

Today the verifier rejects the load: the range of pkt is 54 bytes, but the
sum has no range. With patch 1 the sum keeps the range, and the prog can
read the 16 bytes that are in the packet for each value of off.

  cpu = hash % nr_cpus;
  bit = 1 << order;

Today each result is an unknown scalar, unless the second operand is
a constant. With patch 26 the result has bounds that come from the ranges
of the two operands.

Loops
=====

Scalar evolution examines each loop before the main pass of the verifier.
For 'for (i = 0; i < 10; i++)' it calculates the number of iterations. If
it also has a formula for each live register that the loop changes, then
the verifier gives these registers their ranges over all iterations and
verifies the body one time. The verifier unrolls all other loops: it
verifies them one iteration at a time.

  loop --> is there a count? --> does each live register --> verified
                 |               have a formula?             one time
                 | no                  | no
                 v                     v
              unrolled              unrolled

Patch 8 is a fix: the second question got a wrong 'yes' for a number in
a part of a stack slot. The other patches let more loops pass:

  patch  question  the loop
  -----  --------  --------------------------------------------------------
  10     count     The bound is in .rodata.
  12     count     The counter is in the stack, and a helper gets the
                   address of a stack slot as a number.
  14     count     'r += 1; r += 1', 'r -= 1', '(u32)r' made of two shifts
  16     count     The first value or the bound is a range.
  18     formula   A number that only loses bits, a pointer to arena,
                   a register that gets the same constant each time
  20     count     The loop has more than 256 exits.
  22     formula   The counter is an 'int' that lives on the stack.
  24     count     'continue', or a copy of the test at the end of each
                   path: several back edges
  28     count     The latch is false in the first iteration.
  29     count     'for (i = 63; i >= 0; i--)', 'while (n--)'
  30     count     The latch tests a flag that a jump sets.

The latch is the jump that closes the loop.

The verifier relies on the count: nothing stops a counted loop at run time,
and the ranges of the variables come from the count. It does not rely on
the formulas of patch 18: it compares the state that returns to the loop
head with the state at the head.

The verifier verifies a counted loop with ranges and never goes back to one
iteration at a time. Thus each patch that counts more loops can lose a prog
that needs exact values in each iteration. The logs describe these progs.
None of them is in the corpora below.

Static subprogs and limits
==========================

BTF of a static subprog describes the source. It does not describe what the
compiler passes. rustc adds a hidden pointer to the result, and it passes
a pair in two registers. Then a function with 4 parameters takes
6 arguments.

  patch  the static subprog                  the verifier
  -----  ----------------------------------  ------------------------------
  3      has unreliable BTF and returns in   refuses fexit, fmod_ret and
         R0:R2                               fsession: they keep only R0
  4      reads a register of r1-r5 that BTF  marks BTF as unreliable: then
         does not have                       a trampoline keeps r1-r5
  6      loads more stack arguments than     accepts the prog, and refuses
         BTF has                             to attach a trampoline

  limit                                            today  with the series
  -----------------------------------------------  -----  ---------------
  arguments of a static subprog                       12               24
  subprogs                                           256             1024
  functions that a load from a table of functions     64             1024
  can give

The limits of kfuncs, trampolines and global subprogs do not change.

The limits are what the progs of https://github.com/4ast/rust-bpf need.
These progs do not load yet: they need more changes of the verifier.

Veristat changes
================

A: bpf-next d4bf9e34e299. B: this series. The two runs use the same
objects. The selftests that the series adds or changes are not counted:
they test the verifier itself.
Insns is the number of insns that the verifier processes. It is not the
size of a prog.
Progs is the number of progs that load in the two runs.

Corpus                 Progs  Insns (A)  Insns (B)      Insns (DIFF)
---------------------  -----  ---------  ---------  ----------------
selftests               3573    6993083    6574720  -418363 (-5.98%)
selftests, no_alu32     3430    6287968    6044572  -243396 (-3.87%)
selftests, cpuv4        3444    5120894    5117161    -3733 (-0.07%)
selftests, bpf_gcc      3211    1520384    1438463   -81921 (-5.39%)
37 builds of Cilium     5189   42046146   42046146       +0 (+0.00%)
sched-ext/scx            493    2971692    2851736  -119956 (-4.04%)
scx, as BPF CI has it    428    1321821    1315591    -6230 (-0.47%)
tools/sched_ext          240     118790     118790       +0 (+0.00%)
public progs of Meta     511   10383121   10360656   -22465 (-0.22%)

libarena is in the first row only.

Verdict changes
---------------

No prog is lost. 5 progs load only in B:

  scx_pandemonium.bpf.o     pandemonium_enqueue
  scx_pandemonium.bpf.o     pandemonium_select_cpu
  bpf_gcc/profiler1.bpf.o   raw_tracepoint__sched_process_exit
  bpf_gcc/profiler2.bpf.o   raw_tracepoint__sched_process_exit
  bpf_gcc/profiler3.bpf.o   raw_tracepoint__sched_process_exit

scx_pandemonium, patch 8: a counted loop also changes a 32-bit number in
the stack. The verifier took the slot for an unknown scalar and did not
unroll the loop. But the number differs each time at the loop head, so the
verifier cannot prune there: "The sequence of 8193 jumps is too complex".

profiler, patch 24: gcc moves a pointer through a map value and ends the
loop with 'if r7 != r4', where r4 is the pointer to the end. The verifier
does not decide this jump and goes on behind the last element: "invalid
access to map value". The loop has two back edges. With a count the pointer
has its range.

Regressions
-----------

Progs that load in the two runs. The larger Insns is 1,000 or more, and B
needs at least 5% more insns. The list is complete.

File                              Program            Insns (A)  Insns (B)      Insns (DIFF)
--------------------------------  -----------------  ---------  ---------  ----------------
lib_alloc_selftests_noasan.bpf.o  alloc_selftest         23569      29898   +6329 (+26.85%)
str_map_test.bpf.o                test_str_match           859       1038    +179 (+20.84%)
ci/scx_flow.bpf.o                 flow_dispatch         147592     166903  +19311 (+13.08%)
libarena_asan.bpf.o               test_buddy_create       4563       4865     +302 (+6.62%)
libarena_asan.bpf.o               arena_buddy_reset       4597       4900     +303 (+6.59%)
scx_pandemonium.bpf.o             pandemonium_tick        1044       1103      +59 (+5.65%)

alloc_selftest, test_str_match, flow_dispatch and pandemonium_tick shift,
divide or take a remainder by a range. The result was an unknown scalar.
With patch 26 it has bounds, so states that were equal differ now, and the
verifier prunes fewer paths. The same bounds decide jumps in other progs:
see scx_rusty and scx_flow below.

In the two progs of libarena loops that had no count are counted now.

Top wins (30 of 89)
-------------------

Progs that load in the two runs. The larger Insns is 1,000 or more, and B
needs at least 5% fewer insns. A prog that is in several builds is listed
one time: the build with the most insns in A.
no_alu32/, bpf_gcc/: the build of the selftests. ci/: scx, as BPF CI has
it. Ranked by percentage change, then by the change of Insns, file,
program.

File                                    Program                                  Insns (A)  Insns (B)       Insns (DIFF)
--------------------------------------  ---------------------------------------  ---------  ---------  -----------------
no_alu32/timer_start_delete_race.bpf.o  start_timer                                  46008         32   -45976 (-99.93%)
no_alu32/timer_start_delete_race.bpf.o  delete_elem                                  20004         15   -19989 (-99.93%)
no_alu32/access_map_in_map.bpf.o        access_map_in_array                          24606         43   -24563 (-99.83%)
no_alu32/access_map_in_map.bpf.o        access_map_in_htab                           24606         43   -24563 (-99.83%)
no_alu32/access_map_in_map.bpf.o        sleepable_access_map_in_array                24606         43   -24563 (-99.83%)
no_alu32/access_map_in_map.bpf.o        sleepable_access_map_in_htab                 24606         43   -24563 (-99.83%)
no_alu32/linked_list.bpf.o              clear_global_array_list                      15384         66   -15318 (-99.57%)
no_alu32/linked_list.bpf.o              clear_global_nested_list                      5634         25    -5609 (-99.56%)
no_alu32/linked_list.bpf.o              clear_global_list                             4866         22    -4844 (-99.55%)
no_alu32/linked_list.bpf.o              clear_map_list                                4877         33    -4844 (-99.32%)
no_alu32/linked_list.bpf.o              clear_inner_map_list                          4885         41    -4844 (-99.16%)
no_alu32/rhash.bpf.o                    test_rhash_update_elements                    8866        103    -8763 (-98.84%)
no_alu32/timer.bpf.o                    test1                                         5011        263    -4748 (-94.75%)
bpf_gcc/bpf_iter_unix.bpf.o             dump_unix                                     5591        302    -5289 (-94.60%)
libarena_asan.bpf.o                     test_buddy_alloc_multiple                   242319      17506  -224813 (-92.78%)
bpf_gcc/bpf_iter_task_stack.bpf.o       dump_task_stack                               7245        636    -6609 (-91.22%)
verity_enforce.bpf.o                    bpfj_verity_mmap_file                         6313        876    -5437 (-86.12%)
no_alu32/verifier_arena_large.bpf.o     big_alloc2                                    3231        487    -2744 (-84.93%)
bpf_gcc/rbtree_search_kptr.bpf.o        rbtree_search_kptr_ref                        1085        241     -844 (-77.79%)
libarena.bpf.o                          test_rbtree_add_remove_circular_reverse      13930       6349    -7581 (-54.42%)
bpf_gcc/profiler1.bpf.o                 kprobe__proc_sys_write                        2607       1250    -1357 (-52.05%)
no_alu32/linked_list.bpf.o              inner_map_list_push_pop_multiple             14553       7229    -7324 (-50.33%)
no_alu32/linked_list.bpf.o              map_list_push_pop_multiple                   14744       7420    -7324 (-49.67%)
no_alu32/linked_list.bpf.o              global_list_push_pop_multiple                13931       7201    -6730 (-48.31%)
bpf_gcc/profiler1.bpf.o                 tracepoint__syscalls__sys_enter_kill         24035      12812   -11223 (-46.69%)
ci/scx_rusty.bpf.o                      rusty_stopping                               21750      11901    -9849 (-45.28%)
bpf_gcc/profiler1.bpf.o                 raw_tracepoint__sched_process_exec            3080       1727    -1353 (-43.93%)
libarena.bpf.o                          test_rbtree_insert_many_noalloc              11478       6741    -4737 (-41.27%)
libarena.bpf.o                          test_rbtree_insert_many_update               11478       6741    -4737 (-41.27%)
scx_flow.bpf.o                          flow_select_cpu                             145475      89352   -56123 (-38.58%)

Signed-off-by: Alexei Starovoitov <ast@kernel.org>

Alexei Starovoitov (37):
  bpf: Keep the range of a packet pointer when a number >= 0 is added
  selftests/bpf: Test range of a packet pointer after a number is added
  bpf: Refuse fexit on an unreliable static subprog that returns in
    R0:R2
  bpf: Don't trust BTF of a static subprog that reads more registers
  selftests/bpf: Test trampolines on subprogs that take more than BTF
    says
  bpf: Count stack arguments of a static subprog from its code
  selftests/bpf: Test static subprogs that don't take what BTF says
  bpf: Don't treat a partial spill as widened in scalar evolution
  selftests/bpf: Test loops that change a partial spill
  bpf: Let scalar evolution see loads from read-only maps
  selftests/bpf: Test scalar evolution with a loop bound in .rodata
  bpf: Helpers don't write through ARG_ANYTHING
  selftests/bpf: Test scalar evolution with stack address as
    ARG_ANYTHING
  bpf: Fold sums of constants and two shifts by 32 in scalar evolution
  selftests/bpf: Test sums of constants and shifts by 32 in scalar
    evolution
  bpf: Count loops whose first value or bound is a range
  selftests/bpf: Test loops whose first value or bound is a range
  bpf: Describe more registers of a counted loop
  selftests/bpf: Test more registers of a counted loop
  bpf: Compute scev for a loop that has more than 256 exits
  selftests/bpf: Test a loop with 301 exits
  bpf: Describe a 32-bit counter that lives on the stack
  selftests/bpf: Test a 32-bit counter that lives on the stack
  bpf: Count a loop with several back edges
  selftests/bpf: Test loops with several back edges
  bpf: Compute bounds for a shift, a division and a remainder by a range
  selftests/bpf: Test a shift, a division and a remainder by a range
  bpf: Count a loop whose latch is false in the first iteration
  bpf: Count '!=' across 0 in 32 bits and loops that go down
  bpf: Count a loop whose latch tests a flag that a jump sets
  selftests/bpf: Test more latches of counted loops
  bpf: Allow BPF_MAX_SUBPROGS targets of a read from a table of
    functions
  bpf: Keep the frame of analyze_subprog() small
  bpf: Allow 24 arguments of static subprogs
  selftests/bpf: Test a static subprog with 24 arguments
  bpf: Bump BPF_MAX_SUBPROGS to 1024
  selftests/bpf: Make room in veristat for the stats of 1024 subprogs

 include/linux/bpf.h                           |   19 +-
 include/linux/bpf_verifier.h                  |   40 +-
 kernel/bpf/backtrack.c                        |    2 +-
 kernel/bpf/btf.c                              |   18 +-
 kernel/bpf/const_fold.c                       |   11 +-
 kernel/bpf/fixups.c                           |    2 +-
 kernel/bpf/liveness.c                         |   34 +-
 kernel/bpf/loops.c                            |  105 +-
 kernel/bpf/scev.c                             | 1041 +++++++++++++++--
 kernel/bpf/verifier.c                         |  263 +++--
 .../selftests/bpf/prog_tests/tracing_struct.c |   30 +-
 .../selftests/bpf/prog_tests/verifier.c       |    4 +
 .../bpf/progs/tracing_struct_int128_tgt.c     |   22 +-
 .../bpf/progs/tracing_struct_int128_tracer.c  |    6 +-
 .../selftests/bpf/progs/verifier_alu_range.c  |  168 +++
 .../bpf/progs/verifier_direct_packet_access.c |  100 ++
 .../selftests/bpf/progs/verifier_loop_latch.c |  165 +++
 .../selftests/bpf/progs/verifier_precision.c  |   11 +-
 .../selftests/bpf/progs/verifier_scev.c       |  692 ++++++++++-
 .../selftests/bpf/progs/verifier_stack_arg.c  |  325 ++++-
 .../bpf/progs/verifier_stack_arg_order.c      |    8 +-
 tools/testing/selftests/bpf/veristat.c        |    7 +-
 22 files changed, 2749 insertions(+), 324 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_alu_range.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_loop_latch.c

-- 
2.55.0


^ permalink raw reply	[flat|nested] 49+ messages in thread

end of thread, other threads:[~2026-11-04 18:40 UTC | newest]

Thread overview: 49+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-03 23:40 [PATCH bpf-next 00/37] bpf: More precision, more counted loops, larger limits Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 01/37] bpf: Keep the range of a packet pointer when a number >= 0 is added Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 02/37] selftests/bpf: Test range of a packet pointer after a number " Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 03/37] bpf: Refuse fexit on an unreliable static subprog that returns in R0:R2 Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 04/37] bpf: Don't trust BTF of a static subprog that reads more registers Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 05/37] selftests/bpf: Test trampolines on subprogs that take more than BTF says Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 06/37] bpf: Count stack arguments of a static subprog from its code Alexei Starovoitov
2026-11-04  0:14   ` sashiko-bot
2026-11-04  1:05     ` Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 07/37] selftests/bpf: Test static subprogs that don't take what BTF says Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 08/37] bpf: Don't treat a partial spill as widened in scalar evolution Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 09/37] selftests/bpf: Test loops that change a partial spill Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 10/37] bpf: Let scalar evolution see loads from read-only maps Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 11/37] selftests/bpf: Test scalar evolution with a loop bound in .rodata Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 12/37] bpf: Helpers don't write through ARG_ANYTHING Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 13/37] selftests/bpf: Test scalar evolution with stack address as ARG_ANYTHING Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 14/37] bpf: Fold sums of constants and two shifts by 32 in scalar evolution Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 15/37] selftests/bpf: Test sums of constants and " Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 16/37] bpf: Count loops whose first value or bound is a range Alexei Starovoitov
2026-11-04  0:21   ` sashiko-bot
2026-11-04  1:05     ` Alexei Starovoitov
2026-11-04  7:26   ` Eduard Zingerman
2026-11-04 18:25     ` Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 17/37] selftests/bpf: Test " Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 18/37] bpf: Describe more registers of a counted loop Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 19/37] selftests/bpf: Test " Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 20/37] bpf: Compute scev for a loop that has more than 256 exits Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 21/37] selftests/bpf: Test a loop with 301 exits Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 22/37] bpf: Describe a 32-bit counter that lives on the stack Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 23/37] selftests/bpf: Test " Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 24/37] bpf: Count a loop with several back edges Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 25/37] selftests/bpf: Test loops " Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 26/37] bpf: Compute bounds for a shift, a division and a remainder by a range Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 27/37] selftests/bpf: Test " Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 28/37] bpf: Count a loop whose latch is false in the first iteration Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 29/37] bpf: Count '!=' across 0 in 32 bits and loops that go down Alexei Starovoitov
2026-11-04  0:26   ` sashiko-bot
2026-11-04  1:06     ` Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 30/37] bpf: Count a loop whose latch tests a flag that a jump sets Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 31/37] selftests/bpf: Test more latches of counted loops Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 32/37] bpf: Allow BPF_MAX_SUBPROGS targets of a read from a table of functions Alexei Starovoitov
2026-11-04  0:12   ` sashiko-bot
2026-11-04  1:06     ` Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 33/37] bpf: Keep the frame of analyze_subprog() small Alexei Starovoitov
2026-11-03 23:40 ` [PATCH bpf-next 34/37] bpf: Allow 24 arguments of static subprogs Alexei Starovoitov
2026-11-03 23:41 ` [PATCH bpf-next 35/37] selftests/bpf: Test a static subprog with 24 arguments Alexei Starovoitov
2026-11-03 23:41 ` [PATCH bpf-next 36/37] bpf: Bump BPF_MAX_SUBPROGS to 1024 Alexei Starovoitov
2026-11-03 23:41 ` [PATCH bpf-next 37/37] selftests/bpf: Make room in veristat for the stats of 1024 subprogs Alexei Starovoitov
2026-11-04 18:40 ` [PATCH bpf-next 00/37] bpf: More precision, more counted loops, larger limits patchwork-bot+netdevbpf

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox