前言

基本架构

以下是Lua 5.3.5源码在src目录下的代码结构整理，分为三大部分：虚拟机****核心功能、源代码****解析和预编译、内嵌库。每个部分包含核心文件及其作用说明，便于快速理解Lua源码的组织架构。

一、虚拟机核心功能部分

负责Lua虚拟机的核心运行机制，包括内存管理、垃圾回收、字节码执行等。

文件	作用
lapi.c	提供C语言接口，实现Lua与C的交互
ldebug.c	Debug接口，支持断点、堆栈跟踪等调试功能
ldo.c	管理函数调用栈和协程栈
lfunc.c	管理函数原型（Proto）和闭包（Closure）的创建与销毁
lgc.c	垃圾回收机制（GC），包括标记-清除算法和分代回收策略
lmem.c	内存管理接口，负责动态内存分配与释放
lobject.c	对象操作函数，处理Lua中所有数据类型的通用操作（如类型判断、值转换）
lopcodes.c	定义虚拟机字节码的操作码（OpCode）及其编码格式
lstate.c	管理全局状态机（lua_State），维护运行时环境、注册表等全局信息
lstring.c	实现字符串池（String Interning），避免重复字符串的内存开销
ltable.c	表（Table）的实现，包括哈希表和数组的混合结构及元表操作
ltm.c	元方法（Metamethod）的处理，如__index、__add等运算符重载
lvm.c	虚拟机核心，解释执行字节码指令
lzio.c	输入流接口，支持从文件、字符串等源读取数据
lua.c	Lua可执行程序的入口（main函数），提供命令行交互环境

二、源代码解析和预编译部分

将Lua脚本编译为字节码，支持序列化与反序列化。

文件	作用
lcode.c	代码生成器，将抽象语法树（AST）转换为虚拟机字节码
ldump.c	序列化预编译的Lua字节码，生成.luac文件
llex.c	词法分析器，将源代码分割为Token（如标识符、关键字、数字等）
lparser.c	语法分析器，构建抽象语法树（AST）并校验语义合法性
lundump.c	还原预编译的字节码，加载.luac文件到内存

三、内嵌库部分

提供Lua标准库的实现，支持基础功能扩展。

文件	作用
lauxlib.c	辅助函数库，简化C模块开发（如参数检查、内存错误处理）
lbaselib.c	基础库，实现print()、assert()、error()等核心函数
ldblib.c	Debug库，提供debug.traceback()、debug.getlocal()等调试工具
linit.c	内嵌库初始化，注册所有标准库到全局环境
liolib.c	I/O库，实现文件读写（io.open()）、流操作（io.stdin）等
lmathlib.c	数学库，提供math.sin()、math.random()等数学函数
loadlib.c	动态扩展库管理，支持require()加载C模块
loslib.c	操作系统库，封装os.time()、os.execute()等系统调用
lstrlib.c	字符串库，支持模式匹配、格式化（string.match()、string.format()）
ltablib.c	表处理库，实现table.insert()、table.sort()等操作

总结

Lua源码设计特点：

模块化清晰：三个部分职责分离，虚拟机核心、编译器、标准库各自独立，便于维护。
轻量高效：总代码约1万行，核心虚拟机（lvm.c、lstate.c）和编译器（lparser.c、lcode.c）占主体。
可扩展性强：通过lauxlib.c和loadlib.c支持C模块动态加载，内嵌库可裁剪。

对于源码学习建议：

从入口开始：优先阅读lua.c的main函数，理解解释器初始化流程。

深入****虚拟机：结合lopcodes.c的字节码定义，分析lvm.c中的指令执行逻辑。

实践调试：通过修改ldebug.c添加自定义调试信息，观察运行时行为。

Lua的精简架构使其成为学习编译器与虚拟机设计的优秀范本，建议按“核心→编译器→库”的顺序逐步深入。

GC

版本发展

Lua在5.0版本的时候，使⽤的是“双⾊标记清除算法”，垃圾回收过程⼀旦开始就需要等待全部完成才能继续其它流程，此时如果待处理的对象很多，则会卡顿至完成处理完所有对象，极大影响程序性能。

