bpf: Do not include stack ptr register in precision backtracking bookkeeping
Subsystems (5)
Yonghong Song
reviewerPATCH v5 1/2 bpf: Do not include stack ptr register in precision backtracking bookkeeping
Yi Lai reported an issue ([1]) where the following warning appears in kernel dmesg:
[ 60.643604] verifier backtracking bug
[ 60.643635] WARNING: CPU: 10 PID: 2315 at kernel/bpf/verifier.c:4302 __mark_chain_precision+0x3a6c/0x3e10
[ 60.648428] Modules linked in: bpf_testmod(OE)
[ 60.650471] CPU: 10 UID: 0 PID: 2315 Comm: test_progs Tainted: G OE 6.15.0-rc4-gef11287f8289-dirty #327 PREEMPT(full)
[ 60.654385] Tainted: [O]=OOT_MODULE, [E]=UNSIGNED_MODULE
[ 60.656682] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.14.0-0-g155821a1990b-prebuilt.qemu.org 04/01/2014
[ 60.660475] RIP: 0010:__mark_chain_precision+0x3a6c/0x3e10
[ 60.662814] Code: 5a 30 84 89 ea e8 c4 d9 01 00 80 3d 3e 7d d8 04 00 0f 85 60 fa ff ff c6 05 31 7d d8 04
01 48 c7 c7 00 58 30 84 e8 c4 06 a5 ff <0f> 0b e9 46 fa ff ff 48 ...
[ 60.668720] RSP: 0018:ffff888116cc7298 EFLAGS: 00010246
[ 60.671075] RAX: 54d70e82dfd31900 RBX: ffff888115b65e20 RCX: 0000000000000000
[ 60.673659] RDX: 0000000000000001 RSI: 0000000000000004 RDI: 00000000ffffffff
[ 60.676241] RBP: 0000000000000400 R08: ffff8881f6f23bd3 R09: 1ffff1103ede477a
[ 60.678787] R10: dffffc0000000000 R11: ffffed103ede477b R12: ffff888115b60ae8
[ 60.681420] R13: 1ffff11022b6cbc4 R14: 00000000fffffff2 R15: 0000000000000001
[ 60.684030] FS: 00007fc2aedd80c0(0000) GS:ffff88826fa8a000(0000) knlGS:0000000000000000
[ 60.686837] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 60.689027] CR2: 000056325369e000 CR3: 000000011088b002 CR4: 0000000000370ef0
[ 60.691623] Call Trace:
[ 60.692821] <TASK>
[ 60.693960] ? __pfx_verbose+0x10/0x10
[ 60.695656] ? __pfx_disasm_kfunc_name+0x10/0x10
[ 60.697495] check_cond_jmp_op+0x16f7/0x39b0
[ 60.699237] do_check+0x58fa/0xab10
...Further analysis shows the warning is at line 4302 as below:
4294 /* static subprog call instruction, which
4295 * means that we are exiting current subprog,
4296 * so only r1-r5 could be still requested as
4297 * precise, r0 and r6-r10 or any stack slot in
4298 * the current frame should be zero by now
4299 */
4300 if (bt_reg_mask(bt) & ~BPF_REGMASK_ARGS) {
4301 verbose(env, "BUG regs %x\n", bt_reg_mask(bt));
4302 WARN_ONCE(1, "verifier backtracking bug");
4303 return -EFAULT;4304 }
With the below test (also in the next patch):
__used __naked static void __bpf_jmp_r10(void)
{
asm volatile (
"r2 = 2314885393468386424 ll;"
"goto +0;"
"if r2 <= r10 goto +3;"
"if r1 >= -1835016 goto +0;"
"if r2 <= 8 goto +0;"
"if r3 <= 0 goto +0;"
"exit;"
::: __clobber_all);}
SEC("?raw_tp")
__naked void bpf_jmp_r10(void)
{
asm volatile (
"r3 = 0 ll;"
"call __bpf_jmp_r10;"
"r0 = 0;"
"exit;"
::: __clobber_all);}
The following is the verifier failure log:
0: (18) r3 = 0x0 ; R3_w=0
2: (85) call pc+2
caller:
R10=fp0
callee:
frame1: R1=ctx() R3_w=0 R10=fp0
5: frame1: R1=ctx() R3_w=0 R10=fp0
; asm volatile (" \ @ verifier_precision.c:184
5: (18) r2 = 0x20202000256c6c78 ; frame1: R2_w=0x20202000256c6c78
7: (05) goto pc+0
8: (bd) if r2 <= r10 goto pc+3 ; frame1: R2_w=0x20202000256c6c78 R10=fp0
9: (35) if r1 >= 0xffe3fff8 goto pc+0 ; frame1: R1=ctx()
10: (b5) if r2 <= 0x8 goto pc+0
mark_precise: frame1: last_idx 10 first_idx 0 subseq_idx -1
mark_precise: frame1: regs=r2 stack= before 9: (35) if r1 >= 0xffe3fff8 goto pc+0
mark_precise: frame1: regs=r2 stack= before 8: (bd) if r2 <= r10 goto pc+3
mark_precise: frame1: regs=r2,r10 stack= before 7: (05) goto pc+0
mark_precise: frame1: regs=r2,r10 stack= before 5: (18) r2 = 0x20202000256c6c78
mark_precise: frame1: regs=r10 stack= before 2: (85) call pc+2
BUG regs 400
The main failure reason is due to r10 in precision backtracking bookkeeping. Actually r10 is always precise and there is no need to add it for the precision backtracking bookkeeping.
One way to fix the issue is to prevent bt_set_reg() if any src/dst reg is r10. Andrii suggested to go with push_insn_history() approach to avoid explicitly checking r10 in backtrack_insn().
This patch added push_insn_history() support for cond_jmp like 'rX <op> rY' operations. In check_cond_jmp_op(), if any of rX or rY is a stack pointer, push_insn_history() will record such information, and later backtrack_insn() will do bt_set_reg() properly for those register(s).
[1] https://lore.kernel.org/bpf/Z%2F8q3xzpU59CIYQE@ly-workstation/
Reported by: Yi Lai <[email protected]>
--- include/linux/bpf_verifier.h | 12 ++++++++---- kernel/bpf/verifier.c | 18 ++++++++++++++++-- 2 files changed, 24 insertions(+), 6 deletions(-)
Changelogs:
v4 -> v5:
- v4: https://lore.kernel.org/bpf/[email protected]/
- Simplify implementation in backtrack_insn() and check_cond_jmp_op().
v3 -> v4:
- v3: https://lore.kernel.org/bpf/[email protected]/
- Fix an issue in push_cond_jmp_history(). Previously, '!src_reg' was used to check whether insn is 'dreg <op> imm' or not. But actually '!src_reg' is always non-NULL. The new fix is using insn directly.
v2 -> v3:
- v2: https://lore.kernel.org/bpf/[email protected]/
- In v2, I put sreg_flag/dreg_flag into bpf_insn_hist_entry and the information includes register numbers. This is not necessary as later insn in backtracking can retrieve the register number. So the new change is remove sreg_flag/dreg_flag from bpf_insn_hist_entry and add two bits in bpf_insn_hist_entry.flags to record whether the registers (cond jump like <reg> op < reg>) are stack pointer or not. Other changes depend on this data structure change.
v1 -> v2:
- v1: https://lore.kernel.org/bpf/[email protected]/
- In v1, we check r10 register explicitly in backtrack_insn() to decide whether we should do bt_set_reg() or not. Andrii suggested to do push_insn_history() instead. Whether a particular register (r10 in this case) should be available for backtracking or not is in check_cond_jmp_op(), and such information is pushed with push_insn_history(). Later in backtrack_insn(), such info is retrieved to decide whether precision marking should be done or not. This apporach can avoid explicit checking for r10 in backtrack_insn().
include/linux/bpf_verifier.h +8 -4
@@ -356,7 +356,11 @@ enum {INSN_F_SPI_MASK =0x3f ,/* 6 bits */ INSN_F_SPI_SHIFT =3 ,/* shifted 3 bits to the left */ -INSN_F_STACK_ACCESS =BIT (9 ),/* we need 10 bits total */ +INSN_F_STACK_ACCESS =BIT (9 ), + +INSN_F_DST_REG_STACK =BIT (10 ),/* dst_reg is PTR_TO_STACK */ +INSN_F_SRC_REG_STACK =BIT (11 ),/* src_reg is PTR_TO_STACK */ +/* total 12 bits are used now. */ };static_assert (INSN_F_FRAMENO_MASK +1 >=MAX_CALL_FRAMES );
@@ -365,9 +369,9 @@ static_assert(INSN_F_SPI_MASK + 1 >= MAX_BPF_STACK / 8);struct bpf_insn_hist_entry {u32 idx;/* insn idx can't be bigger than 1 million */ -u32 prev_idx :22 ; -/* special flags, e.g., whether insn is doing register stack spill/load */ -u32 flags :10 ; +u32 prev_idx :20 ; +/* special INSN_F_xxx flags */ +u32 flags :12 ;/* additional registers that need precision tracking when this * jump is backtracked, vector of six 10-bit records */
kernel/bpf/verifier.c +16 -2
@@ -4410,8 +4410,10 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,* before it would be equally necessary to * propagate it to dreg. */ -bt_set_reg (bt, dreg); -bt_set_reg (bt, sreg); +if (!hist || !(hist->flags &INSN_F_SRC_REG_STACK )) +bt_set_reg (bt, sreg); +if (!hist || !(hist->flags &INSN_F_DST_REG_STACK )) +bt_set_reg (bt, dreg); }else if (BPF_SRC (insn->code) ==BPF_K ) {/* dreg <cond> K * Only dreg still needs precision before
@@ -16407,6 +16409,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,struct bpf_reg_state *eq_branch_regs;struct linked_regs linked_regs = {};u8 opcode =BPF_OP (insn->code); +int insn_flags =0 ;bool is_jmp32;int pred =-1 ;int err;
@@ -16465,6 +16468,9 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, insn->src_reg);return -EACCES ; } + +if (src_reg->type ==PTR_TO_STACK ) + insn_flags |=INSN_F_SRC_REG_STACK ; }else {if (insn->src_reg !=BPF_REG_0 ) {verbose (env,"BPF_JMP/JMP32 uses reserved fields\n" );
@@ -16476,6 +16482,14 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,__mark_reg_known (src_reg, insn->imm); } +if (dst_reg->type ==PTR_TO_STACK ) + insn_flags |=INSN_F_DST_REG_STACK ; +if (insn_flags) { + err =push_insn_history (env, this_branch, insn_flags,0 ); +if (err) +return err; + } + is_jmp32 =BPF_CLASS (insn->code) ==BPF_JMP32 ; pred =is_branch_taken (dst_reg, src_reg, opcode, is_jmp32);if (pred >=0 ) {
Signature · 1 line
2.47.1
Yonghong Song
reviewerPATCH v5 2/2 selftests/bpf: Add tests with stack ptr register in conditional jmp
Add two tests:
- one test has 'rX <op> r10' where rX is not r10, and
- another test has 'rX <op> rY' where rX and rY are not r10 but there is an early insn 'rX = r10'.
Without previous verifier change, both tests will fail.
--- .../selftests/bpf/progs/verifier_precision.c | 53 +++++++++++++++++++ 1 file changed, 53 insertions(+)
tools/testing/selftests/bpf/progs/verifier_precision.c +53 -0
@@ -178,4 +178,57 @@ __naked int state_loop_first_last_equal(void) ); } +__used __naked static void __bpf_cond_op_r10 (void ) +{ + asmvolatile ( +"r2 = 2314885393468386424 ll;" +"goto +0;" +"if r2 <= r10 goto +3;" +"if r1 >= -1835016 goto +0;" +"if r2 <= 8 goto +0;" +"if r3 <= 0 goto +0;" +"exit;" + ::: __clobber_all); +} + +SEC("?raw_tp") +__success __log_level(2) +__msg("8: (bd) if r2 <= r10 goto pc+3") +__msg("9: (35) if r1 >= 0xffe3fff8 goto pc+0") +__msg("10: (b5) if r2 <= 0x8 goto pc+0") +__msg("mark_precise: frame1: last_idx 10 first_idx 0 subseq_idx -1") +__msg("mark_precise: frame1: regs=r2 stack= before 9: (35) if r1 >= 0xffe3fff8 goto pc+0") +__msg("mark_precise: frame1: regs=r2 stack= before 8: (bd) if r2 <= r10 goto pc+3") +__msg("mark_precise: frame1: regs=r2 stack= before 7: (05) goto pc+0") +__naked void bpf_cond_op_r10 (void ) +{ + asmvolatile ( +"r3 = 0 ll;" +"call __bpf_cond_op_r10;" +"r0 = 0;" +"exit;" + ::: __clobber_all); +} + +SEC("?raw_tp") +__success __log_level(2) +__msg("3: (bf) r3 = r10") +__msg("4: (bd) if r3 <= r2 goto pc+1") +__msg("5: (b5) if r2 <= 0x8 goto pc+2") +__msg("mark_precise: frame0: last_idx 5 first_idx 0 subseq_idx -1") +__msg("mark_precise: frame0: regs=r2 stack= before 4: (bd) if r3 <= r2 goto pc+1") +__msg("mark_precise: frame0: regs=r2 stack= before 3: (bf) r3 = r10") +__naked void bpf_cond_op_not_r10 (void ) +{ + asmvolatile ( +"r0 = 0;" +"r2 = 2314885393468386424 ll;" +"r3 = r10;" +"if r3 <= r2 goto +1;" +"if r2 <= 8 goto +2;" +"r0 = 2 ll;" +"exit;" + ::: __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.47.1
Re: [PATCH bpf-next v5 2/2] selftests/bpf: Add tests with stack ptr register in conditional jmp
Hi Andrii and Yonghong,
Quoted 11 lines · Yonghong Song
Add two tests:
- one test has 'rX <op> r10' where rX is not r10, and
- another test has 'rX <op> rY' where rX and rY are not r10 but there is an early insn 'rX = r10'.Without previous verifier change, both tests will fail.
Signed-off-by Yonghong Song <[email protected]>--- .../selftests/bpf/progs/verifier_precision.c | 53 +++++++++++++++++++ 1 file changed, 53 insertions(+)
I was looking this commit (5ffb537e416e) since it was a BPF selftest test for CVE-2025-38279, but upon looking I found that the commit differs from the patch, there is an extra hunk that changed kernel/bpf/verifier.c that wasn't found the Yonghong's original patch.
I suppose it was meant to be squashed into the previous commit e2d2115e56c4 "bpf: Do not include stack ptr register in precision backtracking bookkeeping"?
Since stable backports got only e2d2115e56c4, but not the 5ffb537e416e here with the extra change for kernel/bpf/verifier.c, I'd guess the backtracking logic in the stable kernel isn't correct at the moment, so I'll send 5ffb537e416e "selftests/bpf: Add tests with stack ptr register in conditional jmp" to stable as well. Let me know if that's not the right thing to do.
Shung-Hsi
kernel/bpf/verifier.c +5 -2
@@ -16456,6 +16456,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,if (src_reg->type ==PTR_TO_STACK ) insn_flags |=INSN_F_SRC_REG_STACK ; +if (dst_reg->type ==PTR_TO_STACK ) + insn_flags |=INSN_F_DST_REG_STACK ; }else {if (insn->src_reg !=BPF_REG_0 ) {verbose (env,"BPF_JMP/JMP32 uses reserved fields\n" );
@@ -16465,10 +16467,11 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,memset (src_reg,0 ,sizeof (*src_reg)); src_reg->type =SCALAR_VALUE ;__mark_reg_known (src_reg, insn->imm); + +if (dst_reg->type ==PTR_TO_STACK ) + insn_flags |=INSN_F_DST_REG_STACK ; } -if (dst_reg->type ==PTR_TO_STACK ) - insn_flags |=INSN_F_DST_REG_STACK ;if (insn_flags) { err =push_insn_history (env, this_branch, insn_flags,0 );if (err)
Quoted 1 line
tools/testing/selftests/bpf/progs/verifier_precision.c +0
-0
...
Yonghong Song
reviewerRe: [PATCH bpf-next v5 2/2] selftests/bpf: Add tests with stack ptr register in conditional jmp
Quoted 14 lines · Shung-Hsi Yu
Hi Andrii and Yonghong,
Quoted 11 lines · Yonghong Song
Add two tests:
- one test has 'rX <op> r10' where rX is not r10, and
- another test has 'rX <op> rY' where rX and rY are not r10 but there is an early insn 'rX = r10'.Without previous verifier change, both tests will fail.
Signed-off-by Yonghong Song <[email protected]>--- .../selftests/bpf/progs/verifier_precision.c | 53 +++++++++++++++++++ 1 file changed, 53 insertions(+)
Quoted 8 lines
I was looking this commit (
5ffb537e416e) since it was a BPF selftest test for CVE-2025-38279, but upon looking I found that the commit differs from the patch, there is an extra hunk that changedkernel/bpf/verifier.cthat wasn't found the Yonghong's original patch.I suppose it was meant to be squashed into the previous commit
e2d2115e56c4"bpf: Do not include stack ptr register in precision backtracking bookkeeping"?
Andrii made some change to my original patch for easy understanding. See
https://lore.kernel.org/bpf/[email protected]
Quoted below:
"
I've moved it inside the preceding if/else (twice), so it's more obvious that BPF_X deal with both src_reg and dst_reg, and BPF_K case deals only with BPF_K. The end result is the same, but I found this way a bit easier to follow. Applied to bpf-next, thanks.
kernel/bpf/verifier.c index 831c2eff56e1..c9a372ca7830 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -16471,6 +16471,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, renamed from kernel/bpf/verifier.c +0 -0
if (src_reg->type == PTR_TO_STACK)
insn_flags |= INSN_F_SRC_REG_STACK;
+ if (dst_reg->type == PTR_TO_STACK) + insn_flags |= INSN_F_DST_REG_STACK; } else {
if (insn->src_reg != BPF_REG_0) {
verbose(env, "BPF_JMP/JMP32 uses reserved fields\n");
@@ -16480,10 +16482,11 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
memset(src_reg, 0, sizeof(*src_reg));
src_reg->type = SCALAR_VALUE;
__mark_reg_known(src_reg, insn->imm);+ + if (dst_reg->type == PTR_TO_STACK) + insn_flags |= INSN_F_DST_REG_STACK; }
- if (dst_reg->type == PTR_TO_STACK) - insn_flags |= INSN_F_DST_REG_STACK; if (insn_flags) {
err = push_insn_history(env, this_branch, insn_flags, 0);
if (err)...
"
Quoted 41 lines
Since stable backports got only
e2d2115e56c4, but not the5ffb537e416ehere with the extra change forkernel/bpf/verifier.c, I'd guess the backtracking logic in the stable kernel isn't correct at the moment, so I'll send5ffb537e416e"selftests/bpf: Add tests with stack ptr register in conditional jmp" to stable as well. Let me know if that's not the right thing to do.Shung-Hsi
kernel/bpf/verifier.c +5
-2@@ -16456,6 +16456,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,if (src_reg->type ==PTR_TO_STACK ) insn_flags |=INSN_F_SRC_REG_STACK ; +if (dst_reg->type ==PTR_TO_STACK ) + insn_flags |=INSN_F_DST_REG_STACK ; }else {if (insn->src_reg !=BPF_REG_0 ) {verbose (env,"BPF_JMP/JMP32 uses reserved fields\n" );@@ -16465,10 +16467,11 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,memset (src_reg,0 ,sizeof (*src_reg)); src_reg->type =SCALAR_VALUE ;__mark_reg_known (src_reg, insn->imm); + +if (dst_reg->type ==PTR_TO_STACK ) + insn_flags |=INSN_F_DST_REG_STACK ; } -if (dst_reg->type ==PTR_TO_STACK ) - insn_flags |=INSN_F_DST_REG_STACK ;if (insn_flags) { err =push_insn_history (env, this_branch, insn_flags,0 );if (err)Quoted 2 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +0
-0...
Re: [PATCH bpf-next v5 2/2] selftests/bpf: Add tests with stack ptr register in conditional jmp
Quoted 24 lines · Yonghong Song
Quoted 14 lines · Shung-Hsi Yu
Hi Andrii and Yonghong,
Quoted 11 lines · Yonghong Song
Add two tests:
- one test has 'rX <op> r10' where rX is not r10, and
- another test has 'rX <op> rY' where rX and rY are not r10 but there is an early insn 'rX = r10'.Without previous verifier change, both tests will fail.
Signed-off-by Yonghong Song <[email protected]>--- .../selftests/bpf/progs/verifier_precision.c | 53 +++++++++++++++++++ 1 file changed, 53 insertions(+)Quoted 8 lines
I was looking this commit (
5ffb537e416e) since it was a BPF selftest test for CVE-2025-38279, but upon looking I found that the commit differs from the patch, there is an extra hunk that changedkernel/bpf/verifier.cthat wasn't found the Yonghong's original patch.I suppose it was meant to be squashed into the previous commit
e2d2115e56c4"bpf: Do not include stack ptr register in precision backtracking bookkeeping"?
Quoted 9 lines
Andrii made some change to my original patch for easy understanding. See
https://lore.kernel.org/bpf/[email protected]
Quoted below:
"
I've moved it inside the preceding if/else (twice), so it's more obvious thatBPF_Xdeal with bothsrc_reganddst_reg, andBPF_Kcase deals only withBPF_K. The end result is the same, but I found this way a bit easier to follow. Applied to bpf-next, thanks.
Argh, indeed I missed the sibling thread. Thanks for point that out.
Shung-Hsi
...
Quoted 206 lines · Yonghong Song
Yi Lai reported an issue ([1]) where the following warning appears in kernel dmesg:
[ 60.643604] verifier backtracking bug [ 60.643635] WARNING: CPU: 10 PID: 2315 at kernel/bpf/verifier.c:4302 __mark_chain_precision+0x3a6c/0x3e10 [ 60.648428] Modules linked in: bpf_testmod(OE) [ 60.650471] CPU: 10 UID: 0 PID: 2315 Comm: test_progs Tainted: G OE 6.15.0-rc4-gef11287f8289-dirty #327 PREEMPT(full) [ 60.654385] Tainted: [O]=OOT_MODULE, [E]=UNSIGNED_MODULE [ 60.656682] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.14.0-0-g155821a1990b-prebuilt.qemu.org 04/01/2014 [ 60.660475] RIP: 0010:__mark_chain_precision+0x3a6c/0x3e10 [ 60.662814] Code: 5a 30 84 89 ea e8 c4 d9 01 00 80 3d 3e 7d d8 04 00 0f 85 60 fa ff ff c6 05 31 7d d8 04 01 48 c7 c7 00 58 30 84 e8 c4 06 a5 ff <0f> 0b e9 46 fa ff ff 48 ... [ 60.668720] RSP: 0018:ffff888116cc7298 EFLAGS: 00010246 [ 60.671075] RAX: 54d70e82dfd31900 RBX: ffff888115b65e20 RCX: 0000000000000000 [ 60.673659] RDX: 0000000000000001 RSI: 0000000000000004 RDI: 00000000ffffffff [ 60.676241] RBP: 0000000000000400 R08: ffff8881f6f23bd3 R09: 1ffff1103ede477a [ 60.678787] R10: dffffc0000000000 R11: ffffed103ede477b R12: ffff888115b60ae8 [ 60.681420] R13: 1ffff11022b6cbc4 R14: 00000000fffffff2 R15: 0000000000000001 [ 60.684030] FS: 00007fc2aedd80c0(0000) GS:ffff88826fa8a000(0000) knlGS:0000000000000000 [ 60.686837] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 60.689027] CR2: 000056325369e000 CR3: 000000011088b002 CR4: 0000000000370ef0 [ 60.691623] Call Trace: [ 60.692821] <TASK> [ 60.693960] ? __pfx_verbose+0x10/0x10 [ 60.695656] ? __pfx_disasm_kfunc_name+0x10/0x10 [ 60.697495] check_cond_jmp_op+0x16f7/0x39b0 [ 60.699237] do_check+0x58fa/0xab10 ...Further analysis shows the warning is at line 4302 as below:
4294 /* static subprog call instruction, which
4295 * means that we are exiting current subprog, 4296 * so only r1-r5 could be still requested as 4297 * precise, r0 and r6-r10 or any stack slot in 4298 * the current frame should be zero by now 4299 */ 4300 if (bt_reg_mask(bt) & ~BPF_REGMASK_ARGS) { 4301 verbose(env, "BUG regs %x\n", bt_reg_mask(bt)); 4302 WARN_ONCE(1, "verifier backtracking bug"); 4303 return -EFAULT;4304 }
With the below test (also in the next patch):
__used__nakedstatic void__bpf_jmp_r10(void){ asm volatile ( "r2 = 2314885393468386424 ll;" "goto +0;" "if r2 <= r10 goto +3;" "if r1 >= -1835016 goto +0;" "if r2 <= 8 goto +0;" "if r3 <= 0 goto +0;" "exit;" ::: __clobber_all);}
SEC("?raw_tp") __naked void bpf_jmp_r10(void) { asm volatile ( "r3 = 0 ll;" "call __bpf_jmp_r10;" "r0 = 0;" "exit;" ::: __clobber_all); }The following is the verifier failure log:
0: (18) r3 =0x0; R3_w=0
2: (85) call pc+2
caller:R10=fp0 callee: frame1: R1=ctx() R3_w=0 R10=fp05: frame1: R1=ctx() R3_w=0 R10=fp0
; asm volatile (" \ @ verifier_precision.c:184
5: (18) r2 =0x20202000256c6c78; frame1: R2_w=0x20202000256c6c78
7: (05) goto pc+0
8: (bd) if r2 <= r10 goto pc+3 ; frame1: R2_w=0x20202000256c6c78 R10=fp0
9: (35) if r1 >=0xffe3fff8goto pc+0 ; frame1: R1=ctx()
10: (b5) if r2 <=0x8goto pc+0
mark_precise: frame1:last_idx10first_idx0subseq_idx-1
mark_precise: frame1: regs=r2 stack= before 9: (35) if r1 >=0xffe3fff8goto pc+0
mark_precise: frame1: regs=r2 stack= before 8: (bd) if r2 <= r10 goto pc+3
mark_precise: frame1: regs=r2,r10 stack= before 7: (05) goto pc+0
mark_precise: frame1: regs=r2,r10 stack= before 5: (18) r2 =0x20202000256c6c78
mark_precise: frame1: regs=r10 stack= before 2: (85) call pc+2
BUG regs 400The main failure reason is due to r10 in precision backtracking bookkeeping. Actually r10 is always precise and there is no need to add it for the precision backtracking bookkeeping.
One way to fix the issue is to prevent
bt_set_reg()if any src/dst reg is r10. Andrii suggested to go withpush_insn_history()approach to avoid explicitly checking r10 inbacktrack_insn().This patch added
push_insn_history()support forcond_jmplike 'rX <op> rY' operations. Incheck_cond_jmp_op(), if any of rX or rY is a stack pointer,push_insn_history()will record such information, and laterbacktrack_insn()will dobt_set_reg()properly for those register(s).[1] https://lore.kernel.org/bpf/Z%2F8q3xzpU59CIYQE@ly-workstation/
Reported by: Yi Lai <[email protected]>
Fixes 407958a0e980 ("bpf: encapsulate precision backtracking bookkeeping")Signed-off-by Yonghong Song <[email protected]>--- include/linux/bpf_verifier.h | 12 ++++++++---- kernel/bpf/verifier.c | 18 ++++++++++++++++-- 2 files changed, 24 insertions(+), 6 deletions(-)Changelogs:
v4 -> v5:
- v4: https://lore.kernel.org/bpf/[email protected]/
- Simplify implementation inbacktrack_insn()andcheck_cond_jmp_op().
v3 -> v4:
- v3: https://lore.kernel.org/bpf/[email protected]/
- Fix an issue inpush_cond_jmp_history(). Previously, '!src_reg' was used to check whether insn is 'dreg <op> imm' or not. But actually '!src_reg' is always non-NULL. The new fix is using insn directly.
v2 -> v3:
- v2: https://lore.kernel.org/bpf/[email protected]/
- In v2, I put sreg_flag/dreg_flag intobpf_insn_hist_entryand the information includes register numbers. This is not necessary as later insn in backtracking can retrieve the register number. So the new change is remove sreg_flag/dreg_flag frombpf_insn_hist_entryand add two bits in bpf_insn_hist_entry.flags to record whether the registers (cond jump like <reg> op < reg>) are stack pointer or not. Other changes depend on this data structure change.
v1 -> v2:
- v1: https://lore.kernel.org/bpf/[email protected]/
- In v1, we check r10 register explicitly inbacktrack_insn()to decide whether we should dobt_set_reg()or not. Andrii suggested to dopush_insn_history()instead. Whether a particular register (r10 in this case) should be available for backtracking or not is incheck_cond_jmp_op(), and such information is pushed withpush_insn_history(). Later inbacktrack_insn(), such info is retrieved to decide whether precision marking should be done or not. This apporach can avoid explicit checking for r10 inbacktrack_insn().include/linux/bpf_verifier.h +8
-4@@ -356,7 +356,11 @@ enum {INSN_F_SPI_MASK =0x3f ,/* 6 bits */ INSN_F_SPI_SHIFT =3 ,/* shifted 3 bits to the left */ -INSN_F_STACK_ACCESS =BIT (9 ),/* we need 10 bits total */ +INSN_F_STACK_ACCESS =BIT (9 ), + +INSN_F_DST_REG_STACK =BIT (10 ),/* dst_reg is PTR_TO_STACK */ +INSN_F_SRC_REG_STACK =BIT (11 ),/* src_reg is PTR_TO_STACK */ +/* total 12 bits are used now. */ };static_assert (INSN_F_FRAMENO_MASK +1 >=MAX_CALL_FRAMES );@@ -365,9 +369,9 @@ static_assert(INSN_F_SPI_MASK + 1 >= MAX_BPF_STACK / 8);struct bpf_insn_hist_entry {u32 idx;/* insn idx can't be bigger than 1 million */ -u32 prev_idx :22 ; -/* special flags, e.g., whether insn is doing register stack spill/load */ -u32 flags :10 ; +u32 prev_idx :20 ; +/* special INSN_F_xxx flags */ +u32 flags :12 ;/* additional registers that need precision tracking when this * jump is backtracked, vector of six 10-bit records */ kernel/bpf/verifier.c +8
-2@@ -4410,8 +4410,10 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,* before it would be equally necessary to * propagate it to dreg. */ -bt_set_reg (bt, dreg); -bt_set_reg (bt, sreg); +if (!hist || !(hist->flags &INSN_F_SRC_REG_STACK )) +bt_set_reg (bt, sreg); +if (!hist || !(hist->flags &INSN_F_DST_REG_STACK )) +bt_set_reg (bt, dreg); }else if (BPF_SRC (insn->code) ==BPF_K ) {/* dreg <cond> K * Only dreg still needs precision before @@ -16407,6 +16409,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,struct bpf_reg_state *eq_branch_regs;struct linked_regs linked_regs = {};u8 opcode =BPF_OP (insn->code); +int insn_flags =0 ;bool is_jmp32;int pred =-1 ;int err;@@ -16465,6 +16468,9 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, insn->src_reg);return -EACCES ; } + +if (src_reg->type ==PTR_TO_STACK ) + insn_flags |=INSN_F_SRC_REG_STACK ; }else {if (insn->src_reg !=BPF_REG_0 ) {verbose (env,"BPF_JMP/JMP32 uses reserved fields\n" );
kernel/bpf/verifier.c static int check_cond_jmp_op(struct bpf_verifier_env *env, · line 16486
Quoted 5 lines
kernel/bpf/verifier.c +2
-0@@ -16476,6 +16482,14 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,__mark_reg_known (src_reg, insn->imm); } +if (dst_reg->type ==PTR_TO_STACK ) + insn_flags |=INSN_F_DST_REG_STACK ;
I've moved it inside the preceding if/else (twice), so it's more obvious that BPF_X deal with both src_reg and dst_reg, and BPF_K case deals only with BPF_K. The end result is the same, but I found this way a bit easier to follow. Applied to bpf-next, thanks.
kernel/bpf/verifier.c +0 -0
@@ -16471,6 +16471,8 @@ static int check_cond_jmp_op(struct
bpf_verifier_env *env,
if (src_reg->type == PTR_TO_STACK)
insn_flags |= INSN_F_SRC_REG_STACK;
+ if (dst_reg->type == PTR_TO_STACK)
+ insn_flags |= INSN_F_DST_REG_STACK;
} else {
if (insn->src_reg != BPF_REG_0) {
verbose(env, "BPF_JMP/JMP32 uses reserved fields\n");
@@ -16480,10 +16482,11 @@ static int check_cond_jmp_op(struct
bpf_verifier_env *env,
memset(src_reg, 0, sizeof(*src_reg));
src_reg->type = SCALAR_VALUE;
__mark_reg_known(src_reg, insn->imm);
+
+ if (dst_reg->type == PTR_TO_STACK)
+ insn_flags |= INSN_F_DST_REG_STACK;
}- if (dst_reg->type == PTR_TO_STACK)
- insn_flags |= INSN_F_DST_REG_STACK;
if (insn_flags) {
err = push_insn_history(env, this_branch, insn_flags, 0);
if (err)Quoted 12 lines
kernel/bpf/verifier.c +6
-1+if (insn_flags) { + err =push_insn_history (env, this_branch, insn_flags,0 ); +if (err) +return err; + } + is_jmp32 =BPF_CLASS (insn->code) ==BPF_JMP32 ; pred =is_branch_taken (dst_reg, src_reg, opcode, is_jmp32);if (pred >=0 ) { --2.47.1
This series was applied to bpf/bpf-next.git (master) by Andrii Nakryiko <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Andrii Nakryiko <[email protected]>:
Quoted 28 lines · On Fri, 23 May 2025 21:13:35 -0700 you wrote:
Yi Lai reported an issue ([1]) where the following warning appears in kernel dmesg:
[ 60.643604] verifier backtracking bug [ 60.643635] WARNING: CPU: 10 PID: 2315 at kernel/bpf/verifier.c:4302 __mark_chain_precision+0x3a6c/0x3e10 [ 60.648428] Modules linked in: bpf_testmod(OE) [ 60.650471] CPU: 10 UID: 0 PID: 2315 Comm: test_progs Tainted: G OE 6.15.0-rc4-gef11287f8289-dirty #327 PREEMPT(full) [ 60.654385] Tainted: [O]=OOT_MODULE, [E]=UNSIGNED_MODULE [ 60.656682] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.14.0-0-g155821a1990b-prebuilt.qemu.org 04/01/2014 [ 60.660475] RIP: 0010:__mark_chain_precision+0x3a6c/0x3e10 [ 60.662814] Code: 5a 30 84 89 ea e8 c4 d9 01 00 80 3d 3e 7d d8 04 00 0f 85 60 fa ff ff c6 05 31 7d d8 04 01 48 c7 c7 00 58 30 84 e8 c4 06 a5 ff <0f> 0b e9 46 fa ff ff 48 ... [ 60.668720] RSP: 0018:ffff888116cc7298 EFLAGS: 00010246 [ 60.671075] RAX: 54d70e82dfd31900 RBX: ffff888115b65e20 RCX: 0000000000000000 [ 60.673659] RDX: 0000000000000001 RSI: 0000000000000004 RDI: 00000000ffffffff [ 60.676241] RBP: 0000000000000400 R08: ffff8881f6f23bd3 R09: 1ffff1103ede477a [ 60.678787] R10: dffffc0000000000 R11: ffffed103ede477b R12: ffff888115b60ae8 [ 60.681420] R13: 1ffff11022b6cbc4 R14: 00000000fffffff2 R15: 0000000000000001 [ 60.684030] FS: 00007fc2aedd80c0(0000) GS:ffff88826fa8a000(0000) knlGS:0000000000000000 [ 60.686837] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 60.689027] CR2: 000056325369e000 CR3: 000000011088b002 CR4: 0000000000370ef0 [ 60.691623] Call Trace: [ 60.692821] <TASK> [ 60.693960] ? __pfx_verbose+0x10/0x10 [ 60.695656] ? __pfx_disasm_kfunc_name+0x10/0x10 [ 60.697495] check_cond_jmp_op+0x16f7/0x39b0 [ 60.699237] do_check+0x58fa/0xab10 ...
Quoted 1 line
[...]
Here is the summary with links:
- [bpf-next,v5,1/2] bpf: Do not include stack ptr register in precision backtracking bookkeeping
https://git.kernel.org/bpf/bpf-next/c/e2d2115e56c4 - [bpf-next,v5,2/2] selftests/bpf: Add tests with stack ptr register in conditional jmp https://git.kernel.org/bpf/bpf-next/c/5ffb537e416e
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html