- Change witness_displaydescendants() to accept the indentation level as

  a parameter instead of using the level of a given witness.  When
  recursing, pass an indent level of indent + 1.
- Make use of the information witness_levelall() provides in
  witness_display_list() to use an O(n) algorithm instead of an O(n^2)
  algo to decide which witnesses to display hierarchies from.  Basically,
  we only display a hierarchy for witnesses with a level of 0.
- Add a new per-witness flag that is reset at the start of
  witness_display() for all witness's and is set the first time a witness
  is displayed in witness_displaydescendants().  If a witness is
  encountered more than once in the lock order tree (which happens often),
  witness_displaydescendants() marks the later occurrences with the string
  "(already displayed)" and doesn't display the subtree under that
  witness.  This avoids duplicating large amounts of the lock order tree
  in the 'show witness' output in DDB.

All these changes serve to make 'show witness' a lot more readable and
useful than it was previously.

1 files changed, 25 insertions, 21 deletions

diff --git a/sys/kern/subr_witness.c b/sys/kern/subr_witness.c
index ef8505c..c46276b 100644
--- a/sys/kern/subr_witness.c
+++ b/sys/kern/subr_witness.c
@@ -129,6 +129,7 @@ struct witness {
 	u_char	w_Giant_squawked:1;
 	u_char	w_other_squawked:1;
 	u_char	w_same_squawked:1;
+	u_char	w_displayed:1;
 };
 
 struct witness_child_list_entry {
@@ -166,7 +167,7 @@ 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 *);
+					   struct witness *, int indent);
 static const char *fixup_filename(const char *file);
 static void	witness_leveldescendents(struct witness *parent, int level);
 static void	witness_levelall(void);
@@ -480,25 +481,15 @@ static void
 witness_display_list(void(*prnt)(const char *fmt, ...),
 		     struct witness_list *list)
 {
-	struct witness *w, *w1;
-	int found;
+	struct witness *w;
 
 	STAILQ_FOREACH(w, list, w_typelist) {
-		if (w->w_file == NULL)
-			continue;
-		found = 0;
-		STAILQ_FOREACH(w1, list, w_typelist) {
-			if (isitmychild(w1, w)) {
-				found++;
-				break;
-			}
-		}
-		if (found)
+		if (w->w_file == NULL || w->w_level > 0)
 			continue;
 		/*
 		 * This lock has no anscestors, display its descendants. 
 		 */
-		witness_displaydescendants(prnt, w);
+		witness_displaydescendants(prnt, w, 0);
 	}
 }
 	
@@ -510,6 +501,11 @@ witness_display(void(*prnt)(const char *fmt, ...))
 	KASSERT(!witness_cold, ("%s: witness_cold", __func__));
 	witness_levelall();
 
+	/* Clear all the displayed flags. */
+	STAILQ_FOREACH(w, &w_all, w_list) {
+		w->w_displayed = 0;
+	}
+
 	/*
 	 * First, handle sleep locks which have been acquired at least
 	 * once.
@@ -1376,26 +1372,34 @@ witness_leveldescendents(struct witness *parent, int level)
 
 static void
 witness_displaydescendants(void(*prnt)(const char *fmt, ...),
-			   struct witness *parent)
+			   struct witness *parent, int indent)
 {
 	struct witness_child_list_entry *wcl;
 	int i, level;
 
 	level = parent->w_level;
 	prnt("%-2d", level);
-	for (i = 0; i < level; i++)
+	for (i = 0; i < indent; i++)
 		prnt(" ");
-	if (parent->w_refcount > 0) {
+	if (parent->w_refcount > 0)
 		prnt("%s", parent->w_name);
+	else
+		prnt("(dead)");
+	if (parent->w_displayed) {
+		prnt(" -- (already displayed)\n");
+		return;
+	}
+	parent->w_displayed = 1;
+	if (parent->w_refcount > 0) {
 		if (parent->w_file != NULL)
-			prnt(" -- last acquired @ %s:%d\n", parent->w_file,
+			prnt(" -- last acquired @ %s:%d", parent->w_file,
 			    parent->w_line);
-	} else
-		prnt("(dead)\n");
+	}
+	prnt("\n");
 	for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
 		for (i = 0; i < wcl->wcl_count; i++)
 			    witness_displaydescendants(prnt,
-				wcl->wcl_children[i]);
+				wcl->wcl_children[i], indent + 1);
 }
 
 #ifdef BLESSING