Lua升级到5.1版本后，算法发生了很大的变化，算法优化成了“三⾊标记清除算法”，后续的版本都⼀直采⽤该算法。垃圾回收过程可以增量式的分步执⾏，不再需要等待全部执⾏完毕再执⾏后⾯的其它程序流程。但这个算法也有⼀定局限性，虽然垃圾回收过程可以分步执⾏，但这是⼀个由前往后的过程，意味着不能在处理到中间的时候⼜返回去前⾯处理新的对象，新加⼊的内存垃圾⼀定得等到本次垃圾回收过程处理完所有旧对象，下⼀次垃圾回收机制重新开始才能被处理到，所以及时性不够强。

Lua升级到5.1版本后，除了⽀持“三⾊标记清除算法”，还新增了⼀个可选择的垃圾回收算法类型“分代式算法”，该算法把对象按年龄(被垃圾回收处理的次数)分为年轻⼀代和⽼⼀代。对年轻的对象会有更多的“关爱”，会有更及时的响应，所以能解决“三⾊标记清除算法”的及时性问题。但是“分代算法”也有其局限性，就是会有⽼⼀代对象的内存****堆积和残留。所以在实际使⽤中，使⽤者可根据⾃身需求确定使⽤哪⼀种垃圾回收算法或者混合使⽤。

数据结构

Lua有两种垃圾回收算法，分别为增量式标记清除算法与分代式算法，见源码***《lstate.h》***中的枚举定义：

我们常说的GC即代表GarbageCollection，译为垃圾回收。见上图英文，KGC则代表Kindofgarbagecollection，翻译为垃圾回收类型，Lua中分为两种垃圾回收算法类型：

1）***KGC_INC：incrementalgc***，增量式算法，实现方式即为我们说到的三色标记清除算法；

2）***KGC_GEN:genrationalgc***，分代式算法。

默认的垃圾回收算法类型

若开发人员没有设置Lua的垃圾回收算法类型，则增量式三色标记清除算法类型为默认垃圾回收类型，见源码***《lstate.c》中lua_newstate***：

此函数用于创建Lua运行状态机，可理解为Lua主线程运行环境的初始化，红框部分代码g->gckind=KGC_INC即表示默认使用增量式算法。

使用默认的增量式三色标记清除算法可满足大多数Lua项目的需求，所以相对于分代式算法，大家更应该加强理解这个三色标记清除算法。

垃圾回收的基础单位-GCObject

接下来，我们就真正开始讲解Lua对象在内存中的组织与遍历形式。在Lua中，我们上层开发者使用的对象其实都是TValue类型的对象，然后这些TValue对象有些会直接存储有意义数据，有些则通过指针指向一个需要被垃圾回收机制所管理的对象，而这些被管理的对象，他们有着共同的特点，就是他们都是从GCObject类继承的子类型。

TValue:

// lobject.h
/*
** 目标值. 这是Lua中的值的基础代理: 一个准确的值加上其类型
*/
#define TValuefields	Value value_; lu_byte tt_

typedef struct TValue {
  TValuefields;
} TValue;

Value:

// lobject.h
/*
** 所有lua值的union
*/
typedef union Value {
  struct GCObject *gc;    /* 可收集对象(table，string，完整userdata类型等，所有类型查看union GCUnion) */
  void *p;         /* light userdata */
  lua_CFunction f; /* light C functions */
  lua_Integer i;   /* integer numbers */
  lua_Number n;    /* float numbers */
  /* 无用，但可避免未初始化值的警告 */
  lu_byte ub;
} Value;

上述的4个字段变量，他们都是分配于栈之中，内存回收算法不需要回收栈里面的对象。因为随着代码的执行，栈顶指针会不断移动，在上述变量脱离了作用域之后，即变量数值存储的内存地址不在当前运行的栈顶范围的时候，就等于是进行了自动的清除，因为下次栈顶指针再次移动到该位置进行写入的时候，就相当于自动对旧的内存进行了覆盖与回收。

//  Igс.c
/*
** 创建一个新的可收集对象(通过传入的type, size, offset)并且将他和‘allgc'列表链接
*/
GCObject *luaC_newobjdt (lua_State *L, int tt, size_t sz, size_t offset) {
  global_State *g = G(L);
  char *p = cast_charp(  luaM_newobject  (L, novariant(tt), sz));
  GCObject *o = cast(GCObject *, p + offset);
  o->marked = luaC_white(g);
  o->tt = tt;
    
  o->next = g->allgc;
  g->allgc = o;
     
  return o;
}


GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
  return luaC_newobjdt(L, tt, sz, 0);
}

luaM_newobject

会调用 malloc****堆内存空间的分配

1 2	//lmem.h #define luaM_newobject(L,tag,s) luaM_malloc_(L, (s), tag)

