在《 Programming in Lua（三）－ Yields in C 》里討論了 Lua 虛擬機(jī)對(duì) yields-in-C 及其 stack 的處理。當(dāng)時(shí)還未讀 Lua 虛擬機(jī)的實(shí)際代碼，只根據(jù)語(yǔ)言的行為來(lái)推測(cè)，有些術(shù)語(yǔ)也不符合通常用法。最近從 Lua stack 的實(shí)現(xiàn)入手，發(fā)現(xiàn)了一些以前沒(méi)想過(guò)的問(wèn)題：為什么 resumes-in-C 從來(lái)不是問(wèn)題？為什么有 lua_yieldk() 而沒(méi)有對(duì)應(yīng)的 lua_resumek() ？

首先從術(shù)語(yǔ)的標(biāo)準(zhǔn)化說(shuō)起?！?Programming in Lua（三）－ Yields in C 》里有多處這樣的描述：

• 「stack 上 ?? 的執(zhí)行層次」；
• 「virtual stack 上的 Lua 部分的 stack」；
• 「Lua stack 段」。

其中「執(zhí)行層次」、「部分」、「段」這樣的字眼應(yīng)該替換為「stack frame」這個(gè)更常用的術(shù)語(yǔ)。線程運(yùn)行時(shí)，stack 呈現(xiàn)兩層意義。一是后入先出的簡(jiǎn)單線性結(jié)構(gòu)；二是把此線性結(jié)構(gòu)劃分成與函數(shù)調(diào)用層次一一對(duì)應(yīng)的若干段，這樣的一段就被稱(chēng)為一個(gè) stack frame。大多數(shù)語(yǔ)言的 runtime 或虛擬機(jī)中，stack frame 并無(wú)單獨(dú)的數(shù)據(jù)結(jié)構(gòu)表示。在 64-bit x86 的 C runtime (CRT) 中，每個(gè) stack frame 的首項(xiàng)是上一層 stack frame 的最低地址 (base)，稱(chēng)為 stored frame pointer (SFP)，最頂層 stack frame base 存儲(chǔ)在 %ebp 寄存器中 。即每次生成新的 stack frame 時(shí)，首先將 %ebp 寄存器入棧形成 SFP，然后把當(dāng)前的 %esp 賦給 %ebp。通過(guò)這種方式讓需要解析 stack frame 的程序 (比如 debugger) 得到所需信息。(SFP 并非一定存在，臭名昭著的 omit-frame-pointer 編譯器優(yōu)化會(huì)去掉 SFP，這時(shí) debugger 只能借助額外存儲(chǔ)的 symbols 來(lái)解析 stack frame。)

就需求本身來(lái)說(shuō)，Lua stack 要解決的問(wèn)題比 C 復(fù)雜的多，甚至比同為動(dòng)態(tài)語(yǔ)言的 Python 更復(fù)雜?；谔摂M機(jī)的語(yǔ)言的 call stack 有兩種可能的設(shè)計(jì)：一是借用虛擬機(jī)本身的 CRT stack。Byte-code 的函數(shù)調(diào)用指令對(duì)應(yīng)虛擬機(jī)本身 native 代碼的函數(shù)調(diào)用，虛擬機(jī)的 CRT stack 隨 byte-code 函數(shù)調(diào)用的層次增加而增長(zhǎng)。二是由虛擬機(jī)維護(hù)額外的 call stack 數(shù)據(jù)結(jié)構(gòu)。Byte-code 的函數(shù)調(diào)用指令和其它指令一樣，在虛擬機(jī)的同一個(gè)循環(huán)中完成，虛擬機(jī)的 CRT stack 不體現(xiàn) byte-code 函數(shù)的調(diào)用層次。后者通常被稱(chēng)為 stackless 方案，前者暫且對(duì)應(yīng)稱(chēng)為 stackful 方案。

Lua 是 embedded/extension 語(yǔ)言，byte code 的運(yùn)行總會(huì)夾雜 C 函數(shù)。這些 C 函數(shù)的 call stack 在邏輯上是 byte-code 運(yùn)行狀態(tài)的一部分，實(shí)際上則間雜在 Lua 虛擬機(jī)的 CRT stack 中 (在涉及 Lua 的情況下討論 CRT stack 時(shí)，要始終說(shuō)明是虛擬機(jī)的 CRT stack 還是 C 函數(shù)的 call stack)。從這個(gè)角度來(lái)說(shuō)，embedded/extension 語(yǔ)言更傾向于選擇 stackful 設(shè)計(jì)。但 stackful 設(shè)計(jì)的固有缺陷在于 stack 結(jié)構(gòu)是平臺(tái)相關(guān)的，很難用跨平臺(tái)的方式實(shí)現(xiàn)諸多功能，比如協(xié)作式多任務(wù) (cooperative multi-threading)，跟蹤垃圾回收 (tracing-GC)，lexical closure。盡管不是全部原因，Python 缺少諸多高級(jí)特性與其 stackful 實(shí)現(xiàn)有很大關(guān)系。

