bisecting cause commit starting from addb0679839a1f74da6ec742137558be244dd0e9 building syzkaller on 7795ae03c0d2358a40130693e40e0fcab5232ed2 testing commit addb0679839a1f74da6ec742137558be244dd0e9 with gcc (GCC) 8.1.0 run #0: crashed: possible deadlock in neigh_change_state run #1: crashed: possible deadlock in neigh_change_state run #2: crashed: possible deadlock in neigh_change_state run #3: crashed: possible deadlock in neigh_change_state run #4: crashed: possible deadlock in neigh_change_state run #5: crashed: possible deadlock in neigh_change_state run #6: crashed: WARNING: possible circular locking dependency detected run #7: crashed: possible deadlock in neigh_change_state run #8: crashed: possible deadlock in neigh_change_state run #9: crashed: possible deadlock in neigh_change_state testing release v4.19 testing commit 84df9525b0c27f3ebc2ebb1864fa62a97fdedb7d with gcc (GCC) 8.1.0 all runs: OK # git bisect start addb0679839a1f74da6ec742137558be244dd0e9 84df9525b0c27f3ebc2ebb1864fa62a97fdedb7d Bisecting: 7937 revisions left to test after this (roughly 13 steps) [dad4f140edaa3f6bb452b6913d41af1ffd672e45] Merge branch 'xarray' of git://git.infradead.org/users/willy/linux-dax testing commit dad4f140edaa3f6bb452b6913d41af1ffd672e45 with gcc (GCC) 8.1.0 all runs: OK # git bisect good dad4f140edaa3f6bb452b6913d41af1ffd672e45 Bisecting: 3952 revisions left to test after this (roughly 12 steps) [59fc453b21f767f2fb0ff4dc0a947e9b9c9e6d14] Merge branch 'akpm' (patches from Andrew) testing commit 59fc453b21f767f2fb0ff4dc0a947e9b9c9e6d14 with gcc (GCC) 8.1.0 all runs: OK # git bisect good 59fc453b21f767f2fb0ff4dc0a947e9b9c9e6d14 Bisecting: 1976 revisions left to test after this (roughly 11 steps) [d2a36971ef595069b7a600d1144c2e0881a930a1] net: phy: don't allow __set_phy_supported to add unsupported modes testing commit d2a36971ef595069b7a600d1144c2e0881a930a1 with gcc (GCC) 8.1.0 all runs: OK # git bisect good d2a36971ef595069b7a600d1144c2e0881a930a1 Bisecting: 950 revisions left to test after this (roughly 10 steps) [ce01a56ba3d9a56e9c7dd4662e2753b102a17d62] Merge tag 'wireless-drivers-next-for-davem-2018-11-30' of git://git.kernel.org/pub/scm/linux/kernel/git/kvalo/wireless-drivers-next testing commit ce01a56ba3d9a56e9c7dd4662e2753b102a17d62 with gcc (GCC) 8.1.0 all runs: OK # git bisect good ce01a56ba3d9a56e9c7dd4662e2753b102a17d62 Bisecting: 461 revisions left to test after this (roughly 9 steps) [d387ac13ad12194a62d268a6b7a0633ef832f6bd] Merge tag 'drm-fixes-2018-12-07' of git://anongit.freedesktop.org/drm/drm testing commit d387ac13ad12194a62d268a6b7a0633ef832f6bd with gcc (GCC) 8.1.0 all runs: OK # git bisect good d387ac13ad12194a62d268a6b7a0633ef832f6bd Bisecting: 279 revisions left to test after this (roughly 8 steps) [40e020c129cfc991e8ab4736d2665351ffd1468d] Linux 4.20-rc6 testing commit 40e020c129cfc991e8ab4736d2665351ffd1468d with gcc (GCC) 8.1.0 all runs: OK # git bisect good 40e020c129cfc991e8ab4736d2665351ffd1468d Bisecting: 145 revisions left to test after this (roughly 7 steps) [d8ed257f313f64e9835e61d1365dea95a0a1c9c6] tcp: handle EOR and FIN conditions the same in tcp_tso_should_defer() testing commit d8ed257f313f64e9835e61d1365dea95a0a1c9c6 with gcc (GCC) 8.1.0 run #0: crashed: BUG: corrupted list in neigh_mark_dead run #1: crashed: KASAN: use-after-free Read in neigh_mark_dead run #2: crashed: BUG: corrupted list in ___neigh_create run #3: crashed: BUG: corrupted list in neigh_mark_dead run #4: crashed: BUG: corrupted list in neigh_mark_dead run #5: crashed: BUG: corrupted list in neigh_mark_dead run #6: crashed: BUG: corrupted list in neigh_mark_dead run #7: crashed: BUG: corrupted list in corrupted run #8: crashed: BUG: corrupted list in neigh_mark_dead run #9: crashed: BUG: corrupted list in neigh_mark_dead # git bisect bad d8ed257f313f64e9835e61d1365dea95a0a1c9c6 Bisecting: 66 revisions left to test after this (roughly 6 steps) [d6a4b570d346c335bda4041c7e59d9a413083bc7] Merge branch 'dsa-mtu' testing commit d6a4b570d346c335bda4041c7e59d9a413083bc7 with gcc (GCC) 8.1.0 all runs: OK # git bisect good d6a4b570d346c335bda4041c7e59d9a413083bc7 Bisecting: 33 revisions left to test after this (roughly 5 steps) [381c356e956627d387b7f0944d7616175057504f] net: hns3: rename process_hw_error function testing commit 381c356e956627d387b7f0944d7616175057504f with gcc (GCC) 8.1.0 all runs: OK # git bisect good 381c356e956627d387b7f0944d7616175057504f Bisecting: 16 revisions left to test after this (roughly 4 steps) [83af01ba1c2d38d3075b38af2a2116eb1ebe67e6] Merge branch 'tc-testing-next' testing commit 83af01ba1c2d38d3075b38af2a2116eb1ebe67e6 with gcc (GCC) 8.1.0 run #0: crashed: BUG: corrupted list in ___neigh_create run #1: crashed: KASAN: use-after-free Read in neigh_mark_dead run #2: crashed: BUG: corrupted list in neigh_mark_dead run #3: crashed: BUG: corrupted list in neigh_mark_dead run #4: crashed: BUG: corrupted list in corrupted run #5: crashed: BUG: corrupted list in neigh_mark_dead run #6: crashed: BUG: corrupted list in corrupted run #7: crashed: BUG: corrupted list in neigh_mark_dead run #8: crashed: BUG: corrupted list in neigh_mark_dead run #9: crashed: BUG: corrupted list in neigh_mark_dead # git bisect bad 83af01ba1c2d38d3075b38af2a2116eb1ebe67e6 Bisecting: 8 revisions left to test after this (roughly 3 steps) [c3529177db471b964fbe327ffb801266f0482d64] net: hns3: handle hw errors of SSU testing commit c3529177db471b964fbe327ffb801266f0482d64 with gcc (GCC) 8.1.0 all runs: OK # git bisect good c3529177db471b964fbe327ffb801266f0482d64 Bisecting: 4 revisions left to test after this (roughly 2 steps) [0fbe82e628c817e292ff588cd5847fc935e025f2] net: call sk_dst_reset when set SO_DONTROUTE testing commit 0fbe82e628c817e292ff588cd5847fc935e025f2 with gcc (GCC) 8.1.0 run #0: crashed: BUG: corrupted list in neigh_mark_dead run #1: crashed: BUG: corrupted list in neigh_mark_dead run #2: crashed: BUG: corrupted list in corrupted run #3: crashed: BUG: corrupted list in ___neigh_create run #4: crashed: BUG: corrupted list in ___neigh_create run #5: crashed: KASAN: use-after-free Read in neigh_mark_dead run #6: crashed: BUG: corrupted list in corrupted run #7: crashed: BUG: corrupted list in neigh_mark_dead run #8: crashed: BUG: corrupted list in neigh_mark_dead run #9: crashed: BUG: corrupted list in neigh_mark_dead # git bisect bad 0fbe82e628c817e292ff588cd5847fc935e025f2 Bisecting: 1 revision left to test after this (roughly 1 step) [12edfdfc79860f42fa493f81518e040376b6a5bc] Merge branch 'hns3-error-handling' testing commit 12edfdfc79860f42fa493f81518e040376b6a5bc with gcc (GCC) 8.1.0 all runs: OK # git bisect good 12edfdfc79860f42fa493f81518e040376b6a5bc Bisecting: 0 revisions left to test after this (roughly 0 steps) [58956317c8de52009d1a38a721474c24aef74fe7] neighbor: Improve garbage collection testing commit 58956317c8de52009d1a38a721474c24aef74fe7 with gcc (GCC) 8.1.0 run #0: crashed: KASAN: use-after-free Read in neigh_mark_dead run #1: crashed: KASAN: use-after-free Read in neigh_mark_dead run #2: crashed: BUG: corrupted list in neigh_mark_dead run #3: crashed: KASAN: use-after-free Read in neigh_mark_dead run #4: crashed: KASAN: use-after-free Read in neigh_mark_dead run #5: crashed: BUG: corrupted list in neigh_mark_dead run #6: crashed: BUG: corrupted list in neigh_mark_dead run #7: crashed: BUG: corrupted list in neigh_mark_dead run #8: crashed: BUG: corrupted list in neigh_mark_dead run #9: crashed: BUG: corrupted list in neigh_mark_dead # git bisect bad 58956317c8de52009d1a38a721474c24aef74fe7 58956317c8de52009d1a38a721474c24aef74fe7 is the first bad commit commit 58956317c8de52009d1a38a721474c24aef74fe7 Author: David Ahern Date: Fri Dec 7 12:24:57 2018 -0800 neighbor: Improve garbage collection The existing garbage collection algorithm has a number of problems: 1. The gc algorithm will not evict PERMANENT entries as those entries are managed by userspace, yet the existing algorithm walks the entire hash table which means it always considers PERMANENT entries when looking for entries to evict. In some use cases (e.g., EVPN) there can be tens of thousands of PERMANENT entries leading to wasted CPU cycles when gc kicks in. As an example, with 32k permanent entries, neigh_alloc has been observed taking more than 4 msec per invocation. 2. Currently, when the number of neighbor entries hits gc_thresh2 and the last flush for the table was more than 5 seconds ago gc kicks in walks the entire hash table evicting *all* entries not in PERMANENT or REACHABLE state and not marked as externally learned. There is no discriminator on when the neigh entry was created or if it just moved from REACHABLE to another NUD_VALID state (e.g., NUD_STALE). It is possible for entries to be created or for established neighbor entries to be moved to STALE (e.g., an external node sends an ARP request) right before the 5 second window lapses: -----|---------x|----------|----- t-5 t t+5 If that happens those entries are evicted during gc causing unnecessary thrashing on neighbor entries and userspace caches trying to track them. Further, this contradicts the description of gc_thresh2 which says "Entries older than 5 seconds will be cleared". One workaround is to make gc_thresh2 == gc_thresh3 but that negates the whole point of having separate thresholds. 3. Clearing *all* neigh non-PERMANENT/REACHABLE/externally learned entries when gc_thresh2 is exceeded is over kill and contributes to trashing especially during startup. This patch addresses these problems as follows: 1. Use of a separate list_head to track entries that can be garbage collected along with a separate counter. PERMANENT entries are not added to this list. The gc_thresh parameters are only compared to the new counter, not the total entries in the table. The forced_gc function is updated to only walk this new gc_list looking for entries to evict. 2. Entries are added to the list head at the tail and removed from the front. 3. Entries are only evicted if they were last updated more than 5 seconds ago, adhering to the original intent of gc_thresh2. 4. Forced gc is stopped once the number of gc_entries drops below gc_thresh2. 5. Since gc checks do not apply to PERMANENT entries, gc levels are skipped when allocating a new neighbor for a PERMANENT entry. By extension this means there are no explicit limits on the number of PERMANENT entries that can be created, but this is no different than FIB entries or FDB entries. Signed-off-by: David Ahern Signed-off-by: David S. Miller :040000 040000 24d9e3b96dfd7fb1ad1dd5b4ec793222e6557b5f ef194261e4a6dd9525a809d48bdf7350965b91a5 M Documentation :040000 040000 7f6648160963802ae6d29863ab62cfc06072062f 5a8b8df0eae8625656a1ef41979ad85254b7a894 M include :040000 040000 d79e1d56f9184053712869f7dca789d43dd8630c 1b3ba8ba1f14e19f7da6ac20e38477209545b916 M net revisions tested: 16, total time: 4h13m14.777441495s (build: 1h34m53.15193628s, test: 2h33m15.540577621s) first bad commit: 58956317c8de52009d1a38a721474c24aef74fe7 neighbor: Improve garbage collection cc: ["corbet@lwn.net" "davem@davemloft.net" "dsahern@gmail.com" "linux-doc@vger.kernel.org" "linux-kernel@vger.kernel.org" "netdev@vger.kernel.org"] crash: BUG: corrupted list in neigh_mark_dead list_del corruption. prev->next should be ffff8881beb9e2b0, but was ffff8881cb42bdb0 ------------[ cut here ]------------ kernel BUG at lib/list_debug.c:53! invalid opcode: 0000 [#1] PREEMPT SMP KASAN kobject: 'loop5' (000000009356dbbf): kobject_uevent_env CPU: 0 PID: 2799 Comm: kworker/0:2 Not tainted 4.20.0-rc4+ #0 Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 01/01/2011 kobject: 'loop5' (000000009356dbbf): fill_kobj_path: path = '/devices/virtual/block/loop5' Workqueue: events_power_efficient neigh_periodic_work RIP: 0010:__list_del_entry_valid.cold.1+0x48/0x4a lib/list_debug.c:51 Code: 29 1e 88 e8 9d 63 f1 fd 0f 0b 48 89 de 48 c7 c7 00 2b 1e 88 e8 8c 63 f1 fd 0f 0b 48 89 de 48 c7 c7 a0 2a 1e 88 e8 7b 63 f1 fd <0f> 0b 48 89 d9 48 c7 c7 60 2b 1e 88 e8 6a 63 f1 fd 0f 0b 48 89 f1 RSP: 0000:ffff8881cd0cf448 EFLAGS: 00010286 RAX: 0000000000000054 RBX: ffff8881beb9e2b0 RCX: 0000000000000000 RDX: 0000000000000000 RSI: ffffffff881e28a0 RDI: ffffffff8ac137a0 kobject: 'loop1' (0000000002c43457): kobject_uevent_env RBP: ffff8881cd0cf460 R08: ffffed103b5c5021 R09: ffffed103b5c5020 R10: ffffed103b5c5020 R11: ffff8881dae28107 R12: ffff8881cb42bdb0 R13: ffffffff89b54020 R14: 1ffff11039a19e95 R15: ffff8881cd0cf568 FS: 0000000000000000(0000) GS:ffff8881dae00000(0000) knlGS:0000000000000000 CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 CR2: 00007f9baed40a30 CR3: 000000000906a000 CR4: 00000000001406f0 DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400 Call Trace: __list_del_entry include/linux/list.h:117 [inline] list_del_init include/linux/list.h:159 [inline] neigh_mark_dead+0x130/0x3e0 net/core/neighbour.c:125 kobject: 'loop1' (0000000002c43457): fill_kobj_path: path = '/devices/virtual/block/loop1' kobject: 'loop3' (00000000b4cdf777): kobject_uevent_env neigh_periodic_work+0x726/0xb20 net/core/neighbour.c:905 kobject: 'loop3' (00000000b4cdf777): fill_kobj_path: path = '/devices/virtual/block/loop3' process_one_work+0xadf/0x1ad0 kernel/workqueue.c:2153 kobject: 'loop2' (0000000065f45d7e): kobject_uevent_env kobject: 'loop2' (0000000065f45d7e): fill_kobj_path: path = '/devices/virtual/block/loop2' kobject: 'loop0' (00000000efcc40b8): kobject_uevent_env worker_thread+0x176/0x12a0 kernel/workqueue.c:2296 kobject: 'loop0' (00000000efcc40b8): fill_kobj_path: path = '/devices/virtual/block/loop0' kobject: 'loop1' (0000000002c43457): kobject_uevent_env kthread+0x327/0x3f0 kernel/kthread.c:246 kobject: 'loop1' (0000000002c43457): fill_kobj_path: path = '/devices/virtual/block/loop1' ret_from_fork+0x3a/0x50 arch/x86/entry/entry_64.S:352 Modules linked in: ---[ end trace a0a01ffbf78cf1fe ]--- kobject: 'loop4' (0000000092f3f877): kobject_uevent_env RIP: 0010:__list_del_entry_valid.cold.1+0x48/0x4a lib/list_debug.c:51 kobject: 'loop4' (0000000092f3f877): fill_kobj_path: path = '/devices/virtual/block/loop4' Code: 29 1e 88 e8 9d 63 f1 fd 0f 0b 48 89 de 48 c7 c7 00 2b 1e 88 e8 8c 63 f1 fd 0f 0b 48 89 de 48 c7 c7 a0 2a 1e 88 e8 7b 63 f1 fd <0f> 0b 48 89 d9 48 c7 c7 60 2b 1e 88 e8 6a 63 f1 fd 0f 0b 48 89 f1 RSP: 0000:ffff8881cd0cf448 EFLAGS: 00010286 RAX: 0000000000000054 RBX: ffff8881beb9e2b0 RCX: 0000000000000000 RDX: 0000000000000000 RSI: ffffffff881e28a0 RDI: ffffffff8ac137a0 RBP: ffff8881cd0cf460 R08: ffffed103b5c5021 R09: ffffed103b5c5020 R10: ffffed103b5c5020 R11: ffff8881dae28107 R12: ffff8881cb42bdb0 kobject: 'loop0' (00000000efcc40b8): kobject_uevent_env R13: ffffffff89b54020 R14: 1ffff11039a19e95 R15: ffff8881cd0cf568 FS: 0000000000000000(0000) GS:ffff8881dae00000(0000) knlGS:0000000000000000 CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 CR2: 00007f9baed40a30 CR3: 000000000906a000 CR4: 00000000001406f0 DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400