深入浅出Lua虚拟机
作者:郑小辉 | 腾讯 游戏客户端开发高级工程师
写在前面:本文所有的文字都是我手工一个一个敲的,以及本文后面分享的Demo代码都是我一行一行码的,在我之前已经有非常多的前辈研究过Lua虚拟机了,所以本文很多思想必然是踏在这些巨人的肩膀上的。
本文标题是”深入浅出Lua虚拟机”,其实重点在浅出这两字上。毕竟作者的技术水平有限。但是听说名字要起的屌一点文章才有人看,故而得名。
谨以此文奉献给那些对Lua虚拟机有兴趣的人。希望本文能达到一个抛砖引玉的效果。
Lua的执行流程:
Lua代码的整个流程:
如下图所示:程序员编码lua文件->语法词法分析生成Lua的字节码文件(对应Lua工具链的Luac.exe)->Lua虚拟机解析字节码,并执行其中的指令集->输出结果。
蓝色和绿色的部分是本文所试图去讲的内容。
词法语法分析:
我不准备讲Lua的所有词法分析过程,毕竟如果浪费太多时间来写这个的话一会策划同学要提刀来问我需求的开发进度如何了,所以长话短说,我就根据自己对Lua的理解,以某一个具体的例子来做分析:
Lua代码块:
If a < b then a = c end
这句话咱们程序员能看懂,可是计算机就跟某些男程序员家里负责貌美如花的老婆一样,只知道这是一串用英文字符拼出来的一行没有任何意义的字符串而已。
为了让计算机能够读懂这句话,那么我们要做的第一件事情就是分词:既然你看不懂。我就先把一句话拆成一个一个单词,而且我告诉你每个单词的含义是什么。
分词的结果大概长下面这样:
分词结果 类型(意义)
if Type_If (if 关键字)
a Type_Var (这是一个变量)
< Type_OpLess(这是一个小于号)
b Type_Var(这是一个变量)
then Type_Then(Then关键字)
a Type_Var (这是一个变量)
= Type_OpEqual(这是一个等号)
c Type_Var(这是一个变量)
end Type_End(End关键字)
好了。现在计算机终于明白了。原来你写的这行代码里面有9个字,而且每个字的意思我都懂了。所以现在问题是,计算机理解了这句话了吗?
计算机依然不理解。就好像“吃饭”这句话,计算机理解了 “吃”是动词,张开嘴巴的意思。“饭”是名词,指的米饭的意思。但是你把吃饭放在一起,计算机并不知道这是“张开嘴巴,把饭放进嘴里,并且咽到胃里”的意思。因为计算机只知道“张开嘴巴”和“米饭”两件事,这两件事有什么联系,计算机并不能理解。有人会说了:简单:吃+其他字 这种结构就让计算机笼统的理解为把后一个词代表的东西放进嘴巴里的意思就好了啊?这种情况适合”吃饭”这个词,但是如果这样你让计算机怎么理解“吃惊”这个词呢?所以这里引出下一个话题:语义解析。
关于语义解析这块,如果大家想要了解的更深入,可以去了解一下AST(抽象语法树)。然而对于我们这个例子,我们用简单的方式模拟着去理解就好了。
对于Lua而言,每一个关键字都有自己特别的结构。所以Lua的关键字将成为语义解析的重点。我们现在涉及到的if这个例子:我们可以简单的用伪代码表述这个解析过程:
对于if语句我们可以抽象成这种结构:
If condition(条件表达式) then dosth(语句块) end
所以对if语句块进行解析的伪代码如下:
ReadTokenWord();
If(tokenWord.type == Type_If) then
ReadCondition() //读取条件表达式
ReadThen() //读取关键字then
ReadCodeBlock() //读取逻辑代码块
ReadEnd() //读取关键字End
End
所以为了让计算机理解,我们还是得把这个东西变成数据结构。
因为我只是做一个Demo而已,所以我用了先验知识。也就是我假定我们的If语句块逻辑结构是这样的:
If 小于条件表达式 then 赋值表达式 End
所以在我的Demo里转成C++数据结构就是IfStateMent大概是这样:
OK,所以现在,我们整个词法语法分析都做完了。但是真正的Lua虚拟机并不能执行我们的ifStateMent这种东西。Lua源码里的实现也是类似这种TokenType 和 结构化的 if Statement whileStatement等等,并且Lua没有生成完整的语法树。Lua源码的实现里面,它是解析一些语句,生成临时的语法树,然后翻译成指令集的。并不会等所有的语句都解析完了再翻译的。语义解析和翻译成指令集是并行的一个过程。贴一个源码里面关于语义解析的部分实现:
OK,现在咱们已经把我们程序员输入的Lua代码变成了一个数据结构(计算机能读懂)。下一步我们要把这个数据结构再变成Lua虚拟机能认识的东西,这个东西就是 Lua 指令集!
至于转换的过程,对于我们这个例子,大概是这样的:
If a < b then a = c end
先理解条件 a<b:一种基于寄存器的指令设计大概是这样的:
a,b均为变量。假定我们的可用的寄存器索引值从10(0-9号寄存器都已经被占用了)开始:又假定我们有一个常量索引表:0号常量:字符’a’,1号常量:字符串’b’。那么a<b可以被翻译为这样:
- LoadK 10,0 :将_G[ConstVar[0]]载入10号寄存器: R[10] = _G[“a”]
- LoadK 11,1 :将_G[ConstVar[1]]载入11号寄存器: R[11] = _G[“b”]
- LT 10,11 : 比较R[10]<R[11]是否成立,如果成立,则跳过下一条指令(++PC),否则执行下一条指令。LT后面跟着的一条指令必然是JMP指令。就是如果R[10]<R[11]成立,则不执行JMP,直接执行JMP后面的一条指令(a=c的语句块对应的指令集),否则直接跳过下面的一个语句块(跳过a=c的赋值过程)。
同理,继续进行a=c的翻译等等。
所以If a < b then a = c end在我写的demo里面最后被翻译成了:
OK,我们现在大概明白了从Lua代码怎么变成指令集的这件事了。
现在我们来具体看一下Lua5.1的指令集:
Lua的指令集是定长的,每一条指令都是32位,其中大概长这样:
每一条指令的低六位 都是指令的指令码,比如 0代表MOVE,12代表Add。Lua总共有37条指令,分别是MOVE,LOADK,LOADBOOL,LOADNIL,GETUPVAL,GETGLOBAL,GETTABLE,
SETGLOBAL,SETUPVAL,SETTABLE,NEWTABLE,SELF,ADD,SUB,MUL,DIV,MOD,POW,
UNM,NOT,LEN,CONCAT,JMP,EQ,LT,LE,TEST,TESTSET,CALL,TAILCALL,RETURN,FORLOOP,
TFORLOOP,SETLIST,CLOSE,CLOSURE,VARARG.
我们发现图上还有iABC,iABx,iAsBx。这个意思是有的指令格式是 OPCODE,A,B,C的格式,有的指令是OPCODE A,BX格式,有的是OPCODE A,sBX格式。sBx和bx的区别是bx是一个无符号整数,而sbx表示的是一个有符号的数,也就是sbx可以是负数。
我不打算详细的讲每一条指令,我还是举个例子:
指令编码 0x 00004041 这条指令怎么解析:
0x4041 = 0000 0000 0000 0000 0100 0000 0100 0001
低六位(0~5)是opcode:000001 = 1 = LoadK指令(0~37分别对应了我上面列的38条指令,按顺序来的,0是Move,1是loadk,2是loadbool.....37是vararg)。LoadK指令格式是iABC(C没用上,仅ab有用)格式。所以我们再继续读ab。
a = 低6~13位 为 00000001 = 1所以a=1
b = 低14~22位 为000000001 = 1所以b=1
所以0x4041 = LOADK 1, 1
指令码如何解析我也在demo里面写了,代码大概是这样:
那么Lua文件经过Luac的编译后生成的Lua字节码,Lua字节码文件里面除了包含指令集之外又有哪些东西呢?当然不会像我上面的那个词法语法解析那个demo那么弱智拉。所以下面我们就讲一下Lua字节码文件的结构:
Lua字节码文件(*.lua.bytes)包含了:文件头+顶层函数:
文件头结构:
顶层函数和其他普通函数都拥有同样的结构:
所以我们是可以轻松自己写代码去解析的。后文提供的Demo源码里面我也已经实现了字节码文件的解析。
Demo中的例子是涉及到的Lua源代码以及最终解析字节码得到的信息分别是:
OK,本文现在就剩最后一点点东西了:Lua虚拟机是怎么执行这些指令的呢?
大概是这样的:
While(指令不为空)
执行指令
取下一条要执行的指令
End
每一条指令应该怎么执行呢???如果大家还有印象的话,咱们前文语义解析完之后转指令集是这样的:
a < b
- LoadK 10,0 :将_G[ConstVar[0]]载入10号寄存器: R[10] = _G[“a”]
- LoadK 11,1 :将_G[ConstVar[1]]载入11号寄存器: R[11] = _G[“b”]
- LT 10,11 : 比较R[10]<R[11]是否成立,如果成立,则跳过下一条指令(++PC),否则执行下一条指令。LT后面跟着的一条指令必然是JMP指令。就是如果R[10]<R[11]成立,则不执行JMP,直接执行JMP后面的一条指令(a=c的语句块),否则直接跳过下面的一个语句块(跳过a=c的赋值过程)。
那当然是指令后面的文字就已经详细的描述了指令的执行逻辑拉,嘿嘿。
为了真正的执行起来,所以我们在数据结构上设计需要 1,寄存器:2,常量表:3,全局变量表:
为了能执行我们demo里面的例子:
我实现了这段代码涉及到的所有指令
insExecute[(int)OP_LOADK] = &LuaVM::LoadK;
insExecute[(int)OP_SETGLOBAL] = &LuaVM::SetGlobal;
insExecute[(int)OP_GETGLOBAL] = &LuaVM::GetGlobal;
insExecute[(int)OP_ADD] = &LuaVM::_Add;
insExecute[(int)OP_SUB] = &LuaVM::_Sub;
insExecute[(int)OP_MUL] = &LuaVM::_Mul;
insExecute[(int)OP_DIV] = &LuaVM::_Div;
insExecute[(int)OP_CALL] = &LuaVM::_Call;
insExecute[(int)OP_MOD] = &LuaVM::_Mod;
insExecute[(int)OP_LT] = &LuaVM::_LT;
insExecute[(int)OP_JMP] = &LuaVM::_JMP;
insExecute[(int)OP_RETURN] = &LuaVM::_Return;
以Add为例:
bool LuaVM::_Add(LuaInstrunction ins)
{
//R(A):=RK(B)+RK(C) :::
//Todo:必要的参数合法性检查:如果有问题则抛异常
// 将ins.bValue代表的数据和ins.cValue代表的数据相加的结果赋值给索引值为ins.aValue的寄存器
luaRegisters[ins.aValue].SetValue(0, GetBK(ins.bValue) + GetBK(ins.cValue));
return true;
}
下面是程序的运行效果截图:
看完整个过程,其实可以思考这个问题:为什么Lua执行效率会远远低于C程序?
个人愚见:
1,真假寄存器:Lua指令集涉及到的寄存器是模拟的寄存器,其实质还是内存上的一个数据。访问速度取决于CPU对内存的访问速度。而C程序最后可以用win32指令集or Arm指令集来执行。这里面涉及到的寄存器EBX,ESP等都是CPU上面的与非门,其访问速度=CPU的频率(和cpu访问内存的速度对比简直一个天上一个地上)。
2,指令集运行的平台:Lua指令集运行的平台是Lua虚拟机。而C程序指令集运行的直接是硬件支持的。
3,C里面的数据直接对应的就是内存地址。而Lua里面的数据对应的是一个描述这个数据的数据结构。所以隔了这么一层,效率也大打折扣了。
4,比如Lua的Gc操作等等这些东西都是C程序不需要去做的。。。。
OK,最后献上我写的这个demo的源代码:这份源代码是我在清明节在家的时候瞎写的。也就是说代码并没有经过耐心的整理,而且清明节有人找我出去喝酒,导致我有很长一段时间都处于“我艹快点码完我要出去喝了”这种心不在焉的状态,所以有些编码格式和结构设计都处处能看到随性的例子~毕竟只是一个demo嘛。人生在世,要有佛性,随缘就好!如果各位真的想进一步理解关于Lua虚拟机的东西,那么我推荐诸位有空耐着性子去读一读Lua虚拟机的源代码~
最后,诚挚感谢所有看到了最后这句话的同学。谢谢你们耐着性子看完了一个技术菜鸡的长篇废话。