[PATCH bpf-next 0/2] bpf: support shift operations with non-const source operand

[PATCH bpf-next 0/2] bpf: support shift operations with non-const source operand

[Tianci Cao]

Add support for BPF shift operations (BPF_LSH, BPF_RSH, BPF_ARSH)
when the source operand is not a constant.

---

v2 => v3:
- Make comments in scalar32_min_max_arsh and scalar_min_max_arsh
  more concise.
- Change the variable name: umin/umax -> min_shift/max_shift.
- Add tests for non-const src shift operations:
  1. overflow for lsh, rsh and arsh
  2. positive, negative and mixed range dst for arsh

v2: https://lore.kernel.org/bpf/20260612121041.25254-1-ziye@zju.edu.cn/

v1 => v2:
- Fix incorrect comments in scalar32_min_max_arsh and scalar_min_max_arsh.

v1: https://lore.kernel.org/bpf/20260612093818.18609-1-ziye@zju.edu.cn/

Tianci Cao (2):
  bpf: support shift operations with non-const src operand
  selftests/bpf: Add tests for non-const src shift with bounded dst

 kernel/bpf/verifier.c                         |  99 ++++++++---
 .../selftests/bpf/progs/verifier_bounds.c     | 167 ++++++++++++++++++
 2 files changed, 241 insertions(+), 25 deletions(-)

-- 
2.43.0

[PATCH bpf-next 1/2] bpf: support shift operations with non-const src operand

[Tianci Cao]

Currently, the BPF verifier only compute shift operations when the shift
amount is a known constant. This is overly restrictive for cases where
the shift amount is bounded but not fully determined at verification time.
For example, the result of following code is set unknown even though
the shift amount is bounded to [1, 4]:

    u32 shift = bpf_get_prandom_u32();
    shift &= 3;    // shift is in range [0, 3]
    shift += 1;    // shift is in range [1, 4]
    r1 <<= shift;  // non-const but bounded shift amount

Modify the shift helper functions (scalar_min_max_lsh,
scalar32_min_max_lsh, scalar_min_max_rsh, scalar32_min_max_rsh,
scalar_min_max_arsh, scalar32_min_max_arsh) to handle non-const
but bounded shift amounts.

Update is_safe_to_compute_dst_reg_range() to remove the src_is_const
check for shift operations. This approach ensures the verifier
remains sound while allowing more programs to pass verification.

Also modify the comment on is_safe_to_compute_dst_reg_range.
Shifts by more than insn bitness are legal in the BPF ISA; they are
currently implementation-defined behaviour of the underlying architecture,
rather than UB, and have been made legal for performance reasons.
See: https://lore.kernel.org/bpf/20210706112502.2064236-47-sashal@kernel.org

Co-developed-by: Yazhou Tang <tangyazhou518@outlook.com>
Signed-off-by: Yazhou Tang <tangyazhou518@outlook.com>
Co-developed-by: Shenghao Yuan <shenghaoyuan0928@163.com>
Signed-off-by: Shenghao Yuan <shenghaoyuan0928@163.com>
Signed-off-by: Tianci Cao <ziye@zju.edu.cn>
---
 kernel/bpf/verifier.c | 99 ++++++++++++++++++++++++++++++++-----------
 1 file changed, 74 insertions(+), 25 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2abc79dbf281..bf247c219cab 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14277,7 +14277,8 @@ static void scalar32_min_max_lsh(struct bpf_reg_state *dst_reg,
 	struct tnum subreg = tnum_subreg(dst_reg->var_off);
 
 	__scalar32_min_max_lsh(dst_reg, umin_val, umax_val);
-	dst_reg->var_off = tnum_subreg(tnum_lshift(subreg, umin_val));
+	dst_reg->var_off = (umin_val == umax_val) ?
+			   tnum_subreg(tnum_lshift(subreg, umin_val)) : tnum_unknown;
 	/* Not required but being careful mark reg64 bounds as unknown so
 	 * that we are forced to pick them up from tnum and zext later and
 	 * if some path skips this step we are still safe.
@@ -14322,7 +14323,8 @@ static void scalar_min_max_lsh(struct bpf_reg_state *dst_reg,
 	__scalar64_min_max_lsh(dst_reg, umin_val, umax_val);
 	__scalar32_min_max_lsh(dst_reg, umin_val, umax_val);
 
-	dst_reg->var_off = tnum_lshift(dst_reg->var_off, umin_val);
+	dst_reg->var_off = (umin_val == umax_val) ?
+			   tnum_lshift(dst_reg->var_off, umin_val) : tnum_unknown;
 	/* We may learn something more from the var_off */
 	__update_reg_bounds(dst_reg);
 }
