Archive for 2012年1月

为什么 Mac OS X 先进 (续) ?

2012/01/19

几个月前写的《为什么 Mac OS X 先进?》有人认同也有人反感。想给它写个续篇缘于最近发生的两件事情。一件是为了买《 The Design and Implementation of the FreeBSD Operating System 》在 amazon.com 上闲逛(后来在 china-pub.com 上买到了影印版),惊喜地看到《 DTrace: Dynamic Tracing on Oracle Solaris, Mac OS X, and FreeBSD 》已经出版了。五年前在杭州西湖边的酒店首次听 Sun Microsystems 工程师介绍 DTrace,还只是 Solaris 上和我不太相关的东西。半年前得知 DTrace 已经被移植到 OS X 上,在 amazon.com 上看到这本书处于未出版的预定状态。今天终于能翻着这本书在 OS X 上把玩 DTrace,心情有些许激动。

另一件事是同事向我推荐 Blackhat 的 Dionysus Blazakis 的《 The Apple Sandbox 》。在《 Sandbox 初探 》中我提到过,Sandbox 是在 DAC 和 MAC 两种安全模型都不适合个人计算的情况下另辟的第三条路。读了 Blazakis 的 paper 发现 Apple 没我描绘的那么特立独行 [注]。OS X 自 Leopard 起就已经集成了通用 MAC 架构 TrustedBSD,只是一直未有具体策略施加其上(TrustedBSD 只是执行 MAC 策略的机制而不是策略本身)。Lion 中新出现的 Sandbox 是在该架构上编写的 policy module。如《 Sandbox 初探 》所述,Apple 的创新在于和 UI framework 集成的动态安全策略。在执行安全策略的底层架构上,Apple 并不是自己发明车轮,而是直接采用了 BSD 社区的方案。另一方面,如 Blazakis 所说,Sandbox 也为 TrustedBSD 增加了高价值的功能,没有这类 closed 系统的无缝封装,无法想像 TrustedBSD 能在普通大众的计算机上发挥作用。

这两件事情让我回忆起前段时间看到的关于「开放模式」的讨论。Mac OS X 常被称为 closed 系统,相对而言有人甚至称 Windows 为 open 系统。Closed 略带贬义,因为有人盲目崇信 open 必胜。Steve Jobs 和 Bill Gates 都更愿意用含蓄一些的词,前者称 Mac 为 integrated 系统,后者称 Windows 为 compatible 系统。我认为做比较还是该用 open/closed 这样的直白词汇,但是要在各个层次分别描述:

  • Closed open-core 系统:Mac OS X
  • Open closed-core 系统:Windows
  • Open 系统:Linux,BSD

这些年 Mac 似乎远比 Windows 成功。Linux 和 BSD 这类 open 系统的成功领域是嵌入式设备、移动系统、服务器和超级计算等定制硬件系统,从软硬件的整体角度来说也构成 closed open-core 系统。看来 close open-core 是这阵子的黄金模式。传记《 Steve Jobs 》反复表达 closed 系统在提供优秀用户体验方面的 open 系统不可比拟的优势。但是人们经常忽视 Apple 产品在 open-core 方面的优势。

上面两个实例充分体现了 open-core 模式的优势。Jobs 公布 OS X 的第一个预览版时强调它是 Unix 并非吸引观众的权宜之计,目前为止七个版本的发展中,OS X 和Unix-like 系统社区一直保持密切的交流(还没有提这些年 Apple 向 Unix-like 反哺的代码,比如 Grand Central Dispatch)。这几年 Mac 上很多创新都来自公共领域经过考验的杰作。Closed-core 的 Windows 尽管能用于更广范围的廉价硬件(以牺牲用户体验为代价),但是集成这些创新明显力不从心。一是和 Unix-like 不兼容的内核必然导致移植成本增加,二是长久隔离于 Unix 圈之外的开发团队对公共领域的创新缺乏敏感,以至于只有 Apple 等其它厂商早有所行动之后才能缓慢跟进。

关于底层和上层的 open/close 模式问题,曾经在《 Open Source 的界限 》中从 open source 项目角度讨论过。Open-core 无疑是总结这个模式的好名字。Open source 的界限,就是 open 的界限,也是 open 的生命力所在。

