[PATCH bpf-next 0/6] bpf: Prep patches for static stack liveness.

[PATCH bpf-next 0/6] bpf: Prep patches for static stack liveness.

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

First 6 prep patches for static stack liveness.

. do src/dst_reg validation early and remove defensive checks

. sort subprog in topo order. We wanted to do this long ago
  to process global subprogs this way and in other cases.

. Add constant folding pass that computes map_ptr, subprog_idx,
  loads from readonly maps, and other constants that fit into 32-bit

. Use these constants to eliminate dead code. Replace predicted
  conditional branches with "jmp always". That reduces JIT prog size.

. Add two helpers that return access size from their arguments.

Alexei Starovoitov (6):
  bpf: Do register range validation early
  bpf: Sort subprogs in topological order after check_cfg()
  selftests/bpf: Add tests for subprog topological ordering
  bpf: Add compute_const_regs() and prune_dead_branches() passes
  bpf: Move verifier helpers to header
  bpf: Add helper and kfunc stack access size resolution

 include/linux/bpf_verifier.h                  |  61 +++
 kernel/bpf/Makefile                           |   2 +-
 kernel/bpf/const_fold.c                       | 385 ++++++++++++++++++
 kernel/bpf/verifier.c                         | 373 ++++++++++++++---
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../selftests/bpf/progs/verifier_scalar_ids.c |  20 +-
 .../bpf/progs/verifier_subprog_topo.c         | 226 ++++++++++
 7 files changed, 1000 insertions(+), 69 deletions(-)
 create mode 100644 kernel/bpf/const_fold.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_subprog_topo.c

-- 
2.52.0

[PATCH bpf-next 1/6] bpf: Do register range validation early

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Instead of checking src/dst range multiple times during
the main verifier pass do them once.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/verifier.c | 34 ++++++++--------------------------
 1 file changed, 8 insertions(+), 26 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8c1cf2eb6cbb..3ec786361698 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2249,13 +2249,6 @@ static void __mark_reg_const_zero(const struct bpf_verifier_env *env, struct bpf
 static void mark_reg_known_zero(struct bpf_verifier_env *env,
 				struct bpf_reg_state *regs, u32 regno)
 {
-	if (WARN_ON(regno >= MAX_BPF_REG)) {
-		verbose(env, "mark_reg_known_zero(regs, %u)\n", regno);
-		/* Something bad happened, let's kill all regs */
-		for (regno = 0; regno < MAX_BPF_REG; regno++)
-			__mark_reg_not_init(env, regs + regno);
-		return;
-	}
 	__mark_reg_known_zero(regs + regno);
 }
 
@@ -2908,13 +2901,6 @@ static void __mark_reg_unknown(const struct bpf_verifier_env *env,
 static void mark_reg_unknown(struct bpf_verifier_env *env,
 			     struct bpf_reg_state *regs, u32 regno)
 {
-	if (WARN_ON(regno >= MAX_BPF_REG)) {
-		verbose(env, "mark_reg_unknown(regs, %u)\n", regno);
-		/* Something bad happened, let's kill all regs except FP */
-		for (regno = 0; regno < BPF_REG_FP; regno++)
-			__mark_reg_not_init(env, regs + regno);
-		return;
-	}
 	__mark_reg_unknown(env, regs + regno);
 }
 
@@ -2947,13 +2933,6 @@ static void __mark_reg_not_init(const struct bpf_verifier_env *env,
 static void mark_reg_not_init(struct bpf_verifier_env *env,
 			      struct bpf_reg_state *regs, u32 regno)
 {
-	if (WARN_ON(regno >= MAX_BPF_REG)) {
-		verbose(env, "mark_reg_not_init(regs, %u)\n", regno);
-		/* Something bad happened, let's kill all regs except FP */
-		for (regno = 0; regno < BPF_REG_FP; regno++)
-			__mark_reg_not_init(env, regs + regno);
-		return;
-	}
 	__mark_reg_not_init(env, regs + regno);
 }
 
@@ -3958,11 +3937,6 @@ static int __check_reg_arg(struct bpf_verifier_env *env, struct bpf_reg_state *r
 	struct bpf_reg_state *reg;
 	bool rw64;
 
-	if (regno >= MAX_BPF_REG) {
-		verbose(env, "R%d is invalid\n", regno);
-		return -EINVAL;
-	}
-
 	mark_reg_scratched(env, regno);
 
 	reg = &regs[regno];
@@ -22070,6 +22044,14 @@ static int resolve_pseudo_ldimm64(struct bpf_verifier_env *env)
 			verbose(env, "unknown opcode %02x\n", insn->code);
 			return -EINVAL;
 		}
+		if (insn->dst_reg >= MAX_BPF_REG) {
+			verbose(env, "R%d is invalid\n", insn->dst_reg);
+			return -EINVAL;
+		}
+		if (insn->src_reg >= MAX_BPF_REG) {
+			verbose(env, "R%d is invalid\n", insn->src_reg);
+			return -EINVAL;
+		}
 	}
 
 	/* now all pseudo BPF_LD_IMM64 instructions load valid
-- 
2.52.0

Re: [PATCH bpf-next 1/6] bpf: Do register range validation early

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 2207 bytes --]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... mark_reg_known_zero, mark_reg_unknown, mark_reg_not_init
      WARN_ON guards removed ... ]

> @@ -3957,11 +3936,6 @@ static int __check_reg_arg(...)
>  	struct bpf_insn *insn = env->prog->insnsi + env->insn_idx;
>  	struct bpf_reg_state *reg;
>  	bool rw64;
> -
> -	if (regno >= MAX_BPF_REG) {
> -		verbose(env, "R%d is invalid\n", regno);
> -		return -EINVAL;
> -	}
>
>  	mark_reg_scratched(env, regno);

[ ... ]

> @@ -22070,6 +22044,14 @@
> 			verbose(env, "unknown opcode %02x\n", insn->code);
> 			return -EINVAL;
> 		}
> +		if (insn->dst_reg >= MAX_BPF_REG) {
> +			verbose(env, "R%d is invalid\n", insn->dst_reg);
> +			return -EINVAL;
> +		}
> +		if (insn->src_reg >= MAX_BPF_REG) {
> +			verbose(env, "R%d is invalid\n", insn->src_reg);
> +			return -EINVAL;
> +		}
>  	}

These new checks are placed after the BPF_LD_IMM64 handling block
in resolve_pseudo_ldimm64(). That block exits via the next_insn
label:

    next_insn:
            insn++;
            i++;
            continue;

The continue skips the new dst_reg/src_reg validation for
BPF_LD_IMM64 instructions. Since insn->dst_reg is a 4-bit
field (range 0-15) and MAX_BPF_REG is 11, could a crafted
BPF_LD_IMM64 instruction with dst_reg >= 11 reach
check_ld_imm() without ever being validated?

check_ld_imm() passes insn->dst_reg to check_reg_arg(),
which calls __check_reg_arg(), where the bounds check was
removed by this patch. That leads to regs[regno] with
regno >= MAX_BPF_REG, which is an out-of-bounds access on
struct bpf_func_state.regs[MAX_BPF_REG].

The fields immediately after regs[] in bpf_func_state are
callsite, frameno, and subprogno, so the OOB write would
corrupt verifier state.

Would it make sense to add the dst_reg/src_reg validation
inside the BPF_LD_IMM64 block, or move the new checks above
that block so they apply to all instructions?


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

Re: [PATCH bpf-next 1/6] bpf: Do register range validation early

[Alexei Starovoitov]

On Tue, Mar 31, 2026 at 8:38 PM <bot+bpf-ci@kernel.org> wrote:
>
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
>
> [ ... mark_reg_known_zero, mark_reg_unknown, mark_reg_not_init
>       WARN_ON guards removed ... ]
>
> > @@ -3957,11 +3936,6 @@ static int __check_reg_arg(...)
> >       struct bpf_insn *insn = env->prog->insnsi + env->insn_idx;
> >       struct bpf_reg_state *reg;
> >       bool rw64;
> > -
> > -     if (regno >= MAX_BPF_REG) {
> > -             verbose(env, "R%d is invalid\n", regno);
> > -             return -EINVAL;
> > -     }
> >
> >       mark_reg_scratched(env, regno);
>
> [ ... ]
>
> > @@ -22070,6 +22044,14 @@
> >                       verbose(env, "unknown opcode %02x\n", insn->code);
> >                       return -EINVAL;
> >               }
> > +             if (insn->dst_reg >= MAX_BPF_REG) {
> > +                     verbose(env, "R%d is invalid\n", insn->dst_reg);
> > +                     return -EINVAL;
> > +             }
> > +             if (insn->src_reg >= MAX_BPF_REG) {
> > +                     verbose(env, "R%d is invalid\n", insn->src_reg);
> > +                     return -EINVAL;
> > +             }
> >       }
>
> These new checks are placed after the BPF_LD_IMM64 handling block
> in resolve_pseudo_ldimm64(). That block exits via the next_insn
> label:
>
>     next_insn:
>             insn++;
>             i++;
>             continue;
>
> The continue skips the new dst_reg/src_reg validation for
> BPF_LD_IMM64 instructions. Since insn->dst_reg is a 4-bit
> field (range 0-15) and MAX_BPF_REG is 11, could a crafted
> BPF_LD_IMM64 instruction with dst_reg >= 11 reach
> check_ld_imm() without ever being validated?

Nice one. Will fix.

Re: [PATCH bpf-next 1/6] bpf: Do register range validation early

[Mykyta Yatsenko]

On 4/1/26 3:16 AM, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> Instead of checking src/dst range multiple times during
> the main verifier pass do them once.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---
resolve_pseudo_ldimm64() runs earlier into verification, so it makes 
sense to move this basic check there and remove from other places. Looks 
good, other than issue that AI found.
>   kernel/bpf/verifier.c | 34 ++++++++--------------------------
>   1 file changed, 8 insertions(+), 26 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 8c1cf2eb6cbb..3ec786361698 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2249,13 +2249,6 @@ static void __mark_reg_const_zero(const struct bpf_verifier_env *env, struct bpf
>   static void mark_reg_known_zero(struct bpf_verifier_env *env,
>   				struct bpf_reg_state *regs, u32 regno)
>   {
> -	if (WARN_ON(regno >= MAX_BPF_REG)) {
> -		verbose(env, "mark_reg_known_zero(regs, %u)\n", regno);
> -		/* Something bad happened, let's kill all regs */
> -		for (regno = 0; regno < MAX_BPF_REG; regno++)
> -			__mark_reg_not_init(env, regs + regno);
> -		return;
> -	}
>   	__mark_reg_known_zero(regs + regno);
>   }
>   
> @@ -2908,13 +2901,6 @@ static void __mark_reg_unknown(const struct bpf_verifier_env *env,
>   static void mark_reg_unknown(struct bpf_verifier_env *env,
>   			     struct bpf_reg_state *regs, u32 regno)
>   {
> -	if (WARN_ON(regno >= MAX_BPF_REG)) {
> -		verbose(env, "mark_reg_unknown(regs, %u)\n", regno);
> -		/* Something bad happened, let's kill all regs except FP */
> -		for (regno = 0; regno < BPF_REG_FP; regno++)
> -			__mark_reg_not_init(env, regs + regno);
> -		return;
> -	}
>   	__mark_reg_unknown(env, regs + regno);
>   }
>   
> @@ -2947,13 +2933,6 @@ static void __mark_reg_not_init(const struct bpf_verifier_env *env,
>   static void mark_reg_not_init(struct bpf_verifier_env *env,
>   			      struct bpf_reg_state *regs, u32 regno)
>   {
> -	if (WARN_ON(regno >= MAX_BPF_REG)) {
> -		verbose(env, "mark_reg_not_init(regs, %u)\n", regno);
> -		/* Something bad happened, let's kill all regs except FP */
> -		for (regno = 0; regno < BPF_REG_FP; regno++)
> -			__mark_reg_not_init(env, regs + regno);
> -		return;
> -	}
>   	__mark_reg_not_init(env, regs + regno);
>   }
>   
> @@ -3958,11 +3937,6 @@ static int __check_reg_arg(struct bpf_verifier_env *env, struct bpf_reg_state *r
>   	struct bpf_reg_state *reg;
>   	bool rw64;
>   
> -	if (regno >= MAX_BPF_REG) {
> -		verbose(env, "R%d is invalid\n", regno);
> -		return -EINVAL;
> -	}
> -
>   	mark_reg_scratched(env, regno);
>   
>   	reg = &regs[regno];
> @@ -22070,6 +22044,14 @@ static int resolve_pseudo_ldimm64(struct bpf_verifier_env *env)
>   			verbose(env, "unknown opcode %02x\n", insn->code);
>   			return -EINVAL;
>   		}
> +		if (insn->dst_reg >= MAX_BPF_REG) {
> +			verbose(env, "R%d is invalid\n", insn->dst_reg);
> +			return -EINVAL;
> +		}
> +		if (insn->src_reg >= MAX_BPF_REG) {
> +			verbose(env, "R%d is invalid\n", insn->src_reg);
> +			return -EINVAL;
> +		}
>   	}
>   
>   	/* now all pseudo BPF_LD_IMM64 instructions load valid

Re: [PATCH bpf-next 1/6] bpf: Do register range validation early

[Alexei Starovoitov]

On Wed, Apr 1, 2026 at 8:56 AM Mykyta Yatsenko
<mykyta.yatsenko5@gmail.com> wrote:
>
> On 4/1/26 3:16 AM, Alexei Starovoitov wrote:
> > From: Alexei Starovoitov <ast@kernel.org>
> >
> > Instead of checking src/dst range multiple times during
> > the main verifier pass do them once.
> >
> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > ---
> resolve_pseudo_ldimm64() runs earlier into verification, so it makes
> sense to move this basic check there and remove from other places. Looks
> good, other than issue that AI found.

btw as a next step I'll move all of the insn validation out of
the main pass. We're wasting cycles revalidating the same insn
multiple times.

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

[Alexei Starovoitov]

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);
+	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++) {
+				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;
-- 
2.52.0

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

[Mykyta Yatsenko]

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;

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

[Eduard Zingerman]

On Wed, 2026-04-01 at 18:06 +0100, Mykyta Yatsenko wrote:

[...]

> > +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.

Agree with Mykyta here, remembering the index to return to would be nice here.

> > +				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--;
> > +			}
> > +		}
> > +	}

[...]

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

[Alexei Starovoitov]

On Wed, Apr 1, 2026 at 2:10 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2026-04-01 at 18:06 +0100, Mykyta Yatsenko wrote:
>
> [...]
>
> > > +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.
>
> Agree with Mykyta here, remembering the index to return to would be nice here.

Sorry, but it will be too ugly for no good reason.
Instead of simple: int *dfs_stack it would need to be a stack
of pairs (subprog, last_idx) and what for?
So we don't rescan prog insns? Even if there are 100 calls in a subprog.
We quickly skip them over with this loop. Processed calls
are also discarded.
I prototyped it and didn't like what I saw.

[PATCH bpf-next 3/6] selftests/bpf: Add tests for subprog topological ordering

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Add few tests for topo sort:
- linear chain: main -> A -> B
- diamond: main -> A, main -> B, A -> C, B -> C
- mixed global/static: main -> global -> static leaf
- shared callee: main -> leaf, main -> global -> leaf
- duplicate calls: main calls same subprog twice
- no calls: single subprog

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../bpf/progs/verifier_subprog_topo.c         | 226 ++++++++++++++++++
 2 files changed, 228 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_subprog_topo.c

diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index bcf01cb4cfe4..1ac366fd4dae 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -93,6 +93,7 @@
 #include "verifier_stack_ptr.skel.h"
 #include "verifier_store_release.skel.h"
 #include "verifier_subprog_precision.skel.h"
+#include "verifier_subprog_topo.skel.h"
 #include "verifier_subreg.skel.h"
 #include "verifier_tailcall.skel.h"
 #include "verifier_tailcall_jit.skel.h"
@@ -238,6 +239,7 @@ void test_verifier_spin_lock(void)            { RUN(verifier_spin_lock); }
 void test_verifier_stack_ptr(void)            { RUN(verifier_stack_ptr); }
 void test_verifier_store_release(void)        { RUN(verifier_store_release); }
 void test_verifier_subprog_precision(void)    { RUN(verifier_subprog_precision); }
+void test_verifier_subprog_topo(void)        { RUN(verifier_subprog_topo); }
 void test_verifier_subreg(void)               { RUN(verifier_subreg); }
 void test_verifier_tailcall(void)             { RUN(verifier_tailcall); }
 void test_verifier_tailcall_jit(void)         { RUN(verifier_tailcall_jit); }
diff --git a/tools/testing/selftests/bpf/progs/verifier_subprog_topo.c b/tools/testing/selftests/bpf/progs/verifier_subprog_topo.c
new file mode 100644
index 000000000000..e2b9d14bbc3d
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_subprog_topo.c
@@ -0,0 +1,226 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+/* linear chain main -> A -> B */
+__naked __noinline __used
+static unsigned long linear_b(void)
+{
+	asm volatile (
+		"r0 = 42;"
+		"exit;"
+	);
+}
+
+__naked __noinline __used
+static unsigned long linear_a(void)
+{
+	asm volatile (
+		"call linear_b;"
+		"exit;"
+	);
+}
+
+SEC("?raw_tp")
+__success __log_level(2)
+__msg("topo_order[0] = linear_b")
+__msg("topo_order[1] = linear_a")
+__msg("topo_order[2] = topo_linear")
+__naked int topo_linear(void)
+{
+	asm volatile (
+		"call linear_a;"
+		"exit;"
+	);
+}
+
+/* diamond main -> A, main -> B, A -> C, B -> C */
+__naked __noinline __used
+static unsigned long diamond_c(void)
+{
+	asm volatile (
+		"r0 = 1;"
+		"exit;"
+	);
+}
+
+__naked __noinline __used
+static unsigned long diamond_b(void)
+{
+	asm volatile (
+		"call diamond_c;"
+		"exit;"
+	);
+}
+
+__naked __noinline __used
+static unsigned long diamond_a(void)
+{
+	asm volatile (
+		"call diamond_c;"
+		"exit;"
+	);
+}
+
+SEC("?raw_tp")
+__success __log_level(2)
+__msg("topo_order[0] = diamond_c")
+__msg("topo_order[3] = topo_diamond")
+__naked int topo_diamond(void)
+{
+	asm volatile (
+		"call diamond_a;"
+		"call diamond_b;"
+		"exit;"
+	);
+}
+
+/* main -> global_a (global) -> static_leaf (static, leaf) */
+__naked __noinline __used
+static unsigned long static_leaf(void)
+{
+	asm volatile (
+		"r0 = 7;"
+		"exit;"
+	);
+}
+
+__noinline __used
+int global_a(int x)
+{
+	return static_leaf();
+}
+
+SEC("?raw_tp")
+__success __log_level(2)
+__msg("topo_order[0] = static_leaf")
+__msg("topo_order[1] = global_a")
+__msg("topo_order[2] = topo_mixed")
+__naked int topo_mixed(void)
+{
+	asm volatile (
+		"r1 = 0;"
+		"call global_a;"
+		"exit;"
+	);
+}
+
+/*
+ * shared static callee from global and main:
+ * main -> shared_leaf (static)
+ * main -> global_b (global) -> shared_leaf (static)
+ */
+__naked __noinline __used
+static unsigned long shared_leaf(void)
+{
+	asm volatile (
+		"r0 = 99;"
+		"exit;"
+	);
+}
+
+__noinline __used
+int global_b(int x)
+{
+	return shared_leaf();
+}
+
+SEC("?raw_tp")
+__success __log_level(2)
+__msg("topo_order[0] = shared_leaf")
+__msg("topo_order[1] = global_b")
+__msg("topo_order[2] = topo_shared")
+__naked int topo_shared(void)
+{
+	asm volatile (
+		"call shared_leaf;"
+		"r1 = 0;"
+		"call global_b;"
+		"exit;"
+	);
+}
+
+/* duplicate calls to the same subprog */
+__naked __noinline __used
+static unsigned long dup_leaf(void)
+{
+	asm volatile (
+		"r0 = 0;"
+		"exit;"
+	);
+}
+
+SEC("?raw_tp")
+__success __log_level(2)
+__msg("topo_order[0] = dup_leaf")
+__msg("topo_order[1] = topo_dup_calls")
+__naked int topo_dup_calls(void)
+{
+	asm volatile (
+		"call dup_leaf;"
+		"call dup_leaf;"
+		"exit;"
+	);
+}
+
+/* main calls bpf_loop() with loop_cb as the callback */
+static int loop_cb(int idx, void *ctx)
+{
+	return 0;
+}
+
+SEC("?raw_tp")
+__success __log_level(2)
+__msg("topo_order[0] = loop_cb")
+__msg("topo_order[1] = topo_loop_cb")
+int topo_loop_cb(void)
+{
+	bpf_loop(1, loop_cb, NULL, 0);
+	return 0;
+}
+
+/*
+ * bpf_loop callback calling another subprog
+ * main -> bpf_loop(callback=loop_cb2) -> loop_cb2 -> loop_cb2_leaf
+ */
+__naked __noinline __used
+static unsigned long loop_cb2_leaf(void)
+{
+	asm volatile (
+		"r0 = 0;"
+		"exit;"
+	);
+}
+
+static int loop_cb2(int idx, void *ctx)
+{
+	return loop_cb2_leaf();
+}
+
+SEC("?raw_tp")
+__success __log_level(2)
+__msg("topo_order[0] = loop_cb2_leaf")
+__msg("topo_order[1] = loop_cb2")
+__msg("topo_order[2] = topo_loop_cb_chain")
+int topo_loop_cb_chain(void)
+{
+	bpf_loop(1, loop_cb2, NULL, 0);
+	return 0;
+}
+
+/* no calls (single subprog) */
+SEC("?raw_tp")
+__success __log_level(2)
+__msg("topo_order[0] = topo_no_calls")
+__naked int topo_no_calls(void)
+{
+	asm volatile (
+		"r0 = 0;"
+		"exit;"
+	);
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.52.0

[PATCH bpf-next 4/6] bpf: Add compute_const_regs() and prune_dead_branches() passes

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Add two passes before the main verifier pass:

compute_const_regs() is a forward dataflow analysis that tracks
register values in R0-R9 across the program using fixed-point
iteration in reverse postorder. Each register is tracked with
a six-state lattice:

  UNVISITED -> CONST(val) / MAP_PTR(map_index) /
               MAP_VALUE(map_index, offset) / SUBPROG(num) -> UNKNOWN

At merge points, if two paths produce the same state and value for
a register, it stays; otherwise it becomes UNKNOWN.

The analysis handles:
 - MOV, ADD, SUB, AND with immediate or register operands
 - LD_IMM64 for plain constants, map FDs, map values, and subprogs
 - LDX from read-only maps: constant-folds the load by reading the
   map value directly via bpf_map_direct_read()

Results that fit in 32 bits are stored per-instruction in
insn_aux_data and bitmasks.

prune_dead_branches() uses the computed constants to evaluate
conditional branches. When both operands of a conditional jump are
known constants, the branch outcome is determined statically and the
instruction is rewritten to an unconditional jump.
The CFG postorder is then recomputed to reflect new control flow.
This eliminates dead edges so that subsequent liveness analysis
doesn't propagate through dead code.

Also add runtime sanity check to validate that precomputed
constants match the verifier's tracked state.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h                  |  23 ++
 kernel/bpf/Makefile                           |   2 +-
 kernel/bpf/const_fold.c                       | 385 ++++++++++++++++++
 kernel/bpf/verifier.c                         |  43 +-
 .../selftests/bpf/progs/verifier_scalar_ids.c |  20 +-
 5 files changed, 458 insertions(+), 15 deletions(-)
 create mode 100644 kernel/bpf/const_fold.c

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 4f492eaad5c2..0d797de30a3a 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -595,6 +595,18 @@ struct bpf_insn_aux_data {
 	u32 scc;
 	/* registers alive before this instruction. */
 	u16 live_regs_before;
+	/*
+	 * Bitmask of R0-R9 that hold known values at this instruction.
+	 * const_reg_mask: scalar constants that fit in 32 bits.
+	 * const_reg_map_mask: map pointers, val is map_index into used_maps[].
+	 * const_reg_subprog_mask: subprog pointers, val is subprog number.
+	 * const_reg_vals[i] holds the 32-bit value for register i.
+	 * Populated by compute_const_regs() pre-pass.
+	 */
+	u16 const_reg_mask;
+	u16 const_reg_map_mask;
+	u16 const_reg_subprog_mask;
+	u32 const_reg_vals[10];
 };
 
 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
@@ -943,6 +955,10 @@ void bpf_free_kfunc_btf_tab(struct bpf_kfunc_btf_tab *tab);
 
 int mark_chain_precision(struct bpf_verifier_env *env, int regno);
 
+bool bpf_map_is_rdonly(const struct bpf_map *map);
+int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val,
+			bool is_ldsx);
+
 #define BPF_BASE_TYPE_MASK	GENMASK(BPF_BASE_TYPE_BITS - 1, 0)
 
 /* extract base type from bpf_{arg, return, reg}_type. */
@@ -1086,6 +1102,13 @@ struct bpf_iarray *bpf_insn_successors(struct bpf_verifier_env *env, u32 idx);
 void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask);
 bool bpf_calls_callback(struct bpf_verifier_env *env, int insn_idx);
 
