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

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

このコミットは、Goコンパイラのレジスタ最適化における重要なバグ修正に関するものです。具体的には、関数の入力変数（引数）のライブネス（生存期間）に関するガベージコレクタの認識と、レジスタ最適化器の挙動との間の不整合を解消します。この不整合は、特にスライスのような複数ワードのデータ型において、メモリ破損を引き起こす可能性がありました。

変更されたファイルは以下の通りです。

  • src/cmd/5g/opt.h
  • src/cmd/5g/reg.c
  • src/cmd/6g/opt.h
  • src/cmd/6g/reg.c
  • src/cmd/8g/opt.h
  • src/cmd/8g/reg.c
  • test/fixedbugs/issue7944.go

これらのファイルは、Goコンパイラの各アーキテクチャ（5g: ARM, 6g: AMD64, 8g: 386）における最適化とレジスタ割り当てに関連する部分です。また、バグを再現し修正を検証するための新しいテストケースが追加されています。

コミット

commit 26ad5d4ff021e7784dca22e76c43494e76913911
Author: Russ Cox <rsc@golang.org>
Date:   Mon May 12 17:19:02 2014 -0400

    cmd/gc: fix liveness vs regopt mismatch for input variables
    
    The inputs to a function are marked live at all times in the
    liveness bitmaps, so that the garbage collector will not free
    the things they point at and reuse the pointers, so that the
    pointers shown in stack traces are guaranteed not to have
    been recycled.
    
    Unfortunately, no one told the register optimizer that the
    inputs need to be preserved at all call sites. If a function
    is done with a particular input value, the optimizer will stop
    preserving it across calls. For single-word values this just
    means that the value recorded might be stale. For multi-word
    values like slices, the value recorded could be only partially stale:
    it can happen that, say, the cap was updated but not the len,
    or that the len was updated but not the base pointer.
    Either of these possibilities (and others) would make the
    garbage collector misinterpret memory, leading to memory
    corruption.
    
    This came up in a real program, in which the garbage collector's
    'slice len ≤ slice cap' check caught the inconsistency.
    
    Fixes #7944.
    
    LGTM=iant
    R=golang-codereviews, iant
    CC=golang-codereviews, khr
    https://golang.org/cl/100370045

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

https://github.com/golang/go/commit/26ad5d4ff021e7784dca22e76c43494e76913911

元コミット内容

cmd/gc: 入力変数におけるライブネスとレジスタ最適化の不整合を修正

関数の入力は、ガベージコレクタがそれらが指すものを解放したりポインタを再利用したりしないように、ライブネスビットマップ内で常にライブとしてマークされています。これにより、スタックトレースに表示されるポインタが再利用されていないことが保証されます。

残念ながら、レジスタ最適化器には、すべての呼び出しサイトで入力変数を保持する必要があることが伝えられていませんでした。関数が特定の入力値の処理を終えると、最適化器は呼び出しをまたいでその値を保持するのをやめてしまいます。単一ワードの値の場合、これは記録された値が古くなることを意味するだけです。スライスのような複数ワードの値の場合、記録された値は部分的にしか古くならない可能性があります。例えば、capは更新されたがlenは更新されなかったり、lenは更新されたがベースポインタは更新されなかったりする可能性があります。これらの可能性（およびその他）のいずれも、ガベージコレクタがメモリを誤って解釈し、メモリ破損につながる可能性があります。

これは実際のプログラムで発生し、ガベージコレクタの「slice len ≤ slice cap」チェックがこの不整合を検出しました。

Fixes #7944.

変更の背景

このコミットは、Goプログラムの実行時における潜在的なメモリ破損バグを修正するために行われました。問題の根源は、Goのガベージコレクタ（GC）が変数の「ライブネス」（プログラムの将来の実行でその変数がまだ使用される可能性があるかどうか）を追跡する方法と、コンパイラのレジスタ最適化器が変数を扱う方法との間の不整合にありました。

具体的には、Goランタイムは、関数の引数（入力変数）がスタックトレースの正確性を保証するために、常に「ライブ」であると見なします。これは、ガベージコレクタがこれらの引数が指すメモリを誤って解放したり、ポインタを再利用したりするのを防ぐためです。しかし、コンパイラのレジスタ最適化器は、このGCの要件を完全に認識していませんでした。

