Next round: revised futex(2) man page for review

FUTEX_CLOCK_REALTIME (since Linux 2.6.28)
This option bit can be employed only with the
FUTEX_WAIT_BITSET and FUTEX_WAIT_REQUEUE_PI operations.

If this option is set, the kernel treats timeout as an absolute time based on CLOCK_REALTIME.

.\" FIXME XXX I added CLOCK_MONOTONIC below. Okay?
If this option is not set, the kernel treats timeout as relative time, measured against the CLOCK_MONOTONIC clock.

The operation specified in futex_op is one of the following:

FUTEX_WAIT (since Linux 2.6.0)
This operation tests that the value at the futex word pointed to by the address uaddr still contains the expected value val, and if so, then sleeps awaiting FUTEX_WAKE on the futex word. The load of the value of the futex word is an atomic memory access (i.e., using atomic machine instructions of the respective architec‐ ture). This load, the comparison with the expected value, and starting to sleep are performed atomically and totally ordered with respect to other futex operations on the same futex word. If the thread starts to sleep, it is consid‐ ered a waiter on this futex word. If the futex value does not match val, then the call fails immediately with the error EAGAIN.

The purpose of the comparison with the expected value is to prevent lost wake-ups: If another thread changed the value of the futex word after the calling thread decided to block based on the prior value, and if the other thread executed a FUTEX_WAKE operation (or similar wake-up) after the value change and before this FUTEX_WAIT operation, then the latter will observe the value change and will not start to sleep.

If the timeout argument is non-NULL, its contents specify a relative timeout for the wait, measured according to the
.\" FIXME XXX I added CLOCK_MONOTONIC below. Okay?

CLOCK_MONOTONIC clock. (This interval will be rounded up to the system clock granularity, and kernel scheduling delays mean that the blocking interval may overrun by a small amount.)

If timeout is NULL, the call blocks indef‐
initely.

The arguments uaddr2 and val3 are ignored.

FUTEX_WAKE (since Linux 2.6.0)
This operation wakes at most val of the waiters that are waiting (e.g., inside FUTEX_WAIT) on the futex word at the address uaddr. Most commonly, val is specified as either 1 (wake up a single waiter) or INT_MAX (wake up all wait‐
ers). No guarantee is provided about which waiters are
awoken (e.g., a waiter with a higher scheduling priority is not guaranteed to be awoken in preference to a waiter with a lower priority).

The arguments timeout, uaddr2, and val3 are ignored.

FUTEX_FD (from Linux 2.6.0 up to and including Linux 2.6.25)
This operation creates a file descriptor that is associ‐ ated with the futex at uaddr. The caller must close the returned file descriptor after use. When another process or thread performs a FUTEX_WAKE on the futex word, the
file descriptor indicates as being readable with
select(2), poll(2), and epoll(7)

The file descriptor can be used to obtain asynchronous
notifications: if val is nonzero, then when another process or thread executes a FUTEX_WAKE, the caller will receive the signal number that was passed in val.

The arguments timeout, uaddr2 and val3 are ignored.

.\" FIXME(Torvald) We never define "upped". Maybe just remove the
.\" following sentence?
To prevent race conditions, the caller should test if the futex has been upped after FUTEX_FD returns.

Because it was inherently racy, FUTEX_FD has been removed from Linux 2.6.26 onward.

FUTEX_REQUEUE (since Linux 2.6.0)
.\" FIXME(Torvald) Is there some indication that FUTEX_REQUEUE is broken

.\"     in general, or is this comment implicitly speaking about the
.\"     condvar (?) use case? If the latter we might want to weaken the
.\"     advice below a little.

.\" [Anyone else have input on this?]

Avoid using this operation. It is broken for its intended purpose. Use FUTEX_CMP_REQUEUE instead.

This operation performs the same task as
FUTEX_CMP_REQUEUE, except that no check is made using the value in val3. (The argument val3 is ignored.)

FUTEX_CMP_REQUEUE (since Linux 2.6.7)
This operation first checks whether the location uaddr
still contains the value val3. If not, the operation
fails with the error EAGAIN. Otherwise, the operation wakes up a maximum of val waiters that are waiting on the futex at uaddr. If there are more than val waiters, then the remaining waiters are removed from the wait queue of the source futex at uaddr and added to the wait queue of the target futex at uaddr2. The val2 argument specifies an upper limit on the number of waiters that are requeued to the futex at uaddr2.

.\" FIXME(Torvald) Is the following correct? Or is just the decision .\" which threads to wake or requeue part of the atomic operation?

The load from uaddr is an atomic memory access (i.e., using atomic machine instructions of the respective archi‐ tecture). This load, the comparison with val3, and the requeueing of any waiters are performed atomically and totally ordered with respect to other operations on the same futex word.

This operation was added as a replacement for the earlier FUTEX_REQUEUE. The difference is that the check of the value at uaddr can be used to ensure that requeueing hap‐ pens only under certain conditions. Both operations can
be used to avoid a "thundering herd" effect when
FUTEX_WAKE is used and all of the waiters that are woken need to acquire another futex.

.\" FIXME Please review the following new paragraph to see if it is
.\" accurate.
Typical values to specify for val are 0 or or 1. (Speci‐ fying INT_MAX is not useful, because it would make the FUTEX_CMP_REQUEUE operation equivalent to FUTEX_WAKE.) The limit value specified via val2 is typically either 1 or INT_MAX. (Specifying the argument as 0 is not useful, because it would make the FUTEX_CMP_REQUEUE operation equivalent to FUTEX_WAIT.)

.\" FIXME Here, it would be helpful to have an example of how
.\" FUTEX_CMP_REQUEUE might be used, at the same time illustrating
.\" why FUTEX_WAKE is unsuitable for the same use case.

       FUTEX_WAKE_OP (since Linux 2.6.14)

.\" FIXME I added a lengthy piece of text on FUTEX_WAKE_OP text,
.\" and I'd be happy if someone checked it.
.\"
.\" FIXME(Torvald) The glibc condvar implementation is currently being
.\" revised (e.g., to not use an internal lock anymore).
.\" It is probably more future-proof to remove this paragraph.
.\" [Torvald, do you have an update here?]
.\"
This operation was added to support some user-space use cases where more than one futex must be handled at the same time. The most notable example is the implementation of pthread_cond_signal(3), which requires operations on two futexes, the one used to implement the mutex and the one used in the implementation of the wait queue associ‐ ated with the condition variable. FUTEX_WAKE_OP allows such cases to be implemented without leading to high rates of contention and context switching.

The FUTEX_WAIT_OP operation is equivalent to executing the following code atomically and totally ordered with respect to other futex operations on any of the two supplied futex words:

int oldval = *(int *) uaddr2;
*(int *) uaddr2 = oldval op oparg; futex(uaddr, FUTEX_WAKE, val, 0, 0, 0); if (oldval cmp cmparg)
futex(uaddr2, FUTEX_WAKE, val2, 0, 0, 0);

In other words, FUTEX_WAIT_OP does the following:

* saves the original value of the futex word at uaddr2 and performs an operation to modify the value of the futex at uaddr2; this is an atomic read-modify-write memory access (i.e., using atomic machine instructions of the respective architecture)

* wakes up a maximum of val waiters on the futex for the futex word at uaddr; and

* dependent on the results of a test of the original value of the futex word at uaddr2, wakes up a maximum of val2 waiters on the futex for the futex word at uaddr2.

The operation and comparison that are to be performed are encoded in the bits of the argument val3. Pictorially, the encoding is:

+---+---+-----------+-----------+
|op |cmp| oparg | cmparg |
+---+---+-----------+-----------+
4 4 12 12 <== # of bits

Expressed in code, the encoding is:

#define FUTEX_OP(op, oparg, cmp, cmparg) \
(((op & 0xf) << 28) | \
((cmp & 0xf) << 24) | \
((oparg & 0xfff) << 12) | \
(cmparg & 0xfff))

In the above, op and cmp are each one of the codes listed
below. The oparg and cmparg components are literal
numeric values, except as noted below.

The op component has one of the following values:

FUTEX_OP_SET 0 /* uaddr2 = oparg; */
FUTEX_OP_ADD 1 /* uaddr2 += oparg; */
FUTEX_OP_OR 2 /* uaddr2 |= oparg; */
FUTEX_OP_ANDN 3 /* uaddr2 &= ~oparg; */
FUTEX_OP_XOR 4 /* uaddr2 ^= oparg; */

In addition, bit-wise ORing the following value into op causes (1 << oparg) to be used as the operand:

FUTEX_OP_ARG_SHIFT 8 /* Use (1 << oparg) as operand */

The cmp field is one of the following:

FUTEX_OP_CMP_EQ 0 /* if (oldval == cmparg) wake */
FUTEX_OP_CMP_NE 1 /* if (oldval != cmparg) wake */
FUTEX_OP_CMP_LT 2 /* if (oldval < cmparg) wake */
FUTEX_OP_CMP_LE 3 /* if (oldval <= cmparg) wake */
FUTEX_OP_CMP_GT 4 /* if (oldval > cmparg) wake */
FUTEX_OP_CMP_GE 5 /* if (oldval >= cmparg) wake */

The return value of FUTEX_WAKE_OP is the sum of the number of waiters woken on the futex uaddr plus the number of waiters woken on the futex uaddr2.

FUTEX_WAIT_BITSET (since Linux 2.6.25)
This operation is like FUTEX_WAIT except that val3 is used to provide a 32-bit bitset to the kernel. This bitset is stored in the kernel-internal state of the waiter. See the description of FUTEX_WAKE_BITSET for further details.

The FUTEX_WAIT_BITSET operation also interprets the time‐ out argument differently from FUTEX_WAIT. See the discus‐ sion of FUTEX_CLOCK_REALTIME, above.

The uaddr2 argument is ignored.

FUTEX_WAKE_BITSET (since Linux 2.6.25)
This operation is the same as FUTEX_WAKE except that the val3 argument is used to provide a 32-bit bitset to the kernel. This bitset is used to select which waiters should be woken up. The selection is done by a bit-wise AND of the "wake" bitset (i.e., the value in val3) and the bitset which is stored in the kernel-internal state of the
waiter (the "wait" bitset that is set using
FUTEX_WAIT_BITSET). All of the waiters for which the
result of the AND is nonzero are woken up; the remaining waiters are left sleeping.

.\" FIXME XXX Is this next paragraph that I added okay?
The effect of FUTEX_WAIT_BITSET and FUTEX_WAKE_BITSET is to allow selective wake-ups among multiple waiters that are blocked on the same futex. Note, however, that using this bitset multiplexing feature on a futex is less effi‐ cient than simply using multiple futexes, because employ‐

ing bitset multiplexing requires the kernel to check all waiters on a futex, including those that are not inter‐ ested in being woken up (i.e., they do not have the rele‐ vant bit set in their "wait" bitset).

The uaddr2 and timeout arguments are ignored.

The FUTEX_WAIT and FUTEX_WAKE operations correspond to FUTEX_WAIT_BITSET and FUTEX_WAKE_BITSET operations where the bitsets are all ones.

Priority-inheritance futexes
Linux supports priority-inheritance (PI) futexes in order to han‐ dle priority-inversion problems that can be encountered with nor‐ mal futex locks. Priority inversion is the problem that occurs when a high-priority task is blocked waiting to acquire a lock held by a low-priority task, while tasks at an intermediate pri‐ ority continuously preempt the low-priority task from the CPU. Consequently, the low-priority task makes no progress toward releasing the lock, and the high-priority task remains blocked.

Priority inheritance is a mechanism for dealing with the prior‐ ity-inversion problem. With this mechanism, when a high-priority task becomes blocked by a lock held by a low-priority task, the latter's priority is temporarily raised to that of the former, so that it is not preempted by any intermediate level tasks, and can thus make progress toward releasing the lock. To be effective, priority inheritance must be transitive, meaning that if a high- priority task blocks on a lock held by a lower-priority task that is itself blocked by lock held by another intermediate-priority task (and so on, for chains of arbitrary length), then both of those task (or more generally, all of the tasks in a lock chain) have their priorities raised to be the same as the high-priority task.

.\" FIXME XXX The following is my attempt at a definition of PI futexes,
.\" based on mail discussions with Darren Hart. Does it seem okay?

From a user-space perspective, what makes a futex PI-aware is a policy agreement between user space and the kernel about the value of the futex word (described in a moment), coupled with the use of the PI futex operations described below (in particular, FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, and FUTEX_CMP_REQUEUE_PI).

.\" FIXME XXX ===== Start of adapted Hart/Guniguntala text =====

.\"       The following text is drawn from the Hart/Guniguntala paper
.\"       (listed in SEE ALSO), but I have reworded some pieces
.\"       significantly. Please check it.

The PI futex operations described below differ from the other futex operations in that they impose policy on the use of the value of the futex word:

* If the lock is not acquired, the futex word's value shall be 0.

* If the lock is acquired, the futex word's value shall be the thread ID (TID; see gettid(2)) of the owning thread.

* If the lock is owned and there are threads contending for the lock, then the FUTEX_WAITERS bit shall be set in the futex word's value; in other words, this value is:

FUTEX_WAITERS | TID

Note that a PI futex word never just has the value FUTEX_WAITERS, which is a permissible state for non-PI futexes.

With this policy in place, a user-space application can acquire a not-acquired lock or release a lock that no other threads try to acquire using atomic instructions executed in user space (e.g., a compare-and-swap operation such as cmpxchg on the x86 architec‐
ture). Acquiring a lock simply consists of using compare-and-
swap to atomically set the futex word's value to the caller's TID if its previous value was 0. Releasing a lock requires using compare-and-swap to set the futex word's value to 0 if the previ‐ ous value was the expected TID.

If a futex is already acquired (i.e., has a nonzero value), wait‐ ers must employ the FUTEX_LOCK_PI operation to acquire the lock. If other threads are waiting for the lock, then the FUTEX_WAITERS bit is set in the futex value; in this case, the lock owner must employ the FUTEX_UNLOCK_PI operation to release the lock.

In the cases where callers are forced into the kernel (i.e., required to perform a futex() call), they then deal directly with a so-called RT-mutex, a kernel locking mechanism which implements the required priority-inheritance semantics. After the RT-mutex is acquired, the futex value is updated accordingly, before the calling thread returns to user space.
.\" FIXME ===== End of adapted Hart/Guniguntala text =====

.\" FIXME We need some explanation in the following paragraph of *why*
.\" it is important to note that "the kernel will update the
.\" futex word's value prior
It is important to note to returning to user space" . Can someone
explain? that the kernel will update the futex word's value
prior to returning to user space. Unlike the other futex opera‐ tions described above, the PI futex operations are designed for the implementation of very specific IPC mechanisms.

.\"
.\" FIXME XXX In discussing errors for FUTEX_CMP_REQUEUE_PI, Darren Hart

.\"       made the observation that "EINVAL is returned if the non-pi 
.\"       to pi or op pairing semantics are violated."
.\"       Probably there needs to be a general statement about this
.\"       requirement, probably located at about this point in the page.
.\"       Darren (or someone else), care to take a shot at this?

.\" FIXME Somewhere on this page (I guess under the discussion of PI
.\" futexes) we need a discussion of the FUTEX_OWNER_DIED bit.
.\" Can someone propose a text?

PI futexes are operated on by specifying one of the following values in futex_op:

FUTEX_LOCK_PI (since Linux 2.6.18)
.\" FIXME I did some significant rewording of tglx's text to create

.\"       the text below.
.\"       Please check the following paragraph, in case I injected
.\"       errors.

