Re: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

Re: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

[Manfred Spraul]

Ingo wrote:

>fixing this second race is hard - it involves a heavy race-check operation
>that has to lock all bases, and has to re-check the base->running_timer
>value, and timer_pending condition atomically.
>  
>
What about moving the "timer running" information into the timer_list, 
instead of keeping it in the base?
For example base=0 means neither running nor pending. base=1 means 
running, but not pending, and pointers mean pending on the given base.

This would allow an atomic test without the brute force locking.

--   
     Manfred

Re: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

[Ingo Molnar]

On Sat, 11 Oct 2003, Manfred Spraul wrote:

> What about moving the "timer running" information into the timer_list,
> instead of keeping it in the base? For example base=0 means neither
> running nor pending. base=1 means running, but not pending, and pointers
> mean pending on the given base.
> 
> This would allow an atomic test without the brute force locking.

it's not so simple. Firstly, it would burden some of the other timer
codepaths with extra logic. (mod/add/del_timer) Secondly, the use of
timer->base is closely controlled, and it's not that simple to clear the
value of '1' from timer->base after the timer has run. [this could race
with any other CPU.]

it would be much cleaner to add another timer->running field, especially
since this would be the 8th word-sized field in struct timer_list, making
it a nice round structure size.

btw., there's a third type of timer race we have. If a timer function is
delayed by more than 1 timer tick [which could happen under eg. UML], then
it's possible for the timer function to run on another CPU in parallel to
the already executing timer function.

	Ingo

Re: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

[Ingo Molnar]

On Sat, 11 Oct 2003, Ingo Molnar wrote:

> since this would be the 8th word-sized field in struct timer_list,
> making it a nice round structure size.

it's the 9th field in fact, due to timer->magic.

	Ingo

Re: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

[Manfred Spraul]

Ingo Molnar wrote:

>On Sat, 11 Oct 2003, Ingo Molnar wrote:
>
>  
>
>>since this would be the 8th word-sized field in struct timer_list,
>>making it a nice round structure size.
>>    
>>
>
>it's the 9th field in fact, due to timer->magic.
>  
>
I found one problem: the same timer can run on multiple cpus at the same time.

timer on cpu 0. running on cpu 0.
add_timer on cpu 1. expires immediately. running on cpu 1.

Your mail arrived out of order - thus I don't know yet if the 9th field 
is a counter or a flag - a counter might work, but is quite ugly.

--
    Manfred

Re: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

[Ingo Molnar]

On Sat, 11 Oct 2003, Ingo Molnar wrote:

> it would be much cleaner to add another timer->running field, especially
> since this would be the 8th word-sized field in struct timer_list,
> making it a nice round structure size.
> 
> btw., there's a third type of timer race we have. If a timer function is
> delayed by more than 1 timer tick [which could happen under eg. UML],
> then it's possible for the timer function to run on another CPU in
> parallel to the already executing timer function.

i've implemented the timer->running field, and it's quite straightforward
and solves all 3 types of races. It also simplifies del_timer_sync() quite
visibly, and it's probably a fair del_timer_sync() speedup as well. I
tested the attached patch on SMP and UP x86 as well, works fine for me.

