projects/linux·blob v2.6.21 · refs

2799 lines · 69.5 KiB

1/*
2 * kernel/lockdep.c
3 *
4 * Runtime locking correctness validator
5 *
6 * Started by Ingo Molnar:
7 *
8 * Copyright (C) 2006 Red Hat, Inc., Ingo Molnar <[email protected]>
9 *
10 * this code maps all the lock dependencies as they occur in a live kernel
11 * and will warn about the following classes of locking bugs:
12 *
13 * - lock inversion scenarios
14 * - circular lock dependencies
15 * - hardirq/softirq safe/unsafe locking bugs
16 *
17 * Bugs are reported even if the current locking scenario does not cause
18 * any deadlock at this point.
19 *
20 * I.e. if anytime in the past two locks were taken in a different order,
21 * even if it happened for another task, even if those were different
22 * locks (but of the same class as this lock), this code will detect it.
23 *
24 * Thanks to Arjan van de Ven for coming up with the initial idea of
25 * mapping lock dependencies runtime.
26 */
27#include <linux/mutex.h>
28#include <linux/sched.h>
29#include <linux/delay.h>
30#include <linux/module.h>
31#include <linux/proc_fs.h>
32#include <linux/seq_file.h>
33#include <linux/spinlock.h>
34#include <linux/kallsyms.h>
35#include <linux/interrupt.h>
36#include <linux/stacktrace.h>
37#include <linux/debug_locks.h>
38#include <linux/irqflags.h>
39#include <linux/utsname.h>
40
41#include <asm/sections.h>
42
43#include "lockdep_internals.h"
44
45/*
46 * lockdep_lock: protects the lockdep graph, the hashes and the
47 * class/list/hash allocators.
48 *
49 * This is one of the rare exceptions where it's justified
50 * to use a raw spinlock - we really dont want the spinlock
51 * code to recurse back into the lockdep code...
52 */
53static raw_spinlock_t lockdep_lock = (raw_spinlock_t)__RAW_SPIN_LOCK_UNLOCKED;
54
55static int graph_lock(void)
56{
57 __raw_spin_lock(&lockdep_lock);
58 /*
59 * Make sure that if another CPU detected a bug while
60 * walking the graph we dont change it (while the other
61 * CPU is busy printing out stuff with the graph lock
62 * dropped already)
63 */
64 if (!debug_locks) {
65 __raw_spin_unlock(&lockdep_lock);
66 return 0;
67 }
68 return 1;
69}
70
71static inline int graph_unlock(void)
72{
73 if (debug_locks && !__raw_spin_is_locked(&lockdep_lock))
74 return DEBUG_LOCKS_WARN_ON(1);
75
76 __raw_spin_unlock(&lockdep_lock);
77 return 0;
78}
79
80/*
81 * Turn lock debugging off and return with 0 if it was off already,
82 * and also release the graph lock:
83 */
84static inline int debug_locks_off_graph_unlock(void)
85{
86 int ret = debug_locks_off();
87
88 __raw_spin_unlock(&lockdep_lock);
89
90 return ret;
91}
92
93static int lockdep_initialized;
94
95unsigned long nr_list_entries;
96static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
97
98/*
99 * Allocate a lockdep entry. (assumes the graph_lock held, returns
100 * with NULL on failure)
101 */
102static struct lock_list *alloc_list_entry(void)
103{
104 if (nr_list_entries >= MAX_LOCKDEP_ENTRIES) {
105 if (!debug_locks_off_graph_unlock())
106 return NULL;
107
108 printk("BUG: MAX_LOCKDEP_ENTRIES too low!\n");
109 printk("turning off the locking correctness validator.\n");
110 return NULL;
111 }
112 return list_entries + nr_list_entries++;
113}
114
115/*
116 * All data structures here are protected by the global debug_lock.
117 *
118 * Mutex key structs only get allocated, once during bootup, and never
119 * get freed - this significantly simplifies the debugging code.
120 */
121unsigned long nr_lock_classes;
122static struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
123
124/*
125 * We keep a global list of all lock classes. The list only grows,
126 * never shrinks. The list is only accessed with the lockdep
127 * spinlock lock held.
128 */
129LIST_HEAD(all_lock_classes);
130
131/*
132 * The lockdep classes are in a hash-table as well, for fast lookup:
133 */
134#define CLASSHASH_BITS (MAX_LOCKDEP_KEYS_BITS - 1)
135#define CLASSHASH_SIZE (1UL << CLASSHASH_BITS)
136#define CLASSHASH_MASK (CLASSHASH_SIZE - 1)
137#define __classhashfn(key) ((((unsigned long)key >> CLASSHASH_BITS) + (unsigned long)key) & CLASSHASH_MASK)
138#define classhashentry(key) (classhash_table + __classhashfn((key)))
139
140static struct list_head classhash_table[CLASSHASH_SIZE];
141
142unsigned long nr_lock_chains;
143static struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS];
144
145/*
146 * We put the lock dependency chains into a hash-table as well, to cache
147 * their existence:
148 */
149#define CHAINHASH_BITS (MAX_LOCKDEP_CHAINS_BITS-1)
150#define CHAINHASH_SIZE (1UL << CHAINHASH_BITS)
151#define CHAINHASH_MASK (CHAINHASH_SIZE - 1)
152#define __chainhashfn(chain) \
153 (((chain >> CHAINHASH_BITS) + chain) & CHAINHASH_MASK)
154#define chainhashentry(chain) (chainhash_table + __chainhashfn((chain)))
155
156static struct list_head chainhash_table[CHAINHASH_SIZE];
157
158/*
159 * The hash key of the lock dependency chains is a hash itself too:
160 * it's a hash of all locks taken up to that lock, including that lock.
161 * It's a 64-bit hash, because it's important for the keys to be
162 * unique.
163 */
164#define iterate_chain_key(key1, key2) \
165 (((key1) << MAX_LOCKDEP_KEYS_BITS) ^ \
166 ((key1) >> (64-MAX_LOCKDEP_KEYS_BITS)) ^ \
167 (key2))
168
169void lockdep_off(void)
170{
171 current->lockdep_recursion++;
172}
173
174EXPORT_SYMBOL(lockdep_off);
175
176void lockdep_on(void)
177{
178 current->lockdep_recursion--;
179}
180
181EXPORT_SYMBOL(lockdep_on);
182
183/*
184 * Debugging switches:
185 */
186
187#define VERBOSE 0
188#define VERY_VERBOSE 0
189
190#if VERBOSE
191# define HARDIRQ_VERBOSE 1
192# define SOFTIRQ_VERBOSE 1
193#else
194# define HARDIRQ_VERBOSE 0
195# define SOFTIRQ_VERBOSE 0
196#endif
197
198#if VERBOSE || HARDIRQ_VERBOSE || SOFTIRQ_VERBOSE
199/*
200 * Quick filtering for interesting events:
201 */
202static int class_filter(struct lock_class *class)
203{
204#if 0
205 /* Example */
206 if (class->name_version == 1 &&
207 !strcmp(class->name, "lockname"))
208 return 1;
209 if (class->name_version == 1 &&
210 !strcmp(class->name, "&struct->lockfield"))
211 return 1;
212#endif
213 /* Filter everything else. 1 would be to allow everything else */
214 return 0;
215}
216#endif
217
218static int verbose(struct lock_class *class)
219{
220#if VERBOSE
221 return class_filter(class);
222#endif
223 return 0;
224}
225
226#ifdef CONFIG_TRACE_IRQFLAGS
227
228static int hardirq_verbose(struct lock_class *class)
229{
230#if HARDIRQ_VERBOSE
231 return class_filter(class);
232#endif
233 return 0;
234}
235
236static int softirq_verbose(struct lock_class *class)
237{
238#if SOFTIRQ_VERBOSE
239 return class_filter(class);
240#endif
241 return 0;
242}
243
244#endif
245
246/*
247 * Stack-trace: tightly packed array of stack backtrace
248 * addresses. Protected by the graph_lock.
249 */
250unsigned long nr_stack_trace_entries;
251static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES];
252
253static int save_trace(struct stack_trace *trace)
254{
255 trace->nr_entries = 0;
256 trace->max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries;
257 trace->entries = stack_trace + nr_stack_trace_entries;
258
259 trace->skip = 3;
260 trace->all_contexts = 0;
261
262 save_stack_trace(trace, NULL);
263
264 trace->max_entries = trace->nr_entries;
265
266 nr_stack_trace_entries += trace->nr_entries;
267
268 if (nr_stack_trace_entries == MAX_STACK_TRACE_ENTRIES) {
269 if (!debug_locks_off_graph_unlock())
270 return 0;
271
272 printk("BUG: MAX_STACK_TRACE_ENTRIES too low!\n");
273 printk("turning off the locking correctness validator.\n");
274 dump_stack();
275
276 return 0;
277 }
278
279 return 1;
280}
281
282unsigned int nr_hardirq_chains;
283unsigned int nr_softirq_chains;
284unsigned int nr_process_chains;
285unsigned int max_lockdep_depth;
286unsigned int max_recursion_depth;
287
288#ifdef CONFIG_DEBUG_LOCKDEP
289/*
290 * We cannot printk in early bootup code. Not even early_printk()
291 * might work. So we mark any initialization errors and printk
292 * about it later on, in lockdep_info().
293 */
294static int lockdep_init_error;
295
296/*
297 * Various lockdep statistics:
298 */
299atomic_t chain_lookup_hits;
300atomic_t chain_lookup_misses;
301atomic_t hardirqs_on_events;
302atomic_t hardirqs_off_events;
303atomic_t redundant_hardirqs_on;
304atomic_t redundant_hardirqs_off;
305atomic_t softirqs_on_events;
306atomic_t softirqs_off_events;
307atomic_t redundant_softirqs_on;
308atomic_t redundant_softirqs_off;
309atomic_t nr_unused_locks;
310atomic_t nr_cyclic_checks;
311atomic_t nr_cyclic_check_recursions;
312atomic_t nr_find_usage_forwards_checks;
313atomic_t nr_find_usage_forwards_recursions;
314atomic_t nr_find_usage_backwards_checks;
315atomic_t nr_find_usage_backwards_recursions;
316# define debug_atomic_inc(ptr) atomic_inc(ptr)
317# define debug_atomic_dec(ptr) atomic_dec(ptr)
318# define debug_atomic_read(ptr) atomic_read(ptr)
319#else
320# define debug_atomic_inc(ptr) do { } while (0)
321# define debug_atomic_dec(ptr) do { } while (0)
322# define debug_atomic_read(ptr) 0
323#endif
324
325/*
326 * Locking printouts:
327 */
328
329static const char *usage_str[] =
330{
331 [LOCK_USED] = "initial-use ",
332 [LOCK_USED_IN_HARDIRQ] = "in-hardirq-W",
333 [LOCK_USED_IN_SOFTIRQ] = "in-softirq-W",
334 [LOCK_ENABLED_SOFTIRQS] = "softirq-on-W",
335 [LOCK_ENABLED_HARDIRQS] = "hardirq-on-W",
336 [LOCK_USED_IN_HARDIRQ_READ] = "in-hardirq-R",
337 [LOCK_USED_IN_SOFTIRQ_READ] = "in-softirq-R",
338 [LOCK_ENABLED_SOFTIRQS_READ] = "softirq-on-R",
339 [LOCK_ENABLED_HARDIRQS_READ] = "hardirq-on-R",
340};
341
342const char * __get_key_name(struct lockdep_subclass_key *key, char *str)
343{
344 unsigned long offs, size;
345 char *modname;
346
347 return kallsyms_lookup((unsigned long)key, &size, &offs, &modname, str);
348}
349
350void
351get_usage_chars(struct lock_class *class, char *c1, char *c2, char *c3, char *c4)
352{
353 *c1 = '.', *c2 = '.', *c3 = '.', *c4 = '.';
354
355 if (class->usage_mask & LOCKF_USED_IN_HARDIRQ)
356 *c1 = '+';
357 else
358 if (class->usage_mask & LOCKF_ENABLED_HARDIRQS)
359 *c1 = '-';
360
361 if (class->usage_mask & LOCKF_USED_IN_SOFTIRQ)
362 *c2 = '+';
363 else
364 if (class->usage_mask & LOCKF_ENABLED_SOFTIRQS)
365 *c2 = '-';
366
367 if (class->usage_mask & LOCKF_ENABLED_HARDIRQS_READ)
368 *c3 = '-';
369 if (class->usage_mask & LOCKF_USED_IN_HARDIRQ_READ) {
370 *c3 = '+';
371 if (class->usage_mask & LOCKF_ENABLED_HARDIRQS_READ)
372 *c3 = '?';
373 }
374
375 if (class->usage_mask & LOCKF_ENABLED_SOFTIRQS_READ)
376 *c4 = '-';
377 if (class->usage_mask & LOCKF_USED_IN_SOFTIRQ_READ) {
378 *c4 = '+';
379 if (class->usage_mask & LOCKF_ENABLED_SOFTIRQS_READ)
380 *c4 = '?';
381 }
382}
383
384static void print_lock_name(struct lock_class *class)
385{
386 char str[KSYM_NAME_LEN + 1], c1, c2, c3, c4;
387 const char *name;
388
389 get_usage_chars(class, &c1, &c2, &c3, &c4);
390
391 name = class->name;
392 if (!name) {
393 name = __get_key_name(class->key, str);
394 printk(" (%s", name);
395 } else {
396 printk(" (%s", name);
397 if (class->name_version > 1)
398 printk("#%d", class->name_version);
399 if (class->subclass)
400 printk("/%d", class->subclass);
401 }
402 printk("){%c%c%c%c}", c1, c2, c3, c4);
403}
404
405static void print_lockdep_cache(struct lockdep_map *lock)
406{
407 const char *name;
408 char str[KSYM_NAME_LEN + 1];
409
410 name = lock->name;
411 if (!name)
412 name = __get_key_name(lock->key->subkeys, str);
413
414 printk("%s", name);
415}
416
417static void print_lock(struct held_lock *hlock)
418{
419 print_lock_name(hlock->class);
420 printk(", at: ");
421 print_ip_sym(hlock->acquire_ip);
422}
423
424static void lockdep_print_held_locks(struct task_struct *curr)
425{
426 int i, depth = curr->lockdep_depth;
427
428 if (!depth) {
429 printk("no locks held by %s/%d.\n", curr->comm, curr->pid);
430 return;
431 }
432 printk("%d lock%s held by %s/%d:\n",
433 depth, depth > 1 ? "s" : "", curr->comm, curr->pid);
434
435 for (i = 0; i < depth; i++) {
436 printk(" #%d: ", i);
437 print_lock(curr->held_locks + i);
438 }
439}
440
441static void print_lock_class_header(struct lock_class *class, int depth)
442{
443 int bit;
444
445 printk("%*s->", depth, "");
446 print_lock_name(class);
447 printk(" ops: %lu", class->ops);
448 printk(" {\n");
449
450 for (bit = 0; bit < LOCK_USAGE_STATES; bit++) {
451 if (class->usage_mask & (1 << bit)) {
452 int len = depth;
453
454 len += printk("%*s %s", depth, "", usage_str[bit]);
455 len += printk(" at:\n");
456 print_stack_trace(class->usage_traces + bit, len);
457 }
458 }
459 printk("%*s }\n", depth, "");
460
461 printk("%*s ... key at: ",depth,"");
462 print_ip_sym((unsigned long)class->key);
463}
464
465/*
466 * printk all lock dependencies starting at <entry>:
467 */
468static void print_lock_dependencies(struct lock_class *class, int depth)
469{
470 struct lock_list *entry;
471
472 if (DEBUG_LOCKS_WARN_ON(depth >= 20))
473 return;
474
475 print_lock_class_header(class, depth);
476
477 list_for_each_entry(entry, &class->locks_after, entry) {
478 if (DEBUG_LOCKS_WARN_ON(!entry->class))
479 return;
480
481 print_lock_dependencies(entry->class, depth + 1);
482
483 printk("%*s ... acquired at:\n",depth,"");
484 print_stack_trace(&entry->trace, 2);
485 printk("\n");
486 }
487}
488
489/*
490 * Add a new dependency to the head of the list:
491 */
492static int add_lock_to_list(struct lock_class *class, struct lock_class *this,
493 struct list_head *head, unsigned long ip, int distance)
494{
495 struct lock_list *entry;
496 /*
497 * Lock not present yet - get a new dependency struct and
498 * add it to the list:
499 */
500 entry = alloc_list_entry();
501 if (!entry)
502 return 0;
503
504 entry->class = this;
505 entry->distance = distance;
506 if (!save_trace(&entry->trace))
507 return 0;
508
509 /*
510 * Since we never remove from the dependency list, the list can
511 * be walked lockless by other CPUs, it's only allocation
512 * that must be protected by the spinlock. But this also means
513 * we must make new entries visible only once writes to the
514 * entry become visible - hence the RCU op:
515 */
516 list_add_tail_rcu(&entry->entry, head);
517
518 return 1;
519}
520
521/*
522 * Recursive, forwards-direction lock-dependency checking, used for
523 * both noncyclic checking and for hardirq-unsafe/softirq-unsafe
524 * checking.
525 *
526 * (to keep the stackframe of the recursive functions small we
527 * use these global variables, and we also mark various helper
528 * functions as noinline.)
529 */
530static struct held_lock *check_source, *check_target;
531
532/*
533 * Print a dependency chain entry (this is only done when a deadlock
534 * has been detected):
535 */
536static noinline int
537print_circular_bug_entry(struct lock_list *target, unsigned int depth)
538{
539 if (debug_locks_silent)
540 return 0;
541 printk("\n-> #%u", depth);
542 print_lock_name(target->class);
543 printk(":\n");
544 print_stack_trace(&target->trace, 6);
545
546 return 0;
547}
548
549static void print_kernel_version(void)
550{
551 printk("%s %.*s\n", init_utsname()->release,
552 (int)strcspn(init_utsname()->version, " "),
553 init_utsname()->version);
554}
555
556/*
557 * When a circular dependency is detected, print the
558 * header first:
559 */
560static noinline int
561print_circular_bug_header(struct lock_list *entry, unsigned int depth)
562{
563 struct task_struct *curr = current;
564
565 if (!debug_locks_off_graph_unlock() || debug_locks_silent)
566 return 0;
567
568 printk("\n=======================================================\n");
569 printk( "[ INFO: possible circular locking dependency detected ]\n");
570 print_kernel_version();
571 printk( "-------------------------------------------------------\n");
572 printk("%s/%d is trying to acquire lock:\n",
573 curr->comm, curr->pid);
574 print_lock(check_source);
575 printk("\nbut task is already holding lock:\n");
576 print_lock(check_target);
577 printk("\nwhich lock already depends on the new lock.\n\n");
578 printk("\nthe existing dependency chain (in reverse order) is:\n");
579
580 print_circular_bug_entry(entry, depth);
581
582 return 0;
583}
584
585static noinline int print_circular_bug_tail(void)
586{
587 struct task_struct *curr = current;
588 struct lock_list this;
589
590 if (debug_locks_silent)
591 return 0;
592
593 this.class = check_source->class;
594 if (!save_trace(&this.trace))
595 return 0;
596
597 print_circular_bug_entry(&this, 0);
598
599 printk("\nother info that might help us debug this:\n\n");
600 lockdep_print_held_locks(curr);
601
602 printk("\nstack backtrace:\n");
603 dump_stack();
604
605 return 0;
606}
607
608#define RECURSION_LIMIT 40
609
610static int noinline print_infinite_recursion_bug(void)
611{
612 if (!debug_locks_off_graph_unlock())
613 return 0;
614
615 WARN_ON(1);
616
617 return 0;
618}
619
620/*
621 * Prove that the dependency graph starting at <entry> can not
622 * lead to <target>. Print an error and return 0 if it does.
623 */
624static noinline int
625check_noncircular(struct lock_class *source, unsigned int depth)
626{
627 struct lock_list *entry;
628
629 debug_atomic_inc(&nr_cyclic_check_recursions);
630 if (depth > max_recursion_depth)
631 max_recursion_depth = depth;
632 if (depth >= RECURSION_LIMIT)
633 return print_infinite_recursion_bug();
634 /*
635 * Check this lock's dependency list:
636 */
637 list_for_each_entry(entry, &source->locks_after, entry) {
638 if (entry->class == check_target->class)
639 return print_circular_bug_header(entry, depth+1);
640 debug_atomic_inc(&nr_cyclic_checks);
641 if (!check_noncircular(entry->class, depth+1))
642 return print_circular_bug_entry(entry, depth+1);
643 }
644 return 1;
645}
646
647static int very_verbose(struct lock_class *class)
648{
649#if VERY_VERBOSE
650 return class_filter(class);
651#endif
652 return 0;
653}
654#ifdef CONFIG_TRACE_IRQFLAGS
655
656/*
657 * Forwards and backwards subgraph searching, for the purposes of
658 * proving that two subgraphs can be connected by a new dependency
659 * without creating any illegal irq-safe -> irq-unsafe lock dependency.
660 */
661static enum lock_usage_bit find_usage_bit;
662static struct lock_class *forwards_match, *backwards_match;
663
664/*
665 * Find a node in the forwards-direction dependency sub-graph starting
666 * at <source> that matches <find_usage_bit>.
667 *
668 * Return 2 if such a node exists in the subgraph, and put that node
669 * into <forwards_match>.
670 *
671 * Return 1 otherwise and keep <forwards_match> unchanged.
672 * Return 0 on error.
673 */
674static noinline int
675find_usage_forwards(struct lock_class *source, unsigned int depth)
676{
677 struct lock_list *entry;
678 int ret;
679
680 if (depth > max_recursion_depth)
681 max_recursion_depth = depth;
682 if (depth >= RECURSION_LIMIT)
683 return print_infinite_recursion_bug();
684
685 debug_atomic_inc(&nr_find_usage_forwards_checks);
686 if (source->usage_mask & (1 << find_usage_bit)) {
687 forwards_match = source;
688 return 2;
689 }
690
691 /*
692 * Check this lock's dependency list:
693 */
694 list_for_each_entry(entry, &source->locks_after, entry) {
695 debug_atomic_inc(&nr_find_usage_forwards_recursions);
696 ret = find_usage_forwards(entry->class, depth+1);
697 if (ret == 2 || ret == 0)
698 return ret;
699 }
700 return 1;
701}
702
703/*
704 * Find a node in the backwards-direction dependency sub-graph starting
705 * at <source> that matches <find_usage_bit>.
706 *
707 * Return 2 if such a node exists in the subgraph, and put that node
708 * into <backwards_match>.
709 *
710 * Return 1 otherwise and keep <backwards_match> unchanged.
711 * Return 0 on error.
712 */
713static noinline int
714find_usage_backwards(struct lock_class *source, unsigned int depth)
715{
716 struct lock_list *entry;
717 int ret;
718
719 if (!__raw_spin_is_locked(&lockdep_lock))
720 return DEBUG_LOCKS_WARN_ON(1);
721
722 if (depth > max_recursion_depth)
723 max_recursion_depth = depth;
724 if (depth >= RECURSION_LIMIT)
725 return print_infinite_recursion_bug();
726
727 debug_atomic_inc(&nr_find_usage_backwards_checks);
728 if (source->usage_mask & (1 << find_usage_bit)) {
729 backwards_match = source;
730 return 2;
731 }
732
733 /*
734 * Check this lock's dependency list:
735 */
736 list_for_each_entry(entry, &source->locks_before, entry) {
737 debug_atomic_inc(&nr_find_usage_backwards_recursions);
738 ret = find_usage_backwards(entry->class, depth+1);
739 if (ret == 2 || ret == 0)
740 return ret;
741 }
742 return 1;
743}
744
745static int
746print_bad_irq_dependency(struct task_struct *curr,
747 struct held_lock *prev,
748 struct held_lock *next,
749 enum lock_usage_bit bit1,
750 enum lock_usage_bit bit2,
751 const char *irqclass)
752{
753 if (!debug_locks_off_graph_unlock() || debug_locks_silent)
754 return 0;
755
756 printk("\n======================================================\n");
757 printk( "[ INFO: %s-safe -> %s-unsafe lock order detected ]\n",
758 irqclass, irqclass);
759 print_kernel_version();
760 printk( "------------------------------------------------------\n");
761 printk("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] is trying to acquire:\n",
762 curr->comm, curr->pid,
763 curr->hardirq_context, hardirq_count() >> HARDIRQ_SHIFT,
764 curr->softirq_context, softirq_count() >> SOFTIRQ_SHIFT,
765 curr->hardirqs_enabled,
766 curr->softirqs_enabled);
767 print_lock(next);
768
769 printk("\nand this task is already holding:\n");
770 print_lock(prev);
771 printk("which would create a new lock dependency:\n");
772 print_lock_name(prev->class);
773 printk(" ->");
774 print_lock_name(next->class);
775 printk("\n");
776
777 printk("\nbut this new dependency connects a %s-irq-safe lock:\n",
778 irqclass);
779 print_lock_name(backwards_match);
780 printk("\n... which became %s-irq-safe at:\n", irqclass);
781
782 print_stack_trace(backwards_match->usage_traces + bit1, 1);
783
784 printk("\nto a %s-irq-unsafe lock:\n", irqclass);
785 print_lock_name(forwards_match);
786 printk("\n... which became %s-irq-unsafe at:\n", irqclass);
787 printk("...");
788
789 print_stack_trace(forwards_match->usage_traces + bit2, 1);
790
791 printk("\nother info that might help us debug this:\n\n");
792 lockdep_print_held_locks(curr);
793
794 printk("\nthe %s-irq-safe lock's dependencies:\n", irqclass);
795 print_lock_dependencies(backwards_match, 0);
796
797 printk("\nthe %s-irq-unsafe lock's dependencies:\n", irqclass);
798 print_lock_dependencies(forwards_match, 0);
799
800 printk("\nstack backtrace:\n");
801 dump_stack();
802
803 return 0;
804}
805
806static int
807check_usage(struct task_struct *curr, struct held_lock *prev,
808 struct held_lock *next, enum lock_usage_bit bit_backwards,
809 enum lock_usage_bit bit_forwards, const char *irqclass)
810{
811 int ret;
812
813 find_usage_bit = bit_backwards;
814 /* fills in <backwards_match> */
815 ret = find_usage_backwards(prev->class, 0);
816 if (!ret || ret == 1)
817 return ret;
818
819 find_usage_bit = bit_forwards;
820 ret = find_usage_forwards(next->class, 0);
821 if (!ret || ret == 1)
822 return ret;
823 /* ret == 2 */
824 return print_bad_irq_dependency(curr, prev, next,
825 bit_backwards, bit_forwards, irqclass);
826}
827
828#endif
829
830static int
831print_deadlock_bug(struct task_struct *curr, struct held_lock *prev,
832 struct held_lock *next)
833{
834 if (!debug_locks_off_graph_unlock() || debug_locks_silent)
835 return 0;
836
837 printk("\n=============================================\n");
838 printk( "[ INFO: possible recursive locking detected ]\n");
839 print_kernel_version();
840 printk( "---------------------------------------------\n");
841 printk("%s/%d is trying to acquire lock:\n",
842 curr->comm, curr->pid);
843 print_lock(next);
844 printk("\nbut task is already holding lock:\n");
845 print_lock(prev);
846
847 printk("\nother info that might help us debug this:\n");
848 lockdep_print_held_locks(curr);
849
850 printk("\nstack backtrace:\n");
851 dump_stack();
852
853 return 0;
854}
855
856/*
857 * Check whether we are holding such a class already.
858 *
859 * (Note that this has to be done separately, because the graph cannot
860 * detect such classes of deadlocks.)
861 *
862 * Returns: 0 on deadlock detected, 1 on OK, 2 on recursive read
863 */
864static int
865check_deadlock(struct task_struct *curr, struct held_lock *next,
866 struct lockdep_map *next_instance, int read)
867{
868 struct held_lock *prev;
869 int i;
870
871 for (i = 0; i < curr->lockdep_depth; i++) {
872 prev = curr->held_locks + i;
873 if (prev->class != next->class)
874 continue;
875 /*
876 * Allow read-after-read recursion of the same
877 * lock class (i.e. read_lock(lock)+read_lock(lock)):
878 */
879 if ((read == 2) && prev->read)
880 return 2;
881 return print_deadlock_bug(curr, prev, next);
882 }
883 return 1;
884}
885
886/*
887 * There was a chain-cache miss, and we are about to add a new dependency
888 * to a previous lock. We recursively validate the following rules:
889 *
890 * - would the adding of the <prev> -> <next> dependency create a
891 * circular dependency in the graph? [== circular deadlock]
892 *
893 * - does the new prev->next dependency connect any hardirq-safe lock
894 * (in the full backwards-subgraph starting at <prev>) with any
895 * hardirq-unsafe lock (in the full forwards-subgraph starting at
896 * <next>)? [== illegal lock inversion with hardirq contexts]
897 *
898 * - does the new prev->next dependency connect any softirq-safe lock
899 * (in the full backwards-subgraph starting at <prev>) with any
900 * softirq-unsafe lock (in the full forwards-subgraph starting at
901 * <next>)? [== illegal lock inversion with softirq contexts]
902 *
903 * any of these scenarios could lead to a deadlock.
904 *
905 * Then if all the validations pass, we add the forwards and backwards
906 * dependency.
907 */
908static int
909check_prev_add(struct task_struct *curr, struct held_lock *prev,
910 struct held_lock *next, int distance)
911{
912 struct lock_list *entry;
913 int ret;
914
915 /*
916 * Prove that the new <prev> -> <next> dependency would not
917 * create a circular dependency in the graph. (We do this by
918 * forward-recursing into the graph starting at <next>, and
919 * checking whether we can reach <prev>.)
920 *
921 * We are using global variables to control the recursion, to
922 * keep the stackframe size of the recursive functions low:
923 */
924 check_source = next;
925 check_target = prev;
926 if (!(check_noncircular(next->class, 0)))
927 return print_circular_bug_tail();
928
929#ifdef CONFIG_TRACE_IRQFLAGS
930 /*
931 * Prove that the new dependency does not connect a hardirq-safe
932 * lock with a hardirq-unsafe lock - to achieve this we search
933 * the backwards-subgraph starting at <prev>, and the
934 * forwards-subgraph starting at <next>:
935 */
936 if (!check_usage(curr, prev, next, LOCK_USED_IN_HARDIRQ,
937 LOCK_ENABLED_HARDIRQS, "hard"))
938 return 0;
939
940 /*
941 * Prove that the new dependency does not connect a hardirq-safe-read
942 * lock with a hardirq-unsafe lock - to achieve this we search
943 * the backwards-subgraph starting at <prev>, and the
944 * forwards-subgraph starting at <next>:
945 */
946 if (!check_usage(curr, prev, next, LOCK_USED_IN_HARDIRQ_READ,
947 LOCK_ENABLED_HARDIRQS, "hard-read"))
948 return 0;
949
950 /*
951 * Prove that the new dependency does not connect a softirq-safe
952 * lock with a softirq-unsafe lock - to achieve this we search
953 * the backwards-subgraph starting at <prev>, and the
954 * forwards-subgraph starting at <next>:
955 */
956 if (!check_usage(curr, prev, next, LOCK_USED_IN_SOFTIRQ,
957 LOCK_ENABLED_SOFTIRQS, "soft"))
958 return 0;
959 /*
960 * Prove that the new dependency does not connect a softirq-safe-read
961 * lock with a softirq-unsafe lock - to achieve this we search
962 * the backwards-subgraph starting at <prev>, and the
963 * forwards-subgraph starting at <next>:
964 */
965 if (!check_usage(curr, prev, next, LOCK_USED_IN_SOFTIRQ_READ,
966 LOCK_ENABLED_SOFTIRQS, "soft"))
967 return 0;
968#endif
969 /*
970 * For recursive read-locks we do all the dependency checks,
971 * but we dont store read-triggered dependencies (only
972 * write-triggered dependencies). This ensures that only the
973 * write-side dependencies matter, and that if for example a
974 * write-lock never takes any other locks, then the reads are
975 * equivalent to a NOP.
976 */
977 if (next->read == 2 || prev->read == 2)
978 return 1;
979 /*
980 * Is the <prev> -> <next> dependency already present?
981 *
982 * (this may occur even though this is a new chain: consider
983 * e.g. the L1 -> L2 -> L3 -> L4 and the L5 -> L1 -> L2 -> L3
984 * chains - the second one will be new, but L1 already has
985 * L2 added to its dependency list, due to the first chain.)
986 */
987 list_for_each_entry(entry, &prev->class->locks_after, entry) {
988 if (entry->class == next->class) {
989 if (distance == 1)
990 entry->distance = 1;
991 return 2;
992 }
993 }
994
995 /*
996 * Ok, all validations passed, add the new lock
997 * to the previous lock's dependency list:
998 */
999 ret = add_lock_to_list(prev->class, next->class,
1000 &prev->class->locks_after, next->acquire_ip, distance);
1001
1002 if (!ret)
1003 return 0;
1004
1005 ret = add_lock_to_list(next->class, prev->class,
1006 &next->class->locks_before, next->acquire_ip, distance);
1007 if (!ret)
1008 return 0;
1009
1010 /*
1011 * Debugging printouts:
1012 */
1013 if (verbose(prev->class) || verbose(next->class)) {
1014 graph_unlock();
1015 printk("\n new dependency: ");
1016 print_lock_name(prev->class);
1017 printk(" => ");
1018 print_lock_name(next->class);
1019 printk("\n");
1020 dump_stack();
1021 return graph_lock();
1022 }
1023 return 1;
1024}
1025
1026/*
1027 * Add the dependency to all directly-previous locks that are 'relevant'.
1028 * The ones that are relevant are (in increasing distance from curr):
1029 * all consecutive trylock entries and the final non-trylock entry - or
1030 * the end of this context's lock-chain - whichever comes first.
1031 */
1032static int
1033check_prevs_add(struct task_struct *curr, struct held_lock *next)
1034{
1035 int depth = curr->lockdep_depth;
1036 struct held_lock *hlock;
1037
1038 /*
1039 * Debugging checks.
1040 *
1041 * Depth must not be zero for a non-head lock:
1042 */
1043 if (!depth)
1044 goto out_bug;
1045 /*
1046 * At least two relevant locks must exist for this
1047 * to be a head:
1048 */
1049 if (curr->held_locks[depth].irq_context !=
1050 curr->held_locks[depth-1].irq_context)
1051 goto out_bug;
1052
1053 for (;;) {
1054 int distance = curr->lockdep_depth - depth + 1;
1055 hlock = curr->held_locks + depth-1;
1056 /*
1057 * Only non-recursive-read entries get new dependencies
1058 * added:
1059 */
1060 if (hlock->read != 2) {
1061 if (!check_prev_add(curr, hlock, next, distance))
1062 return 0;
1063 /*
1064 * Stop after the first non-trylock entry,
1065 * as non-trylock entries have added their
1066 * own direct dependencies already, so this
1067 * lock is connected to them indirectly:
1068 */
1069 if (!hlock->trylock)
1070 break;
1071 }
1072 depth--;
1073 /*
1074 * End of lock-stack?
1075 */
1076 if (!depth)
1077 break;
1078 /*
1079 * Stop the search if we cross into another context:
1080 */
1081 if (curr->held_locks[depth].irq_context !=
1082 curr->held_locks[depth-1].irq_context)
1083 break;
1084 }
1085 return 1;
1086out_bug:
1087 if (!debug_locks_off_graph_unlock())
1088 return 0;
1089
1090 WARN_ON(1);
1091
1092 return 0;
1093}
1094
1095
1096/*
1097 * Is this the address of a static object:
1098 */
1099static int static_obj(void *obj)
1100{
1101 unsigned long start = (unsigned long) &_stext,
1102 end = (unsigned long) &_end,
1103 addr = (unsigned long) obj;
1104#ifdef CONFIG_SMP
1105 int i;
1106#endif
1107
1108 /*
1109 * static variable?
1110 */
1111 if ((addr >= start) && (addr < end))
1112 return 1;
1113
1114#ifdef CONFIG_SMP
1115 /*
1116 * percpu var?
1117 */
1118 for_each_possible_cpu(i) {
1119 start = (unsigned long) &__per_cpu_start + per_cpu_offset(i);
1120 end = (unsigned long) &__per_cpu_start + PERCPU_ENOUGH_ROOM
1121 + per_cpu_offset(i);
1122
1123 if ((addr >= start) && (addr < end))
1124 return 1;
1125 }
1126#endif
1127
1128 /*
1129 * module var?
1130 */
1131 return is_module_address(addr);
1132}
1133
1134/*
1135 * To make lock name printouts unique, we calculate a unique
1136 * class->name_version generation counter:
1137 */
1138static int count_matching_names(struct lock_class *new_class)
1139{
1140 struct lock_class *class;
1141 int count = 0;
1142
1143 if (!new_class->name)
1144 return 0;
1145
1146 list_for_each_entry(class, &all_lock_classes, lock_entry) {
1147 if (new_class->key - new_class->subclass == class->key)
1148 return class->name_version;
1149 if (class->name && !strcmp(class->name, new_class->name))
1150 count = max(count, class->name_version);
1151 }
1152
1153 return count + 1;
1154}
1155
1156/*
1157 * Register a lock's class in the hash-table, if the class is not present
1158 * yet. Otherwise we look it up. We cache the result in the lock object
1159 * itself, so actual lookup of the hash should be once per lock object.
1160 */
1161static inline struct lock_class *
1162look_up_lock_class(struct lockdep_map *lock, unsigned int subclass)
1163{
1164 struct lockdep_subclass_key *key;
1165 struct list_head *hash_head;
1166 struct lock_class *class;
1167
1168#ifdef CONFIG_DEBUG_LOCKDEP
1169 /*
1170 * If the architecture calls into lockdep before initializing
1171 * the hashes then we'll warn about it later. (we cannot printk
1172 * right now)
1173 */
1174 if (unlikely(!lockdep_initialized)) {
1175 lockdep_init();
1176 lockdep_init_error = 1;
1177 }
1178#endif
1179
1180 /*
1181 * Static locks do not have their class-keys yet - for them the key
1182 * is the lock object itself:
1183 */
1184 if (unlikely(!lock->key))
1185 lock->key = (void *)lock;
1186
1187 /*
1188 * NOTE: the class-key must be unique. For dynamic locks, a static
1189 * lock_class_key variable is passed in through the mutex_init()
1190 * (or spin_lock_init()) call - which acts as the key. For static
1191 * locks we use the lock object itself as the key.
1192 */
1193 BUILD_BUG_ON(sizeof(struct lock_class_key) > sizeof(struct lock_class));
1194
1195 key = lock->key->subkeys + subclass;
1196
1197 hash_head = classhashentry(key);
1198
1199 /*
1200 * We can walk the hash lockfree, because the hash only
1201 * grows, and we are careful when adding entries to the end:
1202 */
1203 list_for_each_entry(class, hash_head, hash_entry)
1204 if (class->key == key)
1205 return class;
1206
1207 return NULL;
1208}
1209
1210/*
1211 * Register a lock's class in the hash-table, if the class is not present
1212 * yet. Otherwise we look it up. We cache the result in the lock object
1213 * itself, so actual lookup of the hash should be once per lock object.
1214 */
1215static inline struct lock_class *
1216register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
1217{
1218 struct lockdep_subclass_key *key;
1219 struct list_head *hash_head;
1220 struct lock_class *class;
1221 unsigned long flags;
1222
1223 class = look_up_lock_class(lock, subclass);
1224 if (likely(class))
1225 return class;
1226
1227 /*
1228 * Debug-check: all keys must be persistent!
1229 */
1230 if (!static_obj(lock->key)) {
1231 debug_locks_off();
1232 printk("INFO: trying to register non-static key.\n");
1233 printk("the code is fine but needs lockdep annotation.\n");
1234 printk("turning off the locking correctness validator.\n");
1235 dump_stack();
1236
1237 return NULL;
1238 }
1239
1240 key = lock->key->subkeys + subclass;
1241 hash_head = classhashentry(key);
1242
1243 raw_local_irq_save(flags);
1244 if (!graph_lock()) {
1245 raw_local_irq_restore(flags);
1246 return NULL;
1247 }
1248 /*
1249 * We have to do the hash-walk again, to avoid races
1250 * with another CPU:
1251 */
1252 list_for_each_entry(class, hash_head, hash_entry)
1253 if (class->key == key)
1254 goto out_unlock_set;
1255 /*
1256 * Allocate a new key from the static array, and add it to
1257 * the hash:
1258 */
1259 if (nr_lock_classes >= MAX_LOCKDEP_KEYS) {
1260 if (!debug_locks_off_graph_unlock()) {
1261 raw_local_irq_restore(flags);
1262 return NULL;
1263 }
1264 raw_local_irq_restore(flags);
1265
1266 printk("BUG: MAX_LOCKDEP_KEYS too low!\n");
1267 printk("turning off the locking correctness validator.\n");
1268 return NULL;
1269 }
1270 class = lock_classes + nr_lock_classes++;
1271 debug_atomic_inc(&nr_unused_locks);
1272 class->key = key;
1273 class->name = lock->name;
1274 class->subclass = subclass;
1275 INIT_LIST_HEAD(&class->lock_entry);
1276 INIT_LIST_HEAD(&class->locks_before);
1277 INIT_LIST_HEAD(&class->locks_after);
1278 class->name_version = count_matching_names(class);
1279 /*
1280 * We use RCU's safe list-add method to make
1281 * parallel walking of the hash-list safe:
1282 */
1283 list_add_tail_rcu(&class->hash_entry, hash_head);
1284
1285 if (verbose(class)) {
1286 graph_unlock();
1287 raw_local_irq_restore(flags);
1288
1289 printk("\nnew class %p: %s", class->key, class->name);
1290 if (class->name_version > 1)
1291 printk("#%d", class->name_version);
1292 printk("\n");
1293 dump_stack();
1294
1295 raw_local_irq_save(flags);
1296 if (!graph_lock()) {
1297 raw_local_irq_restore(flags);
1298 return NULL;
1299 }
1300 }
1301out_unlock_set:
1302 graph_unlock();
1303 raw_local_irq_restore(flags);
1304
1305 if (!subclass || force)
1306 lock->class_cache = class;
1307
1308 if (DEBUG_LOCKS_WARN_ON(class->subclass != subclass))
1309 return NULL;
1310
1311 return class;
1312}
1313
1314/*
1315 * Look up a dependency chain. If the key is not present yet then
1316 * add it and return 0 - in this case the new dependency chain is
1317 * validated. If the key is already hashed, return 1.
1318 */
1319static inline int lookup_chain_cache(u64 chain_key, struct lock_class *class)
1320{
1321 struct list_head *hash_head = chainhashentry(chain_key);
1322 struct lock_chain *chain;
1323
1324 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
1325 return 0;
1326 /*
1327 * We can walk it lock-free, because entries only get added
1328 * to the hash:
1329 */
1330 list_for_each_entry(chain, hash_head, entry) {
1331 if (chain->chain_key == chain_key) {
1332cache_hit:
1333 debug_atomic_inc(&chain_lookup_hits);
1334 if (very_verbose(class))
1335 printk("\nhash chain already cached, key: "
1336 "%016Lx tail class: [%p] %s\n",
1337 (unsigned long long)chain_key,
1338 class->key, class->name);
1339 return 0;
1340 }
1341 }
1342 if (very_verbose(class))
1343 printk("\nnew hash chain, key: %016Lx tail class: [%p] %s\n",
1344 (unsigned long long)chain_key, class->key, class->name);
1345 /*
1346 * Allocate a new chain entry from the static array, and add
1347 * it to the hash:
1348 */
1349 if (!graph_lock())
1350 return 0;
1351 /*
1352 * We have to walk the chain again locked - to avoid duplicates:
1353 */
1354 list_for_each_entry(chain, hash_head, entry) {
1355 if (chain->chain_key == chain_key) {
1356 graph_unlock();
1357 goto cache_hit;
1358 }
1359 }
1360 if (unlikely(nr_lock_chains >= MAX_LOCKDEP_CHAINS)) {
1361 if (!debug_locks_off_graph_unlock())
1362 return 0;
1363
1364 printk("BUG: MAX_LOCKDEP_CHAINS too low!\n");
1365 printk("turning off the locking correctness validator.\n");
1366 return 0;
1367 }
1368 chain = lock_chains + nr_lock_chains++;
1369 chain->chain_key = chain_key;
1370 list_add_tail_rcu(&chain->entry, hash_head);
1371 debug_atomic_inc(&chain_lookup_misses);
1372#ifdef CONFIG_TRACE_IRQFLAGS
1373 if (current->hardirq_context)
1374 nr_hardirq_chains++;
1375 else {
1376 if (current->softirq_context)
1377 nr_softirq_chains++;
1378 else
1379 nr_process_chains++;
1380 }
1381#else
1382 nr_process_chains++;
1383#endif
1384
1385 return 1;
1386}
1387
1388/*
1389 * We are building curr_chain_key incrementally, so double-check
1390 * it from scratch, to make sure that it's done correctly:
1391 */
1392static void check_chain_key(struct task_struct *curr)
1393{
1394#ifdef CONFIG_DEBUG_LOCKDEP
1395 struct held_lock *hlock, *prev_hlock = NULL;
1396 unsigned int i, id;
1397 u64 chain_key = 0;
1398
1399 for (i = 0; i < curr->lockdep_depth; i++) {
1400 hlock = curr->held_locks + i;
1401 if (chain_key != hlock->prev_chain_key) {
1402 debug_locks_off();
1403 printk("hm#1, depth: %u [%u], %016Lx != %016Lx\n",
1404 curr->lockdep_depth, i,
1405 (unsigned long long)chain_key,
1406 (unsigned long long)hlock->prev_chain_key);
1407 WARN_ON(1);
1408 return;
1409 }
1410 id = hlock->class - lock_classes;
1411 if (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
1412 return;
1413
1414 if (prev_hlock && (prev_hlock->irq_context !=
1415 hlock->irq_context))
1416 chain_key = 0;
1417 chain_key = iterate_chain_key(chain_key, id);
1418 prev_hlock = hlock;
1419 }
1420 if (chain_key != curr->curr_chain_key) {
1421 debug_locks_off();
1422 printk("hm#2, depth: %u [%u], %016Lx != %016Lx\n",
1423 curr->lockdep_depth, i,
1424 (unsigned long long)chain_key,
1425 (unsigned long long)curr->curr_chain_key);
1426 WARN_ON(1);
1427 }
1428#endif
1429}
1430
1431#ifdef CONFIG_TRACE_IRQFLAGS
1432
1433/*
1434 * print irq inversion bug:
1435 */
1436static int
1437print_irq_inversion_bug(struct task_struct *curr, struct lock_class *other,
1438 struct held_lock *this, int forwards,
1439 const char *irqclass)
1440{
1441 if (!debug_locks_off_graph_unlock() || debug_locks_silent)
1442 return 0;
1443
1444 printk("\n=========================================================\n");
1445 printk( "[ INFO: possible irq lock inversion dependency detected ]\n");
1446 print_kernel_version();
1447 printk( "---------------------------------------------------------\n");
1448 printk("%s/%d just changed the state of lock:\n",
1449 curr->comm, curr->pid);
1450 print_lock(this);
1451 if (forwards)
1452 printk("but this lock took another, %s-irq-unsafe lock in the past:\n", irqclass);
1453 else
1454 printk("but this lock was taken by another, %s-irq-safe lock in the past:\n", irqclass);
1455 print_lock_name(other);
1456 printk("\n\nand interrupts could create inverse lock ordering between them.\n\n");
1457
1458 printk("\nother info that might help us debug this:\n");
1459 lockdep_print_held_locks(curr);
1460
1461 printk("\nthe first lock's dependencies:\n");
1462 print_lock_dependencies(this->class, 0);
1463
1464 printk("\nthe second lock's dependencies:\n");
1465 print_lock_dependencies(other, 0);
1466
1467 printk("\nstack backtrace:\n");
1468 dump_stack();
1469
1470 return 0;
1471}
1472
1473/*
1474 * Prove that in the forwards-direction subgraph starting at <this>
1475 * there is no lock matching <mask>:
1476 */
1477static int
1478check_usage_forwards(struct task_struct *curr, struct held_lock *this,
1479 enum lock_usage_bit bit, const char *irqclass)
1480{
1481 int ret;
1482
1483 find_usage_bit = bit;
1484 /* fills in <forwards_match> */
1485 ret = find_usage_forwards(this->class, 0);
1486 if (!ret || ret == 1)
1487 return ret;
1488
1489 return print_irq_inversion_bug(curr, forwards_match, this, 1, irqclass);
1490}
1491
1492/*
1493 * Prove that in the backwards-direction subgraph starting at <this>
1494 * there is no lock matching <mask>:
1495 */
1496static int
1497check_usage_backwards(struct task_struct *curr, struct held_lock *this,
1498 enum lock_usage_bit bit, const char *irqclass)
1499{
1500 int ret;
1501
1502 find_usage_bit = bit;
1503 /* fills in <backwards_match> */
1504 ret = find_usage_backwards(this->class, 0);
1505 if (!ret || ret == 1)
1506 return ret;
1507
1508 return print_irq_inversion_bug(curr, backwards_match, this, 0, irqclass);
1509}
1510
1511void print_irqtrace_events(struct task_struct *curr)
1512{
1513 printk("irq event stamp: %u\n", curr->irq_events);
1514 printk("hardirqs last enabled at (%u): ", curr->hardirq_enable_event);
1515 print_ip_sym(curr->hardirq_enable_ip);
1516 printk("hardirqs last disabled at (%u): ", curr->hardirq_disable_event);
1517 print_ip_sym(curr->hardirq_disable_ip);
1518 printk("softirqs last enabled at (%u): ", curr->softirq_enable_event);
1519 print_ip_sym(curr->softirq_enable_ip);
1520 printk("softirqs last disabled at (%u): ", curr->softirq_disable_event);
1521 print_ip_sym(curr->softirq_disable_ip);
1522}
1523
1524#endif
1525
1526static int
1527print_usage_bug(struct task_struct *curr, struct held_lock *this,
1528 enum lock_usage_bit prev_bit, enum lock_usage_bit new_bit)
1529{
1530 if (!debug_locks_off_graph_unlock() || debug_locks_silent)
1531 return 0;
1532
1533 printk("\n=================================\n");
1534 printk( "[ INFO: inconsistent lock state ]\n");
1535 print_kernel_version();
1536 printk( "---------------------------------\n");
1537
1538 printk("inconsistent {%s} -> {%s} usage.\n",
1539 usage_str[prev_bit], usage_str[new_bit]);
1540
1541 printk("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] takes:\n",
1542 curr->comm, curr->pid,
1543 trace_hardirq_context(curr), hardirq_count() >> HARDIRQ_SHIFT,
1544 trace_softirq_context(curr), softirq_count() >> SOFTIRQ_SHIFT,
1545 trace_hardirqs_enabled(curr),
1546 trace_softirqs_enabled(curr));
1547 print_lock(this);
1548
1549 printk("{%s} state was registered at:\n", usage_str[prev_bit]);
1550 print_stack_trace(this->class->usage_traces + prev_bit, 1);
1551
1552 print_irqtrace_events(curr);
1553 printk("\nother info that might help us debug this:\n");
1554 lockdep_print_held_locks(curr);
1555
1556 printk("\nstack backtrace:\n");
1557 dump_stack();
1558
1559 return 0;
1560}
1561
1562/*
1563 * Print out an error if an invalid bit is set:
1564 */
1565static inline int
1566valid_state(struct task_struct *curr, struct held_lock *this,
1567 enum lock_usage_bit new_bit, enum lock_usage_bit bad_bit)
1568{
1569 if (unlikely(this->class->usage_mask & (1 << bad_bit)))
1570 return print_usage_bug(curr, this, bad_bit, new_bit);
1571 return 1;
1572}
1573
1574#define STRICT_READ_CHECKS 1
1575
1576/*
1577 * Mark a lock with a usage bit, and validate the state transition:
1578 */
1579static int mark_lock(struct task_struct *curr, struct held_lock *this,
1580 enum lock_usage_bit new_bit, unsigned long ip)
1581{
1582 unsigned int new_mask = 1 << new_bit, ret = 1;
1583
1584 /*
1585 * If already set then do not dirty the cacheline,
1586 * nor do any checks:
1587 */
1588 if (likely(this->class->usage_mask & new_mask))
1589 return 1;
1590
1591 if (!graph_lock())
1592 return 0;
1593 /*
1594 * Make sure we didnt race:
1595 */
1596 if (unlikely(this->class->usage_mask & new_mask)) {
1597 graph_unlock();
1598 return 1;
1599 }
1600
1601 this->class->usage_mask |= new_mask;
1602
1603#ifdef CONFIG_TRACE_IRQFLAGS
1604 if (new_bit == LOCK_ENABLED_HARDIRQS ||
1605 new_bit == LOCK_ENABLED_HARDIRQS_READ)
1606 ip = curr->hardirq_enable_ip;
1607 else if (new_bit == LOCK_ENABLED_SOFTIRQS ||
1608 new_bit == LOCK_ENABLED_SOFTIRQS_READ)
1609 ip = curr->softirq_enable_ip;
1610#endif
1611 if (!save_trace(this->class->usage_traces + new_bit))
1612 return 0;
1613
1614 switch (new_bit) {
1615#ifdef CONFIG_TRACE_IRQFLAGS
1616 case LOCK_USED_IN_HARDIRQ:
1617 if (!valid_state(curr, this, new_bit, LOCK_ENABLED_HARDIRQS))
1618 return 0;
1619 if (!valid_state(curr, this, new_bit,
1620 LOCK_ENABLED_HARDIRQS_READ))
1621 return 0;
1622 /*
1623 * just marked it hardirq-safe, check that this lock
1624 * took no hardirq-unsafe lock in the past:
1625 */
1626 if (!check_usage_forwards(curr, this,
1627 LOCK_ENABLED_HARDIRQS, "hard"))
1628 return 0;
1629#if STRICT_READ_CHECKS
1630 /*
1631 * just marked it hardirq-safe, check that this lock
1632 * took no hardirq-unsafe-read lock in the past:
1633 */
1634 if (!check_usage_forwards(curr, this,
1635 LOCK_ENABLED_HARDIRQS_READ, "hard-read"))
1636 return 0;
1637#endif
1638 if (hardirq_verbose(this->class))
1639 ret = 2;
1640 break;
1641 case LOCK_USED_IN_SOFTIRQ:
1642 if (!valid_state(curr, this, new_bit, LOCK_ENABLED_SOFTIRQS))
1643 return 0;
1644 if (!valid_state(curr, this, new_bit,
1645 LOCK_ENABLED_SOFTIRQS_READ))
1646 return 0;
1647 /*
1648 * just marked it softirq-safe, check that this lock
1649 * took no softirq-unsafe lock in the past:
1650 */
1651 if (!check_usage_forwards(curr, this,
1652 LOCK_ENABLED_SOFTIRQS, "soft"))
1653 return 0;
1654#if STRICT_READ_CHECKS
1655 /*
1656 * just marked it softirq-safe, check that this lock
1657 * took no softirq-unsafe-read lock in the past:
1658 */
1659 if (!check_usage_forwards(curr, this,
1660 LOCK_ENABLED_SOFTIRQS_READ, "soft-read"))
1661 return 0;
1662#endif
1663 if (softirq_verbose(this->class))
1664 ret = 2;
1665 break;
1666 case LOCK_USED_IN_HARDIRQ_READ:
1667 if (!valid_state(curr, this, new_bit, LOCK_ENABLED_HARDIRQS))
1668 return 0;
1669 /*
1670 * just marked it hardirq-read-safe, check that this lock
1671 * took no hardirq-unsafe lock in the past:
1672 */
1673 if (!check_usage_forwards(curr, this,
1674 LOCK_ENABLED_HARDIRQS, "hard"))
1675 return 0;
1676 if (hardirq_verbose(this->class))
1677 ret = 2;
1678 break;
1679 case LOCK_USED_IN_SOFTIRQ_READ:
1680 if (!valid_state(curr, this, new_bit, LOCK_ENABLED_SOFTIRQS))
1681 return 0;
1682 /*
1683 * just marked it softirq-read-safe, check that this lock
1684 * took no softirq-unsafe lock in the past:
1685 */
1686 if (!check_usage_forwards(curr, this,
1687 LOCK_ENABLED_SOFTIRQS, "soft"))
1688 return 0;
1689 if (softirq_verbose(this->class))
1690 ret = 2;
1691 break;
1692 case LOCK_ENABLED_HARDIRQS:
1693 if (!valid_state(curr, this, new_bit, LOCK_USED_IN_HARDIRQ))
1694 return 0;
1695 if (!valid_state(curr, this, new_bit,
1696 LOCK_USED_IN_HARDIRQ_READ))
1697 return 0;
1698 /*
1699 * just marked it hardirq-unsafe, check that no hardirq-safe
1700 * lock in the system ever took it in the past:
1701 */
1702 if (!check_usage_backwards(curr, this,
1703 LOCK_USED_IN_HARDIRQ, "hard"))
1704 return 0;
1705#if STRICT_READ_CHECKS
1706 /*
1707 * just marked it hardirq-unsafe, check that no
1708 * hardirq-safe-read lock in the system ever took
1709 * it in the past:
1710 */
1711 if (!check_usage_backwards(curr, this,
1712 LOCK_USED_IN_HARDIRQ_READ, "hard-read"))
1713 return 0;
1714#endif
1715 if (hardirq_verbose(this->class))
1716 ret = 2;
1717 break;
1718 case LOCK_ENABLED_SOFTIRQS:
1719 if (!valid_state(curr, this, new_bit, LOCK_USED_IN_SOFTIRQ))
1720 return 0;
1721 if (!valid_state(curr, this, new_bit,
1722 LOCK_USED_IN_SOFTIRQ_READ))
1723 return 0;
1724 /*
1725 * just marked it softirq-unsafe, check that no softirq-safe
1726 * lock in the system ever took it in the past:
1727 */
1728 if (!check_usage_backwards(curr, this,
1729 LOCK_USED_IN_SOFTIRQ, "soft"))
1730 return 0;
1731#if STRICT_READ_CHECKS
1732 /*
1733 * just marked it softirq-unsafe, check that no
1734 * softirq-safe-read lock in the system ever took
1735 * it in the past:
1736 */
1737 if (!check_usage_backwards(curr, this,
1738 LOCK_USED_IN_SOFTIRQ_READ, "soft-read"))
1739 return 0;
1740#endif
1741 if (softirq_verbose(this->class))
1742 ret = 2;
1743 break;
1744 case LOCK_ENABLED_HARDIRQS_READ:
1745 if (!valid_state(curr, this, new_bit, LOCK_USED_IN_HARDIRQ))
1746 return 0;
1747#if STRICT_READ_CHECKS
1748 /*
1749 * just marked it hardirq-read-unsafe, check that no
1750 * hardirq-safe lock in the system ever took it in the past:
1751 */
1752 if (!check_usage_backwards(curr, this,
1753 LOCK_USED_IN_HARDIRQ, "hard"))
1754 return 0;
1755#endif
1756 if (hardirq_verbose(this->class))
1757 ret = 2;
1758 break;
1759 case LOCK_ENABLED_SOFTIRQS_READ:
1760 if (!valid_state(curr, this, new_bit, LOCK_USED_IN_SOFTIRQ))
1761 return 0;
1762#if STRICT_READ_CHECKS
1763 /*
1764 * just marked it softirq-read-unsafe, check that no
1765 * softirq-safe lock in the system ever took it in the past:
1766 */
1767 if (!check_usage_backwards(curr, this,
1768 LOCK_USED_IN_SOFTIRQ, "soft"))
1769 return 0;
1770#endif
1771 if (softirq_verbose(this->class))
1772 ret = 2;
1773 break;
1774#endif
1775 case LOCK_USED:
1776 /*
1777 * Add it to the global list of classes:
1778 */
1779 list_add_tail_rcu(&this->class->lock_entry, &all_lock_classes);
1780 debug_atomic_dec(&nr_unused_locks);
1781 break;
1782 default:
1783 if (!debug_locks_off_graph_unlock())
1784 return 0;
1785 WARN_ON(1);
1786 return 0;
1787 }
1788
1789 graph_unlock();
1790
1791 /*
1792 * We must printk outside of the graph_lock:
1793 */
1794 if (ret == 2) {
1795 printk("\nmarked lock as {%s}:\n", usage_str[new_bit]);
1796 print_lock(this);
1797 print_irqtrace_events(curr);
1798 dump_stack();
1799 }
1800
1801 return ret;
1802}
1803
1804#ifdef CONFIG_TRACE_IRQFLAGS
1805/*
1806 * Mark all held locks with a usage bit:
1807 */
1808static int
1809mark_held_locks(struct task_struct *curr, int hardirq, unsigned long ip)
1810{
1811 enum lock_usage_bit usage_bit;
1812 struct held_lock *hlock;
1813 int i;
1814
1815 for (i = 0; i < curr->lockdep_depth; i++) {
1816 hlock = curr->held_locks + i;
1817
1818 if (hardirq) {
1819 if (hlock->read)
1820 usage_bit = LOCK_ENABLED_HARDIRQS_READ;
1821 else
1822 usage_bit = LOCK_ENABLED_HARDIRQS;
1823 } else {
1824 if (hlock->read)
1825 usage_bit = LOCK_ENABLED_SOFTIRQS_READ;
1826 else
1827 usage_bit = LOCK_ENABLED_SOFTIRQS;
1828 }
1829 if (!mark_lock(curr, hlock, usage_bit, ip))
1830 return 0;
1831 }
1832
1833 return 1;
1834}
1835
1836/*
1837 * Debugging helper: via this flag we know that we are in
1838 * 'early bootup code', and will warn about any invalid irqs-on event:
1839 */
1840static int early_boot_irqs_enabled;
1841
1842void early_boot_irqs_off(void)
1843{
1844 early_boot_irqs_enabled = 0;
1845}
1846
1847void early_boot_irqs_on(void)
1848{
1849 early_boot_irqs_enabled = 1;
1850}
1851
1852/*
1853 * Hardirqs will be enabled:
1854 */
1855void trace_hardirqs_on(void)
1856{
1857 struct task_struct *curr = current;
1858 unsigned long ip;
1859
1860 if (unlikely(!debug_locks || current->lockdep_recursion))
1861 return;
1862
1863 if (DEBUG_LOCKS_WARN_ON(unlikely(!early_boot_irqs_enabled)))
1864 return;
1865
1866 if (unlikely(curr->hardirqs_enabled)) {
1867 debug_atomic_inc(&redundant_hardirqs_on);
1868 return;
1869 }
1870 /* we'll do an OFF -> ON transition: */
1871 curr->hardirqs_enabled = 1;
1872 ip = (unsigned long) __builtin_return_address(0);
1873
1874 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
1875 return;
1876 if (DEBUG_LOCKS_WARN_ON(current->hardirq_context))
1877 return;
1878 /*
1879 * We are going to turn hardirqs on, so set the
1880 * usage bit for all held locks:
1881 */
1882 if (!mark_held_locks(curr, 1, ip))
1883 return;
1884 /*
1885 * If we have softirqs enabled, then set the usage
1886 * bit for all held locks. (disabled hardirqs prevented
1887 * this bit from being set before)
1888 */
1889 if (curr->softirqs_enabled)
1890 if (!mark_held_locks(curr, 0, ip))
1891 return;
1892
1893 curr->hardirq_enable_ip = ip;
1894 curr->hardirq_enable_event = ++curr->irq_events;
1895 debug_atomic_inc(&hardirqs_on_events);
1896}
1897
1898EXPORT_SYMBOL(trace_hardirqs_on);
1899
1900/*
1901 * Hardirqs were disabled:
1902 */
1903void trace_hardirqs_off(void)
1904{
1905 struct task_struct *curr = current;
1906
1907 if (unlikely(!debug_locks || current->lockdep_recursion))
1908 return;
1909
1910 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
1911 return;
1912
1913 if (curr->hardirqs_enabled) {
1914 /*
1915 * We have done an ON -> OFF transition:
1916 */
1917 curr->hardirqs_enabled = 0;
1918 curr->hardirq_disable_ip = _RET_IP_;
1919 curr->hardirq_disable_event = ++curr->irq_events;
1920 debug_atomic_inc(&hardirqs_off_events);
1921 } else
1922 debug_atomic_inc(&redundant_hardirqs_off);
1923}
1924
1925EXPORT_SYMBOL(trace_hardirqs_off);
1926
1927/*
1928 * Softirqs will be enabled:
1929 */
1930void trace_softirqs_on(unsigned long ip)
1931{
1932 struct task_struct *curr = current;
1933
1934 if (unlikely(!debug_locks))
1935 return;
1936
1937 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
1938 return;
1939
1940 if (curr->softirqs_enabled) {
1941 debug_atomic_inc(&redundant_softirqs_on);
1942 return;
1943 }
1944
1945 /*
1946 * We'll do an OFF -> ON transition:
1947 */
1948 curr->softirqs_enabled = 1;
1949 curr->softirq_enable_ip = ip;
1950 curr->softirq_enable_event = ++curr->irq_events;
1951 debug_atomic_inc(&softirqs_on_events);
1952 /*
1953 * We are going to turn softirqs on, so set the
1954 * usage bit for all held locks, if hardirqs are
1955 * enabled too:
1956 */
1957 if (curr->hardirqs_enabled)
1958 mark_held_locks(curr, 0, ip);
1959}
1960
1961/*
1962 * Softirqs were disabled:
1963 */
1964void trace_softirqs_off(unsigned long ip)
1965{
1966 struct task_struct *curr = current;
1967
1968 if (unlikely(!debug_locks))
1969 return;
1970
1971 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
1972 return;
1973
1974 if (curr->softirqs_enabled) {
1975 /*
1976 * We have done an ON -> OFF transition:
1977 */
1978 curr->softirqs_enabled = 0;
1979 curr->softirq_disable_ip = ip;
1980 curr->softirq_disable_event = ++curr->irq_events;
1981 debug_atomic_inc(&softirqs_off_events);
1982 DEBUG_LOCKS_WARN_ON(!softirq_count());
1983 } else
1984 debug_atomic_inc(&redundant_softirqs_off);
1985}
1986
1987#endif
1988
1989/*
1990 * Initialize a lock instance's lock-class mapping info:
1991 */
1992void lockdep_init_map(struct lockdep_map *lock, const char *name,
1993 struct lock_class_key *key, int subclass)
1994{
1995 if (unlikely(!debug_locks))
1996 return;
1997
1998 if (DEBUG_LOCKS_WARN_ON(!key))
1999 return;
2000 if (DEBUG_LOCKS_WARN_ON(!name))
2001 return;
2002 /*
2003 * Sanity check, the lock-class key must be persistent:
2004 */
2005 if (!static_obj(key)) {
2006 printk("BUG: key %p not in .data!\n", key);
2007 DEBUG_LOCKS_WARN_ON(1);
2008 return;
2009 }
2010 lock->name = name;
2011 lock->key = key;
2012 lock->class_cache = NULL;
2013 if (subclass)
2014 register_lock_class(lock, subclass, 1);
2015}
2016
2017EXPORT_SYMBOL_GPL(lockdep_init_map);
2018
2019/*
2020 * This gets called for every mutex_lock*()/spin_lock*() operation.
2021 * We maintain the dependency maps and validate the locking attempt:
2022 */
2023static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
2024 int trylock, int read, int check, int hardirqs_off,
2025 unsigned long ip)
2026{
2027 struct task_struct *curr = current;
2028 struct lock_class *class = NULL;
2029 struct held_lock *hlock;
2030 unsigned int depth, id;
2031 int chain_head = 0;
2032 u64 chain_key;
2033
2034 if (unlikely(!debug_locks))
2035 return 0;
2036
2037 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
2038 return 0;
2039
2040 if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
2041 debug_locks_off();
2042 printk("BUG: MAX_LOCKDEP_SUBCLASSES too low!\n");
2043 printk("turning off the locking correctness validator.\n");
2044 return 0;
2045 }
2046
2047 if (!subclass)
2048 class = lock->class_cache;
2049 /*
2050 * Not cached yet or subclass?
2051 */
2052 if (unlikely(!class)) {
2053 class = register_lock_class(lock, subclass, 0);
2054 if (!class)
2055 return 0;
2056 }
2057 debug_atomic_inc((atomic_t *)&class->ops);
2058 if (very_verbose(class)) {
2059 printk("\nacquire class [%p] %s", class->key, class->name);
2060 if (class->name_version > 1)
2061 printk("#%d", class->name_version);
2062 printk("\n");
2063 dump_stack();
2064 }
2065
2066 /*
2067 * Add the lock to the list of currently held locks.
2068 * (we dont increase the depth just yet, up until the
2069 * dependency checks are done)
2070 */
2071 depth = curr->lockdep_depth;
2072 if (DEBUG_LOCKS_WARN_ON(depth >= MAX_LOCK_DEPTH))
2073 return 0;
2074
2075 hlock = curr->held_locks + depth;
2076
2077 hlock->class = class;
2078 hlock->acquire_ip = ip;
2079 hlock->instance = lock;
2080 hlock->trylock = trylock;
2081 hlock->read = read;
2082 hlock->check = check;
2083 hlock->hardirqs_off = hardirqs_off;
2084
2085 if (check != 2)
2086 goto out_calc_hash;
2087#ifdef CONFIG_TRACE_IRQFLAGS
2088 /*
2089 * If non-trylock use in a hardirq or softirq context, then
2090 * mark the lock as used in these contexts:
2091 */
2092 if (!trylock) {
2093 if (read) {
2094 if (curr->hardirq_context)
2095 if (!mark_lock(curr, hlock,
2096 LOCK_USED_IN_HARDIRQ_READ, ip))
2097 return 0;
2098 if (curr->softirq_context)
2099 if (!mark_lock(curr, hlock,
2100 LOCK_USED_IN_SOFTIRQ_READ, ip))
2101 return 0;
2102 } else {
2103 if (curr->hardirq_context)
2104 if (!mark_lock(curr, hlock, LOCK_USED_IN_HARDIRQ, ip))
2105 return 0;
2106 if (curr->softirq_context)
2107 if (!mark_lock(curr, hlock, LOCK_USED_IN_SOFTIRQ, ip))
2108 return 0;
2109 }
2110 }
2111 if (!hardirqs_off) {
2112 if (read) {
2113 if (!mark_lock(curr, hlock,
2114 LOCK_ENABLED_HARDIRQS_READ, ip))
2115 return 0;
2116 if (curr->softirqs_enabled)
2117 if (!mark_lock(curr, hlock,
2118 LOCK_ENABLED_SOFTIRQS_READ, ip))
2119 return 0;
2120 } else {
2121 if (!mark_lock(curr, hlock,
2122 LOCK_ENABLED_HARDIRQS, ip))
2123 return 0;
2124 if (curr->softirqs_enabled)
2125 if (!mark_lock(curr, hlock,
2126 LOCK_ENABLED_SOFTIRQS, ip))
2127 return 0;
2128 }
2129 }
2130#endif
2131 /* mark it as used: */
2132 if (!mark_lock(curr, hlock, LOCK_USED, ip))
2133 return 0;
2134out_calc_hash:
2135 /*
2136 * Calculate the chain hash: it's the combined has of all the
2137 * lock keys along the dependency chain. We save the hash value
2138 * at every step so that we can get the current hash easily
2139 * after unlock. The chain hash is then used to cache dependency
2140 * results.
2141 *
2142 * The 'key ID' is what is the most compact key value to drive
2143 * the hash, not class->key.
2144 */
2145 id = class - lock_classes;
2146 if (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
2147 return 0;
2148
2149 chain_key = curr->curr_chain_key;
2150 if (!depth) {
2151 if (DEBUG_LOCKS_WARN_ON(chain_key != 0))
2152 return 0;
2153 chain_head = 1;
2154 }
2155
2156 hlock->prev_chain_key = chain_key;
2157
2158#ifdef CONFIG_TRACE_IRQFLAGS
2159 /*
2160 * Keep track of points where we cross into an interrupt context:
2161 */
2162 hlock->irq_context = 2*(curr->hardirq_context ? 1 : 0) +
2163 curr->softirq_context;
2164 if (depth) {
2165 struct held_lock *prev_hlock;
2166
2167 prev_hlock = curr->held_locks + depth-1;
2168 /*
2169 * If we cross into another context, reset the
2170 * hash key (this also prevents the checking and the
2171 * adding of the dependency to 'prev'):
2172 */
2173 if (prev_hlock->irq_context != hlock->irq_context) {
2174 chain_key = 0;
2175 chain_head = 1;
2176 }
2177 }
2178#endif
2179 chain_key = iterate_chain_key(chain_key, id);
2180 curr->curr_chain_key = chain_key;
2181
2182 /*
2183 * Trylock needs to maintain the stack of held locks, but it
2184 * does not add new dependencies, because trylock can be done
2185 * in any order.
2186 *
2187 * We look up the chain_key and do the O(N^2) check and update of
2188 * the dependencies only if this is a new dependency chain.
2189 * (If lookup_chain_cache() returns with 1 it acquires
2190 * graph_lock for us)
2191 */
2192 if (!trylock && (check == 2) && lookup_chain_cache(chain_key, class)) {
2193 /*
2194 * Check whether last held lock:
2195 *
2196 * - is irq-safe, if this lock is irq-unsafe
2197 * - is softirq-safe, if this lock is hardirq-unsafe
2198 *
2199 * And check whether the new lock's dependency graph
2200 * could lead back to the previous lock.
2201 *
2202 * any of these scenarios could lead to a deadlock. If
2203 * All validations
2204 */
2205 int ret = check_deadlock(curr, hlock, lock, read);
2206
2207 if (!ret)
2208 return 0;
2209 /*
2210 * Mark recursive read, as we jump over it when
2211 * building dependencies (just like we jump over
2212 * trylock entries):
2213 */
2214 if (ret == 2)
2215 hlock->read = 2;
2216 /*
2217 * Add dependency only if this lock is not the head
2218 * of the chain, and if it's not a secondary read-lock:
2219 */
2220 if (!chain_head && ret != 2)
2221 if (!check_prevs_add(curr, hlock))
2222 return 0;
2223 graph_unlock();
2224 } else
2225 /* after lookup_chain_cache(): */
2226 if (unlikely(!debug_locks))
2227 return 0;
2228
2229 curr->lockdep_depth++;
2230 check_chain_key(curr);
2231#ifdef CONFIG_DEBUG_LOCKDEP
2232 if (unlikely(!debug_locks))
2233 return 0;
2234#endif
2235 if (unlikely(curr->lockdep_depth >= MAX_LOCK_DEPTH)) {
2236 debug_locks_off();
2237 printk("BUG: MAX_LOCK_DEPTH too low!\n");
2238 printk("turning off the locking correctness validator.\n");
2239 return 0;
2240 }
2241
2242 if (unlikely(curr->lockdep_depth > max_lockdep_depth))
2243 max_lockdep_depth = curr->lockdep_depth;
2244
2245 return 1;
2246}
2247
2248static int
2249print_unlock_inbalance_bug(struct task_struct *curr, struct lockdep_map *lock,
2250 unsigned long ip)
2251{
2252 if (!debug_locks_off())
2253 return 0;
2254 if (debug_locks_silent)
2255 return 0;
2256
2257 printk("\n=====================================\n");
2258 printk( "[ BUG: bad unlock balance detected! ]\n");
2259 printk( "-------------------------------------\n");
2260 printk("%s/%d is trying to release lock (",
2261 curr->comm, curr->pid);
2262 print_lockdep_cache(lock);
2263 printk(") at:\n");
2264 print_ip_sym(ip);
2265 printk("but there are no more locks to release!\n");
2266 printk("\nother info that might help us debug this:\n");
2267 lockdep_print_held_locks(curr);
2268
2269 printk("\nstack backtrace:\n");
2270 dump_stack();
2271
2272 return 0;
2273}
2274
2275/*
2276 * Common debugging checks for both nested and non-nested unlock:
2277 */
2278static int check_unlock(struct task_struct *curr, struct lockdep_map *lock,
2279 unsigned long ip)
2280{
2281 if (unlikely(!debug_locks))
2282 return 0;
2283 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
2284 return 0;
2285
2286 if (curr->lockdep_depth <= 0)
2287 return print_unlock_inbalance_bug(curr, lock, ip);
2288
2289 return 1;
2290}
2291
2292/*
2293 * Remove the lock to the list of currently held locks in a
2294 * potentially non-nested (out of order) manner. This is a
2295 * relatively rare operation, as all the unlock APIs default
2296 * to nested mode (which uses lock_release()):
2297 */
2298static int
2299lock_release_non_nested(struct task_struct *curr,
2300 struct lockdep_map *lock, unsigned long ip)
2301{
2302 struct held_lock *hlock, *prev_hlock;
2303 unsigned int depth;
2304 int i;
2305
2306 /*
2307 * Check whether the lock exists in the current stack
2308 * of held locks:
2309 */
2310 depth = curr->lockdep_depth;
2311 if (DEBUG_LOCKS_WARN_ON(!depth))
2312 return 0;
2313
2314 prev_hlock = NULL;
2315 for (i = depth-1; i >= 0; i--) {
2316 hlock = curr->held_locks + i;
2317 /*
2318 * We must not cross into another context:
2319 */
2320 if (prev_hlock && prev_hlock->irq_context != hlock->irq_context)
2321 break;
2322 if (hlock->instance == lock)
2323 goto found_it;
2324 prev_hlock = hlock;
2325 }
2326 return print_unlock_inbalance_bug(curr, lock, ip);
2327
2328found_it:
2329 /*
2330 * We have the right lock to unlock, 'hlock' points to it.
2331 * Now we remove it from the stack, and add back the other
2332 * entries (if any), recalculating the hash along the way:
2333 */
2334 curr->lockdep_depth = i;
2335 curr->curr_chain_key = hlock->prev_chain_key;
2336
2337 for (i++; i < depth; i++) {
2338 hlock = curr->held_locks + i;
2339 if (!__lock_acquire(hlock->instance,
2340 hlock->class->subclass, hlock->trylock,
2341 hlock->read, hlock->check, hlock->hardirqs_off,
2342 hlock->acquire_ip))
2343 return 0;
2344 }
2345
2346 if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - 1))
2347 return 0;
2348 return 1;
2349}
2350
2351/*
2352 * Remove the lock to the list of currently held locks - this gets
2353 * called on mutex_unlock()/spin_unlock*() (or on a failed
2354 * mutex_lock_interruptible()). This is done for unlocks that nest
2355 * perfectly. (i.e. the current top of the lock-stack is unlocked)
2356 */
2357static int lock_release_nested(struct task_struct *curr,
2358 struct lockdep_map *lock, unsigned long ip)
2359{
2360 struct held_lock *hlock;
2361 unsigned int depth;
2362
2363 /*
2364 * Pop off the top of the lock stack:
2365 */
2366 depth = curr->lockdep_depth - 1;
2367 hlock = curr->held_locks + depth;
2368
2369 /*
2370 * Is the unlock non-nested:
2371 */
2372 if (hlock->instance != lock)
2373 return lock_release_non_nested(curr, lock, ip);
2374 curr->lockdep_depth--;
2375
2376 if (DEBUG_LOCKS_WARN_ON(!depth && (hlock->prev_chain_key != 0)))
2377 return 0;
2378
2379 curr->curr_chain_key = hlock->prev_chain_key;
2380
2381#ifdef CONFIG_DEBUG_LOCKDEP
2382 hlock->prev_chain_key = 0;
2383 hlock->class = NULL;
2384 hlock->acquire_ip = 0;
2385 hlock->irq_context = 0;
2386#endif
2387 return 1;
2388}
2389
2390/*
2391 * Remove the lock to the list of currently held locks - this gets
2392 * called on mutex_unlock()/spin_unlock*() (or on a failed
2393 * mutex_lock_interruptible()). This is done for unlocks that nest
2394 * perfectly. (i.e. the current top of the lock-stack is unlocked)
2395 */
2396static void
2397__lock_release(struct lockdep_map *lock, int nested, unsigned long ip)
2398{
2399 struct task_struct *curr = current;
2400
2401 if (!check_unlock(curr, lock, ip))
2402 return;
2403
2404 if (nested) {
2405 if (!lock_release_nested(curr, lock, ip))
2406 return;
2407 } else {
2408 if (!lock_release_non_nested(curr, lock, ip))
2409 return;
2410 }
2411
2412 check_chain_key(curr);
2413}
2414
2415/*
2416 * Check whether we follow the irq-flags state precisely:
2417 */
2418static void check_flags(unsigned long flags)
2419{
2420#if defined(CONFIG_DEBUG_LOCKDEP) && defined(CONFIG_TRACE_IRQFLAGS)
2421 if (!debug_locks)
2422 return;
2423
2424 if (irqs_disabled_flags(flags))
2425 DEBUG_LOCKS_WARN_ON(current->hardirqs_enabled);
2426 else
2427 DEBUG_LOCKS_WARN_ON(!current->hardirqs_enabled);
2428
2429 /*
2430 * We dont accurately track softirq state in e.g.
2431 * hardirq contexts (such as on 4KSTACKS), so only
2432 * check if not in hardirq contexts:
2433 */
2434 if (!hardirq_count()) {
2435 if (softirq_count())
2436 DEBUG_LOCKS_WARN_ON(current->softirqs_enabled);
2437 else
2438 DEBUG_LOCKS_WARN_ON(!current->softirqs_enabled);
2439 }
2440
2441 if (!debug_locks)
2442 print_irqtrace_events(current);
2443#endif
2444}
2445
2446/*
2447 * We are not always called with irqs disabled - do that here,
2448 * and also avoid lockdep recursion:
2449 */
2450void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
2451 int trylock, int read, int check, unsigned long ip)
2452{
2453 unsigned long flags;
2454
2455 if (unlikely(current->lockdep_recursion))
2456 return;
2457
2458 raw_local_irq_save(flags);
2459 check_flags(flags);
2460
2461 current->lockdep_recursion = 1;
2462 __lock_acquire(lock, subclass, trylock, read, check,
2463 irqs_disabled_flags(flags), ip);
2464 current->lockdep_recursion = 0;
2465 raw_local_irq_restore(flags);
2466}
2467
2468EXPORT_SYMBOL_GPL(lock_acquire);
2469
2470void lock_release(struct lockdep_map *lock, int nested, unsigned long ip)
2471{
2472 unsigned long flags;
2473
2474 if (unlikely(current->lockdep_recursion))
2475 return;
2476
2477 raw_local_irq_save(flags);
2478 check_flags(flags);
2479 current->lockdep_recursion = 1;
2480 __lock_release(lock, nested, ip);
2481 current->lockdep_recursion = 0;
2482 raw_local_irq_restore(flags);
2483}
2484
2485EXPORT_SYMBOL_GPL(lock_release);
2486
2487/*
2488 * Used by the testsuite, sanitize the validator state
2489 * after a simulated failure:
2490 */
2491
2492void lockdep_reset(void)
2493{
2494 unsigned long flags;
2495 int i;
2496
2497 raw_local_irq_save(flags);
2498 current->curr_chain_key = 0;
2499 current->lockdep_depth = 0;
2500 current->lockdep_recursion = 0;
2501 memset(current->held_locks, 0, MAX_LOCK_DEPTH*sizeof(struct held_lock));
2502 nr_hardirq_chains = 0;
2503 nr_softirq_chains = 0;
2504 nr_process_chains = 0;
2505 debug_locks = 1;
2506 for (i = 0; i < CHAINHASH_SIZE; i++)
2507 INIT_LIST_HEAD(chainhash_table + i);
2508 raw_local_irq_restore(flags);
2509}
2510
2511static void zap_class(struct lock_class *class)
2512{
2513 int i;
2514
2515 /*
2516 * Remove all dependencies this lock is
2517 * involved in:
2518 */
2519 for (i = 0; i < nr_list_entries; i++) {
2520 if (list_entries[i].class == class)
2521 list_del_rcu(&list_entries[i].entry);
2522 }
2523 /*
2524 * Unhash the class and remove it from the all_lock_classes list:
2525 */
2526 list_del_rcu(&class->hash_entry);
2527 list_del_rcu(&class->lock_entry);
2528
2529}
2530
2531static inline int within(void *addr, void *start, unsigned long size)
2532{
2533 return addr >= start && addr < start + size;
2534}
2535
2536void lockdep_free_key_range(void *start, unsigned long size)
2537{
2538 struct lock_class *class, *next;
2539 struct list_head *head;
2540 unsigned long flags;
2541 int i;
2542
2543 raw_local_irq_save(flags);
2544 graph_lock();
2545
2546 /*
2547 * Unhash all classes that were created by this module:
2548 */
2549 for (i = 0; i < CLASSHASH_SIZE; i++) {
2550 head = classhash_table + i;
2551 if (list_empty(head))
2552 continue;
2553 list_for_each_entry_safe(class, next, head, hash_entry)
2554 if (within(class->key, start, size))
2555 zap_class(class);
2556 }
2557
2558 graph_unlock();
2559 raw_local_irq_restore(flags);
2560}
2561
2562void lockdep_reset_lock(struct lockdep_map *lock)
2563{
2564 struct lock_class *class, *next;
2565 struct list_head *head;
2566 unsigned long flags;
2567 int i, j;
2568
2569 raw_local_irq_save(flags);
2570
2571 /*
2572 * Remove all classes this lock might have:
2573 */
2574 for (j = 0; j < MAX_LOCKDEP_SUBCLASSES; j++) {
2575 /*
2576 * If the class exists we look it up and zap it:
2577 */
2578 class = look_up_lock_class(lock, j);
2579 if (class)
2580 zap_class(class);
2581 }
2582 /*
2583 * Debug check: in the end all mapped classes should
2584 * be gone.
2585 */
2586 graph_lock();
2587 for (i = 0; i < CLASSHASH_SIZE; i++) {
2588 head = classhash_table + i;
2589 if (list_empty(head))
2590 continue;
2591 list_for_each_entry_safe(class, next, head, hash_entry) {
2592 if (unlikely(class == lock->class_cache)) {
2593 if (debug_locks_off_graph_unlock())
2594 WARN_ON(1);
2595 goto out_restore;
2596 }
2597 }
2598 }
2599 graph_unlock();
2600
2601out_restore:
2602 raw_local_irq_restore(flags);
2603}
2604
2605void lockdep_init(void)
2606{
2607 int i;
2608
2609 /*
2610 * Some architectures have their own start_kernel()
2611 * code which calls lockdep_init(), while we also
2612 * call lockdep_init() from the start_kernel() itself,
2613 * and we want to initialize the hashes only once:
2614 */
2615 if (lockdep_initialized)
2616 return;
2617
2618 for (i = 0; i < CLASSHASH_SIZE; i++)
2619 INIT_LIST_HEAD(classhash_table + i);
2620
2621 for (i = 0; i < CHAINHASH_SIZE; i++)
2622 INIT_LIST_HEAD(chainhash_table + i);
2623
2624 lockdep_initialized = 1;
2625}
2626
2627void __init lockdep_info(void)
2628{
2629 printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");
2630
2631 printk("... MAX_LOCKDEP_SUBCLASSES: %lu\n", MAX_LOCKDEP_SUBCLASSES);
2632 printk("... MAX_LOCK_DEPTH: %lu\n", MAX_LOCK_DEPTH);
2633 printk("... MAX_LOCKDEP_KEYS: %lu\n", MAX_LOCKDEP_KEYS);
2634 printk("... CLASSHASH_SIZE: %lu\n", CLASSHASH_SIZE);
2635 printk("... MAX_LOCKDEP_ENTRIES: %lu\n", MAX_LOCKDEP_ENTRIES);
2636 printk("... MAX_LOCKDEP_CHAINS: %lu\n", MAX_LOCKDEP_CHAINS);
2637 printk("... CHAINHASH_SIZE: %lu\n", CHAINHASH_SIZE);
2638
2639 printk(" memory used by lock dependency info: %lu kB\n",
2640 (sizeof(struct lock_class) * MAX_LOCKDEP_KEYS +
2641 sizeof(struct list_head) * CLASSHASH_SIZE +
2642 sizeof(struct lock_list) * MAX_LOCKDEP_ENTRIES +
2643 sizeof(struct lock_chain) * MAX_LOCKDEP_CHAINS +
2644 sizeof(struct list_head) * CHAINHASH_SIZE) / 1024);
2645
2646 printk(" per task-struct memory footprint: %lu bytes\n",
2647 sizeof(struct held_lock) * MAX_LOCK_DEPTH);
2648
2649#ifdef CONFIG_DEBUG_LOCKDEP
2650 if (lockdep_init_error)
2651 printk("WARNING: lockdep init error! Arch code didnt call lockdep_init() early enough?\n");
2652#endif
2653}
2654
2655static inline int in_range(const void *start, const void *addr, const void *end)
2656{
2657 return addr >= start && addr <= end;
2658}
2659
2660static void
2661print_freed_lock_bug(struct task_struct *curr, const void *mem_from,
2662 const void *mem_to, struct held_lock *hlock)
2663{
2664 if (!debug_locks_off())
2665 return;
2666 if (debug_locks_silent)
2667 return;
2668
2669 printk("\n=========================\n");
2670 printk( "[ BUG: held lock freed! ]\n");
2671 printk( "-------------------------\n");
2672 printk("%s/%d is freeing memory %p-%p, with a lock still held there!\n",
2673 curr->comm, curr->pid, mem_from, mem_to-1);
2674 print_lock(hlock);
2675 lockdep_print_held_locks(curr);
2676
2677 printk("\nstack backtrace:\n");
2678 dump_stack();
2679}
2680
2681/*
2682 * Called when kernel memory is freed (or unmapped), or if a lock
2683 * is destroyed or reinitialized - this code checks whether there is
2684 * any held lock in the memory range of <from> to <to>:
2685 */
2686void debug_check_no_locks_freed(const void *mem_from, unsigned long mem_len)
2687{
2688 const void *mem_to = mem_from + mem_len, *lock_from, *lock_to;
2689 struct task_struct *curr = current;
2690 struct held_lock *hlock;
2691 unsigned long flags;
2692 int i;
2693
2694 if (unlikely(!debug_locks))
2695 return;
2696
2697 local_irq_save(flags);
2698 for (i = 0; i < curr->lockdep_depth; i++) {
2699 hlock = curr->held_locks + i;
2700
2701 lock_from = (void *)hlock->instance;
2702 lock_to = (void *)(hlock->instance + 1);
2703
2704 if (!in_range(mem_from, lock_from, mem_to) &&
2705 !in_range(mem_from, lock_to, mem_to))
2706 continue;
2707
2708 print_freed_lock_bug(curr, mem_from, mem_to, hlock);
2709 break;
2710 }
2711 local_irq_restore(flags);
2712}
2713EXPORT_SYMBOL_GPL(debug_check_no_locks_freed);
2714
2715static void print_held_locks_bug(struct task_struct *curr)
2716{
2717 if (!debug_locks_off())
2718 return;
2719 if (debug_locks_silent)
2720 return;
2721
2722 printk("\n=====================================\n");
2723 printk( "[ BUG: lock held at task exit time! ]\n");
2724 printk( "-------------------------------------\n");
2725 printk("%s/%d is exiting with locks still held!\n",
2726 curr->comm, curr->pid);
2727 lockdep_print_held_locks(curr);
2728
2729 printk("\nstack backtrace:\n");
2730 dump_stack();
2731}
2732
2733void debug_check_no_locks_held(struct task_struct *task)
2734{
2735 if (unlikely(task->lockdep_depth > 0))
2736 print_held_locks_bug(task);
2737}
2738
2739void debug_show_all_locks(void)
2740{
2741 struct task_struct *g, *p;
2742 int count = 10;
2743 int unlock = 1;
2744
2745 if (unlikely(!debug_locks)) {
2746 printk("INFO: lockdep is turned off.\n");
2747 return;
2748 }
2749 printk("\nShowing all locks held in the system:\n");
2750
2751 /*
2752 * Here we try to get the tasklist_lock as hard as possible,
2753 * if not successful after 2 seconds we ignore it (but keep
2754 * trying). This is to enable a debug printout even if a
2755 * tasklist_lock-holding task deadlocks or crashes.
2756 */
2757retry:
2758 if (!read_trylock(&tasklist_lock)) {
2759 if (count == 10)
2760 printk("hm, tasklist_lock locked, retrying... ");
2761 if (count) {
2762 count--;
2763 printk(" #%d", 10-count);
2764 mdelay(200);
2765 goto retry;
2766 }
2767 printk(" ignoring it.\n");
2768 unlock = 0;
2769 }
2770 if (count != 10)
2771 printk(" locked it.\n");
2772
2773 do_each_thread(g, p) {
2774 if (p->lockdep_depth)
2775 lockdep_print_held_locks(p);
2776 if (!unlock)
2777 if (read_trylock(&tasklist_lock))
2778 unlock = 1;
2779 } while_each_thread(g, p);
2780
2781 printk("\n");
2782 printk("=============================================\n\n");
2783
2784 if (unlock)
2785 read_unlock(&tasklist_lock);
2786}
2787
2788EXPORT_SYMBOL_GPL(debug_show_all_locks);
2789
2790void debug_show_held_locks(struct task_struct *task)
2791{
2792 if (unlikely(!debug_locks)) {
2793 printk("INFO: lockdep is turned off.\n");
2794 return;
2795 }
2796 lockdep_print_held_locks(task);
2797}
2798
2799EXPORT_SYMBOL_GPL(debug_show_held_locks);