用Lua开发游戏已经有一段时间了,但是对Lua的理解还一直停留在浅层。最近想深入研究下,于是着手开始看Lua源码,并在本文记录知识点。

模块

GC

1.基本数据结构

Lua的基本数据结构是一个类型union+type。相关的核心代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

** Common type for all collectable objects
*/
typedef struct ;


** Common Header for all collectable objects (in macro form, to be
** included in other objects)
*/

GCObject *next;
lu_byte tt;
lu_byte marked


** Common type has only the common header
*/
struct
{
CommonHeader;
};


** Tagged Values. This is the basic representation of values in Lua,
** an actual value plus a tag with its type.
*/


** Union of all Lua values
*/
typedef union Value {
GCObject *gc; /* collectable objects */
void *p; /* light userdata */
int b; /* booleans */
lua_CFunction f; /* light C functions */
lua_Integer i; /* integer numbers */
lua_Number n; /* float numbers */
} Value;

#define TValuefields
Value value_;
int tt_

typedef struct lua_TValue
{
TValuefields;
} TValue;

2.GC算法和流程

  1. 双色标记清除算法

    在Lua5.0中的GC,是一次性不可被打断的操作,执行的算法是Mark-and-sweep算法,在执行GC操作的时候,会设置2种颜色,黑色和白色,然后执行GC的流程,大体的伪代码流程如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    每个新创建的对象为白色

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

    //标记阶段
    当前对象链表中还有未被扫描的元素:
    从中取出对象并将其标记为黑色
    遍历这个对象关联的其他所有对象:
    标记为黑色

    //回收阶段
    遍历所有对象:
    如果为白色:
    这些对象没有被引用,则执行回收
    否则:
    这些对象仍然被引用,需要保留

    整个过程是不能被打断的,这是为了避免一种情况:
    如果可以被打断,在GC的过程中新创建一个对象
    那么如果标记为白色,此时处于回收阶段,那么这个对象没有被扫描就会被回收;
    如果标记为黑色,此时处于回收阶段,那么这个对象没有被扫描就会被保留
    两种情况都不适合,所以只有让整个过程不可被打断,带来的问题就是造成gc的时候卡顿

  2. 三色标记清除算法

    虽然是三色,本质是四色,颜色分为三种:

    白色: 当前对象为待访问状态,表示对象还未被gc标记过,也就是对象创建的初始状态; 同理,如果在gc完成后,仍然为白色,则说明当前对象没有被引用,则可以被清除回收

    灰色: 当前对象为待扫描状态,当前对象已经被扫描过,但是其引用的其他对象没有被扫描

    黑色: 当前对象已经扫描过,并且其引用的其他对象也被扫描过

    其流程伪代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    每个新创建的对象为白色

    //初始化阶段
    遍历root阶段中引用的对象,从白色设置为灰色,并放入到灰色节点列表中

    //标记阶段
    当灰色链表中还有未被扫描的元素:
    从中去除一个对象并将其标记为黑色
    遍历这个对象关联的其他所有对象:
    如果是白色:
    标记为灰色,并加入灰色链表中

    //回收阶段
    遍历所有对象:
    如果为白色:
    这些对象没有被引用,需要被回收
    否则:
    重新加入对象链表中等待下次gc

    整个标记过程是可以被打断的,被打断后回来只需要接着执行标记过程即可,回收阶段是不可被打断的。

    如何解决在标记阶段之后创建的对象为白色的问题?
    分裂白色为两种白色,一种为当前白色 currentwhite, 一种为非当前白色 otherwhite,新创建的对象都为otherwhite,则在执行回收的时候,如果为otherwhite则不执行回收操作,等待下次gc的时候,会执行白色的轮换,则新创建的对象会进入下一轮GC。