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

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

このコミットは、Goランタイムにおけるハッシュマップへの要素挿入中に発生する可能性のあるガベージコレクション (GC) の問題を修正します。具体的には、間接的にキーや値を格納するハッシュマップに要素を挿入する際、GCがハッシュマップを不整合な状態と認識してしまう問題を解決し、Goプログラムの安定性と堅牢性を向上させています。

コミット

commit 54dffda2b6f967d216b59fcbda116c74b07c4990
Author: Jan Ziak <0xe2.0x9a.0x9b@gmail.com>
Date:   Tue Mar 19 22:17:39 2013 +0100

    runtime: prevent garbage collection during hashmap insertion
    
    Inserting a key-value pair into a hashmap storing keys or values
    indirectly can cause the garbage collector to find the hashmap in
    an inconsistent state.
    
    Fixes #5074.
    
    R=golang-dev, minux.ma, rsc
    CC=golang-dev
    https://golang.org/cl/7913043

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

https://github.com/golang/go/commit/54dffda2b6f967d216b59fcbda116c74b07c4990

元コミット内容

Goランタイムにおいて、ハッシュマップへの挿入中にガベージコレクションが発生するのを防ぐ変更です。間接的にキーや値を格納するハッシュマップにキーと値のペアを挿入する際、ガベージコレクタがハッシュマップを不整合な状態で見つける可能性がありました。このコミットは、Issue #5074 を修正します。

変更の背景

この変更の背景には、Goランタイムのガベージコレクタとハッシュマップの実装における特定の競合状態が存在しました。Goのハッシュマップ（map型）は、内部的にキーと値を直接格納するのではなく、ポインタを介して間接的に参照する場合があります。これは、キーや値のサイズが大きい場合や、インターフェース型のように動的な型情報を持つ場合に特に顕著です。

問題は、このような間接的なキーや値を持つハッシュマップに新しい要素を挿入するプロセス中に発生しました。ハッシュマップへの挿入は複数のステップからなる操作であり、メモリの割り当て、ポインタの更新、データのコピーなどが含まれます。この一連の操作の途中でガベージコレクタが実行されると、ハッシュマップの内部構造が一時的に不整合な状態になる可能性がありました。

具体的には、新しいキーや値のためのメモリが割り当てられたものの、まだハッシュマップのデータ構造に完全にリンクされていない、あるいは古いデータがまだ参照されているが新しいデータへのポインタが部分的に更新されている、といった状態です。このような「中間状態」でGCがヒープをスキャンすると、GCは無効なポインタを検出したり、到達可能なオブジェクトを誤って解放したり、あるいはその逆で到達不能なオブジェクトを解放し損ねたりする可能性がありました。これにより、ランタイムパニック、データ破損、メモリリークといった深刻なバグにつながる恐れがありました。

Issue #5074 は、まさにこの問題、すなわちハッシュマップへの挿入中にGCが実行されることによって引き起こされるランタイムのクラッシュを報告していました。このコミットは、この競合状態を解消し、ハッシュマップの挿入操作がアトミックにGCから保護されるようにすることで、ランタイムの堅牢性を高めることを目的としています。

前提知識の解説

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

ガベージコレクションは、プログラムが動的に割り当てたメモリのうち、もはやどの部分からも参照されていない（到達不能な）メモリ領域を自動的に解放するプロセスです。これにより、プログラマは手動でのメモリ管理の負担から解放され、メモリリークやダングリングポインタといった一般的なメモリ関連のバグを防ぐことができます。

GoのGCは、並行マーク＆スイープ方式を採用しています。これは、プログラムの実行と並行してGCが動作し、アプリケーションの実行を長時間停止させる「ストップ・ザ・ワールド」フェーズを最小限に抑えることを目指しています。GCの主なフェーズは以下の通りです。

  1. マークフェーズ: プログラムのルート（グローバル変数、スタック上の変数など）から到達可能なすべてのオブジェクトをマークします。
  2. スイープフェーズ: マークされなかった（到達不能な）オブジェクトが占めるメモリ領域を解放し、再利用可能な状態にします。

