[PATCH v2 0/6] locking/lockdep: Reuse zapped chain_hlocks entries

[PATCH v2 0/6] locking/lockdep: Reuse zapped chain_hlocks entries

[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

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

-- 
2.18.1

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

[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.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/locking/lockdep.c           | 2 ++
 kernel/locking/lockdep_internals.h | 1 +
 kernel/locking/lockdep_proc.c      | 9 +++++++++
 3 files changed, 12 insertions(+)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 32282e7112d3..c8d0374101b0 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -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)
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 18d85aebbb57..a31d16fd3c43 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -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);
diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
index dadb7b7fba37..d98d349bb648 100644
--- a/kernel/locking/lockdep_proc.c
+++ b/kernel/locking/lockdep_proc.c
@@ -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;
 }
 
-- 
2.18.1

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

[Peter Zijlstra]

On Mon, Dec 16, 2019 at 10:15:12AM -0500, Waiman Long wrote:
> 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.
> 

> diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
> index dadb7b7fba37..d98d349bb648 100644
> --- a/kernel/locking/lockdep_proc.c
> +++ b/kernel/locking/lockdep_proc.c
> @@ -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;
>  }

Why is that conditional?

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

[Waiman Long]

On 1/13/20 9:55 AM, Peter Zijlstra wrote:
> On Mon, Dec 16, 2019 at 10:15:12AM -0500, Waiman Long wrote:
>> 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.
>>
>> diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
>> index dadb7b7fba37..d98d349bb648 100644
>> --- a/kernel/locking/lockdep_proc.c
>> +++ b/kernel/locking/lockdep_proc.c
>> @@ -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;
>>  }
> 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

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

[Bart Van Assche]

On 1/13/20 6:58 AM, Waiman Long wrote:
> On 1/13/20 9:55 AM, Peter Zijlstra wrote:
>> On Mon, Dec 16, 2019 at 10:15:12AM -0500, Waiman Long wrote:
>>> 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.
>>>
>>> diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
>>> index dadb7b7fba37..d98d349bb648 100644
>>> --- a/kernel/locking/lockdep_proc.c
>>> +++ b/kernel/locking/lockdep_proc.c
>>> @@ -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;
>>>   }
>> 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.

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.

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

[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.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/locking/lockdep.c           | 36 ++++--------------------------
 kernel/locking/lockdep_internals.h |  4 ++--
 kernel/locking/lockdep_proc.c      |  2 +-
 3 files changed, 7 insertions(+), 35 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index c8d0374101b0..30ebfe4978d5 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -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
 }
 
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index a31d16fd3c43..5dec0fe12507 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -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
diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
index d98d349bb648..4c7dc0a8935d 100644
--- a/kernel/locking/lockdep_proc.c
+++ b/kernel/locking/lockdep_proc.c
@@ -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
 
-- 
2.18.1

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

[Peter Zijlstra]

On Mon, Dec 16, 2019 at 10:15:13AM -0500, Waiman Long wrote:
> 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.

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

[Waiman Long]

On 1/13/20 10:18 AM, Peter Zijlstra wrote:
> On Mon, Dec 16, 2019 at 10:15:13AM -0500, Waiman Long wrote:
>> 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.
I will prefer having it only when it actually happens rather than
leaving a partial chain behind assuming that it may happen.
>
> 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

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

[Bart Van Assche]

On 1/13/20 7:18 AM, Peter Zijlstra wrote:
> On Mon, Dec 16, 2019 at 10:15:13AM -0500, Waiman Long wrote:
>> 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.

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.

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

[Waiman Long]

On 1/13/20 11:05 AM, Bart Van Assche wrote:
> On 1/13/20 7:18 AM, Peter Zijlstra wrote:
>> On Mon, Dec 16, 2019 at 10:15:13AM -0500, Waiman Long wrote:
>>> 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.
>
> 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

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

[Waiman Long]

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

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/locking/lockdep.c           | 2 ++
 kernel/locking/lockdep_internals.h | 1 +
 kernel/locking/lockdep_proc.c      | 2 ++
 3 files changed, 5 insertions(+)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 30ebfe4978d5..8293f7e80ee6 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -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
 }
 
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 5dec0fe12507..35758e469ff7 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -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);
diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
index 4c7dc0a8935d..7c15dd03cf49 100644
--- a/kernel/locking/lockdep_proc.c
+++ b/kernel/locking/lockdep_proc.c
@@ -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;
 }
 
-- 
2.18.1

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

[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.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/locking/lockdep.c           | 232 ++++++++++++++++++++++++++---
 kernel/locking/lockdep_internals.h |   2 +
 kernel/locking/lockdep_proc.c      |   4 +
 3 files changed, 219 insertions(+), 19 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 8293f7e80ee6..f7dcd4e77a70 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -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);
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 35758e469ff7..91bbc5684103 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -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;
diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
index 7c15dd03cf49..125c65e20bff 100644
--- a/kernel/locking/lockdep_proc.c
+++ b/kernel/locking/lockdep_proc.c
@@ -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;
 }
 
