Programming in Lua(五)- Coroutine, Lua Stack

在《 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_Statestack 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 是一个非常巧妙的设计。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s


%d 博主赞过: