In computing, a futex (short for "fast userspace mutex") is a kernel system call that programmers can use to implement basic locking, or as a building block for higher-level locking abstractions such as semaphores and POSIX mutexes or condition variables.
A futex consists of a kernel-space wait queue that is attached to an atomic integer in userspace. Multiple processes or threads operate on the integer entirely in userspace (using atomic operations to avoid interfering with one another), and only resort to the fast but still more expensive system calls 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.
History
editHubertus 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.
[1] 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, Linus Torvalds strongly opposed this idea and rejected any related patches.[2]
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.[3]
In 2013, Microsoft patented futex-related[4] WaitOnAddress and the patent was granted in 2014.[5]
In May 2014, the CVE system announced a vulnerability discovered in the Linux kernel's futex subsystem that allowed denial-of-service attacks or local privilege escalation.[6][7]
In May 2015, the Linux kernel introduced a deadlock bug via 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.[8]
Futexes have been implemented in OpenBSD since 2016.[9]
The futex mechanism is one of the core concepts of the Zircon kernel[10] in Google's Fuchsia operating system since at least April 2018.[11]
Apple implemented futex in iOS/iPadOS/tvOS 17.4, macOS 14.4, watchOS 10.4 and visionOS 1.1.[12]
Futex like functionality was added to C++ with the atomic::wait, atomic::notify_one, and atomic::notify_all 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.[13] with the waitv syscall.
Operations
editFutexes have two basic operations, WAIT and WAKE.
WAIT(addr, val)
- If the value stored at the address
addrisval, puts the current thread to sleep.
WAKE(addr, num)
- Wakes up
numnumber of threads waiting on the addressaddr.
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.[14]
CMP_REQUEUE(old_addr, new_addr, num_wake, num_move, val)
- If the value stored at the address
old_addrisval, wakesnum_wakethreads waiting on the addressold_addr, and enqueuesnum_movethreads waiting on the addressold_addrto now wait on the addressnew_addr. This can be used to avoid the thundering herd problem on wake.[15][16]
WAKE_OP(addr1, addr2, num1, num2, op, op_arg, cmp, cmp_arg)
- Will read
addr2, performopwithop_argon it, and store the result back toaddr2. Then it will wakenum1threads waiting onaddr1, and, if the previously read value fromaddr2matchescmp_argusing comparisoncmp, will wakenum2threads waiting onaddr2. This very flexible and generic wake mechanism is useful for implementing many synchronization primitives.
FUTEX2 API:
WAITV(waiters: {addr, val, flags}*, num)
- Wait on many, wake on any. For each of the
numentries in thewaitersvector do a parallelWAIToperation on the address and value. Return the index of the first address being awoken. Theflagscan be used to indicate different bit widths.
See also
editReferences
edit- ^ "Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux" by Franke, Russell, Kirkwood. Published in 2002 for the Ottawa Linux Symposium.
- ^ Torvalds, Linus. "Futex Asynchronous Interface".
- ^ "WaitOnAddress function". Retrieved 2019-11-01.
- ^ "Comparing WaitOnAddress with futexes". Retrieved 2024-05-09.
- ^ "US8782674B2 Wait on address synchronization interface". Retrieved 2019-11-01.
- ^ CVE-2014-3153
- ^ "[SECURITY] [DSA 2949-1] linux security update". Lists.debian.org. 2014-06-05. Retrieved 2014-06-08.
- ^ "Linux futex_wait() bug..." 2015-05-13. Retrieved 2018-03-24.
- ^ Mazurek, Michal. "'Futexes for OpenBSD' - MARC". marc.info. Retrieved 30 April 2017.
- ^ "Zircon Kernel Concepts". fuchsia.dev. Retrieved 20 October 2019.
- ^ "zx_futex_wait". fuchsia.dev. Retrieved 20 October 2019.
- ^ "os_sync_wait_on_address". Apple Developer Documentation. Retrieved 2025-04-14.
- ^ "FUTEX2's sys_futex_waitv() Sent In For Linux 5.16 To Help Linux Gaming". Retrieved 23 May 2025.
- ^ Futexes Are Tricky Ulrich Drepper (Red Hat, v1.6, 2011)
- ^ Linux futex(2) man page, FUTEX_CMP_REQUEUE section
- ^ Zircon zx_futex_requeue documentation
External links
edit- - futex() system call
- - futex semantics and usage
- Hubertus Franke, Rusty Russell, Matthew Kirkwood. Fuss, futexes and furwocks: Fast Userlevel Locking in Linux, Ottawa Linux Symposium 2002.
- Drepper, Ulrich (2011). "Futexes are Tricky" (PDF). 1.6. Red Hat.
- Bert Hubert (2004). Unofficial Futex manpages
- Ingo Molnar. "Robust Futexes", Linux Kernel Documentation
- "Priority Inheritance Futexes", Linux Kernel Documentation
