xref: /linux/kernel/locking/lockdep.c (revision ec03de73b1e11e5b0c30d3c35e09dffe7496bb06)
1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * kernel/lockdep.c
4  *
5  * Runtime locking correctness validator
6  *
7  * Started by Ingo Molnar:
8  *
9  *  Copyright (C) 2006,2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
10  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
11  *
12  * this code maps all the lock dependencies as they occur in a live kernel
13  * and will warn about the following classes of locking bugs:
14  *
15  * - lock inversion scenarios
16  * - circular lock dependencies
17  * - hardirq/softirq safe/unsafe locking bugs
18  *
19  * Bugs are reported even if the current locking scenario does not cause
20  * any deadlock at this point.
21  *
22  * I.e. if anytime in the past two locks were taken in a different order,
23  * even if it happened for another task, even if those were different
24  * locks (but of the same class as this lock), this code will detect it.
25  *
26  * Thanks to Arjan van de Ven for coming up with the initial idea of
27  * mapping lock dependencies runtime.
28  */
29 #define DISABLE_BRANCH_PROFILING
30 #include <linux/mutex.h>
31 #include <linux/sched.h>
32 #include <linux/sched/clock.h>
33 #include <linux/sched/task.h>
34 #include <linux/sched/mm.h>
35 #include <linux/delay.h>
36 #include <linux/module.h>
37 #include <linux/proc_fs.h>
38 #include <linux/seq_file.h>
39 #include <linux/spinlock.h>
40 #include <linux/kallsyms.h>
41 #include <linux/interrupt.h>
42 #include <linux/stacktrace.h>
43 #include <linux/debug_locks.h>
44 #include <linux/irqflags.h>
45 #include <linux/utsname.h>
46 #include <linux/hash.h>
47 #include <linux/ftrace.h>
48 #include <linux/stringify.h>
49 #include <linux/bitmap.h>
50 #include <linux/bitops.h>
51 #include <linux/gfp.h>
52 #include <linux/random.h>
53 #include <linux/jhash.h>
54 #include <linux/nmi.h>
55 #include <linux/rcupdate.h>
56 #include <linux/kprobes.h>
57 #include <linux/lockdep.h>
58 #include <linux/context_tracking.h>
59 #include <linux/console.h>
60 
61 #include <asm/sections.h>
62 
63 #include "lockdep_internals.h"
64 
65 #include <trace/events/lock.h>
66 
67 #ifdef CONFIG_PROVE_LOCKING
68 static int prove_locking = 1;
69 module_param(prove_locking, int, 0644);
70 #else
71 #define prove_locking 0
72 #endif
73 
74 #ifdef CONFIG_LOCK_STAT
75 static int lock_stat = 1;
76 module_param(lock_stat, int, 0644);
77 #else
78 #define lock_stat 0
79 #endif
80 
81 #ifdef CONFIG_SYSCTL
82 static struct ctl_table kern_lockdep_table[] = {
83 #ifdef CONFIG_PROVE_LOCKING
84 	{
85 		.procname       = "prove_locking",
86 		.data           = &prove_locking,
87 		.maxlen         = sizeof(int),
88 		.mode           = 0644,
89 		.proc_handler   = proc_dointvec,
90 	},
91 #endif /* CONFIG_PROVE_LOCKING */
92 #ifdef CONFIG_LOCK_STAT
93 	{
94 		.procname       = "lock_stat",
95 		.data           = &lock_stat,
96 		.maxlen         = sizeof(int),
97 		.mode           = 0644,
98 		.proc_handler   = proc_dointvec,
99 	},
100 #endif /* CONFIG_LOCK_STAT */
101 };
102 
kernel_lockdep_sysctls_init(void)103 static __init int kernel_lockdep_sysctls_init(void)
104 {
105 	register_sysctl_init("kernel", kern_lockdep_table);
106 	return 0;
107 }
108 late_initcall(kernel_lockdep_sysctls_init);
109 #endif /* CONFIG_SYSCTL */
110 
111 DEFINE_PER_CPU(unsigned int, lockdep_recursion);
112 EXPORT_PER_CPU_SYMBOL_GPL(lockdep_recursion);
113 
lockdep_enabled(void)114 static __always_inline bool lockdep_enabled(void)
115 {
116 	if (!debug_locks)
117 		return false;
118 
119 	if (this_cpu_read(lockdep_recursion))
120 		return false;
121 
122 	if (current->lockdep_recursion)
123 		return false;
124 
125 	return true;
126 }
127 
128 /*
129  * lockdep_lock: protects the lockdep graph, the hashes and the
130  *               class/list/hash allocators.
131  *
132  * This is one of the rare exceptions where it's justified
133  * to use a raw spinlock - we really dont want the spinlock
134  * code to recurse back into the lockdep code...
135  */
136 static arch_spinlock_t __lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
137 static struct task_struct *__owner;
138 
lockdep_lock(void)139 static inline void lockdep_lock(void)
140 {
141 	DEBUG_LOCKS_WARN_ON(!irqs_disabled());
142 
143 	__this_cpu_inc(lockdep_recursion);
144 	arch_spin_lock(&__lock);
145 	__owner = current;
146 }
147 
lockdep_unlock(void)148 static inline void lockdep_unlock(void)
149 {
150 	DEBUG_LOCKS_WARN_ON(!irqs_disabled());
151 
152 	if (debug_locks && DEBUG_LOCKS_WARN_ON(__owner != current))
153 		return;
154 
155 	__owner = NULL;
156 	arch_spin_unlock(&__lock);
157 	__this_cpu_dec(lockdep_recursion);
158 }
159 
lockdep_assert_locked(void)160 static inline bool lockdep_assert_locked(void)
161 {
162 	return DEBUG_LOCKS_WARN_ON(__owner != current);
163 }
164 
165 static struct task_struct *lockdep_selftest_task_struct;
166 
167 
graph_lock(void)168 static int graph_lock(void)
169 {
170 	lockdep_lock();
171 	/*
172 	 * Make sure that if another CPU detected a bug while
173 	 * walking the graph we dont change it (while the other
174 	 * CPU is busy printing out stuff with the graph lock
175 	 * dropped already)
176 	 */
177 	if (!debug_locks) {
178 		lockdep_unlock();
179 		return 0;
180 	}
181 	return 1;
182 }
183 
graph_unlock(void)184 static inline void graph_unlock(void)
185 {
186 	lockdep_unlock();
187 }
188 
189 /*
190  * Turn lock debugging off and return with 0 if it was off already,
191  * and also release the graph lock:
192  */
debug_locks_off_graph_unlock(void)193 static inline int debug_locks_off_graph_unlock(void)
194 {
195 	int ret = debug_locks_off();
196 
197 	lockdep_unlock();
198 
199 	return ret;
200 }
201 
202 unsigned long nr_list_entries;
203 static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
204 static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);
205 
206 /*
207  * All data structures here are protected by the global debug_lock.
208  *
209  * nr_lock_classes is the number of elements of lock_classes[] that is
210  * in use.
211  */
212 #define KEYHASH_BITS		(MAX_LOCKDEP_KEYS_BITS - 1)
213 #define KEYHASH_SIZE		(1UL << KEYHASH_BITS)
214 static struct hlist_head lock_keys_hash[KEYHASH_SIZE];
215 unsigned long nr_lock_classes;
216 unsigned long nr_zapped_classes;
217 unsigned long max_lock_class_idx;
218 struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
219 DECLARE_BITMAP(lock_classes_in_use, MAX_LOCKDEP_KEYS);
220 
hlock_class(struct held_lock * hlock)221 static inline struct lock_class *hlock_class(struct held_lock *hlock)
222 {
223 	unsigned int class_idx = hlock->class_idx;
224 
225 	/* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfield */
226 	barrier();
227 
228 	if (!test_bit(class_idx, lock_classes_in_use)) {
229 		/*
230 		 * Someone passed in garbage, we give up.
231 		 */
232 		DEBUG_LOCKS_WARN_ON(1);
233 		return NULL;
234 	}
235 
236 	/*
237 	 * At this point, if the passed hlock->class_idx is still garbage,
238 	 * we just have to live with it
239 	 */
240 	return lock_classes + class_idx;
241 }
242 
243 #ifdef CONFIG_LOCK_STAT
244 static DEFINE_PER_CPU(struct lock_class_stats[MAX_LOCKDEP_KEYS], cpu_lock_stats);
245 
lockstat_clock(void)246 static inline u64 lockstat_clock(void)
247 {
248 	return local_clock();
249 }
250 
lock_point(unsigned long points[],unsigned long ip)251 static int lock_point(unsigned long points[], unsigned long ip)
252 {
253 	int i;
254 
255 	for (i = 0; i < LOCKSTAT_POINTS; i++) {
256 		if (points[i] == 0) {
257 			points[i] = ip;
258 			break;
259 		}
260 		if (points[i] == ip)
261 			break;
262 	}
263 
264 	return i;
265 }
266 
lock_time_inc(struct lock_time * lt,u64 time)267 static void lock_time_inc(struct lock_time *lt, u64 time)
268 {
269 	if (time > lt->max)
270 		lt->max = time;
271 
272 	if (time < lt->min || !lt->nr)
273 		lt->min = time;
274 
275 	lt->total += time;
276 	lt->nr++;
277 }
278 
lock_time_add(struct lock_time * src,struct lock_time * dst)279 static inline void lock_time_add(struct lock_time *src, struct lock_time *dst)
280 {
281 	if (!src->nr)
282 		return;
283 
284 	if (src->max > dst->max)
285 		dst->max = src->max;
286 
287 	if (src->min < dst->min || !dst->nr)
288 		dst->min = src->min;
289 
290 	dst->total += src->total;
291 	dst->nr += src->nr;
292 }
293 
lock_stats(struct lock_class * class)294 struct lock_class_stats lock_stats(struct lock_class *class)
295 {
296 	struct lock_class_stats stats;
297 	int cpu, i;
298 
299 	memset(&stats, 0, sizeof(struct lock_class_stats));
300 	for_each_possible_cpu(cpu) {
301 		struct lock_class_stats *pcs =
302 			&per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
303 
304 		for (i = 0; i < ARRAY_SIZE(stats.contention_point); i++)
305 			stats.contention_point[i] += pcs->contention_point[i];
306 
307 		for (i = 0; i < ARRAY_SIZE(stats.contending_point); i++)
308 			stats.contending_point[i] += pcs->contending_point[i];
309 
310 		lock_time_add(&pcs->read_waittime, &stats.read_waittime);
311 		lock_time_add(&pcs->write_waittime, &stats.write_waittime);
312 
313 		lock_time_add(&pcs->read_holdtime, &stats.read_holdtime);
314 		lock_time_add(&pcs->write_holdtime, &stats.write_holdtime);
315 
316 		for (i = 0; i < ARRAY_SIZE(stats.bounces); i++)
317 			stats.bounces[i] += pcs->bounces[i];
318 	}
319 
320 	return stats;
321 }
322 
clear_lock_stats(struct lock_class * class)323 void clear_lock_stats(struct lock_class *class)
324 {
325 	int cpu;
326 
327 	for_each_possible_cpu(cpu) {
328 		struct lock_class_stats *cpu_stats =
329 			&per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
330 
331 		memset(cpu_stats, 0, sizeof(struct lock_class_stats));
332 	}
333 	memset(class->contention_point, 0, sizeof(class->contention_point));
334 	memset(class->contending_point, 0, sizeof(class->contending_point));
335 }
336 
get_lock_stats(struct lock_class * class)337 static struct lock_class_stats *get_lock_stats(struct lock_class *class)
338 {
339 	return &this_cpu_ptr(cpu_lock_stats)[class - lock_classes];
340 }
341 
lock_release_holdtime(struct held_lock * hlock)342 static void lock_release_holdtime(struct held_lock *hlock)
343 {
344 	struct lock_class_stats *stats;
345 	u64 holdtime;
346 
347 	if (!lock_stat)
348 		return;
349 
350 	holdtime = lockstat_clock() - hlock->holdtime_stamp;
351 
352 	stats = get_lock_stats(hlock_class(hlock));
353 	if (hlock->read)
354 		lock_time_inc(&stats->read_holdtime, holdtime);
355 	else
356 		lock_time_inc(&stats->write_holdtime, holdtime);
357 }
358 #else
lock_release_holdtime(struct held_lock * hlock)359 static inline void lock_release_holdtime(struct held_lock *hlock)
360 {
361 }
362 #endif
363 
364 /*
365  * We keep a global list of all lock classes. The list is only accessed with
366  * the lockdep spinlock lock held. free_lock_classes is a list with free
367  * elements. These elements are linked together by the lock_entry member in
368  * struct lock_class.
369  */
370 static LIST_HEAD(all_lock_classes);
371 static LIST_HEAD(free_lock_classes);
372 
373 /**
374  * struct pending_free - information about data structures about to be freed
375  * @zapped: Head of a list with struct lock_class elements.
376  * @lock_chains_being_freed: Bitmap that indicates which lock_chains[] elements
377  *	are about to be freed.
378  */
379 struct pending_free {
380 	struct list_head zapped;
381 	DECLARE_BITMAP(lock_chains_being_freed, MAX_LOCKDEP_CHAINS);
382 };
383 
384 /**
385  * struct delayed_free - data structures used for delayed freeing
386  *
387  * A data structure for delayed freeing of data structures that may be
388  * accessed by RCU readers at the time these were freed.
389  *
390  * @rcu_head:  Used to schedule an RCU callback for freeing data structures.
391  * @index:     Index of @pf to which freed data structures are added.
392  * @scheduled: Whether or not an RCU callback has been scheduled.
393  * @pf:        Array with information about data structures about to be freed.
394  */
395 static struct delayed_free {
396 	struct rcu_head		rcu_head;
397 	int			index;
398 	int			scheduled;
399 	struct pending_free	pf[2];
400 } delayed_free;
401 
402 /*
403  * The lockdep classes are in a hash-table as well, for fast lookup:
404  */
405 #define CLASSHASH_BITS		(MAX_LOCKDEP_KEYS_BITS - 1)
406 #define CLASSHASH_SIZE		(1UL << CLASSHASH_BITS)
407 #define __classhashfn(key)	hash_long((unsigned long)key, CLASSHASH_BITS)
408 #define classhashentry(key)	(classhash_table + __classhashfn((key)))
409 
410 static struct hlist_head classhash_table[CLASSHASH_SIZE];
411 
412 /*
413  * We put the lock dependency chains into a hash-table as well, to cache
414  * their existence:
415  */
416 #define CHAINHASH_BITS		(MAX_LOCKDEP_CHAINS_BITS-1)
417 #define CHAINHASH_SIZE		(1UL << CHAINHASH_BITS)
418 #define __chainhashfn(chain)	hash_long(chain, CHAINHASH_BITS)
419 #define chainhashentry(chain)	(chainhash_table + __chainhashfn((chain)))
420 
421 static struct hlist_head chainhash_table[CHAINHASH_SIZE];
422 
423 /*
424  * the id of held_lock
425  */
hlock_id(struct held_lock * hlock)426 static inline u16 hlock_id(struct held_lock *hlock)
427 {
428 	BUILD_BUG_ON(MAX_LOCKDEP_KEYS_BITS + 2 > 16);
429 
430 	return (hlock->class_idx | (hlock->read << MAX_LOCKDEP_KEYS_BITS));
431 }
432 
chain_hlock_class_idx(u16 hlock_id)433 static inline unsigned int chain_hlock_class_idx(u16 hlock_id)
434 {
435 	return hlock_id & (MAX_LOCKDEP_KEYS - 1);
436 }
437 
438 /*
439  * The hash key of the lock dependency chains is a hash itself too:
440  * it's a hash of all locks taken up to that lock, including that lock.
441  * It's a 64-bit hash, because it's important for the keys to be
442  * unique.
443  */
iterate_chain_key(u64 key,u32 idx)444 static inline u64 iterate_chain_key(u64 key, u32 idx)
445 {
446 	u32 k0 = key, k1 = key >> 32;
447 
448 	__jhash_mix(idx, k0, k1); /* Macro that modifies arguments! */
449 
450 	return k0 | (u64)k1 << 32;
451 }
452 
lockdep_init_task(struct task_struct * task)453 void lockdep_init_task(struct task_struct *task)
454 {
455 	task->lockdep_depth = 0; /* no locks held yet */
456 	task->curr_chain_key = INITIAL_CHAIN_KEY;
457 	task->lockdep_recursion = 0;
458 }
459 
lockdep_recursion_inc(void)460 static __always_inline void lockdep_recursion_inc(void)
461 {
462 	__this_cpu_inc(lockdep_recursion);
463 }
464 
lockdep_recursion_finish(void)465 static __always_inline void lockdep_recursion_finish(void)
466 {
467 	if (WARN_ON_ONCE(__this_cpu_dec_return(lockdep_recursion)))
468 		__this_cpu_write(lockdep_recursion, 0);
469 }
470 
lockdep_set_selftest_task(struct task_struct * task)471 void lockdep_set_selftest_task(struct task_struct *task)
472 {
473 	lockdep_selftest_task_struct = task;
474 }
475 
476 /*
477  * Debugging switches:
478  */
479 
480 #define VERBOSE			0
481 #define VERY_VERBOSE		0
482 
483 #if VERBOSE
484 # define HARDIRQ_VERBOSE	1
485 # define SOFTIRQ_VERBOSE	1
486 #else
487 # define HARDIRQ_VERBOSE	0
488 # define SOFTIRQ_VERBOSE	0
489 #endif
490 
491 #if VERBOSE || HARDIRQ_VERBOSE || SOFTIRQ_VERBOSE
492 /*
493  * Quick filtering for interesting events:
494  */
class_filter(struct lock_class * class)495 static int class_filter(struct lock_class *class)
496 {
497 #if 0
498 	/* Example */
499 	if (class->name_version == 1 &&
500 			!strcmp(class->name, "lockname"))
501 		return 1;
502 	if (class->name_version == 1 &&
503 			!strcmp(class->name, "&struct->lockfield"))
504 		return 1;
505 #endif
506 	/* Filter everything else. 1 would be to allow everything else */
507 	return 0;
508 }
509 #endif
510 
verbose(struct lock_class * class)511 static int verbose(struct lock_class *class)
512 {
513 #if VERBOSE
514 	return class_filter(class);
515 #endif
516 	return 0;
517 }
518 
print_lockdep_off(const char * bug_msg)519 static void print_lockdep_off(const char *bug_msg)
520 {
521 	printk(KERN_DEBUG "%s\n", bug_msg);
522 	printk(KERN_DEBUG "turning off the locking correctness validator.\n");
523 #ifdef CONFIG_LOCK_STAT
524 	printk(KERN_DEBUG "Please attach the output of /proc/lock_stat to the bug report\n");
525 #endif
526 }
527 
528 unsigned long nr_stack_trace_entries;
529 
530 #ifdef CONFIG_PROVE_LOCKING
531 /**
532  * struct lock_trace - single stack backtrace
533  * @hash_entry:	Entry in a stack_trace_hash[] list.
534  * @hash:	jhash() of @entries.
535  * @nr_entries:	Number of entries in @entries.
536  * @entries:	Actual stack backtrace.
537  */
538 struct lock_trace {
539 	struct hlist_node	hash_entry;
540 	u32			hash;
541 	u32			nr_entries;
542 	unsigned long		entries[] __aligned(sizeof(unsigned long));
543 };
544 #define LOCK_TRACE_SIZE_IN_LONGS				\
545 	(sizeof(struct lock_trace) / sizeof(unsigned long))
546 /*
547  * Stack-trace: sequence of lock_trace structures. Protected by the graph_lock.
548  */
549 static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES];
550 static struct hlist_head stack_trace_hash[STACK_TRACE_HASH_SIZE];
551 
traces_identical(struct lock_trace * t1,struct lock_trace * t2)552 static bool traces_identical(struct lock_trace *t1, struct lock_trace *t2)
553 {
554 	return t1->hash == t2->hash && t1->nr_entries == t2->nr_entries &&
555 		memcmp(t1->entries, t2->entries,
556 		       t1->nr_entries * sizeof(t1->entries[0])) == 0;
557 }
558 
save_trace(void)559 static struct lock_trace *save_trace(void)
560 {
561 	struct lock_trace *trace, *t2;
562 	struct hlist_head *hash_head;
563 	u32 hash;
564 	int max_entries;
565 
566 	BUILD_BUG_ON_NOT_POWER_OF_2(STACK_TRACE_HASH_SIZE);
567 	BUILD_BUG_ON(LOCK_TRACE_SIZE_IN_LONGS >= MAX_STACK_TRACE_ENTRIES);
568 
569 	trace = (struct lock_trace *)(stack_trace + nr_stack_trace_entries);
570 	max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries -
571 		LOCK_TRACE_SIZE_IN_LONGS;
572 
573 	if (max_entries <= 0) {
574 		if (!debug_locks_off_graph_unlock())
575 			return NULL;
576 
577 		nbcon_cpu_emergency_enter();
578 		print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!");
579 		dump_stack();
580 		nbcon_cpu_emergency_exit();
581 
582 		return NULL;
583 	}
584 	trace->nr_entries = stack_trace_save(trace->entries, max_entries, 3);
585 
586 	hash = jhash(trace->entries, trace->nr_entries *
587 		     sizeof(trace->entries[0]), 0);
588 	trace->hash = hash;
589 	hash_head = stack_trace_hash + (hash & (STACK_TRACE_HASH_SIZE - 1));
590 	hlist_for_each_entry(t2, hash_head, hash_entry) {
591 		if (traces_identical(trace, t2))
592 			return t2;
593 	}
594 	nr_stack_trace_entries += LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries;
595 	hlist_add_head(&trace->hash_entry, hash_head);
596 
597 	return trace;
598 }
599 
600 /* Return the number of stack traces in the stack_trace[] array. */
lockdep_stack_trace_count(void)601 u64 lockdep_stack_trace_count(void)
602 {
603 	struct lock_trace *trace;
604 	u64 c = 0;
605 	int i;
606 
607 	for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++) {
608 		hlist_for_each_entry(trace, &stack_trace_hash[i], hash_entry) {
609 			c++;
610 		}
611 	}
612 
613 	return c;
614 }
615 
616 /* Return the number of stack hash chains that have at least one stack trace. */
lockdep_stack_hash_count(void)617 u64 lockdep_stack_hash_count(void)
618 {
619 	u64 c = 0;
620 	int i;
621 
622 	for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++)
623 		if (!hlist_empty(&stack_trace_hash[i]))
624 			c++;
625 
626 	return c;
627 }
628 #endif
629 
630 unsigned int nr_hardirq_chains;
631 unsigned int nr_softirq_chains;
632 unsigned int nr_process_chains;
633 unsigned int max_lockdep_depth;
634 
635 #ifdef CONFIG_DEBUG_LOCKDEP
636 /*
637  * Various lockdep statistics:
638  */
639 DEFINE_PER_CPU(struct lockdep_stats, lockdep_stats);
640 #endif
641 
642 #ifdef CONFIG_PROVE_LOCKING
643 /*
644  * Locking printouts:
645  */
646 
647 #define __USAGE(__STATE)						\
648 	[LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE)"-W",	\
649 	[LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON-W",		\
650 	[LOCK_USED_IN_##__STATE##_READ] = "IN-"__stringify(__STATE)"-R",\
651 	[LOCK_ENABLED_##__STATE##_READ] = __stringify(__STATE)"-ON-R",
652 
653 static const char *usage_str[] =
654 {
655 #define LOCKDEP_STATE(__STATE) __USAGE(__STATE)
656 #include "lockdep_states.h"
657 #undef LOCKDEP_STATE
658 	[LOCK_USED] = "INITIAL USE",
659 	[LOCK_USED_READ] = "INITIAL READ USE",
660 	/* abused as string storage for verify_lock_unused() */
661 	[LOCK_USAGE_STATES] = "IN-NMI",
662 };
663 #endif
664 
__get_key_name(const struct lockdep_subclass_key * key,char * str)665 const char *__get_key_name(const struct lockdep_subclass_key *key, char *str)
666 {
667 	return kallsyms_lookup((unsigned long)key, NULL, NULL, NULL, str);
668 }
669 
lock_flag(enum lock_usage_bit bit)670 static inline unsigned long lock_flag(enum lock_usage_bit bit)
671 {
672 	return 1UL << bit;
673 }
674 
get_usage_char(struct lock_class * class,enum lock_usage_bit bit)675 static char get_usage_char(struct lock_class *class, enum lock_usage_bit bit)
676 {
677 	/*
678 	 * The usage character defaults to '.' (i.e., irqs disabled and not in
679 	 * irq context), which is the safest usage category.
680 	 */
681 	char c = '.';
682 
683 	/*
684 	 * The order of the following usage checks matters, which will
685 	 * result in the outcome character as follows:
686 	 *
687 	 * - '+': irq is enabled and not in irq context
688 	 * - '-': in irq context and irq is disabled
689 	 * - '?': in irq context and irq is enabled
690 	 */
691 	if (class->usage_mask & lock_flag(bit + LOCK_USAGE_DIR_MASK)) {
692 		c = '+';
693 		if (class->usage_mask & lock_flag(bit))
694 			c = '?';
695 	} else if (class->usage_mask & lock_flag(bit))
696 		c = '-';
697 
698 	return c;
699 }
700 
get_usage_chars(struct lock_class * class,char usage[LOCK_USAGE_CHARS])701 void get_usage_chars(struct lock_class *class, char usage[LOCK_USAGE_CHARS])
702 {
703 	int i = 0;
704 
705 #define LOCKDEP_STATE(__STATE) 						\
706 	usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE);	\
707 	usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_READ);
708 #include "lockdep_states.h"
709 #undef LOCKDEP_STATE
710 
711 	usage[i] = '\0';
712 }
713 
__print_lock_name(struct held_lock * hlock,struct lock_class * class)714 static void __print_lock_name(struct held_lock *hlock, struct lock_class *class)
715 {
716 	char str[KSYM_NAME_LEN];
717 	const char *name;
718 
719 	name = class->name;
720 	if (!name) {
721 		name = __get_key_name(class->key, str);
722 		printk(KERN_CONT "%s", name);
723 	} else {
724 		printk(KERN_CONT "%s", name);
725 		if (class->name_version > 1)
726 			printk(KERN_CONT "#%d", class->name_version);
727 		if (class->subclass)
728 			printk(KERN_CONT "/%d", class->subclass);
729 		if (hlock && class->print_fn)
730 			class->print_fn(hlock->instance);
731 	}
732 }
733 
print_lock_name(struct held_lock * hlock,struct lock_class * class)734 static void print_lock_name(struct held_lock *hlock, struct lock_class *class)
735 {
736 	char usage[LOCK_USAGE_CHARS];
737 
738 	get_usage_chars(class, usage);
739 
740 	printk(KERN_CONT " (");
741 	__print_lock_name(hlock, class);
742 	printk(KERN_CONT "){%s}-{%d:%d}", usage,
743 			class->wait_type_outer ?: class->wait_type_inner,
744 			class->wait_type_inner);
745 }
746 
print_lockdep_cache(struct lockdep_map * lock)747 static void print_lockdep_cache(struct lockdep_map *lock)
748 {
749 	const char *name;
750 	char str[KSYM_NAME_LEN];
751 
752 	name = lock->name;
753 	if (!name)
754 		name = __get_key_name(lock->key->subkeys, str);
755 
756 	printk(KERN_CONT "%s", name);
757 }
758 
print_lock(struct held_lock * hlock)759 static void print_lock(struct held_lock *hlock)
760 {
761 	/*
762 	 * We can be called locklessly through debug_show_all_locks() so be
763 	 * extra careful, the hlock might have been released and cleared.
764 	 *
765 	 * If this indeed happens, lets pretend it does not hurt to continue
766 	 * to print the lock unless the hlock class_idx does not point to a
767 	 * registered class. The rationale here is: since we don't attempt
768 	 * to distinguish whether we are in this situation, if it just
769 	 * happened we can't count on class_idx to tell either.
770 	 */
771 	struct lock_class *lock = hlock_class(hlock);
772 
773 	if (!lock) {
774 		printk(KERN_CONT "<RELEASED>\n");
775 		return;
776 	}
777 
778 	printk(KERN_CONT "%px", hlock->instance);
779 	print_lock_name(hlock, lock);
780 	printk(KERN_CONT ", at: %pS\n", (void *)hlock->acquire_ip);
781 }
782 
lockdep_print_held_locks(struct task_struct * p)783 static void lockdep_print_held_locks(struct task_struct *p)
784 {
785 	int i, depth = READ_ONCE(p->lockdep_depth);
786 
787 	if (!depth)
788 		printk("no locks held by %s/%d.\n", p->comm, task_pid_nr(p));
789 	else
790 		printk("%d lock%s held by %s/%d:\n", depth,
791 		       str_plural(depth), p->comm, task_pid_nr(p));
792 	/*
793 	 * It's not reliable to print a task's held locks if it's not sleeping
794 	 * and it's not the current task.
795 	 */
796 	if (p != current && task_is_running(p))
797 		return;
798 	for (i = 0; i < depth; i++) {
799 		printk(" #%d: ", i);
800 		print_lock(p->held_locks + i);
801 	}
802 }
803 
print_kernel_ident(void)804 static void print_kernel_ident(void)
805 {
806 	printk("%s %.*s %s\n", init_utsname()->release,
807 		(int)strcspn(init_utsname()->version, " "),
808 		init_utsname()->version,
809 		print_tainted());
810 }
811 
very_verbose(struct lock_class * class)812 static int very_verbose(struct lock_class *class)
813 {
814 #if VERY_VERBOSE
815 	return class_filter(class);
816 #endif
817 	return 0;
818 }
819 
820 /*
821  * Is this the address of a static object:
822  */
823 #ifdef __KERNEL__
static_obj(const void * obj)824 static int static_obj(const void *obj)
825 {
826 	unsigned long addr = (unsigned long) obj;
827 
828 	if (is_kernel_core_data(addr))
829 		return 1;
830 
831 	/*
832 	 * keys are allowed in the __ro_after_init section.
833 	 */
834 	if (is_kernel_rodata(addr))
835 		return 1;
836 
837 	/*
838 	 * in initdata section and used during bootup only?
839 	 * NOTE: On some platforms the initdata section is
840 	 * outside of the _stext ... _end range.
841 	 */
842 	if (system_state < SYSTEM_FREEING_INITMEM &&
843 		init_section_contains((void *)addr, 1))
844 		return 1;
845 
846 	/*
847 	 * in-kernel percpu var?
848 	 */
849 	if (is_kernel_percpu_address(addr))
850 		return 1;
851 
852 	/*
853 	 * module static or percpu var?
854 	 */
855 	return is_module_address(addr) || is_module_percpu_address(addr);
856 }
857 #endif
858 
859 /*
860  * To make lock name printouts unique, we calculate a unique
861  * class->name_version generation counter. The caller must hold the graph
862  * lock.
863  */
count_matching_names(struct lock_class * new_class)864 static int count_matching_names(struct lock_class *new_class)
865 {
866 	struct lock_class *class;
867 	int count = 0;
868 
869 	if (!new_class->name)
870 		return 0;
871 
872 	list_for_each_entry(class, &all_lock_classes, lock_entry) {
873 		if (new_class->key - new_class->subclass == class->key)
874 			return class->name_version;
875 		if (class->name && !strcmp(class->name, new_class->name))
876 			count = max(count, class->name_version);
877 	}
878 
879 	return count + 1;
880 }
881 
882 /* used from NMI context -- must be lockless */
883 static noinstr struct lock_class *
look_up_lock_class(const struct lockdep_map * lock,unsigned int subclass)884 look_up_lock_class(const struct lockdep_map *lock, unsigned int subclass)
885 {
886 	struct lockdep_subclass_key *key;
887 	struct hlist_head *hash_head;
888 	struct lock_class *class;
889 
890 	if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
891 		instrumentation_begin();
892 		debug_locks_off();
893 		nbcon_cpu_emergency_enter();
894 		printk(KERN_ERR
895 			"BUG: looking up invalid subclass: %u\n", subclass);
896 		printk(KERN_ERR
897 			"turning off the locking correctness validator.\n");
898 		dump_stack();
899 		nbcon_cpu_emergency_exit();
900 		instrumentation_end();
901 		return NULL;
902 	}
903 
904 	/*
905 	 * If it is not initialised then it has never been locked,
906 	 * so it won't be present in the hash table.
907 	 */
908 	if (unlikely(!lock->key))
909 		return NULL;
910 
911 	/*
912 	 * NOTE: the class-key must be unique. For dynamic locks, a static
913 	 * lock_class_key variable is passed in through the mutex_init()
914 	 * (or spin_lock_init()) call - which acts as the key. For static
915 	 * locks we use the lock object itself as the key.
916 	 */
917 	BUILD_BUG_ON(sizeof(struct lock_class_key) >
918 			sizeof(struct lockdep_map));
919 
920 	key = lock->key->subkeys + subclass;
921 
922 	hash_head = classhashentry(key);
923 
924 	/*
925 	 * We do an RCU walk of the hash, see lockdep_free_key_range().
926 	 */
927 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
928 		return NULL;
929 
930 	hlist_for_each_entry_rcu_notrace(class, hash_head, hash_entry) {
931 		if (class->key == key) {
932 			/*
933 			 * Huh! same key, different name? Did someone trample
934 			 * on some memory? We're most confused.
935 			 */
936 			WARN_ONCE(class->name != lock->name &&
937 				  lock->key != &__lockdep_no_validate__,
938 				  "Looking for class \"%s\" with key %ps, but found a different class \"%s\" with the same key\n",
939 				  lock->name, lock->key, class->name);
940 			return class;
941 		}
942 	}
943 
944 	return NULL;
945 }
946 
947 /*
948  * Static locks do not have their class-keys yet - for them the key is
949  * the lock object itself. If the lock is in the per cpu area, the
950  * canonical address of the lock (per cpu offset removed) is used.
951  */
assign_lock_key(struct lockdep_map * lock)952 static bool assign_lock_key(struct lockdep_map *lock)
953 {
954 	unsigned long can_addr, addr = (unsigned long)lock;
955 
956 #ifdef __KERNEL__
957 	/*
958 	 * lockdep_free_key_range() assumes that struct lock_class_key
959 	 * objects do not overlap. Since we use the address of lock
960 	 * objects as class key for static objects, check whether the
961 	 * size of lock_class_key objects does not exceed the size of
962 	 * the smallest lock object.
963 	 */
964 	BUILD_BUG_ON(sizeof(struct lock_class_key) > sizeof(raw_spinlock_t));
965 #endif
966 
967 	if (__is_kernel_percpu_address(addr, &can_addr))
968 		lock->key = (void *)can_addr;
969 	else if (__is_module_percpu_address(addr, &can_addr))
970 		lock->key = (void *)can_addr;
971 	else if (static_obj(lock))
972 		lock->key = (void *)lock;
973 	else {
974 		/* Debug-check: all keys must be persistent! */
975 		debug_locks_off();
976 		nbcon_cpu_emergency_enter();
977 		pr_err("INFO: trying to register non-static key.\n");
978 		pr_err("The code is fine but needs lockdep annotation, or maybe\n");
979 		pr_err("you didn't initialize this object before use?\n");
980 		pr_err("turning off the locking correctness validator.\n");
981 		dump_stack();
982 		nbcon_cpu_emergency_exit();
983 		return false;
984 	}
985 
986 	return true;
987 }
988 
989 #ifdef CONFIG_DEBUG_LOCKDEP
990 
991 /* Check whether element @e occurs in list @h */
in_list(struct list_head * e,struct list_head * h)992 static bool in_list(struct list_head *e, struct list_head *h)
993 {
994 	struct list_head *f;
995 
996 	list_for_each(f, h) {
997 		if (e == f)
998 			return true;
999 	}
1000 
1001 	return false;
1002 }
1003 
1004 /*
1005  * Check whether entry @e occurs in any of the locks_after or locks_before
1006  * lists.
1007  */
in_any_class_list(struct list_head * e)1008 static bool in_any_class_list(struct list_head *e)
1009 {
1010 	struct lock_class *class;
1011 	int i;
1012 
1013 	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
1014 		class = &lock_classes[i];
1015 		if (in_list(e, &class->locks_after) ||
1016 		    in_list(e, &class->locks_before))
1017 			return true;
1018 	}
1019 	return false;
1020 }
1021 
class_lock_list_valid(struct lock_class * c,struct list_head * h)1022 static bool class_lock_list_valid(struct lock_class *c, struct list_head *h)
1023 {
1024 	struct lock_list *e;
1025 
1026 	list_for_each_entry(e, h, entry) {
1027 		if (e->links_to != c) {
1028 			printk(KERN_INFO "class %s: mismatch for lock entry %ld; class %s <> %s",
1029 			       c->name ? : "(?)",
1030 			       (unsigned long)(e - list_entries),
1031 			       e->links_to && e->links_to->name ?
1032 			       e->links_to->name : "(?)",
1033 			       e->class && e->class->name ? e->class->name :
1034 			       "(?)");
1035 			return false;
1036 		}
1037 	}
1038 	return true;
1039 }
1040 
1041 #ifdef CONFIG_PROVE_LOCKING
1042 static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
1043 #endif
1044 
check_lock_chain_key(struct lock_chain * chain)1045 static bool check_lock_chain_key(struct lock_chain *chain)
1046 {
1047 #ifdef CONFIG_PROVE_LOCKING
1048 	u64 chain_key = INITIAL_CHAIN_KEY;
1049 	int i;
1050 
1051 	for (i = chain->base; i < chain->base + chain->depth; i++)
1052 		chain_key = iterate_chain_key(chain_key, chain_hlocks[i]);
1053 	/*
1054 	 * The 'unsigned long long' casts avoid that a compiler warning
1055 	 * is reported when building tools/lib/lockdep.
1056 	 */
1057 	if (chain->chain_key != chain_key) {
1058 		printk(KERN_INFO "chain %lld: key %#llx <> %#llx\n",
1059 		       (unsigned long long)(chain - lock_chains),
1060 		       (unsigned long long)chain->chain_key,
1061 		       (unsigned long long)chain_key);
1062 		return false;
1063 	}
1064 #endif
1065 	return true;
1066 }
1067 
in_any_zapped_class_list(struct lock_class * class)1068 static bool in_any_zapped_class_list(struct lock_class *class)
1069 {
1070 	struct pending_free *pf;
1071 	int i;
1072 
1073 	for (i = 0, pf = delayed_free.pf; i < ARRAY_SIZE(delayed_free.pf); i++, pf++) {
1074 		if (in_list(&class->lock_entry, &pf->zapped))
1075 			return true;
1076 	}
1077 
1078 	return false;
1079 }
1080 
__check_data_structures(void)1081 static bool __check_data_structures(void)
1082 {
1083 	struct lock_class *class;
1084 	struct lock_chain *chain;
1085 	struct hlist_head *head;
1086 	struct lock_list *e;
1087 	int i;
1088 
1089 	/* Check whether all classes occur in a lock list. */
1090 	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
1091 		class = &lock_classes[i];
1092 		if (!in_list(&class->lock_entry, &all_lock_classes) &&
1093 		    !in_list(&class->lock_entry, &free_lock_classes) &&
1094 		    !in_any_zapped_class_list(class)) {
1095 			printk(KERN_INFO "class %px/%s is not in any class list\n",
1096 			       class, class->name ? : "(?)");
1097 			return false;
1098 		}
1099 	}
1100 
1101 	/* Check whether all classes have valid lock lists. */
1102 	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
1103 		class = &lock_classes[i];
1104 		if (!class_lock_list_valid(class, &class->locks_before))
1105 			return false;
1106 		if (!class_lock_list_valid(class, &class->locks_after))
1107 			return false;
1108 	}
1109 
1110 	/* Check the chain_key of all lock chains. */
1111 	for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
1112 		head = chainhash_table + i;
1113 		hlist_for_each_entry_rcu(chain, head, entry) {
1114 			if (!check_lock_chain_key(chain))
1115 				return false;
1116 		}
1117 	}
1118 
1119 	/*
1120 	 * Check whether all list entries that are in use occur in a class
1121 	 * lock list.
1122 	 */
1123 	for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
1124 		e = list_entries + i;
1125 		if (!in_any_class_list(&e->entry)) {
1126 			printk(KERN_INFO "list entry %d is not in any class list; class %s <> %s\n",
1127 			       (unsigned int)(e - list_entries),
1128 			       e->class->name ? : "(?)",
1129 			       e->links_to->name ? : "(?)");
1130 			return false;
1131 		}
1132 	}
1133 
1134 	/*
1135 	 * Check whether all list entries that are not in use do not occur in
1136 	 * a class lock list.
1137 	 */
1138 	for_each_clear_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
1139 		e = list_entries + i;
1140 		if (in_any_class_list(&e->entry)) {
1141 			printk(KERN_INFO "list entry %d occurs in a class list; class %s <> %s\n",
1142 			       (unsigned int)(e - list_entries),
1143 			       e->class && e->class->name ? e->class->name :
1144 			       "(?)",
1145 			       e->links_to && e->links_to->name ?
1146 			       e->links_to->name : "(?)");
1147 			return false;
1148 		}
1149 	}
1150 
1151 	return true;
1152 }
1153 
1154 int check_consistency = 0;
1155 module_param(check_consistency, int, 0644);
1156 
check_data_structures(void)1157 static void check_data_structures(void)
1158 {
1159 	static bool once = false;
1160 
1161 	if (check_consistency && !once) {
1162 		if (!__check_data_structures()) {
1163 			once = true;
1164 			WARN_ON(once);
1165 		}
1166 	}
1167 }
1168 
1169 #else /* CONFIG_DEBUG_LOCKDEP */
1170 
check_data_structures(void)1171 static inline void check_data_structures(void) { }
1172 
1173 #endif /* CONFIG_DEBUG_LOCKDEP */
1174 
1175 static void init_chain_block_buckets(void);
1176 
1177 /*
1178  * Initialize the lock_classes[] array elements, the free_lock_classes list
1179  * and also the delayed_free structure.
1180  */
init_data_structures_once(void)1181 static void init_data_structures_once(void)
1182 {
1183 	static bool __read_mostly ds_initialized, rcu_head_initialized;
1184 	int i;
1185 
1186 	if (likely(rcu_head_initialized))
1187 		return;
1188 
1189 	if (system_state >= SYSTEM_SCHEDULING) {
1190 		init_rcu_head(&delayed_free.rcu_head);
1191 		rcu_head_initialized = true;
1192 	}
1193 
1194 	if (ds_initialized)
1195 		return;
1196 
1197 	ds_initialized = true;
1198 
1199 	INIT_LIST_HEAD(&delayed_free.pf[0].zapped);
1200 	INIT_LIST_HEAD(&delayed_free.pf[1].zapped);
1201 
1202 	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
1203 		list_add_tail(&lock_classes[i].lock_entry, &free_lock_classes);
1204 		INIT_LIST_HEAD(&lock_classes[i].locks_after);
1205 		INIT_LIST_HEAD(&lock_classes[i].locks_before);
1206 	}
1207 	init_chain_block_buckets();
1208 }
1209 
keyhashentry(const struct lock_class_key * key)1210 static inline struct hlist_head *keyhashentry(const struct lock_class_key *key)
1211 {
1212 	unsigned long hash = hash_long((uintptr_t)key, KEYHASH_BITS);
1213 
1214 	return lock_keys_hash + hash;
1215 }
1216 
1217 /* Register a dynamically allocated key. */
lockdep_register_key(struct lock_class_key * key)1218 void lockdep_register_key(struct lock_class_key *key)
1219 {
1220 	struct hlist_head *hash_head;
1221 	struct lock_class_key *k;
1222 	unsigned long flags;
1223 
1224 	if (WARN_ON_ONCE(static_obj(key)))
1225 		return;
1226 	hash_head = keyhashentry(key);
1227 
1228 	raw_local_irq_save(flags);
1229 	if (!graph_lock())
1230 		goto restore_irqs;
1231 	hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
1232 		if (WARN_ON_ONCE(k == key))
1233 			goto out_unlock;
1234 	}
1235 	hlist_add_head_rcu(&key->hash_entry, hash_head);
1236 out_unlock:
1237 	graph_unlock();
1238 restore_irqs:
1239 	raw_local_irq_restore(flags);
1240 }
1241 EXPORT_SYMBOL_GPL(lockdep_register_key);
1242 
1243 /* Check whether a key has been registered as a dynamic key. */
is_dynamic_key(const struct lock_class_key * key)1244 static bool is_dynamic_key(const struct lock_class_key *key)
1245 {
1246 	struct hlist_head *hash_head;
1247 	struct lock_class_key *k;
1248 	bool found = false;
1249 
1250 	if (WARN_ON_ONCE(static_obj(key)))
1251 		return false;
1252 
1253 	/*
1254 	 * If lock debugging is disabled lock_keys_hash[] may contain
1255 	 * pointers to memory that has already been freed. Avoid triggering
1256 	 * a use-after-free in that case by returning early.
1257 	 */
1258 	if (!debug_locks)
1259 		return true;
1260 
1261 	hash_head = keyhashentry(key);
1262 
1263 	rcu_read_lock();
1264 	hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
1265 		if (k == key) {
1266 			found = true;
1267 			break;
1268 		}
1269 	}
1270 	rcu_read_unlock();
1271 
1272 	return found;
1273 }
1274 
1275 /*
1276  * Register a lock's class in the hash-table, if the class is not present
1277  * yet. Otherwise we look it up. We cache the result in the lock object
1278  * itself, so actual lookup of the hash should be once per lock object.
1279  */
1280 static struct lock_class *
register_lock_class(struct lockdep_map * lock,unsigned int subclass,int force)1281 register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
1282 {
1283 	struct lockdep_subclass_key *key;
1284 	struct hlist_head *hash_head;
1285 	struct lock_class *class;
1286 	int idx;
1287 
1288 	DEBUG_LOCKS_WARN_ON(!irqs_disabled());
1289 
1290 	class = look_up_lock_class(lock, subclass);
1291 	if (likely(class))
1292 		goto out_set_class_cache;
1293 
1294 	if (!lock->key) {
1295 		if (!assign_lock_key(lock))
1296 			return NULL;
1297 	} else if (!static_obj(lock->key) && !is_dynamic_key(lock->key)) {
1298 		return NULL;
1299 	}
1300 
1301 	key = lock->key->subkeys + subclass;
1302 	hash_head = classhashentry(key);
1303 
1304 	if (!graph_lock()) {
1305 		return NULL;
1306 	}
1307 	/*
1308 	 * We have to do the hash-walk again, to avoid races
1309 	 * with another CPU:
1310 	 */
1311 	hlist_for_each_entry_rcu(class, hash_head, hash_entry) {
1312 		if (class->key == key)
1313 			goto out_unlock_set;
1314 	}
1315 
1316 	init_data_structures_once();
1317 
1318 	/* Allocate a new lock class and add it to the hash. */
1319 	class = list_first_entry_or_null(&free_lock_classes, typeof(*class),
1320 					 lock_entry);
1321 	if (!class) {
1322 		if (!debug_locks_off_graph_unlock()) {
1323 			return NULL;
1324 		}
1325 
1326 		nbcon_cpu_emergency_enter();
1327 		print_lockdep_off("BUG: MAX_LOCKDEP_KEYS too low!");
1328 		dump_stack();
1329 		nbcon_cpu_emergency_exit();
1330 		return NULL;
1331 	}
1332 	nr_lock_classes++;
1333 	__set_bit(class - lock_classes, lock_classes_in_use);
1334 	debug_atomic_inc(nr_unused_locks);
1335 	class->key = key;
1336 	class->name = lock->name;
1337 	class->subclass = subclass;
1338 	WARN_ON_ONCE(!list_empty(&class->locks_before));
1339 	WARN_ON_ONCE(!list_empty(&class->locks_after));
1340 	class->name_version = count_matching_names(class);
1341 	class->wait_type_inner = lock->wait_type_inner;
1342 	class->wait_type_outer = lock->wait_type_outer;
1343 	class->lock_type = lock->lock_type;
1344 	/*
1345 	 * We use RCU's safe list-add method to make
1346 	 * parallel walking of the hash-list safe:
1347 	 */
1348 	hlist_add_head_rcu(&class->hash_entry, hash_head);
1349 	/*
1350 	 * Remove the class from the free list and add it to the global list
1351 	 * of classes.
1352 	 */
1353 	list_move_tail(&class->lock_entry, &all_lock_classes);
1354 	idx = class - lock_classes;
1355 	if (idx > max_lock_class_idx)
1356 		max_lock_class_idx = idx;
1357 
1358 	if (verbose(class)) {
1359 		graph_unlock();
1360 
1361 		nbcon_cpu_emergency_enter();
1362 		printk("\nnew class %px: %s", class->key, class->name);
1363 		if (class->name_version > 1)
1364 			printk(KERN_CONT "#%d", class->name_version);
1365 		printk(KERN_CONT "\n");
1366 		dump_stack();
1367 		nbcon_cpu_emergency_exit();
1368 
1369 		if (!graph_lock()) {
1370 			return NULL;
1371 		}
1372 	}
1373 out_unlock_set:
1374 	graph_unlock();
1375 
1376 out_set_class_cache:
1377 	if (!subclass || force)
1378 		lock->class_cache[0] = class;
1379 	else if (subclass < NR_LOCKDEP_CACHING_CLASSES)
1380 		lock->class_cache[subclass] = class;
1381 
1382 	/*
1383 	 * Hash collision, did we smoke some? We found a class with a matching
1384 	 * hash but the subclass -- which is hashed in -- didn't match.
1385 	 */
1386 	if (DEBUG_LOCKS_WARN_ON(class->subclass != subclass))
1387 		return NULL;
1388 
1389 	return class;
1390 }
1391 
1392 #ifdef CONFIG_PROVE_LOCKING
1393 /*
1394  * Allocate a lockdep entry. (assumes the graph_lock held, returns
1395  * with NULL on failure)
1396  */
alloc_list_entry(void)1397 static struct lock_list *alloc_list_entry(void)
1398 {
1399 	int idx = find_first_zero_bit(list_entries_in_use,
1400 				      ARRAY_SIZE(list_entries));
1401 
1402 	if (idx >= ARRAY_SIZE(list_entries)) {
1403 		if (!debug_locks_off_graph_unlock())
1404 			return NULL;
1405 
1406 		nbcon_cpu_emergency_enter();
1407 		print_lockdep_off("BUG: MAX_LOCKDEP_ENTRIES too low!");
1408 		dump_stack();
1409 		nbcon_cpu_emergency_exit();
1410 		return NULL;
1411 	}
1412 	nr_list_entries++;
1413 	__set_bit(idx, list_entries_in_use);
1414 	return list_entries + idx;
1415 }
1416 
1417 /*
1418  * Add a new dependency to the head of the list:
1419  */
add_lock_to_list(struct lock_class * this,struct lock_class * links_to,struct list_head * head,u16 distance,u8 dep,const struct lock_trace * trace)1420 static int add_lock_to_list(struct lock_class *this,
1421 			    struct lock_class *links_to, struct list_head *head,
1422 			    u16 distance, u8 dep,
1423 			    const struct lock_trace *trace)
1424 {
1425 	struct lock_list *entry;
1426 	/*
1427 	 * Lock not present yet - get a new dependency struct and
1428 	 * add it to the list:
1429 	 */
1430 	entry = alloc_list_entry();
1431 	if (!entry)
1432 		return 0;
1433 
1434 	entry->class = this;
1435 	entry->links_to = links_to;
1436 	entry->dep = dep;
1437 	entry->distance = distance;
1438 	entry->trace = trace;
1439 	/*
1440 	 * Both allocation and removal are done under the graph lock; but
1441 	 * iteration is under RCU-sched; see look_up_lock_class() and
1442 	 * lockdep_free_key_range().
1443 	 */
1444 	list_add_tail_rcu(&entry->entry, head);
1445 
1446 	return 1;
1447 }
1448 
1449 /*
1450  * For good efficiency of modular, we use power of 2
1451  */
1452 #define MAX_CIRCULAR_QUEUE_SIZE		(1UL << CONFIG_LOCKDEP_CIRCULAR_QUEUE_BITS)
1453 #define CQ_MASK				(MAX_CIRCULAR_QUEUE_SIZE-1)
1454 
1455 /*
1456  * The circular_queue and helpers are used to implement graph
1457  * breadth-first search (BFS) algorithm, by which we can determine
1458  * whether there is a path from a lock to another. In deadlock checks,
1459  * a path from the next lock to be acquired to a previous held lock
1460  * indicates that adding the <prev> -> <next> lock dependency will
1461  * produce a circle in the graph. Breadth-first search instead of
1462  * depth-first search is used in order to find the shortest (circular)
1463  * path.
1464  */
1465 struct circular_queue {
1466 	struct lock_list *element[MAX_CIRCULAR_QUEUE_SIZE];
1467 	unsigned int  front, rear;
1468 };
1469 
1470 static struct circular_queue lock_cq;
1471 
1472 unsigned int max_bfs_queue_depth;
1473 
1474 static unsigned int lockdep_dependency_gen_id;
1475 
__cq_init(struct circular_queue * cq)1476 static inline void __cq_init(struct circular_queue *cq)
1477 {
1478 	cq->front = cq->rear = 0;
1479 	lockdep_dependency_gen_id++;
1480 }
1481 
__cq_empty(struct circular_queue * cq)1482 static inline int __cq_empty(struct circular_queue *cq)
1483 {
1484 	return (cq->front == cq->rear);
1485 }
1486 
__cq_full(struct circular_queue * cq)1487 static inline int __cq_full(struct circular_queue *cq)
1488 {
1489 	return ((cq->rear + 1) & CQ_MASK) == cq->front;
1490 }
1491 
__cq_enqueue(struct circular_queue * cq,struct lock_list * elem)1492 static inline int __cq_enqueue(struct circular_queue *cq, struct lock_list *elem)
1493 {
1494 	if (__cq_full(cq))
1495 		return -1;
1496 
1497 	cq->element[cq->rear] = elem;
1498 	cq->rear = (cq->rear + 1) & CQ_MASK;
1499 	return 0;
1500 }
1501 
1502 /*
1503  * Dequeue an element from the circular_queue, return a lock_list if
1504  * the queue is not empty, or NULL if otherwise.
1505  */
__cq_dequeue(struct circular_queue * cq)1506 static inline struct lock_list * __cq_dequeue(struct circular_queue *cq)
1507 {
1508 	struct lock_list * lock;
1509 
1510 	if (__cq_empty(cq))
1511 		return NULL;
1512 
1513 	lock = cq->element[cq->front];
1514 	cq->front = (cq->front + 1) & CQ_MASK;
1515 
1516 	return lock;
1517 }
1518 
__cq_get_elem_count(struct circular_queue * cq)1519 static inline unsigned int  __cq_get_elem_count(struct circular_queue *cq)
1520 {
1521 	return (cq->rear - cq->front) & CQ_MASK;
1522 }
1523 
mark_lock_accessed(struct lock_list * lock)1524 static inline void mark_lock_accessed(struct lock_list *lock)
1525 {
1526 	lock->class->dep_gen_id = lockdep_dependency_gen_id;
1527 }
1528 
visit_lock_entry(struct lock_list * lock,struct lock_list * parent)1529 static inline void visit_lock_entry(struct lock_list *lock,
1530 				    struct lock_list *parent)
1531 {
1532 	lock->parent = parent;
1533 }
1534 
lock_accessed(struct lock_list * lock)1535 static inline unsigned long lock_accessed(struct lock_list *lock)
1536 {
1537 	return lock->class->dep_gen_id == lockdep_dependency_gen_id;
1538 }
1539 
get_lock_parent(struct lock_list * child)1540 static inline struct lock_list *get_lock_parent(struct lock_list *child)
1541 {
1542 	return child->parent;
1543 }
1544 
get_lock_depth(struct lock_list * child)1545 static inline int get_lock_depth(struct lock_list *child)
1546 {
1547 	int depth = 0;
1548 	struct lock_list *parent;
1549 
1550 	while ((parent = get_lock_parent(child))) {
1551 		child = parent;
1552 		depth++;
1553 	}
1554 	return depth;
1555 }
1556 
1557 /*
1558  * Return the forward or backward dependency list.
1559  *
1560  * @lock:   the lock_list to get its class's dependency list
1561  * @offset: the offset to struct lock_class to determine whether it is
1562  *          locks_after or locks_before
1563  */
get_dep_list(struct lock_list * lock,int offset)1564 static inline struct list_head *get_dep_list(struct lock_list *lock, int offset)
1565 {
1566 	void *lock_class = lock->class;
1567 
1568 	return lock_class + offset;
1569 }
1570 /*
1571  * Return values of a bfs search:
1572  *
1573  * BFS_E* indicates an error
1574  * BFS_R* indicates a result (match or not)
1575  *
1576  * BFS_EINVALIDNODE: Find a invalid node in the graph.
1577  *
1578  * BFS_EQUEUEFULL: The queue is full while doing the bfs.
1579  *
1580  * BFS_RMATCH: Find the matched node in the graph, and put that node into
1581  *             *@target_entry.
1582  *
1583  * BFS_RNOMATCH: Haven't found the matched node and keep *@target_entry
1584  *               _unchanged_.
1585  */
1586 enum bfs_result {
1587 	BFS_EINVALIDNODE = -2,
1588 	BFS_EQUEUEFULL = -1,
1589 	BFS_RMATCH = 0,
1590 	BFS_RNOMATCH = 1,
1591 };
1592 
1593 /*
1594  * bfs_result < 0 means error
1595  */
bfs_error(enum bfs_result res)1596 static inline bool bfs_error(enum bfs_result res)
1597 {
1598 	return res < 0;
1599 }
1600 
1601 /*
1602  * DEP_*_BIT in lock_list::dep
1603  *
1604  * For dependency @prev -> @next:
1605  *
1606  *   SR: @prev is shared reader (->read != 0) and @next is recursive reader
1607  *       (->read == 2)
1608  *   ER: @prev is exclusive locker (->read == 0) and @next is recursive reader
1609  *   SN: @prev is shared reader and @next is non-recursive locker (->read != 2)
1610  *   EN: @prev is exclusive locker and @next is non-recursive locker
1611  *
1612  * Note that we define the value of DEP_*_BITs so that:
1613  *   bit0 is prev->read == 0
1614  *   bit1 is next->read != 2
1615  */
1616 #define DEP_SR_BIT (0 + (0 << 1)) /* 0 */
1617 #define DEP_ER_BIT (1 + (0 << 1)) /* 1 */
1618 #define DEP_SN_BIT (0 + (1 << 1)) /* 2 */
1619 #define DEP_EN_BIT (1 + (1 << 1)) /* 3 */
1620 
1621 #define DEP_SR_MASK (1U << (DEP_SR_BIT))
1622 #define DEP_ER_MASK (1U << (DEP_ER_BIT))
1623 #define DEP_SN_MASK (1U << (DEP_SN_BIT))
1624 #define DEP_EN_MASK (1U << (DEP_EN_BIT))
1625 
1626 static inline unsigned int
__calc_dep_bit(struct held_lock * prev,struct held_lock * next)1627 __calc_dep_bit(struct held_lock *prev, struct held_lock *next)
1628 {
1629 	return (prev->read == 0) + ((next->read != 2) << 1);
1630 }
1631 
calc_dep(struct held_lock * prev,struct held_lock * next)1632 static inline u8 calc_dep(struct held_lock *prev, struct held_lock *next)
1633 {
1634 	return 1U << __calc_dep_bit(prev, next);
1635 }
1636 
1637 /*
1638  * calculate the dep_bit for backwards edges. We care about whether @prev is
1639  * shared and whether @next is recursive.
1640  */
1641 static inline unsigned int
__calc_dep_bitb(struct held_lock * prev,struct held_lock * next)1642 __calc_dep_bitb(struct held_lock *prev, struct held_lock *next)
1643 {
1644 	return (next->read != 2) + ((prev->read == 0) << 1);
1645 }
1646 
calc_depb(struct held_lock * prev,struct held_lock * next)1647 static inline u8 calc_depb(struct held_lock *prev, struct held_lock *next)
1648 {
1649 	return 1U << __calc_dep_bitb(prev, next);
1650 }
1651 
1652 /*
1653  * Initialize a lock_list entry @lock belonging to @class as the root for a BFS
1654  * search.
1655  */
__bfs_init_root(struct lock_list * lock,struct lock_class * class)1656 static inline void __bfs_init_root(struct lock_list *lock,
1657 				   struct lock_class *class)
1658 {
1659 	lock->class = class;
1660 	lock->parent = NULL;
1661 	lock->only_xr = 0;
1662 }
1663 
1664 /*
1665  * Initialize a lock_list entry @lock based on a lock acquisition @hlock as the
1666  * root for a BFS search.
1667  *
1668  * ->only_xr of the initial lock node is set to @hlock->read == 2, to make sure
1669  * that <prev> -> @hlock and @hlock -> <whatever __bfs() found> is not -(*R)->
1670  * and -(S*)->.
1671  */
bfs_init_root(struct lock_list * lock,struct held_lock * hlock)1672 static inline void bfs_init_root(struct lock_list *lock,
1673 				 struct held_lock *hlock)
1674 {
1675 	__bfs_init_root(lock, hlock_class(hlock));
1676 	lock->only_xr = (hlock->read == 2);
1677 }
1678 
1679 /*
1680  * Similar to bfs_init_root() but initialize the root for backwards BFS.
1681  *
1682  * ->only_xr of the initial lock node is set to @hlock->read != 0, to make sure
1683  * that <next> -> @hlock and @hlock -> <whatever backwards BFS found> is not
1684  * -(*S)-> and -(R*)-> (reverse order of -(*R)-> and -(S*)->).
1685  */
bfs_init_rootb(struct lock_list * lock,struct held_lock * hlock)1686 static inline void bfs_init_rootb(struct lock_list *lock,
1687 				  struct held_lock *hlock)
1688 {
1689 	__bfs_init_root(lock, hlock_class(hlock));
1690 	lock->only_xr = (hlock->read != 0);
1691 }
1692 
__bfs_next(struct lock_list * lock,int offset)1693 static inline struct lock_list *__bfs_next(struct lock_list *lock, int offset)
1694 {
1695 	if (!lock || !lock->parent)
1696 		return NULL;
1697 
1698 	return list_next_or_null_rcu(get_dep_list(lock->parent, offset),
1699 				     &lock->entry, struct lock_list, entry);
1700 }
1701 
1702 /*
1703  * Breadth-First Search to find a strong path in the dependency graph.
1704  *
1705  * @source_entry: the source of the path we are searching for.
1706  * @data: data used for the second parameter of @match function
1707  * @match: match function for the search
1708  * @target_entry: pointer to the target of a matched path
1709  * @offset: the offset to struct lock_class to determine whether it is
1710  *          locks_after or locks_before
1711  *
1712  * We may have multiple edges (considering different kinds of dependencies,
1713  * e.g. ER and SN) between two nodes in the dependency graph. But
1714  * only the strong dependency path in the graph is relevant to deadlocks. A
1715  * strong dependency path is a dependency path that doesn't have two adjacent
1716  * dependencies as -(*R)-> -(S*)->, please see:
1717  *
1718  *         Documentation/locking/lockdep-design.rst
1719  *
1720  * for more explanation of the definition of strong dependency paths
1721  *
1722  * In __bfs(), we only traverse in the strong dependency path:
1723  *
1724  *     In lock_list::only_xr, we record whether the previous dependency only
1725  *     has -(*R)-> in the search, and if it does (prev only has -(*R)->), we
1726  *     filter out any -(S*)-> in the current dependency and after that, the
1727  *     ->only_xr is set according to whether we only have -(*R)-> left.
1728  */
__bfs(struct lock_list * source_entry,void * data,bool (* match)(struct lock_list * entry,void * data),bool (* skip)(struct lock_list * entry,void * data),struct lock_list ** target_entry,int offset)1729 static enum bfs_result __bfs(struct lock_list *source_entry,
1730 			     void *data,
1731 			     bool (*match)(struct lock_list *entry, void *data),
1732 			     bool (*skip)(struct lock_list *entry, void *data),
1733 			     struct lock_list **target_entry,
1734 			     int offset)
1735 {
1736 	struct circular_queue *cq = &lock_cq;
1737 	struct lock_list *lock = NULL;
1738 	struct lock_list *entry;
1739 	struct list_head *head;
1740 	unsigned int cq_depth;
1741 	bool first;
1742 
1743 	lockdep_assert_locked();
1744 
1745 	__cq_init(cq);
1746 	__cq_enqueue(cq, source_entry);
1747 
1748 	while ((lock = __bfs_next(lock, offset)) || (lock = __cq_dequeue(cq))) {
1749 		if (!lock->class)
1750 			return BFS_EINVALIDNODE;
1751 
1752 		/*
1753 		 * Step 1: check whether we already finish on this one.
1754 		 *
1755 		 * If we have visited all the dependencies from this @lock to
1756 		 * others (iow, if we have visited all lock_list entries in
1757 		 * @lock->class->locks_{after,before}) we skip, otherwise go
1758 		 * and visit all the dependencies in the list and mark this
1759 		 * list accessed.
1760 		 */
1761 		if (lock_accessed(lock))
1762 			continue;
1763 		else
1764 			mark_lock_accessed(lock);
1765 
1766 		/*
1767 		 * Step 2: check whether prev dependency and this form a strong
1768 		 *         dependency path.
1769 		 */
1770 		if (lock->parent) { /* Parent exists, check prev dependency */
1771 			u8 dep = lock->dep;
1772 			bool prev_only_xr = lock->parent->only_xr;
1773 
1774 			/*
1775 			 * Mask out all -(S*)-> if we only have *R in previous
1776 			 * step, because -(*R)-> -(S*)-> don't make up a strong
1777 			 * dependency.
1778 			 */
1779 			if (prev_only_xr)
1780 				dep &= ~(DEP_SR_MASK | DEP_SN_MASK);
1781 
1782 			/* If nothing left, we skip */
1783 			if (!dep)
1784 				continue;
1785 
1786 			/* If there are only -(*R)-> left, set that for the next step */
1787 			lock->only_xr = !(dep & (DEP_SN_MASK | DEP_EN_MASK));
1788 		}
1789 
1790 		/*
1791 		 * Step 3: we haven't visited this and there is a strong
1792 		 *         dependency path to this, so check with @match.
1793 		 *         If @skip is provide and returns true, we skip this
1794 		 *         lock (and any path this lock is in).
1795 		 */
1796 		if (skip && skip(lock, data))
1797 			continue;
1798 
1799 		if (match(lock, data)) {
1800 			*target_entry = lock;
1801 			return BFS_RMATCH;
1802 		}
1803 
1804 		/*
1805 		 * Step 4: if not match, expand the path by adding the
1806 		 *         forward or backwards dependencies in the search
1807 		 *
1808 		 */
1809 		first = true;
1810 		head = get_dep_list(lock, offset);
1811 		list_for_each_entry_rcu(entry, head, entry) {
1812 			visit_lock_entry(entry, lock);
1813 
1814 			/*
1815 			 * Note we only enqueue the first of the list into the
1816 			 * queue, because we can always find a sibling
1817 			 * dependency from one (see __bfs_next()), as a result
1818 			 * the space of queue is saved.
1819 			 */
1820 			if (!first)
1821 				continue;
1822 
1823 			first = false;
1824 
1825 			if (__cq_enqueue(cq, entry))
1826 				return BFS_EQUEUEFULL;
1827 
1828 			cq_depth = __cq_get_elem_count(cq);
1829 			if (max_bfs_queue_depth < cq_depth)
1830 				max_bfs_queue_depth = cq_depth;
1831 		}
1832 	}
1833 
1834 	return BFS_RNOMATCH;
1835 }
1836 
1837 static inline enum bfs_result
__bfs_forwards(struct lock_list * src_entry,void * data,bool (* match)(struct lock_list * entry,void * data),bool (* skip)(struct lock_list * entry,void * data),struct lock_list ** target_entry)1838 __bfs_forwards(struct lock_list *src_entry,
1839 	       void *data,
1840 	       bool (*match)(struct lock_list *entry, void *data),
1841 	       bool (*skip)(struct lock_list *entry, void *data),
1842 	       struct lock_list **target_entry)
1843 {
1844 	return __bfs(src_entry, data, match, skip, target_entry,
1845 		     offsetof(struct lock_class, locks_after));
1846 
1847 }
1848 
1849 static inline enum bfs_result
__bfs_backwards(struct lock_list * src_entry,void * data,bool (* match)(struct lock_list * entry,void * data),bool (* skip)(struct lock_list * entry,void * data),struct lock_list ** target_entry)1850 __bfs_backwards(struct lock_list *src_entry,
1851 		void *data,
1852 		bool (*match)(struct lock_list *entry, void *data),
1853 	       bool (*skip)(struct lock_list *entry, void *data),
1854 		struct lock_list **target_entry)
1855 {
1856 	return __bfs(src_entry, data, match, skip, target_entry,
1857 		     offsetof(struct lock_class, locks_before));
1858 
1859 }
1860 
print_lock_trace(const struct lock_trace * trace,unsigned int spaces)1861 static void print_lock_trace(const struct lock_trace *trace,
1862 			     unsigned int spaces)
1863 {
1864 	stack_trace_print(trace->entries, trace->nr_entries, spaces);
1865 }
1866 
1867 /*
1868  * Print a dependency chain entry (this is only done when a deadlock
1869  * has been detected):
1870  */
1871 static noinline void
print_circular_bug_entry(struct lock_list * target,int depth)1872 print_circular_bug_entry(struct lock_list *target, int depth)
1873 {
1874 	if (debug_locks_silent)
1875 		return;
1876 	printk("\n-> #%u", depth);
1877 	print_lock_name(NULL, target->class);
1878 	printk(KERN_CONT ":\n");
1879 	print_lock_trace(target->trace, 6);
1880 }
1881 
1882 static void
print_circular_lock_scenario(struct held_lock * src,struct held_lock * tgt,struct lock_list * prt)1883 print_circular_lock_scenario(struct held_lock *src,
1884 			     struct held_lock *tgt,
1885 			     struct lock_list *prt)
1886 {
1887 	struct lock_class *source = hlock_class(src);
1888 	struct lock_class *target = hlock_class(tgt);
1889 	struct lock_class *parent = prt->class;
1890 	int src_read = src->read;
1891 	int tgt_read = tgt->read;
1892 
1893 	/*
1894 	 * A direct locking problem where unsafe_class lock is taken
1895 	 * directly by safe_class lock, then all we need to show
1896 	 * is the deadlock scenario, as it is obvious that the
1897 	 * unsafe lock is taken under the safe lock.
1898 	 *
1899 	 * But if there is a chain instead, where the safe lock takes
1900 	 * an intermediate lock (middle_class) where this lock is
1901 	 * not the same as the safe lock, then the lock chain is
1902 	 * used to describe the problem. Otherwise we would need
1903 	 * to show a different CPU case for each link in the chain
1904 	 * from the safe_class lock to the unsafe_class lock.
1905 	 */
1906 	if (parent != source) {
1907 		printk("Chain exists of:\n  ");
1908 		__print_lock_name(src, source);
1909 		printk(KERN_CONT " --> ");
1910 		__print_lock_name(NULL, parent);
1911 		printk(KERN_CONT " --> ");
1912 		__print_lock_name(tgt, target);
1913 		printk(KERN_CONT "\n\n");
1914 	}
1915 
1916 	printk(" Possible unsafe locking scenario:\n\n");
1917 	printk("       CPU0                    CPU1\n");
1918 	printk("       ----                    ----\n");
1919 	if (tgt_read != 0)
1920 		printk("  rlock(");
1921 	else
1922 		printk("  lock(");
1923 	__print_lock_name(tgt, target);
1924 	printk(KERN_CONT ");\n");
1925 	printk("                               lock(");
1926 	__print_lock_name(NULL, parent);
1927 	printk(KERN_CONT ");\n");
1928 	printk("                               lock(");
1929 	__print_lock_name(tgt, target);
1930 	printk(KERN_CONT ");\n");
1931 	if (src_read != 0)
1932 		printk("  rlock(");
1933 	else if (src->sync)
1934 		printk("  sync(");
1935 	else
1936 		printk("  lock(");
1937 	__print_lock_name(src, source);
1938 	printk(KERN_CONT ");\n");
1939 	printk("\n *** DEADLOCK ***\n\n");
1940 }
1941 
1942 /*
1943  * When a circular dependency is detected, print the
1944  * header first:
1945  */
1946 static noinline void
print_circular_bug_header(struct lock_list * entry,unsigned int depth,struct held_lock * check_src,struct held_lock * check_tgt)1947 print_circular_bug_header(struct lock_list *entry, unsigned int depth,
1948 			struct held_lock *check_src,
1949 			struct held_lock *check_tgt)
1950 {
1951 	struct task_struct *curr = current;
1952 
1953 	if (debug_locks_silent)
1954 		return;
1955 
1956 	pr_warn("\n");
1957 	pr_warn("======================================================\n");
1958 	pr_warn("WARNING: possible circular locking dependency detected\n");
1959 	print_kernel_ident();
1960 	pr_warn("------------------------------------------------------\n");
1961 	pr_warn("%s/%d is trying to acquire lock:\n",
1962 		curr->comm, task_pid_nr(curr));
1963 	print_lock(check_src);
1964 
1965 	pr_warn("\nbut task is already holding lock:\n");
1966 
1967 	print_lock(check_tgt);
1968 	pr_warn("\nwhich lock already depends on the new lock.\n\n");
1969 	pr_warn("\nthe existing dependency chain (in reverse order) is:\n");
1970 
1971 	print_circular_bug_entry(entry, depth);
1972 }
1973 
1974 /*
1975  * We are about to add A -> B into the dependency graph, and in __bfs() a
1976  * strong dependency path A -> .. -> B is found: hlock_class equals
1977  * entry->class.
1978  *
1979  * If A -> .. -> B can replace A -> B in any __bfs() search (means the former
1980  * is _stronger_ than or equal to the latter), we consider A -> B as redundant.
1981  * For example if A -> .. -> B is -(EN)-> (i.e. A -(E*)-> .. -(*N)-> B), and A
1982  * -> B is -(ER)-> or -(EN)->, then we don't need to add A -> B into the
1983  * dependency graph, as any strong path ..-> A -> B ->.. we can get with
1984  * having dependency A -> B, we could already get a equivalent path ..-> A ->
1985  * .. -> B -> .. with A -> .. -> B. Therefore A -> B is redundant.
1986  *
1987  * We need to make sure both the start and the end of A -> .. -> B is not
1988  * weaker than A -> B. For the start part, please see the comment in
1989  * check_redundant(). For the end part, we need:
1990  *
1991  * Either
1992  *
1993  *     a) A -> B is -(*R)-> (everything is not weaker than that)
1994  *
1995  * or
1996  *
1997  *     b) A -> .. -> B is -(*N)-> (nothing is stronger than this)
1998  *
1999  */
hlock_equal(struct lock_list * entry,void * data)2000 static inline bool hlock_equal(struct lock_list *entry, void *data)
2001 {
2002 	struct held_lock *hlock = (struct held_lock *)data;
2003 
2004 	return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */
2005 	       (hlock->read == 2 ||  /* A -> B is -(*R)-> */
2006 		!entry->only_xr); /* A -> .. -> B is -(*N)-> */
2007 }
2008 
2009 /*
2010  * We are about to add B -> A into the dependency graph, and in __bfs() a
2011  * strong dependency path A -> .. -> B is found: hlock_class equals
2012  * entry->class.
2013  *
2014  * We will have a deadlock case (conflict) if A -> .. -> B -> A is a strong
2015  * dependency cycle, that means:
2016  *
2017  * Either
2018  *
2019  *     a) B -> A is -(E*)->
2020  *
2021  * or
2022  *
2023  *     b) A -> .. -> B is -(*N)-> (i.e. A -> .. -(*N)-> B)
2024  *
2025  * as then we don't have -(*R)-> -(S*)-> in the cycle.
2026  */
hlock_conflict(struct lock_list * entry,void * data)2027 static inline bool hlock_conflict(struct lock_list *entry, void *data)
2028 {
2029 	struct held_lock *hlock = (struct held_lock *)data;
2030 
2031 	return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */
2032 	       (hlock->read == 0 || /* B -> A is -(E*)-> */
2033 		!entry->only_xr); /* A -> .. -> B is -(*N)-> */
2034 }
2035 
print_circular_bug(struct lock_list * this,struct lock_list * target,struct held_lock * check_src,struct held_lock * check_tgt)2036 static noinline void print_circular_bug(struct lock_list *this,
2037 				struct lock_list *target,
2038 				struct held_lock *check_src,
2039 				struct held_lock *check_tgt)
2040 {
2041 	struct task_struct *curr = current;
2042 	struct lock_list *parent;
2043 	struct lock_list *first_parent;
2044 	int depth;
2045 
2046 	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
2047 		return;
2048 
2049 	this->trace = save_trace();
2050 	if (!this->trace)
2051 		return;
2052 
2053 	depth = get_lock_depth(target);
2054 
2055 	nbcon_cpu_emergency_enter();
2056 
2057 	print_circular_bug_header(target, depth, check_src, check_tgt);
2058 
2059 	parent = get_lock_parent(target);
2060 	first_parent = parent;
2061 
2062 	while (parent) {
2063 		print_circular_bug_entry(parent, --depth);
2064 		parent = get_lock_parent(parent);
2065 	}
2066 
2067 	printk("\nother info that might help us debug this:\n\n");
2068 	print_circular_lock_scenario(check_src, check_tgt,
2069 				     first_parent);
2070 
2071 	lockdep_print_held_locks(curr);
2072 
2073 	printk("\nstack backtrace:\n");
2074 	dump_stack();
2075 
2076 	nbcon_cpu_emergency_exit();
2077 }
2078 
print_bfs_bug(int ret)2079 static noinline void print_bfs_bug(int ret)
2080 {
2081 	if (!debug_locks_off_graph_unlock())
2082 		return;
2083 
2084 	/*
2085 	 * Breadth-first-search failed, graph got corrupted?
2086 	 */
2087 	if (ret == BFS_EQUEUEFULL)
2088 		pr_warn("Increase LOCKDEP_CIRCULAR_QUEUE_BITS to avoid this warning:\n");
2089 
2090 	WARN(1, "lockdep bfs error:%d\n", ret);
2091 }
2092 
noop_count(struct lock_list * entry,void * data)2093 static bool noop_count(struct lock_list *entry, void *data)
2094 {
2095 	(*(unsigned long *)data)++;
2096 	return false;
2097 }
2098 
__lockdep_count_forward_deps(struct lock_list * this)2099 static unsigned long __lockdep_count_forward_deps(struct lock_list *this)
2100 {
2101 	unsigned long  count = 0;
2102 	struct lock_list *target_entry;
2103 
2104 	__bfs_forwards(this, (void *)&count, noop_count, NULL, &target_entry);
2105 
2106 	return count;
2107 }
lockdep_count_forward_deps(struct lock_class * class)2108 unsigned long lockdep_count_forward_deps(struct lock_class *class)
2109 {
2110 	unsigned long ret, flags;
2111 	struct lock_list this;
2112 
2113 	__bfs_init_root(&this, class);
2114 
2115 	raw_local_irq_save(flags);
2116 	lockdep_lock();
2117 	ret = __lockdep_count_forward_deps(&this);
2118 	lockdep_unlock();
2119 	raw_local_irq_restore(flags);
2120 
2121 	return ret;
2122 }
2123 
__lockdep_count_backward_deps(struct lock_list * this)2124 static unsigned long __lockdep_count_backward_deps(struct lock_list *this)
2125 {
2126 	unsigned long  count = 0;
2127 	struct lock_list *target_entry;
2128 
2129 	__bfs_backwards(this, (void *)&count, noop_count, NULL, &target_entry);
2130 
2131 	return count;
2132 }
2133 
lockdep_count_backward_deps(struct lock_class * class)2134 unsigned long lockdep_count_backward_deps(struct lock_class *class)
2135 {
2136 	unsigned long ret, flags;
2137 	struct lock_list this;
2138 
2139 	__bfs_init_root(&this, class);
2140 
2141 	raw_local_irq_save(flags);
2142 	lockdep_lock();
2143 	ret = __lockdep_count_backward_deps(&this);
2144 	lockdep_unlock();
2145 	raw_local_irq_restore(flags);
2146 
2147 	return ret;
2148 }
2149 
2150 /*
2151  * Check that the dependency graph starting at <src> can lead to
2152  * <target> or not.
2153  */
2154 static noinline enum bfs_result
check_path(struct held_lock * target,struct lock_list * src_entry,bool (* match)(struct lock_list * entry,void * data),bool (* skip)(struct lock_list * entry,void * data),struct lock_list ** target_entry)2155 check_path(struct held_lock *target, struct lock_list *src_entry,
2156 	   bool (*match)(struct lock_list *entry, void *data),
2157 	   bool (*skip)(struct lock_list *entry, void *data),
2158 	   struct lock_list **target_entry)
2159 {
2160 	enum bfs_result ret;
2161 
2162 	ret = __bfs_forwards(src_entry, target, match, skip, target_entry);
2163 
2164 	if (unlikely(bfs_error(ret)))
2165 		print_bfs_bug(ret);
2166 
2167 	return ret;
2168 }
2169 
2170 static void print_deadlock_bug(struct task_struct *, struct held_lock *, struct held_lock *);
2171 
2172 /*
2173  * Prove that the dependency graph starting at <src> can not
2174  * lead to <target>. If it can, there is a circle when adding
2175  * <target> -> <src> dependency.
2176  *
2177  * Print an error and return BFS_RMATCH if it does.
2178  */
2179 static noinline enum bfs_result
check_noncircular(struct held_lock * src,struct held_lock * target,struct lock_trace ** const trace)2180 check_noncircular(struct held_lock *src, struct held_lock *target,
2181 		  struct lock_trace **const trace)
2182 {
2183 	enum bfs_result ret;
2184 	struct lock_list *target_entry;
2185 	struct lock_list src_entry;
2186 
2187 	bfs_init_root(&src_entry, src);
2188 
2189 	debug_atomic_inc(nr_cyclic_checks);
2190 
2191 	ret = check_path(target, &src_entry, hlock_conflict, NULL, &target_entry);
2192 
2193 	if (unlikely(ret == BFS_RMATCH)) {
2194 		if (!*trace) {
2195 			/*
2196 			 * If save_trace fails here, the printing might
2197 			 * trigger a WARN but because of the !nr_entries it
2198 			 * should not do bad things.
2199 			 */
2200 			*trace = save_trace();
2201 		}
2202 
2203 		if (src->class_idx == target->class_idx)
2204 			print_deadlock_bug(current, src, target);
2205 		else
2206 			print_circular_bug(&src_entry, target_entry, src, target);
2207 	}
2208 
2209 	return ret;
2210 }
2211 
2212 #ifdef CONFIG_TRACE_IRQFLAGS
2213 
2214 /*
2215  * Forwards and backwards subgraph searching, for the purposes of
2216  * proving that two subgraphs can be connected by a new dependency
2217  * without creating any illegal irq-safe -> irq-unsafe lock dependency.
2218  *
2219  * A irq safe->unsafe deadlock happens with the following conditions:
2220  *
2221  * 1) We have a strong dependency path A -> ... -> B
2222  *
2223  * 2) and we have ENABLED_IRQ usage of B and USED_IN_IRQ usage of A, therefore
2224  *    irq can create a new dependency B -> A (consider the case that a holder
2225  *    of B gets interrupted by an irq whose handler will try to acquire A).
2226  *
2227  * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a
2228  *    strong circle:
2229  *
2230  *      For the usage bits of B:
2231  *        a) if A -> B is -(*N)->, then B -> A could be any type, so any
2232  *           ENABLED_IRQ usage suffices.
2233  *        b) if A -> B is -(*R)->, then B -> A must be -(E*)->, so only
2234  *           ENABLED_IRQ_*_READ usage suffices.
2235  *
2236  *      For the usage bits of A:
2237  *        c) if A -> B is -(E*)->, then B -> A could be any type, so any
2238  *           USED_IN_IRQ usage suffices.
2239  *        d) if A -> B is -(S*)->, then B -> A must be -(*N)->, so only
2240  *           USED_IN_IRQ_*_READ usage suffices.
2241  */
2242 
2243 /*
2244  * There is a strong dependency path in the dependency graph: A -> B, and now
2245  * we need to decide which usage bit of A should be accumulated to detect
2246  * safe->unsafe bugs.
2247  *
2248  * Note that usage_accumulate() is used in backwards search, so ->only_xr
2249  * stands for whether A -> B only has -(S*)-> (in this case ->only_xr is true).
2250  *
2251  * As above, if only_xr is false, which means A -> B has -(E*)-> dependency
2252  * path, any usage of A should be considered. Otherwise, we should only
2253  * consider _READ usage.
2254  */
usage_accumulate(struct lock_list * entry,void * mask)2255 static inline bool usage_accumulate(struct lock_list *entry, void *mask)
2256 {
2257 	if (!entry->only_xr)
2258 		*(unsigned long *)mask |= entry->class->usage_mask;
2259 	else /* Mask out _READ usage bits */
2260 		*(unsigned long *)mask |= (entry->class->usage_mask & LOCKF_IRQ);
2261 
2262 	return false;
2263 }
2264 
2265 /*
2266  * There is a strong dependency path in the dependency graph: A -> B, and now
2267  * we need to decide which usage bit of B conflicts with the usage bits of A,
2268  * i.e. which usage bit of B may introduce safe->unsafe deadlocks.
2269  *
2270  * As above, if only_xr is false, which means A -> B has -(*N)-> dependency
2271  * path, any usage of B should be considered. Otherwise, we should only
2272  * consider _READ usage.
2273  */
usage_match(struct lock_list * entry,void * mask)2274 static inline bool usage_match(struct lock_list *entry, void *mask)
2275 {
2276 	if (!entry->only_xr)
2277 		return !!(entry->class->usage_mask & *(unsigned long *)mask);
2278 	else /* Mask out _READ usage bits */
2279 		return !!((entry->class->usage_mask & LOCKF_IRQ) & *(unsigned long *)mask);
2280 }
2281 
usage_skip(struct lock_list * entry,void * mask)2282 static inline bool usage_skip(struct lock_list *entry, void *mask)
2283 {
2284 	if (entry->class->lock_type == LD_LOCK_NORMAL)
2285 		return false;
2286 
2287 	/*
2288 	 * Skip local_lock() for irq inversion detection.
2289 	 *
2290 	 * For !RT, local_lock() is not a real lock, so it won't carry any
2291 	 * dependency.
2292 	 *
2293 	 * For RT, an irq inversion happens when we have lock A and B, and on
2294 	 * some CPU we can have:
2295 	 *
2296 	 *	lock(A);
2297 	 *	<interrupted>
2298 	 *	  lock(B);
2299 	 *
2300 	 * where lock(B) cannot sleep, and we have a dependency B -> ... -> A.
2301 	 *
2302 	 * Now we prove local_lock() cannot exist in that dependency. First we
2303 	 * have the observation for any lock chain L1 -> ... -> Ln, for any
2304 	 * 1 <= i <= n, Li.inner_wait_type <= L1.inner_wait_type, otherwise
2305 	 * wait context check will complain. And since B is not a sleep lock,
2306 	 * therefore B.inner_wait_type >= 2, and since the inner_wait_type of
2307 	 * local_lock() is 3, which is greater than 2, therefore there is no
2308 	 * way the local_lock() exists in the dependency B -> ... -> A.
2309 	 *
2310 	 * As a result, we will skip local_lock(), when we search for irq
2311 	 * inversion bugs.
2312 	 */
2313 	if (entry->class->lock_type == LD_LOCK_PERCPU &&
2314 	    DEBUG_LOCKS_WARN_ON(entry->class->wait_type_inner < LD_WAIT_CONFIG))
2315 		return false;
2316 
2317 	/*
2318 	 * Skip WAIT_OVERRIDE for irq inversion detection -- it's not actually
2319 	 * a lock and only used to override the wait_type.
2320 	 */
2321 
2322 	return true;
2323 }
2324 
2325 /*
2326  * Find a node in the forwards-direction dependency sub-graph starting
2327  * at @root->class that matches @bit.
2328  *
2329  * Return BFS_MATCH if such a node exists in the subgraph, and put that node
2330  * into *@target_entry.
2331  */
2332 static enum bfs_result
find_usage_forwards(struct lock_list * root,unsigned long usage_mask,struct lock_list ** target_entry)2333 find_usage_forwards(struct lock_list *root, unsigned long usage_mask,
2334 			struct lock_list **target_entry)
2335 {
2336 	enum bfs_result result;
2337 
2338 	debug_atomic_inc(nr_find_usage_forwards_checks);
2339 
2340 	result = __bfs_forwards(root, &usage_mask, usage_match, usage_skip, target_entry);
2341 
2342 	return result;
2343 }
2344 
2345 /*
2346  * Find a node in the backwards-direction dependency sub-graph starting
2347  * at @root->class that matches @bit.
2348  */
2349 static enum bfs_result
find_usage_backwards(struct lock_list * root,unsigned long usage_mask,struct lock_list ** target_entry)2350 find_usage_backwards(struct lock_list *root, unsigned long usage_mask,
2351 			struct lock_list **target_entry)
2352 {
2353 	enum bfs_result result;
2354 
2355 	debug_atomic_inc(nr_find_usage_backwards_checks);
2356 
2357 	result = __bfs_backwards(root, &usage_mask, usage_match, usage_skip, target_entry);
2358 
2359 	return result;
2360 }
2361 
print_lock_class_header(struct lock_class * class,int depth)2362 static void print_lock_class_header(struct lock_class *class, int depth)
2363 {
2364 	int bit;
2365 
2366 	printk("%*s->", depth, "");
2367 	print_lock_name(NULL, class);
2368 #ifdef CONFIG_DEBUG_LOCKDEP
2369 	printk(KERN_CONT " ops: %lu", debug_class_ops_read(class));
2370 #endif
2371 	printk(KERN_CONT " {\n");
2372 
2373 	for (bit = 0; bit < LOCK_TRACE_STATES; bit++) {
2374 		if (class->usage_mask & (1 << bit)) {
2375 			int len = depth;
2376 
2377 			len += printk("%*s   %s", depth, "", usage_str[bit]);
2378 			len += printk(KERN_CONT " at:\n");
2379 			print_lock_trace(class->usage_traces[bit], len);
2380 		}
2381 	}
2382 	printk("%*s }\n", depth, "");
2383 
2384 	printk("%*s ... key      at: [<%px>] %pS\n",
2385 		depth, "", class->key, class->key);
2386 }
2387 
2388 /*
2389  * Dependency path printing:
2390  *
2391  * After BFS we get a lock dependency path (linked via ->parent of lock_list),
2392  * printing out each lock in the dependency path will help on understanding how
2393  * the deadlock could happen. Here are some details about dependency path
2394  * printing:
2395  *
2396  * 1)	A lock_list can be either forwards or backwards for a lock dependency,
2397  * 	for a lock dependency A -> B, there are two lock_lists:
2398  *
2399  * 	a)	lock_list in the ->locks_after list of A, whose ->class is B and
2400  * 		->links_to is A. In this case, we can say the lock_list is
2401  * 		"A -> B" (forwards case).
2402  *
2403  * 	b)	lock_list in the ->locks_before list of B, whose ->class is A
2404  * 		and ->links_to is B. In this case, we can say the lock_list is
2405  * 		"B <- A" (bacwards case).
2406  *
2407  * 	The ->trace of both a) and b) point to the call trace where B was
2408  * 	acquired with A held.
2409  *
2410  * 2)	A "helper" lock_list is introduced during BFS, this lock_list doesn't
2411  * 	represent a certain lock dependency, it only provides an initial entry
2412  * 	for BFS. For example, BFS may introduce a "helper" lock_list whose
2413  * 	->class is A, as a result BFS will search all dependencies starting with
2414  * 	A, e.g. A -> B or A -> C.
2415  *
2416  * 	The notation of a forwards helper lock_list is like "-> A", which means
2417  * 	we should search the forwards dependencies starting with "A", e.g A -> B
2418  * 	or A -> C.
2419  *
2420  * 	The notation of a bacwards helper lock_list is like "<- B", which means
2421  * 	we should search the backwards dependencies ending with "B", e.g.
2422  * 	B <- A or B <- C.
2423  */
2424 
2425 /*
2426  * printk the shortest lock dependencies from @root to @leaf in reverse order.
2427  *
2428  * We have a lock dependency path as follow:
2429  *
2430  *    @root                                                                 @leaf
2431  *      |                                                                     |
2432  *      V                                                                     V
2433  *	          ->parent                                   ->parent
2434  * | lock_list | <--------- | lock_list | ... | lock_list  | <--------- | lock_list |
2435  * |    -> L1  |            | L1 -> L2  | ... |Ln-2 -> Ln-1|            | Ln-1 -> Ln|
2436  *
2437  * , so it's natural that we start from @leaf and print every ->class and
2438  * ->trace until we reach the @root.
2439  */
2440 static void __used
print_shortest_lock_dependencies(struct lock_list * leaf,struct lock_list * root)2441 print_shortest_lock_dependencies(struct lock_list *leaf,
2442 				 struct lock_list *root)
2443 {
2444 	struct lock_list *entry = leaf;
2445 	int depth;
2446 
2447 	/*compute depth from generated tree by BFS*/
2448 	depth = get_lock_depth(leaf);
2449 
2450 	do {
2451 		print_lock_class_header(entry->class, depth);
2452 		printk("%*s ... acquired at:\n", depth, "");
2453 		print_lock_trace(entry->trace, 2);
2454 		printk("\n");
2455 
2456 		if (depth == 0 && (entry != root)) {
2457 			printk("lockdep:%s bad path found in chain graph\n", __func__);
2458 			break;
2459 		}
2460 
2461 		entry = get_lock_parent(entry);
2462 		depth--;
2463 	} while (entry && (depth >= 0));
2464 }
2465 
2466 /*
2467  * printk the shortest lock dependencies from @leaf to @root.
2468  *
2469  * We have a lock dependency path (from a backwards search) as follow:
2470  *
2471  *    @leaf                                                                 @root
2472  *      |                                                                     |
2473  *      V                                                                     V
2474  *	          ->parent                                   ->parent
2475  * | lock_list | ---------> | lock_list | ... | lock_list  | ---------> | lock_list |
2476  * | L2 <- L1  |            | L3 <- L2  | ... | Ln <- Ln-1 |            |    <- Ln  |
2477  *
2478  * , so when we iterate from @leaf to @root, we actually print the lock
2479  * dependency path L1 -> L2 -> .. -> Ln in the non-reverse order.
2480  *
2481  * Another thing to notice here is that ->class of L2 <- L1 is L1, while the
2482  * ->trace of L2 <- L1 is the call trace of L2, in fact we don't have the call
2483  * trace of L1 in the dependency path, which is alright, because most of the
2484  * time we can figure out where L1 is held from the call trace of L2.
2485  */
2486 static void __used
print_shortest_lock_dependencies_backwards(struct lock_list * leaf,struct lock_list * root)2487 print_shortest_lock_dependencies_backwards(struct lock_list *leaf,
2488 					   struct lock_list *root)
2489 {
2490 	struct lock_list *entry = leaf;
2491 	const struct lock_trace *trace = NULL;
2492 	int depth;
2493 
2494 	/*compute depth from generated tree by BFS*/
2495 	depth = get_lock_depth(leaf);
2496 
2497 	do {
2498 		print_lock_class_header(entry->class, depth);
2499 		if (trace) {
2500 			printk("%*s ... acquired at:\n", depth, "");
2501 			print_lock_trace(trace, 2);
2502 			printk("\n");
2503 		}
2504 
2505 		/*
2506 		 * Record the pointer to the trace for the next lock_list
2507 		 * entry, see the comments for the function.
2508 		 */
2509 		trace = entry->trace;
2510 
2511 		if (depth == 0 && (entry != root)) {
2512 			printk("lockdep:%s bad path found in chain graph\n", __func__);
2513 			break;
2514 		}
2515 
2516 		entry = get_lock_parent(entry);
2517 		depth--;
2518 	} while (entry && (depth >= 0));
2519 }
2520 
2521 static void
print_irq_lock_scenario(struct lock_list * safe_entry,struct lock_list * unsafe_entry,struct lock_class * prev_class,struct lock_class * next_class)2522 print_irq_lock_scenario(struct lock_list *safe_entry,
2523 			struct lock_list *unsafe_entry,
2524 			struct lock_class *prev_class,
2525 			struct lock_class *next_class)
2526 {
2527 	struct lock_class *safe_class = safe_entry->class;
2528 	struct lock_class *unsafe_class = unsafe_entry->class;
2529 	struct lock_class *middle_class = prev_class;
2530 
2531 	if (middle_class == safe_class)
2532 		middle_class = next_class;
2533 
2534 	/*
2535 	 * A direct locking problem where unsafe_class lock is taken
2536 	 * directly by safe_class lock, then all we need to show
2537 	 * is the deadlock scenario, as it is obvious that the
2538 	 * unsafe lock is taken under the safe lock.
2539 	 *
2540 	 * But if there is a chain instead, where the safe lock takes
2541 	 * an intermediate lock (middle_class) where this lock is
2542 	 * not the same as the safe lock, then the lock chain is
2543 	 * used to describe the problem. Otherwise we would need
2544 	 * to show a different CPU case for each link in the chain
2545 	 * from the safe_class lock to the unsafe_class lock.
2546 	 */
2547 	if (middle_class != unsafe_class) {
2548 		printk("Chain exists of:\n  ");
2549 		__print_lock_name(NULL, safe_class);
2550 		printk(KERN_CONT " --> ");
2551 		__print_lock_name(NULL, middle_class);
2552 		printk(KERN_CONT " --> ");
2553 		__print_lock_name(NULL, unsafe_class);
2554 		printk(KERN_CONT "\n\n");
2555 	}
2556 
2557 	printk(" Possible interrupt unsafe locking scenario:\n\n");
2558 	printk("       CPU0                    CPU1\n");
2559 	printk("       ----                    ----\n");
2560 	printk("  lock(");
2561 	__print_lock_name(NULL, unsafe_class);
2562 	printk(KERN_CONT ");\n");
2563 	printk("                               local_irq_disable();\n");
2564 	printk("                               lock(");
2565 	__print_lock_name(NULL, safe_class);
2566 	printk(KERN_CONT ");\n");
2567 	printk("                               lock(");
2568 	__print_lock_name(NULL, middle_class);
2569 	printk(KERN_CONT ");\n");
2570 	printk("  <Interrupt>\n");
2571 	printk("    lock(");
2572 	__print_lock_name(NULL, safe_class);
2573 	printk(KERN_CONT ");\n");
2574 	printk("\n *** DEADLOCK ***\n\n");
2575 }
2576 
2577 static void
print_bad_irq_dependency(struct task_struct * curr,struct lock_list * prev_root,struct lock_list * next_root,struct lock_list * backwards_entry,struct lock_list * forwards_entry,struct held_lock * prev,struct held_lock * next,enum lock_usage_bit bit1,enum lock_usage_bit bit2,const char * irqclass)2578 print_bad_irq_dependency(struct task_struct *curr,
2579 			 struct lock_list *prev_root,
2580 			 struct lock_list *next_root,
2581 			 struct lock_list *backwards_entry,
2582 			 struct lock_list *forwards_entry,
2583 			 struct held_lock *prev,
2584 			 struct held_lock *next,
2585 			 enum lock_usage_bit bit1,
2586 			 enum lock_usage_bit bit2,
2587 			 const char *irqclass)
2588 {
2589 	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
2590 		return;
2591 
2592 	nbcon_cpu_emergency_enter();
2593 
2594 	pr_warn("\n");
2595 	pr_warn("=====================================================\n");
2596 	pr_warn("WARNING: %s-safe -> %s-unsafe lock order detected\n",
2597 		irqclass, irqclass);
2598 	print_kernel_ident();
2599 	pr_warn("-----------------------------------------------------\n");
2600 	pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] is trying to acquire:\n",
2601 		curr->comm, task_pid_nr(curr),
2602 		lockdep_hardirq_context(), hardirq_count() >> HARDIRQ_SHIFT,
2603 		curr->softirq_context, softirq_count() >> SOFTIRQ_SHIFT,
2604 		lockdep_hardirqs_enabled(),
2605 		curr->softirqs_enabled);
2606 	print_lock(next);
2607 
2608 	pr_warn("\nand this task is already holding:\n");
2609 	print_lock(prev);
2610 	pr_warn("which would create a new lock dependency:\n");
2611 	print_lock_name(prev, hlock_class(prev));
2612 	pr_cont(" ->");
2613 	print_lock_name(next, hlock_class(next));
2614 	pr_cont("\n");
2615 
2616 	pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",
2617 		irqclass);
2618 	print_lock_name(NULL, backwards_entry->class);
2619 	pr_warn("\n... which became %s-irq-safe at:\n", irqclass);
2620 
2621 	print_lock_trace(backwards_entry->class->usage_traces[bit1], 1);
2622 
2623 	pr_warn("\nto a %s-irq-unsafe lock:\n", irqclass);
2624 	print_lock_name(NULL, forwards_entry->class);
2625 	pr_warn("\n... which became %s-irq-unsafe at:\n", irqclass);
2626 	pr_warn("...");
2627 
2628 	print_lock_trace(forwards_entry->class->usage_traces[bit2], 1);
2629 
2630 	pr_warn("\nother info that might help us debug this:\n\n");
2631 	print_irq_lock_scenario(backwards_entry, forwards_entry,
2632 				hlock_class(prev), hlock_class(next));
2633 
2634 	lockdep_print_held_locks(curr);
2635 
2636 	pr_warn("\nthe dependencies between %s-irq-safe lock and the holding lock:\n", irqclass);
2637 	print_shortest_lock_dependencies_backwards(backwards_entry, prev_root);
2638 
2639 	pr_warn("\nthe dependencies between the lock to be acquired");
2640 	pr_warn(" and %s-irq-unsafe lock:\n", irqclass);
2641 	next_root->trace = save_trace();
2642 	if (!next_root->trace)
2643 		goto out;
2644 	print_shortest_lock_dependencies(forwards_entry, next_root);
2645 
2646 	pr_warn("\nstack backtrace:\n");
2647 	dump_stack();
2648 out:
2649 	nbcon_cpu_emergency_exit();
2650 }
2651 
2652 static const char *state_names[] = {
2653 #define LOCKDEP_STATE(__STATE) \
2654 	__stringify(__STATE),
2655 #include "lockdep_states.h"
2656 #undef LOCKDEP_STATE
2657 };
2658 
2659 static const char *state_rnames[] = {
2660 #define LOCKDEP_STATE(__STATE) \
2661 	__stringify(__STATE)"-READ",
2662 #include "lockdep_states.h"
2663 #undef LOCKDEP_STATE
2664 };
2665 
state_name(enum lock_usage_bit bit)2666 static inline const char *state_name(enum lock_usage_bit bit)
2667 {
2668 	if (bit & LOCK_USAGE_READ_MASK)
2669 		return state_rnames[bit >> LOCK_USAGE_DIR_MASK];
2670 	else
2671 		return state_names[bit >> LOCK_USAGE_DIR_MASK];
2672 }
2673 
2674 /*
2675  * The bit number is encoded like:
2676  *
2677  *  bit0: 0 exclusive, 1 read lock
2678  *  bit1: 0 used in irq, 1 irq enabled
2679  *  bit2-n: state
2680  */
exclusive_bit(int new_bit)2681 static int exclusive_bit(int new_bit)
2682 {
2683 	int state = new_bit & LOCK_USAGE_STATE_MASK;
2684 	int dir = new_bit & LOCK_USAGE_DIR_MASK;
2685 
2686 	/*
2687 	 * keep state, bit flip the direction and strip read.
2688 	 */
2689 	return state | (dir ^ LOCK_USAGE_DIR_MASK);
2690 }
2691 
2692 /*
2693  * Observe that when given a bitmask where each bitnr is encoded as above, a
2694  * right shift of the mask transforms the individual bitnrs as -1 and
2695  * conversely, a left shift transforms into +1 for the individual bitnrs.
2696  *
2697  * So for all bits whose number have LOCK_ENABLED_* set (bitnr1 == 1), we can
2698  * create the mask with those bit numbers using LOCK_USED_IN_* (bitnr1 == 0)
2699  * instead by subtracting the bit number by 2, or shifting the mask right by 2.
2700  *
2701  * Similarly, bitnr1 == 0 becomes bitnr1 == 1 by adding 2, or shifting left 2.
2702  *
2703  * So split the mask (note that LOCKF_ENABLED_IRQ_ALL|LOCKF_USED_IN_IRQ_ALL is
2704  * all bits set) and recompose with bitnr1 flipped.
2705  */
invert_dir_mask(unsigned long mask)2706 static unsigned long invert_dir_mask(unsigned long mask)
2707 {
2708 	unsigned long excl = 0;
2709 
2710 	/* Invert dir */
2711 	excl |= (mask & LOCKF_ENABLED_IRQ_ALL) >> LOCK_USAGE_DIR_MASK;
2712 	excl |= (mask & LOCKF_USED_IN_IRQ_ALL) << LOCK_USAGE_DIR_MASK;
2713 
2714 	return excl;
2715 }
2716 
2717 /*
2718  * Note that a LOCK_ENABLED_IRQ_*_READ usage and a LOCK_USED_IN_IRQ_*_READ
2719  * usage may cause deadlock too, for example:
2720  *
2721  * P1				P2
2722  * <irq disabled>
2723  * write_lock(l1);		<irq enabled>
2724  *				read_lock(l2);
2725  * write_lock(l2);
2726  * 				<in irq>
2727  * 				read_lock(l1);
2728  *
2729  * , in above case, l1 will be marked as LOCK_USED_IN_IRQ_HARDIRQ_READ and l2
2730  * will marked as LOCK_ENABLE_IRQ_HARDIRQ_READ, and this is a possible
2731  * deadlock.
2732  *
2733  * In fact, all of the following cases may cause deadlocks:
2734  *
2735  * 	 LOCK_USED_IN_IRQ_* -> LOCK_ENABLED_IRQ_*
2736  * 	 LOCK_USED_IN_IRQ_*_READ -> LOCK_ENABLED_IRQ_*
2737  * 	 LOCK_USED_IN_IRQ_* -> LOCK_ENABLED_IRQ_*_READ
2738  * 	 LOCK_USED_IN_IRQ_*_READ -> LOCK_ENABLED_IRQ_*_READ
2739  *
2740  * As a result, to calculate the "exclusive mask", first we invert the
2741  * direction (USED_IN/ENABLED) of the original mask, and 1) for all bits with
2742  * bitnr0 set (LOCK_*_READ), add those with bitnr0 cleared (LOCK_*). 2) for all
2743  * bits with bitnr0 cleared (LOCK_*_READ), add those with bitnr0 set (LOCK_*).
2744  */
exclusive_mask(unsigned long mask)2745 static unsigned long exclusive_mask(unsigned long mask)
2746 {
2747 	unsigned long excl = invert_dir_mask(mask);
2748 
2749 	excl |= (excl & LOCKF_IRQ_READ) >> LOCK_USAGE_READ_MASK;
2750 	excl |= (excl & LOCKF_IRQ) << LOCK_USAGE_READ_MASK;
2751 
2752 	return excl;
2753 }
2754 
2755 /*
2756  * Retrieve the _possible_ original mask to which @mask is
2757  * exclusive. Ie: this is the opposite of exclusive_mask().
2758  * Note that 2 possible original bits can match an exclusive
2759  * bit: one has LOCK_USAGE_READ_MASK set, the other has it
2760  * cleared. So both are returned for each exclusive bit.
2761  */
original_mask(unsigned long mask)2762 static unsigned long original_mask(unsigned long mask)
2763 {
2764 	unsigned long excl = invert_dir_mask(mask);
2765 
2766 	/* Include read in existing usages */
2767 	excl |= (excl & LOCKF_IRQ_READ) >> LOCK_USAGE_READ_MASK;
2768 	excl |= (excl & LOCKF_IRQ) << LOCK_USAGE_READ_MASK;
2769 
2770 	return excl;
2771 }
2772 
2773 /*
2774  * Find the first pair of bit match between an original
2775  * usage mask and an exclusive usage mask.
2776  */
find_exclusive_match(unsigned long mask,unsigned long excl_mask,enum lock_usage_bit * bitp,enum lock_usage_bit * excl_bitp)2777 static int find_exclusive_match(unsigned long mask,
2778 				unsigned long excl_mask,
2779 				enum lock_usage_bit *bitp,
2780 				enum lock_usage_bit *excl_bitp)
2781 {
2782 	int bit, excl, excl_read;
2783 
2784 	for_each_set_bit(bit, &mask, LOCK_USED) {
2785 		/*
2786 		 * exclusive_bit() strips the read bit, however,
2787 		 * LOCK_ENABLED_IRQ_*_READ may cause deadlocks too, so we need
2788 		 * to search excl | LOCK_USAGE_READ_MASK as well.
2789 		 */
2790 		excl = exclusive_bit(bit);
2791 		excl_read = excl | LOCK_USAGE_READ_MASK;
2792 		if (excl_mask & lock_flag(excl)) {
2793 			*bitp = bit;
2794 			*excl_bitp = excl;
2795 			return 0;
2796 		} else if (excl_mask & lock_flag(excl_read)) {
2797 			*bitp = bit;
2798 			*excl_bitp = excl_read;
2799 			return 0;
2800 		}
2801 	}
2802 	return -1;
2803 }
2804 
2805 /*
2806  * Prove that the new dependency does not connect a hardirq-safe(-read)
2807  * lock with a hardirq-unsafe lock - to achieve this we search
2808  * the backwards-subgraph starting at <prev>, and the
2809  * forwards-subgraph starting at <next>:
2810  */
check_irq_usage(struct task_struct * curr,struct held_lock * prev,struct held_lock * next)2811 static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
2812 			   struct held_lock *next)
2813 {
2814 	unsigned long usage_mask = 0, forward_mask, backward_mask;
2815 	enum lock_usage_bit forward_bit = 0, backward_bit = 0;
2816 	struct lock_list *target_entry1;
2817 	struct lock_list *target_entry;
2818 	struct lock_list this, that;
2819 	enum bfs_result ret;
2820 
2821 	/*
2822 	 * Step 1: gather all hard/soft IRQs usages backward in an
2823 	 * accumulated usage mask.
2824 	 */
2825 	bfs_init_rootb(&this, prev);
2826 
2827 	ret = __bfs_backwards(&this, &usage_mask, usage_accumulate, usage_skip, NULL);
2828 	if (bfs_error(ret)) {
2829 		print_bfs_bug(ret);
2830 		return 0;
2831 	}
2832 
2833 	usage_mask &= LOCKF_USED_IN_IRQ_ALL;
2834 	if (!usage_mask)
2835 		return 1;
2836 
2837 	/*
2838 	 * Step 2: find exclusive uses forward that match the previous
2839 	 * backward accumulated mask.
2840 	 */
2841 	forward_mask = exclusive_mask(usage_mask);
2842 
2843 	bfs_init_root(&that, next);
2844 
2845 	ret = find_usage_forwards(&that, forward_mask, &target_entry1);
2846 	if (bfs_error(ret)) {
2847 		print_bfs_bug(ret);
2848 		return 0;
2849 	}
2850 	if (ret == BFS_RNOMATCH)
2851 		return 1;
2852 
2853 	/*
2854 	 * Step 3: we found a bad match! Now retrieve a lock from the backward
2855 	 * list whose usage mask matches the exclusive usage mask from the
2856 	 * lock found on the forward list.
2857 	 *
2858 	 * Note, we should only keep the LOCKF_ENABLED_IRQ_ALL bits, considering
2859 	 * the follow case:
2860 	 *
2861 	 * When trying to add A -> B to the graph, we find that there is a
2862 	 * hardirq-safe L, that L -> ... -> A, and another hardirq-unsafe M,
2863 	 * that B -> ... -> M. However M is **softirq-safe**, if we use exact
2864 	 * invert bits of M's usage_mask, we will find another lock N that is
2865 	 * **softirq-unsafe** and N -> ... -> A, however N -> .. -> M will not
2866 	 * cause a inversion deadlock.
2867 	 */
2868 	backward_mask = original_mask(target_entry1->class->usage_mask & LOCKF_ENABLED_IRQ_ALL);
2869 
2870 	ret = find_usage_backwards(&this, backward_mask, &target_entry);
2871 	if (bfs_error(ret)) {
2872 		print_bfs_bug(ret);
2873 		return 0;
2874 	}
2875 	if (DEBUG_LOCKS_WARN_ON(ret == BFS_RNOMATCH))
2876 		return 1;
2877 
2878 	/*
2879 	 * Step 4: narrow down to a pair of incompatible usage bits
2880 	 * and report it.
2881 	 */
2882 	ret = find_exclusive_match(target_entry->class->usage_mask,
2883 				   target_entry1->class->usage_mask,
2884 				   &backward_bit, &forward_bit);
2885 	if (DEBUG_LOCKS_WARN_ON(ret == -1))
2886 		return 1;
2887 
2888 	print_bad_irq_dependency(curr, &this, &that,
2889 				 target_entry, target_entry1,
2890 				 prev, next,
2891 				 backward_bit, forward_bit,
2892 				 state_name(backward_bit));
2893 
2894 	return 0;
2895 }
2896 
2897 #else
2898 
check_irq_usage(struct task_struct * curr,struct held_lock * prev,struct held_lock * next)2899 static inline int check_irq_usage(struct task_struct *curr,
2900 				  struct held_lock *prev, struct held_lock *next)
2901 {
2902 	return 1;
2903 }
2904 
usage_skip(struct lock_list * entry,void * mask)2905 static inline bool usage_skip(struct lock_list *entry, void *mask)
2906 {
2907 	return false;
2908 }
2909 
2910 #endif /* CONFIG_TRACE_IRQFLAGS */
2911 
2912 #ifdef CONFIG_LOCKDEP_SMALL
2913 /*
2914  * Check that the dependency graph starting at <src> can lead to
2915  * <target> or not. If it can, <src> -> <target> dependency is already
2916  * in the graph.
2917  *
2918  * Return BFS_RMATCH if it does, or BFS_RNOMATCH if it does not, return BFS_E* if
2919  * any error appears in the bfs search.
2920  */
2921 static noinline enum bfs_result
check_redundant(struct held_lock * src,struct held_lock * target)2922 check_redundant(struct held_lock *src, struct held_lock *target)
2923 {
2924 	enum bfs_result ret;
2925 	struct lock_list *target_entry;
2926 	struct lock_list src_entry;
2927 
2928 	bfs_init_root(&src_entry, src);
2929 	/*
2930 	 * Special setup for check_redundant().
2931 	 *
2932 	 * To report redundant, we need to find a strong dependency path that
2933 	 * is equal to or stronger than <src> -> <target>. So if <src> is E,
2934 	 * we need to let __bfs() only search for a path starting at a -(E*)->,
2935 	 * we achieve this by setting the initial node's ->only_xr to true in
2936 	 * that case. And if <prev> is S, we set initial ->only_xr to false
2937 	 * because both -(S*)-> (equal) and -(E*)-> (stronger) are redundant.
2938 	 */
2939 	src_entry.only_xr = src->read == 0;
2940 
2941 	debug_atomic_inc(nr_redundant_checks);
2942 
2943 	/*
2944 	 * Note: we skip local_lock() for redundant check, because as the
2945 	 * comment in usage_skip(), A -> local_lock() -> B and A -> B are not
2946 	 * the same.
2947 	 */
2948 	ret = check_path(target, &src_entry, hlock_equal, usage_skip, &target_entry);
2949 
2950 	if (ret == BFS_RMATCH)
2951 		debug_atomic_inc(nr_redundant);
2952 
2953 	return ret;
2954 }
2955 
2956 #else
2957 
2958 static inline enum bfs_result
check_redundant(struct held_lock * src,struct held_lock * target)2959 check_redundant(struct held_lock *src, struct held_lock *target)
2960 {
2961 	return BFS_RNOMATCH;
2962 }
2963 
2964 #endif
2965 
inc_chains(int irq_context)2966 static void inc_chains(int irq_context)
2967 {
2968 	if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT)
2969 		nr_hardirq_chains++;
2970 	else if (irq_context & LOCK_CHAIN_SOFTIRQ_CONTEXT)
2971 		nr_softirq_chains++;
2972 	else
2973 		nr_process_chains++;
2974 }
2975 
dec_chains(int irq_context)2976 static void dec_chains(int irq_context)
2977 {
2978 	if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT)
2979 		nr_hardirq_chains--;
2980 	else if (irq_context & LOCK_CHAIN_SOFTIRQ_CONTEXT)
2981 		nr_softirq_chains--;
2982 	else
2983 		nr_process_chains--;
2984 }
2985 
2986 static void
print_deadlock_scenario(struct held_lock * nxt,struct held_lock * prv)2987 print_deadlock_scenario(struct held_lock *nxt, struct held_lock *prv)
2988 {
2989 	struct lock_class *next = hlock_class(nxt);
2990 	struct lock_class *prev = hlock_class(prv);
2991 
2992 	printk(" Possible unsafe locking scenario:\n\n");
2993 	printk("       CPU0\n");
2994 	printk("       ----\n");
2995 	printk("  lock(");
2996 	__print_lock_name(prv, prev);
2997 	printk(KERN_CONT ");\n");
2998 	printk("  lock(");
2999 	__print_lock_name(nxt, next);
3000 	printk(KERN_CONT ");\n");
3001 	printk("\n *** DEADLOCK ***\n\n");
3002 	printk(" May be due to missing lock nesting notation\n\n");
3003 }
3004 
3005 static void
print_deadlock_bug(struct task_struct * curr,struct held_lock * prev,struct held_lock * next)3006 print_deadlock_bug(struct task_struct *curr, struct held_lock *prev,
3007 		   struct held_lock *next)
3008 {
3009 	struct lock_class *class = hlock_class(prev);
3010 
3011 	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
3012 		return;
3013 
3014 	nbcon_cpu_emergency_enter();
3015 
3016 	pr_warn("\n");
3017 	pr_warn("============================================\n");
3018 	pr_warn("WARNING: possible recursive locking detected\n");
3019 	print_kernel_ident();
3020 	pr_warn("--------------------------------------------\n");
3021 	pr_warn("%s/%d is trying to acquire lock:\n",
3022 		curr->comm, task_pid_nr(curr));
3023 	print_lock(next);
3024 	pr_warn("\nbut task is already holding lock:\n");
3025 	print_lock(prev);
3026 
3027 	if (class->cmp_fn) {
3028 		pr_warn("and the lock comparison function returns %i:\n",
3029 			class->cmp_fn(prev->instance, next->instance));
3030 	}
3031 
3032 	pr_warn("\nother info that might help us debug this:\n");
3033 	print_deadlock_scenario(next, prev);
3034 	lockdep_print_held_locks(curr);
3035 
3036 	pr_warn("\nstack backtrace:\n");
3037 	dump_stack();
3038 
3039 	nbcon_cpu_emergency_exit();
3040 }
3041 
3042 /*
3043  * Check whether we are holding such a class already.
3044  *
3045  * (Note that this has to be done separately, because the graph cannot
3046  * detect such classes of deadlocks.)
3047  *
3048  * Returns: 0 on deadlock detected, 1 on OK, 2 if another lock with the same
3049  * lock class is held but nest_lock is also held, i.e. we rely on the
3050  * nest_lock to avoid the deadlock.
3051  */
3052 static int
check_deadlock(struct task_struct * curr,struct held_lock * next)3053 check_deadlock(struct task_struct *curr, struct held_lock *next)
3054 {
3055 	struct lock_class *class;
3056 	struct held_lock *prev;
3057 	struct held_lock *nest = NULL;
3058 	int i;
3059 
3060 	for (i = 0; i < curr->lockdep_depth; i++) {
3061 		prev = curr->held_locks + i;
3062 
3063 		if (prev->instance == next->nest_lock)
3064 			nest = prev;
3065 
3066 		if (hlock_class(prev) != hlock_class(next))
3067 			continue;
3068 
3069 		/*
3070 		 * Allow read-after-read recursion of the same
3071 		 * lock class (i.e. read_lock(lock)+read_lock(lock)):
3072 		 */
3073 		if ((next->read == 2) && prev->read)
3074 			continue;
3075 
3076 		class = hlock_class(prev);
3077 
3078 		if (class->cmp_fn &&
3079 		    class->cmp_fn(prev->instance, next->instance) < 0)
3080 			continue;
3081 
3082 		/*
3083 		 * We're holding the nest_lock, which serializes this lock's
3084 		 * nesting behaviour.
3085 		 */
3086 		if (nest)
3087 			return 2;
3088 
3089 		print_deadlock_bug(curr, prev, next);
3090 		return 0;
3091 	}
3092 	return 1;
3093 }
3094 
3095 /*
3096  * There was a chain-cache miss, and we are about to add a new dependency
3097  * to a previous lock. We validate the following rules:
3098  *
3099  *  - would the adding of the <prev> -> <next> dependency create a
3100  *    circular dependency in the graph? [== circular deadlock]
3101  *
3102  *  - does the new prev->next dependency connect any hardirq-safe lock
3103  *    (in the full backwards-subgraph starting at <prev>) with any
3104  *    hardirq-unsafe lock (in the full forwards-subgraph starting at
3105  *    <next>)? [== illegal lock inversion with hardirq contexts]
3106  *
3107  *  - does the new prev->next dependency connect any softirq-safe lock
3108  *    (in the full backwards-subgraph starting at <prev>) with any
3109  *    softirq-unsafe lock (in the full forwards-subgraph starting at
3110  *    <next>)? [== illegal lock inversion with softirq contexts]
3111  *
3112  * any of these scenarios could lead to a deadlock.
3113  *
3114  * Then if all the validations pass, we add the forwards and backwards
3115  * dependency.
3116  */
3117 static int
check_prev_add(struct task_struct * curr,struct held_lock * prev,struct held_lock * next,u16 distance,struct lock_trace ** const trace)3118 check_prev_add(struct task_struct *curr, struct held_lock *prev,
3119 	       struct held_lock *next, u16 distance,
3120 	       struct lock_trace **const trace)
3121 {
3122 	struct lock_list *entry;
3123 	enum bfs_result ret;
3124 
3125 	if (!hlock_class(prev)->key || !hlock_class(next)->key) {
3126 		/*
3127 		 * The warning statements below may trigger a use-after-free
3128 		 * of the class name. It is better to trigger a use-after free
3129 		 * and to have the class name most of the time instead of not
3130 		 * having the class name available.
3131 		 */
3132 		WARN_ONCE(!debug_locks_silent && !hlock_class(prev)->key,
3133 			  "Detected use-after-free of lock class %px/%s\n",
3134 			  hlock_class(prev),
3135 			  hlock_class(prev)->name);
3136 		WARN_ONCE(!debug_locks_silent && !hlock_class(next)->key,
3137 			  "Detected use-after-free of lock class %px/%s\n",
3138 			  hlock_class(next),
3139 			  hlock_class(next)->name);
3140 		return 2;
3141 	}
3142 
3143 	if (prev->class_idx == next->class_idx) {
3144 		struct lock_class *class = hlock_class(prev);
3145 
3146 		if (class->cmp_fn &&
3147 		    class->cmp_fn(prev->instance, next->instance) < 0)
3148 			return 2;
3149 	}
3150 
3151 	/*
3152 	 * Prove that the new <prev> -> <next> dependency would not
3153 	 * create a circular dependency in the graph. (We do this by
3154 	 * a breadth-first search into the graph starting at <next>,
3155 	 * and check whether we can reach <prev>.)
3156 	 *
3157 	 * The search is limited by the size of the circular queue (i.e.,
3158 	 * MAX_CIRCULAR_QUEUE_SIZE) which keeps track of a breadth of nodes
3159 	 * in the graph whose neighbours are to be checked.
3160 	 */
3161 	ret = check_noncircular(next, prev, trace);
3162 	if (unlikely(bfs_error(ret) || ret == BFS_RMATCH))
3163 		return 0;
3164 
3165 	if (!check_irq_usage(curr, prev, next))
3166 		return 0;
3167 
3168 	/*
3169 	 * Is the <prev> -> <next> dependency already present?
3170 	 *
3171 	 * (this may occur even though this is a new chain: consider
3172 	 *  e.g. the L1 -> L2 -> L3 -> L4 and the L5 -> L1 -> L2 -> L3
3173 	 *  chains - the second one will be new, but L1 already has
3174 	 *  L2 added to its dependency list, due to the first chain.)
3175 	 */
3176 	list_for_each_entry(entry, &hlock_class(prev)->locks_after, entry) {
3177 		if (entry->class == hlock_class(next)) {
3178 			if (distance == 1)
3179 				entry->distance = 1;
3180 			entry->dep |= calc_dep(prev, next);
3181 
3182 			/*
3183 			 * Also, update the reverse dependency in @next's
3184 			 * ->locks_before list.
3185 			 *
3186 			 *  Here we reuse @entry as the cursor, which is fine
3187 			 *  because we won't go to the next iteration of the
3188 			 *  outer loop:
3189 			 *
3190 			 *  For normal cases, we return in the inner loop.
3191 			 *
3192 			 *  If we fail to return, we have inconsistency, i.e.
3193 			 *  <prev>::locks_after contains <next> while
3194 			 *  <next>::locks_before doesn't contain <prev>. In
3195 			 *  that case, we return after the inner and indicate
3196 			 *  something is wrong.
3197 			 */
3198 			list_for_each_entry(entry, &hlock_class(next)->locks_before, entry) {
3199 				if (entry->class == hlock_class(prev)) {
3200 					if (distance == 1)
3201 						entry->distance = 1;
3202 					entry->dep |= calc_depb(prev, next);
3203 					return 1;
3204 				}
3205 			}
3206 
3207 			/* <prev> is not found in <next>::locks_before */
3208 			return 0;
3209 		}
3210 	}
3211 
3212 	/*
3213 	 * Is the <prev> -> <next> link redundant?
3214 	 */
3215 	ret = check_redundant(prev, next);
3216 	if (bfs_error(ret))
3217 		return 0;
3218 	else if (ret == BFS_RMATCH)
3219 		return 2;
3220 
3221 	if (!*trace) {
3222 		*trace = save_trace();
3223 		if (!*trace)
3224 			return 0;
3225 	}
3226 
3227 	/*
3228 	 * Ok, all validations passed, add the new lock
3229 	 * to the previous lock's dependency list:
3230 	 */
3231 	ret = add_lock_to_list(hlock_class(next), hlock_class(prev),
3232 			       &hlock_class(prev)->locks_after, distance,
3233 			       calc_dep(prev, next), *trace);
3234 
3235 	if (!ret)
3236 		return 0;
3237 
3238 	ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
3239 			       &hlock_class(next)->locks_before, distance,
3240 			       calc_depb(prev, next), *trace);
3241 	if (!ret)
3242 		return 0;
3243 
3244 	return 2;
3245 }
3246 
3247 /*
3248  * Add the dependency to all directly-previous locks that are 'relevant'.
3249  * The ones that are relevant are (in increasing distance from curr):
3250  * all consecutive trylock entries and the final non-trylock entry - or
3251  * the end of this context's lock-chain - whichever comes first.
3252  */
3253 static int
check_prevs_add(struct task_struct * curr,struct held_lock * next)3254 check_prevs_add(struct task_struct *curr, struct held_lock *next)
3255 {
3256 	struct lock_trace *trace = NULL;
3257 	int depth = curr->lockdep_depth;
3258 	struct held_lock *hlock;
3259 
3260 	/*
3261 	 * Debugging checks.
3262 	 *
3263 	 * Depth must not be zero for a non-head lock:
3264 	 */
3265 	if (!depth)
3266 		goto out_bug;
3267 	/*
3268 	 * At least two relevant locks must exist for this
3269 	 * to be a head:
3270 	 */
3271 	if (curr->held_locks[depth].irq_context !=
3272 			curr->held_locks[depth-1].irq_context)
3273 		goto out_bug;
3274 
3275 	for (;;) {
3276 		u16 distance = curr->lockdep_depth - depth + 1;
3277 		hlock = curr->held_locks + depth - 1;
3278 
3279 		if (hlock->check) {
3280 			int ret = check_prev_add(curr, hlock, next, distance, &trace);
3281 			if (!ret)
3282 				return 0;
3283 
3284 			/*
3285 			 * Stop after the first non-trylock entry,
3286 			 * as non-trylock entries have added their
3287 			 * own direct dependencies already, so this
3288 			 * lock is connected to them indirectly:
3289 			 */
3290 			if (!hlock->trylock)
3291 				break;
3292 		}
3293 
3294 		depth--;
3295 		/*
3296 		 * End of lock-stack?
3297 		 */
3298 		if (!depth)
3299 			break;
3300 		/*
3301 		 * Stop the search if we cross into another context:
3302 		 */
3303 		if (curr->held_locks[depth].irq_context !=
3304 				curr->held_locks[depth-1].irq_context)
3305 			break;
3306 	}
3307 	return 1;
3308 out_bug:
3309 	if (!debug_locks_off_graph_unlock())
3310 		return 0;
3311 
3312 	/*
3313 	 * Clearly we all shouldn't be here, but since we made it we
3314 	 * can reliable say we messed up our state. See the above two
3315 	 * gotos for reasons why we could possibly end up here.
3316 	 */
3317 	WARN_ON(1);
3318 
3319 	return 0;
3320 }
3321 
3322 struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS];
3323 static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
3324 static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
3325 unsigned long nr_zapped_lock_chains;
3326 unsigned int nr_free_chain_hlocks;	/* Free chain_hlocks in buckets */
3327 unsigned int nr_lost_chain_hlocks;	/* Lost chain_hlocks */
3328 unsigned int nr_large_chain_blocks;	/* size > MAX_CHAIN_BUCKETS */
3329 
3330 /*
3331  * The first 2 chain_hlocks entries in the chain block in the bucket
3332  * list contains the following meta data:
3333  *
3334  *   entry[0]:
3335  *     Bit    15 - always set to 1 (it is not a class index)
3336  *     Bits 0-14 - upper 15 bits of the next block index
3337  *   entry[1]    - lower 16 bits of next block index
3338  *
3339  * A next block index of all 1 bits means it is the end of the list.
3340  *
3341  * On the unsized bucket (bucket-0), the 3rd and 4th entries contain
3342  * the chain block size:
3343  *
3344  *   entry[2] - upper 16 bits of the chain block size
3345  *   entry[3] - lower 16 bits of the chain block size
3346  */
3347 #define MAX_CHAIN_BUCKETS	16
3348 #define CHAIN_BLK_FLAG		(1U << 15)
3349 #define CHAIN_BLK_LIST_END	0xFFFFU
3350 
3351 static int chain_block_buckets[MAX_CHAIN_BUCKETS];
3352 
size_to_bucket(int size)3353 static inline int size_to_bucket(int size)
3354 {
3355 	if (size > MAX_CHAIN_BUCKETS)
3356 		return 0;
3357 
3358 	return size - 1;
3359 }
3360 
3361 /*
3362  * Iterate all the chain blocks in a bucket.
3363  */
3364 #define for_each_chain_block(bucket, prev, curr)		\
3365 	for ((prev) = -1, (curr) = chain_block_buckets[bucket];	\
3366 	     (curr) >= 0;					\
3367 	     (prev) = (curr), (curr) = chain_block_next(curr))
3368 
3369 /*
3370  * next block or -1
3371  */
chain_block_next(int offset)3372 static inline int chain_block_next(int offset)
3373 {
3374 	int next = chain_hlocks[offset];
3375 
3376 	WARN_ON_ONCE(!(next & CHAIN_BLK_FLAG));
3377 
3378 	if (next == CHAIN_BLK_LIST_END)
3379 		return -1;
3380 
3381 	next &= ~CHAIN_BLK_FLAG;
3382 	next <<= 16;
3383 	next |= chain_hlocks[offset + 1];
3384 
3385 	return next;
3386 }
3387 
3388 /*
3389  * bucket-0 only
3390  */
chain_block_size(int offset)3391 static inline int chain_block_size(int offset)
3392 {
3393 	return (chain_hlocks[offset + 2] << 16) | chain_hlocks[offset + 3];
3394 }
3395 
init_chain_block(int offset,int next,int bucket,int size)3396 static inline void init_chain_block(int offset, int next, int bucket, int size)
3397 {
3398 	chain_hlocks[offset] = (next >> 16) | CHAIN_BLK_FLAG;
3399 	chain_hlocks[offset + 1] = (u16)next;
3400 
3401 	if (size && !bucket) {
3402 		chain_hlocks[offset + 2] = size >> 16;
3403 		chain_hlocks[offset + 3] = (u16)size;
3404 	}
3405 }
3406 
add_chain_block(int offset,int size)3407 static inline void add_chain_block(int offset, int size)
3408 {
3409 	int bucket = size_to_bucket(size);
3410 	int next = chain_block_buckets[bucket];
3411 	int prev, curr;
3412 
3413 	if (unlikely(size < 2)) {
3414 		/*
3415 		 * We can't store single entries on the freelist. Leak them.
3416 		 *
3417 		 * One possible way out would be to uniquely mark them, other
3418 		 * than with CHAIN_BLK_FLAG, such that we can recover them when
3419 		 * the block before it is re-added.
3420 		 */
3421 		if (size)
3422 			nr_lost_chain_hlocks++;
3423 		return;
3424 	}
3425 
3426 	nr_free_chain_hlocks += size;
3427 	if (!bucket) {
3428 		nr_large_chain_blocks++;
3429 
3430 		/*
3431 		 * Variable sized, sort large to small.
3432 		 */
3433 		for_each_chain_block(0, prev, curr) {
3434 			if (size >= chain_block_size(curr))
3435 				break;
3436 		}
3437 		init_chain_block(offset, curr, 0, size);
3438 		if (prev < 0)
3439 			chain_block_buckets[0] = offset;
3440 		else
3441 			init_chain_block(prev, offset, 0, 0);
3442 		return;
3443 	}
3444 	/*
3445 	 * Fixed size, add to head.
3446 	 */
3447 	init_chain_block(offset, next, bucket, size);
3448 	chain_block_buckets[bucket] = offset;
3449 }
3450 
3451 /*
3452  * Only the first block in the list can be deleted.
3453  *
3454  * For the variable size bucket[0], the first block (the largest one) is
3455  * returned, broken up and put back into the pool. So if a chain block of
3456  * length > MAX_CHAIN_BUCKETS is ever used and zapped, it will just be
3457  * queued up after the primordial chain block and never be used until the
3458  * hlock entries in the primordial chain block is almost used up. That
3459  * causes fragmentation and reduce allocation efficiency. That can be
3460  * monitored by looking at the "large chain blocks" number in lockdep_stats.
3461  */
del_chain_block(int bucket,int size,int next)3462 static inline void del_chain_block(int bucket, int size, int next)
3463 {
3464 	nr_free_chain_hlocks -= size;
3465 	chain_block_buckets[bucket] = next;
3466 
3467 	if (!bucket)
3468 		nr_large_chain_blocks--;
3469 }
3470 
init_chain_block_buckets(void)3471 static void init_chain_block_buckets(void)
3472 {
3473 	int i;
3474 
3475 	for (i = 0; i < MAX_CHAIN_BUCKETS; i++)
3476 		chain_block_buckets[i] = -1;
3477 
3478 	add_chain_block(0, ARRAY_SIZE(chain_hlocks));
3479 }
3480 
3481 /*
3482  * Return offset of a chain block of the right size or -1 if not found.
3483  *
3484  * Fairly simple worst-fit allocator with the addition of a number of size
3485  * specific free lists.
3486  */
alloc_chain_hlocks(int req)3487 static int alloc_chain_hlocks(int req)
3488 {
3489 	int bucket, curr, size;
3490 
3491 	/*
3492 	 * We rely on the MSB to act as an escape bit to denote freelist
3493 	 * pointers. Make sure this bit isn't set in 'normal' class_idx usage.
3494 	 */
3495 	BUILD_BUG_ON((MAX_LOCKDEP_KEYS-1) & CHAIN_BLK_FLAG);
3496 
3497 	init_data_structures_once();
3498 
3499 	if (nr_free_chain_hlocks < req)
3500 		return -1;
3501 
3502 	/*
3503 	 * We require a minimum of 2 (u16) entries to encode a freelist
3504 	 * 'pointer'.
3505 	 */
3506 	req = max(req, 2);
3507 	bucket = size_to_bucket(req);
3508 	curr = chain_block_buckets[bucket];
3509 
3510 	if (bucket) {
3511 		if (curr >= 0) {
3512 			del_chain_block(bucket, req, chain_block_next(curr));
3513 			return curr;
3514 		}
3515 		/* Try bucket 0 */
3516 		curr = chain_block_buckets[0];
3517 	}
3518 
3519 	/*
3520 	 * The variable sized freelist is sorted by size; the first entry is
3521 	 * the largest. Use it if it fits.
3522 	 */
3523 	if (curr >= 0) {
3524 		size = chain_block_size(curr);
3525 		if (likely(size >= req)) {
3526 			del_chain_block(0, size, chain_block_next(curr));
3527 			if (size > req)
3528 				add_chain_block(curr + req, size - req);
3529 			return curr;
3530 		}
3531 	}
3532 
3533 	/*
3534 	 * Last resort, split a block in a larger sized bucket.
3535 	 */
3536 	for (size = MAX_CHAIN_BUCKETS; size > req; size--) {
3537 		bucket = size_to_bucket(size);
3538 		curr = chain_block_buckets[bucket];
3539 		if (curr < 0)
3540 			continue;
3541 
3542 		del_chain_block(bucket, size, chain_block_next(curr));
3543 		add_chain_block(curr + req, size - req);
3544 		return curr;
3545 	}
3546 
3547 	return -1;
3548 }
3549 
free_chain_hlocks(int base,int size)3550 static inline void free_chain_hlocks(int base, int size)
3551 {
3552 	add_chain_block(base, max(size, 2));
3553 }
3554 
lock_chain_get_class(struct lock_chain * chain,int i)3555 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
3556 {
3557 	u16 chain_hlock = chain_hlocks[chain->base + i];
3558 	unsigned int class_idx = chain_hlock_class_idx(chain_hlock);
3559 
3560 	return lock_classes + class_idx;
3561 }
3562 
3563 /*
3564  * Returns the index of the first held_lock of the current chain
3565  */
get_first_held_lock(struct task_struct * curr,struct held_lock * hlock)3566 static inline int get_first_held_lock(struct task_struct *curr,
3567 					struct held_lock *hlock)
3568 {
3569 	int i;
3570 	struct held_lock *hlock_curr;
3571 
3572 	for (i = curr->lockdep_depth - 1; i >= 0; i--) {
3573 		hlock_curr = curr->held_locks + i;
3574 		if (hlock_curr->irq_context != hlock->irq_context)
3575 			break;
3576 
3577 	}
3578 
3579 	return ++i;
3580 }
3581 
3582 #ifdef CONFIG_DEBUG_LOCKDEP
3583 /*
3584  * Returns the next chain_key iteration
3585  */
print_chain_key_iteration(u16 hlock_id,u64 chain_key)3586 static u64 print_chain_key_iteration(u16 hlock_id, u64 chain_key)
3587 {
3588 	u64 new_chain_key = iterate_chain_key(chain_key, hlock_id);
3589 
3590 	printk(" hlock_id:%d -> chain_key:%016Lx",
3591 		(unsigned int)hlock_id,
3592 		(unsigned long long)new_chain_key);
3593 	return new_chain_key;
3594 }
3595 
3596 static void
print_chain_keys_held_locks(struct task_struct * curr,struct held_lock * hlock_next)3597 print_chain_keys_held_locks(struct task_struct *curr, struct held_lock *hlock_next)
3598 {
3599 	struct held_lock *hlock;
3600 	u64 chain_key = INITIAL_CHAIN_KEY;
3601 	int depth = curr->lockdep_depth;
3602 	int i = get_first_held_lock(curr, hlock_next);
3603 
3604 	printk("depth: %u (irq_context %u)\n", depth - i + 1,
3605 		hlock_next->irq_context);
3606 	for (; i < depth; i++) {
3607 		hlock = curr->held_locks + i;
3608 		chain_key = print_chain_key_iteration(hlock_id(hlock), chain_key);
3609 
3610 		print_lock(hlock);
3611 	}
3612 
3613 	print_chain_key_iteration(hlock_id(hlock_next), chain_key);
3614 	print_lock(hlock_next);
3615 }
3616 
print_chain_keys_chain(struct lock_chain * chain)3617 static void print_chain_keys_chain(struct lock_chain *chain)
3618 {
3619 	int i;
3620 	u64 chain_key = INITIAL_CHAIN_KEY;
3621 	u16 hlock_id;
3622 
3623 	printk("depth: %u\n", chain->depth);
3624 	for (i = 0; i < chain->depth; i++) {
3625 		hlock_id = chain_hlocks[chain->base + i];
3626 		chain_key = print_chain_key_iteration(hlock_id, chain_key);
3627 
3628 		print_lock_name(NULL, lock_classes + chain_hlock_class_idx(hlock_id));
3629 		printk("\n");
3630 	}
3631 }
3632 
print_collision(struct task_struct * curr,struct held_lock * hlock_next,struct lock_chain * chain)3633 static void print_collision(struct task_struct *curr,
3634 			struct held_lock *hlock_next,
3635 			struct lock_chain *chain)
3636 {
3637 	nbcon_cpu_emergency_enter();
3638 
3639 	pr_warn("\n");
3640 	pr_warn("============================\n");
3641 	pr_warn("WARNING: chain_key collision\n");
3642 	print_kernel_ident();
3643 	pr_warn("----------------------------\n");
3644 	pr_warn("%s/%d: ", current->comm, task_pid_nr(current));
3645 	pr_warn("Hash chain already cached but the contents don't match!\n");
3646 
3647 	pr_warn("Held locks:");
3648 	print_chain_keys_held_locks(curr, hlock_next);
3649 
3650 	pr_warn("Locks in cached chain:");
3651 	print_chain_keys_chain(chain);
3652 
3653 	pr_warn("\nstack backtrace:\n");
3654 	dump_stack();
3655 
3656 	nbcon_cpu_emergency_exit();
3657 }
3658 #endif
3659 
3660 /*
3661  * Checks whether the chain and the current held locks are consistent
3662  * in depth and also in content. If they are not it most likely means
3663  * that there was a collision during the calculation of the chain_key.
3664  * Returns: 0 not passed, 1 passed
3665  */
check_no_collision(struct task_struct * curr,struct held_lock * hlock,struct lock_chain * chain)3666 static int check_no_collision(struct task_struct *curr,
3667 			struct held_lock *hlock,
3668 			struct lock_chain *chain)
3669 {
3670 #ifdef CONFIG_DEBUG_LOCKDEP
3671 	int i, j, id;
3672 
3673 	i = get_first_held_lock(curr, hlock);
3674 
3675 	if (DEBUG_LOCKS_WARN_ON(chain->depth != curr->lockdep_depth - (i - 1))) {
3676 		print_collision(curr, hlock, chain);
3677 		return 0;
3678 	}
3679 
3680 	for (j = 0; j < chain->depth - 1; j++, i++) {
3681 		id = hlock_id(&curr->held_locks[i]);
3682 
3683 		if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id)) {
3684 			print_collision(curr, hlock, chain);
3685 			return 0;
3686 		}
3687 	}
3688 #endif
3689 	return 1;
3690 }
3691 
3692 /*
3693  * Given an index that is >= -1, return the index of the next lock chain.
3694  * Return -2 if there is no next lock chain.
3695  */
lockdep_next_lockchain(long i)3696 long lockdep_next_lockchain(long i)
3697 {
3698 	i = find_next_bit(lock_chains_in_use, ARRAY_SIZE(lock_chains), i + 1);
3699 	return i < ARRAY_SIZE(lock_chains) ? i : -2;
3700 }
3701 
lock_chain_count(void)3702 unsigned long lock_chain_count(void)
3703 {
3704 	return bitmap_weight(lock_chains_in_use, ARRAY_SIZE(lock_chains));
3705 }
3706 
3707 /* Must be called with the graph lock held. */
alloc_lock_chain(void)3708 static struct lock_chain *alloc_lock_chain(void)
3709 {
3710 	int idx = find_first_zero_bit(lock_chains_in_use,
3711 				      ARRAY_SIZE(lock_chains));
3712 
3713 	if (unlikely(idx >= ARRAY_SIZE(lock_chains)))
3714 		return NULL;
3715 	__set_bit(idx, lock_chains_in_use);
3716 	return lock_chains + idx;
3717 }
3718 
3719 /*
3720  * Adds a dependency chain into chain hashtable. And must be called with
3721  * graph_lock held.
3722  *
3723  * Return 0 if fail, and graph_lock is released.
3724  * Return 1 if succeed, with graph_lock held.
3725  */
add_chain_cache(struct task_struct * curr,struct held_lock * hlock,u64 chain_key)3726 static inline int add_chain_cache(struct task_struct *curr,
3727 				  struct held_lock *hlock,
3728 				  u64 chain_key)
3729 {
3730 	struct hlist_head *hash_head = chainhashentry(chain_key);
3731 	struct lock_chain *chain;
3732 	int i, j;
3733 
3734 	/*
3735 	 * The caller must hold the graph lock, ensure we've got IRQs
3736 	 * disabled to make this an IRQ-safe lock.. for recursion reasons
3737 	 * lockdep won't complain about its own locking errors.
3738 	 */
3739 	if (lockdep_assert_locked())
3740 		return 0;
3741 
3742 	chain = alloc_lock_chain();
3743 	if (!chain) {
3744 		if (!debug_locks_off_graph_unlock())
3745 			return 0;
3746 
3747 		nbcon_cpu_emergency_enter();
3748 		print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!");
3749 		dump_stack();
3750 		nbcon_cpu_emergency_exit();
3751 		return 0;
3752 	}
3753 	chain->chain_key = chain_key;
3754 	chain->irq_context = hlock->irq_context;
3755 	i = get_first_held_lock(curr, hlock);
3756 	chain->depth = curr->lockdep_depth + 1 - i;
3757 
3758 	BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks));
3759 	BUILD_BUG_ON((1UL << 6)  <= ARRAY_SIZE(curr->held_locks));
3760 	BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <= ARRAY_SIZE(lock_classes));
3761 
3762 	j = alloc_chain_hlocks(chain->depth);
3763 	if (j < 0) {
3764 		if (!debug_locks_off_graph_unlock())
3765 			return 0;
3766 
3767 		nbcon_cpu_emergency_enter();
3768 		print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
3769 		dump_stack();
3770 		nbcon_cpu_emergency_exit();
3771 		return 0;
3772 	}
3773 
3774 	chain->base = j;
3775 	for (j = 0; j < chain->depth - 1; j++, i++) {
3776 		int lock_id = hlock_id(curr->held_locks + i);
3777 
3778 		chain_hlocks[chain->base + j] = lock_id;
3779 	}
3780 	chain_hlocks[chain->base + j] = hlock_id(hlock);
3781 	hlist_add_head_rcu(&chain->entry, hash_head);
3782 	debug_atomic_inc(chain_lookup_misses);
3783 	inc_chains(chain->irq_context);
3784 
3785 	return 1;
3786 }
3787 
3788 /*
3789  * Look up a dependency chain. Must be called with either the graph lock or
3790  * the RCU read lock held.
3791  */
lookup_chain_cache(u64 chain_key)3792 static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
3793 {
3794 	struct hlist_head *hash_head = chainhashentry(chain_key);
3795 	struct lock_chain *chain;
3796 
3797 	hlist_for_each_entry_rcu(chain, hash_head, entry) {
3798 		if (READ_ONCE(chain->chain_key) == chain_key) {
3799 			debug_atomic_inc(chain_lookup_hits);
3800 			return chain;
3801 		}
3802 	}
3803 	return NULL;
3804 }
3805 
3806 /*
3807  * If the key is not present yet in dependency chain cache then
3808  * add it and return 1 - in this case the new dependency chain is
3809  * validated. If the key is already hashed, return 0.
3810  * (On return with 1 graph_lock is held.)
3811  */
lookup_chain_cache_add(struct task_struct * curr,struct held_lock * hlock,u64 chain_key)3812 static inline int lookup_chain_cache_add(struct task_struct *curr,
3813 					 struct held_lock *hlock,
3814 					 u64 chain_key)
3815 {
3816 	struct lock_class *class = hlock_class(hlock);
3817 	struct lock_chain *chain = lookup_chain_cache(chain_key);
3818 
3819 	if (chain) {
3820 cache_hit:
3821 		if (!check_no_collision(curr, hlock, chain))
3822 			return 0;
3823 
3824 		if (very_verbose(class)) {
3825 			printk("\nhash chain already cached, key: "
3826 					"%016Lx tail class: [%px] %s\n",
3827 					(unsigned long long)chain_key,
3828 					class->key, class->name);
3829 		}
3830 
3831 		return 0;
3832 	}
3833 
3834 	if (very_verbose(class)) {
3835 		printk("\nnew hash chain, key: %016Lx tail class: [%px] %s\n",
3836 			(unsigned long long)chain_key, class->key, class->name);
3837 	}
3838 
3839 	if (!graph_lock())
3840 		return 0;
3841 
3842 	/*
3843 	 * We have to walk the chain again locked - to avoid duplicates:
3844 	 */
3845 	chain = lookup_chain_cache(chain_key);
3846 	if (chain) {
3847 		graph_unlock();
3848 		goto cache_hit;
3849 	}
3850 
3851 	if (!add_chain_cache(curr, hlock, chain_key))
3852 		return 0;
3853 
3854 	return 1;
3855 }
3856 
validate_chain(struct task_struct * curr,struct held_lock * hlock,int chain_head,u64 chain_key)3857 static int validate_chain(struct task_struct *curr,
3858 			  struct held_lock *hlock,
3859 			  int chain_head, u64 chain_key)
3860 {
3861 	/*
3862 	 * Trylock needs to maintain the stack of held locks, but it
3863 	 * does not add new dependencies, because trylock can be done
3864 	 * in any order.
3865 	 *
3866 	 * We look up the chain_key and do the O(N^2) check and update of
3867 	 * the dependencies only if this is a new dependency chain.
3868 	 * (If lookup_chain_cache_add() return with 1 it acquires
3869 	 * graph_lock for us)
3870 	 */
3871 	if (!hlock->trylock && hlock->check &&
3872 	    lookup_chain_cache_add(curr, hlock, chain_key)) {
3873 		/*
3874 		 * Check whether last held lock:
3875 		 *
3876 		 * - is irq-safe, if this lock is irq-unsafe
3877 		 * - is softirq-safe, if this lock is hardirq-unsafe
3878 		 *
3879 		 * And check whether the new lock's dependency graph
3880 		 * could lead back to the previous lock:
3881 		 *
3882 		 * - within the current held-lock stack
3883 		 * - across our accumulated lock dependency records
3884 		 *
3885 		 * any of these scenarios could lead to a deadlock.
3886 		 */
3887 		/*
3888 		 * The simple case: does the current hold the same lock
3889 		 * already?
3890 		 */
3891 		int ret = check_deadlock(curr, hlock);
3892 
3893 		if (!ret)
3894 			return 0;
3895 		/*
3896 		 * Add dependency only if this lock is not the head
3897 		 * of the chain, and if the new lock introduces no more
3898 		 * lock dependency (because we already hold a lock with the
3899 		 * same lock class) nor deadlock (because the nest_lock
3900 		 * serializes nesting locks), see the comments for
3901 		 * check_deadlock().
3902 		 */
3903 		if (!chain_head && ret != 2) {
3904 			if (!check_prevs_add(curr, hlock))
3905 				return 0;
3906 		}
3907 
3908 		graph_unlock();
3909 	} else {
3910 		/* after lookup_chain_cache_add(): */
3911 		if (unlikely(!debug_locks))
3912 			return 0;
3913 	}
3914 
3915 	return 1;
3916 }
3917 #else
validate_chain(struct task_struct * curr,struct held_lock * hlock,int chain_head,u64 chain_key)3918 static inline int validate_chain(struct task_struct *curr,
3919 				 struct held_lock *hlock,
3920 				 int chain_head, u64 chain_key)
3921 {
3922 	return 1;
3923 }
3924 
init_chain_block_buckets(void)3925 static void init_chain_block_buckets(void)	{ }
3926 #endif /* CONFIG_PROVE_LOCKING */
3927 
3928 /*
3929  * We are building curr_chain_key incrementally, so double-check
3930  * it from scratch, to make sure that it's done correctly:
3931  */
check_chain_key(struct task_struct * curr)3932 static void check_chain_key(struct task_struct *curr)
3933 {
3934 #ifdef CONFIG_DEBUG_LOCKDEP
3935 	struct held_lock *hlock, *prev_hlock = NULL;
3936 	unsigned int i;
3937 	u64 chain_key = INITIAL_CHAIN_KEY;
3938 
3939 	for (i = 0; i < curr->lockdep_depth; i++) {
3940 		hlock = curr->held_locks + i;
3941 		if (chain_key != hlock->prev_chain_key) {
3942 			debug_locks_off();
3943 			/*
3944 			 * We got mighty confused, our chain keys don't match
3945 			 * with what we expect, someone trample on our task state?
3946 			 */
3947 			WARN(1, "hm#1, depth: %u [%u], %016Lx != %016Lx\n",
3948 				curr->lockdep_depth, i,
3949 				(unsigned long long)chain_key,
3950 				(unsigned long long)hlock->prev_chain_key);
3951 			return;
3952 		}
3953 
3954 		/*
3955 		 * hlock->class_idx can't go beyond MAX_LOCKDEP_KEYS, but is
3956 		 * it registered lock class index?
3957 		 */
3958 		if (DEBUG_LOCKS_WARN_ON(!test_bit(hlock->class_idx, lock_classes_in_use)))
3959 			return;
3960 
3961 		if (prev_hlock && (prev_hlock->irq_context !=
3962 							hlock->irq_context))
3963 			chain_key = INITIAL_CHAIN_KEY;
3964 		chain_key = iterate_chain_key(chain_key, hlock_id(hlock));
3965 		prev_hlock = hlock;
3966 	}
3967 	if (chain_key != curr->curr_chain_key) {
3968 		debug_locks_off();
3969 		/*
3970 		 * More smoking hash instead of calculating it, damn see these
3971 		 * numbers float.. I bet that a pink elephant stepped on my memory.
3972 		 */
3973 		WARN(1, "hm#2, depth: %u [%u], %016Lx != %016Lx\n",
3974 			curr->lockdep_depth, i,
3975 			(unsigned long long)chain_key,
3976 			(unsigned long long)curr->curr_chain_key);
3977 	}
3978 #endif
3979 }
3980 
3981 #ifdef CONFIG_PROVE_LOCKING
3982 static int mark_lock(struct task_struct *curr, struct held_lock *this,
3983 		     enum lock_usage_bit new_bit);
3984 
print_usage_bug_scenario(struct held_lock * lock)3985 static void print_usage_bug_scenario(struct held_lock *lock)
3986 {
3987 	struct lock_class *class = hlock_class(lock);
3988 
3989 	printk(" Possible unsafe locking scenario:\n\n");
3990 	printk("       CPU0\n");
3991 	printk("       ----\n");
3992 	printk("  lock(");
3993 	__print_lock_name(lock, class);
3994 	printk(KERN_CONT ");\n");
3995 	printk("  <Interrupt>\n");
3996 	printk("    lock(");
3997 	__print_lock_name(lock, class);
3998 	printk(KERN_CONT ");\n");
3999 	printk("\n *** DEADLOCK ***\n\n");
4000 }
4001 
4002 static void
print_usage_bug(struct task_struct * curr,struct held_lock * this,enum lock_usage_bit prev_bit,enum lock_usage_bit new_bit)4003 print_usage_bug(struct task_struct *curr, struct held_lock *this,
4004 		enum lock_usage_bit prev_bit, enum lock_usage_bit new_bit)
4005 {
4006 	if (!debug_locks_off() || debug_locks_silent)
4007 		return;
4008 
4009 	nbcon_cpu_emergency_enter();
4010 
4011 	pr_warn("\n");
4012 	pr_warn("================================\n");
4013 	pr_warn("WARNING: inconsistent lock state\n");
4014 	print_kernel_ident();
4015 	pr_warn("--------------------------------\n");
4016 
4017 	pr_warn("inconsistent {%s} -> {%s} usage.\n",
4018 		usage_str[prev_bit], usage_str[new_bit]);
4019 
4020 	pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] takes:\n",
4021 		curr->comm, task_pid_nr(curr),
4022 		lockdep_hardirq_context(), hardirq_count() >> HARDIRQ_SHIFT,
4023 		lockdep_softirq_context(curr), softirq_count() >> SOFTIRQ_SHIFT,
4024 		lockdep_hardirqs_enabled(),
4025 		lockdep_softirqs_enabled(curr));
4026 	print_lock(this);
4027 
4028 	pr_warn("{%s} state was registered at:\n", usage_str[prev_bit]);
4029 	print_lock_trace(hlock_class(this)->usage_traces[prev_bit], 1);
4030 
4031 	print_irqtrace_events(curr);
4032 	pr_warn("\nother info that might help us debug this:\n");
4033 	print_usage_bug_scenario(this);
4034 
4035 	lockdep_print_held_locks(curr);
4036 
4037 	pr_warn("\nstack backtrace:\n");
4038 	dump_stack();
4039 
4040 	nbcon_cpu_emergency_exit();
4041 }
4042 
4043 /*
4044  * Print out an error if an invalid bit is set:
4045  */
4046 static inline int
valid_state(struct task_struct * curr,struct held_lock * this,enum lock_usage_bit new_bit,enum lock_usage_bit bad_bit)4047 valid_state(struct task_struct *curr, struct held_lock *this,
4048 	    enum lock_usage_bit new_bit, enum lock_usage_bit bad_bit)
4049 {
4050 	if (unlikely(hlock_class(this)->usage_mask & (1 << bad_bit))) {
4051 		graph_unlock();
4052 		print_usage_bug(curr, this, bad_bit, new_bit);
4053 		return 0;
4054 	}
4055 	return 1;
4056 }
4057 
4058 
4059 /*
4060  * print irq inversion bug:
4061  */
4062 static void
print_irq_inversion_bug(struct task_struct * curr,struct lock_list * root,struct lock_list * other,struct held_lock * this,int forwards,const char * irqclass)4063 print_irq_inversion_bug(struct task_struct *curr,
4064 			struct lock_list *root, struct lock_list *other,
4065 			struct held_lock *this, int forwards,
4066 			const char *irqclass)
4067 {
4068 	struct lock_list *entry = other;
4069 	struct lock_list *middle = NULL;
4070 	int depth;
4071 
4072 	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
4073 		return;
4074 
4075 	nbcon_cpu_emergency_enter();
4076 
4077 	pr_warn("\n");
4078 	pr_warn("========================================================\n");
4079 	pr_warn("WARNING: possible irq lock inversion dependency detected\n");
4080 	print_kernel_ident();
4081 	pr_warn("--------------------------------------------------------\n");
4082 	pr_warn("%s/%d just changed the state of lock:\n",
4083 		curr->comm, task_pid_nr(curr));
4084 	print_lock(this);
4085 	if (forwards)
4086 		pr_warn("but this lock took another, %s-unsafe lock in the past:\n", irqclass);
4087 	else
4088 		pr_warn("but this lock was taken by another, %s-safe lock in the past:\n", irqclass);
4089 	print_lock_name(NULL, other->class);
4090 	pr_warn("\n\nand interrupts could create inverse lock ordering between them.\n\n");
4091 
4092 	pr_warn("\nother info that might help us debug this:\n");
4093 
4094 	/* Find a middle lock (if one exists) */
4095 	depth = get_lock_depth(other);
4096 	do {
4097 		if (depth == 0 && (entry != root)) {
4098 			pr_warn("lockdep:%s bad path found in chain graph\n", __func__);
4099 			break;
4100 		}
4101 		middle = entry;
4102 		entry = get_lock_parent(entry);
4103 		depth--;
4104 	} while (entry && entry != root && (depth >= 0));
4105 	if (forwards)
4106 		print_irq_lock_scenario(root, other,
4107 			middle ? middle->class : root->class, other->class);
4108 	else
4109 		print_irq_lock_scenario(other, root,
4110 			middle ? middle->class : other->class, root->class);
4111 
4112 	lockdep_print_held_locks(curr);
4113 
4114 	pr_warn("\nthe shortest dependencies between 2nd lock and 1st lock:\n");
4115 	root->trace = save_trace();
4116 	if (!root->trace)
4117 		goto out;
4118 	print_shortest_lock_dependencies(other, root);
4119 
4120 	pr_warn("\nstack backtrace:\n");
4121 	dump_stack();
4122 out:
4123 	nbcon_cpu_emergency_exit();
4124 }
4125 
4126 /*
4127  * Prove that in the forwards-direction subgraph starting at <this>
4128  * there is no lock matching <mask>:
4129  */
4130 static int
check_usage_forwards(struct task_struct * curr,struct held_lock * this,enum lock_usage_bit bit)4131 check_usage_forwards(struct task_struct *curr, struct held_lock *this,
4132 		     enum lock_usage_bit bit)
4133 {
4134 	enum bfs_result ret;
4135 	struct lock_list root;
4136 	struct lock_list *target_entry;
4137 	enum lock_usage_bit read_bit = bit + LOCK_USAGE_READ_MASK;
4138 	unsigned usage_mask = lock_flag(bit) | lock_flag(read_bit);
4139 
4140 	bfs_init_root(&root, this);
4141 	ret = find_usage_forwards(&root, usage_mask, &target_entry);
4142 	if (bfs_error(ret)) {
4143 		print_bfs_bug(ret);
4144 		return 0;
4145 	}
4146 	if (ret == BFS_RNOMATCH)
4147 		return 1;
4148 
4149 	/* Check whether write or read usage is the match */
4150 	if (target_entry->class->usage_mask & lock_flag(bit)) {
4151 		print_irq_inversion_bug(curr, &root, target_entry,
4152 					this, 1, state_name(bit));
4153 	} else {
4154 		print_irq_inversion_bug(curr, &root, target_entry,
4155 					this, 1, state_name(read_bit));
4156 	}
4157 
4158 	return 0;
4159 }
4160 
4161 /*
4162  * Prove that in the backwards-direction subgraph starting at <this>
4163  * there is no lock matching <mask>:
4164  */
4165 static int
check_usage_backwards(struct task_struct * curr,struct held_lock * this,enum lock_usage_bit bit)4166 check_usage_backwards(struct task_struct *curr, struct held_lock *this,
4167 		      enum lock_usage_bit bit)
4168 {
4169 	enum bfs_result ret;
4170 	struct lock_list root;
4171 	struct lock_list *target_entry;
4172 	enum lock_usage_bit read_bit = bit + LOCK_USAGE_READ_MASK;
4173 	unsigned usage_mask = lock_flag(bit) | lock_flag(read_bit);
4174 
4175 	bfs_init_rootb(&root, this);
4176 	ret = find_usage_backwards(&root, usage_mask, &target_entry);
4177 	if (bfs_error(ret)) {
4178 		print_bfs_bug(ret);
4179 		return 0;
4180 	}
4181 	if (ret == BFS_RNOMATCH)
4182 		return 1;
4183 
4184 	/* Check whether write or read usage is the match */
4185 	if (target_entry->class->usage_mask & lock_flag(bit)) {
4186 		print_irq_inversion_bug(curr, &root, target_entry,
4187 					this, 0, state_name(bit));
4188 	} else {
4189 		print_irq_inversion_bug(curr, &root, target_entry,
4190 					this, 0, state_name(read_bit));
4191 	}
4192 
4193 	return 0;
4194 }
4195 
print_irqtrace_events(struct task_struct * curr)4196 void print_irqtrace_events(struct task_struct *curr)
4197 {
4198 	const struct irqtrace_events *trace = &curr->irqtrace;
4199 
4200 	nbcon_cpu_emergency_enter();
4201 
4202 	printk("irq event stamp: %u\n", trace->irq_events);
4203 	printk("hardirqs last  enabled at (%u): [<%px>] %pS\n",
4204 		trace->hardirq_enable_event, (void *)trace->hardirq_enable_ip,
4205 		(void *)trace->hardirq_enable_ip);
4206 	printk("hardirqs last disabled at (%u): [<%px>] %pS\n",
4207 		trace->hardirq_disable_event, (void *)trace->hardirq_disable_ip,
4208 		(void *)trace->hardirq_disable_ip);
4209 	printk("softirqs last  enabled at (%u): [<%px>] %pS\n",
4210 		trace->softirq_enable_event, (void *)trace->softirq_enable_ip,
4211 		(void *)trace->softirq_enable_ip);
4212 	printk("softirqs last disabled at (%u): [<%px>] %pS\n",
4213 		trace->softirq_disable_event, (void *)trace->softirq_disable_ip,
4214 		(void *)trace->softirq_disable_ip);
4215 
4216 	nbcon_cpu_emergency_exit();
4217 }
4218 
HARDIRQ_verbose(struct lock_class * class)4219 static int HARDIRQ_verbose(struct lock_class *class)
4220 {
4221 #if HARDIRQ_VERBOSE
4222 	return class_filter(class);
4223 #endif
4224 	return 0;
4225 }
4226 
SOFTIRQ_verbose(struct lock_class * class)4227 static int SOFTIRQ_verbose(struct lock_class *class)
4228 {
4229 #if SOFTIRQ_VERBOSE
4230 	return class_filter(class);
4231 #endif
4232 	return 0;
4233 }
4234 
4235 static int (*state_verbose_f[])(struct lock_class *class) = {
4236 #define LOCKDEP_STATE(__STATE) \
4237 	__STATE##_verbose,
4238 #include "lockdep_states.h"
4239 #undef LOCKDEP_STATE
4240 };
4241 
state_verbose(enum lock_usage_bit bit,struct lock_class * class)4242 static inline int state_verbose(enum lock_usage_bit bit,
4243 				struct lock_class *class)
4244 {
4245 	return state_verbose_f[bit >> LOCK_USAGE_DIR_MASK](class);
4246 }
4247 
4248 typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
4249 			     enum lock_usage_bit bit, const char *name);
4250 
4251 static int
mark_lock_irq(struct task_struct * curr,struct held_lock * this,enum lock_usage_bit new_bit)4252 mark_lock_irq(struct task_struct *curr, struct held_lock *this,
4253 		enum lock_usage_bit new_bit)
4254 {
4255 	int excl_bit = exclusive_bit(new_bit);
4256 	int read = new_bit & LOCK_USAGE_READ_MASK;
4257 	int dir = new_bit & LOCK_USAGE_DIR_MASK;
4258 
4259 	/*
4260 	 * Validate that this particular lock does not have conflicting
4261 	 * usage states.
4262 	 */
4263 	if (!valid_state(curr, this, new_bit, excl_bit))
4264 		return 0;
4265 
4266 	/*
4267 	 * Check for read in write conflicts
4268 	 */
4269 	if (!read && !valid_state(curr, this, new_bit,
4270 				  excl_bit + LOCK_USAGE_READ_MASK))
4271 		return 0;
4272 
4273 
4274 	/*
4275 	 * Validate that the lock dependencies don't have conflicting usage
4276 	 * states.
4277 	 */
4278 	if (dir) {
4279 		/*
4280 		 * mark ENABLED has to look backwards -- to ensure no dependee
4281 		 * has USED_IN state, which, again, would allow  recursion deadlocks.
4282 		 */
4283 		if (!check_usage_backwards(curr, this, excl_bit))
4284 			return 0;
4285 	} else {
4286 		/*
4287 		 * mark USED_IN has to look forwards -- to ensure no dependency
4288 		 * has ENABLED state, which would allow recursion deadlocks.
4289 		 */
4290 		if (!check_usage_forwards(curr, this, excl_bit))
4291 			return 0;
4292 	}
4293 
4294 	if (state_verbose(new_bit, hlock_class(this)))
4295 		return 2;
4296 
4297 	return 1;
4298 }
4299 
4300 /*
4301  * Mark all held locks with a usage bit:
4302  */
4303 static int
mark_held_locks(struct task_struct * curr,enum lock_usage_bit base_bit)4304 mark_held_locks(struct task_struct *curr, enum lock_usage_bit base_bit)
4305 {
4306 	struct held_lock *hlock;
4307 	int i;
4308 
4309 	for (i = 0; i < curr->lockdep_depth; i++) {
4310 		enum lock_usage_bit hlock_bit = base_bit;
4311 		hlock = curr->held_locks + i;
4312 
4313 		if (hlock->read)
4314 			hlock_bit += LOCK_USAGE_READ_MASK;
4315 
4316 		BUG_ON(hlock_bit >= LOCK_USAGE_STATES);
4317 
4318 		if (!hlock->check)
4319 			continue;
4320 
4321 		if (!mark_lock(curr, hlock, hlock_bit))
4322 			return 0;
4323 	}
4324 
4325 	return 1;
4326 }
4327 
4328 /*
4329  * Hardirqs will be enabled:
4330  */
__trace_hardirqs_on_caller(void)4331 static void __trace_hardirqs_on_caller(void)
4332 {
4333 	struct task_struct *curr = current;
4334 
4335 	/*
4336 	 * We are going to turn hardirqs on, so set the
4337 	 * usage bit for all held locks:
4338 	 */
4339 	if (!mark_held_locks(curr, LOCK_ENABLED_HARDIRQ))
4340 		return;
4341 	/*
4342 	 * If we have softirqs enabled, then set the usage
4343 	 * bit for all held locks. (disabled hardirqs prevented
4344 	 * this bit from being set before)
4345 	 */
4346 	if (curr->softirqs_enabled)
4347 		mark_held_locks(curr, LOCK_ENABLED_SOFTIRQ);
4348 }
4349 
4350 /**
4351  * lockdep_hardirqs_on_prepare - Prepare for enabling interrupts
4352  *
4353  * Invoked before a possible transition to RCU idle from exit to user or
4354  * guest mode. This ensures that all RCU operations are done before RCU
4355  * stops watching. After the RCU transition lockdep_hardirqs_on() has to be
4356  * invoked to set the final state.
4357  */
lockdep_hardirqs_on_prepare(void)4358 void lockdep_hardirqs_on_prepare(void)
4359 {
4360 	if (unlikely(!debug_locks))
4361 		return;
4362 
4363 	/*
4364 	 * NMIs do not (and cannot) track lock dependencies, nothing to do.
4365 	 */
4366 	if (unlikely(in_nmi()))
4367 		return;
4368 
4369 	if (unlikely(this_cpu_read(lockdep_recursion)))
4370 		return;
4371 
4372 	if (unlikely(lockdep_hardirqs_enabled())) {
4373 		/*
4374 		 * Neither irq nor preemption are disabled here
4375 		 * so this is racy by nature but losing one hit
4376 		 * in a stat is not a big deal.
4377 		 */
4378 		__debug_atomic_inc(redundant_hardirqs_on);
4379 		return;
4380 	}
4381 
4382 	/*
4383 	 * We're enabling irqs and according to our state above irqs weren't
4384 	 * already enabled, yet we find the hardware thinks they are in fact
4385 	 * enabled.. someone messed up their IRQ state tracing.
4386 	 */
4387 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
4388 		return;
4389 
4390 	/*
4391 	 * See the fine text that goes along with this variable definition.
4392 	 */
4393 	if (DEBUG_LOCKS_WARN_ON(early_boot_irqs_disabled))
4394 		return;
4395 
4396 	/*
4397 	 * Can't allow enabling interrupts while in an interrupt handler,
4398 	 * that's general bad form and such. Recursion, limited stack etc..
4399 	 */
4400 	if (DEBUG_LOCKS_WARN_ON(lockdep_hardirq_context()))
4401 		return;
4402 
4403 	current->hardirq_chain_key = current->curr_chain_key;
4404 
4405 	lockdep_recursion_inc();
4406 	__trace_hardirqs_on_caller();
4407 	lockdep_recursion_finish();
4408 }
4409 EXPORT_SYMBOL_GPL(lockdep_hardirqs_on_prepare);
4410 
lockdep_hardirqs_on(unsigned long ip)4411 void noinstr lockdep_hardirqs_on(unsigned long ip)
4412 {
4413 	struct irqtrace_events *trace = &current->irqtrace;
4414 
4415 	if (unlikely(!debug_locks))
4416 		return;
4417 
4418 	/*
4419 	 * NMIs can happen in the middle of local_irq_{en,dis}able() where the
4420 	 * tracking state and hardware state are out of sync.
4421 	 *
4422 	 * NMIs must save lockdep_hardirqs_enabled() to restore IRQ state from,
4423 	 * and not rely on hardware state like normal interrupts.
4424 	 */
4425 	if (unlikely(in_nmi())) {
4426 		if (!IS_ENABLED(CONFIG_TRACE_IRQFLAGS_NMI))
4427 			return;
4428 
4429 		/*
4430 		 * Skip:
4431 		 *  - recursion check, because NMI can hit lockdep;
4432 		 *  - hardware state check, because above;
4433 		 *  - chain_key check, see lockdep_hardirqs_on_prepare().
4434 		 */
4435 		goto skip_checks;
4436 	}
4437 
4438 	if (unlikely(this_cpu_read(lockdep_recursion)))
4439 		return;
4440 
4441 	if (lockdep_hardirqs_enabled()) {
4442 		/*
4443 		 * Neither irq nor preemption are disabled here
4444 		 * so this is racy by nature but losing one hit
4445 		 * in a stat is not a big deal.
4446 		 */
4447 		__debug_atomic_inc(redundant_hardirqs_on);
4448 		return;
4449 	}
4450 
4451 	/*
4452 	 * We're enabling irqs and according to our state above irqs weren't
4453 	 * already enabled, yet we find the hardware thinks they are in fact
4454 	 * enabled.. someone messed up their IRQ state tracing.
4455 	 */
4456 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
4457 		return;
4458 
4459 	/*
4460 	 * Ensure the lock stack remained unchanged between
4461 	 * lockdep_hardirqs_on_prepare() and lockdep_hardirqs_on().
4462 	 */
4463 	DEBUG_LOCKS_WARN_ON(current->hardirq_chain_key !=
4464 			    current->curr_chain_key);
4465 
4466 skip_checks:
4467 	/* we'll do an OFF -> ON transition: */
4468 	__this_cpu_write(hardirqs_enabled, 1);
4469 	trace->hardirq_enable_ip = ip;
4470 	trace->hardirq_enable_event = ++trace->irq_events;
4471 	debug_atomic_inc(hardirqs_on_events);
4472 }
4473 EXPORT_SYMBOL_GPL(lockdep_hardirqs_on);
4474 
4475 /*
4476  * Hardirqs were disabled:
4477  */
lockdep_hardirqs_off(unsigned long ip)4478 void noinstr lockdep_hardirqs_off(unsigned long ip)
4479 {
4480 	if (unlikely(!debug_locks))
4481 		return;
4482 
4483 	/*
4484 	 * Matching lockdep_hardirqs_on(), allow NMIs in the middle of lockdep;
4485 	 * they will restore the software state. This ensures the software
4486 	 * state is consistent inside NMIs as well.
4487 	 */
4488 	if (in_nmi()) {
4489 		if (!IS_ENABLED(CONFIG_TRACE_IRQFLAGS_NMI))
4490 			return;
4491 	} else if (__this_cpu_read(lockdep_recursion))
4492 		return;
4493 
4494 	/*
4495 	 * So we're supposed to get called after you mask local IRQs, but for
4496 	 * some reason the hardware doesn't quite think you did a proper job.
4497 	 */
4498 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
4499 		return;
4500 
4501 	if (lockdep_hardirqs_enabled()) {
4502 		struct irqtrace_events *trace = &current->irqtrace;
4503 
4504 		/*
4505 		 * We have done an ON -> OFF transition:
4506 		 */
4507 		__this_cpu_write(hardirqs_enabled, 0);
4508 		trace->hardirq_disable_ip = ip;
4509 		trace->hardirq_disable_event = ++trace->irq_events;
4510 		debug_atomic_inc(hardirqs_off_events);
4511 	} else {
4512 		debug_atomic_inc(redundant_hardirqs_off);
4513 	}
4514 }
4515 EXPORT_SYMBOL_GPL(lockdep_hardirqs_off);
4516 
4517 /*
4518  * Softirqs will be enabled:
4519  */
lockdep_softirqs_on(unsigned long ip)4520 void lockdep_softirqs_on(unsigned long ip)
4521 {
4522 	struct irqtrace_events *trace = &current->irqtrace;
4523 
4524 	if (unlikely(!lockdep_enabled()))
4525 		return;
4526 
4527 	/*
4528 	 * We fancy IRQs being disabled here, see softirq.c, avoids
4529 	 * funny state and nesting things.
4530 	 */
4531 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
4532 		return;
4533 
4534 	if (current->softirqs_enabled) {
4535 		debug_atomic_inc(redundant_softirqs_on);
4536 		return;
4537 	}
4538 
4539 	lockdep_recursion_inc();
4540 	/*
4541 	 * We'll do an OFF -> ON transition:
4542 	 */
4543 	current->softirqs_enabled = 1;
4544 	trace->softirq_enable_ip = ip;
4545 	trace->softirq_enable_event = ++trace->irq_events;
4546 	debug_atomic_inc(softirqs_on_events);
4547 	/*
4548 	 * We are going to turn softirqs on, so set the
4549 	 * usage bit for all held locks, if hardirqs are
4550 	 * enabled too:
4551 	 */
4552 	if (lockdep_hardirqs_enabled())
4553 		mark_held_locks(current, LOCK_ENABLED_SOFTIRQ);
4554 	lockdep_recursion_finish();
4555 }
4556 
4557 /*
4558  * Softirqs were disabled:
4559  */
lockdep_softirqs_off(unsigned long ip)4560 void lockdep_softirqs_off(unsigned long ip)
4561 {
4562 	if (unlikely(!lockdep_enabled()))
4563 		return;
4564 
4565 	/*
4566 	 * We fancy IRQs being disabled here, see softirq.c
4567 	 */
4568 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
4569 		return;
4570 
4571 	if (current->softirqs_enabled) {
4572 		struct irqtrace_events *trace = &current->irqtrace;
4573 
4574 		/*
4575 		 * We have done an ON -> OFF transition:
4576 		 */
4577 		current->softirqs_enabled = 0;
4578 		trace->softirq_disable_ip = ip;
4579 		trace->softirq_disable_event = ++trace->irq_events;
4580 		debug_atomic_inc(softirqs_off_events);
4581 		/*
4582 		 * Whoops, we wanted softirqs off, so why aren't they?
4583 		 */
4584 		DEBUG_LOCKS_WARN_ON(!softirq_count());
4585 	} else
4586 		debug_atomic_inc(redundant_softirqs_off);
4587 }
4588 
4589 static int
mark_usage(struct task_struct * curr,struct held_lock * hlock,int check)4590 mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
4591 {
4592 	if (!check)
4593 		goto lock_used;
4594 
4595 	/*
4596 	 * If non-trylock use in a hardirq or softirq context, then
4597 	 * mark the lock as used in these contexts:
4598 	 */
4599 	if (!hlock->trylock) {
4600 		if (hlock->read) {
4601 			if (lockdep_hardirq_context())
4602 				if (!mark_lock(curr, hlock,
4603 						LOCK_USED_IN_HARDIRQ_READ))
4604 					return 0;
4605 			if (curr->softirq_context)
4606 				if (!mark_lock(curr, hlock,
4607 						LOCK_USED_IN_SOFTIRQ_READ))
4608 					return 0;
4609 		} else {
4610 			if (lockdep_hardirq_context())
4611 				if (!mark_lock(curr, hlock, LOCK_USED_IN_HARDIRQ))
4612 					return 0;
4613 			if (curr->softirq_context)
4614 				if (!mark_lock(curr, hlock, LOCK_USED_IN_SOFTIRQ))
4615 					return 0;
4616 		}
4617 	}
4618 
4619 	/*
4620 	 * For lock_sync(), don't mark the ENABLED usage, since lock_sync()
4621 	 * creates no critical section and no extra dependency can be introduced
4622 	 * by interrupts
4623 	 */
4624 	if (!hlock->hardirqs_off && !hlock->sync) {
4625 		if (hlock->read) {
4626 			if (!mark_lock(curr, hlock,
4627 					LOCK_ENABLED_HARDIRQ_READ))
4628 				return 0;
4629 			if (curr->softirqs_enabled)
4630 				if (!mark_lock(curr, hlock,
4631 						LOCK_ENABLED_SOFTIRQ_READ))
4632 					return 0;
4633 		} else {
4634 			if (!mark_lock(curr, hlock,
4635 					LOCK_ENABLED_HARDIRQ))
4636 				return 0;
4637 			if (curr->softirqs_enabled)
4638 				if (!mark_lock(curr, hlock,
4639 						LOCK_ENABLED_SOFTIRQ))
4640 					return 0;
4641 		}
4642 	}
4643 
4644 lock_used:
4645 	/* mark it as used: */
4646 	if (!mark_lock(curr, hlock, LOCK_USED))
4647 		return 0;
4648 
4649 	return 1;
4650 }
4651 
task_irq_context(struct task_struct * task)4652 static inline unsigned int task_irq_context(struct task_struct *task)
4653 {
4654 	return LOCK_CHAIN_HARDIRQ_CONTEXT * !!lockdep_hardirq_context() +
4655 	       LOCK_CHAIN_SOFTIRQ_CONTEXT * !!task->softirq_context;
4656 }
4657 
separate_irq_context(struct task_struct * curr,struct held_lock * hlock)4658 static int separate_irq_context(struct task_struct *curr,
4659 		struct held_lock *hlock)
4660 {
4661 	unsigned int depth = curr->lockdep_depth;
4662 
4663 	/*
4664 	 * Keep track of points where we cross into an interrupt context:
4665 	 */
4666 	if (depth) {
4667 		struct held_lock *prev_hlock;
4668 
4669 		prev_hlock = curr->held_locks + depth-1;
4670 		/*
4671 		 * If we cross into another context, reset the
4672 		 * hash key (this also prevents the checking and the
4673 		 * adding of the dependency to 'prev'):
4674 		 */
4675 		if (prev_hlock->irq_context != hlock->irq_context)
4676 			return 1;
4677 	}
4678 	return 0;
4679 }
4680 
4681 /*
4682  * Mark a lock with a usage bit, and validate the state transition:
4683  */
mark_lock(struct task_struct * curr,struct held_lock * this,enum lock_usage_bit new_bit)4684 static int mark_lock(struct task_struct *curr, struct held_lock *this,
4685 			     enum lock_usage_bit new_bit)
4686 {
4687 	unsigned int new_mask, ret = 1;
4688 
4689 	if (new_bit >= LOCK_USAGE_STATES) {
4690 		DEBUG_LOCKS_WARN_ON(1);
4691 		return 0;
4692 	}
4693 
4694 	if (new_bit == LOCK_USED && this->read)
4695 		new_bit = LOCK_USED_READ;
4696 
4697 	new_mask = 1 << new_bit;
4698 
4699 	/*
4700 	 * If already set then do not dirty the cacheline,
4701 	 * nor do any checks:
4702 	 */
4703 	if (likely(hlock_class(this)->usage_mask & new_mask))
4704 		return 1;
4705 
4706 	if (!graph_lock())
4707 		return 0;
4708 	/*
4709 	 * Make sure we didn't race:
4710 	 */
4711 	if (unlikely(hlock_class(this)->usage_mask & new_mask))
4712 		goto unlock;
4713 
4714 	if (!hlock_class(this)->usage_mask)
4715 		debug_atomic_dec(nr_unused_locks);
4716 
4717 	hlock_class(this)->usage_mask |= new_mask;
4718 
4719 	if (new_bit < LOCK_TRACE_STATES) {
4720 		if (!(hlock_class(this)->usage_traces[new_bit] = save_trace()))
4721 			return 0;
4722 	}
4723 
4724 	if (new_bit < LOCK_USED) {
4725 		ret = mark_lock_irq(curr, this, new_bit);
4726 		if (!ret)
4727 			return 0;
4728 	}
4729 
4730 unlock:
4731 	graph_unlock();
4732 
4733 	/*
4734 	 * We must printk outside of the graph_lock:
4735 	 */
4736 	if (ret == 2) {
4737 		nbcon_cpu_emergency_enter();
4738 		printk("\nmarked lock as {%s}:\n", usage_str[new_bit]);
4739 		print_lock(this);
4740 		print_irqtrace_events(curr);
4741 		dump_stack();
4742 		nbcon_cpu_emergency_exit();
4743 	}
4744 
4745 	return ret;
4746 }
4747 
task_wait_context(struct task_struct * curr)4748 static inline short task_wait_context(struct task_struct *curr)
4749 {
4750 	/*
4751 	 * Set appropriate wait type for the context; for IRQs we have to take
4752 	 * into account force_irqthread as that is implied by PREEMPT_RT.
4753 	 */
4754 	if (lockdep_hardirq_context()) {
4755 		/*
4756 		 * Check if force_irqthreads will run us threaded.
4757 		 */
4758 		if (curr->hardirq_threaded || curr->irq_config)
4759 			return LD_WAIT_CONFIG;
4760 
4761 		return LD_WAIT_SPIN;
4762 	} else if (curr->softirq_context) {
4763 		/*
4764 		 * Softirqs are always threaded.
4765 		 */
4766 		return LD_WAIT_CONFIG;
4767 	}
4768 
4769 	return LD_WAIT_MAX;
4770 }
4771 
4772 static int
print_lock_invalid_wait_context(struct task_struct * curr,struct held_lock * hlock)4773 print_lock_invalid_wait_context(struct task_struct *curr,
4774 				struct held_lock *hlock)
4775 {
4776 	short curr_inner;
4777 
4778 	if (!debug_locks_off())
4779 		return 0;
4780 	if (debug_locks_silent)
4781 		return 0;
4782 
4783 	nbcon_cpu_emergency_enter();
4784 
4785 	pr_warn("\n");
4786 	pr_warn("=============================\n");
4787 	pr_warn("[ BUG: Invalid wait context ]\n");
4788 	print_kernel_ident();
4789 	pr_warn("-----------------------------\n");
4790 
4791 	pr_warn("%s/%d is trying to lock:\n", curr->comm, task_pid_nr(curr));
4792 	print_lock(hlock);
4793 
4794 	pr_warn("other info that might help us debug this:\n");
4795 
4796 	curr_inner = task_wait_context(curr);
4797 	pr_warn("context-{%d:%d}\n", curr_inner, curr_inner);
4798 
4799 	lockdep_print_held_locks(curr);
4800 
4801 	pr_warn("stack backtrace:\n");
4802 	dump_stack();
4803 
4804 	nbcon_cpu_emergency_exit();
4805 
4806 	return 0;
4807 }
4808 
4809 /*
4810  * Verify the wait_type context.
4811  *
4812  * This check validates we take locks in the right wait-type order; that is it
4813  * ensures that we do not take mutexes inside spinlocks and do not attempt to
4814  * acquire spinlocks inside raw_spinlocks and the sort.
4815  *
4816  * The entire thing is slightly more complex because of RCU, RCU is a lock that
4817  * can be taken from (pretty much) any context but also has constraints.
4818  * However when taken in a stricter environment the RCU lock does not loosen
4819  * the constraints.
4820  *
4821  * Therefore we must look for the strictest environment in the lock stack and
4822  * compare that to the lock we're trying to acquire.
4823  */
check_wait_context(struct task_struct * curr,struct held_lock * next)4824 static int check_wait_context(struct task_struct *curr, struct held_lock *next)
4825 {
4826 	u8 next_inner = hlock_class(next)->wait_type_inner;
4827 	u8 next_outer = hlock_class(next)->wait_type_outer;
4828 	u8 curr_inner;
4829 	int depth;
4830 
4831 	if (!next_inner || next->trylock)
4832 		return 0;
4833 
4834 	if (!next_outer)
4835 		next_outer = next_inner;
4836 
4837 	/*
4838 	 * Find start of current irq_context..
4839 	 */
4840 	for (depth = curr->lockdep_depth - 1; depth >= 0; depth--) {
4841 		struct held_lock *prev = curr->held_locks + depth;
4842 		if (prev->irq_context != next->irq_context)
4843 			break;
4844 	}
4845 	depth++;
4846 
4847 	curr_inner = task_wait_context(curr);
4848 
4849 	for (; depth < curr->lockdep_depth; depth++) {
4850 		struct held_lock *prev = curr->held_locks + depth;
4851 		struct lock_class *class = hlock_class(prev);
4852 		u8 prev_inner = class->wait_type_inner;
4853 
4854 		if (prev_inner) {
4855 			/*
4856 			 * We can have a bigger inner than a previous one
4857 			 * when outer is smaller than inner, as with RCU.
4858 			 *
4859 			 * Also due to trylocks.
4860 			 */
4861 			curr_inner = min(curr_inner, prev_inner);
4862 
4863 			/*
4864 			 * Allow override for annotations -- this is typically
4865 			 * only valid/needed for code that only exists when
4866 			 * CONFIG_PREEMPT_RT=n.
4867 			 */
4868 			if (unlikely(class->lock_type == LD_LOCK_WAIT_OVERRIDE))
4869 				curr_inner = prev_inner;
4870 		}
4871 	}
4872 
4873 	if (next_outer > curr_inner)
4874 		return print_lock_invalid_wait_context(curr, next);
4875 
4876 	return 0;
4877 }
4878 
4879 #else /* CONFIG_PROVE_LOCKING */
4880 
4881 static inline int
mark_usage(struct task_struct * curr,struct held_lock * hlock,int check)4882 mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
4883 {
4884 	return 1;
4885 }
4886 
task_irq_context(struct task_struct * task)4887 static inline unsigned int task_irq_context(struct task_struct *task)
4888 {
4889 	return 0;
4890 }
4891 
separate_irq_context(struct task_struct * curr,struct held_lock * hlock)4892 static inline int separate_irq_context(struct task_struct *curr,
4893 		struct held_lock *hlock)
4894 {
4895 	return 0;
4896 }
4897 
check_wait_context(struct task_struct * curr,struct held_lock * next)4898 static inline int check_wait_context(struct task_struct *curr,
4899 				     struct held_lock *next)
4900 {
4901 	return 0;
4902 }
4903 
4904 #endif /* CONFIG_PROVE_LOCKING */
4905 
4906 /*
4907  * Initialize a lock instance's lock-class mapping info:
4908  */
lockdep_init_map_type(struct lockdep_map * lock,const char * name,struct lock_class_key * key,int subclass,u8 inner,u8 outer,u8 lock_type)4909 void lockdep_init_map_type(struct lockdep_map *lock, const char *name,
4910 			    struct lock_class_key *key, int subclass,
4911 			    u8 inner, u8 outer, u8 lock_type)
4912 {
4913 	int i;
4914 
4915 	for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
4916 		lock->class_cache[i] = NULL;
4917 
4918 #ifdef CONFIG_LOCK_STAT
4919 	lock->cpu = raw_smp_processor_id();
4920 #endif
4921 
4922 	/*
4923 	 * Can't be having no nameless bastards around this place!
4924 	 */
4925 	if (DEBUG_LOCKS_WARN_ON(!name)) {
4926 		lock->name = "NULL";
4927 		return;
4928 	}
4929 
4930 	lock->name = name;
4931 
4932 	lock->wait_type_outer = outer;
4933 	lock->wait_type_inner = inner;
4934 	lock->lock_type = lock_type;
4935 
4936 	/*
4937 	 * No key, no joy, we need to hash something.
4938 	 */
4939 	if (DEBUG_LOCKS_WARN_ON(!key))
4940 		return;
4941 	/*
4942 	 * Sanity check, the lock-class key must either have been allocated
4943 	 * statically or must have been registered as a dynamic key.
4944 	 */
4945 	if (!static_obj(key) && !is_dynamic_key(key)) {
4946 		if (debug_locks)
4947 			printk(KERN_ERR "BUG: key %px has not been registered!\n", key);
4948 		DEBUG_LOCKS_WARN_ON(1);
4949 		return;
4950 	}
4951 	lock->key = key;
4952 
4953 	if (unlikely(!debug_locks))
4954 		return;
4955 
4956 	if (subclass) {
4957 		unsigned long flags;
4958 
4959 		if (DEBUG_LOCKS_WARN_ON(!lockdep_enabled()))
4960 			return;
4961 
4962 		raw_local_irq_save(flags);
4963 		lockdep_recursion_inc();
4964 		register_lock_class(lock, subclass, 1);
4965 		lockdep_recursion_finish();
4966 		raw_local_irq_restore(flags);
4967 	}
4968 }
4969 EXPORT_SYMBOL_GPL(lockdep_init_map_type);
4970 
4971 struct lock_class_key __lockdep_no_validate__;
4972 EXPORT_SYMBOL_GPL(__lockdep_no_validate__);
4973 
4974 struct lock_class_key __lockdep_no_track__;
4975 EXPORT_SYMBOL_GPL(__lockdep_no_track__);
4976 
4977 #ifdef CONFIG_PROVE_LOCKING
lockdep_set_lock_cmp_fn(struct lockdep_map * lock,lock_cmp_fn cmp_fn,lock_print_fn print_fn)4978 void lockdep_set_lock_cmp_fn(struct lockdep_map *lock, lock_cmp_fn cmp_fn,
4979 			     lock_print_fn print_fn)
4980 {
4981 	struct lock_class *class = lock->class_cache[0];
4982 	unsigned long flags;
4983 
4984 	raw_local_irq_save(flags);
4985 	lockdep_recursion_inc();
4986 
4987 	if (!class)
4988 		class = register_lock_class(lock, 0, 0);
4989 
4990 	if (class) {
4991 		WARN_ON(class->cmp_fn	&& class->cmp_fn != cmp_fn);
4992 		WARN_ON(class->print_fn && class->print_fn != print_fn);
4993 
4994 		class->cmp_fn	= cmp_fn;
4995 		class->print_fn = print_fn;
4996 	}
4997 
4998 	lockdep_recursion_finish();
4999 	raw_local_irq_restore(flags);
5000 }
5001 EXPORT_SYMBOL_GPL(lockdep_set_lock_cmp_fn);
5002 #endif
5003 
5004 static void
print_lock_nested_lock_not_held(struct task_struct * curr,struct held_lock * hlock)5005 print_lock_nested_lock_not_held(struct task_struct *curr,
5006 				struct held_lock *hlock)
5007 {
5008 	if (!debug_locks_off())
5009 		return;
5010 	if (debug_locks_silent)
5011 		return;
5012 
5013 	nbcon_cpu_emergency_enter();
5014 
5015 	pr_warn("\n");
5016 	pr_warn("==================================\n");
5017 	pr_warn("WARNING: Nested lock was not taken\n");
5018 	print_kernel_ident();
5019 	pr_warn("----------------------------------\n");
5020 
5021 	pr_warn("%s/%d is trying to lock:\n", curr->comm, task_pid_nr(curr));
5022 	print_lock(hlock);
5023 
5024 	pr_warn("\nbut this task is not holding:\n");
5025 	pr_warn("%s\n", hlock->nest_lock->name);
5026 
5027 	pr_warn("\nstack backtrace:\n");
5028 	dump_stack();
5029 
5030 	pr_warn("\nother info that might help us debug this:\n");
5031 	lockdep_print_held_locks(curr);
5032 
5033 	pr_warn("\nstack backtrace:\n");
5034 	dump_stack();
5035 
5036 	nbcon_cpu_emergency_exit();
5037 }
5038 
5039 static int __lock_is_held(const struct lockdep_map *lock, int read);
5040 
5041 /*
5042  * This gets called for every mutex_lock*()/spin_lock*() operation.
5043  * We maintain the dependency maps and validate the locking attempt:
5044  *
5045  * The callers must make sure that IRQs are disabled before calling it,
5046  * otherwise we could get an interrupt which would want to take locks,
5047  * which would end up in lockdep again.
5048  */
__lock_acquire(struct lockdep_map * lock,unsigned int subclass,int trylock,int read,int check,int hardirqs_off,struct lockdep_map * nest_lock,unsigned long ip,int references,int pin_count,int sync)5049 static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
5050 			  int trylock, int read, int check, int hardirqs_off,
5051 			  struct lockdep_map *nest_lock, unsigned long ip,
5052 			  int references, int pin_count, int sync)
5053 {
5054 	struct task_struct *curr = current;
5055 	struct lock_class *class = NULL;
5056 	struct held_lock *hlock;
5057 	unsigned int depth;
5058 	int chain_head = 0;
5059 	int class_idx;
5060 	u64 chain_key;
5061 
5062 	if (unlikely(!debug_locks))
5063 		return 0;
5064 
5065 	if (unlikely(lock->key == &__lockdep_no_track__))
5066 		return 0;
5067 
5068 	if (!prove_locking || lock->key == &__lockdep_no_validate__)
5069 		check = 0;
5070 
5071 	if (subclass < NR_LOCKDEP_CACHING_CLASSES)
5072 		class = lock->class_cache[subclass];
5073 	/*
5074 	 * Not cached?
5075 	 */
5076 	if (unlikely(!class)) {
5077 		class = register_lock_class(lock, subclass, 0);
5078 		if (!class)
5079 			return 0;
5080 	}
5081 
5082 	debug_class_ops_inc(class);
5083 
5084 	if (very_verbose(class)) {
5085 		nbcon_cpu_emergency_enter();
5086 		printk("\nacquire class [%px] %s", class->key, class->name);
5087 		if (class->name_version > 1)
5088 			printk(KERN_CONT "#%d", class->name_version);
5089 		printk(KERN_CONT "\n");
5090 		dump_stack();
5091 		nbcon_cpu_emergency_exit();
5092 	}
5093 
5094 	/*
5095 	 * Add the lock to the list of currently held locks.
5096 	 * (we dont increase the depth just yet, up until the
5097 	 * dependency checks are done)
5098 	 */
5099 	depth = curr->lockdep_depth;
5100 	/*
5101 	 * Ran out of static storage for our per-task lock stack again have we?
5102 	 */
5103 	if (DEBUG_LOCKS_WARN_ON(depth >= MAX_LOCK_DEPTH))
5104 		return 0;
5105 
5106 	class_idx = class - lock_classes;
5107 
5108 	if (depth && !sync) {
5109 		/* we're holding locks and the new held lock is not a sync */
5110 		hlock = curr->held_locks + depth - 1;
5111 		if (hlock->class_idx == class_idx && nest_lock) {
5112 			if (!references)
5113 				references++;
5114 
5115 			if (!hlock->references)
5116 				hlock->references++;
5117 
5118 			hlock->references += references;
5119 
5120 			/* Overflow */
5121 			if (DEBUG_LOCKS_WARN_ON(hlock->references < references))
5122 				return 0;
5123 
5124 			return 2;
5125 		}
5126 	}
5127 
5128 	hlock = curr->held_locks + depth;
5129 	/*
5130 	 * Plain impossible, we just registered it and checked it weren't no
5131 	 * NULL like.. I bet this mushroom I ate was good!
5132 	 */
5133 	if (DEBUG_LOCKS_WARN_ON(!class))
5134 		return 0;
5135 	hlock->class_idx = class_idx;
5136 	hlock->acquire_ip = ip;
5137 	hlock->instance = lock;
5138 	hlock->nest_lock = nest_lock;
5139 	hlock->irq_context = task_irq_context(curr);
5140 	hlock->trylock = trylock;
5141 	hlock->read = read;
5142 	hlock->check = check;
5143 	hlock->sync = !!sync;
5144 	hlock->hardirqs_off = !!hardirqs_off;
5145 	hlock->references = references;
5146 #ifdef CONFIG_LOCK_STAT
5147 	hlock->waittime_stamp = 0;
5148 	hlock->holdtime_stamp = lockstat_clock();
5149 #endif
5150 	hlock->pin_count = pin_count;
5151 
5152 	if (check_wait_context(curr, hlock))
5153 		return 0;
5154 
5155 	/* Initialize the lock usage bit */
5156 	if (!mark_usage(curr, hlock, check))
5157 		return 0;
5158 
5159 	/*
5160 	 * Calculate the chain hash: it's the combined hash of all the
5161 	 * lock keys along the dependency chain. We save the hash value
5162 	 * at every step so that we can get the current hash easily
5163 	 * after unlock. The chain hash is then used to cache dependency
5164 	 * results.
5165 	 *
5166 	 * The 'key ID' is what is the most compact key value to drive
5167 	 * the hash, not class->key.
5168 	 */
5169 	/*
5170 	 * Whoops, we did it again.. class_idx is invalid.
5171 	 */
5172 	if (DEBUG_LOCKS_WARN_ON(!test_bit(class_idx, lock_classes_in_use)))
5173 		return 0;
5174 
5175 	chain_key = curr->curr_chain_key;
5176 	if (!depth) {
5177 		/*
5178 		 * How can we have a chain hash when we ain't got no keys?!
5179 		 */
5180 		if (DEBUG_LOCKS_WARN_ON(chain_key != INITIAL_CHAIN_KEY))
5181 			return 0;
5182 		chain_head = 1;
5183 	}
5184 
5185 	hlock->prev_chain_key = chain_key;
5186 	if (separate_irq_context(curr, hlock)) {
5187 		chain_key = INITIAL_CHAIN_KEY;
5188 		chain_head = 1;
5189 	}
5190 	chain_key = iterate_chain_key(chain_key, hlock_id(hlock));
5191 
5192 	if (nest_lock && !__lock_is_held(nest_lock, -1)) {
5193 		print_lock_nested_lock_not_held(curr, hlock);
5194 		return 0;
5195 	}
5196 
5197 	if (!debug_locks_silent) {
5198 		WARN_ON_ONCE(depth && !hlock_class(hlock - 1)->key);
5199 		WARN_ON_ONCE(!hlock_class(hlock)->key);
5200 	}
5201 
5202 	if (!validate_chain(curr, hlock, chain_head, chain_key))
5203 		return 0;
5204 
5205 	/* For lock_sync(), we are done here since no actual critical section */
5206 	if (hlock->sync)
5207 		return 1;
5208 
5209 	curr->curr_chain_key = chain_key;
5210 	curr->lockdep_depth++;
5211 	check_chain_key(curr);
5212 #ifdef CONFIG_DEBUG_LOCKDEP
5213 	if (unlikely(!debug_locks))
5214 		return 0;
5215 #endif
5216 	if (unlikely(curr->lockdep_depth >= MAX_LOCK_DEPTH)) {
5217 		debug_locks_off();
5218 		nbcon_cpu_emergency_enter();
5219 		print_lockdep_off("BUG: MAX_LOCK_DEPTH too low!");
5220 		printk(KERN_DEBUG "depth: %i  max: %lu!\n",
5221 		       curr->lockdep_depth, MAX_LOCK_DEPTH);
5222 
5223 		lockdep_print_held_locks(current);
5224 		debug_show_all_locks();
5225 		dump_stack();
5226 		nbcon_cpu_emergency_exit();
5227 
5228 		return 0;
5229 	}
5230 
5231 	if (unlikely(curr->lockdep_depth > max_lockdep_depth))
5232 		max_lockdep_depth = curr->lockdep_depth;
5233 
5234 	return 1;
5235 }
5236 
print_unlock_imbalance_bug(struct task_struct * curr,struct lockdep_map * lock,unsigned long ip)5237 static void print_unlock_imbalance_bug(struct task_struct *curr,
5238 				       struct lockdep_map *lock,
5239 				       unsigned long ip)
5240 {
5241 	if (!debug_locks_off())
5242 		return;
5243 	if (debug_locks_silent)
5244 		return;
5245 
5246 	nbcon_cpu_emergency_enter();
5247 
5248 	pr_warn("\n");
5249 	pr_warn("=====================================\n");
5250 	pr_warn("WARNING: bad unlock balance detected!\n");
5251 	print_kernel_ident();
5252 	pr_warn("-------------------------------------\n");
5253 	pr_warn("%s/%d is trying to release lock (",
5254 		curr->comm, task_pid_nr(curr));
5255 	print_lockdep_cache(lock);
5256 	pr_cont(") at:\n");
5257 	print_ip_sym(KERN_WARNING, ip);
5258 	pr_warn("but there are no more locks to release!\n");
5259 	pr_warn("\nother info that might help us debug this:\n");
5260 	lockdep_print_held_locks(curr);
5261 
5262 	pr_warn("\nstack backtrace:\n");
5263 	dump_stack();
5264 
5265 	nbcon_cpu_emergency_exit();
5266 }
5267 
match_held_lock(const struct held_lock * hlock,const struct lockdep_map * lock)5268 static noinstr int match_held_lock(const struct held_lock *hlock,
5269 				   const struct lockdep_map *lock)
5270 {
5271 	if (hlock->instance == lock)
5272 		return 1;
5273 
5274 	if (hlock->references) {
5275 		const struct lock_class *class = lock->class_cache[0];
5276 
5277 		if (!class)
5278 			class = look_up_lock_class(lock, 0);
5279 
5280 		/*
5281 		 * If look_up_lock_class() failed to find a class, we're trying
5282 		 * to test if we hold a lock that has never yet been acquired.
5283 		 * Clearly if the lock hasn't been acquired _ever_, we're not
5284 		 * holding it either, so report failure.
5285 		 */
5286 		if (!class)
5287 			return 0;
5288 
5289 		/*
5290 		 * References, but not a lock we're actually ref-counting?
5291 		 * State got messed up, follow the sites that change ->references
5292 		 * and try to make sense of it.
5293 		 */
5294 		if (DEBUG_LOCKS_WARN_ON(!hlock->nest_lock))
5295 			return 0;
5296 
5297 		if (hlock->class_idx == class - lock_classes)
5298 			return 1;
5299 	}
5300 
5301 	return 0;
5302 }
5303 
5304 /* @depth must not be zero */
find_held_lock(struct task_struct * curr,struct lockdep_map * lock,unsigned int depth,int * idx)5305 static struct held_lock *find_held_lock(struct task_struct *curr,
5306 					struct lockdep_map *lock,
5307 					unsigned int depth, int *idx)
5308 {
5309 	struct held_lock *ret, *hlock, *prev_hlock;
5310 	int i;
5311 
5312 	i = depth - 1;
5313 	hlock = curr->held_locks + i;
5314 	ret = hlock;
5315 	if (match_held_lock(hlock, lock))
5316 		goto out;
5317 
5318 	ret = NULL;
5319 	for (i--, prev_hlock = hlock--;
5320 	     i >= 0;
5321 	     i--, prev_hlock = hlock--) {
5322 		/*
5323 		 * We must not cross into another context:
5324 		 */
5325 		if (prev_hlock->irq_context != hlock->irq_context) {
5326 			ret = NULL;
5327 			break;
5328 		}
5329 		if (match_held_lock(hlock, lock)) {
5330 			ret = hlock;
5331 			break;
5332 		}
5333 	}
5334 
5335 out:
5336 	*idx = i;
5337 	return ret;
5338 }
5339 
reacquire_held_locks(struct task_struct * curr,unsigned int depth,int idx,unsigned int * merged)5340 static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
5341 				int idx, unsigned int *merged)
5342 {
5343 	struct held_lock *hlock;
5344 	int first_idx = idx;
5345 
5346 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
5347 		return 0;
5348 
5349 	for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) {
5350 		switch (__lock_acquire(hlock->instance,
5351 				    hlock_class(hlock)->subclass,
5352 				    hlock->trylock,
5353 				    hlock->read, hlock->check,
5354 				    hlock->hardirqs_off,
5355 				    hlock->nest_lock, hlock->acquire_ip,
5356 				    hlock->references, hlock->pin_count, 0)) {
5357 		case 0:
5358 			return 1;
5359 		case 1:
5360 			break;
5361 		case 2:
5362 			*merged += (idx == first_idx);
5363 			break;
5364 		default:
5365 			WARN_ON(1);
5366 			return 0;
5367 		}
5368 	}
5369 	return 0;
5370 }
5371 
5372 static int
__lock_set_class(struct lockdep_map * lock,const char * name,struct lock_class_key * key,unsigned int subclass,unsigned long ip)5373 __lock_set_class(struct lockdep_map *lock, const char *name,
5374 		 struct lock_class_key *key, unsigned int subclass,
5375 		 unsigned long ip)
5376 {
5377 	struct task_struct *curr = current;
5378 	unsigned int depth, merged = 0;
5379 	struct held_lock *hlock;
5380 	struct lock_class *class;
5381 	int i;
5382 
5383 	if (unlikely(!debug_locks))
5384 		return 0;
5385 
5386 	depth = curr->lockdep_depth;
5387 	/*
5388 	 * This function is about (re)setting the class of a held lock,
5389 	 * yet we're not actually holding any locks. Naughty user!
5390 	 */
5391 	if (DEBUG_LOCKS_WARN_ON(!depth))
5392 		return 0;
5393 
5394 	hlock = find_held_lock(curr, lock, depth, &i);
5395 	if (!hlock) {
5396 		print_unlock_imbalance_bug(curr, lock, ip);
5397 		return 0;
5398 	}
5399 
5400 	lockdep_init_map_type(lock, name, key, 0,
5401 			      lock->wait_type_inner,
5402 			      lock->wait_type_outer,
5403 			      lock->lock_type);
5404 	class = register_lock_class(lock, subclass, 0);
5405 	hlock->class_idx = class - lock_classes;
5406 
5407 	curr->lockdep_depth = i;
5408 	curr->curr_chain_key = hlock->prev_chain_key;
5409 
5410 	if (reacquire_held_locks(curr, depth, i, &merged))
5411 		return 0;
5412 
5413 	/*
5414 	 * I took it apart and put it back together again, except now I have
5415 	 * these 'spare' parts.. where shall I put them.
5416 	 */
5417 	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged))
5418 		return 0;
5419 	return 1;
5420 }
5421 
__lock_downgrade(struct lockdep_map * lock,unsigned long ip)5422 static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
5423 {
5424 	struct task_struct *curr = current;
5425 	unsigned int depth, merged = 0;
5426 	struct held_lock *hlock;
5427 	int i;
5428 
5429 	if (unlikely(!debug_locks))
5430 		return 0;
5431 
5432 	depth = curr->lockdep_depth;
5433 	/*
5434 	 * This function is about (re)setting the class of a held lock,
5435 	 * yet we're not actually holding any locks. Naughty user!
5436 	 */
5437 	if (DEBUG_LOCKS_WARN_ON(!depth))
5438 		return 0;
5439 
5440 	hlock = find_held_lock(curr, lock, depth, &i);
5441 	if (!hlock) {
5442 		print_unlock_imbalance_bug(curr, lock, ip);
5443 		return 0;
5444 	}
5445 
5446 	curr->lockdep_depth = i;
5447 	curr->curr_chain_key = hlock->prev_chain_key;
5448 
5449 	WARN(hlock->read, "downgrading a read lock");
5450 	hlock->read = 1;
5451 	hlock->acquire_ip = ip;
5452 
5453 	if (reacquire_held_locks(curr, depth, i, &merged))
5454 		return 0;
5455 
5456 	/* Merging can't happen with unchanged classes.. */
5457 	if (DEBUG_LOCKS_WARN_ON(merged))
5458 		return 0;
5459 
5460 	/*
5461 	 * I took it apart and put it back together again, except now I have
5462 	 * these 'spare' parts.. where shall I put them.
5463 	 */
5464 	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
5465 		return 0;
5466 
5467 	return 1;
5468 }
5469 
5470 /*
5471  * Remove the lock from the list of currently held locks - this gets
5472  * called on mutex_unlock()/spin_unlock*() (or on a failed
5473  * mutex_lock_interruptible()).
5474  */
5475 static int
__lock_release(struct lockdep_map * lock,unsigned long ip)5476 __lock_release(struct lockdep_map *lock, unsigned long ip)
5477 {
5478 	struct task_struct *curr = current;
5479 	unsigned int depth, merged = 1;
5480 	struct held_lock *hlock;
5481 	int i;
5482 
5483 	if (unlikely(!debug_locks))
5484 		return 0;
5485 
5486 	depth = curr->lockdep_depth;
5487 	/*
5488 	 * So we're all set to release this lock.. wait what lock? We don't
5489 	 * own any locks, you've been drinking again?
5490 	 */
5491 	if (depth <= 0) {
5492 		print_unlock_imbalance_bug(curr, lock, ip);
5493 		return 0;
5494 	}
5495 
5496 	/*
5497 	 * Check whether the lock exists in the current stack
5498 	 * of held locks:
5499 	 */
5500 	hlock = find_held_lock(curr, lock, depth, &i);
5501 	if (!hlock) {
5502 		print_unlock_imbalance_bug(curr, lock, ip);
5503 		return 0;
5504 	}
5505 
5506 	if (hlock->instance == lock)
5507 		lock_release_holdtime(hlock);
5508 
5509 	WARN(hlock->pin_count, "releasing a pinned lock\n");
5510 
5511 	if (hlock->references) {
5512 		hlock->references--;
5513 		if (hlock->references) {
5514 			/*
5515 			 * We had, and after removing one, still have
5516 			 * references, the current lock stack is still
5517 			 * valid. We're done!
5518 			 */
5519 			return 1;
5520 		}
5521 	}
5522 
5523 	/*
5524 	 * We have the right lock to unlock, 'hlock' points to it.
5525 	 * Now we remove it from the stack, and add back the other
5526 	 * entries (if any), recalculating the hash along the way:
5527 	 */
5528 
5529 	curr->lockdep_depth = i;
5530 	curr->curr_chain_key = hlock->prev_chain_key;
5531 
5532 	/*
5533 	 * The most likely case is when the unlock is on the innermost
5534 	 * lock. In this case, we are done!
5535 	 */
5536 	if (i == depth-1)
5537 		return 1;
5538 
5539 	if (reacquire_held_locks(curr, depth, i + 1, &merged))
5540 		return 0;
5541 
5542 	/*
5543 	 * We had N bottles of beer on the wall, we drank one, but now
5544 	 * there's not N-1 bottles of beer left on the wall...
5545 	 * Pouring two of the bottles together is acceptable.
5546 	 */
5547 	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged);
5548 
5549 	/*
5550 	 * Since reacquire_held_locks() would have called check_chain_key()
5551 	 * indirectly via __lock_acquire(), we don't need to do it again
5552 	 * on return.
5553 	 */
5554 	return 0;
5555 }
5556 
5557 static __always_inline
__lock_is_held(const struct lockdep_map * lock,int read)5558 int __lock_is_held(const struct lockdep_map *lock, int read)
5559 {
5560 	struct task_struct *curr = current;
5561 	int i;
5562 
5563 	for (i = 0; i < curr->lockdep_depth; i++) {
5564 		struct held_lock *hlock = curr->held_locks + i;
5565 
5566 		if (match_held_lock(hlock, lock)) {
5567 			if (read == -1 || !!hlock->read == read)
5568 				return LOCK_STATE_HELD;
5569 
5570 			return LOCK_STATE_NOT_HELD;
5571 		}
5572 	}
5573 
5574 	return LOCK_STATE_NOT_HELD;
5575 }
5576 
__lock_pin_lock(struct lockdep_map * lock)5577 static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock)
5578 {
5579 	struct pin_cookie cookie = NIL_COOKIE;
5580 	struct task_struct *curr = current;
5581 	int i;
5582 
5583 	if (unlikely(!debug_locks))
5584 		return cookie;
5585 
5586 	for (i = 0; i < curr->lockdep_depth; i++) {
5587 		struct held_lock *hlock = curr->held_locks + i;
5588 
5589 		if (match_held_lock(hlock, lock)) {
5590 			/*
5591 			 * Grab 16bits of randomness; this is sufficient to not
5592 			 * be guessable and still allows some pin nesting in
5593 			 * our u32 pin_count.
5594 			 */
5595 			cookie.val = 1 + (sched_clock() & 0xffff);
5596 			hlock->pin_count += cookie.val;
5597 			return cookie;
5598 		}
5599 	}
5600 
5601 	WARN(1, "pinning an unheld lock\n");
5602 	return cookie;
5603 }
5604 
__lock_repin_lock(struct lockdep_map * lock,struct pin_cookie cookie)5605 static void __lock_repin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
5606 {
5607 	struct task_struct *curr = current;
5608 	int i;
5609 
5610 	if (unlikely(!debug_locks))
5611 		return;
5612 
5613 	for (i = 0; i < curr->lockdep_depth; i++) {
5614 		struct held_lock *hlock = curr->held_locks + i;
5615 
5616 		if (match_held_lock(hlock, lock)) {
5617 			hlock->pin_count += cookie.val;
5618 			return;
5619 		}
5620 	}
5621 
5622 	WARN(1, "pinning an unheld lock\n");
5623 }
5624 
__lock_unpin_lock(struct lockdep_map * lock,struct pin_cookie cookie)5625 static void __lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
5626 {
5627 	struct task_struct *curr = current;
5628 	int i;
5629 
5630 	if (unlikely(!debug_locks))
5631 		return;
5632 
5633 	for (i = 0; i < curr->lockdep_depth; i++) {
5634 		struct held_lock *hlock = curr->held_locks + i;
5635 
5636 		if (match_held_lock(hlock, lock)) {
5637 			if (WARN(!hlock->pin_count, "unpinning an unpinned lock\n"))
5638 				return;
5639 
5640 			hlock->pin_count -= cookie.val;
5641 
5642 			if (WARN((int)hlock->pin_count < 0, "pin count corrupted\n"))
5643 				hlock->pin_count = 0;
5644 
5645 			return;
5646 		}
5647 	}
5648 
5649 	WARN(1, "unpinning an unheld lock\n");
5650 }
5651 
5652 /*
5653  * Check whether we follow the irq-flags state precisely:
5654  */
check_flags(unsigned long flags)5655 static noinstr void check_flags(unsigned long flags)
5656 {
5657 #if defined(CONFIG_PROVE_LOCKING) && defined(CONFIG_DEBUG_LOCKDEP)
5658 	if (!debug_locks)
5659 		return;
5660 
5661 	/* Get the warning out..  */
5662 	instrumentation_begin();
5663 
5664 	if (irqs_disabled_flags(flags)) {
5665 		if (DEBUG_LOCKS_WARN_ON(lockdep_hardirqs_enabled())) {
5666 			printk("possible reason: unannotated irqs-off.\n");
5667 		}
5668 	} else {
5669 		if (DEBUG_LOCKS_WARN_ON(!lockdep_hardirqs_enabled())) {
5670 			printk("possible reason: unannotated irqs-on.\n");
5671 		}
5672 	}
5673 
5674 #ifndef CONFIG_PREEMPT_RT
5675 	/*
5676 	 * We dont accurately track softirq state in e.g.
5677 	 * hardirq contexts (such as on 4KSTACKS), so only
5678 	 * check if not in hardirq contexts:
5679 	 */
5680 	if (!hardirq_count()) {
5681 		if (softirq_count()) {
5682 			/* like the above, but with softirqs */
5683 			DEBUG_LOCKS_WARN_ON(current->softirqs_enabled);
5684 		} else {
5685 			/* lick the above, does it taste good? */
5686 			DEBUG_LOCKS_WARN_ON(!current->softirqs_enabled);
5687 		}
5688 	}
5689 #endif
5690 
5691 	if (!debug_locks)
5692 		print_irqtrace_events(current);
5693 
5694 	instrumentation_end();
5695 #endif
5696 }
5697 
lock_set_class(struct lockdep_map * lock,const char * name,struct lock_class_key * key,unsigned int subclass,unsigned long ip)5698 void lock_set_class(struct lockdep_map *lock, const char *name,
5699 		    struct lock_class_key *key, unsigned int subclass,
5700 		    unsigned long ip)
5701 {
5702 	unsigned long flags;
5703 
5704 	if (unlikely(!lockdep_enabled()))
5705 		return;
5706 
5707 	raw_local_irq_save(flags);
5708 	lockdep_recursion_inc();
5709 	check_flags(flags);
5710 	if (__lock_set_class(lock, name, key, subclass, ip))
5711 		check_chain_key(current);
5712 	lockdep_recursion_finish();
5713 	raw_local_irq_restore(flags);
5714 }
5715 EXPORT_SYMBOL_GPL(lock_set_class);
5716 
lock_downgrade(struct lockdep_map * lock,unsigned long ip)5717 void lock_downgrade(struct lockdep_map *lock, unsigned long ip)
5718 {
5719 	unsigned long flags;
5720 
5721 	if (unlikely(!lockdep_enabled()))
5722 		return;
5723 
5724 	raw_local_irq_save(flags);
5725 	lockdep_recursion_inc();
5726 	check_flags(flags);
5727 	if (__lock_downgrade(lock, ip))
5728 		check_chain_key(current);
5729 	lockdep_recursion_finish();
5730 	raw_local_irq_restore(flags);
5731 }
5732 EXPORT_SYMBOL_GPL(lock_downgrade);
5733 
5734 /* NMI context !!! */
verify_lock_unused(struct lockdep_map * lock,struct held_lock * hlock,int subclass)5735 static void verify_lock_unused(struct lockdep_map *lock, struct held_lock *hlock, int subclass)
5736 {
5737 #ifdef CONFIG_PROVE_LOCKING
5738 	struct lock_class *class = look_up_lock_class(lock, subclass);
5739 	unsigned long mask = LOCKF_USED;
5740 
5741 	/* if it doesn't have a class (yet), it certainly hasn't been used yet */
5742 	if (!class)
5743 		return;
5744 
5745 	/*
5746 	 * READ locks only conflict with USED, such that if we only ever use
5747 	 * READ locks, there is no deadlock possible -- RCU.
5748 	 */
5749 	if (!hlock->read)
5750 		mask |= LOCKF_USED_READ;
5751 
5752 	if (!(class->usage_mask & mask))
5753 		return;
5754 
5755 	hlock->class_idx = class - lock_classes;
5756 
5757 	print_usage_bug(current, hlock, LOCK_USED, LOCK_USAGE_STATES);
5758 #endif
5759 }
5760 
lockdep_nmi(void)5761 static bool lockdep_nmi(void)
5762 {
5763 	if (raw_cpu_read(lockdep_recursion))
5764 		return false;
5765 
5766 	if (!in_nmi())
5767 		return false;
5768 
5769 	return true;
5770 }
5771 
5772 /*
5773  * read_lock() is recursive if:
5774  * 1. We force lockdep think this way in selftests or
5775  * 2. The implementation is not queued read/write lock or
5776  * 3. The locker is at an in_interrupt() context.
5777  */
read_lock_is_recursive(void)5778 bool read_lock_is_recursive(void)
5779 {
5780 	return force_read_lock_recursive ||
5781 	       !IS_ENABLED(CONFIG_QUEUED_RWLOCKS) ||
5782 	       in_interrupt();
5783 }
5784 EXPORT_SYMBOL_GPL(read_lock_is_recursive);
5785 
5786 /*
5787  * We are not always called with irqs disabled - do that here,
5788  * and also avoid lockdep recursion:
5789  */
lock_acquire(struct lockdep_map * lock,unsigned int subclass,int trylock,int read,int check,struct lockdep_map * nest_lock,unsigned long ip)5790 void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
5791 			  int trylock, int read, int check,
5792 			  struct lockdep_map *nest_lock, unsigned long ip)
5793 {
5794 	unsigned long flags;
5795 
5796 	trace_lock_acquire(lock, subclass, trylock, read, check, nest_lock, ip);
5797 
5798 	if (!debug_locks)
5799 		return;
5800 
5801 	if (unlikely(!lockdep_enabled())) {
5802 		/* XXX allow trylock from NMI ?!? */
5803 		if (lockdep_nmi() && !trylock) {
5804 			struct held_lock hlock;
5805 
5806 			hlock.acquire_ip = ip;
5807 			hlock.instance = lock;
5808 			hlock.nest_lock = nest_lock;
5809 			hlock.irq_context = 2; // XXX
5810 			hlock.trylock = trylock;
5811 			hlock.read = read;
5812 			hlock.check = check;
5813 			hlock.hardirqs_off = true;
5814 			hlock.references = 0;
5815 
5816 			verify_lock_unused(lock, &hlock, subclass);
5817 		}
5818 		return;
5819 	}
5820 
5821 	raw_local_irq_save(flags);
5822 	check_flags(flags);
5823 
5824 	lockdep_recursion_inc();
5825 	__lock_acquire(lock, subclass, trylock, read, check,
5826 		       irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 0);
5827 	lockdep_recursion_finish();
5828 	raw_local_irq_restore(flags);
5829 }
5830 EXPORT_SYMBOL_GPL(lock_acquire);
5831 
lock_release(struct lockdep_map * lock,unsigned long ip)5832 void lock_release(struct lockdep_map *lock, unsigned long ip)
5833 {
5834 	unsigned long flags;
5835 
5836 	trace_lock_release(lock, ip);
5837 
5838 	if (unlikely(!lockdep_enabled() ||
5839 		     lock->key == &__lockdep_no_track__))
5840 		return;
5841 
5842 	raw_local_irq_save(flags);
5843 	check_flags(flags);
5844 
5845 	lockdep_recursion_inc();
5846 	if (__lock_release(lock, ip))
5847 		check_chain_key(current);
5848 	lockdep_recursion_finish();
5849 	raw_local_irq_restore(flags);
5850 }
5851 EXPORT_SYMBOL_GPL(lock_release);
5852 
5853 /*
5854  * lock_sync() - A special annotation for synchronize_{s,}rcu()-like API.
5855  *
5856  * No actual critical section is created by the APIs annotated with this: these
5857  * APIs are used to wait for one or multiple critical sections (on other CPUs
5858  * or threads), and it means that calling these APIs inside these critical
5859  * sections is potential deadlock.
5860  */
lock_sync(struct lockdep_map * lock,unsigned subclass,int read,int check,struct lockdep_map * nest_lock,unsigned long ip)5861 void lock_sync(struct lockdep_map *lock, unsigned subclass, int read,
5862 	       int check, struct lockdep_map *nest_lock, unsigned long ip)
5863 {
5864 	unsigned long flags;
5865 
5866 	if (unlikely(!lockdep_enabled()))
5867 		return;
5868 
5869 	raw_local_irq_save(flags);
5870 	check_flags(flags);
5871 
5872 	lockdep_recursion_inc();
5873 	__lock_acquire(lock, subclass, 0, read, check,
5874 		       irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 1);
5875 	check_chain_key(current);
5876 	lockdep_recursion_finish();
5877 	raw_local_irq_restore(flags);
5878 }
5879 EXPORT_SYMBOL_GPL(lock_sync);
5880 
lock_is_held_type(const struct lockdep_map * lock,int read)5881 noinstr int lock_is_held_type(const struct lockdep_map *lock, int read)
5882 {
5883 	unsigned long flags;
5884 	int ret = LOCK_STATE_NOT_HELD;
5885 
5886 	/*
5887 	 * Avoid false negative lockdep_assert_held() and
5888 	 * lockdep_assert_not_held().
5889 	 */
5890 	if (unlikely(!lockdep_enabled()))
5891 		return LOCK_STATE_UNKNOWN;
5892 
5893 	raw_local_irq_save(flags);
5894 	check_flags(flags);
5895 
5896 	lockdep_recursion_inc();
5897 	ret = __lock_is_held(lock, read);
5898 	lockdep_recursion_finish();
5899 	raw_local_irq_restore(flags);
5900 
5901 	return ret;
5902 }
5903 EXPORT_SYMBOL_GPL(lock_is_held_type);
5904 NOKPROBE_SYMBOL(lock_is_held_type);
5905 
lock_pin_lock(struct lockdep_map * lock)5906 struct pin_cookie lock_pin_lock(struct lockdep_map *lock)
5907 {
5908 	struct pin_cookie cookie = NIL_COOKIE;
5909 	unsigned long flags;
5910 
5911 	if (unlikely(!lockdep_enabled()))
5912 		return cookie;
5913 
5914 	raw_local_irq_save(flags);
5915 	check_flags(flags);
5916 
5917 	lockdep_recursion_inc();
5918 	cookie = __lock_pin_lock(lock);
5919 	lockdep_recursion_finish();
5920 	raw_local_irq_restore(flags);
5921 
5922 	return cookie;
5923 }
5924 EXPORT_SYMBOL_GPL(lock_pin_lock);
5925 
lock_repin_lock(struct lockdep_map * lock,struct pin_cookie cookie)5926 void lock_repin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
5927 {
5928 	unsigned long flags;
5929 
5930 	if (unlikely(!lockdep_enabled()))
5931 		return;
5932 
5933 	raw_local_irq_save(flags);
5934 	check_flags(flags);
5935 
5936 	lockdep_recursion_inc();
5937 	__lock_repin_lock(lock, cookie);
5938 	lockdep_recursion_finish();
5939 	raw_local_irq_restore(flags);
5940 }
5941 EXPORT_SYMBOL_GPL(lock_repin_lock);
5942 
lock_unpin_lock(struct lockdep_map * lock,struct pin_cookie cookie)5943 void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
5944 {
5945 	unsigned long flags;
5946 
5947 	if (unlikely(!lockdep_enabled()))
5948 		return;
5949 
5950 	raw_local_irq_save(flags);
5951 	check_flags(flags);
5952 
5953 	lockdep_recursion_inc();
5954 	__lock_unpin_lock(lock, cookie);
5955 	lockdep_recursion_finish();
5956 	raw_local_irq_restore(flags);
5957 }
5958 EXPORT_SYMBOL_GPL(lock_unpin_lock);
5959 
5960 #ifdef CONFIG_LOCK_STAT
print_lock_contention_bug(struct task_struct * curr,struct lockdep_map * lock,unsigned long ip)5961 static void print_lock_contention_bug(struct task_struct *curr,
5962 				      struct lockdep_map *lock,
5963 				      unsigned long ip)
5964 {
5965 	if (!debug_locks_off())
5966 		return;
5967 	if (debug_locks_silent)
5968 		return;
5969 
5970 	nbcon_cpu_emergency_enter();
5971 
5972 	pr_warn("\n");
5973 	pr_warn("=================================\n");
5974 	pr_warn("WARNING: bad contention detected!\n");
5975 	print_kernel_ident();
5976 	pr_warn("---------------------------------\n");
5977 	pr_warn("%s/%d is trying to contend lock (",
5978 		curr->comm, task_pid_nr(curr));
5979 	print_lockdep_cache(lock);
5980 	pr_cont(") at:\n");
5981 	print_ip_sym(KERN_WARNING, ip);
5982 	pr_warn("but there are no locks held!\n");
5983 	pr_warn("\nother info that might help us debug this:\n");
5984 	lockdep_print_held_locks(curr);
5985 
5986 	pr_warn("\nstack backtrace:\n");
5987 	dump_stack();
5988 
5989 	nbcon_cpu_emergency_exit();
5990 }
5991 
5992 static void
__lock_contended(struct lockdep_map * lock,unsigned long ip)5993 __lock_contended(struct lockdep_map *lock, unsigned long ip)
5994 {
5995 	struct task_struct *curr = current;
5996 	struct held_lock *hlock;
5997 	struct lock_class_stats *stats;
5998 	unsigned int depth;
5999 	int i, contention_point, contending_point;
6000 
6001 	depth = curr->lockdep_depth;
6002 	/*
6003 	 * Whee, we contended on this lock, except it seems we're not
6004 	 * actually trying to acquire anything much at all..
6005 	 */
6006 	if (DEBUG_LOCKS_WARN_ON(!depth))
6007 		return;
6008 
6009 	if (unlikely(lock->key == &__lockdep_no_track__))
6010 		return;
6011 
6012 	hlock = find_held_lock(curr, lock, depth, &i);
6013 	if (!hlock) {
6014 		print_lock_contention_bug(curr, lock, ip);
6015 		return;
6016 	}
6017 
6018 	if (hlock->instance != lock)
6019 		return;
6020 
6021 	hlock->waittime_stamp = lockstat_clock();
6022 
6023 	contention_point = lock_point(hlock_class(hlock)->contention_point, ip);
6024 	contending_point = lock_point(hlock_class(hlock)->contending_point,
6025 				      lock->ip);
6026 
6027 	stats = get_lock_stats(hlock_class(hlock));
6028 	if (contention_point < LOCKSTAT_POINTS)
6029 		stats->contention_point[contention_point]++;
6030 	if (contending_point < LOCKSTAT_POINTS)
6031 		stats->contending_point[contending_point]++;
6032 	if (lock->cpu != smp_processor_id())
6033 		stats->bounces[bounce_contended + !!hlock->read]++;
6034 }
6035 
6036 static void
__lock_acquired(struct lockdep_map * lock,unsigned long ip)6037 __lock_acquired(struct lockdep_map *lock, unsigned long ip)
6038 {
6039 	struct task_struct *curr = current;
6040 	struct held_lock *hlock;
6041 	struct lock_class_stats *stats;
6042 	unsigned int depth;
6043 	u64 now, waittime = 0;
6044 	int i, cpu;
6045 
6046 	depth = curr->lockdep_depth;
6047 	/*
6048 	 * Yay, we acquired ownership of this lock we didn't try to
6049 	 * acquire, how the heck did that happen?
6050 	 */
6051 	if (DEBUG_LOCKS_WARN_ON(!depth))
6052 		return;
6053 
6054 	if (unlikely(lock->key == &__lockdep_no_track__))
6055 		return;
6056 
6057 	hlock = find_held_lock(curr, lock, depth, &i);
6058 	if (!hlock) {
6059 		print_lock_contention_bug(curr, lock, _RET_IP_);
6060 		return;
6061 	}
6062 
6063 	if (hlock->instance != lock)
6064 		return;
6065 
6066 	cpu = smp_processor_id();
6067 	if (hlock->waittime_stamp) {
6068 		now = lockstat_clock();
6069 		waittime = now - hlock->waittime_stamp;
6070 		hlock->holdtime_stamp = now;
6071 	}
6072 
6073 	stats = get_lock_stats(hlock_class(hlock));
6074 	if (waittime) {
6075 		if (hlock->read)
6076 			lock_time_inc(&stats->read_waittime, waittime);
6077 		else
6078 			lock_time_inc(&stats->write_waittime, waittime);
6079 	}
6080 	if (lock->cpu != cpu)
6081 		stats->bounces[bounce_acquired + !!hlock->read]++;
6082 
6083 	lock->cpu = cpu;
6084 	lock->ip = ip;
6085 }
6086 
lock_contended(struct lockdep_map * lock,unsigned long ip)6087 void lock_contended(struct lockdep_map *lock, unsigned long ip)
6088 {
6089 	unsigned long flags;
6090 
6091 	trace_lock_contended(lock, ip);
6092 
6093 	if (unlikely(!lock_stat || !lockdep_enabled()))
6094 		return;
6095 
6096 	raw_local_irq_save(flags);
6097 	check_flags(flags);
6098 	lockdep_recursion_inc();
6099 	__lock_contended(lock, ip);
6100 	lockdep_recursion_finish();
6101 	raw_local_irq_restore(flags);
6102 }
6103 EXPORT_SYMBOL_GPL(lock_contended);
6104 
lock_acquired(struct lockdep_map * lock,unsigned long ip)6105 void lock_acquired(struct lockdep_map *lock, unsigned long ip)
6106 {
6107 	unsigned long flags;
6108 
6109 	trace_lock_acquired(lock, ip);
6110 
6111 	if (unlikely(!lock_stat || !lockdep_enabled()))
6112 		return;
6113 
6114 	raw_local_irq_save(flags);
6115 	check_flags(flags);
6116 	lockdep_recursion_inc();
6117 	__lock_acquired(lock, ip);
6118 	lockdep_recursion_finish();
6119 	raw_local_irq_restore(flags);
6120 }
6121 EXPORT_SYMBOL_GPL(lock_acquired);
6122 #endif
6123 
6124 /*
6125  * Used by the testsuite, sanitize the validator state
6126  * after a simulated failure:
6127  */
6128 
lockdep_reset(void)6129 void lockdep_reset(void)
6130 {
6131 	unsigned long flags;
6132 	int i;
6133 
6134 	raw_local_irq_save(flags);
6135 	lockdep_init_task(current);
6136 	memset(current->held_locks, 0, MAX_LOCK_DEPTH*sizeof(struct held_lock));
6137 	nr_hardirq_chains = 0;
6138 	nr_softirq_chains = 0;
6139 	nr_process_chains = 0;
6140 	debug_locks = 1;
6141 	for (i = 0; i < CHAINHASH_SIZE; i++)
6142 		INIT_HLIST_HEAD(chainhash_table + i);
6143 	raw_local_irq_restore(flags);
6144 }
6145 
6146 /* Remove a class from a lock chain. Must be called with the graph lock held. */
remove_class_from_lock_chain(struct pending_free * pf,struct lock_chain * chain,struct lock_class * class)6147 static void remove_class_from_lock_chain(struct pending_free *pf,
6148 					 struct lock_chain *chain,
6149 					 struct lock_class *class)
6150 {
6151 #ifdef CONFIG_PROVE_LOCKING
6152 	int i;
6153 
6154 	for (i = chain->base; i < chain->base + chain->depth; i++) {
6155 		if (chain_hlock_class_idx(chain_hlocks[i]) != class - lock_classes)
6156 			continue;
6157 		/*
6158 		 * Each lock class occurs at most once in a lock chain so once
6159 		 * we found a match we can break out of this loop.
6160 		 */
6161 		goto free_lock_chain;
6162 	}
6163 	/* Since the chain has not been modified, return. */
6164 	return;
6165 
6166 free_lock_chain:
6167 	free_chain_hlocks(chain->base, chain->depth);
6168 	/* Overwrite the chain key for concurrent RCU readers. */
6169 	WRITE_ONCE(chain->chain_key, INITIAL_CHAIN_KEY);
6170 	dec_chains(chain->irq_context);
6171 
6172 	/*
6173 	 * Note: calling hlist_del_rcu() from inside a
6174 	 * hlist_for_each_entry_rcu() loop is safe.
6175 	 */
6176 	hlist_del_rcu(&chain->entry);
6177 	__set_bit(chain - lock_chains, pf->lock_chains_being_freed);
6178 	nr_zapped_lock_chains++;
6179 #endif
6180 }
6181 
6182 /* Must be called with the graph lock held. */
remove_class_from_lock_chains(struct pending_free * pf,struct lock_class * class)6183 static void remove_class_from_lock_chains(struct pending_free *pf,
6184 					  struct lock_class *class)
6185 {
6186 	struct lock_chain *chain;
6187 	struct hlist_head *head;
6188 	int i;
6189 
6190 	for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
6191 		head = chainhash_table + i;
6192 		hlist_for_each_entry_rcu(chain, head, entry) {
6193 			remove_class_from_lock_chain(pf, chain, class);
6194 		}
6195 	}
6196 }
6197 
6198 /*
6199  * Remove all references to a lock class. The caller must hold the graph lock.
6200  */
zap_class(struct pending_free * pf,struct lock_class * class)6201 static void zap_class(struct pending_free *pf, struct lock_class *class)
6202 {
6203 	struct lock_list *entry;
6204 	int i;
6205 
6206 	WARN_ON_ONCE(!class->key);
6207 
6208 	/*
6209 	 * Remove all dependencies this lock is
6210 	 * involved in:
6211 	 */
6212 	for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
6213 		entry = list_entries + i;
6214 		if (entry->class != class && entry->links_to != class)
6215 			continue;
6216 		__clear_bit(i, list_entries_in_use);
6217 		nr_list_entries--;
6218 		list_del_rcu(&entry->entry);
6219 	}
6220 	if (list_empty(&class->locks_after) &&
6221 	    list_empty(&class->locks_before)) {
6222 		list_move_tail(&class->lock_entry, &pf->zapped);
6223 		hlist_del_rcu(&class->hash_entry);
6224 		WRITE_ONCE(class->key, NULL);
6225 		WRITE_ONCE(class->name, NULL);
6226 		nr_lock_classes--;
6227 		__clear_bit(class - lock_classes, lock_classes_in_use);
6228 		if (class - lock_classes == max_lock_class_idx)
6229 			max_lock_class_idx--;
6230 	} else {
6231 		WARN_ONCE(true, "%s() failed for class %s\n", __func__,
6232 			  class->name);
6233 	}
6234 
6235 	remove_class_from_lock_chains(pf, class);
6236 	nr_zapped_classes++;
6237 }
6238 
reinit_class(struct lock_class * class)6239 static void reinit_class(struct lock_class *class)
6240 {
6241 	WARN_ON_ONCE(!class->lock_entry.next);
6242 	WARN_ON_ONCE(!list_empty(&class->locks_after));
6243 	WARN_ON_ONCE(!list_empty(&class->locks_before));
6244 	memset_startat(class, 0, key);
6245 	WARN_ON_ONCE(!class->lock_entry.next);
6246 	WARN_ON_ONCE(!list_empty(&class->locks_after));
6247 	WARN_ON_ONCE(!list_empty(&class->locks_before));
6248 }
6249 
within(const void * addr,void * start,unsigned long size)6250 static inline int within(const void *addr, void *start, unsigned long size)
6251 {
6252 	return addr >= start && addr < start + size;
6253 }
6254 
inside_selftest(void)6255 static bool inside_selftest(void)
6256 {
6257 	return current == lockdep_selftest_task_struct;
6258 }
6259 
6260 /* The caller must hold the graph lock. */
get_pending_free(void)6261 static struct pending_free *get_pending_free(void)
6262 {
6263 	return delayed_free.pf + delayed_free.index;
6264 }
6265 
6266 static void free_zapped_rcu(struct rcu_head *cb);
6267 
6268 /*
6269 * See if we need to queue an RCU callback, must called with
6270 * the lockdep lock held, returns false if either we don't have
6271 * any pending free or the callback is already scheduled.
6272 * Otherwise, a call_rcu() must follow this function call.
6273 */
prepare_call_rcu_zapped(struct pending_free * pf)6274 static bool prepare_call_rcu_zapped(struct pending_free *pf)
6275 {
6276 	WARN_ON_ONCE(inside_selftest());
6277 
6278 	if (list_empty(&pf->zapped))
6279 		return false;
6280 
6281 	if (delayed_free.scheduled)
6282 		return false;
6283 
6284 	delayed_free.scheduled = true;
6285 
6286 	WARN_ON_ONCE(delayed_free.pf + delayed_free.index != pf);
6287 	delayed_free.index ^= 1;
6288 
6289 	return true;
6290 }
6291 
6292 /* The caller must hold the graph lock. May be called from RCU context. */
__free_zapped_classes(struct pending_free * pf)6293 static void __free_zapped_classes(struct pending_free *pf)
6294 {
6295 	struct lock_class *class;
6296 
6297 	check_data_structures();
6298 
6299 	list_for_each_entry(class, &pf->zapped, lock_entry)
6300 		reinit_class(class);
6301 
6302 	list_splice_init(&pf->zapped, &free_lock_classes);
6303 
6304 #ifdef CONFIG_PROVE_LOCKING
6305 	bitmap_andnot(lock_chains_in_use, lock_chains_in_use,
6306 		      pf->lock_chains_being_freed, ARRAY_SIZE(lock_chains));
6307 	bitmap_clear(pf->lock_chains_being_freed, 0, ARRAY_SIZE(lock_chains));
6308 #endif
6309 }
6310 
free_zapped_rcu(struct rcu_head * ch)6311 static void free_zapped_rcu(struct rcu_head *ch)
6312 {
6313 	struct pending_free *pf;
6314 	unsigned long flags;
6315 	bool need_callback;
6316 
6317 	if (WARN_ON_ONCE(ch != &delayed_free.rcu_head))
6318 		return;
6319 
6320 	raw_local_irq_save(flags);
6321 	lockdep_lock();
6322 
6323 	/* closed head */
6324 	pf = delayed_free.pf + (delayed_free.index ^ 1);
6325 	__free_zapped_classes(pf);
6326 	delayed_free.scheduled = false;
6327 	need_callback =
6328 		prepare_call_rcu_zapped(delayed_free.pf + delayed_free.index);
6329 	lockdep_unlock();
6330 	raw_local_irq_restore(flags);
6331 
6332 	/*
6333 	* If there's pending free and its callback has not been scheduled,
6334 	* queue an RCU callback.
6335 	*/
6336 	if (need_callback)
6337 		call_rcu(&delayed_free.rcu_head, free_zapped_rcu);
6338 
6339 }
6340 
6341 /*
6342  * Remove all lock classes from the class hash table and from the
6343  * all_lock_classes list whose key or name is in the address range [start,
6344  * start + size). Move these lock classes to the zapped_classes list. Must
6345  * be called with the graph lock held.
6346  */
__lockdep_free_key_range(struct pending_free * pf,void * start,unsigned long size)6347 static void __lockdep_free_key_range(struct pending_free *pf, void *start,
6348 				     unsigned long size)
6349 {
6350 	struct lock_class *class;
6351 	struct hlist_head *head;
6352 	int i;
6353 
6354 	/* Unhash all classes that were created by a module. */
6355 	for (i = 0; i < CLASSHASH_SIZE; i++) {
6356 		head = classhash_table + i;
6357 		hlist_for_each_entry_rcu(class, head, hash_entry) {
6358 			if (!within(class->key, start, size) &&
6359 			    !within(class->name, start, size))
6360 				continue;
6361 			zap_class(pf, class);
6362 		}
6363 	}
6364 }
6365 
6366 /*
6367  * Used in module.c to remove lock classes from memory that is going to be
6368  * freed; and possibly re-used by other modules.
6369  *
6370  * We will have had one synchronize_rcu() before getting here, so we're
6371  * guaranteed nobody will look up these exact classes -- they're properly dead
6372  * but still allocated.
6373  */
lockdep_free_key_range_reg(void * start,unsigned long size)6374 static void lockdep_free_key_range_reg(void *start, unsigned long size)
6375 {
6376 	struct pending_free *pf;
6377 	unsigned long flags;
6378 	bool need_callback;
6379 
6380 	init_data_structures_once();
6381 
6382 	raw_local_irq_save(flags);
6383 	lockdep_lock();
6384 	pf = get_pending_free();
6385 	__lockdep_free_key_range(pf, start, size);
6386 	need_callback = prepare_call_rcu_zapped(pf);
6387 	lockdep_unlock();
6388 	raw_local_irq_restore(flags);
6389 	if (need_callback)
6390 		call_rcu(&delayed_free.rcu_head, free_zapped_rcu);
6391 	/*
6392 	 * Wait for any possible iterators from look_up_lock_class() to pass
6393 	 * before continuing to free the memory they refer to.
6394 	 */
6395 	synchronize_rcu();
6396 }
6397 
6398 /*
6399  * Free all lockdep keys in the range [start, start+size). Does not sleep.
6400  * Ignores debug_locks. Must only be used by the lockdep selftests.
6401  */
lockdep_free_key_range_imm(void * start,unsigned long size)6402 static void lockdep_free_key_range_imm(void *start, unsigned long size)
6403 {
6404 	struct pending_free *pf = delayed_free.pf;
6405 	unsigned long flags;
6406 
6407 	init_data_structures_once();
6408 
6409 	raw_local_irq_save(flags);
6410 	lockdep_lock();
6411 	__lockdep_free_key_range(pf, start, size);
6412 	__free_zapped_classes(pf);
6413 	lockdep_unlock();
6414 	raw_local_irq_restore(flags);
6415 }
6416 
lockdep_free_key_range(void * start,unsigned long size)6417 void lockdep_free_key_range(void *start, unsigned long size)
6418 {
6419 	init_data_structures_once();
6420 
6421 	if (inside_selftest())
6422 		lockdep_free_key_range_imm(start, size);
6423 	else
6424 		lockdep_free_key_range_reg(start, size);
6425 }
6426 
6427 /*
6428  * Check whether any element of the @lock->class_cache[] array refers to a
6429  * registered lock class. The caller must hold either the graph lock or the
6430  * RCU read lock.
6431  */
lock_class_cache_is_registered(struct lockdep_map * lock)6432 static bool lock_class_cache_is_registered(struct lockdep_map *lock)
6433 {
6434 	struct lock_class *class;
6435 	struct hlist_head *head;
6436 	int i, j;
6437 
6438 	for (i = 0; i < CLASSHASH_SIZE; i++) {
6439 		head = classhash_table + i;
6440 		hlist_for_each_entry_rcu(class, head, hash_entry) {
6441 			for (j = 0; j < NR_LOCKDEP_CACHING_CLASSES; j++)
6442 				if (lock->class_cache[j] == class)
6443 					return true;
6444 		}
6445 	}
6446 	return false;
6447 }
6448 
6449 /* The caller must hold the graph lock. Does not sleep. */
__lockdep_reset_lock(struct pending_free * pf,struct lockdep_map * lock)6450 static void __lockdep_reset_lock(struct pending_free *pf,
6451 				 struct lockdep_map *lock)
6452 {
6453 	struct lock_class *class;
6454 	int j;
6455 
6456 	/*
6457 	 * Remove all classes this lock might have:
6458 	 */
6459 	for (j = 0; j < MAX_LOCKDEP_SUBCLASSES; j++) {
6460 		/*
6461 		 * If the class exists we look it up and zap it:
6462 		 */
6463 		class = look_up_lock_class(lock, j);
6464 		if (class)
6465 			zap_class(pf, class);
6466 	}
6467 	/*
6468 	 * Debug check: in the end all mapped classes should
6469 	 * be gone.
6470 	 */
6471 	if (WARN_ON_ONCE(lock_class_cache_is_registered(lock)))
6472 		debug_locks_off();
6473 }
6474 
6475 /*
6476  * Remove all information lockdep has about a lock if debug_locks == 1. Free
6477  * released data structures from RCU context.
6478  */
lockdep_reset_lock_reg(struct lockdep_map * lock)6479 static void lockdep_reset_lock_reg(struct lockdep_map *lock)
6480 {
6481 	struct pending_free *pf;
6482 	unsigned long flags;
6483 	int locked;
6484 	bool need_callback = false;
6485 
6486 	raw_local_irq_save(flags);
6487 	locked = graph_lock();
6488 	if (!locked)
6489 		goto out_irq;
6490 
6491 	pf = get_pending_free();
6492 	__lockdep_reset_lock(pf, lock);
6493 	need_callback = prepare_call_rcu_zapped(pf);
6494 
6495 	graph_unlock();
6496 out_irq:
6497 	raw_local_irq_restore(flags);
6498 	if (need_callback)
6499 		call_rcu(&delayed_free.rcu_head, free_zapped_rcu);
6500 }
6501 
6502 /*
6503  * Reset a lock. Does not sleep. Ignores debug_locks. Must only be used by the
6504  * lockdep selftests.
6505  */
lockdep_reset_lock_imm(struct lockdep_map * lock)6506 static void lockdep_reset_lock_imm(struct lockdep_map *lock)
6507 {
6508 	struct pending_free *pf = delayed_free.pf;
6509 	unsigned long flags;
6510 
6511 	raw_local_irq_save(flags);
6512 	lockdep_lock();
6513 	__lockdep_reset_lock(pf, lock);
6514 	__free_zapped_classes(pf);
6515 	lockdep_unlock();
6516 	raw_local_irq_restore(flags);
6517 }
6518 
lockdep_reset_lock(struct lockdep_map * lock)6519 void lockdep_reset_lock(struct lockdep_map *lock)
6520 {
6521 	init_data_structures_once();
6522 
6523 	if (inside_selftest())
6524 		lockdep_reset_lock_imm(lock);
6525 	else
6526 		lockdep_reset_lock_reg(lock);
6527 }
6528 
6529 /*
6530  * Unregister a dynamically allocated key.
6531  *
6532  * Unlike lockdep_register_key(), a search is always done to find a matching
6533  * key irrespective of debug_locks to avoid potential invalid access to freed
6534  * memory in lock_class entry.
6535  */
lockdep_unregister_key(struct lock_class_key * key)6536 void lockdep_unregister_key(struct lock_class_key *key)
6537 {
6538 	struct hlist_head *hash_head = keyhashentry(key);
6539 	struct lock_class_key *k;
6540 	struct pending_free *pf;
6541 	unsigned long flags;
6542 	bool found = false;
6543 	bool need_callback = false;
6544 
6545 	might_sleep();
6546 
6547 	if (WARN_ON_ONCE(static_obj(key)))
6548 		return;
6549 
6550 	raw_local_irq_save(flags);
6551 	lockdep_lock();
6552 
6553 	hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
6554 		if (k == key) {
6555 			hlist_del_rcu(&k->hash_entry);
6556 			found = true;
6557 			break;
6558 		}
6559 	}
6560 	WARN_ON_ONCE(!found && debug_locks);
6561 	if (found) {
6562 		pf = get_pending_free();
6563 		__lockdep_free_key_range(pf, key, 1);
6564 		need_callback = prepare_call_rcu_zapped(pf);
6565 	}
6566 	lockdep_unlock();
6567 	raw_local_irq_restore(flags);
6568 
6569 	if (need_callback)
6570 		call_rcu(&delayed_free.rcu_head, free_zapped_rcu);
6571 
6572 	/* Wait until is_dynamic_key() has finished accessing k->hash_entry. */
6573 	synchronize_rcu();
6574 }
6575 EXPORT_SYMBOL_GPL(lockdep_unregister_key);
6576 
lockdep_init(void)6577 void __init lockdep_init(void)
6578 {
6579 	printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");
6580 
6581 	printk("... MAX_LOCKDEP_SUBCLASSES:  %lu\n", MAX_LOCKDEP_SUBCLASSES);
6582 	printk("... MAX_LOCK_DEPTH:          %lu\n", MAX_LOCK_DEPTH);
6583 	printk("... MAX_LOCKDEP_KEYS:        %lu\n", MAX_LOCKDEP_KEYS);
6584 	printk("... CLASSHASH_SIZE:          %lu\n", CLASSHASH_SIZE);
6585 	printk("... MAX_LOCKDEP_ENTRIES:     %lu\n", MAX_LOCKDEP_ENTRIES);
6586 	printk("... MAX_LOCKDEP_CHAINS:      %lu\n", MAX_LOCKDEP_CHAINS);
6587 	printk("... CHAINHASH_SIZE:          %lu\n", CHAINHASH_SIZE);
6588 
6589 	printk(" memory used by lock dependency info: %zu kB\n",
6590 	       (sizeof(lock_classes) +
6591 		sizeof(lock_classes_in_use) +
6592 		sizeof(classhash_table) +
6593 		sizeof(list_entries) +
6594 		sizeof(list_entries_in_use) +
6595 		sizeof(chainhash_table) +
6596 		sizeof(delayed_free)
6597 #ifdef CONFIG_PROVE_LOCKING
6598 		+ sizeof(lock_cq)
6599 		+ sizeof(lock_chains)
6600 		+ sizeof(lock_chains_in_use)
6601 		+ sizeof(chain_hlocks)
6602 #endif
6603 		) / 1024
6604 		);
6605 
6606 #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
6607 	printk(" memory used for stack traces: %zu kB\n",
6608 	       (sizeof(stack_trace) + sizeof(stack_trace_hash)) / 1024
6609 	       );
6610 #endif
6611 
6612 	printk(" per task-struct memory footprint: %zu bytes\n",
6613 	       sizeof(((struct task_struct *)NULL)->held_locks));
6614 }
6615 
6616 static void
print_freed_lock_bug(struct task_struct * curr,const void * mem_from,const void * mem_to,struct held_lock * hlock)6617 print_freed_lock_bug(struct task_struct *curr, const void *mem_from,
6618 		     const void *mem_to, struct held_lock *hlock)
6619 {
6620 	if (!debug_locks_off())
6621 		return;
6622 	if (debug_locks_silent)
6623 		return;
6624 
6625 	nbcon_cpu_emergency_enter();
6626 
6627 	pr_warn("\n");
6628 	pr_warn("=========================\n");
6629 	pr_warn("WARNING: held lock freed!\n");
6630 	print_kernel_ident();
6631 	pr_warn("-------------------------\n");
6632 	pr_warn("%s/%d is freeing memory %px-%px, with a lock still held there!\n",
6633 		curr->comm, task_pid_nr(curr), mem_from, mem_to-1);
6634 	print_lock(hlock);
6635 	lockdep_print_held_locks(curr);
6636 
6637 	pr_warn("\nstack backtrace:\n");
6638 	dump_stack();
6639 
6640 	nbcon_cpu_emergency_exit();
6641 }
6642 
not_in_range(const void * mem_from,unsigned long mem_len,const void * lock_from,unsigned long lock_len)6643 static inline int not_in_range(const void* mem_from, unsigned long mem_len,
6644 				const void* lock_from, unsigned long lock_len)
6645 {
6646 	return lock_from + lock_len <= mem_from ||
6647 		mem_from + mem_len <= lock_from;
6648 }
6649 
6650 /*
6651  * Called when kernel memory is freed (or unmapped), or if a lock
6652  * is destroyed or reinitialized - this code checks whether there is
6653  * any held lock in the memory range of <from> to <to>:
6654  */
debug_check_no_locks_freed(const void * mem_from,unsigned long mem_len)6655 void debug_check_no_locks_freed(const void *mem_from, unsigned long mem_len)
6656 {
6657 	struct task_struct *curr = current;
6658 	struct held_lock *hlock;
6659 	unsigned long flags;
6660 	int i;
6661 
6662 	if (unlikely(!debug_locks))
6663 		return;
6664 
6665 	raw_local_irq_save(flags);
6666 	for (i = 0; i < curr->lockdep_depth; i++) {
6667 		hlock = curr->held_locks + i;
6668 
6669 		if (not_in_range(mem_from, mem_len, hlock->instance,
6670 					sizeof(*hlock->instance)))
6671 			continue;
6672 
6673 		print_freed_lock_bug(curr, mem_from, mem_from + mem_len, hlock);
6674 		break;
6675 	}
6676 	raw_local_irq_restore(flags);
6677 }
6678 EXPORT_SYMBOL_GPL(debug_check_no_locks_freed);
6679 
print_held_locks_bug(void)6680 static void print_held_locks_bug(void)
6681 {
6682 	if (!debug_locks_off())
6683 		return;
6684 	if (debug_locks_silent)
6685 		return;
6686 
6687 	nbcon_cpu_emergency_enter();
6688 
6689 	pr_warn("\n");
6690 	pr_warn("====================================\n");
6691 	pr_warn("WARNING: %s/%d still has locks held!\n",
6692 	       current->comm, task_pid_nr(current));
6693 	print_kernel_ident();
6694 	pr_warn("------------------------------------\n");
6695 	lockdep_print_held_locks(current);
6696 	pr_warn("\nstack backtrace:\n");
6697 	dump_stack();
6698 
6699 	nbcon_cpu_emergency_exit();
6700 }
6701 
debug_check_no_locks_held(void)6702 void debug_check_no_locks_held(void)
6703 {
6704 	if (unlikely(current->lockdep_depth > 0))
6705 		print_held_locks_bug();
6706 }
6707 EXPORT_SYMBOL_GPL(debug_check_no_locks_held);
6708 
6709 #ifdef __KERNEL__
debug_show_all_locks(void)6710 void debug_show_all_locks(void)
6711 {
6712 	struct task_struct *g, *p;
6713 
6714 	if (unlikely(!debug_locks)) {
6715 		pr_warn("INFO: lockdep is turned off.\n");
6716 		return;
6717 	}
6718 	pr_warn("\nShowing all locks held in the system:\n");
6719 
6720 	rcu_read_lock();
6721 	for_each_process_thread(g, p) {
6722 		if (!p->lockdep_depth)
6723 			continue;
6724 		lockdep_print_held_locks(p);
6725 		touch_nmi_watchdog();
6726 		touch_all_softlockup_watchdogs();
6727 	}
6728 	rcu_read_unlock();
6729 
6730 	pr_warn("\n");
6731 	pr_warn("=============================================\n\n");
6732 }
6733 EXPORT_SYMBOL_GPL(debug_show_all_locks);
6734 #endif
6735 
6736 /*
6737  * Careful: only use this function if you are sure that
6738  * the task cannot run in parallel!
6739  */
debug_show_held_locks(struct task_struct * task)6740 void debug_show_held_locks(struct task_struct *task)
6741 {
6742 	if (unlikely(!debug_locks)) {
6743 		printk("INFO: lockdep is turned off.\n");
6744 		return;
6745 	}
6746 	lockdep_print_held_locks(task);
6747 }
6748 EXPORT_SYMBOL_GPL(debug_show_held_locks);
6749 
lockdep_sys_exit(void)6750 asmlinkage __visible void lockdep_sys_exit(void)
6751 {
6752 	struct task_struct *curr = current;
6753 
6754 	if (unlikely(curr->lockdep_depth)) {
6755 		if (!debug_locks_off())
6756 			return;
6757 		nbcon_cpu_emergency_enter();
6758 		pr_warn("\n");
6759 		pr_warn("================================================\n");
6760 		pr_warn("WARNING: lock held when returning to user space!\n");
6761 		print_kernel_ident();
6762 		pr_warn("------------------------------------------------\n");
6763 		pr_warn("%s/%d is leaving the kernel with locks still held!\n",
6764 				curr->comm, curr->pid);
6765 		lockdep_print_held_locks(curr);
6766 		nbcon_cpu_emergency_exit();
6767 	}
6768 
6769 	/*
6770 	 * The lock history for each syscall should be independent. So wipe the
6771 	 * slate clean on return to userspace.
6772 	 */
6773 	lockdep_invariant_state(false);
6774 }
6775 
lockdep_rcu_suspicious(const char * file,const int line,const char * s)6776 void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
6777 {
6778 	struct task_struct *curr = current;
6779 	int dl = READ_ONCE(debug_locks);
6780 	bool rcu = warn_rcu_enter();
6781 
6782 	/* Note: the following can be executed concurrently, so be careful. */
6783 	nbcon_cpu_emergency_enter();
6784 	pr_warn("\n");
6785 	pr_warn("=============================\n");
6786 	pr_warn("WARNING: suspicious RCU usage\n");
6787 	print_kernel_ident();
6788 	pr_warn("-----------------------------\n");
6789 	pr_warn("%s:%d %s!\n", file, line, s);
6790 	pr_warn("\nother info that might help us debug this:\n\n");
6791 	pr_warn("\n%srcu_scheduler_active = %d, debug_locks = %d\n%s",
6792 	       !rcu_lockdep_current_cpu_online()
6793 			? "RCU used illegally from offline CPU!\n"
6794 			: "",
6795 	       rcu_scheduler_active, dl,
6796 	       dl ? "" : "Possible false positive due to lockdep disabling via debug_locks = 0\n");
6797 
6798 	/*
6799 	 * If a CPU is in the RCU-free window in idle (ie: in the section
6800 	 * between ct_idle_enter() and ct_idle_exit(), then RCU
6801 	 * considers that CPU to be in an "extended quiescent state",
6802 	 * which means that RCU will be completely ignoring that CPU.
6803 	 * Therefore, rcu_read_lock() and friends have absolutely no
6804 	 * effect on a CPU running in that state. In other words, even if
6805 	 * such an RCU-idle CPU has called rcu_read_lock(), RCU might well
6806 	 * delete data structures out from under it.  RCU really has no
6807 	 * choice here: we need to keep an RCU-free window in idle where
6808 	 * the CPU may possibly enter into low power mode. This way we can
6809 	 * notice an extended quiescent state to other CPUs that started a grace
6810 	 * period. Otherwise we would delay any grace period as long as we run
6811 	 * in the idle task.
6812 	 *
6813 	 * So complain bitterly if someone does call rcu_read_lock(),
6814 	 * rcu_read_lock_bh() and so on from extended quiescent states.
6815 	 */
6816 	if (!rcu_is_watching())
6817 		pr_warn("RCU used illegally from extended quiescent state!\n");
6818 
6819 	lockdep_print_held_locks(curr);
6820 	pr_warn("\nstack backtrace:\n");
6821 	dump_stack();
6822 	nbcon_cpu_emergency_exit();
6823 	warn_rcu_exit(rcu);
6824 }
6825 EXPORT_SYMBOL_GPL(lockdep_rcu_suspicious);
6826