- Move state about lock objects out of struct lock_object and into a new

  struct lock_instance that is stored in the per-process and per-CPU lock
  lists.  Previously, the lock lists just kept a pointer to each lock held.
  That pointer is now replaced by a lock instance which contains a pointer
  to the lock object, the file and line of the last acquisition of a lock,
  and various flags about a lock including its recursion count.
- If we sleep while holding a sleepable lock, then mark that lock instance
  as having slept and ignore any lock order violations that occur while
  acquiring Giant when we wake up with slept locks.  This is ok because of
  Giant's special nature.
- Allow witness to differentiate between shared and exclusive locks and
  unlocks of a lock.  Witness will now detect the case when a lock is
  acquired first in one mode and then in another.  Mutexes are always
  locked and unlocked exclusively.  Witness will also now detect the case
  where a process attempts to unlock a shared lock while holding an
  exclusive lock and vice versa.
- Fix a bug in the lock list implementation where we used the wrong
  constant to detect the case where a lock list entry was full.

7 files changed, 231 insertions, 222 deletions

diff --git a/sys/kern/kern_mutex.c b/sys/kern/kern_mutex.c
index 72d4815..0007a8b 100644
--- a/sys/kern/kern_mutex.c
+++ b/sys/kern/kern_mutex.c
@@ -274,8 +274,8 @@ _mtx_trylock(struct mtx *m, int opts, const char *file, int line)
 		 */
 		KASSERT(!mtx_recursed(m),
 		    ("mtx_trylock() called on a recursed mutex"));
-		mtx_update_flags(m, 1);
-		WITNESS_LOCK(&m->mtx_object, opts | LOP_TRYLOCK, file, line);
+		WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE | LOP_TRYLOCK,
+		    file, line);
 	}
 
 	return (rval);
@@ -552,40 +552,6 @@ _mtx_unlock_sleep(struct mtx *m, int opts, const char *file, int line)
  * See the _rel_spin_lock() macro for the details. 
  */
 
-#ifdef WITNESS
-/*
- * Update the lock object flags before calling witness.  Note that when we
- * lock a mutex, this is called after getting the lock, but when unlocking
- * a mutex, this function is called before releasing the lock.
- */
-void
-_mtx_update_flags(struct mtx *m, int locking)
-{
-
-	mtx_assert(m, MA_OWNED);
-	if (locking) {
-		m->mtx_object.lo_flags |= LO_LOCKED;
-		if (mtx_recursed(m))
-			m->mtx_object.lo_flags |= LO_RECURSED;
-		else
-			/* XXX: we shouldn't need this in theory. */
-			m->mtx_object.lo_flags &= ~LO_RECURSED;
-	} else {
-		switch (m->mtx_recurse) {
-		case 0:
-			/* XXX: we shouldn't need the LO_RECURSED in theory. */
-			m->mtx_object.lo_flags &= ~(LO_LOCKED | LO_RECURSED);
-			break;
-		case 1:
-			m->mtx_object.lo_flags &= ~(LO_RECURSED);
-			break;
-		default:
-			break;
-		}
-	}
-}
-#endif
-
 /*
  * The backing function for the INVARIANTS-enabled mtx_assert()
  */
@@ -704,9 +670,8 @@ mtx_destroy(struct mtx *m)
 		MPASS((m->mtx_lock & (MTX_RECURSED|MTX_CONTESTED)) == 0);
 
 		/* Tell witness this isn't locked to make it happy. */
-		m->mtx_object.lo_flags &= ~LO_LOCKED;
-		WITNESS_UNLOCK(&m->mtx_object, MTX_NOSWITCH, __FILE__,
-		    __LINE__);
+		WITNESS_UNLOCK(&m->mtx_object, LOP_EXCLUSIVE | LOP_NOSWITCH,
+		    __FILE__, __LINE__);
 	}
 
 	WITNESS_DESTROY(&m->mtx_object);
diff --git a/sys/kern/kern_sx.c b/sys/kern/kern_sx.c
index 0f39097..2619f4b 100644
--- a/sys/kern/kern_sx.c
+++ b/sys/kern/kern_sx.c
@@ -33,13 +33,6 @@
  *
  * Priority propagation will not generally raise the priority of lock holders,
  * so should not be relied upon in combination with sx locks.
- *
- * The witness code can not detect lock cycles (yet).
- *
- * XXX: When witness is made to function with sx locks, it will need to
- * XXX: be taught to deal with these situations, as they are more involved:
- *   slock --> xlock (deadlock)
- *   slock --> slock (slock recursion, not fatal)
  */
 
 #include <sys/param.h>
@@ -50,10 +43,6 @@
 #include <sys/mutex.h>
 #include <sys/sx.h>
 
