技术奇异点

在《 Programming in Lua（三）－ Yields in C 》里讨论了 Lua 虚拟机对 yields-in-C 及其 stack 的处理。当时还未读 Lua 虚拟机的实际代码，只根据语言的行为来推测，有些术语也不符合通常用法。最近从 Lua stack 的实现入手，发现了一些以前没想过的问题：为什么 resumes-in-C 从来不是问题？为什么有 lua_yieldk() 而没有对应的 lua_resumek() ？

首先从术语的标准化说起。《 Programming in Lua（三）－ Yields in C 》里有多处这样的描述：

• 「stack 上 ⋯⋯ 的执行层次」；
• 「virtual stack 上的 Lua 部分的 stack」；
• 「Lua stack 段」。

其中「执行层次」、「部分」、「段」这样的字眼应该替换为「stack frame」这个更常用的术语。线程运行时，stack 呈现两层意义。一是后入先出的简单线性结构；二是把此线性结构划分成与函数调用层次一一对应的若干段，这样的一段就被称为一个 stack frame。大多数语言的 runtime 或虚拟机中，stack frame 并无单独的数据结构表示。在 64-bit x86 的 C runtime (CRT) 中，每个 stack frame 的首项是上一层 stack frame 的最低地址 (base)，称为 stored frame pointer (SFP)，最顶层 stack frame base 存储在 %ebp 寄存器中 。即每次生成新的 stack frame 时，首先将 %ebp 寄存器入栈形成 SFP，然后把当前的 %esp 赋给 %ebp。通过这种方式让需要解析 stack frame 的程序 (比如 debugger) 得到所需信息。(SFP 并非一定存在，臭名昭著的 omit-frame-pointer 编译器优化会去掉 SFP，这时 debugger 只能借助额外存储的 symbols 来解析 stack frame。)

就需求本身来说，Lua stack 要解决的问题比 C 复杂的多，甚至比同为动态语言的 Python 更复杂。基于虚拟机的语言的 call stack 有两种可能的设计：一是借用虚拟机本身的 CRT stack。Byte-code 的函数调用指令对应虚拟机本身 native 代码的函数调用，虚拟机的 CRT stack 随 byte-code 函数调用的层次增加而增长。二是由虚拟机维护额外的 call stack 数据结构。Byte-code 的函数调用指令和其它指令一样，在虚拟机的同一个循环中完成，虚拟机的 CRT stack 不体现 byte-code 函数的调用层次。后者通常被称为 stackless 方案，前者暂且对应称为 stackful 方案。

Lua 是 embedded/extension 语言，byte code 的运行总会夹杂 C 函数。这些 C 函数的 call stack 在逻辑上是 byte-code 运行状态的一部分，实际上则间杂在 Lua 虚拟机的 CRT stack 中 (在涉及 Lua 的情况下讨论 CRT stack 时，要始终说明是虚拟机的 CRT stack 还是 C 函数的 call stack)。从这个角度来说，embedded/extension 语言更倾向于选择 stackful 设计。但 stackful 设计的固有缺陷在于 stack 结构是平台相关的，很难用跨平台的方式实现诸多功能，比如协作式多任务 (cooperative multi-threading)，跟踪垃圾回收 (tracing-GC)，lexical closure。尽管不是全部原因，Python 缺少诸多高级特性与其 stackful 实现有很大关系。

为了遵守 ANSI C 的跨平台性和更好的实现高级动态功能，Lua 采用了 stackless 实现。这给处理 C 代码的 call stack 带来了一些挑战。Lua 的 stack 存储在 struct lua_State 的 stack field 中，是一个 TValue* 的数组。其内容包括：

• 函数指针。Proto* (Lua 函数) 或者 lua_CFunction (C 函数)。注意函数指针不是函数的返回地址。
• 函数的参数和返回值。包括 Lua 和 C 函数之间传递的参数和返回值。
• Lua 函数的局部变量。

在这个 stack 上缺少一些属于 call stack 的东西：

• C 代码本身的 call stack。
• 函数的返回地址。
• Stack frame 信息，类似 SFP。

这是因为 Lua 采用了双 stack 结构。对应的 stack frame 信息存储在一个 struct CallInfo 链表中，每个节点对应一个 stack frame，它对 TValue* 数组 stack 的描述如下：

• Field func 表示 stack frame 在 TValue* 数组上的起始位置 (之所以用 func 作为 field 名称是因为在 TValue* 数组上这个位置永远是函数指针)，field top 表示结束位置。
• Field union u 存储和函数类型相关的信息。Lua 函数信息存储在 u.l 中，C 函数在 u.c 中。
• u.l.savedpc 表示函数的返回地址。这个值仅当 Lua 函数作为 caller 的情况有效。C 函数作为 caller 时，返回地址在 CRT stack 中。
• 当 C 函数中发生 yield 时，CRT stack 被破坏，该 coroutine 下次被 resume 的执行地址由 u.c.k 来承担。详见《 Programming in Lua（三）－ Yields in C 》。

这里值得多说一句，为什么在 C 函数中执行 yield 会破坏 CRT stack？上文说过，Lua 的设计主要是 stackless 方式，其具体实现是通过 luaV_execute() 中的循环执行 byte code，通过额外数据结构 (其实是双数据结构) 而非 CRT stack 来维护 call stack。但在 resume coroutine 时，luaV_execute() 间接地递归调用自己并在 callee 的循环中执行 resumed coroutine。也就是说由 CRT stack 来维护 coroutine 上下文切换。Yields 的机制是 longjmp 回到 luaV_execute() 函数递归调用自身的下一条指令 (虚拟机的 native 指令而非 byte-code 指令)，同时把 CRT stack 恢复到 resume 前的状态。所以 yields-in-C 会破坏 C 函数的 call stack。

尽管 coroutine 涉及了对 CRT stack 的操作，但是和 error 一样，仅限于 ANSI C 支持的 longjmp，不会破坏 Lua 虚拟机的跨平台性。问题是，为什么 Lua 要在总体的 stackless 设计中制造这个 stackful 例外？首先退一步说，即使采用 stackless 方式实现 coroutine 切换，仅仅能避免在 yields-in-byte-code 中使用 longjmp，仍然无法避免在 yields-in-C 中使用 longjmp。这是因为，虽然不再有必要 longjmp 回到最近一次 resume 之处，但是仍然需要从 yield 之处回到最近的 Lua 虚拟机代码。不仅如此，stackless 方式还要给 resumes-in-C 引入类似的 longjmp (因为不再利用 CRT stack，所以 resumes-in-C 也必须立即回到 Lua 虚拟机代码)，破坏调用 resume 的 C 函数的 call stack，给 resumes-in-C 加上同现在的 yields-in-C 一样的局限性。而现在的 stackful 方法则完全没有这方面的问题。这正是无需 lua_resumek() 的原因。Stackful coroutine 是一个非常巧妙的设计。

This entry was posted on 2013/05/09 at 11:13 上午 and is filed under 软件开发, Lua, 开源. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.