关于lua以及luajit

0x00 What is lua

lua简介

Lua 是一种轻量小巧的脚本语言，用标准C语言编写并以源代码形式开放，其设计目的是为了嵌入应用程序中，从而为应用程序提供灵活的扩展和定制功能。

嵌入式环境使用的脚本语言

lua采用的虚拟机

根据指令获取操作数的方式不同，可以把虚拟机分为基于栈的虚拟机和基于寄存器的虚拟机。

JVM与python使用基于栈的虚拟机，该虚拟机是在当前栈中获取和保存操作数。例如：a=b+c，其相应指令为：

push b
push c
add
pop a

其实现起来比较简单，每条指令占用的存储空间也小。但是，对于运算而言（例如加法），这需要4条指令才能完成，这会对效率有很大影响。

Lua目前采用基于寄存器的虚拟机，例如：a=b+c，其相应指令为：

add a b c

提高了效率。但是，每条指令占用的存储空间也增加了，在编译器设计上也增加了复杂度

lua语言本身

类型定义

Lua 是动态类型语言，变量不要类型定义,只需要为变量赋值。值可以存储在变量中，作为参数传递或结果返回。

Lua有8种类型：nil、boolean、number、string、function、userdata、thread 和 table，他们都在src/lua.h中定义。

string对应LUA_TSTRING

function对应LUA_TFUNCTIOIN。

而userdata比较特殊，它对应LUA_TLIGHTUSERDATA 和 LUA_TUSERDATA。

LUA_TLIGHTUSERDATA是由 Lua 外部的使用者来完成，LUA_TUSERDATA则是通过 Lua 内部来完成，也就是说，LUA_TLIGHTUSERDATA是通过用户来维护其生命周期。

数据类型	描述
nil	这个最简单，只有值nil属于该类，表示一个无效值（在条件表达式中相当于false）。
boolean	包含两个值：false和true。
number	表示双精度类型的实浮点数
string	字符串由一对双引号或单引号来表示
function	由 C 或 Lua 编写的函数
userdata	表示任意存储在变量中的C数据结构
thread	表示执行的独立线路，用于执行协同程序
table	Lua 中的表（table）其实是一个”关联数组”（associative arrays），数组的索引可以是数字、字符串或表类型。在 Lua 里，table 的创建是通过”构造表达式”来完成，最简单构造表达式是{}，用来创建一个空表。

Lua采用了标记清除式（Mark and Sweep）GC算法，算法简述：

标记：每次执行GC时，先以若干根节点开始，逐个把直接或间接和它们相关的节点都做上标记；

清除：当标记完成后，遍历整个对象链表，把被标记为需要删除的节点一一删除即可。

string、function、userdata、thread 和 table都需要gc。需要 gc 的数据类型，都会有一个 CommonHeader 成员。

1 2	//lobject.h #define CommonHeader GCObject *next; lu_byte tt; lu_byte marked

其中，next是指向下一个GC链表的成员，tt表示数据类型、marked为GC相关的标志位。

Lua的基本数据表示方式是type + union的方式，根据不同类型映射到union的不同结构上面, 统一的表示结构lua_TValue：

struct lua_TValue{
    Value value_; 	//实际存储的值
    int tt; 		//存储当前数据类型
}TValue;

typedef union Value {
  GCObject *gc;    /* collectable objects */
  void *p;         /* light userdata */
  int b;           /* booleans */
  lua_CFunction f; /* light C functions */
  lua_Integer i;   /* integer numbers */
  lua_Number n;    /* float numbers */
} Value;

union GCObject{
    GCheader gch;
    union TString ts;
    union Udata u;
    union Closure cl;
    struct Table h;
    struct Proto p;
    struct UpVal uv;
    struct lua_State th;
};

其中，gc 表示需要垃圾回收的一些值，如 string、table 等；p 表示 light userdata，不会被 gc。

Table

Table是Lua中唯一表示数据结构的类型，他是一个混合数据结构。其中的函数环境 (env)、元表 (metatable)、模块 (module) 和注册表 (registery) 等都是通过 table 表示。Lua-5.0 后，table 包含一个哈希表部分和一个数组部分，哈希部分发生冲突就用链表解决。

typedef struct Table {
  ...
  unsigned int sizearray;
  TValue *array;
  lu_byte lsizenode;
  Node *node;
  ...
} Table;

typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;

typedef union TKey {
  struct {
    TValuefields;
    int next;
  } nk;
  TValue tvk;
} TKey;

