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

PATCH Manfred Spraul 4 participants 8 messages Oct 11, 2003 – Oct 15, 2003 High-resolution timers, timer wheel, clockevents

lore

Share & tools

lore

Manfred Spraul

author

2003-10-11 15:01 UTC #0 lore raw

Quoted 5 lines · Ingo

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.

Signature · 1 line

    Manfred

Ingo Molnar

2003-10-11 16:14 UTC #1 lore raw

Quoted 6 lines · Manfred Spraul

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

Ingo Molnar

2003-10-11 16:10 UTC #2 lore raw

Quoted 2 lines · Ingo Molnar

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

Manfred Spraul

author

2003-10-11 16:55 UTC #3 lore raw

Quoted 4 lines · Ingo Molnar

On Sat, 11 Oct 2003, Ingo Molnar wrote:

Quoted 8 lines

Quoted 4 lines
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

Andrew Morton

2003-10-13 10:09 UTC #4 lore raw

In reply to Ingo Molnar

Quoted 9 lines · Ingo Molnar

Quoted 2 lines · Ingo Molnar
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.

Ingo Molnar

2003-10-11 16:42 UTC #5 lore raw

In reply to Ingo Molnar

Quoted 8 lines · Ingo Molnar

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

include/linux/timer.h renamed from include/linux/timer.h.orig +3 -0

@@ -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);
 }

kernel/timer.c renamed from kernel/timer.c.orig +33 ~~-30~~

105 lines not on this page · raw message

Linus Torvalds

2003-10-14 04:25 UTC #6 lore raw

Quoted 5 lines · Ingo Molnar

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:

kernel/timer.c repeat: · line 429

Quoted 9 lines

kernel/timer.c renamed from kernel/timer.c.orig +3 -1

 			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

Ingo Molnar

2003-10-15 18:41 UTC #7 lore raw

Quoted 3 lines · Linus Torvalds

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