second, bigger problem with private futexes

second, bigger problem with private futexes

[Ulrich Drepper]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This one is a big problem:

If I understand the code correctly, a FUTEX_CMP_REQUEUE from a private
futex will add the waiters to the other futex as a private futex.  And
similarly for shared.

I.e., it is not possible to have one futex private and the other shared.
 This is a huge problem.  The shared/private status of a conditional
variable and the mutex used with it don't have to match.  But this is
where FUTEX_CMP_REQUEUE is used.

If this is not changed (assuming I'm right with my analysis of the
kernel code) this means mutexes and condvars will not be able to use
private futexes.

What would be needed is an additional parameter for FUTEX_CMP_REQUEUE
and FUTEX_CMP_REQUEUE_PI which specifies the state (shared/private) of
the target futex.  The original futex' state is encoded in the command
(the FUTEX_PRIVATE_FLAG ORed to FUTEX_CMP_REQUEUE*).

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iD8DBQFGUdYo2ijCOnn/RHQRArmXAKCdW9a/nuJun/0KjftIcMrsURNnrwCgzCf8
XGi6EzPV88DEIwHfnMfKdNg=
=0hVr
-----END PGP SIGNATURE-----

Re: second, bigger problem with private futexes

[Eric Dumazet]

Ulrich Drepper a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> This one is a big problem:
> 
> If I understand the code correctly, a FUTEX_CMP_REQUEUE from a private
> futex will add the waiters to the other futex as a private futex.  And
> similarly for shared.
> 
> I.e., it is not possible to have one futex private and the other shared.
>  This is a huge problem.  The shared/private status of a conditional
> variable and the mutex used with it don't have to match.  But this is
> where FUTEX_CMP_REQUEUE is used.
> 
> If this is not changed (assuming I'm right with my analysis of the
> kernel code) this means mutexes and condvars will not be able to use
> private futexes.

Do you mean POSIX allowed to mix PROCESS_PRIVATE and PROCESS_SHARED condvar 
and mutexes ? Seems silly to me :(

> 
> What would be needed is an additional parameter for FUTEX_CMP_REQUEUE
> and FUTEX_CMP_REQUEUE_PI which specifies the state (shared/private) of
> the target futex.  The original futex' state is encoded in the command
> (the FUTEX_PRIVATE_FLAG ORed to FUTEX_CMP_REQUEUE*).
> 

Well, I guess it should be easy to add this if really necessary.

Re: second, bigger problem with private futexes

[Ulrich Drepper]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Eric Dumazet wrote:
> Do you mean POSIX allowed to mix PROCESS_PRIVATE and PROCESS_SHARED
> condvar and mutexes ? Seems silly to me :(

Don't judge what you don't understand.  If all waiters are always in one
process but the notifiers can be in different processes, this setup
might make a lot of sense.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iD8DBQFGUeRK2ijCOnn/RHQRAqRuAKCpc7cmhsnwfclz1DU81RNXRjm68ACgosZc
RqWca4r+Ya54dp5zNztkYuk=
=sW/1
-----END PGP SIGNATURE-----

Re: second, bigger problem with private futexes

[Eric Dumazet]

Ulrich Drepper a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Eric Dumazet wrote:
>> Do you mean POSIX allowed to mix PROCESS_PRIVATE and PROCESS_SHARED
>> condvar and mutexes ? Seems silly to me :(
> 

> Don't judge what you don't understand.

Yes, I kindly apologise for this crime.

 > If all waiters are always in one
> process but the notifiers can be in different processes, this setup
> might make a lot of sense.

Thanks for providing this information.

I assume in this case the condvar is PSHARED, while mutex could be/is PRIVATE ?

I wonder how old (assuming all shared) code could work, since the notifier 
would call FUTEX_CMP_REQUEUE giving a target address outside of this process vm ?

My understanding (probably bad, since I know nothing about POSIX as you mentioned)

- Old code could not use FUTEX_CMP_REQUEUE if mutex was private.
-> Old code was using a normal FUTEX_WAKE in this case.

So I repeat my question : Should we really add yer another futex command in 
kernel for a corner case ?

Thanks

Re: second, bigger problem with private futexes

[Eric Dumazet]

Eric Dumazet a écrit :
> Ulrich Drepper a écrit :
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Eric Dumazet wrote:
>>> Do you mean POSIX allowed to mix PROCESS_PRIVATE and PROCESS_SHARED
>>> condvar and mutexes ? Seems silly to me :(
>>
> 
>> Don't judge what you don't understand.
> 
> Yes, I kindly apologise for this crime.
> 
>  > If all waiters are always in one
>> process but the notifiers can be in different processes, this setup
>> might make a lot of sense.
> 
> Thanks for providing this information.
> 
> I assume in this case the condvar is PSHARED, while mutex could be/is 
> PRIVATE ?
> 
> I wonder how old (assuming all shared) code could work, since the 
> notifier would call FUTEX_CMP_REQUEUE giving a target address outside of 
> this process vm ?
> 
> My understanding (probably bad, since I know nothing about POSIX as you 
> mentioned)
> 
> - Old code could not use FUTEX_CMP_REQUEUE if mutex was private.
> -> Old code was using a normal FUTEX_WAKE in this case.
> 
> So I repeat my question : Should we really add yer another futex command 
> in kernel for a corner case ?
> 

Reading this I realize it's confusing... :(

Because a process issuing a futex() syscall cannot point to another process vm 
(without giving more information than just a virtual address), I do think :

1) pthread_cond_broadcast() SHOULD use FUTEX_CMP_REQUEUE if :

condvar & mutex are PSHARED

2) pthread_cond_broadcast() MUST use FUTEX_CMP_REQUEUE_PRIVATE if :

condvar & mutex are PRIVATE

3) if condvar is PRIVATE and mutex is SHARED, a FUTEX_WAKE_PRIVATE should be 
done. (and loose the REQUEUE optim)
Yes we could add a special futex primitive for this special case. But I cannot 
see how a program could use such a construct.

4) if condvar is SHARED and mutex is private, we have a *problem*, because the 
process doing the broadcast() can be in another mm. So a requeue is not 
possible at all. -> a FUTEX_WAKE is necessary (no REQUEUE optim)
I guess it's OK performance wise since the notifier in this case probably 
doesnt hold a lock on the mutex. And probably old glibc was doing same thing, 
since the mutex address stored in condvar was possibly in another vm, and 
notifier had the same problem.


