Futex

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computing, a futex (short for "fast userspace mutex") is a Linux 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 kernelspace wait queue that is attached to an aligned 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 relatively 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 is contended; since most operations do not require arbitration between processes, this will not happen in most cases.

History[edit]

Hubertus Franke (IBM Thomas J. Watson Research Center), Matthew Kirkwood, Ingo Molnár (Red Hat) and Rusty Russell (IBM Linux Technology Center) originated futexes. They first appeared in the Linux development kernel version 2.5.7; the semantics stabilized as of version 2.5.40, and they have featured since the 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 strongly opposed this idea and rejected any related patches.[1]

In May 2014 the CVE system announced a vulnerability discovered in the Linux kernel's futex subsystem that allowed denial-of-service or local privilege escalation.[2][3]

Operations[edit]

The basic operations of futexes are based on only two central operations—​WAIT and WAKE—​though some futex implementations (depending on the exact version of the Linux kernel) have a few more operations for more specialized cases.[4]

  • WAIT (addr, val)
Checks if the value stored at the address addr is val, and if it is puts the current thread to sleep.
  • WAKE (addr, val)
Wakes up val number of threads waiting on the address addr.

See also[edit]

Further reading[edit]

References[edit]

  1. ^ Torvalds, Linus. "Futex Asynchronous Interface". 
  2. ^ CVE-2014-3153
  3. ^ "[SECURITY] [DSA 2949-1] linux security update". Lists.debian.org. 2014-06-05. Retrieved 2014-06-08. 
  4. ^ Futexes Are Tricky, Red Hat (v 1.6, 2011).

External links[edit]

  • Benaphores: a similar idea used on BeOS, within a single process only, as early as 1996.