Deleted Added
sdiff udiff text old ( 74900 ) new ( 74912 )
full compact
subr_witness.c (74900) subr_witness.c (74912)
1/*-
2 * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.

--- 13 unchanged lines hidden (view full) ---

22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 *
28 * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
29 * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
1/*-
2 * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.

--- 13 unchanged lines hidden (view full) ---

22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 *
28 * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
29 * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
30 * $FreeBSD: head/sys/kern/subr_witness.c 74900 2001-03-28 02:40:47Z jhb $
30 * $FreeBSD: head/sys/kern/subr_witness.c 74912 2001-03-28 09:03:24Z jhb $
31 */
32
33/*
31 */
32
33/*
34 * Machine independent bits of mutex implementation and implementation of
35 * `witness' structure & related debugging routines.
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.
36 */
37
38/*
39 * Main Entry: witness
40 * Pronunciation: 'wit-n&s
41 * Function: noun
42 * Etymology: Middle English witnesse, from Old English witnes knowledge,
43 * testimony, witness, from 2wit

--- 12 unchanged lines hidden (view full) ---

56 */
57
58#include "opt_ddb.h"
59#include "opt_witness.h"
60
61#include <sys/param.h>
62#include <sys/bus.h>
63#include <sys/kernel.h>
37 */
38
39/*
40 * Main Entry: witness
41 * Pronunciation: 'wit-n&s
42 * Function: noun
43 * Etymology: Middle English witnesse, from Old English witnes knowledge,
44 * testimony, witness, from 2wit

--- 12 unchanged lines hidden (view full) ---

57 */
58
59#include "opt_ddb.h"
60#include "opt_witness.h"
61
62#include <sys/param.h>
63#include <sys/bus.h>
64#include <sys/kernel.h>
65#include <sys/ktr.h>
66#include <sys/lock.h>
64#include <sys/malloc.h>
67#include <sys/malloc.h>
68#include <sys/mutex.h>
65#include <sys/proc.h>
66#include <sys/sysctl.h>
67#include <sys/systm.h>
69#include <sys/proc.h>
70#include <sys/sysctl.h>
71#include <sys/systm.h>
68#include <sys/vmmeter.h>
69#include <sys/ktr.h>
70
72
71#include <machine/atomic.h>
72#include <machine/bus.h>
73#include <machine/clock.h>
74#include <machine/cpu.h>
75
76#include <ddb/ddb.h>
77
73#include <ddb/ddb.h>
74
78#include <vm/vm.h>
79#include <vm/vm_extern.h>
80
81#include <sys/mutex.h>
82
75#define WITNESS_COUNT 200
76#define WITNESS_CHILDCOUNT (WITNESS_COUNT * 4)
83/*
77/*
84 * The WITNESS-enabled mutex debug structure.
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.
85 */
81 */
86#ifdef WITNESS
87struct mtx_debug {
88 struct witness *mtxd_witness;
89 LIST_ENTRY(mtx) mtxd_held;
90 const char *mtxd_file;
91 int mtxd_line;
92};
82#define LOCK_CHILDCOUNT (MAXCPU + 1024) * 2
93
83
94#define mtx_held mtx_debug->mtxd_held
95#define mtx_file mtx_debug->mtxd_file
96#define mtx_line mtx_debug->mtxd_line
97#define mtx_witness mtx_debug->mtxd_witness
98#endif /* WITNESS */
84#define WITNESS_NCHILDREN 6
99
85
100/*
101 * Internal utility macros.
102 */
103#define mtx_unowned(m) ((m)->mtx_lock == MTX_UNOWNED)
86struct witness_child_list_entry;
104
87
105#define mtx_owner(m) (mtx_unowned((m)) ? NULL \
106 : (struct proc *)((m)->mtx_lock & MTX_FLAGMASK))
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};
107
102
108#define SET_PRIO(p, pri) (p)->p_pri.pri_level = (pri)
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};
109
108
110/*
111 * Early WITNESS-enabled declarations.
112 */
113#ifdef WITNESS
109STAILQ_HEAD(witness_list, witness);
114
110
115/*
116 * Internal WITNESS routines which must be prototyped early.
117 *
118 * XXX: When/if witness code is cleaned up, it would be wise to place all
119 * witness prototyping early in this file.
120 */
121static void witness_init(struct mtx *, int flag);
122static void witness_destroy(struct mtx *);
123static void witness_display(void(*)(const char *fmt, ...));
111struct witness_blessed {
112 const char *b_lock1;
113 const char *b_lock2;
114};
124
115
125MALLOC_DEFINE(M_WITNESS, "witness", "witness mtx_debug structure");
116struct witness_order_list_entry {
117 const char *w_name;
118 struct lock_class *w_class;
119};
126
120
127/* All mutexes in system (used for debug/panic) */
128static struct mtx_debug all_mtx_debug = { NULL, {NULL, NULL}, NULL, 0 };
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, ...));
129
142
130/*
131 * This global is set to 0 once it becomes safe to use the witness code.
132 */
133static int witness_cold = 1;
143MALLOC_DEFINE(M_WITNESS, "witness", "witness structure");
134
144
135#else /* WITNESS */
145static int witness_watch;
146TUNABLE_INT_DECL("debug.witness_watch", 1, witness_watch);
147SYSCTL_INT(_debug, OID_AUTO, witness_watch, CTLFLAG_RD, &witness_watch, 0, "");
136
148
137/* XXX XXX XXX
138 * flag++ is sleazoid way of shuting up warning
139 */
140#define witness_init(m, flag) flag++
141#define witness_destroy(m)
142#define witness_try_enter(m, t, f, l)
143#endif /* WITNESS */
144
145/*
146 * All mutex locks in system are kept on the all_mtx list.
147 */
148static struct mtx all_mtx = { MTX_UNOWNED, 0, 0, 0, "All mutexes queue head",
149 TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked),
150 { NULL, NULL }, &all_mtx, &all_mtx,
151#ifdef WITNESS
152 &all_mtx_debug
153#else
154 NULL
155#endif
156 };
157
158/*
159 * Global variables for book keeping.
160 */
161static int mtx_cur_cnt;
162static int mtx_max_cnt;
163
164/*
165 * Couple of strings for KTR_LOCK tracing in order to avoid duplicates.
166 */
167char STR_mtx_lock_slp[] = "GOT (sleep) %s [%p] r=%d at %s:%d";
168char STR_mtx_unlock_slp[] = "REL (sleep) %s [%p] r=%d at %s:%d";
169char STR_mtx_lock_spn[] = "GOT (spin) %s [%p] r=%d at %s:%d";
170char STR_mtx_unlock_spn[] = "REL (spin) %s [%p] r=%d at %s:%d";
171
172/*
173 * Prototypes for non-exported routines.
174 *
175 * NOTE: Prototypes for witness routines are placed at the bottom of the file.
176 */
177static void propagate_priority(struct proc *);
178
179static void
180propagate_priority(struct proc *p)
181{
182 int pri = p->p_pri.pri_level;
183 struct mtx *m = p->p_blocked;
184
185 mtx_assert(&sched_lock, MA_OWNED);
186 for (;;) {
187 struct proc *p1;
188
189 p = mtx_owner(m);
190
191 if (p == NULL) {
192 /*
193 * This really isn't quite right. Really
194 * ought to bump priority of process that
195 * next acquires the mutex.
196 */
197 MPASS(m->mtx_lock == MTX_CONTESTED);
198 return;
199 }
200
201 MPASS(p->p_magic == P_MAGIC);
202 KASSERT(p->p_stat != SSLEEP, ("sleeping process owns a mutex"));
203 if (p->p_pri.pri_level <= pri)
204 return;
205
206 /*
207 * Bump this process' priority.
208 */
209 SET_PRIO(p, pri);
210
211 /*
212 * If lock holder is actually running, just bump priority.
213 */
214 if (p->p_oncpu != NOCPU) {
215 MPASS(p->p_stat == SRUN || p->p_stat == SZOMB);
216 return;
217 }
218
219#ifndef SMP
220 /*
221 * For UP, we check to see if p is curproc (this shouldn't
222 * ever happen however as it would mean we are in a deadlock.)
223 */
224 KASSERT(p != curproc, ("Deadlock detected"));
225#endif
226
227 /*
228 * If on run queue move to new run queue, and
229 * quit.
230 */
231 if (p->p_stat == SRUN) {
232 MPASS(p->p_blocked == NULL);
233 remrunqueue(p);
234 setrunqueue(p);
235 return;
236 }
237
238 /*
239 * If we aren't blocked on a mutex, we should be.
240 */
241 KASSERT(p->p_stat == SMTX, (
242 "process %d(%s):%d holds %s but isn't blocked on a mutex\n",
243 p->p_pid, p->p_comm, p->p_stat,
244 m->mtx_description));
245
246 /*
247 * Pick up the mutex that p is blocked on.
248 */
249 m = p->p_blocked;
250 MPASS(m != NULL);
251
252 /*
253 * Check if the proc needs to be moved up on
254 * the blocked chain
255 */
256 if (p == TAILQ_FIRST(&m->mtx_blocked)) {
257 continue;
258 }
259
260 p1 = TAILQ_PREV(p, procqueue, p_procq);
261 if (p1->p_pri.pri_level <= pri) {
262 continue;
263 }
264
265 /*
266 * Remove proc from blocked chain and determine where
267 * it should be moved up to. Since we know that p1 has
268 * a lower priority than p, we know that at least one
269 * process in the chain has a lower priority and that
270 * p1 will thus not be NULL after the loop.
271 */
272 TAILQ_REMOVE(&m->mtx_blocked, p, p_procq);
273 TAILQ_FOREACH(p1, &m->mtx_blocked, p_procq) {
274 MPASS(p1->p_magic == P_MAGIC);
275 if (p1->p_pri.pri_level > pri)
276 break;
277 }
278
279 MPASS(p1 != NULL);
280 TAILQ_INSERT_BEFORE(p1, p, p_procq);
281 CTR4(KTR_LOCK,
282 "propagate_priority: p %p moved before %p on [%p] %s",
283 p, p1, m, m->mtx_description);
284 }
285}
286
287/*
288 * Function versions of the inlined __mtx_* macros. These are used by
289 * modules and can also be called from assembly language if needed.
290 */
291void
292_mtx_lock_flags(struct mtx *m, int opts, const char *file, int line)
293{
294
295 __mtx_lock_flags(m, opts, file, line);
296}
297
298void
299_mtx_unlock_flags(struct mtx *m, int opts, const char *file, int line)
300{
301
302 __mtx_unlock_flags(m, opts, file, line);
303}
304
305void
306_mtx_lock_spin_flags(struct mtx *m, int opts, const char *file, int line)
307{
308
309 __mtx_lock_spin_flags(m, opts, file, line);
310}
311
312void
313_mtx_unlock_spin_flags(struct mtx *m, int opts, const char *file, int line)
314{
315
316 __mtx_unlock_spin_flags(m, opts, file, line);
317}
318
319/*
320 * The important part of mtx_trylock{,_flags}()
321 * Tries to acquire lock `m.' We do NOT handle recursion here; we assume that
322 * if we're called, it's because we know we don't already own this lock.
323 */
324int
325_mtx_trylock(struct mtx *m, int opts, const char *file, int line)
326{
327 int rval;
328
329 MPASS(curproc != NULL);
330
331 /*
332 * _mtx_trylock does not accept MTX_NOSWITCH option.
333 */
334 KASSERT((opts & MTX_NOSWITCH) == 0,
335 ("mtx_trylock() called with invalid option flag(s) %d", opts));
336
337 rval = _obtain_lock(m, curproc);
338
339#ifdef WITNESS
340 if (rval && m->mtx_witness != NULL) {
341 /*
342 * We do not handle recursion in _mtx_trylock; see the
343 * note at the top of the routine.
344 */
345 KASSERT(!mtx_recursed(m),
346 ("mtx_trylock() called on a recursed mutex"));
347 witness_try_enter(m, (opts | m->mtx_flags), file, line);
348 }
349#endif /* WITNESS */
350
351 if ((opts & MTX_QUIET) == 0)
352 CTR5(KTR_LOCK, "TRY_LOCK %s [%p] result=%d at %s:%d",
353 m->mtx_description, m, rval, file, line);
354
355 return rval;
356}
357
358/*
359 * _mtx_lock_sleep: the tougher part of acquiring an MTX_DEF lock.
360 *
361 * We call this if the lock is either contested (i.e. we need to go to
362 * sleep waiting for it), or if we need to recurse on it.
363 */
364void
365_mtx_lock_sleep(struct mtx *m, int opts, const char *file, int line)
366{
367 struct proc *p = curproc;
368
369 if ((m->mtx_lock & MTX_FLAGMASK) == (uintptr_t)p) {
370 m->mtx_recurse++;
371 atomic_set_ptr(&m->mtx_lock, MTX_RECURSED);
372 if ((opts & MTX_QUIET) == 0)
373 CTR1(KTR_LOCK, "_mtx_lock_sleep: %p recursing", m);
374 return;
375 }
376
377 if ((opts & MTX_QUIET) == 0)
378 CTR4(KTR_LOCK,
379 "_mtx_lock_sleep: %s contested (lock=%p) at %s:%d",
380 m->mtx_description, (void *)m->mtx_lock, file, line);
381
382 while (!_obtain_lock(m, p)) {
383 uintptr_t v;
384 struct proc *p1;
385
386 mtx_lock_spin(&sched_lock);
387 /*
388 * Check if the lock has been released while spinning for
389 * the sched_lock.
390 */
391 if ((v = m->mtx_lock) == MTX_UNOWNED) {
392 mtx_unlock_spin(&sched_lock);
393 continue;
394 }
395
396 /*
397 * The mutex was marked contested on release. This means that
398 * there are processes blocked on it.
399 */
400 if (v == MTX_CONTESTED) {
401 p1 = TAILQ_FIRST(&m->mtx_blocked);
402 MPASS(p1 != NULL);
403 m->mtx_lock = (uintptr_t)p | MTX_CONTESTED;
404
405 if (p1->p_pri.pri_level < p->p_pri.pri_level)
406 SET_PRIO(p, p1->p_pri.pri_level);
407 mtx_unlock_spin(&sched_lock);
408 return;
409 }
410
411 /*
412 * If the mutex isn't already contested and a failure occurs
413 * setting the contested bit, the mutex was either released
414 * or the state of the MTX_RECURSED bit changed.
415 */
416 if ((v & MTX_CONTESTED) == 0 &&
417 !atomic_cmpset_ptr(&m->mtx_lock, (void *)v,
418 (void *)(v | MTX_CONTESTED))) {
419 mtx_unlock_spin(&sched_lock);
420 continue;
421 }
422
423 /*
424 * We deffinately must sleep for this lock.
425 */
426 mtx_assert(m, MA_NOTOWNED);
427
428#ifdef notyet
429 /*
430 * If we're borrowing an interrupted thread's VM context, we
431 * must clean up before going to sleep.
432 */
433 if (p->p_ithd != NULL) {
434 struct ithd *it = p->p_ithd;
435
436 if (it->it_interrupted) {
437 if ((opts & MTX_QUIET) == 0)
438 CTR2(KTR_LOCK,
439 "_mtx_lock_sleep: %p interrupted %p",
440 it, it->it_interrupted);
441 intr_thd_fixup(it);
442 }
443 }
444#endif
445
446 /*
447 * Put us on the list of threads blocked on this mutex.
448 */
449 if (TAILQ_EMPTY(&m->mtx_blocked)) {
450 p1 = (struct proc *)(m->mtx_lock & MTX_FLAGMASK);
451 LIST_INSERT_HEAD(&p1->p_contested, m, mtx_contested);
452 TAILQ_INSERT_TAIL(&m->mtx_blocked, p, p_procq);
453 } else {
454 TAILQ_FOREACH(p1, &m->mtx_blocked, p_procq)
455 if (p1->p_pri.pri_level > p->p_pri.pri_level)
456 break;
457 if (p1)
458 TAILQ_INSERT_BEFORE(p1, p, p_procq);
459 else
460 TAILQ_INSERT_TAIL(&m->mtx_blocked, p, p_procq);
461 }
462
463 /*
464 * Save who we're blocked on.
465 */
466 p->p_blocked = m;
467 p->p_mtxname = m->mtx_description;
468 p->p_stat = SMTX;
469 propagate_priority(p);
470
471 if ((opts & MTX_QUIET) == 0)
472 CTR3(KTR_LOCK,
473 "_mtx_lock_sleep: p %p blocked on [%p] %s", p, m,
474 m->mtx_description);
475
476 mi_switch();
477
478 if ((opts & MTX_QUIET) == 0)
479 CTR3(KTR_LOCK,
480 "_mtx_lock_sleep: p %p free from blocked on [%p] %s",
481 p, m, m->mtx_description);
482
483 mtx_unlock_spin(&sched_lock);
484 }
485
486 return;
487}
488
489/*
490 * _mtx_lock_spin: the tougher part of acquiring an MTX_SPIN lock.
491 *
492 * This is only called if we need to actually spin for the lock. Recursion
493 * is handled inline.
494 */
495void
496_mtx_lock_spin(struct mtx *m, int opts, critical_t mtx_crit, const char *file,
497 int line)
498{
499 int i = 0;
500
501 if ((opts & MTX_QUIET) == 0)
502 CTR1(KTR_LOCK, "_mtx_lock_spin: %p spinning", m);
503
504 for (;;) {
505 if (_obtain_lock(m, curproc))
506 break;
507
508 while (m->mtx_lock != MTX_UNOWNED) {
509 if (i++ < 1000000)
510 continue;
511 if (i++ < 6000000)
512 DELAY(1);
513#ifdef DDB
149#ifdef DDB
514 else if (!db_active)
515#else
516 else
517#endif
518 panic("spin lock %s held by %p for > 5 seconds",
519 m->mtx_description, (void *)m->mtx_lock);
520 }
521 }
522
523 m->mtx_savecrit = mtx_crit;
524 if ((opts & MTX_QUIET) == 0)
525 CTR1(KTR_LOCK, "_mtx_lock_spin: %p spin done", m);
526
527 return;
528}
529
530/*
150/*
531 * _mtx_unlock_sleep: the tougher part of releasing an MTX_DEF lock.
532 *
533 * We are only called here if the lock is recursed or contested (i.e. we
534 * need to wake up a blocked thread).
535 */
536void
537_mtx_unlock_sleep(struct mtx *m, int opts, const char *file, int line)
538{
539 struct proc *p, *p1;
540 struct mtx *m1;
541 int pri;
542
543 p = curproc;
544
545 if (mtx_recursed(m)) {
546 if (--(m->mtx_recurse) == 0)
547 atomic_clear_ptr(&m->mtx_lock, MTX_RECURSED);
548 if ((opts & MTX_QUIET) == 0)
549 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p unrecurse", m);
550 return;
551 }
552
553 mtx_lock_spin(&sched_lock);
554 if ((opts & MTX_QUIET) == 0)
555 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p contested", m);
556
557 p1 = TAILQ_FIRST(&m->mtx_blocked);
558 MPASS(p->p_magic == P_MAGIC);
559 MPASS(p1->p_magic == P_MAGIC);
560
561 TAILQ_REMOVE(&m->mtx_blocked, p1, p_procq);
562
563 if (TAILQ_EMPTY(&m->mtx_blocked)) {
564 LIST_REMOVE(m, mtx_contested);
565 _release_lock_quick(m);
566 if ((opts & MTX_QUIET) == 0)
567 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p not held", m);
568 } else
569 atomic_store_rel_ptr(&m->mtx_lock, (void *)MTX_CONTESTED);
570
571 pri = PRI_MAX;
572 LIST_FOREACH(m1, &p->p_contested, mtx_contested) {
573 int cp = TAILQ_FIRST(&m1->mtx_blocked)->p_pri.pri_level;
574 if (cp < pri)
575 pri = cp;
576 }
577
578 if (pri > p->p_pri.pri_native)
579 pri = p->p_pri.pri_native;
580 SET_PRIO(p, pri);
581
582 if ((opts & MTX_QUIET) == 0)
583 CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p contested setrunqueue %p",
584 m, p1);
585
586 p1->p_blocked = NULL;
587 p1->p_stat = SRUN;
588 setrunqueue(p1);
589
590 if ((opts & MTX_NOSWITCH) == 0 && p1->p_pri.pri_level < pri) {
591#ifdef notyet
592 if (p->p_ithd != NULL) {
593 struct ithd *it = p->p_ithd;
594
595 if (it->it_interrupted) {
596 if ((opts & MTX_QUIET) == 0)
597 CTR2(KTR_LOCK,
598 "_mtx_unlock_sleep: %p interrupted %p",
599 it, it->it_interrupted);
600 intr_thd_fixup(it);
601 }
602 }
603#endif
604 setrunqueue(p);
605 if ((opts & MTX_QUIET) == 0)
606 CTR2(KTR_LOCK,
607 "_mtx_unlock_sleep: %p switching out lock=%p", m,
608 (void *)m->mtx_lock);
609
610 mi_switch();
611 if ((opts & MTX_QUIET) == 0)
612 CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p resuming lock=%p",
613 m, (void *)m->mtx_lock);
614 }
615
616 mtx_unlock_spin(&sched_lock);
617
618 return;
619}
620
621/*
622 * All the unlocking of MTX_SPIN locks is done inline.
623 * See the _rel_spin_lock() macro for the details.
624 */
625
626/*
627 * The backing function for the INVARIANTS-enabled mtx_assert()
628 */
629#ifdef INVARIANT_SUPPORT
630void
631_mtx_assert(struct mtx *m, int what, const char *file, int line)
632{
633 switch (what) {
634 case MA_OWNED:
635 case MA_OWNED | MA_RECURSED:
636 case MA_OWNED | MA_NOTRECURSED:
637 if (!mtx_owned(m))
638 panic("mutex %s not owned at %s:%d",
639 m->mtx_description, file, line);
640 if (mtx_recursed(m)) {
641 if ((what & MA_NOTRECURSED) != 0)
642 panic("mutex %s recursed at %s:%d",
643 m->mtx_description, file, line);
644 } else if ((what & MA_RECURSED) != 0) {
645 panic("mutex %s unrecursed at %s:%d",
646 m->mtx_description, file, line);
647 }
648 break;
649 case MA_NOTOWNED:
650 if (mtx_owned(m))
651 panic("mutex %s owned at %s:%d",
652 m->mtx_description, file, line);
653 break;
654 default:
655 panic("unknown mtx_assert at %s:%d", file, line);
656 }
657}
658#endif
659
660/*
661 * The MUTEX_DEBUG-enabled mtx_validate()
662 */
663#define MV_DESTROY 0 /* validate before destory */
664#define MV_INIT 1 /* validate before init */
665
666#ifdef MUTEX_DEBUG
667
668int mtx_validate __P((struct mtx *, int));
669
670int
671mtx_validate(struct mtx *m, int when)
672{
673 struct mtx *mp;
674 int i;
675 int retval = 0;
676
677#ifdef WITNESS
678 if (witness_cold)
679 return 0;
680#endif
681 if (m == &all_mtx || cold)
682 return 0;
683
684 mtx_lock(&all_mtx);
685/*
686 * XXX - When kernacc() is fixed on the alpha to handle K0_SEG memory properly
687 * we can re-enable the kernacc() checks.
688 */
689#ifndef __alpha__
690 MPASS(kernacc((caddr_t)all_mtx.mtx_next, sizeof(uintptr_t),
691 VM_PROT_READ) == 1);
692#endif
693 MPASS(all_mtx.mtx_next->mtx_prev == &all_mtx);
694 for (i = 0, mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) {
695#ifndef __alpha__
696 if (kernacc((caddr_t)mp->mtx_next, sizeof(uintptr_t),
697 VM_PROT_READ) != 1) {
698 panic("mtx_validate: mp=%p mp->mtx_next=%p",
699 mp, mp->mtx_next);
700 }
701#endif
702 i++;
703 if (i > mtx_cur_cnt) {
704 panic("mtx_validate: too many in chain, known=%d\n",
705 mtx_cur_cnt);
706 }
707 }
708 MPASS(i == mtx_cur_cnt);
709 switch (when) {
710 case MV_DESTROY:
711 for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next)
712 if (mp == m)
713 break;
714 MPASS(mp == m);
715 break;
716 case MV_INIT:
717 for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next)
718 if (mp == m) {
719 /*
720 * Not good. This mutex already exists.
721 */
722 printf("re-initing existing mutex %s\n",
723 m->mtx_description);
724 MPASS(m->mtx_lock == MTX_UNOWNED);
725 retval = 1;
726 }
727 }
728 mtx_unlock(&all_mtx);
729 return (retval);
730}
731#endif
732
733/*
734 * Mutex initialization routine; initialize lock `m' of type contained in
735 * `opts' with options contained in `opts' and description `description.'
736 * Place on "all_mtx" queue.
737 */
738void
739mtx_init(struct mtx *m, const char *description, int opts)
740{
741
742 if ((opts & MTX_QUIET) == 0)
743 CTR2(KTR_LOCK, "mtx_init %p (%s)", m, description);
744
745#ifdef MUTEX_DEBUG
746 /* Diagnostic and error correction */
747 if (mtx_validate(m, MV_INIT))
748 return;
749#endif
750
751 bzero((void *)m, sizeof *m);
752 TAILQ_INIT(&m->mtx_blocked);
753
754#ifdef WITNESS
755 if (!witness_cold) {
756 m->mtx_debug = malloc(sizeof(struct mtx_debug),
757 M_WITNESS, M_NOWAIT | M_ZERO);
758 MPASS(m->mtx_debug != NULL);
759 }
760#endif
761
762 m->mtx_description = description;
763 m->mtx_flags = opts;
764 m->mtx_lock = MTX_UNOWNED;
765
766 /* Put on all mutex queue */
767 mtx_lock(&all_mtx);
768 m->mtx_next = &all_mtx;
769 m->mtx_prev = all_mtx.mtx_prev;
770 m->mtx_prev->mtx_next = m;
771 all_mtx.mtx_prev = m;
772 if (++mtx_cur_cnt > mtx_max_cnt)
773 mtx_max_cnt = mtx_cur_cnt;
774 mtx_unlock(&all_mtx);
775
776#ifdef WITNESS
777 if (!witness_cold)
778 witness_init(m, opts);
779#endif
780}
781
782/*
783 * Remove lock `m' from all_mtx queue.
784 */
785void
786mtx_destroy(struct mtx *m)
787{
788
789#ifdef WITNESS
790 KASSERT(!witness_cold, ("%s: Cannot destroy while still cold\n",
791 __FUNCTION__));
792#endif
793
794 CTR2(KTR_LOCK, "mtx_destroy %p (%s)", m, m->mtx_description);
795
796#ifdef MUTEX_DEBUG
797 if (m->mtx_next == NULL)
798 panic("mtx_destroy: %p (%s) already destroyed",
799 m, m->mtx_description);
800
801 if (!mtx_owned(m)) {
802 MPASS(m->mtx_lock == MTX_UNOWNED);
803 } else {
804 MPASS((m->mtx_lock & (MTX_RECURSED|MTX_CONTESTED)) == 0);
805 }
806
807 /* diagnostic */
808 mtx_validate(m, MV_DESTROY);
809#endif
810
811#ifdef WITNESS
812 if (m->mtx_witness)
813 witness_destroy(m);
814#endif /* WITNESS */
815
816 /* Remove from the all mutex queue */
817 mtx_lock(&all_mtx);
818 m->mtx_next->mtx_prev = m->mtx_prev;
819 m->mtx_prev->mtx_next = m->mtx_next;
820
821#ifdef MUTEX_DEBUG
822 m->mtx_next = m->mtx_prev = NULL;
823#endif
824
825#ifdef WITNESS
826 free(m->mtx_debug, M_WITNESS);
827 m->mtx_debug = NULL;
828#endif
829
830 mtx_cur_cnt--;
831 mtx_unlock(&all_mtx);
832}
833
834
835/*
836 * The WITNESS-enabled diagnostic code.
837 */
838#ifdef WITNESS
839static void
840witness_fixup(void *dummy __unused)
841{
842 struct mtx *mp;
843
844 /*
845 * We have to release Giant before initializing its witness
846 * structure so that WITNESS doesn't get confused.
847 */
848 mtx_unlock(&Giant);
849 mtx_assert(&Giant, MA_NOTOWNED);
850
851 mtx_lock(&all_mtx);
852
853 /* Iterate through all mutexes and finish up mutex initialization. */
854 for (mp = all_mtx.mtx_next; mp != &all_mtx; mp = mp->mtx_next) {
855
856 mp->mtx_debug = malloc(sizeof(struct mtx_debug),
857 M_WITNESS, M_NOWAIT | M_ZERO);
858 MPASS(mp->mtx_debug != NULL);
859
860 witness_init(mp, mp->mtx_flags);
861 }
862 mtx_unlock(&all_mtx);
863
864 /* Mark the witness code as being ready for use. */
865 atomic_store_rel_int(&witness_cold, 0);
866
867 mtx_lock(&Giant);
868}
869SYSINIT(wtnsfxup, SI_SUB_MUTEX, SI_ORDER_FIRST, witness_fixup, NULL)
870
871#define WITNESS_COUNT 200
872#define WITNESS_NCHILDREN 2
873
874int witness_watch = 1;
875
876struct witness {
877 struct witness *w_next;
878 const char *w_description;
879 const char *w_file;
880 int w_line;
881 struct witness *w_morechildren;
882 u_char w_childcnt;
883 u_char w_Giant_squawked:1;
884 u_char w_other_squawked:1;
885 u_char w_same_squawked:1;
886 u_char w_spin:1; /* MTX_SPIN type mutex. */
887 u_int w_level;
888 struct witness *w_children[WITNESS_NCHILDREN];
889};
890
891struct witness_blessed {
892 char *b_lock1;
893 char *b_lock2;
894};
895
896#ifdef DDB
897/*
898 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to
899 * drop into kdebug() when:
900 * - a lock heirarchy violation occurs
901 * - locks are held when going to sleep.
902 */
903int witness_ddb;
904#ifdef WITNESS_DDB
905TUNABLE_INT_DECL("debug.witness_ddb", 1, witness_ddb);

