BPF List
 help / color / mirror / Atom feed
* [PATCH bpf-next v3 00/14] bpf: A stack in arena
@ 2026-11-04  1:23 Alexei Starovoitov
  2026-11-04  1:23 ` [PATCH bpf-next v3 01/14] libbpf: Make arena 4 Gbyte when max_entries is not set Alexei Starovoitov
                   ` (15 more replies)
  0 siblings, 16 replies; 32+ messages in thread
From: Alexei Starovoitov @ 2026-11-04  1:23 UTC (permalink / raw)
  To: bpf; +Cc: daniel, andrii, eddyz87, memxor

From: Alexei Starovoitov <ast@kernel.org>

The goal is to load Rust programs as rustc and LLVM compile them. The test
programs are in https://github.com/4ast/rust-bpf

This is part 2 of "bpf: Stack in arena and a verifier that joins states"
[1], as a series of its own. Part 1 is merged. This series does not depend
on part 3, and it does not change the main pass of the verifier.

The problem
===========

A Rust reference does not say where the object is:

  struct Node<'a> { val: u32, next: Option<&'a Node<'a>> }

  static IN_RODATA: Node = Node { val: 3, next: None };

  fn sum(mut node: Option<&Node>) -> u32 {
      let mut sum = 0;
      while let Some(n) = node { sum += n.val; node = n.next; }
      sum
  }

  let heap = Box::new(Node { val: 20, next: Some(&IN_RODATA) });
  let local = Node { val: 100, next: Some(&*heap) };
  sum(Some(&local));

sum() reads the three nodes with the same two insns:

     local            heap          IN_RODATA
  +---------+      +---------+      +---------+
  | next  --+----->| next  --+----->| None    |
  | 100     |      | 20      |      | 3       |
  +---------+      +---------+      +---------+
       ^                ^                ^
       +----------------+----------------+
                        |
          w0 = *(u32 *)(r1 + 8)      n.val
          r1 = *(u64 *)(r1 + 0)      n.next

These two insns must work for the three areas. Hence the decisions:

  step  memory               where  why
  ----  -------------------  -----  ---------------------------------------
  1     heap                 arena  The prog allocates it and links it with
                                    plain pointers.
  2     .data .bss .rodata   arena  heap.next is a load from arena, so it's
                                    a number. A number can be an address in
                                    arena and nothing else.
  3     address-taken local  arena  r1 is &local, then heap.next. One insn
                                    has one form in JIT.
  4     the rest of the      r10    The verifier doesn't track arena, and
        stack                       user space writes to it.

The size is the second reason. Rust progs routinely need 32 Kbyte of stack.
The kernel stack cannot supply them. The private stack has one frame for
each function and cpu. Thus it supports neither recursion nor a second run
on the same cpu.

The patterns in real code that the tracking of the r10 stack cannot handle:

 1. One insn, two kinds of memory.

      sum(&local_array)     r1 = fp-64    --+
                                            +-->  r2 = *(u64 *)(r1 + 0)
      sum(&vec)             r1 = arena    --+

    A copy of the function for each kind of memory does not help:

      case                               why
      ---------------------------------  ----------------------------------
      the pointer comes from memory      no kind for the compiler, a number
                                         for the verifier
      an indirect call: &dyn Trait, fmt  one function for the two kinds
      if c { &local } else { &*boxed }   one pointer, two kinds
      n pointer arguments                up to 2^n copies

    For example, core::fmt::num writes the digits to a local array. It
    passes a part of the array as &str to Formatter::pad_integral(), which
    calls write_str() of a &mut dyn Write. The same write_str() gets
    strings from .rodata and from the heap.

 2. The address of a local goes to memory. A load gives a number. The
    memory can be the heap, when the object in the heap is dropped first:

      let x = [1, 2, 3];
      let v: Vec<&i32> = x.iter().collect();

The design
==========

The series adds a second stack, in arena. A new register, r12
(BPF_REG_ARENA_SP), points to it.

      kernel memory                     arena
  +---------------------+      +--------------------------+
  | BPF stack    <- r10 |      | heap, statics            |
  |                     |      +--------------------------+
  |  spilled registers  |      | stack in arena    <- r12 |
  |  other locals       |      |                          |
  |                     |      |  locals whose address    |
  +---------------------+      |  the prog takes          |
                               +--------------------------+
  The verifier tracks          The verifier tracks nothing.
  each slot.                   An access cannot leave arena.

 - The compiler selects the stack for each local.
 - Each run of a prog takes a stack at its start and gives it back at its
   exit. The usual case is 8 and 4 insns without a call.
 - The verifier accepts r12 in four insns only: 'r12 += N' as the first
   insn of a function, a load, a store, and 'rX = r12'.
 - x86 and arm64 JITs support r12.