注:虽然《 Sandbox 初探 》在 Sandbox 和 MAC 之间的关系上不太准确,但是这不妨碍它是 Blazakis 的 paper 的有益补充。后者虽然有无可比拟的 reverse engineering 实证作为基础,却没有涵盖 Sandbox 最重要部分 —— 和 UI 集成的通过 Powerbox 动态扩展 sandbox 范围的机制。关于这部分机制我认为《 Sandbox 初探 》的解释是正确的。

近期功课

2012/01/18

最近逛书店(Amazon.com,China-pub.com 还有西单图书大厦)收获不少。想买的和没想到要买的都有了:

  • 《罗马帝国衰亡史》,商务印书馆的经典版式。适合完全没有网络和电脑的时候看。不过有些功课还得通过 Wikipedia 补上。
  • 《The Design and Implementation of the FreeBSD Operating System》,想看看 kernel 的东西,不过没有当年 dig Linux kernel source 那股劲头了。浮光掠影的看看这个 OS X 的近亲吧。
  • 《DTrace: Dynamic Tracing in Oracle Solaris, Mac OS X, and FreeBSD》,对工作最有用的一本。有网络和地方摆电脑的时候认真看。
  • 重读经典的《人月神话》还差五章,没有照到这张里。

解剖 Mutex

2012/01/05

新年前读到 Varnish 开发者 Poul-Henning 的一篇 blog《 The Tools We Work With 》,谈到他对 POSIX thread mutex 做了简单封装来实现「assert if I’m holding this mutex locked」功能。(这里说明一下,Poul-Henning 和本文所指的 mutex 是构建 critical region 而且能够切换线程的 running-wait 状态的锁。在有的 framework 里这种机制有其它名称,如 Cocoa 的 NSLock。本文称进入和离开 critical region 的操作称为 lock/unlock mutex,处于 critical region 中的状态为 holding mutex。)

我对 Poul-Henning 的说法既感兴趣又怀疑,对数据进行多线程并发访问是非常容易出问题的。以前曾经有个著名的只在 rare-path 加锁的 double-checked lock 的错误例子。Varnish 的 assertion 对 mutex 本身相关的(而非它所保护的)数据进行多线程访问。这需要它的 mutex 封装里再提供某种同步机制。Varnish 有没有正确提供这种保护?或者是否会造成性能问题乃至于死锁?为了搞清这些疑问,我下载了一份 Varnish 代码。其中的 lock/unlock/assert 代码基本如下 [1]:

实际代码证实了我的担忧。Lck__Assert() 对 owner 和 held 的访问并无保护。修正这个错误要在 sturct ilck 里定义另一个 mutex(意味着整个系统的 mutex 数目加倍),或者使用一个新的全局 mutex(意味着整个系统的 mutex 竞争急剧增加)。如果仅仅是一个 debug assertion 的需要倒也不是大问题。可是仔细想想,实现 reentrant mutex 也需要类似的功能。因此肯定应该有更好的方法。最后我在 Stackoverflow.com 上得到了一个方案,修改 unlock 方法如下:

我给 Poul-Henning 发信说明这个问题,他同意了我的分析和补救 [2],同时指出了一个我没有意识到的问题。一开始我错以为 owner 是个整数 ID,给出的方案是在 Lck__Unlock() 中将其设置为某个非法值(比如 0 或者 -1)。Poul-Henning 指出 thread_t 是平台相关的不透明类型,没有非法值的定义,他提出用 memset() 清零来作为目前的方案,尽管仍然有下面的缺陷:

  • 全 0 的 thread_t 可能在某些平台上是合法的线程 ID。
  • 尽管在没有 hold mutex 的情况下 owner 几乎不可能等于当前线程 ID,但是由于没有保护,Lck__Assert() 中读取的 thread_t 有可能是一个被其它线程部分修改的受损数据 (corrupted data) 。在某些平台上也许 pthread_equal() 不能安全的处理这种 ID。
  • 不能完全排除在某些罕见情况下一个部分受损的 owner 变量的值恰好等于当前线程 ID。

给 mutex 提供额外的功能并不是简单的任务,给 POSIX thread mutex 这样的跨平台机制扩展功能就更难了。我觉定深入研究一下 mutex,以及在多大程度上能对它们进行跨平台的扩展。

纯软件实现

每个学习多线程编程的人一开始就要接触 critical region 的概念 —— 保证至多一个线程进入的代码区域。经典操作系统教材《 Operating System: Design and Implementation, 2nd Edition 》 [3] 中给出了一个叫做 Peterson 方法的纯软件 critical region 实现(为了描述简单,给出的例子只支持两个线程的情况)[4]:

