[PATCH bpf-next v4 03/16] bpf: Add verifier diagnostic event log

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

Add an environment-owned diagnostic history for verifier reports. Event
payloads keep the user-facing branch history shape, while storage lives
in bpf_verifier_env and follows the active verifier path.

Grow the event array as entries are appended and keep saved positions as
array indices. Later patches can truncate back to those positions when
verifier search backtracks. Add the branch event renderer and branch
recording.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/diagnostics.c | 108 +++++++++++++++++++++++++++++++++++++++
 kernel/bpf/diagnostics.h |   3 ++
 kernel/bpf/verifier.c    |  21 ++++++++
 3 files changed, 132 insertions(+)

diff --git a/kernel/bpf/diagnostics.c b/kernel/bpf/diagnostics.c
index 77dcffb9adee..0e0aa3a7106c 100644
--- a/kernel/bpf/diagnostics.c
+++ b/kernel/bpf/diagnostics.c
@@ -34,8 +34,24 @@
 #define BPF_DIAG_REG_TMP_LEN 192
 #define BPF_DIAG_FMT_CHUNK_SIZE 1024
 #define BPF_DIAG_FMT_BUF_SIZE 256
+#define BPF_DIAG_EVENT_LOG_MAX_SIZE (1U << 20)
 #define DISASM_LINE_LEN 160
 
+enum bpf_diag_history_kind {
+	BPF_DIAG_HISTORY_BRANCH,
+};
+
+struct bpf_diag_history_event {
+	u32 insn_idx : 24;
+	u32 kind : 8;
+	u8 in_lineage : 1;
+	union {
+		struct {
+			bool cond_true;
+		} branch;
+	};
+};
+
 struct disasm_line {
 	char text[DISASM_LINE_LEN];
 	int idx;
@@ -58,12 +74,21 @@ struct diag_fmt_mark {
 	size_t len;
 };
 
+struct bpf_diag_log {
+	struct bpf_diag_history_event *events;
+	u32 cnt;
+	u32 cap;
+	u32 dropped;
+	bool capped;
+};
+
 struct bpf_diag_scratch {
 	struct bpf_linfo_source source_lines[BPF_DIAG_CONTEXT_CNT];
 	struct disasm_line disasm_lines[BPF_DIAG_CONTEXT_CNT];
 };
 
 struct bpf_diag {
+	struct bpf_diag_log log;
 	struct bpf_diag_scratch scratch;
 	struct list_head fmt_chunks;
 };
@@ -229,6 +254,7 @@ void bpf_diag_free(struct bpf_verifier_env *env)
 		return;
 
 	diag_fmt_free(env);
+	kvfree(diag->log.events);
 	kfree(diag);
 	env->diag = NULL;
 }
@@ -245,6 +271,75 @@ static void diag_write(struct bpf_verifier_env *env, const char *fmt, ...)
 	va_end(args);
 }
 
