[PATCH] futex: bugfix for robust futex deadlock when waking only one thread in handle_futex_death

[PATCH] futex: bugfix for robust futex deadlock when waking only one thread in handle_futex_death

[zhang.yi20]

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

From: Zhang Yi <zhang.yi20@zte.com.cn>

Hello,

The function handle_futex_death just wakes one thread, which may be not 
enough when the owner process is dead. Think about this scene£º
1. A robust futex is shared for two processes, each process has multi 
threads try to get the lock. 
2. One of the threads gets the lock, and the others are waiting and sorted 

in order of priority.
3. The process to which the lock owner thread belongs is dying£¬and 
handle_futex_death is called to wake the first waiter 
4. When the first waiter belongs to the same process£¬it has no chance to 
return to the userspace to get the lock and will not call 
handle_futex_death any 
more£¬and then the rest threads of the other process will never be waked, 
and 
will block forever.

This patch wakes all the waiters when lock owner is in group-exit, letting 

all the waiters return to userspace and try to get the lock again.


Signed-off-by: Zhang Yi <zhang.yi20@zte.com.cn>
Tested-by: Ma Chenggong <ma.chenggong@zte.com.cn>
Reviewed-by: Liu Dong <liu.dong3@zte.com.cn>
Reviewed-by: Cui Yunfeng <cui.yunfeng@zte.com.cn>
Reviewed-by: Lu Zhongjun <lu.zhongjun@zte.com.cn>
Reviewed-by: Jiang Biao <jiang.biao2@zte.com.cn>


--- orig/linux-3.9-rc7/kernel/futex.c   2013-04-15 00:45:16.000000000 
+0000
+++ new/linux-3.9-rc7/kernel/futex.c    2013-04-16 10:17:46.264597000 
+0000
@@ -2545,8 +2545,11 @@ 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);
+               if (!pi && (uval & FUTEX_WAITERS)) {
+                       int nr = signal_group_exit(current->signal)
+                                           ? INT_MAX : 1;
+                       futex_wake(uaddr, 1, nr, 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: bugfix for robust futex deadlock when waking only one thread in handle_futex_death

[Darren Hart]

On 04/15/2013 08:02 PM, zhang.yi20@zte.com.cn wrote:
> From: Zhang Yi <zhang.yi20@zte.com.cn>
>
> Hello,

Hi Zhang,

I think you've attempted to address this with your second futex patch,
but please use plain text email on LKML, especially for patches. Ensure
to linewrap your plain text email and avoid mid-line breaks as it makes
the message very difficult to read.

(my mailer can't seem to be forced into replying in plain text mode for this
particular email, not sure what is special about this one).

> The function handle_futex_death just wakes one thread, which may be not
> enough when the owner process is dead. Think about this scene：
> 1. A robust futex is shared for two processes, each process has multi
> threads try to get the lock.
> 2. One of the threads gets the lock, and the others are waiting and sorted
> in order of priority.
> 3. The process to which the lock owner thread belongs is dying，and
> handle_futex_death is called to wake the first waiter
> 4. When the first waiter belongs to the same process，it has no chance to
> return to the userspace to get the lock and will not call
> handle_futex_death any
> more，and then the rest threads of the other process will never be waked,
> and
> will block forever.

A simple functional testcase of this would be really nice to add to
futextest:

https://git.kernel.org/cgit/linux/kernel/git/dvhart/futextest.git/

It would also be good for validating the fix and avoiding regressions.

>
> This patch wakes all the waiters when lock owner is in group-exit, letting
>
> all the waiters return to userspace and try to get the lock again.
>
>
> Signed-off-by: Zhang Yi <zhang.yi20@zte.com.cn>
> Tested-by: Ma Chenggong <ma.chenggong@zte.com.cn>
> Reviewed-by: Liu Dong <liu.dong3@zte.com.cn>
> Reviewed-by: Cui Yunfeng <cui.yunfeng@zte.com.cn>
> Reviewed-by: Lu Zhongjun <lu.zhongjun@zte.com.cn>
> Reviewed-by: Jiang Biao <jiang.biao2@zte.com.cn>
>
>
> --- orig/linux-3.9-rc7/kernel/futex.c   2013-04-15 00:45:16.000000000
> +0000
> +++ new/linux-3.9-rc7/kernel/futex.c    2013-04-16 10:17:46.264597000
> +0000
> @@ -2545,8 +2545,11 @@ 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);
> +               if (!pi && (uval & FUTEX_WAITERS)) {
> +                       int nr = signal_group_exit(current->signal)
> +                                           ? INT_MAX : 1;
> +                       futex_wake(uaddr, 1, nr, FUTEX_BITSET_MATCH_ANY);
> +               }
>         }
>         return 0;
>  }

Performance isn't an issue here as this is an error path. The question
is if the
changed behavior will constitute a problem for existing applications. Rather
than a serialized cascading wake, we have them all wake at once. If an
application depended on the first waker after owner death to do some cleanup
before the rest came along, I could imagine some potential for failure
there.

One possible alternative would be to wake waiters for a different
process group
when OWNER_DEAD is set, and leave it as a single wake.

Peter, Ingo - do you think there is any concern over the wake_all versus
wake_one? I suspect it should be fine, but we obviously need to be
careful when changing the behavior of syscalls.

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

Re: Re: [PATCH] futex: bugfix for robust futex deadlock when waking only one thread in handle_futex_death

