1FUTEX(2)                   Linux Programmer's Manual                  FUTEX(2)
2
3
4

NAME

6       futex - fast user-space locking
7

SYNOPSIS

9       #include <linux/futex.h>
10       #include <sys/time.h>
11
12       int futex(int *uaddr, int futex_op, int val,
13                 const struct timespec *timeout,   /* or: uint32_t val2 */
14                 int *uaddr2, int val3);
15
16       Note: There is no glibc wrapper for this system call; see NOTES.
17

DESCRIPTION

19       The  futex()  system call provides a method for waiting until a certain
20       condition becomes true.  It is typically used as a  blocking  construct
21       in  the  context of shared-memory synchronization.  When using futexes,
22       the majority of the synchronization operations are  performed  in  user
23       space.   A user-space program employs the futex() system call only when
24       it is likely that the program has to block for a longer time until  the
25       condition  becomes  true.  Other futex() operations can be used to wake
26       any processes or threads waiting for a particular condition.
27
28       A futex is a 32-bit value—referred  to  below  as  a  futex  word—whose
29       address  is  supplied to the futex() system call.  (Futexes are 32 bits
30       in size on all platforms, including 64-bit systems.)  All futex  opera‐
31       tions  are  governed  by this value.  In order to share a futex between
32       processes, the futex is placed in a region of  shared  memory,  created
33       using  (for  example)  mmap(2)  or shmat(2).  (Thus, the futex word may
34       have different virtual addresses  in  different  processes,  but  these
35       addresses  all  refer  to  the same location in physical memory.)  In a
36       multithreaded program, it is sufficient to place the futex  word  in  a
37       global variable shared by all threads.
38
39       When  executing  a futex operation that requests to block a thread, the
40       kernel will block only if the futex word has the value that the calling
41       thread  supplied  (as  one of the arguments of the futex() call) as the
42       expected value of the futex word.  The  loading  of  the  futex  word's
43       value,  the  comparison  of that value with the expected value, and the
44       actual blocking will happen atomically and will be totally ordered with
45       respect to concurrent operations performed by other threads on the same
46       futex word.  Thus, the futex word is used to connect  the  synchroniza‐
47       tion  in  user space with the implementation of blocking by the kernel.
48       Analogously to an atomic  compare-and-exchange  operation  that  poten‐
49       tially  changes  shared  memory, blocking via a futex is an atomic com‐
50       pare-and-block operation.
51
52       One use of futexes is for implementing locks.  The state  of  the  lock
53       (i.e.,  acquired  or  not acquired) can be represented as an atomically
54       accessed flag in shared memory.  In the uncontended case, a thread  can
55       access  or  modify the lock state with atomic instructions, for example
56       atomically changing it from not acquired to acquired  using  an  atomic
57       compare-and-exchange  instruction.   (Such  instructions  are performed
58       entirely in user mode, and the kernel maintains  no  information  about
59       the  lock state.)  On the other hand, a thread may be unable to acquire
60       a lock because it is already acquired by another thread.  It  then  may
61       pass  the  lock's  flag  as a futex word and the value representing the
62       acquired state as the expected value to a futex() wait operation.  This
63       futex()  operation will block if and only if the lock is still acquired
64       (i.e., the value in the futex word still matches the "acquired state").
65       When  releasing the lock, a thread has to first reset the lock state to
66       not acquired and then execute a  futex  operation  that  wakes  threads
67       blocked  on  the  lock  flag  used as a futex word (this can be further
68       optimized to avoid unnecessary wake-ups).  See futex(7) for more detail
69       on how to use futexes.
70
71       Besides  the basic wait and wake-up futex functionality, there are fur‐
72       ther futex operations aimed at supporting more complex use cases.
73
74       Note that no explicit initialization or destruction is necessary to use
75       futexes; the kernel maintains a futex (i.e., the kernel-internal imple‐
76       mentation artifact) only while operations such as FUTEX_WAIT, described
77       below, are being performed on a particular futex word.
78
79   Arguments
80       The uaddr argument points to the futex word.  On all platforms, futexes
81       are four-byte integers that must be aligned on  a  four-byte  boundary.
82       The  operation  to  perform  on  the futex is specified in the futex_op
83       argument; val is a value whose meaning and purpose depends on futex_op.
84
85       The remaining arguments (timeout, uaddr2, and val3) are  required  only
86       for  certain  of  the  futex  operations described below.  Where one of
87       these arguments is not required, it is ignored.
88
89       For several blocking operations, the timeout argument is a pointer to a
90       timespec  structure  that  specifies a timeout for the operation.  How‐
91       ever,  notwithstanding the prototype shown above, for some  operations,
92       the  least  significant four bytes of this argument are instead used as
93       an integer whose meaning is determined by  the  operation.   For  these
94       operations,  the kernel casts the timeout value first to unsigned long,
95       then to uint32_t, and in the remainder of this page, this  argument  is
96       referred to as val2 when interpreted in this fashion.
97
98       Where  it  is  required,  the  uaddr2 argument is a pointer to a second
99       futex word that is employed by the operation.
100
101       The interpretation of the final integer argument, val3, depends on  the
102       operation.
103
104   Futex operations
105       The  futex_op  argument consists of two parts: a command that specifies
106       the operation to be performed, bit-wise ORed with zero or more  options
107       that  modify  the  behaviour of the operation.  The options that may be
108       included in futex_op are as follows:
109
110       FUTEX_PRIVATE_FLAG (since Linux 2.6.22)
111              This option bit can be employed with all futex  operations.   It
112              tells  the  kernel  that  the  futex  is process-private and not
113              shared with another process (i.e., it is being used for synchro‐
114              nization only between threads of the same process).  This allows
115              the kernel to make some additional performance optimizations.
116
117              As a convenience, <linux/futex.h> defines  a  set  of  constants
118              with  the  suffix  _PRIVATE  that  are equivalents of all of the
119              operations listed below, but with  the  FUTEX_PRIVATE_FLAG  ORed
120              into  the  constant  value.  Thus, there are FUTEX_WAIT_PRIVATE,
121              FUTEX_WAKE_PRIVATE, and so on.
122
123       FUTEX_CLOCK_REALTIME (since Linux 2.6.28)
124              This option bit can be employed only with the FUTEX_WAIT_BITSET,
125              FUTEX_WAIT_REQUEUE_PI,  and  (since Linux 4.5) FUTEX_WAIT opera‐
126              tions.
127
128              If this option is set, the kernel measures the  timeout  against
129              the CLOCK_REALTIME clock.
130
131              If  this  option  is  not  set,  the kernel measures the timeout
132              against the CLOCK_MONOTONIC clock.
133
134       The operation specified in futex_op is one of the following:
135
136       FUTEX_WAIT (since Linux 2.6.0)
137              This operation tests that the value at the futex word pointed to
138              by  the address uaddr still contains the expected value val, and
139              if so, then sleeps waiting for a  FUTEX_WAKE  operation  on  the
140              futex  word.   The  load  of  the  value of the futex word is an
141              atomic memory access (i.e., using atomic machine instructions of
142              the  respective  architecture).   This load, the comparison with
143              the expected value, and starting to sleep are  performed  atomi‐
144              cally and totally ordered with respect to other futex operations
145              on the same futex word.  If the thread starts to  sleep,  it  is
146              considered a waiter on this futex word.  If the futex value does
147              not match val, then the call fails immediately  with  the  error
148              EAGAIN.
149
150              The purpose of the comparison with the expected value is to pre‐
151              vent lost wake-ups.  If another thread changed the value of  the
152              futex  word  after  the calling thread decided to block based on
153              the prior value, and if the other thread executed  a  FUTEX_WAKE
154              operation (or similar wake-up) after the value change and before
155              this FUTEX_WAIT operation, then the calling thread will  observe
156              the value change and will not start to sleep.
157
158              If the timeout is not NULL, the structure it points to specifies
159              a timeout for the wait.  (This interval will be  rounded  up  to
160              the  system  clock  granularity, and is guaranteed not to expire
161              early.)  The timeout is by default  measured  according  to  the
162              CLOCK_MONOTONIC  clock, but, since Linux 4.5, the CLOCK_REALTIME
163              clock can be  selected  by  specifying  FUTEX_CLOCK_REALTIME  in
164              futex_op.  If timeout is NULL, the call blocks indefinitely.
165
166              Note:  for  FUTEX_WAIT,  timeout  is  interpreted  as a relative
167              value.  This differs from other futex operations, where  timeout
168              is  interpreted  as an absolute value.  To obtain the equivalent
169              of FUTEX_WAIT with an absolute timeout, employ FUTEX_WAIT_BITSET
170              with val3 specified as FUTEX_BITSET_MATCH_ANY.
171
172              The arguments uaddr2 and val3 are ignored.
173
174       FUTEX_WAKE (since Linux 2.6.0)
175              This operation wakes at most val of the waiters that are waiting
176              (e.g., inside FUTEX_WAIT) on  the  futex  word  at  the  address
177              uaddr.   Most  commonly, val is specified as either 1 (wake up a
178              single waiter) or INT_MAX (wake up all waiters).   No  guarantee
179              is  provided about which waiters are awoken (e.g., a waiter with
180              a higher scheduling priority is not guaranteed to be  awoken  in
181              preference to a waiter with a lower priority).
182
183              The arguments timeout, uaddr2, and val3 are ignored.
184
185       FUTEX_FD (from Linux 2.6.0 up to and including Linux 2.6.25)
186              This operation creates a file descriptor that is associated with
187              the futex at uaddr.  The caller must  close  the  returned  file
188              descriptor after use.  When another process or thread performs a
189              FUTEX_WAKE on the futex word, the file descriptor  indicates  as
190              being readable with select(2), poll(2), and epoll(7)
191
192              The file descriptor can be used to obtain asynchronous notifica‐
193              tions: if val is nonzero, then, when another process  or  thread
194              executes a FUTEX_WAKE, the caller will receive the signal number
195              that was passed in val.
196
197              The arguments timeout, uaddr2 and val3 are ignored.
198
199              Because it was inherently racy, FUTEX_FD has been  removed  from
200              Linux 2.6.26 onward.
201
202       FUTEX_REQUEUE (since Linux 2.6.0)
203              This  operation performs the same task as FUTEX_CMP_REQUEUE (see
204              below), except that no check is made using the  value  in  val3.
205              (The argument val3 is ignored.)
206
207       FUTEX_CMP_REQUEUE (since Linux 2.6.7)
208              This  operation  first  checks  whether the location uaddr still
209              contains the value val3.  If not, the operation fails  with  the
210              error  EAGAIN.   Otherwise,  the operation wakes up a maximum of
211              val waiters that are waiting on the futex at  uaddr.   If  there
212              are  more  than  val  waiters,  then  the  remaining waiters are
213              removed from the wait queue of the source  futex  at  uaddr  and
214              added to the wait queue of the target futex at uaddr2.  The val2
215              argument specifies an upper limit on the number of waiters  that
216              are requeued to the futex at uaddr2.
217
218              The  load  from  uaddr  is  an atomic memory access (i.e., using
219              atomic machine instructions  of  the  respective  architecture).
220              This  load,  the comparison with val3, and the requeueing of any
221              waiters  are  performed  atomically  and  totally  ordered  with
222              respect to other operations on the same futex word.
223
224              Typical  values  to  specify  for  val  are 0 or 1.  (Specifying
225              INT_MAX   is   not   useful,   because   it   would   make   the
226              FUTEX_CMP_REQUEUE  operation  equivalent  to  FUTEX_WAKE.)   The
227              limit value specified via val2 is typically either 1 or INT_MAX.
228              (Specifying  the  argument  as 0 is not useful, because it would
229              make the FUTEX_CMP_REQUEUE operation equivalent to FUTEX_WAIT.)
230
231              The FUTEX_CMP_REQUEUE operation was added as a  replacement  for
232              the  earlier FUTEX_REQUEUE.  The difference is that the check of
233              the value at uaddr can be used to ensure that requeueing happens
234              only  under  certain conditions, which allows race conditions to
235              be avoided in certain use cases.
236
237              Both FUTEX_REQUEUE and FUTEX_CMP_REQUEUE can be  used  to  avoid
238              "thundering   herd"   wake-ups   that  could  occur  when  using
239              FUTEX_WAKE in cases where all of the waiters that are woken need
240              to  acquire  another  futex.   Consider  the following scenario,
241              where multiple waiter threads are waiting on  B,  a  wait  queue
242              implemented using a futex:
243
244                  lock(A)
245                  while (!check_value(V)) {
246                      unlock(A);
247                      block_on(B);
248                      lock(A);
249                  };
250                  unlock(A);
251
252              If a waker thread used FUTEX_WAKE, then all waiters waiting on B
253              would be woken up, and they would all try  to  acquire  lock  A.
254              However,  waking  all  of  the  threads  in this manner would be
255              pointless because all except one of the  threads  would  immedi‐
256              ately  block  on lock A again.  By contrast, a requeue operation
257              wakes just one waiter and moves the other waiters to lock A, and
258              when  the  woken  waiter unlocks A then the next waiter can pro‐
259              ceed.
260
261       FUTEX_WAKE_OP (since Linux 2.6.14)
262              This operation was added to support some  user-space  use  cases
263              where more than one futex must be handled at the same time.  The
264              most notable example is the implementation of  pthread_cond_sig‐
265              nal(3),  which  requires operations on two futexes, the one used
266              to implement the mutex and the one used in the implementation of
267              the   wait   queue   associated  with  the  condition  variable.
268              FUTEX_WAKE_OP allows such cases to be implemented without  lead‐
269              ing to high rates of contention and context switching.
270
271              The  FUTEX_WAKE_OP operation is equivalent to executing the fol‐
272              lowing code atomically and totally ordered with respect to other
273              futex operations on any of the two supplied futex words:
274
275                  int oldval = *(int *) uaddr2;
276                  *(int *) uaddr2 = oldval op oparg;
277                  futex(uaddr, FUTEX_WAKE, val, 0, 0, 0);
278                  if (oldval cmp cmparg)
279                      futex(uaddr2, FUTEX_WAKE, val2, 0, 0, 0);
280
281              In other words, FUTEX_WAKE_OP does the following:
282
283              *  saves the original value of the futex word at uaddr2 and per‐
284                 forms an operation to  modify  the  value  of  the  futex  at
285                 uaddr2;  this  is  an  atomic read-modify-write memory access
286                 (i.e., using atomic machine instructions  of  the  respective
287                 architecture)
288
289              *  wakes  up a maximum of val waiters on the futex for the futex
290                 word at uaddr; and
291
292              *  dependent on the results of a test of the original  value  of
293                 the  futex word at uaddr2, wakes up a maximum of val2 waiters
294                 on the futex for the futex word at uaddr2.
295
296              The operation and  comparison  that  are  to  be  performed  are
297              encoded  in  the  bits  of  the argument val3.  Pictorially, the
298              encoding is:
299
300                      +---+---+-----------+-----------+
301                      |op |cmp|   oparg   |  cmparg   |
302                      +---+---+-----------+-----------+
303                        4   4       12          12    <== # of bits
304
305              Expressed in code, the encoding is:
306
307                  #define FUTEX_OP(op, oparg, cmp, cmparg) \
308                                  (((op & 0xf) << 28) | \
309                                  ((cmp & 0xf) << 24) | \
310                                  ((oparg & 0xfff) << 12) | \
311                                  (cmparg & 0xfff))
312
313              In the above, op and cmp are each one of the codes listed below.
314              The  oparg  and  cmparg  components  are literal numeric values,
315              except as noted below.
316
317              The op component has one of the following values:
318
319                  FUTEX_OP_SET        0  /* uaddr2 = oparg; */
320                  FUTEX_OP_ADD        1  /* uaddr2 += oparg; */
321                  FUTEX_OP_OR         2  /* uaddr2 |= oparg; */
322                  FUTEX_OP_ANDN       3  /* uaddr2 &= ~oparg; */
323                  FUTEX_OP_XOR        4  /* uaddr2 ^= oparg; */
324
325              In addition, bit-wise ORing the following value into  op  causes
326              (1 << oparg) to be used as the operand:
327
328                  FUTEX_OP_ARG_SHIFT  8  /* Use (1 << oparg) as operand */
329
330              The cmp field is one of the following:
331
332                  FUTEX_OP_CMP_EQ     0  /* if (oldval == cmparg) wake */
333                  FUTEX_OP_CMP_NE     1  /* if (oldval != cmparg) wake */
334                  FUTEX_OP_CMP_LT     2  /* if (oldval < cmparg) wake */
335                  FUTEX_OP_CMP_LE     3  /* if (oldval <= cmparg) wake */
336                  FUTEX_OP_CMP_GT     4  /* if (oldval > cmparg) wake */
337                  FUTEX_OP_CMP_GE     5  /* if (oldval >= cmparg) wake */
338
339              The  return  value  of FUTEX_WAKE_OP is the sum of the number of
340              waiters woken on the futex uaddr  plus  the  number  of  waiters
341              woken on the futex uaddr2.
342
343       FUTEX_WAIT_BITSET (since Linux 2.6.25)
344              This  operation  is  like FUTEX_WAIT except that val3 is used to
345              provide a 32-bit bit mask to the  kernel.   This  bit  mask,  in
346              which  at  least  one  bit must be set, is stored in the kernel-
347              internal  state  of  the  waiter.   See   the   description   of
348              FUTEX_WAKE_BITSET for further details.
349
350              If  timeout is not NULL, the structure it points to specifies an
351              absolute timeout for the wait operation.  If  timeout  is  NULL,
352              the operation can block indefinitely.
353
354              The uaddr2 argument is ignored.
355
356       FUTEX_WAKE_BITSET (since Linux 2.6.25)
357              This  operation  is  the same as FUTEX_WAKE except that the val3
358              argument is used to provide a 32-bit bit  mask  to  the  kernel.
359              This bit mask, in which at least one bit must be set, is used to
360              select which waiters should be woken up.  The selection is  done
361              by  a  bit-wise  AND  of the "wake" bit mask (i.e., the value in
362              val3) and the bit mask which is stored  in  the  kernel-internal
363              state  of  the  waiter  (the  "wait"  bit mask that is set using
364              FUTEX_WAIT_BITSET).  All of the waiters for which the result  of
365              the  AND is nonzero are woken up; the remaining waiters are left
366              sleeping.
367
368              The effect of  FUTEX_WAIT_BITSET  and  FUTEX_WAKE_BITSET  is  to
369              allow selective wake-ups among multiple waiters that are blocked
370              on the same futex.  However, note that,  depending  on  the  use
371              case,  employing  this  bit-mask multiplexing feature on a futex
372              can be  less  efficient  than  simply  using  multiple  futexes,
373              because  employing  bit-mask multiplexing requires the kernel to
374              check all waiters on a  futex,  including  those  that  are  not
375              interested  in  being woken up (i.e., they do not have the rele‐
376              vant bit set in their "wait" bit mask).
377
378              The constant FUTEX_BITSET_MATCH_ANY, which corresponds to all 32
379              bits  set  in the bit mask, can be used as the val3 argument for
380              FUTEX_WAIT_BITSET and FUTEX_WAKE_BITSET.  Other than differences
381              in  the  handling of the timeout argument, the FUTEX_WAIT opera‐
382              tion is equivalent to FUTEX_WAIT_BITSET with val3  specified  as
383              FUTEX_BITSET_MATCH_ANY;  that  is, allow a wake-up by any waker.
384              The FUTEX_WAKE operation is equivalent to FUTEX_WAKE_BITSET with
385              val3  specified  as FUTEX_BITSET_MATCH_ANY; that is, wake up any
386              waiter(s).
387
388              The uaddr2 and timeout arguments are ignored.
389
390   Priority-inheritance futexes
391       Linux supports priority-inheritance (PI) futexes  in  order  to  handle
392       priority-inversion  problems  that can be encountered with normal futex
393       locks.  Priority inversion is the problem that occurs when a  high-pri‐
394       ority  task is blocked waiting to acquire a lock held by a low-priority
395       task, while tasks at an intermediate priority continuously preempt  the
396       low-priority  task  from  the CPU.  Consequently, the low-priority task
397       makes no progress toward releasing the lock, and the high-priority task
398       remains blocked.
399
400       Priority  inheritance  is  a  mechanism  for dealing with the priority-
401       inversion problem.  With this  mechanism,  when  a  high-priority  task
402       becomes  blocked by a lock held by a low-priority task, the priority of
403       the low-priority task is temporarily raised to that of the  high-prior‐
404       ity  task, so that it is not preempted by any intermediate level tasks,
405       and can thus make progress toward releasing the lock.  To be effective,
406       priority  inheritance must be transitive, meaning that if a high-prior‐
407       ity task blocks on a lock held by a lower-priority task that is  itself
408       blocked  by  a  lock held by another intermediate-priority task (and so
409       on, for chains of arbitrary length), then both of those tasks (or  more
410       generally,  all  of  the  tasks  in a lock chain) have their priorities
411       raised to be the same as the high-priority task.
412
413       From a user-space perspective, what makes a futex PI-aware is a  policy
414       agreement (described below) between user space and the kernel about the
415       value of the futex word, coupled with the use of  the  PI-futex  opera‐
416       tions  described  below.   (Unlike the other futex operations described
417       above, the PI-futex operations are designed for the  implementation  of
418       very specific IPC mechanisms.)
419
420       The  PI-futex  operations  described  below differ from the other futex
421       operations in that they impose policy on the use of the  value  of  the
422       futex word:
423
424       *  If the lock is not acquired, the futex word's value shall be 0.
425
426       *  If  the lock is acquired, the futex word's value shall be the thread
427          ID (TID; see gettid(2)) of the owning thread.
428
429       *  If the lock is owned and there are threads contending for the  lock,
430          then  the  FUTEX_WAITERS bit shall be set in the futex word's value;
431          in other words, this value is:
432
433              FUTEX_WAITERS | TID
434
435          (Note that is invalid for a PI futex  word  to  have  no  owner  and
436          FUTEX_WAITERS set.)
437
438       With  this  policy  in  place,  a user-space application can acquire an
439       unacquired lock or release a lock using atomic instructions executed in
440       user  mode  (e.g.,  a compare-and-swap operation such as cmpxchg on the
441       x86 architecture).  Acquiring a lock simply consists of using  compare-
442       and-swap  to  atomically set the futex word's value to the caller's TID
443       if its previous value was 0.  Releasing a lock requires using  compare-
444       and-swap  to  set the futex word's value to 0 if the previous value was
445       the expected TID.
446
447       If a futex is already acquired (i.e., has  a  nonzero  value),  waiters
448       must  employ the FUTEX_LOCK_PI operation to acquire the lock.  If other
449       threads are waiting for the lock, then the FUTEX_WAITERS bit is set  in
450       the  futex  value;  in  this  case,  the  lock  owner  must  employ the
451       FUTEX_UNLOCK_PI operation to release the lock.
452
453       In the cases where callers are forced into the kernel  (i.e.,  required
454       to  perform  a  futex() call), they then deal directly with a so-called
455       RT-mutex, a kernel locking mechanism which implements the required pri‐
456       ority-inheritance semantics.  After the RT-mutex is acquired, the futex
457       value is updated accordingly, before the calling thread returns to user
458       space.
459
460       It  is  important  to note that the kernel will update the futex word's
461       value prior to returning to user space.  (This prevents the possibility
462       of the futex word's value ending up in an invalid state, such as having
463       an owner but the value being 0, or having waiters but  not  having  the
464       FUTEX_WAITERS bit set.)
465
466       If  a  futex  has an associated RT-mutex in the kernel (i.e., there are
467       blocked waiters) and the owner of the futex/RT-mutex dies unexpectedly,
468       then  the  kernel  cleans up the RT-mutex and hands it over to the next
469       waiter.  This in turn requires that the  user-space  value  is  updated
470       accordingly.   To  indicate  that this is required, the kernel sets the
471       FUTEX_OWNER_DIED bit in the futex word along with the thread ID of  the
472       new  owner.   User  space can detect this situation via the presence of
473       the FUTEX_OWNER_DIED bit and is then responsible for  cleaning  up  the
474       stale state left over by the dead owner.
475
476       PI futexes are operated on by specifying one of the values listed below
477       in futex_op.  Note that the PI futex operations must be used as  paired
478       operations and are subject to some additional requirements:
479
480       *  FUTEX_LOCK_PI   and   FUTEX_TRYLOCK_PI  pair  with  FUTEX_UNLOCK_PI.
481          FUTEX_UNLOCK_PI must be called only on a futex owned by the  calling
482          thread,  as  defined  by the value policy, otherwise the error EPERM
483          results.
484
485       *  FUTEX_WAIT_REQUEUE_PI pairs with FUTEX_CMP_REQUEUE_PI.  This must be
486          performed  from  a non-PI futex to a distinct PI futex (or the error
487          EINVAL results).  Additionally, val (the number  of  waiters  to  be
488          woken) must be 1 (or the error EINVAL results).
489
490       The PI futex operations are as follows:
491
492       FUTEX_LOCK_PI (since Linux 2.6.18)
493              This  operation is used after an attempt to acquire the lock via
494              an atomic user-mode instruction failed because  the  futex  word
495              has a nonzero value—specifically, because it contained the (PID-
496              namespace-specific) TID of the lock owner.
497
498              The operation checks the value of the futex word at the  address
499              uaddr.   If  the value is 0, then the kernel tries to atomically
500              set the futex value to the caller's TID.  If  the  futex  word's
501              value  is  nonzero, the kernel atomically sets the FUTEX_WAITERS
502              bit, which signals the futex owner that  it  cannot  unlock  the
503              futex  in user space atomically by setting the futex value to 0.
504              After that, the kernel:
505
506              1. Tries to find the thread which is associated with  the  owner
507                 TID.
508
509              2. Creates  or  reuses kernel state on behalf of the owner.  (If
510                 this is the first waiter, there is no kernel state  for  this
511                 futex, so kernel state is created by locking the RT-mutex and
512                 the futex owner is made the owner of the RT-mutex.  If  there
513                 are existing waiters, then the existing state is reused.)
514
515              3. Attaches  the  waiter  to  the  futex  (i.e.,  the  waiter is
516                 enqueued on the RT-mutex waiter list).
517
518              If more than one waiter exists, the enqueueing of the waiter  is
519              in  descending  priority  order.   (For  information on priority
520              ordering, see the discussion of the SCHED_DEADLINE,  SCHED_FIFO,
521              and SCHED_RR scheduling policies in sched(7).)  The owner inher‐
522              its either the waiter's CPU bandwidth (if the waiter  is  sched‐
523              uled  under  the SCHED_DEADLINE policy) or the waiter's priority
524              (if the waiter is scheduled under  the  SCHED_RR  or  SCHED_FIFO
525              policy).  This inheritance follows the lock chain in the case of
526              nested locking and performs deadlock detection.
527
528              The timeout argument provides a timeout for  the  lock  attempt.
529              If  timeout is not NULL, the structure it points to specifies an
530              absolute timeout, measured against the CLOCK_REALTIME clock.  If
531              timeout is NULL, the operation will block indefinitely.
532
533              The uaddr2, val, and val3 arguments are ignored.
534
535       FUTEX_TRYLOCK_PI (since Linux 2.6.18)
536              This  operation  tries  to  acquire  the  lock  at uaddr.  It is
537              invoked when a user-space atomic acquire did not succeed because
538              the futex word was not 0.
539
540              Because  the  kernel  has  access to more state information than
541              user space, acquisition of the lock might succeed  if  performed
542              by  the  kernel  in  cases where the futex word (i.e., the state
543              information  accessible  to  use-space)  contains  stale   state
544              (FUTEX_WAITERS  and/or  FUTEX_OWNER_DIED).  This can happen when
545              the owner of the futex died.  User space cannot handle this con‐
546              dition in a race-free manner, but the kernel can fix this up and
547              acquire the futex.
548
549              The uaddr2, val, timeout, and val3 arguments are ignored.
550
551       FUTEX_UNLOCK_PI (since Linux 2.6.18)
552              This operation wakes the top priority waiter that is waiting  in
553              FUTEX_LOCK_PI  on  the futex address provided by the uaddr argu‐
554              ment.
555
556              This is called when the user-space  value  at  uaddr  cannot  be
557              changed atomically from a TID (of the owner) to 0.
558
559              The uaddr2, val, timeout, and val3 arguments are ignored.
560
561       FUTEX_CMP_REQUEUE_PI (since Linux 2.6.31)
562              This  operation  is a PI-aware variant of FUTEX_CMP_REQUEUE.  It
563              requeues waiters that are blocked via  FUTEX_WAIT_REQUEUE_PI  on
564              uaddr  from  a  non-PI source futex (uaddr) to a PI target futex
565              (uaddr2).
566
567              As with FUTEX_CMP_REQUEUE, this operation wakes up a maximum  of
568              val  waiters  that  are waiting on the futex at uaddr.  However,
569              for FUTEX_CMP_REQUEUE_PI, val is required to  be  1  (since  the
570              main  point is to avoid a thundering herd).  The remaining wait‐
571              ers are removed from the wait queue of the source futex at uaddr
572              and added to the wait queue of the target futex at uaddr2.
573
574              The  val2  and  val3  arguments  serve  the same purposes as for
575              FUTEX_CMP_REQUEUE.
576
577       FUTEX_WAIT_REQUEUE_PI (since Linux 2.6.31)
578              Wait on a non-PI futex at uaddr and potentially be requeued (via
579              a  FUTEX_CMP_REQUEUE_PI  operation  in  another  task) onto a PI
580              futex at uaddr2.  The wait operation on uaddr is the same as for
581              FUTEX_WAIT.
582
583              The  waiter  can  be  removed  from  the  wait  on uaddr without
584              requeueing on uaddr2 via a FUTEX_WAKE operation in another task.
585              In this case, the FUTEX_WAIT_REQUEUE_PI operation fails with the
586              error EAGAIN.
587
588              If timeout is not NULL, the structure it points to specifies  an
589              absolute  timeout  for  the wait operation.  If timeout is NULL,
590              the operation can block indefinitely.
591
592              The val3 argument is ignored.
593
594              The FUTEX_WAIT_REQUEUE_PI and FUTEX_CMP_REQUEUE_PI were added to
595              support a fairly specific use case: support for priority-inheri‐
596              tance-aware POSIX threads condition variables.  The idea is that
597              these  operations  should  always  be paired, in order to ensure
598              that user space and the kernel remain in  sync.   Thus,  in  the
599              FUTEX_WAIT_REQUEUE_PI operation, the user-space application pre-
600              specifies the target of the requeue  that  takes  place  in  the
601              FUTEX_CMP_REQUEUE_PI operation.
602

