Module Name: src Committed By: riastradh Date: Sun Dec 22 23:24:21 UTC 2024
Modified Files: src/sys/kern: files.kern kern_time.c subr_time.c src/sys/rump/librump/rumpkern: Makefile.rumpkern src/sys/sys: time.h timevar.h Added Files: src/sys/kern: subr_time_arith.c src/sys/sys: timearith.h Log Message: kern: Move some purely arithmetic routines to subr_time_arith.c. Preparation for testing and fixing: PR kern/58922: itimer(9): arithmetic overflow PR kern/58925: itimer(9) responds erratically to clock wound back PR kern/58926: itimer(9) integer overflow in overrun counting PR kern/58927: itimer(9): overrun accounting is broken To generate a diff of this commit: cvs rdiff -u -r1.60 -r1.61 src/sys/kern/files.kern cvs rdiff -u -r1.226 -r1.227 src/sys/kern/kern_time.c cvs rdiff -u -r1.40 -r1.41 src/sys/kern/subr_time.c cvs rdiff -u -r0 -r1.1 src/sys/kern/subr_time_arith.c cvs rdiff -u -r1.191 -r1.192 src/sys/rump/librump/rumpkern/Makefile.rumpkern cvs rdiff -u -r1.81 -r1.82 src/sys/sys/time.h cvs rdiff -u -r0 -r1.1 src/sys/sys/timearith.h cvs rdiff -u -r1.51 -r1.52 src/sys/sys/timevar.h Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files.
Modified files: Index: src/sys/kern/files.kern diff -u src/sys/kern/files.kern:1.60 src/sys/kern/files.kern:1.61 --- src/sys/kern/files.kern:1.60 Fri Jul 28 18:19:01 2023 +++ src/sys/kern/files.kern Sun Dec 22 23:24:20 2024 @@ -1,4 +1,4 @@ -# $NetBSD: files.kern,v 1.60 2023/07/28 18:19:01 christos Exp $ +# $NetBSD: files.kern,v 1.61 2024/12/22 23:24:20 riastradh Exp $ # # kernel sources @@ -154,6 +154,7 @@ file kern/subr_psref.c kern file kern/subr_specificdata.c kern file kern/subr_tftproot.c tftproot file kern/subr_time.c kern +file kern/subr_time_arith.c kern file kern/subr_thmap.c kern file kern/subr_userconf.c userconf file kern/subr_vmem.c kern Index: src/sys/kern/kern_time.c diff -u src/sys/kern/kern_time.c:1.226 src/sys/kern/kern_time.c:1.227 --- src/sys/kern/kern_time.c:1.226 Sun Dec 22 23:18:29 2024 +++ src/sys/kern/kern_time.c Sun Dec 22 23:24:20 2024 @@ -1,4 +1,4 @@ -/* $NetBSD: kern_time.c,v 1.226 2024/12/22 23:18:29 riastradh Exp $ */ +/* $NetBSD: kern_time.c,v 1.227 2024/12/22 23:24:20 riastradh Exp $ */ /*- * Copyright (c) 2000, 2004, 2005, 2007, 2008, 2009, 2020 @@ -62,7 +62,7 @@ */ #include <sys/cdefs.h> -__KERNEL_RCSID(0, "$NetBSD: kern_time.c,v 1.226 2024/12/22 23:18:29 riastradh Exp $"); +__KERNEL_RCSID(0, "$NetBSD: kern_time.c,v 1.227 2024/12/22 23:24:20 riastradh Exp $"); #include <sys/param.h> #include <sys/types.h> @@ -846,10 +846,9 @@ itimer_arm_real(struct itimer * const it static void itimer_callout(void *arg) { - uint64_t last_val, next_val, interval, now_ns; struct timespec now, next; struct itimer * const it = arg; - int backwards; + int overruns; itimer_lock(); (*it->it_ops->ito_fire)(it); @@ -866,34 +865,13 @@ itimer_callout(void *arg) getnanotime(&now); } - backwards = (timespeccmp(&it->it_time.it_value, &now, >)); - - /* Nonnegative interval guaranteed by itimerfix. */ - KASSERT(it->it_time.it_interval.tv_sec >= 0); - KASSERT(it->it_time.it_interval.tv_nsec >= 0); - - /* Handle the easy case of non-overflown timers first. */ - if (!backwards && - timespecaddok(&it->it_time.it_value, &it->it_time.it_interval)) { - timespecadd(&it->it_time.it_value, &it->it_time.it_interval, - &next); - it->it_time.it_value = next; - } else { - now_ns = timespec2ns(&now); - last_val = timespec2ns(&it->it_time.it_value); - interval = timespec2ns(&it->it_time.it_interval); - - next_val = now_ns + - (now_ns - last_val + interval - 1) % interval; - - if (backwards) - next_val += interval; - else - it->it_overruns += (now_ns - last_val) / interval; - - it->it_time.it_value.tv_sec = next_val / 1000000000; - it->it_time.it_value.tv_nsec = next_val % 1000000000; - } + /* + * Given the current itimer value and interval and the time + * now, compute the next itimer value and count overruns. + */ + itimer_transition(&it->it_time, &now, &next, &overruns); + it->it_time.it_value = next; + it->it_overruns += overruns; /* * Reset the callout, if it's not going away. Index: src/sys/kern/subr_time.c diff -u src/sys/kern/subr_time.c:1.40 src/sys/kern/subr_time.c:1.41 --- src/sys/kern/subr_time.c:1.40 Sun Dec 22 23:18:47 2024 +++ src/sys/kern/subr_time.c Sun Dec 22 23:24:20 2024 @@ -1,4 +1,4 @@ -/* $NetBSD: subr_time.c,v 1.40 2024/12/22 23:18:47 riastradh Exp $ */ +/* $NetBSD: subr_time.c,v 1.41 2024/12/22 23:24:20 riastradh Exp $ */ /* * Copyright (c) 1982, 1986, 1989, 1993 @@ -33,7 +33,7 @@ */ #include <sys/cdefs.h> -__KERNEL_RCSID(0, "$NetBSD: subr_time.c,v 1.40 2024/12/22 23:18:47 riastradh Exp $"); +__KERNEL_RCSID(0, "$NetBSD: subr_time.c,v 1.41 2024/12/22 23:24:20 riastradh Exp $"); #include <sys/param.h> #include <sys/types.h> @@ -62,69 +62,6 @@ tvhzto(const struct timeval *tvp) return tvtohz(&tv); } -/* - * Compute number of ticks in the specified amount of time. - */ -int -tvtohz(const struct timeval *tv) -{ - unsigned long ticks; - long sec, usec; - - /* - * If the number of usecs in the whole seconds part of the time - * difference fits in a long, then the total number of usecs will - * fit in an unsigned long. Compute the total and convert it to - * ticks, rounding up and adding 1 to allow for the current tick - * to expire. Rounding also depends on unsigned long arithmetic - * to avoid overflow. - * - * Otherwise, if the number of ticks in the whole seconds part of - * the time difference fits in a long, then convert the parts to - * ticks separately and add, using similar rounding methods and - * overflow avoidance. This method would work in the previous - * case, but it is slightly slower and assumes that hz is integral. - * - * Otherwise, round the time difference down to the maximum - * representable value. - * - * If ints are 32-bit, then the maximum value for any timeout in - * 10ms ticks is 248 days. - */ - sec = tv->tv_sec; - usec = tv->tv_usec; - - KASSERT(usec >= 0); - KASSERT(usec < 1000000); - - /* catch overflows in conversion time_t->int */ - if (tv->tv_sec > INT_MAX) - return INT_MAX; - if (tv->tv_sec < 0) - return 0; - - if (sec < 0 || (sec == 0 && usec == 0)) { - /* - * Would expire now or in the past. Return 0 ticks. - * This is different from the legacy tvhzto() interface, - * and callers need to check for it. - */ - ticks = 0; - } else if (sec <= (LONG_MAX / 1000000)) - ticks = (((sec * 1000000) + (unsigned long)usec + (tick - 1)) - / tick) + 1; - else if (sec <= (LONG_MAX / hz)) - ticks = (sec * hz) + - (((unsigned long)usec + (tick - 1)) / tick) + 1; - else - ticks = LONG_MAX; - - if (ticks > INT_MAX) - ticks = INT_MAX; - - return ((int)ticks); -} - int tshzto(const struct timespec *tsp) { @@ -163,40 +100,6 @@ tstohz(const struct timespec *ts) return tvtohz(&tv); } -/* - * Check that a proposed value to load into the .it_value or - * .it_interval part of an interval timer is acceptable, and - * fix it to have at least minimal value (i.e. if it is less - * than the resolution of the clock, round it up.). We don't - * timeout the 0,0 value because this means to disable the - * timer or the interval. - */ -int -itimerfix(struct timeval *tv) -{ - - if (tv->tv_usec < 0 || tv->tv_usec >= 1000000) - return EINVAL; - if (tv->tv_sec < 0) - return ETIMEDOUT; - if (tv->tv_sec == 0 && tv->tv_usec != 0 && tv->tv_usec < tick) - tv->tv_usec = tick; - return 0; -} - -int -itimespecfix(struct timespec *ts) -{ - - if (ts->tv_nsec < 0 || ts->tv_nsec >= 1000000000) - return EINVAL; - if (ts->tv_sec < 0) - return ETIMEDOUT; - if (ts->tv_sec == 0 && ts->tv_nsec != 0 && ts->tv_nsec < tick * 1000) - ts->tv_nsec = tick * 1000; - return 0; -} - int inittimeleft(struct timespec *ts, struct timespec *sleepts) { @@ -349,221 +252,3 @@ ts2timo(clockid_t clock_id, int flags, s return 0; } - -bool -timespecaddok(const struct timespec *tsp, const struct timespec *usp) -{ - enum { TIME_MIN = __type_min(time_t), TIME_MAX = __type_max(time_t) }; - time_t a = tsp->tv_sec; - time_t b = usp->tv_sec; - bool carry; - - /* - * Caller is responsible for guaranteeing valid timespec - * inputs. Any user-controlled inputs must be validated or - * adjusted. - */ - KASSERT(tsp->tv_nsec >= 0); - KASSERT(usp->tv_nsec >= 0); - KASSERT(tsp->tv_nsec < 1000000000L); - KASSERT(usp->tv_nsec < 1000000000L); - CTASSERT(1000000000L <= __type_max(long) - 1000000000L); - - /* - * Fail if a + b + carry overflows TIME_MAX, or if a + b - * overflows TIME_MIN because timespecadd adds the carry after - * computing a + b. - * - * Break it into two mutually exclusive and exhaustive cases: - * I. a >= 0 - * II. a < 0 - */ - carry = (tsp->tv_nsec + usp->tv_nsec >= 1000000000L); - if (a >= 0) { - /* - * Case I: a >= 0. If b < 0, then b + 1 <= 0, so - * - * a + b + 1 <= a + 0 <= TIME_MAX, - * - * and - * - * a + b >= 0 + b = b >= TIME_MIN, - * - * so this can't overflow. - * - * If b >= 0, then a + b + carry >= a + b >= 0, so - * negative results and thus results below TIME_MIN are - * impossible; we need only avoid - * - * a + b + carry > TIME_MAX, - * - * which we will do by rejecting if - * - * b > TIME_MAX - a - carry, - * - * which in turn is incidentally always false if b < 0 - * so we don't need extra logic to discriminate on the - * b >= 0 and b < 0 cases. - * - * Since 0 <= a <= TIME_MAX, we know - * - * 0 <= TIME_MAX - a <= TIME_MAX, - * - * and hence - * - * -1 <= TIME_MAX - a - 1 < TIME_MAX. - * - * So we can compute TIME_MAX - a - carry (i.e., either - * TIME_MAX - a or TIME_MAX - a - 1) safely without - * overflow. - */ - if (b > TIME_MAX - a - carry) - return false; - } else { - /* - * Case II: a < 0. If b >= 0, then since a + 1 <= 0, - * we have - * - * a + b + 1 <= b <= TIME_MAX, - * - * and - * - * a + b >= a >= TIME_MIN, - * - * so this can't overflow. - * - * If b < 0, then the intermediate a + b is negative - * and the outcome a + b + 1 is nonpositive, so we need - * only avoid - * - * a + b < TIME_MIN, - * - * which we will do by rejecting if - * - * a < TIME_MIN - b. - * - * (Reminder: The carry is added afterward in - * timespecadd, so to avoid overflow it is not enough - * to merely reject a + b + carry < TIME_MIN.) - * - * It is safe to compute the difference TIME_MIN - b - * because b is negative, so the result lies in - * (TIME_MIN, 0]. - */ - if (b < 0 && a < TIME_MIN - b) - return false; - } - - return true; -} - -bool -timespecsubok(const struct timespec *tsp, const struct timespec *usp) -{ - enum { TIME_MIN = __type_min(time_t), TIME_MAX = __type_max(time_t) }; - time_t a = tsp->tv_sec, b = usp->tv_sec; - bool borrow; - - /* - * Caller is responsible for guaranteeing valid timespec - * inputs. Any user-controlled inputs must be validated or - * adjusted. - */ - KASSERT(tsp->tv_nsec >= 0); - KASSERT(usp->tv_nsec >= 0); - KASSERT(tsp->tv_nsec < 1000000000L); - KASSERT(usp->tv_nsec < 1000000000L); - CTASSERT(1000000000L <= __type_max(long) - 1000000000L); - - /* - * Fail if a - b - borrow overflows TIME_MIN, or if a - b - * overflows TIME_MAX because timespecsub subtracts the borrow - * after computing a - b. - * - * Break it into two mutually exclusive and exhaustive cases: - * I. a < 0 - * II. a >= 0 - */ - borrow = (tsp->tv_nsec - usp->tv_nsec < 0); - if (a < 0) { - /* - * Case I: a < 0. If b < 0, then -b - 1 >= 0, so - * - * a - b - 1 >= a + 0 >= TIME_MIN, - * - * and, since a <= -1, provided that TIME_MIN <= - * -TIME_MAX - 1 so that TIME_MAX <= -TIME_MIN - 1 (in - * fact, equality holds, under the assumption of - * two's-complement arithmetic), - * - * a - b <= -1 - b = -b - 1 <= TIME_MAX, - * - * so this can't overflow. - */ - CTASSERT(TIME_MIN <= -TIME_MAX - 1); - - /* - * If b >= 0, then a - b - borrow <= a - b < 0, so - * positive results and thus results above TIME_MAX are - * impossible; we need only avoid - * - * a - b - borrow < TIME_MIN, - * - * which we will do by rejecting if - * - * a < TIME_MIN + b + borrow. - * - * The right-hand side is safe to evaluate for any - * values of b and borrow as long as TIME_MIN + - * TIME_MAX + 1 <= TIME_MAX, i.e., TIME_MIN <= -1. - * (Note: If time_t were unsigned, this would fail!) - * - * Note: Unlike Case I in timespecaddok, this criterion - * does not work for b < 0, nor can the roles of a and - * b in the inequality be reversed (e.g., -b < TIME_MIN - * - a + borrow) without extra cases like checking for - * b = TEST_MIN. - */ - CTASSERT(TIME_MIN < -1); - if (b >= 0 && a < TIME_MIN + b + borrow) - return false; - } else { - /* - * Case II: a >= 0. If b >= 0, then - * - * a - b <= a <= TIME_MAX, - * - * and, provided TIME_MIN <= -TIME_MAX - 1 (in fact, - * equality holds, under the assumption of - * two's-complement arithmetic) - * - * a - b - 1 >= -b - 1 >= -TIME_MAX - 1 >= TIME_MIN, - * - * so this can't overflow. - */ - CTASSERT(TIME_MIN <= -TIME_MAX - 1); - - /* - * If b < 0, then a - b >= a >= 0, so negative results - * and thus results below TIME_MIN are impossible; we - * need only avoid - * - * a - b > TIME_MAX, - * - * which we will do by rejecting if - * - * a > TIME_MAX + b. - * - * (Reminder: The borrow is subtracted afterward in - * timespecsub, so to avoid overflow it is not enough - * to merely reject a - b - borrow > TIME_MAX.) - * - * It is safe to compute the sum TIME_MAX + b because b - * is negative, so the result lies in [0, TIME_MAX). - */ - if (b < 0 && a > TIME_MAX + b) - return false; - } - - return true; -} Index: src/sys/rump/librump/rumpkern/Makefile.rumpkern diff -u src/sys/rump/librump/rumpkern/Makefile.rumpkern:1.191 src/sys/rump/librump/rumpkern/Makefile.rumpkern:1.192 --- src/sys/rump/librump/rumpkern/Makefile.rumpkern:1.191 Sat Jun 3 09:09:15 2023 +++ src/sys/rump/librump/rumpkern/Makefile.rumpkern Sun Dec 22 23:24:20 2024 @@ -1,4 +1,4 @@ -# $NetBSD: Makefile.rumpkern,v 1.191 2023/06/03 09:09:15 lukem Exp $ +# $NetBSD: Makefile.rumpkern,v 1.192 2024/12/22 23:24:20 riastradh Exp $ # IOCONFDIR:= ${.PARSEDIR} @@ -126,6 +126,7 @@ SRCS+= init_sysctl_base.c \ subr_psref.c \ subr_specificdata.c \ subr_time.c \ + subr_time_arith.c \ subr_thmap.c \ subr_vmem.c \ subr_workqueue.c \ Index: src/sys/sys/time.h diff -u src/sys/sys/time.h:1.81 src/sys/sys/time.h:1.82 --- src/sys/sys/time.h:1.81 Sun May 12 10:34:56 2024 +++ src/sys/sys/time.h Sun Dec 22 23:24:20 2024 @@ -1,4 +1,4 @@ -/* $NetBSD: time.h,v 1.81 2024/05/12 10:34:56 rillig Exp $ */ +/* $NetBSD: time.h,v 1.82 2024/12/22 23:24:20 riastradh Exp $ */ /* * Copyright (c) 1982, 1986, 1993 @@ -266,7 +266,8 @@ ns2bintime(uint64_t ns) } while (0) #define timespec2ns(x) (((uint64_t)(x)->tv_sec) * 1000000000L + (x)->tv_nsec) -#ifdef _KERNEL +#if defined(_KERNEL) || defined(_TIME_TESTING) +#include <sys/stdbool.h> bool timespecaddok(const struct timespec *, const struct timespec *) __pure; bool timespecsubok(const struct timespec *, const struct timespec *) __pure; #endif @@ -310,6 +311,7 @@ struct itimerspec { #define TIMER_ABSTIME 0x1 /* absolute timer */ #ifdef _KERNEL +#include <sys/timearith.h> #include <sys/timevar.h> #else /* !_KERNEL */ #ifndef _STANDALONE Index: src/sys/sys/timevar.h diff -u src/sys/sys/timevar.h:1.51 src/sys/sys/timevar.h:1.52 --- src/sys/sys/timevar.h:1.51 Mon Jul 17 13:44:24 2023 +++ src/sys/sys/timevar.h Sun Dec 22 23:24:20 2024 @@ -1,4 +1,4 @@ -/* $NetBSD: timevar.h,v 1.51 2023/07/17 13:44:24 riastradh Exp $ */ +/* $NetBSD: timevar.h,v 1.52 2024/12/22 23:24:20 riastradh Exp $ */ /* * Copyright (c) 2005, 2008, 2020 The NetBSD Foundation, Inc. @@ -202,8 +202,6 @@ int tshzto(const struct timespec *); int tshztoup(const struct timespec *); int tvhzto(const struct timeval *); void inittimecounter(void); -int itimerfix(struct timeval *); -int itimespecfix(struct timespec *); int ppsratecheck(struct timeval *, int *, int); int ratecheck(struct timeval *, const struct timeval *); int settime(struct proc *p, struct timespec *); @@ -213,8 +211,6 @@ int settimeofday1(const struct timeval * const void *, struct lwp *, bool); int timer_create1(timer_t *, clockid_t, struct sigevent *, copyin_t, struct lwp *); -int tstohz(const struct timespec *); -int tvtohz(const struct timeval *); int inittimeleft(struct timespec *, struct timespec *); int gettimeleft(struct timespec *, struct timespec *); void timerupcall(struct lwp *); Added files: Index: src/sys/kern/subr_time_arith.c diff -u /dev/null src/sys/kern/subr_time_arith.c:1.1 --- /dev/null Sun Dec 22 23:24:21 2024 +++ src/sys/kern/subr_time_arith.c Sun Dec 22 23:24:20 2024 @@ -0,0 +1,490 @@ +/* $NetBSD: subr_time_arith.c,v 1.1 2024/12/22 23:24:20 riastradh Exp $ */ + +/*- + * Copyright (c) 2000, 2004, 2005, 2007, 2008, 2009, 2020 + * The NetBSD Foundation, Inc. + * All rights reserved. + * + * This code is derived from software contributed to The NetBSD Foundation + * by Christopher G. Demetriou, by Andrew Doran, and by Jason R. Thorpe. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Copyright (c) 1982, 1986, 1989, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)kern_clock.c 8.5 (Berkeley) 1/21/94 + * @(#)kern_time.c 8.4 (Berkeley) 5/26/95 + */ + +#include <sys/cdefs.h> +__KERNEL_RCSID(0, "$NetBSD: subr_time_arith.c,v 1.1 2024/12/22 23:24:20 riastradh Exp $"); + +#include <sys/types.h> + +#include <sys/errno.h> +#include <sys/time.h> +#include <sys/timearith.h> + +#if defined(_KERNEL) + +#include <sys/kernel.h> +#include <sys/systm.h> + +#include <machine/limits.h> + +#elif defined(_TIME_TESTING) + +#include <assert.h> +#include <limits.h> +#include <stdbool.h> + +extern int hz; +extern long tick; + +#define KASSERT assert + +#endif + +/* + * Compute number of ticks in the specified amount of time. + */ +int +tvtohz(const struct timeval *tv) +{ + unsigned long ticks; + long sec, usec; + + /* + * If the number of usecs in the whole seconds part of the time + * difference fits in a long, then the total number of usecs will + * fit in an unsigned long. Compute the total and convert it to + * ticks, rounding up and adding 1 to allow for the current tick + * to expire. Rounding also depends on unsigned long arithmetic + * to avoid overflow. + * + * Otherwise, if the number of ticks in the whole seconds part of + * the time difference fits in a long, then convert the parts to + * ticks separately and add, using similar rounding methods and + * overflow avoidance. This method would work in the previous + * case, but it is slightly slower and assumes that hz is integral. + * + * Otherwise, round the time difference down to the maximum + * representable value. + * + * If ints are 32-bit, then the maximum value for any timeout in + * 10ms ticks is 248 days. + */ + sec = tv->tv_sec; + usec = tv->tv_usec; + + KASSERT(usec >= 0); + KASSERT(usec < 1000000); + + /* catch overflows in conversion time_t->int */ + if (tv->tv_sec > INT_MAX) + return INT_MAX; + if (tv->tv_sec < 0) + return 0; + + if (sec < 0 || (sec == 0 && usec == 0)) { + /* + * Would expire now or in the past. Return 0 ticks. + * This is different from the legacy tvhzto() interface, + * and callers need to check for it. + */ + ticks = 0; + } else if (sec <= (LONG_MAX / 1000000)) + ticks = (((sec * 1000000) + (unsigned long)usec + (tick - 1)) + / tick) + 1; + else if (sec <= (LONG_MAX / hz)) + ticks = (sec * hz) + + (((unsigned long)usec + (tick - 1)) / tick) + 1; + else + ticks = LONG_MAX; + + if (ticks > INT_MAX) + ticks = INT_MAX; + + return ((int)ticks); +} + +/* + * Check that a proposed value to load into the .it_value or + * .it_interval part of an interval timer is acceptable, and + * fix it to have at least minimal value (i.e. if it is less + * than the resolution of the clock, round it up.). We don't + * timeout the 0,0 value because this means to disable the + * timer or the interval. + */ +int +itimerfix(struct timeval *tv) +{ + + if (tv->tv_usec < 0 || tv->tv_usec >= 1000000) + return EINVAL; + if (tv->tv_sec < 0) + return ETIMEDOUT; + if (tv->tv_sec == 0 && tv->tv_usec != 0 && tv->tv_usec < tick) + tv->tv_usec = tick; + return 0; +} + +int +itimespecfix(struct timespec *ts) +{ + + if (ts->tv_nsec < 0 || ts->tv_nsec >= 1000000000) + return EINVAL; + if (ts->tv_sec < 0) + return ETIMEDOUT; + if (ts->tv_sec == 0 && ts->tv_nsec != 0 && ts->tv_nsec < tick * 1000) + ts->tv_nsec = tick * 1000; + return 0; +} + +/* + * timespecaddok(tsp, usp) + * + * True if tsp + usp can be computed without overflow, i.e., if it + * is OK to do timespecadd(tsp, usp, ...). + */ +bool +timespecaddok(const struct timespec *tsp, const struct timespec *usp) +{ + enum { TIME_MIN = __type_min(time_t), TIME_MAX = __type_max(time_t) }; + time_t a = tsp->tv_sec; + time_t b = usp->tv_sec; + bool carry; + + /* + * Caller is responsible for guaranteeing valid timespec + * inputs. Any user-controlled inputs must be validated or + * adjusted. + */ + KASSERT(tsp->tv_nsec >= 0); + KASSERT(usp->tv_nsec >= 0); + KASSERT(tsp->tv_nsec < 1000000000L); + KASSERT(usp->tv_nsec < 1000000000L); + __CTASSERT(1000000000L <= __type_max(long) - 1000000000L); + + /* + * Fail if a + b + carry overflows TIME_MAX, or if a + b + * overflows TIME_MIN because timespecadd adds the carry after + * computing a + b. + * + * Break it into two mutually exclusive and exhaustive cases: + * I. a >= 0 + * II. a < 0 + */ + carry = (tsp->tv_nsec + usp->tv_nsec >= 1000000000L); + if (a >= 0) { + /* + * Case I: a >= 0. If b < 0, then b + 1 <= 0, so + * + * a + b + 1 <= a + 0 <= TIME_MAX, + * + * and + * + * a + b >= 0 + b = b >= TIME_MIN, + * + * so this can't overflow. + * + * If b >= 0, then a + b + carry >= a + b >= 0, so + * negative results and thus results below TIME_MIN are + * impossible; we need only avoid + * + * a + b + carry > TIME_MAX, + * + * which we will do by rejecting if + * + * b > TIME_MAX - a - carry, + * + * which in turn is incidentally always false if b < 0 + * so we don't need extra logic to discriminate on the + * b >= 0 and b < 0 cases. + * + * Since 0 <= a <= TIME_MAX, we know + * + * 0 <= TIME_MAX - a <= TIME_MAX, + * + * and hence + * + * -1 <= TIME_MAX - a - 1 < TIME_MAX. + * + * So we can compute TIME_MAX - a - carry (i.e., either + * TIME_MAX - a or TIME_MAX - a - 1) safely without + * overflow. + */ + if (b > TIME_MAX - a - carry) + return false; + } else { + /* + * Case II: a < 0. If b >= 0, then since a + 1 <= 0, + * we have + * + * a + b + 1 <= b <= TIME_MAX, + * + * and + * + * a + b >= a >= TIME_MIN, + * + * so this can't overflow. + * + * If b < 0, then the intermediate a + b is negative + * and the outcome a + b + 1 is nonpositive, so we need + * only avoid + * + * a + b < TIME_MIN, + * + * which we will do by rejecting if + * + * a < TIME_MIN - b. + * + * (Reminder: The carry is added afterward in + * timespecadd, so to avoid overflow it is not enough + * to merely reject a + b + carry < TIME_MIN.) + * + * It is safe to compute the difference TIME_MIN - b + * because b is negative, so the result lies in + * (TIME_MIN, 0]. + */ + if (b < 0 && a < TIME_MIN - b) + return false; + } + + return true; +} + +/* + * timespecsubok(tsp, usp) + * + * True if tsp - usp can be computed without overflow, i.e., if it + * is OK to do timespecsub(tsp, usp, ...). + */ +bool +timespecsubok(const struct timespec *tsp, const struct timespec *usp) +{ + enum { TIME_MIN = __type_min(time_t), TIME_MAX = __type_max(time_t) }; + time_t a = tsp->tv_sec, b = usp->tv_sec; + bool borrow; + + /* + * Caller is responsible for guaranteeing valid timespec + * inputs. Any user-controlled inputs must be validated or + * adjusted. + */ + KASSERT(tsp->tv_nsec >= 0); + KASSERT(usp->tv_nsec >= 0); + KASSERT(tsp->tv_nsec < 1000000000L); + KASSERT(usp->tv_nsec < 1000000000L); + __CTASSERT(1000000000L <= __type_max(long) - 1000000000L); + + /* + * Fail if a - b - borrow overflows TIME_MIN, or if a - b + * overflows TIME_MAX because timespecsub subtracts the borrow + * after computing a - b. + * + * Break it into two mutually exclusive and exhaustive cases: + * I. a < 0 + * II. a >= 0 + */ + borrow = (tsp->tv_nsec - usp->tv_nsec < 0); + if (a < 0) { + /* + * Case I: a < 0. If b < 0, then -b - 1 >= 0, so + * + * a - b - 1 >= a + 0 >= TIME_MIN, + * + * and, since a <= -1, provided that TIME_MIN <= + * -TIME_MAX - 1 so that TIME_MAX <= -TIME_MIN - 1 (in + * fact, equality holds, under the assumption of + * two's-complement arithmetic), + * + * a - b <= -1 - b = -b - 1 <= TIME_MAX, + * + * so this can't overflow. + */ + __CTASSERT(TIME_MIN <= -TIME_MAX - 1); + + /* + * If b >= 0, then a - b - borrow <= a - b < 0, so + * positive results and thus results above TIME_MAX are + * impossible; we need only avoid + * + * a - b - borrow < TIME_MIN, + * + * which we will do by rejecting if + * + * a < TIME_MIN + b + borrow. + * + * The right-hand side is safe to evaluate for any + * values of b and borrow as long as TIME_MIN + + * TIME_MAX + 1 <= TIME_MAX, i.e., TIME_MIN <= -1. + * (Note: If time_t were unsigned, this would fail!) + * + * Note: Unlike Case I in timespecaddok, this criterion + * does not work for b < 0, nor can the roles of a and + * b in the inequality be reversed (e.g., -b < TIME_MIN + * - a + borrow) without extra cases like checking for + * b = TEST_MIN. + */ + __CTASSERT(TIME_MIN < -1); + if (b >= 0 && a < TIME_MIN + b + borrow) + return false; + } else { + /* + * Case II: a >= 0. If b >= 0, then + * + * a - b <= a <= TIME_MAX, + * + * and, provided TIME_MIN <= -TIME_MAX - 1 (in fact, + * equality holds, under the assumption of + * two's-complement arithmetic) + * + * a - b - 1 >= -b - 1 >= -TIME_MAX - 1 >= TIME_MIN, + * + * so this can't overflow. + */ + __CTASSERT(TIME_MIN <= -TIME_MAX - 1); + + /* + * If b < 0, then a - b >= a >= 0, so negative results + * and thus results below TIME_MIN are impossible; we + * need only avoid + * + * a - b > TIME_MAX, + * + * which we will do by rejecting if + * + * a > TIME_MAX + b. + * + * (Reminder: The borrow is subtracted afterward in + * timespecsub, so to avoid overflow it is not enough + * to merely reject a - b - borrow > TIME_MAX.) + * + * It is safe to compute the sum TIME_MAX + b because b + * is negative, so the result lies in [0, TIME_MAX). + */ + if (b < 0 && a > TIME_MAX + b) + return false; + } + + return true; +} + +/* + * itimer_transition(it, now, next, &overruns) + * + * Given: + * + * - it: the current state of an itimer (it_value = last expiry + * time, it_interval = periodic rescheduling interval), and + * + * - now: the current time on the itimer's clock; + * + * compute: + * + * - next: the next time the itimer should be scheduled for, and + * - overruns: the number of overruns if we're firing late. + * + * XXX This should maybe also say whether the itimer should expire + * at all. + */ +void +itimer_transition(const struct itimerspec *restrict it, + const struct timespec *restrict now, + struct timespec *restrict next, + int *restrict overrunsp) +{ + uint64_t last_val, next_val, interval, now_ns; + int backwards; + + /* + * Zero the outputs so we can test assertions in userland + * without undefined behaviour. + */ + timespecclear(next); + *overrunsp = 0; + + /* + * Paranoia: Caller should guarantee this. + */ + if (!timespecisset(&it->it_interval)) { + timespecclear(next); + return; + } + + backwards = (timespeccmp(&it->it_value, now, >)); + + /* Nonnegative interval guaranteed by itimerfix. */ + KASSERT(it->it_interval.tv_sec >= 0); + KASSERT(it->it_interval.tv_nsec >= 0); + + /* Handle the easy case of non-overflown timers first. */ + if (!backwards && + timespecaddok(&it->it_value, &it->it_interval)) { + timespecadd(&it->it_value, &it->it_interval, + next); + } else { + now_ns = timespec2ns(now); + last_val = timespec2ns(&it->it_value); + interval = timespec2ns(&it->it_interval); + + next_val = now_ns + + (now_ns - last_val + interval - 1) % interval; + + if (backwards) + next_val += interval; + else + *overrunsp = (now_ns - last_val) / interval; + + next->tv_sec = next_val / 1000000000; + next->tv_nsec = next_val % 1000000000; + } +} Index: src/sys/sys/timearith.h diff -u /dev/null src/sys/sys/timearith.h:1.1 --- /dev/null Sun Dec 22 23:24:21 2024 +++ src/sys/sys/timearith.h Sun Dec 22 23:24:20 2024 @@ -0,0 +1,77 @@ +/* $NetBSD: timearith.h,v 1.1 2024/12/22 23:24:20 riastradh Exp $ */ + +/* + * Copyright (c) 2005, 2008, 2020 The NetBSD Foundation, Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Copyright (c) 1982, 1986, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)time.h 8.5 (Berkeley) 5/4/95 + */ + +#ifndef _SYS_TIMEARITH_H_ +#define _SYS_TIMEARITH_H_ + +struct itimerspec; +struct timespec; +struct timeval; + +int tstohz(const struct timespec *); +int tvtohz(const struct timeval *); + +int itimerfix(struct timeval *); +int itimespecfix(struct timespec *); + +void itimer_transition(const struct itimerspec *restrict, + const struct timespec *restrict, + struct timespec *restrict, int *restrict); + +#endif /* _SYS_TIMEARITH_H_ */