- Split the itismychild() function into two functions: insertchild()

  adds a witness to the child list of a parent witness.  rebalancetree()
  runs through the entire tree removing direct descendants of witnesses
  who already have said child witness as an indirect descendant through
  another direct descendant.  itismychild() now calls insertchild()
  followed by rebalancetree() and no longer needs the evil hack of
  having static recursed variable.
- Add a function reparentchildren() that adds all the direct descendants
  of one witness as direct descendants of another witness.
- Change the return value of itismychild() and similar functions so that
  they return 0 in the case of failure due to lack of resources instead
  of 1.  This makes the return value more intuitive.
- Check the return value of itismychild() when defining the static lock
  order in witness_initialize().
- Don't try to setup a lock instance in witness_lock() if itismychild()
  fails.  Witness is hosed anyways so no need to do any more witness
  related activity at that point.  It also makes the code flow easier to
  understand.
- Add a new depart() function as the opposite of enroll().  When the
  reference count of a witness drops to 0 in witness_destroy(), this
  function is called on that witness.  First, it runs through the
  lock order tree using reparentchildren() to reparent direct descendants
  of the departing witness to each of the witness' parents in the tree.
  Next, it releases it's own child list and other associated resources.
  Finally it calls rebalanacetree() to rebalance the lock order tree.
- Sort function prototypes into something closer to alphabetical order.

As a result of these changes, there should no longer be 'dead' witnesses
in the order tree, and repeatedly loading and unloading a module should no
longer exhaust witness of its internal resources.

Inspired by:	gallatin

1 files changed, 144 insertions, 42 deletions

diff --git a/sys/kern/subr_witness.c b/sys/kern/subr_witness.c
index f032a04..ef8505c 100644
--- a/sys/kern/subr_witness.c
+++ b/sys/kern/subr_witness.c
@@ -151,15 +151,20 @@ struct witness_order_list_entry {
 	struct	lock_class *w_class;
 };
 
+#ifdef BLESSING
+static int	blessed(struct witness *, struct witness *);
+#endif
+static int	depart(struct witness *w);
 static struct	witness *enroll(const char *description,
 				struct lock_class *lock_class);
-static int	itismychild(struct witness *parent, struct witness *child);
-static void	removechild(struct witness *parent, struct witness *child);
+static int	insertchild(struct witness *parent, struct witness *child);
 static int	isitmychild(struct witness *parent, struct witness *child);
 static int	isitmydescendant(struct witness *parent, struct witness *child);
-#ifdef BLESSING
-static int	blessed(struct witness *, struct witness *);
-#endif
+static int	itismychild(struct witness *parent, struct witness *child);
+static int	rebalancetree(struct witness_list *list);
+static void	removechild(struct witness *parent, struct witness *child);
+static int	reparentchildren(struct witness *newparent,
+		    struct witness *oldparent);
 static void	witness_displaydescendants(void(*)(const char *fmt, ...),
 					   struct witness *);
 static const char *fixup_filename(const char *file);
@@ -376,7 +381,8 @@ witness_initialize(void *dummy __unused)
 			if (w1 == NULL)
 				continue;
 			w1->w_file = "order list";
-			itismychild(w, w1);
+			if (!itismychild(w, w1))
+				panic("Not enough memory for static orders!");
 			w = w1;
 		}
 	}
@@ -453,7 +459,13 @@ witness_destroy(struct lock_object *lock)
 		mtx_lock_spin(&w_mtx);
 		MPASS(w->w_refcount > 0);
 		w->w_refcount--;
-		mtx_unlock_spin(&w_mtx);
+
+		/*
+		 * Lock is already released if we have an allocation failure
+		 * and depart() fails.
+		 */
+		if (w->w_refcount != 0 || depart(w))
+			mtx_unlock_spin(&w_mtx);
 	}
 
 	mtx_lock(&all_mtx);
@@ -775,15 +787,15 @@ witness_lock(struct lock_object *lock, int flags, const char *file, int line)
 	 * Giant if it is the wrong direction.  The real lock order is that
 	 * sleepable locks come before Giant.
 	 */
-	if (lock1->li_lock == &Giant.mtx_object &&
-	    (lock->lo_flags & LO_SLEEPABLE) != 0)
-		mtx_unlock_spin(&w_mtx);
-	else {
+	if (!(lock1->li_lock == &Giant.mtx_object &&
+	    (lock->lo_flags & LO_SLEEPABLE) != 0)) {
 		CTR3(KTR_WITNESS, "%s: adding %s as a child of %s", __func__,
 		    lock->lo_type, lock1->li_lock->lo_type);
 		if (!itismychild(lock1->li_lock->lo_witness, w))
-			mtx_unlock_spin(&w_mtx);
+			/* Witness is dead. */
+			return;
 	} 
+	mtx_unlock_spin(&w_mtx);
 
 out:
 #ifdef DDB
@@ -1109,20 +1121,91 @@ enroll(const char *description, struct lock_class *lock_class)
 	return (w);
 }
 
+/* Don't let the door bang you on the way out... */
 static int
