BPF List
 help / color / mirror / Atom feed
* [PATCH bpf-next 00/26] bpf: Find linked registers by scalar evolution, remove scalar ids
@ 2026-11-09  6:46 Alexei Starovoitov
  2026-11-09  6:46 ` [PATCH bpf-next 01/26] bpf: Keep the 32-bit range across a no-op sign extension Alexei Starovoitov
                   ` (26 more replies)
  0 siblings, 27 replies; 37+ messages in thread
From: Alexei Starovoitov @ 2026-11-09  6:46 UTC (permalink / raw)
  To: bpf; +Cc: daniel, andrii, eddyz87, memxor

From: Alexei Starovoitov <ast@kernel.org>

  char *buf = bpf_map_lookup_elem(&map, &key);    /* 128 bytes */
  ..
  p = buf + i;                                    /* i is a byte */
  if (i > 100)
          return 0;
  *p = buf[0];

The jump bounds i. p was computed before:

  invalid access to map value, value_size=128 off=255 size=1

People do not write that, compilers do. In a loop over strings or records
in a buffer clang computes 'buf + i' at the end of an iteration and tests
i at the start of the next one. Patch 15 has such a loop.

What the verifier knows about two registers is in the state:

  r2 = r1                     r1 and r2 get id 7
  r2 += 4                     id 7 | BPF_ADD_CONST64, delta 4
  *(u64 *)(r10 - 8) = r1      fp-8 has id 7
  if r1 > 100 goto ..         sync_linked_regs() refines all three

A scalar id is dropped at the second '+=', at a sign extension, at a 32-bit
spill of a wider value. A jump refines at most five registers and stack
slots (LINKED_REGS_MAX), the others lose their id. Nothing links a pointer
to its index. And scalar ids have a price: every insn that moves or
changes a scalar assigns, keeps or clears ids, regsafe() maps the ids of
two states, a join reconciles them. States that differ in nothing but
scalar ids are verified twice.

That r2 is r1 + 4, and that p is buf + i, is static. It takes no state.
Scalar evolution has it for loops: every register and stack slot has an
expression there. This series computes the expressions for whole subprogs,
before the main pass. A value that no expression describes, such as the
result of a call or a load, gets an SSA name: %r0.8 is the def of r0 by
insn 8. The prog above:

   0: call bpf_get_prandom_u32#7     r0 is %r0.0
   1: r7 = r0
   2: r7 &= 255                      r7 is (& %r0.0 255)
   8: call bpf_map_lookup_elem#1     r0 is %r0.8
  10: r6 = r0
  11: r2 = r6
  12: r2 += r7                       r2 is (+ %r0.8 (& %r0.0 255))
  13: if r7 > 0x64 goto pc+2

r6 is %r0.8 too, so at insn 13 r2 is r6 + r7. For each conditional jump
scev.c computes the linked registers: the live registers and stack slots
that are a tested register + a constant (delta) on every path to the jump,
or a pointer + a tested register + delta. The main pass refines them after
the jump. Scalar ids go.

Linked registers are static. A link holds on every path to its jump,
whatever state gets there (intraprocedural: the entry values of a subprog
are symbols, so a fact holds for every caller). There is no limit of five
registers and none on the constants that are added. A link can hold modulo
2^32, 2^16 or 2^8 only, which covers extensions and partial spills. The
types of the registers are read in the state at the jump. Nothing is added
to struct bpf_reg_state, and delta goes.

Patch 1, by Vineet Gupta, stands alone.
  1  'w0 = (s8)w0' keeps a 32-bit range that fits in s8 already: the sign
     extension is a no-op.