The other places for an address-taken local that were tried:

  where the local is                      what breaks it
  --------------------------------------  ---------------------------------
  structs by value, more inlining         an optimization. Pattern 2 stays
  a second vm area or arena, a map value  a different base: pattern 1
  arena, a fixed frame for each function  recursion, a second run on the
  and cpu, as in the private stack        same cpu
  arena stack, the kernel supplies it     this series

The logs of patches 8, 9, 11 and 12 give the reasons for the other
choices: where the stack pointer is, how a run gets a stack, what the
verifier accepts, and which x86 register r12 is.

The compiler
============

The compiler selects the stack by use, after all IR optimizations, for the
full local and its full life:

  rule 1   r10   The function that owns the local passes its address to
                 a helper or a kfunc: iterator, irq flag, dynptr, map key.
  rule 2   r10   The prog stores a kernel pointer in it and loads it again.
                 Also a local that holds the address of such a local.
  else     r12

Thus open coded iterators, bpf_local_irq_save() and dynptrs work as today.
When the compiler puts such a local in r12 by mistake, the prog does not
load: its address and what is loaded from it are numbers for the verifier.
It is not a memory error.

  what      clang for C today     with the flag, for Rust
  --------  --------------------  -----------------------------------------
  statics   __arena variables:    statics: .addr_space.1 and
            .addr_space.1         .bss.addr_space.1
  locals    r10                   r10 or r12
  casts     by type: __arena      by origin: one cast for each pointer that
            pointers              doesn't come from the kernel

  data in .rodata                  where
  -------------------------------  -------------
  statics of Rust                  arena
  tables of functions              read-only map
  strings for helpers and kfuncs   read-only map

The price: .rodata in arena is writable, and its values are not constants
for the verifier.

No released compiler emits this code. The change to the BPF backend of LLVM
is in review: https://github.com/llvm/llvm-project/pull/235577

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

  patches 1-2    The default size of arena.
  patches 3-4    addr_space_cast of a pointer that is not in arena. The
                 compiler casts a pointer when it does not know its origin.
  patches 5-7    Statics: .bss.addr_space.1, and pointers that are stored
                 in arena.
  patches 8-14   r12: the register, the stacks, the verifier, the JITs, the
                 tests.

Patches 8-14 do not change the code of progs without r12. A prog with r12
pays 0.3 to 2.3 nsec in each run on x86-64 (Zen 5) with hot caches. Loads,
stores and calls cost the same as with r10. Patches 9-12 have the tables.
Patch 3 changes the code of a prog in C only where the verifier finds a
kernel pointer at a cast.

v2 -> v3:
 - Rebased. The three fixes that v2 needed are merged. BPF CI could not
   apply v2 without them.
 - Patch 11: bpf_patch_insn_data() is gone. The code that takes a stack and
   gives it back goes through the list of deferred patches. A call that the
   verifier emits is marked in the insn (BPF_EMIT_KERNEL_CALL), not in
   insn_aux_data.
 - Patch 11: "bpf: End bpf_loop() when the time of may_goto is up" added
   is_called to struct bpf_subprog_info, for functions that BPF code calls
   and for callbacks of other helpers. A callback of another helper can
   take a stack, a function that BPF code calls cannot. The callbacks have
   a bit of their own now, is_other_cb.
 - Patch 8: BPF_REG_AX is r13 also in the tests of may_goto and of the
   patch list that were merged after v2.
 - Patch 14: three tests of may_goto in progs with r12. The test of callx
   is built when CAN_USE_CALLX is defined.
 - Patch 4: two tests: the cast of an untrusted kernel pointer is a move.
 - Patch 11: a call of the main prog is rejected, as a call of a callback
   that takes a stack.
 - Patches 2, 7 and 14: arena_default_size, arena_data_ptrs and arena_stack
   are serial, as the other tests in prog_tests/arena_*.c.
 - Patch 7: the test fails when .bss.addr_space.1 is not aligned.
 - Corrections in the logs of patches 3, 9, 11 and 14.
 - The log of patch 1 says why libbpf needs the default also when the
   kernel accepts 0 (Andrii, Kumar).
 - The cover letter has an example for pattern 2, and it says what happens
   when the compiler selects r12 by mistake (Kumar).
 - The code of patches 1, 3, 5, 6, 9, 10, 12 and 13 is the same.

v2: https://lore.kernel.org/bpf/20261101030511.1578690-1-alexei.starovoitov@gmail.com/

