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

このコミットは、Goランタイムにおけるハッシュテーブル（マップ）の内部構造に対するガベージコレクション（GC）の扱い方を変更するものです。具体的には、ハッシュテーブルに特化したGCコードを削除し、代わりに型情報に基づいてGCが動作するように修正しています。これにより、GCの汎用性が向上し、マップのGC処理がより効率的かつ正確になります。

コミット

commit fb376021bea084d5320a8059176ab86880832f5c
Author: Keith Randall <khr@golang.org>
Date:   Sat Aug 31 09:09:50 2013 -0700

    runtime: record type information for hashtable internal structures.
    Remove all hashtable-specific GC code.
    
    Fixes bug 6119.
    
    R=cshapiro, dvyukov, khr
    CC=golang-dev
    https://golang.org/cl/13078044

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

https://github.com/golang/go/commit/fb376021bea084d5320a8059176ab86880832f5c

元コミット内容

Goランタイムにおいて、ハッシュテーブルの内部構造に関する型情報を記録するように変更し、ハッシュテーブルに特化したGCコードをすべて削除します。これにより、バグ6119が修正されます。

変更の背景

Goのガベージコレクタは、ヒープ上のオブジェクトを正確に識別し、到達可能なオブジェクトを保持し、到達不能なオブジェクトを解放する役割を担っています。以前のGoランタイムでは、マップ（ハッシュテーブル）の内部構造（バケットやHmapヘッダなど）をGCが処理するために、マップに特化したGCロジックがsrc/pkg/runtime/mgc0.c内に存在していました。

このアプローチにはいくつかの問題がありました。

1. GCロジックの重複と複雑性: マップの内部構造が変更されるたびに、GCコードも手動で更新する必要があり、GCロジックが複雑化し、バグの温床となる可能性がありました。
2. 汎用性の欠如: マップに特化したGCコードは、他のデータ構造のGCには適用できず、GCシステムの汎用性を損なっていました。
3. 正確性の問題: マップの内部構造がGCによって正しくスキャンされない場合、メモリリークや不正なメモリ解放が発生する可能性がありました。

このコミットは、これらの問題を解決するために、マップの内部構造を通常のGoの型システムに統合し、GCがその型情報に基づいて自動的にマップをスキャンできるようにすることを目指しています。これにより、マップに特化したGCコードが不要になり、GCシステムの堅牢性と保守性が向上します。

前提知識の解説

このコミットを理解するためには、以下のGoランタイムとGCに関する基本的な知識が必要です。

• Goのマップ（ハッシュテーブル）の内部構造: Goのマップは、キーと値のペアを格納するためのデータ構造です。内部的には、Hmapというヘッダ構造と、Bucketと呼ばれるバケットの配列で構成されています。各バケットは複数のキーと値を保持でき、オーバーフローした場合には追加のバケット（オーバーフローバケット）にリンクされます。
• Goのガベージコレクション（GC）: Goはトレース型GCを採用しており、ヒープ上のオブジェクトをスキャンして到達可能性を判断します。GCは、オブジェクトの型情報（_type構造体）を利用して、そのオブジェクトがポインタを含むかどうか、含まれる場合はどのオフセットにポインタがあるかを判断します。
• GCプログラム（GC Prog）: GoのGCは、オブジェクトのレイアウトを記述する「GCプログラム」と呼ばれるバイトコードのようなものを使用します。このプログラムは、GCがオブジェクトをスキャンする際に、どの部分がポインタであり、どの部分がポインタでないかを指示します。
• reflectパッケージ: Goのreflectパッケージは、実行時にGoの型情報を検査・操作するための機能を提供します。ランタイム内部でも、型の情報を扱うために利用されます。
• src/cmd/gc: Goコンパイラのバックエンドの一部で、型情報の生成やGCプログラムの生成など、ランタイムと密接に関連する処理を行います。
• src/pkg/runtime: Goランタイムのソースコードが含まれるディレクトリで、GC、スケジューラ、メモリ管理など、Goプログラムの実行に必要な低レベルな機能が実装されています。
• runtime·mallocgc: Goランタイムのメモリ割り当て関数で、GCヒープからメモリを割り当てます。この関数は、割り当てられたメモリの型情報を受け取り、GCがそのメモリをスキャンできるようにします。

