Merge branch 'bpf-indirect-calls-of-bpf-subprogs-callx'

Alexei Starovoitov says:

====================
bpf: Indirect calls of bpf subprogs (callx)

From: Alexei Starovoitov <ast@kernel.org>

v1->v2:
- Dropped "bpf: Don't fold loads from insn_array maps into constants".
  bpf_map_direct_read() rejects insn_array already.
- patch 1: emit the same diag as sort_subprogs_topo() (bpf-ci).
- patch 3 is new: taking the address of a function that is never called
  hit verifier_bug() in jit_subprogs(). Not related to callx, but callx
  makes it likely.
- patch 4: BPF_OP() == BPF_CALL in liveness like in const_fold, explained
  in the comment why slots are live before callx callsite (Eduard).
- patch 5: moved !bpf_is_callx() into nested 'if' (Eduard). JIT support
  is checked before the type of the register.
- patch 6: sync callbacks are in the call graph too. Stack depth of
  a callback whose address is read from .rodata or taken in another
  subprog was not accounted.
- patch 10:
  . check_cfg() explores functions of a table one at a time. It was
    losing changes_pkt_data and other effects of the functions in
    a table that call each other.
  . no cmpxchg64(), it's not available on all 32-bit archs.
  . don't reject the prog that reads a pointer to a function that was
    removed as dead code (sashiko).
  . load of the pointer sets jit_required, so the prog that passes it to
    a helper as a callback can't run in the interpreter (bpf-ci).
  . tbl[i].data at variable offset is a regular load when none of
    the possible offsets overlaps with a pointer (bpf-ci).
- patch 12: append the functions and copy the map only for progs that
  have callx. The rest use .rodata as-is (bpf-ci). Pass token_fd to map
  create. Dropped dead bpf_map_lookup_elem() fallback.
- patch 14: light skeleton reserves fd_array slots only when the object
  has callx.
- selftests: anchored callx_retval_is_tracked to the caller, the tests
  of global func in a table and of const folding of the pointer test what
  they claim now, skip without JIT, fixed ASSERT_GT() of u32 and
  the comment, added tests for the above (bpf-ci). The table in
  callx_rodata_lskel test is volatile. clang was turning it into
  direct calls, so the test didn't test light skeleton.
- Added acks.
v1: https://lore.kernel.org/bpf/20260922011323.1298619-1-alexei.starovoitov@gmail.com/

Introduce BPF_JMP | BPF_CALL | BPF_X 'callx dst_reg' instruction: indirect
call of bpf subprog with address in a register. LLVM emits it for calls
via function pointer. The verifier rejected it as unknown opcode.

Only static subprogs can be called. The callee is verified in the context
of the caller like a direct call of static subprog. No callx into global
subprogs, helpers or kfuncs.

All callees are known before the main verifier pass. The address of
the callee comes from:

- ld_imm64 BPF_PSEUDO_FUNC, which is allowed for static subprogs only.
  add_subprogs() and check_cfg() see them already.

- 64-bit load from read-only data: tables of functions, struct ops,
  vtables, where pointers are mixed with other data. Rust needs that:

    r6 = vtable ll
    r1 = *(u64 *)(r6 + 0)      // data
    r2 = *(u64 *)(r6 + 8)      // pointer to a function
    callx r2

  libbpf keeps the data in a frozen read-only array map, one per prog
  that has callx, and stores byte offset of static function in the prog
  into the pointer. Progs without callx use .rodata as before.
  The kernel guesses pointers by that value before check_cfg() (patch 10).
  Wrong guess is safe. Functions referenced by data only are found via
  func_info (patch 9). After JIT the kernel replaces the offsets in
  the map with addresses. The prog must be the only user of the map,
  since other progs would have been verified with its old content. The
  prog reads addresses as data, so CAP_PERFMON is required.

Both produce PTR_TO_FUNC.

The passes before the main one don't know the callee and treat callx
conservatively (patch 4). The main pass records caller -> callee edges.
Recursion and stack depth checks use them afterwards (patch 6).

In C:

  static const struct shape_ops square_ops = { 1, area, 10, perimeter };
  ...
  return ops->area(x) * ops->scale + ops->perimeter(ops->id);

and

  static int (* const handlers[])(struct xdp_md *) = { foo, bar, baz };
  ...
  if (i < ARRAY_SIZE(handlers))
          return handlers[i](ctx);

plus what clang compiles without data: picking one of several functions,
passing a function pointer into another function.

Patches 1-3 are fixes I hit along the way: a prog without callx that
hangs bpf_prog_load() in check_max_stack_depth(), its test, and
verifier_bug() when the address of a function that is never called is
taken.