GCが正しく機能するためには、GCがヒープをスキャンする際に、すべてのデータ構造が整合性の取れた状態である必要があります。もしデータ構造が一時的に不整合な状態にあるときにGCがスキャンを行うと、誤った判断を下し、プログラムのクラッシュやデータ破損を引き起こす可能性があります。

Goのハッシュマップ (map)

Goのmap型は、キーと値のペアを格納するための組み込みのデータ構造です。内部的にはハッシュテーブルとして実装されており、キーのハッシュ値に基づいて値を効率的に検索、挿入、削除できます。Goのmapは、ランタイムのCコード（src/pkg/runtime/hashmap.cなど）で実装されています。

Goのハッシュマップは、キーや値の型に応じて、それらを直接ハッシュマップのバケットに格納するか、あるいはポインタを介して間接的にヒープに格納するかを決定します。

  • 直接格納: キーや値が比較的小さく、ポインタを含まない（例: int, string, 小さなstruct）場合、それらはハッシュマップの内部構造に直接埋め込まれることがあります。
  • 間接格納: キーや値が大きい、あるいはポインタを含む（例: []byte, interface{}, 大きなstruct）場合、それらはヒープに別途割り当てられ、ハッシュマップはそれらへのポインタを格納します。この「間接」参照が、本コミットで修正される問題の核心に関わってきます。

runtime·mallocgc と dogc フラグ

runtime·mallocgc は、Goランタイムがメモリをヒープに割り当てるために使用する内部関数です。この関数は、ガベージコレクタと密接に連携して動作します。

runtime·mallocgc には、メモリ割り当て中にGCの動作を制御するためのフラグが渡されます。このコミットで特に重要なのは、dogc (do garbage collection) フラグです。通常、dogc は 1 に設定され、メモリ割り当て中にGCが必要であれば実行されることを許可します。しかし、特定のクリティカルなセクション（例えば、GCがデータ構造の整合性を期待するような操作中）では、dogc を 0 に設定することで、その割り当て操作中にGCがトリガーされるのを一時的に抑制することができます。これは、GCが不整合な状態のデータ構造をスキャンするのを防ぐための重要なメカニズムです。

技術的詳細

このコミットの技術的な解決策は、主に以下の2つの側面から構成されています。

  1. ハッシュマップ挿入時のGC抑制: ハッシュマップに間接的なキーや値を挿入する際に、新しいキーや値のためのメモリを割り当てる runtime·mallocgc 呼び出しにおいて、GCが実行されないように dogc=0 フラグを設定します。
  2. GCスキャン時のハッシュマップ整合性チェックの強化: GCがハッシュマップをスキャンする際に、間接的なキーや値のポインタが有効なヒープ領域を指しているかをデバッグモードでチェックするアサーションを追加します。

src/pkg/runtime/hashmap.c の変更

runtime·mapassign 関数は、Goのmapにキーと値のペアを割り当てる（挿入または更新する）ランタイム関数です。この関数内で、新しいキーや値が間接的に格納される必要がある場合、runtime·mal（古いメモリ割り当て関数）または runtime·mallocgc が呼び出されます。

変更前は、runtime·mal が使用されていましたが、これはGCの動作を制御する機能がありませんでした。変更後、runtime·mallocgc が導入され、その際に dogc=0 フラグが渡されるようになりました。

// 変更前 (runtime·mal は GC を考慮しない)
if(h->flag & IndirectKey)
    *(void**)res = runtime·mal(t->key->size);
if(h->flag & IndirectVal)
    *(void**)(res+h->valoff) = runtime·mal(t->elem->size);

// 変更後 (runtime·mallocgc に dogc=0 を渡す)
if(h->flag & IndirectKey)
    *(void**)res = runtime·mallocgc(t->key->size, 0, 0, 1); // dogc=0
if(h->flag & IndirectVal)
    *(void**)(res+h->valoff) = runtime·mallocgc(t->elem->size, 0, 0, 1); // dogc=0