在Lua中，垃圾回收机制的作用就是帮助开发者自动清除回收这部分堆空间内存。

o->next = g->allgc; g->allgc = o;

形成了一个链表

GCObject的next字段，还有global_State的*GCObject *allgc**字段，它们的类型都是指针类型，指向*GCObject**对象

这边相当于建堆的操作堆的Root是 *GCObject allgc

// lobject.h 
/*
** 所有gc对象公共的通用header (以宏形式的形式包含在其他对象中)
** next: 下一个GCObject
** tt: 对象类型
** marked: 标记
*/
#define CommonHeader	struct GCObject *next; lu_byte tt; lu_byte marked


/* gc对象类型 */
typedef struct GCObject {
  CommonHeader;
} GCObject;

销毁

GCObject销毁在*《lgc.c》freeobj* 中根据不同数据结构去采用不同的销毁函数

不需要GC的类型

我们知道Lua总共有9种基础类型分别为：nil, boolean, lightuserdata, number, string, table, function, userdata, thread

//lua.h
/*
** 基础类型
*/
#define LUA_TNONE		(-1)

#define LUA_TNIL		0
#define LUA_TBOOLEAN		1
#define LUA_TLIGHTUSERDATA	2
#define LUA_TNUMBER		3
#define LUA_TSTRING		4
#define LUA_TTABLE		5
#define LUA_TFUNCTION		6
#define LUA_TUSERDATA		7
#define LUA_TTHREAD		8

#define LUA_NUMTYPES		9

有另外的字段进行表示

1）lightuserdata类型使用Value的void* p字段；

2）number类型对象使用Value的lua_Integer i和lua_Number n字段；

逻辑上不需要GC的

3）我们的nil对象是不需要存储任何数值的；

4）然后boolean对象会把true和false作为一种子类型，以不同标识存储在类型标识tt(typetag)中；

string,table,function,userdata,thread 都是需要GC的类型

在每一个定义的struct中都会存在一个 CommonHeader

特殊的是function类型数据结构闭包Closure的定义

我们知道分为Lua闭包和C语言闭包 都使用了 ClosureHeader

ClosureHeader 引用了CommonHeader

1
2
3

//lobject.h
#define ClosureHeader \
	CommonHeader; lu_byte nupvalues; GCObject *gclist

lua 利用了 CommonHeader 处理的数据类型

就都可以理解为都为GCObject的子类型

Mark

复习一下CommonHeader：

其中marked字段为lu_byte类型一个字节有8位

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

在分代算法中会使用marked字段的第0-2位

// lgc.h
/* 分代模式中对象年龄 */
#define G_NEW		0	/* 当前周期创建 */
#define G_SURVIVAL	1	/* 上一个周期创建 */
#define G_OLD0		2	/* 2个周期后变老 在这个周期中被标记为旧的由frw设置的屏障(屏障：用于在GC过程中保护某些对象不被错误回收，可以确保在收集器运行时，某些重要的引用关系不被破坏) marked old by frw. barrier in this cycle */
#define G_OLD1		3	/* 1个周期后变老 第一个完整周期的老对象 first full cycle as old */
#define G_OLD		4	/* really old object (not to be visited) */
#define G_TOUCHED1	5	/* 这个周期被touched的老对象 */
#define G_TOUCHED2	6	/* 上一周期被touched的老对象 */

#define AGEBITS		7  /* 所有的年龄位 (111) */

在三色标记清除算法中会有染色过程会使用marked字段的第3-5位


/*
** 位的布局使用’marked' 前3位用于分代模式的‘age'，最后一位用于测试
** 由于清除阶段是增量式的，需要防止清除阶段产生的新对象被错误回收，所以使用两种白色(一种需要被回收，一种不需要)
*/
#define WHITE0BIT	3  /* 对象是白色(type 0) */
#define WHITE1BIT	4  /* 对象是白色(type 1) */
#define BLACKBIT	5  /* 对象是黑色 */
#define FINALIZEDBIT	6  /* 对象是否有终结器(析构标记，定义了析构器的对象拥有这个析构标记，代表释放之前需要先调用__GC元方法) */

#define TESTBIT		7

触发时机

垃圾回收机制的触发时机，讲解用于触发垃圾回收，控制算法步长的债务管理算法。详细介绍算法中债务的产生方式，债务的触发方式，还有债务的偿还清算方式。

债务管理算法