Peterson 方法解释了线程抢占问题,但它只是一个假定各线程严格顺序执行的教学例子,在今天的计算机上是不能正常工作的,因为编译器和 CPU 采取下列措施优化程序的性能:

  • 编译器生成的优化代码和源代码并非按顺序对应。
  • CPU 在运行过程中以提升性能为目的打乱指令的执行顺序。
  • CPU 在运行过程中通过流水线对同一指令序列的不同部分并行执行。
  • 每个 CPU 有自己的局部 cache,没有固定机制保证局部 cache 和主内存同步的顺序和时延。

当然编译器和 CPU 进行这些优化乱序的时候不能任意而为。为了在最大程度上延续这些技术出现之前的编程方式,这些优化机制保证在「单一线程内」的运行结果仍然和顺序执行等效。「顺序等效」确保在 Lck__Unlock() 中对 owner 清零可以让 assertion 正确工作,因为只有当 Lck__Assert() 和 lock 处于同一线程内,并且处于 critical region 内,owner 才等于当前线程 ID。

由于不改变编程方式,无需程序员介入,这种「等效保证」和 CPU 频率的提升一起被视为前多核时代的性能「免费午餐」。但是「顺序等效」不能扩展到多线程,如果没有显式求助硬件的保证:

  • 一个线程的执行在其它线程看来并非严格顺序执行。
  • 一个线程对内存的改动不能立即对其它线程可见。
  • 一个线程对内存的改动对其它线程的可见顺序不一定和改动顺序一致。

在上面的 Peterson 方法代码中,两个线程在第 12 行可能同时看到 while 的判定条件为 FALSE,因为变量 turninterested 可能分别在各 CPU 的局部 cache 中有未经同步的拷贝。在「唯一线程进入」的基础上,今天操作系统的 critical region 要提供更多功能,它要保证:

  • 最多只有一个线程能进入 critical region;
  • 编译器不进行跨越 critical region 边界的乱序优化;
  • CPU 不进行跨越 critical region 边界的乱序执行;
  • 所有 CPU 的局部 cache 在 critical region 的边界和主内存同步。

简单 Mutex

为了保证 CPU 和主内存之间的同步,硬件提供了一套 inter-processor communication 机制。这些机制是为了像 kernel 这样的高性能底层代码设计的,和 critical region 的基本概念有一定距离。比如 read/write barrier 只是保证了同步的时序,不保证时延。最接近 critical region 的机制是「总线锁」[5],它保证了上面列出的 critical region 四条要求的后三条。但总线锁的持续时间只是某些特定的单条指令 [6],不能构建真正的 critical region。操作系统在它的基础上实现了一套 lock/unlock mutex 的操作。Mutex 的数据结构是一个 CPU 总线锁支持原子化修改的整数类型和一个线程等待队列。Lock 操作如下(或者等效):

  1. 执行一个原子操作,对整数减一并返回结果。
  2. 如果结果为 -1,说明 critical region 内没有其它线程,继续执行进入 critical region。
  3. 如果结果小于 -1,将当前线程放入等待队列。

Unlock 操作如下:

  1. 执行一个原子操作,对整数加一并返回结果。
  2. 如果结果为 0,说明没有其它线程被阻塞。
  3. 如果结果小于 0,将等待队列中的一个线程执行放入 kernel scheduler 的 ready 队列(唤醒该线程)。

这种简单的 mutex 不是大多数应用程序使用的 rentrant mutex,和后者有如下区别,

  • 同一线程试图两次 lock 一个简单 mutex 会导致死锁。而 reentrant mutex 可以被同一线程 lock 多次。
  • 在同一线程中对 reentrant mutex 的线程必须成对出现。而简单 mutex 没有这个限制。
  • 由于第二点,处于一个 reentrant mutex 的 critical region 中的线程称为这个 mutex 的 owner。而简单 mutex 没有 owner。

简单 mutex 在 Linux 和 BSD 的 kernel 代码中叫做 semaphore。Reentrant mutex 在简单 mutex 的基础之上实现。

