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

このコミットは、Go言語のコンパイラとランタイムにおける重要な改善を導入し、ガベージコレクション（GC）の効率性を向上させるものです。具体的には、関数のスタックフレーム内の引数領域におけるポインタの位置を示すビットマップを生成し、それを利用するように変更されています。これにより、ガベージコレクタはスタックをスキャンする際に、ポインタを含まない場所を正確に無視できるようになり、GCの精度とパフォーマンスが向上します。

コミット

commit 4e0a51c210ededa82809756ca1cc72b1fb1def8d
Author: Carl Shapiro <cshapiro@google.com>
Date:   Tue May 28 17:59:10 2013 -0700

    cmd/5l, cmd/6l, cmd/8l, cmd/gc, runtime: generate and use bitmaps of argument pointer locations
    
    With this change the compiler emits a bitmap for each function
    covering its stack frame arguments area.  If an argument word
    is known to contain a pointer, a bit is set.  The garbage
    collector reads this information when scanning the stack by
    frames and uses it to ignores locations known to not contain a
    pointer.
    
    R=golang-dev, bradfitz, daniel.morsing, dvyukov, khr, khr, iant, cshapiro
    CC=golang-dev
    https://golang.org/cl/9223046

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

https://github.com/golang/go/commit/4e0a51c210ededa82809756ca1cc72b1fb1def8d

元コミット内容

cmd/5l, cmd/6l, cmd/8l, cmd/gc, runtime: generate and use bitmaps of argument pointer locations

With this change the compiler emits a bitmap for each function
covering its stack frame arguments area.  If an argument word
is known to contain a pointer, a bit is set.  The garbage
collector reads this information when scanning the stack by
frames and uses it to ignores locations known to not contain a
pointer.

変更の背景

Go言語のガベージコレクタは、プログラムが使用しているメモリを自動的に管理し、不要になったメモリを解放する役割を担っています。GCの重要なフェーズの一つに「スタックスキャン」があります。これは、現在実行中の関数のスタックフレームを検査し、そこに含まれるポインタ（ヒープ上のオブジェクトを指す参照）を特定するプロセスです。これらのポインタをたどることで、GCは「到達可能」なオブジェクト（まだ使用されているオブジェクト）を識別し、到達不可能なオブジェクト（不要になったオブジェクト）を解放の対象とします。

このコミット以前のGoのGCでは、スタックフレーム内の引数領域をスキャンする際に、どのワードがポインタであるかを正確に識別する情報が不足している場合がありました。そのため、GCは保守的に引数領域全体をスキャンする必要があり、これは不必要なメモリの走査を引き起こし、GCのパフォーマンスに影響を与える可能性がありました。特に、引数領域に多くの非ポインタ値が含まれている場合、この非効率性は顕著になります。

この変更の背景には、GCの精度を向上させ、スキャン時間を短縮することで、Goプログラム全体の実行効率を高めるという目的があります。コンパイラがポインタの正確な位置を示すビットマップを生成することで、ランタイムのガベージコレクタはより効率的にスタックをスキャンし、不要な作業を削減できるようになります。

前提知識の解説

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

ガベージコレクションは、プログラマが手動でメモリを解放する手間を省き、メモリリークを防ぐための自動メモリ管理手法です。Go言語のGCは、並行（concurrent）かつ三色マーク・アンド・スイープ（tri-color mark-and-sweep）アルゴリズムをベースにしています。

• マークフェーズ: GCは、ルート（グローバル変数、スタック上の変数など）から到達可能なすべてのオブジェクトを「マーク」します。
• スイープフェーズ: マークされなかったオブジェクト（到達不可能なオブジェクト）は、不要なメモリとして解放されます。

スタックとスタックフレーム

プログラムが関数を呼び出すと、その関数の実行に必要な情報（ローカル変数、引数、戻りアドレスなど）を格納するために、メモリの「スタック」領域に「スタックフレーム」が割り当てられます。関数が終了すると、そのスタックフレームは解放されます。

ポインタ

ポインタは、メモリ上の特定のアドレスを指し示す変数です。GCは、ポインタをたどることで、メモリ上のオブジェクト間の参照関係を把握し、どのオブジェクトがまだ使用されているかを判断します。

ビットマップ（ビットベクトル）

ビットマップは、データの各要素の状態を1ビットで表現するデータ構造です。例えば、ある要素が存在するかどうかを0または1で示す場合などに使用されます。これにより、メモリを非常に効率的に使用できます。このコミットでは、スタックフレームの引数領域内の各ワードがポインタであるかどうかを1ビットで示すために使用されます。

Goコンパイラとリンカの役割

• Goコンパイラ (cmd/gc, cmd/5g, cmd/6g, cmd/8gなど): Goのソースコードを機械語に変換し、オブジェクトファイルを生成します。このコミットでは、コンパイラが関数の引数領域のポインタマップ情報を生成する役割を担います。
• Goリンカ (cmd/5l, cmd/6l, cmd/8lなど): コンパイラが生成した複数のオブジェクトファイルやライブラリを結合し、実行可能なバイナリを生成します。このコミットでは、リンカがコンパイラから渡されたポインタマップ情報をバイナリに埋め込み、ランタイムが利用できるようにする役割を担います。

