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