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

このコミットは、Goランタイムのハッシュマップ（map型）の内部構造に対するガベージコレクション（GC）の挙動を最適化するものです。具体的には、ハッシュマップのバケット配列がポインタを含んでいるにもかかわらず、GCがその配列自体を自動的にスキャンしないように変更し、代わりにhash_gciterという専用のイテレータを通じてポインタをGCに明示的に通知することで、GCの効率と正確性を向上させています。これにより、Goのマップ操作におけるGCのオーバーヘッドが削減され、バグ6119が修正されました。

コミット

commit 0df438c683d7a2b8acb47d767ff37c3b22c1b61d
Author: Keith Randall <khr@golang.org>
Date:   Tue Aug 13 12:36:03 2013 -0700

    runtime: tell GC not to scan internal hashmap structures.
    We'll do it ourselves via hash_gciter, thanks.
    Fixes bug 6119.
    
    R=golang-dev, dvyukov, cookieo9, rsc
    CC=golang-dev
    https://golang.org/cl/12840043

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

https://github.com/golang/go/commit/0df438c683d7a2b8acb47d767ff37c3b22c1b61d

元コミット内容

--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -259,7 +259,10 @@ hash_init(MapType *t, Hmap *h, uint32 hint)
 		// done lazily later.
 		buckets = nil;
 	} else {
-		buckets = runtime·mallocgc(bucketsize << B, 0, FlagNoZero);
+		buckets = runtime·mallocgc(bucketsize << B, 0, FlagNoZero | FlagNoPointers);
+		// Note: the array really does have pointers, but we tell the gc about
+		// them explicitly via gciter below.  We use FlagNoPointers to prevent
+		// the gc from scanning the bucket array itself.  Fixes issue 6119.
 		for(i = 0; i < (uintptr)1 << B; i++) {
 			b = (Bucket*)(buckets + i * bucketsize);
 			clearbucket(b);
@@ -330,7 +333,7 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)
 			if((hash & newbit) == 0) {
 				if(xi == BUCKETSIZE) {
 					if(checkgc) mstats.next_gc = mstats.heap_alloc;
-					newx = runtime·mallocgc(h->bucketsize, 0, FlagNoZero);
+					newx = runtime·mallocgc(h->bucketsize, 0, FlagNoZero | FlagNoPointers);
 					clearbucket(newx);
 					x->overflow = newx;
 					x = newx;
@@ -355,7 +358,7 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)
 				} else {
 					if(yi == BUCKETSIZE) {
 					if(checkgc) mstats.next_gc = mstats.heap_alloc;
-					newy = runtime·mallocgc(h->bucketsize, 0, FlagNoZero);
+					newy = runtime·mallocgc(h->bucketsize, 0, FlagNoZero | FlagNoPointers);
 					clearbucket(newy);
 					y->overflow = newy;
 					y = newy;
@@ -451,7 +454,7 @@ hash_grow(MapType *t, Hmap *h)
 	old_buckets = h->buckets;
 	// NOTE: this could be a big malloc, but since we don't need zeroing it is probably fast.
 	if(checkgc) mstats.next_gc = mstats.heap_alloc;
-	new_buckets = runtime·mallocgc((uintptr)h->bucketsize << (h->B + 1), 0, FlagNoZero);
+	new_buckets = runtime·mallocgc((uintptr)h->bucketsize << (h->B + 1), 0, FlagNoZero | FlagNoPointers);
 	flags = (h->flags & ~(Iterator | OldIterator));
 	if((h->flags & Iterator) != 0) {
 		flags |= OldIterator;
@@ -615,7 +618,7 @@ hash_insert(MapType *t, Hmap *h, void *key, void *value)
 	hash = h->hash0;
 	t->key->alg->hash(&hash, t->key->size, key);
 	if(h->buckets == nil) {
-		h->buckets = runtime·mallocgc(h->bucketsize, 0, FlagNoZero);
+		h->buckets = runtime·mallocgc(h->bucketsize, 0, FlagNoZero | FlagNoPointers);
 		b = (Bucket*)(h->buckets);
 		clearbucket(b);
 	}
@@ -665,7 +668,7 @@ hash_insert(MapType *t, Hmap *h, void *key, void *value)
 	if(inserti == nil) {
 		// all current buckets are full, allocate a new one.
 		if(checkgc) mstats.next_gc = mstats.heap_alloc;
-		newb = runtime·mallocgc(h->bucketsize, 0, FlagNoZero);
+		newb = runtime·mallocgc(h->bucketsize, 0, FlagNoZero | FlagNoPointers);
 		clearbucket(newb);
 		b->overflow = newb;
 		inserti = newb->tophash;

変更の背景

この変更は、Goランタイムのガベージコレクタ（GC）がハッシュマップの内部構造を不必要にスキャンすることによって発生していたバグ（Issue 6119）を修正するために導入されました。

Goのハッシュマップ（map型）は、内部的にバケットと呼ばれる配列構造を使用してキーと値を格納します。これらのバケットには、キーや値、そしてオーバーフローバケットへのポインタが含まれることがあります。GoのGCは、ヒープ上のオブジェクトをスキャンして到達可能なポインタを追跡し、到達不能なオブジェクトを解放することでメモリを管理します。

しかし、ハッシュマップのバケット配列は、その構造上、GCが自動的にスキャンすると問題が生じる可能性がありました。具体的には、バケット内のデータ配置や、オーバーフローバケットへのリンクの管理方法がGCの一般的なポインタスキャンロジックと完全に一致しない場合、GCが誤ってポインタを認識したり、逆にポインタを見落としたりするリスクがありました。これにより、GCがハッシュマップの整合性を損なったり、メモリリークやクラッシュを引き起こす可能性がありました。

このコミットの目的は、GCがハッシュマップの内部構造を「賢く」スキャンできるようにすることです。つまり、GCにバケット配列全体を盲目的にスキャンさせるのではなく、ハッシュマップのランタイムコード自身が、hash_gciterという専用のメカニズムを通じて、GCが必要とするポインタ情報のみを正確に提供するように変更することです。これにより、GCの正確性が保証され、同時に不必要なスキャンが排除されることでGCのパフォーマンスも向上します。

前提知識の解説

このコミットを理解するためには、以下のGoランタイムとガベージコレクションに関する前提知識が必要です。

1. Goのガベージコレクション (GC)

Goは、自動メモリ管理のために並行マーク＆スイープ型ガベージコレクタを採用しています。GCの基本的なプロセスは以下の通りです。

• マークフェーズ (Mark Phase): GCは、プログラムが現在使用しているオブジェクト（ルートセットから到達可能なオブジェクト）を特定します。ルートセットには、グローバル変数、スタック上の変数、レジスタなどが含まれます。GCはこれらのルートからポインタをたどり、到達可能なすべてのオブジェクトに「マーク」を付けます。
• スイープフェーズ (Sweep Phase): マークされなかったオブジェクト（到達不能なオブジェクト）は、もはやプログラムから参照されていないと判断され、メモリが解放されます。

GCが正しく機能するためには、ヒープ上のどのメモリ領域がポインタを含んでいるかを正確に知る必要があります。Goのランタイムは、型情報（Type Information）を利用して、各オブジェクトのメモリレイアウトを把握し、どこにポインタがあるかを識別します。

2. runtime·mallocgc とメモリ割り当てフラグ

runtime·mallocgcは、Goランタイムがヒープからメモリを割り当てるために使用する内部関数です。この関数は、割り当てるメモリのサイズに加えて、いくつかのフラグを受け取ります。これらのフラグは、GCに対して割り当てられたメモリの特性を伝えます。

• FlagNoZero: このフラグは、割り当てられたメモリをゼロクリアしないことをGCに指示します。通常、Goは新しく割り当てられたメモリをゼロクリアしますが、パフォーマンス上の理由から、後で初期化されることが確実な場合はこのフラグを使用してゼロクリアをスキップできます。
• FlagNoPointers: このフラグが重要です。これは、割り当てられたメモリ領域に「ポインタが含まれていない」ことをGCに伝えます。GCは、このフラグが設定されたメモリ領域を自動的にスキャンしません。これは、GCのオーバーヘッドを削減するために使用されますが、もし実際にポインタが含まれているにもかかわらずこのフラグを設定すると、GCがポインタを見落とし、メモリリークや不正なメモリアクセスを引き起こす可能性があります。

3. Goのハッシュマップ (map) の内部構造

Goのmapは、内部的にハッシュテーブルとして実装されています。その主要な構成要素は以下の通りです。

• バケット (Bucket): キーと値のペアを格納する基本的な単位です。各バケットは固定サイズで、複数のキー/値ペアを保持できます。
• オーバーフローバケット (Overflow Bucket): バケットが満杯になった場合、新しいキー/値ペアはオーバーフローバケットに格納されます。オーバーフローバケットは、元のバケットからポインタでリンクされます。
• ポインタ (Pointers): バケット内には、キーや値がポインタ型である場合、それらのポインタが格納されます。また、オーバーフローバケットへのリンクもポインタです。

4. hash_gciter

hash_gciterは、Goランタイムのハッシュマップ実装の一部であり、GCがハッシュマップの内部構造を正確にスキャンするためのカスタムイテレータ（走査メカニズム）です。FlagNoPointersが設定されたメモリ領域はGCによって自動スキャンされないため、hash_gciterのようなカスタムメカニズムが、その領域内のポインタをGCに明示的に「提示」する必要があります。これにより、GCはハッシュマップの複雑な内部構造を正しく理解し、到達可能なオブジェクトをマークできます。

技術的詳細

このコミットの核心は、Goのハッシュマップの内部バケット配列のメモリ割り当てにおいて、runtime·mallocgc関数にFlagNoPointersフラグを追加した点にあります。

従来のGoのGCは、ヒープ上のすべてのメモリ領域を、その型情報に基づいてポインタの有無を判断し、ポインタがあればスキャンしていました。しかし、ハッシュマップのバケット配列は、その内部構造がGCの一般的なポインタスキャンロジックと完全に一致しない場合がありました。例えば、バケット内のキーや値の配置、あるいはオーバーフローバケットへのポインタの管理方法が、GCが期待するポインタのオフセットと異なる場合、GCが誤ったメモリ位置をポインタとして解釈したり、逆に有効なポインタを見落としたりする可能性がありました。

Issue 6119は、まさにこの問題に起因するバグでした。GCがハッシュマップの内部構造を誤ってスキャンすることで、不正なメモリアクセスや、GCがオブジェクトを誤って解放してしまうなどの問題が発生していました。

このコミットでは、この問題を解決するために以下の戦略が取られました。

1. FlagNoPointersの導入: runtime·mallocgcでハッシュマップのバケット配列を割り当てる際に、FlagNoPointersフラグを設定します。これにより、GCはバケット配列のメモリ領域を「ポインタを含まない」ものとして扱い、自動的なポインタスキャンを行わなくなります。
2. hash_gciterによる明示的なポインタ通知: バケット配列には実際にはポインタ（キー、値、オーバーフローバケットへのリンク）が含まれているため、GCがそれらを見落とさないようにする必要があります。そこで、Goランタイムのハッシュマップコードは、hash_gciterという専用のメカニズムを通じて、バケット配列内の有効なポインタをGCに明示的に通知するように変更されました。hash_gciterは、ハッシュマップの内部構造を正確に理解しているため、どのメモリ位置がポインタであるかを正確にGCに伝えることができます。

このアプローチにより、以下の利点が得られます。

• GCの正確性の向上: GCがハッシュマップの内部構造を誤って解釈するリスクがなくなります。hash_gciterが提供する正確なポインタ情報に基づいてのみスキャンが行われるため、バグ6119のような問題が修正されます。
• GCパフォーマンスの最適化: GCがバケット配列全体を盲目的にスキャンする必要がなくなるため、不必要なメモリ領域のスキャンが削減され、GCのオーバーヘッドが軽減されます。これは、特に大規模なマップを使用する場合にパフォーマンス上のメリットをもたらします。

要するに、この変更は、GCにハッシュマップの内部構造を「任せる」のではなく、ハッシュマップ自身がGCに対して「私はこのポインタを持っています」と明示的に教えることで、より堅牢で効率的なGCを実現しています。

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

変更はすべて src/pkg/runtime/hashmap.c ファイル内で行われています。 具体的には、ハッシュマップのバケットやオーバーフローバケットを割り当てる runtime·mallocgc 関数の呼び出し箇所に、FlagNoPointers フラグが追加されています。

// hash_init 関数内
-		buckets = runtime·mallocgc(bucketsize << B, 0, FlagNoZero);
+		buckets = runtime·mallocgc(bucketsize << B, 0, FlagNoZero | FlagNoPointers);
 		// Note: the array really does have pointers, but we tell the gc about
 		// them explicitly via gciter below.  We use FlagNoPointers to prevent
 		// the gc from scanning the bucket array itself.  Fixes issue 6119.

// evacuate 関数内 (バケットの再配置時)
-					newx = runtime·mallocgc(h->bucketsize, 0, FlagNoZero);
+					newx = runtime·mallocgc(h->bucketsize, 0, FlagNoZero | FlagNoPointers);
-					newy = runtime·mallocgc(h->bucketsize, 0, FlagNoZero);
+					newy = runtime·mallocgc(h->bucketsize, 0, FlagNoZero | FlagNoPointers);

// hash_grow 関数内 (マップの拡張時)
-	new_buckets = runtime·mallocgc((uintptr)h->bucketsize << (h->B + 1), 0, FlagNoZero);
+	new_buckets = runtime·mallocgc((uintptr)h->bucketsize << (h->B + 1), 0, FlagNoZero | FlagNoPointers);

// hash_insert 関数内 (要素挿入時)
-	h->buckets = runtime·mallocgc(h->bucketsize, 0, FlagNoZero);
+	h->buckets = runtime·mallocgc(h->bucketsize, 0, FlagNoZero | FlagNoPointers);
-		newb = runtime·mallocgc(h->bucketsize, 0, FlagNoZero);
+		newb = runtime·mallocgc(h->bucketsize, 0, FlagNoZero | FlagNoPointers);

コアとなるコードの解説

上記の変更は、Goのハッシュマップが内部的に使用するメモリ割り当ての挙動を根本的に変更しています。

runtime·mallocgcは、Goランタイムがヒープからメモリを確保するための低レベルな関数です。この関数に渡される最後の引数は、割り当てられるメモリの特性をGCに伝えるためのフラグです。

変更前は、FlagNoZeroのみが設定されていました。これは、割り当てられたメモリがゼロクリアされないことを意味しますが、GCは依然としてそのメモリ領域をポインタが含まれる可能性があるものとして自動的にスキャンしようとします。

変更後、FlagNoPointersフラグが追加されました。このフラグは、GCに対して「このメモリ領域には、GCが自動的にスキャンすべきポインタは含まれていない」と明示的に伝えます。

しかし、ハッシュマップのバケット配列には実際にはポインタ（キー、値、オーバーフローバケットへのリンク）が含まれています。この矛盾は、追加されたコメントによって説明されています。

// Note: the array really does have pointers, but we tell the gc about
// them explicitly via gciter below.  We use FlagNoPointers to prevent
// the gc from scanning the bucket array itself.  Fixes issue 6119.

このコメントは、以下の重要な点を明らかにしています。

1. ポインタの存在: バケット配列は確かにポインタを含んでいます。
2. GCの自動スキャン停止: FlagNoPointersを使用することで、GCがこのバケット配列を自動的にスキャンするのを防ぎます。これは、GCがハッシュマップの複雑な内部構造を誤って解釈するのを避けるためです。
3. hash_gciterによる明示的な通知: GCは自動的にスキャンしませんが、hash_gciterという別のメカニズムが、バケット配列内の有効なポインタをGCに明示的に通知します。これにより、GCはハッシュマップ内の到達可能なオブジェクトを正確にマークできます。

この変更により、GCはハッシュマップの内部構造をより正確かつ効率的に処理できるようになり、バグ6119で報告されたようなGCの誤動作が修正されました。これは、Goのランタイムが特定のデータ構造のGC処理を最適化するために、低レベルのメモリ割り当てフラグとカスタムのGCイテレータをどのように連携させているかを示す良い例です。

関連リンク

• Go Issue 6119: https://github.com/golang/go/issues/6119
• Go CL 12840043: https://golang.org/cl/12840043

参考にした情報源リンク

• Goのガベージコレクションに関する公式ドキュメントやブログ記事
• Goランタイムのソースコード（特に src/runtime/mgc.go, src/runtime/mheap.go, src/runtime/map.go など）
• Goのmap型の内部実装に関する技術記事や解説
• runtime·mallocgc および関連するフラグに関するGoのソースコードコメント