CLR 深度探索系列：Card Table 與 Brick Table 詳解（垃圾回收專題二）

問題背景：GC 壓縮階段的指針更新挑戰

GC Heap 運行一段時間後，配置空間不斷增長。進行局部或完整 GC 時，會執行 壓縮：移動倖存物件消除碎片。問題來了——若某「小物件」被移動，且被其他物件引用，GC 必須找到所有指向該物件的引用並更新。遍歷整個 Heap、Root、Handle Table 極其昂貴。Card Table 與 Brick Table 正是為解決此問題而生的輔助索引結構。

Card Table：寫入屏障的索引地圖

結構定義

• 連續記憶體區域，作為位圖索引。
• 每個 bit 對應 GC Heap 中 128 bytes 區域（一張「卡」）。
• 更新粒度為 byte（8 bits = 1 KB 區域）：一次更新會將整個 byte 置為 0xFF。

運作機制

1. 托管代碼修改物件引用（如 obj.Field = otherObj）時，JIT 生成的代碼會自動插入寫入屏障，呼叫 GCHeap::ErectWriteBarrier 或 WriteBarrierHelper。
2. 寫入屏障計算目標位址對應的 Card 索引，將 Card Table 中對應 byte 置 0xFF（標記「髒」）。
3. GC 掃描階段，僅掃描標記為髒的 Card 所覆蓋區域，大幅縮小搜尋範圍。

核心代碼：ErectWriteBarrier

void GCHeap::ErectWriteBarrier(OBJECTREF *dst, OBJECTREF ref)
{
    // 1. 檢查 dst 是否在 GC Heap 範圍內
    if (((BYTE**)&dst) < g_lowest_address || ((BYTE**)&dst) >= g_highest_address)
        return;

    // 2. 檢查引用目標 ref 是否在 Ephemeral 範圍內（Gen 0/1）
    if ((BYTE*)OBJECTREFToObject(ref) >= g_ephemeral_low 
        && (BYTE*)OBJECTREFToObject(ref) < g_ephemeral_high)
    {
        size_t card = gcard_of((BYTE*)dst);
        BYTE* pCardByte = (BYTE*)g_card_table + card / 8; // CARDS_PER_BYTE = 8
        BYTE bitMask = (BYTE)(1 << (card % 8));
        
        // 3. 若該 bit 未置位，整個 byte 置 0xFF（標記 1KB 區域為髒）
        if (!(*pCardByte & bitMask))
            *pCardByte = 0xFF;
    }
}

關鍵設計細節

• 只追蹤 Ephemeral 範圍內的引用目標：Gen 2 物件不移動，無需追蹤指向它們的引用更新。
• Byte 級更新而非 Bit 級：以空間換時間，避免原子性位操作開銷。
• Write Barrier 技術：JIT 在特定 CIL 指令（stfld, stobj, stelem.ref 等）後插入屏障代碼，x86 下通常為幾條組合語言指令。

Brick Table：物件定位的導航儀

結構定義

• 16 位元有號整數陣列（short[]）。
• 每個 Brick Slot 覆蓋 2048 bytes (2 KB) Heap 區域。
• 三種取值語意：
  1. 正數：從 Brick 起始位址到最近物件的位移量。
  2. 負數：相對於 Brick Table 自身的唯一標識（用於特殊物件）。
  3. 保留值：作為標記位使用。

核心用途

GC 壓縮/掃描階段，快速定位 Heap 中某位址對應的物件起始位置。配合 Card Table 使用：Card Table 粗略定位「髒區域」，Brick Table 精確定位區域內的物件邊界。

兩表協同：GC 掃描流程簡述

1. GC 開始，遍歷 Card Table 找出所有「髒」Card（byte == 0xFF）。
2. 對每個髒 Card，計算其覆蓋的 1 KB 區域範圍。
3. 利用 Brick Table 在該區域內快速枚舉物件（透過位移跳躍）。
4. 檢查物件引用欄位，更新指向已移動物件的引用。
5. 清理 Card Table 對應 byte（重置為 0），準備下一輪。

局限性提醒

Card Table 與 Brick Table 均為近似結構：

• Card Table 以 1 KB 粒度標記，可能誤報（False Positive）——實際未修改引用的區域也被掃描。
• Brick Table 位移機制在物件極大或極小時精度受限。
• 兩者無法 100% 精確反映 Heap 狀態，但以極小空間/時間開銷換取 GC 效能飛躍，是經典工程權衡典範。