RT-Mutex-3——实现分析-pi-futex与rt-mutex

一、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。

从任务 task_struct 结构的视角来看 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 C ---> 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 的流程留给读者自行分析了。

四、总结

1. 上层也可以通过 pi-futex 使用内核中 rt-mutex 的逻辑。

参考：
futex基础问答：http://www.wowotech.net/kernel_synchronization/futex.html