timeout(9): new flag: TIMEOUT_SCHEDULED, new statistic: tos_scheduled

This flag is set whenever a timeout is put on the wheel and cleared upon
(a) running, (b) deletion, and (c) readdition.  It serves two purposes:

1. Facilitate distinguishing scheduled and rescheduled timeouts.  When a
   timeout is put on the wheel it is "scheduled" for a later softclock().
   If this happens two or more times it is also said to be "rescheduled".
   The tos_rescheduled value thus indicates how many distant timeouts
   have been cascaded into a lower wheel level.

2. Eliminate false late timeouts.  A timeout is not late if it is due
   before softclock() has had a chance to schedule it.  To track this we
   need additional state, hence a new flag.

rprocter@ raises some interesting questions.  Some answers:

 - This interface is not stable and name changes are possible at a
   later date.

 - Although rescheduling timeouts is a side effect of the underlying
   implementation, I don't forsee us using anything but a timeout wheel
   in the future.  Other data structures are too slow in practice, so
   I doubt that the concept of a rescheduled timeout will be irrelevant
   any time soon.

 - I think the development utility of gathering these sorts of statistics
   is high.  Watching the distribution of timeouts under a given workflow
   is informative.

ok visa@

1 files changed, 10 insertions, 6 deletions

diff --git a/sys/kern/kern_timeout.c b/sys/kern/kern_timeout.c
index 1ef591bbccb..27d667ed0e1 100644
--- a/sys/kern/kern_timeout.c
+++ b/sys/kern/kern_timeout.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: kern_timeout.c,v 1.66 2019/12/12 18:12:43 cheloha Exp $	*/
+/*	$OpenBSD: kern_timeout.c,v 1.67 2019/12/25 00:15:36 cheloha Exp $	*/
 /*
  * Copyright (c) 2001 Thomas Nordin <nordin@openbsd.org>
  * Copyright (c) 2000-2001 Artur Grabowski <art@openbsd.org>
@@ -250,7 +250,7 @@ timeout_add(struct timeout *new, int to_ticks)
 	/* Initialize the time here, it won't change. */
 	old_time = new->to_time;
 	new->to_time = to_ticks + ticks;
-	CLR(new->to_flags, TIMEOUT_TRIGGERED);
+	CLR(new->to_flags, TIMEOUT_TRIGGERED | TIMEOUT_SCHEDULED);
 
 	/*
 	 * If this timeout already is scheduled and now is moved
@@ -377,7 +377,7 @@ timeout_del(struct timeout *to)
 		tostat.tos_cancelled++;
 		ret = 1;
 	}
-	CLR(to->to_flags, TIMEOUT_TRIGGERED);
+	CLR(to->to_flags, TIMEOUT_TRIGGERED | TIMEOUT_SCHEDULED);
 	tostat.tos_deleted++;
 	mtx_leave(&timeout_mutex);
 
@@ -471,7 +471,7 @@ timeout_run(struct timeout *to)
 
 	MUTEX_ASSERT_LOCKED(&timeout_mutex);
 
-	CLR(to->to_flags, TIMEOUT_ONQUEUE);
+	CLR(to->to_flags, TIMEOUT_ONQUEUE | TIMEOUT_SCHEDULED);
 	SET(to->to_flags, TIMEOUT_TRIGGERED);
 
 	fn = to->to_func;
@@ -512,10 +512,14 @@ softclock(void *arg)
 		if (delta > 0) {
 			bucket = &BUCKET(delta, to->to_time);
 			CIRCQ_INSERT_TAIL(bucket, &to->to_list);
-			tostat.tos_rescheduled++;
+			if (ISSET(to->to_flags, TIMEOUT_SCHEDULED))
+				tostat.tos_rescheduled++;
+			else
+				SET(to->to_flags, TIMEOUT_SCHEDULED);
+			tostat.tos_scheduled++;
 			continue;
 		}
-		if (delta < 0)
+		if (ISSET(to->to_flags, TIMEOUT_SCHEDULED) && delta < 0)
 			tostat.tos_late++;
 		if (ISSET(to->to_flags, TIMEOUT_NEEDPROCCTX)) {
 			CIRCQ_INSERT_TAIL(&timeout_proc, &to->to_list);