看到一个 Bob Nystrom 写的 C 语言实现的 Garbage Collector

借着这个小程序顺便深入地了解一下Lua的垃圾回收机制

Garbage Collector算法小结

这是之前做的一点小笔记:

C Garbage Collector

首先还是先来看看这个 C 的基本的垃圾回收器

采用的算法

用的是经典的 Mark & Sweep 算法

在上面的笔记里面已经介绍的很清楚了

该算法的工作原理几乎与我们对 可访问性(reachability) 的定义完全一样:

  1. 从根节点开始,依次遍历整个对象图。每当你访问到一个对象,在上面设置一个 标记(mark) 位,置为 true 。

  2. 一旦搞定,找出所有标记位为 not 的对象集,然后删除它们。

对象对

要想清理垃圾,首先我们得制造点垃圾出来

所以假设我们正在为一种简单的语言编写一个解释器。它是动态的类型并且有两种类型的变量:intpair 。 下面是用枚举来标示一个对象的类型:

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
typedef enum {
OBJ_INT,
OBJ_PAIR
} ObjectType;
// 因为一个对象在虚拟机中可以是这两个当中的任意一种类型,所以在C中用tagged union 来实现对象
typedef struct sObject {
//表示对象类型:pair or int
ObjectType type;
unsigned char marked;
//仅维持一张由所有分配过(内存)的对象(组成)的链表。
struct sObject*next;
//union持有这个数据
//union就是一个结构体,它将字段重叠在内存中
union {
int value;
struct {
struct sObject* head;
struct sObject* tail;
};
};
} Object;

小虚拟机

虚拟机要么基于栈( JVM , CLR ),要么基于寄存器( Lua ),其实本质上说都是基于栈的,它用来保存一个表达式中间需要用到的临时变量和局部变量

下面我们建立一个简洁的虚拟机模型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 小虚拟机
typedef struct {
Object* stack[STACK_MAX];
int stackSize;
//虚拟机会保留链表头的痕迹
Object* firstObject;
//追踪创建了多少个对象
int numObjects;
//多少数目之后清理
int maxObjects;
} VM;

虚拟机的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 初始化一个虚拟机
VM* () {
VM* vm = malloc(sizeof(VM));
vm->stackSize = 0;
Object* firstObject = NULL;
vm->numObjects = 0;
vm->maxObjects = 8;
return vm;
}
//操作虚拟机堆栈
void push(VM* vm, Object* value) {
assert(vm->stackSize < STACK_MAX, "Stack overflow!!!");
vm->stack[vm->stackSize++] = value;
}
Object* pop(VM* vm) {
assert(vm->stackSize > 0, "Stack underflow!!!");
return vm->stack[--vm->stackSize];
}

Mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void mark(Object* object) {
//检查循环!
if (object->marked) return;
object->marked = 1;
if (object->type == OBJ_PAIR) {
mark(object->head);
mark(object->tail);
}
}
void markAll(VM* vm) {
for (int i = 0; i < vm->stackSize; i++) {
mark(vm->stack[i]);
}
}

Sweep

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//清理
//仅维持一张由所有分配过(内存)的对象(组成)的链表。
void sweep(VM* vm) {
Object** object = &vm->firstObject;
while (*object) {
if (!(*object)->marked) {
//没有访问过,所以从链表中移除然后释放它
Object* unreached = *object;
*object = unreached->next;
free(unreached);
vm->numObjects--;
} else {
//访问过,所以不标记它
(*object)->marked = 0;
object = &(*object)->next;
}
}
}

GC

1
2
3
4
5
6
7
8
9
10
void gc(VM* vm) {
int numObjects = vm->numObjects;
markAll(vm);
sweep(vm);
vm->maxObjects = vm->numObjects * 2;
printf("Collected %d objects, %d remaining.n", numObjects - vm->numObjects,
vm->numObjects);
}

对象操作函数

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
Object* newObject(VM* vm, ObjectType type) {
if (vm->numObjects == vm->maxObjects) gc(vm);
Object* object = malloc(sizeof(Object));
object->type = type;
//无论何时创建对象,都添加到链表中
object->next = vm->firstObject;
vm->firstObject = object;
object->marked = 0;
vm->numObjects++;
return object;
}
//编写方法将每种类型的对象压到虚拟机的栈上
void pushInt(VM* vm, int intValue) {
Object* object = newObject(vm, OBJ_INT);
object->value = intValue;
push(vm, object);
}
Object* pushPair(VM* vm) {
Object* object = newObject(vm, OBJ_PAIR);
object->tail = pop(vm);
object->head = pop(vm);
push(vm, object);
return object;
}
void objectPrint(Object* object) {
switch (object->type) {
case OBJ_INT:
printf("%d", object->value);
break;
case OBJ_PAIR:
printf("(");
objectPrint(object->head);
printf(", ");
objectPrint(object->tail);
printf(")");
break;
}
}

free、test、main

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
void freeVM(VM *vm) {
vm->stackSize = 0;
gc(vm);
free(vm);
}
void test1() {
printf("Test1: Objects on stack are preserved.n");
VM* vm = newVM();
pushInt(vm, 1);
pushInt(vm, 2);
gc(vm);
assert(vm->numObjects == 2, "Should have preserved objects.");
freeVM(vm);
}
void test2() {
printf("Test2: Objects on stack are collected.n");
VM* vm = newVM();
pushInt(vm, 1);
pushInt(vm, 2);
pop(vm);
pop(vm);
gc(vm);
assert(vm->numObjects == 0, "Should have collected objects.");
freeVM(vm);
}
void test3() {
printf("Test3: Reach nested objects.n");
VM* vm = newVM();
pushInt(vm, 1);
pushInt(vm, 2);
pushPair(vm);
pushInt(vm, 3);
pushInt(vm, 4);
pushPair(vm);
pushPair(vm);
gc(vm);
assert(vm->numObjects == 7, "Should have reached objects.");
freeVM(vm);
}
void test4() {
printf("Test4: Handle cycles.n");
VM* vm = newVM();
pushInt(vm, 1);
pushInt(vm, 2);
Object* a = pushPair(vm);
pushInt(vm, 3);
pushInt(vm, 4);
Object* b = pushPair(vm);
//建立一个循环, 并且让2 和 4 不可到达和收集
a->tail = b;
b->tail = a;
gc(vm);
assert(vm->numObjects == 4, "Should have collected objects.");
freeVM(vm);
}
void perfTest() {
printf("Performance Tsetn");
VM* vm = newVM();
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 20; j++) {
pushInt(vm, i);
}
for (int k = 0; k < 20; k++) {
pop(vm);
}
}
freeVM(vm);
}
int main(int argc, const char * argv[]) {
test1();
test2();
test3();
test4();
perfTest();
return 0;
}

测试结果

总结

这个简单的收集器与目前 RubyLua 中的收集器非常的相似,所以下一次我们将深入了解 LuaGC 机制。