Replace timer_bh with tasklet

This patch replaces the timer_bh with a tasklet. It also introduces
a way to flag a tasklet as a must run (i.e. do NOT kick up to ksoftirqd).

It make NO sense to pass timer work to a task.

Comments...

diff -urN linux-2.5.22/include/linux/interrupt.h
linux/include/linux/interrupt.h
--- linux-2.5.22/include/linux/interrupt.h Sun Jun 16
19:31:22 2002
+++ linux/include/linux/interrupt.h Mon Jun 17 15:58:59 2002
@@ -57,12 +57,19 @@

enum
{
- HI_SOFTIRQ=0,
+ RUN_TIMER_LIST=0,
+ HI_SOFTIRQ,
NET_TX_SOFTIRQ,
NET_RX_SOFTIRQ,
TASKLET_SOFTIRQ
};

+/*
+ * The ALWAYS_SOFTIRQ tasks will always be called repeatedly (until
+ * the pending bit stays cleared) each time do_softirq is called.
+ */
+#define ALWAYS_SOFTIRQ (1 << RUN_TIMER_LIST)
+
/* softirq mask and active fields moved to irq_cpustat_t in
* asm/hardirq.h to get better cache usage. KAO */
@@ -74,6 +81,7 @@
};

asmlinkage void do_softirq(void);
+extern void timer_softirq(struct softirq_action* a);
extern void open_softirq(int nr, void (*action)(struct
softirq_action*), void *data);
extern void softirq_init(void);
#define __cpu_raise_softirq(cpu, nr) do {
softirq_pending(cpu) |= 1UL << (nr); } while (0)

diff -urN linux-2.5.22/kernel/sched.c linux/kernel/sched.c
@@ -1633,7 +1633,6 @@
 }
 
 extern void init_timervecs(void);
-extern void timer_bh(void);
 extern void tqueue_bh(void);
 extern void immediate_bh(void);
 

@@ -1671,7 +1670,6 @@
 	wake_up_process(current);
 
 	init_timervecs();
-	init_bh(TIMER_BH, timer_bh);
 	init_bh(TQUEUE_BH, tqueue_bh);
 	init_bh(IMMEDIATE_BH, immediate_bh);
 

diff -urN linux-2.5.22/kernel/softirq.c
linux/kernel/softirq.c

@@ -96,7 +96,7 @@
 		local_irq_disable();
 
 		pending = softirq_pending(cpu);
-		if (pending & mask) {
+		if (pending & (mask | ALWAYS_SOFTIRQ)) {
 			mask &= ~pending;
 			goto restart;
 		}

@@ -332,6 +332,7 @@
 
 	open_softirq(TASKLET_SOFTIRQ, tasklet_action, NULL);
 	open_softirq(HI_SOFTIRQ, tasklet_hi_action, NULL);
+	open_softirq(RUN_TIMER_LIST,timer_softirq, NULL);
 }
 
 void __run_task_queue(task_queue *list)

diff -urN linux-2.5.22/kernel/timer.c linux/kernel/timer.c
@@ -14,6 +14,7 @@
  *                              Copyright (C) 1998  Andrea

Arcangeli
* 1999-03-10 Improved NTP compatibility by Ulrich Windl
* 2002-05-31 Move sys_sysinfo here and make its locking
sane, Robert Love
+ * 2002-06-17 Run timers off a tasklet and remove TIMER_BH
*/

#include <linux/config.h>
@@ -37,6 +38,12 @@
/* The current time */
struct timeval xtime __attribute__ ((aligned (16)));

+/*
+ * This atomic prevents re-entry of the run_timer_list and has the side
+ * effect of shifting conflict runs to the "owning" cpu.
+ */
+static atomic_t timer_tasklet_lock = ATOMIC_INIT(-1); +
/* Don't completely fail for HZ > 500. */
int tickadj = 500/HZ ? : 1; /* microsecs */

@@ -645,7 +652,7 @@
unsigned long ticks;

/*
- * update_times() is run from the raw timer_bh handler so
we
+ * update_times() is run from the raw timer_tasklet so we
* just know that the irqs are locally enabled and so we
don't
* need to save/restore the flags of the local CPU here.
-arca
*/
@@ -661,10 +668,24 @@
write_unlock_irq(&xtime_lock);
}

-void timer_bh(void)
+
+/*
+ * timer_tasklet_lock starts at -1. 0 then means it is cool to
+ * continue. If another cpu bumps it while the first is still in
+ * run_timer_list, it will be detected on exit and we will run it
+ * again. But multiple entries are not needed, just once for all the
+ * "hits" while we are in run_timer_list.
+ */
+void timer_softirq(struct softirq_action* a)
{
- update_times();
- run_timer_list();
+ if (!atomic_inc_and_test(&timer_tasklet_lock))
+ return;
+
+ do {
+ atomic_set(&timer_tasklet_lock, 0);
+ update_times();
+ run_timer_list();
+ } while (!atomic_add_negative(-1,
&timer_tasklet_lock));
}

void do_timer(struct pt_regs *regs)
@@ -675,7 +696,7 @@