This operation is used after after an attempt to acquire the lock via an atomic user-space instruction failed because the futex word has a nonzero value—specifically, because it contained the namespace-specific TID of the lock owner.
.\" FIXME In the preceding line, what does "namespace-specific" mean?

.\"       (I kept those words from tglx.)
.\"       That is, what kind of namespace are we talking about?
.\"       (I suppose we are talking PID namespaces here, but I want to
.\"       be sure.)

The operation checks the value of the futex word at the address uaddr. If the value is 0, then the kernel tries to atomically set the futex value to the caller's TID.
.\" FIXME What would be the cause(s) of failure referred to
.\" in the following sentence?
If
that fails, or the futex word's value is nonzero, the ker‐

nel atomically sets the FUTEX_WAITERS bit, which signals the futex owner that it cannot unlock the futex in user space atomically by setting the futex value to 0. After that, the kernel tries to find the thread which is associ‐ ated with the owner TID, creates or reuses kernel state on behalf of the owner and attaches the waiter to it.
.\" FIXME Could I get a bit more detail on the previous lines?
.\" What is "creates or reuses kernel state" about?
.\" (I think this needs to be clearer in the page)

.\" FIXME In the next line, what type of "priority" are we talking about?
.\" Realtime priorities for SCHED_FIFO and SCHED_RR?
.\" Or something else?

The
enqueueing of the waiter is in descending priority order if more than one waiter exists.

.\" FIXME In the next sentence, what type of "priority" are we talking about?
.\" Realtime priorities for SCHED_FIFO and SCHED_RR?
.\" Or something else?
.\" FIXME What does "bandwidth" refer to in the next sentence?

The owner inherits either
the priority or the bandwidth of the waiter.

.\" FIXME In the preceding sentence, what determines whether the
.\" owner inherits the priority versus the bandwidth?

.\" FIXME Could I get some help translating the next sentence into
.\" something that user-space developers (and I) can understand?
.\" In particular, what are "nested locks" in this context?

This inheri‐
tance follows the lock chain in the case of nested locking and performs deadlock detection.

.\" FIXME tglx said "The timeout argument is handled as described in
.\" FUTEX_WAIT." However, it appears to me that this is not right.
.\" Is the following formulation correct?
The timeout argument provides a timeout for the lock attempt. It is interpreted as an absolute time, measured against the CLOCK_REALTIME clock. If timeout is NULL, the operation will block indefinitely.

The uaddr2, val, and val3 arguments are ignored.

FUTEX_TRYLOCK_PI (since Linux 2.6.18)
.\" FIXME I think it would be helpful here to say a few more words about
.\" the difference(s) between FUTEX_LOCK_PI and FUTEX_TRYLOCK_PI.
.\" Can someone propose something?
This operation tries to acquire the futex at uaddr. It
deals with the situation where the TID value at uaddr is
0, but the FUTEX_WAITERS bit is set. User space cannot
handle this condition in a race-free manner
.\" FIXME How does the situation in the previous sentence come about?
.\" Probably it would be helpful to say something about that in
.\" the man page.
.\" FIXME And *how* does FUTEX_TRYLOCK_PI deal with this situation?

The uaddr2, val, timeout, and val3 arguments are ignored.

FUTEX_UNLOCK_PI (since Linux 2.6.18)
This operation wakes the top priority waiter that is wait‐ ing in FUTEX_LOCK_PI on the futex address provided by the uaddr argument.

This is called when the user space value at uaddr cannot be changed atomically from a TID (of the owner) to 0.

The uaddr2, val, timeout, and val3 arguments are ignored.

FUTEX_CMP_REQUEUE_PI (since Linux 2.6.31)
This operation is a PI-aware variant of FUTEX_CMP_REQUEUE.
It requeues waiters that are blocked via
FUTEX_WAIT_REQUEUE_PI on uaddr from a non-PI source futex (uaddr) to a PI target futex (uaddr2).

As with FUTEX_CMP_REQUEUE, this operation wakes up a maxi‐ mum of val waiters that are waiting on the futex at uaddr. However, for FUTEX_CMP_REQUEUE_PI, val is required to be 1 (since the main point is to avoid a thundering herd). The remaining waiters are removed from the wait queue of the source futex at uaddr and added to the wait queue of the target futex at uaddr2.

The val2 and val3 arguments serve the same purposes as for FUTEX_CMP_REQUEUE.
.\" FIXME The page at http://locklessinc.com/articles/futex_cheat_sheet/

.\"       notes that "priority-inheritance Futex to priority-inheritance
.\"       Futex requeues are currently unsupported". Do we need to say
.\"       something in the man page about that?

       FUTEX_WAIT_REQUEUE_PI (since Linux 2.6.31)

.\" FIXME I find the next sentence (from tglx) pretty hard to grok.
.\" Could someone explain it a bit more?

Wait operation to wait on a non-PI futex at uaddr and potentially be requeued onto a PI futex at uaddr2. The wait operation on uaddr is the same as FUTEX_WAIT.

.\" FIXME I'm not quite clear on the meaning of the following sentence.

.\"       Is this trying to say that while blocked in a
.\"       FUTEX_WAIT_REQUEUE_PI, it could happen that another
.\"       task does a FUTEX_WAKE on uaddr that simply causes
.\"       a normal wake, with the result that the FUTEX_WAIT_REQUEUE_PI
.\"       does not complete? What happens then to the FUTEX_WAIT_REQUEUE_PI
.\"       opertion? Does it remain blocked, or does it unblock
.\"       In which case, what does user space see?

The
waiter can be removed from the wait on uaddr via
FUTEX_WAKE without requeueing on uaddr2.

.\" FIXME Please check the following. tglx said "The timeout argument
.\" is handled as described in FUTEX_WAIT.", but the truth is
.\" as below, AFAICS

If timeout is not NULL, it specifies a timeout for the wait operation; this timeout is interpreted as outlined above in the description of the FUTEX_CLOCK_REALTIME
option. If timeout is NULL, the operation can block
indefinitely.

The val3 argument is ignored.

.\" FIXME Re the preceding sentence... Actually 'val3' is internally set to

.\"       FUTEX_BITSET_MATCH_ANY before calling futex_wait_requeue_pi().
.\"       I'm not sure we need to say anything about this though.
.\"       Comments?

The FUTEX_WAIT_REQUEUE_PI and FUTEX_CMP_REQUEUE_PI were added to support a fairly specific use case: support for priority-inheritance-aware POSIX threads condition vari‐ ables. The idea is that these operations should always be paired, in order to ensure that user space and the kernel remain in sync. Thus, in the FUTEX_WAIT_REQUEUE_PI opera‐ tion, the user-space application pre-specifies the target
of the requeue that takes place in the
FUTEX_CMP_REQUEUE_PI operation.

RETURN VALUE
In the event of an error (and assuming that futex() was invoked via syscall(2)), all operations return -1 and set errno to indi‐ cate the cause of the error. The return value on success depends on the operation, as described in the following list:

FUTEX_WAIT
Returns 0 if the caller was woken up. Note that a wake-up can also be caused by common futex usage patterns in unre‐ lated code that happened to have previously used the futex word's memory location (e.g., typical futex-based imple‐ mentations of Pthreads mutexes can cause this under some conditions). Therefore, callers should always conserva‐ tively assume that a return value of 0 can mean a spurious wake-up, and use the futex word's value (i.e., the user space synchronization scheme)
to decide whether to continue to block or not.

FUTEX_WAKE
Returns the number of waiters that were woken up.

FUTEX_FD
Returns the new file descriptor associated with the futex.

FUTEX_REQUEUE
Returns the number of waiters that were woken up.

FUTEX_CMP_REQUEUE
Returns the total number of waiters that were woken up or
requeued to the futex for the futex word at uaddr2. If
this value is greater than val, then difference is the number of waiters requeued to the futex for the futex word at uaddr2.

FUTEX_WAKE_OP
Returns the total number of waiters that were woken up. This is the sum of the woken waiters on the two futexes for the futex words at uaddr and uaddr2.

FUTEX_WAIT_BITSET
Returns 0 if the caller was woken up. See FUTEX_WAIT for how to interpret this correctly in practice.

FUTEX_WAKE_BITSET
Returns the number of waiters that were woken up.

FUTEX_LOCK_PI
Returns 0 if the futex was successfully locked.

FUTEX_TRYLOCK_PI
Returns 0 if the futex was successfully locked.

FUTEX_UNLOCK_PI
Returns 0 if the futex was successfully unlocked.

FUTEX_CMP_REQUEUE_PI
Returns the total number of waiters that were woken up or requeued to the futex for the futex word at uaddr2. If this value is greater than val, then difference is the number of waiters requeued to the futex for the futex word at uaddr2.

FUTEX_WAIT_REQUEUE_PI
Returns 0 if the caller was successfully requeued to the futex for the futex word at uaddr2.

ERRORS
EACCES No read access to the memory of a futex word.

EAGAIN (FUTEX_WAIT, FUTEX_WAIT_BITSET, FUTEX_WAIT_REQUEUE_PI) The
value pointed to by uaddr was not equal to the expected value val at the time of the call.

Note: on Linux, the symbolic names EAGAIN and EWOULDBLOCK (both of which appear in different parts of the kernel futex code) have the same value.

EAGAIN (FUTEX_CMP_REQUEUE, FUTEX_CMP_REQUEUE_PI) The value
pointed to by uaddr is not equal to the expected value
val3. (This probably indicates a race; use the safe
FUTEX_WAKE now.)
.\" FIXME: Is the preceding sentence "(This probably...") correct?
.\" [I would prefer to remove this sentence. [email protected]]

EAGAIN (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI)
The futex owner thread ID of uaddr (for
FUTEX_CMP_REQUEUE_PI: uaddr2) is about to exit, but has not yet handled the internal state cleanup. Try again.

.\" FIXME XXX Should there be an EAGAIN case for FUTEX_TRYLOCK_PI?

.\"       It seems so, looking at the handling of the rt_mutex_trylock()
.\"       call in futex_lock_pi()
.\"       (Davidlohr also thinks so.)

EDEADLK
(FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI)
The futex word at uaddr is already locked by the caller.

EDEADLK

.\" FIXME I reworded tglx's text somewhat; is the following okay?

(FUTEX_CMP_REQUEUE_PI) While requeueing a waiter to the PI futex for the futex word at uaddr2, the kernel detected a deadlock.

.\" FIXME XXX I see that kernel/locking/rtmutex.c uses EDEADLK in some

.\"       places, and EDEADLOCK in others. On almost all architectures
.\"       these constants are synonymous. Is there a reason that both
.\"       names are used?

EFAULT A required pointer argument (i.e., uaddr, uaddr2, or time‐
out) did not point to a valid user-space address.

EINTR A FUTEX_WAIT or FUTEX_WAIT_BITSET operation was inter‐
rupted by a signal (see signal(7)). In kernels before
Linux 2.6.22, this error could also be returned for on a spurious wakeup; since Linux 2.6.22, this no longer hap‐ pens.

EINVAL The operation in futex_op is one of those that employs a
timeout, but the supplied timeout argument was invalid (tv_sec was less than zero, or tv_nsec was not less than 1,000,000,000).

EINVAL The operation specified in futex_op employs one or both of
the pointers uaddr and uaddr2, but one of these does not point to a valid object—that is, the address is not four- byte-aligned.

EINVAL (FUTEX_WAIT_BITSET, FUTEX_WAKE_BITSET) The bitset supplied
in val3 is zero.

EINVAL (FUTEX_CMP_REQUEUE_PI) uaddr equals uaddr2 (i.e., an
attempt was made to requeue to the same futex).

EINVAL (FUTEX_FD) The signal number supplied in val is invalid.

EINVAL (FUTEX_WAKE, FUTEX_WAKE_OP, FUTEX_WAKE_BITSET,
FUTEX_REQUEUE, FUTEX_CMP_REQUEUE) The kernel detected an inconsistency between the user-space state at uaddr and the kernel state—that is, it detected a waiter which waits in FUTEX_LOCK_PI on uaddr.

EINVAL (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_UNLOCK_PI) The
kernel detected an inconsistency between the user-space state at uaddr and the kernel state. This indicates either state corruption or that the kernel found a waiter
on uaddr which is waiting via FUTEX_WAIT or
FUTEX_WAIT_BITSET.

.\" FIXME Above, tglx did not mention the "state corruption" case for

.\"       FUTEX_UNLOCK_PI, but I have added it, since I'm estimating
.\"       that it also applied for FUTEX_UNLOCK_PI.
.\"       So, does that case also apply for FUTEX_UNLOCK_PI?

EINVAL (FUTEX_CMP_REQUEUE_PI) The kernel detected an inconsis‐
tency between the user-space state at uaddr2 and the ker‐ nel state; that is, the kernel detected a waiter which waits via FUTEX_WAIT on uaddr2.
.\" FIXME In the preceding sentence, tglx did not mention FUTEX_WAIT_BITSET,
.\" but should that not also be included here?

EINVAL (FUTEX_CMP_REQUEUE_PI) The kernel detected an inconsis‐
tency between the user-space state at uaddr and the kernel state; that is, the kernel detected a waiter which waits via FUTEX_WAIT or FUTEX_WAIT_BITESET on uaddr.

EINVAL (FUTEX_CMP_REQUEUE_PI) The kernel detected an inconsis‐
tency between the user-space state at uaddr and the kernel state; that is, the kernel detected a waiter which waits
on uaddr via FUTEX_LOCK_PI (instead of
FUTEX_WAIT_REQUEUE_PI).

.\" FIXME XXX The following is a reworded version of Darren Hart's text.
.\" Please check that I did not introduce any errors.
EINVAL (FUTEX_CMP_REQUEUE_PI) An attempt was made to requeue a
waiter to a futex other than that specified by the match‐ ing FUTEX_WAIT_REQUEUE_PI call for that waiter.

EINVAL (FUTEX_CMP_REQUEUE_PI) The val argument is not 1.

EINVAL Invalid argument.

ENOMEM (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI)
The kernel could not allocate memory to hold state infor‐ mation.

ENFILE (FUTEX_FD) The system limit on the total number of open
files has been reached.

ENOSYS Invalid operation specified in futex_op.

ENOSYS The FUTEX_CLOCK_REALTIME option was specified in futex_op,
but the accompanying operation was neither FUTEX_WAIT_BIT‐ SET nor FUTEX_WAIT_REQUEUE_PI.

ENOSYS (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_UNLOCK_PI,
FUTEX_CMP_REQUEUE_PI, FUTEX_WAIT_REQUEUE_PI) A run-time check determined that the operation is not available. The PI futex operations are not implemented on all architec‐ tures and are not supported on some CPU variants.

EPERM (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI)
The caller is not allowed to attach itself to the futex at uaddr (for FUTEX_CMP_REQUEUE_PI: the futex at uaddr2). (This may be caused by a state corruption in user space.)

EPERM (FUTEX_UNLOCK_PI) The caller does not own the lock repre‐
sented by the futex word.

ESRCH (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI)

.\" FIXME I reworded the following sentence a bit differently from
.\" tglx's formulation. Is it okay?

The thread ID in the futex word at uaddr does not exist.

ESRCH (FUTEX_CMP_REQUEUE_PI)

.\" FIXME I reworded the following sentence a bit differently from
.\" tglx's formulation. Is it okay?

The thread ID in the futex word at
uaddr2 does not exist.

Quoted 9 lines

FUTEX_WAKE (since Linux 2.6.0)
This operation wakes at most val of the waiters that are waiting (e.g., inside FUTEX_WAIT) on the futex word at the address uaddr. Most commonly, val is specified as either 1 (wake up a single waiter) or INT_MAX (wake up all wait‐
ers). No guarantee is provided about which waiters are
awoken (e.g., a waiter with a higher scheduling priority is not guaranteed to be awoken in preference to a waiter with a lower priority).

That's only correct up to Linux 2.6.21.

Since 2.6.22 we have a priority ordered wakeup. For SCHED_OTHER threads this takes the nice level into account. Threads with the same priority are woken in FIFO order.

Quoted 10 lines · Thomas Gleixner

Quoted 9 lines

FUTEX_WAKE (since Linux 2.6.0)
This operation wakes at most val of the waiters that are waiting (e.g., inside FUTEX_WAIT) on the futex word at the address uaddr. Most commonly, val is specified as either 1 (wake up a single waiter) or INT_MAX (wake up all wait‐
ers). No guarantee is provided about which waiters are
awoken (e.g., a waiter with a higher scheduling priority is not guaranteed to be awoken in preference to a waiter with a lower priority).

Quoted 5 lines

That's only correct up to Linux 2.6.21.

Since 2.6.22 we have a priority ordered wakeup. For SCHED_OTHER threads this takes the nice level into account. Threads with the same priority are woken in FIFO order.

Maybe don't mention the effects of SCHED_OTHER, order by nice value is 'wrong'.

Also, this code seems to use plist, which means it won't do the right thing for SCHED_DEADLINE either.

Do we want to go fix that?

Quoted 12 lines · Peter Zijlstra

Quoted 10 lines · Thomas Gleixner

Quoted 9 lines

FUTEX_WAKE (since Linux 2.6.0)
This operation wakes at most val of the waiters that are waiting (e.g., inside FUTEX_WAIT) on the futex word at the address uaddr. Most commonly, val is specified as either 1 (wake up a single waiter) or INT_MAX (wake up all wait‐
ers). No guarantee is provided about which waiters are
awoken (e.g., a waiter with a higher scheduling priority is not guaranteed to be awoken in preference to a waiter with a lower priority).

Quoted 8 lines

Quoted 5 lines

That's only correct up to Linux 2.6.21.

Since 2.6.22 we have a priority ordered wakeup. For SCHED_OTHER threads this takes the nice level into account. Threads with the same priority are woken in FIFO order.

Maybe don't mention the effects of SCHED_OTHER, order by nice value is 'wrong'.

Indeed.

Quoted 4 lines

Also, this code seems to use plist, which means it won't do the right thing for SCHED_DEADLINE either.

Do we want to go fix that?

I think so.

Also, this code seems to use plist, which means it won't do the right thing for SCHED_DEADLINE either.

On Mon, 27 Jul 2015, Michael Kerrisk (man-pages) wrote:

Quoted 6 lines

FUTEX_REQUEUE (since Linux 2.6.0)
.\" FIXME(Torvald) Is there some indication that FUTEX_REQUEUE is broken

.\"     in general, or is this comment implicitly speaking about the
.\"     condvar (?) use case? If the latter we might want to weaken the
.\"     advice below a little.

.\" [Anyone else have input on this?]

The condvar use case exposes the flaw nicely, but that's pretty much true for everything which wants a sane requeue operation.

Quoted 8 lines

Avoid using this operation. It is broken for its intended purpose. Use FUTEX_CMP_REQUEUE instead.

This operation performs the same task as
FUTEX_CMP_REQUEUE, except that no check is made using the value in val3. (The argument val3 is ignored.)

Quoted 1 line · Thomas Gleixner

On Mon, 27 Jul 2015, Michael Kerrisk (man-pages) wrote:

...

Quoted 9 lines

Quoted 6 lines

FUTEX_REQUEUE (since Linux 2.6.0)
.\" FIXME(Torvald) Is there some indication that FUTEX_REQUEUE is broken

.\"     in general, or is this comment implicitly speaking about the
.\"     condvar (?) use case? If the latter we might want to weaken the
.\"     advice below a little.

.\" [Anyone else have input on this?]

The condvar use case exposes the flaw nicely, but that's pretty much true for everything which wants a sane requeue operation.

In an earlier discussion I argued this point (that FUTURE_REQUEUE is broken and should not be used in new code) and someone argued strongly against... stating that there were legitimate uses for it. Of course I'm struggling to find the thread and the reference at the moment - immensely useful, I know.

I'll continue trying to find it and see if it can be useful here. I believe Torvald was on the thread as well.

Quoted 8 lines

Quoted 8 lines

Avoid using this operation. It is broken for its intended purpose. Use FUTEX_CMP_REQUEUE instead.

This operation performs the same task as
FUTEX_CMP_REQUEUE, except that no check is made using the value in val3. (The argument val3 is ignored.)

Signature · 2 lines

Darren Hart
Intel Open Source Technology Center

Found it on libc-alpha, here it is for reference:

From: Rich Felker <[email protected]>
Date: Wed, 29 Oct 2014 22:43:17 -0400
To: Darren Hart <[email protected]>
Cc: Carlos O'Donell <[email protected]>, Roland McGrath <roland-/[email protected]>, Torvald Riegel <[email protected]>, GLIBC Devel <libc-alpha-9JcytcrH/[email protected]>, Michael Kerrisk <[email protected]>
Subject: Re: Add futex wrapper to glibc?

On Wed, Oct 29, 2014 at 06:59:15PM -0700, Darren Hart wrote:
> > We are IMO at the stage where futex is stable, few things are > > changing, and with documentation in place, I would consider adding a > > futex wrapper.
>
> Yes, at least for the defined OP codes. New OPs may be added of > course, but that isn't a concern for supporting what exists today, and > doesn't break compatibility.
>
> I wonder though... can we not wrap FUTEX_REQUEUE? It's fundamentally > broken. FUTEX_CMP_REQUEUE should *always* be used instead. The glibc > wrapper is one way to encourage developers to do the right thing > (don't expose the bad op in the header).

