Skip to contentSkip to conversation

gettimeofday question

DISCUSSION Russell King 4 participants 15 messages Mar 3, 2001 – Mar 21, 2001

lore
Share & tools
lore
#0 lore raw

Hi,

I've noticed that one of my machines here suffers from the "time going backwards problem" and so started thinking about the x86 solution.

I've come to the conclusion that it has a hole which could cause it to return the wrong time in one specific case:

- in do_gettimeofday(), we disable irqs (read_lock_irqsave)
- the ISA timer wraps, but we've got interrupts disabled, so no update of xtime or jiffies occurs
- in do_slow_gettimeoffset(), we read the timer, which has wrapped
- since jiffies_p != jiffies, we do not apply any correction
- our idea of time is now one jiffy slow.

Further more, while do_gettimeofday() is still within the read_lock_irqsave, we spin_unlock(&i8253_lock) in do_slow_gettimeoffset() and _re-enable_ interrupts! This means when we later read xtime, we're doing it with interrupts enabled.

This applies to both 2.2.18 and 2.4.2.

--
Russell King ([email protected]) The developer of ARM Linux
http://www.arm.linux.org.uk/personal/aboutme.html

#1 lore raw
Quoted 4 lines · Russell King

Further more, while do_gettimeofday() is still within the read_lock_irqsave, we spin_unlock(&i8253_lock) in do_slow_gettimeoffset() and _re-enable_ interrupts! This means when we later read xtime, we're doing it with interrupts enabled.

Ok, so this is a classic brainfart. The rest of the original message still stands though.

--
Russell King ([email protected]) The developer of ARM Linux
http://www.arm.linux.org.uk/personal/aboutme.html

#2 lore raw
In reply to Russell King
Quoted 8 lines · Russell King

Hi,

I've noticed that one of my machines here suffers from the "time going backwards problem" and so started thinking about the x86 solution.

I've come to the conclusion that it has a hole which could cause it to return the wrong time in one specific case:

Quoted 6 lines

- in do_gettimeofday(), we disable irqs (read_lock_irqsave)
- the ISA timer wraps, but we've got interrupts disabled, so no update of xtime or jiffies occurs
- in do_slow_gettimeoffset(), we read the timer, which has wrapped
- since jiffies_p != jiffies, we do not apply any correction
- our idea of time is now one jiffy slow.

I never heard any response to this. Could some knowledgeable person please take a look at it?

Thanks.

--
Russell King ([email protected]) The developer of ARM Linux
http://www.arm.linux.org.uk/personal/aboutme.html

#3 lore raw
In reply to Russell King
Quoted 13 lines · Russell King
Quoted 6 lines

I've noticed that one of my machines here suffers from the "time going backwards problem" and so started thinking about the x86 solution.

I've come to the conclusion that it has a hole which could cause it to return the wrong time in one specific case:

Quoted 6 lines

- in do_gettimeofday(), we disable irqs (read_lock_irqsave)
- the ISA timer wraps, but we've got interrupts disabled, so no update of xtime or jiffies occurs
- in do_slow_gettimeoffset(), we read the timer, which has wrapped
- since jiffies_p != jiffies, we do not apply any correction
- our idea of time is now one jiffy slow.

Quoted 2 lines

I never heard any response to this. Could some knowledgeable person please take a look at it?