-/*
- * XXX: We don't implement the LO_RECURSED flag for this lock yet.
- * We could do this by walking p_sleeplocks if we really wanted to.
- */
 struct lock_class lock_class_sx = {
 	"sx",
 	LC_SLEEPLOCK | LC_SLEEPABLE | LC_RECURSABLE
@@ -68,7 +57,7 @@ sx_init(struct sx *sx, const char *description)
 	lock = &sx->sx_object;
 	lock->lo_class = &lock_class_sx;
 	lock->lo_name = description;
-	lock->lo_flags = LO_WITNESS | LO_SLEEPABLE;
+	lock->lo_flags = LO_WITNESS | LO_RECURSABLE | LO_SLEEPABLE;
 	mtx_init(&sx->sx_lock, "sx backing lock",
 	    MTX_DEF | MTX_NOWITNESS | MTX_QUIET);
 	sx->sx_cnt = 0;
@@ -121,9 +110,6 @@ _sx_slock(struct sx *sx, const char *file, int line)
 	/* Acquire a shared lock. */
 	sx->sx_cnt++;
 
-#ifdef WITNESS
-	sx->sx_object.lo_flags |= LO_LOCKED;
-#endif
 	LOCK_LOG_LOCK("SLOCK", &sx->sx_object, 0, 0, file, line);
 	WITNESS_LOCK(&sx->sx_object, 0, file, line);
 
@@ -160,11 +146,8 @@ _sx_xlock(struct sx *sx, const char *file, int line)
 	sx->sx_cnt--;
 	sx->sx_xholder = curproc;
 
-#ifdef WITNESS
-	sx->sx_object.lo_flags |= LO_LOCKED;
-#endif
 	LOCK_LOG_LOCK("XLOCK", &sx->sx_object, 0, 0, file, line);
-	WITNESS_LOCK(&sx->sx_object, 0, file, line);
+	WITNESS_LOCK(&sx->sx_object, LOP_EXCLUSIVE, file, line);
 
 	mtx_unlock(&sx->sx_lock);
 }
@@ -176,10 +159,6 @@ _sx_sunlock(struct sx *sx, const char *file, int line)
 	mtx_lock(&sx->sx_lock);
 	_SX_ASSERT_SLOCKED(sx);
 
-#ifdef WITNESS
-	if (sx->sx_cnt == 0)
-		sx->sx_object.lo_flags &= ~LO_LOCKED;
-#endif
 	WITNESS_UNLOCK(&sx->sx_object, 0, file, line);
 
 	/* Release. */
@@ -210,10 +189,7 @@ _sx_xunlock(struct sx *sx, const char *file, int line)
 	_SX_ASSERT_XLOCKED(sx);
 	MPASS(sx->sx_cnt == -1);
 
-#ifdef WITNESS
-	sx->sx_object.lo_flags &= ~LO_LOCKED;
-#endif
-	WITNESS_UNLOCK(&sx->sx_object, 0, file, line);
+	WITNESS_UNLOCK(&sx->sx_object, LOP_EXCLUSIVE, file, line);
 
 	/* Release. */
 	sx->sx_cnt++;
diff --git a/sys/kern/subr_turnstile.c b/sys/kern/subr_turnstile.c
index 72d4815..0007a8b 100644
--- a/sys/kern/subr_turnstile.c
+++ b/sys/kern/subr_turnstile.c
@@ -274,8 +274,8 @@ _mtx_trylock(struct mtx *m, int opts, const char *file, int line)
 		 */
 		KASSERT(!mtx_recursed(m),
 		    ("mtx_trylock() called on a recursed mutex"));
-		mtx_update_flags(m, 1);
-		WITNESS_LOCK(&m->mtx_object, opts | LOP_TRYLOCK, file, line);
+		WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE | LOP_TRYLOCK,
+		    file, line);
 	}
 
 	return (rval);
@@ -552,40 +552,6 @@ _mtx_unlock_sleep(struct mtx *m, int opts, const char *file, int line)
  * See the _rel_spin_lock() macro for the details. 
  */
 
-#ifdef WITNESS
-/*
- * Update the lock object flags before calling witness.  Note that when we
- * lock a mutex, this is called after getting the lock, but when unlocking
- * a mutex, this function is called before releasing the lock.
- */
-void
-_mtx_update_flags(struct mtx *m, int locking)
-{
-
-	mtx_assert(m, MA_OWNED);
-	if (locking) {
-		m->mtx_object.lo_flags |= LO_LOCKED;
-		if (mtx_recursed(m))
-			m->mtx_object.lo_flags |= LO_RECURSED;
-		else
-			/* XXX: we shouldn't need this in theory. */
-			m->mtx_object.lo_flags &= ~LO_RECURSED;
-	} else {
-		switch (m->mtx_recurse) {
-		case 0:
-			/* XXX: we shouldn't need the LO_RECURSED in theory. */
-			m->mtx_object.lo_flags &= ~(LO_LOCKED | LO_RECURSED);
-			break;
-		case 1:
-			m->mtx_object.lo_flags &= ~(LO_RECURSED);
-			break;
-		default:
-			break;
-		}
-	}
-}
-#endif
-
 /*
  * The backing function for the INVARIANTS-enabled mtx_assert()
  */