Thanks

Re: second, bigger problem with private futexes

[Ulrich Drepper]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Eric Dumazet wrote:
> 3) if condvar is PRIVATE and mutex is SHARED, a FUTEX_WAKE_PRIVATE
> should be done. (and loose the REQUEUE optim)
> Yes we could add a special futex primitive for this special case. But I
> cannot see how a program could use such a construct.

Very easily: mutexes are often created independently from the condvars
and they are used for many things.  Maybe a program is even creating all
mutexes as shared to be ready for all situations.  Normally doing this
is no big problem, the performance penalties are minimal.


> 4) if condvar is SHARED and mutex is private, we have a *problem*,
> because the process doing the broadcast() can be in another mm. So a
> requeue is not possible at all.

It is if we can specify the owner of the mutex.  I.e., the PID.

But yes, this case is extremely ugly.


The problem is that all these cases worked nice so far.  They all had
the same good performance.  Now we are severely penalizing code which
mismatches condvar and mutex shared attributes.  There is a good reason
why we introduced FUTEX_CMP_REQUEUE, the benefits in certain programs is
huge.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iD8DBQFGUfZT2ijCOnn/RHQRAkT0AJ4pgX7RtdUf8uwyP9v7o+nkv/9uMACfbx6+
kBaJLSSvDBjN09KMgmLKnSI=
=4XMz
-----END PGP SIGNATURE-----

Re: second, bigger problem with private futexes

[Eric Dumazet]

Ulrich Drepper a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Eric Dumazet wrote:
>> 3) if condvar is PRIVATE and mutex is SHARED, a FUTEX_WAKE_PRIVATE
>> should be done. (and loose the REQUEUE optim)
>> Yes we could add a special futex primitive for this special case. But I
>> cannot see how a program could use such a construct.
> 
> Very easily: mutexes are often created independently from the condvars
> and they are used for many things.  Maybe a program is even creating all
> mutexes as shared to be ready for all situations.  Normally doing this
> is no big problem, the performance penalties are minimal.
> 
> 
>> 4) if condvar is SHARED and mutex is private, we have a *problem*,
>> because the process doing the broadcast() can be in another mm. So a
>> requeue is not possible at all.
> 
> It is if we can specify the owner of the mutex.  I.e., the PID.

well, then we have a refcounting issue on pid , or problem in pid reuse.

> 
> But yes, this case is extremely ugly.
> 
> 
> The problem is that all these cases worked nice so far.  They all had
> the same good performance.  Now we are severely penalizing code which
> mismatches condvar and mutex shared attributes.  There is a good reason
> why we introduced FUTEX_CMP_REQUEUE, the benefits in certain programs is
> huge.

This analysis seems unfair to me, after a quick reading of glibc code.

Right now, glibc cannot use FUTEX_CMP_REQUEUE if condvar is pshared.

/* Do not use requeue for pshared condvars.  */
if (cond->__data.__mutex == (void *) ~0l)
	goto wake_all;

So how introducing private futexes is penalizing this case ?

Fact is that if condvar is pshared, we *cannot* use CMP_REQUEUE since threads 
doing the broadcast() can be in a separate process and virtual address of 
mutex of waiting threads could point to unrelated memory.

Thanks