Date: Thu, 5 Jan 2006 11:22:16 -0800 (PST) From: Don Lewis <truckman@FreeBSD.org> To: stable@FreeBSD.org Subject: WITNESS speedup patch for RELENG_5 Message-ID: <200601051922.k05JMGMc015613@gw.catspoiler.org>
next in thread | raw e-mail | index | archive | help
If you are running RELENG_5 and using WITNESS, you might want to try the
patch below. It speeds up WITNESS rather dramatically. This patch was
committed to HEAD in late August (subr_witness.c 1.198) and early
September (subr_witness.c 1.200). It was MFC'ed to RELENG_6 in the last
few days. I'd like to MFC it to RELENG_5, but I think it should get a
bit more exposure before I do.
Index: sys/kern/subr_witness.c
===================================================================
RCS file: /home/ncvs/src/sys/kern/subr_witness.c,v
retrieving revision 1.178.2.8
diff -u -r1.178.2.8 subr_witness.c
--- sys/kern/subr_witness.c 4 May 2005 19:26:30 -0000 1.178.2.8
+++ sys/kern/subr_witness.c 12 Sep 2005 04:52:53 -0000
@@ -165,16 +165,9 @@
static int isitmychild(struct witness *parent, struct witness *child);
static int isitmydescendant(struct witness *parent, struct witness *child);
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 int sysctl_debug_witness_watch(SYSCTL_HANDLER_ARGS);
-static void witness_displaydescendants(void(*)(const char *fmt, ...),
- 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);
static struct witness *witness_get(void);
static void witness_free(struct witness *m);
static struct witness_child_list_entry *witness_child_get(void);
@@ -185,20 +178,21 @@
struct lock_object *lock);
static void witness_list_lock(struct lock_instance *instance);
#ifdef DDB
-static void witness_list(struct thread *td);
+static void witness_leveldescendents(struct witness *parent, int level);
+static void witness_levelall(void);
+static void witness_displaydescendants(void(*)(const char *fmt, ...),
+ struct witness *, int indent);
static void witness_display_list(void(*prnt)(const char *fmt, ...),
struct witness_list *list);
static void witness_display(void(*)(const char *fmt, ...));
+static void witness_list(struct thread *td);
#endif
SYSCTL_NODE(_debug, OID_AUTO, witness, CTLFLAG_RW, 0, "Witness Locking");
/*
- * If set to 0, witness is disabled. If set to 1, witness performs full lock
- * order checking for all locks. If set to 2 or higher, then witness skips
- * the full lock order check if the lock being acquired is at a higher level
- * (i.e. farther down in the tree) than the current lock. This last mode is
- * somewhat experimental and not considered fully safe. At runtime, this
+ * If set to 0, witness is disabled. If set to a non-zero value, witness
+ * performs full lock order checking for all locks. At runtime, this
* value may be set to 0 to turn off witness. witness is not allowed be
* turned on once it is turned off, however.
*/
@@ -250,6 +244,16 @@
static struct witness_child_list_entry *w_child_free = NULL;
static struct lock_list_entry *w_lock_list_free = NULL;
+static int w_free_cnt, w_spin_cnt, w_sleep_cnt, w_child_free_cnt, w_child_cnt;
+SYSCTL_INT(_debug_witness, OID_AUTO, free_cnt, CTLFLAG_RD, &w_free_cnt, 0, "");
+SYSCTL_INT(_debug_witness, OID_AUTO, spin_cnt, CTLFLAG_RD, &w_spin_cnt, 0, "");
+SYSCTL_INT(_debug_witness, OID_AUTO, sleep_cnt, CTLFLAG_RD, &w_sleep_cnt, 0,
+ "");
+SYSCTL_INT(_debug_witness, OID_AUTO, child_free_cnt, CTLFLAG_RD,
+ &w_child_free_cnt, 0, "");
+SYSCTL_INT(_debug_witness, OID_AUTO, child_cnt, CTLFLAG_RD, &w_child_cnt, 0,
+ "");
+
static struct witness w_data[WITNESS_COUNT];
static struct witness_child_list_entry w_childdata[WITNESS_CHILDCOUNT];
static struct lock_list_entry w_locklistdata[LOCK_CHILDCOUNT];
@@ -575,6 +579,87 @@
#ifdef DDB
static void
+witness_levelall (void)
+{
+ struct witness_list *list;
+ struct witness *w, *w1;
+
+ /*
+ * First clear all levels.
+ */
+ STAILQ_FOREACH(w, &w_all, w_list) {
+ w->w_level = 0;
+ }
+
+ /*
+ * Look for locks with no parent and level all their descendants.
+ */
+ STAILQ_FOREACH(w, &w_all, w_list) {
+ /*
+ * This is just an optimization, technically we could get
+ * away just walking the all list each time.
+ */
+ if (w->w_class->lc_flags & LC_SLEEPLOCK)
+ list = &w_sleep;
+ else
+ list = &w_spin;
+ STAILQ_FOREACH(w1, list, w_typelist) {
+ if (isitmychild(w1, w))
+ goto skip;
+ }
+ witness_leveldescendents(w, 0);
+ skip:
+ ; /* silence GCC 3.x */
+ }
+}
+
+static void
+witness_leveldescendents(struct witness *parent, int level)
+{
+ struct witness_child_list_entry *wcl;
+ int i;
+
+ if (parent->w_level < level)
+ parent->w_level = level;
+ level++;
+ for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
+ for (i = 0; i < wcl->wcl_count; i++)
+ witness_leveldescendents(wcl->wcl_children[i], level);
+}
+
+static void
+witness_displaydescendants(void(*prnt)(const char *fmt, ...),
+ 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 < indent; i++)
+ prnt(" ");
+ 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", parent->w_file,
+ parent->w_line);
+ }
+ 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], indent + 1);
+}
+
+static void
witness_display_list(void(*prnt)(const char *fmt, ...),
struct witness_list *list)
{
@@ -795,18 +880,11 @@
MPASS(!mtx_owned(&w_mtx));
mtx_lock_spin(&w_mtx);
/*
- * If we have a known higher number just say ok
- */
- if (witness_watch > 1 && w->w_level > w1->w_level) {
- mtx_unlock_spin(&w_mtx);
- return;
- }
- /*
* If we know that the the lock we are acquiring comes after
* the lock we most recently acquired in the lock order tree,
* then there is no need for any further checks.
*/
- if (isitmydescendant(w1, w)) {
+ if (isitmychild(w1, w)) {
mtx_unlock_spin(&w_mtx);
return;
}
@@ -1287,11 +1365,13 @@
w->w_class = lock_class;
w->w_refcount = 1;
STAILQ_INSERT_HEAD(&w_all, w, w_list);
- if (lock_class->lc_flags & LC_SPINLOCK)
+ if (lock_class->lc_flags & LC_SPINLOCK) {
STAILQ_INSERT_HEAD(&w_spin, w, w_typelist);
- else if (lock_class->lc_flags & LC_SLEEPLOCK)
+ w_spin_cnt++;
+ } else if (lock_class->lc_flags & LC_SLEEPLOCK) {
STAILQ_INSERT_HEAD(&w_sleep, w, w_typelist);
- else {
+ w_sleep_cnt++;
+ } else {
mtx_unlock_spin(&w_mtx);
panic("lock class %s is not sleep or spin",
lock_class->lc_name);
@@ -1309,10 +1389,13 @@
struct witness *parent;
MPASS(w->w_refcount == 0);
- if (w->w_class->lc_flags & LC_SLEEPLOCK)
+ if (w->w_class->lc_flags & LC_SLEEPLOCK) {
list = &w_sleep;
- else
+ w_sleep_cnt--;
+ } else {
list = &w_spin;
+ w_spin_cnt--;
+ }
/*
* First, we run through the entire tree looking for any
* witnesses that the outgoing witness is a child of. For
@@ -1323,8 +1406,6 @@
if (!isitmychild(parent, w))
continue;
removechild(parent, w);
- if (!reparentchildren(parent, w))
- return (0);
}
/*
@@ -1333,6 +1414,7 @@
*/
for (wcl = w->w_children; wcl != NULL; wcl = nwcl) {
nwcl = wcl->wcl_next;
+ w_child_cnt--;
witness_child_free(wcl);
}
@@ -1343,34 +1425,6 @@
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);
}
@@ -1395,31 +1449,13 @@
*wcl = witness_child_get();
if (*wcl == NULL)
return (0);
+ w_child_cnt++;
}
(*wcl)->wcl_children[(*wcl)->wcl_count++] = child;
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)
@@ -1441,7 +1477,7 @@
list = &w_sleep;
else
list = &w_spin;
- return (rebalancetree(list));
+ return (1);
}
static void
@@ -1465,6 +1501,7 @@
return;
wcl1 = *wcl;
*wcl = wcl1->wcl_next;
+ w_child_cnt--;
witness_child_free(wcl1);
}
@@ -1503,87 +1540,6 @@
return (0);
}
-static void
-witness_levelall (void)
-{
- struct witness_list *list;
- struct witness *w, *w1;
-
- /*
- * First clear all levels.
- */
- STAILQ_FOREACH(w, &w_all, w_list) {
- w->w_level = 0;
- }
-
- /*
- * Look for locks with no parent and level all their descendants.
- */
- STAILQ_FOREACH(w, &w_all, w_list) {
- /*
- * This is just an optimization, technically we could get
- * away just walking the all list each time.
- */
- if (w->w_class->lc_flags & LC_SLEEPLOCK)
- list = &w_sleep;
- else
- list = &w_spin;
- STAILQ_FOREACH(w1, list, w_typelist) {
- if (isitmychild(w1, w))
- goto skip;
- }
- witness_leveldescendents(w, 0);
- skip:
- ; /* silence GCC 3.x */
- }
-}
-
-static void
-witness_leveldescendents(struct witness *parent, int level)
-{
- struct witness_child_list_entry *wcl;
- int i;
-
- if (parent->w_level < level)
- parent->w_level = level;
- level++;
- for (wcl = parent->w_children; wcl != NULL; wcl = wcl->wcl_next)
- for (i = 0; i < wcl->wcl_count; i++)
- witness_leveldescendents(wcl->wcl_children[i], level);
-}
-
-static void
-witness_displaydescendants(void(*prnt)(const char *fmt, ...),
- 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 < indent; i++)
- prnt(" ");
- 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", parent->w_file,
- parent->w_line);
- }
- 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], indent + 1);
-}
-
#ifdef BLESSING
static int
blessed(struct witness *w1, struct witness *w2)
@@ -1623,6 +1579,7 @@
}
w = STAILQ_FIRST(&w_free);
STAILQ_REMOVE_HEAD(&w_free, w_list);
+ w_free_cnt--;
bzero(w, sizeof(*w));
return (w);
}
@@ -1632,6 +1589,7 @@
{
STAILQ_INSERT_HEAD(&w_free, w, w_list);
+ w_free_cnt++;
}
static struct witness_child_list_entry *
@@ -1651,6 +1609,7 @@
return (NULL);
}
w_child_free = wcl->wcl_next;
+ w_child_free_cnt--;
bzero(wcl, sizeof(*wcl));
return (wcl);
}
@@ -1661,6 +1620,7 @@
wcl->wcl_next = w_child_free;
w_child_free = wcl;
+ w_child_free_cnt++;
}
static struct lock_list_entry *
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200601051922.k05JMGMc015613>