Lua学习总结

2023年10月1日更新

---

前言

工作一直在写 Lua 相关的游戏逻辑脚本，但一直没做个总结，前端时间看了一下 Lua 语言的底层逻辑，做个记录总结让以后可以拿出来翻翻看。文章有点长，可以通过索引查找对应内容。

---

Lua 的底层与编译

语言类型与区别

Lua 语言是以 C 语言为底层的脚本语言（动态语言，运行时编译），与 C 语言，C++等静态语言（静态语言，运行前编译）不同。其中 Lua 的执行主要运行流程如下：

• 程序员编辑 Lua 脚本代码，保存.lua 文件
• 语法词法分析，并生成指令集（*lua.byte 文件），属于编译过程
• Lua 虚拟机执行指令集，属于执行过程
• 输出结果

这里放一张由大佬（烟雨迷离半世殇）做的对比表格：

语言	编辑	预编译	运行时编译	执行
Lua	编写 lua 文件	无	虚拟机读取字节码并转换成虚拟机指令，汇编器编译成机器码	CPU 执行机器码
C#	编写 cs 文件	被 C#编译器编译成 dll，包含 IL 代码	CLR 使用 JIT 编译把 IL 转换成机器码	CPU 执行机器码

Lua 语言编译原理

Lua 语言的的编译，首先需要明白代码块（chunk），闭包（closure），和原型（proto）的关系。

1. chunk：代码块，一段符合 Lua 语法的代码。
2. closure：Lua 运行期间的一个实例对象，在运行期间调用的大多是一个 closure。
3. proto：（原型）Lua 语言中 closure 的原型（类似与 C++中对象声明与实例的关系），定义了有关代码段的大部分信息，包括：
   • 指令列表：包含了函数编译后生成的虚拟机指令。
   • 常量表：这个函数运行期需要的所有常量，在指令中，常量使用常量表 id 进行索引。
   • 子 proto 表：所有内嵌于这个函数的proto列表，在 OP_CLOSURE 指令中的 proto id 就是索引的这个表。
   • 局部变量描述：这个函数使用到的所有局部变量名称，以及生命期。由于所有的局部变量运行期都被转化成了寄存器id，所以这些信息只是 debug 使用。
   • Upvalue 描述：upvalue 是内嵌函数中能够访问到的外包函数中的局部变量；称为外部局部变量感觉更为贴切。在创建 closure 时（创建函数实例）初始化 Upvalue。

每一个 proto 在运行期间可以产生多个 closure 对象来表示函数实例。

**closure是运行期的对象**，与运行期关系更大；而与编译期相关的其实是proto对象，他才是编译过程真正需要生成的目标对象。

Lua 语言编译流程

• 首先调用lua_load api，将一块符合 lua 语法的代码块Chunk进行编译。
• 编译为当前的 Chunk 生成一个mainfunc proto对象，并生成一个父对象mainfunc closure对象放到当前的栈顶中，等待接下来的执行。
• Chunk 内部的每个function statement（函数语句）也都会生成一个对应的子proto，保存在外层函数的子函数列表中（proto 中有子 proto 列表）。
• 所有最外层的**function statement**的 proto 会被保存到mainfunc proto的子函数列表中。
• 按照层次依次编译，形成一个以mainfunc为根节点的 proto 树。

---

Lua 的底层数据结构

只要讲到有关于 Lua 与其他语言交互的过程的相关原理，虚拟机一定是一个不可能绕过的概念。需要注意的是不同于像**C#，java等语言使用的是基于堆栈的虚拟机**，Lua5.0 之后，**Lua语言开始改用基于寄存器的虚拟机。**首先了解一下，Lua 底层数据结构的实现方式。

C 语言的实现面向对象（注意可能存在 Lua 版本差异）

由于 Lua 的底层是通过 C 语言进行实现的，所以在设置 Lua 的数据结构的时候，也是通过 C 语言来进行实现。而主要的实现思路是：

• 定义一个公共的数据结构作为基础类型，用来存储表达数据的基础信息，其他类型由此派生（需要注意的是这个基础类型需要包含所有数据的存储方式，通过 Union 进行实现）。
• 使用联合（ union ）来将所有数据包进来，
  • Value提供基础数据的存储方式（GC 对象，指针，number 与布朗值）以及GCObject。
  • GCObject提供所有非基础类型的存储方式（table，string，closure 等），需要进行垃圾回收