Patches 2 - 7 change kernel/bpf/scev.c only. They are prerequisites of
patch 12: they get the expressions ready for all code. The main pass does
not use them yet. No verdict changes.
  2  A fix of the representation. 'w5 >>= w4' and 'r5 >>= r4; w5 = w5' had
     the same expression, (zext32 (>> r5 r4)). They are distinct values.
     The operands of 32-bit shifts and divisions are zero or sign
     extended, a shift amount is masked:
     (zext32 (>> (zext32 r5) (& r4 31))).
  3  Cost. Expressions are going to be constructed for all insns of a prog,
     not only for loops. The hash table allocated for every second
     expression. It gets chains in an array, it grows, (REG r) has a fixed
     id. With all code analyzed: 471 -> 6 allocations per load, the time in
     scev.c per insn goes from 485 to 291 ns. A constant factor, 1.7.
  4  Cost. No phi for a dead register (pruned SSA). At a join point 25
     registers and stack slots have two expressions on average, one of
     them is live. 1.79 -> 0.78 expressions per insn, 291 to 170 ns per
     insn: 1.7 again.
  5  Simplify an expression at construction, so that 'r2 is r1 + 3' is at
     its root however many insns computed it. Patches 12 and 15 compare
     expressions at every conditional jump.
  6  What a load or a call returns was '_', one expression for all of
     them. Such a value gets an SSA name: a def by an insn, %r0.6, or a phi
     before an insn, %r8.7=phi(1, 2). From here on an expression id can be
     a value number (struct expr::is_vn): the registers that have it hold
     the same value.
  7  Compute the expressions for whole subprogs. A subprog is analyzed as
     the outermost loop, which runs once. No users yet.

Patches 8 - 9 are about stack slots. A slot keeps its expression across
a store through a pointer and across a call if that insn cannot write to
the slot. scev.c takes that from bpf_may_write_mask(). liveness.c computes
the mask before the main pass: it tracks the values derived from FP and
looks at the types of the arguments of helpers and kfuncs. Nothing checked
it.
  8  bpf_sys_bpf() stores log_true_size into the attr of its caller, but
     arg2_type in bpf_sys_bpf_proto is ARG_PTR_TO_MEM | MEM_RDONLY. Mark it
     MEM_WRITE.
  9  The main pass sees every write to a stack. Check each of them against
     the mask of the insn.

Patches 10 - 11 fix what is wrong in the main pass today. The patches
after them refine more registers and stack slots, so more progs would run
into both.
 10  'r0 <<= 3; r0 += 5; if r0 s< -2 goto ..; if r0 s> 1 goto ..'
     The range [-2, 1] and var_off don't overlap. The verifier goes on with
     an empty register, up to "verifier bug: REG INVARIANTS VIOLATION".
     Detect at the jump that the branch is dead.
 11  On big endian the first half-slot of a 64-bit spill has the upper 32
     bits of the value. __clean_func_state() and stacksafe() treated it as
     a 32-bit spill, which has the low 32 bits.

Patches 12 - 16 use the expressions.
 12  A new ability. find_linked_regs() computes the linked registers of
     each conditional jump: expressions with a constant difference, modulo
     2^64, 2^32, 2^16 or 2^8. check_cond_jmp_op() refines them:
     refine_linked_regs(). sync_linked_regs() still runs.
 13  Tests for 12. The tests of scalar ids stay and cover the mechanism.
     The new ones are for what only a static analysis can get wrong:
     an arena add that is converted to ALU32, a store through a dynptr
     slice, an edge that the verifier adds, a link at a loop header,
     a pointer that is not a scalar, big endian half-slots, an empty
     intersection.
 14  More tests, by Vineet Gupta: sign extensions, for 1 and 12.
 15  A new ability. A linked register can be a pointer: base + the tested
     register + delta. After the jump the main pass recomputes it, as
     'p = buf; p += i' would, with the i that the jump refined. The prog at
     the top loads. A live register or stack slot has to hold buf at the
     jump: 'buf += i' in place is not found.
 16  Tests for 15.

