Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 1565] ファイルの概要

このコミットは、Go言語のランタイムに初期のマーク＆スイープ型ガベージコレクタ（GC）を導入するものです。主にsrc/runtimeディレクトリ内のメモリ管理関連ファイルが変更されており、新しいGCの実装ファイルsrc/runtime/mgc0.cと、GCの動作を検証するためのテストファイルtest/gc.goおよびtest/gc1.goが追加されています。

変更された主なファイルとその役割は以下の通りです。

  • src/lib/malloc.go: Go言語側からメモリ割り当て統計やGCを操作するためのインターフェースが追加されています。
  • src/runtime/Makefile: 新しいGC関連のソースファイルmgc0.cがビルドプロセスに追加されています。
  • src/runtime/malloc.c: メモリ割り当て関数mallocと解放関数freeがGCと連携するように変更され、mallocgcというGCトリガーを含む新しい割り当て関数が追加されています。オブジェクトの参照状態を追跡するためのmlookup関数のシグネチャも変更されています。
  • src/runtime/malloc.h: メモリ統計構造体MStatsにGC関連のフィールド（inuse_pages, next_gc, enablegc）が追加され、MSpan構造体にはGC参照情報（gcref, gcref0）が追加されています。また、GC参照状態を表す列挙型（RefFree, RefManual, RefStack, RefNone, RefSome）が定義されています。
  • src/runtime/malloc_go.cgo: Go言語のmallocパッケージからC言語のランタイム関数を呼び出す部分が更新され、GC()関数が追加されています。
  • src/runtime/mcentral.c: メモリブロックの割り当て時にGC参照情報を考慮するように変更されています。
  • src/runtime/mgc0.c: 新規追加ファイル。マーク＆スイープGCの主要なロジックが実装されています。これには、ルートからのオブジェクトのスキャン（scanblock, scanstack）、マークフェーズ（mark）、スイープフェーズ（sweepspan, sweepspanlist, sweep）、およびGCのメインエントリポイントであるgc関数が含まれます。
  • src/runtime/mheap.c: ヒープ管理に関連する変更で、MHeap_AllocとMHeap_Freeがmstats.inuse_pagesを更新するように変更され、MHeap_LookupMaybeという新しいルックアップ関数が追加されています。
  • src/runtime/msize.c: メモリサイズクラスの計算にGCオーバーヘッドが考慮されるように変更されています。
  • src/runtime/proc.c: プロセス管理に関連する変更で、GCの有効化（mstats.enablegc = 1）や、mallocの代わりにmallocgcを使用する箇所が導入されています。
  • src/runtime/rt1_amd64_darwin.c, src/runtime/rt1_amd64_linux.c: ロック取得・解放時にm->locksカウンタを更新する変更が含まれています。これはGCがロック保持中に実行されないようにするためのものです。
  • src/runtime/runtime.c: コマンドライン引数と環境変数の処理方法が変更されています。
  • src/runtime/runtime.h: M構造体にlocksフィールドが追加され、GC関連の関数プロトタイプが宣言されています。
  • test/gc.go: 新規追加ファイル。GCの基本的な動作をテストするGoプログラムです。
  • test/gc1.go: 新規追加ファイル。大量のメモリ割り当てを行い、GCがトリガーされることを確認するためのテストプログラムです。

コミット

commit 1ce17918e32afe42824404a1419b54a465e8b155
Author: Russ Cox <rsc@golang.org>
Date:   Mon Jan 26 17:37:05 2009 -0800

    gc #0.  mark and sweep collector.
    
    R=r,gri
    DELTA=472  (423 added, 2 deleted, 47 changed)
    OCL=23522
    CL=23541

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/1ce17918e32afe42824404a1419b54a465e8b155

元コミット内容

gc #0.  mark and sweep collector.

R=r,gri
DELTA=472  (423 added, 2 deleted, 47 changed)
OCL=23522
CL=23541

変更の背景