struct lua_TValue {
  Value value_;
  int tt_;         //数据类型标识，新版11种（下截图），同时使用TValuefields进行表示
} TValue;

typedef union {
	GCObject *gc;    //上述所有需要进行数据回收的联合体，指针，指向联合体GCObject定义（table，thread，closure等）
	void *p;         //轻量级light，userdata，指针
	lua_CFunction f; //旧版没有这个。C语言函数
	lua_Integer i;   //整形类型，Lua5.1版本中只使用了lua_Number来进行整数和浮点数表示，但范围比int64_t类型小，之后Lua5.3扩充了整形类型来表示整数
	lua_Number n;    //默认为double类型，Lua重编译可更换
	int b;           //boolean值
}Value;

//内部包括table，string，usedata等定义
union GCObject{
	GCheader gch;
	union UTString ts;
	union Udata u;
	union Closure cl;
	struct Table h;
	struct Proto p;
	struct UpVal uv;
	struct lua_State th; /*thread*/
}

//以下不涉及数据结构表示，只是垃圾回收GC相关定义
//GCheader结构体
typedef struct GCheader{
	CommonHeader;
} GCheader;

//CommonHeader定义
#define CommonHeader GCObject *next;lu_byte tt;lu_byte marked
//next:下一个GC链表的成员
//tt：表示数据的类型，即上文图表2.1中的相关类型宏定义
//marked：GC相关标记位

综上所述，Lua 中的数据结构是基于TValue来进行表示的。需要注意的是Value中存在的指针*p 是用来存储数据结构 lightusedate（自定义类型），而GCObject中的的对象是用来存储 usedate（自定义类型）对象，分别对应上图（数据结构）中的类型 2 与类型 7。这也表示了**usedate会由Lua自动进行回收，但是lightusedate需要程序员自己进行管理**。有上述代码可以得出结论：

• number、boolean、nil、light userdata 四种类型的值是直接存在栈上元素里的，和垃圾回收无关。
• string、table、closure、userdata、thread 等存在栈上元素里的只是指针，数据在堆中他们都会在生命周期结束后被垃圾回收。
• function 类型的存储，通过上述编译原理部分内容以及GCObject的 Proto 与 Closure 进行实现

数据结构：表 Table

Lua 中的数据结构中，表 Table 是最重要的一种。在逻辑上是一个关联数组（哈希表，实际上是有一个哈希表与数组组成），可以通过任何值（除了 nil）来索引表项，表项可以存储任何类型的值。原因可以看一下存储在GCObject中的 struct 表 table 的代码结构：

typedef struct Table {
	CommonHeader;
	lu_byte flags; //元方法存在标记，标记为1，表示元方法不存在
	lu_byte lsizenode; //散列桶数组的大小的 log2(size)
	struct Table netatable; //元表
	TValue *array; //指针，指向数组表，数组表中的数据，起始键为1
	Node *node; //散列桶起始指针
	Node *lastfree; //散列桶末尾指针
	GCObject *gclist; //GC相关的链表
	int sizearray; //数组表的长度
} Table;

//table中node所包含的数据与结构（如上图表所示）
typedef union Tkey{
	struct {
		TValuefield;
		struct Node *next;
	}nk;
	Tvalue tvk;
}Tkey;

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

有上图以及逻辑代码可以看出：

• Table 的数据存储分为两个部分：所有键值在 1 与 n（上限）之间的数据存储在数组表中，非整数键值或超过键值表示范围的通过散列表进行存储。（这就是 Lua 中迭代器pair与ipair遍历的区别原理）
• 数据存储通过 TValue 类型进行存储的。这表示表中可以存放所有的 Lua 数据结构。
• 表**netatable**与标记flags实现了元表元方法的相关功能。

除了以上可以由结构看出的内容之外，有关于表的存储内容相关的部分也需要注意：

