两道面试题与我的一点面经

由于工作的关系,在加入现在的公司后,作为技术人员参加了大大小小的一些面试,包括最近几次,与以往不同的是,以前参加面试是找工作,是被面试者,现在则变成了面试别人的角色,以考察技术为主。

组里招聘的职位是 Linux 下的开发,所以 HR 推来的应聘者大都对 Linux 很有兴趣,至少也有 Linux 的相关经验。在这些面试交流中,总体感觉 Linux 比起几年前来更流行了,也许使用 Linux 进行日常操作的人并不多,但至少在 Linux 下进行开发的人群基数应该算相当大了。

说到 Linux 开发,这个概念太宽泛了,不同的项目需求所需要的系统架构,实现技术往往千差万别。能够找到一个匹配项目需求的开发人员当然最好了,但这往往可遇不可求。退而求其次,是找到一个具有扎实 基础的开发人员。对 Linux 开发来说,这样的基础在我看来有至少有两个方面,一是 C 语言的基础,Linux 下的大部分开源软件都是用 C 写的,扎实的 C 语言基础可以帮助开发人员在解决问题时(尤其是找不到书面文档时),通过阅读源代码来定位问题。而且即使项目开发不用 C 语言,扎实的 C 语言基础也能帮助开发人员迅速上手新的语言;二是 Linux 下的基本命令以及 Shell 的基础,Shell 可以看作是了解一个 Linux 系统的入口,虽然在今天 Python, Perl 等脚本语言更流行,但熟练掌握 Shell 仍是不可或缺的。

现在来卖弄一下其中的两道面试题,我认为这两道题比较能够反映上面提到的两个基础。这两道题的类型并不鲜见,从网上搜也能搜一大把,不过在面试的诸多同学中,完全答对的也不多,也许是公司庙太小,吸引不到佛吧。第一道是关于 C 语言指针的,第二道是关于在 Shell 下执行命令的。思考一下,然后在命令行上检查你是否完全理解了这两道题的意思。

1. 假设在 32 位机上,有如下的两条语句定义了两个变量:

char *s = "hello";
char a[] = "hello";

a. sizeof(s) 与 sizeof(a) 分别是多少?

b. 根据上面的定义,如下两条语句是否有问题,如果有问题,在什么时候发生?

*s++ = 'H';
*a++ = 'H';

2. 在 Bash 下,运行下面命令的结果以及输出分别是什么?这里假设 # 为命令行提示符,当前目录是 /home/test。

a. # pwd
b. # $(pwd)
c. # echo pwd
d. # echo $(pwd)
e. # pwd | echo
f. # $(pwd) | echo

最后,想要说的一点是应聘一个工作成功与否大多数情况下与答题的正确程度无关,扎实的技术基础也就是让你在面试时更加自信而已,当然最终受益的还是你自己。

文件传输 [xkcd]

互联网在经过 20 多年的发展后,一个仍然让人苦恼的问题是如何在两个普通用户之间传输大文件,xkcd 的一副漫画对此做了很好的讽刺,也许某些时候,用信鸽叼 U 盘的方式是最快的。

File Transfer by xkcd

PS:说点与本文无关的,建立这个博客有大半年的时间了,期间获得了不少朋友的关注,自己也学到了不少东西,与我而言,写博客是一件愉快的体验,把自己学到的东西拿出来与大家分享的过程,也是自己重新理解一遍的过程。不过写博客又很累,更重要的是耗费精力,弄得自己很少有时间学习新的知识。所以一直在找一个歇一歇的理由,这也是最近更新越来越慢的原因。

建立博客的时候,因为嫌备案麻烦,我把它放在了国外(GoDaddy),了解到 GFW 的操蛋性,我购买了独立的 IP,不过这仍然无法阻止博客在本周彻底无法访问的杯具,相信这与本博客无关,应该是 GFW 把 GoDaddy 的地址段全封了。这倒是为自己找到了一个借口,可以歇一歇了。

当然这不是再见,本博客仍然会更新,您仍然可以通过 Google reader 阅读全文 feed,只是您不必再有所期待了。

[译文] 编写 C 库:Part 1(上)

[译者前言] 本文译自 David Zeuthen 编写的 Writing a C library 系列文章,原文载于作者在 blogspot 上的博客。该系列文章的版权属于原文作者所有,本文是该系列文章的第一篇的上半部分:Writing a C library: Part 1

基础库

libc 是处于相当底层的一套库,因此存在一些高层的库使得使用 C 语言进行编程可以获得更愉快的体验,这包括 GLib 以及 GTK+ 里的一些库。即使下面的阐述多少有些围绕着 GLib 以及 GTK+ 进行,这些阐述对任何 C 代码来说都是有用的,不管代码是基于 libc,GLib 还是其它的库如 NSPRAPRSamba 的一些库

大多数程序员都会同意的一点是实现那些基本的数据类型(比如字符串处理,内存分配,链表,数组,哈希表,队列)并不是一个好的想法,特别是仅仅因为你能够实现,因为这只会让别人理解以及维护你的代码更加困难。这些地方正是C 库如 GLib 与 GTK+ 发挥作用的地方,它们提供了大部分这样的功能。此外,当你最终需要那些并不简单的功能时(相当可能的情况是你会),如操作 Unicode解释复杂的脚本D-Bus 支持,或计算校验和,问问自己(更糟的情况:当你的经理或同伴问起你时)回避使用一个有着良好测试良好维护的库是否是一个好的决定。

特别地,对于类似密码算法这样的功能,选择自己实现通常是一个糟糕的想法(更糟的是自己发明一个新的算法);相反,更好的选择应该是使用那些已知的经过良好测试的库,比如 NSS(如果你这样做了,要注意正确地使用它)。需要提及的是,该库还经过了 FIPS-140 的认证,如果你想跟美国联邦政府做生意的话,这是一个必要的需求。

类似地,对于事件通知来说,虽然使用 epollpoll 效率要高,但如果你的应用程序需要处理的文件描述符只在 10 个这样的数量级上,使用哪个并不重要。另一方面,如果你知道你需要处理上千个文件描述符,只需要在专门的线程里使用 epoll,你仍然可以在你的库或应用里大量使用如 GLib 等库。同理,如果你需要从链表里删除的节点数量级为 O(1),那么也许你应该用嵌入式链表,而不是 GList

最重要的是,不管你最终使用了什么库或代码,至少要确保自己对所用库的相关数据类型,概念,以及实现细节有一个基本的理解。举例来说,GLib 里面的一些高层构造如 GHashTableg_timeout_add()g_file_set_contents() 都非常易用而不需要知道它们是怎么实现的或理解文件描述符是什么。比如,当存储数据时,你希望这个操作是个原子操作(避免数据丢失),并且知道 g_file_set_contents() 可以实现这个操作通常就足够了(通常阅读 API 文档会告诉你那些你需要知道的内容)。此外,确保你能理解你最终使用的数据类型的算法复杂度,以及他们在现代硬件上是怎么工作的

