[PATCH bpf-next 1/3] bpf: Support negative offsets and BPF_SUB for linked register tracking

[Puranjay Mohan <puranjay@kernel.org>]

Extend the linked register tracking to support:

1. Negative offsets via BPF_ADD (e.g., r1 += -4)
2. BPF_SUB operations (e.g., r1 -= 4), which is treated as r1 += -4

Previously, the verifier only tracked positive constant deltas between
linked registers using BPF_ADD. This limitation meant patterns like:

  r1 = r0
  r1 += -4
  if r1 s>= 0 goto ...   // r1 >= 0 implies r0 >= 4
  // verifier couldn't propagate bounds back to r0

With this change, the verifier can now track negative deltas in reg->off
(which is already s32), enabling bound propagation for the above pattern.

The changes include:
- Accept BPF_SUB in addition to BPF_ADD
- Change overflow check from val > (u32)S32_MAX to checking if val fits
  in s32 range: (s64)val != (s64)(s32)val
- For BPF_SUB, negate the offset with a guard against S32_MIN overflow
- Keep !alu32 restriction as 32-bit ALU has known issues with upper bits

Signed-off-by: Puranjay Mohan <puranjay@kernel.org>
---
 kernel/bpf/verifier.c | 26 +++++++++++++++++++-------
 1 file changed, 19 insertions(+), 7 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 53635ea2e41b..5eca33e02d6e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -15710,22 +15710,34 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
 	 * update r1 after 'if' condition.
 	 */
 	if (env->bpf_capable &&
-	    BPF_OP(insn->code) == BPF_ADD && !alu32 &&
-	    dst_reg->id && is_reg_const(src_reg, false)) {
+	    (BPF_OP(insn->code) == BPF_ADD || BPF_OP(insn->code) == BPF_SUB) &&
+	    !alu32 && dst_reg->id && is_reg_const(src_reg, false)) {
 		u64 val = reg_const_value(src_reg, false);
+		s32 off;
 
-		if ((dst_reg->id & BPF_ADD_CONST) ||
-		    /* prevent overflow in sync_linked_regs() later */
-		    val > (u32)S32_MAX) {
+		if ((s64)val != (s64)(s32)val)
+			goto clear_id;
+
+		off = (s32)val;
+
+		if (BPF_OP(insn->code) == BPF_SUB) {
+			/* Negating S32_MIN would overflow */
+			if (off == S32_MIN)
+				goto clear_id;
+			off = -off;
+		}
+
+		if (dst_reg->id & BPF_ADD_CONST) {
 			/*
 			 * If the register already went through rX += val
 			 * we cannot accumulate another val into rx->off.
 			 */
+clear_id:
 			dst_reg->off = 0;
 			dst_reg->id = 0;
 		} else {
 			dst_reg->id |= BPF_ADD_CONST;
-			dst_reg->off = val;
+			dst_reg->off = off;
 		}
 	} else {
 		/*
@@ -16821,7 +16833,7 @@ static void sync_linked_regs(struct bpf_verifier_state *vstate, struct bpf_reg_s
 			s32 saved_off = reg->off;
 
 			fake_reg.type = SCALAR_VALUE;
-			__mark_reg_known(&fake_reg, (s32)reg->off - (s32)known_reg->off);
+			__mark_reg_known(&fake_reg, (s64)reg->off - (s64)known_reg->off);
 
 			/* reg = known_reg; reg += delta */
 			copy_register_state(reg, known_reg);
-- 
2.47.3