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
45 * Date: before 12th century
46 * 1 : attestation of a fact or event : TESTIMONY
47 * 2 : one that gives evidence; specifically : one who testifies in
48 * a cause or before a judicial tribunal
49 * 3 : one asked to be present at a transaction so as to be able to
50 * testify to its having taken place
51 * 4 : one who has personal knowledge of something
52 * 5 a : something serving as evidence or proof : SIGN
53 * b : public affirmation by word or example of usually
54 * religious faith or conviction <the heroic witness to divine
55 * life -- Pilot>
56 * 6 capitalized : a member of the Jehovah's Witnesses
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 threads
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 blessed(struct witness *, struct witness *);
128static void witness_displaydescendants(void(*)(const char *fmt, ...),
129 struct witness *);
130static void witness_leveldescendents(struct witness *parent, int level);
131static void witness_levelall(void);
132static struct witness *witness_get(void);
133static void witness_free(struct witness *m);
134static struct witness_child_list_entry *witness_child_get(void);
135static void witness_child_free(struct witness_child_list_entry *wcl);
136static struct lock_list_entry *witness_lock_list_get(void);
137static void witness_lock_list_free(struct lock_list_entry *lle);
138static struct lock_instance *find_instance(struct lock_list_entry *lock_list,
139 struct lock_object *lock);
140#if defined(DDB)
141static void witness_display_list(void(*prnt)(const char *fmt, ...),
142 struct witness_list *list);
143static void witness_display(void(*)(const char *fmt, ...));
144#endif
145
146MALLOC_DEFINE(M_WITNESS, "witness", "witness structure");
147
148static int witness_watch = 1;
149TUNABLE_INT("debug.witness_watch", &witness_watch);
150SYSCTL_INT(_debug, OID_AUTO, witness_watch, CTLFLAG_RD, &witness_watch, 0, "");
151
152#ifdef DDB
153/*
154 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to
155 * drop into kdebug() when:
156 * - a lock heirarchy violation occurs
157 * - locks are held when going to sleep.
158 */
159#ifdef WITNESS_DDB
160int witness_ddb = 1;
161#else
162int witness_ddb = 0;
163#endif
164TUNABLE_INT("debug.witness_ddb", &witness_ddb);
165SYSCTL_INT(_debug, OID_AUTO, witness_ddb, CTLFLAG_RW, &witness_ddb, 0, "");
166#endif /* DDB */
167
168#ifdef WITNESS_SKIPSPIN
169int witness_skipspin = 1;
170#else
171int witness_skipspin = 0;
172#endif
173TUNABLE_INT("debug.witness_skipspin", &witness_skipspin);
174SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0,
175 "");
176
177static struct mtx w_mtx;
178static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free);
179static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all);
180static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin);
181static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep);
182static struct witness_child_list_entry *w_child_free = NULL;
183static struct lock_list_entry *w_lock_list_free = NULL;
184static int witness_dead; /* fatal error, probably no memory */
185
186static struct witness w_data[WITNESS_COUNT];
187static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT];
188static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
189
190static struct witness_order_list_entry order_lists[] = {
191 { "Giant", &lock_class_mtx_sleep },
192 { "proctree", &lock_class_sx },
193 { "allproc", &lock_class_sx },
194 { "sigio lock", &lock_class_mtx_sleep },
195 { "process group", &lock_class_mtx_sleep },
196 { "process lock", &lock_class_mtx_sleep },
197 { "session", &lock_class_mtx_sleep },
198 { "uidinfo hash", &lock_class_mtx_sleep },
199 { "uidinfo struct", &lock_class_mtx_sleep },
200 { NULL, NULL },
201 /*
202 * spin locks
203 */
204#ifdef SMP
205 { "ap boot", &lock_class_mtx_spin },
206#ifdef __i386__
207 { "com", &lock_class_mtx_spin },
208#endif
209#endif
210 { "sio", &lock_class_mtx_spin },
211#ifdef __i386__
212 { "cy", &lock_class_mtx_spin },
213#endif
214 { "ng_node", &lock_class_mtx_spin },
215 { "ng_worklist", &lock_class_mtx_spin },
216 { "ithread table lock", &lock_class_mtx_spin },
217 { "sched lock", &lock_class_mtx_spin },
218 { "callout", &lock_class_mtx_spin },
219 /*
220 * leaf locks
221 */
222 { "allpmaps", &lock_class_mtx_spin },
223 { "vm page buckets mutex", &lock_class_mtx_spin },
224 { "vm page queue free mutex", &lock_class_mtx_spin },
225 { "icu", &lock_class_mtx_spin },
226#ifdef SMP
227 { "smp rendezvous", &lock_class_mtx_spin },
228#if defined(__i386__) && defined(APIC_IO)
229 { "tlb", &lock_class_mtx_spin },
230#endif
231#endif
232 { "clk", &lock_class_mtx_spin },
233 { "mutex profiling lock", &lock_class_mtx_spin },
234 { "zombie_thread_lock", &lock_class_mtx_spin },
235 { NULL, NULL },
236 { NULL, NULL }
237};
238
239/*
240 * Pairs of locks which have been blessed
241 * Don't complain about order problems with blessed locks
242 */
243static struct witness_blessed blessed_list[] = {
244};
245static int blessed_count =
246 sizeof(blessed_list) / sizeof(struct witness_blessed);
247
248/*
249 * List of all locks in the system.
250 */
251TAILQ_HEAD(, lock_object) all_locks = TAILQ_HEAD_INITIALIZER(all_locks);
252
253static struct mtx all_mtx = {
254 { &lock_class_mtx_sleep, /* mtx_object.lo_class */
255 "All locks list", /* mtx_object.lo_name */
256 "All locks list", /* mtx_object.lo_type */
257 LO_INITIALIZED, /* mtx_object.lo_flags */
258 { NULL, NULL }, /* mtx_object.lo_list */
259 NULL }, /* mtx_object.lo_witness */
260 MTX_UNOWNED, 0, /* mtx_lock, mtx_recurse */
261 TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked),
262 { NULL, NULL } /* mtx_contested */
263};
264
265/*
266 * This global is set to 0 once it becomes safe to use the witness code.
267 */
268static int witness_cold = 1;
269
270/*
271 * Global variables for book keeping.
272 */
273static int lock_cur_cnt;
274static int lock_max_cnt;
275
276/*
277 * The WITNESS-enabled diagnostic code.
278 */
279static void
280witness_initialize(void *dummy __unused)
281{
282 struct lock_object *lock;
283 struct witness_order_list_entry *order;
284 struct witness *w, *w1;
285 int i;
286
287 /*
288 * We have to release Giant before initializing its witness
289 * structure so that WITNESS doesn't get confused.
290 */
291 mtx_unlock(&Giant);
292 mtx_assert(&Giant, MA_NOTOWNED);
293
294 CTR1(KTR_WITNESS, "%s: initializing witness", __func__);
295 TAILQ_INSERT_HEAD(&all_locks, &all_mtx.mtx_object, lo_list);
296 mtx_init(&w_mtx, "witness lock", NULL, MTX_SPIN | MTX_QUIET |
297 MTX_NOWITNESS);
298 for (i = 0; i < WITNESS_COUNT; i++)
299 witness_free(&w_data[i]);
300 for (i = 0; i < WITNESS_CHILDCOUNT; i++)
301 witness_child_free(&w_childdata[i]);
302 for (i = 0; i < LOCK_CHILDCOUNT; i++)
303 witness_lock_list_free(&w_locklistdata[i]);
304
305 /* First add in all the specified order lists. */
306 for (order = order_lists; order->w_name != NULL; order++) {
307 w = enroll(order->w_name, order->w_class);
308 if (w == NULL)
309 continue;
310 w->w_file = "order list";
311 for (order++; order->w_name != NULL; order++) {
312 w1 = enroll(order->w_name, order->w_class);
313 if (w1 == NULL)
314 continue;
315 w1->w_file = "order list";
316 itismychild(w, w1);
317 w = w1;
318 }
319 }
320
321 /* Iterate through all locks and add them to witness. */
322 mtx_lock(&all_mtx);
323 TAILQ_FOREACH(lock, &all_locks, lo_list) {
324 if (lock->lo_flags & LO_WITNESS)
325 lock->lo_witness = enroll(lock->lo_type,
326 lock->lo_class);
327 else
328 lock->lo_witness = NULL;
329 }
330 mtx_unlock(&all_mtx);
331
332 /* Mark the witness code as being ready for use. */
333 atomic_store_rel_int(&witness_cold, 0);
334
335 mtx_lock(&Giant);
336}
337SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize, NULL)
338
339void
340witness_init(struct lock_object *lock)
341{
342 struct lock_class *class;
343
344 class = lock->lo_class;
345 if (lock->lo_flags & LO_INITIALIZED)
346 panic("%s: lock (%s) %s is already initialized", __func__,
347 class->lc_name, lock->lo_name);
348 if ((lock->lo_flags & LO_RECURSABLE) != 0 &&
349 (class->lc_flags & LC_RECURSABLE) == 0)
350 panic("%s: lock (%s) %s can not be recursable", __func__,
351 class->lc_name, lock->lo_name);
352 if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
353 (class->lc_flags & LC_SLEEPABLE) == 0)
354 panic("%s: lock (%s) %s can not be sleepable", __func__,
355 class->lc_name, lock->lo_name);
356 if ((lock->lo_flags & LO_UPGRADABLE) != 0 &&
357 (class->lc_flags & LC_UPGRADABLE) == 0)
358 panic("%s: lock (%s) %s can not be upgradable", __func__,
359 class->lc_name, lock->lo_name);
360
361 mtx_lock(&all_mtx);
362 TAILQ_INSERT_TAIL(&all_locks, lock, lo_list);
363 lock->lo_flags |= LO_INITIALIZED;
364 lock_cur_cnt++;
365 if (lock_cur_cnt > lock_max_cnt)
366 lock_max_cnt = lock_cur_cnt;
367 mtx_unlock(&all_mtx);
368 if (!witness_cold && !witness_dead && panicstr == NULL &&
369 (lock->lo_flags & LO_WITNESS) != 0)
370 lock->lo_witness = enroll(lock->lo_type, class);
371 else
372 lock->lo_witness = NULL;
373}
374
375void
376witness_destroy(struct lock_object *lock)
377{
378 struct witness *w;
379
380 if (witness_cold)
381 panic("lock (%s) %s destroyed while witness_cold",
382 lock->lo_class->lc_name, lock->lo_name);
383 if ((lock->lo_flags & LO_INITIALIZED) == 0)
384 panic("%s: lock (%s) %s is not initialized", __func__,
385 lock->lo_class->lc_name, lock->lo_name);
386
387 /* XXX: need to verify that no one holds the lock */
388 w = lock->lo_witness;
389 if (w != NULL) {
390 mtx_lock_spin(&w_mtx);
391 MPASS(w->w_refcount > 0);
392 w->w_refcount--;
393 mtx_unlock_spin(&w_mtx);
394 }
395
396 mtx_lock(&all_mtx);
397 lock_cur_cnt--;
398 TAILQ_REMOVE(&all_locks, lock, lo_list);
399 lock->lo_flags &= ~LO_INITIALIZED;
400 mtx_unlock(&all_mtx);
401}
402
403#if defined(DDB)
404static void
405witness_display_list(void(*prnt)(const char *fmt, ...),
406 struct witness_list *list)
407{
408 struct witness *w, *w1;
409 int found;
410
411 STAILQ_FOREACH(w, list, w_typelist) {
412 if (w->w_file == NULL)
413 continue;
414 found = 0;
415 STAILQ_FOREACH(w1, list, w_typelist) {
416 if (isitmychild(w1, w)) {
417 found++;
418 break;
419 }
420 }
421 if (found)
422 continue;
423 /*
424 * This lock has no anscestors, display its descendants.
425 */
426 witness_displaydescendants(prnt, w);
427 }
428}
429
430static void
431witness_display(void(*prnt)(const char *fmt, ...))
432{
433 struct witness *w;
434
435 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
436 witness_levelall();
437
438 /*
439 * First, handle sleep locks which have been acquired at least
440 * once.
441 */
442 prnt("Sleep locks:\n");
443 witness_display_list(prnt, &w_sleep);
444
445 /*
446 * Now do spin locks which have been acquired at least once.
447 */
448 prnt("\nSpin locks:\n");
449 witness_display_list(prnt, &w_spin);
450
451 /*
452 * Finally, any locks which have not been acquired yet.
453 */
454 prnt("\nLocks which were never acquired:\n");
455 STAILQ_FOREACH(w, &w_all, w_list) {
456 if (w->w_file != NULL || w->w_refcount == 0)
457 continue;
458 prnt("%s\n", w->w_name);
459 }
460}
461#endif
462
463void
464witness_lock(struct lock_object *lock, int flags, const char *file, int line)
465{
466 struct lock_list_entry **lock_list, *lle;
467 struct lock_instance *lock1, *lock2;
468 struct lock_class *class;
469 struct witness *w, *w1;
470 struct thread *td;
471 int i, j;
472#ifdef DDB
473 int go_into_ddb = 0;
474#endif /* DDB */
475
476 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
477 panicstr != NULL)
478 return;
479 w = lock->lo_witness;
480 class = lock->lo_class;
481 td = curthread;
482
483 if (class->lc_flags & LC_SLEEPLOCK) {
484 /*
485 * Since spin locks include a critical section, this check
486 * impliclty enforces a lock order of all sleep locks before
487 * all spin locks.
488 */
489 if (td->td_critnest != 0 && (flags & LOP_TRYLOCK) == 0)
490 panic("blockable sleep lock (%s) %s @ %s:%d",
491 class->lc_name, lock->lo_name, file, line);
492 lock_list = &td->td_sleeplocks;
493 } else
494 lock_list = PCPU_PTR(spinlocks);
495
496 /*
497 * Try locks do not block if they fail to acquire the lock, thus
498 * there is no danger of deadlocks or of switching while holding a
499 * spin lock if we acquire a lock via a try operation.
500 */
501 if (flags & LOP_TRYLOCK)
502 goto out;
503
504 /*
505 * Is this the first lock acquired? If so, then no order checking
506 * is needed.
507 */
508 if (*lock_list == NULL)
509 goto out;
510
511 /*
512 * Check to see if we are recursing on a lock we already own.
513 */
514 lock1 = find_instance(*lock_list, lock);
515 if (lock1 != NULL) {
516 if ((lock1->li_flags & LI_EXCLUSIVE) != 0 &&
517 (flags & LOP_EXCLUSIVE) == 0) {
518 printf("shared lock of (%s) %s @ %s:%d\n",
519 class->lc_name, lock->lo_name, file, line);
520 printf("while exclusively locked from %s:%d\n",
521 lock1->li_file, lock1->li_line);
522 panic("share->excl");
523 }
524 if ((lock1->li_flags & LI_EXCLUSIVE) == 0 &&
525 (flags & LOP_EXCLUSIVE) != 0) {
526 printf("exclusive lock of (%s) %s @ %s:%d\n",
527 class->lc_name, lock->lo_name, file, line);
528 printf("while share locked from %s:%d\n",
529 lock1->li_file, lock1->li_line);
530 panic("excl->share");
531 }
532 lock1->li_flags++;
533 if ((lock->lo_flags & LO_RECURSABLE) == 0) {
534 printf(
535 "recursed on non-recursive lock (%s) %s @ %s:%d\n",
536 class->lc_name, lock->lo_name, file, line);
537 printf("first acquired @ %s:%d\n", lock1->li_file,
538 lock1->li_line);
539 panic("recurse");
540 }
541 CTR4(KTR_WITNESS, "%s: pid %d recursed on %s r=%d", __func__,
542 td->td_proc->p_pid, lock->lo_name,
543 lock1->li_flags & LI_RECURSEMASK);
544 lock1->li_file = file;
545 lock1->li_line = line;
546 return;
547 }
548
549 /*
550 * Check for duplicate locks of the same type. Note that we only
551 * have to check for this on the last lock we just acquired. Any
552 * other cases will be caught as lock order violations.
553 */
554 lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
555 w1 = lock1->li_lock->lo_witness;
556 if (w1 == w) {
557 if (w->w_same_squawked || (lock->lo_flags & LO_DUPOK))
558 goto out;
559 w->w_same_squawked = 1;
560 printf("acquiring duplicate lock of same type: \"%s\"\n",
561 lock->lo_type);
562 printf(" 1st %s @ %s:%d\n", lock1->li_lock->lo_name,
563 lock1->li_file, lock1->li_line);
564 printf(" 2nd %s @ %s:%d\n", lock->lo_name, file, line);
565#ifdef DDB
566 go_into_ddb = 1;
567#endif /* DDB */
568 goto out;
569 }
570 MPASS(!mtx_owned(&w_mtx));
571 mtx_lock_spin(&w_mtx);
572 /*
573 * If we have a known higher number just say ok
574 */
575 if (witness_watch > 1 && w->w_level > w1->w_level) {
576 mtx_unlock_spin(&w_mtx);
577 goto out;
578 }
579 if (isitmydescendant(w1, w)) {
580 mtx_unlock_spin(&w_mtx);
581 goto out;
582 }
583 for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) {
584 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
585
586 MPASS(j < WITNESS_COUNT);
587 lock1 = &lle->ll_children[i];
588 w1 = lock1->li_lock->lo_witness;
589
590 /*
591 * If this lock doesn't undergo witness checking,
592 * then skip it.
593 */
594 if (w1 == NULL) {
595 KASSERT((lock1->li_lock->lo_flags & LO_WITNESS) == 0,
596 ("lock missing witness structure"));
597 continue;
598 }
599 /*
600 * If we are locking Giant and we slept with this
601 * lock, then skip it.
602 */
603 if ((lock1->li_flags & LI_SLEPT) != 0 &&
604 lock == &Giant.mtx_object)
605 continue;
606 /*
607 * If we are locking a sleepable lock and this lock
608 * isn't sleepable and isn't Giant, we want to treat
609 * it as a lock order violation to enfore a general
610 * lock order of sleepable locks before non-sleepable
611 * locks. Thus, we only bother checking the lock
612 * order hierarchy if we pass the initial test.
613 */
614 if (!((lock->lo_flags & LO_SLEEPABLE) != 0 &&
615 ((lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0 &&
616 lock1->li_lock != &Giant.mtx_object)) &&
617 !isitmydescendant(w, w1))
618 continue;
619 /*
620 * We have a lock order violation, check to see if it
621 * is allowed or has already been yelled about.
622 */
623 mtx_unlock_spin(&w_mtx);
624 if (blessed(w, w1))
625 goto out;
626 if (lock1->li_lock == &Giant.mtx_object) {
627 if (w1->w_Giant_squawked)
628 goto out;
629 else
630 w1->w_Giant_squawked = 1;
631 } else {
632 if (w1->w_other_squawked)
633 goto out;
634 else
635 w1->w_other_squawked = 1;
636 }
637 /*
638 * Ok, yell about it.
639 */
640 printf("lock order reversal\n");
641 /*
642 * Try to locate an earlier lock with
643 * witness w in our list.
644 */
645 do {
646 lock2 = &lle->ll_children[i];
647 MPASS(lock2->li_lock != NULL);
648 if (lock2->li_lock->lo_witness == w)
649 break;
650 i--;
651 if (i == 0 && lle->ll_next != NULL) {
652 lle = lle->ll_next;
653 i = lle->ll_count - 1;
654 MPASS(i != 0);
655 }
656 } while (i >= 0);
657 if (i < 0) {
658 printf(" 1st %p %s (%s) @ %s:%d\n",
659 lock1->li_lock, lock1->li_lock->lo_name,
660 lock1->li_lock->lo_type, lock1->li_file,
661 lock1->li_line);
662 printf(" 2nd %p %s (%s) @ %s:%d\n", lock,
663 lock->lo_name, lock->lo_type, file, line);
664 } else {
665 printf(" 1st %p %s (%s) @ %s:%d\n",
666 lock2->li_lock, lock2->li_lock->lo_name,
667 lock2->li_lock->lo_type, lock2->li_file,
668 lock2->li_line);
669 printf(" 2nd %p %s (%s) @ %s:%d\n",
670 lock1->li_lock, lock1->li_lock->lo_name,
671 lock1->li_lock->lo_type, lock1->li_file,
672 lock1->li_line);
673 printf(" 3rd %p %s (%s) @ %s:%d\n", lock,
674 lock->lo_name, lock->lo_type, file, line);
675 }
676#ifdef DDB
677 go_into_ddb = 1;
678#endif /* DDB */
679 goto out;
680 }
681 }
682 lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
683 /*
684 * Don't build a new relationship if we are locking Giant just
685 * after waking up and the previous lock in the list was acquired
686 * prior to blocking.
687 */
688 if (lock == &Giant.mtx_object && (lock1->li_flags & LI_SLEPT) != 0)
689 mtx_unlock_spin(&w_mtx);
690 else {
691 CTR3(KTR_WITNESS, "%s: adding %s as a child of %s", __func__,
692 lock->lo_type, lock1->li_lock->lo_type);
693 if (!itismychild(lock1->li_lock->lo_witness, w))
694 mtx_unlock_spin(&w_mtx);
695 }
696
697out:
698#ifdef DDB
699 if (witness_ddb && go_into_ddb)
700 Debugger(__func__);
701#endif /* DDB */
702 w->w_file = file;
703 w->w_line = line;
704
705 lle = *lock_list;
706 if (lle == NULL || lle->ll_count == LOCK_NCHILDREN) {
707 lle = witness_lock_list_get();
708 if (lle == NULL)
709 return;
710 lle->ll_next = *lock_list;
711 CTR3(KTR_WITNESS, "%s: pid %d added lle %p", __func__,
712 td->td_proc->p_pid, lle);
713 *lock_list = lle;
714 }
715 lock1 = &lle->ll_children[lle->ll_count++];
716 lock1->li_lock = lock;
717 lock1->li_line = line;
718 lock1->li_file = file;
719 if ((flags & LOP_EXCLUSIVE) != 0)
720 lock1->li_flags = LI_EXCLUSIVE;
721 else
722 lock1->li_flags = 0;
723 CTR4(KTR_WITNESS, "%s: pid %d added %s as lle[%d]", __func__,
724 td->td_proc->p_pid, lock->lo_name, lle->ll_count - 1);
725}
726
727void
728witness_upgrade(struct lock_object *lock, int flags, const char *file, int line)
729{
730 struct lock_instance *instance;
731 struct lock_class *class;
732
733 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
734 if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
735 return;
736 class = lock->lo_class;
737 if ((lock->lo_flags & LO_UPGRADABLE) == 0)
738 panic("upgrade of non-upgradable lock (%s) %s @ %s:%d",
739 class->lc_name, lock->lo_name, file, line);
740 if ((flags & LOP_TRYLOCK) == 0)
741 panic("non-try upgrade of lock (%s) %s @ %s:%d", class->lc_name,
742 lock->lo_name, file, line);
743 if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
744 panic("upgrade of non-sleep lock (%s) %s @ %s:%d",
745 class->lc_name, lock->lo_name, file, line);
746 instance = find_instance(curthread->td_sleeplocks, lock);
747 if (instance == NULL)
748 panic("upgrade of unlocked lock (%s) %s @ %s:%d",
749 class->lc_name, lock->lo_name, file, line);
750 if ((instance->li_flags & LI_EXCLUSIVE) != 0)
751 panic("upgrade of exclusive lock (%s) %s @ %s:%d",
752 class->lc_name, lock->lo_name, file, line);
753 if ((instance->li_flags & LI_RECURSEMASK) != 0)
754 panic("upgrade of recursed lock (%s) %s r=%d @ %s:%d",
755 class->lc_name, lock->lo_name,
756 instance->li_flags & LI_RECURSEMASK, file, line);
757 instance->li_flags |= LI_EXCLUSIVE;
758}
759
760void
761witness_downgrade(struct lock_object *lock, int flags, const char *file,
762 int line)
763{
764 struct lock_instance *instance;
765 struct lock_class *class;
766
767 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
768 if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
769 return;
770 class = lock->lo_class;
771 if ((lock->lo_flags & LO_UPGRADABLE) == 0)
772 panic("downgrade of non-upgradable lock (%s) %s @ %s:%d",
773 class->lc_name, lock->lo_name, file, line);
774 if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
775 panic("downgrade of non-sleep lock (%s) %s @ %s:%d",
776 class->lc_name, lock->lo_name, file, line);
777 instance = find_instance(curthread->td_sleeplocks, lock);
778 if (instance == NULL)
779 panic("downgrade of unlocked lock (%s) %s @ %s:%d",
780 class->lc_name, lock->lo_name, file, line);
781 if ((instance->li_flags & LI_EXCLUSIVE) == 0)
782 panic("downgrade of shared lock (%s) %s @ %s:%d",
783 class->lc_name, lock->lo_name, file, line);
784 if ((instance->li_flags & LI_RECURSEMASK) != 0)
785 panic("downgrade of recursed lock (%s) %s r=%d @ %s:%d",
786 class->lc_name, lock->lo_name,
787 instance->li_flags & LI_RECURSEMASK, file, line);
788 instance->li_flags &= ~LI_EXCLUSIVE;
789}
790
791void
792witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
793{
794 struct lock_list_entry **lock_list, *lle;
795 struct lock_instance *instance;
796 struct lock_class *class;
797 struct thread *td;
798 register_t s;
799 int i, j;
800
801 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
802 panicstr != NULL)
803 return;
804 td = curthread;
805 class = lock->lo_class;
806 if (class->lc_flags & LC_SLEEPLOCK)
807 lock_list = &td->td_sleeplocks;
808 else
809 lock_list = PCPU_PTR(spinlocks);
810 for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
811 for (i = 0; i < (*lock_list)->ll_count; i++) {
812 instance = &(*lock_list)->ll_children[i];
813 if (instance->li_lock == lock) {
814 if ((instance->li_flags & LI_EXCLUSIVE) != 0 &&
815 (flags & LOP_EXCLUSIVE) == 0) {
816 printf(
817 "shared unlock of (%s) %s @ %s:%d\n",
818 class->lc_name, lock->lo_name,
819 file, line);
820 printf(
821 "while exclusively locked from %s:%d\n",
822 instance->li_file,
823 instance->li_line);
824 panic("excl->ushare");
825 }
826 if ((instance->li_flags & LI_EXCLUSIVE) == 0 &&
827 (flags & LOP_EXCLUSIVE) != 0) {
828 printf(
829 "exclusive unlock of (%s) %s @ %s:%d\n",
830 class->lc_name, lock->lo_name,
831 file, line);
832 printf(
833 "while share locked from %s:%d\n",
834 instance->li_file,
835 instance->li_line);
836 panic("share->uexcl");
837 }
838 /* If we are recursed, unrecurse. */
839 if ((instance->li_flags & LI_RECURSEMASK) > 0) {
840 CTR4(KTR_WITNESS,
841 "%s: pid %d unrecursed on %s r=%d", __func__,
842 td->td_proc->p_pid,
843 instance->li_lock->lo_name,
844 instance->li_flags);
845 instance->li_flags--;
846 return;
847 }
848 s = intr_disable();
849 CTR4(KTR_WITNESS,
850 "%s: pid %d removed %s from lle[%d]", __func__,
851 td->td_proc->p_pid,
852 instance->li_lock->lo_name,
853 (*lock_list)->ll_count - 1);
854 for (j = i; j < (*lock_list)->ll_count - 1; j++)
855 (*lock_list)->ll_children[j] =
856 (*lock_list)->ll_children[j + 1];
857 (*lock_list)->ll_count--;
858 intr_restore(s);
859 if ((*lock_list)->ll_count == 0) {
860 lle = *lock_list;
861 *lock_list = lle->ll_next;
862 CTR3(KTR_WITNESS,
863 "%s: pid %d removed lle %p", __func__,
864 td->td_proc->p_pid, lle);
865 witness_lock_list_free(lle);
866 }
867 return;
868 }
869 }
870 panic("lock (%s) %s not locked @ %s:%d", class->lc_name, lock->lo_name,
871 file, line);
872}
873
874/*
875 * Warn if any held locks are not sleepable. Note that Giant and the lock
876 * passed in are both special cases since they are both released during the
877 * sleep process and aren't actually held while the thread is asleep.
878 */
879int
880witness_sleep(int check_only, struct lock_object *lock, const char *file,
881 int line)
882{
883 struct lock_list_entry **lock_list, *lle;
884 struct lock_instance *lock1;
885 struct thread *td;
886 int i, n;
887
888 if (witness_cold || witness_dead || panicstr != NULL)
889 return (0);
890 n = 0;
891 td = curthread;
892 lock_list = &td->td_sleeplocks;
893again:
894 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
895 for (i = lle->ll_count - 1; i >= 0; i--) {
896 lock1 = &lle->ll_children[i];
897 if (lock1->li_lock == lock ||
898 lock1->li_lock == &Giant.mtx_object)
899 continue;
900 if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0) {
901 if (check_only == 0) {
902 CTR3(KTR_WITNESS,
903 "pid %d: sleeping with lock (%s) %s held",
904 td->td_proc->p_pid,
905 lock1->li_lock->lo_class->lc_name,
906 lock1->li_lock->lo_name);
907 lock1->li_flags |= LI_SLEPT;
908 }
909 continue;
910 }
911 n++;
912 printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
913 file, line, check_only ? "could sleep" : "sleeping",
914 lock1->li_lock->lo_name, lock1->li_file,
915 lock1->li_line);
916 }
917 if (lock_list == &td->td_sleeplocks && PCPU_GET(spinlocks) != NULL) {
918 /*
919 * Since we already hold a spinlock preemption is
920 * already blocked.
921 */
922 lock_list = PCPU_PTR(spinlocks);
923 goto again;
924 }
925#ifdef DDB
926 if (witness_ddb && n)
927 Debugger(__func__);
928#endif /* DDB */
929 return (n);
930}
931
| 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
45 * Date: before 12th century
46 * 1 : attestation of a fact or event : TESTIMONY
47 * 2 : one that gives evidence; specifically : one who testifies in
48 * a cause or before a judicial tribunal
49 * 3 : one asked to be present at a transaction so as to be able to
50 * testify to its having taken place
51 * 4 : one who has personal knowledge of something
52 * 5 a : something serving as evidence or proof : SIGN
53 * b : public affirmation by word or example of usually
54 * religious faith or conviction <the heroic witness to divine
55 * life -- Pilot>
56 * 6 capitalized : a member of the Jehovah's Witnesses
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 threads
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 blessed(struct witness *, struct witness *);
128static void witness_displaydescendants(void(*)(const char *fmt, ...),
129 struct witness *);
130static void witness_leveldescendents(struct witness *parent, int level);
131static void witness_levelall(void);
132static struct witness *witness_get(void);
133static void witness_free(struct witness *m);
134static struct witness_child_list_entry *witness_child_get(void);
135static void witness_child_free(struct witness_child_list_entry *wcl);
136static struct lock_list_entry *witness_lock_list_get(void);
137static void witness_lock_list_free(struct lock_list_entry *lle);
138static struct lock_instance *find_instance(struct lock_list_entry *lock_list,
139 struct lock_object *lock);
140#if defined(DDB)
141static void witness_display_list(void(*prnt)(const char *fmt, ...),
142 struct witness_list *list);
143static void witness_display(void(*)(const char *fmt, ...));
144#endif
145
146MALLOC_DEFINE(M_WITNESS, "witness", "witness structure");
147
148static int witness_watch = 1;
149TUNABLE_INT("debug.witness_watch", &witness_watch);
150SYSCTL_INT(_debug, OID_AUTO, witness_watch, CTLFLAG_RD, &witness_watch, 0, "");
151
152#ifdef DDB
153/*
154 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to
155 * drop into kdebug() when:
156 * - a lock heirarchy violation occurs
157 * - locks are held when going to sleep.
158 */
159#ifdef WITNESS_DDB
160int witness_ddb = 1;
161#else
162int witness_ddb = 0;
163#endif
164TUNABLE_INT("debug.witness_ddb", &witness_ddb);
165SYSCTL_INT(_debug, OID_AUTO, witness_ddb, CTLFLAG_RW, &witness_ddb, 0, "");
166#endif /* DDB */
167
168#ifdef WITNESS_SKIPSPIN
169int witness_skipspin = 1;
170#else
171int witness_skipspin = 0;
172#endif
173TUNABLE_INT("debug.witness_skipspin", &witness_skipspin);
174SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0,
175 "");
176
177static struct mtx w_mtx;
178static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free);
179static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all);
180static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin);
181static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep);
182static struct witness_child_list_entry *w_child_free = NULL;
183static struct lock_list_entry *w_lock_list_free = NULL;
184static int witness_dead; /* fatal error, probably no memory */
185
186static struct witness w_data[WITNESS_COUNT];
187static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT];
188static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
189
190static struct witness_order_list_entry order_lists[] = {
191 { "Giant", &lock_class_mtx_sleep },
192 { "proctree", &lock_class_sx },
193 { "allproc", &lock_class_sx },
194 { "sigio lock", &lock_class_mtx_sleep },
195 { "process group", &lock_class_mtx_sleep },
196 { "process lock", &lock_class_mtx_sleep },
197 { "session", &lock_class_mtx_sleep },
198 { "uidinfo hash", &lock_class_mtx_sleep },
199 { "uidinfo struct", &lock_class_mtx_sleep },
200 { NULL, NULL },
201 /*
202 * spin locks
203 */
204#ifdef SMP
205 { "ap boot", &lock_class_mtx_spin },
206#ifdef __i386__
207 { "com", &lock_class_mtx_spin },
208#endif
209#endif
210 { "sio", &lock_class_mtx_spin },
211#ifdef __i386__
212 { "cy", &lock_class_mtx_spin },
213#endif
214 { "ng_node", &lock_class_mtx_spin },
215 { "ng_worklist", &lock_class_mtx_spin },
216 { "ithread table lock", &lock_class_mtx_spin },
217 { "sched lock", &lock_class_mtx_spin },
218 { "callout", &lock_class_mtx_spin },
219 /*
220 * leaf locks
221 */
222 { "allpmaps", &lock_class_mtx_spin },
223 { "vm page buckets mutex", &lock_class_mtx_spin },
224 { "vm page queue free mutex", &lock_class_mtx_spin },
225 { "icu", &lock_class_mtx_spin },
226#ifdef SMP
227 { "smp rendezvous", &lock_class_mtx_spin },
228#if defined(__i386__) && defined(APIC_IO)
229 { "tlb", &lock_class_mtx_spin },
230#endif
231#endif
232 { "clk", &lock_class_mtx_spin },
233 { "mutex profiling lock", &lock_class_mtx_spin },
234 { "zombie_thread_lock", &lock_class_mtx_spin },
235 { NULL, NULL },
236 { NULL, NULL }
237};
238
239/*
240 * Pairs of locks which have been blessed
241 * Don't complain about order problems with blessed locks
242 */
243static struct witness_blessed blessed_list[] = {
244};
245static int blessed_count =
246 sizeof(blessed_list) / sizeof(struct witness_blessed);
247
248/*
249 * List of all locks in the system.
250 */
251TAILQ_HEAD(, lock_object) all_locks = TAILQ_HEAD_INITIALIZER(all_locks);
252
253static struct mtx all_mtx = {
254 { &lock_class_mtx_sleep, /* mtx_object.lo_class */
255 "All locks list", /* mtx_object.lo_name */
256 "All locks list", /* mtx_object.lo_type */
257 LO_INITIALIZED, /* mtx_object.lo_flags */
258 { NULL, NULL }, /* mtx_object.lo_list */
259 NULL }, /* mtx_object.lo_witness */
260 MTX_UNOWNED, 0, /* mtx_lock, mtx_recurse */
261 TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked),
262 { NULL, NULL } /* mtx_contested */
263};
264
265/*
266 * This global is set to 0 once it becomes safe to use the witness code.
267 */
268static int witness_cold = 1;
269
270/*
271 * Global variables for book keeping.
272 */
273static int lock_cur_cnt;
274static int lock_max_cnt;
275
276/*
277 * The WITNESS-enabled diagnostic code.
278 */
279static void
280witness_initialize(void *dummy __unused)
281{
282 struct lock_object *lock;
283 struct witness_order_list_entry *order;
284 struct witness *w, *w1;
285 int i;
286
287 /*
288 * We have to release Giant before initializing its witness
289 * structure so that WITNESS doesn't get confused.
290 */
291 mtx_unlock(&Giant);
292 mtx_assert(&Giant, MA_NOTOWNED);
293
294 CTR1(KTR_WITNESS, "%s: initializing witness", __func__);
295 TAILQ_INSERT_HEAD(&all_locks, &all_mtx.mtx_object, lo_list);
296 mtx_init(&w_mtx, "witness lock", NULL, MTX_SPIN | MTX_QUIET |
297 MTX_NOWITNESS);
298 for (i = 0; i < WITNESS_COUNT; i++)
299 witness_free(&w_data[i]);
300 for (i = 0; i < WITNESS_CHILDCOUNT; i++)
301 witness_child_free(&w_childdata[i]);
302 for (i = 0; i < LOCK_CHILDCOUNT; i++)
303 witness_lock_list_free(&w_locklistdata[i]);
304
305 /* First add in all the specified order lists. */
306 for (order = order_lists; order->w_name != NULL; order++) {
307 w = enroll(order->w_name, order->w_class);
308 if (w == NULL)
309 continue;
310 w->w_file = "order list";
311 for (order++; order->w_name != NULL; order++) {
312 w1 = enroll(order->w_name, order->w_class);
313 if (w1 == NULL)
314 continue;
315 w1->w_file = "order list";
316 itismychild(w, w1);
317 w = w1;
318 }
319 }
320
321 /* Iterate through all locks and add them to witness. */
322 mtx_lock(&all_mtx);
323 TAILQ_FOREACH(lock, &all_locks, lo_list) {
324 if (lock->lo_flags & LO_WITNESS)
325 lock->lo_witness = enroll(lock->lo_type,
326 lock->lo_class);
327 else
328 lock->lo_witness = NULL;
329 }
330 mtx_unlock(&all_mtx);
331
332 /* Mark the witness code as being ready for use. */
333 atomic_store_rel_int(&witness_cold, 0);
334
335 mtx_lock(&Giant);
336}
337SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize, NULL)
338
339void
340witness_init(struct lock_object *lock)
341{
342 struct lock_class *class;
343
344 class = lock->lo_class;
345 if (lock->lo_flags & LO_INITIALIZED)
346 panic("%s: lock (%s) %s is already initialized", __func__,
347 class->lc_name, lock->lo_name);
348 if ((lock->lo_flags & LO_RECURSABLE) != 0 &&
349 (class->lc_flags & LC_RECURSABLE) == 0)
350 panic("%s: lock (%s) %s can not be recursable", __func__,
351 class->lc_name, lock->lo_name);
352 if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
353 (class->lc_flags & LC_SLEEPABLE) == 0)
354 panic("%s: lock (%s) %s can not be sleepable", __func__,
355 class->lc_name, lock->lo_name);
356 if ((lock->lo_flags & LO_UPGRADABLE) != 0 &&
357 (class->lc_flags & LC_UPGRADABLE) == 0)
358 panic("%s: lock (%s) %s can not be upgradable", __func__,
359 class->lc_name, lock->lo_name);
360
361 mtx_lock(&all_mtx);
362 TAILQ_INSERT_TAIL(&all_locks, lock, lo_list);
363 lock->lo_flags |= LO_INITIALIZED;
364 lock_cur_cnt++;
365 if (lock_cur_cnt > lock_max_cnt)
366 lock_max_cnt = lock_cur_cnt;
367 mtx_unlock(&all_mtx);
368 if (!witness_cold && !witness_dead && panicstr == NULL &&
369 (lock->lo_flags & LO_WITNESS) != 0)
370 lock->lo_witness = enroll(lock->lo_type, class);
371 else
372 lock->lo_witness = NULL;
373}
374
375void
376witness_destroy(struct lock_object *lock)
377{
378 struct witness *w;
379
380 if (witness_cold)
381 panic("lock (%s) %s destroyed while witness_cold",
382 lock->lo_class->lc_name, lock->lo_name);
383 if ((lock->lo_flags & LO_INITIALIZED) == 0)
384 panic("%s: lock (%s) %s is not initialized", __func__,
385 lock->lo_class->lc_name, lock->lo_name);
386
387 /* XXX: need to verify that no one holds the lock */
388 w = lock->lo_witness;
389 if (w != NULL) {
390 mtx_lock_spin(&w_mtx);
391 MPASS(w->w_refcount > 0);
392 w->w_refcount--;
393 mtx_unlock_spin(&w_mtx);
394 }
395
396 mtx_lock(&all_mtx);
397 lock_cur_cnt--;
398 TAILQ_REMOVE(&all_locks, lock, lo_list);
399 lock->lo_flags &= ~LO_INITIALIZED;
400 mtx_unlock(&all_mtx);
401}
402
403#if defined(DDB)
404static void
405witness_display_list(void(*prnt)(const char *fmt, ...),
406 struct witness_list *list)
407{
408 struct witness *w, *w1;
409 int found;
410
411 STAILQ_FOREACH(w, list, w_typelist) {
412 if (w->w_file == NULL)
413 continue;
414 found = 0;
415 STAILQ_FOREACH(w1, list, w_typelist) {
416 if (isitmychild(w1, w)) {
417 found++;
418 break;
419 }
420 }
421 if (found)
422 continue;
423 /*
424 * This lock has no anscestors, display its descendants.
425 */
426 witness_displaydescendants(prnt, w);
427 }
428}
429
430static void
431witness_display(void(*prnt)(const char *fmt, ...))
432{
433 struct witness *w;
434
435 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
436 witness_levelall();
437
438 /*
439 * First, handle sleep locks which have been acquired at least
440 * once.
441 */
442 prnt("Sleep locks:\n");
443 witness_display_list(prnt, &w_sleep);
444
445 /*
446 * Now do spin locks which have been acquired at least once.
447 */
448 prnt("\nSpin locks:\n");
449 witness_display_list(prnt, &w_spin);
450
451 /*
452 * Finally, any locks which have not been acquired yet.
453 */
454 prnt("\nLocks which were never acquired:\n");
455 STAILQ_FOREACH(w, &w_all, w_list) {
456 if (w->w_file != NULL || w->w_refcount == 0)
457 continue;
458 prnt("%s\n", w->w_name);
459 }
460}
461#endif
462
463void
464witness_lock(struct lock_object *lock, int flags, const char *file, int line)
465{
466 struct lock_list_entry **lock_list, *lle;
467 struct lock_instance *lock1, *lock2;
468 struct lock_class *class;
469 struct witness *w, *w1;
470 struct thread *td;
471 int i, j;
472#ifdef DDB
473 int go_into_ddb = 0;
474#endif /* DDB */
475
476 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
477 panicstr != NULL)
478 return;
479 w = lock->lo_witness;
480 class = lock->lo_class;
481 td = curthread;
482
483 if (class->lc_flags & LC_SLEEPLOCK) {
484 /*
485 * Since spin locks include a critical section, this check
486 * impliclty enforces a lock order of all sleep locks before
487 * all spin locks.
488 */
489 if (td->td_critnest != 0 && (flags & LOP_TRYLOCK) == 0)
490 panic("blockable sleep lock (%s) %s @ %s:%d",
491 class->lc_name, lock->lo_name, file, line);
492 lock_list = &td->td_sleeplocks;
493 } else
494 lock_list = PCPU_PTR(spinlocks);
495
496 /*
497 * Try locks do not block if they fail to acquire the lock, thus
498 * there is no danger of deadlocks or of switching while holding a
499 * spin lock if we acquire a lock via a try operation.
500 */
501 if (flags & LOP_TRYLOCK)
502 goto out;
503
504 /*
505 * Is this the first lock acquired? If so, then no order checking
506 * is needed.
507 */
508 if (*lock_list == NULL)
509 goto out;
510
511 /*
512 * Check to see if we are recursing on a lock we already own.
513 */
514 lock1 = find_instance(*lock_list, lock);
515 if (lock1 != NULL) {
516 if ((lock1->li_flags & LI_EXCLUSIVE) != 0 &&
517 (flags & LOP_EXCLUSIVE) == 0) {
518 printf("shared lock of (%s) %s @ %s:%d\n",
519 class->lc_name, lock->lo_name, file, line);
520 printf("while exclusively locked from %s:%d\n",
521 lock1->li_file, lock1->li_line);
522 panic("share->excl");
523 }
524 if ((lock1->li_flags & LI_EXCLUSIVE) == 0 &&
525 (flags & LOP_EXCLUSIVE) != 0) {
526 printf("exclusive lock of (%s) %s @ %s:%d\n",
527 class->lc_name, lock->lo_name, file, line);
528 printf("while share locked from %s:%d\n",
529 lock1->li_file, lock1->li_line);
530 panic("excl->share");
531 }
532 lock1->li_flags++;
533 if ((lock->lo_flags & LO_RECURSABLE) == 0) {
534 printf(
535 "recursed on non-recursive lock (%s) %s @ %s:%d\n",
536 class->lc_name, lock->lo_name, file, line);
537 printf("first acquired @ %s:%d\n", lock1->li_file,
538 lock1->li_line);
539 panic("recurse");
540 }
541 CTR4(KTR_WITNESS, "%s: pid %d recursed on %s r=%d", __func__,
542 td->td_proc->p_pid, lock->lo_name,
543 lock1->li_flags & LI_RECURSEMASK);
544 lock1->li_file = file;
545 lock1->li_line = line;
546 return;
547 }
548
549 /*
550 * Check for duplicate locks of the same type. Note that we only
551 * have to check for this on the last lock we just acquired. Any
552 * other cases will be caught as lock order violations.
553 */
554 lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
555 w1 = lock1->li_lock->lo_witness;
556 if (w1 == w) {
557 if (w->w_same_squawked || (lock->lo_flags & LO_DUPOK))
558 goto out;
559 w->w_same_squawked = 1;
560 printf("acquiring duplicate lock of same type: \"%s\"\n",
561 lock->lo_type);
562 printf(" 1st %s @ %s:%d\n", lock1->li_lock->lo_name,
563 lock1->li_file, lock1->li_line);
564 printf(" 2nd %s @ %s:%d\n", lock->lo_name, file, line);
565#ifdef DDB
566 go_into_ddb = 1;
567#endif /* DDB */
568 goto out;
569 }
570 MPASS(!mtx_owned(&w_mtx));
571 mtx_lock_spin(&w_mtx);
572 /*
573 * If we have a known higher number just say ok
574 */
575 if (witness_watch > 1 && w->w_level > w1->w_level) {
576 mtx_unlock_spin(&w_mtx);
577 goto out;
578 }
579 if (isitmydescendant(w1, w)) {
580 mtx_unlock_spin(&w_mtx);
581 goto out;
582 }
583 for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) {
584 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
585
586 MPASS(j < WITNESS_COUNT);
587 lock1 = &lle->ll_children[i];
588 w1 = lock1->li_lock->lo_witness;
589
590 /*
591 * If this lock doesn't undergo witness checking,
592 * then skip it.
593 */
594 if (w1 == NULL) {
595 KASSERT((lock1->li_lock->lo_flags & LO_WITNESS) == 0,
596 ("lock missing witness structure"));
597 continue;
598 }
599 /*
600 * If we are locking Giant and we slept with this
601 * lock, then skip it.
602 */
603 if ((lock1->li_flags & LI_SLEPT) != 0 &&
604 lock == &Giant.mtx_object)
605 continue;
606 /*
607 * If we are locking a sleepable lock and this lock
608 * isn't sleepable and isn't Giant, we want to treat
609 * it as a lock order violation to enfore a general
610 * lock order of sleepable locks before non-sleepable
611 * locks. Thus, we only bother checking the lock
612 * order hierarchy if we pass the initial test.
613 */
614 if (!((lock->lo_flags & LO_SLEEPABLE) != 0 &&
615 ((lock1->li_lock->lo_flags & LO_SLEEPABLE) == 0 &&
616 lock1->li_lock != &Giant.mtx_object)) &&
617 !isitmydescendant(w, w1))
618 continue;
619 /*
620 * We have a lock order violation, check to see if it
621 * is allowed or has already been yelled about.
622 */
623 mtx_unlock_spin(&w_mtx);
624 if (blessed(w, w1))
625 goto out;
626 if (lock1->li_lock == &Giant.mtx_object) {
627 if (w1->w_Giant_squawked)
628 goto out;
629 else
630 w1->w_Giant_squawked = 1;
631 } else {
632 if (w1->w_other_squawked)
633 goto out;
634 else
635 w1->w_other_squawked = 1;
636 }
637 /*
638 * Ok, yell about it.
639 */
640 printf("lock order reversal\n");
641 /*
642 * Try to locate an earlier lock with
643 * witness w in our list.
644 */
645 do {
646 lock2 = &lle->ll_children[i];
647 MPASS(lock2->li_lock != NULL);
648 if (lock2->li_lock->lo_witness == w)
649 break;
650 i--;
651 if (i == 0 && lle->ll_next != NULL) {
652 lle = lle->ll_next;
653 i = lle->ll_count - 1;
654 MPASS(i != 0);
655 }
656 } while (i >= 0);
657 if (i < 0) {
658 printf(" 1st %p %s (%s) @ %s:%d\n",
659 lock1->li_lock, lock1->li_lock->lo_name,
660 lock1->li_lock->lo_type, lock1->li_file,
661 lock1->li_line);
662 printf(" 2nd %p %s (%s) @ %s:%d\n", lock,
663 lock->lo_name, lock->lo_type, file, line);
664 } else {
665 printf(" 1st %p %s (%s) @ %s:%d\n",
666 lock2->li_lock, lock2->li_lock->lo_name,
667 lock2->li_lock->lo_type, lock2->li_file,
668 lock2->li_line);
669 printf(" 2nd %p %s (%s) @ %s:%d\n",
670 lock1->li_lock, lock1->li_lock->lo_name,
671 lock1->li_lock->lo_type, lock1->li_file,
672 lock1->li_line);
673 printf(" 3rd %p %s (%s) @ %s:%d\n", lock,
674 lock->lo_name, lock->lo_type, file, line);
675 }
676#ifdef DDB
677 go_into_ddb = 1;
678#endif /* DDB */
679 goto out;
680 }
681 }
682 lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
683 /*
684 * Don't build a new relationship if we are locking Giant just
685 * after waking up and the previous lock in the list was acquired
686 * prior to blocking.
687 */
688 if (lock == &Giant.mtx_object && (lock1->li_flags & LI_SLEPT) != 0)
689 mtx_unlock_spin(&w_mtx);
690 else {
691 CTR3(KTR_WITNESS, "%s: adding %s as a child of %s", __func__,
692 lock->lo_type, lock1->li_lock->lo_type);
693 if (!itismychild(lock1->li_lock->lo_witness, w))
694 mtx_unlock_spin(&w_mtx);
695 }
696
697out:
698#ifdef DDB
699 if (witness_ddb && go_into_ddb)
700 Debugger(__func__);
701#endif /* DDB */
702 w->w_file = file;
703 w->w_line = line;
704
705 lle = *lock_list;
706 if (lle == NULL || lle->ll_count == LOCK_NCHILDREN) {
707 lle = witness_lock_list_get();
708 if (lle == NULL)
709 return;
710 lle->ll_next = *lock_list;
711 CTR3(KTR_WITNESS, "%s: pid %d added lle %p", __func__,
712 td->td_proc->p_pid, lle);
713 *lock_list = lle;
714 }
715 lock1 = &lle->ll_children[lle->ll_count++];
716 lock1->li_lock = lock;
717 lock1->li_line = line;
718 lock1->li_file = file;
719 if ((flags & LOP_EXCLUSIVE) != 0)
720 lock1->li_flags = LI_EXCLUSIVE;
721 else
722 lock1->li_flags = 0;
723 CTR4(KTR_WITNESS, "%s: pid %d added %s as lle[%d]", __func__,
724 td->td_proc->p_pid, lock->lo_name, lle->ll_count - 1);
725}
726
727void
728witness_upgrade(struct lock_object *lock, int flags, const char *file, int line)
729{
730 struct lock_instance *instance;
731 struct lock_class *class;
732
733 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
734 if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
735 return;
736 class = lock->lo_class;
737 if ((lock->lo_flags & LO_UPGRADABLE) == 0)
738 panic("upgrade of non-upgradable lock (%s) %s @ %s:%d",
739 class->lc_name, lock->lo_name, file, line);
740 if ((flags & LOP_TRYLOCK) == 0)
741 panic("non-try upgrade of lock (%s) %s @ %s:%d", class->lc_name,
742 lock->lo_name, file, line);
743 if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
744 panic("upgrade of non-sleep lock (%s) %s @ %s:%d",
745 class->lc_name, lock->lo_name, file, line);
746 instance = find_instance(curthread->td_sleeplocks, lock);
747 if (instance == NULL)
748 panic("upgrade of unlocked lock (%s) %s @ %s:%d",
749 class->lc_name, lock->lo_name, file, line);
750 if ((instance->li_flags & LI_EXCLUSIVE) != 0)
751 panic("upgrade of exclusive lock (%s) %s @ %s:%d",
752 class->lc_name, lock->lo_name, file, line);
753 if ((instance->li_flags & LI_RECURSEMASK) != 0)
754 panic("upgrade of recursed lock (%s) %s r=%d @ %s:%d",
755 class->lc_name, lock->lo_name,
756 instance->li_flags & LI_RECURSEMASK, file, line);
757 instance->li_flags |= LI_EXCLUSIVE;
758}
759
760void
761witness_downgrade(struct lock_object *lock, int flags, const char *file,
762 int line)
763{
764 struct lock_instance *instance;
765 struct lock_class *class;
766
767 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
768 if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
769 return;
770 class = lock->lo_class;
771 if ((lock->lo_flags & LO_UPGRADABLE) == 0)
772 panic("downgrade of non-upgradable lock (%s) %s @ %s:%d",
773 class->lc_name, lock->lo_name, file, line);
774 if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
775 panic("downgrade of non-sleep lock (%s) %s @ %s:%d",
776 class->lc_name, lock->lo_name, file, line);
777 instance = find_instance(curthread->td_sleeplocks, lock);
778 if (instance == NULL)
779 panic("downgrade of unlocked lock (%s) %s @ %s:%d",
780 class->lc_name, lock->lo_name, file, line);
781 if ((instance->li_flags & LI_EXCLUSIVE) == 0)
782 panic("downgrade of shared lock (%s) %s @ %s:%d",
783 class->lc_name, lock->lo_name, file, line);
784 if ((instance->li_flags & LI_RECURSEMASK) != 0)
785 panic("downgrade of recursed lock (%s) %s r=%d @ %s:%d",
786 class->lc_name, lock->lo_name,
787 instance->li_flags & LI_RECURSEMASK, file, line);
788 instance->li_flags &= ~LI_EXCLUSIVE;
789}
790
791void
792witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
793{
794 struct lock_list_entry **lock_list, *lle;
795 struct lock_instance *instance;
796 struct lock_class *class;
797 struct thread *td;
798 register_t s;
799 int i, j;
800
801 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
802 panicstr != NULL)
803 return;
804 td = curthread;
805 class = lock->lo_class;
806 if (class->lc_flags & LC_SLEEPLOCK)
807 lock_list = &td->td_sleeplocks;
808 else
809 lock_list = PCPU_PTR(spinlocks);
810 for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
811 for (i = 0; i < (*lock_list)->ll_count; i++) {
812 instance = &(*lock_list)->ll_children[i];
813 if (instance->li_lock == lock) {
814 if ((instance->li_flags & LI_EXCLUSIVE) != 0 &&
815 (flags & LOP_EXCLUSIVE) == 0) {
816 printf(
817 "shared unlock of (%s) %s @ %s:%d\n",
818 class->lc_name, lock->lo_name,
819 file, line);
820 printf(
821 "while exclusively locked from %s:%d\n",
822 instance->li_file,
823 instance->li_line);
824 panic("excl->ushare");
825 }
826 if ((instance->li_flags & LI_EXCLUSIVE) == 0 &&
827 (flags & LOP_EXCLUSIVE) != 0) {
828 printf(
829 "exclusive unlock of (%s) %s @ %s:%d\n",
830 class->lc_name, lock->lo_name,
831 file, line);
832 printf(
833 "while share locked from %s:%d\n",
834 instance->li_file,
835 instance->li_line);
836 panic("share->uexcl");
837 }
838 /* If we are recursed, unrecurse. */
839 if ((instance->li_flags & LI_RECURSEMASK) > 0) {
840 CTR4(KTR_WITNESS,
841 "%s: pid %d unrecursed on %s r=%d", __func__,
842 td->td_proc->p_pid,
843 instance->li_lock->lo_name,
844 instance->li_flags);
845 instance->li_flags--;
846 return;
847 }
848 s = intr_disable();
849 CTR4(KTR_WITNESS,
850 "%s: pid %d removed %s from lle[%d]", __func__,
851 td->td_proc->p_pid,
852 instance->li_lock->lo_name,
853 (*lock_list)->ll_count - 1);
854 for (j = i; j < (*lock_list)->ll_count - 1; j++)
855 (*lock_list)->ll_children[j] =
856 (*lock_list)->ll_children[j + 1];
857 (*lock_list)->ll_count--;
858 intr_restore(s);
859 if ((*lock_list)->ll_count == 0) {
860 lle = *lock_list;
861 *lock_list = lle->ll_next;
862 CTR3(KTR_WITNESS,
863 "%s: pid %d removed lle %p", __func__,
864 td->td_proc->p_pid, lle);
865 witness_lock_list_free(lle);
866 }
867 return;
868 }
869 }
870 panic("lock (%s) %s not locked @ %s:%d", class->lc_name, lock->lo_name,
871 file, line);
872}
873
874/*
875 * Warn if any held locks are not sleepable. Note that Giant and the lock
876 * passed in are both special cases since they are both released during the
877 * sleep process and aren't actually held while the thread is asleep.
878 */
879int
880witness_sleep(int check_only, struct lock_object *lock, const char *file,
881 int line)
882{
883 struct lock_list_entry **lock_list, *lle;
884 struct lock_instance *lock1;
885 struct thread *td;
886 int i, n;
887
888 if (witness_cold || witness_dead || panicstr != NULL)
889 return (0);
890 n = 0;
891 td = curthread;
892 lock_list = &td->td_sleeplocks;
893again:
894 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
895 for (i = lle->ll_count - 1; i >= 0; i--) {
896 lock1 = &lle->ll_children[i];
897 if (lock1->li_lock == lock ||
898 lock1->li_lock == &Giant.mtx_object)
899 continue;
900 if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0) {
901 if (check_only == 0) {
902 CTR3(KTR_WITNESS,
903 "pid %d: sleeping with lock (%s) %s held",
904 td->td_proc->p_pid,
905 lock1->li_lock->lo_class->lc_name,
906 lock1->li_lock->lo_name);
907 lock1->li_flags |= LI_SLEPT;
908 }
909 continue;
910 }
911 n++;
912 printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
913 file, line, check_only ? "could sleep" : "sleeping",
914 lock1->li_lock->lo_name, lock1->li_file,
915 lock1->li_line);
916 }
917 if (lock_list == &td->td_sleeplocks && PCPU_GET(spinlocks) != NULL) {
918 /*
919 * Since we already hold a spinlock preemption is
920 * already blocked.
921 */
922 lock_list = PCPU_PTR(spinlocks);
923 goto again;
924 }
925#ifdef DDB
926 if (witness_ddb && n)
927 Debugger(__func__);
928#endif /* DDB */
929 return (n);
930}
931
|
932static struct witness *
933enroll(const char *description, struct lock_class *lock_class)
934{
935 struct witness *w;
936
937 if (!witness_watch || witness_dead || panicstr != NULL)
938 return (NULL);
939 if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin)
940 return (NULL);
941 mtx_lock_spin(&w_mtx);
942 STAILQ_FOREACH(w, &w_all, w_list) {
943 if (w->w_name == description || (w->w_refcount > 0 &&
944 strcmp(description, w->w_name) == 0)) {
945 w->w_refcount++;
946 mtx_unlock_spin(&w_mtx);
947 if (lock_class != w->w_class)
948 panic(
949 "lock (%s) %s does not match earlier (%s) lock",
950 description, lock_class->lc_name,
951 w->w_class->lc_name);
952 return (w);
953 }
954 }
955 /*
956 * This isn't quite right, as witness_cold is still 0 while we
957 * enroll all the locks initialized before witness_initialize().
958 */
959 if ((lock_class->lc_flags & LC_SPINLOCK) && !witness_cold) {
960 mtx_unlock_spin(&w_mtx);
961 panic("spin lock %s not in order list", description);
962 }
963 if ((w = witness_get()) == NULL)
964 return (NULL);
965 w->w_name = description;
966 w->w_class = lock_class;
967 w->w_refcount = 1;
968 STAILQ_INSERT_HEAD(&w_all, w, w_list);
969 if (lock_class->lc_flags & LC_SPINLOCK)
970 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
971 else if (lock_class->lc_flags & LC_SLEEPLOCK)
972 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
973 else {
974 mtx_unlock_spin(&w_mtx);
975 panic("lock class %s is not sleep or spin",
976 lock_class->lc_name);
977 }
978 mtx_unlock_spin(&w_mtx);
979 return (w);
980}
981
982static int
983itismychild(struct witness *parent, struct witness *child)
984{
985 static int recursed;
986 struct witness_child_list_entry **wcl;
987 struct witness_list *list;
988
989 MPASS(child != NULL && parent != NULL);
990 if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
991 (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
992 panic(
993 "%s: parent (%s) and child (%s) are not the same lock type",
994 __func__, parent->w_class->lc_name,
995 child->w_class->lc_name);
996
997 /*
998 * Insert "child" after "parent"
999 */
1000 wcl = &parent->w_children;
1001 while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN)
1002 wcl = &(*wcl)->wcl_next;
1003 if (*wcl == NULL) {
1004 *wcl = witness_child_get();
1005 if (*wcl == NULL)
1006 return (1);
1007 }
1008 (*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
1009
1010 /*
1011 * Now prune whole tree. We look for cases where a lock is now
1012 * both a descendant and a direct child of a given lock. In that
1013 * case, we want to remove the direct child link from the tree.
1014 */
1015 if (recursed)
1016 return (0);
1017 recursed = 1;
1018 if (parent->w_class->lc_flags & LC_SLEEPLOCK)
1019 list = &w_sleep;
1020 else
1021 list = &w_spin;
1022 STAILQ_FOREACH(child, list, w_typelist) {
1023 STAILQ_FOREACH(parent, list, w_typelist) {
1024 if (!isitmychild(parent, child))
1025 continue;
1026 removechild(parent, child);
1027 if (isitmydescendant(parent, child))
1028 continue;
1029 itismychild(parent, child);
1030 }
1031 }
1032 recursed = 0;
1033 witness_levelall();
1034 return (0);
1035}
1036
1037static void
1038removechild(struct witness *parent, struct witness *child)
1039{
1040 struct witness_child_list_entry **wcl, *wcl1;
1041 int i;
1042
1043 for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next)
1044 for (i = 0; i < (*wcl)->wcl_count; i++)
1045 if ((*wcl)->wcl_children[i] == child)
1046 goto found;
1047 return;
1048found:
1049 (*wcl)->wcl_count--;
1050 if ((*wcl)->wcl_count > i)
1051 (*wcl)->wcl_children[i] =
1052 (*wcl)->wcl_children[(*wcl)->wcl_count];
1053 MPASS((*wcl)->wcl_children[i] != NULL);
1054 if ((*wcl)->wcl_count != 0)
1055 return;
1056 wcl1 = *wcl;
1057 *wcl = wcl1->wcl_next;
1058 witness_child_free(wcl1);
1059}
1060
1061static int
1062isitmychild(struct witness *parent, struct witness *child)
1063{
1064 struct witness_child_list_entry *wcl;
1065 int i;
1066
1067 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1068 for (i = 0; i < wcl->wcl_count; i++) {
1069 if (wcl->wcl_children[i] == child)
1070 return (1);
1071 }
1072 }
1073 return (0);
1074}
1075
1076static int
1077isitmydescendant(struct witness *parent, struct witness *child)
1078{
1079 struct witness_child_list_entry *wcl;
1080 int i, j;
1081
1082 if (isitmychild(parent, child))
1083 return (1);
1084 j = 0;
1085 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1086 MPASS(j < 1000);
1087 for (i = 0; i < wcl->wcl_count; i++) {
1088 if (isitmydescendant(wcl->wcl_children[i], child))
1089 return (1);
1090 }
1091 j++;
1092 }
1093 return (0);
1094}
1095
1096void
1097witness_levelall (void)
1098{
1099 struct witness_list *list;
1100 struct witness *w, *w1;
1101
1102 /*
1103 * First clear all levels.
1104 */
1105 STAILQ_FOREACH(w, &w_all, w_list) {
1106 w->w_level = 0;
1107 }
1108
1109 /*
1110 * Look for locks with no parent and level all their descendants.
1111 */
1112 STAILQ_FOREACH(w, &w_all, w_list) {
1113 /*
1114 * This is just an optimization, technically we could get
1115 * away just walking the all list each time.
1116 */
1117 if (w->w_class->lc_flags & LC_SLEEPLOCK)
1118 list = &w_sleep;
1119 else
1120 list = &w_spin;
1121 STAILQ_FOREACH(w1, list, w_typelist) {
1122 if (isitmychild(w1, w))
1123 goto skip;
1124 }
1125 witness_leveldescendents(w, 0);
1126 skip:
1127 ; /* silence GCC 3.x */
1128 }
1129}
1130
1131static void
1132witness_leveldescendents(struct witness *parent, int level)
1133{
1134 struct witness_child_list_entry *wcl;
1135 int i;
1136
1137 if (parent->w_level < level)
1138 parent->w_level = level;
1139 level++;
1140 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
1141 for (i = 0; i < wcl->wcl_count; i++)
1142 witness_leveldescendents(wcl->wcl_children[i], level);
1143}
1144
1145static void
1146witness_displaydescendants(void(*prnt)(const char *fmt, ...),
1147 struct witness *parent)
1148{
1149 struct witness_child_list_entry *wcl;
1150 int i, level;
1151
1152 level = parent->w_level;
1153 prnt("%-2d", level);
1154 for (i = 0; i < level; i++)
1155 prnt(" ");
1156 if (parent->w_refcount > 0) {
1157 prnt("%s", parent->w_name);
1158 if (parent->w_file != NULL)
1159 prnt(" -- last acquired @ %s:%d\n", parent->w_file,
1160 parent->w_line);
1161 } else
1162 prnt("(dead)\n");
1163 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
1164 for (i = 0; i < wcl->wcl_count; i++)
1165 witness_displaydescendants(prnt,
1166 wcl->wcl_children[i]);
1167}
1168
1169static int
1170blessed(struct witness *w1, struct witness *w2)
1171{
1172 int i;
1173 struct witness_blessed *b;
1174
1175 for (i = 0; i < blessed_count; i++) {
1176 b = &blessed_list[i];
1177 if (strcmp(w1->w_name, b->b_lock1) == 0) {
1178 if (strcmp(w2->w_name, b->b_lock2) == 0)
1179 return (1);
1180 continue;
1181 }
1182 if (strcmp(w1->w_name, b->b_lock2) == 0)
1183 if (strcmp(w2->w_name, b->b_lock1) == 0)
1184 return (1);
1185 }
1186 return (0);
1187}
1188
1189static struct witness *
1190witness_get(void)
1191{
1192 struct witness *w;
1193
1194 if (witness_dead) {
1195 mtx_unlock_spin(&w_mtx);
1196 return (NULL);
1197 }
1198 if (STAILQ_EMPTY(&w_free)) {
1199 witness_dead = 1;
1200 mtx_unlock_spin(&w_mtx);
1201 printf("%s: witness exhausted\n", __func__);
1202 return (NULL);
1203 }
1204 w = STAILQ_FIRST(&w_free);
1205 STAILQ_REMOVE_HEAD(&w_free, w_list);
1206 bzero(w, sizeof(*w));
1207 return (w);
1208}
1209
1210static void
1211witness_free(struct witness *w)
1212{
1213
1214 STAILQ_INSERT_HEAD(&w_free, w, w_list);
1215}
1216
1217static struct witness_child_list_entry *
1218witness_child_get(void)
1219{
1220 struct witness_child_list_entry *wcl;
1221
1222 if (witness_dead) {
1223 mtx_unlock_spin(&w_mtx);
1224 return (NULL);
1225 }
1226 wcl = w_child_free;
1227 if (wcl == NULL) {
1228 witness_dead = 1;
1229 mtx_unlock_spin(&w_mtx);
1230 printf("%s: witness exhausted\n", __func__);
1231 return (NULL);
1232 }
1233 w_child_free = wcl->wcl_next;
1234 bzero(wcl, sizeof(*wcl));
1235 return (wcl);
1236}
1237
1238static void
1239witness_child_free(struct witness_child_list_entry *wcl)
1240{
1241
1242 wcl->wcl_next = w_child_free;
1243 w_child_free = wcl;
1244}
1245
1246static struct lock_list_entry *
1247witness_lock_list_get(void)
1248{
1249 struct lock_list_entry *lle;
1250
1251 if (witness_dead)
1252 return (NULL);
1253 mtx_lock_spin(&w_mtx);
1254 lle = w_lock_list_free;
1255 if (lle == NULL) {
1256 witness_dead = 1;
1257 mtx_unlock_spin(&w_mtx);
1258 printf("%s: witness exhausted\n", __func__);
1259 return (NULL);
1260 }
1261 w_lock_list_free = lle->ll_next;
1262 mtx_unlock_spin(&w_mtx);
1263 bzero(lle, sizeof(*lle));
1264 return (lle);
1265}
1266
1267static void
1268witness_lock_list_free(struct lock_list_entry *lle)
1269{
1270
1271 mtx_lock_spin(&w_mtx);
1272 lle->ll_next = w_lock_list_free;
1273 w_lock_list_free = lle;
1274 mtx_unlock_spin(&w_mtx);
1275}
1276
1277static struct lock_instance *
1278find_instance(struct lock_list_entry *lock_list, struct lock_object *lock)
1279{
1280 struct lock_list_entry *lle;
1281 struct lock_instance *instance;
1282 int i;
1283
1284 for (lle = lock_list; lle != NULL; lle = lle->ll_next)
1285 for (i = lle->ll_count - 1; i >= 0; i--) {
1286 instance = &lle->ll_children[i];
1287 if (instance->li_lock == lock)
1288 return (instance);
1289 }
1290 return (NULL);
1291}
1292
1293int
1294witness_list_locks(struct lock_list_entry **lock_list)
1295{
1296 struct lock_list_entry *lle;
1297 struct lock_instance *instance;
1298 struct lock_object *lock;
1299 int i, nheld;
1300
1301 nheld = 0;
1302 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
1303 for (i = lle->ll_count - 1; i >= 0; i--) {
1304 instance = &lle->ll_children[i];
1305 lock = instance->li_lock;
1306 printf("%s %s %s",
1307 (instance->li_flags & LI_EXCLUSIVE) != 0 ?
1308 "exclusive" : "shared",
1309 lock->lo_class->lc_name, lock->lo_name);
1310 if (lock->lo_type != lock->lo_name)
1311 printf(" (%s)", lock->lo_type);
1312 printf(" r = %d (%p) locked @ %s:%d\n",
1313 instance->li_flags & LI_RECURSEMASK, lock,
1314 instance->li_file, instance->li_line);
1315 nheld++;
1316 }
1317 return (nheld);
1318}
1319
1320/*
1321 * Calling this on td != curthread is bad unless we are in ddb.
1322 */
1323int
1324witness_list(struct thread *td)
1325{
1326 int nheld;
1327
1328 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1329#ifdef DDB
1330 KASSERT(td == curthread || db_active,
1331 ("%s: td != curthread and we aren't in the debugger", __func__));
1332 if (!db_active && witness_dead)
1333 return (0);
1334#else
1335 KASSERT(td == curthread, ("%s: p != curthread", __func__));
1336 if (witness_dead)
1337 return (0);
1338#endif
1339 nheld = witness_list_locks(&td->td_sleeplocks);
1340
1341 /*
1342 * We only handle spinlocks if td == curthread. This is somewhat broken
1343 * if td is currently executing on some other CPU and holds spin locks
1344 * as we won't display those locks. If we had a MI way of getting
1345 * the per-cpu data for a given cpu then we could use
1346 * td->td_kse->ke_oncpu to get the list of spinlocks for this thread
1347 * and "fix" this.
1348 *
1349 * That still wouldn't really fix this unless we locked sched_lock
1350 * or stopped the other CPU to make sure it wasn't changing the list
1351 * out from under us. It is probably best to just not try to handle
1352 * threads on other CPU's for now.
1353 */
1354 if (td == curthread && PCPU_GET(spinlocks) != NULL)
1355 nheld += witness_list_locks(PCPU_PTR(spinlocks));
1356
1357 return (nheld);
1358}
1359
1360void
1361witness_save(struct lock_object *lock, const char **filep, int *linep)
1362{
1363 struct lock_instance *instance;
1364
1365 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1366 if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
1367 return;
1368 if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
1369 panic("%s: lock (%s) %s is not a sleep lock", __func__,
1370 lock->lo_class->lc_name, lock->lo_name);
1371 instance = find_instance(curthread->td_sleeplocks, lock);
1372 if (instance == NULL)
1373 panic("%s: lock (%s) %s not locked", __func__,
1374 lock->lo_class->lc_name, lock->lo_name);
1375 *filep = instance->li_file;
1376 *linep = instance->li_line;
1377}
1378
1379void
1380witness_restore(struct lock_object *lock, const char *file, int line)
1381{
1382 struct lock_instance *instance;
1383
1384 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1385 if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
1386 return;
1387 if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
1388 panic("%s: lock (%s) %s is not a sleep lock", __func__,
1389 lock->lo_class->lc_name, lock->lo_name);
1390 instance = find_instance(curthread->td_sleeplocks, lock);
1391 if (instance == NULL)
1392 panic("%s: lock (%s) %s not locked", __func__,
1393 lock->lo_class->lc_name, lock->lo_name);
1394 lock->lo_witness->w_file = file;
1395 lock->lo_witness->w_line = line;
1396 instance->li_file = file;
1397 instance->li_line = line;
1398}
1399
1400void
1401witness_assert(struct lock_object *lock, int flags, const char *file, int line)
1402{
1403#ifdef INVARIANT_SUPPORT
1404 struct lock_instance *instance;
1405
1406 if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
1407 return;
1408 if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) != 0)
1409 instance = find_instance(curthread->td_sleeplocks, lock);
1410 else if ((lock->lo_class->lc_flags & LC_SPINLOCK) != 0)
1411 instance = find_instance(PCPU_GET(spinlocks), lock);
1412 else {
1413 panic("Lock (%s) %s is not sleep or spin!",
1414 lock->lo_class->lc_name, lock->lo_name);
1415 return;
1416 }
1417 switch (flags) {
1418 case LA_UNLOCKED:
1419 if (instance != NULL)
1420 panic("Lock (%s) %s locked @ %s:%d.",
1421 lock->lo_class->lc_name, lock->lo_name, file, line);
1422 break;
1423 case LA_LOCKED:
1424 case LA_LOCKED | LA_RECURSED:
1425 case LA_LOCKED | LA_NOTRECURSED:
1426 case LA_SLOCKED:
1427 case LA_SLOCKED | LA_RECURSED:
1428 case LA_SLOCKED | LA_NOTRECURSED:
1429 case LA_XLOCKED:
1430 case LA_XLOCKED | LA_RECURSED:
1431 case LA_XLOCKED | LA_NOTRECURSED:
1432 if (instance == NULL) {
1433 panic("Lock (%s) %s not locked @ %s:%d.",
1434 lock->lo_class->lc_name, lock->lo_name, file, line);
1435 break;
1436 }
1437 if ((flags & LA_XLOCKED) != 0 &&
1438 (instance->li_flags & LI_EXCLUSIVE) == 0)
1439 panic("Lock (%s) %s not exclusively locked @ %s:%d.",
1440 lock->lo_class->lc_name, lock->lo_name, file, line);
1441 if ((flags & LA_SLOCKED) != 0 &&
1442 (instance->li_flags & LI_EXCLUSIVE) != 0)
1443 panic("Lock (%s) %s exclusively locked @ %s:%d.",
1444 lock->lo_class->lc_name, lock->lo_name, file, line);
1445 if ((flags & LA_RECURSED) != 0 &&
1446 (instance->li_flags & LI_RECURSEMASK) == 0)
1447 panic("Lock (%s) %s not recursed @ %s:%d.",
1448 lock->lo_class->lc_name, lock->lo_name, file, line);
1449 if ((flags & LA_NOTRECURSED) != 0 &&
1450 (instance->li_flags & LI_RECURSEMASK) != 0)
1451 panic("Lock (%s) %s recursed @ %s:%d.",
1452 lock->lo_class->lc_name, lock->lo_name, file, line);
1453 break;
1454 default:
1455 panic("Invalid lock assertion at %s:%d.", file, line);
1456
1457 }
1458#endif /* INVARIANT_SUPPORT */
1459}
1460
1461#ifdef DDB
1462
1463DB_SHOW_COMMAND(locks, db_witness_list)
1464{
1465 struct thread *td;
1466 pid_t pid;
1467 struct proc *p;
1468
1469 if (have_addr) {
1470 pid = (addr % 16) + ((addr >> 4) % 16) * 10 +
1471 ((addr >> 8) % 16) * 100 + ((addr >> 12) % 16) * 1000 +
1472 ((addr >> 16) % 16) * 10000;
1473 /* sx_slock(&allproc_lock); */
1474 FOREACH_PROC_IN_SYSTEM(p) {
1475 if (p->p_pid == pid)
1476 break;
1477 }
1478 /* sx_sunlock(&allproc_lock); */
1479 if (p == NULL) {
1480 db_printf("pid %d not found\n", pid);
1481 return;
1482 }
1483 FOREACH_THREAD_IN_PROC(p, td) {
1484 witness_list(td);
1485 }
1486 } else {
1487 td = curthread;
1488 witness_list(td);
1489 }
1490}
1491
1492DB_SHOW_COMMAND(witness, db_witness_display)
1493{
1494
1495 witness_display(db_printf);
1496}
1497#endif
| 954static struct witness *
955enroll(const char *description, struct lock_class *lock_class)
956{
957 struct witness *w;
958
959 if (!witness_watch || witness_dead || panicstr != NULL)
960 return (NULL);
961 if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin)
962 return (NULL);
963 mtx_lock_spin(&w_mtx);
964 STAILQ_FOREACH(w, &w_all, w_list) {
965 if (w->w_name == description || (w->w_refcount > 0 &&
966 strcmp(description, w->w_name) == 0)) {
967 w->w_refcount++;
968 mtx_unlock_spin(&w_mtx);
969 if (lock_class != w->w_class)
970 panic(
971 "lock (%s) %s does not match earlier (%s) lock",
972 description, lock_class->lc_name,
973 w->w_class->lc_name);
974 return (w);
975 }
976 }
977 /*
978 * This isn't quite right, as witness_cold is still 0 while we
979 * enroll all the locks initialized before witness_initialize().
980 */
981 if ((lock_class->lc_flags & LC_SPINLOCK) && !witness_cold) {
982 mtx_unlock_spin(&w_mtx);
983 panic("spin lock %s not in order list", description);
984 }
985 if ((w = witness_get()) == NULL)
986 return (NULL);
987 w->w_name = description;
988 w->w_class = lock_class;
989 w->w_refcount = 1;
990 STAILQ_INSERT_HEAD(&w_all, w, w_list);
991 if (lock_class->lc_flags & LC_SPINLOCK)
992 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
993 else if (lock_class->lc_flags & LC_SLEEPLOCK)
994 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
995 else {
996 mtx_unlock_spin(&w_mtx);
997 panic("lock class %s is not sleep or spin",
998 lock_class->lc_name);
999 }
1000 mtx_unlock_spin(&w_mtx);
1001 return (w);
1002}
1003
1004static int
1005itismychild(struct witness *parent, struct witness *child)
1006{
1007 static int recursed;
1008 struct witness_child_list_entry **wcl;
1009 struct witness_list *list;
1010
1011 MPASS(child != NULL && parent != NULL);
1012 if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
1013 (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
1014 panic(
1015 "%s: parent (%s) and child (%s) are not the same lock type",
1016 __func__, parent->w_class->lc_name,
1017 child->w_class->lc_name);
1018
1019 /*
1020 * Insert "child" after "parent"
1021 */
1022 wcl = &parent->w_children;
1023 while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN)
1024 wcl = &(*wcl)->wcl_next;
1025 if (*wcl == NULL) {
1026 *wcl = witness_child_get();
1027 if (*wcl == NULL)
1028 return (1);
1029 }
1030 (*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
1031
1032 /*
1033 * Now prune whole tree. We look for cases where a lock is now
1034 * both a descendant and a direct child of a given lock. In that
1035 * case, we want to remove the direct child link from the tree.
1036 */
1037 if (recursed)
1038 return (0);
1039 recursed = 1;
1040 if (parent->w_class->lc_flags & LC_SLEEPLOCK)
1041 list = &w_sleep;
1042 else
1043 list = &w_spin;
1044 STAILQ_FOREACH(child, list, w_typelist) {
1045 STAILQ_FOREACH(parent, list, w_typelist) {
1046 if (!isitmychild(parent, child))
1047 continue;
1048 removechild(parent, child);
1049 if (isitmydescendant(parent, child))
1050 continue;
1051 itismychild(parent, child);
1052 }
1053 }
1054 recursed = 0;
1055 witness_levelall();
1056 return (0);
1057}
1058
1059static void
1060removechild(struct witness *parent, struct witness *child)
1061{
1062 struct witness_child_list_entry **wcl, *wcl1;
1063 int i;
1064
1065 for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next)
1066 for (i = 0; i < (*wcl)->wcl_count; i++)
1067 if ((*wcl)->wcl_children[i] == child)
1068 goto found;
1069 return;
1070found:
1071 (*wcl)->wcl_count--;
1072 if ((*wcl)->wcl_count > i)
1073 (*wcl)->wcl_children[i] =
1074 (*wcl)->wcl_children[(*wcl)->wcl_count];
1075 MPASS((*wcl)->wcl_children[i] != NULL);
1076 if ((*wcl)->wcl_count != 0)
1077 return;
1078 wcl1 = *wcl;
1079 *wcl = wcl1->wcl_next;
1080 witness_child_free(wcl1);
1081}
1082
1083static int
1084isitmychild(struct witness *parent, struct witness *child)
1085{
1086 struct witness_child_list_entry *wcl;
1087 int i;
1088
1089 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1090 for (i = 0; i < wcl->wcl_count; i++) {
1091 if (wcl->wcl_children[i] == child)
1092 return (1);
1093 }
1094 }
1095 return (0);
1096}
1097
1098static int
1099isitmydescendant(struct witness *parent, struct witness *child)
1100{
1101 struct witness_child_list_entry *wcl;
1102 int i, j;
1103
1104 if (isitmychild(parent, child))
1105 return (1);
1106 j = 0;
1107 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1108 MPASS(j < 1000);
1109 for (i = 0; i < wcl->wcl_count; i++) {
1110 if (isitmydescendant(wcl->wcl_children[i], child))
1111 return (1);
1112 }
1113 j++;
1114 }
1115 return (0);
1116}
1117
1118void
1119witness_levelall (void)
1120{
1121 struct witness_list *list;
1122 struct witness *w, *w1;
1123
1124 /*
1125 * First clear all levels.
1126 */
1127 STAILQ_FOREACH(w, &w_all, w_list) {
1128 w->w_level = 0;
1129 }
1130
1131 /*
1132 * Look for locks with no parent and level all their descendants.
1133 */
1134 STAILQ_FOREACH(w, &w_all, w_list) {
1135 /*
1136 * This is just an optimization, technically we could get
1137 * away just walking the all list each time.
1138 */
1139 if (w->w_class->lc_flags & LC_SLEEPLOCK)
1140 list = &w_sleep;
1141 else
1142 list = &w_spin;
1143 STAILQ_FOREACH(w1, list, w_typelist) {
1144 if (isitmychild(w1, w))
1145 goto skip;
1146 }
1147 witness_leveldescendents(w, 0);
1148 skip:
1149 ; /* silence GCC 3.x */
1150 }
1151}
1152
1153static void
1154witness_leveldescendents(struct witness *parent, int level)
1155{
1156 struct witness_child_list_entry *wcl;
1157 int i;
1158
1159 if (parent->w_level < level)
1160 parent->w_level = level;
1161 level++;
1162 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
1163 for (i = 0; i < wcl->wcl_count; i++)
1164 witness_leveldescendents(wcl->wcl_children[i], level);
1165}
1166
1167static void
1168witness_displaydescendants(void(*prnt)(const char *fmt, ...),
1169 struct witness *parent)
1170{
1171 struct witness_child_list_entry *wcl;
1172 int i, level;
1173
1174 level = parent->w_level;
1175 prnt("%-2d", level);
1176 for (i = 0; i < level; i++)
1177 prnt(" ");
1178 if (parent->w_refcount > 0) {
1179 prnt("%s", parent->w_name);
1180 if (parent->w_file != NULL)
1181 prnt(" -- last acquired @ %s:%d\n", parent->w_file,
1182 parent->w_line);
1183 } else
1184 prnt("(dead)\n");
1185 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
1186 for (i = 0; i < wcl->wcl_count; i++)
1187 witness_displaydescendants(prnt,
1188 wcl->wcl_children[i]);
1189}
1190
1191static int
1192blessed(struct witness *w1, struct witness *w2)
1193{
1194 int i;
1195 struct witness_blessed *b;
1196
1197 for (i = 0; i < blessed_count; i++) {
1198 b = &blessed_list[i];
1199 if (strcmp(w1->w_name, b->b_lock1) == 0) {
1200 if (strcmp(w2->w_name, b->b_lock2) == 0)
1201 return (1);
1202 continue;
1203 }
1204 if (strcmp(w1->w_name, b->b_lock2) == 0)
1205 if (strcmp(w2->w_name, b->b_lock1) == 0)
1206 return (1);
1207 }
1208 return (0);
1209}
1210
1211static struct witness *
1212witness_get(void)
1213{
1214 struct witness *w;
1215
1216 if (witness_dead) {
1217 mtx_unlock_spin(&w_mtx);
1218 return (NULL);
1219 }
1220 if (STAILQ_EMPTY(&w_free)) {
1221 witness_dead = 1;
1222 mtx_unlock_spin(&w_mtx);
1223 printf("%s: witness exhausted\n", __func__);
1224 return (NULL);
1225 }
1226 w = STAILQ_FIRST(&w_free);
1227 STAILQ_REMOVE_HEAD(&w_free, w_list);
1228 bzero(w, sizeof(*w));
1229 return (w);
1230}
1231
1232static void
1233witness_free(struct witness *w)
1234{
1235
1236 STAILQ_INSERT_HEAD(&w_free, w, w_list);
1237}
1238
1239static struct witness_child_list_entry *
1240witness_child_get(void)
1241{
1242 struct witness_child_list_entry *wcl;
1243
1244 if (witness_dead) {
1245 mtx_unlock_spin(&w_mtx);
1246 return (NULL);
1247 }
1248 wcl = w_child_free;
1249 if (wcl == NULL) {
1250 witness_dead = 1;
1251 mtx_unlock_spin(&w_mtx);
1252 printf("%s: witness exhausted\n", __func__);
1253 return (NULL);
1254 }
1255 w_child_free = wcl->wcl_next;
1256 bzero(wcl, sizeof(*wcl));
1257 return (wcl);
1258}
1259
1260static void
1261witness_child_free(struct witness_child_list_entry *wcl)
1262{
1263
1264 wcl->wcl_next = w_child_free;
1265 w_child_free = wcl;
1266}
1267
1268static struct lock_list_entry *
1269witness_lock_list_get(void)
1270{
1271 struct lock_list_entry *lle;
1272
1273 if (witness_dead)
1274 return (NULL);
1275 mtx_lock_spin(&w_mtx);
1276 lle = w_lock_list_free;
1277 if (lle == NULL) {
1278 witness_dead = 1;
1279 mtx_unlock_spin(&w_mtx);
1280 printf("%s: witness exhausted\n", __func__);
1281 return (NULL);
1282 }
1283 w_lock_list_free = lle->ll_next;
1284 mtx_unlock_spin(&w_mtx);
1285 bzero(lle, sizeof(*lle));
1286 return (lle);
1287}
1288
1289static void
1290witness_lock_list_free(struct lock_list_entry *lle)
1291{
1292
1293 mtx_lock_spin(&w_mtx);
1294 lle->ll_next = w_lock_list_free;
1295 w_lock_list_free = lle;
1296 mtx_unlock_spin(&w_mtx);
1297}
1298
1299static struct lock_instance *
1300find_instance(struct lock_list_entry *lock_list, struct lock_object *lock)
1301{
1302 struct lock_list_entry *lle;
1303 struct lock_instance *instance;
1304 int i;
1305
1306 for (lle = lock_list; lle != NULL; lle = lle->ll_next)
1307 for (i = lle->ll_count - 1; i >= 0; i--) {
1308 instance = &lle->ll_children[i];
1309 if (instance->li_lock == lock)
1310 return (instance);
1311 }
1312 return (NULL);
1313}
1314
1315int
1316witness_list_locks(struct lock_list_entry **lock_list)
1317{
1318 struct lock_list_entry *lle;
1319 struct lock_instance *instance;
1320 struct lock_object *lock;
1321 int i, nheld;
1322
1323 nheld = 0;
1324 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
1325 for (i = lle->ll_count - 1; i >= 0; i--) {
1326 instance = &lle->ll_children[i];
1327 lock = instance->li_lock;
1328 printf("%s %s %s",
1329 (instance->li_flags & LI_EXCLUSIVE) != 0 ?
1330 "exclusive" : "shared",
1331 lock->lo_class->lc_name, lock->lo_name);
1332 if (lock->lo_type != lock->lo_name)
1333 printf(" (%s)", lock->lo_type);
1334 printf(" r = %d (%p) locked @ %s:%d\n",
1335 instance->li_flags & LI_RECURSEMASK, lock,
1336 instance->li_file, instance->li_line);
1337 nheld++;
1338 }
1339 return (nheld);
1340}
1341
1342/*
1343 * Calling this on td != curthread is bad unless we are in ddb.
1344 */
1345int
1346witness_list(struct thread *td)
1347{
1348 int nheld;
1349
1350 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1351#ifdef DDB
1352 KASSERT(td == curthread || db_active,
1353 ("%s: td != curthread and we aren't in the debugger", __func__));
1354 if (!db_active && witness_dead)
1355 return (0);
1356#else
1357 KASSERT(td == curthread, ("%s: p != curthread", __func__));
1358 if (witness_dead)
1359 return (0);
1360#endif
1361 nheld = witness_list_locks(&td->td_sleeplocks);
1362
1363 /*
1364 * We only handle spinlocks if td == curthread. This is somewhat broken
1365 * if td is currently executing on some other CPU and holds spin locks
1366 * as we won't display those locks. If we had a MI way of getting
1367 * the per-cpu data for a given cpu then we could use
1368 * td->td_kse->ke_oncpu to get the list of spinlocks for this thread
1369 * and "fix" this.
1370 *
1371 * That still wouldn't really fix this unless we locked sched_lock
1372 * or stopped the other CPU to make sure it wasn't changing the list
1373 * out from under us. It is probably best to just not try to handle
1374 * threads on other CPU's for now.
1375 */
1376 if (td == curthread && PCPU_GET(spinlocks) != NULL)
1377 nheld += witness_list_locks(PCPU_PTR(spinlocks));
1378
1379 return (nheld);
1380}
1381
1382void
1383witness_save(struct lock_object *lock, const char **filep, int *linep)
1384{
1385 struct lock_instance *instance;
1386
1387 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1388 if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
1389 return;
1390 if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
1391 panic("%s: lock (%s) %s is not a sleep lock", __func__,
1392 lock->lo_class->lc_name, lock->lo_name);
1393 instance = find_instance(curthread->td_sleeplocks, lock);
1394 if (instance == NULL)
1395 panic("%s: lock (%s) %s not locked", __func__,
1396 lock->lo_class->lc_name, lock->lo_name);
1397 *filep = instance->li_file;
1398 *linep = instance->li_line;
1399}
1400
1401void
1402witness_restore(struct lock_object *lock, const char *file, int line)
1403{
1404 struct lock_instance *instance;
1405
1406 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1407 if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
1408 return;
1409 if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) == 0)
1410 panic("%s: lock (%s) %s is not a sleep lock", __func__,
1411 lock->lo_class->lc_name, lock->lo_name);
1412 instance = find_instance(curthread->td_sleeplocks, lock);
1413 if (instance == NULL)
1414 panic("%s: lock (%s) %s not locked", __func__,
1415 lock->lo_class->lc_name, lock->lo_name);
1416 lock->lo_witness->w_file = file;
1417 lock->lo_witness->w_line = line;
1418 instance->li_file = file;
1419 instance->li_line = line;
1420}
1421
1422void
1423witness_assert(struct lock_object *lock, int flags, const char *file, int line)
1424{
1425#ifdef INVARIANT_SUPPORT
1426 struct lock_instance *instance;
1427
1428 if (lock->lo_witness == NULL || witness_dead || panicstr != NULL)
1429 return;
1430 if ((lock->lo_class->lc_flags & LC_SLEEPLOCK) != 0)
1431 instance = find_instance(curthread->td_sleeplocks, lock);
1432 else if ((lock->lo_class->lc_flags & LC_SPINLOCK) != 0)
1433 instance = find_instance(PCPU_GET(spinlocks), lock);
1434 else {
1435 panic("Lock (%s) %s is not sleep or spin!",
1436 lock->lo_class->lc_name, lock->lo_name);
1437 return;
1438 }
1439 switch (flags) {
1440 case LA_UNLOCKED:
1441 if (instance != NULL)
1442 panic("Lock (%s) %s locked @ %s:%d.",
1443 lock->lo_class->lc_name, lock->lo_name, file, line);
1444 break;
1445 case LA_LOCKED:
1446 case LA_LOCKED | LA_RECURSED:
1447 case LA_LOCKED | LA_NOTRECURSED:
1448 case LA_SLOCKED:
1449 case LA_SLOCKED | LA_RECURSED:
1450 case LA_SLOCKED | LA_NOTRECURSED:
1451 case LA_XLOCKED:
1452 case LA_XLOCKED | LA_RECURSED:
1453 case LA_XLOCKED | LA_NOTRECURSED:
1454 if (instance == NULL) {
1455 panic("Lock (%s) %s not locked @ %s:%d.",
1456 lock->lo_class->lc_name, lock->lo_name, file, line);
1457 break;
1458 }
1459 if ((flags & LA_XLOCKED) != 0 &&
1460 (instance->li_flags & LI_EXCLUSIVE) == 0)
1461 panic("Lock (%s) %s not exclusively locked @ %s:%d.",
1462 lock->lo_class->lc_name, lock->lo_name, file, line);
1463 if ((flags & LA_SLOCKED) != 0 &&
1464 (instance->li_flags & LI_EXCLUSIVE) != 0)
1465 panic("Lock (%s) %s exclusively locked @ %s:%d.",
1466 lock->lo_class->lc_name, lock->lo_name, file, line);
1467 if ((flags & LA_RECURSED) != 0 &&
1468 (instance->li_flags & LI_RECURSEMASK) == 0)
1469 panic("Lock (%s) %s not recursed @ %s:%d.",
1470 lock->lo_class->lc_name, lock->lo_name, file, line);
1471 if ((flags & LA_NOTRECURSED) != 0 &&
1472 (instance->li_flags & LI_RECURSEMASK) != 0)
1473 panic("Lock (%s) %s recursed @ %s:%d.",
1474 lock->lo_class->lc_name, lock->lo_name, file, line);
1475 break;
1476 default:
1477 panic("Invalid lock assertion at %s:%d.", file, line);
1478
1479 }
1480#endif /* INVARIANT_SUPPORT */
1481}
1482
1483#ifdef DDB
1484
1485DB_SHOW_COMMAND(locks, db_witness_list)
1486{
1487 struct thread *td;
1488 pid_t pid;
1489 struct proc *p;
1490
1491 if (have_addr) {
1492 pid = (addr % 16) + ((addr >> 4) % 16) * 10 +
1493 ((addr >> 8) % 16) * 100 + ((addr >> 12) % 16) * 1000 +
1494 ((addr >> 16) % 16) * 10000;
1495 /* sx_slock(&allproc_lock); */
1496 FOREACH_PROC_IN_SYSTEM(p) {
1497 if (p->p_pid == pid)
1498 break;
1499 }
1500 /* sx_sunlock(&allproc_lock); */
1501 if (p == NULL) {
1502 db_printf("pid %d not found\n", pid);
1503 return;
1504 }
1505 FOREACH_THREAD_IN_PROC(p, td) {
1506 witness_list(td);
1507 }
1508 } else {
1509 td = curthread;
1510 witness_list(td);
1511 }
1512}
1513
1514DB_SHOW_COMMAND(witness, db_witness_display)
1515{
1516
1517 witness_display(db_printf);
1518}
1519#endif
|