Counting on the time stamp counter
The TSC can also be read quickly (it is just a CPU register, after all), making it of interest for system timekeeping. There are a lot of applications which check the current time frequently, to the point that gettimeofday() is one of the most performance-critical system calls in Linux. By using the TSC to interpolate within the resolution of a coarser clock, the system can give accurate, high-resolution time without taking a lot of time in the process.
That is the idea, anyway. In practice, the TSC turns out to be hard to use in this way. If the CPU frequency changes (as it will on CPUs which can vary their power consumption), the TSC rate will change as well. If the processor is halted (as can happen when it goes idle), the TSC may stop altogether. On multiprocessor systems, the TSCs on different processors may drift away from each other over time - leading to a situation where a process could read a time on one CPU, move to a second processor, and encounter a time earlier than the one it read on the first processor.
These challenges notwithstanding, the Linux kernel tries to make the best use of the TSC possible. The code which deals with the TSC contains a number of checks to try to detect situations where TSC-based time might not be reliable. One of those checks, in particular, compares TSC time against the jiffies count, which is incremented by way of the timer tick. If, after ten seconds' worth of ticks, the number of TSC cycles seen differs from what would have been expected, the kernel concludes that the TSC is not stable and stops using it for time information.
Interesting things happen when the dynamic tick patch is thrown into the mix. With dynamic ticks, the periodic timer interrupt is turned off whenever there's nothing to be done in the near future, allowing the processor to remain idle for longer and consume less power. Once something happens, however, the jiffies count must be updated to reflect the timer ticks which were missed - something which is generally done by obtaining the time from another source. At best, this series of events defeats the test which ensures that the TSC is operating in a stable manner; at worst, it can lead to corrupted system time. Not a good state of affairs.
For this reason, the recently-updated high-resolution timers and dynamic tick patch set includes a change which disables use of the TSC. It seems that the high-resolution timers and dynamic tick features are incompatible with the TSC - and that people configuring kernels must choose between the two. Since the TSC does have real performance benefits, disabling it has predictably made some people unhappy, to the point that some would prefer to see the timer patches remain out of the kernel for now.
In response to the objections, Ingo Molnar has explained things this way:
Ingo has also posted a test program which demonstrates that time inconsistencies on TSC-based systems are common - at least, when multiple processors are in use.
Arjan van de Ven has suggested a "duct tape" solution which might work well enough "to keep the illusion alive." It involves setting up offsets and multipliers for each processor's TSC. Between the offsets (which could compensate for TSC drift between processors) and the multipliers (which adjust for frequency changes), some semblance of synchronized and accurate TSC-based time could be maintained - as long as the kernel is able to detect TSC-related events and adjust those values accordingly. No code which implements this idea has yet been posted, however.
The conversation faded out with no real conclusion, though, near the end,
Thomas Gleixner did note that the complete
disabling of the TSC was "overkill." The preferred solution, which he is
working on, is to keep the system from going into the dynamic tick mode if
there is no other reliable timer available. Once that code has been
posted, it may be possible to have the full set: high-resolution timers,
dynamic ticks, and fast clocks using the TSC.
| Index entries for this article | |
|---|---|
| Kernel | Timekeeping |
| Kernel | TSC |
Posted Nov 16, 2006 3:23 UTC (Thu)
by jreiser (subscriber, #11027)
[Link] (1 responses)
This theory has never been correct for x86 processors. The minimum cost for rdtsc was 9 cycles in a PentiumMMX-166MHz. On a Pentium4Xeon-3.0GHz it takes 97 cycles. The conclusion? The hardware reads TSC serially one bit at a time, or one byte at a time on old processors.
Posted Nov 16, 2006 4:41 UTC (Thu)
by PaulMcKenney (✭ supporter ✭, #9624)
[Link]
Posted Nov 16, 2006 6:26 UTC (Thu)
by pjm (guest, #2080)
[Link] (4 responses)
[Dropping that part of rule 3 would more often expose callers mistakenly assuming that time strictly increases. Exposing bugs more often may be either a good or bad thing.]
Posted Nov 17, 2006 5:10 UTC (Fri)
by zooko (guest, #2589)
[Link] (3 responses)
Unfortunately Unix and Linux haven't traditionally offered the former to user-land programmers (although I'm told that Linux kernel code itself has long required monotonic timers for some things).
The current state of the art appears to be an ill-considered belief that you can have most of both most of the time (possibly because there is a human sysadmin finessing the difference for you) and and that the occasional violation of one or both of those requirements probably won't hurt too much. Bah. I hate that kind of irresponsible engineering.
("Occasional incorrectness won't hurt too much" thinking can often get by for years -- until a malicious actor gets involved who knows how to cause or to exploit this occasional incorrectness. In any case occasional incorrectness can occasionally cause planes to crash, precious documents to be deleted, etc.)
I believe that recent modern Linux and glibc do offer a monotonically increasing timer (i.e. implementing CLOCK_MONOTONIC for clock_gettime()). Now if only programmers will come to realize that they sometimes need it...
(P.S. An even more subtle and vexing problem is that you cannot have both monotonicity *and* "the rate of the passage of time correlates with a standard notion of the rate of time".)
Posted Nov 17, 2006 23:09 UTC (Fri)
by giraffedata (guest, #1954)
[Link] (2 responses)
Can you elaborate? I think you're saying that if I want a clock that correlates to UTC, it must necessarily step backwards sometimes. I don't see why.
Posted Nov 29, 2006 12:37 UTC (Wed)
by robbe (guest, #16131)
[Link] (1 responses)
See http://en.wikipedia.org/wiki/Coordinated_Universal_Time
Posted Nov 29, 2006 17:19 UTC (Wed)
by giraffedata (guest, #1954)
[Link]
Ah. That's probably it.
Except that UTC does not stand still or go backwards. When there's a leap second, UTC goes steadily forward from 23:59:59 to 23:59:60 and then to 00:00:00. Note that a UTC time of day is a tuple of numbers (year, month, day, hour, minute, second).
But the standard Linux time representation (a single number) does step backward at leap second time; it's defined that way to make it easy to compute UTC from it.
And I think zooko's statement that a programmer can't have a time that is both monotonically nondecreasing and correlates to a human time standard has to be qualified to the case that the time is represented by a single number. As long as you're willing to work with multiple numbers, two obvious ways are TAI + delta as you suggest, and just plain UTC.
Posted Nov 16, 2006 13:13 UTC (Thu)
by rvfh (guest, #31018)
[Link] (1 responses)
I hope they fix the bug that soft locks my kernel for 2 minutes
when somebody contacts me via Skype in the process (Skype
forums and LKML), as someone said it
was potentially HPET/TSC related. This DoS attack does not seem to be of much interest to kernel
developers
though, so I won't hold my breath! I guess that puts me in the 1/5th who
are impacted by a kernel bug then...
Posted Nov 17, 2006 7:04 UTC (Fri)
by rise (guest, #5045)
[Link]
Posted Nov 16, 2006 13:48 UTC (Thu)
by brugolsky (guest, #28)
[Link]
Linux timekeeping has always been a black art, and until John Stultz's rewrite, seemed to me to proceed from the wrong direction. At least now it looks comprehensible.
Do other kernels (*BSD, Solaris) take a markedly different approach?
There does seem to be some work going on to make the TSC more useful on SMP systems, e.g., [PATCH 1/2] Make the TSC safe to be used by gettimeofday().
The TSC can also be read quickly (it is just a CPU register, after all) ...
Counting on the time stamp counter
The rumor I hear is that reading TSC does some degree of instruction-stream serialization. Someone from Intel or AMD might be able to shed better light on the performance of rdtsc.Counting on the time stamp counter
One way of guaranteeing that ‘time never goes backwards’ is to use a variant of Lamport timestamps (or see full paper). For gettimeofday, we have it a bit easier: gettimeofday gives only microsecond precision, so it only guarantees that time never goes backwards, it doesn't guarantee that time advances between two events. Thus, we don't even need the property that distinct events have distinct timestamps, so we don't need the process ID stuff mentioned on that page, and we could go so far as to ~gratuitously drop the “and then applies rule 1 before timestamping the event as received” part from rule 3.
How to ensure monotonic nondecreasing time
Programmers need to realize that they cannot have both monotonically non-decreasing (or monotonically increasing) *and* "correlates to shared human date-time e.g. UTC". Sometimes you require the latter and can live without the former. Sometimes it is the other way around.How to ensure monotonic nondecreasing time
How to ensure monotonic nondecreasing time
Programmers need to realize that they cannot have both monotonically non-decreasing (or monotonically increasing) *and* "correlates to shared human date-time e.g. UTC".
I guess zooko allured to leap seconds, where UTC stands still for How to ensure monotonic nondecreasing time
(acually: jumps backwards by) a second. Maybe keeping TAI and the current
delta is the answer to this one?
How to ensure monotonic nondecreasing time
I guess zooko alluded to leap seconds, where UTC stands still for
(actually: jumps backwards by) a second.
Counting on the time stamp counter
Interesting, I've been seeing soft-locks for months as well. Oddly enough though almost nothing else responds on my laptop (basically only the keyboard lamp), toggling volume up and down will sometimes pop it out of lockup immediately.Counting on the time stamp counter
It is quite remarkable just how many clocks are in a typical PC, all of which have serious drawbacks. Vojtech Pavlik provided a nice summary a while back:
What do other platforms do?