avoid holding timeout_mutex while interacting with the scheduler.

as noted by haesbaert, this is necessary to avoid deadlocks because
the scheduler can call back into the timeout subsystem while its
holding its own locks.

this happened in two places. firstly, in softclock() it would take
timeout_mutex to find pending work. if that pending work needs a
process context, it would queue the work for the thread and call
wakeup, which enters the scheduler locks. if another cpu is trying
to tsleep (or msleep) with a timeout specified, the sleep code would
be holding the sched lock and call timeout_add, which takes
timeout_mutex.

this is solved by deferring the wakeup to after timeout_mutex is
left. this also has the benefit of mitigating the number of wakeups
done per softclock tick.

secondly, the timeout worker thread takes timeout_mutex and calls
msleep when there's no work to do (ie, the queue is empty). msleep
will take the sched locks. again, if another cpu does a tsleep
with a timeout, you get a deadlock.

to solve this im using sleep_setup and sleep_finish to sleep on an
empty queue, which is safe to do outside the lock as it is comparisons
of the queue head pointers, not derefs of the contents of the queue.

as long as the sleeps and wakeups are ordered correctly with the
enqueue and dequeue operations under the mutex, this all works.
you can think of the queue as a single descriptor ring, and the
wakeup as an interrupt.

the second deadlock was identified by guenther@
ok tedu@ mpi@

1 files changed, 16 insertions, 9 deletions

diff --git a/sys/kern/kern_timeout.c b/sys/kern/kern_timeout.c
index 6c6477e00a9..f3e2fe29c3d 100644
--- a/sys/kern/kern_timeout.c
+++ b/sys/kern/kern_timeout.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: kern_timeout.c,v 1.49 2016/09/22 12:55:24 mpi Exp $	*/
+/*	$OpenBSD: kern_timeout.c,v 1.50 2016/10/03 11:54:29 dlg Exp $	*/
 /*
  * Copyright (c) 2001 Thomas Nordin <nordin@openbsd.org>
  * Copyright (c) 2000-2001 Artur Grabowski <art@openbsd.org>
@@ -375,6 +375,7 @@ softclock(void *arg)
 	int delta;
 	struct circq *bucket;
 	struct timeout *to;
+	int needsproc = 0;
 
 	mtx_enter(&timeout_mutex);
 	while (!CIRCQ_EMPTY(&timeout_todo)) {
@@ -391,7 +392,7 @@ softclock(void *arg)
 			CIRCQ_INSERT(&to->to_list, bucket);
 		} else if (to->to_flags & TIMEOUT_NEEDPROCCTX) {
 			CIRCQ_INSERT(&to->to_list, &timeout_proc);
-			wakeup(&timeout_proc);
+			needsproc = 1;
 		} else {
 #ifdef DEBUG
 			if (delta < 0)
@@ -401,6 +402,9 @@ softclock(void *arg)
 		}
 	}
 	mtx_leave(&timeout_mutex);
+
+	if (needsproc)
+		wakeup(&timeout_proc);
 }
 
 void
@@ -415,6 +419,7 @@ softclock_thread(void *arg)
 {
 	CPU_INFO_ITERATOR cii;
 	struct cpu_info *ci;
+	struct sleep_state sls;
 	struct timeout *to;
 
 	KERNEL_ASSERT_LOCKED();
@@ -427,16 +432,18 @@ softclock_thread(void *arg)
 	KASSERT(ci != NULL);
 	sched_peg_curproc(ci);
 
-	mtx_enter(&timeout_mutex);
 	for (;;) {
-		while (CIRCQ_EMPTY(&timeout_proc))
-			msleep(&timeout_proc, &timeout_mutex, PSWP, "bored", 0);
+		sleep_setup(&sls, &timeout_proc, PSWP, "bored");
+		sleep_finish(&sls, CIRCQ_EMPTY(&timeout_proc));
 
-		to = timeout_from_circq(CIRCQ_FIRST(&timeout_proc));
-		CIRCQ_REMOVE(&to->to_list);
-		timeout_run(to);
+		mtx_enter(&timeout_mutex);
+		while (!CIRCQ_EMPTY(&timeout_proc)) {
+			to = timeout_from_circq(CIRCQ_FIRST(&timeout_proc));
+			CIRCQ_REMOVE(&to->to_list);
+			timeout_run(to);
+		}
+		mtx_leave(&timeout_mutex);
 	}
-	mtx_leave(&timeout_mutex);
 }
 
 #ifndef SMALL_KERNEL