개념 설명 전체 · v6.6 / kernel/locking/lockdep.c
1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * kernel/lockdep.c 4 * 5 * Runtime locking correctness validator 6 * 7 * Started by Ingo Molnar: 8 * 9 * Copyright (C) 2006,2007 Red Hat, Inc., Ingo Molnar <[email protected]> 10 * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra 11 * 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: 14 * 15 * - lock inversion scenarios 16 * - circular lock dependencies 17 * - hardirq/softirq safe/unsafe locking bugs 18 * 19 * Bugs are reported even if the current locking scenario does not cause 20 * any deadlock at this point. 21 * 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. 25 * 26 * Thanks to Arjan van de Ven for coming up with the initial idea of 27 * mapping lock dependencies runtime. 28 */ 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> 57 #include <linux/lockdep.h> 58 #include <linux/context_tracking.h> 59 60 #include <asm/sections.h> 61 62 #include "lockdep_internals.h" 63 64 #include <trace/events/lock.h> 65 66 #ifdef CONFIG_PROVE_LOCKING 67 static int prove_locking = 1; 68 module_param(prove_locking, int, 0644); 69 #else 70 #define prove_locking 0 71 #endif 72 73 #ifdef CONFIG_LOCK_STAT 74 static int lock_stat = 1; 75 module_param(lock_stat, int, 0644); 76 #else 77 #define lock_stat 0 78 #endif 79 80 #ifdef CONFIG_SYSCTL 81 static struct ctl_table kern_lockdep_table[] = { 82 #ifdef CONFIG_PROVE_LOCKING 83 { 84 .procname = "prove_locking", 85 .data = &prove_locking, 86 .maxlen = sizeof(int), 87 .mode = 0644, 88 .proc_handler = proc_dointvec, 89 }, 90 #endif /* CONFIG_PROVE_LOCKING */ 91 #ifdef CONFIG_LOCK_STAT 92 { 93 .procname = "lock_stat", 94 .data = &lock_stat, 95 .maxlen = sizeof(int), 96 .mode = 0644, 97 .proc_handler = proc_dointvec, 98 }, 99 #endif /* CONFIG_LOCK_STAT */ 100 { } 101 }; 102 103 static __init int kernel_lockdep_sysctls_init(void) 104 { 105 register_sysctl_init("kernel", kern_lockdep_table); 106 return 0; 107 } 108 late_initcall(kernel_lockdep_sysctls_init); 109 #endif /* CONFIG_SYSCTL */ 110 111 DEFINE_PER_CPU(unsigned int, lockdep_recursion); 112 EXPORT_PER_CPU_SYMBOL_GPL(lockdep_recursion); 113 114 static __always_inline bool lockdep_enabled(void) 115 { 116 if (!debug_locks) 117 return false; 118 119 if (this_cpu_read(lockdep_recursion)) 120 return false; 121 122 if (current->lockdep_recursion) 123 return false; 124 125 return true; 126 } 127 128 /* 129 * lockdep_lock: protects the lockdep graph, the hashes and the 130 * class/list/hash allocators. 131 * 132 * This is one of the rare exceptions where it's justified 133 * to use a raw spinlock - we really dont want the spinlock 134 * code to recurse back into the lockdep code... 135 */ 136 static arch_spinlock_t __lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED; 137 static struct task_struct *__owner; 138 139 static inline void lockdep_lock(void) 140 { 141 DEBUG_LOCKS_WARN_ON(!irqs_disabled()); 142 143 __this_cpu_inc(lockdep_recursion); 144 arch_spin_lock(&__lock); 145 __owner = current; 146 } 147 148 static inline void lockdep_unlock(void) 149 { 150 DEBUG_LOCKS_WARN_ON(!irqs_disabled()); 151 152 if (debug_locks && DEBUG_LOCKS_WARN_ON(__owner != current)) 153 return; 154 155 __owner = NULL; 156 arch_spin_unlock(&__lock); 157 __this_cpu_dec(lockdep_recursion); 158 } 159 160 static inline bool lockdep_assert_locked(void) 161 { 162 return DEBUG_LOCKS_WARN_ON(__owner != current); 163 } 164 165 static struct task_struct *lockdep_selftest_task_struct; 166 167 168 static int graph_lock(void) 169 { 170 lockdep_lock(); 171 /* 172 * Make sure that if another CPU detected a bug while 173 * walking the graph we dont change it (while the other 174 * CPU is busy printing out stuff with the graph lock 175 * dropped already) 176 */ 177 if (!debug_locks) { 178 lockdep_unlock(); 179 return 0; 180 } 181 return 1; 182 } 183 184 static inline void graph_unlock(void) 185 { 186 lockdep_unlock(); 187 } 188 189 /* 190 * Turn lock debugging off and return with 0 if it was off already, 191 * and also release the graph lock: 192 */ 193 static inline int debug_locks_off_graph_unlock(void) 194 { 195 int ret = debug_locks_off(); 196 197 lockdep_unlock(); 198 199 return ret; 200 } 201 202 unsigned long nr_list_entries; 203 static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES]; 204 static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES); 205 206 /* 207 * All data structures here are protected by the global debug_lock. 208 * 209 * nr_lock_classes is the number of elements of lock_classes[] that is 210 * in use. 211 */ 212 #define KEYHASH_BITS (MAX_LOCKDEP_KEYS_BITS - 1) 213 #define KEYHASH_SIZE (1UL << KEYHASH_BITS) 214 static struct hlist_head lock_keys_hash[KEYHASH_SIZE]; 215 unsigned long nr_lock_classes; 216 unsigned long nr_zapped_classes; 217 unsigned long max_lock_class_idx; 218 struct lock_class lock_classes[MAX_LOCKDEP_KEYS]; 219 DECLARE_BITMAP(lock_classes_in_use, MAX_LOCKDEP_KEYS); 220 221 static inline struct lock_class *hlock_class(struct held_lock *hlock) 222 { 223 unsigned int class_idx = hlock->class_idx; 224 225 /* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfield */ 226 barrier(); 227 228 if (!test_bit(class_idx, lock_classes_in_use)) { 229 /* 230 * Someone passed in garbage, we give up. 231 */ 232 DEBUG_LOCKS_WARN_ON(1); 233 return NULL; 234 } 235 236 /* 237 * At this point, if the passed hlock->class_idx is still garbage, 238 * we just have to live with it 239 */ 240 return lock_classes + class_idx; 241 } 242 243 #ifdef CONFIG_LOCK_STAT 244 static DEFINE_PER_CPU(struct lock_class_stats[MAX_LOCKDEP_KEYS], cpu_lock_stats); 245 246 static inline u64 lockstat_clock(void) 247 { 248 return local_clock(); 249 } 250 251 static int lock_point(unsigned long points[], unsigned long ip) 252 { 253 int i; 254 255 for (i = 0; i < LOCKSTAT_POINTS; i++) { 256 if (points[i] == 0) { 257 points[i] = ip; 258 break; 259 } 260 if (points[i] == ip) 261 break; 262 } 263 264 return i; 265 } 266 267 static void lock_time_inc(struct lock_time *lt, u64 time) 268 { 269 if (time > lt->max) 270 lt->max = time; 271 272 if (time < lt->min || !lt->nr) 273 lt->min = time; 274 275 lt->total += time; 276 lt->nr++; 277 } 278 279 static inline void lock_time_add(struct lock_time *src, struct lock_time *dst) 280 { 281 if (!src->nr) 282 return; 283 284 if (src->max > dst->max) 285 dst->max = src->max; 286 287 if (src->min < dst->min || !dst->nr) 288 dst->min = src->min; 289 290 dst->total += src->total; 291 dst->nr += src->nr; 292 } 293 294 struct lock_class_stats lock_stats(struct lock_class *class) 295 { 296 struct lock_class_stats stats; 297 int cpu, i; 298 299 memset(&stats, 0, sizeof(struct lock_class_stats)); 300 for_each_possible_cpu(cpu) { 301 struct lock_class_stats *pcs = 302 &per_cpu(cpu_lock_stats, cpu)[class - lock_classes]; 303 304 for (i = 0; i < ARRAY_SIZE(stats.contention_point); i++) 305 stats.contention_point[i] += pcs->contention_point[i]; 306 307 for (i = 0; i < ARRAY_SIZE(stats.contending_point); i++) 308 stats.contending_point[i] += pcs->contending_point[i]; 309 310 lock_time_add(&pcs->read_waittime, &stats.read_waittime); 311 lock_time_add(&pcs->write_waittime, &stats.write_waittime); 312 313 lock_time_add(&pcs->read_holdtime, &stats.read_holdtime); 314 lock_time_add(&pcs->write_holdtime, &stats.write_holdtime); 315 316 for (i = 0; i < ARRAY_SIZE(stats.bounces); i++) 317 stats.bounces[i] += pcs->bounces[i]; 318 } 319 320 return stats; 321 } 322 323 void clear_lock_stats(struct lock_class *class) 324 { 325 int cpu; 326 327 for_each_possible_cpu(cpu) { 328 struct lock_class_stats *cpu_stats = 329 &per_cpu(cpu_lock_stats, cpu)[class - lock_classes]; 330 331 memset(cpu_stats, 0, sizeof(struct lock_class_stats)); 332 } 333 memset(class->contention_point, 0, sizeof(class->contention_point)); 334 memset(class->contending_point, 0, sizeof(class->contending_point)); 335 } 336 337 static struct lock_class_stats *get_lock_stats(struct lock_class *class) 338 { 339 return &this_cpu_ptr(cpu_lock_stats)[class - lock_classes]; 340 } 341 342 static void lock_release_holdtime(struct held_lock *hlock) 343 { 344 struct lock_class_stats *stats; 345 u64 holdtime; 346 347 if (!lock_stat) 348 return; 349 350 holdtime = lockstat_clock() - hlock->holdtime_stamp; 351 352 stats = get_lock_stats(hlock_class(hlock)); 353 if (hlock->read) 354 lock_time_inc(&stats->read_holdtime, holdtime); 355 else 356 lock_time_inc(&stats->write_holdtime, holdtime); 357 } 358 #else 359 static inline void lock_release_holdtime(struct held_lock *hlock) 360 { 361 } 362 #endif 363 364 /* 365 * We keep a global list of all lock classes. The list is only accessed with 366 * the lockdep spinlock lock held. free_lock_classes is a list with free 367 * elements. These elements are linked together by the lock_entry member in 368 * struct lock_class. 369 */ 370 static LIST_HEAD(all_lock_classes); 371 static LIST_HEAD(free_lock_classes); 372 373 /** 374 * struct pending_free - information about data structures about to be freed 375 * @zapped: Head of a list with struct lock_class elements. 376 * @lock_chains_being_freed: Bitmap that indicates which lock_chains[] elements 377 * are about to be freed. 378 */ 379 struct pending_free { 380 struct list_head zapped; 381 DECLARE_BITMAP(lock_chains_being_freed, MAX_LOCKDEP_CHAINS); 382 }; 383 384 /** 385 * struct delayed_free - data structures used for delayed freeing 386 * 387 * A data structure for delayed freeing of data structures that may be 388 * accessed by RCU readers at the time these were freed. 389 * 390 * @rcu_head: Used to schedule an RCU callback for freeing data structures. 391 * @index: Index of @pf to which freed data structures are added. 392 * @scheduled: Whether or not an RCU callback has been scheduled. 393 * @pf: Array with information about data structures about to be freed. 394 */ 395 static struct delayed_free { 396 struct rcu_head rcu_head; 397 int index; 398 int scheduled; 399 struct pending_free pf[2]; 400 } delayed_free; 401 402 /* 403 * The lockdep classes are in a hash-table as well, for fast lookup: 404 */ 405 #define CLASSHASH_BITS (MAX_LOCKDEP_KEYS_BITS - 1) 406 #define CLASSHASH_SIZE (1UL << CLASSHASH_BITS) 407 #define __classhashfn(key) hash_long((unsigned long)key, CLASSHASH_BITS) 408 #define classhashentry(key) (classhash_table + __classhashfn((key))) 409 410 static struct hlist_head classhash_table[CLASSHASH_SIZE]; 411 412 /* 413 * We put the lock dependency chains into a hash-table as well, to cache 414 * their existence: 415 */ 416 #define CHAINHASH_BITS (MAX_LOCKDEP_CHAINS_BITS-1) 417 #define CHAINHASH_SIZE (1UL << CHAINHASH_BITS) 418 #define __chainhashfn(chain) hash_long(chain, CHAINHASH_BITS) 419 #define chainhashentry(chain) (chainhash_table + __chainhashfn((chain))) 420 421 static struct hlist_head chainhash_table[CHAINHASH_SIZE]; 422 423 /* 424 * the id of held_lock 425 */ 426 static inline u16 hlock_id(struct held_lock *hlock) 427 { 428 BUILD_BUG_ON(MAX_LOCKDEP_KEYS_BITS + 2 > 16); 429 430 return (hlock->class_idx | (hlock->read << MAX_LOCKDEP_KEYS_BITS)); 431 } 432 433 static inline unsigned int chain_hlock_class_idx(u16 hlock_id) 434 { 435 return hlock_id & (MAX_LOCKDEP_KEYS - 1); 436 } 437 438 /* 439 * The hash key of the lock dependency chains is a hash itself too: 440 * it's a hash of all locks taken up to that lock, including that lock. 441 * It's a 64-bit hash, because it's important for the keys to be 442 * unique. 443 */ 444 static inline u64 iterate_chain_key(u64 key, u32 idx) 445 { 446 u32 k0 = key, k1 = key >> 32; 447 448 __jhash_mix(idx, k0, k1); /* Macro that modifies arguments! */ 449 450 return k0 | (u64)k1 << 32; 451 } 452 453 void lockdep_init_task(struct task_struct *task) 454 { 455 task->lockdep_depth = 0; /* no locks held yet */ 456 task->curr_chain_key = INITIAL_CHAIN_KEY; 457 task->lockdep_recursion = 0; 458 } 459 460 static __always_inline void lockdep_recursion_inc(void) 461 { 462 __this_cpu_inc(lockdep_recursion); 463 } 464 465 static __always_inline void lockdep_recursion_finish(void) 466 { 467 if (WARN_ON_ONCE(__this_cpu_dec_return(lockdep_recursion))) 468 __this_cpu_write(lockdep_recursion, 0); 469 } 470 471 void lockdep_set_selftest_task(struct task_struct *task) 472 { 473 lockdep_selftest_task_struct = task; 474 } 475 476 /* 477 * Debugging switches: 478 */ 479 480 #define VERBOSE 0 481 #define VERY_VERBOSE 0 482 483 #if VERBOSE 484 # define HARDIRQ_VERBOSE 1 485 # define SOFTIRQ_VERBOSE 1 486 #else 487 # define HARDIRQ_VERBOSE 0 488 # define SOFTIRQ_VERBOSE 0 489 #endif 490 491 #if VERBOSE || HARDIRQ_VERBOSE || SOFTIRQ_VERBOSE 492 /* 493 * Quick filtering for interesting events: 494 */ 495 static int class_filter(struct lock_class *class) 496 { 497 #if 0 498 /* Example */ 499 if (class->name_version == 1 && 500 !strcmp(class->name, "lockname")) 501 return 1; 502 if (class->name_version == 1 && 503 !strcmp(class->name, "&struct->lockfield")) 504 return 1; 505 #endif 506 /* Filter everything else. 1 would be to allow everything else */ 507 return 0; 508 } 509 #endif 510 511 static int verbose(struct lock_class *class) 512 { 513 #if VERBOSE 514 return class_filter(class); 515 #endif 516 return 0; 517 } 518 519 static void print_lockdep_off(const char *bug_msg) 520 { 521 printk(KERN_DEBUG "%s\n", bug_msg); 522 printk(KERN_DEBUG "turning off the locking correctness validator.\n"); 523 #ifdef CONFIG_LOCK_STAT 524 printk(KERN_DEBUG "Please attach the output of /proc/lock_stat to the bug report\n"); 525 #endif 526 } 527 528 unsigned long nr_stack_trace_entries; 529 530 #ifdef CONFIG_PROVE_LOCKING 531 /** 532 * struct lock_trace - single stack backtrace 533 * @hash_entry: Entry in a stack_trace_hash[] list. 534 * @hash: jhash() of @entries. 535 * @nr_entries: Number of entries in @entries. 536 * @entries: Actual stack backtrace. 537 */ 538 struct lock_trace { 539 struct hlist_node hash_entry; 540 u32 hash; 541 u32 nr_entries; 542 unsigned long entries[] __aligned(sizeof(unsigned long)); 543 }; 544 #define LOCK_TRACE_SIZE_IN_LONGS \ 545 (sizeof(struct lock_trace) / sizeof(unsigned long)) 546 /* 547 * Stack-trace: sequence of lock_trace structures. Protected by the graph_lock. 548 */ 549 static unsigned long stack_trace[MAX_STACK_TRACE_ENTRIES]; 550 static struct hlist_head stack_trace_hash[STACK_TRACE_HASH_SIZE]; 551 552 static bool traces_identical(struct lock_trace *t1, struct lock_trace *t2) 553 { 554 return t1->hash == t2->hash && t1->nr_entries == t2->nr_entries && 555 memcmp(t1->entries, t2->entries, 556 t1->nr_entries * sizeof(t1->entries[0])) == 0; 557 } 558 559 static struct lock_trace *save_trace(void) 560 { 561 struct lock_trace *trace, *t2; 562 struct hlist_head *hash_head; 563 u32 hash; 564 int max_entries; 565 566 BUILD_BUG_ON_NOT_POWER_OF_2(STACK_TRACE_HASH_SIZE); 567 BUILD_BUG_ON(LOCK_TRACE_SIZE_IN_LONGS >= MAX_STACK_TRACE_ENTRIES); 568 569 trace = (struct lock_trace *)(stack_trace + nr_stack_trace_entries); 570 max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries - 571 LOCK_TRACE_SIZE_IN_LONGS; 572 573 if (max_entries <= 0) { 574 if (!debug_locks_off_graph_unlock()) 575 return NULL; 576 577 print_lockdep_off("BUG: MAX_STACK_TRACE_ENTRIES too low!"); 578 dump_stack(); 579 580 return NULL; 581 } 582 trace->nr_entries = stack_trace_save(trace->entries, max_entries, 3); 583 584 hash = jhash(trace->entries, trace->nr_entries * 585 sizeof(trace->entries[0]), 0); 586 trace->hash = hash; 587 hash_head = stack_trace_hash + (hash & (STACK_TRACE_HASH_SIZE - 1)); 588 hlist_for_each_entry(t2, hash_head, hash_entry) { 589 if (traces_identical(trace, t2)) 590 return t2; 591 } 592 nr_stack_trace_entries += LOCK_TRACE_SIZE_IN_LONGS + trace->nr_entries; 593 hlist_add_head(&trace->hash_entry, hash_head); 594 595 return trace; 596 } 597 598 /* Return the number of stack traces in the stack_trace[] array. */ 599 u64 lockdep_stack_trace_count(void) 600 { 601 struct lock_trace *trace; 602 u64 c = 0; 603 int i; 604 605 for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++) { 606 hlist_for_each_entry(trace, &stack_trace_hash[i], hash_entry) { 607 c++; 608 } 609 } 610 611 return c; 612 } 613 614 /* Return the number of stack hash chains that have at least one stack trace. */ 615 u64 lockdep_stack_hash_count(void) 616 { 617 u64 c = 0; 618 int i; 619 620 for (i = 0; i < ARRAY_SIZE(stack_trace_hash); i++) 621 if (!hlist_empty(&stack_trace_hash[i])) 622 c++; 623 624 return c; 625 } 626 #endif 627 628 unsigned int nr_hardirq_chains; 629 unsigned int nr_softirq_chains; 630 unsigned int nr_process_chains; 631 unsigned int max_lockdep_depth; 632 633 #ifdef CONFIG_DEBUG_LOCKDEP 634 /* 635 * Various lockdep statistics: 636 */ 637 DEFINE_PER_CPU(struct lockdep_stats, lockdep_stats); 638 #endif 639 640 #ifdef CONFIG_PROVE_LOCKING 641 /* 642 * Locking printouts: 643 */ 644 645 #define __USAGE(__STATE) \ 646 [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE)"-W", \ 647 [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON-W", \ 648 [LOCK_USED_IN_##__STATE##_READ] = "IN-"__stringify(__STATE)"-R",\ 649 [LOCK_ENABLED_##__STATE##_READ] = __stringify(__STATE)"-ON-R", 650 651 static const char *usage_str[] = 652 { 653 #define LOCKDEP_STATE(__STATE) __USAGE(__STATE) 654 #include "lockdep_states.h" 655 #undef LOCKDEP_STATE 656 [LOCK_USED] = "INITIAL USE", 657 [LOCK_USED_READ] = "INITIAL READ USE", 658 /* abused as string storage for verify_lock_unused() */ 659 [LOCK_USAGE_STATES] = "IN-NMI", 660 }; 661 #endif 662 663 const char *__get_key_name(const struct lockdep_subclass_key *key, char *str) 664 { 665 return kallsyms_lookup((unsigned long)key, NULL, NULL, NULL, str); 666 } 667 668 static inline unsigned long lock_flag(enum lock_usage_bit bit) 669 { 670 return 1UL << bit; 671 } 672 673 static char get_usage_char(struct lock_class *class, enum lock_usage_bit bit) 674 { 675 /* 676 * The usage character defaults to '.' (i.e., irqs disabled and not in 677 * irq context), which is the safest usage category. 678 */ 679 char c = '.'; 680 681 /* 682 * The order of the following usage checks matters, which will 683 * result in the outcome character as follows: 684 * 685 * - '+': irq is enabled and not in irq context 686 * - '-': in irq context and irq is disabled 687 * - '?': in irq context and irq is enabled 688 */ 689 if (class->usage_mask & lock_flag(bit + LOCK_USAGE_DIR_MASK)) { 690 c = '+'; 691 if (class->usage_mask & lock_flag(bit)) 692 c = '?'; 693 } else if (class->usage_mask & lock_flag(bit)) 694 c = '-'; 695 696 return c; 697 } 698 699 void get_usage_chars(struct lock_class *class, char usage[LOCK_USAGE_CHARS]) 700 { 701 int i = 0; 702 703 #define LOCKDEP_STATE(__STATE) \ 704 usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE); \ 705 usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_READ); 706 #include "lockdep_states.h" 707 #undef LOCKDEP_STATE 708 709 usage[i] = '\0'; 710 } 711 712 static void __print_lock_name(struct held_lock *hlock, struct lock_class *class) 713 { 714 char str[KSYM_NAME_LEN]; 715 const char *name; 716 717 name = class->name; 718 if (!name) { 719 name = __get_key_name(class->key, str); 720 printk(KERN_CONT "%s", name); 721 } else { 722 printk(KERN_CONT "%s", name); 723 if (class->name_version > 1) 724 printk(KERN_CONT "#%d", class->name_version); 725 if (class->subclass) 726 printk(KERN_CONT "/%d", class->subclass); 727 if (hlock && class->print_fn) 728 class->print_fn(hlock->instance); 729 } 730 } 731 732 static void print_lock_name(struct held_lock *hlock, struct lock_class *class) 733 { 734 char usage[LOCK_USAGE_CHARS]; 735 736 get_usage_chars(class, usage); 737 738 printk(KERN_CONT " ("); 739 __print_lock_name(hlock, class); 740 printk(KERN_CONT "){%s}-{%d:%d}", usage, 741 class->wait_type_outer ?: class->wait_type_inner, 742 class->wait_type_inner); 743 } 744 745 static void print_lockdep_cache(struct lockdep_map *lock) 746 { 747 const char *name; 748 char str[KSYM_NAME_LEN]; 749 750 name = lock->name; 751 if (!name) 752 name = __get_key_name(lock->key->subkeys, str); 753 754 printk(KERN_CONT "%s", name); 755 } 756 757 static void print_lock(struct held_lock *hlock) 758 { 759 /* 760 * We can be called locklessly through debug_show_all_locks() so be 761 * extra careful, the hlock might have been released and cleared. 762 * 763 * If this indeed happens, lets pretend it does not hurt to continue 764 * to print the lock unless the hlock class_idx does not point to a 765 * registered class. The rationale here is: since we don't attempt 766 * to distinguish whether we are in this situation, if it just 767 * happened we can't count on class_idx to tell either. 768 */ 769 struct lock_class *lock = hlock_class(hlock); 770 771 if (!lock) { 772 printk(KERN_CONT "<RELEASED>\n"); 773 return; 774 } 775 776 printk(KERN_CONT "%px", hlock->instance); 777 print_lock_name(hlock, lock); 778 printk(KERN_CONT ", at: %pS\n", (void *)hlock->acquire_ip); 779 } 780 781 static void lockdep_print_held_locks(struct task_struct *p) 782 { 783 int i, depth = READ_ONCE(p->lockdep_depth); 784 785 if (!depth) 786 printk("no locks held by %s/%d.\n", p->comm, task_pid_nr(p)); 787 else 788 printk("%d lock%s held by %s/%d:\n", depth, 789 depth > 1 ? "s" : "", p->comm, task_pid_nr(p)); 790 /* 791 * It's not reliable to print a task's held locks if it's not sleeping 792 * and it's not the current task. 793 */ 794 if (p != current && task_is_running(p)) 795 return; 796 for (i = 0; i < depth; i++) { 797 printk(" #%d: ", i); 798 print_lock(p->held_locks + i); 799 } 800 } 801 802 static void print_kernel_ident(void) 803 { 804 printk("%s %.*s %s\n", init_utsname()->release, 805 (int)strcspn(init_utsname()->version, " "), 806 init_utsname()->version, 807 print_tainted()); 808 } 809 810 static int very_verbose(struct lock_class *class) 811 { 812 #if VERY_VERBOSE 813 return class_filter(class); 814 #endif 815 return 0; 816 } 817 818 /* 819 * Is this the address of a static object: 820 */ 821 #ifdef __KERNEL__ 822 static int static_obj(const void *obj) 823 { 824 unsigned long addr = (unsigned long) obj; 825 826 if (is_kernel_core_data(addr)) 827 return 1; 828 829 /* 830 * keys are allowed in the __ro_after_init section. 831 */ 832 if (is_kernel_rodata(addr)) 833 return 1; 834 835 /* 836 * in initdata section and used during bootup only? 837 * NOTE: On some platforms the initdata section is 838 * outside of the _stext ... _end range. 839 */ 840 if (system_state < SYSTEM_FREEING_INITMEM && 841 init_section_contains((void *)addr, 1)) 842 return 1; 843 844 /* 845 * in-kernel percpu var? 846 */ 847 if (is_kernel_percpu_address(addr)) 848 return 1; 849 850 /* 851 * module static or percpu var? 852 */ 853 return is_module_address(addr) || is_module_percpu_address(addr); 854 } 855 #endif 856 857 /* 858 * To make lock name printouts unique, we calculate a unique 859 * class->name_version generation counter. The caller must hold the graph 860 * lock. 861 */ 862 static int count_matching_names(struct lock_class *new_class) 863 { 864 struct lock_class *class; 865 int count = 0; 866 867 if (!new_class->name) 868 return 0; 869 870 list_for_each_entry(class, &all_lock_classes, lock_entry) { 871 if (new_class->key - new_class->subclass == class->key) 872 return class->name_version; 873 if (class->name && !strcmp(class->name, new_class->name)) 874 count = max(count, class->name_version); 875 } 876 877 return count + 1; 878 } 879 880 /* used from NMI context -- must be lockless */ 881 static noinstr struct lock_class * 882 look_up_lock_class(const struct lockdep_map *lock, unsigned int subclass) 883 { 884 struct lockdep_subclass_key *key; 885 struct hlist_head *hash_head; 886 struct lock_class *class; 887 888 if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) { 889 instrumentation_begin(); 890 debug_locks_off(); 891 printk(KERN_ERR 892 "BUG: looking up invalid subclass: %u\n", subclass); 893 printk(KERN_ERR 894 "turning off the locking correctness validator.\n"); 895 dump_stack(); 896 instrumentation_end(); 897 return NULL; 898 } 899 900 /* 901 * If it is not initialised then it has never been locked, 902 * so it won't be present in the hash table. 903 */ 904 if (unlikely(!lock->key)) 905 return NULL; 906 907 /* 908 * NOTE: the class-key must be unique. For dynamic locks, a static 909 * lock_class_key variable is passed in through the mutex_init() 910 * (or spin_lock_init()) call - which acts as the key. For static 911 * locks we use the lock object itself as the key. 912 */ 913 BUILD_BUG_ON(sizeof(struct lock_class_key) > 914 sizeof(struct lockdep_map)); 915 916 key = lock->key->subkeys + subclass; 917 918 hash_head = classhashentry(key); 919 920 /* 921 * We do an RCU walk of the hash, see lockdep_free_key_range(). 922 */ 923 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled())) 924 return NULL; 925 926 hlist_for_each_entry_rcu_notrace(class, hash_head, hash_entry) { 927 if (class->key == key) { 928 /* 929 * Huh! same key, different name? Did someone trample 930 * on some memory? We're most confused. 931 */ 932 WARN_ONCE(class->name != lock->name && 933 lock->key != &__lockdep_no_validate__, 934 "Looking for class \"%s\" with key %ps, but found a different class \"%s\" with the same key\n", 935 lock->name, lock->key, class->name); 936 return class; 937 } 938 } 939 940 return NULL; 941 } 942 943 /* 944 * Static locks do not have their class-keys yet - for them the key is 945 * the lock object itself. If the lock is in the per cpu area, the 946 * canonical address of the lock (per cpu offset removed) is used. 947 */ 948 static bool assign_lock_key(struct lockdep_map *lock) 949 { 950 unsigned long can_addr, addr = (unsigned long)lock; 951 952 #ifdef __KERNEL__ 953 /* 954 * lockdep_free_key_range() assumes that struct lock_class_key 955 * objects do not overlap. Since we use the address of lock 956 * objects as class key for static objects, check whether the 957 * size of lock_class_key objects does not exceed the size of 958 * the smallest lock object. 959 */ 960 BUILD_BUG_ON(sizeof(struct lock_class_key) > sizeof(raw_spinlock_t)); 961 #endif 962 963 if (__is_kernel_percpu_address(addr, &can_addr)) 964 lock->key = (void *)can_addr; 965 else if (__is_module_percpu_address(addr, &can_addr)) 966 lock->key = (void *)can_addr; 967 else if (static_obj(lock)) 968 lock->key = (void *)lock; 969 else { 970 /* Debug-check: all keys must be persistent! */ 971 debug_locks_off(); 972 pr_err("INFO: trying to register non-static key.\n"); 973 pr_err("The code is fine but needs lockdep annotation, or maybe\n"); 974 pr_err("you didn't initialize this object before use?\n"); 975 pr_err("turning off the locking correctness validator.\n"); 976 dump_stack(); 977 return false; 978 } 979 980 return true; 981 } 982 983 #ifdef CONFIG_DEBUG_LOCKDEP 984 985 /* Check whether element @e occurs in list @h */ 986 static bool in_list(struct list_head *e, struct list_head *h) 987 { 988 struct list_head *f; 989 990 list_for_each(f, h) { 991 if (e == f) 992 return true; 993 } 994 995 return false; 996 } 997 998 /* 999 * Check whether entry @e occurs in any of the locks_after or locks_before 1000 * lists. 1001 */ 1002 static bool in_any_class_list(struct list_head *e) 1003 { 1004 struct lock_class *class; 1005 int i; 1006 1007 for (i = 0; i < ARRAY_SIZE(lock_classes); i++) { 1008 class = &lock_classes[i]; 1009 if (in_list(e, &class->locks_after) || 1010 in_list(e, &class->locks_before)) 1011 return true; 1012 } 1013 return false; 1014 } 1015 1016 static bool class_lock_list_valid(struct lock_class *c, struct list_head *h) 1017 { 1018 struct lock_list *e; 1019 1020 list_for_each_entry(e, h, entry) { 1021 if (e->links_to != c) { 1022 printk(KERN_INFO "class %s: mismatch for lock entry %ld; class %s <> %s", 1023 c->name ? : "(?)", 1024 (unsigned long)(e - list_entries), 1025 e->links_to && e->links_to->name ? 1026 e->links_to->name : "(?)", 1027 e->class && e->class->name ? e->class->name : 1028 "(?)"); 1029 return false; 1030 } 1031 } 1032 return true; 1033 } 1034 1035 #ifdef CONFIG_PROVE_LOCKING 1036 static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS]; 1037 #endif 1038 1039 static bool check_lock_chain_key(struct lock_chain *chain) 1040 { 1041 #ifdef CONFIG_PROVE_LOCKING 1042 u64 chain_key = INITIAL_CHAIN_KEY; 1043 int i; 1044 1045 for (i = chain->base; i < chain->base + chain->depth; i++) 1046 chain_key = iterate_chain_key(chain_key, chain_hlocks[i]); 1047 /* 1048 * The 'unsigned long long' casts avoid that a compiler warning 1049 * is reported when building tools/lib/lockdep. 1050 */ 1051 if (chain->chain_key != chain_key) { 1052 printk(KERN_INFO "chain %lld: key %#llx <> %#llx\n", 1053 (unsigned long long)(chain - lock_chains), 1054 (unsigned long long)chain->chain_key, 1055 (unsigned long long)chain_key); 1056 return false; 1057 } 1058 #endif 1059 return true; 1060 } 1061 1062 static bool in_any_zapped_class_list(struct lock_class *class) 1063 { 1064 struct pending_free *pf; 1065 int i; 1066 1067 for (i = 0, pf = delayed_free.pf; i < ARRAY_SIZE(delayed_free.pf); i++, pf++) { 1068 if (in_list(&class->lock_entry, &pf->zapped)) 1069 return true; 1070 } 1071 1072 return false; 1073 } 1074 1075 static bool __check_data_structures(void) 1076 { 1077 struct lock_class *class; 1078 struct lock_chain *chain; 1079 struct hlist_head *head; 1080 struct lock_list *e; 1081 int i; 1082 1083 /* Check whether all classes occur in a lock list. */ 1084 for (i = 0; i < ARRAY_SIZE(lock_classes); i++) { 1085 class = &lock_classes[i]; 1086 if (!in_list(&class->lock_entry, &all_lock_classes) && 1087 !in_list(&class->lock_entry, &free_lock_classes) && 1088 !in_any_zapped_class_list(class)) { 1089 printk(KERN_INFO "class %px/%s is not in any class list\n", 1090 class, class->name ? : "(?)"); 1091 return false; 1092 } 1093 } 1094 1095 /* Check whether all classes have valid lock lists. */ 1096 for (i = 0; i < ARRAY_SIZE(lock_classes); i++) { 1097 class = &lock_classes[i]; 1098 if (!class_lock_list_valid(class, &class->locks_before)) 1099 return false; 1100 if (!class_lock_list_valid(class, &class->locks_after)) 1101 return false; 1102 } 1103 1104 /* Check the chain_key of all lock chains. */ 1105 for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) { 1106 head = chainhash_table + i; 1107 hlist_for_each_entry_rcu(chain, head, entry) { 1108 if (!check_lock_chain_key(chain)) 1109 return false; 1110 } 1111 } 1112 1113 /* 1114 * Check whether all list entries that are in use occur in a class 1115 * lock list. 1116 */ 1117 for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) { 1118 e = list_entries + i; 1119 if (!in_any_class_list(&e->entry)) { 1120 printk(KERN_INFO "list entry %d is not in any class list; class %s <> %s\n", 1121 (unsigned int)(e - list_entries), 1122 e->class->name ? : "(?)", 1123 e->links_to->name ? : "(?)"); 1124 return false; 1125 } 1126 } 1127 1128 /* 1129 * Check whether all list entries that are not in use do not occur in 1130 * a class lock list. 1131 */ 1132 for_each_clear_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) { 1133 e = list_entries + i; 1134 if (in_any_class_list(&e->entry)) { 1135 printk(KERN_INFO "list entry %d occurs in a class list; class %s <> %s\n", 1136 (unsigned int)(e - list_entries), 1137 e->class && e->class->name ? e->class->name : 1138 "(?)", 1139 e->links_to && e->links_to->name ? 1140 e->links_to->name : "(?)"); 1141 return false; 1142 } 1143 } 1144 1145 return true; 1146 } 1147 1148 int check_consistency = 0; 1149 module_param(check_consistency, int, 0644); 1150 1151 static void check_data_structures(void) 1152 { 1153 static bool once = false; 1154 1155 if (check_consistency && !once) { 1156 if (!__check_data_structures()) { 1157 once = true; 1158 WARN_ON(once); 1159 } 1160 } 1161 } 1162 1163 #else /* CONFIG_DEBUG_LOCKDEP */ 1164 1165 static inline void check_data_structures(void) { } 1166 1167 #endif /* CONFIG_DEBUG_LOCKDEP */ 1168 1169 static void init_chain_block_buckets(void); 1170 1171 /* 1172 * Initialize the lock_classes[] array elements, the free_lock_classes list 1173 * and also the delayed_free structure. 1174 */ 1175 static void init_data_structures_once(void) 1176 { 1177 static bool __read_mostly ds_initialized, rcu_head_initialized; 1178 int i; 1179 1180 if (likely(rcu_head_initialized)) 1181 return; 1182 1183 if (system_state >= SYSTEM_SCHEDULING) { 1184 init_rcu_head(&delayed_free.rcu_head); 1185 rcu_head_initialized = true; 1186 } 1187 1188 if (ds_initialized) 1189 return; 1190 1191 ds_initialized = true; 1192 1193 INIT_LIST_HEAD(&delayed_free.pf[0].zapped); 1194 INIT_LIST_HEAD(&delayed_free.pf[1].zapped); 1195 1196 for (i = 0; i < ARRAY_SIZE(lock_classes); i++) { 1197 list_add_tail(&lock_classes[i].lock_entry, &free_lock_classes); 1198 INIT_LIST_HEAD(&lock_classes[i].locks_after); 1199 INIT_LIST_HEAD(&lock_classes[i].locks_before); 1200 } 1201 init_chain_block_buckets(); 1202 } 1203 1204 static inline struct hlist_head *keyhashentry(const struct lock_class_key *key) 1205 { 1206 unsigned long hash = hash_long((uintptr_t)key, KEYHASH_BITS); 1207 1208 return lock_keys_hash + hash; 1209 } 1210 1211 /* Register a dynamically allocated key. */ 1212 void lockdep_register_key(struct lock_class_key *key) 1213 { 1214 struct hlist_head *hash_head; 1215 struct lock_class_key *k; 1216 unsigned long flags; 1217 1218 if (WARN_ON_ONCE(static_obj(key))) 1219 return; 1220 hash_head = keyhashentry(key); 1221 1222 raw_local_irq_save(flags); 1223 if (!graph_lock()) 1224 goto restore_irqs; 1225 hlist_for_each_entry_rcu(k, hash_head, hash_entry) { 1226 if (WARN_ON_ONCE(k == key)) 1227 goto out_unlock; 1228 } 1229 hlist_add_head_rcu(&key->hash_entry, hash_head); 1230 out_unlock: 1231 graph_unlock(); 1232 restore_irqs: 1233 raw_local_irq_restore(flags); 1234 } 1235 EXPORT_SYMBOL_GPL(lockdep_register_key); 1236 1237 /* Check whether a key has been registered as a dynamic key. */ 1238 static bool is_dynamic_key(const struct lock_class_key *key) 1239 { 1240 struct hlist_head *hash_head; 1241 struct lock_class_key *k; 1242 bool found = false; 1243 1244 if (WARN_ON_ONCE(static_obj(key))) 1245 return false; 1246 1247 /* 1248 * If lock debugging is disabled lock_keys_hash[] may contain 1249 * pointers to memory that has already been freed. Avoid triggering 1250 * a use-after-free in that case by returning early. 1251 */ 1252 if (!debug_locks) 1253 return true; 1254 1255 hash_head = keyhashentry(key); 1256 1257 rcu_read_lock(); 1258 hlist_for_each_entry_rcu(k, hash_head, hash_entry) { 1259 if (k == key) { 1260 found = true; 1261 break; 1262 } 1263 } 1264 rcu_read_unlock(); 1265 1266 return found; 1267 } 1268 1269 /* 1270 * Register a lock's class in the hash-table, if the class is not present 1271 * yet. Otherwise we look it up. We cache the result in the lock object 1272 * itself, so actual lookup of the hash should be once per lock object. 1273 */ 1274 static struct lock_class * 1275 register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force) 1276 { 1277 struct lockdep_subclass_key *key; 1278 struct hlist_head *hash_head; 1279 struct lock_class *class; 1280 int idx; 1281 1282 DEBUG_LOCKS_WARN_ON(!irqs_disabled()); 1283 1284 class = look_up_lock_class(lock, subclass); 1285 if (likely(class)) 1286 goto out_set_class_cache; 1287 1288 if (!lock->key) { 1289 if (!assign_lock_key(lock)) 1290 return NULL; 1291 } else if (!static_obj(lock->key) && !is_dynamic_key(lock->key)) { 1292 return NULL; 1293 } 1294 1295 key = lock->key->subkeys + subclass; 1296 hash_head = classhashentry(key); 1297 1298 if (!graph_lock()) { 1299 return NULL; 1300 } 1301 /* 1302 * We have to do the hash-walk again, to avoid races 1303 * with another CPU: 1304 */ 1305 hlist_for_each_entry_rcu(class, hash_head, hash_entry) { 1306 if (class->key == key) 1307 goto out_unlock_set; 1308 } 1309 1310 init_data_structures_once(); 1311 1312 /* Allocate a new lock class and add it to the hash. */ 1313 class = list_first_entry_or_null(&free_lock_classes, typeof(*class), 1314 lock_entry); 1315 if (!class) { 1316 if (!debug_locks_off_graph_unlock()) { 1317 return NULL; 1318 } 1319 1320 print_lockdep_off("BUG: MAX_LOCKDEP_KEYS too low!"); 1321 dump_stack(); 1322 return NULL; 1323 } 1324 nr_lock_classes++; 1325 __set_bit(class - lock_classes, lock_classes_in_use); 1326 debug_atomic_inc(nr_unused_locks); 1327 class->key = key; 1328 class->name = lock->name; 1329 class->subclass = subclass; 1330 WARN_ON_ONCE(!list_empty(&class->locks_before)); 1331 WARN_ON_ONCE(!list_empty(&class->locks_after)); 1332 class->name_version = count_matching_names(class); 1333 class->wait_type_inner = lock->wait_type_inner; 1334 class->wait_type_outer = lock->wait_type_outer; 1335 class->lock_type = lock->lock_type; 1336 /* 1337 * We use RCU's safe list-add method to make 1338 * parallel walking of the hash-list safe: 1339 */ 1340 hlist_add_head_rcu(&class->hash_entry, hash_head); 1341 /* 1342 * Remove the class from the free list and add it to the global list 1343 * of classes. 1344 */ 1345 list_move_tail(&class->lock_entry, &all_lock_classes); 1346 idx = class - lock_classes; 1347 if (idx > max_lock_class_idx) 1348 max_lock_class_idx = idx; 1349 1350 if (verbose(class)) { 1351 graph_unlock(); 1352 1353 printk("\nnew class %px: %s", class->key, class->name); 1354 if (class->name_version > 1) 1355 printk(KERN_CONT "#%d", class->name_version); 1356 printk(KERN_CONT "\n"); 1357 dump_stack(); 1358 1359 if (!graph_lock()) { 1360 return NULL; 1361 } 1362 } 1363 out_unlock_set: 1364 graph_unlock(); 1365 1366 out_set_class_cache: 1367 if (!subclass || force) 1368 lock->class_cache[0] = class; 1369 else if (subclass < NR_LOCKDEP_CACHING_CLASSES) 1370 lock->class_cache[subclass] = class; 1371 1372 /* 1373 * Hash collision, did we smoke some? We found a class with a matching 1374 * hash but the subclass -- which is hashed in -- didn't match. 1375 */ 1376 if (DEBUG_LOCKS_WARN_ON(class->subclass != subclass)) 1377 return NULL; 1378 1379 return class; 1380 } 1381 1382 #ifdef CONFIG_PROVE_LOCKING 1383 /* 1384 * Allocate a lockdep entry. (assumes the graph_lock held, returns 1385 * with NULL on failure) 1386 */ 1387 static struct lock_list *alloc_list_entry(void) 1388 { 1389 int idx = find_first_zero_bit(list_entries_in_use, 1390 ARRAY_SIZE(list_entries)); 1391 1392 if (idx >= ARRAY_SIZE(list_entries)) { 1393 if (!debug_locks_off_graph_unlock()) 1394 return NULL; 1395 1396 print_lockdep_off("BUG: MAX_LOCKDEP_ENTRIES too low!"); 1397 dump_stack(); 1398 return NULL; 1399 } 1400 nr_list_entries++; 1401 __set_bit(idx, list_entries_in_use); 1402 return list_entries + idx; 1403 } 1404 1405 /* 1406 * Add a new dependency to the head of the list: 1407 */ 1408 static int add_lock_to_list(struct lock_class *this, 1409 struct lock_class *links_to, struct list_head *head, 1410 u16 distance, u8 dep, 1411 const struct lock_trace *trace) 1412 { 1413 struct lock_list *entry; 1414 /* 1415 * Lock not present yet - get a new dependency struct and 1416 * add it to the list: 1417 */ 1418 entry = alloc_list_entry(); 1419 if (!entry) 1420 return 0; 1421 1422 entry->class = this; 1423 entry->links_to = links_to; 1424 entry->dep = dep; 1425 entry->distance = distance; 1426 entry->trace = trace; 1427 /* 1428 * Both allocation and removal are done under the graph lock; but 1429 * iteration is under RCU-sched; see look_up_lock_class() and 1430 * lockdep_free_key_range(). 1431 */ 1432 list_add_tail_rcu(&entry->entry, head); 1433 1434 return 1; 1435 } 1436 1437 /* 1438 * For good efficiency of modular, we use power of 2 1439 */ 1440 #define MAX_CIRCULAR_QUEUE_SIZE (1UL << CONFIG_LOCKDEP_CIRCULAR_QUEUE_BITS) 1441 #define CQ_MASK (MAX_CIRCULAR_QUEUE_SIZE-1) 1442 1443 /* 1444 * The circular_queue and helpers are used to implement graph 1445 * breadth-first search (BFS) algorithm, by which we can determine 1446 * whether there is a path from a lock to another. In deadlock checks, 1447 * a path from the next lock to be acquired to a previous held lock 1448 * indicates that adding the <prev> -> <next> lock dependency will 1449 * produce a circle in the graph. Breadth-first search instead of 1450 * depth-first search is used in order to find the shortest (circular) 1451 * path. 1452 */ 1453 struct circular_queue { 1454 struct lock_list *element[MAX_CIRCULAR_QUEUE_SIZE]; 1455 unsigned int front, rear; 1456 }; 1457 1458 static struct circular_queue lock_cq; 1459 1460 unsigned int max_bfs_queue_depth; 1461 1462 static unsigned int lockdep_dependency_gen_id; 1463 1464 static inline void __cq_init(struct circular_queue *cq) 1465 { 1466 cq->front = cq->rear = 0; 1467 lockdep_dependency_gen_id++; 1468 } 1469 1470 static inline int __cq_empty(struct circular_queue *cq) 1471 { 1472 return (cq->front == cq->rear); 1473 } 1474 1475 static inline int __cq_full(struct circular_queue *cq) 1476 { 1477 return ((cq->rear + 1) & CQ_MASK) == cq->front; 1478 } 1479 1480 static inline int __cq_enqueue(struct circular_queue *cq, struct lock_list *elem) 1481 { 1482 if (__cq_full(cq)) 1483 return -1; 1484 1485 cq->element[cq->rear] = elem; 1486 cq->rear = (cq->rear + 1) & CQ_MASK; 1487 return 0; 1488 } 1489 1490 /* 1491 * Dequeue an element from the circular_queue, return a lock_list if 1492 * the queue is not empty, or NULL if otherwise. 1493 */ 1494 static inline struct lock_list * __cq_dequeue(struct circular_queue *cq) 1495 { 1496 struct lock_list * lock; 1497 1498 if (__cq_empty(cq)) 1499 return NULL; 1500 1501 lock = cq->element[cq->front]; 1502 cq->front = (cq->front + 1) & CQ_MASK; 1503 1504 return lock; 1505 } 1506 1507 static inline unsigned int __cq_get_elem_count(struct circular_queue *cq) 1508 { 1509 return (cq->rear - cq->front) & CQ_MASK; 1510 } 1511 1512 static inline void mark_lock_accessed(struct lock_list *lock) 1513 { 1514 lock->class->dep_gen_id = lockdep_dependency_gen_id; 1515 } 1516 1517 static inline void visit_lock_entry(struct lock_list *lock, 1518 struct lock_list *parent) 1519 { 1520 lock->parent = parent; 1521 } 1522 1523 static inline unsigned long lock_accessed(struct lock_list *lock) 1524 { 1525 return lock->class->dep_gen_id == lockdep_dependency_gen_id; 1526 } 1527 1528 static inline struct lock_list *get_lock_parent(struct lock_list *child) 1529 { 1530 return child->parent; 1531 } 1532 1533 static inline int get_lock_depth(struct lock_list *child) 1534 { 1535 int depth = 0; 1536 struct lock_list *parent; 1537 1538 while ((parent = get_lock_parent(child))) { 1539 child = parent; 1540 depth++; 1541 } 1542 return depth; 1543 } 1544 1545 /* 1546 * Return the forward or backward dependency list. 1547 * 1548 * @lock: the lock_list to get its class's dependency list 1549 * @offset: the offset to struct lock_class to determine whether it is 1550 * locks_after or locks_before 1551 */ 1552 static inline struct list_head *get_dep_list(struct lock_list *lock, int offset) 1553 { 1554 void *lock_class = lock->class; 1555 1556 return lock_class + offset; 1557 } 1558 /* 1559 * Return values of a bfs search: 1560 * 1561 * BFS_E* indicates an error 1562 * BFS_R* indicates a result (match or not) 1563 * 1564 * BFS_EINVALIDNODE: Find a invalid node in the graph. 1565 * 1566 * BFS_EQUEUEFULL: The queue is full while doing the bfs. 1567 * 1568 * BFS_RMATCH: Find the matched node in the graph, and put that node into 1569 * *@target_entry. 1570 * 1571 * BFS_RNOMATCH: Haven't found the matched node and keep *@target_entry 1572 * _unchanged_. 1573 */ 1574 enum bfs_result { 1575 BFS_EINVALIDNODE = -2, 1576 BFS_EQUEUEFULL = -1, 1577 BFS_RMATCH = 0, 1578 BFS_RNOMATCH = 1, 1579 }; 1580 1581 /* 1582 * bfs_result < 0 means error 1583 */ 1584 static inline bool bfs_error(enum bfs_result res) 1585 { 1586 return res < 0; 1587 } 1588 1589 /* 1590 * DEP_*_BIT in lock_list::dep 1591 * 1592 * For dependency @prev -> @next: 1593 * 1594 * SR: @prev is shared reader (->read != 0) and @next is recursive reader 1595 * (->read == 2) 1596 * ER: @prev is exclusive locker (->read == 0) and @next is recursive reader 1597 * SN: @prev is shared reader and @next is non-recursive locker (->read != 2) 1598 * EN: @prev is exclusive locker and @next is non-recursive locker 1599 * 1600 * Note that we define the value of DEP_*_BITs so that: 1601 * bit0 is prev->read == 0 1602 * bit1 is next->read != 2 1603 */ 1604 #define DEP_SR_BIT (0 + (0 << 1)) /* 0 */ 1605 #define DEP_ER_BIT (1 + (0 << 1)) /* 1 */ 1606 #define DEP_SN_BIT (0 + (1 << 1)) /* 2 */ 1607 #define DEP_EN_BIT (1 + (1 << 1)) /* 3 */ 1608 1609 #define DEP_SR_MASK (1U << (DEP_SR_BIT)) 1610 #define DEP_ER_MASK (1U << (DEP_ER_BIT)) 1611 #define DEP_SN_MASK (1U << (DEP_SN_BIT)) 1612 #define DEP_EN_MASK (1U << (DEP_EN_BIT)) 1613 1614 static inline unsigned int 1615 __calc_dep_bit(struct held_lock *prev, struct held_lock *next) 1616 { 1617 return (prev->read == 0) + ((next->read != 2) << 1); 1618 } 1619 1620 static inline u8 calc_dep(struct held_lock *prev, struct held_lock *next) 1621 { 1622 return 1U << __calc_dep_bit(prev, next); 1623 } 1624 1625 /* 1626 * calculate the dep_bit for backwards edges. We care about whether @prev is 1627 * shared and whether @next is recursive. 1628 */ 1629 static inline unsigned int 1630 __calc_dep_bitb(struct held_lock *prev, struct held_lock *next) 1631 { 1632 return (next->read != 2) + ((prev->read == 0) << 1); 1633 } 1634 1635 static inline u8 calc_depb(struct held_lock *prev, struct held_lock *next) 1636 { 1637 return 1U << __calc_dep_bitb(prev, next); 1638 } 1639 1640 /* 1641 * Initialize a lock_list entry @lock belonging to @class as the root for a BFS 1642 * search. 1643 */ 1644 static inline void __bfs_init_root(struct lock_list *lock, 1645 struct lock_class *class) 1646 { 1647 lock->class = class; 1648 lock->parent = NULL; 1649 lock->only_xr = 0; 1650 } 1651 1652 /* 1653 * Initialize a lock_list entry @lock based on a lock acquisition @hlock as the 1654 * root for a BFS search. 1655 * 1656 * ->only_xr of the initial lock node is set to @hlock->read == 2, to make sure 1657 * that <prev> -> @hlock and @hlock -> <whatever __bfs() found> is not -(*R)-> 1658 * and -(S*)->. 1659 */ 1660 static inline void bfs_init_root(struct lock_list *lock, 1661 struct held_lock *hlock) 1662 { 1663 __bfs_init_root(lock, hlock_class(hlock)); 1664 lock->only_xr = (hlock->read == 2); 1665 } 1666 1667 /* 1668 * Similar to bfs_init_root() but initialize the root for backwards BFS. 1669 * 1670 * ->only_xr of the initial lock node is set to @hlock->read != 0, to make sure 1671 * that <next> -> @hlock and @hlock -> <whatever backwards BFS found> is not 1672 * -(*S)-> and -(R*)-> (reverse order of -(*R)-> and -(S*)->). 1673 */ 1674 static inline void bfs_init_rootb(struct lock_list *lock, 1675 struct held_lock *hlock) 1676 { 1677 __bfs_init_root(lock, hlock_class(hlock)); 1678 lock->only_xr = (hlock->read != 0); 1679 } 1680 1681 static inline struct lock_list *__bfs_next(struct lock_list *lock, int offset) 1682 { 1683 if (!lock || !lock->parent) 1684 return NULL; 1685 1686 return list_next_or_null_rcu(get_dep_list(lock->parent, offset), 1687 &lock->entry, struct lock_list, entry); 1688 } 1689 1690 /* 1691 * Breadth-First Search to find a strong path in the dependency graph. 1692 * 1693 * @source_entry: the source of the path we are searching for. 1694 * @data: data used for the second parameter of @match function 1695 * @match: match function for the search 1696 * @target_entry: pointer to the target of a matched path 1697 * @offset: the offset to struct lock_class to determine whether it is 1698 * locks_after or locks_before 1699 * 1700 * We may have multiple edges (considering different kinds of dependencies, 1701 * e.g. ER and SN) between two nodes in the dependency graph. But 1702 * only the strong dependency path in the graph is relevant to deadlocks. A 1703 * strong dependency path is a dependency path that doesn't have two adjacent 1704 * dependencies as -(*R)-> -(S*)->, please see: 1705 * 1706 * Documentation/locking/lockdep-design.rst 1707 * 1708 * for more explanation of the definition of strong dependency paths 1709 * 1710 * In __bfs(), we only traverse in the strong dependency path: 1711 * 1712 * In lock_list::only_xr, we record whether the previous dependency only 1713 * has -(*R)-> in the search, and if it does (prev only has -(*R)->), we 1714 * filter out any -(S*)-> in the current dependency and after that, the 1715 * ->only_xr is set according to whether we only have -(*R)-> left. 1716 */ 1717 static enum bfs_result __bfs(struct lock_list *source_entry, 1718 void *data, 1719 bool (*match)(struct lock_list *entry, void *data), 1720 bool (*skip)(struct lock_list *entry, void *data), 1721 struct lock_list **target_entry, 1722 int offset) 1723 { 1724 struct circular_queue *cq = &lock_cq; 1725 struct lock_list *lock = NULL; 1726 struct lock_list *entry; 1727 struct list_head *head; 1728 unsigned int cq_depth; 1729 bool first; 1730 1731 lockdep_assert_locked(); 1732 1733 __cq_init(cq); 1734 __cq_enqueue(cq, source_entry); 1735 1736 while ((lock = __bfs_next(lock, offset)) || (lock = __cq_dequeue(cq))) { 1737 if (!lock->class) 1738 return BFS_EINVALIDNODE; 1739 1740 /* 1741 * Step 1: check whether we already finish on this one. 1742 * 1743 * If we have visited all the dependencies from this @lock to 1744 * others (iow, if we have visited all lock_list entries in 1745 * @lock->class->locks_{after,before}) we skip, otherwise go 1746 * and visit all the dependencies in the list and mark this 1747 * list accessed. 1748 */ 1749 if (lock_accessed(lock)) 1750 continue; 1751 else 1752 mark_lock_accessed(lock); 1753 1754 /* 1755 * Step 2: check whether prev dependency and this form a strong 1756 * dependency path. 1757 */ 1758 if (lock->parent) { /* Parent exists, check prev dependency */ 1759 u8 dep = lock->dep; 1760 bool prev_only_xr = lock->parent->only_xr; 1761 1762 /* 1763 * Mask out all -(S*)-> if we only have *R in previous 1764 * step, because -(*R)-> -(S*)-> don't make up a strong 1765 * dependency. 1766 */ 1767 if (prev_only_xr) 1768 dep &= ~(DEP_SR_MASK | DEP_SN_MASK); 1769 1770 /* If nothing left, we skip */ 1771 if (!dep) 1772 continue; 1773 1774 /* If there are only -(*R)-> left, set that for the next step */ 1775 lock->only_xr = !(dep & (DEP_SN_MASK | DEP_EN_MASK)); 1776 } 1777 1778 /* 1779 * Step 3: we haven't visited this and there is a strong 1780 * dependency path to this, so check with @match. 1781 * If @skip is provide and returns true, we skip this 1782 * lock (and any path this lock is in). 1783 */ 1784 if (skip && skip(lock, data)) 1785 continue; 1786 1787 if (match(lock, data)) { 1788 *target_entry = lock; 1789 return BFS_RMATCH; 1790 } 1791 1792 /* 1793 * Step 4: if not match, expand the path by adding the 1794 * forward or backwards dependencies in the search 1795 * 1796 */ 1797 first = true; 1798 head = get_dep_list(lock, offset); 1799 list_for_each_entry_rcu(entry, head, entry) { 1800 visit_lock_entry(entry, lock); 1801 1802 /* 1803 * Note we only enqueue the first of the list into the 1804 * queue, because we can always find a sibling 1805 * dependency from one (see __bfs_next()), as a result 1806 * the space of queue is saved. 1807 */ 1808 if (!first) 1809 continue; 1810 1811 first = false; 1812 1813 if (__cq_enqueue(cq, entry)) 1814 return BFS_EQUEUEFULL; 1815 1816 cq_depth = __cq_get_elem_count(cq); 1817 if (max_bfs_queue_depth < cq_depth) 1818 max_bfs_queue_depth = cq_depth; 1819 } 1820 } 1821 1822 return BFS_RNOMATCH; 1823 } 1824 1825 static inline enum bfs_result 1826 __bfs_forwards(struct lock_list *src_entry, 1827 void *data, 1828 bool (*match)(struct lock_list *entry, void *data), 1829 bool (*skip)(struct lock_list *entry, void *data), 1830 struct lock_list **target_entry) 1831 { 1832 return __bfs(src_entry, data, match, skip, target_entry, 1833 offsetof(struct lock_class, locks_after)); 1834 1835 } 1836 1837 static inline enum bfs_result 1838 __bfs_backwards(struct lock_list *src_entry, 1839 void *data, 1840 bool (*match)(struct lock_list *entry, void *data), 1841 bool (*skip)(struct lock_list *entry, void *data), 1842 struct lock_list **target_entry) 1843 { 1844 return __bfs(src_entry, data, match, skip, target_entry, 1845 offsetof(struct lock_class, locks_before)); 1846 1847 } 1848 1849 static void print_lock_trace(const struct lock_trace *trace, 1850 unsigned int spaces) 1851 { 1852 stack_trace_print(trace->entries, trace->nr_entries, spaces); 1853 } 1854 1855 /* 1856 * Print a dependency chain entry (this is only done when a deadlock 1857 * has been detected): 1858 */ 1859 static noinline void 1860 print_circular_bug_entry(struct lock_list *target, int depth) 1861 { 1862 if (debug_locks_silent) 1863 return; 1864 printk("\n-> #%u", depth); 1865 print_lock_name(NULL, target->class); 1866 printk(KERN_CONT ":\n"); 1867 print_lock_trace(target->trace, 6); 1868 } 1869 1870 static void 1871 print_circular_lock_scenario(struct held_lock *src, 1872 struct held_lock *tgt, 1873 struct lock_list *prt) 1874 { 1875 struct lock_class *source = hlock_class(src); 1876 struct lock_class *target = hlock_class(tgt); 1877 struct lock_class *parent = prt->class; 1878 int src_read = src->read; 1879 int tgt_read = tgt->read; 1880 1881 /* 1882 * A direct locking problem where unsafe_class lock is taken 1883 * directly by safe_class lock, then all we need to show 1884 * is the deadlock scenario, as it is obvious that the 1885 * unsafe lock is taken under the safe lock. 1886 * 1887 * But if there is a chain instead, where the safe lock takes 1888 * an intermediate lock (middle_class) where this lock is 1889 * not the same as the safe lock, then the lock chain is 1890 * used to describe the problem. Otherwise we would need 1891 * to show a different CPU case for each link in the chain 1892 * from the safe_class lock to the unsafe_class lock. 1893 */ 1894 if (parent != source) { 1895 printk("Chain exists of:\n "); 1896 __print_lock_name(src, source); 1897 printk(KERN_CONT " --> "); 1898 __print_lock_name(NULL, parent); 1899 printk(KERN_CONT " --> "); 1900 __print_lock_name(tgt, target); 1901 printk(KERN_CONT "\n\n"); 1902 } 1903 1904 printk(" Possible unsafe locking scenario:\n\n"); 1905 printk(" CPU0 CPU1\n"); 1906 printk(" ---- ----\n"); 1907 if (tgt_read != 0) 1908 printk(" rlock("); 1909 else 1910 printk(" lock("); 1911 __print_lock_name(tgt, target); 1912 printk(KERN_CONT ");\n"); 1913 printk(" lock("); 1914 __print_lock_name(NULL, parent); 1915 printk(KERN_CONT ");\n"); 1916 printk(" lock("); 1917 __print_lock_name(tgt, target); 1918 printk(KERN_CONT ");\n"); 1919 if (src_read != 0) 1920 printk(" rlock("); 1921 else if (src->sync) 1922 printk(" sync("); 1923 else 1924 printk(" lock("); 1925 __print_lock_name(src, source); 1926 printk(KERN_CONT ");\n"); 1927 printk("\n *** DEADLOCK ***\n\n"); 1928 } 1929 1930 /* 1931 * When a circular dependency is detected, print the 1932 * header first: 1933 */ 1934 static noinline void 1935 print_circular_bug_header(struct lock_list *entry, unsigned int depth, 1936 struct held_lock *check_src, 1937 struct held_lock *check_tgt) 1938 { 1939 struct task_struct *curr = current; 1940 1941 if (debug_locks_silent) 1942 return; 1943 1944 pr_warn("\n"); 1945 pr_warn("======================================================\n"); 1946 pr_warn("WARNING: possible circular locking dependency detected\n"); 1947 print_kernel_ident(); 1948 pr_warn("------------------------------------------------------\n"); 1949 pr_warn("%s/%d is trying to acquire lock:\n", 1950 curr->comm, task_pid_nr(curr)); 1951 print_lock(check_src); 1952 1953 pr_warn("\nbut task is already holding lock:\n"); 1954 1955 print_lock(check_tgt); 1956 pr_warn("\nwhich lock already depends on the new lock.\n\n"); 1957 pr_warn("\nthe existing dependency chain (in reverse order) is:\n"); 1958 1959 print_circular_bug_entry(entry, depth); 1960 } 1961 1962 /* 1963 * We are about to add A -> B into the dependency graph, and in __bfs() a 1964 * strong dependency path A -> .. -> B is found: hlock_class equals 1965 * entry->class. 1966 * 1967 * If A -> .. -> B can replace A -> B in any __bfs() search (means the former 1968 * is _stronger_ than or equal to the latter), we consider A -> B as redundant. 1969 * For example if A -> .. -> B is -(EN)-> (i.e. A -(E*)-> .. -(*N)-> B), and A 1970 * -> B is -(ER)-> or -(EN)->, then we don't need to add A -> B into the 1971 * dependency graph, as any strong path ..-> A -> B ->.. we can get with 1972 * having dependency A -> B, we could already get a equivalent path ..-> A -> 1973 * .. -> B -> .. with A -> .. -> B. Therefore A -> B is redundant. 1974 * 1975 * We need to make sure both the start and the end of A -> .. -> B is not 1976 * weaker than A -> B. For the start part, please see the comment in 1977 * check_redundant(). For the end part, we need: 1978 * 1979 * Either 1980 * 1981 * a) A -> B is -(*R)-> (everything is not weaker than that) 1982 * 1983 * or 1984 * 1985 * b) A -> .. -> B is -(*N)-> (nothing is stronger than this) 1986 * 1987 */ 1988 static inline bool hlock_equal(struct lock_list *entry, void *data) 1989 { 1990 struct held_lock *hlock = (struct held_lock *)data; 1991 1992 return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */ 1993 (hlock->read == 2 || /* A -> B is -(*R)-> */ 1994 !entry->only_xr); /* A -> .. -> B is -(*N)-> */ 1995 } 1996 1997 /* 1998 * We are about to add B -> A into the dependency graph, and in __bfs() a 1999 * strong dependency path A -> .. -> B is found: hlock_class equals 2000 * entry->class. 2001 * 2002 * We will have a deadlock case (conflict) if A -> .. -> B -> A is a strong 2003 * dependency cycle, that means: 2004 * 2005 * Either 2006 * 2007 * a) B -> A is -(E*)-> 2008 * 2009 * or 2010 * 2011 * b) A -> .. -> B is -(*N)-> (i.e. A -> .. -(*N)-> B) 2012 * 2013 * as then we don't have -(*R)-> -(S*)-> in the cycle. 2014 */ 2015 static inline bool hlock_conflict(struct lock_list *entry, void *data) 2016 { 2017 struct held_lock *hlock = (struct held_lock *)data; 2018 2019 return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */ 2020 (hlock->read == 0 || /* B -> A is -(E*)-> */ 2021 !entry->only_xr); /* A -> .. -> B is -(*N)-> */ 2022 } 2023 2024 static noinline void print_circular_bug(struct lock_list *this, 2025 struct lock_list *target, 2026 struct held_lock *check_src, 2027 struct held_lock *check_tgt) 2028 { 2029 struct task_struct *curr = current; 2030 struct lock_list *parent; 2031 struct lock_list *first_parent; 2032 int depth; 2033 2034 if (!debug_locks_off_graph_unlock() || debug_locks_silent) 2035 return; 2036 2037 this->trace = save_trace(); 2038 if (!this->trace) 2039 return; 2040 2041 depth = get_lock_depth(target); 2042 2043 print_circular_bug_header(target, depth, check_src, check_tgt); 2044 2045 parent = get_lock_parent(target); 2046 first_parent = parent; 2047 2048 while (parent) { 2049 print_circular_bug_entry(parent, --depth); 2050 parent = get_lock_parent(parent); 2051 } 2052 2053 printk("\nother info that might help us debug this:\n\n"); 2054 print_circular_lock_scenario(check_src, check_tgt, 2055 first_parent); 2056 2057 lockdep_print_held_locks(curr); 2058 2059 printk("\nstack backtrace:\n"); 2060 dump_stack(); 2061 } 2062 2063 static noinline void print_bfs_bug(int ret) 2064 { 2065 if (!debug_locks_off_graph_unlock()) 2066 return; 2067 2068 /* 2069 * Breadth-first-search failed, graph got corrupted? 2070 */ 2071 WARN(1, "lockdep bfs error:%d\n", ret); 2072 } 2073 2074 static bool noop_count(struct lock_list *entry, void *data) 2075 { 2076 (*(unsigned long *)data)++; 2077 return false; 2078 } 2079 2080 static unsigned long __lockdep_count_forward_deps(struct lock_list *this) 2081 { 2082 unsigned long count = 0; 2083 struct lock_list *target_entry; 2084 2085 __bfs_forwards(this, (void *)&count, noop_count, NULL, &target_entry); 2086 2087 return count; 2088 } 2089 unsigned long lockdep_count_forward_deps(struct lock_class *class) 2090 { 2091 unsigned long ret, flags; 2092 struct lock_list this; 2093 2094 __bfs_init_root(&this, class); 2095 2096 raw_local_irq_save(flags); 2097 lockdep_lock(); 2098 ret = __lockdep_count_forward_deps(&this); 2099 lockdep_unlock(); 2100 raw_local_irq_restore(flags); 2101 2102 return ret; 2103 } 2104 2105 static unsigned long __lockdep_count_backward_deps(struct lock_list *this) 2106 { 2107 unsigned long count = 0; 2108 struct lock_list *target_entry; 2109 2110 __bfs_backwards(this, (void *)&count, noop_count, NULL, &target_entry); 2111 2112 return count; 2113 } 2114 2115 unsigned long lockdep_count_backward_deps(struct lock_class *class) 2116 { 2117 unsigned long ret, flags; 2118 struct lock_list this; 2119 2120 __bfs_init_root(&this, class); 2121 2122 raw_local_irq_save(flags); 2123 lockdep_lock(); 2124 ret = __lockdep_count_backward_deps(&this); 2125 lockdep_unlock(); 2126 raw_local_irq_restore(flags); 2127 2128 return ret; 2129 } 2130 2131 /* 2132 * Check that the dependency graph starting at <src> can lead to 2133 * <target> or not. 2134 */ 2135 static noinline enum bfs_result 2136 check_path(struct held_lock *target, struct lock_list *src_entry, 2137 bool (*match)(struct lock_list *entry, void *data), 2138 bool (*skip)(struct lock_list *entry, void *data), 2139 struct lock_list **target_entry) 2140 { 2141 enum bfs_result ret; 2142 2143 ret = __bfs_forwards(src_entry, target, match, skip, target_entry); 2144 2145 if (unlikely(bfs_error(ret))) 2146 print_bfs_bug(ret); 2147 2148 return ret; 2149 } 2150 2151 static void print_deadlock_bug(struct task_struct *, struct held_lock *, struct held_lock *); 2152 2153 /* 2154 * Prove that the dependency graph starting at <src> can not 2155 * lead to <target>. If it can, there is a circle when adding 2156 * <target> -> <src> dependency. 2157 * 2158 * Print an error and return BFS_RMATCH if it does. 2159 */ 2160 static noinline enum bfs_result 2161 check_noncircular(struct held_lock *src, struct held_lock *target, 2162 struct lock_trace **const trace) 2163 { 2164 enum bfs_result ret; 2165 struct lock_list *target_entry; 2166 struct lock_list src_entry; 2167 2168 bfs_init_root(&src_entry, src); 2169 2170 debug_atomic_inc(nr_cyclic_checks); 2171 2172 ret = check_path(target, &src_entry, hlock_conflict, NULL, &target_entry); 2173 2174 if (unlikely(ret == BFS_RMATCH)) { 2175 if (!*trace) { 2176 /* 2177 * If save_trace fails here, the printing might 2178 * trigger a WARN but because of the !nr_entries it 2179 * should not do bad things. 2180 */ 2181 *trace = save_trace(); 2182 } 2183 2184 if (src->class_idx == target->class_idx) 2185 print_deadlock_bug(current, src, target); 2186 else 2187 print_circular_bug(&src_entry, target_entry, src, target); 2188 } 2189 2190 return ret; 2191 } 2192 2193 #ifdef CONFIG_TRACE_IRQFLAGS 2194 2195 /* 2196 * Forwards and backwards subgraph searching, for the purposes of 2197 * proving that two subgraphs can be connected by a new dependency 2198 * without creating any illegal irq-safe -> irq-unsafe lock dependency. 2199 * 2200 * A irq safe->unsafe deadlock happens with the following conditions: 2201 * 2202 * 1) We have a strong dependency path A -> ... -> B 2203 * 2204 * 2) and we have ENABLED_IRQ usage of B and USED_IN_IRQ usage of A, therefore 2205 * irq can create a new dependency B -> A (consider the case that a holder 2206 * of B gets interrupted by an irq whose handler will try to acquire A). 2207 * 2208 * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a 2209 * strong circle: 2210 * 2211 * For the usage bits of B: 2212 * a) if A -> B is -(*N)->, then B -> A could be any type, so any 2213 * ENABLED_IRQ usage suffices. 2214 * b) if A -> B is -(*R)->, then B -> A must be -(E*)->, so only 2215 * ENABLED_IRQ_*_READ usage suffices. 2216 * 2217 * For the usage bits of A: 2218 * c) if A -> B is -(E*)->, then B -> A could be any type, so any 2219 * USED_IN_IRQ usage suffices. 2220 * d) if A -> B is -(S*)->, then B -> A must be -(*N)->, so only 2221 * USED_IN_IRQ_*_READ usage suffices. 2222 */ 2223 2224 /* 2225 * There is a strong dependency path in the dependency graph: A -> B, and now 2226 * we need to decide which usage bit of A should be accumulated to detect 2227 * safe->unsafe bugs. 2228 * 2229 * Note that usage_accumulate() is used in backwards search, so ->only_xr 2230 * stands for whether A -> B only has -(S*)-> (in this case ->only_xr is true). 2231 * 2232 * As above, if only_xr is false, which means A -> B has -(E*)-> dependency 2233 * path, any usage of A should be considered. Otherwise, we should only 2234 * consider _READ usage. 2235 */ 2236 static inline bool usage_accumulate(struct lock_list *entry, void *mask) 2237 { 2238 if (!entry->only_xr) 2239 *(unsigned long *)mask |= entry->class->usage_mask; 2240 else /* Mask out _READ usage bits */ 2241 *(unsigned long *)mask |= (entry->class->usage_mask & LOCKF_IRQ); 2242 2243 return false; 2244 } 2245 2246 /* 2247 * There is a strong dependency path in the dependency graph: A -> B, and now 2248 * we need to decide which usage bit of B conflicts with the usage bits of A, 2249 * i.e. which usage bit of B may introduce safe->unsafe deadlocks. 2250 * 2251 * As above, if only_xr is false, which means A -> B has -(*N)-> dependency 2252 * path, any usage of B should be considered. Otherwise, we should only 2253 * consider _READ usage. 2254 */ 2255 static inline bool usage_match(struct lock_list *entry, void *mask) 2256 { 2257 if (!entry->only_xr) 2258 return !!(entry->class->usage_mask & *(unsigned long *)mask); 2259 else /* Mask out _READ usage bits */ 2260 return !!((entry->class->usage_mask & LOCKF_IRQ) & *(unsigned long *)mask); 2261 } 2262 2263 static inline bool usage_skip(struct lock_list *entry, void *mask) 2264 { 2265 if (entry->class->lock_type == LD_LOCK_NORMAL) 2266 return false; 2267 2268 /* 2269 * Skip local_lock() for irq inversion detection. 2270 * 2271 * For !RT, local_lock() is not a real lock, so it won't carry any 2272 * dependency. 2273 * 2274 * For RT, an irq inversion happens when we have lock A and B, and on 2275 * some CPU we can have: 2276 * 2277 * lock(A); 2278 * <interrupted> 2279 * lock(B); 2280 * 2281 * where lock(B) cannot sleep, and we have a dependency B -> ... -> A. 2282 * 2283 * Now we prove local_lock() cannot exist in that dependency. First we 2284 * have the observation for any lock chain L1 -> ... -> Ln, for any 2285 * 1 <= i <= n, Li.inner_wait_type <= L1.inner_wait_type, otherwise 2286 * wait context check will complain. And since B is not a sleep lock, 2287 * therefore B.inner_wait_type >= 2, and since the inner_wait_type of 2288 * local_lock() is 3, which is greater than 2, therefore there is no 2289 * way the local_lock() exists in the dependency B -> ... -> A. 2290 * 2291 * As a result, we will skip local_lock(), when we search for irq 2292 * inversion bugs. 2293 */ 2294 if (entry->class->lock_type == LD_LOCK_PERCPU && 2295 DEBUG_LOCKS_WARN_ON(entry->class->wait_type_inner < LD_WAIT_CONFIG)) 2296 return false; 2297 2298 /* 2299 * Skip WAIT_OVERRIDE for irq inversion detection -- it's not actually 2300 * a lock and only used to override the wait_type. 2301 */ 2302 2303 return true; 2304 } 2305 2306 /* 2307 * Find a node in the forwards-direction dependency sub-graph starting 2308 * at @root->class that matches @bit. 2309 * 2310 * Return BFS_MATCH if such a node exists in the subgraph, and put that node 2311 * into *@target_entry. 2312 */ 2313 static enum bfs_result 2314 find_usage_forwards(struct lock_list *root, unsigned long usage_mask, 2315 struct lock_list **target_entry) 2316 { 2317 enum bfs_result result; 2318 2319 debug_atomic_inc(nr_find_usage_forwards_checks); 2320 2321 result = __bfs_forwards(root, &usage_mask, usage_match, usage_skip, target_entry); 2322 2323 return result; 2324 } 2325 2326 /* 2327 * Find a node in the backwards-direction dependency sub-graph starting 2328 * at @root->class that matches @bit. 2329 */ 2330 static enum bfs_result 2331 find_usage_backwards(struct lock_list *root, unsigned long usage_mask, 2332 struct lock_list **target_entry) 2333 { 2334 enum bfs_result result; 2335 2336 debug_atomic_inc(nr_find_usage_backwards_checks); 2337 2338 result = __bfs_backwards(root, &usage_mask, usage_match, usage_skip, target_entry); 2339 2340 return result; 2341 } 2342 2343 static void print_lock_class_header(struct lock_class *class, int depth) 2344 { 2345 int bit; 2346 2347 printk("%*s->", depth, ""); 2348 print_lock_name(NULL, class); 2349 #ifdef CONFIG_DEBUG_LOCKDEP 2350 printk(KERN_CONT " ops: %lu", debug_class_ops_read(class)); 2351 #endif 2352 printk(KERN_CONT " {\n"); 2353 2354 for (bit = 0; bit < LOCK_TRACE_STATES; bit++) { 2355 if (class->usage_mask & (1 << bit)) { 2356 int len = depth; 2357 2358 len += printk("%*s %s", depth, "", usage_str[bit]); 2359 len += printk(KERN_CONT " at:\n"); 2360 print_lock_trace(class->usage_traces[bit], len); 2361 } 2362 } 2363 printk("%*s }\n", depth, ""); 2364 2365 printk("%*s ... key at: [<%px>] %pS\n", 2366 depth, "", class->key, class->key); 2367 } 2368 2369 /* 2370 * Dependency path printing: 2371 * 2372 * After BFS we get a lock dependency path (linked via ->parent of lock_list), 2373 * printing out each lock in the dependency path will help on understanding how 2374 * the deadlock could happen. Here are some details about dependency path 2375 * printing: 2376 * 2377 * 1) A lock_list can be either forwards or backwards for a lock dependency, 2378 * for a lock dependency A -> B, there are two lock_lists: 2379 * 2380 * a) lock_list in the ->locks_after list of A, whose ->class is B and 2381 * ->links_to is A. In this case, we can say the lock_list is 2382 * "A -> B" (forwards case). 2383 * 2384 * b) lock_list in the ->locks_before list of B, whose ->class is A 2385 * and ->links_to is B. In this case, we can say the lock_list is 2386 * "B <- A" (bacwards case). 2387 * 2388 * The ->trace of both a) and b) point to the call trace where B was 2389 * acquired with A held. 2390 * 2391 * 2) A "helper" lock_list is introduced during BFS, this lock_list doesn't 2392 * represent a certain lock dependency, it only provides an initial entry 2393 * for BFS. For example, BFS may introduce a "helper" lock_list whose 2394 * ->class is A, as a result BFS will search all dependencies starting with 2395 * A, e.g. A -> B or A -> C. 2396 * 2397 * The notation of a forwards helper lock_list is like "-> A", which means 2398 * we should search the forwards dependencies starting with "A", e.g A -> B 2399 * or A -> C. 2400 * 2401 * The notation of a bacwards helper lock_list is like "<- B", which means 2402 * we should search the backwards dependencies ending with "B", e.g. 2403 * B <- A or B <- C. 2404 */ 2405 2406 /* 2407 * printk the shortest lock dependencies from @root to @leaf in reverse order. 2408 * 2409 * We have a lock dependency path as follow: 2410 * 2411 * @root @leaf 2412 * | | 2413 * V V 2414 * ->parent ->parent 2415 * | lock_list | <--------- | lock_list | ... | lock_list | <--------- | lock_list | 2416 * | -> L1 | | L1 -> L2 | ... |Ln-2 -> Ln-1| | Ln-1 -> Ln| 2417 * 2418 * , so it's natural that we start from @leaf and print every ->class and 2419 * ->trace until we reach the @root. 2420 */ 2421 static void __used 2422 print_shortest_lock_dependencies(struct lock_list *leaf, 2423 struct lock_list *root) 2424 { 2425 struct lock_list *entry = leaf; 2426 int depth; 2427 2428 /*compute depth from generated tree by BFS*/ 2429 depth = get_lock_depth(leaf); 2430 2431 do { 2432 print_lock_class_header(entry->class, depth); 2433 printk("%*s ... acquired at:\n", depth, ""); 2434 print_lock_trace(entry->trace, 2); 2435 printk("\n"); 2436 2437 if (depth == 0 && (entry != root)) { 2438 printk("lockdep:%s bad path found in chain graph\n", __func__); 2439 break; 2440 } 2441 2442 entry = get_lock_parent(entry); 2443 depth--; 2444 } while (entry && (depth >= 0)); 2445 } 2446 2447 /* 2448 * printk the shortest lock dependencies from @leaf to @root. 2449 * 2450 * We have a lock dependency path (from a backwards search) as follow: 2451 * 2452 * @leaf @root 2453 * | | 2454 * V V 2455 * ->parent ->parent 2456 * | lock_list | ---------> | lock_list | ... | lock_list | ---------> | lock_list | 2457 * | L2 <- L1 | | L3 <- L2 | ... | Ln <- Ln-1 | | <- Ln | 2458 * 2459 * , so when we iterate from @leaf to @root, we actually print the lock 2460 * dependency path L1 -> L2 -> .. -> Ln in the non-reverse order. 2461 * 2462 * Another thing to notice here is that ->class of L2 <- L1 is L1, while the 2463 * ->trace of L2 <- L1 is the call trace of L2, in fact we don't have the call 2464 * trace of L1 in the dependency path, which is alright, because most of the 2465 * time we can figure out where L1 is held from the call trace of L2. 2466 */ 2467 static void __used 2468 print_shortest_lock_dependencies_backwards(struct lock_list *leaf, 2469 struct lock_list *root) 2470 { 2471 struct lock_list *entry = leaf; 2472 const struct lock_trace *trace = NULL; 2473 int depth; 2474 2475 /*compute depth from generated tree by BFS*/ 2476 depth = get_lock_depth(leaf); 2477 2478 do { 2479 print_lock_class_header(entry->class, depth); 2480 if (trace) { 2481 printk("%*s ... acquired at:\n", depth, ""); 2482 print_lock_trace(trace, 2); 2483 printk("\n"); 2484 } 2485 2486 /* 2487 * Record the pointer to the trace for the next lock_list 2488 * entry, see the comments for the function. 2489 */ 2490 trace = entry->trace; 2491 2492 if (depth == 0 && (entry != root)) { 2493 printk("lockdep:%s bad path found in chain graph\n", __func__); 2494 break; 2495 } 2496 2497 entry = get_lock_parent(entry); 2498 depth--; 2499 } while (entry && (depth >= 0)); 2500 } 2501 2502 static void 2503 print_irq_lock_scenario(struct lock_list *safe_entry, 2504 struct lock_list *unsafe_entry, 2505 struct lock_class *prev_class, 2506 struct lock_class *next_class) 2507 { 2508 struct lock_class *safe_class = safe_entry->class; 2509 struct lock_class *unsafe_class = unsafe_entry->class; 2510 struct lock_class *middle_class = prev_class; 2511 2512 if (middle_class == safe_class) 2513 middle_class = next_class; 2514 2515 /* 2516 * A direct locking problem where unsafe_class lock is taken 2517 * directly by safe_class lock, then all we need to show 2518 * is the deadlock scenario, as it is obvious that the 2519 * unsafe lock is taken under the safe lock. 2520 * 2521 * But if there is a chain instead, where the safe lock takes 2522 * an intermediate lock (middle_class) where this lock is 2523 * not the same as the safe lock, then the lock chain is 2524 * used to describe the problem. Otherwise we would need 2525 * to show a different CPU case for each link in the chain 2526 * from the safe_class lock to the unsafe_class lock. 2527 */ 2528 if (middle_class != unsafe_class) { 2529 printk("Chain exists of:\n "); 2530 __print_lock_name(NULL, safe_class); 2531 printk(KERN_CONT " --> "); 2532 __print_lock_name(NULL, middle_class); 2533 printk(KERN_CONT " --> "); 2534 __print_lock_name(NULL, unsafe_class); 2535 printk(KERN_CONT "\n\n"); 2536 } 2537 2538 printk(" Possible interrupt unsafe locking scenario:\n\n"); 2539 printk(" CPU0 CPU1\n"); 2540 printk(" ---- ----\n"); 2541 printk(" lock("); 2542 __print_lock_name(NULL, unsafe_class); 2543 printk(KERN_CONT ");\n"); 2544 printk(" local_irq_disable();\n"); 2545 printk(" lock("); 2546 __print_lock_name(NULL, safe_class); 2547 printk(KERN_CONT ");\n"); 2548 printk(" lock("); 2549 __print_lock_name(NULL, middle_class); 2550 printk(KERN_CONT ");\n"); 2551 printk(" <Interrupt>\n"); 2552 printk(" lock("); 2553 __print_lock_name(NULL, safe_class); 2554 printk(KERN_CONT ");\n"); 2555 printk("\n *** DEADLOCK ***\n\n"); 2556 } 2557 2558 static void 2559 print_bad_irq_dependency(struct task_struct *curr, 2560 struct lock_list *prev_root, 2561 struct lock_list *next_root, 2562 struct lock_list *backwards_entry, 2563 struct lock_list *forwards_entry, 2564 struct held_lock *prev, 2565 struct held_lock *next, 2566 enum lock_usage_bit bit1, 2567 enum lock_usage_bit bit2, 2568 const char *irqclass) 2569 { 2570 if (!debug_locks_off_graph_unlock() || debug_locks_silent) 2571 return; 2572 2573 pr_warn("\n"); 2574 pr_warn("=====================================================\n"); 2575 pr_warn("WARNING: %s-safe -> %s-unsafe lock order detected\n", 2576 irqclass, irqclass); 2577 print_kernel_ident(); 2578 pr_warn("-----------------------------------------------------\n"); 2579 pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] is trying to acquire:\n", 2580 curr->comm, task_pid_nr(curr), 2581 lockdep_hardirq_context(), hardirq_count() >> HARDIRQ_SHIFT, 2582 curr->softirq_context, softirq_count() >> SOFTIRQ_SHIFT, 2583 lockdep_hardirqs_enabled(), 2584 curr->softirqs_enabled); 2585 print_lock(next); 2586 2587 pr_warn("\nand this task is already holding:\n"); 2588 print_lock(prev); 2589 pr_warn("which would create a new lock dependency:\n"); 2590 print_lock_name(prev, hlock_class(prev)); 2591 pr_cont(" ->"); 2592 print_lock_name(next, hlock_class(next)); 2593 pr_cont("\n"); 2594 2595 pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n", 2596 irqclass); 2597 print_lock_name(NULL, backwards_entry->class); 2598 pr_warn("\n... which became %s-irq-safe at:\n", irqclass); 2599 2600 print_lock_trace(backwards_entry->class->usage_traces[bit1], 1); 2601 2602 pr_warn("\nto a %s-irq-unsafe lock:\n", irqclass); 2603 print_lock_name(NULL, forwards_entry->class); 2604 pr_warn("\n... which became %s-irq-unsafe at:\n", irqclass); 2605 pr_warn("..."); 2606 2607 print_lock_trace(forwards_entry->class->usage_traces[bit2], 1); 2608 2609 pr_warn("\nother info that might help us debug this:\n\n"); 2610 print_irq_lock_scenario(backwards_entry, forwards_entry, 2611 hlock_class(prev), hlock_class(next)); 2612 2613 lockdep_print_held_locks(curr); 2614 2615 pr_warn("\nthe dependencies between %s-irq-safe lock and the holding lock:\n", irqclass); 2616 print_shortest_lock_dependencies_backwards(backwards_entry, prev_root); 2617 2618 pr_warn("\nthe dependencies between the lock to be acquired"); 2619 pr_warn(" and %s-irq-unsafe lock:\n", irqclass); 2620 next_root->trace = save_trace(); 2621 if (!next_root->trace) 2622 return; 2623 print_shortest_lock_dependencies(forwards_entry, next_root); 2624 2625 pr_warn("\nstack backtrace:\n"); 2626 dump_stack(); 2627 } 2628 2629 static const char *state_names[] = { 2630 #define LOCKDEP_STATE(__STATE) \ 2631 __stringify(__STATE), 2632 #include "lockdep_states.h" 2633 #undef LOCKDEP_STATE 2634 }; 2635 2636 static const char *state_rnames[] = { 2637 #define LOCKDEP_STATE(__STATE) \ 2638 __stringify(__STATE)"-READ", 2639 #include "lockdep_states.h" 2640 #undef LOCKDEP_STATE 2641 }; 2642 2643 static inline const char *state_name(enum lock_usage_bit bit) 2644 { 2645 if (bit & LOCK_USAGE_READ_MASK) 2646 return state_rnames[bit >> LOCK_USAGE_DIR_MASK]; 2647 else 2648 return state_names[bit >> LOCK_USAGE_DIR_MASK]; 2649 } 2650 2651 /* 2652 * The bit number is encoded like: 2653 * 2654 * bit0: 0 exclusive, 1 read lock 2655 * bit1: 0 used in irq, 1 irq enabled 2656 * bit2-n: state 2657 */ 2658 static int exclusive_bit(int new_bit) 2659 { 2660 int state = new_bit & LOCK_USAGE_STATE_MASK; 2661 int dir = new_bit & LOCK_USAGE_DIR_MASK; 2662 2663 /* 2664 * keep state, bit flip the direction and strip read. 2665 */ 2666 return state | (dir ^ LOCK_USAGE_DIR_MASK); 2667 } 2668 2669 /* 2670 * Observe that when given a bitmask where each bitnr is encoded as above, a 2671 * right shift of the mask transforms the individual bitnrs as -1 and 2672 * conversely, a left shift transforms into +1 for the individual bitnrs. 2673 * 2674 * So for all bits whose number have LOCK_ENABLED_* set (bitnr1 == 1), we can 2675 * create the mask with those bit numbers using LOCK_USED_IN_* (bitnr1 == 0) 2676 * instead by subtracting the bit number by 2, or shifting the mask right by 2. 2677 * 2678 * Similarly, bitnr1 == 0 becomes bitnr1 == 1 by adding 2, or shifting left 2. 2679 * 2680 * So split the mask (note that LOCKF_ENABLED_IRQ_ALL|LOCKF_USED_IN_IRQ_ALL is 2681 * all bits set) and recompose with bitnr1 flipped. 2682 */ 2683 static unsigned long invert_dir_mask(unsigned long mask) 2684 { 2685 unsigned long excl = 0; 2686 2687 /* Invert dir */ 2688 excl |= (mask & LOCKF_ENABLED_IRQ_ALL) >> LOCK_USAGE_DIR_MASK; 2689 excl |= (mask & LOCKF_USED_IN_IRQ_ALL) << LOCK_USAGE_DIR_MASK; 2690 2691 return excl; 2692 } 2693 2694 /* 2695 * Note that a LOCK_ENABLED_IRQ_*_READ usage and a LOCK_USED_IN_IRQ_*_READ 2696 * usage may cause deadlock too, for example: 2697 * 2698 * P1 P2 2699 * <irq disabled> 2700 * write_lock(l1); <irq enabled> 2701 * read_lock(l2); 2702 * write_lock(l2); 2703 * <in irq> 2704 * read_lock(l1); 2705 * 2706 * , in above case, l1 will be marked as LOCK_USED_IN_IRQ_HARDIRQ_READ and l2 2707 * will marked as LOCK_ENABLE_IRQ_HARDIRQ_READ, and this is a possible 2708 * deadlock. 2709 * 2710 * In fact, all of the following cases may cause deadlocks: 2711 * 2712 * LOCK_USED_IN_IRQ_* -> LOCK_ENABLED_IRQ_* 2713 * LOCK_USED_IN_IRQ_*_READ -> LOCK_ENABLED_IRQ_* 2714 * LOCK_USED_IN_IRQ_* -> LOCK_ENABLED_IRQ_*_READ 2715 * LOCK_USED_IN_IRQ_*_READ -> LOCK_ENABLED_IRQ_*_READ 2716 * 2717 * As a result, to calculate the "exclusive mask", first we invert the 2718 * direction (USED_IN/ENABLED) of the original mask, and 1) for all bits with 2719 * bitnr0 set (LOCK_*_READ), add those with bitnr0 cleared (LOCK_*). 2) for all 2720 * bits with bitnr0 cleared (LOCK_*_READ), add those with bitnr0 set (LOCK_*). 2721 */ 2722 static unsigned long exclusive_mask(unsigned long mask) 2723 { 2724 unsigned long excl = invert_dir_mask(mask); 2725 2726 excl |= (excl & LOCKF_IRQ_READ) >> LOCK_USAGE_READ_MASK; 2727 excl |= (excl & LOCKF_IRQ) << LOCK_USAGE_READ_MASK; 2728 2729 return excl; 2730 } 2731 2732 /* 2733 * Retrieve the _possible_ original mask to which @mask is 2734 * exclusive. Ie: this is the opposite of exclusive_mask(). 2735 * Note that 2 possible original bits can match an exclusive 2736 * bit: one has LOCK_USAGE_READ_MASK set, the other has it 2737 * cleared. So both are returned for each exclusive bit. 2738 */ 2739 static unsigned long original_mask(unsigned long mask) 2740 { 2741 unsigned long excl = invert_dir_mask(mask); 2742 2743 /* Include read in existing usages */ 2744 excl |= (excl & LOCKF_IRQ_READ) >> LOCK_USAGE_READ_MASK; 2745 excl |= (excl & LOCKF_IRQ) << LOCK_USAGE_READ_MASK; 2746 2747 return excl; 2748 } 2749 2750 /* 2751 * Find the first pair of bit match between an original 2752 * usage mask and an exclusive usage mask. 2753 */ 2754 static int find_exclusive_match(unsigned long mask, 2755 unsigned long excl_mask, 2756 enum lock_usage_bit *bitp, 2757 enum lock_usage_bit *excl_bitp) 2758 { 2759 int bit, excl, excl_read; 2760 2761 for_each_set_bit(bit, &mask, LOCK_USED) { 2762 /* 2763 * exclusive_bit() strips the read bit, however, 2764 * LOCK_ENABLED_IRQ_*_READ may cause deadlocks too, so we need 2765 * to search excl | LOCK_USAGE_READ_MASK as well. 2766 */ 2767 excl = exclusive_bit(bit); 2768 excl_read = excl | LOCK_USAGE_READ_MASK; 2769 if (excl_mask & lock_flag(excl)) { 2770 *bitp = bit; 2771 *excl_bitp = excl; 2772 return 0; 2773 } else if (excl_mask & lock_flag(excl_read)) { 2774 *bitp = bit; 2775 *excl_bitp = excl_read; 2776 return 0; 2777 } 2778 } 2779 return -1; 2780 } 2781 2782 /* 2783 * Prove that the new dependency does not connect a hardirq-safe(-read) 2784 * lock with a hardirq-unsafe lock - to achieve this we search 2785 * the backwards-subgraph starting at <prev>, and the 2786 * forwards-subgraph starting at <next>: 2787 */ 2788 static int check_irq_usage(struct task_struct *curr, struct held_lock *prev, 2789 struct held_lock *next) 2790 { 2791 unsigned long usage_mask = 0, forward_mask, backward_mask; 2792 enum lock_usage_bit forward_bit = 0, backward_bit = 0; 2793 struct lock_list *target_entry1; 2794 struct lock_list *target_entry; 2795 struct lock_list this, that; 2796 enum bfs_result ret; 2797 2798 /* 2799 * Step 1: gather all hard/soft IRQs usages backward in an 2800 * accumulated usage mask. 2801 */ 2802 bfs_init_rootb(&this, prev); 2803 2804 ret = __bfs_backwards(&this, &usage_mask, usage_accumulate, usage_skip, NULL); 2805 if (bfs_error(ret)) { 2806 print_bfs_bug(ret); 2807 return 0; 2808 } 2809 2810 usage_mask &= LOCKF_USED_IN_IRQ_ALL; 2811 if (!usage_mask) 2812 return 1; 2813 2814 /* 2815 * Step 2: find exclusive uses forward that match the previous 2816 * backward accumulated mask. 2817 */ 2818 forward_mask = exclusive_mask(usage_mask); 2819 2820 bfs_init_root(&that, next); 2821 2822 ret = find_usage_forwards(&that, forward_mask, &target_entry1); 2823 if (bfs_error(ret)) { 2824 print_bfs_bug(ret); 2825 return 0; 2826 } 2827 if (ret == BFS_RNOMATCH) 2828 return 1; 2829 2830 /* 2831 * Step 3: we found a bad match! Now retrieve a lock from the backward 2832 * list whose usage mask matches the exclusive usage mask from the 2833 * lock found on the forward list. 2834 * 2835 * Note, we should only keep the LOCKF_ENABLED_IRQ_ALL bits, considering 2836 * the follow case: 2837 * 2838 * When trying to add A -> B to the graph, we find that there is a 2839 * hardirq-safe L, that L -> ... -> A, and another hardirq-unsafe M, 2840 * that B -> ... -> M. However M is **softirq-safe**, if we use exact 2841 * invert bits of M's usage_mask, we will find another lock N that is 2842 * **softirq-unsafe** and N -> ... -> A, however N -> .. -> M will not 2843 * cause a inversion deadlock. 2844 */ 2845 backward_mask = original_mask(target_entry1->class->usage_mask & LOCKF_ENABLED_IRQ_ALL); 2846 2847 ret = find_usage_backwards(&this, backward_mask, &target_entry); 2848 if (bfs_error(ret)) { 2849 print_bfs_bug(ret); 2850 return 0; 2851 } 2852 if (DEBUG_LOCKS_WARN_ON(ret == BFS_RNOMATCH)) 2853 return 1; 2854 2855 /* 2856 * Step 4: narrow down to a pair of incompatible usage bits 2857 * and report it. 2858 */ 2859 ret = find_exclusive_match(target_entry->class->usage_mask, 2860 target_entry1->class->usage_mask, 2861 &backward_bit, &forward_bit); 2862 if (DEBUG_LOCKS_WARN_ON(ret == -1)) 2863 return 1; 2864 2865 print_bad_irq_dependency(curr, &this, &that, 2866 target_entry, target_entry1, 2867 prev, next, 2868 backward_bit, forward_bit, 2869 state_name(backward_bit)); 2870 2871 return 0; 2872 } 2873 2874 #else 2875 2876 static inline int check_irq_usage(struct task_struct *curr, 2877 struct held_lock *prev, struct held_lock *next) 2878 { 2879 return 1; 2880 } 2881 2882 static inline bool usage_skip(struct lock_list *entry, void *mask) 2883 { 2884 return false; 2885 } 2886 2887 #endif /* CONFIG_TRACE_IRQFLAGS */ 2888 2889 #ifdef CONFIG_LOCKDEP_SMALL 2890 /* 2891 * Check that the dependency graph starting at <src> can lead to 2892 * <target> or not. If it can, <src> -> <target> dependency is already 2893 * in the graph. 2894 * 2895 * Return BFS_RMATCH if it does, or BFS_RNOMATCH if it does not, return BFS_E* if 2896 * any error appears in the bfs search. 2897 */ 2898 static noinline enum bfs_result 2899 check_redundant(struct held_lock *src, struct held_lock *target) 2900 { 2901 enum bfs_result ret; 2902 struct lock_list *target_entry; 2903 struct lock_list src_entry; 2904 2905 bfs_init_root(&src_entry, src); 2906 /* 2907 * Special setup for check_redundant(). 2908 * 2909 * To report redundant, we need to find a strong dependency path that 2910 * is equal to or stronger than <src> -> <target>. So if <src> is E, 2911 * we need to let __bfs() only search for a path starting at a -(E*)->, 2912 * we achieve this by setting the initial node's ->only_xr to true in 2913 * that case. And if <prev> is S, we set initial ->only_xr to false 2914 * because both -(S*)-> (equal) and -(E*)-> (stronger) are redundant. 2915 */ 2916 src_entry.only_xr = src->read == 0; 2917 2918 debug_atomic_inc(nr_redundant_checks); 2919 2920 /* 2921 * Note: we skip local_lock() for redundant check, because as the 2922 * comment in usage_skip(), A -> local_lock() -> B and A -> B are not 2923 * the same. 2924 */ 2925 ret = check_path(target, &src_entry, hlock_equal, usage_skip, &target_entry); 2926 2927 if (ret == BFS_RMATCH) 2928 debug_atomic_inc(nr_redundant); 2929 2930 return ret; 2931 } 2932 2933 #else 2934 2935 static inline enum bfs_result 2936 check_redundant(struct held_lock *src, struct held_lock *target) 2937 { 2938 return BFS_RNOMATCH; 2939 } 2940 2941 #endif 2942 2943 static void inc_chains(int irq_context) 2944 { 2945 if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT) 2946 nr_hardirq_chains++; 2947 else if (irq_context & LOCK_CHAIN_SOFTIRQ_CONTEXT) 2948 nr_softirq_chains++; 2949 else 2950 nr_process_chains++; 2951 } 2952 2953 static void dec_chains(int irq_context) 2954 { 2955 if (irq_context & LOCK_CHAIN_HARDIRQ_CONTEXT) 2956 nr_hardirq_chains--; 2957 else if (irq_context & LOCK_CHAIN_SOFTIRQ_CONTEXT) 2958 nr_softirq_chains--; 2959 else 2960 nr_process_chains--; 2961 } 2962 2963 static void 2964 print_deadlock_scenario(struct held_lock *nxt, struct held_lock *prv) 2965 { 2966 struct lock_class *next = hlock_class(nxt); 2967 struct lock_class *prev = hlock_class(prv); 2968 2969 printk(" Possible unsafe locking scenario:\n\n"); 2970 printk(" CPU0\n"); 2971 printk(" ----\n"); 2972 printk(" lock("); 2973 __print_lock_name(prv, prev); 2974 printk(KERN_CONT ");\n"); 2975 printk(" lock("); 2976 __print_lock_name(nxt, next); 2977 printk(KERN_CONT ");\n"); 2978 printk("\n *** DEADLOCK ***\n\n"); 2979 printk(" May be due to missing lock nesting notation\n\n"); 2980 } 2981 2982 static void 2983 print_deadlock_bug(struct task_struct *curr, struct held_lock *prev, 2984 struct held_lock *next) 2985 { 2986 struct lock_class *class = hlock_class(prev); 2987 2988 if (!debug_locks_off_graph_unlock() || debug_locks_silent) 2989 return; 2990 2991 pr_warn("\n"); 2992 pr_warn("============================================\n"); 2993 pr_warn("WARNING: possible recursive locking detected\n"); 2994 print_kernel_ident(); 2995 pr_warn("--------------------------------------------\n"); 2996 pr_warn("%s/%d is trying to acquire lock:\n", 2997 curr->comm, task_pid_nr(curr)); 2998 print_lock(next); 2999 pr_warn("\nbut task is already holding lock:\n"); 3000 print_lock(prev); 3001 3002 if (class->cmp_fn) { 3003 pr_warn("and the lock comparison function returns %i:\n", 3004 class->cmp_fn(prev->instance, next->instance)); 3005 } 3006 3007 pr_warn("\nother info that might help us debug this:\n"); 3008 print_deadlock_scenario(next, prev); 3009 lockdep_print_held_locks(curr); 3010 3011 pr_warn("\nstack backtrace:\n"); 3012 dump_stack(); 3013 } 3014 3015 /* 3016 * Check whether we are holding such a class already. 3017 * 3018 * (Note that this has to be done separately, because the graph cannot 3019 * detect such classes of deadlocks.) 3020 * 3021 * Returns: 0 on deadlock detected, 1 on OK, 2 if another lock with the same 3022 * lock class is held but nest_lock is also held, i.e. we rely on the 3023 * nest_lock to avoid the deadlock. 3024 */ 3025 static int 3026 check_deadlock(struct task_struct *curr, struct held_lock *next) 3027 { 3028 struct lock_class *class; 3029 struct held_lock *prev; 3030 struct held_lock *nest = NULL; 3031 int i; 3032 3033 for (i = 0; i < curr->lockdep_depth; i++) { 3034 prev = curr->held_locks + i; 3035 3036 if (prev->instance == next->nest_lock) 3037 nest = prev; 3038 3039 if (hlock_class(prev) != hlock_class(next)) 3040 continue; 3041 3042 /* 3043 * Allow read-after-read recursion of the same 3044 * lock class (i.e. read_lock(lock)+read_lock(lock)): 3045 */ 3046 if ((next->read == 2) && prev->read) 3047 continue; 3048 3049 class = hlock_class(prev); 3050 3051 if (class->cmp_fn && 3052 class->cmp_fn(prev->instance, next->instance) < 0) 3053 continue; 3054 3055 /* 3056 * We're holding the nest_lock, which serializes this lock's 3057 * nesting behaviour. 3058 */ 3059 if (nest) 3060 return 2; 3061 3062 print_deadlock_bug(curr, prev, next); 3063 return 0; 3064 } 3065 return 1; 3066 } 3067 3068 /* 3069 * There was a chain-cache miss, and we are about to add a new dependency 3070 * to a previous lock. We validate the following rules: 3071 * 3072 * - would the adding of the <prev> -> <next> dependency create a 3073 * circular dependency in the graph? [== circular deadlock] 3074 * 3075 * - does the new prev->next dependency connect any hardirq-safe lock 3076 * (in the full backwards-subgraph starting at <prev>) with any 3077 * hardirq-unsafe lock (in the full forwards-subgraph starting at 3078 * <next>)? [== illegal lock inversion with hardirq contexts] 3079 * 3080 * - does the new prev->next dependency connect any softirq-safe lock 3081 * (in the full backwards-subgraph starting at <prev>) with any 3082 * softirq-unsafe lock (in the full forwards-subgraph starting at 3083 * <next>)? [== illegal lock inversion with softirq contexts] 3084 * 3085 * any of these scenarios could lead to a deadlock. 3086 * 3087 * Then if all the validations pass, we add the forwards and backwards 3088 * dependency. 3089 */ 3090 static int 3091 check_prev_add(struct task_struct *curr, struct held_lock *prev, 3092 struct held_lock *next, u16 distance, 3093 struct lock_trace **const trace) 3094 { 3095 struct lock_list *entry; 3096 enum bfs_result ret; 3097 3098 if (!hlock_class(prev)->key || !hlock_class(next)->key) { 3099 /* 3100 * The warning statements below may trigger a use-after-free 3101 * of the class name. It is better to trigger a use-after free 3102 * and to have the class name most of the time instead of not 3103 * having the class name available. 3104 */ 3105 WARN_ONCE(!debug_locks_silent && !hlock_class(prev)->key, 3106 "Detected use-after-free of lock class %px/%s\n", 3107 hlock_class(prev), 3108 hlock_class(prev)->name); 3109 WARN_ONCE(!debug_locks_silent && !hlock_class(next)->key, 3110 "Detected use-after-free of lock class %px/%s\n", 3111 hlock_class(next), 3112 hlock_class(next)->name); 3113 return 2; 3114 } 3115 3116 if (prev->class_idx == next->class_idx) { 3117 struct lock_class *class = hlock_class(prev); 3118 3119 if (class->cmp_fn && 3120 class->cmp_fn(prev->instance, next->instance) < 0) 3121 return 2; 3122 } 3123 3124 /* 3125 * Prove that the new <prev> -> <next> dependency would not 3126 * create a circular dependency in the graph. (We do this by 3127 * a breadth-first search into the graph starting at <next>, 3128 * and check whether we can reach <prev>.) 3129 * 3130 * The search is limited by the size of the circular queue (i.e., 3131 * MAX_CIRCULAR_QUEUE_SIZE) which keeps track of a breadth of nodes 3132 * in the graph whose neighbours are to be checked. 3133 */ 3134 ret = check_noncircular(next, prev, trace); 3135 if (unlikely(bfs_error(ret) || ret == BFS_RMATCH)) 3136 return 0; 3137 3138 if (!check_irq_usage(curr, prev, next)) 3139 return 0; 3140 3141 /* 3142 * Is the <prev> -> <next> dependency already present? 3143 * 3144 * (this may occur even though this is a new chain: consider 3145 * e.g. the L1 -> L2 -> L3 -> L4 and the L5 -> L1 -> L2 -> L3 3146 * chains - the second one will be new, but L1 already has 3147 * L2 added to its dependency list, due to the first chain.) 3148 */ 3149 list_for_each_entry(entry, &hlock_class(prev)->locks_after, entry) { 3150 if (entry->class == hlock_class(next)) { 3151 if (distance == 1) 3152 entry->distance = 1; 3153 entry->dep |= calc_dep(prev, next); 3154 3155 /* 3156 * Also, update the reverse dependency in @next's 3157 * ->locks_before list. 3158 * 3159 * Here we reuse @entry as the cursor, which is fine 3160 * because we won't go to the next iteration of the 3161 * outer loop: 3162 * 3163 * For normal cases, we return in the inner loop. 3164 * 3165 * If we fail to return, we have inconsistency, i.e. 3166 * <prev>::locks_after contains <next> while 3167 * <next>::locks_before doesn't contain <prev>. In 3168 * that case, we return after the inner and indicate 3169 * something is wrong. 3170 */ 3171 list_for_each_entry(entry, &hlock_class(next)->locks_before, entry) { 3172 if (entry->class == hlock_class(prev)) { 3173 if (distance == 1) 3174 entry->distance = 1; 3175 entry->dep |= calc_depb(prev, next); 3176 return 1; 3177 } 3178 } 3179 3180 /* <prev> is not found in <next>::locks_before */ 3181 return 0; 3182 } 3183 } 3184 3185 /* 3186 * Is the <prev> -> <next> link redundant? 3187 */ 3188 ret = check_redundant(prev, next); 3189 if (bfs_error(ret)) 3190 return 0; 3191 else if (ret == BFS_RMATCH) 3192 return 2; 3193 3194 if (!*trace) { 3195 *trace = save_trace(); 3196 if (!*trace) 3197 return 0; 3198 } 3199 3200 /* 3201 * Ok, all validations passed, add the new lock 3202 * to the previous lock's dependency list: 3203 */ 3204 ret = add_lock_to_list(hlock_class(next), hlock_class(prev), 3205 &hlock_class(prev)->locks_after, distance, 3206 calc_dep(prev, next), *trace); 3207 3208 if (!ret) 3209 return 0; 3210 3211 ret = add_lock_to_list(hlock_class(prev), hlock_class(next), 3212 &hlock_class(next)->locks_before, distance, 3213 calc_depb(prev, next), *trace); 3214 if (!ret) 3215 return 0; 3216 3217 return 2; 3218 } 3219 3220 /* 3221 * Add the dependency to all directly-previous locks that are 'relevant'. 3222 * The ones that are relevant are (in increasing distance from curr): 3223 * all consecutive trylock entries and the final non-trylock entry - or 3224 * the end of this context's lock-chain - whichever comes first. 3225 */ 3226 static int 3227 check_prevs_add(struct task_struct *curr, struct held_lock *next) 3228 { 3229 struct lock_trace *trace = NULL; 3230 int depth = curr->lockdep_depth; 3231 struct held_lock *hlock; 3232 3233 /* 3234 * Debugging checks. 3235 * 3236 * Depth must not be zero for a non-head lock: 3237 */ 3238 if (!depth) 3239 goto out_bug; 3240 /* 3241 * At least two relevant locks must exist for this 3242 * to be a head: 3243 */ 3244 if (curr->held_locks[depth].irq_context != 3245 curr->held_locks[depth-1].irq_context) 3246 goto out_bug; 3247 3248 for (;;) { 3249 u16 distance = curr->lockdep_depth - depth + 1; 3250 hlock = curr->held_locks + depth - 1; 3251 3252 if (hlock->check) { 3253 int ret = check_prev_add(curr, hlock, next, distance, &trace); 3254 if (!ret) 3255 return 0; 3256 3257 /* 3258 * Stop after the first non-trylock entry, 3259 * as non-trylock entries have added their 3260 * own direct dependencies already, so this 3261 * lock is connected to them indirectly: 3262 */ 3263 if (!hlock->trylock) 3264 break; 3265 } 3266 3267 depth--; 3268 /* 3269 * End of lock-stack? 3270 */ 3271 if (!depth) 3272 break; 3273 /* 3274 * Stop the search if we cross into another context: 3275 */ 3276 if (curr->held_locks[depth].irq_context != 3277 curr->held_locks[depth-1].irq_context) 3278 break; 3279 } 3280 return 1; 3281 out_bug: 3282 if (!debug_locks_off_graph_unlock()) 3283 return 0; 3284 3285 /* 3286 * Clearly we all shouldn't be here, but since we made it we 3287 * can reliable say we messed up our state. See the above two 3288 * gotos for reasons why we could possibly end up here. 3289 */ 3290 WARN_ON(1); 3291 3292 return 0; 3293 } 3294 3295 struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS]; 3296 static DECLARE_BITMAP(lock_chains_in_use, MAX_LOCKDEP_CHAINS); 3297 static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS]; 3298 unsigned long nr_zapped_lock_chains; 3299 unsigned int nr_free_chain_hlocks; /* Free chain_hlocks in buckets */ 3300 unsigned int nr_lost_chain_hlocks; /* Lost chain_hlocks */ 3301 unsigned int nr_large_chain_blocks; /* size > MAX_CHAIN_BUCKETS */ 3302 3303 /* 3304 * The first 2 chain_hlocks entries in the chain block in the bucket 3305 * list contains the following meta data: 3306 * 3307 * entry[0]: 3308 * Bit 15 - always set to 1 (it is not a class index) 3309 * Bits 0-14 - upper 15 bits of the next block index 3310 * entry[1] - lower 16 bits of next block index 3311 * 3312 * A next block index of all 1 bits means it is the end of the list. 3313 * 3314 * On the unsized bucket (bucket-0), the 3rd and 4th entries contain 3315 * the chain block size: 3316 * 3317 * entry[2] - upper 16 bits of the chain block size 3318 * entry[3] - lower 16 bits of the chain block size 3319 */ 3320 #define MAX_CHAIN_BUCKETS 16 3321 #define CHAIN_BLK_FLAG (1U << 15) 3322 #define CHAIN_BLK_LIST_END 0xFFFFU 3323 3324 static int chain_block_buckets[MAX_CHAIN_BUCKETS]; 3325 3326 static inline int size_to_bucket(int size) 3327 { 3328 if (size > MAX_CHAIN_BUCKETS) 3329 return 0; 3330 3331 return size - 1; 3332 } 3333 3334 /* 3335 * Iterate all the chain blocks in a bucket. 3336 */ 3337 #define for_each_chain_block(bucket, prev, curr) \ 3338 for ((prev) = -1, (curr) = chain_block_buckets[bucket]; \ 3339 (curr) >= 0; \ 3340 (prev) = (curr), (curr) = chain_block_next(curr)) 3341 3342 /* 3343 * next block or -1 3344 */ 3345 static inline int chain_block_next(int offset) 3346 { 3347 int next = chain_hlocks[offset]; 3348 3349 WARN_ON_ONCE(!(next & CHAIN_BLK_FLAG)); 3350 3351 if (next == CHAIN_BLK_LIST_END) 3352 return -1; 3353 3354 next &= ~CHAIN_BLK_FLAG; 3355 next <<= 16; 3356 next |= chain_hlocks[offset + 1]; 3357 3358 return next; 3359 } 3360 3361 /* 3362 * bucket-0 only 3363 */ 3364 static inline int chain_block_size(int offset) 3365 { 3366 return (chain_hlocks[offset + 2] << 16) | chain_hlocks[offset + 3]; 3367 } 3368 3369 static inline void init_chain_block(int offset, int next, int bucket, int size) 3370 { 3371 chain_hlocks[offset] = (next >> 16) | CHAIN_BLK_FLAG; 3372 chain_hlocks[offset + 1] = (u16)next; 3373 3374 if (size && !bucket) { 3375 chain_hlocks[offset + 2] = size >> 16; 3376 chain_hlocks[offset + 3] = (u16)size; 3377 } 3378 } 3379 3380 static inline void add_chain_block(int offset, int size) 3381 { 3382 int bucket = size_to_bucket(size); 3383 int next = chain_block_buckets[bucket]; 3384 int prev, curr; 3385 3386 if (unlikely(size < 2)) { 3387 /* 3388 * We can't store single entries on the freelist. Leak them. 3389 * 3390 * One possible way out would be to uniquely mark them, other 3391 * than with CHAIN_BLK_FLAG, such that we can recover them when 3392 * the block before it is re-added. 3393 */ 3394 if (size) 3395 nr_lost_chain_hlocks++; 3396 return; 3397 } 3398 3399 nr_free_chain_hlocks += size; 3400 if (!bucket) { 3401 nr_large_chain_blocks++; 3402 3403 /* 3404 * Variable sized, sort large to small. 3405 */ 3406 for_each_chain_block(0, prev, curr) { 3407 if (size >= chain_block_size(curr)) 3408 break; 3409 } 3410 init_chain_block(offset, curr, 0, size); 3411 if (prev < 0) 3412 chain_block_buckets[0] = offset; 3413 else 3414 init_chain_block(prev, offset, 0, 0); 3415 return; 3416 } 3417 /* 3418 * Fixed size, add to head. 3419 */ 3420 init_chain_block(offset, next, bucket, size); 3421 chain_block_buckets[bucket] = offset; 3422 } 3423 3424 /* 3425 * Only the first block in the list can be deleted. 3426 * 3427 * For the variable size bucket[0], the first block (the largest one) is 3428 * returned, broken up and put back into the pool. So if a chain block of 3429 * length > MAX_CHAIN_BUCKETS is ever used and zapped, it will just be 3430 * queued up after the primordial chain block and never be used until the 3431 * hlock entries in the primordial chain block is almost used up. That 3432 * causes fragmentation and reduce allocation efficiency. That can be 3433 * monitored by looking at the "large chain blocks" number in lockdep_stats. 3434 */ 3435 static inline void del_chain_block(int bucket, int size, int next) 3436 { 3437 nr_free_chain_hlocks -= size; 3438 chain_block_buckets[bucket] = next; 3439 3440 if (!bucket) 3441 nr_large_chain_blocks--; 3442 } 3443 3444 static void init_chain_block_buckets(void) 3445 { 3446 int i; 3447 3448 for (i = 0; i < MAX_CHAIN_BUCKETS; i++) 3449 chain_block_buckets[i] = -1; 3450 3451 add_chain_block(0, ARRAY_SIZE(chain_hlocks)); 3452 } 3453 3454 /* 3455 * Return offset of a chain block of the right size or -1 if not found. 3456 * 3457 * Fairly simple worst-fit allocator with the addition of a number of size 3458 * specific free lists. 3459 */ 3460 static int alloc_chain_hlocks(int req) 3461 { 3462 int bucket, curr, size; 3463 3464 /* 3465 * We rely on the MSB to act as an escape bit to denote freelist 3466 * pointers. Make sure this bit isn't set in 'normal' class_idx usage. 3467 */ 3468 BUILD_BUG_ON((MAX_LOCKDEP_KEYS-1) & CHAIN_BLK_FLAG); 3469 3470 init_data_structures_once(); 3471 3472 if (nr_free_chain_hlocks < req) 3473 return -1; 3474 3475 /* 3476 * We require a minimum of 2 (u16) entries to encode a freelist 3477 * 'pointer'. 3478 */ 3479 req = max(req, 2); 3480 bucket = size_to_bucket(req); 3481 curr = chain_block_buckets[bucket]; 3482 3483 if (bucket) { 3484 if (curr >= 0) { 3485 del_chain_block(bucket, req, chain_block_next(curr)); 3486 return curr; 3487 } 3488 /* Try bucket 0 */ 3489 curr = chain_block_buckets[0]; 3490 } 3491 3492 /* 3493 * The variable sized freelist is sorted by size; the first entry is 3494 * the largest. Use it if it fits. 3495 */ 3496 if (curr >= 0) { 3497 size = chain_block_size(curr); 3498 if (likely(size >= req)) { 3499 del_chain_block(0, size, chain_block_next(curr)); 3500 add_chain_block(curr + req, size - req); 3501 return curr; 3502 } 3503 } 3504 3505 /* 3506 * Last resort, split a block in a larger sized bucket. 3507 */ 3508 for (size = MAX_CHAIN_BUCKETS; size > req; size--) { 3509 bucket = size_to_bucket(size); 3510 curr = chain_block_buckets[bucket]; 3511 if (curr < 0) 3512 continue; 3513 3514 del_chain_block(bucket, size, chain_block_next(curr)); 3515 add_chain_block(curr + req, size - req); 3516 return curr; 3517 } 3518 3519 return -1; 3520 } 3521 3522 static inline void free_chain_hlocks(int base, int size) 3523 { 3524 add_chain_block(base, max(size, 2)); 3525 } 3526 3527 struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i) 3528 { 3529 u16 chain_hlock = chain_hlocks[chain->base + i]; 3530 unsigned int class_idx = chain_hlock_class_idx(chain_hlock); 3531 3532 return lock_classes + class_idx; 3533 } 3534 3535 /* 3536 * Returns the index of the first held_lock of the current chain 3537 */ 3538 static inline int get_first_held_lock(struct task_struct *curr, 3539 struct held_lock *hlock) 3540 { 3541 int i; 3542 struct held_lock *hlock_curr; 3543 3544 for (i = curr->lockdep_depth - 1; i >= 0; i--) { 3545 hlock_curr = curr->held_locks + i; 3546 if (hlock_curr->irq_context != hlock->irq_context) 3547 break; 3548 3549 } 3550 3551 return ++i; 3552 } 3553 3554 #ifdef CONFIG_DEBUG_LOCKDEP 3555 /* 3556 * Returns the next chain_key iteration 3557 */ 3558 static u64 print_chain_key_iteration(u16 hlock_id, u64 chain_key) 3559 { 3560 u64 new_chain_key = iterate_chain_key(chain_key, hlock_id); 3561 3562 printk(" hlock_id:%d -> chain_key:%016Lx", 3563 (unsigned int)hlock_id, 3564 (unsigned long long)new_chain_key); 3565 return new_chain_key; 3566 } 3567 3568 static void 3569 print_chain_keys_held_locks(struct task_struct *curr, struct held_lock *hlock_next) 3570 { 3571 struct held_lock *hlock; 3572 u64 chain_key = INITIAL_CHAIN_KEY; 3573 int depth = curr->lockdep_depth; 3574 int i = get_first_held_lock(curr, hlock_next); 3575 3576 printk("depth: %u (irq_context %u)\n", depth - i + 1, 3577 hlock_next->irq_context); 3578 for (; i < depth; i++) { 3579 hlock = curr->held_locks + i; 3580 chain_key = print_chain_key_iteration(hlock_id(hlock), chain_key); 3581 3582 print_lock(hlock); 3583 } 3584 3585 print_chain_key_iteration(hlock_id(hlock_next), chain_key); 3586 print_lock(hlock_next); 3587 } 3588 3589 static void print_chain_keys_chain(struct lock_chain *chain) 3590 { 3591 int i; 3592 u64 chain_key = INITIAL_CHAIN_KEY; 3593 u16 hlock_id; 3594 3595 printk("depth: %u\n", chain->depth); 3596 for (i = 0; i < chain->depth; i++) { 3597 hlock_id = chain_hlocks[chain->base + i]; 3598 chain_key = print_chain_key_iteration(hlock_id, chain_key); 3599 3600 print_lock_name(NULL, lock_classes + chain_hlock_class_idx(hlock_id)); 3601 printk("\n"); 3602 } 3603 } 3604 3605 static void print_collision(struct task_struct *curr, 3606 struct held_lock *hlock_next, 3607 struct lock_chain *chain) 3608 { 3609 pr_warn("\n"); 3610 pr_warn("============================\n"); 3611 pr_warn("WARNING: chain_key collision\n"); 3612 print_kernel_ident(); 3613 pr_warn("----------------------------\n"); 3614 pr_warn("%s/%d: ", current->comm, task_pid_nr(current)); 3615 pr_warn("Hash chain already cached but the contents don't match!\n"); 3616 3617 pr_warn("Held locks:"); 3618 print_chain_keys_held_locks(curr, hlock_next); 3619 3620 pr_warn("Locks in cached chain:"); 3621 print_chain_keys_chain(chain); 3622 3623 pr_warn("\nstack backtrace:\n"); 3624 dump_stack(); 3625 } 3626 #endif 3627 3628 /* 3629 * Checks whether the chain and the current held locks are consistent 3630 * in depth and also in content. If they are not it most likely means 3631 * that there was a collision during the calculation of the chain_key. 3632 * Returns: 0 not passed, 1 passed 3633 */ 3634 static int check_no_collision(struct task_struct *curr, 3635 struct held_lock *hlock, 3636 struct lock_chain *chain) 3637 { 3638 #ifdef CONFIG_DEBUG_LOCKDEP 3639 int i, j, id; 3640 3641 i = get_first_held_lock(curr, hlock); 3642 3643 if (DEBUG_LOCKS_WARN_ON(chain->depth != curr->lockdep_depth - (i - 1))) { 3644 print_collision(curr, hlock, chain); 3645 return 0; 3646 } 3647 3648 for (j = 0; j < chain->depth - 1; j++, i++) { 3649 id = hlock_id(&curr->held_locks[i]); 3650 3651 if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id)) { 3652 print_collision(curr, hlock, chain); 3653 return 0; 3654 } 3655 } 3656 #endif 3657 return 1; 3658 } 3659 3660 /* 3661 * Given an index that is >= -1, return the index of the next lock chain. 3662 * Return -2 if there is no next lock chain. 3663 */ 3664 long lockdep_next_lockchain(long i) 3665 { 3666 i = find_next_bit(lock_chains_in_use, ARRAY_SIZE(lock_chains), i + 1); 3667 return i < ARRAY_SIZE(lock_chains) ? i : -2; 3668 } 3669 3670 unsigned long lock_chain_count(void) 3671 { 3672 return bitmap_weight(lock_chains_in_use, ARRAY_SIZE(lock_chains)); 3673 } 3674 3675 /* Must be called with the graph lock held. */ 3676 static struct lock_chain *alloc_lock_chain(void) 3677 { 3678 int idx = find_first_zero_bit(lock_chains_in_use, 3679 ARRAY_SIZE(lock_chains)); 3680 3681 if (unlikely(idx >= ARRAY_SIZE(lock_chains))) 3682 return NULL; 3683 __set_bit(idx, lock_chains_in_use); 3684 return lock_chains + idx; 3685 } 3686 3687 /* 3688 * Adds a dependency chain into chain hashtable. And must be called with 3689 * graph_lock held. 3690 * 3691 * Return 0 if fail, and graph_lock is released. 3692 * Return 1 if succeed, with graph_lock held. 3693 */ 3694 static inline int add_chain_cache(struct task_struct *curr, 3695 struct held_lock *hlock, 3696 u64 chain_key) 3697 { 3698 struct hlist_head *hash_head = chainhashentry(chain_key); 3699 struct lock_chain *chain; 3700 int i, j; 3701 3702 /* 3703 * The caller must hold the graph lock, ensure we've got IRQs 3704 * disabled to make this an IRQ-safe lock.. for recursion reasons 3705 * lockdep won't complain about its own locking errors. 3706 */ 3707 if (lockdep_assert_locked()) 3708 return 0; 3709 3710 chain = alloc_lock_chain(); 3711 if (!chain) { 3712 if (!debug_locks_off_graph_unlock()) 3713 return 0; 3714 3715 print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!"); 3716 dump_stack(); 3717 return 0; 3718 } 3719 chain->chain_key = chain_key; 3720 chain->irq_context = hlock->irq_context; 3721 i = get_first_held_lock(curr, hlock); 3722 chain->depth = curr->lockdep_depth + 1 - i; 3723 3724 BUILD_BUG_ON((1UL << 24) <= ARRAY_SIZE(chain_hlocks)); 3725 BUILD_BUG_ON((1UL << 6) <= ARRAY_SIZE(curr->held_locks)); 3726 BUILD_BUG_ON((1UL << 8*sizeof(chain_hlocks[0])) <= ARRAY_SIZE(lock_classes)); 3727 3728 j = alloc_chain_hlocks(chain->depth); 3729 if (j < 0) { 3730 if (!debug_locks_off_graph_unlock()) 3731 return 0; 3732 3733 print_lockdep_off("BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!"); 3734 dump_stack(); 3735 return 0; 3736 } 3737 3738 chain->base = j; 3739 for (j = 0; j < chain->depth - 1; j++, i++) { 3740 int lock_id = hlock_id(curr->held_locks + i); 3741 3742 chain_hlocks[chain->base + j] = lock_id; 3743 } 3744 chain_hlocks[chain->base + j] = hlock_id(hlock); 3745 hlist_add_head_rcu(&chain->entry, hash_head); 3746 debug_atomic_inc(chain_lookup_misses); 3747 inc_chains(chain->irq_context); 3748 3749 return 1; 3750 } 3751 3752 /* 3753 * Look up a dependency chain. Must be called with either the graph lock or 3754 * the RCU read lock held. 3755 */ 3756 static inline struct lock_chain *lookup_chain_cache(u64 chain_key) 3757 { 3758 struct hlist_head *hash_head = chainhashentry(chain_key); 3759 struct lock_chain *chain; 3760 3761 hlist_for_each_entry_rcu(chain, hash_head, entry) { 3762 if (READ_ONCE(chain->chain_key) == chain_key) { 3763 debug_atomic_inc(chain_lookup_hits); 3764 return chain; 3765 } 3766 } 3767 return NULL; 3768 } 3769 3770 /* 3771 * If the key is not present yet in dependency chain cache then 3772 * add it and return 1 - in this case the new dependency chain is 3773 * validated. If the key is already hashed, return 0. 3774 * (On return with 1 graph_lock is held.) 3775 */ 3776 static inline int lookup_chain_cache_add(struct task_struct *curr, 3777 struct held_lock *hlock, 3778 u64 chain_key) 3779 { 3780 struct lock_class *class = hlock_class(hlock); 3781 struct lock_chain *chain = lookup_chain_cache(chain_key); 3782 3783 if (chain) { 3784 cache_hit: 3785 if (!check_no_collision(curr, hlock, chain)) 3786 return 0; 3787 3788 if (very_verbose(class)) { 3789 printk("\nhash chain already cached, key: " 3790 "%016Lx tail class: [%px] %s\n", 3791 (unsigned long long)chain_key, 3792 class->key, class->name); 3793 } 3794 3795 return 0; 3796 } 3797 3798 if (very_verbose(class)) { 3799 printk("\nnew hash chain, key: %016Lx tail class: [%px] %s\n", 3800 (unsigned long long)chain_key, class->key, class->name); 3801 } 3802 3803 if (!graph_lock()) 3804 return 0; 3805 3806 /* 3807 * We have to walk the chain again locked - to avoid duplicates: 3808 */ 3809 chain = lookup_chain_cache(chain_key); 3810 if (chain) { 3811 graph_unlock(); 3812 goto cache_hit; 3813 } 3814 3815 if (!add_chain_cache(curr, hlock, chain_key)) 3816 return 0; 3817 3818 return 1; 3819 } 3820 3821 static int validate_chain(struct task_struct *curr, 3822 struct held_lock *hlock, 3823 int chain_head, u64 chain_key) 3824 { 3825 /* 3826 * Trylock needs to maintain the stack of held locks, but it 3827 * does not add new dependencies, because trylock can be done 3828 * in any order. 3829 * 3830 * We look up the chain_key and do the O(N^2) check and update of 3831 * the dependencies only if this is a new dependency chain. 3832 * (If lookup_chain_cache_add() return with 1 it acquires 3833 * graph_lock for us) 3834 */ 3835 if (!hlock->trylock && hlock->check && 3836 lookup_chain_cache_add(curr, hlock, chain_key)) { 3837 /* 3838 * Check whether last held lock: 3839 * 3840 * - is irq-safe, if this lock is irq-unsafe 3841 * - is softirq-safe, if this lock is hardirq-unsafe 3842 * 3843 * And check whether the new lock's dependency graph 3844 * could lead back to the previous lock: 3845 * 3846 * - within the current held-lock stack 3847 * - across our accumulated lock dependency records 3848 * 3849 * any of these scenarios could lead to a deadlock. 3850 */ 3851 /* 3852 * The simple case: does the current hold the same lock 3853 * already? 3854 */ 3855 int ret = check_deadlock(curr, hlock); 3856 3857 if (!ret) 3858 return 0; 3859 /* 3860 * Add dependency only if this lock is not the head 3861 * of the chain, and if the new lock introduces no more 3862 * lock dependency (because we already hold a lock with the 3863 * same lock class) nor deadlock (because the nest_lock 3864 * serializes nesting locks), see the comments for 3865 * check_deadlock(). 3866 */ 3867 if (!chain_head && ret != 2) { 3868 if (!check_prevs_add(curr, hlock)) 3869 return 0; 3870 } 3871 3872 graph_unlock(); 3873 } else { 3874 /* after lookup_chain_cache_add(): */ 3875 if (unlikely(!debug_locks)) 3876 return 0; 3877 } 3878 3879 return 1; 3880 } 3881 #else 3882 static inline int validate_chain(struct task_struct *curr, 3883 struct held_lock *hlock, 3884 int chain_head, u64 chain_key) 3885 { 3886 return 1; 3887 } 3888 3889 static void init_chain_block_buckets(void) { } 3890 #endif /* CONFIG_PROVE_LOCKING */ 3891 3892 /* 3893 * We are building curr_chain_key incrementally, so double-check 3894 * it from scratch, to make sure that it's done correctly: 3895 */ 3896 static void check_chain_key(struct task_struct *curr) 3897 { 3898 #ifdef CONFIG_DEBUG_LOCKDEP 3899 struct held_lock *hlock, *prev_hlock = NULL; 3900 unsigned int i; 3901 u64 chain_key = INITIAL_CHAIN_KEY; 3902 3903 for (i = 0; i < curr->lockdep_depth; i++) { 3904 hlock = curr->held_locks + i; 3905 if (chain_key != hlock->prev_chain_key) { 3906 debug_locks_off(); 3907 /* 3908 * We got mighty confused, our chain keys don't match 3909 * with what we expect, someone trample on our task state? 3910 */ 3911 WARN(1, "hm#1, depth: %u [%u], %016Lx != %016Lx\n", 3912 curr->lockdep_depth, i, 3913 (unsigned long long)chain_key, 3914 (unsigned long long)hlock->prev_chain_key); 3915 return; 3916 } 3917 3918 /* 3919 * hlock->class_idx can't go beyond MAX_LOCKDEP_KEYS, but is 3920 * it registered lock class index? 3921 */ 3922 if (DEBUG_LOCKS_WARN_ON(!test_bit(hlock->class_idx, lock_classes_in_use))) 3923 return; 3924 3925 if (prev_hlock && (prev_hlock->irq_context != 3926 hlock->irq_context)) 3927 chain_key = INITIAL_CHAIN_KEY; 3928 chain_key = iterate_chain_key(chain_key, hlock_id(hlock)); 3929 prev_hlock = hlock; 3930 } 3931 if (chain_key != curr->curr_chain_key) { 3932 debug_locks_off(); 3933 /* 3934 * More smoking hash instead of calculating it, damn see these 3935 * numbers float.. I bet that a pink elephant stepped on my memory. 3936 */ 3937 WARN(1, "hm#2, depth: %u [%u], %016Lx != %016Lx\n", 3938 curr->lockdep_depth, i, 3939 (unsigned long long)chain_key, 3940 (unsigned long long)curr->curr_chain_key); 3941 } 3942 #endif 3943 } 3944 3945 #ifdef CONFIG_PROVE_LOCKING 3946 static int mark_lock(struct task_struct *curr, struct held_lock *this, 3947 enum lock_usage_bit new_bit); 3948 3949 static void print_usage_bug_scenario(struct held_lock *lock) 3950 { 3951 struct lock_class *class = hlock_class(lock); 3952 3953 printk(" Possible unsafe locking scenario:\n\n"); 3954 printk(" CPU0\n"); 3955 printk(" ----\n"); 3956 printk(" lock("); 3957 __print_lock_name(lock, class); 3958 printk(KERN_CONT ");\n"); 3959 printk(" <Interrupt>\n"); 3960 printk(" lock("); 3961 __print_lock_name(lock, class); 3962 printk(KERN_CONT ");\n"); 3963 printk("\n *** DEADLOCK ***\n\n"); 3964 } 3965 3966 static void 3967 print_usage_bug(struct task_struct *curr, struct held_lock *this, 3968 enum lock_usage_bit prev_bit, enum lock_usage_bit new_bit) 3969 { 3970 if (!debug_locks_off() || debug_locks_silent) 3971 return; 3972 3973 pr_warn("\n"); 3974 pr_warn("================================\n"); 3975 pr_warn("WARNING: inconsistent lock state\n"); 3976 print_kernel_ident(); 3977 pr_warn("--------------------------------\n"); 3978 3979 pr_warn("inconsistent {%s} -> {%s} usage.\n", 3980 usage_str[prev_bit], usage_str[new_bit]); 3981 3982 pr_warn("%s/%d [HC%u[%lu]:SC%u[%lu]:HE%u:SE%u] takes:\n", 3983 curr->comm, task_pid_nr(curr), 3984 lockdep_hardirq_context(), hardirq_count() >> HARDIRQ_SHIFT, 3985 lockdep_softirq_context(curr), softirq_count() >> SOFTIRQ_SHIFT, 3986 lockdep_hardirqs_enabled(), 3987 lockdep_softirqs_enabled(curr)); 3988 print_lock(this); 3989 3990 pr_warn("{%s} state was registered at:\n", usage_str[prev_bit]); 3991 print_lock_trace(hlock_class(this)->usage_traces[prev_bit], 1); 3992 3993 print_irqtrace_events(curr); 3994 pr_warn("\nother info that might help us debug this:\n"); 3995 print_usage_bug_scenario(this); 3996 3997 lockdep_print_held_locks(curr); 3998 3999 pr_warn("\nstack backtrace:\n"); 4000 dump_stack(); 4001 } 4002 4003 /* 4004 * Print out an error if an invalid bit is set: 4005 */ 4006 static inline int 4007 valid_state(struct task_struct *curr, struct held_lock *this, 4008 enum lock_usage_bit new_bit, enum lock_usage_bit bad_bit) 4009 { 4010 if (unlikely(hlock_class(this)->usage_mask & (1 << bad_bit))) { 4011 graph_unlock(); 4012 print_usage_bug(curr, this, bad_bit, new_bit); 4013 return 0; 4014 } 4015 return 1; 4016 } 4017 4018 4019 /* 4020 * print irq inversion bug: 4021 */ 4022 static void 4023 print_irq_inversion_bug(struct task_struct *curr, 4024 struct lock_list *root, struct lock_list *other, 4025 struct held_lock *this, int forwards, 4026 const char *irqclass) 4027 { 4028 struct lock_list *entry = other; 4029 struct lock_list *middle = NULL; 4030 int depth; 4031 4032 if (!debug_locks_off_graph_unlock() || debug_locks_silent) 4033 return; 4034 4035 pr_warn("\n"); 4036 pr_warn("========================================================\n"); 4037 pr_warn("WARNING: possible irq lock inversion dependency detected\n"); 4038 print_kernel_ident(); 4039 pr_warn("--------------------------------------------------------\n"); 4040 pr_warn("%s/%d just changed the state of lock:\n", 4041 curr->comm, task_pid_nr(curr)); 4042 print_lock(this); 4043 if (forwards) 4044 pr_warn("but this lock took another, %s-unsafe lock in the past:\n", irqclass); 4045 else 4046 pr_warn("but this lock was taken by another, %s-safe lock in the past:\n", irqclass); 4047 print_lock_name(NULL, other->class); 4048 pr_warn("\n\nand interrupts could create inverse lock ordering between them.\n\n"); 4049 4050 pr_warn("\nother info that might help us debug this:\n"); 4051 4052 /* Find a middle lock (if one exists) */ 4053 depth = get_lock_depth(other); 4054 do { 4055 if (depth == 0 && (entry != root)) { 4056 pr_warn("lockdep:%s bad path found in chain graph\n", __func__); 4057 break; 4058 } 4059 middle = entry; 4060 entry = get_lock_parent(entry); 4061 depth--; 4062 } while (entry && entry != root && (depth >= 0)); 4063 if (forwards) 4064 print_irq_lock_scenario(root, other, 4065 middle ? middle->class : root->class, other->class); 4066 else 4067 print_irq_lock_scenario(other, root, 4068 middle ? middle->class : other->class, root->class); 4069 4070 lockdep_print_held_locks(curr); 4071 4072 pr_warn("\nthe shortest dependencies between 2nd lock and 1st lock:\n"); 4073 root->trace = save_trace(); 4074 if (!root->trace) 4075 return; 4076 print_shortest_lock_dependencies(other, root); 4077 4078 pr_warn("\nstack backtrace:\n"); 4079 dump_stack(); 4080 } 4081 4082 /* 4083 * Prove that in the forwards-direction subgraph starting at <this> 4084 * there is no lock matching <mask>: 4085 */ 4086 static int 4087 check_usage_forwards(struct task_struct *curr, struct held_lock *this, 4088 enum lock_usage_bit bit) 4089 { 4090 enum bfs_result ret; 4091 struct lock_list root; 4092 struct lock_list *target_entry; 4093 enum lock_usage_bit read_bit = bit + LOCK_USAGE_READ_MASK; 4094 unsigned usage_mask = lock_flag(bit) | lock_flag(read_bit); 4095 4096 bfs_init_root(&root, this); 4097 ret = find_usage_forwards(&root, usage_mask, &target_entry); 4098 if (bfs_error(ret)) { 4099 print_bfs_bug(ret); 4100 return 0; 4101 } 4102 if (ret == BFS_RNOMATCH) 4103 return 1; 4104 4105 /* Check whether write or read usage is the match */ 4106 if (target_entry->class->usage_mask & lock_flag(bit)) { 4107 print_irq_inversion_bug(curr, &root, target_entry, 4108 this, 1, state_name(bit)); 4109 } else { 4110 print_irq_inversion_bug(curr, &root, target_entry, 4111 this, 1, state_name(read_bit)); 4112 } 4113 4114 return 0; 4115 } 4116 4117 /* 4118 * Prove that in the backwards-direction subgraph starting at <this> 4119 * there is no lock matching <mask>: 4120 */ 4121 static int 4122 check_usage_backwards(struct task_struct *curr, struct held_lock *this, 4123 enum lock_usage_bit bit) 4124 { 4125 enum bfs_result ret; 4126 struct lock_list root; 4127 struct lock_list *target_entry; 4128 enum lock_usage_bit read_bit = bit + LOCK_USAGE_READ_MASK; 4129 unsigned usage_mask = lock_flag(bit) | lock_flag(read_bit); 4130 4131 bfs_init_rootb(&root, this); 4132 ret = find_usage_backwards(&root, usage_mask, &target_entry); 4133 if (bfs_error(ret)) { 4134 print_bfs_bug(ret); 4135 return 0; 4136 } 4137 if (ret == BFS_RNOMATCH) 4138 return 1; 4139 4140 /* Check whether write or read usage is the match */ 4141 if (target_entry->class->usage_mask & lock_flag(bit)) { 4142 print_irq_inversion_bug(curr, &root, target_entry, 4143 this, 0, state_name(bit)); 4144 } else { 4145 print_irq_inversion_bug(curr, &root, target_entry, 4146 this, 0, state_name(read_bit)); 4147 } 4148 4149 return 0; 4150 } 4151 4152 void print_irqtrace_events(struct task_struct *curr) 4153 { 4154 const struct irqtrace_events *trace = &curr->irqtrace; 4155 4156 printk("irq event stamp: %u\n", trace->irq_events); 4157 printk("hardirqs last enabled at (%u): [<%px>] %pS\n", 4158 trace->hardirq_enable_event, (void *)trace->hardirq_enable_ip, 4159 (void *)trace->hardirq_enable_ip); 4160 printk("hardirqs last disabled at (%u): [<%px>] %pS\n", 4161 trace->hardirq_disable_event, (void *)trace->hardirq_disable_ip, 4162 (void *)trace->hardirq_disable_ip); 4163 printk("softirqs last enabled at (%u): [<%px>] %pS\n", 4164 trace->softirq_enable_event, (void *)trace->softirq_enable_ip, 4165 (void *)trace->softirq_enable_ip); 4166 printk("softirqs last disabled at (%u): [<%px>] %pS\n", 4167 trace->softirq_disable_event, (void *)trace->softirq_disable_ip, 4168 (void *)trace->softirq_disable_ip); 4169 } 4170 4171 static int HARDIRQ_verbose(struct lock_class *class) 4172 { 4173 #if HARDIRQ_VERBOSE 4174 return class_filter(class); 4175 #endif 4176 return 0; 4177 } 4178 4179 static int SOFTIRQ_verbose(struct lock_class *class) 4180 { 4181 #if SOFTIRQ_VERBOSE 4182 return class_filter(class); 4183 #endif 4184 return 0; 4185 } 4186 4187 static int (*state_verbose_f[])(struct lock_class *class) = { 4188 #define LOCKDEP_STATE(__STATE) \ 4189 __STATE##_verbose, 4190 #include "lockdep_states.h" 4191 #undef LOCKDEP_STATE 4192 }; 4193 4194 static inline int state_verbose(enum lock_usage_bit bit, 4195 struct lock_class *class) 4196 { 4197 return state_verbose_f[bit >> LOCK_USAGE_DIR_MASK](class); 4198 } 4199 4200 typedef int (*check_usage_f)(struct task_struct *, struct held_lock *, 4201 enum lock_usage_bit bit, const char *name); 4202 4203 static int 4204 mark_lock_irq(struct task_struct *curr, struct held_lock *this, 4205 enum lock_usage_bit new_bit) 4206 { 4207 int excl_bit = exclusive_bit(new_bit); 4208 int read = new_bit & LOCK_USAGE_READ_MASK; 4209 int dir = new_bit & LOCK_USAGE_DIR_MASK; 4210 4211 /* 4212 * Validate that this particular lock does not have conflicting 4213 * usage states. 4214 */ 4215 if (!valid_state(curr, this, new_bit, excl_bit)) 4216 return 0; 4217 4218 /* 4219 * Check for read in write conflicts 4220 */ 4221 if (!read && !valid_state(curr, this, new_bit, 4222 excl_bit + LOCK_USAGE_READ_MASK)) 4223 return 0; 4224 4225 4226 /* 4227 * Validate that the lock dependencies don't have conflicting usage 4228 * states. 4229 */ 4230 if (dir) { 4231 /* 4232 * mark ENABLED has to look backwards -- to ensure no dependee 4233 * has USED_IN state, which, again, would allow recursion deadlocks. 4234 */ 4235 if (!check_usage_backwards(curr, this, excl_bit)) 4236 return 0; 4237 } else { 4238 /* 4239 * mark USED_IN has to look forwards -- to ensure no dependency 4240 * has ENABLED state, which would allow recursion deadlocks. 4241 */ 4242 if (!check_usage_forwards(curr, this, excl_bit)) 4243 return 0; 4244 } 4245 4246 if (state_verbose(new_bit, hlock_class(this))) 4247 return 2; 4248 4249 return 1; 4250 } 4251 4252 /* 4253 * Mark all held locks with a usage bit: 4254 */ 4255 static int 4256 mark_held_locks(struct task_struct *curr, enum lock_usage_bit base_bit) 4257 { 4258 struct held_lock *hlock; 4259 int i; 4260 4261 for (i = 0; i < curr->lockdep_depth; i++) { 4262 enum lock_usage_bit hlock_bit = base_bit; 4263 hlock = curr->held_locks + i; 4264 4265 if (hlock->read) 4266 hlock_bit += LOCK_USAGE_READ_MASK; 4267 4268 BUG_ON(hlock_bit >= LOCK_USAGE_STATES); 4269 4270 if (!hlock->check) 4271 continue; 4272 4273 if (!mark_lock(curr, hlock, hlock_bit)) 4274 return 0; 4275 } 4276 4277 return 1; 4278 } 4279 4280 /* 4281 * Hardirqs will be enabled: 4282 */ 4283 static void __trace_hardirqs_on_caller(void) 4284 { 4285 struct task_struct *curr = current; 4286 4287 /* 4288 * We are going to turn hardirqs on, so set the 4289 * usage bit for all held locks: 4290 */ 4291 if (!mark_held_locks(curr, LOCK_ENABLED_HARDIRQ)) 4292 return; 4293 /* 4294 * If we have softirqs enabled, then set the usage 4295 * bit for all held locks. (disabled hardirqs prevented 4296 * this bit from being set before) 4297 */ 4298 if (curr->softirqs_enabled) 4299 mark_held_locks(curr, LOCK_ENABLED_SOFTIRQ); 4300 } 4301 4302 /** 4303 * lockdep_hardirqs_on_prepare - Prepare for enabling interrupts 4304 * 4305 * Invoked before a possible transition to RCU idle from exit to user or 4306 * guest mode. This ensures that all RCU operations are done before RCU 4307 * stops watching. After the RCU transition lockdep_hardirqs_on() has to be 4308 * invoked to set the final state. 4309 */ 4310 void lockdep_hardirqs_on_prepare(void) 4311 { 4312 if (unlikely(!debug_locks)) 4313 return; 4314 4315 /* 4316 * NMIs do not (and cannot) track lock dependencies, nothing to do. 4317 */ 4318 if (unlikely(in_nmi())) 4319 return; 4320 4321 if (unlikely(this_cpu_read(lockdep_recursion))) 4322 return; 4323 4324 if (unlikely(lockdep_hardirqs_enabled())) { 4325 /* 4326 * Neither irq nor preemption are disabled here 4327 * so this is racy by nature but losing one hit 4328 * in a stat is not a big deal. 4329 */ 4330 __debug_atomic_inc(redundant_hardirqs_on); 4331 return; 4332 } 4333 4334 /* 4335 * We're enabling irqs and according to our state above irqs weren't 4336 * already enabled, yet we find the hardware thinks they are in fact 4337 * enabled.. someone messed up their IRQ state tracing. 4338 */ 4339 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled())) 4340 return; 4341 4342 /* 4343 * See the fine text that goes along with this variable definition. 4344 */ 4345 if (DEBUG_LOCKS_WARN_ON(early_boot_irqs_disabled)) 4346 return; 4347 4348 /* 4349 * Can't allow enabling interrupts while in an interrupt handler, 4350 * that's general bad form and such. Recursion, limited stack etc.. 4351 */ 4352 if (DEBUG_LOCKS_WARN_ON(lockdep_hardirq_context())) 4353 return; 4354 4355 current->hardirq_chain_key = current->curr_chain_key; 4356 4357 lockdep_recursion_inc(); 4358 __trace_hardirqs_on_caller(); 4359 lockdep_recursion_finish(); 4360 } 4361 EXPORT_SYMBOL_GPL(lockdep_hardirqs_on_prepare); 4362 4363 void noinstr lockdep_hardirqs_on(unsigned long ip) 4364 { 4365 struct irqtrace_events *trace = ¤t->irqtrace; 4366 4367 if (unlikely(!debug_locks)) 4368 return; 4369 4370 /* 4371 * NMIs can happen in the middle of local_irq_{en,dis}able() where the 4372 * tracking state and hardware state are out of sync. 4373 * 4374 * NMIs must save lockdep_hardirqs_enabled() to restore IRQ state from, 4375 * and not rely on hardware state like normal interrupts. 4376 */ 4377 if (unlikely(in_nmi())) { 4378 if (!IS_ENABLED(CONFIG_TRACE_IRQFLAGS_NMI)) 4379 return; 4380 4381 /* 4382 * Skip: 4383 * - recursion check, because NMI can hit lockdep; 4384 * - hardware state check, because above; 4385 * - chain_key check, see lockdep_hardirqs_on_prepare(). 4386 */ 4387 goto skip_checks; 4388 } 4389 4390 if (unlikely(this_cpu_read(lockdep_recursion))) 4391 return; 4392 4393 if (lockdep_hardirqs_enabled()) { 4394 /* 4395 * Neither irq nor preemption are disabled here 4396 * so this is racy by nature but losing one hit 4397 * in a stat is not a big deal. 4398 */ 4399 __debug_atomic_inc(redundant_hardirqs_on); 4400 return; 4401 } 4402 4403 /* 4404 * We're enabling irqs and according to our state above irqs weren't 4405 * already enabled, yet we find the hardware thinks they are in fact 4406 * enabled.. someone messed up their IRQ state tracing. 4407 */ 4408 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled())) 4409 return; 4410 4411 /* 4412 * Ensure the lock stack remained unchanged between 4413 * lockdep_hardirqs_on_prepare() and lockdep_hardirqs_on(). 4414 */ 4415 DEBUG_LOCKS_WARN_ON(current->hardirq_chain_key != 4416 current->curr_chain_key); 4417 4418 skip_checks: 4419 /* we'll do an OFF -> ON transition: */ 4420 __this_cpu_write(hardirqs_enabled, 1); 4421 trace->hardirq_enable_ip = ip; 4422 trace->hardirq_enable_event = ++trace->irq_events; 4423 debug_atomic_inc(hardirqs_on_events); 4424 } 4425 EXPORT_SYMBOL_GPL(lockdep_hardirqs_on); 4426 4427 /* 4428 * Hardirqs were disabled: 4429 */ 4430 void noinstr lockdep_hardirqs_off(unsigned long ip) 4431 { 4432 if (unlikely(!debug_locks)) 4433 return; 4434 4435 /* 4436 * Matching lockdep_hardirqs_on(), allow NMIs in the middle of lockdep; 4437 * they will restore the software state. This ensures the software 4438 * state is consistent inside NMIs as well. 4439 */ 4440 if (in_nmi()) { 4441 if (!IS_ENABLED(CONFIG_TRACE_IRQFLAGS_NMI)) 4442 return; 4443 } else if (__this_cpu_read(lockdep_recursion)) 4444 return; 4445 4446 /* 4447 * So we're supposed to get called after you mask local IRQs, but for 4448 * some reason the hardware doesn't quite think you did a proper job. 4449 */ 4450 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled())) 4451 return; 4452 4453 if (lockdep_hardirqs_enabled()) { 4454 struct irqtrace_events *trace = ¤t->irqtrace; 4455 4456 /* 4457 * We have done an ON -> OFF transition: 4458 */ 4459 __this_cpu_write(hardirqs_enabled, 0); 4460 trace->hardirq_disable_ip = ip; 4461 trace->hardirq_disable_event = ++trace->irq_events; 4462 debug_atomic_inc(hardirqs_off_events); 4463 } else { 4464 debug_atomic_inc(redundant_hardirqs_off); 4465 } 4466 } 4467 EXPORT_SYMBOL_GPL(lockdep_hardirqs_off); 4468 4469 /* 4470 * Softirqs will be enabled: 4471 */ 4472 void lockdep_softirqs_on(unsigned long ip) 4473 { 4474 struct irqtrace_events *trace = ¤t->irqtrace; 4475 4476 if (unlikely(!lockdep_enabled())) 4477 return; 4478 4479 /* 4480 * We fancy IRQs being disabled here, see softirq.c, avoids 4481 * funny state and nesting things. 4482 */ 4483 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled())) 4484 return; 4485 4486 if (current->softirqs_enabled) { 4487 debug_atomic_inc(redundant_softirqs_on); 4488 return; 4489 } 4490 4491 lockdep_recursion_inc(); 4492 /* 4493 * We'll do an OFF -> ON transition: 4494 */ 4495 current->softirqs_enabled = 1; 4496 trace->softirq_enable_ip = ip; 4497 trace->softirq_enable_event = ++trace->irq_events; 4498 debug_atomic_inc(softirqs_on_events); 4499 /* 4500 * We are going to turn softirqs on, so set the 4501 * usage bit for all held locks, if hardirqs are 4502 * enabled too: 4503 */ 4504 if (lockdep_hardirqs_enabled()) 4505 mark_held_locks(current, LOCK_ENABLED_SOFTIRQ); 4506 lockdep_recursion_finish(); 4507 } 4508 4509 /* 4510 * Softirqs were disabled: 4511 */ 4512 void lockdep_softirqs_off(unsigned long ip) 4513 { 4514 if (unlikely(!lockdep_enabled())) 4515 return; 4516 4517 /* 4518 * We fancy IRQs being disabled here, see softirq.c 4519 */ 4520 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled())) 4521 return; 4522 4523 if (current->softirqs_enabled) { 4524 struct irqtrace_events *trace = ¤t->irqtrace; 4525 4526 /* 4527 * We have done an ON -> OFF transition: 4528 */ 4529 current->softirqs_enabled = 0; 4530 trace->softirq_disable_ip = ip; 4531 trace->softirq_disable_event = ++trace->irq_events; 4532 debug_atomic_inc(softirqs_off_events); 4533 /* 4534 * Whoops, we wanted softirqs off, so why aren't they? 4535 */ 4536 DEBUG_LOCKS_WARN_ON(!softirq_count()); 4537 } else 4538 debug_atomic_inc(redundant_softirqs_off); 4539 } 4540 4541 static int 4542 mark_usage(struct task_struct *curr, struct held_lock *hlock, int check) 4543 { 4544 if (!check) 4545 goto lock_used; 4546 4547 /* 4548 * If non-trylock use in a hardirq or softirq context, then 4549 * mark the lock as used in these contexts: 4550 */ 4551 if (!hlock->trylock) { 4552 if (hlock->read) { 4553 if (lockdep_hardirq_context()) 4554 if (!mark_lock(curr, hlock, 4555 LOCK_USED_IN_HARDIRQ_READ)) 4556 return 0; 4557 if (curr->softirq_context) 4558 if (!mark_lock(curr, hlock, 4559 LOCK_USED_IN_SOFTIRQ_READ)) 4560 return 0; 4561 } else { 4562 if (lockdep_hardirq_context()) 4563 if (!mark_lock(curr, hlock, LOCK_USED_IN_HARDIRQ)) 4564 return 0; 4565 if (curr->softirq_context) 4566 if (!mark_lock(curr, hlock, LOCK_USED_IN_SOFTIRQ)) 4567 return 0; 4568 } 4569 } 4570 4571 /* 4572 * For lock_sync(), don't mark the ENABLED usage, since lock_sync() 4573 * creates no critical section and no extra dependency can be introduced 4574 * by interrupts 4575 */ 4576 if (!hlock->hardirqs_off && !hlock->sync) { 4577 if (hlock->read) { 4578 if (!mark_lock(curr, hlock, 4579 LOCK_ENABLED_HARDIRQ_READ)) 4580 return 0; 4581 if (curr->softirqs_enabled) 4582 if (!mark_lock(curr, hlock, 4583 LOCK_ENABLED_SOFTIRQ_READ)) 4584 return 0; 4585 } else { 4586 if (!mark_lock(curr, hlock, 4587 LOCK_ENABLED_HARDIRQ)) 4588 return 0; 4589 if (curr->softirqs_enabled) 4590 if (!mark_lock(curr, hlock, 4591 LOCK_ENABLED_SOFTIRQ)) 4592 return 0; 4593 } 4594 } 4595 4596 lock_used: 4597 /* mark it as used: */ 4598 if (!mark_lock(curr, hlock, LOCK_USED)) 4599 return 0; 4600 4601 return 1; 4602 } 4603 4604 static inline unsigned int task_irq_context(struct task_struct *task) 4605 { 4606 return LOCK_CHAIN_HARDIRQ_CONTEXT * !!lockdep_hardirq_context() + 4607 LOCK_CHAIN_SOFTIRQ_CONTEXT * !!task->softirq_context; 4608 } 4609 4610 static int separate_irq_context(struct task_struct *curr, 4611 struct held_lock *hlock) 4612 { 4613 unsigned int depth = curr->lockdep_depth; 4614 4615 /* 4616 * Keep track of points where we cross into an interrupt context: 4617 */ 4618 if (depth) { 4619 struct held_lock *prev_hlock; 4620 4621 prev_hlock = curr->held_locks + depth-1; 4622 /* 4623 * If we cross into another context, reset the 4624 * hash key (this also prevents the checking and the 4625 * adding of the dependency to 'prev'): 4626 */ 4627 if (prev_hlock->irq_context != hlock->irq_context) 4628 return 1; 4629 } 4630 return 0; 4631 } 4632 4633 /* 4634 * Mark a lock with a usage bit, and validate the state transition: 4635 */ 4636 static int mark_lock(struct task_struct *curr, struct held_lock *this, 4637 enum lock_usage_bit new_bit) 4638 { 4639 unsigned int new_mask, ret = 1; 4640 4641 if (new_bit >= LOCK_USAGE_STATES) { 4642 DEBUG_LOCKS_WARN_ON(1); 4643 return 0; 4644 } 4645 4646 if (new_bit == LOCK_USED && this->read) 4647 new_bit = LOCK_USED_READ; 4648 4649 new_mask = 1 << new_bit; 4650 4651 /* 4652 * If already set then do not dirty the cacheline, 4653 * nor do any checks: 4654 */ 4655 if (likely(hlock_class(this)->usage_mask & new_mask)) 4656 return 1; 4657 4658 if (!graph_lock()) 4659 return 0; 4660 /* 4661 * Make sure we didn't race: 4662 */ 4663 if (unlikely(hlock_class(this)->usage_mask & new_mask)) 4664 goto unlock; 4665 4666 if (!hlock_class(this)->usage_mask) 4667 debug_atomic_dec(nr_unused_locks); 4668 4669 hlock_class(this)->usage_mask |= new_mask; 4670 4671 if (new_bit < LOCK_TRACE_STATES) { 4672 if (!(hlock_class(this)->usage_traces[new_bit] = save_trace())) 4673 return 0; 4674 } 4675 4676 if (new_bit < LOCK_USED) { 4677 ret = mark_lock_irq(curr, this, new_bit); 4678 if (!ret) 4679 return 0; 4680 } 4681 4682 unlock: 4683 graph_unlock(); 4684 4685 /* 4686 * We must printk outside of the graph_lock: 4687 */ 4688 if (ret == 2) { 4689 printk("\nmarked lock as {%s}:\n", usage_str[new_bit]); 4690 print_lock(this); 4691 print_irqtrace_events(curr); 4692 dump_stack(); 4693 } 4694 4695 return ret; 4696 } 4697 4698 static inline short task_wait_context(struct task_struct *curr) 4699 { 4700 /* 4701 * Set appropriate wait type for the context; for IRQs we have to take 4702 * into account force_irqthread as that is implied by PREEMPT_RT. 4703 */ 4704 if (lockdep_hardirq_context()) { 4705 /* 4706 * Check if force_irqthreads will run us threaded. 4707 */ 4708 if (curr->hardirq_threaded || curr->irq_config) 4709 return LD_WAIT_CONFIG; 4710 4711 return LD_WAIT_SPIN; 4712 } else if (curr->softirq_context) { 4713 /* 4714 * Softirqs are always threaded. 4715 */ 4716 return LD_WAIT_CONFIG; 4717 } 4718 4719 return LD_WAIT_MAX; 4720 } 4721 4722 static int 4723 print_lock_invalid_wait_context(struct task_struct *curr, 4724 struct held_lock *hlock) 4725 { 4726 short curr_inner; 4727 4728 if (!debug_locks_off()) 4729 return 0; 4730 if (debug_locks_silent) 4731 return 0; 4732 4733 pr_warn("\n"); 4734 pr_warn("=============================\n"); 4735 pr_warn("[ BUG: Invalid wait context ]\n"); 4736 print_kernel_ident(); 4737 pr_warn("-----------------------------\n"); 4738 4739 pr_warn("%s/%d is trying to lock:\n", curr->comm, task_pid_nr(curr)); 4740 print_lock(hlock); 4741 4742 pr_warn("other info that might help us debug this:\n"); 4743 4744 curr_inner = task_wait_context(curr); 4745 pr_warn("context-{%d:%d}\n", curr_inner, curr_inner); 4746 4747 lockdep_print_held_locks(curr); 4748 4749 pr_warn("stack backtrace:\n"); 4750 dump_stack(); 4751 4752 return 0; 4753 } 4754 4755 /* 4756 * Verify the wait_type context. 4757 * 4758 * This check validates we take locks in the right wait-type order; that is it 4759 * ensures that we do not take mutexes inside spinlocks and do not attempt to 4760 * acquire spinlocks inside raw_spinlocks and the sort. 4761 * 4762 * The entire thing is slightly more complex because of RCU, RCU is a lock that 4763 * can be taken from (pretty much) any context but also has constraints. 4764 * However when taken in a stricter environment the RCU lock does not loosen 4765 * the constraints. 4766 * 4767 * Therefore we must look for the strictest environment in the lock stack and 4768 * compare that to the lock we're trying to acquire. 4769 */ 4770 static int check_wait_context(struct task_struct *curr, struct held_lock *next) 4771 { 4772 u8 next_inner = hlock_class(next)->wait_type_inner; 4773 u8 next_outer = hlock_class(next)->wait_type_outer; 4774 u8 curr_inner; 4775 int depth; 4776 4777 if (!next_inner || next->trylock) 4778 return 0; 4779 4780 if (!next_outer) 4781 next_outer = next_inner; 4782 4783 /* 4784 * Find start of current irq_context.. 4785 */ 4786 for (depth = curr->lockdep_depth - 1; depth >= 0; depth--) { 4787 struct held_lock *prev = curr->held_locks + depth; 4788 if (prev->irq_context != next->irq_context) 4789 break; 4790 } 4791 depth++; 4792 4793 curr_inner = task_wait_context(curr); 4794 4795 for (; depth < curr->lockdep_depth; depth++) { 4796 struct held_lock *prev = curr->held_locks + depth; 4797 struct lock_class *class = hlock_class(prev); 4798 u8 prev_inner = class->wait_type_inner; 4799 4800 if (prev_inner) { 4801 /* 4802 * We can have a bigger inner than a previous one 4803 * when outer is smaller than inner, as with RCU. 4804 * 4805 * Also due to trylocks. 4806 */ 4807 curr_inner = min(curr_inner, prev_inner); 4808 4809 /* 4810 * Allow override for annotations -- this is typically 4811 * only valid/needed for code that only exists when 4812 * CONFIG_PREEMPT_RT=n. 4813 */ 4814 if (unlikely(class->lock_type == LD_LOCK_WAIT_OVERRIDE)) 4815 curr_inner = prev_inner; 4816 } 4817 } 4818 4819 if (next_outer > curr_inner) 4820 return print_lock_invalid_wait_context(curr, next); 4821 4822 return 0; 4823 } 4824 4825 #else /* CONFIG_PROVE_LOCKING */ 4826 4827 static inline int 4828 mark_usage(struct task_struct *curr, struct held_lock *hlock, int check) 4829 { 4830 return 1; 4831 } 4832 4833 static inline unsigned int task_irq_context(struct task_struct *task) 4834 { 4835 return 0; 4836 } 4837 4838 static inline int separate_irq_context(struct task_struct *curr, 4839 struct held_lock *hlock) 4840 { 4841 return 0; 4842 } 4843 4844 static inline int check_wait_context(struct task_struct *curr, 4845 struct held_lock *next) 4846 { 4847 return 0; 4848 } 4849 4850 #endif /* CONFIG_PROVE_LOCKING */ 4851 4852 /* 4853 * Initialize a lock instance's lock-class mapping info: 4854 */ 4855 void lockdep_init_map_type(struct lockdep_map *lock, const char *name, 4856 struct lock_class_key *key, int subclass, 4857 u8 inner, u8 outer, u8 lock_type) 4858 { 4859 int i; 4860 4861 for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++) 4862 lock->class_cache[i] = NULL; 4863 4864 #ifdef CONFIG_LOCK_STAT 4865 lock->cpu = raw_smp_processor_id(); 4866 #endif 4867 4868 /* 4869 * Can't be having no nameless bastards around this place! 4870 */ 4871 if (DEBUG_LOCKS_WARN_ON(!name)) { 4872 lock->name = "NULL"; 4873 return; 4874 } 4875 4876 lock->name = name; 4877 4878 lock->wait_type_outer = outer; 4879 lock->wait_type_inner = inner; 4880 lock->lock_type = lock_type; 4881 4882 /* 4883 * No key, no joy, we need to hash something. 4884 */ 4885 if (DEBUG_LOCKS_WARN_ON(!key)) 4886 return; 4887 /* 4888 * Sanity check, the lock-class key must either have been allocated 4889 * statically or must have been registered as a dynamic key. 4890 */ 4891 if (!static_obj(key) && !is_dynamic_key(key)) { 4892 if (debug_locks) 4893 printk(KERN_ERR "BUG: key %px has not been registered!\n", key); 4894 DEBUG_LOCKS_WARN_ON(1); 4895 return; 4896 } 4897 lock->key = key; 4898 4899 if (unlikely(!debug_locks)) 4900 return; 4901 4902 if (subclass) { 4903 unsigned long flags; 4904 4905 if (DEBUG_LOCKS_WARN_ON(!lockdep_enabled())) 4906 return; 4907 4908 raw_local_irq_save(flags); 4909 lockdep_recursion_inc(); 4910 register_lock_class(lock, subclass, 1); 4911 lockdep_recursion_finish(); 4912 raw_local_irq_restore(flags); 4913 } 4914 } 4915 EXPORT_SYMBOL_GPL(lockdep_init_map_type); 4916 4917 struct lock_class_key __lockdep_no_validate__; 4918 EXPORT_SYMBOL_GPL(__lockdep_no_validate__); 4919 4920 #ifdef CONFIG_PROVE_LOCKING 4921 void lockdep_set_lock_cmp_fn(struct lockdep_map *lock, lock_cmp_fn cmp_fn, 4922 lock_print_fn print_fn) 4923 { 4924 struct lock_class *class = lock->class_cache[0]; 4925 unsigned long flags; 4926 4927 raw_local_irq_save(flags); 4928 lockdep_recursion_inc(); 4929 4930 if (!class) 4931 class = register_lock_class(lock, 0, 0); 4932 4933 if (class) { 4934 WARN_ON(class->cmp_fn && class->cmp_fn != cmp_fn); 4935 WARN_ON(class->print_fn && class->print_fn != print_fn); 4936 4937 class->cmp_fn = cmp_fn; 4938 class->print_fn = print_fn; 4939 } 4940 4941 lockdep_recursion_finish(); 4942 raw_local_irq_restore(flags); 4943 } 4944 EXPORT_SYMBOL_GPL(lockdep_set_lock_cmp_fn); 4945 #endif 4946 4947 static void 4948 print_lock_nested_lock_not_held(struct task_struct *curr, 4949 struct held_lock *hlock) 4950 { 4951 if (!debug_locks_off()) 4952 return; 4953 if (debug_locks_silent) 4954 return; 4955 4956 pr_warn("\n"); 4957 pr_warn("==================================\n"); 4958 pr_warn("WARNING: Nested lock was not taken\n"); 4959 print_kernel_ident(); 4960 pr_warn("----------------------------------\n"); 4961 4962 pr_warn("%s/%d is trying to lock:\n", curr->comm, task_pid_nr(curr)); 4963 print_lock(hlock); 4964 4965 pr_warn("\nbut this task is not holding:\n"); 4966 pr_warn("%s\n", hlock->nest_lock->name); 4967 4968 pr_warn("\nstack backtrace:\n"); 4969 dump_stack(); 4970 4971 pr_warn("\nother info that might help us debug this:\n"); 4972 lockdep_print_held_locks(curr); 4973 4974 pr_warn("\nstack backtrace:\n"); 4975 dump_stack(); 4976 } 4977 4978 static int __lock_is_held(const struct lockdep_map *lock, int read); 4979 4980 /* 4981 * This gets called for every mutex_lock*()/spin_lock*() operation. 4982 * We maintain the dependency maps and validate the locking attempt: 4983 * 4984 * The callers must make sure that IRQs are disabled before calling it, 4985 * otherwise we could get an interrupt which would want to take locks, 4986 * which would end up in lockdep again. 4987 */ 4988 static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass, 4989 int trylock, int read, int check, int hardirqs_off, 4990 struct lockdep_map *nest_lock, unsigned long ip, 4991 int references, int pin_count, int sync) 4992 { 4993 struct task_struct *curr = current; 4994 struct lock_class *class = NULL; 4995 struct held_lock *hlock; 4996 unsigned int depth; 4997 int chain_head = 0; 4998 int class_idx; 4999 u64 chain_key; 5000 5001 if (unlikely(!debug_locks)) 5002 return 0; 5003 5004 if (!prove_locking || lock->key == &__lockdep_no_validate__) 5005 check = 0; 5006 5007 if (subclass < NR_LOCKDEP_CACHING_CLASSES) 5008 class = lock->class_cache[subclass]; 5009 /* 5010 * Not cached? 5011 */ 5012 if (unlikely(!class)) { 5013 class = register_lock_class(lock, subclass, 0); 5014 if (!class) 5015 return 0; 5016 } 5017 5018 debug_class_ops_inc(class); 5019 5020 if (very_verbose(class)) { 5021 printk("\nacquire class [%px] %s", class->key, class->name); 5022 if (class->name_version > 1) 5023 printk(KERN_CONT "#%d", class->name_version); 5024 printk(KERN_CONT "\n"); 5025 dump_stack(); 5026 } 5027 5028 /* 5029 * Add the lock to the list of currently held locks. 5030 * (we dont increase the depth just yet, up until the 5031 * dependency checks are done) 5032 */ 5033 depth = curr->lockdep_depth; 5034 /* 5035 * Ran out of static storage for our per-task lock stack again have we? 5036 */ 5037 if (DEBUG_LOCKS_WARN_ON(depth >= MAX_LOCK_DEPTH)) 5038 return 0; 5039 5040 class_idx = class - lock_classes; 5041 5042 if (depth && !sync) { 5043 /* we're holding locks and the new held lock is not a sync */ 5044 hlock = curr->held_locks + depth - 1; 5045 if (hlock->class_idx == class_idx && nest_lock) { 5046 if (!references) 5047 references++; 5048 5049 if (!hlock->references) 5050 hlock->references++; 5051 5052 hlock->references += references; 5053 5054 /* Overflow */ 5055 if (DEBUG_LOCKS_WARN_ON(hlock->references < references)) 5056 return 0; 5057 5058 return 2; 5059 } 5060 } 5061 5062 hlock = curr->held_locks + depth; 5063 /* 5064 * Plain impossible, we just registered it and checked it weren't no 5065 * NULL like.. I bet this mushroom I ate was good! 5066 */ 5067 if (DEBUG_LOCKS_WARN_ON(!class)) 5068 return 0; 5069 hlock->class_idx = class_idx; 5070 hlock->acquire_ip = ip; 5071 hlock->instance = lock; 5072 hlock->nest_lock = nest_lock; 5073 hlock->irq_context = task_irq_context(curr); 5074 hlock->trylock = trylock; 5075 hlock->read = read; 5076 hlock->check = check; 5077 hlock->sync = !!sync; 5078 hlock->hardirqs_off = !!hardirqs_off; 5079 hlock->references = references; 5080 #ifdef CONFIG_LOCK_STAT 5081 hlock->waittime_stamp = 0; 5082 hlock->holdtime_stamp = lockstat_clock(); 5083 #endif 5084 hlock->pin_count = pin_count; 5085 5086 if (check_wait_context(curr, hlock)) 5087 return 0; 5088 5089 /* Initialize the lock usage bit */ 5090 if (!mark_usage(curr, hlock, check)) 5091 return 0; 5092 5093 /* 5094 * Calculate the chain hash: it's the combined hash of all the 5095 * lock keys along the dependency chain. We save the hash value 5096 * at every step so that we can get the current hash easily 5097 * after unlock. The chain hash is then used to cache dependency 5098 * results. 5099 * 5100 * The 'key ID' is what is the most compact key value to drive 5101 * the hash, not class->key. 5102 */ 5103 /* 5104 * Whoops, we did it again.. class_idx is invalid. 5105 */ 5106 if (DEBUG_LOCKS_WARN_ON(!test_bit(class_idx, lock_classes_in_use))) 5107 return 0; 5108 5109 chain_key = curr->curr_chain_key; 5110 if (!depth) { 5111 /* 5112 * How can we have a chain hash when we ain't got no keys?! 5113 */ 5114 if (DEBUG_LOCKS_WARN_ON(chain_key != INITIAL_CHAIN_KEY)) 5115 return 0; 5116 chain_head = 1; 5117 } 5118 5119 hlock->prev_chain_key = chain_key; 5120 if (separate_irq_context(curr, hlock)) { 5121 chain_key = INITIAL_CHAIN_KEY; 5122 chain_head = 1; 5123 } 5124 chain_key = iterate_chain_key(chain_key, hlock_id(hlock)); 5125 5126 if (nest_lock && !__lock_is_held(nest_lock, -1)) { 5127 print_lock_nested_lock_not_held(curr, hlock); 5128 return 0; 5129 } 5130 5131 if (!debug_locks_silent) { 5132 WARN_ON_ONCE(depth && !hlock_class(hlock - 1)->key); 5133 WARN_ON_ONCE(!hlock_class(hlock)->key); 5134 } 5135 5136 if (!validate_chain(curr, hlock, chain_head, chain_key)) 5137 return 0; 5138 5139 /* For lock_sync(), we are done here since no actual critical section */ 5140 if (hlock->sync) 5141 return 1; 5142 5143 curr->curr_chain_key = chain_key; 5144 curr->lockdep_depth++; 5145 check_chain_key(curr); 5146 #ifdef CONFIG_DEBUG_LOCKDEP 5147 if (unlikely(!debug_locks)) 5148 return 0; 5149 #endif 5150 if (unlikely(curr->lockdep_depth >= MAX_LOCK_DEPTH)) { 5151 debug_locks_off(); 5152 print_lockdep_off("BUG: MAX_LOCK_DEPTH too low!"); 5153 printk(KERN_DEBUG "depth: %i max: %lu!\n", 5154 curr->lockdep_depth, MAX_LOCK_DEPTH); 5155 5156 lockdep_print_held_locks(current); 5157 debug_show_all_locks(); 5158 dump_stack(); 5159 5160 return 0; 5161 } 5162 5163 if (unlikely(curr->lockdep_depth > max_lockdep_depth)) 5164 max_lockdep_depth = curr->lockdep_depth; 5165 5166 return 1; 5167 } 5168 5169 static void print_unlock_imbalance_bug(struct task_struct *curr, 5170 struct lockdep_map *lock, 5171 unsigned long ip) 5172 { 5173 if (!debug_locks_off()) 5174 return; 5175 if (debug_locks_silent) 5176 return; 5177 5178 pr_warn("\n"); 5179 pr_warn("=====================================\n"); 5180 pr_warn("WARNING: bad unlock balance detected!\n"); 5181 print_kernel_ident(); 5182 pr_warn("-------------------------------------\n"); 5183 pr_warn("%s/%d is trying to release lock (", 5184 curr->comm, task_pid_nr(curr)); 5185 print_lockdep_cache(lock); 5186 pr_cont(") at:\n"); 5187 print_ip_sym(KERN_WARNING, ip); 5188 pr_warn("but there are no more locks to release!\n"); 5189 pr_warn("\nother info that might help us debug this:\n"); 5190 lockdep_print_held_locks(curr); 5191 5192 pr_warn("\nstack backtrace:\n"); 5193 dump_stack(); 5194 } 5195 5196 static noinstr int match_held_lock(const struct held_lock *hlock, 5197 const struct lockdep_map *lock) 5198 { 5199 if (hlock->instance == lock) 5200 return 1; 5201 5202 if (hlock->references) { 5203 const struct lock_class *class = lock->class_cache[0]; 5204 5205 if (!class) 5206 class = look_up_lock_class(lock, 0); 5207 5208 /* 5209 * If look_up_lock_class() failed to find a class, we're trying 5210 * to test if we hold a lock that has never yet been acquired. 5211 * Clearly if the lock hasn't been acquired _ever_, we're not 5212 * holding it either, so report failure. 5213 */ 5214 if (!class) 5215 return 0; 5216 5217 /* 5218 * References, but not a lock we're actually ref-counting? 5219 * State got messed up, follow the sites that change ->references 5220 * and try to make sense of it. 5221 */ 5222 if (DEBUG_LOCKS_WARN_ON(!hlock->nest_lock)) 5223 return 0; 5224 5225 if (hlock->class_idx == class - lock_classes) 5226 return 1; 5227 } 5228 5229 return 0; 5230 } 5231 5232 /* @depth must not be zero */ 5233 static struct held_lock *find_held_lock(struct task_struct *curr, 5234 struct lockdep_map *lock, 5235 unsigned int depth, int *idx) 5236 { 5237 struct held_lock *ret, *hlock, *prev_hlock; 5238 int i; 5239 5240 i = depth - 1; 5241 hlock = curr->held_locks + i; 5242 ret = hlock; 5243 if (match_held_lock(hlock, lock)) 5244 goto out; 5245 5246 ret = NULL; 5247 for (i--, prev_hlock = hlock--; 5248 i >= 0; 5249 i--, prev_hlock = hlock--) { 5250 /* 5251 * We must not cross into another context: 5252 */ 5253 if (prev_hlock->irq_context != hlock->irq_context) { 5254 ret = NULL; 5255 break; 5256 } 5257 if (match_held_lock(hlock, lock)) { 5258 ret = hlock; 5259 break; 5260 } 5261 } 5262 5263 out: 5264 *idx = i; 5265 return ret; 5266 } 5267 5268 static int reacquire_held_locks(struct task_struct *curr, unsigned int depth, 5269 int idx, unsigned int *merged) 5270 { 5271 struct held_lock *hlock; 5272 int first_idx = idx; 5273 5274 if (DEBUG_LOCKS_WARN_ON(!irqs_disabled())) 5275 return 0; 5276 5277 for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) { 5278 switch (__lock_acquire(hlock->instance, 5279 hlock_class(hlock)->subclass, 5280 hlock->trylock, 5281 hlock->read, hlock->check, 5282 hlock->hardirqs_off, 5283 hlock->nest_lock, hlock->acquire_ip, 5284 hlock->references, hlock->pin_count, 0)) { 5285 case 0: 5286 return 1; 5287 case 1: 5288 break; 5289 case 2: 5290 *merged += (idx == first_idx); 5291 break; 5292 default: 5293 WARN_ON(1); 5294 return 0; 5295 } 5296 } 5297 return 0; 5298 } 5299 5300 static int 5301 __lock_set_class(struct lockdep_map *lock, const char *name, 5302 struct lock_class_key *key, unsigned int subclass, 5303 unsigned long ip) 5304 { 5305 struct task_struct *curr = current; 5306 unsigned int depth, merged = 0; 5307 struct held_lock *hlock; 5308 struct lock_class *class; 5309 int i; 5310 5311 if (unlikely(!debug_locks)) 5312 return 0; 5313 5314 depth = curr->lockdep_depth; 5315 /* 5316 * This function is about (re)setting the class of a held lock, 5317 * yet we're not actually holding any locks. Naughty user! 5318 */ 5319 if (DEBUG_LOCKS_WARN_ON(!depth)) 5320 return 0; 5321 5322 hlock = find_held_lock(curr, lock, depth, &i); 5323 if (!hlock) { 5324 print_unlock_imbalance_bug(curr, lock, ip); 5325 return 0; 5326 } 5327 5328 lockdep_init_map_type(lock, name, key, 0, 5329 lock->wait_type_inner, 5330 lock->wait_type_outer, 5331 lock->lock_type); 5332 class = register_lock_class(lock, subclass, 0); 5333 hlock->class_idx = class - lock_classes; 5334 5335 curr->lockdep_depth = i; 5336 curr->curr_chain_key = hlock->prev_chain_key; 5337 5338 if (reacquire_held_locks(curr, depth, i, &merged)) 5339 return 0; 5340 5341 /* 5342 * I took it apart and put it back together again, except now I have 5343 * these 'spare' parts.. where shall I put them. 5344 */ 5345 if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged)) 5346 return 0; 5347 return 1; 5348 } 5349 5350 static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip) 5351 { 5352 struct task_struct *curr = current; 5353 unsigned int depth, merged = 0; 5354 struct held_lock *hlock; 5355 int i; 5356 5357 if (unlikely(!debug_locks)) 5358 return 0; 5359 5360 depth = curr->lockdep_depth; 5361 /* 5362 * This function is about (re)setting the class of a held lock, 5363 * yet we're not actually holding any locks. Naughty user! 5364 */ 5365 if (DEBUG_LOCKS_WARN_ON(!depth)) 5366 return 0; 5367 5368 hlock = find_held_lock(curr, lock, depth, &i); 5369 if (!hlock) { 5370 print_unlock_imbalance_bug(curr, lock, ip); 5371 return 0; 5372 } 5373 5374 curr->lockdep_depth = i; 5375 curr->curr_chain_key = hlock->prev_chain_key; 5376 5377 WARN(hlock->read, "downgrading a read lock"); 5378 hlock->read = 1; 5379 hlock->acquire_ip = ip; 5380 5381 if (reacquire_held_locks(curr, depth, i, &merged)) 5382 return 0; 5383 5384 /* Merging can't happen with unchanged classes.. */ 5385 if (DEBUG_LOCKS_WARN_ON(merged)) 5386 return 0; 5387 5388 /* 5389 * I took it apart and put it back together again, except now I have 5390 * these 'spare' parts.. where shall I put them. 5391 */ 5392 if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth)) 5393 return 0; 5394 5395 return 1; 5396 } 5397 5398 /* 5399 * Remove the lock from the list of currently held locks - this gets 5400 * called on mutex_unlock()/spin_unlock*() (or on a failed 5401 * mutex_lock_interruptible()). 5402 */ 5403 static int 5404 __lock_release(struct lockdep_map *lock, unsigned long ip) 5405 { 5406 struct task_struct *curr = current; 5407 unsigned int depth, merged = 1; 5408 struct held_lock *hlock; 5409 int i; 5410 5411 if (unlikely(!debug_locks)) 5412 return 0; 5413 5414 depth = curr->lockdep_depth; 5415 /* 5416 * So we're all set to release this lock.. wait what lock? We don't 5417 * own any locks, you've been drinking again? 5418 */ 5419 if (depth <= 0) { 5420 print_unlock_imbalance_bug(curr, lock, ip); 5421 return 0; 5422 } 5423 5424 /* 5425 * Check whether the lock exists in the current stack 5426 * of held locks: 5427 */ 5428 hlock = find_held_lock(curr, lock, depth, &i); 5429 if (!hlock) { 5430 print_unlock_imbalance_bug(curr, lock, ip); 5431 return 0; 5432 } 5433 5434 if (hlock->instance == lock) 5435 lock_release_holdtime(hlock); 5436 5437 WARN(hlock->pin_count, "releasing a pinned lock\n"); 5438 5439 if (hlock->references) { 5440 hlock->references--; 5441 if (hlock->references) { 5442 /* 5443 * We had, and after removing one, still have 5444 * references, the current lock stack is still 5445 * valid. We're done! 5446 */ 5447 return 1; 5448 } 5449 } 5450 5451 /* 5452 * We have the right lock to unlock, 'hlock' points to it. 5453 * Now we remove it from the stack, and add back the other 5454 * entries (if any), recalculating the hash along the way: 5455 */ 5456 5457 curr->lockdep_depth = i; 5458 curr->curr_chain_key = hlock->prev_chain_key; 5459 5460 /* 5461 * The most likely case is when the unlock is on the innermost 5462 * lock. In this case, we are done! 5463 */ 5464 if (i == depth-1) 5465 return 1; 5466 5467 if (reacquire_held_locks(curr, depth, i + 1, &merged)) 5468 return 0; 5469 5470 /* 5471 * We had N bottles of beer on the wall, we drank one, but now 5472 * there's not N-1 bottles of beer left on the wall... 5473 * Pouring two of the bottles together is acceptable. 5474 */ 5475 DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged); 5476 5477 /* 5478 * Since reacquire_held_locks() would have called check_chain_key() 5479 * indirectly via __lock_acquire(), we don't need to do it again 5480 * on return. 5481 */ 5482 return 0; 5483 } 5484 5485 static __always_inline 5486 int __lock_is_held(const struct lockdep_map *lock, int read) 5487 { 5488 struct task_struct *curr = current; 5489 int i; 5490 5491 for (i = 0; i < curr->lockdep_depth; i++) { 5492 struct held_lock *hlock = curr->held_locks + i; 5493 5494 if (match_held_lock(hlock, lock)) { 5495 if (read == -1 || !!hlock->read == read) 5496 return LOCK_STATE_HELD; 5497 5498 return LOCK_STATE_NOT_HELD; 5499 } 5500 } 5501 5502 return LOCK_STATE_NOT_HELD; 5503 } 5504 5505 static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock) 5506 { 5507 struct pin_cookie cookie = NIL_COOKIE; 5508 struct task_struct *curr = current; 5509 int i; 5510 5511 if (unlikely(!debug_locks)) 5512 return cookie; 5513 5514 for (i = 0; i < curr->lockdep_depth; i++) { 5515 struct held_lock *hlock = curr->held_locks + i; 5516 5517 if (match_held_lock(hlock, lock)) { 5518 /* 5519 * Grab 16bits of randomness; this is sufficient to not 5520 * be guessable and still allows some pin nesting in 5521 * our u32 pin_count. 5522 */ 5523 cookie.val = 1 + (sched_clock() & 0xffff); 5524 hlock->pin_count += cookie.val; 5525 return cookie; 5526 } 5527 } 5528 5529 WARN(1, "pinning an unheld lock\n"); 5530 return cookie; 5531 } 5532 5533 static void __lock_repin_lock(struct lockdep_map *lock, struct pin_cookie cookie) 5534 { 5535 struct task_struct *curr = current; 5536 int i; 5537 5538 if (unlikely(!debug_locks)) 5539 return; 5540 5541 for (i = 0; i < curr->lockdep_depth; i++) { 5542 struct held_lock *hlock = curr->held_locks + i; 5543 5544 if (match_held_lock(hlock, lock)) { 5545 hlock->pin_count += cookie.val; 5546 return; 5547 } 5548 } 5549 5550 WARN(1, "pinning an unheld lock\n"); 5551 } 5552 5553 static void __lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie) 5554 { 5555 struct task_struct *curr = current; 5556 int i; 5557 5558 if (unlikely(!debug_locks)) 5559 return; 5560 5561 for (i = 0; i < curr->lockdep_depth; i++) { 5562 struct held_lock *hlock = curr->held_locks + i; 5563 5564 if (match_held_lock(hlock, lock)) { 5565 if (WARN(!hlock->pin_count, "unpinning an unpinned lock\n")) 5566 return; 5567 5568 hlock->pin_count -= cookie.val; 5569 5570 if (WARN((int)hlock->pin_count < 0, "pin count corrupted\n")) 5571 hlock->pin_count = 0; 5572 5573 return; 5574 } 5575 } 5576 5577 WARN(1, "unpinning an unheld lock\n"); 5578 } 5579 5580 /* 5581 * Check whether we follow the irq-flags state precisely: 5582 */ 5583 static noinstr void check_flags(unsigned long flags) 5584 { 5585 #if defined(CONFIG_PROVE_LOCKING) && defined(CONFIG_DEBUG_LOCKDEP) 5586 if (!debug_locks) 5587 return; 5588 5589 /* Get the warning out.. */ 5590 instrumentation_begin(); 5591 5592 if (irqs_disabled_flags(flags)) { 5593 if (DEBUG_LOCKS_WARN_ON(lockdep_hardirqs_enabled())) { 5594 printk("possible reason: unannotated irqs-off.\n"); 5595 } 5596 } else { 5597 if (DEBUG_LOCKS_WARN_ON(!lockdep_hardirqs_enabled())) { 5598 printk("possible reason: unannotated irqs-on.\n"); 5599 } 5600 } 5601 5602 #ifndef CONFIG_PREEMPT_RT 5603 /* 5604 * We dont accurately track softirq state in e.g. 5605 * hardirq contexts (such as on 4KSTACKS), so only 5606 * check if not in hardirq contexts: 5607 */ 5608 if (!hardirq_count()) { 5609 if (softirq_count()) { 5610 /* like the above, but with softirqs */ 5611 DEBUG_LOCKS_WARN_ON(current->softirqs_enabled); 5612 } else { 5613 /* lick the above, does it taste good? */ 5614 DEBUG_LOCKS_WARN_ON(!current->softirqs_enabled); 5615 } 5616 } 5617 #endif 5618 5619 if (!debug_locks) 5620 print_irqtrace_events(current); 5621 5622 instrumentation_end(); 5623 #endif 5624 } 5625 5626 void lock_set_class(struct lockdep_map *lock, const char *name, 5627 struct lock_class_key *key, unsigned int subclass, 5628 unsigned long ip) 5629 { 5630 unsigned long flags; 5631 5632 if (unlikely(!lockdep_enabled())) 5633 return; 5634 5635 raw_local_irq_save(flags); 5636 lockdep_recursion_inc(); 5637 check_flags(flags); 5638 if (__lock_set_class(lock, name, key, subclass, ip)) 5639 check_chain_key(current); 5640 lockdep_recursion_finish(); 5641 raw_local_irq_restore(flags); 5642 } 5643 EXPORT_SYMBOL_GPL(lock_set_class); 5644 5645 void lock_downgrade(struct lockdep_map *lock, unsigned long ip) 5646 { 5647 unsigned long flags; 5648 5649 if (unlikely(!lockdep_enabled())) 5650 return; 5651 5652 raw_local_irq_save(flags); 5653 lockdep_recursion_inc(); 5654 check_flags(flags); 5655 if (__lock_downgrade(lock, ip)) 5656 check_chain_key(current); 5657 lockdep_recursion_finish(); 5658 raw_local_irq_restore(flags); 5659 } 5660 EXPORT_SYMBOL_GPL(lock_downgrade); 5661 5662 /* NMI context !!! */ 5663 static void verify_lock_unused(struct lockdep_map *lock, struct held_lock *hlock, int subclass) 5664 { 5665 #ifdef CONFIG_PROVE_LOCKING 5666 struct lock_class *class = look_up_lock_class(lock, subclass); 5667 unsigned long mask = LOCKF_USED; 5668 5669 /* if it doesn't have a class (yet), it certainly hasn't been used yet */ 5670 if (!class) 5671 return; 5672 5673 /* 5674 * READ locks only conflict with USED, such that if we only ever use 5675 * READ locks, there is no deadlock possible -- RCU. 5676 */ 5677 if (!hlock->read) 5678 mask |= LOCKF_USED_READ; 5679 5680 if (!(class->usage_mask & mask)) 5681 return; 5682 5683 hlock->class_idx = class - lock_classes; 5684 5685 print_usage_bug(current, hlock, LOCK_USED, LOCK_USAGE_STATES); 5686 #endif 5687 } 5688 5689 static bool lockdep_nmi(void) 5690 { 5691 if (raw_cpu_read(lockdep_recursion)) 5692 return false; 5693 5694 if (!in_nmi()) 5695 return false; 5696 5697 return true; 5698 } 5699 5700 /* 5701 * read_lock() is recursive if: 5702 * 1. We force lockdep think this way in selftests or 5703 * 2. The implementation is not queued read/write lock or 5704 * 3. The locker is at an in_interrupt() context. 5705 */ 5706 bool read_lock_is_recursive(void) 5707 { 5708 return force_read_lock_recursive || 5709 !IS_ENABLED(CONFIG_QUEUED_RWLOCKS) || 5710 in_interrupt(); 5711 } 5712 EXPORT_SYMBOL_GPL(read_lock_is_recursive); 5713 5714 /* 5715 * We are not always called with irqs disabled - do that here, 5716 * and also avoid lockdep recursion: 5717 */ 5718 void lock_acquire(struct lockdep_map *lock, unsigned int subclass, 5719 int trylock, int read, int check, 5720 struct lockdep_map *nest_lock, unsigned long ip) 5721 { 5722 unsigned long flags; 5723 5724 trace_lock_acquire(lock, subclass, trylock, read, check, nest_lock, ip); 5725 5726 if (!debug_locks) 5727 return; 5728 5729 if (unlikely(!lockdep_enabled())) { 5730 /* XXX allow trylock from NMI ?!? */ 5731 if (lockdep_nmi() && !trylock) { 5732 struct held_lock hlock; 5733 5734 hlock.acquire_ip = ip; 5735 hlock.instance = lock; 5736 hlock.nest_lock = nest_lock; 5737 hlock.irq_context = 2; // XXX 5738 hlock.trylock = trylock; 5739 hlock.read = read; 5740 hlock.check = check; 5741 hlock.hardirqs_off = true; 5742 hlock.references = 0; 5743 5744 verify_lock_unused(lock, &hlock, subclass); 5745 } 5746 return; 5747 } 5748 5749 raw_local_irq_save(flags); 5750 check_flags(flags); 5751 5752 lockdep_recursion_inc(); 5753 __lock_acquire(lock, subclass, trylock, read, check, 5754 irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 0); 5755 lockdep_recursion_finish(); 5756 raw_local_irq_restore(flags); 5757 } 5758 EXPORT_SYMBOL_GPL(lock_acquire); 5759 5760 void lock_release(struct lockdep_map *lock, unsigned long ip) 5761 { 5762 unsigned long flags; 5763 5764 trace_lock_release(lock, ip); 5765 5766 if (unlikely(!lockdep_enabled())) 5767 return; 5768 5769 raw_local_irq_save(flags); 5770 check_flags(flags); 5771 5772 lockdep_recursion_inc(); 5773 if (__lock_release(lock, ip)) 5774 check_chain_key(current); 5775 lockdep_recursion_finish(); 5776 raw_local_irq_restore(flags); 5777 } 5778 EXPORT_SYMBOL_GPL(lock_release); 5779 5780 /* 5781 * lock_sync() - A special annotation for synchronize_{s,}rcu()-like API. 5782 * 5783 * No actual critical section is created by the APIs annotated with this: these 5784 * APIs are used to wait for one or multiple critical sections (on other CPUs 5785 * or threads), and it means that calling these APIs inside these critical 5786 * sections is potential deadlock. 5787 */ 5788 void lock_sync(struct lockdep_map *lock, unsigned subclass, int read, 5789 int check, struct lockdep_map *nest_lock, unsigned long ip) 5790 { 5791 unsigned long flags; 5792 5793 if (unlikely(!lockdep_enabled())) 5794 return; 5795 5796 raw_local_irq_save(flags); 5797 check_flags(flags); 5798 5799 lockdep_recursion_inc(); 5800 __lock_acquire(lock, subclass, 0, read, check, 5801 irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 1); 5802 check_chain_key(current); 5803 lockdep_recursion_finish(); 5804 raw_local_irq_restore(flags); 5805 } 5806 EXPORT_SYMBOL_GPL(lock_sync); 5807 5808 noinstr int lock_is_held_type(const struct lockdep_map *lock, int read) 5809 { 5810 unsigned long flags; 5811 int ret = LOCK_STATE_NOT_HELD; 5812 5813 /* 5814 * Avoid false negative lockdep_assert_held() and 5815 * lockdep_assert_not_held(). 5816 */ 5817 if (unlikely(!lockdep_enabled())) 5818 return LOCK_STATE_UNKNOWN; 5819 5820 raw_local_irq_save(flags); 5821 check_flags(flags); 5822 5823 lockdep_recursion_inc(); 5824 ret = __lock_is_held(lock, read); 5825 lockdep_recursion_finish(); 5826 raw_local_irq_restore(flags); 5827 5828 return ret; 5829 } 5830 EXPORT_SYMBOL_GPL(lock_is_held_type); 5831 NOKPROBE_SYMBOL(lock_is_held_type); 5832 5833 struct pin_cookie lock_pin_lock(struct lockdep_map *lock) 5834 { 5835 struct pin_cookie cookie = NIL_COOKIE; 5836 unsigned long flags; 5837 5838 if (unlikely(!lockdep_enabled())) 5839 return cookie; 5840 5841 raw_local_irq_save(flags); 5842 check_flags(flags); 5843 5844 lockdep_recursion_inc(); 5845 cookie = __lock_pin_lock(lock); 5846 lockdep_recursion_finish(); 5847 raw_local_irq_restore(flags); 5848 5849 return cookie; 5850 } 5851 EXPORT_SYMBOL_GPL(lock_pin_lock); 5852 5853 void lock_repin_lock(struct lockdep_map *lock, struct pin_cookie cookie) 5854 { 5855 unsigned long flags; 5856 5857 if (unlikely(!lockdep_enabled())) 5858 return; 5859 5860 raw_local_irq_save(flags); 5861 check_flags(flags); 5862 5863 lockdep_recursion_inc(); 5864 __lock_repin_lock(lock, cookie); 5865 lockdep_recursion_finish(); 5866 raw_local_irq_restore(flags); 5867 } 5868 EXPORT_SYMBOL_GPL(lock_repin_lock); 5869 5870 void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie) 5871 { 5872 unsigned long flags; 5873 5874 if (unlikely(!lockdep_enabled())) 5875 return; 5876 5877 raw_local_irq_save(flags); 5878 check_flags(flags); 5879 5880 lockdep_recursion_inc(); 5881 __lock_unpin_lock(lock, cookie); 5882 lockdep_recursion_finish(); 5883 raw_local_irq_restore(flags); 5884 } 5885 EXPORT_SYMBOL_GPL(lock_unpin_lock); 5886 5887 #ifdef CONFIG_LOCK_STAT 5888 static void print_lock_contention_bug(struct task_struct *curr, 5889 struct lockdep_map *lock, 5890 unsigned long ip) 5891 { 5892 if (!debug_locks_off()) 5893 return; 5894 if (debug_locks_silent) 5895 return; 5896 5897 pr_warn("\n"); 5898 pr_warn("=================================\n"); 5899 pr_warn("WARNING: bad contention detected!\n"); 5900 print_kernel_ident(); 5901 pr_warn("---------------------------------\n"); 5902 pr_warn("%s/%d is trying to contend lock (", 5903 curr->comm, task_pid_nr(curr)); 5904 print_lockdep_cache(lock); 5905 pr_cont(") at:\n"); 5906 print_ip_sym(KERN_WARNING, ip); 5907 pr_warn("but there are no locks held!\n"); 5908 pr_warn("\nother info that might help us debug this:\n"); 5909 lockdep_print_held_locks(curr); 5910 5911 pr_warn("\nstack backtrace:\n"); 5912 dump_stack(); 5913 } 5914 5915 static void 5916 __lock_contended(struct lockdep_map *lock, unsigned long ip) 5917 { 5918 struct task_struct *curr = current; 5919 struct held_lock *hlock; 5920 struct lock_class_stats *stats; 5921 unsigned int depth; 5922 int i, contention_point, contending_point; 5923 5924 depth = curr->lockdep_depth; 5925 /* 5926 * Whee, we contended on this lock, except it seems we're not 5927 * actually trying to acquire anything much at all.. 5928 */ 5929 if (DEBUG_LOCKS_WARN_ON(!depth)) 5930 return; 5931 5932 hlock = find_held_lock(curr, lock, depth, &i); 5933 if (!hlock) { 5934 print_lock_contention_bug(curr, lock, ip); 5935 return; 5936 } 5937 5938 if (hlock->instance != lock) 5939 return; 5940 5941 hlock->waittime_stamp = lockstat_clock(); 5942 5943 contention_point = lock_point(hlock_class(hlock)->contention_point, ip); 5944 contending_point = lock_point(hlock_class(hlock)->contending_point, 5945 lock->ip); 5946 5947 stats = get_lock_stats(hlock_class(hlock)); 5948 if (contention_point < LOCKSTAT_POINTS) 5949 stats->contention_point[contention_point]++; 5950 if (contending_point < LOCKSTAT_POINTS) 5951 stats->contending_point[contending_point]++; 5952 if (lock->cpu != smp_processor_id()) 5953 stats->bounces[bounce_contended + !!hlock->read]++; 5954 } 5955 5956 static void 5957 __lock_acquired(struct lockdep_map *lock, unsigned long ip) 5958 { 5959 struct task_struct *curr = current; 5960 struct held_lock *hlock; 5961 struct lock_class_stats *stats; 5962 unsigned int depth; 5963 u64 now, waittime = 0; 5964 int i, cpu; 5965 5966 depth = curr->lockdep_depth; 5967 /* 5968 * Yay, we acquired ownership of this lock we didn't try to 5969 * acquire, how the heck did that happen? 5970 */ 5971 if (DEBUG_LOCKS_WARN_ON(!depth)) 5972 return; 5973 5974 hlock = find_held_lock(curr, lock, depth, &i); 5975 if (!hlock) { 5976 print_lock_contention_bug(curr, lock, _RET_IP_); 5977 return; 5978 } 5979 5980 if (hlock->instance != lock) 5981 return; 5982 5983 cpu = smp_processor_id(); 5984 if (hlock->waittime_stamp) { 5985 now = lockstat_clock(); 5986 waittime = now - hlock->waittime_stamp; 5987 hlock->holdtime_stamp = now; 5988 } 5989 5990 stats = get_lock_stats(hlock_class(hlock)); 5991 if (waittime) { 5992 if (hlock->read) 5993 lock_time_inc(&stats->read_waittime, waittime); 5994 else 5995 lock_time_inc(&stats->write_waittime, waittime); 5996 } 5997 if (lock->cpu != cpu) 5998 stats->bounces[bounce_acquired + !!hlock->read]++; 5999 6000 lock->cpu = cpu; 6001 lock->ip = ip; 6002 } 6003 6004 void lock_contended(struct lockdep_map *lock, unsigned long ip) 6005 { 6006 unsigned long flags; 6007 6008 trace_lock_contended(lock, ip); 6009 6010 if (unlikely(!lock_stat || !lockdep_enabled())) 6011 return; 6012 6013 raw_local_irq_save(flags); 6014 check_flags(flags); 6015 lockdep_recursion_inc(); 6016 __lock_contended(lock, ip); 6017 lockdep_recursion_finish(); 6018 raw_local_irq_restore(flags); 6019 } 6020 EXPORT_SYMBOL_GPL(lock_contended); 6021 6022 void lock_acquired(struct lockdep_map *lock, unsigned long ip) 6023 { 6024 unsigned long flags; 6025 6026 trace_lock_acquired(lock, ip); 6027 6028 if (unlikely(!lock_stat || !lockdep_enabled())) 6029 return; 6030 6031 raw_local_irq_save(flags); 6032 check_flags(flags); 6033 lockdep_recursion_inc(); 6034 __lock_acquired(lock, ip); 6035 lockdep_recursion_finish(); 6036 raw_local_irq_restore(flags); 6037 } 6038 EXPORT_SYMBOL_GPL(lock_acquired); 6039 #endif 6040 6041 /* 6042 * Used by the testsuite, sanitize the validator state 6043 * after a simulated failure: 6044 */ 6045 6046 void lockdep_reset(void) 6047 { 6048 unsigned long flags; 6049 int i; 6050 6051 raw_local_irq_save(flags); 6052 lockdep_init_task(current); 6053 memset(current->held_locks, 0, MAX_LOCK_DEPTH*sizeof(struct held_lock)); 6054 nr_hardirq_chains = 0; 6055 nr_softirq_chains = 0; 6056 nr_process_chains = 0; 6057 debug_locks = 1; 6058 for (i = 0; i < CHAINHASH_SIZE; i++) 6059 INIT_HLIST_HEAD(chainhash_table + i); 6060 raw_local_irq_restore(flags); 6061 } 6062 6063 /* Remove a class from a lock chain. Must be called with the graph lock held. */ 6064 static void remove_class_from_lock_chain(struct pending_free *pf, 6065 struct lock_chain *chain, 6066 struct lock_class *class) 6067 { 6068 #ifdef CONFIG_PROVE_LOCKING 6069 int i; 6070 6071 for (i = chain->base; i < chain->base + chain->depth; i++) { 6072 if (chain_hlock_class_idx(chain_hlocks[i]) != class - lock_classes) 6073 continue; 6074 /* 6075 * Each lock class occurs at most once in a lock chain so once 6076 * we found a match we can break out of this loop. 6077 */ 6078 goto free_lock_chain; 6079 } 6080 /* Since the chain has not been modified, return. */ 6081 return; 6082 6083 free_lock_chain: 6084 free_chain_hlocks(chain->base, chain->depth); 6085 /* Overwrite the chain key for concurrent RCU readers. */ 6086 WRITE_ONCE(chain->chain_key, INITIAL_CHAIN_KEY); 6087 dec_chains(chain->irq_context); 6088 6089 /* 6090 * Note: calling hlist_del_rcu() from inside a 6091 * hlist_for_each_entry_rcu() loop is safe. 6092 */ 6093 hlist_del_rcu(&chain->entry); 6094 __set_bit(chain - lock_chains, pf->lock_chains_being_freed); 6095 nr_zapped_lock_chains++; 6096 #endif 6097 } 6098 6099 /* Must be called with the graph lock held. */ 6100 static void remove_class_from_lock_chains(struct pending_free *pf, 6101 struct lock_class *class) 6102 { 6103 struct lock_chain *chain; 6104 struct hlist_head *head; 6105 int i; 6106 6107 for (i = 0; i < ARRAY_SIZE(chainhash_table); i++) { 6108 head = chainhash_table + i; 6109 hlist_for_each_entry_rcu(chain, head, entry) { 6110 remove_class_from_lock_chain(pf, chain, class); 6111 } 6112 } 6113 } 6114 6115 /* 6116 * Remove all references to a lock class. The caller must hold the graph lock. 6117 */ 6118 static void zap_class(struct pending_free *pf, struct lock_class *class) 6119 { 6120 struct lock_list *entry; 6121 int i; 6122 6123 WARN_ON_ONCE(!class->key); 6124 6125 /* 6126 * Remove all dependencies this lock is 6127 * involved in: 6128 */ 6129 for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) { 6130 entry = list_entries + i; 6131 if (entry->class != class && entry->links_to != class) 6132 continue; 6133 __clear_bit(i, list_entries_in_use); 6134 nr_list_entries--; 6135 list_del_rcu(&entry->entry); 6136 } 6137 if (list_empty(&class->locks_after) && 6138 list_empty(&class->locks_before)) { 6139 list_move_tail(&class->lock_entry, &pf->zapped); 6140 hlist_del_rcu(&class->hash_entry); 6141 WRITE_ONCE(class->key, NULL); 6142 WRITE_ONCE(class->name, NULL); 6143 nr_lock_classes--; 6144 __clear_bit(class - lock_classes, lock_classes_in_use); 6145 if (class - lock_classes == max_lock_class_idx) 6146 max_lock_class_idx--; 6147 } else { 6148 WARN_ONCE(true, "%s() failed for class %s\n", __func__, 6149 class->name); 6150 } 6151 6152 remove_class_from_lock_chains(pf, class); 6153 nr_zapped_classes++; 6154 } 6155 6156 static void reinit_class(struct lock_class *class) 6157 { 6158 WARN_ON_ONCE(!class->lock_entry.next); 6159 WARN_ON_ONCE(!list_empty(&class->locks_after)); 6160 WARN_ON_ONCE(!list_empty(&class->locks_before)); 6161 memset_startat(class, 0, key); 6162 WARN_ON_ONCE(!class->lock_entry.next); 6163 WARN_ON_ONCE(!list_empty(&class->locks_after)); 6164 WARN_ON_ONCE(!list_empty(&class->locks_before)); 6165 } 6166 6167 static inline int within(const void *addr, void *start, unsigned long size) 6168 { 6169 return addr >= start && addr < start + size; 6170 } 6171 6172 static bool inside_selftest(void) 6173 { 6174 return current == lockdep_selftest_task_struct; 6175 } 6176 6177 /* The caller must hold the graph lock. */ 6178 static struct pending_free *get_pending_free(void) 6179 { 6180 return delayed_free.pf + delayed_free.index; 6181 } 6182 6183 static void free_zapped_rcu(struct rcu_head *cb); 6184 6185 /* 6186 * Schedule an RCU callback if no RCU callback is pending. Must be called with 6187 * the graph lock held. 6188 */ 6189 static void call_rcu_zapped(struct pending_free *pf) 6190 { 6191 WARN_ON_ONCE(inside_selftest()); 6192 6193 if (list_empty(&pf->zapped)) 6194 return; 6195 6196 if (delayed_free.scheduled) 6197 return; 6198 6199 delayed_free.scheduled = true; 6200 6201 WARN_ON_ONCE(delayed_free.pf + delayed_free.index != pf); 6202 delayed_free.index ^= 1; 6203 6204 call_rcu(&delayed_free.rcu_head, free_zapped_rcu); 6205 } 6206 6207 /* The caller must hold the graph lock. May be called from RCU context. */ 6208 static void __free_zapped_classes(struct pending_free *pf) 6209 { 6210 struct lock_class *class; 6211 6212 check_data_structures(); 6213 6214 list_for_each_entry(class, &pf->zapped, lock_entry) 6215 reinit_class(class); 6216 6217 list_splice_init(&pf->zapped, &free_lock_classes); 6218 6219 #ifdef CONFIG_PROVE_LOCKING 6220 bitmap_andnot(lock_chains_in_use, lock_chains_in_use, 6221 pf->lock_chains_being_freed, ARRAY_SIZE(lock_chains)); 6222 bitmap_clear(pf->lock_chains_being_freed, 0, ARRAY_SIZE(lock_chains)); 6223 #endif 6224 } 6225 6226 static void free_zapped_rcu(struct rcu_head *ch) 6227 { 6228 struct pending_free *pf; 6229 unsigned long flags; 6230 6231 if (WARN_ON_ONCE(ch != &delayed_free.rcu_head)) 6232 return; 6233 6234 raw_local_irq_save(flags); 6235 lockdep_lock(); 6236 6237 /* closed head */ 6238 pf = delayed_free.pf + (delayed_free.index ^ 1); 6239 __free_zapped_classes(pf); 6240 delayed_free.scheduled = false; 6241 6242 /* 6243 * If there's anything on the open list, close and start a new callback. 6244 */ 6245 call_rcu_zapped(delayed_free.pf + delayed_free.index); 6246 6247 lockdep_unlock(); 6248 raw_local_irq_restore(flags); 6249 } 6250 6251 /* 6252 * Remove all lock classes from the class hash table and from the 6253 * all_lock_classes list whose key or name is in the address range [start, 6254 * start + size). Move these lock classes to the zapped_classes list. Must 6255 * be called with the graph lock held. 6256 */ 6257 static void __lockdep_free_key_range(struct pending_free *pf, void *start, 6258 unsigned long size) 6259 { 6260 struct lock_class *class; 6261 struct hlist_head *head; 6262 int i; 6263 6264 /* Unhash all classes that were created by a module. */ 6265 for (i = 0; i < CLASSHASH_SIZE; i++) { 6266 head = classhash_table + i; 6267 hlist_for_each_entry_rcu(class, head, hash_entry) { 6268 if (!within(class->key, start, size) && 6269 !within(class->name, start, size)) 6270 continue; 6271 zap_class(pf, class); 6272 } 6273 } 6274 } 6275 6276 /* 6277 * Used in module.c to remove lock classes from memory that is going to be 6278 * freed; and possibly re-used by other modules. 6279 * 6280 * We will have had one synchronize_rcu() before getting here, so we're 6281 * guaranteed nobody will look up these exact classes -- they're properly dead 6282 * but still allocated. 6283 */ 6284 static void lockdep_free_key_range_reg(void *start, unsigned long size) 6285 { 6286 struct pending_free *pf; 6287 unsigned long flags; 6288 6289 init_data_structures_once(); 6290 6291 raw_local_irq_save(flags); 6292 lockdep_lock(); 6293 pf = get_pending_free(); 6294 __lockdep_free_key_range(pf, start, size); 6295 call_rcu_zapped(pf); 6296 lockdep_unlock(); 6297 raw_local_irq_restore(flags); 6298 6299 /* 6300 * Wait for any possible iterators from look_up_lock_class() to pass 6301 * before continuing to free the memory they refer to. 6302 */ 6303 synchronize_rcu(); 6304 } 6305 6306 /* 6307 * Free all lockdep keys in the range [start, start+size). Does not sleep. 6308 * Ignores debug_locks. Must only be used by the lockdep selftests. 6309 */ 6310 static void lockdep_free_key_range_imm(void *start, unsigned long size) 6311 { 6312 struct pending_free *pf = delayed_free.pf; 6313 unsigned long flags; 6314 6315 init_data_structures_once(); 6316 6317 raw_local_irq_save(flags); 6318 lockdep_lock(); 6319 __lockdep_free_key_range(pf, start, size); 6320 __free_zapped_classes(pf); 6321 lockdep_unlock(); 6322 raw_local_irq_restore(flags); 6323 } 6324 6325 void lockdep_free_key_range(void *start, unsigned long size) 6326 { 6327 init_data_structures_once(); 6328 6329 if (inside_selftest()) 6330 lockdep_free_key_range_imm(start, size); 6331 else 6332 lockdep_free_key_range_reg(start, size); 6333 } 6334 6335 /* 6336 * Check whether any element of the @lock->class_cache[] array refers to a 6337 * registered lock class. The caller must hold either the graph lock or the 6338 * RCU read lock. 6339 */ 6340 static bool lock_class_cache_is_registered(struct lockdep_map *lock) 6341 { 6342 struct lock_class *class; 6343 struct hlist_head *head; 6344 int i, j; 6345 6346 for (i = 0; i < CLASSHASH_SIZE; i++) { 6347 head = classhash_table + i; 6348 hlist_for_each_entry_rcu(class, head, hash_entry) { 6349 for (j = 0; j < NR_LOCKDEP_CACHING_CLASSES; j++) 6350 if (lock->class_cache[j] == class) 6351 return true; 6352 } 6353 } 6354 return false; 6355 } 6356 6357 /* The caller must hold the graph lock. Does not sleep. */ 6358 static void __lockdep_reset_lock(struct pending_free *pf, 6359 struct lockdep_map *lock) 6360 { 6361 struct lock_class *class; 6362 int j; 6363 6364 /* 6365 * Remove all classes this lock might have: 6366 */ 6367 for (j = 0; j < MAX_LOCKDEP_SUBCLASSES; j++) { 6368 /* 6369 * If the class exists we look it up and zap it: 6370 */ 6371 class = look_up_lock_class(lock, j); 6372 if (class) 6373 zap_class(pf, class); 6374 } 6375 /* 6376 * Debug check: in the end all mapped classes should 6377 * be gone. 6378 */ 6379 if (WARN_ON_ONCE(lock_class_cache_is_registered(lock))) 6380 debug_locks_off(); 6381 } 6382 6383 /* 6384 * Remove all information lockdep has about a lock if debug_locks == 1. Free 6385 * released data structures from RCU context. 6386 */ 6387 static void lockdep_reset_lock_reg(struct lockdep_map *lock) 6388 { 6389 struct pending_free *pf; 6390 unsigned long flags; 6391 int locked; 6392 6393 raw_local_irq_save(flags); 6394 locked = graph_lock(); 6395 if (!locked) 6396 goto out_irq; 6397 6398 pf = get_pending_free(); 6399 __lockdep_reset_lock(pf, lock); 6400 call_rcu_zapped(pf); 6401 6402 graph_unlock(); 6403 out_irq: 6404 raw_local_irq_restore(flags); 6405 } 6406 6407 /* 6408 * Reset a lock. Does not sleep. Ignores debug_locks. Must only be used by the 6409 * lockdep selftests. 6410 */ 6411 static void lockdep_reset_lock_imm(struct lockdep_map *lock) 6412 { 6413 struct pending_free *pf = delayed_free.pf; 6414 unsigned long flags; 6415 6416 raw_local_irq_save(flags); 6417 lockdep_lock(); 6418 __lockdep_reset_lock(pf, lock); 6419 __free_zapped_classes(pf); 6420 lockdep_unlock(); 6421 raw_local_irq_restore(flags); 6422 } 6423 6424 void lockdep_reset_lock(struct lockdep_map *lock) 6425 { 6426 init_data_structures_once(); 6427 6428 if (inside_selftest()) 6429 lockdep_reset_lock_imm(lock); 6430 else 6431 lockdep_reset_lock_reg(lock); 6432 } 6433 6434 /* 6435 * Unregister a dynamically allocated key. 6436 * 6437 * Unlike lockdep_register_key(), a search is always done to find a matching 6438 * key irrespective of debug_locks to avoid potential invalid access to freed 6439 * memory in lock_class entry. 6440 */ 6441 void lockdep_unregister_key(struct lock_class_key *key) 6442 { 6443 struct hlist_head *hash_head = keyhashentry(key); 6444 struct lock_class_key *k; 6445 struct pending_free *pf; 6446 unsigned long flags; 6447 bool found = false; 6448 6449 might_sleep(); 6450 6451 if (WARN_ON_ONCE(static_obj(key))) 6452 return; 6453 6454 raw_local_irq_save(flags); 6455 lockdep_lock(); 6456 6457 hlist_for_each_entry_rcu(k, hash_head, hash_entry) { 6458 if (k == key) { 6459 hlist_del_rcu(&k->hash_entry); 6460 found = true; 6461 break; 6462 } 6463 } 6464 WARN_ON_ONCE(!found && debug_locks); 6465 if (found) { 6466 pf = get_pending_free(); 6467 __lockdep_free_key_range(pf, key, 1); 6468 call_rcu_zapped(pf); 6469 } 6470 lockdep_unlock(); 6471 raw_local_irq_restore(flags); 6472 6473 /* Wait until is_dynamic_key() has finished accessing k->hash_entry. */ 6474 synchronize_rcu(); 6475 } 6476 EXPORT_SYMBOL_GPL(lockdep_unregister_key); 6477 6478 void __init lockdep_init(void) 6479 { 6480 printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n"); 6481 6482 printk("... MAX_LOCKDEP_SUBCLASSES: %lu\n", MAX_LOCKDEP_SUBCLASSES); 6483 printk("... MAX_LOCK_DEPTH: %lu\n", MAX_LOCK_DEPTH); 6484 printk("... MAX_LOCKDEP_KEYS: %lu\n", MAX_LOCKDEP_KEYS); 6485 printk("... CLASSHASH_SIZE: %lu\n", CLASSHASH_SIZE); 6486 printk("... MAX_LOCKDEP_ENTRIES: %lu\n", MAX_LOCKDEP_ENTRIES); 6487 printk("... MAX_LOCKDEP_CHAINS: %lu\n", MAX_LOCKDEP_CHAINS); 6488 printk("... CHAINHASH_SIZE: %lu\n", CHAINHASH_SIZE); 6489 6490 printk(" memory used by lock dependency info: %zu kB\n", 6491 (sizeof(lock_classes) + 6492 sizeof(lock_classes_in_use) + 6493 sizeof(classhash_table) + 6494 sizeof(list_entries) + 6495 sizeof(list_entries_in_use) + 6496 sizeof(chainhash_table) + 6497 sizeof(delayed_free) 6498 #ifdef CONFIG_PROVE_LOCKING 6499 + sizeof(lock_cq) 6500 + sizeof(lock_chains) 6501 + sizeof(lock_chains_in_use) 6502 + sizeof(chain_hlocks) 6503 #endif 6504 ) / 1024 6505 ); 6506 6507 #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) 6508 printk(" memory used for stack traces: %zu kB\n", 6509 (sizeof(stack_trace) + sizeof(stack_trace_hash)) / 1024 6510 ); 6511 #endif 6512 6513 printk(" per task-struct memory footprint: %zu bytes\n", 6514 sizeof(((struct task_struct *)NULL)->held_locks)); 6515 } 6516 6517 static void 6518 print_freed_lock_bug(struct task_struct *curr, const void *mem_from, 6519 const void *mem_to, struct held_lock *hlock) 6520 { 6521 if (!debug_locks_off()) 6522 return; 6523 if (debug_locks_silent) 6524 return; 6525 6526 pr_warn("\n"); 6527 pr_warn("=========================\n"); 6528 pr_warn("WARNING: held lock freed!\n"); 6529 print_kernel_ident(); 6530 pr_warn("-------------------------\n"); 6531 pr_warn("%s/%d is freeing memory %px-%px, with a lock still held there!\n", 6532 curr->comm, task_pid_nr(curr), mem_from, mem_to-1); 6533 print_lock(hlock); 6534 lockdep_print_held_locks(curr); 6535 6536 pr_warn("\nstack backtrace:\n"); 6537 dump_stack(); 6538 } 6539 6540 static inline int not_in_range(const void* mem_from, unsigned long mem_len, 6541 const void* lock_from, unsigned long lock_len) 6542 { 6543 return lock_from + lock_len <= mem_from || 6544 mem_from + mem_len <= lock_from; 6545 } 6546 6547 /* 6548 * Called when kernel memory is freed (or unmapped), or if a lock 6549 * is destroyed or reinitialized - this code checks whether there is 6550 * any held lock in the memory range of <from> to <to>: 6551 */ 6552 void debug_check_no_locks_freed(const void *mem_from, unsigned long mem_len) 6553 { 6554 struct task_struct *curr = current; 6555 struct held_lock *hlock; 6556 unsigned long flags; 6557 int i; 6558 6559 if (unlikely(!debug_locks)) 6560 return; 6561 6562 raw_local_irq_save(flags); 6563 for (i = 0; i < curr->lockdep_depth; i++) { 6564 hlock = curr->held_locks + i; 6565 6566 if (not_in_range(mem_from, mem_len, hlock->instance, 6567 sizeof(*hlock->instance))) 6568 continue; 6569 6570 print_freed_lock_bug(curr, mem_from, mem_from + mem_len, hlock); 6571 break; 6572 } 6573 raw_local_irq_restore(flags); 6574 } 6575 EXPORT_SYMBOL_GPL(debug_check_no_locks_freed); 6576 6577 static void print_held_locks_bug(void) 6578 { 6579 if (!debug_locks_off()) 6580 return; 6581 if (debug_locks_silent) 6582 return; 6583 6584 pr_warn("\n"); 6585 pr_warn("====================================\n"); 6586 pr_warn("WARNING: %s/%d still has locks held!\n", 6587 current->comm, task_pid_nr(current)); 6588 print_kernel_ident(); 6589 pr_warn("------------------------------------\n"); 6590 lockdep_print_held_locks(current); 6591 pr_warn("\nstack backtrace:\n"); 6592 dump_stack(); 6593 } 6594 6595 void debug_check_no_locks_held(void) 6596 { 6597 if (unlikely(current->lockdep_depth > 0)) 6598 print_held_locks_bug(); 6599 } 6600 EXPORT_SYMBOL_GPL(debug_check_no_locks_held); 6601 6602 #ifdef __KERNEL__ 6603 void debug_show_all_locks(void) 6604 { 6605 struct task_struct *g, *p; 6606 6607 if (unlikely(!debug_locks)) { 6608 pr_warn("INFO: lockdep is turned off.\n"); 6609 return; 6610 } 6611 pr_warn("\nShowing all locks held in the system:\n"); 6612 6613 rcu_read_lock(); 6614 for_each_process_thread(g, p) { 6615 if (!p->lockdep_depth) 6616 continue; 6617 lockdep_print_held_locks(p); 6618 touch_nmi_watchdog(); 6619 touch_all_softlockup_watchdogs(); 6620 } 6621 rcu_read_unlock(); 6622 6623 pr_warn("\n"); 6624 pr_warn("=============================================\n\n"); 6625 } 6626 EXPORT_SYMBOL_GPL(debug_show_all_locks); 6627 #endif 6628 6629 /* 6630 * Careful: only use this function if you are sure that 6631 * the task cannot run in parallel! 6632 */ 6633 void debug_show_held_locks(struct task_struct *task) 6634 { 6635 if (unlikely(!debug_locks)) { 6636 printk("INFO: lockdep is turned off.\n"); 6637 return; 6638 } 6639 lockdep_print_held_locks(task); 6640 } 6641 EXPORT_SYMBOL_GPL(debug_show_held_locks); 6642 6643 asmlinkage __visible void lockdep_sys_exit(void) 6644 { 6645 struct task_struct *curr = current; 6646 6647 if (unlikely(curr->lockdep_depth)) { 6648 if (!debug_locks_off()) 6649 return; 6650 pr_warn("\n"); 6651 pr_warn("================================================\n"); 6652 pr_warn("WARNING: lock held when returning to user space!\n"); 6653 print_kernel_ident(); 6654 pr_warn("------------------------------------------------\n"); 6655 pr_warn("%s/%d is leaving the kernel with locks still held!\n", 6656 curr->comm, curr->pid); 6657 lockdep_print_held_locks(curr); 6658 } 6659 6660 /* 6661 * The lock history for each syscall should be independent. So wipe the 6662 * slate clean on return to userspace. 6663 */ 6664 lockdep_invariant_state(false); 6665 } 6666 6667 void lockdep_rcu_suspicious(const char *file, const int line, const char *s) 6668 { 6669 struct task_struct *curr = current; 6670 int dl = READ_ONCE(debug_locks); 6671 bool rcu = warn_rcu_enter(); 6672 6673 /* Note: the following can be executed concurrently, so be careful. */ 6674 pr_warn("\n"); 6675 pr_warn("=============================\n"); 6676 pr_warn("WARNING: suspicious RCU usage\n"); 6677 print_kernel_ident(); 6678 pr_warn("-----------------------------\n"); 6679 pr_warn("%s:%d %s!\n", file, line, s); 6680 pr_warn("\nother info that might help us debug this:\n\n"); 6681 pr_warn("\n%srcu_scheduler_active = %d, debug_locks = %d\n%s", 6682 !rcu_lockdep_current_cpu_online() 6683 ? "RCU used illegally from offline CPU!\n" 6684 : "", 6685 rcu_scheduler_active, dl, 6686 dl ? "" : "Possible false positive due to lockdep disabling via debug_locks = 0\n"); 6687 6688 /* 6689 * If a CPU is in the RCU-free window in idle (ie: in the section 6690 * between ct_idle_enter() and ct_idle_exit(), then RCU 6691 * considers that CPU to be in an "extended quiescent state", 6692 * which means that RCU will be completely ignoring that CPU. 6693 * Therefore, rcu_read_lock() and friends have absolutely no 6694 * effect on a CPU running in that state. In other words, even if 6695 * such an RCU-idle CPU has called rcu_read_lock(), RCU might well 6696 * delete data structures out from under it. RCU really has no 6697 * choice here: we need to keep an RCU-free window in idle where 6698 * the CPU may possibly enter into low power mode. This way we can 6699 * notice an extended quiescent state to other CPUs that started a grace 6700 * period. Otherwise we would delay any grace period as long as we run 6701 * in the idle task. 6702 * 6703 * So complain bitterly if someone does call rcu_read_lock(), 6704 * rcu_read_lock_bh() and so on from extended quiescent states. 6705 */ 6706 if (!rcu_is_watching()) 6707 pr_warn("RCU used illegally from extended quiescent state!\n"); 6708 6709 lockdep_print_held_locks(curr); 6710 pr_warn("\nstack backtrace:\n"); 6711 dump_stack(); 6712 warn_rcu_exit(rcu); 6713 } 6714 EXPORT_SYMBOL_GPL(lockdep_rcu_suspicious);