@@ -704,9 +670,8 @@ mtx_destroy(struct mtx *m)
 		MPASS((m->mtx_lock & (MTX_RECURSED|MTX_CONTESTED)) == 0);
 
 		/* Tell witness this isn't locked to make it happy. */
-		m->mtx_object.lo_flags &= ~LO_LOCKED;
-		WITNESS_UNLOCK(&m->mtx_object, MTX_NOSWITCH, __FILE__,
-		    __LINE__);
+		WITNESS_UNLOCK(&m->mtx_object, LOP_EXCLUSIVE | LOP_NOSWITCH,
+		    __FILE__, __LINE__);
 	}
 
 	WITNESS_DESTROY(&m->mtx_object);
diff --git a/sys/kern/subr_witness.c b/sys/kern/subr_witness.c
index a3e5f1e..a44cb44 100644
--- a/sys/kern/subr_witness.c
+++ b/sys/kern/subr_witness.c
@@ -139,6 +139,8 @@ static void	witness_child_free(struct witness_child_list_entry *wcl);
 static struct	lock_list_entry *witness_lock_list_get(void);
 static void	witness_lock_list_free(struct lock_list_entry *lle);
 static void	witness_display(void(*)(const char *fmt, ...));
+static struct	lock_instance *find_instance(struct lock_list_entry *lock_list,
+					     struct lock_object *lock);
 
 MALLOC_DEFINE(M_WITNESS, "witness", "witness structure");
 
@@ -245,8 +247,6 @@ STAILQ_HEAD(, lock_object) all_locks = STAILQ_HEAD_INITIALIZER(all_locks);
 static struct mtx all_mtx = {
 	{ &lock_class_mtx_sleep,	/* mtx_object.lo_class */
 	  "All locks list",		/* mtx_object.lo_name */
-	  NULL,				/* mtx_object.lo_file */
-	  0,				/* mtx_object.lo_line */
 	  LO_INITIALIZED,		/* mtx_object.lo_flags */
 	  { NULL },			/* mtx_object.lo_list */
 	  NULL },			/* mtx_object.lo_witness */
@@ -342,12 +342,12 @@ witness_init(struct lock_object *lock)
 	    (class->lc_flags & LC_RECURSABLE) == 0)
 		panic("%s: lock (%s) %s can not be recursable!\n", __func__,
 		    class->lc_name, lock->lo_name);
-	
+
 	if ((lock->lo_flags & LO_SLEEPABLE) != 0 &&
 	    (class->lc_flags & LC_SLEEPABLE) == 0)
 		panic("%s: lock (%s) %s can not be sleepable!\n", __func__,
 		    class->lc_name, lock->lo_name);
-	
+
 	mtx_lock(&all_mtx);
 	STAILQ_INSERT_TAIL(&all_locks, lock, lo_list);
 	lock->lo_flags |= LO_INITIALIZED;
@@ -375,10 +375,7 @@ witness_destroy(struct lock_object *lock)
 		panic("%s: lock (%s) %s is not initialized!\n", __func__,
 		    lock->lo_class->lc_name, lock->lo_name);
 
