locking/lockdep: Reuse zapped chain_hlocks entries
Waiman Long
reviewerv6 cover locking/lockdep: Reuse zapped chain_hlocks entries
v6:
- Drop patch 7 for now.
- Incorporate further changes as suggested by PeterZ.
- Increase MAX_CHAIN_BUCKETS to 16 to further minimize the possibility of having more than one chain block in bucket 0.
v5:
- Fix more build errors reported by kbuild test robot.
v4:
- Fix build errors reported by kbuild test robot.
- Adopt the single chain block allocator code suggested by PeterZ which combine the last 3 patches of v3 series.
- Add another patch to introduce a fast path in the chain block allocator.
- In patch 1, move the inc_chains() out of CONFIG_TRACE_IRQFLAGS conditional compilation block.
v3:
- Move the bug fix patches to the beginning of the series.
- Include a number of changes as suggested by PeterZ.
- Increase MAX_CHAIN_BUCKETS from 8 to 10 to reduce the chance of using the unsized list.
- Add patch 7 to add a lockdep_early_init() call.
- Add patch 8 to allocate chain hlocks by splitting large chain block as a last resort.
v2:
- Revamp the chain_hlocks reuse patch to store the freed chain_hlocks information in the chain_hlocks entries themselves avoiding the need of a separate set of tracking structures. This, however, requires a minimum allocation size of at least 2. Thanks to PeterZ for his review and inspiring this change.
- Remove the leakage counter as it is no longer applicable.
- Add patch 6 to make the output of /proc/lockdep_chains more readable.
It was found that when running a workload that kept on adding lock classes and then zapping them repetitively, the system will eventually run out of chain_hlocks[] entries even though there were still plenty of other lockdep data buffers available.
[ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! [ 4318.444809] turning off the locking correctness validator.
In order to fix this problem, we have to make chain_hlocks[] entries reusable just like other lockdep arrays. Besides that, the patchset also adds some zapped class and chain_hlocks counters to be tracked by /proc/lockdep_stats. It also fixes leakage in the irq context counters and makes the output of /proc/lockdep_chains more readable.
Waiman Long (6):
locking/lockdep: Decrement irq context counters when removing lock
chain
locking/lockdep: Display irq_context names in /proc/lockdep_chains locking/lockdep: Track number of zapped classes locking/lockdep: Throw away all lock chains with zapped class locking/lockdep: Track number of zapped lock chains locking/lockdep: Reuse freed chain_hlocks entries
kernel/locking/lockdep.c | 332 ++++++++++++++++++++++++----- kernel/locking/lockdep_internals.h | 14 +- kernel/locking/lockdep_proc.c | 31 ++- 3 files changed, 312 insertions(+), 65 deletions(-)
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v6 1/6 locking/lockdep: Decrement irq context counters when removing lock chain
There are currently three counters to track the irq context of a lock chain - nr_hardirq_chains, nr_softirq_chains and nr_process_chains. They are incremented when a new lock chain is added, but they are not decremented when a lock chain is removed. That causes some of the statistic counts reported by /proc/lockdep_stats to be incorrect.
Fix that by decrementing the right counter when a lock chain is removed.
Since inc_chains() no longer accesses hardirq_context and softirq_context directly, it is moved out from the CONFIG_TRACE_IRQFLAGS conditional compilation block.
--- kernel/locking/lockdep.c | 40 +++++++++++++++++------------- kernel/locking/lockdep_internals.h | 6 +++++ 2 files changed, 29 insertions(+), 17 deletions(-)
kernel/locking/lockdep.c +23 -17
@@ -2298,18 +2298,6 @@ static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,return 0 ; } -static void inc_chains (void ) -{ -if (current->hardirq_context) - nr_hardirq_chains++; -else { -if (current->softirq_context) - nr_softirq_chains++; -else - nr_process_chains++; - } -} -#else static inline int check_irq_usage(struct task_struct *curr,
@@ -2317,13 +2305,27 @@ static inline int check_irq_usage(struct task_struct *curr, {return 1 ; } +#endif /* CONFIG_TRACE_IRQFLAGS */ -static inline void inc_chains (void ) +static void inc_chains (int irq_context) { - nr_process_chains++; +if (irq_context &LOCK_CHAIN_HARDIRQ_CONTEXT ) + nr_hardirq_chains++; +else if (irq_context &LOCK_CHAIN_SOFTIRQ_CONTEXT ) + nr_softirq_chains++; +else + nr_process_chains++; } -#endif /* CONFIG_TRACE_IRQFLAGS */ +static void dec_chains (int irq_context) +{ +if (irq_context &LOCK_CHAIN_HARDIRQ_CONTEXT ) + nr_hardirq_chains--; +else if (irq_context &LOCK_CHAIN_SOFTIRQ_CONTEXT ) + nr_softirq_chains--; +else + nr_process_chains--; +}static void print_deadlock_scenario (struct held_lock *nxt,struct held_lock *prv)
@@ -2843,7 +2845,7 @@ static inline int add_chain_cache(struct task_struct *curr,hlist_add_head_rcu (&chain->entry, hash_head);debug_atomic_inc (chain_lookup_misses); -inc_chains (); +inc_chains (chain->irq_context);return 1 ; }
@@ -3596,7 +3598,8 @@ mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)static inline unsigned int task_irq_context (struct task_struct *task) { -return 2 * !!task->hardirq_context + !!task->softirq_context; +return LOCK_CHAIN_HARDIRQ_CONTEXT * !!task->hardirq_context + +LOCK_CHAIN_SOFTIRQ_CONTEXT * !!task->softirq_context; } static int separate_irq_context(struct task_struct *curr,
@@ -4798,6 +4801,8 @@ static void remove_class_from_lock_chain(struct pending_free *pf,return ;/* Overwrite the chain key for concurrent RCU readers. */ WRITE_ONCE (chain->chain_key, chain_key); +dec_chains (chain->irq_context); +/* * Note: calling hlist_del_rcu() from inside a * hlist_for_each_entry_rcu() loop is safe.
@@ -4819,6 +4824,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf, } *new_chain = *chain;hlist_add_head_rcu (&new_chain->entry,chainhashentry (chain_key)); +inc_chains (new_chain->irq_context);#endif }
kernel/locking/lockdep_internals.h +6 -0
@@ -106,6 +106,12 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ =#define STACK_TRACE_HASH_SIZE 16384#endif +/* +* Bit definitions for lock_chain.irq_context +*/ +#define LOCK_CHAIN_SOFTIRQ_CONTEXT (1 << 0) +#define LOCK_CHAIN_HARDIRQ_CONTEXT (1 << 1) +#define MAX_LOCKDEP_CHAINS (1UL << MAX_LOCKDEP_CHAINS_BITS)#define MAX_LOCKDEP_CHAIN_HLOCKS (MAX_LOCKDEP_CHAINS*5)
Signature · 1 line
2.18.1
[tip: locking/core] locking/lockdep: Decrement IRQ context counters when removing lock chain
The following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: b3b9c187dc2544923a601733a85352b9ddaba9b3 Gitweb: https://git.kernel.org/tip/b3b9c187dc2544923a601733a85352b9ddaba9b3 Author: Waiman Long <[email protected]> AuthorDate: Thu, 06 Feb 2020 10:24:03 -05:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Tue, 11 Feb 2020 13:10:48 +01:00
locking/lockdep: Decrement IRQ context counters when removing lock chain
There are currently three counters to track the IRQ context of a lock chain - nr_hardirq_chains, nr_softirq_chains and nr_process_chains. They are incremented when a new lock chain is added, but they are not decremented when a lock chain is removed. That causes some of the statistic counts reported by /proc/lockdep_stats to be incorrect. IRQ
Fix that by decrementing the right counter when a lock chain is removed.
Since inc_chains() no longer accesses hardirq_context and softirq_context directly, it is moved out from the CONFIG_TRACE_IRQFLAGS conditional compilation block.
--- kernel/locking/lockdep.c | 40 ++++++++++++++++------------- kernel/locking/lockdep_internals.h | 6 ++++- 2 files changed, 29 insertions(+), 17 deletions(-)
kernel/locking/lockdep.c +23 -17
@@ -2298,18 +2298,6 @@ static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,return 0 ; } -static void inc_chains (void ) -{ -if (current->hardirq_context) - nr_hardirq_chains++; -else { -if (current->softirq_context) - nr_softirq_chains++; -else - nr_process_chains++; - } -} -#else static inline int check_irq_usage(struct task_struct *curr,
@@ -2317,13 +2305,27 @@ static inline int check_irq_usage(struct task_struct *curr, {return 1 ; } +#endif /* CONFIG_TRACE_IRQFLAGS */ -static inline void inc_chains (void ) +static void inc_chains (int irq_context) { - nr_process_chains++; +if (irq_context &LOCK_CHAIN_HARDIRQ_CONTEXT ) + nr_hardirq_chains++; +else if (irq_context &LOCK_CHAIN_SOFTIRQ_CONTEXT ) + nr_softirq_chains++; +else + nr_process_chains++; } -#endif /* CONFIG_TRACE_IRQFLAGS */ +static void dec_chains (int irq_context) +{ +if (irq_context &LOCK_CHAIN_HARDIRQ_CONTEXT ) + nr_hardirq_chains--; +else if (irq_context &LOCK_CHAIN_SOFTIRQ_CONTEXT ) + nr_softirq_chains--; +else + nr_process_chains--; +}static void print_deadlock_scenario (struct held_lock *nxt,struct held_lock *prv)
@@ -2843,7 +2845,7 @@ static inline int add_chain_cache(struct task_struct *curr,hlist_add_head_rcu (&chain->entry, hash_head);debug_atomic_inc (chain_lookup_misses); -inc_chains (); +inc_chains (chain->irq_context);return 1 ; }
@@ -3596,7 +3598,8 @@ lock_used:static inline unsigned int task_irq_context (struct task_struct *task) { -return 2 * !!task->hardirq_context + !!task->softirq_context; +return LOCK_CHAIN_HARDIRQ_CONTEXT * !!task->hardirq_context + +LOCK_CHAIN_SOFTIRQ_CONTEXT * !!task->softirq_context; } static int separate_irq_context(struct task_struct *curr,
@@ -4798,6 +4801,8 @@ recalc:return ;/* Overwrite the chain key for concurrent RCU readers. */ WRITE_ONCE (chain->chain_key, chain_key); +dec_chains (chain->irq_context); +/* * Note: calling hlist_del_rcu() from inside a * hlist_for_each_entry_rcu() loop is safe.
@@ -4819,6 +4824,7 @@ recalc: } *new_chain = *chain;hlist_add_head_rcu (&new_chain->entry,chainhashentry (chain_key)); +inc_chains (new_chain->irq_context);#endif }
kernel/locking/lockdep_internals.h +6 -0
@@ -106,6 +106,12 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ =#define STACK_TRACE_HASH_SIZE 16384#endif +/* +* Bit definitions for lock_chain.irq_context +*/ +#define LOCK_CHAIN_SOFTIRQ_CONTEXT (1 << 0) +#define LOCK_CHAIN_HARDIRQ_CONTEXT (1 << 1) +#define MAX_LOCKDEP_CHAINS (1UL << MAX_LOCKDEP_CHAINS_BITS)#define MAX_LOCKDEP_CHAIN_HLOCKS (MAX_LOCKDEP_CHAINS*5)
Waiman Long
reviewerPATCH v6 2/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
[tip: locking/core] locking/lockdep: Display irq_context names in /proc/lockdep_chains
The following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: b9875e9882295749a14b31e16dd504ae904cf070 Gitweb: https://git.kernel.org/tip/b9875e9882295749a14b31e16dd504ae904cf070 Author: Waiman Long <[email protected]> AuthorDate: Thu, 06 Feb 2020 10:24:04 -05:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Tue, 11 Feb 2020 13:10:48 +01:00
locking/lockdep: Display irq_context names in /proc/lockdep_chains
Currently, the irq_context field of a lock chains displayed in /proc/lockdep_chains is just a number. It is likely that many people may not know what a non-zero number means. To make the information more useful, print the actual irq names ("softirq" and "hardirq") instead.
--- kernel/locking/lockdep_proc.c | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-)
kernel/locking/lockdep_proc.c +8 -1
@@ -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);
Waiman Long
reviewerPATCH v6 3/6 locking/lockdep: Track number of zapped classes
In reply to Waiman LongThe whole point of the lockdep dynamic key patch is to allow unused locks to be removed from the lockdep data buffers so that existing buffer space can be reused. However, there is no way to find out how many unused locks are zapped and so we don't know if the zapping process is working properly.
Add a new nr_zapped_classes counter to track that and show it in /proc/lockdep_stats.
--- kernel/locking/lockdep.c | 2 ++ kernel/locking/lockdep_internals.h | 1 + kernel/locking/lockdep_proc.c | 6 ++++++ 3 files changed, 9 insertions(+)
kernel/locking/lockdep.c +2 -0
@@ -147,6 +147,7 @@ static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);#define KEYHASH_SIZE (1UL << KEYHASH_BITS)static struct hlist_head lock_keys_hash[KEYHASH_SIZE ];unsigned long nr_lock_classes; +unsigned long nr_zapped_classes;#ifndef CONFIG_DEBUG_LOCKDEP static#endif
@@ -4880,6 +4881,7 @@ static void zap_class(struct pending_free *pf, struct lock_class *class) }remove_class_from_lock_chains (pf, class); + nr_zapped_classes++; }static void reinit_class (struct lock_class *class)
kernel/locking/lockdep_internals.h +1 -0
@@ -130,6 +130,7 @@ extern const char *__get_key_name(const struct lockdep_subclass_key *key,struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i);extern unsigned long nr_lock_classes; +extern unsigned long nr_zapped_classes;extern unsigned long nr_list_entries;long lockdep_next_lockchain (long i);unsigned long lock_chain_count (void );
kernel/locking/lockdep_proc.c +6 -0
@@ -343,6 +343,12 @@ static int lockdep_stats_show(struct seq_file *m, void *v)seq_printf (m," debug_locks: %11u\n" , debug_locks); +/* +* Zappped classes and lockdep data buffers reuse statistics. +*/ +seq_puts (m,"\n" ); +seq_printf (m," zapped classes: %11lu\n" , + nr_zapped_classes);return 0 ; }
Signature · 1 line
2.18.1
[tip: locking/core] locking/lockdep: Track number of zapped classes
The following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 1d44bcb4fdb650b2a57c9ff593a4d246a10ad801 Gitweb: https://git.kernel.org/tip/1d44bcb4fdb650b2a57c9ff593a4d246a10ad801 Author: Waiman Long <[email protected]> AuthorDate: Thu, 06 Feb 2020 10:24:05 -05:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Tue, 11 Feb 2020 13:10:49 +01:00
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 counter to track that and show it in /proc/lockdep_stats.
--- kernel/locking/lockdep.c | 2 ++ kernel/locking/lockdep_internals.h | 1 + kernel/locking/lockdep_proc.c | 6 ++++++ 3 files changed, 9 insertions(+)
kernel/locking/lockdep.c +2 -0
@@ -147,6 +147,7 @@ static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);#define KEYHASH_SIZE (1UL << KEYHASH_BITS)static struct hlist_head lock_keys_hash[KEYHASH_SIZE ];unsigned long nr_lock_classes; +unsigned long nr_zapped_classes;#ifndef CONFIG_DEBUG_LOCKDEP static#endif
@@ -4880,6 +4881,7 @@ static void zap_class(struct pending_free *pf, struct lock_class *class) }remove_class_from_lock_chains (pf, class); + nr_zapped_classes++; }static void reinit_class (struct lock_class *class)
kernel/locking/lockdep_internals.h +1 -0
@@ -130,6 +130,7 @@ extern const char *__get_key_name(const struct lockdep_subclass_key *key,struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i);extern unsigned long nr_lock_classes; +extern unsigned long nr_zapped_classes;extern unsigned long nr_list_entries;long lockdep_next_lockchain (long i);unsigned long lock_chain_count (void );
kernel/locking/lockdep_proc.c +6 -0
@@ -343,6 +343,12 @@ static int lockdep_stats_show(struct seq_file *m, void *v)seq_printf (m," debug_locks: %11u\n" , debug_locks); +/* +* Zappped classes and lockdep data buffers reuse statistics. +*/ +seq_puts (m,"\n" ); +seq_printf (m," zapped classes: %11lu\n" , + nr_zapped_classes);return 0 ; }
Waiman Long
reviewerPATCH v6 4/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 likely to be invalid. If the zapped class is at the end of the chain, the partial chain without the zapped class should have been stored already as the current code will store all its predecessor chains. If the zapped class is somewhere in the middle, there is no guarantee that the partial chain will actually happen. It may just clutter up the hash and make searching slower. I would rather prefer storing the chain only when it actually happens.
So just dump the corresponding chain_hlocks entries for now. A latter patch will try to reuse the freed chain_hlocks entries.
This patch also changes the type of nr_chain_hlocks to unsigned integer to be consistent with the other counters.
--- kernel/locking/lockdep.c | 37 ++++-------------------------- kernel/locking/lockdep_internals.h | 4 ++-- kernel/locking/lockdep_proc.c | 2 +- 3 files changed, 7 insertions(+), 36 deletions(-)
kernel/locking/lockdep.c +4 -33
@@ -2625,8 +2625,8 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS ]; static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); -int nr_chain_hlocks;static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS ]; +unsigned int nr_chain_hlocks;struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i) {
@@ -4772,36 +4772,23 @@ static void remove_class_from_lock_chain(struct pending_free *pf, struct lock_class *class) {#ifdef CONFIG_PROVE_LOCKING -struct lock_chain *new_chain; -u64 chain_key;int i;for (i = chain->base; i < chain->base + chain->depth; i++) {if (chain_hlocks[i] != class - lock_classes)continue ; -/* The code below leaks one chain_hlock[] entry. */ -if (--chain->depth >0 ) { -memmove (&chain_hlocks[i], &chain_hlocks[i +1 ], - (chain->base + chain->depth - i) * -sizeof (chain_hlocks[0 ])); - }/* * Each lock class occurs at most once in a lock chain so once * we found a match we can break out of this loop. */ - goto recalc; + goto free_lock_chain; }/* Since the chain has not been modified, return. */ return ; -recalc: - chain_key =INITIAL_CHAIN_KEY ; -for (i = chain->base; i < chain->base + chain->depth; i++) - chain_key =iterate_chain_key (chain_key, chain_hlocks[i]); -if (chain->depth && chain->chain_key == chain_key) -return ; +free_lock_chain:/* Overwrite the chain key for concurrent RCU readers. */ -WRITE_ONCE (chain->chain_key, chain_key); +WRITE_ONCE (chain->chain_key,INITIAL_CHAIN_KEY );dec_chains (chain->irq_context);/*
@@ -4810,22 +4797,6 @@ static void remove_class_from_lock_chain(struct pending_free *pf,*/ hlist_del_rcu (&chain->entry);__set_bit (chain - lock_chains, pf->lock_chains_being_freed); -if (chain->depth ==0 ) -return ; -/* -* If the modified lock chain matches an existing lock chain, drop -* the modified lock chain. -*/ -if (lookup_chain_cache (chain_key)) -return ; - new_chain =alloc_lock_chain (); -if (WARN_ON_ONCE (!new_chain)) { -debug_locks_off (); -return ; - } - *new_chain = *chain; -hlist_add_head_rcu (&new_chain->entry,chainhashentry (chain_key)); -inc_chains (new_chain->irq_context);#endif }
kernel/locking/lockdep_internals.h +2 -2
@@ -134,14 +134,14 @@ extern unsigned long nr_zapped_classes;extern unsigned long nr_list_entries;long lockdep_next_lockchain (long i);unsigned long lock_chain_count (void ); -extern int nr_chain_hlocks;extern unsigned long nr_stack_trace_entries;extern unsigned int nr_hardirq_chains;extern unsigned int nr_softirq_chains;extern unsigned int nr_process_chains; -extern unsigned int max_lockdep_depth; +extern unsigned int nr_chain_hlocks; +extern unsigned int max_lockdep_depth;extern unsigned int max_bfs_queue_depth;#ifdef CONFIG_PROVE_LOCKING
kernel/locking/lockdep_proc.c +1 -1
@@ -278,7 +278,7 @@ static int lockdep_stats_show(struct seq_file *m, void *v)#ifdef CONFIG_PROVE_LOCKING seq_printf (m," dependency chains: %11lu [max: %lu]\n" ,lock_chain_count (),MAX_LOCKDEP_CHAINS ); -seq_printf (m," dependency chain hlocks: %11d [max: %lu]\n" , +seq_printf (m," dependency chain hlocks: %11u [max: %lu]\n" , nr_chain_hlocks,MAX_LOCKDEP_CHAIN_HLOCKS );#endif
Signature · 1 line
2.18.1
[tip: locking/core] locking/lockdep: Throw away all lock chains with zapped class
The following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 836bd74b5957779171c9648e9e29145fc089fffe Gitweb: https://git.kernel.org/tip/836bd74b5957779171c9648e9e29145fc089fffe Author: Waiman Long <[email protected]> AuthorDate: Thu, 06 Feb 2020 10:24:06 -05:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Tue, 11 Feb 2020 13:10:50 +01:00
locking/lockdep: Throw away all lock chains with zapped class
If a lock chain contains a class that is zapped, the whole lock chain is likely to be invalid. If the zapped class is at the end of the chain, the partial chain without the zapped class should have been stored already as the current code will store all its predecessor chains. If the zapped class is somewhere in the middle, there is no guarantee that the partial chain will actually happen. It may just clutter up the hash and make searching slower. I would rather prefer storing the chain only when it actually happens.
So just dump the corresponding chain_hlocks entries for now. A latter patch will try to reuse the freed chain_hlocks entries.
This patch also changes the type of nr_chain_hlocks to unsigned integer to be consistent with the other counters.
--- kernel/locking/lockdep.c | 37 +++-------------------------- kernel/locking/lockdep_internals.h | 4 +-- kernel/locking/lockdep_proc.c | 2 +- 3 files changed, 7 insertions(+), 36 deletions(-)
kernel/locking/lockdep.c +4 -33
@@ -2625,8 +2625,8 @@ out_bug:struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS ]; static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); -int nr_chain_hlocks;static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS ]; +unsigned int nr_chain_hlocks;struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i) {
@@ -4772,36 +4772,23 @@ static void remove_class_from_lock_chain(struct pending_free *pf, struct lock_class *class) {#ifdef CONFIG_PROVE_LOCKING -struct lock_chain *new_chain; -u64 chain_key;int i;for (i = chain->base; i < chain->base + chain->depth; i++) {if (chain_hlocks[i] != class - lock_classes)continue ; -/* The code below leaks one chain_hlock[] entry. */ -if (--chain->depth >0 ) { -memmove (&chain_hlocks[i], &chain_hlocks[i +1 ], - (chain->base + chain->depth - i) * -sizeof (chain_hlocks[0 ])); - }/* * Each lock class occurs at most once in a lock chain so once * we found a match we can break out of this loop. */ - goto recalc; + goto free_lock_chain; }/* Since the chain has not been modified, return. */ return ; -recalc: - chain_key =INITIAL_CHAIN_KEY ; -for (i = chain->base; i < chain->base + chain->depth; i++) - chain_key =iterate_chain_key (chain_key, chain_hlocks[i]); -if (chain->depth && chain->chain_key == chain_key) -return ; +free_lock_chain:/* Overwrite the chain key for concurrent RCU readers. */ -WRITE_ONCE (chain->chain_key, chain_key); +WRITE_ONCE (chain->chain_key,INITIAL_CHAIN_KEY );dec_chains (chain->irq_context);/*
@@ -4810,22 +4797,6 @@ recalc:*/ hlist_del_rcu (&chain->entry);__set_bit (chain - lock_chains, pf->lock_chains_being_freed); -if (chain->depth ==0 ) -return ; -/* -* If the modified lock chain matches an existing lock chain, drop -* the modified lock chain. -*/ -if (lookup_chain_cache (chain_key)) -return ; - new_chain =alloc_lock_chain (); -if (WARN_ON_ONCE (!new_chain)) { -debug_locks_off (); -return ; - } - *new_chain = *chain; -hlist_add_head_rcu (&new_chain->entry,chainhashentry (chain_key)); -inc_chains (new_chain->irq_context);#endif }
kernel/locking/lockdep_internals.h +2 -2
@@ -134,14 +134,14 @@ extern unsigned long nr_zapped_classes;extern unsigned long nr_list_entries;long lockdep_next_lockchain (long i);unsigned long lock_chain_count (void ); -extern int nr_chain_hlocks;extern unsigned long nr_stack_trace_entries;extern unsigned int nr_hardirq_chains;extern unsigned int nr_softirq_chains;extern unsigned int nr_process_chains; -extern unsigned int max_lockdep_depth; +extern unsigned int nr_chain_hlocks; +extern unsigned int max_lockdep_depth;extern unsigned int max_bfs_queue_depth;#ifdef CONFIG_PROVE_LOCKING
kernel/locking/lockdep_proc.c +1 -1
@@ -278,7 +278,7 @@ static int lockdep_stats_show(struct seq_file *m, void *v)#ifdef CONFIG_PROVE_LOCKING seq_printf (m," dependency chains: %11lu [max: %lu]\n" ,lock_chain_count (),MAX_LOCKDEP_CHAINS ); -seq_printf (m," dependency chain hlocks: %11d [max: %lu]\n" , +seq_printf (m," dependency chain hlocks: %11u [max: %lu]\n" , nr_chain_hlocks,MAX_LOCKDEP_CHAIN_HLOCKS );#endif
Waiman Long
reviewerPATCH v6 5/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 | 4 ++++ 3 files changed, 7 insertions(+)
kernel/locking/lockdep.c +2 -0
@@ -2626,6 +2626,7 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS ]; static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS ]; +unsigned long nr_zapped_lock_chains;unsigned int nr_chain_hlocks;struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i)
@@ -4797,6 +4798,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,*/ hlist_del_rcu (&chain->entry);__set_bit (chain - lock_chains, pf->lock_chains_being_freed); + nr_zapped_lock_chains++;#endif }
kernel/locking/lockdep_internals.h +1 -0
@@ -131,6 +131,7 @@ struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i);extern unsigned long nr_lock_classes;extern unsigned long nr_zapped_classes; +extern unsigned long nr_zapped_lock_chains;extern unsigned long nr_list_entries;long lockdep_next_lockchain (long i);unsigned long lock_chain_count (void );
kernel/locking/lockdep_proc.c +4 -0
@@ -349,6 +349,10 @@ static int lockdep_stats_show(struct seq_file *m, void *v)seq_puts (m,"\n" );seq_printf (m," zapped classes: %11lu\n" , nr_zapped_classes); +#ifdef CONFIG_PROVE_LOCKING +seq_printf (m," zapped lock chains: %11lu\n" , + nr_zapped_lock_chains); +#endif return 0 ; }
Signature · 1 line
2.18.1
[tip: locking/core] locking/lockdep: Track number of zapped lock chains
The following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 797b82eb906eeba24dcd6e9ab92faef01fc684cb Gitweb: https://git.kernel.org/tip/797b82eb906eeba24dcd6e9ab92faef01fc684cb Author: Waiman Long <[email protected]> AuthorDate: Thu, 06 Feb 2020 10:24:07 -05:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Tue, 11 Feb 2020 13:10:51 +01:00
locking/lockdep: Track number of zapped lock chains
Add a new counter nr_zapped_lock_chains to track the number lock chains that have been removed.
--- kernel/locking/lockdep.c | 2 ++ kernel/locking/lockdep_internals.h | 1 + kernel/locking/lockdep_proc.c | 4 ++++ 3 files changed, 7 insertions(+)
kernel/locking/lockdep.c +2 -0
@@ -2626,6 +2626,7 @@ out_bug:struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS ]; static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS ]; +unsigned long nr_zapped_lock_chains;unsigned int nr_chain_hlocks;struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i)
@@ -4797,6 +4798,7 @@ free_lock_chain:*/ 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
@@ -131,6 +131,7 @@ struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i);extern unsigned long nr_lock_classes;extern unsigned long nr_zapped_classes; +extern unsigned long nr_zapped_lock_chains;extern unsigned long nr_list_entries;long lockdep_next_lockchain (long i);unsigned long lock_chain_count (void );
kernel/locking/lockdep_proc.c +4 -0
@@ -349,6 +349,10 @@ static int lockdep_stats_show(struct seq_file *m, void *v)seq_puts (m,"\n" );seq_printf (m," zapped classes: %11lu\n" , nr_zapped_classes); +#ifdef CONFIG_PROVE_LOCKING +seq_printf (m," zapped lock chains: %11lu\n" , + nr_zapped_lock_chains); +#endif return 0 ; }
Waiman Long
reviewerPATCH v6 6/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 chain_hlocks entries are put into bucketed lists (MAX_CHAIN_BUCKETS) of chain blocks. Bucket 0 is the variable size bucket which houses chain blocks of size larger than MAX_CHAIN_BUCKETS sorted in decreasing size order. Initially, the whole array is in one chain block (the primordial chain block) in bucket 0.
The minimum size of a chain block is 2 chain_hlocks entries. That will be the minimum allocation size. In other word, allocation requests for one chain_hlocks entry will cause 2-entry block to be returned and hence 1 entry will be wasted.
Allocation requests for the chain_hlocks are fulfilled first by looking for chain block of matching size. If not found, the first chain block from bucket[0] (the largest one) is split. That can cause hlock entries fragmentation and reduce allocation efficiency if a chain block of size > MAX_CHAIN_BUCKETS is ever zapped and put back to after the primordial chain block. So the MAX_CHAIN_BUCKETS must be large enough that this should seldom happen.
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 running out of chain_hlocks entries as long as the total number of outstanding lock classes at any time remain within a reasonable limit.
Two new tracking counters, nr_free_chain_hlocks & nr_large_chain_blocks, are added to track the total number of chain_hlocks entries in the free bucketed lists and the number of large chain blocks in buckets[0] respectively. The nr_free_chain_hlocks replaces nr_chain_hlocks.
The nr_large_chain_blocks counter enables to see if we should increase the number of buckets (MAX_CHAIN_BUCKETS) available so as to avoid to avoid the fragmentation problem in bucket[0].
An internal nfsd test that ran for more than an hour and kept on loading and unloading kernel modules could cause the following message to be displayed.
[ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!
The patched kernel was able to complete the test with a lot of free chain_hlocks entries to spare:
# cat /proc/lockdep_stats
:
dependency chains: 18867 [max: 65536]
dependency chain hlocks: 74926 [max: 327680]
dependency chain hlocks lost: 0
:
zapped classes: 1541
zapped lock chains: 56765
large chain blocks: 1By changing MAX_CHAIN_BUCKETS to 3 and add a counter for the size of the largest chain block. The system still worked and We got the following lockdep_stats data:
dependency chains: 18601 [max: 65536]
dependency chain hlocks used: 73133 [max: 327680]
dependency chain hlocks lost: 0
: zapped classes: 1541 zapped lock chains: 56702 large chain blocks: 45165 large chain block size: 20165
By running the test again, I was indeed able to cause chain_hlocks entries to get lost:
dependency chain hlocks used: 74806 [max: 327680]
dependency chain hlocks lost: 575
:
large chain blocks: 48737
large chain block size: 7
Due to the fragmentation, it is possible that the "MAX_LOCKDEP_CHAIN_HLOCKS too low!" error can happen even if a lot of of chain_hlocks entries appear to be free.
Fortunately, a MAX_CHAIN_BUCKETS value of 16 should be big enough that few variable sized chain blocks, other than the initial one, should ever be present in bucket 0.
--- kernel/locking/lockdep.c | 255 +++++++++++++++++++++++++++-- kernel/locking/lockdep_internals.h | 4 +- kernel/locking/lockdep_proc.c | 12 +- 3 files changed, 256 insertions(+), 15 deletions(-)
kernel/locking/lockdep.c +244 -11
@@ -1071,13 +1071,15 @@ static inline void check_data_structures(void) { }#endif /* CONFIG_DEBUG_LOCKDEP */ +static void init_chain_block_buckets (void ); +/* * Initialize the lock_classes[] array elements, the free_lock_classes list * and also the delayed_free structure. */ static void init_data_structures_once (void ) { -static bool ds_initialized, rcu_head_initialized; +static bool __read_mostly ds_initialized, rcu_head_initialized;int i;if (likely (rcu_head_initialized))
@@ -1101,6 +1103,7 @@ static void init_data_structures_once(void)INIT_LIST_HEAD (&lock_classes[i].locks_after);INIT_LIST_HEAD (&lock_classes[i].locks_before); } +init_chain_block_buckets (); }static inline struct hlist_head *keyhashentry (const struct lock_class_key *key)
@@ -2627,7 +2630,234 @@ struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS ];unsigned long nr_zapped_lock_chains; -unsigned int nr_chain_hlocks; +unsigned int nr_free_chain_hlocks;/* Free chain_hlocks in buckets */ +unsigned int nr_lost_chain_hlocks;/* Lost chain_hlocks */ +unsigned int nr_large_chain_blocks;/* size > MAX_CHAIN_BUCKETS */ + +/* +* The first 2 chain_hlocks entries in the chain block in the bucket +* list contains the following meta data: +* +* entry[0]: +* Bit 15 - always set to 1 (it is not a class index) +* Bits 0-14 - upper 15 bits of the next block index +* entry[1] - lower 16 bits of next block index +* +* A next block index of all 1 bits means it is the end of the list. +* +* On the unsized bucket (bucket-0), the 3rd and 4th entries contain +* the chain block size: +* +* entry[2] - upper 16 bits of the chain block size +* entry[3] - lower 16 bits of the chain block size +*/ +#define MAX_CHAIN_BUCKETS 16 +#define CHAIN_BLK_FLAG (1U << 15) +#define CHAIN_BLK_LIST_END 0xFFFFU + +static int chain_block_buckets[MAX_CHAIN_BUCKETS ]; + +static inline int size_to_bucket (int size) +{ +if (size >MAX_CHAIN_BUCKETS ) +return 0 ; + +return size -1 ; +} + +/* +* Iterate all the chain blocks in a bucket. +*/ +#define for_each_chain_block (bucket, prev, curr) \ + for ((prev) = -1, (curr) = chain_block_buckets[bucket]; \ + (curr) >= 0; \ + (prev) = (curr), (curr) = chain_block_next(curr)) + +/* +* next block or -1 +*/ +static inline int chain_block_next (int offset) +{ +int next = chain_hlocks[offset]; + +WARN_ON_ONCE (!(next &CHAIN_BLK_FLAG )); + +if (next ==CHAIN_BLK_LIST_END ) +return -1 ; + + next &= ~CHAIN_BLK_FLAG ; + next <<=16 ; + next |= chain_hlocks[offset +1 ]; + +return next; +} + +/* +* bucket-0 only +*/ +static inline int chain_block_size (int offset) +{ +return (chain_hlocks[offset +2 ] <<16 ) | chain_hlocks[offset +3 ]; +} + +static inline void init_chain_block (int offset,int next,int bucket,int size) +{ + chain_hlocks[offset] = (next >>16 ) |CHAIN_BLK_FLAG ; + chain_hlocks[offset +1 ] = (u16 )next; + +if (size && !bucket) { + chain_hlocks[offset +2 ] = size >>16 ; + chain_hlocks[offset +3 ] = (u16 )size; + } +} + +static inline void add_chain_block (int offset,int size) +{ +int bucket =size_to_bucket (size); +int next = chain_block_buckets[bucket]; +int prev, curr; + +if (unlikely (size <2 )) { +/* +* We can't store single entries on the freelist. Leak them. +* +* One possible way out would be to uniquely mark them, other +* than with CHAIN_BLK_FLAG, such that we can recover them when +* the block before it is re-added. +*/ +if (size) + nr_lost_chain_hlocks++; +return ; + } + + nr_free_chain_hlocks += size; +if (!bucket) { + nr_large_chain_blocks++; + +if (unlikely (next >=0 )) { +/* +* Variable sized, sort large to small. +*/ +for_each_chain_block (0 , prev, curr) { +if (size >=chain_block_size (curr)) +break ; + } +init_chain_block (offset, curr,0 , size); +if (prev <0 ) + chain_block_buckets[0 ] = offset; +else +init_chain_block (prev, offset,0 ,0 ); +return ; + } + } +/* +* Fixed size or bucket[0] empty, add to head. +*/ +init_chain_block (offset, next, bucket, size); + chain_block_buckets[bucket] = offset; +} + +/* +* Only the first block in the list can be deleted. +* +* For the variable size bucket[0], the first block (the largest one) is +* returned, broken up and put back into the pool. So if a chain block of +* length > MAX_CHAIN_BUCKETS is ever used and zapped, it will just be +* queued up after the primordial chain block and never be used until the +* hlock entries in the primordial chain block is almost used up. That +* causes fragmentation and reduce allocation efficiency. That can be +* monitored by looking at the "large chain blocks" number in lockdep_stats. +*/ +static inline void del_chain_block (int bucket,int size,int next) +{ + nr_free_chain_hlocks -= size; + chain_block_buckets[bucket] = next; + +if (!bucket) + nr_large_chain_blocks--; +} + +static void init_chain_block_buckets (void ) +{ +int i; + +for (i =0 ; i <MAX_CHAIN_BUCKETS ; i++) + chain_block_buckets[i] =-1 ; + +add_chain_block (0 ,ARRAY_SIZE (chain_hlocks)); +} + +/* +* Return offset of a chain block of the right size or -1 if not found. +* +* Fairly simple worst-fit allocator with the addition of a number of size +* specific free lists. +*/ +static int alloc_chain_hlocks (int req) +{ +int bucket, curr, size; + +/* +* We rely on the MSB to act as an escape bit to denote freelist +* pointers. Make sure this bit isn't set in 'normal' class_idx usage. +*/ +BUILD_BUG_ON ((MAX_LOCKDEP_KEYS -1 ) &CHAIN_BLK_FLAG ); + +init_data_structures_once (); + +if (nr_free_chain_hlocks < req) +return -1 ; + +/* +* We require a minimum of 2 (u16) entries to encode a freelist +* 'pointer'. +*/ + req =max (req,2 ); + bucket =size_to_bucket (req); + curr = chain_block_buckets[bucket]; + +if (bucket && (curr >=0 )) { +del_chain_block (bucket, req,chain_block_next (curr)); +return curr; + }else if (bucket) { +/* Try bucket 0 */ + curr = chain_block_buckets[0 ]; + } + +/* +* The variable sized freelist is sorted by size; the first entry is +* the largest. Use it if it fits. +*/ +if (curr >=0 ) { + size =chain_block_size (curr); +if (likely (size >= req)) { +del_chain_block (0 , size,chain_block_next (curr)); +add_chain_block (curr + req, size - req); +return curr; + } + } + +/* +* Last resort, split a block in a larger sized bucket. +*/ +for (size =MAX_CHAIN_BUCKETS ; size > req; size--) { + bucket =size_to_bucket (size); + curr = chain_block_buckets[bucket]; +if (curr <0 ) +continue ; + +del_chain_block (bucket, size,chain_block_next (curr)); +add_chain_block (curr + req, size - req); +return curr; + } + +return -1 ; +} + +static inline void free_chain_hlocks (int base,int size) +{ +add_chain_block (base,max (size,2 )); +}struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i) {
@@ -2828,15 +3058,8 @@ static inline int add_chain_cache(struct task_struct *curr,BUILD_BUG_ON ((1UL <<6 ) <=ARRAY_SIZE (curr->held_locks));BUILD_BUG_ON ((1UL <<8 *sizeof (chain_hlocks[0 ])) <=ARRAY_SIZE (lock_classes)); -if (likely (nr_chain_hlocks + chain->depth <=MAX_LOCKDEP_CHAIN_HLOCKS )) { - chain->base = nr_chain_hlocks; -for (j =0 ; j < chain->depth -1 ; j++, i++) { -int lock_id = curr->held_locks[i].class_idx; - chain_hlocks[chain->base + j] = lock_id; - } - chain_hlocks[chain->base + j] = class - lock_classes; - nr_chain_hlocks += chain->depth; - }else { + j =alloc_chain_hlocks (chain->depth); +if (j <0 ) {if (!debug_locks_off_graph_unlock ())return 0 ;
@@ -2845,6 +3068,13 @@ static inline int add_chain_cache(struct task_struct *curr,return 0 ; } + chain->base = j; +for (j =0 ; j < chain->depth -1 ; j++, i++) { +int lock_id = curr->held_locks[i].class_idx; + + chain_hlocks[chain->base + j] = lock_id; + } + chain_hlocks[chain->base + j] = class - lock_classes;hlist_add_head_rcu (&chain->entry, hash_head);debug_atomic_inc (chain_lookup_misses);inc_chains (chain->irq_context);
@@ -2991,6 +3221,8 @@ static inline int validate_chain(struct task_struct *curr, {return 1 ; } + +static void init_chain_block_buckets (void ) { }#endif /* CONFIG_PROVE_LOCKING */ /*
@@ -4788,6 +5020,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,return ; free_lock_chain: +free_chain_hlocks (chain->base, chain->depth);/* Overwrite the chain key for concurrent RCU readers. */ WRITE_ONCE (chain->chain_key,INITIAL_CHAIN_KEY );dec_chains (chain->irq_context);
kernel/locking/lockdep_internals.h +3 -1
@@ -140,7 +140,9 @@ extern unsigned long nr_stack_trace_entries;extern unsigned int nr_hardirq_chains;extern unsigned int nr_softirq_chains;extern unsigned int nr_process_chains; -extern unsigned int nr_chain_hlocks; +extern unsigned int nr_free_chain_hlocks; +extern unsigned int nr_lost_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 +9 -3
@@ -137,7 +137,7 @@ static int lc_show(struct seq_file *m, void *v) };if (v ==SEQ_START_TOKEN ) { -if (nr_chain_hlocks >MAX_LOCKDEP_CHAIN_HLOCKS ) +if (!nr_free_chain_hlocks)seq_printf (m,"(buggered) " );seq_printf (m,"all lock chains:\n" );return 0 ;
@@ -278,8 +278,12 @@ static int lockdep_stats_show(struct seq_file *m, void *v)#ifdef CONFIG_PROVE_LOCKING seq_printf (m," dependency chains: %11lu [max: %lu]\n" ,lock_chain_count (),MAX_LOCKDEP_CHAINS ); -seq_printf (m," dependency chain hlocks: %11u [max: %lu]\n" , - nr_chain_hlocks,MAX_LOCKDEP_CHAIN_HLOCKS ); +seq_printf (m," dependency chain hlocks used: %11lu [max: %lu]\n" , +MAX_LOCKDEP_CHAIN_HLOCKS - + (nr_free_chain_hlocks + nr_lost_chain_hlocks), +MAX_LOCKDEP_CHAIN_HLOCKS ); +seq_printf (m," dependency chain hlocks lost: %11u\n" , + nr_lost_chain_hlocks);#endif #ifdef CONFIG_TRACE_IRQFLAGS
@@ -352,6 +356,8 @@ static int lockdep_stats_show(struct seq_file *m, void *v)#ifdef CONFIG_PROVE_LOCKING seq_printf (m," zapped lock chains: %11lu\n" , nr_zapped_lock_chains); +seq_printf (m," large chain blocks: %11u\n" , + nr_large_chain_blocks);#endif return 0 ; }
Signature · 1 line
2.18.1
Peter Zijlstra
maintainerRe: [PATCH v6 6/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 19 lines · Waiman Long
kernel/locking/lockdep.c +18
-0+#define for_each_chain_block (bucket, prev, curr) \ + for ((prev) = -1, (curr) = chain_block_buckets[bucket]; \ + (curr) >= 0; \ + (prev) = (curr), (curr) = chain_block_next(curr)) +static inline void add_chain_block (int offset,int size) +{ +int bucket =size_to_bucket (size); +int next = chain_block_buckets[bucket]; +int prev, curr; + +if (unlikely (size <2 )) { +/* +* We can't store single entries on the freelist. Leak them. +* +* One possible way out would be to uniquely mark them, other +* than with CHAIN_BLK_FLAG, such that we can recover them when +* the block before it is re-added. +*/
kernel/locking/lockdep.c struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; · line 2737
Quoted 10 lines
kernel/locking/lockdep.c +10
-0+if (size) + nr_lost_chain_hlocks++; +return ; + } + + nr_free_chain_hlocks += size; +if (!bucket) { + nr_large_chain_blocks++; + +if (unlikely (next >=0 )) {
I was surprised by this condition..
kernel/locking/lockdep.c struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; · line 2744
Quoted 7 lines
kernel/locking/lockdep.c +7
-0+/* +* Variable sized, sort large to small. +*/ +for_each_chain_block (0 , prev, curr) { +if (size >=chain_block_size (curr)) +break ; + }
Because if that is not so, then here:
@curr == @next @prev == -1
kernel/locking/lockdep.c struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; · line 2745
Quoted 1 line
kernel/locking/lockdep.c +1
-0+init_chain_block (offset, curr,0 , size);
and this will be identical to:
init_chain_block(offset, next, bucket, size);
kernel/locking/lockdep.c struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; · line 2749
Quoted 4 lines
kernel/locking/lockdep.c +4
-0+if (prev <0 ) + chain_block_buckets[0 ] = offset; +else +init_chain_block (prev, offset,0 ,0 );
and this will be:
chain_block_buckets[bucket] = offset;
Or am I missing something?
Quoted 9 lines
kernel/locking/lockdep.c +9
-0+return ; + } + } +/* +* Fixed size or bucket[0] empty, add to head. +*/ +init_chain_block (offset, next, bucket, size); + chain_block_buckets[bucket] = offset; +}
Waiman Long
reviewerRe: [PATCH v6 6/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 22 lines · Peter Zijlstra
Quoted 21 lines · Waiman Long
kernel/locking/lockdep.c +21
-0+#define for_each_chain_block (bucket, prev, curr) \ + for ((prev) = -1, (curr) = chain_block_buckets[bucket]; \ + (curr) >= 0; \ + (prev) = (curr), (curr) = chain_block_next(curr)) +static inline void add_chain_block (int offset,int size) +{ +int bucket =size_to_bucket (size); +int next = chain_block_buckets[bucket]; +int prev, curr; + +if (unlikely (size <2 )) { +/* +* We can't store single entries on the freelist. Leak them. +* +* One possible way out would be to uniquely mark them, other +* than with CHAIN_BLK_FLAG, such that we can recover them when +* the block before it is re-added. +*/ +if (size) + nr_lost_chain_hlocks++; +return ;
Quoted 8 lines
kernel/locking/lockdep.c struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; · line 2737
Quoted 7 lines
kernel/locking/lockdep.c +7
-0+ } + + nr_free_chain_hlocks += size; +if (!bucket) { + nr_large_chain_blocks++; + +if (unlikely (next >=0 )) {I was surprised by this condition..
Yes, this condition is optional and the code will still work as expected without that. I added that so that for the common case where there is only 1 chain block in block 0 and it gets deleted and added repetitively, it will go to the simpler code path instead of the more complicated one.
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH v6 6/6] locking/lockdep: Reuse freed chain_hlocks entries
In reply to Waiman LongQuoted 20 lines · Waiman Long
kernel/locking/lockdep.c +20
-0+static int alloc_chain_hlocks (int req) +{ +int bucket, curr, size; + +/* +* We rely on the MSB to act as an escape bit to denote freelist +* pointers. Make sure this bit isn't set in 'normal' class_idx usage. +*/ +BUILD_BUG_ON ((MAX_LOCKDEP_KEYS -1 ) &CHAIN_BLK_FLAG ); + +init_data_structures_once (); + +if (nr_free_chain_hlocks < req) +return -1 ; + +/* +* We require a minimum of 2 (u16) entries to encode a freelist +* 'pointer'. +*/ + req =max (req,2 );
kernel/locking/lockdep.c struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; · line 2825
Quoted 10 lines
kernel/locking/lockdep.c +10
-0+ bucket =size_to_bucket (req); + curr = chain_block_buckets[bucket]; + +if (bucket && (curr >=0 )) { +del_chain_block (bucket, req,chain_block_next (curr)); +return curr; + }else if (bucket) { +/* Try bucket 0 */ + curr = chain_block_buckets[0 ]; + }
if (bucket) {
if (curr >= 0) {
del_chain_block(bucket, req, chain_block_next(curr));
return curr;
}
/* Try bucket 0 */
curr = chain_block_bucket[0];
}reads much easier IMO.
Quoted 29 lines
kernel/locking/lockdep.c +29
-0+/* +* The variable sized freelist is sorted by size; the first entry is +* the largest. Use it if it fits. +*/ +if (curr >=0 ) { + size =chain_block_size (curr); +if (likely (size >= req)) { +del_chain_block (0 , size,chain_block_next (curr)); +add_chain_block (curr + req, size - req); +return curr; + } + } + +/* +* Last resort, split a block in a larger sized bucket. +*/ +for (size =MAX_CHAIN_BUCKETS ; size > req; size--) { + bucket =size_to_bucket (size); + curr = chain_block_buckets[bucket]; +if (curr <0 ) +continue ; + +del_chain_block (bucket, size,chain_block_next (curr)); +add_chain_block (curr + req, size - req); +return curr; + } + +return -1 ; +}
Waiman Long
reviewerRe: [PATCH v6 6/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 40 lines · Peter Zijlstra
Quoted 20 lines · Waiman Long
kernel/locking/lockdep.c +20
-0+static int alloc_chain_hlocks (int req) +{ +int bucket, curr, size; + +/* +* We rely on the MSB to act as an escape bit to denote freelist +* pointers. Make sure this bit isn't set in 'normal' class_idx usage. +*/ +BUILD_BUG_ON ((MAX_LOCKDEP_KEYS -1 ) &CHAIN_BLK_FLAG ); + +init_data_structures_once (); + +if (nr_free_chain_hlocks < req) +return -1 ; + +/* +* We require a minimum of 2 (u16) entries to encode a freelist +* 'pointer'. +*/ + req =max (req,2 );kernel/locking/lockdep.c struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; · line 2825
Quoted 10 lines
kernel/locking/lockdep.c +10
-0+ bucket =size_to_bucket (req); + curr = chain_block_buckets[bucket]; + +if (bucket && (curr >=0 )) { +del_chain_block (bucket, req,chain_block_next (curr)); +return curr; + }else if (bucket) { +/* Try bucket 0 */ + curr = chain_block_buckets[0 ]; + }if (bucket) { if (curr >= 0) { del_chain_block(bucket, req, chain_block_next(curr)); return curr; } /* Try bucket 0 */ curr = chain_block_bucket[0]; }
Quoted 1 line
reads much easier IMO.
Yes, that is simpler. I can send out an updated patch if you want, or you can apply the change when you pull the patch.
Thanks,
Longman
Peter Zijlstra
maintainerRe: [PATCH v6 6/6] locking/lockdep: Reuse freed chain_hlocks entries
Quoted 41 lines · Waiman Long
Quoted 40 lines · Peter Zijlstra
Quoted 20 lines · Waiman Long
kernel/locking/lockdep.c +20
-0+static int alloc_chain_hlocks (int req) +{ +int bucket, curr, size; + +/* +* We rely on the MSB to act as an escape bit to denote freelist +* pointers. Make sure this bit isn't set in 'normal' class_idx usage. +*/ +BUILD_BUG_ON ((MAX_LOCKDEP_KEYS -1 ) &CHAIN_BLK_FLAG ); + +init_data_structures_once (); + +if (nr_free_chain_hlocks < req) +return -1 ; + +/* +* We require a minimum of 2 (u16) entries to encode a freelist +* 'pointer'. +*/ + req =max (req,2 );kernel/locking/lockdep.c struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; · line 2825
Quoted 10 lines
kernel/locking/lockdep.c +10
-0+ bucket =size_to_bucket (req); + curr = chain_block_buckets[bucket]; + +if (bucket && (curr >=0 )) { +del_chain_block (bucket, req,chain_block_next (curr)); +return curr; + }else if (bucket) { +/* Try bucket 0 */ + curr = chain_block_buckets[0 ]; + }if (bucket) { if (curr >= 0) { del_chain_block(bucket, req, chain_block_next(curr)); return curr; } /* Try bucket 0 */ curr = chain_block_bucket[0]; }
Quoted 4 lines
Quoted 1 line
reads much easier IMO.
Yes, that is simpler. I can send out an updated patch if you want, or you can apply the change when you pull the patch.
I'll frob it. Thanks!
[tip: locking/core] locking/lockdep: Reuse freed chain_hlocks entries
In reply to Waiman LongThe following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 810507fe6fd5ff3de429121adff49523fabb643a Gitweb: https://git.kernel.org/tip/810507fe6fd5ff3de429121adff49523fabb643a Author: Waiman Long <[email protected]> AuthorDate: Thu, 06 Feb 2020 10:24:08 -05:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Tue, 11 Feb 2020 13:10:52 +01:00
locking/lockdep: Reuse freed chain_hlocks entries
Once a lock class is zapped, all the lock chains that include the zapped class are essentially useless. The lock_chain structure itself can be reused, but not the corresponding chain_hlocks[] entries. Over time, we will run out of chain_hlocks entries while there are still plenty of other lockdep array entries available.
To fix this imbalance, we have to make chain_hlocks entries reusable just like the others. As the freed chain_hlocks entries are in blocks of various lengths. A simple bitmap like the one used in the other reusable lockdep arrays isn't applicable. Instead the chain_hlocks entries are put into bucketed lists (MAX_CHAIN_BUCKETS) of chain blocks. Bucket 0 is the variable size bucket which houses chain blocks of size larger than MAX_CHAIN_BUCKETS sorted in decreasing size order. Initially, the whole array is in one chain block (the primordial chain block) in bucket 0.
The minimum size of a chain block is 2 chain_hlocks entries. That will be the minimum allocation size. In other word, allocation requests for one chain_hlocks entry will cause 2-entry block to be returned and hence 1 entry will be wasted.
Allocation requests for the chain_hlocks are fulfilled first by looking for chain block of matching size. If not found, the first chain block from bucket[0] (the largest one) is split. That can cause hlock entries fragmentation and reduce allocation efficiency if a chain block of size > MAX_CHAIN_BUCKETS is ever zapped and put back to after the primordial chain block. So the MAX_CHAIN_BUCKETS must be large enough that this should seldom happen.
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 running out of chain_hlocks entries as long as the total number of outstanding lock classes at any time remain within a reasonable limit.
Two new tracking counters, nr_free_chain_hlocks & nr_large_chain_blocks, are added to track the total number of chain_hlocks entries in the free bucketed lists and the number of large chain blocks in buckets[0] respectively. The nr_free_chain_hlocks replaces nr_chain_hlocks.
The nr_large_chain_blocks counter enables to see if we should increase the number of buckets (MAX_CHAIN_BUCKETS) available so as to avoid to avoid the fragmentation problem in bucket[0].
An internal nfsd test that ran for more than an hour and kept on loading and unloading kernel modules could cause the following message to be displayed.
[ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!
The patched kernel was able to complete the test with a lot of free chain_hlocks entries to spare:
# cat /proc/lockdep_stats
:
dependency chains: 18867 [max: 65536]
dependency chain hlocks: 74926 [max: 327680]
dependency chain hlocks lost: 0
:
zapped classes: 1541
zapped lock chains: 56765
large chain blocks: 1By changing MAX_CHAIN_BUCKETS to 3 and add a counter for the size of the largest chain block. The system still worked and We got the following lockdep_stats data:
dependency chains: 18601 [max: 65536]
dependency chain hlocks used: 73133 [max: 327680]
dependency chain hlocks lost: 0
: zapped classes: 1541 zapped lock chains: 56702 large chain blocks: 45165 large chain block size: 20165
By running the test again, I was indeed able to cause chain_hlocks entries to get lost:
dependency chain hlocks used: 74806 [max: 327680]
dependency chain hlocks lost: 575
:
large chain blocks: 48737
large chain block size: 7
Due to the fragmentation, it is possible that the "MAX_LOCKDEP_CHAIN_HLOCKS too low!" error can happen even if a lot of of chain_hlocks entries appear to be free.
Fortunately, a MAX_CHAIN_BUCKETS value of 16 should be big enough that few variable sized chain blocks, other than the initial one, should ever be present in bucket 0.
--- kernel/locking/lockdep.c | 254 ++++++++++++++++++++++++++-- kernel/locking/lockdep_internals.h | 4 +- kernel/locking/lockdep_proc.c | 12 +- 3 files changed, 255 insertions(+), 15 deletions(-)
kernel/locking/lockdep.c +243 -11
@@ -1071,13 +1071,15 @@ static inline void check_data_structures(void) { }#endif /* CONFIG_DEBUG_LOCKDEP */ +static void init_chain_block_buckets (void ); +/* * Initialize the lock_classes[] array elements, the free_lock_classes list * and also the delayed_free structure. */ static void init_data_structures_once (void ) { -static bool ds_initialized, rcu_head_initialized; +static bool __read_mostly ds_initialized, rcu_head_initialized;int i;if (likely (rcu_head_initialized))
@@ -1101,6 +1103,7 @@ static void init_data_structures_once(void)INIT_LIST_HEAD (&lock_classes[i].locks_after);INIT_LIST_HEAD (&lock_classes[i].locks_before); } +init_chain_block_buckets (); }static inline struct hlist_head *keyhashentry (const struct lock_class_key *key)
@@ -2627,7 +2630,233 @@ struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS ];unsigned long nr_zapped_lock_chains; -unsigned int nr_chain_hlocks; +unsigned int nr_free_chain_hlocks;/* Free chain_hlocks in buckets */ +unsigned int nr_lost_chain_hlocks;/* Lost chain_hlocks */ +unsigned int nr_large_chain_blocks;/* size > MAX_CHAIN_BUCKETS */ + +/* +* The first 2 chain_hlocks entries in the chain block in the bucket +* list contains the following meta data: +* +* entry[0]: +* Bit 15 - always set to 1 (it is not a class index) +* Bits 0-14 - upper 15 bits of the next block index +* entry[1] - lower 16 bits of next block index +* +* A next block index of all 1 bits means it is the end of the list. +* +* On the unsized bucket (bucket-0), the 3rd and 4th entries contain +* the chain block size: +* +* entry[2] - upper 16 bits of the chain block size +* entry[3] - lower 16 bits of the chain block size +*/ +#define MAX_CHAIN_BUCKETS 16 +#define CHAIN_BLK_FLAG (1U << 15) +#define CHAIN_BLK_LIST_END 0xFFFFU + +static int chain_block_buckets[MAX_CHAIN_BUCKETS ]; + +static inline int size_to_bucket (int size) +{ +if (size >MAX_CHAIN_BUCKETS ) +return 0 ; + +return size -1 ; +} + +/* +* Iterate all the chain blocks in a bucket. +*/ +#define for_each_chain_block (bucket, prev, curr) \ + for ((prev) = -1, (curr) = chain_block_buckets[bucket]; \ + (curr) >= 0; \ + (prev) = (curr), (curr) = chain_block_next(curr)) + +/* +* next block or -1 +*/ +static inline int chain_block_next (int offset) +{ +int next = chain_hlocks[offset]; + +WARN_ON_ONCE (!(next &CHAIN_BLK_FLAG )); + +if (next ==CHAIN_BLK_LIST_END ) +return -1 ; + + next &= ~CHAIN_BLK_FLAG ; + next <<=16 ; + next |= chain_hlocks[offset +1 ]; + +return next; +} + +/* +* bucket-0 only +*/ +static inline int chain_block_size (int offset) +{ +return (chain_hlocks[offset +2 ] <<16 ) | chain_hlocks[offset +3 ]; +} + +static inline void init_chain_block (int offset,int next,int bucket,int size) +{ + chain_hlocks[offset] = (next >>16 ) |CHAIN_BLK_FLAG ; + chain_hlocks[offset +1 ] = (u16 )next; + +if (size && !bucket) { + chain_hlocks[offset +2 ] = size >>16 ; + chain_hlocks[offset +3 ] = (u16 )size; + } +} + +static inline void add_chain_block (int offset,int size) +{ +int bucket =size_to_bucket (size); +int next = chain_block_buckets[bucket]; +int prev, curr; + +if (unlikely (size <2 )) { +/* +* We can't store single entries on the freelist. Leak them. +* +* One possible way out would be to uniquely mark them, other +* than with CHAIN_BLK_FLAG, such that we can recover them when +* the block before it is re-added. +*/ +if (size) + nr_lost_chain_hlocks++; +return ; + } + + nr_free_chain_hlocks += size; +if (!bucket) { + nr_large_chain_blocks++; + +/* +* Variable sized, sort large to small. +*/ +for_each_chain_block (0 , prev, curr) { +if (size >=chain_block_size (curr)) +break ; + } +init_chain_block (offset, curr,0 , size); +if (prev <0 ) + chain_block_buckets[0 ] = offset; +else +init_chain_block (prev, offset,0 ,0 ); +return ; + } +/* +* Fixed size, add to head. +*/ +init_chain_block (offset, next, bucket, size); + chain_block_buckets[bucket] = offset; +} + +/* +* Only the first block in the list can be deleted. +* +* For the variable size bucket[0], the first block (the largest one) is +* returned, broken up and put back into the pool. So if a chain block of +* length > MAX_CHAIN_BUCKETS is ever used and zapped, it will just be +* queued up after the primordial chain block and never be used until the +* hlock entries in the primordial chain block is almost used up. That +* causes fragmentation and reduce allocation efficiency. That can be +* monitored by looking at the "large chain blocks" number in lockdep_stats. +*/ +static inline void del_chain_block (int bucket,int size,int next) +{ + nr_free_chain_hlocks -= size; + chain_block_buckets[bucket] = next; + +if (!bucket) + nr_large_chain_blocks--; +} + +static void init_chain_block_buckets (void ) +{ +int i; + +for (i =0 ; i <MAX_CHAIN_BUCKETS ; i++) + chain_block_buckets[i] =-1 ; + +add_chain_block (0 ,ARRAY_SIZE (chain_hlocks)); +} + +/* +* Return offset of a chain block of the right size or -1 if not found. +* +* Fairly simple worst-fit allocator with the addition of a number of size +* specific free lists. +*/ +static int alloc_chain_hlocks (int req) +{ +int bucket, curr, size; + +/* +* We rely on the MSB to act as an escape bit to denote freelist +* pointers. Make sure this bit isn't set in 'normal' class_idx usage. +*/ +BUILD_BUG_ON ((MAX_LOCKDEP_KEYS -1 ) &CHAIN_BLK_FLAG ); + +init_data_structures_once (); + +if (nr_free_chain_hlocks < req) +return -1 ; + +/* +* We require a minimum of 2 (u16) entries to encode a freelist +* 'pointer'. +*/ + req =max (req,2 ); + bucket =size_to_bucket (req); + curr = chain_block_buckets[bucket]; + +if (bucket) { +if (curr >=0 ) { +del_chain_block (bucket, req,chain_block_next (curr)); +return curr; + } +/* Try bucket 0 */ + curr = chain_block_buckets[0 ]; + } + +/* +* The variable sized freelist is sorted by size; the first entry is +* the largest. Use it if it fits. +*/ +if (curr >=0 ) { + size =chain_block_size (curr); +if (likely (size >= req)) { +del_chain_block (0 , size,chain_block_next (curr)); +add_chain_block (curr + req, size - req); +return curr; + } + } + +/* +* Last resort, split a block in a larger sized bucket. +*/ +for (size =MAX_CHAIN_BUCKETS ; size > req; size--) { + bucket =size_to_bucket (size); + curr = chain_block_buckets[bucket]; +if (curr <0 ) +continue ; + +del_chain_block (bucket, size,chain_block_next (curr)); +add_chain_block (curr + req, size - req); +return curr; + } + +return -1 ; +} + +static inline void free_chain_hlocks (int base,int size) +{ +add_chain_block (base,max (size,2 )); +}struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i) {
@@ -2828,15 +3057,8 @@ static inline int add_chain_cache(struct task_struct *curr,BUILD_BUG_ON ((1UL <<6 ) <=ARRAY_SIZE (curr->held_locks));BUILD_BUG_ON ((1UL <<8 *sizeof (chain_hlocks[0 ])) <=ARRAY_SIZE (lock_classes)); -if (likely (nr_chain_hlocks + chain->depth <=MAX_LOCKDEP_CHAIN_HLOCKS )) { - chain->base = nr_chain_hlocks; -for (j =0 ; j < chain->depth -1 ; j++, i++) { -int lock_id = curr->held_locks[i].class_idx; - chain_hlocks[chain->base + j] = lock_id; - } - chain_hlocks[chain->base + j] = class - lock_classes; - nr_chain_hlocks += chain->depth; - }else { + j =alloc_chain_hlocks (chain->depth); +if (j <0 ) {if (!debug_locks_off_graph_unlock ())return 0 ;
@@ -2845,6 +3067,13 @@ static inline int add_chain_cache(struct task_struct *curr,return 0 ; } + chain->base = j; +for (j =0 ; j < chain->depth -1 ; j++, i++) { +int lock_id = curr->held_locks[i].class_idx; + + chain_hlocks[chain->base + j] = lock_id; + } + chain_hlocks[chain->base + j] = class - lock_classes;hlist_add_head_rcu (&chain->entry, hash_head);debug_atomic_inc (chain_lookup_misses);inc_chains (chain->irq_context);
@@ -2991,6 +3220,8 @@ static inline int validate_chain(struct task_struct *curr, {return 1 ; } + +static void init_chain_block_buckets (void ) { }#endif /* CONFIG_PROVE_LOCKING */ /*
@@ -4788,6 +5019,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,return ; free_lock_chain: +free_chain_hlocks (chain->base, chain->depth);/* Overwrite the chain key for concurrent RCU readers. */ WRITE_ONCE (chain->chain_key,INITIAL_CHAIN_KEY );dec_chains (chain->irq_context);
kernel/locking/lockdep_internals.h +3 -1
@@ -140,7 +140,9 @@ extern unsigned long nr_stack_trace_entries;extern unsigned int nr_hardirq_chains;extern unsigned int nr_softirq_chains;extern unsigned int nr_process_chains; -extern unsigned int nr_chain_hlocks; +extern unsigned int nr_free_chain_hlocks; +extern unsigned int nr_lost_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 +9 -3
@@ -137,7 +137,7 @@ static int lc_show(struct seq_file *m, void *v) };if (v ==SEQ_START_TOKEN ) { -if (nr_chain_hlocks >MAX_LOCKDEP_CHAIN_HLOCKS ) +if (!nr_free_chain_hlocks)seq_printf (m,"(buggered) " );seq_printf (m,"all lock chains:\n" );return 0 ;
@@ -278,8 +278,12 @@ static int lockdep_stats_show(struct seq_file *m, void *v)#ifdef CONFIG_PROVE_LOCKING seq_printf (m," dependency chains: %11lu [max: %lu]\n" ,lock_chain_count (),MAX_LOCKDEP_CHAINS ); -seq_printf (m," dependency chain hlocks: %11u [max: %lu]\n" , - nr_chain_hlocks,MAX_LOCKDEP_CHAIN_HLOCKS ); +seq_printf (m," dependency chain hlocks used: %11lu [max: %lu]\n" , +MAX_LOCKDEP_CHAIN_HLOCKS - + (nr_free_chain_hlocks + nr_lost_chain_hlocks), +MAX_LOCKDEP_CHAIN_HLOCKS ); +seq_printf (m," dependency chain hlocks lost: %11u\n" , + nr_lost_chain_hlocks);#endif #ifdef CONFIG_TRACE_IRQFLAGS
@@ -352,6 +356,8 @@ static int lockdep_stats_show(struct seq_file *m, void *v)#ifdef CONFIG_PROVE_LOCKING seq_printf (m," zapped lock chains: %11lu\n" , nr_zapped_lock_chains); +seq_printf (m," large chain blocks: %11u\n" , + nr_large_chain_blocks);#endif return 0 ; }