Lua源码阅读:数据结构与栈

承接上篇虚拟机概述,解析函数执行流程。

### 数据结构与栈:

每个Lua 虚拟机对应一个 lua_State 结构体,它使用 TValue 数组来模拟栈,其中包括几个与栈相关的成员:

  • stack:栈数组的起始位置
  • base:当前函数栈的基地址
  • top:当前栈的下一个可用位置

这些成员的初始化操作在 stack_init 函数中完成。

然而 lua_State 里面存放的是一个 lua 虚拟机的全局状态,当执行到一个函数时,需要有对应的数据结构来表示函数相关的信息,这个数据结构就是 CallInfo,这个结构体中同样有 top、base这两个与栈相关的成员。

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  
** case, the actual 'func' value is saved in field 'extra'.   
** When a function calls another with a continuation, 'extra' keeps  
** the function index so that, in case of errors, the continuation  
** function can be called with the correct top.  
*/  
typedef struct  {  
  StkId func;  /* function index in the stack */  
  StkId	top;  /* top for this function */  
  struct  *previous, *next;  /* dynamic call link */  
  union {  
    struct {  /* only for Lua functions */  
      StkId base;  /* base for this function */  
      const Instruction *savedpc;  
    } l;  
    struct {  /* only for C functions */  
      lua_KFunction k;  /* continuation in case of yields */  
      ptrdiff_t old_errfunc;  
      lua_KContext ctx;  /* context info. in case of yields */  
    } c;  
  } u;  
  ptrdiff_t extra;  
  short nresults;  /* expected number of results from this function */  
  lu_byte callstatus;  
} CallInfo;  

—|—

在 lua_State 中,有一个 base_ci 的 CallInfo 数组,存储的就是 CallInfo 的信息,而另一个 ci 成员,指向的就是当前函数的 CallInfo 指针。

在调用函数之前,一般会调用 luaD_precall 函数:

  1. 保存当前虚拟机执行的命令 savedpc 到当前 CallInfo 的 savedpc 中。此处保存下来是为了后面调用完毕之后恢复执行。
  2. 分别计算出待调用函数的 base、top 值,这些值的计算依赖于函数的参数数量。
  3. 从 lua_State 的 base_ci 数组中分配一个新的 CallInfo 指针,存储前面两步计算出来的信息,切换到这个函数准备调用。

### 命令的解析:

首先,分析阶段要用到的数据结构是 FuncState。这个结构体用于在语法分析时保存解析函数之后相关的信息,根据其中的 prev 指针成员来串联起来。对于下面的 Lua 代码:

1  
2  
3  
4  
5  
-- 最外层 FuncState fs1  
local function a()	-- 函数 a 的 FuncState fsa  
	local function b()	-- 函数 b 的 FuncState fsb  
	end  
end  

—|—

涉及到三个 FuncState 指针,一层一层嵌套包围,其中fs1是 fsa 的父指针:

在 FuncState 结构体中,有一个成员 Proto *f,它用来保存这个 FuncState 解析命令后生成的命令,其中除了自己的,还包括内部嵌套的子函数的:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
/* state needed to generate code for a given function */  
typedef struct FuncState {  
  Proto *f;  /* current function header */  
  struct FuncState *prev;  /* enclosing function */  
  struct LexState *ls;  /* lexical state */  
  struct BlockCnt *bl;  /* chain of current blocks */  
  int pc;  /* next position to code (equivalent to 'ncode') */  
  int lasttarget;   /* 'label' of last 'jump label' */  
  int jpc;  /* list of pending jumps to 'pc' */  
  int nk;  /* number of elements in 'k' */  
  int np;  /* number of elements in 'p' */  
  int firstlocal;  /* index of first local var (in Dyndata array) */  
  short nlocvars;  /* number of elements in 'f->locvars' */  
  lu_byte nactvar;  /* number of active local variables */  
  lu_byte nups;  /* number of upvalues */  
  lu_byte freereg;  /* first free register */  
} FuncState;  

—|—

各个层次的 Proto 数据是逐层包含的,因此最外层的全局 FuncState 结构体中的 Proto 数组一定有这个全局结构中所有 Proto 的信息,也就是解析完毕之后的命令信息。

而 luaY_parser 这个函数,它是分析阶段的唯一入口函数,这个函数的返回值就是 Proto 指针,而 FuncState 等数据结构仅是用于分析过程中的临时数据结构,它们最终都是为了解析代码生成命令到 Proto 结构体服务的。