最后,不要在网上与那些不相干的人较真讨论关于膨胀(bloated)的库,通常这是对时间与资源的浪费。

备忘清单

  • 不要重新发明那些基本的数据类型(除非性能是主要的考虑)。
  • 不要回避那些标准的库,仅仅因为它们是可移植的。
  • 使用多个库并且功能有重叠时要警惕。
  • 在一定程度上可能的话,将库的使用作为一个私有的实现细节。
  • 为正确的工作选择正确的工具 – 不要把时间浪费在无用的讨论上。

库的初始化与关闭

有些库会要求在调用其它库函数前,调用某个特殊的库函数完成一些初始化工作,通常这个函数叫做 foo_init(),它一般用来初始化该库用到的全局变量以及数据结构。此外,有些库还会提供一个关闭函数,典型的名字是 foo_shutdown()(其它名字如 foo_cleanup(),foo_fini(),foo_exit(),甚至 foo_deinit() 也有使用的),该函数一般用来释放库用到的所有资源。提供一个 shutdown() 函数的主要理由是可以让 Valgrind(用来发现内存泄漏)更好用,或者当使用了 dlopen() 系列函数时用以释放资源。

通常,应该避免库的初始化函数与关闭函数,因为它们有可能导致应用程序依赖链上的两个不相关的库的冲突;也就是说,如果你不在使用它们的地方调用它们,你将强制应用程序在 main() 函数里调用一个 init() 函数,仅仅因为某些深藏在依赖链里的库使用了该库而没有初始化它。

然而,如果一个库不提供初始化函数的话,这个库里的每个库函数都将不得不调用一个内部的初始化函数来完成必要的初始化,这并不总是可行的,并且有可能成为性能上的负担。实际中,这个初始化检测只需要在某些函数中执行,因为一个库里的大部分函数依赖于从该库其它库函数获取的某个对象或结构进行操作。所以实际上,检测只需要在那些 _new() 函数里或不操作任何对象的函数里执行。

例如,使用 GLib 的类型系统的程序都需要调用 g_type_init() 函数,这包括那些基于 libgobject-2.0 的库如 libpolkit-gobject-1,也就是说,如果你不在调用 polkit_authority_get_sync() 之前调用 g_type_init(),那么你的程序很有可能会 segfault。自然地,这是大部分使用 GLib 的新人都会出错的地方,并且你真的不能责怪他们。如果有的话,g_type_init() 可以说是为什么应该尽可能避免 init() 函数的典型代表。

库的初始化函数需要存在的一个可能的理由是库的配置,要么是应用程序需要的特殊配置(应用程序也许希望使用库的某个特殊行为),要么是终端用户需要的配置(通过操作 argv 与 argc),一个可供查看的例子是 gtk_init()。对于这个问题最好的解决方法是避免配置,但如果实在不太可行的话,使用环境变量来控制库的行为会更好一些。作为例子,可以查看 libgtk-3.0 支持的环境变量libgio-2.0 支持的环境变量

如果你的库提供了初始化函数,确保该函数是幂等的(idempotent),并且线程安全,也就是说,该函数可以同时从多个线程里被调用多次。如果你的库也提供了关闭函数,确保你的库使用了某种方式的“初始化计数(initialization count)”,从而保证当该库的所有用户都调用完它的 shutdown() 函数后,该库只关闭一次。同样,如果可能的话,确保你的库的 init/shutdown 函数也调用了它所依赖的库的 init/shutdown 函数。

通常,一个库的 init() 与 shutdown() 可以通过引入上下文对象(context object)来移除掉 – 这可同时解决诸如全局状态(令人讨厌并且有可能破坏同一进程里的多个库的用户),锁(将可以基于上下文实例),以及回调/通知(可以回调并且将事件推到分离的线程里)等方面的问题。作为例子,可以参见 libudevstruct udev_monitor

备忘清单

  • 避免 init()/shutdown() 函数 – 如果无法避免它们,确保它们是幂等的,线程安全的,以及引用计数的。
  • 使用环境变量来传递库的初始化参数,而不是 argc 与 argv。
  • 你很容易会在同一个进程里遇到两个不相关的库的用户 – 通常在主应用程序不知道的情况下。确保你的库能处理这种情况。
  • 避免不安全的 API 如 atexit(3),以及当需要考虑移植性时,避免不可移植的构造方式如库的构造符与析构符(例如,gcc 的 __attribute__(constructor) 与 __attribute__(destructor))。

LinuxCon 2011 的趣事

今年是 Linux 诞生的 20 周年,Linux Foundation 为此举办了很多活动来庆祝,其中最正点的是上上周(Aug 17 – Aug 19)在温哥华举办的 LinuxCon 2011。包括 Linus Torvalds 先生在内的多位业界大佬都参加了这一盛会,大佬们指点江山、激扬文字,感怀过去、展望未来,为我们留下了一届团结的大会,胜利的大会。本人仔细研读了与会人员的一些纪要,于细微之处精心揣摩,从而整理出本届大会一些重要的精神供各位同学传阅。

Linux – Then and Now

Linux Foundation 在这次大会召开之前,对注册与会人员做了一个小调查,主要是针对用户过去与现在的 Linux 使用习惯,调查结果制成了一张图表在大会召开之时公布。其中最令人感兴趣的一项是当前使用的发行版,Ubuntu 与 Fedora 不出所料的排在了前两位,出人意料的是排在第三的 Arch,随后是 Debian, openSUSE, Mint。这个结果与 DistroWatch 的排名并不完全一致(Mint 在 DistroWatch 上的排名高高在上),也许是因为参加 LinuxCon 的多是开发人员或资深 Linux 用户(或许普通用户更喜欢 Mint?)。曾经有传言称 Linus 在抛弃 Gnome 3 转投 Xfce 后,也顺便切换到了 Mint,不过后来证实这是以讹传讹,至少 Mint 还需要更多时间来扩大自己的影响力。

Linux - Then and Now

正主 Linus Torvalds 的问答

各种各样的技术讲座,主题演讲是一届成功的大会所不可缺少的,比如 Linux Foundation 的 CEO Jim Zemlin,Red Hat 的 CEO Jim Whitehurst 等人的演讲。不过,一个庆祝 Linux 的盛会如果缺少了 Linus Torvalds 先生显然是不完整的,在 Greg K.H 的主持下,Linus 非正式的回答了观众提出的几个问题。

Linus and Greg K.H

【ARM 平台看起来已没那么糟糕】

ARM 平台的支持一直是最近一段时间 Linus 最不满意的地方,ARM 平台的前途不言而喻,但是在 Linus 眼里,ARM 平台就是一个大杂烩,各个硬件厂商始终没有一个标准平台的意识,导致内核人员在支持 ARM 架构上痛苦不堪。不过从最近两个内核版本来看,情况似乎已没那么糟糕。Ubuntu 最近宣布了从下个版本开始对 ARM 架构的服务器版本支持,似乎也在助力 ARM 平台。

