GC的标记-清除算法由标记阶段和清除阶段组成，标记阶段是标记出活动对象的阶段，《GC算法实践(二) 对象标记、清除算法》一文中已经实现了对活动对象的标记，该步骤需要从根对象出发，递归标记由根对象可以访问到的所有对象。
清除阶段则是将非活动对象（垃圾）回收的阶段，暂且把这些回收后的一个一个的非活动对象叫做空闲块。回收当然是为了再次利用，所以需要用合适的方法把这些空闲块组织起来，使得分配内存的时候可以从这些空闲快中找出可用的内存空间。一般的做法是把这些空闲快加入到一个链表中，这个链表叫做空闲块链表。分配内存的时候就从这个空闲块链表中查找合适的空闲块。
由于标记算法已经实现，标记-清除算法中，空闲块链表的操作是关键！
1.空闲块链表的定义及基本操作
1.1空闲块链表的定义
随着分配-回收操作的交替进行，空闲块会大小不一，可能会变得很零碎，有可能是几个字节（如4个字节），所以这里决定单独用一个链表来保存这些空闲块的信息。《垃圾回收的算法与实现》一书中有一个非常巧妙的实现，每一个空闲块都有一个字段作为指针，用该指针指向下一个空闲块，很自然的形成了一个链表，这样就不用另外建立链表了。不过既然程序都写出来了，暂时就不换方法了。
一个空闲块的基本信息是块的起始地址和块大小，所以对空闲块链表定义如下：
// 链表结点的定义
typedef struct _list_item {
char* start_addr; // 空闲块的起始地址
ushort chunk_size; // 空闲块的地址
struct _list_item *next; // 下一个空闲块的地址
}ListItem;
// 空闲块链表的定义
typedef struct _free_chunck_list {
ListItem *head; // 指向第一个结点
ListItem *last_visit_item; // 上次访问的结点
}FreeChunkList;
声明一个全局变量，作为空闲块链表：
FreeChunkList *free_chunk_list;
1.2初始化空闲块链表
让初始化变量
free_chunk_list
，让它指向一个空的链表：
void initFreeChunkList(Heap *heap) {
free_chunk_list = (FreeChunkList*)malloc(sizeof(FreeChunkList));
free_chunk_list->head = NULL;
free_chunk_list->last_visit_item = NULL;
}
1.3添加一个空闲块到空闲块链表
添加一个空闲块到空闲块链表，该操作比较重要，需要考虑到相邻空闲块合并的情况，包括：前向合并、后向合并，以及前后向合并。
空闲块链表中的空闲块是按空闲块首地址升序排列的。
/**
* 添加一个空闲块到空闲块链表，同时进合并相邻的空闲块
* @param free_chunk_list 空闲块链表(全局变量)
* @param chunk_start_addr 空闲块的首地址
* @param chunk_size 空闲块的大小，单位：字节
*/
void addFreeChunk(FreeChunkList *free_chunk_list, char* chunk_start_addr, ushort chunk_size) {
char *tmp_addr;
ListItem *cur_item;
ListItem *prev_item;
ListItem *new_item;
char *chunk_end_addr = chunk_start_addr + chunk_size;
prev_item = cur_item = free_chunk_list->head;
// empty
if (cur_item == NULL) {
printf("\t[:-> first insert]\n");
new_item = newListItem(chunk_start_addr, chunk_size);
free_chunk_list->head = new_item;
return;
}
// 从上次遍历的位置开始查找
if (free_chunk_list->last_visit_item != NULL) {
cur_item = free_chunk_list->last_visit_item;
}
// 找到合适的位置
while (cur_item != NULL && cur_item->start_addr < chunk_start_addr) {
prev_item = cur_item;
cur_item = cur_item->next;
}
if (cur_item != NULL && chunk_end_addr == cur_item->start_addr) {
// if can also forward merge
if (chunk_start_addr == (prev_item->start_addr + prev_item->chunk_size)) {
printf("\t[<==> back and forward merge]\n");
prev_item->chunk_size += (cur_item->chunk_size + chunk_size);
prev_item->next = cur_item->next;
free(cur_item); // free
} else {
printf("\t[=>back merge]\n");
cur_item->start_addr = chunk_start_addr;
cur_item->chunk_size += chunk_size;
}
} else if (chunk_start_addr == (prev_item->start_addr + prev_item->chunk_size)) {
// only forward merge
printf("\t[<= forward merge]\n");
prev_item->chunk_size += chunk_size;
} else {
printf("\t[-> insert into list]\n");
new_item = newListItem(chunk_start_addr, chunk_size);
new_item->next = cur_item;
prev_item->next = new_item;
}
// 记住上次遍历的位置，避免每次都从头查找
free_chunk_list->last_visit_item = prev_item;
}
1.3从空闲块中分配内存
回收了空闲块，需要分配内存时可以从空闲块查找，找到合适大小的块就返回，没有就返回空
NULL
。这里采用的方式是找到一块大于等于所需空间的空闲块就停止查找。
/**
* 从空闲块中分配内存
* @param free_chunk_list 空闲块链表(全局变量)
* @param size 要分配的内存大小，单位：字节
*/
char* alloc_memory_from_fchunk(FreeChunkList *free_chunk_list, ushort size) {
ListItem *tmp_item, *prev_item;
char *alloc_addr = NULL;
prev_item = free_chunk_list->head;
for(tmp_item = prev_item; tmp_item != NULL; tmp_item = tmp_item->next) {
if (tmp_item->chunk_size == size) {
alloc_addr = tmp_item->start_addr;
if (prev_item == tmp_item) {
free_chunk_list->head = tmp_item->next;
} else {
prev_item->next = tmp_item->next;
}
free(tmp_item);
break;
} else if (tmp_item->chunk_size > size) {
alloc_addr = tmp_item->start_addr;
tmp_item->start_addr += size;
tmp_item->chunk_size -= size;
break;
}
}
return alloc_addr;
}
2.创建对象时内存分配的方法修正
本来可以把刚初始化的堆/堆中未分配的内存空间也当做一个空闲块来使用，不过这里作了下区分，创建对象时，先是从回收的空闲块中分配内存，如果没找到合适的，就从堆中未分配的内存空间中分配。只是为了演示而已。
创建对象时，内存分配方法改为如下：
// 尝试从空闲块中分配
addr = alloc_memory_from_fchunk(free_chunk_list, total_size);
if (addr == NULL) {
addr = alloc_memory(cur_heap, total_size); // 从堆中分配
printf("alloc [0x%p] from heap, size=%d\n", addr, total_size);
} else {
printf("alloc [0x%p] from free chunk, size=%d\n", addr, total_size);
}
3.清除阶段-遍历堆
这一阶段遍历堆，如果遇到活动对象，将对象的标记为复位为0；如果遇到非活动对象（垃圾），调用前面定义的
addFreeChunk
方法加入到空闲块链表中。
由于堆中已经是活动对象与空闲块交错分布了，不能像在“标记-压缩算法”和“复制算法”中一样，把堆直接当做一个链表来遍历。这里需要借助我们建立的空闲块链表，它的结点所对应的空闲块是按首地址升序排列的，因此可以用来辅助遍历堆。
假设空闲块链表、堆中的内存分配状态如下图：
上图中，空闲块链表中只有两个结点，命名为
item
和
next_item
，
chunk_size
字段没有画出来。
item.start_addr
指向空闲块
F1
，
next_item.start_addr
指向空闲块
F2
。堆中有三块对象区域，分别为
A1
、
A2
、
A3
，每个区域可能有多个对象，区域内对象的地址是连续的，之间没有空闲块。当前堆是
heap
。
遍历上图所示状态的堆步骤如下：
- 步骤1：遍历对象区域
A1
heap->start_addr
item
item->start_addr
heap->start_addr
item->start_addr
heap->start_addr
item->start_addr + item.chunk_size
A1
A1
- 步骤2：跳过空闲块
F1
A1
F1
- 步骤3：遍历对象区域
A2
A2
item->start_addr + item.chunk_size
next_item->start_addr
- 步骤4：跳过空闲块
F2
- 步骤5：遍历最后一个对象区域
A3
next_item->start_addr + next_item.chunk_size
heap->free_addr
A3
）。
该步骤执行完后，
heap->start_addr
heap->end_addr
将以上步骤一般化，写成代码，封装在函数
sweep_garbage
中，如下：
void sweep_garbage(Heap *heap) {
char *tmp_addr, *next_addr, *end_addr;
Object *obj;
int obj_size;
ListItem *item, *next_item = NULL;
item = free_chunk_list->head;
printf("sweep_garbage: \n");
tmp_addr = heap->start_addr;
while () {
if (item == NULL) {
end_addr = heap->free_addr;
next_addr = NULL;
next_item = NULL;
} else {
end_addr = item->start_addr;
next_addr = item->start_addr + item->chunk_size;
next_item = item->next;
}
while(tmp_addr < end_addr) {
obj = (Object*)tmp_addr;
obj_size = OBJ_SIZE(obj);
if (obj->flag == ) { // garbage
printf("object[%d] at 0x%p is Garbage, size=%d\n", OBJ_GET_INT(obj, ), obj, obj_size);
addFreeChunk(free_chunk_list, tmp_addr, obj_size);
} else {
obj->flag = ;
printf("object[%d] at 0x%p is active\n", OBJ_GET_INT(obj, ), obj);
}
tmp_addr += obj_size;
}
if (item == NULL) {
break;
}
printf("___skip free chunk: start_addr=%p,size=%d\n", tmp_addr, next_addr-tmp_addr);
tmp_addr = next_addr; // skip free memory
item = next_item;
}
free_chunk_list->last_visit_item = NULL;
}
用同样的思路可以用来把堆的状态打印出来（活动对象、非活动对象、空闲块），代码就免了。
4.测试
至此，空闲块的回收与再利用，遍历堆等功能均已实现，接下来就是测试。
构建初始状态，代码如下：
void test_alloc_memory_fchunk() {
Object *objects[];
int obj_len[] = {,,,,,};
int i;
for(i=; i<; i++) {
objects[i] = new_object(obj_len[i]);
OBJ_SET_INT(objects[i], , i);
}
OBJ_SET_OBJ(objects[], , objects[]); // objects[3]->objects[5]
OBJ_SET_OBJ(objects[], , objects[]); // objects[1]->objects[3]
root[] = objects[]; // object[0]、object[2]、object[4] are garbage
root[] = NULL;
}
对应的内存状态示意图如下：
一共创建了6个对象，其中3个对象不能从根对象遍历到，它们是
object[0]
、
object[2]
和
object[4]
，另外三个对象可以从根对象遍历到，是活动对象，它们之间的引用关系如箭头所示：
object[1]->object[3]->object[5]
。
为了调试，更清楚了解垃圾回收前后都是什么状态，把每次垃圾回收的测试分为5步输出调试信息：
- 1.打印活动对象
- 2.打印垃圾回收前堆的状态（活动对象、垃圾、空闲块）
- 3.打印垃圾回收过程
- 4.打印垃圾回收后的空闲块链表
- 5.打印垃圾回收后堆的状态（活动对象、垃圾、空闲块）
4.1首次垃圾回收测试
测试能否正确识别垃圾并回收。
4.1.1把活动对象打印出来，结果如下：
object[] at:
=>object[] at:
=>object[] at:
相邻行之间的缩进表示它们之间的引用关系，上面的输出表示
object[1]->object[3]->object[5]
。
4.1.2把垃圾收集前堆的状态打印出来，如下：
scan heap(@ head of object, # active, * garbage, _ free):
@******@#####@*******@#####@******@#####
为了方便查看，用一个字符来表示内存的4个字节，其中
@
表示对象的前4个字节，用于区分连续的对象；
#
表示为活动对象的内存空间，
*
表示非活动对象（垃圾）的内存空间，
_
表示空闲块的内存空间。这个要记住，不然后面看不懂。
上面的输出表示有三个活动对象、三个非活动对象，相互交错排列。
4.1.3把垃圾回收过程打印出来，如下：
sweep_garbage:
object[] at is Garbage, size=
[:-> first insert]
object[] at is active
object[] at is Garbage, size=
[-> insert into list]
object[] at is active
object[] at is Garbage, size=
[-> insert into list]
object[] at is active
如果发现有需要回收的对象，会打印出如
object[0] at 0x00120F4C is Garbage, size=24
所示的信息，包含了对象的首地址和大小，并且，会在下一行打印把对象（此时变成了空闲块）加入到空闲块链表的情况（是否有合并等）。
上面输出的信息很清楚，表示一共发现了3个垃圾对象，大小分别为24、28、24字节，第一个空闲块
object[0]
是首次加入到链表，后面的两次是插入到链表。
4.1.4把空闲块链表打印出来，如下：
---------------------free chunk list details------------------------
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
----------------------End free chunk list---------------------------
可见，空闲块成功地加入到了空闲块链表中，与上一步的结果是对应的。
4.1.5把垃圾收集后堆的状态打印出来，如下：
scan heap(@ head of object, # active, * garbage, _ free):
______@#####_______@#####______@#####
对比步骤4.1.2，非活动对象都变成了空闲块，说明垃圾回收成功！
4.2测试二：从空闲块中分配内存
本次测试从空闲块中可以找到一个空闲块来分配给对象。
创建一个对象，并加入到根对象集合：
obj7 = new_object();
OBJ_SET_INT(obj7, , );
root[] = obj7;
分配内存的调试输出如下：
可见这次创建对象，分配内存是从空闲块分配的，分配了20字节出来，分配的首地址正是第一个空闲块的首地址，从“首次垃圾回收测试”中的输出可知，这是OK的。
4.2.1活动对象
object[] at:
=>object[] at:
=>object[] at:
object[] at:
与预期吻合。
4.2.2收集前堆的状态
scan heap(@ head of object, # active, * garbage, _ free):
@#####_@#####_______@#####______@#####
第一个活动对象与第二个活动对象之间隔了一个4字节大小的空闲块，是因为原来第一个空闲块是24字节，而给对象
object[7]
分配内存时只用了20个字节。
4.2.3垃圾收集
sweep_garbage:
object[] at is active
___skip free chunk: start_addr=F60,size=
object[] at is active
___skip free chunk: start_addr=F78,size=
object[] at is active
___skip free chunk: start_addr=FA8,size=
object[] at is active
没有发现垃圾，正常！
4.2.4空闲块链表
---------------------free chunk list details------------------------
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
----------------------End free chunk list---------------------------
第一个空闲块只剩4个字节了，首地址增加了20个字节。其它空闲块没有变。
4.2.5收集后堆的状态
@#####_@#####_______@#####______@#####
因为没有发现垃圾，所以与收集前的一样。
4.3 测试三：分配大一点的对象
本次测试分配大一点的对象，使得遍历空闲块链表后不能找到合适的块，需要从堆的未分配空间中分配。仅仅是创建该对象，没有与其他对象相关联，也没有加入到根对象集合中，因此，该对象会成为垃圾。
当前，空闲块链表最大的块为28字节，这里创建一个36字节大小的对象。
代码如下：
obj8 = new_object();
OBJ_SET_INT(obj8, , );
分配内存的调试输出如下：
可见并没有在空闲块中分配，而是在堆的未分配空间中分配的。
4.3.1活动对象
object[] at:
=>object[] at:
=>object[] at:
object[] at:
因为新创建的对象没有与其他对象相关联，也没有加入到根对象集合中，所以该步骤本次测试输出的结果与“测试二”一样。
4.3.2收集前堆的状态
scan heap(@ head of object, # active, * garbage, _ free):
@#####_@#####_______@#####______@#####@*********
本次测试创建的对象是在堆的未分配空间中分配的，刚好挨着最后一个对象。
正如我们的预期，新创建的对象是非活动对象，即将变成垃圾被回收。
4.3.3垃圾收集过程
sweep_garbage:
object[] at is active
___skip free chunk: start_addr=F60,size=
object[] at is active
___skip free chunk: start_addr=F78,size=
object[] at is active
___skip free chunk: start_addr=FA8,size=
object[] at is active
object[] at is Garbage, size=
[-> insert into list]
正如我们的预期，
object[8] at 0x00120FD4 is Garbage, size=36
，新创建的对象被回收了。
4.3.4空闲块链表
---------------------free chunk list details------------------------
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
----------------------End free chunk list---------------------------
与前一个步骤反映的是同一个事情，该对象被正确加入到空闲块链表了。
4.3.5回收后堆的状态
scan heap(@ head of object, # active, * garbage, _ free):
@#####_@#####_______@#####______@#####_________
综合对比前面的步骤，可知该步骤的输出如实反映了堆中内存的状态。
4.4 测试四：从空闲块链表中查找多次才找到
本次测试分配中等大小的内存，需要从空闲块中查找多次才能找到。
当前空闲块链表中最大的空闲块为36字节，其次为28字节，因此，本次分配的内存大小定为32字节。
obj9 = new_object();
OBJ_SET_INT(obj9, , );
OBJ_SET_OBJ(root[], , obj9);
该对象被根对象集合中的某个对象引用了，因此是活动对象。
分配内存的调试输出如下：
可见，是从空闲块链表中分配的。
4.4.1活动对象
object[] at:
=>object[] at:
=>object[] at:
object[] at:
=>object[] at:
object[9]
被根对象
object[7]
引用。
4.4.2收集前堆的状态
scan heap(@ head of object, # active, * garbage, _ free):
@#####_@#####_______@#####______@#####@########_
查看最后一个对象，可见确实分配到了那个地址，剩下了4个字节的空闲块。
4.4.3垃圾收集
sweep_garbage:
object[] at is active
___skip free chunk: start_addr=F60,size=
object[] at is active
___skip free chunk: start_addr=F78,size=
object[] at is active
___skip free chunk: start_addr=FA8,size=
object[] at is active
object[] at is active
___skip free chunk: start_addr=FF4,size=
上面的输出完整的描述了遍历堆的完整过程。
4.4.4空闲块链表
---------------------free chunk list details------------------------
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
----------------------End free chunk list---------------------------
与前一个测试相比，最后一个空闲块由36字节变成了4个字节。
4.4.5收集后堆的状态
scan heap(@ head of object, # active, * garbage, _ free):
@#####_@#####_______@#####______@#####@########_
由于没有出现垃圾，所以与收集前的一样。
4.5测试五：空闲块的后向合并
这次测试空闲块加入到链表时后向合并相邻空闲块的功能。
把第四次测试中创建的对象
object[9]
变成非活动对象：
OBJ_SET_OBJ(root[], , NULL);
4.5.1活动对象
object[] at:
=>object[] at:
=>object[] at:
object[] at:
正如我们预期，
object[7]
不再引用
object[9]
了。
4.5.2收集前堆的状态
scan heap(@ head of object, # active, * garbage, _ free):
@#####_@#####_______@#####______@#####@********_
果然，“测试四”中创建的
object[9]
变成非活动对象了，它后面跟着4个字节的空闲块。
4.5.3垃圾收集
sweep_garbage:
object[] at is active
___skip free chunk: start_addr=F60,size=
object[] at is active
___skip free chunk: start_addr=F78,size=
object[] at is active
___skip free chunk: start_addr=FA8,size=
object[] at is active
object[] at is Garbage, size=
[=>back merge]
___skip free chunk: start_addr=FF4,size=
收集
object[9]
时，打印出了
[=>back merge]
，就是跟后面的4个字节的空闲块合并了。
4.5.4空闲块链表
---------------------free chunk list details------------------------
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
----------------------End free chunk list---------------------------
后向合并成功，空闲块链表又回到了“测试三”时的情况。
4.5.5收集后堆的状态
scan heap(@ head of object, # active, * garbage, _ free):
@#####_@#####_______@#####______@#####_________
跟“测试三”同一步骤的打印结果一模一样。
4.6测试六：空闲块的前后向合并
该次测试，测试空闲块的前向合并与后向合并同时发生的情形。
记得在“首次测试”中，
object[2]
和
object[4]
均变成了垃圾。这次测试把
object[3]
也变成垃圾，这样就可以测试到前向合并与后向合并同时发生的情形。
4.6.1活动对象
object[] at:
=>object[] at:
object[] at:
可见，活动对象中确实没有
object[3]
了，原来是
object[1]->object[3]->object[5]
。
4.6.2堆的状态
scan heap(@ head of object, # active, * garbage, _ free):
@#####_@#####_______@*****______@#####_________
看到中间的
@*****
，确实如我们所料。
4.6.3垃圾收集
sweep_garbage:
object[] at is active
___skip free chunk: start_addr=F60,size=
object[] at is active
___skip free chunk: start_addr=F78,size=
object[] at is Garbage, size=
[<==> back and forward merge]
___skip free chunk: start_addr=FA8,size=
object[] at is active
___skip free chunk: start_addr=FD4,size=
在回收
object[3]
时，打印出了
[<==> back and forward merge]
。可见是发生了前后向合并。
4.6.4空闲块链表
---------------------free chunk list details------------------------
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
chunk[]: start_addr=, size=
----------------------End free chunk list---------------------------
三个相邻的空闲块合并后，变成了一个大的空闲块，28+20+24=72。
4.6.5收集后堆的状态
scan heap(@ head of object, # active, * garbage, _ free):
@#####_@#####__________________@#####_________
确实可以看到一个大的空闲块：
__________________
。
综上，空闲块加入到空闲块链表时，前后向合并是OK的。
5.总结
以上测试均OK，说明本文的“标记-清除算法“是OK的，该算法的总体思路大致如此，具体应用则需要具体设计了。