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