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

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

このコミットは、Goランタイムにおけるガベージコレクション (GC) のビットマップ破損のバグを修正するものです。具体的には、GC中に複数のゴルーチンが同時にヒープのビットマップを更新しようとした際に発生する競合状態 (race condition) を解消し、ビットマップの整合性を保証します。

コミット

commit 5bfe8adee5100444cdde78d4897d1673df96c813
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Sat Jun 28 19:20:46 2014 -0700

    runtime: fix GC bitmap corruption
    Fixes #8299.
    
    R=golang-codereviews
    CC=golang-codereviews, khr, rsc
    https://golang.org/cl/103640044

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

https://github.com/golang/go/commit/5bfe8adee5100444cdde78d4897d1673df96c813

元コミット内容

このコミットは、Goランタイムのsrc/pkg/runtime/mgc0.cファイルにおいて、ガベージコレクション中のビットマップ更新ロジックを修正しています。以前は、ビットマップの更新が単純な代入操作で行われていましたが、GCが並行して実行されている場合に競合状態が発生し、ビットマップが破損する可能性がありました。このコミットでは、GCが進行中で複数のプロセッサが関与している場合に、Compare-And-Swap (CAS) 操作を用いてビットマップの更新をアトミックに行うように変更されています。

変更の背景

Goのガベージコレクタは、プログラムの実行と並行して動作する「並行GC」を採用しています。これにより、GCによるアプリケーションの一時停止（ストップ・ザ・ワールド）時間を最小限に抑え、全体的なパフォーマンスを向上させています。しかし、並行処理には常に競合状態のリスクが伴います。

このコミットの背景にある問題は、GCがヒープ上のオブジェクトをマークする際に使用する「GCビットマップ」の破損です。runtime·markfreed関数は、メモリブロックが解放されたことをビットマップに記録する役割を担っています。GCが並行して動作している間、複数のゴルーチン（またはGCワーカー）が同時に同じビットマップエントリを更新しようとすると、更新が非アトミックであるために、一方の更新が他方の更新によって上書きされ、ビットマップが不正な状態になる可能性がありました。

ビットマップの破損は、GCがヒープの状態を誤って認識することにつながり、結果として以下のような深刻な問題を引き起こす可能性があります。

  • メモリリーク: ライブなオブジェクトが誤って到達不能と判断され、解放されてしまう。
  • クラッシュ: 解放されたメモリにアクセスしようとしたり、不正なポインタを辿ろうとしたりすることで、プログラムがクラッシュする（セグメンテーション違反など）。
  • データ破損: 不正なメモリ領域への書き込みが発生し、アプリケーションのデータが破損する。

このコミットは、このようなGCビットマップの破損を防ぎ、Goランタイムの安定性と信頼性を向上させることを目的としています。

前提知識の解説

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

ガベージコレクションは、プログラムが動的に確保したメモリ領域のうち、もはや使用されていない（到達不能な）ものを自動的に解放する仕組みです。GoのGCは、主に以下のフェーズで構成されます。

  • マークフェーズ: ヒープ上のオブジェクトのうち、現在使用されている（ライブな）ものを特定します。プログラムのエントリポイント（ルート）から到達可能なすべてのオブジェクトを辿り、マークします。
  • スイープフェーズ: マークされなかった（到達不能な）オブジェクトが占めるメモリ領域を解放し、再利用可能にします。

GoのGCは、アプリケーションの実行と並行してマークフェーズの一部を実行する「並行マーク＆スイープ」方式を採用しています。これにより、GCによるアプリケーションの停止時間を短縮しています。

GCビットマップ

GCビットマップは、Goランタイムがヒープメモリの構造を効率的に管理するために使用する重要なデータ構造です。ヒープ上の各メモリブロック（オブジェクト）について、そのブロック内のどのワード（通常はポインタサイズ）がポインタを含んでいるか、どのワードが非ポインタデータを含んでいるかを示すビット列です。

  • ポインタ情報: GCは、オブジェクトを走査する際に、どのフィールドがポインタであるかを知る必要があります。ビットマップは、このポインタ情報をコンパクトに表現します。
  • マーク情報: GCのマークフェーズでは、オブジェクトがライブであるかどうかの情報もビットマップに記録されることがあります。
  • アロケーション情報: メモリブロックが現在割り当てられているか、解放されているかといった状態もビットマップで管理されることがあります。