+int find_subprog(struct bpf_verifier_env *env, int off);
+int compute_const_regs(struct bpf_verifier_env *env);
+int prune_dead_branches(struct bpf_verifier_env *env);
+int compute_postorder(struct bpf_verifier_env *env);
+bool insn_is_cond_jump(u8 code);
+bool is_may_goto_insn(struct bpf_insn *insn);
+
 int bpf_stack_liveness_init(struct bpf_verifier_env *env);
 void bpf_stack_liveness_free(struct bpf_verifier_env *env);
 int bpf_update_live_stack(struct bpf_verifier_env *env);
diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
index 79cf22860a99..b8ae7b0988a4 100644
--- a/kernel/bpf/Makefile
+++ b/kernel/bpf/Makefile
@@ -6,7 +6,7 @@ cflags-nogcse-$(CONFIG_X86)$(CONFIG_CC_IS_GCC) := -fno-gcse
 endif
 CFLAGS_core.o += -Wno-override-init $(cflags-nogcse-yy)
 
-obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o log.o token.o liveness.o
+obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o log.o token.o liveness.o const_fold.o
 obj-$(CONFIG_BPF_SYSCALL) += bpf_iter.o map_iter.o task_iter.o prog_iter.o link_iter.o
 obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o
 obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o bpf_insn_array.o
