Re: [PATCH RFC bpf-next v2 2/6] bpf: compute loops hierarchy

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] Worst-case O(N^2) algorithmic complexity in assign_header() lacking cond_resched() leads to soft lockup.
--

commit 5ba437ec70f22b36c162a26467753448539086e8
Author: Eduard Zingerman <eddyz87@gmail.com>

bpf: compute loops hierarchy

This commit introduces an analysis phase to the bpf verifier that computes
the loops hierarchy using a non-recursive adaptation of the Wei et al.
algorithm. It records the innermost loop header per instruction to be used
as sampling points for callchain profiling.

> diff --git a/kernel/bpf/loops.c b/kernel/bpf/loops.c
> new file mode 100644
> index 0000000000000..1f0b10c57957a
> --- /dev/null
> +++ b/kernel/bpf/loops.c

[ ... ]

> +static int assign_header(struct bpf_verifier_env *env, struct loops_dfs *dfs, int n, int h)
> +{
> +	struct bpf_insn_aux_data *aux = env->insn_aux_data;
> +	int *dfs_pos = dfs->dfs_pos;
> +	int err, nh;
> +
> +	err = mark_header(env, h);
> +	if (err)
> +		return err;
> +
> +	/* Don't encode self-loops, otherwise can't reflect loops nesting structure. */
> +	if (n == h)
> +		return 0;
> +
> +	/* Make sure that loop headers up the chain are sorted by dfs_pos. */
> +	while (aux[n].loop_header != -1) {
> +		nh = aux[n].loop_header;
> +		if (nh == h)
> +			return 0;
> +		if (dfs_pos[nh] < dfs_pos[h]) {
> +			aux[n].loop_header = h;
> +			n = h;
> +			h = nh;
> +		} else {
> +			n = nh;
> +		}
> +	}

[Severity: High]
Could this while loop lead to a cpu soft lockup under specific pathological
conditions?

With deeply nested loops and cross-edges, it appears possible to force
repeated O(n) traversals of this header chain for O(n) nodes without
actually modifying the chain. Given the 1 million bpf instruction limit,
this worst-case O(n^2) algorithmic complexity might result in a massive
number of iterations.

Because neither this chain traversal nor the surrounding search algorithm in
compute_loops_in_subprog() seem to call cond_resched(), does this risk
stalling the cpu core long enough to trigger a system soft lockup or a
local denial of service?

> +	aux[n].loop_header = h;
> +	return 0;
> +}

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260526-better-1m-reporting-v2-0-e7ec61c45d41@gmail.com?part=2