1 // SPDX-License-Identifier: GPL-2.0-only
5 * Runtime locking correctness validator
7 * Started by Ingo Molnar:
9 * Copyright (C) 2006,2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
10 * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
12 * this code maps all the lock dependencies as they occur in a live kernel
13 * and will warn about the following classes of locking bugs:
15 * - lock inversion scenarios
16 * - circular lock dependencies
17 * - hardirq/softirq safe/unsafe locking bugs
19 * Bugs are reported even if the current locking scenario does not cause
20 * any deadlock at this point.
22 * I.e. if anytime in the past two locks were taken in a different order,
23 * even if it happened for another task, even if those were different
24 * locks (but of the same class as this lock), this code will detect it.
26 * Thanks to Arjan van de Ven for coming up with the initial idea of
27 * mapping lock dependencies runtime.
29 #define DISABLE_BRANCH_PROFILING
30 #include <linux/mutex.h>
31 #include <linux/sched.h>
32 #include <linux/sched/clock.h>
33 #include <linux/sched/task.h>
34 #include <linux/sched/mm.h>
35 #include <linux/delay.h>
36 #include <linux/module.h>
37 #include <linux/proc_fs.h>
38 #include <linux/seq_file.h>
39 #include <linux/spinlock.h>
40 #include <linux/kallsyms.h>
41 #include <linux/interrupt.h>
42 #include <linux/stacktrace.h>
43 #include <linux/debug_locks.h>
44 #include <linux/irqflags.h>
45 #include <linux/utsname.h>
46 #include <linux/hash.h>
47 #include <linux/ftrace.h>
48 #include <linux/stringify.h>
49 #include <linux/bitmap.h>
50 #include <linux/bitops.h>
51 #include <linux/gfp.h>
52 #include <linux/random.h>
53 #include <linux/jhash.h>
54 #include <linux/nmi.h>
55 #include <linux/rcupdate.h>
56 #include <linux/kprobes.h>
58 #include <asm/sections.h>
60 #include "lockdep_internals.h"
62 #define CREATE_TRACE_POINTS
63 #include <trace/events/lock.h>
65 #ifdef CONFIG_PROVE_LOCKING
66 int prove_locking
= 1;
67 module_param(prove_locking
, int, 0644);
69 #define prove_locking 0
72 #ifdef CONFIG_LOCK_STAT
74 module_param(lock_stat
, int, 0644);
80 * lockdep_lock: protects the lockdep graph, the hashes and the
81 * class/list/hash allocators.
83 * This is one of the rare exceptions where it's justified
84 * to use a raw spinlock - we really dont want the spinlock
85 * code to recurse back into the lockdep code...
87 static arch_spinlock_t lockdep_lock
= (arch_spinlock_t
)__ARCH_SPIN_LOCK_UNLOCKED
;
88 static struct task_struct
*lockdep_selftest_task_struct
;
90 static int graph_lock(void)
92 arch_spin_lock(&lockdep_lock
);
94 * Make sure that if another CPU detected a bug while
95 * walking the graph we dont change it (while the other
96 * CPU is busy printing out stuff with the graph lock
100 arch_spin_unlock(&lockdep_lock
);
103 /* prevent any recursions within lockdep from causing deadlocks */
104 current
->lockdep_recursion
++;
108 static inline int graph_unlock(void)
110 if (debug_locks
&& !arch_spin_is_locked(&lockdep_lock
)) {
112 * The lockdep graph lock isn't locked while we expect it to
113 * be, we're confused now, bye!
115 return DEBUG_LOCKS_WARN_ON(1);
118 current
->lockdep_recursion
--;
119 arch_spin_unlock(&lockdep_lock
);
124 * Turn lock debugging off and return with 0 if it was off already,
125 * and also release the graph lock:
127 static inline int debug_locks_off_graph_unlock(void)
129 int ret
= debug_locks_off();
131 arch_spin_unlock(&lockdep_lock
);
136 unsigned long nr_list_entries
;
137 static struct lock_list list_entries
[MAX_LOCKDEP_ENTRIES
];
138 static DECLARE_BITMAP(list_entries_in_use
, MAX_LOCKDEP_ENTRIES
);
141 * All data structures here are protected by the global debug_lock.
143 * nr_lock_classes is the number of elements of lock_classes[] that is
146 #define KEYHASH_BITS (MAX_LOCKDEP_KEYS_BITS - 1)
147 #define KEYHASH_SIZE (1UL << KEYHASH_BITS)
148 static struct hlist_head lock_keys_hash
[KEYHASH_SIZE
];
149 unsigned long nr_lock_classes
;
150 #ifndef CONFIG_DEBUG_LOCKDEP
153 struct lock_class lock_classes
[MAX_LOCKDEP_KEYS
];
154 static DECLARE_BITMAP(lock_classes_in_use
, MAX_LOCKDEP_KEYS
);
156 static inline struct lock_class
*hlock_class(struct held_lock
*hlock
)
158 unsigned int class_idx
= hlock
->class_idx
;
160 /* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfield */
163 if (!test_bit(class_idx
, lock_classes_in_use
)) {
165 * Someone passed in garbage, we give up.
167 DEBUG_LOCKS_WARN_ON(1);
172 * At this point, if the passed hlock->class_idx is still garbage,
173 * we just have to live with it
175 return lock_classes
+ class_idx
;
178 #ifdef CONFIG_LOCK_STAT
179 static DEFINE_PER_CPU(struct lock_class_stats
[MAX_LOCKDEP_KEYS
], cpu_lock_stats
);
181 static inline u64
lockstat_clock(void)
183 return local_clock();
186 static int lock_point(unsigned long points
[], unsigned long ip
)
190 for (i
= 0; i
< LOCKSTAT_POINTS
; i
++) {
191 if (points
[i
] == 0) {
202 static void lock_time_inc(struct lock_time
*lt
, u64 time
)
207 if (time
< lt
->min
|| !lt
->nr
)
214 static inline void lock_time_add(struct lock_time
*src
, struct lock_time
*dst
)
219 if (src
->max
> dst
->max
)
222 if (src
->min
< dst
->min
|| !dst
->nr
)
225 dst
->total
+= src
->total
;
229 struct lock_class_stats
lock_stats(struct lock_class
*class)
231 struct lock_class_stats stats
;
234 memset(&stats
, 0, sizeof(struct lock_class_stats
));
235 for_each_possible_cpu(cpu
) {
236 struct lock_class_stats
*pcs
=
237 &per_cpu(cpu_lock_stats
, cpu
)[class - lock_classes
];
239 for (i
= 0; i
< ARRAY_SIZE(stats
.contention_point
); i
++)
240 stats
.contention_point
[i
] += pcs
->contention_point
[i
];
242 for (i
= 0; i
< ARRAY_SIZE(stats
.contending_point
); i
++)
243 stats
.contending_point
[i
] += pcs
->contending_point
[i
];
245 lock_time_add(&pcs
->read_waittime
, &stats
.read_waittime
);
246 lock_time_add(&pcs
->write_waittime
, &stats
.write_waittime
);
248 lock_time_add(&pcs
->read_holdtime
, &stats
.read_holdtime
);
249 lock_time_add(&pcs
->write_holdtime
, &stats
.write_holdtime
);
251 for (i
= 0; i
< ARRAY_SIZE(stats
.bounces
); i
++)
252 stats
.bounces
[i
] += pcs
->bounces
[i
];
258 void clear_lock_stats(struct lock_class
*class)
262 for_each_possible_cpu(cpu
) {
263 struct lock_class_stats
*cpu_stats
=
264 &per_cpu(cpu_lock_stats
, cpu
)[class - lock_classes
];
266 memset(cpu_stats
, 0, sizeof(struct lock_class_stats
));
268 memset(class->contention_point
, 0, sizeof(class->contention_point
));
269 memset(class->contending_point
, 0, sizeof(class->contending_point
));
272 static struct lock_class_stats
*get_lock_stats(struct lock_class
*class)
274 return &this_cpu_ptr(cpu_lock_stats
)[class - lock_classes
];
277 static void lock_release_holdtime(struct held_lock
*hlock
)
279 struct lock_class_stats
*stats
;
285 holdtime
= lockstat_clock() - hlock
->holdtime_stamp
;
287 stats
= get_lock_stats(hlock_class(hlock
));
289 lock_time_inc(&stats
->read_holdtime
, holdtime
);
291 lock_time_inc(&stats
->write_holdtime
, holdtime
);
294 static inline void lock_release_holdtime(struct held_lock
*hlock
)
300 * We keep a global list of all lock classes. The list is only accessed with
301 * the lockdep spinlock lock held. free_lock_classes is a list with free
302 * elements. These elements are linked together by the lock_entry member in
305 LIST_HEAD(all_lock_classes
);
306 static LIST_HEAD(free_lock_classes
);
309 * struct pending_free - information about data structures about to be freed
310 * @zapped: Head of a list with struct lock_class elements.
311 * @lock_chains_being_freed: Bitmap that indicates which lock_chains[] elements
312 * are about to be freed.
314 struct pending_free
{
315 struct list_head zapped
;
316 DECLARE_BITMAP(lock_chains_being_freed
, MAX_LOCKDEP_CHAINS
);
320 * struct delayed_free - data structures used for delayed freeing
322 * A data structure for delayed freeing of data structures that may be
323 * accessed by RCU readers at the time these were freed.
325 * @rcu_head: Used to schedule an RCU callback for freeing data structures.
326 * @index: Index of @pf to which freed data structures are added.
327 * @scheduled: Whether or not an RCU callback has been scheduled.
328 * @pf: Array with information about data structures about to be freed.
330 static struct delayed_free
{
331 struct rcu_head rcu_head
;
334 struct pending_free pf
[2];
338 * The lockdep classes are in a hash-table as well, for fast lookup:
340 #define CLASSHASH_BITS (MAX_LOCKDEP_KEYS_BITS - 1)
341 #define CLASSHASH_SIZE (1UL << CLASSHASH_BITS)
342 #define __classhashfn(key) hash_long((unsigned long)key, CLASSHASH_BITS)
343 #define classhashentry(key) (classhash_table + __classhashfn((key)))
345 static struct hlist_head classhash_table
[CLASSHASH_SIZE
];
348 * We put the lock dependency chains into a hash-table as well, to cache
351 #define CHAINHASH_BITS (MAX_LOCKDEP_CHAINS_BITS-1)
352 #define CHAINHASH_SIZE (1UL << CHAINHASH_BITS)
353 #define __chainhashfn(chain) hash_long(chain, CHAINHASH_BITS)
354 #define chainhashentry(chain) (chainhash_table + __chainhashfn((chain)))
356 static struct hlist_head chainhash_table
[CHAINHASH_SIZE
];
359 * The hash key of the lock dependency chains is a hash itself too:
360 * it's a hash of all locks taken up to that lock, including that lock.
361 * It's a 64-bit hash, because it's important for the keys to be
364 static inline u64
iterate_chain_key(u64 key
, u32 idx
)
366 u32 k0
= key
, k1
= key
>> 32;
368 __jhash_mix(idx
, k0
, k1
); /* Macro that modifies arguments! */
370 return k0
| (u64
)k1
<< 32;
373 void lockdep_init_task(struct task_struct
*task
)
375 task
->lockdep_depth
= 0; /* no locks held yet */
376 task
->curr_chain_key
= INITIAL_CHAIN_KEY
;
377 task
->lockdep_recursion
= 0;
380 void lockdep_off(void)
382 current
->lockdep_recursion
++;
384 EXPORT_SYMBOL(lockdep_off
);
386 void lockdep_on(void)
388 current
->lockdep_recursion
--;
390 EXPORT_SYMBOL(lockdep_on
);
392 void lockdep_set_selftest_task(struct task_struct
*task
)
394 lockdep_selftest_task_struct
= task
;
398 * Debugging switches:
402 #define VERY_VERBOSE 0
405 # define HARDIRQ_VERBOSE 1
406 # define SOFTIRQ_VERBOSE 1
408 # define HARDIRQ_VERBOSE 0
409 # define SOFTIRQ_VERBOSE 0
412 #if VERBOSE || HARDIRQ_VERBOSE || SOFTIRQ_VERBOSE
414 * Quick filtering for interesting events:
416 static int class_filter(struct lock_class
*class)
420 if (class->name_version
== 1 &&
421 !strcmp(class->name
, "lockname"))
423 if (class->name_version
== 1 &&
424 !strcmp(class->name
, "&struct->lockfield"))
427 /* Filter everything else. 1 would be to allow everything else */
432 static int verbose(struct lock_class
*class)
435 return class_filter(class);
440 static void print_lockdep_off(const char *bug_msg
)
442 printk(KERN_DEBUG
"%s\n", bug_msg
);
443 printk(KERN_DEBUG
"turning off the locking correctness validator.\n");
444 #ifdef CONFIG_LOCK_STAT
445 printk(KERN_DEBUG
"Please attach the output of /proc/lock_stat to the bug report\n");
449 unsigned long nr_stack_trace_entries
;
451 #ifdef CONFIG_PROVE_LOCKING
453 * struct lock_trace - single stack backtrace
454 * @hash_entry: Entry in a stack_trace_hash[] list.
455 * @hash: jhash() of @entries.
456 * @nr_entries: Number of entries in @entries.
457 * @entries: Actual stack backtrace.
460 struct hlist_node hash_entry
;
463 unsigned long entries
[0] __aligned(sizeof(unsigned long));
465 #define LOCK_TRACE_SIZE_IN_LONGS \
466 (sizeof(struct lock_trace) / sizeof(unsigned long))
468 * Stack-trace: sequence of lock_trace structures. Protected by the graph_lock.
470 static unsigned long stack_trace
[MAX_STACK_TRACE_ENTRIES
];
471 static struct hlist_head stack_trace_hash
[STACK_TRACE_HASH_SIZE
];
473 static bool traces_identical(struct lock_trace
*t1
, struct lock_trace
*t2
)
475 return t1
->hash
== t2
->hash
&& t1
->nr_entries
== t2
->nr_entries
&&
476 memcmp(t1
->entries
, t2
->entries
,
477 t1
->nr_entries
* sizeof(t1
->entries
[0])) == 0;
480 static struct lock_trace
*save_trace(void)
482 struct lock_trace
*trace
, *t2
;
483 struct hlist_head
*hash_head
;
487 BUILD_BUG_ON_NOT_POWER_OF_2(STACK_TRACE_HASH_SIZE
);
488 BUILD_BUG_ON(LOCK_TRACE_SIZE_IN_LONGS
>= MAX_STACK_TRACE_ENTRIES
);
490 trace
= (struct lock_trace
*)(stack_trace
+ nr_stack_trace_entries
);
491 max_entries
= MAX_STACK_TRACE_ENTRIES
- nr_stack_trace_entries
-
492 LOCK_TRACE_SIZE_IN_LONGS
;
494 if (max_entries
<= 0) {
495 if (!debug_locks_off_graph_unlock())
498 print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!");
503 trace
->nr_entries
= stack_trace_save(trace
->entries
, max_entries
, 3);
505 hash
= jhash(trace
->entries
, trace
->nr_entries
*
506 sizeof(trace
->entries
[0]), 0);
508 hash_head
= stack_trace_hash
+ (hash
& (STACK_TRACE_HASH_SIZE
- 1));
509 hlist_for_each_entry(t2
, hash_head
, hash_entry
) {
510 if (traces_identical(trace
, t2
))
513 nr_stack_trace_entries
+= LOCK_TRACE_SIZE_IN_LONGS
+ trace
->nr_entries
;
514 hlist_add_head(&trace
->hash_entry
, hash_head
);
519 /* Return the number of stack traces in the stack_trace[] array. */
520 u64
lockdep_stack_trace_count(void)
522 struct lock_trace
*trace
;
526 for (i
= 0; i
< ARRAY_SIZE(stack_trace_hash
); i
++) {
527 hlist_for_each_entry(trace
, &stack_trace_hash
[i
], hash_entry
) {
535 /* Return the number of stack hash chains that have at least one stack trace. */
536 u64
lockdep_stack_hash_count(void)
541 for (i
= 0; i
< ARRAY_SIZE(stack_trace_hash
); i
++)
542 if (!hlist_empty(&stack_trace_hash
[i
]))
549 unsigned int nr_hardirq_chains
;
550 unsigned int nr_softirq_chains
;
551 unsigned int nr_process_chains
;
552 unsigned int max_lockdep_depth
;
554 #ifdef CONFIG_DEBUG_LOCKDEP
556 * Various lockdep statistics:
558 DEFINE_PER_CPU(struct lockdep_stats
, lockdep_stats
);
561 #ifdef CONFIG_PROVE_LOCKING
566 #define __USAGE(__STATE) \
567 [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE)"-W", \
568 [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON-W", \
569 [LOCK_USED_IN_##__STATE##_READ] = "IN-"__stringify(__STATE)"-R",\
570 [LOCK_ENABLED_##__STATE##_READ] = __stringify(__STATE)"-ON-R",
572 static const char *usage_str
[] =
574 #define LOCKDEP_STATE(__STATE) __USAGE(__STATE)
575 #include "lockdep_states.h"
577 [LOCK_USED
] = "INITIAL USE",
581 const char *__get_key_name(const struct lockdep_subclass_key
*key
, char *str
)
583 return kallsyms_lookup((unsigned long)key
, NULL
, NULL
, NULL
, str
);
586 static inline unsigned long lock_flag(enum lock_usage_bit bit
)
591 static char get_usage_char(struct lock_class
*class, enum lock_usage_bit bit
)
594 * The usage character defaults to '.' (i.e., irqs disabled and not in
595 * irq context), which is the safest usage category.
600 * The order of the following usage checks matters, which will
601 * result in the outcome character as follows:
603 * - '+': irq is enabled and not in irq context
604 * - '-': in irq context and irq is disabled
605 * - '?': in irq context and irq is enabled
607 if (class->usage_mask
& lock_flag(bit
+ LOCK_USAGE_DIR_MASK
)) {
609 if (class->usage_mask
& lock_flag(bit
))
611 } else if (class->usage_mask
& lock_flag(bit
))
617 void get_usage_chars(struct lock_class
*class, char usage
[LOCK_USAGE_CHARS
])
621 #define LOCKDEP_STATE(__STATE) \
622 usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE); \
623 usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_READ);
624 #include "lockdep_states.h"
630 static void __print_lock_name(struct lock_class
*class)
632 char str
[KSYM_NAME_LEN
];
637 name
= __get_key_name(class->key
, str
);
638 printk(KERN_CONT
"%s", name
);
640 printk(KERN_CONT
"%s", name
);
641 if (class->name_version
> 1)
642 printk(KERN_CONT
"#%d", class->name_version
);
644 printk(KERN_CONT
"/%d", class->subclass
);
648 static void print_lock_name(struct lock_class
*class)
650 char usage
[LOCK_USAGE_CHARS
];
652 get_usage_chars(class, usage
);
654 printk(KERN_CONT
" (");
655 __print_lock_name(class);
656 printk(KERN_CONT
"){%s}", usage
);
659 static void print_lockdep_cache(struct lockdep_map
*lock
)
662 char str
[KSYM_NAME_LEN
];
666 name
= __get_key_name(lock
->key
->subkeys
, str
);
668 printk(KERN_CONT
"%s", name
);
671 static void print_lock(struct held_lock
*hlock
)
674 * We can be called locklessly through debug_show_all_locks() so be
675 * extra careful, the hlock might have been released and cleared.
677 * If this indeed happens, lets pretend it does not hurt to continue
678 * to print the lock unless the hlock class_idx does not point to a
679 * registered class. The rationale here is: since we don't attempt
680 * to distinguish whether we are in this situation, if it just
681 * happened we can't count on class_idx to tell either.
683 struct lock_class
*lock
= hlock_class(hlock
);
686 printk(KERN_CONT
"<RELEASED>\n");
690 printk(KERN_CONT
"%px", hlock
->instance
);
691 print_lock_name(lock
);
692 printk(KERN_CONT
", at: %pS\n", (void *)hlock
->acquire_ip
);
695 static void lockdep_print_held_locks(struct task_struct
*p
)
697 int i
, depth
= READ_ONCE(p
->lockdep_depth
);
700 printk("no locks held by %s/%d.\n", p
->comm
, task_pid_nr(p
));
702 printk("%d lock%s held by %s/%d:\n", depth
,
703 depth
> 1 ? "s" : "", p
->comm
, task_pid_nr(p
));
705 * It's not reliable to print a task's held locks if it's not sleeping
706 * and it's not the current task.
708 if (p
->state
== TASK_RUNNING
&& p
!= current
)
710 for (i
= 0; i
< depth
; i
++) {
712 print_lock(p
->held_locks
+ i
);
716 static void print_kernel_ident(void)
718 printk("%s %.*s %s\n", init_utsname()->release
,
719 (int)strcspn(init_utsname()->version
, " "),
720 init_utsname()->version
,
724 static int very_verbose(struct lock_class
*class)
727 return class_filter(class);
733 * Is this the address of a static object:
736 static int static_obj(const void *obj
)
738 unsigned long start
= (unsigned long) &_stext
,
739 end
= (unsigned long) &_end
,
740 addr
= (unsigned long) obj
;
742 if (arch_is_kernel_initmem_freed(addr
))
748 if ((addr
>= start
) && (addr
< end
))
751 if (arch_is_kernel_data(addr
))
755 * in-kernel percpu var?
757 if (is_kernel_percpu_address(addr
))
761 * module static or percpu var?
763 return is_module_address(addr
) || is_module_percpu_address(addr
);
768 * To make lock name printouts unique, we calculate a unique
769 * class->name_version generation counter. The caller must hold the graph
772 static int count_matching_names(struct lock_class
*new_class
)
774 struct lock_class
*class;
777 if (!new_class
->name
)
780 list_for_each_entry(class, &all_lock_classes
, lock_entry
) {
781 if (new_class
->key
- new_class
->subclass
== class->key
)
782 return class->name_version
;
783 if (class->name
&& !strcmp(class->name
, new_class
->name
))
784 count
= max(count
, class->name_version
);
790 static inline struct lock_class
*
791 look_up_lock_class(const struct lockdep_map
*lock
, unsigned int subclass
)
793 struct lockdep_subclass_key
*key
;
794 struct hlist_head
*hash_head
;
795 struct lock_class
*class;
797 if (unlikely(subclass
>= MAX_LOCKDEP_SUBCLASSES
)) {
800 "BUG: looking up invalid subclass: %u\n", subclass
);
802 "turning off the locking correctness validator.\n");
808 * If it is not initialised then it has never been locked,
809 * so it won't be present in the hash table.
811 if (unlikely(!lock
->key
))
815 * NOTE: the class-key must be unique. For dynamic locks, a static
816 * lock_class_key variable is passed in through the mutex_init()
817 * (or spin_lock_init()) call - which acts as the key. For static
818 * locks we use the lock object itself as the key.
820 BUILD_BUG_ON(sizeof(struct lock_class_key
) >
821 sizeof(struct lockdep_map
));
823 key
= lock
->key
->subkeys
+ subclass
;
825 hash_head
= classhashentry(key
);
828 * We do an RCU walk of the hash, see lockdep_free_key_range().
830 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
833 hlist_for_each_entry_rcu(class, hash_head
, hash_entry
) {
834 if (class->key
== key
) {
836 * Huh! same key, different name? Did someone trample
837 * on some memory? We're most confused.
839 WARN_ON_ONCE(class->name
!= lock
->name
&&
840 lock
->key
!= &__lockdep_no_validate__
);
849 * Static locks do not have their class-keys yet - for them the key is
850 * the lock object itself. If the lock is in the per cpu area, the
851 * canonical address of the lock (per cpu offset removed) is used.
853 static bool assign_lock_key(struct lockdep_map
*lock
)
855 unsigned long can_addr
, addr
= (unsigned long)lock
;
859 * lockdep_free_key_range() assumes that struct lock_class_key
860 * objects do not overlap. Since we use the address of lock
861 * objects as class key for static objects, check whether the
862 * size of lock_class_key objects does not exceed the size of
863 * the smallest lock object.
865 BUILD_BUG_ON(sizeof(struct lock_class_key
) > sizeof(raw_spinlock_t
));
868 if (__is_kernel_percpu_address(addr
, &can_addr
))
869 lock
->key
= (void *)can_addr
;
870 else if (__is_module_percpu_address(addr
, &can_addr
))
871 lock
->key
= (void *)can_addr
;
872 else if (static_obj(lock
))
873 lock
->key
= (void *)lock
;
875 /* Debug-check: all keys must be persistent! */
877 pr_err("INFO: trying to register non-static key.\n");
878 pr_err("the code is fine but needs lockdep annotation.\n");
879 pr_err("turning off the locking correctness validator.\n");
887 #ifdef CONFIG_DEBUG_LOCKDEP
889 /* Check whether element @e occurs in list @h */
890 static bool in_list(struct list_head
*e
, struct list_head
*h
)
894 list_for_each(f
, h
) {
903 * Check whether entry @e occurs in any of the locks_after or locks_before
906 static bool in_any_class_list(struct list_head
*e
)
908 struct lock_class
*class;
911 for (i
= 0; i
< ARRAY_SIZE(lock_classes
); i
++) {
912 class = &lock_classes
[i
];
913 if (in_list(e
, &class->locks_after
) ||
914 in_list(e
, &class->locks_before
))
920 static bool class_lock_list_valid(struct lock_class
*c
, struct list_head
*h
)
924 list_for_each_entry(e
, h
, entry
) {
925 if (e
->links_to
!= c
) {
926 printk(KERN_INFO
"class %s: mismatch for lock entry %ld; class %s <> %s",
928 (unsigned long)(e
- list_entries
),
929 e
->links_to
&& e
->links_to
->name
?
930 e
->links_to
->name
: "(?)",
931 e
->class && e
->class->name
? e
->class->name
:
939 #ifdef CONFIG_PROVE_LOCKING
940 static u16 chain_hlocks
[MAX_LOCKDEP_CHAIN_HLOCKS
];
943 static bool check_lock_chain_key(struct lock_chain
*chain
)
945 #ifdef CONFIG_PROVE_LOCKING
946 u64 chain_key
= INITIAL_CHAIN_KEY
;
949 for (i
= chain
->base
; i
< chain
->base
+ chain
->depth
; i
++)
950 chain_key
= iterate_chain_key(chain_key
, chain_hlocks
[i
]);
952 * The 'unsigned long long' casts avoid that a compiler warning
953 * is reported when building tools/lib/lockdep.
955 if (chain
->chain_key
!= chain_key
) {
956 printk(KERN_INFO
"chain %lld: key %#llx <> %#llx\n",
957 (unsigned long long)(chain
- lock_chains
),
958 (unsigned long long)chain
->chain_key
,
959 (unsigned long long)chain_key
);
966 static bool in_any_zapped_class_list(struct lock_class
*class)
968 struct pending_free
*pf
;
971 for (i
= 0, pf
= delayed_free
.pf
; i
< ARRAY_SIZE(delayed_free
.pf
); i
++, pf
++) {
972 if (in_list(&class->lock_entry
, &pf
->zapped
))
979 static bool __check_data_structures(void)
981 struct lock_class
*class;
982 struct lock_chain
*chain
;
983 struct hlist_head
*head
;
987 /* Check whether all classes occur in a lock list. */
988 for (i
= 0; i
< ARRAY_SIZE(lock_classes
); i
++) {
989 class = &lock_classes
[i
];
990 if (!in_list(&class->lock_entry
, &all_lock_classes
) &&
991 !in_list(&class->lock_entry
, &free_lock_classes
) &&
992 !in_any_zapped_class_list(class)) {
993 printk(KERN_INFO
"class %px/%s is not in any class list\n",
994 class, class->name
? : "(?)");
999 /* Check whether all classes have valid lock lists. */
1000 for (i
= 0; i
< ARRAY_SIZE(lock_classes
); i
++) {
1001 class = &lock_classes
[i
];
1002 if (!class_lock_list_valid(class, &class->locks_before
))
1004 if (!class_lock_list_valid(class, &class->locks_after
))
1008 /* Check the chain_key of all lock chains. */
1009 for (i
= 0; i
< ARRAY_SIZE(chainhash_table
); i
++) {
1010 head
= chainhash_table
+ i
;
1011 hlist_for_each_entry_rcu(chain
, head
, entry
) {
1012 if (!check_lock_chain_key(chain
))
1018 * Check whether all list entries that are in use occur in a class
1021 for_each_set_bit(i
, list_entries_in_use
, ARRAY_SIZE(list_entries
)) {
1022 e
= list_entries
+ i
;
1023 if (!in_any_class_list(&e
->entry
)) {
1024 printk(KERN_INFO
"list entry %d is not in any class list; class %s <> %s\n",
1025 (unsigned int)(e
- list_entries
),
1026 e
->class->name
? : "(?)",
1027 e
->links_to
->name
? : "(?)");
1033 * Check whether all list entries that are not in use do not occur in
1034 * a class lock list.
1036 for_each_clear_bit(i
, list_entries_in_use
, ARRAY_SIZE(list_entries
)) {
1037 e
= list_entries
+ i
;
1038 if (in_any_class_list(&e
->entry
)) {
1039 printk(KERN_INFO
"list entry %d occurs in a class list; class %s <> %s\n",
1040 (unsigned int)(e
- list_entries
),
1041 e
->class && e
->class->name
? e
->class->name
:
1043 e
->links_to
&& e
->links_to
->name
?
1044 e
->links_to
->name
: "(?)");
1052 int check_consistency
= 0;
1053 module_param(check_consistency
, int, 0644);
1055 static void check_data_structures(void)
1057 static bool once
= false;
1059 if (check_consistency
&& !once
) {
1060 if (!__check_data_structures()) {
1067 #else /* CONFIG_DEBUG_LOCKDEP */
1069 static inline void check_data_structures(void) { }
1071 #endif /* CONFIG_DEBUG_LOCKDEP */
1074 * Initialize the lock_classes[] array elements, the free_lock_classes list
1075 * and also the delayed_free structure.
1077 static void init_data_structures_once(void)
1079 static bool ds_initialized
, rcu_head_initialized
;
1082 if (likely(rcu_head_initialized
))
1085 if (system_state
>= SYSTEM_SCHEDULING
) {
1086 init_rcu_head(&delayed_free
.rcu_head
);
1087 rcu_head_initialized
= true;
1093 ds_initialized
= true;
1095 INIT_LIST_HEAD(&delayed_free
.pf
[0].zapped
);
1096 INIT_LIST_HEAD(&delayed_free
.pf
[1].zapped
);
1098 for (i
= 0; i
< ARRAY_SIZE(lock_classes
); i
++) {
1099 list_add_tail(&lock_classes
[i
].lock_entry
, &free_lock_classes
);
1100 INIT_LIST_HEAD(&lock_classes
[i
].locks_after
);
1101 INIT_LIST_HEAD(&lock_classes
[i
].locks_before
);
1105 static inline struct hlist_head
*keyhashentry(const struct lock_class_key
*key
)
1107 unsigned long hash
= hash_long((uintptr_t)key
, KEYHASH_BITS
);
1109 return lock_keys_hash
+ hash
;
1112 /* Register a dynamically allocated key. */
1113 void lockdep_register_key(struct lock_class_key
*key
)
1115 struct hlist_head
*hash_head
;
1116 struct lock_class_key
*k
;
1117 unsigned long flags
;
1119 if (WARN_ON_ONCE(static_obj(key
)))
1121 hash_head
= keyhashentry(key
);
1123 raw_local_irq_save(flags
);
1126 hlist_for_each_entry_rcu(k
, hash_head
, hash_entry
) {
1127 if (WARN_ON_ONCE(k
== key
))
1130 hlist_add_head_rcu(&key
->hash_entry
, hash_head
);
1134 raw_local_irq_restore(flags
);
1136 EXPORT_SYMBOL_GPL(lockdep_register_key
);
1138 /* Check whether a key has been registered as a dynamic key. */
1139 static bool is_dynamic_key(const struct lock_class_key
*key
)
1141 struct hlist_head
*hash_head
;
1142 struct lock_class_key
*k
;
1145 if (WARN_ON_ONCE(static_obj(key
)))
1149 * If lock debugging is disabled lock_keys_hash[] may contain
1150 * pointers to memory that has already been freed. Avoid triggering
1151 * a use-after-free in that case by returning early.
1156 hash_head
= keyhashentry(key
);
1159 hlist_for_each_entry_rcu(k
, hash_head
, hash_entry
) {
1171 * Register a lock's class in the hash-table, if the class is not present
1172 * yet. Otherwise we look it up. We cache the result in the lock object
1173 * itself, so actual lookup of the hash should be once per lock object.
1175 static struct lock_class
*
1176 register_lock_class(struct lockdep_map
*lock
, unsigned int subclass
, int force
)
1178 struct lockdep_subclass_key
*key
;
1179 struct hlist_head
*hash_head
;
1180 struct lock_class
*class;
1182 DEBUG_LOCKS_WARN_ON(!irqs_disabled());
1184 class = look_up_lock_class(lock
, subclass
);
1186 goto out_set_class_cache
;
1189 if (!assign_lock_key(lock
))
1191 } else if (!static_obj(lock
->key
) && !is_dynamic_key(lock
->key
)) {
1195 key
= lock
->key
->subkeys
+ subclass
;
1196 hash_head
= classhashentry(key
);
1198 if (!graph_lock()) {
1202 * We have to do the hash-walk again, to avoid races
1205 hlist_for_each_entry_rcu(class, hash_head
, hash_entry
) {
1206 if (class->key
== key
)
1207 goto out_unlock_set
;
1210 init_data_structures_once();
1212 /* Allocate a new lock class and add it to the hash. */
1213 class = list_first_entry_or_null(&free_lock_classes
, typeof(*class),
1216 if (!debug_locks_off_graph_unlock()) {
1220 print_lockdep_off("BUG: MAX_LOCKDEP_KEYS too low!");
1225 __set_bit(class - lock_classes
, lock_classes_in_use
);
1226 debug_atomic_inc(nr_unused_locks
);
1228 class->name
= lock
->name
;
1229 class->subclass
= subclass
;
1230 WARN_ON_ONCE(!list_empty(&class->locks_before
));
1231 WARN_ON_ONCE(!list_empty(&class->locks_after
));
1232 class->name_version
= count_matching_names(class);
1234 * We use RCU's safe list-add method to make
1235 * parallel walking of the hash-list safe:
1237 hlist_add_head_rcu(&class->hash_entry
, hash_head
);
1239 * Remove the class from the free list and add it to the global list
1242 list_move_tail(&class->lock_entry
, &all_lock_classes
);
1244 if (verbose(class)) {
1247 printk("\nnew class %px: %s", class->key
, class->name
);
1248 if (class->name_version
> 1)
1249 printk(KERN_CONT
"#%d", class->name_version
);
1250 printk(KERN_CONT
"\n");
1253 if (!graph_lock()) {
1260 out_set_class_cache
:
1261 if (!subclass
|| force
)
1262 lock
->class_cache
[0] = class;
1263 else if (subclass
< NR_LOCKDEP_CACHING_CLASSES
)
1264 lock
->class_cache
[subclass
] = class;
1267 * Hash collision, did we smoke some? We found a class with a matching
1268 * hash but the subclass -- which is hashed in -- didn't match.
1270 if (DEBUG_LOCKS_WARN_ON(class->subclass
!= subclass
))
1276 #ifdef CONFIG_PROVE_LOCKING
1278 * Allocate a lockdep entry. (assumes the graph_lock held, returns
1279 * with NULL on failure)
1281 static struct lock_list
*alloc_list_entry(void)
1283 int idx
= find_first_zero_bit(list_entries_in_use
,
1284 ARRAY_SIZE(list_entries
));
1286 if (idx
>= ARRAY_SIZE(list_entries
)) {
1287 if (!debug_locks_off_graph_unlock())
1290 print_lockdep_off("BUG: MAX_LOCKDEP_ENTRIES too low!");
1295 __set_bit(idx
, list_entries_in_use
);
1296 return list_entries
+ idx
;
1300 * Add a new dependency to the head of the list:
1302 static int add_lock_to_list(struct lock_class
*this,
1303 struct lock_class
*links_to
, struct list_head
*head
,
1304 unsigned long ip
, int distance
,
1305 const struct lock_trace
*trace
)
1307 struct lock_list
*entry
;
1309 * Lock not present yet - get a new dependency struct and
1310 * add it to the list:
1312 entry
= alloc_list_entry();
1316 entry
->class = this;
1317 entry
->links_to
= links_to
;
1318 entry
->distance
= distance
;
1319 entry
->trace
= trace
;
1321 * Both allocation and removal are done under the graph lock; but
1322 * iteration is under RCU-sched; see look_up_lock_class() and
1323 * lockdep_free_key_range().
1325 list_add_tail_rcu(&entry
->entry
, head
);
1331 * For good efficiency of modular, we use power of 2
1333 #define MAX_CIRCULAR_QUEUE_SIZE 4096UL
1334 #define CQ_MASK (MAX_CIRCULAR_QUEUE_SIZE-1)
1337 * The circular_queue and helpers are used to implement graph
1338 * breadth-first search (BFS) algorithm, by which we can determine
1339 * whether there is a path from a lock to another. In deadlock checks,
1340 * a path from the next lock to be acquired to a previous held lock
1341 * indicates that adding the <prev> -> <next> lock dependency will
1342 * produce a circle in the graph. Breadth-first search instead of
1343 * depth-first search is used in order to find the shortest (circular)
1346 struct circular_queue
{
1347 struct lock_list
*element
[MAX_CIRCULAR_QUEUE_SIZE
];
1348 unsigned int front
, rear
;
1351 static struct circular_queue lock_cq
;
1353 unsigned int max_bfs_queue_depth
;
1355 static unsigned int lockdep_dependency_gen_id
;
1357 static inline void __cq_init(struct circular_queue
*cq
)
1359 cq
->front
= cq
->rear
= 0;
1360 lockdep_dependency_gen_id
++;
1363 static inline int __cq_empty(struct circular_queue
*cq
)
1365 return (cq
->front
== cq
->rear
);
1368 static inline int __cq_full(struct circular_queue
*cq
)
1370 return ((cq
->rear
+ 1) & CQ_MASK
) == cq
->front
;
1373 static inline int __cq_enqueue(struct circular_queue
*cq
, struct lock_list
*elem
)
1378 cq
->element
[cq
->rear
] = elem
;
1379 cq
->rear
= (cq
->rear
+ 1) & CQ_MASK
;
1384 * Dequeue an element from the circular_queue, return a lock_list if
1385 * the queue is not empty, or NULL if otherwise.
1387 static inline struct lock_list
* __cq_dequeue(struct circular_queue
*cq
)
1389 struct lock_list
* lock
;
1394 lock
= cq
->element
[cq
->front
];
1395 cq
->front
= (cq
->front
+ 1) & CQ_MASK
;
1400 static inline unsigned int __cq_get_elem_count(struct circular_queue
*cq
)
1402 return (cq
->rear
- cq
->front
) & CQ_MASK
;
1405 static inline void mark_lock_accessed(struct lock_list
*lock
,
1406 struct lock_list
*parent
)
1410 nr
= lock
- list_entries
;
1411 WARN_ON(nr
>= ARRAY_SIZE(list_entries
)); /* Out-of-bounds, input fail */
1412 lock
->parent
= parent
;
1413 lock
->class->dep_gen_id
= lockdep_dependency_gen_id
;
1416 static inline unsigned long lock_accessed(struct lock_list
*lock
)
1420 nr
= lock
- list_entries
;
1421 WARN_ON(nr
>= ARRAY_SIZE(list_entries
)); /* Out-of-bounds, input fail */
1422 return lock
->class->dep_gen_id
== lockdep_dependency_gen_id
;
1425 static inline struct lock_list
*get_lock_parent(struct lock_list
*child
)
1427 return child
->parent
;
1430 static inline int get_lock_depth(struct lock_list
*child
)
1433 struct lock_list
*parent
;
1435 while ((parent
= get_lock_parent(child
))) {
1443 * Return the forward or backward dependency list.
1445 * @lock: the lock_list to get its class's dependency list
1446 * @offset: the offset to struct lock_class to determine whether it is
1447 * locks_after or locks_before
1449 static inline struct list_head
*get_dep_list(struct lock_list
*lock
, int offset
)
1451 void *lock_class
= lock
->class;
1453 return lock_class
+ offset
;
1457 * Forward- or backward-dependency search, used for both circular dependency
1458 * checking and hardirq-unsafe/softirq-unsafe checking.
1460 static int __bfs(struct lock_list
*source_entry
,
1462 int (*match
)(struct lock_list
*entry
, void *data
),
1463 struct lock_list
**target_entry
,
1466 struct lock_list
*entry
;
1467 struct lock_list
*lock
;
1468 struct list_head
*head
;
1469 struct circular_queue
*cq
= &lock_cq
;
1472 if (match(source_entry
, data
)) {
1473 *target_entry
= source_entry
;
1478 head
= get_dep_list(source_entry
, offset
);
1479 if (list_empty(head
))
1483 __cq_enqueue(cq
, source_entry
);
1485 while ((lock
= __cq_dequeue(cq
))) {
1492 head
= get_dep_list(lock
, offset
);
1494 DEBUG_LOCKS_WARN_ON(!irqs_disabled());
1496 list_for_each_entry_rcu(entry
, head
, entry
) {
1497 if (!lock_accessed(entry
)) {
1498 unsigned int cq_depth
;
1499 mark_lock_accessed(entry
, lock
);
1500 if (match(entry
, data
)) {
1501 *target_entry
= entry
;
1506 if (__cq_enqueue(cq
, entry
)) {
1510 cq_depth
= __cq_get_elem_count(cq
);
1511 if (max_bfs_queue_depth
< cq_depth
)
1512 max_bfs_queue_depth
= cq_depth
;
1520 static inline int __bfs_forwards(struct lock_list
*src_entry
,
1522 int (*match
)(struct lock_list
*entry
, void *data
),
1523 struct lock_list
**target_entry
)
1525 return __bfs(src_entry
, data
, match
, target_entry
,
1526 offsetof(struct lock_class
, locks_after
));
1530 static inline int __bfs_backwards(struct lock_list
*src_entry
,
1532 int (*match
)(struct lock_list
*entry
, void *data
),
1533 struct lock_list
**target_entry
)
1535 return __bfs(src_entry
, data
, match
, target_entry
,
1536 offsetof(struct lock_class
, locks_before
));
1540 static void print_lock_trace(const struct lock_trace
*trace
,
1541 unsigned int spaces
)
1543 stack_trace_print(trace
->entries
, trace
->nr_entries
, spaces
);
1547 * Print a dependency chain entry (this is only done when a deadlock
1548 * has been detected):
1550 static noinline
void
1551 print_circular_bug_entry(struct lock_list
*target
, int depth
)
1553 if (debug_locks_silent
)
1555 printk("\n-> #%u", depth
);
1556 print_lock_name(target
->class);
1557 printk(KERN_CONT
":\n");
1558 print_lock_trace(target
->trace
, 6);
1562 print_circular_lock_scenario(struct held_lock
*src
,
1563 struct held_lock
*tgt
,
1564 struct lock_list
*prt
)
1566 struct lock_class
*source
= hlock_class(src
);
1567 struct lock_class
*target
= hlock_class(tgt
);
1568 struct lock_class
*parent
= prt
->class;
1571 * A direct locking problem where unsafe_class lock is taken
1572 * directly by safe_class lock, then all we need to show
1573 * is the deadlock scenario, as it is obvious that the
1574 * unsafe lock is taken under the safe lock.
1576 * But if there is a chain instead, where the safe lock takes
1577 * an intermediate lock (middle_class) where this lock is
1578 * not the same as the safe lock, then the lock chain is
1579 * used to describe the problem. Otherwise we would need
1580 * to show a different CPU case for each link in the chain
1581 * from the safe_class lock to the unsafe_class lock.
1583 if (parent
!= source
) {
1584 printk("Chain exists of:\n ");
1585 __print_lock_name(source
);
1586 printk(KERN_CONT
" --> ");
1587 __print_lock_name(parent
);
1588 printk(KERN_CONT
" --> ");
1589 __print_lock_name(target
);
1590 printk(KERN_CONT
"\n\n");
1593 printk(" Possible unsafe locking scenario:\n\n");
1594 printk(" CPU0 CPU1\n");
1595 printk(" ---- ----\n");
1597 __print_lock_name(target
);
1598 printk(KERN_CONT
");\n");
1600 __print_lock_name(parent
);
1601 printk(KERN_CONT
");\n");
1603 __print_lock_name(target
);
1604 printk(KERN_CONT
");\n");
1606 __print_lock_name(source
);
1607 printk(KERN_CONT
");\n");
1608 printk("\n *** DEADLOCK ***\n\n");
1612 * When a circular dependency is detected, print the
1615 static noinline
void
1616 print_circular_bug_header(struct lock_list
*entry
, unsigned int depth
,
1617 struct held_lock
*check_src
,
1618 struct held_lock
*check_tgt
)
1620 struct task_struct
*curr
= current
;
1622 if (debug_locks_silent
)
1626 pr_warn("======================================================\n");
1627 pr_warn("WARNING: possible circular locking dependency detected\n");
1628 print_kernel_ident();
1629 pr_warn("------------------------------------------------------\n");
1630 pr_warn("%s/%d is trying to acquire lock:\n",
1631 curr
->comm
, task_pid_nr(curr
));
1632 print_lock(check_src
);
1634 pr_warn("\nbut task is already holding lock:\n");
1636 print_lock(check_tgt
);
1637 pr_warn("\nwhich lock already depends on the new lock.\n\n");
1638 pr_warn("\nthe existing dependency chain (in reverse order) is:\n");
1640 print_circular_bug_entry(entry
, depth
);
1643 static inline int class_equal(struct lock_list
*entry
, void *data
)
1645 return entry
->class == data
;
1648 static noinline
void print_circular_bug(struct lock_list
*this,
1649 struct lock_list
*target
,
1650 struct held_lock
*check_src
,
1651 struct held_lock
*check_tgt
)
1653 struct task_struct
*curr
= current
;
1654 struct lock_list
*parent
;
1655 struct lock_list
*first_parent
;
1658 if (!debug_locks_off_graph_unlock() || debug_locks_silent
)
1661 this->trace
= save_trace();
1665 depth
= get_lock_depth(target
);
1667 print_circular_bug_header(target
, depth
, check_src
, check_tgt
);
1669 parent
= get_lock_parent(target
);
1670 first_parent
= parent
;
1673 print_circular_bug_entry(parent
, --depth
);
1674 parent
= get_lock_parent(parent
);
1677 printk("\nother info that might help us debug this:\n\n");
1678 print_circular_lock_scenario(check_src
, check_tgt
,
1681 lockdep_print_held_locks(curr
);
1683 printk("\nstack backtrace:\n");
1687 static noinline
void print_bfs_bug(int ret
)
1689 if (!debug_locks_off_graph_unlock())
1693 * Breadth-first-search failed, graph got corrupted?
1695 WARN(1, "lockdep bfs error:%d\n", ret
);
1698 static int noop_count(struct lock_list
*entry
, void *data
)
1700 (*(unsigned long *)data
)++;
1704 static unsigned long __lockdep_count_forward_deps(struct lock_list
*this)
1706 unsigned long count
= 0;
1707 struct lock_list
*uninitialized_var(target_entry
);
1709 __bfs_forwards(this, (void *)&count
, noop_count
, &target_entry
);
1713 unsigned long lockdep_count_forward_deps(struct lock_class
*class)
1715 unsigned long ret
, flags
;
1716 struct lock_list
this;
1721 raw_local_irq_save(flags
);
1722 arch_spin_lock(&lockdep_lock
);
1723 ret
= __lockdep_count_forward_deps(&this);
1724 arch_spin_unlock(&lockdep_lock
);
1725 raw_local_irq_restore(flags
);
1730 static unsigned long __lockdep_count_backward_deps(struct lock_list
*this)
1732 unsigned long count
= 0;
1733 struct lock_list
*uninitialized_var(target_entry
);
1735 __bfs_backwards(this, (void *)&count
, noop_count
, &target_entry
);
1740 unsigned long lockdep_count_backward_deps(struct lock_class
*class)
1742 unsigned long ret
, flags
;
1743 struct lock_list
this;
1748 raw_local_irq_save(flags
);
1749 arch_spin_lock(&lockdep_lock
);
1750 ret
= __lockdep_count_backward_deps(&this);
1751 arch_spin_unlock(&lockdep_lock
);
1752 raw_local_irq_restore(flags
);
1758 * Check that the dependency graph starting at <src> can lead to
1759 * <target> or not. Print an error and return 0 if it does.
1762 check_path(struct lock_class
*target
, struct lock_list
*src_entry
,
1763 struct lock_list
**target_entry
)
1767 ret
= __bfs_forwards(src_entry
, (void *)target
, class_equal
,
1770 if (unlikely(ret
< 0))
1777 * Prove that the dependency graph starting at <src> can not
1778 * lead to <target>. If it can, there is a circle when adding
1779 * <target> -> <src> dependency.
1781 * Print an error and return 0 if it does.
1784 check_noncircular(struct held_lock
*src
, struct held_lock
*target
,
1785 struct lock_trace
**const trace
)
1788 struct lock_list
*uninitialized_var(target_entry
);
1789 struct lock_list src_entry
= {
1790 .class = hlock_class(src
),
1794 debug_atomic_inc(nr_cyclic_checks
);
1796 ret
= check_path(hlock_class(target
), &src_entry
, &target_entry
);
1798 if (unlikely(!ret
)) {
1801 * If save_trace fails here, the printing might
1802 * trigger a WARN but because of the !nr_entries it
1803 * should not do bad things.
1805 *trace
= save_trace();
1808 print_circular_bug(&src_entry
, target_entry
, src
, target
);
1814 #ifdef CONFIG_LOCKDEP_SMALL
1816 * Check that the dependency graph starting at <src> can lead to
1817 * <target> or not. If it can, <src> -> <target> dependency is already
1820 * Print an error and return 2 if it does or 1 if it does not.
1823 check_redundant(struct held_lock
*src
, struct held_lock
*target
)
1826 struct lock_list
*uninitialized_var(target_entry
);
1827 struct lock_list src_entry
= {
1828 .class = hlock_class(src
),
1832 debug_atomic_inc(nr_redundant_checks
);
1834 ret
= check_path(hlock_class(target
), &src_entry
, &target_entry
);
1837 debug_atomic_inc(nr_redundant
);
1846 #ifdef CONFIG_TRACE_IRQFLAGS
1848 static inline int usage_accumulate(struct lock_list
*entry
, void *mask
)
1850 *(unsigned long *)mask
|= entry
->class->usage_mask
;
1856 * Forwards and backwards subgraph searching, for the purposes of
1857 * proving that two subgraphs can be connected by a new dependency
1858 * without creating any illegal irq-safe -> irq-unsafe lock dependency.
1861 static inline int usage_match(struct lock_list
*entry
, void *mask
)
1863 return entry
->class->usage_mask
& *(unsigned long *)mask
;
1867 * Find a node in the forwards-direction dependency sub-graph starting
1868 * at @root->class that matches @bit.
1870 * Return 0 if such a node exists in the subgraph, and put that node
1871 * into *@target_entry.
1873 * Return 1 otherwise and keep *@target_entry unchanged.
1874 * Return <0 on error.
1877 find_usage_forwards(struct lock_list
*root
, unsigned long usage_mask
,
1878 struct lock_list
**target_entry
)
1882 debug_atomic_inc(nr_find_usage_forwards_checks
);
1884 result
= __bfs_forwards(root
, &usage_mask
, usage_match
, target_entry
);
1890 * Find a node in the backwards-direction dependency sub-graph starting
1891 * at @root->class that matches @bit.
1893 * Return 0 if such a node exists in the subgraph, and put that node
1894 * into *@target_entry.
1896 * Return 1 otherwise and keep *@target_entry unchanged.
1897 * Return <0 on error.
1900 find_usage_backwards(struct lock_list
*root
, unsigned long usage_mask
,
1901 struct lock_list
**target_entry
)
1905 debug_atomic_inc(nr_find_usage_backwards_checks
);
1907 result
= __bfs_backwards(root
, &usage_mask
, usage_match
, target_entry
);
1912 static void print_lock_class_header(struct lock_class
*class, int depth
)
1916 printk("%*s->", depth
, "");
1917 print_lock_name(class);
1918 #ifdef CONFIG_DEBUG_LOCKDEP
1919 printk(KERN_CONT
" ops: %lu", debug_class_ops_read(class));
1921 printk(KERN_CONT
" {\n");
1923 for (bit
= 0; bit
< LOCK_USAGE_STATES
; bit
++) {
1924 if (class->usage_mask
& (1 << bit
)) {
1927 len
+= printk("%*s %s", depth
, "", usage_str
[bit
]);
1928 len
+= printk(KERN_CONT
" at:\n");
1929 print_lock_trace(class->usage_traces
[bit
], len
);
1932 printk("%*s }\n", depth
, "");
1934 printk("%*s ... key at: [<%px>] %pS\n",
1935 depth
, "", class->key
, class->key
);
1939 * printk the shortest lock dependencies from @start to @end in reverse order:
1942 print_shortest_lock_dependencies(struct lock_list
*leaf
,
1943 struct lock_list
*root
)
1945 struct lock_list
*entry
= leaf
;
1948 /*compute depth from generated tree by BFS*/
1949 depth
= get_lock_depth(leaf
);
1952 print_lock_class_header(entry
->class, depth
);
1953 printk("%*s ... acquired at:\n", depth
, "");
1954 print_lock_trace(entry
->trace
, 2);
1957 if (depth
== 0 && (entry
!= root
)) {
1958 printk("lockdep:%s bad path found in chain graph\n", __func__
);
1962 entry
= get_lock_parent(entry
);
1964 } while (entry
&& (depth
>= 0));
1968 print_irq_lock_scenario(struct lock_list
*safe_entry
,
1969 struct lock_list
*unsafe_entry
,
1970 struct lock_class
*prev_class
,
1971 struct lock_class
*next_class
)
1973 struct lock_class
*safe_class
= safe_entry
->class;
1974 struct lock_class
*unsafe_class
= unsafe_entry
->class;
1975 struct lock_class
*middle_class
= prev_class
;
1977 if (middle_class
== safe_class
)
1978 middle_class
= next_class
;
1981 * A direct locking problem where unsafe_class lock is taken
1982 * directly by safe_class lock, then all we need to show
1983 * is the deadlock scenario, as it is obvious that the
1984 * unsafe lock is taken under the safe lock.
1986 * But if there is a chain instead, where the safe lock takes
1987 * an intermediate lock (middle_class) where this lock is
1988 * not the same as the safe lock, then the lock chain is
1989 * used to describe the problem. Otherwise we would need
1990 * to show a different CPU case for each link in the chain
1991 * from the safe_class lock to the unsafe_class lock.
1993 if (middle_class
!= unsafe_class
) {
1994 printk("Chain exists of:\n ");
1995 __print_lock_name(safe_class
);
1996 printk(KERN_CONT
" --> ");
1997 __print_lock_name(middle_class
);
1998 printk(KERN_CONT
" --> ");
1999 __print_lock_name(unsafe_class
);
2000 printk(KERN_CONT
"\n\n");
2003 printk(" Possible interrupt unsafe locking scenario:\n\n");
2004 printk(" CPU0 CPU1\n");
2005 printk(" ---- ----\n");
2007 __print_lock_name(unsafe_class
);
2008 printk(KERN_CONT
");\n");
2009 printk(" local_irq_disable();\n");
2011 __print_lock_name(safe_class
);
2012 printk(KERN_CONT
");\n");
2014 __print_lock_name(middle_class
);
2015 printk(KERN_CONT
");\n");
2016 printk(" <Interrupt>\n");
2018 __print_lock_name(safe_class
);
2019 printk(KERN_CONT
");\n");
2020 printk("\n *** DEADLOCK ***\n\n");
2024 print_bad_irq_dependency(struct task_struct
*curr
,
2025 struct lock_list
*prev_root
,
2026 struct lock_list
*next_root
,
2027 struct lock_list
*backwards_entry
,
2028 struct lock_list
*forwards_entry
,
2029 struct held_lock
*prev
,
2030 struct held_lock
*next
,
2031 enum lock_usage_bit bit1
,
2032 enum lock_usage_bit bit2
,
2033 const char *irqclass
)
2035 if (!debug_locks_off_graph_unlock() || debug_locks_silent
)
2039 pr_warn("=====================================================\n");
2040 pr_warn("WARNING: %s-safe -> %s-unsafe lock order detected\n",
2041 irqclass
, irqclass
);
2042 print_kernel_ident();
2043 pr_warn("-----------------------------------------------------\n");
2044 pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] is trying to acquire:\n",
2045 curr
->comm
, task_pid_nr(curr
),
2046 curr
->hardirq_context
, hardirq_count() >> HARDIRQ_SHIFT
,
2047 curr
->softirq_context
, softirq_count() >> SOFTIRQ_SHIFT
,
2048 curr
->hardirqs_enabled
,
2049 curr
->softirqs_enabled
);
2052 pr_warn("\nand this task is already holding:\n");
2054 pr_warn("which would create a new lock dependency:\n");
2055 print_lock_name(hlock_class(prev
));
2057 print_lock_name(hlock_class(next
));
2060 pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",
2062 print_lock_name(backwards_entry
->class);
2063 pr_warn("\n... which became %s-irq-safe at:\n", irqclass
);
2065 print_lock_trace(backwards_entry
->class->usage_traces
[bit1
], 1);
2067 pr_warn("\nto a %s-irq-unsafe lock:\n", irqclass
);
2068 print_lock_name(forwards_entry
->class);
2069 pr_warn("\n... which became %s-irq-unsafe at:\n", irqclass
);
2072 print_lock_trace(forwards_entry
->class->usage_traces
[bit2
], 1);
2074 pr_warn("\nother info that might help us debug this:\n\n");
2075 print_irq_lock_scenario(backwards_entry
, forwards_entry
,
2076 hlock_class(prev
), hlock_class(next
));
2078 lockdep_print_held_locks(curr
);
2080 pr_warn("\nthe dependencies between %s-irq-safe lock and the holding lock:\n", irqclass
);
2081 prev_root
->trace
= save_trace();
2082 if (!prev_root
->trace
)
2084 print_shortest_lock_dependencies(backwards_entry
, prev_root
);
2086 pr_warn("\nthe dependencies between the lock to be acquired");
2087 pr_warn(" and %s-irq-unsafe lock:\n", irqclass
);
2088 next_root
->trace
= save_trace();
2089 if (!next_root
->trace
)
2091 print_shortest_lock_dependencies(forwards_entry
, next_root
);
2093 pr_warn("\nstack backtrace:\n");
2097 static const char *state_names
[] = {
2098 #define LOCKDEP_STATE(__STATE) \
2099 __stringify(__STATE),
2100 #include "lockdep_states.h"
2101 #undef LOCKDEP_STATE
2104 static const char *state_rnames
[] = {
2105 #define LOCKDEP_STATE(__STATE) \
2106 __stringify(__STATE)"-READ",
2107 #include "lockdep_states.h"
2108 #undef LOCKDEP_STATE
2111 static inline const char *state_name(enum lock_usage_bit bit
)
2113 if (bit
& LOCK_USAGE_READ_MASK
)
2114 return state_rnames
[bit
>> LOCK_USAGE_DIR_MASK
];
2116 return state_names
[bit
>> LOCK_USAGE_DIR_MASK
];
2120 * The bit number is encoded like:
2122 * bit0: 0 exclusive, 1 read lock
2123 * bit1: 0 used in irq, 1 irq enabled
2126 static int exclusive_bit(int new_bit
)
2128 int state
= new_bit
& LOCK_USAGE_STATE_MASK
;
2129 int dir
= new_bit
& LOCK_USAGE_DIR_MASK
;
2132 * keep state, bit flip the direction and strip read.
2134 return state
| (dir
^ LOCK_USAGE_DIR_MASK
);
2138 * Observe that when given a bitmask where each bitnr is encoded as above, a
2139 * right shift of the mask transforms the individual bitnrs as -1 and
2140 * conversely, a left shift transforms into +1 for the individual bitnrs.
2142 * So for all bits whose number have LOCK_ENABLED_* set (bitnr1 == 1), we can
2143 * create the mask with those bit numbers using LOCK_USED_IN_* (bitnr1 == 0)
2144 * instead by subtracting the bit number by 2, or shifting the mask right by 2.
2146 * Similarly, bitnr1 == 0 becomes bitnr1 == 1 by adding 2, or shifting left 2.
2148 * So split the mask (note that LOCKF_ENABLED_IRQ_ALL|LOCKF_USED_IN_IRQ_ALL is
2149 * all bits set) and recompose with bitnr1 flipped.
2151 static unsigned long invert_dir_mask(unsigned long mask
)
2153 unsigned long excl
= 0;
2156 excl
|= (mask
& LOCKF_ENABLED_IRQ_ALL
) >> LOCK_USAGE_DIR_MASK
;
2157 excl
|= (mask
& LOCKF_USED_IN_IRQ_ALL
) << LOCK_USAGE_DIR_MASK
;
2163 * As above, we clear bitnr0 (LOCK_*_READ off) with bitmask ops. First, for all
2164 * bits with bitnr0 set (LOCK_*_READ), add those with bitnr0 cleared (LOCK_*).
2165 * And then mask out all bitnr0.
2167 static unsigned long exclusive_mask(unsigned long mask
)
2169 unsigned long excl
= invert_dir_mask(mask
);
2172 excl
|= (excl
& LOCKF_IRQ_READ
) >> LOCK_USAGE_READ_MASK
;
2173 excl
&= ~LOCKF_IRQ_READ
;
2179 * Retrieve the _possible_ original mask to which @mask is
2180 * exclusive. Ie: this is the opposite of exclusive_mask().
2181 * Note that 2 possible original bits can match an exclusive
2182 * bit: one has LOCK_USAGE_READ_MASK set, the other has it
2183 * cleared. So both are returned for each exclusive bit.
2185 static unsigned long original_mask(unsigned long mask
)
2187 unsigned long excl
= invert_dir_mask(mask
);
2189 /* Include read in existing usages */
2190 excl
|= (excl
& LOCKF_IRQ
) << LOCK_USAGE_READ_MASK
;
2196 * Find the first pair of bit match between an original
2197 * usage mask and an exclusive usage mask.
2199 static int find_exclusive_match(unsigned long mask
,
2200 unsigned long excl_mask
,
2201 enum lock_usage_bit
*bitp
,
2202 enum lock_usage_bit
*excl_bitp
)
2206 for_each_set_bit(bit
, &mask
, LOCK_USED
) {
2207 excl
= exclusive_bit(bit
);
2208 if (excl_mask
& lock_flag(excl
)) {
2218 * Prove that the new dependency does not connect a hardirq-safe(-read)
2219 * lock with a hardirq-unsafe lock - to achieve this we search
2220 * the backwards-subgraph starting at <prev>, and the
2221 * forwards-subgraph starting at <next>:
2223 static int check_irq_usage(struct task_struct
*curr
, struct held_lock
*prev
,
2224 struct held_lock
*next
)
2226 unsigned long usage_mask
= 0, forward_mask
, backward_mask
;
2227 enum lock_usage_bit forward_bit
= 0, backward_bit
= 0;
2228 struct lock_list
*uninitialized_var(target_entry1
);
2229 struct lock_list
*uninitialized_var(target_entry
);
2230 struct lock_list
this, that
;
2234 * Step 1: gather all hard/soft IRQs usages backward in an
2235 * accumulated usage mask.
2238 this.class = hlock_class(prev
);
2240 ret
= __bfs_backwards(&this, &usage_mask
, usage_accumulate
, NULL
);
2246 usage_mask
&= LOCKF_USED_IN_IRQ_ALL
;
2251 * Step 2: find exclusive uses forward that match the previous
2252 * backward accumulated mask.
2254 forward_mask
= exclusive_mask(usage_mask
);
2257 that
.class = hlock_class(next
);
2259 ret
= find_usage_forwards(&that
, forward_mask
, &target_entry1
);
2268 * Step 3: we found a bad match! Now retrieve a lock from the backward
2269 * list whose usage mask matches the exclusive usage mask from the
2270 * lock found on the forward list.
2272 backward_mask
= original_mask(target_entry1
->class->usage_mask
);
2274 ret
= find_usage_backwards(&this, backward_mask
, &target_entry
);
2279 if (DEBUG_LOCKS_WARN_ON(ret
== 1))
2283 * Step 4: narrow down to a pair of incompatible usage bits
2286 ret
= find_exclusive_match(target_entry
->class->usage_mask
,
2287 target_entry1
->class->usage_mask
,
2288 &backward_bit
, &forward_bit
);
2289 if (DEBUG_LOCKS_WARN_ON(ret
== -1))
2292 print_bad_irq_dependency(curr
, &this, &that
,
2293 target_entry
, target_entry1
,
2295 backward_bit
, forward_bit
,
2296 state_name(backward_bit
));
2303 static inline int check_irq_usage(struct task_struct
*curr
,
2304 struct held_lock
*prev
, struct held_lock
*next
)
2308 #endif /* CONFIG_TRACE_IRQFLAGS */
2310 static void inc_chains(int irq_context
)
2312 if (irq_context
& LOCK_CHAIN_HARDIRQ_CONTEXT
)
2313 nr_hardirq_chains
++;
2314 else if (irq_context
& LOCK_CHAIN_SOFTIRQ_CONTEXT
)
2315 nr_softirq_chains
++;
2317 nr_process_chains
++;
2320 static void dec_chains(int irq_context
)
2322 if (irq_context
& LOCK_CHAIN_HARDIRQ_CONTEXT
)
2323 nr_hardirq_chains
--;
2324 else if (irq_context
& LOCK_CHAIN_SOFTIRQ_CONTEXT
)
2325 nr_softirq_chains
--;
2327 nr_process_chains
--;
2331 print_deadlock_scenario(struct held_lock
*nxt
, struct held_lock
*prv
)
2333 struct lock_class
*next
= hlock_class(nxt
);
2334 struct lock_class
*prev
= hlock_class(prv
);
2336 printk(" Possible unsafe locking scenario:\n\n");
2340 __print_lock_name(prev
);
2341 printk(KERN_CONT
");\n");
2343 __print_lock_name(next
);
2344 printk(KERN_CONT
");\n");
2345 printk("\n *** DEADLOCK ***\n\n");
2346 printk(" May be due to missing lock nesting notation\n\n");
2350 print_deadlock_bug(struct task_struct
*curr
, struct held_lock
*prev
,
2351 struct held_lock
*next
)
2353 if (!debug_locks_off_graph_unlock() || debug_locks_silent
)
2357 pr_warn("============================================\n");
2358 pr_warn("WARNING: possible recursive locking detected\n");
2359 print_kernel_ident();
2360 pr_warn("--------------------------------------------\n");
2361 pr_warn("%s/%d is trying to acquire lock:\n",
2362 curr
->comm
, task_pid_nr(curr
));
2364 pr_warn("\nbut task is already holding lock:\n");
2367 pr_warn("\nother info that might help us debug this:\n");
2368 print_deadlock_scenario(next
, prev
);
2369 lockdep_print_held_locks(curr
);
2371 pr_warn("\nstack backtrace:\n");
2376 * Check whether we are holding such a class already.
2378 * (Note that this has to be done separately, because the graph cannot
2379 * detect such classes of deadlocks.)
2381 * Returns: 0 on deadlock detected, 1 on OK, 2 on recursive read
2384 check_deadlock(struct task_struct
*curr
, struct held_lock
*next
)
2386 struct held_lock
*prev
;
2387 struct held_lock
*nest
= NULL
;
2390 for (i
= 0; i
< curr
->lockdep_depth
; i
++) {
2391 prev
= curr
->held_locks
+ i
;
2393 if (prev
->instance
== next
->nest_lock
)
2396 if (hlock_class(prev
) != hlock_class(next
))
2400 * Allow read-after-read recursion of the same
2401 * lock class (i.e. read_lock(lock)+read_lock(lock)):
2403 if ((next
->read
== 2) && prev
->read
)
2407 * We're holding the nest_lock, which serializes this lock's
2408 * nesting behaviour.
2413 print_deadlock_bug(curr
, prev
, next
);
2420 * There was a chain-cache miss, and we are about to add a new dependency
2421 * to a previous lock. We validate the following rules:
2423 * - would the adding of the <prev> -> <next> dependency create a
2424 * circular dependency in the graph? [== circular deadlock]
2426 * - does the new prev->next dependency connect any hardirq-safe lock
2427 * (in the full backwards-subgraph starting at <prev>) with any
2428 * hardirq-unsafe lock (in the full forwards-subgraph starting at
2429 * <next>)? [== illegal lock inversion with hardirq contexts]
2431 * - does the new prev->next dependency connect any softirq-safe lock
2432 * (in the full backwards-subgraph starting at <prev>) with any
2433 * softirq-unsafe lock (in the full forwards-subgraph starting at
2434 * <next>)? [== illegal lock inversion with softirq contexts]
2436 * any of these scenarios could lead to a deadlock.
2438 * Then if all the validations pass, we add the forwards and backwards
2442 check_prev_add(struct task_struct
*curr
, struct held_lock
*prev
,
2443 struct held_lock
*next
, int distance
,
2444 struct lock_trace
**const trace
)
2446 struct lock_list
*entry
;
2449 if (!hlock_class(prev
)->key
|| !hlock_class(next
)->key
) {
2451 * The warning statements below may trigger a use-after-free
2452 * of the class name. It is better to trigger a use-after free
2453 * and to have the class name most of the time instead of not
2454 * having the class name available.
2456 WARN_ONCE(!debug_locks_silent
&& !hlock_class(prev
)->key
,
2457 "Detected use-after-free of lock class %px/%s\n",
2459 hlock_class(prev
)->name
);
2460 WARN_ONCE(!debug_locks_silent
&& !hlock_class(next
)->key
,
2461 "Detected use-after-free of lock class %px/%s\n",
2463 hlock_class(next
)->name
);
2468 * Prove that the new <prev> -> <next> dependency would not
2469 * create a circular dependency in the graph. (We do this by
2470 * a breadth-first search into the graph starting at <next>,
2471 * and check whether we can reach <prev>.)
2473 * The search is limited by the size of the circular queue (i.e.,
2474 * MAX_CIRCULAR_QUEUE_SIZE) which keeps track of a breadth of nodes
2475 * in the graph whose neighbours are to be checked.
2477 ret
= check_noncircular(next
, prev
, trace
);
2478 if (unlikely(ret
<= 0))
2481 if (!check_irq_usage(curr
, prev
, next
))
2485 * For recursive read-locks we do all the dependency checks,
2486 * but we dont store read-triggered dependencies (only
2487 * write-triggered dependencies). This ensures that only the
2488 * write-side dependencies matter, and that if for example a
2489 * write-lock never takes any other locks, then the reads are
2490 * equivalent to a NOP.
2492 if (next
->read
== 2 || prev
->read
== 2)
2495 * Is the <prev> -> <next> dependency already present?
2497 * (this may occur even though this is a new chain: consider
2498 * e.g. the L1 -> L2 -> L3 -> L4 and the L5 -> L1 -> L2 -> L3
2499 * chains - the second one will be new, but L1 already has
2500 * L2 added to its dependency list, due to the first chain.)
2502 list_for_each_entry(entry
, &hlock_class(prev
)->locks_after
, entry
) {
2503 if (entry
->class == hlock_class(next
)) {
2505 entry
->distance
= 1;
2510 #ifdef CONFIG_LOCKDEP_SMALL
2512 * Is the <prev> -> <next> link redundant?
2514 ret
= check_redundant(prev
, next
);
2520 *trace
= save_trace();
2526 * Ok, all validations passed, add the new lock
2527 * to the previous lock's dependency list:
2529 ret
= add_lock_to_list(hlock_class(next
), hlock_class(prev
),
2530 &hlock_class(prev
)->locks_after
,
2531 next
->acquire_ip
, distance
, *trace
);
2536 ret
= add_lock_to_list(hlock_class(prev
), hlock_class(next
),
2537 &hlock_class(next
)->locks_before
,
2538 next
->acquire_ip
, distance
, *trace
);
2546 * Add the dependency to all directly-previous locks that are 'relevant'.
2547 * The ones that are relevant are (in increasing distance from curr):
2548 * all consecutive trylock entries and the final non-trylock entry - or
2549 * the end of this context's lock-chain - whichever comes first.
2552 check_prevs_add(struct task_struct
*curr
, struct held_lock
*next
)
2554 struct lock_trace
*trace
= NULL
;
2555 int depth
= curr
->lockdep_depth
;
2556 struct held_lock
*hlock
;
2561 * Depth must not be zero for a non-head lock:
2566 * At least two relevant locks must exist for this
2569 if (curr
->held_locks
[depth
].irq_context
!=
2570 curr
->held_locks
[depth
-1].irq_context
)
2574 int distance
= curr
->lockdep_depth
- depth
+ 1;
2575 hlock
= curr
->held_locks
+ depth
- 1;
2578 * Only non-recursive-read entries get new dependencies
2581 if (hlock
->read
!= 2 && hlock
->check
) {
2582 int ret
= check_prev_add(curr
, hlock
, next
, distance
,
2588 * Stop after the first non-trylock entry,
2589 * as non-trylock entries have added their
2590 * own direct dependencies already, so this
2591 * lock is connected to them indirectly:
2593 if (!hlock
->trylock
)
2599 * End of lock-stack?
2604 * Stop the search if we cross into another context:
2606 if (curr
->held_locks
[depth
].irq_context
!=
2607 curr
->held_locks
[depth
-1].irq_context
)
2612 if (!debug_locks_off_graph_unlock())
2616 * Clearly we all shouldn't be here, but since we made it we
2617 * can reliable say we messed up our state. See the above two
2618 * gotos for reasons why we could possibly end up here.
2625 struct lock_chain lock_chains
[MAX_LOCKDEP_CHAINS
];
2626 static DECLARE_BITMAP(lock_chains_in_use
, MAX_LOCKDEP_CHAINS
);
2627 int nr_chain_hlocks
;
2628 static u16 chain_hlocks
[MAX_LOCKDEP_CHAIN_HLOCKS
];
2630 struct lock_class
*lock_chain_get_class(struct lock_chain
*chain
, int i
)
2632 return lock_classes
+ chain_hlocks
[chain
->base
+ i
];
2636 * Returns the index of the first held_lock of the current chain
2638 static inline int get_first_held_lock(struct task_struct
*curr
,
2639 struct held_lock
*hlock
)
2642 struct held_lock
*hlock_curr
;
2644 for (i
= curr
->lockdep_depth
- 1; i
>= 0; i
--) {
2645 hlock_curr
= curr
->held_locks
+ i
;
2646 if (hlock_curr
->irq_context
!= hlock
->irq_context
)
2654 #ifdef CONFIG_DEBUG_LOCKDEP
2656 * Returns the next chain_key iteration
2658 static u64
print_chain_key_iteration(int class_idx
, u64 chain_key
)
2660 u64 new_chain_key
= iterate_chain_key(chain_key
, class_idx
);
2662 printk(" class_idx:%d -> chain_key:%016Lx",
2664 (unsigned long long)new_chain_key
);
2665 return new_chain_key
;
2669 print_chain_keys_held_locks(struct task_struct
*curr
, struct held_lock
*hlock_next
)
2671 struct held_lock
*hlock
;
2672 u64 chain_key
= INITIAL_CHAIN_KEY
;
2673 int depth
= curr
->lockdep_depth
;
2674 int i
= get_first_held_lock(curr
, hlock_next
);
2676 printk("depth: %u (irq_context %u)\n", depth
- i
+ 1,
2677 hlock_next
->irq_context
);
2678 for (; i
< depth
; i
++) {
2679 hlock
= curr
->held_locks
+ i
;
2680 chain_key
= print_chain_key_iteration(hlock
->class_idx
, chain_key
);
2685 print_chain_key_iteration(hlock_next
->class_idx
, chain_key
);
2686 print_lock(hlock_next
);
2689 static void print_chain_keys_chain(struct lock_chain
*chain
)
2692 u64 chain_key
= INITIAL_CHAIN_KEY
;
2695 printk("depth: %u\n", chain
->depth
);
2696 for (i
= 0; i
< chain
->depth
; i
++) {
2697 class_id
= chain_hlocks
[chain
->base
+ i
];
2698 chain_key
= print_chain_key_iteration(class_id
, chain_key
);
2700 print_lock_name(lock_classes
+ class_id
);
2705 static void print_collision(struct task_struct
*curr
,
2706 struct held_lock
*hlock_next
,
2707 struct lock_chain
*chain
)
2710 pr_warn("============================\n");
2711 pr_warn("WARNING: chain_key collision\n");
2712 print_kernel_ident();
2713 pr_warn("----------------------------\n");
2714 pr_warn("%s/%d: ", current
->comm
, task_pid_nr(current
));
2715 pr_warn("Hash chain already cached but the contents don't match!\n");
2717 pr_warn("Held locks:");
2718 print_chain_keys_held_locks(curr
, hlock_next
);
2720 pr_warn("Locks in cached chain:");
2721 print_chain_keys_chain(chain
);
2723 pr_warn("\nstack backtrace:\n");
2729 * Checks whether the chain and the current held locks are consistent
2730 * in depth and also in content. If they are not it most likely means
2731 * that there was a collision during the calculation of the chain_key.
2732 * Returns: 0 not passed, 1 passed
2734 static int check_no_collision(struct task_struct
*curr
,
2735 struct held_lock
*hlock
,
2736 struct lock_chain
*chain
)
2738 #ifdef CONFIG_DEBUG_LOCKDEP
2741 i
= get_first_held_lock(curr
, hlock
);
2743 if (DEBUG_LOCKS_WARN_ON(chain
->depth
!= curr
->lockdep_depth
- (i
- 1))) {
2744 print_collision(curr
, hlock
, chain
);
2748 for (j
= 0; j
< chain
->depth
- 1; j
++, i
++) {
2749 id
= curr
->held_locks
[i
].class_idx
;
2751 if (DEBUG_LOCKS_WARN_ON(chain_hlocks
[chain
->base
+ j
] != id
)) {
2752 print_collision(curr
, hlock
, chain
);
2761 * Given an index that is >= -1, return the index of the next lock chain.
2762 * Return -2 if there is no next lock chain.
2764 long lockdep_next_lockchain(long i
)
2766 i
= find_next_bit(lock_chains_in_use
, ARRAY_SIZE(lock_chains
), i
+ 1);
2767 return i
< ARRAY_SIZE(lock_chains
) ? i
: -2;
2770 unsigned long lock_chain_count(void)
2772 return bitmap_weight(lock_chains_in_use
, ARRAY_SIZE(lock_chains
));
2775 /* Must be called with the graph lock held. */
2776 static struct lock_chain
*alloc_lock_chain(void)
2778 int idx
= find_first_zero_bit(lock_chains_in_use
,
2779 ARRAY_SIZE(lock_chains
));
2781 if (unlikely(idx
>= ARRAY_SIZE(lock_chains
)))
2783 __set_bit(idx
, lock_chains_in_use
);
2784 return lock_chains
+ idx
;
2788 * Adds a dependency chain into chain hashtable. And must be called with
2791 * Return 0 if fail, and graph_lock is released.
2792 * Return 1 if succeed, with graph_lock held.
2794 static inline int add_chain_cache(struct task_struct
*curr
,
2795 struct held_lock
*hlock
,
2798 struct lock_class
*class = hlock_class(hlock
);
2799 struct hlist_head
*hash_head
= chainhashentry(chain_key
);
2800 struct lock_chain
*chain
;
2804 * The caller must hold the graph lock, ensure we've got IRQs
2805 * disabled to make this an IRQ-safe lock.. for recursion reasons
2806 * lockdep won't complain about its own locking errors.
2808 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
2811 chain
= alloc_lock_chain();
2813 if (!debug_locks_off_graph_unlock())
2816 print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!");
2820 chain
->chain_key
= chain_key
;
2821 chain
->irq_context
= hlock
->irq_context
;
2822 i
= get_first_held_lock(curr
, hlock
);
2823 chain
->depth
= curr
->lockdep_depth
+ 1 - i
;
2825 BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks
));
2826 BUILD_BUG_ON((1UL << 6) <= ARRAY_SIZE(curr
->held_locks
));
2827 BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks
[0])) <= ARRAY_SIZE(lock_classes
));
2829 if (likely(nr_chain_hlocks
+ chain
->depth
<= MAX_LOCKDEP_CHAIN_HLOCKS
)) {
2830 chain
->base
= nr_chain_hlocks
;
2831 for (j
= 0; j
< chain
->depth
- 1; j
++, i
++) {
2832 int lock_id
= curr
->held_locks
[i
].class_idx
;
2833 chain_hlocks
[chain
->base
+ j
] = lock_id
;
2835 chain_hlocks
[chain
->base
+ j
] = class - lock_classes
;
2836 nr_chain_hlocks
+= chain
->depth
;
2838 if (!debug_locks_off_graph_unlock())
2841 print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!");
2846 hlist_add_head_rcu(&chain
->entry
, hash_head
);
2847 debug_atomic_inc(chain_lookup_misses
);
2848 inc_chains(chain
->irq_context
);
2854 * Look up a dependency chain. Must be called with either the graph lock or
2855 * the RCU read lock held.
2857 static inline struct lock_chain
*lookup_chain_cache(u64 chain_key
)
2859 struct hlist_head
*hash_head
= chainhashentry(chain_key
);
2860 struct lock_chain
*chain
;
2862 hlist_for_each_entry_rcu(chain
, hash_head
, entry
) {
2863 if (READ_ONCE(chain
->chain_key
) == chain_key
) {
2864 debug_atomic_inc(chain_lookup_hits
);
2872 * If the key is not present yet in dependency chain cache then
2873 * add it and return 1 - in this case the new dependency chain is
2874 * validated. If the key is already hashed, return 0.
2875 * (On return with 1 graph_lock is held.)
2877 static inline int lookup_chain_cache_add(struct task_struct
*curr
,
2878 struct held_lock
*hlock
,
2881 struct lock_class
*class = hlock_class(hlock
);
2882 struct lock_chain
*chain
= lookup_chain_cache(chain_key
);
2886 if (!check_no_collision(curr
, hlock
, chain
))
2889 if (very_verbose(class)) {
2890 printk("\nhash chain already cached, key: "
2891 "%016Lx tail class: [%px] %s\n",
2892 (unsigned long long)chain_key
,
2893 class->key
, class->name
);
2899 if (very_verbose(class)) {
2900 printk("\nnew hash chain, key: %016Lx tail class: [%px] %s\n",
2901 (unsigned long long)chain_key
, class->key
, class->name
);
2908 * We have to walk the chain again locked - to avoid duplicates:
2910 chain
= lookup_chain_cache(chain_key
);
2916 if (!add_chain_cache(curr
, hlock
, chain_key
))
2922 static int validate_chain(struct task_struct
*curr
,
2923 struct held_lock
*hlock
,
2924 int chain_head
, u64 chain_key
)
2927 * Trylock needs to maintain the stack of held locks, but it
2928 * does not add new dependencies, because trylock can be done
2931 * We look up the chain_key and do the O(N^2) check and update of
2932 * the dependencies only if this is a new dependency chain.
2933 * (If lookup_chain_cache_add() return with 1 it acquires
2934 * graph_lock for us)
2936 if (!hlock
->trylock
&& hlock
->check
&&
2937 lookup_chain_cache_add(curr
, hlock
, chain_key
)) {
2939 * Check whether last held lock:
2941 * - is irq-safe, if this lock is irq-unsafe
2942 * - is softirq-safe, if this lock is hardirq-unsafe
2944 * And check whether the new lock's dependency graph
2945 * could lead back to the previous lock:
2947 * - within the current held-lock stack
2948 * - across our accumulated lock dependency records
2950 * any of these scenarios could lead to a deadlock.
2953 * The simple case: does the current hold the same lock
2956 int ret
= check_deadlock(curr
, hlock
);
2961 * Mark recursive read, as we jump over it when
2962 * building dependencies (just like we jump over
2968 * Add dependency only if this lock is not the head
2969 * of the chain, and if it's not a secondary read-lock:
2971 if (!chain_head
&& ret
!= 2) {
2972 if (!check_prevs_add(curr
, hlock
))
2978 /* after lookup_chain_cache_add(): */
2979 if (unlikely(!debug_locks
))
2986 static inline int validate_chain(struct task_struct
*curr
,
2987 struct held_lock
*hlock
,
2988 int chain_head
, u64 chain_key
)
2992 #endif /* CONFIG_PROVE_LOCKING */
2995 * We are building curr_chain_key incrementally, so double-check
2996 * it from scratch, to make sure that it's done correctly:
2998 static void check_chain_key(struct task_struct
*curr
)
3000 #ifdef CONFIG_DEBUG_LOCKDEP
3001 struct held_lock
*hlock
, *prev_hlock
= NULL
;
3003 u64 chain_key
= INITIAL_CHAIN_KEY
;
3005 for (i
= 0; i
< curr
->lockdep_depth
; i
++) {
3006 hlock
= curr
->held_locks
+ i
;
3007 if (chain_key
!= hlock
->prev_chain_key
) {
3010 * We got mighty confused, our chain keys don't match
3011 * with what we expect, someone trample on our task state?
3013 WARN(1, "hm#1, depth: %u [%u], %016Lx != %016Lx\n",
3014 curr
->lockdep_depth
, i
,
3015 (unsigned long long)chain_key
,
3016 (unsigned long long)hlock
->prev_chain_key
);
3021 * hlock->class_idx can't go beyond MAX_LOCKDEP_KEYS, but is
3022 * it registered lock class index?
3024 if (DEBUG_LOCKS_WARN_ON(!test_bit(hlock
->class_idx
, lock_classes_in_use
)))
3027 if (prev_hlock
&& (prev_hlock
->irq_context
!=
3028 hlock
->irq_context
))
3029 chain_key
= INITIAL_CHAIN_KEY
;
3030 chain_key
= iterate_chain_key(chain_key
, hlock
->class_idx
);
3033 if (chain_key
!= curr
->curr_chain_key
) {
3036 * More smoking hash instead of calculating it, damn see these
3037 * numbers float.. I bet that a pink elephant stepped on my memory.
3039 WARN(1, "hm#2, depth: %u [%u], %016Lx != %016Lx\n",
3040 curr
->lockdep_depth
, i
,
3041 (unsigned long long)chain_key
,
3042 (unsigned long long)curr
->curr_chain_key
);
3047 #ifdef CONFIG_PROVE_LOCKING
3048 static int mark_lock(struct task_struct
*curr
, struct held_lock
*this,
3049 enum lock_usage_bit new_bit
);
3051 static void print_usage_bug_scenario(struct held_lock
*lock
)
3053 struct lock_class
*class = hlock_class(lock
);
3055 printk(" Possible unsafe locking scenario:\n\n");
3059 __print_lock_name(class);
3060 printk(KERN_CONT
");\n");
3061 printk(" <Interrupt>\n");
3063 __print_lock_name(class);
3064 printk(KERN_CONT
");\n");
3065 printk("\n *** DEADLOCK ***\n\n");
3069 print_usage_bug(struct task_struct
*curr
, struct held_lock
*this,
3070 enum lock_usage_bit prev_bit
, enum lock_usage_bit new_bit
)
3072 if (!debug_locks_off_graph_unlock() || debug_locks_silent
)
3076 pr_warn("================================\n");
3077 pr_warn("WARNING: inconsistent lock state\n");
3078 print_kernel_ident();
3079 pr_warn("--------------------------------\n");
3081 pr_warn("inconsistent {%s} -> {%s} usage.\n",
3082 usage_str
[prev_bit
], usage_str
[new_bit
]);
3084 pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] takes:\n",
3085 curr
->comm
, task_pid_nr(curr
),
3086 trace_hardirq_context(curr
), hardirq_count() >> HARDIRQ_SHIFT
,
3087 trace_softirq_context(curr
), softirq_count() >> SOFTIRQ_SHIFT
,
3088 trace_hardirqs_enabled(curr
),
3089 trace_softirqs_enabled(curr
));
3092 pr_warn("{%s} state was registered at:\n", usage_str
[prev_bit
]);
3093 print_lock_trace(hlock_class(this)->usage_traces
[prev_bit
], 1);
3095 print_irqtrace_events(curr
);
3096 pr_warn("\nother info that might help us debug this:\n");
3097 print_usage_bug_scenario(this);
3099 lockdep_print_held_locks(curr
);
3101 pr_warn("\nstack backtrace:\n");
3106 * Print out an error if an invalid bit is set:
3109 valid_state(struct task_struct
*curr
, struct held_lock
*this,
3110 enum lock_usage_bit new_bit
, enum lock_usage_bit bad_bit
)
3112 if (unlikely(hlock_class(this)->usage_mask
& (1 << bad_bit
))) {
3113 print_usage_bug(curr
, this, bad_bit
, new_bit
);
3121 * print irq inversion bug:
3124 print_irq_inversion_bug(struct task_struct
*curr
,
3125 struct lock_list
*root
, struct lock_list
*other
,
3126 struct held_lock
*this, int forwards
,
3127 const char *irqclass
)
3129 struct lock_list
*entry
= other
;
3130 struct lock_list
*middle
= NULL
;
3133 if (!debug_locks_off_graph_unlock() || debug_locks_silent
)
3137 pr_warn("========================================================\n");
3138 pr_warn("WARNING: possible irq lock inversion dependency detected\n");
3139 print_kernel_ident();
3140 pr_warn("--------------------------------------------------------\n");
3141 pr_warn("%s/%d just changed the state of lock:\n",
3142 curr
->comm
, task_pid_nr(curr
));
3145 pr_warn("but this lock took another, %s-unsafe lock in the past:\n", irqclass
);
3147 pr_warn("but this lock was taken by another, %s-safe lock in the past:\n", irqclass
);
3148 print_lock_name(other
->class);
3149 pr_warn("\n\nand interrupts could create inverse lock ordering between them.\n\n");
3151 pr_warn("\nother info that might help us debug this:\n");
3153 /* Find a middle lock (if one exists) */
3154 depth
= get_lock_depth(other
);
3156 if (depth
== 0 && (entry
!= root
)) {
3157 pr_warn("lockdep:%s bad path found in chain graph\n", __func__
);
3161 entry
= get_lock_parent(entry
);
3163 } while (entry
&& entry
!= root
&& (depth
>= 0));
3165 print_irq_lock_scenario(root
, other
,
3166 middle
? middle
->class : root
->class, other
->class);
3168 print_irq_lock_scenario(other
, root
,
3169 middle
? middle
->class : other
->class, root
->class);
3171 lockdep_print_held_locks(curr
);
3173 pr_warn("\nthe shortest dependencies between 2nd lock and 1st lock:\n");
3174 root
->trace
= save_trace();
3177 print_shortest_lock_dependencies(other
, root
);
3179 pr_warn("\nstack backtrace:\n");
3184 * Prove that in the forwards-direction subgraph starting at <this>
3185 * there is no lock matching <mask>:
3188 check_usage_forwards(struct task_struct
*curr
, struct held_lock
*this,
3189 enum lock_usage_bit bit
, const char *irqclass
)
3192 struct lock_list root
;
3193 struct lock_list
*uninitialized_var(target_entry
);
3196 root
.class = hlock_class(this);
3197 ret
= find_usage_forwards(&root
, lock_flag(bit
), &target_entry
);
3205 print_irq_inversion_bug(curr
, &root
, target_entry
,
3211 * Prove that in the backwards-direction subgraph starting at <this>
3212 * there is no lock matching <mask>:
3215 check_usage_backwards(struct task_struct
*curr
, struct held_lock
*this,
3216 enum lock_usage_bit bit
, const char *irqclass
)
3219 struct lock_list root
;
3220 struct lock_list
*uninitialized_var(target_entry
);
3223 root
.class = hlock_class(this);
3224 ret
= find_usage_backwards(&root
, lock_flag(bit
), &target_entry
);
3232 print_irq_inversion_bug(curr
, &root
, target_entry
,
3237 void print_irqtrace_events(struct task_struct
*curr
)
3239 printk("irq event stamp: %u\n", curr
->irq_events
);
3240 printk("hardirqs last enabled at (%u): [<%px>] %pS\n",
3241 curr
->hardirq_enable_event
, (void *)curr
->hardirq_enable_ip
,
3242 (void *)curr
->hardirq_enable_ip
);
3243 printk("hardirqs last disabled at (%u): [<%px>] %pS\n",
3244 curr
->hardirq_disable_event
, (void *)curr
->hardirq_disable_ip
,
3245 (void *)curr
->hardirq_disable_ip
);
3246 printk("softirqs last enabled at (%u): [<%px>] %pS\n",
3247 curr
->softirq_enable_event
, (void *)curr
->softirq_enable_ip
,
3248 (void *)curr
->softirq_enable_ip
);
3249 printk("softirqs last disabled at (%u): [<%px>] %pS\n",
3250 curr
->softirq_disable_event
, (void *)curr
->softirq_disable_ip
,
3251 (void *)curr
->softirq_disable_ip
);
3254 static int HARDIRQ_verbose(struct lock_class
*class)
3257 return class_filter(class);
3262 static int SOFTIRQ_verbose(struct lock_class
*class)
3265 return class_filter(class);
3270 #define STRICT_READ_CHECKS 1
3272 static int (*state_verbose_f
[])(struct lock_class
*class) = {
3273 #define LOCKDEP_STATE(__STATE) \
3275 #include "lockdep_states.h"
3276 #undef LOCKDEP_STATE
3279 static inline int state_verbose(enum lock_usage_bit bit
,
3280 struct lock_class
*class)
3282 return state_verbose_f
[bit
>> LOCK_USAGE_DIR_MASK
](class);
3285 typedef int (*check_usage_f
)(struct task_struct
*, struct held_lock
*,
3286 enum lock_usage_bit bit
, const char *name
);
3289 mark_lock_irq(struct task_struct
*curr
, struct held_lock
*this,
3290 enum lock_usage_bit new_bit
)
3292 int excl_bit
= exclusive_bit(new_bit
);
3293 int read
= new_bit
& LOCK_USAGE_READ_MASK
;
3294 int dir
= new_bit
& LOCK_USAGE_DIR_MASK
;
3297 * mark USED_IN has to look forwards -- to ensure no dependency
3298 * has ENABLED state, which would allow recursion deadlocks.
3300 * mark ENABLED has to look backwards -- to ensure no dependee
3301 * has USED_IN state, which, again, would allow recursion deadlocks.
3303 check_usage_f usage
= dir
?
3304 check_usage_backwards
: check_usage_forwards
;
3307 * Validate that this particular lock does not have conflicting
3310 if (!valid_state(curr
, this, new_bit
, excl_bit
))
3314 * Validate that the lock dependencies don't have conflicting usage
3317 if ((!read
|| STRICT_READ_CHECKS
) &&
3318 !usage(curr
, this, excl_bit
, state_name(new_bit
& ~LOCK_USAGE_READ_MASK
)))
3322 * Check for read in write conflicts
3325 if (!valid_state(curr
, this, new_bit
, excl_bit
+ LOCK_USAGE_READ_MASK
))
3328 if (STRICT_READ_CHECKS
&&
3329 !usage(curr
, this, excl_bit
+ LOCK_USAGE_READ_MASK
,
3330 state_name(new_bit
+ LOCK_USAGE_READ_MASK
)))
3334 if (state_verbose(new_bit
, hlock_class(this)))
3341 * Mark all held locks with a usage bit:
3344 mark_held_locks(struct task_struct
*curr
, enum lock_usage_bit base_bit
)
3346 struct held_lock
*hlock
;
3349 for (i
= 0; i
< curr
->lockdep_depth
; i
++) {
3350 enum lock_usage_bit hlock_bit
= base_bit
;
3351 hlock
= curr
->held_locks
+ i
;
3354 hlock_bit
+= LOCK_USAGE_READ_MASK
;
3356 BUG_ON(hlock_bit
>= LOCK_USAGE_STATES
);
3361 if (!mark_lock(curr
, hlock
, hlock_bit
))
3369 * Hardirqs will be enabled:
3371 static void __trace_hardirqs_on_caller(unsigned long ip
)
3373 struct task_struct
*curr
= current
;
3375 /* we'll do an OFF -> ON transition: */
3376 curr
->hardirqs_enabled
= 1;
3379 * We are going to turn hardirqs on, so set the
3380 * usage bit for all held locks:
3382 if (!mark_held_locks(curr
, LOCK_ENABLED_HARDIRQ
))
3385 * If we have softirqs enabled, then set the usage
3386 * bit for all held locks. (disabled hardirqs prevented
3387 * this bit from being set before)
3389 if (curr
->softirqs_enabled
)
3390 if (!mark_held_locks(curr
, LOCK_ENABLED_SOFTIRQ
))
3393 curr
->hardirq_enable_ip
= ip
;
3394 curr
->hardirq_enable_event
= ++curr
->irq_events
;
3395 debug_atomic_inc(hardirqs_on_events
);
3398 void lockdep_hardirqs_on(unsigned long ip
)
3400 if (unlikely(!debug_locks
|| current
->lockdep_recursion
))
3403 if (unlikely(current
->hardirqs_enabled
)) {
3405 * Neither irq nor preemption are disabled here
3406 * so this is racy by nature but losing one hit
3407 * in a stat is not a big deal.
3409 __debug_atomic_inc(redundant_hardirqs_on
);
3414 * We're enabling irqs and according to our state above irqs weren't
3415 * already enabled, yet we find the hardware thinks they are in fact
3416 * enabled.. someone messed up their IRQ state tracing.
3418 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
3422 * See the fine text that goes along with this variable definition.
3424 if (DEBUG_LOCKS_WARN_ON(early_boot_irqs_disabled
))
3428 * Can't allow enabling interrupts while in an interrupt handler,
3429 * that's general bad form and such. Recursion, limited stack etc..
3431 if (DEBUG_LOCKS_WARN_ON(current
->hardirq_context
))
3434 current
->lockdep_recursion
= 1;
3435 __trace_hardirqs_on_caller(ip
);
3436 current
->lockdep_recursion
= 0;
3438 NOKPROBE_SYMBOL(lockdep_hardirqs_on
);
3441 * Hardirqs were disabled:
3443 void lockdep_hardirqs_off(unsigned long ip
)
3445 struct task_struct
*curr
= current
;
3447 if (unlikely(!debug_locks
|| current
->lockdep_recursion
))
3451 * So we're supposed to get called after you mask local IRQs, but for
3452 * some reason the hardware doesn't quite think you did a proper job.
3454 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
3457 if (curr
->hardirqs_enabled
) {
3459 * We have done an ON -> OFF transition:
3461 curr
->hardirqs_enabled
= 0;
3462 curr
->hardirq_disable_ip
= ip
;
3463 curr
->hardirq_disable_event
= ++curr
->irq_events
;
3464 debug_atomic_inc(hardirqs_off_events
);
3466 debug_atomic_inc(redundant_hardirqs_off
);
3468 NOKPROBE_SYMBOL(lockdep_hardirqs_off
);
3471 * Softirqs will be enabled:
3473 void trace_softirqs_on(unsigned long ip
)
3475 struct task_struct
*curr
= current
;
3477 if (unlikely(!debug_locks
|| current
->lockdep_recursion
))
3481 * We fancy IRQs being disabled here, see softirq.c, avoids
3482 * funny state and nesting things.
3484 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
3487 if (curr
->softirqs_enabled
) {
3488 debug_atomic_inc(redundant_softirqs_on
);
3492 current
->lockdep_recursion
= 1;
3494 * We'll do an OFF -> ON transition:
3496 curr
->softirqs_enabled
= 1;
3497 curr
->softirq_enable_ip
= ip
;
3498 curr
->softirq_enable_event
= ++curr
->irq_events
;
3499 debug_atomic_inc(softirqs_on_events
);
3501 * We are going to turn softirqs on, so set the
3502 * usage bit for all held locks, if hardirqs are
3505 if (curr
->hardirqs_enabled
)
3506 mark_held_locks(curr
, LOCK_ENABLED_SOFTIRQ
);
3507 current
->lockdep_recursion
= 0;
3511 * Softirqs were disabled:
3513 void trace_softirqs_off(unsigned long ip
)
3515 struct task_struct
*curr
= current
;
3517 if (unlikely(!debug_locks
|| current
->lockdep_recursion
))
3521 * We fancy IRQs being disabled here, see softirq.c
3523 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
3526 if (curr
->softirqs_enabled
) {
3528 * We have done an ON -> OFF transition:
3530 curr
->softirqs_enabled
= 0;
3531 curr
->softirq_disable_ip
= ip
;
3532 curr
->softirq_disable_event
= ++curr
->irq_events
;
3533 debug_atomic_inc(softirqs_off_events
);
3535 * Whoops, we wanted softirqs off, so why aren't they?
3537 DEBUG_LOCKS_WARN_ON(!softirq_count());
3539 debug_atomic_inc(redundant_softirqs_off
);
3543 mark_usage(struct task_struct
*curr
, struct held_lock
*hlock
, int check
)
3549 * If non-trylock use in a hardirq or softirq context, then
3550 * mark the lock as used in these contexts:
3552 if (!hlock
->trylock
) {
3554 if (curr
->hardirq_context
)
3555 if (!mark_lock(curr
, hlock
,
3556 LOCK_USED_IN_HARDIRQ_READ
))
3558 if (curr
->softirq_context
)
3559 if (!mark_lock(curr
, hlock
,
3560 LOCK_USED_IN_SOFTIRQ_READ
))
3563 if (curr
->hardirq_context
)
3564 if (!mark_lock(curr
, hlock
, LOCK_USED_IN_HARDIRQ
))
3566 if (curr
->softirq_context
)
3567 if (!mark_lock(curr
, hlock
, LOCK_USED_IN_SOFTIRQ
))
3571 if (!hlock
->hardirqs_off
) {
3573 if (!mark_lock(curr
, hlock
,
3574 LOCK_ENABLED_HARDIRQ_READ
))
3576 if (curr
->softirqs_enabled
)
3577 if (!mark_lock(curr
, hlock
,
3578 LOCK_ENABLED_SOFTIRQ_READ
))
3581 if (!mark_lock(curr
, hlock
,
3582 LOCK_ENABLED_HARDIRQ
))
3584 if (curr
->softirqs_enabled
)
3585 if (!mark_lock(curr
, hlock
,
3586 LOCK_ENABLED_SOFTIRQ
))
3592 /* mark it as used: */
3593 if (!mark_lock(curr
, hlock
, LOCK_USED
))
3599 static inline unsigned int task_irq_context(struct task_struct
*task
)
3601 return LOCK_CHAIN_HARDIRQ_CONTEXT
* !!task
->hardirq_context
+
3602 LOCK_CHAIN_SOFTIRQ_CONTEXT
* !!task
->softirq_context
;
3605 static int separate_irq_context(struct task_struct
*curr
,
3606 struct held_lock
*hlock
)
3608 unsigned int depth
= curr
->lockdep_depth
;
3611 * Keep track of points where we cross into an interrupt context:
3614 struct held_lock
*prev_hlock
;
3616 prev_hlock
= curr
->held_locks
+ depth
-1;
3618 * If we cross into another context, reset the
3619 * hash key (this also prevents the checking and the
3620 * adding of the dependency to 'prev'):
3622 if (prev_hlock
->irq_context
!= hlock
->irq_context
)
3629 * Mark a lock with a usage bit, and validate the state transition:
3631 static int mark_lock(struct task_struct
*curr
, struct held_lock
*this,
3632 enum lock_usage_bit new_bit
)
3634 unsigned int new_mask
= 1 << new_bit
, ret
= 1;
3636 if (new_bit
>= LOCK_USAGE_STATES
) {
3637 DEBUG_LOCKS_WARN_ON(1);
3642 * If already set then do not dirty the cacheline,
3643 * nor do any checks:
3645 if (likely(hlock_class(this)->usage_mask
& new_mask
))
3651 * Make sure we didn't race:
3653 if (unlikely(hlock_class(this)->usage_mask
& new_mask
)) {
3658 hlock_class(this)->usage_mask
|= new_mask
;
3660 if (!(hlock_class(this)->usage_traces
[new_bit
] = save_trace()))
3665 debug_atomic_dec(nr_unused_locks
);
3668 ret
= mark_lock_irq(curr
, this, new_bit
);
3676 * We must printk outside of the graph_lock:
3679 printk("\nmarked lock as {%s}:\n", usage_str
[new_bit
]);
3681 print_irqtrace_events(curr
);
3688 #else /* CONFIG_PROVE_LOCKING */
3691 mark_usage(struct task_struct
*curr
, struct held_lock
*hlock
, int check
)
3696 static inline unsigned int task_irq_context(struct task_struct
*task
)
3701 static inline int separate_irq_context(struct task_struct
*curr
,
3702 struct held_lock
*hlock
)
3707 #endif /* CONFIG_PROVE_LOCKING */
3710 * Initialize a lock instance's lock-class mapping info:
3712 void lockdep_init_map(struct lockdep_map
*lock
, const char *name
,
3713 struct lock_class_key
*key
, int subclass
)
3717 for (i
= 0; i
< NR_LOCKDEP_CACHING_CLASSES
; i
++)
3718 lock
->class_cache
[i
] = NULL
;
3720 #ifdef CONFIG_LOCK_STAT
3721 lock
->cpu
= raw_smp_processor_id();
3725 * Can't be having no nameless bastards around this place!
3727 if (DEBUG_LOCKS_WARN_ON(!name
)) {
3728 lock
->name
= "NULL";
3735 * No key, no joy, we need to hash something.
3737 if (DEBUG_LOCKS_WARN_ON(!key
))
3740 * Sanity check, the lock-class key must either have been allocated
3741 * statically or must have been registered as a dynamic key.
3743 if (!static_obj(key
) && !is_dynamic_key(key
)) {
3745 printk(KERN_ERR
"BUG: key %px has not been registered!\n", key
);
3746 DEBUG_LOCKS_WARN_ON(1);
3751 if (unlikely(!debug_locks
))
3755 unsigned long flags
;
3757 if (DEBUG_LOCKS_WARN_ON(current
->lockdep_recursion
))
3760 raw_local_irq_save(flags
);
3761 current
->lockdep_recursion
= 1;
3762 register_lock_class(lock
, subclass
, 1);
3763 current
->lockdep_recursion
= 0;
3764 raw_local_irq_restore(flags
);
3767 EXPORT_SYMBOL_GPL(lockdep_init_map
);
3769 struct lock_class_key __lockdep_no_validate__
;
3770 EXPORT_SYMBOL_GPL(__lockdep_no_validate__
);
3773 print_lock_nested_lock_not_held(struct task_struct
*curr
,
3774 struct held_lock
*hlock
,
3777 if (!debug_locks_off())
3779 if (debug_locks_silent
)
3783 pr_warn("==================================\n");
3784 pr_warn("WARNING: Nested lock was not taken\n");
3785 print_kernel_ident();
3786 pr_warn("----------------------------------\n");
3788 pr_warn("%s/%d is trying to lock:\n", curr
->comm
, task_pid_nr(curr
));
3791 pr_warn("\nbut this task is not holding:\n");
3792 pr_warn("%s\n", hlock
->nest_lock
->name
);
3794 pr_warn("\nstack backtrace:\n");
3797 pr_warn("\nother info that might help us debug this:\n");
3798 lockdep_print_held_locks(curr
);
3800 pr_warn("\nstack backtrace:\n");
3804 static int __lock_is_held(const struct lockdep_map
*lock
, int read
);
3807 * This gets called for every mutex_lock*()/spin_lock*() operation.
3808 * We maintain the dependency maps and validate the locking attempt:
3810 * The callers must make sure that IRQs are disabled before calling it,
3811 * otherwise we could get an interrupt which would want to take locks,
3812 * which would end up in lockdep again.
3814 static int __lock_acquire(struct lockdep_map
*lock
, unsigned int subclass
,
3815 int trylock
, int read
, int check
, int hardirqs_off
,
3816 struct lockdep_map
*nest_lock
, unsigned long ip
,
3817 int references
, int pin_count
)
3819 struct task_struct
*curr
= current
;
3820 struct lock_class
*class = NULL
;
3821 struct held_lock
*hlock
;
3827 if (unlikely(!debug_locks
))
3830 if (!prove_locking
|| lock
->key
== &__lockdep_no_validate__
)
3833 if (subclass
< NR_LOCKDEP_CACHING_CLASSES
)
3834 class = lock
->class_cache
[subclass
];
3838 if (unlikely(!class)) {
3839 class = register_lock_class(lock
, subclass
, 0);
3844 debug_class_ops_inc(class);
3846 if (very_verbose(class)) {
3847 printk("\nacquire class [%px] %s", class->key
, class->name
);
3848 if (class->name_version
> 1)
3849 printk(KERN_CONT
"#%d", class->name_version
);
3850 printk(KERN_CONT
"\n");
3855 * Add the lock to the list of currently held locks.
3856 * (we dont increase the depth just yet, up until the
3857 * dependency checks are done)
3859 depth
= curr
->lockdep_depth
;
3861 * Ran out of static storage for our per-task lock stack again have we?
3863 if (DEBUG_LOCKS_WARN_ON(depth
>= MAX_LOCK_DEPTH
))
3866 class_idx
= class - lock_classes
;
3869 hlock
= curr
->held_locks
+ depth
- 1;
3870 if (hlock
->class_idx
== class_idx
&& nest_lock
) {
3874 if (!hlock
->references
)
3875 hlock
->references
++;
3877 hlock
->references
+= references
;
3880 if (DEBUG_LOCKS_WARN_ON(hlock
->references
< references
))
3887 hlock
= curr
->held_locks
+ depth
;
3889 * Plain impossible, we just registered it and checked it weren't no
3890 * NULL like.. I bet this mushroom I ate was good!
3892 if (DEBUG_LOCKS_WARN_ON(!class))
3894 hlock
->class_idx
= class_idx
;
3895 hlock
->acquire_ip
= ip
;
3896 hlock
->instance
= lock
;
3897 hlock
->nest_lock
= nest_lock
;
3898 hlock
->irq_context
= task_irq_context(curr
);
3899 hlock
->trylock
= trylock
;
3901 hlock
->check
= check
;
3902 hlock
->hardirqs_off
= !!hardirqs_off
;
3903 hlock
->references
= references
;
3904 #ifdef CONFIG_LOCK_STAT
3905 hlock
->waittime_stamp
= 0;
3906 hlock
->holdtime_stamp
= lockstat_clock();
3908 hlock
->pin_count
= pin_count
;
3910 /* Initialize the lock usage bit */
3911 if (!mark_usage(curr
, hlock
, check
))
3915 * Calculate the chain hash: it's the combined hash of all the
3916 * lock keys along the dependency chain. We save the hash value
3917 * at every step so that we can get the current hash easily
3918 * after unlock. The chain hash is then used to cache dependency
3921 * The 'key ID' is what is the most compact key value to drive
3922 * the hash, not class->key.
3925 * Whoops, we did it again.. class_idx is invalid.
3927 if (DEBUG_LOCKS_WARN_ON(!test_bit(class_idx
, lock_classes_in_use
)))
3930 chain_key
= curr
->curr_chain_key
;
3933 * How can we have a chain hash when we ain't got no keys?!
3935 if (DEBUG_LOCKS_WARN_ON(chain_key
!= INITIAL_CHAIN_KEY
))
3940 hlock
->prev_chain_key
= chain_key
;
3941 if (separate_irq_context(curr
, hlock
)) {
3942 chain_key
= INITIAL_CHAIN_KEY
;
3945 chain_key
= iterate_chain_key(chain_key
, class_idx
);
3947 if (nest_lock
&& !__lock_is_held(nest_lock
, -1)) {
3948 print_lock_nested_lock_not_held(curr
, hlock
, ip
);
3952 if (!debug_locks_silent
) {
3953 WARN_ON_ONCE(depth
&& !hlock_class(hlock
- 1)->key
);
3954 WARN_ON_ONCE(!hlock_class(hlock
)->key
);
3957 if (!validate_chain(curr
, hlock
, chain_head
, chain_key
))
3960 curr
->curr_chain_key
= chain_key
;
3961 curr
->lockdep_depth
++;
3962 check_chain_key(curr
);
3963 #ifdef CONFIG_DEBUG_LOCKDEP
3964 if (unlikely(!debug_locks
))
3967 if (unlikely(curr
->lockdep_depth
>= MAX_LOCK_DEPTH
)) {
3969 print_lockdep_off("BUG: MAX_LOCK_DEPTH too low!");
3970 printk(KERN_DEBUG
"depth: %i max: %lu!\n",
3971 curr
->lockdep_depth
, MAX_LOCK_DEPTH
);
3973 lockdep_print_held_locks(current
);
3974 debug_show_all_locks();
3980 if (unlikely(curr
->lockdep_depth
> max_lockdep_depth
))
3981 max_lockdep_depth
= curr
->lockdep_depth
;
3986 static void print_unlock_imbalance_bug(struct task_struct
*curr
,
3987 struct lockdep_map
*lock
,
3990 if (!debug_locks_off())
3992 if (debug_locks_silent
)
3996 pr_warn("=====================================\n");
3997 pr_warn("WARNING: bad unlock balance detected!\n");
3998 print_kernel_ident();
3999 pr_warn("-------------------------------------\n");
4000 pr_warn("%s/%d is trying to release lock (",
4001 curr
->comm
, task_pid_nr(curr
));
4002 print_lockdep_cache(lock
);
4005 pr_warn("but there are no more locks to release!\n");
4006 pr_warn("\nother info that might help us debug this:\n");
4007 lockdep_print_held_locks(curr
);
4009 pr_warn("\nstack backtrace:\n");
4013 static int match_held_lock(const struct held_lock
*hlock
,
4014 const struct lockdep_map
*lock
)
4016 if (hlock
->instance
== lock
)
4019 if (hlock
->references
) {
4020 const struct lock_class
*class = lock
->class_cache
[0];
4023 class = look_up_lock_class(lock
, 0);
4026 * If look_up_lock_class() failed to find a class, we're trying
4027 * to test if we hold a lock that has never yet been acquired.
4028 * Clearly if the lock hasn't been acquired _ever_, we're not
4029 * holding it either, so report failure.
4035 * References, but not a lock we're actually ref-counting?
4036 * State got messed up, follow the sites that change ->references
4037 * and try to make sense of it.
4039 if (DEBUG_LOCKS_WARN_ON(!hlock
->nest_lock
))
4042 if (hlock
->class_idx
== class - lock_classes
)
4049 /* @depth must not be zero */
4050 static struct held_lock
*find_held_lock(struct task_struct
*curr
,
4051 struct lockdep_map
*lock
,
4052 unsigned int depth
, int *idx
)
4054 struct held_lock
*ret
, *hlock
, *prev_hlock
;
4058 hlock
= curr
->held_locks
+ i
;
4060 if (match_held_lock(hlock
, lock
))
4064 for (i
--, prev_hlock
= hlock
--;
4066 i
--, prev_hlock
= hlock
--) {
4068 * We must not cross into another context:
4070 if (prev_hlock
->irq_context
!= hlock
->irq_context
) {
4074 if (match_held_lock(hlock
, lock
)) {
4085 static int reacquire_held_locks(struct task_struct
*curr
, unsigned int depth
,
4086 int idx
, unsigned int *merged
)
4088 struct held_lock
*hlock
;
4089 int first_idx
= idx
;
4091 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
4094 for (hlock
= curr
->held_locks
+ idx
; idx
< depth
; idx
++, hlock
++) {
4095 switch (__lock_acquire(hlock
->instance
,
4096 hlock_class(hlock
)->subclass
,
4098 hlock
->read
, hlock
->check
,
4099 hlock
->hardirqs_off
,
4100 hlock
->nest_lock
, hlock
->acquire_ip
,
4101 hlock
->references
, hlock
->pin_count
)) {
4107 *merged
+= (idx
== first_idx
);
4118 __lock_set_class(struct lockdep_map
*lock
, const char *name
,
4119 struct lock_class_key
*key
, unsigned int subclass
,
4122 struct task_struct
*curr
= current
;
4123 unsigned int depth
, merged
= 0;
4124 struct held_lock
*hlock
;
4125 struct lock_class
*class;
4128 if (unlikely(!debug_locks
))
4131 depth
= curr
->lockdep_depth
;
4133 * This function is about (re)setting the class of a held lock,
4134 * yet we're not actually holding any locks. Naughty user!
4136 if (DEBUG_LOCKS_WARN_ON(!depth
))
4139 hlock
= find_held_lock(curr
, lock
, depth
, &i
);
4141 print_unlock_imbalance_bug(curr
, lock
, ip
);
4145 lockdep_init_map(lock
, name
, key
, 0);
4146 class = register_lock_class(lock
, subclass
, 0);
4147 hlock
->class_idx
= class - lock_classes
;
4149 curr
->lockdep_depth
= i
;
4150 curr
->curr_chain_key
= hlock
->prev_chain_key
;
4152 if (reacquire_held_locks(curr
, depth
, i
, &merged
))
4156 * I took it apart and put it back together again, except now I have
4157 * these 'spare' parts.. where shall I put them.
4159 if (DEBUG_LOCKS_WARN_ON(curr
->lockdep_depth
!= depth
- merged
))
4164 static int __lock_downgrade(struct lockdep_map
*lock
, unsigned long ip
)
4166 struct task_struct
*curr
= current
;
4167 unsigned int depth
, merged
= 0;
4168 struct held_lock
*hlock
;
4171 if (unlikely(!debug_locks
))
4174 depth
= curr
->lockdep_depth
;
4176 * This function is about (re)setting the class of a held lock,
4177 * yet we're not actually holding any locks. Naughty user!
4179 if (DEBUG_LOCKS_WARN_ON(!depth
))
4182 hlock
= find_held_lock(curr
, lock
, depth
, &i
);
4184 print_unlock_imbalance_bug(curr
, lock
, ip
);
4188 curr
->lockdep_depth
= i
;
4189 curr
->curr_chain_key
= hlock
->prev_chain_key
;
4191 WARN(hlock
->read
, "downgrading a read lock");
4193 hlock
->acquire_ip
= ip
;
4195 if (reacquire_held_locks(curr
, depth
, i
, &merged
))
4198 /* Merging can't happen with unchanged classes.. */
4199 if (DEBUG_LOCKS_WARN_ON(merged
))
4203 * I took it apart and put it back together again, except now I have
4204 * these 'spare' parts.. where shall I put them.
4206 if (DEBUG_LOCKS_WARN_ON(curr
->lockdep_depth
!= depth
))
4213 * Remove the lock from the list of currently held locks - this gets
4214 * called on mutex_unlock()/spin_unlock*() (or on a failed
4215 * mutex_lock_interruptible()).
4218 __lock_release(struct lockdep_map
*lock
, unsigned long ip
)
4220 struct task_struct
*curr
= current
;
4221 unsigned int depth
, merged
= 1;
4222 struct held_lock
*hlock
;
4225 if (unlikely(!debug_locks
))
4228 depth
= curr
->lockdep_depth
;
4230 * So we're all set to release this lock.. wait what lock? We don't
4231 * own any locks, you've been drinking again?
4234 print_unlock_imbalance_bug(curr
, lock
, ip
);
4239 * Check whether the lock exists in the current stack
4242 hlock
= find_held_lock(curr
, lock
, depth
, &i
);
4244 print_unlock_imbalance_bug(curr
, lock
, ip
);
4248 if (hlock
->instance
== lock
)
4249 lock_release_holdtime(hlock
);
4251 WARN(hlock
->pin_count
, "releasing a pinned lock\n");
4253 if (hlock
->references
) {
4254 hlock
->references
--;
4255 if (hlock
->references
) {
4257 * We had, and after removing one, still have
4258 * references, the current lock stack is still
4259 * valid. We're done!
4266 * We have the right lock to unlock, 'hlock' points to it.
4267 * Now we remove it from the stack, and add back the other
4268 * entries (if any), recalculating the hash along the way:
4271 curr
->lockdep_depth
= i
;
4272 curr
->curr_chain_key
= hlock
->prev_chain_key
;
4275 * The most likely case is when the unlock is on the innermost
4276 * lock. In this case, we are done!
4281 if (reacquire_held_locks(curr
, depth
, i
+ 1, &merged
))
4285 * We had N bottles of beer on the wall, we drank one, but now
4286 * there's not N-1 bottles of beer left on the wall...
4287 * Pouring two of the bottles together is acceptable.
4289 DEBUG_LOCKS_WARN_ON(curr
->lockdep_depth
!= depth
- merged
);
4292 * Since reacquire_held_locks() would have called check_chain_key()
4293 * indirectly via __lock_acquire(), we don't need to do it again
4299 static nokprobe_inline
4300 int __lock_is_held(const struct lockdep_map
*lock
, int read
)
4302 struct task_struct
*curr
= current
;
4305 for (i
= 0; i
< curr
->lockdep_depth
; i
++) {
4306 struct held_lock
*hlock
= curr
->held_locks
+ i
;
4308 if (match_held_lock(hlock
, lock
)) {
4309 if (read
== -1 || hlock
->read
== read
)
4319 static struct pin_cookie
__lock_pin_lock(struct lockdep_map
*lock
)
4321 struct pin_cookie cookie
= NIL_COOKIE
;
4322 struct task_struct
*curr
= current
;
4325 if (unlikely(!debug_locks
))
4328 for (i
= 0; i
< curr
->lockdep_depth
; i
++) {
4329 struct held_lock
*hlock
= curr
->held_locks
+ i
;
4331 if (match_held_lock(hlock
, lock
)) {
4333 * Grab 16bits of randomness; this is sufficient to not
4334 * be guessable and still allows some pin nesting in
4335 * our u32 pin_count.
4337 cookie
.val
= 1 + (prandom_u32() >> 16);
4338 hlock
->pin_count
+= cookie
.val
;
4343 WARN(1, "pinning an unheld lock\n");
4347 static void __lock_repin_lock(struct lockdep_map
*lock
, struct pin_cookie cookie
)
4349 struct task_struct
*curr
= current
;
4352 if (unlikely(!debug_locks
))
4355 for (i
= 0; i
< curr
->lockdep_depth
; i
++) {
4356 struct held_lock
*hlock
= curr
->held_locks
+ i
;
4358 if (match_held_lock(hlock
, lock
)) {
4359 hlock
->pin_count
+= cookie
.val
;
4364 WARN(1, "pinning an unheld lock\n");
4367 static void __lock_unpin_lock(struct lockdep_map
*lock
, struct pin_cookie cookie
)
4369 struct task_struct
*curr
= current
;
4372 if (unlikely(!debug_locks
))
4375 for (i
= 0; i
< curr
->lockdep_depth
; i
++) {
4376 struct held_lock
*hlock
= curr
->held_locks
+ i
;
4378 if (match_held_lock(hlock
, lock
)) {
4379 if (WARN(!hlock
->pin_count
, "unpinning an unpinned lock\n"))
4382 hlock
->pin_count
-= cookie
.val
;
4384 if (WARN((int)hlock
->pin_count
< 0, "pin count corrupted\n"))
4385 hlock
->pin_count
= 0;
4391 WARN(1, "unpinning an unheld lock\n");
4395 * Check whether we follow the irq-flags state precisely:
4397 static void check_flags(unsigned long flags
)
4399 #if defined(CONFIG_PROVE_LOCKING) && defined(CONFIG_DEBUG_LOCKDEP)
4403 if (irqs_disabled_flags(flags
)) {
4404 if (DEBUG_LOCKS_WARN_ON(current
->hardirqs_enabled
)) {
4405 printk("possible reason: unannotated irqs-off.\n");
4408 if (DEBUG_LOCKS_WARN_ON(!current
->hardirqs_enabled
)) {
4409 printk("possible reason: unannotated irqs-on.\n");
4414 * We dont accurately track softirq state in e.g.
4415 * hardirq contexts (such as on 4KSTACKS), so only
4416 * check if not in hardirq contexts:
4418 if (!hardirq_count()) {
4419 if (softirq_count()) {
4420 /* like the above, but with softirqs */
4421 DEBUG_LOCKS_WARN_ON(current
->softirqs_enabled
);
4423 /* lick the above, does it taste good? */
4424 DEBUG_LOCKS_WARN_ON(!current
->softirqs_enabled
);
4429 print_irqtrace_events(current
);
4433 void lock_set_class(struct lockdep_map
*lock
, const char *name
,
4434 struct lock_class_key
*key
, unsigned int subclass
,
4437 unsigned long flags
;
4439 if (unlikely(current
->lockdep_recursion
))
4442 raw_local_irq_save(flags
);
4443 current
->lockdep_recursion
= 1;
4445 if (__lock_set_class(lock
, name
, key
, subclass
, ip
))
4446 check_chain_key(current
);
4447 current
->lockdep_recursion
= 0;
4448 raw_local_irq_restore(flags
);
4450 EXPORT_SYMBOL_GPL(lock_set_class
);
4452 void lock_downgrade(struct lockdep_map
*lock
, unsigned long ip
)
4454 unsigned long flags
;
4456 if (unlikely(current
->lockdep_recursion
))
4459 raw_local_irq_save(flags
);
4460 current
->lockdep_recursion
= 1;
4462 if (__lock_downgrade(lock
, ip
))
4463 check_chain_key(current
);
4464 current
->lockdep_recursion
= 0;
4465 raw_local_irq_restore(flags
);
4467 EXPORT_SYMBOL_GPL(lock_downgrade
);
4470 * We are not always called with irqs disabled - do that here,
4471 * and also avoid lockdep recursion:
4473 void lock_acquire(struct lockdep_map
*lock
, unsigned int subclass
,
4474 int trylock
, int read
, int check
,
4475 struct lockdep_map
*nest_lock
, unsigned long ip
)
4477 unsigned long flags
;
4479 if (unlikely(current
->lockdep_recursion
))
4482 raw_local_irq_save(flags
);
4485 current
->lockdep_recursion
= 1;
4486 trace_lock_acquire(lock
, subclass
, trylock
, read
, check
, nest_lock
, ip
);
4487 __lock_acquire(lock
, subclass
, trylock
, read
, check
,
4488 irqs_disabled_flags(flags
), nest_lock
, ip
, 0, 0);
4489 current
->lockdep_recursion
= 0;
4490 raw_local_irq_restore(flags
);
4492 EXPORT_SYMBOL_GPL(lock_acquire
);
4494 void lock_release(struct lockdep_map
*lock
, unsigned long ip
)
4496 unsigned long flags
;
4498 if (unlikely(current
->lockdep_recursion
))
4501 raw_local_irq_save(flags
);
4503 current
->lockdep_recursion
= 1;
4504 trace_lock_release(lock
, ip
);
4505 if (__lock_release(lock
, ip
))
4506 check_chain_key(current
);
4507 current
->lockdep_recursion
= 0;
4508 raw_local_irq_restore(flags
);
4510 EXPORT_SYMBOL_GPL(lock_release
);
4512 int lock_is_held_type(const struct lockdep_map
*lock
, int read
)
4514 unsigned long flags
;
4517 if (unlikely(current
->lockdep_recursion
))
4518 return 1; /* avoid false negative lockdep_assert_held() */
4520 raw_local_irq_save(flags
);
4523 current
->lockdep_recursion
= 1;
4524 ret
= __lock_is_held(lock
, read
);
4525 current
->lockdep_recursion
= 0;
4526 raw_local_irq_restore(flags
);
4530 EXPORT_SYMBOL_GPL(lock_is_held_type
);
4531 NOKPROBE_SYMBOL(lock_is_held_type
);
4533 struct pin_cookie
lock_pin_lock(struct lockdep_map
*lock
)
4535 struct pin_cookie cookie
= NIL_COOKIE
;
4536 unsigned long flags
;
4538 if (unlikely(current
->lockdep_recursion
))
4541 raw_local_irq_save(flags
);
4544 current
->lockdep_recursion
= 1;
4545 cookie
= __lock_pin_lock(lock
);
4546 current
->lockdep_recursion
= 0;
4547 raw_local_irq_restore(flags
);
4551 EXPORT_SYMBOL_GPL(lock_pin_lock
);
4553 void lock_repin_lock(struct lockdep_map
*lock
, struct pin_cookie cookie
)
4555 unsigned long flags
;
4557 if (unlikely(current
->lockdep_recursion
))
4560 raw_local_irq_save(flags
);
4563 current
->lockdep_recursion
= 1;
4564 __lock_repin_lock(lock
, cookie
);
4565 current
->lockdep_recursion
= 0;
4566 raw_local_irq_restore(flags
);
4568 EXPORT_SYMBOL_GPL(lock_repin_lock
);
4570 void lock_unpin_lock(struct lockdep_map
*lock
, struct pin_cookie cookie
)
4572 unsigned long flags
;
4574 if (unlikely(current
->lockdep_recursion
))
4577 raw_local_irq_save(flags
);
4580 current
->lockdep_recursion
= 1;
4581 __lock_unpin_lock(lock
, cookie
);
4582 current
->lockdep_recursion
= 0;
4583 raw_local_irq_restore(flags
);
4585 EXPORT_SYMBOL_GPL(lock_unpin_lock
);
4587 #ifdef CONFIG_LOCK_STAT
4588 static void print_lock_contention_bug(struct task_struct
*curr
,
4589 struct lockdep_map
*lock
,
4592 if (!debug_locks_off())
4594 if (debug_locks_silent
)
4598 pr_warn("=================================\n");
4599 pr_warn("WARNING: bad contention detected!\n");
4600 print_kernel_ident();
4601 pr_warn("---------------------------------\n");
4602 pr_warn("%s/%d is trying to contend lock (",
4603 curr
->comm
, task_pid_nr(curr
));
4604 print_lockdep_cache(lock
);
4607 pr_warn("but there are no locks held!\n");
4608 pr_warn("\nother info that might help us debug this:\n");
4609 lockdep_print_held_locks(curr
);
4611 pr_warn("\nstack backtrace:\n");
4616 __lock_contended(struct lockdep_map
*lock
, unsigned long ip
)
4618 struct task_struct
*curr
= current
;
4619 struct held_lock
*hlock
;
4620 struct lock_class_stats
*stats
;
4622 int i
, contention_point
, contending_point
;
4624 depth
= curr
->lockdep_depth
;
4626 * Whee, we contended on this lock, except it seems we're not
4627 * actually trying to acquire anything much at all..
4629 if (DEBUG_LOCKS_WARN_ON(!depth
))
4632 hlock
= find_held_lock(curr
, lock
, depth
, &i
);
4634 print_lock_contention_bug(curr
, lock
, ip
);
4638 if (hlock
->instance
!= lock
)
4641 hlock
->waittime_stamp
= lockstat_clock();
4643 contention_point
= lock_point(hlock_class(hlock
)->contention_point
, ip
);
4644 contending_point
= lock_point(hlock_class(hlock
)->contending_point
,
4647 stats
= get_lock_stats(hlock_class(hlock
));
4648 if (contention_point
< LOCKSTAT_POINTS
)
4649 stats
->contention_point
[contention_point
]++;
4650 if (contending_point
< LOCKSTAT_POINTS
)
4651 stats
->contending_point
[contending_point
]++;
4652 if (lock
->cpu
!= smp_processor_id())
4653 stats
->bounces
[bounce_contended
+ !!hlock
->read
]++;
4657 __lock_acquired(struct lockdep_map
*lock
, unsigned long ip
)
4659 struct task_struct
*curr
= current
;
4660 struct held_lock
*hlock
;
4661 struct lock_class_stats
*stats
;
4663 u64 now
, waittime
= 0;
4666 depth
= curr
->lockdep_depth
;
4668 * Yay, we acquired ownership of this lock we didn't try to
4669 * acquire, how the heck did that happen?
4671 if (DEBUG_LOCKS_WARN_ON(!depth
))
4674 hlock
= find_held_lock(curr
, lock
, depth
, &i
);
4676 print_lock_contention_bug(curr
, lock
, _RET_IP_
);
4680 if (hlock
->instance
!= lock
)
4683 cpu
= smp_processor_id();
4684 if (hlock
->waittime_stamp
) {
4685 now
= lockstat_clock();
4686 waittime
= now
- hlock
->waittime_stamp
;
4687 hlock
->holdtime_stamp
= now
;
4690 trace_lock_acquired(lock
, ip
);
4692 stats
= get_lock_stats(hlock_class(hlock
));
4695 lock_time_inc(&stats
->read_waittime
, waittime
);
4697 lock_time_inc(&stats
->write_waittime
, waittime
);
4699 if (lock
->cpu
!= cpu
)
4700 stats
->bounces
[bounce_acquired
+ !!hlock
->read
]++;
4706 void lock_contended(struct lockdep_map
*lock
, unsigned long ip
)
4708 unsigned long flags
;
4710 if (unlikely(!lock_stat
|| !debug_locks
))
4713 if (unlikely(current
->lockdep_recursion
))
4716 raw_local_irq_save(flags
);
4718 current
->lockdep_recursion
= 1;
4719 trace_lock_contended(lock
, ip
);
4720 __lock_contended(lock
, ip
);
4721 current
->lockdep_recursion
= 0;
4722 raw_local_irq_restore(flags
);
4724 EXPORT_SYMBOL_GPL(lock_contended
);
4726 void lock_acquired(struct lockdep_map
*lock
, unsigned long ip
)
4728 unsigned long flags
;
4730 if (unlikely(!lock_stat
|| !debug_locks
))
4733 if (unlikely(current
->lockdep_recursion
))
4736 raw_local_irq_save(flags
);
4738 current
->lockdep_recursion
= 1;
4739 __lock_acquired(lock
, ip
);
4740 current
->lockdep_recursion
= 0;
4741 raw_local_irq_restore(flags
);
4743 EXPORT_SYMBOL_GPL(lock_acquired
);
4747 * Used by the testsuite, sanitize the validator state
4748 * after a simulated failure:
4751 void lockdep_reset(void)
4753 unsigned long flags
;
4756 raw_local_irq_save(flags
);
4757 lockdep_init_task(current
);
4758 memset(current
->held_locks
, 0, MAX_LOCK_DEPTH
*sizeof(struct held_lock
));
4759 nr_hardirq_chains
= 0;
4760 nr_softirq_chains
= 0;
4761 nr_process_chains
= 0;
4763 for (i
= 0; i
< CHAINHASH_SIZE
; i
++)
4764 INIT_HLIST_HEAD(chainhash_table
+ i
);
4765 raw_local_irq_restore(flags
);
4768 /* Remove a class from a lock chain. Must be called with the graph lock held. */
4769 static void remove_class_from_lock_chain(struct pending_free
*pf
,
4770 struct lock_chain
*chain
,
4771 struct lock_class
*class)
4773 #ifdef CONFIG_PROVE_LOCKING
4774 struct lock_chain
*new_chain
;
4778 for (i
= chain
->base
; i
< chain
->base
+ chain
->depth
; i
++) {
4779 if (chain_hlocks
[i
] != class - lock_classes
)
4781 /* The code below leaks one chain_hlock[] entry. */
4782 if (--chain
->depth
> 0) {
4783 memmove(&chain_hlocks
[i
], &chain_hlocks
[i
+ 1],
4784 (chain
->base
+ chain
->depth
- i
) *
4785 sizeof(chain_hlocks
[0]));
4788 * Each lock class occurs at most once in a lock chain so once
4789 * we found a match we can break out of this loop.
4793 /* Since the chain has not been modified, return. */
4797 chain_key
= INITIAL_CHAIN_KEY
;
4798 for (i
= chain
->base
; i
< chain
->base
+ chain
->depth
; i
++)
4799 chain_key
= iterate_chain_key(chain_key
, chain_hlocks
[i
]);
4800 if (chain
->depth
&& chain
->chain_key
== chain_key
)
4802 /* Overwrite the chain key for concurrent RCU readers. */
4803 WRITE_ONCE(chain
->chain_key
, chain_key
);
4804 dec_chains(chain
->irq_context
);
4807 * Note: calling hlist_del_rcu() from inside a
4808 * hlist_for_each_entry_rcu() loop is safe.
4810 hlist_del_rcu(&chain
->entry
);
4811 __set_bit(chain
- lock_chains
, pf
->lock_chains_being_freed
);
4812 if (chain
->depth
== 0)
4815 * If the modified lock chain matches an existing lock chain, drop
4816 * the modified lock chain.
4818 if (lookup_chain_cache(chain_key
))
4820 new_chain
= alloc_lock_chain();
4821 if (WARN_ON_ONCE(!new_chain
)) {
4825 *new_chain
= *chain
;
4826 hlist_add_head_rcu(&new_chain
->entry
, chainhashentry(chain_key
));
4827 inc_chains(new_chain
->irq_context
);
4831 /* Must be called with the graph lock held. */
4832 static void remove_class_from_lock_chains(struct pending_free
*pf
,
4833 struct lock_class
*class)
4835 struct lock_chain
*chain
;
4836 struct hlist_head
*head
;
4839 for (i
= 0; i
< ARRAY_SIZE(chainhash_table
); i
++) {
4840 head
= chainhash_table
+ i
;
4841 hlist_for_each_entry_rcu(chain
, head
, entry
) {
4842 remove_class_from_lock_chain(pf
, chain
, class);
4848 * Remove all references to a lock class. The caller must hold the graph lock.
4850 static void zap_class(struct pending_free
*pf
, struct lock_class
*class)
4852 struct lock_list
*entry
;
4855 WARN_ON_ONCE(!class->key
);
4858 * Remove all dependencies this lock is
4861 for_each_set_bit(i
, list_entries_in_use
, ARRAY_SIZE(list_entries
)) {
4862 entry
= list_entries
+ i
;
4863 if (entry
->class != class && entry
->links_to
!= class)
4865 __clear_bit(i
, list_entries_in_use
);
4867 list_del_rcu(&entry
->entry
);
4869 if (list_empty(&class->locks_after
) &&
4870 list_empty(&class->locks_before
)) {
4871 list_move_tail(&class->lock_entry
, &pf
->zapped
);
4872 hlist_del_rcu(&class->hash_entry
);
4873 WRITE_ONCE(class->key
, NULL
);
4874 WRITE_ONCE(class->name
, NULL
);
4876 __clear_bit(class - lock_classes
, lock_classes_in_use
);
4878 WARN_ONCE(true, "%s() failed for class %s\n", __func__
,
4882 remove_class_from_lock_chains(pf
, class);
4885 static void reinit_class(struct lock_class
*class)
4887 void *const p
= class;
4888 const unsigned int offset
= offsetof(struct lock_class
, key
);
4890 WARN_ON_ONCE(!class->lock_entry
.next
);
4891 WARN_ON_ONCE(!list_empty(&class->locks_after
));
4892 WARN_ON_ONCE(!list_empty(&class->locks_before
));
4893 memset(p
+ offset
, 0, sizeof(*class) - offset
);
4894 WARN_ON_ONCE(!class->lock_entry
.next
);
4895 WARN_ON_ONCE(!list_empty(&class->locks_after
));
4896 WARN_ON_ONCE(!list_empty(&class->locks_before
));
4899 static inline int within(const void *addr
, void *start
, unsigned long size
)
4901 return addr
>= start
&& addr
< start
+ size
;
4904 static bool inside_selftest(void)
4906 return current
== lockdep_selftest_task_struct
;
4909 /* The caller must hold the graph lock. */
4910 static struct pending_free
*get_pending_free(void)
4912 return delayed_free
.pf
+ delayed_free
.index
;
4915 static void free_zapped_rcu(struct rcu_head
*cb
);
4918 * Schedule an RCU callback if no RCU callback is pending. Must be called with
4919 * the graph lock held.
4921 static void call_rcu_zapped(struct pending_free
*pf
)
4923 WARN_ON_ONCE(inside_selftest());
4925 if (list_empty(&pf
->zapped
))
4928 if (delayed_free
.scheduled
)
4931 delayed_free
.scheduled
= true;
4933 WARN_ON_ONCE(delayed_free
.pf
+ delayed_free
.index
!= pf
);
4934 delayed_free
.index
^= 1;
4936 call_rcu(&delayed_free
.rcu_head
, free_zapped_rcu
);
4939 /* The caller must hold the graph lock. May be called from RCU context. */
4940 static void __free_zapped_classes(struct pending_free
*pf
)
4942 struct lock_class
*class;
4944 check_data_structures();
4946 list_for_each_entry(class, &pf
->zapped
, lock_entry
)
4947 reinit_class(class);
4949 list_splice_init(&pf
->zapped
, &free_lock_classes
);
4951 #ifdef CONFIG_PROVE_LOCKING
4952 bitmap_andnot(lock_chains_in_use
, lock_chains_in_use
,
4953 pf
->lock_chains_being_freed
, ARRAY_SIZE(lock_chains
));
4954 bitmap_clear(pf
->lock_chains_being_freed
, 0, ARRAY_SIZE(lock_chains
));
4958 static void free_zapped_rcu(struct rcu_head
*ch
)
4960 struct pending_free
*pf
;
4961 unsigned long flags
;
4963 if (WARN_ON_ONCE(ch
!= &delayed_free
.rcu_head
))
4966 raw_local_irq_save(flags
);
4967 arch_spin_lock(&lockdep_lock
);
4968 current
->lockdep_recursion
= 1;
4971 pf
= delayed_free
.pf
+ (delayed_free
.index
^ 1);
4972 __free_zapped_classes(pf
);
4973 delayed_free
.scheduled
= false;
4976 * If there's anything on the open list, close and start a new callback.
4978 call_rcu_zapped(delayed_free
.pf
+ delayed_free
.index
);
4980 current
->lockdep_recursion
= 0;
4981 arch_spin_unlock(&lockdep_lock
);
4982 raw_local_irq_restore(flags
);
4986 * Remove all lock classes from the class hash table and from the
4987 * all_lock_classes list whose key or name is in the address range [start,
4988 * start + size). Move these lock classes to the zapped_classes list. Must
4989 * be called with the graph lock held.
4991 static void __lockdep_free_key_range(struct pending_free
*pf
, void *start
,
4994 struct lock_class
*class;
4995 struct hlist_head
*head
;
4998 /* Unhash all classes that were created by a module. */
4999 for (i
= 0; i
< CLASSHASH_SIZE
; i
++) {
5000 head
= classhash_table
+ i
;
5001 hlist_for_each_entry_rcu(class, head
, hash_entry
) {
5002 if (!within(class->key
, start
, size
) &&
5003 !within(class->name
, start
, size
))
5005 zap_class(pf
, class);
5011 * Used in module.c to remove lock classes from memory that is going to be
5012 * freed; and possibly re-used by other modules.
5014 * We will have had one synchronize_rcu() before getting here, so we're
5015 * guaranteed nobody will look up these exact classes -- they're properly dead
5016 * but still allocated.
5018 static void lockdep_free_key_range_reg(void *start
, unsigned long size
)
5020 struct pending_free
*pf
;
5021 unsigned long flags
;
5023 init_data_structures_once();
5025 raw_local_irq_save(flags
);
5026 arch_spin_lock(&lockdep_lock
);
5027 current
->lockdep_recursion
= 1;
5028 pf
= get_pending_free();
5029 __lockdep_free_key_range(pf
, start
, size
);
5030 call_rcu_zapped(pf
);
5031 current
->lockdep_recursion
= 0;
5032 arch_spin_unlock(&lockdep_lock
);
5033 raw_local_irq_restore(flags
);
5036 * Wait for any possible iterators from look_up_lock_class() to pass
5037 * before continuing to free the memory they refer to.
5043 * Free all lockdep keys in the range [start, start+size). Does not sleep.
5044 * Ignores debug_locks. Must only be used by the lockdep selftests.
5046 static void lockdep_free_key_range_imm(void *start
, unsigned long size
)
5048 struct pending_free
*pf
= delayed_free
.pf
;
5049 unsigned long flags
;
5051 init_data_structures_once();
5053 raw_local_irq_save(flags
);
5054 arch_spin_lock(&lockdep_lock
);
5055 __lockdep_free_key_range(pf
, start
, size
);
5056 __free_zapped_classes(pf
);
5057 arch_spin_unlock(&lockdep_lock
);
5058 raw_local_irq_restore(flags
);
5061 void lockdep_free_key_range(void *start
, unsigned long size
)
5063 init_data_structures_once();
5065 if (inside_selftest())
5066 lockdep_free_key_range_imm(start
, size
);
5068 lockdep_free_key_range_reg(start
, size
);
5072 * Check whether any element of the @lock->class_cache[] array refers to a
5073 * registered lock class. The caller must hold either the graph lock or the
5076 static bool lock_class_cache_is_registered(struct lockdep_map
*lock
)
5078 struct lock_class
*class;
5079 struct hlist_head
*head
;
5082 for (i
= 0; i
< CLASSHASH_SIZE
; i
++) {
5083 head
= classhash_table
+ i
;
5084 hlist_for_each_entry_rcu(class, head
, hash_entry
) {
5085 for (j
= 0; j
< NR_LOCKDEP_CACHING_CLASSES
; j
++)
5086 if (lock
->class_cache
[j
] == class)
5093 /* The caller must hold the graph lock. Does not sleep. */
5094 static void __lockdep_reset_lock(struct pending_free
*pf
,
5095 struct lockdep_map
*lock
)
5097 struct lock_class
*class;
5101 * Remove all classes this lock might have:
5103 for (j
= 0; j
< MAX_LOCKDEP_SUBCLASSES
; j
++) {
5105 * If the class exists we look it up and zap it:
5107 class = look_up_lock_class(lock
, j
);
5109 zap_class(pf
, class);
5112 * Debug check: in the end all mapped classes should
5115 if (WARN_ON_ONCE(lock_class_cache_is_registered(lock
)))
5120 * Remove all information lockdep has about a lock if debug_locks == 1. Free
5121 * released data structures from RCU context.
5123 static void lockdep_reset_lock_reg(struct lockdep_map
*lock
)
5125 struct pending_free
*pf
;
5126 unsigned long flags
;
5129 raw_local_irq_save(flags
);
5130 locked
= graph_lock();
5134 pf
= get_pending_free();
5135 __lockdep_reset_lock(pf
, lock
);
5136 call_rcu_zapped(pf
);
5140 raw_local_irq_restore(flags
);
5144 * Reset a lock. Does not sleep. Ignores debug_locks. Must only be used by the
5145 * lockdep selftests.
5147 static void lockdep_reset_lock_imm(struct lockdep_map
*lock
)
5149 struct pending_free
*pf
= delayed_free
.pf
;
5150 unsigned long flags
;
5152 raw_local_irq_save(flags
);
5153 arch_spin_lock(&lockdep_lock
);
5154 __lockdep_reset_lock(pf
, lock
);
5155 __free_zapped_classes(pf
);
5156 arch_spin_unlock(&lockdep_lock
);
5157 raw_local_irq_restore(flags
);
5160 void lockdep_reset_lock(struct lockdep_map
*lock
)
5162 init_data_structures_once();
5164 if (inside_selftest())
5165 lockdep_reset_lock_imm(lock
);
5167 lockdep_reset_lock_reg(lock
);
5170 /* Unregister a dynamically allocated key. */
5171 void lockdep_unregister_key(struct lock_class_key
*key
)
5173 struct hlist_head
*hash_head
= keyhashentry(key
);
5174 struct lock_class_key
*k
;
5175 struct pending_free
*pf
;
5176 unsigned long flags
;
5181 if (WARN_ON_ONCE(static_obj(key
)))
5184 raw_local_irq_save(flags
);
5188 pf
= get_pending_free();
5189 hlist_for_each_entry_rcu(k
, hash_head
, hash_entry
) {
5191 hlist_del_rcu(&k
->hash_entry
);
5196 WARN_ON_ONCE(!found
);
5197 __lockdep_free_key_range(pf
, key
, 1);
5198 call_rcu_zapped(pf
);
5201 raw_local_irq_restore(flags
);
5203 /* Wait until is_dynamic_key() has finished accessing k->hash_entry. */
5206 EXPORT_SYMBOL_GPL(lockdep_unregister_key
);
5208 void __init
lockdep_init(void)
5210 printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");
5212 printk("... MAX_LOCKDEP_SUBCLASSES: %lu\n", MAX_LOCKDEP_SUBCLASSES
);
5213 printk("... MAX_LOCK_DEPTH: %lu\n", MAX_LOCK_DEPTH
);
5214 printk("... MAX_LOCKDEP_KEYS: %lu\n", MAX_LOCKDEP_KEYS
);
5215 printk("... CLASSHASH_SIZE: %lu\n", CLASSHASH_SIZE
);
5216 printk("... MAX_LOCKDEP_ENTRIES: %lu\n", MAX_LOCKDEP_ENTRIES
);
5217 printk("... MAX_LOCKDEP_CHAINS: %lu\n", MAX_LOCKDEP_CHAINS
);
5218 printk("... CHAINHASH_SIZE: %lu\n", CHAINHASH_SIZE
);
5220 printk(" memory used by lock dependency info: %zu kB\n",
5221 (sizeof(lock_classes
) +
5222 sizeof(lock_classes_in_use
) +
5223 sizeof(classhash_table
) +
5224 sizeof(list_entries
) +
5225 sizeof(list_entries_in_use
) +
5226 sizeof(chainhash_table
) +
5227 sizeof(delayed_free
)
5228 #ifdef CONFIG_PROVE_LOCKING
5230 + sizeof(lock_chains
)
5231 + sizeof(lock_chains_in_use
)
5232 + sizeof(chain_hlocks
)
5237 #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
5238 printk(" memory used for stack traces: %zu kB\n",
5239 (sizeof(stack_trace
) + sizeof(stack_trace_hash
)) / 1024
5243 printk(" per task-struct memory footprint: %zu bytes\n",
5244 sizeof(((struct task_struct
*)NULL
)->held_locks
));
5248 print_freed_lock_bug(struct task_struct
*curr
, const void *mem_from
,
5249 const void *mem_to
, struct held_lock
*hlock
)
5251 if (!debug_locks_off())
5253 if (debug_locks_silent
)
5257 pr_warn("=========================\n");
5258 pr_warn("WARNING: held lock freed!\n");
5259 print_kernel_ident();
5260 pr_warn("-------------------------\n");
5261 pr_warn("%s/%d is freeing memory %px-%px, with a lock still held there!\n",
5262 curr
->comm
, task_pid_nr(curr
), mem_from
, mem_to
-1);
5264 lockdep_print_held_locks(curr
);
5266 pr_warn("\nstack backtrace:\n");
5270 static inline int not_in_range(const void* mem_from
, unsigned long mem_len
,
5271 const void* lock_from
, unsigned long lock_len
)
5273 return lock_from
+ lock_len
<= mem_from
||
5274 mem_from
+ mem_len
<= lock_from
;
5278 * Called when kernel memory is freed (or unmapped), or if a lock
5279 * is destroyed or reinitialized - this code checks whether there is
5280 * any held lock in the memory range of <from> to <to>:
5282 void debug_check_no_locks_freed(const void *mem_from
, unsigned long mem_len
)
5284 struct task_struct
*curr
= current
;
5285 struct held_lock
*hlock
;
5286 unsigned long flags
;
5289 if (unlikely(!debug_locks
))
5292 raw_local_irq_save(flags
);
5293 for (i
= 0; i
< curr
->lockdep_depth
; i
++) {
5294 hlock
= curr
->held_locks
+ i
;
5296 if (not_in_range(mem_from
, mem_len
, hlock
->instance
,
5297 sizeof(*hlock
->instance
)))
5300 print_freed_lock_bug(curr
, mem_from
, mem_from
+ mem_len
, hlock
);
5303 raw_local_irq_restore(flags
);
5305 EXPORT_SYMBOL_GPL(debug_check_no_locks_freed
);
5307 static void print_held_locks_bug(void)
5309 if (!debug_locks_off())
5311 if (debug_locks_silent
)
5315 pr_warn("====================================\n");
5316 pr_warn("WARNING: %s/%d still has locks held!\n",
5317 current
->comm
, task_pid_nr(current
));
5318 print_kernel_ident();
5319 pr_warn("------------------------------------\n");
5320 lockdep_print_held_locks(current
);
5321 pr_warn("\nstack backtrace:\n");
5325 void debug_check_no_locks_held(void)
5327 if (unlikely(current
->lockdep_depth
> 0))
5328 print_held_locks_bug();
5330 EXPORT_SYMBOL_GPL(debug_check_no_locks_held
);
5333 void debug_show_all_locks(void)
5335 struct task_struct
*g
, *p
;
5337 if (unlikely(!debug_locks
)) {
5338 pr_warn("INFO: lockdep is turned off.\n");
5341 pr_warn("\nShowing all locks held in the system:\n");
5344 for_each_process_thread(g
, p
) {
5345 if (!p
->lockdep_depth
)
5347 lockdep_print_held_locks(p
);
5348 touch_nmi_watchdog();
5349 touch_all_softlockup_watchdogs();
5354 pr_warn("=============================================\n\n");
5356 EXPORT_SYMBOL_GPL(debug_show_all_locks
);
5360 * Careful: only use this function if you are sure that
5361 * the task cannot run in parallel!
5363 void debug_show_held_locks(struct task_struct
*task
)
5365 if (unlikely(!debug_locks
)) {
5366 printk("INFO: lockdep is turned off.\n");
5369 lockdep_print_held_locks(task
);
5371 EXPORT_SYMBOL_GPL(debug_show_held_locks
);
5373 asmlinkage __visible
void lockdep_sys_exit(void)
5375 struct task_struct
*curr
= current
;
5377 if (unlikely(curr
->lockdep_depth
)) {
5378 if (!debug_locks_off())
5381 pr_warn("================================================\n");
5382 pr_warn("WARNING: lock held when returning to user space!\n");
5383 print_kernel_ident();
5384 pr_warn("------------------------------------------------\n");
5385 pr_warn("%s/%d is leaving the kernel with locks still held!\n",
5386 curr
->comm
, curr
->pid
);
5387 lockdep_print_held_locks(curr
);
5391 * The lock history for each syscall should be independent. So wipe the
5392 * slate clean on return to userspace.
5394 lockdep_invariant_state(false);
5397 void lockdep_rcu_suspicious(const char *file
, const int line
, const char *s
)
5399 struct task_struct
*curr
= current
;
5401 /* Note: the following can be executed concurrently, so be careful. */
5403 pr_warn("=============================\n");
5404 pr_warn("WARNING: suspicious RCU usage\n");
5405 print_kernel_ident();
5406 pr_warn("-----------------------------\n");
5407 pr_warn("%s:%d %s!\n", file
, line
, s
);
5408 pr_warn("\nother info that might help us debug this:\n\n");
5409 pr_warn("\n%srcu_scheduler_active = %d, debug_locks = %d\n",
5410 !rcu_lockdep_current_cpu_online()
5411 ? "RCU used illegally from offline CPU!\n"
5412 : !rcu_is_watching()
5413 ? "RCU used illegally from idle CPU!\n"
5415 rcu_scheduler_active
, debug_locks
);
5418 * If a CPU is in the RCU-free window in idle (ie: in the section
5419 * between rcu_idle_enter() and rcu_idle_exit(), then RCU
5420 * considers that CPU to be in an "extended quiescent state",
5421 * which means that RCU will be completely ignoring that CPU.
5422 * Therefore, rcu_read_lock() and friends have absolutely no
5423 * effect on a CPU running in that state. In other words, even if
5424 * such an RCU-idle CPU has called rcu_read_lock(), RCU might well
5425 * delete data structures out from under it. RCU really has no
5426 * choice here: we need to keep an RCU-free window in idle where
5427 * the CPU may possibly enter into low power mode. This way we can
5428 * notice an extended quiescent state to other CPUs that started a grace
5429 * period. Otherwise we would delay any grace period as long as we run
5432 * So complain bitterly if someone does call rcu_read_lock(),
5433 * rcu_read_lock_bh() and so on from extended quiescent states.
5435 if (!rcu_is_watching())
5436 pr_warn("RCU used illegally from extended quiescent state!\n");
5438 lockdep_print_held_locks(curr
);
5439 pr_warn("\nstack backtrace:\n");
5442 EXPORT_SYMBOL_GPL(lockdep_rcu_suspicious
);