Re:[parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

Re:[parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Joel Soete]

> A review of 'arch/parisc/kernel/time.c' and in particular
> 'timer_interrupt' and 'gettimeoffset'  show that this code has a
> couple of design flaws.
> 
> 1. cr16 is treated as signed.
> 2. No attempt is made to handle cr16 wrapping.
> 3. jiffies vs. wall_jiffies adjustment is incorrect.
> 
> I have rewritten 'timer_interrupt'.
> 
> A. cr16 is treated as an unsigned long.
> B. The following 3 scenarios exist.
> 
> 1. The timer interrupt fires, and 'now' comes after 'next_tick'
mmm (just a thought) what's up if now comes after next_tick but cr16 has
already wrap 1, 2, ... times?

> 2. The timer interrupt fires, and 'now' has wrapped and is before 'next=
_tick'
> 3. The timer interrupt fires, and 'now' is *just* before 'next_tick'
> 
> In theory 99% of the time we should be in scenario 1. On occasion we
> may miss a timer interrupt, end up close to wrapping, and we get
> scenario 2. Scenario 3 is just plain wrong and for now I will BUG() if
> the timer fires before we intended.
> 
> I have adjusted 'gettimeoffset' in the following fashion:
> 
> A. cr16 is treated as an unsigned long.
> B. Never ever ever return a negative adjustment.
> C. (jiffies - wall_jiffies) adjustment is always positive and added to =
usec.
> D. The 3 timer scenarios (same as above), exist.
> 
> I assert that 'gettimeoffset' should never return a negative value. It
> represents the postive adjustment accounting for the fact that we are
> *part* of the way through a tick.
> 
> The patch is attached. Please review. I booted this on my a500 without
> any problems. I don't really know how to look for problems so I ran
> the glibc testsuite and didn't get any extra regressions.
> 
> The real test will be to run this on a 715/50 and look for Guy's
> reported problems. Guy, would you mind patching your kernel with this
> patch and testing again?
> 
Make sense to me but patch doesn't works for me on b2k 32bit kernel ;-(
it was hanging (no error msg on lcd display) just after "Memory: 262144k
available" then I have to force reboot power off/on cycle.

Thanks,
    Joel

 
> Cheers,
> Carlos.
> 
> =0A=0A----------=0AClub Scarlet : Tout le monde gagne! Si vous devenez =
aujourd'hui Scarlet One grace a un client existant de Scarlet, vous recev=
ez tous les deux un cadeau d'une valeur de 50 euros! Surfez vite sur http=
://www.clubscarlet.be

_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Wed, Aug 30, 2006 at 06:38:19PM +0200, Joel Soete wrote:
> > 1. The timer interrupt fires, and 'now' comes after 'next_tick'
> mmm (just a thought) what's up if now comes after next_tick but cr16 has
> already wrap 1, 2, ... times?

Every ~4 seconds a 32-bit cycle counter running 1Ghz will wrap.
If it wraps twice between any two interrupts, I think we are already screwed.
There is no way to detect that with a 32-bit kernel.  My hope is the same
bug is visible on 64-bit kernel where we have 30 billion or so seconds
before the counter will wrap.

> > reported problems. Guy, would you mind patching your kernel with this
> > patch and testing again?
>
> Make sense to me but patch doesn't works for me on b2k 32bit kernel ;-(
> it was hanging (no error msg on lcd display) just after "Memory: 262144k
> available" then I have to force reboot power off/on cycle.

I'll give it a go as well.

grant
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Carlos O'Donell]

On 8/30/06, Grant Grundler <grundler@parisc-linux.org> wrote:
> On Wed, Aug 30, 2006 at 06:38:19PM +0200, Joel Soete wrote:
> > > 1. The timer interrupt fires, and 'now' comes after 'next_tick'
> > mmm (just a thought) what's up if now comes after next_tick but cr16 has
> > already wrap 1, 2, ... times?
>
> Every ~4 seconds a 32-bit cycle counter running 1Ghz will wrap.
> If it wraps twice between any two interrupts, I think we are already screwed.
> There is no way to detect that with a 32-bit kernel.  My hope is the same
> bug is visible on 64-bit kernel where we have 30 billion or so seconds
> before the counter will wrap.
>
> > > reported problems. Guy, would you mind patching your kernel with this
> > > patch and testing again?
> >
> > Make sense to me but patch doesn't works for me on b2k 32bit kernel ;-(
> > it was hanging (no error msg on lcd display) just after "Memory: 262144k
> > available" then I have to force reboot power off/on cycle.
>
> I'll give it a go as well.

It actaully turns out I don't think I ever booted this patch, my
palo.conf was hosed and I was writing the wrong kernel. It was too
good to be true :)

I'll have a go at testing this again tonight.

Cheers,
Carlos.
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[James Bottomley]

On Wed, 2006-08-30 at 16:23 -0400, Carlos O'Donell wrote:
> It actaully turns out I don't think I ever booted this patch, my
> palo.conf was hosed and I was writing the wrong kernel. It was too
> good to be true :)
> 
> I'll have a go at testing this again tonight.