RETURN VALUE

604       In  the  event  of  an error (and assuming that futex() was invoked via
605       syscall(2)), all operations return -1 and set  errno  to  indicate  the
606       cause of the error.
607
608       The  return  value on success depends on the operation, as described in
609       the following list:
610
611       FUTEX_WAIT
612              Returns 0 if the caller was woken up.  Note that a  wake-up  can
613              also  be caused by common futex usage patterns in unrelated code
614              that happened to have previously used the  futex  word's  memory
615              location  (e.g., typical futex-based implementations of Pthreads
616              mutexes can cause this under some conditions).  Therefore, call‐
617              ers should always conservatively assume that a return value of 0
618              can mean a spurious wake-up, and  use  the  futex  word's  value
619              (i.e.,  the user-space synchronization scheme) to decide whether
620              to continue to block or not.
621
622       FUTEX_WAKE
623              Returns the number of waiters that were woken up.
624
625       FUTEX_FD
626              Returns the new file descriptor associated with the futex.
627
628       FUTEX_REQUEUE
629              Returns the number of waiters that were woken up.
630
631       FUTEX_CMP_REQUEUE
632              Returns the total number  of  waiters  that  were  woken  up  or
633              requeued  to  the  futex  for the futex word at uaddr2.  If this
634              value is greater than val, then the difference is the number  of
635              waiters requeued to the futex for the futex word at uaddr2.
636
637       FUTEX_WAKE_OP
638              Returns the total number of waiters that were woken up.  This is
639              the sum of the woken waiters on the two futexes  for  the  futex
640              words at uaddr and uaddr2.
641
642       FUTEX_WAIT_BITSET
643              Returns 0 if the caller was woken up.  See FUTEX_WAIT for how to
644              interpret this correctly in practice.
645
646       FUTEX_WAKE_BITSET
647              Returns the number of waiters that were woken up.
648
649       FUTEX_LOCK_PI
650              Returns 0 if the futex was successfully locked.
651
652       FUTEX_TRYLOCK_PI
653              Returns 0 if the futex was successfully locked.
654
655       FUTEX_UNLOCK_PI
656              Returns 0 if the futex was successfully unlocked.
657
658       FUTEX_CMP_REQUEUE_PI
659              Returns the total number  of  waiters  that  were  woken  up  or
660              requeued  to  the  futex  for the futex word at uaddr2.  If this
661              value is greater than val, then  difference  is  the  number  of
662              waiters requeued to the futex for the futex word at uaddr2.
663
664       FUTEX_WAIT_REQUEUE_PI
665              Returns  0  if the caller was successfully requeued to the futex
666              for the futex word at uaddr2.
667

