Re: [PATCH bpf-next v8 05/22] bpf: Prepare for an exception cleanup table before the CFG walk

[Yonghong Song <yonghong.song@linux.dev>]

On 10/1/26 7:31 AM, bot+bpf-ci@kernel.org wrote:
>> bpf: Prepare for an exception cleanup table before the CFG walk
> TL;DR: bpf_exc_check_prog() rescans the whole program for bpf_throw, and a
> later patch calls it at every bpf_unwind() visit, so verification time may
> balloon on large programs; suggests caching the result.
>
>> diff --git a/kernel/bpf/exception.c b/kernel/bpf/exception.c
>> index 3ea1bff5cc90..e12cdb12cde3 100644
>> --- a/kernel/bpf/exception.c
>> +++ b/kernel/bpf/exception.c
>> @@ -141,6 +141,85 @@ int bpf_exc_check_info(struct bpf_verifier_env *env, const union bpf_attr *attr,
> [ ... ]
>
>> +static int reject_throw(struct bpf_verifier_env *env)
>> +{
>> +	u32 i;
>> +
>> +	for (i = 0; i < env->prog->len; i++) {
>> +		if (!bpf_is_throw_kfunc(&env->prog->insnsi[i]))
>> +			continue;
>> +		verbose(env,
>> +			"exception cleanup cannot be combined with bpf_throw at insn %u\n",
>> +			i);
>> +		return -EINVAL;
>> +	}
>> +	return 0;
>> +}
> [ ... ]
>
>> +int bpf_exc_check_prog(struct bpf_verifier_env *env)
>> +{
>> +	int err;
>> +
> [ ... ]
>
>> +	err = reject_throw(env);
>> +	if (err)
>> +		return err;
>> +	env->prog->jit_required = 1;
>> +	return 0;
>> +}
> Can this scan make verification time grow with the number of bpf_unwind()
> instructions the verifier visits?
>
> The commit message says the checks in bpf_exc_check_prog() are also run
> "at every bpf_unwind()", and a later patch in the series (5de314709a62
> "bpf: Dispatch cleanup pads by rewriting return addresses") does that from
> process_bpf_unwind():
>
>      static int process_bpf_unwind(struct bpf_verifier_env *env, ...)
>      {
>          ...
>          err = bpf_exc_check_prog(env);
>
> Each of those calls reaches reject_throw(), which walks all env->prog->len
> instructions looking for bpf_throw.
>
> None of the things bpf_exc_check_prog() tests can change once do_check()
> is running: the offload flag, jit_requested, exception_callback_subprog and
> whether a bpf_throw insn exists are all fixed before the main pass.  Only
> env->ops can change, and only for struct_ops, in check_attach_btf_id()
> before do_check().
>
> So the scan gives the same answer each time, but every visit costs
> O(prog->len) instead of O(1).  That means the BPF_COMPLEXITY_LIMIT_INSNS
> budget no longer bounds verifier cost linearly; the cost becomes roughly
> visits * prog_len.
>
> For example, a program with about 500K reachable insns plus a bounded loop
> of the form "if (x == i) bpf_unwind();" could reach bpf_unwind() tens of
> thousands of times within the 1M processed insn budget.  Each visit would
> rescan 500K insns, which is around 10^10 to 10^11 extra iterations, or
> tens of seconds of extra verifier CPU for a single load.
>
> Would it make sense to run reject_throw() once and cache the result in
> env?  Alternatively, the bpf_unwind() path could re-check only the
> gen_epilogue condition, which is the one that becomes known after
> bpf_exc_prepare().

As you mentioned, yes, this is an optimization issue. We can remove
bpf_exc_check_prog() for checking per bpf_unwind() insn. We can do
a collective checking after all insns are checked. This way
bpf_exc_check_prog() will be called only once.

>
>
> ---
> 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/36872142096