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.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * 3. Berkeley Software Design Inc's name may not be used to endorse or
13 * promote products derived from this software without specific prior
14 * written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
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 76772 2001-05-17 22:44:56Z 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
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 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, ...));
142static struct lock_instance *find_instance(struct lock_list_entry *lock_list,
143 struct lock_object *lock);
144
145MALLOC_DEFINE(M_WITNESS, "witness", "witness structure");
146
147static int witness_watch;
148TUNABLE_INT_DECL("debug.witness_watch", 1, witness_watch);
149SYSCTL_INT(_debug, OID_AUTO, witness_watch, CTLFLAG_RD, &witness_watch, 0, "");
150
151#ifdef DDB
152/*
153 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to
154 * drop into kdebug() when:
155 * - a lock heirarchy violation occurs
156 * - locks are held when going to sleep.
157 */
158int witness_ddb;
159#ifdef WITNESS_DDB
160TUNABLE_INT_DECL("debug.witness_ddb", 1, witness_ddb);
161#else
162TUNABLE_INT_DECL("debug.witness_ddb", 0, witness_ddb);
163#endif
164SYSCTL_INT(_debug, OID_AUTO, witness_ddb, CTLFLAG_RW, &witness_ddb, 0, "");
165#endif /* DDB */
166
167int witness_skipspin;
168#ifdef WITNESS_SKIPSPIN
169TUNABLE_INT_DECL("debug.witness_skipspin", 1, witness_skipspin);
170#else
171TUNABLE_INT_DECL("debug.witness_skipspin", 0, witness_skipspin);
172#endif
173SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0,
174 "");
175
176static struct mtx w_mtx;
177static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free);
178static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all);
179static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin);
180static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep);
181static struct witness_child_list_entry *w_child_free = NULL;
182static struct lock_list_entry *w_lock_list_free = NULL;
183static int witness_dead; /* fatal error, probably no memory */
184
185static struct witness w_data[WITNESS_COUNT];
186static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT];
187static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
188
189static struct witness_order_list_entry order_lists[] = {
190 { "Giant", &lock_class_mtx_sleep },
191 { "proctree", &lock_class_sx },
192 { "allproc", &lock_class_sx },
193 { "process lock", &lock_class_mtx_sleep },
194 { "uidinfo hash", &lock_class_mtx_sleep },
195 { "uidinfo struct", &lock_class_mtx_sleep },
196 { NULL, NULL },
197 /*
198 * spin locks
199 */
200#if defined(__i386__) && defined (SMP)
201 { "com", &lock_class_mtx_spin },
202#endif
203 { "sio", &lock_class_mtx_spin },
204#ifdef __i386__
205 { "cy", &lock_class_mtx_spin },
206#endif
207 { "ng_node", &lock_class_mtx_spin },
208 { "ng_worklist", &lock_class_mtx_spin },
209 { "ithread table lock", &lock_class_mtx_spin },
210 { "sched lock", &lock_class_mtx_spin },
211 { "clk", &lock_class_mtx_spin },
212 { "callout", &lock_class_mtx_spin },
213 /*
214 * leaf locks
215 */
216#ifdef SMP
217 { "ap boot", &lock_class_mtx_spin },
218#ifdef __i386__
219 { "imen", &lock_class_mtx_spin },
220#endif
221 { "smp rendezvous", &lock_class_mtx_spin },
222#endif
223 { NULL, NULL },
224 { NULL, NULL }
225};
226
227static const char *dup_list[] = {
228 "process lock",
229 NULL
230};
231
232/*
233 * Pairs of locks which have been blessed
234 * Don't complain about order problems with blessed locks
235 */
236static struct witness_blessed blessed_list[] = {
237};
238static int blessed_count =
239 sizeof(blessed_list) / sizeof(struct witness_blessed);
240
241/*
242 * List of all locks in the system.
243 */
244STAILQ_HEAD(, lock_object) all_locks = STAILQ_HEAD_INITIALIZER(all_locks);
245
246static struct mtx all_mtx = {
247 { &lock_class_mtx_sleep, /* mtx_object.lo_class */
248 "All locks list", /* mtx_object.lo_name */
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 if (w == NULL)
300 continue;
301 w->w_file = "order list";
302 for (order++; order->w_name != NULL; order++) {
303 w1 = enroll(order->w_name, order->w_class);
304 if (w1 == NULL)
305 continue;
306 w1->w_file = "order list";
307 itismychild(w, w1);
308 w = w1;
309 }
310 }
311
312 /* Iterate through all locks and add them to witness. */
313 mtx_lock(&all_mtx);
314 STAILQ_FOREACH(lock, &all_locks, lo_list) {
315 if (lock->lo_flags & LO_WITNESS)
316 lock->lo_witness = enroll(lock->lo_name,
317 lock->lo_class);
318 else
319 lock->lo_witness = NULL;
320 }
321 mtx_unlock(&all_mtx);
322
323 /* Mark the witness code as being ready for use. */
324 atomic_store_rel_int(&witness_cold, 0);
325
326 mtx_lock(&Giant);
327}
328SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize, NULL)
329
330void
331witness_init(struct lock_object *lock)
332{
333 struct lock_class *class;
334
335 class = lock->lo_class;
336 if (lock->lo_flags & LO_INITIALIZED)
337 panic("%s: lock (%s) %s is already initialized!\n", __func__,
338 class->lc_name, lock->lo_name);
339
340 if ((lock->lo_flags & LO_RECURSABLE) != 0 &&
341 (class->lc_flags & LC_RECURSABLE) == 0)
342 panic("%s: lock (%s) %s can not be recursable!\n", __func__,
343 class->lc_name, lock->lo_name);
344
345 if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
346 (class->lc_flags & LC_SLEEPABLE) == 0)
347 panic("%s: lock (%s) %s can not be sleepable!\n", __func__,
348 class->lc_name, lock->lo_name);
349
350 mtx_lock(&all_mtx);
351 STAILQ_INSERT_TAIL(&all_locks, lock, lo_list);
352 lock->lo_flags |= LO_INITIALIZED;
353 lock_cur_cnt++;
354 if (lock_cur_cnt > lock_max_cnt)
355 lock_max_cnt = lock_cur_cnt;
356 mtx_unlock(&all_mtx);
357 if (!witness_cold && !witness_dead &&
358 (lock->lo_flags & LO_WITNESS) != 0)
359 lock->lo_witness = enroll(lock->lo_name, class);
360 else
361 lock->lo_witness = NULL;
362}
363
364void
365witness_destroy(struct lock_object *lock)
366{
367 struct witness *w;
368
369 if (witness_cold)
370 panic("lock (%s) %s destroyed while witness_cold",
371 lock->lo_class->lc_name, lock->lo_name);
372
373 if ((lock->lo_flags & LO_INITIALIZED) == 0)
374 panic("%s: lock (%s) %s is not initialized!\n", __func__,
375 lock->lo_class->lc_name, lock->lo_name);
376
377 /* XXX: need to verify that no one holds the lock */
378 w = lock->lo_witness;
379 if (w != NULL) {
380 mtx_lock_spin(&w_mtx);
381 w->w_refcount--;
382 if (w->w_refcount == 0) {
383 w->w_name = "(dead)";
384 w->w_file = "(dead)";
385 w->w_line = 0;
386 }
387 mtx_unlock_spin(&w_mtx);
388 }
389
390 mtx_lock(&all_mtx);
391 lock_cur_cnt--;
392 STAILQ_REMOVE(&all_locks, lock, lock_object, lo_list);
393 lock->lo_flags &= LO_INITIALIZED;
394 mtx_unlock(&all_mtx);
395}
396
397static void
398witness_display_list(void(*prnt)(const char *fmt, ...),
399 struct witness_list *list)
400{
401 struct witness *w, *w1;
402 int found;
403
404 STAILQ_FOREACH(w, list, w_typelist) {
405 if (w->w_file == NULL)
406 continue;
407 found = 0;
408 STAILQ_FOREACH(w1, list, w_typelist) {
409 if (isitmychild(w1, w)) {
410 found++;
411 break;
412 }
413 }
414 if (found)
415 continue;
416 /*
417 * This lock has no anscestors, display its descendants.
418 */
419 witness_displaydescendants(prnt, w);
420 }
421}
422
423static void
424witness_display(void(*prnt)(const char *fmt, ...))
425{
426 struct witness *w;
427
428 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
429 witness_levelall();
430
431 /*
432 * First, handle sleep locks which have been acquired at least
433 * once.
434 */
435 prnt("Sleep locks:\n");
436 witness_display_list(prnt, &w_sleep);
437
438 /*
439 * Now do spin locks which have been acquired at least once.
440 */
441 prnt("\nSpin locks:\n");
442 witness_display_list(prnt, &w_spin);
443
444 /*
445 * Finally, any locks which have not been acquired yet.
446 */
447 prnt("\nLocks which were never acquired:\n");
448 STAILQ_FOREACH(w, &w_all, w_list) {
449 if (w->w_file != NULL)
450 continue;
451 prnt("%s\n", w->w_name);
452 }
453}
454
455void
456witness_lock(struct lock_object *lock, int flags, const char *file, int line)
457{
458 struct lock_list_entry **lock_list, *lle;
459 struct lock_instance *lock1, *lock2;
460 struct lock_class *class;
461 struct witness *w, *w1;
462 struct proc *p;
463 int i, j;
464#ifdef DDB
465 int go_into_ddb = 0;
466#endif /* DDB */
467
468 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
469 panicstr)
470 return;
471 w = lock->lo_witness;
472 class = lock->lo_class;
473 p = curproc;
474
475 /*
476 * We have to hold a spinlock to keep lock_list valid across the check
477 * in the LC_SLEEPLOCK case. In the LC_SPINLOCK case, it is already
478 * protected by the spinlock we are currently performing the witness
479 * checks on, so it is ok to release the lock after performing this
480 * check. All we have to protect is the LC_SLEEPLOCK case when no
481 * spinlocks are held as we may get preempted during this check and
482 * lock_list could end up pointing to some other CPU's spinlock list.
483 */
484 mtx_lock_spin(&w_mtx);
485 lock_list = PCPU_PTR(spinlocks);
486 if (class->lc_flags & LC_SLEEPLOCK) {
487 if (*lock_list != NULL && (flags & LOP_TRYLOCK) == 0) {
488 mtx_unlock_spin(&w_mtx);
489 panic("blockable sleep lock (%s) %s @ %s:%d",
490 class->lc_name, lock->lo_name, file, line);
491 }
492 lock_list = &p->p_sleeplocks;
493 }
494 mtx_unlock_spin(&w_mtx);
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 lock1->li_file = file;
542 lock1->li_line = line;
543 return;
544 }
545
546 /*
547 * Check for duplicate locks of the same type. Note that we only
548 * have to check for this on the last lock we just acquired. Any
549 * other cases will be caught as lock order violations.
550 */
551 lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
552 w1 = lock1->li_lock->lo_witness;
553 if (w1 == w) {
554 if (w->w_same_squawked || dup_ok(w))
555 goto out;
556 w->w_same_squawked = 1;
557 printf("acquiring duplicate lock of same type: \"%s\"\n",
558 lock->lo_name);
559 printf(" 1st @ %s:%d\n", lock1->li_file, lock1->li_line);
560 printf(" 2nd @ %s:%d\n", file, line);
561#ifdef DDB
562 go_into_ddb = 1;
563#endif /* DDB */
564 goto out;
565 }
566 MPASS(!mtx_owned(&w_mtx));
567 mtx_lock_spin(&w_mtx);
568 /*
569 * If we have a known higher number just say ok
570 */
571 if (witness_watch > 1 && w->w_level > w1->w_level) {
572 mtx_unlock_spin(&w_mtx);
573 goto out;
574 }
575 if (isitmydescendant(w1, w)) {
576 mtx_unlock_spin(&w_mtx);
577 goto out;
578 }
579 for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) {
580 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
581
582 MPASS(j < WITNESS_COUNT);
583 lock1 = &lle->ll_children[i];
584 w1 = lock1->li_lock->lo_witness;
585
586 /*
587 * If this lock doesn't undergo witness checking,
588 * then skip it.
589 */
590 if (w1 == NULL) {
591 KASSERT((lock1->li_lock->lo_flags & LO_WITNESS) == 0,
592 ("lock missing witness structure"));
593 continue;
594 }
595 /*
596 * If we are locking Giant and we slept with this
597 * lock, then skip it.
598 */
599 if ((lock1->li_flags & LI_SLEPT) != 0 &&
600 lock == &Giant.mtx_object)
601 continue;
602 if (!isitmydescendant(w, w1))
603 continue;
604 /*
605 * We have a lock order violation, check to see if it
606 * is allowed or has already been yelled about.
607 */
608 mtx_unlock_spin(&w_mtx);
609 if (blessed(w, w1))
610 goto out;
611 if (lock1->li_lock == &Giant.mtx_object) {
612 if (w1->w_Giant_squawked)
613 goto out;
614 else
615 w1->w_Giant_squawked = 1;
616 } else {
617 if (w1->w_other_squawked)
618 goto out;
619 else
620 w1->w_other_squawked = 1;
621 }
622 /*
623 * Ok, yell about it.
624 */
625 printf("lock order reversal\n");
626 /*
627 * Try to locate an earlier lock with
628 * witness w in our list.
629 */
630 do {
631 lock2 = &lle->ll_children[i];
632 MPASS(lock2->li_lock != NULL);
633 if (lock2->li_lock->lo_witness == w)
634 break;
635 i--;
636 if (i == 0 && lle->ll_next != NULL) {
637 lle = lle->ll_next;
638 i = lle->ll_count - 1;
639 MPASS(i != 0);
640 }
641 } while (i >= 0);
642 if (i < 0) {
643 printf(" 1st %p %s @ %s:%d\n", lock1->li_lock,
644 lock1->li_lock->lo_name, lock1->li_file,
645 lock1->li_line);
646 printf(" 2nd %p %s @ %s:%d\n", lock,
647 lock->lo_name, file, line);
648 } else {
649 printf(" 1st %p %s @ %s:%d\n", lock2->li_lock,
650 lock2->li_lock->lo_name, lock2->li_file,
651 lock2->li_line);
652 printf(" 2nd %p %s @ %s:%d\n", lock1->li_lock,
653 lock1->li_lock->lo_name, lock1->li_file,
654 lock1->li_line);
655 printf(" 3rd %p %s @ %s:%d\n", lock,
656 lock->lo_name, file, line);
657 }
658#ifdef DDB
659 go_into_ddb = 1;
660#endif /* DDB */
661 goto out;
662 }
663 }
664 lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
665 if (!itismychild(lock1->li_lock->lo_witness, w))
666 mtx_unlock_spin(&w_mtx);
667
668out:
669#ifdef DDB
670 if (witness_ddb && go_into_ddb)
671 Debugger(__func__);
672#endif /* DDB */
673 w->w_file = file;
674 w->w_line = line;
675
676 lle = *lock_list;
677 if (lle == NULL || lle->ll_count == LOCK_NCHILDREN) {
678 *lock_list = witness_lock_list_get();
679 if (*lock_list == NULL)
680 return;
681 (*lock_list)->ll_next = lle;
682 lle = *lock_list;
683 }
684 lock1 = &lle->ll_children[lle->ll_count++];
685 lock1->li_lock = lock;
686 lock1->li_line = line;
687 lock1->li_file = file;
688 if ((flags & LOP_EXCLUSIVE) != 0)
689 lock1->li_flags = LI_EXCLUSIVE;
690 else
691 lock1->li_flags = 0;
692}
693
694void
695witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
696{
697 struct lock_list_entry **lock_list, *lle;
698 struct lock_instance *instance;
699 struct lock_class *class;
700 struct proc *p;
701 int i, j;
702
703 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
704 panicstr)
705 return;
706 p = curproc;
707 class = lock->lo_class;
708 if (class->lc_flags & LC_SLEEPLOCK)
709 lock_list = &p->p_sleeplocks;
710 else
711 lock_list = PCPU_PTR(spinlocks);
712 for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
713 for (i = 0; i < (*lock_list)->ll_count; i++) {
714 instance = &(*lock_list)->ll_children[i];
715 if (instance->li_lock == lock) {
716 if ((instance->li_flags & LI_EXCLUSIVE) != 0 &&
717 (flags & LOP_EXCLUSIVE) == 0) {
718 printf(
719 "shared unlock of (%s) %s @ %s:%d\n",
720 class->lc_name, lock->lo_name,
721 file, line);
722 printf(
723 "while exclusively locked from %s:%d\n",
724 instance->li_file,
725 instance->li_line);
726 panic("excl->ushare");
727 }
728 if ((instance->li_flags & LI_EXCLUSIVE) == 0 &&
729 (flags & LOP_EXCLUSIVE) != 0) {
730 printf(
731 "exclusive unlock of (%s) %s @ %s:%d\n",
732 class->lc_name, lock->lo_name,
733 file, line);
734 printf(
735 "while share locked from %s:%d\n",
736 instance->li_file,
737 instance->li_line);
738 panic("share->uexcl");
739 }
740 /* If we are recursed, unrecurse. */
741 if ((instance->li_flags & LI_RECURSEMASK) > 0) {
742 instance->li_flags--;
743 goto out;
744 }
745 (*lock_list)->ll_count--;
746 for (j = i; j < (*lock_list)->ll_count; j++)
747 (*lock_list)->ll_children[j] =
748 (*lock_list)->ll_children[j + 1];
749 if ((*lock_list)->ll_count == 0) {
750 lle = *lock_list;
751 *lock_list = lle->ll_next;
752 witness_lock_list_free(lle);
753 }
754 goto out;
755 }
756 }
757 panic("lock (%s) %s not locked @ %s:%d", class->lc_name, lock->lo_name,
758 file, line);
759out:
760 /*
761 * We don't need to protect this PCPU_GET() here against preemption
762 * because if we hold any spinlocks then we are already protected,
763 * and if we don't we will get NULL if we hold no spinlocks even if
764 * we switch CPU's while reading it.
765 */
766 if (class->lc_flags & LC_SLEEPLOCK) {
767 if ((flags & LOP_NOSWITCH) == 0 && PCPU_GET(spinlocks) != NULL)
768 panic("switchable sleep unlock (%s) %s @ %s:%d",
769 class->lc_name, lock->lo_name, file, line);
770 }
771}
772
773/*
774 * Warn if any held locks are not sleepable. Note that Giant and the lock
775 * passed in are both special cases since they are both released during the
776 * sleep process and aren't actually held while the process is asleep.
777 */
778int
779witness_sleep(int check_only, struct lock_object *lock, const char *file,
780 int line)
781{
782 struct lock_list_entry **lock_list, *lle;
783 struct lock_instance *lock1;
784 struct proc *p;
785 critical_t savecrit;
786 int i, n;
787
788 if (witness_dead || panicstr)
789 return (0);
790 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
791 n = 0;
792 /*
793 * Preemption bad because we need PCPU_PTR(spinlocks) to not change.
794 */
795 savecrit = critical_enter();
796 p = curproc;
797 lock_list = &p->p_sleeplocks;
798again:
799 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
800 for (i = lle->ll_count - 1; i >= 0; i--) {
801 lock1 = &lle->ll_children[i];
802 if (lock1->li_lock == lock ||
803 lock1->li_lock == &Giant.mtx_object)
804 continue;
805 if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0) {
806 if (check_only == 0)
807 lock1->li_flags |= LI_SLEPT;
808 continue;
809 }
810 n++;
811 printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
812 file, line, check_only ? "could sleep" : "sleeping",
813 lock1->li_lock->lo_name, lock1->li_file,
814 lock1->li_line);
815 }
816 if (lock_list == &p->p_sleeplocks) {
817 lock_list = PCPU_PTR(spinlocks);
818 goto again;
819 }
820#ifdef DDB
821 if (witness_ddb && n)
822 Debugger(__func__);
823#endif /* DDB */
824 critical_exit(savecrit);
825 return (n);
826}
827
828static struct witness *
829enroll(const char *description, struct lock_class *lock_class)
830{
831 struct witness *w;
832
833 if (!witness_watch || witness_dead)
834 return (NULL);
835
836 if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin)
837 return (NULL);
838 mtx_lock_spin(&w_mtx);
839 STAILQ_FOREACH(w, &w_all, w_list) {
840 if (strcmp(description, w->w_name) == 0) {
841 w->w_refcount++;
842 mtx_unlock_spin(&w_mtx);
843 if (lock_class != w->w_class)
844 panic(
845 "lock (%s) %s does not match earlier (%s) lock",
846 description, lock_class->lc_name,
847 w->w_class->lc_name);
848 return (w);
849 }
850 }
851 /*
852 * This isn't quite right, as witness_cold is still 0 while we
853 * enroll all the locks initialized before witness_initialize().
854 */
855 if ((lock_class->lc_flags & LC_SPINLOCK) && !witness_cold) {
856 mtx_unlock_spin(&w_mtx);
857 panic("spin lock %s not in order list", description);
858 }
859 if ((w = witness_get()) == NULL)
860 return (NULL);
861 w->w_name = description;
862 w->w_class = lock_class;
863 w->w_refcount = 1;
864 STAILQ_INSERT_HEAD(&w_all, w, w_list);
865 if (lock_class->lc_flags & LC_SPINLOCK)
866 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
867 else if (lock_class->lc_flags & LC_SLEEPLOCK)
868 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
869 else {
870 mtx_unlock_spin(&w_mtx);
871 panic("lock class %s is not sleep or spin",
872 lock_class->lc_name);
873 }
874 mtx_unlock_spin(&w_mtx);
875
876 return (w);
877}
878
879static int
880itismychild(struct witness *parent, struct witness *child)
881{
882 static int recursed;
883 struct witness_child_list_entry **wcl;
884 struct witness_list *list;
885
886 MPASS(child != NULL && parent != NULL);
887 if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
888 (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
889 panic(
890 "%s: parent (%s) and child (%s) are not the same lock type",
891 __func__, parent->w_class->lc_name,
892 child->w_class->lc_name);
893
894 /*
895 * Insert "child" after "parent"
896 */
897 wcl = &parent->w_children;
898 while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN)
899 wcl = &(*wcl)->wcl_next;
900
901 if (*wcl == NULL) {
902 *wcl = witness_child_get();
903 if (*wcl == NULL)
904 return (1);
905 }
906
907 (*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
908
909 /*
910 * Now prune whole tree. We look for cases where a lock is now
911 * both a descendant and a direct child of a given lock. In that
912 * case, we want to remove the direct child link from the tree.
913 */
914 if (recursed)
915 return (0);
916 recursed = 1;
917 if (parent->w_class->lc_flags & LC_SLEEPLOCK)
918 list = &w_sleep;
919 else
920 list = &w_spin;
921 STAILQ_FOREACH(child, list, w_typelist) {
922 STAILQ_FOREACH(parent, list, w_typelist) {
923 if (!isitmychild(parent, child))
924 continue;
925 removechild(parent, child);
926 if (isitmydescendant(parent, child))
927 continue;
928 itismychild(parent, child);
929 }
930 }
931 recursed = 0;
932 witness_levelall();
933 return (0);
934}
935
936static void
937removechild(struct witness *parent, struct witness *child)
938{
939 struct witness_child_list_entry **wcl, *wcl1;
940 int i;
941
942 for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next)
943 for (i = 0; i < (*wcl)->wcl_count; i++)
944 if ((*wcl)->wcl_children[i] == child)
945 goto found;
946 return;
947found:
948 (*wcl)->wcl_count--;
949 if ((*wcl)->wcl_count > i)
950 (*wcl)->wcl_children[i] =
951 (*wcl)->wcl_children[(*wcl)->wcl_count];
952 MPASS((*wcl)->wcl_children[i] != NULL);
953
954 if ((*wcl)->wcl_count != 0)
955 return;
956
957 wcl1 = *wcl;
958 *wcl = wcl1->wcl_next;
959 witness_child_free(wcl1);
960}
961
962static int
963isitmychild(struct witness *parent, struct witness *child)
964{
965 struct witness_child_list_entry *wcl;
966 int i;
967
968 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
969 for (i = 0; i < wcl->wcl_count; i++) {
970 if (wcl->wcl_children[i] == child)
971 return (1);
972 }
973 }
974 return (0);
975}
976
977static int
978isitmydescendant(struct witness *parent, struct witness *child)
979{
980 struct witness_child_list_entry *wcl;
981 int i, j;
982
983 if (isitmychild(parent, child))
984 return (1);
985 j = 0;
986 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
987 MPASS(j < 1000);
988 for (i = 0; i < wcl->wcl_count; i++) {
989 if (isitmydescendant(wcl->wcl_children[i], child))
990 return (1);
991 }
992 j++;
993 }
994 return (0);
995}
996
997void
998witness_levelall (void)
999{
1000 struct witness_list *list;
1001 struct witness *w, *w1;
1002
1003 /*
1004 * First clear all levels.
1005 */
1006 STAILQ_FOREACH(w, &w_all, w_list) {
1007 w->w_level = 0;
1008 }
1009
1010 /*
1011 * Look for locks with no parent and level all their descendants.
1012 */
1013 STAILQ_FOREACH(w, &w_all, w_list) {
1014 /*
1015 * This is just an optimization, technically we could get
1016 * away just walking the all list each time.
1017 */
1018 if (w->w_class->lc_flags & LC_SLEEPLOCK)
1019 list = &w_sleep;
1020 else
1021 list = &w_spin;
1022 STAILQ_FOREACH(w1, list, w_typelist) {
1023 if (isitmychild(w1, w))
1024 goto skip;
1025 }
1026 witness_leveldescendents(w, 0);
1027 skip:
1028 }
1029}
1030
1031static void
1032witness_leveldescendents(struct witness *parent, int level)
1033{
1034 struct witness_child_list_entry *wcl;
1035 int i;
1036
1037 if (parent->w_level < level)
1038 parent->w_level = level;
1039 level++;
1040 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
1041 for (i = 0; i < wcl->wcl_count; i++)
1042 witness_leveldescendents(wcl->wcl_children[i], level);
1043}
1044
1045static void
1046witness_displaydescendants(void(*prnt)(const char *fmt, ...),
1047 struct witness *parent)
1048{
1049 struct witness_child_list_entry *wcl;
1050 int i, level;
1051
1052 level = parent->w_level;
1053
1054 prnt("%-2d", level);
1055 for (i = 0; i < level; i++)
1056 prnt(" ");
1057 prnt("%s", parent->w_name);
1058 if (parent->w_file != NULL)
1059 prnt(" -- last acquired @ %s:%d\n", parent->w_file,
1060 parent->w_line);
1061
1062 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
1063 for (i = 0; i < wcl->wcl_count; i++)
1064 witness_displaydescendants(prnt,
1065 wcl->wcl_children[i]);
1066}
1067
1068static int
1069dup_ok(struct witness *w)
1070{
1071 const char **dup;
1072
1073 for (dup = dup_list; *dup != NULL; dup++)
1074 if (strcmp(w->w_name, *dup) == 0)
1075 return (1);
1076 return (0);
1077}
1078
1079static int
1080blessed(struct witness *w1, struct witness *w2)
1081{
1082 int i;
1083 struct witness_blessed *b;
1084
1085 for (i = 0; i < blessed_count; i++) {
1086 b = &blessed_list[i];
1087 if (strcmp(w1->w_name, b->b_lock1) == 0) {
1088 if (strcmp(w2->w_name, b->b_lock2) == 0)
1089 return (1);
1090 continue;
1091 }
1092 if (strcmp(w1->w_name, b->b_lock2) == 0)
1093 if (strcmp(w2->w_name, b->b_lock1) == 0)
1094 return (1);
1095 }
1096 return (0);
1097}
1098
1099static struct witness *
1100witness_get(void)
1101{
1102 struct witness *w;
1103
1104 if (witness_dead) {
1105 mtx_unlock_spin(&w_mtx);
1106 return (NULL);
1107 }
1108 if (STAILQ_EMPTY(&w_free)) {
1109 witness_dead = 1;
1110 mtx_unlock_spin(&w_mtx);
1111 printf("%s: witness exhausted\n", __func__);
1112 return (NULL);
1113 }
1114 w = STAILQ_FIRST(&w_free);
1115 STAILQ_REMOVE_HEAD(&w_free, w_list);
1116 bzero(w, sizeof(*w));
1117 return (w);
1118}
1119
1120static void
1121witness_free(struct witness *w)
1122{
1123
1124 STAILQ_INSERT_HEAD(&w_free, w, w_list);
1125}
1126
1127static struct witness_child_list_entry *
1128witness_child_get(void)
1129{
1130 struct witness_child_list_entry *wcl;
1131
1132 if (witness_dead) {
1133 mtx_unlock_spin(&w_mtx);
1134 return (NULL);
1135 }
1136 wcl = w_child_free;
1137 if (wcl == NULL) {
1138 witness_dead = 1;
1139 mtx_unlock_spin(&w_mtx);
1140 printf("%s: witness exhausted\n", __func__);
1141 return (NULL);
1142 }
1143 w_child_free = wcl->wcl_next;
1144 bzero(wcl, sizeof(*wcl));
1145 return (wcl);
1146}
1147
1148static void
1149witness_child_free(struct witness_child_list_entry *wcl)
1150{
1151
1152 wcl->wcl_next = w_child_free;
1153 w_child_free = wcl;
1154}
1155
1156static struct lock_list_entry *
1157witness_lock_list_get(void)
1158{
1159 struct lock_list_entry *lle;
1160
1161 if (witness_dead)
1162 return (NULL);
1163 mtx_lock_spin(&w_mtx);
1164 lle = w_lock_list_free;
1165 if (lle == NULL) {
1166 witness_dead = 1;
1167 mtx_unlock_spin(&w_mtx);
1168 printf("%s: witness exhausted\n", __func__);
1169 return (NULL);
1170 }
1171 w_lock_list_free = lle->ll_next;
1172 mtx_unlock_spin(&w_mtx);
1173 bzero(lle, sizeof(*lle));
1174 return (lle);
1175}
1176
1177static void
1178witness_lock_list_free(struct lock_list_entry *lle)
1179{
1180
1181 mtx_lock_spin(&w_mtx);
1182 lle->ll_next = w_lock_list_free;
1183 w_lock_list_free = lle;
1184 mtx_unlock_spin(&w_mtx);
1185}
1186
1187static struct lock_instance *
1188find_instance(struct lock_list_entry *lock_list, struct lock_object *lock)
1189{
1190 struct lock_list_entry *lle;
1191 struct lock_instance *instance;
1192 int i;
1193
1194 for (lle = lock_list; lle != NULL; lle = lle->ll_next)
1195 for (i = lle->ll_count - 1; i >= 0; i--) {
1196 instance = &lle->ll_children[i];
1197 if (instance->li_lock == lock)
1198 return (instance);
1199 }
1200 return (NULL);
1201}
1202
1203int
1204witness_list_locks(struct lock_list_entry **lock_list)
1205{
1206 struct lock_list_entry *lle;
1207 struct lock_instance *instance;
1208 struct lock_object *lock;
1209 int i, nheld;
1210
1211 nheld = 0;
1212 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
1213 for (i = lle->ll_count - 1; i >= 0; i--) {
1214 instance = &lle->ll_children[i];
1215 lock = instance->li_lock;
1216 printf("%s (%s) %s (%p) locked @ %s:%d\n",
1217 (instance->li_flags & LI_EXCLUSIVE) != 0 ?
1218 "exclusive" : "shared",
1219 lock->lo_class->lc_name, lock->lo_name, lock,
1220 instance->li_file, instance->li_line);
1221 nheld++;
1222 }
1223 return (nheld);
1224}
1225
1226/*
1227 * Calling this on p != curproc is bad unless we are in ddb.
1228 */
1229int
1230witness_list(struct proc *p)
1231{
1232 critical_t savecrit;
1233 int nheld;
1234
1235 KASSERT(p == curproc || db_active,
1236 ("%s: p != curproc and we aren't in the debugger", __func__));
1237 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1238
1239 if (!db_active && witness_dead)
1240 return (0);
1241
1242 nheld = witness_list_locks(&p->p_sleeplocks);
1243
1244 /*
1245 * We only handle spinlocks if p == curproc. This is somewhat broken
1246 * if p is currently executing on some other CPU and holds spin locks
1247 * as we won't display those locks. If we had a MI way of getting
1248 * the per-cpu data for a given cpu then we could use p->p_oncpu to
1249 * get the list of spinlocks for this process and "fix" this.
1250 */
1251 if (p == curproc) {
1252 /*
1253 * Preemption bad because we need PCPU_PTR(spinlocks) to not
1254 * change.
1255 */
1256 savecrit = critical_enter();
1257 nheld += witness_list_locks(PCPU_PTR(spinlocks));
1258 critical_exit(savecrit);
1259 }
1260
1261 return (nheld);
1262}
1263
1264void
1265witness_save(struct lock_object *lock, const char **filep, int *linep)
1266{
1267 struct lock_instance *instance;
1268
1269 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
1270 if (lock->lo_witness == NULL || witness_dead)
1271 return;
1272
1273 KASSERT(lock->lo_class->lc_flags & LC_SLEEPLOCK,
1274 ("%s: lock (%s) %s is not a sleep lock", __func__,
1275 lock->lo_class->lc_name, lock->lo_name));
1276 instance = find_instance(curproc->p_sleeplocks, lock);
1277 KASSERT(instance != NULL, ("%s: lock (%s) %s not locked", __func__,
1278 lock->lo_class->lc_name, lock->lo_name));
1279
1280 *filep = instance->li_file;
1281 *linep = instance->li_line;
1282}
1283
1284void
1285witness_restore(struct lock_object *lock, const char *file, int line)
1286{
1287 struct lock_instance *instance;
1288
1289 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
1290 if (lock->lo_witness == NULL || witness_dead)
1291 return;
1292
1293 KASSERT(lock->lo_class->lc_flags & LC_SLEEPLOCK,
1294 ("%s: lock (%s) %s is not a sleep lock", __func__,
1295 lock->lo_class->lc_name, lock->lo_name));
1296 instance = find_instance(curproc->p_sleeplocks, lock);
1297 KASSERT(instance != NULL, ("%s: lock (%s) %s not locked", __func__,
1298 lock->lo_class->lc_name, lock->lo_name));
1299
1300 lock->lo_witness->w_file = file;
1301 lock->lo_witness->w_line = line;
1302 instance->li_file = file;
1303 instance->li_line = line;
1304}
1305
1306#ifdef DDB
1307
1308DB_SHOW_COMMAND(locks, db_witness_list)
1309{
1310 struct proc *p;
1311 pid_t pid;
1312
1313 if (have_addr) {
1314 pid = (addr % 16) + ((addr >> 4) % 16) * 10 +
1315 ((addr >> 8) % 16) * 100 + ((addr >> 12) % 16) * 1000 +
1316 ((addr >> 16) % 16) * 10000;
1317
1318 /* sx_slock(&allproc_lock); */
1319 LIST_FOREACH(p, &allproc, p_list) {
1320 if (p->p_pid == pid)
1321 break;
1322 }
1323 /* sx_sunlock(&allproc_lock); */
1324 if (p == NULL) {
1325 db_printf("pid %d not found\n", pid);
1326 return;
1327 }
1328 } else
1329 p = curproc;
1330
1331 witness_list(p);
1332}
1333
1334DB_SHOW_COMMAND(witness, db_witness_display)
1335{
1336
1337 witness_display(db_printf);
1338}
1339#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.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * 3. Berkeley Software Design Inc's name may not be used to endorse or
13 * promote products derived from this software without specific prior
14 * written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
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 76772 2001-05-17 22:44:56Z 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
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 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, ...));
142static struct lock_instance *find_instance(struct lock_list_entry *lock_list,
143 struct lock_object *lock);
144
145MALLOC_DEFINE(M_WITNESS, "witness", "witness structure");
146
147static int witness_watch;
148TUNABLE_INT_DECL("debug.witness_watch", 1, witness_watch);
149SYSCTL_INT(_debug, OID_AUTO, witness_watch, CTLFLAG_RD, &witness_watch, 0, "");
150
151#ifdef DDB
152/*
153 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to
154 * drop into kdebug() when:
155 * - a lock heirarchy violation occurs
156 * - locks are held when going to sleep.
157 */
158int witness_ddb;
159#ifdef WITNESS_DDB
160TUNABLE_INT_DECL("debug.witness_ddb", 1, witness_ddb);
161#else
162TUNABLE_INT_DECL("debug.witness_ddb", 0, witness_ddb);
163#endif
164SYSCTL_INT(_debug, OID_AUTO, witness_ddb, CTLFLAG_RW, &witness_ddb, 0, "");
165#endif /* DDB */
166
167int witness_skipspin;
168#ifdef WITNESS_SKIPSPIN
169TUNABLE_INT_DECL("debug.witness_skipspin", 1, witness_skipspin);
170#else
171TUNABLE_INT_DECL("debug.witness_skipspin", 0, witness_skipspin);
172#endif
173SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0,
174 "");
175
176static struct mtx w_mtx;
177static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free);
178static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all);
179static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin);
180static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep);
181static struct witness_child_list_entry *w_child_free = NULL;
182static struct lock_list_entry *w_lock_list_free = NULL;
183static int witness_dead; /* fatal error, probably no memory */
184
185static struct witness w_data[WITNESS_COUNT];
186static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT];
187static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
188
189static struct witness_order_list_entry order_lists[] = {
190 { "Giant", &lock_class_mtx_sleep },
191 { "proctree", &lock_class_sx },
192 { "allproc", &lock_class_sx },
193 { "process lock", &lock_class_mtx_sleep },
194 { "uidinfo hash", &lock_class_mtx_sleep },
195 { "uidinfo struct", &lock_class_mtx_sleep },
196 { NULL, NULL },
197 /*
198 * spin locks
199 */
200#if defined(__i386__) && defined (SMP)
201 { "com", &lock_class_mtx_spin },
202#endif
203 { "sio", &lock_class_mtx_spin },
204#ifdef __i386__
205 { "cy", &lock_class_mtx_spin },
206#endif
207 { "ng_node", &lock_class_mtx_spin },
208 { "ng_worklist", &lock_class_mtx_spin },
209 { "ithread table lock", &lock_class_mtx_spin },
210 { "sched lock", &lock_class_mtx_spin },
211 { "clk", &lock_class_mtx_spin },
212 { "callout", &lock_class_mtx_spin },
213 /*
214 * leaf locks
215 */
216#ifdef SMP
217 { "ap boot", &lock_class_mtx_spin },
218#ifdef __i386__
219 { "imen", &lock_class_mtx_spin },
220#endif
221 { "smp rendezvous", &lock_class_mtx_spin },
222#endif
223 { NULL, NULL },
224 { NULL, NULL }
225};
226
227static const char *dup_list[] = {
228 "process lock",
229 NULL
230};
231
232/*
233 * Pairs of locks which have been blessed
234 * Don't complain about order problems with blessed locks
235 */
236static struct witness_blessed blessed_list[] = {
237};
238static int blessed_count =
239 sizeof(blessed_list) / sizeof(struct witness_blessed);
240
241/*
242 * List of all locks in the system.
243 */
244STAILQ_HEAD(, lock_object) all_locks = STAILQ_HEAD_INITIALIZER(all_locks);
245
246static struct mtx all_mtx = {
247 { &lock_class_mtx_sleep, /* mtx_object.lo_class */
248 "All locks list", /* mtx_object.lo_name */
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 if (w == NULL)
300 continue;
301 w->w_file = "order list";
302 for (order++; order->w_name != NULL; order++) {
303 w1 = enroll(order->w_name, order->w_class);
304 if (w1 == NULL)
305 continue;
306 w1->w_file = "order list";
307 itismychild(w, w1);
308 w = w1;
309 }
310 }
311
312 /* Iterate through all locks and add them to witness. */
313 mtx_lock(&all_mtx);
314 STAILQ_FOREACH(lock, &all_locks, lo_list) {
315 if (lock->lo_flags & LO_WITNESS)
316 lock->lo_witness = enroll(lock->lo_name,
317 lock->lo_class);
318 else
319 lock->lo_witness = NULL;
320 }
321 mtx_unlock(&all_mtx);
322
323 /* Mark the witness code as being ready for use. */
324 atomic_store_rel_int(&witness_cold, 0);
325
326 mtx_lock(&Giant);
327}
328SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize, NULL)
329
330void
331witness_init(struct lock_object *lock)
332{
333 struct lock_class *class;
334
335 class = lock->lo_class;
336 if (lock->lo_flags & LO_INITIALIZED)
337 panic("%s: lock (%s) %s is already initialized!\n", __func__,
338 class->lc_name, lock->lo_name);
339
340 if ((lock->lo_flags & LO_RECURSABLE) != 0 &&
341 (class->lc_flags & LC_RECURSABLE) == 0)
342 panic("%s: lock (%s) %s can not be recursable!\n", __func__,
343 class->lc_name, lock->lo_name);
344
345 if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
346 (class->lc_flags & LC_SLEEPABLE) == 0)
347 panic("%s: lock (%s) %s can not be sleepable!\n", __func__,
348 class->lc_name, lock->lo_name);
349
350 mtx_lock(&all_mtx);
351 STAILQ_INSERT_TAIL(&all_locks, lock, lo_list);
352 lock->lo_flags |= LO_INITIALIZED;
353 lock_cur_cnt++;
354 if (lock_cur_cnt > lock_max_cnt)
355 lock_max_cnt = lock_cur_cnt;
356 mtx_unlock(&all_mtx);
357 if (!witness_cold && !witness_dead &&
358 (lock->lo_flags & LO_WITNESS) != 0)
359 lock->lo_witness = enroll(lock->lo_name, class);
360 else
361 lock->lo_witness = NULL;
362}
363
364void
365witness_destroy(struct lock_object *lock)
366{
367 struct witness *w;
368
369 if (witness_cold)
370 panic("lock (%s) %s destroyed while witness_cold",
371 lock->lo_class->lc_name, lock->lo_name);
372
373 if ((lock->lo_flags & LO_INITIALIZED) == 0)
374 panic("%s: lock (%s) %s is not initialized!\n", __func__,
375 lock->lo_class->lc_name, lock->lo_name);
376
377 /* XXX: need to verify that no one holds the lock */
378 w = lock->lo_witness;
379 if (w != NULL) {
380 mtx_lock_spin(&w_mtx);
381 w->w_refcount--;
382 if (w->w_refcount == 0) {
383 w->w_name = "(dead)";
384 w->w_file = "(dead)";
385 w->w_line = 0;
386 }
387 mtx_unlock_spin(&w_mtx);
388 }
389
390 mtx_lock(&all_mtx);
391 lock_cur_cnt--;
392 STAILQ_REMOVE(&all_locks, lock, lock_object, lo_list);
393 lock->lo_flags &= LO_INITIALIZED;
394 mtx_unlock(&all_mtx);
395}
396
397static void
398witness_display_list(void(*prnt)(const char *fmt, ...),
399 struct witness_list *list)
400{
401 struct witness *w, *w1;
402 int found;
403
404 STAILQ_FOREACH(w, list, w_typelist) {
405 if (w->w_file == NULL)
406 continue;
407 found = 0;
408 STAILQ_FOREACH(w1, list, w_typelist) {
409 if (isitmychild(w1, w)) {
410 found++;
411 break;
412 }
413 }
414 if (found)
415 continue;
416 /*
417 * This lock has no anscestors, display its descendants.
418 */
419 witness_displaydescendants(prnt, w);
420 }
421}
422
423static void
424witness_display(void(*prnt)(const char *fmt, ...))
425{
426 struct witness *w;
427
428 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
429 witness_levelall();
430
431 /*
432 * First, handle sleep locks which have been acquired at least
433 * once.
434 */
435 prnt("Sleep locks:\n");
436 witness_display_list(prnt, &w_sleep);
437
438 /*
439 * Now do spin locks which have been acquired at least once.
440 */
441 prnt("\nSpin locks:\n");
442 witness_display_list(prnt, &w_spin);
443
444 /*
445 * Finally, any locks which have not been acquired yet.
446 */
447 prnt("\nLocks which were never acquired:\n");
448 STAILQ_FOREACH(w, &w_all, w_list) {
449 if (w->w_file != NULL)
450 continue;
451 prnt("%s\n", w->w_name);
452 }
453}
454
455void
456witness_lock(struct lock_object *lock, int flags, const char *file, int line)
457{
458 struct lock_list_entry **lock_list, *lle;
459 struct lock_instance *lock1, *lock2;
460 struct lock_class *class;
461 struct witness *w, *w1;
462 struct proc *p;
463 int i, j;
464#ifdef DDB
465 int go_into_ddb = 0;
466#endif /* DDB */
467
468 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
469 panicstr)
470 return;
471 w = lock->lo_witness;
472 class = lock->lo_class;
473 p = curproc;
474
475 /*
476 * We have to hold a spinlock to keep lock_list valid across the check
477 * in the LC_SLEEPLOCK case. In the LC_SPINLOCK case, it is already
478 * protected by the spinlock we are currently performing the witness
479 * checks on, so it is ok to release the lock after performing this
480 * check. All we have to protect is the LC_SLEEPLOCK case when no
481 * spinlocks are held as we may get preempted during this check and
482 * lock_list could end up pointing to some other CPU's spinlock list.
483 */
484 mtx_lock_spin(&w_mtx);
485 lock_list = PCPU_PTR(spinlocks);
486 if (class->lc_flags & LC_SLEEPLOCK) {
487 if (*lock_list != NULL && (flags & LOP_TRYLOCK) == 0) {
488 mtx_unlock_spin(&w_mtx);
489 panic("blockable sleep lock (%s) %s @ %s:%d",
490 class->lc_name, lock->lo_name, file, line);
491 }
492 lock_list = &p->p_sleeplocks;
493 }
494 mtx_unlock_spin(&w_mtx);
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 lock1->li_file = file;
542 lock1->li_line = line;
543 return;
544 }
545
546 /*
547 * Check for duplicate locks of the same type. Note that we only
548 * have to check for this on the last lock we just acquired. Any
549 * other cases will be caught as lock order violations.
550 */
551 lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
552 w1 = lock1->li_lock->lo_witness;
553 if (w1 == w) {
554 if (w->w_same_squawked || dup_ok(w))
555 goto out;
556 w->w_same_squawked = 1;
557 printf("acquiring duplicate lock of same type: \"%s\"\n",
558 lock->lo_name);
559 printf(" 1st @ %s:%d\n", lock1->li_file, lock1->li_line);
560 printf(" 2nd @ %s:%d\n", file, line);
561#ifdef DDB
562 go_into_ddb = 1;
563#endif /* DDB */
564 goto out;
565 }
566 MPASS(!mtx_owned(&w_mtx));
567 mtx_lock_spin(&w_mtx);
568 /*
569 * If we have a known higher number just say ok
570 */
571 if (witness_watch > 1 && w->w_level > w1->w_level) {
572 mtx_unlock_spin(&w_mtx);
573 goto out;
574 }
575 if (isitmydescendant(w1, w)) {
576 mtx_unlock_spin(&w_mtx);
577 goto out;
578 }
579 for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) {
580 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
581
582 MPASS(j < WITNESS_COUNT);
583 lock1 = &lle->ll_children[i];
584 w1 = lock1->li_lock->lo_witness;
585
586 /*
587 * If this lock doesn't undergo witness checking,
588 * then skip it.
589 */
590 if (w1 == NULL) {
591 KASSERT((lock1->li_lock->lo_flags & LO_WITNESS) == 0,
592 ("lock missing witness structure"));
593 continue;
594 }
595 /*
596 * If we are locking Giant and we slept with this
597 * lock, then skip it.
598 */
599 if ((lock1->li_flags & LI_SLEPT) != 0 &&
600 lock == &Giant.mtx_object)
601 continue;
602 if (!isitmydescendant(w, w1))
603 continue;
604 /*
605 * We have a lock order violation, check to see if it
606 * is allowed or has already been yelled about.
607 */
608 mtx_unlock_spin(&w_mtx);
609 if (blessed(w, w1))
610 goto out;
611 if (lock1->li_lock == &Giant.mtx_object) {
612 if (w1->w_Giant_squawked)
613 goto out;
614 else
615 w1->w_Giant_squawked = 1;
616 } else {
617 if (w1->w_other_squawked)
618 goto out;
619 else
620 w1->w_other_squawked = 1;
621 }
622 /*
623 * Ok, yell about it.
624 */
625 printf("lock order reversal\n");
626 /*
627 * Try to locate an earlier lock with
628 * witness w in our list.
629 */
630 do {
631 lock2 = &lle->ll_children[i];
632 MPASS(lock2->li_lock != NULL);
633 if (lock2->li_lock->lo_witness == w)
634 break;
635 i--;
636 if (i == 0 && lle->ll_next != NULL) {
637 lle = lle->ll_next;
638 i = lle->ll_count - 1;
639 MPASS(i != 0);
640 }
641 } while (i >= 0);
642 if (i < 0) {
643 printf(" 1st %p %s @ %s:%d\n", lock1->li_lock,
644 lock1->li_lock->lo_name, lock1->li_file,
645 lock1->li_line);
646 printf(" 2nd %p %s @ %s:%d\n", lock,
647 lock->lo_name, file, line);
648 } else {
649 printf(" 1st %p %s @ %s:%d\n", lock2->li_lock,
650 lock2->li_lock->lo_name, lock2->li_file,
651 lock2->li_line);
652 printf(" 2nd %p %s @ %s:%d\n", lock1->li_lock,
653 lock1->li_lock->lo_name, lock1->li_file,
654 lock1->li_line);
655 printf(" 3rd %p %s @ %s:%d\n", lock,
656 lock->lo_name, file, line);
657 }
658#ifdef DDB
659 go_into_ddb = 1;
660#endif /* DDB */
661 goto out;
662 }
663 }
664 lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
665 if (!itismychild(lock1->li_lock->lo_witness, w))
666 mtx_unlock_spin(&w_mtx);
667
668out:
669#ifdef DDB
670 if (witness_ddb && go_into_ddb)
671 Debugger(__func__);
672#endif /* DDB */
673 w->w_file = file;
674 w->w_line = line;
675
676 lle = *lock_list;
677 if (lle == NULL || lle->ll_count == LOCK_NCHILDREN) {
678 *lock_list = witness_lock_list_get();
679 if (*lock_list == NULL)
680 return;
681 (*lock_list)->ll_next = lle;
682 lle = *lock_list;
683 }
684 lock1 = &lle->ll_children[lle->ll_count++];
685 lock1->li_lock = lock;
686 lock1->li_line = line;
687 lock1->li_file = file;
688 if ((flags & LOP_EXCLUSIVE) != 0)
689 lock1->li_flags = LI_EXCLUSIVE;
690 else
691 lock1->li_flags = 0;
692}
693
694void
695witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
696{
697 struct lock_list_entry **lock_list, *lle;
698 struct lock_instance *instance;
699 struct lock_class *class;
700 struct proc *p;
701 int i, j;
702
703 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
704 panicstr)
705 return;
706 p = curproc;
707 class = lock->lo_class;
708 if (class->lc_flags & LC_SLEEPLOCK)
709 lock_list = &p->p_sleeplocks;
710 else
711 lock_list = PCPU_PTR(spinlocks);
712 for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
713 for (i = 0; i < (*lock_list)->ll_count; i++) {
714 instance = &(*lock_list)->ll_children[i];
715 if (instance->li_lock == lock) {
716 if ((instance->li_flags & LI_EXCLUSIVE) != 0 &&
717 (flags & LOP_EXCLUSIVE) == 0) {
718 printf(
719 "shared unlock of (%s) %s @ %s:%d\n",
720 class->lc_name, lock->lo_name,
721 file, line);
722 printf(
723 "while exclusively locked from %s:%d\n",
724 instance->li_file,
725 instance->li_line);
726 panic("excl->ushare");
727 }
728 if ((instance->li_flags & LI_EXCLUSIVE) == 0 &&
729 (flags & LOP_EXCLUSIVE) != 0) {
730 printf(
731 "exclusive unlock of (%s) %s @ %s:%d\n",
732 class->lc_name, lock->lo_name,
733 file, line);
734 printf(
735 "while share locked from %s:%d\n",
736 instance->li_file,
737 instance->li_line);
738 panic("share->uexcl");
739 }
740 /* If we are recursed, unrecurse. */
741 if ((instance->li_flags & LI_RECURSEMASK) > 0) {
742 instance->li_flags--;
743 goto out;
744 }
745 (*lock_list)->ll_count--;
746 for (j = i; j < (*lock_list)->ll_count; j++)
747 (*lock_list)->ll_children[j] =
748 (*lock_list)->ll_children[j + 1];
749 if ((*lock_list)->ll_count == 0) {
750 lle = *lock_list;
751 *lock_list = lle->ll_next;
752 witness_lock_list_free(lle);
753 }
754 goto out;
755 }
756 }
757 panic("lock (%s) %s not locked @ %s:%d", class->lc_name, lock->lo_name,
758 file, line);
759out:
760 /*
761 * We don't need to protect this PCPU_GET() here against preemption
762 * because if we hold any spinlocks then we are already protected,
763 * and if we don't we will get NULL if we hold no spinlocks even if
764 * we switch CPU's while reading it.
765 */
766 if (class->lc_flags & LC_SLEEPLOCK) {
767 if ((flags & LOP_NOSWITCH) == 0 && PCPU_GET(spinlocks) != NULL)
768 panic("switchable sleep unlock (%s) %s @ %s:%d",
769 class->lc_name, lock->lo_name, file, line);
770 }
771}
772
773/*
774 * Warn if any held locks are not sleepable. Note that Giant and the lock
775 * passed in are both special cases since they are both released during the
776 * sleep process and aren't actually held while the process is asleep.
777 */
778int
779witness_sleep(int check_only, struct lock_object *lock, const char *file,
780 int line)
781{
782 struct lock_list_entry **lock_list, *lle;
783 struct lock_instance *lock1;
784 struct proc *p;
785 critical_t savecrit;
786 int i, n;
787
788 if (witness_dead || panicstr)
789 return (0);
790 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
791 n = 0;
792 /*
793 * Preemption bad because we need PCPU_PTR(spinlocks) to not change.
794 */
795 savecrit = critical_enter();
796 p = curproc;
797 lock_list = &p->p_sleeplocks;
798again:
799 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
800 for (i = lle->ll_count - 1; i >= 0; i--) {
801 lock1 = &lle->ll_children[i];
802 if (lock1->li_lock == lock ||
803 lock1->li_lock == &Giant.mtx_object)
804 continue;
805 if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0) {
806 if (check_only == 0)
807 lock1->li_flags |= LI_SLEPT;
808 continue;
809 }
810 n++;
811 printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
812 file, line, check_only ? "could sleep" : "sleeping",
813 lock1->li_lock->lo_name, lock1->li_file,
814 lock1->li_line);
815 }
816 if (lock_list == &p->p_sleeplocks) {
817 lock_list = PCPU_PTR(spinlocks);
818 goto again;
819 }
820#ifdef DDB
821 if (witness_ddb && n)
822 Debugger(__func__);
823#endif /* DDB */
824 critical_exit(savecrit);
825 return (n);
826}
827
828static struct witness *
829enroll(const char *description, struct lock_class *lock_class)
830{
831 struct witness *w;
832
833 if (!witness_watch || witness_dead)
834 return (NULL);
835
836 if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin)
837 return (NULL);
838 mtx_lock_spin(&w_mtx);
839 STAILQ_FOREACH(w, &w_all, w_list) {
840 if (strcmp(description, w->w_name) == 0) {
841 w->w_refcount++;
842 mtx_unlock_spin(&w_mtx);
843 if (lock_class != w->w_class)
844 panic(
845 "lock (%s) %s does not match earlier (%s) lock",
846 description, lock_class->lc_name,
847 w->w_class->lc_name);
848 return (w);
849 }
850 }
851 /*
852 * This isn't quite right, as witness_cold is still 0 while we
853 * enroll all the locks initialized before witness_initialize().
854 */
855 if ((lock_class->lc_flags & LC_SPINLOCK) && !witness_cold) {
856 mtx_unlock_spin(&w_mtx);
857 panic("spin lock %s not in order list", description);
858 }
859 if ((w = witness_get()) == NULL)
860 return (NULL);
861 w->w_name = description;
862 w->w_class = lock_class;
863 w->w_refcount = 1;
864 STAILQ_INSERT_HEAD(&w_all, w, w_list);
865 if (lock_class->lc_flags & LC_SPINLOCK)
866 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
867 else if (lock_class->lc_flags & LC_SLEEPLOCK)
868 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
869 else {
870 mtx_unlock_spin(&w_mtx);
871 panic("lock class %s is not sleep or spin",
872 lock_class->lc_name);
873 }
874 mtx_unlock_spin(&w_mtx);
875
876 return (w);
877}
878
879static int
880itismychild(struct witness *parent, struct witness *child)
881{
882 static int recursed;
883 struct witness_child_list_entry **wcl;
884 struct witness_list *list;
885
886 MPASS(child != NULL && parent != NULL);
887 if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
888 (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
889 panic(
890 "%s: parent (%s) and child (%s) are not the same lock type",
891 __func__, parent->w_class->lc_name,
892 child->w_class->lc_name);
893
894 /*
895 * Insert "child" after "parent"
896 */
897 wcl = &parent->w_children;
898 while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN)
899 wcl = &(*wcl)->wcl_next;
900
901 if (*wcl == NULL) {
902 *wcl = witness_child_get();
903 if (*wcl == NULL)
904 return (1);
905 }
906
907 (*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
908
909 /*
910 * Now prune whole tree. We look for cases where a lock is now
911 * both a descendant and a direct child of a given lock. In that
912 * case, we want to remove the direct child link from the tree.
913 */
914 if (recursed)
915 return (0);
916 recursed = 1;
917 if (parent->w_class->lc_flags & LC_SLEEPLOCK)
918 list = &w_sleep;
919 else
920 list = &w_spin;
921 STAILQ_FOREACH(child, list, w_typelist) {
922 STAILQ_FOREACH(parent, list, w_typelist) {
923 if (!isitmychild(parent, child))
924 continue;
925 removechild(parent, child);
926 if (isitmydescendant(parent, child))
927 continue;
928 itismychild(parent, child);
929 }
930 }
931 recursed = 0;
932 witness_levelall();
933 return (0);
934}
935
936static void
937removechild(struct witness *parent, struct witness *child)
938{
939 struct witness_child_list_entry **wcl, *wcl1;
940 int i;
941
942 for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next)
943 for (i = 0; i < (*wcl)->wcl_count; i++)
944 if ((*wcl)->wcl_children[i] == child)
945 goto found;
946 return;
947found:
948 (*wcl)->wcl_count--;
949 if ((*wcl)->wcl_count > i)
950 (*wcl)->wcl_children[i] =
951 (*wcl)->wcl_children[(*wcl)->wcl_count];
952 MPASS((*wcl)->wcl_children[i] != NULL);
953
954 if ((*wcl)->wcl_count != 0)
955 return;
956
957 wcl1 = *wcl;
958 *wcl = wcl1->wcl_next;
959 witness_child_free(wcl1);
960}
961
962static int
963isitmychild(struct witness *parent, struct witness *child)
964{
965 struct witness_child_list_entry *wcl;
966 int i;
967
968 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
969 for (i = 0; i < wcl->wcl_count; i++) {
970 if (wcl->wcl_children[i] == child)
971 return (1);
972 }
973 }
974 return (0);
975}
976
977static int
978isitmydescendant(struct witness *parent, struct witness *child)
979{
980 struct witness_child_list_entry *wcl;
981 int i, j;
982
983 if (isitmychild(parent, child))
984 return (1);
985 j = 0;
986 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
987 MPASS(j < 1000);
988 for (i = 0; i < wcl->wcl_count; i++) {
989 if (isitmydescendant(wcl->wcl_children[i], child))
990 return (1);
991 }
992 j++;
993 }
994 return (0);
995}
996
997void
998witness_levelall (void)
999{
1000 struct witness_list *list;
1001 struct witness *w, *w1;
1002
1003 /*
1004 * First clear all levels.
1005 */
1006 STAILQ_FOREACH(w, &w_all, w_list) {
1007 w->w_level = 0;
1008 }
1009
1010 /*
1011 * Look for locks with no parent and level all their descendants.
1012 */
1013 STAILQ_FOREACH(w, &w_all, w_list) {
1014 /*
1015 * This is just an optimization, technically we could get
1016 * away just walking the all list each time.
1017 */
1018 if (w->w_class->lc_flags & LC_SLEEPLOCK)
1019 list = &w_sleep;
1020 else
1021 list = &w_spin;
1022 STAILQ_FOREACH(w1, list, w_typelist) {
1023 if (isitmychild(w1, w))
1024 goto skip;
1025 }
1026 witness_leveldescendents(w, 0);
1027 skip:
1028 }
1029}
1030
1031static void
1032witness_leveldescendents(struct witness *parent, int level)
1033{
1034 struct witness_child_list_entry *wcl;
1035 int i;
1036
1037 if (parent->w_level < level)
1038 parent->w_level = level;
1039 level++;
1040 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
1041 for (i = 0; i < wcl->wcl_count; i++)
1042 witness_leveldescendents(wcl->wcl_children[i], level);
1043}
1044
1045static void
1046witness_displaydescendants(void(*prnt)(const char *fmt, ...),
1047 struct witness *parent)
1048{
1049 struct witness_child_list_entry *wcl;
1050 int i, level;
1051
1052 level = parent->w_level;
1053
1054 prnt("%-2d", level);
1055 for (i = 0; i < level; i++)
1056 prnt(" ");
1057 prnt("%s", parent->w_name);
1058 if (parent->w_file != NULL)
1059 prnt(" -- last acquired @ %s:%d\n", parent->w_file,
1060 parent->w_line);
1061
1062 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
1063 for (i = 0; i < wcl->wcl_count; i++)
1064 witness_displaydescendants(prnt,
1065 wcl->wcl_children[i]);
1066}
1067
1068static int
1069dup_ok(struct witness *w)
1070{
1071 const char **dup;
1072
1073 for (dup = dup_list; *dup != NULL; dup++)
1074 if (strcmp(w->w_name, *dup) == 0)
1075 return (1);
1076 return (0);
1077}
1078
1079static int
1080blessed(struct witness *w1, struct witness *w2)
1081{
1082 int i;
1083 struct witness_blessed *b;
1084
1085 for (i = 0; i < blessed_count; i++) {
1086 b = &blessed_list[i];
1087 if (strcmp(w1->w_name, b->b_lock1) == 0) {
1088 if (strcmp(w2->w_name, b->b_lock2) == 0)
1089 return (1);
1090 continue;
1091 }
1092 if (strcmp(w1->w_name, b->b_lock2) == 0)
1093 if (strcmp(w2->w_name, b->b_lock1) == 0)
1094 return (1);
1095 }
1096 return (0);
1097}
1098
1099static struct witness *
1100witness_get(void)
1101{
1102 struct witness *w;
1103
1104 if (witness_dead) {
1105 mtx_unlock_spin(&w_mtx);
1106 return (NULL);
1107 }
1108 if (STAILQ_EMPTY(&w_free)) {
1109 witness_dead = 1;
1110 mtx_unlock_spin(&w_mtx);
1111 printf("%s: witness exhausted\n", __func__);
1112 return (NULL);
1113 }
1114 w = STAILQ_FIRST(&w_free);
1115 STAILQ_REMOVE_HEAD(&w_free, w_list);
1116 bzero(w, sizeof(*w));
1117 return (w);
1118}
1119
1120static void
1121witness_free(struct witness *w)
1122{
1123
1124 STAILQ_INSERT_HEAD(&w_free, w, w_list);
1125}
1126
1127static struct witness_child_list_entry *
1128witness_child_get(void)
1129{
1130 struct witness_child_list_entry *wcl;
1131
1132 if (witness_dead) {
1133 mtx_unlock_spin(&w_mtx);
1134 return (NULL);
1135 }
1136 wcl = w_child_free;
1137 if (wcl == NULL) {
1138 witness_dead = 1;
1139 mtx_unlock_spin(&w_mtx);
1140 printf("%s: witness exhausted\n", __func__);
1141 return (NULL);
1142 }
1143 w_child_free = wcl->wcl_next;
1144 bzero(wcl, sizeof(*wcl));
1145 return (wcl);
1146}
1147
1148static void
1149witness_child_free(struct witness_child_list_entry *wcl)
1150{
1151
1152 wcl->wcl_next = w_child_free;
1153 w_child_free = wcl;
1154}
1155
1156static struct lock_list_entry *
1157witness_lock_list_get(void)
1158{
1159 struct lock_list_entry *lle;
1160
1161 if (witness_dead)
1162 return (NULL);
1163 mtx_lock_spin(&w_mtx);
1164 lle = w_lock_list_free;
1165 if (lle == NULL) {
1166 witness_dead = 1;
1167 mtx_unlock_spin(&w_mtx);
1168 printf("%s: witness exhausted\n", __func__);
1169 return (NULL);
1170 }
1171 w_lock_list_free = lle->ll_next;
1172 mtx_unlock_spin(&w_mtx);
1173 bzero(lle, sizeof(*lle));
1174 return (lle);
1175}
1176
1177static void
1178witness_lock_list_free(struct lock_list_entry *lle)
1179{
1180
1181 mtx_lock_spin(&w_mtx);
1182 lle->ll_next = w_lock_list_free;
1183 w_lock_list_free = lle;
1184 mtx_unlock_spin(&w_mtx);
1185}
1186
1187static struct lock_instance *
1188find_instance(struct lock_list_entry *lock_list, struct lock_object *lock)
1189{
1190 struct lock_list_entry *lle;
1191 struct lock_instance *instance;
1192 int i;
1193
1194 for (lle = lock_list; lle != NULL; lle = lle->ll_next)
1195 for (i = lle->ll_count - 1; i >= 0; i--) {
1196 instance = &lle->ll_children[i];
1197 if (instance->li_lock == lock)
1198 return (instance);
1199 }
1200 return (NULL);
1201}
1202
1203int
1204witness_list_locks(struct lock_list_entry **lock_list)
1205{
1206 struct lock_list_entry *lle;
1207 struct lock_instance *instance;
1208 struct lock_object *lock;
1209 int i, nheld;
1210
1211 nheld = 0;
1212 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
1213 for (i = lle->ll_count - 1; i >= 0; i--) {
1214 instance = &lle->ll_children[i];
1215 lock = instance->li_lock;
1216 printf("%s (%s) %s (%p) locked @ %s:%d\n",
1217 (instance->li_flags & LI_EXCLUSIVE) != 0 ?
1218 "exclusive" : "shared",
1219 lock->lo_class->lc_name, lock->lo_name, lock,
1220 instance->li_file, instance->li_line);
1221 nheld++;
1222 }
1223 return (nheld);
1224}
1225
1226/*
1227 * Calling this on p != curproc is bad unless we are in ddb.
1228 */
1229int
1230witness_list(struct proc *p)
1231{
1232 critical_t savecrit;
1233 int nheld;
1234
1235 KASSERT(p == curproc || db_active,
1236 ("%s: p != curproc and we aren't in the debugger", __func__));
1237 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1238
1239 if (!db_active && witness_dead)
1240 return (0);
1241
1242 nheld = witness_list_locks(&p->p_sleeplocks);
1243
1244 /*
1245 * We only handle spinlocks if p == curproc. This is somewhat broken
1246 * if p is currently executing on some other CPU and holds spin locks
1247 * as we won't display those locks. If we had a MI way of getting
1248 * the per-cpu data for a given cpu then we could use p->p_oncpu to
1249 * get the list of spinlocks for this process and "fix" this.
1250 */
1251 if (p == curproc) {
1252 /*
1253 * Preemption bad because we need PCPU_PTR(spinlocks) to not
1254 * change.
1255 */
1256 savecrit = critical_enter();
1257 nheld += witness_list_locks(PCPU_PTR(spinlocks));
1258 critical_exit(savecrit);
1259 }
1260
1261 return (nheld);
1262}
1263
1264void
1265witness_save(struct lock_object *lock, const char **filep, int *linep)
1266{
1267 struct lock_instance *instance;
1268
1269 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
1270 if (lock->lo_witness == NULL || witness_dead)
1271 return;
1272
1273 KASSERT(lock->lo_class->lc_flags & LC_SLEEPLOCK,
1274 ("%s: lock (%s) %s is not a sleep lock", __func__,
1275 lock->lo_class->lc_name, lock->lo_name));
1276 instance = find_instance(curproc->p_sleeplocks, lock);
1277 KASSERT(instance != NULL, ("%s: lock (%s) %s not locked", __func__,
1278 lock->lo_class->lc_name, lock->lo_name));
1279
1280 *filep = instance->li_file;
1281 *linep = instance->li_line;
1282}
1283
1284void
1285witness_restore(struct lock_object *lock, const char *file, int line)
1286{
1287 struct lock_instance *instance;
1288
1289 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
1290 if (lock->lo_witness == NULL || witness_dead)
1291 return;
1292
1293 KASSERT(lock->lo_class->lc_flags & LC_SLEEPLOCK,
1294 ("%s: lock (%s) %s is not a sleep lock", __func__,
1295 lock->lo_class->lc_name, lock->lo_name));
1296 instance = find_instance(curproc->p_sleeplocks, lock);
1297 KASSERT(instance != NULL, ("%s: lock (%s) %s not locked", __func__,
1298 lock->lo_class->lc_name, lock->lo_name));
1299
1300 lock->lo_witness->w_file = file;
1301 lock->lo_witness->w_line = line;
1302 instance->li_file = file;
1303 instance->li_line = line;
1304}
1305
1306#ifdef DDB
1307
1308DB_SHOW_COMMAND(locks, db_witness_list)
1309{
1310 struct proc *p;
1311 pid_t pid;
1312
1313 if (have_addr) {
1314 pid = (addr % 16) + ((addr >> 4) % 16) * 10 +
1315 ((addr >> 8) % 16) * 100 + ((addr >> 12) % 16) * 1000 +
1316 ((addr >> 16) % 16) * 10000;
1317
1318 /* sx_slock(&allproc_lock); */
1319 LIST_FOREACH(p, &allproc, p_list) {
1320 if (p->p_pid == pid)
1321 break;
1322 }
1323 /* sx_sunlock(&allproc_lock); */
1324 if (p == NULL) {
1325 db_printf("pid %d not found\n", pid);
1326 return;
1327 }
1328 } else
1329 p = curproc;
1330
1331 witness_list(p);
1332}
1333
1334DB_SHOW_COMMAND(witness, db_witness_display)
1335{
1336
1337 witness_display(db_printf);
1338}
1339#endif