ERRORS

669       EACCES No read access to the memory of a futex word.
670
671       EAGAIN (FUTEX_WAIT, FUTEX_WAIT_BITSET, FUTEX_WAIT_REQUEUE_PI) The value
672              pointed  to  by uaddr was not equal to the expected value val at
673              the time of the call.
674
675              Note: on Linux, the symbolic names EAGAIN and EWOULDBLOCK  (both
676              of  which  appear  in  different parts of the kernel futex code)
677              have the same value.
678
679       EAGAIN (FUTEX_CMP_REQUEUE, FUTEX_CMP_REQUEUE_PI) The value  pointed  to
680              by uaddr is not equal to the expected value val3.
681
682       EAGAIN (FUTEX_LOCK_PI,   FUTEX_TRYLOCK_PI,   FUTEX_CMP_REQUEUE_PI)  The
683              futex  owner  thread  ID  of  uaddr  (for  FUTEX_CMP_REQUEUE_PI:
684              uaddr2)  is  about to exit, but has not yet handled the internal
685              state cleanup.  Try again.
686
687       EDEADLK
688              (FUTEX_LOCK_PI,  FUTEX_TRYLOCK_PI,   FUTEX_CMP_REQUEUE_PI)   The
689              futex word at uaddr is already locked by the caller.
690
691       EDEADLK
692              (FUTEX_CMP_REQUEUE_PI) While requeueing a waiter to the PI futex
693              for the futex word at uaddr2, the kernel detected a deadlock.
694
695       EFAULT A required pointer argument (i.e., uaddr,  uaddr2,  or  timeout)
696              did not point to a valid user-space address.
697
698       EINTR  A FUTEX_WAIT or FUTEX_WAIT_BITSET operation was interrupted by a
699              signal (see signal(7)).  In kernels before  Linux  2.6.22,  this
700              error  could also be returned for a spurious wakeup; since Linux
701              2.6.22, this no longer happens.
702
703       EINVAL The operation in futex_op is one of those that employs  a  time‐
704              out,  but  the supplied timeout argument was invalid (tv_sec was
705              less than zero, or tv_nsec was not less than 1,000,000,000).
706
707       EINVAL The operation specified in futex_op employs one or both  of  the
708              pointers  uaddr and uaddr2, but one of these does not point to a
709              valid object—that is, the address is not four-byte-aligned.
710
711       EINVAL (FUTEX_WAIT_BITSET, FUTEX_WAKE_BITSET) The bit mask supplied  in
712              val3 is zero.
713
714       EINVAL (FUTEX_CMP_REQUEUE_PI) uaddr equals uaddr2 (i.e., an attempt was
715              made to requeue to the same futex).
716
717       EINVAL (FUTEX_FD) The signal number supplied in val is invalid.
718
719       EINVAL (FUTEX_WAKE,  FUTEX_WAKE_OP,  FUTEX_WAKE_BITSET,  FUTEX_REQUEUE,
720              FUTEX_CMP_REQUEUE)  The kernel detected an inconsistency between
721              the user-space state at uaddr and the kernel state—that  is,  it
722              detected a waiter which waits in FUTEX_LOCK_PI on uaddr.
723
724       EINVAL (FUTEX_LOCK_PI,  FUTEX_TRYLOCK_PI,  FUTEX_UNLOCK_PI)  The kernel
725              detected an inconsistency between the user-space state at  uaddr
726              and the kernel state.  This indicates either state corruption or
727              that the kernel found a waiter on uaddr  which  is  waiting  via
728              FUTEX_WAIT or FUTEX_WAIT_BITSET.
729
730       EINVAL (FUTEX_CMP_REQUEUE_PI)  The  kernel  detected  an  inconsistency
731              between the user-space state at uaddr2  and  the  kernel  state;
732              that is, the kernel detected a waiter which waits via FUTEX_WAIT
733              or FUTEX_WAIT_BITSET on uaddr2.
734
735       EINVAL (FUTEX_CMP_REQUEUE_PI)  The  kernel  detected  an  inconsistency
736              between the user-space state at uaddr and the kernel state; that
737              is, the kernel detected a waiter which waits via  FUTEX_WAIT  or
738              FUTEX_WAIT_BITESET on uaddr.
739
740       EINVAL (FUTEX_CMP_REQUEUE_PI)  The  kernel  detected  an  inconsistency
741              between the user-space state at uaddr and the kernel state; that
742              is,  the  kernel  detected  a  waiter  which  waits on uaddr via
743              FUTEX_LOCK_PI (instead of FUTEX_WAIT_REQUEUE_PI).
744
745       EINVAL (FUTEX_CMP_REQUEUE_PI) An attempt was made to requeue  a  waiter
746              to   a   futex   other  than  that  specified  by  the  matching
747              FUTEX_WAIT_REQUEUE_PI call for that waiter.
748
749       EINVAL (FUTEX_CMP_REQUEUE_PI) The val argument is not 1.
750
751       EINVAL Invalid argument.
752
753       ENFILE (FUTEX_FD) The system-wide limit on the  total  number  of  open
754              files has been reached.
755
756       ENOMEM (FUTEX_LOCK_PI, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) The ker‐
757              nel could not allocate memory to hold state information.
758
759       ENOSYS Invalid operation specified in futex_op.
760
761       ENOSYS The FUTEX_CLOCK_REALTIME option was specified in  futex_op,  but
762              the    accompanying    operation    was    neither   FUTEX_WAIT,
763              FUTEX_WAIT_BITSET, nor FUTEX_WAIT_REQUEUE_PI.
764
765       ENOSYS (FUTEX_LOCK_PI,        FUTEX_TRYLOCK_PI,        FUTEX_UNLOCK_PI,
766              FUTEX_CMP_REQUEUE_PI,  FUTEX_WAIT_REQUEUE_PI)  A  run-time check
767              determined that the operation is not  available.   The  PI-futex
768              operations  are not implemented on all architectures and are not
769              supported on some CPU variants.
770
771       EPERM  (FUTEX_LOCK_PI,  FUTEX_TRYLOCK_PI,   FUTEX_CMP_REQUEUE_PI)   The
772              caller  is  not  allowed  to attach itself to the futex at uaddr
773              (for FUTEX_CMP_REQUEUE_PI: the futex at uaddr2).  (This  may  be
774              caused by a state corruption in user space.)
775
776       EPERM  (FUTEX_UNLOCK_PI)  The  caller does not own the lock represented
777              by the futex word.
778
779       ESRCH  (FUTEX_LOCK_PI,  FUTEX_TRYLOCK_PI,   FUTEX_CMP_REQUEUE_PI)   The
780              thread ID in the futex word at uaddr does not exist.
781
782       ESRCH  (FUTEX_CMP_REQUEUE_PI) The thread ID in the futex word at uaddr2
783              does not exist.
784
785       ETIMEDOUT
786              The operation in futex_op  employed  the  timeout  specified  in
787              timeout, and the timeout expired before the operation completed.
788