+static struct bpf_diag_log *diag_event_log(struct bpf_verifier_env *env)
+{
+	struct bpf_diag *diag = diag_env(env);
+
+	return diag ? &diag->log : NULL;
+}
+
+u32 bpf_diag_event_log_pos(struct bpf_verifier_env *env)
+{
+	struct bpf_diag *diag = diag_env(env);
+
+	if (!diag)
+		return 0;
+	return diag->log.cnt;
+}
+
+void bpf_diag_event_log_reset(struct bpf_verifier_env *env, u32 pos)
+{
+	struct bpf_diag *diag = env->diag;
+	struct bpf_diag_log *log;
+	u32 end;
+
+	if (!diag)
+		return;
+
+	log = &diag->log;
+	end = log->cnt;
+	if (WARN_ON_ONCE(pos > end))
+		pos = end;
+
+	log->cnt = pos;
+}
+
+static void diag_append_history(struct bpf_verifier_env *env,
+				const struct bpf_diag_history_event *event)
+{
+	struct bpf_diag_history_event *events;
+	struct bpf_diag_log *log;
+	u32 cap, max_events;
+
+	log = diag_event_log(env);
+	if (!log)
+		return;
+
+	if (log->cnt < log->cap) {
+		log->events[log->cnt++] = *event;
+		return;
+	}
+
+	max_events = BPF_DIAG_EVENT_LOG_MAX_SIZE / sizeof(*events);
+	if (log->capped || log->cap == max_events) {
+		if (log->dropped != U32_MAX)
+			log->dropped++;
+		return;
+	}
+
+	cap = min_t(u32, log->cap ? log->cap * 2 : 64, max_events);
+	events = kvrealloc(log->events, array_size(cap, sizeof(*events)), GFP_KERNEL_ACCOUNT);
+	if (!events) {
+		log->capped = true;
+		if (log->dropped != U32_MAX)
+			log->dropped++;
+		return;
+	}
+	log->events = events;
+	log->cap = cap;
+	log->events[log->cnt++] = *event;
+}
+
 static void diag_print_wrapped_prefixed(struct bpf_verifier_env *env, const char *first_prefix,
 					const char *next_prefix, const char *text)
 {
@@ -564,3 +659,16 @@ void bpf_diag_source(struct bpf_verifier_env *env, u32 insn_idx, const char *lab
 out_restore:
 	diag_fmt_restore(env, mark);
 }
+
+void bpf_diag_record_branch(struct bpf_verifier_env *env, u32 insn_idx, bool cond_true)
+{
+	struct bpf_diag_history_event event = {
+		.insn_idx = insn_idx,
+		.kind = BPF_DIAG_HISTORY_BRANCH,
+		.branch = {
+			.cond_true = cond_true,
+		},
+	};
+
+	diag_append_history(env, &event);
+}
diff --git a/kernel/bpf/diagnostics.h b/kernel/bpf/diagnostics.h
index 7b391cf49ae5..9cc6b4747a06 100644
--- a/kernel/bpf/diagnostics.h
+++ b/kernel/bpf/diagnostics.h
@@ -15,10 +15,13 @@ char *bpf_diag_fmt_buf(struct bpf_verifier_env *env, size_t size);
 const char *bpf_diag_vfmt(struct bpf_verifier_env *env, const char *fmt, va_list args)
 	__printf(2, 0);
 const char *bpf_diag_fmt(struct bpf_verifier_env *env, const char *fmt, ...) __printf(2, 3);
+u32 bpf_diag_event_log_pos(struct bpf_verifier_env *env);
+void bpf_diag_event_log_reset(struct bpf_verifier_env *env, u32 pos);
 void bpf_diag_free(struct bpf_verifier_env *env);
 void bpf_diag_header(struct bpf_verifier_env *env, const char *category,
 			    const char *problem);
 void bpf_diag_source(struct bpf_verifier_env *env, u32 insn_idx, const char *label,
 			    const char *fmt, ...) __printf(4, 5);
+void bpf_diag_record_branch(struct bpf_verifier_env *env, u32 insn_idx, bool cond_true);
 
 #endif /* __BPF_DIAGNOSTICS_H */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6bc2ccf35971..6ca366ff5037 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -17369,6 +17369,27 @@ static int do_check(struct bpf_verifier_env *env)
 
 		state->last_insn_idx = env->prev_insn_idx;
 		state->insn_idx = env->insn_idx;
+		/*
+		 * Record the incoming edge so active and queued paths use the same
+		 * branch-recording path. A zero-offset conditional has identical
+		 * successors, so its outcome cannot be reconstructed from the edge.
+		 */
+		if (!state->speculative && prev_insn_idx >= 0 && prev_insn_idx < insn_cnt) {
+			struct bpf_insn *prev_insn = &insns[prev_insn_idx];
+			int fallthrough_idx = prev_insn_idx + 1;
+			int branch_idx = prev_insn_idx + bpf_jmp_offset(prev_insn) + 1;
+			u8 class = BPF_CLASS(prev_insn->code);
+			u8 opcode = BPF_OP(prev_insn->code);
+
+			if ((class == BPF_JMP || class == BPF_JMP32) &&
+			    opcode != BPF_JA && opcode != BPF_CALL && opcode != BPF_EXIT &&
+			    opcode <= BPF_JCOND && branch_idx != fallthrough_idx) {
+				if (env->insn_idx == branch_idx)
+					bpf_diag_record_branch(env, prev_insn_idx, true);
+				else if (env->insn_idx == fallthrough_idx)
+					bpf_diag_record_branch(env, prev_insn_idx, false);
+			}
+		}
 
 		if (bpf_is_prune_point(env, env->insn_idx)) {
 			err = bpf_is_state_visited(env, env->insn_idx);
-- 
2.53.0