LWN: Comments on "Counting on the time stamp counter"

How to ensure monotonic nondecreasing time

giraffedata — 2006-11-29T17:19:41+00:00

I guess zooko alluded to leap seconds, where UTC stands still for (actually: jumps backwards by) a second.

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.

How to ensure monotonic nondecreasing time

robbe — 2006-11-29T12:37:39+00:00

I guess zooko allured to leap seconds, where UTC stands still for
(acually: jumps backwards by) a second. Maybe keeping TAI and the current
delta is the answer to this one?

See http://en.wikipedia.org/wiki/Coordinated_Universal_Time

How to ensure monotonic nondecreasing time

giraffedata — 2006-11-17T23:09:01+00:00

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".

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.

Counting on the time stamp counter

rise — 2006-11-17T07:04:05+00:00

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.

How to ensure monotonic nondecreasing time

zooko — 2006-11-17T05:10:27+00:00

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.

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".)

What do other platforms do?

brugolsky — 2006-11-16T13:48:49+00:00

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:

RTC: 0.5 sec resolution, interrupts
PIT: takes ages to read, overflows at each timer interrupt
PMTMR: takes ages to read, overflows in approx 4 seconds, no interrupt
HPET: slow to read, overflows in 5 minutes. Nice, but usually not present.
TSC: fast, completely unreliable. Frequency changes, CPUs diverge over time.
LAPIC: reasonably fast, unreliable, per-cpu

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().

Counting on the time stamp counter

rvfh — 2006-11-16T13:13:25+00:00

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...

How to ensure monotonic nondecreasing time

pjm — 2006-11-16T06:26:33+00:00

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.

[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.]

Counting on the time stamp counter

PaulMcKenney — 2006-11-16T04:41:36+00:00

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

jreiser — 2006-11-16T03:23:59+00:00

The TSC can also be read quickly (it is just a CPU register, after all) ...

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.