Actually, according to my analysis on ioz (pa8800) there seem to be some
hidden issues with our implementation (i.e. it's not the mathematics).

The first problem is that interrupts are re-entrant, so the timer
interrupt can get re-interrupted.  If this happens between the mfctl(16)
and the mtctl(), which is made much longer by the use of while loops,
then there's a small possibility that the interrupt caused us to miss
the next tick (i.e. cr16 moved beyond next_tick while in the interrupt).
I see this very occasionally on the pa8800 caused by flush IPIs (since
the cache is so huge) ... it's probably caused by SCSI interrupts on the
C3xxx that everyone else is testing with.  However, when this happens,
you have to wait for cr16 to wrap before you get another timer
interrupt, which I believe to be the source of the time jumps and
negative offsets in gettimeoffset().

My proposed fix for this is below.  However, we seem to have a few other
issues:

     1. On SMP, cr16 of the secondary processors (and next_tick) is
        never initialised ... we just wait for the timer to wrap and
        then pick up ticking from there.
     2. processor_probe() blows away all of the next_tick data when it's
        called (once for every CPU)
     3. We're regularly missing multiple ticks ... mainly below about
        30 .. there must be some cause for this but I can't immediately
        find it.
     4. we don't obey CONFIG_HZ at all the clock is always either 1000
        for pa2.0 or 100 for pa1.0

James

diff --git a/arch/parisc/kernel/time.c b/arch/parisc/kernel/time.c
index 5facc9b..93322a2 100644
--- a/arch/parisc/kernel/time.c
+++ b/arch/parisc/kernel/time.c
@@ -48,9 +48,13 @@ irqreturn_t timer_interrupt(int irq, voi
 	long next_tick;
 	int nticks;
 	int cpu = smp_processor_id();
+	unsigned long flags;
 
 	profile_tick(CPU_PROFILING, regs);
 
+	/* Don't want to be interrupted while calculating
+	 * time offsets */
+	local_irq_save(flags);
 	now = mfctl(16);
 	/* initialize next_tick to time at last clocktick */
 	next_tick = cpu_data[cpu].it_value;
@@ -63,13 +67,24 @@ irqreturn_t timer_interrupt(int irq, voi
 	 * Variables are *signed*.
 	 */
 
-	nticks = 0;
-	while((next_tick - now) < halftick) {
+	/* Don't do expensive mul and div for the likely case */
+	if (likely(now - next_tick < clocktick)) {
+		nticks = 1;
 		next_tick += clocktick;
+	} else {
+		nticks = ((now - next_tick)/clocktick) + 1;
+		next_tick += clocktick*nticks;
+	}
+	/* Don't interrupt too much.  If we only have half
+	 * the time to go to the next tick, push it out one
+	 * more tick */
+	if (unlikely(next_tick - now < halftick)) {
 		nticks++;
+		next_tick += clocktick;
 	}
 	mtctl(next_tick, 16);
 	cpu_data[cpu].it_value = next_tick;
+	local_irq_restore(flags);
 
 	while (nticks--) {
 #ifdef CONFIG_SMP


_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Carlos O'Donell]

On 9/2/06, James Bottomley <James.Bottomley@steeleye.com> wrote:
> Actually, according to my analysis on ioz (pa8800) there seem to be some
> hidden issues with our implementation (i.e. it's not the mathematics).

Thanks for the review.

> The first problem is that interrupts are re-entrant, so the timer
> interrupt can get re-interrupted.  If this happens between the mfctl(16)
> and the mtctl(), which is made much longer by the use of while loops,
> then there's a small possibility that the interrupt caused us to miss
> the next tick (i.e. cr16 moved beyond next_tick while in the interrupt).
> I see this very occasionally on the pa8800 caused by flush IPIs (since
> the cache is so huge) ... it's probably caused by SCSI interrupts on the
> C3xxx that everyone else is testing with.  However, when this happens,
> you have to wait for cr16 to wrap before you get another timer
> interrupt, which I believe to be the source of the time jumps and
> negative offsets in gettimeoffset().

You address two issues here 1) Long times between timer_interrupts,
2) negative offsets in gettimeoffset().

The first issue is a problem I had not considered. It is a very likely
scenario that timer_interrupt is interrupted by another
timer_interrupt, and overwrites the cr16 value of the most recent
interrupt. Your patch here is definately correct, I had considered the
reentrancy of this function.

Your guess that this is the solution to problem 2) is not quite right.
I will argue that the "halftick" counting is at fault here. When a
"halftick" is counted as a full tick the system time moves into the
future. All calls to gettimeoffset must therefore return negative
adjustments. I think removing the erroneous halftick counting is the
solution to issue 2.

> My proposed fix for this is below.  However, we seem to have a few other
> issues:
>
>      1. On SMP, cr16 of the secondary processors (and next_tick) is
>         never initialised ... we just wait for the timer to wrap and
>         then pick up ticking from there.
>      2. processor_probe() blows away all of the next_tick data when it's
>         called (once for every CPU)
>      3. We're regularly missing multiple ticks ... mainly below about
>         30 .. there must be some cause for this but I can't immediately
>         find it.

#3 is worrying.

>      4. we don't obey CONFIG_HZ at all the clock is always either 1000
>         for pa2.0 or 100 for pa1.0
>
> James
>
> diff --git a/arch/parisc/kernel/time.c b/arch/parisc/kernel/time.c
> index 5facc9b..93322a2 100644
> --- a/arch/parisc/kernel/time.c
> +++ b/arch/parisc/kernel/time.c
> @@ -48,9 +48,13 @@ irqreturn_t timer_interrupt(int irq, voi
>         long next_tick;
>         int nticks;
>         int cpu = smp_processor_id();
> +       unsigned long flags;
>
>         profile_tick(CPU_PROFILING, regs);
>
> +       /* Don't want to be interrupted while calculating
> +        * time offsets */
> +       local_irq_save(flags);
>         now = mfctl(16);
>         /* initialize next_tick to time at last clocktick */
>         next_tick = cpu_data[cpu].it_value;
> @@ -63,13 +67,24 @@ irqreturn_t timer_interrupt(int irq, voi
>          * Variables are *signed*.
>          */
>
> -       nticks = 0;
> -       while((next_tick - now) < halftick) {
> +       /* Don't do expensive mul and div for the likely case */
> +       if (likely(now - next_tick < clocktick)) {
> +               nticks = 1;
>                 next_tick += clocktick;
> +       } else {
> +               nticks = ((now - next_tick)/clocktick) + 1;
> +               next_tick += clocktick*nticks;
> +       }
> +       /* Don't interrupt too much.  If we only have half
> +        * the time to go to the next tick, push it out one
> +        * more tick */
> +       if (unlikely(next_tick - now < halftick)) {
>                 nticks++;
> +               next_tick += clocktick;
>         }
>         mtctl(next_tick, 16);
>         cpu_data[cpu].it_value = next_tick;
> +       local_irq_restore(flags);
>
>         while (nticks--) {
>  #ifdef CONFIG_SMP
>

Grant, we should merge James' fix into the current working patch for
timer cleanups.

Cheers,
Carlos.
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[James Bottomley]

On Sun, 2006-09-03 at 11:00 -0400, Carlos O'Donell wrote:
> You address two issues here 1) Long times between timer_interrupts,
> 2) negative offsets in gettimeoffset().
> 
> The first issue is a problem I had not considered. It is a very likely
> scenario that timer_interrupt is interrupted by another
> timer_interrupt, and overwrites the cr16 value of the most recent
> interrupt. Your patch here is definately correct, I had considered the
> reentrancy of this function.

Actually, we don't have a re-entrancy problem: the way the EIEM works,
we can't get another timer_interrupt until we come out of this one.  We
can, however, get all other interrupts in this code.   Like I said, on
pa8800 the culprit was cache flushing IPI's, which can take > 1ms to
execute (because the cache is so huge).

> Your guess that this is the solution to problem 2) is not quite right.
> I will argue that the "halftick" counting is at fault here. When a
> "halftick" is counted as a full tick the system time moves into the
> future. All calls to gettimeoffset must therefore return negative
> adjustments. I think removing the erroneous halftick counting is the
> solution to issue 2.

Memory is cheap in this array.  What we should really have is two cycle
values:  prev_tick and next_tick.  Then we can run do_gettimeoffset from
prev_tick (the cycle value at last interrupt) and thus not muck about
trying to work out from jiffies if this is a halftick or a multiple
tick.

James



_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[James Bottomley]

On Sun, 2006-09-03 at 11:00 -0400, Carlos O'Donell wrote:
> Your guess that this is the solution to problem 2) is not quite right.
> I will argue that the "halftick" counting is at fault here. When a
> "halftick" is counted as a full tick the system time moves into the
> future. All calls to gettimeoffset must therefore return negative
> adjustments. I think removing the erroneous halftick counting is the
> solution to issue 2.


Actually, I think we just accept it as a feature rather than a bug.
Since the timer interrupts miss so many ticks, halftick processing looks
like a good idea to me.  Thus, we have to assume gettimeoffset() can be
negative by up to half a tick.  The current processing in
do_gettimeofday() already copes nicely with this.

James


_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Sun, Sep 03, 2006 at 11:14:53AM -0500, James Bottomley wrote:
> Since the timer interrupts miss so many ticks, halftick processing looks
> like a good idea to me.

I was going to argue halfticks are a bad idea.
They just make it all more complicated.
My last version of the rewrite patch does away with them complete.

>   Thus, we have to assume gettimeoffset() can be
> negative by up to half a tick.  The current processing in
> do_gettimeofday() already copes nicely with this.

It deals nicely _without_ halfticks too.

grant
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Sat, Sep 02, 2006 at 10:52:06AM -0500, James Bottomley wrote:
> The first problem is that interrupts are re-entrant, so the timer
> interrupt can get re-interrupted.

Doesn't this violate one of the basic tenants of linux interrupts?

I know the interrupt handler (same instance) can't be invoked on
two different CPUs and it seems re-entrance would be a similar
case.

>      1. On SMP, cr16 of the secondary processors (and next_tick) is
>         never initialised ... we just wait for the timer to wrap and
>         then pick up ticking from there.

I saw that too and happen to have committed the fix for it last night.

>      2. processor_probe() blows away all of the next_tick data when it's
>         called (once for every CPU)

Fixed that too :)

>      3. We're regularly missing multiple ticks ... mainly below about
>         30 .. there must be some cause for this but I can't immediately
>         find it.

Ok. I'm not sure how to look for that either.

>      4. we don't obey CONFIG_HZ at all the clock is always either 1000
>         for pa2.0 or 100 for pa1.0

Also committed a fix for that.

> diff --git a/arch/parisc/kernel/time.c b/arch/parisc/kernel/time.c

Is it ok if I only add the irqsave/restore to my current patch?
I also like the "avoid div/mul ops" test too.

I'd like to defer discussion on halfticks for now.
I consider that an optimization we can defer for now.

thanks,
grant
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[John David Anglin]

> Is it ok if I only add the irqsave/restore to my current patch?
> I also like the "avoid div/mul ops" test too.

I agree on that.  They are very expensive, especially in 64-bit code.

I'm playing with the patch below.  The main thing I tried to do is
reduce the amount of code in the irqsave/restore.  GCC didn't do a
great job of optimizing the code.  I think we would get better code
if clocktick and halftick were copied to temps before the irqsave.

I was also concerned about nticks not being unsigned long.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)

Index: time.c
===================================================================
RCS file: /var/cvs/linux-2.6/arch/parisc/kernel/time.c,v
retrieving revision 1.16
diff -u -p -u -r1.16 time.c
--- time.c	24 Jun 2006 16:05:18 -0000	1.16
+++ time.c	3 Sep 2006 19:42:24 -0000
@@ -47,29 +47,34 @@ irqreturn_t timer_interrupt(int irq, voi
 {
 	long now;
 	long next_tick;
-	int nticks;
+	unsigned long nticks = 0;
 	int cpu = smp_processor_id();
+	long flags;
 
 	profile_tick(CPU_PROFILING, regs);
 
-	now = mfctl(16);
-	/* initialize next_tick to time at last clocktick */
+	/* Initialize next_tick to time at last clocktick */
 	next_tick = cpu_data[cpu].it_value;
 
-	/* since time passes between the interrupt and the mfctl()
-	 * above, it is never true that last_tick + clocktick == now.  If we
-	 * never miss a clocktick, we could set next_tick = last_tick + clocktick
-	 * but maybe we'll miss ticks, hence the loop.
+	/* Since time passes between the interrupt and the mfctl(),
+	 * it is never true that last_tick + clocktick == now.
+	 * If we never miss a clocktick, we could set
+	 * next_tick = last_tick + clocktick, * but maybe we'll miss
+	 * ticks, hence the loop.
 	 *
 	 * Variables are *signed*.
 	 */
 
-	nticks = 0;
+	/* Don't want to be interrupted while calculating
+	 * the time for the next tick.  */
+	local_irq_save(flags);
+	now = mfctl(16);
 	while((next_tick - now) < halftick) {
 		next_tick += clocktick;
 		nticks++;
 	}
 	mtctl(next_tick, 16);
+	local_irq_restore(flags);
 	cpu_data[cpu].it_value = next_tick;
 
 	while (nticks--) {
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Sun, Sep 03, 2006 at 03:59:34PM -0400, John David Anglin wrote:
> > Is it ok if I only add the irqsave/restore to my current patch?
> > I also like the "avoid div/mul ops" test too.
> 
> I agree on that.  They are very expensive, especially in 64-bit code.
> 
> I'm playing with the patch below.  The main thing I tried to do is
> reduce the amount of code in the irqsave/restore.

I've not applied the irqsave/restore since I don't think it does anything.
do_cpu_irq_mask() doesn't allow nested external interrupts.

> GCC didn't do a great job of optimizing the code.  I think we would
> get better code if clocktick and halftick were copied to temps before
> the irqsave.

hrm...I would expect the same result from __read_mostly but can understand
why that's not as useful as I hoped.

Can we tell GCC that clocktick doesn't change during execution of this code?
ie despite being a global, it's a "constant" and doesn't need to be
reloaded on each loop iteration?


> I was also concerned about nticks not being unsigned long.

I agree. I'm leaning very strongly in favor of the unsigned version
of the code. Even though I think Carlos demonstrated the signed
math is correct. So unless someone objects to the unsigned version
I posted earlier soon (assuming I address all bug fixes), I'd like
to commit that in the next couple of days.

thanks,
grant

> 
> Dave
> -- 
> J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
> National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)
> 
> Index: time.c
> ===================================================================
> RCS file: /var/cvs/linux-2.6/arch/parisc/kernel/time.c,v
> retrieving revision 1.16
> diff -u -p -u -r1.16 time.c
> --- time.c	24 Jun 2006 16:05:18 -0000	1.16
> +++ time.c	3 Sep 2006 19:42:24 -0000
> @@ -47,29 +47,34 @@ irqreturn_t timer_interrupt(int irq, voi
>  {
>  	long now;
>  	long next_tick;
> -	int nticks;
> +	unsigned long nticks = 0;
>  	int cpu = smp_processor_id();
> +	long flags;
>  
>  	profile_tick(CPU_PROFILING, regs);
>  
> -	now = mfctl(16);
> -	/* initialize next_tick to time at last clocktick */
> +	/* Initialize next_tick to time at last clocktick */
>  	next_tick = cpu_data[cpu].it_value;
>  
> -	/* since time passes between the interrupt and the mfctl()
> -	 * above, it is never true that last_tick + clocktick == now.  If we
> -	 * never miss a clocktick, we could set next_tick = last_tick + clocktick
> -	 * but maybe we'll miss ticks, hence the loop.
> +	/* Since time passes between the interrupt and the mfctl(),
> +	 * it is never true that last_tick + clocktick == now.
> +	 * If we never miss a clocktick, we could set
> +	 * next_tick = last_tick + clocktick, * but maybe we'll miss
> +	 * ticks, hence the loop.
>  	 *
>  	 * Variables are *signed*.
>  	 */
>  
> -	nticks = 0;
> +	/* Don't want to be interrupted while calculating
> +	 * the time for the next tick.  */
> +	local_irq_save(flags);
> +	now = mfctl(16);
>  	while((next_tick - now) < halftick) {
>  		next_tick += clocktick;
>  		nticks++;
>  	}
>  	mtctl(next_tick, 16);
> +	local_irq_restore(flags);
>  	cpu_data[cpu].it_value = next_tick;
>  
>  	while (nticks--) {
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[John David Anglin]

> > GCC didn't do a great job of optimizing the code.  I think we would
> > get better code if clocktick and halftick were copied to temps before
> > the irqsave.
> 
> hrm...I would expect the same result from __read_mostly but can understand
> why that's not as useful as I hoped.

They are getting relead on every use.

> Can we tell GCC that clocktick doesn't change during execution of this code?
> ie despite being a global, it's a "constant" and doesn't need to be
> reloaded on each loop iteration?

I think it's tricky.  Constants go in readonly data.  However, the
values need to be initialized at runtime.  Copying the values to
"register" tempories before the loop seems to resolve the problem.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[John David Anglin]

> I've not applied the irqsave/restore since I don't think it does anything.
> do_cpu_irq_mask() doesn't allow nested external interrupts.

I updated what I'm testing to remove the irqsave/restore.  I'm interested
to see if this helps various random failures that occur, particularly in
the libjava testsuite with thread intensive code.

> > GCC didn't do a great job of optimizing the code.  I think we would
> > get better code if clocktick and halftick were copied to temps before
> > the irqsave.
> 
> hrm...I would expect the same result from __read_mostly but can understand
> why that's not as useful as I hoped.

#define __read_mostly __attribute__((__section__(".data.read_mostly")))

GCC doesn't do anything special with this section as far as I can tell.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)

Index: time.c
===================================================================
RCS file: /var/cvs/linux-2.6/arch/parisc/kernel/time.c,v
retrieving revision 1.16
diff -u -p -u -r1.16 time.c
--- time.c	24 Jun 2006 16:05:18 -0000	1.16
+++ time.c	4 Sep 2006 03:26:43 -0000
@@ -47,26 +47,38 @@ irqreturn_t timer_interrupt(int irq, voi
 {
 	long now;
 	long next_tick;
-	int nticks;
+	unsigned long nticks = 0;
+	long ct = clocktick;
+	long ht = halftick;
 	int cpu = smp_processor_id();
 
 	profile_tick(CPU_PROFILING, regs);
 
-	now = mfctl(16);
-	/* initialize next_tick to time at last clocktick */
+	/* Initialize next_tick to time of last clocktick */
 	next_tick = cpu_data[cpu].it_value;
 
-	/* since time passes between the interrupt and the mfctl()
-	 * above, it is never true that last_tick + clocktick == now.  If we
-	 * never miss a clocktick, we could set next_tick = last_tick + clocktick
-	 * but maybe we'll miss ticks, hence the loop.
+	/* Since time passes between the interrupt and the mfctl(),
+	 * it is never true that last_tick + clocktick == now.
+	 * If we never missed a clocktick, we could set
+	 * next_tick = last_tick + clocktick, but maybe we'll
+	 * miss ticks, hence the loop.  It also ensures that the
+	 * count for the next interrupt is at least a half tick
+	 * away.
+	 *
+	 * Variables are *signed*.  As a result, onc cycle of ticks
+	 * will be missed if interrupt latency every causes the 
+	 * difference between next_tick and now to exceed roughly
+	 * half the 32-bit wrap counter period.
+	 *
+	 * We only use local automatic variables in the loop to
+	 * avoid the possibility of an interruption delaying the
+	 * setting of cr16 for the next tick.
 	 *
-	 * Variables are *signed*.
 	 */
 
-	nticks = 0;
-	while((next_tick - now) < halftick) {
-		next_tick += clocktick;
+	now = mfctl(16);
+	while((next_tick - now) < ht) {
+		next_tick += ct;
 		nticks++;
 	}
 	mtctl(next_tick, 16);
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[James Bottomley]

On Sun, 2006-09-03 at 13:38 -0600, Grant Grundler wrote:
> Doesn't this violate one of the basic tenants of linux interrupts?
> 
> I know the interrupt handler (same instance) can't be invoked on
> two different CPUs and it seems re-entrance would be a similar
> case.

re-entrant is the wrong word ... however all linux interrupt handlers
should be interruptible (unless they specifically disable interrupts).
Ours apparently still aren't, so I'll see about fixing them.

The timer interrupt is the exception, actually, because it's set
IRQF_DISABLED which means no interrupts in timer_interrupt() until
they're specifically enabled, which doesn't happen until well into the
softirq processing.

James


_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[James Bottomley]

On Sun, 2006-09-03 at 13:31 -0600, Grant Grundler wrote:
> On Sun, Sep 03, 2006 at 11:14:53AM -0500, James Bottomley wrote:
> > Since the timer interrupts miss so many ticks, halftick processing looks
> > like a good idea to me.
> 
> I was going to argue halfticks are a bad idea.
> They just make it all more complicated.
> My last version of the rewrite patch does away with them complete.

I tried this on ioz ... you can simply remove the halftick code in my
version of the patch.  What happens is that we start to drop astonishing
number of ticks occasionally ... it looks like we're getting wrap
conditions again.

James


_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[John David Anglin]

> On Sun, 2006-09-03 at 13:31 -0600, Grant Grundler wrote:
> > On Sun, Sep 03, 2006 at 11:14:53AM -0500, James Bottomley wrote:
> > > Since the timer interrupts miss so many ticks, halftick processing looks
> > > like a good idea to me.
> > 
> > I was going to argue halfticks are a bad idea.
> > They just make it all more complicated.
> > My last version of the rewrite patch does away with them complete.
> 
> I tried this on ioz ... you can simply remove the halftick code in my
> version of the patch.  What happens is that we start to drop astonishing
> number of ticks occasionally ... it looks like we're getting wrap
> conditions again.

There needs to be a check to ensure that the code has enough time
to set cr16 with the new compare time before the counter passes this
value.  If it misses, the counter will wrap.  This probably doesn't
need to be a full half tick if it's desireable to avoid negative
offsets.

In my mind, it's important to ensure that timer interrupts are not
disabled for long periods.  If that's not possible, we could go back
to 100 Hz.  However, I've been using 1000 Hz in an embedded project
using a small 8-bit micro running at 40 MHz.  So, I think 1000 Hz
should be possible on most PA processors.

I've reworked my previous patch to use unsigned variables.  As a
result, it can handle twice the latency.  There's one unlikely case
that could be detected.  That's an exact wrap of the counter
(next_tick == now).  This is extremely unlikely on LP64.  On 32-bit
kernels, we can't handle latencies larger than 0x100000000, so it
didn't seem worthwhile checking for this special case.

There's weren't any problems with the libjava testsuite with the
last patch, but one run probably isn't enough to be sure that this
change helps.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)

Index: time.c
===================================================================
RCS file: /var/cvs/linux-2.6/arch/parisc/kernel/time.c,v
retrieving revision 1.16
diff -u -p -u -r1.16 time.c
--- time.c	24 Jun 2006 16:05:18 -0000	1.16
+++ time.c	4 Sep 2006 16:29:34 -0000
@@ -36,8 +36,8 @@
 /* xtime and wall_jiffies keep wall-clock time */
 extern unsigned long wall_jiffies;
 
-static long clocktick __read_mostly;	/* timer cycles per tick */
-static long halftick __read_mostly;
+static unsigned long clocktick __read_mostly;	/* timer cycles per tick */
+static unsigned long halftick __read_mostly;
 
 #ifdef CONFIG_SMP
 extern void smp_do_timer(struct pt_regs *regs);
@@ -45,28 +45,41 @@ extern void smp_do_timer(struct pt_regs 
 
 irqreturn_t timer_interrupt(int irq, void *dev_id, struct pt_regs *regs)
 {
-	long now;
-	long next_tick;
-	int nticks;
+	unsigned long now;
+	unsigned long next_tick;
+	unsigned long nticks = 0;
+	unsigned long ct = clocktick;
+	unsigned long ht = halftick;
 	int cpu = smp_processor_id();
 
 	profile_tick(CPU_PROFILING, regs);
 
-	now = mfctl(16);
-	/* initialize next_tick to time at last clocktick */
+	/* Initialize next_tick to time of last clocktick */
 	next_tick = cpu_data[cpu].it_value;
 
-	/* since time passes between the interrupt and the mfctl()
-	 * above, it is never true that last_tick + clocktick == now.  If we
-	 * never miss a clocktick, we could set next_tick = last_tick + clocktick
-	 * but maybe we'll miss ticks, hence the loop.
+	/* Since time passes between the interrupt and the mfctl(),
+	 * it is never true that last_tick + clocktick == now.
+	 * If we never missed a clocktick, we could set
+	 * next_tick = last_tick + clocktick, but maybe we'll
+	 * miss ticks, hence the loop.  It also ensures that the
+	 * count for the next interrupt is at least a half tick
+	 * away.
+	 *
+	 * We use local automatic variables to avoid the
+	 * possibility of an interruption delaying the setting
+	 * of cr16 for the next tick.
 	 *
-	 * Variables are *signed*.
 	 */
 
-	nticks = 0;
-	while((next_tick - now) < halftick) {
-		next_tick += clocktick;
+	now = mfctl(16);
+	while((now - next_tick) >= ct) {
+		next_tick += ct;
+		nticks++;
+	}
+	next_tick += ct;
+	nticks++;
+	if ((next_tick - now) < ht) {
+		next_tick += ct;
 		nticks++;
 	}
 	mtctl(next_tick, 16);
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[James Bottomley]

On Mon, 2006-09-04 at 12:57 -0400, John David Anglin wrote:
> There needs to be a check to ensure that the code has enough time
> to set cr16 with the new compare time before the counter passes this
> value.  If it misses, the counter will wrap.  This probably doesn't
> need to be a full half tick if it's desireable to avoid negative
> offsets.

Exactly!

> In my mind, it's important to ensure that timer interrupts are not
> disabled for long periods.  If that's not possible, we could go back
> to 100 Hz.  However, I've been using 1000 Hz in an embedded project
> using a small 8-bit micro running at 40 MHz.  So, I think 1000 Hz
> should be possible on most PA processors.

Well ... I'm not sure about the rest of the PA world.  It's certainly
not possible on ioz (or any other pa8800).  According to my benchmarks,
the cache flush IPI takes 47ms to execute.  However, the pa8800 has such
a huge cache, it might not take this long on the other PA boxes.

James


_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[John David Anglin]

> On Mon, 2006-09-04 at 12:57 -0400, John David Anglin wrote:
> > There needs to be a check to ensure that the code has enough time
> > to set cr16 with the new compare time before the counter passes this
> > value.  If it misses, the counter will wrap.  This probably doesn't
> > need to be a full half tick if it's desireable to avoid negative
> > offsets.
> 
> Exactly!

The loop in the last timer patch that I sent, as compiled for a 32-bit 
c3k kernel, is four instructions.  Using a 500 us half tick time and
assuming a slow 50 MHz cpu, I estimate we should be able to handle
latencies up to about 6 seconds.  The maximum latency time for faster
cpus are proportionately longer.  That should be enough to handle most
circumstances except for an uninitialized tick value.  Another loop
could be added with a larger decrement if we need to handle larger
latencies.

I'd hoped that improving the handling of timer interrupts might
fix the behavior of expect, but it doesn't.  If I run the binutils
ld testsuite under load, it usually hangs at the end of the test:

dave     28731 28706  4 14:56 pts/1    00:00:25 expect -- /usr/share/dejagnu/runtest.exp --tool ld --srcdir /home/dave/gnu/binutils-2.16.91/src/ld/testsuite CC=gcc -L/home/dave/gnu/binutils-2.16.91/objdir/./ld CFLAGS=-g -O2 CXX=c++ -L/home/dave/gnu/binutils-2.16.91/objdir/./ld CXXFLAGS=-g -O2 CC_FOR_HOST=gcc CFLAGS_FOR_HOST=-g -O2 OFILES=ldgram.o ldlex.o lexsup.o ldlang.o mri.o ldctor.o ldmain.o ldwrite.o ldexp.o  ldemul.o ldver.o ldmisc.o ldfile.o ldcref.o ehppalinux.o  BFDLIB=../bfd/.libs/libbfd.a LIBIBERTY=../libiberty/libiberty.a  LIBS=
dave     28751 28731  0 14:56 pts/1    00:00:00 [expect] <defunct>

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Mon, Sep 04, 2006 at 12:57:25PM -0400, John David Anglin wrote:
> There needs to be a check to ensure that the code has enough time
> to set cr16 with the new compare time before the counter passes this
> value.  If it misses, the counter will wrap.  This probably doesn't
> need to be a full half tick if it's desireable to avoid negative
> offsets.

Yes - I agree. I think this is the last bug in my code.
I'll just "skip" one tick in that case.
My guess is we'll never need more than a 0x1000 cycles
to read CR16, calculate the new "next_tick" and write CR16.

I picked 0x1000 because it very easy to test for: "if (x >> 12)...".

I'll review the your patch and see if I missed anything else
and then post version #4 (or #5?). Lost count.

grant

_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[James Bottomley]

On Mon, 2006-09-04 at 15:21 -0600, Grant Grundler wrote:
> \Yes - I agree. I think this is the last bug in my code.
> I'll just "skip" one tick in that case.
> My guess is we'll never need more than a 0x1000 cycles
> to read CR16, calculate the new "next_tick" and write CR16.
> 
> I picked 0x1000 because it very easy to test for: "if (x >> 12)...".
> 
> I'll review the your patch and see if I missed anything else
> and then post version #4 (or #5?). Lost count.

This is the one I'm using that seems most stable (no more > 9 lost
ticks, even on a pa8800).  However, to get it this stable, I do require
nested interrupts.  It also does halftick processing as Grant does, so
it doesn't ever push the time into the future, it just holds off one
tick beyond where we currently are.

James

Index: parisc-2.6/arch/parisc/kernel/time.c
===================================================================
--- parisc-2.6.orig/arch/parisc/kernel/time.c	2006-09-03 21:07:45.000000000 -0700
+++ parisc-2.6/arch/parisc/kernel/time.c	2006-09-04 15:07:33.000000000 -0700
@@ -48,6 +48,7 @@
 	long next_tick;
 	int nticks;
 	int cpu = smp_processor_id();
+	unsigned long cr16_val;
 
 	profile_tick(CPU_PROFILING, regs);
 
@@ -63,12 +64,24 @@
 	 * Variables are *signed*.
 	 */
 
-	nticks = 0;
-	while((next_tick - now) < halftick) {
+	/* Don't do expensive mul and div for the likely case */
+	if (likely(now - next_tick < clocktick)) {
+		nticks = 1;
 		next_tick += clocktick;
-		nticks++;
+	} else {
+		nticks = ((now - next_tick)/clocktick) + 1;
+		next_tick += clocktick*nticks;
+	}
+	/* Don't interrupt too much.  If we only have half
+	 * the time to go to the next tick, push it out one
+	 * more tick */
+	cr16_val = next_tick;
+	if (unlikely(next_tick - now < halftick)) {
+		/* don't increment nticks ... the next
+		 * tick will take care of that */
+		cr16_val += clocktick;
 	}
-	mtctl(next_tick, 16);
+	mtctl(cr16_val, 16);
 	cpu_data[cpu].it_value = next_tick;
 
 	while (nticks--) {


_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[John David Anglin]

> +	if (likely(now - next_tick < clocktick)) {
> +		nticks = 1;
>  		next_tick += clocktick;
> -		nticks++;
> +	} else {
> +		nticks = ((now - next_tick)/clocktick) + 1;
> +		next_tick += clocktick*nticks;
> +	}

I'd rather loop if now - next_tick isn't too many ticks.  Integer
division and multiplation are very expensive, particularly when
running in 64-bit mode.  We don't have optimized millicode to do it.
So, I don't much like falling into the unlikely case if we are just
delayed one tick.

I'm still concerned that we may take a TLB exception in this code
and substantially increase the calculation time.

It's somewhat unclear whether any of these tweaks will solve the
B160 issue.  The halftick margin may not be enough in the slow
path at 1000 Hz and decreasing the tick rate may be the only fix
on slow machines.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Mon, Sep 04, 2006 at 07:52:51PM -0400, John David Anglin wrote:
> > +	if (likely(now - next_tick < clocktick)) {
> > +		nticks = 1;
> >  		next_tick += clocktick;
> > -		nticks++;
> > +	} else {
> > +		nticks = ((now - next_tick)/clocktick) + 1;
> > +		next_tick += clocktick*nticks;
> > +	}
> 
> I'd rather loop if now - next_tick isn't too many ticks.

Yeah, but we don't know how many times we will loop unless
we've already done the math.

>  Integer division and multiplation are very expensive, particularly when
> running in 64-bit mode.  We don't have optimized millicode to do it.
> So, I don't much like falling into the unlikely case if we are just
> delayed one tick.

How many loops would be a reasonable tradeoff? 5? 10?
We'd need a histogram from a "slow" machine to see that tradeoff.


> I'm still concerned that we may take a TLB exception in this code
> and substantially increase the calculation time.

Hrm...what would cause a TLB exception in timer_interrupt?
Accessing a global var?

> It's somewhat unclear whether any of these tweaks will solve the
> B160 issue.  The halftick margin may not be enough in the slow
> path at 1000 Hz and decreasing the tick rate may be the only fix
> on slow machines.

I'm pretty sure the halftick margin will be plenty.
At 1000Hz, a 50Mhz machine will have 50K cycles per tick.
Even with cache miss for global var (let's say ~300 cycles),
8 cycles for CR16 reads, 300-400 cycles for the math (using div/mul)
we are still under 1K cycles of processing. Say I'm off by a
factor or 2 or 4 and it's still a pretty wide margin.

Instead of a global var access for halftick, would a
hard coded value (e.g. 4k) that's easy to test for be
more efficient?

I'm still thinking of ~0xfffUL or (x>>12).

thanks,
grant
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[James Bottomley]

On Mon, 2006-09-04 at 23:12 -0600, Grant Grundler wrote:
> > I'm still concerned that we may take a TLB exception in this code
> > and substantially increase the calculation time.
> 
> Hrm...what would cause a TLB exception in timer_interrupt?
> Accessing a global var?

A TLB miss could be caused by either code or data ... we only have a few
hundred entries, so the chances of the timer_interrupt code or data
being not in the TLB cache are high.

However, the TLB miss handling code is pretty speedy ... we can
certainly fill a TLB entry in around 20 instructions on the fast path.

James


_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Tue, Sep 05, 2006 at 10:53:34AM -0500, James Bottomley wrote:
> On Mon, 2006-09-04 at 23:12 -0600, Grant Grundler wrote:
> > > I'm still concerned that we may take a TLB exception in this code
> > > and substantially increase the calculation time.
> > 
> > Hrm...what would cause a TLB exception in timer_interrupt?
> > Accessing a global var?
> 
> A TLB miss could be caused by either code or data ... we only have a few
> hundred entries, so the chances of the timer_interrupt code or data
> being not in the TLB cache are high.

If we only have one TLB entry for kernel text (code), we should
never have a miss because of code accesses. I thought that was
the case but don't know for sure. ISTR some discussion about
use of BTLB (PA1.1) and Large Pages (PA 2.0) hardwired for kernel.

Kernel data would probably benefit too.

> However, the TLB miss handling code is pretty speedy ... we can
> certainly fill a TLB entry in around 20 instructions on the fast path.

Add trap latency (e.g. sync/RFI) and it's still pretty small (not more
than "hundreds" of cycles.  I'm worried about orders of magnitutude
bigger latencies.

thanks,
grant
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[James Bottomley]

On Tue, 2006-09-05 at 16:49 -0600, Grant Grundler wrote:
> If we only have one TLB entry for kernel text (code), we should
> never have a miss because of code accesses. I thought that was
> the case but don't know for sure. ISTR some discussion about
> use of BTLB (PA1.1) and Large Pages (PA 2.0) hardwired for kernel.
> 
> Kernel data would probably benefit too.

Erm ... no, we never actually implemented this.  We still use 4k TLB
entries for the entire kernel and its data.

> Add trap latency (e.g. sync/RFI) and it's still pretty small (not more
> than "hundreds" of cycles.  I'm worried about orders of magnitutude
> bigger latencies.

Right ... it's a source of potential delay, but not a significant one.

James


_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[John David Anglin]

> On Tue, Sep 05, 2006 at 10:53:34AM -0500, James Bottomley wrote:
> > On Mon, 2006-09-04 at 23:12 -0600, Grant Grundler wrote:
> > > > I'm still concerned that we may take a TLB exception in this code
> > > > and substantially increase the calculation time.
> > > 
> > > Hrm...what would cause a TLB exception in timer_interrupt?
> > > Accessing a global var?
> > 
> > A TLB miss could be caused by either code or data ... we only have a few
> > hundred entries, so the chances of the timer_interrupt code or data
> > being not in the TLB cache are high.
> 
> If we only have one TLB entry for kernel text (code), we should
> never have a miss because of code accesses. I thought that was
> the case but don't know for sure. ISTR some discussion about
> use of BTLB (PA1.1) and Large Pages (PA 2.0) hardwired for kernel.

Ok, I think we can rule out this as a significant cause for delay
in calculating the time for the next tick.

I brought it up because I think the only way the current code
fails are:

1) We take too long calculating the time for the next tick and
   then have to wait one complete 32-bit counter cycle for the
   next interrupt.  For the D160, we have about 27000 ticks per
   counter cycle.  The loop is four instructions.  We have 80000
   instruction cycles in a half tick.  Thus, we should be able
   to do about 20000 loop iterations in a half tick assuming
   assuming the cpu doesn't mispredict the branch.  Thus, we can't
   quite catch up a complete cycle but the current code can handle
   quite a large interrupt latency.

2) We have a huge interrupt latency and hit the half cycle limit
   present when using signed arithmetic.  The interrupt latency
   may not be real if the timer values are getting clobbered or
   not properly initialized.  Grant, you may have already fixed
   the problem with your recent patches.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[John David Anglin]

> >  Integer division and multiplation are very expensive, particularly when
> > running in 64-bit mode.  We don't have optimized millicode to do it.
> > So, I don't much like falling into the unlikely case if we are just
> > delayed one tick.
> 
> How many loops would be a reasonable tradeoff? 5? 10?
> We'd need a histogram from a "slow" machine to see that tradeoff.

The decision to loop versus division/multiplication can be made
based on the average number of cycles needed for the former versus
the latter.  If now - next_tick is less than nticks, then loop.
I'm sure the average number of cycles for division/multiplication
depends on whether the code is 32 bits or 64 bits.  Take a look
at __divdi3 if you want to see how horrible integer division is.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[John David Anglin]

> May I ask you which expect (and tcl) release did you use?

I use my own compiled version of expect built against tcl 8.3:

Expect version is       5.43.0
Tcl version is          8.3
Framework version is    1.4.4

I've had fewer issues with tcl 8.3.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[John David Anglin]

> The signed math works correctly as an approximation (off by 2) and I
> do admit I find no fault in the math, but it is still confusing.

The signed math works as long as the latency in delivering the
interruption is not larger than about half a cycle.  Once
next_tick - now >= halftick, then we stop updating next_tick
until the counter wraps.  Probably, this could be extended
using unsigned math but you still have to handle the wrap.

The other issue is to ensure that the compare value for the
next interrupt is set before the counter passes this count.
We could have an interruption between the read and write
of cr16 even with interrupts disabled.  So, I think we should
minimize memory accesses.  The enclosed change eliminates
the memory accesses.

It may be we don't need the save/restore if interrupts are disabled.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)

Index: time.c
===================================================================
RCS file: /var/cvs/linux-2.6/arch/parisc/kernel/time.c,v
retrieving revision 1.16
diff -u -p -u -r1.16 time.c
--- time.c	24 Jun 2006 16:05:18 -0000	1.16
+++ time.c	3 Sep 2006 21:17:25 -0000
@@ -47,29 +47,36 @@ irqreturn_t timer_interrupt(int irq, voi
 {
 	long now;
 	long next_tick;
-	int nticks;
+	unsigned long nticks = 0;
+	long ct = clocktick;
+	long ht = halftick;
 	int cpu = smp_processor_id();
+	long flags;
 
 	profile_tick(CPU_PROFILING, regs);
 
-	now = mfctl(16);
-	/* initialize next_tick to time at last clocktick */
+	/* Initialize next_tick to time at last clocktick */
 	next_tick = cpu_data[cpu].it_value;
 
-	/* since time passes between the interrupt and the mfctl()
-	 * above, it is never true that last_tick + clocktick == now.  If we
-	 * never miss a clocktick, we could set next_tick = last_tick + clocktick
-	 * but maybe we'll miss ticks, hence the loop.
+	/* Since time passes between the interrupt and the mfctl(),
+	 * it is never true that last_tick + clocktick == now.
+	 * If we never miss a clocktick, we could set
+	 * next_tick = last_tick + clocktick, * but maybe we'll miss
+	 * ticks, hence the loop.
 	 *
 	 * Variables are *signed*.
 	 */
 
-	nticks = 0;
-	while((next_tick - now) < halftick) {
-		next_tick += clocktick;
+	/* Don't want to be interrupted while calculating
+	 * the time for the next tick.  */
+	local_irq_save(flags);
+	now = mfctl(16);
+	while((next_tick - now) < ht) {
+		next_tick += ct;
 		nticks++;
 	}
 	mtctl(next_tick, 16);
+	local_irq_restore(flags);
 	cpu_data[cpu].it_value = next_tick;
 
 	while (nticks--) {
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Carlos O'Donell]

On 9/3/06, Grant Grundler <grundler@parisc-linux.org> wrote:
> I'll rework my code later today to try to match the discussion so far.

Original code:

 58         now = mfctl(16);
 60         next_tick = cpu_data[cpu].it_value;
 70         nticks = 0;
 71         while((next_tick - now) < halftick) {
 72                 next_tick += clocktick;
 73                 nticks++;
 74         }
 75         mtctl(next_tick, 16);
 76         cpu_data[cpu].it_value = next_tick;

1. Let us assume a 32-bit CPU with a 32-bit counter and a 32-bit
trigger register.
2. Assume that it_value is *near* the signed long boundary (0x7fffff)
3. The counter and trigger match, raising an interrupt.
4. During the interrupt delivery cr16 wraps into negative signed long,
but only a little bit.
    Let us say cr16 is ~(0x7fffffff + 50)
5. The value "next_tick - now" is equivalent to:
    "next_tick - (-now)" since now is negative.
    "next_tick + now"
6. The signed long math wraps, and the solution is a small negative
number, or small positive number, in this case it is +48.
7. The while loop adds clockticks until we are positive and bigger
than halftick. Adding 1 clocktick.

The signed math works correctly as an approximation (off by 2) and I
do admit I find no fault in the math, but it is still confusing.

However, as James points out, if the *real* cr16 gets ahead of the
newly set it_value, by delaying this function due to other interrupts,
then we will have to wait for a full wrap to have it trigger another
timer interrupt.

Cheers,
Carlos.
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[James Bottomley]

On Sun, 2006-09-03 at 13:55 -0600, Grant Grundler wrote:
> I'm not sure about that. James might be wrong in this case.
> See do_cpu_irq_mask().
> It clears EIEM and thus disables all external interrupts
> including the interval timer. The comment is wrong in that
> we disable all EIEM bits, not just TIMER and IPI.

Yes ... I thought I fixed that the last time I pulled this code apart,
but apparently not.

I'll concentrate on fixing this, since I suspect it is the root cause of
the horrible interrupt latencies causing the ticks to back up.

James


_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Sun, Sep 03, 2006 at 10:54:18AM -0400, Carlos O'Donell wrote:
> >Yes. I'm now pretty sure the fix for that will be in gettimeoffset()
> >and not in timer_interrupt(). But I agree the two functions are very
> >similar but have to handle slightly different corner cases.
> 
> I still disagree, if you see James most recent patch which disabled
> IRQ's while we handle the timer interrupt, you will see that both
> functions are closer to being similar :)

I'm not sure about that. James might be wrong in this case.
See do_cpu_irq_mask().
It clears EIEM and thus disables all external interrupts
including the interval timer. The comment is wrong in that
we disable all EIEM bits, not just TIMER and IPI.

> I will assert that at the end of the day we will be writing
> "cr16_offset" which is a generic function that can be called with
> interrupts disabled and *that* will handle all the corner cases and be
> called by "timer_interrupt" and "gettimeoffset".

hrm ok. I'll keep that in mind. I'm not convinced of that
yet since those are both performance critical piecves of code.

...
> >Sorry - this didn't make sense. Can you provide an example?
> >For simplicity assume a 5 bit counter and pick the values
> >that illustrate your case.
> 
> 5 bit counter.
> it_value = 5
> cr16 = ... free running.
> clocktick = 5
> halftick = 2
> 
> a. Counter goes off at 8. Expected to go off at 5.

Itimer will interrupt at 5 if it was expect to go off at 5.
timer_interrupt() will never get invoked until 8 becuase of
interrupt handling overhead.

> b. Since (8 - 5) == 3 > 2 or a halftick, we push forward 2 ticks
> c. Set it_value to 15.

Ok. I really don't like the business with halftick pushing
system time "into the future".  Maybe we can just drop one tick
on the floor. Ie skip it and handle it on the next "full" tick?

> 1. User calls gettimeofday.
> 2. cr16 says time is 9
> 3. The it_value is 15, subtract a clocktick and you get 10.
> 
> *boom*
> 
> The value of cr16 is < the value of a rolled back clocktick.
> In counting the halftick, we need to rollback the halftick in gettimeoffset.

No. We need to just drop the next tick and not count it until
the next round.

> >Division is much more expensive than integer multiplication.
> >Is there a way to do the division once _and_ get the remainder?
> >
> >My assumption that integer multiplication is "cheaper"
> >could be wrong.
> 
> I timed this for some reasonable values of dividend and divisor.
> The division and modulo operation is ~156 cycles.
> The integer multiplication is ~73 cycles.
> This is the average cr16 tick over 1000 runs.
> The integer multiplication is "cheaper"

ok - many thanks for doing that.

...
> You say the following equations are correct:
> 
> ticks_elapsed = (now - next_tick) / clocktick;
> remainder = now - (ticks_elapsed * clocktick);
> 
> The ticks_elapsed equation *is* correct.
> 
> The remainder equation is wrong. The value of "now" could be 4GB, the
> value of "next_tick" could be "4GB - clocktick", the ticks_elapsed
> value is 1. This is correct. However, the remainder is going to be
> "4GB - 1 * clocktick" which is incorrect. The remainder in this case
> is zero.

> 
> To get the remainder you *must* do:
> 
> remainder = (now - next_tick) - (ticks_elapsed * clocktick)
> 
> This gives you the left over ticks you didn't count. I have added
> brackets here to clarify the math.

Yes - got it now. thanks again!

> I have come to the conclusion that adding the halftick is conceptually 
> wrong.
> 
> Follow me on this.
> 
> 1. By adding the halftick, as a real tick, the system time moves into
> the future.

I'm already convinced this is wrong and leads to too many complications.

> 2. A system with future time means we need negative gettimeoffset 
> adjustments.
> 3. Negative gettimeoffset adjustment complicate things needlessly.
> 4. Halfticks should not be counted, and should be ignored.
> 5. Ignoring halfticks is not a problem, when the late timer interrupt
> arrives we will accrue all full ticks anyway.
> 
> What do you think?

total agreement.
I'll rework my code later today to try to match the discussion so far.

thanks,
grant
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Carlos O'Donell]

On 8/31/06, Grant Grundler <grundler@parisc-linux.org> wrote:
> I think it's arbitrary where the overflow occurs.
> Maybe unsigned math overflow is easier to visualize/understand.
> At least it is for me.

I agree with you, unsigned long code is easier to maintain.
Signed math overflow is implementation defined behaviour, it should
not be relied upon.

> Yes. I'm now pretty sure the fix for that will be in gettimeoffset()
> and not in timer_interrupt(). But I agree the two functions are very
> similar but have to handle slightly different corner cases.

I still disagree, if you see James most recent patch which disabled
IRQ's while we handle the timer interrupt, you will see that both
functions are closer to being similar :)

I will assert that at the end of the day we will be writing
"cr16_offset" which is a generic function that can be called with
interrupts disabled and *that* will handle all the corner cases and be
called by "timer_interrupt" and "gettimeoffset".

> I was thinking the opposite: I'm missing a "tick_elapsed" count
> on each timer interrupt.

That might also be the case.

> >  Does cr16 *actuall* count at the instruction rate, or
> > does it count at 1/2 rate?
>
> I _believe_ all implementations count at the actual rate.
> At least I'm not aware of any implementations that don't
> count at the advertized clock speed.

OK.

> > There is a bug here because of this, you are right to be warry of the
> > halftick adjustment. It is also needed in gettimeoffset, or "now" will
> > appear before "next_tick" without wrapping.
>
> Sorry - this didn't make sense. Can you provide an example?
> For simplicity assume a 5 bit counter and pick the values
> that illustrate your case.

5 bit counter.
it_value = 5
cr16 = ... free running.
clocktick = 5
halftick = 2

a. Counter goes off at 8. Expected to go off at 5.
b. Since (8 - 5) == 3 > 2 or a halftick, we push forward 2 ticks
c. Set it_value to 15.

1. User calls gettimeofday.
2. cr16 says time is 9
3. The it_value is 15, subtract a clocktick and you get 10.

*boom*

The value of cr16 is < the value of a rolled back clocktick.
In counting the halftick, we need to rollback the halftick in gettimeoffset.

> > What have you got against modulo?
>
> Modulo is a division.
> Division is much more expensive than integer multiplication.
> Is there a way to do the division once _and_ get the remainder?
>
> My assumption that integer multiplication is "cheaper"
> could be wrong.

I timed this for some reasonable values of dividend and divisor.
The division and modulo operation is ~156 cycles.
The integer multiplication is ~73 cycles.
This is the average cr16 tick over 1000 runs.
The integer multiplication is "cheaper"

> >  The correct math is as follows.
> >
> > remainder = now - next_tick - ticks_elapsed * clocktick;
>
> Erm, no.  ticks_elapsed was calculated here:
>         ticks_elapsed = (now - next_tick) / clocktick;
>
> (the line above.)
> I'm taking advantage of truncation since this is integer division.
> That make more sense?

Let us do some math.

You say the following equations are correct:

ticks_elapsed = (now - next_tick) / clocktick;
remainder = now - (ticks_elapsed * clocktick);

The ticks_elapsed equation *is* correct.

The remainder equation is wrong. The value of "now" could be 4GB, the
value of "next_tick" could be "4GB - clocktick", the ticks_elapsed
value is 1. This is correct. However, the remainder is going to be
"4GB - 1 * clocktick" which is incorrect. The remainder in this case
is zero.

To get the remainder you *must* do:

remainder = (now - next_tick) - (ticks_elapsed * clocktick)

This gives you the left over ticks you didn't count. I have added
brackets here to clarify the math.

> > >+               /* "now" is either early or cr16 wrapped.  */
> > >+               if (~next_tick < clocktick) {
> >
> > Too clever for me :)
>
> Now I'm worried. :)
> I've already removed this code in the version I'm working on now.

I was only joking here, but a comment is absolutely required when you
use clever 1's compliment tricks to approximate more compilcated
mathematics. Including a comment saying that it's 1 off.

> > Somwhere in thie function we need to makeup for the halftick...
>
> Hrm. I need to think more about that. You might be right.

I have come to the conclusion that adding the halftick is conceptually wrong.

Follow me on this.

1. By adding the halftick, as a real tick, the system time moves into
the future.
2. A system with future time means we need negative gettimeoffset adjustments.
3. Negative gettimeoffset adjustment complicate things needlessly.
4. Halfticks should not be counted, and should be ignored.
5. Ignoring halfticks is not a problem, when the late timer interrupt
arrives we will accrue all full ticks anyway.

What do you think?

Cheers,
Carlos.
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Fri, Sep 01, 2006 at 04:48:25PM -0600, Grant Grundler wrote:
> On Thu, Aug 31, 2006 at 12:53:27AM -0600, Grant Grundler wrote:
> > And I've hacked your version some more.
> > diff is below.
> 
> version #3: seems to be working fine on 64-bit SMP.
> 32-bit UP kernel is still under construction.
...
> gettimeoffset printk is busticated. I'll fix that in the next version.
> But it looks like wrapped values are causing problems.

Looks like only the printk is broken.

The attached test program (based on Guy's description) seems
to be working fine on 32-bit UP/b2600:
...
Time : 1157151360 sec, 106770 usec
Time : 1157151361 sec, 116765 usec
Time : 1157151362 sec, 126770 usec
Time : 1157151363 sec, 136764 usec
...

Note there is ~10ms shift on each "Time" output.
I believe this is because the task will run on the next
tick _after_ the 1 second time has expired.

hth,
grant


#include <stdio.h>
#include <sys/time.h>
#include <time.h>
main()
{
	struct timeval tv;

	while(gettimeofday(&tv, NULL) == 0) {
		printf("Time : %d sec, %d usec\n", tv.tv_sec, tv.tv_usec);
		sleep(1);
	}
}
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Thu, Aug 31, 2006 at 12:53:27AM -0600, Grant Grundler wrote:
> And I've hacked your version some more.
> diff is below.

version #3: seems to be working fine on 64-bit SMP.
32-bit UP kernel is still under construction.

That means gettimeoffset() hasn't been tested.
And I'm getting the following warnings on my b2600:
...
Setting the system clock..                                                      
timer_interrupt(CPU 0): delayed! run ntpdate ticks 859 cycles FFF51A1C rem 40E59C next/now FFFE7A9D/96080
gettimeoffset(CPU -119762782): missing ticks!cycles FFC87AE4 prev/now/next 6EBEA41/14C624/4C4B40  clock 0
gettimeoffset(CPU -177625053): missing ticks!cycles FFC87AE4 prev/now/next A5ED2C0/14C624/4C4B40  clock 12
gettimeoffset(CPU -238800592): missing ticks!cycles FFC87AE4 prev/now/next E0449B3/14C624/4C4B40  clock 12
gettimeoffset(CPU -302979574): missing ticks!cycles FFC87AE4 prev/now/next 11D794D9/14C624/4C4B40  clock 0
Sysgettimeoffset(CPU -361861366): missing ticks!cycles FFC87AE4 prev/now/next 155A0BD9/14C624/4C4B40  clock 12                                                  
tem Clock set. Local time: Fri Sep  1 22:42:09 UTC 2006. 

gettimeoffset printk is busticated. I'll fix that in the next version.
But it looks like wrapped values are causing problems.

The timer_interrupt warning might be reasonable given we are making
a call to firmware to set the clock and block interrupts for
the duration.


In addition to time.c, two more files are touched:
	smp.c	I couldn't see where slave CPUs would start
		the interval timer and added the call here.

	param.h	Use CONFIG_HZ for interval timer.
		We were ignored this before.

I just realized one small change to arch/parisc/kernel/processor.c
is missin from this diff. We don't want processor_probe() to clobber
CPU0's cpu_data. "it_value" has already been initialized.

enjoy!
grant


diff --git a/arch/parisc/kernel/smp.c b/arch/parisc/kernel/smp.c
index 98e4095..f33e8de 100644
--- a/arch/parisc/kernel/smp.c
+++ b/arch/parisc/kernel/smp.c
@@ -430,8 +430,9 @@ smp_do_timer(struct pt_regs *regs)
 static void __init
 smp_cpu_init(int cpunum)
 {
-	extern int init_per_cpu(int);  /* arch/parisc/kernel/setup.c */
+	extern int init_per_cpu(int);  /* arch/parisc/kernel/processor.c */
 	extern void init_IRQ(void);    /* arch/parisc/kernel/irq.c */
+	extern void start_cpu_itimer(void); /* arch/parisc/kernel/time.c */
 
 	/* Set modes and Enable floating point coprocessor */
 	(void) init_per_cpu(cpunum);
@@ -457,6 +458,7 @@ smp_cpu_init(int cpunum)
 	enter_lazy_tlb(&init_mm, current);
 
 	init_IRQ();   /* make sure no IRQ's are enabled or pending */
+	start_cpu_itimer();
 }
 
 
diff --git a/arch/parisc/kernel/time.c b/arch/parisc/kernel/time.c
index 5facc9b..337c4ec 100644
--- a/arch/parisc/kernel/time.c
+++ b/arch/parisc/kernel/time.c
@@ -35,8 +35,8 @@ #include <linux/timex.h>
 /* xtime and wall_jiffies keep wall-clock time */
 extern unsigned long wall_jiffies;
 
-static long clocktick __read_mostly;	/* timer cycles per tick */
-static long halftick __read_mostly;
+static unsigned long clocktick __read_mostly;	/* timer cycles per tick */
+static unsigned long halftick __read_mostly;
 
 #ifdef CONFIG_SMP
 extern void smp_do_timer(struct pt_regs *regs);
@@ -44,34 +44,77 @@ #endif
 
 irqreturn_t timer_interrupt(int irq, void *dev_id, struct pt_regs *regs)
 {
-	long now;
-	long next_tick;
-	int nticks;
+	unsigned long now;
+	unsigned long next_tick;
+	unsigned long cycles_elapsed;
+        unsigned long cycles_remainder;
+	unsigned long ticks_elapsed = 1;	/* at least one elapsed */
 	int cpu = smp_processor_id();
 
 	profile_tick(CPU_PROFILING, regs);
 
-	now = mfctl(16);
-	/* initialize next_tick to time at last clocktick */
+	/* Initialize next_tick to the expected tick time. */
 	next_tick = cpu_data[cpu].it_value;
 
-	/* since time passes between the interrupt and the mfctl()
-	 * above, it is never true that last_tick + clocktick == now.  If we
-	 * never miss a clocktick, we could set next_tick = last_tick + clocktick
-	 * but maybe we'll miss ticks, hence the loop.
-	 *
-	 * Variables are *signed*.
+	/* Get current interval timer.
+	 * CR16 reads as 64 bits in CPU wide mode.
+	 * CR16 reads as 32 bits in CPU narrow mode.
 	 */
+	now = mfctl(16);
+
+	cycles_elapsed = now - next_tick;
+
+	/* Determine how much time elapsed.  */
+	if (now < next_tick) {
+		/* Scenario 2: CR16 wrapped after clock tick.
+		 * 1's complement will give us the "elapse cycles".
+		 *
+		 * This "cr16 wrapped" cruft is primarily for 32-bit kernels.
+		 * So think "unsigned long is u32" when reading the code.
+		 * And yes, of course 64-bit will someday wrap, but only
+	  	 * every 198841 days on a 1GHz machine.
+		 */
+		cycles_elapsed = ~cycles_elapsed;   /* off by one cycle - don't care */
+	}
+
+	ticks_elapsed += cycles_elapsed / clocktick;
+	cycles_remainder = cycles_elapsed % clocktick;
 
-	nticks = 0;
-	while((next_tick - now) < halftick) {
-		next_tick += clocktick;
-		nticks++;
+	/* Can we differentiate between "early CR16" (aka Scenario 1) and
+	 * "long delay" (aka Scenario 3)? I don't think so.
+	 *
+	 * We expected timer_interrupt to be delivered at least a few hundred
+	 * cycles after the IT fires. But it's arbitrary how much time passes
+	 * before we call it "late". I've picked one second.
+	 */
+	if (ticks_elapsed > HZ) {
+		/* Scenario 3: very long delay?  bad in any case */
+		printk (KERN_CRIT "timer_interrupt(CPU %d): delayed! run ntpdate"
+			" ticks %ld cycles %lX rem %lX"
+			" next/now %lX/%lX\n",
+			cpu,
+			ticks_elapsed, cycles_elapsed, cycles_remainder,
+			next_tick, now );
+
+		ticks_elapsed = 1;	/* hack to limit damage in loop below */
 	}
+
+
+	/* Determine when (in CR16 cycles) next IT interrupt will fire.
+	 * We want IT to fire modulo clocktick even if we miss/skip some.
+	 * But those interrupts don't in fact get delivered that regularly.
+	 */
+	next_tick = now + (clocktick - cycles_remainder);
+
+	/* Program the IT when to deliver the next interrupt. */
+        /* Only bottom 32-bits of next_tick are written to cr16.  */
 	mtctl(next_tick, 16);
 	cpu_data[cpu].it_value = next_tick;
 
-	while (nticks--) {
+	/* Now that we are done mucking with unreliable delivery of interrupts,
+	 * go do system house keeping.
+	 */
+	while (ticks_elapsed--) {
 #ifdef CONFIG_SMP
 		smp_do_timer(regs);
 #else
@@ -124,21 +167,40 @@ #ifndef CONFIG_SMP
 	 *    Once parisc-linux learns the cr16 difference between processors,
 	 *    this could be made to work.
 	 */
-	long last_tick;
-	long elapsed_cycles;
+	unsigned long now;
+	unsigned long prev_tick;
+	unsigned long next_tick;
+	unsigned long elapsed_cycles;
+	unsigned long usec;
 
-	/* it_value is the intended time of the next tick */
-	last_tick = cpu_data[smp_processor_id()].it_value;
+	next_tick = cpu_data[smp_processor_id()].it_value;
+	now = mfctl(16);	/* Read the hardware interval timer.  */
 
-	/* Subtract one tick and account for possible difference between
-	 * when we expected the tick and when it actually arrived.
-	 * (aka wall vs real)
-	 */
-	last_tick -= clocktick * (jiffies - wall_jiffies + 1);
-	elapsed_cycles = mfctl(16) - last_tick;
+	prev_tick = next_tick - clocktick;
 
-	/* the precision of this math could be improved */
-	return elapsed_cycles / (PAGE0->mem_10msec / 10000);
+	/* Assume Scenario 1: "now" is later than prev_tick.  */
+	elapsed_cycles = now - prev_tick;
+
+	if (now < prev_tick) {
+		/* Scenario 2: CR16 wrapped!
+		 * 1's complement is close enough.
+		 */
+		elapsed_cycles = ~elapsed_cycles;
+	}
+
+	if (elapsed_cycles > (HZ * clocktick)) {
+		/* Scenario 3: clock ticks are missing. */
+		printk (KERN_CRIT "gettimeoffset(CPU %d): missing ticks!"
+			"cycles %lX prev/now/next %lX/%lX/%lX  clock %lX\n",
+			 elapsed_cycles, prev_tick, now, next_tick, clocktick);
+	}
+
+	/* FIXME: Can we improve the precision? Not with PAGE0. */
+	usec = (elapsed_cycles * 10000) / PAGE0->mem_10msec;
+
+	/* add in "lost" jiffies */
+	usec += clocktick * (jiffies - wall_jiffies);
+	return usec;
 #else
 	return 0;
 #endif
@@ -149,6 +211,7 @@ do_gettimeofday (struct timeval *tv)
 {
 	unsigned long flags, seq, usec, sec;
 
+	/* Hold xtime_lock and adjust timeval.  */
 	do {
 		seq = read_seqbegin_irqsave(&xtime_lock, flags);
 		usec = gettimeoffset();
@@ -156,25 +219,13 @@ do_gettimeofday (struct timeval *tv)
 		usec += (xtime.tv_nsec / 1000);
 	} while (read_seqretry_irqrestore(&xtime_lock, seq, flags));
 
-	if (unlikely(usec > LONG_MAX)) {
-		/* This can happen if the gettimeoffset adjustment is
-		 * negative and xtime.tv_nsec is smaller than the
-		 * adjustment */
-		printk(KERN_ERR "do_gettimeofday() spurious xtime.tv_nsec of %ld\n", usec);
-		usec += USEC_PER_SEC;
-		--sec;
-		/* This should never happen, it means the negative
-		 * time adjustment was more than a second, so there's
-		 * something seriously wrong */
-		BUG_ON(usec > LONG_MAX);
-	}
-
-
+	/* Move adjusted usec's into sec's.  */
 	while (usec >= USEC_PER_SEC) {
 		usec -= USEC_PER_SEC;
 		++sec;
 	}
 
+	/* Return adjusted result.  */
 	tv->tv_sec = sec;
 	tv->tv_usec = usec;
 }
@@ -226,22 +277,24 @@ unsigned long long sched_clock(void)
 }
 
 
+void __init start_cpu_itimer(void)
+{
+	unsigned int cpu = smp_processor_id();
+	unsigned long next_tick = mfctl(16) + clocktick;
+
+	mtctl(next_tick, 16);		/* kick off Interval Timer (CR16) */
+
+	cpu_data[cpu].it_value = next_tick;
+}
+
 void __init time_init(void)
 {
-	unsigned long next_tick;
 	static struct pdc_tod tod_data;
 
 	clocktick = (100 * PAGE0->mem_10msec) / HZ;
 	halftick = clocktick / 2;
 
-	/* Setup clock interrupt timing */
-
-	next_tick = mfctl(16);
-	next_tick += clocktick;
-	cpu_data[smp_processor_id()].it_value = next_tick;
-
-	/* kick off Itimer (CR16) */
-	mtctl(next_tick, 16);
+	start_cpu_itimer();	/* get CPU 0 started */
 
 	if(pdc_tod_read(&tod_data) == 0) {
 		write_seqlock_irq(&xtime_lock);
diff --git a/include/asm-parisc/param.h b/include/asm-parisc/param.h
index 07cb9b9..32e03d8 100644
--- a/include/asm-parisc/param.h
+++ b/include/asm-parisc/param.h
@@ -2,13 +2,9 @@ #ifndef _ASMPARISC_PARAM_H
 #define _ASMPARISC_PARAM_H
 
 #ifdef __KERNEL__
-# ifdef CONFIG_PA20
-#  define HZ		1000		/* Faster machines */
-# else
-#  define HZ		100		/* Internal kernel timer frequency */
-# endif
-# define USER_HZ	100		/* .. some user interfaces are in "ticks" */
-# define CLOCKS_PER_SEC	(USER_HZ)	/* like times() */
+#define HZ		CONFIG_HZ
+#define USER_HZ		100		/* some user API use "ticks" */
+#define CLOCKS_PER_SEC	(USER_HZ)	/* like times() */
 #endif
 
 #ifndef HZ
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Thu, Aug 31, 2006 at 02:52:44PM -0400, Carlos O'Donell wrote:
...
> >> 2. No attempt is made to handle cr16 wrapping.
> >
> >The signed math was supposed to handle it.
> >I believe it did but forgot details since looking at
> >it a few years ago.
> 
> That is *even* worse, signed arithmetic overflow is compiler
> implementation dependant. It's also therefore not very nice C code.
> The overflow case is in the middle of the 32-bit range now, where you
> had a very large positive number which wraps to a very large negative
> number. The gap is almost the entire 32-bit range, or 27 seconds on a
> 160Mhz box as we have shown already.

I think it's arbitrary where the overflow occurs.
Maybe unsigned math overflow is easier to visualize/understand.
At least it is for me.

> >I personally prefer to NOT use signed math in this case.
> >But that's honestly not a great reason to change this code.
> >I'd really prefer some evidence the kernel code is wrong.
> 
> I agree, this patch was an attempt to provide an alternate
> implementation that made sense and was maintainer friendly. I believe
> we should be able to get this working better and handle the failures
> seen on the slower boxes.

Yes. I'm now pretty sure the fix for that will be in gettimeoffset()
and not in timer_interrupt(). But I agree the two functions are very
similar but have to handle slightly different corner cases.

> >13.065388 sec
> >30 Aug 23:52:04 ntpdate[14055]: step time server 195.234.188.26 offset 
> >11.578574 sec
> >30 Aug 23:52:31 ntpdate[14058]: step time server 203.217.30.156 offset 
> >13.954358 sec
> >...
> 
> Technically it is implementation dependant, and can be as low as 1/2
> the peak instruction rate. In correcting timer_interrupt, I remember
> removing what I thought was a spurious 'clocktick' addition in the
> implementation.

I was thinking the opposite: I'm missing a "tick_elapsed" count
on each timer interrupt.

>  Does cr16 *actuall* count at the instruction rate, or
> does it count at 1/2 rate?

I _believe_ all implementations count at the actual rate.
At least I'm not aware of any implementations that don't
count at the advertized clock speed.

...
> I think the detection of Scenario 3 is wrong in your patch, I'll
> epxlain further down in the code.
...

> 
> >...
> >> I assert that 'gettimeoffset' should never return a negative value. It
> >> represents the postive adjustment accounting for the fact that we are
> >> *part* of the way through a tick.
> >
> >I have to think about this more. But I wonder if how "halftick" is
> >handled in timer_interrupt does not play well with this concept.
> 
> There is a bug here because of this, you are right to be warry of the
> halftick adjustment. It is also needed in gettimeoffset, or "now" will
> appear before "next_tick" without wrapping.

Sorry - this didn't make sense. Can you provide an example?
For simplicity assume a 5 bit counter and pick the values
that illustrate your case.


> >Please review and see if I added any new bugs.
> 
> There is 1 addtional bug.
...
> >+       /* Determine how much time elapsed.  */
> >+       if (now > next_tick) {
> >+               /* Scenario 1: "now" is late. A bit late is normal. */
> >+               ticks_elapsed = (now - next_tick) / clocktick;
> >+               remainder = now - (ticks_elapsed * clocktick);
> 
> What have you got against modulo?

Modulo is a division.
Division is much more expensive than integer multiplication.
Is there a way to do the division once _and_ get the remainder?

My assumption that integer multiplication is "cheaper"
could be wrong.

>  The correct math is as follows.
> 
> remainder = now - next_tick - ticks_elapsed * clocktick;

Erm, no.  ticks_elapsed was calculated here:
	ticks_elapsed = (now - next_tick) / clocktick;

(the line above.)
I'm taking advantage of truncation since this is integer division.
That make more sense?

> >+               /* "now" is either early or cr16 wrapped.  */
> >+               if (~next_tick < clocktick) {
> 
> Too clever for me :)

Now I'm worried. :)
I've already removed this code in the version I'm working on now.

...
> >+       } else {
> >+               /* "now" is either early or cr16 wrapped.  */
> >+               if (next_next_tick < last_tick) {
> 
> This could also use your clever "~next_tick < clocktick" trick.
> Remember this is only a heuristic to catch wrapping.

Yup - I'll post a new version that boots 64-bit correctly in a bit.
I've still not got the "wrapping" rules correct.

...
> Somwhere in thie function we need to makeup for the halftick...

Hrm. I need to think more about that. You might be right.

> Joel has already seen a BUG, which IMO is caused by gettimeoffset not
> taking into account the halftick.

ok. I was just looking at that.

thanks,
grant
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Carlos O'Donell]

On 8/31/06, Grant Grundler <grundler@parisc-linux.org> wrote:
> > 1. cr16 is treated as signed.
>
> This was by design. Paul Bame (IIRC) wrote this code and
> while I was never that comfortable with it, I could never
> find anything wrong with it either. Randolph Chung and I
> stared at timer_interrupt() _alot_.

It's twice as smart as I am, therefore I am four times too dumb to
maintain this code. My aim was ti simplify this code, because when the
new timer infrastructure goes into place it will be crucial that we
handle the wrapping right.

> > 2. No attempt is made to handle cr16 wrapping.
>
> The signed math was supposed to handle it.
> I believe it did but forgot details since looking at
> it a few years ago.

That is *even* worse, signed arithmetic overflow is compiler
implementation dependant. It's also therefore not very nice C code.
The overflow case is in the middle of the 32-bit range now, where you
had a very large positive number which wraps to a very large negative
number. The gap is almost the entire 32-bit range, or 27 seconds on a
160Mhz box as we have shown already.

> I personally prefer to NOT use signed math in this case.
> But that's honestly not a great reason to change this code.
> I'd really prefer some evidence the kernel code is wrong.

I agree, this patch was an attempt to provide an alternate
implementation that made sense and was maintainer friendly. I believe
we should be able to get this working better and handle the failures
seen on the slower boxes.

> And I've hacked your version some more.
> diff is below.

Thanks.

> I've included your changes to gettimeoffset() in my patch below
> and will review those next.

Ok.

> And something is certainly wrong with my version of the code.
> It seems to be running the system clock at ~ 1/2 speed now. :)
>
> odine:~# while : ; do sleep 10 ; ntpdate pool.ntp.org ; done
> 30 Aug 23:51:13 ntpdate[14051]: step time server 203.217.30.156 offset 60.165510 sec
> 30 Aug 23:51:39 ntpdate[14053]: step time server 203.217.30.156 offset 13.065388 sec
> 30 Aug 23:52:04 ntpdate[14055]: step time server 195.234.188.26 offset 11.578574 sec
> 30 Aug 23:52:31 ntpdate[14058]: step time server 203.217.30.156 offset 13.954358 sec
> ...

Technically it is implementation dependant, and can be as low as 1/2
the peak instruction rate. In correcting timer_interrupt, I remember
removing what I thought was a spurious 'clocktick' addition in the
implementation. Does cr16 *actuall* count at the instruction rate, or
does it count at 1/2 rate?

> > A. cr16 is treated as an unsigned long.
> > B. The following 3 scenarios exist.
> >
> > 1. The timer interrupt fires, and 'now' comes after 'next_tick'
>
> This is the "normal" case I think. 'now' should always lag behind
> 'next_tick' and how much depends on how long interrupts are blocked
> on that CPU.

Sounds good.

> > 2. The timer interrupt fires, and 'now' has wrapped and is before
> > 'next_tick'
> > 3. The timer interrupt fires, and 'now' is *just* before 'next_tick'
> >
> > In theory 99% of the time we should be in scenario 1. On occasion we
> > may miss a timer interrupt, end up close to wrapping, and we get
> > scenario 2.
>
> I'll assert we don't need to miss a timer interrupt to hit Scenario 2.
> All we need is a timer interrupt that scheduled near 4GB (but below)
> and 'normal' lag in interrupt delivery/handling will allow the
> CR16 to wrap.

A timer interrupt that is scheduled near the 4GB boundary is what I
meant by "end up close to wrapping." You are right that interrupt
delivery/handling lag might mean cr16 would wrap without causing a
missed interrupt.

> > Scenario 3 is just plain wrong and for now I will BUG() if
> > the timer fires before we intended.
>
> I agree.

I think the detection of Scenario 3 is wrong in your patch, I'll
epxlain further down in the code.

> ...
> > I assert that 'gettimeoffset' should never return a negative value. It
> > represents the postive adjustment accounting for the fact that we are
> > *part* of the way through a tick.
>
> I have to think about this more. But I wonder if how "halftick" is
> handled in timer_interrupt does not play well with this concept.

There is a bug here because of this, you are right to be warry of the
halftick adjustment. It is also needed in gettimeoffset, or "now" will
appear before "next_tick" without wrapping.

> Please review and see if I added any new bugs.

There is 1 addtional bug.

> Note that I replaced the "~0UL - XXX" with "~ XXX".
> I'll be off by one cycle. I don't care.
>
> thanks,
> grant
>
>
> diff --git a/arch/parisc/kernel/time.c b/arch/parisc/kernel/time.c
> index 5facc9b..9f6cf58 100644
> --- a/arch/parisc/kernel/time.c
> +++ b/arch/parisc/kernel/time.c
> @@ -44,34 +44,58 @@ #endif
>
>  irqreturn_t timer_interrupt(int irq, void *dev_id, struct pt_regs *regs)
>  {
> -       long now;
> -       long next_tick;
> -       int nticks;
> +       unsigned long now;
> +       unsigned long next_tick;
> +        unsigned long remainder;
> +       unsigned long ticks_elapsed = 0;
>         int cpu = smp_processor_id();
>
>         profile_tick(CPU_PROFILING, regs);
>
> -       now = mfctl(16);
> -       /* initialize next_tick to time at last clocktick */
> +       /* Initialize next_tick to the expected tick time. */
>         next_tick = cpu_data[cpu].it_value;
>
> -       /* since time passes between the interrupt and the mfctl()
> -        * above, it is never true that last_tick + clocktick == now.  If we
> -        * never miss a clocktick, we could set next_tick = last_tick + clocktick
> -        * but maybe we'll miss ticks, hence the loop.
> -        *
> -        * Variables are *signed*.
> +       /* Get current interval timer.
> +        * CR16 reads as 64 or 32 bit value depending CPU wide/narrow mode.
>          */
> +       now = mfctl(16);
> +
> +       /* Determine how much time elapsed.  */
> +       if (now > next_tick) {
> +               /* Scenario 1: "now" is late. A bit late is normal. */
> +               ticks_elapsed = (now - next_tick) / clocktick;
> +               remainder = now - (ticks_elapsed * clocktick);

What have you got against modulo? The correct math is as follows.

remainder = now - next_tick - ticks_elapsed * clocktick;

> +       }
> +        else {
> +               /* "now" is either early or cr16 wrapped.  */
> +               if (~next_tick < clocktick) {

Too clever for me :)

> +                       unsigned long difference;
> +
> +                       /* Scenario 2: A missed clock tick would wrap. */
> +                       difference = ~0UL - (next_tick - now);
> +                       ticks_elapsed = difference / clocktick;
> +                       remainder = difference % clocktick;
> +               } else {
> +                       /* Scenario 3: We didn't miss a clock tick.
> +                          "now" is early?  */
> +                       printk ("timer_interrupt: Now is early, now = %lx, next_tick = %lx, clocktick = %lx\n", now, next_tick, clocktick);
> +                       BUG ();
> +               }
> +       }
>
> -       nticks = 0;
> -       while((next_tick - now) < halftick) {
> -               next_tick += clocktick;
> -               nticks++;
> +       if (remainder > halftick) {
> +               /* More than 1/2 way into the next tick. It counts.  */
> +               ticks_elapsed++;
>         }
> +
> +       /* Add any full ticks that have elapsed plus the one we want next. */
> +       next_tick += (ticks_elapsed + 1) * clocktick;
> +
> +        /* Only bottom 32-bits of next_tick are written to cr16.  */
>         mtctl(next_tick, 16);
>         cpu_data[cpu].it_value = next_tick;
>
> -       while (nticks--) {
> +       while (ticks_elapsed--) {
>  #ifdef CONFIG_SMP
>                 smp_do_timer(regs);
>  #else
> @@ -124,21 +148,47 @@ #ifndef CONFIG_SMP
>          *    Once parisc-linux learns the cr16 difference between processors,
>          *    this could be made to work.
>          */
> -       long last_tick;
> -       long elapsed_cycles;
> +       unsigned long now;
> +       unsigned long last_tick;
> +       unsigned long next_tick;
> +       unsigned long next_next_tick;
> +       unsigned long elapsed_cycles;
> +       unsigned long usec;
> +       unsigned long lost;
>
>         /* it_value is the intended time of the next tick */
> -       last_tick = cpu_data[smp_processor_id()].it_value;
> +       next_tick = cpu_data[smp_processor_id()].it_value;
> +       next_next_tick = next_tick + clocktick;
>
> -       /* Subtract one tick and account for possible difference between
> -        * when we expected the tick and when it actually arrived.
> -        * (aka wall vs real)
> -        */
> -       last_tick -= clocktick * (jiffies - wall_jiffies + 1);
> -       elapsed_cycles = mfctl(16) - last_tick;
> +       /* This represents lost jiffies.  */
> +       lost = clocktick * (jiffies - wall_jiffies);
> +
> +       /* We roll back 1 tick.  */
> +       last_tick = next_tick - clocktick;
> +
> +       /* Read the hardware interval timer.  */
> +       now = mfctl(16);
> +
> +       if (now > last_tick) {
> +               /* Scenario 1: "now" is later than last_tick.  */
> +               elapsed_cycles = now - last_tick;
> +       } else {
> +               /* "now" is either early or cr16 wrapped.  */
> +               if (next_next_tick < last_tick) {

This could also use your clever "~next_tick < clocktick" trick.
Remember this is only a heuristic to catch wrapping.

> +                       /* Scenario 2: A missed clock tick would wrap. */
> +                       elapsed_cycles = ~0UL - (last_tick - now);
> +               } else {
> +                       /* Scenario 3: We didn't miss a clock tick.
> +                          "now" is early?  */
> +                       printk ("gettimeoffset: Now is early, now = %lx, last_tick = %lx, next_tick = %lx, clocktick = %lx\n", now, last_tick, next_tick, clocktick);
> +                       BUG ();
> +               }
> +       }

Somwhere in thie function we need to makeup for the halftick...

> -       /* the precision of this math could be improved */
> -       return elapsed_cycles / (PAGE0->mem_10msec / 10000);
> +       /* FIXME: Improve precision. */
> +       usec = elapsed_cycles * 10000 / PAGE0->mem_10msec;
> +       usec += lost;
> +       return usec;
>  #else
>         return 0;
>  #endif

Joel has already seen a BUG, which IMO is caused by gettimeoffset not
taking into account the halftick.

Cheers,
Carlos.
_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux

Re: [parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Grant Grundler]

On Wed, Aug 30, 2006 at 12:48:43AM -0400, Carlos O'Donell wrote:
> A review of 'arch/parisc/kernel/time.c' and in particular
> 'timer_interrupt' and 'gettimeoffset'  show that this code has a
> couple of design flaws.
> 
> 1. cr16 is treated as signed.

This was by design. Paul Bame (IIRC) wrote this code and
while I was never that comfortable with it, I could never 
find anything wrong with it either. Randolph Chung and I
stared at timer_interrupt() _alot_.

> 2. No attempt is made to handle cr16 wrapping.

The signed math was supposed to handle it.
I believe it did but forgot details since looking at
it a few years ago.

I personally prefer to NOT use signed math in this case.
But that's honestly not a great reason to change this code.
I'd really prefer some evidence the kernel code is wrong.

> 3. jiffies vs. wall_jiffies adjustment is incorrect.
> 
> I have rewritten 'timer_interrupt'.

And I've hacked your version some more.
diff is below.

I've included your changes to gettimeoffset() in my patch below
and will review those next.

And something is certainly wrong with my version of the code.
It seems to be running the system clock at ~ 1/2 speed now. :)

odine:~# while : ; do sleep 10 ; ntpdate pool.ntp.org ; done
30 Aug 23:51:13 ntpdate[14051]: step time server 203.217.30.156 offset 60.165510 sec
30 Aug 23:51:39 ntpdate[14053]: step time server 203.217.30.156 offset 13.065388 sec
30 Aug 23:52:04 ntpdate[14055]: step time server 195.234.188.26 offset 11.578574 sec
30 Aug 23:52:31 ntpdate[14058]: step time server 203.217.30.156 offset 13.954358 sec
...

> A. cr16 is treated as an unsigned long.
> B. The following 3 scenarios exist.
> 
> 1. The timer interrupt fires, and 'now' comes after 'next_tick'

This is the "normal" case I think. 'now' should always lag behind
'next_tick' and how much depends on how long interrupts are blocked
on that CPU.

> 2. The timer interrupt fires, and 'now' has wrapped and is before 
> 'next_tick'
> 3. The timer interrupt fires, and 'now' is *just* before 'next_tick'
> 
> In theory 99% of the time we should be in scenario 1. On occasion we
> may miss a timer interrupt, end up close to wrapping, and we get
> scenario 2.

I'll assert we don't need to miss a timer interrupt to hit Scenario 2.
All we need is a timer interrupt that scheduled near 4GB (but below)
and 'normal' lag in interrupt delivery/handling will allow the
CR16 to wrap.

> Scenario 3 is just plain wrong and for now I will BUG() if
> the timer fires before we intended.

I agree.

...
> I assert that 'gettimeoffset' should never return a negative value. It
> represents the postive adjustment accounting for the fact that we are
> *part* of the way through a tick.

I have to think about this more. But I wonder if how "halftick" is
handled in timer_interrupt does not play well with this concept.

> The patch is attached. Please review. I booted this on my a500 without
> any problems. I don't really know how to look for problems so I ran
> the glibc testsuite and didn't get any extra regressions.

I've only booted on a500 (64-bit kernel) and will try on b2600
(32-bit kernel) next.


Please review and see if I added any new bugs.

Note that I replaced the "~0UL - XXX" with "~ XXX".
I'll be off by one cycle. I don't care.

thanks,
grant


diff --git a/arch/parisc/kernel/time.c b/arch/parisc/kernel/time.c
index 5facc9b..9f6cf58 100644
--- a/arch/parisc/kernel/time.c
+++ b/arch/parisc/kernel/time.c
@@ -44,34 +44,58 @@ #endif
 
 irqreturn_t timer_interrupt(int irq, void *dev_id, struct pt_regs *regs)
 {
-	long now;
-	long next_tick;
-	int nticks;
+	unsigned long now;
+	unsigned long next_tick;
+        unsigned long remainder;
+	unsigned long ticks_elapsed = 0;
 	int cpu = smp_processor_id();
 
 	profile_tick(CPU_PROFILING, regs);
 
-	now = mfctl(16);
-	/* initialize next_tick to time at last clocktick */
+	/* Initialize next_tick to the expected tick time. */
 	next_tick = cpu_data[cpu].it_value;
 
-	/* since time passes between the interrupt and the mfctl()
-	 * above, it is never true that last_tick + clocktick == now.  If we
-	 * never miss a clocktick, we could set next_tick = last_tick + clocktick
-	 * but maybe we'll miss ticks, hence the loop.
-	 *
-	 * Variables are *signed*.
+	/* Get current interval timer.
+	 * CR16 reads as 64 or 32 bit value depending CPU wide/narrow mode.
 	 */
+	now = mfctl(16);
+
+	/* Determine how much time elapsed.  */
+	if (now > next_tick) {
+		/* Scenario 1: "now" is late. A bit late is normal. */
+		ticks_elapsed = (now - next_tick) / clocktick;
+		remainder = now - (ticks_elapsed * clocktick);
+	}
+        else {
+		/* "now" is either early or cr16 wrapped.  */
+		if (~next_tick < clocktick) {
+			unsigned long difference;
+
+			/* Scenario 2: A missed clock tick would wrap. */
+			difference = ~0UL - (next_tick - now);
+			ticks_elapsed = difference / clocktick;
+			remainder = difference % clocktick;
+		} else {
+			/* Scenario 3: We didn't miss a clock tick. 
+			   "now" is early?  */
+			printk ("timer_interrupt: Now is early, now = %lx, next_tick = %lx, clocktick = %lx\n", now, next_tick, clocktick);
+			BUG ();
+		}
+	}
 
-	nticks = 0;
-	while((next_tick - now) < halftick) {
-		next_tick += clocktick;
-		nticks++;
+	if (remainder > halftick) {
+		/* More than 1/2 way into the next tick. It counts.  */
+		ticks_elapsed++;
 	}
+
+	/* Add any full ticks that have elapsed plus the one we want next. */
+	next_tick += (ticks_elapsed + 1) * clocktick;
+
+        /* Only bottom 32-bits of next_tick are written to cr16.  */
 	mtctl(next_tick, 16);
 	cpu_data[cpu].it_value = next_tick;
 
-	while (nticks--) {
+	while (ticks_elapsed--) {
 #ifdef CONFIG_SMP
 		smp_do_timer(regs);
 #else
@@ -124,21 +148,47 @@ #ifndef CONFIG_SMP
 	 *    Once parisc-linux learns the cr16 difference between processors,
 	 *    this could be made to work.
 	 */
-	long last_tick;
-	long elapsed_cycles;
+	unsigned long now;
+	unsigned long last_tick;
+	unsigned long next_tick;
+	unsigned long next_next_tick;
+	unsigned long elapsed_cycles;
+	unsigned long usec;
+	unsigned long lost;
 
 	/* it_value is the intended time of the next tick */
-	last_tick = cpu_data[smp_processor_id()].it_value;
+	next_tick = cpu_data[smp_processor_id()].it_value;
+	next_next_tick = next_tick + clocktick;
 
-	/* Subtract one tick and account for possible difference between
-	 * when we expected the tick and when it actually arrived.
-	 * (aka wall vs real)
-	 */
-	last_tick -= clocktick * (jiffies - wall_jiffies + 1);
-	elapsed_cycles = mfctl(16) - last_tick;
+	/* This represents lost jiffies.  */
+	lost = clocktick * (jiffies - wall_jiffies); 
+	
+	/* We roll back 1 tick.  */
+	last_tick = next_tick - clocktick;
+
+	/* Read the hardware interval timer.  */
+	now = mfctl(16);
+
+	if (now > last_tick) {
+		/* Scenario 1: "now" is later than last_tick.  */
+		elapsed_cycles = now - last_tick;
+	} else {
+		/* "now" is either early or cr16 wrapped.  */
+		if (next_next_tick < last_tick) {
+			/* Scenario 2: A missed clock tick would wrap. */
+			elapsed_cycles = ~0UL - (last_tick - now);
+		} else {
+			/* Scenario 3: We didn't miss a clock tick. 
+			   "now" is early?  */
+			printk ("gettimeoffset: Now is early, now = %lx, last_tick = %lx, next_tick = %lx, clocktick = %lx\n", now, last_tick, next_tick, clocktick);
+			BUG ();
+		}
+	}
 
-	/* the precision of this math could be improved */
-	return elapsed_cycles / (PAGE0->mem_10msec / 10000);
+	/* FIXME: Improve precision. */
+	usec = elapsed_cycles * 10000 / PAGE0->mem_10msec;
+	usec += lost;
+	return usec;
 #else
 	return 0;
 #endif
@@ -149,6 +199,7 @@ do_gettimeofday (struct timeval *tv)
 {
 	unsigned long flags, seq, usec, sec;
 
+	/* Hold xtime_lock and adjust timeval.  */
 	do {
 		seq = read_seqbegin_irqsave(&xtime_lock, flags);
 		usec = gettimeoffset();
@@ -156,25 +207,13 @@ do_gettimeofday (struct timeval *tv)
 		usec += (xtime.tv_nsec / 1000);
 	} while (read_seqretry_irqrestore(&xtime_lock, seq, flags));
 
-	if (unlikely(usec > LONG_MAX)) {
-		/* This can happen if the gettimeoffset adjustment is
-		 * negative and xtime.tv_nsec is smaller than the
-		 * adjustment */
-		printk(KERN_ERR "do_gettimeofday() spurious xtime.tv_nsec of %ld\n", usec);
-		usec += USEC_PER_SEC;
-		--sec;
-		/* This should never happen, it means the negative
-		 * time adjustment was more than a second, so there's
-		 * something seriously wrong */
-		BUG_ON(usec > LONG_MAX);
-	}
-

[parisc-linux] [PATCH] timer_interrupt and gettimeoffset.

[Carlos O'Donell]

[-- Attachment #1: Type: text/plain, Size: 1673 bytes --]

A review of 'arch/parisc/kernel/time.c' and in particular
'timer_interrupt' and 'gettimeoffset'  show that this code has a
couple of design flaws.

1. cr16 is treated as signed.
2. No attempt is made to handle cr16 wrapping.
3. jiffies vs. wall_jiffies adjustment is incorrect.

I have rewritten 'timer_interrupt'.

A. cr16 is treated as an unsigned long.
B. The following 3 scenarios exist.

1. The timer interrupt fires, and 'now' comes after 'next_tick'
2. The timer interrupt fires, and 'now' has wrapped and is before 'next_tick'
3. The timer interrupt fires, and 'now' is *just* before 'next_tick'

In theory 99% of the time we should be in scenario 1. On occasion we
may miss a timer interrupt, end up close to wrapping, and we get
scenario 2. Scenario 3 is just plain wrong and for now I will BUG() if
the timer fires before we intended.

I have adjusted 'gettimeoffset' in the following fashion:

A. cr16 is treated as an unsigned long.
B. Never ever ever return a negative adjustment.
C. (jiffies - wall_jiffies) adjustment is always positive and added to usec.
D. The 3 timer scenarios (same as above), exist.

I assert that 'gettimeoffset' should never return a negative value. It
represents the postive adjustment accounting for the fact that we are
*part* of the way through a tick.

The patch is attached. Please review. I booted this on my a500 without
any problems. I don't really know how to look for problems so I ran
the glibc testsuite and didn't get any extra regressions.

The real test will be to run this on a 715/50 and look for Guy's
reported problems. Guy, would you mind patching your kernel with this
patch and testing again?

Cheers,
Carlos.

[-- Attachment #2: patch-2006-08-29-time.diff --]
[-- Type: text/x-patch, Size: 5421 bytes --]

diff --git a/arch/parisc/kernel/time.c b/arch/parisc/kernel/time.c
index 5facc9b..ce7dc5e 100644
--- a/arch/parisc/kernel/time.c
+++ b/arch/parisc/kernel/time.c
@@ -44,32 +44,57 @@ #endif
 
 irqreturn_t timer_interrupt(int irq, void *dev_id, struct pt_regs *regs)
 {
-	long now;
-	long next_tick;
-	int nticks;
+	unsigned long now;
+	unsigned long next_tick;
+	unsigned long next_next_tick;
+	unsigned long difference;
+        unsigned long remainder;
+	int nticks = 0;
 	int cpu = smp_processor_id();
 
 	profile_tick(CPU_PROFILING, regs);
 
-	now = mfctl(16);
-	/* initialize next_tick to time at last clocktick */
+	/* Initialize next_tick to the expected tick time. */
 	next_tick = cpu_data[cpu].it_value;
+	next_next_tick = next_tick + clocktick;
 
-	/* since time passes between the interrupt and the mfctl()
-	 * above, it is never true that last_tick + clocktick == now.  If we
-	 * never miss a clocktick, we could set next_tick = last_tick + clocktick
-	 * but maybe we'll miss ticks, hence the loop.
-	 *
-	 * Variables are *signed*.
-	 */
+	/* Get current interval timer reading, reads as 64/32 bit
+           value depending if you have a 64/32 bit machine.  */
+	now = mfctl(16);
 
-	nticks = 0;
-	while((next_tick - now) < halftick) {
-		next_tick += clocktick;
+	/* Determine how much time elapsed.  */
+	if (now > next_tick) {
+		/* Scenario 1: "now" is late.  */
+		nticks = (now - next_tick) / clocktick;
+		remainder = (now - next_tick) % clocktick;
+	}
+        else {
+		/* "now" is either early or cr16 wrapped.  */
+		if (next_next_tick < next_tick) {
+			/* Scenario 2: A missed clock tick would wrap. */
+			difference = ~0UL - (next_tick - now);
+			nticks = difference / clocktick;
+			remainder = difference % clocktick;
+		} else {
+			/* Scenario 3: We didn't miss a clock tick. 
+			   "now" is early?  */
+			printk ("timer_interrupt: Now is early, now = %lx, next_tick = %lx, clocktick = %lx\n", now, next_tick, clocktick);
+			BUG ();
+		}
+	}
+
+	/* Check the remainder to see how far we are into the next tick?  */
+	if (remainder > halftick) {
+		/* More than 1/2 way in? Count a tick.  */
 		nticks++;
 	}
-	mtctl(next_tick, 16);
-	cpu_data[cpu].it_value = next_tick;
+
+	/* Add any full ticks that have elapsed.  */
+	next_next_tick += nticks * clocktick;
+
+        /* Only bottom 32-bits of next_tick are written to cr16.  */
+	mtctl(next_next_tick, 16);
+	cpu_data[cpu].it_value = next_next_tick;
 
 	while (nticks--) {
 #ifdef CONFIG_SMP
@@ -124,21 +149,47 @@ #ifndef CONFIG_SMP
 	 *    Once parisc-linux learns the cr16 difference between processors,
 	 *    this could be made to work.
 	 */
-	long last_tick;
-	long elapsed_cycles;
+	unsigned long now;
+	unsigned long last_tick;
+	unsigned long next_tick;
+	unsigned long next_next_tick;
+	unsigned long elapsed_cycles;
+	unsigned long usec;
+	unsigned long lost;
 
 	/* it_value is the intended time of the next tick */
-	last_tick = cpu_data[smp_processor_id()].it_value;
+	next_tick = cpu_data[smp_processor_id()].it_value;
+	next_next_tick = next_tick + clocktick;
 
-	/* Subtract one tick and account for possible difference between
-	 * when we expected the tick and when it actually arrived.
-	 * (aka wall vs real)
-	 */
-	last_tick -= clocktick * (jiffies - wall_jiffies + 1);
-	elapsed_cycles = mfctl(16) - last_tick;
+	/* This represents lost jiffies.  */
+	lost = clocktick * (jiffies - wall_jiffies); 
+	
+	/* We roll back 1 tick.  */
+	last_tick = next_tick - clocktick;
+
+	/* Read the hardware interval timer.  */
+	now = mfctl(16);
 
-	/* the precision of this math could be improved */
-	return elapsed_cycles / (PAGE0->mem_10msec / 10000);
+	if (now > last_tick) {
+		/* Scenario 1: "now" is later than last_tick.  */
+		elapsed_cycles = now - last_tick;
+	} else {
+		/* "now" is either early or cr16 wrapped.  */
+		if (next_next_tick < last_tick) {
+			/* Scenario 2: A missed clock tick would wrap. */
+			elapsed_cycles = ~0UL - (last_tick - now);
+		} else {
+			/* Scenario 3: We didn't miss a clock tick. 
+			   "now" is early?  */
+			printk ("gettimeoffset: Now is early, now = %lx, last_tick = %lx, next_tick = %lx, clocktick = %lx\n", now, last_tick, next_tick, clocktick);
+			BUG ();
+		}
+	}
+
+	/* FIXME: Improve precision. */
+	usec = elapsed_cycles * 10000 / PAGE0->mem_10msec;
+	usec += lost;
+	return usec;
 #else
 	return 0;
 #endif
@@ -149,6 +200,7 @@ do_gettimeofday (struct timeval *tv)
 {
 	unsigned long flags, seq, usec, sec;
 
+	/* Hold xtime_lock and adjust timeval.  */
 	do {
 		seq = read_seqbegin_irqsave(&xtime_lock, flags);
 		usec = gettimeoffset();
@@ -156,25 +208,13 @@ do_gettimeofday (struct timeval *tv)
 		usec += (xtime.tv_nsec / 1000);
 	} while (read_seqretry_irqrestore(&xtime_lock, seq, flags));
 
-	if (unlikely(usec > LONG_MAX)) {
-		/* This can happen if the gettimeoffset adjustment is
-		 * negative and xtime.tv_nsec is smaller than the
-		 * adjustment */
-		printk(KERN_ERR "do_gettimeofday() spurious xtime.tv_nsec of %ld\n", usec);
-		usec += USEC_PER_SEC;
-		--sec;
-		/* This should never happen, it means the negative
-		 * time adjustment was more than a second, so there's
-		 * something seriously wrong */
-		BUG_ON(usec > LONG_MAX);
-	}
-
-
+	/* Move adjusted usec's into sec's.  */
 	while (usec >= USEC_PER_SEC) {
 		usec -= USEC_PER_SEC;
 		++sec;
 	}
 
+	/* Return adjusted result.  */
 	tv->tv_sec = sec;
 	tv->tv_usec = usec;
 }

[-- Attachment #3: Type: text/plain, Size: 169 bytes --]

_______________________________________________
parisc-linux mailing list
parisc-linux@lists.parisc-linux.org
http://lists.parisc-linux.org/mailman/listinfo/parisc-linux