Skip to contentSkip to conversation

locking/lockdep: Reuse zapped chain_hlocks entries

PATCH Superseded Waiman Long 2 participants 24 messages Feb 3, 2020 – Feb 5, 2020 Locking primitives

v5 of 6 Superseded Latest is v6 →

lore
Share & tools
lore

Waiman Long

author reviewer
#0 lore raw

v5 cover locking/lockdep: Reuse zapped chain_hlocks entries

v5:
- Fix more build errors reported by kbuild test robot.

v4:
- Fix build errors reported by kbuild test robot.
- Adopt the single chain block allocator code suggested by PeterZ which combine the last 3 patches of v3 series.
- Add another patch to introduce a fast path in the chain block allocator.
- In patch 1, move the inc_chains() out of CONFIG_TRACE_IRQFLAGS conditional compilation block.

v3:
- Move the bug fix patches to the beginning of the series.
- Include a number of changes as suggested by PeterZ.
- Increase MAX_CHAIN_BUCKETS from 8 to 10 to reduce the chance of using the unsized list.
- Add patch 7 to add a lockdep_early_init() call.
- Add patch 8 to allocate chain hlocks by splitting large chain block as a last resort.

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 (7):
locking/lockdep: Decrement irq context counters when removing lock
chain
locking/lockdep: Display irq_context names in /proc/lockdep_chains 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: Add a fast path for chain_hlocks allocation

 kernel/locking/lockdep.c           | 335 ++++++++++++++++++++++++-----
 kernel/locking/lockdep_internals.h |  13 +-
 kernel/locking/lockdep_proc.c      |  28 ++-
 3 files changed, 311 insertions(+), 65 deletions(-)
Signature · 1 line
2.18.1
author reviewer
#1 lore raw

PATCH v5 1/7 locking/lockdep: Decrement irq context counters when removing lock chain

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.

Since inc_chains() no longer accesses hardirq_context and softirq_context directly, it is moved out from the CONFIG_TRACE_IRQFLAGS conditional compilation block.

Fixes a0b0fd53e1e6 ("locking/lockdep: Free lock classes that are no longer in use")
---
 kernel/locking/lockdep.c           | 40 +++++++++++++++++-------------
 kernel/locking/lockdep_internals.h |  6 +++++
 2 files changed, 29 insertions(+), 17 deletions(-)
kernel/locking/lockdep.c +23 -17
index 32406ef0d6a2..35449f5b79fb 100644
@@ -2298,18 +2298,6 @@ static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
 	return 0;
 }
 
-static void inc_chains(void)
-{
-	if (current->hardirq_context)
-		nr_hardirq_chains++;
-	else {
-		if (current->softirq_context)
-			nr_softirq_chains++;
-		else
-			nr_process_chains++;
-	}
-}
-
 #else
 
 static inline int check_irq_usage(struct task_struct *curr,
@@ -2317,13 +2305,27 @@ static inline int check_irq_usage(struct task_struct *curr,
 {
 	return 1;
 }
+#endif /* CONFIG_TRACE_IRQFLAGS */
 
-static inline void inc_chains(void)
+static void inc_chains(int irq_context)
 {
-	nr_process_chains++;
+	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++;
 }
 
-#endif /* CONFIG_TRACE_IRQFLAGS */
+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--;
+}
 
 static void
 print_deadlock_scenario(struct held_lock *nxt, struct held_lock *prv)
@@ -2843,7 +2845,7 @@ static inline int add_chain_cache(struct task_struct *curr,
 
 	hlist_add_head_rcu(&chain->entry, hash_head);
 	debug_atomic_inc(chain_lookup_misses);
-	inc_chains();
+	inc_chains(chain->irq_context);
 
 	return 1;
 }
@@ -3596,7 +3598,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,
@@ -4798,6 +4801,8 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 		return;
 	/* Overwrite the chain key for concurrent RCU readers. */
 	WRITE_ONCE(chain->chain_key, chain_key);
+	dec_chains(chain->irq_context);
+
 	/*
 	 * Note: calling hlist_del_rcu() from inside a
 	 * hlist_for_each_entry_rcu() loop is safe.
@@ -4819,6 +4824,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 	}
 	*new_chain = *chain;
 	hlist_add_head_rcu(&new_chain->entry, chainhashentry(chain_key));
+	inc_chains(new_chain->irq_context);
 #endif
 }
 
kernel/locking/lockdep_internals.h +6 -0
index 18d85aebbb57..a525368b8cf6 100644
@@ -106,6 +106,12 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ =
 #define STACK_TRACE_HASH_SIZE	16384
 #endif
 
+/*
+ * Bit definitions for lock_chain.irq_context
+ */
+#define LOCK_CHAIN_SOFTIRQ_CONTEXT	(1 << 0)
+#define LOCK_CHAIN_HARDIRQ_CONTEXT	(1 << 1)
+
 #define MAX_LOCKDEP_CHAINS	(1UL << MAX_LOCKDEP_CHAINS_BITS)
 
 #define MAX_LOCKDEP_CHAIN_HLOCKS (MAX_LOCKDEP_CHAINS*5)
Signature · 1 line
2.18.1
author reviewer
#2 lore raw

PATCH v5 2/7 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 9bb6d2497b04..0f6842bcfba8 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
#3 lore raw

PATCH v5 3/7 locking/lockdep: Track number of zapped classes

In reply to 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 counter to track that and show it in /proc/lockdep_stats.

---
 kernel/locking/lockdep.c           | 2 ++
 kernel/locking/lockdep_internals.h | 1 +
 kernel/locking/lockdep_proc.c      | 6 ++++++
 3 files changed, 9 insertions(+)
kernel/locking/lockdep.c +2 -0
index 35449f5b79fb..28222d03345f 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
@@ -4880,6 +4881,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 a525368b8cf6..76db80446a32 100644
@@ -130,6 +130,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 +6 -0
index 0f6842bcfba8..453e497b6124 100644
@@ -343,6 +343,12 @@ 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.
+	 */
+	seq_puts(m, "\n");
+	seq_printf(m, " zapped classes:                %11lu\n",
+			nr_zapped_classes);
 	return 0;
 }
 
Signature · 1 line
2.18.1
author reviewer
#4 lore raw

PATCH v5 4/7 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 likely to be invalid. If the zapped class is at the end of the chain, the partial chain without the zapped class should have been stored already as the current code will store all its predecessor chains. If the zapped class 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. I would rather prefer storing the chain only when it actually happens.

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           | 37 ++++--------------------------
 kernel/locking/lockdep_internals.h |  4 ++--
 kernel/locking/lockdep_proc.c      |  2 +-
 3 files changed, 7 insertions(+), 36 deletions(-)