array、sizearray 用于表示数组部分及其大小，node、lsizenode 表示哈希部分与大小。

当查找table中的数据时，其逻辑如下：

（1）对于字符串类型，通过 luaH_getstr() 先获得相应字符串在哈希表中的链表，然后遍历这个链表，采用内存地址比较字符串，若找到则返回相应的值，否则 nil 。

（2）如果是整型，则调用 luaH_getint() 查找，如果 key 的值小于等于数组大小，则直接返回相应的值，否则去哈希表中去查找。

（3）对应其他类型，统一调用 getgeneric()，也就是计算 hash 值并在链表中查找，通过 luaV_equalobj() 对各种类型进行比较。

lua解释器体系结构

其中，stack 成员用于指向栈底，而 base 指向当前正在执行的函数的第一个参数，而 top 指向栈顶。寄存器实际上是栈上元素的别名。pc 来指向下一条要执行的指令。

Lua字节码

Lua 的指令使用 32bit 的无符号整型表示，可以通过luac编译成字节码。

例如，查看lua5.1编译后的字节码文件，文件头部12字节为：1b4c 7561 5100 0104 0804 0800。其中，1b4c 7561为\033Lua；51表示Lua版本为5.1；00为保留位；01表示字节序为小端；04表示int大小为4字节；08表示size_t的大小为8字节；04表示内部指令的大小为4字节；08代表lua中数字的大小为8字节。

执行流程

Lua虚拟机最后会调用luaV_execute()函数，其主要逻辑就是取指令、递增PC、根据指令操作码进行switch...case...。

其他

（1）Lua 语言本身是支持闭包（closure）的（把几个值和函数绑定在一起），在 Lua 中，这些值被称为 upvalues；而且，每个函数和一个函数环境（env）绑定。

（2）Lua编译系统的工作就是将符合语法规则的代码转换成可运行的闭包，闭包对象是 Lua 运行中一个函数的实例对象。

（3）每个闭包都对应着自己的 proto，而在运行期间，一个 proto 可以产生多个闭包来代表这个函数实例。

lua中重要的API

常用API函数

API name	Description
void lua_pushcclosure (lua_State, lua_CFunction, int)	注册C函数，fn为要注册的函数指针
#define luaL_dofile (luaL_loadfile(L, filename) or lua_pcall(L, 0, LUA_MULTRET, 0))	加载并运行指定的文件
int luaL_loadfilex (lua_State, const char, const char)	把文件加载为 Lua 代码，代码块的名字为name
int lua_load (lua_State,lua_Reader,void,const char,const char)	加载一段 Lua 代码块，但不运行它。把一个编译好的代码块作为一个 Lua 函数压到栈顶。否则，压入错误消息参数 reader 。 chunkname是一个字符串，标识了正在加载的块名。mode是一个字符串，指定如何编译数据块。可能取值为：（1）”b”：该块是预编译的二进制块。（2）”t”：预编译的文本块。
const char *lua_pushfstring (lua_State, const char, …)	把一个格式化的字符串压栈，然后返回这个字符串的指针，类似于sprintf
const char *lua_tolstring (lua_State, int, size_t)	将给定索引处的 Lua 值转换为一个 C 字符串，它还把字符串长度赋值到 *len中。

LuaU_undump函数

此函数用于lua文件头的检测。

LClosure *luaU_undump(lua_State *L, ZIO *Z, const char *name) {
    LoadState S;
    ...
    S.L = L;
    S.Z = Z;
    checkHeader(&S);
	...
}

#define LUA_SIGNATURE "\x1bLua"
#define LUAC_FORMAT   0
// LUA_VERSION_MAJOR为主版本号，LUA_VERSION_MINOR为子版本号
// 例如Lua版本为5.3，则 LUAC_VERSION=83=0x53
#define MYINT(s)      (s[0]-'0')
#define LUAC_VERSION  (MYINT(LUA_VERSION_MAJOR)*16+MYINT(LUA_VERSION_MINOR))


