Skip to contentSkip to conversation

timer locking optimization

PATCH Oleg Nesterov 2 participants 8 messages Nov 29, 2005 – Nov 30, 2005

lore
Share & tools
lore
#0 lore raw

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.

#1 lore raw

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

#2 lore raw
In reply to Oleg Nesterov

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
Index: linux-2.6/kernel/timer.c
===================================================================
@@ -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 *timer
 
 	BUG_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;
+			}
 		}
 	}
 
#3 lore raw
Quoted 13 lines · Roman Zippel
kernel/timer.c +1 -0
@@ -210,6 +203,7 @@ int __mod_timer(struct timer_list *timer
 
        BUG_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.

#4 lore raw

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

#5 lore raw
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.

#6 lore raw
In reply to Roman Zippel

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 *timer
 
        BUG_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.

#7 lore raw

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 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()).

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