Re: [PATCH bpf-next v2 09/22] bpf: Strip nops through the patch list

[bot+bpf-ci]

> bpf: Strip nops through the patch list

TL;DR: The nop-stripping look-back in bpf_opt_remove_nops() may be quadratic
with no preemption or signal check, so a crafted program with many nops could
stall BPF_PROG_LOAD on non-preemptible kernels.

> diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
> index 95f4fe5d607e..7c7c38eb9f0c 100644
> --- a/kernel/bpf/fixups.c
> +++ b/kernel/bpf/fixups.c

[ ... ]

> -static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
> -{
> -	struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
> -	unsigned int orig_prog_len = env->prog->len;
> -	int err;
> -
> -	if (bpf_rewrite_must_abort())
> -		return -EINTR;
> -

[ ... ]

> @@ -1028,32 +855,63 @@ int bpf_opt_remove_dead_code(struct bpf_verifier_env *env)
>  	return bpf_patch_list_commit(env);
>  }
>
> +/*
> + * Whether insn i is a nop once the insns in 'removed' are gone. Only forward
> + * jumps over removed insns can turn into one.
> + */
> +static bool insn_is_nop(struct bpf_verifier_env *env, int i,
> +			const unsigned long *removed)
> +{

[ ... ]

>  int bpf_opt_remove_nops(struct bpf_verifier_env *env)
>  {

[ ... ]

> +	for (i = 0; i < insn_cnt; i++) {
> +		if (!insn_is_nop(env, i, removed))
>  			continue;
> +		/*
> +		 * Removing may_goto +0 can turn the may_goto +1 in front of it
> +		 * into another one, look back as long as it does.
> +		 */
> +		for (j = i; ; ) {
> +			__set_bit(j, removed);
> +			if (env->prog->insnsi[j].code != MAY_GOTO_0.code)
> +				break;
> +			while (--j >= 0 && test_bit(j, removed))
> +				;
> +			if (j < 0 || !insn_is_nop(env, j, removed))
> +				break;
> +		}
> +	}

Is the look-back here still linear in the program size, and can it still be
interrupted?

The removed verifier_remove_insns() called bpf_rewrite_must_abort() on every
removal, and the old "i -= 2" step back went through it each time, so each
step had a fatal_signal_pending() and cond_resched() check.  The new
look-back has neither.

After a may_goto +0 is marked, the inner loop walks back bit by bit over the
whole contiguous run of already removed insns:

    while (--j >= 0 && test_bit(j, removed))
            ;

Consider N "ja 0" followed by K "may_goto +0" and an exit.  Every
may_goto +0 walks back over all of the N "ja 0" plus the earlier
may_goto +0 insns before it reaches j < 0, so the marking loop does about
K * N test_bit() calls.

K is limited by BPF_COMPLEXITY_LIMIT_JMP_SEQ (8192), since each may_goto
pushes a pending state while the main path continues to the exit.  N is
limited by BPF_COMPLEXITY_LIMIT_INSNS (1M) for a privileged loader, and
nops are only stripped when env->bpf_capable is set.  With N around 970k and
K around 8000 that is about 8e9 iterations of test_bit() in a loop with no
preemption point, so BPF_PROG_LOAD cannot be killed or rescheduled on a
CONFIG_PREEMPT_NONE or CONFIG_PREEMPT_VOLUNTARY kernel until it finishes.

The only bpf_rewrite_must_abort() check left is in bpf_patch_list_del(),
which is reached from the for_each_set_bit() loop that runs after this
marking loop.

Could the loop remember the index of the last insn that was kept, instead of
rescanning the removed run for each may_goto +0?  That would keep the pass
linear, as the commit message intends, and a bpf_rewrite_must_abort() call
in the look-back would restore the killable/preemptible behaviour.

> +
> +	for_each_set_bit(i, removed, insn_cnt) {
> +		err = bpf_patch_list_del(env, i);
> +		if (err)
> +			break;
>  	}
> +	bitmap_free(removed);
>
> -	return 0;
> +	return err ?: bpf_patch_list_commit(env);
>  }


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/41053659762