the timer->running field is now also used to guarantee serialization of
timer->fn execution of the same timer [race #3]. This is a quite
reasonable thing to expect, and a fair portion of timer users do expect
this.

	Ingo

--- linux/include/linux/timer.h.orig	
+++ linux/include/linux/timer.h	
@@ -18,6 +18,7 @@ struct timer_list {
 	unsigned long data;
 
 	struct tvec_t_base_s *base;
+	unsigned long running;
 };
 
 #define TIMER_MAGIC	0x4b87ad6e
@@ -29,6 +30,7 @@ struct timer_list {
 		.base = NULL,					\
 		.magic = TIMER_MAGIC,				\
 		.lock = SPIN_LOCK_UNLOCKED,			\
+		.running = 0,					\
 	}
 
 /***
@@ -42,6 +44,7 @@ static inline void init_timer(struct tim
 {
 	timer->base = NULL;
 	timer->magic = TIMER_MAGIC;
+	timer->running = 0;
 	spin_lock_init(&timer->lock);
 }
 
--- linux/kernel/timer.c.orig	
+++ linux/kernel/timer.c	
@@ -57,7 +57,6 @@ typedef struct tvec_root_s {
 struct tvec_t_base_s {
 	spinlock_t lock;
 	unsigned long timer_jiffies;
-	struct timer_list *running_timer;
 	tvec_root_t tv1;
 	tvec_t tv2;
 	tvec_t tv3;
@@ -67,14 +66,6 @@ struct tvec_t_base_s {
 
 typedef struct tvec_t_base_s tvec_base_t;
 
-static inline void set_running_timer(tvec_base_t *base,
-					struct timer_list *timer)
-{
-#ifdef CONFIG_SMP
-	base->running_timer = timer;
-#endif
-}
-
 /* Fake initialization */
 static DEFINE_PER_CPU(tvec_base_t, tvec_bases) = { SPIN_LOCK_UNLOCKED };
 
@@ -315,35 +306,27 @@ EXPORT_SYMBOL(del_timer);
  * the timer it also makes sure the handler has finished executing on other
  * CPUs.
  *
- * Synchronization rules: callers must prevent restarting of the timer,
- * otherwise this function is meaningless. It must not be called from
- * interrupt contexts. Upon exit the timer is not queued and the handler
- * is not running on any CPU.
+ * Synchronization rules: callers must prevent restarting of the timer
+ * (except restarting the timer from the timer function itself), otherwise
+ * this function is meaningless. It must not be called from interrupt
+ * contexts. Upon exit the timer is not queued and the handler is not
+ * running on any CPU.
  *
- * The function returns whether it has deactivated a pending timer or not.
+ * The function returns the number of times it has deactivated a pending
+ * timer.
  */
 int del_timer_sync(struct timer_list *timer)
 {
-	tvec_base_t *base;
-	int i, ret = 0;
+	int ret = 0;
 
 	check_timer(timer);
 
 del_again:
 	ret += del_timer(timer);
 
-	for (i = 0; i < NR_CPUS; i++) {
-		if (!cpu_online(i))
-			continue;
-
-		base = &per_cpu(tvec_bases, i);
-		if (base->running_timer == timer) {
-			while (base->running_timer == timer) {
-				cpu_relax();
-				preempt_check_resched();
-			}
-			break;
-		}
+	while (unlikely(timer->running)) {
+		cpu_relax();
+		preempt_check_resched();
 	}
 	smp_rmb();
 	if (timer_pending(timer))
@@ -417,16 +400,36 @@ repeat:
  			fn = timer->function;
  			data = timer->data;
 
+#ifdef CONFIG_SMP
+			/*
+			 * If the timer is running on another CPU then
+			 * wait for it - without holding the base lock.
+			 * This is a very rare but possible situation.
+			 *
+			 * Re-start the whole processing after that, the
+			 * timer might have been removed while we dropped
+			 * the lock.
+			 */
+			if (unlikely(timer->running)) {
+				spin_unlock_irq(&base->lock);
+				while (timer->running)
+					cpu_relax();
+				spin_lock_irq(&base->lock);
+				goto repeat;
+			}
+			timer->running = 1;
+#endif
 			list_del(&timer->entry);
 			timer->base = NULL;
-			set_running_timer(base, timer);
 			spin_unlock_irq(&base->lock);
 			fn(data);
 			spin_lock_irq(&base->lock);
+#ifdef CONFIG_SMP
+			timer->running = 0;
+#endif
 			goto repeat;
 		}
 	}
-	set_running_timer(base, NULL);
 	spin_unlock_irq(&base->lock);
 }
 

Re: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

[Andrew Morton]

Ingo Molnar <mingo@elte.hu> wrote:
>
> 
> On Sat, 11 Oct 2003, Ingo Molnar wrote:
> 
> > since this would be the 8th word-sized field in struct timer_list,
> > making it a nice round structure size.
> 
> it's the 9th field in fact, due to timer->magic.
> 

We can remove the debug code now.  Or wrap it in a debug config option.

Re: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

[Linus Torvalds]

On Sat, 11 Oct 2003, Ingo Molnar wrote:
> 
> i've implemented the timer->running field, and it's quite straightforward
> and solves all 3 types of races. It also simplifies del_timer_sync() quite
> visibly, and it's probably a fair del_timer_sync() speedup as well. I
> tested the attached patch on SMP and UP x86 as well, works fine for me.

