Skip to contentSkip to conversation

locking/lockdep: Reuse zapped chain_hlocks entries

PATCH Superseded Waiman Long 3 participants 29 messages Dec 16, 2019 – Jan 15, 2020 Locking primitives

v2 of 6 Superseded Latest is v6 →

lore
Share & tools
lore

Waiman Long

author reviewer
#0 lore raw

v2 cover locking/lockdep: Reuse zapped chain_hlocks entries

v2:
- Revamp the chain_hlocks reuse patch to store the freed chain_hlocks information in the chain_hlocks entries themselves avoiding the need of a separate set of tracking structures. This, however, requires a minimum allocation size of at least 2. Thanks to PeterZ for his review and inspiring this change.
- Remove the leakage counter as it is no longer applicable.
- Add patch 6 to make the output of /proc/lockdep_chains more readable.

It was found that when running a workload that kept on adding lock classes and then zapping them repetitively, the system will eventually run out of chain_hlocks[] entries even though there were still plenty of other lockdep data buffers available.

  [ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!
  [ 4318.444809] turning off the locking correctness validator.

In order to fix this problem, we have to make chain_hlocks[] entries reusable just like other lockdep arrays. Besides that, the patchset also adds some zapped class and chain_hlocks counters to be tracked by /proc/lockdep_stats. It also fixes leakage in the irq context counters and makes the output of /proc/lockdep_chains more readable.

Waiman Long (6):
locking/lockdep: Track number of zapped classes locking/lockdep: Throw away all lock chains with zapped class locking/lockdep: Track number of zapped lock chains locking/lockdep: Reuse freed chain_hlocks entries locking/lockdep: Decrement irq context counters when removing lock
chain
locking/lockdep: Display irq_context names in /proc/lockdep_chains

 kernel/locking/lockdep.c           | 307 +++++++++++++++++++++++------
 kernel/locking/lockdep_internals.h |  14 +-
 kernel/locking/lockdep_proc.c      |  26 ++-
 3 files changed, 282 insertions(+), 65 deletions(-)
Signature · 1 line
2.18.1
author reviewer
#1 lore raw

PATCH v2 1/6 locking/lockdep: Track number of zapped classes

The whole point of the lockdep dynamic key patch is to allow unused locks to be removed from the lockdep data buffers so that existing buffer space can be reused. However, there is no way to find out how many unused locks are zapped and so we don't know if the zapping process is working properly.

Add a new nr_zapped_classes variable to track that and show it in /proc/lockdep_stats if it is non-zero.

---
 kernel/locking/lockdep.c           | 2 ++
 kernel/locking/lockdep_internals.h | 1 +
 kernel/locking/lockdep_proc.c      | 9 +++++++++
 3 files changed, 12 insertions(+)
kernel/locking/lockdep.c +2 -0
index 32282e7112d3..c8d0374101b0 100644
@@ -147,6 +147,7 @@ static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);
 #define KEYHASH_SIZE		(1UL << KEYHASH_BITS)
 static struct hlist_head lock_keys_hash[KEYHASH_SIZE];
 unsigned long nr_lock_classes;
+unsigned long nr_zapped_classes;
 #ifndef CONFIG_DEBUG_LOCKDEP
 static
 #endif
@@ -4875,6 +4876,7 @@ static void zap_class(struct pending_free *pf, struct lock_class *class)
 	}
 
 	remove_class_from_lock_chains(pf, class);
+	nr_zapped_classes++;
 }
 
 static void reinit_class(struct lock_class *class)
kernel/locking/lockdep_internals.h +1 -0
index 18d85aebbb57..a31d16fd3c43 100644
@@ -124,6 +124,7 @@ extern const char *__get_key_name(const struct lockdep_subclass_key *key,
 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i);
 
 extern unsigned long nr_lock_classes;
+extern unsigned long nr_zapped_classes;
 extern unsigned long nr_list_entries;
 long lockdep_next_lockchain(long i);
 unsigned long lock_chain_count(void);
kernel/locking/lockdep_proc.c +9 -0
index dadb7b7fba37..d98d349bb648 100644
@@ -336,6 +336,15 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 	seq_printf(m, " debug_locks:                   %11u\n",
 			debug_locks);
 
+	/*
+	 * Zappped classes and lockdep data buffers reuse statistics.
+	 */
+	if (!nr_zapped_classes)
+		return 0;
+
+	seq_puts(m, "\n");
+	seq_printf(m, " zapped classes:                %11lu\n",
+			nr_zapped_classes);
 	return 0;
 }
 
Signature · 1 line
2.18.1
maintainer
#2 lore raw

Re: [PATCH v2 1/6] locking/lockdep: Track number of zapped classes

Quoted 19 lines · Waiman Long

The whole point of the lockdep dynamic key patch is to allow unused locks to be removed from the lockdep data buffers so that existing buffer space can be reused. However, there is no way to find out how many unused locks are zapped and so we don't know if the zapping process is working properly.

Add a new nr_zapped_classes variable to track that and show it in /proc/lockdep_stats if it is non-zero.

kernel/locking/lockdep_proc.c +1 -0
index dadb7b7fba37..d98d349bb648 100644
@@ -336,6 +336,15 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 	seq_printf(m, " debug_locks:                   %11u\n",
 			debug_locks);
 
+	/*

kernel/locking/lockdep_proc.c static int lockdep_stats_show(struct seq_file *m, void *v) · line 349

Quoted 10 lines
kernel/locking/lockdep_proc.c +8 -0
+	 * Zappped classes and lockdep data buffers reuse statistics.
+	 */
+	if (!nr_zapped_classes)
+		return 0;
+
+	seq_puts(m, "\n");
+	seq_printf(m, " zapped classes:                %11lu\n",
+			nr_zapped_classes);
 	return 0;
 }

Why is that conditional?

author reviewer
#3 lore raw

Re: [PATCH v2 1/6] locking/lockdep: Track number of zapped classes

Quoted 18 lines · Peter Zijlstra
Quoted 17 lines · Waiman Long

The whole point of the lockdep dynamic key patch is to allow unused locks to be removed from the lockdep data buffers so that existing buffer space can be reused. However, there is no way to find out how many unused locks are zapped and so we don't know if the zapping process is working properly.

Add a new nr_zapped_classes variable to track that and show it in /proc/lockdep_stats if it is non-zero.

kernel/locking/lockdep_proc.c +0 -0
index dadb7b7fba37..d98d349bb648 100644
@@ -336,6 +336,15 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 	seq_printf(m, " debug_locks:                   %11u\n",
 			debug_locks);
 
Quoted 13 lines

kernel/locking/lockdep_proc.c static int lockdep_stats_show(struct seq_file *m, void *v) · line 349

Quoted 11 lines
kernel/locking/lockdep_proc.c +9 -0
+	/*
+	 * Zappped classes and lockdep data buffers reuse statistics.
+	 */
+	if (!nr_zapped_classes)
+		return 0;
+
+	seq_puts(m, "\n");
+	seq_printf(m, " zapped classes:                %11lu\n",
+			nr_zapped_classes);
 	return 0;
 }

Why is that conditional?

Because I thought zapping class doesn't occur that often. Apparently, class zapping happens when the system first boots up. I guess that conditional check isn't needed. I can remove it in the next version.

Cheers,
Longman

#4 lore raw

Re: [PATCH v2 1/6] locking/lockdep: Track number of zapped classes

Quoted 32 lines · Waiman Long
Quoted 18 lines · Peter Zijlstra
Quoted 17 lines · Waiman Long

