.NET ガベージ コレクタを C# で書く – パート 6: マーク＆スイープ

この記事がお役に立ったら、Pro .NET Memory Managementの第2版もぜひご覧ください。 .NET ガベージコレクタ内部についてさらに深く知ることができます！

長い（むしろ極端に長い）休止期間を経て、C# で .NET ガベージコレクタを構築する旅を再開します。前回のパートでは、単純なアプリケーションが動くように最小限の GC API を実装し、ヒープを走査できるようにオブジェクトをメモリ上に配置する方法を学びました。その後、管理対象オブジェクトの参照を取得する手段も習得しました。復習が必要な場合は、以下の記事へ戻ってください。

• パート 1 – はじめにとプロジェクト設定
• パート 2 – 最小 GC の実装
• パート 3 – DAC を使った管理オブジェクトの検査
• パート 4 – 管理ヒープの走査
• パート 5 – GCDesc をデコードしてオブジェクト参照を取得

すべて読む時間がない場合は、ヒープレイアウトを説明したパート 4 に注目することをおすすめします。

---

マークフェーズ

マークフェーズでは、ユーザーコードから現在到達可能な全オブジェクトを見つけ出し、もう到達不可能になったものが解放できるかどうかを判断します。

ルートの決定

GC はコレクション開始時に「必ず生存」とみなす参照（ルート）から探索を始めます。ルートは次の3種類に分類されます。

1. ローカル変数とスレッド固有ストレージ
2. GC ハンドル
3. ファイナライザキュー

実際には、静的フィールドは GC ハンドルによって生存が保証されています。

GC は後2つのバケットを管理しますが、最初のバケット（ローカル変数など）はランタイム自身が処理します。

IGCToCLR

では

GcScanRoots

メソッドを公開しており、このメソッドはコールバックを受け取り、すべてのローカル変数に対して呼び出されます。さらに、

GcScanRoots

は3つの引数（

condemned

、

max_gen

（サーバGC の特殊ケースでほぼ無視可）と

ScanContext

）を取ります。

[StructLayout(LayoutKind.Sequential)]
public struct ScanContext
{
    public IntPtr thread_under_crawl;
    public int thread_number;
    public int thread_count;
    public IntPtr stack_limit;          // スキャンロジックが読み取り許可されるスレッドスタックの最下点
    public bool promotion;              // TRUE: Promotion, FALSE: Relocation.
    public bool concurrent;             // TRUE: concurrent scanning
    public IntPtr _unused1;
    public IntPtr pMD;
    public int _unused3;
}

本実装では、

promotion

と

_unused1

の2つだけを使用します。

• promotion

  は実行エンジンに「プロモーション（上位世代へ移動）用のマークか、再配置用のマークか」を知らせます。ここでは true を設定しています。

• _unused1

  は GC が自由に使えるポインタサイズフィールドです。ここには

  GCHeap

  のインスタンスへのポインタを格納します。

  GcScanRoots

  に渡すコールバックは

  [UnmanagedCallersOnly]

  でなければならないため、静的メソッドになります。

private void MarkPhase()
{
    ScanContext scanContext = new();
    scanContext.promotion   = true;
    scanContext._unused1     = GCHandle.ToIntPtr(_handle);

    var scanRootsCallback =
        (delegate* unmanaged<GCObject**, ScanContext*, uint, void>)&ScanRootsCallback;

    _gcToClr.GcScanRoots((IntPtr)scanRootsCallback, 2, 2, &scanContext);
}

[UnmanagedCallersOnly]
private static void ScanRootsCallback(GCObject** obj,
                                      ScanContext* context,
                                      uint flags)
{
    var handle   = GCHandle.FromIntPtr(context->_unused1);
    var gcHeap   = (GCHeap)handle.Target!;
    gcHeap.ScanRoots(*obj, context, (GcCallFlags)flags);
}

private void ScanRoots(GCObject* obj,
                       ScanContext* context,
                       GcCallFlags flags)
{
    // TODO: 実際のコールバック実装
}

---

コンザーバティブモード

「コンザーバティブモード」という用語を使う前に、まずは説明しておきます。

DOTNET_gcConservative=1

を設定すると、実行エンジンは 正確 ルート追跡（どこがルートか明確に分かる）から 保守的 ルート追跡へ切り替わります。保守的モードでは、スタック全体をスキャンし、GC が管理するメモリ領域にポインタを指す値をすべて報告します。その結果、誤検出（false positive）が増え、GC の負荷が大きくなります。主に CLR が完全に実装されていない環境や、新機能のテスト時に使われます。現在のカスタム GC ではコンザーバティブモードへの対応は予定していません。

---

ScanRoots コールバック

ScanRoots

のコールバック内で、与えられたオブジェクトから出てくるすべての参照を検出し、その参照ツリーを走査して見つかったオブジェクトをマークします。パート 5 で「あるオブジェクトの参照を取得する」方法を学び、

EnumerateObjectReferences

メソッドに実装しました。ここでは、オブジェクトがマーク済みかどうかを記録する必要があります。

いくつかの手段があります。x64 ならオブジェクトヘッダーにパディングがあり、その領域を再利用できるかもしれません。しかし、後で他の最適化に使う予定なので、今回は実際の .NET GC が行っている方法を採用します。

