git: 9408dc3cc478 - stable/13 - time(3): Optimize tvtohz() function.
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Sat, 12 Nov 2022 12:41:47 UTC
The branch stable/13 has been updated by hselasky: URL: https://cgit.FreeBSD.org/src/commit/?id=9408dc3cc478c48e63f4be5a076f22156a8716d2 commit 9408dc3cc478c48e63f4be5a076f22156a8716d2 Author: Hans Petter Selasky <hselasky@FreeBSD.org> AuthorDate: 2022-10-20 16:49:51 +0000 Commit: Hans Petter Selasky <hselasky@FreeBSD.org> CommitDate: 2022-11-12 11:59:47 +0000 time(3): Optimize tvtohz() function. List of changes: - Use integer multiplication instead of long multiplication, because the result is an integer. - Remove multiple if-statements and predict new if-statements. - Rename local variable name, "ticks" into "retval" to avoid shadowing the system "ticks" global variable. Reviewed by: kib@ and imp@ Sponsored by: NVIDIA Networking Differential Revision: https://reviews.freebsd.org/D36859 (cherry picked from commit 35a33d14b593ba93feb8fed8d0689bc8e0edd15b) --- sys/kern/kern_clock.c | 113 ++++++++++++++++++++++++++++++-------------------- sys/kern/subr_param.c | 2 + sys/sys/time.h | 1 + 3 files changed, 70 insertions(+), 46 deletions(-) diff --git a/sys/kern/kern_clock.c b/sys/kern/kern_clock.c index 3998ffd2a607..7201f9bb2a0d 100644 --- a/sys/kern/kern_clock.c +++ b/sys/kern/kern_clock.c @@ -523,60 +523,81 @@ hardclock_sync(int cpu) } /* - * Compute number of ticks in the specified amount of time. + * Regular integer scaling formula without loosing precision: + */ +#define TIME_INT_SCALE(value, mul, div) \ + (((value) / (div)) * (mul) + (((value) % (div)) * (mul)) / (div)) + +/* + * Macro for converting seconds and microseconds into actual ticks, + * based on the given hz value: + */ +#define TIME_TO_TICKS(sec, usec, hz) \ + ((sec) * (hz) + TIME_INT_SCALE(usec, hz, 1 << 6) / (1000000 >> 6)) + +#define TIME_ASSERT_VALID_HZ(hz) \ + _Static_assert(TIME_TO_TICKS(INT_MAX / (hz) - 1, 999999, hz) >= 0 && \ + TIME_TO_TICKS(INT_MAX / (hz) - 1, 999999, hz) < INT_MAX, \ + "tvtohz() can overflow the regular integer type") + +/* + * Compile time assert the maximum and minimum values to fit into a + * regular integer when computing TIME_TO_TICKS(): + */ +TIME_ASSERT_VALID_HZ(HZ_MAXIMUM); +TIME_ASSERT_VALID_HZ(HZ_MINIMUM); + +/* + * The forumla is mostly linear, but test some more common values just + * in case: + */ +TIME_ASSERT_VALID_HZ(1024); +TIME_ASSERT_VALID_HZ(1000); +TIME_ASSERT_VALID_HZ(128); +TIME_ASSERT_VALID_HZ(100); + +/* + * Compute number of ticks representing the specified amount of time. + * If the specified time is negative, a value of 1 is returned. This + * function returns a value from 1 up to and including INT_MAX. */ int tvtohz(struct timeval *tv) { - unsigned long ticks; - long sec, usec; + int retval; /* - * 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 have 32 bits, then the maximum value for any timeout in - * 10ms ticks is 248 days. + * The values passed here may come from user-space and these + * checks ensure "tv_usec" is within its allowed range: */ - sec = tv->tv_sec; - usec = tv->tv_usec; - if (usec < 0) { - sec--; - usec += 1000000; - } - if (sec < 0) { -#ifdef DIAGNOSTIC - if (usec > 0) { - sec++; - usec -= 1000000; + + /* check for tv_usec underflow */ + if (__predict_false(tv->tv_usec < 0)) { + tv->tv_sec += tv->tv_usec / 1000000; + tv->tv_usec = tv->tv_usec % 1000000; + /* convert tv_usec to a positive value */ + if (__predict_true(tv->tv_usec < 0)) { + tv->tv_usec += 1000000; + tv->tv_sec -= 1; } - printf("tvotohz: negative time difference %ld sec %ld usec\n", - sec, usec); -#endif - ticks = 1; - } else if (sec <= LONG_MAX / 1000000) - ticks = howmany(sec * 1000000 + (unsigned long)usec, tick) + 1; - else if (sec <= LONG_MAX / hz) - ticks = sec * hz - + howmany((unsigned long)usec, tick) + 1; - else - ticks = LONG_MAX; - if (ticks > INT_MAX) - ticks = INT_MAX; - return ((int)ticks); + /* check for tv_usec overflow */ + } else if (__predict_false(tv->tv_usec >= 1000000)) { + tv->tv_sec += tv->tv_usec / 1000000; + tv->tv_usec = tv->tv_usec % 1000000; + } + + /* check for tv_sec underflow */ + if (__predict_false(tv->tv_sec < 0)) + return (1); + /* check for tv_sec overflow (including room for the tv_usec part) */ + else if (__predict_false(tv->tv_sec >= tick_seconds_max)) + return (INT_MAX); + + /* cast to "int" to avoid platform differences */ + retval = TIME_TO_TICKS((int)tv->tv_sec, (int)tv->tv_usec, hz); + + /* add one additional tick */ + return (retval + 1); } /* diff --git a/sys/kern/subr_param.c b/sys/kern/subr_param.c index 94b60a6e5538..fe2aadb74797 100644 --- a/sys/kern/subr_param.c +++ b/sys/kern/subr_param.c @@ -88,6 +88,7 @@ static int sysctl_kern_vm_guest(SYSCTL_HANDLER_ARGS); int hz; /* system clock's frequency */ int tick; /* usec per tick (1000000 / hz) */ +time_t tick_seconds_max; /* max hz * seconds an integer can hold */ struct bintime tick_bt; /* bintime per tick (1s / hz) */ sbintime_t tick_sbt; int maxusers; /* base tunable */ @@ -191,6 +192,7 @@ init_param1(void) tick = 1000000 / hz; tick_sbt = SBT_1S / hz; tick_bt = sbttobt(tick_sbt); + tick_seconds_max = INT_MAX / hz; /* * Arrange for ticks to wrap 10 minutes after boot to help catch diff --git a/sys/sys/time.h b/sys/sys/time.h index 5d7f3f07234e..20375b9a82af 100644 --- a/sys/sys/time.h +++ b/sys/sys/time.h @@ -505,6 +505,7 @@ extern volatile time_t time_second; extern volatile time_t time_uptime; extern struct bintime tc_tick_bt; extern sbintime_t tc_tick_sbt; +extern time_t tick_seconds_max; extern struct bintime tick_bt; extern sbintime_t tick_sbt; extern int tc_precexp;