Lua源码解析《GC管理一》

2019-02-28 本文已影响144人肖马克_蛮牛

使用版本： Lua 5.3.5

人人从心，水滴石穿

感觉文章有用，支持打赏，钱够了提现就会捐出去，虽是一小老百姓，余生愿尽最大努力做慈善。

写在前面

理解底层实现原理，可以写出更优质的代码。C、C++对于GC都是程序手动控制的，而C#、JAVA这种高级语言都有了托管堆，自动GC。Lua作为开源脚本语言，也实现了自动GC，很值得我们学习借鉴。

面试常问

Lua的GC是用什么算法实现的。
Lua的weaktable是什么，有什么功能。
uLua/toLua/xLua等框架里面的Lua内存如何管理的，有什么坑和注意事项。

GC原理及数据结构算法

不管什么语言，GC释放的核心原理都是判断一块内存有没有用，如果没有用，就是释放掉内存。所以核心问题就是，如何判断一块内存有没有用。不同的语言，采用的算法是不一样的。

Java语言GC算法核心是，对内存引用做计数器，有引用计数器+1，当为0是就释放。
C#的GC算法一定程度上采用了Java，但核心算法是“Mark-sweep & compace”算法。
Lua采用的是“Mark-sweep”算法，就是标记内存有没有引用，没有引用则释放。目前lua标记算法，采用的是“三色增量标记算法”，早起的lua版本采用的是二色算法。

Lua GC 源码解析

1. lua关于GC的源码在lgc文件下，很简洁，去掉换行，一共不到1000行代码就实现了gc。

image.png

喜欢自己研究的同学，直接先看lgc.h头文件，里面的注释很详细。
/*
** Collectable objects may have one of three colors: white, which
** means the object is not marked; gray, which means the
** object is marked, but its references may be not marked; and
** black, which means that the object and all its references are marked.
** The main invariant of the garbage collector, while marking objects,
** is that a black object can never point to a white one. Moreover,
** any gray object must be in a "gray list" (gray, grayagain, weak,
** allweak, ephemeron) so that it can be visited again before finishing
** the collection cycle. These lists have no meaning when the invariant
** is not being enforced (e.g., sweep phase).
*/

2. 头文件上面的注释必看，介绍了“白-灰-黑”三个颜色标记的含义。

简单来说：lua所有的可回收对象，都会标记为以上三个颜色，
白色：表示对象没有被标记，也就是没有地方引用，最终会被GC掉
灰色：表示对象被标记，但是它内部关联的对象可能没有被标记；
黑色：表示对象被标记，内部所有的关联的对象也都被标记；

       自己理解的伪代码如下：
      1. 一开始，所有新创建的对象都标记为白色；

      2.  GC管理器开始GC算法，遍历程序root节点中所有引用的对象，将其标记为灰色，并存放到一个集合中；

      3. while(灰色集合不为空）：
          3.1 取出一个对象，标记为黑色
          3.2 遍历这个对象关联的所有其他对象，if对象为白色，标记为灰色，放入灰色结合中

     4. 遍历对象链表，如果为白色，执行GC，否则不处理，放回对象链表。

注意，新创建的对象是白色，要清理的对象也是白色，为了在第四步区分屏障，那些是new object, 那些是经过GC算法计算过要清理的 old object，白色分为white1和white2，类似抽屉算法。

image.png

GC算法的执行过程

整个GC过程如下图，分为8个阶段， 0-7分别是他们的先后顺序，下一篇我们分别介绍这几个阶段的功能和源码。