Date: Fri, 1 Mar 2019 13:27:17 +0200 From: Konstantin Belousov <kib@freebsd.org> To: Mark Millard <marklmi@yahoo.com>, bde@freebsd.org Cc: freebsd-hackers Hackers <freebsd-hackers@freebsd.org>, FreeBSD PowerPC ML <freebsd-ppc@freebsd.org> Subject: Re: powerpc64 head -r344018 stuck sleeping problems: th->th_scale * tc_delta(th) overflows unsigned 64 bits sometimes [patched failed] Message-ID: <20190301112717.GW2420@kib.kiev.ua> In-Reply-To: <28C2BB0A-3DAA-4D18-A317-49A8DD52778F@yahoo.com> References: <D3D7E9F4-9A5E-4320-B3C8-EC5CEF4A2764@yahoo.com> <20190228145542.GT2420@kib.kiev.ua> <20190228150811.GU2420@kib.kiev.ua> <962D78C3-65BE-40C1-BB50-A0088223C17B@yahoo.com> <28C2BB0A-3DAA-4D18-A317-49A8DD52778F@yahoo.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, Feb 28, 2019 at 11:39:06PM -0800, Mark Millard wrote:
> [The new, trial code also has truncation occurring.]
In fact no, I do not think it is.
> An example observation of diff_scaled having an overflowed
> value was:
>
> scale_factor == 0x80da2067ac
> scale_factor*freq overflows unsigned, 64 bit representation.
> tim_offset == 0x3da0eaeb
> tim_cnt == 0x42dea3c4
> tim_diff == 0x53db8d9
> For reference: 0x1fc9d43 == 0xffffffffffffffffull/scale_factor
> scaled_diff == 0xA353A5BF3FF780CC (truncated to 64 bits)
>
> But for the new, trail code:
>
> 0x80da2067ac is 40 bits
> 0x53db8d9 is 27 bits
> So 67 bits, more than 63. Then:
>
> x
> == (0x80da2067ac>>32) * 0x53db8d9
> == 0x80 * 0x53db8d9
> == 0x29EDC6C80
>
> x>>32
> == 0x2
>
> x<<32
> == 0x9EDC6C8000000000 (limited to 64 bits)
> Note the truncation of: 0x29EDC6C8000000000.
Right, this is how the patch is supposed to work. Note that the overflow
bits 'lost' due to overflow of the left shift are the same bits that as
used to increment bt->sec:
bt->sec += x >> 32;
So the 2 seconds are accounted for.
>
> Thus the "bintime_addx(bt, x << 32)" is still
> based on a truncated value.
>
I must admit that 2 seconds of interval where the timehands where
not updated is too much. This might be the real cause of all ppc
troubles. I tried to see if the overflow case is possible on amd64,
and did not get a single case of the '> 63' branch executed during the
/usr/tests/lib/libc run.
Actually, the same overflow-prone code exists in libc, so below is the
updated patch:
- I added __predict_false()
- libc multiplication is also done separately for high-order bits.
(fftclock counterpart is still pending).
diff --git a/lib/libc/sys/__vdso_gettimeofday.c b/lib/libc/sys/__vdso_gettimeofday.c
index 3749e0473af..a14576988ff 100644
--- a/lib/libc/sys/__vdso_gettimeofday.c
+++ b/lib/libc/sys/__vdso_gettimeofday.c
@@ -32,6 +32,8 @@ __FBSDID("$FreeBSD$");
#include <sys/time.h>
#include <sys/vdso.h>
#include <errno.h>
+#include <limits.h>
+#include <strings.h>
#include <time.h>
#include <machine/atomic.h>
#include "libc_private.h"
@@ -62,6 +64,7 @@ binuptime(struct bintime *bt, struct vdso_timekeep *tk, int abs)
{
struct vdso_timehands *th;
uint32_t curr, gen;
+ uint64_t scale, x;
u_int delta;
int error;
@@ -78,7 +81,14 @@ binuptime(struct bintime *bt, struct vdso_timekeep *tk, int abs)
continue;
if (error != 0)
return (error);
- bintime_addx(bt, th->th_scale * delta);
+ scale = th->th_scale;
+ if (__predict_false(fls(scale) + fls(delta) > 63)) {
+ x = (scale >> 32) * delta;
+ scale &= UINT_MAX;
+ bt->sec += x >> 32;
+ bintime_addx(bt, x << 32);
+ }
+ bintime_addx(bt, scale * delta);
if (abs)
bintime_add(bt, &th->th_boottime);
diff --git a/sys/kern/kern_tc.c b/sys/kern/kern_tc.c
index 2656fb4d22f..be75781e000 100644
--- a/sys/kern/kern_tc.c
+++ b/sys/kern/kern_tc.c
@@ -355,13 +355,22 @@ void
binuptime(struct bintime *bt)
{
struct timehands *th;
- u_int gen;
+ uint64_t scale, x;
+ u_int delta, gen;
do {
th = timehands;
gen = atomic_load_acq_int(&th->th_generation);
*bt = th->th_offset;
- bintime_addx(bt, th->th_scale * tc_delta(th));
+ scale = th->th_scale;
+ delta = tc_delta(th);
+ if (__predict_false(fls(scale) + fls(delta) > 63)) {
+ x = (scale >> 32) * delta;
+ scale &= UINT_MAX;
+ bt->sec += x >> 32;
+ bintime_addx(bt, x << 32);
+ }
+ bintime_addx(bt, scale * delta);
atomic_thread_fence_acq();
} while (gen == 0 || gen != th->th_generation);
}
@@ -388,13 +397,22 @@ void
bintime(struct bintime *bt)
{
struct timehands *th;
- u_int gen;
+ uint64_t scale, x;
+ u_int delta, gen;
do {
th = timehands;
gen = atomic_load_acq_int(&th->th_generation);
*bt = th->th_bintime;
- bintime_addx(bt, th->th_scale * tc_delta(th));
+ scale = th->th_scale;
+ delta = tc_delta(th);
+ if (__predict_false(fls(scale) + fls(delta) > 63)) {
+ x = (scale >> 32) * delta;
+ scale &= UINT_MAX;
+ bt->sec += x >> 32;
+ bintime_addx(bt, x << 32);
+ }
+ bintime_addx(bt, scale * delta);
atomic_thread_fence_acq();
} while (gen == 0 || gen != th->th_generation);
}
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20190301112717.GW2420>