update_process_times(user_mode(regs));
#endif
- mark_bh(TIMER_BH);
+ raise_softirq( RUN_TIMER_LIST );
if (TQ_ACTIVE(tq_timer))
mark_bh(TQUEUE_BH);
}

George Anzinger   [email protected]
High-res-timers: 
http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch:
http://www.kernel.org/pub/linux/kernel/people/rml

I hate adding infrastructure that isn't needed.

Is there any reason why it would be _wrong_ to pass the timer work to a task? In particular, is it really any more wrong than anything else?

I don't see that there is any difference between a timer bh and any other BH.

Linus

PS. Your email is also seriously whitespace-damaged, so the patch wouldn't have worked anyway.

I reasoned that the timers, unlike most other I/O, directly drive the system. For example, the time slice is counted down by the timer BH. By pushing the timer out to ksoftirqd, running at nice 19, you open the door to a compute bound task running over its time slice (admittedly this should be caught on the next interrupt). Also, a great deal of the system depends on timers to expire reasonably close to the correct time and not to be delayed by scheduling decisions (oops, recursion).

As to infrastructure, why is ksoftirqd needed at all? IMNSHO it introduces system overhead just when the system is most loaded. The work must be done sometime soon in any case. Interrupts are on so all we are gaining is a bit of responsiveness in the current task. But who is to say that the more important task isn't being held off by the delay introduced by the ksoftirqd "feature".

I do think that it would be a good thing to move some BH processing to the task level, but I think it must be done selectively AND that there should be a task per BH. That task should also be adjusted in priority, to the users requirements. This would allow, for example, the network BH code to run at a mid level priority such that some real time tasks could preempt it, while others could be preempted by it.

But today we are just trying to say that of all the BH handlers, the timer BH, since it drives the scheduler, is more important than other BHs.

Sigh, I know.... Lets agree on what is to be done and I will cut a new patch...

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

I have had some problems with timers delayed up to 0.06s in 2.4 kernels, could that be this problem?

Richard

It could be. Depends on what was going on at the time. In most cases, however, the next interrupt should cause a call to softirq and thus run the timer list. This would seem to indicate at 20ms delay at most (first call busys softirq thru a 10ms tick followed by recovery at the next tick).

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

I have generated high load to test how accurately my genrtc driver will work - it turned out that timers added with add_timer occassionally get delayed by several jiffies. Results were much worse on IO bound load, especially IDE drives, CPU intensive userspace apps didn't appear to matter.

Using schedule_task() to poll the event seems to work without any problems.

this was also my impression after looking at the lowlevel interrupt handling so I am really puzzled.

Richard

From: george anzinger <[email protected]>
Date: Mon, 17 Jun 2002 20:45:14 -0700

This patch replaces the timer_bh with a tasklet.

This is going to break a lot of stuff.

For one thing, the net/core/dev.c:deliver_to_old_ones() code to disable timers no longer will work.

If you had deleted TIMER_BH you would have noticed this breakage.

Also, aren't there some dependencies on HI_SOFTIRQ being first in that enumeration? This needs to be answered before going further with this patch.

Could you elaborate on the reason for the above bit of code? Is it to cover some thing from the past or is this an on going issue? I.e. will this disappear soon? Is its usage dependent on a particular driver?

Mostly I am interested in this because it may be at the bottom of a VERY elusive bug (4 systems, heavy network load, crash at 22 hours into the test). Please help.

-g

George Anzinger   [email protected]
High-res-timers: 
http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch:
http://www.kernel.org/pub/linux/kernel/people/rml

The comment says:
/* Deliver skb to an old protocol, which is not threaded well
or which do not understand shared skbs.
*/

so it's nothing to do with drivers, but old protocols (like SNA, I guess).

Why did you decide to use a softirq for timers rather than a tasklet?

Revolutions do not require corporate support.

HI_SOFTIRQ, if I understand it right, runs the old BH code. Since most (all) of this is going away, it would appear just the place to put the timer stuff. TIMER_BH was first before and is still first.

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Hello!

But this is impossible, timers must not race with another BHs, all the code using BHs depends on this. That's why they are BHs.

Also, looping for timers seems to be pure pathalogy. It can be raised only if you looped in softirq for a jiffie, in this case waking ksoftirqd is not unusual.

I feel your goal is high res timers, right? You can do them separately to avoid conflicts with classic timers.

Alexey

If indeed they do "race" the old code had the timer_bh being first. So does this patch.

This is one of the most hard to control paths in the system as ALL it does is execute functions that are unknown as to size, duration, etc. One would hope that they never run for long, but...

Not really. One REALLY expects timers to expire in timed order :) Using a separate procedure to deliver a timer just because it is of a different resolution opens one up to a world of pathology.

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Hello!

I do not understand what you mean here.

I feel you misunderstand my comment. I said the patch is one pure big bug, because tasklets are not serialized wrt BHs. Timer MUST. If you are going to get rid of this must, start from editing all the code which makes this assumption.

Pardon, your code has an effect only after this "but..." happens and this effect is insane.