This one is also buggy.

It is _not_ ok to do this:

>  			list_del(&timer->entry);
>  			timer->base = NULL;
> -			set_running_timer(base, timer);
>  			spin_unlock_irq(&base->lock);
>  			fn(data);
>  			spin_lock_irq(&base->lock);
> +#ifdef CONFIG_SMP
> +			timer->running = 0;
> +#endif

since the timer may not even _exist_ any more - the act of running the 
timer may well have free'd the timer structure, and you're now zeroing 
memory that may have been re-allocated for something else.

This is exactly why we load all the timer data into local variables before 
we run the timer function, and we don't touch "timer" afterwards.

In short, you really need to re-visit this whole thing.

		Linus

Re: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

[Ingo Molnar]

On Mon, 13 Oct 2003, Linus Torvalds wrote:

> since the timer may not even _exist_ any more - the act of running the
> timer may well have free'd the timer structure, and you're now zeroing
> memory that may have been re-allocated for something else.

doh, indeed.

i'm happy with the timer->base write ordering fix that addresses the first
race, it fixes the bug that was actually triggered in RL. The other two
races are present too but were present in previous incarnations of the
timer code too. I'll think about them - both rely on racing with timer
expiry itself - which is more likely to trigger these days because the
tick is now 1 msec, and kernel virtualization is more common too, which
can introduce almost arbitrary 'CPU delays' at any point in the kernel.

	Ingo

Re: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

[Andrea Arcangeli]

Hi Ingo,

On Sat, Oct 11, 2003 at 10:55:42AM +0200, Ingo Molnar wrote:
> 
> the patch below fixes two del_timer_sync() races that are still in the
> timer code.
> 
> the first race was actually triggered in a 2.4 backport of the 2.6 timer
> code. The second race was never triggered - it is mostly theoretical on a
> standalone kernel. (it's more likely in any virtualized or otherwise
> preemptable environment.)
> 
> both races happen when self-rearming timers are used. One mainstream
> example is kernel/itimer.c. The effect of the races is that
> del_timer_sync() lets a timer running instead of synchronizing with it,
> causing logic bugs (and crashes) in the affected kernel code. One typical
> incarnation of the race is a double add_timer().
> 
> race #1:
> 
> this code in __run_timers() is running on CPU0:
> 
>                         list_del(&timer->entry);
>                         timer->base = NULL;
> 			[*]
>                         set_running_timer(base, timer);
>                         spin_unlock_irq(&base->lock);
> 			[**]
>                         fn(data);
>                         spin_lock_irq(&base->lock);
> 
> CPU0 gets stuck at the [*] code-point briefly - after the timer->base has
> been set to NULL, but before the base->running_timer pointer has been set
> up. This is a fundamentally volatile scenario, as there's _zero_ knowledge
> in the data structures that this timer is about to be executed!

the 2.4 backport I'm using doesn't clear timer->base in __run_timers (it
actually never clears it).  This mean, del_timer_sync will serialize
against set_running_timers (aka timer_enter) just fine using the
base->lock. And the base can't change under del_timer_sync thanks to the
guarantee provided by the per-timer spinlock that I take in every timer
entry point (add_timer/del_timer/del_timer_sync whatever). I take the
per-timer lock before taking the base->lock of course.

In short I don't think the backported implementation I'm using was
vulnerable. Of course del_timer_sync unlocks both locks if  the timer
was running, before retrying, this allows the fn() callback to complete
(the recursive add_timer executed inside fn() needs to go ahead and take
the timer->lock before the timer can be nuked synchronously).

I find the per-timer spinlock much more relaible. And it's needed
anyways to get mod_timer against mod_timer right (I assume you already
backported that fix). Recently I also added the needed cpu_relax for HT
in the spinlock-by-hand slow paths of the 2.4 backport that I wrote
(this isn't an issue in 2.6 where the timer has a proper spinlock and
not a spinlock by hand).

