bpf: Add callx calls to the call graph

The callee of callx is known to the main verifier pass only, but
sort_subprogs_topo() (recursion check) and check_max_stack_depth()
(stack size, number of frames, tail_call_reachable, private stack) need
the call graph. Both treat ld_imm64 BPF_PSEUDO_FUNC as a call from
the subprog that takes the address, which is not where callx calls it:

  main:  r1 = foo ll; call bar
  bar:   callx r1

The call chain is main -> bar -> foo, but only main -> bar and
main -> foo are seen.

Record caller -> callee edge in a bitmap when the main pass processes
callx. It explores all feasible paths, so all feasible edges are there.
Then:

- rerun sort_subprogs_topo() after the main pass with callx edges.
  Unbounded recursion is already rejected by the frame limit. This one
  catches bounded recursion via callx, same as direct recursion.
  The call graph is not context sensitive: foo() that calls bar() via
  callx and bar() that calls foo() is a recursion even if it never
  happens in the same call chain.

- check_max_stack_depth_subprog() walks all recorded callees at each
  callx.

The same goes for sync callbacks. The address of a callback may be
taken in one subprog and passed to a helper in another one:

  main:  r1 = cb ll; call bar
  bar:   r2 = r1; call bpf_loop

Only main -> cb was accounted. Record caller -> callback edge in
push_callback_call() and walk the edges at helper and kfunc calls
that call callbacks too.

JITs pass tail call counter to the callee in a register. callx doesn't.
Reject tail_call_reachable callees of callx.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924031042.1690890-7-alexei.starovoitov@gmail.com

1 files changed, 7 insertions, 0 deletions

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 6380c851ed24..931f305fa440 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -965,6 +965,13 @@ struct bpf_verifier_env {
 	struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 2]; /* max + 2 for the fake and exception subprogs */
 	/* subprog indices sorted in topological order: leaves first, callers last */
 	int subprog_topo_order[BPF_MAX_SUBPROGS + 2];
+	/*
+	 * Call graph edges created by callx instructions. A bitmap of
+	 * subprog_cnt * subprog_cnt bits, where bit (caller * subprog_cnt + callee)
+	 * is set when the main verification pass sees 'caller' calling 'callee'
+	 * via callx. Allocated when the first such edge is recorded.
+	 */
+	unsigned long *callx_edges;
 	union {
 		struct bpf_idmap idmap_scratch;
 		struct bpf_idset idset_scratch;