强健 futex 的说明¶
- 发起人:
Ingo Molnar <mingo@redhat.com>
背景¶
什么是强健 futex？要回答这个问题，我们首先需要了解什么是 futex：普通的 futex 是一种特殊的锁，在无竞争的情况下，它们可以在用户空间获取/释放，而无需进入内核。
futex 本质上是一个用户空间地址，例如一个 32 位的锁变量字段。如果用户空间注意到竞争（锁已被占用且其他人也想获取它），那么该锁会被标记为一个值，表示“有一个等待者挂起”，并且使用 sys_futex(FUTEX_WAIT) 系统调用来等待对方释放它。内核在内部创建一个“futex 队列”，以便稍后能够将等待者与唤醒者匹配起来 —— 而无需它们互相了解。当拥有者线程释放 futex 时，它会（通过变量值）注意到有挂起的等待者，并执行 sys_futex(FUTEX_WAKE) 系统调用来唤醒它们。一旦所有等待者都获取并释放了锁，futex 就会回到“无竞争”状态，并且没有与其关联的内核态状态。内核会完全忘记该地址曾经存在过 futex。这种方法使 futex 非常轻量且具有可扩展性。
“强健性”是指在持有锁的同时处理崩溃：如果一个进程在持有与其他进程共享的 pthread_mutex_t 锁时过早退出（例如 yum 在持有 pthread_mutex_t 时发生段错误，或者 yum 被 kill -9 杀死），那么该锁的等待者需要被通知，因为该锁的最后一个拥有者以某种不正常的方式退出了。
为了解决这类问题，“强健互斥锁”用户空间 API 被创建出来：如果拥有者过早退出，pthread_mutex_lock() 会返回一个错误值 —— 新的拥有者可以决定该锁保护的数据是否可以被安全地恢复。
然而，基于 futex 的互斥锁存在一个很大的概念问题：是内核销毁了拥有者任务（例如由于段错误 SEGFAULT），但内核无法协助清理：如果没有“futex 队列”（并且在大多数情况下确实没有，因为 futex 是快速轻量级锁），那么内核就没有信息来清理所持有的锁！用户空间也没有机会在锁之后进行清理 —— 用户空间是崩溃的一方，因此它没有机会进行清理。进退维谷（Catch-22）。
在实践中，例如当 yum 被 kill -9 杀死（或发生段错误）时，需要重启系统来释放基于 futex 的锁。这是针对 yum 的主要 bug 报告之一。
为了解决这个问题，传统的方法是扩展 vma（虚拟内存区域描述符）概念，引入“附加到该区域的挂起强健 futex”的概念。这种方法需要向 sys_futex() 引入 3 种新的系统调用变体：FUTEX_REGISTER、FUTEX_DEREGISTER 和 FUTEX_RECOVER。在 do_exit() 时，会搜索所有的 vma，以查看它们是否设置了 robust_head。这种方法遗留了两个根本性问题
它具有相当复杂的锁和竞争场景。基于 vma 的方法已经搁置多年，但它们仍然不够完全可靠。
它们必须在每个线程的
sys_exit()时扫描*每一个* vma！
第二个缺点是致命的：在 Linux 上 pthread_exit() 大约需要 1 微秒，但如果有数千（或数万）个 vma，每次 pthread_exit() 都需要一毫秒或更长时间，同时还会彻底破坏 CPU 的 L1 和 L2 缓存！
即使对于普通的进程 sys_exit_group() 调用，这也是非常明显的：内核必须无条件地进行 vma 扫描！（这是因为内核不知道有多少个强健 futex 需要清理，因为强健 futex 可能在另一个任务中注册过，并且 futex 变量可能只是被 mmap() 到了当前进程的地址空间中）。
这种巨大的开销迫使人们创建了 CONFIG_FUTEX_ROBUST，以便普通内核可以将其关闭，但更糟糕的是：这种开销使得强健 futex 对于任何类型的通用 Linux 发行版来说都不切实际。
所以必须采取一些措施。
强健 futex 的新方法¶
这种新方法的核心是用户空间持有的每个线程私有的强健锁列表（由 glibc 维护）—— 该用户空间列表通过一个新的系统调用注册到内核中 [这种注册在每个线程生命周期中最多发生一次]。在 do_exit() 时，内核会检查这个用户空间列表：是否有需要清理的强健 futex 锁？
在常见情况下，在 do_exit() 时，没有注册列表，因此强健 futex 的成本只是一个 current->futex.robust_list != NULL 的比较。如果线程已经注册了一个列表，那么通常该列表是空的。如果线程/进程崩溃或以某种不正确的方式终止，则该列表可能不为空：在这种情况下，内核会仔细遍历该列表 [不盲目信任它]，用 FUTEX_OWNER_DIED 位标记该线程拥有的所有锁，并唤醒一个等待者（如果有的话）。
在 do_exit() 时，该列表保证是私有的且属于每个线程，因此内核可以以无锁方式访问它。
不过，可能会存在一种竞争条件：由于向列表添加和从列表中删除是在 glibc 获取 futex 之后完成的，因此线程（或进程）在那里死掉留下了几条指令的窗口期，从而导致 futex 挂起。为了防止这种可能性，用户空间（glibc）还维护了一个简单的每个线程的“list_op_pending”字段，以便在线程获取锁之后、但在将其自身添加到列表之前刚好死掉时，允许内核进行清理。Glibc 在尝试获取 futex 之前设置此 list_op_pending 字段，并在列表添加（或列表删除）完成后清除它。
这就是所需的全部内容 —— 强健 futex 清理的其余部分都在用户空间完成 [就像之前的补丁一样]。
Ulrich Drepper 已经为这个新机制实现了必要的 glibc 支持，从而完全启用了强健互斥锁。
与基于 vma 的方法相比，这种基于用户空间列表的方法的关键区别在于
它快得多得多：在线程退出时，不需要遍历每一个 vma（！），而基于 VM 的方法必须这样做。只需执行一个非常简单的“列表是否为空”操作。
不需要对 VM 进行任何更改 —— ‘
struct address_space’ 保持原样。不需要注册单独的锁：强健互斥锁不需要任何额外的每个锁的系统调用。因此，强健互斥锁成为一种非常轻量级的原语 —— 它们不会迫使应用程序设计人员在性能和强健性之间做出艰难的选择 —— 强健互斥锁同样快速。
不会发生每个锁的内核分配。
不需要资源限制。
不需要内核空间恢复调用（FUTEX_RECOVER）。
实现和加锁是“显而易见”的，并且与 VM 没有交互。
性能¶
我使用新方法对内核处理 100 万（！）个持有的锁的列表所需的时间进行了基准测试 [在 2GHz CPU 上]
设置了 FUTEX_WAIT [存在竞争的互斥锁]：130 毫秒
未设置 FUTEX_WAIT [无竞争的互斥锁]：30 毫秒
我还测试了一种由 glibc 进行锁通知的方法 [目前对于 !pshared 强健互斥锁就是这样做的]，这耗费了 256 毫秒 —— 明显更慢，因为用户空间必须执行 100 万次 FUTEX_WAKE 系统调用。
（100 万个持有的锁闻所未闻 —— 我们预计同时最多只会有少数几个锁被持有。尽管如此，很高兴得知这种方法具有良好的可扩展性。）
实现细节¶
该补丁添加了两个新的系统调用：一个用于注册用户空间列表，另一个用于查询注册的列表指针
asmlinkage long
sys_set_robust_list(struct robust_list_head __user *head,
size_t len);
asmlinkage long
sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr,
size_t __user *len_ptr);
列表注册非常快：指针简单地存储在 current->futex.robust_list 中。[请注意，将来如果强健 futex 变得普及，我们可以扩展 sys_clone() 为新线程注册一个强健列表头，而无需另一个系统调用。]
因此，对于不使用强健 futex 的任务，开销几乎为零，即使对于强健 futex 用户，每个线程生命周期也只有一个额外的系统调用，并且清理操作（如果发生的话）也是快速且直接的。内核在内部对强健 futex 和普通 futex 没有做任何区分。
如果在退出时发现某个 futex 仍被持有，内核会设置 futex 字的以下位
#define FUTEX_OWNER_DIED 0x40000000
并唤醒下一个 futex 等待者（如果有的话）。用户空间负责完成其余的清理工作。
否则，glibc 通过将 TID 原子地写入 futex 字段来获取强健 futex。等待者设置 FUTEX_WAITERS 位
#define FUTEX_WAITERS 0x80000000
剩余的位留给 TID。
测试、架构支持¶
我已经在 x86 和 x86_64 上测试了新的系统调用，并且确保了即使故意损坏用户空间列表，对该列表的解析也是强健的 [ ;-) ]。
目前 i386 and x86_64（注：原文保留 i386 和 x86_64）的系统调用已经连通，Ulrich 已经测试了新的 glibc 代码（在 x86_64 和 i386 上），并且它适用于他的强健互斥锁测试用例。
所有其他架构应该也能很好地编译 —— 但它们暂时还没有新的系统调用。
各架构在编写系统调用之前，需要实现新的 futex_atomic_cmpxchg_inatomic() 内联函数。