Patches 17 - 24 remove scalar ids: their users (17 - 20), the ids (21),
dead code (22 - 24).
 17  scev.c left it to the main pass to check, by scalar ids, that an
     induction variable and its copy hold the same value at loop entry. It
     compares their expressions there.
 18  scev.c does not analyze irreducible loops, so the jumps in them have
     no linked registers. Find them in the basic block of the jump (local
     value numbering).
 19  Remove sync_linked_regs(). Jumps refine by scalar evolution only.
 20  flow_join_makes_up() recognized copies of a scalar by their id. It
     compares their ranges. A heuristic on which states are joined:
     soundness does not depend on it.
 21  Stop assigning ids to scalars. States that differed in scalar ids only
     are one state.
 22  Dead code: scalar ids in regsafe().
 23  Dead code: scalar ids in the join of states.
 24  Dead code: scalar ids in the log and in bpf_verifier.h.

Patches 25 - 26 are about loops of GCC. scev.c computes the iteration
count of a loop (header_count: how often the header is executed).
header_count = backedge-taken count + 1. A loop without it is walked: the
verifier unrolls the loop, one state per iteration; a counted loop is
summarized, one state for all iterations. A long loop that is walked ends
with "more than 1024 states that cannot be joined". Such loops loaded when
the verifier explored each path.
 25  A new ability. GCC keeps 'int i' as the sign extension of a 32-bit
     add: 'w1 += 1; r3 = (s32)r1'. That is a new recurrence,
     (sext32 (linear r3 1)). A wrap is handled.
 26  Tests for 25.
Long loops of GCC that still have no iteration count are rejected as
before, among them dump_task_sleepable() of bpf_iter_tasks.c, where one of
two backedges has no linear latch.

Precision that is lost is listed in patches 17 and 19. Most of it: linked
registers belong to the frame of the jump. Scalar ids also linked
registers and stack slots of the callers: a subprog that tests its
argument refined the register that the caller keeps.

Patches 12 - 24 do what patches 3 - 12 of Vineet Gupta's "bpf: track scalar
equality across the low 32 bits" v3 [1] do, without a link in the state.
Patch 1 and the tests of patch 14 are his.

The selftests as GCC builds them gain most. GCC keeps the int that a call
returned as 'r5 = (s32)r0', tests w0 and returns r5, and no scalar id
links r5 to r0. "should have been in [0, 1]" is in the log of
test_progs-bpf_gcc 19 times before the series and never after it,
83 tests and 303 subtests fail in place of 87 and 320. Of the 220 entries
of BPF CI's deny list for that flavour 64 pass, 58 did.

kernel/ and include/: 1513 lines added, 948 removed.

veristat over 32913 progs, against the tree before the series. 29 more
load: 20 of the selftests as GCC builds them, among them profiler1-3,
test_sk_lookup and setget_sockopt, and 9 asm tests. One asm test stops
loading in its four flavours, "regalloc in callee". Patch 19 changes it.

                     progs           load     insns   states
  selftests, clang   18810  11750 -> 11754   -0.21 %  -0.43 %
  selftests, GCC      6011   3651 ->  3672   -3.74 %  -4.28 %
  Cilium              5193   5189 ->  5189   -0.80 %  -1.76 %
  sched_ext           1272   1163 ->  1163   +0.05 %  +0.03 %
  katran, bpfjailer    538    511 ->   511   -0.48 %  -0.66 %
  Rust                1089   1081 ->  1081   -5.56 %  -6.59 %
  all                32913  23345 -> 23370   -2.79 %  -4.42 %

To load them the kernel spends 1.4 % more instructions on the C programs
and 4.3 % fewer on those in Rust (perf stat): scev.c analyzes all code
(patches 7 and 12), the main pass verifies fewer insns and states
(patch 21). mem_peak of veristat goes down by 0.9 % and 7.5 %. Load time
follows the instructions: 1 to 2 % more for the C programs, 4 to 8 % less
for those in Rust.

[1] https://lore.kernel.org/bpf/20261020161907.2115379-1-vineet.gupta@linux.dev/

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

