[PATCH bpf-next v3 13/17] bpf: Report Program Structure CFG errors

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

Augment selected subprogram CFG validation failures with Program Structure
reports. These errors are structural rather than path-dependent, so the report
focuses on source and instruction context instead of causal history.

Cover jumps that leave the current subprogram, subprograms whose last
instruction can fall through into the next subprogram, and recursive bpf2bpf
call graph edges.

Format long jump-range reasons directly in diagnostics.c, and keep the
fallthrough suggestion aligned with the verifier check by suggesting exit or
explicit jumps.

Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/cfg.c         | 55 ++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/diagnostics.c | 19 ++++++++++++++
 kernel/bpf/diagnostics.h |  3 +++
 kernel/bpf/verifier.c    | 32 +++++++++++++++++++++++
 4 files changed, 109 insertions(+)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 26d37066465f..376f6b6d469c 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -5,6 +5,8 @@
 #include <linux/filter.h>
 #include <linux/sort.h>
 
+#include "diagnostics.h"
+
 #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)
 
 /* non-recursive DFS pseudo code
@@ -113,6 +115,12 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
 	if (w < 0 || w >= env->prog->len) {
 		verbose_linfo(env, t, "%d: ", t);
 		verbose(env, "jump out of range from insn %d to %d\n", t, w);
+		bpf_diag_report_program_structure(env, t, "jump out of range",
+						  "Keep branch targets inside the program.",
+						  "Instruction %d jumps to instruction %d, but the "
+						  "program only contains instructions 0 through "
+						  "%d.",
+						  t, w, env->prog->len - 1);
 		return -EINVAL;
 	}
 
@@ -136,6 +144,15 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
 		verbose_linfo(env, t, "%d: ", t);
 		verbose_linfo(env, w, "%d: ", w);
 		verbose(env, "back-edge from insn %d to %d\n", t, w);
+		bpf_diag_report_program_structure(env, t, "back-edge is not allowed",
+						  "Load with privileges that allow this back-edge, "
+						  "or rewrite "
+						  "the control flow so it does not branch "
+						  "backward.",
+						  "Instruction %d branches back to instruction %d. "
+						  "This program is being rejected without the "
+						  "privilege needed for this back-edge.",
+						  t, w);
 		return -EINVAL;
 	} else if (insn_state[w] == EXPLORED) {
 		/* forward- or cross-edge */
@@ -316,6 +333,14 @@ static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env,
 
 	if (!jt) {
 		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);
+		bpf_diag_report_program_structure(env, subprog_start, "missing jump table",
+						  "Make sure subprograms containing gotox "
+						  "instructions are "
+						  "accompanied by jump tables referencing these "
+						  "subprograms.",
+						  "No jump table was found for the subprogram that "
+						  "starts at instruction %u.",
+						  subprog_start);
 		return ERR_PTR(-EINVAL);
 	}
 
@@ -343,6 +368,13 @@ create_jt(int t, struct bpf_verifier_env *env)
 		if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) {
 			verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n",
 					t, subprog_start, subprog_end);
+			bpf_diag_report_program_structure(env, t, "jump table target out of range",
+							  "Keep every jump-table target inside the "
+							  "same subprogram.",
+							  "The jump table for instruction %d "
+							  "points outside subprogram range "
+							  "[%u,%u).",
+							  t, subprog_start, subprog_end);
 			kvfree(jt);
 			return ERR_PTR(-EINVAL);
 		}
@@ -374,6 +406,13 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)
 		w = jt->items[i];
 		if (w < 0 || w >= env->prog->len) {
 			verbose(env, "indirect jump out of range from insn %d to %d\n", t, w);
+			bpf_diag_report_program_structure(env, t, "indirect jump out of range",
+							  "Keep indirect jump targets inside the "
+							  "program.",
+							  "Instruction %d can jump indirectly to "
+							  "instruction %d, but the program only "
+							  "contains instructions 0 through %d.",
+							  t, w, env->prog->len - 1);
 			return -EINVAL;
 		}
 
@@ -624,12 +663,28 @@ int bpf_check_cfg(struct bpf_verifier_env *env)
 
 		if (insn_state[i] != EXPLORED) {
 			verbose(env, "unreachable insn %d\n", i);
+			bpf_diag_report_program_structure(env, i, "unreachable instruction",
+							  "Remove the unreachable instruction or "
+							  "add valid control flow that reaches it.",
+							  "Instruction %d is not reachable from "
+							  "the program entry point.",
+							  i);
 			ret = -EINVAL;
 			goto err_free;
 		}
 		if (bpf_is_ldimm64(insn)) {
 			if (insn_state[i + 1] != 0) {
 				verbose(env, "jump into the middle of ldimm64 insn %d\n", i);
+				bpf_diag_report_program_structure(env, i,
+								  "jump into ldimm64 immediate",
+								  "Target the first instruction of "
+								  "the ldimm64 pair, or "
+								  "restructure the jump target.",
+								  "Control flow reaches the second "
+								  "half of the ldimm64 instruction "
+								  "pair that starts at instruction "
+								  "%d.",
+								  i);
 				ret = -EINVAL;
 				goto err_free;
 			}
diff --git a/kernel/bpf/diagnostics.c b/kernel/bpf/diagnostics.c
index c90be89d4707..5496e7a0235b 100644
--- a/kernel/bpf/diagnostics.c
+++ b/kernel/bpf/diagnostics.c
@@ -1277,6 +1277,25 @@ void bpf_diag_ctx(struct bpf_verifier_env *env, enum bpf_diag_ctx_report report,
 		return;
 	}
 }
