Re: [PATCH] fix nanosleep() granularity bumps

Re: [PATCH] fix nanosleep() granularity bumps

[Tim Schmielau]

On Tue, 18 Mar 2003, Tim Schmielau wrote:

> Please don't yet forward to Linus. After twisting my little brain a bit
> further, I see that the patch is still wrong if the lowest TVR_BITS of
> INITIAL_JIFFIES happen to be zero while others are not.

OK, this one looks ugly but should be correct, even in the case of a
partial timer cascade on the first timer interrupt:


--- linux-2.5.65/kernel/timer.c.orig	Tue Mar 18 13:02:39 2003
+++ linux-2.5.65/kernel/timer.c	Tue Mar 18 13:41:53 2003
@@ -1182,11 +1182,23 @@
 		INIT_LIST_HEAD(base->tv1.vec + j);

 	base->timer_jiffies = INITIAL_JIFFIES;
-	base->tv1.index = INITIAL_JIFFIES & TVR_MASK;
-	base->tv2.index = (INITIAL_JIFFIES >> TVR_BITS) & TVN_MASK;
-	base->tv3.index = (INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS)) & TVN_MASK;
-	base->tv4.index = (INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS)) & TVN_MASK;
-	base->tv5.index = (INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS)) & TVN_MASK;
+	/*
+	 * The tv indices are always larger by one compared to the
+	 * respective parts of timer_jiffies. If all lower indices are
+	 * zero at initialisation, this is achieved by an (otherwise
+	 * unneccessary) invocation of the timer cascade on the first
+	 * timer interrupt. If not, we need to take it into account
+	 * here:
+	 */
+	j  = (base->tv1.index = INITIAL_JIFFIES & TVR_MASK) !=0;
+	j |= (base->tv2.index = ((INITIAL_JIFFIES >> TVR_BITS) + j)
+	                        & TVN_MASK) !=0;
+	j |= (base->tv3.index = ((INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS)) + j)
+	                        & TVN_MASK) !=0;
+	j |= (base->tv4.index = ((INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS)) + j)
+	                        & TVN_MASK) !=0;
+	      base->tv5.index = ((INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS)) + j)
+	                        & TVN_MASK;
 }

 static int __devinit timer_cpu_notify(struct notifier_block *self,

Re: [PATCH] fix nanosleep() granularity bumps

[george anzinger]

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



Here is a fix for the problem that eliminates the index from the 
structure.  The index ALWAYS depends on the current value of 
base->timer_jiffies in a rather simple way which is I exploit.  Either 
patch works, but this seems much simpler...

-g


Tim Schmielau wrote:
> On Tue, 18 Mar 2003, Tim Schmielau wrote:
> 
> 
>>Please don't yet forward to Linus. After twisting my little brain a bit
>>further, I see that the patch is still wrong if the lowest TVR_BITS of
>>INITIAL_JIFFIES happen to be zero while others are not.
> 
> 
> OK, this one looks ugly but should be correct, even in the case of a
> partial timer cascade on the first timer interrupt:
> 
> 
> --- linux-2.5.65/kernel/timer.c.orig	Tue Mar 18 13:02:39 2003
> +++ linux-2.5.65/kernel/timer.c	Tue Mar 18 13:41:53 2003
> @@ -1182,11 +1182,23 @@
>  		INIT_LIST_HEAD(base->tv1.vec + j);
> 
>  	base->timer_jiffies = INITIAL_JIFFIES;
> -	base->tv1.index = INITIAL_JIFFIES & TVR_MASK;
> -	base->tv2.index = (INITIAL_JIFFIES >> TVR_BITS) & TVN_MASK;
> -	base->tv3.index = (INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS)) & TVN_MASK;
> -	base->tv4.index = (INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS)) & TVN_MASK;
> -	base->tv5.index = (INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS)) & TVN_MASK;
> +	/*
> +	 * The tv indices are always larger by one compared to the
> +	 * respective parts of timer_jiffies. If all lower indices are
> +	 * zero at initialisation, this is achieved by an (otherwise
> +	 * unneccessary) invocation of the timer cascade on the first
> +	 * timer interrupt. If not, we need to take it into account
> +	 * here:
> +	 */
> +	j  = (base->tv1.index = INITIAL_JIFFIES & TVR_MASK) !=0;
> +	j |= (base->tv2.index = ((INITIAL_JIFFIES >> TVR_BITS) + j)
> +	                        & TVN_MASK) !=0;
> +	j |= (base->tv3.index = ((INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS)) + j)
> +	                        & TVN_MASK) !=0;
> +	j |= (base->tv4.index = ((INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS)) + j)
> +	                        & TVN_MASK) !=0;
> +	      base->tv5.index = ((INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS)) + j)
> +	                        & TVN_MASK;
>  }
> 
>  static int __devinit timer_cpu_notify(struct notifier_block *self,
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

[-- Attachment #2: hrtimers-runtimer-2.5.64.patch --]
[-- Type: text/plain, Size: 3159 bytes --]

diff -urP -I '\$Id:.*Exp \$' -X /usr/src/patch.exclude linux-2.5.64-kb/kernel/timer.c linux/kernel/timer.c
--- linux-2.5.64-kb/kernel/timer.c	2003-03-05 15:10:40.000000000 -0800
+++ linux/kernel/timer.c	2003-03-18 17:59:02.000000000 -0800
@@ -44,12 +44,10 @@
 #define TVR_MASK (TVR_SIZE - 1)
 
 typedef struct tvec_s {
-	int index;
 	struct list_head vec[TVN_SIZE];
 } tvec_t;
 
 typedef struct tvec_root_s {
-	int index;
 	struct list_head vec[TVR_SIZE];
 } tvec_root_t;
 
@@ -117,7 +115,7 @@
 		 * Can happen if you add a timer with expires == jiffies,
 		 * or you set a timer to go off in the past
 		 */
-		vec = base->tv1.vec + base->tv1.index;
+		vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
 	} else if (idx <= 0xffffffffUL) {
 		int i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
 		vec = base->tv5.vec + i;
@@ -351,12 +349,12 @@
 #endif
 
 
-static int cascade(tvec_base_t *base, tvec_t *tv)
+static int cascade(tvec_base_t *base, tvec_t *tv, int index)
 {
 	/* cascade all the timers from tv up one level */
 	struct list_head *head, *curr, *next;
 
-	head = tv->vec + tv->index;
+	head = tv->vec + index;
 	curr = head->next;
 	/*
 	 * We are removing _all_ timers from the list, so we don't  have to
@@ -374,7 +372,7 @@
 	}
 	INIT_LIST_HEAD(head);
 
-	return tv->index = (tv->index + 1) & TVN_MASK;
+	return index  & TVN_MASK;
 }
 
 /***
@@ -384,22 +382,26 @@
  * This function cascades all vectors and executes all expired timer
  * vectors.
  */
+#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK
+
 static inline void __run_timers(tvec_base_t *base)
 {
+	int index = base->timer_jiffies & TVR_MASK;
 	spin_lock_irq(&base->lock);
+	if(jiffies - base->timer_jiffies > 0)
 	while ((long)(jiffies - base->timer_jiffies) >= 0) {
 		struct list_head *head, *curr;
 
 		/*
 		 * Cascade timers:
 		 */
-		if (!base->tv1.index &&
-			(cascade(base, &base->tv2) == 1) &&
-				(cascade(base, &base->tv3) == 1) &&
-					cascade(base, &base->tv4) == 1)
-			cascade(base, &base->tv5);
+		if (!index &&
+			(cascade(base, &base->tv2, INDEX(0)) == 1) &&
+				(cascade(base, &base->tv3, INDEX(1)) == 1) &&
+					cascade(base, &base->tv4, INDEX(2)) == 1)
+			cascade(base, &base->tv5, INDEX(3));
 repeat:
-		head = base->tv1.vec + base->tv1.index;
+		head = base->tv1.vec + index;
 		curr = head->next;
 		if (curr != head) {
 			void (*fn)(unsigned long);
@@ -424,7 +426,6 @@
 			goto repeat;
 		}
 		++base->timer_jiffies; 
-		base->tv1.index = (base->tv1.index + 1) & TVR_MASK;
 	}
 #if CONFIG_SMP
 	base->running_timer = NULL;
@@ -1181,12 +1182,7 @@
 	for (j = 0; j < TVR_SIZE; j++)
 		INIT_LIST_HEAD(base->tv1.vec + j);
 
-	base->timer_jiffies = INITIAL_JIFFIES;
-	base->tv1.index = INITIAL_JIFFIES & TVR_MASK;
-	base->tv2.index = (INITIAL_JIFFIES >> TVR_BITS) & TVN_MASK;
-	base->tv3.index = (INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS)) & TVN_MASK;
-	base->tv4.index = (INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS)) & TVN_MASK;
-	base->tv5.index = (INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS)) & TVN_MASK;
+	base->timer_jiffies = jiffies -1;
 }
 	
 static int __devinit timer_cpu_notify(struct notifier_block *self, 

Re: [PATCH] fix nanosleep() granularity bumps

[Andrew Morton]

george anzinger <george@mvista.com> wrote:
>
> 
> 
> Here is a fix for the problem that eliminates the index from the 
> structure.  The index ALWAYS depends on the current value of 
> base->timer_jiffies in a rather simple way which is I exploit.  Either 
> patch works, but this seems much simpler...

Seems to be a nice change.  I think it would be better to get Tim's fix into
Linus's tree and let your rationalisation bake for a while in -mm.

There is currently a mysterious timer lockup happening on power4 machines. 
I'd like to keep these changes well-separated in time so we can get an
understanding of what code changes correlate with changed behaviour.

There are timer changes in Linus's post-2.5.65 tree and your patch generates
zillions of rejects against everything.  Can you send me a diff against
Linus's latest sometime?

Re: [PATCH] fix nanosleep() granularity bumps

[george anzinger]

Andrew Morton wrote:
> george anzinger <george@mvista.com> wrote:
> 
>>
>>
>>Here is a fix for the problem that eliminates the index from the 
>>structure.  The index ALWAYS depends on the current value of 
>>base->timer_jiffies in a rather simple way which is I exploit.  Either 
>>patch works, but this seems much simpler...
> 
> 
> Seems to be a nice change.  I think it would be better to get Tim's fix into
> Linus's tree and let your rationalisation bake for a while in -mm.
> 
> There is currently a mysterious timer lockup happening on power4 machines. 
> I'd like to keep these changes well-separated in time so we can get an
> understanding of what code changes correlate with changed behaviour.

Tell me more...
> 
> There are timer changes in Linus's post-2.5.65 tree and your patch generates
> zillions of rejects against everything.  Can you send me a diff against
> Linus's latest sometime?

Sure, possibly even tonight.

-g



> 
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: [PATCH] fix nanosleep() granularity bumps

[Andrew Morton]

george anzinger <george@mvista.com> wrote:
>
> > There is currently a mysterious timer lockup happening on power4 machines. 
> > I'd like to keep these changes well-separated in time so we can get an
> > understanding of what code changes correlate with changed behaviour.
> 
> Tell me more...

Don't know much more really.  Anton has a machine which fairly repeatably
locks up at jiffies = 0x100104100.

> Latest BK. Ive been getting this lockup for a while,
> It _always_ triggers when jiffies = 0x100104100.
> 
> c000000000068a14 cascade+0x74
> c0000000000694a4 run_timer_softirq+0x244
> c0000000000614f0 do_softirq+0x174
> c000000000012c10 timer_interrupt+0x1a8
> c000000000012a0c cpu_idle+0xc0

This _might_ be the timer-handler-does-add_timer(right now) lockup which was
fixed in Linus's tree today.

Re: [PATCH] fix nanosleep() granularity bumps

[Tim Schmielau]

On Tue, 18 Mar 2003, Andrew Morton wrote:

> george anzinger <george@mvista.com> wrote:
> > Here is a fix for the problem that eliminates the index from the
> > structure.
[...]
> Seems to be a nice change.  I think it would be better to get Tim's fix into
> Linus's tree and let your rationalisation bake for a while in -mm.

I'm all for this way. Push my quick'n ugly patch to mainline soon to get
thinks working again. Have at least one mainline release before changing
again to start off from something working. Then add George's patch when
it has matured.

> There is currently a mysterious timer lockup happening on power4 machines.
> I'd like to keep these changes well-separated in time so we can get an
> understanding of what code changes correlate with changed behaviour.

Can this problem be reproduced with INITIAL_JIFFIES=0? Just to make sure I
didn't break something more.


On Tue, 18 Mar 2003, George Anzinger wrote:

> Here is a fix for the problem that eliminates the index from the
> structure.  The index ALWAYS depends on the current value of
> base->timer_jiffies in a rather simple way which is I exploit.  Either
> patch works, but this seems much simpler...
[...]
> @@ -384,22 +382,26 @@
>   * This function cascades all vectors and executes all expired timer
>   * vectors.
>   */
> +#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) &
TVN_MASK

No, with the current implementation we need
 #define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS) +1) &
 TVN_MASK
although I'd like to see that cleaned up.

> +
> static inline void __run_timers(tvec_base_t *base)
>  {
> +	int index = base->timer_jiffies & TVR_MASK;
>  	spin_lock_irq(&base->lock);
> +	if(jiffies - base->timer_jiffies > 0)
>  	while ((long)(jiffies - base->timer_jiffies) >= 0) {
>  		struct list_head *head, *curr;
>

Are the doubled 'if' and 'while' really what you meant?

> @@ -1181,12 +1182,7 @@
>  	for (j = 0; j < TVR_SIZE; j++)
>  		INIT_LIST_HEAD(base->tv1.vec + j);
>
> -	base->timer_jiffies = INITIAL_JIFFIES;
> -	base->tv1.index = INITIAL_JIFFIES & TVR_MASK;
> -	base->tv2.index = (INITIAL_JIFFIES >> TVR_BITS) & TVN_MASK;
> -	base->tv3.index = (INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS)) &
TVN_MASK;
> -	base->tv4.index = (INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS)) &
TVN_MASK;
> -	base->tv5.index = (INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS)) &
TVN_MASK;
> +	base->timer_jiffies = jiffies -1;
>  }
>
>  static int __devinit timer_cpu_notify(struct notifier_block *self,

Why 'jiffies -1'? This will just be made up for in the first
timer interrupt, where timer_jiffies will get incremented twice.


Did you bother to test the patch? It doesn't even boot for me, and I don't
see how it is supposed to.
I'll look into it more closely in the evening. Have to go to work now.

Tim

Re: [PATCH] fix nanosleep() granularity bumps

[george anzinger]

Tim Schmielau wrote:
> On Tue, 18 Mar 2003, Andrew Morton wrote:
> 
> 
>>george anzinger <george@mvista.com> wrote:
>>
>>>Here is a fix for the problem that eliminates the index from the
>>>structure.
> 
> [...]
> 
>>Seems to be a nice change.  I think it would be better to get Tim's fix into
>>Linus's tree and let your rationalisation bake for a while in -mm.
> 
> 
> I'm all for this way. Push my quick'n ugly patch to mainline soon to get
> thinks working again. Have at least one mainline release before changing
> again to start off from something working. Then add George's patch when
> it has matured.
> 
> 
>>There is currently a mysterious timer lockup happening on power4 machines.
>>I'd like to keep these changes well-separated in time so we can get an
>>understanding of what code changes correlate with changed behaviour.
> 
> 
> Can this problem be reproduced with INITIAL_JIFFIES=0? Just to make sure I
> didn't break something more.
> 
> 
> On Tue, 18 Mar 2003, George Anzinger wrote:
> 
> 
>>Here is a fix for the problem that eliminates the index from the
>>structure.  The index ALWAYS depends on the current value of
>>base->timer_jiffies in a rather simple way which is I exploit.  Either
>>patch works, but this seems much simpler...
> 
> [...]
> 
>>@@ -384,22 +382,26 @@
>>  * This function cascades all vectors and executes all expired timer
>>  * vectors.
>>  */
>>+#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) &
> 
> TVN_MASK
> 
> No, with the current implementation we need
>  #define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS) +1) &
>  TVN_MASK
> although I'd like to see that cleaned up.

As near as I can tell this is not true if done here.  I could be 
wrong, but I think the tests will fail if the "1" is added.  I will 
try it though, just to be sure.
> 
> 
>>+
>>static inline void __run_timers(tvec_base_t *base)
>> {
>>+	int index = base->timer_jiffies & TVR_MASK;
>> 	spin_lock_irq(&base->lock);
>>+	if(jiffies - base->timer_jiffies > 0)
>> 	while ((long)(jiffies - base->timer_jiffies) >= 0) {
>> 		struct list_head *head, *curr;
>>
> 
> 
> Are the doubled 'if' and 'while' really what you meant?

Darn, you are right. The if is left over debug code.  Teach me to do 
ifs with out {}.
> 
> 
>>@@ -1181,12 +1182,7 @@
>> 	for (j = 0; j < TVR_SIZE; j++)
>> 		INIT_LIST_HEAD(base->tv1.vec + j);
>>
>>-	base->timer_jiffies = INITIAL_JIFFIES;
>>-	base->tv1.index = INITIAL_JIFFIES & TVR_MASK;
>>-	base->tv2.index = (INITIAL_JIFFIES >> TVR_BITS) & TVN_MASK;
>>-	base->tv3.index = (INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS)) &
> 
> TVN_MASK;
> 
>>-	base->tv4.index = (INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS)) &
> 
> TVN_MASK;
> 
>>-	base->tv5.index = (INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS)) &
> 
> TVN_MASK;
> 
>>+	base->timer_jiffies = jiffies -1;
>> }
>>
>> static int __devinit timer_cpu_notify(struct notifier_block *self,
> 
> 
> Why 'jiffies -1'? This will just be made up for in the first
> timer interrupt, where timer_jiffies will get incremented twice.

I wanted to be conservative.  Jiffies should work, but as you say it 
will be made up.  I did not want ANY possibity of getting a timer in 
the list ahead of where the list was.
> 
> 
> Did you bother to test the patch? It doesn't even boot for me, and I don't
> see how it is supposed to.

I did, and it booted and ran the clock_nanosleep test (actually a more 
rigerous verson of same).

> I'll look into it more closely in the evening. Have to go to work now.
> 
> Tim
> 
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: [PATCH] fix nanosleep() granularity bumps

[george anzinger]

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

The attached patch is for 2.5.65.  As of this moment, the bk patch has 
not been posted to the snapshots directory.  I will wait for that to 
update.

For what its worth, can someone explain how the add_timer call from 
run_timers was causing a problem.  The code looks right to me, unless 
the caller is so nasty as to continue to do the same thing (which 
would loop forever).  In this case, the simple fix is to bump the 
base->timer_jiffies at the beginning of the loop rather than the end. 
   This would cause the new timer to be put in the next jiffie instead 
of the current one AND it is free!

-g



Tim Schmielau wrote:
> 
> On Tue, 18 Mar 2003, Andrew Morton wrote:
> 
> 
>>george anzinger <george@mvista.com> wrote:
>>
>>>Here is a fix for the problem that eliminates the index from the
>>>structure.
> 
> [...]
> 
>>Seems to be a nice change.  I think it would be better to get Tim's fix into
>>Linus's tree and let your rationalisation bake for a while in -mm.
> 
> 
> I'm all for this way. Push my quick'n ugly patch to mainline soon to get
> thinks working again. Have at least one mainline release before changing
> again to start off from something working. Then add George's patch when
> it has matured.
> 
> 
>>There is currently a mysterious timer lockup happening on power4 machines.
>>I'd like to keep these changes well-separated in time so we can get an
>>understanding of what code changes correlate with changed behaviour.
> 
> 
> Can this problem be reproduced with INITIAL_JIFFIES=0? Just to make sure I
> didn't break something more.
> 
> 
> On Tue, 18 Mar 2003, George Anzinger wrote:
> 
> 
>>Here is a fix for the problem that eliminates the index from the
>>structure.  The index ALWAYS depends on the current value of
>>base->timer_jiffies in a rather simple way which is I exploit.  Either
>>patch works, but this seems much simpler...
> 
> [...]
> 
>>@@ -384,22 +382,26 @@
>>  * This function cascades all vectors and executes all expired timer
>>  * vectors.
>>  */
>>+#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) &
> 
> TVN_MASK
> 
> No, with the current implementation we need
>  #define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS) +1) &
>  TVN_MASK
> although I'd like to see that cleaned up.

I tried with the +1 and boot hangs trying to set up networking.  I 
think the difference is that the init code is trying to set things up 
the way they would look AFTER cascade executes and this is doing it 
BEFORE the cascade call.
> 
> 
>>+
>>static inline void __run_timers(tvec_base_t *base)
>> {
>>+	int index = base->timer_jiffies & TVR_MASK;
>> 	spin_lock_irq(&base->lock);
>>+	if(jiffies - base->timer_jiffies > 0)
>> 	while ((long)(jiffies - base->timer_jiffies) >= 0) {
>> 		struct list_head *head, *curr;
>>
> 
> 
> Are the doubled 'if' and 'while' really what you meant?

Remove in the attached patch :)
> 
> 
>>@@ -1181,12 +1182,7 @@
>> 	for (j = 0; j < TVR_SIZE; j++)
>> 		INIT_LIST_HEAD(base->tv1.vec + j);
>>
>>-	base->timer_jiffies = INITIAL_JIFFIES;
>>-	base->tv1.index = INITIAL_JIFFIES & TVR_MASK;
>>-	base->tv2.index = (INITIAL_JIFFIES >> TVR_BITS) & TVN_MASK;
>>-	base->tv3.index = (INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS)) &
> 
> TVN_MASK;
> 
>>-	base->tv4.index = (INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS)) &
> 
> TVN_MASK;
> 
>>-	base->tv5.index = (INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS)) &
> 
> TVN_MASK;
> 
>>+	base->timer_jiffies = jiffies -1;
>> }
>>
>> static int __devinit timer_cpu_notify(struct notifier_block *self,
> 
> 
> Why 'jiffies -1'? This will just be made up for in the first
> timer interrupt, where timer_jiffies will get incremented twice.

Again, I removed the -1 in the attached.
> 
> 
> Did you bother to test the patch? It doesn't even boot for me, and I don't
> see how it is supposed to.
> I'll look into it more closely in the evening. Have to go to work now.

The old one ran on 2.5.64 but not 2.5.65 ???  I found and fixed a bug 
(index needs to be caculated INSIDE the while loop) that seems to have 
been the cause.
> 
> Tim


-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

[-- Attachment #2: hrtimers-runtimer-2.5.65.patch --]
[-- Type: text/plain, Size: 3117 bytes --]

diff -urP -I '\$Id:.*Exp \$' -X /usr/src/patch.exclude linux-2.5.65-kb/kernel/timer.c linux/kernel/timer.c
--- linux-2.5.65-kb/kernel/timer.c	2003-03-05 15:10:40.000000000 -0800
+++ linux/kernel/timer.c	2003-03-19 01:08:24.000000000 -0800
@@ -44,12 +44,10 @@
 #define TVR_MASK (TVR_SIZE - 1)
 
 typedef struct tvec_s {
-	int index;
 	struct list_head vec[TVN_SIZE];
 } tvec_t;
 
 typedef struct tvec_root_s {
-	int index;
 	struct list_head vec[TVR_SIZE];
 } tvec_root_t;
 
@@ -117,7 +115,7 @@
 		 * Can happen if you add a timer with expires == jiffies,
 		 * or you set a timer to go off in the past
 		 */
-		vec = base->tv1.vec + base->tv1.index;
+		vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
 	} else if (idx <= 0xffffffffUL) {
 		int i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
 		vec = base->tv5.vec + i;
@@ -351,12 +349,12 @@
 #endif
 
 
-static int cascade(tvec_base_t *base, tvec_t *tv)
+static int cascade(tvec_base_t *base, tvec_t *tv, int index)
 {
 	/* cascade all the timers from tv up one level */
 	struct list_head *head, *curr, *next;
 
-	head = tv->vec + tv->index;
+	head = tv->vec + index;
 	curr = head->next;
 	/*
 	 * We are removing _all_ timers from the list, so we don't  have to
@@ -374,7 +372,7 @@
 	}
 	INIT_LIST_HEAD(head);
 
-	return tv->index = (tv->index + 1) & TVN_MASK;
+	return index  & TVN_MASK;
 }
 
 /***
@@ -384,22 +382,25 @@
  * This function cascades all vectors and executes all expired timer
  * vectors.
  */
+#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK
+
 static inline void __run_timers(tvec_base_t *base)
 {
 	spin_lock_irq(&base->lock);
 	while ((long)(jiffies - base->timer_jiffies) >= 0) {
 		struct list_head *head, *curr;
+		int index = base->timer_jiffies & TVR_MASK;
 
 		/*
 		 * Cascade timers:
 		 */
-		if (!base->tv1.index &&
-			(cascade(base, &base->tv2) == 1) &&
-				(cascade(base, &base->tv3) == 1) &&
-					cascade(base, &base->tv4) == 1)
-			cascade(base, &base->tv5);
+		if (!index &&
+			(cascade(base, &base->tv2, INDEX(0)) == 1) &&
+				(cascade(base, &base->tv3, INDEX(1)) == 1) &&
+					cascade(base, &base->tv4, INDEX(2)) == 1)
+			cascade(base, &base->tv5, INDEX(3));
 repeat:
-		head = base->tv1.vec + base->tv1.index;
+		head = base->tv1.vec + index;
 		curr = head->next;
 		if (curr != head) {
 			void (*fn)(unsigned long);
@@ -424,7 +425,6 @@
 			goto repeat;
 		}
 		++base->timer_jiffies; 
-		base->tv1.index = (base->tv1.index + 1) & TVR_MASK;
 	}
 #if CONFIG_SMP
 	base->running_timer = NULL;
@@ -1181,12 +1181,7 @@
 	for (j = 0; j < TVR_SIZE; j++)
 		INIT_LIST_HEAD(base->tv1.vec + j);
 
-	base->timer_jiffies = INITIAL_JIFFIES;
-	base->tv1.index = INITIAL_JIFFIES & TVR_MASK;
-	base->tv2.index = (INITIAL_JIFFIES >> TVR_BITS) & TVN_MASK;
-	base->tv3.index = (INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS)) & TVN_MASK;
-	base->tv4.index = (INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS)) & TVN_MASK;
-	base->tv5.index = (INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS)) & TVN_MASK;
+	base->timer_jiffies = jiffies;
 }
 	
 static int __devinit timer_cpu_notify(struct notifier_block *self, 

Re: [PATCH] fix nanosleep() granularity bumps

[Tim Schmielau]

On Wed, 19 Mar 2003, george anzinger wrote:

> In this case, the simple fix is to bump the
> base->timer_jiffies at the beginning of the loop rather than the end.
>    This would cause the new timer to be put in the next jiffie instead
> of the current one AND it is free!

Yes, doing it this way looks correct to me.

> > No, with the current implementation we need
> >  #define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS) +1) &
> >  TVN_MASK
> > although I'd like to see that cleaned up.
>
> I tried with the +1 and boot hangs trying to set up networking.  I
> think the difference is that the init code is trying to set things up
> the way they would look AFTER cascade executes and this is doing it
> BEFORE the cascade call.

With the above change, it should be correct without the +1

> > Why 'jiffies -1'? This will just be made up for in the first
> > timer interrupt, where timer_jiffies will get incremented twice.
>
> Again, I removed the -1 in the attached.

If you really want to be conservative, we'd better start with
INITIAL_JIFFIES. Should be the same anyways. But if not, we might lose a
timer scheduled for INITIAL_JIFFIES (not that I think it's possible to
insert one before timer initialisation in the first place :-)
or even a timer cascade.

> > Did you bother to test the patch? It doesn't even boot for me, and I don't
> > see how it is supposed to.
> > I'll look into it more closely in the evening. Have to go to work now.
>
> The old one ran on 2.5.64 but not 2.5.65 ???  I found and fixed a bug
> (index needs to be caculated INSIDE the while loop) that seems to have
> been the cause.

Ok will test in the evening.

Tim

Re: [PATCH] fix nanosleep() granularity bumps

[george anzinger]

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

I found a problem with the last version.  The attached is for 
2.5.65-1.1171 (i.e. after the other post 2.5.65 changes).  The bug is 
fixed, and the code even simpler here.

The problem in the prior patch was that cascade should return:
(index +1) &... not  index &...

Here I changed the call to cascade() to expect "index" back so it 
checks for 0 instead of 1.  Nice and simple.

-g

Tim Schmielau wrote:
> On Wed, 19 Mar 2003, george anzinger wrote:
> 
> 
>>In this case, the simple fix is to bump the
>>base->timer_jiffies at the beginning of the loop rather than the end.
>>   This would cause the new timer to be put in the next jiffie instead
>>of the current one AND it is free!
> 
> 
> Yes, doing it this way looks correct to me.
> 
> 
>>>No, with the current implementation we need
>>> #define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS) +1) &
>>> TVN_MASK
>>>although I'd like to see that cleaned up.
>>
>>I tried with the +1 and boot hangs trying to set up networking.  I
>>think the difference is that the init code is trying to set things up
>>the way they would look AFTER cascade executes and this is doing it
>>BEFORE the cascade call.
> 
> 
> With the above change, it should be correct without the +1
> 
> 
>>>Why 'jiffies -1'? This will just be made up for in the first
>>>timer interrupt, where timer_jiffies will get incremented twice.
>>
>>Again, I removed the -1 in the attached.
> 
> 
> If you really want to be conservative, we'd better start with
> INITIAL_JIFFIES. Should be the same anyways. But if not, we might lose a
> timer scheduled for INITIAL_JIFFIES (not that I think it's possible to
> insert one before timer initialisation in the first place :-)
> or even a timer cascade.
> 
> 
>>>Did you bother to test the patch? It doesn't even boot for me, and I don't
>>>see how it is supposed to.
>>>I'll look into it more closely in the evening. Have to go to work now.
>>
>>The old one ran on 2.5.64 but not 2.5.65 ???  I found and fixed a bug
>>(index needs to be caculated INSIDE the while loop) that seems to have
>>been the cause.
> 
> 
> Ok will test in the evening.
> 
> Tim
> 
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

[-- Attachment #2: hrtimers-run-2.5.65-1.1171.patch --]
[-- Type: text/plain, Size: 3304 bytes --]

diff -urP -I '\$Id:.*Exp \$' -X /usr/src/patch.exclude linux-2.5.65-1.1171-kb/kernel/timer.c linux/kernel/timer.c
--- linux-2.5.65-1.1171-kb/kernel/timer.c	2003-03-19 12:32:28.000000000 -0800
+++ linux/kernel/timer.c	2003-03-19 13:08:24.000000000 -0800
@@ -44,12 +44,10 @@
 #define TVR_MASK (TVR_SIZE - 1)
 
 typedef struct tvec_s {
-	int index;
 	struct list_head vec[TVN_SIZE];
 } tvec_t;
 
 typedef struct tvec_root_s {
-	int index;
 	struct list_head vec[TVR_SIZE];
 } tvec_root_t;
 
@@ -134,7 +132,7 @@
 		 * Can happen if you add a timer with expires == jiffies,
 		 * or you set a timer to go off in the past
 		 */
-		vec = base->tv1.vec + base->tv1.index;
+		vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
 	} else if (idx <= 0xffffffffUL) {
 		int i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
 		vec = base->tv5.vec + i;
@@ -368,12 +366,12 @@
 #endif
 
 
-static int cascade(tvec_base_t *base, tvec_t *tv)
+static int cascade(tvec_base_t *base, tvec_t *tv, int index)
 {
 	/* cascade all the timers from tv up one level */
 	struct list_head *head, *curr;
 
-	head = tv->vec + tv->index;
+	head = tv->vec + index;
 	curr = head->next;
 	/*
 	 * We are removing _all_ timers from the list, so we don't  have to
@@ -389,7 +387,7 @@
 	}
 	INIT_LIST_HEAD(head);
 
-	return tv->index = (tv->index + 1) & TVN_MASK;
+	return index;
 }
 
 /***
@@ -399,6 +397,8 @@
  * This function cascades all vectors and executes all expired timer
  * vectors.
  */
+#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK
+
 static inline void __run_timers(tvec_base_t *base)
 {
 	struct timer_list *timer;
@@ -407,18 +407,19 @@
 	while (time_after_eq(jiffies, base->timer_jiffies)) {
 		LIST_HEAD(deferred_timers);
 		struct list_head *head;
-
+ 		int index = base->timer_jiffies & TVR_MASK;
+ 
 		/*
 		 * Cascade timers:
 		 */
-		if (!base->tv1.index &&
-			(cascade(base, &base->tv2) == 1) &&
-				(cascade(base, &base->tv3) == 1) &&
-					cascade(base, &base->tv4) == 1)
-			cascade(base, &base->tv5);
+		if (!index &&
+			(! cascade(base, &base->tv2, INDEX(0))) &&
+				(! cascade(base, &base->tv3, INDEX(1))) &&
+					! cascade(base, &base->tv4, INDEX(2)))
+			cascade(base, &base->tv5, INDEX(3));
 		base->run_timer_list_running = &deferred_timers;
 repeat:
-		head = base->tv1.vec + base->tv1.index;
+		head = base->tv1.vec + index;
 		if (!list_empty(head)) {
 			void (*fn)(unsigned long);
 			unsigned long data;
@@ -437,7 +438,6 @@
 		}
 		base->run_timer_list_running = NULL;
 		++base->timer_jiffies; 
-		base->tv1.index = (base->tv1.index + 1) & TVR_MASK;
 		while (!list_empty(&deferred_timers)) {
 			timer = list_entry(deferred_timers.prev,
 						struct timer_list, entry);
@@ -1198,12 +1198,7 @@
 	for (j = 0; j < TVR_SIZE; j++)
 		INIT_LIST_HEAD(base->tv1.vec + j);
 
-	base->timer_jiffies = INITIAL_JIFFIES;
-	base->tv1.index = INITIAL_JIFFIES & TVR_MASK;
-	base->tv2.index = (INITIAL_JIFFIES >> TVR_BITS) & TVN_MASK;
-	base->tv3.index = (INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS)) & TVN_MASK;
-	base->tv4.index = (INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS)) & TVN_MASK;
-	base->tv5.index = (INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS)) & TVN_MASK;
+	base->timer_jiffies = jiffies;
 }
 	
 static int __devinit timer_cpu_notify(struct notifier_block *self, 

Re: [PATCH] Remove defered timer list in favor of moving the list time update

[george anzinger]

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

Andrew Morton wrote:
> george anzinger <george@mvista.com> wrote:
> 
>>I found a problem with the last version.  The attached is for 
>>2.5.65-1.1171 (i.e. after the other post 2.5.65 changes).  The bug is 
>>fixed, and theAndrew Morton wrote:
 > george anzinger <george@mvista.com> wrote:
 >
 >>I found a problem with the last version.  The attached is for
 >>2.5.65-1.1171 (i.e. after the other post 2.5.65 changes).  The bug is
 >>fixed, and the code even simpler here.
 >
 >
 > Thanks, I'll queue that up after Tim's stuff is merged.

And this removes the defered queue in favor of just moving the list 
time update to just prior to the repeat label.  (Apply after my 
"bumps" patch.)

Do I have the right Andrea?
 >
 >

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml
  code even simpler here.
> 
> 
> Thanks, I'll queue that up after Tim's stuff is merged.
> 
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

[-- Attachment #2: hrtimers-run-def.patch --]
[-- Type: text/plain, Size: 2022 bytes --]

--- linux-2.5.65-1.1171-run/kernel/timer.cX	2003-03-19 13:08:24.000000000 -0800
+++ linux/kernel/timer.c	2003-03-19 14:16:53.000000000 -0800
@@ -55,7 +55,6 @@
 	spinlock_t lock;
 	unsigned long timer_jiffies;
 	struct timer_list *running_timer;
-	struct list_head *run_timer_list_running;
 	tvec_root_t tv1;
 	tvec_t tv2;
 	tvec_t tv3;
@@ -100,12 +99,6 @@
 		check_timer_failed(timer);
 }
 
-/*
- * If a timer handler re-adds the timer with expires == jiffies, the timer
- * running code can lock up.  So here we detect that situation and park the
- * timer onto base->run_timer_list_running.  It will be added to the main timer
- * structures later, by __run_timers().
- */
 
 static void internal_add_timer(tvec_base_t *base, struct timer_list *timer)
 {
@@ -113,9 +106,7 @@
 	unsigned long idx = expires - base->timer_jiffies;
 	struct list_head *vec;
 
-	if (base->run_timer_list_running) {
-		vec = base->run_timer_list_running;
-	} else if (idx < TVR_SIZE) {
+	if (idx < TVR_SIZE) {
 		int i = expires & TVR_MASK;
 		vec = base->tv1.vec + i;
 	} else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
@@ -405,7 +396,6 @@
 
 	spin_lock_irq(&base->lock);
 	while (time_after_eq(jiffies, base->timer_jiffies)) {
-		LIST_HEAD(deferred_timers);
 		struct list_head *head;
  		int index = base->timer_jiffies & TVR_MASK;
  
@@ -417,7 +407,7 @@
 				(! cascade(base, &base->tv3, INDEX(1))) &&
 					! cascade(base, &base->tv4, INDEX(2)))
 			cascade(base, &base->tv5, INDEX(3));
-		base->run_timer_list_running = &deferred_timers;
+		++base->timer_jiffies; 
 repeat:
 		head = base->tv1.vec + index;
 		if (!list_empty(head)) {
@@ -436,14 +426,6 @@
 			spin_lock_irq(&base->lock);
 			goto repeat;
 		}
-		base->run_timer_list_running = NULL;
-		++base->timer_jiffies; 
-		while (!list_empty(&deferred_timers)) {
-			timer = list_entry(deferred_timers.prev,
-						struct timer_list, entry);
-			list_del(&timer->entry);
-			internal_add_timer(base, timer);
-		}
 	}
 	set_running_timer(base, NULL);
 	spin_unlock_irq(&base->lock);

Re: [PATCH] fix nanosleep() granularity bumps

[Tim Schmielau]

On Wed, 19 Mar 2003, george anzinger wrote:

> I found a problem with the last version.  The attached is for
> 2.5.65-1.1171 (i.e. after the other post 2.5.65 changes).  The bug is
> fixed, and the code even simpler here.
>
> The problem in the prior patch was that cascade should return:
> (index +1) &... not  index &...

I haven't had time yet to look into any of the patches more closely,
but ...

> Here I changed the call to cascade() to expect "index" back so it
> checks for 0 instead of 1.  Nice and simple.

... this is what I expected to come out from our simplification and what
made me suspicious against the previous version.
So I'd just guess the patch is fine now.

Tim

Re: [PATCH] fix nanosleep() granularity bumps

[Andrew Morton]

george anzinger <george@mvista.com> wrote:
>
> The attached patch is for 2.5.65.  As of this moment, the bk patch has 
> not been posted to the snapshots directory.  I will wait for that to 
> update.

Don't use the snapshots directory.  Use

	http://www.kernel.org/pub/linux/kernel/v2.5/testing/cset/

It is more up to date.

> For what its worth, can someone explain how the add_timer call from 
> run_timers was causing a problem.  The code looks right to me, unless 
> the caller is so nasty as to continue to do the same thing (which 
> would loop forever).

That was the problem.

> In this case, the simple fix is to bump the 
> base->timer_jiffies at the beginning of the loop rather than the end. 
>    This would cause the new timer to be put in the next jiffie instead 
> of the current one AND it is free!

Didn't think of that - I just ported up Andrea's fix.

Re: [PATCH] fix nanosleep() granularity bumps

[george anzinger]

Andrew Morton wrote:
> george anzinger <george@mvista.com> wrote:
> 
>>The attached patch is for 2.5.65.  As of this moment, the bk patch has 
>>not been posted to the snapshots directory.  I will wait for that to 
>>update.
> 
> 
> Don't use the snapshots directory.  Use
> 
> 	http://www.kernel.org/pub/linux/kernel/v2.5/testing/cset/

but then I need to pull each patch ... :)

-g
> 
> It is more up to date.
> 
> 
>>For what its worth, can someone explain how the add_timer call from 
>>run_timers was causing a problem.  The code looks right to me, unless 
>>the caller is so nasty as to continue to do the same thing (which 
>>would loop forever).
> 
> 
> That was the problem.
> 
> 
>>In this case, the simple fix is to bump the 
>>base->timer_jiffies at the beginning of the loop rather than the end. 
>>   This would cause the new timer to be put in the next jiffie instead 
>>of the current one AND it is free!
> 
> 
> Didn't think of that - I just ported up Andrea's fix.
> 
> 
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: [PATCH] fix nanosleep() granularity bumps

[Andrew Morton]

george anzinger <george@mvista.com> wrote:
>
> Andrew Morton wrote:
> > george anzinger <george@mvista.com> wrote:
> > 
> >>The attached patch is for 2.5.65.  As of this moment, the bk patch has 
> >>not been posted to the snapshots directory.  I will wait for that to 
> >>update.
> > 
> > 
> > Don't use the snapshots directory.  Use
> > 
> > 	http://www.kernel.org/pub/linux/kernel/v2.5/testing/cset/
> 
> but then I need to pull each patch ... :)
> 

No.  The link at the top:

	"Gzipped full patch from v2.5.65 to ChangeSet 1.1171" 

is the diff from 2.5.65 to tip-of-tree.

Re: [PATCH] fix nanosleep() granularity bumps

[george anzinger]

Andrew Morton wrote:
> george anzinger <george@mvista.com> wrote:
> 
>>Andrew Morton wrote:
>>
>>>george anzinger <george@mvista.com> wrote:
>>>
>>>
>>>>The attached patch is for 2.5.65.  As of this moment, the bk patch has 
>>>>not been posted to the snapshots directory.  I will wait for that to 
>>>>update.
>>>
>>>
>>>Don't use the snapshots directory.  Use
>>>
>>>	http://www.kernel.org/pub/linux/kernel/v2.5/testing/cset/
>>
>>but then I need to pull each patch ... :)
>>
> 
> 
> No.  The link at the top:
> 
> 	"Gzipped full patch from v2.5.65 to ChangeSet 1.1171" 
> 
> is the diff from 2.5.65 to tip-of-tree.

Cool :)  Wish it were ...patch.gz instead of txt.gz, but then I would 
probably complain if I was hung with a new rope :)
> 
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml