1 /* $NetBSD: subr_lockdebug.c,v 1.4 2007/02/22 06:34:44 thorpej Exp $ */ 2 3 /*- 4 * Copyright (c) 2006, 2007 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Andrew Doran. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the NetBSD 21 * Foundation, Inc. and its contributors. 22 * 4. Neither the name of The NetBSD Foundation nor the names of its 23 * contributors may be used to endorse or promote products derived 24 * from this software without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 27 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 28 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 29 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 30 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 31 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 32 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 33 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 34 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 35 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 36 * POSSIBILITY OF SUCH DAMAGE. 37 */ 38 39 /* 40 * Basic lock debugging code shared among lock primatives. 41 */ 42 43 #include "opt_multiprocessor.h" 44 #include "opt_ddb.h" 45 46 #include <sys/cdefs.h> 47 __KERNEL_RCSID(0, "$NetBSD: subr_lockdebug.c,v 1.4 2007/02/22 06:34:44 thorpej Exp $"); 48 49 #include <sys/param.h> 50 #include <sys/proc.h> 51 #include <sys/systm.h> 52 #include <sys/kmem.h> 53 #include <sys/lock.h> 54 #include <sys/lockdebug.h> 55 #include <sys/sleepq.h> 56 57 #include <machine/cpu.h> 58 59 #ifdef LOCKDEBUG 60 61 #define LD_BATCH_SHIFT 9 62 #define LD_BATCH (1 << LD_BATCH_SHIFT) 63 #define LD_BATCH_MASK (LD_BATCH - 1) 64 #define LD_MAX_LOCKS 1048576 65 #define LD_SLOP 16 66 67 #define LD_LOCKED 0x01 68 #define LD_SLEEPER 0x02 69 70 #define LD_NOID LD_MAX_LOCKS 71 72 typedef union lockdebuglk { 73 struct { 74 __cpu_simple_lock_t lku_lock; 75 int lku_oldspl; 76 } ul; 77 uint8_t lk_pad[64]; 78 } volatile __aligned(64) lockdebuglk_t; 79 80 #define lk_lock ul.lku_lock 81 #define lk_oldspl ul.lku_oldspl 82 83 typedef struct lockdebug { 84 _TAILQ_ENTRY(struct lockdebug, volatile) ld_chain; 85 _TAILQ_ENTRY(struct lockdebug, volatile) ld_achain; 86 volatile void *ld_lock; 87 lockops_t *ld_lockops; 88 struct lwp *ld_lwp; 89 uintptr_t ld_locked; 90 uintptr_t ld_unlocked; 91 u_int ld_id; 92 uint16_t ld_shares; 93 uint16_t ld_cpu; 94 uint8_t ld_flags; 95 uint8_t ld_shwant; /* advisory */ 96 uint8_t ld_exwant; /* advisory */ 97 uint8_t ld_unused; 98 } volatile lockdebug_t; 99 100 typedef _TAILQ_HEAD(lockdebuglist, struct lockdebug, volatile) lockdebuglist_t; 101 102 lockdebuglk_t ld_sleeper_lk; 103 lockdebuglk_t ld_spinner_lk; 104 lockdebuglk_t ld_free_lk; 105 106 lockdebuglist_t ld_sleepers; 107 lockdebuglist_t ld_spinners; 108 lockdebuglist_t ld_free; 109 lockdebuglist_t ld_all; 110 int ld_nfree; 111 int ld_freeptr; 112 int ld_recurse; 113 lockdebug_t *ld_table[LD_MAX_LOCKS / LD_BATCH]; 114 115 lockdebug_t ld_prime[LD_BATCH]; 116 117 void lockdebug_abort1(lockdebug_t *, lockdebuglk_t *lk, const char *, 118 const char *); 119 void lockdebug_more(void); 120 121 static inline void 122 lockdebug_lock(lockdebuglk_t *lk) 123 { 124 int s; 125 126 s = spllock(); 127 __cpu_simple_lock(&lk->lk_lock); 128 lk->lk_oldspl = s; 129 } 130 131 static inline void 132 lockdebug_unlock(lockdebuglk_t *lk) 133 { 134 int s; 135 136 s = lk->lk_oldspl; 137 __cpu_simple_unlock(&(lk->lk_lock)); 138 splx(s); 139 } 140 141 /* 142 * lockdebug_lookup: 143 * 144 * Find a lockdebug structure by ID and return it locked. 145 */ 146 static inline lockdebug_t * 147 lockdebug_lookup(u_int id, lockdebuglk_t **lk) 148 { 149 lockdebug_t *base, *ld; 150 151 if (id == LD_NOID) 152 return NULL; 153 154 if (id == 0 || id >= LD_MAX_LOCKS) 155 panic("lockdebug_lookup: uninitialized lock (1, id=%d)", id); 156 157 base = ld_table[id >> LD_BATCH_SHIFT]; 158 ld = base + (id & LD_BATCH_MASK); 159 160 if (base == NULL || ld->ld_lock == NULL || ld->ld_id != id) 161 panic("lockdebug_lookup: uninitialized lock (2, id=%d)", id); 162 163 if ((ld->ld_flags & LD_SLEEPER) != 0) 164 *lk = &ld_sleeper_lk; 165 else 166 *lk = &ld_spinner_lk; 167 168 lockdebug_lock(*lk); 169 return ld; 170 } 171 172 /* 173 * lockdebug_init: 174 * 175 * Initialize the lockdebug system. Allocate an initial pool of 176 * lockdebug structures before the VM system is up and running. 177 */ 178 void 179 lockdebug_init(void) 180 { 181 lockdebug_t *ld; 182 int i; 183 184 __cpu_simple_lock_init(&ld_sleeper_lk.lk_lock); 185 __cpu_simple_lock_init(&ld_spinner_lk.lk_lock); 186 __cpu_simple_lock_init(&ld_free_lk.lk_lock); 187 188 TAILQ_INIT(&ld_free); 189 TAILQ_INIT(&ld_all); 190 TAILQ_INIT(&ld_sleepers); 191 TAILQ_INIT(&ld_spinners); 192 193 ld = ld_prime; 194 ld_table[0] = ld; 195 for (i = 1, ld++; i < LD_BATCH; i++, ld++) { 196 ld->ld_id = i; 197 TAILQ_INSERT_TAIL(&ld_free, ld, ld_chain); 198 TAILQ_INSERT_TAIL(&ld_all, ld, ld_achain); 199 } 200 ld_freeptr = 1; 201 ld_nfree = LD_BATCH - 1; 202 } 203 204 /* 205 * lockdebug_alloc: 206 * 207 * A lock is being initialized, so allocate an associated debug 208 * structure. 209 */ 210 u_int 211 lockdebug_alloc(volatile void *lock, lockops_t *lo) 212 { 213 struct cpu_info *ci; 214 lockdebug_t *ld; 215 216 if (ld_freeptr == 0) { 217 printf("lockdebug_alloc: not initialized yet, lock=%p\n", 218 __UNVOLATILE(lock)); 219 return LD_NOID; 220 } 221 222 if (panicstr != NULL) 223 return LD_NOID; 224 225 ci = curcpu(); 226 227 /* 228 * Pinch a new debug structure. We may recurse because we call 229 * kmem_alloc(), which may need to initialize new locks somewhere 230 * down the path. If not recursing, we try to maintain at keep 231 * LD_SLOP structures free, which should hopefully be enough to 232 * satisfy kmem_alloc(). If we can't provide a structure, not to 233 * worry: we'll just mark the lock as not having an ID. 234 */ 235 lockdebug_lock(&ld_free_lk); 236 ci->ci_lkdebug_recurse++; 237 238 if (TAILQ_EMPTY(&ld_free)) { 239 if (ci->ci_lkdebug_recurse > 1) { 240 ci->ci_lkdebug_recurse--; 241 lockdebug_unlock(&ld_free_lk); 242 return LD_NOID; 243 } 244 lockdebug_more(); 245 } else if (ci->ci_lkdebug_recurse == 1 && ld_nfree < LD_SLOP) 246 lockdebug_more(); 247 248 if ((ld = TAILQ_FIRST(&ld_free)) == NULL) { 249 lockdebug_unlock(&ld_free_lk); 250 return LD_NOID; 251 } 252 253 TAILQ_REMOVE(&ld_free, ld, ld_chain); 254 ld_nfree--; 255 256 ci->ci_lkdebug_recurse--; 257 lockdebug_unlock(&ld_free_lk); 258 259 if (ld->ld_lock != NULL) 260 panic("lockdebug_alloc: corrupt table"); 261 262 if (lo->lo_sleeplock) 263 lockdebug_lock(&ld_sleeper_lk); 264 else 265 lockdebug_lock(&ld_spinner_lk); 266 267 /* Initialise the structure. */ 268 ld->ld_lock = lock; 269 ld->ld_lockops = lo; 270 ld->ld_locked = 0; 271 ld->ld_unlocked = 0; 272 ld->ld_lwp = NULL; 273 274 if (lo->lo_sleeplock) { 275 ld->ld_flags = LD_SLEEPER; 276 lockdebug_unlock(&ld_sleeper_lk); 277 } else { 278 ld->ld_flags = 0; 279 lockdebug_unlock(&ld_spinner_lk); 280 } 281 282 return ld->ld_id; 283 } 284 285 /* 286 * lockdebug_free: 287 * 288 * A lock is being destroyed, so release debugging resources. 289 */ 290 void 291 lockdebug_free(volatile void *lock, u_int id) 292 { 293 lockdebug_t *ld; 294 lockdebuglk_t *lk; 295 296 if (panicstr != NULL) 297 return; 298 299 if ((ld = lockdebug_lookup(id, &lk)) == NULL) 300 return; 301 302 if (ld->ld_lock != lock) { 303 panic("lockdebug_free: destroying uninitialized lock %p" 304 "(ld_id=%d ld_lock=%p)", lock, id, ld->ld_lock); 305 lockdebug_abort1(ld, lk, __func__, "lock record follows"); 306 } 307 if ((ld->ld_flags & LD_LOCKED) != 0 || ld->ld_shares != 0) 308 lockdebug_abort1(ld, lk, __func__, "is locked"); 309 310 ld->ld_lock = NULL; 311 312 lockdebug_unlock(lk); 313 314 lockdebug_lock(&ld_free_lk); 315 TAILQ_INSERT_TAIL(&ld_free, ld, ld_chain); 316 ld_nfree++; 317 lockdebug_unlock(&ld_free_lk); 318 } 319 320 /* 321 * lockdebug_more: 322 * 323 * Allocate a batch of debug structures and add to the free list. 324 * Must be called with ld_free_lk held. 325 */ 326 void 327 lockdebug_more(void) 328 { 329 lockdebug_t *ld; 330 void *block; 331 int i, base; 332 333 while (ld_nfree < LD_SLOP) { 334 lockdebug_unlock(&ld_free_lk); 335 block = kmem_zalloc(LD_BATCH * sizeof(lockdebug_t), KM_SLEEP); 336 lockdebug_lock(&ld_free_lk); 337 338 if (block == NULL) 339 return; 340 341 if (ld_nfree > LD_SLOP) { 342 /* Somebody beat us to it. */ 343 lockdebug_unlock(&ld_free_lk); 344 kmem_free(block, LD_BATCH * sizeof(lockdebug_t)); 345 lockdebug_lock(&ld_free_lk); 346 continue; 347 } 348 349 base = ld_freeptr; 350 ld_nfree += LD_BATCH; 351 ld = block; 352 base <<= LD_BATCH_SHIFT; 353 354 for (i = 0; i < LD_BATCH; i++, ld++) { 355 ld->ld_id = i + base; 356 TAILQ_INSERT_TAIL(&ld_free, ld, ld_chain); 357 TAILQ_INSERT_TAIL(&ld_all, ld, ld_achain); 358 } 359 360 mb_write(); 361 ld_table[ld_freeptr++] = block; 362 } 363 } 364 365 /* 366 * lockdebug_wantlock: 367 * 368 * Process the preamble to a lock acquire. 369 */ 370 void 371 lockdebug_wantlock(u_int id, uintptr_t where, int shared) 372 { 373 struct lwp *l = curlwp; 374 lockdebuglk_t *lk; 375 lockdebug_t *ld; 376 bool recurse; 377 378 (void)shared; 379 recurse = false; 380 381 if (panicstr != NULL) 382 return; 383 384 if ((ld = lockdebug_lookup(id, &lk)) == NULL) 385 return; 386 387 if ((ld->ld_flags & LD_LOCKED) != 0) { 388 if ((ld->ld_flags & LD_SLEEPER) != 0) { 389 if (ld->ld_lwp == l) 390 recurse = true; 391 } else if (ld->ld_cpu == (uint16_t)cpu_number()) 392 recurse = true; 393 } 394 395 if (shared) 396 ld->ld_shwant++; 397 else 398 ld->ld_exwant++; 399 400 if (recurse) 401 lockdebug_abort1(ld, lk, __func__, "locking against myself"); 402 403 lockdebug_unlock(lk); 404 } 405 406 /* 407 * lockdebug_locked: 408 * 409 * Process a lock acquire operation. 410 */ 411 void 412 lockdebug_locked(u_int id, uintptr_t where, int shared) 413 { 414 struct lwp *l = curlwp; 415 lockdebuglk_t *lk; 416 lockdebug_t *ld; 417 418 if (panicstr != NULL) 419 return; 420 421 if ((ld = lockdebug_lookup(id, &lk)) == NULL) 422 return; 423 424 if (shared) { 425 l->l_shlocks++; 426 ld->ld_shares++; 427 ld->ld_shwant--; 428 } else { 429 if ((ld->ld_flags & LD_LOCKED) != 0) 430 lockdebug_abort1(ld, lk, __func__, 431 "already locked"); 432 433 ld->ld_flags |= LD_LOCKED; 434 ld->ld_locked = where; 435 ld->ld_cpu = (uint16_t)cpu_number(); 436 ld->ld_lwp = l; 437 ld->ld_exwant--; 438 439 if ((ld->ld_flags & LD_SLEEPER) != 0) { 440 l->l_exlocks++; 441 TAILQ_INSERT_TAIL(&ld_sleepers, ld, ld_chain); 442 } else { 443 curcpu()->ci_spin_locks2++; 444 TAILQ_INSERT_TAIL(&ld_spinners, ld, ld_chain); 445 } 446 } 447 448 lockdebug_unlock(lk); 449 } 450 451 /* 452 * lockdebug_unlocked: 453 * 454 * Process a lock release operation. 455 */ 456 void 457 lockdebug_unlocked(u_int id, uintptr_t where, int shared) 458 { 459 struct lwp *l = curlwp; 460 lockdebuglk_t *lk; 461 lockdebug_t *ld; 462 463 if (panicstr != NULL) 464 return; 465 466 if ((ld = lockdebug_lookup(id, &lk)) == NULL) 467 return; 468 469 if (shared) { 470 if (l->l_shlocks == 0) 471 lockdebug_abort1(ld, lk, __func__, 472 "no shared locks held by LWP"); 473 if (ld->ld_shares == 0) 474 lockdebug_abort1(ld, lk, __func__, 475 "no shared holds on this lock"); 476 l->l_shlocks--; 477 ld->ld_shares--; 478 } else { 479 if ((ld->ld_flags & LD_LOCKED) == 0) 480 lockdebug_abort1(ld, lk, __func__, "not locked"); 481 482 if ((ld->ld_flags & LD_SLEEPER) != 0) { 483 if (ld->ld_lwp != curlwp) 484 lockdebug_abort1(ld, lk, __func__, 485 "not held by current LWP"); 486 ld->ld_flags &= ~LD_LOCKED; 487 ld->ld_unlocked = where; 488 ld->ld_lwp = NULL; 489 curlwp->l_exlocks--; 490 TAILQ_REMOVE(&ld_sleepers, ld, ld_chain); 491 } else { 492 if (ld->ld_cpu != (uint16_t)cpu_number()) 493 lockdebug_abort1(ld, lk, __func__, 494 "not held by current CPU"); 495 ld->ld_flags &= ~LD_LOCKED; 496 ld->ld_unlocked = where; 497 ld->ld_lwp = NULL; 498 curcpu()->ci_spin_locks2--; 499 TAILQ_REMOVE(&ld_spinners, ld, ld_chain); 500 } 501 } 502 503 lockdebug_unlock(lk); 504 } 505 506 /* 507 * lockdebug_barrier: 508 * 509 * Panic if we hold more than one specified spin lock, and optionally, 510 * if we hold sleep locks. 511 */ 512 void 513 lockdebug_barrier(volatile void *spinlock, int slplocks) 514 { 515 struct lwp *l = curlwp; 516 lockdebug_t *ld; 517 uint16_t cpuno; 518 519 if (panicstr != NULL) 520 return; 521 522 if (curcpu()->ci_spin_locks2 != 0) { 523 cpuno = (uint16_t)cpu_number(); 524 525 lockdebug_lock(&ld_spinner_lk); 526 TAILQ_FOREACH(ld, &ld_spinners, ld_chain) { 527 if (ld->ld_lock == spinlock) { 528 if (ld->ld_cpu != cpuno) 529 lockdebug_abort1(ld, &ld_spinner_lk, 530 __func__, 531 "not held by current CPU"); 532 continue; 533 } 534 if (ld->ld_cpu == cpuno) 535 lockdebug_abort1(ld, &ld_spinner_lk, 536 __func__, "spin lock held"); 537 } 538 lockdebug_unlock(&ld_spinner_lk); 539 } 540 541 if (!slplocks) { 542 if (l->l_exlocks != 0) { 543 lockdebug_lock(&ld_sleeper_lk); 544 TAILQ_FOREACH(ld, &ld_sleepers, ld_chain) { 545 if (ld->ld_lwp == l) 546 lockdebug_abort1(ld, &ld_sleeper_lk, 547 __func__, "sleep lock held"); 548 } 549 lockdebug_unlock(&ld_sleeper_lk); 550 } 551 if (l->l_shlocks != 0) 552 panic("lockdebug_barrier: holding %d shared locks", 553 l->l_shlocks); 554 } 555 } 556 557 /* 558 * lockdebug_dump: 559 * 560 * Dump information about a lock on panic, or for DDB. 561 */ 562 static void 563 lockdebug_dump(lockdebug_t *ld, void (*pr)(const char *, ...)) 564 { 565 int sleeper = (ld->ld_flags & LD_SLEEPER); 566 567 (*pr)( 568 "lock address : %#018lx type : %18s\n" 569 "shared holds : %18u exclusive: %18u\n" 570 "shares wanted: %18u exclusive: %18u\n" 571 "current cpu : %18u last held: %18u\n" 572 "current lwp : %#018lx last held: %#018lx\n" 573 "last locked : %#018lx unlocked : %#018lx\n", 574 (long)ld->ld_lock, (sleeper ? "sleep/adaptive" : "spin"), 575 (unsigned)ld->ld_shares, ((ld->ld_flags & LD_LOCKED) != 0), 576 (unsigned)ld->ld_shwant, (unsigned)ld->ld_exwant, 577 (unsigned)cpu_number(), (unsigned)ld->ld_cpu, 578 (long)curlwp, (long)ld->ld_lwp, 579 (long)ld->ld_locked, (long)ld->ld_unlocked); 580 581 if (ld->ld_lockops->lo_dump != NULL) 582 (*ld->ld_lockops->lo_dump)(ld->ld_lock); 583 584 if (sleeper) { 585 (*pr)("\n"); 586 turnstile_print(ld->ld_lock, pr); 587 } 588 } 589 590 /* 591 * lockdebug_dump: 592 * 593 * Dump information about a known lock. 594 */ 595 void 596 lockdebug_abort1(lockdebug_t *ld, lockdebuglk_t *lk, const char *func, 597 const char *msg) 598 { 599 600 printf_nolog("%s error: %s: %s\n\n", ld->ld_lockops->lo_name, 601 func, msg); 602 lockdebug_dump(ld, printf_nolog); 603 lockdebug_unlock(lk); 604 printf_nolog("\n"); 605 panic("LOCKDEBUG"); 606 } 607 608 #endif /* LOCKDEBUG */ 609 610 /* 611 * lockdebug_lock_print: 612 * 613 * Handle the DDB 'show lock' command. 614 */ 615 #ifdef DDB 616 void 617 lockdebug_lock_print(void *addr, void (*pr)(const char *, ...)) 618 { 619 #ifdef LOCKDEBUG 620 lockdebug_t *ld; 621 622 TAILQ_FOREACH(ld, &ld_all, ld_achain) { 623 if (ld->ld_lock == addr) { 624 lockdebug_dump(ld, pr); 625 return; 626 } 627 } 628 (*pr)("Sorry, no record of a lock with address %p found.\n", addr); 629 #else 630 (*pr)("Sorry, kernel not built with the LOCKDEBUG option.\n"); 631 #endif /* LOCKDEBUG */ 632 } 633 #endif /* DDB */ 634 635 /* 636 * lockdebug_abort: 637 * 638 * An error has been trapped - dump lock info and call panic(). 639 */ 640 void 641 lockdebug_abort(int id, volatile void *lock, lockops_t *ops, 642 const char *func, const char *msg) 643 { 644 #ifdef LOCKDEBUG 645 lockdebug_t *ld; 646 lockdebuglk_t *lk; 647 648 if ((ld = lockdebug_lookup(id, &lk)) != NULL) { 649 lockdebug_abort1(ld, lk, func, msg); 650 /* NOTREACHED */ 651 } 652 #endif /* LOCKDEBUG */ 653 654 printf_nolog("%s error: %s: %s\n\n" 655 "lock address : %#018lx\n" 656 "current cpu : %18d\n" 657 "current lwp : %#018lx\n", 658 ops->lo_name, func, msg, (long)lock, (int)cpu_number(), 659 (long)curlwp); 660 661 (*ops->lo_dump)(lock); 662 663 printf_nolog("\n"); 664 panic("lock error"); 665 } 666