1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
45  *	Pronunciation: 'wit-n&s
59  *	      life -- Pilot>
79  * a sleepable lock because it is a non-sleepable lock and non-sleepable
162 #define	WITNESS_PARENT		0x01	/* Parent, aka direct ancestor. */
189  * are held in a per-cpu list while sleep locks are held in per-thread list.
205  * when we traverse the list we read children[count-1] as the first entry
294 	return ((w1->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) ==  in witness_lock_type_equal()
295 		(w2->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)));  in witness_lock_type_equal()
302 	return (a->from == b->from && a->to == b->to);  in witness_lock_order_key_equal()
307 static void	adopt(struct witness *parent, struct witness *child);
314 static int	isitmychild(struct witness *parent, struct witness *child);
315 static int	isitmydescendant(struct witness *parent, struct witness *child);
316 static void	itismychild(struct witness *parent, struct witness *child);
321 static void	witness_add_fullgraph(struct sbuf *sb, struct witness *parent);
329 static void	witness_ddb_level_descendants(struct witness *parent, int l);
343 static int	witness_lock_order_add(struct witness *parent,
345 static int	witness_lock_order_check(struct witness *parent,
348 					    struct witness *parent,
364  * If set to 0, lock order checking is disabled.  If set to -1,
380  *	- a lock hierarchy violation occurs
381  *	- locks are held when going to sleep.
395  *	- a lock hierarchy violation occurs
396  *	- locks are held when going to sleep.
500 	{ "pmc-sleep", &lock_class_mtx_sleep },
637 	{ "dn->dn_mtx", &lock_class_sx },
638 	{ "dr->dt.di.dr_mtx", &lock_class_sx },
639 	{ "db->db_mtx", &lock_class_sx },
682 	{ "pmc-per-proc", &lock_class_mtx_spin },
709 	{ "pmc-leaf", &lock_class_mtx_spin },
730 	 * A UFS vnode may be locked in vget() while a buffer belonging to the
731 	 * parent directory vnode is locked.
736 	 * The tarfs decompression stream vnode may be locked while a
737 	 * buffer belonging to a tarfs data vnode is locked.
781  * The WITNESS-enabled diagnostic code.  Note that the witness code does
782  * assume that the early boot is single-threaded at least until after this
817 	for (i = witness_count - 1; i >= 0; i--) {  in witness_startup()
823 	KASSERT(STAILQ_FIRST(&w_free)->w_index == 0,  in witness_startup()
828 	w_free_cnt--;  in witness_startup()
840 	for (order = order_lists; order->w_name != NULL; order++) {  in witness_startup()
841 		w = enroll(order->w_name, order->w_class);  in witness_startup()
844 		w->w_file = "order list";  in witness_startup()
845 		for (order++; order->w_name != NULL; order++) {  in witness_startup()
846 			w1 = enroll(order->w_name, order->w_class);  in witness_startup()
849 			w1->w_file = "order list";  in witness_startup()
859 		KASSERT(lock->lo_flags & LO_WITNESS,  in witness_startup()
861 		    __func__, lock->lo_name));  in witness_startup()
862 		lock->lo_witness = enroll(pending_locks[i].wh_type,  in witness_startup()
879 	if ((lock->lo_flags & LO_RECURSABLE) != 0 &&  in witness_init()
880 	    (class->lc_flags & LC_RECURSABLE) == 0)  in witness_init()
882 		    __func__, class->lc_name, lock->lo_name);  in witness_init()
883 	if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&  in witness_init()
884 	    (class->lc_flags & LC_SLEEPABLE) == 0)  in witness_init()
886 		    __func__, class->lc_name, lock->lo_name);  in witness_init()
887 	if ((lock->lo_flags & LO_UPGRADABLE) != 0 &&  in witness_init()
888 	    (class->lc_flags & LC_UPGRADABLE) == 0)  in witness_init()
890 		    __func__, class->lc_name, lock->lo_name);  in witness_init()
900 	    (lock->lo_flags & LO_WITNESS) == 0)  in witness_init()
901 		lock->lo_witness = NULL;  in witness_init()
910 		lock->lo_witness = enroll(type, class);  in witness_init()
923 		    class->lc_name, lock->lo_name);  in witness_destroy()
926 	if ((lock->lo_flags & LO_WITNESS) == 0 || lock->lo_witness == NULL)  in witness_destroy()
928 	w = lock->lo_witness;  in witness_destroy()
931 	MPASS(w->w_refcount > 0);  in witness_destroy()
932 	w->w_refcount--;  in witness_destroy()
934 	if (w->w_refcount == 0)  in witness_destroy()
949 		w->w_ddb_level = -1;  in witness_ddb_compute_levels()
956 		if (w->w_num_ancestors > 0)  in witness_ddb_compute_levels()
967 	if (w->w_ddb_level >= l)  in witness_ddb_level_descendants()
970 	w->w_ddb_level = l;  in witness_ddb_level_descendants()
974 		if (w_rmatrix[w->w_index][i] & WITNESS_PARENT)  in witness_ddb_level_descendants()
988 	     w->w_name, w->w_class->lc_name,  in witness_ddb_display_descendants()
989 	     w->w_ddb_level, w->w_refcount);  in witness_ddb_display_descendants()
990 	if (w->w_displayed) {  in witness_ddb_display_descendants()
991 		prnt(" -- (already displayed)\n");  in witness_ddb_display_descendants()
994 	w->w_displayed = 1;  in witness_ddb_display_descendants()
995 	if (w->w_file != NULL && w->w_line != 0)  in witness_ddb_display_descendants()
996 		prnt(" -- last acquired @ %s:%d\n", fixup_filename(w->w_file),  in witness_ddb_display_descendants()
997 		    w->w_line);  in witness_ddb_display_descendants()
999 		prnt(" -- never acquired\n");  in witness_ddb_display_descendants()
1001 	WITNESS_INDEX_ASSERT(w->w_index);  in witness_ddb_display_descendants()
1005 		if (w_rmatrix[w->w_index][i] & WITNESS_PARENT)  in witness_ddb_display_descendants()
1018 		if (w->w_file == NULL || w->w_ddb_level > 0)  in witness_ddb_display_list()
1021 		/* This lock has no anscestors - display its descendants. */  in witness_ddb_display_list()
1038 		w->w_displayed = 0;  in witness_ddb_display()
1062 		if (w->w_file != NULL || w->w_refcount == 0)  in witness_ddb_display()
1064 		prnt("%s (type: %s, depth: %d)\n", w->w_name,  in witness_ddb_display()
1065 		    w->w_class->lc_name, w->w_ddb_level);  in witness_ddb_display()
1075 	if (witness_watch == -1 || KERNEL_PANICKED())  in witness_defineorder()
1079 	if (lock1 == NULL || lock1->lo_witness == NULL || lock2 == NULL ||  in witness_defineorder()
1080 	    lock2->lo_witness == NULL)  in witness_defineorder()
1091 	    isitmydescendant(lock2->lo_witness, lock1->lo_witness)) {  in witness_defineorder()
1098 	    lock2->lo_witness->w_name, lock1->lo_witness->w_name);  in witness_defineorder()
1099 	itismychild(lock1->lo_witness, lock2->lo_witness);  in witness_defineorder()
1115 	if (witness_cold || witness_watch < 1 || lock->lo_witness == NULL ||  in witness_checkorder()
1119 	w = lock->lo_witness;  in witness_checkorder()
1123 	if (class->lc_flags & LC_SLEEPLOCK) {  in witness_checkorder()
1129 		if (td->td_critnest != 0 && !kdb_active)  in witness_checkorder()
1132 			    class->lc_name, lock->lo_name,  in witness_checkorder()
1139 		lock_list = td->td_sleeplocks;  in witness_checkorder()
1140 		if (lock_list == NULL || lock_list->ll_count == 0)  in witness_checkorder()
1153 		if (lock_list == NULL || lock_list->ll_count == 0) {  in witness_checkorder()
1167 		if ((lock1->li_flags & LI_EXCLUSIVE) != 0 &&  in witness_checkorder()
1170 			    class->lc_name, lock->lo_name,  in witness_checkorder()
1172 			witness_output("while exclusively locked from %s:%d\n",  in witness_checkorder()
1173 			    fixup_filename(lock1->li_file), lock1->li_line);  in witness_checkorder()
1174 			kassert_panic("excl->share");  in witness_checkorder()
1176 		if ((lock1->li_flags & LI_EXCLUSIVE) == 0 &&  in witness_checkorder()
1179 			    class->lc_name, lock->lo_name,  in witness_checkorder()
1181 			witness_output("while share locked from %s:%d\n",  in witness_checkorder()
1182 			    fixup_filename(lock1->li_file), lock1->li_line);  in witness_checkorder()
1183 			kassert_panic("share->excl");  in witness_checkorder()
1188 	/* Warn if the interlock is not locked exactly once. */  in witness_checkorder()
1193 			kassert_panic("interlock (%s) %s not locked @ %s:%d",  in witness_checkorder()
1194 			    iclass->lc_name, interlock->lo_name,  in witness_checkorder()
1196 		else if ((lock1->li_flags & LI_RECURSEMASK) != 0)  in witness_checkorder()
1198 			    iclass->lc_name, interlock->lo_name,  in witness_checkorder()
1205 	plock = &lock_list->ll_children[lock_list->ll_count - 1];  in witness_checkorder()
1206 	if (interlock != NULL && plock->li_lock == interlock) {  in witness_checkorder()
1207 		if (lock_list->ll_count > 1)  in witness_checkorder()
1209 			    &lock_list->ll_children[lock_list->ll_count - 2];  in witness_checkorder()
1211 			lle = lock_list->ll_next;  in witness_checkorder()
1219 			plock = &lle->ll_children[lle->ll_count - 1];  in witness_checkorder()
1228 	w1 = plock->li_lock->lo_witness;  in witness_checkorder()
1245 		i = w->w_index;  in witness_checkorder()
1246 		if (!(lock->lo_flags & LO_DUPOK) && !(flags & LOP_DUPOK) &&  in witness_checkorder()
1249 			w->w_reversed = 1;  in witness_checkorder()
1253 			    w->w_name);  in witness_checkorder()
1254 			witness_output(" 1st %s @ %s:%d\n", plock->li_lock->lo_name,  in witness_checkorder()
1255 			    fixup_filename(plock->li_file), plock->li_line);  in witness_checkorder()
1256 			witness_output(" 2nd %s @ %s:%d\n", lock->lo_name,  in witness_checkorder()
1273 	for (j = 0, lle = lock_list; lle != NULL; lle = lle->ll_next) {  in witness_checkorder()
1274 		for (i = lle->ll_count - 1; i >= 0; i--, j++) {  in witness_checkorder()
1279 			lock1 = &lle->ll_children[i];  in witness_checkorder()
1284 			if (interlock == lock1->li_lock)  in witness_checkorder()
1291 			w1 = lock1->li_lock->lo_witness;  in witness_checkorder()
1293 				KASSERT((lock1->li_lock->lo_flags & LO_WITNESS) == 0,  in witness_checkorder()
1302 			if ((lock1->li_flags & LI_SLEEPABLE) != 0 &&  in witness_checkorder()
1310 			if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&  in witness_checkorder()
1312 			    lock1->li_lock == &Giant.lock_object)  in witness_checkorder()
1319 			 * sleepable locks before non-sleepable locks.  in witness_checkorder()
1321 			if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&  in witness_checkorder()
1323 			    (lock1->li_flags & LI_SLEEPABLE) == 0)  in witness_checkorder()
1327 			 * If we are locking Giant and this is a non-sleepable  in witness_checkorder()
1330 			if ((lock1->li_flags & LI_SLEEPABLE) == 0 &&  in witness_checkorder()
1347 			if (w_rmatrix[w1->w_index][w->w_index] & WITNESS_REVERSAL)  in witness_checkorder()
1351 			w_rmatrix[w1->w_index][w->w_index] |= WITNESS_REVERSAL;  in witness_checkorder()
1352 			w_rmatrix[w->w_index][w1->w_index] |= WITNESS_REVERSAL;  in witness_checkorder()
1353 			w->w_reversed = w1->w_reversed = 1;  in witness_checkorder()
1371 					stack_copy(&data->wlod_stack,  in witness_checkorder()
1385 			if ((lock->lo_flags & LO_IS_VNODE) != 0 &&  in witness_checkorder()
1386 			    (lock1->li_lock->lo_flags & LO_IS_VNODE) != 0)  in witness_checkorder()
1393 			if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&  in witness_checkorder()
1395 			    (lock1->li_flags & LI_SLEEPABLE) == 0)  in witness_checkorder()
1397 		"lock order reversal: (sleepable after non-sleepable)\n");  in witness_checkorder()
1398 			else if ((lock1->li_flags & LI_SLEEPABLE) == 0  in witness_checkorder()
1401 		"lock order reversal: (Giant after non-sleepable)\n");  in witness_checkorder()
1410 				lock2 = &lle->ll_children[i];  in witness_checkorder()
1411 				MPASS(lock2->li_lock != NULL);  in witness_checkorder()
1412 				if (lock2->li_lock->lo_witness == w)  in witness_checkorder()
1414 				if (i == 0 && lle->ll_next != NULL) {  in witness_checkorder()
1415 					lle = lle->ll_next;  in witness_checkorder()
1416 					i = lle->ll_count - 1;  in witness_checkorder()
1419 					i--;  in witness_checkorder()
1423 				    lock1->li_lock, lock1->li_lock->lo_name,  in witness_checkorder()
1424 				    w1->w_name, w1->w_class->lc_name,  in witness_checkorder()
1425 				    fixup_filename(lock1->li_file),  in witness_checkorder()
1426 				    lock1->li_line);  in witness_checkorder()
1428 				    lock, lock->lo_name, w->w_name,  in witness_checkorder()
1429 				    w->w_class->lc_name, fixup_filename(file),  in witness_checkorder()
1432 				struct witness *w2 = lock2->li_lock->lo_witness;  in witness_checkorder()
1435 				    lock2->li_lock, lock2->li_lock->lo_name,  in witness_checkorder()
1436 				    w2->w_name, w2->w_class->lc_name,  in witness_checkorder()
1437 				    fixup_filename(lock2->li_file),  in witness_checkorder()
1438 				    lock2->li_line);  in witness_checkorder()
1440 				    lock1->li_lock, lock1->li_lock->lo_name,  in witness_checkorder()
1441 				    w1->w_name, w1->w_class->lc_name,  in witness_checkorder()
1442 				    fixup_filename(lock1->li_file),  in witness_checkorder()
1443 				    lock1->li_line);  in witness_checkorder()
1445 				    lock->lo_name, w->w_name,  in witness_checkorder()
1446 				    w->w_class->lc_name, fixup_filename(file),  in witness_checkorder()
1459 				    "lock order %s -> %s established at:\n",  in witness_checkorder()
1460 					    w->w_name, w1->w_name);  in witness_checkorder()
1466 				    "lock order %s -> %s attempted at:\n",  in witness_checkorder()
1467 				    w1->w_name, w->w_name);  in witness_checkorder()
1487 	    !(plock->li_lock == &Giant.lock_object &&  in witness_checkorder()
1488 	    (lock->lo_flags & LO_SLEEPABLE) != 0 &&  in witness_checkorder()
1491 		    w->w_name, plock->li_lock->lo_witness->w_name);  in witness_checkorder()
1492 		itismychild(plock->li_lock->lo_witness, w);  in witness_checkorder()
1506 	if (witness_cold || witness_watch == -1 || lock->lo_witness == NULL ||  in witness_lock()
1509 	w = lock->lo_witness;  in witness_lock()
1513 	if (LOCK_CLASS(lock)->lc_flags & LC_SLEEPLOCK)  in witness_lock()
1514 		lock_list = &td->td_sleeplocks;  in witness_lock()
1518 	/* Update per-witness last file and line acquire. */  in witness_lock()
1519 	w->w_file = file;  in witness_lock()
1520 	w->w_line = line;  in witness_lock()
1525 		instance->li_flags++;  in witness_lock()
1527 		    td->td_proc->p_pid, lock->lo_name,  in witness_lock()
1528 		    instance->li_flags & LI_RECURSEMASK);  in witness_lock()
1534 	if (lle == NULL || lle->ll_count == LOCK_NCHILDREN) {  in witness_lock()
1538 		lle->ll_next = *lock_list;  in witness_lock()
1540 		    td->td_proc->p_pid, lle);  in witness_lock()
1543 	instance = &lle->ll_children[lle->ll_count++];  in witness_lock()
1544 	instance->li_lock = lock;  in witness_lock()
1545 	instance->li_line = line;  in witness_lock()
1546 	instance->li_file = file;  in witness_lock()
1547 	instance->li_flags = 0;  in witness_lock()
1549 		instance->li_flags |= LI_EXCLUSIVE;  in witness_lock()
1550 	if ((lock->lo_flags & LO_SLEEPABLE) != 0 && (flags & LOP_NOSLEEP) == 0)  in witness_lock()
1551 		instance->li_flags |= LI_SLEEPABLE;  in witness_lock()
1553 	    td->td_proc->p_pid, lock->lo_name, lle->ll_count - 1);  in witness_lock()
1563 	if (lock->lo_witness == NULL || witness_watch == -1 || KERNEL_PANICKED())  in witness_upgrade()
1567 		if ((lock->lo_flags & LO_UPGRADABLE) == 0)  in witness_upgrade()
1569 			    "upgrade of non-upgradable lock (%s) %s @ %s:%d",  in witness_upgrade()
1570 			    class->lc_name, lock->lo_name,  in witness_upgrade()
1572 		if ((class->lc_flags & LC_SLEEPLOCK) == 0)  in witness_upgrade()
1574 			    "upgrade of non-sleep lock (%s) %s @ %s:%d",  in witness_upgrade()
1575 			    class->lc_name, lock->lo_name,  in witness_upgrade()
1578 	instance = find_instance(curthread->td_sleeplocks, lock);  in witness_upgrade()
1581 		    class->lc_name, lock->lo_name,  in witness_upgrade()
1586 		if ((instance->li_flags & LI_EXCLUSIVE) != 0)  in witness_upgrade()
1589 			    class->lc_name, lock->lo_name,  in witness_upgrade()
1591 		if ((instance->li_flags & LI_RECURSEMASK) != 0)  in witness_upgrade()
1594 			    class->lc_name, lock->lo_name,  in witness_upgrade()
1595 			    instance->li_flags & LI_RECURSEMASK,  in witness_upgrade()
1598 	instance->li_flags |= LI_EXCLUSIVE;  in witness_upgrade()
1609 	if (lock->lo_witness == NULL || witness_watch == -1 || KERNEL_PANICKED())  in witness_downgrade()
1613 		if ((lock->lo_flags & LO_UPGRADABLE) == 0)  in witness_downgrade()
1615 			    "downgrade of non-upgradable lock (%s) %s @ %s:%d",  in witness_downgrade()
1616 			    class->lc_name, lock->lo_name,  in witness_downgrade()
1618 		if ((class->lc_flags & LC_SLEEPLOCK) == 0)  in witness_downgrade()
1620 			    "downgrade of non-sleep lock (%s) %s @ %s:%d",  in witness_downgrade()
1621 			    class->lc_name, lock->lo_name,  in witness_downgrade()
1624 	instance = find_instance(curthread->td_sleeplocks, lock);  in witness_downgrade()
1627 		    class->lc_name, lock->lo_name,  in witness_downgrade()
1632 		if ((instance->li_flags & LI_EXCLUSIVE) == 0)  in witness_downgrade()
1635 			    class->lc_name, lock->lo_name,  in witness_downgrade()
1637 		if ((instance->li_flags & LI_RECURSEMASK) != 0)  in witness_downgrade()
1640 			    class->lc_name, lock->lo_name,  in witness_downgrade()
1641 			    instance->li_flags & LI_RECURSEMASK,  in witness_downgrade()
1644 	instance->li_flags &= ~LI_EXCLUSIVE;  in witness_downgrade()
1657 	if (witness_cold || lock->lo_witness == NULL || KERNEL_PANICKED())  in witness_unlock()
1663 	if (class->lc_flags & LC_SLEEPLOCK)  in witness_unlock()
1664 		lock_list = &td->td_sleeplocks;  in witness_unlock()
1668 	for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)  in witness_unlock()
1669 		for (i = 0; i < (*lock_list)->ll_count; i++) {  in witness_unlock()
1670 			instance = &(*lock_list)->ll_children[i];  in witness_unlock()
1671 			if (instance->li_lock == lock)  in witness_unlock()
1682 		kassert_panic("lock (%s) %s not locked @ %s:%d", class->lc_name,  in witness_unlock()
1683 		    lock->lo_name, fixup_filename(file), line);  in witness_unlock()
1691 	if ((instance->li_flags & LI_EXCLUSIVE) != 0 && witness_watch > 0 &&  in witness_unlock()
1694 		    class->lc_name, lock->lo_name, fixup_filename(file), line);  in witness_unlock()
1695 		witness_output("while exclusively locked from %s:%d\n",  in witness_unlock()
1696 		    fixup_filename(instance->li_file), instance->li_line);  in witness_unlock()
1697 		kassert_panic("excl->ushare");  in witness_unlock()
1699 	if ((instance->li_flags & LI_EXCLUSIVE) == 0 && witness_watch > 0 &&  in witness_unlock()
1702 		    class->lc_name, lock->lo_name, fixup_filename(file), line);  in witness_unlock()
1703 		witness_output("while share locked from %s:%d\n",  in witness_unlock()
1704 		    fixup_filename(instance->li_file),  in witness_unlock()
1705 		    instance->li_line);  in witness_unlock()
1706 		kassert_panic("share->uexcl");  in witness_unlock()
1709 	if ((instance->li_flags & LI_RECURSEMASK) > 0) {  in witness_unlock()
1711 		    td->td_proc->p_pid, instance->li_lock->lo_name,  in witness_unlock()
1712 		    instance->li_flags);  in witness_unlock()
1713 		instance->li_flags--;  in witness_unlock()
1717 	if ((instance->li_flags & LI_NORELEASE) != 0 && witness_watch > 0) {  in witness_unlock()
1719 		    class->lc_name, lock->lo_name, fixup_filename(file), line);  in witness_unlock()
1726 	    td->td_proc->p_pid, instance->li_lock->lo_name,  in witness_unlock()
1727 	    (*lock_list)->ll_count - 1);  in witness_unlock()
1728 	for (j = i; j < (*lock_list)->ll_count - 1; j++)  in witness_unlock()
1729 		(*lock_list)->ll_children[j] =  in witness_unlock()
1730 		    (*lock_list)->ll_children[j + 1];  in witness_unlock()
1731 	(*lock_list)->ll_count--;  in witness_unlock()
1743 	if ((*lock_list)->ll_count == 0) {  in witness_unlock()
1745 			if (lle->ll_next == NULL)  in witness_unlock()
1749 		*lock_list = lle->ll_next;  in witness_unlock()
1751 		    td->td_proc->p_pid, lle);  in witness_unlock()
1762 	lle = td->td_sleeplocks;  in witness_thread_exit()
1765 	if (lle->ll_count != 0) {  in witness_thread_exit()
1766 		for (n = 0; lle != NULL; lle = lle->ll_next)  in witness_thread_exit()
1767 			for (i = lle->ll_count - 1; i >= 0; i--) {  in witness_thread_exit()
1772 				witness_list_lock(&lle->ll_children[i],  in witness_thread_exit()
1785  * non-exempt locks are held, then a supplied message is printed to the
1802 	for (lle = td->td_sleeplocks; lle != NULL; lle = lle->ll_next)  in witness_warn()
1803 		for (i = lle->ll_count - 1; i >= 0; i--) {  in witness_warn()
1804 			lock1 = &lle->ll_children[i];  in witness_warn()
1805 			if (lock1->li_lock == lock)  in witness_warn()
1808 			    lock1->li_lock == &Giant.lock_object)  in witness_warn()
1811 			    (lock1->li_flags & LI_SLEEPABLE) != 0)  in witness_warn()
1819 				    "non-sleepable " : "");  in witness_warn()
1832 	if (lock_list != NULL && lock_list->ll_count != 0) {  in witness_warn()
1841 		lock1 = &lock_list->ll_children[lock_list->ll_count - 1];  in witness_warn()
1842 		if (lock_list->ll_count == 1 && lock_list->ll_next == NULL &&  in witness_warn()
1843 		    lock1->li_lock == lock && n == 0)  in witness_warn()
1850 		    (flags & WARN_SLEEPOK) != 0 ?  "non-sleepable " : "");  in witness_warn()
1866 	if (witness_cold || witness_watch < 1 || lock->lo_witness == NULL)  in witness_file()
1868 	w = lock->lo_witness;  in witness_file()
1869 	return (w->w_file);  in witness_file()
1877 	if (witness_cold || witness_watch < 1 || lock->lo_witness == NULL)  in witness_line()
1879 	w = lock->lo_witness;  in witness_line()
1880 	return (w->w_line);  in witness_line()
1890 	if (witness_watch == -1 || KERNEL_PANICKED())  in enroll()
1892 	if ((lock_class->lc_flags & LC_SPINLOCK)) {  in enroll()
1895 	} else if ((lock_class->lc_flags & LC_SLEEPLOCK) == 0) {  in enroll()
1897 		    lock_class->lc_name);  in enroll()
1908 	strcpy(w->w_name, description);  in enroll()
1909 	w->w_class = lock_class;  in enroll()
1910 	w->w_refcount = 1;  in enroll()
1912 	if (lock_class->lc_flags & LC_SPINLOCK) {  in enroll()
1915 	} else if (lock_class->lc_flags & LC_SLEEPLOCK) {  in enroll()
1926 	w->w_refcount++;  in enroll()
1927 	if (w->w_refcount == 1)  in enroll()
1928 		w->w_class = lock_class;  in enroll()
1930 	if (lock_class != w->w_class)  in enroll()
1933 		    description, lock_class->lc_name,  in enroll()
1934 		    w->w_class->lc_name);  in enroll()
1941 	MPASS(w->w_refcount == 0);  in depart()
1942 	if (w->w_class->lc_flags & LC_SLEEPLOCK) {  in depart()
1943 		w_sleep_cnt--;  in depart()
1945 		w_spin_cnt--;  in depart()
1950 	w->w_file = NULL;  in depart()
1951 	w->w_line = 0;  in depart()
1956 adopt(struct witness *parent, struct witness *child)  in adopt()  argument
1964 	if (isitmychild(parent, child))  in adopt()
1974 	pi = parent->w_index;  in adopt()
1975 	ci = child->w_index;  in adopt()
1983 	 * If parent was not already an ancestor of child,  in adopt()
1987 		parent->w_num_descendants++;  in adopt()
1988 		child->w_num_ancestors++;  in adopt()
2033 				witness_watch = -1;  in adopt()
2042 				witness_watch = -1;  in adopt()
2049 itismychild(struct witness *parent, struct witness *child)  in itismychild()  argument
2053 	MPASS(child != NULL && parent != NULL);  in itismychild()
2057 	if (!witness_lock_type_equal(parent, child)) {  in itismychild()
2065 		    "%s: parent \"%s\" (%s) and child \"%s\" (%s) are not "  in itismychild()
2066 		    "the same lock type", __func__, parent->w_name,  in itismychild()
2067 		    parent->w_class->lc_name, child->w_name,  in itismychild()
2068 		    child->w_class->lc_name);  in itismychild()
2072 	adopt(parent, child);  in itismychild()
2085 	i1 = w1->w_index;  in _isitmyx()
2086 	i2 = w2->w_index;  in _isitmyx()
2101 		    fname, w1->w_name, i1, w2->w_name, i2, i1, i2, r1,  in _isitmyx()
2105 		witness_watch = -1;  in _isitmyx()
2111  * Checks if @child is a direct child of @parent.
2114 isitmychild(struct witness *parent, struct witness *child)  in isitmychild()  argument
2116 	return (_isitmyx(parent, child, WITNESS_PARENT, __func__));  in isitmychild()
2137 		if (strcmp(w1->w_name, b->b_lock1) == 0) {  in blessed()
2138 			if (strcmp(w2->w_name, b->b_lock2) == 0)  in blessed()
2142 		if (strcmp(w1->w_name, b->b_lock2) == 0)  in blessed()
2143 			if (strcmp(w2->w_name, b->b_lock1) == 0)  in blessed()
2158 	if (witness_watch == -1) {  in witness_get()
2163 		witness_watch = -1;  in witness_get()
2170 	w_free_cnt--;  in witness_get()
2171 	index = w->w_index;  in witness_get()
2175 	w->w_index = index;  in witness_get()
2193 	if (witness_watch == -1)  in witness_lock_list_get()
2198 		witness_watch = -1;  in witness_lock_list_get()
2203 	w_lock_list_free = lle->ll_next;  in witness_lock_list_get()
2213 	lle->ll_next = w_lock_list_free;  in witness_lock_list_free()
2225 	for (lle = list; lle != NULL; lle = lle->ll_next)  in find_instance()
2226 		for (i = lle->ll_count - 1; i >= 0; i--) {  in find_instance()
2227 			instance = &lle->ll_children[i];  in find_instance()
2228 			if (instance->li_lock == lock)  in find_instance()
2240 	lock = instance->li_lock;  in witness_list_lock()
2241 	prnt("%s %s %s", (instance->li_flags & LI_EXCLUSIVE) != 0 ?  in witness_list_lock()
2242 	    "exclusive" : "shared", LOCK_CLASS(lock)->lc_name, lock->lo_name);  in witness_list_lock()
2243 	if (lock->lo_witness->w_name != lock->lo_name)  in witness_list_lock()
2244 		prnt(" (%s)", lock->lo_witness->w_name);  in witness_list_lock()
2245 	prnt(" r = %d (%p) locked @ %s:%d\n",  in witness_list_lock()
2246 	    instance->li_flags & LI_RECURSEMASK, lock,  in witness_list_lock()
2247 	    fixup_filename(instance->li_file), instance->li_line);  in witness_list_lock()
2285 	if (td->td_sleeplocks == NULL)  in witness_thread_has_locks()
2287 	return (td->td_sleeplocks->ll_count != 0);  in witness_thread_has_locks()
2311 	for (lle = *lock_list; lle != NULL; lle = lle->ll_next)  in witness_list_locks()
2312 		for (i = lle->ll_count - 1; i >= 0; i--) {  in witness_list_locks()
2313 			witness_list_lock(&lle->ll_children[i], prnt);  in witness_list_locks()
2323  * per-cpu data to try to find the lock instance for this spin lock to
2333 	if (owner->td_critnest == 0 || owner->td_oncpu == NOCPU)  in witness_display_spinlock()
2335 	pc = pcpu_find(owner->td_oncpu);  in witness_display_spinlock()
2336 	instance = find_instance(pc->pc_spinlocks, lock);  in witness_display_spinlock()
2360 	if (lock->lo_witness == NULL || witness_watch == -1 || KERNEL_PANICKED())  in witness_save()
2363 	if (class->lc_flags & LC_SLEEPLOCK)  in witness_save()
2364 		lock_list = curthread->td_sleeplocks;  in witness_save()
2372 		kassert_panic("%s: lock (%s) %s not locked", __func__,  in witness_save()
2373 		    class->lc_name, lock->lo_name);  in witness_save()
2376 	*filep = instance->li_file;  in witness_save()
2377 	*linep = instance->li_line;  in witness_save()
2395 	if (lock->lo_witness == NULL || witness_watch == -1 || KERNEL_PANICKED())  in witness_restore()
2398 	if (class->lc_flags & LC_SLEEPLOCK)  in witness_restore()
2399 		lock_list = curthread->td_sleeplocks;  in witness_restore()
2407 		kassert_panic("%s: lock (%s) %s not locked", __func__,  in witness_restore()
2408 		    class->lc_name, lock->lo_name);  in witness_restore()
2409 	lock->lo_witness->w_file = file;  in witness_restore()
2410 	lock->lo_witness->w_line = line;  in witness_restore()
2413 	instance->li_file = file;  in witness_restore()
2414 	instance->li_line = line;  in witness_restore()
2424 	if (lock->lo_witness == NULL || witness_watch < 1 || KERNEL_PANICKED())  in witness_find_instance()
2427 	if ((class->lc_flags & LC_SLEEPLOCK) != 0) {  in witness_find_instance()
2428 		*instance = find_instance(curthread->td_sleeplocks, lock);  in witness_find_instance()
2430 	} else if ((class->lc_flags & LC_SPINLOCK) != 0) {  in witness_find_instance()
2435 		    class->lc_name, lock->lo_name);  in witness_find_instance()
2457 			kassert_panic("Lock (%s) %s locked @ %s:%d.",  in witness_assert()
2458 			    class->lc_name, lock->lo_name,  in witness_assert()
2471 			kassert_panic("Lock (%s) %s not locked @ %s:%d.",  in witness_assert()
2472 			    class->lc_name, lock->lo_name,  in witness_assert()
2477 		    (instance->li_flags & LI_EXCLUSIVE) == 0)  in witness_assert()
2479 			    "Lock (%s) %s not exclusively locked @ %s:%d.",  in witness_assert()
2480 			    class->lc_name, lock->lo_name,  in witness_assert()
2483 		    (instance->li_flags & LI_EXCLUSIVE) != 0)  in witness_assert()
2485 			    "Lock (%s) %s exclusively locked @ %s:%d.",  in witness_assert()
2486 			    class->lc_name, lock->lo_name,  in witness_assert()
2489 		    (instance->li_flags & LI_RECURSEMASK) == 0)  in witness_assert()
2491 			    class->lc_name, lock->lo_name,  in witness_assert()
2494 		    (instance->li_flags & LI_RECURSEMASK) != 0)  in witness_assert()
2496 			    class->lc_name, lock->lo_name,  in witness_assert()
2510  *   -1 if not owned
2521 	return (instance == NULL ? -1 : 1);  in witness_is_owned()
2534 	if (lock->lo_witness == NULL || witness_watch == -1 || KERNEL_PANICKED())  in witness_setflag()
2537 	if (class->lc_flags & LC_SLEEPLOCK)  in witness_setflag()
2538 		lock_list = curthread->td_sleeplocks;  in witness_setflag()
2546 		kassert_panic("%s: lock (%s) %s not locked", __func__,  in witness_setflag()
2547 		    class->lc_name, lock->lo_name);  in witness_setflag()
2552 		instance->li_flags |= flag;  in witness_setflag()
2554 		instance->li_flags &= ~flag;  in witness_setflag()
2579 	witness_list_locks(&td->td_sleeplocks, db_printf);  in witness_ddb_list()
2585 	 * the per-cpu data for a given cpu then we could use  in witness_ddb_list()
2586 	 * td->td_oncpu to get the list of spinlocks for this thread  in witness_ddb_list()
2589 	 * That still wouldn't really fix this unless we locked the scheduler  in witness_ddb_list()
2625 			db_printf("Process %d (%s) thread %p (%d)\n", p->p_pid,  in DB_SHOW_ALL_COMMAND()
2626 			    p->p_comm, td, td->td_tid);  in DB_SHOW_ALL_COMMAND()
2660 	stack_zero(&tmp_data1->wlod_stack);  in sbuf_print_witness_badstacks()
2661 	stack_zero(&tmp_data2->wlod_stack);  in sbuf_print_witness_badstacks()
2681 		if (w1->w_reversed == 0) {  in sbuf_print_witness_badstacks()
2690 		if (tmp_w1->w_reversed == 0)  in sbuf_print_witness_badstacks()
2717 				stack_zero(&tmp_data1->wlod_stack);  in sbuf_print_witness_badstacks()
2718 				stack_copy(&data1->wlod_stack,  in sbuf_print_witness_badstacks()
2719 				    &tmp_data1->wlod_stack);  in sbuf_print_witness_badstacks()
2722 				stack_zero(&tmp_data2->wlod_stack);  in sbuf_print_witness_badstacks()
2723 				stack_copy(&data2->wlod_stack,  in sbuf_print_witness_badstacks()
2724 				    &tmp_data2->wlod_stack);  in sbuf_print_witness_badstacks()
2733 			    tmp_w1->w_name, tmp_w1->w_class->lc_name,  in sbuf_print_witness_badstacks()
2734 			    tmp_w2->w_name, tmp_w2->w_class->lc_name);  in sbuf_print_witness_badstacks()
2737 			"Lock order \"%s\"(%s) -> \"%s\"(%s) first seen at:\n",  in sbuf_print_witness_badstacks()
2738 				    tmp_w1->w_name, tmp_w1->w_class->lc_name,  in sbuf_print_witness_badstacks()
2739 				    tmp_w2->w_name, tmp_w2->w_class->lc_name);  in sbuf_print_witness_badstacks()
2740 				stack_sbuf_print(sb, &tmp_data1->wlod_stack);  in sbuf_print_witness_badstacks()
2745 			"Lock order \"%s\"(%s) -> \"%s\"(%s) first seen at:\n",  in sbuf_print_witness_badstacks()
2746 				    tmp_w2->w_name, tmp_w2->w_class->lc_name,  in sbuf_print_witness_badstacks()
2747 				    tmp_w1->w_name, tmp_w1->w_class->lc_name);  in sbuf_print_witness_badstacks()
2748 				stack_sbuf_print(sb, &tmp_data2->wlod_stack);  in sbuf_print_witness_badstacks()
2793 	sbuf_print_witness_badstacks(sb, &req->oldidx);  in sysctl_debug_witness_badstacks()
2845 	if (error != 0 || req->newptr == NULL)  in sysctl_debug_witness_channel()
2890 		w->w_displayed = 0;  in sysctl_debug_witness_fullgraph()
2911 	if (error != 0 || req->newptr == NULL)  in sysctl_debug_witness_watch()
2913 	if (value > 1 || value < -1 ||  in sysctl_debug_witness_watch()
2914 	    (witness_watch == -1 && value != witness_watch))  in sysctl_debug_witness_watch()
2925 	if (w->w_displayed != 0 || (w->w_file == NULL && w->w_line == 0))  in witness_add_fullgraph()
2927 	w->w_displayed = 1;  in witness_add_fullgraph()
2929 	WITNESS_INDEX_ASSERT(w->w_index);  in witness_add_fullgraph()
2931 		if (w_rmatrix[w->w_index][i] & WITNESS_PARENT) {  in witness_add_fullgraph()
2932 			sbuf_printf(sb, "\"%s\",\"%s\"\n", w->w_name,  in witness_add_fullgraph()
2942  * terminator. Otherwise, reads the first size bytes. Returns an unsigned 32-bit
3005 		if (strcmp(w->w_name, key) == 0)  in witness_hash_get()
3007 		w = w->w_hash_next;  in witness_hash_get()
3020 	MPASS(w->w_name != NULL);  in witness_hash_put()
3023 	KASSERT(witness_hash_get(w->w_name) == NULL,  in witness_hash_put()
3025 	KASSERT(w->w_hash_next == NULL,  in witness_hash_put()
3026 	    ("%s: w->w_hash_next != NULL", __func__));  in witness_hash_put()
3028 	hash = witness_hash_djb2(w->w_name, 0) % w_hash.wh_size;  in witness_hash_put()
3029 	w->w_hash_next = w_hash.wh_array[hash];  in witness_hash_put()
3035 witness_lock_order_get(struct witness *parent, struct witness *child)  in witness_lock_order_get()  argument
3041 	MPASS(parent != NULL && child != NULL);  in witness_lock_order_get()
3042 	key.from = parent->w_index;  in witness_lock_order_get()
3043 	key.to = child->w_index;  in witness_lock_order_get()
3046 	if ((w_rmatrix[parent->w_index][child->w_index]  in witness_lock_order_get()
3054 		if (witness_lock_order_key_equal(&data->wlod_key, &key))  in witness_lock_order_get()
3056 		data = data->wlod_next;  in witness_lock_order_get()
3064  * Verify that parent and child have a known relationship, are not the same,
3065  * and child is actually a child of parent.  This is done without w_mtx
3069 witness_lock_order_check(struct witness *parent, struct witness *child)  in witness_lock_order_check()  argument
3071 	if (parent != child &&  in witness_lock_order_check()
3072 	    w_rmatrix[parent->w_index][child->w_index]  in witness_lock_order_check()
3074 	    isitmychild(parent, child))  in witness_lock_order_check()
3081 witness_lock_order_add(struct witness *parent, struct witness *child)  in witness_lock_order_add()  argument
3087 	MPASS(parent != NULL && child != NULL);  in witness_lock_order_add()
3088 	key.from = parent->w_index;  in witness_lock_order_add()
3089 	key.to = child->w_index;  in witness_lock_order_add()
3092 	if (w_rmatrix[parent->w_index][child->w_index]  in witness_lock_order_add()
3098 	w_rmatrix[parent->w_index][child->w_index] |= WITNESS_LOCK_ORDER_KNOWN;  in witness_lock_order_add()
3102 	w_lofree = data->wlod_next;  in witness_lock_order_add()
3103 	data->wlod_next = w_lohash.wloh_array[hash];  in witness_lock_order_add()
3104 	data->wlod_key = key;  in witness_lock_order_add()
3107 	stack_save(&data->wlod_stack);  in witness_lock_order_add()