-	if (lock->lo_flags & LO_LOCKED)
-		panic("lock (%s) %s destroyed while held",
-		    lock->lo_class->lc_name, lock->lo_name);
-
+	/* XXX: need to verify that no one holds the lock */
 	w = lock->lo_witness;
 	if (w != NULL) {
 		mtx_lock_spin(&w_mtx);
@@ -460,7 +457,7 @@ void
 witness_lock(struct lock_object *lock, int flags, const char *file, int line)
 {
 	struct lock_list_entry **lock_list, *lle;
-	struct lock_object *lock1, *lock2;
+	struct lock_instance *lock1, *lock2;
 	struct lock_class *class;
 	struct witness *w, *w1;
 	struct proc *p;
@@ -476,19 +473,6 @@ witness_lock(struct lock_object *lock, int flags, const char *file, int line)
 	class = lock->lo_class;
 	p = curproc;
 
-	if ((lock->lo_flags & LO_LOCKED) == 0)
-		panic("%s: lock (%s) %s is not locked @ %s:%d", __func__,
-		    class->lc_name, lock->lo_name, file, line);
-
-	if ((lock->lo_flags & LO_RECURSED) != 0) {
-		if ((lock->lo_flags & LO_RECURSABLE) == 0)
-			panic(
-			"%s: recursed on non-recursive lock (%s) %s @ %s:%d first aquired @ %s:%d",
-			    __func__, class->lc_name, lock->lo_name, file,
-			    line, lock->lo_file, lock->lo_line);
-		return;
-	}
-	
 	/*
 	 * We have to hold a spinlock to keep lock_list valid across the check
 	 * in the LC_SLEEPLOCK case.  In the LC_SPINLOCK case, it is already
@@ -521,19 +505,54 @@ witness_lock(struct lock_object *lock, int flags, const char *file, int line)
 		goto out;
 
 	/*
+	 * Check to see if we are recursing on a lock we already own.
+	 */
+	lock1 = find_instance(*lock_list, lock);
+	if (lock1 != NULL) {
+		if ((lock1->li_flags & LI_EXCLUSIVE) != 0 &&
+		    (flags & LOP_EXCLUSIVE) == 0) {
+			printf("shared lock of (%s) %s @ %s:%d\n",
+			    class->lc_name, lock->lo_name, file, line);
+			printf("while exclusively locked from %s:%d\n",
+			    lock1->li_file, lock1->li_line);
+			panic("share->excl");
+		}
+		if ((lock1->li_flags & LI_EXCLUSIVE) == 0 &&
+		    (flags & LOP_EXCLUSIVE) != 0) {
+			printf("exclusive lock of (%s) %s @ %s:%d\n",
+			    class->lc_name, lock->lo_name, file, line);
+			printf("while share locked from %s:%d\n",
+			    lock1->li_file, lock1->li_line);
+			panic("excl->share");
+		}
+		lock1->li_flags++;
+		if ((lock->lo_flags & LO_RECURSABLE) == 0) {
+			printf(
+			"recursed on non-recursive lock (%s) %s @ %s:%d\n",
+			    class->lc_name, lock->lo_name, file, line);
+			printf("first acquired @ %s:%d\n", lock1->li_file,
+			    lock1->li_line);
+			panic("recurse");
+		}
+		lock1->li_file = file;
+		lock1->li_line = line;
+		return;
+	}
+
+	/*
 	 * Check for duplicate locks of the same type.  Note that we only
 	 * have to check for this on the last lock we just acquired.  Any
 	 * other cases will be caught as lock order violations.
 	 */
-	lock1 = (*lock_list)->ll_children[(*lock_list)->ll_count - 1];
-	w1 = lock1->lo_witness;
+	lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
+	w1 = lock1->li_lock->lo_witness;
 	if (w1 == w) {
 		if (w->w_same_squawked || dup_ok(w))
 			goto out;
 		w->w_same_squawked = 1;
 		printf("acquiring duplicate lock of same type: \"%s\"\n", 
 			lock->lo_name);
-		printf(" 1st @ %s:%d\n", w->w_file, w->w_line);
+		printf(" 1st @ %s:%d\n", lock1->li_file, lock1->li_line);
 		printf(" 2nd @ %s:%d\n", file, line);
 #ifdef DDB
 		go_into_ddb = 1;
@@ -557,18 +576,25 @@ witness_lock(struct lock_object *lock, int flags, const char *file, int line)
 		for (i = lle->ll_count - 1; i >= 0; i--, j++) {
 
 			MPASS(j < WITNESS_COUNT);
-			lock1 = lle->ll_children[i];
-			w1 = lock1->lo_witness;
+			lock1 = &lle->ll_children[i];
+			w1 = lock1->li_lock->lo_witness;
 
 			/*
 			 * If this lock doesn't undergo witness checking,
 			 * then skip it.
 			 */
 			if (w1 == NULL) {
-				KASSERT((lock1->lo_flags & LO_WITNESS) == 0,
+				KASSERT((lock1->li_lock->lo_flags & LO_WITNESS) == 0,
 				    ("lock missing witness structure"));
 				continue;
 			}
+			/*
+			 * If we are locking Giant and we slept with this
+			 * lock, then skip it.
+			 */
+			if ((lock1->li_flags & LI_SLEPT) != 0 &&
+			    lock == &Giant.mtx_object)
+				continue;
 			if (!isitmydescendant(w, w1))
 				continue;
 			/*
@@ -578,7 +604,7 @@ witness_lock(struct lock_object *lock, int flags, const char *file, int line)
 			mtx_unlock_spin(&w_mtx);
 			if (blessed(w, w1))
 				goto out;
-			if (lock1 == &Giant.mtx_object) {
+			if (lock1->li_lock == &Giant.mtx_object) {
 				if (w1->w_Giant_squawked)
 					goto out;
 				else
@@ -598,9 +624,9 @@ witness_lock(struct lock_object *lock, int flags, const char *file, int line)
 			 * witness w in our list.
 			 */
 			do {
-				lock2 = lle->ll_children[i];
-				MPASS(lock2 != NULL);
-				if (lock2->lo_witness == w)
+				lock2 = &lle->ll_children[i];
+				MPASS(lock2->li_lock != NULL);
+				if (lock2->li_lock->lo_witness == w)
 					break;
 				i--;
 				if (i == 0 && lle->ll_next != NULL) {
@@ -609,29 +635,30 @@ witness_lock(struct lock_object *lock, int flags, const char *file, int line)
 					MPASS(i != 0);
 				}
 			} while (i >= 0);
-			if (i < 0)
-				/*
-				 * We are very likely bogus in this case.
-				 */
-				printf(" 1st %s last acquired @ %s:%d\n",
-				    w->w_name, w->w_file, w->w_line);
-			else
-				printf(" 1st %p %s @ %s:%d\n", lock2,
-				    lock2->lo_name, lock2->lo_file,
-				    lock2->lo_line);
-			printf(" 2nd %p %s @ %s:%d\n",
-			    lock1, lock1->lo_name, lock1->lo_file,
-			    lock1->lo_line);
-			printf(" 3rd %p %s @ %s:%d\n",
-			    lock, lock->lo_name, file, line);
+			if (i < 0) {
+				printf(" 1st %p %s @ %s:%d\n", lock1->li_lock,
+				    lock1->li_lock->lo_name, lock1->li_file,
+				    lock1->li_line);
+				printf(" 2nd %p %s @ %s:%d\n", lock,
+				    lock->lo_name, file, line);
+			} else {
+				printf(" 1st %p %s @ %s:%d\n", lock2->li_lock,
+				    lock2->li_lock->lo_name, lock2->li_file,
+				    lock2->li_line);
+				printf(" 2nd %p %s @ %s:%d\n", lock1->li_lock,
+				    lock1->li_lock->lo_name, lock1->li_file,
+				    lock1->li_line);
+				printf(" 3rd %p %s @ %s:%d\n", lock,
+				    lock->lo_name, file, line);
+			}
 #ifdef DDB
 			go_into_ddb = 1;
 #endif /* DDB */
 			goto out;
 		}
 	}
-	lock1 = (*lock_list)->ll_children[(*lock_list)->ll_count - 1];
-	if (!itismychild(lock1->lo_witness, w))
+	lock1 = &(*lock_list)->ll_children[(*lock_list)->ll_count - 1];
+	if (!itismychild(lock1->li_lock->lo_witness, w))
 		mtx_unlock_spin(&w_mtx);
 
 out:
@@ -641,24 +668,30 @@ out:
 #endif /* DDB */
 	w->w_file = file;
 	w->w_line = line;
-	lock->lo_line = line;
-	lock->lo_file = file;
 	
 	lle = *lock_list;
-	if (lle == NULL || lle->ll_count == LOCK_CHILDCOUNT) {
+	if (lle == NULL || lle->ll_count == LOCK_NCHILDREN) {
 		*lock_list = witness_lock_list_get();
 		if (*lock_list == NULL)
 			return;
 		(*lock_list)->ll_next = lle;
 		lle = *lock_list;
 	}
-	lle->ll_children[lle->ll_count++] = lock;
+	lock1 = &lle->ll_children[lle->ll_count++];
+	lock1->li_lock = lock;
+	lock1->li_line = line;
+	lock1->li_file = file;
+	if ((flags & LOP_EXCLUSIVE) != 0)
+		lock1->li_flags = LI_EXCLUSIVE;
+	else
+		lock1->li_flags = 0;
 }
 
 void
 witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
 {
 	struct lock_list_entry **lock_list, *lle;
+	struct lock_instance *instance;
 	struct lock_class *class;
 	struct proc *p;
 	int i, j;
@@ -668,32 +701,43 @@ witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
 		return;
 	p = curproc;
 	class = lock->lo_class;
-
-	if (lock->lo_flags & LO_RECURSED) {
-		if ((lock->lo_flags & LO_LOCKED) == 0)
-			panic("%s: recursed lock (%s) %s is not locked @ %s:%d",
-			    __func__, class->lc_name, lock->lo_name, file,
-			    line);
-		return;
-	}
-
-	/*
-	 * We don't need to protect this PCPU_GET() here against preemption
-	 * because if we hold any spinlocks then we are already protected,
-	 * and if we don't we will get NULL if we hold no spinlocks even if
-	 * we switch CPU's while reading it.
-	 */
-	if (class->lc_flags & LC_SLEEPLOCK) {
-		if ((flags & LOP_NOSWITCH) == 0 && PCPU_GET(spinlocks) != NULL)
-			panic("switchable sleep unlock (%s) %s @ %s:%d",
-			    class->lc_name, lock->lo_name, file, line);
+	if (class->lc_flags & LC_SLEEPLOCK)
 		lock_list = &p->p_sleeplocks;
-	} else
+	else
 		lock_list = PCPU_PTR(spinlocks);
-
 	for (; *lock_list != NULL; lock_list = &(*lock_list)->ll_next)
-		for (i = 0; i < (*lock_list)->ll_count; i++)
-			if ((*lock_list)->ll_children[i] == lock) {
+		for (i = 0; i < (*lock_list)->ll_count; i++) {
+			instance = &(*lock_list)->ll_children[i];
+			if (instance->li_lock == lock) {
+				if ((instance->li_flags & LI_EXCLUSIVE) != 0 &&
+				    (flags & LOP_EXCLUSIVE) == 0) {
+					printf(
+					"shared unlock of (%s) %s @ %s:%d\n",
+					    class->lc_name, lock->lo_name,
+					    file, line);
+					printf(
+					"while exclusively locked from %s:%d\n",
+					    instance->li_file,
+					    instance->li_line);
+					panic("excl->ushare");
+				}
+				if ((instance->li_flags & LI_EXCLUSIVE) == 0 &&
+				    (flags & LOP_EXCLUSIVE) != 0) {
+					printf(
+					"exclusive unlock of (%s) %s @ %s:%d\n",
+					    class->lc_name, lock->lo_name,
+					    file, line);
+					printf(
+					"while share locked from %s:%d\n",
+					    instance->li_file,
+					    instance->li_line);
+					panic("share->uexcl");
+				}
+				/* If we are recursed, unrecurse. */
+				if ((instance->li_flags & LI_RECURSEMASK) > 0) {
+					instance->li_flags--;
+					goto out;
+				}
 				(*lock_list)->ll_count--;
 				for (j = i; j < (*lock_list)->ll_count; j++)
 					(*lock_list)->ll_children[j] =
@@ -703,8 +747,23 @@ witness_unlock(struct lock_object *lock, int flags, const char *file, int line)
 					*lock_list = lle->ll_next;
 					witness_lock_list_free(lle);
 				}
-				return;
+				goto out;
 			}
+		}
+	panic("lock (%s) %s not locked @ %s:%d", class->lc_name, lock->lo_name,
+	    file, line);
+out:
+	/*
+	 * We don't need to protect this PCPU_GET() here against preemption
+	 * because if we hold any spinlocks then we are already protected,
+	 * and if we don't we will get NULL if we hold no spinlocks even if
+	 * we switch CPU's while reading it.
+	 */
+	if (class->lc_flags & LC_SLEEPLOCK) {
+		if ((flags & LOP_NOSWITCH) == 0 && PCPU_GET(spinlocks) != NULL)
+			panic("switchable sleep unlock (%s) %s @ %s:%d",
+			    class->lc_name, lock->lo_name, file, line);
+	}
 }
 
 /*
@@ -717,7 +776,7 @@ witness_sleep(int check_only, struct lock_object *lock, const char *file,
 	      int line)
 {
 	struct lock_list_entry **lock_list, *lle;
-	struct lock_object *lock1;
+	struct lock_instance *lock1;
 	struct proc *p;
 	critical_t savecrit;
 	int i, n;
@@ -735,14 +794,20 @@ witness_sleep(int check_only, struct lock_object *lock, const char *file,
 again:
 	for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
 		for (i = lle->ll_count - 1; i >= 0; i--) {
-			lock1 = lle->ll_children[i];
-			if (lock1 == lock || lock1 == &Giant.mtx_object ||
-			    (lock1->lo_flags & LO_SLEEPABLE))
+			lock1 = &lle->ll_children[i];
+			if (lock1->li_lock == lock ||
+			    lock1->li_lock == &Giant.mtx_object)
 				continue;
+			if ((lock1->li_lock->lo_flags & LO_SLEEPABLE) != 0) {
+				if (check_only == 0)
+					lock1->li_flags |= LI_SLEPT;
+				continue;
+			}
 			n++;
 			printf("%s:%d: %s with \"%s\" locked from %s:%d\n",
 			    file, line, check_only ? "could sleep" : "sleeping",
-			    lock1->lo_name, lock1->lo_file, lock1->lo_line);
+			    lock1->li_lock->lo_name, lock1->li_file,
+			    lock1->li_line);
 		}
 	if (lock_list == &p->p_sleeplocks) {
 		lock_list = PCPU_PTR(spinlocks);
@@ -1105,20 +1170,40 @@ witness_lock_list_free(struct lock_list_entry *lle)
 	mtx_unlock_spin(&w_mtx);
 }
 
+static struct lock_instance *
+find_instance(struct lock_list_entry *lock_list, struct lock_object *lock)
+{
+	struct lock_list_entry *lle;
+	struct lock_instance *instance;
+	int i;
+
+	for (lle = lock_list; lle != NULL; lle = lle->ll_next)
+		for (i = lle->ll_count - 1; i >= 0; i--) {
+			instance = &lle->ll_children[i];
+			if (instance->li_lock == lock)
+				return (instance);
+		}
+	return (NULL);
+}
+
 int
 witness_list_locks(struct lock_list_entry **lock_list)
 {
 	struct lock_list_entry *lle;
+	struct lock_instance *instance;
 	struct lock_object *lock;
 	int i, nheld;
 
 	nheld = 0;
 	for (lle = *lock_list; lle != NULL; lle = lle->ll_next)
 		for (i = lle->ll_count - 1; i >= 0; i--) {
-			lock = lle->ll_children[i];
-			printf("\t(%s) %s (%p) locked at %s:%d\n",
+			instance = &lle->ll_children[i];
+			lock = instance->li_lock;
+			printf("%s (%s) %s (%p) locked @ %s:%d\n",
+			    (instance->li_flags & LI_EXCLUSIVE) != 0 ?
+			    "exclusive" : "shared",
 			    lock->lo_class->lc_name, lock->lo_name, lock,
-			    lock->lo_file, lock->lo_line);
+			    instance->li_file, instance->li_line);
 			nheld++;
 		}
 	return (nheld);
@@ -1162,27 +1247,43 @@ witness_list(struct proc *p)
 void
 witness_save(struct lock_object *lock, const char **filep, int *linep)
 {
+	struct lock_instance *instance;
 
 	KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
 	if (lock->lo_witness == NULL)
 		return;
 
-	*filep = lock->lo_file;
-	*linep = lock->lo_line;
+	KASSERT(lock->lo_class->lc_flags & LC_SLEEPLOCK,
+	    ("%s: lock (%s) %s is not a sleep lock", __func__,
+	    lock->lo_class->lc_name, lock->lo_name));
+	instance = find_instance(curproc->p_sleeplocks, lock);
+	KASSERT(instance != NULL, ("%s: lock (%s) %s not locked", __func__,
+	    lock->lo_class->lc_name, lock->lo_name));
+	    
+	*filep = instance->li_file;
+	*linep = instance->li_line;
 }
 
 void
 witness_restore(struct lock_object *lock, const char *file, int line)
 {
+	struct lock_instance *instance;
 
 	KASSERT(!witness_cold, ("%s: witness_cold\n", __func__));
 	if (lock->lo_witness == NULL)
 		return;
 
+	KASSERT(lock->lo_class->lc_flags & LC_SLEEPLOCK,
+	    ("%s: lock (%s) %s is not a sleep lock", __func__,
+	    lock->lo_class->lc_name, lock->lo_name));
+	instance = find_instance(curproc->p_sleeplocks, lock);
+	KASSERT(instance != NULL, ("%s: lock (%s) %s not locked", __func__,
+	    lock->lo_class->lc_name, lock->lo_name));
+
 	lock->lo_witness->w_file = file;
 	lock->lo_witness->w_line = line;
-	lock->lo_file = file;
-	lock->lo_line = line;
+	instance->li_file = file;
+	instance->li_line = line;
 }
 
 #ifdef DDB
diff --git a/sys/sys/_lock.h b/sys/sys/_lock.h
index 646ad21..a93c843 100644
--- a/sys/sys/_lock.h
+++ b/sys/sys/_lock.h
@@ -34,8 +34,6 @@
 struct	lock_object {
 	struct	lock_class *lo_class;
 	const	char *lo_name;
-	const	char *lo_file;		/* File and line of last acquire. */
-	int	lo_line;
 	u_int	lo_flags;
 	STAILQ_ENTRY(lock_object) lo_list; /* List of all locks in system. */
 	struct	witness *lo_witness;
diff --git a/sys/sys/lock.h b/sys/sys/lock.h
index a63e3f5..643986a 100644
--- a/sys/sys/lock.h
+++ b/sys/sys/lock.h
@@ -67,8 +67,10 @@ struct	lock_class {
 #define	LO_QUIET	0x00040000	/* Don't log locking operations. */
 #define	LO_RECURSABLE	0x00080000	/* Lock may recurse. */
 #define	LO_SLEEPABLE	0x00100000	/* Lock may be held while sleeping. */
-#define	LO_LOCKED	0x01000000	/* Someone holds this lock. */
-#define	LO_RECURSED	0x02000000	/* Someone has recursed on this lock. */
+
+#define	LI_RECURSEMASK	0x0000ffff	/* Recursion depth of lock instance. */
+#define	LI_SLEPT	0x00010000	/* Lock instance has been slept with. */
+#define	LI_EXCLUSIVE	0x00020000	/* Exclusive lock instance. */
 
 /*
  * Option flags passed to lock operations that witness also needs to know
@@ -77,9 +79,23 @@ struct	lock_class {
 #define	LOP_NOSWITCH	0x00000001	/* Lock doesn't switch on release. */
 #define	LOP_QUIET	0x00000002	/* Don't log locking operations. */
 #define	LOP_TRYLOCK	0x00000004	/* Don't check lock order. */
+#define	LOP_EXCLUSIVE	0x00000008	/* Exclusive lock. */
 
 #ifdef _KERNEL
 /*
+ * Lock instances.  A lock instance is the data associated with a lock while
+ * it is held by witness.  For example, a lock instance will hold the
+ * recursion count of a lock.  Lock instances are held in lists.  Spin locks
+ * are held in a per-cpu list while sleep locks are held in per-process list.
+ */
+struct	lock_instance {
+	struct	lock_object *li_lock;
+	const	char *li_file;		/* File and line of last acquire. */
+	int	li_line;
+	u_int	li_flags;		/* Recursion count and LI_* flags. */
+};
+
+/*
  * A simple list type used to build the list of locks held by a process
  * or CPU.  We can't simply embed the list in struct lock_object since a
  * lock may be held by more than one process if it is a shared lock.  Locks
@@ -89,11 +105,11 @@ struct	lock_class {
  * when we traverse the list we read children[count-1] as the first entry
  * down to children[0] as the final entry.
  */
-#define	LOCK_NCHILDREN	6
+#define	LOCK_NCHILDREN	3
 
 struct	lock_list_entry {
 	struct	lock_list_entry *ll_next;
-	struct	lock_object *ll_children[LOCK_NCHILDREN];
+	struct	lock_instance ll_children[LOCK_NCHILDREN];
 	u_int	ll_count;
 };
 
diff --git a/sys/sys/mutex.h b/sys/sys/mutex.h
index 91ec080..b5418da 100644
--- a/sys/sys/mutex.h
+++ b/sys/sys/mutex.h
@@ -115,9 +115,6 @@ void	_mtx_unlock_spin_flags(struct mtx *m, int opts, const char *file,
 #ifdef INVARIANT_SUPPORT
 void	_mtx_assert(struct mtx *m, int what, const char *file, int line);
 #endif
-#ifdef WITNESS
-void	_mtx_update_flags(struct mtx *m, int locking);
-#endif
 
 /*
  * We define our machine-independent (unoptimized) mutex micro-operations
@@ -205,15 +202,6 @@ void	_mtx_update_flags(struct mtx *m, int locking);
 #endif
 
 /*
- * Update the lock object flags based on the current mutex state.
- */
-#ifdef WITNESS
-#define mtx_update_flags(m, locking)	_mtx_update_flags((m), (locking))
-#else
-#define	mtx_update_flags(m, locking)
-#endif
-
-/*
  * Exported lock manipulation interface.
  *
  * mtx_lock(m) locks MTX_DEF mutex `m'
@@ -277,8 +265,8 @@ void	_mtx_update_flags(struct mtx *m, int locking);
 	_get_sleep_lock((m), curproc, (opts), (file), (line));		\
 	LOCK_LOG_LOCK("LOCK", &(m)->mtx_object, opts, m->mtx_recurse,	\
 	    (file), (line));						\
-	mtx_update_flags((m), 1);					\
-	WITNESS_LOCK(&(m)->mtx_object, (opts), (file), (line));		\
+	WITNESS_LOCK(&(m)->mtx_object, (opts) | LOP_EXCLUSIVE, (file),	\
+	    (line));							\
 } while (0)
 
 #define __mtx_lock_spin_flags(m, opts, file, line) do {			\
@@ -286,28 +274,28 @@ void	_mtx_update_flags(struct mtx *m, int locking);
 	_get_spin_lock((m), curproc, (opts), (file), (line));		\
 	LOCK_LOG_LOCK("LOCK", &(m)->mtx_object, opts, m->mtx_recurse,	\
 	    (file), (line));						\
-	mtx_update_flags((m), 1);					\
-	WITNESS_LOCK(&(m)->mtx_object, (opts), (file), (line));		\
+	WITNESS_LOCK(&(m)->mtx_object, (opts) | LOP_EXCLUSIVE, (file),	\
+	    (line));							\
 } while (0)
 
 #define __mtx_unlock_flags(m, opts, file, line) do {			\
 	MPASS(curproc != NULL);						\
 	mtx_assert((m), MA_OWNED);					\
-	mtx_update_flags((m), 0);					\
-	WITNESS_UNLOCK(&(m)->mtx_object, (opts), (file), (line));	\
-	_rel_sleep_lock((m), curproc, (opts), (file), (line));		\
+	WITNESS_UNLOCK(&(m)->mtx_object, (opts) | LOP_EXCLUSIVE,	\
+	    (file), (line));						\
 	LOCK_LOG_LOCK("UNLOCK", &(m)->mtx_object, (opts),		\
 	    (m)->mtx_recurse, (file), (line));				\
+	_rel_sleep_lock((m), curproc, (opts), (file), (line));		\
 } while (0)
 
 #define __mtx_unlock_spin_flags(m, opts, file, line) do {		\
 	MPASS(curproc != NULL);						\
 	mtx_assert((m), MA_OWNED);					\
-	mtx_update_flags((m), 0);					\
-	WITNESS_UNLOCK(&(m)->mtx_object, (opts), (file), (line));	\
-	_rel_spin_lock((m));						\
+	WITNESS_UNLOCK(&(m)->mtx_object, (opts) | LOP_EXCLUSIVE,	\
+	    (file), (line));						\
 	LOCK_LOG_LOCK("UNLOCK", &(m)->mtx_object, (opts),		\
 	    (m)->mtx_recurse, (file), (line));				\
+	_rel_spin_lock((m));						\
 } while (0)
 
 #define mtx_trylock_flags(m, opts)					\