-- 
2.18.1

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

[Peter Zijlstra]

On Mon, Dec 16, 2019 at 10:15:15AM -0500, Waiman Long wrote:
> +#define CHAIN_HLOCKS_MASK	0xffff

> +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;
> +	}
> +}

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.

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

[Waiman Long]

On 1/13/20 10:51 AM, Peter Zijlstra wrote:
> On Mon, Dec 16, 2019 at 10:15:15AM -0500, Waiman Long wrote:
>> +#define CHAIN_HLOCKS_MASK	0xffff
>> +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;
>> +	}
>> +}
> 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.
>
Yes, I am aware that the macro may not be needed. Will make the changes
in the next version.

Thanks,
Longman

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

[Peter Zijlstra]

On Mon, Dec 16, 2019 at 10:15:15AM -0500, Waiman Long wrote:
> +/*
> + * 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;
> +		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?

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

[Waiman Long]

On 1/13/20 10:58 AM, Peter Zijlstra wrote:
> On Mon, Dec 16, 2019 at 10:15:15AM -0500, Waiman Long wrote:
>> +/*
>> + * 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;
>> +		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?
>
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

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

[Peter Zijlstra]

On Mon, Jan 13, 2020 at 11:24:37AM -0500, Waiman Long wrote:
> On 1/13/20 10:58 AM, Peter Zijlstra wrote:

> > 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.

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?

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

[Waiman Long]

On 1/14/20 4:46 AM, Peter Zijlstra wrote:
> On Mon, Jan 13, 2020 at 11:24:37AM -0500, Waiman Long wrote:
>> On 1/13/20 10:58 AM, Peter Zijlstra wrote:
>>> 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.
> 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.
>
> 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

>
> 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?
>

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

[Peter Zijlstra]

On Tue, Jan 14, 2020 at 02:16:58PM -0500, Waiman Long wrote:
> On 1/14/20 4:46 AM, Peter Zijlstra wrote:

> > 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.

> > 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.

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

[Waiman Long]

On 1/15/20 5:44 AM, Peter Zijlstra wrote:
> On Tue, Jan 14, 2020 at 02:16:58PM -0500, Waiman Long wrote:
>> On 1/14/20 4:46 AM, Peter Zijlstra wrote:
>>> 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.

>>> 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.
>
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

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

[Peter Zijlstra]

On Mon, Dec 16, 2019 at 10:15:15AM -0500, Waiman Long wrote:
> 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?

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

[Waiman Long]

On 1/13/20 10:59 AM, Peter Zijlstra wrote:
> On Mon, Dec 16, 2019 at 10:15:15AM -0500, Waiman Long wrote:
>> 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

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

[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")
Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/locking/lockdep.c           | 35 +++++++++++++++++++++---------
 kernel/locking/lockdep_internals.h |  6 +++++
 2 files changed, 31 insertions(+), 10 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index f7dcd4e77a70..4ea23bb6f8d3 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -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.
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 91bbc5684103..9425155b9053 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -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.
-- 
2.18.1

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

[Peter Zijlstra]

On Mon, Dec 16, 2019 at 10:15:16AM -0500, Waiman Long wrote:
> 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")
> Signed-off-by: Waiman Long <longman@redhat.com>

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

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

[Waiman Long]

On 1/14/20 4:53 AM, Peter Zijlstra wrote:
> On Mon, Dec 16, 2019 at 10:15:16AM -0500, Waiman Long wrote:
>> 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")
>> Signed-off-by: Waiman Long <longman@redhat.com>
> 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

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

[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.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/locking/lockdep_proc.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
index 125c65e20bff..7f08bb4e7037 100644
--- a/kernel/locking/lockdep_proc.c
+++ b/kernel/locking/lockdep_proc.c
@@ -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);
-- 
2.18.1

Re: [PATCH v2 0/6] locking/lockdep: Reuse zapped chain_hlocks entries

[Waiman Long]

On 12/16/19 10:15 AM, Waiman Long wrote:
>  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(-)
>
Ping! Any comments or suggestion for further improvement?

Cheers,
Longman

Re: [PATCH v2 0/6] locking/lockdep: Reuse zapped chain_hlocks entries

[Peter Zijlstra]

On Mon, Jan 06, 2020 at 10:54:24AM -0500, Waiman Long wrote:

> 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 :-)

Re: [PATCH v2 0/6] locking/lockdep: Reuse zapped chain_hlocks entries

[Waiman Long]

On 1/6/20 11:50 AM, Peter Zijlstra wrote:
> On Mon, Jan 06, 2020 at 10:54:24AM -0500, Waiman Long wrote:
>
>> 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