一、什么是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还有其他利用在复杂场景的操做码，因为在手机场景没有利用，本文不再介绍。
我们整理各个操做码的参数如下：
三、关于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代码：
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函数唤醒之前挂进唤醒队列的使命
七、为何futex要撑持PI？
Non-PI futex引起的优先级翻转（priority inversion）问题如下图所示：
低优先级使命C起首持锁，如许当高优先级使命A试图持锁失败进进D形态。一般而言，C使命临界区比力短，完成之后就释放锁，使命A就能够施行了。然而，在C施行过程中，中等优先级的使命B被唤醒，侵占了使命C的施行，那时候，所有优先级在A和C之间的使命都能够侵占C的施行，从而使得使命A无法在确定的时间内获取到CPU资本。
PI futex中的PI就是priority inheritance，能够通过优先级继续的办法来处理系统中呈现的优先级翻转问题。详细的办法就是当使命A持锁失败的时候，锁的owner task（即使命C）需要暂时性的把优先级提拔至使命A的优先级。而在释放锁的时候，将其优先级停止恢复原值。
当然，上面只是一个简单的例子，现实系统会涉及更多的锁和线程，但原理类似。关于线程，我们需要笔录：
1、该线程持锁哪些锁，那些锁的top waiter是谁，对所有的top waiter根据优先级停止排序。
2、该线程阻塞在哪一把锁上
关于锁，我们需要笔录：
1、该锁的owner是谁
2、阻塞在该锁的线程们（根据优先级停止排序）。
重视，那里我们把优先级更高的阿谁阻塞线程喊做该所的top waiter。
有了那些信息，我们需要庇护一个原则就OK了：一个使命的暂时优先级应该提拔至其持有锁的top waiter线程中更高的阿谁优先级。
八、Rt mutex的原理为何？
PI-futex是通过rt mutex来实现的，因而我们那里简单的聊一聊内核的那个PI-aware mutex。
从rt mutex的视角看使命：
rt_mutex_waiter用来笼统一个阻塞在rt mutex的使命：task成员指向那个使命，lock成员指向对应的rt mutex对象，tree_entry是挂进blocker红黑树的节点，rt mutex对象的waiters成员就是那颗红黑树的根节点（wait_lock成员用来庇护红黑树的操做）。而owner则指向持锁的使命。需要特殊阐明的是waiters那个红黑树是根据使命优先级排序的，left most节点就是对应该锁的top waiter。
从使命的视角来看rt mutex：
为了撑持rt mutex，task struct也增加了若干的成员，最重要的就是pi_waiters。因为一个使命能够持有多把锁，每把锁都有top waiter，因而和一个使命联系关系的top waiter也有十分多，那些top waiter构成了一个红黑树（同样也是根据优先级排序），pi_waiters成员就是那颗红黑树的根节点。那颗红黑树的left most的使命优先级就是实现优先级继续协议中规定要暂时提拔的优先级。pi_top_task成员指向了left most节点对应的使命对象，我们称之top pi waiter。Task struct的pi_blocked_on成员则指向其阻塞的rt_mutex_waiter对象。
有了上面的根本概念之后，我们讲一下PI chain的概念。起首看看使命和锁的根本关系，如下图所示：
在上面的图片中，task 1持有了Lock A和Lock B，阻塞在Lock C上。一个使命只能阻塞在一个锁上，所以红色箭头只能是从使命到锁，不克不及分叉。因为一个使命能够持有多把锁，所以黑色箭头会有多个锁指向一个使命，即多把锁会聚于使命。有了那个根本的关系图之后，我们能够构成愈加复杂的使命和锁的逻辑图，如下：
在上面那张图中有四条PI chain：
1、Lock D---task 2
2、task 4---Lock D---task 2
3、Lock A---task 1---Lock C---task 2
4、task 3---Lock B---task 1---Lock C---task 2
为了可以让PI一般起感化，PI chain中的使命必需庇护如许的关系：处于PI chain中右端的使命的优先级必需大于等于PI chain中左端的使命们。我们以第四条PI chain为例，使命2的优先级必需大于等于使命1和使命3的优先级，而使命1的优先级必需要大于等于使命3的优先级。
九、PI futex和rt mutex有什么关系？
熟悉Linux的工程师都领会内核中的mutex互斥锁以及撑持PI的互斥锁版本rt mutex。假设想让用户空间的互斥锁实现优先级继续的功用，那么其实不需要futex模块实现复杂的PI chain，现实上对PI形态的跟踪是通过rt mutex代办署理来完成的，原理图如下：
我们先看接口部门，normal futex利用FUTEX_WAIT和FUTEX_WAKE操做码来完成阻塞和唤醒的动做。关于PI futex而言，FUTEX_LOCK_PI用来施行上锁，而FUTEX_UNLOCK_PI用来完成解锁。那里的lock和unlock其实是对futex的代办署理rt mutex而言的。
无论是normal futex仍是PI futex，阻塞于futex的使命城市有一个futex_q对象与之对应。关于normal futex，有了futex_q对象，挂进期待队列和将其唤醒的功用都能轻松实现。关于PI futex，我们不单单需要挂进队列和唤醒使命，最重要的是我们需要根据PI chain完成使命优先级的调整。为了完成那个功用，需要两个额外的对象，一个是rt_mutex_waiter，表达一个阻塞在rt mutex的使命，其rt mutex指针指向了其阻塞在哪个rt mutex上。别的一个是futex_pi_state对象，它笔录了优先级翻转的信息，包罗该用户空间上层锁对应的内核态的rt mutex，rt mutex的owner使命的信息等。
十、Pi futex逻辑过程
Pi futex次要有两个逻辑过程：通过FUTEX_LOCK_PI上锁，通过FUTEX_UNLOCK_PI完成释放锁的逻辑。
那里的“上锁”有点误导，不是“试图持锁”的意思，而是合作上层锁失败之后，陷进内核预备进进阻塞形态。那里为了笔录PI state，所以需要对代办署理rt mutex施行上锁的动做（根本上也是会阻塞在rt mutex上）。关于pi futex的。一般futex的部门，例如get hash key、找futex对应的hash bucket、插进hash队列等操做，那里不再描述，次要看PI futex特有的部门。
第一次futex lock pi略微复杂一点，需要完成owner持锁和current task的阻塞在锁上那两个动做。重视：那里的锁指的是rt mutex。当线程持上层锁胜利的时候，我们其实不能同时对rt mutex持锁胜利并设置owner，因而那时候其实不会有futex系统挪用进进内核。当第一次阻塞的时候，会通过futex系统挪用把owner id传递给内核，那时候我们需要分配一个futex pi state对象创建一个rt mutex，同时成立那个rt mutex和owner task的关系：
1、挂进owner task的futex pi state链表。一个使命能够持有多把上层锁，所以需要链表治理，当然纷歧定每一个使命持有的上层锁都有对应的futex pi state对象，没有合作也就不会陷进内核挪用FUTEX_LOCK_PI。
2、futex pi state对象的owner成员指向对应的owner task
第二个重要的动做就是让current task往获取rt mutex，上面刚刚设定了owner，那里current task持锁的成果可能率就是会阻塞，不外我们原来就是通过那个阻塞关系来完成PI 形态的跟踪的。rt_mutex_waiter对象笼统了一个阻塞在rt mutex的使命，我们需要成立rt_mutex_waiter对象、阻塞使命和rt mutex的关系，详细包罗：
1、rt_mutex_waiter对象的lock成员指向对应于的rt mutex，表达该使命阻塞在那个锁上。rt_mutex_waiter对象的task成员指向当前要阻塞的使命对象。
2、将rt_mutex_waiter对象插进rt mutex的waiters红黑树。
3、task struct的pi_blocked_on设置为该rt_mutex_waiter对象。
4、关于rt mutex而言，有了新的阻塞使命，假设优先级比目前该rt mutex的top waiter更高的话，那么需要更新owner task的top waiter，将旧的top waiter节点从红黑树中删除，将新的top waiter插进owner task的top waiter红黑树。
5、根据新的top waiter更新owner task的动态优先级。一旦修改了owner task的优先级，那么其相关的PI chain都需要停止优先级调整。
第二次以及后续的FUTEX_LOCK_PI会简单一点，因为不需要新建rt mutex对象了，只需要在bucket找到第一个futex_q对象，通过其pi state指针就能够定位rt mutex了。有了rt mutex，通过上锁即可让本身阻塞在那个rt mutex上了。
FUTEX_UNLOCK_PI的流程留给读者自行阐发了。
十一、小结
本文通干预干与答的形式简单的介绍了内核futex机造，它是上层同步机造的基石。在PI Futex的介绍中，我们对rt mutex浅尝辄行，读者未能领略其全貌。后续我们会出一篇关于rt mutex的文章，敬请等待。
参考文献：
1、linux-5.10.61内核源代码
2、linux-5.10.61\Documentation\locking\*
长按存眷
内核工匠微信
Linux 内核黑科技 | 手艺文章 | 精选教程