-itismychild(struct witness *parent, struct witness *child)
+depart(struct witness *w)
 {
-	static int recursed;
-	struct witness_child_list_entry **wcl;
+	struct witness_child_list_entry *wcl, *nwcl;
 	struct witness_list *list;
+	struct witness *parent;
+
+	MPASS(w->w_refcount == 0);
+	if (w->w_class->lc_flags & LC_SLEEPLOCK)
+		list = &w_sleep;
+	else
+		list = &w_spin;
+	/*
+	 * First, we run through the entire tree looking for any
+	 * witnesses that the outgoing witness is a child of.  For
+	 * each parent that we find, we reparent all the direct
+	 * children of the outgoing witness to its parent.
+	 */
+	STAILQ_FOREACH(parent, list, w_typelist) {
+		if (!isitmychild(parent, w))
+			continue;
+		removechild(parent, w);
+		if (!reparentchildren(parent, w))
+			return (0);
+	}
+
+	/*
+	 * Now we go through and free up the child list of the
+	 * outgoing witness.
+	 */
+	for (wcl = w->w_children; wcl != NULL; wcl = nwcl) {
+		nwcl = wcl->wcl_next;
+		witness_child_free(wcl);
+	}
+
+	/*
+	 * Detach from various lists and free.
+	 */
+	STAILQ_REMOVE(list, w, witness, w_typelist);
+	STAILQ_REMOVE(&w_all, w, witness, w_list);
+	witness_free(w);
+
+	/* Finally, fixup the tree. */
+	return (rebalancetree(list));
+}
+
+
+/*
+ * Prune an entire lock order tree.  We look for cases where a lock
+ * is now both a descendant and a direct child of a given lock.  In
+ * that case, we want to remove the direct child link from the tree.
+ *
+ * Returns false if insertchild() fails.
+ */
+static int
+rebalancetree(struct witness_list *list)
+{
+	struct witness *child, *parent;
+
+	STAILQ_FOREACH(child, list, w_typelist) {
+		STAILQ_FOREACH(parent, list, w_typelist) {
+			if (!isitmychild(parent, child))
+				continue;
+			removechild(parent, child);
+			if (isitmydescendant(parent, child))
+				continue;
+			if (!insertchild(parent, child))
+				return (0);
+		}
+	}
+	witness_levelall();
+	return (1);
+}
+
+/*
+ * Add "child" as a direct child of "parent".  Returns false if
+ * we fail due to out of memory.
+ */
+static int
+insertchild(struct witness *parent, struct witness *child)
+{
+	struct witness_child_list_entry **wcl;
 
 	MPASS(child != NULL && parent != NULL);
-	if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
-	    (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
-		panic(
-		"%s: parent (%s) and child (%s) are not the same lock type",
-		    __func__, parent->w_class->lc_name,
-		    child->w_class->lc_name);
 
 	/*
 	 * Insert "child" after "parent"
@@ -1133,35 +1216,54 @@ itismychild(struct witness *parent, struct witness *child)
 	if (*wcl == NULL) {
 		*wcl = witness_child_get();
 		if (*wcl == NULL)
-			return (1);
+			return (0);
 	}
 	(*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
 
-	/*
-	 * Now prune whole tree.  We look for cases where a lock is now
-	 * both a descendant and a direct child of a given lock.  In that
-	 * case, we want to remove the direct child link from the tree.
-	 */
-	if (recursed)
+	return (1);
+}
+
+/*
+ * Make all the direct descendants of oldparent be direct descendants
+ * of newparent.
+ */
+static int
+reparentchildren(struct witness *newparent, struct witness *oldparent)
+{
+	struct witness_child_list_entry *wcl;
+	int i;
+
+	/* Avoid making a witness a child of itself. */
+	MPASS(!isitmychild(oldparent, newparent));
+	
+	for (wcl = oldparent->w_children; wcl != NULL; wcl = wcl->wcl_next)
+		for (i = 0; i < wcl->wcl_count; i++)
+			if (!insertchild(newparent, wcl->wcl_children[i]))
+				return (0);
+	return (1);
+}
+
+static int
+itismychild(struct witness *parent, struct witness *child)
+{
+	struct witness_list *list;
+
+	MPASS(child != NULL && parent != NULL);
+	if ((parent->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)) !=
+	    (child->w_class->lc_flags & (LC_SLEEPLOCK | LC_SPINLOCK)))
+		panic(
+		"%s: parent (%s) and child (%s) are not the same lock type",
+		    __func__, parent->w_class->lc_name,
+		    child->w_class->lc_name);
+
+	if (!insertchild(parent, child))
 		return (0);
-	recursed = 1;
+
 	if (parent->w_class->lc_flags & LC_SLEEPLOCK)
 		list = &w_sleep;
 	else
 		list = &w_spin;
-	STAILQ_FOREACH(child, list, w_typelist) {
-		STAILQ_FOREACH(parent, list, w_typelist) {
-			if (!isitmychild(parent, child))
-				continue;
-			removechild(parent, child);
-			if (isitmydescendant(parent, child))
-				continue;
-			itismychild(parent, child);
-		}
-	}
-	recursed = 0;
-	witness_levelall();
-	return (0);
+	return (rebalancetree(list));
 }
 
 static void