[PATCH] lockdep: Walk only in-use lock chains in zap_class()

[Vlad Poenaru <vlad.wing@gmail.com>]

remove_class_from_lock_chains() visits every bucket of chainhash_table,
which has MAX_LOCKDEP_CHAINS / 2 buckets however many chains exist. With
CONFIG_LOCKDEP_CHAINS_BITS=20 that is 512K buckets per zapped class,
walked with IRQs disabled under the graph lock, on every
lockdep_unregister_key().

That hurts users that unregister keys often. Almost every qdisc has a
dynamic key, so "tc qdisc replace dev eth0 root mq" on a multi-queue NIC
unregisters one key per TX queue, all under RTNL.

Iterate lock_chains_in_use instead. Scanning the bitmap costs
MAX_LOCKDEP_CHAINS / BITS_PER_LONG words (16K at CHAINS_BITS=20); the
rest of the cost follows the number of chains actually allocated. To
tell hashed chains apart from slots that are allocated but not hashed:

 - unhash with hlist_del_init_rcu(), so a chain waiting for its RCU
   grace period is hlist_unhashed(); RCU readers still follow ->next;
 - initialise ->entry in alloc_lock_chain(), so a slot orphaned when
   alloc_chain_hlocks() fails in add_chain_cache() is unhashed too;
 - have lockdep_reset() release the chain slots along with the hash
   buckets, and forget pending frees of them, instead of leaving them
   marked in use.

On an x86_64 KASAN + PROVE_LOCKING kernel with LOCKDEP_BITS=20 and
LOCKDEP_CHAINS_BITS=20 (64 vCPU KVM guest, mq on a 64-queue netdevsim
device), the chain walk per zap_class() drops from 7.3 ms to 0.09 ms
with 8K chains in use, and from 14.8 ms to 1.2 ms with 214K chains.

Signed-off-by: Vlad Poenaru <vlad.wing@gmail.com>
---
 kernel/locking/lockdep.c | 48 +++++++++++++++++++++++++++++-----------
 1 file changed, 35 insertions(+), 13 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index c3dc84a7cef26..3a42811b37d39 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3761,6 +3761,8 @@ static struct lock_chain *alloc_lock_chain(void)
 	if (unlikely(idx >= ARRAY_SIZE(lock_chains)))
 		return NULL;
 	__set_bit(idx, lock_chains_in_use);
+	/* Unhashed until add_chain_cache() succeeds, see zap_class(). */
+	INIT_HLIST_NODE(&lock_chains[idx].entry);
 	return lock_chains + idx;
 }
 
@@ -6279,15 +6281,22 @@ void lockdep_reset(void)
 	debug_locks = 1;
 	for (i = 0; i < CHAINHASH_SIZE; i++)
 		INIT_HLIST_HEAD(chainhash_table + i);
+#ifdef CONFIG_PROVE_LOCKING
+	/* The chains are gone from the hash, release their slots too. */
+	bitmap_zero(lock_chains_in_use, ARRAY_SIZE(lock_chains));
+	for (i = 0; i < ARRAY_SIZE(delayed_free.pf); i++)
+		bitmap_zero(delayed_free.pf[i].lock_chains_being_freed,
+			    ARRAY_SIZE(lock_chains));
+#endif
 	raw_local_irq_restore(flags);
 }
 
+#ifdef CONFIG_PROVE_LOCKING
 /* Remove a class from a lock chain. Must be called with the graph lock held. */
 static void remove_class_from_lock_chain(struct pending_free *pf,
 					 struct lock_chain *chain,
 					 struct lock_class *class)
 {
-#ifdef CONFIG_PROVE_LOCKING
 	int i;
 
 	for (i = chain->base; i < chain->base + chain->depth; i++) {
@@ -6309,29 +6318,42 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 	dec_chains(chain->irq_context);
 
 	/*
-	 * Note: calling hlist_del_rcu() from inside a
-	 * hlist_for_each_entry_rcu() loop is safe.
+	 * Use the _init variant so that hlist_unhashed() tells
+	 * remove_class_from_lock_chains() to skip this chain while it waits
+	 * for an RCU grace period. Concurrent RCU readers can still follow
+	 * ->next.
 	 */
-	hlist_del_rcu(&chain->entry);
+	hlist_del_init_rcu(&chain->entry);
 	__set_bit(chain - lock_chains, pf->lock_chains_being_freed);
 	nr_zapped_lock_chains++;
-#endif
 }
+#endif
 
-/* Must be called with the graph lock held. */
+/*
+ * Must be called with the graph lock held.
+ *
+ * Walk the lock_chains_in_use bitmap rather than every bucket of
+ * chainhash_table: the hash table has MAX_LOCKDEP_CHAINS / 2 buckets
+ * whether or not they are in use, so walking it costs the same with a
+ * nearly empty table as with a full one. That walk dominates
+ * lockdep_unregister_key() with large CONFIG_LOCKDEP_CHAINS_BITS values.
+ * Slots that are allocated but not hashed (being freed, or orphaned when
+ * chain_hlocks ran out) are skipped.
+ */
 static void remove_class_from_lock_chains(struct pending_free *pf,
 					  struct lock_class *class)
 {
+#ifdef CONFIG_PROVE_LOCKING
 	struct lock_chain *chain;
-	struct hlist_head *head;
-	int i;
+	unsigned long i;
 
-	for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
-		head = chainhash_table + i;
-		hlist_for_each_entry_rcu(chain, head, entry) {
-			remove_class_from_lock_chain(pf, chain, class);
-		}
+	for_each_set_bit(i, lock_chains_in_use, ARRAY_SIZE(lock_chains)) {
+		chain = lock_chains + i;
+		if (hlist_unhashed(&chain->entry))
+			continue;
+		remove_class_from_lock_chain(pf, chain, class);
 	}
+#endif
 }
 
 /*
-- 
2.53.0-Meta