Lua 设计与实现 -- 虚拟机篇
Abstract Keywords Lua 技术笔记
Citation Yao Qing-sheng.Lua 设计与实现 -- 虚拟机篇.FUTURE & CIVILIZATION Natural/Social Philosophy & Infomation Sciences,20220615. https://yaoqs.github.io/20220615/lua-she-ji-yu-shi-xian-xu-ni-ji-pian/
转载自 Lua 设计与实现–虚拟机篇
本篇文章是 Lua 设计与实现专栏的第三篇，主要结合了《Lua 设计与实现》书中的第五章 (虚拟机)，以及 lua5.3 源码进行一些总结，由于原书中主要是基于 lua5.1 进行书写的，所以可能会有跟书中列举代码不一致的地方，不过大体上是保持一致的。
同时，本文虚拟机的概念和类型划分的内容主要参考了这篇 blog 的，里面讲的挺详细的。
¶ 虚拟机基本概念
虚拟机指借助软件系统对物理机器指令执行进行的一种模拟。首先，对于物理机器的执行，主要是机器从内存中 fetch 指令，通过总线传输到 CPU，然后进行译码、执行、结果存储等步骤。既然虚拟机是对其进行的一种模拟，那么也逃不过以下几个特点：
将源码编译成 VM 所能执行的字节码。
字节码格式 (指令格式)，例如三元式、四元式、波兰式等。
函数调用的相关栈结构，函数的出入口和传参方式。
指令指针，类似于物理机的指令寄存器 (EIP)。
虚拟 CPU。 instruction dispatcher。
取指：通过 IP fetch 下一条指令
译码：对指令进行翻译，得到指令类型，并且解析其操作数。
执行：跳到对应逻辑块进行执行。
¶ 栈式虚拟机和寄存器式虚拟机
虽然虚拟机的实现都逃不过以上几步，但是以具体实现来看，又分为两大类：栈式和寄存器式。
¶ 栈式虚拟机
采用栈式虚拟机的语言有 JVM、CPython 以及.Net CLR 等。 它的概念很简单，就是所有的指令执行，都是基于一个操作数栈的。你想要执行任何指令时，对不起，得先入栈，然后算完了再给我出栈。流程如下图：
总的来说，就是抽象出了一个高度可移植的操作数栈，所有代码都会被编译成字节码，然后字节码就是在玩这个栈。 好处是实现简单，移植性强。坏处是指令条数比较多，数据转移次数比较多，因为每一次入栈出栈都牵涉数据的转移。
¶ 寄存器式虚拟机
采用寄存器式的虚拟机有 lua 和 Dalvik 等。 这种实现没有操作数栈这一概念，但是会有许多的虚拟寄存器。这类虚拟寄存器有别于 CPU 的寄存器，因为 CPU 寄存器往往是定址的 (比如 DX 本身就是能存东西)，而寄存器式的虚拟机中的寄存器通常有两层含义：(1) 寄存器别名 (比如 lua 里的 RA、RB、RC、RBx 等)，它们往往只是起到一个地址映射的功能，它会根据指令中跟操作数相关的字段计算出操作数实际的内存地址，从而取出操作数进行计算；(2) 实际寄存器，有点类似操作数栈，也是一个全局的运行时栈，只不过这个栈是跟函数走的，一个函数对应一个栈帧，栈帧里每个 slot 就是一个寄存器，第 1 步中通过别名映射后的地址就是每个 slot 的地址。具体的栈帧可以参考后文讲 CallInfo 时的栈帧图。 好处是指令条数少，数据转移次数少。坏处是单挑指令长度较长。
具体来看，lua 里的实际寄存器数组是用 TValue 结构的栈来模拟的，这个栈也是 lua 和 C 进行交互的虚拟栈。 lua 里的字节码叫做 opcode，本文正文将对 "源码 -> 字节码生成 -> 字节码执行" 这整个流程进行介绍，并对其中的关键函数和数据结构进行源码级别的剖析。
¶ 关键函数和结构分析
luaL_dofile：包含了 luaL_loadfile 和 lua_pcall 两个步骤，分别对应了函数的解析和执行阶段。
luaL_loadfile：会调用具体的 parser，对 lua 文件进行进行词法和语法分析，把 source 转化成 opcode，并创建 Proto 结构保存该 opcode 和该函数的元信息。 Proto 结构如下：
该结构基本涵盖了 parse 阶段该函数的所有分析信息。主要包括以下几部分：
- 常量表。比如在函数里写了 a = 1 + 2，那这里的 1 和 2 就会放在常量表里。
- 局部变量信息。包含了局部变量的名字和它在函数中的生存周期区间 (用 pc 来衡量)。
- Upvalue 信息。包含了该 upvalue 的名字和它是否归属于本函数栈还是外层函数栈的标记。
- opcode 列表。包含了该函数实际调用的所有指令。其实就是一个 int32 类型的列表，因为 lua 虚拟机里每个指令对应一个 int32.
lua_pcall：这个函数最终会调到 luaD_call，也就是 lua 虚拟机里函数执行的主要函数。
从代码里可以看出，luaD_call 的调用分为两步：
luaD_precall：
如果是 C 函数或者 C 闭包，会直接创建单个函数调用的运行时结构 CallInfo，来完成函数的进栈和出栈。
如果是 lua 闭包，在 precall 中只会做函数调用前的准备工作，实际执行会在后一步 luaV_execute 中进行。这里的准备工作主要包括：(1) 处理 lua 的不定长参数、参数数量不够时的 nil 填充等。(2) 分配 CallInfo 结构，并填充该函数运行时所需的 base、top、opcode 等信息，注意 CallInfo 结构里还有个很关键的 func 字段，它指向栈里对应的 LClosure 结构，这个结构为虚拟机后续执行提供 upvalue 表和常量表的查询，毕竟后续对常量和 upvalue 的 read 操作，都是需要把它们从这两个表中加载到寄存器里的。
luaV_execute：这一步就是我们前面提到的 lua 虚拟机的 CPU 了，因为所有指令的实际执行都是在这个函数里完成的。它做的主要工作，就是在一个大循环里，不断的 fetch 和 dispatch 指令。每次的 fetch 就是把 pc 加 1，而 dispatch 就是一个大的 swtich-case，每个不同类型的 opcode 对应不同的执行逻辑。举一个创建 table 的例子：
在该指令中，会首先对 32 位指令进行位操作，得到该 table 的初始数组和 hash 表部分的大小 b 和 c，然后调用 luaH_new 来创建 table，最后根据 b 和 c 的值，对 table 进行 resize 操作。
另外，前面提到的 CallInfo 结构，包含了单个函数调用，lua 虚拟机所需要的辅助数据结构，它的结构如下：
下图是 lua 虚拟机在执行第二个函数时的一个栈示意图：
我们来看下 lua_State 里与之相关的几个字段：
- stack。TValue * 类型，记录了 "内存" 起始地址。
- base。TValue * 类型，记录当前函数的第一个参数位置。
- top。TValue * 类型，记录当前函数的栈顶。
- base_ci。当前栈里所有的函数调用 CallInfo 数组。
- ci。当前函数的 CallInfo。
可以发现，通过这样的组织结构，luavm 可以方便的获取到任意函数的位置以及其中的所有参数位置。而每个 CallInfo 里又记录了函数的执行 pc，因此 vm 对函数的执行可以说是了如指掌了。
¶ 指令格式
前文已经提到，lua 虚拟机的单条指令长度为 32 位。其位分布如下图所示：
这里的 OpCode，就是指令的类型，由于其只有 6 位，所有 lua 最多支持 63 种指令类型。而对于 A、B、C、Bx、sBx 等，都是该指令的参数，参数的值通常指的是一个相对偏移，例如相对于当前函数 base 的偏移，相对于常量表头的偏移等。另外，根据指令的不同，参数个数和类型也可能不同。来看几个常用的例子：
- 从变量赋值：
其实就是简单的把寄存器 RB (i) 的值赋值到寄存器 RA (i) 中去，这里的寄存器指的就是我们栈里头的某个坑位。 所以这里的 RA 和 RB 宏，都是一个栈地址获取操作，全部的定义如下：
这些宏的内部实现主要分为 2 步：
通过 GETARG_XXX (i) 从当前指令中获取参数 XXX 的值
用函数 base 或者常量表 base 去加这个参数值得到最终的栈 (寄存器) 地址。
从常量赋值：
与变量赋值唯一的不同，就是 RB 是基于常量表的偏移。
- 设置 table 字段：
这里不上代码了，这里 RK 是一个条件宏，因为我有可能是 t [a] = b, 也可能是 t1 = b，key 如果是变量 a，说明 a 肯定是在函数栈里头的变量，对应的寻址就用 RB，而如果 key 是 1，说明它不存在函数栈里头，而是在函数常量表里头，寻址就用 KB。
¶ 简单例子
我们结合一个简单的 lua chunk，decompile 一下它生成的 byte code (这里 decode 使用的也是书中介绍的 ChunkSpy 工具，目前已支持了 5.3)，从而加深理解：
我们先来看下该 chunk 对应的函数，在生成的字节码里，称之为 level 1 function：
一个函数最终的字节码，基本就包含三块：
- 常量表
- upvalue 表
- code。所有的字节指令，都是在玩常量表、upvalue 表和寄存器栈。可以结合具体的指令来理解。
我们再来看下定义在 chunk 里的 testFunc 函数，它被称为 level 2 函数，如果我在 testFunc 里还嵌套了子函数，称为 level 3 函数，以此类推。该函数的字节码与 level 1 的格式基本一致，这里就直接上图，不逐行解释了：
¶ 总结
¶ 虚拟机执行流程图
在梳理完整个 lua 虚拟机的源码分析，opcode 的生成和执行逻辑以后，我们可以上书中的一个总流程图来回顾一下：
这个图中最核心的两块，一个是 Proto 结构，它是分析阶段和执行阶段的桥梁；另一个是 OpCode 的执行，这一块可以结合前面虚拟机概念，以及 Stack-based 和 Register-based VM 的区别一起理解，包括但不限于：从 CallInfo 里 fetch 指令，指令执行时的 switch case 跳转和操作数的寻址，运行时的栈帧布局，lua_State 中的关键字段等等。 本文的总结就到这里，后面有时间可能会啃一啃书中第六章 “指令的解析与执行”，因为这两章其实联系比较紧密，到时候如果有新的收获也会同步到这边来。
本文转自 https://zhuanlan.zhihu.com/p/61888678，如有侵权，请联系删除。
Address:Department of Natural/Social Philosophy & Infomation Sciences, CHINA
Biography...
转载或引用本文时请遵守许可协议，注明出处、不得用于商业用途！
Like this article? Support the author with
