Futex

<h2 id="history">History</h2>

Hubertus Franke (<a href="/facts/IBM/QszA7nwd">IBM</a> <a href="/facts/Thomas_J._Watson_Research_Center/XfGnAzRW">Thomas J. Watson Research Center</a>), Matthew Kirkwood, <a href="/facts/Ingo_Moln%C3%A1r/AXNHauYW">Ingo Molnár</a> (<a href="/facts/Red_Hat/5rhmBLBa">Red Hat</a>), and <a href="/facts/Rusty_Russell/xNEL8RgP">Rusty Russell</a> (<a href="/facts/IBM_Linux_Technology_Center/RCaroV97">IBM Linux Technology Center</a>) originated the futex mechanism on <a href="/facts/Linux/9FvCKSTq">Linux</a> in 2002.
<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> In the same year, discussions took place on a proposal to make futexes accessible via the file system by creating a special node in /dev or /proc. However, <a href="/facts/Linus_Torvalds/EdDKP534">Linus Torvalds</a> strongly opposed this idea and rejected any related patches.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
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 <a href="/facts/Linux_kernel_mainline/dlkduHuA">Linux kernel mainline</a> 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.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
In 2013, Microsoft patented futex-related<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> WaitOnAddress and the patent was granted in 2014.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
In May 2014, the <a href="/facts/Common_Vulnerabilities_and_Exposures/r6uEABNB">CVE</a> system announced a vulnerability discovered in the Linux kernel's futex subsystem that allowed denial-of-service attacks or local privilege escalation.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
In May 2015, the <a href="/facts/Kernel_(operating_system)/uEj4U3Rz">Linux kernel</a> introduced a deadlock bug via <a href="https://github.com/torvalds/linux/commit/b0c29f79ecea">Commit b0c29f79ecea</a> 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.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
Futexes have been implemented in <a href="/facts/OpenBSD/xmPS9tek">OpenBSD</a> since 2016.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
The futex mechanism is one of the core concepts of the Zircon kernel<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> in <a href="/facts/Google/GT9Sugza">Google</a>'s <a href="/facts/Fuchsia_(operating_system)/R6rWLC2q">Fuchsia operating system</a> since at least April 2018.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
Apple implemented futex in iOS/iPadOS/tvOS 17.4, macOS 14.4, watchOS 10.4 and visionOS 1.1.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="operations">Operations</h2>
Futexes have two basic operations, WAIT and WAKE.

<ul><li>WAIT(addr, val)</li></ul>
If the value stored at the address addr is val, puts the current thread to sleep.
<ul><li>WAKE(addr, num)</li></ul>
Wakes up num number of threads waiting on the address addr.
For more advanced uses, there are a number of other operations, the most used being CMP_REQUEUE and WAKE_OP, which both function as more generic WAKE operations.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