GCビットマップが正確であることは、GCがヒープを正しく走査し、ライブなオブジェクトを誤って解放したり、到達不能なオブジェクトを誤って保持したりしないために不可欠です。

競合状態 (Race Condition) とアトミック操作

競合状態は、複数の並行プロセスやスレッドが共有リソース（この場合はGCビットマップ）に同時にアクセスし、そのアクセス順序によって結果が非決定的に変わってしまう状況を指します。特に、読み取り-変更-書き込み (Read-Modify-Write) の操作がアトミックでない場合に発生しやすいです。

例えば、ビットマップの特定のビットをセットする操作が「現在のビットマップの値を読み込む」「読み込んだ値の特定のビットを変更する」「変更した値をビットマップに書き込む」という3つのステップで行われるとします。もし2つのゴルーチンが同時にこの操作を行おうとした場合、以下のようなシナリオで競合状態が発生します。

  1. ゴルーチンAがビットマップの値を読み込む (値X)。
  2. ゴルーチンBがビットマップの値を読み込む (値X)。
  3. ゴルーチンAが読み込んだ値Xを基にビットマップの値を変更し、書き込む (値Y)。
  4. ゴルーチンBが読み込んだ値Xを基にビットマップの値を変更し、書き込む (値Z)。

この場合、ゴルーチンAの変更がゴルーチンBによって上書きされてしまい、ゴルーチンAの意図した変更が失われる可能性があります。

アトミック操作は、その操作全体が不可分であり、他の並行操作によって中断されないことを保証する操作です。これにより、競合状態を防ぎ、共有データの整合性を保つことができます。Goランタイムでは、runtime·casp (Compare-And-Swap Pointer) のような低レベルのアトミック操作が提供されており、これを用いて競合状態を安全に解決します。CASは、「もし現在の値が期待する値と一致すれば、新しい値に更新する」という操作をアトミックに行います。

技術的詳細

このコミットの技術的詳細な修正は、runtime·markfreed関数におけるGCビットマップの更新方法にあります。

runtime·markfreed関数は、メモリブロックが解放された際に、そのブロックに対応するGCビットマップのビットをbitAllocated（割り当て済み）状態に設定する役割を担っています。これは、GCがそのメモリ領域を再利用可能と認識するための重要なステップです。

修正前のコードでは、ビットマップの更新は以下の単純な代入操作で行われていました。

*b = (*b & ~(bitMask<<shift)) | (bitAllocated<<shift);

この操作は、*b（ビットマップワード）の特定のビットをクリアし、その後bitAllocatedビットをセットするというものです。しかし、これはCPUレベルでは複数の命令に分解される可能性があり、並行して実行される他のゴルーチンからのアクセスと競合する可能性がありました。

修正後のコードでは、この更新操作がGCの実行状況とプロセッサ数に応じて条件分岐するようになりました。

  1. !g->m->gcing || work.nproc == 1 の場合:

    • !g->m->gcing: GCが現在進行中でない場合。
    • work.nproc == 1: システムが単一のプロセッサで動作している場合（並行処理の競合が発生しない）。 この条件が真の場合、以前と同様の単純な代入操作が使用されます。これは、これらの条件下では競合状態が発生しないため、アトミック操作のオーバーヘッドを避けるためです。コメントにもあるように、通常操作時（GC中でない時）は、スパンビットマップは並行して更新されず、キャッシュされるか、MCentralロックによって保護されているため、競合は発生しません。

  2. else の場合 (g->m->gcing && work.nproc > 1):

    • GCが進行中であり、かつ複数のプロセッサが関与している場合。 この条件下では、複数のゴルーチンが同時にビットマップを更新しようとする競合状態が発生する可能性があります。これを解決するために、Compare-And-Swap (CAS) ループが導入されました。
    for(;;) {
    xbits = *b; // 現在のビットマップの値を読み込む
    // CAS操作: もし *b の値が xbits と同じであれば、新しい値に更新する
    if(runtime·casp((void**)b, (void*)xbits, (void*)((xbits & ~(bitMask<<shift)) | (bitAllocated<<shift))))
        break; // 更新に成功したらループを抜ける
}

    このループは、*bの現在の値をxbitsに読み込み、そのxbitsを期待値としてCAS操作を試みます。CAS操作は、*bの現在の値がxbitsと一致する場合にのみ、新しい計算された値に*bをアトミックに更新します。もし一致しない場合（つまり、他のゴルーチンがxbitsを読み込んだ後に*bを更新してしまった場合）、CASは失敗し、ループは再試行されます。これにより、ビットマップの更新が常にアトミックに行われ、競合状態による破損が防止されます。

