Add lock order checking for timeouts

The caller of timeout_barrier() must not hold locks that could prevent
timeout handlers from making progress. The system could deadlock
otherwise.

This patch makes witness(4) able to detect barrier locking errors.
This is done by introducing a pseudo-lock that couples the lock chains
of barrier callers to the lock chains of timeout handlers.

In order to find these errors faster, this diff adds a synchronous
version of cancelling timeouts, timeout_del_barrier(9). As the
synchronous intent is explicit, this interface can check lock order
immediately instead of waiting for the potentially rare occurrence of
timeout_barrier(9).

OK dlg@ mpi@

3 files changed, 85 insertions, 5 deletions

diff --git a/share/man/man9/timeout.9 b/share/man/man9/timeout.9
index af5be306b90..2c846bd65ce 100644
--- a/share/man/man9/timeout.9
+++ b/share/man/man9/timeout.9
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: timeout.9,v 1.45 2017/11/24 02:36:53 dlg Exp $
+.\"	$OpenBSD: timeout.9,v 1.46 2019/04/14 08:51:31 visa Exp $
 .\"
 .\" Copyright (c) 2000 Artur Grabowski <art@openbsd.org>
 .\" All rights reserved.
@@ -23,7 +23,7 @@
 .\" OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 .\" ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: November 24 2017 $
+.Dd $Mdocdate: April 14 2019 $
 .Dt TIMEOUT_SET 9
 .Os
 .Sh NAME
@@ -38,6 +38,7 @@
 .Nm timeout_add_ts ,
 .Nm timeout_add_bt ,
 .Nm timeout_del ,
+.Nm timeout_del_barrier ,
 .Nm timeout_barrier ,
 .Nm timeout_pending ,
 .Nm timeout_initialized ,
@@ -55,6 +56,8 @@
 .Fn timeout_add "struct timeout *to" "int ticks"
 .Ft int
 .Fn timeout_del "struct timeout *to"
+.Ft int
+.Fn timeout_del_barrier "struct timeout *to"
 .Ft void
 .Fn timeout_barrier "struct timeout *to"
 .Ft int
@@ -156,6 +159,11 @@ will cancel the timeout in the argument
 If the timeout has already executed or has never been added
 the call will have no effect.
 .Pp
+.Fn timeout_del_barrier
+is like
+.Fn timeout_del
+but it will wait until any current execution of the timeout has completed.
+.Pp
 .Fn timeout_barrier
 ensures that any current execution of the timeout in the argument
 .Fa to
@@ -232,6 +240,8 @@ interrupt context at or below
 .Dv IPL_CLOCK .
 .Pp
 .Fn timeout_barrier
+and
+.Fn timeout_del_barrier
 can be called from process context.
 .Pp
 When the timeout runs, the
@@ -258,6 +268,8 @@ will return 1 if the timeout
 was added to the timeout schedule or 0 if it was already queued.
 .Pp
 .Fn timeout_del
+and
+.Fn timeout_del_barrier
 will return 1 if the timeout
 .Fa to
 was removed from the pending timeout schedule or 0 if it was not
diff --git a/sys/kern/kern_timeout.c b/sys/kern/kern_timeout.c
index e34dc6aaf08..17ed988c12f 100644
--- a/sys/kern/kern_timeout.c
+++ b/sys/kern/kern_timeout.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: kern_timeout.c,v 1.53 2017/12/14 02:42:18 dlg Exp $	*/
+/*	$OpenBSD: kern_timeout.c,v 1.54 2019/04/14 08:51:31 visa Exp $	*/
 /*
  * Copyright (c) 2001 Thomas Nordin <nordin@openbsd.org>
  * Copyright (c) 2000-2001 Artur Grabowski <art@openbsd.org>
@@ -32,6 +32,7 @@
 #include <sys/mutex.h>
 #include <sys/kernel.h>
 #include <sys/queue.h>			/* _Q_INVALIDATE */
+#include <sys/witness.h>
 
 #ifdef DDB
 #include <machine/db_machdep.h>
@@ -131,6 +132,47 @@ struct mutex timeout_mutex = MUTEX_INITIALIZER(IPL_HIGH);
 void softclock_thread(void *);
 void softclock_create_thread(void *);
 
