关于健壮型 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-ed），那么该锁的等待者需要被通知该锁的最后一个所有者以某种不规则的方式退出。
为了解决这类问题，创建了“健壮互斥锁”用户空间 API：如果所有者过早退出，pthread_mutex_lock() 会返回一个错误值 - 并且新的所有者可以决定由该锁保护的数据是否可以安全恢复。
但是基于 futex 的互斥锁存在一个很大的概念问题：是内核销毁了所有者任务（例如，由于 SEGFAULT），但是内核无法帮助进行清理：如果没有“futex 队列”（并且在大多数情况下没有，因为 futex 是快速的轻量级锁），那么内核没有信息来清理持有的锁！用户空间也没有机会清理锁 - 用户空间是崩溃的一方，因此它没有机会清理。进退两难。
实际上，当例如 yum 被 kill -9-ed（或发生段错误）时，需要系统重启才能释放基于该 futex 的锁。 这是针对 yum 的主要错误报告之一。
为了解决这个问题，传统的方法是扩展 vma（虚拟内存区域描述符）概念，使其具有“附加到此区域的待处理健壮型 futex”的概念。 这种方法需要 3 个新的 sys_futex() 系统调用变体：FUTEX_REGISTER、FUTEX_DEREGISTER 和 FUTEX_RECOVER。 在 do_exit() 时，会搜索所有 vma 以查看它们是否设置了 robust_head。 这种方法仍然存在两个根本问题
它具有相当复杂的锁机制和竞争场景。 基于 vma 的方法已经挂起多年，但它们仍然不完全可靠。
它们必须在 sys_exit() 时扫描 _每个_ vma，每个线程！
第二个缺点是真正的杀手：pthread_exit() 在 Linux 上大约需要 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->robust_list != NULL 比较。 如果线程注册了一个列表，那么通常该列表是空的。 如果线程/进程崩溃或以某种不正确的方式终止，那么该列表可能非空：在这种情况下，内核会仔细地遍历该列表 [不信任它]，并将该线程拥有的所有锁标记为 FUTEX_OWNER_DIED 位，并唤醒一个等待者（如果有）。
该列表保证在 do_exit() 时是私有的和每个线程的，因此内核可以以无锁方式访问它。
但是存在一种可能的竞争：由于添加到列表和从列表删除是在 glibc 获取 futex 之后完成的，因此线程（或进程）可能会在那里死亡，从而使 futex 挂起。 为了防止这种可能性，用户空间 (glibc) 还维护一个简单的每个线程的 'list_op_pending' 字段，以便内核在线程获取锁后但在添加到列表之前死亡时进行清理。 Glibc 在尝试获取 futex 之前设置此 list_op_pending 字段，并在列表添加（或列表删除）完成后清除它。
这就是所需要的全部 - 所有剩余的 robust-futex 清理都在用户空间中完成 [就像之前的补丁一样]。
Ulrich Drepper 已经实现了这个新机制所需的 glibc 支持，这完全启用了健壮互斥锁。
与基于 vma 的方法相比，这种基于用户空间列表的方法的主要区别
它更快得多：在线程退出时，无需遍历每个 vma (!)，而 VM-based 方法必须这样做。 只需一个非常简单的“列表是否为空”操作即可。
不需要 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->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 和 x86_64 系统调用目前已连接，Ulrich 已经测试了新的 glibc 代码（在 x86_64 和 i386 上），它适用于他的 robust-mutex 测试用例。
所有其他架构也应该构建良好 - 但它们还没有新的系统调用。
架构需要在编写系统调用之前实现新的 futex_atomic_cmpxchg_inatomic() 内联函数。