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

[Michael Kerrisk (man-pages)]

Hi Thomas,

Thank you for the comments below. This helps hugely:
more than 30 of my FIXMEs have now gone away!

I have a few open questions, which you can find
by searching for the string "???". If you would have
a chance to look at those, I'd appreciate it.

On 07/28/2015 10:23 PM, Thomas Gleixner wrote:
> On Mon, 27 Jul 2015, Michael Kerrisk (man-pages) wrote:
>>        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.
> 
> That's correct.

Thanks.

>>        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?
> 
> Yes.

Thanks.

> 
>>               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.
> 
>> 		  If timeout is NULL, the call blocks indefâ
>>               initely.
> 
> Right.

Thanks. Reworded as you suggest. 

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

So, this got picked up in a little subthread by Peter Zijsltra. I'll
reply there.

>>               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.
> 
> Yes, just remove it.

Done.

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

Yep. I dealt with this in an earlier response to mail from Darren (where 
you also replied). I've removed the warning that FUTEX_REQUEUE is broken.

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

>>               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.)
> 
> It's correct.

Thanks.

>> .\" 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 ...

Thanks, I used a lot of that text.

[...]

>>        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â
> 
> 		s/is less efficient/can be less efficient/
> 
> It really depends on the usecase.

Thanks. Amended as you suggest.

>>               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 =====
> 
> That's correct.

Thanks.

>> .\" 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.

Okay -- thanks. I've noted these details, but need to consider more about
what changes (if any) are needed to the page.

>> .\" 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.

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

>> .\" 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.

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


>>        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.)
> 
> Yes.

Thanks.

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

Okay. , I removed "that fails, or"
> 
> 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();   

Thanks, I filed the above point away as a comment in the source.

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

Thanks, I've reworked this passage somewhat, to read:

              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.  If
              the  futex  word's value is nonzero, the kernel 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:

              1. Tries to find the thread which is associated  with  the
                 owner TID.

              2. Creates  or reuses kernel state on behalf of the owner.
                 (If this is the first waiter, there is no kernel  state
                 for  this  futex, so kernel state is created by locking
                 the RT-mutex and the futex owner is made the  owner  of
                 the  RT-mutex.  If there are existing waiters, then the
                 existing state is reused.)

              3. Attaches the waiter to it (i.e., the waiter is enqueued
                 on the RT-mutex waiter list).

>> .\" 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.

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


>> .\" 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.

Thanks!

>> .\" 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.

Thanks.

By now, I have reworded this passage to read:

             If  more  than  one  waiter  exists, the enqueueing of the
              waiter is in descending priority order.  (For  information
              on   priority   ordering,   see   the  discussion  of  the
              SCHED_DEADLINE, SCHED_FIFO, and SCHED_RR scheduling  poliâ
              cies in sched(7).)  The owner inherits either the waiter's
              CPU bandwidth  (if  the  waiter  is  scheduled  under  the
              SCHED_DEADLINE  policy)  or  the waiter's priority (if the
              waiter is scheduled under the SCHED_RR or SCHED_FIFO  polâ
              icy).  This inheritance follows the lock chain in the case
              of nested locking (i.e., task 1 blocks on lock A, held  by
              task 2, while task 2 blocks on lock B, held by task 3) 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.
> 
> Indeed.

Thanks.

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

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


>>               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?
>>
> 
> And they never will be supported because they make no sense at all.  

Okay, thanks. I've removed that FIXME.

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

Thanks. I've done a little rewording here. See below.

>> .\" 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.

Thanks.

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

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


>> .\" 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.
> 
> Correct

Thanks.

>> .\" 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

Thanks.

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

[...]

>> 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. --triegel@xxxxxxxxxx]
> 
> This part should be removed:
> 
>       "(This  probably  indicates  a  race;  use the safe FUTEX_WAKE now.)

Thanks. Done.

>>
>>        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.)
> 
>   Yes. It's the same internal logic so it can return EAGAIN

Thanks.

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

Thanks.

>>
>> .\" 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.

Okay.

[...]

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

Thanks.


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

Thanks. I added "[via FUTEX_WAIT] or FUTEX_WAIT_BITSET".

>>
>>        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.
> 
> Correct. That handles the case:
> 
> 	 wait_requeue_pi(A, B);
> 	 requeue_pi(A, C);

Thanks.

[...]

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

Thanks.

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

Thanks.

Cheers,

Michael

PS: The latest version of the page can be found in its entirety at
http://git.kernel.org/cgit/docs/man-pages/man-pages.git/log/?h=draft_futex

-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/