You're mistaken here. There are plenty of valid ways to use FUTEX_REQUEUE - for example if the calling thread is requeuing the target(s) to a lock that the calling thread owns. Just because it doesn't meet the needs of the way glibc was using it internally doesn't mean it's useless for other applications.

In any case, I don't think there's a proposal to intercept/modify the commands to futex, just to pass them through (and possibly do a cancellable syscall for some of them).

Quoted 15 lines · Darren Hart

Quoted 1 line · Thomas Gleixner

On Mon, 27 Jul 2015, Michael Kerrisk (man-pages) wrote:

...

Quoted 9 lines

Quoted 6 lines

FUTEX_REQUEUE (since Linux 2.6.0)
.\" FIXME(Torvald) Is there some indication that FUTEX_REQUEUE is broken

.\"     in general, or is this comment implicitly speaking about the
.\"     condvar (?) use case? If the latter we might want to weaken the
.\"     advice below a little.

.\" [Anyone else have input on this?]

The condvar use case exposes the flaw nicely, but that's pretty much true for everything which wants a sane requeue operation.

Quoted 8 lines

In an earlier discussion I argued this point (that FUTURE_REQUEUE is broken and should not be used in new code) and someone argued strongly against... stating that there were legitimate uses for it. Of course I'm struggling to find the thread and the reference at the moment - immensely useful, I know.

I'll continue trying to find it and see if it can be useful here. I believe Torvald was on the thread as well.

Found it on libc-alpha, here it is for reference:

From: Rich Felker <[email protected]>
Date: Wed, 29 Oct 2014 22:43:17 -0400
To: Darren Hart <[email protected]>
Cc: Carlos O'Donell <[email protected]>, Roland McGrath <roland-/[email protected]>, Torvald Riegel <[email protected]>, GLIBC Devel <libc-alpha-9JcytcrH/[email protected]>, Michael Kerrisk <[email protected]>
Subject: Re: Add futex wrapper to glibc?

On Wed, Oct 29, 2014 at 06:59:15PM -0700, Darren Hart wrote:
> > We are IMO at the stage where futex is stable, few things are > > changing, and with documentation in place, I would consider adding a > > futex wrapper.
>
> Yes, at least for the defined OP codes. New OPs may be added of > course, but that isn't a concern for supporting what exists today, and > doesn't break compatibility.
>
> I wonder though... can we not wrap FUTEX_REQUEUE? It's fundamentally > broken. FUTEX_CMP_REQUEUE should *always* be used instead. The glibc > wrapper is one way to encourage developers to do the right thing > (don't expose the bad op in the header).

You're mistaken here. There are plenty of valid ways to use FUTEX_REQUEUE - for example if the calling thread is requeuing the target(s) to a lock that the calling thread owns. Just because it doesn't meet the needs of the way glibc was using it internally doesn't mean it's useless for other applications.

In any case, I don't think there's a proposal to intercept/modify the commands to futex, just to pass them through (and possibly do a cancellable syscall for some of them).

Rich

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Avoid using this operation. It is broken for its intended purpose. Use FUTEX_CMP_REQUEUE instead.

This operation performs the same task as
FUTEX_CMP_REQUEUE, except that no check is made using the value in val3. (The argument val3 is ignored.)

Quoted 2 lines

.\" FIXME XXX The following is my attempt at a definition of PI futexes,
.\" based on mail discussions with Darren Hart. Does it seem okay?

Quoted 4 lines · Michael Kerrisk (man-pages)

FUTEX_CLOCK_REALTIME (since Linux 2.6.28)
This option bit can be employed only with the
FUTEX_WAIT_BITSET and FUTEX_WAIT_REQUEUE_PI operations.

Quoted 6 lines

If this option is set, the kernel treats timeout as an absolute time based on CLOCK_REALTIME.

.\" FIXME XXX I added CLOCK_MONOTONIC below. Okay?
If this option is not set, the kernel treats timeout as relative time, measured against the CLOCK_MONOTONIC clock.

That's correct.

Quoted 26 lines

The operation specified in futex_op is one of the following:

FUTEX_WAIT (since Linux 2.6.0)
This operation tests that the value at the futex word pointed to by the address uaddr still contains the expected value val, and if so, then sleeps awaiting FUTEX_WAKE on the futex word. The load of the value of the futex word is an atomic memory access (i.e., using atomic machine instructions of the respective architec‐ ture). This load, the comparison with the expected value, and starting to sleep are performed atomically and totally ordered with respect to other futex operations on the same futex word. If the thread starts to sleep, it is consid‐ ered a waiter on this futex word. If the futex value does not match val, then the call fails immediately with the error EAGAIN.

The purpose of the comparison with the expected value is to prevent lost wake-ups: If another thread changed the value of the futex word after the calling thread decided to block based on the prior value, and if the other thread executed a FUTEX_WAKE operation (or similar wake-up) after the value change and before this FUTEX_WAIT operation, then the latter will observe the value change and will not start to sleep.

Quoted 3 lines

If the timeout argument is non-NULL, its contents specify a relative timeout for the wait, measured according to the
.\" FIXME XXX I added CLOCK_MONOTONIC below. Okay?

Yes.

Quoted 5 lines

CLOCK_MONOTONIC clock. (This interval will be rounded up to the system clock granularity, and kernel scheduling delays mean that the blocking interval may overrun by a small amount.)

The given wait time will be rounded up to the system clock granularity and is guaranteed not to expire early.

There are a gazillion reasons why it can expire late, but the guarantee is that it never expires prematurely.

Quoted 2 lines

If timeout is NULL, the call blocks indef‐
initely.

Right.

Quoted 12 lines

The arguments uaddr2 and val3 are ignored.

FUTEX_WAKE (since Linux 2.6.0)
This operation wakes at most val of the waiters that are waiting (e.g., inside FUTEX_WAIT) on the futex word at the address uaddr. Most commonly, val is specified as either 1 (wake up a single waiter) or INT_MAX (wake up all wait‐
ers). No guarantee is provided about which waiters are
awoken (e.g., a waiter with a higher scheduling priority is not guaranteed to be awoken in preference to a waiter with a lower priority).

That's only correct up to Linux 2.6.21.

Since 2.6.22 we have a priority ordered wakeup. For SCHED_OTHER threads this takes the nice level into account. Threads with the same priority are woken in FIFO order.

Quoted 16 lines

The arguments timeout, uaddr2, and val3 are ignored.

FUTEX_FD (from Linux 2.6.0 up to and including Linux 2.6.25)
This operation creates a file descriptor that is associ‐ ated with the futex at uaddr. The caller must close the returned file descriptor after use. When another process or thread performs a FUTEX_WAKE on the futex word, the
file descriptor indicates as being readable with
select(2), poll(2), and epoll(7)

The file descriptor can be used to obtain asynchronous
notifications: if val is nonzero, then when another process or thread executes a FUTEX_WAKE, the caller will receive the signal number that was passed in val.

Quoted 6 lines

The arguments timeout, uaddr2 and val3 are ignored.

.\" FIXME(Torvald) We never define "upped". Maybe just remove the
.\" following sentence?
To prevent race conditions, the caller should test if the futex has been upped after FUTEX_FD returns.

Yes, just remove it.

Quoted 9 lines

Because it was inherently racy, FUTEX_FD has been removed from Linux 2.6.26 onward.

FUTEX_REQUEUE (since Linux 2.6.0)
.\" FIXME(Torvald) Is there some indication that FUTEX_REQUEUE is broken

.\"     in general, or is this comment implicitly speaking about the
.\"     condvar (?) use case? If the latter we might want to weaken the
.\"     advice below a little.

.\" [Anyone else have input on this?]

The condvar use case exposes the flaw nicely, but that's pretty much true for everything which wants a sane requeue operation.

Quoted 22 lines

Avoid using this operation. It is broken for its intended purpose. Use FUTEX_CMP_REQUEUE instead.

This operation performs the same task as
FUTEX_CMP_REQUEUE, except that no check is made using the value in val3. (The argument val3 is ignored.)

FUTEX_CMP_REQUEUE (since Linux 2.6.7)
This operation first checks whether the location uaddr
still contains the value val3. If not, the operation
fails with the error EAGAIN. Otherwise, the operation wakes up a maximum of val waiters that are waiting on the futex at uaddr. If there are more than val waiters, then the remaining waiters are removed from the wait queue of the source futex at uaddr and added to the wait queue of the target futex at uaddr2. The val2 argument specifies an upper limit on the number of waiters that are requeued to the futex at uaddr2.

.\" FIXME(Torvald) Is the following correct? Or is just the decision .\" which threads to wake or requeue part of the atomic operation?

Quoted 6 lines

The load from uaddr is an atomic memory access (i.e., using atomic machine instructions of the respective archi‐ tecture). This load, the comparison with val3, and the requeueing of any waiters are performed atomically and totally ordered with respect to other operations on the same futex word.

It's atomic as the other atomic operations on the futex word. It's always performed with the proper lock(s) held in the kernel. That means any concurrent operation will serialize on that lock(s). User space has to make sure, that depending on the observed value no concurrent operations happen, but that's something the kernel cannot control.

Quoted 8 lines

This operation was added as a replacement for the earlier FUTEX_REQUEUE. The difference is that the check of the value at uaddr can be used to ensure that requeueing hap‐ pens only under certain conditions. Both operations can
be used to avoid a "thundering herd" effect when
FUTEX_WAKE is used and all of the waiters that are woken need to acquire another futex.

Quoted 9 lines

.\" FIXME Please review the following new paragraph to see if it is
.\" accurate.
Typical values to specify for val are 0 or or 1. (Speci‐ fying INT_MAX is not useful, because it would make the FUTEX_CMP_REQUEUE operation equivalent to FUTEX_WAKE.) The limit value specified via val2 is typically either 1 or INT_MAX. (Specifying the argument as 0 is not useful, because it would make the FUTEX_CMP_REQUEUE operation equivalent to FUTEX_WAIT.)

