Skip to contentSkip to conversation

second, bigger problem with private futexes

DISCUSSION Ulrich Drepper 2 participants 7 messages May 21, 2007

lore
Share & tools
lore
#0 lore raw

-----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-----

#1 lore raw
Quoted 9 lines · 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.

Quoted 8 lines

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 :(

Quoted 6 lines

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.

#2 lore raw

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

Quoted 2 lines · Eric Dumazet

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-----

#3 lore raw
Quoted 9 lines · Ulrich Drepper

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

Quoted 2 lines · Eric Dumazet

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.

Quoted 3 lines

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

#4 lore raw
Quoted 21 lines · Eric Dumazet
Quoted 9 lines · Ulrich Drepper

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

Quoted 2 lines · Eric Dumazet

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.

Quoted 3 lines

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 ?

Quoted 9 lines

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

#5 lore raw

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

Quoted 4 lines · Eric Dumazet

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.

Quoted 3 lines

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-----

#6 lore raw
Quoted 15 lines · Ulrich Drepper

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

Quoted 4 lines · Eric Dumazet

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.

Quoted 5 lines
Quoted 3 lines

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.

Quoted 9 lines

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