[PATCH bpf-next v5 3/5] bpf: Add helper to detect indirect jump targets

[Xu Kuohai]

From: Xu Kuohai <xukuohai@xxxxxxxxxx>

Introduce helper bpf_insn_is_indirect_target to determine whether a BPF
instruction is an indirect jump target. This helper will be used by
follow-up patches to decide where to emit indirect landing pad instructions.

Add a new flag to struct bpf_insn_aux_data to mark instructions that are
indirect jump targets. The BPF verifier sets this flag, and the helper
checks it to determine whether an instruction is an indirect jump target.

Also add a new field to struct bpf_insn_aux_data to track the instruction
final index in the bpf prog, as the instructions may be rewritten by
constant blinding in the JIT stage. This field is used as a binary search
key to find the corresponding insn_aux_data for a given instruction.

Signed-off-by: Xu Kuohai <xukuohai@xxxxxxxxxx>
---
 include/linux/bpf.h          |  2 ++
 include/linux/bpf_verifier.h | 10 ++++++----
 kernel/bpf/core.c            | 38 +++++++++++++++++++++++++++++++++---
 kernel/bpf/verifier.c        | 13 +++++++++++-
 4 files changed, 55 insertions(+), 8 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 05b34a6355b0..90760e250865 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1541,6 +1541,8 @@ bool bpf_has_frame_pointer(unsigned long ip);
 int bpf_jit_charge_modmem(u32 size);
 void bpf_jit_uncharge_modmem(u32 size);
 bool bpf_prog_has_trampoline(const struct bpf_prog *prog);
+bool bpf_insn_is_indirect_target(const struct bpf_verifier_env *env, const struct bpf_prog *prog,
+				 int insn_idx);
 #else
 static inline int bpf_trampoline_link_prog(struct bpf_tramp_link *link,
 					   struct bpf_trampoline *tr,
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index c1e30096ea7b..f8f70e5414f0 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -577,16 +577,18 @@ struct bpf_insn_aux_data {
 
 	/* below fields are initialized once */
 	unsigned int orig_idx; /* original instruction index */
-	bool jmp_point;
-	bool prune_point;
+	unsigned int final_idx; /* final instruction index */
+	u32 jmp_point:1;
+	u32 prune_point:1;
 	/* ensure we check state equivalence and save state checkpoint and
 	 * this instruction, regardless of any heuristics
 	 */
-	bool force_checkpoint;
+	u32 force_checkpoint:1;
 	/* true if instruction is a call to a helper function that
 	 * accepts callback function as a parameter.
 	 */
-	bool calls_callback;
+	u32 calls_callback:1;
+	u32 indirect_target:1; /* if it is an indirect jump target */
 	/*
 	 * CFG strongly connected component this instruction belongs to,
 	 * zero if it is a singleton SCC.
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 7702c232c62e..9a760cf43d68 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -1486,13 +1486,41 @@ static void adjust_insn_arrays(struct bpf_prog *prog, u32 off, u32 len)
 #endif
 }
 
+static int bpf_insn_aux_cmp_by_insn_idx(const void *a, const void *b)
+{
+	int insn_idx = *(int *)a;
+	int final_idx = ((const struct bpf_insn_aux_data *)b)->final_idx;
+
+	return insn_idx - final_idx;
+}
+
+bool bpf_insn_is_indirect_target(const struct bpf_verifier_env *env, const struct bpf_prog *prog,
+				 int insn_idx)
+{
+	struct bpf_insn_aux_data *insn_aux;
+	int func_idx, subprog_start, subprog_end;
+
+	if (!env)
+		return false;
+
+	func_idx = prog->aux->func_idx;
+	subprog_start = env->subprog_info[func_idx].start;
+	subprog_end = env->subprog_info[func_idx + 1].start;
+
+	insn_aux = bsearch(&insn_idx, &env->insn_aux_data[subprog_start],
+			   subprog_end - subprog_start,
+			   sizeof(struct bpf_insn_aux_data), bpf_insn_aux_cmp_by_insn_idx);
+
+	return insn_aux && insn_aux->indirect_target;
+}
+
 struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bpf_prog *prog)
 {
 	struct bpf_insn insn_buff[16], aux[2];
 	struct bpf_prog *clone, *tmp;
-	int insn_delta, insn_cnt;
+	int insn_delta, insn_cnt, subprog_start;
 	struct bpf_insn *insn;
-	int i, rewritten;
+	int i, j, rewritten;
 
 	if (!prog->blinding_requested || prog->blinded)
 		return prog;
@@ -1503,8 +1531,10 @@ struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bp
 
 	insn_cnt = clone->len;
 	insn = clone->insnsi;
+	subprog_start = env->subprog_info[prog->aux->func_idx].start;
 
-	for (i = 0; i < insn_cnt; i++, insn++) {
+	for (i = 0, j = 0; i < insn_cnt; i++, j++, insn++) {
+		env->insn_aux_data[subprog_start + j].final_idx = i;
 		if (bpf_pseudo_func(insn)) {
 			/* ld_imm64 with an address of bpf subprog is not
 			 * a user controlled constant. Don't randomize it,
@@ -1512,6 +1542,8 @@ struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bp
 			 */
 			insn++;
 			i++;
+			j++;
+			env->insn_aux_data[subprog_start + j].final_idx = i;
 			continue;
 		}
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1d2d42078ddf..5f08d521e58a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3971,6 +3971,11 @@ static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
 	return env->insn_aux_data[insn_idx].jmp_point;
 }
 
+static void mark_indirect_target(struct bpf_verifier_env *env, int idx)
+{
+	env->insn_aux_data[idx].indirect_target = true;
+}
+
 #define LR_FRAMENO_BITS	3
 #define LR_SPI_BITS	6
 #define LR_ENTRY_BITS	(LR_SPI_BITS + LR_FRAMENO_BITS + 1)
@@ -20943,12 +20948,14 @@ static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *in
 	}
 
 	for (i = 0; i < n - 1; i++) {
+		mark_indirect_target(env, env->gotox_tmp_buf->items[i]);
 		other_branch = push_stack(env, env->gotox_tmp_buf->items[i],
 					  env->insn_idx, env->cur_state->speculative);
 		if (IS_ERR(other_branch))
 			return PTR_ERR(other_branch);
 	}
 	env->insn_idx = env->gotox_tmp_buf->items[n-1];
+	mark_indirect_target(env, env->insn_idx);
 	return 0;
 }
 
@@ -22817,6 +22824,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 		num_exentries = 0;
 		insn = func[i]->insnsi;
 		for (j = 0; j < func[i]->len; j++, insn++) {
+			env->insn_aux_data[subprog_start + j].final_idx = j;
 			if (BPF_CLASS(insn->code) == BPF_LDX &&
 			    (BPF_MODE(insn->code) == BPF_PROBE_MEM ||
 			     BPF_MODE(insn->code) == BPF_PROBE_MEM32 ||
@@ -26088,8 +26096,11 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 
 	/* constants blinding in the JIT may increase prog->len */
 	len = env->prog->len;
-	if (env->subprog_cnt == 1)
+	if (env->subprog_cnt == 1) {
+		for (i = 0; i < len; i++)
+			env->insn_aux_data[i].final_idx = i;
 		env->prog = bpf_prog_select_jit(env, env->prog, &ret);
+	}
 
 	adjust_btf_func(env);
 
-- 
2.47.3