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

このコミットは、Go言語のランタイムにおけるメモリ管理、特にガベージコレクション（GC）の初期段階における参照カウントのサポート追加と、マーク＆スイープ方式の「Stop-the-World」型GCの導入に関するものです。これは、Go言語のメモリ管理戦略が進化する過程における中間的なステップとして位置づけられます。

コミット

• コミットハッシュ: 3f8aa662e9710f821411dc9c6f0f0be8c756e40d
• Author: Russ Cox rsc@golang.org
• Date: Fri Dec 5 15:24:18 2008 -0800

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

https://github.com/golang/go/commit/3f8aa662e9710f821411dc9c6f0f0be8c756e40d

元コミット内容

add support for ref counts to memory allocator.

mark and sweep, stop the world garbage collector
(intermediate step in the way to ref counting).
can run pretty with an explicit gc after each file.

R=r
DELTA=502  (346 added, 143 deleted, 13 changed)
OCL=20630
CL=20635
---
 src/runtime/Makefile           |   2 +-\
 src/runtime/mem.c              |  96 +++++++++++++++++++++++++
 src/runtime/proc.c             |  43 ++++++++++-\
 src/runtime/runtime.c          |  77 --------------------\
 src/runtime/runtime.h          |   8 +++
 src/runtime/stack.c            |  19 -----\
 usr/rsc/mem/Makefile           |   5 +-\
 usr/rsc/mem/allocator.go       |   2 +\
 usr/rsc/mem/malloc.c           | 159 +++++++++++++++++++++++++++++++----------
 usr/rsc/mem/malloc.h           |  44 ++++++++++++\
 usr/rsc/mem/{stack.c => mem.c} |  17 +++++
 usr/rsc/mem/testrandom.go      |   8 ++-\
 12 files changed, 341 insertions(+), 139 deletions(-)

変更の背景

このコミットは、Go言語がまだ初期開発段階にあった2008年に行われたものです。Go言語は、その設計目標の一つとして効率的なメモリ管理と並行処理を掲げていました。ガベージコレクション（GC）は、メモリ管理の自動化において中心的な役割を果たします。

コミットメッセージによると、この変更の主な目的は「メモリ割り当て器への参照カウントのサポート追加」と「マーク＆スイープ、Stop-the-Worldガベージコレクタ」の導入です。これは、GoのGC戦略が参照カウント方式から、より堅牢で並行処理に適したマーク＆スイープ方式へと移行する過渡期を示唆しています。

初期のGoランタイムでは、メモリ管理の基本的なメカニズムが構築されており、このコミットはその上にGC機能を追加しようとする試みです。特に、「参照カウントへの道の中間ステップ」という記述は、開発チームが様々なGCアプローチを検討し、最終的にマーク＆スイープ方式に落ち着くまでの試行錯誤の一端を垣間見せます。

また、「各ファイルの後に明示的なGCでかなりうまく実行できる」という記述は、この時点でのGCがまだ最適化されておらず、手動でのGCトリガーが必要なほど初期的な実装であったことを示しています。

前提知識の解説

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

ガベージコレクションは、プログラムが動的に確保したメモリ領域のうち、もはや使用されなくなった（参照されなくなった）ものを自動的に解放する仕組みです。これにより、プログラマは手動でのメモリ解放の煩雑さから解放され、メモリリークなどのバグを減らすことができます。

GCにはいくつかの主要なアルゴリズムがあります。

1. 参照カウント (Reference Counting): 各オブジェクトがどれだけの参照を持っているかをカウントし、参照カウントが0になったオブジェクトをガベージとして回収します。実装が比較的単純で、メモリ解放が即座に行われるため、レイテンシが低いという利点があります。しかし、循環参照（AがBを参照し、BがAを参照するような場合）を検出できない、参照カウントの更新にオーバーヘッドがある、といった欠点があります。

2. マーク＆スイープ (Mark and Sweep): GCが実行される際に、まず「マーク」フェーズで、ルート（グローバル変数、スタック上の変数など）から到達可能なすべてのオブジェクトをマークします。次に「スイープ」フェーズで、マークされなかった（到達不可能な）オブジェクトをガベージとして回収し、メモリを解放します。循環参照を検出できる、参照カウントのような頻繁な更新オーバーヘッドがない、といった利点があります。欠点としては、GC実行中にプログラムの実行が一時停止する「Stop-the-World (STW)」時間が発生する可能性があることや、メモリの断片化が発生しやすいことが挙げられます。

