locking/lockdep: Reuse zapped chain_hlocks entries
Waiman Long
reviewerv2 cover locking/lockdep: Reuse zapped chain_hlocks entries
v2:
- Revamp the chain_hlocks reuse patch to store the freed chain_hlocks information in the chain_hlocks entries themselves avoiding the need of a separate set of tracking structures. This, however, requires a minimum allocation size of at least 2. Thanks to PeterZ for his review and inspiring this change.
- Remove the leakage counter as it is no longer applicable.
- Add patch 6 to make the output of /proc/lockdep_chains more readable.
It was found that when running a workload that kept on adding lock classes and then zapping them repetitively, the system will eventually run out of chain_hlocks[] entries even though there were still plenty of other lockdep data buffers available.
[ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! [ 4318.444809] turning off the locking correctness validator.
In order to fix this problem, we have to make chain_hlocks[] entries reusable just like other lockdep arrays. Besides that, the patchset also adds some zapped class and chain_hlocks counters to be tracked by /proc/lockdep_stats. It also fixes leakage in the irq context counters and makes the output of /proc/lockdep_chains more readable.
Waiman Long (6):
locking/lockdep: Track number of zapped classes locking/lockdep: Throw away all lock chains with zapped class locking/lockdep: Track number of zapped lock chains locking/lockdep: Reuse freed chain_hlocks entries locking/lockdep: Decrement irq context counters when removing lock
chain
locking/lockdep: Display irq_context names in /proc/lockdep_chains
kernel/locking/lockdep.c | 307 +++++++++++++++++++++++------ kernel/locking/lockdep_internals.h | 14 +- kernel/locking/lockdep_proc.c | 26 ++- 3 files changed, 282 insertions(+), 65 deletions(-)
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 1/6 locking/lockdep: Track number of zapped classes
The whole point of the lockdep dynamic key patch is to allow unused locks to be removed from the lockdep data buffers so that existing buffer space can be reused. However, there is no way to find out how many unused locks are zapped and so we don't know if the zapping process is working properly.
Add a new nr_zapped_classes variable to track that and show it in /proc/lockdep_stats if it is non-zero.
--- kernel/locking/lockdep.c | 2 ++ kernel/locking/lockdep_internals.h | 1 + kernel/locking/lockdep_proc.c | 9 +++++++++ 3 files changed, 12 insertions(+)
kernel/locking/lockdep.c +2 -0
@@ -147,6 +147,7 @@ static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);#define KEYHASH_SIZE (1UL << KEYHASH_BITS)static struct hlist_head lock_keys_hash[KEYHASH_SIZE ];unsigned long nr_lock_classes; +unsigned long nr_zapped_classes;#ifndef CONFIG_DEBUG_LOCKDEP static#endif
@@ -4875,6 +4876,7 @@ static void zap_class(struct pending_free *pf, struct lock_class *class) }remove_class_from_lock_chains (pf, class); + nr_zapped_classes++; }static void reinit_class (struct lock_class *class)
kernel/locking/lockdep_internals.h +1 -0
@@ -124,6 +124,7 @@ extern const char *__get_key_name(const struct lockdep_subclass_key *key,struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i);extern unsigned long nr_lock_classes; +extern unsigned long nr_zapped_classes;extern unsigned long nr_list_entries;long lockdep_next_lockchain (long i);unsigned long lock_chain_count (void );
kernel/locking/lockdep_proc.c +9 -0
@@ -336,6 +336,15 @@ static int lockdep_stats_show(struct seq_file *m, void *v)seq_printf (m," debug_locks: %11u\n" , debug_locks); +/* +* Zappped classes and lockdep data buffers reuse statistics. +*/ +if (!nr_zapped_classes) +return 0 ; + +seq_puts (m,"\n" ); +seq_printf (m," zapped classes: %11lu\n" , + nr_zapped_classes);return 0 ; }
Signature · 1 line
2.18.1
Peter Zijlstra
maintainerRe: [PATCH v2 1/6] locking/lockdep: Track number of zapped classes
Quoted 19 lines · Waiman Long
The whole point of the lockdep dynamic key patch is to allow unused locks to be removed from the lockdep data buffers so that existing buffer space can be reused. However, there is no way to find out how many unused locks are zapped and so we don't know if the zapping process is working properly.
Add a new
nr_zapped_classesvariable to track that and show it in/proc/lockdep_statsif it is non-zero.kernel/locking/lockdep_proc.c +1
-0@@ -336,6 +336,15 @@ static int lockdep_stats_show(struct seq_file *m, void *v)seq_printf (m," debug_locks: %11u\n" , debug_locks); +/*
kernel/locking/lockdep_proc.c static int lockdep_stats_show(struct seq_file *m, void *v) · line 349
Quoted 10 lines
kernel/locking/lockdep_proc.c +8
-0+* Zappped classes and lockdep data buffers reuse statistics. +*/ +if (!nr_zapped_classes) +return 0 ; + +seq_puts (m,"\n" ); +seq_printf (m," zapped classes: %11lu\n" , + nr_zapped_classes);return 0 ; }
Why is that conditional?
Waiman Long
reviewerRe: [PATCH v2 1/6] locking/lockdep: Track number of zapped classes
Quoted 18 lines · Peter Zijlstra
Quoted 17 lines · Waiman Long
The whole point of the lockdep dynamic key patch is to allow unused locks to be removed from the lockdep data buffers so that existing buffer space can be reused. However, there is no way to find out how many unused locks are zapped and so we don't know if the zapping process is working properly.
Add a new
nr_zapped_classesvariable to track that and show it in/proc/lockdep_statsif it is non-zero.kernel/locking/lockdep_proc.c +0
-0@@ -336,6 +336,15 @@ static int lockdep_stats_show(struct seq_file *m, void *v)seq_printf (m," debug_locks: %11u\n" , debug_locks);
Quoted 13 lines
kernel/locking/lockdep_proc.c static int lockdep_stats_show(struct seq_file *m, void *v) · line 349
Quoted 11 lines
kernel/locking/lockdep_proc.c +9
-0+/* +* Zappped classes and lockdep data buffers reuse statistics. +*/ +if (!nr_zapped_classes) +return 0 ; + +seq_puts (m,"\n" ); +seq_printf (m," zapped classes: %11lu\n" , + nr_zapped_classes);return 0 ; }Why is that conditional?
Because I thought zapping class doesn't occur that often. Apparently, class zapping happens when the system first boots up. I guess that conditional check isn't needed. I can remove it in the next version.
Cheers,
Longman
Re: [PATCH v2 1/6] locking/lockdep: Track number of zapped classes
Quoted 32 lines · Waiman Long
Quoted 18 lines · Peter Zijlstra
Quoted 17 lines · Waiman Long
The whole point of the lockdep dynamic key patch is to allow unused locks to be removed from the lockdep data buffers so that existing buffer space can be reused. However, there is no way to find out how many unused locks are zapped and so we don't know if the zapping process is working properly.
Add a new
nr_zapped_classesvariable to track that and show it in/proc/lockdep_statsif it is non-zero.kernel/locking/lockdep_proc.c +0
-0@@ -336,6 +336,15 @@ static int lockdep_stats_show(struct seq_file *m, void *v)seq_printf (m," debug_locks: %11u\n" , debug_locks);Quoted 13 lines
kernel/locking/lockdep_proc.c static int lockdep_stats_show(struct seq_file *m, void *v) · line 349
Quoted 11 lines
kernel/locking/lockdep_proc.c +9
-0+/* +* Zappped classes and lockdep data buffers reuse statistics. +*/ +if (!nr_zapped_classes) +return 0 ; + +seq_puts (m,"\n" ); +seq_printf (m," zapped classes: %11lu\n" , + nr_zapped_classes);return 0 ; }Why is that conditional?
Quoted 3 lines
Because I thought zapping class doesn't occur that often. Apparently, class zapping happens when the system first boots up. I guess that conditional check isn't needed. I can remove it in the next version.
Zapping a lock class happens every time a lock key is unregistered. That can happen any time as one can see in the following grep output:
$ git grep -lw 'lockdep_unregister_key' drivers/net/bonding/bond_main.c:4446: lockdep_unregister_key(&bond->stats_lock_key); drivers/net/team/team.c:1676: lockdep_unregister_key(&team->team_lock_key); drivers/net/team/team.c:1984: lockdep_unregister_key(&team->team_lock_key); include/linux/lockdep.h:294:extern void lockdep_unregister_key(struct lock_class_key *key); include/linux/lockdep.h:464:static inline void lockdep_unregister_key(struct lock_class_key *key) kernel/locking/lockdep.c:5166:void lockdep_unregister_key(struct lock_class_key *key) kernel/locking/lockdep.c:5201:EXPORT_SYMBOL_GPL(lockdep_unregister_key); kernel/workqueue.c:3456: lockdep_unregister_key(&wq->key); net/core/dev.c:9172: lockdep_unregister_key(&dev->qdisc_tx_busylock_key); net/core/dev.c:9173: lockdep_unregister_key(&dev->qdisc_running_key); net/core/dev.c:9174: lockdep_unregister_key(&dev->qdisc_xmit_lock_key); net/core/dev.c:9175: lockdep_unregister_key(&dev->addr_list_lock_key); net/core/dev.c:9183: lockdep_unregister_key(&dev->qdisc_xmit_lock_key); net/core/dev.c:9184: lockdep_unregister_key(&dev->addr_list_lock_key); tools/lib/lockdep/include/liblockdep/common.h:48:void lockdep_unregister_key(struct lock_class_key *key); tools/lib/lockdep/include/liblockdep/mutex.h:58: lockdep_unregister_key(&lock->key);
Bart.
Waiman Long
reviewerPATCH v2 2/6 locking/lockdep: Throw away all lock chains with zapped class
In reply to Waiman LongIf a lock chain contains a class that is zapped, the whole lock chain is now invalid. There is no point in keeping a partial chain behind hoping it can be useful. So just dump the corresponding chain_hlocks entries for now. A latter patch will try to reuse the freed chain_hlocks entries.
This patch also changes the type of nr_chain_hlocks to unsigned integer to be consistent with the other counters.
--- kernel/locking/lockdep.c | 36 ++++-------------------------- kernel/locking/lockdep_internals.h | 4 ++-- kernel/locking/lockdep_proc.c | 2 +- 3 files changed, 7 insertions(+), 35 deletions(-)
kernel/locking/lockdep.c +4 -32
@@ -2624,8 +2624,8 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS ]; static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); -int nr_chain_hlocks;static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS ]; +unsigned int nr_chain_hlocks;struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i) {
@@ -4770,57 +4770,29 @@ static void remove_class_from_lock_chain(struct pending_free *pf, struct lock_class *class) {#ifdef CONFIG_PROVE_LOCKING -struct lock_chain *new_chain; -u64 chain_key;int i;for (i = chain->base; i < chain->base + chain->depth; i++) {if (chain_hlocks[i] != class - lock_classes)continue ; -/* The code below leaks one chain_hlock[] entry. */ -if (--chain->depth >0 ) { -memmove (&chain_hlocks[i], &chain_hlocks[i +1 ], - (chain->base + chain->depth - i) * -sizeof (chain_hlocks[0 ])); - }/* * Each lock class occurs at most once in a lock chain so once * we found a match we can break out of this loop. */ - goto recalc; + goto free_lock_chain; }/* Since the chain has not been modified, return. */ return ; -recalc: - chain_key =INITIAL_CHAIN_KEY ; -for (i = chain->base; i < chain->base + chain->depth; i++) - chain_key =iterate_chain_key (chain_key, chain_hlocks[i]); -if (chain->depth && chain->chain_key == chain_key) -return ; +free_lock_chain:/* Overwrite the chain key for concurrent RCU readers. */ -WRITE_ONCE (chain->chain_key, chain_key); +WRITE_ONCE (chain->chain_key,INITIAL_CHAIN_KEY );/* * Note: calling hlist_del_rcu() from inside a * hlist_for_each_entry_rcu() loop is safe. */ hlist_del_rcu (&chain->entry);__set_bit (chain - lock_chains, pf->lock_chains_being_freed); -if (chain->depth ==0 ) -return ; -/* -* If the modified lock chain matches an existing lock chain, drop -* the modified lock chain. -*/ -if (lookup_chain_cache (chain_key)) -return ; - new_chain =alloc_lock_chain (); -if (WARN_ON_ONCE (!new_chain)) { -debug_locks_off (); -return ; - } - *new_chain = *chain; -hlist_add_head_rcu (&new_chain->entry,chainhashentry (chain_key));#endif }
kernel/locking/lockdep_internals.h +2 -2
@@ -128,14 +128,14 @@ extern unsigned long nr_zapped_classes;extern unsigned long nr_list_entries;long lockdep_next_lockchain (long i);unsigned long lock_chain_count (void ); -extern int nr_chain_hlocks;extern unsigned long nr_stack_trace_entries;extern unsigned int nr_hardirq_chains;extern unsigned int nr_softirq_chains;extern unsigned int nr_process_chains; -extern unsigned int max_lockdep_depth; +extern unsigned int nr_chain_hlocks; +extern unsigned int max_lockdep_depth;extern unsigned int max_bfs_queue_depth;#ifdef CONFIG_PROVE_LOCKING
kernel/locking/lockdep_proc.c +1 -1
@@ -271,7 +271,7 @@ static int lockdep_stats_show(struct seq_file *m, void *v)#ifdef CONFIG_PROVE_LOCKING seq_printf (m," dependency chains: %11lu [max: %lu]\n" ,lock_chain_count (),MAX_LOCKDEP_CHAINS ); -seq_printf (m," dependency chain hlocks: %11d [max: %lu]\n" , +seq_printf (m," dependency chain hlocks: %11u [max: %lu]\n" , nr_chain_hlocks,MAX_LOCKDEP_CHAIN_HLOCKS );#endif
Signature · 1 line
2.18.1
Peter Zijlstra
maintainerRe: [PATCH v2 2/6] locking/lockdep: Throw away all lock chains with zapped class
Quoted 2 lines · Waiman Long
If a lock chain contains a class that is zapped, the whole lock chain is now invalid.
Possibly. But I'm thinking that argument can/should be made mode elaborate.
Suppose we have A->B->C, and we're about to remove B.
Now, I suppose the trivial argument goes that if we remove the text that causes A->B, then so B->C will no longer happen. However, that doesn't mean A->C won't still occur.
OTOH, we might already have A->C and so our resulting chain would be a duplicate. Conversely, if we didn't already have A->C and it does indeed still occur (say it was omitted due to the redundant logic), then we will create this dependency the next time we'll encounter it.
Bart, do you see a problem with this reasoning?
In short, yes, I think you're right and we can remove the whole thing. But please, expand the Changelog a bit, possibly add some of this reasoning into a comment.
Waiman Long
reviewerRe: [PATCH v2 2/6] locking/lockdep: Throw away all lock chains with zapped class
Quoted 7 lines · Peter Zijlstra
Quoted 2 lines · Waiman Long
If a lock chain contains a class that is zapped, the whole lock chain is now invalid.
Possibly. But I'm thinking that argument can/should be made mode elaborate.
Suppose we have
A->B->C, and we're about to remove B.
Quoted 8 lines
Now, I suppose the trivial argument goes that if we remove the text that causes
A->B, then soB->Cwill no longer happen. However, that doesn't meanA->Cwon't still occur.OTOH, we might already have
A->Cand so our resulting chain would be a duplicate. Conversely, if we didn't already haveA->Cand it does indeed still occur (say it was omitted due to the redundant logic), then we will create this dependency the next time we'll encounter it.
I will prefer having it only when it actually happens rather than leaving a partial chain behind assuming that it may happen.
Quoted 7 lines
Bart, do you see a problem with this reasoning?
In short, yes, I think you're right and we can remove the whole thing. But please, expand the Changelog a bit, possibly add some of this reasoning into a comment.
Yes, I will elaborate more in the changelog.
Cheers,
Longman
Re: [PATCH v2 2/6] locking/lockdep: Throw away all lock chains with zapped class
In reply to Peter ZijlstraQuoted 17 lines · Peter Zijlstra
Quoted 2 lines · Waiman Long
If a lock chain contains a class that is zapped, the whole lock chain is now invalid.
Possibly. But I'm thinking that argument can/should be made mode elaborate.
Suppose we have
A->B->C, and we're about to remove B.Now, I suppose the trivial argument goes that if we remove the text that causes
A->B, then soB->Cwill no longer happen. However, that doesn't meanA->Cwon't still occur.OTOH, we might already have
A->Cand so our resulting chain would be a duplicate. Conversely, if we didn't already haveA->Cand it does indeed still occur (say it was omitted due to the redundant logic), then we will create this dependency the next time we'll encounter it.
Quoted 5 lines
Bart, do you see a problem with this reasoning?
In short, yes, I think you're right and we can remove the whole thing. But please, expand the Changelog a bit, possibly add some of this reasoning into a comment.
I think unconditionally dropping lock chains is wrong. If a lock class is zapped the rest of the lock chain remains valid and hence should be retained unless it duplicates another lock chain or if the length of the lock chain is reduced to a single element.
Bart.
Waiman Long
reviewerRe: [PATCH v2 2/6] locking/lockdep: Throw away all lock chains with zapped class
Quoted 22 lines · Bart Van Assche
Quoted 21 lines · Peter Zijlstra
Quoted 3 lines · Waiman Long
If a lock chain contains a class that is zapped, the whole lock chain is
now invalid.Possibly. But I'm thinking that argument can/should be made mode elaborate.
Suppose we have
A->B->C, and we're about to remove B.Now, I suppose the trivial argument goes that if we remove the text that causes
A->B, then soB->Cwill no longer happen. However, that doesn't meanA->Cwon't still occur.OTOH, we might already have
A->Cand so our resulting chain would be a duplicate. Conversely, if we didn't already haveA->Cand it does indeed still occur (say it was omitted due to the redundant logic), then we will create this dependency the next time we'll encounter it.Bart, do you see a problem with this reasoning?
Quoted 8 lines
Quoted 3 lines
In short, yes, I think you're right and we can remove the whole thing. But please, expand the Changelog a bit, possibly add some of this reasoning into a comment.
I think unconditionally dropping lock chains is wrong. If a lock class is zapped the rest of the lock chain remains valid and hence should be retained unless it duplicates another lock chain or if the length of the lock chain is reduced to a single element.
If the zapped class is at the end of the chain, the shorten one without the zapped class should have been stored already as the current code will store all its predecessor chains. If it is somewhere in the middle, there is no guarantee that the partial chain will actually happen. It may just clutter up the hash and make searching slower. Why don't we just store it when it actually happens?
Cheers,
Longman
Waiman Long
reviewerPATCH v2 3/6 locking/lockdep: Track number of zapped lock chains
In reply to Waiman LongAdd a new counter nr_zapped_lock_chains to track the number lock chains that have been removed.
--- kernel/locking/lockdep.c | 2 ++ kernel/locking/lockdep_internals.h | 1 + kernel/locking/lockdep_proc.c | 2 ++ 3 files changed, 5 insertions(+)
kernel/locking/lockdep.c +2 -0
@@ -2625,6 +2625,7 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS ]; static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS ]; +unsigned long nr_zapped_lock_chains;unsigned int nr_chain_hlocks;struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i)
@@ -4793,6 +4794,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,*/ hlist_del_rcu (&chain->entry);__set_bit (chain - lock_chains, pf->lock_chains_being_freed); + nr_zapped_lock_chains++;#endif }
kernel/locking/lockdep_internals.h +1 -0
@@ -125,6 +125,7 @@ struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i);extern unsigned long nr_lock_classes;extern unsigned long nr_zapped_classes; +extern unsigned long nr_zapped_lock_chains;extern unsigned long nr_list_entries;long lockdep_next_lockchain (long i);unsigned long lock_chain_count (void );
kernel/locking/lockdep_proc.c +2 -0
@@ -345,6 +345,8 @@ static int lockdep_stats_show(struct seq_file *m, void *v)seq_puts (m,"\n" );seq_printf (m," zapped classes: %11lu\n" , nr_zapped_classes); +seq_printf (m," zapped lock chains: %11lu\n" , + nr_zapped_lock_chains);return 0 ; }
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 4/6 locking/lockdep: Reuse freed chain_hlocks entries
In reply to Waiman LongOnce 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: 0By 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: 64By monitoring the output of lockdep_stats, the number of free chain hlocks and large chain blocks grew and shrank (sometimes to 0) repetitively as the test was progressing. There was no movement in the large chain blocks count with a MAX_CHAIN_BUCKETS value of 8.
--- kernel/locking/lockdep.c | 232 ++++++++++++++++++++++++++--- kernel/locking/lockdep_internals.h | 2 + kernel/locking/lockdep_proc.c | 4 + 3 files changed, 219 insertions(+), 19 deletions(-)
kernel/locking/lockdep.c +213 -19
@@ -2627,6 +2627,208 @@ static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS ];unsigned long nr_zapped_lock_chains;unsigned int nr_chain_hlocks; +unsigned int nr_free_chain_hlocks;/* Free cfhain_hlocks in buckets */ +unsigned int nr_large_chain_blocks;/* size > MAX_CHAIN_BUCKETS */ + +#ifdef CONFIG_PROVE_LOCKING +/* +* As chain_hlocks entries are allocated and freed, the freed entries are +* grouped into chain blocks that can be reused again. These chain blocks +* are put into a bucketed list according to their block size. +* +* Two APIs are provided for chain block allocation and freeing: +* - int alloc_chain_hlocks(int size) +* - void free_chain_hlocks(int base, int size) +* +* A minimum allocation size of 2 entries is enforced. When a lock chain +* is freed, the corresponding chain_hlocks[] entries are put into one +* of the bucketed lists: +* 2 <= size <= MAX_CHAIN_BUCKETS => buckets[size-1] +* > MAX_CHAIN_BUCKETS => buckets[0] +* +* When an allocation request is made, alloc_chain_hlocks() will first +* look up the matching bucketed list to find a free chain block. If not +* found, allocation will be made directly from the chain_hlocks array +* from the current nr_chain_hlocks value. +* +* Note that a chain_hlocks entry contain the class index which is +* crrently limited to 13 bits. +* +* The first 2 chain_hlocks entries in the chain block in the bucket +* list contains the following meta data: +* entry[0]: +* Bit 15 - always set to 1 (it is not a class index) +* Bits 0-14 - upper 15 bits of the next block index +* entry[1] - lower 16 bits of next block index +* +* A next block index of all 1 bits means it is the end of the list. +* +* On the unsized bucket (buckets[0]), the 3rd and 4th entries contain +* the chain block size. +* +* entry[2] - upper 16 bits of the chain block size +* entry[3] - lower 16 bits of the chain block size +* +* TODO: +* Evaluate if merging neighoring chain blocks and breaking a large chain +* block into smaller ones can be helpful in reducing the number of free +* held_hlocks entries stored in the bucketed lists. +*/ +#define MAX_CHAIN_BUCKETS 8 +#define CHAIN_HLOCKS_MASK 0xffff +#define CHAIN_BLK_FLAG (1U << 15) +#define CHAIN_BLK_LIST_END ((u16)-1) + +/* +* An empty bucket has a value of -1. Otherwise, it represents an offset +* to the chain_hlocks array. +*/ +static int chain_block_buckets[MAX_CHAIN_BUCKETS ]; + +static inline void init_chain_block_buckets (void ) +{ +int i; + +for (i =0 ; i <MAX_CHAIN_BUCKETS ; i++) + chain_block_buckets[i] =-1 ; +} + +/* +* Return offset of next chain block or -1 if end of list. +*/ +static inline int next_chain_block (int offset) +{ +if (chain_hlocks[offset] ==CHAIN_BLK_LIST_END ) +return -1 ; +return ((chain_hlocks[offset] & ~CHAIN_BLK_FLAG ) <<16 ) | + chain_hlocks[offset +1 ]; +} + +static inline void set_chain_block (int offset,int size,int next) +{ +if (unlikely (offset <0 )) { + chain_block_buckets[0 ] = next; +return ; + } + chain_hlocks[offset] = (next >>16 ) |CHAIN_BLK_FLAG ; + chain_hlocks[offset +1 ] = next &CHAIN_HLOCKS_MASK ; +if (size >MAX_CHAIN_BUCKETS ) { + chain_hlocks[offset +2 ] = size >>16 ; + chain_hlocks[offset +3 ] = size &CHAIN_HLOCKS_MASK ; + } +} + +/* +* This function should only be called for chain block in buckets[0]. +*/ +static inline int chain_block_size (int offset) +{ +return (chain_hlocks[offset +2 ] <<16 ) | chain_hlocks[offset +3 ]; +} + +/* +* Return offset of a chain block of the right size or -1 if not found. +*/ +static inline int alloc_chain_hlocks_from_buckets (int size) +{ +int prev, curr, next; + +if (!nr_free_chain_hlocks) +return -1 ; + +if (size <=MAX_CHAIN_BUCKETS ) { + curr = chain_block_buckets[size -1 ]; +if (curr <0 ) +return -1 ; + + chain_block_buckets[size -1 ] =next_chain_block (curr); + nr_free_chain_hlocks -= size; +return curr; + } + +/* +* Look for a free chain block of the given size +* +* It is rare to have a lock chain with depth > MAX_CHAIN_BUCKETS. +* It is also more expensive as we may iterate the whole list +* without finding one. +*/ + prev =-1 ; + curr = chain_block_buckets[0 ]; +while (curr >=0 ) { + next =next_chain_block (curr); +if (chain_block_size (curr) == size) { +set_chain_block (prev,0 , next); + nr_free_chain_hlocks -= size; + nr_large_chain_blocks--; +return curr; + } + prev = curr; + curr = next; + } +return -1 ; +} + +static inline void free_chain_hlocks (int base,int size) +{ +if (size <2 ) + size =2 ; + + nr_free_chain_hlocks += size; +if (size <=MAX_CHAIN_BUCKETS ) { +set_chain_block (base,0 , chain_block_buckets[size -1 ]); + chain_block_buckets[size -1 ] = base; +return ; + } +set_chain_block (base, size, chain_block_buckets[0 ]); + chain_block_buckets[0 ] = base; + nr_large_chain_blocks++; +} +#else +static inline void init_chain_block_buckets (void ) { } +static inline int alloc_chain_hlocks_from_buckets (int size) +{ +return -1 ; +} +#endif /* CONFIG_PROVE_LOCKING */ + +/* +* The graph lock must be held before calling this function. +* +* Return: an offset to chain_hlocks if successful, or +* -1 with graph lock released +*/ +static int alloc_chain_hlocks (int size) +{ +int curr; + +if (size <2 ) + size =2 ; + + curr =alloc_chain_hlocks_from_buckets (size); +if (curr >=0 ) +return curr; + +BUILD_BUG_ON ((1UL <<24 ) <=ARRAY_SIZE (chain_hlocks)); +BUILD_BUG_ON ((1UL <<6 ) <=ARRAY_SIZE (current->held_locks)); +BUILD_BUG_ON ((1UL <<8 *sizeof (chain_hlocks[0 ])) <= +ARRAY_SIZE (lock_classes)); + +/* +* Allocate directly from chain_hlocks. +*/ +if (likely (nr_chain_hlocks + size <=MAX_LOCKDEP_CHAIN_HLOCKS )) { + curr = nr_chain_hlocks; + nr_chain_hlocks += size; +return curr; + } +if (!debug_locks_off_graph_unlock ()) +return -1 ; + +print_lockdep_off ("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!" ); +dump_stack (); +return -1 ; +}struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i) {
@@ -2822,28 +3024,17 @@ static inline int add_chain_cache(struct task_struct *curr, chain->irq_context = hlock->irq_context; i =get_first_held_lock (curr, hlock); chain->depth = curr->lockdep_depth +1 - i; + j =alloc_chain_hlocks (chain->depth); +if (j <0 ) +return 0 ; -BUILD_BUG_ON ((1UL <<24 ) <=ARRAY_SIZE (chain_hlocks)); -BUILD_BUG_ON ((1UL <<6 ) <=ARRAY_SIZE (curr->held_locks)); -BUILD_BUG_ON ((1UL <<8 *sizeof (chain_hlocks[0 ])) <=ARRAY_SIZE (lock_classes)); - -if (likely (nr_chain_hlocks + chain->depth <=MAX_LOCKDEP_CHAIN_HLOCKS )) { - chain->base = nr_chain_hlocks; -for (j =0 ; j < chain->depth -1 ; j++, i++) { -int lock_id = curr->held_locks[i].class_idx; - chain_hlocks[chain->base + j] = lock_id; - } - chain_hlocks[chain->base + j] = class - lock_classes; - nr_chain_hlocks += chain->depth; - }else { -if (!debug_locks_off_graph_unlock ()) -return 0 ; + chain->base = j; +for (j =0 ; j < chain->depth -1 ; j++, i++) { +int lock_id = curr->held_locks[i].class_idx; -print_lockdep_off ("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!" ); -dump_stack (); -return 0 ; + chain_hlocks[chain->base + j] = lock_id; } - + chain_hlocks[chain->base + j] = class - lock_classes;hlist_add_head_rcu (&chain->entry, hash_head);debug_atomic_inc (chain_lookup_misses);inc_chains ();
@@ -4786,6 +4977,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,return ; free_lock_chain: +free_chain_hlocks (chain->base, chain->depth);/* Overwrite the chain key for concurrent RCU readers. */ WRITE_ONCE (chain->chain_key,INITIAL_CHAIN_KEY );/*
@@ -5178,6 +5370,8 @@ EXPORT_SYMBOL_GPL(lockdep_unregister_key);void __init lockdep_init (void ) { +init_chain_block_buckets (); +printk ("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n" );printk ("... MAX_LOCKDEP_SUBCLASSES: %lu\n" ,MAX_LOCKDEP_SUBCLASSES );
kernel/locking/lockdep_internals.h +2 -0
@@ -135,6 +135,8 @@ extern unsigned int nr_hardirq_chains;extern unsigned int nr_softirq_chains;extern unsigned int nr_process_chains;extern unsigned int nr_chain_hlocks; +extern unsigned int nr_free_chain_hlocks; +extern unsigned int nr_large_chain_blocks;extern unsigned int max_lockdep_depth;extern unsigned int max_bfs_queue_depth;
kernel/locking/lockdep_proc.c +4 -0
@@ -347,6 +347,10 @@ static int lockdep_stats_show(struct seq_file *m, void *v) nr_zapped_classes);seq_printf (m," zapped lock chains: %11lu\n" , nr_zapped_lock_chains); +seq_printf (m," free chain hlocks: %11u\n" , + nr_free_chain_hlocks); +seq_printf (m," large chain blocks: %11u\n" , + nr_large_chain_blocks);return 0 ; }
Signature · 1 line
2.18.1
Peter Zijlstra
maintainerRe: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 5 lines · Waiman Long
kernel/locking/lockdep.c +4
-0+#define CHAIN_HLOCKS_MASK 0xffff +static inline void set_chain_block (int offset,int size,int next) +{ +if (unlikely (offset <0 )) {
kernel/locking/lockdep.c static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); · line 2719
Quoted 10 lines
kernel/locking/lockdep.c +10
-0+ chain_block_buckets[0 ] = next; +return ; + } + chain_hlocks[offset] = (next >>16 ) |CHAIN_BLK_FLAG ; + chain_hlocks[offset +1 ] = next &CHAIN_HLOCKS_MASK ; +if (size >MAX_CHAIN_BUCKETS ) { + chain_hlocks[offset +2 ] = size >>16 ; + chain_hlocks[offset +3 ] = size &CHAIN_HLOCKS_MASK ; + } +}
AFAICT HLOCKS_MASK is superfluous. That is, you're assigning to a u16, it will truncate automagically.
But if you want to make it more explicit, something like:
chain_hlocks[offset + 1] = (u16)next;
might be easier to read still.
Waiman Long
reviewerRe: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 18 lines · Peter Zijlstra
Quoted 4 lines · Waiman Long
kernel/locking/lockdep.c +4
-0+#define CHAIN_HLOCKS_MASK 0xffff +static inline void set_chain_block (int offset,int size,int next) +{ +if (unlikely (offset <0 )) {kernel/locking/lockdep.c static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); · line 2719
Quoted 10 lines
kernel/locking/lockdep.c +10
-0+ chain_block_buckets[0 ] = next; +return ; + } + chain_hlocks[offset] = (next >>16 ) |CHAIN_BLK_FLAG ; + chain_hlocks[offset +1 ] = next &CHAIN_HLOCKS_MASK ; +if (size >MAX_CHAIN_BUCKETS ) { + chain_hlocks[offset +2 ] = size >>16 ; + chain_hlocks[offset +3 ] = size &CHAIN_HLOCKS_MASK ; + } +}AFAICT
HLOCKS_MASKis superfluous. That is, you're assigning to a u16, it will truncate automagically.
Quoted 6 lines
But if you want to make it more explicit, something like:
chain_hlocks[offset + 1] = (u16)next;might be easier to read still.
Yes, I am aware that the macro may not be needed. Will make the changes in the next version.
Thanks,
Longman
Peter Zijlstra
maintainerRe: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries
In reply to Waiman LongQuoted 70 lines · Waiman Long
kernel/locking/lockdep.c +69
-0+/* +* Return offset of a chain block of the right size or -1 if not found. +*/ +static inline int alloc_chain_hlocks_from_buckets (int size) +{ +int prev, curr, next; + +if (!nr_free_chain_hlocks) +return -1 ; + +if (size <=MAX_CHAIN_BUCKETS ) { + curr = chain_block_buckets[size -1 ]; +if (curr <0 ) +return -1 ; + + chain_block_buckets[size -1 ] =next_chain_block (curr); + nr_free_chain_hlocks -= size; +return curr; + } + +/* +* Look for a free chain block of the given size +* +* It is rare to have a lock chain with depth > MAX_CHAIN_BUCKETS. +* It is also more expensive as we may iterate the whole list +* without finding one. +*/ + prev =-1 ; + curr = chain_block_buckets[0 ]; +while (curr >=0 ) { + next =next_chain_block (curr); +if (chain_block_size (curr) == size) { +set_chain_block (prev,0 , next); + nr_free_chain_hlocks -= size; + nr_large_chain_blocks--; +return curr; + } + prev = curr; + curr = next; + } +return -1 ; +} +/* +* The graph lock must be held before calling this function. +* +* Return: an offset to chain_hlocks if successful, or +* -1 with graph lock released +*/ +static int alloc_chain_hlocks (int size) +{ +int curr; + +if (size <2 ) + size =2 ; + + curr =alloc_chain_hlocks_from_buckets (size); +if (curr >=0 ) +return curr; + +BUILD_BUG_ON ((1UL <<24 ) <=ARRAY_SIZE (chain_hlocks)); +BUILD_BUG_ON ((1UL <<6 ) <=ARRAY_SIZE (current->held_locks)); +BUILD_BUG_ON ((1UL <<8 *sizeof (chain_hlocks[0 ])) <= +ARRAY_SIZE (lock_classes)); + +/* +* Allocate directly from chain_hlocks. +*/ +if (likely (nr_chain_hlocks + size <=MAX_LOCKDEP_CHAIN_HLOCKS )) { + curr = nr_chain_hlocks;
kernel/locking/lockdep.c static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
Quoted 10 lines
kernel/locking/lockdep.c +10
-0+ nr_chain_hlocks += size; +return curr; + } +if (!debug_locks_off_graph_unlock ()) +return -1 ; + +print_lockdep_off ("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!" ); +dump_stack (); +return -1 ; +}
*groan*....
That's _two_ allocators :/ And it can trivially fail, even if there's plenty space available.
Consider nr_chain_hlocks is exhaused, and @size is empty, but size+1 still has blocks.
I'm guessing you didn't make it a single allocator because you didn't want to implement block splitting? why?
Waiman Long
reviewerRe: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 82 lines · Peter Zijlstra
Quoted 69 lines · Waiman Long
kernel/locking/lockdep.c +69
-0+/* +* Return offset of a chain block of the right size or -1 if not found. +*/ +static inline int alloc_chain_hlocks_from_buckets (int size) +{ +int prev, curr, next; + +if (!nr_free_chain_hlocks) +return -1 ; + +if (size <=MAX_CHAIN_BUCKETS ) { + curr = chain_block_buckets[size -1 ]; +if (curr <0 ) +return -1 ; + + chain_block_buckets[size -1 ] =next_chain_block (curr); + nr_free_chain_hlocks -= size; +return curr; + } + +/* +* Look for a free chain block of the given size +* +* It is rare to have a lock chain with depth > MAX_CHAIN_BUCKETS. +* It is also more expensive as we may iterate the whole list +* without finding one. +*/ + prev =-1 ; + curr = chain_block_buckets[0 ]; +while (curr >=0 ) { + next =next_chain_block (curr); +if (chain_block_size (curr) == size) { +set_chain_block (prev,0 , next); + nr_free_chain_hlocks -= size; + nr_large_chain_blocks--; +return curr; + } + prev = curr; + curr = next; + } +return -1 ; +} +/* +* The graph lock must be held before calling this function. +* +* Return: an offset to chain_hlocks if successful, or +* -1 with graph lock released +*/ +static int alloc_chain_hlocks (int size) +{ +int curr; + +if (size <2 ) + size =2 ; + + curr =alloc_chain_hlocks_from_buckets (size); +if (curr >=0 ) +return curr; + +BUILD_BUG_ON ((1UL <<24 ) <=ARRAY_SIZE (chain_hlocks)); +BUILD_BUG_ON ((1UL <<6 ) <=ARRAY_SIZE (current->held_locks)); +BUILD_BUG_ON ((1UL <<8 *sizeof (chain_hlocks[0 ])) <= +ARRAY_SIZE (lock_classes)); + +/* +* Allocate directly from chain_hlocks. +*/ +if (likely (nr_chain_hlocks + size <=MAX_LOCKDEP_CHAIN_HLOCKS )) { + curr = nr_chain_hlocks;kernel/locking/lockdep.c static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); · line 2831
Quoted 10 lines
kernel/locking/lockdep.c +10
-0+ nr_chain_hlocks += size; +return curr; + } +if (!debug_locks_off_graph_unlock ()) +return -1 ; + +print_lockdep_off ("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!" ); +dump_stack (); +return -1 ; +}*groan*....
Quoted 9 lines
That's _two_ allocators :/ And it can trivially fail, even if there's plenty space available.
Consider
nr_chain_hlocksis 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
Peter Zijlstra
maintainerRe: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 11 lines · Waiman Long
Quoted 9 lines · Peter Zijlstra
That's _two_ allocators :/ And it can trivially fail, even if there's plenty space available.
Consider
nr_chain_hlocksis exhaused, and @size is empty, but size+1 still has blocks.I'm guessing you didn't make it a single allocator because you didn't want to implement block splitting? why?
Quoted 8 lines
In my testing, most of the lock chains tend to be rather short (within the 2-8 range). I don't see a lot of free blocks left in the system after the test. So I don't see a need to implement block splitting for now.
If you think this is a feature that needs to be implemented for the patch to be complete, I can certainly add patch to do that. My initial thought is just to split long blocks in the unsized list for allocation request that is no longer than 8 to make thing easier.
From an engineering POV I'd much prefer a single complete allocator over two half ones. We can leave block merger out of the initial allocator I suppose and worry about that if/when fragmentation really shows to be a problem.
I'm thinking worst-fit might work well for our use-case. Best-fit would result in a heap of tiny fragments and we don't have really large allocations, which is the Achilles-heel of worst-fit.
Also, since you put in a minimal allocation size of 2, but did not mandate size is a multiple of 2, there is a weird corner case of size-1 fragments. The simplest case is to leak those, but put in a counter so we can see if they're a problem -- there is a fairly trivial way to recover them without going full merge.
Also, there's a bunch of syzcaller reports of running out of ENTRIES/CHAIN_HLOCKS, perhaps try some of those workloads to better stress the allocator?
Waiman Long
reviewerRe: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 19 lines · Peter Zijlstra
Quoted 10 lines · Waiman Long
Quoted 9 lines · Peter Zijlstra
That's _two_ allocators :/ And it can trivially fail, even if there's plenty space available.
Consider
nr_chain_hlocksis exhaused, and @size is empty, but size+1 still has blocks.I'm guessing you didn't make it a single allocator because you didn't want to implement block splitting? why?
Quoted 8 lines
In my testing, most of the lock chains tend to be rather short (within the 2-8 range). I don't see a lot of free blocks left in the system after the test. So I don't see a need to implement block splitting for now.
If you think this is a feature that needs to be implemented for the patch to be complete, I can certainly add patch to do that. My initial thought is just to split long blocks in the unsized list for allocation request that is no longer than 8 to make thing easier.
Quoted 8 lines
From an engineering POV I'd much prefer a single complete allocator over two half ones. We can leave block merger out of the initial allocator I suppose and worry about that if/when fragmentation really shows to be a problem.
I'm thinking worst-fit might work well for our use-case. Best-fit would result in a heap of tiny fragments and we don't have really large allocations, which is the Achilles-heel of worst-fit.
I am going to add a patch to split chain block as a last resort in case we run out of the main buffer.
Quoted 6 lines
Also, since you put in a minimal allocation size of 2, but did not mandate size is a multiple of 2, there is a weird corner case of size-1 fragments. The simplest case is to leak those, but put in a counter so we can see if they're a problem -- there is a fairly trivial way to recover them without going full merge.
There is no size-1 fragment. Are you referring to the those blocks with a size of 2, but with only one entry used? There are some wasted space there. I can add a counter to track that.
Cheers,
Longman
Quoted 5 lines
Also, there's a bunch of syzcaller reports of running out of ENTRIES/CHAIN_HLOCKS, perhaps try some of those workloads to better stress the allocator?
Peter Zijlstra
maintainerRe: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 7 lines · Waiman Long
Quoted 3 lines · Peter Zijlstra
I'm thinking worst-fit might work well for our use-case. Best-fit would result in a heap of tiny fragments and we don't have really large allocations, which is the Achilles-heel of worst-fit.
I am going to add a patch to split chain block as a last resort in case we run out of the main buffer.
It will be the common path; you'll start with a single huge fragment.
Remember, 1 allocator is better than 2.
Quoted 9 lines
Quoted 5 lines
Also, since you put in a minimal allocation size of 2, but did not mandate size is a multiple of 2, there is a weird corner case of size-1 fragments. The simplest case is to leak those, but put in a counter so we can see if they're a problem -- there is a fairly trivial way to recover them without going full merge.
There is no size-1 fragment. Are you referring to the those blocks with a size of 2, but with only one entry used? There are some wasted space there. I can add a counter to track that.
There will be; imagine you have a size-6 fragment and request a size-5, then we'll have to split off one. But one is too short to encode on the free lists.
Suppose you tag them with -2, then on free of the size-5, we can check if curr+size+1 is -2 and reunite.
First-fit or best-fit would result in lots of that, hence my suggestion to use worst-fit if you can't find an exact match.
Waiman Long
reviewerRe: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 10 lines · Peter Zijlstra
Quoted 6 lines · Waiman Long
Quoted 3 lines · Peter Zijlstra
I'm thinking worst-fit might work well for our use-case. Best-fit would result in a heap of tiny fragments and we don't have really large allocations, which is the Achilles-heel of worst-fit.
I am going to add a patch to split chain block as a last resort in case we run out of the main buffer.
It will be the common path; you'll start with a single huge fragment.
Remember, 1 allocator is better than 2.
One reason why I keep the array allocation code is because it is simple and fast. Using a free block in the bucket will be a bit slower. Still we are just dealing with the first block in the list as long as the size isn't bigger than MAX_CHAIN_BUCKETS. Now if we need to deal with block splitting (or even merging), it will be even more slow. Given the fact that we are holding the graph lock in doing all these. It could have a visible impact on performance.
That is the primary reason why I intend to allow block splitting only as the last resort when the chain_hlocks array is running out.
Quoted 12 lines
Quoted 8 lines
Quoted 5 lines
Also, since you put in a minimal allocation size of 2, but did not mandate size is a multiple of 2, there is a weird corner case of size-1 fragments. The simplest case is to leak those, but put in a counter so we can see if they're a problem -- there is a fairly trivial way to recover them without going full merge.
There is no size-1 fragment. Are you referring to the those blocks with a size of 2, but with only one entry used? There are some wasted space there. I can add a counter to track that.
There will be; imagine you have a size-6 fragment and request a size-5, then we'll have to split off one. But one is too short to encode on the free lists.
Quoted 6 lines
Suppose you tag them with -2, then on free of the size-5, we can check if curr+size+1 is -2 and reunite.
First-fit or best-fit would result in lots of that, hence my suggestion to use worst-fit if you can't find an exact match.
What I am thinking is to allow block splitting only if it has a size that is at least 2 larger than the desire value. In that way, we will not produce a fragment that is less than 2 in size. The down side is that we have fewer viable candidates for splitting.
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries
In reply to Waiman LongQuoted 4 lines · Waiman Long
An internal nfsd test that ran for more than an hour could cause the following message to be displayed.
[ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!
I'm guessing the pertinent detail you forget to mention here is that that test re-loads the nfs modules lots of times?
Waiman Long
reviewerRe: [PATCH v2 4/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 8 lines · Peter Zijlstra
Quoted 4 lines · Waiman Long
An internal nfsd test that ran for more than an hour could cause the following message to be displayed.
[ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!I'm guessing the pertinent detail you forget to mention here is that that test re-loads the nfs modules lots of times?
Yes, that is true. I will mention it in the next version.
Thanks,
Longman
Waiman Long
reviewerPATCH v2 5/6 locking/lockdep: Decrement irq context counters when removing lock chain
In reply to Waiman LongThere 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.
--- kernel/locking/lockdep.c | 35 +++++++++++++++++++++--------- kernel/locking/lockdep_internals.h | 6 +++++ 2 files changed, 31 insertions(+), 10 deletions(-)
kernel/locking/lockdep.c +25 -10
@@ -2300,16 +2300,24 @@ static int check_irq_usage(struct task_struct *curr, struct held_lock *prev, return 0; } -static void inc_chains (void ) +static void inc_chains (int irq_context) { -if (current->hardirq_context) +if (irq_context &LOCK_CHAIN_HARDIRQ_CONTEXT ) nr_hardirq_chains++; -else { -if (current->softirq_context) - nr_softirq_chains++; -else - nr_process_chains++; - } +else if (irq_context &LOCK_CHAIN_SOFTIRQ_CONTEXT ) + nr_softirq_chains++; +else + nr_process_chains++; +} + +static void dec_chains (int irq_context) +{ +if (irq_context &LOCK_CHAIN_HARDIRQ_CONTEXT ) + nr_hardirq_chains--; +else if (irq_context &LOCK_CHAIN_SOFTIRQ_CONTEXT ) + nr_softirq_chains--; +else + nr_process_chains--; }#else
@@ -2325,6 +2333,10 @@ static inline void inc_chains(void) nr_process_chains++; } +static void dec_chains (int irq_context) +{ + nr_process_chains--; +}#endif /* CONFIG_TRACE_IRQFLAGS */ static void
@@ -3037,7 +3049,7 @@ static inline int add_chain_cache(struct task_struct *curr, chain_hlocks[chain->base + j] = class - lock_classes;hlist_add_head_rcu (&chain->entry, hash_head);debug_atomic_inc (chain_lookup_misses); -inc_chains (); +inc_chains (chain->irq_context);return 1 ; }
@@ -3790,7 +3802,8 @@ mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)static inline unsigned int task_irq_context (struct task_struct *task) { -return 2 * !!task->hardirq_context + !!task->softirq_context; +return LOCK_CHAIN_HARDIRQ_CONTEXT * !!task->hardirq_context + +LOCK_CHAIN_SOFTIRQ_CONTEXT * !!task->softirq_context; } static int separate_irq_context(struct task_struct *curr,
@@ -4980,6 +4993,8 @@ static void remove_class_from_lock_chain(struct pending_free *pf,free_chain_hlocks (chain->base, chain->depth);/* Overwrite the chain key for concurrent RCU readers. */ WRITE_ONCE (chain->chain_key,INITIAL_CHAIN_KEY ); +dec_chains (chain->irq_context); +/* * Note: calling hlist_del_rcu() from inside a * hlist_for_each_entry_rcu() loop is safe.
kernel/locking/lockdep_internals.h +6 -0
@@ -98,6 +98,12 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ =#define MAX_LOCKDEP_CHAINS_BITS 16 +/* +* Bit definitions for lock_chain.irq_context +*/ +#define LOCK_CHAIN_SOFTIRQ_CONTEXT (1 << 0) +#define LOCK_CHAIN_HARDIRQ_CONTEXT (1 << 1) +/* * Stack-trace: tightly packed array of stack backtrace * addresses. Protected by the hash_lock.
Signature · 1 line
2.18.1
Peter Zijlstra
maintainerRe: [PATCH v2 5/6] locking/lockdep: Decrement irq context counters when removing lock chain
Quoted 10 lines · Waiman Long
There are currently three counters to track the irq context of a lock chain -
nr_hardirq_chains,nr_softirq_chainsandnr_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_statsto 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 <[email protected]>
Fixes go at the start of a series, because if the depend on prior patches (as this one does) we cannot apply them.
Waiman Long
reviewerRe: [PATCH v2 5/6] locking/lockdep: Decrement irq context counters when removing lock chain
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Waiman Long
There are currently three counters to track the irq context of a lock chain -
nr_hardirq_chains,nr_softirq_chainsandnr_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_statsto be incorrect.
Quoted 7 lines
Quoted 4 lines
Fix that by decrementing the right counter when a lock chain is removed.
Fixes a0b0fd53e1e6 ("locking/lockdep: Free lock classes that are no longer in use")Signed-off-by Waiman Long <[email protected]>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
Waiman Long
reviewerPATCH v2 6/6 locking/lockdep: Display irq_context names in /proc/lockdep_chains
In reply to Waiman LongCurrently, 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
@@ -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
Waiman Long
reviewerQuoted 32 lines · Waiman Long
v2:
- Revamp thechain_hlocksreuse patch to store the freedchain_hlocksinformation in thechain_hlocksentries 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_chainsmore 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_hlockscounters to be tracked by/proc/lockdep_stats. It also fixes leakage in the irq context counters and makes the output of/proc/lockdep_chainsmore 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 freedchain_hlocksentries locking/lockdep: Decrement irq context counters when removing lock
chain
locking/lockdep: Displayirq_contextnames in/proc/lockdep_chains
Quoted 5 lines
kernel/locking/lockdep.c | 307 +++++++++++++++++++++++------ kernel/locking/lockdep_internals.h | 14 +- kernel/locking/lockdep_proc.c | 26 ++- 3 files changed, 282 insertions(+), 65 deletions(-)
Ping! Any comments or suggestion for further improvement?
Cheers,
Longman
Peter Zijlstra
maintainerQuoted 1 line · Waiman Long
Ping! Any comments or suggestion for further improvement?
You got stuck in the xmas pile -- I haven't looked at email in 2 weeks. I'll try and get to it soon-ish :-)
Waiman Long
reviewerQuoted 6 lines · Peter Zijlstra
Quoted 1 line · Waiman Long
Ping! Any comments or suggestion for further improvement?
You got stuck in the xmas pile -- I haven't looked at email in 2 weeks. I'll try and get to it soon-ish :-)
Thanks!
Longman