runtime·mallocgc(size, typ, dogc, zeroed) の引数は以下の通りです。

  • size: 割り当てるメモリのサイズ。
  • typ: 割り当てるオブジェクトの型情報（GCがポインタをスキャンするために使用）。ここでは 0 (nil) が渡されており、型情報がないことを示唆しています。これは、割り当てられたメモリが後で型付けされるためかもしれません。
  • dogc: ガベージコレクションを許可するかどうか。0 は許可しないことを意味します。
  • zeroed: 割り当てられたメモリをゼロクリアするかどうか。1 はゼロクリアすることを意味します。

この変更により、ハッシュマップへのキー/値の挿入中に新しいメモリが割り当てられる際、GCがその割り当て操作の途中で実行されることがなくなります。これにより、ハッシュマップが一時的に不整合な状態にある間にGCがスキャンを行うことを防ぎます。

src/pkg/runtime/mgc0.c の変更

scanblock 関数は、GCのマークフェーズ中にメモリブロックをスキャンし、そこに含まれるポインタを特定してマークする役割を担います。この関数内で、ハッシュマップのキーや値が間接的に参照されている場合（d.indirectkey または d.indirectval が真の場合）、GCはそれらのポインタをたどって参照先のオブジェクトをマークする必要があります。

このコミットでは、デバッグビルド (Debug マクロが定義されている場合) において、間接的なキーや値のポインタが有効なヒープ領域 (arena_start から arena_used の間) を指しているかをチェックするアサーションが追加されました。

// 変更前
else
    *ptrbufpos++ = (PtrTarget){*(void**)d.key_data, mapkey_ti};

// 変更後
else {
    if(Debug) {
        obj = *(void**)d.key_data;
        if(!(arena_start <= obj && obj < arena_used))
            runtime·throw("scanblock: inconsistent hashmap");
    }
    *ptrbufpos++ = (PtrTarget){*(void**)d.key_data, mapkey_ti};
}

同様のチェックが値 (d.val_data) に対しても追加されています。

このアサーションは、ハッシュマップの挿入中にGCが実行されることによって引き起こされる不整合な状態を、デバッグビルドで早期に検出するためのものです。もし runtime·mallocgc の dogc=0 によるGC抑制が何らかの理由で機能しなかったり、他の競合状態が存在したりした場合、このチェックが runtime·throw を呼び出してパニックを引き起こし、問題の根本原因を特定するのに役立ちます。

src/pkg/runtime/gc_test.go の変更

このファイルには、TestGcHashmapIndirection という新しいテストケースが追加されました。このテストは、ハッシュマップへの間接的なキーの挿入がGCと競合しないことを検証するために設計されています。

func TestGcHashmapIndirection(t *testing.T) {
    defer debug.SetGCPercent(debug.SetGCPercent(1))
    runtime.GC()
    type T struct {
        a [256]int
    }
    m := make(map[T]T)
    for i := 0; i < 2000; i++ {
        var a T
        a.a[0] = i
        m[a] = T{}
    }
}
  • defer debug.SetGCPercent(debug.SetGCPercent(1)): GCのトリガー頻度を非常に高く設定し、GCが頻繁に実行されるようにします。SetGCPercent(1) は、ヒープサイズが1%増加するごとにGCをトリガーするように設定します。これにより、ハッシュマップ挿入中にGCが実行される可能性が高まります。テストの終了時には元のGCパーセンテージに戻します。
  • runtime.GC(): 明示的にGCを実行し、クリーンな状態からテストを開始します。
  • type T struct { a [256]int }: 比較的大きなサイズの構造体 T を定義します。この構造体は、ハッシュマップのキーとして使用される際に、Goランタイムが間接的に（ポインタを介して）格納する可能性が高い型です。
  • m := make(map[T]T): キーと値の両方に T 型を使用するハッシュマップを作成します。
  • for i := 0; i < 2000; i++: 2000回ループして、ハッシュマップに新しい要素を挿入します。各キーはユニークになるように a.a[0] = i で設定されます。

