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
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
>>>>> On Fri, 14 Mar 2003 15:34:36 +0100, Eric Piel <[email protected]> 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
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
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
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
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
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,
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,
george anzinger <[email protected]> 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?
Andrew Morton wrote:
> george anzinger <[email protected]> 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 [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
>
--
George Anzinger [email protected]
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml
george anzinger <[email protected]> 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.
On Tue, 18 Mar 2003, Andrew Morton wrote:
> george anzinger <[email protected]> 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
Tim Schmielau wrote:
> On Tue, 18 Mar 2003, Andrew Morton wrote:
>
>
>>george anzinger <[email protected]> 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 [email protected]
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml
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,
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 <[email protected]> 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.
Andrew Morton wrote:
> george anzinger <[email protected]> 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 [email protected]
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml
george anzinger <[email protected]> wrote:
>
> Andrew Morton wrote:
> > george anzinger <[email protected]> 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.
Andrew Morton wrote:
> george anzinger <[email protected]> wrote:
>
>>Andrew Morton wrote:
>>
>>>george anzinger <[email protected]> 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 [email protected]
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml
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,
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
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
> 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