このコミットは、Go言語の初期開発段階において、言語ランタイムに基本的なガベージコレクタ機能を導入するために行われました。Go言語はメモリ安全性を重視しており、手動でのメモリ管理に伴う複雑さやエラー（メモリリーク、ダングリングポインタなど）を避けるために、自動メモリ管理（ガベージコレクション）が不可欠です。

コミットメッセージにある「gc #0」という表記は、これがGo言語における最初のガベージコレクタの実装であることを示唆しています。初期のGoランタイムは、おそらく単純なアロケータのみで動作しており、メモリが枯渇するか、プログラムが終了するまで解放されない状態だったと考えられます。本格的なアプリケーション開発や長期稼働を考慮すると、不要になったメモリを自動的に回収する仕組みが早期に必要とされました。

このマーク＆スイープコレクタの導入は、Go言語のメモリ管理モデルの基礎を築くものであり、その後のより高度なGCアルゴリズム（例えば、並行GCや世代別GC）への進化の第一歩となりました。また、コミットメッセージに「NOT INTENDED FOR PRODUCTION USE.」と明記されているように、この初期実装はあくまでプロトタイプであり、その後の改善を前提としたものでした。これは、GCの基本的な機能検証と、メモリ割り当ておよびスタックウォーク機構のテストを目的としていたことを示しています。

前提知識の解説

ガベージコレクション (Garbage Collection, GC)

ガベージコレクションは、プログラムが動的に確保したメモリ領域のうち、もはやどの部分からも参照されなくなった（到達不可能になった）ものを自動的に解放する仕組みです。これにより、プログラマは手動でメモリを解放する手間から解放され、メモリリークやダングリングポインタといったメモリ関連のバグを減らすことができます。

マーク＆スイープ (Mark and Sweep)

マーク＆スイープは、最も基本的なGCアルゴリズムの一つです。その動作は大きく2つのフェーズに分かれます。

  1. マークフェーズ (Mark Phase):

    • GCの実行が開始されると、まずプログラムの実行が一時停止されます（"Stop the World"）。
    • GCは、プログラムが直接アクセスできる「ルートセット」と呼ばれるオブジェクト群（例: グローバル変数、実行中の関数のスタック上のローカル変数）から開始します。
    • ルートセットから到達可能なすべてのオブジェクトをたどり、それらを「使用中（ライブ）」としてマークします。これは、グラフ探索アルゴリズム（深さ優先探索や幅優先探索）に似ています。
    • マークされていないオブジェクトは、プログラムから到達不可能であり、不要な「ガベージ」とみなされます。

  2. スイープフェーズ (Sweep Phase):

    • マークフェーズが完了すると、GCはヒープ全体を走査します。
    • マークされていないオブジェクトが見つかった場合、そのメモリ領域を解放し、再利用可能なフリーリストに追加します。
    • マークされたオブジェクトはそのまま保持され、次のGCサイクルで再度マークされる可能性があります。
    • このフェーズが完了すると、プログラムの実行が再開されます。

Stop the World (STW)

マーク＆スイープGCの初期実装では、マークフェーズとスイープフェーズの実行中、アプリケーションの実行を完全に停止させる必要があります。これを「Stop the World (STW)」と呼びます。STW中はアプリケーションが応答しなくなるため、その時間が長くなるとユーザー体験に悪影響を与えます。Go言語のGCは、このSTW時間を最小限に抑える方向に進化してきました。

Go言語のメモリ管理の基本概念（初期段階）

Go言語のランタイムは、独自のメモリ管理システムを持っています。

  • ヒープ (Heap): プログラムが動的に確保するメモリ領域。Goのオブジェクト（構造体、スライス、マップなど）は通常ヒープに割り当てられます。
  • スタック (Stack): 関数の呼び出しやローカル変数が格納されるメモリ領域。Goのスタックは動的に伸縮します。
  • MSpan: Goのメモリ管理における基本的な単位の一つで、連続したページ（OSから割り当てられるメモリの最小単位）の集合を表します。MSpanは、特定のサイズのオブジェクトを格納するために使用されるか、大きな単一のオブジェクトを格納するために使用されます。
  • MCentral: 特定のサイズクラス（オブジェクトのサイズに応じた分類）のMSpanを管理する構造体。
  • MHeap: ヒープ全体を管理する構造体で、MSpanの割り当てや解放、MCentralへの分配などを行います。
  • サイズクラス (Size Class): Goのメモリ管理では、異なるサイズのオブジェクトを効率的に管理するために、あらかじめ定義されたいくつかのサイズカテゴリ（サイズクラス）にメモリブロックを分類します。これにより、メモリの断片化を減らし、割り当ての効率を高めます。