#### 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;  /* maximum stack used 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;	/* 保存分析之后生成的 OpCode 数组 */  
  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 保存 upvalue 的数组 */  
  struct LClosure *cache;  /* last created closure with this prototype */  
  TString  *source;  /* used for debug information */  
  GCObject *gclist;  
} Proto;  

—|—

### 命令格式:

lua 虚拟机的命令格式:

operation.png

首先,Lua 的命令是 32 位的:

  • Opcode:操作数
  • A、B、C:参数

不同操作数的命令格式不同、含义不同。操作数是 6 位的,所以 Lua 最多支持 2^6-1 = 31 个命令。Lua 代码中,将每个操作数及其对应的命令格式都在 lopcodes.h 中的 OpCode 枚举类型中定义。

Lua 虚拟机命令中有着不同的参数:

格式 说明
R(A) A参数作为寄存器索引,R(B)、R(C)依此类推
pc 进程计数器,这个数据用于指示当前命令的地址
Kst(n) 常量数组中的第n个数据
Upvalue(n) upvalue 数组中的第 n 个数据
Gbl[sym] 全局符号表中取名为 sym 的数据
RK(B) B 可能是寄存器索引,也可能是常量数组索引,RK(C)类似
sBx 有符号整数,用于表示跳转偏移量

在lopcodes.h 文档中还定义了每个命令的格式,以及相关的宏;这里定义了在一个命令中每个参数对应的大小和位置。

RK(B)的意思有两层,一是这个命令格式只可能作用在 OpCode 的 B、C 参数上,不会作用在参数 A 上;二是这个数据除了从函数栈获取之外,还有可能从常量数组中获取,关键在于宏 ISK 的判断。

1  
2  
/* test whether value is a constant */  

—|—

判断这个数据的第 8 位是不是 1,如果是,则认为应该从 K 数组获取数据,否则就是从函数栈寄存器中获取数据。

从寄存器中取命令是在以 R 开头的宏中,实际代码中会使用一个 base 再加上对应的地址,base 值保存的是函数栈基址:

1  
2  
3  
4  
/* to be used after possible stack reallocation */  
#define RB(i)	check_exp(getBMode(GET_OPCODE(i)) == OpArgR, base+GETARG_B(i))  
#define RC(i)	check_exp(getCMode(GET_OPCODE(i)) == OpArgR, base+GETARG_C(i))  

—|—

### 命令的执行:

命令执行的入口函数是 luaV_execute:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
void luaV_execute (lua_State *L) {  
  CallInfo *ci = L->ci;  
  LClosure *cl;  
  TValue *k;  
  StkId base;  
 newframe:  /* reentry point when frame changes (call/return) */  
  lua_assert(ci == L->ci);  
  cl = clLvalue(ci->func);  
  k = cl->p->k;  
  base = ci->u.l.base;  
  /* main loop of interpreter */  
  for (;;) {  
    Instruction i = *(ci->u.l.savedpc++);  
    StkId ra;  
    if ((L->hookmask & (LUA_MASKLINE | LUA_MASKCOUNT)) &&  
        (--L->hookcount == 0 || L->hookmask & LUA_MASKLINE)) {  
      Protect(luaG_traceexec(L));  
    }  
    /* WARNING: several calls may realloc the stack and invalidate 'ra' */  
    ra = RA(i);  
    lua_assert(base == ci->u.l.base);  
    lua_assert(base <= L->top && L->top < L->stack + L->stacksize);  

—|—

  • ci:用于保存当前命令的执行位置(以及一些其他信息,包括动态调用链的双向链表)
  • cl:当前所在的函数环境
  • base:当前函数环境的栈 base 地址
  • k:当前函数环境的常量数组

总结:

  1. 分析阶段最后的结果就是Proto结构体。在这个结构体中,code成员用于存储命令,f数组用于保存里面嵌套的函数的Proto结构体。
  2. 每个环境都有自己对应的栈,base指向这个栈的基地址,top指向这个栈的栈顶地址。取函数栈内的数据,都是以base基地址为基础地址的操作。
  3. 在虚拟机开始执行命令之前,需要把对应的命令和栈地址切换到所要执行的函数的数据上。

参考:

  1. 《Lua设计与实现》(codedump 著)
  2. Lua 源码解析

糖果

糖果
LUA教程

Lapis框架的常用处理方法

Lapis框架的常用处理方法 Continue reading

MoonScript实现选择排序

Published on February 26, 2017

MoonScript与Redis客户端

Published on January 19, 2017