5 .\" ----------------------------------------------------------------------------
6 .\" "THE BEER-WARE LICENSE" (Revision 42):
7 .\" <phk@login.dknet.dk> wrote this file. As long as you retain this notice you
8 .\" can do whatever you want with this stuff. If we meet some day, and you think
9 .\" this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
10 .\" ----------------------------------------------------------------------------
14 Timecounters: Efficient and precise timekeeping in SMP kernels.
16 .A "Poul-Henning Kamp" "The FreeBSD Project"
18 The FreeBSD timecounters are an architecture-independent implementation
19 of a binary timescale using whatever hardware support is at hand
20 for tracking time. The binary timescale converts using simple
21 multiplication to canonical timescales based on micro- or nano-seconds
22 and can interface seamlessly to the NTP PLL/FLL facilities for clock
23 synchronisation. Timecounters are implemented using lock-less
24 stable-storage based primitives which scale efficiently in SMP
25 systems. The math and implementation behind timecounters will
26 be detailed as well as the mechanisms used for synchronisation. \**
29 This paper was presented at the EuroBSDcon 2002 conference in Amsterdam.
35 Despite digging around for it, I have not been able to positively
36 identify the first computer which knew the time of day.
37 The feature probably arrived either from the commercial side
38 so service centres could bill computer cycles to customers or from
39 the technical side so computers could timestamp external events,
40 but I have not been able to conclusively nail the first implementation down.
42 But there is no doubt that it happened very early in the development
44 and if systems like the ``SAGE'' [SAGE] did not know what time
45 it was I would be amazed.
47 On the other hand, it took a long time for a real time clock to
48 become a standard feature:
50 The ``Apple ]['' computer
51 had neither in hardware or software any notion what time it was.
53 The original ``IBM PC'' did know what time it was, provided you typed
54 it in when you booted it, but it forgot when you turned it off.
56 One of the ``advanced technologies'' in the ``IBM PC/AT'' was a battery
57 backed CMOS chip which kept track of time even when the computer
60 Today we expect our computers to know the time, and with network
61 protocols like NTP we will usually find that they do, give and
62 take some milliseconds.
64 This article is about the code in the FreeBSD kernel which keeps
67 Time and timescale basics
69 Despite the fact that time is the physical quantity (or maybe entity
70 ?) about which we know the least, it is at the same time [sic!] what we
71 can measure with the highest precision of all physical quantities.
73 The current crop of atomic clocks will neither gain nor lose a
74 second in the next couple hundred million years, provided we
75 stick to the preventative maintenance schedules. This is a feat
76 roughly in line with to knowing the circumference of the Earth
77 with one micrometer precision, in real time.
79 While it is possible to measure time by means other than oscillations,
80 for instance transport or consumption of a substance at a well-known
81 rate, such designs play no practical role in time measurement because
82 their performance is significantly inferior to oscillation based
85 In other words, it is pretty fair to say that all relevant
86 timekeeping is based on oscillating phenomena:
90 sun-dial Earths rotation about its axis.
91 calendar Ditto + Earths orbit around the sun.
92 clockwork Mechanical oscillation of pendulum.
93 crystals Mechanical resonance in quartz.
94 atomic Quantum-state transitions in atoms.
97 We can therefore with good fidelity define ``a clock'' to be the
98 combination of an oscillator and a counting mechanism:
100 .if t .PSPIC fig3.eps
102 The standard second is currently defined as
104 The duration of 9,192,631,770 periods of the radiation corresponding to the transition between the two hyperfine levels of the ground state of the caesium 133 atom.
106 and we have frequency standards which are able to mark a sequence of
108 with an error less than ø2 cdot 10 sup{-15}ø [DMK2001] with commercially
109 available products doing better than ø1 cdot 10 sup{-14}ø [AG2002].
111 Unlike other physical units with a conventionally defined origin,
112 longitude for instance, the ephemeral nature of time prevents us
113 from putting a stake in the ground, so to speak, and measure from
114 there. For measuring time we have to rely on ``dead reckoning'',
115 just like the navigators before Harrison built his clocks [RGO2002]:
116 We have to tally how far we went from our reference point, keeping a
117 running total at all times, and use that as our estimated position.
119 The upshot of this is, that we cannot define a timescale by any
120 other means than some other timescale(s).
122 ``Relative time'' is a time interval between two events, and for this
123 we only need to agree on the rate of the oscillator.
125 ``Absolute time'' consists of a well defined point in time and the
126 time interval since then, this is a bit more tricky.
128 The Internationally agreed upon TAI and the UTC timescales
129 starts at (from a physics point of view) arbitrary points in time
130 and progresses in integral intervals of the standard second, with the
131 difference being that UTC does tricks to the counting to stay roughly
132 in sync with Earths rotation \**.
134 The first atomic based definition actually operated in a different way:
135 each year would have its own value determined for the frequency of the
136 caesium resonance, selected so as to match the revolution rate of the
137 Earth. This resulted in time-intervals being very unwieldy business,
138 and more and more scientists realized that that the caesium resonance
139 was many times more stable than the angular momentum of the Earth.
140 Eventually the new leap-second method were introduced in 1972.
141 It is interesting to note that the autumn leaves falling on the
142 northern hemisphere affects the angular momentum enough to change
143 the Earths rotational rate measurably.
146 TAI is defined as a sequence of standard seconds (the first timescale),
147 counted from January 1st 1958 (the second timescale).
149 UTC is defined basically the same way, but every so often a leap-second
150 is inserted (or theoretically deleted) to keep UTC synchronised
151 with Earths rotation.
153 Both the implementation of these two, and a few others speciality
154 timescales are the result of the
155 combined efforts of several hundred atomic frequency standards in
156 various laboratories and institutions throughout the world, all
157 reporting to the BIPM in Paris who calculate the ``paper clock'' which
158 TAI and UTC really are using a carefully designed weighting algorithm \**.
160 The majority of these clocks are model 5071A from Agilent (the test
161 and measurement company formerly known as ``Hewlett-Packard'') which
162 count for as much as 85% of the combined weight.
163 A fact the company deservedly is proud of.
164 The majority of the remaining weight is assigned to a handful of big
165 custom-design units like the PTB2 and NIST7.
168 Leap seconds are typically announced six to nine months in advance,
169 based on precise observations of median transit times of stars and VLBI
170 radio astronomy of very distant quasars.
172 The perceived wisdom of leap-seconds have been gradually decreasing
173 in recent years, as devices and products with built-in calendar
174 functionality becomes more and more common and people realize that
175 user input or software upgrades are necessary to instruct the
176 calendar functionality about upcoming leap seconds.
180 UNIX systems use a timescale which pretends to be UTC, but defined
181 as the count of standard seconds since 00:00:00 01-01-1970 UTC,
182 ignoring the leap-seconds. This definition has never been perceived
185 Ignoring leap seconds means that unless some trickery is performed
186 when a leap second happens on the UTC scale, UNIX clocks would be
187 one second off. Another implication is that the length of a
188 time interval calculated on UNIX time_t variables, can be up to 22
189 (and counting) seconds wrong relative to the same time interval
190 measured on the UTC timescale.
192 Recent efforts have tried to make the NTP protocol make up for this
193 deficiency by transmitting the UTC-TAI offset as part of the protocol.
196 Fractional seconds are represented two ways in UNIX, ``timeval'' and
197 ``timespec''. Both of these formats are two-component structures
198 which record the number of seconds, and the number of microseconds
199 or nanoseconds respectively.
201 This unfortunate definition makes arithmetic on these two formats
202 quite expensive to perform in terms of computer instructions:
205 /* Subtract timeval from timespec */
206 t3.tv_sec = t1.tv_sec - t2.tv_sec;
207 t3.tv_nsec = t1.tv_nsec -
209 if (t3.tv_nsec >= 1000000000) {
211 t3.tv_nsec -= 1000000000;
212 } else if (t3.tv_nsec < 0) {
214 t3.tv_nsec += 1000000000;
219 While nanoseconds will probably be enough for most timestamping
220 tasks faced by UNIX computers for a number of years, it is an
221 increasingly uncomfortable situation that CPU clock periods and
222 instruction timings are already not representable in the standard
223 time formats available on UNIX for consumer grade hardware,
224 and the first POSIX mandated API, \fCclock_getres(3)\fP has
225 already effectively reached end of life as a result of this.
227 Hopefully the various standards bodies will address this issue
228 better in the future.
230 Precision, Stability and Resolution
232 Three very important terms in timekeeping are ``precision'',
233 ``stability'' and ``resolution''.
234 While the three words may seem to describe somewhat the
235 same property in most uses, their use in timekeeping covers three
236 very distinct and well defined properties of a clock.
238 Resolution in clocks is simply a matter of the step-size of the
239 counter or in other words: the rate at which it steps.
240 A counter running on a 1 MHz frequency will have a resolution
243 Precision talks about how close to the intended rate the clock runs,
244 stability about how much the rate varies and resolution about the
245 size of the smallest timeinterval we can measure.
247 From a quality point of view, Stability is a much more
248 valuable property than precision, this is probably best explained
249 using a graphic illustration of the difference between the two
252 .if t .PSPIC fig1.eps
254 In the top row we have instability, the bullet holes are spread over
255 a large fraction of the target area.
256 In the bottom row, the bullets all hit in a very small area.
258 On the left side, we have lack of precision, the holes obviously are
259 not centred on the target, a systematic offset exists.
260 In the right side we have precision, the bullets are centred on
263 We cannot easily get resolution into this analogy, the obvious
264 representation as the diameter of the bullet-hole is not correct,
265 it would have to be the grid or other pattern of locations where
266 the bullet could possibly penetrate the target material, but this
267 gets too quantum-mechanical-oid to serve the instructional purpose.
270 Transposing these four targets to actual clocks, the situation
271 could look like the following plots:
273 .if t .PSPIC fig2.eps
275 On the x-axis we have time and on the y-axis how wrong the clock
276 was at a given point in time.
278 The reason atomic standards are such a big deal in timekeeping is
279 that they are incredibly stable: they are able to generate an oscillation
280 where the period varies by roughly a millionth of a billonth of a
281 second in long term measurements.
283 They are in fact not nearly as precise as they are stable, but as
284 one can see from the graphic above, a stable clock which is not
285 precise can be easily corrected for the offset and thus calibrated
286 is as good as any clock.
288 This lack of precision is not necessarily a flaw in these kinds of
289 devices, once you get into the ø10 cdot 10 sup{-15}ø territory
290 things like the blackbody spectrum at the particular absolute
291 temperature of the clocks hardware and general relativistic
292 effects mostly dependent on the altitude above earths center
293 has to be corrected for \**.
295 This particularly becomes an issue with space-based atomic standards
296 as those found on the ``Navstar'' GPS satellites.
299 Design goals of timecounters
301 After this brief description of the major features of the local
302 landscape, we can look at the design goals of timecounters in detail:
304 .I "Provide timestamps in timeval and timespec formats,"
306 This is obviously the basic task we have to solve, but as was noted
307 earlier, this is in no way the performance requirement.
309 .I "on both the ``uptime'' and the POSIX timescales,"
311 The ``uptime'' timescale is convenient for time intervals which are
312 not anchored in UTC time: the run time of processes, the access
313 time of disks and similar.
315 The uptime timescale counts seconds starting from when the system
316 is booted. The POSIX/UTC timescale is implemented by adding an
317 estimate of the POSIX time when the system booted to the uptime
320 .I "using whatever hardware we have available at the time,"
322 Which in a subtle way also implies ``be able to switch from one
323 piece of hardware to another on the fly'' since we may not know
324 right up front what hardware we have access to and which is
327 .I "while supporting time the NTP PLL/FLL discipline code,"
329 The NTP kernel PLL/FLL code allows the local clock and timescale
330 to be synchronised or syntonised to an external timescale either
331 via network packets or hardware connection. This also implies
332 that the rate and phase of the timescale must be manoeuvrable
333 with sufficient resolution.
335 .I "and providing support for the RFC 2783 PPS API,"
337 This is mainly for the benefit of the NTPD daemons communication
338 with external clock or frequency hardware, but it has many other
339 interesting uses as well [PHK2001].
341 .I "in a SMP efficient way."
343 Timestamps are used many places in the kernel and often at pretty
344 high rate so it is important that the timekeeping facility
345 does not become a point of CPU or lock contention.
347 Timecounter timestamp format.
349 Choosing the fundamental timestamp format for the timecounters is
350 mostly a question of the resolution and steer-ability requirements.
352 There are two basic options on contemporary hardware: use a 32 bit
353 integer for the fractional part of seconds, or use a 64 bit which
354 is computationally more expensive.
356 The question therefore reduced to the somewhat simpler: can we get
357 away with using only 32 bit ?
359 Since 32 bits fractional seconds have a resolution of slightly
360 better than quarter of a nanosecond (.2328 nsec) it can obviously
361 be converted to nanosecond resolution struct timespec timestamps
362 with no loss of precision, but unfortunately not with pure 32 bit
363 arithmetic as that would result in unacceptable rounding errors.
365 But timecounters also need to represent the clock period of the
366 chosen hardware and this hardware might be the GHz range CPU-clock.
367 The list of clock frequencies we could support with 32 bits are:
371 ø2 sup{32} / 1ø ø=ø 4.294 GHz
372 ø2 sup{32} / 2ø ø=ø 2.147 GHz
373 ø2 sup{32} / 3ø ø=ø 1.432 GHz
375 ø2 sup{32} / (2 sup{32}-1)ø ø=ø 1.000 Hz
377 We can immediately see that 32 bit is insufficient to faithfully
378 represent clock frequencies even in the low GHz area, much less in
379 the range of frequencies which have already been vapourwared by
380 both IBM, Intel and AMD.
381 QED: 32 bit fractions are not enough.
383 With 64 bit fractions the same table looks like:
387 ø2 sup{64} / 1ø ø=ø ø 18.45 cdot 10 sup{9}ø GHz
388 ø2 sup{64} / 2ø ø=ø ø 9.223 cdot 10 sup{9}ø GHz
390 ø2 sup{64} / 2 sup{32}ø ø=ø 4.294 GHz
392 ø2 sup{64} / (2 sup{64}-1)ø ø=ø 1.000 Hz
394 And the resolution in the 4 GHz frequency range is approximately one Hz.
396 The following format have therefore been chosen as the basic format
397 for timecounters operations:
406 Notice that the format will adapt to any size of time_t variable,
407 keeping timecounters safely out of the ``We SHALL prepare for the
408 Y2.038K problem'' war zone.
410 One beauty of the bintime format, compared to the timeval and
411 timespec formats is that it is a binary number, not a pseudo-decimal
412 number. If compilers and standards allowed, the representation
413 would have been ``int128_t'' or at least ``int96_t'', but since this
414 is currently not possible, we have to express the simple concept
415 of multiword addition in the C language which has no concept of a
418 To add two bintime values, the code therefore looks like this \**:
420 If the reader suspects the '>' is a typo, further study is suggested.
428 bt3->frac = bt1->frac + bt2->frac;
429 bt3->sec = bt1->sec + bt2->sec;
435 An important property of the bintime format is that it can be
436 converted to and from timeval and timespec formats with simple
437 multiplication and shift operations as shown in these two
438 actual code fragments:
442 bintime2timespec(struct bintime *bt,
446 ts->tv_sec = bt->sec;
448 ((uint64_t)1000000000 *
449 (uint32_t)(bt->frac >> 32)) >> 32;
456 timespec2bintime(struct timespec *ts,
460 bt->sec = ts->tv_sec;
462 int(2^64 / 1000000000) */
463 bt->frac = ts->tv_nsec *
464 (uint64_t)18446744073LL;
470 How timecounters work
472 To produce a current timestamp the timecounter code
473 reads the hardware counter, subtracts a reference
474 count to find the number of steps the counter has
475 progressed since the reference timestamp.
476 This number of steps is multiplied with a factor
477 derived from the counters frequency, taking into account
478 any corrections from the NTP PLL/FLL and this product
479 is added to the reference timestamp to get a timestamp.
481 This timestamp is on the ``uptime'' time scale, so if
482 UNIX/UTC time is requested, the estimated time of boot is
483 added to the timestamp and finally it is scaled to the
484 timeval or timespec if that is the desired format.
486 A fairly large number of functions are provided to produce
487 timestamps, depending on the desired timescale and output
492 Desired uptime UTC/POSIX
493 Format timescale timescale
495 bintime binuptime() bintime()
496 timespec nanouptime() nanotime()
497 timeval microuptime() microtime()
500 Some applications need to timestamp events, but are not
501 particular picky about the precision.
502 In many cases a precision of tenths or hundreds of
503 seconds is sufficient.
505 A very typical case is UNIX file timestamps:
506 There is little point in spending computational resources getting an
507 exact nanosecond timestamp, when the data is written to
508 a mechanical device which has several milliseconds of unpredictable
509 delay before the operation is completed.
511 Therefore a complementary shadow family of timestamping functions
512 with the prefix ``get'' have been added.
514 These functions return the reference
515 timestamp from the current timehands structure without going to the
516 hardware to determine how much time has elapsed since then.
517 These timestamps are known to be correct to within rate at which
518 the periodic update runs, which in practice means 1 to 10 milliseconds.
522 The delta-count operation is straightforward subtraction, but we
523 need to logically AND the result with a bit-mask with the same number
524 (or less) bits as the counter implements,
525 to prevent higher order bits from getting set when the counter rolls over:
529 Delta Count = (Count sub{now} - Count sub{ref}) ~ BITAND ~ mask
532 The scaling step is straightforward.
536 T sub{now} = Delta Count cdot R sub{counter} + T sub{ref}
539 The scaling factor øR sub{counter}ø will be described below.
541 At regular intervals, scheduled by \fChardclock()\fP, a housekeeping
542 routine is run which does the following:
544 A timestamp with associated hardware counter reading is elevated
545 to be the new reference timecount:
550 Delta Count = (Count sub{now} - Count sub{ref}) ~ BITAND ~ mask
555 T sub{now} = Delta Count cdot R sub{counter}
560 Count sub{ref} = Count sub{now}
565 T sub{ref} = T sub{now}
569 If a new second has started, the NTP processing routines are called
570 and the correction they return and the counters frequency is used
571 to calculate the new scaling factor øR sub{counter}ø:
575 R sub{counter} = {2 sup{64} over Freq sub{counter}} cdot ( 1 + R sub{NTP} )
578 Since we only have access to 64 bit arithmetic, dividing something
579 into ø2 sup{64}ø is a problem, so in the name of code clarity
580 and efficiency, we sacrifice the low order bit and instead calculate:
584 R sub{counter} = 2 cdot {2 sup{63} over Freq sub{counter}} cdot ( 1 + R sub{NTP} )
587 The øR sub{NTP}ø correct factor arrives as the signed number of
588 nanoseconds (with 32 bit binary fractions) to adjust per second.
589 This quasi-decimal number is a bit of a square peg in our round binary
590 hole, and a conversion factor is needed.
591 Ideally we want to multiply this factor by:
595 2 sup {64} over {10 sup{9} cdot 2 sup{32}} = 4.294967296
598 This is not a nice number to work with.
599 Fortunately, the precision of this correction is not critical, we are
600 within an factor of a million of the ø10 sup{-15}ø performance level
601 of state of the art atomic clocks, so we can use an approximation
602 on this term without anybody noticing.
604 Deciding which fraction to use as approximation needs to carefully
605 consider any possible overflows that could happen.
606 In this case the correction may be as large as \(+- 5000 PPM which
607 leaves us room to multiply with about 850 in a multiply-before-divide
609 Unfortunately, there are no good fractions which multiply with less
610 than 850 and at the same time divide by a power of two, which is
611 desirable since it can be implemented as a binary shift instead of
612 an expensive full division.
614 A divide-before-multiply approximation necessarily results in a loss
615 of lower order bits, but in this case dividing by 512 and multiplying
616 by 2199 gives a good approximation where the lower order bit loss is
620 2199 over 512 = 4.294921875
623 The resulting error is an systematic under compensation of 10.6PPM
624 of the requested change, or ø1.06 cdot 10 sup -14ø per nanosecond
626 This is perfectly acceptable.
628 Putting it all together, including the one bit we put on the alter for the
629 Goddess of code clarity, the formula looks like this:
633 R sub{counter} = 2 cdot {{2 sup{63} + 2199 cdot {R sub{NTP}} over 1024} over Freq sub{counter}}
636 Presented here in slightly unorthodox format to show the component arithmetic
637 operations as they are carried out in the code.
639 Frequency of the periodic update
641 The hardware counter should have a long enough
642 period, ie, number of distinct counter values divided by
643 frequency, to not roll over before our periodic update function
644 has had a chance to update the reference timestamp data.
646 The periodic update function is called from \fChardclock()\fP which
647 runs at a rate which is controlled by the kernel parameter
650 By default HZ is 100 which means that only hardware with a period
651 longer than 10 msec is usable.
652 If HZ is configured higher than 1000, an internal divider is
653 activated to keep the timecounter periodic update running
654 no more often than 2000 times per second.
656 Let us take an example:
657 At HZ=100 a 16 bit counter can run no faster than:
661 2 sup{16} cdot {100 Hz} = 6.5536 MHz
664 Similarly, if the counter runs at 10MHz, the minimum HZ is
668 {10 MHz} over {2 sup{16}} = 152.6 Hz
672 Some amount of margin is of course always advisable,
673 and a factor two is considered prudent.
678 Provided our hardware can be read atomically, that our arithmetic
679 has enough bits to not roll over and that our clock frequency is
680 perfectly, or at least sufficiently, stable, we could avoid the
681 periodic update function, and consequently disregard the entire
683 We are seldom that lucky in practice.
685 The straightforward way of dealing with meta data updates is to
686 put a lock of some kind on the data and grab hold of that before
688 This would however be a very heavy-handed approach. First of
689 all, the updates are infrequent compared to simple references,
690 second it is not important which particular state of meta data
691 a consumer gets hold of, as long as it is consistent: as long
692 as the øCount sub{ref}ø and øT sub{ref}ø are a matching pair,
693 and not old enough to cause an ambiguity with hardware counter
694 rollover, a valid timestamp can be derived from them.
696 A pseudo-stable-storage with generation count method has been
698 A ring of ten ``timehands'' data structures are used to hold the
699 state of the timecounter system, the periodic update function
700 updates the next structure with the new reference data and
701 scaling factor and makes it the current timehands.
703 The beauty of this arrangement lies in the fact that even though
704 a particular ``timehands'' data structure has been bumped from being
705 the ``currents state'' by its successor, it still contains valid data
706 for some amount of time into the future.
708 Therefore, a process which has started the timestamping process but
709 suffered an interrupt which resulted in the above periodic processing
710 can continue unaware of this afterwards and not suffer corruption
711 or miscalculation even though it holds no locks on the shared
713 .if t .PSPIC fig4.eps
715 This scheme has an inherent risk that a process may be de-scheduled for
716 so long time that it will not manage to complete the timestamping
717 process before the entire ring of timehands have been recycled.
718 This case is covered by each timehand having a private generation number
719 which is temporarily set to zero during the periodic processing, to
720 mark inconsistent data, and incremented to one more than the
721 previous value when the update has finished and the timehands
724 The timestamping code will grab a copy of this generation number and
725 compare this copy to the generation in the timehands after completion
726 and if they differ it will restart the timestamping calculation.
731 gen = th->th_generation;
732 /* calculate timestamp */
734 gen != th->th_generation);
738 Each hardware device supporting timecounting is represented by a
739 small data structure called a timecounter, which documents the
740 frequency, the number of bits implemented by the counter and a method
741 function to read the counter.
743 Part of the state in the timehands structure is a pointer to the
744 relevant timecounter structure, this makes it possible to change
745 to a one piece of hardware to another ``on the fly'' by updating
746 the current timehands pointer in a manner similar to the periodic
749 In practice this can be done with sysctl(8):
752 sysctl kern.timecounter.hardware=TSC
756 at any time while the system is running.
760 A closer look on ``suitable hardware'' is warranted
762 It is obvious from the above description that the ideal hardware
763 for timecounting is a wide binary counter running at a constant
765 and atomically readable by all CPUs in the system with a fast
766 instruction(-sequence).
768 When looking at the hardware support on the PC platform, one
769 is somewhat tempted to sigh deeply and mutter ``so much for theory'',
770 because none of the above parameters seems to have been on the
771 drawing board together yet.
773 All IBM PC derivatives contain a device more or less compatible
774 with the venerable Intel i8254 chip.
775 This device contains 3 counters of 16 bits each,
776 one of which is wired so it can interrupt the CPU when the
777 programmable terminal count is reached.
779 The problem with this device is that it only has 8bit bus-width,
780 so reading a 16 bit timestamp takes 3 I/O operations: one to latch
781 the count in an internal register, and two to read the high and
782 low parts of that register respectively.
784 Obviously, on multi-CPU systems this cannot be done without some
785 kind of locking mechanism preventing the other CPUs from trying
786 to do the same thing at the same time.
788 Less obviously we find it is even worse than that:
789 Since a low priority kernel thread
790 might be reading a timestamp when an interrupt comes in, and since
791 the interrupt thread might also attempt to generate a timestamp,
792 we need to totally block interrupts out while doing those three
795 And just to make life even more complicated, FreeBSD uses the same
796 counter to provide the periodic interrupts which schedule the
797 \fChardclock()\fP routine, so in addition the code has to deal with the
798 fact that the counter does not count down from a power of two and
799 that an interrupt is generated right after the reloading of the
800 counter when it reaches zero.
802 Ohh, and did I mention that the interrupt rate for hardclock() will
803 be set to a higher frequency if profiling is active ? \**
805 I will not even mention the fact that it can be set also to ridiculous
806 high frequencies in order to be able to use the binary driven ``beep''
807 speaker in the PC in a PCM fashion to output ``real sounds''.
810 It hopefully doesn't ever get more complicated than that, but it
811 shows, in its own bizarre and twisted way, just how little help the
812 timecounter code needs from the actual hardware.
814 The next kind of hardware support to materialise was the ``CPU clock
815 counter'' called ``TSC'' in official data-sheets.
816 This is basically a on-CPU counter, which counts at the rate
819 Unfortunately, the electrical power needed to run a CPU is pretty
820 precisely proportional with the clock frequency for the
821 prevailing CMOS chip technology, so
822 the advent of computers powered by batteries prompted technologies
823 like APM, ACPI, SpeedStep and others which varies or throttles the
824 CPU clock to match computing demand in order to minimise the power
827 This technology also found ways into stationary computers from
828 two different vectors.
829 The first vector was technical: Cheaper cooling solutions can be used
830 for the CPU if they are employed resulting in cheaper commodity
832 The second vector was political: For reasons beyond reason, energy
833 conservation became an issue with personal computers, despite the fact
834 that practically all north American households contains 4 to 5 household
835 items which through inefficient designs waste more power than a
836 personal computer use.
839 Another wiggle for the TSC is that it is not usable on multi-CPU
840 systems because the counter is implemented inside the CPU and
841 not readable from other CPUs in the system.
843 The counters on different CPUs are not guaranteed
844 to run syntonously (ie: show the same count at the same time).
845 For some architectures like the DEC/alpha architecture they do not even
846 run synchronously (ie: at the same rate) because the CPU clock frequency
847 is generated by a small SAW device on the chip which is very sensitive
848 to temperature changes.
850 The ACPI specification finally brings some light:
851 it postulates the existence of a 24 or 32 bit
852 counter running at a standardised constant frequency and
853 specifically notes that this is intended to be used for timekeeping.
855 The frequency chosen, 3.5795454... MHz\**
857 The reason for this odd-ball frequency has to be sought in the ghastly
858 colours offered by the original IBM PC Color Graphics Adapter: It
859 delivered NTSC format output and therefore introduced the NTSC colour
860 sync frequency into personal computers.
862 is not quite as high as one
863 could have wished for, but it is certainly a big improvement over
864 the i8254 hardware in terms of access path.
866 But trust it to Murphys Law: The majority of implementations so far
867 have failed to provide latching suitable to avoid meta-stability
868 problems, and several readings from the counter is necessary to
869 get a reliable timestamp.
870 In difference from the i8254 mentioned above, we do not need to
871 any locking while doing so, since each individual read is atomic.
873 An initialization routine tries to test if the ACPI counter is properly
874 latched by examining the width of a histogram over read delta-values.
876 Other architectures are similarly equipped with means for timekeeping,
877 but generally more carefully thought out compared to the haphazard
878 developments of the IBM PC architecture.
880 One final important wiggle of all this, is that it may not be possible
881 to determine which piece of hardware is best suited for clock
882 use until well into or even after the bootstrap process.
884 One example of this is the Loran-C receiver designed by Prof. Dave Mills
886 which is unsuitable as timecounter until the daemon program which
887 implements the software-half of the receiver has properly initialised
888 and locked onto a Loran-C signal.
890 Ideal timecounter hardware
892 As proof of concept, a sort of an existentialist protest against
893 the sorry state describe above, the author undertook a project to
894 prove that it is possible to do better than that, since none of
895 the standard hardware offered a way to fully validate the timecounter
898 Using a COTS product, ``HOT1'', from Virtual Computers Corporation
899 [VCC2002] containing a FPGA chip on a PCI form factor card, a 26
900 bit timecounter running at 100MHz was successfully implemented.
902 .if t .PSPIC fig5.eps
905 In order to show that timestamping does not necessarily have to
906 be done using unpredictable and uncalibratable interrupts, an
907 array of latches were implemented as well, which allow up to 10
908 external signals to latch the reading of the counter when
909 an external PPS signal transitions from logic high to logic
912 Using this setup, a standard 133 MHz Pentium based PC is able to
913 timestamp the PPS output of the Motorola UT+ GPS receiver with
914 a precision of \(+- 10 nanoseconds \(+- one count which in practice
915 averages out to roughly \(+- 15 nanoseconds\**:
917 The reason the plot does not show a very distinct 10 nanosecond
918 quantization is that the GPS receiver produces the PPS signal from
919 a clock with a roughly 55 nanosecond period and then predicts in
920 the serial data stream how many nanoseconds this will be offset
922 This plot shows the timestamps corrected for this ``negative
923 sawtooth correction''.
928 It shold be noted that the author is no hardware wizard and
929 a number of issues in the implementation results in less than
930 ideal noise performance.
932 Now compare this to ``ideal'' timecounter to the normal setup
933 where the PPS signal is used
934 to trigger an interrupt via the DCD pin on a serial port, and
935 the interrupt handler calls \fCnanotime()\fP to timestamp
936 the external event \**:
938 In both cases, the computers clock frequency controlled
939 with a Rubidium Frequency standard.
940 The average quality of crystals used for computers would
941 totally obscure the curves due to their temperature coefficient.
946 It is painfully obvious that the interrupt latency is the
947 dominant noise factor in PPS timestamping in the second case.
948 The asymetric distribution of the noise in the second plot
949 also more or less entirely invalidates the design assumption
950 in the NTP PLL/FLL kernel code that timestamps are dominated
951 by gaussian noise with few spikes.
953 Status and availability
955 The timecounter code has been developed and used in FreeBSD
956 for a number of years and has now reached maturity.
957 The source-code is located almost entirely in the kernel source file
958 kern_tc.c, with a few necessary adaptations in code which
959 interfaces to it, primarily the NTP PLL/FLL code.
961 The code runs on all FreeBSD platforms including i386, alpha,
962 PC98, sparc64, ia64 and s/390 and contains no wordsize or
963 endianess issues not specifically handled in the sourcecode.
965 The timecounter implementation is distributed under the ``BSD''
966 open source license or the even more free ``Beer-ware'' license.
968 While the ability to accurately model and compensate for
969 inaccuracies typical of atomic frequency standards are not
970 catering to the larger userbase, but this ability and precision
971 of the code guarntees solid support for the widespread deployment
972 of NTP as a time synchronization protocol, without rounding
973 or accumulative errors.
975 Adding support for new hardware and platforms have been
976 done several times by other developers without any input from the
977 author, so this particular aspect of timecounters design
978 seems to work very well.
982 At this point in time, no specific plans exist for further
983 development of the timecounters code.
985 Various micro-optimizations, mostly to compensate for inadequate
986 compiler optimization could be contemplated, but the author
987 resists these on the basis that they significantly decrease
988 the readability of the source code.
995 The author would like to thank:
998 for his invaluable assistance
999 in taming the evil i8254 timecounter, as well as the enthusiastic
1000 resistance he has provided throughout.
1002 Professor Dave Mills of University of Delaware for his work on
1003 NTP, for lending out the neglected twin Loran-C receiver and for
1004 picking up the glove when timecounters made it clear
1005 that the old ``microkernel'' NTP timekeeping code were not up to snuff
1008 Tom Van Baak for helping out, despite the best efforts of the National
1009 Danish Posts center for Customs and Dues to prevent it.
1011 Corby Dawson for helping with the care and feeding for caesium standards.
1013 The staff at the NELS Loran-C control station in Bø, Norway for providing
1014 information about step-changes.
1016 The staff at NELS Loran-C station Eiðe, Faeroe
1017 Islands for permission to tour their installation.
1019 The FreeBSD users for putting up with ``micro uptime went backwards''.
1024 Published specifications for Agilent model 5071A Primary Frequency
1027 http://www.agilent.com
1030 "Accuracy Evaluation of a Cesium Fountain Primary Frequency Standard at NIST."
1031 D. M. Meekhof, S. R. Jefferts, M. Stephanovic, and T. E. Parker
1032 IEEE Transactions on instrumentation and measurement, VOL. 50, NO. 2,
1036 "Monitoring Natural Gas Usage"
1038 http://phk.freebsd.dk/Gasdims/
1041 "A computer-controlled LORAN-C receiver for precision timekeeping."
1043 Electrical Engineering Department Report 92-3-1, University of Delaware, March 1992, 63 pp.
1046 Levine, J., and D. Mills. "Using the Network Time Protocol to transmit International Atomic Time (TAI)". Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Reston VA, November 2000), 431-439.
1050 Mills, D.L., and P.-H. Kamp.
1051 Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Reston VA, November 2000), 423-430.
1054 For an introduction to Harrison and his clocks, see for
1057 http://www.rog.nmm.ac.uk/museum/harrison/
1060 a more detailed and possibly better researched account: Dava
1061 Sobels excellent book, "Longitude: The True Story of a Lone
1062 Genius Who Solved the Greatest Scientific Problem of His
1063 Time" Penguin USA (Paper); ISBN: 0140258795.
1066 This ``gee-wiz'' kind of article in Dr. Dobbs Journal is a good place to
1069 http://www.ddj.com/documents/s=1493/ddj0001hc/0085a.htm
1072 Please consult Virtual Computer Corporations homepage:
projects / FreeBSD / FreeBSD.git / blob