技術的詳細

このコミットの主要な変更点は、マップの内部構造であるHmapとBucketを、Goの型システムに組み込むことです。これにより、GCはこれらの構造を通常のGoオブジェクトと同様に扱い、型情報に基づいてポインタをスキャンできるようになります。

具体的には、以下の変更が行われています。

1. src/cmd/gc/go.hとsrc/cmd/gc/reflect.cにおける型情報の追加:

   • Type構造体にbucketとhmapフィールドが追加され、マップのバケット型とHmap型へのポインタを保持できるようになりました。
   • mapbucket関数とhmap関数が追加されました。これらの関数は、与えられたマップ型に基づいて、その内部構造であるBucketとHmapに対応するType構造体を動的に生成します。これらの生成された型は、GCがマップの内部構造を正確にスキャンするために必要な情報（サイズ、ポインタのオフセットなど）を含んでいます。
   • dtypesym関数が変更され、マップ型を処理する際に、新しく生成されたBucket型とHmap型のシンボルもGCに登録されるようになりました。

2. src/pkg/reflect/type.goにおける型情報の拡張:

   • mapType構造体にbucketとhmapフィールドが追加され、ランタイムレベルでマップの内部構造の型情報を保持できるようになりました。
   • MapOf関数（マップ型を生成する関数）が変更され、bucketOfとhMapOf関数を呼び出して、マップのキーと値の型に基づいてBucket型とHmap型を生成し、mapTypeに設定するようになりました。
   • bucketOf関数とhMapOf関数は、reflectパッケージ内でBucketとHmapのGCプログラムを動的に構築します。これにより、GCはこれらの内部構造を適切にスキャンできます。特に、_GC_PTRなどのGC命令を使用して、ポインタフィールドのオフセットをGCプログラムにエンコードしています。
   • chanMapGCがchanGCにリネームされ、マップに特化したGCプログラムが削除されました。

3. src/pkg/runtime/hashmap.cにおけるGCコードの削除とruntime·mallocgcの変更:

   • hashmap.cから、マップのバケットやキー、値のGCに関する明示的なコード（clearbucketマクロの削除、CanFreeBucket、CanFreeKeyフラグの削除、hash_gciter関連の関数の削除など）が大幅に削除されました。
   • runtime·mallocgcの呼び出しにおいて、マップのバケットやHmapを割り当てる際に、以前は汎用的なTypeInfo_ArrayやTypeInfo_Mapを使用していた箇所が、新しく生成されたt->bucketやt->hmapといった具体的な型情報（uintptr)t->bucket | TypeInfo_Arrayのように）を渡すように変更されました。これにより、GCは割り当てられたメモリがマップのどの内部構造であるかを正確に認識し、その型情報に基づいてスキャンできるようになります。

4. src/pkg/runtime/mgc0.cとsrc/pkg/runtime/mgc0.hにおけるGCロジックの簡素化:

   • mgc0.cから、マップに特化したGCスキャンロジック（TypeInfo_Mapケースの削除、GC_MAP_NEXT命令の削除など）が削除されました。
   • mgc0.hからGC_MAP_PTR命令が削除されました。

これらの変更により、GoのGCは、マップの内部構造を明示的に知る必要がなくなり、汎用的な型情報に基づいてポインタをスキャンするメカニズムに完全に依存するようになりました。これは、GCシステムの設計における重要な改善であり、将来的なデータ構造の追加や変更に対するGCの適応性を高めます。

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

このコミットのコアとなる変更は、主に以下のファイルに集中しています。