通常来说，一段需要偶尔执行的逻辑需要被触发，无外乎有两种方式：

1）定时触发：使用定时器，每隔固定的时间执行一次；

2）事件驱动：每当特定事件发生的时候执行一次。

在Lua中，采用的是第二种，即事件驱动的触发方式，具体的实现使用的是本文将要介绍的债务管理算法，债务增加事件就是驱动逻辑的事件，当债务增加到大于0时，就会触发GC

typedef struct global_State {
            l_mem totalbytes;  /* 当前已经分配内存的总字节数 - GCdebt */
            l_mem GCdebt;  /* 尚未由收集器补偿的已分配字节(GC的债务(负数)，当债务 > 0 时，触发GC) */
            lu_mem GCestimate;  /* 正在使用的非垃圾内存预估 */
}global_State;

l_mem为size_t的别名，可理解为整型，表示内存字节数

1）*l_mem totalbytes*：可理解为个人总消费，见上图，数值等于真实消费（allocated已分配的总内存）+ 预充值到系统的金额（用于后续抵消债务）。

2）***l_mem GCdebt***：债务。负数的话其绝对值代表预充值多少金额到系统；正数代表需要偿还多少债务。

3）lu_mem GCestimate：非垃圾对象内存占用。在GC中已经处理完毕，被视为合法非垃圾对象的内存占用，在债务算法中可理解为消费后已经确认的订单消费金额。

知道了global_State中这3个数据字段的抽象含义，我们现在可以从资产债务的角度再说一下GC的功能了：在程序运行中，随着内存的不断使用，真实消费会不断增加，因为增长的消费金额先消耗预充值部分，当消费增加的部分超过了预充值的金额，说明预充值的金额耗尽了，又要去借债了，此时则会触发GC。GC触发后会继续处理那些未被处理完毕的消费订单，GC结束后则会再次预充值一笔金额并等待下次GC的重新开始。

债务的产生

债务就是每次产生GCObject或者更精确地说是每次申请堆内存空间的时候产生的，每申请1字节的堆空间，就会产生1单位的债务

// lmem.c
// malloc
void *luaM_malloc_ (lua_State *L, size_t size, int tag) {
  if (size == 0)
    return NULL;  /* that's all */
  else {
    global_State *g = G(L);
    void *newblock = firsttry(g, NULL, tag, size);
    if (l_unlikely(newblock == NULL)) {
      newblock = tryagain(L, NULL, tag, size);
      if (newblock == NULL)
        luaM_error(L);
    }
    g->GCdebt += size;    // 增加债务
    return newblock;
  }
}

债务的检测

每次有债务新增的时候，系统就会检测当前累积的总债务是否已经大于0，大于0表示预充值的金额耗尽了，正式进入真正的负债，系统就会要求你还清债务。

// lgc.h
/*
** 当债务变成正数时，做一步收集. 'pre'/'pos'允许在需要时进行一些调整
** 宏 'condchangemem'用于重度测试(每次有机会都强制执行一次完整的gc)
*/
#define luaC_condGC(L,pre,pos) \
	{ if (G(L)->GCdebt > 0) { pre; luaC_step(L); pos;}; \
	  condchangemem(L,pre,pos); }

#define luaC_checkGC(L)		luaC_condGC(L,(void)0,(void)0)

大于0就会执行**luaC_step(L)**函数

luaC_checkGC的调用时机是在各种申请了堆内存的对象创建的时候，调用的地方很多

创建一个string类型对象
我们知道闭包分为lua闭包与C语言闭包，下面是创建一个C语言闭包
创建一个table
字符串拼接的时候
创建协程的时候

债务的偿还

我们知道堆内存对象的创建会产生债务，相对应的，堆内存对象的释放则会减少对应内存字节数的债务

// lmem.c

/*
** 释放内存
*/
void luaM_free_ (lua_State *L, void *block, size_t osize) {
  global_State *g = G(L);
  lua_assert((osize == 0) == (block == NULL));
  callfrealloc(g, block, osize, 0);
  g->GCdebt -= osize; 		// 减少债务
}

luaM_free_函数会在GCObject被GC清除的时候调用进行堆内存的释放。

债务的清算

// lgc.c
/*
** 如果收集器正在运行，执行一个基础GC步骤（如果收集器没在运行中，设置一个合理的debt以避免每次check他都被调用)
*/
void luaC_step (lua_State *L) {
  global_State *g = G(L);
  if (!gcrunning(g))  /* 没有运行? */ {
    luaE_setdebt(g, -2000);
  }
  else {
    if ( isdecGCmodegen(g) )
      genstep(L, g);  // 分代算法单步
    else
      incstep(L, g);   // 增量式标记清除算法单步
  }
}