do_slow_gettimeoffset() is supposed to correct for wrapping. But where it says:

	#define BUGGY_NEPTUN_TIMER

		if( jiffies_t == jiffies_p ) {
		    if( count > count_p ) {
			      /* the nutcase */

Shouldn't that say "count < count_p"?

-- Jamie

#4 lore raw
In reply to Russell King
Quoted 21 lines · Jamie Lokier
Quoted 13 lines · Russell King
Quoted 6 lines

I've noticed that one of my machines here suffers from the "time going backwards problem" and so started thinking about the x86 solution.

I've come to the conclusion that it has a hole which could cause it to return the wrong time in one specific case:

Quoted 6 lines

- in do_gettimeofday(), we disable irqs (read_lock_irqsave)
- the ISA timer wraps, but we've got interrupts disabled, so no update of xtime or jiffies occurs
- in do_slow_gettimeoffset(), we read the timer, which has wrapped
- since jiffies_p != jiffies, we do not apply any correction
- our idea of time is now one jiffy slow.

Quoted 2 lines

I never heard any response to this. Could some knowledgeable person please take a look at it?

do_slow_gettimeoffset() is supposed to correct for wrapping. But where it says:

Quoted 7 lines
        #define BUGGY_NEPTUN_TIMER

                if( jiffies_t == jiffies_p ) {
                    if( count > count_p ) {
                              /* the nutcase */

Shouldn't that say "count < count_p"?

I've been looking at related code a bit lately... (please correct me if I'm wrong on something...)

The TIMER1 on an EBSA285 counts down, in which case, count > count_p is correct. I don't know which direction the isa_ timer counts.

Russell, I know that at least the EBSA285's timer1_gettimeoffset() needs some attention to fix a time going backward problem. (include/asm-arm/arch-ebsa285/time.h)
I have been using the following recently. I'm no longer seeing the gettimeofday() going backwards with this change. (NOTE! I can't vouch for the 100% correctness of this code.. I'll talk a bit more about that after the code, but I think it's closer than it was.)

int count;

static int count_p = LATCH; /* for the first call after boot
*/

        static unsigned long jiffies_p = 0;

        /*
         * cache volatile jiffies temporarily; we have IRQs turned off.
         */
        unsigned long jiffies_t;

        count = *CSR_TIMER1_VALUE;      /* read the count */

        jiffies_t = jiffies;

        /* Detect timer underflows.  If we haven't had a timer tick

since
the last time we were called, and time is apparently going backwards, the counter must have wrapped during this routine.
*/

        if ((jiffies_t == jiffies_p) && (count > count_p))
                count -= LATCH;
        else
                jiffies_p = jiffies_t;

        count_p = count;

        count = (LATCH - count) * tick;
    /* Round up to nearest tick */
        count = (count + LATCH/2) / LATCH;

        return count;

This should prevent us from seeing time jump back for slightly less than a jiffie. I'm a little unsure of the "rounding" code... We are supposed to be returning the number of microseconds since the start of this jiffie. (right?) From my (possibly flawed) understanding of this code, perhaps the following would make more sense?

/*
* tick = # of usecs per jiffie
* (set in kernel/sched.c, modified by xntpd thru kernel/time.c)
* LATCH = # timer decrements per jiffie <linux/timex.h>
* count = # timer decrements remaining in this jiffie
*
* LATCH - count = # of timer decrements that have occurred so far in
* the current (cached) jiffie.
*
* (LATCH - count)(timer decs) tick (usec) (jiffie)
* x ----------- x ----------------- = (usec)
* (jiffie) LATCH (timer decs)
*/

        usecs = (LATCH - count) * tick / LATCH;
        return usecs;

Now... all the above makes the time-going-backward problem happen less, but the original post may still have a point...

---- timer interrupt
---- jiffies++
---- gettimeoffset
(sets jiffies_p and count_p)
---- timer interrupt
---- jiffies++
#--- DISABLE INTERRUPTS
#--- timer interrupt
#--- gettimeoffset
# jiffies_t != jiffies_p, so we don't detect an
# underflow (wrapped counter) condition, so the time
# reported is ~10ms less than it should be.
# (sets jiffies_p and count_p)
#--- REENABLE INTERRUPTS
---- jiffies++
---- timer interrupt
---- jiffies++

The problem is only going to occur if gettimeoffset has not been called in the past 10ms. Once 10ms has passed, either jiffies has changed, or count will have passed count_p.

My first thought on a fix for this is to have do_timer (kernel/sched.c) update the *_p variables... but that's kinda ugly. Perhaps it should call gettimeoffset to make sure that it keeps up with the jiffies? Ummm.... Of course, if interrupt are disabled for multiple jiffies, I'm not sure quite how we detect that either...

Thoughts, comments, questions, etc. welcome.

Eli
-----------------------. Rule of Accuracy: When working toward
Eli Carter | the solution of a problem, it always
eli.carter(at)inet.com `------------------ helps if you know the answer.

#5 lore raw
Quoted 2 lines · Eli Carter

Russell, I know that at least the EBSA285's timer1_gettimeoffset() needs some attention to fix a time going backward problem.

I know about this, which is what started me looking at what x86 does, and I am firmly of the conclusion that x86 is buggy as it stands.

I believe that we can, instead of having a per-machine fix on ARM, have a generic fix. At the moment, I haven't worked out exactly what this generic fix would be.

Quoted 3 lines

The problem is only going to occur if gettimeoffset has not been called in the past 10ms. Once 10ms has passed, either jiffies has changed, or count will have passed count_p.

My concern with the x86 fix is what if 9.9999999999ms has passed since the last timer tick, and we got the timer tick after we disabled interrupts and entered do_gettimeofday. This can lead to the tests in there miscorrecting IMHO. You won't see it with an infinite loop reading the time of day...

I'll re-read your mail in more depth later tonight. Appologies if this reply appears to be a little early.

--
Russell King ([email protected]) The developer of ARM Linux
http://www.arm.linux.org.uk/personal/aboutme.html

#6 lore raw
Quoted 7 lines · Russell King
Quoted 2 lines · Eli Carter

Russell, I know that at least the EBSA285's timer1_gettimeoffset() needs some attention to fix a time going backward problem.

I know about this, which is what started me looking at what x86 does, and I am firmly of the conclusion that x86 is buggy as it stands.

Ah, OK.

Quoted 4 lines

I believe that we can, instead of having a per-machine fix on ARM, have a generic fix. At the moment, I haven't worked out exactly what this generic fix would be.

Quoted 8 lines
Quoted 3 lines

The problem is only going to occur if gettimeoffset has not been called in the past 10ms. Once 10ms has passed, either jiffies has changed, or count will have passed count_p.

My concern with the x86 fix is what if 9.9999999999ms has passed since the last timer tick, and we got the timer tick after we disabled interrupts and entered do_gettimeofday. This can lead to the tests in there miscorrecting IMHO. You won't see it with an infinite loop reading the time of day...

Hmm... I'm not seeing it quite yet...
do_gettimeofday doesn't
-- disable interrupts for do_gettimeofday
-- interrupt raised for "TIMER1" (or isa timer or whatever), the timer's counter wraps back to the value of LATCH and begins decrementing. -- we make a copy of xtime
-- gettimeoffset is called. Assuming it has been called less than 10ms ago, (jiffies_t == jiffies_p && count > count_p) is true, so we adjust the 10ms for that, and return the number of usecs since the last jiffie change.
-- add the offset, bringing us up to the correct time
-- lost_ticks adjusts for the number of jiffies that have been counted but not added to xtime (and thus has no impact on the gettimeoffset logic)

    (so, shouldn't this be "tv->tv_usec += lost_ticks *

USECS_PER_JIFFY;"?
or can lost_ticks never be greater than 1?)
-- restore interrupts
-- jiffies & lost_ticks get incremented

What are you seeing that I'm missing?

Quoted 2 lines

I'll re-read your mail in more depth later tonight. Appologies if this reply appears to be a little early.

No problem. I'd like to see this code fixed correctly, so I'm happy to help.

C-ya,

Eli
-----------------------. Rule of Accuracy: When working toward
Eli Carter | the solution of a problem, it always
eli.carter(at)inet.com `------------------ helps if you know the answer.

#7 lore raw
Quoted 1 line · Eli Carter

What are you seeing that I'm missing?

Ok, after sitting down and thinking again about this problem, its not the 9.9999ms case, but the 10.000000001 case:

First time:
- interrupts disabled
- read jiffies
- read counter
- jiffies_p != jiffies_t
- set jiffies_p = jiffies_t
- set counter_p = counter
- correction of (latch - counter) applied -> almost a full 10ms
- interrupts enabled
- counter rolls over
- jiffies updated
- counter is at, or near maximum
- time returned we'll call "0".

10.0000001ms later:
- interrupts disabled
- read jiffies
- counter rolls over
- read counter
- jiffies_p != jiffies_t
- set jiffies_p = jiffies_t
- set counter_p = counter
- correction of (latch - counter) applied -> almost nothing
- interrupts enabled
- jiffies updated
- time returned - "0" + almost nothing

Next read immediately after:
- interrupts disabled
- read jiffies
- read counter
- jiffies_p != jiffies_t
- set jiffies_p = jiffies_t
- set counter_p = counter
- correction of (latch - counter) applied -> slightly more than almost nothing
- interrupts enabled
- time returned - "10ms" + slightly more than almost nothing

Like I say, this requires good timing to create, so may not be too much of a problem, but it does seem to be a problem that could occur.

I'm wondering if something like the following will plug this hole:

	read_lock_xtime_and_ints();
	jiffies_1 = jiffies;
	counter_1 = counter;
	read_unlock_xtime_and_ints();
	read_lock_xtime_and_ints();
	jiffies_2 = jiffies;
	counter_2 = counter;
	read_unlock_xtime_and_ints();

	if (jiffies_1 != jiffies_2) {
		/*
		 * we rolled over while reading counter_1.  Therefore
		 * we can't trust it.  Use *_2 instead.  Note that we
		 * would have received an interrupt between read_unlock
		 * and read_lock.
		 */
		jiffies_1 = jiffies_2;
		counter_1 = counter_1;
	} else {
		/*
		 * we didn't roll over while reading counter_1
		 * we can safely use counter_1 as is.  Neither
		 * did we receive a timer interrupt between the
		 * read_unlock and read_lock.
		 */
	}

	/* apply standard counter correction factor */

The only thing I haven't looked at is whether xtime would be updated.

--
Russell King ([email protected]) The developer of ARM Linux
http://www.arm.linux.org.uk/personal/aboutme.html

#8 lore raw
Quoted 6 lines · Russell King
Quoted 1 line · Eli Carter

What are you seeing that I'm missing?

Ok, after sitting down and thinking again about this problem, its not the 9.9999ms case, but the 10.000000001 case:

And you described (in much better detail) the same problem I was talking about in the first email I sent today.

gettimeoffset does not handle cases >10ms.

Quoted 2 lines

Like I say, this requires good timing to create, so may not be too much of a problem, but it does seem to be a problem that could occur.

You should be able to create this "maliciously" within the kernel (or with bad driver code...) with something like:
Disable interrupts for 10ms, then call gettimeofday, reenable interrupts, then call gettimeofday.
(I think.)

Quoted 1 line

I'm wondering if something like the following will plug this hole:

Yes, but it digs another to get the dirt to fill the first one. :/ for instance:

Quoted 5 lines
        read_lock_xtime_and_ints();
        jiffies_1 = jiffies;
        counter_1 = counter;
        read_unlock_xtime_and_ints();

Time passes due to an interrupt handler.... but not a full jiffy, so jiffies hasn't changed.
Also, what if this function is called with interrupts disabled? (Is that legal?) If so, we've broken the locking expected by the caller.

Quoted 1 line
        read_lock_xtime_and_ints();

And just for giggles, the counter rolls over here. (And with interrupts disabled, jiffies isn't updated yet...)

Quoted 15 lines
        jiffies_2 = jiffies;
        counter_2 = counter;
        read_unlock_xtime_and_ints();

        if (jiffies_1 != jiffies_2) {
                /*
                 * we rolled over while reading counter_1.  Therefore
                 * we can't trust it.  Use *_2 instead.  Note that we
                 * would have received an interrupt between read_unlock
                 * and read_lock.
                 */
                jiffies_1 = jiffies_2;
                counter_1 = counter_1;
        } else {
                /*
Quoted 8 lines
                 * we didn't roll over while reading counter_1
                 * we can safely use counter_1 as is.  Neither
                 * did we receive a timer interrupt between the
                 * read_unlock and read_lock.
                 */
        }

        /* apply standard counter correction factor */

Which might be just less than 10ms inaccurate due to that interrupt handler that ran after we read the times. So we are no more accurate than before. :/

Unless you use counter_2, but then you have the original problem again.

Quoted 1 line

The only thing I haven't looked at is whether xtime would be updated.

That is updated in the timer bottom half; jiffies and lost_ticks are updated in the timer interrupt. lost_ticks is then used by the bottom half to update xtime. (That's why the gettimeofday portion references lost_ticks.)

Comments?

Eli
-----------------------. Rule of Accuracy: When working toward
Eli Carter | the solution of a problem, it always
eli.carter(at)inet.com `------------------ helps if you know the answer.

#9 lore raw
Quoted 2 lines · Eli Carter

And you described (in much better detail) the same problem I was talking about in the first email I sent today.

Ok, at least we've got the same picture that we're working from now.

Quoted 9 lines

Yes, but it digs another to get the dirt to fill the first one. :/ for instance:

Quoted 5 lines
        read_lock_xtime_and_ints();
        jiffies_1 = jiffies;
        counter_1 = counter;
        read_unlock_xtime_and_ints();
Quoted 4 lines

Time passes due to an interrupt handler.... but not a full jiffy, so jiffies hasn't changed.
Also, what if this function is called with interrupts disabled? (Is that legal?) If so, we've broken the locking expected by the caller.

The calling function does indeed do the read_lock_xtime_and_ints() bit for us. However, we can always do a read_unlock(); sti(); read_lock_irq(); in do_gettimeofday(). Whether we want to or not is another matter, especially as its not nice for a called function to explicitly enable interrupts.

As for timer interrupts taking more than 10ms, yes, that is another problem. ;(

Quoted 1 line

Comments?

This problem has a non-trivial solution, and I think whoever originally wrote the x86 do_gettimeofday code decided that it wasn't worth finding a solution to it.

--
Russell King ([email protected]) The developer of ARM Linux
http://www.arm.linux.org.uk/personal/aboutme.html

#10 lore raw
Quoted 3 lines · Russell King

This problem has a non-trivial solution, and I think whoever originally wrote the x86 do_gettimeofday code decided that it wasn't worth finding a solution to it.

So are you going to use the x86 solution and not worry about the >10ms problem for now? The x86 is an improvement over the current situation (at least on ebsa285). Or do you have something else in mind?

Eli
-----------------------. Rule of Accuracy: When working toward
Eli Carter | the solution of a problem, it always
eli.carter(at)inet.com `------------------ helps if you know the answer.

#11 lore raw
In reply to Russell King
Quoted 6 lines · Russell King
Quoted 1 line · Eli Carter

What are you seeing that I'm missing?

Ok, after sitting down and thinking again about this problem, its not the 9.9999ms case, but the 10.000000001 case:

[snip]

Quoted 2 lines

Like I say, this requires good timing to create, so may not be too much of a problem, but it does seem to be a problem that could occur.

It appears that this problem is easier to create than we originally gave credit for.... All that is needed is for gettimeoffset() not to be called for a _minimum_ of >10ms, and for the timer to wrap during a call to do_gettimeofday() or during a period of time where interrupts are disabled and do_gettimeofday() is called. Note that there is no upper limit to the time...

If we call gettimeoffset() after do_timer() returns (and there-by update the internal variables every 10ms), we should reduce the impact of this bug dramatically (in theory--in practice, disabling interrupts for long periods can also have some bad effects that this won't help, but I think that's another issue.)

One of the guys I'm working with did some testing on this, and he was seeing this problem (off by 10ms) every 5 to 10 minutes (on a modified ARM & kernel). With the additional gettimeoffset() call, he no longer saw it (at least within ~3hrs.).

Questions, comments, etc.?

Eli
-----------------------. Rule of Accuracy: When working toward
Eli Carter | the solution of a problem, it always
eli.carter(at)inet.com `------------------ helps if you know the answer.

#12 lore raw
In reply to Russell King
Quoted 25 lines · Eli Carter
Quoted 6 lines · Russell King
Quoted 1 line · Eli Carter

What are you seeing that I'm missing?

Ok, after sitting down and thinking again about this problem, its not the 9.9999ms case, but the 10.000000001 case:

[snip]

Quoted 2 lines

Like I say, this requires good timing to create, so may not be too much of a problem, but it does seem to be a problem that could occur.

It appears that this problem is easier to create than we originally gave credit for.... All that is needed is for gettimeoffset() not to be called for a _minimum_ of >10ms, and for the timer to wrap during a call to do_gettimeofday() or during a period of time where interrupts are disabled and do_gettimeofday() is called. Note that there is no upper limit to the time...

If we call gettimeoffset() after do_timer() returns (and there-by update the internal variables every 10ms), we should reduce the impact of this bug dramatically (in theory--in practice, disabling interrupts for long periods can also have some bad effects that this won't help, but I think that's another issue.)

Quoted 6 lines

One of the guys I'm working with did some testing on this, and he was seeing this problem (off by 10ms) every 5 to 10 minutes (on a modified ARM & kernel). With the additional gettimeoffset() call, he no longer saw it (at least within ~3hrs.).

Questions, comments, etc.?

Another thought...

If we pull count_p and jiffies_p out of the various *_gettimeoffset() functions, and added an updatetimeoffset() that only updated count_p and jiffies_p, (and called it after every do_timer(),) we'd accomplish the same thing, but with less overhead.

(This is based on looking at the ARM code; I haven't fully studied the x86 & others.)

Questions, comments, etc?

Eli
-----------------------. Rule of Accuracy: When working toward
Eli Carter | the solution of a problem, it always
eli.carter(at)inet.com `------------------ helps if you know the answer.

#13 lore raw
In reply to Russell King
Quoted 32 lines · Eli Carter
Quoted 30 lines · Eli Carter
Quoted 6 lines · Russell King
Quoted 1 line · Eli Carter

What are you seeing that I'm missing?

Ok, after sitting down and thinking again about this problem, its not the 9.9999ms case, but the 10.000000001 case:

[snip]

Quoted 2 lines

Like I say, this requires good timing to create, so may not be too much of a problem, but it does seem to be a problem that could occur.

It appears that this problem is easier to create than we originally gave credit for.... All that is needed is for gettimeoffset() not to be called for a _minimum_ of >10ms, and for the timer to wrap during a call to do_gettimeofday() or during a period of time where interrupts are disabled and do_gettimeofday() is called. Note that there is no upper limit to the time...

If we call gettimeoffset() after do_timer() returns (and there-by update the internal variables every 10ms), we should reduce the impact of this bug dramatically (in theory--in practice, disabling interrupts for long periods can also have some bad effects that this won't help, but I think that's another issue.)

One of the guys I'm working with did some testing on this, and he was seeing this problem (off by 10ms) every 5 to 10 minutes (on a modified ARM & kernel). With the additional gettimeoffset() call, he no longer saw it (at least within ~3hrs.).

Quoted 8 lines
Quoted 1 line

Questions, comments, etc.?

Another thought...

If we pull count_p and jiffies_p out of the various *_gettimeoffset() functions, and added an updatetimeoffset() that only updated count_p and jiffies_p, (and called it after every do_timer(),) we'd accomplish the same thing, but with less overhead.

Ok, it just dawned on me...
if we update jiffies_p every time we update jiffies, it stands to reason that they will always be equal... soooo... we can eliminate the need for that check, and hence, the variable.

Since we are open to this problem from 10ms after the last call to gettimeoffset to the time that interrupts are enabled, we should be significantly better off.

We still have a race, just smaller....Updating count_p twice per jiffie should eliminate the problem in practice (though in theory, we still have a race.) Errrm... ????

Questions, comments, etc?

Eli
-----------------------. Rule of Accuracy: When working toward
Eli Carter | the solution of a problem, it always
eli.carter(at)inet.com `------------------ helps if you know the answer.

#14 lore raw

Question on binutils release to use

In reply to Russell King

Hi all,

I'm looking into upgrading my binutils to the latest stable release. I
do kernel work so I'm guessing from previous experience that I have to get the Linux specific one. I tracked the linux specific versions down to ftp.kernel.org but am not certain as to which one is the latest stable release. The frequency of releases posted there make it look like the snapshot released are interposed with the stable releases and the release notes don't appear to be helpful as all the releases have been labeled as "beta". Checking into a couple of distributions in development I also notice they are not using anything beyond 2.10.1.x so I'm a bit concerned about just getting the latest binutils package from the ftp directory. May someone please point me to the latest release considered as stable and which will work with all kernel compiles (2.2.x and 2.4.x). Or if I can safely use the latest release in the binutils directory please let me know as well. Thank you.