svn commit: r346176 - head/sys/sys

[Bruce Evans]

On Sat, 13 Apr 2019, Warner Losh wrote:

>  Fix sbttons for values > 2s
>
>  Add test against negative times. Add code to cope with larger values
>  properly.
>
>  Discussed with: bde@ (quite some time ago, for an earlier version)

I am unhappy with previous attempted fixes in this area, and still have large
local patches.

Old versions supported negative times.  This was broken in 2 stages:
- use a buggy inline conversion function instead of a working macro
- break negative times further when fixing overflow bugs in the inline
   function
- attempt to panic for negative times, but actually do nothing since
   this is in unreachable code.

> Modified: head/sys/sys/time.h
> ==============================================================================
> --- head/sys/sys/time.h	Sat Apr 13 04:42:17 2019	(r346175)
> +++ head/sys/sys/time.h	Sat Apr 13 04:46:35 2019	(r346176)
> @@ -184,8 +184,18 @@ sbttobt(sbintime_t _sbt)
> static __inline int64_t
> sbttons(sbintime_t _sbt)
> {
> +	uint64_t ns;
>
> -	return ((1000000000 * _sbt) >> 32);

sbintime_t is a signed type so as to support negative times.  This function
returns a signed type so as to support negative times.

The original sloppy and fast version with a macro worked for all negative
times, modulo the assumption that right shifts propagate the sign bit.
It just did _sbt >> 32.

The above slower and more accurate version might have worked for negative
times similarly, but this is less clear.  E.g., if _sbt is -1 second, that
is 0xffffffff (-1) in the high 32 bits and 0 in the low 32 bits.
Multiplying this by 10**9 doesn't overflow since both terms are signed,
and gives a result near -1 in the high bits and the shift works before.
I think similarly for all negative values down to the overflow threshold
of about -2 seconds.

Similarly for the other functions -- the simple shifts just worked
(unportably), while all later versions have overflow and/or sign extension
bugs.

> +#ifdef KASSERT
> +	KASSERT(_sbt >= 0, ("Negative values illegal for sbttons: %jx", _sbt));
> +#endif

KASSERT is never defined here except in code with style bugs.  In the
kernel, sys/time.h is never included directly except in code with style
bugs.  It is normally included as part of standard namespace pollution
in sys/param.h.  Namespace pollution defeats ifdefs like this.  KASSERT
is only defined in sys/systm.h (except...), so it is never defined when
sys/param.h includes sys/time.h (except in code with even worse style
bugs, such as including sys/systm.h unsorted before sys/systm.h...).

In userland, KASSERT is never defined here except in code with style bugs
(such as being chummy with the implementation and defining KASSERT to use
here) and in code to demonstrate the brokenness of this header (KASSERT is
in the application namespace, so the demonstration can define it as
'syntax error'.

> +	ns = _sbt;

This corrupts the type from signed to unsigned.

This has no effect except to ensure breaking negative times.  E.g., if
the time is not negative, then the conversion doesn't change its value.
Ottherwise, the conversion prevents propagation of the sign bit.  E.g,
if the time is -1 then shifting right the signed value by 32 keeps it
as -1, but shifting right the unsigned value gives UINT32_MAX seconds =
UINT32_MAX * 10**9 nsec = about 1/4 of UINT64_MAX seconds.  Since this
and all other possible values in ns are less than 1/4 UINT64_MAX, then
are also less than INT64_MAX, so conversion back to a signed type doesn't
overflow them back to a negative value.

> +	if (ns >= SBT_1S)
> +		ns = (ns >> 32) * 1000000000;
> +	else
> +		ns = 0;
> +

Style bug (extra blank line).  In KNF, statements are separated by a
semilcolon and a single newline.  An extra newline is especially bad
when it is used to separate closely related statements like here.

> +	return (ns + (1000000000 * (_sbt & 0xffffffffu) >> 32));

This seems to be correct, except for its style bugs of spelling the U
suffix in lower case.  I don't like using the suffix, but the value
of plain 0xffffffff after promotion to the type of _sbt is unclear.

> }
>
> static __inline sbintime_t

Conversion in the opposite direction is more difficult and buggier.  I
currently use the following cut down version with only the most important
function fixed:

XX Index: time.h
XX ===================================================================
XX --- time.h	(revision 346046)
XX +++ time.h	(working copy)
XX @@ -200,8 +200,20 @@
XX  		sb = (_ns / 1000000000) * SBT_1S;
XX  		_ns = _ns % 1000000000;

These divisons are very slow on i386, and not very fast on amd64.  They
defeat the manual reductions to shifts and multiplications in the rest
of the code.  This case starts unnecessarily early (at 1 second instead
of at the overflow threshold of 4+ seconds).

XX  	}
XX +#if 0
XX  	/* 9223372037 = ceil(2^63 / 1000000000) */
XX  	sb += ((_ns * 9223372037ull) + 0x7fffffff) >> 31;

Current version that I don't like, due to its magic 922* and use of the
long long abomination, and wrong magic bias 0x7fffffff (this almost works.
IIRC, it gives errors of 1-3 sbintime_t values (fractional nsec) and it
is hard to see why the errors are so small since its value makes no sense).

XX +#elif 0
XX +	sb += (_ns * (((uint64_t)1 << 63) / 500000000 + 1) + 0xffffffff) >> 32;

Similar version without the abomination and without the magic numbers divided
by 2.

The 922* number is bogus for another reason.  It is reduced from an 1844*
number (== UINT64_MAX divided by some power of 10) so as to avoid overflow
for signed values.  But the code is supposed to eliminate signed values.
It can use the more natural number 1844* or the better expression for it
above together with not dividing everything by 2.

I now remember one source of the off by 1-3 error.  Dividing everything by
2 loses 1 bit, so gives off by 1 errors.  Maybe the 0x7fffffff magic number
is correct after all.

XX +#elif 1
XX +	sb += (_ns << 32) / 1000000000 + (_ns == 0 ? 0 : 1);

Not the best version, but it is what I have been using.  It depends on
division being fast or the compiler reducing division to multiplication,
and to do this, first notice that _ns has been reduced to 32 bits so
the division is not a full 64-bit one.  Then always round up except
for _ns = 0, and add 1 even if the result is already correctly rounded.
This rounding is sloppy and not quite right, but so is the rounding
resulting from adding the bias before the shift.

XX +#else
XX +	uint64_t factor, frac;
XX +
XX +	factor = ((uint64_t)1 << 63) / 500000000;
XX +	frac = ((0 - factor * 1000000000) << 32) / 1000000000;
XX +	sb += (_ns * factor + ((_ns * frac) >> 32) + 0xffffffff) >> 32;
XX +#endif

This version is supposed to do correct rounding.  It is significantly slower,
but not nearly as slow as the mul/div by 10**9 above the threshold.  The
compiler is supposed to turn the division by 10**9 here into a multiplication,
but it looks like I was not careful enough to reduce so that this is possible,
so this is very slow on i386 where I didn't test it and not fast on amd64
where I did test it.

XX  	return (sb);
XX  }
XX

See also my fixes in calcru1().  These do the scaling more carefully than
the above, but the final conversion of the result in usec to a timeval is
very slow on i386, etc., as usual because mul/div of 64-bit usec by 10**6
is very slow.  More precisely, it is very slow only in the kernel since
libkern still uses a very slow method written in C, and merely slow
in userland where libgcc uses a method half as good as possible.

The old macro versions are also much better in the usual case where the
caller doesn't care about accuracy.

Bruce