gettimeofday resolution seriously degraded in test9

gettimeofday resolution seriously degraded in test9

[Joe Korty]

[ 2nd posting, the first seems to have been lost ]

Linus,
 This bit of -test9 code reduces the resolution of gettimeofday(2) from
1 microsecond to 1 millisecond whenever a negative time adjustment is
in progress.  This seriously damages efforts to measure time intervals
accurately with gettimeofday.  Please consider backing it out.

Joe


diff -Nura linux-2.6.0-test8/arch/i386/kernel/time.c linux-2.6.0-test9/arch/i386/kernel/time.c
--- linux-2.6.0-test8/arch/i386/kernel/time.c	2003-10-17 17:43:11.000000000 -0400
+++ linux-2.6.0-test9/arch/i386/kernel/time.c	2003-10-25 14:43:37.000000000 -0400
@@ -104,6 +104,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));

Re: gettimeofday resolution seriously degraded in test9

[Stephen Hemminger]

On Mon, 27 Oct 2003 18:44:47 -0500
Joe Korty <joe.korty@ccur.com> wrote:

> [ 2nd posting, the first seems to have been lost ]
> 
> Linus,
>  This bit of -test9 code reduces the resolution of gettimeofday(2) from
> 1 microsecond to 1 millisecond whenever a negative time adjustment is
> in progress.  This seriously damages efforts to measure time intervals
> accurately with gettimeofday.  Please consider backing it out.
> 
> Joe

The problem is that it is worse to have time go backwards which is what we
have done up until test9. It might be possible to compress time when NTP is doing
negative adjustments, but if you really care about microsecond resolution then
you will still lose. 

If you care about microseconds, then NTP is going to whack your data.  It has to
cause clock to speed up/slow down.  Your data points will skip and stall due to it.
Use a different clock source or don't run NTP if you are doing real time stuff.

Re: gettimeofday resolution seriously degraded in test9

[john stultz]

On Mon, 2003-10-27 at 15:44, Joe Korty wrote:
> [ 2nd posting, the first seems to have been lost ]
> 
> Linus,
>  This bit of -test9 code reduces the resolution of gettimeofday(2) from
> 1 microsecond to 1 millisecond whenever a negative time adjustment is
> in progress.  This seriously damages efforts to measure time intervals
> accurately with gettimeofday.  Please consider backing it out.
> 
> Joe
> 
> 
> diff -Nura linux-2.6.0-test8/arch/i386/kernel/time.c linux-2.6.0-test9/arch/i386/kernel/time.c
> --- linux-2.6.0-test8/arch/i386/kernel/time.c	2003-10-17 17:43:11.000000000 -0400
> +++ linux-2.6.0-test9/arch/i386/kernel/time.c	2003-10-25 14:43:37.000000000 -0400
> @@ -104,6 +104,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));
> 

Hmm. This is the stair-step effect of capping time for NTP adjustments.
The side effect was expected, but I didn't figure it would be so drastic
as NTP adjustments are supposedly limited to 10%. Do you not see time
inconsistencies when running without this patch?

Stephen, any thoughts?  

thanks
-john

Re: gettimeofday resolution seriously degraded in test9

[Stephen Hemminger]

Arghh... the patch was being way more agressive than necessary.  
tickadj which limits NTP is always 1 (for HZ=1000) so NTP will change
at most 1 us per clock tick.  This meant we only had to stop time
for the last us of the interval.


diff -Nru a/arch/i386/kernel/time.c b/arch/i386/kernel/time.c
--- a/arch/i386/kernel/time.c	Mon Oct 27 17:13:22 2003
+++ b/arch/i386/kernel/time.c	Mon Oct 27 17:13:22 2003
@@ -110,8 +110,9 @@
 		 * 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;
+		if (unlikely(time_adjust < 0) && 
+		    unlikely(usec > tick_usec - tickadj)) 
+			usec = tick_usec - tickadj;
 
 		sec = xtime.tv_sec;
 		usec += (xtime.tv_nsec / 1000);

Re: gettimeofday resolution seriously degraded in test9

[Gabriel Paubert]

On Mon, Oct 27, 2003 at 05:17:38PM -0800, Stephen Hemminger wrote:
> Arghh... the patch was being way more agressive than necessary.  
> tickadj which limits NTP is always 1 (for HZ=1000) so NTP will change
> at most 1 us per clock tick.  This meant we only had to stop time
> for the last us of the interval.

Hmm, I still don't like it. What does it do to timestamping in
interrupts in the kernel, especially when there is a burst of
interrupts?

If I read it correctly, the time will be frozen between the time
the timer interrupt should have arrived and the time it is processed.
So the last micosecond of the interval could extend well into the next
interval, or do I miss something (I also suspect that it could
make PPSKit behave strangely for this reason)?

