巴德工作小組

Boehm-Demers-Weiser 垃圾收集器

這是 C 和 C++ 保守垃圾收集器的版本 8.3.0（下一個版本開發）。

許可證：麻省理工學院風格

下載

您可能會在下載頁面或 BDWGC 網站上找到更新/穩定的版本。

此外，開發儲存庫中還提供了最新的錯誤修復和新功能。

概述

這是一個通用的垃圾收集儲存分配器。 使用的演算法描述於：

• Boehm, H. 和 M. Weiser，“不合作環境中的垃圾收集”，軟體實踐與經驗，1988 年 9 月，第 807-820 頁。

• Boehm, H.、A. Demers 和 S. Shenker，“Mostly Parallel Garbage Collection”，ACM SIGPLAN '91 程式語言設計和實現會議記錄，SIGPLAN 通知 26, 6（1991 年 6 月），第 157 頁164.

• Boehm, H.，“節省空間的保守垃圾收集”，ACM SIGPLAN '91 程式語言設計和實現會議記錄，SIGPLAN 通知 28, 6（1993 年 6 月），第 197-206 頁。

• Boehm H.，“減少垃圾收集器快取未命中”，2000 年記憶體管理國際研討會論文集。

收集器和最佳化編譯器之間可能的互動在中討論

• Boehm, H. 和 D. Chase，“GC 安全 C 編譯的建議”，《C 語言翻譯雜誌》4, 2（1992 年 12 月）。

• Boehm H.，“簡單 GC 安全編譯”，ACM SIGPLAN '96 程式語言設計和實作會議論文集。

與第二個參考文獻中所述的收集器不同，該收集器在整個收集期間（預設）或在分配期間增量地停止變元的情況下運作。 （後者在較少的機器上受支援。）在最常見的平台上，它可以在有或沒有線程支援的情況下構建。 在某些平台上，它可以利用多處理器來加速垃圾收集。

該收藏家背後的許多想法先前已被其他人探索過。 值得注意的是，Xerox PARC 在20 世紀80 年代初開發的一些運行時系統保守地掃描線程堆疊以定位可能的指針（請參閱Paul Rovner，“將垃圾收集和運行時類型添加到強類型靜態檢查並發語言”施樂帕洛阿爾托研究中心 CSL 84-7)。 Doug McIlroy 編寫了一個更簡單的完全保守的收集器，它是版本 8 UNIX (tm) 的一部分，但似乎並未廣泛使用。

包括使用收集器作為洩漏檢測器的基本工具，以及使用收集器的相當複雜的字串包“線”。 （請參閱 README.cords 和 H.-J. Boehm、R. Atkinson 和 M. Plass，“繩索：繩索的替代品”，軟體實踐和經驗 25, 12（1995 年 12 月），第 1315-1330 頁。與Xerox Cedar 中的「rope」套件非常相似，或SGI STL 或g++ 發行版中的「rope」套件。

更多收集器文件可以在概述中找到。

GitHub 已知客戶端頁面上列出了收集器的一些已知用途。

一般說明

這是一個垃圾收集儲存分配器，旨在用作 C 的 malloc 的插件替代品。

由於收集器不需要標記指針，因此它不會嘗試確保回收所有不可存取的儲存空間。 然而，根據我們的經驗，它在回收未使用的記憶體方面通常比大多數使用明確釋放的 C 程式更成功。 與手動引入的洩漏不同，未回收的內存量通常保持有限。

在下文中，「物件」被定義為由下述例程指派的記憶體區域。

任何不打算收集的物件必須從其他此類可存取物件或從暫存器、堆疊、資料或靜態分配的 bss 段指向。 堆疊或暫存器中的指標可以指向物件內的任何位置。如果收集器是使用定義的ALL_INTERIOR_POINTERS進行編譯的，或者以其他方式設定了GC_all_interior_pointers （現在是預設值），則堆疊指標也是如此。

不使用ALL_INTERIOR_POINTERS進行編譯可能需要從堆到物件開頭的指針，從而減少垃圾物件的意外保留。 但對於大多數佔用一小部分可能地址空間的程式來說，這似乎不再是一個重要問題。

