[PATCH] futex: Remove the owner check when waking task in handle_futex_death

[PATCH] futex: Remove the owner check when waking task in handle_futex_death

[zhang.yi20]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=GB2312, Size: 1956 bytes --]


Hi all,

Task processes all its owned robust futex when it is exiting,
to ensure the futexes can be taken by other tasks.

Though this can not work good in sometimes.
Think about this scene£º
1. A robust mutex is shared for two processes, each process has
   multi threads to lock the mutex.
2. One of the threads locks the mutex, and the others are waiting
   and sorted in order of priority.
3. The process to which the mutex owner thread belongs is dying
   without unlocking the mutex£¬and handle_futex_death is invoked
   to wake the first waiter.
4. If the first waiter belongs to the same process£¬it has no chance
   to return to the userspace to lock the mutex, and it won't wake
   the next waiter because it is not the owner of the mutex.
5. The rest waiters of the other process may block forever.

This patch remove the owner check when waking task in handle_futex_death.
If above occured, The dying task can wake the next waiter by processing its list_op_pending.
The waked task could return to userspace and try to lock the mutex again.


Signed-off-by: Zhang Yi <zhang.yi20@zte.com.cn>
Reviewed-by: Xie Baoyou <xie.baoyou@zte.com.cn>
Reviewed-by: Lu Zhongjun <lu.zhongjun@zte.com.cn>



--- linux/kernel/futex.c	2013-09-25 09:24:34.639634244 +0000
+++ linux/kernel/futex.c	2013-09-25 10:12:17.619673546 +0000
@@ -2541,14 +2541,15 @@ retry:
 		}
 		if (nval != uval)
 			goto retry;
-
-		/*
-		 * Wake robust non-PI futexes here. The wakeup of
-		 * PI futexes happens in exit_pi_state():
-		 */
-		if (!pi && (uval & FUTEX_WAITERS))
-			futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
 	}
+
+	/*
+	 * Wake robust non-PI futexes here. The wakeup of
+	 * PI futexes happens in exit_pi_state():
+	 */
+	if (!pi)
+		futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
+
 	return 0;
 }
