王科杰

Jack's Notes

0%

Lua源码学习

发表于 分类于 Valine：

lua虚拟机

阅读源代码的次序

首先、阅读外围的库是如何实现功能扩展的，
然后、阅读 Lua 的具体实现。
之后、可以开始了解 Lua VM 的实现。
接下来就是分别理解函数调用、返回，string，metatable，table实现
debug模块是一个额外的设施、
最后是parse 等等编译相关的部分。
垃圾收集将是最难的部分，可能会花掉最多的时间去理解细节。Lua GC 的源码剖析

虚拟机核心功能

文件 作用
lua.c 可执行main函数入口
lapi.c C语言接口
ldebug.c Debug接口
ldo.c 函数调用、栈管理
lfunc.c 函数原型及闭包管理
lgc.c 垃圾回收机制
lmem.c 内存管理
lobject.c 对象操作函数
lopcodes.c 虚拟机字节码定义
lstate.c 全局状态机 管理全局信息
lstring.c 字符串池
ltable.c 表类型的相关操作
ltm.c 元方法
lvm.c 虚拟机
lzio.c 输入流接口

源代码解析和预编译

文件 作用
lcode.c 代码生成器
ldump.c 序列化预编译的Lua字节码
llex.c 词法分析器
lparse.c 解析器
lundump.c 还原预编译的字节码

内嵌库

文件 作用
lauxlib.c 库编写用到的辅助函数库
lbaselib.c 基础库
ldblib.c Debug库
linit.c 内嵌库的初始化
liolib.c IO库
lmathlib.c 数学库
loadlib.c 动态扩展库管理
loslib.c OS库
lstrlib.c 字符串库
ltablib.c 表处理库

外部符号的前缀指示其来自的模块：

luaA_-lapi.c
luaB_-lbaselib.c
luaC_-lgc.c 垃圾回收部分
luaD_-ldo.c 函数的运行流程：函数调用及返回
luaE_-lstate.c 虚拟机的当前状态
luaF_-lfunc.c function实现
luaG_-ldebug.c
luaH_-ltable.c table实现
luaI_-lauxlib.c
luaK_-lcode.c
luaL_-lauxlib.c / h，linit.c（公共函数）
luaM_-lmem.c 内存管理
luaO_-lobject.c 不同的数据类型
luaP_-lopcodes.c 虚拟机的行为是由一组 opcode 控制的
luaS_-lstring.c string实现
luaT_-ltm.c 元表
luaU_-lundump.c
luaV_-lvm.c 虚拟机对 opcode 的解析和运作
luaX_-llex.c
luaY_-lparser.c
luaZ_-lzio.c 带缓冲的流处理
lua_-lapi.c / h + luaconf.h，debug.c
luai_-luaconf.h
luaopen_-luaconf.h +库（lbaselib.c，ldblib.c，liolib.c，lmathlib.c，
loadlib.c，loslib.c，lstrlib.c，ltablib.c）

结构体/类型

Value结构体 

1
2
3
4
5
6
7
8
9
10
/*
** Union of all Lua values
*/
typedef union Value {
  struct GCObject *gc;    /* collectable objects */
  void *p;         /* light userdata */
  lua_CFunction f; /* light C functions */
  lua_Integer i;   /* integer numbers */
  lua_Number n;    /* float numbers */
} Value;

TValue结构体 

1
2
3
4
5
6
7
8
9
10
/*
** Tagged Values. This is the basic representation of values in Lua:
** an actual value plus a tag with its type.
*/

#define TValuefields	Value value_; lu_byte tt_

typedef struct TValue {
  TValuefields;
} TValue;

GCObject

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
** Common Header for all collectable objects (in macro form, to be
** included in other objects)
*/

#define CommonHeader	GCObject *next; lu_byte tt; lu_byte marked


/*
** Common type has only the common header
*/
struct GCObject {
  CommonHeader;
};

可回收的类型,都继承自GCObject

  • TString
  • Udata
  • Proto
  • Closure
  • Table

TString的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
** Header for string value; string bytes follow the end of this structure
** (aligned according to 'UTString'; see next).
*/
typedef struct TString {
  CommonHeader;
  lu_byte extra;  /* reserved words for short strings; "has hash" for longs */
  lu_byte shrlen;  /* length for short strings */
  unsigned int hash;
  union {
    size_t lnglen;  /* length for long strings */
    struct TString *hnext;  /* linked list for hash table */
  } u;
} TString;

Udata定义

1
2
3
4
5
6
7
8
9
10
11
/*
** Header for userdata; memory area follows the end of this structure
** (aligned according to 'UUdata'; see next).
*/
typedef struct Udata {
  CommonHeader;
  lu_byte ttuv_;  /* user value's tag */
  struct Table *metatable;
  size_t len;  /* number of bytes */
  union Value user_;  /* user value */
} Udata;

