健壮的 futex ABI

作者:

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

健壮 futex（Robust_futexes）提供了一种除常规 futex 之外的机制，用于在任务退出时由内核协助清理持有的锁。

线程当前持有哪些 futex 的相关数据保存在用户空间的一个链表中，当获取和释放锁时，可以高效地对其进行更新而无需内核干预。除了普通 futex 所需的干预之外，robust_futexes 仅需以下额外的内核干预：

  1. 每个线程进行一次性调用，以告知内核其持有的 robust_futexes 链表从何处开始，以及

  2. 退出时的内核内部代码，用于处理退出线程所持有的链表中的任何锁。

现有的常规 futex 已经提供了一种“快速用户空间锁”（Fast Userspace Locking）机制，它在无竞争加锁时无需系统调用，而在有竞争加锁时通过在内核中维护等待线程列表来处理。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” 指向线程地址空间中由三个字（word）组成的结构。在 32 位架构上每个字为 32 位，在 64 位架构上为 64 位，且使用本地字节序。每个线程都应当拥有自己线程私有的 “head”。

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

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

第二个字称为 “offset”，指定了从关联的“锁条目”地址开始，正向或负向偏移到被称为“锁字”（lock word）的地址的偏移量。与上面其他字不同，“锁字”始终是 32 位的。“锁字”的高 2 位包含 2 个标志位，低 30 位包含持有该锁的线程的线程 ID (TID)。有关标志位的描述，请参见下文。

第三个字称为 “list_op_pending”，在链表插入和删除期间包含“锁条目”地址的临时副本，若线程在加锁或解锁操作的中途退出，则需要它来正确解决竞态条件。

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

“锁字”始终为 32 位，旨在与 robust_futexes 结合使用，作为 futex 机制所使用的同一个 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 嵌入到更大的用户级锁结构中，每个锁一个。内核的 robust_futex 机制并不关心该结构中还有什么其他内容，只要该线程使用的所有 robust_futexes 到“锁字”的 “offset” 相同即可。线程应使用“锁条目”指针将其当前持有的锁链接起来。锁之间也可能具有其他链接（例如双向链表的反向指针），但这与内核无关。

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

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

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

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

在从其持有的锁列表中添加或移除锁时，为了让内核无论任务何时退出都能正确处理锁清理（例如在操作此链表的中途收到了意外的信号 9），用户代码在进行“锁条目”的插入和移除时必须遵守以下协议

插入时

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

  2. 获取 futex 锁，

  3. 将锁条目（其“锁字”的低 30 位中包含线程 ID (TID)）添加到以 “head” 开头的链表中，并且

  4. 清除 “list_op_pending” 字。

移除时

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

  2. 从 “head” 链表中移除该锁的锁条目，

  3. 释放 futex 锁，并且

  4. 清除 “lock_op_pending” 字。

请注意，纯粹在用户空间中移除 robust futex 存在竞态条件。请参阅下一章以了解更多信息以及如何避免这种情况。

在退出时，内核将检查存储在 “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 时，它对该条目不做任何处理，并继续处理下一个条目。

健壮释放存在竞态条件

仅在用户空间中将 robust futex 从链表中移除存在竞态条件。引用 Thomas Gleixner 的解释

robust futex 解锁机制在清除 robust_list_head::list_op_pending 指针方面存在竞态条件，因为解锁和清除指针不是原子的。竞态窗口位于解锁和清除 pending 操作指针之间。如果任务被迫在此窗口中退出，退出时在清理 robust 链表时将访问可能无效的 pending 操作指针。如果另一个任务在清理之前设法取消映射包含该锁的对象，就会发生这种情况，从而导致 UAF。在最坏的情况下，当访问发生时，如果无关的内容已被映射到相同的地址，这个 UAF 会导致内存损坏。

可在 https://lore.kernel.org/lkml/20260316162316.356674433@kernel.org/ 阅读完整的深入分析

为了克服这一问题，内核需要参与锁释放操作。这确保了释放操作在“释放锁”以及“从 list_op_pending 中移除地址”这两个动作方面是“原子”发生的。如果释放操作被信号中断，内核还将验证它是否中断了释放操作。

对于有竞争的解锁情况（即其他线程正在等待锁释放），futex() 系统调用提供了 FUTEX_ROBUST_UNLOCK 操作特性标志，它必须与以下操作之一结合使用：FUTEX_WAKE、FUTEX_WAKE_BITSET 或 FUTEX_UNLOCK_PI。内核将释放锁（将 futex 字设置为零），并清除 list_op_pending 字段。然后，它将继续执行常规的唤醒路径。

对于无竞争路径，检查 futex 字与清除 list_op_pending 字段之间仍然存在竞态条件。为了在不需要完整系统调用的情况下解决此问题，用户空间应调用虚拟系统调用 __vdso_futex_robust_listXX_try_unlock()（其中 XX 为 32 或 64，取决于指针的大小）。如果 vDSO 调用成功，则意味着它已经释放了锁并清除了 list_op_pending。如果失败，则意味着该锁有等待者，需要调用带有 FUTEX_ROBUST_UNLOCK 的 futex() 系统调用。