Lua 源码分析

14 Apr 2022 | code, lua

之前看得比较多的都是OOP的源码，像C这种面向过程的代码看得不多，这次正好学习一下面向过程的最佳实践方法。

宏没有类型系统，再加上各种缩写，看得头痛

内存管理

Lua允许在创建虚拟机时（调用lua_newstate），提供自定义内存分配函数，接口如下：void * (*lua_Alloc) (void *ud, void *ptr, size_t osize, size_t nsize)。当编写自定义的函数时，接口的实参为我们提供了以下信息（或者说要求）：

这个分配函数会在虚拟机分配内存、释放内存、扩展内存时被调用，根据不同操作传入的实参不同，来判断应该进行哪种处理。默认的内存分配函数是l_alloc，封装了::free和::realloc:

static void *l_alloc (void *ud, void *ptr, size_t osize, size_t nsize) {
  (void)ud;
  (void)osize;
  if (nsize == 0) {
    free(ptr);
    return NULL;
  }
  else
    return realloc(ptr, nsize);
}

内存分配模块（lmem.h/c）相关的接口如下：

基本类型

多态的实现方式

// 1. 这种方式在python源码也见过
struct base { int type };
struct derive { 
    struct base info; 
    ...
};
// 2. 使用union
struct deriveA { ... };
struct deriveB { ... };
struct base {
    int type;
    union {
        deriveA d_a;
        deriveB d_b;
    } value;
};

每个需要GC的类型都会以CommonHeader宏作为起始，宏定义如下：#define CommonHeader GCObject *next; lu_byte tt; lu_byte marked。定义中成员的含义：next下一个链表成员、tt数据类型、markedGC标志位。

用GCHeader包装CommonHeader。用意何在？答：没有的话，会把三个成员都直接放到GCObject中，三个成员变互斥了

用GCObject联合体把所有需要GC的类型囊括，为什么需要gch这个字段，调用具体类型的CommonHeader不也可以？

union GCObject {
    GCHeader gch;
    union TString ts;
    ...
};

用Value联合体把所有类型囊括。用TValue封装Value，CommonHeader的tt和TValuefields的tt重复了？

#define TValuefields Value value; int tt
typedef struct lua_TValue {
  TValuefields;
} TValue;

字符串

字符串使用union进行定义，并加入union { double u; void *s; long l;};。这是为了对齐。

typedef union TString { 
    union { double u; void *s; long l;};
    struct {
        CommonHeader;
        ...
    } tsv;
} TString;

Lua有个字符串对象池（stringtable global_State::strt，用开链表实现），里面的对象没被引用则被回收，关键字除外。stringtable实现如下：

typedef struct stringtable {
  GCObject **hash;
  lu_int32 nuse;  /* number of elements */
  int size;       
} stringtable;

字符串相关接口如下:

长字符串逐位计算哈希的方法可能带来Hash Dos的风险，在5.2.1时引入随机种子进行修复。

表

表定义如下：

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

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

typedef struct Table {
  CommonHeader;
  TValue *array;  
  Node *node;
  ...
} Table;

整数数据可以存在array指向的数组中，也可以存在node指向的开放寻址法哈希表中。非整数类型全部存在哈希表中。TKey中的nk主要是用来当Key的哈希值相同时，开链用。

相关接口如下：

元方法

typedef struct global_State {
  struct Table *mt[NUM_TAGS];  /* metatables for basic types */
  TString *tmname[TM_N];  /* array with tag-method names */
} global_State;

typedef struct Table {
  ...
  lu_byte flags;
  struct Table *metatable;
} Table;

metatable的键值对是<TString,TValue>。常用的方法名位于global_State::tmname数组，该数组被luaT_init赋值。Table::flags按位来标明该表是否有某个常用的方法。当要查找某元表是否有某个方法，会先调用fasttm进行查找。

异常

为了能够实现嵌套的异常，用lua_longjmp封装了::jmp_buf，由previous串起了异常链。而lua_State::errorJmp提供一个全局变量的作用，用它来记录当前的恢复点。

struct lua_longjmp {
  struct lua_longjmp *previous;
  luai_jmpbuf b;
  volatile int status;  /* error code */
};

struct lua_State {
  ...
  struct lua_longjmp *errorJmp;  /* current error recover point */
};

try和catch实现方式如下：

#if defined(__cplusplus)
#define LUAI_THROW(L,c)	throw(c)
#define LUAI_TRY(L,c,a)	try { a } catch(...) \
	{ if ((c)->status == 0) (c)->status = -1; }
#else
/* default handling with long jumps */
#define LUAI_THROW(L,c)	longjmp((c)->b, 1)
#define LUAI_TRY(L,c,a)	if (setjmp((c)->b) == 0) { a }
#endif