有許多修改指標識別演算法的例程。即使未定義ALL_INTERIOR_POINTERS ， GC_register_displacement也允許識別某些內部指標。 GC_malloc_ignore_off_page允許忽略一些指向大物件中間的指針，大大降低了意外保留大物件的機率。 對於大多數目的，如果您從非常大的物件的分配中收到收集器警告，似乎最好使用ALL_INTERIOR_POINTERS進行編譯並使用GC_malloc_ignore_off_page 。 詳細資訊請參閱此處。

警告：垃圾收集器看不到由標準（系統） malloc分配的記憶體內的指標。 因此，僅從這樣的區域指向的物件可能會被過早釋放。 因此，建議標準malloc僅用於保證不包含指向垃圾可收集記憶體的指標的記憶體區域，例如 I/O 緩衝區。 C 語言自動、靜態或暫存器變數中的指標可以正確辨識。 （請注意， GC_malloc_uncollectable語意與標準 malloc 類似，但分配由收集器追蹤的物件。）

警告：收集器並不總是知道如何在與動態庫關聯的資料區域中尋找指標。 如果您知道如何在作業系統上尋找這些資料區域（請參閱GC_add_roots ），那麼這很容易解決。 預設情況下，包含並使用在 SunOS、IRIX 5.X 和 6.X、HP/UX、Alpha OSF/1、Linux 和 Win32 下執行此操作的程式碼。 （有關 Windows 詳細信息，請參閱 README.win32 和 README.win64。）在其他系統上，收集器可能不會考慮來自動態庫資料區域的指標。 如果您正在編寫一個依賴收集器掃描動態庫資料區域的程序，那麼至少包含一次對GC_is_visible呼叫以確保這些區域對收集器可見可能是一個好主意。

請注意，垃圾收集器不需要被告知共享唯讀資料。 但是，如果共享庫機制可能引入可能包含指標的不連續資料區域，則確實需要通知收集器。

大多數訊號的訊號處理可能會在收集期間以及分配過程的不間斷部分期間被推遲。與標準 ANSI C malloc 一樣，預設情況下，當另一個 malloc 呼叫可能正在進行時，從訊號處理程序呼叫 malloc（和其他 GC 例程）是不安全的。

分配器/收集器也可以配置為執行緒安全操作。 （也可以實現完全的訊號安全，但代價是每個 malloc 需要兩次系統調用，這通常是不可接受的。）

警告：收集器不保證掃描執行緒本地儲存（例如使用pthread_getspecific存取的類型）。 不過，收集器確實會掃描執行緒堆疊，因此通常最好的解決方案是確保儲存在執行緒本地儲存中的任何指標在其生命週期內也儲存在執行緒的堆疊上。 （這可以說是一個長期存在的錯誤，但尚未修復。）

搭建和安裝

建構收集器的方法有多種：

• CMake（這是推薦的方式）

• GNU autoconf/automake

• 之字形（實驗）

• MS nmake（直接）

• 直接產生文件

• 手動C編譯

CMake

建立 libgc（以及 libcord）並使用 cmake 執行測試的最簡單方法：

 mkdir outcd 輸出
cmake -Dbuild_tests=ON ..
cmake --build .ctest

這是建立庫的最跨平台的方式。有關詳細信息，請參閱 README.cmake。

GNU Autoconf/Automake

請注意，收集器來源儲存庫不包含configure和類似的自動生成文件，因此從來源儲存庫基於 autoconf 建立收集器的完整過程可能如下所示：

 ./autogen.sh
./配置
進行檢查

GNU 風格的建置流程了解常用的目標和選項。 make install安裝 libgc 和 libcord。 嘗試./configure --help查看所有設定選項。 目前不可能以這種方式執行建置選項的所有組合。

有關詳細信息，請參閱 README.autoconf。

之字形

使用 zig 建構和測試收集器的最簡單形式是直接的：

 Zig 建置測試

可以透過使用變數來配置構建，例如zig build -Denable_redirect_malloc -Denable_threads=false 。 Zig 提供了出色的交叉編譯功能，它的配置如下：

 zig build -Dtarget=riscv64-linux-musl

目前需要 zig 0.12 的 nightly 版本，可以從 https://ziglang.org/download/ 下載

MS nmake