技術的詳細

このコミットで導入されたGCは、Go言語のランタイムに組み込まれた最初のマーク＆スイープコレクタです。その実装はsrc/runtime/mgc0.cに集約されており、以下の主要なコンポーネントとメカニズムを含んでいます。

1. オブジェクトの参照状態追跡

GCは、各メモリブロック（オブジェクト）の参照状態を追跡するために、uint32型の参照カウンタのようなフィールドを使用します。これはMSpan構造体に追加されたgcrefまたはgcref0フィールドによって管理されます。

  • MSpan構造体:

    struct MSpan
{
    // ...
    uint32	ref;		// number of allocated objects in this span
    uint32	sizeclass;	// size class
    uint32	state;		// MSpanInUse or MSpanFree
    union {
        uint32	*gcref;	// sizeclass > 0 (small objects)
        uint32	gcref0;	// sizeclass == 0 (large objects)
    };
};

    gcrefは、sizeclass > 0（小さなオブジェクトが複数含まれるスパン）の場合に、スパン内の各オブジェクトの参照状態を指すポインタとして機能します。gcref0は、sizeclass == 0（大きな単一オブジェクトのスパン）の場合に、そのオブジェクト自身の参照状態を直接格納します。

  • 参照状態の列挙型: src/runtime/malloc.hで定義されています。

    enum
{
    RefcountOverhead = 4,	// one uint32 per object
    RefFree = 0,	// must be zero
    RefManual,	// manual allocation - don't free
    RefStack,		// stack segment - don't free and don't scan for pointers
    RefNone,		// no references (initially, or after sweep if not marked)
    RefSome,		// some references (marked during scan)
};
    • RefFree: オブジェクトが解放済みであることを示す。
    • RefManual: 手動で割り当てられたオブジェクトで、GCの対象外。
    • RefStack: スタックセグメントの一部で、GCの対象外かつポインタスキャンも行わない。
    • RefNone: 参照されていない、またはマークフェーズでまだマークされていない状態。
    • RefSome: マークフェーズで到達可能とマークされた状態。

2. メモリ割り当てとGCトリガー

  • mallocgc関数 (src/runtime/malloc.c): 新しいメモリ割り当て関数mallocgcが導入されました。これはmallocを呼び出してメモリを確保した後、現在の使用メモリ量（mstats.inuse_pages）が次のGCトリガー閾値（mstats.next_gc）を超えている場合に、gc(0)を呼び出してGCをトリガーします。

    void*
mallocgc(uintptr size)
{
    void *v;
    v = malloc(size);
    if(mstats.inuse_pages > mstats.next_gc)
        gc(0); // Trigger GC if threshold exceeded
    return v;
}

    これにより、メモリ割り当てのたびにGCの必要性がチェックされ、自動的にGCが実行されるようになります。

  • mstats構造体 (src/runtime/malloc.h): ランタイムのメモリ統計を保持するMStats構造体に、GC関連のフィールドが追加されました。

    struct MStats
{
    // ...
    uint64	inuse_pages;	// protected by mheap.Lock
    uint64	next_gc;	// protected by mheap.Lock
    bool	enablegc;
};
    • inuse_pages: 現在使用中のメモリページ数。
    • next_gc: 次のGCがトリガーされるべき使用メモリ量の閾値。
    • enablegc: GCが有効かどうかを示すフラグ。ブートストラップ完了後に有効化されます。

3. GCのメインロジック (src/runtime/mgc0.c)