為了遵守 ANSI C 的跨平臺(tái)性和更好的實(shí)現(xiàn)高級(jí)動(dòng)態(tài)功能，Lua 采用了 stackless 實(shí)現(xiàn)。這給處理 C 代碼的 call stack 帶來(lái)了一些挑戰(zhàn)。Lua 的 stack 存儲(chǔ)在 struct lua_State 的 stack field 中，是一個(gè) TValue* 的數(shù)組。其內(nèi)容包括：

• 函數(shù)指針。Proto* (Lua 函數(shù)) 或者 lua_CFunction (C 函數(shù))。注意函數(shù)指針不是函數(shù)的返回地址。
• 函數(shù)的參數(shù)和返回值。包括 Lua 和 C 函數(shù)之間傳遞的參數(shù)和返回值。
• Lua 函數(shù)的局部變量。

在這個(gè) stack 上缺少一些屬于 call stack 的東西：

• C 代碼本身的 call stack。
• 函數(shù)的返回地址。
• Stack frame 信息，類(lèi)似 SFP。

這是因?yàn)?Lua 采用了雙 stack 結(jié)構(gòu)。對(duì)應(yīng)的 stack frame 信息存儲(chǔ)在一個(gè) struct CallInfo 鏈表中，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè) stack frame，它對(duì) TValue* 數(shù)組 stack 的描述如下：

• Field func 表示 stack frame 在 TValue* 數(shù)組上的起始位置 (之所以用 func 作為 field 名稱(chēng)是因?yàn)樵?TValue* 數(shù)組上這個(gè)位置永遠(yuǎn)是函數(shù)指針)，field top 表示結(jié)束位置。
• Field union u 存儲(chǔ)和函數(shù)類(lèi)型相關(guān)的信息。Lua 函數(shù)信息存儲(chǔ)在 u.l 中，C 函數(shù)在 u.c 中。
• u.l.savedpc 表示函數(shù)的返回地址。這個(gè)值僅當(dāng) Lua 函數(shù)作為 caller 的情況有效。C 函數(shù)作為 caller 時(shí)，返回地址在 CRT stack 中。
• 當(dāng) C 函數(shù)中發(fā)生 yield 時(shí)，CRT stack 被破壞，該 coroutine 下次被 resume 的執(zhí)行地址由 u.c.k 來(lái)承擔(dān)。詳見(jiàn)《 Programming in Lua（三）－ Yields in C 》。

這里值得多說(shuō)一句，為什么在 C 函數(shù)中執(zhí)行 yield 會(huì)破壞 CRT stack？上文說(shuō)過(guò)，Lua 的設(shè)計(jì)主要是 stackless 方式，其具體實(shí)現(xiàn)是通過(guò) luaV_execute() 中的循環(huán)執(zhí)行 byte code，通過(guò)額外數(shù)據(jù)結(jié)構(gòu) (其實(shí)是雙數(shù)據(jù)結(jié)構(gòu)) 而非 CRT stack 來(lái)維護(hù) call stack。但在 resume coroutine 時(shí)，luaV_execute() 間接地遞歸調(diào)用自己并在 callee 的循環(huán)中執(zhí)行 resumed coroutine。也就是說(shuō)由 CRT stack 來(lái)維護(hù) coroutine 上下文切換。Yields 的機(jī)制是 longjmp 回到 luaV_execute() 函數(shù)遞歸調(diào)用自身的下一條指令 (虛擬機(jī)的 native 指令而非 byte-code 指令)，同時(shí)把 CRT stack 恢復(fù)到 resume 前的狀態(tài)。所以 yields-in-C 會(huì)破壞 C 函數(shù)的 call stack。

盡管 coroutine 涉及了對(duì) CRT stack 的操作，但是和 error 一樣，僅限于 ANSI C 支持的 longjmp，不會(huì)破壞 Lua 虛擬機(jī)的跨平臺(tái)性。問(wèn)題是，為什么 Lua 要在總體的 stackless 設(shè)計(jì)中制造這個(gè) stackful 例外？首先退一步說(shuō)，即使采用 stackless 方式實(shí)現(xiàn) coroutine 切換，僅僅能避免在 yields-in-byte-code 中使用 longjmp，仍然無(wú)法避免在 yields-in-C 中使用 longjmp。這是因?yàn)椋m然不再有必要 longjmp 回到最近一次 resume 之處，但是仍然需要從 yield 之處回到最近的 Lua 虛擬機(jī)代碼。不僅如此，stackless 方式還要給 resumes-in-C 引入類(lèi)似的 longjmp (因?yàn)椴辉倮?CRT stack，所以 resumes-in-C 也必須立即回到 Lua 虛擬機(jī)代碼)，破壞調(diào)用 resume 的 C 函數(shù)的 call stack，給 resumes-in-C 加上同現(xiàn)在的 yields-in-C 一樣的局限性。而現(xiàn)在的 stackful 方法則完全沒(méi)有這方面的問(wèn)題。這正是無(wú)需 lua_resumek() 的原因。Stackful coroutine 是一個(gè)非常巧妙的設(shè)計(jì)。

這篇文章發(fā)布于 2013年05月9日，星期四，11:38，歸類(lèi)于 Lua, 開(kāi)源, 軟件開(kāi)發(fā)。 您可以跟蹤這篇文章的評(píng)論通過(guò) RSS 2.0 feed。 您可以留下評(píng)論，或者從您的站點(diǎn)trackback。