> race #2
> 
> the checking of del_timer_sync() for 'pending or running timer' is
> fundamentally unrobust. Eg. if CPU0 gets stuck at the [***] point below:
> 
>                 base = &per_cpu(tvec_bases, i);
>                 if (base->running_timer == timer) {
>                         while (base->running_timer == timer) {
>                                 cpu_relax();
>                                 preempt_check_resched();
>                         }
> 			[***]
>                         break;
>                 }
>         }
>         smp_rmb();
>         if (timer_pending(timer))
>                 goto del_again;
> 
> 
> then del_timer_sync() has already decided that this timer is not running
> (we just finished loop-waiting for it), but we have not done the
> timer_pending() check yet.
> 
> if the timer has re-armed itself, and if the timer expires on CPU1 (this
> needs a long delay on CPU0 but that's not hard to achieve eg. in UML or
> with kernel preemption enabled), then CPU1 could start to expire the timer
> and gets to the [**] point in __run_timers (see above), then CPU1 gets
> stalled and CPU0 is unstalled, then the timer_pending() check in
> del_timer_sync() will not notice the running timer, and del_timer_sync()  
> returns - while CPU1 is just about to run the timer!

This also cannot happen with my current implementation. The
del_timer_sync cannot race with code before the unlock of the
base->lock.

I'm not checking all bases, I'm only checking the current
timer->base->running_timer to see if the timer is stull running (the
base cannot change under me anyways), and the check is completely
serialized. Nothing can change under del_timer_sync while I compare
timer->base->running_timer to timer.

My suggestion is to take the timer->lock everywhere, including
del_timer/del_timer_sync/add_timer_on in 2.6 too (and we may have to
stop clearing the base too). Currently in 2.6 add_timer_on is also
unsafe in rearming the timer, the per-timer locking everywhere will make
it safe against del_timer_sync too. Then all races will be automatically
closed like in my 2.4 version. Of course you will need to take the base
lock too in the del_timer_sync synchronous checks, but del_timer has to
take it anyways for removing the timer from the queue, so del_timer_sync
won't be slowed down by it if you do both things at the same time (as in
my current 2.4 implementation incidentally). And the cacheline with the
timer likely will be hot anyways for all the list_del/add, so I doubt
enforcing the full locking like I'm doing in 2.4 can be a significant
hit, and it makes everything so much simpler since you know nothing can
change under you after you get first the timer->lock and then the
base->lock.

I'd appreciate if you could double check I'm not missing something about
this problem.

For the record my latest and greatest implementation I'm talking about
above, is very easy to review and/or apply to any 2.4 tree, it's here:

	http://www.us.kernel.org/pub/linux/kernel/people/andrea/kernels/v2.4/2.4.23pre6aa3/00_smp-timers-not-deadlocking-6

(the non-deadlocking is because of the numerous anti-deadlock fixes
included into this version)

Comments welcome, thanks.

[patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0

[Ingo Molnar]

the patch below fixes two del_timer_sync() races that are still in the
timer code.

the first race was actually triggered in a 2.4 backport of the 2.6 timer
code. The second race was never triggered - it is mostly theoretical on a
standalone kernel. (it's more likely in any virtualized or otherwise
preemptable environment.)

both races happen when self-rearming timers are used. One mainstream
example is kernel/itimer.c. The effect of the races is that
del_timer_sync() lets a timer running instead of synchronizing with it,
causing logic bugs (and crashes) in the affected kernel code. One typical
incarnation of the race is a double add_timer().

race #1:

this code in __run_timers() is running on CPU0:

                        list_del(&timer->entry);
                        timer->base = NULL;
			[*]
                        set_running_timer(base, timer);
                        spin_unlock_irq(&base->lock);
			[**]
                        fn(data);
                        spin_lock_irq(&base->lock);

CPU0 gets stuck at the [*] code-point briefly - after the timer->base has
been set to NULL, but before the base->running_timer pointer has been set
up. This is a fundamentally volatile scenario, as there's _zero_ knowledge
in the data structures that this timer is about to be executed!

now CPU1 comes along and calls del_timer_sync(). It will find nothing -
neither timer->base nor base->running_timer will cause it to synchronize.  
It will return and report that the timer has been deleted - shortly
afterwards CPU1 continues to execute the timer fn, which will cause
crashes.

this particular race is easy to fix by reordering the timer->base clearing
with set_running_timer(), and putting a wmb() between them, but there's
more races:

race #2

the checking of del_timer_sync() for 'pending or running timer' is
fundamentally unrobust. Eg. if CPU0 gets stuck at the [***] point below:

                base = &per_cpu(tvec_bases, i);
                if (base->running_timer == timer) {
                        while (base->running_timer == timer) {
                                cpu_relax();
                                preempt_check_resched();
                        }
			[***]
                        break;
                }
        }
        smp_rmb();
        if (timer_pending(timer))
                goto del_again;


