关于健壮 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 的互斥锁存在一个很大的概念问题：是内核销毁了所有者任务（例如，由于段错误），但内核无法帮助清理：如果没有“futex 队列”（并且在大多数情况下没有，futex 是快速的轻量级锁），那么内核没有信息来清理持有的锁！用户空间也没有机会在锁之后进行清理 - 用户空间是崩溃的那个，因此它没有机会进行清理。进退两难。
实际上，例如当 yum 被 kill -9（或段错误）时，需要系统重启才能释放该基于 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 字段，并在列表添加（或列表删除）完成后清除它。
这就是所需要的全部 - 所有剩余的健壮-futex 清理都在用户空间中完成 [就像以前的补丁一样]。
Ulrich Drepper 已经实现了这种新机制所需的 glibc 支持，从而完全启用了健壮互斥锁。
与基于 vma 的方法相比，这种基于用户空间列表的方法的主要区别
它快得多：在线程退出时，无需循环遍历每个 vma (!)，而基于 VM 的方法必须这样做。只执行一个非常简单的“列表是否为空”操作。
不需要 VM 更改 - ‘
struct address_space’ 保持不变。不需要注册单个锁：健壮互斥锁不需要任何额外的每个锁系统调用。因此，健壮互斥锁成为一个非常轻量级的原语 - 因此它们不会迫使应用程序设计者在性能和健壮性之间做出艰难的选择 - 健壮互斥锁同样快。
不会发生每个锁的内核分配。
不需要资源限制。
不需要内核空间恢复调用 (FUTEX_RECOVER)。
实现和锁定是“显而易见的”，并且与 VM 没有交互。
性能¶
我使用新方法 [在 2GHz CPU 上] 对内核处理 100 万个 (!) 持有锁列表所需的时间进行了基准测试
设置了 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 上），它对于他的健壮互斥测试用例有效。
所有其他架构应该也可以正常构建 - 但它们目前还没有新的系统调用。
架构需要先实现新的 futex_atomic_cmpxchg_inatomic() 内联函数，然后再编写系统调用。