技術的詳細

このコミットの核心は、Goのコンパイラとランタイムが連携して、関数のスタックフレーム内の引数領域におけるポインタの正確な位置をガベージコレクタに伝える新しいメカニズムを導入した点にあります。

1. コンパイラによるポインタマップの生成 (src/cmd/gc/pgen.c):

   • Goコンパイラは、各関数のコンパイル時に、その関数の引数領域を分析します。
   • pointermapという新しい関数が導入され、引数領域内のどのワードがポインタを含むかを識別します。
   • この情報はビットマップ（Bvec）として表現されます。例えば、引数領域のN番目のワードがポインタであれば、ビットマップのN番目のビットがセットされます。
   • コンパイラは、このビットマップ情報を新しい擬似命令 (ANPTRS と APTRS) として生成し、オブジェクトファイルに出力します。
     • ANPTRS (Argument Number of Pointers): ポインタマップのビット数（引数領域のワード数）を定義します。
     • APTRS (Argument Pointers): 実際のビットマップデータ（32ビットごとのワード）を定義します。

2. リンカによるポインタマップの処理と埋め込み (src/cmd/5l/obj.c, src/cmd/6l/obj.c, src/cmd/8l/obj.c, src/cmd/ld/lib.c):

   • リンカは、コンパイラが生成したオブジェクトファイルから ANPTRS と APTRS 命令を読み取ります。
   • これらの命令から、各関数のポインタマップデータを抽出し、実行可能バイナリのシンボルテーブルに格納します。
   • Sym構造体（シンボル情報を表す）に nptrs (ポインタマップのビット数) と ptrs (ポインタマップデータへのポインタ) という新しいフィールドが追加され、この情報が保持されます。

3. ランタイムによるポインタマップの利用 (src/pkg/runtime/mgc0.c, src/pkg/runtime/extern.go, src/pkg/runtime/runtime.h, src/pkg/runtime/symtab.c):

   • Goランタイムは、実行可能バイナリのシンボルテーブルから関数のポインタマップ情報を読み込みます。
   • runtime.Func構造体（Goの関数情報を表す）に ptrs という新しいフィールドが追加され、このポインタマップが格納されます。
   • ガベージコレクタのスタックスキャンロジック (addframeroots 関数) が変更されます。
   • 変更後、addframeroots は Func.ptrs を参照し、引数領域のどの位置にポインタが存在するかを正確に判断します。
   • これにより、GCはポインタを含まないワードをスキャン対象から除外できるようになり、スキャン効率が大幅に向上します。

bv.c の役割

src/cmd/gc/bv.c は、ビットベクトル（ビットマップ）を操作するためのユーティリティ関数を提供します。これには、ビットベクトルのアロケーション (bvalloc)、ビットの設定 (bvset)、ビットのクリア (bvres)、ビットの取得 (bvget)、ビットベクトルの比較 (bvcmp)、およびビットベクトルが空であるかどうかのチェック (bvisempty) などが含まれます。これらの関数は、コンパイラがポインタマップを効率的に構築するために使用されます。

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

このコミットは広範囲にわたる変更を含みますが、特に重要な変更箇所は以下の通りです。

1. src/cmd/gc/bv.c の新規追加:

   • ビットベクトル（ビットマップ）を扱うためのユーティリティ関数群が実装されています。

2. src/cmd/gc/go.h の変更:

   • Bvec 構造体の定義と、bv.c で定義されたビットベクトル操作関数のプロトタイプが追加されています。

3. src/cmd/gc/pgen.c の変更:

   • compile 関数内で pointermap(fn); が呼び出されるようになり、各関数のポインタマップ生成が統合されました。
   • walktype1 および walktype 関数が追加され、型情報に基づいてポインタの位置を特定し、ビットマップに記録するロジックが実装されています。
   • pointermap 関数が追加され、Bvec を使用してポインタマップを構築し、ANPTRS および APTRS 擬似命令として出力するロジックが実装されています。

4. src/cmd/5l/obj.c, src/cmd/6l/obj.c, src/cmd/8l/obj.c の変更:

   • リンカのオブジェクトファイル読み込みロジックに、新しい擬似命令 ANPTRS と APTRS のハンドリングが追加されています。
   • Sym 構造体に nptrs と ptrs フィールドが追加され、ポインタマップ情報が格納されるようになっています。

5. src/cmd/ld/lib.c の変更:

   • リンカがシンボル情報を生成する際に、.nptrs と .ptrs という新しいメタデータシンボルを出力するロジックが追加されています。

6. src/pkg/runtime/extern.go および src/pkg/runtime/runtime.h の変更:

   • Func 構造体に ptrs Slice フィールドが追加され、ランタイムがポインタマップにアクセスできるようになりました。

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

   • addframeroots 関数が大幅に修正され、f->ptrs (ポインタマップ) を利用して、スタックフレームの引数領域をより精密にスキャンするようになりました。これにより、ポインタを含むワードのみがGCの対象となります。