Stop-the-World (STW)

「Stop-the-World」とは、ガベージコレクタが動作している間、アプリケーションの実行が完全に停止する状態を指します。STWが発生すると、ユーザーはアプリケーションの一時的なフリーズを経験する可能性があり、特にリアルタイム性が求められるシステムでは問題となります。Go言語のGCは、初期のSTW型から、後に並行GCへと進化し、STW時間を大幅に短縮する努力がなされてきました。

Goランタイム

Goランタイムは、Goプログラムの実行を管理する低レベルのシステムです。これには、スケジューラ（ゴルーチンの管理）、メモリ割り当て器、ガベージコレクタ、システムコールインターフェースなどが含まれます。Goプログラムは、Goランタイムと密接に連携して動作します。

mmap システムコール

mmap (memory map) は、Unix系OSで利用されるシステムコールで、ファイルやデバイスをプロセスのアドレス空間にマッピングするために使用されます。メモリ割り当て器がOSから直接メモリを要求する際にも利用されます。このコミットでは、sys·mmapとしてGoランタイムから呼び出されています。

技術的詳細

このコミットは、Goランタイムのメモリ管理サブシステムに大きな変更を加えています。

1. src/runtime/mem.c の新規追加: このファイルは、Goランタイムのメモリ管理のスタブ（仮実装）を提供するために新しく追加されました。stackalloc や mal といった基本的なメモリ割り当て関数が含まれています。特に mal 関数は、スタックセグメントの割り当てにも使用されるため、再帰的な呼び出しの可能性を考慮した実装になっています。sys·mmap を直接呼び出すことで、スタックの成長による再帰的な mal 呼び出しを避ける工夫が見られます。

2. src/runtime/proc.c の変更:

   • sched 構造体に gomaxprocs と stopped (Note型) が追加されました。gomaxprocs は、Goプログラムが利用できるCPUコアの最大数を設定する GOMAXPROCS 環境変数を反映します。
   • stoptheworld と starttheworld 関数が一時的なものとして追加されました。これらは、マーク＆スイープGCのために、すべてのゴルーチン（M: マシン）の実行を一時停止・再開するメカニズムを提供します。stoptheworld は sched.mcpumax を1に設定し、実行中のMが1つになるまで待機します。
   • malg 関数（ゴルーチン割り当て）で、スタックの割り当てに mal ではなく stackalloc を使用するように変更されました。
   • sys·entersyscall および sys·exitsyscall で、ゴルーチンのステータス (g->status) が Gsyscall および Grunning に適切に設定されるようになりました。これはGCがゴルーチンの状態を正確に把握するために重要です。

3. src/runtime/runtime.c からメモリ割り当てロジックの移動: 以前 runtime.c にあった NHUNK, PROT_*, MAP_* などの定数定義や、brk, mal, sys·mal といったメモリ割り当て関数が mem.c へと移動されました。これにより、メモリ管理関連のコードがよりモジュール化され、GCのテストが容易になるように設計されています。

4. src/runtime/stack.c の削除と usr/rsc/mem/stack.c の usr/rsc/mem/mem.c へのリネーム: ランタイムのスタック管理に関するスタブが src/runtime/stack.c から削除され、usr/rsc/mem/stack.c が usr/rsc/mem/mem.c にリネームされました。これは、Goランタイムのメモリ管理の実験的な部分が usr/rsc/mem ディレクトリに集約されつつあることを示唆しています。

5. usr/rsc/mem/malloc.c および usr/rsc/mem/malloc.h の大幅な変更: このファイル群は、Goのメモリ割り当て器の核心部分であり、GCの導入に伴い大きく変更されました。

   • Span 構造体と Central 構造体の定義が malloc.h に移動され、より明確になりました。
   • Span 構造体に aprev, anext (全スパンのリスト用)、ref (参照カウント用) または refbase (パックされた参照カウントへのポインタ) が追加されました。これは、参照カウントGCの実験的なサポートを示しています。
   • RefFree, RefManual, RefStack といった参照カウントの状態を示す定数が定義されました。
   • findobj 関数が追加されました。これは、与えられたポインタが既知のメモリブロックを指しているかどうかをチェックし、そのオブジェクトのベースポインタ、サイズ、および参照カウントへのポインタを返します。これはGCがオブジェクトの参照状態を追跡するために不可欠な機能です。
   • allocsmall および free 関数内で、参照カウントの初期化やチェックが行われるようになりました。特に free 関数では、解放時に参照カウントが 0, RefManual, RefStack 以外であればエラーをスローするチェックが追加されています。
   • spanfirst, spanlast といったグローバル変数が追加され、すべての Span を連結リストで管理するようになりました。これは、マーク＆スイープGCがヒープ全体を走査する際に利用される可能性があります。

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