+
+void bpf_diag_report_program_structure(struct bpf_verifier_env *env, u32 insn_idx,
+				       const char *problem, const char *suggestion,
+				       const char *reason_fmt, ...)
+{
+	va_list args;
+
+	bpf_diag_report_header(env, CATEGORY_PROGRAM_STRUCTURE, problem);
+	diag_report_section(env, "Reason");
+
+	va_start(args, reason_fmt);
+	diag_vprint_indented(env, reason_fmt, args);
+	va_end(args);
+
+	diag_report_section(env, "At");
+	bpf_diag_report_source(env, insn_idx, "error", "%s", problem);
+
+	diag_report_suggestion(env, "%s", suggestion);
+}
 void bpf_diag_report_invalid_deref(struct bpf_verifier_env *env, u32 insn_idx, int regno,
 				   const char *reg_name, const struct bpf_reg_state *reg,
 				   enum bpf_diag_invalid_deref_kind kind, s64 offset)
diff --git a/kernel/bpf/diagnostics.h b/kernel/bpf/diagnostics.h
index f26432e84d9f..bb29f4235a68 100644
--- a/kernel/bpf/diagnostics.h
+++ b/kernel/bpf/diagnostics.h
@@ -168,6 +168,9 @@ void bpf_diag_report_call_type(struct bpf_verifier_env *env, u32 insn_idx, int a
 void bpf_diag_ctx(struct bpf_verifier_env *env, enum bpf_diag_ctx_report report, u32 insn_idx,
 		  const char *operation, enum bpf_diag_context_kind ctx_kind, const char *context,
 		  const char *suggestion);
+void bpf_diag_report_program_structure(struct bpf_verifier_env *env, u32 insn_idx,
+				       const char *problem, const char *suggestion,
+				       const char *reason_fmt, ...) __printf(5, 6);
 int bpf_diag_record_branch(struct bpf_verifier_env *env, u32 insn_idx, bool cond_true);
 void bpf_diag_record_mod(struct bpf_verifier_env *env, u32 insn_idx,
 			 struct bpf_diag_mod_target target, enum bpf_diag_mod_reason reason,
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e253fbc733a4..44e1907ac792 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3041,6 +3041,17 @@ static int check_subprogs(struct bpf_verifier_env *env)
 		off = i + bpf_jmp_offset(&insn[i]) + 1;
 		if (off < subprog_start || off >= subprog_end) {
 			verbose(env, "jump out of range from insn %d to %d\n", i, off);
+			bpf_diag_report_program_structure(env, i, "jump out of range",
+							  "Keep branch targets within the same "
+							  "subprogram, or use an explicit "
+							  "subprogram call.",
+							  "Instruction %d jumps to instruction %d, "
+							  "but subprogram %d only contains "
+							  "instructions %d through %d. A branch "
+							  "target must stay inside the same "
+							  "subprogram.",
+							  i, off, cur_subprog, subprog_start,
+							  subprog_end - 1);
 			return -EINVAL;
 		}
 next:
@@ -3053,6 +3064,18 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			    code != (BPF_JMP32 | BPF_JA) &&
 			    code != (BPF_JMP | BPF_JA)) {
 				verbose(env, "last insn is not an exit or jmp\n");
+				bpf_diag_report_program_structure(env, i,
+								  "subprogram can fall through",
+								  "End each subprogram with an "
+								  "exit or an explicit jump that "
+								  "keeps control flow inside the "
+								  "subprogram.",
+								  "Subprogram %d reaches its last "
+								  "instruction %d without an exit "
+								  "or jump, so control could "
+								  "continue into the next "
+								  "subprogram.",
+								  cur_subprog, i);
 				return -EINVAL;
 			}
 			subprog_start = subprog_end;
@@ -3125,6 +3148,15 @@ static int sort_subprogs_topo(struct bpf_verifier_env *env)
 					verbose(env, "recursive call from %s() to %s()\n",
 						bpf_verifier_subprog_name(env, cur),
 						bpf_verifier_subprog_name(env, callee));
+					bpf_diag_report_program_structure(
+						env, idx, "recursive subprogram call",
+						"Rewrite the recursion as an explicit bounded "
+						"loop, or split the logic so subprogram calls do "
+						"not form a cycle.",
+						"This bpf2bpf call would make the subprogram call "
+						"graph recursive. The verifier requires a finite, "
+						"acyclic call graph so it can bound stack depth "
+						"and analysis.");
 					ret = -EINVAL;
 					goto out;
 				}
-- 
2.53.0