Alexei Starovoitov (24):
  bpf: Model 32-bit shifts and divisions exactly in scalar evolution
  bpf: Construct scalar evolution expressions without allocations
  bpf: Don't join dead registers in scalar evolution
  bpf: Simplify scalar evolution expressions at construction
  bpf: Give SSA names to the values that scalar evolution does not track
  bpf: Compute scalar evolution expressions for whole subprogs
  bpf: Mark the attr argument of bpf_sys_bpf() as MEM_WRITE
  bpf: Check writes to the stack against bpf_may_write_mask()
  bpf: Detect a dead branch when a range and var_off don't overlap
  bpf: Don't treat half of a 64-bit spill as a 32-bit spill on big
    endian
  bpf: Refine registers linked by scalar evolution at conditional jumps
  selftests/bpf: Test registers linked by scalar evolution
  bpf: Recompute a pointer after the jump that bounds its index
  selftests/bpf: Test a pointer computed before its index is bounded
  bpf: Find a copy of an induction variable without scalar ids
  bpf: Find linked registers in the basic blocks of irreducible loops
  bpf: Remove sync_linked_regs(), refine by scalar evolution only
  bpf: Recognize copies of a scalar by their ranges in
    flow_join_makes_up()
  bpf: Stop assigning ids to scalars
  bpf: Remove scalar ids from regsafe()
  bpf: Remove scalar ids from the join of states
  bpf: Remove scalar ids from the log and from bpf_verifier.h
  bpf: Support sign-extended 32-bit linear scalar evolution
  selftests/bpf: Test loops with a sign-extended 32-bit induction
    variable

Vineet Gupta (2):
  bpf: Keep the 32-bit range across a no-op sign extension
  selftests/bpf: Test sign extensions of a range and of a linked
    register

 include/linux/bpf_verifier.h                  |   53 +-
 kernel/bpf/flow.c                             |   15 +-
 kernel/bpf/join.c                             |   54 +-
 kernel/bpf/liveness.c                         |   13 +
 kernel/bpf/log.c                              |   10 +-
 kernel/bpf/scev.c                             | 1594 +++++++++++++----
 kernel/bpf/states.c                           |  127 +-
 kernel/bpf/syscall.c                          |    2 +-
 kernel/bpf/verifier.c                         |  593 +++---
 .../selftests/bpf/prog_tests/reg_bounds.c     |    5 +-
 .../selftests/bpf/progs/verifier_arena.c      |   70 +
 .../bpf/progs/verifier_array_access.c         |    2 +-
 .../selftests/bpf/progs/verifier_bounds.c     |   37 +-
 .../bpf/progs/verifier_bounds_step.c          |    6 +-
 .../bpf/progs/verifier_direct_packet_access.c |    2 +-
 .../bpf/progs/verifier_linked_scalars.c       |    5 +-
 .../selftests/bpf/progs/verifier_loop_latch.c |    8 +-
 .../selftests/bpf/progs/verifier_movsx.c      |  186 ++
 .../selftests/bpf/progs/verifier_raw_stack.c  |   35 +
 .../selftests/bpf/progs/verifier_reg_equal.c  |   11 +-
 .../selftests/bpf/progs/verifier_regalloc.c   |    2 +-
 .../selftests/bpf/progs/verifier_scalar_ids.c |   70 +-
 .../selftests/bpf/progs/verifier_scev.c       |  321 +++-
 .../selftests/bpf/progs/verifier_spill_fill.c |   31 +
 24 files changed, 2147 insertions(+), 1105 deletions(-)

-- 
2.55.0


^ permalink raw reply	[flat|nested] 37+ messages in thread
end of thread, other threads:[~2026-11-09 18:16 UTC | newest]

