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