Re: [PATCH bpf 1/6] bpf: Avoid quadratic successor rescan in bpf_compute_scc

[Eduard Zingerman <eddyz87@gmail.com>]

On Wed, 2026-09-09 at 22:40 +0200, Daniel Borkmann wrote:
> The iterative Tarjan DFS in bpf_compute_scc() emulates recursion with an
> explicit 'dfs' stack: when a successor has not been visited yet, the
> successor is pushed and the walk restarts at the top of the loop. On the
> way back to a vertex the successor scan starts over at index zero, so a
> vertex with k successors rescans up to k successors on each of its up to k
> descents, i.e. O(k^2) work.
> 
> For ordinary instructions k <= 2 and this is irrelevant. For a gotox the
> successors are the jump table of the containing subprogram, whose size is
> bounded only by the max_entries of the insn_array map, so k can reach the
> 1M instruction complexity limit. Loading such a program keeps a CPU busy
> in the loop for a very long time before verification even begins.
> 
> Record in 'dfs_pos' the successor index each frame stopped at and resume
> the scan there. Each edge is therefore examined a bounded number of times
> and the walk becomes linear in the number of edges.
> 
> Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
> Reported-by: STAR Labs SG <info@starlabs.sg>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

The change looks correct, but I'd cleanup the comments a bit,
to me these look too LLM-ish.

>  kernel/bpf/cfg.c | 41 +++++++++++++++++++++++++++++++++++------
>  1 file changed, 35 insertions(+), 6 deletions(-)
> 
> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index 842c7d1eabcc..081f7003eae6 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -749,7 +749,7 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
>  	struct bpf_insn_aux_data *aux = env->insn_aux_data;
>  	const u32 insn_cnt = env->prog->len;
>  	int stack_sz, dfs_sz, err = 0;
> -	u32 *stack, *pre, *low, *dfs;
> +	u32 *stack, *pre, *low, *dfs, *dfs_pos;
>  	u32 i, j, t, w;
>  	u32 next_preorder_num;
>  	u32 next_scc_id;
> @@ -762,13 +762,16 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
>  	 * - 'stack' accumulates vertices in DFS order, see invariant comment below;
>  	 * - 'pre[t] == p' => preorder number of vertex 't' is 'p';
>  	 * - 'low[t] == n' => smallest preorder number of the vertex reachable from 't' is 'n';
> -	 * - 'dfs' DFS traversal stack, used to emulate explicit recursion.
> +	 * - 'dfs' DFS traversal stack, used to emulate explicit recursion;
> +	 * - 'dfs_pos[k] == j' => the frame 'dfs[k]' resumes visiting its
> +	 *   successors at index 'j'.
>  	 */
>  	stack = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
>  	pre = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
>  	low = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
>  	dfs = kvcalloc(insn_cnt, sizeof(*dfs), GFP_KERNEL_ACCOUNT);
> -	if (!stack || !pre || !low || !dfs) {
> +	dfs_pos = kvcalloc(insn_cnt, sizeof(*dfs_pos), GFP_KERNEL_ACCOUNT);
> +	if (!stack || !pre || !low || !dfs || !dfs_pos) {
>  		err = -ENOMEM;
>  		goto exit;
>  	}
> @@ -851,6 +854,7 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
>  		stack_sz = 0;
>  		dfs_sz = 1;
>  		dfs[0] = i;
> +		dfs_pos[0] = 0;
>  dfs_continue:
>  		while (dfs_sz) {
>  			w = dfs[dfs_sz - 1];
> @@ -860,13 +864,37 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
>  				next_preorder_num++;
>  				stack[stack_sz++] = w;
>  			}
> -			/* Visit 'w' successors */
> +			/*
> +			 * Visit 'w' successors, resuming at the successor this
> +			 * frame last descended into. Restarting the scan at zero
> +			 * on every return to 'w' would examine each successor
> +			 * once per descent, i.e. quadratic in the number of
> +			 * successors, which for a gotox is the size of the jump
> +			 * table.

Please drop the paragraph above, this fact was already stated in the
commit message.

> +			 *
> +			 * Re-folding the successors before that index would be a

I think "visiting" is a better term in this context.

> +			 * no-op. Such a successor 's' has 'pre[s] != 0' by then,
> +			 * so it is never pushed onto 'dfs' again, and low[s] can
> +			 * only decrease while 's' is the top of 'dfs'. If 's' is
> +			 * still on 'dfs' it sits below 'w' and cannot become the
> +			 * top before 'w' is popped; otherwise the only remaining
> +			 * write to low[s] is the pop of its SCC, setting it to
> +			 * NOT_ON_STACK, for which the min below is a no-op.
> +			 */

Tbh, I find this paragraph extremely hard to parse.
Why not simply /* Visit the next 'w' successor */ ?

>  			succ = bpf_insn_successors(env, w);
> -			for (j = 0; j < succ->cnt; ++j) {
> +			for (j = dfs_pos[dfs_sz - 1]; j < succ->cnt; ++j) {
>  				if (pre[succ->items[j]]) {
>  					low[w] = min(low[w], low[succ->items[j]]);
>  				} else {
> -					dfs[dfs_sz++] = succ->items[j];
> +					/*
> +					 * Resume at 'j', not 'j + 1': the successor
> +					 * is revisited once its DFS completes, to
> +					 * fold its low[] into low[w].
> +					 */

/*
 * Once DFS for succ->items[j] is complete, the pre[succ->items[j]] would be non-zero,
 * hence resuming at 'j' allows to follow the update low[w] = min(...) branch above.
 */

> +					dfs_pos[dfs_sz - 1] = j;
> +					dfs_pos[dfs_sz] = 0;
> +					dfs[dfs_sz] = succ->items[j];
> +					dfs_sz++;
>  					goto dfs_continue;
>  				}
>  			}
> @@ -916,5 +944,6 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
>  	kvfree(pre);
>  	kvfree(low);
>  	kvfree(dfs);
> +	kvfree(dfs_pos);
>  	return err;
>  }