Time precision, adjtime(x) vs. gettimeofday

Hi !

While fixing problems experienced by some scientific users who found out that gettimeofday() could sometimes run backward, I found a nasty issue I don't know if we can fix at all or if it's not worth bothering.

So the problem is with any arch (ppc, x86, ...) who uses a HW timer (like the CPU timebase on PPC) to provide better-than-jiffy precision in do_gettimeofday().

The problem is that the offset added to xtime value (typically the HW timer current value minus the HW timer value at the last timer interrupt scaled to usec) uses a scaling factor which has been calibrated once, and doesn't take into account the adjustements done to xtime increase by adjtime/adjtimex algorithm.

That means that if, for example, adjtimex was called with a factor that is trying to slow you down a bit, and you call gettimeofday right before the end of a jiffy period, you may calculate an offset based on the HW timer that is actually higher than what will be really added to xtime on the next interrupt.

So you can end-up returning non-monotonic values from gettimeofday().

I don't see a way to fix that that wouldn't bloat do_gettimeofday(), except if we can, at jiffy interrupt time, pre-calculate a scaling factor for the next jiffy and just apply it on the HW timer value on the next calls to do_gettimeofday(). But that option would need better understanding of the adjtime(x) algorithm that what I have at this point.

Storing the last value to make sure we don't return a value that is lower will defeat the read_lock/write_lock mecanism, forcing us to take the write_lock(), and thus screwing up scalability.

Any idea ?

Note: In addition to the above, there seem to be a race on x86 2.4 (only, 2.6 doesn't have it) due to the fact that the actual xtime increase is done from a bottom half. The HW timer "last stamp" is stored from the HW interrupt, xtime is only updated on the BH, so if gettimeofday is called in between those 2, you'll end up using the "new" "last stamp" with the old xtime, thus returning an incorrect value. A fix we use on PPC is to use

jiffies - wall_jiffies

As an additional correction.

Ben.

	Hi!,

Well, it it affects gettimeofday which has a precision of 1 part in 10000 (100 ppm), it means that our boot time timebase calibration was not very good to start with, on my set of running VME machines I have the following (values in ppm):

$cat /nfsroots/v*/etc/ntp/drift
-10.191
-2.787
3.869
-5.645
-1.146
-7.383
4.400
5.824
4.640
0.014
-8.371
0.056
-2.324
-5.655
-5.828
-4.862
-3.380

I can understand that we'll certainly have more serious problems of non-monotonicity for nanosecond precision timestamps.

I also have from time to time a bad timebase calibration at boot which makes the drift go to about 400ppm. I just don't have this problem on any machine right now. I believed I mentioned this issue once on the list but never found time to track it.

Maybe the boot-time timebase calibration could use a longer period. However, I'd first like to know by how much the timebase calibration of the user which has the problem varies between reboots.

As I said, only if you have fairly large corrections. Anything below

AFAIR, this correction is also done on x86.

Regards,
Gabriel

Boot time calibration can't be perfect... I depends very much on the quality of what your are calibrating against, and the bus path to it.

On most pmacs, I'm calibrating either against a VIA timer which isn't _that_ good or on OF value (which are themselves calibrated, I think, against the KeyLargo timer).

On all cases, those will drift some way from what the NTP server will give, either a lot or not, it will. So we may end up adjusting our kernel rate and thus opening a window for the problem.

Ben.

No, indeed.

At the time you it is performed, most devices should not be active (no long DMA bursts) so the variations should be rather small. Another solution is to increase the measurement period. I have to use one second on some machines because I don't have anything else reliable (only the RTC which changes every second and its interrupt pin is not routed), even a 1 to 2 second delay does not significantly affect boot times.

On the Macs I have around here, the ntp drift values are:
- on a PB G3/400: +8ppm
- on a PM G4/466: -6ppm

that's not _that_ bad (I believe these come from OF).

10 ppm of a 10ms jiffy is 0.1 microseconds. Increasing HZ can only improve this figure, although it is stupid to run the correction loop that often IMNSHO.

I repeat the question: what are the values of drift on the machines that encounter the problem ? Is this drift stable or unstable?

The worst variations of drift I've seen are a few ppm for a given machine, barring the occasional boot-time calibration problems that I have encountered.

Gabriel

So far, there is no problem. The problem that was happening was a via_calibrate_decr() bug with HZ != 100, but when investigating, I figured out that we had a potential problem there, that's all and that's why I want people like you who know those problems well to state if it's worth bothering ;)

OK.

The following will prevent adjtime from causing time regression. It delays starting the adjtime mechanism for one tick, and keeps gettimeofday inside the window.

Only fixes i386, but changes to other arch would be similar.

Running a simple clock test program and playing with adjtime demonstrates that this fixes the problem (and 2.6.0-test6 is broken).
But given the fragile nature of the timer code, it should go through some more testing before inclusion. Andrew could you put this in the next -mm tree?

diff -Nru a/arch/i386/kernel/time.c b/arch/i386/kernel/time.c
@@ -102,6 +102,15 @@
 		lost = jiffies - wall_jiffies;
 		if (lost)
 			usec += lost * (1000000 / HZ);
+
+		/*
+		 * If time_adjust is negative then NTP is slowing the clock
+		 * so make sure not to go into next possible interval.
+		 * Better to lose some accuracy than have time go backwards..
+		 */
+		if (unlikely(time_adjust < 0) && usec > tickadj)
+			usec = tickadj;
+
 		sec = xtime.tv_sec;
 		usec += (xtime.tv_nsec / 1000);
 	} while (read_seqretry(&xtime_lock, seq));

