Clamping now reproduces the widened range at every back edge,
so induction variable ranges no longer vary between iterations.
This can produce identical checkpoint states in terminating programs,
for example:

  int main(...) {
    for (int i = 0; i < 10; i++) {
      foo(...);
      for (int j = 0; j < 3; j++)
        ...;
    }
  }

  void foo(...) {
    ...;
  }

Handle two cases in states.c:bpf_is_state_visited():
- For checkpoints inside foo(), look for active loops in upper frames
  as well. Otherwise current_loop() returns NULL and an identical
  callee state can trigger an infinite loop report.
- For checkpoints inside the inner loop, skip the infinite loop check
  when the current state is inside a terminating loop in any frame.
  That loop bounds how many times its body is re-executed, so an
  identical state on a later iteration does not imply nontermination.
  This covers the inner loop above, re-entered with a fresh entry
  state on each outer iteration, and inner loops SCEV cannot analyze.

The nested_terminating_prune test still rejects such an outer loop,
but now reaches the jump complexity limit instead of reporting an
infinite loop. Update its expected message accordingly.

Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/states.c                               | 36 ++++++++++++++++++-----
 tools/testing/selftests/bpf/progs/verifier_scev.c |  2 +-
 2 files changed, 29 insertions(+), 9 deletions(-)

diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index d7df6632a5c4..a6ae86f973e3 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -1358,13 +1358,33 @@ static bool need_loop_checkpoint(struct bpf_verifier_env *env, int insn_idx)
 	return top->loop_id == insn_idx && top->terminates;
 }
 
+/* Searches for an innermost loop entry starting from an innermost frame. */
 static struct loop_stack_entry *current_loop(struct bpf_verifier_state *st)
 {
-	struct bpf_func_state *frame = st->frame[st->curframe];
+	struct bpf_func_state *frame;
+	int fr;
 
-	if (frame->loop_stack_cnt == 0)
-		return NULL;
-	return &frame->loop_stack[frame->loop_stack_cnt - 1];
+	for (fr = st->curframe; fr >= 0; fr--) {
+		frame = st->frame[fr];
+		if (frame->loop_stack_cnt)
+			return &frame->loop_stack[frame->loop_stack_cnt - 1];
+	}
+	return NULL;
+}
+
+/* True if any of the loops call chain is currently in terminates. */
+static bool in_a_terminating_loop(struct bpf_verifier_state *st)
+{
+	struct bpf_func_state *frame;
+	int l, fr;
+
+	for (fr = st->curframe; fr >= 0; fr--) {
+		frame = st->frame[fr];
+		for (l = frame->loop_stack_cnt - 1; l >= 0; l--)
+			if (frame->loop_stack[l].terminates)
+				return true;
+	}
+	return false;
 }
 
 int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
@@ -1528,10 +1548,10 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 			 */
 			old_loop = current_loop(&sl->state);
 			cur_loop = current_loop(cur);
-			if (old_loop && cur_loop &&
-			    old_loop->terminates && cur_loop->terminates &&
-			    old_loop->entry_state == cur_loop->entry_state) {
-				if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
+			if (old_loop && cur_loop && in_a_terminating_loop(cur)) {
+				if (old_loop->terminates && cur_loop->terminates &&
+				    old_loop->entry_state == cur_loop->entry_state &&
+				    states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
 					loop = true;
 					goto hit;
 				}
diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c
index 14594ba5dbfd..9074b2f043d4 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scev.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scev.c
@@ -3351,7 +3351,7 @@ SEC("xdp")
 __failure
 __log_level(2)
 __flag(BPF_F_TEST_STATE_FREQ)
-__msg("infinite loop detected at insn 6")
+__msg("The sequence of 8193 jumps is too complex.")
 __naked void nested_terminating_prune(void)
 {
 	asm volatile ("					\

-- 
2.56.0