static void checkHeader (LoadState *S) {
    checkliteral(S, LUA_SIGNATURE + 1, "not a");  // 检查头部签名
    if (LoadByte(S) != LUAC_VERSION)              // 检查luac版本号
    	error(S, "version mismatch in");
    if (LoadByte(S) != LUAC_FORMAT)               // 检查格式号，一般为0
    	error(S, "format mismatch in");
    checkliteral(S, LUAC_DATA, "corrupted");      // 检查头部的6-11字节
    checksize(S, int);                            // 检查头部的12-16字节
    checksize(S, size_t);
    checksize(S, Instruction);
    checksize(S, lua_Integer);
    checksize(S, lua_Number);
    if (LoadInteger(S) != LUAC_INT)
    	error(S, "endianness mismatch in");
    if (LoadNumber(S) != LUAC_NUM)
    	error(S, "float format mismatch in");
}

Lua文件读取&解析的调用链示例

其中，luaX_next主要用于语法TOKEN的分割，而statlist主要根据分割出来的TOKEN，组装成语法块语句，最后将语句组装成语法树。

0x01 luajit

Luajit将原生Lua进行了扩展，使它支持JIT方式编译运行，Luajit有如下特点：

（1）运行时编译。

（2）兼容AOT编译。

（3）引入了中间表示IR。

Luajit文件格式

参考：https://github.com/feicong/lua_re/blob/master/lua/lua_re3.md

Luajit官方并没有直接给出Luajit字节码文件的格式文档，但可以通过阅读Luajit源码中加载与生成Luajit字节码文件的函数，来单步跟踪分析出它的文件格式，这两个函数分别是lj_bcread()与lj_bcwrite()

从这两个函数调用的bcread_header()、bcread_proto()、bcwrite_header()、bcwrite_proto()等子函数名可以初步了解到，Luajit字节码文件与Luac一样，将文件格式分为头部分信息Header与函数信息Proto两部分。

Luajit字节码文件的Header部分为了与Luac命名上保持一致，这里将其描述为GlobalHeader，它的定义如下：

typedef struct {
    char signature[3];
    uchar version;
    GlobalHeaderFlags flags;
    if (!is_stripped) {
        uleb128 length;
        char chunkname[uleb128_value(length)];
    }
} GlobalHeader;

上述header解释如下：

（1）luajit字节码文件的头3个字节必须为0x1b4c4a，这是它的Magic Number（signature）。

（2）version是luajit字节码文件的版本号，占1个字节。

（3）flags是文件的标志位，采用uleb128编码（占用的字节码与数据的实际大小相关）。其中包含3个字段：

（a）FLAG_IS_BIG_ENDIAN表示大端序还是小端序。

（b）FLAG_IS_STRIPPED表示是否去除调试信息。如果包含调试信息，即FLAG_IS_STRIPPED没有被置位，那么在GlobalHeader中会多出两个字段：length（字符串长度），chunkname（Luajit文件的源文件名字符串）。

（c）FLAG_HAS_FFI表示是否有外部函数接口（FFI信息）。

typedef enum {
    FLAG_IS_BIG_ENDIAN = 0b00000001,
    FLAG_IS_STRIPPED = 0b00000010,
    FLAG_HAS_FFI = 0b00000100
} FLAG;

Luajit字节码文件的Proto中有ProtoHeader字段，它描述了Proto的头部信息，如下所示：

typedef struct {
    uleb128 size;
    if (uleb128_value(size) > 0) {
        ProtoFlags flags;
        uchar arguments_count;
        uchar framesize;
        uchar upvalues_count;
        uleb128 complex_constants_count;
        uleb128 numeric_constants_count;
        uleb128 instructions_count;
        if (!is_stripped) {
            uleb128 debuginfo_size;
            uleb128 first_line_number;
            uleb128 lines_count;
        }
    }
} ProtoHeader;

上述ProtoHeader解释如下：

（1）size字段是标识了从当前字段开始，整个Proto结构体的大小。

（2）flas是ProtoHeader的标志位，其使用的ProtoFlags是一个uchar类型，取值如下：

typedef enum {
    FLAG_HAS_CHILD = 0b00000001,
    FLAG_IS_VARIADIC = 0b00000010,
    FLAG_HAS_FFI = 0b00000100,
    FLAG_JIT_DISABLED = 0b00001000,
    FLAG_HAS_ILOOP = 0b00010000
} PROTO_FLAG;

各取值的含义如下：

（a）FLAG_HAS_CHILD标识当前proto是一个子函数，也就是闭包（closure）。举个例子来理解一下：

function Create(n) 
	local function foo1()
		print(n)
        local function foo2()
            n = n + 10 
		    print(n)
            local function foo3()
                n = n + 100
                print(n)
            end
        end
	end
	return foo1,foo2,foo3
end
f1,f2,f3 = Create(1000)
f1()