在 Windows 上，假設已安裝並適當配置了 Microsoft 建置工具，則可以直接使用nmake建置程式庫並執行測試，例如透過鍵入nmake -f NT_MAKEFILE check 。 但是，建議的方法是使用如上所述的 cmake。

有關詳細信息，請參閱 README.win32。

直接產生文件

對於舊式（經典）基於 makefile 的建置過程，輸入make -f Makefile.direct check將自動建置 libgc、libcord，然後執行一些測試，例如gctest 。 此測試是對收集器功能的比較膚淺的測試。 失敗透過核心轉儲或收集器損壞的訊息來指示。 gctest在合理的 2023 年老式 64 位元桌面上運行可能需要十幾秒鐘。它最多可能使用約 30 MB 的記憶體。

Makefile.direct 將產生一個庫 libgc.a，您應該連結到該庫。

手動C編譯

最後，在大多數目標上，可以使用單一編譯器呼叫直接建構和測試收集器，如下所示（範例缺乏多執行緒支援）：

 cc -I include -o gctest測試/gctest.c extra/gc.c && ./gctest

例如，這對於調試目的可能很方便。

可配置的巨集

透過定義 README.macros 檔案中列出的宏，可以在建置過程中更精確地配置庫。

預設情況下，該庫是在啟用線程支援（即線程安全操作）的情況下建立的，除非透過以下方式明確停用：

• -Denable_threads=false傳遞給cmake或zig build選項

• --disable-threads選項傳遞給./configure

收集器在預設配置下靜默運作。如果出現問題，通常可以透過定義GC_PRINT_STATS或GC_PRINT_VERBOSE_STATS環境變數來變更。 這將為每個集合產生幾行描述性輸出。 （給定的統計數據表現出一些特殊性。由於各種原因，事情似乎沒有加起來，最明顯的是碎片損失。這些對於設計的程式gctest可能比您的應用程式更重要。）

原子操作

如果編譯器支援原子內在函數，現在可以選擇使用（克隆） libatomic_ops 。 大多數現代編譯器都是這樣做的。 值得注意的例外是 MS 編譯器（從 Visual Studio 2022 開始）。

如果需要，大多數作業系統發行版都有libatomic_ops包；或者，您可以從 https://github.com/ivmai/libatomic_ops 空間下載或克隆它。

可移植性

目前，收集器設計為在使用平面 32 位元或 64 位元位址空間的機器上運行，基本上無需修改。其中包括絕大多數工作站和 x86（i386 或更高版本）PC。

在少數情況下（例如，OS/2、Win32）會提供單獨的 makefile；它們有一個單獨的特定於主機的 docs/platforms/README.* 檔案。

動態函式庫僅在SunOS/Solaris（甚至在最新的Sun 3 發行版上該支援不起作用）、Linux、FreeBSD、NetBSD、IRIX、HP/UX、Win32（不是win32s）和DEC 上的OSF/1 下取得完全支援AXP 機器以及 dyn_load.c 頂部附近列出的其他一些機器。 在其他計算機上，我們建議您執行以下操作之一：

1. 新增動態庫支援（並將程式碼發送給我們）。

2. 使用庫的靜態版本。

3. 安排動態庫使用標準 malloc。如果庫儲存指向垃圾收集物件的指針，這仍然很危險。但幾乎​​所有標準介面都禁止這樣做，因為它們正確地處理指向堆疊分配物件的指標。 （ strtok是一個例外。不要使用它。）

在所有情況下，我們都假設指針對齊與標準 C 編譯器強制執行的一致。 如果您使用非標準編譯器，您可能必須調整include/private/gc_priv.h中定義的對齊參數。 請注意，這也可能是打包記錄/結構的問題，如果它們強制減少指標的對齊。

到非位元組尋址或不使用 32 位元或 64 位元位址的機器的連接埠將需要付出很大的努力。 要移植到普通的 MSDOS 或 win16 是很困難的。

對於尚未提及的機器或非標準編譯器，此處提供了一些移植建議。

分配器的 C 介面

以下例程旨在由使用者直接呼叫。請注意，通常只需要GC_malloc 。如果收集器必須從非標準位置（例如，從GC_stackbottom器尚未理解的機器上的動態庫資料區域）進行跟踪，則可能需要GC_clear_roots和GC_add_roots呼叫。 （底部）的良好近似值。

