valid dup lock logic for witness

[John-Mark Gurney]

I have been working on kqueue, and to support kq in kq, I need to obtain
two kq locks (both of the same type) at the same time.  Normally this can
cause a deadlock, but using a proper lock ordering strategy, it can be
avoided.  In the kq case, I chose to aquire a kq global lock before
acquiring multiple kq locks.  (In the proc case, jhb said you aquire
the child's before the parents.)

Mutexs have the flag MTX_DUPOK that notify witness that duplicate locks
are ok, but this can hide other problems (and in fact would have in my
testing).

I have created a patch that lets you inform witness the a duplicate lock
is valid as long as you hold another lock.  The only run time change is
that when a duplicate lock is found, it will run through another table
to verify it's ok before printing out the back trace.

Anyone have objections to this?

-- 
  John-Mark Gurney				Voice: +1 415 225 5579

     "All that I will do, has been done, All that I have, has not."
-------------- next part --------------
Index: subr_witness.c
===================================================================
RCS file: /usr/src/FreeBSD/src/sys/kern/subr_witness.c,v
retrieving revision 1.176
diff -u -r1.176 subr_witness.c
--- subr_witness.c	10 Jul 2004 21:42:16 -0000	1.176
+++ subr_witness.c	5 Aug 2004 21:22:22 -0000
@@ -155,6 +155,13 @@
 	struct	lock_class *w_class;
 };
 
+struct witness_order_dup_list_entry {
+	const	char *w_name_dup;
+	struct	lock_class *w_class_dup;
+	const	char *w_name_parent;
+	struct	lock_class *w_class_parent;
+};
+
 #ifdef BLESSING
 static int	blessed(struct witness *, struct witness *);
 #endif
@@ -183,6 +190,7 @@
 static void	witness_lock_list_free(struct lock_list_entry *lle);
 static struct	lock_instance *find_instance(struct lock_list_entry *lock_list,
 					     struct lock_object *lock);
+static int	dup_lock_ok(struct lock_list_entry *lock_list);
 static void	witness_list_lock(struct lock_instance *instance);
 #ifdef DDB
 static void	witness_list(struct thread *td);
@@ -366,6 +374,11 @@
 	{ NULL, NULL }
 };
 
+static struct witness_order_dup_list_entry dup_order_lists[] = {
+	{ "kqueue", &lock_class_mtx_sleep,
+		"kqueue order", &lock_class_mtx_sleep },
+};
+
 #ifdef BLESSING
 /*
  * Pairs of locks which have been blessed
@@ -764,6 +777,8 @@
 	if (w1 == w) {
 		if (w->w_same_squawked || (lock->lo_flags & LO_DUPOK))
 			return;
+		if (dup_lock_ok(*lock_list))
+			return;
 		w->w_same_squawked = 1;
 		printf("acquiring duplicate lock of same type: \"%s\"\n", 
 			lock->lo_type);
@@ -1692,6 +1707,32 @@
 				return (instance);
 		}
 	return (NULL);
+}
+
+static int
+dup_lock_ok(struct lock_list_entry *lock_list)
+{
+	struct lock_instance *lock;
+	struct lock_object *lo;
+	struct witness_order_dup_list_entry *wdup;
+	int i, j;
+
+	for (i = 0; i < sizeof dup_order_lists / sizeof *dup_order_lists; i++) {
+		lock = &lock_list->ll_children[lock_list->ll_count - 1];
+		wdup = &dup_order_lists[i];
+		lo = lock->li_lock;
+		if (strcmp(lo->lo_type, wdup->w_name_dup) == 0 &&
+		    lo->lo_class == wdup->w_class_dup) {
+			for (j = lock_list->ll_count - 1; j >= 0; j--) {
+				lo = lock_list->ll_children[j].li_lock;
+				if (strcmp(lo->lo_type, wdup->w_name_parent) ==
+				    0 && lo->lo_class == wdup->w_class_parent)
+					return 1;
+			}
+		}
+	}
+
+	return 0;
 }
 
 static void