mgc0.cは、マーク＆スイープGCの核心部分を実装しています。

  • gc(int32 force)関数: GCのメインエントリポイントです。

    • mstats.enablegcが有効で、かつロックが保持されていない（m->locks == 0）場合にのみ実行されます。これは、GCがランタイムの重要なセクションでデッドロックを引き起こさないようにするための初期の安全策です。
    • GOGC環境変数からGCの閾値（gcpercent）を読み込みます。GOGC=offの場合はGCを無効にします。
    • semacquire(&gcsema)でGCセマフォを取得し、GCの並行実行を防ぎます。
    • stoptheworld()を呼び出して、すべてのGoルーチンを一時停止させます。
    • mark()関数を呼び出してマークフェーズを実行します。
    • sweep()関数を呼び出してスイープフェーズを実行します。
    • mstats.next_gcを更新し、次のGCトリガー閾値を設定します。これは、現在の使用メモリ量にgcpercentを掛けた値に基づいて計算されます（例: gcpercent=100なら使用メモリが2倍になったらGC）。
    • starttheworld()を呼び出して、Goルーチンの実行を再開します。
    • semrelease(&gcsema)でGCセマフォを解放します。

  • mark()関数:

    • データセグメントとBSSセグメント（グローバル変数など）をルートとしてスキャンします（scanblock(0, etext, end - etext)）。
    • すべてのGoルーチン（allgリスト）のスタックをスキャンします（scanstack(gp)）。これにより、スタック上のポインタから到達可能なオブジェクトがマークされます。
    • scanblock関数は、メモリブロック内のポインタを再帰的にたどり、到達可能なオブジェクトのgcrefをRefSomeに設定します。

  • sweep()関数:

    • mheap.centralにあるすべてのMSpanリスト（nonemptyとempty）を走査します。
    • sweepspan(MSpan *s)関数を呼び出して、個々のスパンをスイープします。
    • sweepspanは、スパン内の各オブジェクトのgcrefの状態を確認します。
      • RefNoneのオブジェクトはガベージと判断され、free()を呼び出して解放されます。
      • RefSomeのオブジェクトはライブと判断され、次のGCサイクルのためにgcrefをRefNoneにリセットします。
      • RefFree, RefManual, RefStackのオブジェクトは無視されます。

4. その他の変更点

  • mlookup関数の拡張: src/runtime/malloc.cのmlookup関数は、与えられたアドレスがどのオブジェクトに属するかを調べ、そのオブジェクトのベースアドレス、サイズ、そしてGC参照ポインタを返すように拡張されました。これにより、GCがオブジェクトの参照状態を直接操作できるようになります。
  • NumSizeClassesの増加: src/runtime/malloc.hで定義されているNumSizeClasses（メモリサイズクラスの数）が133から150に増加しています。これは、より多くの異なるサイズのオブジェクトを効率的に管理するための調整と考えられます。
  • ロックとGCの連携: src/runtime/rt1_amd64_darwin.cとsrc/runtime/rt1_amd64_linux.cで、ロックの取得・解放時にm->locksカウンタをインクリメント/デクリメントするようになりました。gc関数はこのカウンタをチェックし、ロックが保持されている間はGCを実行しないようにします。これは、GCがロックを必要とする操作と競合するのを防ぐための重要な同期メカニズムです。

この初期GC実装は、シンプルながらもGo言語の自動メモリ管理の基盤を築き、その後の高性能なGCアルゴリズム開発への道を開きました。特に、"Stop the World"方式であること、そしてgcrefというシンプルな参照状態追跡メカニズムが特徴です。

コアとなるコードの変更箇所

1. src/runtime/mgc0.c (新規追加ファイル)

このファイル全体がGCのコアロジックです。特に以下の関数が重要です。

  • gc(int32 force): GCのトリガーと全体の流れを制御します。

    void
