[PATCH] Race condition in del_timer_sync (2.5)

[PATCH] Race condition in del_timer_sync (2.5)

[Tejun Huh]

 Hello,

 This patch fixes a race between del_timer_sync and recursive timers.
Current implementation allows the value of timer->base that is used
for timer_pending test to be fetched before finishing running_timer
test, so it's possible for a recursive time to be pending after
del_timer_sync.  Adding smp_rmb before timer_pending removes the race.

 The patch is against the latest 2.5 bk tree.  Please point out if I
got something wrong.  TIA.

-- 
tejun

diff -Nru a/kernel/timer.c b/kernel/timer.c
--- a/kernel/timer.c	Tue Sep  2 11:56:58 2003
+++ b/kernel/timer.c	Tue Sep  2 11:56:58 2003
@@ -338,6 +338,7 @@
 			break;
 		}
 	}
+	smp_rmb();
 	if (timer_pending(timer))
 		goto del_again;
 

Re: [PATCH] Race condition in del_timer_sync (2.5)

[Ingo Molnar]

On Tue, 2 Sep 2003, Tejun Huh wrote:

>  This patch fixes a race between del_timer_sync and recursive timers.
> Current implementation allows the value of timer->base that is used for
> timer_pending test to be fetched before finishing running_timer test, so
> it's possible for a recursive time to be pending after del_timer_sync.  
> Adding smp_rmb before timer_pending removes the race.

good catch. Have you ever trigger this bug, or did you find it via code
review?

just to explore the scope of this problem a bit more: at first glance all
other timer_pending() uses seem to be safe. del_timer_sync()'s
timer_pending() use is special, because it's next to the ->running_timer
check without any barriers inbetween - so we could indeed in theory end up
with having the two reads reordered and a freshly added timer (on another
CPU) not being recognized properly. Also, this is the only timer API call
that guarantees the complete stopping of a timer.

	Ingo

Re: [PATCH] Race condition in del_timer_sync (2.5)

[Tejun Huh]

On Tue, Sep 02, 2003 at 08:33:50AM +0200, Ingo Molnar wrote:
> 
> On Tue, 2 Sep 2003, Tejun Huh wrote:
> 
> >  This patch fixes a race between del_timer_sync and recursive timers.
> > Current implementation allows the value of timer->base that is used for
> > timer_pending test to be fetched before finishing running_timer test, so
> > it's possible for a recursive time to be pending after del_timer_sync.  
> > Adding smp_rmb before timer_pending removes the race.
> 
> good catch. Have you ever trigger this bug, or did you find it via code
> review?

 I found it via code review.  Actually, I haven't succeeded to boot
even once with 2.5 on my test box.  It prints a lot of messages about
scheduling while atomic and eventually panics.  I'm trying to identify
what's causing the problem.  Wish me luck. :-)

> just to explore the scope of this problem a bit more: at first glance all
> other timer_pending() uses seem to be safe. del_timer_sync()'s
> timer_pending() use is special, because it's next to the ->running_timer
> check without any barriers inbetween - so we could indeed in theory end up
> with having the two reads reordered and a freshly added timer (on another
> CPU) not being recognized properly. Also, this is the only timer API call
> that guarantees the complete stopping of a timer.
> 
> 	Ingo

 Yeap, in other cases, when timer_pending() fails to see timer->base,
it can be thought as the test took place before the timer is added,
and leaving pending timer behind is semantically ok.  But because a
recusive timer without some other entity trying to add it should
actually be removed by timer_del_sync(), timer_pending() test should
be barriered from running_timer test.

 I'll submit the patch to Linus soon.

-- 
tejun

Re: [PATCH] Race condition in del_timer_sync (2.5)

[Linus Torvalds]

On Tue, 2 Sep 2003, Tejun Huh wrote:
> 
>  I'll submit the patch to Linus soon.

I actually already committed it to my tree, since everybody seems to agree 
on it...

		Linus

----
# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
#	           ChangeSet	1.1412  -> 1.1413 
#	      kernel/timer.c	1.66    -> 1.67   
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 03/09/02	torvalds@home.osdl.org	1.1413
# Fix del_timer_sync() SMP memory ordering (from Tejun Huh <tejun@aratech.co.kr>)
# 
# From Tejun's posting:
# >
# > This patch fixes a race between del_timer_sync and recursive timers.
# > Current implementation allows the value of timer->base that is used
# > for timer_pending test to be fetched before finishing running_timer
# > test, so it's possible for a recursive time to be pending after
# > del_timer_sync.  Adding smp_rmb before timer_pending removes the race.
# --------------------------------------------
#
diff -Nru a/kernel/timer.c b/kernel/timer.c
--- a/kernel/timer.c	Tue Sep  2 00:55:15 2003
+++ b/kernel/timer.c	Tue Sep  2 00:55:15 2003
@@ -338,6 +338,7 @@
 			break;
 		}
 	}
+	smp_rmb();
 	if (timer_pending(timer))
 		goto del_again;