> 
> 
> diff -Nru a/arch/i386/kernel/time.c b/arch/i386/kernel/time.c
> --- a/arch/i386/kernel/time.c	Mon Oct 27 17:13:22 2003
> +++ b/arch/i386/kernel/time.c	Mon Oct 27 17:13:22 2003
> @@ -110,8 +110,9 @@
>  		 * 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;
> +		if (unlikely(time_adjust < 0) && 
> +		    unlikely(usec > tick_usec - tickadj)) 
> +			usec = tick_usec - tickadj;

So wouldn't it be better to put:
			usec = max(usec, tick_usec)-tickadj;
to freeze the time for only a few microseconds even for kernel clients
of gettimeofday() when the timer interrupt comes a bit late?

Now if you are looking at the microsecond level of precision, there is 
something else in which is worth considering as commented in the
appended patch. In short, I consider "do it first because it's faster 
to be a bogus argument", rather do it in the order which should
minimize the jitter of the measurements (outb and inb have enough
serialization that no other synchronization should be necessary).

I'm not sure that it will result in easily measurable improvements. 
But it should not hurt either.

The same could be applied to other timer in the file (HPET) and other files 
but I don't have any machines on which I can test these, and ensuring
that the instruction are executed in the right order is a bit more
difficult than with inb and outbs.

	Regards,
	Gabriel

===== arch/i386/kernel/timers/timer_tsc.c 1.29 vs edited =====
--- 1.29/arch/i386/kernel/timers/timer_tsc.c	Fri Oct 10 23:01:24 2003
+++ edited/arch/i386/kernel/timers/timer_tsc.c	Tue Oct 28 11:04:28 2003
@@ -165,8 +165,10 @@
 	last_offset = ((unsigned long long)last_tsc_high<<32)|last_tsc_low;
 	/*
 	 * It is important that these two operations happen almost at
-	 * the same time. We do the RDTSC stuff first, since it's
-	 * faster. To avoid any inconsistencies, we need interrupts
+	 * the same time. The delay of acquiring the spinlock and
+	 * accessing the PIT may be large, especially if the bus is busy
+	 * with DMA transactions, so the rdtsc is done after to limit 
+	 * jitter. To avoid any inconsistencies, we need interrupts
 	 * disabled locally.
 	 */
 
@@ -175,15 +177,16 @@
 	 * has the SA_INTERRUPT flag set. -arca
 	 */
 	
-	/* read Pentium cycle counter */
-
-	rdtsc(last_tsc_low, last_tsc_high);
-
 	spin_lock(&i8253_lock);
 	outb_p(0x00, PIT_MODE);     /* latch the count ASAP */
 
 	count = inb_p(PIT_CH0);    /* read the latched count */
 	count |= inb(PIT_CH0) << 8;