It's correct.

Quoted 3 lines

.\" FIXME Here, it would be helpful to have an example of how
.\" FUTEX_CMP_REQUEUE might be used, at the same time illustrating
.\" why FUTEX_WAKE is unsuitable for the same use case.

Waiters:

lock(A)
while (!check_value(V)) {

  	unlock(A);
	block_on(B);
	lock(A);

};
unlock(A);

Note: B is a wait queue implemented with futexes.

If the waker would use FUTEX_WAKE and wake all waiters waiting on B then those would all try to acquire lock A. That's called thundering herd and pointless because all except one would immediately block on lock A again.

Requeueing prevents that because it only wakes one waiter and moves the other waiters to lock A. When that waiter unlocks A then the next waiter can proceed ...

Quoted 12 lines

FUTEX_WAKE_BITSET (since Linux 2.6.25)
This operation is the same as FUTEX_WAKE except that the val3 argument is used to provide a 32-bit bitset to the kernel. This bitset is used to select which waiters should be woken up. The selection is done by a bit-wise AND of the "wake" bitset (i.e., the value in val3) and the bitset which is stored in the kernel-internal state of the
waiter (the "wait" bitset that is set using
FUTEX_WAIT_BITSET). All of the waiters for which the
result of the AND is nonzero are woken up; the remaining waiters are left sleeping.

Quoted 6 lines

.\" FIXME XXX Is this next paragraph that I added okay?
The effect of FUTEX_WAIT_BITSET and FUTEX_WAKE_BITSET is to allow selective wake-ups among multiple waiters that are blocked on the same futex. Note, however, that using this bitset multiplexing feature on a futex is less effi‐ cient than simply using multiple futexes, because employ‐

s/is less efficient/can be less efficient/

It really depends on the usecase.

Quoted 85 lines

ing bitset multiplexing requires the kernel to check all waiters on a futex, including those that are not inter‐ ested in being woken up (i.e., they do not have the rele‐ vant bit set in their "wait" bitset).

The uaddr2 and timeout arguments are ignored.

The FUTEX_WAIT and FUTEX_WAKE operations correspond to FUTEX_WAIT_BITSET and FUTEX_WAKE_BITSET operations where the bitsets are all ones.

Priority-inheritance futexes
Linux supports priority-inheritance (PI) futexes in order to han‐ dle priority-inversion problems that can be encountered with nor‐ mal futex locks. Priority inversion is the problem that occurs when a high-priority task is blocked waiting to acquire a lock held by a low-priority task, while tasks at an intermediate pri‐ ority continuously preempt the low-priority task from the CPU. Consequently, the low-priority task makes no progress toward releasing the lock, and the high-priority task remains blocked.

Priority inheritance is a mechanism for dealing with the prior‐ ity-inversion problem. With this mechanism, when a high-priority task becomes blocked by a lock held by a low-priority task, the latter's priority is temporarily raised to that of the former, so that it is not preempted by any intermediate level tasks, and can thus make progress toward releasing the lock. To be effective, priority inheritance must be transitive, meaning that if a high- priority task blocks on a lock held by a lower-priority task that is itself blocked by lock held by another intermediate-priority task (and so on, for chains of arbitrary length), then both of those task (or more generally, all of the tasks in a lock chain) have their priorities raised to be the same as the high-priority task.

.\" FIXME XXX The following is my attempt at a definition of PI futexes,
.\" based on mail discussions with Darren Hart. Does it seem okay?

From a user-space perspective, what makes a futex PI-aware is a policy agreement between user space and the kernel about the value of the futex word (described in a moment), coupled with the use of the PI futex operations described below (in particular, FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, and FUTEX_CMP_REQUEUE_PI).

.\" FIXME XXX ===== Start of adapted Hart/Guniguntala text =====

.\"       The following text is drawn from the Hart/Guniguntala paper
.\"       (listed in SEE ALSO), but I have reworded some pieces
.\"       significantly. Please check it.

The PI futex operations described below differ from the other futex operations in that they impose policy on the use of the value of the futex word:

* If the lock is not acquired, the futex word's value shall be 0.

* If the lock is acquired, the futex word's value shall be the thread ID (TID; see gettid(2)) of the owning thread.

* If the lock is owned and there are threads contending for the lock, then the FUTEX_WAITERS bit shall be set in the futex word's value; in other words, this value is:

FUTEX_WAITERS | TID

Note that a PI futex word never just has the value FUTEX_WAITERS, which is a permissible state for non-PI futexes.

With this policy in place, a user-space application can acquire a not-acquired lock or release a lock that no other threads try to acquire using atomic instructions executed in user space (e.g., a compare-and-swap operation such as cmpxchg on the x86 architec‐
ture). Acquiring a lock simply consists of using compare-and-
swap to atomically set the futex word's value to the caller's TID if its previous value was 0. Releasing a lock requires using compare-and-swap to set the futex word's value to 0 if the previ‐ ous value was the expected TID.

If a futex is already acquired (i.e., has a nonzero value), wait‐ ers must employ the FUTEX_LOCK_PI operation to acquire the lock. If other threads are waiting for the lock, then the FUTEX_WAITERS bit is set in the futex value; in this case, the lock owner must employ the FUTEX_UNLOCK_PI operation to release the lock.

Quoted 7 lines

In the cases where callers are forced into the kernel (i.e., required to perform a futex() call), they then deal directly with a so-called RT-mutex, a kernel locking mechanism which implements the required priority-inheritance semantics. After the RT-mutex is acquired, the futex value is updated accordingly, before the calling thread returns to user space.
.\" FIXME ===== End of adapted Hart/Guniguntala text =====

That's correct.

Quoted 8 lines

.\" FIXME We need some explanation in the following paragraph of *why*
.\" it is important to note that "the kernel will update the
.\" futex word's value prior
It is important to note to returning to user space" . Can someone
explain? that the kernel will update the futex word's value
prior to returning to user space. Unlike the other futex opera‐ tions described above, the PI futex operations are designed for the implementation of very specific IPC mechanisms.

If there are multiple waiters on a pi futex then a wake pi operation will wake the first waiter and hand over the lock to this waiter. This includes handing over the rtmutex which represents the futex in the kernel. The strict requirement is that the futex owner and the rtmutex owner must be the same, except for the update period which is serialized by the futex internal locking. That means the kernel must update the user space value prior to returning to user space.

Quoted 6 lines

.\" FIXME XXX In discussing errors for FUTEX_CMP_REQUEUE_PI, Darren Hart

.\"       made the observation that "EINVAL is returned if the non-pi 
.\"       to pi or op pairing semantics are violated."
.\"       Probably there needs to be a general statement about this
.\"       requirement, probably located at about this point in the page.
.\"       Darren (or someone else), care to take a shot at this?

Well, that's hard to describe because the kernel only has a limited way of detecting such mismatches. It only can detect it when there are non PI waiters on a futex and a PI function is called or vice versa.

Quoted 3 lines

.\" FIXME Somewhere on this page (I guess under the discussion of PI
.\" futexes) we need a discussion of the FUTEX_OWNER_DIED bit.
.\" Can someone propose a text?

If a futex has a rtmutex associated in the kernel, i.e. when there are blocked waiters, and the owner of the futex/rtmutex dies unexpectedly, then the kernel cleans up the rtmutex (as it holds a reference to the dying task) and hands it over to the next waiter. That requires that the user space value is updated accordingly. The kernel sets the FUTEX_OWNER_DIED in the user space value along with the TID of the new owner. User space is responsible for cleaning this up, though there are cases where the kernel does the cleanup.

The FUTEX_OWNER_DIED bit can also be set on uncontended futexes, where the kernel has no state associated. This happens via the robust futex mechanism. In that case the futex value will be set to FUTEX_OWNER_DIED. The robust futex mechanism is also available for non PI futexes.

Quoted 14 lines

PI futexes are operated on by specifying one of the following values in futex_op:

FUTEX_LOCK_PI (since Linux 2.6.18)
.\" FIXME I did some significant rewording of tglx's text to create

.\"       the text below.
.\"       Please check the following paragraph, in case I injected
.\"       errors.

This operation is used after after an attempt to acquire the lock via an atomic user-space instruction failed because the futex word has a nonzero value—specifically, because it contained the namespace-specific TID of the lock owner.
.\" FIXME In the preceding line, what does "namespace-specific" mean?

Quoted 4 lines

.\"       (I kept those words from tglx.)
.\"       That is, what kind of namespace are we talking about?
.\"       (I suppose we are talking PID namespaces here, but I want to
.\"       be sure.)

Yes.

Quoted 7 lines

The operation checks the value of the futex word at the address uaddr. If the value is 0, then the kernel tries to atomically set the futex value to the caller's TID.
.\" FIXME What would be the cause(s) of failure referred to
.\" in the following sentence?
If
that fails, or the futex word's value is nonzero, the ker‐

'If that fails' does not make sense. If the user space access fails we return -EFAULT and let user space deal with the mess.

The operation here is similar to the FUTEX_WAIT logic. When the user space atomic acquire does not succeed because the futex value was non zero, then the waiter goes into the kernel, takes the kernel internal lock and retries the acquisition under the lock. If the acquisition does not succeed either, then it sets the FUTEX_WAITERS bit, to signal the lock owner that it needs to go into the kernel. Here is the pseudo code:

		lock(kernel_lock);
	retry:
		
		/*
		 * Owner might have unlocked in userspace before we
		 * were able to set the waiter bit.
		 */
		if (atomic_acquire(futex) == SUCCESS) {
		   unlock(kernel_lock());
		   return 0;
		}

		/*
		 * Owner might have unlocked after the above atomic_acquire()

		 * attempt.
		 */
		if (atomic_set_waiters_bit(futex) != SUCCESS)
		   goto retry;

		queue_waiter();
		unlock(kernel_lock);
		block();   

Quoted 9 lines

nel atomically sets the FUTEX_WAITERS bit, which signals the futex owner that it cannot unlock the futex in user space atomically by setting the futex value to 0. After that, the kernel tries to find the thread which is associ‐ ated with the owner TID, creates or reuses kernel state on behalf of the owner and attaches the waiter to it.
.\" FIXME Could I get a bit more detail on the previous lines?
.\" What is "creates or reuses kernel state" about?
.\" (I think this needs to be clearer in the page)

If this is the first waiter then there is no kernel state for this futex, so it is created. That means the rtmutex is locked and the futex owner established as the owner of the rtmutex. If there is a waiter, then the state is reused, i.e. the new waiter is enqueued into the rtmutex waiter list.

Quoted 7 lines

.\" FIXME In the next line, what type of "priority" are we talking about?
.\" Realtime priorities for SCHED_FIFO and SCHED_RR?
.\" Or something else?

The
enqueueing of the waiter is in descending priority order if more than one waiter exists.

That also covers sched deadline.

Quoted 7 lines

.\" FIXME In the next sentence, what type of "priority" are we talking about?
.\" Realtime priorities for SCHED_FIFO and SCHED_RR?
.\" Or something else?
.\" FIXME What does "bandwidth" refer to in the next sentence?

The owner inherits either
the priority or the bandwidth of the waiter.

If the highest priority waiter is SCHED_DEADLINE, then the owner inherits cpu bandwidth from the waiter as there is no priority associated to SCHED_DEADLINE tasks.

If the highest priority waiter is SCHED_FIFO/RR, then the owner inherits the waiter priority.

Quoted 10 lines

.\" FIXME In the preceding sentence, what determines whether the
.\" owner inherits the priority versus the bandwidth?

.\" FIXME Could I get some help translating the next sentence into
.\" something that user-space developers (and I) can understand?
.\" In particular, what are "nested locks" in this context?

This inheri‐
tance follows the lock chain in the case of nested locking and performs deadlock detection.

T1 blocks on lock A held by T2
T2 blocks on lock B held by T3

So we have a lock chain A, B. The inheritance mechanism follows the lock chain and propagates the highest waiter priority up to the end of the chain.

Quoted 7 lines

.\" FIXME tglx said "The timeout argument is handled as described in
.\" FUTEX_WAIT." However, it appears to me that this is not right.
.\" Is the following formulation correct?
The timeout argument provides a timeout for the lock attempt. It is interpreted as an absolute time, measured against the CLOCK_REALTIME clock. If timeout is NULL, the operation will block indefinitely.

Indeed.

Quoted 14 lines

The uaddr2, val, and val3 arguments are ignored.

FUTEX_TRYLOCK_PI (since Linux 2.6.18)
.\" FIXME I think it would be helpful here to say a few more words about
.\" the difference(s) between FUTEX_LOCK_PI and FUTEX_TRYLOCK_PI.
.\" Can someone propose something?
This operation tries to acquire the futex at uaddr. It
deals with the situation where the TID value at uaddr is
0, but the FUTEX_WAITERS bit is set. User space cannot
handle this condition in a race-free manner
.\" FIXME How does the situation in the previous sentence come about?
.\" Probably it would be helpful to say something about that in
.\" the man page.
.\" FIXME And *how* does FUTEX_TRYLOCK_PI deal with this situation?

That should be expressed differently:

This operation tries to acquire the futex at uaddr. It's invoked when the user space atomic acquire did not succeed because the user space value was not 0.

The trylock in kernel might succeed because the user space value contains stale state (FUTEX_WAITERS and or FUTEX_OWNER_DIED). This can happen when the owner of the futex died.

Quoted 26 lines

The uaddr2, val, timeout, and val3 arguments are ignored.

FUTEX_UNLOCK_PI (since Linux 2.6.18)
This operation wakes the top priority waiter that is wait‐ ing in FUTEX_LOCK_PI on the futex address provided by the uaddr argument.

This is called when the user space value at uaddr cannot be changed atomically from a TID (of the owner) to 0.

The uaddr2, val, timeout, and val3 arguments are ignored.

FUTEX_CMP_REQUEUE_PI (since Linux 2.6.31)
This operation is a PI-aware variant of FUTEX_CMP_REQUEUE.
It requeues waiters that are blocked via
FUTEX_WAIT_REQUEUE_PI on uaddr from a non-PI source futex (uaddr) to a PI target futex (uaddr2).

As with FUTEX_CMP_REQUEUE, this operation wakes up a maxi‐ mum of val waiters that are waiting on the futex at uaddr. However, for FUTEX_CMP_REQUEUE_PI, val is required to be 1 (since the main point is to avoid a thundering herd). The remaining waiters are removed from the wait queue of the source futex at uaddr and added to the wait queue of the target futex at uaddr2.

Quoted 7 lines

The val2 and val3 arguments serve the same purposes as for FUTEX_CMP_REQUEUE.
.\" FIXME The page at http://locklessinc.com/articles/futex_cheat_sheet/

.\"       notes that "priority-inheritance Futex to priority-inheritance
.\"       Futex requeues are currently unsupported". Do we need to say
.\"       something in the man page about that?

And they never will be supported because they make no sense at all.

Quoted 9 lines

       FUTEX_WAIT_REQUEUE_PI (since Linux 2.6.31)

.\" FIXME I find the next sentence (from tglx) pretty hard to grok.
.\" Could someone explain it a bit more?

Wait operation to wait on a non-PI futex at uaddr and potentially be requeued onto a PI futex at uaddr2. The wait operation on uaddr is the same as FUTEX_WAIT.

let me copy the pseudo code from cmp_requeue

lock(A)
while (!check_value(V)) {

  	unlock(A);
	block_on(B);
	lock(A);

};
unlock(A);

So in this case B is the non-PI futex (the wait queue) and A is a PI futex. So wait operation on B is the same as in FUTEX_WAIT.