このテストは、GCが頻繁に発生する状況下で、間接的なキーを持つハッシュマップへの多数の挿入操作が、ランタイムパニックやクラッシュを引き起こさないことを確認します。もし修正が不十分であれば、このテストは失敗するはずです。

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

src/pkg/runtime/gc_test.go

--- a/src/pkg/runtime/gc_test.go
+++ b/src/pkg/runtime/gc_test.go
@@ -7,6 +7,7 @@ package runtime_test
 import (
 	"os"
 	"runtime"
+	"runtime/debug"
 	"testing"
 )
 
@@ -82,3 +83,17 @@ func TestGcDeepNesting(t *testing.T) {
 		t.Fail()
 	}
 }
+
+func TestGcHashmapIndirection(t *testing.T) {
+	defer debug.SetGCPercent(debug.SetGCPercent(1))
+	runtime.GC()
+	type T struct {
+		a [256]int
+	}
+	m := make(map[T]T)
+	for i := 0; i < 2000; i++ {
+		var a T
+		a.a[0] = i
+		m[a] = T{}
+	}
+}

src/pkg/runtime/hashmap.c

--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -1016,10 +1016,12 @@ runtime·mapassign(MapType *t, Hmap *h, byte *ak, byte *av)
 	res = nil;
 	hit = hash_insert(t, h, ak, (void**)&res);
 	if(!hit) {
+		// Need to pass dogc=0 to runtime·mallocgc because the garbage collector
+		// is assuming that all hashmaps are in a consistent state.
 		if(h->flag & IndirectKey)
-			*(void**)res = runtime·mal(t->key->size);
+			*(void**)res = runtime·mallocgc(t->key->size, 0, 0, 1);
 		if(h->flag & IndirectVal)
-			*(void**)(res+h->valoff) = runtime·mal(t->elem->size);
+			*(void**)(res+h->valoff) = runtime·mallocgc(t->elem->size, 0, 0, 1);
 	}
 	t->key->alg->copy(t->key->size, hash_keyptr(h, res), ak);
 	t->elem->alg->copy(t->elem->size, hash_valptr(h, res), av);

src/pkg/runtime/mgc0.c

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -932,14 +932,26 @@ scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
 					if(!(mapkey_kind & KindNoPointers) || d.indirectkey) {
 						if(!d.indirectkey)
 							*objbufpos++ = (Obj){d.key_data, mapkey_size, mapkey_ti};
-						else
+						else {
+							if(Debug) {
+								obj = *(void**)d.key_data;
+								if(!(arena_start <= obj && obj < arena_used))
+									runtime·throw("scanblock: inconsistent hashmap");
+							}
 							*ptrbufpos++ = (PtrTarget){*(void**)d.key_data, mapkey_ti};
+						}
 					}
 					if(!(mapval_kind & KindNoPointers) || d.indirectval) {
 						if(!d.indirectval)
 							*objbufpos++ = (Obj){d.val_data, mapval_size, mapval_ti};
-						else
+						else {
+							if(Debug) {
+								obj = *(void**)d.val_data;
+								if(!(arena_start <= obj && obj < arena_used))
+									runtime·throw("scanblock: inconsistent hashmap");
+							}
 							*ptrbufpos++ = (PtrTarget){*(void**)d.val_data, mapval_ti};
+						}
 					}
 				}
 			}

コアとなるコードの解説