Not supported:
- JITs other than x86-64 and arm64. No interpreter support.
- x86-64 with FineIBT: bpf_jit_supports_callx() returns false.
- tail calls in callees of callx.
- pointers to functions in writable data, misaligned pointers.
====================

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

3 files changed, 53 insertions, 0 deletions

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index e7c5e203eddd..9525d3ecd923 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -344,8 +344,18 @@ struct bpf_map {
 	s64 __percpu *elem_count;
 	u64 cookie; /* write-once */
 	char *excl_prog_sha;
+	/*
+	 * Which programs use the map, see bpf_map_claim(): 0 - none so far,
+	 * aux of the program - only that one, the same with BPF_MAP_USER_PATCHED
+	 * set - only that one and it stored the addresses of its functions into
+	 * the map, BPF_MAP_USER_MANY - more than one.
+	 */
+	unsigned long user;
 };
 
+#define BPF_MAP_USER_MANY	1UL
+#define BPF_MAP_USER_PATCHED	1UL
+
 static inline const char *btf_field_type_name(enum btf_field_type type)
 {
 	switch (type) {
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 92f528c45605..578bccf5cf76 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -786,6 +786,21 @@ int bpf_log_attr_finalize(struct bpf_log_attr *attr, struct bpf_verifier_log *lo
 
 #define BPF_MAX_SUBPROGS 256
 
+/*
+ * A pointer to a static subprog in the value of a frozen read-only array map:
+ * a 64-bit value that is the offset in bytes of the first instruction of
+ * the subprog in the program.
+ */
+struct bpf_func_ptr {
+	struct bpf_map *map;
+	u32 map_off;		/* offset of the pointer in the value of the map */
+	u32 orig_off;		/* what the map has: the first instruction of the subprog */
+	u32 xlated_off;		/* the same after instructions were patched and removed */
+};
+
+/* the subprog that a bpf_func_ptr pointed to was removed as dead code */
+#define BPF_FUNC_PTR_DELETED ((u32)-1)
+
 struct bpf_subprog_arg_info {
 	enum bpf_arg_type arg_type;
 	union {
@@ -965,6 +980,20 @@ 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];
+	/*
+	 * Pointers to static subprogs found in frozen read-only maps of the
+	 * program, see resolve_func_ptrs(). Sorted by map and map_off.
+	 */
+	struct bpf_func_ptr *func_ptrs;
+	u32 func_ptr_cnt;
+	bool has_callx;
+	/*
+	 * 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;
@@ -1089,6 +1118,12 @@ static inline bool bpf_pseudo_kfunc_call(const struct bpf_insn *insn)
 	       insn->src_reg == BPF_PSEUDO_KFUNC_CALL;
 }
 
+/* callx: indirect call of a bpf subprog whose address is in insn->dst_reg */
+static inline bool bpf_is_callx(const struct bpf_insn *insn)
+{
+	return insn->code == (BPF_JMP | BPF_CALL | BPF_X);
+}
+
 __printf(2, 0) void bpf_verifier_vlog(struct bpf_verifier_log *log,
 				      const char *fmt, va_list args);
 __printf(2, 3) void bpf_verifier_log_write(struct bpf_verifier_env *env,
@@ -1311,6 +1346,13 @@ static inline bool bt_is_frame_slot_set(struct backtrack_state *bt, u32 frame, u
 }
 
 bool bpf_map_is_rdonly(const struct bpf_map *map);
+struct bpf_func_ptr *bpf_map_func_ptrs(struct bpf_verifier_env *env,
+				       const struct bpf_map *map, u32 *cnt);
+struct bpf_func_ptr *bpf_map_range_func_ptrs(struct bpf_verifier_env *env,
+					     const struct bpf_map *map,
+					     u64 off, u64 size, u32 *cnt);
+void bpf_adjust_func_ptrs(struct bpf_verifier_env *env, u32 off, u32 len);
+void bpf_adjust_func_ptrs_after_remove(struct bpf_verifier_env *env, u32 off, u32 len);
 int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val,
 			bool is_ldsx);
 
diff --git a/include/linux/filter.h b/include/linux/filter.h
index 422284b4fa96..4f0662e42897 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -1237,6 +1237,7 @@ bool bpf_jit_inlines_helper_call(s32 imm);
 bool bpf_jit_supports_subprog_tailcalls(void);
 bool bpf_jit_supports_percpu_insn(void);
 bool bpf_jit_supports_kfunc_call(void);
+bool bpf_jit_supports_callx(void);
 bool bpf_jit_supports_kfunc_ret_reg_pair(void);
 bool bpf_jit_supports_stack_args(void);
 bool bpf_jit_supports_arena_args(void);