@@ -14349,7 +14351,8 @@ static void scalar32_min_max_rsh(struct bpf_reg_state *dst_reg,
 	 * var_off of the result.
 	 */
 
-	dst_reg->var_off = tnum_rshift(subreg, umin_val);
+	dst_reg->var_off = (umin_val == umax_val) ?
+			   tnum_rshift(subreg, umin_val) : tnum_unknown;
 	reg_set_urange32(dst_reg, reg_u32_min(dst_reg) >> umax_val,
 			 reg_u32_max(dst_reg) >> umin_val);
 
@@ -14377,7 +14380,8 @@ static void scalar_min_max_rsh(struct bpf_reg_state *dst_reg,
 	 * and rely on inferring new ones from the unsigned bounds and
 	 * var_off of the result.
 	 */
-	dst_reg->var_off = tnum_rshift(dst_reg->var_off, umin_val);
+	dst_reg->var_off = (umin_val == umax_val) ?
+			   tnum_rshift(dst_reg->var_off, umin_val) : tnum_unknown;
 	reg_set_urange64(dst_reg, reg_umin(dst_reg) >> umax_val,
 			 reg_umax(dst_reg) >> umin_val);
 
@@ -14392,18 +14396,41 @@ static void scalar_min_max_rsh(struct bpf_reg_state *dst_reg,
 static void scalar32_min_max_arsh(struct bpf_reg_state *dst_reg,
 				  struct bpf_reg_state *src_reg)
 {
-	u64 umin_val = reg_u32_min(src_reg);
+	u32 umin_shift = reg_u32_min(src_reg);
+	u32 umax_shift = reg_u32_max(src_reg);
+	s32 smin = reg_s32_min(dst_reg);
+	s32 smax = reg_s32_max(dst_reg);
 
-	/* Upon reaching here, src_known is true and
-	 * umax_val is equal to umin_val.
-	 * Blow away the dst_reg umin_value/umax_value and rely on
-	 * dst_reg var_off to refine the result.
+	/*
+	 * BPF_ARSH on 32-bit subregister. ARSH is a signed divide by
+	 * 2^k (rounding toward -inf for negatives). With a non-constant
+	 * shift in [umin, umax], the result is bounded by dividing the
+	 * extremes of [smin, smax] by the extremes of the divisor:
+	 *
+	 *   smin >= 0:  [smin / 2^umax, smax / 2^umin]
+	 *   smax <  0:  [smin / 2^umin, smax / 2^umax]
+	 *   mixed:      [smin / 2^umin, smax / 2^umin]
+	 *
+	 * var_off is tnum_unknown since a non-constant shift prevents
+	 * precise bit tracking.
 	 */
-	reg_set_srange32(dst_reg,
-			 (u32)(((s32)reg_s32_min(dst_reg)) >> umin_val),
-			 (u32)(((s32)reg_s32_max(dst_reg)) >> umin_val));
-
-	dst_reg->var_off = tnum_arshift(tnum_subreg(dst_reg->var_off), umin_val, 32);
+	if (umin_shift == umax_shift) {
+		reg_set_srange32(dst_reg, (u32)(smin >> umin_shift),
+				 (u32)(smax >> umin_shift));
+		dst_reg->var_off = tnum_arshift(tnum_subreg(dst_reg->var_off),
+						umin_shift, 32);
+	} else {
+		if (smin >= 0)
+			reg_set_srange32(dst_reg, (u32)(smin >> umax_shift),
+					 (u32)(smax >> umin_shift));
+		else if (smax < 0)
+			reg_set_srange32(dst_reg, (u32)(smin >> umin_shift),
+					 (u32)(smax >> umax_shift));
+		else
+			reg_set_srange32(dst_reg, (u32)(smin >> umin_shift),
+					 (u32)(smax >> umin_shift));
+		dst_reg->var_off = tnum_unknown;
+	}
 
 	__mark_reg64_unbounded(dst_reg);
 	__update_reg32_bounds(dst_reg);
@@ -14412,15 +14439,37 @@ static void scalar32_min_max_arsh(struct bpf_reg_state *dst_reg,
 static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
 				struct bpf_reg_state *src_reg)
 {
-	u64 umin_val = reg_umin(src_reg);
+	u64 umin_shift = reg_umin(src_reg);
+	u64 umax_shift = reg_umax(src_reg);
+	s64 smin = reg_smin(dst_reg);
+	s64 smax = reg_smax(dst_reg);
 
-	/* Upon reaching here, src_known is true and umax_val is equal
-	 * to umin_val.
+	/*
+	 * BPF_ARSH (arithmetic right shift) on 64-bit register. Signed
+	 * divide by 2^k, rounding toward -inf for negatives. With a
+	 * non-constant shift in [umin, umax], the result is bounded
+	 * by dividing the extremes of [smin, smax] by the extremes
+	 * of the divisor:
+	 *
+	 *   smin >= 0:  [smin / 2^umax, smax / 2^umin]
+	 *   smax <  0:  [smin / 2^umin, smax / 2^umax]
+	 *   mixed:      [smin / 2^umin, smax / 2^umin]
+	 *
+	 * var_off is tnum_unknown since a non-constant shift prevents
+	 * precise bit tracking.
 	 */
-	reg_set_srange64(dst_reg, reg_smin(dst_reg) >> umin_val,
-			 reg_smax(dst_reg) >> umin_val);
-
-	dst_reg->var_off = tnum_arshift(dst_reg->var_off, umin_val, 64);
+	if (umin_shift == umax_shift) {
+		reg_set_srange64(dst_reg, smin >> umin_shift, smax >> umin_shift);
+		dst_reg->var_off = tnum_arshift(dst_reg->var_off, umin_shift, 64);
+	} else {
+		if (smin >= 0)
+			reg_set_srange64(dst_reg, smin >> umax_shift, smax >> umin_shift);
+		else if (smax < 0)
+			reg_set_srange64(dst_reg, smin >> umin_shift, smax >> umax_shift);
+		else
+			reg_set_srange64(dst_reg, smin >> umin_shift, smax >> umin_shift);
+		dst_reg->var_off = tnum_unknown;
+	}
 
 	/* Its not easy to operate on alu32 bounds here because it depends
 	 * on bits being shifted in from upper 32-bits. Take easy way out
@@ -14516,14 +14565,14 @@ static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
 	case BPF_MOD:
 		return src_is_const;
 
-	/* Shift operators range is only computable if shift dimension operand
-	 * is a constant. Shifts greater than 31 or 63 are undefined. This
-	 * includes shifts by a negative number.
+	/*
+	 * Shifts greater than 31 or 63 are implementation-defined behaviour.
+	 * This includes shifts by a negative number.
 	 */
 	case BPF_LSH:
 	case BPF_RSH:
 	case BPF_ARSH:
-		return (src_is_const && reg_umax(src_reg) < insn_bitness);
+		return reg_umax(src_reg) < insn_bitness;
 	default:
 		return false;
 	}
-- 
2.43.0

Re: [PATCH bpf-next 1/2] bpf: support shift operations with non-const src operand

[bot+bpf-ci]

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

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 2abc79dbf281..bf247c219cab 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -14516,14 +14565,14 @@ static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>  	case BPF_MOD:
>  		return src_is_const;
>
> -	/* Shift operators range is only computable if shift dimension operand
> -	 * is a constant. Shifts greater than 31 or 63 are undefined. This
> -	 * includes shifts by a negative number.
> +	/*
> +	 * Shifts greater than 31 or 63 are implementation-defined behaviour.
> +	 * This includes shifts by a negative number.
>  	 */
>  	case BPF_LSH:
>  	case BPF_RSH:
>  	case BPF_ARSH:
> -		return (src_is_const && reg_umax(src_reg) < insn_bitness);
> +		return reg_umax(src_reg) < insn_bitness;

This drops the src_is_const requirement so that non-constant but bounded
shift amounts are now range-tracked.

Is there a real use case driving this?

Earlier review on this series asked whether compilers actually generate
non-const bounded shifts, and whether any real programs are rejected today
because of the conservative handling.  It was also noted that the current
behaviour does not reject such programs, it just falls back to an unbounded
dst register.  The range tracking added for BPF_DIV/BPF_MOD deliberately
keeps requiring a constant operand for similar reasons.

Without a motivating program that is rejected today, is it worth adding this
complexity to the verifier?


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

Re: [PATCH bpf-next 1/2] bpf: support shift operations with non-const src operand

[Shung-Hsi Yu]

Nit: subject prefix is missing 'v3'.

On Tue, Jun 23, 2026 at 12:42:12PM +0000, bot+bpf-ci@kernel.org wrote:
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 2abc79dbf281..bf247c219cab 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> 
> [ ... ]
> 
> > @@ -14516,14 +14565,14 @@ static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
> >  	case BPF_MOD:
> >  		return src_is_const;
> >
> > -	/* Shift operators range is only computable if shift dimension operand
> > -	 * is a constant. Shifts greater than 31 or 63 are undefined. This
> > -	 * includes shifts by a negative number.
> > +	/*
> > +	 * Shifts greater than 31 or 63 are implementation-defined behaviour.
> > +	 * This includes shifts by a negative number.
> >  	 */
> >  	case BPF_LSH:
> >  	case BPF_RSH:
> >  	case BPF_ARSH:
> > -		return (src_is_const && reg_umax(src_reg) < insn_bitness);
> > +		return reg_umax(src_reg) < insn_bitness;
> 
> This drops the src_is_const requirement so that non-constant but bounded
> shift amounts are now range-tracked.
> 
> Is there a real use case driving this?
> 
> Earlier review on this series asked whether compilers actually generate
> non-const bounded shifts, and whether any real programs are rejected today
> because of the conservative handling.  It was also noted that the current
> behaviour does not reject such programs, it just falls back to an unbounded
> dst register.  The range tracking added for BPF_DIV/BPF_MOD deliberately
> keeps requiring a constant operand for similar reasons.
> 
> Without a motivating program that is rejected today, is it worth adding this
> complexity to the verifier?

I am with the bot here. This adds complexity in the ARSH code path, and
while LSH/RSH code path does pretty much already support non-const
shift, without a compiler generated program showing this pattern it is
hard to justify moving the patchset forward.

[PATCH bpf-next 2/2] selftests/bpf: Add tests for non-const src shift with bounded dst

[Tianci Cao]

Extend the non-const src shift tests to cover scenarios where the
destination is also a bounded random value, not a constant. This
stresses the verifier's ability to compute correct bounds and var_off
when both shift operands carry unknown bits.

Also add overflow-src variants for the BPF_LSH, BPF_RSH and BPF_ARSH
tests where the shift amount src is in range [32, 35] for 32-bit shifts
or [64, 67] for 64-bit shifts. These cases confirm that the verifier
correctly drops the dst register bounds (R1=scalar()) when the shift
amount exceeds the operand width.

The full set of new and extended tests:

  [lsh]  [32]: dst=1,        src=[1, 4]     (dst=const, src=bounded)
  [lsh]  [32]: dst=1,        src=[32, 35]   (overflow src)
  [lsh]  [64]: dst=1,        src=[1, 4]     (dst=const, src=bounded)
  [lsh]  [64]: dst=1,        src=[64, 67]   (overflow src)
  [rsh]  [32]: dst=0xff,     src=[1, 4]     (dst=const, src=bounded)
  [rsh]  [32]: dst=1,        src=[32, 35]   (overflow src)
  [rsh]  [64]: dst=0xff,     src=[1, 4]     (dst=const, src=bounded)
  [rsh]  [64]: dst=1,        src=[64, 67]   (overflow src)
  [arsh] [32]: dst=-8,       src=[1, 4]     (dst=const, src=bounded)
  [arsh] [32]: dst=1,        src=[32, 35]   (overflow src)
  [arsh] [64]: dst=-8,       src=[1, 4]     (dst=const, src=bounded)
  [arsh] [64]: dst=1,        src=[64, 67]   (overflow src)
  [arsh] [32]: dst=[1, 8],   src=[1, 2]     (positive dst)
  [arsh] [32]: dst=[-8, 7],  src=[1, 2]     (mixed-sign dst)
  [arsh] [32]: dst=[-16,-8], src=[1, 2]     (negative / overflow dst)
  [arsh] [64]: dst=[1, 8],   src=[1, 2]     (positive dst)
  [arsh] [64]: dst=[-8, 7],  src=[1, 2]     (mixed-sign dst)
  [arsh] [64]: dst=[-16,-8], src=[1, 2]     (negative / overflow dst)

Co-developed-by: Yazhou Tang <tangyazhou518@outlook.com>
Signed-off-by: Yazhou Tang <tangyazhou518@outlook.com>
Co-developed-by: Shenghao Yuan <shenghaoyuan0928@163.com>
Signed-off-by: Shenghao Yuan <shenghaoyuan0928@163.com>
Signed-off-by: Tianci Cao <ziye@zju.edu.cn>
---
 .../selftests/bpf/progs/verifier_bounds.c     | 167 ++++++++++++++++++
 1 file changed, 167 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index bc038ac2df98..52ae3dc59360 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -482,6 +482,173 @@ l0_%=:	/* exit */					\
 	: __clobber_all);
 }
 
+#define SHIFT_NON_CONST_SRC_TEST(name, desc, rand, dst, src, op, src_add, dst_init, msg) \
+	SEC("socket")					\
+	__description(desc)				\
+	__success __log_level(2)			\
+	__msg(#dst " " op " " #src " {{.*}}; " msg)	\
+	__naked void name(void)				\
+	{						\
+		asm volatile ("				\
+		call %[bpf_get_prandom_u32];		\
+		" #src " = " #rand ";			\
+		" #src " &= 3;				\
+		" #src " += " #src_add ";		\
+		" #dst " = " #dst_init ";		\
+		" #dst " " op " " #src ";		\
+		exit;					\
+"		:: __imm(bpf_get_prandom_u32)		\
+		: __clobber_all);			\
+	}
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_lsh_32,
+	"bounds check after non-const 32-bit left shift",
+	w0, w1, w2, "<<=", 1, 1,
+	"R1=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=16,var_off=(0x0; 0x1f))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_lsh_32_overflow,
+	"bounds check after non-const 32-bit lsh with overflow src",
+	w0, w1, w2, "<<=", 32, 1,
+	"R1=scalar() R2=scalar(smin=umin=smin32=umin32=32,smax=umax=smax32=umax32=35,var_off=(0x20; 0x3))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_rsh_32,
+	"bounds check after non-const 32-bit right shift",
+	w0, w1, w2, ">>=", 1, 0xff,
+	"R1=scalar(smin=umin=smin32=umin32=15,smax=umax=smax32=umax32=127,var_off=(0x0; 0x7f))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_rsh_32_overflow,
+	"bounds check after non-const 32-bit rsh with overflow src",
+	w0, w1, w2, ">>=", 32, 1,
+	"R1=scalar() R2=scalar(smin=umin=smin32=umin32=32,smax=umax=smax32=umax32=35,var_off=(0x20; 0x3))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_arsh_32,
+	"bounds check after non-const 32-bit arithmetic shift",
+	w0, w1, w2, "s>>=", 1, -8,
+	"R1=scalar(smin=umin=umin32=0xfffffffc,smax=umax=0xffffffff,smin32=-4,smax32=-1,var_off=(0xfffffffc; 0x3)) R2=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_arsh_32_overflow,
+	"bounds check after non-const 32-bit arsh with overflow src",
+	w0, w1, w2, "s>>=", 32, 1,
+	"R1=scalar() R2=scalar(smin=umin=smin32=umin32=32,smax=umax=smax32=umax32=35,var_off=(0x20; 0x3))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_lsh_64,
+	"bounds check after non-const 64-bit left shift",
+	r0, r1, r2, "<<=", 1, 1,
+	"R1=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=16,var_off=(0x0; 0x1f))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_lsh_64_overflow,
+	"bounds check after non-const 64-bit lsh with overflow src",
+	r0, r1, r2, "<<=", 64, 1,
+	"R1=scalar() R2=scalar(smin=umin=smin32=umin32=64,smax=umax=smax32=umax32=67,var_off=(0x40; 0x3))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_rsh_64,
+	"bounds check after non-const 64-bit right shift",
+	r0, r1, r2, ">>=", 1, 0xff,
+	"R1=scalar(smin=umin=smin32=umin32=15,smax=umax=smax32=umax32=127,var_off=(0x0; 0x7f))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_rsh_64_overflow,
+	"bounds check after non-const 64-bit rsh with overflow src",
+	r0, r1, r2, ">>=", 64, 1,
+	"R1=scalar() R2=scalar(smin=umin=smin32=umin32=64,smax=umax=smax32=umax32=67,var_off=(0x40; 0x3))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_arsh_64,
+	"bounds check after non-const 64-bit arithmetic shift",
+	r0, r1, r2, "s>>=", 1, -8,
+	"R1=scalar(smin=smin32=-4,smax=smax32=-1,umin=0xfffffffffffffffc,umin32=0xfffffffc,var_off=(0xfffffffffffffffc; 0x3)) R2=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))"
+)
+
+SHIFT_NON_CONST_SRC_TEST(
+	shift_with_non_const_src_arsh_64_overflow,
+	"bounds check after non-const 64-bit arsh with overflow src",
+	r0, r1, r2, "s>>=", 64, 1,
+	"R1=scalar() R2=scalar(smin=umin=smin32=umin32=64,smax=umax=smax32=umax32=67,var_off=(0x40; 0x3))"
+)
+
+#define SHIFT_ARSH_DST_RANGE_TEST(name, desc, rand, dst, src, dst_mask, dst_delta, msg) \
+	SEC("socket")					\
+	__description(desc)				\
+	__success __log_level(2)			\
+	__msg(#dst " s>>= " #src " {{.*}}; {{.*}} " msg)\
+	__naked void name(void)				\
+	{						\
+		asm volatile ("				\
+		call %[bpf_get_prandom_u32];		\
+		" #dst " = " #rand ";			\
+		" #dst " &= " #dst_mask ";		\
+		" #dst " += " #dst_delta ";		\
+		call %[bpf_get_prandom_u32];		\
+		" #src " = " #rand ";			\
+		" #src " &= 1;				\
+		" #src " += 1;				\
+		" #dst " s>>= " #src ";			\
+		exit;					\
+"		:: __imm(bpf_get_prandom_u32)		\
+		: __clobber_all);			\
+	}
+
+SHIFT_ARSH_DST_RANGE_TEST(
+	shift_with_non_const_src_arsh_32_pos,
+	"bounds check after non-const 32-bit arsh with positive dst",
+	w0, w6, w2, 7, 1,
+	"R6=scalar(smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))"
+)
+
+SHIFT_ARSH_DST_RANGE_TEST(
+	shift_with_non_const_src_arsh_32_mixed,
+	"bounds check after non-const 32-bit arsh with mixed-sign dst",
+	w0, w6, w2, 15, -8,
+	"R6=scalar(smin=0,smax=umax=0xffffffff,smin32=-4,smax32=3,var_off=(0x0; 0xffffffff))"
+)
+
+SHIFT_ARSH_DST_RANGE_TEST(
+	shift_with_non_const_src_arsh_32_neg,
+	"bounds check after non-const 32-bit arsh with negative dst",
+	w0, w6, w2, 8, -16,
+	"R6=scalar(smin=umin=umin32=0xfffffff8,smax=umax=umax32=0xfffffffe,smin32=-8,smax32=-2,var_off=(0xfffffff8; 0x7))"
+)
+
+SHIFT_ARSH_DST_RANGE_TEST(
+	shift_with_non_const_src_arsh_64_pos,
+	"bounds check after non-const 64-bit arsh with positive dst",
+	r0, r6, r2, 7, 1,
+	"R6=scalar(smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))"
+)
+
+SHIFT_ARSH_DST_RANGE_TEST(
+	shift_with_non_const_src_arsh_64_mixed,
+	"bounds check after non-const 64-bit arsh with mixed-sign dst",
+	r0, r6, r2, 15, -8,
+	"R6=scalar(smin=smin32=-4,smax=smax32=3)"
+)
+
+SHIFT_ARSH_DST_RANGE_TEST(
+	shift_with_non_const_src_arsh_64_neg,
+	"bounds check after non-const 64-bit arsh with negative dst",
+	r0, r6, r2, 8, -16,
+	"R6=scalar(smin=smin32=-8,smax=smax32=-2,umin=0xfffffffffffffff8,umax=0xfffffffffffffffe,umin32=0xfffffff8,umax32=0xfffffffe,var_off=(0xfffffffffffffff8; 0x7))"
+)
+
 SEC("socket")
 __description("bounds check after 32-bit right shift with 64-bit input")
 __failure __msg("math between map_value pointer and 4294967294 is not allowed")
-- 
2.43.0

[PATCH bpf-next 0/2] bpf: support shift operations with non-const source operand

[Tianci Cao]

Add support for BPF shift operations (BPF_LSH, BPF_RSH, BPF_ARSH)
when the source operand is not a constant but is bounded.

Tianci Cao (2):
  bpf: support shift operations with non-const src operand
  selftests/bpf: Add tests for non-const src shift

 kernel/bpf/verifier.c                         | 100 ++++++++++++----
 .../selftests/bpf/progs/verifier_bounds.c     | 108 ++++++++++++++++++
 2 files changed, 184 insertions(+), 24 deletions(-)

-- 
2.43.0

[PATCH bpf-next 1/2] bpf: support shift operations with non-const src operand

[Tianci Cao]

Currently, the BPF verifier only allows shift operations when the shift
amount is a known constant. This is overly restrictive for cases where
the shift amount is bounded but not fully determined at verification time.
For example, the following code is rejected by the verifier even though
the shift amount is bounded to [1, 4]:

    u32 shift = bpf_get_prandom_u32();
    shift &= 3;    // shift is in range [0, 3]
    shift += 1;    // shift is in range [1, 4]
    r1 <<= shift;  // non-const but bounded shift amount

Modify the shift helper functions (scalar_min_max_lsh,
scalar32_min_max_lsh, scalar_min_max_rsh, scalar32_min_max_rsh,
scalar_min_max_arsh, scalar32_min_max_arsh) to handle non-const
but bounded shift amounts.

Update is_safe_to_compute_dst_reg_range() to remove the src_is_const
check for shift operations. This approach ensures the verifier
remains sound while allowing more programs to pass verification.

Also modify the comment on is_safe_to_compute_dst_reg_range.
Shifts by more than insn bitness are legal in the BPF ISA; they are
currently implementation-defined behaviour of the underlying architecture,
rather than UB, and have been made legal for performance reasons.
See: https://lore.kernel.org/bpf/20210706112502.2064236-47-sashal@kernel.org

Co-developed-by: Yazhou Tang <tangyazhou518@outlook.com>
Signed-off-by: Yazhou Tang <tangyazhou518@outlook.com>
Co-developed-by: Shenghao Yuan <shenghaoyuan0928@163.com>
Signed-off-by: Shenghao Yuan <shenghaoyuan0928@163.com>
Signed-off-by: Tianci Cao <ziye@zju.edu.cn>
---
 kernel/bpf/verifier.c | 100 ++++++++++++++++++++++++++++++++----------
 1 file changed, 76 insertions(+), 24 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8ed484cb1a8a..6eba2af1b5c4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14184,7 +14184,8 @@ static void scalar32_min_max_lsh(struct bpf_reg_state *dst_reg,
 	struct tnum subreg = tnum_subreg(dst_reg->var_off);
 
 	__scalar32_min_max_lsh(dst_reg, umin_val, umax_val);
-	dst_reg->var_off = tnum_subreg(tnum_lshift(subreg, umin_val));
+	dst_reg->var_off = (umin_val == umax_val) ?
+			   tnum_subreg(tnum_lshift(subreg, umin_val)) : tnum_unknown;
 	/* Not required but being careful mark reg64 bounds as unknown so
 	 * that we are forced to pick them up from tnum and zext later and
 	 * if some path skips this step we are still safe.
@@ -14229,7 +14230,8 @@ static void scalar_min_max_lsh(struct bpf_reg_state *dst_reg,
 	__scalar64_min_max_lsh(dst_reg, umin_val, umax_val);
 	__scalar32_min_max_lsh(dst_reg, umin_val, umax_val);
 
-	dst_reg->var_off = tnum_lshift(dst_reg->var_off, umin_val);
+	dst_reg->var_off = (umin_val == umax_val) ?
+			   tnum_lshift(dst_reg->var_off, umin_val) : tnum_unknown;
 	/* We may learn something more from the var_off */
 	__update_reg_bounds(dst_reg);
 }
@@ -14256,7 +14258,8 @@ static void scalar32_min_max_rsh(struct bpf_reg_state *dst_reg,
 	 * var_off of the result.
 	 */
 
-	dst_reg->var_off = tnum_rshift(subreg, umin_val);
+	dst_reg->var_off = (umin_val == umax_val) ?
+			   tnum_rshift(subreg, umin_val) : tnum_unknown;
 	reg_set_urange32(dst_reg, reg_u32_min(dst_reg) >> umax_val,
 			 reg_u32_max(dst_reg) >> umin_val);
 
@@ -14284,7 +14287,8 @@ static void scalar_min_max_rsh(struct bpf_reg_state *dst_reg,
 	 * and rely on inferring new ones from the unsigned bounds and
 	 * var_off of the result.
 	 */
-	dst_reg->var_off = tnum_rshift(dst_reg->var_off, umin_val);
+	dst_reg->var_off = (umin_val == umax_val) ?
+			   tnum_rshift(dst_reg->var_off, umin_val) : tnum_unknown;
 	reg_set_urange64(dst_reg, reg_umin(dst_reg) >> umax_val,
 			 reg_umax(dst_reg) >> umin_val);
 
@@ -14299,18 +14303,44 @@ static void scalar_min_max_rsh(struct bpf_reg_state *dst_reg,
 static void scalar32_min_max_arsh(struct bpf_reg_state *dst_reg,
 				  struct bpf_reg_state *src_reg)
 {
-	u64 umin_val = reg_u32_min(src_reg);
+	u32 umin_val = reg_u32_min(src_reg);
+	u32 umax_val = reg_u32_max(src_reg);
+	s32 smin = reg_s32_min(dst_reg);
+	s32 smax = reg_s32_max(dst_reg);
 
-	/* Upon reaching here, src_known is true and
-	 * umax_val is equal to umin_val.
-	 * Blow away the dst_reg umin_value/umax_value and rely on
-	 * dst_reg var_off to refine the result.
+	/*
+	 * BPF_ARSH on 32-bit subregister. The shift amount [umin, umax]
+	 * may be non-constant, so we conservatively derive signed bounds:
+	 *
+	 *   smin >= 0: non-negative value; right-shift reduces magnitude.
+	 *              result in [s32_max >> umax_val, s32_min >> umin_val]
+	 *              e.g. [4,8] >> [1,2] → [1,4]
+	 *   smax <  0: negative value; right-shift increases (toward 0).
+	 *              result in [s32_min >> umin_val, s32_max >> umax_val]
+	 *              e.g. [-8,-4] >> [1,2] → [-4,-1]
+	 *   mixed:     result in [s32_min >> umin_val, s32_max >> umin_val]
+	 *              e.g. [-8,8] >> [1,2] → [-4,4]
+	 *
+	 * var_off is set to tnum_unknown because without a constant shift
+	 * amount we cannot precisely track which bits remain known.
 	 */
-	reg_set_srange32(dst_reg,
-			 (u32)(((s32)reg_s32_min(dst_reg)) >> umin_val),
-			 (u32)(((s32)reg_s32_max(dst_reg)) >> umin_val));
-
-	dst_reg->var_off = tnum_arshift(tnum_subreg(dst_reg->var_off), umin_val, 32);
+	if (umin_val == umax_val) {
+		reg_set_srange32(dst_reg, (u32)(smin >> umin_val),
+				 (u32)(smax >> umin_val));
+		dst_reg->var_off = tnum_arshift(tnum_subreg(dst_reg->var_off),
+						umin_val, 32);
+	} else {
+		if (smin >= 0)
+			reg_set_srange32(dst_reg, (u32)(smin >> umax_val),
+					 (u32)(smax >> umin_val));
+		else if (smax < 0)
+			reg_set_srange32(dst_reg, (u32)(smin >> umin_val),
+					 (u32)(smax >> umax_val));
+		else
+			reg_set_srange32(dst_reg, (u32)(smin >> umin_val),
+					 (u32)(smax >> umin_val));
+		dst_reg->var_off = tnum_unknown;
+	}
 
 	__mark_reg64_unbounded(dst_reg);
 	__update_reg32_bounds(dst_reg);
@@ -14320,14 +14350,36 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
 				struct bpf_reg_state *src_reg)
 {
 	u64 umin_val = reg_umin(src_reg);
+	u64 umax_val = reg_umax(src_reg);
+	s64 smin = reg_smin(dst_reg);
+	s64 smax = reg_smax(dst_reg);
 
-	/* Upon reaching here, src_known is true and umax_val is equal
-	 * to umin_val.
+	/*
+	 * BPF_ARSH (arithmetic right shift) on 64-bit register.
+	 * Same three-branch logic as the 32-bit variant (scalar32_min_max_arsh):
+	 *
+	 *   smin >= 0: result in [smax >> umax_val, smin >> umin_val]
+	 *              e.g. [4,8] >> [1,2] → [1,4]
+	 *   smax <  0: result in [smin >> umin_val, smax >> umax_val]
+	 *              e.g. [-8,-4] >> [1,2] → [-4,-1]
+	 *   mixed:     result in [smin >> umin_val, smax >> umin_val]
+	 *              e.g. [-8,8] >> [1,2] → [-4,4]
+	 *
+	 * var_off is set to tnum_unknown since a non-constant shift amount
+	 * prevents precise bit tracking.
 	 */
-	reg_set_srange64(dst_reg, reg_smin(dst_reg) >> umin_val,
-			 reg_smax(dst_reg) >> umin_val);
-
-	dst_reg->var_off = tnum_arshift(dst_reg->var_off, umin_val, 64);
+	if (umin_val == umax_val) {
+		reg_set_srange64(dst_reg, smin >> umin_val, smax >> umin_val);
+		dst_reg->var_off = tnum_arshift(dst_reg->var_off, umin_val, 64);
+	} else {
+		if (smin >= 0)
+			reg_set_srange64(dst_reg, smin >> umax_val, smax >> umin_val);
+		else if (smax < 0)
+			reg_set_srange64(dst_reg, smin >> umin_val, smax >> umax_val);
+		else
+			reg_set_srange64(dst_reg, smin >> umin_val, smax >> umin_val);
+		dst_reg->var_off = tnum_unknown;
+	}
 
 	/* Its not easy to operate on alu32 bounds here because it depends
 	 * on bits being shifted in from upper 32-bits. Take easy way out
@@ -14423,14 +14475,14 @@ static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
 	case BPF_MOD:
 		return src_is_const;
 
-	/* Shift operators range is only computable if shift dimension operand
-	 * is a constant. Shifts greater than 31 or 63 are undefined. This
-	 * includes shifts by a negative number.
+	/*
+	 * Shifts greater than 31 or 63 are implementation-defined behaviour.
+	 * This includes shifts by a negative number.
 	 */
 	case BPF_LSH:
 	case BPF_RSH:
 	case BPF_ARSH:
-		return (src_is_const && reg_umax(src_reg) < insn_bitness);
+		return reg_umax(src_reg) < insn_bitness;
 	default:
 		return false;
 	}
-- 
2.43.0

Re: [PATCH bpf-next 1/2] bpf: support shift operations with non-const src operand

[bot+bpf-ci]

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

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index eb46a81a8c51..cec051a4e942 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -14387,18 +14391,44 @@ static void scalar_min_max_rsh(struct bpf_reg_state *dst_reg,
>  static void scalar32_min_max_arsh(struct bpf_reg_state *dst_reg,
>  				  struct bpf_reg_state *src_reg)
>  {
> -	u64 umin_val = reg_u32_min(src_reg);
> +	u32 umin_val = reg_u32_min(src_reg);
> +	u32 umax_val = reg_u32_max(src_reg);
> +	s32 smin = reg_s32_min(dst_reg);
> +	s32 smax = reg_s32_max(dst_reg);
>
> +	/*
> +	 * BPF_ARSH on 32-bit subregister. The shift amount [umin, umax]
> +	 * may be non-constant, so we conservatively derive signed bounds:
> +	 *
> +	 *   smin >= 0: non-negative value; right-shift reduces magnitude.
> +	 *              result in [s32_max >> umax_val, s32_min >> umin_val]
> +	 *              e.g. [4,8] >> [1,2] → [1,4]

The comment for the smin >= 0 branch describes the result as
[s32_max >> umax_val, s32_min >> umin_val], but the code below computes
[smin >> umax_val, smax >> umin_val]:

>  	if (umin_val == umax_val) {
>  ...
>  	} else {
>  		if (smin >= 0)
>  			reg_set_srange32(dst_reg, (u32)(smin >> umax_val),
>  					 (u32)(smax >> umin_val));

The worked example in the comment matches the code rather than the
prose formula: [4,8] >> [1,2] gives [4>>2, 8>>1] = [1,4] as written in
the example, whereas [s32_max>>umax, s32_min>>umin] = [8>>2, 4>>1] =
[2,2].  Should the comment read [s32_min >> umax_val, s32_max >> umin_val]
so it agrees with the code and the example?

> +	 *   smax <  0: negative value; right-shift increases (toward 0).
> +	 *              result in [s32_min >> umin_val, s32_max >> umax_val]
> +	 *              e.g. [-8,-4] >> [1,2] → [-4,-1]
> +	 *   mixed:     result in [s32_min >> umin_val, s32_max >> umin_val]
> +	 *              e.g. [-8,8] >> [1,2] → [-4,4]
> +	 *
> +	 * var_off is set to tnum_unknown because without a constant shift
> +	 * amount we cannot precisely track which bits remain known.
> +	 */

[ ... ]

> @@ -14408,14 +14438,36 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
>  				struct bpf_reg_state *src_reg)
>  {
>  	u64 umin_val = reg_umin(src_reg);
> +	u64 umax_val = reg_umax(src_reg);
> +	s64 smin = reg_smin(dst_reg);
> +	s64 smax = reg_smax(dst_reg);
>
> +	/*
> +	 * BPF_ARSH (arithmetic right shift) on 64-bit register.
> +	 * Same three-branch logic as the 32-bit variant (scalar32_min_max_arsh):
> +	 *
> +	 *   smin >= 0: result in [smax >> umax_val, smin >> umin_val]
> +	 *              e.g. [4,8] >> [1,2] → [1,4]

The same mismatch appears in the 64-bit variant.  The comment states the
smin >= 0 branch produces [smax >> umax_val, smin >> umin_val], but the
code computes [smin >> umax_val, smax >> umin_val]:

>  	if (umin_val == umax_val) {
>  ...
>  	} else {
>  		if (smin >= 0)
>  			reg_set_srange64(dst_reg, smin >> umax_val, smax >> umin_val);

Again the example [4,8] >> [1,2] → [1,4] matches the code, not the
formula [smax>>umax, smin>>umin] = [8>>2, 4>>1] = [2,2].  Could the
comment be updated to [smin >> umax_val, smax >> umin_val]?

> +	 *   smax <  0: result in [smin >> umin_val, smax >> umax_val]
> +	 *              e.g. [-8,-4] >> [1,2] → [-4,-1]
> +	 *   mixed:     result in [smin >> umin_val, smax >> umin_val]
> +	 *              e.g. [-8,8] >> [1,2] → [-4,4]
> +	 *
> +	 * var_off is set to tnum_unknown since a non-constant shift amount
> +	 * prevents precise bit tracking.
> +	 */


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

Re: [PATCH bpf-next 1/2] bpf: support shift operations with non-const src operand

[Alexei Starovoitov]

On Fri Jun 12, 2026 at 2:38 AM PDT, Tianci Cao wrote:
> Currently, the BPF verifier only allows shift operations when the shift
> amount is a known constant. This is overly restrictive for cases where
> the shift amount is bounded but not fully determined at verification time.
> For example, the following code is rejected by the verifier even though
> the shift amount is bounded to [1, 4]:
>
>     u32 shift = bpf_get_prandom_u32();
>     shift &= 3;    // shift is in range [0, 3]
>     shift += 1;    // shift is in range [1, 4]
>     r1 <<= shift;  // non-const but bounded shift amount

Rejected? I don't believe so. The verifier accepts it, but falls
back to conservative.

> Modify the shift helper functions (scalar_min_max_lsh,
> scalar32_min_max_lsh, scalar_min_max_rsh, scalar32_min_max_rsh,
> scalar_min_max_arsh, scalar32_min_max_arsh) to handle non-const
> but bounded shift amounts.
>
> Update is_safe_to_compute_dst_reg_range() to remove the src_is_const
> check for shift operations. This approach ensures the verifier
> remains sound while allowing more programs to pass verification.
>
> Also modify the comment on is_safe_to_compute_dst_reg_range.
> Shifts by more than insn bitness are legal in the BPF ISA; they are
> currently implementation-defined behaviour of the underlying architecture,
> rather than UB, and have been made legal for performance reasons.
> See: https://lore.kernel.org/bpf/20210706112502.2064236-47-sashal@kernel.org

What this is for?
Do you see such code generated by compiler in real programs?
Does it cause issues with accepting such _real_ programs ?

If not, sorry, we should not complicate the verifier for theoretical case.

pw-bot: cr

Re: [PATCH bpf-next 1/2] bpf: support shift operations with non-const src operand

[Eduard Zingerman]

On Fri, 2026-06-12 at 09:09 -0700, Alexei Starovoitov wrote:
> On Fri Jun 12, 2026 at 2:38 AM PDT, Tianci Cao wrote:
> > Currently, the BPF verifier only allows shift operations when the shift
> > amount is a known constant. This is overly restrictive for cases where
> > the shift amount is bounded but not fully determined at verification time.
> > For example, the following code is rejected by the verifier even though
> > the shift amount is bounded to [1, 4]:
> > 
> >     u32 shift = bpf_get_prandom_u32();
> >     shift &= 3;    // shift is in range [0, 3]
> >     shift += 1;    // shift is in range [1, 4]
> >     r1 <<= shift;  // non-const but bounded shift amount
> 
> Rejected? I don't believe so. The verifier accepts it, but falls
> back to conservative.

Yes, the verifier would resort to making dst register unbound.

> 
> > Modify the shift helper functions (scalar_min_max_lsh,
> > scalar32_min_max_lsh, scalar_min_max_rsh, scalar32_min_max_rsh,
> > scalar_min_max_arsh, scalar32_min_max_arsh) to handle non-const
> > but bounded shift amounts.
> > 
> > Update is_safe_to_compute_dst_reg_range() to remove the src_is_const
> > check for shift operations. This approach ensures the verifier
> > remains sound while allowing more programs to pass verification.
> > 
> > Also modify the comment on is_safe_to_compute_dst_reg_range.
> > Shifts by more than insn bitness are legal in the BPF ISA; they are
> > currently implementation-defined behaviour of the underlying architecture,
> > rather than UB, and have been made legal for performance reasons.
> > See: https://lore.kernel.org/bpf/20210706112502.2064236-47-sashal@kernel.org
> 
> What this is for?
> Do you see such code generated by compiler in real programs?
> Does it cause issues with accepting such _real_ programs ?
> 
> If not, sorry, we should not complicate the verifier for theoretical case.

LSH/RSH code paths modifications are absolutely minimal,
I think there is no reason not to land those.
ARSH code path has more changes, but the logic is simple.

Re: [PATCH bpf-next 1/2] bpf: support shift operations with non-const src operand

[曹天赐]

On 6/12/26 9:09, Alexei Starovoitov wrote:
> On Fri Jun 12, 2026 at 2:38 AM PDT, Tianci Cao wrote:
> > Currently, the BPF verifier only allows shift operations when the shift
> > amount is a known constant. This is overly restrictive for cases where
> > the shift amount is bounded but not fully determined at verification time.
> > For example, the following code is rejected by the verifier even though
> > the shift amount is bounded to [1, 4]:
> >
> >     u32 shift = bpf_get_prandom_u32();
> >     shift &= 3;    // shift is in range [0, 3]
> >     shift += 1;    // shift is in range [1, 4]
> >     r1 <<= shift;  // non-const but bounded shift amount
>
> Rejected? I don't believe so. The verifier accepts it, but falls
> back to conservative.

Right, I should have said "falls back to conservative". The dst
register just becomes unknown. Sorry for the confusion.

> What this is for?
> Do you see such code generated by compiler in real programs?
> Does it cause issues with accepting such _real_ programs ?
>
> If not, sorry, we should not complicate the verifier for theoretical case.
The motivation here is purely about relaxing an overly
strict check in the verifier. In our opinion, the "shift amount must
be fully constant" rule is more conservative than necessary.
The verifier already tracks [umin, umax] for the src register,
and a bounded-but-non-const shift can be handled soundly with very
simple logic. The patch extends the existing scalar_min_max_*
helpers to take advantage of this. Happy to hear other thoughts
on whether this is worth landing.

Re: [PATCH bpf-next 1/2] bpf: support shift operations with non-const src operand

[Eduard Zingerman]

On Fri, 2026-06-12 at 17:38 +0800, Tianci Cao wrote:
> Currently, the BPF verifier only allows shift operations when the shift
> amount is a known constant. This is overly restrictive for cases where
> the shift amount is bounded but not fully determined at verification time.
> For example, the following code is rejected by the verifier even though
> the shift amount is bounded to [1, 4]:
> 
>     u32 shift = bpf_get_prandom_u32();
>     shift &= 3;    // shift is in range [0, 3]
>     shift += 1;    // shift is in range [1, 4]
>     r1 <<= shift;  // non-const but bounded shift amount
> 
> Modify the shift helper functions (scalar_min_max_lsh,
> scalar32_min_max_lsh, scalar_min_max_rsh, scalar32_min_max_rsh,
> scalar_min_max_arsh, scalar32_min_max_arsh) to handle non-const
> but bounded shift amounts.
> 
> Update is_safe_to_compute_dst_reg_range() to remove the src_is_const
> check for shift operations. This approach ensures the verifier
> remains sound while allowing more programs to pass verification.
> 
> Also modify the comment on is_safe_to_compute_dst_reg_range.
> Shifts by more than insn bitness are legal in the BPF ISA; they are
> currently implementation-defined behaviour of the underlying architecture,
> rather than UB, and have been made legal for performance reasons.
> See: https://lore.kernel.org/bpf/20210706112502.2064236-47-sashal@kernel.org
> 
> Co-developed-by: Yazhou Tang <tangyazhou518@outlook.com>
> Signed-off-by: Yazhou Tang <tangyazhou518@outlook.com>
> Co-developed-by: Shenghao Yuan <shenghaoyuan0928@163.com>
> Signed-off-by: Shenghao Yuan <shenghaoyuan0928@163.com>
> Signed-off-by: Tianci Cao <ziye@zju.edu.cn>
> ---

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

> @@ -14320,14 +14350,36 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
>  				struct bpf_reg_state *src_reg)
>  {
>  	u64 umin_val = reg_umin(src_reg);
> +	u64 umax_val = reg_umax(src_reg);
> +	s64 smin = reg_smin(dst_reg);
> +	s64 smax = reg_smax(dst_reg);

Nit: the naming becomes confusing when reading 'smin >> umax_val'.
     I'd use something like 'smin >> max_shift'.

>  
> -	/* Upon reaching here, src_known is true and umax_val is equal
> -	 * to umin_val.
> +	/*
> +	 * BPF_ARSH (arithmetic right shift) on 64-bit register.
> +	 * Same three-branch logic as the 32-bit variant (scalar32_min_max_arsh):
> +	 *
> +	 *   smin >= 0: result in [smax >> umax_val, smin >> umin_val]
> +	 *              e.g. [4,8] >> [1,2] → [1,4]

Nit: I'm not sure that repeating the code snippet in the comment is helpful, tbh.
     Maybe just have an example for each case and explain it in terms of dividing
     by smallest or biggest divisor.

> +	 *   smax <  0: result in [smin >> umin_val, smax >> umax_val]
> +	 *              e.g. [-8,-4] >> [1,2] → [-4,-1]
> +	 *   mixed:     result in [smin >> umin_val, smax >> umin_val]
> +	 *              e.g. [-8,8] >> [1,2] → [-4,4]
> +	 *
> +	 * var_off is set to tnum_unknown since a non-constant shift amount
> +	 * prevents precise bit tracking.
>  	 */
> -	reg_set_srange64(dst_reg, reg_smin(dst_reg) >> umin_val,
> -			 reg_smax(dst_reg) >> umin_val);
> -
> -	dst_reg->var_off = tnum_arshift(dst_reg->var_off, umin_val, 64);
> +	if (umin_val == umax_val) {
> +		reg_set_srange64(dst_reg, smin >> umin_val, smax >> umin_val);
> +		dst_reg->var_off = tnum_arshift(dst_reg->var_off, umin_val, 64);
> +	} else {
> +		if (smin >= 0)
> +			reg_set_srange64(dst_reg, smin >> umax_val, smax >> umin_val);
> +		else if (smax < 0)
> +			reg_set_srange64(dst_reg, smin >> umin_val, smax >> umax_val);
> +		else
> +			reg_set_srange64(dst_reg, smin >> umin_val, smax >> umin_val);
> +		dst_reg->var_off = tnum_unknown;
> +	}
>  
>  	/* Its not easy to operate on alu32 bounds here because it depends
>  	 * on bits being shifted in from upper 32-bits. Take easy way out

[...]

Re: [PATCH bpf-next 1/2] bpf: support shift operations with non-const src operand

[曹天赐]

On 6/13/26 5:17, Eduard Zingerman wrote:
> On Fri, 2026-06-12 at 17:38 +0800, Tianci Cao wrote:
[...]
> 
>> @@ -14320,14 +14350,36 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
>>   				struct bpf_reg_state *src_reg)
>>   {
>>   	u64 umin_val = reg_umin(src_reg);
>> +	u64 umax_val = reg_umax(src_reg);
>> +	s64 smin = reg_smin(dst_reg);
>> +	s64 smax = reg_smax(dst_reg);
> 
> Nit: the naming becomes confusing when reading 'smin >> umax_val'.
>       I'd use something like 'smin >> max_shift'.
Agreed. I will make this change in v2.

>> -	/* Upon reaching here, src_known is true and umax_val is equal
>> -	 * to umin_val.
>> +	/*
>> +	 * BPF_ARSH (arithmetic right shift) on 64-bit register.
>> +	 * Same three-branch logic as the 32-bit variant (scalar32_min_max_arsh):
>> +	 *
>> +	 *   smin >= 0: result in [smax >> umax_val, smin >> umin_val]
>> +	 *              e.g. [4,8] >> [1,2] → [1,4]
> 
> Nit: I'm not sure that repeating the code snippet in the comment is helpful, tbh.
>       Maybe just have an example for each case and explain it in terms of dividing
>       by smallest or biggest divisor.
> 

Agreed. I will move some comments.

> 
> [...]