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
On Sat, Mar 03, 2001 at 12:49:04PM +0000, Russell King wrote:
> 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
On Sat, Mar 03, 2001 at 12:49:04PM +0000, Russell King wrote:
> 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.
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
Russell King wrote:
> > 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.
>
> 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
Jamie Lokier wrote:
>
> Russell King wrote:
> > > 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.
> >
> > 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"?
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.
Eli Carter writes:
> 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.
> 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
Russell King wrote:
>
> Eli Carter writes:
> > 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.
> 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.
>
> > 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?
> 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.
Eli Carter writes:
> 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
Russell King wrote:
>
> Eli Carter writes:
> > 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.
> 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.)
> 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:
>
> 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.
> read_lock_xtime_and_ints();
And just for giggles, the counter rolls over here. (And with interrupts
disabled, jiffies isn't updated yet...)
> 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 */
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.
> 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.
Eli Carter writes:
> 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.
> Yes, but it digs another to get the dirt to fill the first one. :/ for
> instance:
>
> >
> > 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.
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. ;(
> 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
Russell King wrote:
> 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.
Russell King wrote:
>
> Eli Carter writes:
> > 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]
> 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.
Eli Carter wrote:
>
> Russell King wrote:
> >
> > Eli Carter writes:
> > > 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]
> > 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.?
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.
Eli Carter wrote:
>
> Eli Carter wrote:
> >
> > Russell King wrote:
> > >
> > > Eli Carter writes:
> > > > 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]
> > > 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.?
>
> 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.
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.