【Android and fork】

ZDNet 的 SJVN 问到了 Android 的开发,显然,Android 的内核分支现在是游离于 Kernel 之外的最大一支了,什么时候 Android 的修改能并入官方 Kernel 一直是平台开发人员所关心的问题。Linus 表示短时间内似乎很难有变化,不过最终 Android 的内核会稳定下来,也许需要4到5年。喜欢 fork 的 Linus 并不担心 Android 的这种分支会给 Kernel 带来不好的影响,天下大势,分久必合,合久必分吗。

【虚拟化是魔鬼】

KVM 与 Xen 的比较问题也被提了出来,Linus 则直接的表示,他不是喜欢虚拟化的人,虽然 Kernel 开发人员通常都更喜欢 KVM,但 Linus 并没有厚此薄彼,他表示自己更喜欢直接面对硬件,而 Virtualization is evil。除了 Linus 以外,虚拟化仍然是热炒的焦点之一,Red Hat 在 LinuxCon 2011 上就发布了 RHEV 3.0,Eucalyptus 的 CEO Marten Mickos 也不同意 Linus 的看法。

【Linus 的第二职业】

当有人问道 Linus 会否一直干下去这个老生常谈的问题时,Linus 表示他正在建立自己的第二份职业,喜欢潜水的他即将获得潜水的一个高级认证。当然,这份工作并不像 Kernel 维护那样来钱快,所以除非他的子女都已经念上大学,并且他也不想睡在大桥底下,他还会一直干下去(长时间的鼓掌!)。

IBM 的勇敢尝试

作为最早投向 Linux 阵营的大厂家,来自 IBM 的 Dr. Irving Wladawsky-Berger 讲述了当初 IBM 与 Linux 的故事。现在看来,IBM 在 Linux 上的早期投入与转型是多么的有先见之明,但当初的道路并非那么容易。Wladawsky-Berger 特别感到抱歉的是当年他刚刚任命了某个人来领导 Linux 业务,那个人就碰上了 SCO 的诉讼,好在 IBM 笑到了最后。Wladawsky-Berger 甚至不怀好意的希望在下次举办 LinuxCon 时,能够将当初 SCO 聘请的金牌律师与 Eben Moglen(FSF 的公益律师)一块请来,做个演讲。

Wladawsky-Berger 也提到了 Linux 被称作共产主义阴谋(communist consipiracy)的时候,他觉得非常可笑,因为之前 IBM 通常被称作资本主义的猪(capitalist pigs),而真正的共产主义国家,这个世界上只剩下两个(朝鲜与古巴,他没有提到我的祖国),他们看起来不像是能够发起一个雄伟计划从而统治世界的国家。

当然,IBM 真正值得共享的经验在于,他们并没有把 Linux 看作是又一个操作系统,就像当初 IBM 没有将 Internet 简单的视作是又一个网络一样,Internet 显然并不只是 TCP/IP,而 Linux 也不只是一个高效的内核,IBM 对 Linux 的拥抱是他们将 Linux 看作是未来创新的平台,就像 Internet 一样。

悲催的 HP

当 HP 的 开源技术执行官 Phil Robb 在 LinuxCon 上演讲 HP 的 webOS 时,他打死也不会料到在他的演讲结束后不久,HP 就宣布了 webOS 的死刑。就像当初 Nokia 抛弃 MeeGo 一样,HP 在花了巨量的资金收购 Palm,并正式推出基于 webOS 的 TouchPad 后就这样抛弃了 webOS。

Robb 讲述了 webOS 与 Linux 的关系,webOS 是怎样基于 Linux,并且还包含了一些 GPLv3 程序。HP 向 WebKit,Node.js 贡献了自己的代码,而这在当时的 Palm 是没有的。Robb 也表示 HP 会随着 webOS 的成长进一步加强与内核开发人员的合作,而这一切将随着 HP 抛弃 webOS 的声明随风而去,曾经 webOS 与 MeeGo 都被看作是比 Android 更开放的 Linux 移动平台,现在世界大战将只剩下 Android vs Apple,你说这有多无趣啊。

引用与致谢

linux.com 的相关报道:

internetnews.com 的相关报道:

密码的强度 [xkcd]

xkcd 的一副漫画对当前的密码选择策略做了一个很好的讽刺。

password_strength

经过 20 年的努力,我们终于成功的训练的每个人都学会使用,人类难以记住,电脑却容易破解的密码。

不知道组成密码强度 entropy 的各个单元值是怎么得来的,显然如果这个分析属实的话,那将解放多少为了记密码而备受困扰的人们啊。希望所有开发密码安全系统的人(或系统安全管理员)都看看这副漫画,然后将那些愚蠢的密码限制去掉(最大密码长度,必须包含数字、大写字母、特殊符号)。

[译文] 使用 PyPy 编写解释器:Part 2

[译者前言]:本系列译文译自 PyPy Status Blog 刊登的 Writing an Interpreter with PyPy 系列文章,原文作者为 Andrew Brown,该系列文章的版权属于原文作者所有,在此向 Andrew Brown 以及 PyPy Status Blog 表示致谢。本文译自该系列的第二篇:Writing an Interpreter with PyPy, Part 2: Adding a JIT.

添加 JIT

将 RPython 翻译成 C 当然相当酷,不过 PyPy 还有一个非常棒的功能,即为你的解释器生成 JIT 编译器。没错,通过一些关于你的解释器构成的提示,PyPy 能够生成并包含一个 JIT 编译器,这个 JIT 编译器在运行时,能够将我们的 BF 语言的解释代码翻译成机器指令。

那我们该做些什么让 PyPy 去生成 JIT 编译器呢?首先,它需要知道你的字节码的 evaluation loop 在哪里,它可以据此跟踪正在执行的目标语言(BF)指令。

我们还需要让它知道是什么定义了一个特定的 execution frame。因为我们的语言并没有真正的 stack frame,这可以归结为对于一个特定指令的执行,哪些是常量,而哪些不是。它们分别被称作 “green” 变量以及 “red” 变量。[译注 1]

下面的内容请参考我们的 example2.py 例子。

在我们的主循环里,共使用了 4 个变量:pc, program, bracket_map, tape。当然,pc, program 以及 bracket_map 是 green 变量,它们定义了特定指令的执行。如果 JIT 发现与之前相同的 green 变量组合,它知道自己跳回到了之前的指令,因此一定是在执行一个循环。变量 tape 是我们的 red 变量,它正是我们的指令所操作的数据。

让我们告诉 PyPy 这些信息。导入 JitDriver,并生成一个它的实例:

from pypy.rlib.jit import JitDriver
jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'], reds=['tape'])

然后在 mainloop 函数的 while 循环的最开头添加如下一行:

jitdriver.jit_merge_point(pc=pc, tape=tape, program=program, bracket_map=bracket_map)

