> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index ed7ba0e6a9ce..25fa90e731e3 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -17124,6 +17124,23 @@ static int indirect_jump_min_max_index(struct
> bpf_verifier_env *env,
> return 0;
> }
>
> +static bool is_cfg_indirect_jump_target(struct bpf_verifier_env *env,
> + u32 target)
> +{
> + struct bpf_iarray *jt = env->insn_aux_data[env->insn_idx].jt;
> + int i;
> +
> + if (!jt)
> + return false;
> +
> + for (i = 0; i < jt->cnt; i++) {
> + if (jt->items[i] == target)
> + return true;
> + }
> +
> + return false;
> +}
> +
> /* gotox *dst_reg */
> static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn
> *insn)
> {
[ ... ]
> @@ -17171,6 +17188,15 @@ static int check_indirect_jump(struct
> bpf_verifier_env *env, struct bpf_insn *in
> return -EINVAL;
> }
>
> + for (i = 0; i < n; i++) {
> + if (!is_cfg_indirect_jump_target(env,
> env->gotox_tmp_buf->items[i])) {
> + verbose(env,
> + "gotox target %u from map id=%d is not in the
> CFG jump table\n",
> + env->gotox_tmp_buf->items[i], map->id);
> + return -EINVAL;
> + }
> + }
> +
Could this nested loop create an O(N * M) algorithmic complexity that
bypasses verifier complexity limits?
The outer loop iterates n times, and is_cfg_indirect_jump_target()
performs a linear scan over jt->cnt items. Both n and jt->cnt are bounded
by the map's max_entries, which can be very large.
Since there is no cond_resched() here, this creates a synchronous
iteration sequence that could trigger the kernel watchdog panic or lead to
CPU soft lockup.
Given that both gotox_tmp_buf->items and jt->items are strictly sorted
arrays, could this be optimized to O(N + M) using a two-pointer merge
approach or O(N log M) using binary search?
Raised by [email protected] in v1:
https://lore.kernel.org/bpf/[email protected]/
> for (i = 0; i < n - 1; i++) {
> mark_indirect_target(env, env->gotox_tmp_buf->items[i]);
> other_branch = push_stack(env, env->gotox_tmp_buf->items[i],
[ ... ]
---
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/27216356316
