Re: [BUG] nanosleep() granularity bumps up in 2.5.64 (was: [PATCH] settimeofday() not synchronised with gettimeofday())

Re: [BUG] nanosleep() granularity bumps up in 2.5.64 (was: [PATCH] settimeofday() not synchronised with gettimeofday())

[Eric Piel]

David Mosberger wrote:
> Are you running ntp?
Yes (I hadn't noticed it) but it was not connected to any server and
disabling it doesn't change the results.
 

> 
> On 2.5:
> 
>         $ time sleep 16
>         real    0m16.002s
>         user    0m0.001s
>         sys     0m0.002s
> 
>         $ time sleep 16.02
>         real    0m25.189s
>         user    0m0.000s
>         sys     0m0.001s
> 
> So clearly something very strange is going on.  My suspicion is that
> the bug was introduced back when x86 switched from 100Hz to 1000Hz
> ticks, but that's just a guess.  Eric, would you be
> able/willing/interested to look into this?
Sure, I aim at porting the high resolution timers but any annoying bug
related to the time can be interesting to remove.

Coincidently Vita has just reported a bug on the lkml which, after a
closer look, seems to be the same:
>   When playing with select() timeout values I found that granularity
> of nanosleep() in 2.5.64 kernel bumps to 256 msec. Trying to get finer
> granularity it ends up sleeping to the next multiple of 256 msec

>From what I understand their is a bug in the timers that causes a big
granularity. The case of Vita is a very good example. Also, after 16s it
seems the granuality (slowly?!) jumps from 1/64th s to 16s! :
sleep requested	 time obtained
14.000000000     14.006201744
15.000000000     15.006647110
16.000000000     16.007089615
17.000000000     18.742679596
18.000000000     32.014190674
19.000000000     32.014190674
20.000000000     32.014190674

I think lines like that from patch-2.5.64 are very suspicious to be
related to the bug:
+	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;

Any idea/sugestion/patch is welcomed. Whatever, I will try to fix this
as soon as I'm back from my week end :-)

	Eric

Re: [Linux-ia64] Re: [BUG] nanosleep() granularity bumps up in 2.5.64 (was: [PATCH] settimeofday() not synchronised with gettimeofday())

[Matthew Wilcox]

On Fri, Mar 14, 2003 at 03:34:36PM +0100, Eric Piel wrote:
> I think lines like that from patch-2.5.64 are very suspicious to be
> related to the bug:
> +	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;

No, I don't think so.  Those lines are for starting `jiffies' at a very
high number so we spot jiffie-wrap bugs early on.

-- 
"It's not Hollywood.  War is real, war is primarily not about defeat or
victory, it is about death.  I've seen thousands and thousands of dead bodies.
Do you think I want to have an academic debate on this subject?" -- Robert Fisk

Re: [Linux-ia64] Re: [BUG] nanosleep() granularity bumps up in 2.5.64 (was: [PATCH] settimeofday() not synchronised with gettimeofday())

[Vitezslav Samel]

On Fri, Mar 14, 2003 at 02:48:59PM +0000, Matthew Wilcox wrote:
> On Fri, Mar 14, 2003 at 03:34:36PM +0100, Eric Piel wrote:
> > I think lines like that from patch-2.5.64 are very suspicious to be
> > related to the bug:
> > +	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;
> 
> No, I don't think so.  Those lines are for starting `jiffies' at a very
> high number so we spot jiffie-wrap bugs early on.

  The nanosleep() bug narrowed down to 2.5.63-bk2. That's version, the "initial
jiffies" patch went in. And yes, it's on i686 machine.

	Cheers,
		Vita

Re: [BUG] nanosleep() granularity bumps up in 2.5.64

[Tim Schmielau]

On Mon, 17 Mar 2003, Vitezslav Samel wrote:

> On Fri, Mar 14, 2003 at 02:48:59PM +0000, Matthew Wilcox wrote:
> > On Fri, Mar 14, 2003 at 03:34:36PM +0100, Eric Piel wrote:
> > > I think lines like that from patch-2.5.64 are very suspicious to be
> > > related to the bug:
> > > +	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;
> >
> > No, I don't think so.  Those lines are for starting `jiffies' at a very
> > high number so we spot jiffie-wrap bugs early on.
>
>   The nanosleep() bug narrowed down to 2.5.63-bk2. That's version, the "initial
> jiffies" patch went in. And yes, it's on i686 machine.

You can easily check whether it's connected with this change by setting
INITIAL_JIFFIES to zero. This should exactly recover the previous
situation.
I.e., something like the following (untested, hand-crafted) patch:

--- linux-2.5.64/include/linux/time.h
+++ linux-2.5.64/include/linux/time.h
@@ -28,7 +28,7 @@
  * Have the 32 bit jiffies value wrap 5 minutes after boot
  * so jiffies wrap bugs show up earlier.
  */
- #define INITIAL_JIFFIES ((unsigned int) (-300*HZ))
+ #define INITIAL_JIFFIES 0

 /*
  * Change timeval to jiffies, trying to avoid the


Tim

[BUG & WORKAROUND] nanosleep() granularity bumps up in 2.5.64

[Tim Schmielau]

On Mon, 17 Mar 2003, Tim Schmielau wrote:

> On Mon, 17 Mar 2003, Vitezslav Samel wrote:
>
> >   The nanosleep() bug narrowed down to 2.5.63-bk2. That's version, the "initial
> > jiffies" patch went in. And yes, it's on i686 machine.
>
> You can easily check whether it's connected with this change by setting
> INITIAL_JIFFIES to zero. This should exactly recover the previous
> situation.

OK. I've done the test myself and I plead guilty. As a temporary
workaround you can apply the following patch:


--- linux-2.5.64/include/linux/time.h.orig	Wed Mar  5 04:29:24 2003
+++ linux-2.5.64/include/linux/time.h	Mon Mar 17 20:31:06 2003
@@ -31,7 +31,7 @@
  * Have the 32 bit jiffies value wrap 5 minutes after boot
  * so jiffies wrap bugs show up earlier.
  */
-#define INITIAL_JIFFIES ((unsigned int) (-300*HZ))
+#define INITIAL_JIFFIES 0

 /*
  * Change timeval to jiffies, trying to avoid the


Still, after half an hour of glancing at the code I can't see my mistake.
I've re-checked that the problem does not occur with the original "initial
jiffies" patch for 2.4. So I must have missed a (subtle?) difference
between 2.4 and 2.5 when I did the forward-port.

Sorry,
Tim

[PATCH] fix nanosleep() granularity bumps

[Tim Schmielau]

On Mon, 17 Mar 2003, Tim Schmielau wrote:

> I've re-checked that the problem does not occur with the original "initial
> jiffies" patch for 2.4.

Stupid me - 2.4 with the patch has the same problem, it just takes 10x as
long to show up, a range that was not covered by the testcase.


The actual problem is that I didn't fully understand the, well,
'elaborated' way of counting jiffies in the timer cascade:

When starting out with timer_jiffies=0, the timer cascade is
(unneccessarily) triggered on the first timer interrupt, incrementing all
the higher indices.
When starting with any other initial jiffies value, we miss that and end
up with all higher indices being off by one.

Fix is as follows:

--- linux-2.5.65/kernel/timer.c	Wed Mar  5 04:29:33 2003
+++ linux-2.5.65-jfix/kernel/timer.c	Tue Mar 18 09:40:13 2003
@@ -1183,10 +1183,14 @@

 	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->tv2.index = ((INITIAL_JIFFIES >> TVR_BITS)
+	                   + (INITIAL_JIFFIES!=0)) & TVN_MASK;
+	base->tv3.index = ((INITIAL_JIFFIES >> (TVR_BITS+TVN_BITS))
+	                   + (INITIAL_JIFFIES!=0)) & TVN_MASK;
+	base->tv4.index = ((INITIAL_JIFFIES >> (TVR_BITS+2*TVN_BITS))
+	                   + (INITIAL_JIFFIES!=0)) & TVN_MASK;
+	base->tv5.index = ((INITIAL_JIFFIES >> (TVR_BITS+3*TVN_BITS))
+	                   + (INITIAL_JIFFIES!=0)) & TVN_MASK;
 }

 static int __devinit timer_cpu_notify(struct notifier_block *self,


Sorry for all the trouble,
Tim

Re: [PATCH] fix nanosleep() granularity bumps

[Finn Arne Gangstad]

On Tue, Mar 18, 2003 at 10:05:56AM +0100, Tim Schmielau wrote:
> On Mon, 17 Mar 2003, Tim Schmielau wrote:
> 
> > I've re-checked that the problem does not occur with the original "initial
> > jiffies" patch for 2.4.
> 
> Stupid me - 2.4 with the patch has the same problem, it just takes 10x as
> long to show up, a range that was not covered by the testcase.
> 
> 
> The actual problem is that I didn't fully understand the, well,
> 'elaborated' way of counting jiffies in the timer cascade:
> 
> When starting out with timer_jiffies=0, the timer cascade is
> (unneccessarily) triggered on the first timer interrupt, incrementing all
> the higher indices.
> When starting with any other initial jiffies value, we miss that and end
> up with all higher indices being off by one.

Suggest the attached patch as a fix instead - easier to understand I
think and works for every possible start value. This is what I made for
Andrea Arcangeli many years ago...

diff -ur linux-2.5.65/kernel/timer.c linux-2.5.65-new/kernel/timer.c
--- linux-2.5.65/kernel/timer.c	2003-03-17 22:44:41.000000000 +0100
+++ linux-2.5.65-new/kernel/timer.c	2003-03-24 12:57:31.000000000 +0100
@@ -1182,11 +1182,14 @@
 		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->tv1.index = (1 + (INITIAL_JIFFIES - 1)) & TVR_MASK;
+	base->tv2.index = (1 + ((INITIAL_JIFFIES - 1) >> TVR_BITS)) & TVN_MASK;
+	base->tv3.index = (1 + ((INITIAL_JIFFIES - 1)
+				>> (TVR_BITS + TVN_BITS))) & TVN_MASK;
+	base->tv4.index = (1 + ((INITIAL_JIFFIES - 1)
+				>> (TVR_BITS + 2 * TVN_BITS))) & TVN_MASK;
+	base->tv5.index = (1 + ((INITIAL_JIFFIES - 1)
+				>> (TVR_BITS + 3 * TVN_BITS))) & TVN_MASK;
 }
 	
 static int __devinit timer_cpu_notify(struct notifier_block *self, 


- Finn Arne

Re: [PATCH] fix nanosleep() granularity bumps

[Tim Schmielau]

> On Tue, Mar 18, 2003 at 10:05:56AM +0100, Tim Schmielau wrote:
[...]
> Suggest the attached patch as a fix instead - easier to understand I
> think and works for every possible start value. This is what I made for
> Andrea Arcangeli many years ago...
>
> diff -ur linux-2.5.65/kernel/timer.c linux-2.5.65-new/kernel/timer.c
> --- linux-2.5.65/kernel/timer.c	2003-03-17 22:44:41.000000000 +0100
> +++ linux-2.5.65-new/kernel/timer.c	2003-03-24 12:57:31.000000000 +0100
> @@ -1182,11 +1182,14 @@
>  		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->tv1.index = (1 + (INITIAL_JIFFIES - 1)) & TVR_MASK;
> +	base->tv2.index = (1 + ((INITIAL_JIFFIES - 1) >> TVR_BITS)) & TVN_MASK;
> +	base->tv3.index = (1 + ((INITIAL_JIFFIES - 1)
> +				>> (TVR_BITS + TVN_BITS))) & TVN_MASK;
> +	base->tv4.index = (1 + ((INITIAL_JIFFIES - 1)
> +				>> (TVR_BITS + 2 * TVN_BITS))) & TVN_MASK;
> +	base->tv5.index = (1 + ((INITIAL_JIFFIES - 1)
> +				>> (TVR_BITS + 3 * TVN_BITS))) & TVN_MASK;
>  }
>
>  static int __devinit timer_cpu_notify(struct notifier_block *self,

Too late - the whole tv[1-5].index duplication is gone already after a
cleanup done by George Anzinger.

Tim

Re: [Linux-ia64] Re: [BUG] nanosleep() granularity bumps up in 2.5.64 (was: [PATCH] settimeofday() not synchronised with gettimeofday())

[David Mosberger]

>>>>> On Fri, 14 Mar 2003 15:34:36 +0100, Eric Piel <Eric.Piel@Bull.Net> said:

  Eric> Sure, I aim at porting the high resolution timers but any
  Eric> annoying bug related to the time can be interesting to remove.

Great!  It would be great to have someone who can focus on that.

  Eric> Any idea/sugestion/patch is welcomed. Whatever, I will try to
  Eric> fix this as soon as I'm back from my week end :-)

Does the x86 show the same behavior?  That would be a useful start to
narrow down the problem.

	--david

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] 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