我们还需要定义一个 JitPolicy。看,这就是所有我们需要做的,并不需要什么花哨的东西:

def jitpolicy(driver):
    from pypy.jit.codewriter.policy import JitPolicy
    return JitPolicy()

具体内容参见 example3.py

现在再次生成我们的解释器,不过要加上标志 –opt=jit:[译注 2]

$ python ./pypy/pypy/translator/goal/translate.py --opt=jit example3.py

当打开 JIT 后,翻译过程明显变长,在我的机器上大约需要 8 分钟,并且生成的二进制程序也相当大。现在试着再次运行 mandel.b 程序,你会发现差别很大,这次运行只需要 12 秒,而之前为 45 秒!

非常有趣是吧,通过 mandel.b 例子,你可以看到我们的 JIT 编译器在什么时候从解释代码切换到了机器代码。输出的头几行打印的还算快,不过之后,程序就跟飞起来了一样,打印速度也越来越快。

关于 tracing JIT compiler 的一点

现在是时候去了解一下 tracing JIT compiler 是如何工作的了。这里是一个简要的描述:解释器通常运行的是你所写的解释器代码,当它检测到目标语言(BF)的某个循环代码经常执行,那么这个循环将被认为 “hot”,并且被标记下来做跟踪。当下一次进入该循环时,解释器将进入跟踪模式(tracing mode),每一条执行的指令都会被记录下来。

当循环结束,跟踪也就停止了。对循环的跟踪记录将被送到一个优化器(optimizer),然后是汇编器(assembler),最终生成机器代码。这些机器代码将在随后的循环调用时被执行。

基于对解释器代码的某些假定(assumption),生成的机器代码通常会针对大多数情况进行优化。因此这些机器代码都会包含一些保护(guard),用来验证这些假定。如果某个保护检测失败,那么在运行时解释器将回退到普通的解释代码。

可以从这里了解更多关于 JIT 编译器的详细信息。

调试与跟踪日志

我们还能再做的更好一点吗?怎么才能看到 JIT 在做什么?让我们做两件事情。

首先,让我们添加一个 get_printable_location 函数,它将在调试跟踪日志时用到:

def get_location(pc, program, bracket_map):
    return "%s_%s_%s" % (
        program[:pc], program[pc], program[pc+1:]
    )
jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'], reds=['tape'],
                      get_printable_location=get_location)

这个函数的参数为那些 green 变量,并且返回一个字符串。在这里我们会打印出 BF 代码,并且将正在执行的指令用 ‘_‘ 包括起来。

下载 example4.py 并按与 example3.py 相同的方式生成解释器。

现在让我们打开跟踪日志来运行一个测试程序(test.b,将在一个循环内打印字母 ‘A’ 15 次)[译注 3]

$ PYPYLOG=jit-log-opt:logfile ./example4-c test.b

现在再来看一下文件 ‘logfile’。这个文件阅读起来相当困难,这里是我对它最好的解释。

这个文件记录了我们的解释器所有执行过的跟踪过程,我们据此可以窥出有哪些代码是被编译成了机器代码。这些日志在查看还有哪些不必须的指令或空间可以优化时,会非常有用。

每个执行的跟踪都起始于类似如下这样一行:

[3c091099e7a4a7] {jit-log-opt-loop

结束于类似这样一行:

[3c091099eae17d jit-log-opt-loop}

再往下的一行将告诉你它所在的循环号,以及包括了多少个 ops。在我的情况下,第一个跟踪过程看起来如下所示:

[3c167c92b9118f] {jit-log-opt-loop
# Loop 0 : loop with 26 ops
[p0, p1, i2, i3]
debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
debug_merge_point('+<[>[>_+_<-]>.[<+>-]<<-]++++++++++.', 0)
i4 = getarrayitem_gc(p1, i2, descr=<SignedArrayDescr>)
i6 = int_add(i4, 1)
setarrayitem_gc(p1, i2, i6, descr=<SignedArrayDescr>)
debug_merge_point('+<[>[>+_<_-]>.[<+>-]<<-]++++++++++.', 0)
debug_merge_point('+<[>[>+<_-_]>.[<+>-]<<-]++++++++++.', 0)
i7 = getarrayitem_gc(p1, i3, descr=<SignedArrayDescr>)
i9 = int_sub(i7, 1)
setarrayitem_gc(p1, i3, i9, descr=<SignedArrayDescr>)
debug_merge_point('+<[>[>+<-_]_>.[<+>-]<<-]++++++++++.', 0)
i10 = int_is_true(i9)
guard_true(i10, descr=<Guard2>) [p0]
i14 = call(ConstClass(ll_dict_lookup__dicttablePtr_Signed_Signed), ConstPtr(ptr12), 90, 90, descr=<SignedCallDescr>)
guard_no_exception(, descr=<Guard3>) [i14, p0]
i16 = int_and(i14, -9223372036854775808)
i17 = int_is_true(i16)
guard_false(i17, descr=<Guard4>) [i14, p0]
i19 = call(ConstClass(ll_get_value__dicttablePtr_Signed), ConstPtr(ptr12), i14, descr=<SignedCallDescr>)
guard_no_exception(, descr=<Guard5>) [i19, p0]
i21 = int_add(i19, 1)
i23 = int_lt(i21, 114)
guard_true(i23, descr=<Guard6>) [i21, p0]
guard_value(i21, 86, descr=<Guard7>) [i21, p0]
debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
jump(p0, p1, i2, i3, descr=<Loop0>)
[3c167c92bc6a15] jit-log-opt-loop}

我将那些 debug_merge_point 行所包含的指令串去掉了一些,实在是太长了。

让我们看看它都做了些什么。这个跟踪过程有 4 个参数:2 个对象指针(p0 与 p1)以及 2 个整数(i2 与 i3)。看看我们添加的那些调试行(debug_merge_point),看起来它正在跟踪循环([>+<-])的执行。

它执行的第一个操作是在第四行所示的 “>”,但是紧接着又执行了下一个操作。”>” 操作没有指令,并且看起来它被完全优化掉了。这个循环总是在磁带的同一部分上进行操作,磁带指针对这个跟踪过程来说是不变的。因此一个明确的前进操作是不必须的。

第 5 行到第 8 行是针对 “+” 操作的指令。首先它获得由指针 p1 指向的数组里的索引为 i2 的元素(第 6 行),加 1 后将它存入 i6(第 7 行),然后再存回数组(第 8 行)。

第 9 行开始 “<” 操作,但它是另一个 no-op 操作。现在看起来传给这个跟踪过程的 i2 与 i3 似乎是已经计算出的这个循环使用到的两个磁带指针。同样可以推导出来的是 p1 是磁带数组,不过不太清楚 p0 指的是什么。

第 10 到 13 行执行的是 “-” 操作:获取数组元素值(第 11 行),减 1(第 12 行),并将该值存回数组(第 13 行)。

接下来在第 14 行是 “]” 操作。第 15 到 16 行检测 i9 是否是 true(non-zero)。看,i9 是我们刚刚执行减法操作并存回到数组的值,现在被用作检测循环条件,这正如我们希望的那样(回忆一下 “]” 的定义)。第 16 行是一个保护检测,如果条件不满足,执行将跳到另外某个地方,在这里将跳到名为 <Guard2> 的过程,并且传递一个参数:p0。

