Merge branch 'bpf-calls-to-bpf_loop-should-have-an-scc-and-accumulate-backedges'

Eduard Zingerman says:

====================
bpf: calls to bpf_loop() should have an SCC and accumulate backedges

This is a correctness fix for the verification of BPF programs that
work with callback-calling functions. The problem is the same as the
issue fixed by series [1] for iterator-based loops: some of the states
created while processing the callback function body might have
incomplete read or precision marks.

An example of an unsafe program that is accepted without this fix can
be found in patch #2.

There is some impact on verification performance:

File                             Program               Insns (A)  Insns (B)  Insns      (DIFF)
-------------------------------  --------------------  ---------  ---------  -----------------
pyperf600_bpf_loop.bpf.o         on_event                   4247       9985   +5738 (+135.11%)
setget_sockopt.bpf.o             skops_sockopt              5719       7446    +1727 (+30.20%)
setget_sockopt.bpf.o             socket_post_create         1253       1603     +350 (+27.93%)
strobemeta_bpf_loop.bpf.o        on_event                   3424       7224   +3800 (+110.98%)
test_tcp_custom_syncookie.bpf.o  tcp_custom_syncookie      11929      38307  +26378 (+221.12%)
xdp_synproxy_kern.bpf.o          syncookie_tc              13986      23035    +9049 (+64.70%)
xdp_synproxy_kern.bpf.o          syncookie_xdp             13881      21022    +7141 (+51.44%)

Total progs: 4172
Old success: 2520
New success: 2520
total_insns diff min:    0.00%
total_insns diff max:  221.12%
0 -> value: 0
value -> 0: 0
total_insns abs max old: 837,487
total_insns abs max new: 837,487
   0 .. 5    %: 4163
   5 .. 15   %: 2
  25 .. 35   %: 2
  50 .. 60   %: 1
  60 .. 70   %: 1
 110 .. 120  %: 1
 135 .. 145  %: 1
 220 .. 225  %: 1

[1] https://lore.kernel.org/bpf/174968344350.3524559.14906547029551737094.git-patchwork-notify@kernel.org/
---
====================

Link: https://patch.msgid.link/20251229-scc-for-callbacks-v1-0-ceadfe679900@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

1 files changed, 9 insertions, 4 deletions

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2de1a736ef69..0baae7828af2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -19830,8 +19830,10 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 				}
 			}
 			if (bpf_calls_callback(env, insn_idx)) {
-				if (states_equal(env, &sl->state, cur, RANGE_WITHIN))
+				if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
+					loop = true;
 					goto hit;
+				}
 				goto skip_inf_loop_check;
 			}
 			/* attempt to detect infinite loop to avoid unnecessary doomed work */
@@ -25071,15 +25073,18 @@ dfs_continue:
 			}
 			/*
 			 * Assign SCC number only if component has two or more elements,
-			 * or if component has a self reference.
+			 * or if component has a self reference, or if instruction is a
+			 * callback calling function (implicit loop).
 			 */
-			assign_scc = stack[stack_sz - 1] != w;
-			for (j = 0; j < succ->cnt; ++j) {
+			assign_scc = stack[stack_sz - 1] != w;	/* two or more elements? */
+			for (j = 0; j < succ->cnt; ++j) {	/* self reference? */
 				if (succ->items[j] == w) {
 					assign_scc = true;
 					break;
 				}
 			}
+			if (bpf_calls_callback(env, w)) /* implicit loop? */
+				assign_scc = true;
 			/* Pop component elements from stack */
 			do {
 				t = stack[--stack_sz];