bpf: Improve linked register tracking
Subsystems (4)
cover bpf: Improve linked register tracking
This series extends the BPF verifier's linked register tracking to handle negative offsets and BPF_SUB operations, enabling better bounds propagation for common arithmetic patterns.
The verifier previously only tracked positive constant deltas between linked registers using BPF_ADD. This meant patterns using negative offsets or subtraction couldn't benefit from bounds propagation:
r1 = r0
r1 += -4
if r1 s>= 0 goto ... // r1 >= 0 implies r0 >= 4
// verifier couldn't propagate bounds back to r0
Patch 1 extends scalar_min_max_add() to:
- Accept BPF_SUB in addition to BPF_ADD (treating r1 -= 4 as r1 += -4)
- Change the overflow check to properly validate s32 range
- Add a guard against S32_MIN negation overflow
- Retain the !alu32 restriction due to known issues with 32-bit ALU upper bits
Patches 2-3 update the selftests:
- Patch 2 adds comprehensive tests covering success cases (negative offsets, BPF_SUB), failure cases (32-bit ALU, double ADD), and large delta edge cases (S32_MIN/S32_MAX offsets)
- Patch 3 updates an existing test's expected output to reflect the new tracking behavior
Puranjay Mohan (3):
bpf: Support negative offsets and BPF_SUB for linked register tracking selftests/bpf: Add tests for linked register tracking with negative
offsets
selftests/bpf: Update expected output for sub64_partial_overflow test
kernel/bpf/verifier.c | 26 ++- .../selftests/bpf/progs/verifier_bounds.c | 2 +- .../bpf/progs/verifier_linked_scalars.c | 213 ++++++++++++++++++ 3 files changed, 233 insertions(+), 8 deletions(-)
base-commit: 2175ccfb93fd91d0ece74684eb7ab9443de806ec
Signature · 1 line
2.47.3
PATCH 1/3 bpf: Support negative offsets and BPF_SUB for linked register tracking
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
--- kernel/bpf/verifier.c | 26 +++++++++++++++++++------- 1 file changed, 19 insertions(+), 7 deletions(-)
kernel/bpf/verifier.c +19 -7
@@ -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_ss32 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);
Signature · 1 line
2.47.3
Re: [PATCH bpf-next 1/3] bpf: Support negative offsets and BPF_SUB for linked register tracking
Quoted 16 lines · Puranjay Mohan
Extend the linked register tracking to support:
1. Negative offsets via
BPF_ADD(e.g., r1 += -4)
2.BPF_SUBoperations (e.g., r1 -= 4), which is treated as r1 += -4Previously, 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 r0With this change, the verifier can now track negative deltas in
reg->off(which is already s32), enabling bound propagation for the above pattern.
Quoted 6 lines
The changes include:
- AcceptBPF_SUBin addition toBPF_ADD
- Change overflow check from val > (u32)S32_MAX to checking if val fits in s32 range: (s64)val != (s64)(s32)val
- ForBPF_SUB, negate the offset with a guard againstS32_MINoverflow
- Keep !alu32 restriction as 32-bit ALU has known issues with upper bits
This is because we don't know if other registers with the same id have their upper 32-bits as zeroes, right?
I'm curious how often we hit this limitation in practice, I would expect code operating on 32-bit values to hit this from time to time. E.g. see example in [1] (but it is mitigated by an LLVM workaround).
Quoted 3 lines
Signed-off-by Puranjay Mohan <[email protected]>---
[...]
Eduard Zingerman
maintainerRe: [PATCH bpf-next 1/3] bpf: Support negative offsets and BPF_SUB for linked register tracking
Quoted 24 lines · Eduard Zingerman
Quoted 16 lines · Puranjay Mohan
Extend the linked register tracking to support:
1. Negative offsets via
BPF_ADD(e.g., r1 += -4)
2.BPF_SUBoperations (e.g., r1 -= 4), which is treated as r1 += -4Previously, 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 r0With this change, the verifier can now track negative deltas in
reg->off(which is already s32), enabling bound propagation for the above pattern.Quoted 6 lines
The changes include:
- AcceptBPF_SUBin addition toBPF_ADD
- Change overflow check from val > (u32)S32_MAX to checking if val fits in s32 range: (s64)val != (s64)(s32)val
- ForBPF_SUB, negate the offset with a guard againstS32_MINoverflow
- Keep !alu32 restriction as 32-bit ALU has known issues with upper bits
Quoted 2 lines
This is because we don't know if other registers with the same id have their upper 32-bits as zeroes, right?
Nah, we do know if their upper halves are zeroes or not, registers with same id are identical up to the ->off field. So, it appears that this restriction can be partially lifted if we check if dst_reg upper half is zero before operation. Wdyt?
Quoted 13 lines
I'm curious how often we hit this limitation in practice, I would expect code operating on 32-bit values to hit this from time to time. E.g. see example in [1] (but it is mitigated by an LLVM workaround).
Quoted 3 lines
Signed-off-by Puranjay Mohan <[email protected]>---
Acked-by Eduard Zingerman <[email protected]>[...]
Re: [PATCH bpf-next 1/3] bpf: Support negative offsets and BPF_SUB for linked register tracking
Quoted 26 lines · Eduard Zingerman
Quoted 24 lines · Eduard Zingerman
Quoted 22 lines · Puranjay Mohan
Extend the linked register tracking to support:
1. Negative offsets via
BPF_ADD(e.g., r1 += -4)
2.BPF_SUBoperations (e.g., r1 -= 4), which is treated as r1 += -4Previously, 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 r0With 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:
- AcceptBPF_SUBin addition toBPF_ADD
- Change overflow check from val > (u32)S32_MAX to checking if val fits in s32 range: (s64)val != (s64)(s32)val
- ForBPF_SUB, negate the offset with a guard againstS32_MINoverflow
- Keep !alu32 restriction as 32-bit ALU has known issues with upper bits
Quoted 8 lines
Quoted 2 lines
This is because we don't know if other registers with the same id have their upper 32-bits as zeroes, right?
Nah, we do know if their upper halves are zeroes or not, registers with same id are identical up to the ->off field. So, it appears that this restriction can be partially lifted if we check if
dst_regupper half is zero before operation. Wdyt?
Let's figure out how to support w-registers too.
Hao Sun's 1st category:
https://lore.kernel.org/bpf/CACkBjsauBbmKRAgEhOujtpGBeAWksar9yS+0hk1i9pLYwtQN3A@mail.gmail.com/
is exactly this missing feature.
Instead of adding them as failures in patch 2, let's make them successes.
pw-bot: cr
PATCH 2/3 selftests/bpf: Add tests for linked register tracking with negative offsets
In reply to Puranjay MohanAdd tests for linked register tracking with negative offsets and BPF_SUB:
Success cases (64-bit ALU, tracking works):
- scalars_neg: r1 += -4 with signed comparison
- scalars_neg_sub: r1 -= 4 with signed comparison
- scalars_pos: r1 += 4 with unsigned comparison
- scalars_sub_neg_imm: r1 -= -4 (equivalent to r1 += 4)
Failure cases (tracking disabled, documents limitations):
- scalars_neg_alu32_add: 32-bit ADD not tracked
- scalars_neg_alu32_sub: 32-bit SUB not tracked
- scalars_double_add: Double ADD clears ID
Large delta tests (verifies 64-bit arithmetic in sync_linked_regs):
- scalars_sync_delta_overflow: S32_MIN offset
- scalars_sync_delta_overflow_large_range: S32_MAX offset
--- .../bpf/progs/verifier_linked_scalars.c | 213 ++++++++++++++++++ 1 file changed, 213 insertions(+)
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +213 -0
@@ -31,4 +31,217 @@ l1: \ " ::: __clobber_all); } +SEC("socket") +__description("scalars: linked scalars with negative offset") +__success +__naked void scalars_neg (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r1 += -4; \ +if r1 s< 0 goto l2; \ +if r0 != 0 goto l2; \ +r0 /= 0; \ +l2: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* Same test but using BPF_SUB instead of BPF_ADD with negative immediate */ +SEC("socket") +__description("scalars: linked scalars with SUB") +__success +__naked void scalars_neg_sub (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r1 -= 4; \ +if r1 s< 0 goto l2_sub; \ +if r0 != 0 goto l2_sub; \ +r0 /= 0; \ +l2_sub: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* 32-bit ALU: linked scalar tracking not supported, ID cleared */ +SEC("socket") +__description("scalars: linked scalars 32-bit ADD not tracked") +__failure +__msg("div by zero") +__naked void scalars_neg_alu32_add(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w0 &= 0xff; \ +w1 = w0; \ +w1 += -4; \ +if w1 s< 0 goto l2_alu32_add; \ +if w0 != 0 goto l2_alu32_add; \ +r0 /= 0; \ +l2_alu32_add: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* 32-bit ALU: linked scalar tracking not supported, ID cleared */ +SEC("socket") +__description("scalars: linked scalars 32-bit SUB not tracked") +__failure +__msg("div by zero") +__naked void scalars_neg_alu32_sub(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w0 &= 0xff; \ +w1 = w0; \ +w1 -= 4; \ +if w1 s< 0 goto l2_alu32_sub; \ +if w0 != 0 goto l2_alu32_sub; \ +r0 /= 0; \ +l2_alu32_sub: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* Positive offset: r1 = r0 + 4, then if r1 >= 6, r0 >= 2, so r0 != 0 */ +SEC("socket") +__description("scalars: linked scalars positive offset") +__success +__naked void scalars_pos (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r1 += 4; \ +if r1 < 6 goto l2_pos; \ +if r0 != 0 goto l2_pos; \ +r0 /= 0; \ +l2_pos: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* SUB with negative immediate: r1 -= -4 is equivalent to r1 += 4 */ +SEC("socket") +__description("scalars: linked scalars SUB negative immediate") +__success +__naked void scalars_sub_neg_imm (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r1 -= -4; \ +if r1 < 6 goto l2_sub_neg; \ +if r0 != 0 goto l2_sub_neg; \ +r0 /= 0; \ +l2_sub_neg: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* Double ADD clears the ID (can't accumulate offsets) */ +SEC("socket") +__description("scalars: linked scalars double ADD clears ID") +__failure +__msg("div by zero") +__naked void scalars_double_add(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r1 += 2; \ +r1 += 2; \ +if r1 < 6 goto l2_double; \ +if r0 != 0 goto l2_double; \ +r0 /= 0; \ +l2_double: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* Test that sync_linked_regs() correctly handles large offset differences. +* r1.off = S32_MIN, r2.off = 1, delta = S32_MIN - 1 requires 64-bit math. +*/ +SEC("socket") +__description("scalars: linked regs sync with large delta (S32_MIN offset)") +__success +__naked void scalars_sync_delta_overflow (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r2 = r0; \ +r1 += %[s32_min]; \ +r2 += 1; \ +if r2 s< 100 goto l2_overflow; \ +if r1 s< 0 goto l2_overflow; \ +r0 /= 0; \ +l2_overflow: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32), + [s32_min]"i"((int)(-2147483647 - 1)) + : __clobber_all); +} + +/* +* Another large delta case: r1.off = S32_MAX, r2.off = -1. +* delta = S32_MAX - (-1) = S32_MAX + 1 requires 64-bit math. +*/ +SEC("socket") +__description("scalars: linked regs sync with large delta (S32_MAX offset)") +__success +__naked void scalars_sync_delta_overflow_large_range (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r2 = r0; \ +r1 += %[s32_max]; \ +r2 += -1; \ +if r2 s< 0 goto l2_large; \ +if r1 s>= 0 goto l2_large; \ +r0 /= 0; \ +l2_large: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32), + [s32_max]"i"((int)2147483647) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.47.3
Eduard Zingerman
maintainerRe: [PATCH bpf-next 2/3] selftests/bpf: Add tests for linked register tracking with negative offsets
Quoted 27 lines · Puranjay Mohan
Add tests for linked register tracking with negative offsets and
BPF_SUB:Success cases (64-bit ALU, tracking works):
-scalars_neg: r1 += -4 with signed comparison
-scalars_neg_sub: r1 -= 4 with signed comparison
-scalars_pos: r1 += 4 with unsigned comparison
-scalars_sub_neg_imm: r1 -= -4 (equivalent to r1 += 4)Failure cases (tracking disabled, documents limitations):
-scalars_neg_alu32_add: 32-bit ADD not tracked
-scalars_neg_alu32_sub: 32-bit SUB not tracked
-scalars_double_add: Double ADD clears IDLarge delta tests (verifies 64-bit arithmetic in
sync_linked_regs):
-scalars_sync_delta_overflow:S32_MINoffset
-scalars_sync_delta_overflow_large_range:S32_MAXoffsetSigned-off-by Puranjay Mohan <[email protected]>--- .../bpf/progs/verifier_linked_scalars.c | 213 ++++++++++++++++++ 1 file changed, 213 insertions(+)tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l1: \ · line 35
Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +2
-0@@ -31,4 +31,217 @@ l1: \ " ::: __clobber_all); } +SEC("socket") +__description ("scalars: linked scalars with negative offset" )
Nit: I think that __description tag should be avoided in the new code.
w/o this tag the test case could be executed as follows:
./test_progs -t verifier_linked_scalars/scalars_reg
with this tag the test case should be executed as:
./test_progs -t "verifier_linked_scalars/scalars: linked scalars with negative offset"
and I'm not sure test_progs handles spaces properly (even if it does, the invocation is inconvenient). So, I'd just put the description in the comments.
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l1: \ · line 44
Quoted 9 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +9
-0+__success +__naked void scalars_neg(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r0 &= 0xff; \ + r1 = r0; \ + r1 += -4; \ + if r1 s< 0 goto l2; \
^^
This is a file-global label.
It's better to use goto 1f ...; 1: <code> in such cases, or a special %= substitution. There are multiple examples for both in the test cases. See [1] and [2].
[1] https://sourceware.org/binutils/docs-2.36/as.html#Symbol-Names (local labels)
[2] https://gcc.gnu.org/onlinedocs/gcc-14.1.0/gcc/Extended-Asm.html#Special-format-strings
Quoted 161 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +161
-0+ if r0 != 0 goto l2; \ + r0 /=0 ; \ +l2: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* Same test but using BPF_SUB instead of BPF_ADD with negative immediate */ +SEC("socket") +__description("scalars: linked scalars with SUB") +__success +__naked void scalars_neg_sub (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r1 -= 4; \ +if r1 s< 0 goto l2_sub; \ +if r0 != 0 goto l2_sub; \ +r0 /= 0; \ +l2_sub: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* 32-bit ALU: linked scalar tracking not supported, ID cleared */ +SEC("socket") +__description("scalars: linked scalars 32-bit ADD not tracked") +__failure +__msg("div by zero") +__naked void scalars_neg_alu32_add(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w0 &= 0xff; \ +w1 = w0; \ +w1 += -4; \ +if w1 s< 0 goto l2_alu32_add; \ +if w0 != 0 goto l2_alu32_add; \ +r0 /= 0; \ +l2_alu32_add: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* 32-bit ALU: linked scalar tracking not supported, ID cleared */ +SEC("socket") +__description("scalars: linked scalars 32-bit SUB not tracked") +__failure +__msg("div by zero") +__naked void scalars_neg_alu32_sub(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w0 &= 0xff; \ +w1 = w0; \ +w1 -= 4; \ +if w1 s< 0 goto l2_alu32_sub; \ +if w0 != 0 goto l2_alu32_sub; \ +r0 /= 0; \ +l2_alu32_sub: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* Positive offset: r1 = r0 + 4, then if r1 >= 6, r0 >= 2, so r0 != 0 */ +SEC("socket") +__description("scalars: linked scalars positive offset") +__success +__naked void scalars_pos (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r1 += 4; \ +if r1 < 6 goto l2_pos; \ +if r0 != 0 goto l2_pos; \ +r0 /= 0; \ +l2_pos: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* SUB with negative immediate: r1 -= -4 is equivalent to r1 += 4 */ +SEC("socket") +__description("scalars: linked scalars SUB negative immediate") +__success +__naked void scalars_sub_neg_imm (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r1 -= -4; \ +if r1 < 6 goto l2_sub_neg; \ +if r0 != 0 goto l2_sub_neg; \ +r0 /= 0; \ +l2_sub_neg: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* Double ADD clears the ID (can't accumulate offsets) */ +SEC("socket") +__description("scalars: linked scalars double ADD clears ID") +__failure +__msg("div by zero") +__naked void scalars_double_add(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r1 += 2; \ +r1 += 2; \ +if r1 < 6 goto l2_double; \ +if r0 != 0 goto l2_double; \ +r0 /= 0; \ +l2_double: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* Test that sync_linked_regs() correctly handles large offset differences. +* r1.off = S32_MIN, r2.off = 1, delta = S32_MIN - 1 requires 64-bit math. +*/ +SEC("socket") +__description("scalars: linked regs sync with large delta (S32_MIN offset)") +__success +__naked void scalars_sync_delta_overflow (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r0 &= 0xff; \ + r1 = r0; \ + r2 = r0; \ + r1 += %[s32_min]; \
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l1: \ · line 215
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+ r2 +=1 ; \ + if r2 s< 100 goto l2_overflow; \ + if r1 s< 0 goto l2_overflow; \ + r0 /=0 ; \ +l2_overflow: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32), + [s32_min]"i"((int)(-2147483647 - 1))
^^^^^^^^^^^
Nit: use INT_MIN?
Quoted 32 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +31
-0+ : __clobber_all); +} + +/* +* Another large delta case: r1.off = S32_MAX, r2.off = -1. +* delta = S32_MAX - (-1) = S32_MAX + 1 requires 64-bit math. +*/ +SEC("socket") +__description("scalars: linked regs sync with large delta (S32_MAX offset)") +__success +__naked void scalars_sync_delta_overflow_large_range (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r0 &= 0xff; \ +r1 = r0; \ +r2 = r0; \ +r1 += %[s32_max]; \ +r2 += -1; \ +if r2 s< 0 goto l2_large; \ +if r1 s>= 0 goto l2_large; \ +r0 /= 0; \ +l2_large: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32), + [s32_max]"i"((int)2147483647) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
__description(). Was: [PATCH bpf-next 2/3] selftests/bpf: Add tests for linked register tracking with negative offsets
Quoted 38 lines · Eduard Zingerman
Quoted 27 lines · Puranjay Mohan
Add tests for linked register tracking with negative offsets and
BPF_SUB:Success cases (64-bit ALU, tracking works):
-scalars_neg: r1 += -4 with signed comparison
-scalars_neg_sub: r1 -= 4 with signed comparison
-scalars_pos: r1 += 4 with unsigned comparison
-scalars_sub_neg_imm: r1 -= -4 (equivalent to r1 += 4)Failure cases (tracking disabled, documents limitations):
-scalars_neg_alu32_add: 32-bit ADD not tracked
-scalars_neg_alu32_sub: 32-bit SUB not tracked
-scalars_double_add: Double ADD clears IDLarge delta tests (verifies 64-bit arithmetic in
sync_linked_regs):
-scalars_sync_delta_overflow:S32_MINoffset
-scalars_sync_delta_overflow_large_range:S32_MAXoffsetSigned-off-by Puranjay Mohan <[email protected]>--- .../bpf/progs/verifier_linked_scalars.c | 213 ++++++++++++++++++ 1 file changed, 213 insertions(+)tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +0
-0tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l1: \ · line 35
Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +2
-0@@ -31,4 +31,217 @@ l1: \ " ::: __clobber_all); } +SEC("socket") +__description ("scalars: linked scalars with negative offset" )Nit: I think that
__descriptiontag should be avoided in the new code.
w/o this tag the test case could be executed as follows:
Quoted 8 lines
./test_progs -t verifier_linked_scalars/scalars_reg
with this tag the test case should be executed as:
./test_progs -t "verifier_linked_scalars/scalars: linked scalars with negative offset"
and I'm not sure
test_progshandles spaces properly (even if it does, the invocation is inconvenient). So, I'd just put the description in the comments.
Going back to this. I think 'description' tag is useful and it makes test_progs output more human readable, but we should do something about test_loader.c
if (!description)
description = spec->prog_name;since specifying a full description is indeed inconvenient.
Maybe test_progs should print both: prog_name and description.
Eduard Zingerman
maintainerRe: [PATCH bpf-next 2/3] selftests/bpf: Add tests for linked register tracking with negative offsets
In reply to Puranjay MohanOn Wed, 2026-01-07 at 12:39 -0800, Puranjay Mohan wrote:
[...]
Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +7
-0+/* +* Test that sync_linked_regs() correctly handles large offset differences. +* r1.off = S32_MIN, r2.off = 1, delta = S32_MIN - 1 requires 64-bit math. +*/ +SEC("socket") +__description ("scalars: linked regs sync with large delta (S32_MIN offset)" ) +__success
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l1: \ · line 207
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+__naked void scalars_sync_delta_overflow (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r0 &= 0xff; \ + r1 = r0; \ + r2 = r0; \ + r1 += %[s32_min]; \ + r2 += 1; \ + if r2 s< 100 goto l2_overflow; \
If I remove the above check the test case still passes.
What is the purpose of the test?
If the purpose is to check that S32_MIN can be used as delta for BPF_ADD operations, then constants in the second comparison should be picked in a way for comparison to be unpredictable w/o first comparison.
Quoted 19 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +18
-0+ if r1 s< 0 goto l2_overflow; \ + r0 /=0 ; \ +l2_overflow: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32), + [s32_min]"i"((int)(-2147483647 - 1)) + : __clobber_all); +} + +/* +* Another large delta case: r1.off = S32_MAX, r2.off = -1. +* delta = S32_MAX - (-1) = S32_MAX + 1 requires 64-bit math. +*/ +SEC("socket") +__description ("scalars: linked regs sync with large delta (S32_MAX offset)" ) +__success
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l1: \ · line 235
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+__naked void scalars_sync_delta_overflow_large_range (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r0 &= 0xff; \ + r1 = r0; \ + r2 = r0; \ + r1 += %[s32_max]; \ + r2 += -1; \ + if r2 s< 0 goto l2_large; \
Same issue here.
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l1: \ · line 243
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +8
-0+ if r1 s>= 0 goto l2_large; \ + r0 /=0 ; \ +l2_large: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32), + [s32_max]"i"((int)2147483647)
^^^^^^^^^^^^^^^
Out of curiosity, did you write this by hand or was it generated?
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +3
-0+ : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Re: [PATCH bpf-next 2/3] selftests/bpf: Add tests for linked register tracking with negative offsets
Quoted 69 lines · Eduard Zingerman
On Wed, 2026-01-07 at 12:39 -0800, Puranjay Mohan wrote:
[...]
Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +7
-0+/* +* Test that sync_linked_regs() correctly handles large offset differences. +* r1.off = S32_MIN, r2.off = 1, delta = S32_MIN - 1 requires 64-bit math. +*/ +SEC("socket") +__description ("scalars: linked regs sync with large delta (S32_MIN offset)" ) +__successtools/testing/selftests/bpf/progs/verifier_linked_scalars.c l1: \ · line 207
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+__naked void scalars_sync_delta_overflow (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r0 &= 0xff; \ + r1 = r0; \ + r2 = r0; \ + r1 += %[s32_min]; \ + r2 += 1; \ + if r2 s< 100 goto l2_overflow; \If I remove the above check the test case still passes.
What is the purpose of the test?
If the purpose is to check thatS32_MINcan be used as delta forBPF_ADDoperations, then constants in the second comparison should be picked in a way for comparison to be unpredictable w/o first comparison.Quoted 19 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +18
-0+ if r1 s< 0 goto l2_overflow; \ + r0 /=0 ; \ +l2_overflow: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32), + [s32_min]"i"((int)(-2147483647 - 1)) + : __clobber_all); +} + +/* +* Another large delta case: r1.off = S32_MAX, r2.off = -1. +* delta = S32_MAX - (-1) = S32_MAX + 1 requires 64-bit math. +*/ +SEC("socket") +__description ("scalars: linked regs sync with large delta (S32_MAX offset)" ) +__successtools/testing/selftests/bpf/progs/verifier_linked_scalars.c l1: \ · line 235
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +10
-0+__naked void scalars_sync_delta_overflow_large_range (void ) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r0 &= 0xff; \ + r1 = r0; \ + r2 = r0; \ + r1 += %[s32_max]; \ + r2 += -1; \ + if r2 s< 0 goto l2_large; \Same issue here.
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c l1: \ · line 243
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +8
-0+ if r1 s>= 0 goto l2_large; \ + r0 /=0 ; \ +l2_large: \ + r0 =0 ; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32), + [s32_max]"i"((int)2147483647)
Quoted 2 lines
^^^^^^^^^^^^^^^Out of curiosity, did you write this by hand or was it generated?
So, these two are generated by claude and the we want to test if the line __mark_reg_known(&fake_reg, (s64)reg->off - (s64)known_reg->off); in sync_linked_regs() working correctly. Before patch 1 it looked like __mark_reg_known(&fake_reg, (s32)reg->off - (s32)known_reg->off) and it would break for the pair of values (S32_MAX, -1) and (S32_MIN, 1).
So, this test fails before the change from (s32) to (s64) in sync_linked_regs, if I remove the lines that you are referring to (if r2 s< 0 goto l2_large;, etc.) then it passes even with (s32).
So, I think this test is checking the right things.
PATCH 3/3 selftests/bpf: Update expected output for sub64_partial_overflow test
In reply to Puranjay MohanUpdate the expected regex pattern for the sub64_partial_overflow test. With BPF_SUB now supporting linked register tracking, the verifier output shows R3=scalar(id=1-1) instead of R3=scalar() because r3 is now tracked as linked to r0 with an offset of -1.
--- tools/testing/selftests/bpf/progs/verifier_bounds.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
tools/testing/selftests/bpf/progs/verifier_bounds.c +1 -1
@@ -1477,7 +1477,7 @@ __naked void sub64_full_overflow(void) SEC("socket") __description("64-bit subtraction, partial overflow, result in unbounded reg") __success __log_level(2) -__msg("3: (1f) r3 -= r2 {{.*}} R3=scalar()") +__msg("3: (1f) r3 -= r2 {{.*}} R3=scalar(id=1-1)") __retval(0)__naked void sub64_partial_overflow (void ) {
Signature · 1 line
2.47.3
Eduard Zingerman
maintainerRe: [PATCH bpf-next 3/3] selftests/bpf: Update expected output for sub64_partial_overflow test
Quoted 7 lines · Puranjay Mohan
Update the expected regex pattern for the
sub64_partial_overflowtest. WithBPF_SUBnow supporting linked register tracking, the verifier output shows R3=scalar(id=1-1) instead of R3=scalar() because r3 is now tracked as linked to r0 with an offset of -1.Signed-off-by Puranjay Mohan <[email protected]>---
W/o this patch selftests fail after patch #1, right? We usually keep such test fixes in verifier patches. Such that selftests are passing after each commit, This makes any potential git bisect simpler.
Quoted 16 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)tools/testing/selftests/bpf/progs/verifier_bounds.c +1
-1@@ -1477,7 +1477,7 @@ __naked void sub64_full_overflow(void) SEC("socket") __description("64-bit subtraction, partial overflow, result in unbounded reg") __success __log_level(2) -__msg("3: (1f) r3 -= r2 {{.*}} R3=scalar()") +__msg("3: (1f) r3 -= r2 {{.*}} R3=scalar(id=1-1)") __retval(0)__naked void sub64_partial_overflow (void ) {
Re: [PATCH bpf-next 3/3] selftests/bpf: Update expected output for sub64_partial_overflow test
Quoted 7 lines · Eduard Zingerman
Quoted 5 lines · Puranjay Mohan
Update the expected regex pattern for the
sub64_partial_overflowtest. WithBPF_SUBnow supporting linked register tracking, the verifier output shows R3=scalar(id=1-1) instead of R3=scalar() because r3 is now tracked as linked to r0 with an offset of -1.
Quoted 7 lines
Quoted 2 lines
Signed-off-by Puranjay Mohan <[email protected]>---
W/o this patch selftests fail after patch #1, right? We usually keep such test fixes in verifier patches. Such that selftests are passing after each commit, This makes any potential git bisect simpler.
Yes, I will merge this with the first patch in v2.
Quoted 17 lines
Quoted 17 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)tools/testing/selftests/bpf/progs/verifier_bounds.c +1
-1@@ -1477,7 +1477,7 @@ __naked void sub64_full_overflow(void) SEC("socket") __description("64-bit subtraction, partial overflow, result in unbounded reg") __success __log_level(2) -__msg("3: (1f) r3 -= r2 {{.*}} R3=scalar()") +__msg("3: (1f) r3 -= r2 {{.*}} R3=scalar(id=1-1)") __retval(0)__naked void sub64_partial_overflow (void ) {