VERSIONS

790       Futexes were first made available in a stable kernel release with Linux
791       2.6.0.
792
793       Initial futex support was merged in  Linux  2.5.7  but  with  different
794       semantics  from  what was described above.  A four-argument system call
795       with the semantics described in  this  page  was  introduced  in  Linux
796       2.5.40.   A fifth argument was added in Linux 2.5.70, and a sixth argu‐
797       ment was added in Linux 2.6.7.
798

CONFORMING TO

800       This system call is Linux-specific.
801

NOTES

803       Glibc does not provide a wrapper for this system call;  call  it  using
804       syscall(2).
805
806       Several  higher-level  programming  abstractions  are  implemented  via
807       futexes, including POSIX semaphores and various POSIX threads  synchro‐
808       nization  mechanisms  (mutexes,  condition variables, read-write locks,
809       and barriers).
810

EXAMPLE

812       The program below demonstrates use of futexes in a program where a par‐
813       ent  process and a child process use a pair of futexes located inside a
814       shared anonymous mapping to synchronize access to  a  shared  resource:
815       the  terminal.   The  two  processes  each write nloops (a command-line
816       argument that defaults to 5 if omitted) messages to  the  terminal  and
817       employ  a  synchronization protocol that ensures that they alternate in
818       writing messages.  Upon running this program we see output such as  the
819       following:
820
821           $ ./futex_demo
822           Parent (18534) 0
823           Child  (18535) 0
824           Parent (18534) 1
825           Child  (18535) 1
826           Parent (18534) 2
827           Child  (18535) 2
828           Parent (18534) 3
829           Child  (18535) 3
830           Parent (18534) 4
831           Child  (18535) 4
832
833   Program source
834
835       /* futex_demo.c
836
837          Usage: futex_demo [nloops]
838                           (Default: 5)
839
840          Demonstrate the use of futexes in a program where parent and child
841          use a pair of futexes located inside a shared anonymous mapping to
842          synchronize access to a shared resource: the terminal. The two
843          processes each write 'num-loops' messages to the terminal and employ
844          a synchronization protocol that ensures that they alternate in
845          writing messages.
846       */
847       #define _GNU_SOURCE
848       #include <stdio.h>
849       #include <errno.h>
850       #include <stdlib.h>
851       #include <unistd.h>
852       #include <sys/wait.h>
853       #include <sys/mman.h>
854       #include <sys/syscall.h>
855       #include <linux/futex.h>
856       #include <sys/time.h>
857
858       #define errExit(msg)    do { perror(msg); exit(EXIT_FAILURE); \
859                               } while (0)
860
861       static int *futex1, *futex2, *iaddr;
862
863       static int
864       futex(int *uaddr, int futex_op, int val,
865             const struct timespec *timeout, int *uaddr2, int val3)
866       {
867           return syscall(SYS_futex, uaddr, futex_op, val,
868                          timeout, uaddr, val3);
869       }
870
871       /* Acquire the futex pointed to by 'futexp': wait for its value to
872          become 1, and then set the value to 0. */
873
874       static void
875       fwait(int *futexp)
876       {
877           int s;
878
879           /* __sync_bool_compare_and_swap(ptr, oldval, newval) is a gcc
880              built-in function.  It atomically performs the equivalent of:
881
882                  if (*ptr == oldval)
883                      *ptr = newval;
884
885              It returns true if the test yielded true and *ptr was updated.
886              The alternative here would be to employ the equivalent atomic
887              machine-language instructions.  For further information, see
888              the GCC Manual. */
889
890           while (1) {
891
892               /* Is the futex available? */
893
894               if (__sync_bool_compare_and_swap(futexp, 1, 0))
895                   break;      /* Yes */
896
897               /* Futex is not available; wait */
898
899               s = futex(futexp, FUTEX_WAIT, 0, NULL, NULL, 0);
900               if (s == -1 && errno != EAGAIN)
901                   errExit("futex-FUTEX_WAIT");
902           }
903       }
904
905       /* Release the futex pointed to by 'futexp': if the futex currently
906          has the value 0, set its value to 1 and the wake any futex waiters,
907          so that if the peer is blocked in fpost(), it can proceed. */
908
909       static void
910       fpost(int *futexp)
911       {
912           int s;
913
914           /* __sync_bool_compare_and_swap() was described in comments above */
915
916           if (__sync_bool_compare_and_swap(futexp, 0, 1)) {
917
918               s = futex(futexp, FUTEX_WAKE, 1, NULL, NULL, 0);
919               if (s  == -1)
920                   errExit("futex-FUTEX_WAKE");
921           }
922       }
923
924       int
925       main(int argc, char *argv[])
926       {
927           pid_t childPid;
928           int j, nloops;
929
930           setbuf(stdout, NULL);
931
932           nloops = (argc > 1) ? atoi(argv[1]) : 5;
933
934           /* Create a shared anonymous mapping that will hold the futexes.
935              Since the futexes are being shared between processes, we
936              subsequently use the "shared" futex operations (i.e., not the
937              ones suffixed "_PRIVATE") */
938
939           iaddr = mmap(NULL, sizeof(int) * 2, PROT_READ | PROT_WRITE,
940                       MAP_ANONYMOUS | MAP_SHARED, -1, 0);
941           if (iaddr == MAP_FAILED)
942               errExit("mmap");
943
944           futex1 = &iaddr[0];
945           futex2 = &iaddr[1];
946
947           *futex1 = 0;        /* State: unavailable */
948           *futex2 = 1;        /* State: available */
949
950           /* Create a child process that inherits the shared anonymous
951              mapping */
952
953           childPid = fork();
954           if (childPid == -1)
955               errExit("fork");
956
957           if (childPid == 0) {        /* Child */
958               for (j = 0; j < nloops; j++) {
959                   fwait(futex1);
960                   printf("Child  (%ld) %d\n", (long) getpid(), j);
961                   fpost(futex2);
962               }
963
964               exit(EXIT_SUCCESS);
965           }
966
967           /* Parent falls through to here */
968
969           for (j = 0; j < nloops; j++) {
970               fwait(futex2);
971               printf("Parent (%ld) %d\n", (long) getpid(), j);
972               fpost(futex1);
973           }
974
975           wait(NULL);
976
977           exit(EXIT_SUCCESS);
978       }
979

