[インデックス 15960] ファイルの概要
このコミットは、Go言語のコンパイラ（cmd/gc）におけるデータ競合検出器（Race Detector）の挙動を改善するものです。具体的には、定数による除算において生成されるHMUL（High Multiply）ノードが、データ競合検出器によって誤って検出されないように、racewalk処理の対象に含める変更を行っています。これにより、特定の条件下で発生しうる誤検知（false negative）を防ぎ、データ競合検出の精度を向上させています。
コミット
commit 5f9a9433ea5f3e933d9950994edaf45c36a92ffb
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date: Tue Mar 26 23:35:42 2013 +0100
cmd/gc: enable racewalk of HMUL nodes.
A HMUL node appears in some constant divisions, but
to observe a false negative in race detector the divisor must be
suitably chosen to make sure the only memory access is
done for HMUL.
R=dvyukov
CC=golang-dev
https://golang.org/cl/7935045
---
src/cmd/gc/racewalk.c | 18 +++++++++---------\n src/pkg/runtime/race/testdata/mop_test.go | 4 ++--
2 files changed, 11 insertions(+), 11 deletions(-)
diff --git a/src/cmd/gc/racewalk.c b/src/cmd/gc/racewalk.c
index 80257985dd..fee5cf4226 100644
--- a/src/cmd/gc/racewalk.c
+++ b/src/cmd/gc/racewalk.c
@@ -241,6 +241,7 @@ racewalknode(Node **np, NodeList **init, int wr, int skip)\n case OXOR:\n case OSUB:\n case OMUL:\n+\tcase OHMUL:\n \tcase OEQ:\n \tcase ONE:\n \tcase OLT:\n@@ -379,19 +380,18 @@ racewalknode(Node **np, NodeList **init, int wr, int skip)\n \tcase OPARAM: // it appears only in fn->exit to copy heap params back\n \tcase OCLOSUREVAR:// immutable pointer to captured variable\n \tcase ODOTMETH: // either part of CALLMETH or CALLPART (lowered to PTRLIT)\n-\t\tgoto ret;\n-\n-\t// unimplemented\n-\tcase OSLICESTR:\n-\tcase OAPPEND:\n-\tcase ODCL:\n+\tcase OINDREG: // at this stage, only n(SP) nodes from nodarg\n+\tcase ODCL: // declarations (without value) cannot be races\n \tcase ODCLCONST:\n \tcase ODCLTYPE:\n-\tcase OLITERAL:\n \tcase OTYPE:\n \tcase ONONAME:\n-\tcase OINDREG:\n-\tcase OHMUL:\n+\tcase OLITERAL:\n+\tcase OSLICESTR: // always preceded by bounds checking, avoid double instrumentation.\n+\t\tgoto ret;\n+\n+\t// unimplemented\n+\tcase OAPPEND:\n \t\tgoto ret;\n \t}\n \ndiff --git a/src/pkg/runtime/race/testdata/mop_test.go b/src/pkg/runtime/race/testdata/mop_test.go\nindex f0fe868ccb..1a7ed96249 100644\n--- a/src/pkg/runtime/race/testdata/mop_test.go\n+++ b/src/pkg/runtime/race/testdata/mop_test.go\n@@ -339,11 +339,11 @@ func TestRaceDiv(t *testing.T) {\n }\n \n func TestRaceDivConst(t *testing.T) {\n-\tvar x, y, z int\n+\tvar x, y, z uint32\n \tch := make(chan int, 2)\n \n \tgo func() {\n-\t\tx = y / 3\n+\t\tx = y / 3 // involves only a HMUL node\n \t\tch <- 1\n \t}()\n \tgo func() {\n```
## GitHub上でのコミットページへのリンク
[https://github.com/golang/go/commit/5f9a9433ea5f3e933d9950994edaf45c36a92ffb](https://github.com/golang/go/commit/5f9a9433ea5f3e933d9950994edaf45c36a92ffb)
## 元コミット内容
このコミットは、Goコンパイラのデータ競合検出器において、`HMUL`ノードの`racewalk`処理を有効にすることを目的としています。`HMUL`ノードは特定の定数除算で出現しますが、データ競合検出器が誤検知（false negative）を発生させるためには、`HMUL`ノードのみがメモリにアクセスするように除数が適切に選択される必要があります。
## 変更の背景
Go言語のデータ競合検出器は、並行処理におけるメモリ競合（複数のゴルーチンが同時に同じメモリ位置にアクセスし、少なくとも一方が書き込み操作である場合に発生する問題）を検出するための強力なツールです。しかし、コンパイラの最適化によって生成される特定の種類のノードが、この検出器の対象から漏れることで、本来検出されるべき競合が見過ごされる（false negative）可能性があります。
このコミットの背景には、定数による除算の最適化があります。Goコンパイラは、`x / C`（Cは定数）のような除算を、乗算とビットシフトの組み合わせに変換することがあります。この変換の過程で、`HMUL`（High Multiply）ノードが生成されることがあります。`HMUL`ノードは、64ビット乗算の結果の上位32ビット（またはそれに対応する部分）を意味し、除算の逆演算として利用されます。
問題は、この`HMUL`ノードがメモリにアクセスする可能性があるにもかかわらず、データ競合検出器の`racewalk`処理の対象から除外されていた点にありました。その結果、`HMUL`ノードが関与するメモリ操作でデータ競合が発生した場合、検出器がそれを検知できないという「false negative」の可能性が生じていました。特に、除数が巧妙に選ばれた場合、`HMUL`ノードが唯一のメモリアクセスとなる状況を作り出すことができ、その場合に競合が見過ごされるリスクがありました。
このコミットは、この`HMUL`ノードを`racewalk`処理の対象に含めることで、データ競合検出器の網羅性を高め、より正確な競合検出を可能にすることを目的としています。
## 前提知識の解説
### Go言語のデータ競合検出器 (Race Detector)
Go言語に組み込まれているデータ競合検出器は、並行プログラムのデバッグにおいて非常に重要なツールです。これは、実行時にメモリへのアクセスを監視し、複数のゴルーチンが同時に同じメモリ位置にアクセスし、そのうち少なくとも1つが書き込み操作である場合に警告を発します。これにより、デッドロックや予期せぬプログラムの挙動の原因となるデータ競合を特定できます。
### `cmd/gc`
`cmd/gc`は、Go言語の公式コンパイラの実装です。Goのソースコードを機械語に変換する主要なツールであり、最適化やコード生成の多くの段階を含んでいます。
### `racewalk.c`
`racewalk.c`は、Goコンパイラの`cmd/gc`の一部であり、データ競合検出器のためのコードインストゥルメンテーション（計測コードの挿入）を担当するファイルです。コンパイラは、プログラムの抽象構文木（AST）を走査し、メモリへのアクセス（読み込みや書き込み）が行われる箇所に、データ競合検出器が監視するための特別な命令（インストゥルメンテーションコード）を挿入します。この走査プロセスが「racewalk」と呼ばれます。
### `Node`と`Op`
Goコンパイラ内部では、プログラムの構造は`Node`と呼ばれるデータ構造で表現されます。各`Node`は、変数、定数、演算子、関数呼び出しなど、プログラムの様々な要素を表します。`Op`は、これらの`Node`がどのような種類の操作（例: `OADD`は加算、`OMUL`は乗算）を表すかを示す列挙型です。
### `HMUL`ノード (High Multiply)
`HMUL`は「High Multiply」の略で、Goコンパイラが特定の最適化、特に定数による除算を行う際に生成される中間表現（IR）のノードです。例えば、`x / 3`のような除算は、コンパイラによって`x * (magic_number) >> (shift_amount)`のような乗算とビットシフトの組み合わせに変換されることがあります。この変換は、除算が乗算よりもCPUサイクルを多く消費するため、パフォーマンス向上のために行われます。`HMUL`ノードは、この乗算の結果の上位ビット（例えば、64ビット乗算の結果の上位32ビット）を表すために使用されます。これは、除算の商を効率的に計算するために必要となる場合があります。
### False Negative (誤検知漏れ)
データ競合検出器における「false negative」とは、実際にデータ競合が発生しているにもかかわらず、検出器がそれを報告しない状態を指します。これは、検出器の網羅性や精度に問題があることを示し、デバッグを困難にする可能性があります。
## 技術的詳細
Goコンパイラの`racewalk`処理は、プログラムのASTを走査し、メモリ操作が行われるノードに対してデータ競合検出のためのインストゥルメンテーションコードを挿入します。この処理は、`racewalknode`関数によって行われます。
`racewalknode`関数内には、様々な`Op`（操作の種類）に対応する`case`文が存在し、それぞれのノードタイプがどのように処理されるべきかを定義しています。一部のノードタイプは、メモリアクセスを伴わないため、`racewalk`処理をスキップして`goto ret;`で早期にリターンします。
このコミット以前は、`HMUL`ノードがこのスキップリストに含まれていました。これは、`HMUL`ノードが直接的なメモリ操作を行わないと見なされていたためかもしれません。しかし、前述の通り、`HMUL`ノードは定数除算の最適化の一部として生成され、その結果がメモリに書き込まれる可能性があります。特に、除数が適切に選択された場合、`HMUL`ノードの計算結果が直接メモリに影響を与え、他のメモリ操作が伴わない状況でデータ競合が発生する可能性がありました。この場合、`HMUL`ノードが`racewalk`の対象から外れていると、競合が検出されずに「false negative」となります。
このコミットの変更は、`racewalknode`関数において、`HMUL`ノードを`OMUL`（通常の乗算）などと同様に、メモリアクセスを伴う可能性のある操作として扱うように修正しています。これにより、`HMUL`ノードが関与するメモリ操作もデータ競合検出器の監視対象となり、誤検知の可能性が排除されます。
また、テストケース`src/pkg/runtime/race/testdata/mop_test.go`の変更は、この修正が正しく機能することを確認するためのものです。`TestRaceDivConst`関数において、`x = y / 3`という操作が`HMUL`ノードを生成する典型的な例として使用され、この操作がデータ競合検出器によって正しく監視されることを検証しています。`uint32`型への変更は、特定のビット幅での`HMUL`ノードの生成をより確実にし、テストの再現性を高めるためと考えられます。
## コアとなるコードの変更箇所
### `src/cmd/gc/racewalk.c`
```diff
--- a/src/cmd/gc/racewalk.c
+++ b/src/cmd/gc/racewalk.c
@@ -241,6 +241,7 @@ racewalknode(Node **np, NodeList **init, int wr, int skip)\n case OXOR:\n case OSUB:\n case OMUL:\n+\tcase OHMUL:\n case OEQ:\n case ONE:\n case OLT:\
@@ -379,19 +380,18 @@ racewalknode(Node **np, NodeList **init, int wr, int skip)\n \tcase OPARAM: // it appears only in fn->exit to copy heap params back\n \tcase OCLOSUREVAR:// immutable pointer to captured variable\n \tcase ODOTMETH: // either part of CALLMETH or CALLPART (lowered to PTRLIT)\n-\t\tgoto ret;\n-\n-\t// unimplemented\n-\tcase OSLICESTR:\n-\tcase OAPPEND:\n-\tcase ODCL:\n+\tcase OINDREG: // at this stage, only n(SP) nodes from nodarg\n+\tcase ODCL: // declarations (without value) cannot be races\n \tcase ODCLCONST:\n \tcase ODCLTYPE:\n-\tcase OLITERAL:\n \tcase OTYPE:\n \tcase ONONAME:\n-\tcase OINDREG:\n-\tcase OHMUL:\n+\tcase OLITERAL:\n+\tcase OSLICESTR: // always preceded by bounds checking, avoid double instrumentation.\n+\t\tgoto ret;\n+\n+\t// unimplemented\n+\tcase OAPPEND:\n \t\tgoto ret;\
racewalknode関数のswitch文において、OMUL（乗算）のケースにOHMULが追加されました。これにより、HMULノードも通常の算術演算子と同様にracewalk処理の対象となります。racewalknode関数の後半にある、goto ret;で早期リターンするノードのリストからOHMULが削除されました。これは、OHMULがもはや「未実装」または「競合検出不要」なノードではないことを意味します。- 同時に、
OINDREG（レジスタ間接参照）がgoto ret;のリストに移動されました。これは、OINDREGがこの段階ではn(SP)（スタックポインタからのオフセット）ノードのみを指し、競合検出の対象外と判断されたためです。 OSLICESTR（文字列スライス）もgoto ret;のリストに移動され、その理由として「常に境界チェックが先行するため、二重のインストゥルメンテーションを避ける」とコメントが追加されました。
src/pkg/runtime/race/testdata/mop_test.go
--- a/src/pkg/runtime/race/testdata/mop_test.go
+++ b/src/pkg/runtime/race/testdata/mop_test.go
@@ -339,11 +339,11 @@ func TestRaceDiv(t *testing.T) {\n }\n \n func TestRaceDivConst(t *testing.T) {\n-\tvar x, y, z int\n+\tvar x, y, z uint32\n \tch := make(chan int, 2)\n \n \tgo func() {\n-\t\tx = y / 3\n+\t\tx = y / 3 // involves only a HMUL node\n \t\tch <- 1\n \t}()\n \tgo func() {\
TestRaceDivConst関数において、変数x,y,zの型がintからuint32に変更されました。x = y / 3という行に「// involves only a HMUL node」というコメントが追加されました。これは、この除算操作がコンパイラによってHMULノードを含む形に最適化されることを明示しています。
コアとなるコードの解説
src/cmd/gc/racewalk.cの変更
racewalk.cにおける変更の核心は、HMULノードがデータ競合検出器の監視対象となるように、racewalknode関数の処理フローを変更した点です。
以前は、HMULノードはgoto ret;のブロック内にあり、これはracewalknode関数がそのノードに対して何も特別な処理を行わずに早期にリターンすることを意味していました。つまり、HMULノードが関与するメモリ操作は、データ競合検出器によってインストゥルメンテーションされず、監視対象外となっていました。
このコミットでは、HMULをOMUL（通常の乗算）と同じcaseブロックに移動させました。これにより、HMULノードもOMULと同様に、そのオペランドや結果がメモリにアクセスする可能性があるものとして扱われ、データ競合検出器が必要なインストゥルメンテーションコードを挿入するようになります。この変更により、HMULノードが関与するメモリ競合も適切に検出されるようになり、データ競合検出器の「false negative」の問題が解決されます。
OINDREGとOSLICESTRの移動は、racewalk処理の最適化と正確性の向上を目的としています。OINDREGは、このコンパイル段階ではスタックポインタからのオフセットを指すことが多く、直接的な競合の対象ではないため、スキップリストに移動されました。OSLICESTRは、常に先行する境界チェックによって安全性が保証されるため、二重のインストゥルメンテーションを避けるためにスキップリストに移動されました。これらの変更は、racewalk処理の効率を向上させつつ、競合検出の正確性を維持するためのものです。
src/pkg/runtime/race/testdata/mop_test.goの変更
mop_test.goの変更は、racewalk.cの修正が意図通りに機能することを検証するためのテストケースの調整です。
- 型の変更 (
intからuint32へ):x,y,zの型をintからuint32に変更した理由は、コンパイラが特定の型と定数除算の組み合わせでHMULノードを生成する可能性が高まるためと考えられます。uint32のような固定幅の符号なし整数型は、コンパイラが除算を乗算とシフトに変換する際に、より予測可能な挙動を示すことがあります。これにより、テストケースが確実にHMULノードを生成し、そのracewalk処理がテストされることを保証します。 - コメントの追加:
x = y / 3 // involves only a HMUL nodeというコメントは、この行がHMULノードを生成する典型的な例であることを明示しています。これは、このテストがHMULノードのracewalk処理を具体的に検証していることを示すものです。
このテストケースは、2つのゴルーチンがyにアクセスし、その結果をxに代入する際に、y / 3という操作がHMULノードを介して行われる状況をシミュレートしています。HMULノードが正しくracewalkされるようになれば、このテストはデータ競合を正しく検出するはずです。
関連リンク
- Go CL 7935045: https://golang.org/cl/7935045
参考にした情報源リンク
- Go Race Detector: https://go.dev/doc/articles/race_detector
- Go Compiler Internals (General): https://go.dev/doc/articles/go_compiler_internals
- Division by constant optimization: https://en.wikipedia.org/wiki/Division_algorithm#Division_by_a_constant
- High Multiply (HMUL) in compilers (general concept): https://www.cs.cmu.edu/~411/lectures/lec10-code-gen.pdf (General compiler optimization context, not specific to Go)
- Go source code (for context on
cmd/gcandracewalk.c): https://github.com/golang/go