オブジェクトレイアウト

メモリ上のオブジェクトは次のようになっています。

                      Object
                +-----------------+
                | Object header   |
                +-----------------+
Object ref ---> | MethodTable*    |
                +-----------------+
                |  Field1         |
                +-----------------+
                |  Field2         |
                +-----------------+
                |  Field3         |
                +-----------------|
                |  Field4         |
                +-----------------+

ポイントは、メソッドテーブルポインタがポインタ境界に揃えてあるため、32ビット環境では最下位2ビット（64ビットなら3ビット）が常に0であることです。GC はオブジェクトをマークする際に、その最低位ビットを 1 に設定します。コレクション終了時には元のポインタに戻す必要があります。

GCObject

構造体に

Mark

,

Unmark

,

IsMarked

、そして

MethodTable

プロパティ（マーク状態を無視してメソッドテーブルにアクセス）を追加します。

[StructLayout(LayoutKind.Sequential)]
public unsafe struct GCObject
{
    public MethodTable* RawMethodTable;
    public uint Length;

    public readonly MethodTable* MethodTable =>
        (MethodTable*)((nint)RawMethodTable & ~1);

    public bool IsMarked() => ((nint)RawMethodTable & 1) != 0;

    public void Mark()   => RawMethodTable = (MethodTable*)((nint)MethodTable | 1);
    public void Unmark() => RawMethodTable = (MethodTable*)((nint)MethodTable & ~1);

    // …
}

DFS による走査

実際の参照ツリーを探索するには、再帰を使わずにスタックで深さ優先探索（DFS）を行います。

GC_CALL_INTERIOR

フラグが付いたルートは現時点では無視します。

private Stack<IntPtr> _markStack = new();

private void ScanRoots(GCObject* obj,
                       ScanContext* context,
                       GcCallFlags flags)
{
    if ((IntPtr)obj == 0) return;

    if (flags.HasFlag(GcCallFlags.GC_CALL_INTERIOR))
    {
        // TODO: interior pointer を扱う
        return;
    }

    _markStack.Push((IntPtr)obj);

    while (_markStack.Count > 0)
    {
        var ptr = _markStack.Pop();
        var o   = (GCObject*)ptr;

        if (o->IsMarked()) continue;

        o->EnumerateObjectReferences(_markStack.Push);
        o->Mark();
    }
}

interior pointer の問題

例えば次のようなコードを考えてみてください。

private static ref int GetInteriorPointer()
{
    var array = new int[10];
    return ref array[5];
}

GetInteriorPointer

は配列内の要素への参照（interior pointer）を返します。GC がその配列を回収してしまうと、残っている

ref int

から不正アクセスが起きます。このような interior pointer を正しく扱うには、ポインタからオブジェクト開始位置を特定しマークする必要があります。現時点では、この問題は無視しています。

---

スイーピング

ルートにより到達可能なオブジェクトをすべてマークした後、ヒープ全体を走査して未マークのオブジェクトを解放します。現在の実装ではメモリ再利用は行わず、単純に領域をクリアしています。ただし、ヒープが「歩きやすい」状態を保つために、古いオブジェクトの代わりにフリーオブジェクト（パート 4 で説明）を配置します。マーク済みだった場合は必ず

Unmark

を呼び出して元のメソッドテーブルポインタに戻します。

private void Sweep()
{
    foreach (IntPtr ptr in WalkHeapObjects())
    {
        var obj   = (GCObject*)ptr;
        bool marked = obj->IsMarked();
        obj->Unmark();

        bool isFreeObject = obj->MethodTable == _freeObjectMethodTable;

        if (!marked && !isFreeObject)
        {
            var startPtr = ptr - IntPtr.Size; // ヘッダーを含む
            var endPtr   = Align(startPtr + (nint)obj->ComputeSize());

            // メモリをクリア
            new Span<byte>((void*)startPtr, (int)(endPtr - startPtr)).Clear();

            // フリーオブジェクトで置き換えてヒープを走査可能に保つ
            AllocateFreeObject(ptr,
                               (uint)(endPtr - startPtr - SizeOfObject));
        }
    }
}

private IEnumerable<IntPtr> WalkHeapObjects()
{
    foreach (var segment in _segments)
    {
        foreach (var obj in WalkHeapObjects(segment.Start, segment.Current))
        {
            yield return obj;
        }
    }
}

private IEnumerable<IntPtr> WalkHeapObjects(nint start, nint end)
{
    var ptr = start + IntPtr.Size;

    while (ptr < end)
    {
        yield return ptr;
        ptr = FindNextObject(ptr);
    }

    static unsafe nint FindNextObject(nint current)
    {
        var obj = (GCObject*)current;
        return Align(current + (nint)obj->ComputeSize());
    }
}

---

まとめ

これで基本的なマーク＆スイープサイクルは実装できました。実際にアプリケーションを走らせると、まだ interior pointer の処理や GC ハンドル・ファイナライザキューの対応が欠けているためクラッシュします。次回の記事ではそれらを追加し、完全なガベージコレクタへと仕上げていきます。

詳細コードは GitHub で公開していますので、ご興味のある方はぜひご確認ください。