Date: Tue, 24 Jul 2012 19:03:47 +0000 From: gmiller@FreeBSD.org To: svn-soc-all@FreeBSD.org Subject: socsvn commit: r239739 - in soc2012/gmiller/locking-head: . lib/libwitness Message-ID: <20120724190347.485971065672@hub.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: gmiller Date: Tue Jul 24 19:03:47 2012 New Revision: 239739 URL: http://svnweb.FreeBSD.org/socsvn/?view=rev&rev=239739 Log: r239770@FreeBSD-dev: root | 2012-07-23 18:50:02 -0500 Produce an optimized lock order graph. Modified: soc2012/gmiller/locking-head/ (props changed) soc2012/gmiller/locking-head/lib/libwitness/graph.c soc2012/gmiller/locking-head/lib/libwitness/lockinfo.c soc2012/gmiller/locking-head/lib/libwitness/witness.h soc2012/gmiller/locking-head/lib/libwitness/wrappers.c Modified: soc2012/gmiller/locking-head/lib/libwitness/graph.c ============================================================================== --- soc2012/gmiller/locking-head/lib/libwitness/graph.c Tue Jul 24 18:53:28 2012 (r239738) +++ soc2012/gmiller/locking-head/lib/libwitness/graph.c Tue Jul 24 19:03:47 2012 (r239739) @@ -27,6 +27,9 @@ #include "witness.h" +static SLIST_HEAD(graph_root_head, lock_info) graph_roots = + SLIST_HEAD_INITIALIZER(graph_roots); + static int scan_graph(struct lock_info *graph, struct lock_info *lock) { @@ -49,14 +52,44 @@ } static void +optimize_path(struct lock_info *from, struct lock_info *to) +{ + struct lock_info *child; + struct lock_info *previous; + struct lock_info *next; + + previous = NULL; + child = from->child; + while (child != NULL) { + next = child->sibling; + + if (child == to) { + if (previous == NULL) { + from->child = next; + } else { + previous->sibling = next; + } + + if (!scan_graph(from, to)) { + child->sibling = from->child; + from->child = child; + } + } + + child = next; + } +} + +static void optimize_links(struct lock_info *to) { - to = to; - /* - XXX find first node with multiple children, then start scanning for - multiple paths to "to" from any node with multiple children and - a link to "to" - */ + struct lock_info *from; + + SLIST_FOREACH(from, &graph_roots, root_next) { + if (scan_graph(from, to)) { + optimize_path(from, to); + } + } } int @@ -70,6 +103,8 @@ return (-1); } + SLIST_REMOVE(&graph_roots, from, lock_info, root_next); + to->sibling = from->child; from->child = to; @@ -77,3 +112,15 @@ return (0); } + +void +add_root(struct lock_info *root) +{ + SLIST_INSERT_HEAD(&graph_roots, root, root_next); +} + +void +reset_graph(void) +{ + SLIST_INIT(&graph_roots); +} Modified: soc2012/gmiller/locking-head/lib/libwitness/lockinfo.c ============================================================================== --- soc2012/gmiller/locking-head/lib/libwitness/lockinfo.c Tue Jul 24 18:53:28 2012 (r239738) +++ soc2012/gmiller/locking-head/lib/libwitness/lockinfo.c Tue Jul 24 19:03:47 2012 (r239739) @@ -39,7 +39,7 @@ struct lock_info * lookup_lock(void *lock) { - struct lock_info *info; + struct lock_info *info = NULL; SLIST_FOREACH(info, &lock_info_head, lock_info_next) { if (info->lock == lock && info->active) { @@ -58,6 +58,7 @@ SLIST_INIT(&info->bless_head); SLIST_INSERT_HEAD(&lock_info_head, info, lock_info_next); + add_root(info); } } Modified: soc2012/gmiller/locking-head/lib/libwitness/witness.h ============================================================================== --- soc2012/gmiller/locking-head/lib/libwitness/witness.h Tue Jul 24 18:53:28 2012 (r239738) +++ soc2012/gmiller/locking-head/lib/libwitness/witness.h Tue Jul 24 19:03:47 2012 (r239739) @@ -41,6 +41,7 @@ struct lock_info { SLIST_ENTRY(lock_info) lock_info_next; + SLIST_ENTRY(lock_info) root_next; void *lock; int active; struct lock_info *child; @@ -51,10 +52,13 @@ extern pthread_mutex_t witness_mtx; +void add_root(struct lock_info *root); void add_lock(struct lock_info *lock); void remove_lock(struct lock_info *lock); int insert_lock(struct lock_info *new_lock, struct lock_info *previous); +void reset_graph(void); + void reset_lists(void); void log_reversal(struct lock_info *lock, Modified: soc2012/gmiller/locking-head/lib/libwitness/wrappers.c ============================================================================== --- soc2012/gmiller/locking-head/lib/libwitness/wrappers.c Tue Jul 24 18:53:28 2012 (r239738) +++ soc2012/gmiller/locking-head/lib/libwitness/wrappers.c Tue Jul 24 19:03:47 2012 (r239739) @@ -445,6 +445,7 @@ _pthread_mutex_lock(&witness_mtx); reset_lists(); + reset_graph(); reset_lock_info(); _pthread_mutex_unlock(&witness_mtx);
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20120724190347.485971065672>