![[LWN Logo]](/images/lwn.banner.gif)
Date: Tue, 30 May 2000 21:07:52 +1000
From: Andrew Morton <andrewm@uow.edu.au>
To: Alan Cox <alan@lxorguk.ukuu.org.uk>
Subject: [patch] timers: plan B
This is a multi-part message in MIME format.
--------------A4B9E3059BDDC0DD800C98A7
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Last week the proposal was to fix the obvious deadlocks, make del_timer
synchronous and to rely on the deadlock detection to find things.
This would find the most bugs in the shortest time but would
disrupt a lot of developers who may not want to review
their timer code immediately.
But there are no quick fixes and it is preferable to fix the important
stuff a bit at a time. Keep the patches smaller.
So here's plan B:
- Fix del_timer_sync() and give it a deadlock detector
- Rename del_timer to del_timer_async
- #define del_timer del_timer_async.
That is what the attached patch does. It is, effectively, a no-op.
- Over the next couple of weeks I work with the IDE, SCSI, net,
drivers/net and drivers/video maintainers to review their timer
code and get it migrated across to use del_timer_sync and
del_timer_async.
- We can then #define del_timer del_timer_sync and rely on the
deadlock detector to accelerate the auditing process. If it causes
problems then people can just revert that #define.
The long-term plan is to remove del_timer ALTOGETHER. All code should
use either del_timer_async or del_timer_sync. In the interim del_timer
will continue to work, but the presence of del_timer should be a flag
which says "unaudited, possibly buggy".
Migrating code to use del_timer_sync/async will break
back-compatibility, so the various k-compat headers
will need to gain a couple of new #defines:
#define del_timer_async del_timer
#define del_timer_sync del_timer
How does that all sound?
The attached patch is against test1-ac5.
- del_timer becomes del_timer_async.
- del_timer_sync is made unracy and gets a deadlock detector and
a very temporary race-reporter.
- For UP, we keep del_timer. del_timer_sync and del_timer_async
are #defined onto it.
- Removes:
timer_list.running
timer_set_running()
timer_synchronize()
timer_is_running()
The latter breaks some debug code in include/net/tcp.h,
but it is already ifdefed out. Easy to fix.
When reviewing the new del_timer_sync() please bear in mind that
there is a fair bit of diagnostic stuff there. It's all on a very
rarely travelled path and most of this will go away, but I expect the
deadlock detector will be there for a long time.
--
-akpm-
(But what to do about 2.2?)
--------------A4B9E3059BDDC0DD800C98A7
Content-Type: text/plain; charset=us-ascii;
name="timer-core-8.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="timer-core-8.patch"
--- linux-2.4.0test1-ac5/kernel/timer.c Mon May 15 21:25:15 2000
+++ linux-akpm/kernel/timer.c Tue May 30 20:47:28 2000
@@ -13,6 +13,8 @@
* serialize accesses to xtime/lost_ticks).
* Copyright (C) 1998 Andrea Arcangeli
* 1999-03-10 Improved NTP compatibility by Ulrich Windl
+ * 2000-05-27 Make del_timer synchronous, add del_timer_async - Andrew Morton.
+ * http://kernelnotes.org/lnxlists/linux-kernel/lk_0005_04/msg00672.html
*/
#include <linux/config.h>
@@ -72,6 +74,23 @@
unsigned long prof_len;
unsigned long prof_shift;
+#ifdef CONFIG_SMP
+/*
+ * A non-zero entry here indicates a currently-running timer on
+ * the CPU identified by running_timer_cpu.
+ */
+static struct timer_list *running_timer;
+static int running_timer_cpu;
+
+/* FIXME: delete this stuff */
+#ifdef CONFIG_X86
+extern void show_stack(unsigned long* esp); /* Why doesn't this have a prototype? */
+#define x86_show_stack() show_stack(0)
+#else
+#define x86_show_stack() do { } while (0)
+#endif
+#endif /* CONFIG_SMP */
+
/*
* Event timer code
*/
@@ -201,6 +220,7 @@
return ret;
}
+#ifndef CONFIG_SMP
int del_timer(struct timer_list * timer)
{
int ret;
@@ -212,39 +232,83 @@
spin_unlock_irqrestore(&timerlist_lock, flags);
return ret;
}
+#endif
#ifdef CONFIG_SMP
-/*
- * SMP specific function to delete periodic timer.
- * Caller must disable by some means restarting the timer
- * for new. Upon exit the timer is not queued and handler is not running
- * on any CPU. It returns number of times, which timer was deleted
- * (for reference counting).
- */
+
+int del_timer_async(struct timer_list * timer)
+{
+ int ret;
+ unsigned long flags;
+
+ spin_lock_irqsave(&timerlist_lock, flags);
+ ret = detach_timer(timer);
+ timer->list.next = timer->list.prev = NULL;
+ spin_unlock_irqrestore(&timerlist_lock, flags);
+ return ret;
+}
int del_timer_sync(struct timer_list * timer)
{
- int ret = 0;
+ int ret;
+ unsigned long flags;
- for (;;) {
- unsigned long flags;
- int running;
+ spin_lock_irqsave(&timerlist_lock, flags);
+ ret = detach_timer(timer);
+ timer->list.next = timer->list.prev = 0;
- spin_lock_irqsave(&timerlist_lock, flags);
- ret += detach_timer(timer);
- timer->list.next = timer->list.prev = 0;
- running = timer->running;
+ if (running_timer == timer) { /* This timer's handler is presently running */
+ int j;
+ struct timer_list * volatile *vtl;
+
+ if (running_timer_cpu == smp_processor_id())
+ goto out; /* Handler is deleting timer. Usually pointless. */
+
+ /* FIXME: temp */
+ printk( "del_timer_sync(%p) during handler execution! Called from %p\n"
+ "See http://www.uow.edu.au/~andrewm/linux/del_timer.html\n",
+ timer, __builtin_return_address(0));
+ x86_show_stack();
+re_del_timer:
+ /* Unlock the timer list and spin until handler completion. */
spin_unlock_irqrestore(&timerlist_lock, flags);
+ vtl = (struct timer_list * volatile *)&(running_timer);
+ for (j = 50 * 1000 * 1000; j != 0; --j) {
+ if (*vtl != timer)
+ break;
+ }
+ spin_lock_irqsave(&timerlist_lock, flags);
- if (!running)
- return ret;
- timer_synchronize(timer);
+ if (j == 0) {
+ printk( "del_timer_sync(%p): deadlock! Called from %p\n",
+ timer, __builtin_return_address(0));
+ printk("See http://www.uow.edu.au/~andrewm/linux/deadlock.html\n");
+ x86_show_stack();
+ } else {
+ if (running_timer == timer) {
+ /* There's a tiny chance that the same timer handler has started to run again */
+ printk("del_timer_sync(%p): the timer started running again!\n", timer);
+ x86_show_stack();
+ goto re_del_timer;
+ }
+ /*
+ * OK, we have the lock and the timer handler is definitely not running. But the
+ * handler may have re-added the timer, and it may have deleted the timer.
+ * But we assume that the handler has NOT kfree'ed the timer. We can assume this
+ * because calling del_timer() on a timer which is freed in the handler is a BUG.
+ */
+ if (timer_pending(timer)) {
+ printk("del_timer_sync(): timer was re-added\n");
+ ret += detach_timer(timer);
+ timer->list.next = timer->list.prev = 0;
+ }
+ }
}
-
+out:
+ spin_unlock_irqrestore(&timerlist_lock, flags);
return ret;
}
-#endif
-
+#endif /* CONFIG_SMP */
static inline void cascade_timers(struct timer_vec *tv)
{
@@ -295,10 +359,20 @@
detach_timer(timer);
timer->list.next = timer->list.prev = NULL;
- timer_set_running(timer);
+#ifdef CONFIG_SMP
+ if (running_timer != 0)
+ BUG();
+ running_timer = timer;
+ running_timer_cpu = smp_processor_id();
+#endif
spin_unlock_irq(&timerlist_lock);
fn(data);
spin_lock_irq(&timerlist_lock);
+#ifdef CONFIG_SMP
+ if (running_timer != timer)
+ BUG();
+ running_timer = 0;
+#endif
goto repeat;
}
++timer_jiffies;
--- linux-2.4.0test1-ac5/include/linux/timer.h Tue May 30 18:45:52 2000
+++ linux-akpm/include/linux/timer.h Tue May 30 20:24:01 2000
@@ -54,11 +54,36 @@
unsigned long expires;
unsigned long data;
void (*function)(unsigned long);
- volatile int running;
};
extern void add_timer(struct timer_list * timer);
+#define timer_exit(t) (void)(t)
+
+#ifdef CONFIG_SMP
+extern int del_timer_async(struct timer_list * timer);
+extern int del_timer_sync(struct timer_list * timer);
+#ifndef del_timer
+#define del_timer del_timer_async
+#endif
+#else
extern int del_timer(struct timer_list * timer);
+#ifndef del_timer_sync
+#define del_timer_sync del_timer
+#endif
+#ifndef del_timer_async
+#define del_timer_async del_timer
+#endif
+#endif
+
+#define INIT_TIMER_FND(fn, d) { \
+ list: LIST_HEAD_INIT_NULL, \
+ expires: 0, \
+ data: d, \
+ function: fn, \
+}
+
+#define INIT_TIMER_FN(fn) INIT_TIMER_FND(fn, 0)
+#define INIT_TIMER INIT_TIMER_FN(0)
/*
* mod_timer is a more efficient way to update the expire field of an
@@ -72,29 +97,12 @@
static inline void init_timer(struct timer_list * timer)
{
timer->list.next = timer->list.prev = NULL;
-#ifdef CONFIG_SMP
- timer->running = 0;
-#endif
}
static inline int timer_pending (const struct timer_list * timer)
{
return timer->list.next != NULL;
}
-
-#ifdef CONFIG_SMP
-#define timer_exit(t) do { (t)->running = 0; mb(); } while (0)
-#define timer_set_running(t) do { (t)->running = 1; mb(); } while (0)
-#define timer_is_running(t) ((t)->running != 0)
-#define timer_synchronize(t) while (timer_is_running(t)) barrier()
-extern int del_timer_sync(struct timer_list * timer);
-#else
-#define timer_exit(t) (void)(t)
-#define timer_set_running(t) (void)(t)
-#define timer_is_running(t) (0)
-#define timer_synchronize(t) do { (void)(t); barrier(); } while(0)
-#define del_timer_sync(t) del_timer(t)
-#endif
/*
* These inlines deal with timer wrapping correctly. You are
--- linux-2.4.0test1-ac5/include/linux/list.h Wed Apr 26 22:52:03 2000
+++ linux-akpm/include/linux/list.h Sat May 27 22:26:43 2000
@@ -19,6 +19,8 @@
#define LIST_HEAD_INIT(name) { &(name), &(name) }
+#define LIST_HEAD_INIT_NULL { 0, 0 }
+
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
--- linux-2.4.0test1-ac5/kernel/ksyms.c Tue May 30 18:45:52 2000
+++ linux-akpm/kernel/ksyms.c Tue May 30 18:51:13 2000
@@ -341,9 +341,16 @@
EXPORT_SYMBOL(proc_doulongvec_ms_jiffies_minmax);
EXPORT_SYMBOL(proc_doulongvec_minmax);
-/* interrupt handling */
+/* kernel timers */
EXPORT_SYMBOL(add_timer);
+#ifdef CONFIG_SMP
+EXPORT_SYMBOL(del_timer_async);
+EXPORT_SYMBOL(del_timer_sync);
+#else
EXPORT_SYMBOL(del_timer);
+#endif
+
+/* interrupt handling */
EXPORT_SYMBOL(request_irq);
EXPORT_SYMBOL(free_irq);
@@ -356,9 +363,6 @@
EXPORT_SYMBOL(autoirq_report);
#endif
-#ifdef CONFIG_SMP
-EXPORT_SYMBOL(del_timer_sync);
-#endif
EXPORT_SYMBOL(mod_timer);
EXPORT_SYMBOL(tq_timer);
EXPORT_SYMBOL(tq_immediate);
--------------A4B9E3059BDDC0DD800C98A7--
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/