編程實戰：C語言制作垃圾回收器

來源：https://www.lmlphp.com/user/1774/article/item/19294/

編輯整理：技術讓夢想更偉大 | 李肖遙

人們似乎認為編寫垃圾回收機制是很難的，是一種只有少數智者和Hans Boehm(et al)才能理解的高深魔法。我認為編寫垃圾回收最難的地方就是內存分配，這和閱讀K&R所寫的malloc樣例難度是相當的。

在開始之前有一些重要的事情需要說明一下：第一，我們所寫的代碼是基于Linux Kernel的，注意是Linux Kernel而不是GNU/Linux。第二，我們的代碼是32bit的。第三，請不要直接使用這些代碼。我并不保證這些代碼完全正確，可能其中有一些我還未發現的小的bug，但是整體思路仍然是正確的。好了，讓我們開始吧。

編寫malloc

最開始，我們需要寫一個內存分配器(memmory allocator)，也可以叫做內存分配函數(malloc function)。最簡單的內存分配實現方法就是維護一個由空閑內存塊組成的鏈表，這些空閑內存塊在需要的時候被分割或分配。當用戶請求一塊內存時，一塊合適大小的內存塊就會從鏈表中被移除并分配給用戶。如果鏈表中沒有合適的空閑內存塊存在，而且更大的空閑內存塊已經被分割成小的內存塊了或內核也正在請求更多的內存(譯者注：就是鏈表中的空閑內存塊都太小不足以分配給用戶的情況)。那么此時，會釋放掉一塊內存并把它添加到空閑塊鏈表中。

在鏈表中的每個空閑內存塊都有一個頭(header)用來描述內存塊的信息。我們的header包含兩個部分，第一部分表示內存塊的大小，第二部分指向下一個空閑內存塊。

將頭(header)內嵌進內存塊中是唯一明智的做法，而且這樣還可以享有字節自動對齊的好處，這很重要。

由于我們需要同時跟蹤我們“當前使用過的內存塊”和“未使用的內存塊”，因此除了維護空閑內存的鏈表外，我們還需要一條維護當前已用內存塊的鏈表(為了方便，這兩條鏈表后面分別寫為“空閑塊鏈表”和“已用塊鏈表”)。我們從空閑塊鏈表中移除的內存塊會被添加到已用塊鏈表中，反之亦然。

現在我們差不多已經做好準備來完成malloc實現的第一步了。但是再那之前，我們需要知道怎樣向內核申請內存。

動態分配的內存會駐留在一個叫做堆(heap)的地方，堆是介于棧(stack)和BSS(未初始化的數據段－你所有的全局變量都存放在這里且具有默認值為0)之間的一塊內存。堆(heap)的內存地址起始于(低地址)BSS段的邊界，結束于一個分隔地址(這個分隔地址是已建立映射的內存和未建立映射的內存的分隔線)。為了能夠從內核中獲取更多的內存，我們只需提高這個分隔地址。為了提高這個分隔地址我們需要調用一個叫作 sbrk 的Unix系統的系統調用，這個函數可以根據我們提供的參數來提高分隔地址，如果函數執行成功則會返回以前的分隔地址，如果失敗將會返回－1。

利用我們現在知道的知識，我們可以創建兩個函數：morecore()和add_to_free_list()。當空閑塊鏈表缺少內存塊時，我們調用morecore()函數來申請更多的內存。由于每次向內核申請內存的代價是昂貴的，我們以頁(page-size)為單位申請內存。頁的大小在這并不是很重要的知識點，不過這有一個很簡單解釋：頁是虛擬內存映射到物理內存的最小內存單位。接下來我們就可以使用add_to_list()將申請到的內存塊加入空閑塊鏈表。

現在我們有了兩個有力的函數，接下來我們就可以直接編寫malloc函數了。我們掃描空閑塊鏈表當遇到第一塊滿足要求的內存塊(內存塊比所需內存大即滿足要求)時，停止掃描，而不是掃描整個鏈表來尋找大小最合適的內存塊，我們所采用的這種算法思想其實就是首次適應(與最佳適應相對)。

注意：有件事情需要說明一下，內存塊頭部結構中size這一部分的計數單位是塊(Block)，而不是Byte。

注意這個函數的成功與否，取決于我們第一次使用時是否使 freep = &base 。這點我們會在初始化函數中進行設置。

盡管我們的代碼完全沒有考慮到內存碎片，但是它能工作。既然它可以工作，我們就可以開始下一個有趣的部分－垃圾回收！

標記和清掃

我們說過垃圾回收器會很簡單，因此我們盡可能的使用簡單的方法：標記和清除方式。這個算法分為兩個部分：

首先，我們需要掃描所有可能存在指向堆中數據(heap data)的變量的內存空間并確認這些內存空間中的變量是否指向堆中的數據。為了做到這點，對于可能內存空間中的每個字長(word-size)的數據塊，我們遍歷已用塊鏈表中的內存塊。如果數據塊所指向的內存是在已用鏈表塊中的某一內存塊中，我們對這個內存塊進行標記。

第二部分是，當掃描完所有可能的內存空間后，我們遍歷已用塊鏈表將所有未被標記的內存塊移到空閑塊鏈表中。