この修正は、Goランタイムの並行GCの堅牢性を高める上で非常に重要です。

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

変更はsrc/pkg/runtime/mgc0.cファイルのruntime·markfreed関数内で行われています。

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -2731,7 +2731,7 @@ runtime·markscan(void *v)\n void\n runtime·markfreed(void *v)\n {\n-\tuintptr *b, off, shift;\n+\tuintptr *b, off, shift, xbits;\n \n \tif(0)\n \t\truntime·printf(\"markfreed %p\\n\", v);\n@@ -2742,7 +2742,18 @@ runtime·markfreed(void *v)\n \toff = (uintptr*)v - (uintptr*)runtime·mheap.arena_start;  // word offset\n \tb = (uintptr*)runtime·mheap.arena_start - off/wordsPerBitmapWord - 1;\n \tshift = off % wordsPerBitmapWord;\n-\t*b = (*b & ~(bitMask<<shift)) | (bitAllocated<<shift);\n+\tif(!g->m->gcing || work.nproc == 1) {\n+\t\t// During normal operation (not GC), the span bitmap is not updated concurrently,\n+\t\t// because either the span is cached or accesses are protected with MCentral lock.\n+\t\t*b = (*b & ~(bitMask<<shift)) | (bitAllocated<<shift);\n+\t} else {\n+\t\t// During GC other threads concurrently mark heap.\n+\t\tfor(;;) {\n+\t\t\txbits = *b;\n+\t\t\tif(runtime·casp((void**)b, (void*)xbits, (void*)((xbits & ~(bitMask<<shift)) | (bitAllocated<<shift))))\n+\t\t\t\tbreak;\n+\t\t}\n+\t}\n }\n \n // check that the block at v of size n is marked freed.\n```

## コアとなるコードの解説

`runtime·markfreed`関数は、指定されたメモリブロック`v`が解放されたことをマークするために呼び出されます。

1.  **変数の追加**: `uintptr xbits;` が追加されました。これはCAS操作で使用する、ビットマップの現在の値を一時的に保持するための変数です。
2.  **ビットマップ位置の計算**:
    *   `off = (uintptr*)v - (uintptr*)runtime·mheap.arena_start;`：解放されたメモリブロック`v`が、ヒープのアリーナ開始位置からどれくらいのワードオフセットにあるかを計算します。
    *   `b = (uintptr*)runtime·mheap.arena_start - off/wordsPerBitmapWord - 1;`：計算されたオフセットに基づき、対応するGCビットマップのワード`b`のアドレスを特定します。GoのGCビットマップは、アリーナの先頭から逆方向に配置されることがあります。
    *   `shift = off % wordsPerBitmapWord;`：ビットマップワード`*b`内で、どのビットを操作すべきかのシフト量を計算します。
3.  **条件分岐による更新ロジック**:
    *   `if(!g->m->gcing || work.nproc == 1)`:
        *   `g->m->gcing`は、現在のM（マシン、OSスレッド）がGCを実行中であるかを示すフラグです。`!g->m->gcing`はGCが実行中でないことを意味します。
        *   `work.nproc`は、GC作業に利用可能なプロセッサの数です。`work.nproc == 1`は、並行処理が行われていないことを意味します。
        *   これらの条件下では、競合状態のリスクがないため、従来の非アトミックなビットマップ更新が行われます。`*b = (*b & ~(bitMask<<shift)) | (bitAllocated<<shift);` は、`*b`の`shift`位置にある`bitMask`で指定されたビットをクリアし、代わりに`bitAllocated`ビットをセットします。
    *   `else` (`g->m->gcing && work.nproc > 1`):
        *   GCが進行中であり、複数のプロセッサが並行してGC作業を行っている場合、競合状態が発生する可能性があります。
        *   `for(;;)` ループが導入され、アトミックなCompare-And-Swap (CAS) 操作によってビットマップが更新されます。
        *   `xbits = *b;`：現在のビットマップワードの値を読み取ります。
        *   `runtime·casp((void**)b, (void*)xbits, (void*)((xbits & ~(bitMask<<shift)) | (bitAllocated<<shift)))`：
            *   `b`が指すメモリ位置の現在の値が`xbits`（読み取った古い値）と等しい場合、その値を新しく計算された値`((xbits & ~(bitMask<<shift)) | (bitAllocated<<shift))`にアトミックに更新します。
            *   CAS操作が成功した場合（`true`を返す）、`break`でループを抜けます。
            *   CAS操作が失敗した場合（`false`を返す、つまり他のゴルーチンが`xbits`を読み取った後に`*b`を更新してしまった場合）、ループは続行され、再度`*b`の値を読み取り直してCASを試みます。
        このCASループにより、複数のゴルーチンが同時にビットマップを更新しようとしても、常に一貫性のある状態が保たれます。

この変更は、Goランタイムの並行GCにおけるデータ競合を根本的に解決し、GCビットマップの整合性を保証することで、ランタイムの安定性を大幅に向上させています。

## 関連リンク

*   Go言語のガベージコレクションに関する公式ドキュメントやブログ記事 (GoのバージョンによってGCの実装は進化しているため、当時の情報と現在の情報には差異がある可能性があります)
*   GoのIssueトラッカーでの #8299 の詳細 (もし公開されていれば)

## 参考にした情報源リンク

*   Goのソースコード (`src/pkg/runtime/mgc0.c`)
*   Goのガベージコレクションに関する一般的な解説記事や論文
*   Compare-And-Swap (CAS) 操作に関する並行プログラミングの概念
*   Web検索結果 (GCビットマップの一般的な説明)
    *   go.dev (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHdc9hEGdz_HbtmoNSzVPESEd4iBrcwprbevhkGZHwbarcj-P0tdz-GWiZZDCxgaQZESn24ThDh7pwPUPgseXs71JUcSc-xK3WBuMmZEO7igm4ky9JmNN2MzSW--7eOclk=)
    *   stalkr.net (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHaobfrsn_VVeTf_3ww3_g9YYMUQLaeNVPiufusxzPJGnvEhytz2ExF6FcWSFpDffg2SycdXsEi_ysCiYJ_jkWqA1b2U2pJEmFMV22IZCTQJfYBHSwDl-K12Vye9cshRtId5NXLzAkEPREKalRJD1eI5QLNG0upLPFbMRe_u4TlujIyAqiq)
    *   marcan.st (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGJp51f2ApM1edXpk9S7pl3SZspTuWYmPH5WnNdlRRAfe6GKr45x21DMOj9M8oojU0kwWjOKC9DabL3ftqebd8-fUP0hhKSBNBUkT2clGhHGLbSGI0hRUoVUut6rBnIw48EDMKZroqxjZbeeNrEYawFSGeNFORY)
    *   github.com (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFceO5H6BowBvGT91DNcDvqye234-aY20J_0_-ZR1YKLXWFif1irVfP1ARjjutX-zQv7kn2IDKyKOpHUeY73LVn5o-Jfxy5pFJtsNv2mH2QV3WdO0wbfmBV6jK_ehinVtkum050)