Futexes are broken

[Jakub Jermář]

Tomas Brambora wrote:

Consider the following scenario:
Threads A, B. missed_wakeups == 0 && futex_counter == -1; A in crit.
sec., B sleeping on the futex with timeout.
1) A leaves crit. section ⇒ calls futex_wakeup and changes futex_counter to 0;
2) B times out and is removed from the waitq, but gets preempted
before returning to userspace.
3) A find empty waitq and increments the missed_wakeup count.
4) A returns to userspace and before getting preempted calls futex_down.
5) futex_counter == 0 ⇒ A decrements it to -1 and calls futex_sleep.
Return ESYNCH_OK_ATOMIC because missed_wakeups ==1 ⇒ calls
futex_sleep again and gets blocked there. Now futex_counter == -1 and
missed_wakeups == 0.
6) B is scheduled, returns to userspace with ESYNCH_TIMEOUT and
increments futex_counter.

So we have futex_counter == 0 and missed_wakeups == 0. While there is
NO THREAD in the critical section (A is sleeping on the futex, B has
timed out while sleeping).

Ergo, it is broken.

[Jakub Jermář]

Fixed in changeset:head,160.

This changeset replaces the original incorrect futex implementation with a simplified one, which, I believe, is correct.