正是由于 reentrant mutex 的 lock 和 unlock 操作必须在同一线程中成对出现,Varnish 的 Lck__Assert() 才能(在加入我的修改之后)利用单线程的「顺序等效」保证 owner 的状态能正确反映 holding mutex 的状态。这里我们会发现 Varnish 的 assertion 有一个基本语义的问题,它使用了 owner 的概念,要求 lock/unlock 在同一线程成对出现,这表明它针对的是 reentrant mutex。但是在它的 lock/unlock 操作中没有处理 holding mutex 的嵌套层数。这是 Varnish 的另一个错误,它没有显现出来也许是因为在 Varnish 中 reentrant mutex 并不实际发生嵌套 lock。或者也可以说一个有 owner 的 mutex 只是要求 lock/unlock 处于同一线程,并不一定非要支持 reentrant,但我认为这样复杂化 mutex 的分类并无必要。最好还是把 owner 和 reentrant 等同起来概念比较明晰。好在明确这个问题之后不影响其它讨论。对嵌套层次的支持也可以很容易地加入到 Varnish 的 assertion 中。

Reentrant Mutex

到目前为止,我们有了一个利用「等效原理」基本可以工作的「assert if I’m holding this (reentrant) mutex locked」机制,也回顾了简单 mutex 的原理。理论上可以利用二者来实现 reentrant mutex。还有这么几个问题没有得到确定的回答:

  • 类型 thread_t 是一个复杂的结构还是一个简单类型(整数/指针)?
  • POSIX 库能否保证目前 Varnish 的 assertion 正常工作?
  • 如果 thread_t 是一个复杂类型的话,POSIX 库很可能需要一个 directory 来维护这个复杂类型和内核的 thread ID 之间的联系。那么该 directory 也需要某些同步机制来保护(比如 kernel semaphore)。那就意味着 pthread_self() 这样的方法也有相当可观的性能开销,在这种情况下利用「等效原理」避免 mutex 的性能提升是否有意义?
  • POSIX thread 库是否真的利用「顺序等效」实现 reentrant mutex?
  • 如果不是,POSIX thread 的实现方式和「等效原则」相比性能如何?

由于 POSIX 是跨平台标准,所以这些问题不可能得到完全解答。最后的答案只限于 OS X [7](很大程度上适用于所有 BSD 系统)。

在 OS X 上 thread_t 是一个指针。pthread_self() 从 GS 寄存器返回该指针。GS 是 kernel 维护 per-thread 数据的寄存器。Per-thread 数据在各自线程内遵循「顺序等效」,无需同步机制。这解决了前三个问题 —— Varnish 的 assertion 可以在 OS X 上正常工作, pthread_equal() 也不会有性能损耗。更进一步说,利用通用的 per-thread 数据机制可以更有效的利用「顺序等效」原理。比如可以维护当前线程 hold 的所有 mutex。POSIX 提供 per-thread 数据的通用接口,如 pthread_key_create()。 相比之下,目前 Varnish 利用「顺序等效」原理只是一种 ad-hoc 的方式。

接下来,POSIX thread 库利用 thread_t 的成员来实现 reentrant mutex 功能。在 OS X 的 pthread_mutex_unlock() 并没有类似 Lck__Assertion() 对 owner 清零的操作,只有类似将 held 设置为 FALSE 的操作。它并没有采用 ad-hoc 的「顺序等效」来实现「assert if I’m holding this mutex locked」,也没有采用 per-thread 数据。在 POSIX thread mutex 里,除了用来创建 critical region 的底层 semaphore 之外,还有一个专门保护 thread_t 成员的「锁」。这个锁不是 mutex 而是 spinlock。Spinlock 的语义类似简单 (non-reentrant) mutex (semaphore),不同之处在于线程竞争时后入线程不会被放入等待队列,而是进入空循环,所以在 critical region 很短的时候性能开销没有 mutex 那么大。

从 OS X 的实现来看,对性能开销的顾虑并没有我一开始担心的那么大。比较之下,我提出的修正 Varnish assertion 的方式太 ad-hoc,完全可以采用更可靠的 spinlock 或者 per-thread 数据。

脚注:

  1. 为了叙述清楚我删除和修改了一些无关代码。
  2. 我提议的修改 2011 年 12 月 28 日进入 Varnish 的 code base。
  3. 62 页图 2-9。这是我在大学买的第一本英文影印版书。Linus 编写 Linux kernel 之前通读了此书第一版。
  4. 由于采用空循环的 busy wait 而非线程的挂起,这个机制不是 mutex。
  5. 《Intel® 64 and IA-32 Architectures Developer’s Manual: Vol. 3A》,第 8.1.2.2 节:Software Controlled Bus Locking。
  6. 同上。
  7. Apple 的 open source 页面