客戶端程式碼可能包括gc.h ，它定義了以下所有內容以及許多其他內容。

1. GC_malloc(bytes) - 分配給定大小的物件。 與 malloc 不同，物件在傳回給使用者之前會被清除。當GC_malloc確定合適時，它將呼叫垃圾收集器。如果無法從作業系統取得足夠的空間，GC_malloc 可能會回傳 0。 這是空間不足最可能造成的後果。 其他可能的後果是函數呼叫將由於缺乏堆疊空間而失敗，或者收集器將因無法維護其內部資料結構而以其他方式失敗，或者關鍵的系統進程將失敗並導致機器癱瘓。 大多數這些可能性與 malloc 實作無關。

2. GC_malloc_atomic(bytes) - 指派給定大小的對象，保證不包含任何指標。 不保證傳回的物件被清除。 （始終可以替換為GC_malloc ，但會導致更快的收集時間。如果使用GC_malloc_atomic分配大型字元陣列等，收集器可能會比靜態分配更快地運行。）

3. GC_realloc(object, new_bytes) - 將物件的大小改為給定大小。 傳回指向新物件的指針，該指針可能與舊物件的指針相同，也可能不同。 當且僅當舊物件是原子的時，新物件才被視為原子的。 如果新對像是複合對象且大於原始對象，則新加入的位元組將被清除。這很有可能會分配一個新的物件。

4. GC_free(object) - 明確釋放GC_malloc或GC_malloc_atomic或朋友傳回的物件。 不是必需的，但如果效能至關重要，可以用來最小化集合。 對於非常小的物件（<= 8 位元組）可能會造成效能損失。

5. GC_expand_hp(bytes) - 明確增加堆疊大小。 （如果垃圾收集未能回收足夠的內存，這通常會自動完成。明確調用GC_expand_hp可能會阻止程式啟動時不必要的頻繁收集。）

6. GC_malloc_ignore_off_page(bytes) - 與GC_malloc相同，但客戶端承諾在物件處於活動狀態時保留指向物件的第一個GC 堆疊（512 .. 4096 位元組或甚至更多，取決於配置）內某處的指針。 （該指標通常應聲明為 volatile，以防止編譯器最佳化的干擾。）這是分配可能大於 100 KB 左右的任何內容的建議方法。 （ GC_malloc可能會導致回收此類物件失敗。）

7. GC_set_warn_proc(proc) - 可用來重定向來自收集器的警告。 此類警告應該很少見，並且在程式碼開發過程中不應被忽略。

8. GC_enable_incremental() - 啟用分代和增量收集。 對於提供對頁面髒資訊的存取的機器上的大堆很有用。 一些髒位元實作可能會幹擾調試（透過捕獲位址錯誤）並對系統呼叫的堆參數施加限制（因為系統呼叫內的寫入錯誤可能無法很好地處理）。

