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的，該算法的總體思路大緻如此，具體應用則需要具體設計了。