Thread overview: 37+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-09  6:46 [PATCH bpf-next 00/26] bpf: Find linked registers by scalar evolution, remove scalar ids Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 01/26] bpf: Keep the 32-bit range across a no-op sign extension Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 02/26] bpf: Model 32-bit shifts and divisions exactly in scalar evolution Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 03/26] bpf: Construct scalar evolution expressions without allocations Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 04/26] bpf: Don't join dead registers in scalar evolution Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 05/26] bpf: Simplify scalar evolution expressions at construction Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 06/26] bpf: Give SSA names to the values that scalar evolution does not track Alexei Starovoitov
2026-11-09  7:45   ` bot+bpf-ci
2026-11-09  6:46 ` [PATCH bpf-next 07/26] bpf: Compute scalar evolution expressions for whole subprogs Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 08/26] bpf: Mark the attr argument of bpf_sys_bpf() as MEM_WRITE Alexei Starovoitov
2026-11-09  7:17   ` bot+bpf-ci
2026-11-09  6:46 ` [PATCH bpf-next 09/26] bpf: Check writes to the stack against bpf_may_write_mask() Alexei Starovoitov
2026-11-09  7:42   ` sashiko-bot
2026-11-09  6:46 ` [PATCH bpf-next 10/26] bpf: Detect a dead branch when a range and var_off don't overlap Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 11/26] bpf: Don't treat half of a 64-bit spill as a 32-bit spill on big endian Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 12/26] bpf: Refine registers linked by scalar evolution at conditional jumps Alexei Starovoitov
2026-11-09  7:41   ` sashiko-bot
2026-11-09  7:45   ` bot+bpf-ci
2026-11-09  6:46 ` [PATCH bpf-next 13/26] selftests/bpf: Test registers linked by scalar evolution Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 14/26] selftests/bpf: Test sign extensions of a range and of a linked register Alexei Starovoitov
2026-11-09  6:46 ` [PATCH bpf-next 15/26] bpf: Recompute a pointer after the jump that bounds its index Alexei Starovoitov
2026-11-09  7:32   ` sashiko-bot
2026-11-09  6:47 ` [PATCH bpf-next 16/26] selftests/bpf: Test a pointer computed before its index is bounded Alexei Starovoitov
2026-11-09  6:47 ` [PATCH bpf-next 17/26] bpf: Find a copy of an induction variable without scalar ids Alexei Starovoitov
2026-11-09  7:30   ` bot+bpf-ci
2026-11-09  6:47 ` [PATCH bpf-next 18/26] bpf: Find linked registers in the basic blocks of irreducible loops Alexei Starovoitov
2026-11-09  6:47 ` [PATCH bpf-next 19/26] bpf: Remove sync_linked_regs(), refine by scalar evolution only Alexei Starovoitov
2026-11-09  6:47 ` [PATCH bpf-next 20/26] bpf: Recognize copies of a scalar by their ranges in flow_join_makes_up() Alexei Starovoitov
2026-11-09  6:47 ` [PATCH bpf-next 21/26] bpf: Stop assigning ids to scalars Alexei Starovoitov
2026-11-09  7:08   ` sashiko-bot
2026-11-09  6:47 ` [PATCH bpf-next 22/26] bpf: Remove scalar ids from regsafe() Alexei Starovoitov
2026-11-09  7:06   ` sashiko-bot
2026-11-09  6:47 ` [PATCH bpf-next 23/26] bpf: Remove scalar ids from the join of states Alexei Starovoitov
2026-11-09  6:47 ` [PATCH bpf-next 24/26] bpf: Remove scalar ids from the log and from bpf_verifier.h Alexei Starovoitov
2026-11-09  6:47 ` [PATCH bpf-next 25/26] bpf: Support sign-extended 32-bit linear scalar evolution Alexei Starovoitov
2026-11-09  6:47 ` [PATCH bpf-next 26/26] selftests/bpf: Test loops with a sign-extended 32-bit induction variable Alexei Starovoitov
2026-11-09 18:16 ` [PATCH bpf-next 00/26] bpf: Find linked registers by scalar evolution, remove scalar ids Alexei Starovoitov

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