The whole point of the lockdep dynamic key patch is to allow unused locks to be removed from the lockdep data buffers so that existing buffer space can be reused. However, there is no way to find out how many unused locks are zapped and so we don't know if the zapping process is working properly.

Add a new nr_zapped_classes variable to track that and show it in /proc/lockdep_stats if it is non-zero.

kernel/locking/lockdep_proc.c +0 -0
index dadb7b7fba37..d98d349bb648 100644
@@ -336,6 +336,15 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
  	seq_printf(m, " debug_locks:                   %11u\n",
  			debug_locks);
 
Quoted 13 lines

kernel/locking/lockdep_proc.c static int lockdep_stats_show(struct seq_file *m, void *v) · line 349

Quoted 11 lines
kernel/locking/lockdep_proc.c +9 -0
+	/*
+	 * Zappped classes and lockdep data buffers reuse statistics.
+	 */
+	if (!nr_zapped_classes)
+		return 0;
+
+	seq_puts(m, "\n");
+	seq_printf(m, " zapped classes:                %11lu\n",
+			nr_zapped_classes);
  	return 0;
  }

Why is that conditional?

Quoted 3 lines

Because I thought zapping class doesn't occur that often. Apparently, class zapping happens when the system first boots up. I guess that conditional check isn't needed. I can remove it in the next version.

Zapping a lock class happens every time a lock key is unregistered. That can happen any time as one can see in the following grep output:

$ git grep -lw 'lockdep_unregister_key'
drivers/net/bonding/bond_main.c:4446: lockdep_unregister_key(&bond->stats_lock_key);
drivers/net/team/team.c:1676:	lockdep_unregister_key(&team->team_lock_key);
drivers/net/team/team.c:1984:		lockdep_unregister_key(&team->team_lock_key);
include/linux/lockdep.h:294:extern void lockdep_unregister_key(struct lock_class_key *key);
include/linux/lockdep.h:464:static inline void lockdep_unregister_key(struct lock_class_key *key)
kernel/locking/lockdep.c:5166:void lockdep_unregister_key(struct lock_class_key *key)
kernel/locking/lockdep.c:5201:EXPORT_SYMBOL_GPL(lockdep_unregister_key);
kernel/workqueue.c:3456:	lockdep_unregister_key(&wq->key);
net/core/dev.c:9172:	lockdep_unregister_key(&dev->qdisc_tx_busylock_key);
net/core/dev.c:9173:	lockdep_unregister_key(&dev->qdisc_running_key);
net/core/dev.c:9174:	lockdep_unregister_key(&dev->qdisc_xmit_lock_key);
net/core/dev.c:9175:	lockdep_unregister_key(&dev->addr_list_lock_key);
net/core/dev.c:9183:	lockdep_unregister_key(&dev->qdisc_xmit_lock_key);
net/core/dev.c:9184:	lockdep_unregister_key(&dev->addr_list_lock_key);
tools/lib/lockdep/include/liblockdep/common.h:48:void lockdep_unregister_key(struct lock_class_key *key);
tools/lib/lockdep/include/liblockdep/mutex.h:58: lockdep_unregister_key(&lock->key);

Bart.

author reviewer
#5 lore raw

PATCH v2 2/6 locking/lockdep: Throw away all lock chains with zapped class

In reply to Waiman Long

If a lock chain contains a class that is zapped, the whole lock chain is now invalid. There is no point in keeping a partial chain behind hoping it can be useful. So just dump the corresponding chain_hlocks entries for now. A latter patch will try to reuse the freed chain_hlocks entries.

This patch also changes the type of nr_chain_hlocks to unsigned integer to be consistent with the other counters.

---
 kernel/locking/lockdep.c           | 36 ++++--------------------------
 kernel/locking/lockdep_internals.h |  4 ++--
 kernel/locking/lockdep_proc.c      |  2 +-
 3 files changed, 7 insertions(+), 35 deletions(-)
kernel/locking/lockdep.c +4 -32
index c8d0374101b0..30ebfe4978d5 100644
@@ -2624,8 +2624,8 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)
 
 struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS];
 static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
-int nr_chain_hlocks;
 static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
+unsigned int nr_chain_hlocks;
 
 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
 {
@@ -4770,57 +4770,29 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 					 struct lock_class *class)
 {
 #ifdef CONFIG_PROVE_LOCKING
-	struct lock_chain *new_chain;
-	u64 chain_key;
 	int i;
 
 	for (i = chain->base; i < chain->base + chain->depth; i++) {
 		if (chain_hlocks[i] != class - lock_classes)
 			continue;
-		/* The code below leaks one chain_hlock[] entry. */
-		if (--chain->depth > 0) {
-			memmove(&chain_hlocks[i], &chain_hlocks[i + 1],
-				(chain->base + chain->depth - i) *
-				sizeof(chain_hlocks[0]));
-		}
 		/*
 		 * Each lock class occurs at most once in a lock chain so once
 		 * we found a match we can break out of this loop.
 		 */
-		goto recalc;
+		goto free_lock_chain;
 	}
 	/* Since the chain has not been modified, return. */
 	return;
 
-recalc:
-	chain_key = INITIAL_CHAIN_KEY;
-	for (i = chain->base; i < chain->base + chain->depth; i++)
-		chain_key = iterate_chain_key(chain_key, chain_hlocks[i]);
-	if (chain->depth && chain->chain_key == chain_key)
-		return;
+free_lock_chain:
 	/* Overwrite the chain key for concurrent RCU readers. */
-	WRITE_ONCE(chain->chain_key, chain_key);
+	WRITE_ONCE(chain->chain_key, INITIAL_CHAIN_KEY);
 	/*
 	 * Note: calling hlist_del_rcu() from inside a
 	 * hlist_for_each_entry_rcu() loop is safe.
 	 */
 	hlist_del_rcu(&chain->entry);
 	__set_bit(chain - lock_chains, pf->lock_chains_being_freed);
-	if (chain->depth == 0)
-		return;
-	/*
-	 * If the modified lock chain matches an existing lock chain, drop
-	 * the modified lock chain.
-	 */
-	if (lookup_chain_cache(chain_key))
-		return;
-	new_chain = alloc_lock_chain();
-	if (WARN_ON_ONCE(!new_chain)) {
-		debug_locks_off();
-		return;
-	}
-	*new_chain = *chain;
-	hlist_add_head_rcu(&new_chain->entry, chainhashentry(chain_key));
 #endif
 }
 
kernel/locking/lockdep_internals.h +2 -2
index a31d16fd3c43..5dec0fe12507 100644
@@ -128,14 +128,14 @@ extern unsigned long nr_zapped_classes;
 extern unsigned long nr_list_entries;
 long lockdep_next_lockchain(long i);
 unsigned long lock_chain_count(void);
-extern int nr_chain_hlocks;
 extern unsigned long nr_stack_trace_entries;
 
 extern unsigned int nr_hardirq_chains;
 extern unsigned int nr_softirq_chains;
 extern unsigned int nr_process_chains;
-extern unsigned int max_lockdep_depth;
+extern unsigned int nr_chain_hlocks;
 
+extern unsigned int max_lockdep_depth;
 extern unsigned int max_bfs_queue_depth;
 
 #ifdef CONFIG_PROVE_LOCKING
kernel/locking/lockdep_proc.c +1 -1
index d98d349bb648..4c7dc0a8935d 100644
@@ -271,7 +271,7 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 #ifdef CONFIG_PROVE_LOCKING
 	seq_printf(m, " dependency chains:             %11lu [max: %lu]\n",
 			lock_chain_count(), MAX_LOCKDEP_CHAINS);