Quoted 8 lines

.\" FIXME I'm not quite clear on the meaning of the following sentence.

.\"       Is this trying to say that while blocked in a
.\"       FUTEX_WAIT_REQUEUE_PI, it could happen that another
.\"       task does a FUTEX_WAKE on uaddr that simply causes
.\"       a normal wake, with the result that the FUTEX_WAIT_REQUEUE_PI
.\"       does not complete? What happens then to the FUTEX_WAIT_REQUEUE_PI
.\"       opertion? Does it remain blocked, or does it unblock
.\"       In which case, what does user space see?

It unblocks and returns -EWOULDBLOCK.

Quoted 3 lines

The
waiter can be removed from the wait on uaddr via
FUTEX_WAKE without requeueing on uaddr2.

Quoted 10 lines

.\" FIXME Please check the following. tglx said "The timeout argument
.\" is handled as described in FUTEX_WAIT.", but the truth is
.\" as below, AFAICS

If timeout is not NULL, it specifies a timeout for the wait operation; this timeout is interpreted as outlined above in the description of the FUTEX_CLOCK_REALTIME
option. If timeout is NULL, the operation can block
indefinitely.

Quoted 1 line

The val3 argument is ignored.

Correct

Quoted 4 lines

.\" FIXME Re the preceding sentence... Actually 'val3' is internally set to

.\"       FUTEX_BITSET_MATCH_ANY before calling futex_wait_requeue_pi().
.\"       I'm not sure we need to say anything about this though.
.\"       Comments?

That's a kernel internal and can be removed

Quoted 12 lines

The FUTEX_WAIT_REQUEUE_PI and FUTEX_CMP_REQUEUE_PI were added to support a fairly specific use case: support for priority-inheritance-aware POSIX threads condition vari‐ ables. The idea is that these operations should always be paired, in order to ensure that user space and the kernel remain in sync. Thus, in the FUTEX_WAIT_REQUEUE_PI opera‐ tion, the user-space application pre-specifies the target
of the requeue that takes place in the
FUTEX_CMP_REQUEUE_PI operation.

RETURN VALUE

Quoted 11 lines

ERRORS
EACCES No read access to the memory of a futex word.

EAGAIN (FUTEX_WAIT, FUTEX_WAIT_BITSET, FUTEX_WAIT_REQUEUE_PI) The
value pointed to by uaddr was not equal to the expected value val at the time of the call.

Note: on Linux, the symbolic names EAGAIN and EWOULDBLOCK (both of which appear in different parts of the kernel futex code) have the same value.

Quoted 6 lines

EAGAIN (FUTEX_CMP_REQUEUE, FUTEX_CMP_REQUEUE_PI) The value
pointed to by uaddr is not equal to the expected value
val3. (This probably indicates a race; use the safe
FUTEX_WAKE now.)
.\" FIXME: Is the preceding sentence "(This probably...") correct?
.\" [I would prefer to remove this sentence. [email protected]]

This part should be removed:

"(This probably indicates a race; use the safe FUTEX_WAKE now.)

Quoted 6 lines

EAGAIN (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI)
The futex owner thread ID of uaddr (for
FUTEX_CMP_REQUEUE_PI: uaddr2) is about to exit, but has not yet handled the internal state cleanup. Try again.

Quoted 4 lines

.\" FIXME XXX Should there be an EAGAIN case for FUTEX_TRYLOCK_PI?

.\"       It seems so, looking at the handling of the rt_mutex_trylock()
.\"       call in futex_lock_pi()
.\"       (Davidlohr also thinks so.)

Yes. It's the same internal logic so it can return EAGAIN

Quoted 6 lines

EDEADLK
(FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI)
The futex word at uaddr is already locked by the caller.

EDEADLK

Quoted 5 lines

.\" FIXME I reworded tglx's text somewhat; is the following okay?

(FUTEX_CMP_REQUEUE_PI) While requeueing a waiter to the PI futex for the futex word at uaddr2, the kernel detected a deadlock.

Yes

Quoted 5 lines

.\" FIXME XXX I see that kernel/locking/rtmutex.c uses EDEADLK in some

.\"       places, and EDEADLOCK in others. On almost all architectures
.\"       these constants are synonymous. Is there a reason that both
.\"       names are used?

No. We should probably fix that.

Quoted 6 lines

EINVAL (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_UNLOCK_PI) The
kernel detected an inconsistency between the user-space state at uaddr and the kernel state. This indicates either state corruption or that the kernel found a waiter
on uaddr which is waiting via FUTEX_WAIT or
FUTEX_WAIT_BITSET.

Quoted 4 lines

.\" FIXME Above, tglx did not mention the "state corruption" case for

.\"       FUTEX_UNLOCK_PI, but I have added it, since I'm estimating
.\"       that it also applied for FUTEX_UNLOCK_PI.
.\"       So, does that case also apply for FUTEX_UNLOCK_PI?

Yes

Quoted 7 lines

EINVAL (FUTEX_CMP_REQUEUE_PI) The kernel detected an inconsis‐
tency between the user-space state at uaddr2 and the ker‐ nel state; that is, the kernel detected a waiter which waits via FUTEX_WAIT on uaddr2.
.\" FIXME In the preceding sentence, tglx did not mention FUTEX_WAIT_BITSET,
.\" but should that not also be included here?

Yes

Quoted 12 lines

EINVAL (FUTEX_CMP_REQUEUE_PI) The kernel detected an inconsis‐
tency between the user-space state at uaddr and the kernel state; that is, the kernel detected a waiter which waits via FUTEX_WAIT or FUTEX_WAIT_BITESET on uaddr.

EINVAL (FUTEX_CMP_REQUEUE_PI) The kernel detected an inconsis‐
tency between the user-space state at uaddr and the kernel state; that is, the kernel detected a waiter which waits
on uaddr via FUTEX_LOCK_PI (instead of
FUTEX_WAIT_REQUEUE_PI).

Quoted 5 lines

.\" FIXME XXX The following is a reworded version of Darren Hart's text.
.\" Please check that I did not introduce any errors.
EINVAL (FUTEX_CMP_REQUEUE_PI) An attempt was made to requeue a
waiter to a futex other than that specified by the match‐ ing FUTEX_WAIT_REQUEUE_PI call for that waiter.

Correct. That handles the case:

	 wait_requeue_pi(A, B);
	 requeue_pi(A, C);

Quoted 6 lines

ESRCH (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI)

.\" FIXME I reworded the following sentence a bit differently from
.\" tglx's formulation. Is it okay?

The thread ID in the futex word at uaddr does not exist.

Right.

Quoted 7 lines

ESRCH (FUTEX_CMP_REQUEUE_PI)

.\" FIXME I reworded the following sentence a bit differently from
.\" tglx's formulation. Is it okay?

The thread ID in the futex word at
uaddr2 does not exist.

Right

Quoted 22 lines

Quoted 15 lines

FUTEX_CMP_REQUEUE (since Linux 2.6.7)
This operation first checks whether the location uaddr
still contains the value val3. If not, the operation
fails with the error EAGAIN. Otherwise, the operation wakes up a maximum of val waiters that are waiting on the futex at uaddr. If there are more than val waiters, then the remaining waiters are removed from the wait queue of the source futex at uaddr and added to the wait queue of the target futex at uaddr2. The val2 argument specifies an upper limit on the number of waiters that are requeued to the futex at uaddr2.

.\" FIXME(Torvald) Is the following correct? Or is just the decision .\" which threads to wake or requeue part of the atomic operation?

Quoted 6 lines

The load from uaddr is an atomic memory access (i.e., using atomic machine instructions of the respective archi‐ tecture). This load, the comparison with val3, and the requeueing of any waiters are performed atomically and totally ordered with respect to other operations on the same futex word.

Quoted 6 lines

It's atomic as the other atomic operations on the futex word. It's always performed with the proper lock(s) held in the kernel. That means any concurrent operation will serialize on that lock(s). User space has to make sure, that depending on the observed value no concurrent operations happen, but that's something the kernel cannot control.

???
Sorry, I'm not clear here. Is the current text correct then? Or is some change needed.

Quoted 9 lines

Quoted 8 lines

.\" FIXME We need some explanation in the following paragraph of *why*
.\" it is important to note that "the kernel will update the
.\" futex word's value prior
It is important to note to returning to user space" . Can someone
explain? that the kernel will update the futex word's value
prior to returning to user space. Unlike the other futex opera‐ tions described above, the PI futex operations are designed for the implementation of very specific IPC mechanisms.

Quoted 7 lines

If there are multiple waiters on a pi futex then a wake pi operation will wake the first waiter and hand over the lock to this waiter. This includes handing over the rtmutex which represents the futex in the kernel. The strict requirement is that the futex owner and the rtmutex owner must be the same, except for the update period which is serialized by the futex internal locking. That means the kernel must update the user space value prior to returning to user space.

Quoted 7 lines

Quoted 6 lines

.\" FIXME XXX In discussing errors for FUTEX_CMP_REQUEUE_PI, Darren Hart

.\"       made the observation that "EINVAL is returned if the non-pi 
.\"       to pi or op pairing semantics are violated."
.\"       Probably there needs to be a general statement about this
.\"       requirement, probably located at about this point in the page.
.\"       Darren (or someone else), care to take a shot at this?

Quoted 3 lines

Well, that's hard to describe because the kernel only has a limited way of detecting such mismatches. It only can detect it when there are non PI waiters on a futex and a PI function is called or vice versa.

Hmmm. Okay, I filed your comments away for reference, but hopefully someone can help with some actual text.

Quoted 13 lines

Quoted 3 lines

.\" FIXME Somewhere on this page (I guess under the discussion of PI
.\" futexes) we need a discussion of the FUTEX_OWNER_DIED bit.
.\" Can someone propose a text?

If a futex has a rtmutex associated in the kernel, i.e. when there are blocked waiters, and the owner of the futex/rtmutex dies unexpectedly, then the kernel cleans up the rtmutex (as it holds a reference to the dying task) and hands it over to the next waiter. That requires that the user space value is updated accordingly. The kernel sets the FUTEX_OWNER_DIED in the user space value along with the TID of the new owner. User space is responsible for cleaning this up, though there are cases where the kernel does the cleanup.

Quoted 5 lines

The FUTEX_OWNER_DIED bit can also be set on uncontended futexes, where the kernel has no state associated. This happens via the robust futex mechanism. In that case the futex value will be set to FUTEX_OWNER_DIED. The robust futex mechanism is also available for non PI futexes.

???
So, I added part of that text to the page, as follows:

If a futex has an associated RT-mutex in the kernel (i.e., there are blocked waiters) and the owner of the futex/RT-mutex dies unexpectedly, then the kernel cleans up the RT-mutex and hands it over to the next waiter. This in turn requires that the user- space value is updated accordingly. To indicate that this is required, the kernel sets the FUTEX_OWNER_DIED bit in the futex word along with the thread ID of the new owner. User space is then responsible for cleaning this up (though there are cases where the kernel does the cleanup).

Okay?

I think the last sentence still requires a little work though. What does user space need to do in terms of clean up?

Quoted 8 lines

Quoted 7 lines

.\" FIXME In the next line, what type of "priority" are we talking about?
.\" Realtime priorities for SCHED_FIFO and SCHED_RR?
.\" Or something else?

The
enqueueing of the waiter is in descending priority order if more than one waiter exists.

Quoted 1 line

That also covers sched deadline.

???
Thanks. If the realm is restricted purely to SCHED_OTHER (SCHED_NORMAL) processes, does the nice value come into play also?

So by now, I've reworked this text to be:

FUTEX_TRYLOCK_PI (since Linux 2.6.18)
This operation tries to acquire the futex at uaddr. It is invoked when a user-space atomic acquire did not succeed because the futex word was not 0.

The trylock in kernel might succeed because the futex word
contains stale state (FUTEX_WAITERS and/or
FUTEX_OWNER_DIED). This can happen when the owner of the
futex died. User space cannot handle this condition in a race-free manner

Okay?

I must admit that I find "the trylock in kernel might succeed"hard to understand. Could you elaborate a little?

???
So now I've reworded the opening text describing FUTEX_WAIT_REQUEUE_PI as follows:

FUTEX_WAIT_REQUEUE_PI (since Linux 2.6.31)
Wait on a non-PI futex at uaddr and potentially be requeued (via a FUTEX_CMP_REQUEUE_PI operation in another task) onto a PI futex at uaddr2. The wait operation on uaddr is the same as for FUTEX_WAIT.

The waiter can be removed from the wait on uaddr without requeueing on uaddr2 via a FUTEX_WAIT operation in another

task. In this case, the FUTEX_WAIT_REQUEUE_PI operation
returns with the error EWOULDBLOCK.

Okay?

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

.\" FIXME XXX In discussing errors for FUTEX_CMP_REQUEUE_PI, Darren Hart

.\"       made the observation that "EINVAL is returned if the non-pi 
.\"       to pi or op pairing semantics are violated."
.\"       Probably there needs to be a general statement about this
.\"       requirement, probably located at about this point in the page.
.\"       Darren (or someone else), care to take a shot at this?

Quoted 6 lines

Quoted 3 lines

Well, that's hard to describe because the kernel only has a limited way of detecting such mismatches. It only can detect it when there are non PI waiters on a futex and a PI function is called or vice versa.

Hmmm. Okay, I filed your comments away for reference, but hopefully someone can help with some actual text.

I let Darren come up with something sensible :)

Quoted 29 lines · Michael Kerrisk (man-pages)

Quoted 22 lines

Quoted 15 lines

FUTEX_CMP_REQUEUE (since Linux 2.6.7)
This operation first checks whether the location uaddr
still contains the value val3. If not, the operation
fails with the error EAGAIN. Otherwise, the operation wakes up a maximum of val waiters that are waiting on the futex at uaddr. If there are more than val waiters, then the remaining waiters are removed from the wait queue of the source futex at uaddr and added to the wait queue of the target futex at uaddr2. The val2 argument specifies an upper limit on the number of waiters that are requeued to the futex at uaddr2.

.\" FIXME(Torvald) Is the following correct? Or is just the decision .\" which threads to wake or requeue part of the atomic operation?

Quoted 6 lines

The load from uaddr is an atomic memory access (i.e., using atomic machine instructions of the respective archi‐ tecture). This load, the comparison with val3, and the requeueing of any waiters are performed atomically and totally ordered with respect to other operations on the same futex word.

Quoted 6 lines

It's atomic as the other atomic operations on the futex word. It's always performed with the proper lock(s) held in the kernel. That means any concurrent operation will serialize on that lock(s). User space has to make sure, that depending on the observed value no concurrent operations happen, but that's something the kernel cannot control.

Quoted 3 lines

???
Sorry, I'm not clear here. Is the current text correct then? Or is some change needed.

I think we need some change here because the meaning of atomic is unclear. The basic rules of futexes are:

- All modifying operations on the futex value have to be done with atomic instructions, usually cmpxchg. That applies to both kernel and user space.

That's the atomicity at the futex value level.

- In the kernel we have to create/modify/destroy state in order to provide the blocking/requeueing etc.

This state needs protection as well. So all operations related to the kernel internal state are serialized on the hash bucket locks. The hash buckets are a scalability mechanism to avoid contention on a single lock protecting all kernel internal state. For simplicity reasons you can just think of a global lock protecting all kernel internal state.

If the kernel creates/modifies state then it can be necessary to either reread the futex value or modify it. That happens under the locks as well.

So in the case of requeue, we take the proper locks and perform the comparison with val3 and the requeueing with the locks held.