上述代码中，最外层的Create()向内，每个function都包含一个Closure。在Luac文件格式中，每个Proto都有一个Protos字段，它用来描述Proto与Closure之间的层次信息，Proto采用从外向内的递归方式进行存储。而LUAJIT则采用线性的从内向外的同级结构进行存储，PROTO与CLOSURE之前的层级关系使用FLAGS字段的FLAG_HAS_CHILD标志位进行标识，当FLAGS字段的FLAG_HAS_CHILD标志位被置位，则表示当前层的PROTO是上一层PROTO的CLOSURE。上述代码在Luajit的文件结构如下：

struct Luajit lj;
    struct GlobalHeader header;
    struct Proto proto[0];  //foo3()
    struct Proto proto[1];  //foo2()
    struct Proto proto[2];  //foo1()
    struct Proto proto[3];  //Create()
    struct Proto proto[4];  //Full file
    struct Proto proto[5];  //empty

从存局中可以看出，最内层的foo3()位于Proto的最外层，它与LUAC的布局是相反的，而proto[4]表示了整个Lua文件，它是Proto的最上层。最后的proto[5]，它在读取其ProtoHeader的size字段时，由于其值为0，而中止了整个文件的解析。即它的内容为空。

（b）FLAG_IS_VARIADIC标识了当前Proto是否返回多个值，上面的代码中，只有Create()的flags字段会对该标志置位（因为只有它有返回值）。

（c）FLAG_HAS_FFI标识当前Proto是否有通过FFI扩展调用系统的功能函数。

（d）FLAG_JIT_DISABLED标识当前Proto是否禁用JIT，对于包含了具体代码的Proto，它的值通常没有没有被置位，表示有JIT代码。

（e）FLAG_HAS_ILOOP标识了当前Proto是否包含了ILOOP与JLOOP等指令，编译器好进行优化。

（3）arguments_count表示当前Proto有几个参数。

（4）framesize标识了Proto使用的栈大小。

（5）upvalues_count、complex_constants_count、numeric_constants_count、instructions_count分别表示UpValue个数、复合常数个数、数值常数个数、指令条数等信息。

UpValue：当一个函数引用了一个外部函数的局部变量时，这个局部变量就成为了 Upvalue。Upvalue 会在堆上被创建并持续存活，直到没有任何函数引用它为止。当一个函数被垃圾回收时，它所引用的 Upvalue 也会被垃圾回收。

（6）如果包含调试信息，那么会有debuginfo_size、first_line_number、lines_count，分别表示DebugInfo结构体占用的字节大小、当前Proto在源文件中的起始行、当前Proto在源文件中所占的行数。

下面就到了proto的主体部分：

（1）指令Instruction数组，每条指令长度与Luac一样，占用32位，但使用的指令格式完全不同。

（2）常量信息，主要包含3个数组，分别是upvalues、complex_constants、numeric_constants数组。complex_constants可以保存字符串、整型、浮点型、TAB表等信息。

（3）debuginfo调试信息。分为LineInfo与VarInfos两部分，前者是存储的一条条的行信息，后者是局部变量信息，包括变量类型、名称、以及它的作用域起始地址与结束地址。

其他

Luajit的线性结构解析起来比Luac简单，只需要按序解析Proto，直接读取到字节0结束即可。

0x02 Luajit字节码

Luajit的字节码设计与原生Lua有很多不同，最终到的效果是：字节码的编码实现更加简单，执行效率也比原生LUAC指令更加高效。

Lua指令的参考文档为：http://wiki.luajit.org/Bytecode-2.0

每条指令都为32位，指令分为opcode与操作数两部分。Lua原生指令是不对齐的，即不同的域（A、B、C等）不一定为8位或16位，而Luajit的每个域都为8位或16位。

Luajit的指令由5部分组成，分别为：指令名称name、3个操作数域ma/mb/mc、指令类型mt。

指令名称例如：ISLT、ADDVV、USETS、TGETV。它们有些有前后缀，后缀有：

V variable slot。变量槽。
S string constant。字符串常量。
N number constant。数值常量。
P primitive type。原始类型。
B unsigned byte literal。无符号字节字面量。
M multiple arguments/results。多参数与返回值。

前缀有：

T table。表。
F function。函数。
U UpValue。上值。
K constant。常量。
G global。全局。

那么，USETS代表为UpValue设置字符串值，TGETV代表获取一个表结构中指定索引的数据。