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