Re: [PATCH bpf-next 2/6] bpf: Sort subprogs in topological order after check_cfg()

[Mykyta Yatsenko <mykyta.yatsenko5@gmail.com>]

On 4/1/26 3:16 AM, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> Add a pass that sorts subprogs in topological order so that iterating
> subprog_topo_order[] walks leaf subprogs first, then their callers.
> This is computed as a DFS post-order traversal of the CFG.
> 
> The pass runs after check_cfg() to ensure the CFG has been validated
> before traversing and after postorder has been computed to avoid
> walking dead code.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---
>   include/linux/bpf_verifier.h |  2 +
>   kernel/bpf/verifier.c        | 83 ++++++++++++++++++++++++++++++++++++
>   2 files changed, 85 insertions(+)
> 
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 090aa26d1c98..4f492eaad5c2 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -787,6 +787,8 @@ struct bpf_verifier_env {
>   	const struct bpf_line_info *prev_linfo;
>   	struct bpf_verifier_log log;
>   	struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 2]; /* max + 2 for the fake and exception subprogs */
> +	/* subprog indices sorted in topological order: leaves first, callers last */
> +	int subprog_topo_order[BPF_MAX_SUBPROGS + 2];
>   	union {
>   		struct bpf_idmap idmap_scratch;
>   		struct bpf_idset idset_scratch;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 3ec786361698..432806011d47 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3742,6 +3742,85 @@ static int check_subprogs(struct bpf_verifier_env *env)
>   	return 0;
>   }
>   
> +/*
> + * Sort subprogs in topological order so that leaf subprogs come first and
> + * their callers come later. This is a DFS post-order traversal of the call
> + * graph. Scan only reachable instructions (those in the computed postorder) of
> + * the current subprog to discover callees (direct subprogs and sync
> + * callbacks).
> + */
> +static int sort_subprogs_topo(struct bpf_verifier_env *env)
> +{
> +	struct bpf_subprog_info *si = env->subprog_info;
> +	int *insn_postorder = env->cfg.insn_postorder;
> +	struct bpf_insn *insn = env->prog->insnsi;
> +	int cnt = env->subprog_cnt;
> +	int *dfs_stack = NULL;
> +	int top = 0, order = 0;
> +	int i, ret = 0;
> +	u8 *color = NULL;
> +
> +	color = kcalloc(cnt, sizeof(*color), GFP_KERNEL);

It looks like we are using GFP_KERNEL_ACCOUNT consistently in verifier, 
should this be different?

> +	dfs_stack = kmalloc_array(cnt, sizeof(*dfs_stack), GFP_KERNEL);
> +	if (!color || !dfs_stack) {
> +		ret = -ENOMEM;
> +		goto out;
> +	}
> +
> +	/*
> +	 * DFS post-order traversal.
> +	 * Color values: 0 = unvisited, 1 = on stack, 2 = done.
> +	 */
> +	for (i = 0; i < cnt; i++) {
> +		if (color[i])
> +			continue;
> +		color[i] = 1;
> +		dfs_stack[top++] = i;
> +
> +		while (top > 0) {
> +			int cur = dfs_stack[top - 1];
> +			int po_start = si[cur].postorder_start;
> +			int po_end = si[cur + 1].postorder_start;
> +			bool pushed = false;
> +			int j;
> +
> +			for (j = po_start; j < po_end; j++) {

Is there a chance that restarting this loop every time from po_start may 
penalize performance? For example some very big BPF program with a lot 
of different subprog calls, perhaps autogenerated.

> +				int idx = insn_postorder[j];
> +				int callee;
> +
> +				if (!bpf_pseudo_call(&insn[idx]) && !bpf_pseudo_func(&insn[idx]))
> +					continue;
> +				callee = find_subprog(env, idx + insn[idx].imm + 1);
> +				if (callee < 0) {
> +					ret = -EFAULT;
> +					goto out;
> +				}
> +				if (color[callee])
> +					continue;
> +				color[callee] = 1;
> +				dfs_stack[top++] = callee;
> +				pushed = true;
> +				break;
> +			}
> +
> +			if (!pushed) {
> +				color[cur] = 2;
> +				env->subprog_topo_order[order++] = cur;
> +				top--;
> +			}
> +		}
> +	}
> +
> +	if (env->log.level & BPF_LOG_LEVEL2)
> +		for (i = 0; i < cnt; i++)
> +			verbose(env, "topo_order[%d] = %s\n",
> +				i, subprog_name(env, env->subprog_topo_order[i]));
> +out:
> +	kfree(dfs_stack);
> +	kfree(color);
> +	return ret;
> +}
> +
>   static int mark_stack_slot_obj_read(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
>   				    int spi, int nr_slots)
>   {
> @@ -26274,6 +26353,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
>   	if (ret)
>   		goto skip_full_check;
>   
> +	ret = sort_subprogs_topo(env);
> +	if (ret < 0)
> +		goto skip_full_check;
> +
>   	ret = compute_scc(env);
>   	if (ret < 0)
>   		goto skip_full_check;