Lua的垃圾回收（上）
Lua 5.3版本的垃圾回收
垃圾回收算法
垃圾回收算法一般分为两类：引用计数法和标记扫描法。
引用计数法
所谓引用计数法，是指在为对象申请内存的时候，在分配的内存块预留一块区域用于存放这块内存被引用的次数，当被引用的时候增一，解引用的时候减一，当这块内存的引用次数降到0的时候，这块内存被认为不可访问，直接被回收。
标记清除法
所谓标记清除法则是将整个算法分为标记和清除两大部分：
标记部分：从根节点开始遍历所有节点，将与根节点关联的节点进行标记；
清除部分：标记结束之后，遍历整个对象链表，将需要删除的节点进行删除即可。
Lua的垃圾回收机制
Lua的垃圾回收采取的是标记清除法，但是原生的标记清除法有一个问题，就是每次垃圾回收需要遍历整个内存，当系统复杂之后，内存使用复杂&内存遍历运算量大，一次处理容易导致程序运行出现卡顿；为此Lua的不同版本都尝试针对此问题进行优化：
Lua5.0采取的机制是，当内存分配超过上次GC的两倍就全量跑一遍GC，这个机制优化效果有限；
Lua5.1则采取渐进式的垃圾回收，但是渐进式的垃圾回收有个问题，就是内存的使用是动态变化的，两次扫描之间内存块的引用状态可能会发生变化，对扫描和回收的结果产生影响，为此Lua引入三色标记法解决这个问题。在介绍Lua的渐进式垃圾回收流程之前，我们先了解一些Lua的垃圾回收的一些基本机制：
三色标记法
所谓三色标记法，是指Lua用黑、白、灰三色来标记一个对象的可回收状态，其中：
白色：无法被访问到的对象是白色；
灰色：可以被访问，但是没有被递归扫描完全的对象是灰色；
黑色：可以被访问，且完全扫描过的对象是黑色。
因此白色对象是日后会被回收的部分，黑色对象是日后需要保留的部分，灰色对象则是黑色集和白色集的边界，即还未来得及处理的部分
这中间存在两个问题：
1）首先，对于渐进式内存回收来说，假设对于对象t已经被完全扫描了，但是由于回收和标记流程是分离的，所以可能在标记之后回收之前会新创建一个表new_t，当我们运行t.x=new_t时，则对象t又变成未完全扫描状态，针对这种情况，需要将其重新放回灰色列表，等待处理
2）在上述示例中，因为新创建的对象创建的时候已经过了标记阶段，所以对象是白色的，但是为了避免在后续阶段新创建的对象还未使用就被回收，所以在实际Lua源码的垃圾回收流程对于此类对象的白色进行特殊的标记，以规避误回收的情况
根集合
Lua的垃圾回收是从根节点集合开始，这类节点包括：
注册表，而注册表有引用了全局表、主线程、标准库的代码等；
原生类型的metatable。
弱引用表
Lua的垃圾回收还有一类特殊类型的对象，弱引用表（weak table），在介绍弱引用表之前我们需要了解一些基本概念：
Lua引用
在C/C++中，引用就是变量的别名，这样可以通过对别名进行操作达到对和变量本身进行操作一样的效果，在实现层面可以理解为引用其实是地址的传递，类似于“指针”的概念，区别在于引用一旦被指定就不能被改变。
在Lua中，有八种基本类型，这其中table、function、thread、userdata类型的变量是引用类型，即不存储变量的值，而是存一个指向他们的地址；因此对于这些类型的变量的赋值，参数传递和返回都是地址的传递，不存在值的复制过程。
引用类型
Lua中引用分为强引用和弱引用，主要是针对内存回收而言，他们区别在于：
1）强引用的对象，一旦对象被强引用，则这个对象一定不会被内存回收
2）弱引用的对象，若是一个对象的引用都是弱引用，则这个对象会在下次垃圾回收的时候被回收
弱引用表
而弱引用表，是指表中的key或者val对象是弱引用的，通过设置表的元表的__mode字段实现：
1）若table A的元表的__mode字段值为k，则表示table的key是弱引用的，即当key被添加到这个表之后，没有被强引用，则在下次GC的时候key指向的对象就会被回收掉
2）若table A的元表的__mode字段值为v，则表示table的val是弱引用的，若是没有被强引用，则val指向的对象会在下次垃圾回收的时候被回收掉
3）__mode的字段还可以取值为kv，则表示table是前面二者的综合
对于普通的强引用表，当把对象放入表时就产生一个引用，若是这个表一直被引用，但是对于此元素没有其他地方对这个表元素进行引用，gc是不会对此元素进行回收，要么手动回收，要么放任其常驻内存。而若是指定了其中key或者val是弱引用的，则对象一个创建放进table之后，一直没有被引用，那么对象会在垃圾回收的时候被释放掉。
垃圾回收流程概述
原理上Lua的垃圾回收包括以下几个步骤：
1）垃圾回收的触发，当新建可回收对象的时候，会判断是否达到GC的条件
2）若是满足GC的条件，则从根集合开始，将节点标记灰色，加入到灰色链表
3）轮询灰色链表是否为空，若不为空则取出对象设置为黑色并遍历其关联的对象
4）对于灰色链表进行一次原子性的清除操作
5）逐个遍历垃圾链表，针对调用其_gc元方法
6）遍历对象链表，判断对象是否为白，是的话释放对象所占用空间
参考文献
Lua GC机制分析与理解-上 - 知乎 (zhihu.com)
Lua垃圾回收机制和弱引用table - 简书 (jianshu.com)
Lua 5.3 设计实现(六) GC 垃圾回收 | Yuerer's Blog
云风的 BLOG: Lua GC 的工作原理 (codingnow.com)
深入 Lua Garbage Collector(四) | 趣果有间 (kelele67.github.io)
[Lua]弱表Weak table超越-CSDN博客lua 弱表