-	seq_printf(m, " dependency chain hlocks:       %11d [max: %lu]\n",
+	seq_printf(m, " dependency chain hlocks:       %11u [max: %lu]\n",
 			nr_chain_hlocks, MAX_LOCKDEP_CHAIN_HLOCKS);
 #endif
 
Signature · 1 line
2.18.1
maintainer
#6 lore raw

Re: [PATCH v2 2/6] locking/lockdep: Throw away all lock chains with zapped class

Quoted 2 lines · Waiman Long

If a lock chain contains a class that is zapped, the whole lock chain is now invalid.

Possibly. But I'm thinking that argument can/should be made mode elaborate.

Suppose we have A->B->C, and we're about to remove B.

Now, I suppose the trivial argument goes that if we remove the text that causes A->B, then so B->C will no longer happen. However, that doesn't mean A->C won't still occur.

OTOH, we might already have A->C and so our resulting chain would be a duplicate. Conversely, if we didn't already have A->C and it does indeed still occur (say it was omitted due to the redundant logic), then we will create this dependency the next time we'll encounter it.

Bart, do you see a problem with this reasoning?

In short, yes, I think you're right and we can remove the whole thing. But please, expand the Changelog a bit, possibly add some of this reasoning into a comment.

author reviewer
#7 lore raw

Re: [PATCH v2 2/6] locking/lockdep: Throw away all lock chains with zapped class

Quoted 7 lines · Peter Zijlstra
Quoted 2 lines · Waiman Long

If a lock chain contains a class that is zapped, the whole lock chain is now invalid.

Possibly. But I'm thinking that argument can/should be made mode elaborate.

Suppose we have A->B->C, and we're about to remove B.

Quoted 8 lines

Now, I suppose the trivial argument goes that if we remove the text that causes A->B, then so B->C will no longer happen. However, that doesn't mean A->C won't still occur.

OTOH, we might already have A->C and so our resulting chain would be a duplicate. Conversely, if we didn't already have A->C and it does indeed still occur (say it was omitted due to the redundant logic), then we will create this dependency the next time we'll encounter it.

I will prefer having it only when it actually happens rather than leaving a partial chain behind assuming that it may happen.

Quoted 7 lines

Bart, do you see a problem with this reasoning?

In short, yes, I think you're right and we can remove the whole thing. But please, expand the Changelog a bit, possibly add some of this reasoning into a comment.

Yes, I will elaborate more in the changelog.

Cheers,
Longman

#8 lore raw

Re: [PATCH v2 2/6] locking/lockdep: Throw away all lock chains with zapped class

In reply to Peter Zijlstra
Quoted 17 lines · Peter Zijlstra
Quoted 2 lines · Waiman Long

If a lock chain contains a class that is zapped, the whole lock chain is now invalid.

Possibly. But I'm thinking that argument can/should be made mode elaborate.

Suppose we have A->B->C, and we're about to remove B.

Now, I suppose the trivial argument goes that if we remove the text that causes A->B, then so B->C will no longer happen. However, that doesn't mean A->C won't still occur.

OTOH, we might already have A->C and so our resulting chain would be a duplicate. Conversely, if we didn't already have A->C and it does indeed still occur (say it was omitted due to the redundant logic), then we will create this dependency the next time we'll encounter it.

Quoted 5 lines

Bart, do you see a problem with this reasoning?

In short, yes, I think you're right and we can remove the whole thing. But please, expand the Changelog a bit, possibly add some of this reasoning into a comment.

I think unconditionally dropping lock chains is wrong. If a lock class is zapped the rest of the lock chain remains valid and hence should be retained unless it duplicates another lock chain or if the length of the lock chain is reduced to a single element.

Bart.

author reviewer
#9 lore raw

Re: [PATCH v2 2/6] locking/lockdep: Throw away all lock chains with zapped class

Quoted 22 lines · Bart Van Assche
Quoted 21 lines · Peter Zijlstra
Quoted 3 lines · Waiman Long

If a lock chain contains a class that is zapped, the whole lock chain is
now invalid.

Possibly. But I'm thinking that argument can/should be made mode elaborate.

Suppose we have A->B->C, and we're about to remove B.

Now, I suppose the trivial argument goes that if we remove the text that causes A->B, then so B->C will no longer happen. However, that doesn't mean A->C won't still occur.

OTOH, we might already have A->C and so our resulting chain would be a duplicate. Conversely, if we didn't already have A->C and it does indeed still occur (say it was omitted due to the redundant logic), then we will create this dependency the next time we'll encounter it.

Bart, do you see a problem with this reasoning?

Quoted 8 lines
Quoted 3 lines

In short, yes, I think you're right and we can remove the whole thing. But please, expand the Changelog a bit, possibly add some of this reasoning into a comment.

I think unconditionally dropping lock chains is wrong. If a lock class is zapped the rest of the lock chain remains valid and hence should be retained unless it duplicates another lock chain or if the length of the lock chain is reduced to a single element.

If the zapped class is at the end of the chain, the shorten one without the zapped class should have been stored already as the current code will store all its predecessor chains. If it is somewhere in the middle, there is no guarantee that the partial chain will actually happen. It may just clutter up the hash and make searching slower. Why don't we just store it when it actually happens?

Cheers,
Longman

author reviewer
#10 lore raw

PATCH v2 3/6 locking/lockdep: Track number of zapped lock chains

In reply to Waiman Long

Add a new counter nr_zapped_lock_chains to track the number lock chains that have been removed.

---
 kernel/locking/lockdep.c           | 2 ++
 kernel/locking/lockdep_internals.h | 1 +
 kernel/locking/lockdep_proc.c      | 2 ++
 3 files changed, 5 insertions(+)
kernel/locking/lockdep.c +2 -0
index 30ebfe4978d5..8293f7e80ee6 100644
@@ -2625,6 +2625,7 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)
 struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS];
 static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
 static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
+unsigned long nr_zapped_lock_chains;
 unsigned int nr_chain_hlocks;
 
 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
@@ -4793,6 +4794,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 	 */
 	hlist_del_rcu(&chain->entry);
 	__set_bit(chain - lock_chains, pf->lock_chains_being_freed);
+	nr_zapped_lock_chains++;
 #endif
 }
 
kernel/locking/lockdep_internals.h +1 -0
index 5dec0fe12507..35758e469ff7 100644
@@ -125,6 +125,7 @@ struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i);
 
 extern unsigned long nr_lock_classes;
 extern unsigned long nr_zapped_classes;
+extern unsigned long nr_zapped_lock_chains;
 extern unsigned long nr_list_entries;
 long lockdep_next_lockchain(long i);
 unsigned long lock_chain_count(void);
kernel/locking/lockdep_proc.c +2 -0
index 4c7dc0a8935d..7c15dd03cf49 100644
@@ -345,6 +345,8 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 	seq_puts(m, "\n");
 	seq_printf(m, " zapped classes:                %11lu\n",
 			nr_zapped_classes);
+	seq_printf(m, " zapped lock chains:            %11lu\n",
+			nr_zapped_lock_chains);
 	return 0;
 }
 
Signature · 1 line
2.18.1
author reviewer
#11 lore raw

PATCH v2 4/6 locking/lockdep: Reuse freed chain_hlocks entries