提供了luaD_throw和luaD_rawrunprotected接口来搭配使用异常，它们的主要工作是对lua_longjmp *lua_State::errorJmp使用try和catch的宏

State

Lua虚拟机对象就是一个lua_State，它代表一个线程，有独立的数据栈和调用链。同一个虚拟机的所有执行线程共享一个global_State

数据栈

typedef TValue *StkId;

struct lua_State {
  ...
  StkId stack_last; 
  StkId stack;  
  int stacksize;
};

调用栈

CallInfo保存正在调用函数的运行状态，调用栈以CallInfo数组的方式存储在lua_State::base_ci中。

struct lua_State {
  ...
  CallInfo *end_ci; 
  CallInfo *base_ci; 
  int size_ci; 
};

每个CallInfo有相关成员指明该函数在运行时，数据在数据栈的位置：

typedef struct CallInfo {
  StkId base; 
  StkId func; 
  StkId	top; 
  const Instruction *savedpc;
  ...
} CallInfo;

同时lua_State也有一些成员指明当前正在运行的CallInfo以及当前栈的位置

struct lua_State {
  ...
  StkId top;  
  StkId base;
  CallInfo *ci; 
  const Instruction *savedpc; 
};

UpValue

upvalue原始值还在数据栈上，则这个upvalue是open的，否则是close的

typedef struct UpVal {
  ...
  TValue *v; 
  union {
    TValue value; 
    struct {
      struct UpVal *prev;
      struct UpVal *next;
    } l;
  } u;
} UpVal;

当处于代码块中，UpVal::v指向数据栈上的对象，UpVal::u::l为串联UpValue的指针。当离开代码块，栈上对象被销毁，由UpVal::u::value保存原数据栈上的对象，UpVal::v指向UpVal::u::value

闭包

闭包有两种：

typedef struct CClosure {
  ClosureHeader;
  lua_CFunction f;
  TValue upvalue[1];
} CClosure;

typedef struct LClosure {
  ClosureHeader;
  struct Proto *p;
  UpVal *upvals[1];
} LClosure;

typedef union Closure {
  CClosure c;
  LClosure l;
} Closure;

CClosure的upvalue是直接存放在结构体中的。

struct lua_State {
  ...
  GCObject *openupval;  /* list of open upvalues in this stack */
};

typedef struct global_State {
  ...
  UpVal uvhead;  /* head of double-linked list of all open upvalues */
} global_State;

lua_State::openupval 是当前线程的open upvalues单向链表（链表顺序按照数据栈从高到低？），global_State::uvhead是全部open upvalues的双向链表

lua闭包有两种生成方法，一种在虚拟机运行的过程中被动态构造出来的。这时，闭包需引用的upvalue都在当前的数据栈上。利用luaF_findupval可以把数据栈上的值转换为upvalue。另一种 TODO：yunfeng

函数调用

虚拟机

寄存器式的虚拟机，指令格式及含义见lopcodes.*。

部分字节码的执行逻辑如下：

local t
if a == b then
  t = true
else
  t = false
end

// 1: EQ 1 0 1
// 2: JMP 0 1 ; to 4
// 3: LOADBOOL 0 0 1
// 4: LOADBOOL 0 1 0

有了一个参数让pc++，可以避免额外插入一条JMP指令。

TODO

UserData

定义同TString，有个metatable表记录元方法

typedef union Udata {
  L_Umaxalign dummy; 
  struct {
    CommonHeader;
    struct Table *metatable;
    ...
  } uv;
} Udata;

luaS_newudata 分配空间并初始化，数据和字符串一样，都是紧跟在Udata后面

当C/C++想调用lua中一个值时，lua将数值压入lua虚拟栈中，然后通过lua提供api来读取，当C/C++想向lua传入一个值时，C++通过lua提供的api将数值压入lua虚拟栈中，lua便可进行调用，通过这样交互完成相互调用。也就是说，C/C++并没有直接和lua数据完全的绝对互通，而是通过这个lua虚拟栈作桥梁。一旦数据进入lua那边，就是lua自己维护了，包含lua自己产生的变量或者管理的数据，，C++要想访问只能先让lua将其放到栈上再通过lua api来访问

我们向Lua注册的C函数应该是这种格式的：typedef int (*lua_CFunction) (lua_State *L)

TODO

GC

使用三色增量标记清除算法，白色表示该对象没有被GC标记，灰色表示被GC访问过但其引用的其他对象还没有被访问，黑色表示对象已经被GC访问且其引用的其他对象也被访问。

其中白色又被细分为双白色，即当前白色和非当前白色，两种白色的状态交替使用，只有对象时当前白色才会被回收。

前端

一遍扫描就生成字节码

环境

调试

协程

参考

Older · View Archive (37)

LevelDB 源码分析

Newer

In Search of an Understandable Consensus Algorithm