• src/cmd/gc/reflect.c:
  • mapbucket関数とhmap関数の追加。これらは、マップのバケットとHmapヘッダの型情報を動的に生成します。
  • dtypesym関数におけるマップ型処理の変更。新しく生成されたBucket型とHmap型のシンボルをGCに登録します。
• src/pkg/reflect/type.go:
  • mapType構造体へのbucketとhmapフィールドの追加。
  • MapOf関数におけるbucketOfとhMapOf関数の呼び出しによる内部構造の型情報の設定。
  • bucketOf関数とhMapOf関数の追加。これらは、BucketとHmapのGCプログラムを動的に構築します。
• src/pkg/runtime/hashmap.c:
  • マップに特化したGC関連のフラグ（CanFreeBucket, CanFreeKey）やマクロ（clearbucket）の削除。
  • runtime·mallocgcの呼び出しにおいて、マップの内部構造を割り当てる際に、具体的な型情報（t->bucketやt->hmap）を渡すように変更。
  • hash_gciter関連の構造体と関数の削除。
• src/pkg/runtime/mgc0.c:
  • マップに特化したGCスキャンロジックの削除。

コアとなるコードの解説

src/cmd/gc/reflect.c

// Builds a type respresenting a Bucket structure for
// the given map type.  This type is not visible to users -
// we include only enough information to generate a correct GC
// program for it.
// Make sure this stays in sync with ../../pkg/runtime/hashmap.c!
static Type*
mapbucket(Type *t)
{
    // ... (Bucket構造体のフィールドに対応するType構造体を構築)
    // overflowfield->type = ptrto(bucket); // overflowフィールドはBucketへのポインタ
    // keysfield->type->type = keytype;     // keysフィールドはキーの配列
    // valuesfield->type->type = valtype;   // valuesフィールドは値の配列
    // ...
}

// Builds a type respresenting a Hmap structure for
// the given map type.  This type is not visible to users -
// we include only enough information to generate a correct GC
// program for it.
// Make sure this stays in sync with ../../pkg/runtime/hashmap.c!
static Type*
hmap(Type *t)
{
    // ... (Hmap構造体のフィールドに対応するType構造体を構築)
    // bucketsfield->type = ptrto(bucket); // bucketsフィールドはBucketへのポインタ
    // oldbucketsfield->type = ptrto(bucket); // oldbucketsフィールドもBucketへのポインタ
    // ...
}

mapbucketとhmap関数は、コンパイラがマップの内部構造（BucketとHmap）の型情報を生成するために使用されます。これらの型情報は、GCがマップのメモリレイアウトを理解し、ポインタを正確にスキャンするために不可欠です。特に、ptrto(bucket)のように、ポインタフィールドの型を明示的に指定することで、GCが参照を追跡できるようにしています。

src/pkg/reflect/type.go

type mapType struct {
	rtype  `reflect:"map"`
	key    *rtype // map key type
	elem   *rtype // map element (value) type
	bucket *rtype // internal bucket structure
	hmap   *rtype // internal map header
}

func MapOf(key, elem Type) Type {
    // ...
    mt.bucket = bucketOf(ktyp, etyp)
    mt.hmap = hMapOf(mt.bucket)
    // ...
}

func bucketOf(ktyp, etyp *rtype) *rtype {
    // ...
    // GCプログラムを動的に構築
    // gc = append(gc, _GC_PTR, offset, 0 /*self pointer set below*/) // overflow
    // gc = append(gc, _GC_ARRAY_START, offset, BUCKETSIZE, ktyp.size) // keys
    // gc = appendGCProgram(gc, ktyp)
    // gc = append(gc, _GC_ARRAY_NEXT)
    // ...
}

func hMapOf(bucket *rtype) *rtype {
    // ...
    // GCプログラムを動的に構築
    // gc = append(gc, _GC_PTR, offset, uintptr(bucket.gc)) // buckets
    // gc = append(gc, _GC_PTR, offset, uintptr(bucket.gc)) // oldbuckets
    // ...
}