Proto定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
** Function Prototypes
*/
typedef struct Proto {
  CommonHeader;
  lu_byte numparams;  /* number of fixed parameters */
  lu_byte is_vararg;
  lu_byte maxstacksize;  /* number of registers needed by this function */
  int sizeupvalues;  /* size of 'upvalues' */
  int sizek;  /* size of 'k' */
  int sizecode;
  int sizelineinfo;
  int sizep;  /* size of 'p' */
  int sizelocvars;
  int linedefined;
  int lastlinedefined;
  TValue *k;  /* constants used by the function */
  Instruction *code;  /* opcodes */
  struct Proto **p;  /* functions defined inside the function */
  int *lineinfo;  /* map from opcodes to source lines (debug information) */
  LocVar *locvars;  /* information about local variables (debug information) */
  Upvaldesc *upvalues;  /* upvalue information */
  struct LClosure *cache;  /* last-created closure with this prototype */
  TString  *source;  /* used for debug information */
  GCObject *gclist;
} Proto;

Closure分为两种，Lua闭包和C闭包，定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
** Closures
*/

#define ClosureHeader \
	CommonHeader; lu_byte nupvalues; GCObject *gclist

typedef struct CClosure {
  ClosureHeader;
  lua_CFunction f;
  TValue upvalue[1];  /* list of upvalues */
} CClosure;

typedef struct LClosure {
  ClosureHeader;
  struct Proto *p; //lua函数的原型指针
  UpVal *upvals[1];  /* list of upvalues */
} LClosure;

Table定义：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */
  lu_byte lsizenode;  /* log2 of size of 'node' array */
  unsigned int sizearray;  /* size of 'array' array */
  TValue *array;  /* array part */
  Node *node;
  Node *lastfree;  /* any free position is before this position */
  struct Table *metatable;
  GCObject *gclist;
} Table;

从面向对象的角度分析的话，可以认为这5种内部基础类型，都继承自GCObject。
创建一个内部对象，使用同一个的接口函数luaC_newobj (lua_State *L, int tt, size_t sz) 参数说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
** create a new collectable object (with given type and size) and link
** it to 'allgc' list.
*/
GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
  global_State *g = G(L);
  GCObject *o = cast(GCObject *, luaM_newobject(L, novariant(tt), sz));
  o->marked = luaC_white(g); //标记这个对象是white
  o->tt = tt;  //类型
  o->next = g->allgc; //新创建的对象放到gclist的最前面
  g->allgc = o;
  return o;
}

#define luaM_newobject(L,tag,s)	luaM_realloc_(L, NULL, tag, (s))

/*
** generic allocation routine.
*/
void *luaM_realloc_ (lua_State *L, void *block, size_t osize, size_t nsize) {
  void *newblock;
  global_State *g = G(L);
  size_t realosize = (block) ? osize : 0; //新建的话，block都是NULL
  lua_assert((realosize == 0) == (block == NULL));
#if defined(HARDMEMTESTS)
  if (nsize > realosize && g->gcrunning)
    luaC_fullgc(L, 1);  /* force a GC whenever possible */
#endif
  newblock = (*g->frealloc)(g->ud, block, osize, nsize);  //调用的就是l_alloc
  if (newblock == NULL && nsize > 0) {
    lua_assert(nsize > realosize);  /* cannot fail when shrinking a block */
    if (g->version) {  /* is state fully built? */
      luaC_fullgc(L, 1);  /* try to free some memory... */
      newblock = (*g->frealloc)(g->ud, block, osize, nsize);  /* try again */
    }
    if (newblock == NULL)
      luaD_throw(L, LUA_ERRMEM);
  }
  lua_assert((nsize == 0) == (newblock == NULL));
  g->GCdebt = (g->GCdebt + nsize) - realosize;
  return newblock;
}

GCObjcet类型

通过统一的接口luaC_newobj函数，创建的内部对象都是GCObjcet类型。如果要正常使用，还需要做一次转换，LUA对于这种抽象结构转换为具体对象结构的行为，封装了一套宏函数:

1
2
3
4
5
6
7
8
9
10
11
/* macros to convert a GCObject into a specific value */
#define gco2ts(o)  \
	check_exp(novariant((o)->tt) == LUA_TSTRING, &((cast_u(o))->ts))
#define gco2u(o)  check_exp((o)->tt == LUA_TUSERDATA, &((cast_u(o))->u))
#define gco2lcl(o)  check_exp((o)->tt == LUA_TLCL, &((cast_u(o))->cl.l))
#define gco2ccl(o)  check_exp((o)->tt == LUA_TCCL, &((cast_u(o))->cl.c))
#define gco2cl(o)  \
	check_exp(novariant((o)->tt) == LUA_TFUNCTION, &((cast_u(o))->cl))
#define gco2t(o)  check_exp((o)->tt == LUA_TTABLE, &((cast_u(o))->h))
#define gco2p(o)  check_exp((o)->tt == LUA_TPROTO, &((cast_u(o))->p))
#define gco2th(o)  check_exp((o)->tt == LUA_TTHREAD, &((cast_u(o))->th))