In reply to Waiman Long

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 freed chain_hlocks entries are formed into a chain block and put into a free bucketed list according to the block size. On allocation, the corresponding chain block bucket is searched first before allocating directly from the chain_hlocks array.

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 overflowing the chain_hlocks array 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 counters enables us to see how efficient the current workload is able to reuse the freed chain_hlocks entries in the bucketed lists. The nr_large_chain_blocks counter enables to see if we should increase the number of buckets (MAX_CHAIN_BUCKETS) available as linear search is used to find a matching chain block which is much slower than the O(1) time to find a chain block with size not bigger than MAX_CHAIN_BUCKETS.

An internal nfsd test that ran for more than an hour 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 chain_hlocks entries to spare:

  # cat /proc/lockdep_stats
     :
   dependency chains:                   24861 [max: 65536]
   dependency chain hlocks:            102232 [max: 327680]
     :
   zapped classes:                       1538
   zapped lock chains:                  57077
   free chain hlocks:                     335
   large chain blocks:                      0

By modifying MAX_CHAIN_BUCKETS to 3 in order to exercise the large chain blocks allocation and freeing code paths, the stats were:

  # cat /proc/lockdep_stats
     :
   dependency chains:                   24561 [max: 65536]
   dependency chain hlocks:            103098 [max: 327680]
     :
   zapped classes:                       1544
   zapped lock chains:                  57067
   free chain hlocks:                     383
   large chain blocks:                     64

By monitoring the output of lockdep_stats, the number of free chain hlocks and large chain blocks grew and shrank (sometimes to 0) repetitively as the test was progressing. There was no movement in the large chain blocks count with a MAX_CHAIN_BUCKETS value of 8.

---
 kernel/locking/lockdep.c           | 232 ++++++++++++++++++++++++++---
 kernel/locking/lockdep_internals.h |   2 +
 kernel/locking/lockdep_proc.c      |   4 +
 3 files changed, 219 insertions(+), 19 deletions(-)
kernel/locking/lockdep.c +213 -19
index 8293f7e80ee6..f7dcd4e77a70 100644
@@ -2627,6 +2627,208 @@ static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
 static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
 unsigned long nr_zapped_lock_chains;
 unsigned int nr_chain_hlocks;