このコミットでは、主に以下のファイルが変更されています。

• src/runtime/Makefile: mem.c の追加と stack.c の削除に伴う変更。
• src/runtime/mem.c: 新規追加。メモリ管理のスタブ関数 (mal, stackalloc など) を定義。
• src/runtime/proc.c: ゴルーチンとスケジューラの管理、stoptheworld/starttheworld 関数の追加。
• src/runtime/runtime.c: 以前のメモリ割り当て関連コードの削除。
• src/runtime/runtime.h: 新しいゴルーチンステータス Gsyscall の追加、stoptheworld/starttheworld のプロトタイプ宣言。
• src/runtime/stack.c: 削除。
• usr/rsc/mem/Makefile: mem.c と ms.c の追加に伴う変更。
• usr/rsc/mem/allocator.go: find 関数と gc 関数のエクスポート宣言を追加。
• usr/rsc/mem/malloc.c: メモリ割り当て器の主要なロジック、Span と Central の管理、findobj 関数の実装、参照カウント関連のロジック。
• usr/rsc/mem/malloc.h: Span と Central 構造体の定義、参照カウント関連の定数、findobj のプロトタイプ宣言。
• usr/rsc/mem/{stack.c => mem.c}: ファイル名変更と、stackalloc で参照カウントを設定するロジックの追加。
• usr/rsc/mem/testrandom.go: allocator.find のテストコードを追加。

コアとなるコードの解説

src/runtime/mem.c

このファイルは、Goランタイムのメモリ割り当ての基本的なビルディングブロックを提供します。

// Stubs for memory management.
// In a separate file so they can be overridden during testing of gc.
...
void*
mal(uint32 n)
{
    byte* v;
    // round to keep everything 64-bit aligned
    n = rnd(n, 8);

    // be careful.  calling any function might invoke
    // mal to allocate more stack.
    if(n > NHUNK) {
        v = brk(n);
    } else {
        // allocate a new hunk if this one is too small
        if(n > m->mem.nhunk) {
            // ... (sys·mmap directly to avoid recursion issues)
            m->mem.hunk =
                sys·mmap(nil, NHUNK, PROT_READ|PROT_WRITE,
                    MAP_ANON|MAP_PRIVATE, 0, 0);
            m->mem.nhunk = NHUNK;
            m->mem.nmmap += NHUNK;
        }
        v = m->mem.hunk;
        m->mem.hunk += n;
        m->mem.nhunk -= n;
    }
    m->mem.nmal += n;
    return v;
}

mal 関数は、指定されたサイズのメモリを割り当てます。特に注目すべきは、スタックの割り当てにも使用されるため、再帰的な呼び出しを避けるための工夫が凝らされている点です。大きな割り当て (n > NHUNK) の場合は brk (内部で sys·mmap を呼び出すラッパー) を使用しますが、小さな割り当てで現在のメモリチャンク (m->mem.hunk) が不足する場合は、直接 sys·mmap を呼び出すことで、mal がスタックを成長させるために再帰的に呼び出されるのを防いでいます。

src/runtime/proc.c

このファイルは、Goのスケジューラとゴルーチン管理を担当します。

// TODO(rsc): Remove. This is only temporary,
// for the mark and sweep collector.
void
stoptheworld(void)
{
    lock(&sched);
    sched.mcpumax = 1;
    while(sched.mcpu > 1) {
        noteclear(&sched.stopped);
        unlock(&sched);
        notesleep(&sched.stopped);
        lock(&sched);
    }
    unlock(&sched);
}

// TODO(rsc): Remove. This is only temporary,
// for the mark and sweep collector.
void
starttheworld(void)
{
    lock(&sched);
    sched.mcpumax = sched.gomaxprocs;
    matchmg();
    unlock(&sched);
}

stoptheworld と starttheworld 関数は、マーク＆スイープGCの実行中にすべてのゴルーチンを一時停止・再開するために導入されました。stoptheworld は、実行中のM (マシン、OSスレッドに相当) の数を1に制限し、他のMが停止するのを待ちます。これは、GCがメモリの状態を安全にスキャンするために、プログラムの実行を一時的に停止させる「Stop-the-World」フェーズを実装しています。コメントにあるように、これらは一時的な実装であり、後のGoバージョンではより洗練された並行GCに置き換えられます。

