Re: [PATCH bpf-next 03/11] bpf: look for current loop in upper frames in states_equal()

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: current_loop() ignores outer loops when inner loop is re-entered
--

commit 999e70b9b80c780cef9257c5cc41cf3820aa644f
Author: Eduard Zingerman <eddyz87@gmail.com>

bpf: look for current loop in upper frames in states_equal()

This commit updates current_loop() to search upper call frames for an active
loop entry when checking if the current loop exploration terminates in
bpf_is_state_visited(). This allows checkpoints inside callees invoked from a
bounded loop to be pruned and to skip false-positive infinite loop checks.

> diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
> index d7df6632a5c47..306ad208a8e41 100644
> --- a/kernel/bpf/states.c
> +++ b/kernel/bpf/states.c
> @@ -1361,10 +1361,14 @@ static bool need_loop_checkpoint(struct bpf_verifier_env *env, int insn_idx)
>  static struct loop_stack_entry *current_loop(struct bpf_verifier_state *st)
>  {
>  	struct bpf_func_state *frame = st->frame[st->curframe];
> +	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];
> +	}

[Severity: Medium]
What happens if a terminating outer loop enters a terminating inner loop
(either in a callee or nested in the same function) on a subsequent outer
iteration without having been pruned at the outer loop header?

On each fresh entry into the inner loop, handle_loop_entry_exit() allocates a
new entry_state via bpf_split_cur_state():

kernel/bpf/verifier.c:handle_loop_entry_exit() {
	...
	/* Create a loop_entry checkpoint before widening */
	err = bpf_split_cur_state(env);
	if (err)
		return err;

	entry->min_header_count = iters.min_header_count;
	entry->max_header_count = iters.max_header_count;
	entry->entry_state = cur->parent;
	entry->terminates = true;
	...
}

When the outer loop takes its backedge into a second iteration (for example,
when a 32-bit stack spill becomes STACK_MISC during iteration 1 so the outer
header does not immediately prune) and re-enters the inner loop, the inner
loop receives a distinct entry_state from the one recorded in the first outer
iteration's checkpoint.

Because current_loop() unconditionally returns the innermost active loop entry,
bpf_is_state_visited() only compares the inner loop's entry_state pointers:

kernel/bpf/states.c:bpf_is_state_visited() {
	...
	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)) {
			loop = true;
			goto hit;
		}
		goto skip_inf_loop_check;
	}
	...
}

Since old_loop->entry_state != cur_loop->entry_state for the re-entered inner
loop, this check fails without noticing that an enclosing terminating loop in
the same or upper frame still has a matching entry_state.

Execution then falls through to the infinite loop check, where
loop_stack_safe() does not compare entry_state:

kernel/bpf/states.c:loop_stack_safe() {
	...
	for (i = 0; i < old->loop_stack_cnt; i++) {
		if (old_stack[i].loop_id == cur_stack[i].loop_id &&
		    old_stack[i].max_header_count == cur_stack[i].max_header_count &&
		    old_stack[i].terminates == cur_stack[i].terminates)
			continue;
		return false;
	}
	...
}

Won't states_maybe_looping() and states_equal(env, &sl->state, cur, EXACT)
then match the inner loop checkpoint from the previous outer iteration and
falsely reject the program with an infinite loop error?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261023-scev-simpler-clamp-v1-0-d43a07eda7af@gmail.com?part=3