Merge branch 'locking-core-for-linus' of git://git.kernel.org/pub/scm/linux/kernel...
[sfrench/cifs-2.6.git] / kernel / locking / lockdep.c
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
58 #include <asm/sections.h>
59
60 #include "lockdep_internals.h"
61
62 #define CREATE_TRACE_POINTS
63 #include <trace/events/lock.h>
64
65 #ifdef CONFIG_PROVE_LOCKING
66 int prove_locking = 1;
67 module_param(prove_locking, int, 0644);
68 #else
69 #define prove_locking 0
70 #endif
71
72 #ifdef CONFIG_LOCK_STAT
73 int lock_stat = 1;
74 module_param(lock_stat, int, 0644);
75 #else
76 #define lock_stat 0
77 #endif
78
79 /*
80  * lockdep_lock: protects the lockdep graph, the hashes and the
81  *               class/list/hash allocators.
82  *
83  * This is one of the rare exceptions where it's justified
84  * to use a raw spinlock - we really dont want the spinlock
85  * code to recurse back into the lockdep code...
86  */
87 static arch_spinlock_t lockdep_lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;
88 static struct task_struct *lockdep_selftest_task_struct;
89
90 static int graph_lock(void)
91 {
92         arch_spin_lock(&lockdep_lock);
93         /*
94          * Make sure that if another CPU detected a bug while
95          * walking the graph we dont change it (while the other
96          * CPU is busy printing out stuff with the graph lock
97          * dropped already)
98          */
99         if (!debug_locks) {
100                 arch_spin_unlock(&lockdep_lock);
101                 return 0;
102         }
103         /* prevent any recursions within lockdep from causing deadlocks */
104         current->lockdep_recursion++;
105         return 1;
106 }
107
108 static inline int graph_unlock(void)
109 {
110         if (debug_locks && !arch_spin_is_locked(&lockdep_lock)) {
111                 /*
112                  * The lockdep graph lock isn't locked while we expect it to
113                  * be, we're confused now, bye!
114                  */
115                 return DEBUG_LOCKS_WARN_ON(1);
116         }
117
118         current->lockdep_recursion--;
119         arch_spin_unlock(&lockdep_lock);
120         return 0;
121 }
122
123 /*
124  * Turn lock debugging off and return with 0 if it was off already,
125  * and also release the graph lock:
126  */
127 static inline int debug_locks_off_graph_unlock(void)
128 {
129         int ret = debug_locks_off();
130
131         arch_spin_unlock(&lockdep_lock);
132
133         return ret;
134 }
135
136 unsigned long nr_list_entries;
137 static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
138 static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);
139
140 /*
141  * All data structures here are protected by the global debug_lock.
142  *
143  * nr_lock_classes is the number of elements of lock_classes[] that is
144  * in use.
145  */
146 #define KEYHASH_BITS            (MAX_LOCKDEP_KEYS_BITS - 1)
147 #define KEYHASH_SIZE            (1UL << KEYHASH_BITS)
148 static struct hlist_head lock_keys_hash[KEYHASH_SIZE];
149 unsigned long nr_lock_classes;
150 #ifndef CONFIG_DEBUG_LOCKDEP
151 static
152 #endif
153 struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
154 static DECLARE_BITMAP(lock_classes_in_use, MAX_LOCKDEP_KEYS);
155
156 static inline struct lock_class *hlock_class(struct held_lock *hlock)
157 {
158         unsigned int class_idx = hlock->class_idx;
159
160         /* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfield */
161         barrier();
162
163         if (!test_bit(class_idx, lock_classes_in_use)) {
164                 /*
165                  * Someone passed in garbage, we give up.
166                  */
167                 DEBUG_LOCKS_WARN_ON(1);
168                 return NULL;
169         }
170
171         /*
172          * At this point, if the passed hlock->class_idx is still garbage,
173          * we just have to live with it
174          */
175         return lock_classes + class_idx;
176 }
177
178 #ifdef CONFIG_LOCK_STAT
179 static DEFINE_PER_CPU(struct lock_class_stats[MAX_LOCKDEP_KEYS], cpu_lock_stats);
180
181 static inline u64 lockstat_clock(void)
182 {
183         return local_clock();
184 }
185
186 static int lock_point(unsigned long points[], unsigned long ip)
187 {
188         int i;
189
190         for (i = 0; i < LOCKSTAT_POINTS; i++) {
191                 if (points[i] == 0) {
192                         points[i] = ip;
193                         break;
194                 }
195                 if (points[i] == ip)
196                         break;
197         }
198
199         return i;
200 }
201
202 static void lock_time_inc(struct lock_time *lt, u64 time)
203 {
204         if (time > lt->max)
205                 lt->max = time;
206
207         if (time < lt->min || !lt->nr)
208                 lt->min = time;
209
210         lt->total += time;
211         lt->nr++;
212 }
213
214 static inline void lock_time_add(struct lock_time *src, struct lock_time *dst)
215 {
216         if (!src->nr)
217                 return;
218
219         if (src->max > dst->max)
220                 dst->max = src->max;
221
222         if (src->min < dst->min || !dst->nr)
223                 dst->min = src->min;
224
225         dst->total += src->total;
226         dst->nr += src->nr;
227 }
228
229 struct lock_class_stats lock_stats(struct lock_class *class)
230 {
231         struct lock_class_stats stats;
232         int cpu, i;
233
234         memset(&stats, 0, sizeof(struct lock_class_stats));
235         for_each_possible_cpu(cpu) {
236                 struct lock_class_stats *pcs =
237                         &per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
238
239                 for (i = 0; i < ARRAY_SIZE(stats.contention_point); i++)
240                         stats.contention_point[i] += pcs->contention_point[i];
241
242                 for (i = 0; i < ARRAY_SIZE(stats.contending_point); i++)
243                         stats.contending_point[i] += pcs->contending_point[i];
244
245                 lock_time_add(&pcs->read_waittime, &stats.read_waittime);
246                 lock_time_add(&pcs->write_waittime, &stats.write_waittime);
247
248                 lock_time_add(&pcs->read_holdtime, &stats.read_holdtime);
249                 lock_time_add(&pcs->write_holdtime, &stats.write_holdtime);
250
251                 for (i = 0; i < ARRAY_SIZE(stats.bounces); i++)
252                         stats.bounces[i] += pcs->bounces[i];
253         }
254
255         return stats;
256 }
257
258 void clear_lock_stats(struct lock_class *class)
259 {
260         int cpu;
261
262         for_each_possible_cpu(cpu) {
263                 struct lock_class_stats *cpu_stats =
264                         &per_cpu(cpu_lock_stats, cpu)[class - lock_classes];
265
266                 memset(cpu_stats, 0, sizeof(struct lock_class_stats));
267         }
268         memset(class->contention_point, 0, sizeof(class->contention_point));
269         memset(class->contending_point, 0, sizeof(class->contending_point));
270 }
271
272 static struct lock_class_stats *get_lock_stats(struct lock_class *class)
273 {
274         return &this_cpu_ptr(cpu_lock_stats)[class - lock_classes];
275 }
276
277 static void lock_release_holdtime(struct held_lock *hlock)
278 {
279         struct lock_class_stats *stats;
280         u64 holdtime;
281
282         if (!lock_stat)
283                 return;
284
285         holdtime = lockstat_clock() - hlock->holdtime_stamp;
286
287         stats = get_lock_stats(hlock_class(hlock));
288         if (hlock->read)
289                 lock_time_inc(&stats->read_holdtime, holdtime);
290         else
291                 lock_time_inc(&stats->write_holdtime, holdtime);
292 }
293 #else
294 static inline void lock_release_holdtime(struct held_lock *hlock)
295 {
296 }
297 #endif
298
299 /*
300  * We keep a global list of all lock classes. The list is only accessed with
301  * the lockdep spinlock lock held. free_lock_classes is a list with free
302  * elements. These elements are linked together by the lock_entry member in
303  * struct lock_class.
304  */
305 LIST_HEAD(all_lock_classes);
306 static LIST_HEAD(free_lock_classes);
307
308 /**
309  * struct pending_free - information about data structures about to be freed
310  * @zapped: Head of a list with struct lock_class elements.
311  * @lock_chains_being_freed: Bitmap that indicates which lock_chains[] elements
312  *      are about to be freed.
313  */
314 struct pending_free {
315         struct list_head zapped;
316         DECLARE_BITMAP(lock_chains_being_freed, MAX_LOCKDEP_CHAINS);
317 };
318
319 /**
320  * struct delayed_free - data structures used for delayed freeing
321  *
322  * A data structure for delayed freeing of data structures that may be
323  * accessed by RCU readers at the time these were freed.
324  *
325  * @rcu_head:  Used to schedule an RCU callback for freeing data structures.
326  * @index:     Index of @pf to which freed data structures are added.
327  * @scheduled: Whether or not an RCU callback has been scheduled.
328  * @pf:        Array with information about data structures about to be freed.
329  */
330 static struct delayed_free {
331         struct rcu_head         rcu_head;
332         int                     index;
333         int                     scheduled;
334         struct pending_free     pf[2];
335 } delayed_free;
336
337 /*
338  * The lockdep classes are in a hash-table as well, for fast lookup:
339  */
340 #define CLASSHASH_BITS          (MAX_LOCKDEP_KEYS_BITS - 1)
341 #define CLASSHASH_SIZE          (1UL << CLASSHASH_BITS)
342 #define __classhashfn(key)      hash_long((unsigned long)key, CLASSHASH_BITS)
343 #define classhashentry(key)     (classhash_table + __classhashfn((key)))
344
345 static struct hlist_head classhash_table[CLASSHASH_SIZE];
346
347 /*
348  * We put the lock dependency chains into a hash-table as well, to cache
349  * their existence:
350  */
351 #define CHAINHASH_BITS          (MAX_LOCKDEP_CHAINS_BITS-1)
352 #define CHAINHASH_SIZE          (1UL << CHAINHASH_BITS)
353 #define __chainhashfn(chain)    hash_long(chain, CHAINHASH_BITS)
354 #define chainhashentry(chain)   (chainhash_table + __chainhashfn((chain)))
355
356 static struct hlist_head chainhash_table[CHAINHASH_SIZE];
357
358 /*
359  * The hash key of the lock dependency chains is a hash itself too:
360  * it's a hash of all locks taken up to that lock, including that lock.
361  * It's a 64-bit hash, because it's important for the keys to be
362  * unique.
363  */
364 static inline u64 iterate_chain_key(u64 key, u32 idx)
365 {
366         u32 k0 = key, k1 = key >> 32;
367
368         __jhash_mix(idx, k0, k1); /* Macro that modifies arguments! */
369
370         return k0 | (u64)k1 << 32;
371 }
372
373 void lockdep_init_task(struct task_struct *task)
374 {
375         task->lockdep_depth = 0; /* no locks held yet */
376         task->curr_chain_key = INITIAL_CHAIN_KEY;
377         task->lockdep_recursion = 0;
378 }
379
380 void lockdep_off(void)
381 {
382         current->lockdep_recursion++;
383 }
384 EXPORT_SYMBOL(lockdep_off);
385
386 void lockdep_on(void)
387 {
388         current->lockdep_recursion--;
389 }
390 EXPORT_SYMBOL(lockdep_on);
391
392 void lockdep_set_selftest_task(struct task_struct *task)
393 {
394         lockdep_selftest_task_struct = task;
395 }
396
397 /*
398  * Debugging switches:
399  */
400
401 #define VERBOSE                 0
402 #define VERY_VERBOSE            0
403
404 #if VERBOSE
405 # define HARDIRQ_VERBOSE        1
406 # define SOFTIRQ_VERBOSE        1
407 #else
408 # define HARDIRQ_VERBOSE        0
409 # define SOFTIRQ_VERBOSE        0
410 #endif
411
412 #if VERBOSE || HARDIRQ_VERBOSE || SOFTIRQ_VERBOSE
413 /*
414  * Quick filtering for interesting events:
415  */
416 static int class_filter(struct lock_class *class)
417 {
418 #if 0
419         /* Example */
420         if (class->name_version == 1 &&
421                         !strcmp(class->name, "lockname"))
422                 return 1;
423         if (class->name_version == 1 &&
424                         !strcmp(class->name, "&struct->lockfield"))
425                 return 1;
426 #endif
427         /* Filter everything else. 1 would be to allow everything else */
428         return 0;
429 }
430 #endif
431
432 static int verbose(struct lock_class *class)
433 {
434 #if VERBOSE
435         return class_filter(class);
436 #endif
437         return 0;
438 }
439
440 static void print_lockdep_off(const char *bug_msg)
441 {
442         printk(KERN_DEBUG "%s\n", bug_msg);
443         printk(KERN_DEBUG "turning off the locking correctness validator.\n");
444 #ifdef CONFIG_LOCK_STAT
445         printk(KERN_DEBUG "Please attach the output of /proc/lock_stat to the bug report\n");
446 #endif
447 }
448
449 unsigned long nr_stack_trace_entries;
450
451 #ifdef CONFIG_PROVE_LOCKING
452 /**
453  * struct lock_trace - single stack backtrace
454  * @hash_entry: Entry in a stack_trace_hash[] list.
455  * @hash:       jhash() of @entries.
456  * @nr_entries: Number of entries in @entries.
457  * @entries:    Actual stack backtrace.
458  */
459 struct lock_trace {
460         struct hlist_node       hash_entry;
461         u32                     hash;
462         u32                     nr_entries;
463         unsigned long           entries[0] __aligned(sizeof(unsigned long));
464 };
465 #define LOCK_TRACE_SIZE_IN_LONGS                                \
466         (sizeof(struct lock_trace) / sizeof(unsigned long))
467 /*
468  * Stack-trace: sequence of lock_trace structures. Protected by the graph_lock.
469  */
470 static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES];
471 static struct hlist_head stack_trace_hash[STACK_TRACE_HASH_SIZE];
472
473 static bool traces_identical(struct lock_trace *t1, struct lock_trace *t2)
474 {
475         return t1->hash == t2->hash && t1->nr_entries == t2->nr_entries &&
476                 memcmp(t1->entries, t2->entries,
477                        t1->nr_entries * sizeof(t1->entries[0])) == 0;
478 }
479
480 static struct lock_trace *save_trace(void)
481 {
482         struct lock_trace *trace, *t2;
483         struct hlist_head *hash_head;
484         u32 hash;
485         unsigned int max_entries;
486
487         BUILD_BUG_ON_NOT_POWER_OF_2(STACK_TRACE_HASH_SIZE);
488         BUILD_BUG_ON(LOCK_TRACE_SIZE_IN_LONGS >= MAX_STACK_TRACE_ENTRIES);
489
490         trace = (struct lock_trace *)(stack_trace + nr_stack_trace_entries);
491         max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries -
492                 LOCK_TRACE_SIZE_IN_LONGS;
493         trace->nr_entries = stack_trace_save(trace->entries, max_entries, 3);
494
495         if (nr_stack_trace_entries >= MAX_STACK_TRACE_ENTRIES -
496             LOCK_TRACE_SIZE_IN_LONGS - 1) {
497                 if (!debug_locks_off_graph_unlock())
498                         return NULL;
499
500                 print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!");
501                 dump_stack();
502
503                 return NULL;
504         }
505
506         hash = jhash(trace->entries, trace->nr_entries *
507                      sizeof(trace->entries[0]), 0);
508         trace->hash = hash;
509         hash_head = stack_trace_hash + (hash & (STACK_TRACE_HASH_SIZE - 1));
510         hlist_for_each_entry(t2, hash_head, hash_entry) {
511                 if (traces_identical(trace, t2))
512                         return t2;
513         }
514         nr_stack_trace_entries += LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries;
515         hlist_add_head(&trace->hash_entry, hash_head);
516
517         return trace;
518 }
519
520 /* Return the number of stack traces in the stack_trace[] array. */
521 u64 lockdep_stack_trace_count(void)
522 {
523         struct lock_trace *trace;
524         u64 c = 0;
525         int i;
526
527         for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++) {
528                 hlist_for_each_entry(trace, &stack_trace_hash[i], hash_entry) {
529                         c++;
530                 }
531         }
532
533         return c;
534 }
535
536 /* Return the number of stack hash chains that have at least one stack trace. */
537 u64 lockdep_stack_hash_count(void)
538 {
539         u64 c = 0;
540         int i;
541
542         for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++)
543                 if (!hlist_empty(&stack_trace_hash[i]))
544                         c++;
545
546         return c;
547 }
548 #endif
549
550 unsigned int nr_hardirq_chains;
551 unsigned int nr_softirq_chains;
552 unsigned int nr_process_chains;
553 unsigned int max_lockdep_depth;
554
555 #ifdef CONFIG_DEBUG_LOCKDEP
556 /*
557  * Various lockdep statistics:
558  */
559 DEFINE_PER_CPU(struct lockdep_stats, lockdep_stats);
560 #endif
561
562 #ifdef CONFIG_PROVE_LOCKING
563 /*
564  * Locking printouts:
565  */
566
567 #define __USAGE(__STATE)                                                \
568         [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE)"-W",       \
569         [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON-W",         \
570         [LOCK_USED_IN_##__STATE##_READ] = "IN-"__stringify(__STATE)"-R",\
571         [LOCK_ENABLED_##__STATE##_READ] = __stringify(__STATE)"-ON-R",
572
573 static const char *usage_str[] =
574 {
575 #define LOCKDEP_STATE(__STATE) __USAGE(__STATE)
576 #include "lockdep_states.h"
577 #undef LOCKDEP_STATE
578         [LOCK_USED] = "INITIAL USE",
579 };
580 #endif
581
582 const char *__get_key_name(const struct lockdep_subclass_key *key, char *str)
583 {
584         return kallsyms_lookup((unsigned long)key, NULL, NULL, NULL, str);
585 }
586
587 static inline unsigned long lock_flag(enum lock_usage_bit bit)
588 {
589         return 1UL << bit;
590 }
591
592 static char get_usage_char(struct lock_class *class, enum lock_usage_bit bit)
593 {
594         /*
595          * The usage character defaults to '.' (i.e., irqs disabled and not in
596          * irq context), which is the safest usage category.
597          */
598         char c = '.';
599
600         /*
601          * The order of the following usage checks matters, which will
602          * result in the outcome character as follows:
603          *
604          * - '+': irq is enabled and not in irq context
605          * - '-': in irq context and irq is disabled
606          * - '?': in irq context and irq is enabled
607          */
608         if (class->usage_mask & lock_flag(bit + LOCK_USAGE_DIR_MASK)) {
609                 c = '+';
610                 if (class->usage_mask & lock_flag(bit))
611                         c = '?';
612         } else if (class->usage_mask & lock_flag(bit))
613                 c = '-';
614
615         return c;
616 }
617
618 void get_usage_chars(struct lock_class *class, char usage[LOCK_USAGE_CHARS])
619 {
620         int i = 0;
621
622 #define LOCKDEP_STATE(__STATE)                                          \
623         usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE);     \
624         usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_READ);
625 #include "lockdep_states.h"
626 #undef LOCKDEP_STATE
627
628         usage[i] = '\0';
629 }
630
631 static void __print_lock_name(struct lock_class *class)
632 {
633         char str[KSYM_NAME_LEN];
634         const char *name;
635
636         name = class->name;
637         if (!name) {
638                 name = __get_key_name(class->key, str);
639                 printk(KERN_CONT "%s", name);
640         } else {
641                 printk(KERN_CONT "%s", name);
642                 if (class->name_version > 1)
643                         printk(KERN_CONT "#%d", class->name_version);
644                 if (class->subclass)
645                         printk(KERN_CONT "/%d", class->subclass);
646         }
647 }
648
649 static void print_lock_name(struct lock_class *class)
650 {
651         char usage[LOCK_USAGE_CHARS];
652
653         get_usage_chars(class, usage);
654
655         printk(KERN_CONT " (");
656         __print_lock_name(class);
657         printk(KERN_CONT "){%s}", usage);
658 }
659
660 static void print_lockdep_cache(struct lockdep_map *lock)
661 {
662         const char *name;
663         char str[KSYM_NAME_LEN];
664
665         name = lock->name;
666         if (!name)
667                 name = __get_key_name(lock->key->subkeys, str);
668
669         printk(KERN_CONT "%s", name);
670 }
671
672 static void print_lock(struct held_lock *hlock)
673 {
674         /*
675          * We can be called locklessly through debug_show_all_locks() so be
676          * extra careful, the hlock might have been released and cleared.
677          *
678          * If this indeed happens, lets pretend it does not hurt to continue
679          * to print the lock unless the hlock class_idx does not point to a
680          * registered class. The rationale here is: since we don't attempt
681          * to distinguish whether we are in this situation, if it just
682          * happened we can't count on class_idx to tell either.
683          */
684         struct lock_class *lock = hlock_class(hlock);
685
686         if (!lock) {
687                 printk(KERN_CONT "<RELEASED>\n");
688                 return;
689         }
690
691         printk(KERN_CONT "%px", hlock->instance);
692         print_lock_name(lock);
693         printk(KERN_CONT ", at: %pS\n", (void *)hlock->acquire_ip);
694 }
695
696 static void lockdep_print_held_locks(struct task_struct *p)
697 {
698         int i, depth = READ_ONCE(p->lockdep_depth);
699
700         if (!depth)
701                 printk("no locks held by %s/%d.\n", p->comm, task_pid_nr(p));
702         else
703                 printk("%d lock%s held by %s/%d:\n", depth,
704                        depth > 1 ? "s" : "", p->comm, task_pid_nr(p));
705         /*
706          * It's not reliable to print a task's held locks if it's not sleeping
707          * and it's not the current task.
708          */
709         if (p->state == TASK_RUNNING && p != current)
710                 return;
711         for (i = 0; i < depth; i++) {
712                 printk(" #%d: ", i);
713                 print_lock(p->held_locks + i);
714         }
715 }
716
717 static void print_kernel_ident(void)
718 {
719         printk("%s %.*s %s\n", init_utsname()->release,
720                 (int)strcspn(init_utsname()->version, " "),
721                 init_utsname()->version,
722                 print_tainted());
723 }
724
725 static int very_verbose(struct lock_class *class)
726 {
727 #if VERY_VERBOSE
728         return class_filter(class);
729 #endif
730         return 0;
731 }
732
733 /*
734  * Is this the address of a static object:
735  */
736 #ifdef __KERNEL__
737 static int static_obj(const void *obj)
738 {
739         unsigned long start = (unsigned long) &_stext,
740                       end   = (unsigned long) &_end,
741                       addr  = (unsigned long) obj;
742
743         if (arch_is_kernel_initmem_freed(addr))
744                 return 0;
745
746         /*
747          * static variable?
748          */
749         if ((addr >= start) && (addr < end))
750                 return 1;
751
752         if (arch_is_kernel_data(addr))
753                 return 1;
754
755         /*
756          * in-kernel percpu var?
757          */
758         if (is_kernel_percpu_address(addr))
759                 return 1;
760
761         /*
762          * module static or percpu var?
763          */
764         return is_module_address(addr) || is_module_percpu_address(addr);
765 }
766 #endif
767
768 /*
769  * To make lock name printouts unique, we calculate a unique
770  * class->name_version generation counter. The caller must hold the graph
771  * lock.
772  */
773 static int count_matching_names(struct lock_class *new_class)
774 {
775         struct lock_class *class;
776         int count = 0;
777
778         if (!new_class->name)
779                 return 0;
780
781         list_for_each_entry(class, &all_lock_classes, lock_entry) {
782                 if (new_class->key - new_class->subclass == class->key)
783                         return class->name_version;
784                 if (class->name && !strcmp(class->name, new_class->name))
785                         count = max(count, class->name_version);
786         }
787
788         return count + 1;
789 }
790
791 static inline struct lock_class *
792 look_up_lock_class(const struct lockdep_map *lock, unsigned int subclass)
793 {
794         struct lockdep_subclass_key *key;
795         struct hlist_head *hash_head;
796         struct lock_class *class;
797
798         if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
799                 debug_locks_off();
800                 printk(KERN_ERR
801                         "BUG: looking up invalid subclass: %u\n", subclass);
802                 printk(KERN_ERR
803                         "turning off the locking correctness validator.\n");
804                 dump_stack();
805                 return NULL;
806         }
807
808         /*
809          * If it is not initialised then it has never been locked,
810          * so it won't be present in the hash table.
811          */
812         if (unlikely(!lock->key))
813                 return NULL;
814
815         /*
816          * NOTE: the class-key must be unique. For dynamic locks, a static
817          * lock_class_key variable is passed in through the mutex_init()
818          * (or spin_lock_init()) call - which acts as the key. For static
819          * locks we use the lock object itself as the key.
820          */
821         BUILD_BUG_ON(sizeof(struct lock_class_key) >
822                         sizeof(struct lockdep_map));
823
824         key = lock->key->subkeys + subclass;
825
826         hash_head = classhashentry(key);
827
828         /*
829          * We do an RCU walk of the hash, see lockdep_free_key_range().
830          */
831         if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
832                 return NULL;
833
834         hlist_for_each_entry_rcu(class, hash_head, hash_entry) {
835                 if (class->key == key) {
836                         /*
837                          * Huh! same key, different name? Did someone trample
838                          * on some memory? We're most confused.
839                          */
840                         WARN_ON_ONCE(class->name != lock->name &&
841                                      lock->key != &__lockdep_no_validate__);
842                         return class;
843                 }
844         }
845
846         return NULL;
847 }
848
849 /*
850  * Static locks do not have their class-keys yet - for them the key is
851  * the lock object itself. If the lock is in the per cpu area, the
852  * canonical address of the lock (per cpu offset removed) is used.
853  */
854 static bool assign_lock_key(struct lockdep_map *lock)
855 {
856         unsigned long can_addr, addr = (unsigned long)lock;
857
858 #ifdef __KERNEL__
859         /*
860          * lockdep_free_key_range() assumes that struct lock_class_key
861          * objects do not overlap. Since we use the address of lock
862          * objects as class key for static objects, check whether the
863          * size of lock_class_key objects does not exceed the size of
864          * the smallest lock object.
865          */
866         BUILD_BUG_ON(sizeof(struct lock_class_key) > sizeof(raw_spinlock_t));
867 #endif
868
869         if (__is_kernel_percpu_address(addr, &can_addr))
870                 lock->key = (void *)can_addr;
871         else if (__is_module_percpu_address(addr, &can_addr))
872                 lock->key = (void *)can_addr;
873         else if (static_obj(lock))
874                 lock->key = (void *)lock;
875         else {
876                 /* Debug-check: all keys must be persistent! */
877                 debug_locks_off();
878                 pr_err("INFO: trying to register non-static key.\n");
879                 pr_err("the code is fine but needs lockdep annotation.\n");
880                 pr_err("turning off the locking correctness validator.\n");
881                 dump_stack();
882                 return false;
883         }
884
885         return true;
886 }
887
888 #ifdef CONFIG_DEBUG_LOCKDEP
889
890 /* Check whether element @e occurs in list @h */
891 static bool in_list(struct list_head *e, struct list_head *h)
892 {
893         struct list_head *f;
894
895         list_for_each(f, h) {
896                 if (e == f)
897                         return true;
898         }
899
900         return false;
901 }
902
903 /*
904  * Check whether entry @e occurs in any of the locks_after or locks_before
905  * lists.
906  */
907 static bool in_any_class_list(struct list_head *e)
908 {
909         struct lock_class *class;
910         int i;
911
912         for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
913                 class = &lock_classes[i];
914                 if (in_list(e, &class->locks_after) ||
915                     in_list(e, &class->locks_before))
916                         return true;
917         }
918         return false;
919 }
920
921 static bool class_lock_list_valid(struct lock_class *c, struct list_head *h)
922 {
923         struct lock_list *e;
924
925         list_for_each_entry(e, h, entry) {
926                 if (e->links_to != c) {
927                         printk(KERN_INFO "class %s: mismatch for lock entry %ld; class %s <> %s",
928                                c->name ? : "(?)",
929                                (unsigned long)(e - list_entries),
930                                e->links_to && e->links_to->name ?
931                                e->links_to->name : "(?)",
932                                e->class && e->class->name ? e->class->name :
933                                "(?)");
934                         return false;
935                 }
936         }
937         return true;
938 }
939
940 #ifdef CONFIG_PROVE_LOCKING
941 static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
942 #endif
943
944 static bool check_lock_chain_key(struct lock_chain *chain)
945 {
946 #ifdef CONFIG_PROVE_LOCKING
947         u64 chain_key = INITIAL_CHAIN_KEY;
948         int i;
949
950         for (i = chain->base; i < chain->base + chain->depth; i++)
951                 chain_key = iterate_chain_key(chain_key, chain_hlocks[i]);
952         /*
953          * The 'unsigned long long' casts avoid that a compiler warning
954          * is reported when building tools/lib/lockdep.
955          */
956         if (chain->chain_key != chain_key) {
957                 printk(KERN_INFO "chain %lld: key %#llx <> %#llx\n",
958                        (unsigned long long)(chain - lock_chains),
959                        (unsigned long long)chain->chain_key,
960                        (unsigned long long)chain_key);
961                 return false;
962         }
963 #endif
964         return true;
965 }
966
967 static bool in_any_zapped_class_list(struct lock_class *class)
968 {
969         struct pending_free *pf;
970         int i;
971
972         for (i = 0, pf = delayed_free.pf; i < ARRAY_SIZE(delayed_free.pf); i++, pf++) {
973                 if (in_list(&class->lock_entry, &pf->zapped))
974                         return true;
975         }
976
977         return false;
978 }
979
980 static bool __check_data_structures(void)
981 {
982         struct lock_class *class;
983         struct lock_chain *chain;
984         struct hlist_head *head;
985         struct lock_list *e;
986         int i;
987
988         /* Check whether all classes occur in a lock list. */
989         for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
990                 class = &lock_classes[i];
991                 if (!in_list(&class->lock_entry, &all_lock_classes) &&
992                     !in_list(&class->lock_entry, &free_lock_classes) &&
993                     !in_any_zapped_class_list(class)) {
994                         printk(KERN_INFO "class %px/%s is not in any class list\n",
995                                class, class->name ? : "(?)");
996                         return false;
997                 }
998         }
999
1000         /* Check whether all classes have valid lock lists. */
1001         for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
1002                 class = &lock_classes[i];
1003                 if (!class_lock_list_valid(class, &class->locks_before))
1004                         return false;
1005                 if (!class_lock_list_valid(class, &class->locks_after))
1006                         return false;
1007         }
1008
1009         /* Check the chain_key of all lock chains. */
1010         for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) {
1011                 head = chainhash_table + i;
1012                 hlist_for_each_entry_rcu(chain, head, entry) {
1013                         if (!check_lock_chain_key(chain))
1014                                 return false;
1015                 }
1016         }
1017
1018         /*
1019          * Check whether all list entries that are in use occur in a class
1020          * lock list.
1021          */
1022         for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
1023                 e = list_entries + i;
1024                 if (!in_any_class_list(&e->entry)) {
1025                         printk(KERN_INFO "list entry %d is not in any class list; class %s <> %s\n",
1026                                (unsigned int)(e - list_entries),
1027                                e->class->name ? : "(?)",
1028                                e->links_to->name ? : "(?)");
1029                         return false;
1030                 }
1031         }
1032
1033         /*
1034          * Check whether all list entries that are not in use do not occur in
1035          * a class lock list.
1036          */
1037         for_each_clear_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
1038                 e = list_entries + i;
1039                 if (in_any_class_list(&e->entry)) {
1040                         printk(KERN_INFO "list entry %d occurs in a class list; class %s <> %s\n",
1041                                (unsigned int)(e - list_entries),
1042                                e->class && e->class->name ? e->class->name :
1043                                "(?)",
1044                                e->links_to && e->links_to->name ?
1045                                e->links_to->name : "(?)");
1046                         return false;
1047                 }
1048         }
1049
1050         return true;
1051 }
1052
1053 int check_consistency = 0;
1054 module_param(check_consistency, int, 0644);
1055
1056 static void check_data_structures(void)
1057 {
1058         static bool once = false;
1059
1060         if (check_consistency && !once) {
1061                 if (!__check_data_structures()) {
1062                         once = true;
1063                         WARN_ON(once);
1064                 }
1065         }
1066 }
1067
1068 #else /* CONFIG_DEBUG_LOCKDEP */
1069
1070 static inline void check_data_structures(void) { }
1071
1072 #endif /* CONFIG_DEBUG_LOCKDEP */
1073
1074 /*
1075  * Initialize the lock_classes[] array elements, the free_lock_classes list
1076  * and also the delayed_free structure.
1077  */
1078 static void init_data_structures_once(void)
1079 {
1080         static bool ds_initialized, rcu_head_initialized;
1081         int i;
1082
1083         if (likely(rcu_head_initialized))
1084                 return;
1085
1086         if (system_state >= SYSTEM_SCHEDULING) {
1087                 init_rcu_head(&delayed_free.rcu_head);
1088                 rcu_head_initialized = true;
1089         }
1090
1091         if (ds_initialized)
1092                 return;
1093
1094         ds_initialized = true;
1095
1096         INIT_LIST_HEAD(&delayed_free.pf[0].zapped);
1097         INIT_LIST_HEAD(&delayed_free.pf[1].zapped);
1098
1099         for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
1100                 list_add_tail(&lock_classes[i].lock_entry, &free_lock_classes);
1101                 INIT_LIST_HEAD(&lock_classes[i].locks_after);
1102                 INIT_LIST_HEAD(&lock_classes[i].locks_before);
1103         }
1104 }
1105
1106 static inline struct hlist_head *keyhashentry(const struct lock_class_key *key)
1107 {
1108         unsigned long hash = hash_long((uintptr_t)key, KEYHASH_BITS);
1109
1110         return lock_keys_hash + hash;
1111 }
1112
1113 /* Register a dynamically allocated key. */
1114 void lockdep_register_key(struct lock_class_key *key)
1115 {
1116         struct hlist_head *hash_head;
1117         struct lock_class_key *k;
1118         unsigned long flags;
1119
1120         if (WARN_ON_ONCE(static_obj(key)))
1121                 return;
1122         hash_head = keyhashentry(key);
1123
1124         raw_local_irq_save(flags);
1125         if (!graph_lock())
1126                 goto restore_irqs;
1127         hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
1128                 if (WARN_ON_ONCE(k == key))
1129                         goto out_unlock;
1130         }
1131         hlist_add_head_rcu(&key->hash_entry, hash_head);
1132 out_unlock:
1133         graph_unlock();
1134 restore_irqs:
1135         raw_local_irq_restore(flags);
1136 }
1137 EXPORT_SYMBOL_GPL(lockdep_register_key);
1138
1139 /* Check whether a key has been registered as a dynamic key. */
1140 static bool is_dynamic_key(const struct lock_class_key *key)
1141 {
1142         struct hlist_head *hash_head;
1143         struct lock_class_key *k;
1144         bool found = false;
1145
1146         if (WARN_ON_ONCE(static_obj(key)))
1147                 return false;
1148
1149         /*
1150          * If lock debugging is disabled lock_keys_hash[] may contain
1151          * pointers to memory that has already been freed. Avoid triggering
1152          * a use-after-free in that case by returning early.
1153          */
1154         if (!debug_locks)
1155                 return true;
1156
1157         hash_head = keyhashentry(key);
1158
1159         rcu_read_lock();
1160         hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
1161                 if (k == key) {
1162                         found = true;
1163                         break;
1164                 }
1165         }
1166         rcu_read_unlock();
1167
1168         return found;
1169 }
1170
1171 /*
1172  * Register a lock's class in the hash-table, if the class is not present
1173  * yet. Otherwise we look it up. We cache the result in the lock object
1174  * itself, so actual lookup of the hash should be once per lock object.
1175  */
1176 static struct lock_class *
1177 register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
1178 {
1179         struct lockdep_subclass_key *key;
1180         struct hlist_head *hash_head;
1181         struct lock_class *class;
1182
1183         DEBUG_LOCKS_WARN_ON(!irqs_disabled());
1184
1185         class = look_up_lock_class(lock, subclass);
1186         if (likely(class))
1187                 goto out_set_class_cache;
1188
1189         if (!lock->key) {
1190                 if (!assign_lock_key(lock))
1191                         return NULL;
1192         } else if (!static_obj(lock->key) && !is_dynamic_key(lock->key)) {
1193                 return NULL;
1194         }
1195
1196         key = lock->key->subkeys + subclass;
1197         hash_head = classhashentry(key);
1198
1199         if (!graph_lock()) {
1200                 return NULL;
1201         }
1202         /*
1203          * We have to do the hash-walk again, to avoid races
1204          * with another CPU:
1205          */
1206         hlist_for_each_entry_rcu(class, hash_head, hash_entry) {
1207                 if (class->key == key)
1208                         goto out_unlock_set;
1209         }
1210
1211         init_data_structures_once();
1212
1213         /* Allocate a new lock class and add it to the hash. */
1214         class = list_first_entry_or_null(&free_lock_classes, typeof(*class),
1215                                          lock_entry);
1216         if (!class) {
1217                 if (!debug_locks_off_graph_unlock()) {
1218                         return NULL;
1219                 }
1220
1221                 print_lockdep_off("BUG: MAX_LOCKDEP_KEYS too low!");
1222                 dump_stack();
1223                 return NULL;
1224         }
1225         nr_lock_classes++;
1226         __set_bit(class - lock_classes, lock_classes_in_use);
1227         debug_atomic_inc(nr_unused_locks);
1228         class->key = key;
1229         class->name = lock->name;
1230         class->subclass = subclass;
1231         WARN_ON_ONCE(!list_empty(&class->locks_before));
1232         WARN_ON_ONCE(!list_empty(&class->locks_after));
1233         class->name_version = count_matching_names(class);
1234         /*
1235          * We use RCU's safe list-add method to make
1236          * parallel walking of the hash-list safe:
1237          */
1238         hlist_add_head_rcu(&class->hash_entry, hash_head);
1239         /*
1240          * Remove the class from the free list and add it to the global list
1241          * of classes.
1242          */
1243         list_move_tail(&class->lock_entry, &all_lock_classes);
1244
1245         if (verbose(class)) {
1246                 graph_unlock();
1247
1248                 printk("\nnew class %px: %s", class->key, class->name);
1249                 if (class->name_version > 1)
1250                         printk(KERN_CONT "#%d", class->name_version);
1251                 printk(KERN_CONT "\n");
1252                 dump_stack();
1253
1254                 if (!graph_lock()) {
1255                         return NULL;
1256                 }
1257         }
1258 out_unlock_set:
1259         graph_unlock();
1260
1261 out_set_class_cache:
1262         if (!subclass || force)
1263                 lock->class_cache[0] = class;
1264         else if (subclass < NR_LOCKDEP_CACHING_CLASSES)
1265                 lock->class_cache[subclass] = class;
1266
1267         /*
1268          * Hash collision, did we smoke some? We found a class with a matching
1269          * hash but the subclass -- which is hashed in -- didn't match.
1270          */
1271         if (DEBUG_LOCKS_WARN_ON(class->subclass != subclass))
1272                 return NULL;
1273
1274         return class;
1275 }
1276
1277 #ifdef CONFIG_PROVE_LOCKING
1278 /*
1279  * Allocate a lockdep entry. (assumes the graph_lock held, returns
1280  * with NULL on failure)
1281  */
1282 static struct lock_list *alloc_list_entry(void)
1283 {
1284         int idx = find_first_zero_bit(list_entries_in_use,
1285                                       ARRAY_SIZE(list_entries));
1286
1287         if (idx >= ARRAY_SIZE(list_entries)) {
1288                 if (!debug_locks_off_graph_unlock())
1289                         return NULL;
1290
1291                 print_lockdep_off("BUG: MAX_LOCKDEP_ENTRIES too low!");
1292                 dump_stack();
1293                 return NULL;
1294         }
1295         nr_list_entries++;
1296         __set_bit(idx, list_entries_in_use);
1297         return list_entries + idx;
1298 }
1299
1300 /*
1301  * Add a new dependency to the head of the list:
1302  */
1303 static int add_lock_to_list(struct lock_class *this,
1304                             struct lock_class *links_to, struct list_head *head,
1305                             unsigned long ip, int distance,
1306                             const struct lock_trace *trace)
1307 {
1308         struct lock_list *entry;
1309         /*
1310          * Lock not present yet - get a new dependency struct and
1311          * add it to the list:
1312          */
1313         entry = alloc_list_entry();
1314         if (!entry)
1315                 return 0;
1316
1317         entry->class = this;
1318         entry->links_to = links_to;
1319         entry->distance = distance;
1320         entry->trace = trace;
1321         /*
1322          * Both allocation and removal are done under the graph lock; but
1323          * iteration is under RCU-sched; see look_up_lock_class() and
1324          * lockdep_free_key_range().
1325          */
1326         list_add_tail_rcu(&entry->entry, head);
1327
1328         return 1;
1329 }
1330
1331 /*
1332  * For good efficiency of modular, we use power of 2
1333  */
1334 #define MAX_CIRCULAR_QUEUE_SIZE         4096UL
1335 #define CQ_MASK                         (MAX_CIRCULAR_QUEUE_SIZE-1)
1336
1337 /*
1338  * The circular_queue and helpers are used to implement graph
1339  * breadth-first search (BFS) algorithm, by which we can determine
1340  * whether there is a path from a lock to another. In deadlock checks,
1341  * a path from the next lock to be acquired to a previous held lock
1342  * indicates that adding the <prev> -> <next> lock dependency will
1343  * produce a circle in the graph. Breadth-first search instead of
1344  * depth-first search is used in order to find the shortest (circular)
1345  * path.
1346  */
1347 struct circular_queue {
1348         struct lock_list *element[MAX_CIRCULAR_QUEUE_SIZE];
1349         unsigned int  front, rear;
1350 };
1351
1352 static struct circular_queue lock_cq;
1353
1354 unsigned int max_bfs_queue_depth;
1355
1356 static unsigned int lockdep_dependency_gen_id;
1357
1358 static inline void __cq_init(struct circular_queue *cq)
1359 {
1360         cq->front = cq->rear = 0;
1361         lockdep_dependency_gen_id++;
1362 }
1363
1364 static inline int __cq_empty(struct circular_queue *cq)
1365 {
1366         return (cq->front == cq->rear);
1367 }
1368
1369 static inline int __cq_full(struct circular_queue *cq)
1370 {
1371         return ((cq->rear + 1) & CQ_MASK) == cq->front;
1372 }
1373
1374 static inline int __cq_enqueue(struct circular_queue *cq, struct lock_list *elem)
1375 {
1376         if (__cq_full(cq))
1377                 return -1;
1378
1379         cq->element[cq->rear] = elem;
1380         cq->rear = (cq->rear + 1) & CQ_MASK;
1381         return 0;
1382 }
1383
1384 /*
1385  * Dequeue an element from the circular_queue, return a lock_list if
1386  * the queue is not empty, or NULL if otherwise.
1387  */
1388 static inline struct lock_list * __cq_dequeue(struct circular_queue *cq)
1389 {
1390         struct lock_list * lock;
1391
1392         if (__cq_empty(cq))
1393                 return NULL;
1394
1395         lock = cq->element[cq->front];
1396         cq->front = (cq->front + 1) & CQ_MASK;
1397
1398         return lock;
1399 }
1400
1401 static inline unsigned int  __cq_get_elem_count(struct circular_queue *cq)
1402 {
1403         return (cq->rear - cq->front) & CQ_MASK;
1404 }
1405
1406 static inline void mark_lock_accessed(struct lock_list *lock,
1407                                         struct lock_list *parent)
1408 {
1409         unsigned long nr;
1410
1411         nr = lock - list_entries;
1412         WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
1413         lock->parent = parent;
1414         lock->class->dep_gen_id = lockdep_dependency_gen_id;
1415 }
1416
1417 static inline unsigned long lock_accessed(struct lock_list *lock)
1418 {
1419         unsigned long nr;
1420
1421         nr = lock - list_entries;
1422         WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
1423         return lock->class->dep_gen_id == lockdep_dependency_gen_id;
1424 }
1425
1426 static inline struct lock_list *get_lock_parent(struct lock_list *child)
1427 {
1428         return child->parent;
1429 }
1430
1431 static inline int get_lock_depth(struct lock_list *child)
1432 {
1433         int depth = 0;
1434         struct lock_list *parent;
1435
1436         while ((parent = get_lock_parent(child))) {
1437                 child = parent;
1438                 depth++;
1439         }
1440         return depth;
1441 }
1442
1443 /*
1444  * Return the forward or backward dependency list.
1445  *
1446  * @lock:   the lock_list to get its class's dependency list
1447  * @offset: the offset to struct lock_class to determine whether it is
1448  *          locks_after or locks_before
1449  */
1450 static inline struct list_head *get_dep_list(struct lock_list *lock, int offset)
1451 {
1452         void *lock_class = lock->class;
1453
1454         return lock_class + offset;
1455 }
1456
1457 /*
1458  * Forward- or backward-dependency search, used for both circular dependency
1459  * checking and hardirq-unsafe/softirq-unsafe checking.
1460  */
1461 static int __bfs(struct lock_list *source_entry,
1462                  void *data,
1463                  int (*match)(struct lock_list *entry, void *data),
1464                  struct lock_list **target_entry,
1465                  int offset)
1466 {
1467         struct lock_list *entry;
1468         struct lock_list *lock;
1469         struct list_head *head;
1470         struct circular_queue *cq = &lock_cq;
1471         int ret = 1;
1472
1473         if (match(source_entry, data)) {
1474                 *target_entry = source_entry;
1475                 ret = 0;
1476                 goto exit;
1477         }
1478
1479         head = get_dep_list(source_entry, offset);
1480         if (list_empty(head))
1481                 goto exit;
1482
1483         __cq_init(cq);
1484         __cq_enqueue(cq, source_entry);
1485
1486         while ((lock = __cq_dequeue(cq))) {
1487
1488                 if (!lock->class) {
1489                         ret = -2;
1490                         goto exit;
1491                 }
1492
1493                 head = get_dep_list(lock, offset);
1494
1495                 DEBUG_LOCKS_WARN_ON(!irqs_disabled());
1496
1497                 list_for_each_entry_rcu(entry, head, entry) {
1498                         if (!lock_accessed(entry)) {
1499                                 unsigned int cq_depth;
1500                                 mark_lock_accessed(entry, lock);
1501                                 if (match(entry, data)) {
1502                                         *target_entry = entry;
1503                                         ret = 0;
1504                                         goto exit;
1505                                 }
1506
1507                                 if (__cq_enqueue(cq, entry)) {
1508                                         ret = -1;
1509                                         goto exit;
1510                                 }
1511                                 cq_depth = __cq_get_elem_count(cq);
1512                                 if (max_bfs_queue_depth < cq_depth)
1513                                         max_bfs_queue_depth = cq_depth;
1514                         }
1515                 }
1516         }
1517 exit:
1518         return ret;
1519 }
1520
1521 static inline int __bfs_forwards(struct lock_list *src_entry,
1522                         void *data,
1523                         int (*match)(struct lock_list *entry, void *data),
1524                         struct lock_list **target_entry)
1525 {
1526         return __bfs(src_entry, data, match, target_entry,
1527                      offsetof(struct lock_class, locks_after));
1528
1529 }
1530
1531 static inline int __bfs_backwards(struct lock_list *src_entry,
1532                         void *data,
1533                         int (*match)(struct lock_list *entry, void *data),
1534                         struct lock_list **target_entry)
1535 {
1536         return __bfs(src_entry, data, match, target_entry,
1537                      offsetof(struct lock_class, locks_before));
1538
1539 }
1540
1541 static void print_lock_trace(const struct lock_trace *trace,
1542                              unsigned int spaces)
1543 {
1544         stack_trace_print(trace->entries, trace->nr_entries, spaces);
1545 }
1546
1547 /*
1548  * Print a dependency chain entry (this is only done when a deadlock
1549  * has been detected):
1550  */
1551 static noinline void
1552 print_circular_bug_entry(struct lock_list *target, int depth)
1553 {
1554         if (debug_locks_silent)
1555                 return;
1556         printk("\n-> #%u", depth);
1557         print_lock_name(target->class);
1558         printk(KERN_CONT ":\n");
1559         print_lock_trace(target->trace, 6);
1560 }
1561
1562 static void
1563 print_circular_lock_scenario(struct held_lock *src,
1564                              struct held_lock *tgt,
1565                              struct lock_list *prt)
1566 {
1567         struct lock_class *source = hlock_class(src);
1568         struct lock_class *target = hlock_class(tgt);
1569         struct lock_class *parent = prt->class;
1570
1571         /*
1572          * A direct locking problem where unsafe_class lock is taken
1573          * directly by safe_class lock, then all we need to show
1574          * is the deadlock scenario, as it is obvious that the
1575          * unsafe lock is taken under the safe lock.
1576          *
1577          * But if there is a chain instead, where the safe lock takes
1578          * an intermediate lock (middle_class) where this lock is
1579          * not the same as the safe lock, then the lock chain is
1580          * used to describe the problem. Otherwise we would need
1581          * to show a different CPU case for each link in the chain
1582          * from the safe_class lock to the unsafe_class lock.
1583          */
1584         if (parent != source) {
1585                 printk("Chain exists of:\n  ");
1586                 __print_lock_name(source);
1587                 printk(KERN_CONT " --> ");
1588                 __print_lock_name(parent);
1589                 printk(KERN_CONT " --> ");
1590                 __print_lock_name(target);
1591                 printk(KERN_CONT "\n\n");
1592         }
1593
1594         printk(" Possible unsafe locking scenario:\n\n");
1595         printk("       CPU0                    CPU1\n");
1596         printk("       ----                    ----\n");
1597         printk("  lock(");
1598         __print_lock_name(target);
1599         printk(KERN_CONT ");\n");
1600         printk("                               lock(");
1601         __print_lock_name(parent);
1602         printk(KERN_CONT ");\n");
1603         printk("                               lock(");
1604         __print_lock_name(target);
1605         printk(KERN_CONT ");\n");
1606         printk("  lock(");
1607         __print_lock_name(source);
1608         printk(KERN_CONT ");\n");
1609         printk("\n *** DEADLOCK ***\n\n");
1610 }
1611
1612 /*
1613  * When a circular dependency is detected, print the
1614  * header first:
1615  */
1616 static noinline void
1617 print_circular_bug_header(struct lock_list *entry, unsigned int depth,
1618                         struct held_lock *check_src,
1619                         struct held_lock *check_tgt)
1620 {
1621         struct task_struct *curr = current;
1622
1623         if (debug_locks_silent)
1624                 return;
1625
1626         pr_warn("\n");
1627         pr_warn("======================================================\n");
1628         pr_warn("WARNING: possible circular locking dependency detected\n");
1629         print_kernel_ident();
1630         pr_warn("------------------------------------------------------\n");
1631         pr_warn("%s/%d is trying to acquire lock:\n",
1632                 curr->comm, task_pid_nr(curr));
1633         print_lock(check_src);
1634
1635         pr_warn("\nbut task is already holding lock:\n");
1636
1637         print_lock(check_tgt);
1638         pr_warn("\nwhich lock already depends on the new lock.\n\n");
1639         pr_warn("\nthe existing dependency chain (in reverse order) is:\n");
1640
1641         print_circular_bug_entry(entry, depth);
1642 }
1643
1644 static inline int class_equal(struct lock_list *entry, void *data)
1645 {
1646         return entry->class == data;
1647 }
1648
1649 static noinline void print_circular_bug(struct lock_list *this,
1650                                         struct lock_list *target,
1651                                         struct held_lock *check_src,
1652                                         struct held_lock *check_tgt)
1653 {
1654         struct task_struct *curr = current;
1655         struct lock_list *parent;
1656         struct lock_list *first_parent;
1657         int depth;
1658
1659         if (!debug_locks_off_graph_unlock() || debug_locks_silent)
1660                 return;
1661
1662         this->trace = save_trace();
1663         if (!this->trace)
1664                 return;
1665
1666         depth = get_lock_depth(target);
1667
1668         print_circular_bug_header(target, depth, check_src, check_tgt);
1669
1670         parent = get_lock_parent(target);
1671         first_parent = parent;
1672
1673         while (parent) {
1674                 print_circular_bug_entry(parent, --depth);
1675                 parent = get_lock_parent(parent);
1676         }
1677
1678         printk("\nother info that might help us debug this:\n\n");
1679         print_circular_lock_scenario(check_src, check_tgt,
1680                                      first_parent);
1681
1682         lockdep_print_held_locks(curr);
1683
1684         printk("\nstack backtrace:\n");
1685         dump_stack();
1686 }
1687
1688 static noinline void print_bfs_bug(int ret)
1689 {
1690         if (!debug_locks_off_graph_unlock())
1691                 return;
1692
1693         /*
1694          * Breadth-first-search failed, graph got corrupted?
1695          */
1696         WARN(1, "lockdep bfs error:%d\n", ret);
1697 }
1698
1699 static int noop_count(struct lock_list *entry, void *data)
1700 {
1701         (*(unsigned long *)data)++;
1702         return 0;
1703 }
1704
1705 static unsigned long __lockdep_count_forward_deps(struct lock_list *this)
1706 {
1707         unsigned long  count = 0;
1708         struct lock_list *uninitialized_var(target_entry);
1709
1710         __bfs_forwards(this, (void *)&count, noop_count, &target_entry);
1711
1712         return count;
1713 }
1714 unsigned long lockdep_count_forward_deps(struct lock_class *class)
1715 {
1716         unsigned long ret, flags;
1717         struct lock_list this;
1718
1719         this.parent = NULL;
1720         this.class = class;
1721
1722         raw_local_irq_save(flags);
1723         arch_spin_lock(&lockdep_lock);
1724         ret = __lockdep_count_forward_deps(&this);
1725         arch_spin_unlock(&lockdep_lock);
1726         raw_local_irq_restore(flags);
1727
1728         return ret;
1729 }
1730
1731 static unsigned long __lockdep_count_backward_deps(struct lock_list *this)
1732 {
1733         unsigned long  count = 0;
1734         struct lock_list *uninitialized_var(target_entry);
1735
1736         __bfs_backwards(this, (void *)&count, noop_count, &target_entry);
1737
1738         return count;
1739 }
1740
1741 unsigned long lockdep_count_backward_deps(struct lock_class *class)
1742 {
1743         unsigned long ret, flags;
1744         struct lock_list this;
1745
1746         this.parent = NULL;
1747         this.class = class;
1748
1749         raw_local_irq_save(flags);
1750         arch_spin_lock(&lockdep_lock);
1751         ret = __lockdep_count_backward_deps(&this);
1752         arch_spin_unlock(&lockdep_lock);
1753         raw_local_irq_restore(flags);
1754
1755         return ret;
1756 }
1757
1758 /*
1759  * Check that the dependency graph starting at <src> can lead to
1760  * <target> or not. Print an error and return 0 if it does.
1761  */
1762 static noinline int
1763 check_path(struct lock_class *target, struct lock_list *src_entry,
1764            struct lock_list **target_entry)
1765 {
1766         int ret;
1767
1768         ret = __bfs_forwards(src_entry, (void *)target, class_equal,
1769                              target_entry);
1770
1771         if (unlikely(ret < 0))
1772                 print_bfs_bug(ret);
1773
1774         return ret;
1775 }
1776
1777 /*
1778  * Prove that the dependency graph starting at <src> can not
1779  * lead to <target>. If it can, there is a circle when adding
1780  * <target> -> <src> dependency.
1781  *
1782  * Print an error and return 0 if it does.
1783  */
1784 static noinline int
1785 check_noncircular(struct held_lock *src, struct held_lock *target,
1786                   struct lock_trace **const trace)
1787 {
1788         int ret;
1789         struct lock_list *uninitialized_var(target_entry);
1790         struct lock_list src_entry = {
1791                 .class = hlock_class(src),
1792                 .parent = NULL,
1793         };
1794
1795         debug_atomic_inc(nr_cyclic_checks);
1796
1797         ret = check_path(hlock_class(target), &src_entry, &target_entry);
1798
1799         if (unlikely(!ret)) {
1800                 if (!*trace) {
1801                         /*
1802                          * If save_trace fails here, the printing might
1803                          * trigger a WARN but because of the !nr_entries it
1804                          * should not do bad things.
1805                          */
1806                         *trace = save_trace();
1807                 }
1808
1809                 print_circular_bug(&src_entry, target_entry, src, target);
1810         }
1811
1812         return ret;
1813 }
1814
1815 #ifdef CONFIG_LOCKDEP_SMALL
1816 /*
1817  * Check that the dependency graph starting at <src> can lead to
1818  * <target> or not. If it can, <src> -> <target> dependency is already
1819  * in the graph.
1820  *
1821  * Print an error and return 2 if it does or 1 if it does not.
1822  */
1823 static noinline int
1824 check_redundant(struct held_lock *src, struct held_lock *target)
1825 {
1826         int ret;
1827         struct lock_list *uninitialized_var(target_entry);
1828         struct lock_list src_entry = {
1829                 .class = hlock_class(src),
1830                 .parent = NULL,
1831         };
1832
1833         debug_atomic_inc(nr_redundant_checks);
1834
1835         ret = check_path(hlock_class(target), &src_entry, &target_entry);
1836
1837         if (!ret) {
1838                 debug_atomic_inc(nr_redundant);
1839                 ret = 2;
1840         } else if (ret < 0)
1841                 ret = 0;
1842
1843         return ret;
1844 }
1845 #endif
1846
1847 #ifdef CONFIG_TRACE_IRQFLAGS
1848
1849 static inline int usage_accumulate(struct lock_list *entry, void *mask)
1850 {
1851         *(unsigned long *)mask |= entry->class->usage_mask;
1852
1853         return 0;
1854 }
1855
1856 /*
1857  * Forwards and backwards subgraph searching, for the purposes of
1858  * proving that two subgraphs can be connected by a new dependency
1859  * without creating any illegal irq-safe -> irq-unsafe lock dependency.
1860  */
1861
1862 static inline int usage_match(struct lock_list *entry, void *mask)
1863 {
1864         return entry->class->usage_mask & *(unsigned long *)mask;
1865 }
1866
1867 /*
1868  * Find a node in the forwards-direction dependency sub-graph starting
1869  * at @root->class that matches @bit.
1870  *
1871  * Return 0 if such a node exists in the subgraph, and put that node
1872  * into *@target_entry.
1873  *
1874  * Return 1 otherwise and keep *@target_entry unchanged.
1875  * Return <0 on error.
1876  */
1877 static int
1878 find_usage_forwards(struct lock_list *root, unsigned long usage_mask,
1879                         struct lock_list **target_entry)
1880 {
1881         int result;
1882
1883         debug_atomic_inc(nr_find_usage_forwards_checks);
1884
1885         result = __bfs_forwards(root, &usage_mask, usage_match, target_entry);
1886
1887         return result;
1888 }
1889
1890 /*
1891  * Find a node in the backwards-direction dependency sub-graph starting
1892  * at @root->class that matches @bit.
1893  *
1894  * Return 0 if such a node exists in the subgraph, and put that node
1895  * into *@target_entry.
1896  *
1897  * Return 1 otherwise and keep *@target_entry unchanged.
1898  * Return <0 on error.
1899  */
1900 static int
1901 find_usage_backwards(struct lock_list *root, unsigned long usage_mask,
1902                         struct lock_list **target_entry)
1903 {
1904         int result;
1905
1906         debug_atomic_inc(nr_find_usage_backwards_checks);
1907
1908         result = __bfs_backwards(root, &usage_mask, usage_match, target_entry);
1909
1910         return result;
1911 }
1912
1913 static void print_lock_class_header(struct lock_class *class, int depth)
1914 {
1915         int bit;
1916
1917         printk("%*s->", depth, "");
1918         print_lock_name(class);
1919 #ifdef CONFIG_DEBUG_LOCKDEP
1920         printk(KERN_CONT " ops: %lu", debug_class_ops_read(class));
1921 #endif
1922         printk(KERN_CONT " {\n");
1923
1924         for (bit = 0; bit < LOCK_USAGE_STATES; bit++) {
1925                 if (class->usage_mask & (1 << bit)) {
1926                         int len = depth;
1927
1928                         len += printk("%*s   %s", depth, "", usage_str[bit]);
1929                         len += printk(KERN_CONT " at:\n");
1930                         print_lock_trace(class->usage_traces[bit], len);
1931                 }
1932         }
1933         printk("%*s }\n", depth, "");
1934
1935         printk("%*s ... key      at: [<%px>] %pS\n",
1936                 depth, "", class->key, class->key);
1937 }
1938
1939 /*
1940  * printk the shortest lock dependencies from @start to @end in reverse order:
1941  */
1942 static void __used
1943 print_shortest_lock_dependencies(struct lock_list *leaf,
1944                                  struct lock_list *root)
1945 {
1946         struct lock_list *entry = leaf;
1947         int depth;
1948
1949         /*compute depth from generated tree by BFS*/
1950         depth = get_lock_depth(leaf);
1951
1952         do {
1953                 print_lock_class_header(entry->class, depth);
1954                 printk("%*s ... acquired at:\n", depth, "");
1955                 print_lock_trace(entry->trace, 2);
1956                 printk("\n");
1957
1958                 if (depth == 0 && (entry != root)) {
1959                         printk("lockdep:%s bad path found in chain graph\n", __func__);
1960                         break;
1961                 }
1962
1963                 entry = get_lock_parent(entry);
1964                 depth--;
1965         } while (entry && (depth >= 0));
1966 }
1967
1968 static void
1969 print_irq_lock_scenario(struct lock_list *safe_entry,
1970                         struct lock_list *unsafe_entry,
1971                         struct lock_class *prev_class,
1972                         struct lock_class *next_class)
1973 {
1974         struct lock_class *safe_class = safe_entry->class;
1975         struct lock_class *unsafe_class = unsafe_entry->class;
1976         struct lock_class *middle_class = prev_class;
1977
1978         if (middle_class == safe_class)
1979                 middle_class = next_class;
1980
1981         /*
1982          * A direct locking problem where unsafe_class lock is taken
1983          * directly by safe_class lock, then all we need to show
1984          * is the deadlock scenario, as it is obvious that the
1985          * unsafe lock is taken under the safe lock.
1986          *
1987          * But if there is a chain instead, where the safe lock takes
1988          * an intermediate lock (middle_class) where this lock is
1989          * not the same as the safe lock, then the lock chain is
1990          * used to describe the problem. Otherwise we would need
1991          * to show a different CPU case for each link in the chain
1992          * from the safe_class lock to the unsafe_class lock.
1993          */
1994         if (middle_class != unsafe_class) {
1995                 printk("Chain exists of:\n  ");
1996                 __print_lock_name(safe_class);
1997                 printk(KERN_CONT " --> ");
1998                 __print_lock_name(middle_class);
1999                 printk(KERN_CONT " --> ");
2000                 __print_lock_name(unsafe_class);
2001                 printk(KERN_CONT "\n\n");
2002         }
2003
2004         printk(" Possible interrupt unsafe locking scenario:\n\n");
2005         printk("       CPU0                    CPU1\n");
2006         printk("       ----                    ----\n");
2007         printk("  lock(");
2008         __print_lock_name(unsafe_class);
2009         printk(KERN_CONT ");\n");
2010         printk("                               local_irq_disable();\n");
2011         printk("                               lock(");
2012         __print_lock_name(safe_class);
2013         printk(KERN_CONT ");\n");
2014         printk("                               lock(");
2015         __print_lock_name(middle_class);
2016         printk(KERN_CONT ");\n");
2017         printk("  <Interrupt>\n");
2018         printk("    lock(");
2019         __print_lock_name(safe_class);
2020         printk(KERN_CONT ");\n");
2021         printk("\n *** DEADLOCK ***\n\n");
2022 }
2023
2024 static void
2025 print_bad_irq_dependency(struct task_struct *curr,
2026                          struct lock_list *prev_root,
2027                          struct lock_list *next_root,
2028                          struct lock_list *backwards_entry,
2029                          struct lock_list *forwards_entry,
2030                          struct held_lock *prev,
2031                          struct held_lock *next,
2032                          enum lock_usage_bit bit1,
2033                          enum lock_usage_bit bit2,
2034                          const char *irqclass)
2035 {
2036         if (!debug_locks_off_graph_unlock() || debug_locks_silent)
2037                 return;
2038
2039         pr_warn("\n");
2040         pr_warn("=====================================================\n");
2041         pr_warn("WARNING: %s-safe -> %s-unsafe lock order detected\n",
2042                 irqclass, irqclass);
2043         print_kernel_ident();
2044         pr_warn("-----------------------------------------------------\n");
2045         pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] is trying to acquire:\n",
2046                 curr->comm, task_pid_nr(curr),
2047                 curr->hardirq_context, hardirq_count() >> HARDIRQ_SHIFT,
2048                 curr->softirq_context, softirq_count() >> SOFTIRQ_SHIFT,
2049                 curr->hardirqs_enabled,
2050                 curr->softirqs_enabled);
2051         print_lock(next);
2052
2053         pr_warn("\nand this task is already holding:\n");
2054         print_lock(prev);
2055         pr_warn("which would create a new lock dependency:\n");
2056         print_lock_name(hlock_class(prev));
2057         pr_cont(" ->");
2058         print_lock_name(hlock_class(next));
2059         pr_cont("\n");
2060
2061         pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",
2062                 irqclass);
2063         print_lock_name(backwards_entry->class);
2064         pr_warn("\n... which became %s-irq-safe at:\n", irqclass);
2065
2066         print_lock_trace(backwards_entry->class->usage_traces[bit1], 1);
2067
2068         pr_warn("\nto a %s-irq-unsafe lock:\n", irqclass);
2069         print_lock_name(forwards_entry->class);
2070         pr_warn("\n... which became %s-irq-unsafe at:\n", irqclass);
2071         pr_warn("...");
2072
2073         print_lock_trace(forwards_entry->class->usage_traces[bit2], 1);
2074
2075         pr_warn("\nother info that might help us debug this:\n\n");
2076         print_irq_lock_scenario(backwards_entry, forwards_entry,
2077                                 hlock_class(prev), hlock_class(next));
2078
2079         lockdep_print_held_locks(curr);
2080
2081         pr_warn("\nthe dependencies between %s-irq-safe lock and the holding lock:\n", irqclass);
2082         prev_root->trace = save_trace();
2083         if (!prev_root->trace)
2084                 return;
2085         print_shortest_lock_dependencies(backwards_entry, prev_root);
2086
2087         pr_warn("\nthe dependencies between the lock to be acquired");
2088         pr_warn(" and %s-irq-unsafe lock:\n", irqclass);
2089         next_root->trace = save_trace();
2090         if (!next_root->trace)
2091                 return;
2092         print_shortest_lock_dependencies(forwards_entry, next_root);
2093
2094         pr_warn("\nstack backtrace:\n");
2095         dump_stack();
2096 }
2097
2098 static const char *state_names[] = {
2099 #define LOCKDEP_STATE(__STATE) \
2100         __stringify(__STATE),
2101 #include "lockdep_states.h"
2102 #undef LOCKDEP_STATE
2103 };
2104
2105 static const char *state_rnames[] = {
2106 #define LOCKDEP_STATE(__STATE) \
2107         __stringify(__STATE)"-READ",
2108 #include "lockdep_states.h"
2109 #undef LOCKDEP_STATE
2110 };
2111
2112 static inline const char *state_name(enum lock_usage_bit bit)
2113 {
2114         if (bit & LOCK_USAGE_READ_MASK)
2115                 return state_rnames[bit >> LOCK_USAGE_DIR_MASK];
2116         else
2117                 return state_names[bit >> LOCK_USAGE_DIR_MASK];
2118 }
2119
2120 /*
2121  * The bit number is encoded like:
2122  *
2123  *  bit0: 0 exclusive, 1 read lock
2124  *  bit1: 0 used in irq, 1 irq enabled
2125  *  bit2-n: state
2126  */
2127 static int exclusive_bit(int new_bit)
2128 {
2129         int state = new_bit & LOCK_USAGE_STATE_MASK;
2130         int dir = new_bit & LOCK_USAGE_DIR_MASK;
2131
2132         /*
2133          * keep state, bit flip the direction and strip read.
2134          */
2135         return state | (dir ^ LOCK_USAGE_DIR_MASK);
2136 }
2137
2138 /*
2139  * Observe that when given a bitmask where each bitnr is encoded as above, a
2140  * right shift of the mask transforms the individual bitnrs as -1 and
2141  * conversely, a left shift transforms into +1 for the individual bitnrs.
2142  *
2143  * So for all bits whose number have LOCK_ENABLED_* set (bitnr1 == 1), we can
2144  * create the mask with those bit numbers using LOCK_USED_IN_* (bitnr1 == 0)
2145  * instead by subtracting the bit number by 2, or shifting the mask right by 2.
2146  *
2147  * Similarly, bitnr1 == 0 becomes bitnr1 == 1 by adding 2, or shifting left 2.
2148  *
2149  * So split the mask (note that LOCKF_ENABLED_IRQ_ALL|LOCKF_USED_IN_IRQ_ALL is
2150  * all bits set) and recompose with bitnr1 flipped.
2151  */
2152 static unsigned long invert_dir_mask(unsigned long mask)
2153 {
2154         unsigned long excl = 0;
2155
2156         /* Invert dir */
2157         excl |= (mask & LOCKF_ENABLED_IRQ_ALL) >> LOCK_USAGE_DIR_MASK;
2158         excl |= (mask & LOCKF_USED_IN_IRQ_ALL) << LOCK_USAGE_DIR_MASK;
2159
2160         return excl;
2161 }
2162
2163 /*
2164  * As above, we clear bitnr0 (LOCK_*_READ off) with bitmask ops. First, for all
2165  * bits with bitnr0 set (LOCK_*_READ), add those with bitnr0 cleared (LOCK_*).
2166  * And then mask out all bitnr0.
2167  */
2168 static unsigned long exclusive_mask(unsigned long mask)
2169 {
2170         unsigned long excl = invert_dir_mask(mask);
2171
2172         /* Strip read */
2173         excl |= (excl & LOCKF_IRQ_READ) >> LOCK_USAGE_READ_MASK;
2174         excl &= ~LOCKF_IRQ_READ;
2175
2176         return excl;
2177 }
2178
2179 /*
2180  * Retrieve the _possible_ original mask to which @mask is
2181  * exclusive. Ie: this is the opposite of exclusive_mask().
2182  * Note that 2 possible original bits can match an exclusive
2183  * bit: one has LOCK_USAGE_READ_MASK set, the other has it
2184  * cleared. So both are returned for each exclusive bit.
2185  */
2186 static unsigned long original_mask(unsigned long mask)
2187 {
2188         unsigned long excl = invert_dir_mask(mask);
2189
2190         /* Include read in existing usages */
2191         excl |= (excl & LOCKF_IRQ) << LOCK_USAGE_READ_MASK;
2192
2193         return excl;
2194 }
2195
2196 /*
2197  * Find the first pair of bit match between an original
2198  * usage mask and an exclusive usage mask.
2199  */
2200 static int find_exclusive_match(unsigned long mask,
2201                                 unsigned long excl_mask,
2202                                 enum lock_usage_bit *bitp,
2203                                 enum lock_usage_bit *excl_bitp)
2204 {
2205         int bit, excl;
2206
2207         for_each_set_bit(bit, &mask, LOCK_USED) {
2208                 excl = exclusive_bit(bit);
2209                 if (excl_mask & lock_flag(excl)) {
2210                         *bitp = bit;
2211                         *excl_bitp = excl;
2212                         return 0;
2213                 }
2214         }
2215         return -1;
2216 }
2217
2218 /*
2219  * Prove that the new dependency does not connect a hardirq-safe(-read)
2220  * lock with a hardirq-unsafe lock - to achieve this we search
2221  * the backwards-subgraph starting at <prev>, and the
2222  * forwards-subgraph starting at <next>:
2223  */
2224 static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
2225                            struct held_lock *next)
2226 {
2227         unsigned long usage_mask = 0, forward_mask, backward_mask;
2228         enum lock_usage_bit forward_bit = 0, backward_bit = 0;
2229         struct lock_list *uninitialized_var(target_entry1);
2230         struct lock_list *uninitialized_var(target_entry);
2231         struct lock_list this, that;
2232         int ret;
2233
2234         /*
2235          * Step 1: gather all hard/soft IRQs usages backward in an
2236          * accumulated usage mask.
2237          */
2238         this.parent = NULL;
2239         this.class = hlock_class(prev);
2240
2241         ret = __bfs_backwards(&this, &usage_mask, usage_accumulate, NULL);
2242         if (ret < 0) {
2243                 print_bfs_bug(ret);
2244                 return 0;
2245         }
2246
2247         usage_mask &= LOCKF_USED_IN_IRQ_ALL;
2248         if (!usage_mask)
2249                 return 1;
2250
2251         /*
2252          * Step 2: find exclusive uses forward that match the previous
2253          * backward accumulated mask.
2254          */
2255         forward_mask = exclusive_mask(usage_mask);
2256
2257         that.parent = NULL;
2258         that.class = hlock_class(next);
2259
2260         ret = find_usage_forwards(&that, forward_mask, &target_entry1);
2261         if (ret < 0) {
2262                 print_bfs_bug(ret);
2263                 return 0;
2264         }
2265         if (ret == 1)
2266                 return ret;
2267
2268         /*
2269          * Step 3: we found a bad match! Now retrieve a lock from the backward
2270          * list whose usage mask matches the exclusive usage mask from the
2271          * lock found on the forward list.
2272          */
2273         backward_mask = original_mask(target_entry1->class->usage_mask);
2274
2275         ret = find_usage_backwards(&this, backward_mask, &target_entry);
2276         if (ret < 0) {
2277                 print_bfs_bug(ret);
2278                 return 0;
2279         }
2280         if (DEBUG_LOCKS_WARN_ON(ret == 1))
2281                 return 1;
2282
2283         /*
2284          * Step 4: narrow down to a pair of incompatible usage bits
2285          * and report it.
2286          */
2287         ret = find_exclusive_match(target_entry->class->usage_mask,
2288                                    target_entry1->class->usage_mask,
2289                                    &backward_bit, &forward_bit);
2290         if (DEBUG_LOCKS_WARN_ON(ret == -1))
2291                 return 1;
2292
2293         print_bad_irq_dependency(curr, &this, &that,
2294                                  target_entry, target_entry1,
2295                                  prev, next,
2296                                  backward_bit, forward_bit,
2297                                  state_name(backward_bit));
2298
2299         return 0;
2300 }
2301
2302 static void inc_chains(void)
2303 {
2304         if (current->hardirq_context)
2305                 nr_hardirq_chains++;
2306         else {
2307                 if (current->softirq_context)
2308                         nr_softirq_chains++;
2309                 else
2310                         nr_process_chains++;
2311         }
2312 }
2313
2314 #else
2315
2316 static inline int check_irq_usage(struct task_struct *curr,
2317                                   struct held_lock *prev, struct held_lock *next)
2318 {
2319         return 1;
2320 }
2321
2322 static inline void inc_chains(void)
2323 {
2324         nr_process_chains++;
2325 }
2326
2327 #endif /* CONFIG_TRACE_IRQFLAGS */
2328
2329 static void
2330 print_deadlock_scenario(struct held_lock *nxt, struct held_lock *prv)
2331 {
2332         struct lock_class *next = hlock_class(nxt);
2333         struct lock_class *prev = hlock_class(prv);
2334
2335         printk(" Possible unsafe locking scenario:\n\n");
2336         printk("       CPU0\n");
2337         printk("       ----\n");
2338         printk("  lock(");
2339         __print_lock_name(prev);
2340         printk(KERN_CONT ");\n");
2341         printk("  lock(");
2342         __print_lock_name(next);
2343         printk(KERN_CONT ");\n");
2344         printk("\n *** DEADLOCK ***\n\n");
2345         printk(" May be due to missing lock nesting notation\n\n");
2346 }
2347
2348 static void
2349 print_deadlock_bug(struct task_struct *curr, struct held_lock *prev,
2350                    struct held_lock *next)
2351 {
2352         if (!debug_locks_off_graph_unlock() || debug_locks_silent)
2353                 return;
2354
2355         pr_warn("\n");
2356         pr_warn("============================================\n");
2357         pr_warn("WARNING: possible recursive locking detected\n");
2358         print_kernel_ident();
2359         pr_warn("--------------------------------------------\n");
2360         pr_warn("%s/%d is trying to acquire lock:\n",
2361                 curr->comm, task_pid_nr(curr));
2362         print_lock(next);
2363         pr_warn("\nbut task is already holding lock:\n");
2364         print_lock(prev);
2365
2366         pr_warn("\nother info that might help us debug this:\n");
2367         print_deadlock_scenario(next, prev);
2368         lockdep_print_held_locks(curr);
2369
2370         pr_warn("\nstack backtrace:\n");
2371         dump_stack();
2372 }
2373
2374 /*
2375  * Check whether we are holding such a class already.
2376  *
2377  * (Note that this has to be done separately, because the graph cannot
2378  * detect such classes of deadlocks.)
2379  *
2380  * Returns: 0 on deadlock detected, 1 on OK, 2 on recursive read
2381  */
2382 static int
2383 check_deadlock(struct task_struct *curr, struct held_lock *next)
2384 {
2385         struct held_lock *prev;
2386         struct held_lock *nest = NULL;
2387         int i;
2388
2389         for (i = 0; i < curr->lockdep_depth; i++) {
2390                 prev = curr->held_locks + i;
2391
2392                 if (prev->instance == next->nest_lock)
2393                         nest = prev;
2394
2395                 if (hlock_class(prev) != hlock_class(next))
2396                         continue;
2397
2398                 /*
2399                  * Allow read-after-read recursion of the same
2400                  * lock class (i.e. read_lock(lock)+read_lock(lock)):
2401                  */
2402                 if ((next->read == 2) && prev->read)
2403                         return 2;
2404
2405                 /*
2406                  * We're holding the nest_lock, which serializes this lock's
2407                  * nesting behaviour.
2408                  */
2409                 if (nest)
2410                         return 2;
2411
2412                 print_deadlock_bug(curr, prev, next);
2413                 return 0;
2414         }
2415         return 1;
2416 }
2417
2418 /*
2419  * There was a chain-cache miss, and we are about to add a new dependency
2420  * to a previous lock. We validate the following rules:
2421  *
2422  *  - would the adding of the <prev> -> <next> dependency create a
2423  *    circular dependency in the graph? [== circular deadlock]
2424  *
2425  *  - does the new prev->next dependency connect any hardirq-safe lock
2426  *    (in the full backwards-subgraph starting at <prev>) with any
2427  *    hardirq-unsafe lock (in the full forwards-subgraph starting at
2428  *    <next>)? [== illegal lock inversion with hardirq contexts]
2429  *
2430  *  - does the new prev->next dependency connect any softirq-safe lock
2431  *    (in the full backwards-subgraph starting at <prev>) with any
2432  *    softirq-unsafe lock (in the full forwards-subgraph starting at
2433  *    <next>)? [== illegal lock inversion with softirq contexts]
2434  *
2435  * any of these scenarios could lead to a deadlock.
2436  *
2437  * Then if all the validations pass, we add the forwards and backwards
2438  * dependency.
2439  */
2440 static int
2441 check_prev_add(struct task_struct *curr, struct held_lock *prev,
2442                struct held_lock *next, int distance,
2443                struct lock_trace **const trace)
2444 {
2445         struct lock_list *entry;
2446         int ret;
2447
2448         if (!hlock_class(prev)->key || !hlock_class(next)->key) {
2449                 /*
2450                  * The warning statements below may trigger a use-after-free
2451                  * of the class name. It is better to trigger a use-after free
2452                  * and to have the class name most of the time instead of not
2453                  * having the class name available.
2454                  */
2455                 WARN_ONCE(!debug_locks_silent && !hlock_class(prev)->key,
2456                           "Detected use-after-free of lock class %px/%s\n",
2457                           hlock_class(prev),
2458                           hlock_class(prev)->name);
2459                 WARN_ONCE(!debug_locks_silent && !hlock_class(next)->key,
2460                           "Detected use-after-free of lock class %px/%s\n",
2461                           hlock_class(next),
2462                           hlock_class(next)->name);
2463                 return 2;
2464         }
2465
2466         /*
2467          * Prove that the new <prev> -> <next> dependency would not
2468          * create a circular dependency in the graph. (We do this by
2469          * a breadth-first search into the graph starting at <next>,
2470          * and check whether we can reach <prev>.)
2471          *
2472          * The search is limited by the size of the circular queue (i.e.,
2473          * MAX_CIRCULAR_QUEUE_SIZE) which keeps track of a breadth of nodes
2474          * in the graph whose neighbours are to be checked.
2475          */
2476         ret = check_noncircular(next, prev, trace);
2477         if (unlikely(ret <= 0))
2478                 return 0;
2479
2480         if (!check_irq_usage(curr, prev, next))
2481                 return 0;
2482
2483         /*
2484          * For recursive read-locks we do all the dependency checks,
2485          * but we dont store read-triggered dependencies (only
2486          * write-triggered dependencies). This ensures that only the
2487          * write-side dependencies matter, and that if for example a
2488          * write-lock never takes any other locks, then the reads are
2489          * equivalent to a NOP.
2490          */
2491         if (next->read == 2 || prev->read == 2)
2492                 return 1;
2493         /*
2494          * Is the <prev> -> <next> dependency already present?
2495          *
2496          * (this may occur even though this is a new chain: consider
2497          *  e.g. the L1 -> L2 -> L3 -> L4 and the L5 -> L1 -> L2 -> L3
2498          *  chains - the second one will be new, but L1 already has
2499          *  L2 added to its dependency list, due to the first chain.)
2500          */
2501         list_for_each_entry(entry, &hlock_class(prev)->locks_after, entry) {
2502                 if (entry->class == hlock_class(next)) {
2503                         if (distance == 1)
2504                                 entry->distance = 1;
2505                         return 1;
2506                 }
2507         }
2508
2509 #ifdef CONFIG_LOCKDEP_SMALL
2510         /*
2511          * Is the <prev> -> <next> link redundant?
2512          */
2513         ret = check_redundant(prev, next);
2514         if (ret != 1)
2515                 return ret;
2516 #endif
2517
2518         if (!*trace) {
2519                 *trace = save_trace();
2520                 if (!*trace)
2521                         return 0;
2522         }
2523
2524         /*
2525          * Ok, all validations passed, add the new lock
2526          * to the previous lock's dependency list:
2527          */
2528         ret = add_lock_to_list(hlock_class(next), hlock_class(prev),
2529                                &hlock_class(prev)->locks_after,
2530                                next->acquire_ip, distance, *trace);
2531
2532         if (!ret)
2533                 return 0;
2534
2535         ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
2536                                &hlock_class(next)->locks_before,
2537                                next->acquire_ip, distance, *trace);
2538         if (!ret)
2539                 return 0;
2540
2541         return 2;
2542 }
2543
2544 /*
2545  * Add the dependency to all directly-previous locks that are 'relevant'.
2546  * The ones that are relevant are (in increasing distance from curr):
2547  * all consecutive trylock entries and the final non-trylock entry - or
2548  * the end of this context's lock-chain - whichever comes first.
2549  */
2550 static int
2551 check_prevs_add(struct task_struct *curr, struct held_lock *next)
2552 {
2553         struct lock_trace *trace = NULL;
2554         int depth = curr->lockdep_depth;
2555         struct held_lock *hlock;
2556
2557         /*
2558          * Debugging checks.
2559          *
2560          * Depth must not be zero for a non-head lock:
2561          */
2562         if (!depth)
2563                 goto out_bug;
2564         /*
2565          * At least two relevant locks must exist for this
2566          * to be a head:
2567          */
2568         if (curr->held_locks[depth].irq_context !=
2569                         curr->held_locks[depth-1].irq_context)
2570                 goto out_bug;
2571
2572         for (;;) {
2573                 int distance = curr->lockdep_depth - depth + 1;
2574                 hlock = curr->held_locks + depth - 1;
2575
2576                 /*
2577                  * Only non-recursive-read entries get new dependencies
2578                  * added:
2579                  */
2580                 if (hlock->read != 2 && hlock->check) {
2581                         int ret = check_prev_add(curr, hlock, next, distance,
2582                                                  &trace);
2583                         if (!ret)
2584                                 return 0;
2585
2586                         /*
2587                          * Stop after the first non-trylock entry,
2588                          * as non-trylock entries have added their
2589                          * own direct dependencies already, so this
2590                          * lock is connected to them indirectly:
2591                          */
2592                         if (!hlock->trylock)
2593                                 break;
2594                 }
2595
2596                 depth--;
2597                 /*
2598                  * End of lock-stack?
2599                  */
2600                 if (!depth)
2601                         break;
2602                 /*
2603                  * Stop the search if we cross into another context:
2604                  */
2605                 if (curr->held_locks[depth].irq_context !=
2606                                 curr->held_locks[depth-1].irq_context)
2607                         break;
2608         }
2609         return 1;
2610 out_bug:
2611         if (!debug_locks_off_graph_unlock())
2612                 return 0;
2613
2614         /*
2615          * Clearly we all shouldn't be here, but since we made it we
2616          * can reliable say we messed up our state. See the above two
2617          * gotos for reasons why we could possibly end up here.
2618          */
2619         WARN_ON(1);
2620
2621         return 0;
2622 }
2623
2624 struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS];
2625 static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS);
2626 int nr_chain_hlocks;
2627 static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS];
2628
2629 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
2630 {
2631         return lock_classes + chain_hlocks[chain->base + i];
2632 }
2633
2634 /*
2635  * Returns the index of the first held_lock of the current chain
2636  */
2637 static inline int get_first_held_lock(struct task_struct *curr,
2638                                         struct held_lock *hlock)
2639 {
2640         int i;
2641         struct held_lock *hlock_curr;
2642
2643         for (i = curr->lockdep_depth - 1; i >= 0; i--) {
2644                 hlock_curr = curr->held_locks + i;
2645                 if (hlock_curr->irq_context != hlock->irq_context)
2646                         break;
2647
2648         }
2649
2650         return ++i;
2651 }
2652
2653 #ifdef CONFIG_DEBUG_LOCKDEP
2654 /*
2655  * Returns the next chain_key iteration
2656  */
2657 static u64 print_chain_key_iteration(int class_idx, u64 chain_key)
2658 {
2659         u64 new_chain_key = iterate_chain_key(chain_key, class_idx);
2660
2661         printk(" class_idx:%d -> chain_key:%016Lx",
2662                 class_idx,
2663                 (unsigned long long)new_chain_key);
2664         return new_chain_key;
2665 }
2666
2667 static void
2668 print_chain_keys_held_locks(struct task_struct *curr, struct held_lock *hlock_next)
2669 {
2670         struct held_lock *hlock;
2671         u64 chain_key = INITIAL_CHAIN_KEY;
2672         int depth = curr->lockdep_depth;
2673         int i = get_first_held_lock(curr, hlock_next);
2674
2675         printk("depth: %u (irq_context %u)\n", depth - i + 1,
2676                 hlock_next->irq_context);
2677         for (; i < depth; i++) {
2678                 hlock = curr->held_locks + i;
2679                 chain_key = print_chain_key_iteration(hlock->class_idx, chain_key);
2680
2681                 print_lock(hlock);
2682         }
2683
2684         print_chain_key_iteration(hlock_next->class_idx, chain_key);
2685         print_lock(hlock_next);
2686 }
2687
2688 static void print_chain_keys_chain(struct lock_chain *chain)
2689 {
2690         int i;
2691         u64 chain_key = INITIAL_CHAIN_KEY;
2692         int class_id;
2693
2694         printk("depth: %u\n", chain->depth);
2695         for (i = 0; i < chain->depth; i++) {
2696                 class_id = chain_hlocks[chain->base + i];
2697                 chain_key = print_chain_key_iteration(class_id, chain_key);
2698
2699                 print_lock_name(lock_classes + class_id);
2700                 printk("\n");
2701         }
2702 }
2703
2704 static void print_collision(struct task_struct *curr,
2705                         struct held_lock *hlock_next,
2706                         struct lock_chain *chain)
2707 {
2708         pr_warn("\n");
2709         pr_warn("============================\n");
2710         pr_warn("WARNING: chain_key collision\n");
2711         print_kernel_ident();
2712         pr_warn("----------------------------\n");
2713         pr_warn("%s/%d: ", current->comm, task_pid_nr(current));
2714         pr_warn("Hash chain already cached but the contents don't match!\n");
2715
2716         pr_warn("Held locks:");
2717         print_chain_keys_held_locks(curr, hlock_next);
2718
2719         pr_warn("Locks in cached chain:");
2720         print_chain_keys_chain(chain);
2721
2722         pr_warn("\nstack backtrace:\n");
2723         dump_stack();
2724 }
2725 #endif
2726
2727 /*
2728  * Checks whether the chain and the current held locks are consistent
2729  * in depth and also in content. If they are not it most likely means
2730  * that there was a collision during the calculation of the chain_key.
2731  * Returns: 0 not passed, 1 passed
2732  */
2733 static int check_no_collision(struct task_struct *curr,
2734                         struct held_lock *hlock,
2735                         struct lock_chain *chain)
2736 {
2737 #ifdef CONFIG_DEBUG_LOCKDEP
2738         int i, j, id;
2739
2740         i = get_first_held_lock(curr, hlock);
2741
2742         if (DEBUG_LOCKS_WARN_ON(chain->depth != curr->lockdep_depth - (i - 1))) {
2743                 print_collision(curr, hlock, chain);
2744                 return 0;
2745         }
2746
2747         for (j = 0; j < chain->depth - 1; j++, i++) {
2748                 id = curr->held_locks[i].class_idx;
2749
2750                 if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id)) {
2751                         print_collision(curr, hlock, chain);
2752                         return 0;
2753                 }
2754         }
2755 #endif
2756         return 1;
2757 }
2758
2759 /*
2760  * Given an index that is >= -1, return the index of the next lock chain.
2761  * Return -2 if there is no next lock chain.
2762  */
2763 long lockdep_next_lockchain(long i)
2764 {
2765         i = find_next_bit(lock_chains_in_use, ARRAY_SIZE(lock_chains), i + 1);
2766         return i < ARRAY_SIZE(lock_chains) ? i : -2;
2767 }
2768
2769 unsigned long lock_chain_count(void)
2770 {
2771         return bitmap_weight(lock_chains_in_use, ARRAY_SIZE(lock_chains));
2772 }
2773
2774 /* Must be called with the graph lock held. */
2775 static struct lock_chain *alloc_lock_chain(void)
2776 {
2777         int idx = find_first_zero_bit(lock_chains_in_use,
2778                                       ARRAY_SIZE(lock_chains));
2779
2780         if (unlikely(idx >= ARRAY_SIZE(lock_chains)))
2781                 return NULL;
2782         __set_bit(idx, lock_chains_in_use);
2783         return lock_chains + idx;
2784 }
2785
2786 /*
2787  * Adds a dependency chain into chain hashtable. And must be called with
2788  * graph_lock held.
2789  *
2790  * Return 0 if fail, and graph_lock is released.
2791  * Return 1 if succeed, with graph_lock held.
2792  */
2793 static inline int add_chain_cache(struct task_struct *curr,
2794                                   struct held_lock *hlock,
2795                                   u64 chain_key)
2796 {
2797         struct lock_class *class = hlock_class(hlock);
2798         struct hlist_head *hash_head = chainhashentry(chain_key);
2799         struct lock_chain *chain;
2800         int i, j;
2801
2802         /*
2803          * The caller must hold the graph lock, ensure we've got IRQs
2804          * disabled to make this an IRQ-safe lock.. for recursion reasons
2805          * lockdep won't complain about its own locking errors.
2806          */
2807         if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
2808                 return 0;
2809
2810         chain = alloc_lock_chain();
2811         if (!chain) {
2812                 if (!debug_locks_off_graph_unlock())
2813                         return 0;
2814
2815                 print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!");
2816                 dump_stack();
2817                 return 0;
2818         }
2819         chain->chain_key = chain_key;
2820         chain->irq_context = hlock->irq_context;
2821         i = get_first_held_lock(curr, hlock);
2822         chain->depth = curr->lockdep_depth + 1 - i;
2823
2824         BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks));
2825         BUILD_BUG_ON((1UL << 6)  <= ARRAY_SIZE(curr->held_locks));
2826         BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <= ARRAY_SIZE(lock_classes));
2827
2828         if (likely(nr_chain_hlocks + chain->depth <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
2829                 chain->base = nr_chain_hlocks;
2830                 for (j = 0; j < chain->depth - 1; j++, i++) {
2831                         int lock_id = curr->held_locks[i].class_idx;
2832                         chain_hlocks[chain->base + j] = lock_id;
2833                 }
2834                 chain_hlocks[chain->base + j] = class - lock_classes;
2835                 nr_chain_hlocks += chain->depth;
2836         } else {
2837                 if (!debug_locks_off_graph_unlock())
2838                         return 0;
2839
2840                 print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
2841                 dump_stack();
2842                 return 0;
2843         }
2844
2845         hlist_add_head_rcu(&chain->entry, hash_head);
2846         debug_atomic_inc(chain_lookup_misses);
2847         inc_chains();
2848
2849         return 1;
2850 }
2851
2852 /*
2853  * Look up a dependency chain. Must be called with either the graph lock or
2854  * the RCU read lock held.
2855  */
2856 static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
2857 {
2858         struct hlist_head *hash_head = chainhashentry(chain_key);
2859         struct lock_chain *chain;
2860
2861         hlist_for_each_entry_rcu(chain, hash_head, entry) {
2862                 if (READ_ONCE(chain->chain_key) == chain_key) {
2863                         debug_atomic_inc(chain_lookup_hits);
2864                         return chain;
2865                 }
2866         }
2867         return NULL;
2868 }
2869
2870 /*
2871  * If the key is not present yet in dependency chain cache then
2872  * add it and return 1 - in this case the new dependency chain is
2873  * validated. If the key is already hashed, return 0.
2874  * (On return with 1 graph_lock is held.)
2875  */
2876 static inline int lookup_chain_cache_add(struct task_struct *curr,
2877                                          struct held_lock *hlock,
2878                                          u64 chain_key)
2879 {
2880         struct lock_class *class = hlock_class(hlock);
2881         struct lock_chain *chain = lookup_chain_cache(chain_key);
2882
2883         if (chain) {
2884 cache_hit:
2885                 if (!check_no_collision(curr, hlock, chain))
2886                         return 0;
2887
2888                 if (very_verbose(class)) {
2889                         printk("\nhash chain already cached, key: "
2890                                         "%016Lx tail class: [%px] %s\n",
2891                                         (unsigned long long)chain_key,
2892                                         class->key, class->name);
2893                 }
2894
2895                 return 0;
2896         }
2897
2898         if (very_verbose(class)) {
2899                 printk("\nnew hash chain, key: %016Lx tail class: [%px] %s\n",
2900                         (unsigned long long)chain_key, class->key, class->name);
2901         }
2902
2903         if (!graph_lock())
2904                 return 0;
2905
2906         /*
2907          * We have to walk the chain again locked - to avoid duplicates:
2908          */
2909         chain = lookup_chain_cache(chain_key);
2910         if (chain) {
2911                 graph_unlock();
2912                 goto cache_hit;
2913         }
2914
2915         if (!add_chain_cache(curr, hlock, chain_key))
2916                 return 0;
2917
2918         return 1;
2919 }
2920
2921 static int validate_chain(struct task_struct *curr,
2922                           struct held_lock *hlock,
2923                           int chain_head, u64 chain_key)
2924 {
2925         /*
2926          * Trylock needs to maintain the stack of held locks, but it
2927          * does not add new dependencies, because trylock can be done
2928          * in any order.
2929          *
2930          * We look up the chain_key and do the O(N^2) check and update of
2931          * the dependencies only if this is a new dependency chain.
2932          * (If lookup_chain_cache_add() return with 1 it acquires
2933          * graph_lock for us)
2934          */
2935         if (!hlock->trylock && hlock->check &&
2936             lookup_chain_cache_add(curr, hlock, chain_key)) {
2937                 /*
2938                  * Check whether last held lock:
2939                  *
2940                  * - is irq-safe, if this lock is irq-unsafe
2941                  * - is softirq-safe, if this lock is hardirq-unsafe
2942                  *
2943                  * And check whether the new lock's dependency graph
2944                  * could lead back to the previous lock:
2945                  *
2946                  * - within the current held-lock stack
2947                  * - across our accumulated lock dependency records
2948                  *
2949                  * any of these scenarios could lead to a deadlock.
2950                  */
2951                 /*
2952                  * The simple case: does the current hold the same lock
2953                  * already?
2954                  */
2955                 int ret = check_deadlock(curr, hlock);
2956
2957                 if (!ret)
2958                         return 0;
2959                 /*
2960                  * Mark recursive read, as we jump over it when
2961                  * building dependencies (just like we jump over
2962                  * trylock entries):
2963                  */
2964                 if (ret == 2)
2965                         hlock->read = 2;
2966                 /*
2967                  * Add dependency only if this lock is not the head
2968                  * of the chain, and if it's not a secondary read-lock:
2969                  */
2970                 if (!chain_head && ret != 2) {
2971                         if (!check_prevs_add(curr, hlock))
2972                                 return 0;
2973                 }
2974
2975                 graph_unlock();
2976         } else {
2977                 /* after lookup_chain_cache_add(): */
2978                 if (unlikely(!debug_locks))
2979                         return 0;
2980         }
2981
2982         return 1;
2983 }
2984 #else
2985 static inline int validate_chain(struct task_struct *curr,
2986                                  struct held_lock *hlock,
2987                                  int chain_head, u64 chain_key)
2988 {
2989         return 1;
2990 }
2991 #endif /* CONFIG_PROVE_LOCKING */
2992
2993 /*
2994  * We are building curr_chain_key incrementally, so double-check
2995  * it from scratch, to make sure that it's done correctly:
2996  */
2997 static void check_chain_key(struct task_struct *curr)
2998 {
2999 #ifdef CONFIG_DEBUG_LOCKDEP
3000         struct held_lock *hlock, *prev_hlock = NULL;
3001         unsigned int i;
3002         u64 chain_key = INITIAL_CHAIN_KEY;
3003
3004         for (i = 0; i < curr->lockdep_depth; i++) {
3005                 hlock = curr->held_locks + i;
3006                 if (chain_key != hlock->prev_chain_key) {
3007                         debug_locks_off();
3008                         /*
3009                          * We got mighty confused, our chain keys don't match
3010                          * with what we expect, someone trample on our task state?
3011                          */
3012                         WARN(1, "hm#1, depth: %u [%u], %016Lx != %016Lx\n",
3013                                 curr->lockdep_depth, i,
3014                                 (unsigned long long)chain_key,
3015                                 (unsigned long long)hlock->prev_chain_key);
3016                         return;
3017                 }
3018
3019                 /*
3020                  * hlock->class_idx can't go beyond MAX_LOCKDEP_KEYS, but is
3021                  * it registered lock class index?
3022                  */
3023                 if (DEBUG_LOCKS_WARN_ON(!test_bit(hlock->class_idx, lock_classes_in_use)))
3024                         return;
3025
3026                 if (prev_hlock && (prev_hlock->irq_context !=
3027                                                         hlock->irq_context))
3028                         chain_key = INITIAL_CHAIN_KEY;
3029                 chain_key = iterate_chain_key(chain_key, hlock->class_idx);
3030                 prev_hlock = hlock;
3031         }
3032         if (chain_key != curr->curr_chain_key) {
3033                 debug_locks_off();
3034                 /*
3035                  * More smoking hash instead of calculating it, damn see these
3036                  * numbers float.. I bet that a pink elephant stepped on my memory.
3037                  */
3038                 WARN(1, "hm#2, depth: %u [%u], %016Lx != %016Lx\n",
3039                         curr->lockdep_depth, i,
3040                         (unsigned long long)chain_key,
3041                         (unsigned long long)curr->curr_chain_key);
3042         }
3043 #endif
3044 }
3045
3046 #ifdef CONFIG_PROVE_LOCKING
3047 static int mark_lock(struct task_struct *curr, struct held_lock *this,
3048                      enum lock_usage_bit new_bit);
3049
3050 static void print_usage_bug_scenario(struct held_lock *lock)
3051 {
3052         struct lock_class *class = hlock_class(lock);
3053
3054         printk(" Possible unsafe locking scenario:\n\n");
3055         printk("       CPU0\n");
3056         printk("       ----\n");
3057         printk("  lock(");
3058         __print_lock_name(class);
3059         printk(KERN_CONT ");\n");
3060         printk("  <Interrupt>\n");
3061         printk("    lock(");
3062         __print_lock_name(class);
3063         printk(KERN_CONT ");\n");
3064         printk("\n *** DEADLOCK ***\n\n");
3065 }
3066
3067 static void
3068 print_usage_bug(struct task_struct *curr, struct held_lock *this,
3069                 enum lock_usage_bit prev_bit, enum lock_usage_bit new_bit)
3070 {
3071         if (!debug_locks_off_graph_unlock() || debug_locks_silent)
3072                 return;
3073
3074         pr_warn("\n");
3075         pr_warn("================================\n");
3076         pr_warn("WARNING: inconsistent lock state\n");
3077         print_kernel_ident();
3078         pr_warn("--------------------------------\n");
3079
3080         pr_warn("inconsistent {%s} -> {%s} usage.\n",
3081                 usage_str[prev_bit], usage_str[new_bit]);
3082
3083         pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] takes:\n",
3084                 curr->comm, task_pid_nr(curr),
3085                 trace_hardirq_context(curr), hardirq_count() >> HARDIRQ_SHIFT,
3086                 trace_softirq_context(curr), softirq_count() >> SOFTIRQ_SHIFT,
3087                 trace_hardirqs_enabled(curr),
3088                 trace_softirqs_enabled(curr));
3089         print_lock(this);
3090
3091         pr_warn("{%s} state was registered at:\n", usage_str[prev_bit]);
3092         print_lock_trace(hlock_class(this)->usage_traces[prev_bit], 1);
3093
3094         print_irqtrace_events(curr);
3095         pr_warn("\nother info that might help us debug this:\n");
3096         print_usage_bug_scenario(this);
3097
3098         lockdep_print_held_locks(curr);
3099
3100         pr_warn("\nstack backtrace:\n");
3101         dump_stack();
3102 }
3103
3104 /*
3105  * Print out an error if an invalid bit is set:
3106  */
3107 static inline int
3108 valid_state(struct task_struct *curr, struct held_lock *this,
3109             enum lock_usage_bit new_bit, enum lock_usage_bit bad_bit)
3110 {
3111         if (unlikely(hlock_class(this)->usage_mask & (1 << bad_bit))) {
3112                 print_usage_bug(curr, this, bad_bit, new_bit);
3113                 return 0;
3114         }
3115         return 1;
3116 }
3117
3118
3119 /*
3120  * print irq inversion bug:
3121  */
3122 static void
3123 print_irq_inversion_bug(struct task_struct *curr,
3124                         struct lock_list *root, struct lock_list *other,
3125                         struct held_lock *this, int forwards,
3126                         const char *irqclass)
3127 {
3128         struct lock_list *entry = other;
3129         struct lock_list *middle = NULL;
3130         int depth;
3131
3132         if (!debug_locks_off_graph_unlock() || debug_locks_silent)
3133                 return;
3134
3135         pr_warn("\n");
3136         pr_warn("========================================================\n");
3137         pr_warn("WARNING: possible irq lock inversion dependency detected\n");
3138         print_kernel_ident();
3139         pr_warn("--------------------------------------------------------\n");
3140         pr_warn("%s/%d just changed the state of lock:\n",
3141                 curr->comm, task_pid_nr(curr));
3142         print_lock(this);
3143         if (forwards)
3144                 pr_warn("but this lock took another, %s-unsafe lock in the past:\n", irqclass);
3145         else
3146                 pr_warn("but this lock was taken by another, %s-safe lock in the past:\n", irqclass);
3147         print_lock_name(other->class);
3148         pr_warn("\n\nand interrupts could create inverse lock ordering between them.\n\n");
3149
3150         pr_warn("\nother info that might help us debug this:\n");
3151
3152         /* Find a middle lock (if one exists) */
3153         depth = get_lock_depth(other);
3154         do {
3155                 if (depth == 0 && (entry != root)) {
3156                         pr_warn("lockdep:%s bad path found in chain graph\n", __func__);
3157                         break;
3158                 }
3159                 middle = entry;
3160                 entry = get_lock_parent(entry);
3161                 depth--;
3162         } while (entry && entry != root && (depth >= 0));
3163         if (forwards)
3164                 print_irq_lock_scenario(root, other,
3165                         middle ? middle->class : root->class, other->class);
3166         else
3167                 print_irq_lock_scenario(other, root,
3168                         middle ? middle->class : other->class, root->class);
3169
3170         lockdep_print_held_locks(curr);
3171
3172         pr_warn("\nthe shortest dependencies between 2nd lock and 1st lock:\n");
3173         root->trace = save_trace();
3174         if (!root->trace)
3175                 return;
3176         print_shortest_lock_dependencies(other, root);
3177
3178         pr_warn("\nstack backtrace:\n");
3179         dump_stack();
3180 }
3181
3182 /*
3183  * Prove that in the forwards-direction subgraph starting at <this>
3184  * there is no lock matching <mask>:
3185  */
3186 static int
3187 check_usage_forwards(struct task_struct *curr, struct held_lock *this,
3188                      enum lock_usage_bit bit, const char *irqclass)
3189 {
3190         int ret;
3191         struct lock_list root;
3192         struct lock_list *uninitialized_var(target_entry);
3193
3194         root.parent = NULL;
3195         root.class = hlock_class(this);
3196         ret = find_usage_forwards(&root, lock_flag(bit), &target_entry);
3197         if (ret < 0) {
3198                 print_bfs_bug(ret);
3199                 return 0;
3200         }
3201         if (ret == 1)
3202                 return ret;
3203
3204         print_irq_inversion_bug(curr, &root, target_entry,
3205                                 this, 1, irqclass);
3206         return 0;
3207 }
3208
3209 /*
3210  * Prove that in the backwards-direction subgraph starting at <this>
3211  * there is no lock matching <mask>:
3212  */
3213 static int
3214 check_usage_backwards(struct task_struct *curr, struct held_lock *this,
3215                       enum lock_usage_bit bit, const char *irqclass)
3216 {
3217         int ret;
3218         struct lock_list root;
3219         struct lock_list *uninitialized_var(target_entry);
3220
3221         root.parent = NULL;
3222         root.class = hlock_class(this);
3223         ret = find_usage_backwards(&root, lock_flag(bit), &target_entry);
3224         if (ret < 0) {
3225                 print_bfs_bug(ret);
3226                 return 0;
3227         }
3228         if (ret == 1)
3229                 return ret;
3230
3231         print_irq_inversion_bug(curr, &root, target_entry,
3232                                 this, 0, irqclass);
3233         return 0;
3234 }
3235
3236 void print_irqtrace_events(struct task_struct *curr)
3237 {
3238         printk("irq event stamp: %u\n", curr->irq_events);
3239         printk("hardirqs last  enabled at (%u): [<%px>] %pS\n",
3240                 curr->hardirq_enable_event, (void *)curr->hardirq_enable_ip,
3241                 (void *)curr->hardirq_enable_ip);
3242         printk("hardirqs last disabled at (%u): [<%px>] %pS\n",
3243                 curr->hardirq_disable_event, (void *)curr->hardirq_disable_ip,
3244                 (void *)curr->hardirq_disable_ip);
3245         printk("softirqs last  enabled at (%u): [<%px>] %pS\n",
3246                 curr->softirq_enable_event, (void *)curr->softirq_enable_ip,
3247                 (void *)curr->softirq_enable_ip);
3248         printk("softirqs last disabled at (%u): [<%px>] %pS\n",
3249                 curr->softirq_disable_event, (void *)curr->softirq_disable_ip,
3250                 (void *)curr->softirq_disable_ip);
3251 }
3252
3253 static int HARDIRQ_verbose(struct lock_class *class)
3254 {
3255 #if HARDIRQ_VERBOSE
3256         return class_filter(class);
3257 #endif
3258         return 0;
3259 }
3260
3261 static int SOFTIRQ_verbose(struct lock_class *class)
3262 {
3263 #if SOFTIRQ_VERBOSE
3264         return class_filter(class);
3265 #endif
3266         return 0;
3267 }
3268
3269 #define STRICT_READ_CHECKS      1
3270
3271 static int (*state_verbose_f[])(struct lock_class *class) = {
3272 #define LOCKDEP_STATE(__STATE) \
3273         __STATE##_verbose,
3274 #include "lockdep_states.h"
3275 #undef LOCKDEP_STATE
3276 };
3277
3278 static inline int state_verbose(enum lock_usage_bit bit,
3279                                 struct lock_class *class)
3280 {
3281         return state_verbose_f[bit >> LOCK_USAGE_DIR_MASK](class);
3282 }
3283
3284 typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
3285                              enum lock_usage_bit bit, const char *name);
3286
3287 static int
3288 mark_lock_irq(struct task_struct *curr, struct held_lock *this,
3289                 enum lock_usage_bit new_bit)
3290 {
3291         int excl_bit = exclusive_bit(new_bit);
3292         int read = new_bit & LOCK_USAGE_READ_MASK;
3293         int dir = new_bit & LOCK_USAGE_DIR_MASK;
3294
3295         /*
3296          * mark USED_IN has to look forwards -- to ensure no dependency
3297          * has ENABLED state, which would allow recursion deadlocks.
3298          *
3299          * mark ENABLED has to look backwards -- to ensure no dependee
3300          * has USED_IN state, which, again, would allow  recursion deadlocks.
3301          */
3302         check_usage_f usage = dir ?
3303                 check_usage_backwards : check_usage_forwards;
3304
3305         /*
3306          * Validate that this particular lock does not have conflicting
3307          * usage states.
3308          */
3309         if (!valid_state(curr, this, new_bit, excl_bit))
3310                 return 0;
3311
3312         /*
3313          * Validate that the lock dependencies don't have conflicting usage
3314          * states.
3315          */
3316         if ((!read || STRICT_READ_CHECKS) &&
3317                         !usage(curr, this, excl_bit, state_name(new_bit & ~LOCK_USAGE_READ_MASK)))
3318                 return 0;
3319
3320         /*
3321          * Check for read in write conflicts
3322          */
3323         if (!read) {
3324                 if (!valid_state(curr, this, new_bit, excl_bit + LOCK_USAGE_READ_MASK))
3325                         return 0;
3326
3327                 if (STRICT_READ_CHECKS &&
3328                         !usage(curr, this, excl_bit + LOCK_USAGE_READ_MASK,
3329                                 state_name(new_bit + LOCK_USAGE_READ_MASK)))
3330                         return 0;
3331         }
3332
3333         if (state_verbose(new_bit, hlock_class(this)))
3334                 return 2;
3335
3336         return 1;
3337 }
3338
3339 /*
3340  * Mark all held locks with a usage bit:
3341  */
3342 static int
3343 mark_held_locks(struct task_struct *curr, enum lock_usage_bit base_bit)
3344 {
3345         struct held_lock *hlock;
3346         int i;
3347
3348         for (i = 0; i < curr->lockdep_depth; i++) {
3349                 enum lock_usage_bit hlock_bit = base_bit;
3350