+unsigned int nr_free_chain_hlocks;	/* Free cfhain_hlocks in buckets */
+unsigned int nr_large_chain_blocks;	/* size > MAX_CHAIN_BUCKETS */
+
+#ifdef CONFIG_PROVE_LOCKING
+/*
+ * As chain_hlocks entries are allocated and freed, the freed entries are
+ * grouped into chain blocks that can be reused again. These chain blocks
+ * are put into a bucketed list according to their block size.
+ *
+ * Two APIs are provided for chain block allocation and freeing:
+ *  - int alloc_chain_hlocks(int size)
+ *  - void free_chain_hlocks(int base, int size)
+ *
+ * A minimum allocation size of 2 entries is enforced. When a lock chain
+ * is freed, the corresponding chain_hlocks[] entries are put into one
+ * of the bucketed lists:
+ *   2 <= size <= MAX_CHAIN_BUCKETS => buckets[size-1]
+ *   > MAX_CHAIN_BUCKETS	    => buckets[0]
+ *
+ * When an allocation request is made, alloc_chain_hlocks() will first
+ * look up the matching bucketed list to find a free chain block. If not
+ * found, allocation will be made directly from the chain_hlocks array
+ * from the current nr_chain_hlocks value.
+ *
+ * Note that a chain_hlocks entry contain the class index which is
+ * crrently limited to 13 bits.
+ *
+ * The first 2 chain_hlocks entries in the chain block in the bucket
+ * list contains the following meta data:
+ * entry[0]:
+ *   Bit    15 - always set to 1 (it is not a class index)
+ *   Bits 0-14 - upper 15 bits of the next block index
+ * entry[1]    - lower 16 bits of next block index
+ *
+ * A next block index of all 1 bits means it is the end of the list.
+ *
+ * On the unsized bucket (buckets[0]), the 3rd and 4th entries contain
+ * the chain block size.
+ *
+ * entry[2] - upper 16 bits of the chain block size
+ * entry[3] - lower 16 bits of the chain block size
+ *
+ * TODO:
+ * Evaluate if merging neighoring chain blocks and breaking a large chain
+ * block into smaller ones can be helpful in reducing the number of free
+ * held_hlocks entries stored in the bucketed lists.
+ */
+#define MAX_CHAIN_BUCKETS	8
+#define CHAIN_HLOCKS_MASK	0xffff
+#define CHAIN_BLK_FLAG		(1U << 15)
+#define CHAIN_BLK_LIST_END	((u16)-1)
+
+/*
+ * An empty bucket has a value of -1. Otherwise, it represents an offset
+ * to the chain_hlocks array.
+ */
+static int chain_block_buckets[MAX_CHAIN_BUCKETS];
+
+static inline void init_chain_block_buckets(void)
+{
+	int i;
+
+	for (i = 0; i < MAX_CHAIN_BUCKETS; i++)
+		chain_block_buckets[i] = -1;
+}
+
+/*
+ * Return offset of next chain block or -1 if end of list.
+ */
+static inline int next_chain_block(int offset)
+{
+	if (chain_hlocks[offset] == CHAIN_BLK_LIST_END)
+		return -1;
+	return ((chain_hlocks[offset] & ~CHAIN_BLK_FLAG) << 16) |
+		 chain_hlocks[offset + 1];
+}
+
+static inline void set_chain_block(int offset, int size, int next)
+{
+	if (unlikely(offset < 0)) {
+		chain_block_buckets[0] = next;
+		return;
+	}
+	chain_hlocks[offset] = (next >> 16) | CHAIN_BLK_FLAG;
+	chain_hlocks[offset + 1] = next & CHAIN_HLOCKS_MASK;
+	if (size > MAX_CHAIN_BUCKETS) {
+		chain_hlocks[offset + 2] = size >> 16;
+		chain_hlocks[offset + 3] = size & CHAIN_HLOCKS_MASK;
+	}
+}
+
+/*
+ * This function should only be called for chain block in buckets[0].
+ */
+static inline int chain_block_size(int offset)
+{
+	return (chain_hlocks[offset + 2] << 16) | chain_hlocks[offset + 3];
+}
+
+/*
+ * Return offset of a chain block of the right size or -1 if not found.
+ */
+static inline int alloc_chain_hlocks_from_buckets(int size)
+{
+	int prev, curr, next;
+
+	if (!nr_free_chain_hlocks)
+		return -1;
+
+	if (size <= MAX_CHAIN_BUCKETS) {
+		curr = chain_block_buckets[size - 1];
+		if (curr < 0)
+			return -1;
+
+		chain_block_buckets[size - 1] = next_chain_block(curr);
+		nr_free_chain_hlocks -= size;
+		return curr;
+	}
+
+	/*
+	 * Look for a free chain block of the given size
+	 *
+	 * It is rare to have a lock chain with depth > MAX_CHAIN_BUCKETS.
+	 * It is also more expensive as we may iterate the whole list
+	 * without finding one.
+	 */
+	prev = -1;
+	curr = chain_block_buckets[0];
+	while (curr >= 0) {
+		next = next_chain_block(curr);
+		if (chain_block_size(curr) == size) {
+			set_chain_block(prev, 0, next);
+			nr_free_chain_hlocks -= size;
+			nr_large_chain_blocks--;
+			return curr;
+		}
+		prev = curr;
+		curr = next;
+	}
+	return -1;
+}
+
+static inline void free_chain_hlocks(int base, int size)
+{
+	if (size < 2)
+		size = 2;
+
+	nr_free_chain_hlocks += size;
+	if (size <= MAX_CHAIN_BUCKETS) {
+		set_chain_block(base, 0, chain_block_buckets[size - 1]);
+		chain_block_buckets[size - 1] = base;
+		return;
+	}
+	set_chain_block(base, size, chain_block_buckets[0]);
+	chain_block_buckets[0] = base;
+	nr_large_chain_blocks++;
+}
+#else
+static inline void init_chain_block_buckets(void)	{ }
+static inline int  alloc_chain_hlocks_from_buckets(int size)
+{
+	return -1;
+}
+#endif /* CONFIG_PROVE_LOCKING */
+
+/*
+ * The graph lock must be held before calling this function.
+ *
+ * Return: an offset to chain_hlocks if successful, or
+ *	   -1 with graph lock released
+ */
+static int alloc_chain_hlocks(int size)
+{
+	int curr;
+
+	if (size < 2)
+		size = 2;
+
+	curr = alloc_chain_hlocks_from_buckets(size);
+	if (curr >= 0)
+		return curr;
+
+	BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks));
+	BUILD_BUG_ON((1UL << 6)  <= ARRAY_SIZE(current->held_locks));
+	BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <=
+		     ARRAY_SIZE(lock_classes));
+
+	/*
+	 * Allocate directly from chain_hlocks.
+	 */
+	if (likely(nr_chain_hlocks + size <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
+		curr = nr_chain_hlocks;
+		nr_chain_hlocks += size;
+		return curr;
+	}
+	if (!debug_locks_off_graph_unlock())
+		return -1;
+
+	print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
+	dump_stack();
+	return -1;
+}
 
 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
 {
@@ -2822,28 +3024,17 @@ static inline int add_chain_cache(struct task_struct *curr,
 	chain->irq_context = hlock->irq_context;
 	i = get_first_held_lock(curr, hlock);
 	chain->depth = curr->lockdep_depth + 1 - i;
+	j = alloc_chain_hlocks(chain->depth);
+	if (j < 0)
+		return 0;
 
-	BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks));
-	BUILD_BUG_ON((1UL << 6)  <= ARRAY_SIZE(curr->held_locks));
-	BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <= ARRAY_SIZE(lock_classes));
-
-	if (likely(nr_chain_hlocks + chain->depth <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
-		chain->base = nr_chain_hlocks;
-		for (j = 0; j < chain->depth - 1; j++, i++) {
-			int lock_id = curr->held_locks[i].class_idx;
-			chain_hlocks[chain->base + j] = lock_id;
-		}
-		chain_hlocks[chain->base + j] = class - lock_classes;
-		nr_chain_hlocks += chain->depth;
-	} else {
-		if (!debug_locks_off_graph_unlock())
-			return 0;
+	chain->base = j;
+	for (j = 0; j < chain->depth - 1; j++, i++) {
+		int lock_id = curr->held_locks[i].class_idx;
 
-		print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
-		dump_stack();
-		return 0;
+		chain_hlocks[chain->base + j] = lock_id;
 	}
-
+	chain_hlocks[chain->base + j] = class - lock_classes;
 	hlist_add_head_rcu(&chain->entry, hash_head);
 	debug_atomic_inc(chain_lookup_misses);
 	inc_chains();
@@ -4786,6 +4977,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 	return;
 
 free_lock_chain:
+	free_chain_hlocks(chain->base, chain->depth);
 	/* Overwrite the chain key for concurrent RCU readers. */
 	WRITE_ONCE(chain->chain_key, INITIAL_CHAIN_KEY);
 	/*
@@ -5178,6 +5370,8 @@ EXPORT_SYMBOL_GPL(lockdep_unregister_key);
 
 void __init lockdep_init(void)
 {
+	init_chain_block_buckets();
+
 	printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");
 
 	printk("... MAX_LOCKDEP_SUBCLASSES:  %lu\n", MAX_LOCKDEP_SUBCLASSES);
kernel/locking/lockdep_internals.h +2 -0
index 35758e469ff7..91bbc5684103 100644
@@ -135,6 +135,8 @@ extern unsigned int nr_hardirq_chains;
 extern unsigned int nr_softirq_chains;
 extern unsigned int nr_process_chains;
 extern unsigned int nr_chain_hlocks;
+extern unsigned int nr_free_chain_hlocks;
+extern unsigned int nr_large_chain_blocks;
 
 extern unsigned int max_lockdep_depth;
 extern unsigned int max_bfs_queue_depth;
kernel/locking/lockdep_proc.c +4 -0
index 7c15dd03cf49..125c65e20bff 100644
@@ -347,6 +347,10 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 			nr_zapped_classes);
 	seq_printf(m, " zapped lock chains:            %11lu\n",
 			nr_zapped_lock_chains);
+	seq_printf(m, " free chain hlocks:             %11u\n",
+			nr_free_chain_hlocks);
+	seq_printf(m, " large chain blocks:            %11u\n",
+			nr_large_chain_blocks);
 	return 0;
 }
 
Signature · 1 line
2.18.1
maintainer
#12 lore raw

Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 5 lines · Waiman Long
kernel/locking/lockdep.c +4 -0
+#define CHAIN_HLOCKS_MASK	0xffff
 
+static inline void set_chain_block(int offset, int size, int next)
+{
+	if (unlikely(offset < 0)) {

kernel/locking/lockdep.c static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); · line 2719

Quoted 10 lines
kernel/locking/lockdep.c +10 -0
+		chain_block_buckets[0] = next;
+		return;
+	}
+	chain_hlocks[offset] = (next >> 16) | CHAIN_BLK_FLAG;
+	chain_hlocks[offset + 1] = next & CHAIN_HLOCKS_MASK;
+	if (size > MAX_CHAIN_BUCKETS) {
+		chain_hlocks[offset + 2] = size >> 16;
+		chain_hlocks[offset + 3] = size & CHAIN_HLOCKS_MASK;
+	}
+}

AFAICT HLOCKS_MASK is superfluous. That is, you're assigning to a u16, it will truncate automagically.

But if you want to make it more explicit, something like:

  chain_hlocks[offset + 1] = (u16)next;

might be easier to read still.

author reviewer
#13 lore raw

Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 18 lines · Peter Zijlstra
Quoted 4 lines · Waiman Long
kernel/locking/lockdep.c +4 -0
+#define CHAIN_HLOCKS_MASK	0xffff
+static inline void set_chain_block(int offset, int size, int next)
+{
+	if (unlikely(offset < 0)) {

kernel/locking/lockdep.c static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); · line 2719

Quoted 10 lines
kernel/locking/lockdep.c +10 -0
+		chain_block_buckets[0] = next;
+		return;
+	}
+	chain_hlocks[offset] = (next >> 16) | CHAIN_BLK_FLAG;
+	chain_hlocks[offset + 1] = next & CHAIN_HLOCKS_MASK;
+	if (size > MAX_CHAIN_BUCKETS) {
+		chain_hlocks[offset + 2] = size >> 16;
+		chain_hlocks[offset + 3] = size & CHAIN_HLOCKS_MASK;
+	}
+}

AFAICT HLOCKS_MASK is superfluous. That is, you're assigning to a u16, it will truncate automagically.

Quoted 6 lines

But if you want to make it more explicit, something like:

  chain_hlocks[offset + 1] = (u16)next;

might be easier to read still.

Yes, I am aware that the macro may not be needed. Will make the changes in the next version.

Thanks,
Longman

maintainer
#14 lore raw

Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

In reply to Waiman Long
Quoted 70 lines · Waiman Long
kernel/locking/lockdep.c +69 -0
+/*
+ * Return offset of a chain block of the right size or -1 if not found.
+ */
+static inline int alloc_chain_hlocks_from_buckets(int size)
+{
+	int prev, curr, next;
+
+	if (!nr_free_chain_hlocks)
+		return -1;
+
+	if (size <= MAX_CHAIN_BUCKETS) {
+		curr = chain_block_buckets[size - 1];
+		if (curr < 0)
+			return -1;
+
+		chain_block_buckets[size - 1] = next_chain_block(curr);
+		nr_free_chain_hlocks -= size;
+		return curr;
+	}
+
+	/*
+	 * Look for a free chain block of the given size
+	 *
+	 * It is rare to have a lock chain with depth > MAX_CHAIN_BUCKETS.
+	 * It is also more expensive as we may iterate the whole list
+	 * without finding one.
+	 */
+	prev = -1;
+	curr = chain_block_buckets[0];
+	while (curr >= 0) {
+		next = next_chain_block(curr);
+		if (chain_block_size(curr) == size) {
+			set_chain_block(prev, 0, next);
+			nr_free_chain_hlocks -= size;
+			nr_large_chain_blocks--;
+			return curr;
+		}
+		prev = curr;
+		curr = next;
+	}
+	return -1;
+}
 
+/*
+ * The graph lock must be held before calling this function.
+ *
+ * Return: an offset to chain_hlocks if successful, or
+ *	   -1 with graph lock released
+ */
+static int alloc_chain_hlocks(int size)
+{
+	int curr;
+
+	if (size < 2)
+		size = 2;
+
+	curr = alloc_chain_hlocks_from_buckets(size);
+	if (curr >= 0)
+		return curr;
+
+	BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks));
+	BUILD_BUG_ON((1UL << 6)  <= ARRAY_SIZE(current->held_locks));
+	BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <=
+		     ARRAY_SIZE(lock_classes));
+
+	/*
+	 * Allocate directly from chain_hlocks.
+	 */
+	if (likely(nr_chain_hlocks + size <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
+		curr = nr_chain_hlocks;

kernel/locking/lockdep.c static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);

Quoted 10 lines
kernel/locking/lockdep.c +10 -0
+		nr_chain_hlocks += size;
+		return curr;
+	}
+	if (!debug_locks_off_graph_unlock())
+		return -1;
+
+	print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
+	dump_stack();
+	return -1;
+}

