1116411Sphk.EQ 2116411Sphkdelim �� 3116411Sphk.EN 4116411Sphk.\" 5116411Sphk.\" ---------------------------------------------------------------------------- 6116411Sphk.\" "THE BEER-WARE LICENSE" (Revision 42): 7116411Sphk.\" <phk@login.dknet.dk> wrote this file. As long as you retain this notice you 8116411Sphk.\" can do whatever you want with this stuff. If we meet some day, and you think 9116411Sphk.\" this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 10116411Sphk.\" ---------------------------------------------------------------------------- 11116411Sphk.\" 12116411Sphk.\" $FreeBSD$ 13116411Sphk.\" 14116411Sphk.if n .ND 15116411Sphk.TI 16116411SphkTimecounters: Efficient and precise timekeeping in SMP kernels. 17116411Sphk.AA 18116411Sphk.A "Poul-Henning Kamp" "The FreeBSD Project" 19116411Sphk.AB 20116411Sphk.PP 21116411SphkThe FreeBSD timecounters are an architecture-independent implementation 22116411Sphkof a binary timescale using whatever hardware support is at hand 23116411Sphkfor tracking time. The binary timescale converts using simple 24116411Sphkmultiplication to canonical timescales based on micro- or nano-seconds 25116411Sphkand can interface seamlessly to the NTP PLL/FLL facilities for clock 26116411Sphksynchronisation. Timecounters are implemented using lock-less 27116411Sphkstable-storage based primitives which scale efficiently in SMP 28116411Sphksystems. The math and implementation behind timecounters will 29116411Sphkbe detailed as well as the mechanisms used for synchronisation. \** 30116411Sphk.AE 31116411Sphk.FS 32116411SphkThis paper was presented at the EuroBSDcon 2002 conference in Amsterdam. 33116411Sphk.FE 34116411Sphk.SH 35116411SphkIntroduction 36116411Sphk.PP 37116411SphkDespite digging around for it, I have not been able to positively 38116411Sphkidentify the first computer which knew the time of day. 39116411SphkThe feature probably arrived either from the commercial side 40116411Sphkso service centres could bill computer cycles to customers or from 41116411Sphkthe technical side so computers could timestamp external events, 42116411Sphkbut I have not been able to conclusively nail the first implementation down. 43116411Sphk.LP 44116411SphkBut there is no doubt that it happened very early in the development 45116411Sphkof computers 46116411Sphkand if systems like the ``SAGE'' [SAGE] did not know what time 47116411Sphkit was I would be amazed. 48116411Sphk.LP 49116411SphkOn the other hand, it took a long time for a real time clock to 50116411Sphkbecome a standard feature: 51116411Sphk.LP 52116411SphkThe ``Apple ]['' computer 53116411Sphkhad neither in hardware or software any notion what time it was. 54116411Sphk.LP 55116411SphkThe original ``IBM PC'' did know what time it was, provided you typed 56116411Sphkit in when you booted it, but it forgot when you turned it off. 57116411Sphk.LP 58116411SphkOne of the ``advanced technologies'' in the ``IBM PC/AT'' was a battery 59116411Sphkbacked CMOS chip which kept track of time even when the computer 60116411Sphkwas powered off. 61116411Sphk.LP 62116411SphkToday we expect our computers to know the time, and with network 63116411Sphkprotocols like NTP we will usually find that they do, give and 64116411Sphktake some milliseconds. 65116411Sphk.LP 66116411SphkThis article is about the code in the FreeBSD kernel which keeps 67116411Sphktrack of time. 68116411Sphk.SH 69116411SphkTime and timescale basics 70116411Sphk.PP 71116411SphkDespite the fact that time is the physical quantity (or maybe entity 72116411Sphk?) about which we know the least, it is at the same time [sic!] what we 73116411Sphkcan measure with the highest precision of all physical quantities. 74116411Sphk.LP 75160964SyarThe current crop of atomic clocks will neither gain nor lose a 76116411Sphksecond in the next couple hundred million years, provided we 77116411Sphkstick to the preventative maintenance schedules. This is a feat 78116411Sphkroughly in line with to knowing the circumference of the Earth 79116411Sphkwith one micrometer precision, in real time. 80116411Sphk.LP 81116411SphkWhile it is possible to measure time by means other than oscillations, 82116411Sphkfor instance transport or consumption of a substance at a well-known 83116411Sphkrate, such designs play no practical role in time measurement because 84116411Sphktheir performance is significantly inferior to oscillation based 85116411Sphkdesigns. 86116411Sphk.LP 87116411SphkIn other words, it is pretty fair to say that all relevant 88116411Sphktimekeeping is based on oscillating phenomena: 89116411Sphk.TS 90116411Sphkcenter; 91116411Sphkl l. 92116411Sphksun-dial Earths rotation about its axis. 93116411Sphkcalendar Ditto + Earths orbit around the sun. 94116411Sphkclockwork Mechanical oscillation of pendulum. 95116411Sphkcrystals Mechanical resonance in quartz. 96116411Sphkatomic Quantum-state transitions in atoms. 97116411Sphk.TE 98116411Sphk.LP 99116411SphkWe can therefore with good fidelity define ``a clock'' to be the 100116411Sphkcombination of an oscillator and a counting mechanism: 101116411Sphk.LP 102119760Sjkoshy.if t .PSPIC fig3.eps 103116411Sphk.LP 104116411SphkThe standard second is currently defined as 105116411Sphk.QP 106116411SphkThe 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. 107116411Sphk.LP 108116411Sphkand we have frequency standards which are able to mark a sequence of 109116411Sphksuch seconds 110116411Sphkwith an error less than �2 cdot 10 sup{-15}� [DMK2001] with commercially 111116411Sphkavailable products doing better than �1 cdot 10 sup{-14}� [AG2002]. 112116411Sphk.LP 113119760SjkoshyUnlike other physical units with a conventionally defined origin, 114116411Sphklongitude for instance, the ephemeral nature of time prevents us 115116411Sphkfrom putting a stake in the ground, so to speak, and measure from 116116411Sphkthere. For measuring time we have to rely on ``dead reckoning'', 117116411Sphkjust like the navigators before Harrison built his clocks [RGO2002]: 118116411SphkWe have to tally how far we went from our reference point, keeping a 119116411Sphkrunning total at all times, and use that as our estimated position. 120116411Sphk.LP 121116411SphkThe upshot of this is, that we cannot define a timescale by any 122116411Sphkother means than some other timescale(s). 123116411Sphk.LP 124116411Sphk``Relative time'' is a time interval between two events, and for this 125116411Sphkwe only need to agree on the rate of the oscillator. 126116411Sphk.LP 127116411Sphk``Absolute time'' consists of a well defined point in time and the 128116411Sphktime interval since then, this is a bit more tricky. 129116411Sphk.LP 130116411SphkThe Internationally agreed upon TAI and the UTC timescales 131116411Sphkstarts at (from a physics point of view) arbitrary points in time 132116411Sphkand progresses in integral intervals of the standard second, with the 133116411Sphkdifference being that UTC does tricks to the counting to stay roughly 134116411Sphkin sync with Earths rotation \**. 135116411Sphk.FS 136116411SphkThe first atomic based definition actually operated in a different way: 137116411Sphkeach year would have its own value determined for the frequency of the 138116411Sphkcaesium resonance, selected so as to match the revolution rate of the 139116411SphkEarth. This resulted in time-intervals being very unwieldy business, 140116411Sphkand more and more scientists realized that that the caesium resonance 141116411Sphkwas many times more stable than the angular momentum of the Earth. 142116411SphkEventually the new leap-second method were introduced in 1972. 143116411SphkIt is interesting to note that the autumn leaves falling on the 144116411Sphknorthern hemisphere affects the angular momentum enough to change 145116411Sphkthe Earths rotational rate measurably. 146116411Sphk.FE 147116411Sphk.LP 148116411SphkTAI is defined as a sequence of standard seconds (the first timescale), 149116411Sphkcounted from January 1st 1958 (the second timescale). 150116411Sphk.LP 151116411SphkUTC is defined basically the same way, but every so often a leap-second 152116411Sphkis inserted (or theoretically deleted) to keep UTC synchronised 153116411Sphkwith Earths rotation. 154116411Sphk.LP 155116411SphkBoth the implementation of these two, and a few others speciality 156116411Sphktimescales are the result of the 157116411Sphkcombined efforts of several hundred atomic frequency standards in 158116411Sphkvarious laboratories and institutions throughout the world, all 159116411Sphkreporting to the BIPM in Paris who calculate the ``paper clock'' which 160116411SphkTAI and UTC really are using a carefully designed weighting algorithm \**. 161116411Sphk.FS 162116411SphkThe majority of these clocks are model 5071A from Agilent (the test 163116411Sphkand measurement company formerly known as ``Hewlett-Packard'') which 164116411Sphkcount for as much as 85% of the combined weight. 165116411SphkA fact the company deservedly is proud of. 166116411SphkThe majority of the remaining weight is assigned to a handful of big 167116411Sphkcustom-design units like the PTB2 and NIST7. 168116411Sphk.FE 169116411Sphk.LP 170116411SphkLeap seconds are typically announced six to nine months in advance, 171116411Sphkbased on precise observations of median transit times of stars and VLBI 172116411Sphkradio astronomy of very distant quasars. 173116411Sphk.LP 174116411SphkThe perceived wisdom of leap-seconds have been gradually decreasing 175116411Sphkin recent years, as devices and products with built-in calendar 176116411Sphkfunctionality becomes more and more common and people realize that 177116411Sphkuser input or software upgrades are necessary to instruct the 178116411Sphkcalendar functionality about upcoming leap seconds. 179116411Sphk.SH 180116411SphkUNIX timescales 181116411Sphk.PP 182116411SphkUNIX systems use a timescale which pretends to be UTC, but defined 183116411Sphkas the count of standard seconds since 00:00:00 01-01-1970 UTC, 184116411Sphkignoring the leap-seconds. This definition has never been perceived 185116411Sphkas wise. 186116411Sphk.LP 187116411SphkIgnoring leap seconds means that unless some trickery is performed 188116411Sphkwhen a leap second happens on the UTC scale, UNIX clocks would be 189116411Sphkone second off. Another implication is that the length of a 190116411Sphktime interval calculated on UNIX time_t variables, can be up to 22 191116411Sphk(and counting) seconds wrong relative to the same time interval 192116411Sphkmeasured on the UTC timescale. 193116411Sphk.LP 194116411SphkRecent efforts have tried to make the NTP protocol make up for this 195116411Sphkdeficiency by transmitting the UTC-TAI offset as part of the protocol. 196116411Sphk[MILLS2000A] 197116411Sphk.LP 198116411SphkFractional seconds are represented two ways in UNIX, ``timeval'' and 199116411Sphk``timespec''. Both of these formats are two-component structures 200116411Sphkwhich record the number of seconds, and the number of microseconds 201116411Sphkor nanoseconds respectively. 202116411Sphk.LP 203116411SphkThis unfortunate definition makes arithmetic on these two formats 204116411Sphkquite expensive to perform in terms of computer instructions: 205116411Sphk.DS 206116411Sphk.ps -1 207116411Sphk/* Subtract timeval from timespec */ 208116411Sphkt3.tv_sec = t1.tv_sec - t2.tv_sec; 209116411Sphkt3.tv_nsec = t1.tv_nsec - 210116411Sphk t2.tv_usec * 1000; 211116411Sphkif (t3.tv_nsec >= 1000000000) { 212116411Sphk t3.tv_sec++; 213116411Sphk t3.tv_nsec -= 1000000000; 214116411Sphk} else if (t3.tv_nsec < 0) { 215116411Sphk t3.tv_sec--; 216116411Sphk t3.tv_nsec += 1000000000; 217116411Sphk} 218116411Sphk.ps +1 219116411Sphk.DE 220116411Sphk.LP 221116411SphkWhile nanoseconds will probably be enough for most timestamping 222116411Sphktasks faced by UNIX computers for a number of years, it is an 223116411Sphkincreasingly uncomfortable situation that CPU clock periods and 224116411Sphkinstruction timings are already not representable in the standard 225116411Sphktime formats available on UNIX for consumer grade hardware, 226116411Sphkand the first POSIX mandated API, \fCclock_getres(3)\fP has 227116411Sphkalready effectively reached end of life as a result of this. 228116411Sphk.LP 229116411SphkHopefully the various standards bodies will address this issue 230116411Sphkbetter in the future. 231116411Sphk.SH 232116411SphkPrecision, Stability and Resolution 233116411Sphk.PP 234116411SphkThree very important terms in timekeeping are ``precision'', 235116411Sphk``stability'' and ``resolution''. 236116411SphkWhile the three words may seem to describe somewhat the 237116411Sphksame property in most uses, their use in timekeeping covers three 238116411Sphkvery distinct and well defined properties of a clock. 239116411Sphk.LP 240116411SphkResolution in clocks is simply a matter of the step-size of the 241116411Sphkcounter or in other words: the rate at which it steps. 242116411SphkA counter running on a 1 MHz frequency will have a resolution 243116411Sphkof 1 microsecond. 244116411Sphk.LP 245116411SphkPrecision talks about how close to the intended rate the clock runs, 246116411Sphkstability about how much the rate varies and resolution about the 247116411Sphksize of the smallest timeinterval we can measure. 248116411Sphk.LP 249116411SphkFrom a quality point of view, Stability is a much more 250116411Sphkvaluable property than precision, this is probably best explained 251116411Sphkusing a graphic illustration of the difference between the two 252116411Sphkconcepts: 253116411Sphk.LP 254119760Sjkoshy.if t .PSPIC fig1.eps 255116411Sphk.LP 256116411SphkIn the top row we have instability, the bullet holes are spread over 257116411Sphka large fraction of the target area. 258116411SphkIn the bottom row, the bullets all hit in a very small area. 259116411Sphk.LP 260116411SphkOn the left side, we have lack of precision, the holes obviously are 261116411Sphknot centred on the target, a systematic offset exists. 262116411SphkIn the right side we have precision, the bullets are centred on 263116411Sphkthe target \**. 264116411Sphk.FS 265116411SphkWe cannot easily get resolution into this analogy, the obvious 266116411Sphkrepresentation as the diameter of the bullet-hole is not correct, 267116411Sphkit would have to be the grid or other pattern of locations where 268116411Sphkthe bullet could possibly penetrate the target material, but this 269116411Sphkgets too quantum-mechanical-oid to serve the instructional purpose. 270116411Sphk.FE 271116411Sphk.LP 272116411SphkTransposing these four targets to actual clocks, the situation 273116411Sphkcould look like the following plots: 274116411Sphk.LP 275119760Sjkoshy.if t .PSPIC fig2.eps 276116411Sphk.LP 277116411SphkOn the x-axis we have time and on the y-axis how wrong the clock 278116411Sphkwas at a given point in time. 279116411Sphk.LP 280116411SphkThe reason atomic standards are such a big deal in timekeeping is 281116411Sphkthat they are incredibly stable: they are able to generate an oscillation 282116411Sphkwhere the period varies by roughly a millionth of a billonth of a 283116411Sphksecond in long term measurements. 284116411Sphk.LP 285116411SphkThey are in fact not nearly as precise as they are stable, but as 286116411Sphkone can see from the graphic above, a stable clock which is not 287116411Sphkprecise can be easily corrected for the offset and thus calibrated 288116411Sphkis as good as any clock. 289116411Sphk.LP 290116411SphkThis lack of precision is not necessarily a flaw in these kinds of 291116411Sphkdevices, once you get into the �10 cdot 10 sup{-15}� territory 292116411Sphkthings like the blackbody spectrum at the particular absolute 293116411Sphktemperature of the clocks hardware and general relativistic 294116411Sphkeffects mostly dependent on the altitude above earths center 295116411Sphkhas to be corrected for \**. 296116411Sphk.FS 297116411SphkThis particularly becomes an issue with space-based atomic standards 298116411Sphkas those found on the ``Navstar'' GPS satellites. 299116411Sphk.FE 300116411Sphk.SH 301116411SphkDesign goals of timecounters 302116411Sphk.PP 303116411SphkAfter this brief description of the major features of the local 304116411Sphklandscape, we can look at the design goals of timecounters in detail: 305116411Sphk.LP 306116411Sphk.I "Provide timestamps in timeval and timespec formats," 307116411Sphk.IP 308116411SphkThis is obviously the basic task we have to solve, but as was noted 309116411Sphkearlier, this is in no way the performance requirement. 310116411Sphk.LP 311116411Sphk.I "on both the ``uptime'' and the POSIX timescales," 312116411Sphk.IP 313116411SphkThe ``uptime'' timescale is convenient for time intervals which are 314116411Sphknot anchored in UTC time: the run time of processes, the access 315116411Sphktime of disks and similar. 316116411Sphk.IP 317116411SphkThe uptime timescale counts seconds starting from when the system 318116411Sphkis booted. The POSIX/UTC timescale is implemented by adding an 319116411Sphkestimate of the POSIX time when the system booted to the uptime 320116411Sphktimescale. 321116411Sphk.LP 322116411Sphk.I "using whatever hardware we have available at the time," 323116411Sphk.IP 324116411SphkWhich in a subtle way also implies ``be able to switch from one 325116411Sphkpiece of hardware to another on the fly'' since we may not know 326116411Sphkright up front what hardware we have access to and which is 327116411Sphkpreferable to use. 328116411Sphk.LP 329116411Sphk.I "while supporting time the NTP PLL/FLL discipline code," 330116411Sphk.IP 331116411SphkThe NTP kernel PLL/FLL code allows the local clock and timescale 332116411Sphkto be synchronised or syntonised to an external timescale either 333116411Sphkvia network packets or hardware connection. This also implies 334116411Sphkthat the rate and phase of the timescale must be manoeuvrable 335116411Sphkwith sufficient resolution. 336116411Sphk.LP 337116411Sphk.I "and providing support for the RFC 2783 PPS API," 338116411Sphk.IP 339116411SphkThis is mainly for the benefit of the NTPD daemons communication 340116411Sphkwith external clock or frequency hardware, but it has many other 341116411Sphkinteresting uses as well [PHK2001]. 342116411Sphk.LP 343116411Sphk.I "in a SMP efficient way." 344116411Sphk.IP 345116411SphkTimestamps are used many places in the kernel and often at pretty 346116411Sphkhigh rate so it is important that the timekeeping facility 347116411Sphkdoes not become a point of CPU or lock contention. 348116411Sphk.SH 349116411SphkTimecounter timestamp format. 350116411Sphk.PP 351116411SphkChoosing the fundamental timestamp format for the timecounters is 352116411Sphkmostly a question of the resolution and steer-ability requirements. 353116411Sphk.LP 354116411SphkThere are two basic options on contemporary hardware: use a 32 bit 355116411Sphkinteger for the fractional part of seconds, or use a 64 bit which 356116411Sphkis computationally more expensive. 357116411Sphk.LP 358116411SphkThe question therefore reduced to the somewhat simpler: can we get 359116411Sphkaway with using only 32 bit ? 360116411Sphk.LP 361116411SphkSince 32 bits fractional seconds have a resolution of slightly 362116411Sphkbetter than quarter of a nanosecond (.2328 nsec) it can obviously 363116411Sphkbe converted to nanosecond resolution struct timespec timestamps 364116411Sphkwith no loss of precision, but unfortunately not with pure 32 bit 365116411Sphkarithmetic as that would result in unacceptable rounding errors. 366116411Sphk.LP 367116411SphkBut timecounters also need to represent the clock period of the 368116411Sphkchosen hardware and this hardware might be the GHz range CPU-clock. 369116411SphkThe list of clock frequencies we could support with 32 bits are: 370116411Sphk.TS 371116411Sphkcenter; 372116411Sphkl l n l. 373116411Sphk�2 sup{32} / 1� �=� 4.294 GHz 374116411Sphk�2 sup{32} / 2� �=� 2.147 GHz 375116411Sphk�2 sup{32} / 3� �=� 1.432 GHz 376116411Sphk\&... 377116411Sphk�2 sup{32} / (2 sup{32}-1)� �=� 1.000 Hz 378116411Sphk.TE 379116411SphkWe can immediately see that 32 bit is insufficient to faithfully 380116411Sphkrepresent clock frequencies even in the low GHz area, much less in 381116411Sphkthe range of frequencies which have already been vapourwared by 382116411Sphkboth IBM, Intel and AMD. 383116411SphkQED: 32 bit fractions are not enough. 384116411Sphk.LP 385116411SphkWith 64 bit fractions the same table looks like: 386116411Sphk.TS 387116411Sphkcenter; 388116411Sphkl l r l. 389116411Sphk�2 sup{64} / 1� �=� � 18.45 cdot 10 sup{9}� GHz 390116411Sphk�2 sup{64} / 2� �=� � 9.223 cdot 10 sup{9}� GHz 391116411Sphk\&... 392116411Sphk�2 sup{64} / 2 sup{32}� �=� 4.294 GHz 393116411Sphk\&... 394116411Sphk�2 sup{64} / (2 sup{64}-1)� �=� 1.000 Hz 395116411Sphk.TE 396116411SphkAnd the resolution in the 4 GHz frequency range is approximately one Hz. 397116411Sphk.LP 398116411SphkThe following format have therefore been chosen as the basic format 399116411Sphkfor timecounters operations: 400116411Sphk.DS 401116411Sphk.ps -1 402116411Sphkstruct bintime { 403116411Sphk time_t sec; 404116411Sphk uint64_t frac; 405116411Sphk}; 406116411Sphk.ps +1 407116411Sphk.DE 408116411SphkNotice that the format will adapt to any size of time_t variable, 409116411Sphkkeeping timecounters safely out of the ``We SHALL prepare for the 410116411SphkY2.038K problem'' war zone. 411116411Sphk.LP 412116411SphkOne beauty of the bintime format, compared to the timeval and 413116411Sphktimespec formats is that it is a binary number, not a pseudo-decimal 414116411Sphknumber. If compilers and standards allowed, the representation 415116411Sphkwould have been ``int128_t'' or at least ``int96_t'', but since this 416116411Sphkis currently not possible, we have to express the simple concept 417116411Sphkof multiword addition in the C language which has no concept of a 418116411Sphk``carry bit''. 419116411Sphk.LP 420116411SphkTo add two bintime values, the code therefore looks like this \**: 421116411Sphk.FS 422116411SphkIf the reader suspects the '>' is a typo, further study is suggested. 423116411Sphk.FE 424116411Sphk.LP 425116411Sphk.DS 426116411Sphk.ps -1 427116411Sphkuint64_t u; 428116411Sphk 429116411Sphku = bt1->frac; 430116411Sphkbt3->frac = bt1->frac + bt2->frac; 431116411Sphkbt3->sec = bt1->sec + bt2->sec; 432116411Sphkif (u > bt3->frac) 433116411Sphk bt3->sec += 1; 434116411Sphk.ps +1 435116411Sphk.DE 436116411Sphk.LP 437116411SphkAn important property of the bintime format is that it can be 438116411Sphkconverted to and from timeval and timespec formats with simple 439116411Sphkmultiplication and shift operations as shown in these two 440116411Sphkactual code fragments: 441116411Sphk.DS 442116411Sphk.ps -1 443116411Sphkvoid 444116411Sphkbintime2timespec(struct bintime *bt, 445116411Sphk struct timespec *ts) 446116411Sphk{ 447116411Sphk 448116411Sphk ts->tv_sec = bt->sec; 449116411Sphk ts->tv_nsec = 450116411Sphk ((uint64_t)1000000000 * 451116411Sphk (uint32_t)(bt->frac >> 32)) >> 32; 452116411Sphk} 453116411Sphk.ps +1 454116411Sphk.DE 455116411Sphk.DS 456116411Sphk.ps -1 457116411Sphkvoid 458116411Sphktimespec2bintime(struct timespec *ts, 459116411Sphk struct bintime *bt) 460116411Sphk{ 461116411Sphk 462116411Sphk bt->sec = ts->tv_sec; 463116411Sphk /* 18446744073 = 464116411Sphk int(2^64 / 1000000000) */ 465116411Sphk bt->frac = ts->tv_nsec * 466116411Sphk (uint64_t)18446744073LL; 467116411Sphk} 468116411Sphk.ps +1 469116411Sphk.DE 470116411Sphk.LP 471116411Sphk.SH 472116411SphkHow timecounters work 473116411Sphk.PP 474116411SphkTo produce a current timestamp the timecounter code 475116411Sphkreads the hardware counter, subtracts a reference 476116411Sphkcount to find the number of steps the counter has 477116411Sphkprogressed since the reference timestamp. 478116411SphkThis number of steps is multiplied with a factor 479116411Sphkderived from the counters frequency, taking into account 480116411Sphkany corrections from the NTP PLL/FLL and this product 481116411Sphkis added to the reference timestamp to get a timestamp. 482116411Sphk.LP 483116411SphkThis timestamp is on the ``uptime'' time scale, so if 484116411SphkUNIX/UTC time is requested, the estimated time of boot is 485116411Sphkadded to the timestamp and finally it is scaled to the 486116411Sphktimeval or timespec if that is the desired format. 487116411Sphk.LP 488116411SphkA fairly large number of functions are provided to produce 489116411Sphktimestamps, depending on the desired timescale and output 490116411Sphkformat: 491116411Sphk.TS 492116411Sphkcenter; 493116411Sphkl r r. 494116411SphkDesired uptime UTC/POSIX 495116411SphkFormat timescale timescale 496116411Sphk_ 497116411Sphkbintime binuptime() bintime() 498116411Sphktimespec nanouptime() nanotime() 499116411Sphktimeval microuptime() microtime() 500116411Sphk.TE 501116411Sphk.LP 502116411SphkSome applications need to timestamp events, but are not 503116411Sphkparticular picky about the precision. 504116411SphkIn many cases a precision of tenths or hundreds of 505116411Sphkseconds is sufficient. 506116411Sphk.LP 507116411SphkA very typical case is UNIX file timestamps: 508116411SphkThere is little point in spending computational resources getting an 509116411Sphkexact nanosecond timestamp, when the data is written to 510116411Sphka mechanical device which has several milliseconds of unpredictable 511116411Sphkdelay before the operation is completed. 512116411Sphk.LP 513116411SphkTherefore a complementary shadow family of timestamping functions 514116411Sphkwith the prefix ``get'' have been added. 515116411Sphk.LP 516116411SphkThese functions return the reference 517116411Sphktimestamp from the current timehands structure without going to the 518116411Sphkhardware to determine how much time has elapsed since then. 519116411SphkThese timestamps are known to be correct to within rate at which 520116411Sphkthe periodic update runs, which in practice means 1 to 10 milliseconds. 521116411Sphk.SH 522116411SphkTimecounter math 523116411Sphk.LP 524116411SphkThe delta-count operation is straightforward subtraction, but we 525116411Sphkneed to logically AND the result with a bit-mask with the same number 526116411Sphk(or less) bits as the counter implements, 527116411Sphkto prevent higher order bits from getting set when the counter rolls over: 528116411Sphk.DS 529116411Sphk.ce 530116411Sphk.EQ 531116411SphkDelta Count = (Count sub{now} - Count sub{ref}) ~ BITAND ~ mask 532116411Sphk.EN 533116411Sphk.DE 534116411SphkThe scaling step is straightforward. 535116411Sphk.DS 536116411Sphk.ce 537116411Sphk.EQ 538116411SphkT sub{now} = Delta Count cdot R sub{counter} + T sub{ref} 539116411Sphk.EN 540116411Sphk.DE 541116411SphkThe scaling factor �R sub{counter}� will be described below. 542116411Sphk.LP 543116411SphkAt regular intervals, scheduled by \fChardclock()\fP, a housekeeping 544116411Sphkroutine is run which does the following: 545116411Sphk.LP 546116411SphkA timestamp with associated hardware counter reading is elevated 547116411Sphkto be the new reference timecount: 548116411Sphk.DS 549116411Sphk 550116411Sphk.ce 551116411Sphk.EQ 552116411SphkDelta Count = (Count sub{now} - Count sub{ref}) ~ BITAND ~ mask 553116411Sphk.EN 554116411Sphk 555116411Sphk.ce 556116411Sphk.EQ 557116411SphkT sub{now} = Delta Count cdot R sub{counter} 558116411Sphk.EN 559116411Sphk 560116411Sphk.ce 561116411Sphk.EQ 562116411SphkCount sub{ref} = Count sub{now} 563116411Sphk.EN 564116411Sphk 565116411Sphk.ce 566116411Sphk.EQ 567116411SphkT sub{ref} = T sub{now} 568116411Sphk.EN 569116411Sphk.DE 570116411Sphk.LP 571116411SphkIf a new second has started, the NTP processing routines are called 572116411Sphkand the correction they return and the counters frequency is used 573116411Sphkto calculate the new scaling factor �R sub{counter}�: 574116411Sphk.DS 575116411Sphk.ce 576116411Sphk.EQ 577116411SphkR sub{counter} = {2 sup{64} over Freq sub{counter}} cdot ( 1 + R sub{NTP} ) 578116411Sphk.EN 579116411Sphk.DE 580116411SphkSince we only have access to 64 bit arithmetic, dividing something 581116411Sphkinto �2 sup{64}� is a problem, so in the name of code clarity 582116411Sphkand efficiency, we sacrifice the low order bit and instead calculate: 583116411Sphk.DS 584116411Sphk.ce 585116411Sphk.EQ 586116411SphkR sub{counter} = 2 cdot {2 sup{63} over Freq sub{counter}} cdot ( 1 + R sub{NTP} ) 587116411Sphk.EN 588116411Sphk.DE 589116411SphkThe �R sub{NTP}� correct factor arrives as the signed number of 590116411Sphknanoseconds (with 32 bit binary fractions) to adjust per second. 591116411SphkThis quasi-decimal number is a bit of a square peg in our round binary 592116411Sphkhole, and a conversion factor is needed. 593116411SphkIdeally we want to multiply this factor by: 594116411Sphk.DS 595116411Sphk.ce 596116411Sphk.EQ 597116411Sphk2 sup {64} over {10 sup{9} cdot 2 sup{32}} = 4.294967296 598116411Sphk.EN 599116411Sphk.DE 600116411SphkThis is not a nice number to work with. 601116411SphkFortunately, the precision of this correction is not critical, we are 602116411Sphkwithin an factor of a million of the �10 sup{-15}� performance level 603116411Sphkof state of the art atomic clocks, so we can use an approximation 604116411Sphkon this term without anybody noticing. 605116411Sphk.LP 606116411SphkDeciding which fraction to use as approximation needs to carefully 607116411Sphkconsider any possible overflows that could happen. 608116411SphkIn this case the correction may be as large as \(+- 5000 PPM which 609116411Sphkleaves us room to multiply with about 850 in a multiply-before-divide 610116411Sphksetting. 611116411SphkUnfortunately, there are no good fractions which multiply with less 612116411Sphkthan 850 and at the same time divide by a power of two, which is 613116411Sphkdesirable since it can be implemented as a binary shift instead of 614116411Sphkan expensive full division. 615116411Sphk.LP 616116411SphkA divide-before-multiply approximation necessarily results in a loss 617116411Sphkof lower order bits, but in this case dividing by 512 and multiplying 618116411Sphkby 2199 gives a good approximation where the lower order bit loss is 619116411Sphknot a concern: 620116411Sphk.DE 621116411Sphk.EQ 622116411Sphk2199 over 512 = 4.294921875 623116411Sphk.EN 624116411Sphk.DE 625116411SphkThe resulting error is an systematic under compensation of 10.6PPM 626116411Sphkof the requested change, or �1.06 cdot 10 sup -14� per nanosecond 627116411Sphkof correction. 628116411SphkThis is perfectly acceptable. 629116411Sphk.LP 630116411SphkPutting it all together, including the one bit we put on the alter for the 631116411SphkGoddess of code clarity, the formula looks like this: 632116411Sphk.DS 633116411Sphk.ce 634116411Sphk.EQ 635116411SphkR sub{counter} = 2 cdot {{2 sup{63} + 2199 cdot {R sub{NTP}} over 1024} over Freq sub{counter}} 636116411Sphk.EN 637116411Sphk.DE 638116411SphkPresented here in slightly unorthodox format to show the component arithmetic 639116411Sphkoperations as they are carried out in the code. 640116411Sphk.SH 641116411SphkFrequency of the periodic update 642116411Sphk.PP 643116411SphkThe hardware counter should have a long enough 644116411Sphkperiod, ie, number of distinct counter values divided by 645116411Sphkfrequency, to not roll over before our periodic update function 646116411Sphkhas had a chance to update the reference timestamp data. 647116411Sphk.LP 648116411SphkThe periodic update function is called from \fChardclock()\fP which 649116411Sphkruns at a rate which is controlled by the kernel parameter 650116411Sphk.I HZ . 651116411Sphk.LP 652116411SphkBy default HZ is 100 which means that only hardware with a period 653116411Sphklonger than 10 msec is usable. 654116411SphkIf HZ is configured higher than 1000, an internal divider is 655116411Sphkactivated to keep the timecounter periodic update running 656116411Sphkno more often than 2000 times per second. 657116411Sphk.LP 658116411SphkLet us take an example: 659116411SphkAt HZ=100 a 16 bit counter can run no faster than: 660116411Sphk.DS 661116411Sphk.ce 662116411Sphk.EQ 663116411Sphk2 sup{16} cdot {100 Hz} = 6.5536 MHz 664116411Sphk.EN 665116411Sphk.DE 666116411SphkSimilarly, if the counter runs at 10MHz, the minimum HZ is 667116411Sphk.DS 668116411Sphk.ce 669116411Sphk.EQ 670116411Sphk{10 MHz} over {2 sup{16}} = 152.6 Hz 671116411Sphk.EN 672116411Sphk.DE 673116411Sphk.LP 674116411SphkSome amount of margin is of course always advisable, 675116411Sphkand a factor two is considered prudent. 676116411Sphk.LP 677116411Sphk.SH 678116411SphkLocking, lack of ... 679116411Sphk.PP 680116411SphkProvided our hardware can be read atomically, that our arithmetic 681116411Sphkhas enough bits to not roll over and that our clock frequency is 682116411Sphkperfectly, or at least sufficiently, stable, we could avoid the 683116411Sphkperiodic update function, and consequently disregard the entire 684116411Sphkissue of locking. 685116411SphkWe are seldom that lucky in practice. 686116411Sphk.LP 687116411SphkThe straightforward way of dealing with meta data updates is to 688116411Sphkput a lock of some kind on the data and grab hold of that before 689116411Sphkdoing anything. 690116411SphkThis would however be a very heavy-handed approach. First of 691116411Sphkall, the updates are infrequent compared to simple references, 692116411Sphksecond it is not important which particular state of meta data 693116411Sphka consumer gets hold of, as long as it is consistent: as long 694116411Sphkas the �Count sub{ref}� and �T sub{ref}� are a matching pair, 695116411Sphkand not old enough to cause an ambiguity with hardware counter 696116411Sphkrollover, a valid timestamp can be derived from them. 697116411Sphk.LP 698116411SphkA pseudo-stable-storage with generation count method has been 699116411Sphkchosen instead. 700116411SphkA ring of ten ``timehands'' data structures are used to hold the 701116411Sphkstate of the timecounter system, the periodic update function 702116411Sphkupdates the next structure with the new reference data and 703116411Sphkscaling factor and makes it the current timehands. 704116411Sphk.LP 705116411SphkThe beauty of this arrangement lies in the fact that even though 706116411Sphka particular ``timehands'' data structure has been bumped from being 707116411Sphkthe ``currents state'' by its successor, it still contains valid data 708116411Sphkfor some amount of time into the future. 709116411Sphk.LP 710116411SphkTherefore, a process which has started the timestamping process but 711116411Sphksuffered an interrupt which resulted in the above periodic processing 712116411Sphkcan continue unaware of this afterwards and not suffer corruption 713116411Sphkor miscalculation even though it holds no locks on the shared 714116411Sphkmeta-data. 715119760Sjkoshy.if t .PSPIC fig4.eps 716116411Sphk.LP 717116411SphkThis scheme has an inherent risk that a process may be de-scheduled for 718116411Sphkso long time that it will not manage to complete the timestamping 719116411Sphkprocess before the entire ring of timehands have been recycled. 720116411SphkThis case is covered by each timehand having a private generation number 721116411Sphkwhich is temporarily set to zero during the periodic processing, to 722116411Sphkmark inconsistent data, and incremented to one more than the 723116411Sphkprevious value when the update has finished and the timehands 724116411Sphkis again consistent. 725116411Sphk.LP 726116411SphkThe timestamping code will grab a copy of this generation number and 727116411Sphkcompare this copy to the generation in the timehands after completion 728116411Sphkand if they differ it will restart the timestamping calculation. 729116411Sphk.DS 730116411Sphk.ps -1 731116411Sphkdo { 732116411Sphk th = timehands; 733116411Sphk gen = th->th_generation; 734116411Sphk /* calculate timestamp */ 735116411Sphk} while (gen == 0 || 736116411Sphk gen != th->th_generation); 737116411Sphk.ps +1 738116411Sphk.DE 739116411Sphk.LP 740116411SphkEach hardware device supporting timecounting is represented by a 741116411Sphksmall data structure called a timecounter, which documents the 742116411Sphkfrequency, the number of bits implemented by the counter and a method 743116411Sphkfunction to read the counter. 744116411Sphk.LP 745116411SphkPart of the state in the timehands structure is a pointer to the 746116411Sphkrelevant timecounter structure, this makes it possible to change 747116411Sphkto a one piece of hardware to another ``on the fly'' by updating 748116411Sphkthe current timehands pointer in a manner similar to the periodic 749116411Sphkupdate function. 750116411Sphk.LP 751116411SphkIn practice this can be done with sysctl(8): 752116411Sphk.DS 753116411Sphk.ps -1 754116411Sphksysctl kern.timecounter.hardware=TSC 755116411Sphk.ps +1 756116411Sphk.DE 757116411Sphk.LP 758116411Sphkat any time while the system is running. 759116411Sphk.SH 760116411SphkSuitable hardware 761116411Sphk.PP 762116411SphkA closer look on ``suitable hardware'' is warranted 763116411Sphkat this point. 764116411SphkIt is obvious from the above description that the ideal hardware 765116411Sphkfor timecounting is a wide binary counter running at a constant 766116411Sphkhigh frequency 767116411Sphkand atomically readable by all CPUs in the system with a fast 768116411Sphkinstruction(-sequence). 769116411Sphk.LP 770116411SphkWhen looking at the hardware support on the PC platform, one 771116411Sphkis somewhat tempted to sigh deeply and mutter ``so much for theory'', 772116411Sphkbecause none of the above parameters seems to have been on the 773116411Sphkdrawing board together yet. 774116411Sphk.LP 775116411SphkAll IBM PC derivatives contain a device more or less compatible 776116411Sphkwith the venerable Intel i8254 chip. 777116411SphkThis device contains 3 counters of 16 bits each, 778116411Sphkone of which is wired so it can interrupt the CPU when the 779116411Sphkprogrammable terminal count is reached. 780116411Sphk.LP 781116411SphkThe problem with this device is that it only has 8bit bus-width, 782116411Sphkso reading a 16 bit timestamp takes 3 I/O operations: one to latch 783116411Sphkthe count in an internal register, and two to read the high and 784116411Sphklow parts of that register respectively. 785116411Sphk.LP 786116411SphkObviously, on multi-CPU systems this cannot be done without some 787116411Sphkkind of locking mechanism preventing the other CPUs from trying 788116411Sphkto do the same thing at the same time. 789116411Sphk.LP 790116411SphkLess obviously we find it is even worse than that: 791116411SphkSince a low priority kernel thread 792116411Sphkmight be reading a timestamp when an interrupt comes in, and since 793116411Sphkthe interrupt thread might also attempt to generate a timestamp, 794116411Sphkwe need to totally block interrupts out while doing those three 795116411SphkI/O instructions. 796116411Sphk.LP 797116411SphkAnd just to make life even more complicated, FreeBSD uses the same 798116411Sphkcounter to provide the periodic interrupts which schedule the 799116411Sphk\fChardclock()\fP routine, so in addition the code has to deal with the 800116411Sphkfact that the counter does not count down from a power of two and 801116411Sphkthat an interrupt is generated right after the reloading of the 802116411Sphkcounter when it reaches zero. 803116411Sphk.LP 804116411SphkOhh, and did I mention that the interrupt rate for hardclock() will 805116411Sphkbe set to a higher frequency if profiling is active ? \** 806116411Sphk.FS 807116411SphkI will not even mention the fact that it can be set also to ridiculous 808116411Sphkhigh frequencies in order to be able to use the binary driven ``beep'' 809116411Sphkspeaker in the PC in a PCM fashion to output ``real sounds''. 810116411Sphk.FE 811116411Sphk.LP 812116411SphkIt hopefully doesn't ever get more complicated than that, but it 813116411Sphkshows, in its own bizarre and twisted way, just how little help the 814116411Sphktimecounter code needs from the actual hardware. 815116411Sphk.LP 816116411SphkThe next kind of hardware support to materialise was the ``CPU clock 817116411Sphkcounter'' called ``TSC'' in official data-sheets. 818116411SphkThis is basically a on-CPU counter, which counts at the rate 819116411Sphkof the CPU clock. 820116411Sphk.LP 821116411SphkUnfortunately, the electrical power needed to run a CPU is pretty 822116411Sphkprecisely proportional with the clock frequency for the 823116411Sphkprevailing CMOS chip technology, so 824116411Sphkthe advent of computers powered by batteries prompted technologies 825116411Sphklike APM, ACPI, SpeedStep and others which varies or throttles the 826116411SphkCPU clock to match computing demand in order to minimise the power 827116411Sphkconsumption \**. 828116411Sphk.FS 829116411SphkThis technology also found ways into stationary computers from 830116411Sphktwo different vectors. 831116411SphkThe first vector was technical: Cheaper cooling solutions can be used 832116411Sphkfor the CPU if they are employed resulting in cheaper commodity 833116411Sphkhardware. 834116411SphkThe second vector was political: For reasons beyond reason, energy 835116411Sphkconservation became an issue with personal computers, despite the fact 836116411Sphkthat practically all north American households contains 4 to 5 household 837116411Sphkitems which through inefficient designs waste more power than a 838116411Sphkpersonal computer use. 839116411Sphk.FE 840116411Sphk.LP 841116411SphkAnother wiggle for the TSC is that it is not usable on multi-CPU 842116411Sphksystems because the counter is implemented inside the CPU and 843116411Sphknot readable from other CPUs in the system. 844116411Sphk.LP 845116411SphkThe counters on different CPUs are not guaranteed 846116411Sphkto run syntonously (ie: show the same count at the same time). 847116411SphkFor some architectures like the DEC/alpha architecture they do not even 848116411Sphkrun synchronously (ie: at the same rate) because the CPU clock frequency 849116411Sphkis generated by a small SAW device on the chip which is very sensitive 850116411Sphkto temperature changes. 851116411Sphk.LP 852116411SphkThe ACPI specification finally brings some light: 853116411Sphkit postulates the existence of a 24 or 32 bit 854116411Sphkcounter running at a standardised constant frequency and 855116411Sphkspecifically notes that this is intended to be used for timekeeping. 856116411Sphk.LP 857116411SphkThe frequency chosen, 3.5795454... MHz\** 858116411Sphk.FS 859116411SphkThe reason for this odd-ball frequency has to be sought in the ghastly 860116411Sphkcolours offered by the original IBM PC Color Graphics Adapter: It 861116411Sphkdelivered NTSC format output and therefore introduced the NTSC colour 862116411Sphksync frequency into personal computers. 863116411Sphk.FE 864116411Sphk is not quite as high as one 865116411Sphkcould have wished for, but it is certainly a big improvement over 866116411Sphkthe i8254 hardware in terms of access path. 867116411Sphk.LP 868116411SphkBut trust it to Murphys Law: The majority of implementations so far 869116411Sphkhave failed to provide latching suitable to avoid meta-stability 870116411Sphkproblems, and several readings from the counter is necessary to 871116411Sphkget a reliable timestamp. 872116411SphkIn difference from the i8254 mentioned above, we do not need to 873116411Sphkany locking while doing so, since each individual read is atomic. 874116411Sphk.LP 875116411SphkAn initialization routine tries to test if the ACPI counter is properly 876116411Sphklatched by examining the width of a histogram over read delta-values. 877116411Sphk.LP 878116411SphkOther architectures are similarly equipped with means for timekeeping, 879116411Sphkbut generally more carefully thought out compared to the haphazard 880116411Sphkdevelopments of the IBM PC architecture. 881116411Sphk.LP 882116411SphkOne final important wiggle of all this, is that it may not be possible 883116411Sphkto determine which piece of hardware is best suited for clock 884116411Sphkuse until well into or even after the bootstrap process. 885116411Sphk.LP 886116411SphkOne example of this is the Loran-C receiver designed by Prof. Dave Mills 887116411Sphk[MILLS1992] 888116411Sphkwhich is unsuitable as timecounter until the daemon program which 889116411Sphkimplements the software-half of the receiver has properly initialised 890116411Sphkand locked onto a Loran-C signal. 891116411Sphk.SH 892116411SphkIdeal timecounter hardware 893116411Sphk.LP 894116411SphkAs proof of concept, a sort of an existentialist protest against 895116411Sphkthe sorry state describe above, the author undertook a project to 896116411Sphkprove that it is possible to do better than that, since none of 897116411Sphkthe standard hardware offered a way to fully validate the timecounter 898116411Sphkdesign. 899116411Sphk.LP 900116411SphkUsing a COTS product, ``HOT1'', from Virtual Computers Corporation 901116411Sphk[VCC2002] containing a FPGA chip on a PCI form factor card, a 26 902116411Sphkbit timecounter running at 100MHz was successfully implemented. 903116411Sphk.LP 904119760Sjkoshy.if t .PSPIC fig5.eps 905116411Sphk.LP 906116411Sphk.LP 907116411SphkIn order to show that timestamping does not necessarily have to 908116411Sphkbe done using unpredictable and uncalibratable interrupts, an 909116411Sphkarray of latches were implemented as well, which allow up to 10 910116411Sphkexternal signals to latch the reading of the counter when 911116411Sphkan external PPS signal transitions from logic high to logic 912116411Sphklow or vice versa. 913116411Sphk.LP 914116411SphkUsing this setup, a standard 133 MHz Pentium based PC is able to 915116411Sphktimestamp the PPS output of the Motorola UT+ GPS receiver with 916116411Sphka precision of \(+- 10 nanoseconds \(+- one count which in practice 917116411Sphkaverages out to roughly \(+- 15 nanoseconds\**: 918116411Sphk.FS 919116411SphkThe reason the plot does not show a very distinct 10 nanosecond 920116411Sphkquantization is that the GPS receiver produces the PPS signal from 921116411Sphka clock with a roughly 55 nanosecond period and then predicts in 922116411Sphkthe serial data stream how many nanoseconds this will be offset 923116411Sphkfrom the ideal time. 924116411SphkThis plot shows the timestamps corrected for this ``negative 925116411Sphksawtooth correction''. 926116411Sphk.FE 927116411Sphk.LP 928119760Sjkoshy.if t .PSPIC gps.ps 929116411Sphk.LP 930116411SphkIt shold be noted that the author is no hardware wizard and 931116411Sphka number of issues in the implementation results in less than 932116411Sphkideal noise performance. 933116411Sphk.LP 934116411SphkNow compare this to ``ideal'' timecounter to the normal setup 935116411Sphkwhere the PPS signal is used 936116411Sphkto trigger an interrupt via the DCD pin on a serial port, and 937116411Sphkthe interrupt handler calls \fCnanotime()\fP to timestamp 938116411Sphkthe external event \**: 939116411Sphk.FS 940116411SphkIn both cases, the computers clock frequency controlled 941116411Sphkwith a Rubidium Frequency standard. 942116411SphkThe average quality of crystals used for computers would 943116411Sphktotally obscure the curves due to their temperature coefficient. 944116411Sphk.FE 945116411Sphk.LP 946119760Sjkoshy.if t .PSPIC intr.ps 947116411Sphk.LP 948116411SphkIt is painfully obvious that the interrupt latency is the 949116411Sphkdominant noise factor in PPS timestamping in the second case. 950116411SphkThe asymetric distribution of the noise in the second plot 951116411Sphkalso more or less entirely invalidates the design assumption 952116411Sphkin the NTP PLL/FLL kernel code that timestamps are dominated 953116411Sphkby gaussian noise with few spikes. 954116411Sphk.SH 955116411SphkStatus and availability 956116411Sphk.PP 957116411SphkThe timecounter code has been developed and used in FreeBSD 958116411Sphkfor a number of years and has now reached maturity. 959116411SphkThe source-code is located almost entirely in the kernel source file 960116411Sphkkern_tc.c, with a few necessary adaptations in code which 961116411Sphkinterfaces to it, primarily the NTP PLL/FLL code. 962116411Sphk.LP 963116411SphkThe code runs on all FreeBSD platforms including i386, alpha, 964116411SphkPC98, sparc64, ia64 and s/390 and contains no wordsize or 965116411Sphkendianess issues not specifically handled in the sourcecode. 966116411Sphk.LP 967116411SphkThe timecounter implementation is distributed under the ``BSD'' 968116411Sphkopen source license or the even more free ``Beer-ware'' license. 969116411Sphk.LP 970116411SphkWhile the ability to accurately model and compensate for 971116411Sphkinaccuracies typical of atomic frequency standards are not 972116411Sphkcatering to the larger userbase, but this ability and precision 973116411Sphkof the code guarntees solid support for the widespread deployment 974116411Sphkof NTP as a time synchronization protocol, without rounding 975116411Sphkor accumulative errors. 976116411Sphk.LP 977116411SphkAdding support for new hardware and platforms have been 978116411Sphkdone several times by other developers without any input from the 979116411Sphkauthor, so this particular aspect of timecounters design 980116411Sphkseems to work very well. 981116411Sphk.SH 982116411SphkFuture work 983116411Sphk.PP 984116411SphkAt this point in time, no specific plans exist for further 985116411Sphkdevelopment of the timecounters code. 986116411Sphk.LP 987116411SphkVarious micro-optimizations, mostly to compensate for inadequate 988116411Sphkcompiler optimization could be contemplated, but the author 989116411Sphkresists these on the basis that they significantly decrease 990116411Sphkthe readability of the source code. 991116411Sphk.SH 992116411SphkAcknowledgements 993116411Sphk.PP 994116411Sphk.EQ 995116411Sphkdelim �� 996116411Sphk.EN 997116411SphkThe author would like to thank: 998116411Sphk.LP 999116411SphkBruce Evans 1000116411Sphkfor his invaluable assistance 1001116411Sphkin taming the evil i8254 timecounter, as well as the enthusiastic 1002116411Sphkresistance he has provided throughout. 1003116411Sphk.PP 1004116411SphkProfessor Dave Mills of University of Delaware for his work on 1005116411SphkNTP, for lending out the neglected twin Loran-C receiver and for 1006116411Sphkpicking up the glove when timecounters made it clear 1007116411Sphkthat the old ``microkernel'' NTP timekeeping code were not up to snuff 1008116411Sphk[MILLS2000B]. 1009116411Sphk.PP 1010116411SphkTom Van Baak for helping out, despite the best efforts of the National 1011116411SphkDanish Posts center for Customs and Dues to prevent it. 1012116411Sphk.PP 1013116411SphkCorby Dawson for helping with the care and feeding for caesium standards. 1014116411Sphk.PP 1015116411SphkThe staff at the NELS Loran-C control station in B�, Norway for providing 1016116411Sphkinformation about step-changes. 1017116411Sphk.PP 1018116411SphkThe staff at NELS Loran-C station Ei�e, Faeroe 1019116411SphkIslands for permission to tour their installation. 1020116411Sphk.PP 1021116411SphkThe FreeBSD users for putting up with ``micro uptime went backwards''. 1022116411Sphk.SH 1023116411SphkReferences 1024116411Sphk.LP 1025116411Sphk[AG2002] 1026116411SphkPublished specifications for Agilent model 5071A Primary Frequency 1027116411SphkStandard on 1028116411Sphk.br 1029116411Sphkhttp://www.agilent.com 1030116411Sphk.LP 1031116411Sphk[DMK2001] 1032116411Sphk"Accuracy Evaluation of a Cesium Fountain Primary Frequency Standard at NIST." 1033116411SphkD. M. Meekhof, S. R. Jefferts, M. Stephanovic, and T. E. Parker 1034116411SphkIEEE Transactions on instrumentation and measurement, VOL. 50, NO. 2, 1035116411SphkAPRIL 2001. 1036116411Sphk.LP 1037116411Sphk[PHK2001] 1038116411Sphk"Monitoring Natural Gas Usage" 1039116411SphkPoul-Henning Kamp 1040116411Sphkhttp://phk.freebsd.dk/Gasdims/ 1041116411Sphk.LP 1042116411Sphk[MILLS1992] 1043116411Sphk"A computer-controlled LORAN-C receiver for precision timekeeping." 1044116411SphkMills, D.L. 1045116411SphkElectrical Engineering Department Report 92-3-1, University of Delaware, March 1992, 63 pp. 1046116411Sphk.LP 1047116411Sphk[MILLS2000A] 1048116411SphkLevine, 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. 1049116411Sphk.LP 1050116411Sphk[MILLS2000B] 1051116411Sphk"The nanokernel." 1052116411SphkMills, D.L., and P.-H. Kamp. 1053116411SphkProc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting (Reston VA, November 2000), 423-430. 1054116411Sphk.LP 1055116411Sphk[RGO2002] 1056116411SphkFor an introduction to Harrison and his clocks, see for 1057116411Sphkinstance 1058116411Sphk.br 1059116411Sphkhttp://www.rog.nmm.ac.uk/museum/harrison/ 1060116411Sphk.br 1061116411Sphkor for 1062116411Sphka more detailed and possibly better researched account: Dava 1063116411SphkSobels excellent book, "Longitude: The True Story of a Lone 1064116411SphkGenius Who Solved the Greatest Scientific Problem of His 1065116411SphkTime" Penguin USA (Paper); ISBN: 0140258795. 1066116411Sphk.LP 1067116411Sphk[SAGE] 1068126182SphkThis ``gee-wiz'' kind of article in Dr. Dobbs Journal is a good place to 1069116411Sphkstart: 1070116411Sphk.br 1071116411Sphkhttp://www.ddj.com/documents/s=1493/ddj0001hc/0085a.htm 1072116411Sphk.LP 1073116411Sphk[VCC2002] 1074116411SphkPlease consult Virtual Computer Corporations homepage: 1075116411Sphk.br 1076116411Sphkhttp://www.vcc.com 1077