1/*-
2 * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
--- 13 unchanged lines hidden (view full) ---
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 *
28 * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
29 * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
30 * $FreeBSD: head/sys/kern/subr_witness.c 74912 2001-03-28 09:03:24Z jhb $
31 */
32
33/*
34 * Implementation of the `witness' lock verifier. Originally implemented for
35 * mutexes in BSD/OS. Extended to handle generic lock objects and lock
36 * classes in FreeBSD.
37 */
38
39/*
40 * Main Entry: witness
41 * Pronunciation: 'wit-n&s
42 * Function: noun
43 * Etymology: Middle English witnesse, from Old English witnes knowledge,
44 * testimony, witness, from 2wit
--- 12 unchanged lines hidden (view full) ---
57 */
58
59#include "opt_ddb.h"
60#include "opt_witness.h"
61
62#include <sys/param.h>
63#include <sys/bus.h>
64#include <sys/kernel.h>
65#include <sys/ktr.h>
66#include <sys/lock.h>
67#include <sys/malloc.h>
68#include <sys/mutex.h>
69#include <sys/proc.h>
70#include <sys/sysctl.h>
71#include <sys/systm.h>
72
73#include <ddb/ddb.h>
74
75#define WITNESS_COUNT 200
76#define WITNESS_CHILDCOUNT (WITNESS_COUNT * 4)
77/*
78 * XXX: This is somewhat bogus, as we assume here that at most 1024 processes
79 * will hold LOCK_NCHILDREN * 2 locks. We handle failure ok, and we should
80 * probably be safe for the most part, but it's still a SWAG.
81 */
82#define LOCK_CHILDCOUNT (MAXCPU + 1024) * 2
83
84#define WITNESS_NCHILDREN 6
85
86struct witness_child_list_entry;
87
88struct witness {
89 const char *w_name;
90 struct lock_class *w_class;
91 STAILQ_ENTRY(witness) w_list; /* List of all witnesses. */
92 STAILQ_ENTRY(witness) w_typelist; /* Witnesses of a type. */
93 struct witness_child_list_entry *w_children; /* Great evilness... */
94 const char *w_file;
95 int w_line;
96 u_int w_level;
97 u_int w_refcount;
98 u_char w_Giant_squawked:1;
99 u_char w_other_squawked:1;
100 u_char w_same_squawked:1;
101};
102
103struct witness_child_list_entry {
104 struct witness_child_list_entry *wcl_next;
105 struct witness *wcl_children[WITNESS_NCHILDREN];
106 u_int wcl_count;
107};
108
109STAILQ_HEAD(witness_list, witness);
110
111struct witness_blessed {
112 const char *b_lock1;
113 const char *b_lock2;
114};
115
116struct witness_order_list_entry {
117 const char *w_name;
118 struct lock_class *w_class;
119};
120
121static struct witness *enroll(const char *description,
122 struct lock_class *lock_class);
123static int itismychild(struct witness *parent, struct witness *child);
124static void removechild(struct witness *parent, struct witness *child);
125static int isitmychild(struct witness *parent, struct witness *child);
126static int isitmydescendant(struct witness *parent, struct witness *child);
127static int dup_ok(struct witness *);
128static int blessed(struct witness *, struct witness *);
129static void witness_display_list(void(*prnt)(const char *fmt, ...),
130 struct witness_list *list);
131static void witness_displaydescendants(void(*)(const char *fmt, ...),
132 struct witness *);
133static void witness_leveldescendents(struct witness *parent, int level);
134static void witness_levelall(void);
135static struct witness *witness_get(void);
136static void witness_free(struct witness *m);
137static struct witness_child_list_entry *witness_child_get(void);
138static void witness_child_free(struct witness_child_list_entry *wcl);
139static struct lock_list_entry *witness_lock_list_get(void);
140static void witness_lock_list_free(struct lock_list_entry *lle);
141static void witness_display(void(*)(const char *fmt, ...));
142
143MALLOC_DEFINE(M_WITNESS, "witness", "witness structure");
144
145static int witness_watch;
146TUNABLE_INT_DECL("debug.witness_watch", 1, witness_watch);
147SYSCTL_INT(_debug, OID_AUTO, witness_watch, CTLFLAG_RD, &witness_watch, 0, "");
148
149#ifdef DDB
150/*
151 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to
152 * drop into kdebug() when:
153 * - a lock heirarchy violation occurs
154 * - locks are held when going to sleep.
155 */
156int witness_ddb;
157#ifdef WITNESS_DDB
158TUNABLE_INT_DECL("debug.witness_ddb", 1, witness_ddb);
--- 7 unchanged lines hidden (view full) ---
166#ifdef WITNESS_SKIPSPIN
167TUNABLE_INT_DECL("debug.witness_skipspin", 1, witness_skipspin);
168#else
169TUNABLE_INT_DECL("debug.witness_skipspin", 0, witness_skipspin);
170#endif
171SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0,
172 "");
173
174static struct mtx w_mtx;
175static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free);
176static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all);
177static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin);
178static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep);
179static struct witness_child_list_entry *w_child_free = NULL;
180static struct lock_list_entry *w_lock_list_free = NULL;
181static int witness_dead; /* fatal error, probably no memory */
182
183static struct witness w_data[WITNESS_COUNT];
184static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT];
185static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
186
187static struct witness_order_list_entry order_lists[] = {
188 { "Giant", &lock_class_mtx_sleep },
189 { "proctree", &lock_class_sx },
190 { "allproc", &lock_class_sx },
191 { "process lock", &lock_class_mtx_sleep },
192 { "uidinfo hash", &lock_class_mtx_sleep },
193 { "uidinfo struct", &lock_class_mtx_sleep },
194 { NULL, NULL },
195#if defined(__i386__) && defined (SMP)
196 { "com", &lock_class_mtx_spin },
197#endif
198 { "sio", &lock_class_mtx_spin },
199#ifdef __i386__
200 { "cy", &lock_class_mtx_spin },
201#endif
202 { "ng_node", &lock_class_mtx_spin },
203 { "ng_worklist", &lock_class_mtx_spin },
204 { "ithread table lock", &lock_class_mtx_spin },
205 { "ithread list lock", &lock_class_mtx_spin },
206 { "sched lock", &lock_class_mtx_spin },
207#ifdef __i386__
208 { "clk", &lock_class_mtx_spin },
209#endif
210 { "callout", &lock_class_mtx_spin },
211 /*
212 * leaf locks
213 */
214#ifdef SMP
215#ifdef __i386__
216 { "ap boot", &lock_class_mtx_spin },
217 { "imen", &lock_class_mtx_spin },
218#endif
219 { "smp rendezvous", &lock_class_mtx_spin },
220#endif
221 { NULL, NULL },
222 { NULL, NULL }
223};
224
225static const char *dup_list[] = {
226 "process lock",
227 NULL
228};
229
230/*
231 * Pairs of locks which have been blessed
232 * Don't complain about order problems with blessed locks
233 */
234static struct witness_blessed blessed_list[] = {
235};
236static int blessed_count =
237 sizeof(blessed_list) / sizeof(struct witness_blessed);
238
239/*
240 * List of all locks in the system.
241 */
242STAILQ_HEAD(, lock_object) all_locks = STAILQ_HEAD_INITIALIZER(all_locks);
243
244static struct mtx all_mtx = {
245 { &lock_class_mtx_sleep, /* mtx_object.lo_class */
246 "All locks list", /* mtx_object.lo_name */
247 NULL, /* mtx_object.lo_file */
248 0, /* mtx_object.lo_line */
249 LO_INITIALIZED, /* mtx_object.lo_flags */
250 { NULL }, /* mtx_object.lo_list */
251 NULL }, /* mtx_object.lo_witness */
252 MTX_UNOWNED, 0, /* mtx_lock, mtx_recurse */
253 0, /* mtx_savecrit */
254 TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked),
255 { NULL, NULL } /* mtx_contested */
256};
257
258/*
259 * This global is set to 0 once it becomes safe to use the witness code.
260 */
261static int witness_cold = 1;
262
263/*
264 * Global variables for book keeping.
265 */
266static int lock_cur_cnt;
267static int lock_max_cnt;
268
269/*
270 * The WITNESS-enabled diagnostic code.
271 */
272static void
273witness_initialize(void *dummy __unused)
274{
275 struct lock_object *lock;
276 struct witness_order_list_entry *order;
277 struct witness *w, *w1;
278 int i;
279
280 /*
281 * We have to release Giant before initializing its witness
282 * structure so that WITNESS doesn't get confused.
283 */
284 mtx_unlock(&Giant);
285 mtx_assert(&Giant, MA_NOTOWNED);
286
287 STAILQ_INSERT_HEAD(&all_locks, &all_mtx.mtx_object, lo_list);
288 mtx_init(&w_mtx, "witness lock", MTX_SPIN | MTX_QUIET | MTX_NOWITNESS);
289 for (i = 0; i < WITNESS_COUNT; i++)
290 witness_free(&w_data[i]);
291 for (i = 0; i < WITNESS_CHILDCOUNT; i++)
292 witness_child_free(&w_childdata[i]);
293 for (i = 0; i < LOCK_CHILDCOUNT; i++)
294 witness_lock_list_free(&w_locklistdata[i]);
295
296 /* First add in all the specified order lists. */
297 for (order = order_lists; order->w_name != NULL; order++) {
298 w = enroll(order->w_name, order->w_class);
299 w->w_file = "order list";
300 for (order++; order->w_name != NULL; order++) {
301 w1 = enroll(order->w_name, order->w_class);
302 w1->w_file = "order list";
303 itismychild(w, w1);
304 w = w1;
305 }
306 }
307
308 /* Iterate through all locks and add them to witness. */
309 mtx_lock(&all_mtx);
310 STAILQ_FOREACH(lock, &all_locks, lo_list) {
311 if (lock->lo_flags & LO_WITNESS)
312 lock->lo_witness = enroll(lock->lo_name,
313 lock->lo_class);
314 else
315 lock->lo_witness = NULL;
316 }
317 mtx_unlock(&all_mtx);
318
319 /* Mark the witness code as being ready for use. */
320 atomic_store_rel_int(&witness_cold, 0);
321
322 mtx_lock(&Giant);
323}
324SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize, NULL)
325
326void
327witness_init(struct lock_object *lock)
328{
329 struct lock_class *class;
330
331 class = lock->lo_class;
332 if (lock->lo_flags & LO_INITIALIZED)
333 panic("%s: lock (%s) %s is already initialized!\n", __func__,
334 class->lc_name, lock->lo_name);
335
336 if ((lock->lo_flags & LO_RECURSABLE) != 0 &&
337 (class->lc_flags & LC_RECURSABLE) == 0)
338 panic("%s: lock (%s) %s can not be recursable!\n", __func__,
339 class->lc_name, lock->lo_name);
340
341 if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
342 (class->lc_flags & LC_SLEEPABLE) == 0)
343 panic("%s: lock (%s) %s can not be sleepable!\n", __func__,
344 class->lc_name, lock->lo_name);
345
346 mtx_lock(&all_mtx);
347 STAILQ_INSERT_TAIL(&all_locks, lock, lo_list);
348 lock->lo_flags |= LO_INITIALIZED;
349 lock_cur_cnt++;
350 if (lock_cur_cnt > lock_max_cnt)
351 lock_max_cnt = lock_cur_cnt;
352 mtx_unlock(&all_mtx);
353 if (!witness_cold && !witness_dead &&
354 (lock->lo_flags & LO_WITNESS) != 0)
355 lock->lo_witness = enroll(lock->lo_name, class);
356 else
357 lock->lo_witness = NULL;
358}
359
360void
361witness_destroy(struct lock_object *lock)
362{
363
364 if (witness_cold)
365 panic("lock (%s) %s destroyed while witness_cold",
366 lock->lo_class->lc_name, lock->lo_name);
367
368 if ((lock->lo_flags & LO_INITIALIZED) == 0)
369 panic("%s: lock (%s) %s is not initialized!\n", __func__,
370 lock->lo_class->lc_name, lock->lo_name);
371
372 if (lock->lo_flags & LO_LOCKED)
373 panic("lock (%s) %s destroyed while held",
374 lock->lo_class->lc_name, lock->lo_name);
375
376 mtx_lock(&all_mtx);
377 lock_cur_cnt--;
378 STAILQ_REMOVE(&all_locks, lock, lock_object, lo_list);
379 lock->lo_flags &= LO_INITIALIZED;
380 mtx_unlock(&all_mtx);
381}
382
383static void
384witness_display_list(void(*prnt)(const char *fmt, ...),
385 struct witness_list *list)
386{
387 struct witness *w, *w1;
388 int found;
389
390 STAILQ_FOREACH(w, list, w_typelist) {
391 if (w->w_file == NULL)
392 continue;
393 found = 0;
394 STAILQ_FOREACH(w1, list, w_typelist) {
395 if (isitmychild(w1, w)) {
396 found++;
397 break;
398 }
399 }
400 if (found)
401 continue;
402 /*
403 * This lock has no anscestors, display its descendants.
404 */
405 witness_displaydescendants(prnt, w);
406 }
407}
408
409static void
410witness_display(void(*prnt)(const char *fmt, ...))
411{
412 struct witness *w;
413
414 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
415 witness_levelall();
416
417 /*
418 * First, handle sleep mutexes which have been acquired at least
419 * once.
420 */
421 prnt("Sleep locks:\n");
422 witness_display_list(prnt, &w_sleep);
423
424 /*
425 * Now do spin mutexes which have been acquired at least once.
426 */
427 prnt("\nSpin locks:\n");
428 witness_display_list(prnt, &w_spin);
429
430 /*
431 * Finally, any mutexes which have not been acquired yet.
432 */
433 prnt("\nLocks which were never acquired:\n");
434 STAILQ_FOREACH(w, &w_all, w_list) {
435 if (w->w_file != NULL)
436 continue;
437 prnt("%s\n", w->w_name);
438 }
439}
440
441void
442witness_lock(struct lock_object *lock, int flags, const char *file, int line)
443{
444 struct lock_list_entry **lock_list, *lle;
445 struct lock_object *lock1, *lock2;
446 struct lock_class *class;
447 struct witness *w, *w1;
448 struct proc *p;
449 int i, j;
450#ifdef DDB
451 int go_into_ddb = 0;
452#endif /* DDB */
453
454 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
455 panicstr)
456 return;
457 w = lock->lo_witness;
458 class = lock->lo_class;
459 p = curproc;
460
461 if ((lock->lo_flags & LO_LOCKED) == 0)
462 panic("%s: lock (%s) %s is not locked @ %s:%d", __func__,
463 class->lc_name, lock->lo_name, file, line);
464
465 if ((lock->lo_flags & LO_RECURSED) != 0) {
466 if ((lock->lo_flags & LO_RECURSABLE) == 0)
467 panic(
468 "%s: recursed on non-recursive lock (%s) %s @ %s:%d",
469 __func__, class->lc_name, lock->lo_name, file,
470 line);
471 return;
472 }
473
474 lock_list = PCPU_PTR(spinlocks);
475 if (class->lc_flags & LC_SLEEPLOCK) {
476 if (*lock_list != NULL)
477 panic("blockable sleep lock (%s) %s @ %s:%d",
478 class->lc_name, lock->lo_name, file, line);
479 lock_list = &p->p_sleeplocks;
480 }
481
482 if (flags & LOP_TRYLOCK)
483 goto out;
484
485 /*
486 * Is this the first lock acquired? If so, then no order checking
487 * is needed.
488 */
489 if (*lock_list == NULL)
490 goto out;
491
492 /*
493 * Check for duplicate locks of the same type. Note that we only
494 * have to check for this on the last lock we just acquired. Any
495 * other cases will be caught as lock order violations.
496 */
497 lock1 = (*lock_list)->ll_children[(*lock_list)->ll_count - 1];
498 w1 = lock1->lo_witness;
499 if (w1 == w) {
500 if (w->w_same_squawked || dup_ok(w))
501 goto out;
502 w->w_same_squawked = 1;
503 printf("acquring duplicate lock of same type: \"%s\"\n",
504 lock->lo_name);
505 printf(" 1st @ %s:%d\n", w->w_file, w->w_line);
506 printf(" 2nd @ %s:%d\n", file, line);
507#ifdef DDB
508 go_into_ddb = 1;
509#endif /* DDB */
510 goto out;
511 }
512 MPASS(!mtx_owned(&w_mtx));
513 mtx_lock_spin(&w_mtx);
514 /*
515 * If we have a known higher number just say ok
516 */
517 if (witness_watch > 1 && w->w_level > w1->w_level) {
518 mtx_unlock_spin(&w_mtx);
519 goto out;
520 }
521 if (isitmydescendant(w1, w)) {
522 mtx_unlock_spin(&w_mtx);
523 goto out;
524 }
525 for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) {
526 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
527
528 MPASS(j < WITNESS_COUNT);
529 lock1 = lle->ll_children[i];
530 w1 = lock1->lo_witness;
531
532 /*
533 * If this lock doesn't undergo witness checking,
534 * then skip it.
535 */
536 if (w1 == NULL) {
537 KASSERT((lock1->lo_flags & LO_WITNESS) == 0,
538 ("lock missing witness structure"));
539 continue;
540 }
541 if (!isitmydescendant(w, w1))
542 continue;
543 /*
544 * We have a lock order violation, check to see if it
545 * is allowed or has already been yelled about.
546 */
547 mtx_unlock_spin(&w_mtx);
548 if (blessed(w, w1))
549 goto out;
550 if (lock1 == &Giant.mtx_object) {
551 if (w1->w_Giant_squawked)
552 goto out;
553 else
554 w1->w_Giant_squawked = 1;
555 } else {
556 if (w1->w_other_squawked)
557 goto out;
558 else
559 w1->w_other_squawked = 1;
560 }
561 /*
562 * Ok, yell about it.
563 */
564 printf("lock order reversal\n");
565 /*
566 * Try to locate an earlier lock with
567 * witness w in our list.
568 */
569 do {
570 lock2 = lle->ll_children[i];
571 MPASS(lock2 != NULL);
572 if (lock2->lo_witness == w)
573 break;
574 i--;
575 if (i == 0 && lle->ll_next != NULL) {
576 lle = lle->ll_next;
577 i = lle->ll_count - 1;
578 MPASS(i != 0);
579 }
580 } while (i >= 0);
581 if (i < 0)
582 /*
583 * We are very likely bogus in this case.
584 */
585 printf(" 1st %s last acquired @ %s:%d\n",
586 w->w_name, w->w_file, w->w_line);
587 else
588 printf(" 1st %p %s @ %s:%d\n", lock2,
589 lock2->lo_name, lock2->lo_file,
590 lock2->lo_line);
591 printf(" 2nd %p %s @ %s:%d\n",
592 lock1, lock1->lo_name, lock1->lo_file,
593 lock1->lo_line);
594 printf(" 3rd %p %s @ %s:%d\n",
595 lock, lock->lo_name, file, line);
596#ifdef DDB
597 go_into_ddb = 1;
598#endif /* DDB */
599 goto out;
600 }
601 }
602 lock1 = (*lock_list)->ll_children[(*lock_list)->ll_count - 1];
603 if (!itismychild(lock1->lo_witness, w))
604 mtx_unlock_spin(&w_mtx);
605
606out:
607#ifdef DDB
608 if (witness_ddb && go_into_ddb)
609 Debugger("witness_enter");
610#endif /* DDB */
611 w->w_file = file;
612 w->w_line = line;
613 lock->lo_line = line;
614 lock->lo_file = file;
615
616 lle = *lock_list;
617 if (lle == NULL || lle->ll_count == LOCK_CHILDCOUNT) {
618 *lock_list = witness_lock_list_get();
619 if (*lock_list == NULL)
620 return;
621 (*lock_list)->ll_next = lle;
622 lle = *lock_list;
623 }
624 lle->ll_children[lle->ll_count++] = lock;
625}
626
627void
628witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
629{
630 struct lock_list_entry **lock_list, *lle;
631 struct lock_class *class;
632 struct proc *p;
633 int i, j;
634
635 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
636 panicstr)
637 return;
638 p = curproc;
639 class = lock->lo_class;
640
641 if (lock->lo_flags & LO_RECURSED) {
642 if ((lock->lo_flags & LO_LOCKED) == 0)
643 panic("%s: recursed lock (%s) %s is not locked @ %s:%d",
644 __func__, class->lc_name, lock->lo_name, file,
645 line);
646 return;
647 }
648
649 /*
650 * We don't need to protect this PCPU_GET() here against preemption
651 * because if we hold any spinlocks then we are already protected,
652 * and if we don't we will get NULL if we hold no spinlocks even if
653 * we switch CPU's while reading it.
654 */
655 if (class->lc_flags & LC_SLEEPLOCK) {
656 if ((flags & LOP_NOSWITCH) == 0 && PCPU_GET(spinlocks) != NULL)
657 panic("switchable sleep unlock (%s) %s @ %s:%d",
658 class->lc_name, lock->lo_name, file, line);
659 lock_list = &p->p_sleeplocks;
660 } else
661 lock_list = PCPU_PTR(spinlocks);
662
663 for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
664 for (i = 0; i < (*lock_list)->ll_count; i++)
665 if ((*lock_list)->ll_children[i] == lock) {
666 (*lock_list)->ll_count--;
667 for (j = i; j < (*lock_list)->ll_count; j++)
668 (*lock_list)->ll_children[j] =
669 (*lock_list)->ll_children[j + 1];
670 if ((*lock_list)->ll_count == 0) {
671 lle = *lock_list;
672 *lock_list = lle->ll_next;
673 witness_lock_list_free(lle);
674 }
675 return;
676 }
677}
678
679/*
680 * Warn if any held locks are not sleepable. Note that Giant and the lock
681 * passed in are both special cases since they are both released during the
682 * sleep process and aren't actually held while the process is asleep.
683 */
684int
685witness_sleep(int check_only, struct lock_object *lock, const char *file,
686 int line)
687{
688 struct lock_list_entry **lock_list, *lle;
689 struct lock_object *lock1;
690 struct proc *p;
691 critical_t savecrit;
692 int i, n;
693
694 if (witness_dead || panicstr)
695 return (0);
696 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
697 n = 0;
698 /*
699 * Preemption bad because we need PCPU_PTR(spinlocks) to not change.
700 */
701 savecrit = critical_enter();
702 p = curproc;
703 lock_list = &p->p_sleeplocks;
704again:
705 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
706 for (i = lle->ll_count - 1; i >= 0; i--) {
707 lock1 = lle->ll_children[i];
708 if (lock1 == lock || lock1 == &Giant.mtx_object ||
709 (lock1->lo_flags & LO_SLEEPABLE))
710 continue;
711 n++;
712 printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
713 file, line, check_only ? "could sleep" : "sleeping",
714 lock1->lo_name, lock1->lo_file, lock1->lo_line);
715 }
716 if (lock_list == &p->p_sleeplocks) {
717 lock_list = PCPU_PTR(spinlocks);
718 goto again;
719 }
720#ifdef DDB
721 if (witness_ddb && n)
722 Debugger("witness_sleep");
723#endif /* DDB */
724 critical_exit(savecrit);
725 return (n);
726}
727
728static struct witness *
729enroll(const char *description, struct lock_class *lock_class)
730{
731 struct witness *w;
732
733 if (!witness_watch)
734 return (NULL);
735
736 if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin)
737 return (NULL);
738 mtx_lock_spin(&w_mtx);
739 STAILQ_FOREACH(w, &w_all, w_list) {
740 if (strcmp(description, w->w_name) == 0) {
741 mtx_unlock_spin(&w_mtx);
742 if (lock_class != w->w_class)
743 panic(
744 "lock (%s) %s does not match earlier (%s) lock",
745 description, lock_class->lc_name,
746 w->w_class->lc_name);
747 return (w);
748 }
749 }
750 /*
751 * This isn't quite right, as witness_cold is still 0 while we
752 * enroll all the locks initialized before witness_initialize().
753 */
754 if ((lock_class->lc_flags & LC_SPINLOCK) && !witness_cold)
755 panic("spin lock %s not in order list", description);
756 if ((w = witness_get()) == NULL)
757 return (NULL);
758 w->w_name = description;
759 w->w_class = lock_class;
760 STAILQ_INSERT_HEAD(&w_all, w, w_list);
761 if (lock_class->lc_flags & LC_SPINLOCK)
762 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
763 else if (lock_class->lc_flags & LC_SLEEPLOCK)
764 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
765 else
766 panic("lock class %s is not sleep or spin",
767 lock_class->lc_name);
768 mtx_unlock_spin(&w_mtx);
769
770 return (w);
771}
772
773static int
774itismychild(struct witness *parent, struct witness *child)
775{
776 static int recursed;
777 struct witness_child_list_entry **wcl;
778 struct witness_list *list;
779
780 MPASS(child != NULL && parent != NULL);
781 if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
782 (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
783 panic(
784 "%s: parent (%s) and child (%s) are not the same lock type",
785 __func__, parent->w_class->lc_name,
786 child->w_class->lc_name);
787
788 /*
789 * Insert "child" after "parent"
790 */
791 wcl = &parent->w_children;
792 while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN)
793 wcl = &(*wcl)->wcl_next;
794
795 if (*wcl == NULL) {
796 *wcl = witness_child_get();
797 if (*wcl == NULL)
798 return (1);
799 }
800
801 (*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
802
803 /*
804 * Now prune whole tree. We look for cases where a lock is now
805 * both a descendant and a direct child of a given lock. In that
806 * case, we want to remove the direct child link from the tree.
807 */
808 if (recursed)
809 return (0);
810 recursed = 1;
811 if (parent->w_class->lc_flags & LC_SLEEPLOCK)
812 list = &w_sleep;
813 else
814 list = &w_spin;
815 STAILQ_FOREACH(child, list, w_typelist) {
816 STAILQ_FOREACH(parent, list, w_typelist) {
817 if (!isitmychild(parent, child))
818 continue;
819 removechild(parent, child);
820 if (isitmydescendant(parent, child))
821 continue;
822 itismychild(parent, child);
823 }
824 }
825 recursed = 0;
826 witness_levelall();
827 return (0);
828}
829
830static void
831removechild(struct witness *parent, struct witness *child)
832{
833 struct witness_child_list_entry **wcl, *wcl1;
834 int i;
835
836 for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next)
837 for (i = 0; i < (*wcl)->wcl_count; i++)
838 if ((*wcl)->wcl_children[i] == child)
839 goto found;
840 return;
841found:
842 (*wcl)->wcl_count--;
843 if ((*wcl)->wcl_count > i)
844 (*wcl)->wcl_children[i] =
845 (*wcl)->wcl_children[(*wcl)->wcl_count];
846 MPASS((*wcl)->wcl_children[i] != NULL);
847
848 if ((*wcl)->wcl_count != 0)
849 return;
850
851 wcl1 = *wcl;
852 *wcl = wcl1->wcl_next;
853 witness_child_free(wcl1);
854}
855
856static int
857isitmychild(struct witness *parent, struct witness *child)
858{
859 struct witness_child_list_entry *wcl;
860 int i;
861
862 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
863 for (i = 0; i < wcl->wcl_count; i++) {
864 if (wcl->wcl_children[i] == child)
865 return (1);
866 }
867 }
868 return (0);
869}
870
871static int
872isitmydescendant(struct witness *parent, struct witness *child)
873{
874 struct witness_child_list_entry *wcl;
875 int i, j;
876
877 if (isitmychild(parent, child))
878 return (1);
879 j = 0;
880 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
881 MPASS(j < 1000);
882 for (i = 0; i < wcl->wcl_count; i++) {
883 if (isitmydescendant(wcl->wcl_children[i], child))
884 return (1);
885 }
886 j++;
887 }
888 return (0);
889}
890
891void
892witness_levelall (void)
893{
894 struct witness_list *list;
895 struct witness *w, *w1;
896
897 /*
898 * First clear all levels.
899 */
900 STAILQ_FOREACH(w, &w_all, w_list) {
901 w->w_level = 0;
902 }
903
904 /*
905 * Look for locks with no parent and level all their descendants.
906 */
907 STAILQ_FOREACH(w, &w_all, w_list) {
908 /*
909 * This is just an optimization, technically we could get
910 * away just walking the all list each time.
911 */
912 if (w->w_class->lc_flags & LC_SLEEPLOCK)
913 list = &w_sleep;
914 else
915 list = &w_spin;
916 STAILQ_FOREACH(w1, list, w_typelist) {
917 if (isitmychild(w1, w))
918 goto skip;
919 }
920 witness_leveldescendents(w, 0);
921 skip:
922 }
923}
924
925static void
926witness_leveldescendents(struct witness *parent, int level)
927{
928 struct witness_child_list_entry *wcl;
929 int i;
930
931 if (parent->w_level < level)
932 parent->w_level = level;
933 level++;
934 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
935 for (i = 0; i < wcl->wcl_count; i++)
936 witness_leveldescendents(wcl->wcl_children[i], level);
937}
938
939static void
940witness_displaydescendants(void(*prnt)(const char *fmt, ...),
941 struct witness *parent)
942{
943 struct witness_child_list_entry *wcl;
944 int i, level;
945
946 level = parent->w_level;
947
948 prnt("%-2d", level);
949 for (i = 0; i < level; i++)
950 prnt(" ");
951 prnt("%s", parent->w_name);
952 if (parent->w_file != NULL)
953 prnt(" -- last acquired @ %s:%d\n", parent->w_file,
954 parent->w_line);
955
956 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
957 for (i = 0; i < wcl->wcl_count; i++)
958 witness_displaydescendants(prnt,
959 wcl->wcl_children[i]);
960}
961
962static int
963dup_ok(struct witness *w)
964{
965 const char **dup;
966
967 for (dup = dup_list; *dup != NULL; dup++)
968 if (strcmp(w->w_name, *dup) == 0)
969 return (1);
970 return (0);
971}
972
973static int
974blessed(struct witness *w1, struct witness *w2)
975{
976 int i;
977 struct witness_blessed *b;
978
979 for (i = 0; i < blessed_count; i++) {
980 b = &blessed_list[i];
981 if (strcmp(w1->w_name, b->b_lock1) == 0) {
982 if (strcmp(w2->w_name, b->b_lock2) == 0)
983 return (1);
984 continue;
985 }
986 if (strcmp(w1->w_name, b->b_lock2) == 0)
987 if (strcmp(w2->w_name, b->b_lock1) == 0)
988 return (1);
989 }
990 return (0);
991}
992
993static struct witness *
994witness_get(void)
995{
996 struct witness *w;
997
998 if (STAILQ_EMPTY(&w_free)) {
999 witness_dead = 1;
1000 mtx_unlock_spin(&w_mtx);
1001 printf("%s: witness exhausted\n", __func__);
1002 return (NULL);
1003 }
1004 w = STAILQ_FIRST(&w_free);
1005 STAILQ_REMOVE_HEAD(&w_free, w_list);
1006 bzero(w, sizeof(*w));
1007 return (w);
1008}
1009
1010static void
1011witness_free(struct witness *w)
1012{
1013
1014 STAILQ_INSERT_HEAD(&w_free, w, w_list);
1015}
1016
1017static struct witness_child_list_entry *
1018witness_child_get(void)
1019{
1020 struct witness_child_list_entry *wcl;
1021
1022 wcl = w_child_free;
1023 if (wcl == NULL) {
1024 witness_dead = 1;
1025 mtx_unlock_spin(&w_mtx);
1026 printf("%s: witness exhausted\n", __func__);
1027 return (NULL);
1028 }
1029 w_child_free = wcl->wcl_next;
1030 bzero(wcl, sizeof(*wcl));
1031 return (wcl);
1032}
1033
1034static void
1035witness_child_free(struct witness_child_list_entry *wcl)
1036{
1037
1038 wcl->wcl_next = w_child_free;
1039 w_child_free = wcl;
1040}
1041
1042static struct lock_list_entry *
1043witness_lock_list_get(void)
1044{
1045 struct lock_list_entry *lle;
1046
1047 mtx_lock_spin(&w_mtx);
1048 lle = w_lock_list_free;
1049 if (lle == NULL) {
1050 witness_dead = 1;
1051 mtx_unlock_spin(&w_mtx);
1052 printf("%s: witness exhausted\n", __func__);
1053 return (NULL);
1054 }
1055 w_lock_list_free = lle->ll_next;
1056 mtx_unlock_spin(&w_mtx);
1057 bzero(lle, sizeof(*lle));
1058 return (lle);
1059}
1060
1061static void
1062witness_lock_list_free(struct lock_list_entry *lle)
1063{
1064
1065 mtx_lock_spin(&w_mtx);
1066 lle->ll_next = w_lock_list_free;
1067 w_lock_list_free = lle;
1068 mtx_unlock_spin(&w_mtx);
1069}
1070
1071/*
1072 * Calling this on p != curproc is bad unless we are in ddb.
1073 */
1074int
1075witness_list(struct proc *p)
1076{
1077 struct lock_list_entry **lock_list, *lle;
1078 struct lock_object *lock;
1079 critical_t savecrit;
1080 int i, nheld;
1081
1082 KASSERT(p == curproc || db_active,
1083 ("%s: p != curproc and we aren't in the debugger", __func__));
1084 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1085 nheld = 0;
1086 /*
1087 * Preemption bad because we need PCPU_PTR(spinlocks) to not change.
1088 */
1089 savecrit = critical_enter();
1090 lock_list = &p->p_sleeplocks;
1091again:
1092 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
1093 for (i = lle->ll_count - 1; i >= 0; i--) {
1094 lock = lle->ll_children[i];
1095 printf("\t(%s) %s (%p) locked at %s:%d\n",
1096 lock->lo_class->lc_name, lock->lo_name, lock,
1097 lock->lo_file, lock->lo_line);
1098 nheld++;
1099 }
1100 /*
1101 * We only handle spinlocks if p == curproc. This is somewhat broken
1102 * if p is currently executing on some other CPU and holds spin locks
1103 * as we won't display those locks.
1104 */
1105 if (lock_list == &p->p_sleeplocks && p == curproc) {
1106 lock_list = PCPU_PTR(spinlocks);
1107 goto again;
1108 }
1109 critical_exit(savecrit);
1110
1111 return (nheld);
1112}
1113
1114void
1115witness_save(struct lock_object *lock, const char **filep, int *linep)
1116{
1117
1118 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
1119 if (lock->lo_witness == NULL)
1120 return;
1121
1122 *filep = lock->lo_file;
1123 *linep = lock->lo_line;
1124}
1125
1126void
1127witness_restore(struct lock_object *lock, const char *file, int line)
1128{
1129
1130 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
1131 if (lock->lo_witness == NULL)
1132 return;
1133
1134 lock->lo_witness->w_file = file;
1135 lock->lo_witness->w_line = line;
1136 lock->lo_file = file;
1137 lock->lo_line = line;
1138}
1139
1140#ifdef DDB
1141
1142DB_SHOW_COMMAND(mutexes, db_witness_list)
1143{
1144
1145 witness_list(curproc);
1146}
1147
1148DB_SHOW_COMMAND(witness, db_witness_display)
1149{
1150
1151 witness_display(db_printf);
1152}
1153#endif
2 * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
--- 13 unchanged lines hidden (view full) ---
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 *
28 * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
29 * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
30 * $FreeBSD: head/sys/kern/subr_witness.c 74912 2001-03-28 09:03:24Z jhb $
31 */
32
33/*
34 * Implementation of the `witness' lock verifier. Originally implemented for
35 * mutexes in BSD/OS. Extended to handle generic lock objects and lock
36 * classes in FreeBSD.
37 */
38
39/*
40 * Main Entry: witness
41 * Pronunciation: 'wit-n&s
42 * Function: noun
43 * Etymology: Middle English witnesse, from Old English witnes knowledge,
44 * testimony, witness, from 2wit
--- 12 unchanged lines hidden (view full) ---
57 */
58
59#include "opt_ddb.h"
60#include "opt_witness.h"
61
62#include <sys/param.h>
63#include <sys/bus.h>
64#include <sys/kernel.h>
65#include <sys/ktr.h>
66#include <sys/lock.h>
67#include <sys/malloc.h>
68#include <sys/mutex.h>
69#include <sys/proc.h>
70#include <sys/sysctl.h>
71#include <sys/systm.h>
72
73#include <ddb/ddb.h>
74
75#define WITNESS_COUNT 200
76#define WITNESS_CHILDCOUNT (WITNESS_COUNT * 4)
77/*
78 * XXX: This is somewhat bogus, as we assume here that at most 1024 processes
79 * will hold LOCK_NCHILDREN * 2 locks. We handle failure ok, and we should
80 * probably be safe for the most part, but it's still a SWAG.
81 */
82#define LOCK_CHILDCOUNT (MAXCPU + 1024) * 2
83
84#define WITNESS_NCHILDREN 6
85
86struct witness_child_list_entry;
87
88struct witness {
89 const char *w_name;
90 struct lock_class *w_class;
91 STAILQ_ENTRY(witness) w_list; /* List of all witnesses. */
92 STAILQ_ENTRY(witness) w_typelist; /* Witnesses of a type. */
93 struct witness_child_list_entry *w_children; /* Great evilness... */
94 const char *w_file;
95 int w_line;
96 u_int w_level;
97 u_int w_refcount;
98 u_char w_Giant_squawked:1;
99 u_char w_other_squawked:1;
100 u_char w_same_squawked:1;
101};
102
103struct witness_child_list_entry {
104 struct witness_child_list_entry *wcl_next;
105 struct witness *wcl_children[WITNESS_NCHILDREN];
106 u_int wcl_count;
107};
108
109STAILQ_HEAD(witness_list, witness);
110
111struct witness_blessed {
112 const char *b_lock1;
113 const char *b_lock2;
114};
115
116struct witness_order_list_entry {
117 const char *w_name;
118 struct lock_class *w_class;
119};
120
121static struct witness *enroll(const char *description,
122 struct lock_class *lock_class);
123static int itismychild(struct witness *parent, struct witness *child);
124static void removechild(struct witness *parent, struct witness *child);
125static int isitmychild(struct witness *parent, struct witness *child);
126static int isitmydescendant(struct witness *parent, struct witness *child);
127static int dup_ok(struct witness *);
128static int blessed(struct witness *, struct witness *);
129static void witness_display_list(void(*prnt)(const char *fmt, ...),
130 struct witness_list *list);
131static void witness_displaydescendants(void(*)(const char *fmt, ...),
132 struct witness *);
133static void witness_leveldescendents(struct witness *parent, int level);
134static void witness_levelall(void);
135static struct witness *witness_get(void);
136static void witness_free(struct witness *m);
137static struct witness_child_list_entry *witness_child_get(void);
138static void witness_child_free(struct witness_child_list_entry *wcl);
139static struct lock_list_entry *witness_lock_list_get(void);
140static void witness_lock_list_free(struct lock_list_entry *lle);
141static void witness_display(void(*)(const char *fmt, ...));
142
143MALLOC_DEFINE(M_WITNESS, "witness", "witness structure");
144
145static int witness_watch;
146TUNABLE_INT_DECL("debug.witness_watch", 1, witness_watch);
147SYSCTL_INT(_debug, OID_AUTO, witness_watch, CTLFLAG_RD, &witness_watch, 0, "");
148
149#ifdef DDB
150/*
151 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to
152 * drop into kdebug() when:
153 * - a lock heirarchy violation occurs
154 * - locks are held when going to sleep.
155 */
156int witness_ddb;
157#ifdef WITNESS_DDB
158TUNABLE_INT_DECL("debug.witness_ddb", 1, witness_ddb);
--- 7 unchanged lines hidden (view full) ---
166#ifdef WITNESS_SKIPSPIN
167TUNABLE_INT_DECL("debug.witness_skipspin", 1, witness_skipspin);
168#else
169TUNABLE_INT_DECL("debug.witness_skipspin", 0, witness_skipspin);
170#endif
171SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0,
172 "");
173
174static struct mtx w_mtx;
175static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free);
176static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all);
177static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin);
178static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep);
179static struct witness_child_list_entry *w_child_free = NULL;
180static struct lock_list_entry *w_lock_list_free = NULL;
181static int witness_dead; /* fatal error, probably no memory */
182
183static struct witness w_data[WITNESS_COUNT];
184static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT];
185static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
186
187static struct witness_order_list_entry order_lists[] = {
188 { "Giant", &lock_class_mtx_sleep },
189 { "proctree", &lock_class_sx },
190 { "allproc", &lock_class_sx },
191 { "process lock", &lock_class_mtx_sleep },
192 { "uidinfo hash", &lock_class_mtx_sleep },
193 { "uidinfo struct", &lock_class_mtx_sleep },
194 { NULL, NULL },
195#if defined(__i386__) && defined (SMP)
196 { "com", &lock_class_mtx_spin },
197#endif
198 { "sio", &lock_class_mtx_spin },
199#ifdef __i386__
200 { "cy", &lock_class_mtx_spin },
201#endif
202 { "ng_node", &lock_class_mtx_spin },
203 { "ng_worklist", &lock_class_mtx_spin },
204 { "ithread table lock", &lock_class_mtx_spin },
205 { "ithread list lock", &lock_class_mtx_spin },
206 { "sched lock", &lock_class_mtx_spin },
207#ifdef __i386__
208 { "clk", &lock_class_mtx_spin },
209#endif
210 { "callout", &lock_class_mtx_spin },
211 /*
212 * leaf locks
213 */
214#ifdef SMP
215#ifdef __i386__
216 { "ap boot", &lock_class_mtx_spin },
217 { "imen", &lock_class_mtx_spin },
218#endif
219 { "smp rendezvous", &lock_class_mtx_spin },
220#endif
221 { NULL, NULL },
222 { NULL, NULL }
223};
224
225static const char *dup_list[] = {
226 "process lock",
227 NULL
228};
229
230/*
231 * Pairs of locks which have been blessed
232 * Don't complain about order problems with blessed locks
233 */
234static struct witness_blessed blessed_list[] = {
235};
236static int blessed_count =
237 sizeof(blessed_list) / sizeof(struct witness_blessed);
238
239/*
240 * List of all locks in the system.
241 */
242STAILQ_HEAD(, lock_object) all_locks = STAILQ_HEAD_INITIALIZER(all_locks);
243
244static struct mtx all_mtx = {
245 { &lock_class_mtx_sleep, /* mtx_object.lo_class */
246 "All locks list", /* mtx_object.lo_name */
247 NULL, /* mtx_object.lo_file */
248 0, /* mtx_object.lo_line */
249 LO_INITIALIZED, /* mtx_object.lo_flags */
250 { NULL }, /* mtx_object.lo_list */
251 NULL }, /* mtx_object.lo_witness */
252 MTX_UNOWNED, 0, /* mtx_lock, mtx_recurse */
253 0, /* mtx_savecrit */
254 TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked),
255 { NULL, NULL } /* mtx_contested */
256};
257
258/*
259 * This global is set to 0 once it becomes safe to use the witness code.
260 */
261static int witness_cold = 1;
262
263/*
264 * Global variables for book keeping.
265 */
266static int lock_cur_cnt;
267static int lock_max_cnt;
268
269/*
270 * The WITNESS-enabled diagnostic code.
271 */
272static void
273witness_initialize(void *dummy __unused)
274{
275 struct lock_object *lock;
276 struct witness_order_list_entry *order;
277 struct witness *w, *w1;
278 int i;
279
280 /*
281 * We have to release Giant before initializing its witness
282 * structure so that WITNESS doesn't get confused.
283 */
284 mtx_unlock(&Giant);
285 mtx_assert(&Giant, MA_NOTOWNED);
286
287 STAILQ_INSERT_HEAD(&all_locks, &all_mtx.mtx_object, lo_list);
288 mtx_init(&w_mtx, "witness lock", MTX_SPIN | MTX_QUIET | MTX_NOWITNESS);
289 for (i = 0; i < WITNESS_COUNT; i++)
290 witness_free(&w_data[i]);
291 for (i = 0; i < WITNESS_CHILDCOUNT; i++)
292 witness_child_free(&w_childdata[i]);
293 for (i = 0; i < LOCK_CHILDCOUNT; i++)
294 witness_lock_list_free(&w_locklistdata[i]);
295
296 /* First add in all the specified order lists. */
297 for (order = order_lists; order->w_name != NULL; order++) {
298 w = enroll(order->w_name, order->w_class);
299 w->w_file = "order list";
300 for (order++; order->w_name != NULL; order++) {
301 w1 = enroll(order->w_name, order->w_class);
302 w1->w_file = "order list";
303 itismychild(w, w1);
304 w = w1;
305 }
306 }
307
308 /* Iterate through all locks and add them to witness. */
309 mtx_lock(&all_mtx);
310 STAILQ_FOREACH(lock, &all_locks, lo_list) {
311 if (lock->lo_flags & LO_WITNESS)
312 lock->lo_witness = enroll(lock->lo_name,
313 lock->lo_class);
314 else
315 lock->lo_witness = NULL;
316 }
317 mtx_unlock(&all_mtx);
318
319 /* Mark the witness code as being ready for use. */
320 atomic_store_rel_int(&witness_cold, 0);
321
322 mtx_lock(&Giant);
323}
324SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize, NULL)
325
326void
327witness_init(struct lock_object *lock)
328{
329 struct lock_class *class;
330
331 class = lock->lo_class;
332 if (lock->lo_flags & LO_INITIALIZED)
333 panic("%s: lock (%s) %s is already initialized!\n", __func__,
334 class->lc_name, lock->lo_name);
335
336 if ((lock->lo_flags & LO_RECURSABLE) != 0 &&
337 (class->lc_flags & LC_RECURSABLE) == 0)
338 panic("%s: lock (%s) %s can not be recursable!\n", __func__,
339 class->lc_name, lock->lo_name);
340
341 if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
342 (class->lc_flags & LC_SLEEPABLE) == 0)
343 panic("%s: lock (%s) %s can not be sleepable!\n", __func__,
344 class->lc_name, lock->lo_name);
345
346 mtx_lock(&all_mtx);
347 STAILQ_INSERT_TAIL(&all_locks, lock, lo_list);
348 lock->lo_flags |= LO_INITIALIZED;
349 lock_cur_cnt++;
350 if (lock_cur_cnt > lock_max_cnt)
351 lock_max_cnt = lock_cur_cnt;
352 mtx_unlock(&all_mtx);
353 if (!witness_cold && !witness_dead &&
354 (lock->lo_flags & LO_WITNESS) != 0)
355 lock->lo_witness = enroll(lock->lo_name, class);
356 else
357 lock->lo_witness = NULL;
358}
359
360void
361witness_destroy(struct lock_object *lock)
362{
363
364 if (witness_cold)
365 panic("lock (%s) %s destroyed while witness_cold",
366 lock->lo_class->lc_name, lock->lo_name);
367
368 if ((lock->lo_flags & LO_INITIALIZED) == 0)
369 panic("%s: lock (%s) %s is not initialized!\n", __func__,
370 lock->lo_class->lc_name, lock->lo_name);
371
372 if (lock->lo_flags & LO_LOCKED)
373 panic("lock (%s) %s destroyed while held",
374 lock->lo_class->lc_name, lock->lo_name);
375
376 mtx_lock(&all_mtx);
377 lock_cur_cnt--;
378 STAILQ_REMOVE(&all_locks, lock, lock_object, lo_list);
379 lock->lo_flags &= LO_INITIALIZED;
380 mtx_unlock(&all_mtx);
381}
382
383static void
384witness_display_list(void(*prnt)(const char *fmt, ...),
385 struct witness_list *list)
386{
387 struct witness *w, *w1;
388 int found;
389
390 STAILQ_FOREACH(w, list, w_typelist) {
391 if (w->w_file == NULL)
392 continue;
393 found = 0;
394 STAILQ_FOREACH(w1, list, w_typelist) {
395 if (isitmychild(w1, w)) {
396 found++;
397 break;
398 }
399 }
400 if (found)
401 continue;
402 /*
403 * This lock has no anscestors, display its descendants.
404 */
405 witness_displaydescendants(prnt, w);
406 }
407}
408
409static void
410witness_display(void(*prnt)(const char *fmt, ...))
411{
412 struct witness *w;
413
414 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
415 witness_levelall();
416
417 /*
418 * First, handle sleep mutexes which have been acquired at least
419 * once.
420 */
421 prnt("Sleep locks:\n");
422 witness_display_list(prnt, &w_sleep);
423
424 /*
425 * Now do spin mutexes which have been acquired at least once.
426 */
427 prnt("\nSpin locks:\n");
428 witness_display_list(prnt, &w_spin);
429
430 /*
431 * Finally, any mutexes which have not been acquired yet.
432 */
433 prnt("\nLocks which were never acquired:\n");
434 STAILQ_FOREACH(w, &w_all, w_list) {
435 if (w->w_file != NULL)
436 continue;
437 prnt("%s\n", w->w_name);
438 }
439}
440
441void
442witness_lock(struct lock_object *lock, int flags, const char *file, int line)
443{
444 struct lock_list_entry **lock_list, *lle;
445 struct lock_object *lock1, *lock2;
446 struct lock_class *class;
447 struct witness *w, *w1;
448 struct proc *p;
449 int i, j;
450#ifdef DDB
451 int go_into_ddb = 0;
452#endif /* DDB */
453
454 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
455 panicstr)
456 return;
457 w = lock->lo_witness;
458 class = lock->lo_class;
459 p = curproc;
460
461 if ((lock->lo_flags & LO_LOCKED) == 0)
462 panic("%s: lock (%s) %s is not locked @ %s:%d", __func__,
463 class->lc_name, lock->lo_name, file, line);
464
465 if ((lock->lo_flags & LO_RECURSED) != 0) {
466 if ((lock->lo_flags & LO_RECURSABLE) == 0)
467 panic(
468 "%s: recursed on non-recursive lock (%s) %s @ %s:%d",
469 __func__, class->lc_name, lock->lo_name, file,
470 line);
471 return;
472 }
473
474 lock_list = PCPU_PTR(spinlocks);
475 if (class->lc_flags & LC_SLEEPLOCK) {
476 if (*lock_list != NULL)
477 panic("blockable sleep lock (%s) %s @ %s:%d",
478 class->lc_name, lock->lo_name, file, line);
479 lock_list = &p->p_sleeplocks;
480 }
481
482 if (flags & LOP_TRYLOCK)
483 goto out;
484
485 /*
486 * Is this the first lock acquired? If so, then no order checking
487 * is needed.
488 */
489 if (*lock_list == NULL)
490 goto out;
491
492 /*
493 * Check for duplicate locks of the same type. Note that we only
494 * have to check for this on the last lock we just acquired. Any
495 * other cases will be caught as lock order violations.
496 */
497 lock1 = (*lock_list)->ll_children[(*lock_list)->ll_count - 1];
498 w1 = lock1->lo_witness;
499 if (w1 == w) {
500 if (w->w_same_squawked || dup_ok(w))
501 goto out;
502 w->w_same_squawked = 1;
503 printf("acquring duplicate lock of same type: \"%s\"\n",
504 lock->lo_name);
505 printf(" 1st @ %s:%d\n", w->w_file, w->w_line);
506 printf(" 2nd @ %s:%d\n", file, line);
507#ifdef DDB
508 go_into_ddb = 1;
509#endif /* DDB */
510 goto out;
511 }
512 MPASS(!mtx_owned(&w_mtx));
513 mtx_lock_spin(&w_mtx);
514 /*
515 * If we have a known higher number just say ok
516 */
517 if (witness_watch > 1 && w->w_level > w1->w_level) {
518 mtx_unlock_spin(&w_mtx);
519 goto out;
520 }
521 if (isitmydescendant(w1, w)) {
522 mtx_unlock_spin(&w_mtx);
523 goto out;
524 }
525 for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) {
526 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
527
528 MPASS(j < WITNESS_COUNT);
529 lock1 = lle->ll_children[i];
530 w1 = lock1->lo_witness;
531
532 /*
533 * If this lock doesn't undergo witness checking,
534 * then skip it.
535 */
536 if (w1 == NULL) {
537 KASSERT((lock1->lo_flags & LO_WITNESS) == 0,
538 ("lock missing witness structure"));
539 continue;
540 }
541 if (!isitmydescendant(w, w1))
542 continue;
543 /*
544 * We have a lock order violation, check to see if it
545 * is allowed or has already been yelled about.
546 */
547 mtx_unlock_spin(&w_mtx);
548 if (blessed(w, w1))
549 goto out;
550 if (lock1 == &Giant.mtx_object) {
551 if (w1->w_Giant_squawked)
552 goto out;
553 else
554 w1->w_Giant_squawked = 1;
555 } else {
556 if (w1->w_other_squawked)
557 goto out;
558 else
559 w1->w_other_squawked = 1;
560 }
561 /*
562 * Ok, yell about it.
563 */
564 printf("lock order reversal\n");
565 /*
566 * Try to locate an earlier lock with
567 * witness w in our list.
568 */
569 do {
570 lock2 = lle->ll_children[i];
571 MPASS(lock2 != NULL);
572 if (lock2->lo_witness == w)
573 break;
574 i--;
575 if (i == 0 && lle->ll_next != NULL) {
576 lle = lle->ll_next;
577 i = lle->ll_count - 1;
578 MPASS(i != 0);
579 }
580 } while (i >= 0);
581 if (i < 0)
582 /*
583 * We are very likely bogus in this case.
584 */
585 printf(" 1st %s last acquired @ %s:%d\n",
586 w->w_name, w->w_file, w->w_line);
587 else
588 printf(" 1st %p %s @ %s:%d\n", lock2,
589 lock2->lo_name, lock2->lo_file,
590 lock2->lo_line);
591 printf(" 2nd %p %s @ %s:%d\n",
592 lock1, lock1->lo_name, lock1->lo_file,
593 lock1->lo_line);
594 printf(" 3rd %p %s @ %s:%d\n",
595 lock, lock->lo_name, file, line);
596#ifdef DDB
597 go_into_ddb = 1;
598#endif /* DDB */
599 goto out;
600 }
601 }
602 lock1 = (*lock_list)->ll_children[(*lock_list)->ll_count - 1];
603 if (!itismychild(lock1->lo_witness, w))
604 mtx_unlock_spin(&w_mtx);
605
606out:
607#ifdef DDB
608 if (witness_ddb && go_into_ddb)
609 Debugger("witness_enter");
610#endif /* DDB */
611 w->w_file = file;
612 w->w_line = line;
613 lock->lo_line = line;
614 lock->lo_file = file;
615
616 lle = *lock_list;
617 if (lle == NULL || lle->ll_count == LOCK_CHILDCOUNT) {
618 *lock_list = witness_lock_list_get();
619 if (*lock_list == NULL)
620 return;
621 (*lock_list)->ll_next = lle;
622 lle = *lock_list;
623 }
624 lle->ll_children[lle->ll_count++] = lock;
625}
626
627void
628witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
629{
630 struct lock_list_entry **lock_list, *lle;
631 struct lock_class *class;
632 struct proc *p;
633 int i, j;
634
635 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
636 panicstr)
637 return;
638 p = curproc;
639 class = lock->lo_class;
640
641 if (lock->lo_flags & LO_RECURSED) {
642 if ((lock->lo_flags & LO_LOCKED) == 0)
643 panic("%s: recursed lock (%s) %s is not locked @ %s:%d",
644 __func__, class->lc_name, lock->lo_name, file,
645 line);
646 return;
647 }
648
649 /*
650 * We don't need to protect this PCPU_GET() here against preemption
651 * because if we hold any spinlocks then we are already protected,
652 * and if we don't we will get NULL if we hold no spinlocks even if
653 * we switch CPU's while reading it.
654 */
655 if (class->lc_flags & LC_SLEEPLOCK) {
656 if ((flags & LOP_NOSWITCH) == 0 && PCPU_GET(spinlocks) != NULL)
657 panic("switchable sleep unlock (%s) %s @ %s:%d",
658 class->lc_name, lock->lo_name, file, line);
659 lock_list = &p->p_sleeplocks;
660 } else
661 lock_list = PCPU_PTR(spinlocks);
662
663 for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
664 for (i = 0; i < (*lock_list)->ll_count; i++)
665 if ((*lock_list)->ll_children[i] == lock) {
666 (*lock_list)->ll_count--;
667 for (j = i; j < (*lock_list)->ll_count; j++)
668 (*lock_list)->ll_children[j] =
669 (*lock_list)->ll_children[j + 1];
670 if ((*lock_list)->ll_count == 0) {
671 lle = *lock_list;
672 *lock_list = lle->ll_next;
673 witness_lock_list_free(lle);
674 }
675 return;
676 }
677}
678
679/*
680 * Warn if any held locks are not sleepable. Note that Giant and the lock
681 * passed in are both special cases since they are both released during the
682 * sleep process and aren't actually held while the process is asleep.
683 */
684int
685witness_sleep(int check_only, struct lock_object *lock, const char *file,
686 int line)
687{
688 struct lock_list_entry **lock_list, *lle;
689 struct lock_object *lock1;
690 struct proc *p;
691 critical_t savecrit;
692 int i, n;
693
694 if (witness_dead || panicstr)
695 return (0);
696 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
697 n = 0;
698 /*
699 * Preemption bad because we need PCPU_PTR(spinlocks) to not change.
700 */
701 savecrit = critical_enter();
702 p = curproc;
703 lock_list = &p->p_sleeplocks;
704again:
705 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
706 for (i = lle->ll_count - 1; i >= 0; i--) {
707 lock1 = lle->ll_children[i];
708 if (lock1 == lock || lock1 == &Giant.mtx_object ||
709 (lock1->lo_flags & LO_SLEEPABLE))
710 continue;
711 n++;
712 printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
713 file, line, check_only ? "could sleep" : "sleeping",
714 lock1->lo_name, lock1->lo_file, lock1->lo_line);
715 }
716 if (lock_list == &p->p_sleeplocks) {
717 lock_list = PCPU_PTR(spinlocks);
718 goto again;
719 }
720#ifdef DDB
721 if (witness_ddb && n)
722 Debugger("witness_sleep");
723#endif /* DDB */
724 critical_exit(savecrit);
725 return (n);
726}
727
728static struct witness *
729enroll(const char *description, struct lock_class *lock_class)
730{
731 struct witness *w;
732
733 if (!witness_watch)
734 return (NULL);
735
736 if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin)
737 return (NULL);
738 mtx_lock_spin(&w_mtx);
739 STAILQ_FOREACH(w, &w_all, w_list) {
740 if (strcmp(description, w->w_name) == 0) {
741 mtx_unlock_spin(&w_mtx);
742 if (lock_class != w->w_class)
743 panic(
744 "lock (%s) %s does not match earlier (%s) lock",
745 description, lock_class->lc_name,
746 w->w_class->lc_name);
747 return (w);
748 }
749 }
750 /*
751 * This isn't quite right, as witness_cold is still 0 while we
752 * enroll all the locks initialized before witness_initialize().
753 */
754 if ((lock_class->lc_flags & LC_SPINLOCK) && !witness_cold)
755 panic("spin lock %s not in order list", description);
756 if ((w = witness_get()) == NULL)
757 return (NULL);
758 w->w_name = description;
759 w->w_class = lock_class;
760 STAILQ_INSERT_HEAD(&w_all, w, w_list);
761 if (lock_class->lc_flags & LC_SPINLOCK)
762 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
763 else if (lock_class->lc_flags & LC_SLEEPLOCK)
764 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
765 else
766 panic("lock class %s is not sleep or spin",
767 lock_class->lc_name);
768 mtx_unlock_spin(&w_mtx);
769
770 return (w);
771}
772
773static int
774itismychild(struct witness *parent, struct witness *child)
775{
776 static int recursed;
777 struct witness_child_list_entry **wcl;
778 struct witness_list *list;
779
780 MPASS(child != NULL && parent != NULL);
781 if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
782 (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
783 panic(
784 "%s: parent (%s) and child (%s) are not the same lock type",
785 __func__, parent->w_class->lc_name,
786 child->w_class->lc_name);
787
788 /*
789 * Insert "child" after "parent"
790 */
791 wcl = &parent->w_children;
792 while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN)
793 wcl = &(*wcl)->wcl_next;
794
795 if (*wcl == NULL) {
796 *wcl = witness_child_get();
797 if (*wcl == NULL)
798 return (1);
799 }
800
801 (*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
802
803 /*
804 * Now prune whole tree. We look for cases where a lock is now
805 * both a descendant and a direct child of a given lock. In that
806 * case, we want to remove the direct child link from the tree.
807 */
808 if (recursed)
809 return (0);
810 recursed = 1;
811 if (parent->w_class->lc_flags & LC_SLEEPLOCK)
812 list = &w_sleep;
813 else
814 list = &w_spin;
815 STAILQ_FOREACH(child, list, w_typelist) {
816 STAILQ_FOREACH(parent, list, w_typelist) {
817 if (!isitmychild(parent, child))
818 continue;
819 removechild(parent, child);
820 if (isitmydescendant(parent, child))
821 continue;
822 itismychild(parent, child);
823 }
824 }
825 recursed = 0;
826 witness_levelall();
827 return (0);
828}
829
830static void
831removechild(struct witness *parent, struct witness *child)
832{
833 struct witness_child_list_entry **wcl, *wcl1;
834 int i;
835
836 for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next)
837 for (i = 0; i < (*wcl)->wcl_count; i++)
838 if ((*wcl)->wcl_children[i] == child)
839 goto found;
840 return;
841found:
842 (*wcl)->wcl_count--;
843 if ((*wcl)->wcl_count > i)
844 (*wcl)->wcl_children[i] =
845 (*wcl)->wcl_children[(*wcl)->wcl_count];
846 MPASS((*wcl)->wcl_children[i] != NULL);
847
848 if ((*wcl)->wcl_count != 0)
849 return;
850
851 wcl1 = *wcl;
852 *wcl = wcl1->wcl_next;
853 witness_child_free(wcl1);
854}
855
856static int
857isitmychild(struct witness *parent, struct witness *child)
858{
859 struct witness_child_list_entry *wcl;
860 int i;
861
862 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
863 for (i = 0; i < wcl->wcl_count; i++) {
864 if (wcl->wcl_children[i] == child)
865 return (1);
866 }
867 }
868 return (0);
869}
870
871static int
872isitmydescendant(struct witness *parent, struct witness *child)
873{
874 struct witness_child_list_entry *wcl;
875 int i, j;
876
877 if (isitmychild(parent, child))
878 return (1);
879 j = 0;
880 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
881 MPASS(j < 1000);
882 for (i = 0; i < wcl->wcl_count; i++) {
883 if (isitmydescendant(wcl->wcl_children[i], child))
884 return (1);
885 }
886 j++;
887 }
888 return (0);
889}
890
891void
892witness_levelall (void)
893{
894 struct witness_list *list;
895 struct witness *w, *w1;
896
897 /*
898 * First clear all levels.
899 */
900 STAILQ_FOREACH(w, &w_all, w_list) {
901 w->w_level = 0;
902 }
903
904 /*
905 * Look for locks with no parent and level all their descendants.
906 */
907 STAILQ_FOREACH(w, &w_all, w_list) {
908 /*
909 * This is just an optimization, technically we could get
910 * away just walking the all list each time.
911 */
912 if (w->w_class->lc_flags & LC_SLEEPLOCK)
913 list = &w_sleep;
914 else
915 list = &w_spin;
916 STAILQ_FOREACH(w1, list, w_typelist) {
917 if (isitmychild(w1, w))
918 goto skip;
919 }
920 witness_leveldescendents(w, 0);
921 skip:
922 }
923}
924
925static void
926witness_leveldescendents(struct witness *parent, int level)
927{
928 struct witness_child_list_entry *wcl;
929 int i;
930
931 if (parent->w_level < level)
932 parent->w_level = level;
933 level++;
934 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
935 for (i = 0; i < wcl->wcl_count; i++)
936 witness_leveldescendents(wcl->wcl_children[i], level);
937}
938
939static void
940witness_displaydescendants(void(*prnt)(const char *fmt, ...),
941 struct witness *parent)
942{
943 struct witness_child_list_entry *wcl;
944 int i, level;
945
946 level = parent->w_level;
947
948 prnt("%-2d", level);
949 for (i = 0; i < level; i++)
950 prnt(" ");
951 prnt("%s", parent->w_name);
952 if (parent->w_file != NULL)
953 prnt(" -- last acquired @ %s:%d\n", parent->w_file,
954 parent->w_line);
955
956 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
957 for (i = 0; i < wcl->wcl_count; i++)
958 witness_displaydescendants(prnt,
959 wcl->wcl_children[i]);
960}
961
962static int
963dup_ok(struct witness *w)
964{
965 const char **dup;
966
967 for (dup = dup_list; *dup != NULL; dup++)
968 if (strcmp(w->w_name, *dup) == 0)
969 return (1);
970 return (0);
971}
972
973static int
974blessed(struct witness *w1, struct witness *w2)
975{
976 int i;
977 struct witness_blessed *b;
978
979 for (i = 0; i < blessed_count; i++) {
980 b = &blessed_list[i];
981 if (strcmp(w1->w_name, b->b_lock1) == 0) {
982 if (strcmp(w2->w_name, b->b_lock2) == 0)
983 return (1);
984 continue;
985 }
986 if (strcmp(w1->w_name, b->b_lock2) == 0)
987 if (strcmp(w2->w_name, b->b_lock1) == 0)
988 return (1);
989 }
990 return (0);
991}
992
993static struct witness *
994witness_get(void)
995{
996 struct witness *w;
997
998 if (STAILQ_EMPTY(&w_free)) {
999 witness_dead = 1;
1000 mtx_unlock_spin(&w_mtx);
1001 printf("%s: witness exhausted\n", __func__);
1002 return (NULL);
1003 }
1004 w = STAILQ_FIRST(&w_free);
1005 STAILQ_REMOVE_HEAD(&w_free, w_list);
1006 bzero(w, sizeof(*w));
1007 return (w);
1008}
1009
1010static void
1011witness_free(struct witness *w)
1012{
1013
1014 STAILQ_INSERT_HEAD(&w_free, w, w_list);
1015}
1016
1017static struct witness_child_list_entry *
1018witness_child_get(void)
1019{
1020 struct witness_child_list_entry *wcl;
1021
1022 wcl = w_child_free;
1023 if (wcl == NULL) {
1024 witness_dead = 1;
1025 mtx_unlock_spin(&w_mtx);
1026 printf("%s: witness exhausted\n", __func__);
1027 return (NULL);
1028 }
1029 w_child_free = wcl->wcl_next;
1030 bzero(wcl, sizeof(*wcl));
1031 return (wcl);
1032}
1033
1034static void
1035witness_child_free(struct witness_child_list_entry *wcl)
1036{
1037
1038 wcl->wcl_next = w_child_free;
1039 w_child_free = wcl;
1040}
1041
1042static struct lock_list_entry *
1043witness_lock_list_get(void)
1044{
1045 struct lock_list_entry *lle;
1046
1047 mtx_lock_spin(&w_mtx);
1048 lle = w_lock_list_free;
1049 if (lle == NULL) {
1050 witness_dead = 1;
1051 mtx_unlock_spin(&w_mtx);
1052 printf("%s: witness exhausted\n", __func__);
1053 return (NULL);
1054 }
1055 w_lock_list_free = lle->ll_next;
1056 mtx_unlock_spin(&w_mtx);
1057 bzero(lle, sizeof(*lle));
1058 return (lle);
1059}
1060
1061static void
1062witness_lock_list_free(struct lock_list_entry *lle)
1063{
1064
1065 mtx_lock_spin(&w_mtx);
1066 lle->ll_next = w_lock_list_free;
1067 w_lock_list_free = lle;
1068 mtx_unlock_spin(&w_mtx);
1069}
1070
1071/*
1072 * Calling this on p != curproc is bad unless we are in ddb.
1073 */
1074int
1075witness_list(struct proc *p)
1076{
1077 struct lock_list_entry **lock_list, *lle;
1078 struct lock_object *lock;
1079 critical_t savecrit;
1080 int i, nheld;
1081
1082 KASSERT(p == curproc || db_active,
1083 ("%s: p != curproc and we aren't in the debugger", __func__));
1084 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1085 nheld = 0;
1086 /*
1087 * Preemption bad because we need PCPU_PTR(spinlocks) to not change.
1088 */
1089 savecrit = critical_enter();
1090 lock_list = &p->p_sleeplocks;
1091again:
1092 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
1093 for (i = lle->ll_count - 1; i >= 0; i--) {
1094 lock = lle->ll_children[i];
1095 printf("\t(%s) %s (%p) locked at %s:%d\n",
1096 lock->lo_class->lc_name, lock->lo_name, lock,
1097 lock->lo_file, lock->lo_line);
1098 nheld++;
1099 }
1100 /*
1101 * We only handle spinlocks if p == curproc. This is somewhat broken
1102 * if p is currently executing on some other CPU and holds spin locks
1103 * as we won't display those locks.
1104 */
1105 if (lock_list == &p->p_sleeplocks && p == curproc) {
1106 lock_list = PCPU_PTR(spinlocks);
1107 goto again;
1108 }
1109 critical_exit(savecrit);
1110
1111 return (nheld);
1112}
1113
1114void
1115witness_save(struct lock_object *lock, const char **filep, int *linep)
1116{
1117
1118 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
1119 if (lock->lo_witness == NULL)
1120 return;
1121
1122 *filep = lock->lo_file;
1123 *linep = lock->lo_line;
1124}
1125
1126void
1127witness_restore(struct lock_object *lock, const char *file, int line)
1128{
1129
1130 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
1131 if (lock->lo_witness == NULL)
1132 return;
1133
1134 lock->lo_witness->w_file = file;
1135 lock->lo_witness->w_line = line;
1136 lock->lo_file = file;
1137 lock->lo_line = line;
1138}
1139
1140#ifdef DDB
1141
1142DB_SHOW_COMMAND(mutexes, db_witness_list)
1143{
1144
1145 witness_list(curproc);
1146}
1147
1148DB_SHOW_COMMAND(witness, db_witness_display)
1149{
1150
1151 witness_display(db_printf);
1152}
1153#endif