[src/trunk]: src/sys/kern Add cv_timedwaitbt, cv_timedwaitbt_sig.

[riastradh <riastradh%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/453f40671036
branches:  trunk
changeset: 825193:453f40671036
user:      riastradh <riastradh%NetBSD.org@localhost>
date:      Mon Jul 03 02:12:47 2017 +0000

description:
Add cv_timedwaitbt, cv_timedwaitbt_sig.

Takes struct bintime maximum delay, and decrements it in place so
that you can use it in a loop in case of spurious wakeup.

Discussed on tech-kern a couple years ago:

https://mail-index.netbsd.org/tech-kern/2015/03/23/msg018557.html

Added a parameter for expressing desired precision -- not currently
interpreted, but intended for a future tickless kernel with a choice
of high-resolution timers.

diffstat:

 sys/kern/kern_condvar.c |  147 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 145 insertions(+), 2 deletions(-)

diffs (175 lines):

diff -r 63d2595d4b86 -r 453f40671036 sys/kern/kern_condvar.c
--- a/sys/kern/kern_condvar.c   Mon Jul 03 00:53:33 2017 +0000
+++ b/sys/kern/kern_condvar.c   Mon Jul 03 02:12:47 2017 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: kern_condvar.c,v 1.36 2017/06/08 01:09:52 chs Exp $    */
+/*     $NetBSD: kern_condvar.c,v 1.37 2017/07/03 02:12:47 riastradh Exp $      */
 
 /*-
  * Copyright (c) 2006, 2007, 2008 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_condvar.c,v 1.36 2017/06/08 01:09:52 chs Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_condvar.c,v 1.37 2017/07/03 02:12:47 riastradh Exp $");
 
 #include <sys/param.h>
 #include <sys/systm.h>
@@ -43,6 +43,7 @@
 #include <sys/sleepq.h>
 #include <sys/lockdebug.h>
 #include <sys/cpu.h>
+#include <sys/kernel.h>
 
 /*
  * Accessors for the private contents of the kcondvar_t data type.
@@ -319,6 +320,148 @@
 }
 
 /*
+ * Given a number of seconds, sec, and 2^64ths of a second, frac, we
+ * want a number of ticks for a timeout:
+ *
+ *     timo = hz*(sec + frac/2^64)
+ *          = hz*sec + hz*frac/2^64
+ *          = hz*sec + hz*(frachi*2^32 + fraclo)/2^64
+ *          = hz*sec + hz*frachi/2^32 + hz*fraclo/2^64,
+ *
+ * where frachi is the high 32 bits of frac and fraclo is the
+ * low 32 bits.
+ *
+ * We assume hz < INT_MAX/2 < UINT32_MAX, so
+ *
+ *     hz*fraclo/2^64 < fraclo*2^32/2^64 <= 1,
+ *
+ * since fraclo < 2^32.
+ *
+ * We clamp the result at INT_MAX/2 for a timeout in ticks, since we
+ * can't represent timeouts higher than INT_MAX in cv_timedwait, and
+ * spurious wakeup is OK.  Moreover, we don't want to wrap around,
+ * because we compute end - start in ticks in order to compute the
+ * remaining timeout, and that difference cannot wrap around, so we use
+ * a timeout less than INT_MAX.  Using INT_MAX/2 provides plenty of
+ * margin for paranoia and will exceed most waits in practice by far.
+ */
+static unsigned
+bintime2timo(const struct bintime *bt)
+{
+
+       KASSERT(hz < INT_MAX/2);
+       CTASSERT(INT_MAX/2 < UINT32_MAX);
+       if (bt->sec > ((INT_MAX/2)/hz))
+               return INT_MAX/2;
+       if ((hz*(bt->frac >> 32) >> 32) > (INT_MAX/2 - hz*bt->sec))
+               return INT_MAX/2;
+
+       return hz*bt->sec + (hz*(bt->frac >> 32) >> 32);
+}
+
+/*
+ * timo is in units of ticks.  We want units of seconds and 2^64ths of
+ * a second.  We know hz = 1 sec/tick, and 2^64 = 1 sec/(2^64th of a
+ * second), from which we can conclude 2^64 / hz = 1 (2^64th of a
+ * second)/tick.  So for the fractional part, we compute
+ *
+ *     frac = rem * 2^64 / hz
+ *          = ((rem * 2^32) / hz) * 2^32
+ *
+ * Using truncating integer division instead of real division will
+ * leave us with only about 32 bits of precision, which means about
+ * 1/4-nanosecond resolution, which is good enough for our purposes.
+ */
+static struct bintime
+timo2bintime(unsigned timo)
+{
+
+       return (struct bintime) {
+               .sec = timo / hz,
+               .frac = (((uint64_t)(timo % hz) << 32)/hz << 32),
+       };
+}
+
+/*
+ * cv_timedwaitbt:
+ *
+ *     Wait on a condition variable until awoken or the specified
+ *     timeout expires.  Returns zero if awoken normally or
+ *     EWOULDBLOCK if the timeout expires.
+ *
+ *     On entry, bt is a timeout in bintime.  cv_timedwaitbt subtracts
+ *     the time slept, so on exit, bt is the time remaining after
+ *     sleeping.  No infinite timeout; use cv_wait_sig instead.
+ *
+ *     epsilon is a requested maximum error in timeout (excluding
+ *     spurious wakeups).  Currently not used, will be used in the
+ *     future to choose between low- and high-resolution timers.
+ */
+int
+cv_timedwaitbt(kcondvar_t *cv, kmutex_t *mtx, struct bintime *bt,
+    const struct bintime *epsilon __unused)
+{
+       struct bintime slept;
+       unsigned start, end;
+       int error;
+
+       /*
+        * hardclock_ticks is technically int, but nothing special
+        * happens instead of overflow, so we assume two's-complement
+        * wraparound and just treat it as unsigned.
+        */
+       start = hardclock_ticks;
+       error = cv_timedwait(cv, mtx, bintime2timo(bt));
+       end = hardclock_ticks;
+
+       slept = timo2bintime(end - start);
+       /* bt := bt - slept */
+       bintime_sub(bt, &slept);
+
+       return error;
+}
+
+/*
+ * cv_timedwaitbt_sig:
+ *
+ *     Wait on a condition variable until awoken, the specified
+ *     timeout expires, or interrupted by a signal.  Returns zero if
+ *     awoken normally, EWOULDBLOCK if the timeout expires, or
+ *     EINTR/ERESTART if interrupted by a signal.
+ *
+ *     On entry, bt is a timeout in bintime.  cv_timedwaitbt_sig
+ *     subtracts the time slept, so on exit, bt is the time remaining
+ *     after sleeping.  No infinite timeout; use cv_wait instead.
+ *
+ *     epsilon is a requested maximum error in timeout (excluding
+ *     spurious wakeups).  Currently not used, will be used in the
+ *     future to choose between low- and high-resolution timers.
+ */
+int
+cv_timedwaitbt_sig(kcondvar_t *cv, kmutex_t *mtx, struct bintime *bt,
+    const struct bintime *epsilon __unused)
+{
+       struct bintime slept;
+       unsigned start, end;
+       int error;
+
+       /*
+        * hardclock_ticks is technically int, but nothing special
+        * happens instead of overflow, so we assume two's-complement
+        * wraparound and just treat it as unsigned.
+        */
+       start = hardclock_ticks;
+       error = cv_timedwait_sig(cv, mtx, bintime2timo(bt));
+       end = hardclock_ticks;
+
+       slept = timo2bintime(end - start);
+       /* bt := bt - slept */
+       bintime_sub(bt, &slept);
+
+       return error;
+}
+
+/*
  * cv_signal:
  *
  *     Wake the highest priority LWP waiting on a condition variable.