kernel/locking/lockdep.c +4 -33
index 28222d03345f..ef2a6432dd10 100644
@@ -2625,8 +2625,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)
 {
@@ -4772,36 +4772,23 @@ 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);
 	dec_chains(chain->irq_context);
 
 	/*
@@ -4810,22 +4797,6 @@ 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);
-	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));
-	inc_chains(new_chain->irq_context);
 #endif
 }
 
kernel/locking/lockdep_internals.h +2 -2
index 76db80446a32..926bfa4b4564 100644
@@ -134,14 +134,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 453e497b6124..ca735cb83f48 100644
@@ -278,7 +278,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
author reviewer
#5 lore raw

PATCH v5 5/7 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      | 4 ++++
 3 files changed, 7 insertions(+)
kernel/locking/lockdep.c +2 -0
index ef2a6432dd10..a63976c75253 100644
@@ -2626,6 +2626,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)
@@ -4797,6 +4798,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 926bfa4b4564..af722ceeda33 100644
@@ -131,6 +131,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 +4 -0
index ca735cb83f48..92fe0742453c 100644
@@ -349,6 +349,10 @@ 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);
+#ifdef CONFIG_PROVE_LOCKING
+	seq_printf(m, " zapped lock chains:            %11lu\n",
+			nr_zapped_lock_chains);
+#endif
 	return 0;
 }
 
Signature · 1 line
2.18.1
author reviewer
#6 lore raw

PATCH v5 6/7 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 chain_hlocks entries are put into bucketed lists (MAX_CHAIN_BUCKETS) of chain blocks. Bucket 0 is the dump bucket which houses chain blocks of size larger than MAX_CHAIN_BUCKETS. Initially, the whole array is in one chain block in bucket 0.

Allocation requests for the chain_hlocks are fulfilled first by looking for chain block of matching size. If not found, a larger chain block is split. As 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. When the chain_hlocks[] array is nearly full or highly fragmented, there is a slight chance that 1-entry fragment will be created during the chain block splitting process. Those 1-entry fragments will be discarded and hence leaked.

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 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 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 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 chain_hlocks entries to spare:

  # cat /proc/lockdep_stats
     :
   dependency chains:                   26723 [max: 65536]
   dependency chain hlocks:            115052 [max: 327680]
     :
   zapped classes:                       1538
   zapped lock chains:                  56990
   large chain blocks:                      0
---
 kernel/locking/lockdep.c           | 242 +++++++++++++++++++++++++++--
 kernel/locking/lockdep_internals.h |   3 +-
 kernel/locking/lockdep_proc.c      |   9 +-
 3 files changed, 239 insertions(+), 15 deletions(-)
kernel/locking/lockdep.c +231 -11
index a63976c75253..70288bb2331d 100644
@@ -1071,13 +1071,15 @@ static inline void check_data_structures(void) { }
 
 #endif /* CONFIG_DEBUG_LOCKDEP */
 
+static void init_chain_block_buckets(void);
+
 /*
  * Initialize the lock_classes[] array elements, the free_lock_classes list
  * and also the delayed_free structure.
  */
 static void init_data_structures_once(void)
 {
-	static bool ds_initialized, rcu_head_initialized;
+	static bool __read_mostly ds_initialized, rcu_head_initialized;
 	int i;
 
 	if (likely(rcu_head_initialized))
@@ -1101,6 +1103,7 @@ static void init_data_structures_once(void)
 		INIT_LIST_HEAD(&lock_classes[i].locks_after);
 		INIT_LIST_HEAD(&lock_classes[i].locks_before);
 	}
+	init_chain_block_buckets();
 }
 
 static inline struct hlist_head *keyhashentry(const struct lock_class_key *key)
