Created attachment 1385 [details]
Patch for ntpdate

A repo that should fix the issue is in

  psp.ntp.org:~perlinger/ntp-stable-3023

The original patch still leaves a few potential issues open. OTOH, the whole
thing with 's_fp' (as well as 'l_fp', when it comes to that) has some issues
with the standard, as it makes assumptions about the representation of negative
signed integer values and the behavior resulting from that.

(In reply to comment #2)
> A repo that should fix the issue is in
> 
>   psp.ntp.org:~perlinger/ntp-stable-3023
> 
> The original patch still leaves a few potential issues open. OTOH, the whole
> thing with 's_fp' (as well as 'l_fp', when it comes to that) has some issues
> with the standard, as it makes assumptions about the representation of negative
> signed integer values and the behavior resulting from that.


Has any consideration been given to replacing the l_fp stuff with a few FPU
instructions for the X86 architecture?  My limited testing seemed to indicate
that using the FPU assembly-language instructions did not make the code any
faster, but it sure looked cleaner.  Also, it was faster to use the FPU
instructions than the SSE instructions.  Left to its own devices VS Express
will occasionally use SSE instructions; it was not clear to me that those
substitutions made the code any faster.

(In reply to comment #3)
> 
> Has any consideration been given to replacing the l_fp stuff with a few FPU
> instructions for the X86 architecture?  My limited testing seemed to indicate
> that using the FPU assembly-language instructions did not make the code any
> faster, but it sure looked cleaner.  Also, it was faster to use the FPU
> instructions than the SSE instructions.  Left to its own devices VS Express
> will occasionally use SSE instructions; it was not clear to me that those
> substitutions made the code any faster.

l_fp and s_fp are actually fixed point, not floating point. I don't see how FPU
instructions should help here?

While some operations on l_fp can be done using (integer) SSE or MMX
intrinsics, doing so creates a real portability issue -- unless one has a fall
back strategy with (hopefully portable) C code.

Creating really machine-specific versions (and unfortunately that means
compiler-specific, too) of the _M_xyz macros in ntp_fp.h might give more value
for the money. At least for the 64-bit fixed point values. I gave that a try
once, but it gets messy very fast. And while I might stand corrected, IMHO ntpd
is not exactly a number-crunching application -- and where it *does* heavy
calculations, it uses double floats for it. 

So unless there is a real performance issue with the fixed point arithmetic I
don't feel inclined to tackle that on assembler level.

Of course, if there are any volunteers ... ;)

Thank you for your reply.

>l_fp and s_fp are actually fixed point, not floating point. I don't see how >FPU instructions should help here?


I have never seen s_fp instructions used, so I have no experience with them and
am in no position to comment.

The fundamental operation on the timestamps t1, t2, t3, and t4 is unsigned
64-bit integer subtract.  I tried loading them into the FPU as unsigned
integers and performing the subtract there as a way of circumventing the
somewhat opaque macros.  But since the results could be saved on the NDP stack,
conversion to floating-point delay and offset values would have every bit
available; there was no question of round-off error when the intermediate
products were saved as doubles.  The answers seemed to be correct, but there
was no real speed advantage, and as you point out, asking people to switch to
hand-coded FPU/NDP instructions for little or no savings seemed like a
non-starter.

>Of course, if there are any volunteers ... ;)
I would love to do this, if only the resulting code was more readable and
maintainable.  But every second of my time is committed to the research I am
doing as a sort of intern working from home just in hopes of securing a job so
I can pay off my education debts and actually do something with all this
education.  Plus, I am committed to making the server clock times maximum
likelihood estimates as per the spec, which is also requiring research and on 
which I can only spend one day a week.

I think we have a few options here...

1.) We could use proper (possibly inlined) functions to make the calculations
on the l_fp type, which is (as you pin-pointed) basically a 64bit integer.
Using structures by value as argument and return type is so common today that
using macros for that purpose has IMHO no real point.

2.) We could require that the compiler supports an unsigned 64-bit value, and
we make 'l_fp' a synonym for 'uint64_t'. (Signed integers are no good, due to
the quirks the C standard introduced for negative signed integers).

Option 2 would provide the most readable code, I think, but would also create
the most changes for glitches: Manual execution of two's complement arithmetic
on unsigned types is really error-prone. (It's easy to write something the
compiler groks without warning and that looks sensible but is not really what
you wanted to do...) It would give the best performance, though.

This is basically the only reason why I would prefer C++ here: We have some
arithmetic types (l_fp, s_fp, struct timespec/timeval) that could be wrapped
into C++ classes that would permit a combination of readability and performance
by proper operator overloads. But IMHO that's hardly a reason to convert ntp to
C++, though.

But even functions would be more readable than the macros, and it's easier to
make a generic implementation using portable C and specializations based on the
compiler/target pair.

Just my 5c here. Anyway, I think we should continue on this topic outside the
bug tracker, either via direct email or on one of the mailing lists. ;)

Alfonso, thanks for the report and patch!

Charles, thanks for your input.

Pearly, thanks for your work on this.

The fix is STAGED for 4.2.8p7.

Alfonso,

Thanks for the report.  Please check 4.2.8p7 and mark this bug as VERIFIED or
IN_PROGRESS, as appropriate.

Change should work, but I do not understand why the code tries so hard to get
an absolute value that gets used only for comparison.

In other words, whiy

        u_fp absoffset;
        if (server->soffset < 0)
            absoffset = 1u + (u_fp)(-(server->soffset + 1));
        else
            absoffset = (u_fp)server->soffset;
        dostep = (absoffset >= NTPDATE_THRESHOLD);

is better than

    dostep = server->soffset <= -NTPDATE_THRESHOLD || server->soffset >=
NTPDATE_THRESHOLD;

?

NTPDATE_THRESHOLD is representable as s_fp, so that is not an issue. Sorry for
commenting on this now, but I have not been able to see the solution until it
has been released, could not find where to look.

(In reply to comment #9)
> 
>         u_fp absoffset;
>         if (server->soffset < 0)
>             absoffset = 1u + (u_fp)(-(server->soffset + 1));
>         else
>             absoffset = (u_fp)server->soffset;
>         dostep = (absoffset >= NTPDATE_THRESHOLD);
> 

I guess I suffered from a bout of paranoia at the time...