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