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 <[email protected]>
Reviewed-by: Xie Baoyou <[email protected]>
Reviewed-by: Lu Zhongjun <[email protected]>
--- 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?+???????+%?????ݶ??w??{.n?+????{??G?????{ay? ʇڙ?,j??f???h?????????z_??(?階?ݢj"???m??????G????????????&???~???iO???z??v?^?m???? ????????I?
On Thu, 2013-09-26 at 09:09 +0800, [email protected] 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 <[email protected]>
> Reviewed-by: Xie Baoyou <[email protected]>
> Reviewed-by: Lu Zhongjun <[email protected]>
>
>
>
> --- 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
Darren Hart <[email protected]> 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, [email protected] 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 <[email protected]>
> > Reviewed-by: Xie Baoyou <[email protected]>
> > Reviewed-by: Lu Zhongjun <[email protected]>
> >
> >
> >
> > --- 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?+???????+%?????ݶ??w??{.n?+????{??G?????{ay? ʇڙ?,j??f???h?????????z_??(?階?ݢj"???m??????G????????????&???~???iO???z??v?^?m???? ????????I?
On Fri, 2013-09-27 at 14:45 +0800, [email protected] wrote:
>
> Darren Hart <[email protected]> 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, [email protected] 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 <[email protected]>
> > > Reviewed-by: Xie Baoyou <[email protected]>
> > > Reviewed-by: Lu Zhongjun <[email protected]>
> > >
> > >
> > >
> > > --- 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
Darren Hart <[email protected]> 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.
Zhang Yi <[email protected]> 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 <[email protected]> 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?
On Thu, 26 Sep 2013, [email protected] 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$B!'(J
> 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$B!$(Jand handle_futex_death is invoked
> to wake the first waiter.
> 4. If the first waiter belongs to the same process$B!$(Jit 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
On Thu, 2013-10-24 at 14:47 +0200, Thomas Gleixner wrote:
> On Thu, 26 Sep 2013, [email protected] 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