* [PATCH 0/4] Lockdep: Reduce stack trace memory usage
@ 2019-07-22 18:24 Bart Van Assche
2019-07-22 18:24 ` [PATCH 1/4] locking/lockdep: Make it clear that what lock_class::key points at is not modified Bart Van Assche
` (4 more replies)
0 siblings, 5 replies; 12+ messages in thread
From: Bart Van Assche @ 2019-07-22 18:24 UTC (permalink / raw)
To: Peter Zijlstra; +Cc: Ingo Molnar, linux-kernel, Bart Van Assche
Hi Peter,
An unfortunate side effect of commit 669de8bda87b ("kernel/workqueue: Use
dynamic lockdep keys for workqueues") is that all stack traces associated
with the lockdep key are leaked when a workqueue is destroyed. Fix this by
storing each unique stack trace once. Please consider this patch series
for Linux kernel v5.4.
Thanks,
Bart.
Bart Van Assche (4):
locking/lockdep: Make it clear that what lock_class::key points at is
not modified
stacktrace: Constify 'entries' arguments
locking/lockdep: Reduce space occupied by stack traces
locking/lockdep: Report more stack trace statistics
include/linux/lockdep.h | 11 +-
include/linux/stacktrace.h | 4 +-
kernel/locking/lockdep.c | 159 ++++++++++++++++++++++-------
kernel/locking/lockdep_internals.h | 9 +-
kernel/locking/lockdep_proc.c | 8 +-
kernel/stacktrace.c | 4 +-
6 files changed, 143 insertions(+), 52 deletions(-)
--
2.22.0.657.g960e92d24f-goog
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH 1/4] locking/lockdep: Make it clear that what lock_class::key points at is not modified 2019-07-22 18:24 [PATCH 0/4] Lockdep: Reduce stack trace memory usage Bart Van Assche @ 2019-07-22 18:24 ` Bart Van Assche 2019-07-25 16:08 ` [tip:locking/core] " tip-bot for Bart Van Assche 2019-07-22 18:24 ` [PATCH 2/4] stacktrace: Constify 'entries' arguments Bart Van Assche ` (3 subsequent siblings) 4 siblings, 1 reply; 12+ messages in thread From: Bart Van Assche @ 2019-07-22 18:24 UTC (permalink / raw) To: Peter Zijlstra Cc: Ingo Molnar, linux-kernel, Bart Van Assche, Thomas Gleixner, Will Deacon, Waiman Long This patch does not change the behavior of the lockdep code. Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Will Deacon <will.deacon@arm.com> Cc: Waiman Long <longman@redhat.com> Signed-off-by: Bart Van Assche <bvanassche@acm.org> --- include/linux/lockdep.h | 2 +- kernel/locking/lockdep.c | 2 +- kernel/locking/lockdep_internals.h | 3 ++- kernel/locking/lockdep_proc.c | 2 +- 4 files changed, 5 insertions(+), 4 deletions(-) diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h index 0b0d7259276d..cdb3c2f06092 100644 --- a/include/linux/lockdep.h +++ b/include/linux/lockdep.h @@ -97,7 +97,7 @@ struct lock_class { */ struct list_head locks_after, locks_before; - struct lockdep_subclass_key *key; + const struct lockdep_subclass_key *key; unsigned int subclass; unsigned int dep_gen_id; diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 341f52117f88..f4127c5a495d 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -511,7 +511,7 @@ static const char *usage_str[] = }; #endif -const char * __get_key_name(struct lockdep_subclass_key *key, char *str) +const char *__get_key_name(const struct lockdep_subclass_key *key, char *str) { return kallsyms_lookup((unsigned long)key, NULL, NULL, NULL, str); } diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h index cc83568d5012..2e518369add4 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -116,7 +116,8 @@ extern struct lock_chain lock_chains[]; extern void get_usage_chars(struct lock_class *class, char usage[LOCK_USAGE_CHARS]); -extern const char * __get_key_name(struct lockdep_subclass_key *key, char *str); +extern const char *__get_key_name(const struct lockdep_subclass_key *key, + char *str); struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i); diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c index 65b6a1600c8f..1ba5780182e7 100644 --- a/kernel/locking/lockdep_proc.c +++ b/kernel/locking/lockdep_proc.c @@ -398,7 +398,7 @@ static void seq_lock_time(struct seq_file *m, struct lock_time *lt) static void seq_stats(struct seq_file *m, struct lock_stat_data *data) { - struct lockdep_subclass_key *ckey; + const struct lockdep_subclass_key *ckey; struct lock_class_stats *stats; struct lock_class *class; const char *cname; -- 2.22.0.657.g960e92d24f-goog ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [tip:locking/core] locking/lockdep: Make it clear that what lock_class::key points at is not modified 2019-07-22 18:24 ` [PATCH 1/4] locking/lockdep: Make it clear that what lock_class::key points at is not modified Bart Van Assche @ 2019-07-25 16:08 ` tip-bot for Bart Van Assche 0 siblings, 0 replies; 12+ messages in thread From: tip-bot for Bart Van Assche @ 2019-07-25 16:08 UTC (permalink / raw) To: linux-tip-commits Cc: tglx, bvanassche, mingo, peterz, longman, will.deacon, torvalds, linux-kernel, hpa Commit-ID: 364f6afc4f5537b79cf454eb35cae92920676075 Gitweb: https://git.kernel.org/tip/364f6afc4f5537b79cf454eb35cae92920676075 Author: Bart Van Assche <bvanassche@acm.org> AuthorDate: Mon, 22 Jul 2019 11:24:40 -0700 Committer: Ingo Molnar <mingo@kernel.org> CommitDate: Thu, 25 Jul 2019 15:43:26 +0200 locking/lockdep: Make it clear that what lock_class::key points at is not modified This patch does not change the behavior of the lockdep code. Signed-off-by: Bart Van Assche <bvanassche@acm.org> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Waiman Long <longman@redhat.com> Cc: Will Deacon <will.deacon@arm.com> Link: https://lkml.kernel.org/r/20190722182443.216015-2-bvanassche@acm.org Signed-off-by: Ingo Molnar <mingo@kernel.org> --- include/linux/lockdep.h | 2 +- kernel/locking/lockdep.c | 2 +- kernel/locking/lockdep_internals.h | 3 ++- kernel/locking/lockdep_proc.c | 2 +- 4 files changed, 5 insertions(+), 4 deletions(-) diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h index 0b0d7259276d..cdb3c2f06092 100644 --- a/include/linux/lockdep.h +++ b/include/linux/lockdep.h @@ -97,7 +97,7 @@ struct lock_class { */ struct list_head locks_after, locks_before; - struct lockdep_subclass_key *key; + const struct lockdep_subclass_key *key; unsigned int subclass; unsigned int dep_gen_id; diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 4861cf8e274b..af6627866191 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -511,7 +511,7 @@ static const char *usage_str[] = }; #endif -const char * __get_key_name(struct lockdep_subclass_key *key, char *str) +const char *__get_key_name(const struct lockdep_subclass_key *key, char *str) { return kallsyms_lookup((unsigned long)key, NULL, NULL, NULL, str); } diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h index cc83568d5012..2e518369add4 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -116,7 +116,8 @@ extern struct lock_chain lock_chains[]; extern void get_usage_chars(struct lock_class *class, char usage[LOCK_USAGE_CHARS]); -extern const char * __get_key_name(struct lockdep_subclass_key *key, char *str); +extern const char *__get_key_name(const struct lockdep_subclass_key *key, + char *str); struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i); diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c index bda006f8a88b..ed9842425cac 100644 --- a/kernel/locking/lockdep_proc.c +++ b/kernel/locking/lockdep_proc.c @@ -399,7 +399,7 @@ static void seq_lock_time(struct seq_file *m, struct lock_time *lt) static void seq_stats(struct seq_file *m, struct lock_stat_data *data) { - struct lockdep_subclass_key *ckey; + const struct lockdep_subclass_key *ckey; struct lock_class_stats *stats; struct lock_class *class; const char *cname; ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 2/4] stacktrace: Constify 'entries' arguments 2019-07-22 18:24 [PATCH 0/4] Lockdep: Reduce stack trace memory usage Bart Van Assche 2019-07-22 18:24 ` [PATCH 1/4] locking/lockdep: Make it clear that what lock_class::key points at is not modified Bart Van Assche @ 2019-07-22 18:24 ` Bart Van Assche 2019-07-25 16:09 ` [tip:locking/core] " tip-bot for Bart Van Assche 2019-07-22 18:24 ` [PATCH 3/4] locking/lockdep: Reduce space occupied by stack traces Bart Van Assche ` (2 subsequent siblings) 4 siblings, 1 reply; 12+ messages in thread From: Bart Van Assche @ 2019-07-22 18:24 UTC (permalink / raw) To: Peter Zijlstra Cc: Ingo Molnar, linux-kernel, Bart Van Assche, Thomas Gleixner, Will Deacon, Waiman Long Make it clear to humans and to the compiler that the stack trace ('entries') arguments are not modified. Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Will Deacon <will.deacon@arm.com> Cc: Waiman Long <longman@redhat.com> Signed-off-by: Bart Van Assche <bvanassche@acm.org> --- include/linux/stacktrace.h | 4 ++-- kernel/stacktrace.c | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-) diff --git a/include/linux/stacktrace.h b/include/linux/stacktrace.h index f0cfd12cb45e..83bd8cb475d7 100644 --- a/include/linux/stacktrace.h +++ b/include/linux/stacktrace.h @@ -9,9 +9,9 @@ struct task_struct; struct pt_regs; #ifdef CONFIG_STACKTRACE -void stack_trace_print(unsigned long *trace, unsigned int nr_entries, +void stack_trace_print(const unsigned long *trace, unsigned int nr_entries, int spaces); -int stack_trace_snprint(char *buf, size_t size, unsigned long *entries, +int stack_trace_snprint(char *buf, size_t size, const unsigned long *entries, unsigned int nr_entries, int spaces); unsigned int stack_trace_save(unsigned long *store, unsigned int size, unsigned int skipnr); diff --git a/kernel/stacktrace.c b/kernel/stacktrace.c index f5440abb7532..6d1f68b7e528 100644 --- a/kernel/stacktrace.c +++ b/kernel/stacktrace.c @@ -20,7 +20,7 @@ * @nr_entries: Number of entries in the storage array * @spaces: Number of leading spaces to print */ -void stack_trace_print(unsigned long *entries, unsigned int nr_entries, +void stack_trace_print(const unsigned long *entries, unsigned int nr_entries, int spaces) { unsigned int i; @@ -43,7 +43,7 @@ EXPORT_SYMBOL_GPL(stack_trace_print); * * Return: Number of bytes printed. */ -int stack_trace_snprint(char *buf, size_t size, unsigned long *entries, +int stack_trace_snprint(char *buf, size_t size, const unsigned long *entries, unsigned int nr_entries, int spaces) { unsigned int generated, i, total = 0; -- 2.22.0.657.g960e92d24f-goog ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [tip:locking/core] stacktrace: Constify 'entries' arguments 2019-07-22 18:24 ` [PATCH 2/4] stacktrace: Constify 'entries' arguments Bart Van Assche @ 2019-07-25 16:09 ` tip-bot for Bart Van Assche 0 siblings, 0 replies; 12+ messages in thread From: tip-bot for Bart Van Assche @ 2019-07-25 16:09 UTC (permalink / raw) To: linux-tip-commits Cc: mingo, will.deacon, bvanassche, linux-kernel, longman, tglx, torvalds, peterz, hpa Commit-ID: a2970421640bd9b6a78f2685d7750a791abdfd4e Gitweb: https://git.kernel.org/tip/a2970421640bd9b6a78f2685d7750a791abdfd4e Author: Bart Van Assche <bvanassche@acm.org> AuthorDate: Mon, 22 Jul 2019 11:24:41 -0700 Committer: Ingo Molnar <mingo@kernel.org> CommitDate: Thu, 25 Jul 2019 15:43:26 +0200 stacktrace: Constify 'entries' arguments Make it clear to humans and to the compiler that the stack trace ('entries') arguments are not modified. Signed-off-by: Bart Van Assche <bvanassche@acm.org> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Waiman Long <longman@redhat.com> Cc: Will Deacon <will.deacon@arm.com> Link: https://lkml.kernel.org/r/20190722182443.216015-3-bvanassche@acm.org Signed-off-by: Ingo Molnar <mingo@kernel.org> --- include/linux/stacktrace.h | 4 ++-- kernel/stacktrace.c | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-) diff --git a/include/linux/stacktrace.h b/include/linux/stacktrace.h index f0cfd12cb45e..83bd8cb475d7 100644 --- a/include/linux/stacktrace.h +++ b/include/linux/stacktrace.h @@ -9,9 +9,9 @@ struct task_struct; struct pt_regs; #ifdef CONFIG_STACKTRACE -void stack_trace_print(unsigned long *trace, unsigned int nr_entries, +void stack_trace_print(const unsigned long *trace, unsigned int nr_entries, int spaces); -int stack_trace_snprint(char *buf, size_t size, unsigned long *entries, +int stack_trace_snprint(char *buf, size_t size, const unsigned long *entries, unsigned int nr_entries, int spaces); unsigned int stack_trace_save(unsigned long *store, unsigned int size, unsigned int skipnr); diff --git a/kernel/stacktrace.c b/kernel/stacktrace.c index f5440abb7532..6d1f68b7e528 100644 --- a/kernel/stacktrace.c +++ b/kernel/stacktrace.c @@ -20,7 +20,7 @@ * @nr_entries: Number of entries in the storage array * @spaces: Number of leading spaces to print */ -void stack_trace_print(unsigned long *entries, unsigned int nr_entries, +void stack_trace_print(const unsigned long *entries, unsigned int nr_entries, int spaces) { unsigned int i; @@ -43,7 +43,7 @@ EXPORT_SYMBOL_GPL(stack_trace_print); * * Return: Number of bytes printed. */ -int stack_trace_snprint(char *buf, size_t size, unsigned long *entries, +int stack_trace_snprint(char *buf, size_t size, const unsigned long *entries, unsigned int nr_entries, int spaces) { unsigned int generated, i, total = 0; ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 3/4] locking/lockdep: Reduce space occupied by stack traces 2019-07-22 18:24 [PATCH 0/4] Lockdep: Reduce stack trace memory usage Bart Van Assche 2019-07-22 18:24 ` [PATCH 1/4] locking/lockdep: Make it clear that what lock_class::key points at is not modified Bart Van Assche 2019-07-22 18:24 ` [PATCH 2/4] stacktrace: Constify 'entries' arguments Bart Van Assche @ 2019-07-22 18:24 ` Bart Van Assche 2019-07-24 4:56 ` Eric Biggers 2019-07-25 16:10 ` [tip:locking/core] " tip-bot for Bart Van Assche 2019-07-22 18:24 ` [PATCH 4/4] locking/lockdep: Report more stack trace statistics Bart Van Assche 2019-07-23 9:27 ` [PATCH 0/4] Lockdep: Reduce stack trace memory usage Peter Zijlstra 4 siblings, 2 replies; 12+ messages in thread From: Bart Van Assche @ 2019-07-22 18:24 UTC (permalink / raw) To: Peter Zijlstra Cc: Ingo Molnar, linux-kernel, Bart Van Assche, Thomas Gleixner, Will Deacon, Yuyang Du, Waiman Long, Eric Biggers Although commit 669de8bda87b ("kernel/workqueue: Use dynamic lockdep keys for workqueues") unregisters dynamic lockdep keys when a workqueue is destroyed, a side effect of that commit is that all stack traces associated with the lockdep key are leaked when a workqueue is destroyed. Fix this by storing each unique stack trace once. Other changes in this patch are: - Use NULL instead of { .nr_entries = 0 } to represent 'no trace'. - Store a pointer to a stack trace in struct lock_class and struct lock_list instead of storing 'nr_entries' and 'offset'. This patch avoids that the following program triggers the "BUG: MAX_STACK_TRACE_ENTRIES too low!" complaint: #include <fcntl.h> #include <unistd.h> int main() { for (;;) { int fd = open("/dev/infiniband/rdma_cm", O_RDWR); close(fd); } } Cc: Ingo Molnar <mingo@kernel.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Will Deacon <will.deacon@arm.com> Cc: Yuyang Du <duyuyang@gmail.com> Cc: Waiman Long <longman@redhat.com> Reported-by: Eric Biggers <ebiggers@kernel.org> Suggested-by: Peter Zijlstra <peterz@infradead.org> Signed-off-by: Bart Van Assche <bvanassche@acm.org> --- include/linux/lockdep.h | 9 +- kernel/locking/lockdep.c | 128 ++++++++++++++++++++--------- kernel/locking/lockdep_internals.h | 2 + 3 files changed, 95 insertions(+), 44 deletions(-) diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h index cdb3c2f06092..b8a835fd611b 100644 --- a/include/linux/lockdep.h +++ b/include/linux/lockdep.h @@ -66,10 +66,7 @@ struct lock_class_key { extern struct lock_class_key __lockdep_no_validate__; -struct lock_trace { - unsigned int nr_entries; - unsigned int offset; -}; +struct lock_trace; #define LOCKSTAT_POINTS 4 @@ -105,7 +102,7 @@ struct lock_class { * IRQ/softirq usage tracking bits: */ unsigned long usage_mask; - struct lock_trace usage_traces[XXX_LOCK_USAGE_STATES]; + const struct lock_trace *usage_traces[XXX_LOCK_USAGE_STATES]; /* * Generation counter, when doing certain classes of graph walking, @@ -193,7 +190,7 @@ struct lock_list { struct list_head entry; struct lock_class *class; struct lock_class *links_to; - struct lock_trace trace; + const struct lock_trace *trace; int distance; /* diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index f4127c5a495d..19eace34b5fa 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -449,33 +449,72 @@ static void print_lockdep_off(const char *bug_msg) unsigned long nr_stack_trace_entries; #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) +/** + * struct lock_trace - single stack backtrace + * @hash_entry: Entry in a stack_trace_hash[] list. + * @hash: jhash() of @entries. + * @nr_entries: Number of entries in @entries. + * @entries: Actual stack backtrace. + */ +struct lock_trace { + struct hlist_node hash_entry; + u32 hash; + u32 nr_entries; + unsigned long entries[0] __aligned(sizeof(unsigned long)); +}; +#define LOCK_TRACE_SIZE_IN_LONGS \ + (sizeof(struct lock_trace) / sizeof(unsigned long)) /* - * Stack-trace: tightly packed array of stack backtrace - * addresses. Protected by the graph_lock. + * Stack-trace: sequence of lock_trace structures. Protected by the graph_lock. */ static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES]; +static struct hlist_head stack_trace_hash[STACK_TRACE_HASH_SIZE]; + +static bool traces_identical(struct lock_trace *t1, struct lock_trace *t2) +{ + return t1->hash == t2->hash && t1->nr_entries == t2->nr_entries && + memcmp(t1->entries, t2->entries, + t1->nr_entries * sizeof(t1->entries[0])) == 0; +} -static int save_trace(struct lock_trace *trace) +static struct lock_trace *save_trace(void) { - unsigned long *entries = stack_trace + nr_stack_trace_entries; + struct lock_trace *trace, *t2; + struct hlist_head *hash_head; + u32 hash; unsigned int max_entries; - trace->offset = nr_stack_trace_entries; - max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries; - trace->nr_entries = stack_trace_save(entries, max_entries, 3); - nr_stack_trace_entries += trace->nr_entries; + BUILD_BUG_ON_NOT_POWER_OF_2(STACK_TRACE_HASH_SIZE); + BUILD_BUG_ON(LOCK_TRACE_SIZE_IN_LONGS >= MAX_STACK_TRACE_ENTRIES); + + trace = (struct lock_trace *)(stack_trace + nr_stack_trace_entries); + max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries - + LOCK_TRACE_SIZE_IN_LONGS; + trace->nr_entries = stack_trace_save(trace->entries, max_entries, 3); - if (nr_stack_trace_entries >= MAX_STACK_TRACE_ENTRIES-1) { + if (nr_stack_trace_entries >= MAX_STACK_TRACE_ENTRIES - + LOCK_TRACE_SIZE_IN_LONGS - 1) { if (!debug_locks_off_graph_unlock()) - return 0; + return NULL; print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!"); dump_stack(); - return 0; + return NULL; } - return 1; + hash = jhash(trace->entries, trace->nr_entries * + sizeof(trace->entries[0]), 0); + trace->hash = hash; + hash_head = stack_trace_hash + (hash & (STACK_TRACE_HASH_SIZE - 1)); + hlist_for_each_entry(t2, hash_head, hash_entry) { + if (traces_identical(trace, t2)) + return t2; + } + nr_stack_trace_entries += LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries; + hlist_add_head(&trace->hash_entry, hash_head); + + return trace; } #endif @@ -1235,7 +1274,7 @@ static struct lock_list *alloc_list_entry(void) static int add_lock_to_list(struct lock_class *this, struct lock_class *links_to, struct list_head *head, unsigned long ip, int distance, - struct lock_trace *trace) + const struct lock_trace *trace) { struct lock_list *entry; /* @@ -1249,7 +1288,7 @@ static int add_lock_to_list(struct lock_class *this, entry->class = this; entry->links_to = links_to; entry->distance = distance; - entry->trace = *trace; + entry->trace = trace; /* * Both allocation and removal are done under the graph lock; but * iteration is under RCU-sched; see look_up_lock_class() and @@ -1470,11 +1509,10 @@ static inline int __bfs_backwards(struct lock_list *src_entry, } -static void print_lock_trace(struct lock_trace *trace, unsigned int spaces) +static void print_lock_trace(const struct lock_trace *trace, + unsigned int spaces) { - unsigned long *entries = stack_trace + trace->offset; - - stack_trace_print(entries, trace->nr_entries, spaces); + stack_trace_print(trace->entries, trace->nr_entries, spaces); } /* @@ -1489,7 +1527,7 @@ print_circular_bug_entry(struct lock_list *target, int depth) printk("\n-> #%u", depth); print_lock_name(target->class); printk(KERN_CONT ":\n"); - print_lock_trace(&target->trace, 6); + print_lock_trace(target->trace, 6); } static void @@ -1592,7 +1630,8 @@ static noinline void print_circular_bug(struct lock_list *this, if (!debug_locks_off_graph_unlock() || debug_locks_silent) return; - if (!save_trace(&this->trace)) + this->trace = save_trace(); + if (!this->trace) return; depth = get_lock_depth(target); @@ -1715,7 +1754,7 @@ check_path(struct lock_class *target, struct lock_list *src_entry, */ static noinline int check_noncircular(struct held_lock *src, struct held_lock *target, - struct lock_trace *trace) + struct lock_trace **const trace) { int ret; struct lock_list *uninitialized_var(target_entry); @@ -1729,13 +1768,13 @@ check_noncircular(struct held_lock *src, struct held_lock *target, ret = check_path(hlock_class(target), &src_entry, &target_entry); if (unlikely(!ret)) { - if (!trace->nr_entries) { + if (!*trace) { /* * If save_trace fails here, the printing might * trigger a WARN but because of the !nr_entries it * should not do bad things. */ - save_trace(trace); + *trace = save_trace(); } print_circular_bug(&src_entry, target_entry, src, target); @@ -1859,7 +1898,7 @@ static void print_lock_class_header(struct lock_class *class, int depth) len += printk("%*s %s", depth, "", usage_str[bit]); len += printk(KERN_CONT " at:\n"); - print_lock_trace(class->usage_traces + bit, len); + print_lock_trace(class->usage_traces[bit], len); } } printk("%*s }\n", depth, ""); @@ -1884,7 +1923,7 @@ print_shortest_lock_dependencies(struct lock_list *leaf, do { print_lock_class_header(entry->class, depth); printk("%*s ... acquired at:\n", depth, ""); - print_lock_trace(&entry->trace, 2); + print_lock_trace(entry->trace, 2); printk("\n"); if (depth == 0 && (entry != root)) { @@ -1995,14 +2034,14 @@ print_bad_irq_dependency(struct task_struct *curr, print_lock_name(backwards_entry->class); pr_warn("\n... which became %s-irq-safe at:\n", irqclass); - print_lock_trace(backwards_entry->class->usage_traces + bit1, 1); + print_lock_trace(backwards_entry->class->usage_traces[bit1], 1); pr_warn("\nto a %s-irq-unsafe lock:\n", irqclass); print_lock_name(forwards_entry->class); pr_warn("\n... which became %s-irq-unsafe at:\n", irqclass); pr_warn("..."); - print_lock_trace(forwards_entry->class->usage_traces + bit2, 1); + print_lock_trace(forwards_entry->class->usage_traces[bit2], 1); pr_warn("\nother info that might help us debug this:\n\n"); print_irq_lock_scenario(backwards_entry, forwards_entry, @@ -2011,13 +2050,15 @@ print_bad_irq_dependency(struct task_struct *curr, lockdep_print_held_locks(curr); pr_warn("\nthe dependencies between %s-irq-safe lock and the holding lock:\n", irqclass); - if (!save_trace(&prev_root->trace)) + prev_root->trace = save_trace(); + if (!prev_root->trace) return; print_shortest_lock_dependencies(backwards_entry, prev_root); pr_warn("\nthe dependencies between the lock to be acquired"); pr_warn(" and %s-irq-unsafe lock:\n", irqclass); - if (!save_trace(&next_root->trace)) + next_root->trace = save_trace(); + if (!next_root->trace) return; print_shortest_lock_dependencies(forwards_entry, next_root); @@ -2369,7 +2410,8 @@ check_deadlock(struct task_struct *curr, struct held_lock *next) */ static int check_prev_add(struct task_struct *curr, struct held_lock *prev, - struct held_lock *next, int distance, struct lock_trace *trace) + struct held_lock *next, int distance, + struct lock_trace **const trace) { struct lock_list *entry; int ret; @@ -2444,8 +2486,11 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev, return ret; #endif - if (!trace->nr_entries && !save_trace(trace)) - return 0; + if (!*trace) { + *trace = save_trace(); + if (!*trace) + return 0; + } /* * Ok, all validations passed, add the new lock @@ -2453,14 +2498,14 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev, */ ret = add_lock_to_list(hlock_class(next), hlock_class(prev), &hlock_class(prev)->locks_after, - next->acquire_ip, distance, trace); + next->acquire_ip, distance, *trace); if (!ret) return 0; ret = add_lock_to_list(hlock_class(prev), hlock_class(next), &hlock_class(next)->locks_before, - next->acquire_ip, distance, trace); + next->acquire_ip, distance, *trace); if (!ret) return 0; @@ -2476,7 +2521,7 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev, static int check_prevs_add(struct task_struct *curr, struct held_lock *next) { - struct lock_trace trace = { .nr_entries = 0 }; + struct lock_trace *trace = NULL; int depth = curr->lockdep_depth; struct held_lock *hlock; @@ -3015,7 +3060,7 @@ print_usage_bug(struct task_struct *curr, struct held_lock *this, print_lock(this); pr_warn("{%s} state was registered at:\n", usage_str[prev_bit]); - print_lock_trace(hlock_class(this)->usage_traces + prev_bit, 1); + print_lock_trace(hlock_class(this)->usage_traces[prev_bit], 1); print_irqtrace_events(curr); pr_warn("\nother info that might help us debug this:\n"); @@ -3096,7 +3141,8 @@ print_irq_inversion_bug(struct task_struct *curr, lockdep_print_held_locks(curr); pr_warn("\nthe shortest dependencies between 2nd lock and 1st lock:\n"); - if (!save_trace(&root->trace)) + root->trace = save_trace(); + if (!root->trace) return; print_shortest_lock_dependencies(other, root); @@ -3580,7 +3626,7 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this, hlock_class(this)->usage_mask |= new_mask; - if (!save_trace(hlock_class(this)->usage_traces + new_bit)) + if (!(hlock_class(this)->usage_traces[new_bit] = save_trace())) return 0; switch (new_bit) { @@ -5158,6 +5204,12 @@ void __init lockdep_init(void) ) / 1024 ); +#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) + printk(" memory used for stack traces: %zu kB\n", + (sizeof(stack_trace) + sizeof(stack_trace_hash)) / 1024 + ); +#endif + printk(" per task-struct memory footprint: %zu bytes\n", sizeof(((struct task_struct *)NULL)->held_locks)); } diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h index 2e518369add4..93a008bf77db 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -92,6 +92,7 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ = #define MAX_LOCKDEP_ENTRIES 16384UL #define MAX_LOCKDEP_CHAINS_BITS 15 #define MAX_STACK_TRACE_ENTRIES 262144UL +#define STACK_TRACE_HASH_SIZE 8192 #else #define MAX_LOCKDEP_ENTRIES 32768UL @@ -102,6 +103,7 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ = * addresses. Protected by the hash_lock. */ #define MAX_STACK_TRACE_ENTRIES 524288UL +#define STACK_TRACE_HASH_SIZE 16384 #endif #define MAX_LOCKDEP_CHAINS (1UL << MAX_LOCKDEP_CHAINS_BITS) -- 2.22.0.657.g960e92d24f-goog ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH 3/4] locking/lockdep: Reduce space occupied by stack traces 2019-07-22 18:24 ` [PATCH 3/4] locking/lockdep: Reduce space occupied by stack traces Bart Van Assche @ 2019-07-24 4:56 ` Eric Biggers 2019-07-24 15:47 ` Bart Van Assche 2019-07-25 16:10 ` [tip:locking/core] " tip-bot for Bart Van Assche 1 sibling, 1 reply; 12+ messages in thread From: Eric Biggers @ 2019-07-24 4:56 UTC (permalink / raw) To: Bart Van Assche Cc: Peter Zijlstra, Ingo Molnar, linux-kernel, Thomas Gleixner, Will Deacon, Yuyang Du, Waiman Long On Mon, Jul 22, 2019 at 11:24:42AM -0700, Bart Van Assche wrote: > Although commit 669de8bda87b ("kernel/workqueue: Use dynamic lockdep keys > for workqueues") unregisters dynamic lockdep keys when a workqueue is > destroyed, a side effect of that commit is that all stack traces > associated with the lockdep key are leaked when a workqueue is destroyed. > Fix this by storing each unique stack trace once. Other changes in this > patch are: > - Use NULL instead of { .nr_entries = 0 } to represent 'no trace'. > - Store a pointer to a stack trace in struct lock_class and struct > lock_list instead of storing 'nr_entries' and 'offset'. > > This patch avoids that the following program triggers the "BUG: > MAX_STACK_TRACE_ENTRIES too low!" complaint: Does this also fix any of the other bugs listed at https://lore.kernel.org/lkml/20190710055838.GC2152@sol.localdomain/ ? BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! BUG: MAX_LOCKDEP_CHAINS too low! BUG: MAX_LOCK_DEPTH too low! (2) BUG: MAX_LOCKDEP_ENTRIES too low! > > #include <fcntl.h> > #include <unistd.h> > > int main() > { > for (;;) { > int fd = open("/dev/infiniband/rdma_cm", O_RDWR); > close(fd); > } > } > > Cc: Ingo Molnar <mingo@kernel.org> > Cc: Thomas Gleixner <tglx@linutronix.de> > Cc: Will Deacon <will.deacon@arm.com> > Cc: Yuyang Du <duyuyang@gmail.com> > Cc: Waiman Long <longman@redhat.com> > Reported-by: Eric Biggers <ebiggers@kernel.org> Can you please add: Reported-by: syzbot+6f39a9deb697359fe520@syzkaller.appspotmail.com Thanks, - Eric ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 3/4] locking/lockdep: Reduce space occupied by stack traces 2019-07-24 4:56 ` Eric Biggers @ 2019-07-24 15:47 ` Bart Van Assche 0 siblings, 0 replies; 12+ messages in thread From: Bart Van Assche @ 2019-07-24 15:47 UTC (permalink / raw) To: Peter Zijlstra, Ingo Molnar, linux-kernel, Thomas Gleixner, Will Deacon, Yuyang Du, Waiman Long On 7/23/19 9:56 PM, Eric Biggers wrote: > Does this also fix any of the other bugs listed at > https://lore.kernel.org/lkml/20190710055838.GC2152@sol.localdomain/ > ? > > BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! > BUG: MAX_LOCKDEP_CHAINS too low! > BUG: MAX_LOCK_DEPTH too low! (2) > BUG: MAX_LOCKDEP_ENTRIES too low! Hi Eric, I don't think so. This patch only affects the space occupied by stack traces and not the space occupied by any of the other lockdep data strutures. BTW, in that report I found the following: Title: BUG: MAX_LOCKDEP_CHAINS too low! Last occurred: 5 days ago Reported: 284 days ago Title: BUG: MAX_LOCK_DEPTH too low! (2) Last occurred: 362 days ago Reported: 392 days ago Since these bugs were reported more than 150 days ago these bugs are older than my lockdep changes and hence not a regression due to my lockdep changes. My patch series did not increase the number of "list_entries" tracked by lockdep so I don't think that the "BUG: MAX_LOCKDEP_ENTRIES too low" behavior can be triggered more easily due to my lockdep changes. The "BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!" complaint however may be related. I will check whether it is possible to reduce the space occupied by held lock chains again to what was needed before my patch series. Bart. ^ permalink raw reply [flat|nested] 12+ messages in thread
* [tip:locking/core] locking/lockdep: Reduce space occupied by stack traces 2019-07-22 18:24 ` [PATCH 3/4] locking/lockdep: Reduce space occupied by stack traces Bart Van Assche 2019-07-24 4:56 ` Eric Biggers @ 2019-07-25 16:10 ` tip-bot for Bart Van Assche 1 sibling, 0 replies; 12+ messages in thread From: tip-bot for Bart Van Assche @ 2019-07-25 16:10 UTC (permalink / raw) To: linux-tip-commits Cc: torvalds, duyuyang, ebiggers, bvanassche, will.deacon, longman, mingo, linux-kernel, peterz, hpa, tglx Commit-ID: 12593b7467f9130b64a6d4b6a26ed4ec217b6784 Gitweb: https://git.kernel.org/tip/12593b7467f9130b64a6d4b6a26ed4ec217b6784 Author: Bart Van Assche <bvanassche@acm.org> AuthorDate: Mon, 22 Jul 2019 11:24:42 -0700 Committer: Ingo Molnar <mingo@kernel.org> CommitDate: Thu, 25 Jul 2019 15:43:27 +0200 locking/lockdep: Reduce space occupied by stack traces Although commit 669de8bda87b ("kernel/workqueue: Use dynamic lockdep keys for workqueues") unregisters dynamic lockdep keys when a workqueue is destroyed, a side effect of that commit is that all stack traces associated with the lockdep key are leaked when a workqueue is destroyed. Fix this by storing each unique stack trace once. Other changes in this patch are: - Use NULL instead of { .nr_entries = 0 } to represent 'no trace'. - Store a pointer to a stack trace in struct lock_class and struct lock_list instead of storing 'nr_entries' and 'offset'. This patch avoids that the following program triggers the "BUG: MAX_STACK_TRACE_ENTRIES too low!" complaint: #include <fcntl.h> #include <unistd.h> int main() { for (;;) { int fd = open("/dev/infiniband/rdma_cm", O_RDWR); close(fd); } } Suggested-by: Peter Zijlstra <peterz@infradead.org> Reported-by: Eric Biggers <ebiggers@kernel.org> Signed-off-by: Bart Van Assche <bvanassche@acm.org> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Waiman Long <longman@redhat.com> Cc: Will Deacon <will.deacon@arm.com> Cc: Yuyang Du <duyuyang@gmail.com> Link: https://lkml.kernel.org/r/20190722182443.216015-4-bvanassche@acm.org Signed-off-by: Ingo Molnar <mingo@kernel.org> --- include/linux/lockdep.h | 9 +-- kernel/locking/lockdep.c | 128 ++++++++++++++++++++++++++----------- kernel/locking/lockdep_internals.h | 2 + 3 files changed, 95 insertions(+), 44 deletions(-) diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h index cdb3c2f06092..b8a835fd611b 100644 --- a/include/linux/lockdep.h +++ b/include/linux/lockdep.h @@ -66,10 +66,7 @@ struct lock_class_key { extern struct lock_class_key __lockdep_no_validate__; -struct lock_trace { - unsigned int nr_entries; - unsigned int offset; -}; +struct lock_trace; #define LOCKSTAT_POINTS 4 @@ -105,7 +102,7 @@ struct lock_class { * IRQ/softirq usage tracking bits: */ unsigned long usage_mask; - struct lock_trace usage_traces[XXX_LOCK_USAGE_STATES]; + const struct lock_trace *usage_traces[XXX_LOCK_USAGE_STATES]; /* * Generation counter, when doing certain classes of graph walking, @@ -193,7 +190,7 @@ struct lock_list { struct list_head entry; struct lock_class *class; struct lock_class *links_to; - struct lock_trace trace; + const struct lock_trace *trace; int distance; /* diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index af6627866191..1a96869cb2f0 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -449,33 +449,72 @@ static void print_lockdep_off(const char *bug_msg) unsigned long nr_stack_trace_entries; #ifdef CONFIG_PROVE_LOCKING +/** + * struct lock_trace - single stack backtrace + * @hash_entry: Entry in a stack_trace_hash[] list. + * @hash: jhash() of @entries. + * @nr_entries: Number of entries in @entries. + * @entries: Actual stack backtrace. + */ +struct lock_trace { + struct hlist_node hash_entry; + u32 hash; + u32 nr_entries; + unsigned long entries[0] __aligned(sizeof(unsigned long)); +}; +#define LOCK_TRACE_SIZE_IN_LONGS \ + (sizeof(struct lock_trace) / sizeof(unsigned long)) /* - * Stack-trace: tightly packed array of stack backtrace - * addresses. Protected by the graph_lock. + * Stack-trace: sequence of lock_trace structures. Protected by the graph_lock. */ static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES]; +static struct hlist_head stack_trace_hash[STACK_TRACE_HASH_SIZE]; + +static bool traces_identical(struct lock_trace *t1, struct lock_trace *t2) +{ + return t1->hash == t2->hash && t1->nr_entries == t2->nr_entries && + memcmp(t1->entries, t2->entries, + t1->nr_entries * sizeof(t1->entries[0])) == 0; +} -static int save_trace(struct lock_trace *trace) +static struct lock_trace *save_trace(void) { - unsigned long *entries = stack_trace + nr_stack_trace_entries; + struct lock_trace *trace, *t2; + struct hlist_head *hash_head; + u32 hash; unsigned int max_entries; - trace->offset = nr_stack_trace_entries; - max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries; - trace->nr_entries = stack_trace_save(entries, max_entries, 3); - nr_stack_trace_entries += trace->nr_entries; + BUILD_BUG_ON_NOT_POWER_OF_2(STACK_TRACE_HASH_SIZE); + BUILD_BUG_ON(LOCK_TRACE_SIZE_IN_LONGS >= MAX_STACK_TRACE_ENTRIES); + + trace = (struct lock_trace *)(stack_trace + nr_stack_trace_entries); + max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries - + LOCK_TRACE_SIZE_IN_LONGS; + trace->nr_entries = stack_trace_save(trace->entries, max_entries, 3); - if (nr_stack_trace_entries >= MAX_STACK_TRACE_ENTRIES-1) { + if (nr_stack_trace_entries >= MAX_STACK_TRACE_ENTRIES - + LOCK_TRACE_SIZE_IN_LONGS - 1) { if (!debug_locks_off_graph_unlock()) - return 0; + return NULL; print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!"); dump_stack(); - return 0; + return NULL; } - return 1; + hash = jhash(trace->entries, trace->nr_entries * + sizeof(trace->entries[0]), 0); + trace->hash = hash; + hash_head = stack_trace_hash + (hash & (STACK_TRACE_HASH_SIZE - 1)); + hlist_for_each_entry(t2, hash_head, hash_entry) { + if (traces_identical(trace, t2)) + return t2; + } + nr_stack_trace_entries += LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries; + hlist_add_head(&trace->hash_entry, hash_head); + + return trace; } #endif @@ -1235,7 +1274,7 @@ static struct lock_list *alloc_list_entry(void) static int add_lock_to_list(struct lock_class *this, struct lock_class *links_to, struct list_head *head, unsigned long ip, int distance, - struct lock_trace *trace) + const struct lock_trace *trace) { struct lock_list *entry; /* @@ -1249,7 +1288,7 @@ static int add_lock_to_list(struct lock_class *this, entry->class = this; entry->links_to = links_to; entry->distance = distance; - entry->trace = *trace; + entry->trace = trace; /* * Both allocation and removal are done under the graph lock; but * iteration is under RCU-sched; see look_up_lock_class() and @@ -1470,11 +1509,10 @@ static inline int __bfs_backwards(struct lock_list *src_entry, } -static void print_lock_trace(struct lock_trace *trace, unsigned int spaces) +static void print_lock_trace(const struct lock_trace *trace, + unsigned int spaces) { - unsigned long *entries = stack_trace + trace->offset; - - stack_trace_print(entries, trace->nr_entries, spaces); + stack_trace_print(trace->entries, trace->nr_entries, spaces); } /* @@ -1489,7 +1527,7 @@ print_circular_bug_entry(struct lock_list *target, int depth) printk("\n-> #%u", depth); print_lock_name(target->class); printk(KERN_CONT ":\n"); - print_lock_trace(&target->trace, 6); + print_lock_trace(target->trace, 6); } static void @@ -1592,7 +1630,8 @@ static noinline void print_circular_bug(struct lock_list *this, if (!debug_locks_off_graph_unlock() || debug_locks_silent) return; - if (!save_trace(&this->trace)) + this->trace = save_trace(); + if (!this->trace) return; depth = get_lock_depth(target); @@ -1715,7 +1754,7 @@ check_path(struct lock_class *target, struct lock_list *src_entry, */ static noinline int check_noncircular(struct held_lock *src, struct held_lock *target, - struct lock_trace *trace) + struct lock_trace **const trace) { int ret; struct lock_list *uninitialized_var(target_entry); @@ -1729,13 +1768,13 @@ check_noncircular(struct held_lock *src, struct held_lock *target, ret = check_path(hlock_class(target), &src_entry, &target_entry); if (unlikely(!ret)) { - if (!trace->nr_entries) { + if (!*trace) { /* * If save_trace fails here, the printing might * trigger a WARN but because of the !nr_entries it * should not do bad things. */ - save_trace(trace); + *trace = save_trace(); } print_circular_bug(&src_entry, target_entry, src, target); @@ -1859,7 +1898,7 @@ static void print_lock_class_header(struct lock_class *class, int depth) len += printk("%*s %s", depth, "", usage_str[bit]); len += printk(KERN_CONT " at:\n"); - print_lock_trace(class->usage_traces + bit, len); + print_lock_trace(class->usage_traces[bit], len); } } printk("%*s }\n", depth, ""); @@ -1884,7 +1923,7 @@ print_shortest_lock_dependencies(struct lock_list *leaf, do { print_lock_class_header(entry->class, depth); printk("%*s ... acquired at:\n", depth, ""); - print_lock_trace(&entry->trace, 2); + print_lock_trace(entry->trace, 2); printk("\n"); if (depth == 0 && (entry != root)) { @@ -1995,14 +2034,14 @@ print_bad_irq_dependency(struct task_struct *curr, print_lock_name(backwards_entry->class); pr_warn("\n... which became %s-irq-safe at:\n", irqclass); - print_lock_trace(backwards_entry->class->usage_traces + bit1, 1); + print_lock_trace(backwards_entry->class->usage_traces[bit1], 1); pr_warn("\nto a %s-irq-unsafe lock:\n", irqclass); print_lock_name(forwards_entry->class); pr_warn("\n... which became %s-irq-unsafe at:\n", irqclass); pr_warn("..."); - print_lock_trace(forwards_entry->class->usage_traces + bit2, 1); + print_lock_trace(forwards_entry->class->usage_traces[bit2], 1); pr_warn("\nother info that might help us debug this:\n\n"); print_irq_lock_scenario(backwards_entry, forwards_entry, @@ -2011,13 +2050,15 @@ print_bad_irq_dependency(struct task_struct *curr, lockdep_print_held_locks(curr); pr_warn("\nthe dependencies between %s-irq-safe lock and the holding lock:\n", irqclass); - if (!save_trace(&prev_root->trace)) + prev_root->trace = save_trace(); + if (!prev_root->trace) return; print_shortest_lock_dependencies(backwards_entry, prev_root); pr_warn("\nthe dependencies between the lock to be acquired"); pr_warn(" and %s-irq-unsafe lock:\n", irqclass); - if (!save_trace(&next_root->trace)) + next_root->trace = save_trace(); + if (!next_root->trace) return; print_shortest_lock_dependencies(forwards_entry, next_root); @@ -2369,7 +2410,8 @@ check_deadlock(struct task_struct *curr, struct held_lock *next) */ static int check_prev_add(struct task_struct *curr, struct held_lock *prev, - struct held_lock *next, int distance, struct lock_trace *trace) + struct held_lock *next, int distance, + struct lock_trace **const trace) { struct lock_list *entry; int ret; @@ -2444,8 +2486,11 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev, return ret; #endif - if (!trace->nr_entries && !save_trace(trace)) - return 0; + if (!*trace) { + *trace = save_trace(); + if (!*trace) + return 0; + } /* * Ok, all validations passed, add the new lock @@ -2453,14 +2498,14 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev, */ ret = add_lock_to_list(hlock_class(next), hlock_class(prev), &hlock_class(prev)->locks_after, - next->acquire_ip, distance, trace); + next->acquire_ip, distance, *trace); if (!ret) return 0; ret = add_lock_to_list(hlock_class(prev), hlock_class(next), &hlock_class(next)->locks_before, - next->acquire_ip, distance, trace); + next->acquire_ip, distance, *trace); if (!ret) return 0; @@ -2476,7 +2521,7 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev, static int check_prevs_add(struct task_struct *curr, struct held_lock *next) { - struct lock_trace trace = { .nr_entries = 0 }; + struct lock_trace *trace = NULL; int depth = curr->lockdep_depth; struct held_lock *hlock; @@ -3015,7 +3060,7 @@ print_usage_bug(struct task_struct *curr, struct held_lock *this, print_lock(this); pr_warn("{%s} state was registered at:\n", usage_str[prev_bit]); - print_lock_trace(hlock_class(this)->usage_traces + prev_bit, 1); + print_lock_trace(hlock_class(this)->usage_traces[prev_bit], 1); print_irqtrace_events(curr); pr_warn("\nother info that might help us debug this:\n"); @@ -3096,7 +3141,8 @@ print_irq_inversion_bug(struct task_struct *curr, lockdep_print_held_locks(curr); pr_warn("\nthe shortest dependencies between 2nd lock and 1st lock:\n"); - if (!save_trace(&root->trace)) + root->trace = save_trace(); + if (!root->trace) return; print_shortest_lock_dependencies(other, root); @@ -3580,7 +3626,7 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this, hlock_class(this)->usage_mask |= new_mask; - if (!save_trace(hlock_class(this)->usage_traces + new_bit)) + if (!(hlock_class(this)->usage_traces[new_bit] = save_trace())) return 0; switch (new_bit) { @@ -5157,6 +5203,12 @@ void __init lockdep_init(void) ) / 1024 ); +#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) + printk(" memory used for stack traces: %zu kB\n", + (sizeof(stack_trace) + sizeof(stack_trace_hash)) / 1024 + ); +#endif + printk(" per task-struct memory footprint: %zu bytes\n", sizeof(((struct task_struct *)NULL)->held_locks)); } diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h index 2e518369add4..93a008bf77db 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -92,6 +92,7 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ = #define MAX_LOCKDEP_ENTRIES 16384UL #define MAX_LOCKDEP_CHAINS_BITS 15 #define MAX_STACK_TRACE_ENTRIES 262144UL +#define STACK_TRACE_HASH_SIZE 8192 #else #define MAX_LOCKDEP_ENTRIES 32768UL @@ -102,6 +103,7 @@ static const unsigned long LOCKF_USED_IN_IRQ_READ = * addresses. Protected by the hash_lock. */ #define MAX_STACK_TRACE_ENTRIES 524288UL +#define STACK_TRACE_HASH_SIZE 16384 #endif #define MAX_LOCKDEP_CHAINS (1UL << MAX_LOCKDEP_CHAINS_BITS) ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 4/4] locking/lockdep: Report more stack trace statistics 2019-07-22 18:24 [PATCH 0/4] Lockdep: Reduce stack trace memory usage Bart Van Assche ` (2 preceding siblings ...) 2019-07-22 18:24 ` [PATCH 3/4] locking/lockdep: Reduce space occupied by stack traces Bart Van Assche @ 2019-07-22 18:24 ` Bart Van Assche 2019-07-25 16:10 ` [tip:locking/core] " tip-bot for Bart Van Assche 2019-07-23 9:27 ` [PATCH 0/4] Lockdep: Reduce stack trace memory usage Peter Zijlstra 4 siblings, 1 reply; 12+ messages in thread From: Bart Van Assche @ 2019-07-22 18:24 UTC (permalink / raw) To: Peter Zijlstra Cc: Ingo Molnar, linux-kernel, Bart Van Assche, Thomas Gleixner, Will Deacon, Waiman Long Report the number of stack traces and the number of stack trace hash chains. These two numbers are useful because these allow to estimate the number of stack trace hash collisions. Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Will Deacon <will.deacon@arm.com> Cc: Waiman Long <longman@redhat.com> Signed-off-by: Bart Van Assche <bvanassche@acm.org> --- kernel/locking/lockdep.c | 29 +++++++++++++++++++++++++++++ kernel/locking/lockdep_internals.h | 4 ++++ kernel/locking/lockdep_proc.c | 6 ++++++ 3 files changed, 39 insertions(+) diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 19eace34b5fa..320346b3bdbb 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -516,6 +516,35 @@ static struct lock_trace *save_trace(void) return trace; } + +/* Return the number of stack traces in the stack_trace[] array. */ +u64 lockdep_stack_trace_count(void) +{ + struct lock_trace *trace; + u64 c = 0; + int i; + + for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++) { + hlist_for_each_entry(trace, &stack_trace_hash[i], hash_entry) { + c++; + } + } + + return c; +} + +/* Return the number of stack hash chains that have at least one stack trace. */ +u64 lockdep_stack_hash_count(void) +{ + u64 c = 0; + int i; + + for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++) + if (!hlist_empty(&stack_trace_hash[i])) + c++; + + return c; +} #endif unsigned int nr_hardirq_chains; diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h index 93a008bf77db..18d85aebbb57 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -140,6 +140,10 @@ extern unsigned int max_bfs_queue_depth; #ifdef CONFIG_PROVE_LOCKING extern unsigned long lockdep_count_forward_deps(struct lock_class *); extern unsigned long lockdep_count_backward_deps(struct lock_class *); +#ifdef CONFIG_TRACE_IRQFLAGS +u64 lockdep_stack_trace_count(void); +u64 lockdep_stack_hash_count(void); +#endif #else static inline unsigned long lockdep_count_forward_deps(struct lock_class *class) diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c index 1ba5780182e7..64b5b47ab117 100644 --- a/kernel/locking/lockdep_proc.c +++ b/kernel/locking/lockdep_proc.c @@ -284,6 +284,12 @@ static int lockdep_stats_show(struct seq_file *m, void *v) nr_process_chains); seq_printf(m, " stack-trace entries: %11lu [max: %lu]\n", nr_stack_trace_entries, MAX_STACK_TRACE_ENTRIES); +#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) + seq_printf(m, " number of stack traces: %llu\n", + lockdep_stack_trace_count()); + seq_printf(m, " number of stack hash chains: %llu\n", + lockdep_stack_hash_count()); +#endif seq_printf(m, " combined max dependencies: %11u\n", (nr_hardirq_chains + 1) * (nr_softirq_chains + 1) * -- 2.22.0.657.g960e92d24f-goog ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [tip:locking/core] locking/lockdep: Report more stack trace statistics 2019-07-22 18:24 ` [PATCH 4/4] locking/lockdep: Report more stack trace statistics Bart Van Assche @ 2019-07-25 16:10 ` tip-bot for Bart Van Assche 0 siblings, 0 replies; 12+ messages in thread From: tip-bot for Bart Van Assche @ 2019-07-25 16:10 UTC (permalink / raw) To: linux-tip-commits Cc: bvanassche, tglx, linux-kernel, will.deacon, torvalds, peterz, longman, hpa, mingo Commit-ID: 8c779229d0f4fe83ead90bdcbbf08b02989aa200 Gitweb: https://git.kernel.org/tip/8c779229d0f4fe83ead90bdcbbf08b02989aa200 Author: Bart Van Assche <bvanassche@acm.org> AuthorDate: Mon, 22 Jul 2019 11:24:43 -0700 Committer: Ingo Molnar <mingo@kernel.org> CommitDate: Thu, 25 Jul 2019 15:43:28 +0200 locking/lockdep: Report more stack trace statistics Report the number of stack traces and the number of stack trace hash chains. These two numbers are useful because these allow to estimate the number of stack trace hash collisions. Signed-off-by: Bart Van Assche <bvanassche@acm.org> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Waiman Long <longman@redhat.com> Cc: Will Deacon <will.deacon@arm.com> Link: https://lkml.kernel.org/r/20190722182443.216015-5-bvanassche@acm.org Signed-off-by: Ingo Molnar <mingo@kernel.org> --- kernel/locking/lockdep.c | 29 +++++++++++++++++++++++++++++ kernel/locking/lockdep_internals.h | 4 ++++ kernel/locking/lockdep_proc.c | 6 ++++++ 3 files changed, 39 insertions(+) diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 1a96869cb2f0..3c3902c40a0e 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -516,6 +516,35 @@ static struct lock_trace *save_trace(void) return trace; } + +/* Return the number of stack traces in the stack_trace[] array. */ +u64 lockdep_stack_trace_count(void) +{ + struct lock_trace *trace; + u64 c = 0; + int i; + + for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++) { + hlist_for_each_entry(trace, &stack_trace_hash[i], hash_entry) { + c++; + } + } + + return c; +} + +/* Return the number of stack hash chains that have at least one stack trace. */ +u64 lockdep_stack_hash_count(void) +{ + u64 c = 0; + int i; + + for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++) + if (!hlist_empty(&stack_trace_hash[i])) + c++; + + return c; +} #endif unsigned int nr_hardirq_chains; diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h index 93a008bf77db..18d85aebbb57 100644 --- a/kernel/locking/lockdep_internals.h +++ b/kernel/locking/lockdep_internals.h @@ -140,6 +140,10 @@ extern unsigned int max_bfs_queue_depth; #ifdef CONFIG_PROVE_LOCKING extern unsigned long lockdep_count_forward_deps(struct lock_class *); extern unsigned long lockdep_count_backward_deps(struct lock_class *); +#ifdef CONFIG_TRACE_IRQFLAGS +u64 lockdep_stack_trace_count(void); +u64 lockdep_stack_hash_count(void); +#endif #else static inline unsigned long lockdep_count_forward_deps(struct lock_class *class) diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c index ed9842425cac..dadb7b7fba37 100644 --- a/kernel/locking/lockdep_proc.c +++ b/kernel/locking/lockdep_proc.c @@ -285,6 +285,12 @@ static int lockdep_stats_show(struct seq_file *m, void *v) nr_process_chains); seq_printf(m, " stack-trace entries: %11lu [max: %lu]\n", nr_stack_trace_entries, MAX_STACK_TRACE_ENTRIES); +#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) + seq_printf(m, " number of stack traces: %llu\n", + lockdep_stack_trace_count()); + seq_printf(m, " number of stack hash chains: %llu\n", + lockdep_stack_hash_count()); +#endif seq_printf(m, " combined max dependencies: %11u\n", (nr_hardirq_chains + 1) * (nr_softirq_chains + 1) * ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH 0/4] Lockdep: Reduce stack trace memory usage 2019-07-22 18:24 [PATCH 0/4] Lockdep: Reduce stack trace memory usage Bart Van Assche ` (3 preceding siblings ...) 2019-07-22 18:24 ` [PATCH 4/4] locking/lockdep: Report more stack trace statistics Bart Van Assche @ 2019-07-23 9:27 ` Peter Zijlstra 4 siblings, 0 replies; 12+ messages in thread From: Peter Zijlstra @ 2019-07-23 9:27 UTC (permalink / raw) To: Bart Van Assche; +Cc: Ingo Molnar, linux-kernel On Mon, Jul 22, 2019 at 11:24:39AM -0700, Bart Van Assche wrote: > Hi Peter, > > An unfortunate side effect of commit 669de8bda87b ("kernel/workqueue: Use > dynamic lockdep keys for workqueues") is that all stack traces associated > with the lockdep key are leaked when a workqueue is destroyed. Fix this by > storing each unique stack trace once. Please consider this patch series > for Linux kernel v5.4. > > Thanks, > > Bart. > > Bart Van Assche (4): > locking/lockdep: Make it clear that what lock_class::key points at is > not modified > stacktrace: Constify 'entries' arguments > locking/lockdep: Reduce space occupied by stack traces > locking/lockdep: Report more stack trace statistics > > include/linux/lockdep.h | 11 +- > include/linux/stacktrace.h | 4 +- > kernel/locking/lockdep.c | 159 ++++++++++++++++++++++------- > kernel/locking/lockdep_internals.h | 9 +- > kernel/locking/lockdep_proc.c | 8 +- > kernel/stacktrace.c | 4 +- > 6 files changed, 143 insertions(+), 52 deletions(-) Thanks a lot for doing this Bart, excellent stuff! ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2019-07-25 16:11 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-07-22 18:24 [PATCH 0/4] Lockdep: Reduce stack trace memory usage Bart Van Assche 2019-07-22 18:24 ` [PATCH 1/4] locking/lockdep: Make it clear that what lock_class::key points at is not modified Bart Van Assche 2019-07-25 16:08 ` [tip:locking/core] " tip-bot for Bart Van Assche 2019-07-22 18:24 ` [PATCH 2/4] stacktrace: Constify 'entries' arguments Bart Van Assche 2019-07-25 16:09 ` [tip:locking/core] " tip-bot for Bart Van Assche 2019-07-22 18:24 ` [PATCH 3/4] locking/lockdep: Reduce space occupied by stack traces Bart Van Assche 2019-07-24 4:56 ` Eric Biggers 2019-07-24 15:47 ` Bart Van Assche 2019-07-25 16:10 ` [tip:locking/core] " tip-bot for Bart Van Assche 2019-07-22 18:24 ` [PATCH 4/4] locking/lockdep: Report more stack trace statistics Bart Van Assche 2019-07-25 16:10 ` [tip:locking/core] " tip-bot for Bart Van Assche 2019-07-23 9:27 ` [PATCH 0/4] Lockdep: Reduce stack trace memory usage Peter Zijlstra
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).