gc(int32 force)
{
    // ... (省略: 初期化、GOGC環境変数処理、ロックチェック)

    semacquire(&gcsema); // GCセマフォ取得
    gosave(&g->sched);	// gのスタックポインタを更新
    stoptheworld();     // 全てのGoルーチンを停止

    if(mheap.Lock.key != 0)
        throw("mheap locked during gc");

    if(force || mstats.inuse_pages >= mstats.next_gc) {
        mark();         // マークフェーズ実行
        sweep();        // スイープフェーズ実行
        mstats.next_gc = mstats.inuse_pages+mstats.inuse_pages*gcpercent/100; // 次のGC閾値設定
    }
    starttheworld();    // Goルーチン再開
    gosave(&g->sched);	// gのスタックポインタを更新 (デバッグ用)
    semrelease(&gcsema); // GCセマフォ解放
}

  • mark(): ルートから到達可能なオブジェクトをマークします。

    static void
mark(void)
{
    G *gp;

    // mark data+bss (グローバル変数など)
    scanblock(0, etext, end - etext);

    // mark stacks (Goルーチンのスタック)
    for(gp=allg; gp!=nil; gp=gp->alllink) {
        switch(gp->status){
        // ... (省略: Gの状態に応じた処理)
        case Grunning:
        case Grunnable:
        case Gsyscall:
        case Gwaiting:
            scanstack(gp); // スタックをスキャン
            break;
        }
    }
}

  • sweepspan(MSpan *s): 個々のスパン内のオブジェクトをスイープします。

    static void
sweepspan(MSpan *s)
{
    // ... (省略: 初期チェック)

    if(s->sizeclass == 0) {
        // Large block.
        switch(s->gcref0) {
        // ... (省略: RefFree, RefManual, RefStack は無視)
        case RefNone:
            // ガベージなので解放
            if(Debug)
                printf("free %D at %p\\n", s->npages<<PageShift, p);
            free(p);
            break;
        case RefSome:
            // ライブなので次のGCのためにリセット
            s->gcref0 = RefNone;
            break;
        }
        return;
    }

    // Chunk full of small blocks.
    // ... (省略: small blockの処理、RefcountOverheadを考慮)
    for(i=0; i<n; i++) {
        switch(s->gcref[i]) {
        // ... (省略: RefFree, RefManual, RefStack は無視)
        case RefNone:
            // ガベージなので解放
            if(Debug)
                printf("free %d at %p\\n", size, p+i*size);
            free(p + i*size);
            break;
        case RefSome:
            // ライブなので次のGCのためにリセット
            s->gcref[i] = RefNone;
            break;
        }
    }
}

2. src/runtime/malloc.c

  • mallocgc(uintptr size): GCトリガーを含むメモリ割り当て関数。

    void*
mallocgc(uintptr size)
{
    void *v;
    v = malloc(size); // 通常のメモリ割り当て
    if(mstats.inuse_pages > mstats.next_gc) // GC閾値を超えたら
        gc(0); // GCをトリガー
    return v;
}

  • mlookup関数のシグネチャ変更とGC参照ポインタの追加:

    // 変更前:
// void mlookup(void *v, byte **base, uintptr *size)
// 変更後:
int32
mlookup(void *v, byte **base, uintptr *size, uint32 **ref) // ref引数が追加
{
    // ... (省略: オブジェクトの検索ロジック)
    if(s->sizeclass == 0) {
        // Large object.
        // ...
        if(ref)
            *ref = &s->gcref0; // large objectのgcref0を返す
        return 1;
    }

    // Small objects.
    // ...
    if(ref)
        *ref = &s->gcref[i]; // small objectのgcref[i]を返す
    return 1;
}

3. src/runtime/malloc.h

  • MStats構造体へのGC関連フィールドの追加:

    struct MStats
{
    // ...
    uint64	inuse_pages;	// protected by mheap.Lock
    uint64	next_gc;	// protected by mheap.Lock
    bool	enablegc;
};

  • MSpan構造体へのGC参照フィールドの追加:

    struct MSpan
{
    // ...
    uint32	ref;
    uint32	sizeclass;
    uint32	state;
    union {
        uint32	*gcref;	// sizeclass > 0
        uint32	gcref0;	// sizeclass == 0
    };
};

  • GC参照状態の列挙型定義:

    enum
{
    RefcountOverhead = 4,
    RefFree = 0,
    RefManual,
    RefStack,
    RefNone,
    RefSome,
};

