What is the FUTEX_REQUEUE error?

Question

I assign the Linux FUTEX(2) man page as necessary, reading in the classes of operating systems, as a warning, so that students do not calm down when developing synchronization primitives.

The futex() system call is an API that Linux provides to allow user-level thread synchronization primitives to sleep and wake up when needed. The manual page describes 5 different operations that can be called using the futex() system call. The two main operations are FUTEX_WAIT (which uses the thread to sleep when it tries to get the synchronization object, and someone already holds it) and FUTEX_WAKE (which the thread uses to wake up any waiting threads when it releases the synchronization object.)

The following three operations include the start of the fun. The description of the man page is as follows:

 FUTEX_FD (present up to and including Linux 2.6.25) [...] Because it was inherently racy, FUTEX_FD has been removed from Linux 2.6.26 onward. 

In the Futexes Tricky document , Ulrich Draper, 2004 describes the state of the race (this is a potential missed awakening). But there is also:

 FUTEX_REQUEUE (since Linux 2.5.70) This operation was introduced in order to avoid a "thundering herd" effect when FUTEX_WAKE is used and all processes woken up need to acquire another futex. [...] FUTEX_CMP_REQUEUE (since Linux 2.6.7) There was a race in the intended use of FUTEX_REQUEUE, so FUTEX_CMP_REQUEUE was introduced. [...] 

What was the race at FUTEX_REQUEUE ? Ulrich paper does not even mention it (the article describes the futex_requeue() function, which is implemented using FUTEX_CMP_REQUEUE , but not the FUTEX_REQUEUE operation).

Answer 1

It seems that the race condition is related to the implementation of the mutex in glibc and their mismatch with futexes. FUTEX_CMP_REQUEUE apparently needed to support the more complex glibc mutexes:

They are much more complicated because they support many other functions, such as deadlock testing and recursive locking. In this regard, they have an internal lock that protects an additional condition. This additional lock means that they cannot use the FUTEX_REQUEUE multiplex function due to a possible race.

Source: http://locklessinc.com/articles/futex_cheat_sheet/