Skip site navigation (1)Skip section navigation (2)
Date:      Sat, 15 Dec 2012 19:44:42 +1100 (EST)
From:      Bruce Evans <brde@optusnet.com.au>
To:        Oliver Pinter <oliver.pntr@gmail.com>
Cc:        Davide Italiano <davide@freebsd.org>, freebsd-current <freebsd-current@freebsd.org>, freebsd-arch@freebsd.org
Subject:   Re: [RFC/RFT] calloutng
Message-ID:  <20121215183409.U1603@besplex.bde.org>
In-Reply-To: <CAPjTQNGL_7LnffWB5bbEgW0b6ekOrVzH6QQ6e2=fCFW4%2BmF6FA@mail.gmail.com>
References:  <CACYV=-F7_imU-JsPfeOZEyEPGKO2PVm1w1W3VdsH3jGiDvnmBg@mail.gmail.com> <CA%2BhQ2%2BgyhRHkB9Y%2BeGADvbjvJxSNSjYC%2BTQX8-0mf9LUD1V2HA@mail.gmail.com> <CACYV=-G9sG1Oo%2Bgz3kXmdeK85P7%2BZZg1CnAPLvwCuAbNftmv6A@mail.gmail.com> <CACYV=-EQ=G3JZOQ-9ExGT9spbEGtH5bJOrrgN2oeE2Qh3_rKag@mail.gmail.com> <CAPjTQNGL_7LnffWB5bbEgW0b6ekOrVzH6QQ6e2=fCFW4%2BmF6FA@mail.gmail.com>

next in thread | previous in thread | raw e-mail | index | archive | help
On Fri, 14 Dec 2012, Oliver Pinter wrote:

> 635 -       return tticks;
> 636 +       getbinuptime(&pbt);
> 637 +       bt.sec = data / 1000;
> 638 +       bt.frac = (data % 1000) * (uint64_t)1844674407309000LL;
> 639 +       bintime_add(&bt, &pbt);
> 640 +       return bt;

Style bugs: missing spaces around return value in new and old code.

> 641  }
>
> What is this 1844674407309000LL constant?

This is

     2**64 / 10**6 * 10**3

obfuscated by printing it in hex and doing the scaling by powers of
10 manually, and then giving it a bogus type using the abominable long
long misfeature.  I try to kill this obfuscation and the abimination
whenever I see them.  In sys/time.h, this resulted in a related binary
conversion using a scale factor of

     ((uint64_t)1 << 63) / (1000000000 >> 1).

Here the power of 2 term is 2**63.   2**64 cannot be used since it exceeds
uintmax_t.  The power of 10 term is 10**9.  This is divided by 2 to
compensate for dividing 2**64 by 2.  The abomination is avoided by using
smaller literal values and expandling them to 64-bit values using shifts.

Long long suffixes on literal constants are only needed to support C90
compilers with the long long extension on 32-bit systems anyway.
Otherwise, C90+extension compilers will warn about literal constants
larger than ULONG_MAX (which can only occur on 32-bit systems).  Since
C99 is now the default, the warnings would only without LL in the above
if you use nonstandard CFLAGS.

The above has to convert from the bad units of milliseconds to the bloated
units of bintimes, and it is less refined than most other bintime
conversions.  I think that since it doesn't try to be optimal, it should
just use the standard bintime conversions after first converting
milliseconds to a timeval.  It already does essentially that with its
divisions by 1000:

 	struct timeval tv;

 	tv.tv_sec = data / 1000;
 	tv.tv_usec = data % 1000 * 1000;
 	timeval2bintime(&tv, &bt);

The compliler will probably optimize /1000 and %1000 to shifts in both
this and the above.  Then timeval2bintime() does the almost the same
multiplication as above, but spelled differently accuracy.  Both give
unnecessary inaccuracy in the conversion to weenieseconds: the first
gives:

 	bt.frac = data % 1000 * (2**64 / 10**6 * 10**3);

the second gives:

 	bt.frac = data % 1000 * 1000 * (2**64 / 10**6);

Because of the different grouping of the multiplications, the second
is unfortunately slower (1 more multiplication that cannot be done at
compile time).  The second also gives unnecessary (but findamental to
the method) inaccuracy by pulling out the factor of 1000.  The first
gives the same inaccuracy, and now it is because the constant is not
correctly rounded.  It should be

 	2.0**64 / 10**3 = 1844674407309551.616 (exactly)
 	                = 1844674407309552     (rounded to nearest int)

but is actually rounded down to a multiple of 1000.

It would be better to round the scale factors so that the conversions
are inverses of each other and tticks can be recovered from bt, but
this is impossible.  I tried to make the bintime conversions invert
most values correctly by rounding to nearest, but phk didn't like this
and the result is the bogus comment about always rounding down in time.h.
So when you start with 999 msec in tticks, the resulting bt will be
rounded down a little and converting back will give 998 msec; the
next round of conversions will reduce 1 more, and so on until you
reach a value that is exactly representable in both milliseconds and
weenieseconds (875?).  This despite weenieseconds providing vastly
more accuracy than can be measured and vastly more accuracy than needed
to represent all other time values in the kernel in a unique way.  Just
not in a unique way that is expressible using simple scaling conversions.
The conversions that give uniqueness can still be monotonic, but can't
be nonlinear in the same way that simple scaling gives.

Bruce



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20121215183409.U1603>