timer locking optimization
Review
Quoted 9 lines · Roman Zippel
(quoted diff) +7
-0+ base = timer->base; + spin_lock_irqsave(&base->lock, *flags); + while (unlikely(base != timer->base)) { + /* The timer has migrated to another CPU */ + spin_unlock(&base->lock); cpu_relax(); + base = timer->base; + spin_lock(&base->lock);
This spins with interrupts disabled, not good, imho.
Quoted 16 lines
int
__mod_timer(struct timer_list *timer, unsigned long expires)(quoted diff) +2
-2@@ -212,6 +207,7 @@ int __mod_timer(struct timer_list *timer base = lock_timer_base(timer, &flags); +restart: if (timer_pending(timer)) { detach_timer(timer, 0); ret = 1;@@ -231,11 +227,16 @@ int __mod_timer(struct timer_list *timer /* The timer remains on a former base */ new_base = container_of(base, tvec_base_t, t_base); } else { - /* See the comment in lock_timer_base() */ - timer->base = NULL; + /*
Review int __mod_timer(struct timer_list *timer · line 239
Quoted 10 lines
(quoted diff) +7
-1+ * We shortly release the timer and the timer can + * migrate to another cpu, so recheck the base after + * getting the lock. + */ + timer->base = &new_base->t_base; spin_unlock(&base->lock); spin_lock(&new_base->t_base.lock); - timer->base = &new_base->t_base; + if (unlikely(timer->base != &new_base->t_base)) + goto restart;
This is not right.
This way you can delete the timer (ret == 1), notice that timer's base was changed after re-locking, goto restart, and get ret == 0.
Also, you have wrong value of 'base' after 'goto restart'.
Oleg.
Hi,
Quoted 10 lines · Oleg Nesterov
Review
Quoted 8 lines
(quoted diff) +7
-0+ base = timer->base; + spin_lock_irqsave(&base->lock, *flags); + while (unlikely(base != timer->base)) { + /* The timer has migrated to another CPU */ + spin_unlock(&base->lock); cpu_relax(); + base = timer->base; + spin_lock(&base->lock);This spins with interrupts disabled, not good, imho.
It's the slow path anyway, so restoring flags should indeed be fine.
Quoted 2 lines
This way you can delete the timer (ret == 1), notice that timer's base was changed after re-locking, goto restart, and get ret == 0.
ret is only set, but not reset, so if __mod_timer() deleted the timer it will return 1.
Quoted 1 line
Also, you have wrong value of 'base' after 'goto restart'.
Indeed, thanks for spotting this.
bye, Roman
Hi,
Quoted 1 line · Oleg Nesterov
Also, you have wrong value of 'base' after 'goto restart'.
Here is the updated patch, which fixes this.
bye, Roman
kernel/timer.c +19 -18
@@ -178,27 +178,20 @@ static inline void detach_timer(struct t* * So __run_timers/migrate_timers can safely modify all timers which could * be found on ->tvX lists. -* -* When the timer's base is locked, and the timer removed from list, it is -* possible to set timer->base = NULL and drop the lock: the timer remains -* locked. */ static timer_base_t *lock_timer_base (struct timer_list *timer,unsigned long *flags) {timer_base_t *base; -for (;;) { - base = timer->base; -if (likely (base !=NULL )) { -spin_lock_irqsave (&base->lock, *flags); -if (likely (base == timer->base)) -return base; -/* The timer has migrated to another CPU */ -spin_unlock_irqrestore (&base->lock, *flags); - } -cpu_relax (); - } +again: + base = timer->base; +spin_lock_irqsave (&base->lock, *flags); +if (likely (base == timer->base)) +return base; +/* The timer has migrated to another CPU */ +spin_unlock_irqrestore (&base->lock, *flags); + goto again; }int __mod_timer (struct timer_list *timer,unsigned long expires)
@@ -210,6 +203,7 @@ int __mod_timer(struct timer_list *timerBUG_ON (!timer->function); +restart: base =lock_timer_base (timer, &flags);if (timer_pending (timer)) {
@@ -231,11 +225,18 @@ int __mod_timer(struct timer_list *timer/* The timer remains on a former base */ new_base =container_of (base, tvec_base_t, t_base); }else { -/* See the comment in lock_timer_base() */ - timer->base =NULL ; +/* +* We shortly release the timer and the timer can +* migrate to another cpu, so recheck the base after +* getting the lock. +*/ + timer->base = &new_base->t_base;spin_unlock (&base->lock);spin_lock (&new_base->t_base.lock); - timer->base = &new_base->t_base; +if (unlikely (timer->base != &new_base->t_base)) { +spin_unlock_irqrestore (&new_base->t_base.lock, flags); + goto restart; + } } }
Quoted 13 lines · Roman Zippel
kernel/timer.c +1
-0@@ -210,6 +203,7 @@ int __mod_timer(struct timer_list *timerBUG_ON (!timer->function); +restart: base =lock_timer_base (timer, &flags);if (timer_pending (timer)) {@@ -231,11 +225,18 @@ int __mod_timer(struct timer_list *timer/* The timer remains on a former base */ new_base =container_of (base, tvec_base_t, t_base); }else {
kernel/timer.c int __mod_timer(struct timer_list *timer · line 235
Quoted 10 lines
kernel/timer.c +6
-2-/* See the comment in lock_timer_base() */ - timer->base =NULL ; +/* +* We shortly release the timer and the timer can +* migrate to another cpu, so recheck the base after +* getting the lock. +*/ + timer->base = &new_base->t_base;spin_unlock (&base->lock);spin_lock (&new_base->t_base.lock);
Still not correct, I beleive.
The problem is that you are changing timer->base = &new_base->t_base without holding new_base->t_base.lock, this is racy vs timer_del(). Suppose we are calling __mod_timer(pending_timer):
__mod_timer() locks old base, deletes the timer, changes timer's base, unlocks old base.
Another cpu calls del_timer(). It is possible that this cpu will see the new value of ->base == new_base before it sees changes in the timer->entry. It locks new_base, but this is not enough, because the timer was removed from list under the old base's lock and we don't have a proper serialization. So it is possible that del_timer() sees that the timer is still pending, and will try to delete it again.
In other words, in this scenario __mod_timer() and del_timer() will take 2 different locks trying to serialize access to common data.
You can solve this with memory barriers, but this will be pessimization, not optimization (you will also need smp_rmb in lock_timer_base()).
Honestly, personally I don'like this patch even if it was correct. It complicates the code, and the only win is that it removes 'if (likely(base != NULL))' from the fast path, I doubt this is noticeable.
Also, __mod_timer() becomes "non atomic", but probably this is ok.
Btw, I think you have the same problems in "[PATCH 2/9] ptimer core".
Oleg.
Hi,
Quoted 1 line · Oleg Nesterov
Still not correct, I beleive.
Here is a new idea, what do you think about using spin_trylock(), e.g. something like:
if (spin_trylock(&new_base->t_base.lock)) {
timer->base = &new_base->t_base;
spin_unlock(&base->lock);
} else
new_base = container_of(base, tvec_base_t, t_base);It's not like we must start the timer on the current cpu and this might even be faster. If the new base is busy on another cpu, it's possible we have to pull dirty cache lines from the other cpu, where we might already have the data from the current base already in the cache from the detach.
bye, Roman
Quoted 16 lines · Roman Zippel
Hi,
Quoted 1 line · Oleg Nesterov
Still not correct, I beleive.
Here is a new idea, what do you think about using
spin_trylock(), e.g. something like:if (spin_trylock(&new_base->t_base.lock)) { timer->base = &new_base->t_base; spin_unlock(&base->lock); } else new_base = container_of(base, tvec_base_t, t_base);
Quoted 4 lines
It's not like we must start the timer on the current cpu and this might even be faster. If the new base is busy on another cpu, it's possible we have to pull dirty cache lines from the other cpu, where we might already have the data from the current base already in the cache from the detach.
... and this will simplify the code! I think this is a nice idea. Something like this:
if (base != &new_base->t_base) {
if (unlikely(base->running_timer == timer) ||
!spin_trylock(&new_base->t_base.lock)) {
/* The timer remains on a former base */
new_base = container_of(base, tvec_base_t, t_base);
} else {
timer->base = &new_base->t_base;
spin_unlock(&base->lock);
}
}But please update comments too, and don't forget to cc Ingo and Andrew at least. In my opinion this patch should go separately from other ptimer patches.
Oleg.
kernel/timer.c int __mod_timer(struct timer_list *timer · line 209
Quoted 10 lines · Roman Zippel
int
__mod_timer(struct timer_list *timer, unsigned long expires)kernel/timer.c +1
-0@@ -210,6 +203,7 @@ int __mod_timer(struct timer_list *timerBUG_ON (!timer->function); +restart: base =lock_timer_base (timer, &flags);if (timer_pending (timer)) {
Another problem. __mode_timer() does:
if (timer_pending(timer)) {
detach_timer(timer, 0);Note that 'clear_pending' parameter == 0. This means that detach_timer() will remove the timer from list, but won't clear 'pending' status. So this will crash after 'goto restart' (or in case of concurrent del_timer()).
Oleg.
Hi,
Quoted 8 lines · Oleg Nesterov
Another problem.
__mode_timer()does:if (timer_pending(timer)) { detach_timer(timer, 0);Note that '
clear_pending' parameter == 0. This means thatdetach_timer()will remove the timer from list, but won't clear 'pending' status. So this will crash after 'goto restart' (or in case of concurrentdel_timer()).
I just noticed this too. I'll drop the patch and I'll also change the second patch.
Thanks for looking into this.
bye, Roman