8. src/pkg/runtime/symtab.c の変更:

   • シンボルテーブルの処理ロジックに、.nptrs と .ptrs シンボルを読み込み、runtime.Func 構造体の ptrs フィールドを適切に初期化するコードが追加されています。

コアとなるコードの解説

src/cmd/gc/pgen.c の pointermap 関数 (抜粋)

static void
pointermap(Node *fn)
{
	Type *thistype, *inargtype, *outargtype;
	Bvec *bv;
	Prog *prog;
	int32 i;

	thistype = getthisx(fn->type);
	inargtype = getinargx(fn->type);
	outargtype = getoutargx(fn->type);
	bv = bvalloc(fn->type->argwid / widthptr); // 引数領域のワード数分のビットマップを確保
	if(thistype != nil)
		walktype(thistype, bv); // レシーバの型をウォークしてポインタを記録
	if(inargtype != nil)
		walktype(inargtype, bv); // 入力引数の型をウォークしてポインタを記録
	if(outargtype != nil)
		walktype(outargtype, bv); // 出力引数（戻り値）の型をウォークしてポインタを記録
	if(bvisempty(bv)) {
		// ポインタがない場合は、ビット数0のANPTRS命令を生成
		prog = gins(ANPTRS, N, N);
		prog->to.type = D_CONST;
		prog->to.offset = 0;
	} else {
		// ポインタがある場合は、ビット数とビットマップデータを生成
		prog = gins(ANPTRS, N, N);
		prog->to.type = D_CONST;
		prog->to.offset = bv->n; // ビットマップのビット数
		for(i = 0; i < bv->n; i += 32) {
			prog = gins(APTRS, N, N);
			prog->from.type = D_CONST;
			prog->from.offset = i / 32; // ビットマップのワードインデックス
			prog->to.type = D_CONST;
			prog->to.offset = bv->b[i / 32]; // ビットマップのデータワード
		}
	}
	free(bv);
}

この関数は、関数のレシーバ、入力引数、出力引数（戻り値）の型情報を走査し、ポインタを含むフィールドを特定します。walktype 関数が実際の型走査を行い、bv (ビットベクトル) にポインタの位置をビットとして記録します。最終的に、このビットマップ情報が ANPTRS と APTRS という擬似命令としてコンパイラの出力ストリームに書き込まれます。

src/pkg/runtime/mgc0.c の addframeroots 関数 (抜粋)

static void
addframeroots(Func *f, byte*, byte *sp, void *doframe)
{
	byte *fp, *ap;
	uintptr outs;
	int32 i, j, rem;
	uint32 w, b;

	// ... (スタックポインタの調整など)

	if(f->args > 0) {
		// 引数領域をスキャン
		if(f->ptrs.array != nil) { // ポインタマップが存在する場合
			ap = fp; // 引数領域の開始アドレス
			rem = f->args / sizeof(uintptr); // 引数領域のワード数
			for(i = 0; i < f->ptrs.len; i++) { // ポインタマップの各ワードを走査
				w = ((uint32*)f->ptrs.array)[i]; // ビットマップのワード
				b = 1;
				for((j = (rem < 32) ? rem : 32); j > 0; j--) { // 各ビットをチェック
					if(w & b) // ビットがセットされていればポインタ
						addroot((Obj){ap, sizeof(uintptr), 0}); // そのワードをルートとして追加
					b <<= 1;
					ap += sizeof(uintptr); // 次のワードへ
				}
				rem -= 32;
			}
		} else // ポインタマップが存在しない場合（旧来の動作）
			addroot((Obj){fp, f->args, 0}); // 引数領域全体をルートとして追加
	}
	*(bool*)doframe = (f->args == ArgsSizeUnknown);
}

この関数は、ガベージコレクタがスタックフレームをスキャンする際の主要なロジックを含んでいます。変更後、f->ptrs.array (コンパイラとリンカによって提供されたポインタマップ) が存在するかどうかを確認します。存在する場合、ビットマップをビットごとに走査し、ビットがセットされている（ポインタが存在する）ワードのみをGCのルートとして追加します。これにより、GCはポインタではないデータを含むメモリ領域を不必要にスキャンするのを避けることができます。

関連リンク

• Go言語のガベージコレクションに関する公式ドキュメントやブログ記事:
  • Go's Garbage Collector: A Brief History (Go 1.5 GCの紹介ですが、GCの基本的な考え方を理解するのに役立ちます)
  • The Go Programming Language Specification - Calls (関数の呼び出しと引数に関する仕様)

参考にした情報源リンク

• Go言語のソースコード (特に src/cmd/gc, src/cmd/ld, src/pkg/runtime ディレクトリ)
• Go言語のコンパイラとランタイムの内部構造に関する一般的な知識
• ガベージコレクションのアルゴリズムに関する一般的な情報