sys_fuzzMime-Version: 1.0

[Gary E. Miller]

Yo Eric!

On Tue, 24 Jan 2017 20:35:23 -0500
"Eric S. Raymond" <esr at thyrsus.com> wrote:

> > The NTP case is roughly stiction.  Remember the age of this code.
> > It was working long before CPUs had instructions to read a cycle
> > counter.  Back then, the system clock was updated on the scheduler
> > interrupt.  There was no interpolation between ticks.  

[...]

> Stiction in this context = "adjacent clock reads could get back the
> same value", is that right?  Suddenly a whole bunch of things, like
> the implications of only updating the clock on a scheduler interrupt,
> make sense.

Yeah, I would go so far as saying  "adjacent clock reads will often
get back the same value"

> And now I think I get (a) why Mills fuzzed the clock, and (b) why the
> code is so careful about checking for clock stepback.  If your working
> assumption is that the clock will only update on a scheduler tick, and
> your PLL correction requires you to have a monotonically increasing
> clock, stiction is *bad*.

Yes.

> You have no choice but to fuzz the clock,

I think you went a tad too far.  Your other choice, like
CLOCK_MONOTONIC, is to just add a tiny value (a nano Sec) if it would
be a repeat.

Hard to say which is better as either effect is tiny,

> and the probabilistically least risky way to do it is by around half
> the tick interval, but because random is random you cannot guarantee
> when you have to do it twice between ticks that your second
> pseudosample will be greater than your first.  You need what the code
> calls a "Lamport violation" check to throw out bad pseudosamples.

Here is a description of "Lamport timestamps"

And the rules are simple:

    1. A process increments its counter before each event in that
    process;

    2. When a process sends a message, it includes its counter value
    with the message;

    3. On receiving a message, the counter of the recipient is updated,
    if necessary, to the greater of its current counter and the
    timestamp in the received message. The counter is then incremented
    by 1 before the message is considered received.

Nothing magic there, but a nice formal defniition.  Notice no fuzzing.

Pretty analogous to what happens in libntp/systime.c normalize_time()

Lamport basically ensures monotonically increasing time.  Nothing about
statistics or fuzzing.

> Therefore I *deduce* that the PLL correction (the one NTP does, not
> the in-kernel one Hal tells us is associated with PPS) requires a
> monotonically increasing clock.  It's the simplest explanation for the
> way libntp/systime.c works, and it explains *everything* that has
> puzzled me about that code.

Yeah.  Negative duration is pretty hard to process.  Zero duration
leads to infinities here and there.

> All x86 machines back to the Pentium (1993) have a hardware cycle
> counter; it's called the TSC. As an interesting detail, this was a
> 64-bit register even when the primary word size was 32 bits.

Well, it gets worse, in an Intel SMP chip there may be one TSC per
CPU and they are not always in sync.

As the clock_getres() man page says:

    "These registers may differ between CPUs and as a consequence these
    clocks may return bogus results if a process is migrated to another
    CPU."

Thus the need to not trust the clock and the need for normalize_time()

> > If we are serious about getting rid of that code, I'll put
> > investigating that area higher on my list.  I think we have more
> > important things to do.  
> 
> I think I can take it from here.

I'm not expecting it to be renmoved, but I feel better that it will not
mutate badly.  Might even get better comments now. The timestamp nonce
has value for all hosts and maybe other lurking benefits.  As long as
any fuzz added is less than sys_fuzz then no host I see will be
negatively impacted by it.

RGDS
GARY
---------------------------------------------------------------------------
Gary E. Miller Rellim 109 NW Wilmington Ave., Suite E, Bend, OR 97703
	gem at rellim.com  Tel:+1 541 382 8588

	    Veritas liberabit vos. -- Quid est veritas?
    "If you can’t measure it, you can’t improve it." - Lord Kelvin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 455 bytes
Desc: OpenPGP digital signature
URL: <https://lists.ntpsec.org/pipermail/devel/attachments/20170124/18a4180b/attachment.bin>