Futex

• Basic Concepts
• Working Principles

Basic Concepts

Fast userspace mutex (futex) is a system call capability provided by the kernel. It is a user-space lock that combines basic components and user-space lock logic. It is a lock used by both user space and kernel space, for example, userspace mutex, barrier and cond synchronization lock, and RW lock. The user-space part implements lock logic, and the kernel-space part implements lock scheduling.

When a user-space thread requests a lock, the lock status is first checked in user space. If no lock contention occurs, the user-space thread acquires the lock directly. If lock contention occurs, the futex system call is invoked to request the kernel to suspend the thread and maintain the blocking queue.

When a user-space thread releases a lock, the lock status is first checked in user space. If no other thread is blocked by the lock, the lock is directly released in user space. If there are threads blocked by the lock, the futex system call is invoked to request the kernel to wake up the threads in the blocking queue.

Working Principles

When thread scheduling is required to resolve lock contention or lock release in user space, the futex system call is triggered to pass the user-space lock address to the kernel. The user-space locks are distinguished by lock address in the futex of the kernel. The available virtual address space in user space is 1 GiB. To facilitate search and management of lock addresses, the kernel futex uses hash buckets to store the user-space locks.

There are 80 hash buckets. Buckets 0 to 63 are used to store private locks (hashed based on virtual addresses), and buckets 64 to 79 are used to store shared locks (hashed based on physical addresses). The private/shared attributes are determined by initialization of user-space locks and the input parameters in the futex system call.

Figure 1 Futex design

As shown in above figure, each futex hash bucket stores the futex nodes with the same hash value linked in a futex_list. Each futex node corresponds to a suspended task. The key value of a node uniquely identifies a user-space lock. The nodes with the same key value added to a queue_list indicate a queue of tasks blocked by the same lock.

The following table describes the APIs available for the futex module.

Table 1 Futex module APIs

NOTE: The futex system call and user-space logic form a user-space lock. Therefore, you are advised to use the locks via the user-space POSIX APIs.