+
+	/* read Pentium cycle counter */
+
+	rdtsc(last_tsc_low, last_tsc_high);
+
 	spin_unlock(&i8253_lock);
 
 	if (pit_latch_buggy) {

Re: gettimeofday resolution seriously degraded in test9

[Stephen Hemminger]

On Tue, 28 Oct 2003 12:55:58 +0100
Gabriel Paubert <paubert@iram.es> wrote:

> On Mon, Oct 27, 2003 at 05:17:38PM -0800, Stephen Hemminger wrote:
> > Arghh... the patch was being way more agressive than necessary.  
> > tickadj which limits NTP is always 1 (for HZ=1000) so NTP will change
> > at most 1 us per clock tick.  This meant we only had to stop time
> > for the last us of the interval.
> 
> Hmm, I still don't like it. What does it do to timestamping in
> interrupts in the kernel, especially when there is a burst of
> interrupts?
> 
> If I read it correctly, the time will be frozen between the time
> the timer interrupt should have arrived and the time it is processed.
> So the last micosecond of the interval could extend well into the next
> interval, or do I miss something (I also suspect that it could
> make PPSKit behave strangely for this reason)?

The original problem all this is solving is that when NTP is slowing the clock
there existed real cases where time appeared to go backwards. Assuming NTP was
slowing the clock, then it would update the xtime by 999us at the next timer interrupt.
If a program read time three times:

A:	    xtime = t0
B: A+1000   xtime = t0 + 1000
C: B+1	    xtime = t0 + 999

To behave correctly C > B > A; but we were returning C < B

The code does have bug if we are losing clock interrupts.  The test for
lost interrupts needs to be after the interval clamp.

This should work better. Patch against 2.6.0-test9

diff -Nru a/arch/i386/kernel/time.c b/arch/i386/kernel/time.c
--- a/arch/i386/kernel/time.c	Tue Oct 28 10:08:52 2003
+++ b/arch/i386/kernel/time.c	Tue Oct 28 10:08:52 2003
@@ -94,6 +94,7 @@
 {
 	unsigned long seq;
 	unsigned long usec, sec;
+	unsigned long max_ntp_tick = tick_usec - tickadj;
 
 	do {
 		unsigned long lost;
@@ -102,16 +103,20 @@
 
 		usec = cur_timer->get_offset();
 		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;
+		if (unlikely(time_adjust < 0)) {
+			usec = min(usec, max_ntp_tick);
+
+			if (lost)
+				usec += lost * max_ntp_tick;
+		} 
+		else if (unlikely(lost))
+			usec += lost * tick_usec;
 
 		sec = xtime.tv_sec;
 		usec += (xtime.tv_nsec / 1000);

Re: gettimeofday resolution seriously degraded in test9

[Gabriel Paubert]

On Tue, Oct 28, 2003 at 10:21:20AM -0800, Stephen Hemminger wrote:
> On Tue, 28 Oct 2003 12:55:58 +0100
> Gabriel Paubert <paubert@iram.es> wrote:
> 
> > On Mon, Oct 27, 2003 at 05:17:38PM -0800, Stephen Hemminger wrote:
> > > Arghh... the patch was being way more agressive than necessary.  
> > > tickadj which limits NTP is always 1 (for HZ=1000) so NTP will change
> > > at most 1 us per clock tick.  This meant we only had to stop time
> > > for the last us of the interval.
> > 
> > Hmm, I still don't like it. What does it do to timestamping in
> > interrupts in the kernel, especially when there is a burst of
> > interrupts?
> > 
> > If I read it correctly, the time will be frozen between the time
> > the timer interrupt should have arrived and the time it is processed.
> > So the last micosecond of the interval could extend well into the next
> > interval, or do I miss something (I also suspect that it could
> > make PPSKit behave strangely for this reason)?
> 
> The original problem all this is solving is that when NTP is slowing the clock
> there existed real cases where time appeared to go backwards. Assuming NTP was
> slowing the clock, then it would update the xtime by 999us at the next timer interrupt.
> If a program read time three times:
> 
> A:	    xtime = t0
> B: A+1000   xtime = t0 + 1000
> C: B+1	    xtime = t0 + 999
> 
> To behave correctly C > B > A; but we were returning C < B

Well, it happens almost everyday when I come back to work
and wake my laptop up from sleep and starts receiving ntp packets
(broadcastclient mode). After a few minutes, I have a time adjustment
step of of typically a few hundred milliseconds either way. It's a
once per day event, but it happens.

But anyway, I understand your point. But by doing this you potentially 
cause another problem of fairly large steps in time for interrupt handlers 
that do timestamping.

Consider the following:

- t-2: interrupt A arrives and starts being serviced
- t-1: interrupt B arrives but delayed in the APIC
- t: timer interrupt arrives (it is delayed too)
- t+x1: return from interrupt A
- t+x2: interrupt B serviced
- gettimeofday for time stamping, the returned value will actually 
  be frozen at t-1 for HZ=1000 or t-5 for HZ=100, while the actual
  time is t+something with something maybe up to a few tens of
  microseconds, instead of t+x2-1 or t+x2-5 which would be 
  clearly better.
- t+x3: timer interrupt, time steps suddenly now (or in
  the following BH, can't remember) from t-1 to the correct
  value, creating a fairly large discontinuity.

So what I'm asking you is to change the code so that the discontinuities
are minimized. That's quite important for some applications; actually
in my case the out-of-order gettimeofday don't matter as long as the
steps are small because I don't sample fast enough to be affected
by them, but getting the timestamp wrong by tens of microseconds is bad 
for evaluating the derivatives of the value read from a position encoder, 
as needed for servo loops for example.



> 
> The code does have bug if we are losing clock interrupts.  The test for
> lost interrupts needs to be after the interval clamp.

If we are really losing clock interrupts, we have more serious problems 
anyway (on x86 with classical 8253 timer, I don't know about other x86 
systems, only that PPC recovers from them rather well). This misnamed 
lost_jiffies variable is not the number of lost interrupts, but actually 
the number of jiffies for which the bottom half has not (yet) been 
performed.

> This should work better. Patch against 2.6.0-test9

Still unhappy...

	Gabriel

Re: gettimeofday resolution seriously degraded in test9

[Stephen Hemminger]

On Wed, 29 Oct 2003 11:07:45 +0100
Gabriel Paubert <paubert@iram.es> wrote:


> Consider the following:
> 
> - t-2: interrupt A arrives and starts being serviced
> - t-1: interrupt B arrives but delayed in the APIC
> - t: timer interrupt arrives (it is delayed too)
> - t+x1: return from interrupt A
> - t+x2: interrupt B serviced
> - gettimeofday for time stamping, the returned value will actually 
>   be frozen at t-1 for HZ=1000 or t-5 for HZ=100, while the actual
>   time is t+something with something maybe up to a few tens of
>   microseconds, instead of t+x2-1 or t+x2-5 which would be 
>   clearly better.
> - t+x3: timer interrupt, time steps suddenly now (or in
>   the following BH, can't remember) from t-1 to the correct
>   value, creating a fairly large discontinuity.
> 
> So what I'm asking you is to change the code so that the discontinuities
> are minimized. That's quite important for some applications; actually
> in my case the out-of-order gettimeofday don't matter as long as the
> steps are small because I don't sample fast enough to be affected
> by them, but getting the timestamp wrong by tens of microseconds is bad 
> for evaluating the derivatives of the value read from a position encoder, 
> as needed for servo loops for example.

The suggestion of using time interpolation (like ia64) would make the discontinuities
smaller, but still relying on fine grain gettimeofday for controlling servo loops
with NTP running seems risky. Perhaps what you want to use is the monotonic_clock
which gives better resolution (nanoseconds) and doesn't get hit by NTP. 

A bigger possible change would be for the timer->offset functions to return nanoseconds,
then the offset adjustment code could smooth it out. It would save a divide.

Re: gettimeofday resolution seriously degraded in test9

[Peter Chubb]

>>>>> "Stephen" == Stephen Hemminger <shemminger@osdl.org> writes:

Stephen> On Wed, 29 Oct 2003 11:07:45 +0100 Gabriel Paubert
Stephen> <paubert@iram.es> wrote:
>> for example.

Stephen> The suggestion of using time interpolation (like ia64) would
Stephen> make the discontinuities smaller, but still relying on fine
Stephen> grain gettimeofday for controlling servo loops with NTP
Stephen> running seems risky. Perhaps what you want to use is the
Stephen> monotonic_clock which gives better resolution (nanoseconds)
Stephen> and doesn't get hit by NTP.

monotonic_clock:
	-- isn't implemented for most architectures
	-- even for X86 only works for some timing sources
	-- and for the most common case is variable rate because of
	   power management functions changing the TSC clock rate.

As far as I know, there isn't a constant-rate monotonic clock
available at present for all architectures in the linux kernel.  The
nearest thing is scheduler_clock().

Peter C

Re: gettimeofday resolution seriously degraded in test9

[Gabriel Paubert]

On Wed, Oct 29, 2003 at 11:38:50AM -0800, Stephen Hemminger wrote:
> On Wed, 29 Oct 2003 11:07:45 +0100
> Gabriel Paubert <paubert@iram.es> wrote:
> 
> 
> > Consider the following:
> > 
> > - t-2: interrupt A arrives and starts being serviced
> > - t-1: interrupt B arrives but delayed in the APIC
> > - t: timer interrupt arrives (it is delayed too)
> > - t+x1: return from interrupt A
> > - t+x2: interrupt B serviced
> > - gettimeofday for time stamping, the returned value will actually 
> >   be frozen at t-1 for HZ=1000 or t-5 for HZ=100, while the actual
> >   time is t+something with something maybe up to a few tens of
> >   microseconds, instead of t+x2-1 or t+x2-5 which would be 
> >   clearly better.
> > - t+x3: timer interrupt, time steps suddenly now (or in
> >   the following BH, can't remember) from t-1 to the correct
> >   value, creating a fairly large discontinuity.
> > 
> > So what I'm asking you is to change the code so that the discontinuities
> > are minimized. That's quite important for some applications; actually
> > in my case the out-of-order gettimeofday don't matter as long as the
> > steps are small because I don't sample fast enough to be affected
> > by them, but getting the timestamp wrong by tens of microseconds is bad 
> > for evaluating the derivatives of the value read from a position encoder, 
> > as needed for servo loops for example.
> 
> The suggestion of using time interpolation (like ia64) would make the discontinuities
> smaller, but still relying on fine grain gettimeofday for controlling servo loops
> with NTP running seems risky. Perhaps what you want to use is the monotonic_clock
> which gives better resolution (nanoseconds) and doesn't get hit by NTP. 

When you control a telescope, you'll always have to go back to UT sooner
or later. Monotonic just does not cut it... And yes, I'm aware that the 
code will currently break around leap seconds, but I am still looking for 
a clean, not too bloated, solution to the problem.

Besides that I also need several machines to be synchronized for data
acquisition, and NTP provides me what I need (in the millisecond range),
monotonic can't. It is true that we have set things carefully up here:
we have our own redundant set of NTP stratum 0 (reference) clocks and 
everything which needs to be precisely synchronized is on a rather small 
LAN. Under these conditions what I have seen is that NTP steps the clock 
once at boot to set it, before I start any important program which might 
be affected by this, and then it never ever steps it again. The number 
of machines multiplied by the uptime is about 50 years now and counting, 
that's reliable enough for me.

> 
> A bigger possible change would be for the timer->offset functions to return nanoseconds,
> then the offset adjustment code could smooth it out. It would save a divide.

I believe that it is needed in the long term, but we'll see when 2.7 opens.

	Gabriel

Re: gettimeofday resolution seriously degraded in test9

[George Anzinger]

Peter Chubb wrote:
>>>>>>"Stephen" == Stephen Hemminger <shemminger@osdl.org> writes:
> 
> 
> Stephen> On Wed, 29 Oct 2003 11:07:45 +0100 Gabriel Paubert
> Stephen> <paubert@iram.es> wrote:
> 
>>>for example.
> 
> 
> Stephen> The suggestion of using time interpolation (like ia64) would
> Stephen> make the discontinuities smaller, but still relying on fine
> Stephen> grain gettimeofday for controlling servo loops with NTP
> Stephen> running seems risky. Perhaps what you want to use is the
> Stephen> monotonic_clock which gives better resolution (nanoseconds)
> Stephen> and doesn't get hit by NTP.
> 
> monotonic_clock:
> 	-- isn't implemented for most architectures
> 	-- even for X86 only works for some timing sources
> 	-- and for the most common case is variable rate because of
> 	   power management functions changing the TSC clock rate.
> 
> As far as I know, there isn't a constant-rate monotonic clock
> available at present for all architectures in the linux kernel.  The
> nearest thing is scheduler_clock().

What you want is the POSIX clocks and timers CLOCK_MONOTONIC which is available 
on all archs (as of 2.6).  The call is:

       cc [ flag ... ] file -lrt [ library ... ]

        #include <time.h>

        int clock_gettime(clockid_t which_clock, struct timespec *setting);

where you want "which_clock" to be CLOCK_MONOTONIC.


-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: gettimeofday resolution seriously degraded in test9

[Richard B. Johnson]

On Thu, 30 Oct 2003, George Anzinger wrote:

> Peter Chubb wrote:
> >>>>>>"Stephen" == Stephen Hemminger <shemminger@osdl.org> writes:
> >
> >
> > Stephen> On Wed, 29 Oct 2003 11:07:45 +0100 Gabriel Paubert
> > Stephen> <paubert@iram.es> wrote:
> >
> >>>for example.
> >
> >
> > Stephen> The suggestion of using time interpolation (like ia64) would
> > Stephen> make the discontinuities smaller, but still relying on fine
> > Stephen> grain gettimeofday for controlling servo loops with NTP
> > Stephen> running seems risky. Perhaps what you want to use is the
> > Stephen> monotonic_clock which gives better resolution (nanoseconds)
> > Stephen> and doesn't get hit by NTP.
> >
> > monotonic_clock:
> > 	-- isn't implemented for most architectures
> > 	-- even for X86 only works for some timing sources
> > 	-- and for the most common case is variable rate because of
> > 	   power management functions changing the TSC clock rate.
> >
> > As far as I know, there isn't a constant-rate monotonic clock
> > available at present for all architectures in the linux kernel.  The
> > nearest thing is scheduler_clock().
>
> What you want is the POSIX clocks and timers CLOCK_MONOTONIC which is available
> on all archs (as of 2.6).  The call is:
>
>        cc [ flag ... ] file -lrt [ library ... ]
>
>         #include <time.h>
>
>         int clock_gettime(clockid_t which_clock, struct timespec *setting);
>
> where you want "which_clock" to be CLOCK_MONOTONIC.
>

But there is a more basic problem. Let's say I need time in microseconds,
but the only hardware tick I have is in milliseconds. If I can call
the routine in zero time, it takes 1000 calls before the microsecond
value will change.

There isn't any magic that can solve this problem. It turns out
that with later Intel CPUs, one can get CPU-clock resolution
from rdtsc. However, this is hardware-specific. If somebody
modifies the gettimeofday() and the POSIX clock routines to
use rdtsc when available, a lot of problems will go away.



Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (797.90 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: gettimeofday resolution seriously degraded in test9

[Chris Friesen]

Richard B. Johnson wrote:

> There isn't any magic that can solve this problem. It turns out
> that with later Intel CPUs, one can get CPU-clock resolution
> from rdtsc. However, this is hardware-specific. If somebody
> modifies the gettimeofday() and the POSIX clock routines to
> use rdtsc when available, a lot of problems will go away.

Its not just x86.  PowerPC has a similar call, so does MIPS, and I'm 
sure most other modern cpus do too.

The only problem with this stuff is that they usually slow down when the 
cpu does, so laptops and other power-managed chips cause complexities.

Chris

-- 
Chris Friesen                    | MailStop: 043/33/F10
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: cfriesen@nortelnetworks.com

Re: gettimeofday resolution seriously degraded in test9

[Peter Chubb]

>>>>> "Richard" == Richard B Johnson <root@chaos.analogic.com> writes:

Richard> There isn't any magic that can solve this problem. It turns
Richard> out that with later Intel CPUs, one can get CPU-clock
Richard> resolution from rdtsc. However, this is hardware-specific. If
Richard> somebody modifies the gettimeofday() and the POSIX clock
Richard> routines to use rdtsc when available, a lot of problems will
Richard> go away.

gettimofday() and the posix clock routines (which use gettimeofday())
*do* use rdtsc if the processor has a reliable one --- do_gettimeofday() calls
cur_timer->get_offset(), which is essentially a scaled rdtsc if you're
using timers_tsc.c.

But when you have power management turned on, TSC doesn't run at a
constant rate.   If it gets *too* slow, the timer switches to use the
PIT instead, and one loses the cycle-resolution one would otherwise have.

--
Dr Peter Chubb  http://www.gelato.unsw.edu.au  peterc AT gelato.unsw.edu.au
You are lost in a maze of BitKeeper repositories,   all slightly different.

Re: gettimeofday resolution seriously degraded in test9

[George Anzinger]

Richard B. Johnson wrote:
> On Thu, 30 Oct 2003, George Anzinger wrote:
> 
> 
>>Peter Chubb wrote:
>>
>>>>>>>>"Stephen" == Stephen Hemminger <shemminger@osdl.org> writes:
>>>
>>>
>>>Stephen> On Wed, 29 Oct 2003 11:07:45 +0100 Gabriel Paubert
>>>Stephen> <paubert@iram.es> wrote:
>>>
>>>
>>>>>for example.
>>>
>>>
>>>Stephen> The suggestion of using time interpolation (like ia64) would
>>>Stephen> make the discontinuities smaller, but still relying on fine
>>>Stephen> grain gettimeofday for controlling servo loops with NTP
>>>Stephen> running seems risky. Perhaps what you want to use is the
>>>Stephen> monotonic_clock which gives better resolution (nanoseconds)
>>>Stephen> and doesn't get hit by NTP.
>>>
>>>monotonic_clock:
>>>	-- isn't implemented for most architectures
>>>	-- even for X86 only works for some timing sources
>>>	-- and for the most common case is variable rate because of
>>>	   power management functions changing the TSC clock rate.
>>>
>>>As far as I know, there isn't a constant-rate monotonic clock
>>>available at present for all architectures in the linux kernel.  The
>>>nearest thing is scheduler_clock().
>>
>>What you want is the POSIX clocks and timers CLOCK_MONOTONIC which is available
>>on all archs (as of 2.6).  The call is:
>>
>>       cc [ flag ... ] file -lrt [ library ... ]
>>
>>        #include <time.h>
>>
>>        int clock_gettime(clockid_t which_clock, struct timespec *setting);
>>
>>where you want "which_clock" to be CLOCK_MONOTONIC.
>>
> 
> 
> But there is a more basic problem. Let's say I need time in microseconds,
> but the only hardware tick I have is in milliseconds. If I can call
> the routine in zero time, it takes 1000 calls before the microsecond
> value will change.
> 
> There isn't any magic that can solve this problem. It turns out
> that with later Intel CPUs, one can get CPU-clock resolution
> from rdtsc. However, this is hardware-specific. If somebody
> modifies the gettimeofday() and the POSIX clock routines to
> use rdtsc when available, a lot of problems will go away.

THAT is exactly what both gettimeofday() AND the recommened interface do. 
Resolution will be to the TSC tick on x86.  Almost all archs provide at least 1 
microsecond resolution for both these clocks.

Even the x86 archs without a TSC have and have had, for some time, code which 
gives better than one microsecond resolution.

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: gettimeofday resolution seriously degraded in test9

[George Anzinger]

Peter Chubb wrote:
>>>>>>"Richard" == Richard B Johnson <root@chaos.analogic.com> writes:
> 
> 
> Richard> There isn't any magic that can solve this problem. It turns
> Richard> out that with later Intel CPUs, one can get CPU-clock
> Richard> resolution from rdtsc. However, this is hardware-specific. If
> Richard> somebody modifies the gettimeofday() and the POSIX clock
> Richard> routines to use rdtsc when available, a lot of problems will
> Richard> go away.
> 
> gettimofday() and the posix clock routines (which use gettimeofday())
> *do* use rdtsc if the processor has a reliable one --- do_gettimeofday() calls
> cur_timer->get_offset(), which is essentially a scaled rdtsc if you're
> using timers_tsc.c.
> 
> But when you have power management turned on, TSC doesn't run at a
> constant rate.   If it gets *too* slow, the timer switches to use the
> PIT instead, and one loses the cycle-resolution one would otherwise have.
> 
IF (and that is a big IF) the cpu knows about the change, there is code in 2.6 
to change the scaling of the TSC to match what the hardware is doing.

If you really want stability on the x86 grab the HRT patch (see sig below) and 
set it up to use the pm-timer.  This is rock solid, but does add time to the 
gettimeofday() and friends as it requires an I/O cycle to read it.


-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

[RFC] possible erronous use of tick_usec in do_gettimeofday

[Joe Korty]

test10's version of do_gettimeofday is using tick_usec which is
defined in terms of USER_HZ not HZ.

Against 2.6.0-test10-bk1.  Compiled, not tested, for comment only.

Joe

--- base/arch/i386/kernel/time.c	2003-11-23 20:31:55.000000000 -0500
+++ new/arch/i386/kernel/time.c	2003-11-25 11:22:38.000000000 -0500
@@ -94,7 +94,7 @@
 {
 	unsigned long seq;
 	unsigned long usec, sec;
-	unsigned long max_ntp_tick = tick_usec - tickadj;
+	unsigned long max_ntp_tick;
 
 	do {
 		unsigned long lost;
@@ -110,13 +110,14 @@
 		 * Better to lose some accuracy than have time go backwards..
 		 */
 		if (unlikely(time_adjust < 0)) {
+			max_ntp_tick = (USEC_PER_SEC / HZ) - tickadj;
 			usec = min(usec, max_ntp_tick);
 
 			if (lost)
 				usec += lost * max_ntp_tick;
 		}
 		else if (unlikely(lost))
-			usec += lost * tick_usec;
+			usec += lost * (USEC_PER_SEC / HZ);
 
 		sec = xtime.tv_sec;
 		usec += (xtime.tv_nsec / 1000);

Re: [RFC] possible erronous use of tick_usec in do_gettimeofday

[Stephen Hemminger]

On Tue, 25 Nov 2003 11:42:38 -0500
Joe Korty <joe.korty@ccur.com> wrote:

> test10's version of do_gettimeofday is using tick_usec which is
> defined in terms of USER_HZ not HZ.
> 
> Against 2.6.0-test10-bk1.  Compiled, not tested, for comment only.

Your right. tick_usec is in user hz so the value of max_ntp_tick would be
too large.

Re: [RFC] possible erronous use of tick_usec in do_gettimeofday

[George Anzinger]

Joe Korty wrote:
> test10's version of do_gettimeofday is using tick_usec which is
> defined in terms of USER_HZ not HZ.
> 
> Against 2.6.0-test10-bk1.  Compiled, not tested, for comment only.

We still have the problem that we are doing this calculation in usecs while the 
wall clock uses nsecs.  This would be fine if there were an even number of usecs 
in tick_nsec, but in fact it is somewhat less than (USEC_PER_SEC / HZ).  This 
means that this correction (if we are behind by 7 or more ticks) will push the 
clock past current time.  Here are the numbers:

tick_nsec =999849 or 1ms less 151 ns.  So if we are behind 7 or more ticks we 
will report the time out 1 us too high.  (7 * 151 = 1057 or 1.057 usec).

Question is, do we care?  Will we ever be 7ms late in updating the wall clock? 
As I recall, the wall clock is updated in the interrupt handler for the tick so, 
to be this late, we would need to suffer a long interrupt hold off AND the tick 
recovery code would need to have done its thing.  But this whole time is covered 
by a write_seqlock on xtime_lock, so how can this even happen?  Seems like it is 
only possible when we are locked and we then throw the whole thing away.

A test I would like to see is to put this in the code AFTER the read unlock:

if (lost )
	printk("Lost is %d\n", lost);

(need to pull "	unsigned long lost;" out of the do{}while loop to do this)

In short, I think we are beating a dead issue.

-g
> 
> Joe
> 
> --- base/arch/i386/kernel/time.c	2003-11-23 20:31:55.000000000 -0500
> +++ new/arch/i386/kernel/time.c	2003-11-25 11:22:38.000000000 -0500
> @@ -94,7 +94,7 @@
>  {
>  	unsigned long seq;
>  	unsigned long usec, sec;
> -	unsigned long max_ntp_tick = tick_usec - tickadj;
> +	unsigned long max_ntp_tick;
>  
>  	do {
>  		unsigned long lost;
> @@ -110,13 +110,14 @@
>  		 * Better to lose some accuracy than have time go backwards..
>  		 */
>  		if (unlikely(time_adjust < 0)) {
> +			max_ntp_tick = (USEC_PER_SEC / HZ) - tickadj;
>  			usec = min(usec, max_ntp_tick);
>  
>  			if (lost)
>  				usec += lost * max_ntp_tick;
>  		}
>  		else if (unlikely(lost))
> -			usec += lost * tick_usec;
> +			usec += lost * (USEC_PER_SEC / HZ);
>  
>  		sec = xtime.tv_sec;
>  		usec += (xtime.tv_nsec / 1000);
> 
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: [RFC] possible erronous use of tick_usec in do_gettimeofday

[Joe Korty]

On Tue, Nov 25, 2003 at 11:57:55AM -0800, George Anzinger wrote:
> Joe Korty wrote:
> >test10's version of do_gettimeofday is using tick_usec which is
> >defined in terms of USER_HZ not HZ.
> 
> We still have the problem that we are doing this calculation in usecs while 
> the wall clock uses nsecs.  This would be fine if there were an even number 
> of usecs in tick_nsec, but in fact it is somewhat less than (USEC_PER_SEC / 
> HZ).  This means that this correction (if we are behind by 7 or more ticks) 
> will push the clock past current time.  Here are the numbers:
> 
> tick_nsec =999849 or 1ms less 151 ns.  So if we are behind 7 or more ticks 
> we will report the time out 1 us too high.  (7 * 151 = 1057 or 1.057 usec).
> 
> Question is, do we care?  Will we ever be 7ms late in updating the wall 
> clock? As I recall, the wall clock is updated in the interrupt handler for 
> the tick so, to be this late, we would need to suffer a long interrupt hold 
> off AND the tick recovery code would need to have done its thing.  But this 
> whole time is covered by a write_seqlock on xtime_lock, so how can this 
> even happen?  Seems like it is only possible when we are locked and we then 
> throw the whole thing away.
> 
> A test I would like to see is to put this in the code AFTER the read unlock:
> 
> if (lost )
> 	printk("Lost is %d\n", lost);
> 
> (need to pull "	unsigned long lost;" out of the do{}while loop to do 
> this)
> 
> In short, I think we are beating a dead issue.

There are other issues too: the 'lost' calculation is a prediction
over the next 'lost' number of ticks.  That prediction will be wrong
if 1) adjtime goes to zero within that interval or, 2) adjtime was
zero but went nonzero in that interval due to a adjtimex(2) call.

Despite these flaws the patch replaces truly broken code with code
that is good but slightly inaccurate, which is good enough for now.

Joe

Re: [RFC] possible erronous use of tick_usec in do_gettimeofday

[George Anzinger]

Joe Korty wrote:
> On Tue, Nov 25, 2003 at 11:57:55AM -0800, George Anzinger wrote:
> 
>>Joe Korty wrote:
>>
>>>test10's version of do_gettimeofday is using tick_usec which is
>>>defined in terms of USER_HZ not HZ.
>>
>>We still have the problem that we are doing this calculation in usecs while 
>>the wall clock uses nsecs.  This would be fine if there were an even number 
>>of usecs in tick_nsec, but in fact it is somewhat less than (USEC_PER_SEC / 
>>HZ).  This means that this correction (if we are behind by 7 or more ticks) 
>>will push the clock past current time.  Here are the numbers:
>>
>>tick_nsec =999849 or 1ms less 151 ns.  So if we are behind 7 or more ticks 
>>we will report the time out 1 us too high.  (7 * 151 = 1057 or 1.057 usec).
>>
>>Question is, do we care?  Will we ever be 7ms late in updating the wall 
>>clock? As I recall, the wall clock is updated in the interrupt handler for 
>>the tick so, to be this late, we would need to suffer a long interrupt hold 
>>off AND the tick recovery code would need to have done its thing.  But this 
>>whole time is covered by a write_seqlock on xtime_lock, so how can this 
>>even happen?  Seems like it is only possible when we are locked and we then 
>>throw the whole thing away.
>>
>>A test I would like to see is to put this in the code AFTER the read unlock:
>>
>>if (lost )
>>	printk("Lost is %d\n", lost);
>>
>>(need to pull "	unsigned long lost;" out of the do{}while loop to do 
>>this)
>>
>>In short, I think we are beating a dead issue.
> 
> 
> There are other issues too: the 'lost' calculation is a prediction
> over the next 'lost' number of ticks.  That prediction will be wrong
> if 1) adjtime goes to zero within that interval or, 2) adjtime was
> zero but went nonzero in that interval due to a adjtimex(2) call.
> 
> Despite these flaws the patch replaces truly broken code with code
> that is good but slightly inaccurate, which is good enough for now.

Can you prove that "lost" is EVER non-zero in a case we care about?  I.e. a case 
where the read_seq will exit the loop?

I could be wrong here, but I don't think it can happen.  That is why I suggested 
the if(lost) test.

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: gettimeofday resolution seriously degraded in test9

[David Mosberger]

>>>>> On Tue, 28 Oct 2003 11:59:17 -0800, Stephen Hemminger <shemminger@osdl.org> said:

  Stephen> On 28 Oct 2003 11:19:21 -0800
  Stephen> David Mosberger-Tang <David.Mosberger@acm.org> wrote:

  >> >>>>> On Tue, 28 Oct 2003 19:30:13 +0100, Stephen Hemminger <shemminger@osdl.org> said:

  Stephen> This should work better. Patch against 2.6.0-test9

  >> Why not use the time-interpolator interface defined in timex.h?  It
  >> should handle such things without any special hacks.

  Stephen> Because it has not been used yet outside of ia64.  It would
  Stephen> be worth investigating post 2.6.0 if it could be shown to
  Stephen> be as fast and more correct.  Several people have talked
  Stephen> about redoing the existing mess, but now is not the time to
  Stephen> attack this dragon...

OK, I certainly agree that it's not something that should be done in a
rush, so it's definitely post 2.6.0.

	--david

Re: gettimeofday resolution seriously degraded in test9

[Stephen Hemminger]

On 28 Oct 2003 11:19:21 -0800
David Mosberger-Tang <David.Mosberger@acm.org> wrote:

> >>>>> On Tue, 28 Oct 2003 19:30:13 +0100, Stephen Hemminger <shemminger@osdl.org> said:
> 
>   Stephen> This should work better. Patch against 2.6.0-test9
> 
> Why not use the time-interpolator interface defined in timex.h?  It
> should handle such things without any special hacks.
> 
> 	--david

Because it has not been used yet outside of ia64.  It would be worth investigating
post 2.6.0 if it could be shown to be as fast and more correct.  Several people
have talked about redoing the existing mess, but now is not the time to attack
this dragon...

Re: gettimeofday resolution seriously degraded in test9

[David Mosberger-Tang]

>>>>> On Tue, 28 Oct 2003 19:30:13 +0100, Stephen Hemminger <shemminger@osdl.org> said:

  Stephen> This should work better. Patch against 2.6.0-test9

Why not use the time-interpolator interface defined in timex.h?  It
should handle such things without any special hacks.

	--david