假设我们通过了这个保护,第 17 到 23 行是对 bracket_map 进行字典查找操作,找到我们应该跳向的程序计数器(pc)。我不太清楚这些指令是在做什么,不过看起来有两个外部调用,以及 3 个保护。这些看起来相当昂贵,特别是我们知道 bracket_map 永远也不会变化(而 PyPy 并不知道)。待会儿你将看到我们如何来优化它。

第 24 行是对新获取到的指令指针加 1。第 25,26 行确保它不会超过程序的长度。

此外,第 27 行保护 i21,也就是刚刚递增的指令指针为 86。这是因为它将要跳回到开始(第 29 行),而指令指针为 86 是前提条件。

最后,循环结束于第 28 行,因此 JIT 可以跳到循环体 <Loop0> 去处理该情况(第 29 行),也就是又一次到循环的开头。它传递的参数是(p0, p1, i2, i3)。

优化

之前提到过,每一个循环执行都会做一个字典查找操作,找出匹配的中括号,以准备跳转。这是极其低效的,因为跳转的目标从这次执行到下次是不变的。这些信息是固定的,应该也被编译成机器代码。

问题在于查找操作针对的类型是字典,并且 PyPy 将它看作是不透明的。它并不知道这个字典不会被修改,或每次查询都会返回相同的东西。

我们需要做的是对翻译过程提供另一个提示,告诉它字典查找只是一个 pure function,也就是说,它的输出只依赖于它的输入,并且相同的输入总是会返回相同的输出。

我们要做的是,将字典查找操作包进一个函数里,并且用一个 PyPy 提供的 decorator (pypy.rlib.jit.purefunctioin)来修饰该函数:

@purefunction
def get_matching_bracket(bracket_map, pc):
    return bracket_map[pc]

这个版本参见 example5.py

再次用相同的方法生成解释器,并观察运行速度。运行 mandel.b 现在只需 6 秒!(优化之前需 12 秒)

让我们看一下跟踪日志:

[3c29fad7b792b0] {jit-log-opt-loop
# Loop 0 : loop with 15 ops
[p0, p1, i2, i3]
debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
debug_merge_point('+<[>[>_+_<-]>.[<+>-]<<-]++++++++++.', 0)
i4 = getarrayitem_gc(p1, i2, descr=<SignedArrayDescr>)
i6 = int_add(i4, 1)
setarrayitem_gc(p1, i2, i6, descr=<SignedArrayDescr>)
debug_merge_point('+<[>[>+_<_-]>.[<+>-]<<-]++++++++++.', 0)
debug_merge_point('+<[>[>+<_-_]>.[<+>-]<<-]++++++++++.', 0)
i7 = getarrayitem_gc(p1, i3, descr=<SignedArrayDescr>)
i9 = int_sub(i7, 1)
setarrayitem_gc(p1, i3, i9, descr=<SignedArrayDescr>)
debug_merge_point('+<[>[>+<-_]_>.[<+>-]<<-]++++++++++.', 0)
i10 = int_is_true(i9)
guard_true(i10, descr=<Guard2>) [p0]
debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
jump(p0, p1, i2, i3, descr=<Loop0>)
[3c29fad7ba32ec] jit-log-opt-loop}

不错!每个循环处理只是加,减,两次数组元素加载和存储,以及一个对退出条件的保护。这就是了,这个代码不再需要任何程序计数器的操作。

我不是优化方面的专家,这个提示也是由 Armin Rigo 在 pypy-dev 邮件列表上建议的。Carl Friedrich 有一系列关于如何优化解释器的很好的阐述,非常有帮助。

最后

我希望这个教程能够展示给你们:PyPy 除了是一个快速的 Python 实现以外,还能做些什么。

对于那些希望了解更多关于这个过程是如何工作的同学,这里是我推荐的一些学术论文,它们对这个过程有更深入的讲解。特别是:Tracing the Meta-Level: PyPy’s Tracing JIT Compiler。参见:http://readthedocs.org/docs/pypy/en/latest/extradoc.html

译注

【1】关于 green 变量与 red 变量,这个文档有进一步的解释,该文档解释 green 变量为 循环常量(loop constants),他们用来识别当前的循环;red 变量则是当前循环里用到的所有其它变量。

【2】在 Linux 下,PyPy 似乎需要 libffi.a(而不是 libffi.so)来生成带有 JIT 的解释器。在我的 Fedora 15 系统里,libffi-devel 包并不包含该静态库,需要手动编译 libffi 的源代码包。Ubuntu 11.04 不存在该问题。

【3】原文以及 bitbucket 上并没有给出 test.b 的源程序,下面是我根据跟踪日志里的调试语句,整理的一个 test.b 程序,运行它的结果与作者给出的日志内容基本是相同的,除了个别数字以外(不影响作者在这里的分析)。

++++++++[>++++++++>++++++++<<-]>>+<[>[>+<-]>.[<+>-]<<-]++++++++++.

参考

[译文] 使用 PyPy 编写解释器:Part 1

Microsoft 的可爱的蛋糕与对 Kernel 代码的贡献

作为一个 Linux 用户,你会信任 Microsoft 吗?也许以前你会好不犹豫的说 No,不过最近两条让人大跌眼镜的关于 Microsoft 与 Linux 的新闻则让许多人开始认真思考 Microsoft 与 Linux 的关系,一是在前不久发布的 Linux 3.0 中,来自 LWN 的统计显示 Microsoft 位列 RedHat, Intel, Novell 与 IBM 之后成为第五大 Linux Kernel 代码贡献者;另一个则是 Microsoft 在 Linux 20 周年之际,制作了一则可爱的视频,视频中卡通版的比尔盖茨为小企鹅送去了祝福的蛋糕。

Microsoft vs Linux

不管你对 Microsoft 曾经有多么厌恶,这个视频都会让你脸上露出笑容,片中以轻松的语调回顾了 Microsoft 与 Linux 的战争,并在最后以友好的姿态建议为二者的对抗划上句话,至少 Microsoft 认为二者可以共存,它们的关系应该是 Microsoft and Linux,而不是 Microsoft vs Linux。

这个视频释放的善意当然让人欣慰,世界和平这个词也许说出来有点矫情,不过假如 Microsoft 与 Linux 真的能够相安无事,那这个世界真的会清静许多;如果 Microsoft 不仅仅是贡献 Kernel 代码,还能够在一些应用上遵循标准,甚至开放接口,这个世界无疑将更加美好。不过,就像我的祖国与她那一衣带水的邻居在一起时经常所说的那样,以史为鉴,面向未来。重温 Microsoft 对待 Linux 的历史,也许对于二者未来的关系更有意义。