その結果、最適化器は、関数内で特定の入力変数がもう必要ないと判断すると、その変数をレジスタから解放したり、その値を呼び出しをまたいで保持するのをやめたりすることがありました。単一ワードの変数であれば、これはスタックトレースに古い値が表示される程度の問題で済みます。しかし、スライスのような複数ワード（ポインタ、長さ、容量）で構成される複合型の場合、問題はより深刻になります。例えば、スライスの容量（cap）は更新されたが長さ（len）は更新されなかったり、あるいはベースポインタが更新されなかったりといった「部分的な古さ」が発生する可能性がありました。このような状態は、ガベージコレクタがメモリの状態を誤って解釈し、結果としてメモリ破損（memory corruption）を引き起こす可能性がありました。

このバグは、実際のGoプログラムで発生し、Goのガベージコレクタに組み込まれている「スライスの長さは容量以下でなければならない（slice len <= slice cap）」という整合性チェックによって検出されました。このチェックが不整合を捉えたことで、問題が顕在化し、今回の修正につながりました。

前提知識の解説

このコミットの理解には、以下のGo言語およびコンパイラの概念に関する知識が役立ちます。

  1. Goコンパイラ (cmd/gc): Go言語の公式コンパイラは、ソースコードを機械語に変換する役割を担います。cmd/gcは、Goのツールチェーンの一部であり、Goプログラムのビルドプロセスの中核をなします。コンパイラは、コードの最適化（例: レジスタ割り当て、デッドコード削除）も行い、生成されるバイナリのパフォーマンスを向上させます。

  2. レジスタ最適化 (Register Optimization): CPUには、高速なデータアクセスが可能な「レジスタ」と呼ばれる少数の記憶領域があります。レジスタ最適化は、コンパイラがプログラムの実行中に頻繁にアクセスされる変数を、メモリではなくこれらのレジスタに割り当てることで、プログラムの実行速度を向上させる技術です。変数がレジスタに割り当てられている間は、その変数のメモリ上のコピーは最新の状態ではない可能性があります。

  3. ライブネス (Liveness): プログラム解析における「ライブネス」とは、ある変数がプログラムの特定の時点以降でまだ使用される可能性があるかどうかを示す概念です。変数が「ライブ」であるとは、その変数の現在の値が将来の計算で必要とされる可能性があることを意味します。ガベージコレクタは、ライブでないメモリ領域を解放することができます。

  4. ライブネスビットマップ (Liveness Bitmaps): Goのガベージコレクタは、スタックフレーム上のどのスロットにポインタが含まれているか、そしてそれらのポインタが「ライブ」であるか（つまり、まだ参照されているか）を追跡するためにライブネスビットマップを使用します。これにより、GCは不要になったメモリを安全に解放し、同時にスタックトレースなどのデバッグ情報が正確であることを保証します。特に、パニック発生時などにスタックトレースに表示される変数の値が、GCによって再利用された古いメモリを指さないようにするために重要です。

  5. ガベージコレクタ (Garbage Collector, GC): Goは自動メモリ管理（ガベージコレクション）を採用しています。GCは、プログラムが動的に割り当てたメモリのうち、もはやどの部分からも参照されていない（デッドな）メモリ領域を自動的に識別し、解放するシステムです。これにより、プログラマは手動でのメモリ管理の複雑さから解放されます。GCは、ライブネスビットマップなどの情報に基づいて動作します。

  6. スライス (Slice): Goのスライスは、Go言語における非常に強力で柔軟なデータ構造です。スライスは、内部的には基盤となる配列への「ビュー」または「参照」として機能します。スライスは、以下の3つの要素で構成されます。

    • ポインタ (Pointer): スライスが参照する基盤配列の先頭要素へのポインタ。
    • 長さ (Length, len): スライスに含まれる要素の数。
    • 容量 (Capacity, cap): スライスの基盤配列の先頭から、その配列が保持できる最大要素数。 スライスは複数ワードで構成されるため、その一部が古くなると、GCがメモリを誤って解釈するリスクが高まります。特に len <= cap という不変条件は、スライスの整合性を保つ上で非常に重要です。

  7. メモリ破損 (Memory Corruption): メモリ破損は、プログラムが意図しないメモリ領域に書き込んだり、メモリの内容を誤って解釈したりするプログラミングエラーの一種です。これは、プログラムのクラッシュ、予期せぬ動作、セキュリティ脆弱性など、深刻な問題を引き起こす可能性があります。ガベージコレクタが誤ったライブネス情報に基づいて動作すると、まだ使用中のメモリを解放してしまい、その後に別のデータが書き込まれることでメモリ破損が発生する可能性があります。

