bisecting cause commit starting from 56e337f2cf1326323844927a04e9dbce9a244835 building syzkaller on dfa9a8ed6b12b102fe3625ca8fc786aa86d54a5a testing commit 56e337f2cf1326323844927a04e9dbce9a244835 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 0505bf514add7672429c0cef83d26a283f1ba2e12a2f5c9ae39a312baa14c1b9 all runs: crashed: WARNING in kvm_mmu_notifier_invalidate_range_start testing release v5.16 testing commit df0cc57e057f18e44dac8e6c18aba47ab53202f9 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 1fd9ab6ec52dc5d6eec160897ae3403fe7938723519a9996a423afd6588ef1fc all runs: OK # git bisect start 56e337f2cf1326323844927a04e9dbce9a244835 df0cc57e057f18e44dac8e6c18aba47ab53202f9 Bisecting: 6915 revisions left to test after this (roughly 13 steps) [22ef12195e13c5ec58320dbf99ef85059a2c0820] Merge tag 'staging-5.17-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging testing commit 22ef12195e13c5ec58320dbf99ef85059a2c0820 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 04d46026e084d612a807c5f958c39b2182194586d2492dda165a95dddcbaaf8d all runs: OK # git bisect good 22ef12195e13c5ec58320dbf99ef85059a2c0820 Bisecting: 3458 revisions left to test after this (roughly 12 steps) [0c947b893d69231a9add855939da7c66237ab44f] Merge tag '5.17-rc-part1-smb3-fixes' of git://git.samba.org/sfrench/cifs-2.6 testing commit 0c947b893d69231a9add855939da7c66237ab44f compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: a09d938a4ed02eb4b90dc403a86a70a07c6507620485b60c053c532d3f7514aa all runs: crashed: WARNING in kvm_mmu_notifier_invalidate_range_start # git bisect bad 0c947b893d69231a9add855939da7c66237ab44f Bisecting: 1719 revisions left to test after this (roughly 11 steps) [3fb561b1e0bf4c75bc5f4d799845b08fa5ab3853] Merge tag 'mips_5.17' of git://git.kernel.org/pub/scm/linux/kernel/git/mips/linux testing commit 3fb561b1e0bf4c75bc5f4d799845b08fa5ab3853 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 8c285f708bc2ddd7f2614302f26470631335d2fca86659c208bbe1bab640ccf0 all runs: OK # git bisect good 3fb561b1e0bf4c75bc5f4d799845b08fa5ab3853 Bisecting: 839 revisions left to test after this (roughly 10 steps) [f56caedaf94f9ced5dbfcdb0060a3e788d2078af] Merge branch 'akpm' (patches from Andrew) testing commit f56caedaf94f9ced5dbfcdb0060a3e788d2078af compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: ef3d9d17de4852bd502b5a05ea8c0ace444032bd6e74aa1c7ceceb06c0a36b10 run #0: basic kernel testing failed: BUG: program execution failed: executor NUM: EOF run #1: OK run #2: OK run #3: OK run #4: OK run #5: OK run #6: OK run #7: OK run #8: OK run #9: OK # git bisect good f56caedaf94f9ced5dbfcdb0060a3e788d2078af Bisecting: 460 revisions left to test after this (roughly 9 steps) [cb3f09f9afe5286c0aed7a1c5cc71495de166efb] Merge tag 'hyperv-next-signed-20220114' of git://git.kernel.org/pub/scm/linux/kernel/git/hyperv/linux testing commit cb3f09f9afe5286c0aed7a1c5cc71495de166efb compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: c0b1631b24db8f9632e53594bfd6f0f2a1c2fddac8f79c3bf37fe17e4bffc386 all runs: OK # git bisect good cb3f09f9afe5286c0aed7a1c5cc71495de166efb Bisecting: 225 revisions left to test after this (roughly 8 steps) [1b0c9d00aa2cf93dd26760dc9e4cf4725fc5ec03] Merge tag 'kvm-riscv-5.17-1' of https://github.com/kvm-riscv/linux into HEAD testing commit 1b0c9d00aa2cf93dd26760dc9e4cf4725fc5ec03 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: cf313ead88b6a99114b70632fb0e4da623e66beb117bb61f4b9bcbdf40447a21 all runs: crashed: WARNING in kvm_mmu_notifier_invalidate_range_start # git bisect bad 1b0c9d00aa2cf93dd26760dc9e4cf4725fc5ec03 Bisecting: 117 revisions left to test after this (roughly 7 steps) [93b350f884c451d3cb75e6e3814266cf2d2afab1] Merge branch 'kvm-on-hv-msrbm-fix' into HEAD testing commit 93b350f884c451d3cb75e6e3814266cf2d2afab1 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 84656228be83c5d5b4aad891eab0ecfecd65e09c1fb2f8a6bea7daa19f82a52b all runs: crashed: WARNING in kvm_mmu_notifier_invalidate_range_start # git bisect bad 93b350f884c451d3cb75e6e3814266cf2d2afab1 Bisecting: 58 revisions left to test after this (roughly 6 steps) [75c89e5272fba7f8c8c4e4d7dc23be1b82e4b2d8] KVM: s390: Clear valid_wakeup in kvm_s390_handle_wait(), not in arch hook testing commit 75c89e5272fba7f8c8c4e4d7dc23be1b82e4b2d8 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 8b2a1350806f5279eb4a9e93279645b11e1c81b4fe1e1e962e0a146f094f7ec2 all runs: crashed: WARNING in kvm_mmu_notifier_invalidate_range_start # git bisect bad 75c89e5272fba7f8c8c4e4d7dc23be1b82e4b2d8 Bisecting: 28 revisions left to test after this (roughly 5 steps) [ed922739c9199bf515a3e7fec3e319ce1edeef2a] KVM: Use interval tree to do fast hva lookup in memslots testing commit ed922739c9199bf515a3e7fec3e319ce1edeef2a compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: e5fe44a2f65569c6b96032b220b720635913486a03b15343f8da6dcd2f6c8373 all runs: crashed: WARNING in kvm_mmu_notifier_invalidate_range_start # git bisect bad ed922739c9199bf515a3e7fec3e319ce1edeef2a Bisecting: 14 revisions left to test after this (roughly 4 steps) [3b1816177bfe2ce245a0f1194970644a79951570] KVM: MIPS: Drop pr_debug from memslot commit to avoid using "mem" testing commit 3b1816177bfe2ce245a0f1194970644a79951570 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 647507955345a97d95561891448d438f0c64becdae9085cd2036305bd8461857 all runs: OK # git bisect good 3b1816177bfe2ce245a0f1194970644a79951570 Bisecting: 7 revisions left to test after this (roughly 3 steps) [77aedf26fe5d2795cd6aa1a75a8dd62dbac503e6] KVM: x86: Don't assume old/new memslots are non-NULL at memslot commit testing commit 77aedf26fe5d2795cd6aa1a75a8dd62dbac503e6 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: dbc53163612aff2727d6a7a99cdb3b40db6b8a73f3c21efa79067df5abb30a31 run #0: basic kernel testing failed: BUG: program execution failed: executor NUM: EOF run #1: OK run #2: OK run #3: OK run #4: OK run #5: OK run #6: OK run #7: OK run #8: OK run #9: OK # git bisect good 77aedf26fe5d2795cd6aa1a75a8dd62dbac503e6 Bisecting: 3 revisions left to test after this (roughly 2 steps) [f5756029eef501bcd39ecd844968e4fb3055c1bd] KVM: x86: Use nr_memslot_pages to avoid traversing the memslots array testing commit f5756029eef501bcd39ecd844968e4fb3055c1bd compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: fe57cf852958fc205c04ac6fa3039cd8ec35260ef948d0e99907733605c49557 all runs: OK # git bisect good f5756029eef501bcd39ecd844968e4fb3055c1bd Bisecting: 1 revision left to test after this (roughly 1 step) [1e8617d37fc36407f9fce9c08ef8d254613c00de] KVM: Move WARN on invalid memslot index to update_memslots() testing commit 1e8617d37fc36407f9fce9c08ef8d254613c00de compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: e2602f66b4f495c88525f92e0a4d4ee1b6ee23513026e86dc1f070bd8016796b all runs: OK # git bisect good 1e8617d37fc36407f9fce9c08ef8d254613c00de Bisecting: 0 revisions left to test after this (roughly 0 steps) [26b8345abc75a7404716864710930407b7d873f9] KVM: Resolve memslot ID via a hash table instead of via a static array testing commit 26b8345abc75a7404716864710930407b7d873f9 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: b1c8f17473a31f92e468fd4b518b55d824bf0b832568b365907660df4eaa223a all runs: OK # git bisect good 26b8345abc75a7404716864710930407b7d873f9 ed922739c9199bf515a3e7fec3e319ce1edeef2a is the first bad commit commit ed922739c9199bf515a3e7fec3e319ce1edeef2a Author: Maciej S. Szmigiero Date: Mon Dec 6 20:54:28 2021 +0100 KVM: Use interval tree to do fast hva lookup in memslots The current memslots implementation only allows quick binary search by gfn, quick lookup by hva is not possible - the implementation has to do a linear scan of the whole memslots array, even though the operation being performed might apply just to a single memslot. This significantly hurts performance of per-hva operations with higher memslot counts. Since hva ranges can overlap between memslots an interval tree is needed for tracking them. [sean: handle interval tree updates in kvm_replace_memslot()] Signed-off-by: Maciej S. Szmigiero Message-Id: arch/arm64/kvm/Kconfig | 1 + arch/mips/kvm/Kconfig | 1 + arch/powerpc/kvm/Kconfig | 1 + arch/s390/kvm/Kconfig | 1 + arch/x86/kvm/Kconfig | 1 + include/linux/kvm_host.h | 3 +++ virt/kvm/kvm_main.c | 53 +++++++++++++++++++++++++++++++++++------------- 7 files changed, 47 insertions(+), 14 deletions(-) culprit signature: e5fe44a2f65569c6b96032b220b720635913486a03b15343f8da6dcd2f6c8373 parent signature: b1c8f17473a31f92e468fd4b518b55d824bf0b832568b365907660df4eaa223a revisions tested: 16, total time: 2h44m37.41095733s (build: 1h59m28.913428486s, test: 43m34.258997835s) first bad commit: ed922739c9199bf515a3e7fec3e319ce1edeef2a KVM: Use interval tree to do fast hva lookup in memslots recipients (to): ["gor@linux.ibm.com" "hca@linux.ibm.com" "linux-s390@vger.kernel.org" "maciej.szmigiero@oracle.com" "tsbogend@alpha.franken.de"] recipients (cc): ["agordeev@linux.ibm.com" "aleksandar.qemu.devel@gmail.com" "alexandru.elisei@arm.com" "benh@kernel.crashing.org" "borntraeger@linux.ibm.com" "bp@alien8.de" "catalin.marinas@arm.com" "chenhuacai@kernel.org" "dave.hansen@linux.intel.com" "david@redhat.com" "dja@axtens.net" "frankja@linux.ibm.com" "hpa@zytor.com" "imbrenda@linux.ibm.com" "james.morse@arm.com" "jmattson@google.com" "joro@8bytes.org" "kvm@vger.kernel.org" "kvmarm@lists.cs.columbia.edu" "linux-arm-kernel@lists.infradead.org" "linux-kernel@vger.kernel.org" "linux-mips@vger.kernel.org" "linuxppc-dev@lists.ozlabs.org" "lukas.bulwahn@gmail.com" "maz@kernel.org" "mingo@redhat.com" "mpe@ellerman.id.au" "paulus@samba.org" "pbonzini@redhat.com" "seanjc@google.com" "suzuki.poulose@arm.com" "tglx@linutronix.de" "vkuznets@redhat.com" "wanpengli@tencent.com" "will@kernel.org" "x86@kernel.org"] crash: WARNING in kvm_mmu_notifier_invalidate_range_start ------------[ cut here ]------------ WARNING: CPU: 1 PID: 4052 at arch/x86/kvm/../../../virt/kvm/kvm_main.c:530 trace_kvm_unmap_hva_range include/trace/events/kvm.h:441 [inline] WARNING: CPU: 1 PID: 4052 at arch/x86/kvm/../../../virt/kvm/kvm_main.c:530 kvm_mmu_notifier_invalidate_range_start+0x6c3/0x820 arch/x86/kvm/../../../virt/kvm/kvm_main.c:698 Modules linked in: CPU: 1 PID: 4052 Comm: syz-executor157 Not tainted 5.16.0-rc2-syzkaller #0 Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 01/01/2011 RIP: 0010:__kvm_handle_hva_range arch/x86/kvm/../../../virt/kvm/kvm_main.c:530 [inline] RIP: 0010:kvm_mmu_notifier_invalidate_range_start+0x6c3/0x820 arch/x86/kvm/../../../virt/kvm/kvm_main.c:712 Code: 80 3d a8 f0 63 0b 00 75 d7 48 c7 c2 e0 ed c1 88 be b9 01 00 00 48 c7 c7 e0 f1 c1 88 c6 05 8c f0 63 0b 01 e8 cc 3a 2d 07 eb b6 <0f> 0b e9 a0 fd ff ff 0f 0b e9 77 fd ff ff 0f 0b e9 3c fa ff ff 0f RSP: 0018:ffffc9000273f988 EFLAGS: 00010246 RAX: 0000000080000000 RBX: 000000002000d000 RCX: 0000000000000000 RDX: 0000000000000001 RSI: 0000000000000004 RDI: 0000000000000001 RBP: ffffc90001aff0a8 R08: 0000000000000000 R09: ffffc90001af61d3 R10: fffff5200035ec3a R11: 0000000000000000 R12: ffffc90001af6000 R13: ffffc90001af61d0 R14: dffffc0000000000 R15: ffffc9000273fc08 FS: 0000555555a39300(0000) GS:ffff8880b9f00000(0000) knlGS:0000000000000000 CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 CR2: 0000560c4906f098 CR3: 00000000703b1000 CR4: 00000000003526e0 DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400 Call Trace: mn_hlist_invalidate_range_start mm/mmu_notifier.c:493 [inline] __mmu_notifier_invalidate_range_start+0x1e0/0x690 mm/mmu_notifier.c:548 mmu_notifier_invalidate_range_start include/linux/mmu_notifier.h:459 [inline] move_page_tables+0x1af7/0x2690 mm/mremap.c:498 move_vma+0x39f/0xdd0 mm/mremap.c:629 __do_sys_mremap+0x390/0x1180 mm/mremap.c:1059 do_syscall_x64 arch/x86/entry/common.c:50 [inline] do_syscall_64+0x35/0xb0 arch/x86/entry/common.c:80 entry_SYSCALL_64_after_hwframe+0x44/0xae RIP: 0033:0x7f3762ec3bb9 Code: 28 c3 e8 2a 14 00 00 66 2e 0f 1f 84 00 00 00 00 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 c7 c1 c0 ff ff ff f7 d8 64 89 01 48 RSP: 002b:00007ffd263d2728 EFLAGS: 00000246 ORIG_RAX: 0000000000000019 RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007f3762ec3bb9 RDX: 0000000000001000 RSI: fffffffffffffe74 RDI: 000000002000d000 RBP: 00007f3762e87d60 R08: 0000000020007000 R09: 0000000000000000 R10: 0000000000000003 R11: 0000000000000246 R12: 00007f3762e87df0 R13: 0000000000000000 R14: 0000000000000000 R15: 0000000000000000