bpf: Don't trust pointers spilled in slots that a callee can write

arg_track follows pointers to the stack through registers and spills.
Scalar evolution and the removal of dead slots rely on it to know which
slots an insn reads and writes.

arg_track assumes that a call does not change the pointers that are spilled
in the frame of the caller. But a static subprog or a callback can store
a pointer to other memory there, and the caller can use it:

  *(u64 *)(r10 - 16) = fp-8
  r1 = fp-16, r2 = map_value
  call sub                        ; *(u64 *)(r1 + 0) = r2
  r7 = *(u64 *)(r10 - 16)         ; verifier: map_value. arg_track: fp-8
  *(u64 *)(r10 - 8) = fp-24
  *(u64 *)(r7 + 0) = 0            ; arg_track: fp-8 is overwritten
  r8 = *(u64 *)(r10 - 8)          ; verifier: fp-24. arg_track: none
  loop:
    r1 = *(u64 *)(r10 - 24)       ; the counter of the loop
    ...
    *(u64 *)(r8 + 0) = 4096       ; arg_track: not a write to fp-24

Scalar evolution does not see the last store. It gives the counter the
range of a loop that only increments it. The prog loads, and it accesses
a map value out of bounds.

Valid progs are rejected as well. The store through r7 makes fp-8 dead, and
a later read of fp-8 fails with "slot poisoned by dead code elimination".

When a static subprog or a callback can get a pointer to the frame of its
caller, join every slot of that frame with "not a pointer to the stack".
Reads and possible writes through a filled pointer are still seen, but no
store through it is a certain write. It has to be every slot: the callee
reaches the whole frame from one pointer, and callees are analyzed after
the caller. The price is precision: an 8-byte load through a filled
pointer gives a value that can point to any frame.

For a spilled copy of r10 this needs "bpf: Fix the join of fp+0 with
a value that is not a pointer to stack".

In selftests, Cilium and sched_ext the stack marks change in 4 of 12522
progs. Verdicts, insns and states do not change in any prog.

one_fp_clear_stack_threshold and two_fp_clear_stack_threshold expect the
fake offset fp+0 in the log now.

Fixes: bf0c571f7feb ("bpf: introduce forward arg-tracking dataflow analysis")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261102055913.3598414-4-alexei.starovoitov@gmail.com

0 files changed, 0 insertions, 0 deletions