当 Linus 发出那封著名的宣布 Linux 诞生的邮件时,微软已经凭借 DOS 取得了在 PC 操作系统的主导地位,并开始进入 Windows 的时代,虽然 Linux 并不是为了取代 Windows 而生的,但 Linux 的发展在一定程度上逐渐的威胁到了 Windows,尤其是当 Windows 也进入到 服务器领域时,二者的竞争是不可避免的。

在 1998 年泄漏的 Halloween 文档里, Microsoft 第一次正式的承认了开源特别是 Linux 将是对 Microsoft 统治地位的主要威胁,并提出了一些战略上的措施来阻止 Linux 乃至开源运动的发展。这些泄漏的内部文档令局促不安的微软正式的站到了 Linux 的对立面。

2000 年,Ballmer 在微软的年度财会上对 Linux 的评价引申出了那句臭名昭著的“Linux is communism”,在他看来,Linux 的迅速扩展是因为 Linux 有一些共产主义的特质,那就是 Free。可怜 Ballmer 先生在错误的地方说出了这番话,如果是在天朝,那该多合适啊。

2001 年,又是 Ballmer 先生在一次接受媒体采访时,提到了另一句臭名昭著的话“Linux is a cancer”,他把对 Linux 的痛恨比喻为癌症,任何被它侵蚀的代码都被感染而无法具有知识产权的功能。

2004 年,Microsoft 对 Linux 的打击进入了一个新的阶段,单纯的用肮脏卑鄙下流的语言已经不能起到应有的效果。微软发动了一场市场战役,通过一些客户案例来宣称在实际的使用上,Linux 并不能起到节约开支的作用。

Linux 在不同时期都被指责侵犯了别人的版权,包括微软的,Oracle 的,UNIX 的,这其中有 Microsoft 在背后不遗余力的推动。2009 年 Microsoft 控告 Tomtom 采用了 Linux Kernel 的产品侵犯了微软的 FAT32 代码的版权;在前不久,Microsoft 又指控 Android 代码侵犯了版权,并要求 Samsung 为出厂的每台 Android 设备支付 15 美元。

另一方面,随着 Linux 在 Server 市场的所向披靡,微软又不得不接受这个现实,并不得不在自己的产品中支持 Linux。微软与 Linux 的关系让人觉得这得是精神多么分裂的人才能干出来的事啊。

2009 年,微软的 Hyper-V 的 Linux 驱动被发现包含了 GPL 代码,随后微软开源了该驱动,并对开源的代码使用了 GPL 版权。微软开源的这些代码主要是为了能在自己的 Hypervisor 虚拟机上更好的运行 Linux。显然,云计算与虚拟化的大热,以及 VMWare 的高利润率不可能不吸引到微软投入其中。

微软与 Novell 的合作(现在是 Attachmate,该合作刚刚续到 2016 年) 也是为了能够更好的在 Windows 与 Linux 的互操作性上提供支持,特别是虚拟化的环境下,比如在 Hyper-V 虚拟机上运行 SUSE Enterprise Linux Server。微软在今年早些时候宣布 Hyper-V 虚拟机将支持 CentOS,在刚刚结束的 OSCON 2011 上,微软又宣布 Hyper-V 将正式支持 RHEL。在虚拟化与云计算的大环境下,微软不得不考虑客户多系统的环境。

所有这些都是商业利益,不过在 Linux Kernel 的开发人员眼里,源代码才是最真实的。微软在让自己的代码进入官方 Kernel 的过程中,痛苦不堪。在 2009 年开放源代码并提交给 Kernel 开发人员之后,这些代码并没有直接进入官方 Kernel,而是在 staging tree 中接受 review,直到符合 Kernel 的代码标准为止。

显然,Windows 与 Linux 这两个各有 20 年历史的项目,代码上最直观的不同来自于编码风格。虽然 Linux Kernel 的开发人员都极其痛恨 Windows 的编码规范(DWORD, HANDLE 这些玩意儿),但让 Windows 的开发人员将这些代码一一改成符合 Linux 的编码规范,也不是件好差事。因此在最初的代码提交后,Microsoft 就没了下文,直到负责驱动部分代码维护的 Greg K.H 威胁将这些代码从 staging tree 中拿掉,微软才又开始慢慢的行动起来,不过进程仍然极其缓慢,直到这次 3.0 的发布。根据 LWN 的统计,微软的开发人员将最初提交的 20000 多行代码精简到了大约 15000 行代码。

因此微软这次对 Linux 3.0 的贡献主要集中在对之前开源驱动代码的清理与规范上,未来微软仍有可能对 Linux Kernel 有较大的贡献,因为这些代码仍然在 staging tree 中,仍然有一些问题需要解决才能正式的进入 Kernel,并且随着 Kernel 的发展,这些代码也需要不断维护。至于除此之外,微软会不会对 Linux Kernel 有更多贡献,除非微软开发自己的 Linux 发行版。

最后回到蛋糕身上,当你再次欣赏这个可爱的视频时,你会想到什么呢?

我想到的是,前不久,当 Firefox 5.0 发布时,IE 团队也送上了祝贺的蛋糕。嗯,这是他们的老套路了。

crypt_blowfish 的一行代码引发的 bug

提起安全,不同的人也许会有不同的理解,从日常可见的各种病毒,到互联网背后的各种安全协议,都属于安全的范畴。但对普通的计算机用户来说,最切身的感受还是登录自己系统的密码的安全。要确保密码的安全,除了要求用户使用强壮的不易猜到的密码外,更重要的是系统使用一个安全的方法来存放用户的密码。使用密码学里的某个哈希算法对密码进行哈希,并存放该哈希值就是一种标准的方法。

使用该方法的一个显而易见的优点是避免了存储密码明文所带来的风险,对用户的认证只需用同样的算法对用户输入的密码生成哈希值,并于存储的哈希值进行比较即可。该方法在 Unix/Linux 下由来已久,接口就是我们所熟悉的 crypt(3) 函数。

可以看出,在密码的哈希值已知的情况下,采用的哈希算法越强壮,密码就越难破解。从密码学的角度来说,一个给定的哈希算法返回的哈希值长度通常是固定的,理论上总会有多个密码的哈希值是相同的。因此这里的强壮意味着,即使已知该哈希值和哈希算法,也很难在可行的时间内推算出该密码,或某个其它的哈希值相同的字串。

传统的 crypt(3) 实现使用的是 DES 加密算法的一个变种,该算法在很长的时间内被认为是安全的,但是随着计算机的迅猛发展,该算法在使用了近 30 年后,已不再认为安全。因此,一些其它的算法被选择来代替它,这其中使用最广泛的无疑是 MD5,本文要讲的基于 blowfish 算法的 crypt_blowfish 则是另外的一个。为了区分开这些由不同的算法生成的哈希值,调用 crypt 函数的 salt 参数被赋予新的约定,即如果 salt 字符串以 $id$ 开头,并且以 $ 结尾,那么 id 的值将表示所采用的哈希算法。MD5 的 id 值为 1,crypt_blowfish 的 id 值则为 2a。