技術的詳細

このコミットが修正する問題は、Goコンパイラのレジスタ最適化フェーズと、Goランタイムのガベージコレクタが使用するライブネス情報との間の同期の欠如に起因していました。

Goの設計では、関数の入力変数（引数）は、その関数が実行されている間、常に「ライブ」であると見なされます。この設計は、主に以下の2つの理由に基づいています。

  1. スタックトレースの正確性: プログラムがパニックを起こしたり、デバッグのためにスタックトレースが生成されたりする際、関数の引数の値が正確に表示される必要があります。もし引数がGCによって再利用されたり、最適化によって値が失われたりすると、スタックトレースの情報が誤解を招くものになってしまいます。
  2. GCの安全性: ガベージコレクタは、ライブなポインタが指すメモリを解放しないように動作します。関数の引数にポインタが含まれる場合、それらが常にライブであるとマークされていれば、GCが誤ってそのポインタが指すメモリを解放してしまうことを防げます。

しかし、Goコンパイラのレジスタ最適化器は、この「入力変数は常にライブである」というGCの要件を完全に考慮していませんでした。最適化器は、関数内の特定のポイントで入力変数がもう使用されないと判断すると、その変数をレジスタから解放したり、その値をメモリに書き戻さずに、呼び出しをまたいでその値を保持するのをやめたりすることがありました。

この挙動が問題となるのは、特にスライスのような複数ワードで構成されるデータ型の場合です。スライスは、内部的にポインタ、長さ（len）、容量（cap）の3つのワードで表現されます。もしレジスタ最適化器がスライスのいずれかの部分（例えば、長さや容量）を「デッド」と判断し、その値を更新しなかったり、古い値を保持したりした場合、以下のようなシナリオが発生する可能性がありました。

  • 部分的な古さ: スライスの cap は更新されたが len は更新されなかった、あるいは len は更新されたが基盤配列へのポインタは更新されなかった、といった状況です。
  • GCの誤解釈: ガベージコレクタは、ライブネスビットマップに基づいてメモリをスキャンし、ポインタを識別します。もしスライスの内部表現が不整合な状態（例: len が cap より大きいなど）になると、GCはメモリを誤って解釈し、まだ使用中のメモリを解放してしまったり、無効なポインタを追跡しようとしたりする可能性があります。
  • メモリ破損: 最終的に、GCが誤って解放したメモリが別の用途で再利用されると、元のスライスが指していたデータが上書きされ、メモリ破損が発生します。これは、プログラムのクラッシュや予期せぬ動作につながる非常に深刻なバグです。

この問題は、Goのガベージコレクタに組み込まれているスライスの整合性チェック（slice len <= slice cap）によって実際に検出されました。このチェックは、スライスの内部状態が論理的に矛盾していないことを保証するためのものであり、今回のケースでは、最適化器の不整合によってこの条件が破られたことを示していました。

このコミットは、レジスタ最適化器が関数の入力変数を、GCのライブネス要件に従って適切に扱うように変更することで、この根本的な問題を解決します。

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

このコミットは、Goコンパイラのレジスタ最適化に関連する複数のファイルにわたる変更を含んでいます。主要な変更点は以下の通りです。

  1. src/cmd/{5g,6g,8g}/opt.h の変更: 各アーキテクチャ（ARM, AMD64, 386）の最適化ヘッダーファイルに、新しいBits型の変数ivarが追加されました。

    --- a/src/cmd/5g/opt.h
+++ b/src/cmd/5g/opt.h
@@ -96,6 +96,7 @@ EXTERN	Bits	externs;
 EXTERN	Bits	params;
 EXTERN	Bits	Bits	consts;
 EXTERN	Bits	addrs;