src/pkg/runtime/gc_test.go

  • import "runtime/debug" の追加: debug.SetGCPercent 関数を使用するために、runtime/debug パッケージをインポートします。
  • TestGcHashmapIndirection 関数の追加:
    • defer debug.SetGCPercent(debug.SetGCPercent(1)): この行は、テストの開始時にGCのトリガー頻度を非常に高く設定し（ヒープサイズが1%増加するごとにGCをトリガー）、テスト終了時に元の設定に戻すためのものです。これにより、ハッシュマップへの挿入中にGCが実行される可能性を最大化し、競合状態を再現しやすくします。
    • runtime.GC(): テスト開始前に明示的にGCを実行し、ヒープをクリーンな状態にします。
    • type T struct { a [256]int }: 256個のint配列を持つ構造体Tを定義します。このサイズは、Goランタイムがこの型の値をハッシュマップに直接埋め込むのではなく、ヒープに割り当ててポインタで参照する（間接的に格納する）可能性が高いように意図されています。これにより、問題の対象となる「間接的なキー/値」のシナリオをシミュレートします。
    • m := make(map[T]T): キーと値の両方にT型を使用するマップを作成します。
    • for i := 0; i < 2000; i++: 2000回ループして、マップに新しいキーと値のペアを挿入します。各キーはa.a[0] = iによってユニークに設定されます。この多数の挿入操作中に、GCが頻繁に実行されることで、以前のバグが再現されるかどうかを検証します。テストがパニックを起こさずに完了すれば、修正が成功したことを意味します。

src/pkg/runtime/hashmap.c

  • runtime·mal から runtime·mallocgc への変更:
    • runtime·mapassign 関数内で、ハッシュマップに新しいキーや値のためのメモリを割り当てる際に、以前使用されていた runtime·mal 関数が runtime·mallocgc に置き換えられました。
    • runtime·mallocgc(t->key->size, 0, 0, 1): ここで重要なのは、3番目の引数である dogc フラグが 0 に設定されている点です。これは、「このメモリ割り当て操作中はガベージコレクションを実行しない」という指示をGCに与えます。
    • コメントの追加: // Need to pass dogc=0 to runtime·mallocgc because the garbage collector // is assuming that all hashmaps are in a consistent state. というコメントが追加され、この変更の理由が明確に説明されています。ハッシュマップへの挿入は複数のステップからなる操作であり、その途中でGCが実行されるとハッシュマップが不整合な状態にあるとGCが誤解する可能性があるため、このクリティカルな期間中はGCを抑制する必要があることを示しています。

src/pkg/runtime/mgc0.c

  • GCスキャン時のハッシュマップ整合性チェックの追加:
    • scanblock 関数は、GCのマークフェーズ中にヒープ上のオブジェクトをスキャンし、ポインタをたどって到達可能なオブジェクトをマークします。
    • ハッシュマップのキーや値が間接的に参照されている場合（d.indirectkey または d.indirectval が真の場合）、GCはそれらのポインタが指すメモリ領域をスキャンする必要があります。
    • 追加されたコードブロックは、Debug マクロが定義されている（つまりデバッグビルドである）場合にのみ有効になります。
    • obj = *(void**)d.key_data; および obj = *(void**)d.val_data;: 間接的なキーまたは値のポインタが指すアドレスを取得します。
    • if(!(arena_start <= obj && obj < arena_used)) runtime·throw("scanblock: inconsistent hashmap");: 取得したアドレスが、Goランタイムのヒープ領域（arena_start から arena_used の間）内に収まっているかをチェックします。もしアドレスがヒープの範囲外を指している場合、それはハッシュマップが不整合な状態にあることを意味し、runtime·throw を呼び出してパニックを発生させます。
    • このチェックは、runtime·mallocgc の dogc=0 によるGC抑制が正しく機能していることを検証するためのセーフティネットとして機能します。もし何らかの理由でGCが不整合なハッシュマップをスキャンしてしまった場合、このアサーションが問題を早期に検出し、デバッグを容易にします。

これらの変更により、Goランタイムはハッシュマップへの挿入操作中にGCが不整合な状態をスキャンすることを防ぎ、同時にデバッグビルドではその整合性を積極的にチェックすることで、より堅牢なメモリ管理を実現しています。

関連リンク

参考にした情報源リンク

  • Goのガベージコレクションに関するドキュメントやブログ記事 (一般的なGo GCの仕組みについて)
  • Goのmap実装に関する技術記事やソースコード解析 (Goのmapがどのようにキーと値を格納するかについて)
  • runtime·mallocgc 関数のGoランタイムソースコード (特にdogcフラグの挙動について)
  • Goのテストフレームワークとruntime/debugパッケージのドキュメント (テストケースの理解のため)