(再废话一点,当然,现在来说,MD5 也不再被认为是安全的了,包括 SHA-1,这要归功于王小云教授在 04 年的密码编码年会上对 MD5 的碰撞攻击的著名演讲,因此当前主流发行版使用的哈希算法是 SHA-512。其实从使用范围上来说,基于 blowfish 的哈希算法从未像 MD5 那样广泛,当然,并不是因为 blowfish 加密算法本身不够安全,而是由于 blowfish 并不在 NIST 认可的算法列表里。因此像 Red Hat 这样的发行版制造商在选择替代 MD5 的算法时,并没有考虑它,而是重新设计了基于 SHA-2 的 SHA-256 以及 SHA-512。当前使用 crypt_blowfish 的发行版包括 OpenWall,SUSE 以及 ATL。除此之外,PHP 5.3+也集成了该算法。)

crypt_blowfish 的这个 bug 非常简单,下面是有问题的代码片段:这里的 tmp 类型是 unsigned int,ptr 与 key 的类型都是 char *,key 指向的是待转换的密码字符串。这段代码可以简单理解为,将密码以 4 个字节为单位放到 tmp 里。

tmp = 0;
for (j = 0; j < 4; j++) {
    tmp <<= 8;
    tmp |= *ptr;

    if (!*ptr) ptr = key; else ptr++;
}

这是 crypt_blowfish 的作者所找到的 bug 以及修复:

Oops. In BF_std.c: BF_std_set_key(), change:
    tmp |= *ptr;
to:
    tmp |= (unsigned char)*ptr;

对于熟悉 C 语言的同学来说,这个 bug 很容易理解,也是 C 语言里最容易出错的地方。即 C 语言的标准并没有指定 char 类型是 signed char 还是 unsigned char,而是留给实现自己去定义。当 char 类型被定义为 signed char 类型时(大部分情况是,比如 x86 下的 Linux),这里的 *ptr,将先被转换为 signed int,然后再与 tmp 进行 OR 操作后赋值给 tmp。也就是说,如果密码里的某个字节最高位为 1(ASCII range 128 ~ 255,e.g. 0x80),那么该字节在符号扩展为 signed int 后,扩展的高 3 个字节全为 1(i.e. 0xffffff80),再于 tmp 进行 OR 操作将冲掉之前存储的字节。

简单来说,在某种情况下,如果用户的密码里的某个字节高位为1,那么该 bug 将使得寻找与该密码有相同哈希值的字串变得容易,从而使得密码的破解也相对容易。举个例子,如果某个密码为 “ab£”,那么在该 bug 的影响下,使用 “£” 或者 “xy£” 都将生成相同的哈希值。显然,这是一个令人恼火的 bug,即使在密码里使用这种字节的情况并不常见。

虽然对该 bug 的修复也很简单,只有一行代码,但一个完整的更新方案还要考虑已存在的大量可能正确也可能错误的哈希值,如果只是单纯的升级该修复,那么有可能在升级后,用户使用旧的密码将无法登录进系统。因此,如何保证在打上该修复后,即保证用户登录系统不受影响,又能将期间的安全隐患降到最低,是一个非常棘手的难题。这也是大部分安全问题所共有的特质。

对于该 bug 来说,更糟糕的地方在于,并不是所有的含有 8bit 字节的密码的哈希值(使用旧算法生成的)都处于相同的情况,在修复后的算法下,有的哈希值仍然可以用旧密码生成,有的则必须用另外一个字串生成,有的则无法通过任何字串生成,从而成为一个无法使用的哈希值。不过一个共同点是,如果某个哈希值是由包含 8bit 字节的密码使用旧的算法生成的,那么在新的算法下,如果该哈希值对应一个密码的话,该密码必然包含字节 0xff。

因此 crypt_blowfish 的作者 Solar Designer 提供的解决方案是扩充上文提到的哈希算法 id,简单的说,两个新的 id,$2x$ 与 $2y$ 被定义,其中 $2x$ 被定义为有问题的 crypt_blowfish 算法,$2y$ 被定义为正确的 crypt_blowfish 算法,原有的 $2a$ 则被认为是不确定的算法。新的修复后的算法生成的哈希值的 id 将为 $2y$。

Solar Designer 的方案是一个通用的方案,具体的发行版或集成了 crypt_blowfish 的应用还需要去处理其余的情况,最主要的一点是如何解析 id 为 $2a$ 的哈希值。为了确保任何用户的登录都不受影响,可以将 $2a$ 按 $2x$ 处理,此时 crypt_blowfish 将使用旧的有问题的算法来比对哈希值,当然相应的风险也将存在。如果将 $2a$ 按 $2y$ 处理,此时 crypt_blowfish 将使用新的修复后的算法来比对哈希值,这意味着黑客仍然有可能会利用旧的漏洞登录进系统,为了防止该情况,可以禁止任何包含 0xff 字节的密码,此外,这也意味着某些用户可能再也无法登录,这种情况需要系统或应用使用其它方法来通知用户重置密码。具体的升级方式依赖于具体的管理员策略,但这里没有一个完美的解决方案。系统或应用所能提供的解决办法是提供两个选项,一是是否将 $2a$ 按 $2x$ 处理,二是在上面选项为否的情况下,是否禁止包含 0xff 字节的密码。

研究 crypt_blowfish 的这个 bug 能够得到许多经验与教训。首先,在使用 C 语言编程时,那些需要大量使用位操作,以及经常在 signed 与 unsigned 之间转换的地方要慎之又慎,这些地方通常都在底层,一旦有 bug,影响的将不只是底层的一小块功能,而且难于找到根源;其次,也是有意思的一点是这个 bug 至少已经存在了 13 年之久,而没有被发现。相信这样的 bug 应该这不是最后一个,这提醒我们即使在使用非常成熟的代码库时(不管是开源还是闭源),仍然需要大量枯燥无味的测试,谁又能保证自己恰好不会碰上这样一个 bug 呢。

引用与致谢

Prefetch,性能,与毒药

性能也许是大多数软件开发人员所不愿意面对的特性之一。编写代码是容易的,但优化代码,提高代码的执行效率并不容易。比起写代码时的酣畅淋漓,提高性能除了一开始的架构设计无误外,到最后,往往变成在一些个别代码上的纠结,很多时候你不得不用一些看起来丑陋的代码去替代那些散发着你的灵感的想法。即使如此,这种性能上的努力有时候也并不如期望的那样,甚至更糟。