• Table 的存储的动态的，也就是数组表与散列表的大小是可以进行动态变化的（动态扩容）。
• 最初表的两个部分，都是空的，表的扩容需要 Lua 重新计算散列表与数组表的大小，找到满足一下条件的最大 n 值作为长度：**1到 n 之间至少一半的空间会被利用（避免像稀疏数组一样浪费空间）；并且 n/2+1到 n 之间的空间至少有一个空间被利用**（避免 n/2 个空间就能容纳所有数据时申请 n 个空间而造成浪费）
• Lua 并非在空间上直接增加表大小（结构非链表，不能直接增加节点），而是申请新的空间，并将元数据存放到新空间中。
• 表的两个存储部分：数组表与散列表是分开扩容的。这种混合型结构让表在作为数组使用时，有数组的优点（存储紧凑，性能高，键值隐含，不用在意哈希表的空间与计算开销）。作为散列表使用时，数组部分又常常不存在，从而节省内存空间。

PS：除了以上表述内容之外，Table 数据结构的散列表部分还使用了双重散列技术，又叫双重哈希法，有兴趣可以查找一下相关资料以及 Brent 论文提到的 HashTable 增查新方法 （地址在最后参考文献中）。

数据结构：字符串 String

字符串 String 类型与本身是结构体的 table 类似。它本身是 union 联合提结构，底层代码如下：

//长短字符串定义
#define LUA_TSHRSTR (LUA_TSTRING | (0 << 4))  /* short strings */
#define LUA_TLNGSTR (LUA_TSTRING | (1 << 4))  /* long strings */

//5.2版本，区分长短字符串
typedef struct TString {
  CommonHeader;
  lu_byte extra;  /* reserved words for short strings; "has hash" for longs */
                  /* 对于短字符串：这个标示是否是保留字，长字符串：是否已经哈希① */
  lu_byte shrlen;  /* 短字符串的长度 */
  unsigned int hash;//hash值
  union {
    size_t lnglen;  /* 长字符串的长度 */
    struct TString *hnext;  //哈希表的链表
  } u;
} TString;

typedef union UTString {
  L_Umaxalign dummy;  /* 内存对齐 */
  TString tsv;
} UTString;

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

在 Lua5.2 之后，字符串存储就被分成了两种：长字符串与短字符串。

• 短字符串存储在全局stringtable当中，相同字符串只会有一份实际数据拷贝，每份相同的 TString 对象只是存放一个 hash 值，用来索引 stringtable。
• 长字符串直接存储在 union 的hnext当中，相同字符串在内存都是单独一份数据拷贝。
• 为了避免链表中数据过多导致的可能的一次线性查找过程，除了长字符串单独存储外，还有 luaS_resize(lua_State *L,int newsize)专门进行重新的散列排列，通常在以下两种情况调用：
  • lgc.c 的 checkSizes 函数：散列桶数量太大（是实际存放的字符串 4 倍），减少为原本一倍
  • lstring.c 的 newlstr 函数：字符串数量太大（字符串数量大于桶数量，并且桶数组的数量小于 MAX_INT/2）,对桶进行翻倍扩容

数据结构：thread（叫线程，是协程）

Lua 5.0 版开始， Lua 实现不对称协程（也称为半不对称协程或不完全协程） 。

Lua 将所有关于协同程序的函数放置在一个名为“coroutine”的 table 中。

1. coroutine.create 创建一个 thread 类型的值表示新的协同程序，返回一个协同程序。
2. coroutine.status 检查协同程序的状态（挂起 suspended、运行 running、死亡 dead、正常 normal）。
3. coroutine.resume 启动或再次启动一个协同程序，并将其状态由挂起改为运行。
4. coroutine.yield 让一个协同程序挂起。
5. coroutine.wrap 同样创建一个新的协同程序，返回一个函数。

Lua 中协程是有栈的，这样我们就可以在多级函数嵌套调用内挂起（暂停执行）一个协程。解释器只是简单地将整个栈放在一边而在另一个栈上继续执行。 一个程序可以任意重启任何挂起的协程。当与栈相关的协程不可用时，垃圾回收器就回收栈空间。

---

Lua 虚拟机的跨语言调用

Lua 提供了一个虚拟栈，这个虚拟栈可以完成 Lua 语言与其他语言之间的数据交换。Lua API 本身提供了一系列接口可以让我们操作这个虚拟栈。

以下是 C 语言对虚拟栈的操作 API：

