From nobody Sun Oct 23 08:14:19 2022 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4Mw9wC4ltGz4gX4H; Sun, 23 Oct 2022 08:14:19 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4Mw9wC4CPHz43yP; Sun, 23 Oct 2022 08:14:19 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1666512859; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=jYhLifIEE0Z+w6iKm9LxEuciA2C7Q8F31LOhfDfPWWI=; b=d9euDupHjshsXLgGIv2x+Vc3D+rIEKI78cXn+a3QaZ73gal4QOlOZF0Y56Zff+SxNzJBjt Y/4iR3TV1M1IXdEap3vLgKjPsdu/Tudz44XmgtU1xSd8uWCJUA7Kt9pg7Q5r7C3nmSeC6r iUXm+oSJ9s+LLtO7JpixIV0avL8uHKjF0dqEuS2aH/nriP0R0ecBQc0TQncYREyuRcEJTS 4SHhL+jWRzlXCs0+K7KhjalGd3An+4e8guhJD7mnHXL92YA+yN3TyQO9++cWz6ECNBSGnS IS08DwlH9DZMrT+qlgRryJGDSQJ2POxJw9T6rQv7PfuKjK0//b7d5cLWwIKhhQ== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4Mw9wC3JQlzqRx; Sun, 23 Oct 2022 08:14:19 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 29N8EJVD054303; Sun, 23 Oct 2022 08:14:19 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 29N8EJoC054302; Sun, 23 Oct 2022 08:14:19 GMT (envelope-from git) Date: Sun, 23 Oct 2022 08:14:19 GMT Message-Id: <202210230814.29N8EJoC054302@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Hans Petter Selasky Subject: git: 35a33d14b593 - main - time(3): Optimize tvtohz() function. List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: hselasky X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 35a33d14b593ba93feb8fed8d0689bc8e0edd15b Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1666512859; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=jYhLifIEE0Z+w6iKm9LxEuciA2C7Q8F31LOhfDfPWWI=; b=jTmQwHHIR5CT8uvELW1BCnCBfv83nZKqC/FJX4a6bB7coJSNzsA90QQp2VOyuIPDfZTHT+ QhZzD3UawB94EPpFGzrvwFi+ZcOzaFmeNi5M8tAJS5C/t665blcMSapVItPSzxSsmE4gXt 2oOEORC9AIsN/p7jRyiyNrqpFvBxDvKZlnDcxzlmsoGgJFdG7YfmSc8OThh6rNMtblmXrC DH4uFMedejxuo4ySSnmyvLkvkyQDJPjuKNMQogXZbCdESl2+hf0ViqCuYF+M/K29i4QEdK CL+sTFrPHelNipRX8axR4G2MNZQy5bcWvvdZtseeSU8PqqAJHQNreip9nWrBSA== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1666512859; a=rsa-sha256; cv=none; b=Ou+5kw3A3SMmvN4pkEaRR53XluWeAG3+HaLms0J+XIRSd8bYlT2w9/8j8DyYg/QrCM/rx4 zDyHIT9kZyVdV/ZgRwutrMLFZOG8fTNYVnxlrNuBa3BSx0VYhybpsAVThBmKjxjxbJ1jBO k7rsRaiKwySFyCBcO+MhXHF297jLktHX9AF9yA8DFmt6IuF1f9ogtMwNLH52cIw1l1n4mU xwJ2K/ZGZjX076gLylePQx8Mr4xGj0REru42a0JdLKZZFrmf2kkzZQ9xOh03TEie0lQ7i7 qlFm/FwjaGVAJ8uwO+1LvDdpZpA3282DERQUECEFXHiaqeEXh4szFw0qqAyazQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by hselasky: URL: https://cgit.FreeBSD.org/src/commit/?id=35a33d14b593ba93feb8fed8d0689bc8e0edd15b commit 35a33d14b593ba93feb8fed8d0689bc8e0edd15b Author: Hans Petter Selasky AuthorDate: 2022-10-20 16:49:51 +0000 Commit: Hans Petter Selasky CommitDate: 2022-10-23 08:04:50 +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@ MFC after: 1 week Sponsored by: NVIDIA Networking Differential Revision: https://reviews.freebsd.org/D36859 --- 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 5f2492c473b8..c4bb648e3f25 100644 --- a/sys/kern/kern_clock.c +++ b/sys/kern/kern_clock.c @@ -556,60 +556,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 f9c2f8df87b8..e9d7ddd49e63 100644 --- a/sys/kern/subr_param.c +++ b/sys/kern/subr_param.c @@ -84,6 +84,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 */ @@ -187,6 +188,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;