bisecting fixing commit since 1e78030e5e5b2d8b0cad7136caf9cfab986a6bff building syzkaller on 835dffe7e5d185154a9b147476a17b6301ee139e testing commit 1e78030e5e5b2d8b0cad7136caf9cfab986a6bff with gcc (GCC) 8.1.0 kernel signature: 61b5fc8b569ddb14de4561bbc2f4a29f4e527f304e75b4fd9a3753035ced2723 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 in kernfs_get run #4: crashed: WARNING in kernfs_get run #5: crashed: WARNING in kernfs_get run #6: crashed: WARNING: refcount bug in hci_register_dev run #7: crashed: WARNING in hci_unregister_dev run #8: crashed: WARNING in kernfs_get run #9: crashed: WARNING in kernfs_get testing current HEAD 00086336a8d96a04aa960f912287692a258f6cf5 testing commit 00086336a8d96a04aa960f912287692a258f6cf5 with gcc (GCC) 8.1.0 kernel signature: 3a5ce8809fef70cefa15db4baa977b3aeb1f9dfa5c800ec8b9efaea66d3eb930 all runs: OK # git bisect start 00086336a8d96a04aa960f912287692a258f6cf5 1e78030e5e5b2d8b0cad7136caf9cfab986a6bff Bisecting: 29850 revisions left to test after this (roughly 15 steps) [ec939e4c94bd3ef2fd4f34c15f8aaf79bd0c5ee1] Merge tag 'armsoc-drivers' of git://git.kernel.org/pub/scm/linux/kernel/git/soc/soc testing commit ec939e4c94bd3ef2fd4f34c15f8aaf79bd0c5ee1 with gcc (GCC) 8.1.0 kernel signature: d5bfef988315d6bc96aeb23be55ed5d0c71dcd9fade3fc8e2f10cee5c3259d8e all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good ec939e4c94bd3ef2fd4f34c15f8aaf79bd0c5ee1 Bisecting: 14924 revisions left to test after this (roughly 14 steps) [0150aedda00efe2df9156c57de63f4dea8568e8e] Merge branch 'mauro' into docs-next testing commit 0150aedda00efe2df9156c57de63f4dea8568e8e with gcc (GCC) 8.1.0 kernel signature: 80834c6f0ba8c8d29d5e0be78f8ca99e0efc5def01ed5ff016888e09a7a67862 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 0150aedda00efe2df9156c57de63f4dea8568e8e Bisecting: 7173 revisions left to test after this (roughly 13 steps) [29d9f30d4ce6c7a38745a54a8cddface10013490] Merge git://git.kernel.org/pub/scm/linux/kernel/git/netdev/net-next testing commit 29d9f30d4ce6c7a38745a54a8cddface10013490 with gcc (GCC) 8.1.0 kernel signature: 0d13ac419bb3d0ef97c4c8cf54376c70df154f58b770000ff01b84bb95d58b42 all runs: OK # git bisect bad 29d9f30d4ce6c7a38745a54a8cddface10013490 Bisecting: 3912 revisions left to test after this (roughly 12 steps) [d937a6dfc9428f470c3ce4d459c390944ddef538] Merge branch 'core-objtool-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip testing commit d937a6dfc9428f470c3ce4d459c390944ddef538 with gcc (GCC) 8.1.0 kernel signature: 57587ddcfbcf05e70356fb1cf0bcce1aa9714d7b71f6c65ee5d09685c0e69070 all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good d937a6dfc9428f470c3ce4d459c390944ddef538 Bisecting: 1955 revisions left to test after this (roughly 11 steps) [a47ab26b9e4857ae0d476c23ac88c7a20d8462b8] Merge branch 'net-ethernet-ti-add-networking-support-for-k3-am65x-j721e-soc' testing commit a47ab26b9e4857ae0d476c23ac88c7a20d8462b8 with gcc (GCC) 8.1.0 kernel signature: 2dd7ea63d476e303cf0c79da06579f18dcba127a1fb90fb284ec19f2e591dc37 all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good a47ab26b9e4857ae0d476c23ac88c7a20d8462b8 Bisecting: 1069 revisions left to test after this (roughly 10 steps) [1455c69900c8c6442b182a74087931f4ffb1cac4] Merge tag 'fscrypt-for-linus' of git://git.kernel.org/pub/scm/fs/fscrypt/fscrypt testing commit 1455c69900c8c6442b182a74087931f4ffb1cac4 with gcc (GCC) 8.1.0 kernel signature: 692c0b5f7d69d8187affa14a54b30a82f753d286433a0bc8bfbca58e5eed17d7 all runs: OK # git bisect bad 1455c69900c8c6442b182a74087931f4ffb1cac4 Bisecting: 471 revisions left to test after this (roughly 9 steps) [673b41e04a035d760bc0aff83fa9ee24fd9c2779] staging/octeon: fix up merge error testing commit 673b41e04a035d760bc0aff83fa9ee24fd9c2779 with gcc (GCC) 8.1.0 kernel signature: b8c20521c254aae8fff7f950b678eb70dc8acd4598e01bc660fb7b2be0253185 all runs: OK # git bisect bad 673b41e04a035d760bc0aff83fa9ee24fd9c2779 Bisecting: 218 revisions left to test after this (roughly 8 steps) [a776c270a0b2fad6715cb714187e4290cadb9237] Merge branch 'efi-core-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip testing commit a776c270a0b2fad6715cb714187e4290cadb9237 with gcc (GCC) 8.1.0 kernel signature: 43bae5f265e03f00a103f8100a4ce8c72b1cf4b8f21d9bc94e215f611a61084b all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good a776c270a0b2fad6715cb714187e4290cadb9237 Bisecting: 123 revisions left to test after this (roughly 7 steps) [629b3df7ecb01fddfdf71cb5d3c563d143117c33] Merge branch 'x86/cpu' into perf/core, to resolve conflict testing commit 629b3df7ecb01fddfdf71cb5d3c563d143117c33 with gcc (GCC) 8.1.0 kernel signature: 96bd8c708227c8b04038a40d2ae3cddcc0ec7a966e08619a35c4e42c4b0aeb3d all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good 629b3df7ecb01fddfdf71cb5d3c563d143117c33 Bisecting: 61 revisions left to test after this (roughly 6 steps) [9c40365a65d62d7c06a95fb331b3442cb02d2fd9] threads: Update PID limit comment according to futex UAPI change testing commit 9c40365a65d62d7c06a95fb331b3442cb02d2fd9 with gcc (GCC) 8.1.0 kernel signature: 22c9eb931d34735ea08e85d2d71284473aacf4d278f887bf13e658fd2b58aa16 all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good 9c40365a65d62d7c06a95fb331b3442cb02d2fd9 Bisecting: 30 revisions left to test after this (roughly 5 steps) [6f28b46c4f93b4b4632e8f598c4f796244851a58] ia64: Remove mm.h from asm/uaccess.h testing commit 6f28b46c4f93b4b4632e8f598c4f796244851a58 with gcc (GCC) 8.1.0 kernel signature: 7ba421081bcddc148a8508e7ddfaad0303fa0a1e1729d455f0ebd53459b68553 all runs: OK # git bisect bad 6f28b46c4f93b4b4632e8f598c4f796244851a58 Bisecting: 15 revisions left to test after this (roughly 4 steps) [3867913c45b478dec7f9a60b950ad88a14e2a748] Merge branch 'locking/urgent' testing commit 3867913c45b478dec7f9a60b950ad88a14e2a748 with gcc (GCC) 8.1.0 kernel signature: 9754468aea0c536ccbed45a43cee557177143bd8e239931979dbd2ee775b1bef all runs: OK # git bisect bad 3867913c45b478dec7f9a60b950ad88a14e2a748 Bisecting: 7 revisions left to test after this (roughly 3 steps) [1751060e2527462714359573a39dca10451ffbf8] locking/percpu-rwsem, lockdep: Make percpu-rwsem use its own lockdep_map testing commit 1751060e2527462714359573a39dca10451ffbf8 with gcc (GCC) 8.1.0 kernel signature: dfcceee3ccf3f8199cb314efa18e126bb750eea373db5c9150e4eb2ec9e62cb5 all runs: OK # git bisect bad 1751060e2527462714359573a39dca10451ffbf8 Bisecting: 3 revisions left to test after this (roughly 2 steps) [1d44bcb4fdb650b2a57c9ff593a4d246a10ad801] locking/lockdep: Track number of zapped classes testing commit 1d44bcb4fdb650b2a57c9ff593a4d246a10ad801 with gcc (GCC) 8.1.0 kernel signature: 21707baeb3e29046e2fb5effeb72f34fd661d2c90a59091da5d3d76b4f9f18a3 all runs: crashed: BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! # git bisect good 1d44bcb4fdb650b2a57c9ff593a4d246a10ad801 Bisecting: 1 revision left to test after this (roughly 1 step) [797b82eb906eeba24dcd6e9ab92faef01fc684cb] locking/lockdep: Track number of zapped lock chains testing commit 797b82eb906eeba24dcd6e9ab92faef01fc684cb with gcc (GCC) 8.1.0 kernel signature: a181794cc46afcbc60b8c07ea6213e8e1fcfe64f6e2ccb18340c1136544addbe 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 797b82eb906eeba24dcd6e9ab92faef01fc684cb 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: 9423fb243190e5993c5577c62789ff36555f2dbfa8a5b8b2a05e977a56311c3e 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: 9423fb243190e5993c5577c62789ff36555f2dbfa8a5b8b2a05e977a56311c3e parent signature: a181794cc46afcbc60b8c07ea6213e8e1fcfe64f6e2ccb18340c1136544addbe revisions tested: 18, total time: 4h12m15.736650523s (build: 1h47m15.933275442s, test: 2h23m17.098127099s) first good commit: 810507fe6fd5ff3de429121adff49523fabb643a locking/lockdep: Reuse freed chain_hlocks entries cc: ["longman@redhat.com" "mingo@kernel.org" "peterz@infradead.org"]