什么是健壮(robust) futex

看代码需要,找到了一篇内核大牛写的有来龙去脉的介绍,翻译出来分享给大家,如有错误,欢迎指正。作者是 Ingo Molnar ( mingo@redhat.com ), 匈牙利Linux黑客,在红帽工作,他最出名的是他在操作系统的安全和性能优化方面的贡献。 原文在这里

背景

什么是健壮 futex ?要回答这个问题,我们首先需要了解 futex 是什么: 普通 futex 是特殊类型的锁,非竞争情况下可以从用户空间获取和释放,而无需进入内核。

futex 本质上是一个用户空间地址,例如 32 位大小的锁变量。如果用户空间发生了竞争(锁已被一个线程持有,另外一个线程也想获取它), 该锁就被标记一个值表示”有一个挂起的等待线程”, 调用 futex(FUTEX_WAIT) 的线程将等待其它线程释放这个锁.

内核在内部创建一个 futex 队列, 以便可以匹配锁的等待线程和唤醒线程 — 等待线程和唤醒线程不需要彼此认识。

当持有 futex 的线程释放 futex 时, 它通过锁变量值知道有挂起的等待线程, 就通过futex(FUTEX_WAKE) 系统调用唤醒它们。一旦锁的所有的等待线程得到锁并释放锁, futex 再次回到非竞争状态, 并且内核不再保存该 futex 的状态。内核完全忘记了曾经在某个用户空间地址上有过一个 futex 。这使得 futex 非常轻巧且可扩展。

健壮性是持有锁的线程崩溃后如何处理:如果一个持有 pthread_mutex_t 锁的进程过早退出, 并且该锁还与其他进程共享(例如,yum在持有锁的时候出现段错误崩溃,或者在持有锁的时候被 kill -9杀掉了), 此时锁的所有等待线程需要被通知到:锁的最后一个持有线程不正常退出了。

为了解决此类问题,健壮的互斥体用户空间 API 被创造出来:如果锁的持有线程过早退出, pthread_mutex_lock 返回一个错误值 — 新的持有线程可以决定是否可以安全恢复被该锁保护的数据。

基于互斥体的 futex 有一个很大的概念问题:内核可以销毁持有 futex 的进程(例如, 发生了段错误异常),但内核不能帮助清理 futex :因为没有 futex 队列 (在大多数情况下没有, futex 是快速轻量级锁), 内核就没有信息清理持有锁!用户空间也没有机会在锁被持有后清理 — 因为进程在用户空间崩溃了。 左右为难。

在实际情况中,当 yum 被杀死(或段错误)时, 重启系统才能释放基于 futex 的锁。这是针对 yum 的错误报告的最优先的一个。

为了解决这个问题,传统方法扩展 vma (虚拟内存区域描述符)概念, 增加了一个概念:此内存区域有附加一个挂起的健壮 futex。此方法还要给 futex 系统调用新增3个命令: FUTEX_REGISTER、FUTEX_DEREGISTER 和 FUTEX_RECOVER。在 do_exit() 时, 搜索所有 vmas 以查看是否有一个 robust_head 集合。这种方法有两个基本问题: 

  • 在相当复杂的锁和竞争场景,基于 vma 方法仍然不完全可靠。
  • 他们在每个线程退出 时必须扫描 每个 vma !

第二个缺点是真正的杀手: 正常的 pthread_exit() 需要大约1微秒,但扫描成千上万的vmas后,每个 pthread_exit() 需要一毫秒或更多, 也完全破坏了 CPU 的 L1 和 L2 缓存!

即使对于正常进程,exit_group() 调用也是如此: 内核必须无条件地扫描 vma !(这是因为内核不知道有多少健壮的 futex 要清理,因为一个健壮的 futex 可能已经注册在另一个进程中, futex 变量可能只是简单映射到当前进程的地址空间)。

这一巨大的开销迫使 CONFIG_FUTEX_ROBUST 编译开关被创造,以便正常的内核可以关闭它,但比这更糟的是:这样的开销对于任何类型的通用 Linux 发行版来说, 健壮 futex 是不实用的。

因此,必须做一些事情。

健壮 futex 的新方法