incstep 增量式标记清除算法单步

增量式标记清除算法清算债务的方式，我们称之为“工作（Work）”。算法每次触发后，在开始算法真正开始之前，会根据当前欠下的债务以及需要预充值的金额，进行一个工作量的评估，然后通过while循环不断地去工作，直到完成这些工作量，才允许结束本轮GC

// lgc.c
/*
** 执行一个基础的增量步骤. debt和step size(步骤尺寸)从字节转换成“units of work(工作单位)”
** “工作单元” = g->GCdebt / WORK2MEM
** 然后这个函数循环调用单个步骤直到添加那么多工作单位或完成一个GC周期(暂停状态)
** 最后，他设置debt以控制下个步骤什么时候执行
*/
static void incstep (lua_State *L, global_State *g) {
  int stepmul = (getgcparam(g->gcstepmul) | 1);  /* 避免除以0 */
  l_mem debt = (g->GCdebt / WORK2MEM) * stepmul;  // 当前债务需要完成的work数(此时g->GCdebt >= 0)
  l_mem stepsize = (g->gcstepsize <= log2maxs(l_mem))
                 ? ((cast(l_mem, 1) << g->gcstepsize) / WORK2MEM) * stepmul
                 : MAX_LMEM;  /* 溢出，保持最大值 */
    
    //================================================
  do {  /* 循环直至暂停或有足够的“信用”(负的debt) */
    lu_mem work = singlestep(L);  /* 执行一个单独的步骤 */
    debt -= work;
  } while (debt > -stepsize && g->gcstate != GCSpause); /* 债务少于步长或者gc状态暂停 */
        //================================================
    
    
  if (g->gcstate == GCSpause)
    setpause(g);  /* 暂停直至下一个周期 */
  else {
    debt = (debt / stepmul) * WORK2MEM;  /* 转换“工作单元”为字节 */
    luaE_setdebt(g, debt);
  }
}

*预充值*：之所以还清债务后还要预充值一笔金额，是因为这样可以做一个债务缓冲，下次债务增长时可以先从预充值的金额扣除，可以避免债务迅速大于0而再次快速触发GC，能有效控制GC的频率。

简单来说标记清除算法对债务的清算：就是处理工作的过程，然后在工作量完成后把全局的负债g->GCdebt设置为那个预充值的金额。

只需要看最后一行return work，它就是返回了这次GC步骤对应的工作量:

static lu_mem singlestep (lua_State *L) {
  global_State *g = G(L);
  lu_mem work;
  lua_assert(!g->gcstopem);  /* 收集器不可重入 */
  g->gcstopem = 1;  /* 收集时不能运行紧急收集 */
  switch (g->gcstate) {
    case GCSpause: {
      restartcollection(g); // 重启收集
      g->gcstate = GCSpropagate;  // 进入传播阶段
      work = 1;
      break;
    }
   ...
  }
  g->gcstopem = 0;
  return work;
}

1）内存增长，预充值资产耗尽，真实消费不断增加，g->GCdebt由负数变成正数，触发GC：

2）每次GC完成一定工作量，处理中的消费订单会减少，处理完毕的消费订单会不变或增加，如果顺利释放堆内存对象，则g->GCdebt和总分配的内存（allocated）会下降：

3）每轮GC所有工作量都完成后，保持真实消费不变，调整设置清算债务为预存入的金额，等待下轮GC，下一轮GC触发后则又会重复第1步的轮回：

讲完标记清除算法的债务触发，工作，债务调整清算，接下来我们就讲分代式算法的这些流程。

genstep 全量式分代算法单步

分代式算法为全量式算法，每次开始垃圾回收都需要全部处理完成才能继续下一步。虽然也是通过债务大于0来触发分代式算法的执行，但分代式算法没法像增量式算法那样根据工作量通过循环不断“工作（Work）”积累工作量来进行债务清算，而是全量级地通过两种方案去清算债务：

1）第一种方案为：向年轻人员征税；

2）第二种方案为：向全年纪（年轻+年老）人员征税；

