[lkml]   [2003]   [Oct]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    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

    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

    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:

    (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
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:58    [W:0.030 / U:12.280 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site