2 .\" and Copyright (C) 2015, Thomas Gleixner <tglx@linutronix.de>
3 .\" and Copyright (C) 2015, Michael Kerrisk <mtk.manpages@gmail.com>
5 .\" %%%LICENSE_START(FREELY_REDISTRIBUTABLE)
6 .\" may be freely modified and distributed
9 .\" Niki A. Rahimi (LTC Security Development, narahimi@us.ibm.com)
10 .\" added ERRORS section.
12 .\" Modified 2004-06-17 mtk
13 .\" Modified 2004-10-07 aeb, added FUTEX_REQUEUE, FUTEX_CMP_REQUEUE
15 .\" FIXME Still to integrate are some points from Torvald Riegel's mail of
17 .\" http://thread.gmane.org/gmane.linux.kernel/1703405/focus=7977
19 .\" FIXME Do we need to add some text regarding Torvald Riegel's 2015-01-24 mail
20 .\" http://thread.gmane.org/gmane.linux.kernel/1703405/focus=1873242
22 .TH FUTEX 2 2021-03-22 "Linux" "Linux Programmer's Manual"
24 futex \- fast user-space locking
28 .BR "#include <linux/futex.h>" " /* Definition of " FUTEX_* " constants */"
29 .BR "#include <sys/syscall.h>" " /* Definition of " SYS_* " constants */"
30 .B #include <unistd.h>
32 .BI "long syscall(SYS_futex, uint32_t *" uaddr ", int " futex_op \
34 .BI " const struct timespec *" timeout , \
35 " \fR /* or: \fBuint32_t \fIval2\fP */"
36 .BI " uint32_t *" uaddr2 ", uint32_t " val3 );
40 glibc provides no wrapper for
42 necessitating the use of
47 system call provides a method for waiting until a certain condition becomes
49 It is typically used as a blocking construct in the context of
50 shared-memory synchronization.
51 When using futexes, the majority of
52 the synchronization operations are performed in user space.
53 A user-space program employs the
55 system call only when it is likely that the program has to block for
56 a longer time until the condition becomes true.
59 operations can be used to wake any processes or threads waiting
60 for a particular condition.
62 A futex is a 32-bit value\(emreferred to below as a
63 .IR "futex word" \(emwhose
64 address is supplied to the
67 (Futexes are 32 bits in size on all platforms, including 64-bit systems.)
68 All futex operations are governed by this value.
69 In order to share a futex between processes,
70 the futex is placed in a region of shared memory,
71 created using (for example)
75 (Thus, the futex word may have different
76 virtual addresses in different processes,
77 but these addresses all refer to the same location in physical memory.)
78 In a multithreaded program, it is sufficient to place the futex word
79 in a global variable shared by all threads.
81 When executing a futex operation that requests to block a thread,
82 the kernel will block only if the futex word has the value that the
83 calling thread supplied (as one of the arguments of the
85 call) as the expected value of the futex word.
86 The loading of the futex word's value,
87 the comparison of that value with the expected value,
88 and the actual blocking will happen atomically and will be totally ordered
89 with respect to concurrent operations performed by other threads
90 on the same futex word.
91 .\" Notes from Darren Hart (Dec 2015):
92 .\" Totally ordered with respect futex operations refers to semantics
93 .\" of the ACQUIRE/RELEASE operations and how they impact ordering of
94 .\" memory reads and writes. The kernel futex operations are protected
95 .\" by spinlocks, which ensure that all operations are serialized
96 .\" with respect to one another.
98 .\" This is a lot to attempt to define in this document. Perhaps a
99 .\" reference to linux/Documentation/memory-barriers.txt as a footnote
100 .\" would be sufficient? Or perhaps for this manual, "serialized" would
101 .\" be sufficient, with a footnote regarding "totally ordered" and a
102 .\" pointer to the memory-barrier documentation?
103 Thus, the futex word is used to connect the synchronization in user space
104 with the implementation of blocking by the kernel.
105 Analogously to an atomic
106 compare-and-exchange operation that potentially changes shared memory,
107 blocking via a futex is an atomic compare-and-block operation.
108 .\" FIXME(Torvald Riegel):
109 .\" Eventually we want to have some text in NOTES to satisfy
110 .\" the reference in the following sentence
111 .\" See NOTES for a detailed specification of
112 .\" the synchronization semantics.
114 One use of futexes is for implementing locks.
115 The state of the lock (i.e., acquired or not acquired)
116 can be represented as an atomically accessed flag in shared memory.
117 In the uncontended case,
118 a thread can access or modify the lock state with atomic instructions,
119 for example atomically changing it from not acquired to acquired
120 using an atomic compare-and-exchange instruction.
121 (Such instructions are performed entirely in user mode,
122 and the kernel maintains no information about the lock state.)
123 On the other hand, a thread may be unable to acquire a lock because
124 it is already acquired by another thread.
125 It then may pass the lock's flag as a futex word and the value
126 representing the acquired state as the expected value to a
131 operation will block if and only if the lock is still acquired
132 (i.e., the value in the futex word still matches the "acquired state").
133 When releasing the lock, a thread has to first reset the
134 lock state to not acquired and then execute a futex
135 operation that wakes threads blocked on the lock flag used as a futex word
136 (this can be further optimized to avoid unnecessary wake-ups).
139 for more detail on how to use futexes.
141 Besides the basic wait and wake-up futex functionality, there are further
142 futex operations aimed at supporting more complex use cases.
145 no explicit initialization or destruction is necessary to use futexes;
146 the kernel maintains a futex
147 (i.e., the kernel-internal implementation artifact)
148 only while operations such as
150 described below, are being performed on a particular futex word.
155 argument points to the futex word.
156 On all platforms, futexes are four-byte
157 integers that must be aligned on a four-byte boundary.
158 The operation to perform on the futex is specified in the
162 is a value whose meaning and purpose depends on
165 The remaining arguments
170 are required only for certain of the futex operations described below.
171 Where one of these arguments is not required, it is ignored.
173 For several blocking operations, the
175 argument is a pointer to a
177 structure that specifies a timeout for the operation.
178 However, notwithstanding the prototype shown above, for some operations,
179 the least significant four bytes of this argument are instead
180 used as an integer whose meaning is determined by the operation.
181 For these operations, the kernel casts the
187 and in the remainder of this page, this argument is referred to as
189 when interpreted in this fashion.
191 Where it is required, the
193 argument is a pointer to a second futex word that is employed
196 The interpretation of the final integer argument,
198 depends on the operation.
200 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
205 argument consists of two parts:
206 a command that specifies the operation to be performed,
207 bitwise ORed with zero or more options that
208 modify the behaviour of the operation.
209 The options that may be included in
213 .BR FUTEX_PRIVATE_FLAG " (since Linux 2.6.22)"
214 .\" commit 34f01cc1f512fa783302982776895c73714ebbc2
215 This option bit can be employed with all futex operations.
216 It tells the kernel that the futex is process-private and not shared
217 with another process (i.e., it is being used for synchronization
218 only between threads of the same process).
219 This allows the kernel to make some additional performance optimizations.
220 .\" I.e., It allows the kernel choose the fast path for validating
221 .\" the user-space address and avoids expensive VMA lookups,
222 .\" taking reference counts on file backing store, and so on.
226 defines a set of constants with the suffix
228 that are equivalents of all of the operations listed below,
229 .\" except the obsolete FUTEX_FD, for which the "private" flag was
232 .BR FUTEX_PRIVATE_FLAG
233 ORed into the constant value.
235 .BR FUTEX_WAIT_PRIVATE ,
236 .BR FUTEX_WAKE_PRIVATE ,
239 .BR FUTEX_CLOCK_REALTIME " (since Linux 2.6.28)"
240 .\" commit 1acdac104668a0834cfa267de9946fac7764d486
241 This option bit can be employed only with the
242 .BR FUTEX_WAIT_BITSET ,
243 .BR FUTEX_WAIT_REQUEUE_PI ,
245 .\" commit 337f13046ff03717a9e99675284a817527440a49
248 (since Linux v5.14.0)
249 .\" commit bf22a6976897977b0a3f1aeba6823c959fc4fdae
253 If this option is set, the kernel measures the
259 If this option is not set, the kernel measures the
265 The operation specified in
267 is one of the following:
269 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
272 .BR FUTEX_WAIT " (since Linux 2.6.0)"
273 .\" Strictly speaking, since some time in 2.5.x
274 This operation tests that the value at the
275 futex word pointed to by the address
277 still contains the expected value
279 and if so, then sleeps waiting for a
281 operation on the futex word.
282 The load of the value of the futex word is an atomic memory
283 access (i.e., using atomic machine instructions of the respective
285 This load, the comparison with the expected value, and
286 starting to sleep are performed atomically
287 .\" FIXME: Torvald, I think we may need to add some explanation of
288 .\" "totally ordered" here.
290 with respect to other futex operations on the same futex word.
291 If the thread starts to sleep,
292 it is considered a waiter on this futex word.
293 If the futex value does not match
295 then the call fails immediately with the error
298 The purpose of the comparison with the expected value is to prevent lost
300 If another thread changed the value of the futex word after the
301 calling thread decided to block based on the prior value,
302 and if the other thread executed a
304 operation (or similar wake-up) after the value change and before this
306 operation, then the calling thread will observe the
307 value change and will not start to sleep.
311 is not NULL, the structure it points to specifies a
312 timeout for the wait.
313 (This interval will be rounded up to the system clock granularity,
314 and is guaranteed not to expire early.)
315 The timeout is by default measured according to the
317 clock, but, since Linux 4.5, the
319 clock can be selected by specifying
320 .BR FUTEX_CLOCK_REALTIME
325 is NULL, the call blocks indefinitely.
334 This differs from other futex operations, where
336 is interpreted as an absolute value.
337 To obtain the equivalent of
339 with an absolute timeout, employ
340 .BR FUTEX_WAIT_BITSET
344 .BR FUTEX_BITSET_MATCH_ANY .
351 .\" FIXME . (Torvald) I think we should remove this. Or maybe adapt to a
352 .\" different example.
356 .\" this call is executed if decrementing the count gave a negative value
357 .\" (indicating contention),
358 .\" and will sleep until another process or thread releases
359 .\" the futex and executes the
363 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
366 .BR FUTEX_WAKE " (since Linux 2.6.0)"
367 .\" Strictly speaking, since Linux 2.5.x
368 This operation wakes at most
370 of the waiters that are waiting (e.g., inside
372 on the futex word at the address
376 is specified as either 1 (wake up a single waiter) or
378 (wake up all waiters).
379 No guarantee is provided about which waiters are awoken
380 (e.g., a waiter with a higher scheduling priority is not guaranteed
381 to be awoken in preference to a waiter with a lower priority).
389 .\" FIXME . (Torvald) I think we should remove this. Or maybe adapt to
390 .\" a different example.
394 .\" this is executed if incrementing the count showed that
395 .\" there were waiters,
396 .\" once the futex value has been set to 1
397 .\" (indicating that it is available).
399 .\" How does "incrementing the count show that there were waiters"?
401 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
404 .BR FUTEX_FD " (from Linux 2.6.0 up to and including Linux 2.6.25)"
405 .\" Strictly speaking, from Linux 2.5.x to 2.6.25
406 This operation creates a file descriptor that is associated with
409 The caller must close the returned file descriptor after use.
410 When another process or thread performs a
412 on the futex word, the file descriptor indicates as being readable with
418 The file descriptor can be used to obtain asynchronous notifications: if
420 is nonzero, then, when another process or thread executes a
422 the caller will receive the signal number that was passed in
432 Because it was inherently racy,
435 .\" commit 82af7aca56c67061420d618cc5a30f0fd4106b80
436 from Linux 2.6.26 onward.
438 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
441 .BR FUTEX_REQUEUE " (since Linux 2.6.0)"
442 This operation performs the same task as
443 .BR FUTEX_CMP_REQUEUE
444 (see below), except that no check is made using the value in
450 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
453 .BR FUTEX_CMP_REQUEUE " (since Linux 2.6.7)"
454 This operation first checks whether the location
456 still contains the value
458 If not, the operation fails with the error
460 Otherwise, the operation wakes up a maximum of
462 waiters that are waiting on the futex at
464 If there are more than
466 waiters, then the remaining waiters are removed
467 from the wait queue of the source futex at
469 and added to the wait queue of the target futex at
473 argument specifies an upper limit on the number of waiters
474 that are requeued to the futex at
477 .\" FIXME(Torvald) Is the following correct? Or is just the decision
478 .\" which threads to wake or requeue part of the atomic operation?
481 is an atomic memory access (i.e., using atomic machine instructions of
482 the respective architecture).
483 This load, the comparison with
485 and the requeueing of any waiters are performed atomically and totally
486 ordered with respect to other operations on the same futex word.
487 .\" Notes from a f2f conversation with Thomas Gleixner (Aug 2015): ###
488 .\" The operation is serialized with respect to operations on both
489 .\" source and target futex. No other waiter can enqueue itself
490 .\" for waiting and no other waiter can dequeue itself because of
491 .\" a timeout or signal.
493 Typical values to specify for
498 is not useful, because it would make the
499 .BR FUTEX_CMP_REQUEUE
500 operation equivalent to
502 The limit value specified via
504 is typically either 1 or
506 (Specifying the argument as 0 is not useful, because it would make the
507 .BR FUTEX_CMP_REQUEUE
508 operation equivalent to
513 operation was added as a replacement for the earlier
515 The difference is that the check of the value at
517 can be used to ensure that requeueing happens only under certain
518 conditions, which allows race conditions to be avoided in certain use cases.
519 .\" But, as Rich Felker points out, there remain valid use cases for
520 .\" FUTEX_REQUEUE, for example, when the calling thread is requeuing
521 .\" the target(s) to a lock that the calling thread owns
522 .\" From: Rich Felker <dalias@libc.org>
523 .\" Date: Wed, 29 Oct 2014 22:43:17 -0400
524 .\" To: Darren Hart <dvhart@infradead.org>
525 .\" CC: libc-alpha@sourceware.org, ...
526 .\" Subject: Re: Add futex wrapper to glibc?
531 .BR FUTEX_CMP_REQUEUE
532 can be used to avoid "thundering herd" wake-ups that could occur when using
534 in cases where all of the waiters that are woken need to acquire
536 Consider the following scenario,
537 where multiple waiter threads are waiting on B,
538 a wait queue implemented using a futex:
543 while (!check_value(V)) {
552 If a waker thread used
554 then all waiters waiting on B would be woken up,
555 and they would all try to acquire lock A.
556 However, waking all of the threads in this manner would be pointless because
557 all except one of the threads would immediately block on lock A again.
558 By contrast, a requeue operation wakes just one waiter and moves
559 the other waiters to lock A,
560 and when the woken waiter unlocks A then the next waiter can proceed.
562 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
565 .BR FUTEX_WAKE_OP " (since Linux 2.6.14)"
566 .\" commit 4732efbeb997189d9f9b04708dc26bf8613ed721
567 .\" Author: Jakub Jelinek <jakub@redhat.com>
568 .\" Date: Tue Sep 6 15:16:25 2005 -0700
569 .\" FIXME. (Torvald) The glibc condvar implementation is currently being
570 .\" revised (e.g., to not use an internal lock anymore).
571 .\" It is probably more future-proof to remove this paragraph.
572 .\" [Torvald, do you have an update here?]
573 This operation was added to support some user-space use cases
574 where more than one futex must be handled at the same time.
575 The most notable example is the implementation of
576 .BR pthread_cond_signal (3),
577 which requires operations on two futexes,
578 the one used to implement the mutex and the one used in the implementation
579 of the wait queue associated with the condition variable.
581 allows such cases to be implemented without leading to
582 high rates of contention and context switching.
586 operation is equivalent to executing the following code atomically
587 and totally ordered with respect to other futex operations on
588 any of the two supplied futex words:
592 uint32_t oldval = *(uint32_t *) uaddr2;
593 *(uint32_t *) uaddr2 = oldval \fIop\fP \fIoparg\fP;
594 futex(uaddr, FUTEX_WAKE, val, 0, 0, 0);
595 if (oldval \fIcmp\fP \fIcmparg\fP)
596 futex(uaddr2, FUTEX_WAKE, val2, 0, 0, 0);
605 saves the original value of the futex word at
607 and performs an operation to modify the value of the futex at
609 this is an atomic read-modify-write memory access (i.e., using atomic
610 machine instructions of the respective architecture)
612 wakes up a maximum of
614 waiters on the futex for the futex word at
618 dependent on the results of a test of the original value of the
621 wakes up a maximum of
623 waiters on the futex for the futex word at
627 The operation and comparison that are to be performed are encoded
628 in the bits of the argument
630 Pictorially, the encoding is:
634 +---+---+-----------+-----------+
635 |op |cmp| oparg | cmparg |
636 +---+---+-----------+-----------+
637 4 4 12 12 <== # of bits
641 Expressed in code, the encoding is:
645 #define FUTEX_OP(op, oparg, cmp, cmparg) \e
646 (((op & 0xf) << 28) | \e
647 ((cmp & 0xf) << 24) | \e
648 ((oparg & 0xfff) << 12) | \e
657 are each one of the codes listed below.
662 components are literal numeric values, except as noted below.
666 component has one of the following values:
670 FUTEX_OP_SET 0 /* uaddr2 = oparg; */
671 FUTEX_OP_ADD 1 /* uaddr2 += oparg; */
672 FUTEX_OP_OR 2 /* uaddr2 |= oparg; */
673 FUTEX_OP_ANDN 3 /* uaddr2 &= \(tioparg; */
674 FUTEX_OP_XOR 4 /* uaddr2 \(ha= oparg; */
678 In addition, bitwise ORing the following value into
682 to be used as the operand:
686 FUTEX_OP_ARG_SHIFT 8 /* Use (1 << oparg) as operand */
692 field is one of the following:
696 FUTEX_OP_CMP_EQ 0 /* if (oldval == cmparg) wake */
697 FUTEX_OP_CMP_NE 1 /* if (oldval != cmparg) wake */
698 FUTEX_OP_CMP_LT 2 /* if (oldval < cmparg) wake */
699 FUTEX_OP_CMP_LE 3 /* if (oldval <= cmparg) wake */
700 FUTEX_OP_CMP_GT 4 /* if (oldval > cmparg) wake */
701 FUTEX_OP_CMP_GE 5 /* if (oldval >= cmparg) wake */
707 is the sum of the number of waiters woken on the futex
709 plus the number of waiters woken on the futex
712 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
715 .BR FUTEX_WAIT_BITSET " (since Linux 2.6.25)"
716 .\" commit cd689985cf49f6ff5c8eddc48d98b9d581d9475d
717 This operation is like
721 is used to provide a 32-bit bit mask to the kernel.
722 This bit mask, in which at least one bit must be set,
723 is stored in the kernel-internal state of the waiter.
724 See the description of
725 .BR FUTEX_WAKE_BITSET
730 is not NULL, the structure it points to specifies
731 an absolute timeout for the wait operation.
734 is NULL, the operation can block indefinitely.
740 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
743 .BR FUTEX_WAKE_BITSET " (since Linux 2.6.25)"
744 .\" commit cd689985cf49f6ff5c8eddc48d98b9d581d9475d
745 This operation is the same as
749 argument is used to provide a 32-bit bit mask to the kernel.
750 This bit mask, in which at least one bit must be set,
751 is used to select which waiters should be woken up.
752 The selection is done by a bitwise AND of the "wake" bit mask
755 and the bit mask which is stored in the kernel-internal
756 state of the waiter (the "wait" bit mask that is set using
757 .BR FUTEX_WAIT_BITSET ).
758 All of the waiters for which the result of the AND is nonzero are woken up;
759 the remaining waiters are left sleeping.
762 .BR FUTEX_WAIT_BITSET
764 .BR FUTEX_WAKE_BITSET
765 is to allow selective wake-ups among multiple waiters that are blocked
767 However, note that, depending on the use case,
768 employing this bit-mask multiplexing feature on a
769 futex can be less efficient than simply using multiple futexes,
770 because employing bit-mask multiplexing requires the kernel
771 to check all waiters on a futex,
772 including those that are not interested in being woken up
773 (i.e., they do not have the relevant bit set in their "wait" bit mask).
774 .\" According to http://locklessinc.com/articles/futex_cheat_sheet/:
776 .\" "The original reason for the addition of these extensions
777 .\" was to improve the performance of pthread read-write locks
778 .\" in glibc. However, the pthreads library no longer uses the
779 .\" same locking algorithm, and these extensions are not used
780 .\" without the bitset parameter being all ones.
782 .\" The page goes on to note that the FUTEX_WAIT_BITSET operation
783 .\" is nevertheless used (with a bit mask of all ones) in order to
784 .\" obtain the absolute timeout functionality that is useful
785 .\" for efficiently implementing Pthreads APIs (which use absolute
786 .\" timeouts); FUTEX_WAIT provides only relative timeouts.
789 .BR FUTEX_BITSET_MATCH_ANY ,
790 which corresponds to all 32 bits set in the bit mask, can be used as the
793 .BR FUTEX_WAIT_BITSET
795 .BR FUTEX_WAKE_BITSET .
796 Other than differences in the handling of the
800 operation is equivalent to
801 .BR FUTEX_WAIT_BITSET
805 .BR FUTEX_BITSET_MATCH_ANY ;
806 that is, allow a wake-up by any waker.
809 operation is equivalent to
810 .BR FUTEX_WAKE_BITSET
814 .BR FUTEX_BITSET_MATCH_ANY ;
815 that is, wake up any waiter(s).
821 arguments are ignored.
823 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
825 .SS Priority-inheritance futexes
826 Linux supports priority-inheritance (PI) futexes in order to handle
827 priority-inversion problems that can be encountered with
829 Priority inversion is the problem that occurs when a high-priority
830 task is blocked waiting to acquire a lock held by a low-priority task,
831 while tasks at an intermediate priority continuously preempt
832 the low-priority task from the CPU.
833 Consequently, the low-priority task makes no progress toward
834 releasing the lock, and the high-priority task remains blocked.
836 Priority inheritance is a mechanism for dealing with
837 the priority-inversion problem.
838 With this mechanism, when a high-priority task becomes blocked
839 by a lock held by a low-priority task,
840 the priority of the low-priority task is temporarily raised
841 to that of the high-priority task,
842 so that it is not preempted by any intermediate level tasks,
843 and can thus make progress toward releasing the lock.
844 To be effective, priority inheritance must be transitive,
845 meaning that if a high-priority task blocks on a lock
846 held by a lower-priority task that is itself blocked by a lock
847 held by another intermediate-priority task
848 (and so on, for chains of arbitrary length),
849 then both of those tasks
850 (or more generally, all of the tasks in a lock chain)
851 have their priorities raised to be the same as the high-priority task.
853 From a user-space perspective,
854 what makes a futex PI-aware is a policy agreement (described below)
855 between user space and the kernel about the value of the futex word,
856 coupled with the use of the PI-futex operations described below.
857 (Unlike the other futex operations described above,
858 the PI-futex operations are designed
859 for the implementation of very specific IPC mechanisms.)
861 .\" Quoting Darren Hart:
862 .\" These opcodes paired with the PI futex value policy (described below)
863 .\" defines a "futex" as PI aware. These were created very specifically
864 .\" in support of PI pthread_mutexes, so it makes a lot more sense to
865 .\" talk about a PI aware pthread_mutex, than a PI aware futex, since
866 .\" there is a lot of policy and scaffolding that has to be built up
867 .\" around it to use it properly (this is what a PI pthread_mutex is).
869 .\" mtk: The following text is drawn from the Hart/Guniguntala paper
870 .\" (listed in SEE ALSO), but I have reworded some pieces
873 The PI-futex operations described below differ from the other
874 futex operations in that they impose policy on the use of the value of the
877 If the lock is not acquired, the futex word's value shall be 0.
879 If the lock is acquired, the futex word's value shall
880 be the thread ID (TID;
883 of the owning thread.
885 If the lock is owned and there are threads contending for the lock,
888 bit shall be set in the futex word's value; in other words, this value is:
892 (Note that is invalid for a PI futex word to have no owner and
896 With this policy in place,
897 a user-space application can acquire an unacquired
898 lock or release a lock using atomic instructions executed in user mode
899 (e.g., a compare-and-swap operation such as
901 on the x86 architecture).
902 Acquiring a lock simply consists of using compare-and-swap to atomically
903 set the futex word's value to the caller's TID if its previous value was 0.
904 Releasing a lock requires using compare-and-swap to set the futex word's
905 value to 0 if the previous value was the expected TID.
907 If a futex is already acquired (i.e., has a nonzero value),
908 waiters must employ the
912 operations to acquire the lock.
913 If other threads are waiting for the lock, then the
915 bit is set in the futex value;
916 in this case, the lock owner must employ the
918 operation to release the lock.
920 In the cases where callers are forced into the kernel
921 (i.e., required to perform a
924 they then deal directly with a so-called RT-mutex,
925 a kernel locking mechanism which implements the required
926 priority-inheritance semantics.
927 After the RT-mutex is acquired, the futex value is updated accordingly,
928 before the calling thread returns to user space.
930 It is important to note
931 .\" tglx (July 2015):
932 .\" If there are multiple waiters on a pi futex then a wake pi operation
933 .\" will wake the first waiter and hand over the lock to this waiter. This
934 .\" includes handing over the rtmutex which represents the futex in the
935 .\" kernel. The strict requirement is that the futex owner and the rtmutex
936 .\" owner must be the same, except for the update period which is
937 .\" serialized by the futex internal locking. That means the kernel must
938 .\" update the user-space value prior to returning to user space
939 that the kernel will update the futex word's value prior
940 to returning to user space.
941 (This prevents the possibility of the futex word's value ending
942 up in an invalid state, such as having an owner but the value being 0,
943 or having waiters but not having the
947 If a futex has an associated RT-mutex in the kernel
948 (i.e., there are blocked waiters)
949 and the owner of the futex/RT-mutex dies unexpectedly,
950 then the kernel cleans up the RT-mutex and hands it over to the next waiter.
951 This in turn requires that the user-space value is updated accordingly.
952 To indicate that this is required, the kernel sets the
954 bit in the futex word along with the thread ID of the new owner.
955 User space can detect this situation via the presence of the
957 bit and is then responsible for cleaning up the stale state left over by
959 .\" tglx (July 2015):
960 .\" The FUTEX_OWNER_DIED bit can also be set on uncontended futexes, where
961 .\" the kernel has no state associated. This happens via the robust futex
962 .\" mechanism. In that case the futex value will be set to
963 .\" FUTEX_OWNER_DIED. The robust futex mechanism is also available for non
966 PI futexes are operated on by specifying one of the values listed below in
968 Note that the PI futex operations must be used as paired operations
969 and are subject to some additional requirements:
977 .BR FUTEX_UNLOCK_PI .
979 must be called only on a futex owned by the calling thread,
980 as defined by the value policy, otherwise the error
984 .B FUTEX_WAIT_REQUEUE_PI
986 .BR FUTEX_CMP_REQUEUE_PI .
987 This must be performed from a non-PI futex to a distinct PI futex
993 (the number of waiters to be woken) must be 1
998 The PI futex operations are as follows:
1000 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1003 .BR FUTEX_LOCK_PI " (since Linux 2.6.18)"
1004 .\" commit c87e2837be82df479a6bae9f155c43516d2feebc
1005 This operation is used after an attempt to acquire
1006 the lock via an atomic user-mode instruction failed
1007 because the futex word has a nonzero value\(emspecifically,
1008 because it contained the (PID-namespace-specific) TID of the lock owner.
1010 The operation checks the value of the futex word at the address
1012 If the value is 0, then the kernel tries to atomically set
1013 the futex value to the caller's TID.
1014 If the futex word's value is nonzero,
1015 the kernel atomically sets the
1017 bit, which signals the futex owner that it cannot unlock the futex in
1018 user space atomically by setting the futex value to 0.
1019 .\" tglx (July 2015):
1020 .\" The operation here is similar to the FUTEX_WAIT logic. When the user
1021 .\" space atomic acquire does not succeed because the futex value was non
1022 .\" zero, then the waiter goes into the kernel, takes the kernel internal
1023 .\" lock and retries the acquisition under the lock. If the acquisition
1024 .\" does not succeed either, then it sets the FUTEX_WAITERS bit, to signal
1025 .\" the lock owner that it needs to go into the kernel. Here is the pseudo
1028 .\" lock(kernel_lock);
1032 .\" * Owner might have unlocked in user space before we
1033 .\" * were able to set the waiter bit.
1035 .\" if (atomic_acquire(futex) == SUCCESS) {
1036 .\" unlock(kernel_lock());
1041 .\" * Owner might have unlocked after the above atomic_acquire()
1044 .\" if (atomic_set_waiters_bit(futex) != SUCCESS)
1048 .\" unlock(kernel_lock);
1051 After that, the kernel:
1054 Tries to find the thread which is associated with the owner TID.
1056 Creates or reuses kernel state on behalf of the owner.
1057 (If this is the first waiter, there is no kernel state for this
1058 futex, so kernel state is created by locking the RT-mutex
1059 and the futex owner is made the owner of the RT-mutex.
1060 If there are existing waiters, then the existing state is reused.)
1062 Attaches the waiter to the futex
1063 (i.e., the waiter is enqueued on the RT-mutex waiter list).
1066 If more than one waiter exists,
1067 the enqueueing of the waiter is in descending priority order.
1068 (For information on priority ordering, see the discussion of the
1069 .BR SCHED_DEADLINE ,
1073 scheduling policies in
1075 The owner inherits either the waiter's CPU bandwidth
1076 (if the waiter is scheduled under the
1078 policy) or the waiter's priority (if the waiter is scheduled under the
1084 .\" mtk: If the realm is restricted purely to SCHED_OTHER (SCHED_NORMAL)
1085 .\" processes, does the nice value come into play also?
1087 .\" tglx: No. SCHED_OTHER/NORMAL tasks are handled in FIFO order
1088 This inheritance follows the lock chain in the case of nested locking
1089 .\" (i.e., task 1 blocks on lock A, held by task 2,
1090 .\" while task 2 blocks on lock B, held by task 3)
1091 and performs deadlock detection.
1095 argument provides a timeout for the lock attempt.
1098 is not NULL, the structure it points to specifies
1099 an absolute timeout, measured against the
1102 .\" 2016-07-07 response from Thomas Gleixner on LKML:
1103 .\" From: Thomas Gleixner <tglx@linutronix.de>
1104 .\" Date: 6 July 2016 at 20:57
1105 .\" Subject: Re: futex: Allow FUTEX_CLOCK_REALTIME with FUTEX_WAIT op
1107 .\" On Thu, 23 Jun 2016, Michael Kerrisk (man-pages) wrote:
1108 .\" > On 06/23/2016 08:28 PM, Darren Hart wrote:
1109 .\" > > And as a follow-on, what is the reason for FUTEX_LOCK_PI only using
1110 .\" > > CLOCK_REALTIME? It seems reasonable to me that a user may want to wait a
1111 .\" > > specific amount of time, regardless of wall time.
1113 .\" > Yes, that's another weird inconsistency.
1115 .\" The reason is that phtread_mutex_timedlock() uses absolute timeouts based on
1116 .\" CLOCK_REALTIME. glibc folks asked to make that the default behaviour back
1117 .\" then when we added LOCK_PI.
1120 is NULL, the operation will block indefinitely.
1127 arguments are ignored.
1129 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1132 .BR FUTEX_LOCK_PI2 " (since Linux 5.14.0)"
1133 .\" commit bf22a6976897977b0a3f1aeba6823c959fc4fdae
1134 This operation works similar like
1136 The only difference is the
1139 has support for selectable clocks.
1143 is not NULL, the structure it points to specifies
1144 an absolute timeout.
1147 is NULL, the operation can block indefinitely.
1150 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1153 .BR FUTEX_TRYLOCK_PI " (since Linux 2.6.18)"
1154 .\" commit c87e2837be82df479a6bae9f155c43516d2feebc
1155 This operation tries to acquire the lock at
1157 It is invoked when a user-space atomic acquire did not
1158 succeed because the futex word was not 0.
1160 Because the kernel has access to more state information than user space,
1161 acquisition of the lock might succeed if performed by the
1162 kernel in cases where the futex word
1163 (i.e., the state information accessible to use-space) contains stale state
1166 .BR FUTEX_OWNER_DIED ).
1167 This can happen when the owner of the futex died.
1168 User space cannot handle this condition in a race-free manner,
1169 but the kernel can fix this up and acquire the futex.
1170 .\" Paraphrasing a f2f conversation with Thomas Gleixner about the
1171 .\" above point (Aug 2015): ###
1172 .\" There is a rare possibility of a race condition involving an
1173 .\" uncontended futex with no owner, but with waiters. The
1174 .\" kernel-user-space contract is that if a futex is nonzero, you must
1175 .\" go into kernel. The futex was owned by a task, and that task dies
1176 .\" but there are no waiters, so the futex value is non zero.
1177 .\" Therefore, the next locker has to go into the kernel,
1178 .\" so that the kernel has a chance to clean up. (CMXCH on zero
1179 .\" in user space would fail, so kernel has to clean up.)
1180 .\" Darren Hart (Oct 2015):
1181 .\" The trylock in the kernel has more state, so it can independently
1182 .\" verify the flags that user space must trust implicitly.
1190 arguments are ignored.
1192 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1195 .BR FUTEX_UNLOCK_PI " (since Linux 2.6.18)"
1196 .\" commit c87e2837be82df479a6bae9f155c43516d2feebc
1197 This operation wakes the top priority waiter that is waiting in
1201 on the futex address provided by the
1205 This is called when the user-space value at
1207 cannot be changed atomically from a TID (of the owner) to 0.
1215 arguments are ignored.
1217 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1220 .BR FUTEX_CMP_REQUEUE_PI " (since Linux 2.6.31)"
1221 .\" commit 52400ba946759af28442dee6265c5c0180ac7122
1222 This operation is a PI-aware variant of
1223 .BR FUTEX_CMP_REQUEUE .
1224 It requeues waiters that are blocked via
1225 .B FUTEX_WAIT_REQUEUE_PI
1228 from a non-PI source futex
1230 to a PI target futex
1234 .BR FUTEX_CMP_REQUEUE ,
1235 this operation wakes up a maximum of
1237 waiters that are waiting on the futex at
1240 .BR FUTEX_CMP_REQUEUE_PI ,
1243 (since the main point is to avoid a thundering herd).
1244 The remaining waiters are removed from the wait queue of the source futex at
1246 and added to the wait queue of the target futex at
1251 .\" val2 is the cap on the number of requeued waiters.
1252 .\" In the glibc pthread_cond_broadcast() implementation, this argument
1253 .\" is specified as INT_MAX, and for pthread_cond_signal() it is 0.
1256 arguments serve the same purposes as for
1257 .BR FUTEX_CMP_REQUEUE .
1259 .\" The page at http://locklessinc.com/articles/futex_cheat_sheet/
1260 .\" notes that "priority-inheritance Futex to priority-inheritance
1261 .\" Futex requeues are currently unsupported". However, probably
1262 .\" the page does not need to say nothing about this, since
1263 .\" Thomas Gleixner commented (July 2015): "they never will be
1264 .\" supported because they make no sense at all"
1266 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1269 .BR FUTEX_WAIT_REQUEUE_PI " (since Linux 2.6.31)"
1270 .\" commit 52400ba946759af28442dee6265c5c0180ac7122
1272 Wait on a non-PI futex at
1274 and potentially be requeued (via a
1275 .BR FUTEX_CMP_REQUEUE_PI
1276 operation in another task) onto a PI futex at
1278 The wait operation on
1283 The waiter can be removed from the wait on
1285 without requeueing on
1289 operation in another task.
1291 .BR FUTEX_WAIT_REQUEUE_PI
1292 operation fails with the error
1297 is not NULL, the structure it points to specifies
1298 an absolute timeout for the wait operation.
1301 is NULL, the operation can block indefinitely.
1305 argument is ignored.
1308 .BR FUTEX_WAIT_REQUEUE_PI
1310 .BR FUTEX_CMP_REQUEUE_PI
1311 were added to support a fairly specific use case:
1312 support for priority-inheritance-aware POSIX threads condition variables.
1313 The idea is that these operations should always be paired,
1314 in order to ensure that user space and the kernel remain in sync.
1316 .BR FUTEX_WAIT_REQUEUE_PI
1317 operation, the user-space application pre-specifies the target
1318 of the requeue that takes place in the
1319 .BR FUTEX_CMP_REQUEUE_PI
1322 .\" Darren Hart notes that a patch to allow glibc to fully support
1323 .\" PI-aware pthreads condition variables has not yet been accepted into
1324 .\" glibc. The story is complex, and can be found at
1325 .\" https://sourceware.org/bugzilla/show_bug.cgi?id=11588
1326 .\" Darren notes that in the meantime, the patch is shipped with various
1327 .\" PREEMPT_RT-enabled Linux systems.
1329 .\" Related to the preceding, Darren proposed that somewhere, man-pages
1330 .\" should document the following point:
1332 .\" While the Linux kernel, since 2.6.31, supports requeueing of
1333 .\" priority-inheritance (PI) aware mutexes via the
1334 .\" FUTEX_WAIT_REQUEUE_PI and FUTEX_CMP_REQUEUE_PI futex operations,
1335 .\" the glibc implementation does not yet take full advantage of this.
1336 .\" Specifically, the condvar internal data lock remains a non-PI aware
1337 .\" mutex, regardless of the type of the pthread_mutex associated with
1338 .\" the condvar. This can lead to an unbounded priority inversion on
1339 .\" the internal data lock even when associating a PI aware
1340 .\" pthread_mutex with a condvar during a pthread_cond*_wait
1341 .\" operation. For this reason, it is not recommended to rely on
1342 .\" priority inheritance when using pthread condition variables.
1344 .\" The problem is that the obvious location for this text is
1345 .\" the pthread_cond*wait(3) man page. However, such a man page
1346 .\" does not currently exist.
1348 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1351 In the event of an error (and assuming that
1355 all operations return \-1 and set
1357 to indicate the error.
1359 The return value on success depends on the operation,
1360 as described in the following list:
1363 Returns 0 if the caller was woken up.
1364 Note that a wake-up can also be caused by common futex usage patterns
1365 in unrelated code that happened to have previously used the futex word's
1366 memory location (e.g., typical futex-based implementations of
1367 Pthreads mutexes can cause this under some conditions).
1368 Therefore, callers should always conservatively assume that a return
1369 value of 0 can mean a spurious wake-up, and use the futex word's value
1370 (i.e., the user-space synchronization scheme)
1371 to decide whether to continue to block or not.
1374 Returns the number of waiters that were woken up.
1377 Returns the new file descriptor associated with the futex.
1380 Returns the number of waiters that were woken up.
1382 .B FUTEX_CMP_REQUEUE
1383 Returns the total number of waiters that were woken up or
1384 requeued to the futex for the futex word at
1386 If this value is greater than
1388 then the difference is the number of waiters requeued to the futex for the
1393 Returns the total number of waiters that were woken up.
1394 This is the sum of the woken waiters on the two futexes for
1400 .B FUTEX_WAIT_BITSET
1401 Returns 0 if the caller was woken up.
1404 for how to interpret this correctly in practice.
1406 .B FUTEX_WAKE_BITSET
1407 Returns the number of waiters that were woken up.
1410 Returns 0 if the futex was successfully locked.
1413 Returns 0 if the futex was successfully locked.
1416 Returns 0 if the futex was successfully locked.
1419 Returns 0 if the futex was successfully unlocked.
1421 .B FUTEX_CMP_REQUEUE_PI
1422 Returns the total number of waiters that were woken up or
1423 requeued to the futex for the futex word at
1425 If this value is greater than
1427 then difference is the number of waiters requeued to the futex for
1431 .B FUTEX_WAIT_REQUEUE_PI
1432 Returns 0 if the caller was successfully requeued to the futex for
1436 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1441 No read access to the memory of a futex word.
1445 .BR FUTEX_WAIT_BITSET ,
1446 .BR FUTEX_WAIT_REQUEUE_PI )
1447 The value pointed to by
1449 was not equal to the expected value
1451 at the time of the call.
1454 on Linux, the symbolic names
1458 (both of which appear in different parts of the kernel futex code)
1459 have the same value.
1462 .RB ( FUTEX_CMP_REQUEUE ,
1463 .BR FUTEX_CMP_REQUEUE_PI )
1464 The value pointed to by
1466 is not equal to the expected value
1470 .RB ( FUTEX_LOCK_PI ,
1471 .BR FUTEX_LOCK_PI2 ,
1472 .BR FUTEX_TRYLOCK_PI ,
1473 .BR FUTEX_CMP_REQUEUE_PI )
1474 The futex owner thread ID of
1477 .BR FUTEX_CMP_REQUEUE_PI :
1480 but has not yet handled the internal state cleanup.
1484 .RB ( FUTEX_LOCK_PI ,
1485 .BR FUTEX_LOCK_PI2 ,
1486 .BR FUTEX_TRYLOCK_PI ,
1487 .BR FUTEX_CMP_REQUEUE_PI )
1490 is already locked by the caller.
1493 .\" FIXME . I see that kernel/locking/rtmutex.c uses EDEADLK in some
1494 .\" places, and EDEADLOCK in others. On almost all architectures
1495 .\" these constants are synonymous. Is there a reason that both
1498 .\" tglx (July 2015): "No. We should probably fix that."
1500 .RB ( FUTEX_CMP_REQUEUE_PI )
1501 While requeueing a waiter to the PI futex for the futex word at
1503 the kernel detected a deadlock.
1506 A required pointer argument (i.e.,
1511 did not point to a valid user-space address.
1517 .B FUTEX_WAIT_BITSET
1518 operation was interrupted by a signal (see
1520 In kernels before Linux 2.6.22, this error could also be returned for
1521 a spurious wakeup; since Linux 2.6.22, this no longer happens.
1526 is one of those that employs a timeout, but the supplied
1528 argument was invalid
1530 was less than zero, or
1532 was not less than 1,000,000,000).
1535 The operation specified in
1537 employs one or both of the pointers
1541 but one of these does not point to a valid object\(emthat is,
1542 the address is not four-byte-aligned.
1545 .RB ( FUTEX_WAIT_BITSET ,
1546 .BR FUTEX_WAKE_BITSET )
1547 The bit mask supplied in
1552 .RB ( FUTEX_CMP_REQUEUE_PI )
1556 (i.e., an attempt was made to requeue to the same futex).
1560 The signal number supplied in
1567 .BR FUTEX_WAKE_BITSET ,
1569 .BR FUTEX_CMP_REQUEUE )
1570 The kernel detected an inconsistency between the user-space state at
1572 and the kernel state\(emthat is, it detected a waiter which waits in
1580 .RB ( FUTEX_LOCK_PI ,
1581 .BR FUTEX_LOCK_PI2 ,
1582 .BR FUTEX_TRYLOCK_PI ,
1583 .BR FUTEX_UNLOCK_PI )
1584 The kernel detected an inconsistency between the user-space state at
1586 and the kernel state.
1587 This indicates either state corruption
1588 or that the kernel found a waiter on
1590 which is waiting via
1593 .BR FUTEX_WAIT_BITSET .
1596 .RB ( FUTEX_CMP_REQUEUE_PI )
1597 The kernel detected an inconsistency between the user-space state at
1599 and the kernel state;
1600 .\" From a conversation with Thomas Gleixner (Aug 2015): ###
1601 .\" The kernel sees: I have non PI state for a futex you tried to
1603 that is, the kernel detected a waiter which waits via
1606 .BR FUTEX_WAIT_BITSET
1611 .RB ( FUTEX_CMP_REQUEUE_PI )
1612 The kernel detected an inconsistency between the user-space state at
1614 and the kernel state;
1615 that is, the kernel detected a waiter which waits via
1618 .BR FUTEX_WAIT_BITSET
1623 .RB ( FUTEX_CMP_REQUEUE_PI )
1624 The kernel detected an inconsistency between the user-space state at
1626 and the kernel state;
1627 that is, the kernel detected a waiter which waits on
1634 .BR FUTEX_WAIT_REQUEUE_PI ).
1637 .RB ( FUTEX_CMP_REQUEUE_PI )
1638 .\" This deals with the case:
1639 .\" wait_requeue_pi(A, B);
1640 .\" requeue_pi(A, C);
1641 An attempt was made to requeue a waiter to a futex other than that
1642 specified by the matching
1643 .B FUTEX_WAIT_REQUEUE_PI
1644 call for that waiter.
1647 .RB ( FUTEX_CMP_REQUEUE_PI )
1657 The system-wide limit on the total number of open files has been reached.
1660 .RB ( FUTEX_LOCK_PI ,
1661 .BR FUTEX_LOCK_PI2 ,
1662 .BR FUTEX_TRYLOCK_PI ,
1663 .BR FUTEX_CMP_REQUEUE_PI )
1664 The kernel could not allocate memory to hold state information.
1667 Invalid operation specified in
1672 .BR FUTEX_CLOCK_REALTIME
1673 option was specified in
1675 but the accompanying operation was neither
1677 .BR FUTEX_WAIT_BITSET ,
1678 .BR FUTEX_WAIT_REQUEUE_PI ,
1680 .BR FUTEX_LOCK_PI2 .
1683 .RB ( FUTEX_LOCK_PI ,
1684 .BR FUTEX_LOCK_PI2 ,
1685 .BR FUTEX_TRYLOCK_PI ,
1686 .BR FUTEX_UNLOCK_PI ,
1687 .BR FUTEX_CMP_REQUEUE_PI ,
1688 .BR FUTEX_WAIT_REQUEUE_PI )
1689 A run-time check determined that the operation is not available.
1690 The PI-futex operations are not implemented on all architectures and
1691 are not supported on some CPU variants.
1694 .RB ( FUTEX_LOCK_PI ,
1695 .BR FUTEX_LOCK_PI2 ,
1696 .BR FUTEX_TRYLOCK_PI ,
1697 .BR FUTEX_CMP_REQUEUE_PI )
1698 The caller is not allowed to attach itself to the futex at
1701 .BR FUTEX_CMP_REQUEUE_PI :
1704 (This may be caused by a state corruption in user space.)
1707 .RB ( FUTEX_UNLOCK_PI )
1708 The caller does not own the lock represented by the futex word.
1711 .RB ( FUTEX_LOCK_PI ,
1712 .BR FUTEX_LOCK_PI2 ,
1713 .BR FUTEX_TRYLOCK_PI ,
1714 .BR FUTEX_CMP_REQUEUE_PI )
1715 The thread ID in the futex word at
1720 .RB ( FUTEX_CMP_REQUEUE_PI )
1721 The thread ID in the futex word at
1728 employed the timeout specified in
1730 and the timeout expired before the operation completed.
1732 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1735 Futexes were first made available in a stable kernel release
1738 Initial futex support was merged in Linux 2.5.7 but with different
1739 semantics from what was described above.
1740 A four-argument system call with the semantics
1741 described in this page was introduced in Linux 2.5.40.
1742 A fifth argument was added in Linux 2.5.70,
1743 and a sixth argument was added in Linux 2.6.7.
1745 This system call is Linux-specific.
1747 Several higher-level programming abstractions are implemented via futexes,
1748 including POSIX semaphores and
1749 various POSIX threads synchronization mechanisms
1750 (mutexes, condition variables, read-write locks, and barriers).
1751 .\" TODO FIXME(Torvald) Above, we cite this section and claim it contains
1752 .\" details on the synchronization semantics; add the C11 equivalents
1753 .\" here (or whatever we find consensus for).
1755 .\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1758 The program below demonstrates use of futexes in a program where a parent
1759 process and a child process use a pair of futexes located inside a
1760 shared anonymous mapping to synchronize access to a shared resource:
1762 The two processes each write
1764 (a command-line argument that defaults to 5 if omitted)
1765 messages to the terminal and employ a synchronization protocol
1766 that ensures that they alternate in writing messages.
1767 Upon running this program we see output such as the following:
1771 $ \fB./futex_demo\fP
1789 Usage: futex_demo [nloops]
1792 Demonstrate the use of futexes in a program where parent and child
1793 use a pair of futexes located inside a shared anonymous mapping to
1794 synchronize access to a shared resource: the terminal. The two
1795 processes each write \(aqnum\-loops\(aq messages to the terminal and employ
1796 a synchronization protocol that ensures that they alternate in
1802 #include <stdatomic.h>
1806 #include <sys/wait.h>
1807 #include <sys/mman.h>
1808 #include <sys/syscall.h>
1809 #include <linux/futex.h>
1810 #include <sys/time.h>
1812 #define errExit(msg) do { perror(msg); exit(EXIT_FAILURE); \e
1815 static uint32_t *futex1, *futex2, *iaddr;
1818 futex(uint32_t *uaddr, int futex_op, uint32_t val,
1819 const struct timespec *timeout, uint32_t *uaddr2, uint32_t val3)
1821 return syscall(SYS_futex, uaddr, futex_op, val,
1822 timeout, uaddr2, val3);
1825 /* Acquire the futex pointed to by \(aqfutexp\(aq: wait for its value to
1826 become 1, and then set the value to 0. */
1829 fwait(uint32_t *futexp)
1833 /* atomic_compare_exchange_strong(ptr, oldval, newval)
1834 atomically performs the equivalent of:
1836 if (*ptr == *oldval)
1839 It returns true if the test yielded true and *ptr was updated. */
1843 /* Is the futex available? */
1844 const uint32_t one = 1;
1845 if (atomic_compare_exchange_strong(futexp, &one, 0))
1848 /* Futex is not available; wait. */
1850 s = futex(futexp, FUTEX_WAIT, 0, NULL, NULL, 0);
1851 if (s == \-1 && errno != EAGAIN)
1852 errExit("futex\-FUTEX_WAIT");
1856 /* Release the futex pointed to by \(aqfutexp\(aq: if the futex currently
1857 has the value 0, set its value to 1 and the wake any futex waiters,
1858 so that if the peer is blocked in fwait(), it can proceed. */
1861 fpost(uint32_t *futexp)
1865 /* atomic_compare_exchange_strong() was described
1866 in comments above. */
1868 const uint32_t zero = 0;
1869 if (atomic_compare_exchange_strong(futexp, &zero, 1)) {
1870 s = futex(futexp, FUTEX_WAKE, 1, NULL, NULL, 0);
1872 errExit("futex\-FUTEX_WAKE");
1877 main(int argc, char *argv[])
1882 setbuf(stdout, NULL);
1884 nloops = (argc > 1) ? atoi(argv[1]) : 5;
1886 /* Create a shared anonymous mapping that will hold the futexes.
1887 Since the futexes are being shared between processes, we
1888 subsequently use the "shared" futex operations (i.e., not the
1889 ones suffixed "_PRIVATE"). */
1891 iaddr = mmap(NULL, sizeof(*iaddr) * 2, PROT_READ | PROT_WRITE,
1892 MAP_ANONYMOUS | MAP_SHARED, \-1, 0);
1893 if (iaddr == MAP_FAILED)
1899 *futex1 = 0; /* State: unavailable */
1900 *futex2 = 1; /* State: available */
1902 /* Create a child process that inherits the shared anonymous
1906 if (childPid == \-1)
1909 if (childPid == 0) { /* Child */
1910 for (int j = 0; j < nloops; j++) {
1912 printf("Child (%jd) %d\en", (intmax_t) getpid(), j);
1919 /* Parent falls through to here. */
1921 for (int j = 0; j < nloops; j++) {
1923 printf("Parent (%jd) %d\en", (intmax_t) getpid(), j);
1934 .BR get_robust_list (2),
1935 .BR restart_syscall (2),
1936 .BR pthread_mutexattr_getprotocol (3),
1940 The following kernel source files:
1942 .I Documentation/pi\-futex.txt
1944 .I Documentation/futex\-requeue\-pi.txt
1946 .I Documentation/locking/rt\-mutex.txt
1948 .I Documentation/locking/rt\-mutex\-design.txt
1950 .I Documentation/robust\-futex\-ABI.txt
1952 Franke, H., Russell, R., and Kirwood, M., 2002.
1953 \fIFuss, Futexes and Furwocks: Fast Userlevel Locking in Linux\fP
1954 (from proceedings of the Ottawa Linux Symposium 2002),
1956 .UR http://kernel.org\:/doc\:/ols\:/2002\:/ols2002\-pages\-479\-495.pdf
1959 Hart, D., 2009. \fIA futex overview and update\fP,
1960 .UR http://lwn.net/Articles/360699/
1963 Hart, D.\& and Guniguntala, D., 2009.
1964 \fIRequeue-PI: Making Glibc Condvars PI-Aware\fP
1965 (from proceedings of the 2009 Real-Time Linux Workshop),
1966 .UR http://lwn.net/images/conf/rtlws11/papers/proc/p10.pdf
1969 Drepper, U., 2011. \fIFutexes Are Tricky\fP,
1970 .UR http://www.akkadia.org/drepper/futex.pdf
1973 Futex example library, futex-*.tar.bz2 at
1975 .UR ftp://ftp.kernel.org\:/pub\:/linux\:/kernel\:/people\:/rusty/
1978 .\" FIXME(Torvald) We should probably refer to the glibc code here, in
1979 .\" particular the glibc-internal futex wrapper functions that are
1980 .\" WIP, and the generic pthread_mutex_t and perhaps condvar
1981 .\" implementations.