v1 -> v2:
 - A series of its own, on bpf-next.
 - The default size of arena is 4 Gbyte (Andrii, Kumar).
 - The cover letter and the logs give the reasons for the design (Kumar).
 - A cast that is a move has 64 bits. JITs that need explicit zero
   extension lost the upper half of the pointer (Ihor, CI on s390x).
 - callx of a callback that takes a stack is rejected, as a call is.
 - For the analysis of live stack slots the result of a cast is never
   a certain pointer to a slot. A store to arena counted as a write to the
   stack, and a prog with an access out of bounds loaded.
 - The code that takes a stack is added before gen_prologue() and
   gen_epilogue(). A BPF qdisc without a stack skipped the two.
 - BPF_LD_ABS and BPF_LD_IND are rejected in progs with r12.
 - gotox to the first insn of a function does not take a stack again.
   A call as the first insn of a callback keeps its target.
 - x86: bpf_throw() in a function with stack arguments restored the
   callee saved registers of the kernel from incorrect slots.
 - A slot for a stack does not name pages that are freed.
 - The static linker accepts pointers in arena to static variables.
 - arm64 is tested in QEMU.
 - bpf_alloc(), bpf_free(), bpf_arena_memcmp() and bpf_arena_memcpy() are
   not in the series.

[1] https://lore.kernel.org/bpf/20261026025943.404450-1-alexei.starovoitov@gmail.com/

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

Alexei Starovoitov (14):
  libbpf: Make arena 4 Gbyte when max_entries is not set
  selftests/bpf: Test the default size of arena
  bpf: Treat addr_space_cast of a pointer that is not in arena as a move
  selftests/bpf: Test addr_space_cast of pointers that are not in arena
  libbpf: Support .bss.addr_space.1 section
  libbpf: Relocate pointers that are stored in arena
  selftests/bpf: Test pointers in arena and .bss.addr_space.1
  bpf: Introduce bpf register BPF_REG_ARENA_SP
  bpf: Add stacks for programs to arena
  bpf, x86: Add BPF_ATOMIC_LOCAL
  bpf: Support BPF_REG_ARENA_SP in the verifier
  bpf, x86: Support BPF_REG_ARENA_SP
  bpf, arm64: Support BPF_REG_ARENA_SP
  selftests/bpf: Add tests for BPF_REG_ARENA_SP

 arch/arm64/net/bpf_jit_comp.c                 |   12 +
 arch/x86/net/bpf_jit_comp.c                   |  150 ++-
 include/linux/bpf.h                           |   32 +
 include/linux/bpf_verifier.h                  |   17 +-
 include/linux/filter.h                        |   72 +-
 kernel/bpf/arena.c                            |  142 ++
 kernel/bpf/backtrack.c                        |    2 +-
 kernel/bpf/const_fold.c                       |    7 +
 kernel/bpf/core.c                             |   34 +-
 kernel/bpf/disasm.c                           |    7 +
 kernel/bpf/fixups.c                           |  222 +++-
 kernel/bpf/liveness.c                         |   23 +-
 kernel/bpf/scev.c                             |    9 +-
 kernel/bpf/verifier.c                         |  248 +++-
 tools/lib/bpf/libbpf.c                        |  132 +-
 tools/lib/bpf/linker.c                        |   21 +-
 tools/testing/selftests/bpf/Makefile.skel     |    3 +-
 .../bpf/prog_tests/arena_data_ptrs.c          |   70 +
 .../bpf/prog_tests/arena_default_size.c       |   22 +
 .../selftests/bpf/prog_tests/arena_stack.c    |  323 +++++
 .../selftests/bpf/prog_tests/ctx_rewrite.c    |   14 +-
 .../selftests/bpf/prog_tests/pro_epilogue.c   |    2 +
 .../prog_tests/test_struct_ops_refcounted.c   |    2 +
 .../selftests/bpf/prog_tests/verifier.c       |    4 +
 .../selftests/bpf/progs/arena_data_ptrs.c     |  138 ++
 .../bpf/progs/arena_data_ptrs_fail.c          |   25 +
 .../selftests/bpf/progs/arena_default_size.c  |   21 +
 .../selftests/bpf/progs/arena_noarena.c       |   14 +
 .../testing/selftests/bpf/progs/arena_stack.c |  334 +++++
 .../selftests/bpf/progs/arena_stack_fentry.c  |   13 +
 .../selftests/bpf/progs/arena_stack_grow.c    |  151 +++
 .../selftests/bpf/progs/arena_stack_loop.c    |   77 ++
 .../selftests/bpf/progs/arena_stack_nomem.c   |   41 +
 .../selftests/bpf/progs/arena_stack_throw.c   |  110 ++
 .../bpf/progs/pro_epilogue_arena_stack.c      |  199 +++
 .../struct_ops_refcounted_fail__arena_stack.c |   61 +
 .../selftests/bpf/progs/verifier_arena_cast.c |  800 +++++++++++
 .../bpf/progs/verifier_arena_stack.c          | 1169 +++++++++++++++++
 .../bpf/progs/verifier_bpf_fastcall.c         |   24 +-
 .../selftests/bpf/progs/verifier_may_goto_1.c |   12 +-
 .../selftests/bpf/progs/verifier_patch_list.c |    6 +-
 .../selftests/bpf/progs/verifier_sdiv.c       |   64 +-
 .../selftests/bpf/verifier/basic_stx_ldx.c    |    4 +-
 43 files changed, 4721 insertions(+), 112 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/arena_data_ptrs.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/arena_default_size.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/arena_stack.c
 create mode 100644 tools/testing/selftests/bpf/progs/arena_data_ptrs.c
 create mode 100644 tools/testing/selftests/bpf/progs/arena_data_ptrs_fail.c
 create mode 100644 tools/testing/selftests/bpf/progs/arena_default_size.c
 create mode 100644 tools/testing/selftests/bpf/progs/arena_stack.c
 create mode 100644 tools/testing/selftests/bpf/progs/arena_stack_fentry.c
 create mode 100644 tools/testing/selftests/bpf/progs/arena_stack_grow.c
 create mode 100644 tools/testing/selftests/bpf/progs/arena_stack_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/arena_stack_nomem.c
 create mode 100644 tools/testing/selftests/bpf/progs/arena_stack_throw.c
 create mode 100644 tools/testing/selftests/bpf/progs/pro_epilogue_arena_stack.c
 create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_refcounted_fail__arena_stack.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_arena_cast.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_arena_stack.c


