From nobody Tue Oct 04 11:53:04 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 4MhbgN612vz4dgfl; Tue, 4 Oct 2022 11:53:04 +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 4MhbgN5Tzgz3W11; Tue, 4 Oct 2022 11:53:04 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1664884384; 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=oql0uO19D5sCdWoxxRUmiXRIH0+grp1GSGWn5X/Blec=; b=nzacdjUm4xMeizy6yRsMDeeKZsNfhARywvm2DJOi/a/e1To0rU0EtnYw/2CnwKo9lfEAlB kHCef+dSXH/trUX8LRyuRxZ5HbOq6xlPNA+/YZR0aapHdl582R1GUG1VvwD5By90gOc32P BiXCsIvT4B2ws2m5wxKe7u9nkjd9cElV0h6jXfZDIJF3MDTgriJ4F0GffJgiiqsYRJ7laH rwznm/a/fsUBtr1SjDuSLYTDRPzlZnQIPrZPIDmecvUaUMhArWdH9Hz7mRjq9LNDC1Zmmm Z2D6AM3CO32z9QO23UU+OkwSWp64kdx0iZVgRgBhqOXssVdcB2in9SCYmrt+QQ== 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 4MhbgN4XhwzYj7; Tue, 4 Oct 2022 11:53:04 +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 294Br4xi011557; Tue, 4 Oct 2022 11:53:04 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 294Br4Si011556; Tue, 4 Oct 2022 11:53:04 GMT (envelope-from git) Date: Tue, 4 Oct 2022 11:53:04 GMT Message-Id: <202210041153.294Br4Si011556@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: d97ecf714e79 - main - time(3): Increase precision of time conversion functions by using gcd. 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: d97ecf714e791ad8ca7caa969fd9a5e9347fc96a Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1664884384; 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=oql0uO19D5sCdWoxxRUmiXRIH0+grp1GSGWn5X/Blec=; b=D6mWSLWMlDJlFb2DZoYbNY6h7B9VHQy1pFssIyjzVYOgOygXHwgr9diH4GCet35Dqj0Oty FIW5h6H8GT8igyhg1qAo40UtZbA28YJ+p+GSE75wJ6wEbIT8H5pA5j+WrfZi8PIgZ1mpdk hEQK8uzA8JOYqUDv9J7EouMMcpXwKFDoq/+ECJd7ACI0GTSLSavBrXaOIMDIEEEuLwBqNB timf6G045Y0R2oPHmU+oCl5xG1qqbNwCbXqFhUcNzRPN4SNhL16cUvvUWjbDdevo9Cbl+v ndSbN2GjD+W83YGnpN5EhW6gLqVRWo0gzRvH5V9lGadoijQQHfEi5VNxTLjsdQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1664884384; a=rsa-sha256; cv=none; b=lqwPtzt8GTcd2XoBzdvB4L33Yvd+Mtj8JDAqk2BoCjr5DVOizWE0xPlHB8OisqoZzHQk6z dGOQqiyDfkyDasigAhmkuQJzEANB8fZRXDNkUdTr0Y3ezpd/5mLONZJT2jRgpK/ruEsdAf 5tAyeA/RZhIevyjza00ySh5GLfVYhN12jMTlT9d9UapQAWHmOQTuY/Wi8S84v5c7Ztz/qE ftIo0TLJReakSq1ZUxLbVReUox68P0K5jQ2iAdph3ezhY7ti3mEOanh8gQaiCCmqrVOrfZ va4lvtmqfHdJcRGpteHDuEuDmgxxpfIE4ZLCfzpKI9YpXkUWK9Yab2lBwXjqqg== 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=d97ecf714e791ad8ca7caa969fd9a5e9347fc96a commit d97ecf714e791ad8ca7caa969fd9a5e9347fc96a Author: Hans Petter Selasky AuthorDate: 2022-10-02 22:15:09 +0000 Commit: Hans Petter Selasky CommitDate: 2022-10-04 11:51:06 +0000 time(3): Increase precision of time conversion functions by using gcd. When converting times to and from units which have many leading zeros, it pays off to compute the greatest common divisor first, and then do the scaling product. This way all time unit conversion comes down to scaling a signed or unsigned 64-bit value by a fraction represented by two signed or unsigned 32-bit integers. SBT_1S is defined as 2^32 . When scaling using powers of 10 above 1, the gcd of SBT_1S and 10^N is always greater than or equal to 4, when N is greater or equal to 2. Scaling a sbt value to milliseconds is then done by multiplying by (1000 / 8) and dividing by (2^32 / 8). This trick allows for higher precision at very little additional CPU cost. It shall also be noted that the Xtosbt() functions prior to this patch, sometimes were off-by-one: For example when converting 1 / 8 of a second to sbt as 125ms the old sbt conversion function would compute 0x20000001 while the new function computes 0x20000000 which multiplied by 8 becomes SBT_1S, which is the correct value. Reviewed by: kib@ Differential Revision: https://reviews.freebsd.org/D36857 MFC after: 1 week Sponsored by: NVIDIA Networking --- sys/sys/time.h | 194 ++++++++++++++++++++++++++++++--------------------------- 1 file changed, 101 insertions(+), 93 deletions(-) diff --git a/sys/sys/time.h b/sys/sys/time.h index ce4c7c1b555e..41d84aab5640 100644 --- a/sys/sys/time.h +++ b/sys/sys/time.h @@ -159,117 +159,124 @@ sbttobt(sbintime_t _sbt) } /* - * Decimal<->sbt conversions. Multiplying or dividing by SBT_1NS results in - * large roundoff errors which sbttons() and nstosbt() avoid. Millisecond and - * microsecond functions are also provided for completeness. - * - * These functions return the smallest sbt larger or equal to the - * number of seconds requested so that sbttoX(Xtosbt(y)) == y. Unlike - * top of second computations below, which require that we tick at the - * top of second, these need to be rounded up so we do whatever for at - * least as long as requested. - * - * The naive computation we'd do is this - * ((unit * 2^64 / SIFACTOR) + 2^32-1) >> 32 - * However, that overflows. Instead, we compute - * ((unit * 2^63 / SIFACTOR) + 2^31-1) >> 32 - * and use pre-computed constants that are the ceil of the 2^63 / SIFACTOR - * term to ensure we are using exactly the right constant. We use the lesser - * evil of ull rather than a uint64_t cast to ensure we have well defined - * right shift semantics. With these changes, we get all the ns, us and ms - * conversions back and forth right. - * Note: This file is used for both kernel and userland includes, so we can't - * rely on KASSERT being defined, nor can we pollute the namespace by including - * assert.h. + * Scaling functions for signed and unsigned 64-bit time using any + * 32-bit fraction: */ + static __inline int64_t -sbttons(sbintime_t _sbt) +__stime64_scale32_ceil(int64_t x, int32_t factor, int32_t divisor) { - uint64_t ns; + const int64_t rem = x % divisor; -#ifdef KASSERT - KASSERT(_sbt >= 0, ("Negative values illegal for sbttons: %jx", _sbt)); -#endif - ns = _sbt; - if (ns >= SBT_1S) - ns = (ns >> 32) * 1000000000; - else - ns = 0; + return (x / divisor * factor + (rem * factor + divisor - 1) / divisor); +} + +static __inline int64_t +__stime64_scale32_floor(int64_t x, int32_t factor, int32_t divisor) +{ + const int64_t rem = x % divisor; - return (ns + (1000000000 * (_sbt & 0xffffffffu) >> 32)); + return (x / divisor * factor + (rem * factor) / divisor); } -static __inline sbintime_t -nstosbt(int64_t _ns) +static __inline uint64_t +__utime64_scale32_ceil(uint64_t x, uint32_t factor, uint32_t divisor) { - sbintime_t sb = 0; + const uint64_t rem = x % divisor; -#ifdef KASSERT - KASSERT(_ns >= 0, ("Negative values illegal for nstosbt: %jd", _ns)); -#endif - if (_ns >= 1000000000) { - sb = (_ns / 1000000000) * SBT_1S; - _ns = _ns % 1000000000; - } - /* 9223372037 = ceil(2^63 / 1000000000) */ - sb += ((_ns * 9223372037ull) + 0x7fffffff) >> 31; - return (sb); + return (x / divisor * factor + (rem * factor + divisor - 1) / divisor); } -static __inline int64_t -sbttous(sbintime_t _sbt) +static __inline uint64_t +__utime64_scale32_floor(uint64_t x, uint32_t factor, uint32_t divisor) { + const uint64_t rem = x % divisor; -#ifdef KASSERT - KASSERT(_sbt >= 0, ("Negative values illegal for sbttous: %jx", _sbt)); -#endif - return ((_sbt >> 32) * 1000000 + - (1000000 * (_sbt & 0xffffffffu) >> 32)); + return (x / divisor * factor + (rem * factor) / divisor); } -static __inline sbintime_t -ustosbt(int64_t _us) +/* + * This function finds the common divisor between the two arguments, + * in powers of two. Use a macro, so the compiler will output a + * warning if the value overflows! + * + * Detailed description: + * + * Create a variable with 1's at the positions of the leading 0's + * starting at the least significant bit, producing 0 if none (e.g., + * 01011000 -> 0000 0111). Then these two variables are bitwise AND'ed + * together, to produce the greatest common power of two minus one. In + * the end add one to flip the value to the actual power of two (e.g., + * 0000 0111 + 1 -> 0000 1000). + */ +#define __common_powers_of_two(a, b) \ + ((~(a) & ((a) - 1) & ~(b) & ((b) - 1)) + 1) + +/* + * Scaling functions for signed and unsigned 64-bit time assuming + * reducable 64-bit fractions to 32-bit fractions: + */ + +static __inline int64_t +__stime64_scale64_ceil(int64_t x, int64_t factor, int64_t divisor) { - sbintime_t sb = 0; + const int64_t gcd = __common_powers_of_two(factor, divisor); -#ifdef KASSERT - KASSERT(_us >= 0, ("Negative values illegal for ustosbt: %jd", _us)); -#endif - if (_us >= 1000000) { - sb = (_us / 1000000) * SBT_1S; - _us = _us % 1000000; - } - /* 9223372036855 = ceil(2^63 / 1000000) */ - sb += ((_us * 9223372036855ull) + 0x7fffffff) >> 31; - return (sb); + return (__stime64_scale32_ceil(x, factor / gcd, divisor / gcd)); } static __inline int64_t -sbttoms(sbintime_t _sbt) +__stime64_scale64_floor(int64_t x, int64_t factor, int64_t divisor) { -#ifdef KASSERT - KASSERT(_sbt >= 0, ("Negative values illegal for sbttoms: %jx", _sbt)); -#endif - return ((_sbt >> 32) * 1000 + (1000 * (_sbt & 0xffffffffu) >> 32)); + const int64_t gcd = __common_powers_of_two(factor, divisor); + + return (__stime64_scale32_floor(x, factor / gcd, divisor / gcd)); } -static __inline sbintime_t -mstosbt(int64_t _ms) +static __inline uint64_t +__utime64_scale64_ceil(uint64_t x, uint64_t factor, uint64_t divisor) { - sbintime_t sb = 0; + const uint64_t gcd = __common_powers_of_two(factor, divisor); -#ifdef KASSERT - KASSERT(_ms >= 0, ("Negative values illegal for mstosbt: %jd", _ms)); -#endif - if (_ms >= 1000) { - sb = (_ms / 1000) * SBT_1S; - _ms = _ms % 1000; - } - /* 9223372036854776 = ceil(2^63 / 1000) */ - sb += ((_ms * 9223372036854776ull) + 0x7fffffff) >> 31; - return (sb); + return (__utime64_scale32_ceil(x, factor / gcd, divisor / gcd)); +} + +static __inline uint64_t +__utime64_scale64_floor(uint64_t x, uint64_t factor, uint64_t divisor) +{ + const uint64_t gcd = __common_powers_of_two(factor, divisor); + + return (__utime64_scale32_floor(x, factor / gcd, divisor / gcd)); } +/* + * Decimal<->sbt conversions. Multiplying or dividing by SBT_1NS + * results in large roundoff errors which sbttons() and nstosbt() + * avoid. Millisecond and microsecond functions are also provided for + * completeness. + * + * When converting from sbt to another unit, the result is always + * rounded down. When converting back to sbt the result is always + * rounded up. This gives the property that sbttoX(Xtosbt(y)) == y . + * + * The conversion functions can also handle negative values. + */ +#define SBT_DECLARE_CONVERSION_PAIR(name, units_per_second) \ +static __inline int64_t \ +sbtto##name(sbintime_t sbt) \ +{ \ + return (__stime64_scale64_floor(sbt, units_per_second, SBT_1S)); \ +} \ +static __inline sbintime_t \ +name##tosbt(int64_t name) \ +{ \ + return (__stime64_scale64_ceil(name, SBT_1S, units_per_second)); \ +} + +SBT_DECLARE_CONVERSION_PAIR(ns, 1000000000) +SBT_DECLARE_CONVERSION_PAIR(us, 1000000) +SBT_DECLARE_CONVERSION_PAIR(ms, 1000) + /*- * Background information: * @@ -289,8 +296,8 @@ bintime2timespec(const struct bintime *_bt, struct timespec *_ts) { _ts->tv_sec = _bt->sec; - _ts->tv_nsec = ((uint64_t)1000000000 * - (uint32_t)(_bt->frac >> 32)) >> 32; + _ts->tv_nsec = __utime64_scale64_floor( + _bt->frac, 1000000000, 1ULL << 32) >> 32; } static __inline uint64_t @@ -299,8 +306,8 @@ bintime2ns(const struct bintime *_bt) uint64_t ret; ret = (uint64_t)(_bt->sec) * (uint64_t)1000000000; - ret += (((uint64_t)1000000000 * - (uint32_t)(_bt->frac >> 32)) >> 32); + ret += __utime64_scale64_floor( + _bt->frac, 1000000000, 1ULL << 32) >> 32; return (ret); } @@ -309,8 +316,8 @@ timespec2bintime(const struct timespec *_ts, struct bintime *_bt) { _bt->sec = _ts->tv_sec; - /* 18446744073 = int(2^64 / 1000000000) */ - _bt->frac = _ts->tv_nsec * (uint64_t)18446744073LL; + _bt->frac = __utime64_scale64_floor( + (uint64_t)_ts->tv_nsec << 32, 1ULL << 32, 1000000000); } static __inline void @@ -318,7 +325,8 @@ bintime2timeval(const struct bintime *_bt, struct timeval *_tv) { _tv->tv_sec = _bt->sec; - _tv->tv_usec = ((uint64_t)1000000 * (uint32_t)(_bt->frac >> 32)) >> 32; + _tv->tv_usec = __utime64_scale64_floor( + _bt->frac, 1000000, 1ULL << 32) >> 32; } static __inline void @@ -326,8 +334,8 @@ timeval2bintime(const struct timeval *_tv, struct bintime *_bt) { _bt->sec = _tv->tv_sec; - /* 18446744073709 = int(2^64 / 1000000) */ - _bt->frac = _tv->tv_usec * (uint64_t)18446744073709LL; + _bt->frac = __utime64_scale64_floor( + (uint64_t)_tv->tv_usec << 32, 1ULL << 32, 1000000); } static __inline struct timespec