[ntp:questions] how do I lock in average frequency correction

Terje Mathisen "terje.mathisen at tmsw.no" at ntp.org
Thu Feb 16 06:53:03 UTC 2012

Dennis Ferguson wrote:
> I have had very good results with the following procedure.  If `tc'
> is the 64 bit output of a counter which is continuously incremented
> at the rate of some oscillator then the time can be computed as follows:
>      t = r * (tc<<  s) + c

This is a reasonable way to get a nice clock...
> The value of `s' is selected so that a second's worth of advance of
> tc causes a change to bit 32 of (tc<<  s); that is, `s' is a constant
> pre-computed from the nominal frequency of tc's counter and an assumption
> about how far from the actual frequency of the oscillator that might

The main/only problem with this assumption is that it breaks as soon as 
your tick counter (like the one you get from RDTSC) runs at more than 
4.2 GHz! (Maybe you intended to say that the shift was such that the top 
bit of a 64-bit value would be set?)

It also breaks if/when the tick counter rolls over, doesn't it?

With a full 64-bit counter that happens slightly less often than the 
NTPD clock rolls over, as long as the increment rate is less than 2^32 
ticks/second, but if you are limited to (say) 40 bits, which is the 
resolution of most of the non-TSC counters in an x86 cpu, you do need a 
dependable way to handle rollovers.

Finally, all of this does of course require either a single, very 
stable) frequency for said counter, or some driver support that will 
know about any changes and modify the r and c values at the same time as 
the frequency changes.

> be.  The multiply (r * (tc<<  s)), where `r' is a 64 bit value, returns
> the high order 64 bits of the 128 bit product.  In my case, `t' (and
> hence 'c') was picked to be the time of day computed in the NTP fixed
> point format, i.e. a 32 bit integer seconds part and a 32 bit fractional
> part, so given a tc from the counter the above converts it directly to
> a time of day.  The computation itself takes nanoseconds, or less, on
> a modern processor.

It does take nanoseconds even on the very fastest (IBM Power7/8?) 
available cpus: The 64x64->128 multiplication requires about 7 clock 
cycles, while the shift and add will each require at least one cycle.

Add the time to read the current tick counter (which cannot be less than 
a single cycle, but much more likely to stay in the 10-30 range since 
this isn't a resource you would locate in the critical path of the cpu 
pipeline) and you get anywhere from 2 to 10 ns:

Still pretty fast. :-)

I really don't like the fact that you seem to disregard the need for 
extended time range handling, i.e. even if you produce NTP timestamps, 
they should have a full 64-bit seconds counter so that the full counter 
will never roll over.
> Clearly the adjustment interface operates to produce values of `r' and
> `c' that minimize the error in the result.  Phase adjustments are implemented
> by adding an offset to 'c', and hence have a precision of 233 picoseconds.
> Rate (i.e. frequency) adjustments are implemented by modifying the value
> of 'r', with a corresponding change to 'c' to ensure phase continuity at
> the time of the change, and have a precision of better than 10^-19.  Slews,
> a la adjtime(), can be implemented by making a rate change for a fixed
> interval, at the end of which `r' is returned to its previous value with
> 'c' precisely offset.  The only time `r' and `c' change is when the time
> synchronization software makes a system call to adjust the clock; there
> is no need to do anything in an interrupt service routine (the latter

Except for any interrupt which causes frequency throttling.

> assumes that the system call interface is not ntp_adjtime() or adjtimex();
> while that code can be supported as well there are good arguments for
> why you can expect better results, even from ntpd, if you don't include
> that code in the kernel, though that's a different topic).  If your TSC
> counter is reliable then making the sets of (s, r, c) constants available
> to user space on a shared page allows user space processes to obtain
> accurate time without system calls.  There are no "inconvenient" clock
> rates and the clock precision and jitter is the same as the precision
> and jitter of the underlying hardware counter.
> If you want a "tickless" kernel the best way to do that might be to
> start with a "tickless" system clock.  If you have a continuously
> incrementing counter there is nothing that an interrupt service
> routine needs to do.

I do like your approach. :-)


- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

More information about the questions mailing list