So that lock protection makes these operations 'atomic'. The correct expression is 'serialized'.

Quoted 9 lines

Quoted 9 lines

Quoted 8 lines

.\" FIXME We need some explanation in the following paragraph of *why*
.\" it is important to note that "the kernel will update the
.\" futex word's value prior
It is important to note to returning to user space" . Can someone
explain? that the kernel will update the futex word's value
prior to returning to user space. Unlike the other futex opera‐ tions described above, the PI futex operations are designed for the implementation of very specific IPC mechanisms.

Quoted 7 lines

Quoted 7 lines

If there are multiple waiters on a pi futex then a wake pi operation will wake the first waiter and hand over the lock to this waiter. This includes handing over the rtmutex which represents the futex in the kernel. The strict requirement is that the futex owner and the rtmutex owner must be the same, except for the update period which is serialized by the futex internal locking. That means the kernel must update the user space value prior to returning to user space.

And as noted above: It must update while holding the proper locks.

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

.\" FIXME XXX In discussing errors for FUTEX_CMP_REQUEUE_PI, Darren Hart

.\"       made the observation that "EINVAL is returned if the non-pi 
.\"       to pi or op pairing semantics are violated."
.\"       Probably there needs to be a general statement about this
.\"       requirement, probably located at about this point in the page.
.\"       Darren (or someone else), care to take a shot at this?

Quoted 6 lines

Quoted 3 lines

Well, that's hard to describe because the kernel only has a limited way of detecting such mismatches. It only can detect it when there are non PI waiters on a futex and a PI function is called or vice versa.

Hmmm. Okay, I filed your comments away for reference, but hopefully someone can help with some actual text.

I let Darren come up with something sensible :)

Quoted 32 lines

Quoted 13 lines

Quoted 3 lines

.\" FIXME Somewhere on this page (I guess under the discussion of PI
.\" futexes) we need a discussion of the FUTEX_OWNER_DIED bit.
.\" Can someone propose a text?

If a futex has a rtmutex associated in the kernel, i.e. when there are blocked waiters, and the owner of the futex/rtmutex dies unexpectedly, then the kernel cleans up the rtmutex (as it holds a reference to the dying task) and hands it over to the next waiter. That requires that the user space value is updated accordingly. The kernel sets the FUTEX_OWNER_DIED in the user space value along with the TID of the new owner. User space is responsible for cleaning this up, though there are cases where the kernel does the cleanup.

Quoted 5 lines

The FUTEX_OWNER_DIED bit can also be set on uncontended futexes, where the kernel has no state associated. This happens via the robust futex mechanism. In that case the futex value will be set to FUTEX_OWNER_DIED. The robust futex mechanism is also available for non PI futexes.

???
So, I added part of that text to the page, as follows:

If a futex has an associated RT-mutex in the kernel (i.e., there are blocked waiters) and the owner of the futex/RT-mutex dies unexpectedly, then the kernel cleans up the RT-mutex and hands it over to the next waiter. This in turn requires that the user- space value is updated accordingly. To indicate that this is required, the kernel sets the FUTEX_OWNER_DIED bit in the futex word along with the thread ID of the new owner. User space is then responsible for cleaning this up (though there are cases where the kernel does the cleanup).

Quoted 4 lines

Okay?

I think the last sentence still requires a little work though. What does user space need to do in terms of clean up?

User space has usually state as well. So the FUTEX_OWNER_DIED bit tells userspace that it needs to cleanup the stale state left over by the dead owner.

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines

.\" FIXME In the next line, what type of "priority" are we talking about?
.\" Realtime priorities for SCHED_FIFO and SCHED_RR?
.\" Or something else?

The
enqueueing of the waiter is in descending priority order if more than one waiter exists.

Quoted 5 lines

Quoted 1 line

That also covers sched deadline.

???
Thanks. If the realm is restricted purely to SCHED_OTHER (SCHED_NORMAL) processes, does the nice value come into play also?

No. SCHED_OTHER/NORMAL tasks are handled in FIFO order.

Quoted 13 lines

So by now, I've reworked this text to be:

FUTEX_TRYLOCK_PI (since Linux 2.6.18)
This operation tries to acquire the futex at uaddr. It is invoked when a user-space atomic acquire did not succeed because the futex word was not 0.

The trylock in kernel might succeed because the futex word
contains stale state (FUTEX_WAITERS and/or
FUTEX_OWNER_DIED). This can happen when the owner of the
futex died. User space cannot handle this condition in a race-free manner

Quoted 4 lines

Okay?

I must admit that I find "the trylock in kernel might succeed"hard to understand. Could you elaborate a little?

If the user space value has stale state, then the kernel can fix that up and acquire the futex.

Quoted 10 lines

???
So now I've reworded the opening text describing FUTEX_WAIT_REQUEUE_PI as follows:

FUTEX_WAIT_REQUEUE_PI (since Linux 2.6.31)
Wait on a non-PI futex at uaddr and potentially be requeued (via a FUTEX_CMP_REQUEUE_PI operation in another task) onto a PI futex at uaddr2. The wait operation on uaddr is the same as for FUTEX_WAIT.

Quoted 2 lines

The waiter can be removed from the wait on uaddr without requeueing on uaddr2 via a FUTEX_WAIT operation in another

s/FUTEX_WAIT/FUTEX_WAKE/

Quoted 4 lines

task. In this case, the FUTEX_WAIT_REQUEUE_PI operation
returns with the error EWOULDBLOCK.

Okay?

Yes.

Hello Thomas,

Thanks for the follow up!

Some open questions below are marked with the string ###.

Quoted 60 lines · Michael Kerrisk (man-pages)

Quoted 29 lines

Quoted 22 lines

Quoted 15 lines

FUTEX_CMP_REQUEUE (since Linux 2.6.7)
This operation first checks whether the location uaddr
still contains the value val3. If not, the operation
fails with the error EAGAIN. Otherwise, the operation wakes up a maximum of val waiters that are waiting on the futex at uaddr. If there are more than val waiters, then the remaining waiters are removed from the wait queue of the source futex at uaddr and added to the wait queue of the target futex at uaddr2. The val2 argument specifies an upper limit on the number of waiters that are requeued to the futex at uaddr2.

.\" FIXME(Torvald) Is the following correct? Or is just the decision .\" which threads to wake or requeue part of the atomic operation?

Quoted 6 lines

The load from uaddr is an atomic memory access (i.e., using atomic machine instructions of the respective archi‐ tecture). This load, the comparison with val3, and the requeueing of any waiters are performed atomically and totally ordered with respect to other operations on the same futex word.

Quoted 6 lines

It's atomic as the other atomic operations on the futex word. It's always performed with the proper lock(s) held in the kernel. That means any concurrent operation will serialize on that lock(s). User space has to make sure, that depending on the observed value no concurrent operations happen, but that's something the kernel cannot control.

Quoted 3 lines

???
Sorry, I'm not clear here. Is the current text correct then? Or is some change needed.

I think we need some change here because the meaning of atomic is unclear. The basic rules of futexes are:

- All modifying operations on the futex value have to be done with atomic instructions, usually cmpxchg. That applies to both kernel and user space.

That's the atomicity at the futex value level.

- In the kernel we have to create/modify/destroy state in order to provide the blocking/requeueing etc.

This state needs protection as well. So all operations related to the kernel internal state are serialized on the hash bucket locks. The hash buckets are a scalability mechanism to avoid contention on a single lock protecting all kernel internal state. For simplicity reasons you can just think of a global lock protecting all kernel internal state.

If the kernel creates/modifies state then it can be necessary to either reread the futex value or modify it. That happens under the locks as well.

So in the case of requeue, we take the proper locks and perform the comparison with val3 and the requeueing with the locks held.

Quoted 2 lines

So that lock protection makes these operations 'atomic'. The correct expression is 'serialized'.

###
So, here, i think I need some specific pointers on the precise text changes that are required. Let's talk about this f2f. For convenience, here's the relevant text once again quoted:

FUTEX_CMP_REQUEUE (since Linux 2.6.7)
This operation first checks whether the location uaddr
still contains the value val3. If not, the operation
fails with the error EAGAIN. Otherwise, the operation

wakes up a maximum of val waiters that are waiting on the futex at uaddr. If there are more than val waiters, then the remaining waiters are removed from the wait queue of the source futex at uaddr and added to the wait queue of the target futex at uaddr2. The val2 argument specifies an upper limit on the number of waiters that are requeued to the futex at uaddr2.

The load from uaddr is an atomic memory access (i.e., using atomic machine instructions of the respective archi‐ tecture). This load, the comparison with val3,

and the
requeueing of any waiters are performed atomically and totally ordered with respect to other operations on the same futex word.

Quoted 19 lines

Quoted 11 lines

Quoted 11 lines

Quoted 10 lines

.\" FIXME We need some explanation in the following paragraph of *why*
.\" it is important to note that "the kernel will update the
.\" futex word's value prior
It is important to note to returning to user space" . Can someone
explain? that the kernel will update the futex word's value
prior to returning to user space. Unlike the other futex opera‐ tions described above, the PI futex operations are designed for the implementation of very specific IPC mechanisms.

Quoted 7 lines

Quoted 7 lines

If there are multiple waiters on a pi futex then a wake pi operation will wake the first waiter and hand over the lock to this waiter. This includes handing over the rtmutex which represents the futex in the kernel. The strict requirement is that the futex owner and the rtmutex owner must be the same, except for the update period which is serialized by the futex internal locking. That means the kernel must update the user space value prior to returning to user space.

Quoted 1 line

And as noted above: It must update while holding the proper locks.

(Okay.)

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

.\" FIXME XXX In discussing errors for FUTEX_CMP_REQUEUE_PI, Darren Hart

.\"       made the observation that "EINVAL is returned if the non-pi 
.\"       to pi or op pairing semantics are violated."
.\"       Probably there needs to be a general statement about this
.\"       requirement, probably located at about this point in the page.
.\"       Darren (or someone else), care to take a shot at this?

Quoted 8 lines

Quoted 6 lines

Quoted 3 lines

Well, that's hard to describe because the kernel only has a limited way of detecting such mismatches. It only can detect it when there are non PI waiters on a futex and a PI function is called or vice versa.

Hmmm. Okay, I filed your comments away for reference, but hopefully someone can help with some actual text.

I let Darren come up with something sensible :)

Okay, let's see if Darren has something to say.

Quoted 32 lines

Quoted 32 lines

Quoted 13 lines

Quoted 3 lines

.\" FIXME Somewhere on this page (I guess under the discussion of PI
.\" futexes) we need a discussion of the FUTEX_OWNER_DIED bit.
.\" Can someone propose a text?

If a futex has a rtmutex associated in the kernel, i.e. when there are blocked waiters, and the owner of the futex/rtmutex dies unexpectedly, then the kernel cleans up the rtmutex (as it holds a reference to the dying task) and hands it over to the next waiter. That requires that the user space value is updated accordingly. The kernel sets the FUTEX_OWNER_DIED in the user space value along with the TID of the new owner. User space is responsible for cleaning this up, though there are cases where the kernel does the cleanup.

Quoted 5 lines

The FUTEX_OWNER_DIED bit can also be set on uncontended futexes, where the kernel has no state associated. This happens via the robust futex mechanism. In that case the futex value will be set to FUTEX_OWNER_DIED. The robust futex mechanism is also available for non PI futexes.

???
So, I added part of that text to the page, as follows:

If a futex has an associated RT-mutex in the kernel (i.e., there are blocked waiters) and the owner of the futex/RT-mutex dies unexpectedly, then the kernel cleans up the RT-mutex and hands it over to the next waiter. This in turn requires that the user- space value is updated accordingly. To indicate that this is required, the kernel sets the FUTEX_OWNER_DIED bit in the futex word along with the thread ID of the new owner. User space is then responsible for cleaning this up (though there are cases where the kernel does the cleanup).

Quoted 8 lines

Quoted 4 lines

Okay?

I think the last sentence still requires a little work though. What does user space need to do in terms of clean up?

User space has usually state as well. So the FUTEX_OWNER_DIED bit tells userspace that it needs to cleanup the stale state left over by the dead owner.

###
So I changed the last sentence to

User space is then responsible for cleaning up the stale state left over by the dead owner.

Okay?

Quoted 9 lines

Quoted 9 lines

Quoted 9 lines

Quoted 8 lines

.\" FIXME In the next line, what type of "priority" are we talking about?
.\" Realtime priorities for SCHED_FIFO and SCHED_RR?
.\" Or something else?

The
enqueueing of the waiter is in descending priority order if more than one waiter exists.

Quoted 7 lines

Quoted 5 lines

Quoted 1 line

That also covers sched deadline.

???
Thanks. If the realm is restricted purely to SCHED_OTHER (SCHED_NORMAL) processes, does the nice value come into play also?

No. SCHED_OTHER/NORMAL tasks are handled in FIFO order.

Okay. Thanks.

Quoted 13 lines

Quoted 13 lines

So by now, I've reworked this text to be:

FUTEX_TRYLOCK_PI (since Linux 2.6.18)
This operation tries to acquire the futex at uaddr. It is invoked when a user-space atomic acquire did not succeed because the futex word was not 0.

The trylock in kernel might succeed because the futex word
contains stale state (FUTEX_WAITERS and/or
FUTEX_OWNER_DIED). This can happen when the owner of the
futex died. User space cannot handle this condition in a race-free manner

Quoted 7 lines

Quoted 4 lines

Okay?

I must admit that I find "the trylock in kernel might succeed"hard to understand. Could you elaborate a little?

If the user space value has stale state, then the kernel can fix that up and acquire the futex.

Okay, so I made the last sentence:

User space cannot handle this condition in a race-free manner, but the kernel can fix this up and acquire the futex.

Okay?

However, I realize I should have said more clearly why I find the text hard to understand. As I read this text:

The trylock in kernel might succeed because the futex word contains stale state FUTEX_WAITERS and/or FUTEX_OWNER_DIED).

###

The words "The trylock in kernel might succeed" makes it feel like a contrast is being drawn with some other scenario, but it's not clear what that alternative/contrast is. Do you see what I mean? Let's talk about this f2f.

Quoted 11 lines

Quoted 11 lines

???
So now I've reworded the opening text describing FUTEX_WAIT_REQUEUE_PI as follows:

FUTEX_WAIT_REQUEUE_PI (since Linux 2.6.31)
Wait on a non-PI futex at uaddr and potentially be requeued (via a FUTEX_CMP_REQUEUE_PI operation in another task) onto a PI futex at uaddr2. The wait operation on uaddr is the same as for FUTEX_WAIT.

Quoted 4 lines

Quoted 2 lines

The waiter can be removed from the wait on uaddr without requeueing on uaddr2 via a FUTEX_WAIT operation in another

s/FUTEX_WAIT/FUTEX_WAKE/

Thanks. Fixed.

Quoted 6 lines

Quoted 4 lines

task. In this case, the FUTEX_WAIT_REQUEUE_PI operation
returns with the error EWOULDBLOCK.

Okay?

Yes.

Thanks.

Cheers,

Michael

Signature · 3 lines

Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/

Hello all,

Priority-inheritance futexes
Linux supports priority-inheritance (PI) futexes in order to han‐ dle priority-inversion problems that can be encountered with nor‐ mal futex locks. Priority inversion is the problem that occurs when a high-priority task is blocked waiting to acquire a lock held by a low-priority task, while tasks at an intermediate pri‐ ority continuously preempt the low-priority task from the CPU. Consequently, the low-priority task makes no progress toward releasing the lock, and the high-priority task remains blocked.

