kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)

kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)

[Andreas Mohr]

Hi all,

next_timer_interrupt() contains the following gem:

        /* Check tv2-tv5. */
        varray[0] = &base->tv2;
        varray[1] = &base->tv3;
        varray[2] = &base->tv4;
        varray[3] = &base->tv5;
        for (i = 0; i < 4; i++) {
                j = INDEX(i);
                do {
                        if (list_empty(varray[i]->vec + j)) {
                                j = (j + 1) & TVN_MASK;
                                continue;
                        }
                        list_for_each_entry(nte, varray[i]->vec + j, entry)
                                if (time_before(nte->expires, expires))
                                        expires = nte->expires;
                        if (j < (INDEX(i)) && i < 3)
                                list = varray[i + 1]->vec + (INDEX(i + 1));
                        goto found;
                } while (j != (INDEX(i)));
        }
found:
        if (list) {



Excuse me, but why do we have a while loop here if the last instruction in
the while loop is a straight "goto found"?
(a "continue" simply continue:s the loop without checking the loop condition
at the bottom, right?)


Few lines above there's similar code:

        /* Look for timer events in tv1. */
        j = base->timer_jiffies & TVR_MASK;
        do {
                list_for_each_entry(nte, base->tv1.vec + j, entry) {
                        expires = nte->expires;
                        if (j < (base->timer_jiffies & TVR_MASK))
                                list = base->tv2.vec + (INDEX(0));
                        goto found;
                }
                j = (j + 1) & TVR_MASK;
        } while (j != (base->timer_jiffies & TVR_MASK));


However in this case now we process *one* list only, so the "goto found"
should be ok since we don't need to iterate through the multiple tv2-tv5 lists
as in the other potentially buggy loop.

Also, is the base->tv1.vec vs. base->tv2.vec difference above ok?

Possibly I'm too dense while reading this code, though...

Andreas Mohr

Re: kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)

[Michael Buesch]

On Monday 17 July 2006 20:53, Andreas Mohr wrote:
> (a "continue" simply continue:s the loop without checking the loop condition
> at the bottom, right?)

I don't think so. Test it. This is no infinite loop:

int main(void)
{
        int i = 0;
        do {
                i++;
                continue;
        } while (i < 1000);
}

-- 
Greetings Michael.

Re: kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)

[Valdis.Kletnieks]

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

On Mon, 17 Jul 2006 20:53:30 +0200, Andreas Mohr said:
> Hi all,
> 

>         for (i = 0; i < 4; i++) {
>                 j = INDEX(i);
>                 do {

>                         if (j < (INDEX(i)) && i < 3)
>                                 list = varray[i + 1]->vec + (INDEX(i + 1));
>                         goto found;
>                 } while (j != (INDEX(i)));
>         }
> found:

> Excuse me, but why do we have a while loop here if the last instruction in
> the while loop is a straight "goto found"?

Consider if we take the 'goto found' when i==1.  We leave not only the do/while
but also the for loop.  A 'continue' instead would leave the do/while and then
drive the i==2 and subsequent 'for' iterations....

(Unless my C mastery has severely faded of late?)

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)

[Andreas Schwab]

Andreas Mohr <andi@rhlx01.fht-esslingen.de> writes:

> (a "continue" simply continue:s the loop without checking the loop condition
> at the bottom, right?)

No.  A continue jumps to the end of the loop body.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

[PATCH] fix bad macro param in timer.c (was: kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2))

[Steven Rostedt]

