如何實現與平臺無關的垃圾回收器？

基本上，我有興趣編寫一個平臺無關垃圾回收器C，可能使用標記和掃描算法或它的一個常見變體。理想地，該接口將大致如下工作：如何實現與平臺無關的垃圾回收器？

（1）gc_alloc()分配內存

（2）重新分配gc_realloc()存儲器

（3）gc_run()運行垃圾收集器。

我已經看過由Boehm等開發的libgc垃圾收集庫。 al。，但它不是平臺無關的;它只是被移植到許多不同的系統。我想實現一個垃圾收集器，其中不包含與系統相關的代碼。速度不是巨大的問題。

有什麼建議嗎？

來源

2011-02-11 Thomas Larsen

你不能走棧尋找GC根與平臺無關的，因爲純C提供到堆棧作爲一個沒有訪問整個。 – 2011-02-11 12:51:14

@bdonlan：好點，我已經通過了我以前的一些問題，並接受了最好的答案。 – 2011-02-11 12:54:18

不幸的是，它不是真的有可能使一個真正與平臺無關的垃圾C.收集C標準的嚴格解讀允許任何類型（除unsigned char）有陷阱位 - 位，當他們有錯誤的值，導致系統發出異常信號（即未定義的行爲）。當掃描分配的指針塊時，您無法確定特定的內存塊是否包含合法的指針值，或者只要您嘗試查看其中的值就會陷入陷阱。

作爲整數檢查指針也沒有幫助 - 無需int類型就可以使表示與指針兼容。 intptr_t僅適用於最近的編譯器，我不認爲它的表示也需要兼容。並且整數也可以具有陷阱。

您也不知道指針的對齊要求。在指針沒有對齊要求的平臺上（即可以從任何字節開始），這意味着您需要停止每個字節memcpy以適合指針類型並檢查結果。哦，不同的指針類型也可以有不同的表示，這也是不可避免的。

但是更大的問題是找到根集。 Bohem GC和其他人傾向於掃描堆棧以及靜態數據，以查找應該放在根集中的指針。 沒有操作系統的內存佈局知識，這是不可能的。因此，您需要讓用戶明確標記根集的成員，這種方式會擊敗垃圾收集器的點。

因此，簡而言之，你不能讓一個GC在真正便攜式C.原則上你可以，如果你做一些假設：

假設根集將被明確給你由用戶。
假設指針或int表示中沒有陷阱位。
假設intptr_t可或承擔全部void * s的嚴格排序（即<和>合理的工作與來自不同malloc ations指針）
假設所有的數據指針類型具有代表性與void *兼容。
可選，但提供了很大的速度提升：硬編碼指針的對齊（這遠非通用，需要編譯器和平臺特定）這個假設可以讓您跳過指向已知對齊的指針位置，並且還會減少潛在指針的數量來檢查。

如果你做出這些假設，你應該能夠做出一個保守的標記掃描分配器。使用二叉樹來保存關於分配位置的信息，並掃描分配的指針塊中可能對齊的指針位置。但是，明確提供根集的必要性將使這一切毫無意義 - 它將重新變爲malloc和free，除了對於某些不明確定義的對象集合，您可以跳過它。不是GC應該提供什麼，但我想它可能有其作爲例如虛擬機的一部分的位置（在這種情況下，根集合將從虛擬機可用的信息中導出）。

請注意，這僅適用於保守的 GC - 即盲目工作的那些，在數據中掃描指針而不知道它可能在哪裏。如果您正在使用虛擬機，那麼要容易得多 - 您可以爲虛擬機創建所有分配的統一數據類型，並明確列出可以找到指針的位置。有了這個加上一個明確的根集，你可以構建一個非保守的GC;這應該足以構建虛擬機或解釋器。

來源

2011-02-11 12:59:31 bdonlan

對於標記和掃描算法，你真正需要做的是計算哪些對象可以從根集到達，對嗎？（這是前一陣子，因爲我挖掘到這...）

這可以由一個單獨的GC管理對象的對象圖來管理，而「所有」您需要做的是添加函數來正確管理圖表分配或修改管理對象時的圖形。如果您還爲託管對象添加引用計數，則可以更輕鬆地計算哪些數據可以從堆棧引用直接訪問。

這應該可能寫出相當平臺無關的，雖然這可能是爭論是否真的垃圾收集器。

簡單的僞代碼來說明我的意思通過引用計數和圖形管理：

some_object * pObject = gc_alloc(sizeof(some_object)); 
some_container * pContainer = gc_alloc(sizeof(some_container)); 

pContainer->pObject = pObject; 
/* let the GC know that pContainer has a reference to pObject */ 
gc_object_reference(pContainer, pObject); 

/* a new block of some kind */ 
{ 
    /* let the GC know we have a new reference for pObject */ 
    some_object * pReference = gc_reference(pObject); 

    /* do stuff */ 
    ... 

    /* let the GC know that this reference is no longer used */ 
    gc_left_scope(pReference); 
} 

gc_left_scope(pObject); 
gc_run(); /* should not be able to recycle anything, since there still is a live 
      * reference to pContainer, and that has a reference to pObject 
      */

來源

2011-02-11 13:36:04 Christoffer

如何實現與平臺無關的垃圾回收器？

回答

相關問題