Are you going to mix use of hires and lores timers for one task?

Alexey

At this point I am only aware of one place in the kernel where timers and other BH code interact, that being deliver_to_old_ones() in net/core/dev.c. Even there, it appears that the interaction is not with another BH but with code that at one time was BH code. As I understand it, BH and all of its support stuff is being removed from the kernel. That is why I was asked to submit this patch. So far, this is the only area that has come up as a locking or serialization problem.

As to this bit of code, it appears that changing it to do much the same as it did to the timer_bh to the new timer softirq should resolve the issue.

If you have additional input on this or other problems that need to be addressed, I welcome it.

Correct me if I am wrong, but it looks like the network code has already left the BH playing field.

~snip

Of course. Why use high-res when you don't need it? There is additional overhead for high-res. To require all timers to be high-res when only one is needed is a waste.

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

From: george anzinger <[email protected]>
Date: Wed, 19 Jun 2002 17:39:59 -0700

At this point I am only aware of one place in the kernel where timers and other BH code interact, that being deliver_to_old_ones() in net/core/dev.c.

Are you absolutely sure? What about serial drivers and the TTY layer? Have you audited all of that code too? What about SCSI_BH? What about IMMEDIATE_BH, TQUEUE_BH? Do they interact non-trivially with timers too?

Alexey is right, there needs to be a real audit here before this patch may be considered.

SCSH_BH is gone in 2.5.23. Matthew Wilcox has a patch to remove IMMEDIATE_BH.

TIMER_BH is the only BH left as far as I know.

So the needed synchronization, if any, is against the other softirqs.

Robert Love

From: Robert Love <[email protected]>
Date: 19 Jun 2002 18:53:25 -0700

SCSH_BH is gone in 2.5.23. Matthew Wilcox has a patch to remove IMMEDIATE_BH.

TIMER_BH is the only BH left as far as I know.

What about all of the serial driver BHs? You keep avoiding this issue.

Also, when people remove *_BH they should remove the define in include/linux/interrupt.h Why people leave this there is beyond me, it only causes confusion when people try to figure out what the current state of affairs is.

Because I was told rmk's serial rewrite ditched old-style BHs...

I agree.

Robert Love

From: Robert Love <[email protected]>
Date: 19 Jun 2002 19:05:11 -0700

Because I was told rmk's serial rewrite ditched old-style BHs...

That isn't in the tree now. We can only make analsis of the patch based upon what is in 2.5.x right now, you can't base it on what might be added in the future.

Could there possibly be any interaction between SERIAL_BH and TIMER_BH?

I guess my stance is if each BH-removal patch figures out its syncronization issues, each should be fine regardless of what the other BHs do.

The timer_bh runs often but touches a comprehensible amount of data.

Robert Love

From: Robert Love <[email protected]>
Date: 19 Jun 2002 19:15:34 -0700

Could there possibly be any interaction between SERIAL_BH and TIMER_BH?

Or the drivers... these are the questions that must be answered before we can consider the patch.

Also the TIMER_BH patch has to attend to the deliver_to_old_ones issue before it may be considered further.

Is the only network issue? Is it possible that the network code uses bh_locking to protect against timers? Moveing timers to softirqs would invalidate this sort of protection. Is this an issue?

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

From: george anzinger <[email protected]>
Date: Thu, 20 Jun 2002 16:54:16 -0700

Is the only network issue? Is it possible that the network code uses bh_locking to protect against timers? Moveing timers to softirqs would invalidate this sort of protection. Is this an issue?

It is the whole issue. We have to stop all timers while we run the non-SMP safe protocol code.

Thanks. I think this can be done much the same way it is now. I will modify the patch accordingly.

At the same time, I must say that stoping the timers is, IMNSHO, NOT a good thing for the kernel. It can cause unexpected timer latencies which can impact most any task on the system. (But you already knew this :) I understand that it is not seldom used, but still...

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

From: george anzinger <[email protected]>
Date: Fri, 21 Jun 2002 07:04:28 -0700

Thanks. I think this can be done much the same way it is now. I will modify the patch accordingly.

Thanks, now what about every piece of code doing cli() and expects timers not to run because of that? Are you going to audit all of that too?

I think you still have no idea at all how much breakage you're going to cause nor how much work is necessary to fix that.

You appear to have missed willy's posting a couple of days ago fixing up the serial driver BHs.

Russell King ([email protected])                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

From: Russell King <[email protected]>
Date: Thu, 20 Jun 2002 09:11:16 +0100

You appear to have missed willy's posting a couple of days ago fixing up the serial driver BHs.

Did it get applied to 2.5.x?

I have no idea - I've not looked at what Linus has put into the kernel after 2.5.21 yet. Too busy I'm afraid. However, the patch has been aired on lkml and didn't receive any negative feedback.

Russell King ([email protected])                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

Missed this bit 8/

iirc willy also covered this in one of his postings to lkml, might even have been the serial bh one.

Russell King ([email protected])                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

Hello!

:-) If so, then timer_bh can be removed too. This means that all the serialization is already broken and things cannot become worse. :-)

Alexey