*groan*....

That's _two_ allocators :/ And it can trivially fail, even if there's plenty space available.

Consider nr_chain_hlocks is exhaused, and @size is empty, but size+1 still has blocks.

I'm guessing you didn't make it a single allocator because you didn't want to implement block splitting? why?

author reviewer
#15 lore raw

Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 82 lines · Peter Zijlstra
Quoted 69 lines · Waiman Long
kernel/locking/lockdep.c +69 -0
+/*
+ * Return offset of a chain block of the right size or -1 if not found.
+ */
+static inline int alloc_chain_hlocks_from_buckets(int size)
+{
+	int prev, curr, next;
+
+	if (!nr_free_chain_hlocks)
+		return -1;
+
+	if (size <= MAX_CHAIN_BUCKETS) {
+		curr = chain_block_buckets[size - 1];
+		if (curr < 0)
+			return -1;
+
+		chain_block_buckets[size - 1] = next_chain_block(curr);
+		nr_free_chain_hlocks -= size;
+		return curr;
+	}
+
+	/*
+	 * Look for a free chain block of the given size
+	 *
+	 * It is rare to have a lock chain with depth > MAX_CHAIN_BUCKETS.
+	 * It is also more expensive as we may iterate the whole list
+	 * without finding one.
+	 */
+	prev = -1;
+	curr = chain_block_buckets[0];
+	while (curr >= 0) {
+		next = next_chain_block(curr);
+		if (chain_block_size(curr) == size) {
+			set_chain_block(prev, 0, next);
+			nr_free_chain_hlocks -= size;
+			nr_large_chain_blocks--;
+			return curr;
+		}
+		prev = curr;
+		curr = next;
+	}
+	return -1;
+}
+/*
+ * The graph lock must be held before calling this function.
+ *
+ * Return: an offset to chain_hlocks if successful, or
+ *	   -1 with graph lock released
+ */
+static int alloc_chain_hlocks(int size)
+{
+	int curr;
+
+	if (size < 2)
+		size = 2;
+
+	curr = alloc_chain_hlocks_from_buckets(size);
+	if (curr >= 0)
+		return curr;
+
+	BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks));
+	BUILD_BUG_ON((1UL << 6)  <= ARRAY_SIZE(current->held_locks));
+	BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <=
+		     ARRAY_SIZE(lock_classes));
+
+	/*
+	 * Allocate directly from chain_hlocks.
+	 */
+	if (likely(nr_chain_hlocks + size <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
+		curr = nr_chain_hlocks;

kernel/locking/lockdep.c static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); · line 2831

Quoted 10 lines
kernel/locking/lockdep.c +10 -0
+		nr_chain_hlocks += size;
+		return curr;
+	}
+	if (!debug_locks_off_graph_unlock())
+		return -1;
+
+	print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
+	dump_stack();
+	return -1;
+}

*groan*....

Quoted 9 lines

That's _two_ allocators :/ And it can trivially fail, even if there's plenty space available.

Consider nr_chain_hlocks is exhaused, and @size is empty, but size+1 still has blocks.

I'm guessing you didn't make it a single allocator because you didn't want to implement block splitting? why?

In my testing, most of the lock chains tend to be rather short (within the 2-8 range). I don't see a lot of free blocks left in the system after the test. So I don't see a need to implement block splitting for now.

If you think this is a feature that needs to be implemented for the patch to be complete, I can certainly add patch to do that. My initial thought is just to split long blocks in the unsized list for allocation request that is no longer than 8 to make thing easier.

Cheers,
Longman

maintainer
#16 lore raw

Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 11 lines · Waiman Long
Quoted 9 lines · Peter Zijlstra

That's _two_ allocators :/ And it can trivially fail, even if there's plenty space available.

Consider nr_chain_hlocks is exhaused, and @size is empty, but size+1 still has blocks.

I'm guessing you didn't make it a single allocator because you didn't want to implement block splitting? why?

Quoted 8 lines

In my testing, most of the lock chains tend to be rather short (within the 2-8 range). I don't see a lot of free blocks left in the system after the test. So I don't see a need to implement block splitting for now.

If you think this is a feature that needs to be implemented for the patch to be complete, I can certainly add patch to do that. My initial thought is just to split long blocks in the unsized list for allocation request that is no longer than 8 to make thing easier.

From an engineering POV I'd much prefer a single complete allocator over two half ones. We can leave block merger out of the initial allocator I suppose and worry about that if/when fragmentation really shows to be a problem.

I'm thinking worst-fit might work well for our use-case. Best-fit would result in a heap of tiny fragments and we don't have really large allocations, which is the Achilles-heel of worst-fit.

Also, since you put in a minimal allocation size of 2, but did not mandate size is a multiple of 2, there is a weird corner case of size-1 fragments. The simplest case is to leak those, but put in a counter so we can see if they're a problem -- there is a fairly trivial way to recover them without going full merge.

Also, there's a bunch of syzcaller reports of running out of ENTRIES/CHAIN_HLOCKS, perhaps try some of those workloads to better stress the allocator?

author reviewer
#17 lore raw

Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 19 lines · Peter Zijlstra
Quoted 10 lines · Waiman Long
Quoted 9 lines · Peter Zijlstra

That's _two_ allocators :/ And it can trivially fail, even if there's plenty space available.

Consider nr_chain_hlocks is exhaused, and @size is empty, but size+1 still has blocks.