static void genstep (lua_State *L, global_State *g) {
  if (g->lastatomic != 0)  /* 上一次回收效果不佳？ */
    stepgenfull(L, g);  /* 执行一次完整的回收步骤 */
  else {
    lu_mem majorbase = g->GCestimate;  /* 上一次主回收后的内存量 */
    lu_mem majorinc = (majorbase / 100) * getgcparam(g->genmajormul);
    if (g->GCdebt > 0 && gettotalbytes(g) > majorbase + majorinc) {
      lu_mem numobjs = fullgen(L, g);  /* 执行一次主回收 */
      if (gettotalbytes(g) < majorbase + (majorinc / 2)) {
        /* 自从上一次主回收以来，至少回收了内存增长量的一半；继续执行次回收。 */
        lua_assert(g->lastatomic == 0);
      }
      else {  /* 回收效果不佳 */
        g->lastatomic = numobjs;  /* 标记上一次回收效果不佳 */
        setpause(g);  /* 在下一次（主）回收之前，进行较长时间的等待 */
      }
    }
    else {  /* 常规情况：执行一次次回收 */
      youngcollection(L, g);
      setminordebt(g);
      g->GCestimate = majorbase;  /* 保持基础值 */
    }
  }
  lua_assert(isdecGCmodegen(g));
}

这个固定消费支出数值的一个使用例子，在触发GC后，当满足条件：

真实消费 > 固定消费 + 新增消费检测值

就会执行第二种方案向全年纪人员征税，否则只需要执行第一种向年轻一代征税

在方案1中，GC完成后会把真实消费金额的100分之20，即5分1作为预充值金额。

而在方案2向全年纪（年轻+年老）人员征税的方案中，预充值金额多少还需要看本轮征税结果是否合格。

1）若GC清理的内存不小于固定消费的一半，则仍然是像上述方案1中预充值较小的值，仍然使用真实消费金额的5分之1作为预充值金额；

2）若GC清理的内存小于固定消费的一半，说明本次GC效果不佳，则会预充值更多的金额，让下轮GC更晚地到来，避免短时间内再去做一些无效的垃圾回收。

总结

本篇简述了债务管理算法，以及对于增量式标记清除算法和全量式分代算法分别怎么使用债务和预充值的处理，这边我记录比较粗，可以后面再研究

标记清除算法

简介

全量模式

全量GC：Lua5.0及以前

每个新创建的对象颜色为白色(white)

// 初始化阶段
遍历在root链表中的对象,加入到对象链表

// 标记阶段
当对象链表中还有未扫描的元素:
    从中取出一个对象,标记为黑色(black)
    遍历这个对象关联的其他所有对象:
        标记为黑色(black)

// 回收阶段
遍历所有对象:
    如果为白色(white):
        这些对象都是没有被引用的对象,逐个回收
    否则:
        这些对象时被引用的对象，重新加入对象链表中等待下一轮的GC检查

该算法的问题是：整个GC过程不能被打断，必须暂停程序（Stop the World），一次性扫描并清除完所有对象。

增量模式

步进式GC（增量模式）：Lua5.1

Lua5.1在双色标记清除算法上改进实现了三色增量标记清除算法（Tri-Color Incremental Mark and Sweep）。

该GC算法不再要求一次性标记清除完所有对象，可以被中断去执行业务逻辑，然后再恢复回来继续执行，是一种增量式垃圾收集器（Incremental Collector）。

白色(White)：表示当前对象为待访问状态，用于表示对象还没有被GC的标记过，这也是任何一个Lua对象在创建之后的初始状态。

换言之，如果一个对象，在一个GC扫描完毕之后，仍然是白色的，那么说明该对象没有被系统中任何一个对象所引用，可以回收其空间了。
灰色(Gray)：表示当前对象为带扫描状态，用于表示对象已经被GC访问过，但是被该对象直接引用的其他对象还没有被访问到。
黑色(Black)：表示当前对象为已扫描状态，用于表示对象已经被GC访问过，并且被该对象直接引用的其他对象也已经被访问过了。

每个新创建的对象颜色为白色(white)

// 初始化阶段
遍历在root节点中引用的对象从白色(white)置为灰色(gray),并且放入到灰色节点列表中.

// 标记阶段
当灰色链表中还有未扫描的元素:
    从中取出一个对象,标记为黑色(black)
    遍历这个对象关联的其他所有对象:
        如果是白色(white):
            标记为灰色(gray),加入灰色链表

// 回收阶段
遍历所有对象:
    如果为白色(white):
        这些对象都是没有被引用的对象,逐个回收
    否则:
        重新加入对象链表中等待下一轮的GC检查