diff --git a/kernel/bpf/const_fold.c b/kernel/bpf/const_fold.c
new file mode 100644
index 000000000000..9e5abc6ab46a
--- /dev/null
+++ b/kernel/bpf/const_fold.c
@@ -0,0 +1,385 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
+
+#include <linux/bpf_verifier.h>
+
+/*
+ * Forward dataflow analysis to determine constant register values at every
+ * instruction. Tracks 64-bit constant values in R0-R9 through the program,
+ * using a fixed-point iteration in reverse postorder. Records which registers
+ * hold known constants and their values in
+ * env->insn_aux_data[].{const_reg_mask, const_reg_vals}.
+ */
+
+enum const_arg_state {
+	CONST_ARG_UNVISITED,	/* instruction not yet reached */
+	CONST_ARG_UNKNOWN,	/* register value not a known constant */
+	CONST_ARG_CONST,	/* register holds a known 64-bit constant */
+	CONST_ARG_MAP_PTR,	/* register holds a map pointer, map_index is set */
+	CONST_ARG_MAP_VALUE,	/* register points to map value data, val is offset */
+	CONST_ARG_SUBPROG,	/* register holds a subprog pointer, val is subprog number */
+};
+
+struct const_arg_info {
+	enum const_arg_state state;
+	u32 map_index;
+	u64 val;
+};
+
+static bool ci_is_unvisited(const struct const_arg_info *ci)
+{
+	return ci->state == CONST_ARG_UNVISITED;
+}
+
+static bool ci_is_unknown(const struct const_arg_info *ci)
+{
+	return ci->state == CONST_ARG_UNKNOWN;
+}
+
+static bool ci_is_const(const struct const_arg_info *ci)
+{
+	return ci->state == CONST_ARG_CONST;
+}
+
+static bool ci_is_map_value(const struct const_arg_info *ci)
+{
+	return ci->state == CONST_ARG_MAP_VALUE;
+}
+
+/* Transfer function: compute output register state from instruction. */
+static void const_reg_xfer(struct bpf_verifier_env *env, struct const_arg_info *ci_out,
+			   struct bpf_insn *insn, struct bpf_insn *insns, int idx)
+{
+	struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 };
+	struct const_arg_info *dst = &ci_out[insn->dst_reg];
+	struct const_arg_info *src = &ci_out[insn->src_reg];
+	u8 class = BPF_CLASS(insn->code);
+	u8 opcode = BPF_OP(insn->code) | BPF_SRC(insn->code);
+	int r;
+
+	switch (class) {
+	case BPF_ALU:
+	case BPF_ALU64:
+		switch (opcode) {
+		case BPF_MOV | BPF_K:
+			dst->state = CONST_ARG_CONST;
+			dst->val = (s64)insn->imm;
+			break;
+		case BPF_MOV | BPF_X:
+			*dst = *src;
+			if (!insn->off)
+				break;
+			if (!ci_is_const(dst)) {
+				*dst = unknown;
+				break;
+			}
+			switch (insn->off) {
+			case 8:  dst->val = (s8)dst->val; break;
+			case 16: dst->val = (s16)dst->val; break;
+			case 32: dst->val = (s32)dst->val; break;
+			default: *dst = unknown; break;
+			}
+			break;
+		case BPF_ADD | BPF_K:
+			if (!ci_is_const(dst) && !ci_is_map_value(dst)) {
+				*dst = unknown;
+				break;
+			}
+			dst->val += insn->imm;
+			break;
+		case BPF_SUB | BPF_K:
+			if (!ci_is_const(dst) && !ci_is_map_value(dst)) {
+				*dst = unknown;
+				break;
+			}
+			dst->val -= insn->imm;
+			break;
+		case BPF_AND | BPF_K:
+			if (!ci_is_const(dst)) {
+				if (!insn->imm) {
+					dst->state = CONST_ARG_CONST;
+					dst->val = 0;
+				} else {
+					*dst = unknown;
+				}
+				break;
+			}
+			dst->val &= (s64)insn->imm;
+			break;
+		case BPF_AND | BPF_X:
+			if (ci_is_const(dst) && dst->val == 0)
+				break; /* 0 & x == 0 */
+			if (ci_is_const(src) && src->val == 0) {
+				dst->state = CONST_ARG_CONST;
+				dst->val = 0;
+				break;
+			}
+			if (!ci_is_const(dst) || !ci_is_const(src)) {
+				*dst = unknown;
+				break;
+			}
+			dst->val &= src->val;
+			break;
+		default:
+			*dst = unknown;
+			break;
+		}
+		if (class == BPF_ALU) {
+			if (ci_is_const(dst))
+				dst->val = (u32)dst->val;
+			else if (!ci_is_unknown(dst))
+				*dst = unknown;
+		}
+		break;
+	case BPF_LD:
+		if (BPF_MODE(insn->code) != BPF_IMM || BPF_SIZE(insn->code) != BPF_DW)
+			break;
+		if (insn->src_reg == BPF_PSEUDO_FUNC) {
+			int subprog = find_subprog(env, idx + insn->imm + 1);
+
+			if (subprog >= 0) {
+				dst->state = CONST_ARG_SUBPROG;
+				dst->val = subprog;
+			} else {
+				*dst = unknown;
+			}
+		} else if (insn->src_reg == BPF_PSEUDO_MAP_VALUE ||
+			   insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE) {
+			dst->state = CONST_ARG_MAP_VALUE;
+			dst->map_index = env->insn_aux_data[idx].map_index;
+			dst->val = env->insn_aux_data[idx].map_off;
+		} else if (insn->src_reg == BPF_PSEUDO_MAP_FD ||
+			   insn->src_reg == BPF_PSEUDO_MAP_IDX) {
+			dst->state = CONST_ARG_MAP_PTR;
+			dst->map_index = env->insn_aux_data[idx].map_index;
+		} else if (insn->src_reg == 0) {
+			dst->state = CONST_ARG_CONST;
+			dst->val = (u64)(u32)insn->imm | ((u64)(u32)insns[idx + 1].imm << 32);
+		} else {
+			*dst = unknown;
+		}
+		break;
+	case BPF_LDX:
+		if (!ci_is_map_value(src)) {
+			*dst = unknown;
+			break;
+		}
+		struct bpf_map *map = env->used_maps[src->map_index];
+		int size = bpf_size_to_bytes(BPF_SIZE(insn->code));
+		bool is_ldsx = BPF_MODE(insn->code) == BPF_MEMSX;
+		int off = src->val + insn->off;
+		u64 val = 0;
+
+		if (!bpf_map_is_rdonly(map) || !map->ops->map_direct_value_addr ||
+		    bpf_map_direct_read(map, off, size, &val, is_ldsx)) {
+			*dst = unknown;
+			break;
+		}
+		dst->state = CONST_ARG_CONST;
+		dst->val = val;
+		break;
+	case BPF_JMP:
+		if (opcode != BPF_CALL)
+			break;
+		for (r = BPF_REG_0; r <= BPF_REG_5; r++)
+			ci_out[r] = unknown;
+		break;
+	case BPF_STX:
+		if (BPF_MODE(insn->code) != BPF_ATOMIC)
+			break;
+		if (insn->imm == BPF_CMPXCHG)
+			ci_out[BPF_REG_0] = unknown;
+		else if (insn->imm == BPF_LOAD_ACQ)
+			*dst = unknown;
+		else if (insn->imm & BPF_FETCH)
+			*src = unknown;
+		break;
+	}
+}
+
+/* Join function: merge output state into a successor's input state. */
+static bool const_reg_join(struct const_arg_info *ci_target,
+			   struct const_arg_info *ci_out)
+{
+	bool changed = false;
+	int r;
+
+	for (r = 0; r < MAX_BPF_REG; r++) {
+		struct const_arg_info *old = &ci_target[r];
+		struct const_arg_info *new = &ci_out[r];
+
+		if (ci_is_unvisited(old) && !ci_is_unvisited(new)) {
+			ci_target[r] = *new;
+			changed = true;
+		} else if (!ci_is_unknown(old) && !ci_is_unvisited(old) &&
+			   (new->state != old->state || new->val != old->val ||
+			    new->map_index != old->map_index)) {
+			old->state = CONST_ARG_UNKNOWN;
+			changed = true;
+		}
+	}
+	return changed;
+}
+
+int compute_const_regs(struct bpf_verifier_env *env)
+{
+	struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 };
+	struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;
+	struct bpf_insn *insns = env->prog->insnsi;
+	int insn_cnt = env->prog->len;
+	struct const_arg_info (*ci_in)[MAX_BPF_REG];
+	struct const_arg_info ci_out[MAX_BPF_REG];
+	struct bpf_iarray *succ;
+	bool changed;
+	int i, r;
+
+	/* kvzalloc zeroes memory, so all entries start as CONST_ARG_UNVISITED (0) */
+	ci_in = kvzalloc_objs(*ci_in, insn_cnt, GFP_KERNEL_ACCOUNT);
+	if (!ci_in)
+		return -ENOMEM;
+
+	/* Subprogram entries (including main at subprog 0): all registers unknown */
+	for (i = 0; i < env->subprog_cnt; i++) {
+		int start = env->subprog_info[i].start;
+
+		for (r = 0; r < MAX_BPF_REG; r++)
+			ci_in[start][r] = unknown;
+	}
+
+redo:
+	changed = false;
+	for (i = env->cfg.cur_postorder - 1; i >= 0; i--) {
+		int idx = env->cfg.insn_postorder[i];
+		struct bpf_insn *insn = &insns[idx];
+		struct const_arg_info *ci = ci_in[idx];
+
+		memcpy(ci_out, ci, sizeof(ci_out));
+
+		const_reg_xfer(env, ci_out, insn, insns, idx);
+
+		succ = bpf_insn_successors(env, idx);
+		for (int s = 0; s < succ->cnt; s++)
+			changed |= const_reg_join(ci_in[succ->items[s]], ci_out);
+	}
+	if (changed)
+		goto redo;
+
+	/* Save computed constants into insn_aux[] if they fit into 32-bit */
+	for (i = 0; i < insn_cnt; i++) {
+		u16 mask = 0, map_mask = 0, subprog_mask = 0;
+		struct bpf_insn_aux_data *aux = &insn_aux[i];
+		struct const_arg_info *ci = ci_in[i];
+
+		for (r = BPF_REG_0; r < MAX_BPF_REG; r++) {
+			struct const_arg_info *c = &ci[r];
+
+			switch (c->state) {
+			case CONST_ARG_CONST: {
+				u64 val = c->val;
+
+				if (val != (u32)val)
+					break;
+				mask |= BIT(r);
+				aux->const_reg_vals[r] = val;
+				break;
+			}
+			case CONST_ARG_MAP_PTR:
+				map_mask |= BIT(r);
+				aux->const_reg_vals[r] = c->map_index;
+				break;
+			case CONST_ARG_SUBPROG:
+				subprog_mask |= BIT(r);
+				aux->const_reg_vals[r] = c->val;
+				break;
+			default:
+				break;
+			}
+		}
+		aux->const_reg_mask = mask;
+		aux->const_reg_map_mask = map_mask;
+		aux->const_reg_subprog_mask = subprog_mask;
+	}
+
+	kvfree(ci_in);
+	return 0;
+}
+
+static bool eval_const_branch(u8 opcode, u64 dst_val, u64 src_val)
+{
+	switch (BPF_OP(opcode)) {
+	case BPF_JEQ:	return dst_val == src_val;
+	case BPF_JNE:	return dst_val != src_val;
+	case BPF_JGT:	return dst_val > src_val;
+	case BPF_JGE:	return dst_val >= src_val;
+	case BPF_JLT:	return dst_val < src_val;
+	case BPF_JLE:	return dst_val <= src_val;
+	case BPF_JSGT:	return (s64)dst_val > (s64)src_val;
+	case BPF_JSGE:	return (s64)dst_val >= (s64)src_val;
+	case BPF_JSLT:	return (s64)dst_val < (s64)src_val;
+	case BPF_JSLE:	return (s64)dst_val <= (s64)src_val;
+	case BPF_JSET:	return dst_val & src_val;
+	default:	return false;
+	}
+}
+
+/*
+ * Rewrite conditional branches with constant outcomes into unconditional
+ * jumps using register values resolved by compute_const_regs() pass.
+ * This eliminates dead edges from the CFG so that compute_live_registers()
+ * doesn't propagate liveness through dead code.
+ */
+int prune_dead_branches(struct bpf_verifier_env *env)
+{
+	struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;
+	struct bpf_insn *insns = env->prog->insnsi;
+	int insn_cnt = env->prog->len;
+	bool changed = false;
+	int i;
+
+	for (i = 0; i < insn_cnt; i++) {
+		struct bpf_insn_aux_data *aux = &insn_aux[i];
+		struct bpf_insn *insn = &insns[i];
+		u8 class = BPF_CLASS(insn->code);
+		u64 dst_val, src_val;
+		bool taken;
+
+		if (!insn_is_cond_jump(insn->code))
+			continue;
+		if (is_may_goto_insn(insn))
+			continue;
+
+		if (!(aux->const_reg_mask & BIT(insn->dst_reg)))
+			continue;
+		dst_val = aux->const_reg_vals[insn->dst_reg];
+
+		if (BPF_SRC(insn->code) == BPF_K) {
+			src_val = (u32)insn->imm;
+		} else {
+			if (!(aux->const_reg_mask & BIT(insn->src_reg)))
+				continue;
+			src_val = aux->const_reg_vals[insn->src_reg];
+		}
+
+		if (class == BPF_JMP32) {
+			/*
+			 * The (s32) cast maps the 32-bit range into two u64 sub-ranges:
+			 * [0x00000000, 0x7FFFFFFF] -> [0x0000000000000000, 0x000000007FFFFFFF]
+			 * [0x80000000, 0xFFFFFFFF] -> [0xFFFFFFFF80000000, 0xFFFFFFFFFFFFFFFF]
+			 * The ordering is preserved within each sub-range, and
+			 * the second sub-range is above the first as u64.
+			 */
+			dst_val = (s32)dst_val;
+			src_val = (s32)src_val;
+		}
+
+		taken = eval_const_branch(insn->code, dst_val, src_val);
+		*insn = BPF_JMP_A(taken ? insn->off : 0);
+		changed = true;
+	}
+
+	if (!changed)
+		return 0;
+	/* recompute postorder, since CFG has changed */
+	kvfree(env->cfg.insn_postorder);
+	return compute_postorder(env);
+}
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 432806011d47..493f6acaa386 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -595,7 +595,7 @@ static bool is_async_cb_sleepable(struct bpf_verifier_env *env, struct bpf_insn
 	return false;
 }
 
-static bool is_may_goto_insn(struct bpf_insn *insn)
+bool is_may_goto_insn(struct bpf_insn *insn)
 {
 	return insn->code == (BPF_JMP | BPF_JCOND) && insn->src_reg == BPF_MAY_GOTO;
 }
@@ -3082,7 +3082,7 @@ struct bpf_subprog_info *bpf_find_containing_subprog(struct bpf_verifier_env *en
 }
 
 /* Find subprogram that starts exactly at 'off' */
-static int find_subprog(struct bpf_verifier_env *env, int off)
+int find_subprog(struct bpf_verifier_env *env, int off)
 {
 	struct bpf_subprog_info *p;
 
@@ -7287,7 +7287,7 @@ static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size)
 	set_sext32_default_val(reg, size);
 }
 
-static bool bpf_map_is_rdonly(const struct bpf_map *map)
+bool bpf_map_is_rdonly(const struct bpf_map *map)
 {
 	/* A map is considered read-only if the following condition are true:
 	 *
@@ -7307,8 +7307,8 @@ static bool bpf_map_is_rdonly(const struct bpf_map *map)
 	       !bpf_map_write_active(map);
 }
 
-static int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val,
-			       bool is_ldsx)
+int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val,
+			bool is_ldsx)
 {
 	void *ptr;
 	u64 addr;
@@ -19234,7 +19234,7 @@ static int check_cfg(struct bpf_verifier_env *env)
  * [env->subprog_info[i].postorder_start, env->subprog_info[i+1].postorder_start)
  * with indices of 'i' instructions in postorder.
  */
-static int compute_postorder(struct bpf_verifier_env *env)
+int compute_postorder(struct bpf_verifier_env *env)
 {
 	u32 cur_postorder, i, top, stack_sz, s;
 	int *stack = NULL, *postorder = NULL, *state = NULL;
@@ -21538,6 +21538,27 @@ static int do_check(struct bpf_verifier_env *env)
 		sanitize_mark_insn_seen(env);
 		prev_insn_idx = env->insn_idx;
 
+		/* Sanity check: precomputed constants must match verifier state */
+		if (!state->speculative && insn_aux->const_reg_mask) {
+			struct bpf_reg_state *regs = cur_regs(env);
+			u16 mask = insn_aux->const_reg_mask;
+
+			for (int r = 0; r < MAX_BPF_REG; r++) {
+				u32 cval = insn_aux->const_reg_vals[r];
+
+				if (!(mask & BIT(r)))
+					continue;
+				if (regs[r].type != SCALAR_VALUE)
+					continue;
+				if (!tnum_is_const(regs[r].var_off))
+					continue;
+				if (verifier_bug_if((u32)regs[r].var_off.value != cval,
+						    env, "const R%d: %u != %llu",
+						    r, cval, regs[r].var_off.value))
+					return -EFAULT;
+			}
+		}
+
 		/* Reduce verification complexity by stopping speculative path
 		 * verification when a nospec is encountered.
 		 */
@@ -22527,7 +22548,7 @@ static void sanitize_dead_code(struct bpf_verifier_env *env)
 	}
 }
 
