HOME

TheInfoList



OR:

In computing, a futex (short for "fast userspace
mutex In computer science, a lock or mutex (from mutual exclusion) is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concur ...
") is a
kernel Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learni ...
system call In computing, a system call (commonly abbreviated to syscall) is the programmatic way in which a computer program requests a service from the operating system on which it is executed. This may include hardware-related services (for example, ac ...
that
programmer A computer programmer, sometimes referred to as a software developer, a software engineer, a programmer or a coder, is a person who creates computer programs — often for larger computer software. A programmer is someone who writes/creates ...
s can use to implement basic
lock Lock(s) may refer to: Common meanings *Lock and key, a mechanical device used to secure items of importance *Lock (water navigation), a device for boats to transit between different levels of water, as in a canal Arts and entertainment * ''Lock ...
ing, or as a building block for higher-level locking abstractions such as
semaphore Semaphore (; ) is the use of an apparatus to create a visual signal transmitted over distance. A semaphore can be performed with devices including: fire, lights, flags, sunlight, and moving arms. Semaphores can be used for telegraphy when arra ...
s and
POSIX The Portable Operating System Interface (POSIX) is a family of standards specified by the IEEE Computer Society for maintaining compatibility between operating systems. POSIX defines both the system- and user-level application programming interf ...
mutexes or
condition variable In concurrent programming, a monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become false. Monitors also have a mechanism for signaling other th ...
s. A futex consists of a
kernel Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learni ...
space ''wait queue'' that is attached to an atomic
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
in
userspace A modern computer operating system usually segregates virtual memory into user space and kernel space. Primarily, this separation serves to provide memory protection and hardware protection from malicious or errant software behaviour. Kernel ...
. Multiple processes or threads operate on the integer entirely in userspace (using
atomic operation In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events ( event), that may be extended by adding response events such that: # The extended list can be re- ...
s to avoid interfering with one another), and only resort to relatively expensive
system call In computing, a system call (commonly abbreviated to syscall) is the programmatic way in which a computer program requests a service from the operating system on which it is executed. This may include hardware-related services (for example, ac ...
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 is contended; since most operations do not require arbitration between processes, this will not happen in most cases.


History

On
Linux Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, which in ...
, Hubertus Franke ( IBM
Thomas J. Watson Research Center The Thomas J. Watson Research Center is the headquarters for IBM Research. The center comprises three sites, with its main laboratory in Yorktown Heights, New York, U.S., 38 miles (61 km) north of New York City, Albany, New York and with ...
), Matthew Kirkwood,
Ingo Molnár Ingo Molnár, employed by Red Hat as of May 2013, is a Hungarian Linux hacker. He is known for his contributions to the operating system in terms of security and performance. Life and career Molnár studied at Eötvös Loránd University. W ...
(
Red Hat Red Hat, Inc. is an American software company that provides open source software products to enterprises. Founded in 1993, Red Hat has its corporate headquarters in Raleigh, North Carolina, with other offices worldwide. Red Hat has become ass ...
) and
Rusty Russell Rusty Russell is an Australian free software programmer and advocate, known for his work on the Linux kernel's networking subsystem and the Filesystem Hierarchy Standard. Software development Russell wrote the packet filtering systems ipch ...
(
IBM Linux Technology Center The IBM Linux Technology Center (LTC) is an organization focused on development for the Linux kernel and related open-source software projects. In 1999, IBM created the LTC to combine its software developers interested in Linux and other open-sourc ...
) originated the futex mechanism. Futexes 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 The Linux kernel is a free and open-source, monolithic, modular, multitasking, Unix-like operating system kernel. It was originally authored in 1991 by Linus Torvalds for his i386-based PC, and it was soon adopted as the kernel for the GNU ope ...
since the December 2003 release of 2.6.x stable kernel series. In 2002, 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 Linus Benedict Torvalds ( , ; born 28 December 1969) is a Finnish software engineer who is the creator and, historically, the lead developer of the Linux kernel, used by Linux distributions and other operating systems such as Android. He also c ...
strongly opposed this idea and rejected any related patches. Futexes have been implemented in Microsoft Windows since Windows 8 or Windows Server 2012 under the name WaitOnAddress. In 2013, Microsoft patented futexes and the patent was granted in 2014. 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. In May 2015, the
Linux kernel The Linux kernel is a free and open-source, monolithic, modular, multitasking, Unix-like operating system kernel. It was originally authored in 1991 by Linus Torvalds for his i386-based PC, and it was soon adopted as the kernel for the GNU ope ...
introduced a deadlock bug vi
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. Futexes have been implemented in
OpenBSD OpenBSD is a security-focused, free and open-source, Unix-like operating system based on the Berkeley Software Distribution (BSD). Theo de Raadt created OpenBSD in 1995 by forking NetBSD 1.0. According to the website, the OpenBSD project emph ...
since 2016. The futex mechanism is one of the core concepts of the Zircon kernel in
Google Google LLC () is an American multinational technology company focusing on search engine technology, online advertising, cloud computing, computer software, quantum computing, e-commerce, artificial intelligence, and consumer electronics. I ...
's Fuchsia operating system since at least April 2018.


Operations

Futexes have two basic operations, WAIT and WAKE. * WAIT(addr, val) : If the value stored at the address addr is val, puts the current thread to sleep. * WAKE(addr, num) : 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 REQUEUE and WAKE_OP, which both function as more generic WAKE operations.Futexes Are Tricky
Ulrich Drepper (Red Hat, v1.6, 2011)
* CMP_REQUEUE(old_addr, new_addr, num_wake, num_move, val) : 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
thundering herd problem In computer science, the thundering herd problem occurs when a large number of processes or threads waiting for an event are awoken when that event occurs, but only one process is able to handle the event. When the processes wake up, they will each ...
on wake.Zircon zx_futex_requeue documentation
/ref> * WAKE_OP(addr1, addr2, num1, num2, op, op_arg, cmp, cmp_arg) : Will read addr2, perform op with op_arg on it, and storing 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.


See also

*
Synchronization Synchronization is the coordination of events to operate a system in unison. For example, the conductor of an orchestra keeps the orchestra synchronized or ''in time''. Systems that operate with all parts in synchrony are said to be synchronou ...
*
Fetch-and-add In computer science, the fetch-and-add CPU instruction (FAA) atomically increments the contents of a memory location by a specified value. That is, fetch-and-add performs the operation :increment the value at address by , where is a memory loca ...
*
Compare and swap In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of tha ...


References


External links

* - 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 The Linux Symposium was a Linux and Open Source conference held annually in Canada from 1999 to 2014. The conference was initially named Ottawa Linux Symposium and was held only in Ottawa, but was renamed after being held in other cities in Canada. ...
2002. * * Bert Hubert (2004)
Unofficial Futex manpages
* Ingo Molnar.
Robust Futexes
, ''Linux Kernel Documentation'' *
Priority Inheritance Futexes
, ''Linux Kernel Documentation'' {{Linux kernel Concurrency control Linux kernel features