Priority inheritance is a mechanism for dealing with the prior‐ ity-inversion problem. With this mechanism, when a high-priority task becomes blocked by a lock held by a low-priority task, the latter's priority is temporarily raised to that of the former, so that it is not preempted by any intermediate level tasks, and can thus make progress toward releasing the lock. To be effective, priority inheritance must be transitive, meaning that if a high- priority task blocks on a lock held by a lower-priority task that is itself blocked by lock held by another intermediate-priority task (and so on, for chains of arbitrary length), then both of those task (or more generally, all of the tasks in a lock chain) have their priorities raised to be the same as the high-priority task.

.\" FIXME XXX The following is my attempt at a definition of PI futexes,
.\" based on mail discussions with Darren Hart. Does it seem okay?

From a user-space perspective, what makes a futex PI-aware is a policy agreement between user space and the kernel about the value of the futex word (described in a moment), coupled with the use of the PI futex operations described below (in particular, FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, and FUTEX_CMP_REQUEUE_PI).

.\" FIXME XXX ===== Start of adapted Hart/Guniguntala text =====

.\"       The following text is drawn from the Hart/Guniguntala paper
.\"       (listed in SEE ALSO), but I have reworded some pieces
.\"       significantly. Please check it.

The PI futex operations described below differ from the other futex operations in that they impose policy on the use of the value of the futex word:

* If the lock is not acquired, the futex word's value shall be 0.

* If the lock is acquired, the futex word's value shall be the thread ID (TID; see gettid(2)) of the owning thread.

* If the lock is owned and there are threads contending for the lock, then the FUTEX_WAITERS bit shall be set in the futex word's value; in other words, this value is:

FUTEX_WAITERS | TID

Note that a PI futex word never just has the value FUTEX_WAITERS, which is a permissible state for non-PI futexes.

With this policy in place, a user-space application can acquire a not-acquired lock or release a lock that no other threads try to

acquire using atomic instructions executed in user space (e.g., a compare-and-swap operation such as cmpxchg on the x86 architec‐
ture). Acquiring a lock simply consists of using compare-and-
swap to atomically set the futex word's value to the caller's TID if its previous value was 0. Releasing a lock requires using compare-and-swap to set the futex word's value to 0 if the previ‐ ous value was the expected TID.

If a futex is already acquired (i.e., has a nonzero value), wait‐ ers must employ the FUTEX_LOCK_PI operation to acquire the lock. If other threads are waiting for the lock, then the FUTEX_WAITERS bit is set in the futex value; in this case, the lock owner must employ the FUTEX_UNLOCK_PI operation to release the lock.

In the cases where callers are forced into the kernel (i.e., required to perform a futex() call), they then deal directly with a so-called RT-mutex, a kernel locking mechanism which implements the required priority-inheritance semantics. After the RT-mutex is acquired, the futex value is updated accordingly, before the calling thread returns to user space.

.\" FIXME ===== End of adapted Hart/Guniguntala text =====

.\" FIXME We need some explanation in the following paragraph of *why*
.\" it is important to note that "the kernel will update the
.\" futex word's value prior
It is important to note to returning to user space" . Can someone
explain? that the kernel will update the futex word's value
prior to returning to user space. Unlike the other futex opera‐ tions described above, the PI futex operations are designed for the implementation of very specific IPC mechanisms.

.\"
.\" FIXME XXX In discussing errors for FUTEX_CMP_REQUEUE_PI, Darren Hart

.\"       made the observation that "EINVAL is returned if the non-pi 
.\"       to pi or op pairing semantics are violated."
.\"       Probably there needs to be a general statement about this
.\"       requirement, probably located at about this point in the page.
.\"       Darren (or someone else), care to take a shot at this?

       FUTEX_LOCK_PI (since Linux 2.6.18)
.\" FIXME I did some significant rewording of tglx's text to create
.\"       the text below.
.\"       Please check the following paragraph, in case I injected
.\"       errors.

This operation is used after after an attempt to acquire the lock via an atomic user-space instruction failed because the futex word has a nonzero value—specifically, because it contained the namespace-specific TID of the lock owner.

       FUTEX_TRYLOCK_PI (since Linux 2.6.18)

.\" FIXME I think it would be helpful here to say a few more words about
.\" the difference(s) between FUTEX_LOCK_PI and FUTEX_TRYLOCK_PI.
.\" Can someone propose something?
This operation tries to acquire the futex at uaddr. It
deals with the situation where the TID value at uaddr is
0, but the FUTEX_WAITERS bit is set. User space cannot
handle this condition in a race-free manner
.\" FIXME How does the situation in the previous sentence come about?
.\" Probably it would be helpful to say something about that in
.\" the man page.
.\" FIXME And *how* does FUTEX_TRYLOCK_PI deal with this situation?

FUTEX_CMP_REQUEUE_PI (since Linux 2.6.31)
This operation is a PI-aware variant of FUTEX_CMP_REQUEUE.
It requeues waiters that are blocked via
FUTEX_WAIT_REQUEUE_PI on uaddr from a non-PI source futex (uaddr) to a PI target futex (uaddr2).

As with FUTEX_CMP_REQUEUE, this operation wakes up a maxi‐ mum of val waiters that are waiting on the futex at uaddr. However, for FUTEX_CMP_REQUEUE_PI, val is required to be 1 (since the main point is to avoid a thundering herd). The remaining waiters are removed from the wait queue of the source futex at uaddr and added to the wait queue of the target futex at uaddr2.

The val2 and val3 arguments serve the same purposes as for FUTEX_CMP_REQUEUE.
.\" FIXME The page at http://locklessinc.com/articles/futex_cheat_sheet/

.\"       notes that "priority-inheritance Futex to priority-inheritance
.\"       Futex requeues are currently unsupported". Do we need to say
.\"       something in the man page about that?

       FUTEX_WAIT_REQUEUE_PI (since Linux 2.6.31)

.\" FIXME I find the next sentence (from tglx) pretty hard to grok.
.\" Could someone explain it a bit more?

Wait operation to wait on a non-PI futex at uaddr and potentially be requeued onto a PI futex at uaddr2. The wait operation on uaddr is the same as FUTEX_WAIT.

.\" FIXME I'm not quite clear on the meaning of the following sentence.

.\"       Is this trying to say that while blocked in a
.\"       FUTEX_WAIT_REQUEUE_PI, it could happen that another
.\"       task does a FUTEX_WAKE on uaddr that simply causes
.\"       a normal wake, with the result that the FUTEX_WAIT_REQUEUE_PI
.\"       does not complete? What happens then to the FUTEX_WAIT_REQUEUE_PI
.\"       opertion? Does it remain blocked, or does it unblock
.\"       In which case, what does user space see?

The
waiter can be removed from the wait on uaddr via
FUTEX_WAKE without requeueing on uaddr2.

.\" FIXME XXX The following is a reworded version of Darren Hart's text.
.\" Please check that I did not introduce any errors.
EINVAL (FUTEX_CMP_REQUEUE_PI) An attempt was made to requeue a
waiter to a futex other than that specified by the match‐ ing FUTEX_WAIT_REQUEUE_PI call for that waiter.

Quoted 2 lines · Michael Kerrisk (man-pages)

Hello all,

Michael, thank you for your diligence in following up and collecting reviews. I've attempted to respond to what I was specifically called out in or where I had something specific to add in addition to other replies.

After this, will you send another version (numbered for reference maybe?) with any remaining FIXMEs that haven't yet been addressed according to your accounting?

Quoted 27 lines

Priority-inheritance futexes
Linux supports priority-inheritance (PI) futexes in order to han‐ dle priority-inversion problems that can be encountered with nor‐ mal futex locks. Priority inversion is the problem that occurs when a high-priority task is blocked waiting to acquire a lock held by a low-priority task, while tasks at an intermediate pri‐ ority continuously preempt the low-priority task from the CPU. Consequently, the low-priority task makes no progress toward releasing the lock, and the high-priority task remains blocked.

Priority inheritance is a mechanism for dealing with the prior‐ ity-inversion problem. With this mechanism, when a high-priority task becomes blocked by a lock held by a low-priority task, the latter's priority is temporarily raised to that of the former, so that it is not preempted by any intermediate level tasks, and can thus make progress toward releasing the lock. To be effective, priority inheritance must be transitive, meaning that if a high- priority task blocks on a lock held by a lower-priority task that is itself blocked by lock held by another intermediate-priority task (and so on, for chains of arbitrary length), then both of those task (or more generally, all of the tasks in a lock chain) have their priorities raised to be the same as the high-priority task.

.\" FIXME XXX The following is my attempt at a definition of PI futexes,
.\" based on mail discussions with Darren Hart. Does it seem okay?

Quoted 5 lines

From a user-space perspective, what makes a futex PI-aware is a policy agreement between user space and the kernel about the value of the futex word (described in a moment), coupled with the use of the PI futex operations described below (in particular, FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, and FUTEX_CMP_REQUEUE_PI).

Yes. Was this intended to be a complete opcode list?

PI operations must
use paired operations.

(FUTEX_LOCK_PI | FUTEX_TRYLOCK_PI) : FUTEX_UNLOCK_PI FUTEX_WAIT_REQUEUE_PI : FUTEX_CMP_REQUEUE_PI

And their PRIVATE counterparts of course (which is assumed as it is a flag to the opcode).

Quoted 19 lines

.\" FIXME XXX ===== Start of adapted Hart/Guniguntala text =====

.\"       The following text is drawn from the Hart/Guniguntala paper
.\"       (listed in SEE ALSO), but I have reworded some pieces
.\"       significantly. Please check it.

The PI futex operations described below differ from the other futex operations in that they impose policy on the use of the value of the futex word:

* If the lock is not acquired, the futex word's value shall be 0.

* If the lock is acquired, the futex word's value shall be the thread ID (TID; see gettid(2)) of the owning thread.

* If the lock is owned and there are threads contending for the lock, then the FUTEX_WAITERS bit shall be set in the futex word's value; in other words, this value is:

Quoted 5 lines

FUTEX_WAITERS | TID

Note that a PI futex word never just has the value FUTEX_WAITERS, which is a permissible state for non-PI futexes.

The second clause is inappropriate. I don't know if that was yours or mine, but non-PI futexes do not have a kernel defined value policy, so ==FUTEX_WAITERS cannot be a "permissible state" as any value is permissible for non-PI futexes, and none have a kernel defined state.

Perhaps include a Note under the third bullet as:

Note: It is invalid for a PI futex word to have no owner and
FUTEX_WAITERS set.

Quoted 2 lines

With this policy in place, a user-space application can acquire a not-acquired lock or release a lock that no other threads try to

"that no other threads try to acquire" seems out of place. I think "atomic instructions" is sufficient to express how contention is handled.

Quoted 14 lines

acquire using atomic instructions executed in user space (e.g., a compare-and-swap operation such as cmpxchg on the x86 architec‐
ture). Acquiring a lock simply consists of using compare-and-
swap to atomically set the futex word's value to the caller's TID if its previous value was 0. Releasing a lock requires using compare-and-swap to set the futex word's value to 0 if the previ‐ ous value was the expected TID.

If a futex is already acquired (i.e., has a nonzero value), wait‐ ers must employ the FUTEX_LOCK_PI operation to acquire the lock. If other threads are waiting for the lock, then the FUTEX_WAITERS bit is set in the futex value; in this case, the lock owner must employ the FUTEX_UNLOCK_PI operation to release the lock.

Quoted 6 lines

In the cases where callers are forced into the kernel (i.e., required to perform a futex() call), they then deal directly with a so-called RT-mutex, a kernel locking mechanism which implements the required priority-inheritance semantics. After the RT-mutex is acquired, the futex value is updated accordingly, before the calling thread returns to user space.

This last paragraph relies on kernel implementation rather than behavior. If the RT-mutex is renamed or the mechanism is implemented differently in futexes, this section will require updating. Is that appropriate for a user-space man page?

Quoted 4 lines

.\" FIXME ===== End of adapted Hart/Guniguntala text =====

Quoted 8 lines

.\" FIXME We need some explanation in the following paragraph of *why*
.\" it is important to note that "the kernel will update the
.\" futex word's value prior
It is important to note to returning to user space" . Can someone
explain? that the kernel will update the futex word's value
prior to returning to user space. Unlike the other futex opera‐ tions described above, the PI futex operations are designed for the implementation of very specific IPC mechanisms.

If the kernel didn't perform the update prior to returning to userspace, we could end up in an invalid state. Such as having an owner, but the value being 0. Or having waiters, but not having FUTEX_WAITERS set.

Quoted 7 lines

.\"
.\" FIXME XXX In discussing errors for FUTEX_CMP_REQUEUE_PI, Darren Hart

.\"       made the observation that "EINVAL is returned if the non-pi 
.\"       to pi or op pairing semantics are violated."
.\"       Probably there needs to be a general statement about this
.\"       requirement, probably located at about this point in the page.
.\"       Darren (or someone else), care to take a shot at this?