base-commit: 7b8b803c3ce6e961e9c32a166c7169fcb17da6d4
-- 
2.55.0


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

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

Thread overview: 32+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-04  1:23 [PATCH bpf-next v3 00/14] bpf: A stack in arena Alexei Starovoitov
2026-11-04  1:23 ` [PATCH bpf-next v3 01/14] libbpf: Make arena 4 Gbyte when max_entries is not set Alexei Starovoitov
2026-11-04  1:23 ` [PATCH bpf-next v3 02/14] selftests/bpf: Test the default size of arena Alexei Starovoitov
2026-11-04  1:23 ` [PATCH bpf-next v3 03/14] bpf: Treat addr_space_cast of a pointer that is not in arena as a move Alexei Starovoitov
2026-11-04  2:12   ` bot+bpf-ci
2026-11-04  2:32     ` Alexei Starovoitov
2026-11-04  1:23 ` [PATCH bpf-next v3 04/14] selftests/bpf: Test addr_space_cast of pointers that are not in arena Alexei Starovoitov
2026-11-04  1:40   ` sashiko-bot
2026-11-04  1:23 ` [PATCH bpf-next v3 05/14] libbpf: Support .bss.addr_space.1 section Alexei Starovoitov
2026-11-04  1:59   ` bot+bpf-ci
2026-11-04  1:23 ` [PATCH bpf-next v3 06/14] libbpf: Relocate pointers that are stored in arena Alexei Starovoitov
2026-11-04  1:44   ` sashiko-bot
2026-11-04  2:02     ` Alexei Starovoitov
2026-11-04  2:32       ` Roman Gushchin
2026-11-04  2:37         ` Alexei Starovoitov
2026-11-04  1:59   ` bot+bpf-ci
2026-11-04  2:30     ` Alexei Starovoitov
2026-11-04  1:23 ` [PATCH bpf-next v3 07/14] selftests/bpf: Test pointers in arena and .bss.addr_space.1 Alexei Starovoitov
2026-11-04  1:23 ` [PATCH bpf-next v3 08/14] bpf: Introduce bpf register BPF_REG_ARENA_SP Alexei Starovoitov
2026-11-04  1:23 ` [PATCH bpf-next v3 09/14] bpf: Add stacks for programs to arena Alexei Starovoitov
2026-11-04  1:23 ` [PATCH bpf-next v3 10/14] bpf, x86: Add BPF_ATOMIC_LOCAL Alexei Starovoitov
2026-11-04  1:23 ` [PATCH bpf-next v3 11/14] bpf: Support BPF_REG_ARENA_SP in the verifier Alexei Starovoitov
2026-11-04  2:12   ` bot+bpf-ci
2026-11-04  1:23 ` [PATCH bpf-next v3 12/14] bpf, x86: Support BPF_REG_ARENA_SP Alexei Starovoitov
2026-11-04  1:23 ` [PATCH bpf-next v3 13/14] bpf, arm64: " Alexei Starovoitov
2026-11-04  1:24 ` [PATCH bpf-next v3 14/14] selftests/bpf: Add tests for BPF_REG_ARENA_SP Alexei Starovoitov
2026-11-04  2:12   ` bot+bpf-ci
2026-11-04  2:29     ` Alexei Starovoitov
2026-11-04  3:31 ` [PATCH bpf-next v3 00/14] bpf: A stack in arena Alexei Starovoitov
2026-11-04  7:35   ` Kumar Kartikeya Dwivedi
2026-11-04 18:02     ` Alexei Starovoitov
2026-11-04 20:10 ` 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