Incomputing, afutex (short for "fast userspacemutex") is akernelsystem call thatprogrammers can use to implement basiclocking, or as a building block for higher-level locking abstractions such assemaphores andPOSIX mutexes orcondition variables.
A futex consists of akernel-spacewait queue that is attached to anatomicinteger inuserspace. Multipleprocesses orthreads operate on the integer entirely in userspace (usingatomic operations to avoid interfering with one another), and only resort to the fast but still more expensivesystem 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.
Hubertus Franke (IBMThomas J. Watson Research Center), Matthew Kirkwood,Ingo Molnár (Red Hat), andRusty Russell (IBM Linux Technology Center) originated the futex mechanism onLinux 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 theLinux 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 nameWaitOnAddress.[3]
In 2013, Microsoft patented futex-related[4]WaitOnAddress and the patent was granted in 2014.[5]
In May 2014, theCVE 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, theLinux kernel introduced a deadlock bug viaCommit 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 inOpenBSD since 2016.[9]
The futex mechanism is one of the core concepts of the Zircon kernel[10] inGoogle'sFuchsia 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 toC++ with theatomic::wait,atomic::notify_one, andatomic::notify_all operations inC++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 APIWaitForMultipleObjects, 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.
Futexes have two basic operations,WAIT andWAKE.
WAIT(addr, val)addr isval, puts the current thread to sleep.WAKE(addr, num)num number of threads waiting on the addressaddr.For more advanced uses, there are a number of other operations, the most used beingCMP_REQUEUE andWAKE_OP, which both function as more genericWAKE operations.[14]
CMP_REQUEUE(old_addr, new_addr, num_wake, num_move, val)old_addr isval, wakesnum_wake threads waiting on the addressold_addr, and enqueuesnum_move threads waiting on the addressold_addr to now wait on the addressnew_addr. This can be used to avoid thethundering herd problem on wake.[15][16]WAKE_OP(addr1, addr2, num1, num2, op, op_arg, cmp, cmp_arg)addr2, performop withop_arg on it, and store the result back toaddr2. Then it will wakenum1 threads waiting onaddr1, and, if the previously read value fromaddr2 matchescmp_arg using comparisoncmp, will wakenum2 threads waiting onaddr2. This very flexible and generic wake mechanism is useful for implementing many synchronization primitives.FUTEX2 API:
WAITV(waiters: {addr, val, flags}*, num)num entries in thewaiters vector do a parallelWAIT operation on the address and value. Return the index of the first address being awoken. Theflags can be used to indicate different bit widths.futex(2) - futex() system callfutex(7) - futex semantics and usage