代码

// lgc.c
static lu_mem singlestep (lua_State *L) {
  global_State *g = G(L);
  lu_mem work;
  lua_assert(!g->gcstopem);  /* 收集器不可重入 */
  g->gcstopem = 1;  /* 收集时不能运行紧急收集 */
  switch (g->gcstate) {
    case GCSpause: {
      restartcollection(g); // 重启收集
      g->gcstate = GCSpropagate;  // 进入传播阶段
      work = 1;
      break;
    }
    case GCSpropagate: {
      if (g->gray == NULL) {  /* 没有更多的灰色对象? */
        g->gcstate = GCSenteratomic;  /* 完成传播阶段 */
        work = 0;
      }
      else
        work = propagatemark(g);  /* 遍历一个灰色对象 */
      break;
    }
    case GCSenteratomic: {
      work = atomic(L);
      entersweep(L);
      g->GCestimate = gettotalbytes(g);  /* 第一次预估 */;
      break;
    }
    case GCSswpallgc: {  /* 清除普通对象 */
      work = sweepstep(L, g, GCSswpfinobj, &g->finobj);
      break;
    }
    case GCSswpfinobj: {  /* 清除有终结器的对象 */
      work = sweepstep(L, g, GCSswptobefnz, &g->tobefnz);
      break;
    }
    case GCSswptobefnz: {  /* 清除尚未执行终结器的对象 */
      work = sweepstep(L, g, GCSswpend, NULL);
      break;
    }
    case GCSswpend: {  /* 结束清除 */
      checkSizes(L, g);
      g->gcstate = GCScallfin;
      work = 0;
      break;
    }
    case GCScallfin: {  /* 调用终结器 */
      if (g->tobefnz && !g->gcemergency) {
        g->gcstopem = 0;  /* 在终结器执行期间允许正常收集 */
        work = runafewfinalizers(L, GCFINMAX) * GCFINALIZECOST;
      }
      else {  /* 紧急模式或没有更多终结器 */
        g->gcstate = GCSpause;  /* 完成收集 */
        work = 0;
      }
      break;
    }
    default: lua_assert(0); return 0;
  }
  g->gcstopem = 0;
  return work;
}

表格

状态	分步（step）	说明
GCSpause（gc开始阶段）	不分步（原子操作）	开启新一轮 gc，从root节点遍历并开始标记（mark）， table/proto/closure/thread 对象标记为 gray，加入 g->gray 链表，string/userdata 对象标记为黑色。遍历完成后，切换到GCSpropagate
GCSpropagate（扫描标记阶段）	分步	每次从 g->gray 链表取出一个对象，先标记为 black。如果对象是弱表或 thread，则加入 g->grayagain 链表，然后遍历这个对象的子项开始 mark，把没有标记的对象都标记了。直到 g->gray 链表为空，切换到 GCSatoimic
GCSatoimic（再次扫描标记，并处理finalizer和弱表）	不分步（原子操作）	再次从root节点遍历并开始标记（mark），对 GCSpropagate 期间可能的改变再重新标记，将未标记的对象加入 g->gray 链表。遍历 g->gray 链表取所有对象完成标记。遍历 g->grayagain 链表取所有对象完成标记，遍历弱表，将白色的项置为nil。遍历 g->finobj 链表，把白色的对象移到 g->tobefnz 链表。遍历 g->tobefnz 链表，完成标记（mark）。切换当前白色到另一种白色。切换到 GCSswpallgc
GCSswpallgc（清除阶段）	分步	每次取 g->allgc 链表一定数量的对象（最多GCSWEEPMAX个）, 将还是上一种白色的对象清理掉。 // #define GCSWEEPMAX 100 同时将黑色对象标记为当前白色。当 g->allgc遍历完成，切换到 GCSswpfinobj
GCSswpfinobj（清除阶段）	分步	每次取 g->finobj 链表一定数量的对象（最多GCSWEEPMAX个）, 将还是上一种白色的对象清理掉。 // #define GCSWEEPMAX 100 同时将黑色对象标记为当前白色。当 g->finobj 遍历完成，切换到 GCSswptobefnz
GCSswptobefnz（清除阶段）	分步	每次取 g->tobefnz 链表一定数量的对象（最多GCSWEEPMAX个）, 将还是上一种白色的对象清理掉。 // #define GCSWEEPMAX 100 同时将黑色对象标记为当前白色。当 g->tobefnz 遍历完成，切换到 GCSswpend
GCSswpend	不分步（原子操作）	收缩全局 string 的hash表，保证hash桶利用率超过 1/4，切换到 GCScallfin
GCScallfin（执行finalizer）	分步	每次取 g->tobefnz 链表一定数量的对象（最多GCFINMAX个），执行 __gc元方法，然后将对象标记为白色，加入 g->allgc 链表，等下一次 gc 清理。 // #define GCFINMAX 10 当 g->tobefnz 为空时，切换到 GCSpause