ÿôèº{.nÇ+‰·Ÿ®‰­†+%ŠËÿ±éݶ\x17¥Šwÿº{.nÇ+‰·¥Š{±þG«éÿŠ{ayº\x1dʇڙë,j\a­¢f£¢·hšïêÿ‘êçz_è®\x03(­éšŽŠÝ¢j"ú\x1a¶^[m§ÿÿ¾\a«þG«éÿ¢¸?™¨è­Ú&£ø§~á¶iO•æ¬z·švØ^\x14\x04\x1a¶^[m§ÿÿÃ\fÿ¶ìÿ¢¸?–I¥

Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death

[Darren Hart]

On Thu, 2013-09-26 at 09:09 +0800, zhang.yi20@zte.com.cn wrote:
> Hi all,
> 
> Task processes all its owned robust futex when it is exiting,
> to ensure the futexes can be taken by other tasks.
> 
> Though this can not work good in sometimes.
> Think about this scene：
> 1. A robust mutex is shared for two processes, each process has
>    multi threads to lock the mutex.
> 2. One of the threads locks the mutex, and the others are waiting
>    and sorted in order of priority.
> 3. The process to which the mutex owner thread belongs is dying
>    without unlocking the mutex，and handle_futex_death is invoked
>    to wake the first waiter.
> 4. If the first waiter belongs to the same process，it has no chance
>    to return to the userspace to lock the mutex, and it won't wake
>    the next waiter because it is not the owner of the mutex.
> 5. The rest waiters of the other process may block forever.
> 
> This patch remove the owner check when waking task in handle_futex_death.
> If above occured, The dying task can wake the next waiter by processing its list_op_pending.
> The waked task could return to userspace and try to lock the mutex again.
> 

The problem is if you allow the non-owner to do the wake, you risk
multiple threads calling futex_wake(). Or is that your intention? Wake
one waiter for every thread that calls handle_futex_death()?

> 
> Signed-off-by: Zhang Yi <zhang.yi20@zte.com.cn>
> Reviewed-by: Xie Baoyou <xie.baoyou@zte.com.cn>
> Reviewed-by: Lu Zhongjun <lu.zhongjun@zte.com.cn>
> 
> 
> 
> --- linux/kernel/futex.c	2013-09-25 09:24:34.639634244 +0000
> +++ linux/kernel/futex.c	2013-09-25 10:12:17.619673546 +0000
> @@ -2541,14 +2541,15 @@ retry:
>  		}
>  		if (nval != uval)
>  			goto retry;
> -
> -		/*
> -		 * Wake robust non-PI futexes here. The wakeup of
> -		 * PI futexes happens in exit_pi_state():
> -		 */
> -		if (!pi && (uval & FUTEX_WAITERS))
> -			futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
>  	}
> +
> +	/*
> +	 * Wake robust non-PI futexes here. The wakeup of
> +	 * PI futexes happens in exit_pi_state():
> +	 */
> +	if (!pi)


Why did you drop the FUTEX_WAITERS condition?

You sent a different patch earlier this year that didn't appear to get
any review:

https://lkml.org/lkml/2013/4/8/65

This one woke all the waiters and let them sort it out.

It seems we've hashed through this already, but I'm not finding the
email logs and I don't recall off the top of my head.

> +		futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
> +
>  	return 0;
>  }

-- 
Darren Hart
Intel Open Source Technology Center
Yocto Project - Linux Kernel

Re: Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death

[zhang.yi20]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=GB2312, Size: 3734 bytes --]



Darren Hart <dvhart@linux.intel.com> wrote on 2013/09/27 02:15:17:


> Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death
>
> On Thu, 2013-09-26 at 09:09 +0800, zhang.yi20@zte.com.cn wrote:
> > Hi all,
> >
> > Task processes all its owned robust futex when it is exiting,
> > to ensure the futexes can be taken by other tasks.
> >
> > Though this can not work good in sometimes.
> > Think about this scene£º
> > 1. A robust mutex is shared for two processes, each process has
> >    multi threads to lock the mutex.
> > 2. One of the threads locks the mutex, and the others are waiting
> >    and sorted in order of priority.
> > 3. The process to which the mutex owner thread belongs is dying
> >    without unlocking the mutex£¬and handle_futex_death is invoked
> >    to wake the first waiter.
> > 4. If the first waiter belongs to the same process£¬it has no chance
> >    to return to the userspace to lock the mutex, and it won't wake
> >    the next waiter because it is not the owner of the mutex.
> > 5. The rest waiters of the other process may block forever.
> >
> > This patch remove the owner check when waking task in handle_futex_death.
> > If above occured, The dying task can wake the next waiter by processing its list_op_pending.
> > The waked task could return to userspace and try to lock the mutex again.
> >
>
> The problem is if you allow the non-owner to do the wake, you risk
> multiple threads calling futex_wake(). Or is that your intention? Wake
> one waiter for every thread that calls handle_futex_death()?

Yes.

> >
> > Signed-off-by: Zhang Yi <zhang.yi20@zte.com.cn>
> > Reviewed-by: Xie Baoyou <xie.baoyou@zte.com.cn>
> > Reviewed-by: Lu Zhongjun <lu.zhongjun@zte.com.cn>
> >
> >
> >
> > --- linux/kernel/futex.c   2013-09-25 09:24:34.639634244 +0000
> > +++ linux/kernel/futex.c   2013-09-25 10:12:17.619673546 +0000
> > @@ -2541,14 +2541,15 @@ retry:
> >        }
> >        if (nval != uval)
> >           goto retry;
> > -
> > -      /*
> > -       * Wake robust non-PI futexes here. The wakeup of
> > -       * PI futexes happens in exit_pi_state():
> > -       */
> > -      if (!pi && (uval & FUTEX_WAITERS))
> > -         futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
> >     }
> > +
> > +   /*
> > +    * Wake robust non-PI futexes here. The wakeup of
> > +    * PI futexes happens in exit_pi_state():
> > +    */
> > +   if (!pi)
>
>
> Why did you drop the FUTEX_WAITERS condition?
>
> You sent a different patch earlier this year that didn't appear to get
> any review:
>
> https://lkml.org/lkml/2013/4/8/65
>
> This one woke all the waiters and let them sort it out.
>
> It seems we've hashed through this already, but I'm not finding the
> email logs and I don't recall off the top of my head.
>
> > +      futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
> > +
> >     return 0;
> >  }
>

The earlier patch cannot solve another problem:
The owner wakes the next waiter through normal unlocking which make the
futex value as zero, the waked task exits before actually locking the mutex.
In this case, the owner doesn't call handle_futex_death() and the waked task
doesn't call futex_wake() when they are dying. The rest waiters will still
block as the same.