+EXTERN	Bits	ivar;
 EXTERN	Bits	ovar;
 EXTERN	int	change;
 EXTERN	int32	maxnr;

    ivarは"input variables"（入力変数）の略で、関数の入力引数に対応するビットマップを保持するために使用されます。

  2. src/cmd/{5g,6g,8g}/reg.c の変更: レジスタ割り当てと最適化のロジックを扱うファイルで、以下の重要な変更が行われました。

    • setoutvar 関数の汎用化とリネーム: 以前は戻り値変数（output variables）を設定するためだけに使われていた setoutvar 関数が、setvar というより汎用的な名前に変更され、Bits *dst と Type **args という引数を取るようになりました。これにより、入力変数（ivar）と出力変数（ovar）の両方を設定するために再利用できるようになりました。

      --- a/src/cmd/5g/reg.c
+++ b/src/cmd/5g/reg.c
@@ -57,7 +57,7 @@ rcmp(const void *a1, const void *a2)
 }
 
 static void
-setoutvar(void)
+setvar(Bits *dst, Type **args)
 {
 	Type *t;
 	Node *n;
@@ -66,18 +66,16 @@ setoutvar(void)
 	Bits bit;
 	int z;
 
-	t = structfirst(&save, getoutarg(curfn->type));
+	t = structfirst(&save, args);
 	while(t != T) {
 		n = nodarg(t, 1);
 		a = zprog.from;
 		naddr(n, &a, 0);
 		bit = mkvar(R, &a);
 		for(z=0; z<BITS; z++)
-			ovar.b[z] |= bit.b[z];
+			dst->b[z] |= bit.b[z];
 		t = structnext(&save);
 	}
-//if(bany(&ovar))
-//print("ovar = %Q\n", ovar);
 }

    • regopt 関数での ivar の初期化と設定: regopt 関数（レジスタ最適化のメインエントリポイント）内で、ivar ビットマップが初期化され、関数の引数（getthis(curfn->type) と getinarg(curfn->type)）に基づいて設定されるようになりました。

      --- a/src/cmd/5g/reg.c
+++ b/src/cmd/5g/reg.c
@@ -190,11 +188,14 @@ regopt(Prog *firstp)
 		params.b[z] = 0;
 		consts.b[z] = 0;
 		addrs.b[z] = 0;
+		ivar.b[z] = 0;
 		ovar.b[z] = 0;
 	}
 