We can probably borrow from either the futex.c comments or the futex-requeue-pi.txt in Documentation. Also, it is important to note that the PI requeue operations require two distinct uadders (although that is implied by requiring "non-pi to pi" as a futex cannot be both.

Or... perhaps something like:

Due to the kernel imposed futex word value policy, PI futex operations have additional usage requirements:

FUTEX_WAIT_REQUEUE_PI must be paired with FUTEX_CMP_REQUEUE_PI and be performed from a non-pi futex to a distinct pi futex. Failing to do so will return EINVAL.

Additionally,
FUTEX_CMP_REQUEUE_PI requires that nr_wake=1. [We state in the docs that nr_requeue should be INT_MAX for broadcast and 0 for signal... but that may be overly specific to libc for this manual]

Similarly, FUTEX_UNLOCK_PI must only be called on a futex owned by the calling thread as defined by the value policy, otherwise EPERM is returned.

Were you looking for something like that - or were you looking for justification for these requirements?

...

Quoted 10 lines

       FUTEX_LOCK_PI (since Linux 2.6.18)
.\" FIXME I did some significant rewording of tglx's text to create
.\"       the text below.
.\"       Please check the following paragraph, in case I injected
.\"       errors.

This operation is used after after an attempt to acquire the lock via an atomic user-space instruction failed because the futex word has a nonzero value—specifically, because it contained the namespace-specific TID of the lock owner.

Acked.

Quoted 12 lines

       FUTEX_TRYLOCK_PI (since Linux 2.6.18)

.\" FIXME I think it would be helpful here to say a few more words about
.\" the difference(s) between FUTEX_LOCK_PI and FUTEX_TRYLOCK_PI.
.\" Can someone propose something?
This operation tries to acquire the futex at uaddr. It
deals with the situation where the TID value at uaddr is
0, but the FUTEX_WAITERS bit is set. User space cannot
handle this condition in a race-free manner
.\" FIXME How does the situation in the previous sentence come about?
.\" Probably it would be helpful to say something about that in
.\" the man page.
.\" FIXME And *how* does FUTEX_TRYLOCK_PI deal with this situation?

I guess I wouldn't expect to see this detail in the manual. That state should never exist in userspace as far as I understand it, which makes it a kernel implementation detail and not relevant to a usage manual.

Quoted 15 lines

FUTEX_CMP_REQUEUE_PI (since Linux 2.6.31)
This operation is a PI-aware variant of FUTEX_CMP_REQUEUE.
It requeues waiters that are blocked via
FUTEX_WAIT_REQUEUE_PI on uaddr from a non-PI source futex (uaddr) to a PI target futex (uaddr2).

As with FUTEX_CMP_REQUEUE, this operation wakes up a maxi‐ mum of val waiters that are waiting on the futex at uaddr. However, for FUTEX_CMP_REQUEUE_PI, val is required to be 1 (since the main point is to avoid a thundering herd). The remaining waiters are removed from the wait queue of the source futex at uaddr and added to the wait queue of the target futex at uaddr2.

Quoted 7 lines

The val2 and val3 arguments serve the same purposes as for FUTEX_CMP_REQUEUE.
.\" FIXME The page at http://locklessinc.com/articles/futex_cheat_sheet/

.\"       notes that "priority-inheritance Futex to priority-inheritance
.\"       Futex requeues are currently unsupported". Do we need to say
.\"       something in the man page about that?

I noted this above in response to your request for detail about the *REQUEUE_PI semantics and error codes. Was that sufficient?

Quoted 8 lines

       FUTEX_WAIT_REQUEUE_PI (since Linux 2.6.31)

.\" FIXME I find the next sentence (from tglx) pretty hard to grok.
.\" Could someone explain it a bit more?

Wait operation to wait on a non-PI futex at uaddr and potentially be requeued onto a PI futex at uaddr2. The wait operation on uaddr is the same as FUTEX_WAIT.

The point tglx is making here is that you must know ahead of time and tell the kernel that you intend to use this futex in a REQUEUE_PI operation, and not a regular REQUEUE. This is determined by the both the op codes as well as the required arguments, which I also documented above. Is more detail required?

Quoted 9 lines

.\" FIXME I'm not quite clear on the meaning of the following sentence.

.\"       Is this trying to say that while blocked in a
.\"       FUTEX_WAIT_REQUEUE_PI, it could happen that another
.\"       task does a FUTEX_WAKE on uaddr that simply causes
.\"       a normal wake, with the result that the FUTEX_WAIT_REQUEUE_PI
.\"       does not complete? What happens then to the FUTEX_WAIT_REQUEUE_PI
.\"       opertion? Does it remain blocked, or does it unblock
.\"       In which case, what does user space see?

Quoted 3 lines

The
waiter can be removed from the wait on uaddr via
FUTEX_WAKE without requeueing on uaddr2.

Userspace should see the task wake and continue executing. This would effectively be a cancelation operation - which I didn't think was supported. Thomas?

Quoted 5 lines

.\" FIXME XXX The following is a reworded version of Darren Hart's text.
.\" Please check that I did not introduce any errors.
EINVAL (FUTEX_CMP_REQUEUE_PI) An attempt was made to requeue a
waiter to a futex other than that specified by the match‐ ing FUTEX_WAIT_REQUEUE_PI call for that waiter.

Acked.

Quoted 13 lines

Quoted 4 lines

.\" FIXME ===== End of adapted Hart/Guniguntala text =====

Quoted 8 lines

.\" FIXME We need some explanation in the following paragraph of *why*
.\" it is important to note that "the kernel will update the
.\" futex word's value prior
It is important to note to returning to user space" . Can someone
explain? that the kernel will update the futex word's value
prior to returning to user space. Unlike the other futex opera‐ tions described above, the PI futex operations are designed for the implementation of very specific IPC mechanisms.

Quoted 3 lines

If the kernel didn't perform the update prior to returning to userspace, we could end up in an invalid state. Such as having an owner, but the value being 0. Or having waiters, but not having FUTEX_WAITERS set.

So I've now reworked this passage to read:

It is important to note that the kernel will update the futex
word's value prior to returning to user space. (This prevents
the possibility of the futex word's value ending up in an invalid state, such as having an owner but the value being 0, or having waiters but not having the FUTEX_WAITERS bit set.)

Okay?

Quoted 19 lines

Quoted 8 lines

.\"
.\" FIXME XXX In discussing errors for FUTEX_CMP_REQUEUE_PI, Darren Hart

.\"       made the observation that "EINVAL is returned if the non-pi 
.\"       to pi or op pairing semantics are violated."
.\"       Probably there needs to be a general statement about this
.\"       requirement, probably located at about this point in the page.
.\"       Darren (or someone else), care to take a shot at this?

We can probably borrow from either the futex.c comments or the futex-requeue-pi.txt in Documentation. Also, it is important to note that the PI requeue operations require two distinct uadders (although that is implied by requiring "non-pi to pi" as a futex cannot be both.

Or... perhaps something like:

Due to the kernel imposed futex word value policy, PI futex operations have additional usage requirements:

Quoted 3 lines

FUTEX_WAIT_REQUEUE_PI must be paired with FUTEX_CMP_REQUEUE_PI and be performed from a non-pi futex to a distinct pi futex. Failing to do so will return EINVAL.

For which operation does the EINVAL occur: FUTEX_WAIT_REQUEUE_PI or FUTEX_CMP_REQUEUE_PI?

Quoted 2 lines

And their PRIVATE counterparts of course (which is assumed as it is a flag to the opcode).

Yes. But I don't think that needs to be called out explicitly here (?).

Quoted 31 lines

Quoted 20 lines

.\" FIXME XXX ===== Start of adapted Hart/Guniguntala text =====

.\"       The following text is drawn from the Hart/Guniguntala paper
.\"       (listed in SEE ALSO), but I have reworded some pieces
.\"       significantly. Please check it.

The PI futex operations described below differ from the other futex operations in that they impose policy on the use of the value of the futex word:

* If the lock is not acquired, the futex word's value shall be 0.

* If the lock is acquired, the futex word's value shall be the thread ID (TID; see gettid(2)) of the owning thread.

* If the lock is owned and there are threads contending for the lock, then the FUTEX_WAITERS bit shall be set in the futex word's value; in other words, this value is:

Quoted 5 lines

FUTEX_WAITERS | TID

Note that a PI futex word never just has the value FUTEX_WAITERS, which is a permissible state for non-PI futexes.

The second clause is inappropriate. I don't know if that was yours or mine, but non-PI futexes do not have a kernel defined value policy, so ==FUTEX_WAITERS cannot be a "permissible state" as any value is permissible for non-PI futexes, and none have a kernel defined state.

Quoted 4 lines

Perhaps include a Note under the third bullet as:

Note: It is invalid for a PI futex word to have no owner and
FUTEX_WAITERS set.

Done.

Quoted 6 lines

Quoted 2 lines

With this policy in place, a user-space application can acquire a not-acquired lock or release a lock that no other threads try to

"that no other threads try to acquire" seems out of place. I think "atomic instructions" is sufficient to express how contention is handled.

Yup, changed.

Quoted 21 lines

Quoted 14 lines

acquire using atomic instructions executed in user space (e.g., a compare-and-swap operation such as cmpxchg on the x86 architec‐
ture). Acquiring a lock simply consists of using compare-and-
swap to atomically set the futex word's value to the caller's TID if its previous value was 0. Releasing a lock requires using compare-and-swap to set the futex word's value to 0 if the previ‐ ous value was the expected TID.

If a futex is already acquired (i.e., has a nonzero value), wait‐ ers must employ the FUTEX_LOCK_PI operation to acquire the lock. If other threads are waiting for the lock, then the FUTEX_WAITERS bit is set in the futex value; in this case, the lock owner must employ the FUTEX_UNLOCK_PI operation to release the lock.

Quoted 6 lines

In the cases where callers are forced into the kernel (i.e., required to perform a futex() call), they then deal directly with a so-called RT-mutex, a kernel locking mechanism which implements the required priority-inheritance semantics. After the RT-mutex is acquired, the futex value is updated accordingly, before the calling thread returns to user space.

Quoted 4 lines

This last paragraph relies on kernel implementation rather than behavior. If the RT-mutex is renamed or the mechanism is implemented differently in futexes, this section will require updating. Is that appropriate for a user-space man page?

In the end, I'm not sure. This is (so far) my best attempt at trying to convey an explanation of the behavior provided by the API.

results).

But see my question just above. I'll tweak the first bullet point a little after I hear back from you.

Quoted 22 lines · Michael Kerrisk (man-pages)

.\" FIXME XXX ===== Start of adapted Hart/Guniguntala text =====

.\"       The following text is drawn from the Hart/Guniguntala paper
.\"       (listed in SEE ALSO), but I have reworded some pieces
.\"       significantly. Please check it.

The PI futex operations described below differ from the other futex operations in that they impose policy on the use of the value of the futex word:

* If the lock is not acquired, the futex word's value shall be 0.

* If the lock is acquired, the futex word's value shall be the thread ID (TID; see gettid(2)) of the owning thread.

* If the lock is owned and there are threads contending for the lock, then the FUTEX_WAITERS bit shall be set in the futex word's value; in other words, this value is:

FUTEX_WAITERS | TID

Quoted 2 lines

Note that a PI futex word never just has the value FUTEX_WAITERS, which is a permissible state for non-PI futexes.

The second clause is inappropriate. I don't know if that was yours or mine, but non-PI futexes do not have a kernel defined value policy, so ==FUTEX_WAITERS cannot be a "permissible state" as any value is permissible for non-PI futexes, and none have a kernel defined state.

Quoted 9 lines

.\" FIXME I'm not quite clear on the meaning of the following sentence.

.\"       Is this trying to say that while blocked in a
.\"       FUTEX_WAIT_REQUEUE_PI, it could happen that another
.\"       task does a FUTEX_WAKE on uaddr that simply causes
.\"       a normal wake, with the result that the FUTEX_WAIT_REQUEUE_PI
.\"       does not complete? What happens then to the FUTEX_WAIT_REQUEUE_PI
.\"       opertion? Does it remain blocked, or does it unblock
.\"       In which case, what does user space see?

Quoted 3 lines

The
waiter can be removed from the wait on uaddr via
FUTEX_WAKE without requeueing on uaddr2.

Userspace should see the task wake and continue executing. This would effectively be a cancelation operation - which I didn't think was supported. Thomas?

Quoted 26 lines · Darren Hart

Quoted 24 lines · Michael Kerrisk (man-pages)

.\" FIXME XXX ===== Start of adapted Hart/Guniguntala text =====

.\"       The following text is drawn from the Hart/Guniguntala paper
.\"       (listed in SEE ALSO), but I have reworded some pieces
.\"       significantly. Please check it.

The PI futex operations described below differ from the other futex operations in that they impose policy on the use of the value of the futex word:

* If the lock is not acquired, the futex word's value shall be 0.

* If the lock is acquired, the futex word's value shall be the thread ID (TID; see gettid(2)) of the owning thread.

* If the lock is owned and there are threads contending for the lock, then the FUTEX_WAITERS bit shall be set in the futex word's value; in other words, this value is:

FUTEX_WAITERS | TID

Note that a PI futex word never just has the value FUTEX_WAITERS, which is a permissible state for non-PI futexes.

Quoted 4 lines

The second clause is inappropriate. I don't know if that was yours or mine, but non-PI futexes do not have a kernel defined value policy, so ==FUTEX_WAITERS cannot be a "permissible state" as any value is permissible for non-PI futexes, and none have a kernel defined state.

Depends. If the regular futex is configured as robust, then we have a kernel defined value policy as well.

Quoted 26 lines · Darren Hart

Quoted 24 lines · Michael Kerrisk (man-pages)

.\" FIXME XXX ===== Start of adapted Hart/Guniguntala text =====

.\"       The following text is drawn from the Hart/Guniguntala paper
.\"       (listed in SEE ALSO), but I have reworded some pieces
.\"       significantly. Please check it.

The PI futex operations described below differ from the other futex operations in that they impose policy on the use of the value of the futex word:

* If the lock is not acquired, the futex word's value shall be 0.

* If the lock is acquired, the futex word's value shall be the thread ID (TID; see gettid(2)) of the owning thread.

* If the lock is owned and there are threads contending for the lock, then the FUTEX_WAITERS bit shall be set in the futex word's value; in other words, this value is:

FUTEX_WAITERS | TID

Note that a PI futex word never just has the value FUTEX_WAITERS, which is a permissible state for non-PI futexes.

Quoted 4 lines

The second clause is inappropriate. I don't know if that was yours or mine, but non-PI futexes do not have a kernel defined value policy, so ==FUTEX_WAITERS cannot be a "permissible state" as any value is permissible for non-PI futexes, and none have a kernel defined state.

Depends. If the regular futex is configured as robust, then we have a kernel defined value policy as well.

Quoted 13 lines

Quoted 12 lines

.\" FIXME I'm not quite clear on the meaning of the following sentence.

.\"       Is this trying to say that while blocked in a
.\"       FUTEX_WAIT_REQUEUE_PI, it could happen that another
.\"       task does a FUTEX_WAKE on uaddr that simply causes
.\"       a normal wake, with the result that the FUTEX_WAIT_REQUEUE_PI
.\"       does not complete? What happens then to the FUTEX_WAIT_REQUEUE_PI
.\"       opertion? Does it remain blocked, or does it unblock
.\"       In which case, what does user space see?

The
waiter can be removed from the wait on uaddr via
FUTEX_WAKE without requeueing on uaddr2.

Quoted 3 lines

Userspace should see the task wake and continue executing. This would effectively be a cancelation operation - which I didn't think was supported. Thomas?

We probably never intended to support it, but looking at the code it works (did not try it though). It returns to user space with -EWOULDBLOCK. So it basically behaves like any other spurious wakeup.

Quoted 27 lines · Thomas Gleixner

Quoted 26 lines · Darren Hart

Quoted 24 lines · Michael Kerrisk (man-pages)

.\" FIXME XXX ===== Start of adapted Hart/Guniguntala text =====

.\"       The following text is drawn from the Hart/Guniguntala paper
.\"       (listed in SEE ALSO), but I have reworded some pieces
.\"       significantly. Please check it.

The PI futex operations described below differ from the other futex operations in that they impose policy on the use of the value of the futex word:

* If the lock is not acquired, the futex word's value shall be 0.

* If the lock is acquired, the futex word's value shall be the thread ID (TID; see gettid(2)) of the owning thread.

* If the lock is owned and there are threads contending for the lock, then the FUTEX_WAITERS bit shall be set in the futex word's value; in other words, this value is:

FUTEX_WAITERS | TID

Note that a PI futex word never just has the value FUTEX_WAITERS, which is a permissible state for non-PI futexes.

Quoted 7 lines

Quoted 4 lines

The second clause is inappropriate. I don't know if that was yours or mine, but non-PI futexes do not have a kernel defined value policy, so ==FUTEX_WAITERS cannot be a "permissible state" as any value is permissible for non-PI futexes, and none have a kernel defined state.

Depends. If the regular futex is configured as robust, then we have a kernel defined value policy as well.

Okay -- so do we need a change to the text here?

Quoted 18 lines

Quoted 17 lines

Quoted 10 lines

.\" FIXME I'm not quite clear on the meaning of the following sentence.

.\"       Is this trying to say that while blocked in a
.\"       FUTEX_WAIT_REQUEUE_PI, it could happen that another
.\"       task does a FUTEX_WAKE on uaddr that simply causes
.\"       a normal wake, with the result that the FUTEX_WAIT_REQUEUE_PI
.\"       does not complete? What happens then to the FUTEX_WAIT_REQUEUE_PI
.\"       opertion? Does it remain blocked, or does it unblock
.\"       In which case, what does user space see?

Quoted 3 lines

The
waiter can be removed from the wait on uaddr via
FUTEX_WAKE without requeueing on uaddr2.

Userspace should see the task wake and continue executing. This would effectively be a cancelation operation - which I didn't think was supported. Thomas?

Quoted 3 lines

We probably never intended to support it, but looking at the code it works (did not try it though). It returns to user space with -EWOULDBLOCK. So it basically behaves like any other spurious wakeup.

Again, I assume no changes are required to the man page(?).