bisecting fixing commit since 6fbc7275c7a9ba97877050335f290341a1fd8dbf building syzkaller on 907bf74686129436f81aa40336ee89f7cc01b0b4 testing commit 6fbc7275c7a9ba97877050335f290341a1fd8dbf with gcc (GCC) 8.1.0 kernel signature: d0d09e7f7a2f38cdfe419522fc179de736a9f827d36088352aa27a6f810198cb run #0: crashed: WARNING in kernfs_get run #1: crashed: WARNING in kernfs_get run #2: crashed: WARNING in kernfs_get run #3: crashed: WARNING: refcount bug in hci_register_dev run #4: crashed: WARNING in kernfs_get run #5: crashed: WARNING in kernfs_get run #6: crashed: WARNING in kernfs_get run #7: crashed: WARNING in kernfs_get run #8: crashed: WARNING: refcount bug in hci_register_dev run #9: crashed: WARNING in kernfs_get testing current HEAD 00086336a8d96a04aa960f912287692a258f6cf5 testing commit 00086336a8d96a04aa960f912287692a258f6cf5 with gcc (GCC) 8.1.0 kernel signature: 336a92824196f39183f3c55a3ee589f3ab2d9b90d81fe30398942ef2b2aaa979 all runs: OK # git bisect start 00086336a8d96a04aa960f912287692a258f6cf5 6fbc7275c7a9ba97877050335f290341a1fd8dbf Bisecting: 36690 revisions left to test after this (roughly 15 steps) [89d57dddd7d319ded00415790a0bb3c954b7e386] Merge tag 'media/v5.5-1' of git://git.kernel.org/pub/scm/linux/kernel/git/mchehab/linux-media testing commit 89d57dddd7d319ded00415790a0bb3c954b7e386 with gcc (GCC) 8.1.0 kernel signature: 4dfa329ab852d3513672b4acce5239bda1380f7f79d4a5c9adb49c709466a838 all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good 89d57dddd7d319ded00415790a0bb3c954b7e386 Bisecting: 18292 revisions left to test after this (roughly 14 steps) [7eec11d3a784a283f916590e5aa30b855c2ccfd7] Merge branch 'akpm' (patches from Andrew) testing commit 7eec11d3a784a283f916590e5aa30b855c2ccfd7 with gcc (GCC) 8.1.0 kernel signature: ce1c6904fb26eeb88a1f73d2d6d4d2e28ce09c34e7e41051b41181134ac9caef all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good 7eec11d3a784a283f916590e5aa30b855c2ccfd7 Bisecting: 9505 revisions left to test after this (roughly 13 steps) [56a451b780676bc1cdac011735fe2869fa2e9abf] Merge tag 'ntb-5.7' of git://github.com/jonmason/ntb testing commit 56a451b780676bc1cdac011735fe2869fa2e9abf with gcc (GCC) 8.1.0 kernel signature: 7cc1562c819aa6b5fd66738fced816dcc1cb6204193831c8ed7089ba509e324b all runs: OK # git bisect bad 56a451b780676bc1cdac011735fe2869fa2e9abf Bisecting: 4392 revisions left to test after this (roughly 12 steps) [820d15632ec10bc0cf79595c5a635b795d149520] Merge tag 'socfpga_dts_fix_for_v5.6_v2' of git://git.kernel.org/pub/scm/linux/kernel/git/dinguyen/linux into arm/fixes testing commit 820d15632ec10bc0cf79595c5a635b795d149520 with gcc (GCC) 8.1.0 kernel signature: a888499ba239989bb767af63c4ab7e8fd3022f2fee647d5765d3df5ed3ea5729 all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good 820d15632ec10bc0cf79595c5a635b795d149520 Bisecting: 2281 revisions left to test after this (roughly 11 steps) [59838093be51ee9447f6ad05483d697b6fa0368d] Merge tag 'driver-core-5.7-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/driver-core testing commit 59838093be51ee9447f6ad05483d697b6fa0368d with gcc (GCC) 8.1.0 kernel signature: 03feadc52c57e53bbf54aa9146b0d270d81f2c050f3663011775d39e1d22ad2e run #0: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! run #1: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! run #2: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! run #3: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! run #4: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! run #5: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! run #6: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! run #7: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! run #8: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! run #9: boot failed: can't ssh into the instance # git bisect good 59838093be51ee9447f6ad05483d697b6fa0368d Bisecting: 1164 revisions left to test after this (roughly 10 steps) [673b41e04a035d760bc0aff83fa9ee24fd9c2779] staging/octeon: fix up merge error testing commit 673b41e04a035d760bc0aff83fa9ee24fd9c2779 with gcc (GCC) 8.1.0 kernel signature: a3605a40666cb180d182fb6b7094e3c7e55c8a131d1f93ddeacf46e613ab1a56 all runs: OK # git bisect bad 673b41e04a035d760bc0aff83fa9ee24fd9c2779 Bisecting: 564 revisions left to test after this (roughly 9 steps) [a231bed2267cf45b0759da1d3ad62483b8bd0925] Merge tag 'regulator-spi-v5.7' of git://git.kernel.org/pub/scm/linux/kernel/git/broonie/misc testing commit a231bed2267cf45b0759da1d3ad62483b8bd0925 with gcc (GCC) 8.1.0 kernel signature: 1c31a73d756ae00a117438f7d4daeb490130e26fd2d5f5ddbf81d63c684138c2 all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good a231bed2267cf45b0759da1d3ad62483b8bd0925 Bisecting: 338 revisions left to test after this (roughly 8 steps) [7c4fa150714fb319d4e2bb2303ebbd7307b0fb6d] Merge branch 'core-rcu-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip testing commit 7c4fa150714fb319d4e2bb2303ebbd7307b0fb6d with gcc (GCC) 8.1.0 kernel signature: bb3652e362cdeaeb61266e1a2f4ce3be1d98d30d3c32af1cba390f10a034028a all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good 7c4fa150714fb319d4e2bb2303ebbd7307b0fb6d Bisecting: 162 revisions left to test after this (roughly 7 steps) [4b9fd8a829a1eec7442e38afff21d610604de56a] Merge branch 'locking-core-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip testing commit 4b9fd8a829a1eec7442e38afff21d610604de56a with gcc (GCC) 8.1.0 kernel signature: cb9c1efc2338a371218bf54a21538a43426c74dc4e94232bbd21f47f23f33fc6 all runs: OK # git bisect bad 4b9fd8a829a1eec7442e38afff21d610604de56a Bisecting: 87 revisions left to test after this (roughly 7 steps) [badc61982adb6018a48ed8fe32087b9754cae14b] efi/x86: Add RNG seed EFI table to unencrypted mapping check testing commit badc61982adb6018a48ed8fe32087b9754cae14b with gcc (GCC) 8.1.0 kernel signature: b7ec065e3512c73c5aa522fecf525064b4c486c29c1a391198c0d4cb3ce105fa all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good badc61982adb6018a48ed8fe32087b9754cae14b Bisecting: 43 revisions left to test after this (roughly 6 steps) [9e860351550b28901a78f122b1e2dc97f78ba369] m68knommu: Remove mm.h include from uaccess_no.h testing commit 9e860351550b28901a78f122b1e2dc97f78ba369 with gcc (GCC) 8.1.0 kernel signature: 85ec46195c9dd8660432a34896e5b5e36bcbf1bfb4f1a714f218e42cc6e1f61f all runs: OK # git bisect bad 9e860351550b28901a78f122b1e2dc97f78ba369 Bisecting: 21 revisions left to test after this (roughly 5 steps) [f6f48e18040402136874a6a71611e081b4d0788a] lockdep: Teach lockdep about "USED" <- "IN-NMI" inversions testing commit f6f48e18040402136874a6a71611e081b4d0788a with gcc (GCC) 8.1.0 kernel signature: a04683b8f02d9c21033bb2f5cac10bb3c7551ed09fc0dcab45f5c7d059308434 run #0: OK 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: boot failed: can't ssh into the instance # git bisect bad f6f48e18040402136874a6a71611e081b4d0788a Bisecting: 10 revisions left to test after this (roughly 4 steps) [7f26482a872c36b2ee87ea95b9dcd96e3d5805df] locking/percpu-rwsem: Remove the embedded rwsem testing commit 7f26482a872c36b2ee87ea95b9dcd96e3d5805df with gcc (GCC) 8.1.0 kernel signature: 68e05bc52734f0c06a05b168f59fa6bae41f21cced8d190cface88bea3ed9bf7 all runs: OK # git bisect bad 7f26482a872c36b2ee87ea95b9dcd96e3d5805df Bisecting: 5 revisions left to test after this (roughly 3 steps) [797b82eb906eeba24dcd6e9ab92faef01fc684cb] locking/lockdep: Track number of zapped lock chains testing commit 797b82eb906eeba24dcd6e9ab92faef01fc684cb with gcc (GCC) 8.1.0 kernel signature: 923f67b12db50f1dbe7322dd926361cca260c470f435bf346630781cc19546d7 all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good 797b82eb906eeba24dcd6e9ab92faef01fc684cb Bisecting: 2 revisions left to test after this (roughly 2 steps) [206c98ffbeda588dbbd9d272505c42acbc364a30] locking/percpu-rwsem: Convert to bool testing commit 206c98ffbeda588dbbd9d272505c42acbc364a30 with gcc (GCC) 8.1.0 kernel signature: fe7054e71518c2fa28b9eaf6dba6fe569faab29fe9bf67e1dccc7662332cdcc2 all runs: OK # git bisect bad 206c98ffbeda588dbbd9d272505c42acbc364a30 Bisecting: 0 revisions left to test after this (roughly 1 step) [1751060e2527462714359573a39dca10451ffbf8] locking/percpu-rwsem, lockdep: Make percpu-rwsem use its own lockdep_map testing commit 1751060e2527462714359573a39dca10451ffbf8 with gcc (GCC) 8.1.0 kernel signature: 67f96534eac59acada70763397ef293dcd86eb599ac62133cdb18f9597da417e all runs: OK # git bisect bad 1751060e2527462714359573a39dca10451ffbf8 Bisecting: 0 revisions left to test after this (roughly 0 steps) [810507fe6fd5ff3de429121adff49523fabb643a] locking/lockdep: Reuse freed chain_hlocks entries testing commit 810507fe6fd5ff3de429121adff49523fabb643a with gcc (GCC) 8.1.0 kernel signature: 75acfb800ebba62aeba7509786f1c353c3a1f2ff80b65b9f2b3e701ef251ebc8 all runs: OK # git bisect bad 810507fe6fd5ff3de429121adff49523fabb643a 810507fe6fd5ff3de429121adff49523fabb643a is the first bad commit commit 810507fe6fd5ff3de429121adff49523fabb643a Author: Waiman Long Date: Thu Feb 6 10:24:08 2020 -0500 locking/lockdep: Reuse freed chain_hlocks entries Once a lock class is zapped, all the lock chains that include the zapped class are essentially useless. The lock_chain structure itself can be reused, but not the corresponding chain_hlocks[] entries. Over time, we will run out of chain_hlocks entries while there are still plenty of other lockdep array entries available. To fix this imbalance, we have to make chain_hlocks entries reusable just like the others. As the freed chain_hlocks entries are in blocks of various lengths. A simple bitmap like the one used in the other reusable lockdep arrays isn't applicable. Instead the chain_hlocks entries are put into bucketed lists (MAX_CHAIN_BUCKETS) of chain blocks. Bucket 0 is the variable size bucket which houses chain blocks of size larger than MAX_CHAIN_BUCKETS sorted in decreasing size order. Initially, the whole array is in one chain block (the primordial chain block) in bucket 0. The minimum size of a chain block is 2 chain_hlocks entries. That will be the minimum allocation size. In other word, allocation requests for one chain_hlocks entry will cause 2-entry block to be returned and hence 1 entry will be wasted. Allocation requests for the chain_hlocks are fulfilled first by looking for chain block of matching size. If not found, the first chain block from bucket[0] (the largest one) is split. That can cause hlock entries fragmentation and reduce allocation efficiency if a chain block of size > MAX_CHAIN_BUCKETS is ever zapped and put back to after the primordial chain block. So the MAX_CHAIN_BUCKETS must be large enough that this should seldom happen. By reusing the chain_hlocks entries, we are able to handle workloads that add and zap a lot of lock classes without the risk of running out of chain_hlocks entries as long as the total number of outstanding lock classes at any time remain within a reasonable limit. Two new tracking counters, nr_free_chain_hlocks & nr_large_chain_blocks, are added to track the total number of chain_hlocks entries in the free bucketed lists and the number of large chain blocks in buckets[0] respectively. The nr_free_chain_hlocks replaces nr_chain_hlocks. The nr_large_chain_blocks counter enables to see if we should increase the number of buckets (MAX_CHAIN_BUCKETS) available so as to avoid to avoid the fragmentation problem in bucket[0]. An internal nfsd test that ran for more than an hour and kept on loading and unloading kernel modules could cause the following message to be displayed. [ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! The patched kernel was able to complete the test with a lot of free chain_hlocks entries to spare: # cat /proc/lockdep_stats : dependency chains: 18867 [max: 65536] dependency chain hlocks: 74926 [max: 327680] dependency chain hlocks lost: 0 : zapped classes: 1541 zapped lock chains: 56765 large chain blocks: 1 By changing MAX_CHAIN_BUCKETS to 3 and add a counter for the size of the largest chain block. The system still worked and We got the following lockdep_stats data: dependency chains: 18601 [max: 65536] dependency chain hlocks used: 73133 [max: 327680] dependency chain hlocks lost: 0 : zapped classes: 1541 zapped lock chains: 56702 large chain blocks: 45165 large chain block size: 20165 By running the test again, I was indeed able to cause chain_hlocks entries to get lost: dependency chain hlocks used: 74806 [max: 327680] dependency chain hlocks lost: 575 : large chain blocks: 48737 large chain block size: 7 Due to the fragmentation, it is possible that the "MAX_LOCKDEP_CHAIN_HLOCKS too low!" error can happen even if a lot of of chain_hlocks entries appear to be free. Fortunately, a MAX_CHAIN_BUCKETS value of 16 should be big enough that few variable sized chain blocks, other than the initial one, should ever be present in bucket 0. Suggested-by: Peter Zijlstra Signed-off-by: Waiman Long Signed-off-by: Peter Zijlstra (Intel) Signed-off-by: Ingo Molnar Link: https://lkml.kernel.org/r/20200206152408.24165-7-longman@redhat.com kernel/locking/lockdep.c | 254 +++++++++++++++++++++++++++++++++++-- kernel/locking/lockdep_internals.h | 4 +- kernel/locking/lockdep_proc.c | 12 +- 3 files changed, 255 insertions(+), 15 deletions(-) culprit signature: 75acfb800ebba62aeba7509786f1c353c3a1f2ff80b65b9f2b3e701ef251ebc8 parent signature: 923f67b12db50f1dbe7322dd926361cca260c470f435bf346630781cc19546d7 revisions tested: 19, total time: 4h30m18.437467132s (build: 1h55m9.467385699s, test: 2h33m22.142510259s) first good commit: 810507fe6fd5ff3de429121adff49523fabb643a locking/lockdep: Reuse freed chain_hlocks entries cc: ["longman@redhat.com" "mingo@kernel.org" "peterz@infradead.org"]