This is also the reason that I drop the owner and FUTEX_WAITERS check,
because the futex value can be zero at that time.

In normal case, the userspace code ensure that the owner of lock in robust-list
is current task, we may do redundant waking just for the  list_op_pending.
So I think the patch results in little negative effect.ÿôèº{.nÇ+‰·Ÿ®‰­†+%ŠËÿ±éݶ\x17¥Šwÿº{.nÇ+‰·¥Š{±þG«éÿŠ{ayº\x1dʇڙë,j\a­¢f£¢·hšïêÿ‘êçz_è®\x03(­éšŽŠÝ¢j"ú\x1a¶^[m§ÿÿ¾\a«þG«éÿ¢¸?™¨è­Ú&£ø§~á¶iO•æ¬z·švØ^\x14\x04\x1a¶^[m§ÿÿÃ\fÿ¶ìÿ¢¸?–I¥

Re: Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death

[Darren Hart]

On Fri, 2013-09-27 at 14:45 +0800, zhang.yi20@zte.com.cn wrote:
> 
> Darren Hart <dvhart@linux.intel.com> wrote on 2013/09/27 02:15:17:
> 
> 
> > Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death
> >
> > On Thu, 2013-09-26 at 09:09 +0800, zhang.yi20@zte.com.cn wrote:
> > > Hi all,
> > >
> > > Task processes all its owned robust futex when it is exiting,
> > > to ensure the futexes can be taken by other tasks.
> > >
> > > Though this can not work good in sometimes.
> > > Think about this scene：
> > > 1. A robust mutex is shared for two processes, each process has
> > >    multi threads to lock the mutex.
> > > 2. One of the threads locks the mutex, and the others are waiting
> > >    and sorted in order of priority.
> > > 3. The process to which the mutex owner thread belongs is dying
> > >    without unlocking the mutex，and handle_futex_death is invoked
> > >    to wake the first waiter.
> > > 4. If the first waiter belongs to the same process，it has no chance
> > >    to return to the userspace to lock the mutex, and it won't wake
> > >    the next waiter because it is not the owner of the mutex.
> > > 5. The rest waiters of the other process may block forever.
> > >
> > > This patch remove the owner check when waking task in handle_futex_death.
> > > If above occured, The dying task can wake the next waiter by processing its list_op_pending.
> > > The waked task could return to userspace and try to lock the mutex again.
> > >
> >
> > The problem is if you allow the non-owner to do the wake, you risk
> > multiple threads calling futex_wake(). Or is that your intention? Wake
> > one waiter for every thread that calls handle_futex_death()?
> 
> Yes.
> 
> > >
> > > Signed-off-by: Zhang Yi <zhang.yi20@zte.com.cn>
> > > Reviewed-by: Xie Baoyou <xie.baoyou@zte.com.cn>
> > > Reviewed-by: Lu Zhongjun <lu.zhongjun@zte.com.cn>
> > >
> > >
> > >
> > > --- linux/kernel/futex.c   2013-09-25 09:24:34.639634244 +0000
> > > +++ linux/kernel/futex.c   2013-09-25 10:12:17.619673546 +0000
> > > @@ -2541,14 +2541,15 @@ retry:
> > >        }
> > >        if (nval != uval)
> > >           goto retry;
> > > -
> > > -      /*
> > > -       * Wake robust non-PI futexes here. The wakeup of
> > > -       * PI futexes happens in exit_pi_state():
> > > -       */
> > > -      if (!pi && (uval & FUTEX_WAITERS))
> > > -         futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
> > >     }
> > > +
> > > +   /*
> > > +    * Wake robust non-PI futexes here. The wakeup of
> > > +    * PI futexes happens in exit_pi_state():
> > > +    */
> > > +   if (!pi)
> >
> >
> > Why did you drop the FUTEX_WAITERS condition?
> >
> > You sent a different patch earlier this year that didn't appear to get
> > any review:
> >
> > https://lkml.org/lkml/2013/4/8/65
> >
> > This one woke all the waiters and let them sort it out.
> >
> > It seems we've hashed through this already, but I'm not finding the
> > email logs and I don't recall off the top of my head.
> >
> > > +      futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
> > > +
> > >     return 0;
> > >  }
> >
> 
> The earlier patch cannot solve another problem:
> The owner wakes the next waiter through normal unlocking which make the
> futex value as zero, the waked task exits before actually locking the mutex.
> In this case, the owner doesn't call handle_futex_death() and the waked task
> doesn't call futex_wake() when they are dying. The rest waiters will still
> block as the same.
> 
> This is also the reason that I drop the owner and FUTEX_WAITERS check,
> because the futex value can be zero at that time.
> 

If the FUTEX_WAITERS bit is not set, there are no waiters, and thus no
need to wake. I understand why you dropped the OWNER check, but I'm not
following this one. Where would the futex word be set from having
waiters to zero when there might still be waiters pending?


-- 
Darren Hart
Intel Open Source Technology Center
Yocto Project - Linux Kernel

Re: Re: Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death

[zhang.yi20]

Darren Hart <dvhart@linux.intel.com> wrote on 2013/09/27 23:32:27:

>
> Re: Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death
>
> >
> > The earlier patch cannot solve another problem:
> > The owner wakes the next waiter through normal unlocking which make the
> > futex value as zero, the waked task exits before actually locking the mutex.
> > In this case, the owner doesn't call handle_futex_death() and the waked task
> > doesn't call futex_wake() when they are dying. The rest waiters will still
> > block as the same.
> >
> > This is also the reason that I drop the owner and FUTEX_WAITERS check,
> > because the futex value can be zero at that time.
> >
>
> If the FUTEX_WAITERS bit is not set, there are no waiters, and thus no
> need to wake. I understand why you dropped the OWNER check, but I'm not
> following this one. Where would the futex word be set from having
> waiters to zero when there might still be waiters pending?
>
>
> --
> Darren Hart
> Intel Open Source Technology Center
> Yocto Project - Linux Kernel
>
>

I have drawn a diagram as below:

               process1                     |      process2
   -------------------------------------------------------------
  |       thread1       |      thread2      |      thread3
   -------------------------------------------------------------
t1|pthread_mutex_lock:  |                   |
  |  __lock=self        |                   |
  |                     |                   |
t2|                     |pthread_mutex_lock:|
  |                     |__lock|=FUTEX_WAITERS
  |                     | syscall futex_wait|
  |                     |                   |
t3|                     |                   |pthrea_mutex_lock:
  |                     |                   |__lock|=FUTEX_WAITERS
  |                     |                   | syscall futex_wait
  |                     |                   |
t4|pthread_mutex_unlock:|                   |
  |  __lock=0           |                   |
  |  syscall futex_wake | waked             |
  |                     |                   |
t5| exit                |exit:              |
  |                     | handle_futex_death|
---------------------------------------------------------------
t6|                     |pthread_mutex_lock:|
  |                     |__lock=self|FUTEX_WAITERS


1, At time t4, in the unlocking process of glibc, it clears the FUTEX_WAITERS bit before
calling futex_wake syscall.

2, At time t5, thread2 cannot know if the FUTEX_WAITERS bit was set.

3, Time t6 is expected but can never be true.

Re: Re: Re: Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death

[zhang.yi20]

Zhang Yi <zhang.yi20@zte.com.cn> wrote on 2013/10/08 13:59:36:

> Re: Re: Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death
>
> Darren Hart <dvhart@linux.intel.com> wrote on 2013/09/27 23:32:27:

> >
> > Re: Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death
> >
> > >
> > > The earlier patch cannot solve another problem:
> > > The owner wakes the next waiter through normal unlocking which make the
> > > futex value as zero, the waked task exits before actually locking the mutex.
> > > In this case, the owner doesn't call handle_futex_death() and the waked task
> > > doesn't call futex_wake() when they are dying. The rest waiters will still
> > > block as the same.
> > >
> > > This is also the reason that I drop the owner and FUTEX_WAITERS check,
> > > because the futex value can be zero at that time.
> > >
> >
> > If the FUTEX_WAITERS bit is not set, there are no waiters, and thus no
> > need to wake. I understand why you dropped the OWNER check, but I'm not
> > following this one. Where would the futex word be set from having
> > waiters to zero when there might still be waiters pending?
> >
> >
> > --
> > Darren Hart
> > Intel Open Source Technology Center
> > Yocto Project - Linux Kernel
> >
> >

> I have drawn a diagram as below:
>
>                process1                     |      process2
>    -------------------------------------------------------------
>   |       thread1       |      thread2      |      thread3
>    -------------------------------------------------------------
> t1|pthread_mutex_lock:  |                   |
>   |  __lock=self        |                   |
>   |                     |                   |
> t2|                     |pthread_mutex_lock:|
>   |                     |__lock|=FUTEX_WAITERS
>   |                     | syscall futex_wait|
>   |                     |                   |
> t3|                     |                   |pthrea_mutex_lock:
>   |                     |                   |__lock|=FUTEX_WAITERS
>   |                     |                   | syscall futex_wait
>   |                     |                   |
> t4|pthread_mutex_unlock:|                   |
>   |  __lock=0           |                   |
>   |  syscall futex_wake | waked             |
>   |                     |                   |
> t5| exit                |exit:              |
>   |                     | handle_futex_death|
> ---------------------------------------------------------------
> t6|                     |pthread_mutex_lock:|
>   |                     |__lock=self|FUTEX_WAITERS
>
> 1, At time t4, in the unlocking process of glibc, it clears the FUTEX_WAITERS bit before
> calling futex_wake syscall.
>
> 2, At time t5, thread2 cannot know if the FUTEX_WAITERS bit was set.
>
> 3, Time t6 is expected but can never be true.

Are there any questions?

Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death

[Thomas Gleixner]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1647 bytes --]

On Thu, 26 Sep 2013, zhang.yi20@zte.com.cn wrote:
> Task processes all its owned robust futex when it is exiting,
> to ensure the futexes can be taken by other tasks.
> 
> Though this can not work good in sometimes.
> Think about this scene：
> 1. A robust mutex is shared for two processes, each process has
>    multi threads to lock the mutex.
> 2. One of the threads locks the mutex, and the others are waiting
>    and sorted in order of priority.
> 3. The process to which the mutex owner thread belongs is dying
>    without unlocking the mutex，and handle_futex_death is invoked
>    to wake the first waiter.
> 4. If the first waiter belongs to the same process，it has no chance
>    to return to the userspace to lock the mutex, and it won't wake
>    the next waiter because it is not the owner of the mutex.
> 5. The rest waiters of the other process may block forever.

Fair enough.
 
> This patch remove the owner check when waking task in handle_futex_death.
> If above occured, The dying task can wake the next waiter by processing its list_op_pending.
> The waked task could return to userspace and try to lock the mutex again.
> 

The owner check needs to stay. The robust list is a user space managed
list on which the kernel operates. We do not trust it at all and we
really want as many sanity checks as possible and definitely not
removing one.

The simplest solution is just to wake all waiters and let them sort it
out. We could do a more complex one by checking whether this is a
group exit and not wake any threads belonging to the same process, but
that's not really worth the trouble.

Thanks,

	tglx

Re: [PATCH] futex: Remove the owner check when waking task in handle_futex_death

[Darren Hart]

On Thu, 2013-10-24 at 14:47 +0200, Thomas Gleixner wrote:
> On Thu, 26 Sep 2013, zhang.yi20@zte.com.cn wrote:
> > Task processes all its owned robust futex when it is exiting,
> > to ensure the futexes can be taken by other tasks.
> > 
> > Though this can not work good in sometimes.
> > Think about this scene：
> > 1. A robust mutex is shared for two processes, each process has
> >    multi threads to lock the mutex.
> > 2. One of the threads locks the mutex, and the others are waiting
> >    and sorted in order of priority.
> > 3. The process to which the mutex owner thread belongs is dying
> >    without unlocking the mutex，and handle_futex_death is invoked
> >    to wake the first waiter.
> > 4. If the first waiter belongs to the same process，it has no chance
> >    to return to the userspace to lock the mutex, and it won't wake
> >    the next waiter because it is not the owner of the mutex.
> > 5. The rest waiters of the other process may block forever.
> 
> Fair enough.
>  
> > This patch remove the owner check when waking task in handle_futex_death.
> > If above occured, The dying task can wake the next waiter by processing its list_op_pending.
> > The waked task could return to userspace and try to lock the mutex again.
> > 
> 
> The owner check needs to stay. The robust list is a user space managed
> list on which the kernel operates. We do not trust it at all and we
> really want as many sanity checks as possible and definitely not
> removing one.
> 
> The simplest solution is just to wake all waiters and let them sort it
> out. We could do a more complex one by checking whether this is a
> group exit and not wake any threads belonging to the same process, but
> that's not really worth the trouble.
> 

I think given that this is the error path, that waking everything is a
reasonable approach to addressing the problem. I haven't been able to
step through the failure case as carefully as I've wanted to, but it
appears sound just reading through it.

--
Darren

> Thanks,
> 
>         tglx

-- 
Darren Hart
Intel Open Source Technology Center
Yocto Project - Linux Kernel