健壮的 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 机制与 robust_futexes 结合使用的相同 32 位锁变量。 只有当下一个线程使用 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，每个锁一个。 只要 ‘锁字’ 的 ‘offset’ 对于该线程使用的所有 robust_futexes 相同，内核 robust_futex 机制就不关心该结构中的其他内容。 线程应使用 ‘锁条目’ 指针链接其当前持有的锁。 它还可以在锁之间有其他链接，例如双向链表的反面，但这对于内核来说无关紧要。

通过以这种方式保持其锁的链接，在内核已知的 ‘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 时，它不会对该条目执行任何操作，而是继续到下一个条目。