diff -Nru a/include/linux/timex.h b/include/linux/timex.h
@@ -302,6 +302,7 @@
 extern long time_reftime;	/* time at last adjustment (s) */
 
 extern long time_adjust;	/* The amount of adjtime left */
+extern long time_next_adjust;	/* Value for time_adjust at next tick */
 
 /* interface variables pps->timer interrupt */
 extern long pps_offset;		/* pps time offset (us) */

diff -Nru a/kernel/time.c b/kernel/time.c
@@ -233,7 +233,7 @@
 	result = time_state;	/* mostly `TIME_OK' */
 
 	/* Save for later - semantics of adjtime is to return old value */
-	save_adjust = time_adjust;
+	save_adjust = time_next_adjust ? time_next_adjust : time_adjust;
 
 #if 0	/* STA_CLOCKERR is never set yet */
 	time_status &= ~STA_CLOCKERR;		/* reset STA_CLOCKERR */

@@ -280,7 +280,8 @@
 	    if (txc->modes & ADJ_OFFSET) {	/* values checked earlier */
 		if (txc->modes == ADJ_OFFSET_SINGLESHOT) {
 		    /* adjtime() is independent from ntp_adjtime() */
-		    time_adjust = txc->offset;
+		    if ((time_next_adjust = txc->offset) == 0)
+			 time_adjust = 0;
 		}
 		else if ( time_status & (STA_PLL | STA_PPSTIME) ) {
 		    ltemp = (time_status & (STA_PPSTIME | STA_PPSSIGNAL)) ==

diff -Nru a/kernel/timer.c b/kernel/timer.c
@@ -463,6 +463,7 @@
 long time_adj;				/* tick adjust (scaled 1 / HZ)	*/
 long time_reftime;			/* time at last adjustment (s)	*/
 long time_adjust;
+long time_next_adjust;
 
 /*
  * this routine handles the overflow of the microsecond field

@@ -643,6 +644,12 @@
 	}
 	xtime.tv_nsec += delta_nsec;
 	time_interpolator_update(delta_nsec);
+
+	/* Changes by adjtime() do not take effect till next tick. */
+	if (time_next_adjust != 0) {
+		time_adjust = time_next_adjust;
+		time_next_adjust = 0;
+	}
 }
 
 /*

I like that solution. There is still a possible small issue in 2.4 but I don't think we need to care about it (see below)

Note about the 2.4 SMP race I talked about, x86 is indeed safe, as it also uses (jiffies - wall_jiffies) to adjust the offset, I missed it at first as it's not done from the do_gettimeoffset() function where I was looking for it.

However, that that means we may apply more than one jiffie to xtime at once, thus the above workaround would still have a small hole. But since that happens only with insane interrupt latencies that I don't expect to see in real life, it's probably a non-issue.

2.6 should always have jiffies and wall_jiffies in perfect sync as they are manipulated within the same write_lock block.

Ben.

[snip]

Hmm. Looks good to me. If we're losing ticks, it would make time stair-step somewhat, but it doesn't seem to affect the actual time accumulation.

thanks
-john

Hi!

Having time run backward is not really an option; screensavers start kicking randomly, make has problems, etc, etc.
Pavel

When do you have a heart between your knees?
[Johanka's followup: and *two* hearts?]