mapType構造体にbucketとhmapフィールドが追加されたことで、Goのreflectパッケージを通じてマップの内部構造の型情報にアクセスできるようになりました。MapOf関数は、マップ型を生成する際に、bucketOfとhMapOfを呼び出して、これらの内部構造の型情報を設定します。

bucketOfとhMapOf関数は、GoのGCプログラムを動的に生成する重要な役割を担っています。これらの関数は、_GC_PTR（ポインタ）、_GC_ARRAY_START（配列の開始）、_GC_ARRAY_NEXT（配列の次の要素）などのGC命令を使用して、BucketとHmap構造体内のポインタフィールドのオフセットと型情報をGCプログラムにエンコードします。これにより、GCはこれらの構造体をスキャンする際に、どこにポインタがあるかを正確に判断できます。

src/pkg/runtime/hashmap.c

struct Bucket
{
	// Note: the format of the Bucket is encoded in ../../cmd/gc/reflect.c and
	// ../reflect/type.go.  Don't change this structure without also changing that code!
	uint8  tophash[BUCKETSIZE]; // top 8 bits of hash of each entry (0 = empty)
	Bucket *overflow;           // overflow bucket, if any
	byte   data[1];             // BUCKETSIZE keys followed by BUCKETSIZE values
};

// ...

struct Hmap
{
	// Note: the format of the Hmap is encoded in ../../cmd/gc/reflect.c and
	// ../reflect/type.go.  Don't change this structure without also changing that code!
	uintgo  count;        // # live cells == size of map.  Must be first (used by len() builtin)
	uint32  flags;
	uint32  hash0;        // hash seed
	uint8   B;            // log_2 of # of buckets (can hold up to LOAD * 2^B items)
	uint8   keysize;      // key size in bytes
	uint8   valuesize;    // value size in bytes
	uint16  bucketsize;   // bucket size in bytes
	Bucket *buckets;      // array of buckets; may be nil if count==0.
	Bucket *oldbuckets;   // array of old buckets, nil if no ongoing grow
	uintptr nevacuate;    // progress counter for evacuation (buckets less than this have been evacuated)
};

// ...

// runtime·mallocgcの呼び出し例
// buckets = runtime·mallocgc(bucketsize << B, (uintptr)t->bucket | TypeInfo_Array, 0);
// newx = runtime·mallocgc(h->bucketsize, (uintptr)t->bucket, 0);
// h = runtime·mallocgc(sizeof(*h), (uintptr)typ->hmap, 0);

hashmap.cでは、BucketとHmap構造体の定義に、これらの構造体のレイアウトがreflect.cとtype.goでエンコードされていることを示すコメントが追加されています。これは、これらの構造体を変更する際には、GCが正しく動作するように型情報も更新する必要があることを開発者に警告するものです。

最も重要な変更は、runtime·mallocgcの呼び出し方です。以前は、マップの内部構造を割り当てる際に、GCに対して汎用的な情報（例: TypeInfo_Array）しか渡していませんでした。しかし、このコミット以降は、t->bucketやtyp->hmapといった、reflect.cとtype.goで動的に生成された具体的な型情報を渡すようになりました。これにより、GCは割り当てられたメモリがマップのどの部分であるかを正確に認識し、その型情報に基づいてポインタをスキャンできるようになります。これにより、hashmap.cからマップに特化したGCロジックを削除することが可能になりました。

関連リンク

• Go言語のガベージコレクションに関する公式ドキュメントやブログ記事
• Goのreflectパッケージのドキュメント
• Goのマップの実装に関する技術記事や解説

参考にした情報源リンク

• Goのソースコード（特にsrc/cmd/gc、src/pkg/reflect、src/pkg/runtimeディレクトリ）
• GoのIssue Tracker (bug 6119に関する情報があれば)
• GoのCode Reviewシステム (golang.org/cl/13078044に関する情報があれば)
• Goのガベージコレクションに関する技術ブログや論文
• Goのマップ実装に関する技術ブログや論文