then del_timer_sync() has already decided that this timer is not running
(we just finished loop-waiting for it), but we have not done the
timer_pending() check yet.

if the timer has re-armed itself, and if the timer expires on CPU1 (this
needs a long delay on CPU0 but that's not hard to achieve eg. in UML or
with kernel preemption enabled), then CPU1 could start to expire the timer
and gets to the [**] point in __run_timers (see above), then CPU1 gets
stalled and CPU0 is unstalled, then the timer_pending() check in
del_timer_sync() will not notice the running timer, and del_timer_sync()  
returns - while CPU1 is just about to run the timer!

fixing this second race is hard - it involves a heavy race-check operation
that has to lock all bases, and has to re-check the base->running_timer
value, and timer_pending condition atomically.

this fix also fixes the first race, due to forcing del_timer_sync() to
always observe the timer state atomically, so the [*] code point will
always synchronize with del_timer_sync().

the patch is ugly but safe, and it has fixed the crashes in the 2.4
backport. I tested the patch on 2.6.0-test7 with some heavy itimer use and
it works fine. Removing self-arming timers safely is the sole purpose of
del_timer_sync(), so there's no way around this overhead i think. I
believe we should ultimately fix all major del_timer_sync() users to not
use self-arming timers - having del_timer_sync() in the thread-exit path
is now a considerable source of SMP overhead. But this is out of the scope
of current 2.6 fixes of course, and we have to support self-arming timers
as well.

	Ingo

--- linux/kernel/timer.c.orig
+++ linux/kernel/timer.c
@@ -315,23 +315,30 @@ EXPORT_SYMBOL(del_timer);
  * the timer it also makes sure the handler has finished executing on other
  * CPUs.
  *
- * Synchronization rules: callers must prevent restarting of the timer,
- * otherwise this function is meaningless. It must not be called from
- * interrupt contexts. Upon exit the timer is not queued and the handler
- * is not running on any CPU.
+ * Synchronization rules: callers must prevent restarting of the timer
+ * (except restarting the timer from the timer function itself), otherwise
+ * this function is meaningless. It must not be called from interrupt
+ * contexts. Upon exit the timer is not queued and the handler is not
+ * running on any CPU.
  *
- * The function returns whether it has deactivated a pending timer or not.
+ * The function returns the number of times it has deactivated a pending
+ * timer.
  */
 int del_timer_sync(struct timer_list *timer)
 {
+	int i, ret = 0, again;
+	unsigned long flags;
 	tvec_base_t *base;
-	int i, ret = 0;
 
 	check_timer(timer);
 
 del_again:
 	ret += del_timer(timer);
 
+	/*
+	 * First do a lighter but racy check, whether the
+	 * timer is running on any other CPU:
+	 */
 	for (i = 0; i < NR_CPUS; i++) {
 		if (!cpu_online(i))
 			continue;
@@ -345,8 +352,33 @@ del_again:
 			break;
 		}
 	}
-	smp_rmb();
+
+	/*
+	 * Do a heavy but race-free re-check to make sure both that
+	 * the timer is neither running nor pending:
+	 */
+	again = 0;
+	local_irq_save(flags);
+
+	for (i = 0; i < NR_CPUS; i++)
+		if (cpu_online(i))
+			spin_lock(&per_cpu(tvec_bases, i).lock);
+
 	if (timer_pending(timer))
+		again = 1;
+	else
+		for (i = 0; i < NR_CPUS; i++)
+			if (cpu_online(i) &&
+				(per_cpu(tvec_bases, i).running_timer == timer))
+					again = 1;
+
+	for (i = 0; i < NR_CPUS; i++)
+		if (cpu_online(i))
+			spin_unlock(&per_cpu(tvec_bases, i).lock);
+
+	local_irq_restore(flags);
+
+	if (again)
 		goto del_again;
 
 	return ret;