/*
** push functions (C -> stack)
*/
//数据从C语言到虚拟栈中
LUA_API void  (lua_pushnil) (lua_State *L);
LUA_API void  (lua_pushnumber) (lua_State *L, lua_Number n);
LUA_API void  (lua_pushinteger) (lua_State *L, lua_Integer n);
LUA_API void  (lua_pushlstring) (lua_State *L, const char *s, size_t l);
LUA_API void  (lua_pushstring) (lua_State *L, const char *s);
LUA_API const char *(lua_pushvfstring) (lua_State *L, const char *fmt,
                                                      va_list argp);
LUA_API const char *(lua_pushfstring) (lua_State *L, const char *fmt, ...);
LUA_API void  (lua_pushcclosure) (lua_State *L, lua_CFunction fn, int n);
LUA_API void  (lua_pushboolean) (lua_State *L, int b);
LUA_API void  (lua_pushlightuserdata) (lua_State *L, void *p);
LUA_API int   (lua_pushthread) (lua_State *L);

//数据由虚拟栈到C语言中
/*
** access functions (stack -> C)
*/
LUA_API int             (lua_isnumber) (lua_State *L, int idx);
LUA_API int             (lua_isstring) (lua_State *L, int idx);
LUA_API int             (lua_iscfunction) (lua_State *L, int idx);
LUA_API int             (lua_isuserdata) (lua_State *L, int idx);
LUA_API int             (lua_type) (lua_State *L, int idx);
LUA_API const char     *(lua_typename) (lua_State *L, int tp);

LUA_API int            (lua_equal) (lua_State *L, int idx1, int idx2);
LUA_API int            (lua_rawequal) (lua_State *L, int idx1, int idx2);
LUA_API int            (lua_lessthan) (lua_State *L, int idx1, int idx2);

// 经实测，to* 函数不会出栈
LUA_API lua_Number      (lua_tonumber) (lua_State *L, int idx);
LUA_API lua_Integer     (lua_tointeger) (lua_State *L, int idx);
LUA_API int             (lua_toboolean) (lua_State *L, int idx);
LUA_API const char     *(lua_tolstring) (lua_State *L, int idx, size_t *len);
LUA_API size_t          (lua_objlen) (lua_State *L, int idx);
LUA_API lua_CFunction   (lua_tocfunction) (lua_State *L, int idx);
LUA_API void           *(lua_touserdata) (lua_State *L, int idx);
LUA_API lua_State      *(lua_tothread) (lua_State *L, int idx);
LUA_API const void     *(lua_topointer) (lua_State *L, int idx);

以下是 Lua 对虚拟栈的操作 API：

/*
** get functions (Lua -> stack)
*/
//Lua数据入栈
LUA_API void  (lua_gettable) (lua_State *L, int idx);
LUA_API void  (lua_getfield) (lua_State *L, int idx, const char *k);
LUA_API void  (lua_rawget) (lua_State *L, int idx);
LUA_API void  (lua_rawgeti) (lua_State *L, int idx, int n);
LUA_API void  (lua_createtable) (lua_State *L, int narr, int nrec);
LUA_API void *(lua_newuserdata) (lua_State *L, size_t sz);
LUA_API int   (lua_getmetatable) (lua_State *L, int objindex);
LUA_API void  (lua_getfenv) (lua_State *L, int idx);