usr/rsc/mem/malloc.c および usr/rsc/mem/malloc.h

これらのファイルは、Goのヒープメモリ割り当て器と、GCのためのメタデータ管理を扱います。

malloc.h で定義される Span 構造体は、メモリのページ範囲に関するメタデータを保持します。

struct Span
{
    Span *aprev;    // in list of all spans
    Span *anext;

    Span *next;     // in free lists
    byte *base;     // first byte in span
    uintptr length; // number of pages in span
    int32 cl;
    int32 state;    // state (enum above)
    union {
        int32 ref;      // reference count if state == SpanInUse (for GC)
        int32 *refbase; // ptr to packed ref counts
    };
//  void *type;     // object type if state == SpanInUse (for GC)
};

Span 構造体には、ref または refbase というフィールドが追加されています。これは、オブジェクトの参照カウントを格納するためのものです。ref は大きなオブジェクト用、refbase は小さなオブジェクトのパックされた参照カウントへのポインタとして使用されます。これは、参照カウントGCを実装するための重要な変更点です。

malloc.c の findobj 関数は、GCがオブジェクトのメタデータ（特に参照カウント）を取得するために使用されます。

bool
findobj(void *v, void **obj, int64 *size, int32 **ref)
{
    Span *s;
    int32 siz, off, indx;

    s = spanofptr(v);
    if(s == nil || s->state != SpanInUse)
        return false;

    // Big object
    if(s->cl < 0) {
        if(obj)
            *obj = s->base;
        if(size)
            *size = s->length<<PageShift;
        if(ref)
            *ref = &s->ref;
        return true;
    }

    // Small object
    if((byte*)v >= (byte*)s->refbase)
        return false;
    siz = classtosize[s->cl];
    off = (byte*)v - (byte*)s->base;
    indx = off/siz;
    if(obj)
        *obj = s->base + indx*siz;
    if(size)
        *size = siz;
    if(ref)
        *ref = s->refbase + indx;
    return true;
}

findobj は、与えられたメモリポインタ v がどの Span に属するかを特定し、その Span の状態に基づいて、オブジェクトのベースポインタ、サイズ、そして参照カウントへのポインタを返します。これにより、GCはメモリ上の任意のポインタから、それが指すオブジェクトのメタデータ（特に参照カウント）にアクセスできるようになります。

free 関数では、解放されるオブジェクトの参照カウントがチェックされます。

void
free(void *v)
{
    ...
    if(s->cl < 0) { // Big object
        if(s->ref != 0 && s->ref != RefManual && s->ref != RefStack)
            throw("free - bad ref count");
        s->ref = RefFree;
        ...
    } else { // Small object
        ...
        if(s->refbase[n] != 0 && s->refbase[n] != RefManual && s->refbase[n] != RefStack)
            throw("free - bad ref count1");
        s->refbase[n] = RefFree;
        ...
    }
    ...
}

このコードは、オブジェクトが解放される際に、その参照カウントが 0 (通常の解放)、RefManual (手動管理)、または RefStack (スタック割り当て) のいずれかであることを確認しています。これら以外の値であれば、「不正な参照カウント」としてエラーをスローします。これは、参照カウントGCが正しく機能しているか、またはデバッグのために参照カウントの整合性をチェックする初期的なメカニズムです。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/3f8aa662e9710f821411dc9c6f0f0be8c756e40d

参考にした情報源リンク

• Go言語のガベージコレクションの歴史と進化に関する情報:
  • https://go.dev/blog/go15gc
  • https://medium.com/@ankur_anand/go-garbage-collector-a-comprehensive-guide-7f3b3c4b6f1d
  • https://dev.to/aurelievache/go-s-garbage-collector-from-the-beginning-to-now-300
• Go言語の初期開発に関する情報:
  • https://en.wikipedia.org/wiki/Go_(programming_language)
• Goランタイムの内部構造に関する情報:
  • https://go.dev/src/runtime/proc.go (関連するコメントの存在)
• ガベージコレクションアルゴリズムに関する一般的な情報:
  • https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
  • https://en.wikipedia.org/wiki/Reference_counting
  • https://en.wikipedia.org/wiki/Mark-and-sweep
• mmap システムコールに関する情報:
  • https://man7.org/linux/man-pages/man2/mmap.2.html