@@ -2627,7 +2630,221 @@ 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;
+unsigned int nr_free_chain_hlocks;	/* Free cfhain_hlocks in buckets */
+unsigned int nr_large_chain_blocks;	/* size > MAX_CHAIN_BUCKETS */
+
+/*
+ * 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 (bucket-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
+ */
+#define MAX_CHAIN_BUCKETS	10
+#define CHAIN_BLK_FLAG		(1U << 15)
+#define CHAIN_BLK_LIST_END	0xFFFFU
+
+static int chain_block_buckets[MAX_CHAIN_BUCKETS];
+
+static inline int size_to_bucket(int size)
+{
+	if (size > MAX_CHAIN_BUCKETS)
+		return 0;
+
+	return size - 1;
+}
+
+/*
+ * Iterate all the chain blocks in a bucket.
+ * The loop body has to set the next parameter.
+ */
+#define for_each_chain_block(bucket, prev, curr, next)		\
+	for ((prev) = bucket - MAX_CHAIN_BUCKETS,		\
+	     (curr) = chain_block_buckets[bucket];		\
+	     (curr) >= 0;					\
+	     (prev) = (curr), (curr) = (next))
+
+/*
+ * next block or -1
+ */
+static inline int chain_block_next(int offset)
+{
+	int next = chain_hlocks[offset];
+
+	WARN_ON_ONCE(!(next & CHAIN_BLK_FLAG));
+
+	if (next == CHAIN_BLK_LIST_END)
+		return -1;
+
+	next &= ~CHAIN_BLK_FLAG;
+	next <<= 16;
+	next |= chain_hlocks[offset + 1];
+
+	return next;
+}
+
+/*
+ * bucket-0 only
+ */
+static inline int chain_block_size(int offset)
+{
+	return (chain_hlocks[offset + 2] << 16) | chain_hlocks[offset + 3];
+}
+
+static inline void init_chain_block(int offset, int next, int bucket, int size)
+{
+	chain_hlocks[offset] = (next >> 16) | CHAIN_BLK_FLAG;
+	chain_hlocks[offset + 1] = (u16)next;
+
+	if (bucket == 0) {
+		chain_hlocks[offset + 2] = size >> 16;
+		chain_hlocks[offset + 3] = (u16)size;
+	}
+}
+
+static inline void add_chain_block(int offset, int size)
+{
+	int bucket = size_to_bucket(size);
+	int next = chain_block_buckets[bucket];
+
+	if (unlikely(size < 2))
+		return; // XXX leak!
+
+	init_chain_block(offset, next, bucket, size);
+	chain_block_buckets[bucket] = offset;
+	nr_free_chain_hlocks += size;
+
+	if (bucket == 0)
+		nr_large_chain_blocks++;
+}
+
+/*
+ * When offset < 0, the bucket number is encoded in it.
+ */
+static inline void del_chain_block(int offset, int size, int next)
+{
+	int bucket = size_to_bucket(size);
+
+	nr_free_chain_hlocks -= size;
+	if (offset < 0)
+		chain_block_buckets[offset + MAX_CHAIN_BUCKETS] = next;
+	else
+		init_chain_block(offset, next, bucket, size);
+
+	if (bucket == 0)
+		nr_large_chain_blocks--;
+}
+
+static void init_chain_block_buckets(void)
+{
+	int i;
+
+	for (i = 0; i < MAX_CHAIN_BUCKETS; i++)
+		chain_block_buckets[i] = -1;
+
+	add_chain_block(0, ARRAY_SIZE(chain_hlocks));
+}
+
+/*
+ * Return offset of a chain block of the right size or -1 if not found.
+ *
+ * Fairly simple worst-fit allocator with the addition of a number of size
+ * specific free lists.
+ */
+static int alloc_chain_hlocks(int req)
+{
+	int max_prev, max_curr, max_next, max_size = INT_MIN;
+	int prev, curr, next, size;
+	int bucket;
+
+	/*
+	 * We rely on the MSB to act as an escape bit to denote freelist
+	 * pointers. Make sure this bit isn't set in 'normal' class_idx usage.
+	 */
+	BUILD_BUG_ON((MAX_LOCKDEP_KEYS-1) & CHAIN_BLK_FLAG);
+
+	init_data_structures_once();
+
+	if (!nr_free_chain_hlocks)
+		return -1;
+
+	/*
+	 * We require a minimum of 2 (u16) entries to encode a freelist
+	 * 'pointer'.
+	 */
+	req = max(req, 2);
+	bucket = size_to_bucket(req);
+
+	if (bucket != 0) {
+		curr = chain_block_buckets[bucket];
+		if (curr < 0)
+			goto search;
+
+		del_chain_block(bucket - MAX_CHAIN_BUCKETS, req,
+				chain_block_next(curr));
+		return curr;
+	}
+
+search:
+	/*
+	 * linear search in the 'dump' bucket; look for an exact match or the
+	 * largest block.
+	 */
+	for_each_chain_block(0, prev, curr, next) {
+		size = chain_block_size(curr);
+		next = chain_block_next(curr);
+
+		if (size == req) {
+			del_chain_block(prev, req, next);
+			return curr;
+		}
+
+		if (size > max_size) {
+			max_prev = prev;
+			max_curr = curr;
+			max_next = next;
+			max_size = size;
+		}
+	}
+
+	if (likely(max_size > req)) {
+		del_chain_block(max_prev, max_size, max_next);
+		add_chain_block(max_curr + req, max_size - req);
+		return max_curr;
+	}
+
+	/*
+	 * Last resort, split a block in a larger sized bucket.
+	 */
+	for (size = MAX_CHAIN_BUCKETS; size > req; size--) {
+		bucket = size_to_bucket(size);
+		curr = chain_block_buckets[bucket];
+		if (curr < 0)
+			continue;
+
+		del_chain_block(bucket - MAX_CHAIN_BUCKETS, size,
+				chain_block_next(curr));
+		add_chain_block(curr + req, size - req);
+		return curr;
+	}
+
+	return -1;
+}
+
+static inline void free_chain_hlocks(int base, int size)
+{
+	add_chain_block(base, max(size, 2));
+}
 
 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
 {
@@ -2828,15 +3045,8 @@ static inline int add_chain_cache(struct task_struct *curr,
 	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 {
+	j = alloc_chain_hlocks(chain->depth);
+	if (j < 0) {
 		if (!debug_locks_off_graph_unlock())
 			return 0;
 
@@ -2845,6 +3055,13 @@ static inline int add_chain_cache(struct task_struct *curr,
 		return 0;
 	}
 
+	chain->base = j;
+	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;
 	hlist_add_head_rcu(&chain->entry, hash_head);
 	debug_atomic_inc(chain_lookup_misses);
 	inc_chains(chain->irq_context);
@@ -2991,6 +3208,8 @@ static inline int validate_chain(struct task_struct *curr,
 {
 	return 1;
 }
+
+static void init_chain_block_buckets(void)	{ }
 #endif /* CONFIG_PROVE_LOCKING */
 
 /*
@@ -4788,6 +5007,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);
 	dec_chains(chain->irq_context);
kernel/locking/lockdep_internals.h +2 -1
index af722ceeda33..5040e6729c05 100644
@@ -140,7 +140,8 @@ 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 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 +6 -3
index 92fe0742453c..14932ea50317 100644
@@ -137,7 +137,7 @@ static int lc_show(struct seq_file *m, void *v)
 	};
 
 	if (v == SEQ_START_TOKEN) {
-		if (nr_chain_hlocks > MAX_LOCKDEP_CHAIN_HLOCKS)
+		if (!nr_free_chain_hlocks)
 			seq_printf(m, "(buggered) ");
 		seq_printf(m, "all lock chains:\n");
 		return 0;
@@ -278,8 +278,9 @@ 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:       %11u [max: %lu]\n",
-			nr_chain_hlocks, MAX_LOCKDEP_CHAIN_HLOCKS);
+	seq_printf(m, " dependency chain hlocks:       %11lu [max: %lu]\n",
+			MAX_LOCKDEP_CHAIN_HLOCKS - nr_free_chain_hlocks,
+			MAX_LOCKDEP_CHAIN_HLOCKS);
 #endif
 
 #ifdef CONFIG_TRACE_IRQFLAGS
@@ -352,6 +353,8 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 #ifdef CONFIG_PROVE_LOCKING
 	seq_printf(m, " zapped lock chains:            %11lu\n",
 			nr_zapped_lock_chains);
+	seq_printf(m, " large chain blocks:            %11u\n",
+			nr_large_chain_blocks);
 #endif
 	return 0;
 }
Signature · 1 line
2.18.1
maintainer
#7 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

Review

Quoted 2 lines · Waiman Long
(quoted diff) +2 -0
+	if (unlikely(size < 2))
+		return; // XXX leak!

Stuck this on top...

kernel/locking/lockdep.c +15 -5
@@ -2631,7 +2631,8 @@ struct lock_chain lock_chains[MAX_LOCKDE
 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_free_chain_hlocks;	/* Free cfhain_hlocks in buckets */
+unsigned int nr_free_chain_hlocks;	/* Free chain_hlocks in buckets */
+unsigned int nr_lost_chain_hlocks;	/* Lost chain_hlocks */
 unsigned int nr_large_chain_blocks;	/* size > MAX_CHAIN_BUCKETS */
 
 /*
@@ -2718,8 +2719,17 @@ static inline void add_chain_block(int o
 	int bucket = size_to_bucket(size);
 	int next = chain_block_buckets[bucket];
 
-	if (unlikely(size < 2))
-		return; // XXX leak!
+	if (unlikely(size < 2)) {
+		/*
+		 * We can't store single entries on the freelist. Leak them.
+		 *
+		 * One possible way out would be to uniquely mark them, other
+		 * than with CHAIN_BLK_FLAG, such that we can recover them when
+		 * the block before it is re-added.
+		 */
+		nr_lost_chain_hlocks++;
+		return;
+	}
 
 	init_chain_block(offset, next, bucket, size);
 	chain_block_buckets[bucket] = offset;
@@ -2798,8 +2808,8 @@ static int alloc_chain_hlocks(int req)
 
 search:
 	/*
-	 * linear search in the 'dump' bucket; look for an exact match or the
-	 * largest block.
+	 * linear search of the variable sized freelist; look for an exact
+	 * match or the largest block.
 	 */
 	for_each_chain_block(0, prev, curr, next) {
 		size = chain_block_size(curr);
kernel/locking/lockdep_internals.h +1 -0
@@ -141,6 +141,7 @@ extern unsigned int nr_hardirq_chains;
 extern unsigned int nr_softirq_chains;
 extern unsigned int nr_process_chains;
 extern unsigned int nr_free_chain_hlocks;
+extern unsigned int nr_lost_chain_hlocks;
 extern unsigned int nr_large_chain_blocks;
 
 extern unsigned int max_lockdep_depth;
kernel/locking/lockdep_proc.c +4 -2
@@ -278,9 +278,11 @@ static int lockdep_stats_show(struct seq
 #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:       %11lu [max: %lu]\n",
-			MAX_LOCKDEP_CHAIN_HLOCKS - nr_free_chain_hlocks,
+	seq_printf(m, " dependency chain hlocks used:  %11lu [max: %lu]\n",
+			MAX_LOCKDEP_CHAIN_HLOCKS - (nr_free_chain_hlocks - nr_lost_chain_hlocks),
 			MAX_LOCKDEP_CHAIN_HLOCKS);
+	seq_printf(m, " dependency chain hlocks free:  %11lu\n", nr_free_chain_hlocks);
+	seq_printf(m, " dependency chain hlocks lost:  %11lu\n", nr_lost_chain_hlocks);
 #endif
 
 #ifdef CONFIG_TRACE_IRQFLAGS
author reviewer
#8 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 65 lines · Peter Zijlstra

Review

Quoted 2 lines · Waiman Long
(quoted diff) +2 -0
+	if (unlikely(size < 2))
+		return; // XXX leak!

Stuck this on top...

kernel/locking/lockdep.c +15 -5
@@ -2631,7 +2631,8 @@ struct lock_chain lock_chains[MAX_LOCKDE
 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_free_chain_hlocks;	/* Free cfhain_hlocks in buckets */
+unsigned int nr_free_chain_hlocks;	/* Free chain_hlocks in buckets */
+unsigned int nr_lost_chain_hlocks;	/* Lost chain_hlocks */
 unsigned int nr_large_chain_blocks;	/* size > MAX_CHAIN_BUCKETS */
 
 /*
@@ -2718,8 +2719,17 @@ static inline void add_chain_block(int o
 	int bucket = size_to_bucket(size);
 	int next = chain_block_buckets[bucket];
 
-	if (unlikely(size < 2))
-		return; // XXX leak!
+	if (unlikely(size < 2)) {
+		/*
+		 * We can't store single entries on the freelist. Leak them.
+		 *
+		 * One possible way out would be to uniquely mark them, other
+		 * than with CHAIN_BLK_FLAG, such that we can recover them when
+		 * the block before it is re-added.
+		 */
+		nr_lost_chain_hlocks++;
+		return;
+	}
 
 	init_chain_block(offset, next, bucket, size);
 	chain_block_buckets[bucket] = offset;
@@ -2798,8 +2808,8 @@ static int alloc_chain_hlocks(int req)
 
 search:
 	/*
-	 * linear search in the 'dump' bucket; look for an exact match or the
-	 * largest block.
+	 * linear search of the variable sized freelist; look for an exact
+	 * match or the largest block.
 	 */
 	for_each_chain_block(0, prev, curr, next) {
 		size = chain_block_size(curr);
kernel/locking/lockdep_internals.h +1 -0
@@ -141,6 +141,7 @@ extern unsigned int nr_hardirq_chains;
 extern unsigned int nr_softirq_chains;
 extern unsigned int nr_process_chains;
 extern unsigned int nr_free_chain_hlocks;
+extern unsigned int nr_lost_chain_hlocks;
 extern unsigned int nr_large_chain_blocks;
 
 extern unsigned int max_lockdep_depth;
kernel/locking/lockdep_proc.c +0 -0
@@ -278,9 +278,11 @@ static int lockdep_stats_show(struct seq
 #ifdef CONFIG_PROVE_LOCKING
 	seq_printf(m, " dependency chains:             %11lu [max: %lu]\n",
 			lock_chain_count(), MAX_LOCKDEP_CHAINS);

kernel/locking/lockdep_proc.c static int lockdep_stats_show(struct seq · line 288

Quoted 10 lines
kernel/locking/lockdep_proc.c +4 -2
-	seq_printf(m, " dependency chain hlocks:       %11lu [max: %lu]\n",
-			MAX_LOCKDEP_CHAIN_HLOCKS - nr_free_chain_hlocks,
+	seq_printf(m, " dependency chain hlocks used:  %11lu [max: %lu]\n",
+			MAX_LOCKDEP_CHAIN_HLOCKS - (nr_free_chain_hlocks - nr_lost_chain_hlocks),
 			MAX_LOCKDEP_CHAIN_HLOCKS);
+	seq_printf(m, " dependency chain hlocks free:  %11lu\n", nr_free_chain_hlocks);
+	seq_printf(m, " dependency chain hlocks lost:  %11lu\n", nr_lost_chain_hlocks);
 #endif
 
 #ifdef CONFIG_TRACE_IRQFLAGS

Sure. Will do that.

Thanks for the suggestion.

Cheers,
Longman

author reviewer
#9 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

In reply to Peter Zijlstra

kernel/locking/lockdep_proc.c static int lockdep_stats_show(struct seq · line 285

Quoted 13 lines · Peter Zijlstra
kernel/locking/lockdep_proc.c +4 -2
@@ -278,9 +278,11 @@ static int lockdep_stats_show(struct seq
 #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:       %11lu [max: %lu]\n",
-			MAX_LOCKDEP_CHAIN_HLOCKS - nr_free_chain_hlocks,
+	seq_printf(m, " dependency chain hlocks used:  %11lu [max: %lu]\n",
+			MAX_LOCKDEP_CHAIN_HLOCKS - (nr_free_chain_hlocks - nr_lost_chain_hlocks),
 			MAX_LOCKDEP_CHAIN_HLOCKS);
+	seq_printf(m, " dependency chain hlocks free:  %11lu\n", nr_free_chain_hlocks);
+	seq_printf(m, " dependency chain hlocks lost:  %11lu\n", nr_lost_chain_hlocks);

I do have some comments on this. There are three buckets now - free, lost, used. They add up to MAX_LOCKDEP_CHAIN_HLOCKS. I don't think we need to list all three. We can compute the third one by subtracting max from the other two.

Something like:

kernel/locking/lockdep_proc.c +0 -0
index 14932ea50317..6fe6a21c58d3 100644
@@ -278,9 +278,12 @@ 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:       %11lu [max: %lu]\n", -                       MAX_LOCKDEP_CHAIN_HLOCKS - nr_free_chain_hlocks, +       seq_printf(m, " dependency chain hlocks used:  %11lu [max: %lu]\n", +                       MAX_LOCKDEP_CHAIN_HLOCKS -
+                       (nr_free_chain_hlocks + nr_lost_chain_hlocks), MAX_LOCKDEP_CHAIN_HLOCKS);
+       seq_printf(m, " dependency chain hlocks lost:  %11lu\n", +                       nr_lost_chain_hlocks);
 #endif

 #ifdef CONFIG_TRACE_IRQFLAGS

Cheers,
Longman

maintainer
#10 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 40 lines · Waiman Long

kernel/locking/lockdep_proc.c static int lockdep_stats_show(struct seq · line 285

Quoted 13 lines · Peter Zijlstra
kernel/locking/lockdep_proc.c +4 -2
@@ -278,9 +278,11 @@ static int lockdep_stats_show(struct seq
 #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:       %11lu [max: %lu]\n",
-			MAX_LOCKDEP_CHAIN_HLOCKS - nr_free_chain_hlocks,
+	seq_printf(m, " dependency chain hlocks used:  %11lu [max: %lu]\n",
+			MAX_LOCKDEP_CHAIN_HLOCKS - (nr_free_chain_hlocks - nr_lost_chain_hlocks),
 			MAX_LOCKDEP_CHAIN_HLOCKS);
+	seq_printf(m, " dependency chain hlocks free:  %11lu\n", nr_free_chain_hlocks);
+	seq_printf(m, " dependency chain hlocks lost:  %11lu\n", nr_lost_chain_hlocks);

I do have some comments on this. There are three buckets now - free, lost, used. They add up to MAX_LOCKDEP_CHAIN_HLOCKS. I don't think we need to list all three. We can compute the third one by subtracting max from the other two.

Something like:

kernel/locking/lockdep_proc.c +5 -2
index 14932ea50317..6fe6a21c58d3 100644
@@ -278,9 +278,12 @@ 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:       %11lu [max: %lu]\n",
-                       MAX_LOCKDEP_CHAIN_HLOCKS - nr_free_chain_hlocks,
+       seq_printf(m, " dependency chain hlocks used:  %11lu [max: %lu]\n",
+                       MAX_LOCKDEP_CHAIN_HLOCKS -
+                       (nr_free_chain_hlocks + nr_lost_chain_hlocks),
                         MAX_LOCKDEP_CHAIN_HLOCKS);
+       seq_printf(m, " dependency chain hlocks lost:  %11lu\n",
+                       nr_lost_chain_hlocks);
  #endif
Quoted 1 line

Sure, also I tihnk the compiler is unhappy about %lu vs 'unsigned int' for some of them.

author reviewer
#11 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 35 lines · Peter Zijlstra
Quoted 34 lines · Waiman Long

kernel/locking/lockdep_proc.c static int lockdep_stats_show(struct seq · line 285

Quoted 13 lines · Peter Zijlstra
kernel/locking/lockdep_proc.c +4 -2
@@ -278,9 +278,11 @@ static int lockdep_stats_show(struct seq
 #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:       %11lu [max: %lu]\n",
-			MAX_LOCKDEP_CHAIN_HLOCKS - nr_free_chain_hlocks,
+	seq_printf(m, " dependency chain hlocks used:  %11lu [max: %lu]\n",
+			MAX_LOCKDEP_CHAIN_HLOCKS - (nr_free_chain_hlocks - nr_lost_chain_hlocks),
 			MAX_LOCKDEP_CHAIN_HLOCKS);
+	seq_printf(m, " dependency chain hlocks free:  %11lu\n", nr_free_chain_hlocks);
+	seq_printf(m, " dependency chain hlocks lost:  %11lu\n", nr_lost_chain_hlocks);

I do have some comments on this. There are three buckets now - free, lost, used. They add up to MAX_LOCKDEP_CHAIN_HLOCKS. I don't think we need to list all three. We can compute the third one by subtracting max from the other two.

Something like:

kernel/locking/lockdep_proc.c +2 -2
index 14932ea50317..6fe6a21c58d3 100644
@@ -278,9 +278,12 @@ 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:       %11lu [max: %lu]\n",
-                       MAX_LOCKDEP_CHAIN_HLOCKS - nr_free_chain_hlocks,
+       seq_printf(m, " dependency chain hlocks used:  %11lu [max: %lu]\n",
+                       MAX_LOCKDEP_CHAIN_HLOCKS -
Quoted 9 lines
Quoted 6 lines
kernel/locking/lockdep_proc.c +3 -0
+                       (nr_free_chain_hlocks + nr_lost_chain_hlocks),
                         MAX_LOCKDEP_CHAIN_HLOCKS);
+       seq_printf(m, " dependency chain hlocks lost:  %11lu\n",
+                       nr_lost_chain_hlocks);
  #endif

Sure, also I tihnk the compiler is unhappy about %lu vs 'unsigned int' for some of them.

Yes, I found that after I compiled the code :-)

Cheers,
Longman

maintainer
#12 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

In reply to Waiman Long

Review

Quoted 5 lines · Waiman Long
(quoted diff) +5 -0
+	/*
+	 * We require a minimum of 2 (u16) entries to encode a freelist
+	 * 'pointer'.
+	 */
+	req = max(req, 2);

Would something simple like the below not avoid that whole 1 entry 'chain' nonsense?

It boots and passes the selftests, so it must be perfect :-)

kernel/locking/lockdep.c +1 -1
@@ -3163,7 +3163,7 @@ static int validate_chain(struct task_st
 	 * (If lookup_chain_cache_add() return with 1 it acquires
 	 * graph_lock for us)
 	 */
-	if (!hlock->trylock && hlock->check &&
+	if (!chain_head && !hlock->trylock && hlock->check &&
 	    lookup_chain_cache_add(curr, hlock, chain_key)) {
 		/*
 		 * Check whether last held lock:
author reviewer
#13 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 16 lines · Peter Zijlstra

Review

Quoted 5 lines · Waiman Long
(quoted diff) +5 -0
+	/*
+	 * We require a minimum of 2 (u16) entries to encode a freelist
+	 * 'pointer'.
+	 */
+	req = max(req, 2);

Would something simple like the below not avoid that whole 1 entry 'chain' nonsense?

It boots and passes the selftests, so it must be perfect :-)

kernel/locking/lockdep.c static int validate_chain(struct task_st · line 3169

Quoted 8 lines
kernel/locking/lockdep.c +1 -1
@@ -3163,7 +3163,7 @@ static int validate_chain(struct task_st
 	 * (If lookup_chain_cache_add() return with 1 it acquires
 	 * graph_lock for us)
 	 */
-	if (!hlock->trylock && hlock->check &&
+	if (!chain_head && !hlock->trylock && hlock->check &&
 	    lookup_chain_cache_add(curr, hlock, chain_key)) {
 		/*
 		 * Check whether last held lock:

Well, I think that will eliminate the 1-entry chains for the process context. However, we can still have 1-entry chain in the irq context, I think, as long as there are process context locks in front of it.

I think this fix is still worthwhile as it will eliminate some of the 1-entry chains.

Cheers,
Longman

author reviewer
#14 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 28 lines · Waiman Long
Quoted 15 lines · Peter Zijlstra

Review

Quoted 5 lines · Waiman Long
(quoted diff) +5 -0
+	/*
+	 * We require a minimum of 2 (u16) entries to encode a freelist
+	 * 'pointer'.
+	 */
+	req = max(req, 2);

Would something simple like the below not avoid that whole 1 entry 'chain' nonsense?

It boots and passes the selftests, so it must be perfect :-)

kernel/locking/lockdep.c static int validate_chain(struct task_st · line 3169

Quoted 8 lines
kernel/locking/lockdep.c +1 -1
@@ -3163,7 +3163,7 @@ static int validate_chain(struct task_st
 	 * (If lookup_chain_cache_add() return with 1 it acquires
 	 * graph_lock for us)
 	 */
-	if (!hlock->trylock && hlock->check &&
+	if (!chain_head && !hlock->trylock && hlock->check &&
 	    lookup_chain_cache_add(curr, hlock, chain_key)) {
 		/*
 		 * Check whether last held lock:

Well, I think that will eliminate the 1-entry chains for the process context. However, we can still have 1-entry chain in the irq context, I think, as long as there are process context locks in front of it.

Quoted 2 lines

I think this fix is still worthwhile as it will eliminate some of the 1-entry chains.

Sorry, I think I mis-read the code. This patch will eliminate some cross-context check. How  about something like

kernel/locking/lockdep.c +0 -0
index 32406ef0d6a2..d746897b638f 100644
@@ -2931,7 +2931,7 @@ static int validate_chain(struct task_struct *curr,

         * (If lookup_chain_cache_add() return with 1 it acquires
         * graph_lock for us)
         */
-       if (!hlock->trylock && hlock->check &&
+       if ((chain_head != 1) && !hlock->trylock && hlock->check && lookup_chain_cache_add(curr, hlock, chain_key)) { /*
                 * Check whether last held lock:
@@ -3937,7 +3937,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsign
        hlock->prev_chain_key = chain_key;
        if (separate_irq_context(curr, hlock)) { chain_key = INITIAL_CHAIN_KEY;
-               chain_head = 1;
+               chain_head = 2; /* Head of irq context chain */ }
        chain_key = iterate_chain_key(chain_key, class_idx);
Cheers,
Longman

author reviewer
#15 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 48 lines · Waiman Long
Quoted 28 lines · Waiman Long
Quoted 15 lines · Peter Zijlstra

Review

Quoted 5 lines · Waiman Long
(quoted diff) +5 -0
+	/*
+	 * We require a minimum of 2 (u16) entries to encode a freelist
+	 * 'pointer'.
+	 */
+	req = max(req, 2);

Would something simple like the below not avoid that whole 1 entry 'chain' nonsense?

It boots and passes the selftests, so it must be perfect :-)

kernel/locking/lockdep.c static int validate_chain(struct task_st · line 3169

Quoted 8 lines
kernel/locking/lockdep.c +1 -1
@@ -3163,7 +3163,7 @@ static int validate_chain(struct task_st
 	 * (If lookup_chain_cache_add() return with 1 it acquires
 	 * graph_lock for us)
 	 */
-	if (!hlock->trylock && hlock->check &&
+	if (!chain_head && !hlock->trylock && hlock->check &&
 	    lookup_chain_cache_add(curr, hlock, chain_key)) {
 		/*
 		 * Check whether last held lock:

Well, I think that will eliminate the 1-entry chains for the process context. However, we can still have 1-entry chain in the irq context, I think, as long as there are process context locks in front of it.

Quoted 2 lines

I think this fix is still worthwhile as it will eliminate some of the 1-entry chains.

Sorry, I think I mis-read the code. This patch will eliminate some cross-context check. How  about something like

kernel/locking/lockdep.c +1 -1
index 32406ef0d6a2..d746897b638f 100644
@@ -2931,7 +2931,7 @@ static int validate_chain(struct task_struct *curr,
          * (If lookup_chain_cache_add() return with 1 it acquires
          * graph_lock for us)
          */
-       if (!hlock->trylock && hlock->check &&
+       if ((chain_head != 1) && !hlock->trylock && hlock->check &&
             lookup_chain_cache_add(curr, hlock, chain_key)) {
                 /*
                  * Check whether last held lock:

kernel/locking/lockdep.c static int __lock_acquire(struct lockdep_map · line 3943

Quoted 8 lines
kernel/locking/lockdep.c +1 -1
@@ -3937,7 +3937,7 @@ static int __lock_acquire(struct lockdep_map
 *lock, unsign
         hlock->prev_chain_key = chain_key;
         if (separate_irq_context(curr, hlock)) {
                 chain_key = INITIAL_CHAIN_KEY;
-               chain_head = 1;
+               chain_head = 2; /* Head of irq context chain */
         }
         chain_key = iterate_chain_key(chain_key, class_idx);

Wait, it is possible that we can have deadlock like this:

  cpu 0               cpu 1
  -----               -----
  lock A              lock B
  <irq>               <irq>
  lock B              lock A

If we eliminate 1-entry chain, will that impact our ability to detect this kind of deadlock?

Thanks,
Longman

maintainer
#16 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 10 lines · Waiman Long

Wait, it is possible that we can have deadlock like this:

  cpu 0               cpu 1
  -----               -----
  lock A              lock B
  <irq>               <irq>
  lock B              lock A

If we eliminate 1-entry chain, will that impact our ability to detect this kind of deadlock?

I'm thinking that should trigger irq-inversion (irq-on vs in-irq) on either A or B (depending on timing).

AFAICT the irq-state tracking is outside of validate_chain().

This is also why I think your separate_irq_context() change is not needed.

validate_chain() really only checks the per-context lock nesting, and there, a single lock doesn't do very much. Hence my proposed patch.

author reviewer
#17 lore raw

Re: [PATCH v5 6/7] locking/lockdep: Reuse freed chain_hlocks entries

Quoted 15 lines · Peter Zijlstra
Quoted 10 lines · Waiman Long

Wait, it is possible that we can have deadlock like this:

  cpu 0               cpu 1
  -----               -----
  lock A              lock B
  <irq>               <irq>
  lock B              lock A

If we eliminate 1-entry chain, will that impact our ability to detect this kind of deadlock?

I'm thinking that should trigger irq-inversion (irq-on vs in-irq) on either A or B (depending on timing).

Quoted 8 lines

AFAICT the irq-state tracking is outside of validate_chain().

This is also why I think your separate_irq_context() change is not needed.

validate_chain() really only checks the per-context lock nesting, and there, a single lock doesn't do very much. Hence my proposed patch.

I see. Then it may be OK. I will take a further look just to be sure.

Cheers,
Longman

author reviewer
#18 lore raw

PATCH v5 7/7 locking/lockdep: Add a fast path for chain_hlocks allocation

In reply to Waiman Long

When alloc_chain_hlocks() is called, the most likely scenario is to allocate from the primordial chain block which holds the whole chain_hlocks[] array initially. It is the primordial chain block if its size is bigger than MAX_LOCK_DEPTH. As long as the number of entries left after splitting is still bigger than MAX_CHAIN_BUCKETS it will remain in bucket 0. By splitting out a sub-block at the end, we only need to adjust the size without changing any of the existing linkage information. This optimized fast path can reduce the latency of allocation requests.

This patch does change the order by which chain_hlocks entries are allocated. The original code allocates entries from the beginning of the array. Now it will be allocated from the end of the array backward.

---
 kernel/locking/lockdep.c | 24 ++++++++++++++++++++----
 1 file changed, 20 insertions(+), 4 deletions(-)
kernel/locking/lockdep.c +20 -4
index 70288bb2331d..d05799872882 100644
@@ -2701,15 +2701,19 @@ static inline int chain_block_size(int offset)
 	return (chain_hlocks[offset + 2] << 16) | chain_hlocks[offset + 3];
 }
 
+static inline void init_chain_block_size(int offset, int size)
+{
+	chain_hlocks[offset + 2] = size >> 16;
+	chain_hlocks[offset + 3] = (u16)size;
+}
+
 static inline void init_chain_block(int offset, int next, int bucket, int size)
 {
 	chain_hlocks[offset] = (next >> 16) | CHAIN_BLK_FLAG;
 	chain_hlocks[offset + 1] = (u16)next;
 
-	if (bucket == 0) {
-		chain_hlocks[offset + 2] = size >> 16;
-		chain_hlocks[offset + 3] = (u16)size;
-	}
+	if (bucket == 0)
+		init_chain_block_size(offset, size);
 }
 
 static inline void add_chain_block(int offset, int size)
@@ -2809,6 +2813,18 @@ static int alloc_chain_hlocks(int req)
 			return curr;
 		}
 
+		/*
+		 * Fast path: splitting out a sub-block at the end of the
+		 * primordial chain block.
+		 */
+		if (likely((size > MAX_LOCK_DEPTH) &&
+			   (size - req > MAX_CHAIN_BUCKETS))) {
+			size -= req;
+			nr_free_chain_hlocks -= req;
+			init_chain_block_size(curr, size);
+			return curr + size;
+		}
+
 		if (size > max_size) {
 			max_prev = prev;
 			max_curr = curr;
Signature · 1 line
2.18.1
maintainer
#19 lore raw

Re: [PATCH v5 7/7] locking/lockdep: Add a fast path for chain_hlocks allocation

Quoted 9 lines · Waiman Long

When alloc_chain_hlocks() is called, the most likely scenario is to allocate from the primordial chain block which holds the whole chain_hlocks[] array initially. It is the primordial chain block if its size is bigger than MAX_LOCK_DEPTH. As long as the number of entries left after splitting is still bigger than MAX_CHAIN_BUCKETS it will remain in bucket 0. By splitting out a sub-block at the end, we only need to adjust the size without changing any of the existing linkage information. This optimized fast path can reduce the latency of allocation requests.

Quoted 3 lines

This patch does change the order by which chain_hlocks entries are allocated. The original code allocates entries from the beginning of the array. Now it will be allocated from the end of the array backward.

Cute; but why do we care? Is there any measurable performance indicator?

author reviewer
#20 lore raw

Re: [PATCH v5 7/7] locking/lockdep: Add a fast path for chain_hlocks allocation

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

When alloc_chain_hlocks() is called, the most likely scenario is to allocate from the primordial chain block which holds the whole chain_hlocks[] array initially. It is the primordial chain block if its size is bigger than MAX_LOCK_DEPTH. As long as the number of entries left after splitting is still bigger than MAX_CHAIN_BUCKETS it will remain in bucket 0. By splitting out a sub-block at the end, we only need to adjust the size without changing any of the existing linkage information. This optimized fast path can reduce the latency of allocation requests.

Quoted 5 lines
Quoted 3 lines

This patch does change the order by which chain_hlocks entries are allocated. The original code allocates entries from the beginning of the array. Now it will be allocated from the end of the array backward.

Cute; but why do we care? Is there any measurable performance indicator?

I used parallel kernel compilation test to see if there is a performance benefit. I did see the compile time get reduced by a few seconds out of several minutes of total time on average. So it is only about 1% or so. I didn't mention it as it is within the margin of error.

One of the goals of this patchset is to make sure that little or no performance regression is introduced. That was why I was hesitant to adopt the single allocator approach as suggested. That is also why I add this patch to try to get some performance back.

Cheers,
Longman

maintainer
#21 lore raw

Re: [PATCH v5 7/7] locking/lockdep: Add a fast path for chain_hlocks allocation

In reply to Waiman Long
Quoted 9 lines · Waiman Long
kernel/locking/lockdep.c +5 -0
@@ -2809,6 +2813,18 @@ static int alloc_chain_hlocks(int req)
 			return curr;
 		}
 
+		/*
+		 * Fast path: splitting out a sub-block at the end of the
+		 * primordial chain block.
+		 */
+		if (likely((size > MAX_LOCK_DEPTH) &&

kernel/locking/lockdep.c static int alloc_chain_hlocks(int req) · line 2830

Quoted 10 lines
kernel/locking/lockdep.c +7 -0
+			   (size - req > MAX_CHAIN_BUCKETS))) {
+			size -= req;
+			nr_free_chain_hlocks -= req;
+			init_chain_block_size(curr, size);
+			return curr + size;
+		}
+
 		if (size > max_size) {
 			max_prev = prev;
 			max_curr = curr;

A less horrible hack might be to keep the freelist sorted on size (large -> small)

That moves the linear-search from alloc_chain_hlocks() into add_chain_block(). But the thing is that it would amortize to O(1) because this initial chunk is pretty much 'always' the largest.

Only once we've exhausted the initial block will we hit that search, but then the hope is that we mostly live off of the buckets, not the variable freelist.

maintainer
#22 lore raw

Re: [PATCH v5 7/7] locking/lockdep: Add a fast path for chain_hlocks allocation

Quoted 25 lines · Peter Zijlstra
Quoted 9 lines · Waiman Long
(quoted diff) +5 -0
@@ -2809,6 +2813,18 @@ static int alloc_chain_hlocks(int req)
 			return curr;
 		}
 
+		/*
+		 * Fast path: splitting out a sub-block at the end of the
+		 * primordial chain block.
+		 */
+		if (likely((size > MAX_LOCK_DEPTH) &&

Review static int alloc_chain_hlocks(int req) · line 2830

Quoted 10 lines
(quoted diff) +7 -0
+			   (size - req > MAX_CHAIN_BUCKETS))) {
+			size -= req;
+			nr_free_chain_hlocks -= req;
+			init_chain_block_size(curr, size);
+			return curr + size;
+		}
+
 		if (size > max_size) {
 			max_prev = prev;
 			max_curr = curr;

A less horrible hack might be to keep the freelist sorted on size (large -> small)

Quoted 7 lines

That moves the linear-search from alloc_chain_hlocks() into add_chain_block(). But the thing is that it would amortize to O(1) because this initial chunk is pretty much 'always' the largest.

Only once we've exhausted the initial block will we hit that search, but then the hope is that we mostly live off of the buckets, not the variable freelist.

Completely untested something like so

---

kernel/locking/lockdep.c +38 -45
@@ -2717,7 +2717,7 @@ static inline void init_chain_block(int
 static inline void add_chain_block(int offset, int size)
 {
 	int bucket = size_to_bucket(size);
-	int next = chain_block_buckets[bucket];
+	int prev, curr, next = chain_block_buckets[bucket];
 
 	if (unlikely(size < 2)) {
 		/*
@@ -2731,26 +2731,38 @@ static inline void add_chain_block(int o
 		return;
 	}
 
-	init_chain_block(offset, next, bucket, size);
-	chain_block_buckets[bucket] = offset;
-	nr_free_chain_hlocks += size;
-
-	if (bucket == 0)
+	if (!bucket) {
 		nr_large_chain_blocks++;
+		/*
+		 * Variable sized, sort large to small.
+		 */
+		for_each_chain_block(0, prev, curr, next) {
+			if (size > chain_block_size(curr))
+				break;
+		}
+		init_chain_block(offset, curr, 0, size);
+		if (prev < 0)
+			chain_block_buckets[prev + MAX_CHAIN_BUCKETS] = offset;
+		else
+			init_chain_block(prev, offset, MAX_CHAIN_BUCKETS, 0);
+	} else {
+		/*
+		 * Fixed size, add to head.
+		 */
+		init_chain_block(offset, next, bucket, size);
+		chain_block_buckets[bucket] = offset;
+	}
+	nr_free_chain_hlocks += size;
 }
 
+
 /*
  * When offset < 0, the bucket number is encoded in it.
  */
-static inline void del_chain_block(int offset, int size, int next)
+static inline void del_chain_block(int bucket, int size, int next)
 {
-	int bucket = size_to_bucket(size);
-
 	nr_free_chain_hlocks -= size;
-	if (offset < 0)
-		chain_block_buckets[offset + MAX_CHAIN_BUCKETS] = next;
-	else
-		init_chain_block(offset, next, bucket, size);
+	chain_block_buckets[bucket] = next;
 
 	if (bucket == 0)
 		nr_large_chain_blocks--;
@@ -2774,9 +2786,7 @@ static void init_chain_block_buckets(voi
  */
 static int alloc_chain_hlocks(int req)
 {
-	int max_prev, max_curr, max_next, max_size = INT_MIN;
-	int prev, curr, next, size;
-	int bucket;
+	int bucket, curr, size;
 
 	/*
 	 * We rely on the MSB to act as an escape bit to denote freelist
@@ -2798,40 +2808,24 @@ static int alloc_chain_hlocks(int req)
 
 	if (bucket != 0) {
 		curr = chain_block_buckets[bucket];
-		if (curr < 0)
-			goto search;
-
-		del_chain_block(bucket - MAX_CHAIN_BUCKETS, req,
-				chain_block_next(curr));
-		return curr;
+		if (curr >= 0) {
+			del_chain_block(bucket, req, chain_block_next(curr));
+			return curr;
+		}
 	}
 
-search:
 	/*
-	 * linear search of the variable sized freelist; look for an exact
-	 * match or the largest block.
+	 * The variable sized freelist is sorted by size; the first entry is
+	 * the largest. Use it if it fits.
 	 */
-	for_each_chain_block(0, prev, curr, next) {
+	curr = chain_block_buckets[0];
+	if (curr >= 0) {
 		size = chain_block_size(curr);
-		next = chain_block_next(curr);
-
-		if (size == req) {
-			del_chain_block(prev, req, next);
+		if (likely(size > req)) {
+			del_chain_block(0, size, chain_block_next(curr));
+			add_chain_block(curr + req, size - req);
 			return curr;
 		}
-
-		if (size > max_size) {
-			max_prev = prev;
-			max_curr = curr;
-			max_next = next;
-			max_size = size;
-		}
-	}
-
-	if (likely(max_size > req)) {
-		del_chain_block(max_prev, max_size, max_next);
-		add_chain_block(max_curr + req, max_size - req);
-		return max_curr;
 	}
 
 	/*
@@ -2843,8 +2837,7 @@ static int alloc_chain_hlocks(int req)
 		if (curr < 0)
 			continue;
 
-		del_chain_block(bucket - MAX_CHAIN_BUCKETS, size,
-				chain_block_next(curr));
+		del_chain_block(bucket, size, chain_block_next(curr));
 		add_chain_block(curr + req, size - req);
 		return curr;
 	}
author reviewer
#23 lore raw

Re: [PATCH v5 7/7] locking/lockdep: Add a fast path for chain_hlocks allocation

Quoted 25 lines · Peter Zijlstra
Quoted 24 lines · Peter Zijlstra
Quoted 9 lines · Waiman Long
(quoted diff) +5 -0
@@ -2809,6 +2813,18 @@ static int alloc_chain_hlocks(int req)
 			return curr;
 		}
 
+		/*
+		 * Fast path: splitting out a sub-block at the end of the
+		 * primordial chain block.
+		 */
+		if (likely((size > MAX_LOCK_DEPTH) &&

Review static int alloc_chain_hlocks(int req) · line 2830

Quoted 10 lines
(quoted diff) +7 -0
+			   (size - req > MAX_CHAIN_BUCKETS))) {
+			size -= req;
+			nr_free_chain_hlocks -= req;
+			init_chain_block_size(curr, size);
+			return curr + size;
+		}
+
 		if (size > max_size) {
 			max_prev = prev;
 			max_curr = curr;

A less horrible hack might be to keep the freelist sorted on size (large -> small)

Quoted 8 lines
Quoted 7 lines

That moves the linear-search from alloc_chain_hlocks() into add_chain_block(). But the thing is that it would amortize to O(1) because this initial chunk is pretty much 'always' the largest.

Only once we've exhausted the initial block will we hit that search, but then the hope is that we mostly live off of the buckets, not the variable freelist.

Completely untested something like so

I will integrate that into patch 6. I won't push for this patch for now. It can be for a later discussion.

Thanks,
Longman