-	// build list of return variables
-	setoutvar();
+	// build lists of parameters and results
+	setvar(&ivar, getthis(curfn->type));
+	setvar(&ivar, getinarg(curfn->type));
+	setvar(&ovar, getoutarg(curfn->type));
 
 	/*
 	 * pass 1

      getthisはレシーバ（メソッドの場合）、getinargは通常の入力引数を取得します。

    • prop 関数での ivar の伝播: prop 関数（レジスタのライブネスや使用状況を伝播させる役割を持つ）内で、ACALL（関数呼び出し）または ABL（分岐とリンク）命令を処理する際に、ivar ビットマップが cal（呼び出しによって破壊される可能性のあるレジスタのビットマップ）にマージされるようになりました。これにより、関数呼び出しをまたいで入力変数がライブであるとマークされることが保証されます。

      --- a/src/cmd/5g/reg.c
+++ b/src/cmd/5g/reg.c
@@ -895,8 +896,12 @@ prop(Reg *r, Bits ref, Bits cal)
 		case ABL:
 			if(noreturn(r1->f.prog))
 				break;
+
+			// Mark all input variables (ivar) as used, because that's what the
+			// liveness bitmaps say. The liveness bitmaps say that so that a
+			// panic will not show stale values in the parameter dump.
 			for(z=0; z<BITS; z++) {
-				cal.b[z] |= ref.b[z] | externs.b[z];
+				cal.b[z] |= ref.b[z] | externs.b[z] | ivar.b[z];
 				ref.b[z] = 0;
 			}

      追加されたコメントは、この変更の意図を明確に説明しています。「ライブネスビットマップがそう言っているから、すべての入力変数を「使用中」としてマークする。ライブネスビットマップがそう言っているのは、パニック時にパラメータダンプに古い値が表示されないようにするためである。」

  3. test/fixedbugs/issue7944.go の追加: このコミットは、報告されたバグ（Issue 7944）を再現し、修正が正しく機能することを確認するための新しいテストケースを追加しています。このテストは、スライスを引数として受け取り、そのスライスに対して操作を行い、途中でガベージコレクションを強制的に実行する関数を含んでいます。これにより、レジスタ最適化器とGCの間の不整合が顕在化する状況をシミュレートします。

    // Issue 7944:
// Liveness bitmaps said b was live at call to g,
// but no one told the register optimizer.

package main

import "runtime"

func f(b []byte) {
	for len(b) > 0 {
		n := len(b)
		n = f1(n)
		f2(b[n:])
		b = b[n:]
	}
	g()
}

func f1(n int) int {
	runtime.GC()
	return n
}

func f2(b []byte) {
	runtime.GC()
}

func g() {
	runtime.GC()
}

func main() {
	f(make([]byte, 100))
}

    このテストは、f 関数内でスライス b を繰り返し操作し、f1、f2、g といった関数呼び出しの前後で runtime.GC() を明示的に呼び出すことで、GCが頻繁に実行される状況を作り出しています。これにより、レジスタ最適化器がスライス b のライブネスを誤って判断し、GCが不整合なスライス情報に基づいて動作する可能性をテストしています。

コアとなるコードの解説

これらの変更の核心は、Goコンパイラのレジスタ最適化器が、関数の入力変数（引数）のライブネスに関するGoランタイムの要件を正しく認識し、尊重するようにすることです。

  • ivar の導入: opt.h に ivar ビットマップが追加されたことで、コンパイラは関数の入力変数を明示的に追跡できるようになりました。これは、出力変数（ovar）が追跡されていたのと同様のメカニズムです。

  • setvar の汎用化と regopt での利用: setvar 関数が汎用化され、regopt 関数内で ivar を設定するために使用されるようになったことで、関数の開始時にすべての入力引数が ivar ビットマップに正確に記録されるようになりました。これにより、これらの変数が「ライブ」であるという情報が、最適化プロセスの初期段階で利用可能になります。

  • prop 関数での ivar の伝播: 最も重要な変更は、prop 関数内での ivar の扱い方です。prop 関数は、プログラムの制御フローグラフを辿りながら、レジスタの使用状況やライブネス情報を伝播させる役割を担っています。関数呼び出し（ACALL や ABL）が発生する際、呼び出し元関数のレジスタの一部は、呼び出し先関数によって破壊される可能性があります。この「呼び出しによって破壊される可能性のあるレジスタ」を示すビットマップが cal です。 修正前は、cal には ref（参照されているレジスタ）と externs（外部参照）のみがマージされていました。しかし、修正後は ivar も cal にマージされるようになりました。これは、関数呼び出しが行われる際に、たとえレジスタ最適化器がその入力変数が一時的に不要であると判断したとしても、その入力変数が常にライブであるというGCの要件を満たすために、その変数が保持されるべきであることを強制します。 この変更により、レジスタ最適化器は、関数呼び出しをまたいで入力変数の値を保持するようになり、特にスライスのような複数ワードの複合型の場合に、その内部状態が不整合になることを防ぎます。結果として、ガベージコレクタがメモリを誤って解釈するリスクが排除され、メモリ破損の可能性がなくなります。

  • テストケースの追加: issue7944.go のテストケースは、この修正が実際に問題を解決したことを検証するためのものです。このテストは、スライス操作と強制的なGC呼び出しを組み合わせることで、以前のバグが顕在化する条件を再現し、修正後のコンパイラが正しく動作することを確認します。

これらの変更は、Goコンパイラのレジスタ最適化器とGoランタイムのガベージコレクタの間の協調を改善し、Goプログラムの堅牢性と安全性を高める上で不可欠なものです。

関連リンク

参考にした情報源リンク

  • Go言語の公式ドキュメント (スライス、ガベージコレクションなど)
  • Goコンパイラのソースコード (特に cmd/gc ディレクトリ)
  • コンパイラ最適化に関する一般的な知識 (レジスタ割り当て、ライブネス解析など)
  • ガベージコレクションの原理に関する一般的な知識
  • コミットメッセージと関連するGo Issueの議論