健壮的 Futex ABI

作者:

由 Paul Jackson <pj@sgi.com> 发起

Robust_futexes 提供了一种机制，除了正常的 futexes 之外，还用于在任务退出时内核辅助清理持有的锁。

关于线程持有哪些 futexes 的有趣数据保存在用户空间的一个链表中，在获取和释放锁时可以有效地更新该链表，而无需内核干预。 除了 futexes 之外，robust_futexes 所需的唯一额外内核干预是

  1. 每个线程一次性调用，告诉内核其持有的 robust_futexes 列表的起始位置，以及

  2. 在退出时，内部内核代码处理正在退出的线程持有的任何列出的锁。

现有的普通 futexes 已经提供了一种“快速用户空间锁定”机制，该机制无需系统调用即可处理无竞争锁定，并通过在内核中维护等待线程的列表来处理有竞争锁定。 sys_futex(2) 系统调用上的选项支持等待特定的 futex，以及唤醒特定 futex 上的下一个等待者。

为了使 robust_futexes 工作，用户代码（通常在与应用程序链接的 glibc 等库中）必须完全按照内核期望的方式管理和放置必要的列表元素。 如果它未能做到这一点，那么未正确列出的锁将不会在退出时被清理，可能会导致死锁或等待相同锁的其他线程的其他此类故障。

预计可能使用 robust_futexes 的线程应首先发出系统调用

asmlinkage long
sys_set_robust_list(struct robust_list_head __user *head, size_t len);

指针 “head” 指向线程地址空间中的一个结构，该结构由三个字组成。在 32 位架构上，每个字都是 32 位，在 64 位架构上，每个字都是 64 位，并且是本地字节序。 每个线程都应该有自己的线程私有 “head”。

如果一个线程在 64 位原生架构内核上以 32 位兼容模式运行，那么它实际上可以有两个这样的结构 - 一个使用 32 位字用于 32 位兼容模式，另一个使用 64 位字用于 64 位原生模式。 如果内核是支持 32 位兼容模式的 64 位内核，那么如果已发出相应的 sys_set_robust_list() 调用来设置该列表，它将尝试在每个任务退出时处理两个列表。

“head” 处的内存结构中的第一个字包含指向 “锁条目” 的单链表的指针，每个锁一个，如下所述。 如果列表为空，则指针将指向自身，即 “head”。 最后一个 “锁条目” 指回 “head”。

第二个字，称为 “offset”，指定从相关的 “锁条目” 的地址到 “锁字” 的偏移量，加或减。“锁字” 始终是一个 32 位字，这与其他字不同。“锁字” 在高 2 位中保存 2 个标志位，在低 30 位中保存持有锁的线程的线程 ID (TID)。 有关标志位的说明，请参见下文。

第三个字，称为 “list_op_pending”，在列表插入和删除期间包含 “锁条目” 地址的瞬态副本，并且需要正确解决线程在锁定或解锁操作中间退出时可能出现的竞争。

从 “head” 开始的单链表上的每个 “锁条目” 仅由一个字组成，该字指向下一个 “锁条目”，如果没有更多条目，则指回 “head”。 此外，在每个 “锁条目” 附近，在 “offset” 字指定的距 “锁条目” 的偏移量处，是一个 “锁字”。

“锁字” 始终是 32 位，旨在成为 futex 机制使用的相同的 32 位锁变量，与 robust_futexes 结合使用。 只有下一个线程使用 futex 机制向内核注册了该 “锁字” 的地址，内核才能在线程退出时唤醒等待锁的下一个线程。

对于线程当前持有的每个 futex 锁，如果它希望对此锁的退出清理提供 robust_futex 支持，则它应该在此列表上有一个 “锁条目”，其关联的 “锁字” 位于指定的 “offset” 处。 如果一个线程在持有任何此类锁时死亡，内核将遍历此列表，使用一个指示其持有者死亡的位来标记任何此类锁，并使用 futex 机制唤醒等待该锁的下一个线程。

当一个线程调用上述系统调用以表明它期望使用 robust_futexes 时，内核会存储该任务传入的 “head” 指针。 该任务可以通过使用系统调用稍后检索该值

asmlinkage long
sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr,
                    size_t __user *len_ptr);

预计线程将使用嵌入到更大的用户级别锁定结构中的 robust_futexes，每个锁一个。 内核 robust_futex 机制并不关心该结构中还有什么，只要所有线程使用的 robust_futexes 的 “锁字” 的 “offset” 相同即可。 该线程应使用 “锁条目” 指针链接它当前持有的锁。 它可能还在锁之间有其他链接，例如双链表的反面，但这对于内核来说无关紧要。

通过以这种方式保持其锁链接，在一个以内核已知的 “head” 指针开始的列表上，内核可以为线程提供 robust_futexes 可用的基本服务，即帮助清理在（可能意外的）退出时持有的锁。

正常操作期间的实际锁定和解锁完全由争用线程中的用户级别代码处理，并由现有的 futex 机制等待和唤醒锁。 内核在 robust_futexes 中唯一的基本参与是记住列表 “head” 的位置，并在线程退出时遍历列表，处理离开线程仍然持有的锁，如下所述。

在一个线程的共享内存中，在给定的时间点，各种数据结构上可能存在数千个 futex 锁结构。 在给定时间，只有该线程当前持有的锁的锁结构才应该在该线程的 robust_futex 链接锁列表上。

用户共享内存区域中的给定 futex 锁结构可以在不同的时间被有权访问该区域的任何线程持有。 当前持有此类锁的线程（如果有）在 “锁字” 的低 30 位中用线程的 TID 标记。

当从其持有的锁的列表中添加或删除锁时，为了使内核能够正确处理锁清理，无论任务何时退出（可能在操作此列表的中间获得意外的信号 9），用户代码必须在 “锁条目” 插入和删除时遵守以下协议

在插入时

  1. 将 “list_op_pending” 字设置为要插入的 “锁条目” 的地址，

  2. 获取 futex 锁，

  3. 将锁条目及其线程 ID (TID) 添加到 “锁字” 的低 30 位，添加到从 “head” 开始的链表中，以及

  4. 清除 “list_op_pending” 字。

在删除时

  1. 将 “list_op_pending” 字设置为要删除的 “锁条目” 的地址，

  2. 从此锁的 “head” 列表中删除锁条目，

  3. 释放 futex 锁，以及

  4. 清除 “lock_op_pending” 字。

在退出时，内核将考虑存储在 “list_op_pending” 中的地址和通过遍历从 “head” 开始的列表找到的每个 “锁字” 的地址。 对于每个这样的地址，如果从该地址偏移 “offset” 的 “锁字” 的低 30 位等于退出线程的 TID，则内核将执行两件事

  1. 如果在该字中设置了位 31 (0x80000000)，则尝试在该地址上进行 futex 唤醒，这将唤醒下一个使用 futex 机制等待该地址的线程，以及

  2. 原子地在 “锁字” 中设置位 30 (0x40000000)。

在上面，位 31 由该锁上的 futex 等待者设置，以指示他们正在等待，位 30 由内核设置，以指示锁所有者死亡时持有该锁。

如果内核在任何时候发现以下情况，退出代码将静默停止扫描列表

  1. “head” 指针或后续链接列表指针不是用户空间字的有效地址

  2. “锁字” 的计算位置（地址加上 “offset”）不是 32 位用户空间字的有效地址

  3. 如果列表包含超过 100 万个元素（可能会受到未来内核配置更改的影响）。

当内核看到一个列表条目的 “锁字” 的低 30 位中没有当前线程的 TID 时，它不会对该条目执行任何操作，而是转到下一个条目。