用嵌入式 C 語言，設(shè)計一種垃圾內(nèi)存回收機制。

工程師進階筆記 · 發(fā)表于 2024-12-6 17:50:00

我是老溫，一名熱愛學(xué)習(xí)的嵌入式工程師
關(guān)注我，一起變得更加優(yōu)秀！
工程師們似乎認為編寫垃圾回收機制是很難的，是一種只有少數(shù)智者和Hans Boehm(et al)才能理解的高深魔法。我認為編寫垃圾回收最難的地方就是內(nèi)存分配，這和閱讀 K&R 所寫的 malloc 樣例難度是相當(dāng)?shù)摹?br /> 在開始之前有一些重要的事情需要說明一下：
第一，我們所寫的代碼是基于Linux Kernel的，注意是Linux Kernel而不是GNU/Linux。
第二，我們的代碼是32bit的。
第三，請不要直接使用這些代碼。我并不保證這些代碼完全正確，可能其中有一些我還未發(fā)現(xiàn)的小的bug，但是整體思路仍然是正確的。好了，讓我們開始吧。
1編寫malloc
最開始，我們需要寫一個內(nèi)存分配器(memmory allocator)，也可以叫做內(nèi)存分配函數(shù)(malloc function)。2 B0 p4 ^5 m" m9 T1 V8 F- T
最簡單的內(nèi)存分配實現(xiàn)方法就是維護一個由空閑內(nèi)存塊組成的鏈表，這些空閑內(nèi)存塊在需要的時候被分割或分配。
當(dāng)用戶請求一塊內(nèi)存時，一塊合適大小的內(nèi)存塊就會從鏈表中被移除并分配給用戶。
如果鏈表中沒有合適的空閑內(nèi)存塊存在，而且更大的空閑內(nèi)存塊已經(jīng)被分割成小的內(nèi)存塊了或內(nèi)核也正在請求更多的內(nèi)存(譯者注：就是鏈表中的空閑內(nèi)存塊都太小不足以分配給用戶的情況)。
那么此時，會釋放掉一塊內(nèi)存并把它添加到空閑塊鏈表中。
在鏈表中的每個空閑內(nèi)存塊都有一個頭(header)用來描述內(nèi)存塊的信息。我們的header包含兩個部分，第一部分表示內(nèi)存塊的大小，第二部分指向下一個空閑內(nèi)存塊。
將頭(header)內(nèi)嵌進內(nèi)存塊中是唯一明智的做法，而且這樣還可以享有字節(jié)自動對齊的好處，這很重要。
由于我們需要同時跟蹤我們“當(dāng)前使用過的內(nèi)存塊”和“未使用的內(nèi)存塊”，因此除了維護空閑內(nèi)存的鏈表外，我們還需要一條維護當(dāng)前已用內(nèi)存塊的鏈表(為了方便，這兩條鏈表后面分別寫為“空閑塊鏈表”和“已用塊鏈表”)。
我們從空閑塊鏈表中移除的內(nèi)存塊會被添加到已用塊鏈表中，反之亦然。
現(xiàn)在我們差不多已經(jīng)做好準備來完成malloc實現(xiàn)的第一步了。但是再那之前，我們需要知道怎樣向內(nèi)核申請內(nèi)存。
動態(tài)分配的內(nèi)存會駐留在一個叫做堆(heap)的地方，堆是介于棧(stack)和BSS(未初始化的數(shù)據(jù)段－你所有的全局變量都存放在這里且具有默認值為0)之間的一塊內(nèi)存。
堆(heap)的內(nèi)存地址起始于(低地址)BSS段的邊界，結(jié)束于一個分隔地址(這個分隔地址是已建立映射的內(nèi)存和未建立映射的內(nèi)存的分隔線)。
為了能夠從內(nèi)核中獲取更多的內(nèi)存，我們只需提高這個分隔地址。為了提高這個分隔地址我們需要調(diào)用一個叫作 sbrk 的Unix系統(tǒng)的系統(tǒng)調(diào)用，
這個函數(shù)可以根據(jù)我們提供的參數(shù)來提高分隔地址，如果函數(shù)執(zhí)行成功則會返回以前的分隔地址，如果失敗將會返回－1。
利用我們現(xiàn)在知道的知識，我們可以創(chuàng)建兩個函數(shù)：morecore()和add_to_free_list()。
當(dāng)空閑塊鏈表缺少內(nèi)存塊時，我們調(diào)用morecore()函數(shù)來申請更多的內(nèi)存。由于每次向內(nèi)核申請內(nèi)存的代價是昂貴的，我們以頁(page-size)為單位申請內(nèi)存。
頁的大小在這并不是很重要的知識點，不過這有一個很簡單解釋：頁是虛擬內(nèi)存映射到物理內(nèi)存的最小內(nèi)存單位。
接下來我們就可以使用add_to_list()將申請到的內(nèi)存塊加入空閑塊鏈表。
現(xiàn)在我們有了兩個有力的函數(shù)，接下來我們就可以直接編寫malloc函數(shù)了。
我們掃描空閑塊鏈表當(dāng)遇到第一塊滿足要求的內(nèi)存塊(內(nèi)存塊比所需內(nèi)存大即滿足要求)時，停止掃描，而不是掃描整個鏈表來尋找大小最合適的內(nèi)存塊，我們所采用的這種算法思想其實就是首次適應(yīng)(與最佳適應(yīng)相對)。
注意：有件事情需要說明一下，內(nèi)存塊頭部結(jié)構(gòu)中size這一部分的計數(shù)單位是塊(Block)，而不是Byte。
注意這個函數(shù)的成功與否，取決于我們第一次使用時是否使 freep = &base 。這點我們會在初始化函數(shù)中進行設(shè)置。
盡管我們的代碼完全沒有考慮到內(nèi)存碎片，但是它能工作。既然它可以工作，我們就可以開始下一個有趣的部分－垃圾回收！
2標記與清掃
我們說過垃圾回收器會很簡單，因此我們盡可能的使用簡單的方法：標記和清除方式。這個算法分為兩個部分：
首先，我們需要掃描所有可能存在指向堆中數(shù)據(jù)(heap data)的變量的內(nèi)存空間并確認這些內(nèi)存空間中的變量是否指向堆中的數(shù)據(jù)。
為了做到這點，對于可能內(nèi)存空間中的每個字長(word-size)的數(shù)據(jù)塊，我們遍歷已用塊鏈表中的內(nèi)存塊。
如果數(shù)據(jù)塊所指向的內(nèi)存是在已用鏈表塊中的某一內(nèi)存塊中，我們對這個內(nèi)存塊進行標記。
第二部分是，當(dāng)掃描完所有可能的內(nèi)存空間后，我們遍歷已用塊鏈表將所有未被標記的內(nèi)存塊移到空閑塊鏈表中。
現(xiàn)在很多人會開始認為只是靠編寫類似于malloc那樣的簡單函數(shù)來實現(xiàn)C的垃圾回收是不可行的，因為在函數(shù)中我們無法獲得其外面的很多信息。
例如，在C語言中沒有函數(shù)可以返回分配到堆棧中的所有變量的哈希映射。但是只要我們意識到兩個重要的事實，我們就可以繞過這些東西：
第一，在C中，你可以嘗試訪問任何你想訪問的內(nèi)存地址。因為不可能有一個數(shù)據(jù)塊編譯器可以訪問但是其地址卻不能被表示成一個可以賦值給指針的整數(shù)。
如果一塊內(nèi)存在C程序中被使用了，那么它一定可以被這個程序訪問。這是一個令不熟悉C的編程者很困惑的概念，因為很多編程語言都會限制程序訪問虛擬內(nèi)存，但是C不會。
第二，所有的變量都存儲在內(nèi)存的某個地方。這意味著如果我們可以知道變量們的通常存儲位置，我們可以遍歷這些內(nèi)存位置來尋找每個變量的所有可能值。
另外，因為內(nèi)存的訪問通常是字(word-size)對齊的，因此我們僅需要遍歷內(nèi)存區(qū)域中的每個字(word)即可。
局部變量也可以被存儲在寄存器中，但是我們并不需要擔(dān)心這些因為寄存器經(jīng)常會用于存儲局部變量，而且當(dāng)函數(shù)被調(diào)用的時候他們通常會被存儲在堆棧中。
現(xiàn)在我們有一個標記階段的策略：遍歷一系列的內(nèi)存區(qū)域并查看是否有內(nèi)存可能指向已用塊鏈表。編寫這樣的一個函數(shù)非常的簡潔明了：
為了確保我們只使用頭(header)中的兩個字長(two words)我們使用一種叫做標記指針(tagged pointer)的技術(shù)。
利用header中的next指針指向的地址總是字對齊(word aligned)這一特點，我們可以得出指針低位的幾個有效位總會是0。
因此我們將next指針的最低位進行標記來表示當(dāng)前塊是否被標記。
現(xiàn)在，我們可以掃描內(nèi)存區(qū)域了，但是我們應(yīng)該掃描哪些內(nèi)存區(qū)域呢？我們要掃描的有以下這些：
BBS(未初始化數(shù)據(jù)段)和初始化數(shù)據(jù)段。這里包含了程序的全局變量和局部變量。因為他們有可能應(yīng)用堆(heap)中的一些東西，所以我們需要掃描BSS與初始化數(shù)據(jù)段，已用的數(shù)據(jù)塊。
當(dāng)然，如果用戶分配一個指針來指向另一個已經(jīng)被分配的內(nèi)存塊，我們不會想去釋放掉那個被指向的內(nèi)存塊。堆棧。因為堆棧中包含所有的局部變量，因此這可以說是最需要掃描的區(qū)域了。
我們已經(jīng)了解了關(guān)于堆(heap)的一切，因此編寫一個mark_from_heap函數(shù)將會非常簡單：
幸運的是對于BSS段和已初始化數(shù)據(jù)段，大部分的現(xiàn)代unix鏈接器可以導(dǎo)出 etext 和 end 符號。etext符號的地址是初始化數(shù)據(jù)段的起點(the last address past the text segment，這個段中包含了程序的機器碼)，end符號是堆(heap)的起點。
因此，BSS和已初始化數(shù)據(jù)段位于 &etext 與 &end 之間。這個方法足夠簡單，當(dāng)不是平臺獨立的。
堆棧這部分有一點困難。堆棧的棧頂非常容易找到，只需要使用一點內(nèi)聯(lián)匯編即可，因為它存儲在 sp 這個寄存器中。但是我們將會使用的是 bp 這個寄存器，因為它忽略了一些局部變量。
尋找堆棧的的棧底(堆棧的起點)涉及到一些技巧。出于安全因素的考慮，內(nèi)核傾向于將堆棧的起點隨機化，因此我們很難得到一個地址。
老實說，我在尋找棧底方面并不是專家，但是我有一些點子可以幫你找到一個準確的地址。
( K6 W# ?9 U: c' k. B$ W3 w一個可能的方法是，你可以掃描調(diào)用棧(call stack)來尋找 env 指針，這個指針會被作為一個參數(shù)傳遞給主程序。
另一種方法是從棧頂開始讀取每個更大的后續(xù)地址并處理inexorible SIGSEGV。
) ?. U6 h `' R: d但是我們并不打算采用這兩種方法中的任何一種，我們將利用linux會將棧底放入一個字符串并存于proc目錄下表示該進程的文件中這一事實。這聽起來很愚蠢而且非常間接。
值得慶幸的是，我并不感覺這樣做是滑稽的，因為它和Boehm GC中尋找棧底所用的方法完全相同。
現(xiàn)在我們可以編寫一個簡單的初始化函數(shù)。
在函數(shù)中，我們打開proc文件并找到棧底。棧底是文件中第28個值，因此我們忽略前27個值。Boehm GC和我們的做法不同的是他僅使用系統(tǒng)調(diào)用來讀取文件來避免讓stdlib庫使用堆(heap)，但是我們并不在意這些。
現(xiàn)在我們知道了每個我們需要掃描的內(nèi)存區(qū)域的位置，所以我們終于可以編寫顯示調(diào)用的回收函數(shù)了：
朋友們，所有的東西都已經(jīng)在這了，一個用C為C程序編寫的垃圾回收器。這些代碼自身并不是完整的，它還需要一些微調(diào)來使它可以正常工作，但是大部分代碼是可以獨立工作的。
3總結(jié)
一開始就打算編寫完整的程序是很困難的，你編程的唯一算法就是分而治之。
先編寫內(nèi)存分配函數(shù)，然后編寫查詢內(nèi)存的函數(shù)，然后是清除內(nèi)存的函數(shù)。最后將它們合在一起。
當(dāng)你在編程方面克服這個障礙后，就再也沒有困難的實踐了。你可能有一個算法不太了解，但是任何人只要有足夠的時間就肯定可以通過論文或書理解這個算法。
如果有一個項目看起來令人生畏，那么將它分成完全獨立的幾個部分。
你可能不懂如何編寫一個解釋器，但你絕對可以編寫一個分析器，然后看一下你還有什么需要添加的，添上它。相信自己，終會成功！
來源：https://www.lmlphp.com/user/1774/article/item/19294/
-END-
往期推薦：點擊圖片即可跳轉(zhuǎn)閱讀