Lua 解释器构建：从虚拟机到编译器

增量式标记清除算法

整个 GC 执行的过程中，大致经历以下几个阶段

• pause 阶段

  mainthread 和 global table 包含 GC 起始点，因此要将它们插入到 gray 链表中，并将它们标记为灰色，进入到 propagate 阶段

• propagate 阶段

  • 不断从 gray 链表中取出对象，然后把它从灰色变为黑色，再遍历它所引用的对象，并将其插入到 gray 链表中
  • propagate 阶段累积遍历的对象大小超过一定的字节数，本轮 GC 会被终止，等待下一次 GC 步骤开始后继续扫描 gray 链表中的对象
  • 当 gray 链表为空时，进入 atomic 阶段

• atomic 阶段

  • GC 步骤在 pause 阶段是可以被中断的，假如新建的对象被标记为黑色的对象引用，本轮 GC 就不会对其进行遍历和标记，到 sweep 阶段就会被当作不可达的对象而清除掉
  • 需要为新建对象设置屏障（barrier）
    • 向前设置屏障：直接将新创建的对象标记为灰色，放入到 gray 链表中
    • 向后设置屏障：将黑色对象标记为灰色， grayagain 链表中
  • 原子执行 atomic 阶段

• sweep 阶段

  从 allgc 链表中去除若干个对象；如果已经是本轮 GC 要被清除的 白色 ，那么它会被清除；如果不是，则标记为 另一种白，以供下一轮 GC 使用

Lua 虚拟机的字符串

• 从 Lua-5.2.1 开始，字符串就分为长字符串合短字符串。其中短字符串会进行充分的哈希运算，并进行内部优化处理；长字符串不会进行哈希运算和内部化
• 字符串内部化的本质就是为每个字符串创建唯一的实例
• 在 Lua 中，字符串 Body 长度小于或等于 40B 的是短字符串，大于 40B 的是长字符串；在 Lua-5.3 中，短字符串的大小限制由 LUAI_MAXSHORTLEN 决定，这个宏定义在 llimits.h 中定义

Lua 虚拟机的表

Lua 表的基本数据结构

// luaobject.h
typedef union lua_Value {
    struct GCObject* gc;
    void* p;
    int b;
    lua_Interger i;
    lua_Number n;
    lua_CFunction f;
} Value;

typedef struct lua_TValue {
    Value value_;
    int tt_;
} TValue;

// lua Table
typedef union TKey {
    struct {
        Value value_;
        int tt; // 用来标记 value_是什么类型
        int next;
    } nk;
    TValue tvk;
} TKey;

typedef struct Node {
    TKey key;
    TValue value;
} Node;

struct Table {
    CommonHeader;               // GC 部分
    TValue* array;              // 数组部分
    unsigned int arraysize;     // 数组大小
    Node* node;                 // hash 部分
    unsigned int lsizenode;     // hash 大小，实际大小为 2<sup>lsizenode
    Node* lastfree;             // 空闲指针
    struct GCObject* gclist;    // GC 部分
}

键值的哈希运算

Node 结构的 key 可以是任意 Lua 类型。key值是如何和哈希表的索引对应起来

• 对 key 进行哈希运算
• 根据得到的哈希值，换算成表结构 node 数组的索引值
  • index = hash_value & (2^lsizenode - 1)
• 查找元素
  • 被查找的元素 key 是 int 类型：
    • key 在数组范围之内（在 array 中查找），返回array[k - 1]
    • key 不在数组范围之内，计算哈希值（在 node 链表中查找）
  • 被查找的元素 key 不是 int 类型：key 不在数组范围之内，计算哈希值（在 node 链表中查找）

调整表的大小

• nums[i]的含义：统计 $(2^{i - 1}, 2^i]$ 区间内，所有数组索引值、哈希表key（类型为int）的哈希值位于这个区间的元素总数n

• 判断新插入的元素的 key 值是否为整数类型，如果是则对应区间总数增加 1：nums[i]++

• 完成 nums 的统计后，根据 nums 计算新的数组大小。在数组大小范围内，值不为 nil 的元素要超过数组大小的一半：

  int i = 0;
  int asize = 0;
  for (; i < 32; i++) {
      asize += nums[i];
      if (asize > pow(2, i) / 2) {
          arraysize = pow(2, i)
      }
  }

• 计算在数组大小范围内有效元素的个数，记为array_used_num

• 当数组比原来大时，扩展 原来的数组到新的大小，并将哈希表中 key 值小于等于 arraysize，且大于 0 的元素转移到数组中，并将哈希表大小调整为 $\lceil \log_2^{total - array_used_num} \rceil$，同时对每个node 重新定位