I'm guessing you didn't make it a single allocator because you didn't want to implement block splitting? why?

Quoted 8 lines

In my testing, most of the lock chains tend to be rather short (within the 2-8 range). I don't see a lot of free blocks left in the system after the test. So I don't see a need to implement block splitting for now.

If you think this is a feature that needs to be implemented for the patch to be complete, I can certainly add patch to do that. My initial thought is just to split long blocks in the unsized list for allocation request that is no longer than 8 to make thing easier.

Quoted 8 lines

From an engineering POV I'd much prefer a single complete allocator over two half ones. We can leave block merger out of the initial allocator I suppose and worry about that if/when fragmentation really shows to be a problem.

I'm thinking worst-fit might work well for our use-case. Best-fit would result in a heap of tiny fragments and we don't have really large allocations, which is the Achilles-heel of worst-fit.

I am going to add a patch to split chain block as a last resort in case we run out of the main buffer.

Quoted 6 lines

Also, since you put in a minimal allocation size of 2, but did not mandate size is a multiple of 2, there is a weird corner case of size-1 fragments. The simplest case is to leak those, but put in a counter so we can see if they're a problem -- there is a fairly trivial way to recover them without going full merge.

There is no size-1 fragment. Are you referring to the those blocks with a size of 2, but with only one entry used? There are some wasted space there. I can add a counter to track that.

Cheers,
Longman

Quoted 5 lines

Also, there's a bunch of syzcaller reports of running out of ENTRIES/CHAIN_HLOCKS, perhaps try some of those workloads to better stress the allocator?

maintainer
#18 lore raw

Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 7 lines · Waiman Long
Quoted 3 lines · Peter Zijlstra

I'm thinking worst-fit might work well for our use-case. Best-fit would result in a heap of tiny fragments and we don't have really large allocations, which is the Achilles-heel of worst-fit.

I am going to add a patch to split chain block as a last resort in case we run out of the main buffer.

It will be the common path; you'll start with a single huge fragment.

Remember, 1 allocator is better than 2.

Quoted 9 lines
Quoted 5 lines

Also, since you put in a minimal allocation size of 2, but did not mandate size is a multiple of 2, there is a weird corner case of size-1 fragments. The simplest case is to leak those, but put in a counter so we can see if they're a problem -- there is a fairly trivial way to recover them without going full merge.

There is no size-1 fragment. Are you referring to the those blocks with a size of 2, but with only one entry used? There are some wasted space there. I can add a counter to track that.

There will be; imagine you have a size-6 fragment and request a size-5, then we'll have to split off one. But one is too short to encode on the free lists.

Suppose you tag them with -2, then on free of the size-5, we can check if curr+size+1 is -2 and reunite.

First-fit or best-fit would result in lots of that, hence my suggestion to use worst-fit if you can't find an exact match.

author reviewer
#19 lore raw

Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 10 lines · Peter Zijlstra
Quoted 6 lines · Waiman Long
Quoted 3 lines · Peter Zijlstra

I'm thinking worst-fit might work well for our use-case. Best-fit would result in a heap of tiny fragments and we don't have really large allocations, which is the Achilles-heel of worst-fit.

I am going to add a patch to split chain block as a last resort in case we run out of the main buffer.

It will be the common path; you'll start with a single huge fragment.

Remember, 1 allocator is better than 2.

One reason why I keep the array allocation code is because it is simple and fast. Using a free block in the bucket will be a bit slower. Still we are just dealing with the first block in the list as long as the size isn't bigger than MAX_CHAIN_BUCKETS. Now if we need to deal with block splitting (or even merging), it will be even more slow. Given the fact that we are holding the graph lock in doing all these. It could have a visible impact on performance.

That is the primary reason why I intend to allow block splitting only as the last resort when the chain_hlocks array is running out.

Quoted 12 lines
Quoted 8 lines
Quoted 5 lines

Also, since you put in a minimal allocation size of 2, but did not mandate size is a multiple of 2, there is a weird corner case of size-1 fragments. The simplest case is to leak those, but put in a counter so we can see if they're a problem -- there is a fairly trivial way to recover them without going full merge.

There is no size-1 fragment. Are you referring to the those blocks with a size of 2, but with only one entry used? There are some wasted space there. I can add a counter to track that.

There will be; imagine you have a size-6 fragment and request a size-5, then we'll have to split off one. But one is too short to encode on the free lists.

Quoted 6 lines

Suppose you tag them with -2, then on free of the size-5, we can check if curr+size+1 is -2 and reunite.

First-fit or best-fit would result in lots of that, hence my suggestion to use worst-fit if you can't find an exact match.

What I am thinking is to allow block splitting only if it has a size that is at least 2 larger than the desire value. In that way, we will not produce a fragment that is less than 2 in size. The down side is that we have fewer viable candidates for splitting.

Cheers,
Longman

maintainer
#20 lore raw

Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

In reply to Waiman Long
Quoted 4 lines · Waiman Long

An internal nfsd test that ran for more than an hour could cause the following message to be displayed.

  [ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!

I'm guessing the pertinent detail you forget to mention here is that that test re-loads the nfs modules lots of times?

author reviewer
#21 lore raw

Re: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 8 lines · Peter Zijlstra
Quoted 4 lines · Waiman Long

An internal nfsd test that ran for more than an hour could cause the following message to be displayed.

  [ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!

I'm guessing the pertinent detail you forget to mention here is that that test re-loads the nfs modules lots of times?

Yes, that is true. I will mention it in the next version.

Thanks,
Longman

author reviewer
#22 lore raw

PATCH v2 5/6 locking/lockdep: Decrement irq context counters when removing lock chain

In reply to Waiman Long

There are currently three counters to track the irq context of a lock chain - nr_hardirq_chains, nr_softirq_chains and nr_process_chains. They are incremented when a new lock chain is added, but they are not decremented when a lock chain is removed. That causes some of the statistic counts reported by /proc/lockdep_stats to be incorrect.

Fix that by decrementing the right counter when a lock chain is removed.

Fixes a0b0fd53e1e6 ("locking/lockdep: Free lock classes that are no longer in use")
---
 kernel/locking/lockdep.c           | 35 +++++++++++++++++++++---------
 kernel/locking/lockdep_internals.h |  6 +++++
 2 files changed, 31 insertions(+), 10 deletions(-)
kernel/locking/lockdep.c +25 -10
index f7dcd4e77a70..4ea23bb6f8d3 100644
@@ -2300,16 +2300,24 @@ static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
 	return 0;
 }
 
-static void inc_chains(void)
+static void inc_chains(int irq_context)
 {
-	if (current->hardirq_context)
+	if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT)
 		nr_hardirq_chains++;
-	else {
-		if (current->softirq_context)
-			nr_softirq_chains++;
-		else
-			nr_process_chains++;
-	}
+	else if (irq_context & LOCK_CHAIN_SOFTIRQ_CONTEXT)
+		nr_softirq_chains++;
+	else
+		nr_process_chains++;
+}
+
+static void dec_chains(int irq_context)
+{
+	if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT)
+		nr_hardirq_chains--;
+	else if (irq_context & LOCK_CHAIN_SOFTIRQ_CONTEXT)
+		nr_softirq_chains--;
+	else
+		nr_process_chains--;
 }
 
 #else
@@ -2325,6 +2333,10 @@ static inline void inc_chains(void)
 	nr_process_chains++;
 }
 
+static void dec_chains(int irq_context)
+{
+	nr_process_chains--;
+}
 #endif /* CONFIG_TRACE_IRQFLAGS */
 
 static void
