Re: [PATCH bpf 26/81] bpf: Support BPF_REG_ARENA_SP in the verifier

["Alexei Starovoitov" <alexei.starovoitov@gmail.com>]

On Mon, Oct 26, 2026 at 5:18 PM Kumar Kartikeya Dwivedi <memxor@gmail.com> wrote:
> Overall, I think it is less clear to me (or anyone looking at patches)
> as to why you did things this way.

point taken.

I was wrong in my previous email. An iterator over kernel objects
stays in the r10 stack, and it works today.

> Are there real patterns that existing stack tracking simply cannot
> salvage?

Yes.

Pattern 1: one insn, two kinds of memory

  sum(&local_array)     r1 = fp-64    --+
                                        +-->  r2 = *(u64 *)(r1 + 0)
  sum(&vec)             r1 = arena    --+
                                              one insn, one JIT form

We discussed an idea to let llvm clone such function.
I tried it, and it didn't work.
Short summary:

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

and real case in <&PanicInfo as Display>::fmt().

Pattern 2: the address of a local goes to memory, a load gives a scalar

That's typical rust heap.

Pattern 3: LLVM removes a bounds check, here in core::fmt::num

  loop { remain /= 10000; offset -= 4; buf[offset] = ...; }

and 'buf' is on stack.
run-time clamp won't help, since real tracked spill/fills are in r10.

Pattern 4: fp in an argument

...

So an address-taken local must be where the heap is... in arena.

experiments for arena-stack

  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, sp in a per-cpu cell       preemption, see below
- arena stack, sp in bpf_run_ctx          load, add, store in each function
- arena stack, sp in a hidden argument    an argument and a callee saved
                                          register. BTF does not match
- arena stack, sp in a reserved r9        a verifier change too, and one
                                          register less for the prog
- arena stack, sp in r12, the kernel      the series. It costs verifier
  supplies the stack                      code and a register in each JIT

The choices made for this arena-stack design:

  in the series                    what was rejected and why
  -------------------------------  ----------------------------------------
- one 'r12 += N', the first insn   'r12 -= rX': the depth has no bound
  of a function                    several 'r12 += imm': verifier state
- the verifier tracks nothing      tracked slots: a store through a scalar
                                     invalidates them
- 'rX = r12' gives a scalar        PTR_TO_ARENA: after a load from memory
                                     it is a scalar. Two types at one insn
- the cast of a kernel pointer is  an error: two progs cannot share
  a move (patch 18)                  fill(&mut Event), ring buffer and Box
- the kernel supplies the stacks,  compiler, libbpf: the entry code is in
  one set for each arena             each object file
- contiguous, 32 Kbyte at most,    fixed, 4 per cpu: 512 Mbyte of addresses
  pages at the first use           segments: each function can fail
                                   pages on a fault: can fail in mid-run
- regular arena pages              hidden from user space: no gain. It can
                                     corrupt all other data of the prog
- a run takes the per-cpu stack:   preemption off: no sleepable progs
  a counter, local xadd. If it is  two calls, get and put: 4 nsec
  taken: one of 16 more stacks,    split, sleepable or not: two mechanisms
  then new pages                   skip the second run: not for a scheduler
- grows up: r12 - off, like r10    down, r12 + off: harder to read
- x86-64: R9. Arg 6 of a BPF call  reject 6 arguments: Rust has them
  is on the stack                  r12 in a frame slot: a load per access
- a callback takes its own stack   reject r12 there: scx_central needs it
- bpf_throw() keeps the stack:     a slot in the frame of main: an irq
  the kernel frees the arena as      overwrites it after rsp = rbp
  a whole, and Rust unwinds        give back first: no record of new pages

> It might require teaching the compiler not to move certain types on
> the stack to r12 relative accesses, but it just feels ugly.

it might feel fragile, but it worked for huge corpus of rust crates:
https://github.com/llvm/llvm-project/pull/235577

Your dsq iterator exapmle is 'alloca [48 x i8]' in the IR, so it works
(I replied too soon yesteday).

llvm selects the stack by use: 

  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

> For certain things, like open coded iterators on kernel collections,
> there is no other choice.

Of the 16 rust sched that I hacked 4 walk dsq and 13 call
bpf_local_irq_save(). In testing they loaded and *run*.

But I agree that passing them around is fragile.
The hope is for typed arena to save the day.
Then rule 2 will go away.

> unsure how various assumptions around address contiguity get affected
> when stack reuse occurs [...]

A local never changes its stack, and it is contiguous. The compiler selects
the stack after all IR optimizations, for the full alloca and
its full life. r12 locals have a stack id of their own, and stack coloring merges
only objects with the same id. An iterator in one scope and a buffer in the
next are two allocas, one in each stack.