9. GC_register_finalizer(object, proc, data, 0, 0)和朋友 - 允許註冊終結代碼。 在物件變得無法存取後，將呼叫使用者提供的終結程式碼 ( (*proc)(object, data) ）。有關更複雜的用途以及最終確定順序問題，請參閱gc.h 。

全域變數GC_free_space_divisor可以從預設值 3 向上調整，以使用較少的空間和更多的收集時間，或向下調整以獲得相反的效果。 將其設為 1 幾乎會停用集合並導致所有分配只會增加堆。

變數GC_non_gc_bytes通常為 0，可以更改以反映上述例程分配的記憶體量，這些記憶體不應被視為收集的候選者。 當然，不小心使用可能會導致記憶體消耗過多。

透過include/private/gc_priv.h頂部附近定義的參數可以進行一些額外的調整。

如果僅打算使用GC_malloc ，則可能適合定義：

#define malloc(n) GC_malloc(n)
#define calloc(m,n) GC_malloc((m)*(n))

對於小塊非常分配密集的程式碼， gc_inline.h包含一些可以用來取代GC_malloc和朋友的分配巨集。

垃圾收集器中的所有外部可見名稱均以GC_開頭。為了避免名稱衝突，客戶端程式碼應避免使用此前綴，存取垃圾收集器例程時除外。

有明確類型資訊分配的規定。這很少是必要的。 詳細資訊可以在gc_typed.h中找到。

分配器的 C++ 接口

收集器的 Ellis-Hull C++ 介麵包含在收集器發行版中。 如果您打算使用它，請鍵入./configure --enable-cplusplus && make （或cmake -Denable_cplusplus=ON . && cmake --build . ，或make -f Makefile.direct c++取決於您使用的建置系統）。這將創建 libgccpp.a 和 libgctba.a 文件，或其等效的共享庫（libgccpp.so 和 libgctba.so）。 您應該連結第一個 (gccpp) 或第二個 (gctba)，但不能同時連結兩者。 有關介面的定義，請參閱gc_cpp.h和此處。此介面嘗試在不更改編譯器的情況下近似 Ellis-Detlefs C++ 垃圾收集建議。

很多時候，還需要使用gc_allocator.h和其中宣告的分配器來建構 STL 資料結構。 否則，STL 資料結構的子物件將使用系統分配器進行分配，並且它們引用的物件可能會過早收集。

用作檢漏儀

收集器可用於追蹤旨在使用 malloc/free 運行的 C 程式中的洩漏（例如，具有極端即時性或可移植性限制的程式碼）。 為此，請在 Makefile 中定義FIND_LEAK 。每當發現未明確釋放的不可存取物件時，這將導致收集器列印人類可讀的物件描述。此類物件也會自動回收。

如果所有物件都指派有GC_DEBUG_MALLOC （請參閱下一節），那麼預設情況下，人類可讀的物件描述將至少包含原始檔案和指派洩漏物件的行號。有時這可能就足夠了。 （在某些機器上，它也會報告一個神秘的堆疊追蹤。如果這不是符號性的，有時可以透過使用tools/callprocs.sh foo呼叫程式「foo」來呼叫符號堆疊追蹤。它是一個短 shell呼叫adb 將程式計數器值擴展為符號位址的腳本主要由Scott Schwartz 提供。

請注意，下一節中描述的偵錯工具有時在洩漏查找模式中可能稍微不太有效，因為在後者中GC_debug_free實際上會導致物件的重複使用。 （否則該物件將被簡單地標記為無效。）此外，請注意，大多數 GC 測試並非設計為在FIND_LEAK模式下有意義地運行。

偵錯設施

例程GC_debug_malloc 、 GC_debug_malloc_atomic 、 GC_debug_realloc和GC_debug_free為收集器提供了備用接口，它為記憶體覆蓋錯誤等提供了一些幫助。以這種方式分配的物件帶有附加資訊註釋。 其中一些資訊會在垃圾收集期間進行檢查，並將檢測到的不一致情況報告給 stderr。

如果明確釋放該對象，或在物件處於活動狀態時呼叫收集器，則應擷取超出已指派對象末尾的寫入的簡單情況。 物件的第一次釋放將清除與該物件關聯的偵錯訊息，因此意外地重複呼叫GC_debug_free將報告物件的釋放而沒有偵錯資訊。 除了傳回NULL之外，記憶體不足錯誤還會回報給 stderr。

首次呼叫此函數時會啟用垃圾收集期間的GC_debug_malloc檢查。 這將導致收集過程中速度減慢。 如果需要頻繁的堆檢查，可以透過明確呼叫GC_gcollect來實現，例如從偵錯器中。

GC_debug_malloc分配的物件不應傳遞給GC_realloc或GC_free ，反之亦然。 但是，如果兩個池保持不同，則可以僅使用GC_debug_malloc分配某些對象，並將GC_malloc用於其他對象。 在這種情況下， GC_malloc分配的物件被誤認為已被覆蓋的可能性非常低。 這種情況發生的機率最多為 2**32 分之一。 如果從未呼叫GC_debug_malloc則此機率為零。

GC_debug_malloc 、 GC_debug_malloc_atomic和GC_debug_realloc採用兩個額外的尾隨參數：一個字串和一個整數。 這些不由分配器解釋。 它們儲存在物件中（不複製字串）。 如果偵測到涉及物件的錯誤，則會列印它們。

也提供了巨集GC_MALLOC 、 GC_MALLOC_ATOMIC 、 GC_REALLOC 、 GC_FREE 、 GC_REGISTER_FINALIZER等。 這些需要與對應的（非調試）例程相同的參數。 如果gc.h包含在定義的GC_DEBUG中，它們將呼叫這些函數的偵錯版本，並在適當的情況下將目前檔案名稱和行號作為兩個額外參數傳遞。 如果包含gc.h時未定義GC_DEBUG ，則所有這些巨集將定義為其非偵錯等效項。 ( GC_REGISTER_FINALIZER是必要的，因為指向帶有調試資訊的物件的指針實際上是指向從物件開始位移16 個位元組的指針，並且在調用終結例程時需要進行一些轉換。有關標頭中存儲的詳細信息，請參閱定義dbg_mlc.c 檔案中的 oh 類型。

增量/分代收集

收集器通常會在垃圾收集標記階段期間中斷客戶端程式碼。 如果對於具有大堆的程式需要互動式回應，這可能是不可接受的。 收集器也可以在「分代」模式下運行，在該模式下，它通常嘗試僅收集自上次垃圾收集以來分配的物件。此外，在此模式下，垃圾收集主要以增量方式運行，回應大量GC_malloc請求中的每一個請求，執行少量工作。

該模式透過呼叫GC_enable_incremental來啟用。

只有當收集器有某種方式來判斷哪些物件或頁面最近被修改時，增量收集和分代收集才能有效減少暫停時間。 收集器使用兩個資訊來源：

1. VM系統提供的資訊。 這可以以多種形式之一來提供。 在 Solaris 2.X 下（也可能在其他類似系統下）可以從 /proc 檔案系統讀取有關髒頁的資訊。在其他系統（例如SunOS4.X）下，可以對堆進行寫入保護，並捕獲由此產生的錯誤。在這些系統上，我們要求寫入堆疊的系統呼叫（讀取除外）由客戶端程式碼專門處理。詳細資訊請參閱os_dep.c 。

2. 程式設計師提供的資訊。 如果程式庫已正確編譯，則在呼叫GC_end_stubborn_change後，該物件被視為髒物件。它通常不值得用於短暫的物件。請注意，由於缺少GC_end_stubborn_change或GC_reachable_here呼叫而導致的錯誤可能很少出現且難以追蹤。

蟲

任何沒有可識別指標的記憶體都將被回收。 對清單中的前向和後向連結進行異或並不能解決問題。

由於巧妙的優化，一些 C 優化器可能會丟失最後一個未加掩飾的指向記憶體物件的指標。 這在實踐中幾乎從未被觀察到。

這不是即時收集器。 在標準配置中，收集所需的時間百分比在堆大小之間應保持不變。 但對於較大的堆，收集暫停將會增加。如果啟用並行標記，它們將隨著處理器數量的增加而減少。

（在2007 年老式機器上，GC 時間可能約為每MB 需要掃描和處理的可存取記憶體5 毫秒。您的情況可能會有所不同。）增量/分代收集設施在某些情況下可能會有所幫助。

回饋、貢獻、問題和通知

請將錯誤回報和新功能想法提交到 GitHub 問題。 提交前請檢查是否尚未被其他人完成。

如果您想做出貢獻，請向 GitHub 提交拉取請求。請在提交前以 clang-format 處理修改後的文件。

如果您需要協助，請使用 Stack Overflow。較舊的技術討論可在bdwgc郵件清單檔案中找到 - 它可以作為壓縮檔案下載或在 Narkive 上瀏覽。

若要取得新版本公告，請訂閱 RSS 來源。 （要透過電子郵件接收通知，可以設定第 3 方免費服務，例如 IFTTT RSS Feed。）要獲得所有問題的通知，請在 GitHub 上觀看該專案。

版權和保證、貢獻者

我們的目的是讓 bdwgc (libgc) 在免費和專有軟體中都能輕鬆使用。 因此，我們希望動態或靜態連結到客戶端應用程式的 Boehm-Demers-Weiser 保守垃圾收集器程式碼由自己的授權覆蓋，這在精神上類似於 MIT 風格的授權。

LICENSE 文件中提供了確切的許可資訊。

所有貢獻者都列在作者文件中。