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

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

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