一、什么是futex？

futex是Fast Userspace muTEX的缩写，该机制是由Rusty Russell、Hubertus Franke和Mathew Kirkwood在2.5.7版本的内核中引入，虽然名字中有互斥锁（mutex）的含义，但实际它是一种用于用户空间应用程序的通用同步工具（基于futex可以在userspace实现互斥锁、读写锁、condition variable等同步机制）。Futex组成包括：

内核空间的等待队列
用户空间层的32-bit futex word（所有平台都是32bit，包括64位平台）

在没有竞争的场景下，锁的获取和释放性能都非常高，不需要内核的参与，仅仅是通过用户空间的原子操作来修改futex word的状态即可。在有竞争的场景下，如果线程无法获取futex锁，那么把自己放入到 wait queue中（陷入内核，有系统调用的开销），而在owner task释放锁的时候，如果检测到有竞争（等待队列中有阻塞任务），就会通过系统调用来唤醒等待队列中的任务，使其恢复执行，继续去持锁。如果没有竞争，那么也无需陷入内核。

二、Futex用户和内核空间接口API是什么？

Futex接口函数的原型如下：

Futex系统调用的复杂性体现在其参数上，要理解futex需要充分理解其参数：

futex系统调用支持各种各样的操作码，如下：

1、FUTEX_WAIT：如果futex word中仍然保存着参数val给定的值，那么当前线程则进入睡眠，等待FUTEX_WAKE的操作唤醒它。

2、FUTEX_WAKE：最多唤醒val个等待在futex word上的线程。Val或者等于1（唤醒1个等待线程）或者等于INT_MAX（唤醒全部等待线程）

3、FUTEX_WAIT_BITSET：同FUTEX_WAIT，只不过多提供一个mask的参数

4、FUTEX_WAKE_BITSET：同FUTEX_WAKE，只不过多提供一个mask参数用来选择唤醒哪一个waiter。

5、FUTEX_LOCK_PI：PI版本的FUTEX_WAIT

6、FUTEX_UNLOCK_PI：PI版本的FUTEX_WAKE

7、FUTEX_REQUEUE：这个操作包括唤醒和移动队列两个动作。唤醒val个等待在uaddr上的waiter，如果还有其他的waiter，那么将这些等待在uaddr的waiter转移到uaddr2的等待队列上去（最多转移val2个waiter）

8、FUTEX_CMP_REQUEUE：同上，不过需要对比val3这个uaddr的期望值。

除了futex wait和wake这样的基本操作，futex还有其他应用在复杂场景的操作码，由于在手机场景没有使用，本文不再介绍。

我们整理各个操作码的参数如下：

资料直通车：Linux内核源码技术学习路线+视频教程内核源码

学习直通车：Linux内核源码内存调优文件系统进程管理设备驱动/网络协议栈

三、对于normal futex，内核中如何组织等待队列？

Futex相关的数据结构组织如下图所示：

从逻辑上看，通过futex实现的互斥锁和内核中的互斥锁mutex是一样的（通过futex实现的读写锁的概念和内核的rwsem也是一样，不再赘述），只不过futex互斥锁是分裂开的：futex word和等待队列是分别在用户空间和内核空间，内核的mutex互斥锁可以讲把待队列头放置在mutex对象上，但是对于futex，我们没有对应的内核锁对象，因此我们就需要一个算法将futex word和其等待队列映射起来。为了管理挂入等待队列的futex阻塞任务，内核建立了一个hansh table如下：

在初始化的时候，内核会构建hashsize个futex hash bucket结构，每个bucket用来管理futex链表（hash key相同）。futex_hash_bucket数据结构定义如下：

每一个等待在futex word的task都有一个futex_q对象（后文称之futex阻塞任务对象），根据其哈希值挂入不同的队列：

通过上面的数据结构，只要有了futex word，那么我们就能根据hash key定位到其挂入的链表。当然，为了精准的匹配，还需要其futex key完全相等，具体请参考match_futex函数。关于优先级继承相关的成员后面会详细描述。

四、Futex wait的流程为何？

futex_wait函数的流程如下：

1、如果参数中给定了timeout，那么调用futex_setup_timer来创建一个hrtimer来打断futex wait阻塞状态。

2、通过三元组计算futex hash key，对于process-private类型的futex word，hash key是根据进程地址空间和futex word的虚拟地址来计算，也就是说三元组是( current->mm, address, 0 )。对于share类型的futex word，它会被放置到共享的内存中（通过mmap或者shmat）。在这种场景下，futex word在不同进程中有不同的虚拟地址，但是物理地址是相同的，通过地址空间中的虚拟地址来计算hash key是行不通的。因此share类型的futex word使用的三元组( inode->i_sequence, page->index, offset_within_page )这样的组合来计算hash key。具体的细节请参考get_futex_key函数。

3、有了hash key，我们就可以通过这个key找到哈希表中对应的表头（后文称之hash bucket）。由于后续会把本次futex阻塞任务对象（futex_q）挂入hash bucket，因此需要上锁。

4、在真正插入链表之前还需要校验用户空间传递来的期望值是否发生了变化（表示用户空间有其他线程对该futex word进行了修改），如果保持不变，那么就可以放心插队了，否则返回EWOULDBLOCK，当然，不要忘记解锁。

5、插队动作是在futex_wait_queue_me函数中完成。插队是考虑了优先级的：对于rt线程，优先级高的排在队首，低的在队尾。对于cfs任务，不按照优先级排队，而是采用了FIFO这样的公平策略。同样的，完成插队后不要忘记解锁。