[zhang.yi20]

Darren Hart <dvhart@linux.intel.com> wrote on 2013/04/17 01:05:28:


> 
> Performance isn't an issue here as this is an error path. The question
> is if the
> changed behavior will constitute a problem for existing applications. 
Rather
> than a serialized cascading wake, we have them all wake at once. If an
> application depended on the first waker after owner death to do some 
cleanup
> before the rest came along, I could imagine some potential for failure
> there.
> 

I don't find out there are any APIs can wake all waiters at once, so still 
use futex_wake.
When waiter return form futex_wait syscall, glibc check the futex's value 
and try to modify it by using atomic instructions, and let the waiter 
return only if successed.
The applications which not use the glibc's library should follow this.

> One possible alternative would be to wake waiters for a different
> process group
> when OWNER_DEAD is set, and leave it as a single wake.
> 

To wake one waiter of other process cannot slove this problem , because it 
can be exiting too.

Re: [PATCH] futex: bugfix for robust futex deadlock when waking only one thread in handle_futex_death

[Darren Hart]

On 04/17/2013 03:40 AM, zhang.yi20@zte.com.cn wrote:
> Darren Hart <dvhart@linux.intel.com> wrote on 2013/04/17 01:05:28:
> 
> 
>>
>> Performance isn't an issue here as this is an error path. The question
>> is if the
>> changed behavior will constitute a problem for existing applications. 
> Rather
>> than a serialized cascading wake, we have them all wake at once. If an
>> application depended on the first waker after owner death to do some 
> cleanup
>> before the rest came along, I could imagine some potential for failure
>> there.
>>
> 
> I don't find out there are any APIs can wake all waiters at once, so still 
> use futex_wake.
> When waiter return form futex_wait syscall, glibc check the futex's value 
> and try to modify it by using atomic instructions, and let the waiter 
> return only if successed.
> The applications which not use the glibc's library should follow this.

Indeed they *should*. :-)

> 
>> One possible alternative would be to wake waiters for a different
>> process group
>> when OWNER_DEAD is set, and leave it as a single wake.
>>
> 
> To wake one waiter of other process cannot slove this problem , because it 
> can be exiting too.

If I understood the point of your change, it was to ensure all tasks
would be woken because tasks that were exiting wouldn't propogate the
wake. If there are nothing but exiting tasks available.... does it even
matter?

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

Re: [PATCH] futex: bugfix for robust futex deadlock when waking only one thread in handle_futex_death

[Darren Hart]

On 04/17/2013 06:47 PM, zhang.yi20@zte.com.cn wrote:
> 
> 
> Darren Hart <dvhart@linux.intel.com> wrote on 2013/04/18 03:42:07:
> 
>> 
>> 
>> On 04/17/2013 03:40 AM, zhang.yi20@zte.com.cn wrote:
>> > Darren Hart <dvhart@linux.intel.com> wrote on 2013/04/17 01:05:28:
>> > 
>> > 
>> >>
>> >> Performance isn't an issue here as this is an error path. The question
>> >> is if the
>> >> changed behavior will constitute a problem for existing applications.
>> > Rather
>> >> than a serialized cascading wake, we have them all wake at once. If an
>> >> application depended on the first waker after owner death to do some
>> > cleanup
>> >> before the rest came along, I could imagine some potential for failure
>> >> there.
>> >>
>> > 
>> > I don't find out there are any APIs can wake all waiters at once, so still
>> > use futex_wake.
>> > When waiter return form futex_wait syscall, glibc check the futex's value
>> > and try to modify it by using atomic instructions, and let the waiter
>> > return only if successed.
>> > The applications which not use the glibc's library should follow this.
>> 
>> Indeed they *should*. :-)
>> 
>> > 
>> >> One possible alternative would be to wake waiters for a different
>> >> process group
>> >> when OWNER_DEAD is set, and leave it as a single wake.
>> >>
>> > 
>> > To wake one waiter of other process cannot slove this problem , because it
>> > can be exiting too.
>> 
>> If I understood the point of your change, it was to ensure all tasks
>> would be woken because tasks that were exiting wouldn't propogate the
>> wake. If there are nothing but exiting tasks available.... does it even
>> matter?
>> 
> 
> I mean that there may be some processes (more than 2) waitting for the
> lock, we can't choose the one which is exiting or it will exit later.
> It's difficult to accomplish this.
> 

"or it will exit later" .... I don't follow you there, it sounds like
you are saying if we try to wake the exiting process, that process will
be delayed and take longer to exit.... I don't think that is what you
meant. Can you elaborate please?

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

Re: Re: [PATCH] futex: bugfix for robust futex deadlock when waking only one thread in handle_futex_death

[zhang.yi20]

Darren Hart <dvhart@linux.intel.com> wrote on 2013/04/18 22:54:30:

> 
> "or it will exit later" .... I don't follow you there, it sounds like
> you are saying if we try to wake the exiting process, that process will
> be delayed and take longer to exit.... I don't think that is what you
> meant. Can you elaborate please?
> 

I want to describe this scene:
1, We wake one waiter of other process that is not exiting.
2, Before it returns from do_futex, another thread of the process 
  encounters an exception and leads to process exiting.
3, The waiter returns from do_futex, and handle exit signal first, 
  that it will not return to userspace any more.

So, to my way of thinking, to choose a suitable waiter is difficult.