lkml.org 
[lkml]   [2003]   [Oct]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [patch] SMP races in the timer code, timer-fix-2.6.0-test7-A0
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.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:58    [from the cache]
©2003-2011 Jasper Spaans