6、马上就要阻塞了，如果参数中给定了timeout，这时候就需要启动步骤1中设置的hrtimer了。

7、在真正阻塞之前，还要进一步进行验证，毕竟这时候有可能其他的执行线索（可能是其他线程的futex wake，也可能是timeout callback）完成出队操作。这时候就不能阻塞，否者这个线程可能再也无法醒来。

8、在步骤7中阻塞后，可能有多个唤醒场景：如果任务被正常唤醒（futex wake唤醒），那么其实已经完成出队的动作，这时候直接返回即可，当然，如果有启动hrtimer，我们需要取消它。

9、如果本次futex阻塞任务对象（futex_q）仍然挂在hash bucket的链表上，那表示是有异常发生，需要进行相应的处理并在当前上下文完成出队。具体有两种情况：超时或者被信号打断。

10、如果设置了超期时间，那么在当前上下文会定义hrtimer_sleeper的对象，如果的确是超期唤醒的话，在timer的上下文中会把hrtimer_sleeper中的task成员清掉（设置为NULL），通过这个可以判断是否是超期唤醒。

11、如果当前任务有pending的信号，那说明是被信号打断。如果没有pending信号，那说明是spurious wakeup，需要再尝试一次futex入队操作。

12、一般而言，如果被信号打断，直接返回ERESTARTSYS，让用户空间程序自己决定怎么后续处理就OK了。但是有一种情况例外，那就是设置了timeout（即还没有超期就被信号打断），这种场景需要restart syscall。

五、Futex wake的流程为何？

相比futex_wait，futex_wake就比较简单了，其核心操作就是出队和唤醒futex wait阻塞的任务，具体流程如下：

1、首先通过hash key找到对应的hash bucket，这个操作和futex_wait中是一样的。

2、hash bucket中的链表上的futex阻塞任务对象（futex_q）只是由于hash key相同而走到一起的，实际上并非一定是对应的futex word，因此我们需要遍历链表进行匹配。具体匹配的准则就是三元组完全相等。

3、三元组相等只能说明futex word是对应上了，但是futex机制也提供了用户可以控制唤醒的方法：比特匹配。在futex wait的时候，上层的应用程序可以传递bitset参数来标记自己（FUTEX_WAIT_BITSET），在futex wake的时候，应用程序会传递bitset参数来通知内核自己想要唤醒哪些线程（FUTEX_WAKE_BITSET）。对于FUTEX_WAIT和FUTEX_WAKE，bitset做了特殊处理，设置为FUTEX_BITSET_MATCH_ANY，即futex wake的时候可以唤醒任何阻塞在该futex word的线程。

4、除了bitset，futex wake还可以控制唤醒线程的个数。为了完成多个线程的唤醒，这里使用了唤醒队列（wake queue）。当找到匹配的futex_q的时候，将其从hash bucket的队列中删除，加入到唤醒队列上来。需要注意的是：在进行这些队列操作的时候需要持有hash buck的自旋锁。

5、完成指定数量的扫描之后会结束遍历，调用wake_up_q将wake queue的任务逐个唤醒。

六、Futex requeue是什么鬼？

在讲requeue流程之前我们需要先明白为何会有requeue这个op code。我们以java中的wait-notify机制来说明这个问题。我们有如下的java代码：

编辑切换为居中

添加图片注释，不超过 140 字（可选）

Java中的Wait和notify的功能是native实现，在虚拟机提供支持。Synchronized是java内嵌锁，在虚拟机对应monitor lock（互斥锁），A临界区和B临界区都由monitor lock保护，确保了只有一个线程进入。为了确保A、B临界区的先后关系（A临界区需要等待B临界区的事件通知），我们引入了condition varible。在wait-notify场景中有两个等待队列：一个是monitor lock的等待队列，另外一个是condition varible的等待队列。而对于wait而言，它需要涉及两个等待队列的操作：一个是释放monitor lock（唤醒其等待队列的任务），一个是阻塞在条件变量上（把自己挂入其等待队列）。如果没有requeue，那么这样的操作需要两次futex的系统调用，有了futex requeue，一次futex就OK了。

了解了requeue的由来，其流程也是非常的简单，特别是有了上面两节futex wait和futex wake基础。Requeue的流程如下（requeue有normal requeue和pi requeue，这里我们主要描述normal requeue的流程）：

1、Requeue涉及两个futex，分别用uaddr1和uaddr2表示。这里需要唤醒nr_wake个uaddr1上的线程，同时把其上的nr_requeue个等待任务对象转移到uaddr2对应的等待队列上。首先调用get_futex_key获取两个futex的hash key，并根据hash key找到对应的hash bucket（hash_futex函数）

2、如果是FUTEX_CMP_REQUEUE，那么我们还需要校验uaddr1中的值。需要特别说明的是：这里涉及内核空间访问用户空间的变量，读操作是一个非常复杂的过程，具体参考get_futex_value_locked函数。这些逻辑和本文的主题关系不大，就不再赘述了。

3、遍历uaddr1 等待队列上的所有等待任务对象（futex_q），将nr_wake个futex_q通过mark_wake_futex暂存在wake_q唤醒队列上。通过requeue_futex将uaddr1 等待队列上nr_requeue个futex_q对象转移到uaddr2的等待队列上。注意，这些操作需要持有两个hash bucket的自旋锁。

4、调用wake_up_q函数唤醒之前挂入唤醒队列的任务