新方法的核心是, 每个线程在用户空间有一个私有的健壮锁列表(由 glibc 维护) — 这个列表通过新的系统调用(set_robust_list)在内核中注册.每个线程生存期最多注册一次。在 do_exit()时, 内核检查这个列表: 是否存在健壮的futex锁要清理?

一般情况下的 do_exit() 时候,并没有注册健壮锁列表, 因此健壮 futex 代价只是一个简单的

current->robust_list != NULL

的比较。如果线程已注册健壮锁列表, 则通常情况下该列表是空的。如果线程/进程崩溃或以不正确的方式终止, 健壮锁列表可能非空:在这种情况下,内核小心遍历该列表(不能信任它), 将被该线程持有的所有锁的 FUTEX_OWNER_DIED 位置1,并唤醒一个等待线程(如果有的话)。

该列表保证在 do_exit() 时是每个线程私有的,因此内核可以无锁的方式快速访问它。

然而还有一种竞争可能:因为 glibc 添加和删除列表在 futex 被线程获取之后完成的, 这个过程存在几个指令的窗口期,线程(或进程)可能死在那里, 从而导致 futex 挂起 。

为了防止这种可能性, 用户空间 (glibc)为每个线程还维护一个简单的私有的list_op_pending字段,以允许内核在线程获得锁就死亡之后做清理, 但只在该线程可以将锁添加到列表之前。glibc 在线程尝试获取 futex 之前设置 list_op_pending 字段, 并在列表添加(或列表删除)完成后清除该字段。

这是所有需要的 — 健壮 futex 剩下的所有清理都已在用户空间完成。

Ulrich Drepper 在 glibc 里面已经实现了必要部分来支持这个新的机制, 使得健壮互斥体完全可行。

两种方法的主要区别:

  • 速度要快得多:在线程退出时,无需遍历每个 vma !只有一个非常简单的”列表是否为空”比较操作。
  • 不需要修改虚拟内存 — “struct address_space ” 单独保留。
  • 无需注册单个锁: 健壮互斥体不需要任何额外的针对每个锁系统调用. 健壮互斥体是一个非常轻量级基元 — 它们不强制开发人员在性能和健壮性之间做艰难的选择。
  • 没有针对每个锁的内核分配。
  • 不需要资源限制。
  • 不需要内核空间恢复 (futex(FUTEX_RECOVER))。

性能

我在 2GHZ CPU 上测试内核处理包含100万个持有锁的列表的所需时间:

  • 使用 FUTEX_WAIT (竞争的互斥体): 130 毫秒
  • 没有 FUTEX_WAIT (非竞争的互斥): 30 毫秒

我还测量了 glibc 执行锁通知的时间(通过 pshared 健壮互斥体) , 花了 256毫秒 — 明显较慢, 这是由于用户空间必须做 100 万次 futex(FUTEX_WAKE) 系统调用。
(同时持有100万锁的列表很少见 — 我们一般同时持有一些锁,因而新方法伸缩性很好。)

实现细节

添加两个新的系统调用, 一个用于注册用户空间列表,一个用于查询已注册的列表指针:

long set_robust_list(struct robust_list_head __user *head,
                     size_t len);
long get_robust_list(int pid, struct robust_list_head __user **head_ptr,
                     size_t __user *len_ptr);

列表注册非常快: 指针只是存储在

current->robust_list

里面。[请注意,在未来,如果健壮 futex 得到广泛应用, 我们可以扩展 clone 系统调用在创建新线程的时候就注册robust_list,无需另一个系统调用了。]

因此,对于不使用健壮 fute 的线程,开销几乎为零;即使对于用到健壮 futex 的线程来说也是快速和简单的,每个线程的生命期也只有一次额外的系统调用, 只有在发生了持有锁崩溃时候才做清理操作)。内核内部不用区分健壮的 futex 和一般的 futex。

如果在进程 exit 时内核发现 futex 还被持有,内核设置 futex 的以下位:
#define FUTEX_OWNER_DIED 0x40000000

并唤醒下一个 futex 等待线程(如果有的话)。用户空间做剩下的清理。否则, glibc 通过自动保存当前线程 id 到 futex 关联的内存地址来持有健壮 futex。等待线程设置 FUTEX_WAITERS 位:
#define FUTEX_WAITERS 0x80000000

发表评论

电子邮件地址不会被公开。 必填项已用*标注