On Mon, 2006-07-17 at 20:53 +0200, Andreas Mohr wrote:
> Hi all,
> 
> next_timer_interrupt() contains the following gem:
> 
>         /* Check tv2-tv5. */
>         varray[0] = &base->tv2;
>         varray[1] = &base->tv3;
>         varray[2] = &base->tv4;
>         varray[3] = &base->tv5;
>         for (i = 0; i < 4; i++) {
>                 j = INDEX(i);
>                 do {
>                         if (list_empty(varray[i]->vec + j)) {
>                                 j = (j + 1) & TVN_MASK;
>                                 continue;
>                         }
>                         list_for_each_entry(nte, varray[i]->vec + j, entry)
>                                 if (time_before(nte->expires, expires))
>                                         expires = nte->expires;
>                         if (j < (INDEX(i)) && i < 3)

Looking at what INDEX is defined to be:

#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK

>                                 list = varray[i + 1]->vec + (INDEX(i + 1));

And this INDEX(i+1) is now a ... (TVR_BITS + i + 1 * TVN_BITS)) ...
This doesn't quite look like it suppose to be that way. Probably having
some funny results because of it.

Here's the patch to clean up the macro used to find the index of the
timer vector.

This is definitely a bug fix and should go into 2.6.18

-- Steve

Signed-off-by: Steven Rostedt <rostedt@goodmis.org>

Index: linux-2.6.18-rc2/kernel/timer.c
===================================================================
--- linux-2.6.18-rc2.orig/kernel/timer.c	2006-07-17 21:34:08.000000000 -0400
+++ linux-2.6.18-rc2/kernel/timer.c	2006-07-17 21:34:22.000000000 -0400
@@ -408,7 +408,7 @@ static int cascade(tvec_base_t *base, tv
  * This function cascades all vectors and executes all expired timer
  * vectors.
  */
-#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK
+#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK
 
 static inline void __run_timers(tvec_base_t *base)
 {

Re: kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)

[Steven Rostedt]

On Mon, 2006-07-17 at 15:57 -0400, Valdis.Kletnieks@vt.edu wrote:
> On Mon, 17 Jul 2006 20:53:30 +0200, Andreas Mohr said:
> > Hi all,
> > 
> 
> >         for (i = 0; i < 4; i++) {
> >                 j = INDEX(i);
> >                 do {
> 
> >                         if (j < (INDEX(i)) && i < 3)
> >                                 list = varray[i + 1]->vec + (INDEX(i + 1));
> >                         goto found;
> >                 } while (j != (INDEX(i)));
> >         }
> > found:
> 
> > Excuse me, but why do we have a while loop here if the last instruction in
> > the while loop is a straight "goto found"?
> 
> Consider if we take the 'goto found' when i==1.  We leave not only the do/while
> but also the for loop.  A 'continue' instead would leave the do/while and then
> drive the i==2 and subsequent 'for' iterations....
> 
> (Unless my C mastery has severely faded of late?)

No you are right.  We jump to found because we found what we are looking
for and don't need to look further in any more loops.

-- Steve

Re: [PATCH] fix bad macro param in timer.c

[Steven Rostedt]

Joe Perches suggested another set of parans.  And I believe he's right.

Signed-off-by: Steven Rostedt <rostedt@goodmis.org>

Index: linux-2.6.18-rc2/kernel/timer.c
===================================================================
--- linux-2.6.18-rc2.orig/kernel/timer.c	2006-07-17 21:42:01.000000000 -0400
+++ linux-2.6.18-rc2/kernel/timer.c	2006-07-17 21:56:49.000000000 -0400
@@ -408,7 +408,7 @@ static int cascade(tvec_base_t *base, tv
  * This function cascades all vectors and executes all expired timer
  * vectors.
  */
-#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK
+#define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)
 
 static inline void __run_timers(tvec_base_t *base)
 {

Re: kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)

[Michael Buesch]

On Monday 17 July 2006 21:57, Valdis.Kletnieks@vt.edu wrote:
> On Mon, 17 Jul 2006 20:53:30 +0200, Andreas Mohr said:
> > Hi all,
> > 
> 
> >         for (i = 0; i < 4; i++) {
> >                 j = INDEX(i);
> >                 do {
> 
> >                         if (j < (INDEX(i)) && i < 3)
> >                                 list = varray[i + 1]->vec + (INDEX(i + 1));
> >                         goto found;
> >                 } while (j != (INDEX(i)));
> >         }
> > found:
> 
> > Excuse me, but why do we have a while loop here if the last instruction in
> > the while loop is a straight "goto found"?
> 
> Consider if we take the 'goto found' when i==1.  We leave not only the do/while
> but also the for loop.  A 'continue' instead would leave the do/while and then
> drive the i==2 and subsequent 'for' iterations....

No, it would not. A 'continue' instead of the 'goto found' would
compile to nothing.
Try the following example with and without the 'continue'.

#include <stdio.h>
int main(void)
{
        int i, j;
        for (i = 0; i < 2; i++) {
                j = 0;
                do {
                        printf("i==%d, j==%d\n", i, j);
                        j++;
                        /* goto found; */
                        continue;
                } while (j < 2);
        }
}


Continue is equal to:

LOOP {
	/* foo */
	goto continue; /* == continue */
	/* foo */
continue:
} LOOP

-- 
Greetings Michael.

Re: kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)

[Valdis.Kletnieks]

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

On Tue, 18 Jul 2006 16:29:27 +0200, Michael Buesch said:

> Continue is equal to:
> 
> LOOP {
> 	/* foo */
> 	goto continue; /* == continue */
	/* What the code actually had: */
        goto found; /* Note placement of the label *AFTER* end of loop */
> 	/* foo */
> continue:
> } LOOP

found: /* out of the loop entirely */

A 'continue' drops you *at* the end of the loop. The 'goto found:' in the
original code drops you *after* the end of the loop.  One will potentially go
around for another pass, the other you're *done*.


[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)

[Michael Buesch]

On Tuesday 18 July 2006 16:50, Valdis.Kletnieks@vt.edu wrote:
> On Tue, 18 Jul 2006 16:29:27 +0200, Michael Buesch said:
> 
> > Continue is equal to:
> > 
> > LOOP {
> > 	/* foo */
> > 	goto continue; /* == continue */
> 	/* What the code actually had: */
>         goto found; /* Note placement of the label *AFTER* end of loop */
> > 	/* foo */
> > continue:
> > } LOOP
> 
> found: /* out of the loop entirely */
> 
> A 'continue' drops you *at* the end of the loop. The 'goto found:' in the
> original code drops you *after* the end of the loop.  One will potentially go
> around for another pass, the other you're *done*.

I did not say something else.
I just wanted to say the sentence
> A 'continue' instead would leave the do/while and then
> drive the i==2 and subsequent 'for' iterations....
is wrong. It would _not_ leave the do/while directly.
It will check condition first and _might_ leave it.

-- 
Greetings Michael.

Re: kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)

[Prakash Punnoor]

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

Am Montag Juli 17 2006 20:53 schrieb Andreas Mohr:
>         for (i = 0; i < 4; i++) {
>                 j = INDEX(i);
>                 do {
>                         if (list_empty(varray[i]->vec + j)) {
>                                 j = (j + 1) & TVN_MASK;
>                                 continue;
>                         }
>                         list_for_each_entry(nte, varray[i]->vec + j, entry)
>                                 if (time_before(nte->expires, expires))
>                                         expires = nte->expires;
>                         if (j < (INDEX(i)) && i < 3)
>                                 list = varray[i + 1]->vec + (INDEX(i + 1));
>                         goto found;
>                 } while (j != (INDEX(i)));
>         }
> found:

is equivalent to

  for (i = 0; i < 4; i++) {
      j = INDEX(i);
      do {
          if (!list_empty(varray[i]->vec + j)) {
              list_for_each_entry(nte, varray[i]->vec + j, entry)
                  if (time_before(nte->expires, expires))
                      expires = nte->expires;
              if (j < (INDEX(i)) && i < 3)
                  list = varray[i + 1]->vec + (INDEX(i + 1));
              goto found;
          }
          j = (j + 1) & TVN_MASK;
      } while (j != (INDEX(i)));
  }
  found:


But probably the code in timer.c takes account of probabilities, thus it is a 
bit more obscure.

HTH,
-- 
(°=                 =°)
//\ Prakash Punnoor /\\
V_/                 \_V

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

offtopic boot parameter notsc [Was: Re: kernel/timer.c: next_timer_interrupt() strange/buggy(?) code (2.6.18-rc1-mm2)]

[Sergio Monteiro Basto]

Hi,
I am suffer a problem with lost tickets , that I suspect that begins in
timer.c, I have to boot with notsc , but this is only one workaround,
that don't resolve all problems.
Where I can find some help about this topic ? 
more info about my bug http://bugme.osdl.org/show_bug.cgi?id=6419

Thanks in advance,
--
Sérgio M. B.