• 当数组比原来小时，缩小 原来的数组到新的大小，并将数组中 key 值超过数组大小的元素转移到哈希表中，并将哈希表大小调整为 $\lceil \log_2^{total - array_used_num} \rceil$，同时对每个 node 重新定位

Lua 中的三种函数类别

Light C Function

可以理解为普通的 C 函数，如

static int test_main(struct lua_State* L)
{
    int arg1 = (int)luaL_tointeger(L, 1);
    int arg2 = (int)luaL_tointeger(L, 2);
    printf("test main arg1:%d arg2%d \n", arg1, arg2);
    lua_pushinteger(L, arg1 + arg2);
    return 1;
}

要在 Lua 虚拟机中运行 test_main 函数，需要调用lua_pcall，其声明如下

// L 表示 Lua 线程
// narg 表示在 Lua 线程里执行的函数有多少个参数
// nresult 表示在 Lua 线程里执行的函数有多少个返回值
int lua_pcall(struct lau_State* L, int narg, int nresult);

C 闭包

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

typedef struct CClosure {
    ClosureHeader;
    lua_Function f;
    TValue upvalue[1]; // upvalue 列表
} CClosure;

一个 C 闭包和 Light C Function 函数相比，除了受 GC 托管并且拥有上值列表外，其他功能和 Light C Function 函数差不多

Lua 闭包

Lua 闭包是受 Lua 虚拟机的 GC 托管的，Lua 脚本代码经过编译生成的虚拟指令，以及其他一些编译相关的信息会存放在 LClosure 中的Proto 类型变量中

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

Proto结构

// common/luaobject.h
typedef struct Proto {
    CommonHeader;
    int is_vararg;          // 标记 Lua 函数参数列表是否为可变参，0 表示否，1 表示是
    int nparam;             // 当 is_varrag 为 0 时生效，它表示该函数参数的数量
    Instruction* code;      // Lua 函数经过编译后，生成的虚拟机指令列表
    int sizecode;           // 指明 code 列表的大小
    TValue* k               // 常量列表，如数值、字符串等
    int sizek;              // 常量列表大小
    LocVar* localvars;      // local 变量列表
    int sizelocvar;         // local 变量列表大小
    Upvaldesc* upvalues;    // upvalue 信息列表，主要记录 upvalue 的名称，以及其所在的地址，并不是 upvalue 实际值的列表
    int sizeupvalues;       // upvalue 列表大小
    struct Proto** p;       // 内嵌定义的函数列表
    int sizep;              // proto 列表长度
    TString* source;        // 脚本路径
    struct GCObjects* gclist;
    int maxstacksize;       // Proto 所对应的 Lua 函数被调用时，函数栈的最大尺寸
} Proto;

上值生成过程

上值实际上是再编译时确定（位置信息和外层函数的关联等）、在运行时生成的。用来表示上值的数据结构有两个，一个是编译时期存储上值信息的 Upvaldesc（这个结构并不存储上值的实际值，只是用来标记上值的位置信息），另一个是在运行时实际存储上值的UpVal 结构

// luaobject.h
typedef struct Upvaldesc {
    // 本函数的上值是否指向外层函数的栈（如果不是则指向外层函数的某个上值）
    int in_stack;

    // 上值在外层函数中的位置（栈的位置或 upval 列表中的位置，根据 in_stack 确定）
    int idx;

    // 上值的名称
    TString* name; 
} Upvaldesc；

// luafunc.h
struct Upval {
    // 指向外层函数的 local 变量（开放上值），或者指向自己（上值关闭时）
    TValue* v;

    // Upval 实例被引用的次数
    int refcount;

    union {
        struct {
            struct UpVal* next; .. 下一个开放上值
            int touched;
        } open;
        Tvalue value;
    } u;
}

Lua 脚本的编译信息会被存储到 Proto 结构实例中，当一个 Lua 函数的某个变量不是 local 变量时，如果希望获得它的值，实际上就要查找这个变量的位置，如果在 local 列表中找不到，则进入一下流程：

• 到自己的 Upvaldesc 列表中，根据变量名查找，如果存在则使用它，否则进行下一步；
• 到外层函数查找 local 变量，如果找到它就将它作为自己的上值，否则查找它的 Upvaldesc 表，找到就将其生成为自己的上值，否则进入更外层函数，重复这一步；
• 如果一直到顶级函数都找不到，那么表示这个上值不存在，此时需要去 _ENV 中查找