--- 7 unchanged lines hidden (view full) ---

913#ifdef WITNESS_SKIPSPIN
914TUNABLE_INT_DECL("debug.witness_skipspin", 1, witness_skipspin);
915#else
916TUNABLE_INT_DECL("debug.witness_skipspin", 0, witness_skipspin);
917#endif
918SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0,
919 "");
920
151 * When DDB is enabled and witness_ddb is set to 1, it will cause the system to
152 * drop into kdebug() when:
153 * - a lock heirarchy violation occurs
154 * - locks are held when going to sleep.
155 */
156int witness_ddb;
157#ifdef WITNESS_DDB
158TUNABLE_INT_DECL("debug.witness_ddb", 1, witness_ddb);

--- 7 unchanged lines hidden (view full) ---

166#ifdef WITNESS_SKIPSPIN
167TUNABLE_INT_DECL("debug.witness_skipspin", 1, witness_skipspin);
168#else
169TUNABLE_INT_DECL("debug.witness_skipspin", 0, witness_skipspin);
170#endif
171SYSCTL_INT(_debug, OID_AUTO, witness_skipspin, CTLFLAG_RD, &witness_skipspin, 0,
172 "");
173
921/*
922 * Witness-enabled globals
923 */
924static struct mtx w_mtx;
925static struct witness *w_free;
926static struct witness *w_all;
927static int w_inited;
928static int witness_dead; /* fatal error, probably no memory */
174static struct mtx w_mtx;
175static struct witness_list w_free = STAILQ_HEAD_INITIALIZER(w_free);
176static struct witness_list w_all = STAILQ_HEAD_INITIALIZER(w_all);
177static struct witness_list w_spin = STAILQ_HEAD_INITIALIZER(w_spin);
178static struct witness_list w_sleep = STAILQ_HEAD_INITIALIZER(w_sleep);
179static struct witness_child_list_entry *w_child_free = NULL;
180static struct lock_list_entry *w_lock_list_free = NULL;
181static int witness_dead; /* fatal error, probably no memory */
929
182
930static struct witness w_data[WITNESS_COUNT];
183static struct witness w_data[WITNESS_COUNT];
184static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT];
185static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
931
186
932/*
933 * Internal witness routine prototypes
934 */
935static struct witness *enroll(const char *description, int flag);
936static int itismychild(struct witness *parent, struct witness *child);
937static void removechild(struct witness *parent, struct witness *child);
938static int isitmychild(struct witness *parent, struct witness *child);
939static int isitmydescendant(struct witness *parent, struct witness *child);
940static int dup_ok(struct witness *);
941static int blessed(struct witness *, struct witness *);
942static void
943 witness_displaydescendants(void(*)(const char *fmt, ...), struct witness *);
944static void witness_leveldescendents(struct witness *parent, int level);
945static void witness_levelall(void);
946static struct witness * witness_get(void);
947static void witness_free(struct witness *m);
948
949static char *ignore_list[] = {
950 "witness lock",
951 NULL
952};
953
954static char *spin_order_list[] = {
187static struct witness_order_list_entry order_lists[] = {
188 { "Giant", &lock_class_mtx_sleep },
189 { "proctree", &lock_class_sx },
190 { "allproc", &lock_class_sx },
191 { "process lock", &lock_class_mtx_sleep },
192 { "uidinfo hash", &lock_class_mtx_sleep },
193 { "uidinfo struct", &lock_class_mtx_sleep },
194 { NULL, NULL },
955#if defined(__i386__) && defined (SMP)
195#if defined(__i386__) && defined (SMP)
956 "com",
196 { "com", &lock_class_mtx_spin },
957#endif
197#endif
958 "sio",
198 { "sio", &lock_class_mtx_spin },
959#ifdef __i386__
199#ifdef __i386__
960 "cy",
200 { "cy", &lock_class_mtx_spin },
961#endif
201#endif
962 "ng_node",
963 "ng_worklist",
964 "ithread table lock",
965 "ithread list lock",
966 "sched lock",
202 { "ng_node", &lock_class_mtx_spin },
203 { "ng_worklist", &lock_class_mtx_spin },
204 { "ithread table lock", &lock_class_mtx_spin },
205 { "ithread list lock", &lock_class_mtx_spin },
206 { "sched lock", &lock_class_mtx_spin },
967#ifdef __i386__
207#ifdef __i386__
968 "clk",
208 { "clk", &lock_class_mtx_spin },
969#endif
209#endif
970 "callout",
210 { "callout", &lock_class_mtx_spin },
971 /*
972 * leaf locks
973 */
974#ifdef SMP
975#ifdef __i386__
211 /*
212 * leaf locks
213 */
214#ifdef SMP
215#ifdef __i386__
976 "ap boot",
977 "imen",
216 { "ap boot", &lock_class_mtx_spin },
217 { "imen", &lock_class_mtx_spin },
978#endif
218#endif
979 "smp rendezvous",
219 { "smp rendezvous", &lock_class_mtx_spin },
980#endif
220#endif
981 NULL
221 { NULL, NULL },
222 { NULL, NULL }
982};
983
223};
224
984static char *order_list[] = {
985 "Giant", "proctree", "allproc", "process lock", "uidinfo hash",
986 "uidinfo struct", NULL,
987 NULL
988};
989
990static char *dup_list[] = {
225static const char *dup_list[] = {
991 "process lock",
992 NULL
993};
994
226 "process lock",
227 NULL
228};
229
995static char *sleep_list[] = {
996 "Giant",
997 NULL
998};
999
1000/*
1001 * Pairs of locks which have been blessed
1002 * Don't complain about order problems with blessed locks
1003 */
1004static struct witness_blessed blessed_list[] = {
1005};
1006static int blessed_count =
1007 sizeof(blessed_list) / sizeof(struct witness_blessed);
1008
230/*
231 * Pairs of locks which have been blessed
232 * Don't complain about order problems with blessed locks
233 */
234static struct witness_blessed blessed_list[] = {
235};
236static int blessed_count =
237 sizeof(blessed_list) / sizeof(struct witness_blessed);
238
1009static void
1010witness_init(struct mtx *m, int flag)
1011{
1012 m->mtx_witness = enroll(m->mtx_description, flag);
1013}
239/*
240 * List of all locks in the system.
241 */
242STAILQ_HEAD(, lock_object) all_locks = STAILQ_HEAD_INITIALIZER(all_locks);
1014
243
244static struct mtx all_mtx = {
245 { &lock_class_mtx_sleep, /* mtx_object.lo_class */
246 "All locks list", /* mtx_object.lo_name */
247 NULL, /* mtx_object.lo_file */
248 0, /* mtx_object.lo_line */
249 LO_INITIALIZED, /* mtx_object.lo_flags */
250 { NULL }, /* mtx_object.lo_list */
251 NULL }, /* mtx_object.lo_witness */
252 MTX_UNOWNED, 0, /* mtx_lock, mtx_recurse */
253 0, /* mtx_savecrit */
254 TAILQ_HEAD_INITIALIZER(all_mtx.mtx_blocked),
255 { NULL, NULL } /* mtx_contested */
256};
257
258/*
259 * This global is set to 0 once it becomes safe to use the witness code.
260 */
261static int witness_cold = 1;
262
263/*
264 * Global variables for book keeping.
265 */
266static int lock_cur_cnt;
267static int lock_max_cnt;
268
269/*
270 * The WITNESS-enabled diagnostic code.
271 */
1015static void
272static void
1016witness_destroy(struct mtx *m)
273witness_initialize(void *dummy __unused)
1017{
274{
1018 struct mtx *m1;
1019 struct proc *p;
1020 p = curproc;
1021 LIST_FOREACH(m1, &p->p_heldmtx, mtx_held) {
1022 if (m1 == m) {
1023 LIST_REMOVE(m, mtx_held);
1024 break;
275 struct lock_object *lock;
276 struct witness_order_list_entry *order;
277 struct witness *w, *w1;
278 int i;
279
280 /*
281 * We have to release Giant before initializing its witness
282 * structure so that WITNESS doesn't get confused.
283 */
284 mtx_unlock(&Giant);
285 mtx_assert(&Giant, MA_NOTOWNED);
286
287 STAILQ_INSERT_HEAD(&all_locks, &all_mtx.mtx_object, lo_list);
288 mtx_init(&w_mtx, "witness lock", MTX_SPIN | MTX_QUIET | MTX_NOWITNESS);
289 for (i = 0; i < WITNESS_COUNT; i++)
290 witness_free(&w_data[i]);
291 for (i = 0; i < WITNESS_CHILDCOUNT; i++)
292 witness_child_free(&w_childdata[i]);
293 for (i = 0; i < LOCK_CHILDCOUNT; i++)
294 witness_lock_list_free(&w_locklistdata[i]);
295
296 /* First add in all the specified order lists. */
297 for (order = order_lists; order->w_name != NULL; order++) {
298 w = enroll(order->w_name, order->w_class);
299 w->w_file = "order list";
300 for (order++; order->w_name != NULL; order++) {
301 w1 = enroll(order->w_name, order->w_class);
302 w1->w_file = "order list";
303 itismychild(w, w1);
304 w = w1;
1025 }
1026 }
305 }
306 }
1027 return;
1028
307
308 /* Iterate through all locks and add them to witness. */
309 mtx_lock(&all_mtx);
310 STAILQ_FOREACH(lock, &all_locks, lo_list) {
311 if (lock->lo_flags & LO_WITNESS)
312 lock->lo_witness = enroll(lock->lo_name,
313 lock->lo_class);
314 else
315 lock->lo_witness = NULL;
316 }
317 mtx_unlock(&all_mtx);
318
319 /* Mark the witness code as being ready for use. */
320 atomic_store_rel_int(&witness_cold, 0);
321
322 mtx_lock(&Giant);
1029}
323}
324SYSINIT(witness_init, SI_SUB_WITNESS, SI_ORDER_FIRST, witness_initialize, NULL)
1030
325
326void
327witness_init(struct lock_object *lock)
328{
329 struct lock_class *class;
330
331 class = lock->lo_class;
332 if (lock->lo_flags & LO_INITIALIZED)
333 panic("%s: lock (%s) %s is already initialized!\n", __func__,
334 class->lc_name, lock->lo_name);
335
336 if ((lock->lo_flags & LO_RECURSABLE) != 0 &&
337 (class->lc_flags & LC_RECURSABLE) == 0)
338 panic("%s: lock (%s) %s can not be recursable!\n", __func__,
339 class->lc_name, lock->lo_name);
340
341 if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
342 (class->lc_flags & LC_SLEEPABLE) == 0)
343 panic("%s: lock (%s) %s can not be sleepable!\n", __func__,
344 class->lc_name, lock->lo_name);
345
346 mtx_lock(&all_mtx);
347 STAILQ_INSERT_TAIL(&all_locks, lock, lo_list);
348 lock->lo_flags |= LO_INITIALIZED;
349 lock_cur_cnt++;
350 if (lock_cur_cnt > lock_max_cnt)
351 lock_max_cnt = lock_cur_cnt;
352 mtx_unlock(&all_mtx);
353 if (!witness_cold && !witness_dead &&
354 (lock->lo_flags & LO_WITNESS) != 0)
355 lock->lo_witness = enroll(lock->lo_name, class);
356 else
357 lock->lo_witness = NULL;
358}
359
360void
361witness_destroy(struct lock_object *lock)
362{
363
364 if (witness_cold)
365 panic("lock (%s) %s destroyed while witness_cold",
366 lock->lo_class->lc_name, lock->lo_name);
367
368 if ((lock->lo_flags & LO_INITIALIZED) == 0)
369 panic("%s: lock (%s) %s is not initialized!\n", __func__,
370 lock->lo_class->lc_name, lock->lo_name);
371
372 if (lock->lo_flags & LO_LOCKED)
373 panic("lock (%s) %s destroyed while held",
374 lock->lo_class->lc_name, lock->lo_name);
375
376 mtx_lock(&all_mtx);
377 lock_cur_cnt--;
378 STAILQ_REMOVE(&all_locks, lock, lock_object, lo_list);
379 lock->lo_flags &= LO_INITIALIZED;
380 mtx_unlock(&all_mtx);
381}
382
1031static void
383static void
1032witness_display(void(*prnt)(const char *fmt, ...))
384witness_display_list(void(*prnt)(const char *fmt, ...),
385 struct witness_list *list)
1033{
1034 struct witness *w, *w1;
386{
387 struct witness *w, *w1;
1035 int level, found;
388 int found;
1036
389
1037 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__));
1038 witness_levelall();
1039
1040 /*
1041 * First, handle sleep mutexes which have been acquired at least
1042 * once.
1043 */
1044 prnt("Sleep mutexes:\n");
1045 for (w = w_all; w; w = w->w_next) {
1046 if (w->w_file == NULL || w->w_spin)
390 STAILQ_FOREACH(w, list, w_typelist) {
391 if (w->w_file == NULL)
1047 continue;
392 continue;
1048 for (w1 = w_all; w1; w1 = w1->w_next) {
1049 if (isitmychild(w1, w))
393 found = 0;
394 STAILQ_FOREACH(w1, list, w_typelist) {
395 if (isitmychild(w1, w)) {
396 found++;
1050 break;
397 break;
398 }
1051 }
399 }
1052 if (w1 != NULL)
400 if (found)
1053 continue;
1054 /*
1055 * This lock has no anscestors, display its descendants.
1056 */
1057 witness_displaydescendants(prnt, w);
1058 }
401 continue;
402 /*
403 * This lock has no anscestors, display its descendants.
404 */
405 witness_displaydescendants(prnt, w);
406 }
407}
1059
408
409static void
410witness_display(void(*prnt)(const char *fmt, ...))
411{
412 struct witness *w;
413
414 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
415 witness_levelall();
416
1060 /*
417 /*
418 * First, handle sleep mutexes which have been acquired at least
419 * once.
420 */
421 prnt("Sleep locks:\n");
422 witness_display_list(prnt, &w_sleep);
423
424 /*
1061 * Now do spin mutexes which have been acquired at least once.
1062 */
425 * Now do spin mutexes which have been acquired at least once.
426 */
1063 prnt("\nSpin mutexes:\n");
1064 level = 0;
1065 while (level < sizeof(spin_order_list) / sizeof(char *)) {
1066 found = 0;
1067 for (w = w_all; w; w = w->w_next) {
1068 if (w->w_file == NULL || !w->w_spin)
1069 continue;
1070 if (w->w_level == 1 << level) {
1071 witness_displaydescendants(prnt, w);
1072 level++;
1073 found = 1;
1074 }
1075 }
1076 if (found == 0)
1077 level++;
1078 }
427 prnt("\nSpin locks:\n");
428 witness_display_list(prnt, &w_spin);
1079
1080 /*
1081 * Finally, any mutexes which have not been acquired yet.
1082 */
429
430 /*
431 * Finally, any mutexes which have not been acquired yet.
432 */
1083 prnt("\nMutexes which were never acquired:\n");
1084 for (w = w_all; w; w = w->w_next) {
433 prnt("\nLocks which were never acquired:\n");
434 STAILQ_FOREACH(w, &w_all, w_list) {
1085 if (w->w_file != NULL)
1086 continue;
435 if (w->w_file != NULL)
436 continue;
1087 prnt("%s\n", w->w_description);
437 prnt("%s\n", w->w_name);
1088 }
1089}
1090
1091void
438 }
439}
440
441void
1092witness_enter(struct mtx *m, int flags, const char *file, int line)
442witness_lock(struct lock_object *lock, int flags, const char *file, int line)
1093{
443{
444 struct lock_list_entry **lock_list, *lle;
445 struct lock_object *lock1, *lock2;
446 struct lock_class *class;
1094 struct witness *w, *w1;
447 struct witness *w, *w1;
1095 struct mtx *m1;
1096 struct proc *p;
448 struct proc *p;
1097 int i;
449 int i, j;
1098#ifdef DDB
1099 int go_into_ddb = 0;
1100#endif /* DDB */
1101
450#ifdef DDB
451 int go_into_ddb = 0;
452#endif /* DDB */
453
1102 if (witness_cold || m->mtx_witness == NULL || panicstr)
454 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
455 panicstr)
1103 return;
456 return;
1104 w = m->mtx_witness;
457 w = lock->lo_witness;
458 class = lock->lo_class;
1105 p = curproc;
1106
459 p = curproc;
460
1107 if (flags & MTX_SPIN) {
1108 if ((m->mtx_flags & MTX_SPIN) == 0)
1109 panic("mutex_enter: MTX_SPIN on MTX_DEF mutex %s @"
1110 " %s:%d", m->mtx_description, file, line);
1111 if (mtx_recursed(m)) {
1112 if ((m->mtx_flags & MTX_RECURSE) == 0)
1113 panic("mutex_enter: recursion on non-recursive"
1114 " mutex %s @ %s:%d", m->mtx_description,
1115 file, line);
1116 return;
1117 }
1118 mtx_lock_spin_flags(&w_mtx, MTX_QUIET);
1119 i = PCPU_GET(witness_spin_check);
1120 if (i != 0 && w->w_level < i) {
1121 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
1122 panic("mutex_enter(%s:%x, MTX_SPIN) out of order @"
1123 " %s:%d already holding %s:%x",
1124 m->mtx_description, w->w_level, file, line,
1125 spin_order_list[ffs(i)-1], i);
1126 }
1127 PCPU_SET(witness_spin_check, i | w->w_level);
1128 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
1129 p->p_spinlocks++;
1130 MPASS(p->p_spinlocks > 0);
1131 w->w_file = file;
1132 w->w_line = line;
1133 m->mtx_line = line;
1134 m->mtx_file = file;
1135 return;
1136 }
1137 if ((m->mtx_flags & MTX_SPIN) != 0)
1138 panic("mutex_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d",
1139 m->mtx_description, file, line);
461 if ((lock->lo_flags & LO_LOCKED) == 0)
462 panic("%s: lock (%s) %s is not locked @ %s:%d", __func__,
463 class->lc_name, lock->lo_name, file, line);
1140
464
1141 if (mtx_recursed(m)) {
1142 if ((m->mtx_flags & MTX_RECURSE) == 0)
1143 panic("mutex_enter: recursion on non-recursive"
1144 " mutex %s @ %s:%d", m->mtx_description,
1145 file, line);
465 if ((lock->lo_flags & LO_RECURSED) != 0) {
466 if ((lock->lo_flags & LO_RECURSABLE) == 0)
467 panic(
468 "%s: recursed on non-recursive lock (%s) %s @ %s:%d",
469 __func__, class->lc_name, lock->lo_name, file,
470 line);
1146 return;
1147 }
471 return;
472 }
1148 if (witness_dead)
473
474 lock_list = PCPU_PTR(spinlocks);
475 if (class->lc_flags & LC_SLEEPLOCK) {
476 if (*lock_list != NULL)
477 panic("blockable sleep lock (%s) %s @ %s:%d",
478 class->lc_name, lock->lo_name, file, line);
479 lock_list = &p->p_sleeplocks;
480 }
481
482 if (flags & LOP_TRYLOCK)
1149 goto out;
483 goto out;
1150 if (cold)
1151 goto out;
1152
484
1153 if (p->p_spinlocks != 0)
1154 panic("blockable mtx_lock() of %s when not legal @ %s:%d",
1155 m->mtx_description, file, line);
1156 /*
485 /*
1157 * Is this the first mutex acquired
486 * Is this the first lock acquired? If so, then no order checking
487 * is needed.
1158 */
488 */
1159 if ((m1 = LIST_FIRST(&p->p_heldmtx)) == NULL)
489 if (*lock_list == NULL)
1160 goto out;
1161
490 goto out;
491
1162 if ((w1 = m1->mtx_witness) == w) {
492 /*
493 * Check for duplicate locks of the same type. Note that we only
494 * have to check for this on the last lock we just acquired. Any
495 * other cases will be caught as lock order violations.
496 */
497 lock1 = (*lock_list)->ll_children[(*lock_list)->ll_count - 1];
498 w1 = lock1->lo_witness;
499 if (w1 == w) {
1163 if (w->w_same_squawked || dup_ok(w))
1164 goto out;
1165 w->w_same_squawked = 1;
1166 printf("acquring duplicate lock of same type: \"%s\"\n",
500 if (w->w_same_squawked || dup_ok(w))
501 goto out;
502 w->w_same_squawked = 1;
503 printf("acquring duplicate lock of same type: \"%s\"\n",
1167 m->mtx_description);
504 lock->lo_name);
1168 printf(" 1st @ %s:%d\n", w->w_file, w->w_line);
1169 printf(" 2nd @ %s:%d\n", file, line);
1170#ifdef DDB
1171 go_into_ddb = 1;
1172#endif /* DDB */
1173 goto out;
1174 }
1175 MPASS(!mtx_owned(&w_mtx));
505 printf(" 1st @ %s:%d\n", w->w_file, w->w_line);
506 printf(" 2nd @ %s:%d\n", file, line);
507#ifdef DDB
508 go_into_ddb = 1;
509#endif /* DDB */
510 goto out;
511 }
512 MPASS(!mtx_owned(&w_mtx));
1176 mtx_lock_spin_flags(&w_mtx, MTX_QUIET);
513 mtx_lock_spin(&w_mtx);
1177 /*
1178 * If we have a known higher number just say ok
1179 */
1180 if (witness_watch > 1 && w->w_level > w1->w_level) {
514 /*
515 * If we have a known higher number just say ok
516 */
517 if (witness_watch > 1 && w->w_level > w1->w_level) {
1181 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
518 mtx_unlock_spin(&w_mtx);
1182 goto out;
1183 }
519 goto out;
520 }
1184 if (isitmydescendant(m1->mtx_witness, w)) {
1185 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
521 if (isitmydescendant(w1, w)) {
522 mtx_unlock_spin(&w_mtx);
1186 goto out;
1187 }
523 goto out;
524 }
1188 for (i = 0; m1 != NULL; m1 = LIST_NEXT(m1, mtx_held), i++) {
525 for (j = 0, lle = *lock_list; lle != NULL; lle = lle->ll_next) {
526 for (i = lle->ll_count - 1; i >= 0; i--, j++) {
1189
527
1190 MPASS(i < 200);
1191 w1 = m1->mtx_witness;
1192 if (isitmydescendant(w, w1)) {
1193 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
528 MPASS(j < WITNESS_COUNT);
529 lock1 = lle->ll_children[i];
530 w1 = lock1->lo_witness;
531
532 /*
533 * If this lock doesn't undergo witness checking,
534 * then skip it.
535 */
536 if (w1 == NULL) {
537 KASSERT((lock1->lo_flags & LO_WITNESS) == 0,
538 ("lock missing witness structure"));
539 continue;
540 }
541 if (!isitmydescendant(w, w1))
542 continue;
543 /*
544 * We have a lock order violation, check to see if it
545 * is allowed or has already been yelled about.
546 */
547 mtx_unlock_spin(&w_mtx);
1194 if (blessed(w, w1))
1195 goto out;
548 if (blessed(w, w1))
549 goto out;
1196 if (m1 == &Giant) {
550 if (lock1 == &Giant.mtx_object) {
1197 if (w1->w_Giant_squawked)
1198 goto out;
1199 else
1200 w1->w_Giant_squawked = 1;
1201 } else {
1202 if (w1->w_other_squawked)
1203 goto out;
1204 else
1205 w1->w_other_squawked = 1;
1206 }
551 if (w1->w_Giant_squawked)
552 goto out;
553 else
554 w1->w_Giant_squawked = 1;
555 } else {
556 if (w1->w_other_squawked)
557 goto out;
558 else
559 w1->w_other_squawked = 1;
560 }
561 /*
562 * Ok, yell about it.
563 */
1207 printf("lock order reversal\n");
564 printf("lock order reversal\n");
1208 printf(" 1st %s last acquired @ %s:%d\n",
1209 w->w_description, w->w_file, w->w_line);
565 /*
566 * Try to locate an earlier lock with
567 * witness w in our list.
568 */
569 do {
570 lock2 = lle->ll_children[i];
571 MPASS(lock2 != NULL);
572 if (lock2->lo_witness == w)
573 break;
574 i--;
575 if (i == 0 && lle->ll_next != NULL) {
576 lle = lle->ll_next;
577 i = lle->ll_count - 1;
578 MPASS(i != 0);
579 }
580 } while (i >= 0);
581 if (i < 0)
582 /*
583 * We are very likely bogus in this case.
584 */
585 printf(" 1st %s last acquired @ %s:%d\n",
586 w->w_name, w->w_file, w->w_line);
587 else
588 printf(" 1st %p %s @ %s:%d\n", lock2,
589 lock2->lo_name, lock2->lo_file,
590 lock2->lo_line);
1210 printf(" 2nd %p %s @ %s:%d\n",
591 printf(" 2nd %p %s @ %s:%d\n",
1211 m1, w1->w_description, w1->w_file, w1->w_line);
592 lock1, lock1->lo_name, lock1->lo_file,
593 lock1->lo_line);
1212 printf(" 3rd %p %s @ %s:%d\n",
594 printf(" 3rd %p %s @ %s:%d\n",
1213 m, w->w_description, file, line);
595 lock, lock->lo_name, file, line);
1214#ifdef DDB
1215 go_into_ddb = 1;
1216#endif /* DDB */
1217 goto out;
1218 }
1219 }
596#ifdef DDB
597 go_into_ddb = 1;
598#endif /* DDB */
599 goto out;
600 }
601 }
1220 m1 = LIST_FIRST(&p->p_heldmtx);
1221 if (!itismychild(m1->mtx_witness, w))
1222 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
602 lock1 = (*lock_list)->ll_children[(*lock_list)->ll_count - 1];
603 if (!itismychild(lock1->lo_witness, w))
604 mtx_unlock_spin(&w_mtx);
1223
1224out:
1225#ifdef DDB
1226 if (witness_ddb && go_into_ddb)
1227 Debugger("witness_enter");
1228#endif /* DDB */
1229 w->w_file = file;
1230 w->w_line = line;
605
606out:
607#ifdef DDB
608 if (witness_ddb && go_into_ddb)
609 Debugger("witness_enter");
610#endif /* DDB */
611 w->w_file = file;
612 w->w_line = line;
1231 m->mtx_line = line;
1232 m->mtx_file = file;
1233
1234 /*
1235 * If this pays off it likely means that a mutex being witnessed
1236 * is acquired in hardclock. Put it in the ignore list. It is
1237 * likely not the mutex this assert fails on.
1238 */
1239 MPASS(m->mtx_held.le_prev == NULL);
1240 LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held);
1241}
1242
1243void
1244witness_try_enter(struct mtx *m, int flags, const char *file, int line)
1245{
1246 struct proc *p;
1247 struct witness *w = m->mtx_witness;
1248
1249 if (witness_cold)
1250 return;
1251 if (panicstr)
1252 return;
1253 if (flags & MTX_SPIN) {
1254 if ((m->mtx_flags & MTX_SPIN) == 0)
1255 panic("mutex_try_enter: "
1256 "MTX_SPIN on MTX_DEF mutex %s @ %s:%d",
1257 m->mtx_description, file, line);
1258 if (mtx_recursed(m)) {
1259 if ((m->mtx_flags & MTX_RECURSE) == 0)
1260 panic("mutex_try_enter: recursion on"
1261 " non-recursive mutex %s @ %s:%d",
1262 m->mtx_description, file, line);
613 lock->lo_line = line;
614 lock->lo_file = file;
615
616 lle = *lock_list;
617 if (lle == NULL || lle->ll_count == LOCK_CHILDCOUNT) {
618 *lock_list = witness_lock_list_get();
619 if (*lock_list == NULL)
1263 return;
620 return;
1264 }
1265 mtx_lock_spin_flags(&w_mtx, MTX_QUIET);
1266 PCPU_SET(witness_spin_check,
1267 PCPU_GET(witness_spin_check) | w->w_level);
1268 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
1269 w->w_file = file;
1270 w->w_line = line;
1271 m->mtx_line = line;
1272 m->mtx_file = file;
1273 return;
621 (*lock_list)->ll_next = lle;
622 lle = *lock_list;
1274 }
623 }
1275
1276 if ((m->mtx_flags & MTX_SPIN) != 0)
1277 panic("mutex_try_enter: MTX_DEF on MTX_SPIN mutex %s @ %s:%d",
1278 m->mtx_description, file, line);
1279
1280 if (mtx_recursed(m)) {
1281 if ((m->mtx_flags & MTX_RECURSE) == 0)
1282 panic("mutex_try_enter: recursion on non-recursive"
1283 " mutex %s @ %s:%d", m->mtx_description, file,
1284 line);
1285 return;
1286 }
1287 w->w_file = file;
1288 w->w_line = line;
1289 m->mtx_line = line;
1290 m->mtx_file = file;
1291 p = curproc;
1292 MPASS(m->mtx_held.le_prev == NULL);
1293 LIST_INSERT_HEAD(&p->p_heldmtx, (struct mtx*)m, mtx_held);
624 lle->ll_children[lle->ll_count++] = lock;
1294}
1295
1296void
625}
626
627void
1297witness_exit(struct mtx *m, int flags, const char *file, int line)
628witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
1298{
629{
1299 struct witness *w;
630 struct lock_list_entry **lock_list, *lle;
631 struct lock_class *class;
1300 struct proc *p;
632 struct proc *p;
633 int i, j;
1301
634
1302 if (witness_cold || m->mtx_witness == NULL || panicstr)
635 if (witness_cold || witness_dead || lock->lo_witness == NULL ||
636 panicstr)
1303 return;
637 return;
1304 w = m->mtx_witness;
1305 p = curproc;
638 p = curproc;
639 class = lock->lo_class;
1306
640
1307 if (flags & MTX_SPIN) {
1308 if ((m->mtx_flags & MTX_SPIN) == 0)
1309 panic("mutex_exit: MTX_SPIN on MTX_DEF mutex %s @"
1310 " %s:%d", m->mtx_description, file, line);
1311 if (mtx_recursed(m)) {
1312 if ((m->mtx_flags & MTX_RECURSE) == 0)
1313 panic("mutex_exit: recursion on non-recursive"
1314 " mutex %s @ %s:%d", m->mtx_description,
1315 file, line);
1316 return;
1317 }
1318 mtx_lock_spin_flags(&w_mtx, MTX_QUIET);
1319 PCPU_SET(witness_spin_check,
1320 PCPU_GET(witness_spin_check) & ~w->w_level);
1321 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
1322 MPASS(p->p_spinlocks > 0);
1323 p->p_spinlocks--;
641 if (lock->lo_flags & LO_RECURSED) {
642 if ((lock->lo_flags & LO_LOCKED) == 0)
643 panic("%s: recursed lock (%s) %s is not locked @ %s:%d",
644 __func__, class->lc_name, lock->lo_name, file,
645 line);
1324 return;
1325 }
646 return;
647 }
1326 if ((m->mtx_flags & MTX_SPIN) != 0)
1327 panic("mutex_exit: MTX_DEF on MTX_SPIN mutex %s @ %s:%d",
1328 m->mtx_description, file, line);
1329
648
1330 if (mtx_recursed(m)) {
1331 if ((m->mtx_flags & MTX_RECURSE) == 0)
1332 panic("mutex_exit: recursion on non-recursive"
1333 " mutex %s @ %s:%d", m->mtx_description,
1334 file, line);
1335 return;
1336 }
649 /*
650 * We don't need to protect this PCPU_GET() here against preemption
651 * because if we hold any spinlocks then we are already protected,
652 * and if we don't we will get NULL if we hold no spinlocks even if
653 * we switch CPU's while reading it.
654 */
655 if (class->lc_flags & LC_SLEEPLOCK) {
656 if ((flags & LOP_NOSWITCH) == 0 && PCPU_GET(spinlocks) != NULL)
657 panic("switchable sleep unlock (%s) %s @ %s:%d",
658 class->lc_name, lock->lo_name, file, line);
659 lock_list = &p->p_sleeplocks;
660 } else
661 lock_list = PCPU_PTR(spinlocks);
1337
662
1338 if ((flags & MTX_NOSWITCH) == 0 && p->p_spinlocks != 0 && !cold)
1339 panic("switchable mtx_unlock() of %s when not legal @ %s:%d",
1340 m->mtx_description, file, line);
1341 LIST_REMOVE(m, mtx_held);
1342 m->mtx_held.le_prev = NULL;
663 for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
664 for (i = 0; i < (*lock_list)->ll_count; i++)
665 if ((*lock_list)->ll_children[i] == lock) {
666 (*lock_list)->ll_count--;
667 for (j = i; j < (*lock_list)->ll_count; j++)
668 (*lock_list)->ll_children[j] =
669 (*lock_list)->ll_children[j + 1];
670 if ((*lock_list)->ll_count == 0) {
671 lle = *lock_list;
672 *lock_list = lle->ll_next;
673 witness_lock_list_free(lle);
674 }
675 return;
676 }
1343}
1344
677}
678
679/*
680 * Warn if any held locks are not sleepable. Note that Giant and the lock
681 * passed in are both special cases since they are both released during the
682 * sleep process and aren't actually held while the process is asleep.
683 */
1345int
684int
1346witness_sleep(int check_only, struct mtx *mtx, const char *file, int line)
685witness_sleep(int check_only, struct lock_object *lock, const char *file,
686 int line)
1347{
687{
1348 struct mtx *m;
688 struct lock_list_entry **lock_list, *lle;
689 struct lock_object *lock1;
1349 struct proc *p;
690 struct proc *p;
1350 char **sleep;
1351 int n = 0;
691 critical_t savecrit;
692 int i, n;
1352
693
1353 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__));
694 if (witness_dead || panicstr)
695 return (0);
696 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
697 n = 0;
698 /*
699 * Preemption bad because we need PCPU_PTR(spinlocks) to not change.
700 */
701 savecrit = critical_enter();
1354 p = curproc;
702 p = curproc;
1355 LIST_FOREACH(m, &p->p_heldmtx, mtx_held) {
1356 if (m == mtx)
1357 continue;
1358 for (sleep = sleep_list; *sleep!= NULL; sleep++)
1359 if (strcmp(m->mtx_description, *sleep) == 0)
1360 goto next;
1361 if (n == 0)
1362 printf("Whee!\n");
1363 printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
1364 file, line, check_only ? "could sleep" : "sleeping",
1365 m->mtx_description,
1366 m->mtx_witness->w_file, m->mtx_witness->w_line);
1367 n++;
1368 next:
703 lock_list = &p->p_sleeplocks;
704again:
705 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
706 for (i = lle->ll_count - 1; i >= 0; i--) {
707 lock1 = lle->ll_children[i];
708 if (lock1 == lock || lock1 == &Giant.mtx_object ||
709 (lock1->lo_flags & LO_SLEEPABLE))
710 continue;
711 n++;
712 printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
713 file, line, check_only ? "could sleep" : "sleeping",
714 lock1->lo_name, lock1->lo_file, lock1->lo_line);
715 }
716 if (lock_list == &p->p_sleeplocks) {
717 lock_list = PCPU_PTR(spinlocks);
718 goto again;
1369 }
1370#ifdef DDB
1371 if (witness_ddb && n)
1372 Debugger("witness_sleep");
1373#endif /* DDB */
719 }
720#ifdef DDB
721 if (witness_ddb && n)
722 Debugger("witness_sleep");
723#endif /* DDB */
724 critical_exit(savecrit);
1374 return (n);
1375}
1376
1377static struct witness *
725 return (n);
726}
727
728static struct witness *
1378enroll(const char *description, int flag)
729enroll(const char *description, struct lock_class *lock_class)
1379{
730{
1380 int i;
1381 struct witness *w, *w1;
1382 char **ignore;
1383 char **order;
731 struct witness *w;
1384
1385 if (!witness_watch)
1386 return (NULL);
732
733 if (!witness_watch)
734 return (NULL);
1387 for (ignore = ignore_list; *ignore != NULL; ignore++)
1388 if (strcmp(description, *ignore) == 0)
1389 return (NULL);
1390
735
1391 if (w_inited == 0) {
1392 mtx_init(&w_mtx, "witness lock", MTX_SPIN);
1393 for (i = 0; i < WITNESS_COUNT; i++) {
1394 w = &w_data[i];
1395 witness_free(w);
1396 }
1397 w_inited = 1;
1398 for (order = order_list; *order != NULL; order++) {
1399 w = enroll(*order, MTX_DEF);
1400 w->w_file = "order list";
1401 for (order++; *order != NULL; order++) {
1402 w1 = enroll(*order, MTX_DEF);
1403 w1->w_file = "order list";
1404 itismychild(w, w1);
1405 w = w1;
1406 }
1407 }
1408 }
1409 if ((flag & MTX_SPIN) && witness_skipspin)
736 if ((lock_class->lc_flags & LC_SPINLOCK) && witness_skipspin)
1410 return (NULL);
737 return (NULL);
1411 mtx_lock_spin_flags(&w_mtx, MTX_QUIET);
1412 for (w = w_all; w; w = w->w_next) {
1413 if (strcmp(description, w->w_description) == 0) {
1414 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
738 mtx_lock_spin(&w_mtx);
739 STAILQ_FOREACH(w, &w_all, w_list) {
740 if (strcmp(description, w->w_name) == 0) {
741 mtx_unlock_spin(&w_mtx);
742 if (lock_class != w->w_class)
743 panic(
744 "lock (%s) %s does not match earlier (%s) lock",
745 description, lock_class->lc_name,
746 w->w_class->lc_name);
1415 return (w);
1416 }
1417 }
747 return (w);
748 }
749 }
750 /*
751 * This isn't quite right, as witness_cold is still 0 while we
752 * enroll all the locks initialized before witness_initialize().
753 */
754 if ((lock_class->lc_flags & LC_SPINLOCK) && !witness_cold)
755 panic("spin lock %s not in order list", description);
1418 if ((w = witness_get()) == NULL)
1419 return (NULL);
756 if ((w = witness_get()) == NULL)
757 return (NULL);
1420 w->w_next = w_all;
1421 w_all = w;
1422 w->w_description = description;
1423 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
1424 if (flag & MTX_SPIN) {
1425 w->w_spin = 1;
1426
1427 i = 1;
1428 for (order = spin_order_list; *order != NULL; order++) {
1429 if (strcmp(description, *order) == 0)
1430 break;
1431 i <<= 1;
1432 }
1433 if (*order == NULL)
1434 panic("spin lock %s not in order list", description);
1435 w->w_level = i;
1436 }
758 w->w_name = description;
759 w->w_class = lock_class;
760 STAILQ_INSERT_HEAD(&w_all, w, w_list);
761 if (lock_class->lc_flags & LC_SPINLOCK)
762 STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
763 else if (lock_class->lc_flags & LC_SLEEPLOCK)
764 STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
765 else
766 panic("lock class %s is not sleep or spin",
767 lock_class->lc_name);
768 mtx_unlock_spin(&w_mtx);
1437
1438 return (w);
1439}
1440
1441static int
1442itismychild(struct witness *parent, struct witness *child)
1443{
1444 static int recursed;
769
770 return (w);
771}
772
773static int
774itismychild(struct witness *parent, struct witness *child)
775{
776 static int recursed;
777 struct witness_child_list_entry **wcl;
778 struct witness_list *list;
1445
779
780 MPASS(child != NULL && parent != NULL);
781 if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
782 (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
783 panic(
784 "%s: parent (%s) and child (%s) are not the same lock type",
785 __func__, parent->w_class->lc_name,
786 child->w_class->lc_name);
787
1446 /*
1447 * Insert "child" after "parent"
1448 */
788 /*
789 * Insert "child" after "parent"
790 */
1449 while (parent->w_morechildren)
1450 parent = parent->w_morechildren;
791 wcl = &parent->w_children;
792 while (*wcl != NULL && (*wcl)->wcl_count == WITNESS_NCHILDREN)
793 wcl = &(*wcl)->wcl_next;
1451
794
1452 if (parent->w_childcnt == WITNESS_NCHILDREN) {
1453 if ((parent->w_morechildren = witness_get()) == NULL)
795 if (*wcl == NULL) {
796 *wcl = witness_child_get();
797 if (*wcl == NULL)
1454 return (1);
798 return (1);
1455 parent = parent->w_morechildren;
1456 }
799 }
1457 MPASS(child != NULL);
1458 parent->w_children[parent->w_childcnt++] = child;
800
801 (*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
802
1459 /*
803 /*
1460 * now prune whole tree
804 * Now prune whole tree. We look for cases where a lock is now
805 * both a descendant and a direct child of a given lock. In that
806 * case, we want to remove the direct child link from the tree.
1461 */
1462 if (recursed)
1463 return (0);
1464 recursed = 1;
807 */
808 if (recursed)
809 return (0);
810 recursed = 1;
1465 for (child = w_all; child != NULL; child = child->w_next) {
1466 for (parent = w_all; parent != NULL;
1467 parent = parent->w_next) {
811 if (parent->w_class->lc_flags & LC_SLEEPLOCK)
812 list = &w_sleep;
813 else
814 list = &w_spin;
815 STAILQ_FOREACH(child, list, w_typelist) {
816 STAILQ_FOREACH(parent, list, w_typelist) {
1468 if (!isitmychild(parent, child))
1469 continue;
1470 removechild(parent, child);
1471 if (isitmydescendant(parent, child))
1472 continue;
1473 itismychild(parent, child);
1474 }
1475 }
1476 recursed = 0;
1477 witness_levelall();
1478 return (0);
1479}
1480
1481static void
1482removechild(struct witness *parent, struct witness *child)
1483{
817 if (!isitmychild(parent, child))
818 continue;
819 removechild(parent, child);
820 if (isitmydescendant(parent, child))
821 continue;
822 itismychild(parent, child);
823 }
824 }
825 recursed = 0;
826 witness_levelall();
827 return (0);
828}
829
830static void
831removechild(struct witness *parent, struct witness *child)
832{
1484 struct witness *w, *w1;
833 struct witness_child_list_entry **wcl, *wcl1;
1485 int i;
1486
834 int i;
835
1487 for (w = parent; w != NULL; w = w->w_morechildren)
1488 for (i = 0; i < w->w_childcnt; i++)
1489 if (w->w_children[i] == child)
836 for (wcl = &parent->w_children; *wcl != NULL; wcl = &(*wcl)->wcl_next)
837 for (i = 0; i < (*wcl)->wcl_count; i++)
838 if ((*wcl)->wcl_children[i] == child)
1490 goto found;
1491 return;
1492found:
839 goto found;
840 return;
841found:
1493 for (w1 = w; w1->w_morechildren != NULL; w1 = w1->w_morechildren)
1494 continue;
1495 w->w_children[i] = w1->w_children[--w1->w_childcnt];
1496 MPASS(w->w_children[i] != NULL);
842 (*wcl)->wcl_count--;
843 if ((*wcl)->wcl_count > i)
844 (*wcl)->wcl_children[i] =
845 (*wcl)->wcl_children[(*wcl)->wcl_count];
846 MPASS((*wcl)->wcl_children[i] != NULL);
1497
847
1498 if (w1->w_childcnt != 0)
848 if ((*wcl)->wcl_count != 0)
1499 return;
1500
849 return;
850
1501 if (w1 == parent)
1502 return;
1503 for (w = parent; w->w_morechildren != w1; w = w->w_morechildren)
1504 continue;
1505 w->w_morechildren = 0;
1506 witness_free(w1);
851 wcl1 = *wcl;
852 *wcl = wcl1->wcl_next;
853 witness_child_free(wcl1);
1507}
1508
1509static int
1510isitmychild(struct witness *parent, struct witness *child)
1511{
854}
855
856static int
857isitmychild(struct witness *parent, struct witness *child)
858{
1512 struct witness *w;
859 struct witness_child_list_entry *wcl;
1513 int i;
1514
860 int i;
861
1515 for (w = parent; w != NULL; w = w->w_morechildren) {
1516 for (i = 0; i < w->w_childcnt; i++) {
1517 if (w->w_children[i] == child)
862 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
863 for (i = 0; i < wcl->wcl_count; i++) {
864 if (wcl->wcl_children[i] == child)
1518 return (1);
1519 }
1520 }
1521 return (0);
1522}
1523
1524static int
1525isitmydescendant(struct witness *parent, struct witness *child)
1526{
865 return (1);
866 }
867 }
868 return (0);
869}
870
871static int
872isitmydescendant(struct witness *parent, struct witness *child)
873{
1527 struct witness *w;
1528 int i;
1529 int j;
874 struct witness_child_list_entry *wcl;
875 int i, j;
1530
876
1531 for (j = 0, w = parent; w != NULL; w = w->w_morechildren, j++) {
877 if (isitmychild(parent, child))
878 return (1);
879 j = 0;
880 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next) {
1532 MPASS(j < 1000);
881 MPASS(j < 1000);
1533 for (i = 0; i < w->w_childcnt; i++) {
1534 if (w->w_children[i] == child)
882 for (i = 0; i < wcl->wcl_count; i++) {
883 if (isitmydescendant(wcl->wcl_children[i], child))
1535 return (1);
1536 }
884 return (1);
885 }
1537 for (i = 0; i < w->w_childcnt; i++) {
1538 if (isitmydescendant(w->w_children[i], child))
1539 return (1);
1540 }
886 j++;
1541 }
1542 return (0);
1543}
1544
1545void
1546witness_levelall (void)
1547{
887 }
888 return (0);
889}
890
891void
892witness_levelall (void)
893{
894 struct witness_list *list;
1548 struct witness *w, *w1;
1549
895 struct witness *w, *w1;
896
1550 for (w = w_all; w; w = w->w_next)
1551 if (!(w->w_spin))
1552 w->w_level = 0;
1553 for (w = w_all; w; w = w->w_next) {
1554 if (w->w_spin)
1555 continue;
1556 for (w1 = w_all; w1; w1 = w1->w_next) {
897 /*
898 * First clear all levels.
899 */
900 STAILQ_FOREACH(w, &w_all, w_list) {
901 w->w_level = 0;
902 }
903
904 /*
905 * Look for locks with no parent and level all their descendants.
906 */
907 STAILQ_FOREACH(w, &w_all, w_list) {
908 /*
909 * This is just an optimization, technically we could get
910 * away just walking the all list each time.
911 */
912 if (w->w_class->lc_flags & LC_SLEEPLOCK)
913 list = &w_sleep;
914 else
915 list = &w_spin;
916 STAILQ_FOREACH(w1, list, w_typelist) {
1557 if (isitmychild(w1, w))
917 if (isitmychild(w1, w))
1558 break;
918 goto skip;
1559 }
919 }
1560 if (w1 != NULL)
1561 continue;
1562 witness_leveldescendents(w, 0);
920 witness_leveldescendents(w, 0);
921 skip:
1563 }
1564}
1565
1566static void
1567witness_leveldescendents(struct witness *parent, int level)
1568{
922 }
923}
924
925static void
926witness_leveldescendents(struct witness *parent, int level)
927{
928 struct witness_child_list_entry *wcl;
1569 int i;
929 int i;
1570 struct witness *w;
1571
1572 if (parent->w_level < level)
1573 parent->w_level = level;
1574 level++;
930
931 if (parent->w_level < level)
932 parent->w_level = level;
933 level++;
1575 for (w = parent; w != NULL; w = w->w_morechildren)
1576 for (i = 0; i < w->w_childcnt; i++)
1577 witness_leveldescendents(w->w_children[i], level);
934 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
935 for (i = 0; i < wcl->wcl_count; i++)
936 witness_leveldescendents(wcl->wcl_children[i], level);
1578}
1579
1580static void
1581witness_displaydescendants(void(*prnt)(const char *fmt, ...),
1582 struct witness *parent)
1583{
937}
938
939static void
940witness_displaydescendants(void(*prnt)(const char *fmt, ...),
941 struct witness *parent)
942{
1584 struct witness *w;
1585 int i;
1586 int level;
943 struct witness_child_list_entry *wcl;
944 int i, level;
1587
945
1588 level = parent->w_spin ? ffs(parent->w_level) : parent->w_level;
946 level = parent->w_level;
1589
947
1590 prnt("%d", level);
1591 if (level < 10)
1592 prnt(" ");
948 prnt("%-2d", level);
1593 for (i = 0; i < level; i++)
1594 prnt(" ");
949 for (i = 0; i < level; i++)
950 prnt(" ");
1595 prnt("%s", parent->w_description);
951 prnt("%s", parent->w_name);
1596 if (parent->w_file != NULL)
1597 prnt(" -- last acquired @ %s:%d\n", parent->w_file,
1598 parent->w_line);
1599
952 if (parent->w_file != NULL)
953 prnt(" -- last acquired @ %s:%d\n", parent->w_file,
954 parent->w_line);
955
1600 for (w = parent; w != NULL; w = w->w_morechildren)
1601 for (i = 0; i < w->w_childcnt; i++)
1602 witness_displaydescendants(prnt, w->w_children[i]);
1603 }
956 for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
957 for (i = 0; i < wcl->wcl_count; i++)
958 witness_displaydescendants(prnt,
959 wcl->wcl_children[i]);
960}
1604
1605static int
1606dup_ok(struct witness *w)
1607{
961
962static int
963dup_ok(struct witness *w)
964{
1608 char **dup;
965 const char **dup;
1609
966
1610 for (dup = dup_list; *dup!= NULL; dup++)
1611 if (strcmp(w->w_description, *dup) == 0)
967 for (dup = dup_list; *dup != NULL; dup++)
968 if (strcmp(w->w_name, *dup) == 0)
1612 return (1);
1613 return (0);
1614}
1615
1616static int
1617blessed(struct witness *w1, struct witness *w2)
1618{
1619 int i;
1620 struct witness_blessed *b;
1621
1622 for (i = 0; i < blessed_count; i++) {
1623 b = &blessed_list[i];
969 return (1);
970 return (0);
971}
972
973static int
974blessed(struct witness *w1, struct witness *w2)
975{
976 int i;
977 struct witness_blessed *b;
978
979 for (i = 0; i < blessed_count; i++) {
980 b = &blessed_list[i];
1624 if (strcmp(w1->w_description, b->b_lock1) == 0) {
1625 if (strcmp(w2->w_description, b->b_lock2) == 0)
981 if (strcmp(w1->w_name, b->b_lock1) == 0) {
982 if (strcmp(w2->w_name, b->b_lock2) == 0)
1626 return (1);
1627 continue;
1628 }
983 return (1);
984 continue;
985 }
1629 if (strcmp(w1->w_description, b->b_lock2) == 0)
1630 if (strcmp(w2->w_description, b->b_lock1) == 0)
986 if (strcmp(w1->w_name, b->b_lock2) == 0)
987 if (strcmp(w2->w_name, b->b_lock1) == 0)
1631 return (1);
1632 }
1633 return (0);
1634}
1635
1636static struct witness *
988 return (1);
989 }
990 return (0);
991}
992
993static struct witness *
1637witness_get()
994witness_get(void)
1638{
1639 struct witness *w;
1640
995{
996 struct witness *w;
997
1641 if ((w = w_free) == NULL) {
998 if (STAILQ_EMPTY(&w_free)) {
1642 witness_dead = 1;
999 witness_dead = 1;
1643 mtx_unlock_spin_flags(&w_mtx, MTX_QUIET);
1644 printf("witness exhausted\n");
1000 mtx_unlock_spin(&w_mtx);
1001 printf("%s: witness exhausted\n", __func__);
1645 return (NULL);
1646 }
1002 return (NULL);
1003 }
1647 w_free = w->w_next;
1004 w = STAILQ_FIRST(&w_free);
1005 STAILQ_REMOVE_HEAD(&w_free, w_list);
1648 bzero(w, sizeof(*w));
1649 return (w);
1650}
1651
1652static void
1653witness_free(struct witness *w)
1654{
1006 bzero(w, sizeof(*w));
1007 return (w);
1008}
1009
1010static void
1011witness_free(struct witness *w)
1012{
1655 w->w_next = w_free;
1656 w_free = w;
1013
1014 STAILQ_INSERT_HEAD(&w_free, w, w_list);
1657}
1658
1015}
1016
1659int
1660witness_list(struct proc *p)
1017static struct witness_child_list_entry *
1018witness_child_get(void)
1661{
1019{
1662 struct mtx *m;
1663 int nheld;
1020 struct witness_child_list_entry *wcl;
1664
1021
1665 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__));
1666 nheld = 0;
1667 LIST_FOREACH(m, &p->p_heldmtx, mtx_held) {
1668 printf("\t\"%s\" (%p) locked at %s:%d\n",
1669 m->mtx_description, m,
1670 m->mtx_witness->w_file, m->mtx_witness->w_line);
1671 nheld++;
1022 wcl = w_child_free;
1023 if (wcl == NULL) {
1024 witness_dead = 1;
1025 mtx_unlock_spin(&w_mtx);
1026 printf("%s: witness exhausted\n", __func__);
1027 return (NULL);
1672 }
1028 }
1029 w_child_free = wcl->wcl_next;
1030 bzero(wcl, sizeof(*wcl));
1031 return (wcl);
1032}
1673
1033
1674 return (nheld);
1034static void
1035witness_child_free(struct witness_child_list_entry *wcl)
1036{
1037
1038 wcl->wcl_next = w_child_free;
1039 w_child_free = wcl;
1675}
1676
1040}
1041
1677#ifdef DDB
1042static struct lock_list_entry *
1043witness_lock_list_get(void)
1044{
1045 struct lock_list_entry *lle;
1678
1046
1679DB_SHOW_COMMAND(mutexes, db_witness_list)
1047 mtx_lock_spin(&w_mtx);
1048 lle = w_lock_list_free;
1049 if (lle == NULL) {
1050 witness_dead = 1;
1051 mtx_unlock_spin(&w_mtx);
1052 printf("%s: witness exhausted\n", __func__);
1053 return (NULL);
1054 }
1055 w_lock_list_free = lle->ll_next;
1056 mtx_unlock_spin(&w_mtx);
1057 bzero(lle, sizeof(*lle));
1058 return (lle);
1059}
1060
1061static void
1062witness_lock_list_free(struct lock_list_entry *lle)
1680{
1681
1063{
1064
1682 witness_list(curproc);
1065 mtx_lock_spin(&w_mtx);
1066 lle->ll_next = w_lock_list_free;
1067 w_lock_list_free = lle;
1068 mtx_unlock_spin(&w_mtx);
1683}
1684
1069}
1070
1685DB_SHOW_COMMAND(witness, db_witness_display)
1071/*
1072 * Calling this on p != curproc is bad unless we are in ddb.
1073 */
1074int
1075witness_list(struct proc *p)
1686{
1076{
1077 struct lock_list_entry **lock_list, *lle;
1078 struct lock_object *lock;
1079 critical_t savecrit;
1080 int i, nheld;
1687
1081
1688 witness_display(db_printf);
1082 KASSERT(p == curproc || db_active,
1083 ("%s: p != curproc and we aren't in the debugger", __func__));
1084 KASSERT(!witness_cold, ("%s: witness_cold", __func__));
1085 nheld = 0;
1086 /*
1087 * Preemption bad because we need PCPU_PTR(spinlocks) to not change.
1088 */
1089 savecrit = critical_enter();
1090 lock_list = &p->p_sleeplocks;
1091again:
1092 for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
1093 for (i = lle->ll_count - 1; i >= 0; i--) {
1094 lock = lle->ll_children[i];
1095 printf("\t(%s) %s (%p) locked at %s:%d\n",
1096 lock->lo_class->lc_name, lock->lo_name, lock,
1097 lock->lo_file, lock->lo_line);
1098 nheld++;
1099 }
1100 /*
1101 * We only handle spinlocks if p == curproc. This is somewhat broken
1102 * if p is currently executing on some other CPU and holds spin locks
1103 * as we won't display those locks.
1104 */
1105 if (lock_list == &p->p_sleeplocks && p == curproc) {
1106 lock_list = PCPU_PTR(spinlocks);
1107 goto again;
1108 }
1109 critical_exit(savecrit);
1110
1111 return (nheld);
1689}
1112}
1690#endif
1691
1692void
1113
1114void
1693witness_save(struct mtx *m, const char **filep, int *linep)
1115witness_save(struct lock_object *lock, const char **filep, int *linep)
1694{
1695
1116{
1117
1696 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__));
1697 if (m->mtx_witness == NULL)
1118 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
1119 if (lock->lo_witness == NULL)
1698 return;
1699
1120 return;
1121
1700 *filep = m->mtx_witness->w_file;
1701 *linep = m->mtx_witness->w_line;
1122 *filep = lock->lo_file;
1123 *linep = lock->lo_line;
1702}
1703
1704void
1124}
1125
1126void
1705witness_restore(struct mtx *m, const char *file, int line)
1127witness_restore(struct lock_object *lock, const char *file, int line)
1706{
1707
1128{
1129
1708 KASSERT(!witness_cold, ("%s: witness_cold\n", __FUNCTION__));
1709 if (m->mtx_witness == NULL)
1130 KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
1131 if (lock->lo_witness == NULL)
1710 return;
1711
1132 return;
1133
1712 m->mtx_witness->w_file = file;
1713 m->mtx_witness->w_line = line;
1134 lock->lo_witness->w_file = file;
1135 lock->lo_witness->w_line = line;
1136 lock->lo_file = file;
1137 lock->lo_line = line;
1714}
1715
1138}
1139
1716#endif /* WITNESS */
1140#ifdef DDB
1141
1142DB_SHOW_COMMAND(mutexes, db_witness_list)
1143{
1144
1145 witness_list(curproc);
1146}
1147
1148DB_SHOW_COMMAND(witness, db_witness_display)
1149{
1150
1151 witness_display(db_printf);
1152}
1153#endif