SEE ALSO

981       get_robust_list(2), restart_syscall(2), pthread_mutexattr_getproto‐
982       col(3), futex(7), sched(7)
983
984       The following kernel source files:
985
986       * Documentation/pi-futex.txt
987
988       * Documentation/futex-requeue-pi.txt
989
990       * Documentation/locking/rt-mutex.txt
991
992       * Documentation/locking/rt-mutex-design.txt
993
994       * Documentation/robust-futex-ABI.txt
995
996       Franke, H., Russell, R., and Kirwood, M., 2002.  Fuss, Futexes and Fur‐
997       wocks: Fast Userlevel Locking in Linux (from proceedings of the Ottawa
998       Linux Symposium 2002),
999http://kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf
1000
1001       Hart, D., 2009. A futex overview and update,
1002http://lwn.net/Articles/360699/
1003
1004       Hart, D. and Guniguntala, D., 2009.  Requeue-PI: Making Glibc Condvars
1005       PI-Aware (from proceedings of the 2009 Real-Time Linux Workshop),
1006http://lwn.net/images/conf/rtlws11/papers/proc/p10.pdf
1007
1008       Drepper, U., 2011. Futexes Are Tricky,
1009http://www.akkadia.org/drepper/futex.pdf
1010
1011       Futex example library, futex-*.tar.bz2 at
1012       ⟨ftp://ftp.kernel.org/pub/linux/kernel/people/rusty/⟩
1013

COLOPHON

1015       This page is part of release 4.16 of the Linux man-pages project.  A
1016       description of the project, information about reporting bugs, and the
1017       latest version of this page, can be found at
1018       https://www.kernel.org/doc/man-pages/.
1019
1020
1021
1022Linux                             2017-09-15                          FUTEX(2)
Impressum