推荐一本书<自己动手实现lua虚拟机>

lundump文件

字节流结构 二进制 chunk

头部header

{
签名， “\x1bLua” (0x1b4c7561)
版本， 0x53
格式(0x00) 0x00
LUAC_DATA 0x1993 0d 0a
cint 4
sizet 8
lua虚拟机指令 4
lua_integer 8
lua_number 8
lua_int 0x5678（判断大小端）
lua_num 370.5 (浮点数格式)

}

函数原型

  1. 源文件名
    以@开头的是源码编译而来，以=开头的，是标准库而来
  2. 起止行号
    两个cint,主函数为0
  3. 固定参数个数
  4. 是否是Vararg函数
  5. 寄存器数量
    MaxStackSize, 因为lua是一种栈结构,可以按索引访问，模拟寄存器
  6. 指令表
  7. 常量表
  8. Upvalue表 {Instack,Idx}两个字节
  9. 子函数原型表
  10. 行号表. 和指令表中的指令一一对应
  11. 局部变量表
    LocVar
    {
    VarName  String
StartPC   Uint32
EndPC       Uint32
    }
  12. Upvalue名列表

行号表、局部变量表、Upvalue名列表 都是调试信息

解析二进制 chunk

//头部header校验
lundump.h 里面看 checkHeader函数

//函数原型
LoadCode(S, f);
LoadConstants(S, f);
LoadUpvalues(S, f);
LoadProtos(S, f);
LoadDebug(S, f);

指令集

lopcodes文件

  1. 基于栈的虚拟机(Stack Based)
    Java、.NET、CLR、Python、ruby、Yarv;
    PUSH/POP操作栈，指令集大，平均长度短
  2. 基于寄存器(Resigter Based), lua_5.0以后
    需要把寄存器地址编码进指令，平均长度长

lua采用定长指令集（大约47条指令）， 每条指令4字节32位，6位Opcode操作码，26位操作数Operand

指令编码格式

编码模式

按照高26位区分，四种mode， iABC、iABx、iAsBx、iAx
iABC可以携带ABC三个操作数8+9+9比特
iABx携带 A、Bx，8+18
iAx Ax，26
iAsBx As、Bx 8+18

操作码

6位，最多64条指令，参看opcodes

操作数

A主要用来表示目标寄存器索引，OpArgN、U、R、K

指令表

LUAI_DDEF const lu_byte luaP_opmodes[NUM_OPCODES]

指令解码

CREATE_ABC、CREATE_ABx、CREATE_Ax
sBx是有符号整数，18位。 Excess-K编码模式，Offset Binary. x-K. K取最大无符号一半

Lua API

主要以Lua_开头的。60多个luaL_开头的辅助函数，付主函数建立在基础函数之上

Lua栈

Lua栈是宿主语言和Lua语言沟通的桥梁，api基本上也都是操作这个所谓的栈结构lua_state

Lua数据类型

8种， nil、boolean、number、string、table、function、thread、userdata

虚拟机雏形 Lua运算符

程序计数器(Program Counter, 简称PC)记录正在执行的指令。

表

lua表是一个关联数组, 包含哈希表和数组两个部分

函数调用

参数

  • 固定参数个数，未传递则nil，多传递则忽略
  • 返回值，外部接受几个，多退少补nil的策略，作为函数参数，如数覆盖

load,加载二进制chunk或者源码。把被调函数推入栈顶
call,

交互 lua <-> 其它语言

lua注册表，lua_status里
lua全局环境 G， GlobalTable

闭包和Upvalue

  1. 一等函数，java不支持，可作为参数传递，返回等
  2. 变量作用域。 动态作用域、静态作用域
  3. 闭包。 词法作用域捕获了非局部变量的嵌套函数

Upvalue是lua里面的术语，就是闭包内部捕获的非局部变量。
嵌套函数，捕获外围的外围的函数的变量，外围函数会捕获更外围的局部变量。扁平闭包。

_ENV — 全局环境 隐式的Upvalue

元变成 Metaprogram

值类型默认没有元表，元表nil。 字符串提供了默认元表。

迭代器

迭代器模式.
数值for循环是借助FORPREP和FORLOOP两条指令完成
通用for循环，TFORCALL和TFORLOOP两条指令

异常和错误处理

Lua语法和编译器

  • 词法分析
  • 抽象语法树
  • 语法分析
  • 代码生成

词法分析

字符流(源码)，以’token’的形式分解
类型注释、关键字、标识符、字面量、运算符、分隔符等
lua会忽略 \n \r \t \v \f 空格等空白字符
忽略注释

token -> { … ; : . } .etc

抽象语法树 AST

计算机编程语言一般使用上下文无关文法(Context-free Grammar, CFG)描述，而CFG一般使用巴科斯范式(Backus-Naur Form, BNF)或者其扩展EBNF(Extended BNF)书写

语法分析

YACC、Bison、ANTLR、JavaCC

代码生成

辅助API和基础库

希望对您有所帮助，您的支持将是我莫大的动力！