在不同的领域,提高性能有着不同的实现方法。有的领域也许需要一个更优的算法,有的领域也许需要一些编程上的技巧。在 Kernel 领域,由于 Kernel 直接面对硬件,性能上的优化往往与硬件提供的功能息息相关。当代计算机硬件在性能上最突出的矛盾是 CPU 的运行速度远远超过内存的速度,如果所有内存引用的数据都需要直接从内存读/写的话,CPU 将不得不把时间花在对内存操作的等待上。为此,当代 CPU 都有一些快速的 CPU Cache 用来临时存放所需要的内存数据,以加快运行速度。Kernel 对性能的优化很大一部分就是利用 Cache 的优化,包括经常见到的仔细定义结构体的成员顺序,以使得那些通常需要一块访问的成员在一个 Cache line 内就可以访问到。

让事情更美好(或者更糟糕)的是 CPU 制造商也在想尽一切办法尽量减少内存访问所引起的延迟。常见的这样的高级 CPU 功能包括:Prefetch, Out-Of-Order Execution, Branch Prediction 等等,这些功能有的是纯硬件的,对操作系统透明;有的功能 CPU 会提供相应的指令可用。使用这些先进的硬件功能帮助 Kernel 提高性能,是非常诱人的。然而正如前面提到的那样,采用这些功能有时候并不见得一定能提高性能,由于这些硬件功能在实现细节上的不公开等种种原因,结果甚至更差。Prefetch 就是最近 Kernel 开发人员刚刚学到的一例。

Prefetch 简单的说就是 CPU 通过某种算法猜测接下来可能要执行的指令/数据,然后提前从内存里取出来并存放到 Cache 中,如果猜测的结果与实际执行的一样,则执行速度加快。Prefetch 分为硬件 Prefetch 与 软件 Prefetch。硬件 Prefetch 包括 Prefetch 指令与数据,指令的 Prefetch 相对容易理解,并且可以看出顺序执行的指令 Prefetch 的准确率高,而带有条件判断的语句则需要与 Branch Prediction 功能相结合。数据的 Prefetch 则牵涉到 CPU 对内存数据访问模式的分析,比指令 Prefetch 更加复杂,通常是 CPU 在探测到某些特定的事件后(一般是发生了连续的 Cache misses),触发 Prefetch 自动执行。硬件 Prefetch 对操作系统来说是透明的。软件 Prefetch 则是操作系统或应用程序明确要求 CPU 将某个地址的数据 Prefetch 到 Cache 中,以备以后使用。

Prefetch 由于简单的接口,并且以性能为目的,被 Kernel 开发人员大量使用。最常见的地方是 list.h 里的 prefetch() 宏:

#define list_for_each(pos, head) \
        for (pos = (head)->next; prefetch(pos->next), pos != (head); \
                pos = pos->next)

这里的 prefetch() 宏是对底层硬件平台 prefetch 指令的一个封装,不同的平台有自己的 prefetch 实现方式,一般是在平台的 processor.h 里定义的。上面这段代码使用 prefetch 的想法是,在处理链表中当前节点的同时,让 CPU 将下一个节点的数据提前取出来,并放到 Cache 中,这样当处理到下一个节点时,数据已经在 Cache 里了。通常来说,链表在内存中的存放并不像数组那样连续,因此很难通过 Cache 优化。软件 Prefetch 在这儿提供了将下一个节点数据提前拷贝到 Cache 中的可能。

如果一切都如这里分析的一样,内核大量的链表操作将因此变快。可惜,事实并非如此。

最先对这里的 prefetch 提出质疑的是 Andi Kleen,不过 Andi 的理由并不那么充分,他提交的将 prefetch 从 list.h 中去除的 patch 也没有获得通过。最近 Linus 也对 list.h 里的 prefetch 发表了看法,这一次是 Linus 在自己的机器上 build kernel 时发现了 prefetch 的问题,大量使用 prefetch 并没有带来性能上的改进,相反,去掉 prefetch 反而运行的更快。Ingo Molnar 随后跟进对这里的 prefetch 进行了研究,他重现了 Linus 的问题,并且确认在这里使用 prefetch 将降低约 0.5% 的性能。

虽然 0.5 并不是一个很大的数字,但这里的问题在于本来应该提高性能的地方,却降低了性能。Linus 的分析是,他的测试有相当一部分操作是遍历单向链表 hlist,这些单向链表都很短,并没有多少让 prefetch 提高的空间。甚至,大部分链表只有一个节点,因此这里的 prefetch 的地址是 NULL。很明显,按照一般的设想,CPU 在遇到 prefetch(NULL) 的情况时,应该什么也不做,但在 x86 机器上并非如此。根据 Ingo 的分析,prefetch(NULL) 大约需要 20 个 CPU cycles。Ingo 通过软件的方法绕过了 prefetch(NULL) 的问题,即只有在地址非 NULL 时才执行 prefetch 指令,并做了测试,虽然性能有所进步,但比起完全去掉 prefetch 来仍然要差。

根据 Ingo 的观测,无论在这里添加还是去除 prefetch 操作,CPU 总体上执行 prefetch 指令的次数相差并不大。也就是说,此时 CPU 里的硬件 prefetch 已经处于饱和的状态,如果再通过软件显式去 prefetch 某些数据,似乎干扰了 CPU 正常的硬件 prefetch 策略。所以最好的选择就是让硬件自己去 prefetch,硬件在决定哪些数据该 prefetch 时,表现更好。Ingo 据此得出的结论是:

So the conclusion is: prefetches are absolutely toxic, even if the NULL ones are excluded.

这个结论也与最初 Andi 邮件里的说法相似,Andi 曾引述来自硬件设计人员的反馈,表示硬件开发者并不赞成软件开发人员显式的去使用 prefetch,除非有特别好的理由,而这里的 prefetch 并不是。

最终的结果是在即将发布的 Linux 3.0 里,list 操作里的 prefetch 被拿掉。这个结果与 Andi 提交的 patch 并不完全一致,Andi 的 patch 是提供一个 CONFIG 开关来控制,并且对 K7 架构,prefetch 默认是打开的。

仍然有人认为 Linus 与 Ingo 的分析并不能完全说明所有情况,尤其是 Linus 明确表示在他的测试情况下,list 的长度都很短,如果某个另外的情况使得 list 很长,性能是否会完全不一样呢?是否所有硬件平台的 prefetch 都与 x86 类似呢?没有人能明确回答这样的问题。大多数性能问题,答案都来自于大量的测试以及可信的数据,很多时候理论上的分析,并不完全正确,甚至恰恰相反。在这里,我们最好相信硬件 prefetch 能做的更好。

Kernel 开发人员的这个教训似乎告诉我们 prefetch 真的是一剂毒药。但这并不表示在所有情况下,prefetch 都是有害的,有时候,以毒攻毒也是有用的,正确使用 prefetch 仍然能带来性能上的提升,前提是你深入理解了 prefetch 的毒性,当然更重要的还是枯燥乏味的测试与数据。

引用与致谢