标记阶段

清除阶段-allgc链表

entersweep(): 遍历

luaC_fix(): 标记需要被GC清除的对象

标记阶段—标记初始结点

restartcollection(): 根结点global_State中需要被标记为初始标记结点的字段分别只有4个，分别是：mainthread，l_registry，twups，mt。

标记阶段—染色

reallymarkobject(): 在需要被GC处理的不同GCObject类型中，字符串类型，无UpValue的UserData类型，它们在染色时会直接设置为黑色，因为他们没有引用其它GCObject对象；而function，thread，table，包括他们引用的UpValue类型，都属于可引用其它GCObject对象的集合类型，所以会先设置为灰色。

标记阶段—颜色传播

propagatemark(): g->gray = *getgclist(o);

会先把这个灰色对象修改为黑色，然后根据不同数据类型调用不同的染色函数去对他所有的子对象进行染色。遍历子对象的时候也有可能遇到这个子对象也是属于集合类型，它们也有它们的子对象，此时会把这些集合类子对象先标记为灰色，若是遍历的对象没有引用其它子对象，则可以直接设置为黑色。在颜色传播过程中产生的这些新的集合灰色结点不会立即继续递归往下传播，它们也会先链接到global_State的gray链表头部，等待下一步GC颜色传播的时候继续处理。

/*
** 遍历一个灰色对象，将其转换成黑色
*/
static lu_mem propagatemark (global_State *g) {
  GCObject *o = g->gray;
  nw2black(o);
  g->gray = *getgclist(o);  /* 从‘gray’列表中移除 */
  switch (o->tt) {
    case LUA_VTABLE: return traversetable(g, gco2t(o));
    case LUA_VUSERDATA: return traverseudata(g, gco2u(o));
    case LUA_VLCL: return traverseLclosure(g, gco2lcl(o));
    case LUA_VCCL: return traverseCclosure(g, gco2ccl(o));
    case LUA_VPROTO: return traverseproto(g, gco2p(o));
    case LUA_VTHREAD: return traversethread(g, gco2th(o));
    default: lua_assert(0); return 0;
  }
}

标记传播-各数据类型的传播方式

讲债务管理算法的时候，知道增量式算法中调用的函数的返回值就是遍历处理的TValue对象个数，代表当轮债务清算过程的工作量。

分代算法

经验表明，大部分对象在被分配之后很快就被回收掉了（如栈上的临时变量），长时间存活的对象很大可能会一直存活下去。所以，垃圾回收可以集中精力去回收刚刚造出来的对象。

将所有gc对象分成两种，young和old；过程也分为minor（浅扫描，或次级收集周期）和major（深扫描，或主收集周期）。

对象创建时标记为young，minor过程扫描young对象，当young节点活过了两次gc过程，就会标记成old对象。注：活过两次gc过程也是与lua5.2 gc过程的最大不同点。lua5.2 gc只需要活过一次，就算做old。

minor过程只对young 对象进行遍历清除工作。这样就避免了每次都遍历大量并不活跃却长期存活的old对象，又可以及时清理掉大量生命短暂的young对象。

minor过程越密集，单个过程内的young对象数量就越少，需要做的工作也越少，停顿时间也就缩小了。可见增加minor过程并不会太多的增加整体工作量，却可以更及时的回收内存。

当总的内存增长超过阈值时，会执行major过程，来做一次完整的标记清除（带来严重的GC卡顿），处理全部young对象和old对象，清理垃圾对象后，把所有存活对象都变为old对象。

只不过分代 GC 模式下，major过程（全量 GC）的频率可以降的非常低，因为大量临时内存都通过minor过程清理掉了，内存并不会增长太快。

当遇到必须消除停顿的环境，我们可以手工精确调整：发现内存持续增长，不要主动触发完整的major过程

而是主动切换到增量gc模式，然后周期性的调用 gc step （不等内存分配器来触发）在合理的时间内分步处理完一个完整的 GC 周期，再切换回分代gc模式。