現在很多人會開始認為只是靠編寫類似于malloc那樣的簡單函數來實現C的垃圾回收是不可行的，因為在函數中我們無法獲得其外面的很多信息。例如，在C語言中沒有函數可以返回分配到堆棧中的所有變量的哈希映射。但是只要我們意識到兩個重要的事實，我們就可以繞過這些東西：

第一，在C中，你可以嘗試訪問任何你想訪問的內存地址。因為不可能有一個數據塊編譯器可以訪問但是其地址卻不能被表示成一個可以賦值給指針的整數。如果一塊內存在C程序中被使用了，那么它一定可以被這個程序訪問。這是一個令不熟悉C的編程者很困惑的概念，因為很多編程語言都會限制程序訪問虛擬內存，但是C不會。

第二，所有的變量都存儲在內存的某個地方。這意味著如果我們可以知道變量們的通常存儲位置，我們可以遍歷這些內存位置來尋找每個變量的所有可能值。另外，因為內存的訪問通常是字(word-size)對齊的，因此我們僅需要遍歷內存區域中的每個字(word)即可。

局部變量也可以被存儲在寄存器中，但是我們并不需要擔心這些因為寄存器經常會用于存儲局部變量，而且當函數被調用的時候他們通常會被存儲在堆棧中。

現在我們有一個標記階段的策略：遍歷一系列的內存區域并查看是否有內存可能指向已用塊鏈表。編寫這樣的一個函數非常的簡潔明了：

為了確保我們只使用頭(header)中的兩個字長(two words)我們使用一種叫做標記指針(tagged pointer)的技術。利用header中的next指針指向的地址總是字對齊(word aligned)這一特點，我們可以得出指針低位的幾個有效位總會是0。因此我們將next指針的最低位進行標記來表示當前塊是否被標記。

現在，我們可以掃描內存區域了，但是我們應該掃描哪些內存區域呢？我們要掃描的有以下這些：

BBS(未初始化數據段)和初始化數據段。這里包含了程序的全局變量和局部變量。因為他們有可能應用堆(heap)中的一些東西，所以我們需要掃描BSS與初始化數據段。

已用的數據塊。當然，如果用戶分配一個指針來指向另一個已經被分配的內存塊，我們不會想去釋放掉那個被指向的內存塊。

堆棧。因為堆棧中包含所有的局部變量，因此這可以說是最需要掃描的區域了。

我們已經了解了關于堆(heap)的一切，因此編寫一個mark_from_heap函數將會非常簡單：

幸運的是對于BSS段和已初始化數據段，大部分的現代unix鏈接器可以導出 etext 和 end 符號。etext符號的地址是初始化數據段的起點(the last address past the text segment，這個段中包含了程序的機器碼)，end符號是堆(heap)的起點。因此，BSS和已初始化數據段位于 &etext 與 &end 之間。這個方法足夠簡單，當不是平臺獨立的。

堆棧這部分有一點困難。堆棧的棧頂非常容易找到，只需要使用一點內聯匯編即可，因為它存儲在 sp 這個寄存器中。但是我們將會使用的是 bp 這個寄存器，因為它忽略了一些局部變量。

尋找堆棧的的棧底(堆棧的起點)涉及到一些技巧。出于安全因素的考慮，內核傾向于將堆棧的起點隨機化，因此我們很難得到一個地址。老實說，我在尋找棧底方面并不是專家，但是我有一些點子可以幫你找到一個準確的地址。一個可能的方法是，你可以掃描調用棧(call stack)來尋找 env 指針，這個指針會被作為一個參數傳遞給主程序。另一種方法是從棧頂開始讀取每個更大的后續地址并處理inexorible SIGSEGV。但是我們并不打算采用這兩種方法中的任何一種，我們將利用linux會將棧底放入一個字符串并存于proc目錄下表示該進程的文件中這一事實。這聽起來很愚蠢而且非常間接。值得慶幸的是，我并不感覺這樣做是滑稽的，因為它和Boehm GC中尋找棧底所用的方法完全相同。

現在我們可以編寫一個簡單的初始化函數。在函數中，我們打開proc文件并找到棧底。棧底是文件中第28個值，因此我們忽略前27個值。Boehm GC和我們的做法不同的是他僅使用系統調用來讀取文件來避免讓stdlib庫使用堆(heap)，但是我們并不在意這些。

現在我們知道了每個我們需要掃描的內存區域的位置，所以我們終于可以編寫顯示調用的回收函數了：

朋友們，所有的東西都已經在這了，一個用C為C程序編寫的垃圾回收器。這些代碼自身并不是完整的，它還需要一些微調來使它可以正常工作，但是大部分代碼是可以獨立工作的。

總結

一開始就打算編寫完整的程序是很困難的，你編程的唯一算法就是分而治之。先編寫內存分配函數，然后編寫查詢內存的函數，然后是清除內存的函數。最后將它們合在一起。

當你在編程方面克服這個障礙后，就再也沒有困難的實踐了。你可能有一個算法不太了解，但是任何人只要有足夠的時間就肯定可以通過論文或書理解這個算法。如果有一個項目看起來令人生畏，那么將它分成完全獨立的幾個部分。你可能不懂如何編寫一個解釋器，但你絕對可以編寫一個分析器，然后看一下你還有什么需要添加的，添上它。相信自己，終會成功！