Editing Futex

{{Short description|Kernel system call}}
In [[computing]], a '''futex''' (short for "fast userspace [[mutual exclusion|mutex]]") is a [[Kernel (operating system)|kernel]] [[system call]] that [[programmer]]s can use to implement basic [[lock (computer science)|locking]], or as a building block for higher-level locking abstractions such as [[semaphore (programming)|semaphore]]s and [[POSIX]] mutexes or [[condition variable]]s.

A futex consists of a [[kernel (operating system)|kernel-]]space ''wait queue'' that is attached to an [[Atomic operations|atomic]] [[integer]] in [[userspace]]. Multiple [[Process (computing)|processes]] or [[Thread (computer science)|threads]] operate on the integer entirely in userspace (using [[atomic operation]]s to avoid interfering with one another), and only resort to the fast but still more expensive [[system call]]s to request operations on the wait queue (for example to wake up waiting processes, or to put the current process on the wait queue). A properly programmed futex-based lock will not use system calls except when the lock has contention; since most operations do not require arbitration between processes, this will not happen in most cases.

== {{Anchor|BENAPHORE}}History ==
Hubertus Franke ([[IBM]] [[Thomas J. Watson Research Center]]), Matthew Kirkwood, [[Ingo Molnár]] ([[Red Hat]]), and [[Rusty Russell]] ([[IBM Linux Technology Center]]) originated the futex mechanism on [[Linux]] in 2002.
<ref>
"Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux" by Franke, Russell, Kirkwood. Published in 2002 for the Ottawa Linux Symposium.
</ref> In the same year, discussions took place on a proposal to make futexes accessible via the file system by creating a special node in <code>/dev</code> or <code>/proc</code>. However, [[Linus Torvalds]] strongly opposed this idea and rejected any related patches.<ref>
{{cite web|last=Torvalds|first=Linus|title=Futex Asynchronous Interface
|url=http://yarchive.net/comp/linux/everything_is_file.html}}
</ref>

Futexes then appeared for the first time in version 2.5.7 of the Linux kernel development series; the semantics stabilized as of version 2.5.40, and futexes have been part of the [[Linux kernel mainline]] since the December 2003 release of 2.6.x stable kernel series.

Futex functionality has been implemented in Microsoft Windows since Windows 8 or Windows Server 2012 under the name '''WaitOnAddress'''.<ref>
{{cite web| url= https://docs.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-waitonaddress 
| title=WaitOnAddress function | access-date=2019-11-01}}
</ref>

In 2013, Microsoft patented futex-related<ref>
{{cite web
| url= https://devblogs.microsoft.com/oldnewthing/20170601-00/?p=96265
| title= Comparing WaitOnAddress with futexes
| access-date=2024-05-09}}
</ref> '''WaitOnAddress''' and the patent was granted in 2014.<ref>
{{cite web| url= https://patents.google.com/patent/US8782674B2/en 
| title=US8782674B2 Wait on address synchronization interface | access-date=2019-11-01}}
</ref>
  
In May 2014, the [[Common Vulnerabilities and Exposures|CVE]] system announced a vulnerability discovered in the Linux kernel's futex subsystem that allowed denial-of-service attacks or local privilege escalation.<ref>
[http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-3153 CVE-2014-3153]
</ref><ref>
{{cite web| url= https://lists.debian.org/debian-security-announce/2014/msg00130.html 
| title=[SECURITY&#93; [DSA 2949-1&#93; linux security update |publisher=Lists.debian.org 
| date=2014-06-05 |access-date=2014-06-08}}
</ref>

In May 2015, the [[Kernel (operating system)|Linux kernel]] introduced a deadlock bug via [https://github.com/torvalds/linux/commit/b0c29f79ecea Commit b0c29f79ecea] that caused a hang in user applications. The bug affected many enterprise Linux distributions, including 3.x and 4.x kernels, and Red Hat Enterprise Linux version 5, 6 and 7, SUSE Linux 12 and Amazon Linux.<ref>
{{cite web| url= https://groups.google.com/forum/#!topic/mechanical-sympathy/QbmpZxp6C64
| title=Linux futex_wait() bug...
| date=2015-05-13 |access-date=2018-03-24}}
</ref>

Futexes have been implemented in [[OpenBSD]] since 2016.<ref>{{cite web|last1=Mazurek|first1=Michal|title='Futexes for OpenBSD' - MARC|url=https://marc.info/?l=openbsd-tech&m=147282346309815&w=2|website=marc.info|access-date=30 April 2017}}</ref>

The futex mechanism is one of the core concepts of the Zircon kernel<ref>{{cite web|title=Zircon Kernel Concepts|url=https://fuchsia.dev/fuchsia-src/zircon/concepts#futexes|website=fuchsia.dev|access-date=20 October 2019}}</ref> in [[Google]]'s [[Fuchsia (operating system)|Fuchsia operating system]] since at least April 2018.<ref>{{cite web|title=zx_futex_wait|url=https://fuchsia.dev/fuchsia-src/reference/syscalls/futex_wait|website=fuchsia.dev|access-date=20 October 2019}}</ref>

Apple implemented futex in iOS/iPadOS/tvOS 17.4, macOS 14.4, watchOS 10.4 and visionOS 1.1.<ref>{{Cite web |title=os_sync_wait_on_address |url=https://developer.apple.com/documentation/os/os_sync_wait_on_address |access-date=2025-04-14 |website=Apple Developer Documentation |language=en-US}}</ref>

Futex like functionality was added to [[C++]] with the <code>atomic::wait</code>, <code>atomic::notify_one</code>, and <code>atomic::notify_all</code> operations in [[C++20]].

Support for FUTEX2 in the Linux kernel was designed to support two new main features, first something that can be used to implement the Win32 API '''WaitForMultipleObjects''', and second to be able to wait on addresses other  than 32bit ones. The first step was integrated in 5.16 in November 2021.<ref>{{cite web|title=FUTEX2's sys_futex_waitv() Sent In For Linux 5.16 To Help Linux Gaming|url=https://www.phoronix.com/news/Linux-5.16-sys_futex_waitv|access-date=23 May 2025}}</ref> with the waitv syscall.

== Operations ==
Futexes have two basic operations, <code>WAIT</code> and <code>WAKE</code>.

* <code>WAIT(addr, val)</code>
: If the value stored at the address <code>addr</code> is <code>val</code>, puts the current thread to sleep.
* <code>WAKE(addr, num)</code>
: Wakes up <code>num</code> number of threads waiting on the address <code>addr</code>.

For more advanced uses, there are a number of other operations, the most used being <code>CMP_REQUEUE</code> and <code>WAKE_OP</code>, which both function as more generic <code>WAKE</code> operations.<ref name="Ulrich Drepper">[https://www.akkadia.org/drepper/futex.pdf Futexes Are Tricky] Ulrich Drepper (Red Hat, v1.6, 2011)</ref>

* <code>CMP_REQUEUE(old_addr, new_addr, num_wake, num_move, val)</code>
: If the value stored at the address <code>old_addr</code> is <code>val</code>, wakes <code>num_wake</code> threads waiting on the address <code>old_addr</code>, and enqueues <code>num_move</code> threads waiting on the address <code>old_addr</code> to now wait on the address <code>new_addr</code>. This can be used to avoid the [[thundering herd problem]] on wake.<ref>[http://man7.org/linux/man-pages/man2/futex.2.html Linux futex(2) man page, FUTEX_CMP_REQUEUE section]</ref><ref>[https://fuchsia.dev/fuchsia-src/reference/syscalls/futex_requeue.md Zircon zx_futex_requeue documentation]</ref>
* <code>WAKE_OP(addr1, addr2, num1, num2, op, op_arg, cmp, cmp_arg)</code>
: Will read <code>addr2</code>, perform <code>op</code> with <code>op_arg</code> on it, and store the result back to <code>addr2</code>. Then it will wake <code>num1</code> threads waiting on <code>addr1</code>, and, if the previously read value from <code>addr2</code> matches <code>cmp_arg</code> using comparison <code>cmp</code>, will wake <code>num2</code> threads waiting on <code>addr2</code>. This very flexible and generic wake mechanism is useful for implementing many synchronization primitives.

FUTEX2 API:
* <code>WAITV(waiters: {addr, val, flags}*, num)</code>
: Wait on many, wake on any. For each of the <code>num</code> entries in the <code>waiters</code> vector do a parallel <code>WAIT</code> operation on the address and value. Return the index of the first address being awoken. The <code>flags</code> can be used to indicate different bit widths.

== See also ==
* [[Synchronization (computer science)|Synchronization]]
* [[Fetch-and-add]]
* [[Compare-and-swap]]

== References ==
{{Reflist}}

== External links ==
* {{man|2|futex|Linux||inline}} - futex() system call
* {{man|7|futex|Linux||inline}} - futex semantics and usage
* Hubertus Franke, Rusty Russell, Matthew Kirkwood. ''[https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf Fuss, futexes and furwocks: Fast Userlevel Locking in Linux]'', [[Ottawa Linux Symposium]] 2002.
* {{cite web
 | url = https://www.akkadia.org/drepper/futex.pdf
 | title = Futexes are Tricky
 | last = Drepper
 | first = Ulrich
 | date = 2011
 | version = 1.6
 | publisher = Red Hat }}
* Bert Hubert (2004). [http://ds9a.nl/futex-manpages/ Unofficial Futex manpages]
* Ingo Molnar. "[https://www.kernel.org/doc/Documentation/robust-futexes.txt Robust Futexes]", ''Linux Kernel Documentation''
* "[https://www.kernel.org/doc/Documentation/pi-futex.txt Priority Inheritance Futexes]", ''Linux Kernel Documentation''

{{Linux kernel}}

[[Category:Concurrency control]]
[[Category:Linux kernel features]]