<ul><li>CMP_REQUEUE(old_addr, new_addr, num_wake, num_move, val)</li></ul>
If the value stored at the address old_addr is val, wakes num_wake threads waiting on the address old_addr, and enqueues num_move threads waiting on the address old_addr to now wait on the address new_addr. This can be used to avoid the <a href="/facts/Thundering_herd_problem/7oAguH0U">thundering herd problem</a> on wake.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a><a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>
<ul><li>WAKE_OP(addr1, addr2, num1, num2, op, op_arg, cmp, cmp_arg)</li></ul>
Will read addr2, perform op with op_arg on it, and store the result back to addr2. Then it will wake num1 threads waiting on addr1, and, if the previously read value from addr2 matches cmp_arg using comparison cmp, will wake num2 threads waiting on addr2. This very flexible and generic wake mechanism is useful for implementing many synchronization primitives.
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Synchronization_(computer_science)/n7ID76uM">Synchronization</a></li>
<li><a href="/facts/Fetch-and-add/7GCQDxB2">Fetch-and-add</a></li>
<li><a href="/facts/Compare-and-swap/7mJkkycd">Compare-and-swap</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://manned.org/futex.2">futex(2)</a> - futex() system call</li>
<li><a href="https://manned.org/futex.7">futex(7)</a> - futex semantics and usage</li>
<li>Hubertus Franke, Rusty Russell, Matthew Kirkwood. <a href="https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf">Fuss, futexes and furwocks: Fast Userlevel Locking in Linux</a>, <a href="/facts/Ottawa_Linux_Symposium/NmtVfDd2">Ottawa Linux Symposium</a> 2002.</li>
<li>Drepper, Ulrich (2011). <a href="https://www.akkadia.org/drepper/futex.pdf">"Futexes are Tricky"</a> (PDF). 1.6. Red Hat.</li>
<li>Bert Hubert (2004). <a href="http://ds9a.nl/futex-manpages/">Unofficial Futex manpages</a></li>
<li>Ingo Molnar. "<a href="https://www.kernel.org/doc/Documentation/robust-futexes.txt">Robust Futexes</a>", Linux Kernel Documentation</li>
<li>"<a href="https://www.kernel.org/doc/Documentation/pi-futex.txt">Priority Inheritance Futexes</a>", Linux Kernel Documentation</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">"Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux" by Franke, Russell, Kirkwood. Published in 2002 for the Ottawa Linux Symposium. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Torvalds, Linus. "Futex Asynchronous Interface". <a href="http://yarchive.net/comp/linux/everything_is_file.html" target="_blank">http://yarchive.net/comp/linux/everything_is_file.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">"WaitOnAddress function". Retrieved 2019-11-01. <a href="https://docs.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-waitonaddress" target="_blank">https://docs.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-waitonaddress</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"Comparing WaitOnAddress with futexes". Retrieved 2024-05-09. <a href="https://devblogs.microsoft.com/oldnewthing/20170601-00/?p=96265" target="_blank">https://devblogs.microsoft.com/oldnewthing/20170601-00/?p=96265</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">"US8782674B2 Wait on address synchronization interface". Retrieved 2019-11-01. <a href="https://patents.google.com/patent/US8782674B2/en" target="_blank">https://patents.google.com/patent/US8782674B2/en</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">CVE-2014-3153 <a href="http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-3153" target="_blank">http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-3153</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">"[SECURITY] [DSA 2949-1] linux security update". Lists.debian.org. 2014-06-05. Retrieved 2014-06-08. <a href="https://lists.debian.org/debian-security-announce/2014/msg00130.html" target="_blank">https://lists.debian.org/debian-security-announce/2014/msg00130.html</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">"Linux futex_wait() bug..." 2015-05-13. Retrieved 2018-03-24. <a href="https://groups.google.com/forum/#!topic/mechanical-sympathy/QbmpZxp6C64" target="_blank">https://groups.google.com/forum/#!topic/mechanical-sympathy/QbmpZxp6C64</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Mazurek, Michal. "'Futexes for OpenBSD' - MARC". marc.info. Retrieved 30 April 2017. <a href="https://marc.info/?l=openbsd-tech&m=147282346309815&w=2" target="_blank">https://marc.info/?l=openbsd-tech&m=147282346309815&w=2</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">"Zircon Kernel Concepts". fuchsia.dev. Retrieved 20 October 2019. <a href="https://fuchsia.dev/fuchsia-src/zircon/concepts#futexes" target="_blank">https://fuchsia.dev/fuchsia-src/zircon/concepts#futexes</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">"zx_futex_wait". fuchsia.dev. Retrieved 20 October 2019. <a href="https://fuchsia.dev/fuchsia-src/reference/syscalls/futex_wait" target="_blank">https://fuchsia.dev/fuchsia-src/reference/syscalls/futex_wait</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">"os_sync_wait_on_address". Apple Developer Documentation. Retrieved 2024-03-14. <a href="https://docs.developer.apple.com/documentation/os/4316531-os_sync_wait_on_address" target="_blank">https://docs.developer.apple.com/documentation/os/4316531-os_sync_wait_on_address</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Futexes Are Tricky Ulrich Drepper (Red Hat, v1.6, 2011) <a href="https://www.akkadia.org/drepper/futex.pdf" target="_blank">https://www.akkadia.org/drepper/futex.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Linux futex(2) man page, FUTEX_CMP_REQUEUE section <a href="http://man7.org/linux/man-pages/man2/futex.2.html" target="_blank">http://man7.org/linux/man-pages/man2/futex.2.html</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Zircon zx_futex_requeue documentation <a href="https://fuchsia.dev/fuchsia-src/reference/syscalls/futex_requeue.md" target="_blank">https://fuchsia.dev/fuchsia-src/reference/syscalls/futex_requeue.md</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
</ol>

Futex open-in-new

Futex