-static bool insn_is_cond_jump(u8 code)
+bool insn_is_cond_jump(u8 code)
 {
 	u8 op;
 
@@ -26353,6 +26374,14 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 	if (ret)
 		goto skip_full_check;
 
+	ret = compute_const_regs(env);
+	if (ret < 0)
+		goto skip_full_check;
+
+	ret = prune_dead_branches(env);
+	if (ret < 0)
+		goto skip_full_check;
+
 	ret = sort_subprogs_topo(env);
 	if (ret < 0)
 		goto skip_full_check;
diff --git a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
index 58c7704d61cd..0e907cad5902 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
@@ -592,10 +592,10 @@ __naked void check_ids_in_regsafe_2(void)
  */
 SEC("socket")
 __success __log_level(2)
-__msg("11: (1d) if r3 == r4 goto pc+0")
+__msg("14: (1d) if r3 == r4 goto pc+0")
 __msg("frame 0: propagating r3,r4")
-__msg("11: safe")
-__msg("processed 15 insns")
+__msg("14: safe")
+__msg("processed 18 insns")
 __flag(BPF_F_TEST_STATE_FREQ)
 __naked void no_scalar_id_for_const(void)
 {
@@ -606,13 +606,16 @@ __naked void no_scalar_id_for_const(void)
 	/* possibly generate same scalar ids for r3 and r4 */
 	"r1 = 0;"
 	"r1 = r1;"
+	"r1 |= 0;" /* prevent prune_dead_branches from folding the branch */
 	"r3 = r1;"
 	"r4 = r1;"
 	"goto l1_%=;"
 "l0_%=:"
 	/* possibly generate different scalar ids for r3 and r4 */
 	"r1 = 0;"
+	"r1 |= 0;"
 	"r2 = 0;"
+	"r2 |= 0;"
 	"r3 = r1;"
 	"r4 = r2;"
 "l1_%=:"
@@ -628,10 +631,10 @@ __naked void no_scalar_id_for_const(void)
 /* Same as no_scalar_id_for_const() but for 32-bit values */
 SEC("socket")
 __success __log_level(2)
-__msg("11: (1e) if w3 == w4 goto pc+0")
+__msg("14: (1e) if w3 == w4 goto pc+0")
 __msg("frame 0: propagating r3,r4")
-__msg("11: safe")
-__msg("processed 15 insns")
+__msg("14: safe")
+__msg("processed 18 insns")
 __flag(BPF_F_TEST_STATE_FREQ)
 __naked void no_scalar_id_for_const32(void)
 {
@@ -642,17 +645,20 @@ __naked void no_scalar_id_for_const32(void)
 	/* possibly generate same scalar ids for r3 and r4 */
 	"w1 = 0;"
 	"w1 = w1;"
+	"w1 |= 0;" /* prevent prune_dead_branches from folding the branch */
 	"w3 = w1;"
 	"w4 = w1;"
 	"goto l1_%=;"
 "l0_%=:"
 	/* possibly generate different scalar ids for r3 and r4 */
 	"w1 = 0;"
+	"w1 |= 0;"
 	"w2 = 0;"
+	"w2 |= 0;"
 	"w3 = w1;"
 	"w4 = w2;"
 "l1_%=:"
-	/* predictable jump, marks r1 and r2 precise */
+	/* predictable jump, marks r3 and r4 precise */
 	"if w3 == w4 goto +0;"
 	"r0 = 0;"
 	"exit;"
-- 
2.52.0

Re: [PATCH bpf-next 4/6] bpf: Add compute_const_regs() and prune_dead_branches() passes

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 3685 bytes --]

> diff --git a/kernel/bpf/const_fold.c b/kernel/bpf/const_fold.c
> new file mode 100644
> index 000000000000..9e5abc6ab46a
> --- /dev/null
> +++ b/kernel/bpf/const_fold.c

[ ... ]

> +	/* Save computed constants into insn_aux[] if they fit into 32-bit */
> +	for (i = 0; i < insn_cnt; i++) {
> +		u16 mask = 0, map_mask = 0, subprog_mask = 0;
> +		struct bpf_insn_aux_data *aux = &insn_aux[i];
> +		struct const_arg_info *ci = ci_in[i];
> +
> +		for (r = BPF_REG_0; r < MAX_BPF_REG; r++) {

The loop iterates r from 0 to MAX_BPF_REG - 1 (= 10), but
const_reg_vals[] in bpf_insn_aux_data is declared with 10 elements
(indices 0-9).  When r == 10 and the register happens to be tracked
as a constant, this writes past the end of const_reg_vals[]:

> +			switch (c->state) {
> +			case CONST_ARG_CONST: {
> +				u64 val = c->val;
> +
> +				if (val != (u32)val)
> +					break;
> +				mask |= BIT(r);
> +				aux->const_reg_vals[r] = val;

Would this overflow const_reg_vals[] when r is BPF_REG_10?
The array has 10 entries but the loop goes up to 10 inclusive.

Since compute_const_regs() runs before the main verifier pass,
register numbers in instructions haven't been validated yet.  A
crafted program with dst_reg = BPF_REG_FP in an ALU instruction
would cause the analysis to track R10 as a constant, then
write one element past the array into the next instruction's
bpf_insn_aux_data.

Similarly, in const_reg_xfer():

> +	struct const_arg_info *dst = &ci_out[insn->dst_reg];
> +	struct const_arg_info *src = &ci_out[insn->src_reg];

ci_out is a stack-local array of MAX_BPF_REG (11) elements, but
dst_reg/src_reg are 4-bit fields that can hold values 0-15.
Could instructions with register values above 10 cause an
out-of-bounds access on the stack before the verifier rejects them?

[ ... ]

> +int prune_dead_branches(struct bpf_verifier_env *env)
> +{

[ ... ]

> +		if (BPF_SRC(insn->code) == BPF_K) {
> +			src_val = (u32)insn->imm;

For 64-bit JMP instructions (BPF_JMP class) with BPF_K source, the
BPF interpreter sign-extends the 32-bit immediate to 64 bits:

kernel/bpf/core.c, COND_JMP macro:
    JMP_##OPCODE##_K:
        if ((SIGN##64) DST CMP_OP (SIGN##64) IMM) {

where IMM is insn->imm (s32), so (u64) IMM and (s64) IMM both
sign-extend.

Here the cast (u32)insn->imm zero-extends instead.  For negative
immediates these produce different 64-bit values.  For example,
with imm = -1:

    (u32)(-1) = 0x00000000FFFFFFFF  (what prune_dead_branches uses)
    (s64)(s32)(-1) = 0xFFFFFFFFFFFFFFFF  (what the interpreter uses)

A concrete case: r1 = 0, then "if r1 s> -1 goto target":

    interpreter: (s64)0 > (s64)(-1) = true, branch taken
    prune_dead_branches: (s64)0 > (s64)0xFFFFFFFF = false, not taken

The branch would be incorrectly rewritten to fall-through, and the
jump target becomes dead code.  This also affects unsigned comparisons
when both operands happen to match at 32 bits -- for instance
JGE with dst_val = 0xFFFFFFFF and imm = -1:

    interpreter: 0xFFFFFFFF >= 0xFFFFFFFFFFFFFFFF = false
    prune: 0xFFFFFFFF >= 0xFFFFFFFF = true

Should this be sign-extended to match the interpreter, something like
src_val = insn->imm (relying on the implicit s32 to u64 conversion)?
The JMP32 path already handles this correctly via the subsequent
(s32) cast.

> +		} else {
> +			if (!(aux->const_reg_mask & BIT(insn->src_reg)))
> +				continue;
> +			src_val = aux->const_reg_vals[insn->src_reg];
> +		}

[ ... ]


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

Re: [PATCH bpf-next 4/6] bpf: Add compute_const_regs() and prune_dead_branches() passes

[Alexei Starovoitov]

On Tue, Mar 31, 2026 at 8:49 PM <bot+bpf-ci@kernel.org> wrote:
>
> > diff --git a/kernel/bpf/const_fold.c b/kernel/bpf/const_fold.c
> > new file mode 100644
> > index 000000000000..9e5abc6ab46a
> > --- /dev/null
> > +++ b/kernel/bpf/const_fold.c
>
> [ ... ]
>
> > +     /* Save computed constants into insn_aux[] if they fit into 32-bit */
> > +     for (i = 0; i < insn_cnt; i++) {
> > +             u16 mask = 0, map_mask = 0, subprog_mask = 0;
> > +             struct bpf_insn_aux_data *aux = &insn_aux[i];
> > +             struct const_arg_info *ci = ci_in[i];
> > +
> > +             for (r = BPF_REG_0; r < MAX_BPF_REG; r++) {
>
> The loop iterates r from 0 to MAX_BPF_REG - 1 (= 10), but
> const_reg_vals[] in bpf_insn_aux_data is declared with 10 elements
> (indices 0-9).  When r == 10 and the register happens to be tracked
> as a constant, this writes past the end of const_reg_vals[]:
>
> > +                     switch (c->state) {
> > +                     case CONST_ARG_CONST: {
> > +                             u64 val = c->val;
> > +
> > +                             if (val != (u32)val)
> > +                                     break;
> > +                             mask |= BIT(r);
> > +                             aux->const_reg_vals[r] = val;
>
> Would this overflow const_reg_vals[] when r is BPF_REG_10?
> The array has 10 entries but the loop goes up to 10 inclusive.

Good point.
Changed it as:
-               for (r = BPF_REG_0; r < MAX_BPF_REG; r++) {
+               for (r = BPF_REG_0; r < sizeof(aux->const_reg_vals); r++) {

> Since compute_const_regs() runs before the main verifier pass,
> register numbers in instructions haven't been validated yet.  A
> crafted program with dst_reg = BPF_REG_FP in an ALU instruction
> would cause the analysis to track R10 as a constant, then
> write one element past the array into the next instruction's
> bpf_insn_aux_data.
>
> Similarly, in const_reg_xfer():
>
> > +     struct const_arg_info *dst = &ci_out[insn->dst_reg];
> > +     struct const_arg_info *src = &ci_out[insn->src_reg];
>
> ci_out is a stack-local array of MAX_BPF_REG (11) elements, but
> dst_reg/src_reg are 4-bit fields that can hold values 0-15.
> Could instructions with register values above 10 cause an
> out-of-bounds access on the stack before the verifier rejects them?

nope. because earlier pass validated reg range.

> [ ... ]
>
> > +int prune_dead_branches(struct bpf_verifier_env *env)
> > +{
>
> [ ... ]
>
> > +             if (BPF_SRC(insn->code) == BPF_K) {
> > +                     src_val = (u32)insn->imm;
>
> For 64-bit JMP instructions (BPF_JMP class) with BPF_K source, the
> BPF interpreter sign-extends the 32-bit immediate to 64 bits:
>
> kernel/bpf/core.c, COND_JMP macro:
>     JMP_##OPCODE##_K:
>         if ((SIGN##64) DST CMP_OP (SIGN##64) IMM) {
>
> where IMM is insn->imm (s32), so (u64) IMM and (s64) IMM both
> sign-extend.
>
> Here the cast (u32)insn->imm zero-extends instead.  For negative
> immediates these produce different 64-bit values.  For example,
> with imm = -1:
>
>     (u32)(-1) = 0x00000000FFFFFFFF  (what prune_dead_branches uses)
>     (s64)(s32)(-1) = 0xFFFFFFFFFFFFFFFF  (what the interpreter uses)
>
> A concrete case: r1 = 0, then "if r1 s> -1 goto target":
>
>     interpreter: (s64)0 > (s64)(-1) = true, branch taken
>     prune_dead_branches: (s64)0 > (s64)0xFFFFFFFF = false, not taken
>
> The branch would be incorrectly rewritten to fall-through, and the
> jump target becomes dead code.  This also affects unsigned comparisons
> when both operands happen to match at 32 bits -- for instance
> JGE with dst_val = 0xFFFFFFFF and imm = -1:
>
>     interpreter: 0xFFFFFFFF >= 0xFFFFFFFFFFFFFFFF = false
>     prune: 0xFFFFFFFF >= 0xFFFFFFFF = true
>
> Should this be sign-extended to match the interpreter, something like
> src_val = insn->imm (relying on the implicit s32 to u64 conversion)?
> The JMP32 path already handles this correctly via the subsequent
> (s32) cast.

Agree. Fixed like this:
-                       src_val = (u32)insn->imm;
+                       src_val = insn->imm;

> > +             } else {
> > +                     if (!(aux->const_reg_mask & BIT(insn->src_reg)))
> > +                             continue;
> > +                     src_val = aux->const_reg_vals[insn->src_reg];

Note that this part is fine, since we did:
                                if (val != (u32)val)
                                        break;
                                mask |= BIT(r);
                                aux->const_reg_vals[r] = val;

Re: [PATCH bpf-next 4/6] bpf: Add compute_const_regs() and prune_dead_branches() passes

[Eduard Zingerman]

On Tue, 2026-03-31 at 19:16 -0700, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> Add two passes before the main verifier pass:
> 
> compute_const_regs() is a forward dataflow analysis that tracks
> register values in R0-R9 across the program using fixed-point
> iteration in reverse postorder. Each register is tracked with
> a six-state lattice:
> 
>   UNVISITED -> CONST(val) / MAP_PTR(map_index) /
>                MAP_VALUE(map_index, offset) / SUBPROG(num) -> UNKNOWN
> 
> At merge points, if two paths produce the same state and value for
> a register, it stays; otherwise it becomes UNKNOWN.
> 
> The analysis handles:
>  - MOV, ADD, SUB, AND with immediate or register operands
>  - LD_IMM64 for plain constants, map FDs, map values, and subprogs
>  - LDX from read-only maps: constant-folds the load by reading the
>    map value directly via bpf_map_direct_read()
> 
> Results that fit in 32 bits are stored per-instruction in
> insn_aux_data and bitmasks.
> 
> prune_dead_branches() uses the computed constants to evaluate
> conditional branches. When both operands of a conditional jump are
> known constants, the branch outcome is determined statically and the
> instruction is rewritten to an unconditional jump.
> The CFG postorder is then recomputed to reflect new control flow.
> This eliminates dead edges so that subsequent liveness analysis
> doesn't propagate through dead code.
> 
> Also add runtime sanity check to validate that precomputed
> constants match the verifier's tracked state.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---

Besides issues found by bot this patch lgtm.

[...]

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 4f492eaad5c2..0d797de30a3a 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h

[...]

> @@ -1086,6 +1102,13 @@ struct bpf_iarray *bpf_insn_successors(struct bpf_verifier_env *env, u32 idx);
>  void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask);
>  bool bpf_calls_callback(struct bpf_verifier_env *env, int insn_idx);
>  
> +int find_subprog(struct bpf_verifier_env *env, int off);
> +int compute_const_regs(struct bpf_verifier_env *env);
> +int prune_dead_branches(struct bpf_verifier_env *env);
> +int compute_postorder(struct bpf_verifier_env *env);
> +bool insn_is_cond_jump(u8 code);
> +bool is_may_goto_insn(struct bpf_insn *insn);
> +

Q: What is the policy regarding naming exported functions?
   So far I always used "bpf_..." prefix assuming that this
   is a requirement, was I wrong?

>  int bpf_stack_liveness_init(struct bpf_verifier_env *env);
>  void bpf_stack_liveness_free(struct bpf_verifier_env *env);
>  int bpf_update_live_stack(struct bpf_verifier_env *env);

[...]

> diff --git a/kernel/bpf/const_fold.c b/kernel/bpf/const_fold.c
> new file mode 100644
> index 000000000000..9e5abc6ab46a
> --- /dev/null
> +++ b/kernel/bpf/const_fold.c

[...]

> +/* Transfer function: compute output register state from instruction. */
> +static void const_reg_xfer(struct bpf_verifier_env *env, struct const_arg_info *ci_out,
> +			   struct bpf_insn *insn, struct bpf_insn *insns, int idx)
> +{
> +	struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 };
> +	struct const_arg_info *dst = &ci_out[insn->dst_reg];
> +	struct const_arg_info *src = &ci_out[insn->src_reg];
> +	u8 class = BPF_CLASS(insn->code);
> +	u8 opcode = BPF_OP(insn->code) | BPF_SRC(insn->code);
> +	int r;
> +
> +	switch (class) {
> +	case BPF_ALU:
> +	case BPF_ALU64:
> +		switch (opcode) {
> +		case BPF_MOV | BPF_K:
> +			dst->state = CONST_ARG_CONST;
> +			dst->val = (s64)insn->imm;
> +			break;
> +		case BPF_MOV | BPF_X:
> +			*dst = *src;
> +			if (!insn->off)
> +				break;
> +			if (!ci_is_const(dst)) {
> +				*dst = unknown;
> +				break;
> +			}
> +			switch (insn->off) {
> +			case 8:  dst->val = (s8)dst->val; break;
> +			case 16: dst->val = (s16)dst->val; break;
> +			case 32: dst->val = (s32)dst->val; break;
> +			default: *dst = unknown; break;
> +			}
> +			break;
> +		case BPF_ADD | BPF_K:
> +			if (!ci_is_const(dst) && !ci_is_map_value(dst)) {
> +				*dst = unknown;
> +				break;
> +			}
> +			dst->val += insn->imm;
> +			break;
> +		case BPF_SUB | BPF_K:
> +			if (!ci_is_const(dst) && !ci_is_map_value(dst)) {
> +				*dst = unknown;
> +				break;
> +			}
> +			dst->val -= insn->imm;
> +			break;
> +		case BPF_AND | BPF_K:
> +			if (!ci_is_const(dst)) {
> +				if (!insn->imm) {
> +					dst->state = CONST_ARG_CONST;
> +					dst->val = 0;
> +				} else {
> +					*dst = unknown;
> +				}
> +				break;
> +			}
> +			dst->val &= (s64)insn->imm;
> +			break;
> +		case BPF_AND | BPF_X:
> +			if (ci_is_const(dst) && dst->val == 0)
> +				break; /* 0 & x == 0 */
> +			if (ci_is_const(src) && src->val == 0) {
> +				dst->state = CONST_ARG_CONST;
> +				dst->val = 0;
> +				break;
> +			}
> +			if (!ci_is_const(dst) || !ci_is_const(src)) {
> +				*dst = unknown;
> +				break;
> +			}
> +			dst->val &= src->val;
> +			break;

Just curious, why does this function deal with `0 & reg` cases,
but not the e.g. `0 | reg` cases? Was it something that came up
during testing the static analysis?

> +		default:
> +			*dst = unknown;
> +			break;
> +		}
> +		if (class == BPF_ALU) {
> +			if (ci_is_const(dst))
> +				dst->val = (u32)dst->val;
> +			else if (!ci_is_unknown(dst))
> +				*dst = unknown;
> +		}
> +		break;
> +	case BPF_LD:
> +		if (BPF_MODE(insn->code) != BPF_IMM || BPF_SIZE(insn->code) != BPF_DW)

Should this reset r0-r5 in case of opcode is  BPF_LD|BPF_ABS or BPF_LD|BPF_IND?

> +			break;
> +		if (insn->src_reg == BPF_PSEUDO_FUNC) {
> +			int subprog = find_subprog(env, idx + insn->imm + 1);
> +
> +			if (subprog >= 0) {
> +				dst->state = CONST_ARG_SUBPROG;
> +				dst->val = subprog;
> +			} else {
> +				*dst = unknown;
> +			}
> +		} else if (insn->src_reg == BPF_PSEUDO_MAP_VALUE ||
> +			   insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE) {
> +			dst->state = CONST_ARG_MAP_VALUE;
> +			dst->map_index = env->insn_aux_data[idx].map_index;
> +			dst->val = env->insn_aux_data[idx].map_off;
> +		} else if (insn->src_reg == BPF_PSEUDO_MAP_FD ||
> +			   insn->src_reg == BPF_PSEUDO_MAP_IDX) {
> +			dst->state = CONST_ARG_MAP_PTR;
> +			dst->map_index = env->insn_aux_data[idx].map_index;
> +		} else if (insn->src_reg == 0) {
> +			dst->state = CONST_ARG_CONST;
> +			dst->val = (u64)(u32)insn->imm | ((u64)(u32)insns[idx + 1].imm << 32);
> +		} else {
> +			*dst = unknown;
> +		}
> +		break;
> +	case BPF_LDX:
> +		if (!ci_is_map_value(src)) {
> +			*dst = unknown;
> +			break;
> +		}
> +		struct bpf_map *map = env->used_maps[src->map_index];
> +		int size = bpf_size_to_bytes(BPF_SIZE(insn->code));
> +		bool is_ldsx = BPF_MODE(insn->code) == BPF_MEMSX;
> +		int off = src->val + insn->off;
> +		u64 val = 0;
> +
> +		if (!bpf_map_is_rdonly(map) || !map->ops->map_direct_value_addr ||
> +		    bpf_map_direct_read(map, off, size, &val, is_ldsx)) {

Nit: Similar sequence in verifier.c also checks for map->map_type != BPF_MAP_TYPE_INSN_ARRAY.
     Maybe move this to a helper function?

> +			*dst = unknown;
> +			break;
> +		}
> +		dst->state = CONST_ARG_CONST;
> +		dst->val = val;
> +		break;
> +	case BPF_JMP:
> +		if (opcode != BPF_CALL)
> +			break;
> +		for (r = BPF_REG_0; r <= BPF_REG_5; r++)
> +			ci_out[r] = unknown;
> +		break;
> +	case BPF_STX:
> +		if (BPF_MODE(insn->code) != BPF_ATOMIC)
> +			break;
> +		if (insn->imm == BPF_CMPXCHG)
> +			ci_out[BPF_REG_0] = unknown;
> +		else if (insn->imm == BPF_LOAD_ACQ)
> +			*dst = unknown;
> +		else if (insn->imm & BPF_FETCH)
> +			*src = unknown;
> +		break;
> +	}
> +}

[...]

> +static bool eval_const_branch(u8 opcode, u64 dst_val, u64 src_val)
> +{
> +	switch (BPF_OP(opcode)) {
> +	case BPF_JEQ:	return dst_val == src_val;
> +	case BPF_JNE:	return dst_val != src_val;
> +	case BPF_JGT:	return dst_val > src_val;
> +	case BPF_JGE:	return dst_val >= src_val;
> +	case BPF_JLT:	return dst_val < src_val;
> +	case BPF_JLE:	return dst_val <= src_val;
> +	case BPF_JSGT:	return (s64)dst_val > (s64)src_val;
> +	case BPF_JSGE:	return (s64)dst_val >= (s64)src_val;
> +	case BPF_JSLT:	return (s64)dst_val < (s64)src_val;
> +	case BPF_JSLE:	return (s64)dst_val <= (s64)src_val;
> +	case BPF_JSET:	return dst_val & src_val;
> +	default:	return false;

Do we want to validate that the above are the only opcodes possible,
e.g. in patch #1?

> +	}
> +}
> +
> +/*
> + * Rewrite conditional branches with constant outcomes into unconditional
> + * jumps using register values resolved by compute_const_regs() pass.
> + * This eliminates dead edges from the CFG so that compute_live_registers()
> + * doesn't propagate liveness through dead code.
> + */
> +int prune_dead_branches(struct bpf_verifier_env *env)
> +{
> +	struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;
> +	struct bpf_insn *insns = env->prog->insnsi;
> +	int insn_cnt = env->prog->len;
> +	bool changed = false;
> +	int i;
> +
> +	for (i = 0; i < insn_cnt; i++) {
> +		struct bpf_insn_aux_data *aux = &insn_aux[i];
> +		struct bpf_insn *insn = &insns[i];
> +		u8 class = BPF_CLASS(insn->code);
> +		u64 dst_val, src_val;
> +		bool taken;
> +
> +		if (!insn_is_cond_jump(insn->code))
> +			continue;
> +		if (is_may_goto_insn(insn))
> +			continue;
> +
> +		if (!(aux->const_reg_mask & BIT(insn->dst_reg)))
> +			continue;
> +		dst_val = aux->const_reg_vals[insn->dst_reg];
> +
> +		if (BPF_SRC(insn->code) == BPF_K) {
> +			src_val = (u32)insn->imm;
> +		} else {
> +			if (!(aux->const_reg_mask & BIT(insn->src_reg)))
> +				continue;
> +			src_val = aux->const_reg_vals[insn->src_reg];
> +		}
> +
> +		if (class == BPF_JMP32) {
> +			/*
> +			 * The (s32) cast maps the 32-bit range into two u64 sub-ranges:
> +			 * [0x00000000, 0x7FFFFFFF] -> [0x0000000000000000, 0x000000007FFFFFFF]
> +			 * [0x80000000, 0xFFFFFFFF] -> [0xFFFFFFFF80000000, 0xFFFFFFFFFFFFFFFF]
> +			 * The ordering is preserved within each sub-range, and
> +			 * the second sub-range is above the first as u64.
> +			 */
> +			dst_val = (s32)dst_val;
> +			src_val = (s32)src_val;
> +		}
> +
> +		taken = eval_const_branch(insn->code, dst_val, src_val);
> +		*insn = BPF_JMP_A(taken ? insn->off : 0);
> +		changed = true;
> +	}
> +
> +	if (!changed)
> +		return 0;
> +	/* recompute postorder, since CFG has changed */
> +	kvfree(env->cfg.insn_postorder);
> +	return compute_postorder(env);
> +}
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 432806011d47..493f6acaa386 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -595,7 +595,7 @@ static bool is_async_cb_sleepable(struct bpf_verifier_env *env, struct bpf_insn
>  	return false;
>  }
>  
> -static bool is_may_goto_insn(struct bpf_insn *insn)
> +bool is_may_goto_insn(struct bpf_insn *insn)
>  {
>  	return insn->code == (BPF_JMP | BPF_JCOND) && insn->src_reg == BPF_MAY_GOTO;
>  }
> @@ -3082,7 +3082,7 @@ struct bpf_subprog_info *bpf_find_containing_subprog(struct bpf_verifier_env *en
>  }
>  
>  /* Find subprogram that starts exactly at 'off' */
> -static int find_subprog(struct bpf_verifier_env *env, int off)
> +int find_subprog(struct bpf_verifier_env *env, int off)
>  {
>  	struct bpf_subprog_info *p;
>  
> @@ -7287,7 +7287,7 @@ static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size)
>  	set_sext32_default_val(reg, size);
>  }
>  
> -static bool bpf_map_is_rdonly(const struct bpf_map *map)
> +bool bpf_map_is_rdonly(const struct bpf_map *map)
>  {
>  	/* A map is considered read-only if the following condition are true:
>  	 *
> @@ -7307,8 +7307,8 @@ static bool bpf_map_is_rdonly(const struct bpf_map *map)
>  	       !bpf_map_write_active(map);
>  }
>  
> -static int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val,
> -			       bool is_ldsx)
> +int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val,
> +			bool is_ldsx)
>  {
>  	void *ptr;
>  	u64 addr;
> @@ -19234,7 +19234,7 @@ static int check_cfg(struct bpf_verifier_env *env)
>   * [env->subprog_info[i].postorder_start, env->subprog_info[i+1].postorder_start)
>   * with indices of 'i' instructions in postorder.
>   */
> -static int compute_postorder(struct bpf_verifier_env *env)
> +int compute_postorder(struct bpf_verifier_env *env)
>  {
>  	u32 cur_postorder, i, top, stack_sz, s;
>  	int *stack = NULL, *postorder = NULL, *state = NULL;
> @@ -21538,6 +21538,27 @@ static int do_check(struct bpf_verifier_env *env)
>  		sanitize_mark_insn_seen(env);
>  		prev_insn_idx = env->insn_idx;
>  
> +		/* Sanity check: precomputed constants must match verifier state */
> +		if (!state->speculative && insn_aux->const_reg_mask) {
> +			struct bpf_reg_state *regs = cur_regs(env);
> +			u16 mask = insn_aux->const_reg_mask;
> +
> +			for (int r = 0; r < MAX_BPF_REG; r++) {
> +				u32 cval = insn_aux->const_reg_vals[r];
> +
> +				if (!(mask & BIT(r)))
> +					continue;
> +				if (regs[r].type != SCALAR_VALUE)
> +					continue;
> +				if (!tnum_is_const(regs[r].var_off))
> +					continue;
> +				if (verifier_bug_if((u32)regs[r].var_off.value != cval,
> +						    env, "const R%d: %u != %llu",
> +						    r, cval, regs[r].var_off.value))
> +					return -EFAULT;
> +			}
> +		}
> +
>  		/* Reduce verification complexity by stopping speculative path
>  		 * verification when a nospec is encountered.
>  		 */
> @@ -22527,7 +22548,7 @@ static void sanitize_dead_code(struct bpf_verifier_env *env)
>  	}
>  }
>  
> -static bool insn_is_cond_jump(u8 code)
> +bool insn_is_cond_jump(u8 code)
>  {
>  	u8 op;
>  
> @@ -26353,6 +26374,14 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
>  	if (ret)
>  		goto skip_full_check;
>  
> +	ret = compute_const_regs(env);
> +	if (ret < 0)
> +		goto skip_full_check;
> +
> +	ret = prune_dead_branches(env);
> +	if (ret < 0)
> +		goto skip_full_check;
> +
>  	ret = sort_subprogs_topo(env);
>  	if (ret < 0)
>  		goto skip_full_check;
> diff --git a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
> index 58c7704d61cd..0e907cad5902 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
> @@ -592,10 +592,10 @@ __naked void check_ids_in_regsafe_2(void)
>   */
>  SEC("socket")
>  __success __log_level(2)
> -__msg("11: (1d) if r3 == r4 goto pc+0")
> +__msg("14: (1d) if r3 == r4 goto pc+0")
>  __msg("frame 0: propagating r3,r4")
> -__msg("11: safe")
> -__msg("processed 15 insns")
> +__msg("14: safe")
> +__msg("processed 18 insns")
>  __flag(BPF_F_TEST_STATE_FREQ)
>  __naked void no_scalar_id_for_const(void)
>  {
> @@ -606,13 +606,16 @@ __naked void no_scalar_id_for_const(void)
>  	/* possibly generate same scalar ids for r3 and r4 */
>  	"r1 = 0;"
>  	"r1 = r1;"
> +	"r1 |= 0;" /* prevent prune_dead_branches from folding the branch */
>  	"r3 = r1;"
>  	"r4 = r1;"
>  	"goto l1_%=;"
>  "l0_%=:"
>  	/* possibly generate different scalar ids for r3 and r4 */
>  	"r1 = 0;"
> +	"r1 |= 0;"
>  	"r2 = 0;"
> +	"r2 |= 0;"
>  	"r3 = r1;"
>  	"r4 = r2;"
>  "l1_%=:"
> @@ -628,10 +631,10 @@ __naked void no_scalar_id_for_const(void)
>  /* Same as no_scalar_id_for_const() but for 32-bit values */
>  SEC("socket")
>  __success __log_level(2)
> -__msg("11: (1e) if w3 == w4 goto pc+0")
> +__msg("14: (1e) if w3 == w4 goto pc+0")
>  __msg("frame 0: propagating r3,r4")
> -__msg("11: safe")
> -__msg("processed 15 insns")
> +__msg("14: safe")
> +__msg("processed 18 insns")
>  __flag(BPF_F_TEST_STATE_FREQ)
>  __naked void no_scalar_id_for_const32(void)
>  {
> @@ -642,17 +645,20 @@ __naked void no_scalar_id_for_const32(void)
>  	/* possibly generate same scalar ids for r3 and r4 */
>  	"w1 = 0;"
>  	"w1 = w1;"
> +	"w1 |= 0;" /* prevent prune_dead_branches from folding the branch */
>  	"w3 = w1;"
>  	"w4 = w1;"
>  	"goto l1_%=;"
>  "l0_%=:"
>  	/* possibly generate different scalar ids for r3 and r4 */
>  	"w1 = 0;"
> +	"w1 |= 0;"
>  	"w2 = 0;"
> +	"w2 |= 0;"
>  	"w3 = w1;"
>  	"w4 = w2;"
>  "l1_%=:"
> -	/* predictable jump, marks r1 and r2 precise */
> +	/* predictable jump, marks r3 and r4 precise */
>  	"if w3 == w4 goto +0;"
>  	"r0 = 0;"
>  	"exit;"

Re: [PATCH bpf-next 4/6] bpf: Add compute_const_regs() and prune_dead_branches() passes

[Alexei Starovoitov]

On Wed, Apr 1, 2026 at 2:07 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2026-03-31 at 19:16 -0700, Alexei Starovoitov wrote:
> > From: Alexei Starovoitov <ast@kernel.org>
> >
> > Add two passes before the main verifier pass:
> >
> > compute_const_regs() is a forward dataflow analysis that tracks
> > register values in R0-R9 across the program using fixed-point
> > iteration in reverse postorder. Each register is tracked with
> > a six-state lattice:
> >
> >   UNVISITED -> CONST(val) / MAP_PTR(map_index) /
> >                MAP_VALUE(map_index, offset) / SUBPROG(num) -> UNKNOWN
> >
> > At merge points, if two paths produce the same state and value for
> > a register, it stays; otherwise it becomes UNKNOWN.
> >
> > The analysis handles:
> >  - MOV, ADD, SUB, AND with immediate or register operands
> >  - LD_IMM64 for plain constants, map FDs, map values, and subprogs
> >  - LDX from read-only maps: constant-folds the load by reading the
> >    map value directly via bpf_map_direct_read()
> >
> > Results that fit in 32 bits are stored per-instruction in
> > insn_aux_data and bitmasks.
> >
> > prune_dead_branches() uses the computed constants to evaluate
> > conditional branches. When both operands of a conditional jump are
> > known constants, the branch outcome is determined statically and the
> > instruction is rewritten to an unconditional jump.
> > The CFG postorder is then recomputed to reflect new control flow.
> > This eliminates dead edges so that subsequent liveness analysis
> > doesn't propagate through dead code.
> >
> > Also add runtime sanity check to validate that precomputed
> > constants match the verifier's tracked state.
> >
> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > ---
>
> Besides issues found by bot this patch lgtm.
>
> [...]
>
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index 4f492eaad5c2..0d797de30a3a 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
>
> [...]
>
> > @@ -1086,6 +1102,13 @@ struct bpf_iarray *bpf_insn_successors(struct bpf_verifier_env *env, u32 idx);
> >  void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask);
> >  bool bpf_calls_callback(struct bpf_verifier_env *env, int insn_idx);
> >
> > +int find_subprog(struct bpf_verifier_env *env, int off);
> > +int compute_const_regs(struct bpf_verifier_env *env);
> > +int prune_dead_branches(struct bpf_verifier_env *env);
> > +int compute_postorder(struct bpf_verifier_env *env);
> > +bool insn_is_cond_jump(u8 code);
> > +bool is_may_goto_insn(struct bpf_insn *insn);
> > +
>
> Q: What is the policy regarding naming exported functions?
>    So far I always used "bpf_..." prefix assuming that this
>    is a requirement, was I wrong?

It's nice to have but not mandatory.
imo the names are unique enough, so unlikely to clash.

> >  int bpf_stack_liveness_init(struct bpf_verifier_env *env);
> >  void bpf_stack_liveness_free(struct bpf_verifier_env *env);
> >  int bpf_update_live_stack(struct bpf_verifier_env *env);
>
> [...]
>
> > diff --git a/kernel/bpf/const_fold.c b/kernel/bpf/const_fold.c
> > new file mode 100644
> > index 000000000000..9e5abc6ab46a
> > --- /dev/null
> > +++ b/kernel/bpf/const_fold.c
>
> [...]
>
> > +/* Transfer function: compute output register state from instruction. */
> > +static void const_reg_xfer(struct bpf_verifier_env *env, struct const_arg_info *ci_out,
> > +                        struct bpf_insn *insn, struct bpf_insn *insns, int idx)
> > +{
> > +     struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 };
> > +     struct const_arg_info *dst = &ci_out[insn->dst_reg];
> > +     struct const_arg_info *src = &ci_out[insn->src_reg];
> > +     u8 class = BPF_CLASS(insn->code);
> > +     u8 opcode = BPF_OP(insn->code) | BPF_SRC(insn->code);
> > +     int r;
> > +
> > +     switch (class) {
> > +     case BPF_ALU:
> > +     case BPF_ALU64:
> > +             switch (opcode) {
> > +             case BPF_MOV | BPF_K:
> > +                     dst->state = CONST_ARG_CONST;
> > +                     dst->val = (s64)insn->imm;
> > +                     break;
> > +             case BPF_MOV | BPF_X:
> > +                     *dst = *src;
> > +                     if (!insn->off)
> > +                             break;
> > +                     if (!ci_is_const(dst)) {
> > +                             *dst = unknown;
> > +                             break;
> > +                     }
> > +                     switch (insn->off) {
> > +                     case 8:  dst->val = (s8)dst->val; break;
> > +                     case 16: dst->val = (s16)dst->val; break;
> > +                     case 32: dst->val = (s32)dst->val; break;
> > +                     default: *dst = unknown; break;
> > +                     }
> > +                     break;
> > +             case BPF_ADD | BPF_K:
> > +                     if (!ci_is_const(dst) && !ci_is_map_value(dst)) {
> > +                             *dst = unknown;
> > +                             break;
> > +                     }
> > +                     dst->val += insn->imm;
> > +                     break;
> > +             case BPF_SUB | BPF_K:
> > +                     if (!ci_is_const(dst) && !ci_is_map_value(dst)) {
> > +                             *dst = unknown;
> > +                             break;
> > +                     }
> > +                     dst->val -= insn->imm;
> > +                     break;
> > +             case BPF_AND | BPF_K:
> > +                     if (!ci_is_const(dst)) {
> > +                             if (!insn->imm) {
> > +                                     dst->state = CONST_ARG_CONST;
> > +                                     dst->val = 0;
> > +                             } else {
> > +                                     *dst = unknown;
> > +                             }
> > +                             break;
> > +                     }
> > +                     dst->val &= (s64)insn->imm;
> > +                     break;
> > +             case BPF_AND | BPF_X:
> > +                     if (ci_is_const(dst) && dst->val == 0)
> > +                             break; /* 0 & x == 0 */
> > +                     if (ci_is_const(src) && src->val == 0) {
> > +                             dst->state = CONST_ARG_CONST;
> > +                             dst->val = 0;
> > +                             break;
> > +                     }
> > +                     if (!ci_is_const(dst) || !ci_is_const(src)) {
> > +                             *dst = unknown;
> > +                             break;
> > +                     }
> > +                     dst->val &= src->val;
> > +                     break;
>
> Just curious, why does this function deal with `0 & reg` cases,
> but not the e.g. `0 | reg` cases? Was it something that came up
> during testing the static analysis?

right. rx &= ry is real sched-ext code
where 0 in rx came from rdonly map.

> > +             default:
> > +                     *dst = unknown;
> > +                     break;
> > +             }
> > +             if (class == BPF_ALU) {
> > +                     if (ci_is_const(dst))
> > +                             dst->val = (u32)dst->val;
> > +                     else if (!ci_is_unknown(dst))
> > +                             *dst = unknown;
> > +             }
> > +             break;
> > +     case BPF_LD:
> > +             if (BPF_MODE(insn->code) != BPF_IMM || BPF_SIZE(insn->code) != BPF_DW)
>
> Should this reset r0-r5 in case of opcode is  BPF_LD|BPF_ABS or BPF_LD|BPF_IND?

great catch!
codex and claude never thought of that.

>
> > +                     break;
> > +             if (insn->src_reg == BPF_PSEUDO_FUNC) {
> > +                     int subprog = find_subprog(env, idx + insn->imm + 1);
> > +
> > +                     if (subprog >= 0) {
> > +                             dst->state = CONST_ARG_SUBPROG;
> > +                             dst->val = subprog;
> > +                     } else {
> > +                             *dst = unknown;
> > +                     }
> > +             } else if (insn->src_reg == BPF_PSEUDO_MAP_VALUE ||
> > +                        insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE) {
> > +                     dst->state = CONST_ARG_MAP_VALUE;
> > +                     dst->map_index = env->insn_aux_data[idx].map_index;
> > +                     dst->val = env->insn_aux_data[idx].map_off;
> > +             } else if (insn->src_reg == BPF_PSEUDO_MAP_FD ||
> > +                        insn->src_reg == BPF_PSEUDO_MAP_IDX) {
> > +                     dst->state = CONST_ARG_MAP_PTR;
> > +                     dst->map_index = env->insn_aux_data[idx].map_index;
> > +             } else if (insn->src_reg == 0) {
> > +                     dst->state = CONST_ARG_CONST;
> > +                     dst->val = (u64)(u32)insn->imm | ((u64)(u32)insns[idx + 1].imm << 32);
> > +             } else {
> > +                     *dst = unknown;
> > +             }
> > +             break;
> > +     case BPF_LDX:
> > +             if (!ci_is_map_value(src)) {
> > +                     *dst = unknown;
> > +                     break;
> > +             }
> > +             struct bpf_map *map = env->used_maps[src->map_index];
> > +             int size = bpf_size_to_bytes(BPF_SIZE(insn->code));
> > +             bool is_ldsx = BPF_MODE(insn->code) == BPF_MEMSX;
> > +             int off = src->val + insn->off;
> > +             u64 val = 0;
> > +
> > +             if (!bpf_map_is_rdonly(map) || !map->ops->map_direct_value_addr ||
> > +                 bpf_map_direct_read(map, off, size, &val, is_ldsx)) {
>
> Nit: Similar sequence in verifier.c also checks for map->map_type != BPF_MAP_TYPE_INSN_ARRAY.

ack

>      Maybe move this to a helper function?

it's not exactly the same.
maybe later.

> > +                     *dst = unknown;
> > +                     break;
> > +             }
> > +             dst->state = CONST_ARG_CONST;
> > +             dst->val = val;
> > +             break;
> > +     case BPF_JMP:
> > +             if (opcode != BPF_CALL)
> > +                     break;
> > +             for (r = BPF_REG_0; r <= BPF_REG_5; r++)
> > +                     ci_out[r] = unknown;
> > +             break;
> > +     case BPF_STX:
> > +             if (BPF_MODE(insn->code) != BPF_ATOMIC)
> > +                     break;
> > +             if (insn->imm == BPF_CMPXCHG)
> > +                     ci_out[BPF_REG_0] = unknown;
> > +             else if (insn->imm == BPF_LOAD_ACQ)
> > +                     *dst = unknown;
> > +             else if (insn->imm & BPF_FETCH)
> > +                     *src = unknown;
> > +             break;
> > +     }
> > +}
>
> [...]
>
> > +static bool eval_const_branch(u8 opcode, u64 dst_val, u64 src_val)
> > +{
> > +     switch (BPF_OP(opcode)) {
> > +     case BPF_JEQ:   return dst_val == src_val;
> > +     case BPF_JNE:   return dst_val != src_val;
> > +     case BPF_JGT:   return dst_val > src_val;
> > +     case BPF_JGE:   return dst_val >= src_val;
> > +     case BPF_JLT:   return dst_val < src_val;
> > +     case BPF_JLE:   return dst_val <= src_val;
> > +     case BPF_JSGT:  return (s64)dst_val > (s64)src_val;
> > +     case BPF_JSGE:  return (s64)dst_val >= (s64)src_val;
> > +     case BPF_JSLT:  return (s64)dst_val < (s64)src_val;
> > +     case BPF_JSLE:  return (s64)dst_val <= (s64)src_val;
> > +     case BPF_JSET:  return dst_val & src_val;
> > +     default:        return false;
>
> Do we want to validate that the above are the only opcodes possible,
> e.g. in patch #1?

I felt it's too much defensive programming,
but, on a second thought..
will return -1 and deal with it in the caller.

Re: [PATCH bpf-next 4/6] bpf: Add compute_const_regs() and prune_dead_branches() passes

[Alexei Starovoitov]

On Wed, Apr 1, 2026 at 3:32 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Wed, Apr 1, 2026 at 2:07 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Tue, 2026-03-31 at 19:16 -0700, Alexei Starovoitov wrote:
> > > From: Alexei Starovoitov <ast@kernel.org>
> > >
> > > Add two passes before the main verifier pass:
> > >
> > > compute_const_regs() is a forward dataflow analysis that tracks
> > > register values in R0-R9 across the program using fixed-point
> > > iteration in reverse postorder. Each register is tracked with
> > > a six-state lattice:
> > >
> > >   UNVISITED -> CONST(val) / MAP_PTR(map_index) /
> > >                MAP_VALUE(map_index, offset) / SUBPROG(num) -> UNKNOWN
> > >
> > > At merge points, if two paths produce the same state and value for
> > > a register, it stays; otherwise it becomes UNKNOWN.
> > >
> > > The analysis handles:
> > >  - MOV, ADD, SUB, AND with immediate or register operands
> > >  - LD_IMM64 for plain constants, map FDs, map values, and subprogs
> > >  - LDX from read-only maps: constant-folds the load by reading the
> > >    map value directly via bpf_map_direct_read()
> > >
> > > Results that fit in 32 bits are stored per-instruction in
> > > insn_aux_data and bitmasks.
> > >
> > > prune_dead_branches() uses the computed constants to evaluate
> > > conditional branches. When both operands of a conditional jump are
> > > known constants, the branch outcome is determined statically and the
> > > instruction is rewritten to an unconditional jump.
> > > The CFG postorder is then recomputed to reflect new control flow.
> > > This eliminates dead edges so that subsequent liveness analysis
> > > doesn't propagate through dead code.
> > >
> > > Also add runtime sanity check to validate that precomputed
> > > constants match the verifier's tracked state.
> > >
> > > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > > ---
> >
> > Besides issues found by bot this patch lgtm.
> >
> > [...]
> >
> > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > > index 4f492eaad5c2..0d797de30a3a 100644
> > > --- a/include/linux/bpf_verifier.h
> > > +++ b/include/linux/bpf_verifier.h
> >
> > [...]
> >
> > > @@ -1086,6 +1102,13 @@ struct bpf_iarray *bpf_insn_successors(struct bpf_verifier_env *env, u32 idx);
> > >  void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask);
> > >  bool bpf_calls_callback(struct bpf_verifier_env *env, int insn_idx);
> > >
> > > +int find_subprog(struct bpf_verifier_env *env, int off);
> > > +int compute_const_regs(struct bpf_verifier_env *env);
> > > +int prune_dead_branches(struct bpf_verifier_env *env);
> > > +int compute_postorder(struct bpf_verifier_env *env);
> > > +bool insn_is_cond_jump(u8 code);
> > > +bool is_may_goto_insn(struct bpf_insn *insn);
> > > +
> >
> > Q: What is the policy regarding naming exported functions?
> >    So far I always used "bpf_..." prefix assuming that this
> >    is a requirement, was I wrong?
>
> It's nice to have but not mandatory.
> imo the names are unique enough, so unlikely to clash.

This one I still think is ok, but the other patch does:

-__printf(2, 3) static void verbose(void *private_data, const char *fmt, ...)
+__printf(2, 3) void verbose(void *private_data, const char *fmt, ...)

and this is definitely too much.

Re: [PATCH bpf-next 4/6] bpf: Add compute_const_regs() and prune_dead_branches() passes

[Eduard Zingerman]

On Wed, 2026-04-01 at 19:45 -0700, Alexei Starovoitov wrote:

[...]

> > > Q: What is the policy regarding naming exported functions?
> > >    So far I always used "bpf_..." prefix assuming that this
> > >    is a requirement, was I wrong?
> > 
> > It's nice to have but not mandatory.
> > imo the names are unique enough, so unlikely to clash.
> 
> This one I still think is ok, but the other patch does:
> 
> -__printf(2, 3) static void verbose(void *private_data, const char *fmt, ...)
> +__printf(2, 3) void verbose(void *private_data, const char *fmt, ...)
> 
> and this is definitely too much.

Let's do a bulk rename to bpf_verbose() it is super useful when moving
some parts of the verifier outside of the verifier.c

Re: [PATCH bpf-next 4/6] bpf: Add compute_const_regs() and prune_dead_branches() passes

[Alexei Starovoitov]

On Wed, Apr 1, 2026 at 7:49 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2026-04-01 at 19:45 -0700, Alexei Starovoitov wrote:
>
> [...]
>
> > > > Q: What is the policy regarding naming exported functions?
> > > >    So far I always used "bpf_..." prefix assuming that this
> > > >    is a requirement, was I wrong?
> > >
> > > It's nice to have but not mandatory.
> > > imo the names are unique enough, so unlikely to clash.
> >
> > This one I still think is ok, but the other patch does:
> >
> > -__printf(2, 3) static void verbose(void *private_data, const char *fmt, ...)
> > +__printf(2, 3) void verbose(void *private_data, const char *fmt, ...)
> >
> > and this is definitely too much.
>
> Let's do a bulk rename to bpf_verbose() it is super useful when moving
> some parts of the verifier outside of the verifier.c

no :)
I simply added:
#define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)

[PATCH bpf-next 5/6] bpf: Move verifier helpers to header

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Move several helpers to header as preparation for
the subsequent stack liveness patches.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h | 30 ++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c        | 32 ++++----------------------------
 2 files changed, 34 insertions(+), 28 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 0d797de30a3a..3fccf61afbc8 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -877,6 +877,31 @@ static inline struct bpf_subprog_info *subprog_info(struct bpf_verifier_env *env
 	return &env->subprog_info[subprog];
 }
 
+struct call_summary {
+	u8 num_params;
+	bool is_void;
+	bool fastcall;
+};
+
+static inline bool bpf_helper_call(const struct bpf_insn *insn)
+{
+	return insn->code == (BPF_JMP | BPF_CALL) &&
+	       insn->src_reg == 0;
+}
+
+static inline bool bpf_pseudo_call(const struct bpf_insn *insn)
+{
+	return insn->code == (BPF_JMP | BPF_CALL) &&
+	       insn->src_reg == BPF_PSEUDO_CALL;
+}
+
+static inline bool bpf_pseudo_kfunc_call(const struct bpf_insn *insn)
+{
+	return insn->code == (BPF_JMP | BPF_CALL) &&
+	       insn->src_reg == BPF_PSEUDO_KFUNC_CALL;
+}
+
+__printf(2, 3) void verbose(void *private_data, const char *fmt, ...);
 __printf(2, 0) void bpf_verifier_vlog(struct bpf_verifier_log *log,
 				      const char *fmt, va_list args);
 __printf(2, 3) void bpf_verifier_log_write(struct bpf_verifier_env *env,
@@ -1109,6 +1134,11 @@ int compute_postorder(struct bpf_verifier_env *env);
 bool insn_is_cond_jump(u8 code);
 bool is_may_goto_insn(struct bpf_insn *insn);
 
+int find_subprog(struct bpf_verifier_env *env, int off);
+void verbose_insn(struct bpf_verifier_env *env, struct bpf_insn *insn);
+bool get_call_summary(struct bpf_verifier_env *env, struct bpf_insn *call,
+		      struct call_summary *cs);
+
 int bpf_stack_liveness_init(struct bpf_verifier_env *env);
 void bpf_stack_liveness_free(struct bpf_verifier_env *env);
 int bpf_update_live_stack(struct bpf_verifier_env *env);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 493f6acaa386..88285fae21fa 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -256,24 +256,6 @@ static void bpf_map_key_store(struct bpf_insn_aux_data *aux, u64 state)
 			     (poisoned ? BPF_MAP_KEY_POISON : 0ULL);
 }
 
-static bool bpf_helper_call(const struct bpf_insn *insn)
-{
-	return insn->code == (BPF_JMP | BPF_CALL) &&
-	       insn->src_reg == 0;
-}
-
-static bool bpf_pseudo_call(const struct bpf_insn *insn)
-{
-	return insn->code == (BPF_JMP | BPF_CALL) &&
-	       insn->src_reg == BPF_PSEUDO_CALL;
-}
-
-static bool bpf_pseudo_kfunc_call(const struct bpf_insn *insn)
-{
-	return insn->code == (BPF_JMP | BPF_CALL) &&
-	       insn->src_reg == BPF_PSEUDO_KFUNC_CALL;
-}
-
 struct bpf_map_desc {
 	struct bpf_map *ptr;
 	int uid;
@@ -371,7 +353,7 @@ static const char *btf_type_name(const struct btf *btf, u32 id)
 static DEFINE_MUTEX(bpf_verifier_lock);
 static DEFINE_MUTEX(bpf_percpu_ma_lock);
 
-__printf(2, 3) static void verbose(void *private_data, const char *fmt, ...)
+__printf(2, 3) void verbose(void *private_data, const char *fmt, ...)
 {
 	struct bpf_verifier_env *env = private_data;
 	va_list args;
@@ -4260,7 +4242,7 @@ static const char *disasm_kfunc_name(void *data, const struct bpf_insn *insn)
 	return btf_name_by_offset(desc_btf, func->name_off);
 }
 
-static void verbose_insn(struct bpf_verifier_env *env, struct bpf_insn *insn)
+void verbose_insn(struct bpf_verifier_env *env, struct bpf_insn *insn)
 {
 	const struct bpf_insn_cbs cbs = {
 		.cb_call	= disasm_kfunc_name,
@@ -18532,17 +18514,11 @@ static bool verifier_inlines_helper_call(struct bpf_verifier_env *env, s32 imm)
 	}
 }
 
-struct call_summary {
-	u8 num_params;
-	bool is_void;
-	bool fastcall;
-};
-
 /* If @call is a kfunc or helper call, fills @cs and returns true,
  * otherwise returns false.
  */
-static bool get_call_summary(struct bpf_verifier_env *env, struct bpf_insn *call,
-			     struct call_summary *cs)
+bool get_call_summary(struct bpf_verifier_env *env, struct bpf_insn *call,
+		      struct call_summary *cs)
 {
 	struct bpf_kfunc_call_arg_meta meta;
 	const struct bpf_func_proto *fn;
-- 
2.52.0

Re: [PATCH bpf-next 5/6] bpf: Move verifier helpers to header

[Eduard Zingerman]

On Tue, 2026-03-31 at 19:16 -0700, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> Move several helpers to header as preparation for
> the subsequent stack liveness patches.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---

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

[...]

[PATCH bpf-next 6/6] bpf: Add helper and kfunc stack access size resolution

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

The static stack liveness analysis needs to know how many bytes a
helper or kfunc accesses through a stack pointer argument, so it can
precisely mark the affected stack slots as stack 'def' or 'use'.

Add bpf_helper_stack_access_bytes() and bpf_kfunc_stack_access_bytes()
which resolve the access size for a given call argument.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h |   6 ++
 kernel/bpf/verifier.c        | 181 +++++++++++++++++++++++++++++++++++
 2 files changed, 187 insertions(+)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 3fccf61afbc8..c1e8e970f756 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1138,6 +1138,12 @@ int find_subprog(struct bpf_verifier_env *env, int off);
 void verbose_insn(struct bpf_verifier_env *env, struct bpf_insn *insn);
 bool get_call_summary(struct bpf_verifier_env *env, struct bpf_insn *call,
 		      struct call_summary *cs);
+s64 bpf_helper_stack_access_bytes(struct bpf_verifier_env *env,
+				  struct bpf_insn *insn, int arg,
+				  int insn_idx);
+s64 bpf_kfunc_stack_access_bytes(struct bpf_verifier_env *env,
+				 struct bpf_insn *insn, int arg,
+				 int insn_idx);
 
 int bpf_stack_liveness_init(struct bpf_verifier_env *env);
 void bpf_stack_liveness_free(struct bpf_verifier_env *env);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 88285fae21fa..e5424fc0669a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14080,6 +14080,187 @@ static int fetch_kfunc_arg_meta(struct bpf_verifier_env *env,
 	return 0;
 }
 
+/*
+ * Determine how many bytes a helper accesses through a stack pointer at
+ * argument position @arg (0-based, corresponding to R1-R5).
+ *
+ * Returns:
+ *   > 0   known read access size in bytes
+ *     0   doesn't read anything directly
+ * S64_MIN unknown
+ *   < 0   known write access of (-return) bytes
+ */
+s64 bpf_helper_stack_access_bytes(struct bpf_verifier_env *env, struct bpf_insn *insn,
+				  int arg, int insn_idx)
+{
+	struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx];
+	const struct bpf_func_proto *fn;
+	enum bpf_arg_type at;
+	s64 size;
+
+	if (get_helper_proto(env, insn->imm, &fn) < 0)
+		return S64_MIN;
+
+	at = fn->arg_type[arg];
+
+	switch (base_type(at)) {
+	case ARG_PTR_TO_MAP_KEY:
+	case ARG_PTR_TO_MAP_VALUE: {
+		bool is_key = base_type(at) == ARG_PTR_TO_MAP_KEY;
+		u64 val;
+		int i, map_reg;
+
+		for (i = 0; i < arg; i++) {
+			if (base_type(fn->arg_type[i]) == ARG_CONST_MAP_PTR)
+				break;
+		}
+		if (i >= arg)
+			goto scan_all_maps;
+
+		map_reg = BPF_REG_1 + i;
+
+		if (!(aux->const_reg_map_mask & BIT(map_reg)))
+			goto scan_all_maps;
+
+		i = aux->const_reg_vals[map_reg];
+		if (i < env->used_map_cnt) {
+			size = is_key ? env->used_maps[i]->key_size
+				      : env->used_maps[i]->value_size;
+			goto out;
+		}
+scan_all_maps:
+		/*
+		 * Map pointer is not known at this call site (e.g. different
+		 * maps on merged paths).  Conservatively return the largest
+		 * key_size or value_size across all maps used by the program.
+		 */
+		val = 0;
+		for (i = 0; i < env->used_map_cnt; i++) {
+			struct bpf_map *map = env->used_maps[i];
+			u32 sz = is_key ? map->key_size : map->value_size;
+
+			if (sz > val)
+				val = sz;
+			if (map->inner_map_meta) {
+				sz = is_key ? map->inner_map_meta->key_size
+					    : map->inner_map_meta->value_size;
+				if (sz > val)
+					val = sz;
+			}
+		}
+		size = val ?: S64_MIN;
+		goto out;
+	}
+	case ARG_PTR_TO_MEM:
+		if (at & MEM_FIXED_SIZE) {
+			size = fn->arg_size[arg];
+			goto out;
+		}
+		if (arg + 1 < ARRAY_SIZE(fn->arg_type) &&
+		    arg_type_is_mem_size(fn->arg_type[arg + 1])) {
+			int size_reg = BPF_REG_1 + arg + 1;
+
+			if (aux->const_reg_mask & BIT(size_reg)) {
+				size = (s64)aux->const_reg_vals[size_reg];
+				goto out;
+			}
+			/*
+			 * Size arg is const on each path but differs across
+			 * merged paths.  512 is a safe upper bound for reads.
+			 */
+			if (at & MEM_UNINIT)
+				return S64_MIN;
+			return 512;
+		}
+		return S64_MIN;
+	case ARG_PTR_TO_DYNPTR:
+		return BPF_DYNPTR_SIZE;
+	case ARG_PTR_TO_STACK:
+		/*
+		 * Only used by bpf_calls_callback() helpers. The helper itself
+		 * doesn't access stack. The callback subprog does and it's
+		 * analyzed separately.
+		 */
+		return 0;
+	default:
+		return S64_MIN;
+	}
+out:
+	/*
+	 * MEM_UNINIT args are write-only: the helper initializes the
+	 * buffer without reading it.
+	 */
+	if (size > 0 && at & MEM_UNINIT)
+		return -size;
+	return size;
+}
+
+/*
+ * Determine how many bytes a kfunc accesses through a stack pointer at
+ * argument position @arg (0-based, corresponding to R1-R5).
+ *
+ * Returns:
+ *   > 0      known read access size in bytes
+ *     0      doesn't access memory through that argument (ex: not a pointer)
+ *   S64_MIN  unknown
+ *   < 0      known write access of (-return) bytes
+ */
+s64 bpf_kfunc_stack_access_bytes(struct bpf_verifier_env *env, struct bpf_insn *insn,
+				 int arg, int insn_idx)
+{
+	struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx];
+	struct bpf_kfunc_call_arg_meta meta;
+	const struct btf_param *args;
+	const struct btf_type *t, *ref_t;
+	const struct btf *btf;
+	u32 nargs, type_size;
+	s64 size;
+
+	if (fetch_kfunc_arg_meta(env, insn->imm, insn->off, &meta) < 0)
+		return S64_MIN;
+
+	btf = meta.btf;
+	args = btf_params(meta.func_proto);
+	nargs = btf_type_vlen(meta.func_proto);
+	if (arg >= nargs)
+		return 0;
+
+	t = btf_type_skip_modifiers(btf, args[arg].type, NULL);
+	if (!btf_type_is_ptr(t))
+		return 0;
+
+	/* dynptr: fixed 16-byte on-stack representation */
+	if (is_kfunc_arg_dynptr(btf, &args[arg]))
+		return BPF_DYNPTR_SIZE;
+
+	/* ptr + __sz/__szk pair: size is in the next register */
+	if (arg + 1 < nargs &&
+	    (btf_param_match_suffix(btf, &args[arg + 1], "__sz") ||
+	     btf_param_match_suffix(btf, &args[arg + 1], "__szk"))) {
+		int size_reg = BPF_REG_1 + arg + 1;
+
+		if (aux->const_reg_mask & BIT(size_reg)) {
+			size = (s64)aux->const_reg_vals[size_reg];
+			goto out;
+		}
+		return S64_MIN;
+	}
+
+	/* fixed-size pointed-to type: resolve via BTF */
+	ref_t = btf_type_skip_modifiers(btf, t->type, NULL);
+	if (!IS_ERR(btf_resolve_size(btf, ref_t, &type_size))) {
+		size = type_size;
+		goto out;
+	}
+
+	return S64_MIN;
+out:
+	/* KF_ITER_NEW kfuncs initialize the iterator state at arg 0 */
+	if (size > 0 && arg == 0 && meta.kfunc_flags & KF_ITER_NEW)
+		return -size;
+	return size;
+}
+
 /* check special kfuncs and return:
  *  1  - not fall-through to 'else' branch, continue verification
  *  0  - fall-through to 'else' branch
-- 
2.52.0

Re: [PATCH bpf-next 6/6] bpf: Add helper and kfunc stack access size resolution

[Eduard Zingerman]

On Tue, 2026-03-31 at 19:16 -0700, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> The static stack liveness analysis needs to know how many bytes a
> helper or kfunc accesses through a stack pointer argument, so it can
> precisely mark the affected stack slots as stack 'def' or 'use'.
> 
> Add bpf_helper_stack_access_bytes() and bpf_kfunc_stack_access_bytes()
> which resolve the access size for a given call argument.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---

(Please see below, I think a few cases can be slightly improved).

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

[...]

> +s64 bpf_helper_stack_access_bytes(struct bpf_verifier_env *env, struct bpf_insn *insn,
> +				  int arg, int insn_idx)
> +{

[...]

> +	case ARG_PTR_TO_MEM:
> +		if (at & MEM_FIXED_SIZE) {
> +			size = fn->arg_size[arg];
> +			goto out;
> +		}
> +		if (arg + 1 < ARRAY_SIZE(fn->arg_type) &&
> +		    arg_type_is_mem_size(fn->arg_type[arg + 1])) {
> +			int size_reg = BPF_REG_1 + arg + 1;
> +
> +			if (aux->const_reg_mask & BIT(size_reg)) {
> +				size = (s64)aux->const_reg_vals[size_reg];
> +				goto out;

if `at & MEM_WRITE`, I think it would be correct to `return 0;` here.

> +			}
> +			/*
> +			 * Size arg is const on each path but differs across
> +			 * merged paths.  512 is a safe upper bound for reads.
> +			 */
> +			if (at & MEM_UNINIT)
> +				return S64_MIN;
> +			return 512;

Nit: `return MAX_BPF_STACK;`

> +		}
> +		return S64_MIN;
> +	case ARG_PTR_TO_DYNPTR:
> +		return BPF_DYNPTR_SIZE;
> +	case ARG_PTR_TO_STACK:
> +		/*
> +		 * Only used by bpf_calls_callback() helpers. The helper itself
> +		 * doesn't access stack. The callback subprog does and it's
> +		 * analyzed separately.
> +		 */
> +		return 0;
> +	default:
> +		return S64_MIN;
> +	}
> +out:
> +	/*
> +	 * MEM_UNINIT args are write-only: the helper initializes the
> +	 * buffer without reading it.
> +	 */
> +	if (size > 0 && at & MEM_UNINIT)
> +		return -size;

Same question about MEM_WRITE here, might be possible to `return 0` in
some cases.

> +	return size;
> +}

[...]

[syzbot ci] Re: bpf: Prep patches for static stack liveness.

[syzbot ci]

syzbot ci has tested the following series

[v1] bpf: Prep patches for static stack liveness.
https://lore.kernel.org/all/20260401021635.34636-1-alexei.starovoitov@gmail.com
* [PATCH bpf-next 1/6] bpf: Do register range validation early
* [PATCH bpf-next 2/6] bpf: Sort subprogs in topological order after check_cfg()
* [PATCH bpf-next 3/6] selftests/bpf: Add tests for subprog topological ordering
* [PATCH bpf-next 4/6] bpf: Add compute_const_regs() and prune_dead_branches() passes
* [PATCH bpf-next 5/6] bpf: Move verifier helpers to header
* [PATCH bpf-next 6/6] bpf: Add helper and kfunc stack access size resolution

and found the following issue:
UBSAN: array-index-out-of-bounds in do_check

Full report is available here:
https://ci.syzbot.org/series/3bdef783-321d-4d8d-9fbb-fd61f6cd92d5

***

UBSAN: array-index-out-of-bounds in do_check

tree:      bpf-next
URL:       https://kernel.googlesource.com/pub/scm/linux/kernel/git/bpf/bpf-next.git
base:      0eeb0094ba0321f0927806857b5f01c1577bc245
arch:      amd64
compiler:  Debian clang version 21.1.8 (++20251221033036+2078da43e25a-1~exp1~20251221153213.50), Debian LLD 21.1.8
config:    https://ci.syzbot.org/builds/925251e6-c091-44e6-a321-22bd3bffd780/config

can: raw protocol
can: broadcast manager protocol
can: netlink gateway - max_hops=1
can: SAE J1939
can: isotp protocol (max_pdu_size 8300)
Bluetooth: RFCOMM TTY layer initialized
Bluetooth: RFCOMM socket layer initialized
Bluetooth: RFCOMM ver 1.11
Bluetooth: BNEP (Ethernet Emulation) ver 1.3
Bluetooth: BNEP filters: protocol multicast
Bluetooth: BNEP socket layer initialized
Bluetooth: HIDP (Human Interface Emulation) ver 1.2
Bluetooth: HIDP socket layer initialized
NET: Registered PF_RXRPC protocol family
Key type rxrpc registered
Key type rxrpc_s registered
NET: Registered PF_KCM protocol family
lec:lane_module_init: lec.c: initialized
mpoa:atm_mpoa_init: mpc.c: initialized
l2tp_core: L2TP core driver, V2.0
l2tp_ppp: PPPoL2TP kernel driver, V2.0
l2tp_ip: L2TP IP encapsulation support (L2TPv3)
l2tp_netlink: L2TP netlink interface
l2tp_eth: L2TP ethernet pseudowire support (L2TPv3)
l2tp_ip6: L2TP IP encapsulation support for IPv6 (L2TPv3)
NET: Registered PF_PHONET protocol family
8021q: 802.1Q VLAN Support v1.8
sctp: Hash tables configured (bind 32/56)
NET: Registered PF_RDS protocol family
Registered RDS/infiniband transport
Registered RDS/tcp transport
tipc: Activated (version 2.0.0)
NET: Registered PF_TIPC protocol family
tipc: Started in single node mode
smc: adding smcd device lo without pnetid
NET: Registered PF_SMC protocol family
9pnet: Installing 9P2000 support
NET: Registered PF_CAIF protocol family
NET: Registered PF_IEEE802154 protocol family
Key type dns_resolver registered
Key type ceph registered
libceph: loaded (mon/osd proto 15/24)
batman_adv: B.A.T.M.A.N. advanced 2025.5 (compatibility version 15) loaded
openvswitch: Open vSwitch switching datapath
NET: Registered PF_VSOCK protocol family
mpls_gso: MPLS GSO support
IPI shorthand broadcast: enabled
sched_clock: Marking stable (25300061146, 122105816)->(25454415888, -32248926)
registered taskstats version 1
------------[ cut here ]------------
UBSAN: array-index-out-of-bounds in kernel/bpf/verifier.c:21704:16
index 10 is out of range for type 'u32[10]' (aka 'unsigned int[10]')
CPU: 0 UID: 0 PID: 1 Comm: swapper/0 Not tainted syzkaller #0 PREEMPT(full) 
Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS 1.16.2-debian-1.16.2-1 04/01/2014
Call Trace:
 <TASK>
 dump_stack_lvl+0xe8/0x150
 ubsan_epilogue+0xa/0x30
 __ubsan_handle_out_of_bounds+0xe8/0xf0
 do_check+0x77a1/0x11d50
 do_check_common+0x21ea/0x2dc0
 bpf_check+0x242f/0x1cd90
 bpf_prog_load+0x1484/0x1ae0
 __sys_bpf+0x618/0x950
 kern_sys_bpf+0x185/0x700
 load+0x488/0xad0
 do_one_initcall+0x250/0x8d0
 do_initcall_level+0x104/0x190
 do_initcalls+0x59/0xa0
 kernel_init_freeable+0x2a6/0x3e0
 kernel_init+0x1d/0x1d0
 ret_from_fork+0x51e/0xb90
 ret_from_fork_asm+0x1a/0x30
 </TASK>
---[ end trace ]---


***

If these findings have caused you to resend the series or submit a
separate fix, please add the following tag to your commit message:
  Tested-by: syzbot@syzkaller.appspotmail.com

---
This report is generated by a bot. It may contain errors.
syzbot ci engineers can be reached at syzkaller@googlegroups.com.

To test a patch for this bug, please reply with `#syz test`
(should be on a separate line).

The patch should be attached to the email.
Note: arguments like custom git repos and branches are not supported.

[PATCH v2 bpf-next 0/6] bpf: Prep patches for static stack liveness.

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

v1->v2:
. fixed bugs spotted by Eduard, Mykyta, claude and gemini
. fixed selftests that were failing in unpriv
. gemini(sashiko) found several precision improvements in patch 6,
  but they made no difference in real programs.

v1: https://lore.kernel.org/bpf/20260401021635.34636-1-alexei.starovoitov@gmail.com/
First 6 prep patches for static stack liveness.

. do src/dst_reg validation early and remove defensive checks

. sort subprog in topo order. We wanted to do this long ago
  to process global subprogs this way and in other cases.

. Add constant folding pass that computes map_ptr, subprog_idx,
  loads from readonly maps, and other constants that fit into 32-bit

. Use these constants to eliminate dead code. Replace predicted
  conditional branches with "jmp always". That reduces JIT prog size.

. Add two helpers that return access size from their arguments.

Alexei Starovoitov (6):
  bpf: Do register range validation early
  bpf: Sort subprogs in topological order after check_cfg()
  selftests/bpf: Add tests for subprog topological ordering
  bpf: Add bpf_compute_const_regs() and bpf_prune_dead_branches() passes
  bpf: Move verifier helpers to header
  bpf: Add helper and kfunc stack access size resolution

 include/linux/bpf_verifier.h                  |  60 +++
 kernel/bpf/Makefile                           |   2 +-
 kernel/bpf/const_fold.c                       | 396 ++++++++++++++++
 kernel/bpf/verifier.c                         | 422 ++++++++++++++----
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../selftests/bpf/progs/verifier_scalar_ids.c |  20 +-
 .../bpf/progs/verifier_subprog_topo.c         | 226 ++++++++++
 .../selftests/bpf/progs/verifier_unpriv.c     |   6 +-
 .../selftests/bpf/verifier/junk_insn.c        |   4 +-
 9 files changed, 1045 insertions(+), 93 deletions(-)
 create mode 100644 kernel/bpf/const_fold.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_subprog_topo.c

-- 
2.52.0

[syzbot ci] Re: bpf: Prep patches for static stack liveness.

[syzbot ci]

syzbot ci has tested the following series

[v2] bpf: Prep patches for static stack liveness.
https://lore.kernel.org/all/20260402061744.10885-1-alexei.starovoitov@gmail.com
* [PATCH v2 bpf-next 1/6] bpf: Do register range validation early
* [PATCH v2 bpf-next 2/6] bpf: Sort subprogs in topological order after check_cfg()
* [PATCH v2 bpf-next 3/6] selftests/bpf: Add tests for subprog topological ordering
* [PATCH v2 bpf-next 4/6] bpf: Add bpf_compute_const_regs() and bpf_prune_dead_branches() passes
* [PATCH v2 bpf-next 5/6] bpf: Move verifier helpers to header
* [PATCH v2 bpf-next 6/6] bpf: Add helper and kfunc stack access size resolution

and found the following issue:
UBSAN: array-index-out-of-bounds in do_check

Full report is available here:
https://ci.syzbot.org/series/472db170-a3e5-4e2f-992a-f066f3ec68a0

***

UBSAN: array-index-out-of-bounds in do_check

tree:      bpf-next
URL:       https://kernel.googlesource.com/pub/scm/linux/kernel/git/bpf/bpf-next.git
base:      0eeb0094ba0321f0927806857b5f01c1577bc245
arch:      amd64
compiler:  Debian clang version 21.1.8 (++20251221033036+2078da43e25a-1~exp1~20251221153213.50), Debian LLD 21.1.8
config:    https://ci.syzbot.org/builds/35679c0d-9085-497b-89c5-d447be366fc7/config

can: raw protocol
can: broadcast manager protocol
can: netlink gateway - max_hops=1
can: SAE J1939
can: isotp protocol (max_pdu_size 8300)
Bluetooth: RFCOMM TTY layer initialized
Bluetooth: RFCOMM socket layer initialized
Bluetooth: RFCOMM ver 1.11
Bluetooth: BNEP (Ethernet Emulation) ver 1.3
Bluetooth: BNEP filters: protocol multicast
Bluetooth: BNEP socket layer initialized
Bluetooth: HIDP (Human Interface Emulation) ver 1.2
Bluetooth: HIDP socket layer initialized
NET: Registered PF_RXRPC protocol family
Key type rxrpc registered
Key type rxrpc_s registered
NET: Registered PF_KCM protocol family
lec:lane_module_init: lec.c: initialized
mpoa:atm_mpoa_init: mpc.c: initialized
l2tp_core: L2TP core driver, V2.0
l2tp_ppp: PPPoL2TP kernel driver, V2.0
l2tp_ip: L2TP IP encapsulation support (L2TPv3)
l2tp_netlink: L2TP netlink interface
l2tp_eth: L2TP ethernet pseudowire support (L2TPv3)
l2tp_ip6: L2TP IP encapsulation support for IPv6 (L2TPv3)
NET: Registered PF_PHONET protocol family
8021q: 802.1Q VLAN Support v1.8
sctp: Hash tables configured (bind 32/56)
NET: Registered PF_RDS protocol family
Registered RDS/infiniband transport
Registered RDS/tcp transport
tipc: Activated (version 2.0.0)
NET: Registered PF_TIPC protocol family
tipc: Started in single node mode
smc: adding smcd device lo without pnetid
NET: Registered PF_SMC protocol family
9pnet: Installing 9P2000 support
NET: Registered PF_CAIF protocol family
NET: Registered PF_IEEE802154 protocol family
Key type dns_resolver registered
Key type ceph registered
libceph: loaded (mon/osd proto 15/24)
batman_adv: B.A.T.M.A.N. advanced 2025.5 (compatibility version 15) loaded
openvswitch: Open vSwitch switching datapath
NET: Registered PF_VSOCK protocol family
mpls_gso: MPLS GSO support
IPI shorthand broadcast: enabled
sched_clock: Marking stable (24350040289, 119535998)->(24496627492, -27051205)
registered taskstats version 1
------------[ cut here ]------------
UBSAN: array-index-out-of-bounds in kernel/bpf/verifier.c:21711:16
index 10 is out of range for type 'u32[10]' (aka 'unsigned int[10]')
CPU: 0 UID: 0 PID: 1 Comm: swapper/0 Not tainted syzkaller #0 PREEMPT(full) 
Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS 1.16.2-debian-1.16.2-1 04/01/2014
Call Trace:
 <TASK>
 dump_stack_lvl+0xe8/0x150
 ubsan_epilogue+0xa/0x30
 __ubsan_handle_out_of_bounds+0xe8/0xf0
 do_check+0x77a1/0x11d50
 do_check_common+0x21ea/0x2dc0
 bpf_check+0x242f/0x1cd90
 bpf_prog_load+0x1484/0x1ae0
 __sys_bpf+0x618/0x950
 kern_sys_bpf+0x185/0x700
 load+0x488/0xad0
 do_one_initcall+0x250/0x8d0
 do_initcall_level+0x104/0x190
 do_initcalls+0x59/0xa0
 kernel_init_freeable+0x2a6/0x3e0
 kernel_init+0x1d/0x1d0
 ret_from_fork+0x51e/0xb90
 ret_from_fork_asm+0x1a/0x30
 </TASK>
---[ end trace ]---


***

If these findings have caused you to resend the series or submit a
separate fix, please add the following tag to your commit message:
  Tested-by: syzbot@syzkaller.appspotmail.com

---
This report is generated by a bot. It may contain errors.
syzbot ci engineers can be reached at syzkaller@googlegroups.com.

To test a patch for this bug, please reply with `#syz test`
(should be on a separate line).

The patch should be attached to the email.
Note: arguments like custom git repos and branches are not supported.

Re: [syzbot ci] Re: bpf: Prep patches for static stack liveness.

[Alexei Starovoitov]

On Thu, Apr 2, 2026 at 5:53 AM syzbot ci
<syzbot+ci5d1af9c009034c4e@syzkaller.appspotmail.com> wrote:
>
> ------------[ cut here ]------------
> UBSAN: array-index-out-of-bounds in kernel/bpf/verifier.c:21711:16
> index 10 is out of range for type 'u32[10]' (aka 'unsigned int[10]')

Yes, it's speculative out of bounds. r10 will not appear as const,
since loop that populates it goes to ARRAY_SIZE(aux->const_reg_vals);.

If that's the only thing I'll fix it up while applying.