[RFC PATCH v1 02/14] bpf: Process global subprog's exception propagation

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

Global subprogs are not descended during symbolic execution, but we
summarized whether they can throw an exception (reachable from another
exception throwing subprog) in mark_exception_reachable_subprogs added
by the previous patch.

We must now ensure that we explore the path of the program where
invoking the call instruction leads to an exception being thrown, so
that we can correctly reject programs where it is not permissible to
throw an exception.  For instance, it might be permissible to throw from
a global subprog, but its caller may hold references. Without this
patch, the verifier will accept such programs.

To do this, we use push_stack to push a separate branch into the branch
stack of the verifier, with the same current and previous insn_idx.
Then, we set a bit in the verifier state of the branch to indicate that
the next instruction it will process is of a global subprog call which
will throw an exception. When we encounter this instruction, this bit
will be cleared.

Special care must be taken to update the state pruning logic, as without
any changes, it is possible that we end up pruning when popping the
exception throwing state for exploration. Therefore, while we can never
have the 'global_subprog_call_exception' bit set in the verifier state
of an explored state, we will see it in the current state, and use this
to reject pruning requests and continue its exploration.

Note that we process the exception after processing the call
instruction, similar to how we do a process_bpf_exit_full jump in case
of bpf_throw kfuncs.

Fixes: f18b03fabaa9 ("bpf: Implement BPF exceptions")
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 22 ++++++++++++++++++++++
 2 files changed, 23 insertions(+)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 1d666b6c21e6..5482701e6ad9 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -426,6 +426,7 @@ struct bpf_verifier_state {
 	 * while they are still in use.
 	 */
 	bool used_as_loop_entry;
+	bool global_subprog_call_exception;
 
 	/* first and last insn idx of this verifier state */
 	u32 first_insn_idx;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index bba53c4e3a0c..622c638b123b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1418,6 +1418,7 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state,
 	dst_state->dfs_depth = src->dfs_depth;
 	dst_state->callback_unroll_depth = src->callback_unroll_depth;
 	dst_state->used_as_loop_entry = src->used_as_loop_entry;
+	dst_state->global_subprog_call_exception = src->global_subprog_call_exception;
 	for (i = 0; i <= src->curframe; i++) {
 		dst = dst_state->frame[i];
 		if (!dst) {
@@ -9497,6 +9498,15 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 
 		verbose(env, "Func#%d ('%s') is global and assumed valid.\n",
 			subprog, sub_name);
+		if (subprog_info(env, subprog)->is_throw_reachable && !env->cur_state->global_subprog_call_exception) {
+			struct bpf_verifier_state *branch = push_stack(env, env->insn_idx, env->prev_insn_idx, false);
+
+			if (!branch) {
+				verbose(env, "verifier internal error: cannot push branch to explore exception of global subprog\n");
+				return -EFAULT;
+			}
+			branch->global_subprog_call_exception = true;
+		}
 		/* mark global subprog for verifying after main prog */
 		subprog_aux(env, subprog)->called = true;
 		clear_caller_saved_regs(env, caller->regs);
@@ -9505,6 +9515,9 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		mark_reg_unknown(env, caller->regs, BPF_REG_0);
 		caller->regs[BPF_REG_0].subreg_def = DEF_NOT_SUBREG;
 
+		if (env->cur_state->global_subprog_call_exception)
+			verbose(env, "Func#%d ('%s') may throw exception, exploring program path where exception is thrown\n",
+				subprog, sub_name);
 		/* continue with next insn after call */
 		return 0;
 	}
@@ -16784,6 +16797,10 @@ static bool states_equal(struct bpf_verifier_env *env,
 	if (old->active_rcu_lock != cur->active_rcu_lock)
 		return false;
 
+	/* Prevent pruning to explore state where global subprog call throws an exception. */
+	if (cur->global_subprog_call_exception)
+		return false;
+
 	/* for states to be equal callsites have to be the same
 	 * and all frame states need to be equivalent
 	 */
@@ -17675,6 +17692,11 @@ static int do_check(struct bpf_verifier_env *env)
 				}
 				if (insn->src_reg == BPF_PSEUDO_CALL) {
 					err = check_func_call(env, insn, &env->insn_idx);
+					if (!err && env->cur_state->global_subprog_call_exception) {
+						env->cur_state->global_subprog_call_exception = false;
+						exception_exit = true;
+						goto process_bpf_exit_full;
+					}
 				} else if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
 					err = check_kfunc_call(env, insn, &env->insn_idx);
 					if (!err && is_bpf_throw_kfunc(insn)) {
-- 
2.40.1