Futex

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 kernelspace 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 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

On Linux, Hubertus 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. 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 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 strongly opposed this idea and rejected any related patches.[1]

Futexes have been implemented in Microsoft Windows since Windows 8 or Windows Server 2012 under the name WaitOnAddress.[2]

In 2013 Microsoft patented futexes and the patent was granted in 2014.[3]

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.[4][5]

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.[6]

Futexes have been implemented in OpenBSD since 2016.[7]

The futex mechanism is one of the core concepts of the Zircon kernel[8] in Google's Fuchsia operating system since at least April 2018.[9]

Operations

Futexes have two basic operations, WAIT and WAKE. A third operation called REQUEUE is available and functions as a more generic WAKE operation that can move threads between waiting queues. [10]

  • 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.
  • 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 on wake.[11][12]

See also

References
  1. Torvalds, Linus. "Futex Asynchronous Interface".
  2. "WaitOnAddress function". Retrieved 2019-11-01.
  3. "US8782674B2 Wait on address synchronization interface". Retrieved 2019-11-01.
  4. CVE-2014-3153
  5. "[SECURITY] [DSA 2949-1] linux security update". Lists.debian.org. 2014-06-05. Retrieved 2014-06-08.
  6. "Linux futex_wait() bug..." 2015-05-13. Retrieved 2018-03-24.
  7. Mazurek, Michal. "'Futexes for OpenBSD' - MARC". marc.info. Retrieved 30 April 2017.
  8. "Zircon Kernel Concepts". fuchsia.dev. Retrieved 20 October 2019.
  9. "zx_futex_wait". fuchsia.dev. Retrieved 20 October 2019.
  10. Futexes Are Tricky Ulrich Drepper (Red Hat, v1.6, 2011)
  11. Linux futex(2) man page, FUTEX_CMP_REQUEUE section
  12. Zircon zx_futex_requeue documentation
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.