+#ifdef WITNESS
+struct lock_object timeout_sleeplock_obj = {
+	.lo_name = "timeout",
+	.lo_flags = LO_WITNESS | LO_INITIALIZED | LO_SLEEPABLE |
+	    (LO_CLASS_RWLOCK << LO_CLASSSHIFT)
+};
+struct lock_object timeout_spinlock_obj = {
+	.lo_name = "timeout",
+	.lo_flags = LO_WITNESS | LO_INITIALIZED |
+	    (LO_CLASS_MUTEX << LO_CLASSSHIFT)
+};
+struct lock_type timeout_sleeplock_type = {
+	.lt_name = "timeout"
+};
+struct lock_type timeout_spinlock_type = {
+	.lt_name = "timeout"
+};
+#define TIMEOUT_LOCK_OBJ(needsproc) \
+	((needsproc) ? &timeout_sleeplock_obj : &timeout_spinlock_obj)
+#endif
+
+static void
+timeout_sync_order(int needsproc)
+{
+	WITNESS_CHECKORDER(TIMEOUT_LOCK_OBJ(needsproc),
+	    LOP_NEWORDER, __FILE__, __LINE__, NULL);
+}
+
+static void
+timeout_sync_enter(int needsproc)
+{
+	timeout_sync_order(needsproc);
+	WITNESS_LOCK(TIMEOUT_LOCK_OBJ(needsproc), 0, __FILE__, __LINE__);
+}
+
+static void
+timeout_sync_leave(int needsproc)
+{
+	WITNESS_UNLOCK(TIMEOUT_LOCK_OBJ(needsproc), 0, __FILE__, __LINE__);
+}
+
 /*
  * Some of the "math" in here is a bit tricky.
  *
@@ -159,6 +201,9 @@ timeout_startup(void)
 void
 timeout_proc_init(void)
 {
+	WITNESS_INIT(&timeout_sleeplock_obj, &timeout_sleeplock_type);
+	WITNESS_INIT(&timeout_spinlock_obj, &timeout_spinlock_type);
+
 	kthread_create_deferred(softclock_create_thread, NULL);
 }
 
@@ -324,12 +369,30 @@ timeout_del(struct timeout *to)
 	return (ret);
 }
 
+int
+timeout_del_barrier(struct timeout *to)
+{
+	int removed;
+
+	timeout_sync_order(ISSET(to->to_flags, TIMEOUT_NEEDPROCCTX));
+
+	removed = timeout_del(to);
+	if (!removed)
+		timeout_barrier(to);
+
+	return (removed);
+}
+
 void	timeout_proc_barrier(void *);
 
 void
 timeout_barrier(struct timeout *to)
 {
-	if (!ISSET(to->to_flags, TIMEOUT_NEEDPROCCTX)) {
+	int needsproc = ISSET(to->to_flags, TIMEOUT_NEEDPROCCTX);
+
+	timeout_sync_order(needsproc);
+
+	if (!needsproc) {
 		KERNEL_LOCK();
 		splx(splsoftclock());
 		KERNEL_UNLOCK();
@@ -389,6 +452,7 @@ timeout_run(struct timeout *to)
 {
 	void (*fn)(void *);
 	void *arg;
+	int needsproc;
 
 	MUTEX_ASSERT_LOCKED(&timeout_mutex);
 
@@ -397,9 +461,12 @@ timeout_run(struct timeout *to)
 
 	fn = to->to_func;
 	arg = to->to_arg;
+	needsproc = ISSET(to->to_flags, TIMEOUT_NEEDPROCCTX);
 
 	mtx_leave(&timeout_mutex);
+	timeout_sync_enter(needsproc);
 	fn(arg);
+	timeout_sync_leave(needsproc);
 	mtx_enter(&timeout_mutex);
 }
 
diff --git a/sys/sys/timeout.h b/sys/sys/timeout.h
index 9aaa4ffdf88..0e38ce8a588 100644
--- a/sys/sys/timeout.h
+++ b/sys/sys/timeout.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: timeout.h,v 1.27 2017/11/24 02:36:53 dlg Exp $	*/
+/*	$OpenBSD: timeout.h,v 1.28 2019/04/14 08:51:31 visa Exp $	*/
 /*
  * Copyright (c) 2000-2001 Artur Grabowski <art@openbsd.org>
  * All rights reserved. 
@@ -99,6 +99,7 @@ int timeout_add_msec(struct timeout *, int);
 int timeout_add_usec(struct timeout *, int);
 int timeout_add_nsec(struct timeout *, int);
 int timeout_del(struct timeout *);
+int timeout_del_barrier(struct timeout *);
 void timeout_barrier(struct timeout *);
 
 void timeout_startup(void);