コアとなるコードの解説

このコミットの核心は、Goランタイムに基本的なマーク＆スイープガベージコレクタを統合することです。

  1. GCのトリガーと制御 (gc関数): gc関数は、GCサイクルのオーケストレーターです。

    • mstats.enablegcフラグとm->locksカウンタによって、GCが実行可能かどうかを判断します。enablegcはランタイムの初期化が完了した後にsrc/runtime/proc.cで1に設定され、m->locksはロックが保持されている間はGCを抑制します。これは、GCがメモリ管理の内部ロックと競合してデッドロックを引き起こすのを防ぐための重要な安全機構です。
    • semacquireとsemreleaseは、GCが一度に一つだけ実行されることを保証するためのセマフォです。
    • stoptheworld()とstarttheworld()は、GC実行中にGoルーチンがメモリ状態を変更するのを防ぐために、すべてのGoルーチンの実行を一時停止・再開します。これは、このGCが「Stop the World」型であることを明確に示しています。
    • GCの実行は、force引数が1の場合（手動GC）か、mstats.inuse_pagesがmstats.next_gcを超えた場合（自動GC）にトリガーされます。next_gcは、gcpercentに基づいて動的に調整され、使用メモリ量に比例してGCが実行されるように設計されています。

  2. マークフェーズ (mark関数): mark関数は、ライブオブジェクトを識別する役割を担います。

    • まず、プログラムの静的データ領域（etextからendまで）をスキャンします。これにはグローバル変数などが含まれ、GCルートの一部となります。
    • 次に、現在存在するすべてのGoルーチン（allgリスト）のスタックをスキャンします。スタック上にはローカル変数や関数引数があり、これらがヒープ上のオブジェクトへのポインタを含んでいる可能性があります。
    • scanblock関数は、与えられたメモリブロック内の各ワードを調べ、それが有効なオブジェクトへのポインタであるかどうかをmlookupを使って判断します。もしポインタであれば、そのオブジェクトのgcrefをRefSomeに設定し、そのオブジェクト自体を再帰的にスキャンします。これにより、ルートから到達可能なすべてのオブジェクトがマークされます。

  3. スイープフェーズ (sweepspan関数): sweepspan関数は、マークフェーズでマークされなかったオブジェクトを解放します。

    • ヒープ内の各MSpanを走査します。
    • スパンが大きな単一オブジェクト（s->sizeclass == 0）を保持している場合、そのオブジェクトのgcref0をチェックします。RefNoneであればガベージと判断し、free()で解放します。RefSomeであればライブなので、次のGCサイクルのためにgcref0をRefNoneにリセットします。
    • スパンが複数の小さなオブジェクト（s->sizeclass > 0）を保持している場合、スパン内の各オブジェクトのs->gcref[i]をチェックし、同様にRefNoneなら解放、RefSomeならリセットします。
    • RefFree, RefManual, RefStackのオブジェクトは、GCの対象外としてスキップされます。

  4. メモリ割り当てとGCの連携 (mallocgcとmlookup):

    • mallocgcは、Goプログラムがメモリを要求するたびに呼び出され、割り当て後にGCのトリガー条件をチェックします。これにより、メモリ使用量が増加するにつれて自動的にGCが実行される「適応型」のGCスケジュールが実現されています。
    • mlookup関数の拡張は、GCがオブジェクトの内部構造にアクセスし、その参照状態を直接操作するために不可欠です。これにより、GCはヒープ上の任意のポインタが指すオブジェクトのメタデータ（特にgcref）を取得できるようになります。

この初期実装は、Go言語のメモリ管理の基礎を築きましたが、その後のGoのGCは、並行性、低レイテンシ、スループットの向上を目指して大きく進化していくことになります。このコミットは、その進化の出発点となる重要なマイルストーンです。

関連リンク

参考にした情報源リンク