[ntp:hackers] Non-monotonic time on NT

Terje Mathisen terje.mathisen at hda.hydro.com
Tue May 15 05:50:20 PDT 2007


peda at axentia.se wrote:
> Terje Mathisen wrote:
>> peda at axentia.se wrote:
>>> Terje Mathisen wrote:
>>> From what I observed way back when, the RT thread got to run
>>> several times during each timer tick. I can only assume that
>>> the sawtooth I saw was due to the RT thread going to sleep
>>> (for the last time before the tick) closer and closer to the
>>> tick - never sleeping less than 1 ms - and hence waking up
>>> longer and longer after the tick. Until it was 1 ms "late"
>>> and the whole thing wrapped. One can easily imagine drift in
>>> the other direction as well, of course.
>> I've written code now, it does look like the scheduler runs off 
>> something like a 1024 Hz CMOS clock interrupt, and not the OS clock 
>> itself, which does make things a lot more interesting. :-(
> 
> Great! Someone else has finally "gotten it" :-)

<BG>
> 
> Your implementation seems good, along the lines of fixing the
> problem as early as possible, which will reduce the filtering
> needs.

I'm a lot closer to drop-in working code now:

I have a separate (non-realtime) thread that samples the OS clock every 
ms, with a Sleep(1) between iterations.

When the OS clock has just wrapped around into the next second, I go 
into a special mode: I set a counter equal to 
Floor(milliseconds_per_os_tick), and decrement this every iteration.

When the counter drops down to <= 0, I get aggressive, using Sleep(0) 
between iterations, until the OS clock is updated. On average this 
occurs for about one ms every second, so the overhead is quite low.

Ideally I should Sleep(9) or Sleep(15) just after each OS clock update, 
but this way I get ms accuracy even if the thread missed a little.

So what kind of performance do I get:

The main thread checks the results 10 times/second, and prints out the 
following variables each time "ftime_base" has been updated, i.e. when a 
starting point for extrapolation has been determined:

Date/time of base timestamp, # of TSC cycles since the last read of the 
OS clock (i.e. maximum error in timestamp determination) and the last 
variable is the slope of delta_ftime/delta_tsc, i.e. the amount the TSC 
delta must be multiplied by to convert it into a ftime offset.

C:\DATA>c:\c2\time-res\time-res\debug\time-res.exe
2007-05-15 12:14:24.084710   2280 0.005012472
2007-05-15 12:14:24.678472   1452 0.005012474
2007-05-15 12:14:24.881601   1392 0.005012473
2007-05-15 12:14:25.006603   1248 0.005012469
2007-05-15 12:14:25.037854   1224 0.005012456
2007-05-15 12:14:25.100355   2244 0.005012446
2007-05-15 12:14:25.990997   2256 0.005012460
2007-05-15 12:14:26.506632   2268 0.005012465

Notice that with just 16 samples in the filter (which initially means 16 
timer ticks, the slope value is quite accurate!

Initially I fill the filter on every timer tick, then I back off 
exponentially over the first 1000 samples, at which point I try to 
collect one new sample every second.

A short time (half a minute) later it looks like this:

2007-05-15 12:14:55.366567   2280 0.005012462
2007-05-15 12:14:55.710324   2232 0.005012462
2007-05-15 12:14:59.772902   1200 0.005012464
2007-05-15 12:15:00.038534   1224 0.005012465
2007-05-15 12:15:00.757302   2232 0.005012470
2007-05-15 12:15:01.397940   2244 0.005012480
2007-05-15 12:15:04.804255   1428 0.005012469
2007-05-15 12:15:05.038634   1212 0.005012469

The filtering itself is dead simple:

Each time I get a new valid sample (gated by having 'tsc_delta' less 
than 'sample_limit', and 'sample_limit' increased each time a sample is 
discarded), I redo the filtering:

Grab the best 4 entries, measured by tsc_delta, then take the slope 
between the first and last of these four. Worst case this gives a 
baseline of 3 seconds, on average about 12 seconds.

Set the ftime_base to the last of these good samples, and tsc_slope to 
the slope calculated above.

Notice that even with a short & simple filter like this, the selected 
base sample has a stable collection time of around 1 us (2000 cpu clock 
ticks, and the calculated slope has short-term (between ftime base 
samples) stability in the PPM range.

The result should be extrapolated timestamps that are accurate to better 
than 10 us nearly all the time, and usually in the 1-3 us range.

Independent of all this, the ntp_gettime() call will still grab the OS 
clock counter and verify that the extrapolated time is contained 
somewhere in the current clock tick, otherwise it simply falls back on 
the OS time.

So what happens if the core frequency changes?

Since the 'tsc_slope' value will be wrong, the first few seconds some 
timestamps will be gated by the sanity checks outlined above, but after 
16 new samples has been gathered everything will be back to normal, with 
worst-case a few timestamps with an error of a few ms.

This cannot take last for very long, due to the exponential backoff and 
the fact that after a successful sample, the limit is set to 8 times the 
last selected time.

Peter, I'll send you the test code in a separate mail!

Terje

-- 
- <Terje.Mathisen at hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"


More information about the hackers mailing list