bisecting fixing commit since 728254541ebcc7fee869c3c4c3f36f96be791edb building syzkaller on 7509bf360eba1461ac6059e4cacfbc29c9d2d4c7 testing commit 728254541ebcc7fee869c3c4c3f36f96be791edb with gcc (GCC) 8.1.0 kernel signature: a49d25940759eef2817eb553cb31147a72d50930102daf772290369fc1faae46 run #0: crashed: WARNING in kernfs_get run #1: crashed: WARNING in kernfs_get run #2: crashed: WARNING in kernfs_get run #3: crashed: general protection fault in kernfs_add_one 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 in kernfs_get run #9: crashed: WARNING in kernfs_get testing current HEAD 8632e9b5645bbc2331d21d892b0d6961c1a08429 testing commit 8632e9b5645bbc2331d21d892b0d6961c1a08429 with gcc (GCC) 8.1.0 kernel signature: a27fd3a7f88271ae91ec3c8e494dc007677c7a1095d91c2efb620f87ad3d9344 all runs: OK # git bisect start 8632e9b5645bbc2331d21d892b0d6961c1a08429 728254541ebcc7fee869c3c4c3f36f96be791edb Bisecting: 36679 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: 785a902ae5e73a4f3a65a135e89964fc6f85d959d64f0583b7a539f547ec26b7 all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good 89d57dddd7d319ded00415790a0bb3c954b7e386 Bisecting: 18281 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: df5847ccef22756a8a4f10661d6ad34f6c45033c9bb4383515ab5f14864c953f all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good 7eec11d3a784a283f916590e5aa30b855c2ccfd7 Bisecting: 9494 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: 14b7bfd1dc85bfa97e8f55966816905b1bf4eccf2dee5f83284ce4e8a317091d 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: 6921c574bf3a1528d0059f3b3ea58f324f16e7c0d565576082c29b9bb67cafc7 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: 8e7aa5186924542b15a8762faef282fb8be9e4b7c4d89f3bbb3d4c86c9595a5a all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # 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: 87d496a894792901a9f3291140f1a4ce394d9c5b317d3c3654d4fc2378c9e3c3 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: 336f7e9f8bfba0d72895d47d9fe108d956f7aabc6af4d9058c8c36f514ab344d 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: boot failed: can't ssh into the instance run #9: boot failed: can't ssh into the instance # 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: 869cf6951d5dfc992e60d05109cea4bee48596a78f9bdf0a3b69b50bfb838fd6 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: d2fda76b8c69e359e1d77021cce80630e077935f68c9c0d9a27f932104707242 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: 490d0749abd9a1222c3c9d73cf3a0350c7414d1599fa83e0c0f95d334f536362 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: f11aa3bdebd82ab08db27154c30efe1766ccd54ea548ff9ba8603d5563e2176a 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: 219580975d386ba91b8c64f9f742b24a0f0c6ba25d7e24c786f851157158e4ca all runs: OK # 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: 02cd079adcaf45a55e3fc07700fc7cc93571f6703c1bdcc1acb91217221e6a11 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: 5956496eaee8df073227c52f828809b5e0e9b811f238c5eb6d727466a5962019 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: 32b9bcd01919539e30a79253e851238fe8830c14e9550c8ee346d050709dc903 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: 59dee3447b66111e69e1fbebda13ea7a8d36e93c44adcde6bf48f24e9f0665a0 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: ece55db2158f8df440b55280202920139fb5b2fe7437c0d5c141c5cb61e479d0 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: ece55db2158f8df440b55280202920139fb5b2fe7437c0d5c141c5cb61e479d0 parent signature: 5956496eaee8df073227c52f828809b5e0e9b811f238c5eb6d727466a5962019 revisions tested: 19, total time: 4h37m37.502440574s (build: 1h57m42.0490262s, test: 2h38m1.489178704s) first good commit: 810507fe6fd5ff3de429121adff49523fabb643a locking/lockdep: Reuse freed chain_hlocks entries cc: ["longman@redhat.com" "mingo@kernel.org" "peterz@infradead.org"]