[PATCH bpf-next v2 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.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/cfg.c         | 39 +++++++++++++++++++++++++++++++++++++++
 kernel/bpf/diagnostics.c | 21 +++++++++++++++++++++
 kernel/bpf/diagnostics.h |  5 +++++
 kernel/bpf/verifier.c    | 16 ++++++++++++++++
 4 files changed, 81 insertions(+)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 26d37066465f..032b3dc56f2e 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,11 @@ 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 +143,11 @@ 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",
+						  "Rewrite the control flow as a verifier-supported bounded loop, or load with privileges that allow this back-edge.",
+						  "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 +328,11 @@ 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",
+						  "Provide a jump table whose entries target this subprogram.",
+						  "No jump table was found for the subprogram that starts at instruction %u.",
+						  subprog_start);
 		return ERR_PTR(-EINVAL);
 	}
 
@@ -343,6 +360,12 @@ 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 +397,12 @@ 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 +653,22 @@ 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 7c903e502973..d6893b2626c4 100644
--- a/kernel/bpf/diagnostics.c
+++ b/kernel/bpf/diagnostics.c
@@ -1118,6 +1118,27 @@ void bpf_diag_report_context_underflow(struct bpf_verifier_env *env,
 	bpf_diag_report_suggestion(env, "%s", 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, ...)
+{
+	va_list args;
+
+	bpf_diag_report_header(env, BPF_DIAG_CATEGORY_PROGRAM_STRUCTURE,
+			       problem);
+	bpf_diag_report_section(env, "Reason");
+
+	va_start(args, reason_fmt);
+	bpf_diag_vprint_indented(env, reason_fmt, args);
+	va_end(args);
+
+	bpf_diag_report_section(env, "At");
+	bpf_diag_report_source(env, insn_idx, "error", "%s", problem);
+
+	bpf_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 char *type_name,
diff --git a/kernel/bpf/diagnostics.h b/kernel/bpf/diagnostics.h
index 4611d94e7a18..b881ccaf6deb 100644
--- a/kernel/bpf/diagnostics.h
+++ b/kernel/bpf/diagnostics.h
@@ -216,6 +216,11 @@ void bpf_diag_report_context_underflow(struct bpf_verifier_env *env,
 				       u32 insn_idx, const char *operation,
 				       enum bpf_diag_context_kind ctx_kind,
 				       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);
 void bpf_diag_record_branch(struct bpf_verifier_env *env, u32 insn_idx,
 			    bool cond_true);
 void bpf_diag_record_reg_mod(struct bpf_verifier_env *env, u32 insn_idx,
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3174e12bea9a..e923366c6fdb 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2938,6 +2938,13 @@ 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:
@@ -2950,6 +2957,11 @@ 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;
@@ -3022,6 +3034,10 @@ static int sort_subprogs_topo(struct bpf_verifier_env *env)
 					verbose(env, "recursive call from %s() to %s()\n",
 						subprog_name(env, cur),
 						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