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

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

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.

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

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.

	/* What the code actually had: */
        goto found; /* Note placement of the label *AFTER* end of 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

is wrong. It would _not_ leave the do/while directly. It will check condition first and _might_ leave it.

Greetings Michael.

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

Andreas.

Andreas Schwab, SuSE Labs, [email protected]
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."

Looking at what INDEX is defined to be:

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

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

Index: linux-2.6.18-rc2/kernel/timer.c
===================================================================
@@ -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)
 {

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

Index: linux-2.6.18-rc2/kernel/timer.c
===================================================================
@@ -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)
 {

Am Montag Juli 17 2006 20:53 schrieb Andreas Mohr:

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

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.