* WARNING in __mark_chain_precision
@ 2019-07-08 15:27 syzbot
2019-07-09 3:49 ` Andrii Nakryiko
0 siblings, 1 reply; 15+ messages in thread
From: syzbot @ 2019-07-08 15:27 UTC (permalink / raw)
To: ast, bcrl, bpf, daniel, davem, hawk, jakub.kicinski,
john.fastabend, kafai, linux-aio, linux-fsdevel, linux-kernel,
netdev, songliubraving, syzkaller-bugs, torvalds, viro,
xdp-newbies, yhs
Hello,
syzbot found the following crash on:
HEAD commit: e5a3e259 Merge branch 'bpf-tcp-rtt-hook'
git tree: bpf-next
console output: https://syzkaller.appspot.com/x/log.txt?x=14190c2da00000
kernel config: https://syzkaller.appspot.com/x/.config?x=dd16b8dc9d0d210c
dashboard link: https://syzkaller.appspot.com/bug?extid=4da3ff23081bafe74fc2
compiler: gcc (GCC) 9.0.0 20181231 (experimental)
syz repro: https://syzkaller.appspot.com/x/repro.syz?x=1409ce0da00000
C reproducer: https://syzkaller.appspot.com/x/repro.c?x=17226a0da00000
The bug was bisected to:
commit b53119f13a04879c3bf502828d99d13726639ead
Author: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu Mar 7 01:22:54 2019 +0000
pin iocb through aio.
bisection log: https://syzkaller.appspot.com/x/bisect.txt?x=11427b8ba00000
final crash: https://syzkaller.appspot.com/x/report.txt?x=13427b8ba00000
console output: https://syzkaller.appspot.com/x/log.txt?x=15427b8ba00000
IMPORTANT: if you fix the bug, please add the following tag to the commit:
Reported-by: syzbot+4da3ff23081bafe74fc2@syzkaller.appspotmail.com
Fixes: b53119f13a04 ("pin iocb through aio.")
------------[ cut here ]------------
verifier backtracking bug
WARNING: CPU: 0 PID: 9104 at kernel/bpf/verifier.c:1785
__mark_chain_precision+0x19bb/0x1ee0 kernel/bpf/verifier.c:1785
Kernel panic - not syncing: panic_on_warn set ...
CPU: 0 PID: 9104 Comm: syz-executor284 Not tainted 5.2.0-rc5+ #34
Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS
Google 01/01/2011
Call Trace:
__dump_stack lib/dump_stack.c:77 [inline]
dump_stack+0x172/0x1f0 lib/dump_stack.c:113
panic+0x2cb/0x744 kernel/panic.c:219
__warn.cold+0x20/0x4d kernel/panic.c:576
report_bug+0x263/0x2b0 lib/bug.c:186
fixup_bug arch/x86/kernel/traps.c:179 [inline]
fixup_bug arch/x86/kernel/traps.c:174 [inline]
do_error_trap+0x11b/0x200 arch/x86/kernel/traps.c:272
do_invalid_op+0x37/0x50 arch/x86/kernel/traps.c:291
invalid_op+0x14/0x20 arch/x86/entry/entry_64.S:986
RIP: 0010:__mark_chain_precision+0x19bb/0x1ee0 kernel/bpf/verifier.c:1785
Code: 08 31 ff 89 de e8 95 ba f2 ff 84 db 0f 85 ce fe ff ff e8 48 b9 f2 ff
48 c7 c7 e0 44 91 87 c6 05 1c 15 1f 08 01 e8 03 f1 c4 ff <0f> 0b 41 bc f2
ff ff ff e9 af fe ff ff e8 d3 3c 2c 00 e9 c2 e7 ff
RSP: 0018:ffff88809f04f380 EFLAGS: 00010286
RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000000
RDX: 0000000000000000 RSI: ffffffff815ad926 RDI: ffffed1013e09e62
RBP: ffff88809f04f4d0 R08: ffff88809987a540 R09: 0000000000000000
R10: 0000000000000000 R11: 0000000000000000 R12: 0000000000000000
R13: ffff88809af0c280 R14: 0000000000000001 R15: ffff88809f65cb00
mark_chain_precision kernel/bpf/verifier.c:1822 [inline]
check_cond_jmp_op+0xcd8/0x3c30 kernel/bpf/verifier.c:5842
do_check+0x60f4/0x8a20 kernel/bpf/verifier.c:7782
bpf_check+0x6f99/0x9950 kernel/bpf/verifier.c:9293
bpf_prog_load+0xe68/0x1670 kernel/bpf/syscall.c:1698
__do_sys_bpf+0xa20/0x42d0 kernel/bpf/syscall.c:2849
__se_sys_bpf kernel/bpf/syscall.c:2808 [inline]
__x64_sys_bpf+0x73/0xb0 kernel/bpf/syscall.c:2808
do_syscall_64+0xfd/0x680 arch/x86/entry/common.c:301
entry_SYSCALL_64_after_hwframe+0x49/0xbe
RIP: 0033:0x440369
Code: 18 89 d0 c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 00 48 89 f8 48 89 f7
48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff
ff 0f 83 fb 13 fc ff c3 66 2e 0f 1f 84 00 00 00 00
RSP: 002b:00007ffca85a2fa8 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
RAX: ffffffffffffffda RBX: 00000000004002c8 RCX: 0000000000440369
RDX: 0000000000000048 RSI: 0000000020000200 RDI: 0000000000000005
RBP: 00000000006ca018 R08: 0000000000000000 R09: 0000000000000000
R10: 00000000ffffffff R11: 0000000000000246 R12: 0000000000401bf0
R13: 0000000000401c80 R14: 0000000000000000 R15: 0000000000000000
Kernel Offset: disabled
Rebooting in 86400 seconds..
---
This bug is generated by a bot. It may contain errors.
See https://goo.gl/tpsmEJ for more information about syzbot.
syzbot engineers can be reached at syzkaller@googlegroups.com.
syzbot will keep track of this bug report. See:
https://goo.gl/tpsmEJ#status for how to communicate with syzbot.
For information about bisection process see: https://goo.gl/tpsmEJ#bisection
syzbot can test patches for this bug, for details see:
https://goo.gl/tpsmEJ#testing-patches
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2019-07-08 15:27 WARNING in __mark_chain_precision syzbot
@ 2019-07-09 3:49 ` Andrii Nakryiko
2019-07-09 4:08 ` syzbot
0 siblings, 1 reply; 15+ messages in thread
From: Andrii Nakryiko @ 2019-07-09 3:49 UTC (permalink / raw)
To: syzbot
Cc: Alexei Starovoitov, bcrl, bpf, Daniel Borkmann, David S. Miller,
hawk, Jakub Kicinski, john fastabend, Martin Lau, linux-aio,
linux-fsdevel, open list, Networking, Song Liu, syzkaller-bugs,
torvalds, viro, xdp-newbies, Yonghong Song
#syz test: https://github.com/anakryiko/linux bpf-fix-precise-bpf_st
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2019-07-09 3:49 ` Andrii Nakryiko
@ 2019-07-09 4:08 ` syzbot
0 siblings, 0 replies; 15+ messages in thread
From: syzbot @ 2019-07-09 4:08 UTC (permalink / raw)
To: andrii.nakryiko, ast, bcrl, bpf, daniel, davem, hawk,
jakub.kicinski, john.fastabend, kafai, linux-aio, linux-fsdevel,
linux-kernel, netdev, songliubraving, syzkaller-bugs, torvalds,
viro, xdp-newbies, yhs
Hello,
syzbot has tested the proposed patch and the reproducer did not trigger
crash:
Reported-and-tested-by:
syzbot+4da3ff23081bafe74fc2@syzkaller.appspotmail.com
Tested on:
commit: b9321614 bpf: fix precision bit propagation for BPF_ST ins..
git tree: https://github.com/anakryiko/linux bpf-fix-precise-bpf_st
kernel config: https://syzkaller.appspot.com/x/.config?x=6bb3e6e7997c14f9
compiler: gcc (GCC) 9.0.0 20181231 (experimental)
Note: testing is done by a robot and is best-effort only.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2023-01-04 8:52 ` Hao Sun
@ 2023-01-04 16:51 ` Yonghong Song
0 siblings, 0 replies; 15+ messages in thread
From: Yonghong Song @ 2023-01-04 16:51 UTC (permalink / raw)
To: Hao Sun
Cc: Alexei Starovoitov, Andrii Nakryiko, Stanislav Fomichev,
Andrii Nakryiko, bpf, Alexei Starovoitov, Daniel Borkmann,
John Fastabend, Martin KaFai Lau, Song Liu, Yonghong Song,
KP Singh, Hao Luo, Jiri Olsa, David Miller, Jakub Kicinski,
Jesper Dangaard Brouer, Linux Kernel Mailing List
On 1/4/23 12:52 AM, Hao Sun wrote:
>
>
>> On 4 Jan 2023, at 1:47 PM, Yonghong Song <yhs@meta.com> wrote:
>>
>>
>>
>> On 1/3/23 10:27 AM, Alexei Starovoitov wrote:
>>> On Mon, Jan 2, 2023 at 1:42 AM Hao Sun <sunhao.th@gmail.com> wrote:
>>>>
>>>>
>>>>
>>>> Yonghong Song <yhs@meta.com> 于2023年1月2日周一 03:20写道：
>>>>>
>>>>>
>>>>>
>>>>> On 12/30/22 1:44 AM, Hao Sun wrote:
>>>>>>
>>>>>>
>>>>>> Andrii Nakryiko <andrii.nakryiko@gmail.com> 于2022年12月30日周五 06:16写道：
>>>>>>>
>>>>>>> On Tue, Dec 27, 2022 at 9:24 PM Yonghong Song <yhs@meta.com> wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On 12/20/22 4:30 PM, Andrii Nakryiko wrote:
>>>>>>>>> On Mon, Dec 19, 2022 at 11:13 AM <sdf@google.com> wrote:
>>>>>>>>>>
>>>>>>>>>> On 12/19, Hao Sun wrote:
>>>>>>>>>>> Hi,
>>>>>>>>>>
>>>>>>>>>>> The following backtracking bug can be triggered on the latest bpf-next and
>>>>>>>>>>> Linux 6.1 with the C prog provided. I don't have enough knowledge about
>>>>>>>>>>> this part in the verifier, don't know how to fix this.
>>>>>>>>>>
>>>>>>>>>> Maybe something related to commit be2ef8161572 ("bpf: allow precision
>>>>>>>>>> tracking
>>>>>>>>>> for programs with subprogs") and/or the related ones?
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>> This can be reproduced on:
>>>>>>>>>>
>>>>>>>>>>> HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
>>>>>>>>>>> libelf
>>>>>>>>>>> git tree: bpf-next
>>>>>>>>>>> console log: https://pastebin.com/raw/45hZ7iqm
>>>>>>>>>>> kernel config: https://pastebin.com/raw/0pu1CHRm
>>>>>>>>>>> C reproducer: https://pastebin.com/raw/tqsiezvT
>>>>>>>>>>
>>>>>>>>>>> func#0 @0
>>>>>>>>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>>>>>>>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>>>>>>>>>> 2: (18) r6 = 0xffff888027358000 ;
>>>>>>>>>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>>>>>>>>> 4: (18) r7 = 0xffff88802735a000 ;
>>>>>>>>>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>>>>>>>>>> 6: (18) r8 = 0xffff88802735e000 ;
>>>>>>>>>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>>>>>>>>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>>>>>>>>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>>>>>>>>>> last_idx 10 first_idx 0
>>>>>>>>>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>>>>>>>>>> 11: R9_w=156779191205888
>>>>>>>>>>> 11: (85) call #0
>>>>>>>>>>> 12: (cc) w2 s>>= w7
>>>>>>>>>
>>>>>>>>> w2 should have been set to NOT_INIT (because r1-r5 are clobbered by
>>>>>>>>> calls) and rejected here as !read_ok (see check_reg_arg()) before
>>>>>>>>> attempting to mark precision for r2. Can you please try to debug and
>>>>>>>>> understand why that didn't happen here?
>>>>>>>>
>>>>>>>> The verifier is doing the right thing here and the 'call #0' does
>>>>>>>> implicitly cleared r1-r5.
>>>>>>>>
>>>>>>>> So for 'w2 s>>= w7', since w2 is used, the verifier tries to find
>>>>>>>> its definition by backtracing. It encountered 'call #0', which clears
>>>>>>>
>>>>>>> and that's what I'm saying is incorrect. Normally we'd get !read_ok
>>>>>>> error because s>>= is both READ and WRITE on w2, which is
>>>>>>> uninitialized after call instruction according to BPF ABI. And that's
>>>>>>> what actually seems to happen correctly in my (simpler) tests locally.
>>>>>>> But something is special about this specific repro that somehow either
>>>>>>> bypasses this logic, or attempts to mark precision before we get to
>>>>>>> that test. That's what we should investigate. I haven't tried to run
>>>>>>> this specific repro locally yet, so can't tell for sure.
>>>>>>>
>>>>>>
>>>>>> So, the reason why w2 is not marked as uninit is that the kfunc call in
>>>>>> the BPF program is invalid, "call #0", imm is zero, right?
>>>>>
>>>>> Yes, "call #0" is invalid. As the code below
>>>>>
>>>>>> /* skip for now, but return error when we find this in
>>>>> fixup_kfunc_call */
>>>>>> if (!insn->imm)
>>>>>> return 0;
>>>>>
>>>>> The error report will be delayed later in fixup_kfunc_call().
>>>>>
>>>>> static int fixup_kfunc_call(struct bpf_verifier_env *env, struct
>>>>> bpf_insn *insn,
>>>>> struct bpf_insn *insn_buf, int insn_idx,
>>>>> int *cnt)
>>>>> {
>>>>> const struct bpf_kfunc_desc *desc;
>>>>>
>>>>> if (!insn->imm) {
>>>>> verbose(env, "invalid kernel function call not
>>>>> eliminated in verifier pass\n");
>>>>> return -EINVAL;
>>>>> }
>>>>>
>>>>>
>>>>>> In check_kfunc_call(), it skips this error temporarily:
>>>>>>
>>>>>> /* skip for now, but return error when we find this in fixup_kfunc_call */
>>>>>> if (!insn->imm)
>>>>>> return 0;
>>>>>>
>>>>>> So the kfunc call is the previous instruction before "w2 s>>= w7", this
>>>>>> leads to the warning in backtrack_insn():
>>>>>>
>>>>>> /* regular helper call sets R0 */
>>>>>> *reg_mask &= ~1;
>>>>>> if (*reg_mask & 0x3f) {
>>>>>> /* if backtracing was looking for registers R1-R5
>>>>>> * they should have been found already.
>>>>>> */
>>>>>> verbose(env, "BUG regs %x\n", *reg_mask);
>>>>>> WARN_ONCE(1, "verifier backtracking bug”);
>>>>>> return -EFAULT;
>>>>>> }
>>>>>
>>>>> The main triggering the backtrack_insn() is due to
>>>>>
>>>>> } else {
>>>>> /* scalar += pointer
>>>>> * This is legal, but we have to
>>>>> reverse our
>>>>> * src/dest handling in computing the range
>>>>> */
>>>>> err = mark_chain_precision(env,
>>>>> insn->dst_reg);
>>>>> if (err)
>>>>> return err;
>>>>> return adjust_ptr_min_max_vals(env, insn,
>>>>> src_reg,
>>>>> dst_reg);
>>>>> }
>>>>>
>>>>>
>>>>> unc#0 @0
>>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>>>> 2: (18) r6 = 0xffff888100d29000 ;
>>>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>>> 4: (18) r7 = 0xffff888100d2a000 ;
>>>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>>>> 6: (18) r8 = 0xffff888100d2ac00 ;
>>>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>>>> last_idx 10 first_idx 0
>>>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>>>> 11: R9_w=156779191205888
>>>>> 11: (85) call #0
>>>>> 12: (cc) w2 s>>= w7
>>>>> last_idx 12 first_idx 12
>>>>> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
>>>>> R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>>> R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,v0
>>>>> last_idx 11 first_idx 0
>>>>> regs=4 stack=0 before 11: (85) call #0
>>>>> BUG regs 4
>>>>>
>>>>> For insn 12, 'w2 s>>= w7', w2 is a scalar and w7 is a map_ptr. Hence,
>>>>> based on the above verifier code, mark_chain_precision() is triggered.
>>>>>
>>>>> Not sure what is the purpose of this test. But to make it succeed,
>>>>> first "call #0" need to change to a valid kfunc call, and second, you
>>>>> might want to change 'w2 s>>= w7' to e.g., 'w9 s>>= w7' to avoid
>>>>> precision tracking.
>>>>>
>>>>
>>>> The purpose is not to make the test "succeed", the verifier temporarily
>>>> skips the invalid kfunc insn "call #0", but this insn triggered a warning
>>>> in backtrack_insn(), while it is supposed to reject the program either
>>>> due to insn#12 32bit ptr alu or insn#11 invalid kfunc.
>>>>
>>>> Maybe something like the bellow, after applying the patch, the reproducer
>>>> is rejected:
>>>>
>>>> func#0 @0
>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>>> 2: (18) r6 = 0xffff88817d563000 ; R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>> 4: (18) r7 = 0xffff888171ee9000 ; R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>>> 6: (18) r8 = 0xffff888171ee8000 ; R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>>> last_idx 10 first_idx 0
>>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>>> 11: R9_w=156779191205888
>>>> 11: (85) call #0
>>>> 12: (cc) w2 s>>= w7
>>>> last_idx 12 first_idx 12
>>>> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0) R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0) R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0) R9_w=156779191205888 R10=fp0
>>>> last_idx 11 first_idx 0
>>>> regs=4 stack=0 before 11: (85) call #0
>>>> regs=4 stack=0 before 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>>> regs=4 stack=0 before 8: (18) r9 = 0x8e9700000000
>>>> regs=4 stack=0 before 6: (18) r8 = 0xffff888171ee8000
>>>> regs=4 stack=0 before 4: (18) r7 = 0xffff888171ee9000
>>>> regs=4 stack=0 before 2: (18) r6 = 0xffff88817d563000
>>>> regs=4 stack=0 before 0: (18) r2 = 0x8000000000000
>>>> R2 32-bit pointer arithmetic prohibited
>>>> processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
>>>>
>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>>> index 4a25375ebb0d..abc7e96d826f 100644
>>>> --- a/kernel/bpf/verifier.c
>>>> +++ b/kernel/bpf/verifier.c
>>>> @@ -2743,6 +2743,9 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx,
>>>> *reg_mask |= sreg;
>>>> } else if (class == BPF_JMP || class == BPF_JMP32) {
>>>> if (opcode == BPF_CALL) {
>>>> + /* skip for now, should return error when we find this in fixup_kfunc_call */
>>>> + if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL && insn->imm == 0)
>>>> + return 0;
>>> Makes sense to me. Please submit as an official patch
>>> with s/return 0/return -ENOTSUPP/
>>> Also 'skip for now' isn't quite correct here.
>>> In check_kfunc_call() it's correct, since invalid kfunc with imm==0
>>> could be eliminated during dead code elimination,
>>> but since we're walking this insn here in backtrack_insn
>>> the dead code elimination is not going to kick in.
>>> So it's surely invalid kfunc call if we see it in backtrack_insn.
>>> The comment should probably be something like:
>>> /* kfunc with imm==0 is invalid and fixup_kfunc_call will catch
>>> this error later. Make backtracking conservative with ENOTSUPP. */
>>
>> Do we have the same issue if we have
>> call #1 <or some valid kfunc>
>> instead of
>> call #0
>> ?
>
> Seems no. If that happened, then, it’s another bug. Because as Andrii commented,
> the prog should be rejected due to !read_ok before backing track to the kfunc
> call. In this particular case, the invalid kfunc call is skipped without marking
> Regs as uninitiated so the verifier incorrectly backtrack to that invalid call.
Make sense. Thanks for double checking!
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2023-01-04 5:47 ` Yonghong Song
@ 2023-01-04 8:52 ` Hao Sun
2023-01-04 16:51 ` Yonghong Song
0 siblings, 1 reply; 15+ messages in thread
From: Hao Sun @ 2023-01-04 8:52 UTC (permalink / raw)
To: Yonghong Song
Cc: Alexei Starovoitov, Andrii Nakryiko, Stanislav Fomichev,
Andrii Nakryiko, bpf, Alexei Starovoitov, Daniel Borkmann,
John Fastabend, Martin KaFai Lau, Song Liu, Yonghong Song,
KP Singh, Hao Luo, Jiri Olsa, David Miller, Jakub Kicinski,
Jesper Dangaard Brouer, Linux Kernel Mailing List
> On 4 Jan 2023, at 1:47 PM, Yonghong Song <yhs@meta.com> wrote:
>
>
>
> On 1/3/23 10:27 AM, Alexei Starovoitov wrote:
>> On Mon, Jan 2, 2023 at 1:42 AM Hao Sun <sunhao.th@gmail.com> wrote:
>>>
>>>
>>>
>>> Yonghong Song <yhs@meta.com> 于2023年1月2日周一 03:20写道：
>>>>
>>>>
>>>>
>>>> On 12/30/22 1:44 AM, Hao Sun wrote:
>>>>>
>>>>>
>>>>> Andrii Nakryiko <andrii.nakryiko@gmail.com> 于2022年12月30日周五 06:16写道：
>>>>>>
>>>>>> On Tue, Dec 27, 2022 at 9:24 PM Yonghong Song <yhs@meta.com> wrote:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On 12/20/22 4:30 PM, Andrii Nakryiko wrote:
>>>>>>>> On Mon, Dec 19, 2022 at 11:13 AM <sdf@google.com> wrote:
>>>>>>>>>
>>>>>>>>> On 12/19, Hao Sun wrote:
>>>>>>>>>> Hi,
>>>>>>>>>
>>>>>>>>>> The following backtracking bug can be triggered on the latest bpf-next and
>>>>>>>>>> Linux 6.1 with the C prog provided. I don't have enough knowledge about
>>>>>>>>>> this part in the verifier, don't know how to fix this.
>>>>>>>>>
>>>>>>>>> Maybe something related to commit be2ef8161572 ("bpf: allow precision
>>>>>>>>> tracking
>>>>>>>>> for programs with subprogs") and/or the related ones?
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> This can be reproduced on:
>>>>>>>>>
>>>>>>>>>> HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
>>>>>>>>>> libelf
>>>>>>>>>> git tree: bpf-next
>>>>>>>>>> console log: https://pastebin.com/raw/45hZ7iqm
>>>>>>>>>> kernel config: https://pastebin.com/raw/0pu1CHRm
>>>>>>>>>> C reproducer: https://pastebin.com/raw/tqsiezvT
>>>>>>>>>
>>>>>>>>>> func#0 @0
>>>>>>>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>>>>>>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>>>>>>>>> 2: (18) r6 = 0xffff888027358000 ;
>>>>>>>>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>>>>>>>> 4: (18) r7 = 0xffff88802735a000 ;
>>>>>>>>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>>>>>>>>> 6: (18) r8 = 0xffff88802735e000 ;
>>>>>>>>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>>>>>>>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>>>>>>>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>>>>>>>>> last_idx 10 first_idx 0
>>>>>>>>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>>>>>>>>> 11: R9_w=156779191205888
>>>>>>>>>> 11: (85) call #0
>>>>>>>>>> 12: (cc) w2 s>>= w7
>>>>>>>>
>>>>>>>> w2 should have been set to NOT_INIT (because r1-r5 are clobbered by
>>>>>>>> calls) and rejected here as !read_ok (see check_reg_arg()) before
>>>>>>>> attempting to mark precision for r2. Can you please try to debug and
>>>>>>>> understand why that didn't happen here?
>>>>>>>
>>>>>>> The verifier is doing the right thing here and the 'call #0' does
>>>>>>> implicitly cleared r1-r5.
>>>>>>>
>>>>>>> So for 'w2 s>>= w7', since w2 is used, the verifier tries to find
>>>>>>> its definition by backtracing. It encountered 'call #0', which clears
>>>>>>
>>>>>> and that's what I'm saying is incorrect. Normally we'd get !read_ok
>>>>>> error because s>>= is both READ and WRITE on w2, which is
>>>>>> uninitialized after call instruction according to BPF ABI. And that's
>>>>>> what actually seems to happen correctly in my (simpler) tests locally.
>>>>>> But something is special about this specific repro that somehow either
>>>>>> bypasses this logic, or attempts to mark precision before we get to
>>>>>> that test. That's what we should investigate. I haven't tried to run
>>>>>> this specific repro locally yet, so can't tell for sure.
>>>>>>
>>>>>
>>>>> So, the reason why w2 is not marked as uninit is that the kfunc call in
>>>>> the BPF program is invalid, "call #0", imm is zero, right?
>>>>
>>>> Yes, "call #0" is invalid. As the code below
>>>>
>>>>> /* skip for now, but return error when we find this in
>>>> fixup_kfunc_call */
>>>>> if (!insn->imm)
>>>>> return 0;
>>>>
>>>> The error report will be delayed later in fixup_kfunc_call().
>>>>
>>>> static int fixup_kfunc_call(struct bpf_verifier_env *env, struct
>>>> bpf_insn *insn,
>>>> struct bpf_insn *insn_buf, int insn_idx,
>>>> int *cnt)
>>>> {
>>>> const struct bpf_kfunc_desc *desc;
>>>>
>>>> if (!insn->imm) {
>>>> verbose(env, "invalid kernel function call not
>>>> eliminated in verifier pass\n");
>>>> return -EINVAL;
>>>> }
>>>>
>>>>
>>>>> In check_kfunc_call(), it skips this error temporarily:
>>>>>
>>>>> /* skip for now, but return error when we find this in fixup_kfunc_call */
>>>>> if (!insn->imm)
>>>>> return 0;
>>>>>
>>>>> So the kfunc call is the previous instruction before "w2 s>>= w7", this
>>>>> leads to the warning in backtrack_insn():
>>>>>
>>>>> /* regular helper call sets R0 */
>>>>> *reg_mask &= ~1;
>>>>> if (*reg_mask & 0x3f) {
>>>>> /* if backtracing was looking for registers R1-R5
>>>>> * they should have been found already.
>>>>> */
>>>>> verbose(env, "BUG regs %x\n", *reg_mask);
>>>>> WARN_ONCE(1, "verifier backtracking bug”);
>>>>> return -EFAULT;
>>>>> }
>>>>
>>>> The main triggering the backtrack_insn() is due to
>>>>
>>>> } else {
>>>> /* scalar += pointer
>>>> * This is legal, but we have to
>>>> reverse our
>>>> * src/dest handling in computing the range
>>>> */
>>>> err = mark_chain_precision(env,
>>>> insn->dst_reg);
>>>> if (err)
>>>> return err;
>>>> return adjust_ptr_min_max_vals(env, insn,
>>>> src_reg,
>>>> dst_reg);
>>>> }
>>>>
>>>>
>>>> unc#0 @0
>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>>> 2: (18) r6 = 0xffff888100d29000 ;
>>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>> 4: (18) r7 = 0xffff888100d2a000 ;
>>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>>> 6: (18) r8 = 0xffff888100d2ac00 ;
>>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>>> last_idx 10 first_idx 0
>>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>>> 11: R9_w=156779191205888
>>>> 11: (85) call #0
>>>> 12: (cc) w2 s>>= w7
>>>> last_idx 12 first_idx 12
>>>> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
>>>> R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>> R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,v0
>>>> last_idx 11 first_idx 0
>>>> regs=4 stack=0 before 11: (85) call #0
>>>> BUG regs 4
>>>>
>>>> For insn 12, 'w2 s>>= w7', w2 is a scalar and w7 is a map_ptr. Hence,
>>>> based on the above verifier code, mark_chain_precision() is triggered.
>>>>
>>>> Not sure what is the purpose of this test. But to make it succeed,
>>>> first "call #0" need to change to a valid kfunc call, and second, you
>>>> might want to change 'w2 s>>= w7' to e.g., 'w9 s>>= w7' to avoid
>>>> precision tracking.
>>>>
>>>
>>> The purpose is not to make the test "succeed", the verifier temporarily
>>> skips the invalid kfunc insn "call #0", but this insn triggered a warning
>>> in backtrack_insn(), while it is supposed to reject the program either
>>> due to insn#12 32bit ptr alu or insn#11 invalid kfunc.
>>>
>>> Maybe something like the bellow, after applying the patch, the reproducer
>>> is rejected:
>>>
>>> func#0 @0
>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>> 2: (18) r6 = 0xffff88817d563000 ; R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>> 4: (18) r7 = 0xffff888171ee9000 ; R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>> 6: (18) r8 = 0xffff888171ee8000 ; R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>> last_idx 10 first_idx 0
>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>> 11: R9_w=156779191205888
>>> 11: (85) call #0
>>> 12: (cc) w2 s>>= w7
>>> last_idx 12 first_idx 12
>>> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0) R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0) R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0) R9_w=156779191205888 R10=fp0
>>> last_idx 11 first_idx 0
>>> regs=4 stack=0 before 11: (85) call #0
>>> regs=4 stack=0 before 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>> regs=4 stack=0 before 8: (18) r9 = 0x8e9700000000
>>> regs=4 stack=0 before 6: (18) r8 = 0xffff888171ee8000
>>> regs=4 stack=0 before 4: (18) r7 = 0xffff888171ee9000
>>> regs=4 stack=0 before 2: (18) r6 = 0xffff88817d563000
>>> regs=4 stack=0 before 0: (18) r2 = 0x8000000000000
>>> R2 32-bit pointer arithmetic prohibited
>>> processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
>>>
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index 4a25375ebb0d..abc7e96d826f 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -2743,6 +2743,9 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx,
>>> *reg_mask |= sreg;
>>> } else if (class == BPF_JMP || class == BPF_JMP32) {
>>> if (opcode == BPF_CALL) {
>>> + /* skip for now, should return error when we find this in fixup_kfunc_call */
>>> + if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL && insn->imm == 0)
>>> + return 0;
>> Makes sense to me. Please submit as an official patch
>> with s/return 0/return -ENOTSUPP/
>> Also 'skip for now' isn't quite correct here.
>> In check_kfunc_call() it's correct, since invalid kfunc with imm==0
>> could be eliminated during dead code elimination,
>> but since we're walking this insn here in backtrack_insn
>> the dead code elimination is not going to kick in.
>> So it's surely invalid kfunc call if we see it in backtrack_insn.
>> The comment should probably be something like:
>> /* kfunc with imm==0 is invalid and fixup_kfunc_call will catch
>> this error later. Make backtracking conservative with ENOTSUPP. */
>
> Do we have the same issue if we have
> call #1 <or some valid kfunc>
> instead of
> call #0
> ?
Seems no. If that happened, then, it’s another bug. Because as Andrii commented,
the prog should be rejected due to !read_ok before backing track to the kfunc
call. In this particular case, the invalid kfunc call is skipped without marking
Regs as uninitiated so the verifier incorrectly backtrack to that invalid call.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2023-01-03 18:27 ` Alexei Starovoitov
@ 2023-01-04 5:47 ` Yonghong Song
2023-01-04 8:52 ` Hao Sun
0 siblings, 1 reply; 15+ messages in thread
From: Yonghong Song @ 2023-01-04 5:47 UTC (permalink / raw)
To: Alexei Starovoitov, Hao Sun
Cc: Andrii Nakryiko, Stanislav Fomichev, Andrii Nakryiko, bpf,
Alexei Starovoitov, Daniel Borkmann, John Fastabend,
Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Hao Luo,
Jiri Olsa, David Miller, Jakub Kicinski, Jesper Dangaard Brouer,
Linux Kernel Mailing List
On 1/3/23 10:27 AM, Alexei Starovoitov wrote:
> On Mon, Jan 2, 2023 at 1:42 AM Hao Sun <sunhao.th@gmail.com> wrote:
>>
>>
>>
>> Yonghong Song <yhs@meta.com> 于2023年1月2日周一 03:20写道：
>>>
>>>
>>>
>>> On 12/30/22 1:44 AM, Hao Sun wrote:
>>>>
>>>>
>>>> Andrii Nakryiko <andrii.nakryiko@gmail.com> 于2022年12月30日周五 06:16写道：
>>>>>
>>>>> On Tue, Dec 27, 2022 at 9:24 PM Yonghong Song <yhs@meta.com> wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>> On 12/20/22 4:30 PM, Andrii Nakryiko wrote:
>>>>>>> On Mon, Dec 19, 2022 at 11:13 AM <sdf@google.com> wrote:
>>>>>>>>
>>>>>>>> On 12/19, Hao Sun wrote:
>>>>>>>>> Hi,
>>>>>>>>
>>>>>>>>> The following backtracking bug can be triggered on the latest bpf-next and
>>>>>>>>> Linux 6.1 with the C prog provided. I don't have enough knowledge about
>>>>>>>>> this part in the verifier, don't know how to fix this.
>>>>>>>>
>>>>>>>> Maybe something related to commit be2ef8161572 ("bpf: allow precision
>>>>>>>> tracking
>>>>>>>> for programs with subprogs") and/or the related ones?
>>>>>>>>
>>>>>>>>
>>>>>>>>> This can be reproduced on:
>>>>>>>>
>>>>>>>>> HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
>>>>>>>>> libelf
>>>>>>>>> git tree: bpf-next
>>>>>>>>> console log: https://pastebin.com/raw/45hZ7iqm
>>>>>>>>> kernel config: https://pastebin.com/raw/0pu1CHRm
>>>>>>>>> C reproducer: https://pastebin.com/raw/tqsiezvT
>>>>>>>>
>>>>>>>>> func#0 @0
>>>>>>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>>>>>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>>>>>>>> 2: (18) r6 = 0xffff888027358000 ;
>>>>>>>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>>>>>>> 4: (18) r7 = 0xffff88802735a000 ;
>>>>>>>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>>>>>>>> 6: (18) r8 = 0xffff88802735e000 ;
>>>>>>>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>>>>>>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>>>>>>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>>>>>>>> last_idx 10 first_idx 0
>>>>>>>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>>>>>>>> 11: R9_w=156779191205888
>>>>>>>>> 11: (85) call #0
>>>>>>>>> 12: (cc) w2 s>>= w7
>>>>>>>
>>>>>>> w2 should have been set to NOT_INIT (because r1-r5 are clobbered by
>>>>>>> calls) and rejected here as !read_ok (see check_reg_arg()) before
>>>>>>> attempting to mark precision for r2. Can you please try to debug and
>>>>>>> understand why that didn't happen here?
>>>>>>
>>>>>> The verifier is doing the right thing here and the 'call #0' does
>>>>>> implicitly cleared r1-r5.
>>>>>>
>>>>>> So for 'w2 s>>= w7', since w2 is used, the verifier tries to find
>>>>>> its definition by backtracing. It encountered 'call #0', which clears
>>>>>
>>>>> and that's what I'm saying is incorrect. Normally we'd get !read_ok
>>>>> error because s>>= is both READ and WRITE on w2, which is
>>>>> uninitialized after call instruction according to BPF ABI. And that's
>>>>> what actually seems to happen correctly in my (simpler) tests locally.
>>>>> But something is special about this specific repro that somehow either
>>>>> bypasses this logic, or attempts to mark precision before we get to
>>>>> that test. That's what we should investigate. I haven't tried to run
>>>>> this specific repro locally yet, so can't tell for sure.
>>>>>
>>>>
>>>> So, the reason why w2 is not marked as uninit is that the kfunc call in
>>>> the BPF program is invalid, "call #0", imm is zero, right?
>>>
>>> Yes, "call #0" is invalid. As the code below
>>>
>>>> /* skip for now, but return error when we find this in
>>> fixup_kfunc_call */
>>>> if (!insn->imm)
>>>> return 0;
>>>
>>> The error report will be delayed later in fixup_kfunc_call().
>>>
>>> static int fixup_kfunc_call(struct bpf_verifier_env *env, struct
>>> bpf_insn *insn,
>>> struct bpf_insn *insn_buf, int insn_idx,
>>> int *cnt)
>>> {
>>> const struct bpf_kfunc_desc *desc;
>>>
>>> if (!insn->imm) {
>>> verbose(env, "invalid kernel function call not
>>> eliminated in verifier pass\n");
>>> return -EINVAL;
>>> }
>>>
>>>
>>>> In check_kfunc_call(), it skips this error temporarily:
>>>>
>>>> /* skip for now, but return error when we find this in fixup_kfunc_call */
>>>> if (!insn->imm)
>>>> return 0;
>>>>
>>>> So the kfunc call is the previous instruction before "w2 s>>= w7", this
>>>> leads to the warning in backtrack_insn():
>>>>
>>>> /* regular helper call sets R0 */
>>>> *reg_mask &= ~1;
>>>> if (*reg_mask & 0x3f) {
>>>> /* if backtracing was looking for registers R1-R5
>>>> * they should have been found already.
>>>> */
>>>> verbose(env, "BUG regs %x\n", *reg_mask);
>>>> WARN_ONCE(1, "verifier backtracking bug”);
>>>> return -EFAULT;
>>>> }
>>>
>>> The main triggering the backtrack_insn() is due to
>>>
>>> } else {
>>> /* scalar += pointer
>>> * This is legal, but we have to
>>> reverse our
>>> * src/dest handling in computing the range
>>> */
>>> err = mark_chain_precision(env,
>>> insn->dst_reg);
>>> if (err)
>>> return err;
>>> return adjust_ptr_min_max_vals(env, insn,
>>> src_reg,
>>> dst_reg);
>>> }
>>>
>>>
>>> unc#0 @0
>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>> 2: (18) r6 = 0xffff888100d29000 ;
>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>> 4: (18) r7 = 0xffff888100d2a000 ;
>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>> 6: (18) r8 = 0xffff888100d2ac00 ;
>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>> last_idx 10 first_idx 0
>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>> 11: R9_w=156779191205888
>>> 11: (85) call #0
>>> 12: (cc) w2 s>>= w7
>>> last_idx 12 first_idx 12
>>> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
>>> R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>> R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,v0
>>> last_idx 11 first_idx 0
>>> regs=4 stack=0 before 11: (85) call #0
>>> BUG regs 4
>>>
>>> For insn 12, 'w2 s>>= w7', w2 is a scalar and w7 is a map_ptr. Hence,
>>> based on the above verifier code, mark_chain_precision() is triggered.
>>>
>>> Not sure what is the purpose of this test. But to make it succeed,
>>> first "call #0" need to change to a valid kfunc call, and second, you
>>> might want to change 'w2 s>>= w7' to e.g., 'w9 s>>= w7' to avoid
>>> precision tracking.
>>>
>>
>> The purpose is not to make the test "succeed", the verifier temporarily
>> skips the invalid kfunc insn "call #0", but this insn triggered a warning
>> in backtrack_insn(), while it is supposed to reject the program either
>> due to insn#12 32bit ptr alu or insn#11 invalid kfunc.
>>
>> Maybe something like the bellow, after applying the patch, the reproducer
>> is rejected:
>>
>> func#0 @0
>> 0: R1=ctx(off=0,imm=0) R10=fp0
>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>> 2: (18) r6 = 0xffff88817d563000 ; R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>> 4: (18) r7 = 0xffff888171ee9000 ; R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>> 6: (18) r8 = 0xffff888171ee8000 ; R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>> last_idx 10 first_idx 0
>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>> 11: R9_w=156779191205888
>> 11: (85) call #0
>> 12: (cc) w2 s>>= w7
>> last_idx 12 first_idx 12
>> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0) R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0) R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0) R9_w=156779191205888 R10=fp0
>> last_idx 11 first_idx 0
>> regs=4 stack=0 before 11: (85) call #0
>> regs=4 stack=0 before 10: (36) if w9 >= 0xffffffe3 goto pc+1
>> regs=4 stack=0 before 8: (18) r9 = 0x8e9700000000
>> regs=4 stack=0 before 6: (18) r8 = 0xffff888171ee8000
>> regs=4 stack=0 before 4: (18) r7 = 0xffff888171ee9000
>> regs=4 stack=0 before 2: (18) r6 = 0xffff88817d563000
>> regs=4 stack=0 before 0: (18) r2 = 0x8000000000000
>> R2 32-bit pointer arithmetic prohibited
>> processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 4a25375ebb0d..abc7e96d826f 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -2743,6 +2743,9 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx,
>> *reg_mask |= sreg;
>> } else if (class == BPF_JMP || class == BPF_JMP32) {
>> if (opcode == BPF_CALL) {
>> + /* skip for now, should return error when we find this in fixup_kfunc_call */
>> + if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL && insn->imm == 0)
>> + return 0;
>
>
> Makes sense to me. Please submit as an official patch
> with s/return 0/return -ENOTSUPP/
> Also 'skip for now' isn't quite correct here.
> In check_kfunc_call() it's correct, since invalid kfunc with imm==0
> could be eliminated during dead code elimination,
> but since we're walking this insn here in backtrack_insn
> the dead code elimination is not going to kick in.
> So it's surely invalid kfunc call if we see it in backtrack_insn.
> The comment should probably be something like:
> /* kfunc with imm==0 is invalid and fixup_kfunc_call will catch
> this error later. Make backtracking conservative with ENOTSUPP. */
Do we have the same issue if we have
call #1 <or some valid kfunc>
instead of
call #0
?
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2023-01-02 9:42 ` Hao Sun
@ 2023-01-03 18:27 ` Alexei Starovoitov
2023-01-04 5:47 ` Yonghong Song
0 siblings, 1 reply; 15+ messages in thread
From: Alexei Starovoitov @ 2023-01-03 18:27 UTC (permalink / raw)
To: Hao Sun
Cc: Yonghong Song, Andrii Nakryiko, Stanislav Fomichev,
Andrii Nakryiko, bpf, Alexei Starovoitov, Daniel Borkmann,
John Fastabend, Martin KaFai Lau, Song Liu, Yonghong Song,
KP Singh, Hao Luo, Jiri Olsa, David Miller, Jakub Kicinski,
Jesper Dangaard Brouer, Linux Kernel Mailing List
On Mon, Jan 2, 2023 at 1:42 AM Hao Sun <sunhao.th@gmail.com> wrote:
>
>
>
> Yonghong Song <yhs@meta.com> 于2023年1月2日周一 03:20写道：
> >
> >
> >
> > On 12/30/22 1:44 AM, Hao Sun wrote:
> >>
> >>
> >> Andrii Nakryiko <andrii.nakryiko@gmail.com> 于2022年12月30日周五 06:16写道：
> >>>
> >>> On Tue, Dec 27, 2022 at 9:24 PM Yonghong Song <yhs@meta.com> wrote:
> >>>>
> >>>>
> >>>>
> >>>> On 12/20/22 4:30 PM, Andrii Nakryiko wrote:
> >>>>> On Mon, Dec 19, 2022 at 11:13 AM <sdf@google.com> wrote:
> >>>>>>
> >>>>>> On 12/19, Hao Sun wrote:
> >>>>>>> Hi,
> >>>>>>
> >>>>>>> The following backtracking bug can be triggered on the latest bpf-next and
> >>>>>>> Linux 6.1 with the C prog provided. I don't have enough knowledge about
> >>>>>>> this part in the verifier, don't know how to fix this.
> >>>>>>
> >>>>>> Maybe something related to commit be2ef8161572 ("bpf: allow precision
> >>>>>> tracking
> >>>>>> for programs with subprogs") and/or the related ones?
> >>>>>>
> >>>>>>
> >>>>>>> This can be reproduced on:
> >>>>>>
> >>>>>>> HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
> >>>>>>> libelf
> >>>>>>> git tree: bpf-next
> >>>>>>> console log: https://pastebin.com/raw/45hZ7iqm
> >>>>>>> kernel config: https://pastebin.com/raw/0pu1CHRm
> >>>>>>> C reproducer: https://pastebin.com/raw/tqsiezvT
> >>>>>>
> >>>>>>> func#0 @0
> >>>>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
> >>>>>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
> >>>>>>> 2: (18) r6 = 0xffff888027358000 ;
> >>>>>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> >>>>>>> 4: (18) r7 = 0xffff88802735a000 ;
> >>>>>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
> >>>>>>> 6: (18) r8 = 0xffff88802735e000 ;
> >>>>>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
> >>>>>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
> >>>>>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
> >>>>>>> last_idx 10 first_idx 0
> >>>>>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
> >>>>>>> 11: R9_w=156779191205888
> >>>>>>> 11: (85) call #0
> >>>>>>> 12: (cc) w2 s>>= w7
> >>>>>
> >>>>> w2 should have been set to NOT_INIT (because r1-r5 are clobbered by
> >>>>> calls) and rejected here as !read_ok (see check_reg_arg()) before
> >>>>> attempting to mark precision for r2. Can you please try to debug and
> >>>>> understand why that didn't happen here?
> >>>>
> >>>> The verifier is doing the right thing here and the 'call #0' does
> >>>> implicitly cleared r1-r5.
> >>>>
> >>>> So for 'w2 s>>= w7', since w2 is used, the verifier tries to find
> >>>> its definition by backtracing. It encountered 'call #0', which clears
> >>>
> >>> and that's what I'm saying is incorrect. Normally we'd get !read_ok
> >>> error because s>>= is both READ and WRITE on w2, which is
> >>> uninitialized after call instruction according to BPF ABI. And that's
> >>> what actually seems to happen correctly in my (simpler) tests locally.
> >>> But something is special about this specific repro that somehow either
> >>> bypasses this logic, or attempts to mark precision before we get to
> >>> that test. That's what we should investigate. I haven't tried to run
> >>> this specific repro locally yet, so can't tell for sure.
> >>>
> >>
> >> So, the reason why w2 is not marked as uninit is that the kfunc call in
> >> the BPF program is invalid, "call #0", imm is zero, right?
> >
> > Yes, "call #0" is invalid. As the code below
> >
> >> /* skip for now, but return error when we find this in
> > fixup_kfunc_call */
> >> if (!insn->imm)
> >> return 0;
> >
> > The error report will be delayed later in fixup_kfunc_call().
> >
> > static int fixup_kfunc_call(struct bpf_verifier_env *env, struct
> > bpf_insn *insn,
> > struct bpf_insn *insn_buf, int insn_idx,
> > int *cnt)
> > {
> > const struct bpf_kfunc_desc *desc;
> >
> > if (!insn->imm) {
> > verbose(env, "invalid kernel function call not
> > eliminated in verifier pass\n");
> > return -EINVAL;
> > }
> >
> >
> >> In check_kfunc_call(), it skips this error temporarily:
> >>
> >> /* skip for now, but return error when we find this in fixup_kfunc_call */
> >> if (!insn->imm)
> >> return 0;
> >>
> >> So the kfunc call is the previous instruction before "w2 s>>= w7", this
> >> leads to the warning in backtrack_insn():
> >>
> >> /* regular helper call sets R0 */
> >> *reg_mask &= ~1;
> >> if (*reg_mask & 0x3f) {
> >> /* if backtracing was looking for registers R1-R5
> >> * they should have been found already.
> >> */
> >> verbose(env, "BUG regs %x\n", *reg_mask);
> >> WARN_ONCE(1, "verifier backtracking bug”);
> >> return -EFAULT;
> >> }
> >
> > The main triggering the backtrack_insn() is due to
> >
> > } else {
> > /* scalar += pointer
> > * This is legal, but we have to
> > reverse our
> > * src/dest handling in computing the range
> > */
> > err = mark_chain_precision(env,
> > insn->dst_reg);
> > if (err)
> > return err;
> > return adjust_ptr_min_max_vals(env, insn,
> > src_reg,
> > dst_reg);
> > }
> >
> >
> > unc#0 @0
> > 0: R1=ctx(off=0,imm=0) R10=fp0
> > 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
> > 2: (18) r6 = 0xffff888100d29000 ;
> > R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> > 4: (18) r7 = 0xffff888100d2a000 ;
> > R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
> > 6: (18) r8 = 0xffff888100d2ac00 ;
> > R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
> > 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
> > 10: (36) if w9 >= 0xffffffe3 goto pc+1
> > last_idx 10 first_idx 0
> > regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
> > 11: R9_w=156779191205888
> > 11: (85) call #0
> > 12: (cc) w2 s>>= w7
> > last_idx 12 first_idx 12
> > parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
> > R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> > R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,v0
> > last_idx 11 first_idx 0
> > regs=4 stack=0 before 11: (85) call #0
> > BUG regs 4
> >
> > For insn 12, 'w2 s>>= w7', w2 is a scalar and w7 is a map_ptr. Hence,
> > based on the above verifier code, mark_chain_precision() is triggered.
> >
> > Not sure what is the purpose of this test. But to make it succeed,
> > first "call #0" need to change to a valid kfunc call, and second, you
> > might want to change 'w2 s>>= w7' to e.g., 'w9 s>>= w7' to avoid
> > precision tracking.
> >
>
> The purpose is not to make the test "succeed", the verifier temporarily
> skips the invalid kfunc insn "call #0", but this insn triggered a warning
> in backtrack_insn(), while it is supposed to reject the program either
> due to insn#12 32bit ptr alu or insn#11 invalid kfunc.
>
> Maybe something like the bellow, after applying the patch, the reproducer
> is rejected:
>
> func#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
> 2: (18) r6 = 0xffff88817d563000 ; R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> 4: (18) r7 = 0xffff888171ee9000 ; R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
> 6: (18) r8 = 0xffff888171ee8000 ; R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
> 10: (36) if w9 >= 0xffffffe3 goto pc+1
> last_idx 10 first_idx 0
> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
> 11: R9_w=156779191205888
> 11: (85) call #0
> 12: (cc) w2 s>>= w7
> last_idx 12 first_idx 12
> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0) R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0) R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0) R9_w=156779191205888 R10=fp0
> last_idx 11 first_idx 0
> regs=4 stack=0 before 11: (85) call #0
> regs=4 stack=0 before 10: (36) if w9 >= 0xffffffe3 goto pc+1
> regs=4 stack=0 before 8: (18) r9 = 0x8e9700000000
> regs=4 stack=0 before 6: (18) r8 = 0xffff888171ee8000
> regs=4 stack=0 before 4: (18) r7 = 0xffff888171ee9000
> regs=4 stack=0 before 2: (18) r6 = 0xffff88817d563000
> regs=4 stack=0 before 0: (18) r2 = 0x8000000000000
> R2 32-bit pointer arithmetic prohibited
> processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 4a25375ebb0d..abc7e96d826f 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2743,6 +2743,9 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx,
> *reg_mask |= sreg;
> } else if (class == BPF_JMP || class == BPF_JMP32) {
> if (opcode == BPF_CALL) {
> + /* skip for now, should return error when we find this in fixup_kfunc_call */
> + if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL && insn->imm == 0)
> + return 0;
Makes sense to me. Please submit as an official patch
with s/return 0/return -ENOTSUPP/
Also 'skip for now' isn't quite correct here.
In check_kfunc_call() it's correct, since invalid kfunc with imm==0
could be eliminated during dead code elimination,
but since we're walking this insn here in backtrack_insn
the dead code elimination is not going to kick in.
So it's surely invalid kfunc call if we see it in backtrack_insn.
The comment should probably be something like:
/* kfunc with imm==0 is invalid and fixup_kfunc_call will catch
this error later. Make backtracking conservative with ENOTSUPP. */
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2023-01-01 19:19 ` Yonghong Song
@ 2023-01-02 9:42 ` Hao Sun
2023-01-03 18:27 ` Alexei Starovoitov
0 siblings, 1 reply; 15+ messages in thread
From: Hao Sun @ 2023-01-02 9:42 UTC (permalink / raw)
To: Yonghong Song
Cc: Andrii Nakryiko, Stanislav Fomichev, Andrii Nakryiko, bpf,
Alexei Starovoitov, Daniel Borkmann, John Fastabend,
Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Hao Luo,
Jiri Olsa, David Miller, Jakub Kicinski, Jesper Dangaard Brouer,
Linux Kernel Mailing List
Yonghong Song <yhs@meta.com> 于2023年1月2日周一 03:20写道：
>
>
>
> On 12/30/22 1:44 AM, Hao Sun wrote:
>>
>>
>> Andrii Nakryiko <andrii.nakryiko@gmail.com> 于2022年12月30日周五 06:16写道：
>>>
>>> On Tue, Dec 27, 2022 at 9:24 PM Yonghong Song <yhs@meta.com> wrote:
>>>>
>>>>
>>>>
>>>> On 12/20/22 4:30 PM, Andrii Nakryiko wrote:
>>>>> On Mon, Dec 19, 2022 at 11:13 AM <sdf@google.com> wrote:
>>>>>>
>>>>>> On 12/19, Hao Sun wrote:
>>>>>>> Hi,
>>>>>>
>>>>>>> The following backtracking bug can be triggered on the latest bpf-next and
>>>>>>> Linux 6.1 with the C prog provided. I don't have enough knowledge about
>>>>>>> this part in the verifier, don't know how to fix this.
>>>>>>
>>>>>> Maybe something related to commit be2ef8161572 ("bpf: allow precision
>>>>>> tracking
>>>>>> for programs with subprogs") and/or the related ones?
>>>>>>
>>>>>>
>>>>>>> This can be reproduced on:
>>>>>>
>>>>>>> HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
>>>>>>> libelf
>>>>>>> git tree: bpf-next
>>>>>>> console log: https://pastebin.com/raw/45hZ7iqm
>>>>>>> kernel config: https://pastebin.com/raw/0pu1CHRm
>>>>>>> C reproducer: https://pastebin.com/raw/tqsiezvT
>>>>>>
>>>>>>> func#0 @0
>>>>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>>>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>>>>>> 2: (18) r6 = 0xffff888027358000 ;
>>>>>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>>>>> 4: (18) r7 = 0xffff88802735a000 ;
>>>>>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>>>>>> 6: (18) r8 = 0xffff88802735e000 ;
>>>>>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>>>>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>>>>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>>>>>> last_idx 10 first_idx 0
>>>>>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>>>>>> 11: R9_w=156779191205888
>>>>>>> 11: (85) call #0
>>>>>>> 12: (cc) w2 s>>= w7
>>>>>
>>>>> w2 should have been set to NOT_INIT (because r1-r5 are clobbered by
>>>>> calls) and rejected here as !read_ok (see check_reg_arg()) before
>>>>> attempting to mark precision for r2. Can you please try to debug and
>>>>> understand why that didn't happen here?
>>>>
>>>> The verifier is doing the right thing here and the 'call #0' does
>>>> implicitly cleared r1-r5.
>>>>
>>>> So for 'w2 s>>= w7', since w2 is used, the verifier tries to find
>>>> its definition by backtracing. It encountered 'call #0', which clears
>>>
>>> and that's what I'm saying is incorrect. Normally we'd get !read_ok
>>> error because s>>= is both READ and WRITE on w2, which is
>>> uninitialized after call instruction according to BPF ABI. And that's
>>> what actually seems to happen correctly in my (simpler) tests locally.
>>> But something is special about this specific repro that somehow either
>>> bypasses this logic, or attempts to mark precision before we get to
>>> that test. That's what we should investigate. I haven't tried to run
>>> this specific repro locally yet, so can't tell for sure.
>>>
>>
>> So, the reason why w2 is not marked as uninit is that the kfunc call in
>> the BPF program is invalid, "call #0", imm is zero, right?
>
> Yes, "call #0" is invalid. As the code below
>
>> /* skip for now, but return error when we find this in
> fixup_kfunc_call */
>> if (!insn->imm)
>> return 0;
>
> The error report will be delayed later in fixup_kfunc_call().
>
> static int fixup_kfunc_call(struct bpf_verifier_env *env, struct
> bpf_insn *insn,
> struct bpf_insn *insn_buf, int insn_idx,
> int *cnt)
> {
> const struct bpf_kfunc_desc *desc;
>
> if (!insn->imm) {
> verbose(env, "invalid kernel function call not
> eliminated in verifier pass\n");
> return -EINVAL;
> }
>
>
>> In check_kfunc_call(), it skips this error temporarily:
>>
>> /* skip for now, but return error when we find this in fixup_kfunc_call */
>> if (!insn->imm)
>> return 0;
>>
>> So the kfunc call is the previous instruction before "w2 s>>= w7", this
>> leads to the warning in backtrack_insn():
>>
>> /* regular helper call sets R0 */
>> *reg_mask &= ~1;
>> if (*reg_mask & 0x3f) {
>> /* if backtracing was looking for registers R1-R5
>> * they should have been found already.
>> */
>> verbose(env, "BUG regs %x\n", *reg_mask);
>> WARN_ONCE(1, "verifier backtracking bug”);
>> return -EFAULT;
>> }
>
> The main triggering the backtrack_insn() is due to
>
> } else {
> /* scalar += pointer
> * This is legal, but we have to
> reverse our
> * src/dest handling in computing the range
> */
> err = mark_chain_precision(env,
> insn->dst_reg);
> if (err)
> return err;
> return adjust_ptr_min_max_vals(env, insn,
> src_reg,
> dst_reg);
> }
>
>
> unc#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
> 2: (18) r6 = 0xffff888100d29000 ;
> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> 4: (18) r7 = 0xffff888100d2a000 ;
> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
> 6: (18) r8 = 0xffff888100d2ac00 ;
> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
> 10: (36) if w9 >= 0xffffffe3 goto pc+1
> last_idx 10 first_idx 0
> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
> 11: R9_w=156779191205888
> 11: (85) call #0
> 12: (cc) w2 s>>= w7
> last_idx 12 first_idx 12
> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
> R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,v0
> last_idx 11 first_idx 0
> regs=4 stack=0 before 11: (85) call #0
> BUG regs 4
>
> For insn 12, 'w2 s>>= w7', w2 is a scalar and w7 is a map_ptr. Hence,
> based on the above verifier code, mark_chain_precision() is triggered.
>
> Not sure what is the purpose of this test. But to make it succeed,
> first "call #0" need to change to a valid kfunc call, and second, you
> might want to change 'w2 s>>= w7' to e.g., 'w9 s>>= w7' to avoid
> precision tracking.
>
The purpose is not to make the test "succeed", the verifier temporarily
skips the invalid kfunc insn "call #0", but this insn triggered a warning
in backtrack_insn(), while it is supposed to reject the program either
due to insn#12 32bit ptr alu or insn#11 invalid kfunc.
Maybe something like the bellow, after applying the patch, the reproducer
is rejected:
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
2: (18) r6 = 0xffff88817d563000 ; R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
4: (18) r7 = 0xffff888171ee9000 ; R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
6: (18) r8 = 0xffff888171ee8000 ; R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
10: (36) if w9 >= 0xffffffe3 goto pc+1
last_idx 10 first_idx 0
regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
11: R9_w=156779191205888
11: (85) call #0
12: (cc) w2 s>>= w7
last_idx 12 first_idx 12
parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0) R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0) R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0) R9_w=156779191205888 R10=fp0
last_idx 11 first_idx 0
regs=4 stack=0 before 11: (85) call #0
regs=4 stack=0 before 10: (36) if w9 >= 0xffffffe3 goto pc+1
regs=4 stack=0 before 8: (18) r9 = 0x8e9700000000
regs=4 stack=0 before 6: (18) r8 = 0xffff888171ee8000
regs=4 stack=0 before 4: (18) r7 = 0xffff888171ee9000
regs=4 stack=0 before 2: (18) r6 = 0xffff88817d563000
regs=4 stack=0 before 0: (18) r2 = 0x8000000000000
R2 32-bit pointer arithmetic prohibited
processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 4a25375ebb0d..abc7e96d826f 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2743,6 +2743,9 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx,
*reg_mask |= sreg;
} else if (class == BPF_JMP || class == BPF_JMP32) {
if (opcode == BPF_CALL) {
+ /* skip for now, should return error when we find this in fixup_kfunc_call */
+ if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL && insn->imm == 0)
+ return 0;
if (insn->src_reg == BPF_PSEUDO_CALL)
return -ENOTSUPP;
/* BPF helpers that invoke callback subprogs are
>>
>> Any idea or hint on how to fix this?
>>
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2022-12-30 9:44 ` Hao Sun
@ 2023-01-01 19:19 ` Yonghong Song
2023-01-02 9:42 ` Hao Sun
0 siblings, 1 reply; 15+ messages in thread
From: Yonghong Song @ 2023-01-01 19:19 UTC (permalink / raw)
To: Hao Sun, Andrii Nakryiko
Cc: Stanislav Fomichev, Andrii Nakryiko, bpf, Alexei Starovoitov,
Daniel Borkmann, John Fastabend, Martin KaFai Lau, Song Liu,
Yonghong Song, KP Singh, Hao Luo, Jiri Olsa, David Miller,
Jakub Kicinski, Jesper Dangaard Brouer,
Linux Kernel Mailing List
On 12/30/22 1:44 AM, Hao Sun wrote:
>
>
> Andrii Nakryiko <andrii.nakryiko@gmail.com> 于2022年12月30日周五 06:16写道：
>>
>> On Tue, Dec 27, 2022 at 9:24 PM Yonghong Song <yhs@meta.com> wrote:
>>>
>>>
>>>
>>> On 12/20/22 4:30 PM, Andrii Nakryiko wrote:
>>>> On Mon, Dec 19, 2022 at 11:13 AM <sdf@google.com> wrote:
>>>>>
>>>>> On 12/19, Hao Sun wrote:
>>>>>> Hi,
>>>>>
>>>>>> The following backtracking bug can be triggered on the latest bpf-next and
>>>>>> Linux 6.1 with the C prog provided. I don't have enough knowledge about
>>>>>> this part in the verifier, don't know how to fix this.
>>>>>
>>>>> Maybe something related to commit be2ef8161572 ("bpf: allow precision
>>>>> tracking
>>>>> for programs with subprogs") and/or the related ones?
>>>>>
>>>>>
>>>>>> This can be reproduced on:
>>>>>
>>>>>> HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
>>>>>> libelf
>>>>>> git tree: bpf-next
>>>>>> console log: https://pastebin.com/raw/45hZ7iqm
>>>>>> kernel config: https://pastebin.com/raw/0pu1CHRm
>>>>>> C reproducer: https://pastebin.com/raw/tqsiezvT
>>>>>
>>>>>> func#0 @0
>>>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>>>>> 2: (18) r6 = 0xffff888027358000 ;
>>>>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>>>> 4: (18) r7 = 0xffff88802735a000 ;
>>>>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>>>>> 6: (18) r8 = 0xffff88802735e000 ;
>>>>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>>>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>>>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>>>>> last_idx 10 first_idx 0
>>>>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>>>>> 11: R9_w=156779191205888
>>>>>> 11: (85) call #0
>>>>>> 12: (cc) w2 s>>= w7
>>>>
>>>> w2 should have been set to NOT_INIT (because r1-r5 are clobbered by
>>>> calls) and rejected here as !read_ok (see check_reg_arg()) before
>>>> attempting to mark precision for r2. Can you please try to debug and
>>>> understand why that didn't happen here?
>>>
>>> The verifier is doing the right thing here and the 'call #0' does
>>> implicitly cleared r1-r5.
>>>
>>> So for 'w2 s>>= w7', since w2 is used, the verifier tries to find
>>> its definition by backtracing. It encountered 'call #0', which clears
>>
>> and that's what I'm saying is incorrect. Normally we'd get !read_ok
>> error because s>>= is both READ and WRITE on w2, which is
>> uninitialized after call instruction according to BPF ABI. And that's
>> what actually seems to happen correctly in my (simpler) tests locally.
>> But something is special about this specific repro that somehow either
>> bypasses this logic, or attempts to mark precision before we get to
>> that test. That's what we should investigate. I haven't tried to run
>> this specific repro locally yet, so can't tell for sure.
>>
>
> So, the reason why w2 is not marked as uninit is that the kfunc call in
> the BPF program is invalid, "call #0", imm is zero, right?
Yes, "call #0" is invalid. As the code below
> /* skip for now, but return error when we find this in
fixup_kfunc_call */
> if (!insn->imm)
> return 0;
The error report will be delayed later in fixup_kfunc_call().
static int fixup_kfunc_call(struct bpf_verifier_env *env, struct
bpf_insn *insn,
struct bpf_insn *insn_buf, int insn_idx,
int *cnt)
{
const struct bpf_kfunc_desc *desc;
if (!insn->imm) {
verbose(env, "invalid kernel function call not
eliminated in verifier pass\n");
return -EINVAL;
}
> In check_kfunc_call(), it skips this error temporarily:
>
> /* skip for now, but return error when we find this in fixup_kfunc_call */
> if (!insn->imm)
> return 0;
>
> So the kfunc call is the previous instruction before "w2 s>>= w7", this
> leads to the warning in backtrack_insn():
>
> /* regular helper call sets R0 */
> *reg_mask &= ~1;
> if (*reg_mask & 0x3f) {
> /* if backtracing was looking for registers R1-R5
> * they should have been found already.
> */
> verbose(env, "BUG regs %x\n", *reg_mask);
> WARN_ONCE(1, "verifier backtracking bug”);
> return -EFAULT;
> }
The main triggering the backtrack_insn() is due to
} else {
/* scalar += pointer
* This is legal, but we have to
reverse our
* src/dest handling in computing the range
*/
err = mark_chain_precision(env,
insn->dst_reg);
if (err)
return err;
return adjust_ptr_min_max_vals(env, insn,
src_reg,
dst_reg);
}
unc#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
2: (18) r6 = 0xffff888100d29000 ;
R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
4: (18) r7 = 0xffff888100d2a000 ;
R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
6: (18) r8 = 0xffff888100d2ac00 ;
R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
10: (36) if w9 >= 0xffffffe3 goto pc+1
last_idx 10 first_idx 0
regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
11: R9_w=156779191205888
11: (85) call #0
12: (cc) w2 s>>= w7
last_idx 12 first_idx 12
parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0) R8_w=map_ptr(off=0,ks=2396,v0
last_idx 11 first_idx 0
regs=4 stack=0 before 11: (85) call #0
BUG regs 4
For insn 12, 'w2 s>>= w7', w2 is a scalar and w7 is a map_ptr. Hence,
based on the above verifier code, mark_chain_precision() is triggered.
Not sure what is the purpose of this test. But to make it succeed,
first "call #0" need to change to a valid kfunc call, and second, you
might want to change 'w2 s>>= w7' to e.g., 'w9 s>>= w7' to avoid
precision tracking.
>
> Any idea or hint on how to fix this?
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2022-12-29 22:16 ` Andrii Nakryiko
@ 2022-12-30 9:44 ` Hao Sun
2023-01-01 19:19 ` Yonghong Song
0 siblings, 1 reply; 15+ messages in thread
From: Hao Sun @ 2022-12-30 9:44 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Yonghong Song, Stanislav Fomichev, Andrii Nakryiko, bpf,
Alexei Starovoitov, Daniel Borkmann, John Fastabend,
Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Hao Luo,
Jiri Olsa, David Miller, Jakub Kicinski, Jesper Dangaard Brouer,
Linux Kernel Mailing List
Andrii Nakryiko <andrii.nakryiko@gmail.com> 于2022年12月30日周五 06:16写道：
>
> On Tue, Dec 27, 2022 at 9:24 PM Yonghong Song <yhs@meta.com> wrote:
>>
>>
>>
>> On 12/20/22 4:30 PM, Andrii Nakryiko wrote:
>>> On Mon, Dec 19, 2022 at 11:13 AM <sdf@google.com> wrote:
>>>>
>>>> On 12/19, Hao Sun wrote:
>>>>> Hi,
>>>>
>>>>> The following backtracking bug can be triggered on the latest bpf-next and
>>>>> Linux 6.1 with the C prog provided. I don't have enough knowledge about
>>>>> this part in the verifier, don't know how to fix this.
>>>>
>>>> Maybe something related to commit be2ef8161572 ("bpf: allow precision
>>>> tracking
>>>> for programs with subprogs") and/or the related ones?
>>>>
>>>>
>>>>> This can be reproduced on:
>>>>
>>>>> HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
>>>>> libelf
>>>>> git tree: bpf-next
>>>>> console log: https://pastebin.com/raw/45hZ7iqm
>>>>> kernel config: https://pastebin.com/raw/0pu1CHRm
>>>>> C reproducer: https://pastebin.com/raw/tqsiezvT
>>>>
>>>>> func#0 @0
>>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>>>> 2: (18) r6 = 0xffff888027358000 ;
>>>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>>>> 4: (18) r7 = 0xffff88802735a000 ;
>>>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>>>> 6: (18) r8 = 0xffff88802735e000 ;
>>>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>>>> last_idx 10 first_idx 0
>>>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>>>> 11: R9_w=156779191205888
>>>>> 11: (85) call #0
>>>>> 12: (cc) w2 s>>= w7
>>>
>>> w2 should have been set to NOT_INIT (because r1-r5 are clobbered by
>>> calls) and rejected here as !read_ok (see check_reg_arg()) before
>>> attempting to mark precision for r2. Can you please try to debug and
>>> understand why that didn't happen here?
>>
>> The verifier is doing the right thing here and the 'call #0' does
>> implicitly cleared r1-r5.
>>
>> So for 'w2 s>>= w7', since w2 is used, the verifier tries to find
>> its definition by backtracing. It encountered 'call #0', which clears
>
> and that's what I'm saying is incorrect. Normally we'd get !read_ok
> error because s>>= is both READ and WRITE on w2, which is
> uninitialized after call instruction according to BPF ABI. And that's
> what actually seems to happen correctly in my (simpler) tests locally.
> But something is special about this specific repro that somehow either
> bypasses this logic, or attempts to mark precision before we get to
> that test. That's what we should investigate. I haven't tried to run
> this specific repro locally yet, so can't tell for sure.
>
So, the reason why w2 is not marked as uninit is that the kfunc call in
the BPF program is invalid, "call #0", imm is zero, right?
In check_kfunc_call(), it skips this error temporarily:
/* skip for now, but return error when we find this in fixup_kfunc_call */
if (!insn->imm)
return 0;
So the kfunc call is the previous instruction before "w2 s>>= w7", this
leads to the warning in backtrack_insn():
/* regular helper call sets R0 */
*reg_mask &= ~1;
if (*reg_mask & 0x3f) {
/* if backtracing was looking for registers R1-R5
* they should have been found already.
*/
verbose(env, "BUG regs %x\n", *reg_mask);
WARN_ONCE(1, "verifier backtracking bug”);
return -EFAULT;
}
Any idea or hint on how to fix this?
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2022-12-28 5:23 ` Yonghong Song
@ 2022-12-29 22:16 ` Andrii Nakryiko
2022-12-30 9:44 ` Hao Sun
0 siblings, 1 reply; 15+ messages in thread
From: Andrii Nakryiko @ 2022-12-29 22:16 UTC (permalink / raw)
To: Yonghong Song
Cc: sdf, Hao Sun, Andrii Nakryiko, bpf, Alexei Starovoitov,
Daniel Borkmann, John Fastabend, Martin KaFai Lau, Song Liu,
Yonghong Song, KP Singh, Hao Luo, Jiri Olsa, David Miller,
Jakub Kicinski, Jesper Dangaard Brouer,
Linux Kernel Mailing List
On Tue, Dec 27, 2022 at 9:24 PM Yonghong Song <yhs@meta.com> wrote:
>
>
>
> On 12/20/22 4:30 PM, Andrii Nakryiko wrote:
> > On Mon, Dec 19, 2022 at 11:13 AM <sdf@google.com> wrote:
> >>
> >> On 12/19, Hao Sun wrote:
> >>> Hi,
> >>
> >>> The following backtracking bug can be triggered on the latest bpf-next and
> >>> Linux 6.1 with the C prog provided. I don't have enough knowledge about
> >>> this part in the verifier, don't know how to fix this.
> >>
> >> Maybe something related to commit be2ef8161572 ("bpf: allow precision
> >> tracking
> >> for programs with subprogs") and/or the related ones?
> >>
> >>
> >>> This can be reproduced on:
> >>
> >>> HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
> >>> libelf
> >>> git tree: bpf-next
> >>> console log: https://pastebin.com/raw/45hZ7iqm
> >>> kernel config: https://pastebin.com/raw/0pu1CHRm
> >>> C reproducer: https://pastebin.com/raw/tqsiezvT
> >>
> >>> func#0 @0
> >>> 0: R1=ctx(off=0,imm=0) R10=fp0
> >>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
> >>> 2: (18) r6 = 0xffff888027358000 ;
> >>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> >>> 4: (18) r7 = 0xffff88802735a000 ;
> >>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
> >>> 6: (18) r8 = 0xffff88802735e000 ;
> >>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
> >>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
> >>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
> >>> last_idx 10 first_idx 0
> >>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
> >>> 11: R9_w=156779191205888
> >>> 11: (85) call #0
> >>> 12: (cc) w2 s>>= w7
> >
> > w2 should have been set to NOT_INIT (because r1-r5 are clobbered by
> > calls) and rejected here as !read_ok (see check_reg_arg()) before
> > attempting to mark precision for r2. Can you please try to debug and
> > understand why that didn't happen here?
>
> The verifier is doing the right thing here and the 'call #0' does
> implicitly cleared r1-r5.
>
> So for 'w2 s>>= w7', since w2 is used, the verifier tries to find
> its definition by backtracing. It encountered 'call #0', which clears
and that's what I'm saying is incorrect. Normally we'd get !read_ok
error because s>>= is both READ and WRITE on w2, which is
uninitialized after call instruction according to BPF ABI. And that's
what actually seems to happen correctly in my (simpler) tests locally.
But something is special about this specific repro that somehow either
bypasses this logic, or attempts to mark precision before we get to
that test. That's what we should investigate. I haven't tried to run
this specific repro locally yet, so can't tell for sure.
> r1-r5. Since w2 is not defined, the verifier issued the error:
> BUG regs 4
>
> The specific verifier code is in backtrack_insn():
>
> } else if (class == BPF_JMP || class == BPF_JMP32) {
> if (opcode == BPF_CALL) {
> if (insn->src_reg == BPF_PSEUDO_CALL)
> return -ENOTSUPP;
> /* BPF helpers that invoke callback subprogs are
> * equivalent to BPF_PSEUDO_CALL above
> */
> if (insn->src_reg == 0 &&
> is_callback_calling_function(insn->imm))
> return -ENOTSUPP;
> /* regular helper call sets R0 */
> *reg_mask &= ~1;
> if (*reg_mask & 0x3f) {
> /* if backtracing was looking for
> registers R1-R5
> * they should have been found already.
> */
> verbose(env, "BUG regs %x\n", *reg_mask);
> WARN_ONCE(1, "verifier backtracking bug");
> return -EFAULT;
> }
> }
>
> Note that the above mask '0x3f' which corresponds to registers r1-r5.
> If it tries to find the definition for any of them, 'BUG regs <mask>'
> will be printed out.
>
>
> >
> >
> >>> last_idx 12 first_idx 12
> >>> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
> >>> R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> >>> R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0)
> >>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0) R9_w=156779191205888 R10=fp0
> >>> last_idx 11 first_idx 0
> >>> regs=4 stack=0 before 11: (85) call #0
> >>> BUG regs 4
> >>> processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1
> >>> peak_states 1 mark_read 1
> >>
> >>> ------------[ cut here ]------------
> >>> verifier backtracking bug
> >>> WARNING: CPU: 6 PID: 8646 at kernel/bpf/verifier.c:2756 backtrack_insn
> >>> kernel/bpf/verifier.c:2756 [inline]
> >>> WARNING: CPU: 6 PID: 8646 at kernel/bpf/verifier.c:2756
> >>> __mark_chain_precision+0x1baf/0x1d70 kernel/bpf/verifier.c:3065
> >>> Modules linked in:
> >>> CPU: 6 PID: 8646 Comm: a.out Not tainted 6.1.0-09634-g0e43662e61f2 #146
> >>> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Arch Linux
> >>> 1.16.1-1-1 04/01/2014
> >>> RIP: 0010:backtrack_insn kernel/bpf/verifier.c:2756 [inline]
> >>> RIP: 0010:__mark_chain_precision+0x1baf/0x1d70 kernel/bpf/verifier.c:3065
> >>> Code: 0d 31 ff 89 de e8 91 ec ed ff 84 db 0f 85 ef fe ff ff e8 b4 f0
> >>> ed ff 48 c7 c7 e0 8f 53 8a c6 05 28 71 ab 0d 01 e8 83 b3 1e 08 <0f> 0b
> >>> e9 50 f8 ff ff 48 8b 74 24 38 48 c7 c7 80 d0 63 8d e8 49 46
> >>> RSP: 0018:ffffc9001463f1a0 EFLAGS: 00010282
> >>> RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000000
> >>> RDX: ffff888020470000 RSI: ffffffff816662c0 RDI: fffff520028c7e26
> >>> RBP: 0000000000000004 R08: 0000000000000005 R09: 0000000000000000
> >>> R10: 0000000080000000 R11: 0000000000000000 R12: 0000000000000020
> >>> R13: dffffc0000000000 R14: 000000000000000b R15: ffff88802be74000
> >>> FS: 00007fd3daeb8440(0000) GS:ffff888063980000(0000)
> >>> knlGS:0000000000000000
> >>> CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> >>> CR2: 0000000020000240 CR3: 0000000017394000 CR4: 0000000000750ee0
> >>> PKRU: 55555554
> >>> Call Trace:
> >>> <TASK>
> >>> mark_chain_precision kernel/bpf/verifier.c:3165 [inline]
> >>> adjust_reg_min_max_vals+0x981/0x58d0 kernel/bpf/verifier.c:10715
> >>> check_alu_op+0x380/0x1820 kernel/bpf/verifier.c:10928
> >>> do_check kernel/bpf/verifier.c:13821 [inline]
> >>> do_check_common+0x1c3b/0xe520 kernel/bpf/verifier.c:16289
> >>> do_check_main kernel/bpf/verifier.c:16352 [inline]
> >>> bpf_check+0x83b4/0xb310 kernel/bpf/verifier.c:16936
> >>> bpf_prog_load+0xf7a/0x21a0 kernel/bpf/syscall.c:2619
> >>> __sys_bpf+0xf03/0x5840 kernel/bpf/syscall.c:4979
> >>> __do_sys_bpf kernel/bpf/syscall.c:5083 [inline]
> >>> __se_sys_bpf kernel/bpf/syscall.c:5081 [inline]
> >>> __x64_sys_bpf+0x78/0xc0 kernel/bpf/syscall.c:5081
> >>> do_syscall_x64 arch/x86/entry/common.c:50 [inline]
> >>> do_syscall_64+0x38/0xb0 arch/x86/entry/common.c:80
> >>> entry_SYSCALL_64_after_hwframe+0x63/0xcd
> >>> RIP: 0033:0x7fd3da8e4469
> >>> Code: 00 f3 c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 40 00 48 89 f8 48
> >>> 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d
> >>> 01 f0 ff ff 73 01 c3 48 8b 0d ff 49 2b 00 f7 d8 64 89 01 48
> >>> RSP: 002b:00007fff090c1a78 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
> >>> RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007fd3da8e4469
> >>> RDX: 0000000000000080 RSI: 0000000020000840 RDI: 0000000000000005
> >>> RBP: 00007fff090c2a90 R08: 00007fd3da92e160 R09: 0000000000000000
> >>> R10: 0000000000000000 R11: 0000000000000246 R12: 0000561aefc006c0
> >>> R13: 00007fff090c2b70 R14: 0000000000000000 R15: 0000000000000000
> >>> </TASK>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2022-12-21 0:30 ` Andrii Nakryiko
@ 2022-12-28 5:23 ` Yonghong Song
2022-12-29 22:16 ` Andrii Nakryiko
0 siblings, 1 reply; 15+ messages in thread
From: Yonghong Song @ 2022-12-28 5:23 UTC (permalink / raw)
To: Andrii Nakryiko, sdf
Cc: Hao Sun, Andrii Nakryiko, bpf, Alexei Starovoitov,
Daniel Borkmann, John Fastabend, Martin KaFai Lau, Song Liu,
Yonghong Song, KP Singh, Hao Luo, Jiri Olsa, David Miller,
Jakub Kicinski, Jesper Dangaard Brouer,
Linux Kernel Mailing List
On 12/20/22 4:30 PM, Andrii Nakryiko wrote:
> On Mon, Dec 19, 2022 at 11:13 AM <sdf@google.com> wrote:
>>
>> On 12/19, Hao Sun wrote:
>>> Hi,
>>
>>> The following backtracking bug can be triggered on the latest bpf-next and
>>> Linux 6.1 with the C prog provided. I don't have enough knowledge about
>>> this part in the verifier, don't know how to fix this.
>>
>> Maybe something related to commit be2ef8161572 ("bpf: allow precision
>> tracking
>> for programs with subprogs") and/or the related ones?
>>
>>
>>> This can be reproduced on:
>>
>>> HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
>>> libelf
>>> git tree: bpf-next
>>> console log: https://pastebin.com/raw/45hZ7iqm
>>> kernel config: https://pastebin.com/raw/0pu1CHRm
>>> C reproducer: https://pastebin.com/raw/tqsiezvT
>>
>>> func#0 @0
>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
>>> 2: (18) r6 = 0xffff888027358000 ;
>>> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>> 4: (18) r7 = 0xffff88802735a000 ;
>>> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>> 6: (18) r8 = 0xffff88802735e000 ;
>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
>>> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
>>> 10: (36) if w9 >= 0xffffffe3 goto pc+1
>>> last_idx 10 first_idx 0
>>> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
>>> 11: R9_w=156779191205888
>>> 11: (85) call #0
>>> 12: (cc) w2 s>>= w7
>
> w2 should have been set to NOT_INIT (because r1-r5 are clobbered by
> calls) and rejected here as !read_ok (see check_reg_arg()) before
> attempting to mark precision for r2. Can you please try to debug and
> understand why that didn't happen here?
The verifier is doing the right thing here and the 'call #0' does
implicitly cleared r1-r5.
So for 'w2 s>>= w7', since w2 is used, the verifier tries to find
its definition by backtracing. It encountered 'call #0', which clears
r1-r5. Since w2 is not defined, the verifier issued the error:
BUG regs 4
The specific verifier code is in backtrack_insn():
} else if (class == BPF_JMP || class == BPF_JMP32) {
if (opcode == BPF_CALL) {
if (insn->src_reg == BPF_PSEUDO_CALL)
return -ENOTSUPP;
/* BPF helpers that invoke callback subprogs are
* equivalent to BPF_PSEUDO_CALL above
*/
if (insn->src_reg == 0 &&
is_callback_calling_function(insn->imm))
return -ENOTSUPP;
/* regular helper call sets R0 */
*reg_mask &= ~1;
if (*reg_mask & 0x3f) {
/* if backtracing was looking for
registers R1-R5
* they should have been found already.
*/
verbose(env, "BUG regs %x\n", *reg_mask);
WARN_ONCE(1, "verifier backtracking bug");
return -EFAULT;
}
}
Note that the above mask '0x3f' which corresponds to registers r1-r5.
If it tries to find the definition for any of them, 'BUG regs <mask>'
will be printed out.
>
>
>>> last_idx 12 first_idx 12
>>> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
>>> R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
>>> R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0)
>>> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0) R9_w=156779191205888 R10=fp0
>>> last_idx 11 first_idx 0
>>> regs=4 stack=0 before 11: (85) call #0
>>> BUG regs 4
>>> processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1
>>> peak_states 1 mark_read 1
>>
>>> ------------[ cut here ]------------
>>> verifier backtracking bug
>>> WARNING: CPU: 6 PID: 8646 at kernel/bpf/verifier.c:2756 backtrack_insn
>>> kernel/bpf/verifier.c:2756 [inline]
>>> WARNING: CPU: 6 PID: 8646 at kernel/bpf/verifier.c:2756
>>> __mark_chain_precision+0x1baf/0x1d70 kernel/bpf/verifier.c:3065
>>> Modules linked in:
>>> CPU: 6 PID: 8646 Comm: a.out Not tainted 6.1.0-09634-g0e43662e61f2 #146
>>> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Arch Linux
>>> 1.16.1-1-1 04/01/2014
>>> RIP: 0010:backtrack_insn kernel/bpf/verifier.c:2756 [inline]
>>> RIP: 0010:__mark_chain_precision+0x1baf/0x1d70 kernel/bpf/verifier.c:3065
>>> Code: 0d 31 ff 89 de e8 91 ec ed ff 84 db 0f 85 ef fe ff ff e8 b4 f0
>>> ed ff 48 c7 c7 e0 8f 53 8a c6 05 28 71 ab 0d 01 e8 83 b3 1e 08 <0f> 0b
>>> e9 50 f8 ff ff 48 8b 74 24 38 48 c7 c7 80 d0 63 8d e8 49 46
>>> RSP: 0018:ffffc9001463f1a0 EFLAGS: 00010282
>>> RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000000
>>> RDX: ffff888020470000 RSI: ffffffff816662c0 RDI: fffff520028c7e26
>>> RBP: 0000000000000004 R08: 0000000000000005 R09: 0000000000000000
>>> R10: 0000000080000000 R11: 0000000000000000 R12: 0000000000000020
>>> R13: dffffc0000000000 R14: 000000000000000b R15: ffff88802be74000
>>> FS: 00007fd3daeb8440(0000) GS:ffff888063980000(0000)
>>> knlGS:0000000000000000
>>> CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
>>> CR2: 0000000020000240 CR3: 0000000017394000 CR4: 0000000000750ee0
>>> PKRU: 55555554
>>> Call Trace:
>>> <TASK>
>>> mark_chain_precision kernel/bpf/verifier.c:3165 [inline]
>>> adjust_reg_min_max_vals+0x981/0x58d0 kernel/bpf/verifier.c:10715
>>> check_alu_op+0x380/0x1820 kernel/bpf/verifier.c:10928
>>> do_check kernel/bpf/verifier.c:13821 [inline]
>>> do_check_common+0x1c3b/0xe520 kernel/bpf/verifier.c:16289
>>> do_check_main kernel/bpf/verifier.c:16352 [inline]
>>> bpf_check+0x83b4/0xb310 kernel/bpf/verifier.c:16936
>>> bpf_prog_load+0xf7a/0x21a0 kernel/bpf/syscall.c:2619
>>> __sys_bpf+0xf03/0x5840 kernel/bpf/syscall.c:4979
>>> __do_sys_bpf kernel/bpf/syscall.c:5083 [inline]
>>> __se_sys_bpf kernel/bpf/syscall.c:5081 [inline]
>>> __x64_sys_bpf+0x78/0xc0 kernel/bpf/syscall.c:5081
>>> do_syscall_x64 arch/x86/entry/common.c:50 [inline]
>>> do_syscall_64+0x38/0xb0 arch/x86/entry/common.c:80
>>> entry_SYSCALL_64_after_hwframe+0x63/0xcd
>>> RIP: 0033:0x7fd3da8e4469
>>> Code: 00 f3 c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 40 00 48 89 f8 48
>>> 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d
>>> 01 f0 ff ff 73 01 c3 48 8b 0d ff 49 2b 00 f7 d8 64 89 01 48
>>> RSP: 002b:00007fff090c1a78 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
>>> RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007fd3da8e4469
>>> RDX: 0000000000000080 RSI: 0000000020000840 RDI: 0000000000000005
>>> RBP: 00007fff090c2a90 R08: 00007fd3da92e160 R09: 0000000000000000
>>> R10: 0000000000000000 R11: 0000000000000246 R12: 0000561aefc006c0
>>> R13: 00007fff090c2b70 R14: 0000000000000000 R15: 0000000000000000
>>> </TASK>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2022-12-19 19:13 ` sdf
@ 2022-12-21 0:30 ` Andrii Nakryiko
2022-12-28 5:23 ` Yonghong Song
0 siblings, 1 reply; 15+ messages in thread
From: Andrii Nakryiko @ 2022-12-21 0:30 UTC (permalink / raw)
To: sdf
Cc: Hao Sun, Andrii Nakryiko, bpf, Alexei Starovoitov,
Daniel Borkmann, John Fastabend, Martin KaFai Lau, Song Liu,
Yonghong Song, KP Singh, Hao Luo, Jiri Olsa, David Miller,
Jakub Kicinski, Jesper Dangaard Brouer,
Linux Kernel Mailing List
On Mon, Dec 19, 2022 at 11:13 AM <sdf@google.com> wrote:
>
> On 12/19, Hao Sun wrote:
> > Hi,
>
> > The following backtracking bug can be triggered on the latest bpf-next and
> > Linux 6.1 with the C prog provided. I don't have enough knowledge about
> > this part in the verifier, don't know how to fix this.
>
> Maybe something related to commit be2ef8161572 ("bpf: allow precision
> tracking
> for programs with subprogs") and/or the related ones?
>
>
> > This can be reproduced on:
>
> > HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
> > libelf
> > git tree: bpf-next
> > console log: https://pastebin.com/raw/45hZ7iqm
> > kernel config: https://pastebin.com/raw/0pu1CHRm
> > C reproducer: https://pastebin.com/raw/tqsiezvT
>
> > func#0 @0
> > 0: R1=ctx(off=0,imm=0) R10=fp0
> > 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
> > 2: (18) r6 = 0xffff888027358000 ;
> > R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> > 4: (18) r7 = 0xffff88802735a000 ;
> > R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
> > 6: (18) r8 = 0xffff88802735e000 ;
> > R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
> > 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
> > 10: (36) if w9 >= 0xffffffe3 goto pc+1
> > last_idx 10 first_idx 0
> > regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
> > 11: R9_w=156779191205888
> > 11: (85) call #0
> > 12: (cc) w2 s>>= w7
w2 should have been set to NOT_INIT (because r1-r5 are clobbered by
calls) and rejected here as !read_ok (see check_reg_arg()) before
attempting to mark precision for r2. Can you please try to debug and
understand why that didn't happen here?
> > last_idx 12 first_idx 12
> > parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
> > R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> > R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0)
> > R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0) R9_w=156779191205888 R10=fp0
> > last_idx 11 first_idx 0
> > regs=4 stack=0 before 11: (85) call #0
> > BUG regs 4
> > processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1
> > peak_states 1 mark_read 1
>
> > ------------[ cut here ]------------
> > verifier backtracking bug
> > WARNING: CPU: 6 PID: 8646 at kernel/bpf/verifier.c:2756 backtrack_insn
> > kernel/bpf/verifier.c:2756 [inline]
> > WARNING: CPU: 6 PID: 8646 at kernel/bpf/verifier.c:2756
> > __mark_chain_precision+0x1baf/0x1d70 kernel/bpf/verifier.c:3065
> > Modules linked in:
> > CPU: 6 PID: 8646 Comm: a.out Not tainted 6.1.0-09634-g0e43662e61f2 #146
> > Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Arch Linux
> > 1.16.1-1-1 04/01/2014
> > RIP: 0010:backtrack_insn kernel/bpf/verifier.c:2756 [inline]
> > RIP: 0010:__mark_chain_precision+0x1baf/0x1d70 kernel/bpf/verifier.c:3065
> > Code: 0d 31 ff 89 de e8 91 ec ed ff 84 db 0f 85 ef fe ff ff e8 b4 f0
> > ed ff 48 c7 c7 e0 8f 53 8a c6 05 28 71 ab 0d 01 e8 83 b3 1e 08 <0f> 0b
> > e9 50 f8 ff ff 48 8b 74 24 38 48 c7 c7 80 d0 63 8d e8 49 46
> > RSP: 0018:ffffc9001463f1a0 EFLAGS: 00010282
> > RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000000
> > RDX: ffff888020470000 RSI: ffffffff816662c0 RDI: fffff520028c7e26
> > RBP: 0000000000000004 R08: 0000000000000005 R09: 0000000000000000
> > R10: 0000000080000000 R11: 0000000000000000 R12: 0000000000000020
> > R13: dffffc0000000000 R14: 000000000000000b R15: ffff88802be74000
> > FS: 00007fd3daeb8440(0000) GS:ffff888063980000(0000)
> > knlGS:0000000000000000
> > CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> > CR2: 0000000020000240 CR3: 0000000017394000 CR4: 0000000000750ee0
> > PKRU: 55555554
> > Call Trace:
> > <TASK>
> > mark_chain_precision kernel/bpf/verifier.c:3165 [inline]
> > adjust_reg_min_max_vals+0x981/0x58d0 kernel/bpf/verifier.c:10715
> > check_alu_op+0x380/0x1820 kernel/bpf/verifier.c:10928
> > do_check kernel/bpf/verifier.c:13821 [inline]
> > do_check_common+0x1c3b/0xe520 kernel/bpf/verifier.c:16289
> > do_check_main kernel/bpf/verifier.c:16352 [inline]
> > bpf_check+0x83b4/0xb310 kernel/bpf/verifier.c:16936
> > bpf_prog_load+0xf7a/0x21a0 kernel/bpf/syscall.c:2619
> > __sys_bpf+0xf03/0x5840 kernel/bpf/syscall.c:4979
> > __do_sys_bpf kernel/bpf/syscall.c:5083 [inline]
> > __se_sys_bpf kernel/bpf/syscall.c:5081 [inline]
> > __x64_sys_bpf+0x78/0xc0 kernel/bpf/syscall.c:5081
> > do_syscall_x64 arch/x86/entry/common.c:50 [inline]
> > do_syscall_64+0x38/0xb0 arch/x86/entry/common.c:80
> > entry_SYSCALL_64_after_hwframe+0x63/0xcd
> > RIP: 0033:0x7fd3da8e4469
> > Code: 00 f3 c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 40 00 48 89 f8 48
> > 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d
> > 01 f0 ff ff 73 01 c3 48 8b 0d ff 49 2b 00 f7 d8 64 89 01 48
> > RSP: 002b:00007fff090c1a78 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
> > RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007fd3da8e4469
> > RDX: 0000000000000080 RSI: 0000000020000840 RDI: 0000000000000005
> > RBP: 00007fff090c2a90 R08: 00007fd3da92e160 R09: 0000000000000000
> > R10: 0000000000000000 R11: 0000000000000246 R12: 0000561aefc006c0
> > R13: 00007fff090c2b70 R14: 0000000000000000 R15: 0000000000000000
> > </TASK>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: WARNING in __mark_chain_precision
2022-12-19 7:50 Hao Sun
@ 2022-12-19 19:13 ` sdf
2022-12-21 0:30 ` Andrii Nakryiko
0 siblings, 1 reply; 15+ messages in thread
From: sdf @ 2022-12-19 19:13 UTC (permalink / raw)
To: Hao Sun, Andrii Nakryiko
Cc: bpf, Alexei Starovoitov, Daniel Borkmann, John Fastabend,
Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Hao Luo,
Jiri Olsa, David Miller, Jakub Kicinski, Jesper Dangaard Brouer,
Linux Kernel Mailing List
On 12/19, Hao Sun wrote:
> Hi,
> The following backtracking bug can be triggered on the latest bpf-next and
> Linux 6.1 with the C prog provided. I don't have enough knowledge about
> this part in the verifier, don't know how to fix this.
Maybe something related to commit be2ef8161572 ("bpf: allow precision
tracking
for programs with subprogs") and/or the related ones?
> This can be reproduced on:
> HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate
> libelf
> git tree: bpf-next
> console log: https://pastebin.com/raw/45hZ7iqm
> kernel config: https://pastebin.com/raw/0pu1CHRm
> C reproducer: https://pastebin.com/raw/tqsiezvT
> func#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
> 2: (18) r6 = 0xffff888027358000 ;
> R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> 4: (18) r7 = 0xffff88802735a000 ;
> R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
> 6: (18) r8 = 0xffff88802735e000 ;
> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
> 8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
> 10: (36) if w9 >= 0xffffffe3 goto pc+1
> last_idx 10 first_idx 0
> regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
> 11: R9_w=156779191205888
> 11: (85) call #0
> 12: (cc) w2 s>>= w7
> last_idx 12 first_idx 12
> parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
> R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
> R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0)
> R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0) R9_w=156779191205888 R10=fp0
> last_idx 11 first_idx 0
> regs=4 stack=0 before 11: (85) call #0
> BUG regs 4
> processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1
> peak_states 1 mark_read 1
> ------------[ cut here ]------------
> verifier backtracking bug
> WARNING: CPU: 6 PID: 8646 at kernel/bpf/verifier.c:2756 backtrack_insn
> kernel/bpf/verifier.c:2756 [inline]
> WARNING: CPU: 6 PID: 8646 at kernel/bpf/verifier.c:2756
> __mark_chain_precision+0x1baf/0x1d70 kernel/bpf/verifier.c:3065
> Modules linked in:
> CPU: 6 PID: 8646 Comm: a.out Not tainted 6.1.0-09634-g0e43662e61f2 #146
> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Arch Linux
> 1.16.1-1-1 04/01/2014
> RIP: 0010:backtrack_insn kernel/bpf/verifier.c:2756 [inline]
> RIP: 0010:__mark_chain_precision+0x1baf/0x1d70 kernel/bpf/verifier.c:3065
> Code: 0d 31 ff 89 de e8 91 ec ed ff 84 db 0f 85 ef fe ff ff e8 b4 f0
> ed ff 48 c7 c7 e0 8f 53 8a c6 05 28 71 ab 0d 01 e8 83 b3 1e 08 <0f> 0b
> e9 50 f8 ff ff 48 8b 74 24 38 48 c7 c7 80 d0 63 8d e8 49 46
> RSP: 0018:ffffc9001463f1a0 EFLAGS: 00010282
> RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000000
> RDX: ffff888020470000 RSI: ffffffff816662c0 RDI: fffff520028c7e26
> RBP: 0000000000000004 R08: 0000000000000005 R09: 0000000000000000
> R10: 0000000080000000 R11: 0000000000000000 R12: 0000000000000020
> R13: dffffc0000000000 R14: 000000000000000b R15: ffff88802be74000
> FS: 00007fd3daeb8440(0000) GS:ffff888063980000(0000)
> knlGS:0000000000000000
> CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> CR2: 0000000020000240 CR3: 0000000017394000 CR4: 0000000000750ee0
> PKRU: 55555554
> Call Trace:
> <TASK>
> mark_chain_precision kernel/bpf/verifier.c:3165 [inline]
> adjust_reg_min_max_vals+0x981/0x58d0 kernel/bpf/verifier.c:10715
> check_alu_op+0x380/0x1820 kernel/bpf/verifier.c:10928
> do_check kernel/bpf/verifier.c:13821 [inline]
> do_check_common+0x1c3b/0xe520 kernel/bpf/verifier.c:16289
> do_check_main kernel/bpf/verifier.c:16352 [inline]
> bpf_check+0x83b4/0xb310 kernel/bpf/verifier.c:16936
> bpf_prog_load+0xf7a/0x21a0 kernel/bpf/syscall.c:2619
> __sys_bpf+0xf03/0x5840 kernel/bpf/syscall.c:4979
> __do_sys_bpf kernel/bpf/syscall.c:5083 [inline]
> __se_sys_bpf kernel/bpf/syscall.c:5081 [inline]
> __x64_sys_bpf+0x78/0xc0 kernel/bpf/syscall.c:5081
> do_syscall_x64 arch/x86/entry/common.c:50 [inline]
> do_syscall_64+0x38/0xb0 arch/x86/entry/common.c:80
> entry_SYSCALL_64_after_hwframe+0x63/0xcd
> RIP: 0033:0x7fd3da8e4469
> Code: 00 f3 c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 40 00 48 89 f8 48
> 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d
> 01 f0 ff ff 73 01 c3 48 8b 0d ff 49 2b 00 f7 d8 64 89 01 48
> RSP: 002b:00007fff090c1a78 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
> RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007fd3da8e4469
> RDX: 0000000000000080 RSI: 0000000020000840 RDI: 0000000000000005
> RBP: 00007fff090c2a90 R08: 00007fd3da92e160 R09: 0000000000000000
> R10: 0000000000000000 R11: 0000000000000246 R12: 0000561aefc006c0
> R13: 00007fff090c2b70 R14: 0000000000000000 R15: 0000000000000000
> </TASK>
^ permalink raw reply [flat|nested] 15+ messages in thread
* WARNING in __mark_chain_precision
@ 2022-12-19 7:50 Hao Sun
2022-12-19 19:13 ` sdf
0 siblings, 1 reply; 15+ messages in thread
From: Hao Sun @ 2022-12-19 7:50 UTC (permalink / raw)
To: bpf, Alexei Starovoitov, Daniel Borkmann
Cc: John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu,
Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa,
David Miller, Jakub Kicinski, Jesper Dangaard Brouer,
Linux Kernel Mailing List
Hi,
The following backtracking bug can be triggered on the latest bpf-next and
Linux 6.1 with the C prog provided. I don't have enough knowledge about
this part in the verifier, don't know how to fix this.
This can be reproduced on:
HEAD commit: 0e43662e61f2 tools/resolve_btfids: Use pkg-config to locate libelf
git tree: bpf-next
console log: https://pastebin.com/raw/45hZ7iqm
kernel config: https://pastebin.com/raw/0pu1CHRm
C reproducer: https://pastebin.com/raw/tqsiezvT
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (18) r2 = 0x8000000000000 ; R2_w=2251799813685248
2: (18) r6 = 0xffff888027358000 ;
R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
4: (18) r7 = 0xffff88802735a000 ; R7_w=map_ptr(off=0,ks=156,vs=2624,imm=0)
6: (18) r8 = 0xffff88802735e000 ; R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0)
8: (18) r9 = 0x8e9700000000 ; R9_w=156779191205888
10: (36) if w9 >= 0xffffffe3 goto pc+1
last_idx 10 first_idx 0
regs=200 stack=0 before 8: (18) r9 = 0x8e9700000000
11: R9_w=156779191205888
11: (85) call #0
12: (cc) w2 s>>= w7
last_idx 12 first_idx 12
parent didn't have regs=4 stack=0 marks: R1=ctx(off=0,imm=0)
R2_rw=P2251799813685248 R6_w=map_ptr(off=0,ks=3032,vs=3664,imm=0)
R7_rw=map_ptr(off=0,ks=156,vs=2624,imm=0)
R8_w=map_ptr(off=0,ks=2396,vs=76,imm=0) R9_w=156779191205888 R10=fp0
last_idx 11 first_idx 0
regs=4 stack=0 before 11: (85) call #0
BUG regs 4
processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1
peak_states 1 mark_read 1
------------[ cut here ]------------
verifier backtracking bug
WARNING: CPU: 6 PID: 8646 at kernel/bpf/verifier.c:2756 backtrack_insn
kernel/bpf/verifier.c:2756 [inline]
WARNING: CPU: 6 PID: 8646 at kernel/bpf/verifier.c:2756
__mark_chain_precision+0x1baf/0x1d70 kernel/bpf/verifier.c:3065
Modules linked in:
CPU: 6 PID: 8646 Comm: a.out Not tainted 6.1.0-09634-g0e43662e61f2 #146
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Arch Linux
1.16.1-1-1 04/01/2014
RIP: 0010:backtrack_insn kernel/bpf/verifier.c:2756 [inline]
RIP: 0010:__mark_chain_precision+0x1baf/0x1d70 kernel/bpf/verifier.c:3065
Code: 0d 31 ff 89 de e8 91 ec ed ff 84 db 0f 85 ef fe ff ff e8 b4 f0
ed ff 48 c7 c7 e0 8f 53 8a c6 05 28 71 ab 0d 01 e8 83 b3 1e 08 <0f> 0b
e9 50 f8 ff ff 48 8b 74 24 38 48 c7 c7 80 d0 63 8d e8 49 46
RSP: 0018:ffffc9001463f1a0 EFLAGS: 00010282
RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000000
RDX: ffff888020470000 RSI: ffffffff816662c0 RDI: fffff520028c7e26
RBP: 0000000000000004 R08: 0000000000000005 R09: 0000000000000000
R10: 0000000080000000 R11: 0000000000000000 R12: 0000000000000020
R13: dffffc0000000000 R14: 000000000000000b R15: ffff88802be74000
FS: 00007fd3daeb8440(0000) GS:ffff888063980000(0000) knlGS:0000000000000000
CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 0000000020000240 CR3: 0000000017394000 CR4: 0000000000750ee0
PKRU: 55555554
Call Trace:
<TASK>
mark_chain_precision kernel/bpf/verifier.c:3165 [inline]
adjust_reg_min_max_vals+0x981/0x58d0 kernel/bpf/verifier.c:10715
check_alu_op+0x380/0x1820 kernel/bpf/verifier.c:10928
do_check kernel/bpf/verifier.c:13821 [inline]
do_check_common+0x1c3b/0xe520 kernel/bpf/verifier.c:16289
do_check_main kernel/bpf/verifier.c:16352 [inline]
bpf_check+0x83b4/0xb310 kernel/bpf/verifier.c:16936
bpf_prog_load+0xf7a/0x21a0 kernel/bpf/syscall.c:2619
__sys_bpf+0xf03/0x5840 kernel/bpf/syscall.c:4979
__do_sys_bpf kernel/bpf/syscall.c:5083 [inline]
__se_sys_bpf kernel/bpf/syscall.c:5081 [inline]
__x64_sys_bpf+0x78/0xc0 kernel/bpf/syscall.c:5081
do_syscall_x64 arch/x86/entry/common.c:50 [inline]
do_syscall_64+0x38/0xb0 arch/x86/entry/common.c:80
entry_SYSCALL_64_after_hwframe+0x63/0xcd
RIP: 0033:0x7fd3da8e4469
Code: 00 f3 c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 40 00 48 89 f8 48
89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d
01 f0 ff ff 73 01 c3 48 8b 0d ff 49 2b 00 f7 d8 64 89 01 48
RSP: 002b:00007fff090c1a78 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007fd3da8e4469
RDX: 0000000000000080 RSI: 0000000020000840 RDI: 0000000000000005
RBP: 00007fff090c2a90 R08: 00007fd3da92e160 R09: 0000000000000000
R10: 0000000000000000 R11: 0000000000000246 R12: 0000561aefc006c0
R13: 00007fff090c2b70 R14: 0000000000000000 R15: 0000000000000000
</TASK>
^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2023-01-04 16:56 UTC | newest]
Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-07-08 15:27 WARNING in __mark_chain_precision syzbot
2019-07-09 3:49 ` Andrii Nakryiko
2019-07-09 4:08 ` syzbot
2022-12-19 7:50 Hao Sun
2022-12-19 19:13 ` sdf
2022-12-21 0:30 ` Andrii Nakryiko
2022-12-28 5:23 ` Yonghong Song
2022-12-29 22:16 ` Andrii Nakryiko
2022-12-30 9:44 ` Hao Sun
2023-01-01 19:19 ` Yonghong Song
2023-01-02 9:42 ` Hao Sun
2023-01-03 18:27 ` Alexei Starovoitov
2023-01-04 5:47 ` Yonghong Song
2023-01-04 8:52 ` Hao Sun
2023-01-04 16:51 ` Yonghong Song
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.