/*
** set functions (stack -> Lua)
*/
//Lua获取栈中数据或修改栈中数据
LUA_API void  (lua_settable) (lua_State *L, int idx);
LUA_API void  (lua_setfield) (lua_State *L, int idx, const char *k);
LUA_API void  (lua_rawset) (lua_State *L, int idx);
LUA_API void  (lua_rawseti) (lua_State *L, int idx, int n);
LUA_API int   (lua_setmetatable) (lua_State *L, int obj

除此之外，还有一系列用来控制堆栈的相关函数（栈操作）：

/*
** basic stack manipulation
*/
LUA_API int   (lua_gettop) (lua_State *L);
LUA_API void  (lua_settop) (lua_State *L, int idx);
LUA_API void  (lua_pushvalue) (lua_State *L, int idx);
LUA_API void  (lua_remove) (lua_State *L, int idx);
LUA_API void  (lua_insert) (lua_State *L, int idx);
LUA_API void  (lua_replace) (lua_State *L, int idx);
LUA_API int   (lua_checkstack) (lua_State *L, int sz);

C/C++调用 Lua

C/C++ 获取 Lua 值

1. 使用 lua_getglobal 来获取值并将其压栈。
2. 使用 lua_toXXX 将栈中元素取出（此时元素并不会出栈）转成相应的 C/C++ 类型的值。

C/C++ 调用 Lua 函数

1. 使用 lua_getglobal 来获取函数并将其压栈。
2. 如果这个函数有参数的话，就需要依次将函数的参数也压入栈。
3. 调用 lua_pcall 开始调用函数，调用完成以后，会将返回值压入栈中。
4. 取返回值，调用完毕。

Lua 调用 C/C++

Lua 可以调用 C/C++ 的函数，步骤为：

1. 将 C 的函数包装成 Lua 环境认可的函数：将被调用的 C/C++ 函数从普通的 C/C++ 函数包装成 Lua_CFunction 格式，并需要在函数中将返回值压入栈中，并返回返回值个数;
2. 将包装好的函数注册到 Lua 环境中：使用宏lua_register 调用lua_pushfunction(L,f) 和lua_setglobal(L,n)，将函数存放在一个全局 table 中。
3. 像使用普通 Lua 函数那样使用注册函数。

PS：注意 XLua 或 ToLua 都是对 Lua 虚拟机做了上层封装，方便进行相关接口调用。

---

Lua 的闭包（主要通过 upValue 实现）

Lua 的闭包定义与使用

闭包：**能够读取其他函数内部变量的函数**。

常见形式：通过调用含有一个内部函数加上该外部函数持有的外部局部变量（upvalue）的外部函数产生的一个函数实例。（外部函数+外部局部变量+内部函数（闭包函数））。

function test()
        local i=0
        return function()//尾调用
            i+=1
            return i
        end
    end
    c1=test()
    c2=test()--c1,c2是建立在同一个函数，同一个局部变量的不同实例上面的两个不同的闭包
             --闭包中的upvalue各自独立，调用一次test（）就会产生一个新的闭包

    print(c1()) -->1
    print(c1()) -->2//重复调用时每一个调用都会记住上一次调用后的值，就是说i=1了已经
    print(c2())    -->1//闭包不同所以upvalue不同
    print(c2()) -->2

由上文输出结果可知：闭包中的外部局部变量在每个函数实例中各自独立，两个实例的调用结果不会相互干扰。同时实例中的外部局部变量会被保存。

PS：由于迭代器需要保存上一次调用的状态与下一次成功调用的状态，可以正好用闭包的机制实现。（迭代器只是一个生成器，本身不带有循环）以下是迭代器的实现。

　 function list_iter(t)
            local i=0
            local n=table.getn(t)
            return function()
                i=i+1
                if i<=n then return t[i] end
            end
    end
--使用
t={10,20,90}
iter=list_iter(t)--调用迭代器产生一个闭包
	while true do
		local element=iter()
    if element==nil then break end
       print(element)
    end
end

--泛型for使用：
t={10,0,29}
for element in list_iter(t) do
		print(element)
end
--这里的list_iter()工厂函数只会被调用一次产生一个闭包函数，后面的每一次迭代都是用该闭包函数，而不是工厂函数

Lua 闭包的底层实现

在 Lua 语言运行期间，任何时候只要 Lua 执行一个 function…end 表达式， 它就会创建一个新的闭包。同时每个闭包会包含以下内容：

• 一个对函数原型proto的引用
• 一个对环境的引用（环境其实是一个表，函数可在该表中索引全局变量）
• 一个数组，数组中每个元素都是一个对 upvalue 的引用，可通过该数组来存取外层的局部变量 （upvalue 是 proto 中的一个信息，见上文）

闭包最主要的特点是能够获取其他函数内部变量。Lua 是通过upvalue 的结构来实现该功能的，对任何外层局部变量的存取都能间接地通过 upvalue 来进行。upvalue 最初指向栈中变量活跃的地方（图 4 左边） 。当离开变量作用域时（超过变量生存期时） ，变量被复制到 upvalue 中（图 4 右边） 。由于对变量的存取是通过 upvalue 里的指针间接进行的，因此复制动作对任何存取此变量的代码来说都是没有影响的。

与内层函数不同的是， 声明该局部变量的函数直接在堆栈中存取它的局部变量。通过为每个变量至少创建一个 upvalue 并按所需情况进行重复利用，保证了未决状态（是否超过生存期）的局部变量（pending vars）能够在闭包间正确地共享。为了保证这种唯一性， Lua 为整个运行栈保存了一个链接着所有正打开着的 upvalue（那些当前正指向栈内局部变量的 upvalue）的链表（图 4 中未决状态的局部变量的链表） 。当 Lua 创建一个新的闭包时，它开始遍历所有的外层局部变量，对于其中的每一个，若在上述 upvalue 链表中找到它，就重用此 upvalue，否则， Lua 将创建一个新的 upvalue 并加入链表中。注意，一般情况下这种遍历过程在探查了少数几个节点后就结束了， 因为对于每个被内层函数用到的外层局部变量来说，该链表至少包含一个与其对应的入口（upvalue） 。一旦某个关闭的 upvalue 不再被任何闭包所引用，那么它的存储空间就立刻被回收。

一个函数有可能存取其更外层函数而非直接外层函数的局部变量。 这种情况下，有可能当闭包创建时，此局部变量尚不存在。 Lua 使用 flat 闭包来处理这种情况。有了 flat 闭包，无论何时只要函数存取更外层的局部变量，该变量也会进入其直接外层函数的闭包中。这样，当一个函数被实例化时，所有进入其闭包的变量就在直接外层函数的栈或闭包中了。

---

Lua 的元表与元方法（面向对象）

在 Lua table 中我们可以访问对应的 key 来得到 value 值，但是却无法对两个 table 进行操作。因此Lua 提供了元表(Metatable)，允许我们改变table的行为，每个行为关联了对应的元方法。通俗来说，元表就像是一个“操作指南”，里面包含了一系列操作的解决方案，例如index 方法就是定义了这个表在索引失败的情况下该怎么办，add 方法就是告诉 table 在相加的时候应该怎么做。这里面的index，add 就是元方法。（上文 table 表的结构中可以看见元表与元方法标记）

面向对象的实现

--基类Account
Account = {balance = 0}

function Account:new (o)
	o = o or {}
	setmetatable(o, self)//设置元表为自身
	self.__index = self//设置__index元方法为自身
	return o
end

function Account:deposit (v)
	self.balance = self.balance + v
end

function Account:withdraw (v)
	if v > self.balance then error"insufficient funds" end
	self.balance = self.balance - v
end

--子类SpecialAccount
--此时代表SpecialAccount是Account的一个实例，即继承了Account所有内容
SpecialAccount = Account:new()

--SpecialAccount从Account继承了new方法
--new执行时，self指向SpecialAccount
--s的metable，__index是SpecialAccount
s = SpecialAccount:new{limit = 1000.00}//s继承了SpecialAccount

--在s中找不到deposit域，会到SpecialAccount找，然后到Account中找
s:deposit(100.00)
--------------------------------------------------------------------
--根据上面的描述，我们就可以在SpecialAccount中重写Account方法
function SpecialAccount:withdraw (v)
	if v - self.balance >= self:getLimit() then
		error"insufficient funds"
	end
	self.balance = self.balance - v
end

function SpecialAccount:getLimit ()
	return self.limit or 0
end

--调用方法 s:withdraw(200.00)，Lua 不会到 Account 中查找
--因为它第一次就在 SpecialAccount 中发现了新的 withdraw 方法
--由于 s.limit 等于 1000.00（记住我们创建 s 的时候初始化了这个值）
--程序执行了取款操作，s 的 balance 变成了负值
s:withdraw(200.00)

---

Lua 语言的 GC 算法

两种常见的垃圾回收算法

• 自动引用计数(Automatic Reference Counting)算法（****ARC 算法****）
  • 对每一个对象保存一个整形的引用计数属性，用来记录对象被引用的情况，当记录对象被引用数维 0 时，将会被 GC 进行回收。
  • 实现简单，判定效率高，回收没有延迟
  • 单独的存储计数器字段，增加了存储空间的开销；每次赋值需要更新存储计数器增加了时间开销；无法处理循环引用问题（致命）
  • 解决方法（Java）：可达性分析（不可达对象不等于无引用对象，最少要分析标记两次）
    
• **标记-清除（Mark - Sweep）算法**
  • 当堆中的有效内存空间被耗尽时，停止整个程序，进行标记工作与清除工作
    • 标记：Collector从根节点开始遍历，标记所有被引用对象。（一般在对象的 Header 中记录为可达对象）
    • 清除：Collector对堆内存进行从头到尾的线性遍历，发现没有标记为可达对象的对象将其回收
  • 效率低，GC 时需要停止整个用户进程，用户体验差，清理出的内存不连续没需要维护一个空闲链表

Lua 的 GC 原理与算法设计

• Lua 语言的 GC 算法采用标记-清除（Mark - Sweep）算法
• 在 Lua5.1 之前，Lua 的 GC 过程是一次性不可打断的过程，采用的 Mark 算法是双色标记算法，黑色不被回收，白色被回收。但是如果在 GC 过程的回收阶段中，加入新的对象，不论标记成什么颜色都不对，所以在后来被改进
• Lua5.1 之后采用了分布回收（增量 GC 的实现）以及三色增量标记清除算法
  更新之后的节点主要分为三种：
  • 黑色节点：已经完全扫描过的节点。
  • 灰色节点：在扫描黑色节点时候初步扫描到，但是还未完全扫描的 obj，这类 obj 会被放到一个待处理列表中进行逐个完全扫描。
  • 白色节点：还未被任何黑色节点所引用的节点(因为一旦被黑色节点引用将被置为黑色或灰色)。这里白色又被进一步细分为cur white和old white，lua 会记录当前的cur white颜色，每个节点新创建的时候都是cur white，lua 会在 mark 阶段结束的时候翻转这个cur white的位，从而使得这之前创建的白色节点都是old的，在 sweep 阶段能够得到正确释放。

GC 的主要流程如下：

为每一个新创建的节点设置为cur white（当前白色）
//初始化阶段
遍历root根节点的引用对象，将white（所有白色）设置成灰色，放入灰色节点链表中
//标记阶段（存在引用屏障，保证黑色节点不指向白色节点，灰色是屏障）
循环扫描灰色链表中的元素，将其置为黑色，然后扫描与该元素关联的其他元素，白色置灰加入灰色节点链表
结束回收阶段，将所有cur white的节点设置成old white的节点（保证这些节点都是要被回收的，回收阶段新加入的白色节点不回收）
//回收阶段
（可能存在新的白色节点加入，设置为cur white）
遍历所有对象，回收所有old white节点

---

2023年9月27日补充说明：

由于白色节点分为cur white与old white两种，任何新加入的白色节点都是cur white。只有在标记阶段最后才会将还存在的cur white修改为old white。由于Lua5.1之后采用的分布回收的GC算法，导致在GC的任何过程中都有可能存在新的内存申请，导致产生新的白色节点并且是cur white类型。如果是在回收阶段，可以不做理会，因为回收阶段只会回收所有old white类型的白色节点，但是如果是在标记阶段，则有可能存在新加入的白色节点处在已经遍历过的位置（黑色节点的父对象或子对象→没有加入灰色链表），从而不会被遍历，使得新加入的节点cur white在标记阶段结束时被修改为old white类型，导致新申请的内存被回收。

为了处理以上的这个问题，Lua主要采用了2种barrier机制，避免新申请的白色节点被错误释放：

1. 前向barrier：将被黑色节点引用的白色节点置为黑色或灰色，例如，当表table（黑）新增元表metatable（白）时，会立即将元表置灰
2. 反向barrier：将引用白色节点的黑色节点重新置为灰色，例如，当表table（黑）新增一对键值key_value（白）时，立即将表table置灰

---

Lua 语言的基础写法

指路：Lua 教程 | 菜鸟教程 (runoob.com)

---

参考文献与学习资料

• 探索 Lua5.2 内部实现:编译系统(1) 概述_yuanlin2008 的博客-CSDN 博客
• Lua5.0 原理探究 | 登峰造极者，殊途亦同归。 (lfzxb.top)
• The Implementation of Lua5.0.pdf (codingnow.com)
• Lua 跨语言调用 - 知乎 (zhihu.com)
• Brent 论文提到的 HashTable 增查新方法 地址：https://maths-people.anu.edu.au/~brent/pd/rpb013.pdf
• Lua 相关 - 随笔分类 - 天山鸟 - 博客园 (cnblogs.com)
• https://link.zhihu.com/?target=https%3A//blog.csdn.net/v_xchen_v/article/details/77249332
• 《Lua 的设计与实现》
• 《Lua5.3 王桂林》