@@ -3037,7 +3049,7 @@ static inline int add_chain_cache(struct task_struct *curr,
 	chain_hlocks[chain->base + j] = class - lock_classes;
 	hlist_add_head_rcu(&chain->entry, hash_head);
 	debug_atomic_inc(chain_lookup_misses);
-	inc_chains();
+	inc_chains(chain->irq_context);
 
 	return 1;
 }
@@ -3790,7 +3802,8 @@ mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
 
 static inline unsigned int task_irq_context(struct task_struct *task)
 {
-	return 2 * !!task->hardirq_context + !!task->softirq_context;
+	return LOCK_CHAIN_HARDIRQ_CONTEXT * !!task->hardirq_context +
+	       LOCK_CHAIN_SOFTIRQ_CONTEXT * !!task->softirq_context;
 }
 
 static int separate_irq_context(struct task_struct *curr,
@@ -4980,6 +4993,8 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 	free_chain_hlocks(chain->base, chain->depth);
 	/* Overwrite the chain key for concurrent RCU readers. */
 	WRITE_ONCE(chain->chain_key, INITIAL_CHAIN_KEY);
+	dec_chains(chain->irq_context);
+
 	/*
 	 * Note: calling hlist_del_rcu() from inside a
 	 * hlist_for_each_entry_rcu() loop is safe.
kernel/locking/lockdep_internals.h +6 -0
index 91bbc5684103..9425155b9053 100644
@@ -98,6 +98,12 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ =
 
 #define MAX_LOCKDEP_CHAINS_BITS	16
 
+/*
+ * Bit definitions for lock_chain.irq_context
+ */
+#define LOCK_CHAIN_SOFTIRQ_CONTEXT	(1 << 0)
+#define LOCK_CHAIN_HARDIRQ_CONTEXT	(1 << 1)
+
 /*
  * Stack-trace: tightly packed array of stack backtrace
  * addresses. Protected by the hash_lock.
Signature · 1 line
2.18.1
maintainer
#23 lore raw

Re: [PATCH v2 5/6] locking/lockdep: Decrement irq context counters when removing lock chain

Quoted 10 lines · Waiman Long

There are currently three counters to track the irq context of a lock chain - nr_hardirq_chains, nr_softirq_chains and nr_process_chains. They are incremented when a new lock chain is added, but they are not decremented when a lock chain is removed. That causes some of the statistic counts reported by /proc/lockdep_stats to be incorrect.

Fix that by decrementing the right counter when a lock chain is removed.

Fixes a0b0fd53e1e6 ("locking/lockdep: Free lock classes that are no longer in use")

Fixes go at the start of a series, because if the depend on prior patches (as this one does) we cannot apply them.

author reviewer
#24 lore raw

Re: [PATCH v2 5/6] locking/lockdep: Decrement irq context counters when removing lock chain

Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Waiman Long

There are currently three counters to track the irq context of a lock chain - nr_hardirq_chains, nr_softirq_chains and nr_process_chains. They are incremented when a new lock chain is added, but they are not decremented when a lock chain is removed. That causes some of the statistic counts reported by /proc/lockdep_stats to be incorrect.

Quoted 7 lines
Quoted 4 lines

Fix that by decrementing the right counter when a lock chain is removed.

Fixes a0b0fd53e1e6 ("locking/lockdep: Free lock classes that are no longer in use")

Fixes go at the start of a series, because if the depend on prior patches (as this one does) we cannot apply them.

Will put it at the front in the next version.

Cheers,
Longman

author reviewer
#25 lore raw

PATCH v2 6/6 locking/lockdep: Display irq_context names in /proc/lockdep_chains

In reply to Waiman Long

Currently, the irq_context field of a lock chains displayed in /proc/lockdep_chains is just a number. It is likely that many people may not know what a non-zero number means. To make the information more useful, print the actual irq names ("softirq" and "hardirq") instead.

---
 kernel/locking/lockdep_proc.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)
kernel/locking/lockdep_proc.c +8 -1
index 125c65e20bff..7f08bb4e7037 100644
@@ -128,6 +128,13 @@ static int lc_show(struct seq_file *m, void *v)
 	struct lock_chain *chain = v;
 	struct lock_class *class;
 	int i;
+	static const char * const irq_strs[] = {
+		[0]			     = "0",
+		[LOCK_CHAIN_HARDIRQ_CONTEXT] = "hardirq",
+		[LOCK_CHAIN_SOFTIRQ_CONTEXT] = "softirq",
+		[LOCK_CHAIN_SOFTIRQ_CONTEXT|
+		 LOCK_CHAIN_HARDIRQ_CONTEXT] = "hardirq|softirq",
+	};
 
 	if (v == SEQ_START_TOKEN) {
 		if (nr_chain_hlocks > MAX_LOCKDEP_CHAIN_HLOCKS)
@@ -136,7 +143,7 @@ static int lc_show(struct seq_file *m, void *v)
 		return 0;
 	}
 
-	seq_printf(m, "irq_context: %d\n", chain->irq_context);
+	seq_printf(m, "irq_context: %s\n", irq_strs[chain->irq_context]);
 
 	for (i = 0; i < chain->depth; i++) {
 		class = lock_chain_get_class(chain, i);
Signature · 1 line
2.18.1
author reviewer
#26 lore raw
In reply to Waiman Long
Quoted 32 lines · Waiman Long

v2:
- Revamp the chain_hlocks reuse patch to store the freed chain_hlocks information in the chain_hlocks entries themselves avoiding the need of a separate set of tracking structures. This, however, requires a minimum allocation size of at least 2. Thanks to PeterZ for his review and inspiring this change.
- Remove the leakage counter as it is no longer applicable.
- Add patch 6 to make the output of /proc/lockdep_chains more readable.

It was found that when running a workload that kept on adding lock classes and then zapping them repetitively, the system will eventually run out of chain_hlocks[] entries even though there were still plenty of other lockdep data buffers available.

  [ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!
  [ 4318.444809] turning off the locking correctness validator.

In order to fix this problem, we have to make chain_hlocks[] entries reusable just like other lockdep arrays. Besides that, the patchset also adds some zapped class and chain_hlocks counters to be tracked by /proc/lockdep_stats. It also fixes leakage in the irq context counters and makes the output of /proc/lockdep_chains more readable.

Waiman Long (6):
locking/lockdep: Track number of zapped classes locking/lockdep: Throw away all lock chains with zapped class locking/lockdep: Track number of zapped lock chains locking/lockdep: Reuse freed chain_hlocks entries locking/lockdep: Decrement irq context counters when removing lock
chain
locking/lockdep: Display irq_context names in /proc/lockdep_chains

Quoted 5 lines
 kernel/locking/lockdep.c           | 307 +++++++++++++++++++++++------
 kernel/locking/lockdep_internals.h |  14 +-
 kernel/locking/lockdep_proc.c      |  26 ++-
 3 files changed, 282 insertions(+), 65 deletions(-)

Ping! Any comments or suggestion for further improvement?

Cheers,
Longman

maintainer
#27 lore raw
Quoted 1 line · Waiman Long

Ping! Any comments or suggestion for further improvement?

You got stuck in the xmas pile -- I haven't looked at email in 2 weeks. I'll try and get to it soon-ish :-)

author reviewer
#28 lore raw
Quoted 6 lines · Peter Zijlstra
Quoted 1 line · Waiman Long

Ping! Any comments or suggestion for further improvement?

You got stuck in the xmas pile -- I haven't looked at email in 2 weeks. I'll try and get to it soon-ish :-)

Thanks!
Longman