Re: [BUG] Race condition with it_real_fn in kernel/itimer.c

Re: [BUG] Race condition with it_real_fn in kernel/itimer.c

[Oleg Nesterov]

Steven Rostedt wrote:
>
> +	try_again:
>  		spin_lock_irq(&tsk->sighand->siglock);
>  		interval = tsk->signal->it_real_incr;
>  		val = it_real_value(tsk->signal);
> -		if (val)
> +		if (val) {
> +			spin_unlock_irq(&tsk->sighand->siglock);
>  			del_timer_sync(&tsk->signal->real_timer);
> +			goto try_again;

I think we don't need del_timer_sync() at all, just del_timer().

Because it_real_value() returns 0 when timer is not pending. And
in this case the timer may still be running, but do_setitimer()
doesn't call del_timer_sync().

Oleg.

Re: [BUG] Race condition with it_real_fn in kernel/itimer.c

[Steven Rostedt]

On Wed, 2005-06-15 at 21:39 +0400, Oleg Nesterov wrote:
> Steven Rostedt wrote:
> >
> > +	try_again:
> >  		spin_lock_irq(&tsk->sighand->siglock);
> >  		interval = tsk->signal->it_real_incr;
> >  		val = it_real_value(tsk->signal);
> > -		if (val)
> > +		if (val) {
> > +			spin_unlock_irq(&tsk->sighand->siglock);
> >  			del_timer_sync(&tsk->signal->real_timer);
> > +			goto try_again;
> 
> I think we don't need del_timer_sync() at all, just del_timer().
> 
> Because it_real_value() returns 0 when timer is not pending. And
> in this case the timer may still be running, but do_setitimer()
> doesn't call del_timer_sync().

OK, so is this the better patch?

[Andrew, do NOT use the following]

--- linux-2.6.12-rc6/kernel/itimer.c.orig	2005-06-15 12:14:13.000000000 -0400
+++ linux-2.6.12-rc6/kernel/itimer.c	2005-06-15 14:06:23.000000000 -0400
@@ -157,7 +157,7 @@
 		interval = tsk->signal->it_real_incr;
 		val = it_real_value(tsk->signal);
 		if (val)
-			del_timer_sync(&tsk->signal->real_timer);
+			del_timer(&tsk->signal->real_timer);
 		tsk->signal->it_real_incr =
 			timeval_to_jiffies(&value->it_interval);
 		it_real_arm(tsk, timeval_to_jiffies(&value->it_value));


I haven't played too much with the itimer, what harm can happen if the
timer is running while this is deleted?  [examines code here] This also
looks bad. Since the softirq function can be running and then call
it_real_arm unprotected! And you can see here that it_real_arm is also
called and they both call add_timer! This would not work, so far the
first patch seems to handle this. 


-- Steve

PS. Don't strip the CC list.

[PATCH] Re: [BUG] Race condition with it_real_fn in kernel/itimer.c

[Steven Rostedt]

On Wed, 2005-06-15 at 14:37 -0400, Steven Rostedt wrote:

> 
> I haven't played too much with the itimer, what harm can happen if the
> timer is running while this is deleted?  [examines code here] This also
> looks bad. Since the softirq function can be running and then call
> it_real_arm unprotected! And you can see here that it_real_arm is also
> called and they both call add_timer! This would not work, so far the
> first patch seems to handle this. 

Ha! There's even another problem that I just noticed.  it_real_value
could return zero while the function is running! So you don't get the
protection here either!  Take a look here to see what the problem is.

static unsigned long it_real_value(struct signal_struct *sig)
{
	unsigned long val = 0;
	if (timer_pending(&sig->real_timer)) {
		val = sig->real_timer.expires - jiffies;

		/* look out for negative/zero itimer.. */
		if ((long) val <= 0)
			val = 1;
	}
	return val;
}

and 

static inline int timer_pending(const struct timer_list * timer)
{
	return timer->base != NULL;
}

and

static inline void __run_timers(tvec_base_t *base)
{
  ...
			timer = list_entry(head->next,struct timer_list,entry);
 			fn = timer->function;
 			data = timer->data;

			list_del(&timer->entry);
			set_running_timer(base, timer);
			smp_wmb();
			timer->base = NULL;
			spin_unlock_irq(&base->lock);
			{
				u32 preempt_count = preempt_count();
				fn(data);
...
}


So, timer_pending tests if timer->base is NULL, but here we see that
timer->base IS NULL before the function is called, and as I have said
earlier, the it_real_arm can be called on two CPUS simultaneously. So
here's another patch that should fix this race condition too.


--- linux-2.6.12-rc6/kernel/itimer.c.orig	2005-06-15 12:14:13.000000000 -0400
+++ linux-2.6.12-rc6/kernel/itimer.c	2005-06-15 15:31:12.000000000 -0400
@@ -156,8 +156,15 @@
 		spin_lock_irq(&tsk->sighand->siglock);
 		interval = tsk->signal->it_real_incr;
 		val = it_real_value(tsk->signal);
-		if (val)
-			del_timer_sync(&tsk->signal->real_timer);
+		/*
+		 * Call del_timer_sync unconditionally, since we don't
+		 * know if it is running or not. We also need to unlock
+		 * the siglock so that the it_real_fn called by ksoftirqd
+		 * doesn't wait for us.
+		 */
+		spin_unlock(&tsk->sighand->siglock);
+		del_timer_sync(&tsk->signal->real_timer);
+		spin_lock(&tsk->sighand->siglock);
 		tsk->signal->it_real_incr =
 			timeval_to_jiffies(&value->it_interval);
 		it_real_arm(tsk, timeval_to_jiffies(&value->it_value));


-- Steve

Re: [PATCH] Re: [BUG] Race condition with it_real_fn in kernel/itimer.c

[Oleg Nesterov]

Steven Rostedt wrote:
>
> So, timer_pending tests if timer->base is NULL, but here we see that
> timer->base IS NULL before the function is called, and as I have said
> earlier, the it_real_arm can be called on two CPUS simultaneously. So
> here's another patch that should fix this race condition too.
>
> [...]
>
> +		/*
> +		 * Call del_timer_sync unconditionally, since we don't
> +		 * know if it is running or not. We also need to unlock
> +		 * the siglock so that the it_real_fn called by ksoftirqd
> +		 * doesn't wait for us.
> +		 */
> +		spin_unlock(&tsk->sighand->siglock);
> +		del_timer_sync(&tsk->signal->real_timer);
> +		spin_lock(&tsk->sighand->siglock);

I don't think this is 100% correct. After del_timer_sync() returns another
thread can come and call do_setitimer() and re-arm the timer (because with
your patch we are dropping tsk->sighand->siglock here). So this patch does
not garantees that the timer is not queued/running after del_timer_sync(),
and the it_real_arm can be called on two CPUS simultaneously again.

There is a try_to_del_timer_sync() in the -mm tree which is suitable here:

	again:
		spin_lock_irq(&tsk->sighand->siglock);
		if (try_to_del_timer_sync(&tsk->signal->real_timer) < 0) {
			spin_unlock_irq(&tsk->sighand->siglock);
			goto again;
		}

Oleg.

Re: [BUG] Race condition with it_real_fn in kernel/itimer.c

[Oleg Nesterov]

Steven Rostedt wrote:
> 
> On Wed, 2005-06-15 at 21:39 +0400, Oleg Nesterov wrote:
> >
> > I think we don't need del_timer_sync() at all, just del_timer().
> >
> [...]
>
> it_real_arm unprotected! And you can see here that it_real_arm is also
> called and they both call add_timer! This would not work, so far the
> first patch seems to handle this.

Yes, you are right, thanks.

> PS. Don't strip the CC list.

I am sorry. It's because I am not subscribed to lkml, I saw your message
on http://marc.theaimsgroup.com/. You might know is there an lkml archive
which does not hide recipients list (or in mbox format) ?

Oleg.

Re: [PATCH] Re: [BUG] Race condition with it_real_fn in kernel/itimer.c

[Steven Rostedt]

On Thu, 2005-06-16 at 11:44 +0400, Oleg Nesterov wrote:
> Steven Rostedt wrote:
> >
> > So, timer_pending tests if timer->base is NULL, but here we see that
> > timer->base IS NULL before the function is called, and as I have said
> > earlier, the it_real_arm can be called on two CPUS simultaneously. So
> > here's another patch that should fix this race condition too.
> >
> > [...]
> >
> > +		/*
> > +		 * Call del_timer_sync unconditionally, since we don't
> > +		 * know if it is running or not. We also need to unlock
> > +		 * the siglock so that the it_real_fn called by ksoftirqd
> > +		 * doesn't wait for us.
> > +		 */
> > +		spin_unlock(&tsk->sighand->siglock);
> > +		del_timer_sync(&tsk->signal->real_timer);
> > +		spin_lock(&tsk->sighand->siglock);
> 
> I don't think this is 100% correct. After del_timer_sync() returns another
> thread can come and call do_setitimer() and re-arm the timer (because with
> your patch we are dropping tsk->sighand->siglock here). So this patch does
> not garantees that the timer is not queued/running after del_timer_sync(),
> and the it_real_arm can be called on two CPUS simultaneously again.
> 

I first thought that too, but then looking at the code I noticed:

int do_setitimer(int which, struct itimerval *value, struct itimerval *ovalue)
{
        struct task_struct *tsk = current;

Where tsk is current.  So the only ones that can change the
tsk->signal->real_timer seems to be the task itself and ksoftirqd. So
between del_timer_sync (which handles the ksoftirqd part) and the
spin_lock, there's no one else that can modify tsk->signal->real_timer.
So I don't believe that there is a race condition here.

[thinks about this a little]

Oh wait, is ->signal shared among threads?  Damn, I think so! So you are
right, another _thread_ can come and change this. I forgot about threads
(they're evil! ;-).

> There is a try_to_del_timer_sync() in the -mm tree which is suitable here:
> 
> 	again:
> 		spin_lock_irq(&tsk->sighand->siglock);
> 		if (try_to_del_timer_sync(&tsk->signal->real_timer) < 0) {
> 			spin_unlock_irq(&tsk->sighand->siglock);
> 			goto again;
> 		}

OK, for the -mm branch this may work. But for the current tree, we may
need to do something else.  Like this ugly patch. But it should work!


int do_setitimer(int which, struct itimerval *value, struct itimerval *ovalue)
{
        struct task_struct *tsk = current;
	static spinlock_t lock = SPIN_LOCK_UNLOCKED;

[...]
		spin_lock(&lock);
		spin_unlock(&tsk->sighand->siglock);
		del_timer_sync(&tsk->signal->real_timer);
		spin_lock(&tsk->sighand->siglock);
		spin_unlock(&lock);

This would handle the case for threads in the main line kernel, but it
looks (to me) pretty ugly, but should work. I also don't like this
because it is shared among all tasks!

Andrew, (or Roland since I see Andrew added you to the list)
  
 What do you think? Should try_to_del_timer_sync be brought over to the
mainline, or have the above ugly code added?

-- Steve

Re: [PATCH] Re: [BUG] Race condition with it_real_fn in kernel/itimer.c

[Steven Rostedt]

On Thu, 2005-06-16 at 07:33 -0400, Steven Rostedt wrote:

> int do_setitimer(int which, struct itimerval *value, struct itimerval *ovalue)
> {
>         struct task_struct *tsk = current;
> 	static spinlock_t lock = SPIN_LOCK_UNLOCKED;
> 
> [...]
> 		spin_lock(&lock);
> 		spin_unlock(&tsk->sighand->siglock);
> 		del_timer_sync(&tsk->signal->real_timer);
> 		spin_lock(&tsk->sighand->siglock);
> 		spin_unlock(&lock);

OK, I just got out of bed, so I'm not too with it :-) 

This is pretty much a guaranteed deadlock!  So the first spin_lock needs
to go before the siglock. That should do it!


	case ITIMER_REAL:
		spin_lock_irq(&lock);
		spin_lock(&tsk->sighand->siglock);
		[...]
		spin_unlock(&tsk->sighand->siglock);
		del_timer_sync(&tsk->signal->real_timer);
		spin_lock(&tsk->sighand->siglock);
		spin_unlock(&lock);

We just need to keep two do_setitimer calls from grabbing the siglock.
That first string of code didn't prevent that.

-- Steve

Re: [PATCH] Re: [BUG] Race condition with it_real_fn inkernel/itimer.c

[Oleg Nesterov]

Steven Rostedt wrote:
> 
> Andrew, (or Roland since I see Andrew added you to the list)
> 
>  What do you think? Should try_to_del_timer_sync be brought over to the
> mainline, or have the above ugly code added?

On the other hand, if 2 threads calls do_setitimer() in parallel
they are asking for trouble. So may be it is possible to ignore
this minor problem and stay with your patch?

Oleg.