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

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

このコミットは、Goコンパイラのcmd/gcにおけるデータ競合検出のためのracewalk処理に、より多くのケースを実装し、その正確性と網羅性を向上させるものです。具体的には、特定のノードタイプに対する処理の追加、不要な計測の除外、そして新たな計測対象の導入が含まれています。

コミット

commit 656bc3eb960fb2af7fb057700dd2f5b352b21317
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Thu Mar 21 08:53:52 2013 +0100

    cmd/gc: implement more cases in racewalk.
    
    Add missing CLOSUREVAR in switch.
    Mark MAKE, string conversion nodes as impossible.
    Control statements do not need instrumentation.
    Instrument COM and LROT nodes.
    Instrument map length.
    
    Update #4228
    
    R=dvyukov, golang-dev
    CC=golang-dev
    https://golang.org/cl/7504047

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

https://github.com/golang/go/commit/656bc3eb960fb2af7fb057700dd2f5b352b21317

元コミット内容

cmd/gc: implement more cases in racewalk.

このコミットは、Goコンパイラのcmd/gcパッケージ内のracewalk関数において、データ競合検出のための処理対象となるノードの種類を拡張するものです。具体的には以下の変更が含まれます。

  • CLOSUREVARノードがswitch文に追加されました。
  • MAKEおよび文字列変換に関連するノードが「不可能」としてマークされました。
  • 制御文（if, forなど）は計測が不要とされました。
  • COM（補数演算）およびLROT（左ローテーション）ノードが計測対象に追加されました。
  • マップの長さ（len(map)）の取得が計測対象に追加されました。

これはIssue #4228の更新に関連しています。

変更の背景

Go言語には、並行処理におけるデータ競合（data race）を検出するためのレース検出器（Race Detector）が組み込まれています。このレース検出器は、プログラムの実行中に共有メモリへの同時アクセスを監視し、競合状態を報告することで、並行バグの特定を支援します。

racewalk関数は、Goコンパイラのバックエンドの一部であり、データ競合検出のためにコードを計測（instrumentation）する役割を担っています。計測とは、共有メモリへのアクセスが発生する可能性のある箇所に、レース検出器が監視するための追加コードを挿入することです。

このコミットの背景には、既存のracewalkの実装が、すべての潜在的なデータ競合の発生源を適切に計測できていなかったという問題があります。特に、特定の演算子や組み込み関数の使用が、共有メモリへのアクセスを引き起こす可能性があるにもかかわらず、レース検出器の監視対象から漏れていた可能性があります。

具体的には、以下の点が課題として挙げられます。

  • 網羅性の不足: racewalkが処理すべきノードタイプが不足しており、一部の操作がレース検出器の監視対象外となっていた。
  • 誤った計測: 一部のノードタイプは計測が不要であるにもかかわらず、誤って計測対象として扱われていたか、あるいはその逆の状況があった。
  • マップの長さの計測: len(map)のような操作が、内部的にマップのデータ構造にアクセスするため、データ競合の可能性を秘めているにもかかわらず、適切に計測されていなかった。

これらの課題を解決し、レース検出器の精度と信頼性を向上させることが、このコミットの目的です。

前提知識の解説

このコミットを理解するためには、以下の概念について理解しておく必要があります。

  1. Goコンパイラ (cmd/gc):

    • Go言語の公式コンパイラであり、Goソースコードを機械語に変換します。
    • コンパイルプロセスは複数のステージに分かれており、構文解析、型チェック、中間表現（IR）への変換、最適化、コード生成などが行われます。
    • cmd/gcは、これらのステージの一部を担当し、特に中間表現の操作や最適化、そしてバックエンドでのコード生成に関わります。

  2. 中間表現 (IR) とノード (Node):

    • コンパイラは、ソースコードを直接機械語に変換するのではなく、まず抽象構文木（AST）や、より低レベルの中間表現に変換します。
    • Goコンパイラでは、プログラムの各要素（変数、定数、演算子、関数呼び出しなど）がNodeと呼ばれるデータ構造で表現されます。
    • 各Nodeには、その種類を示すOp（オペレーションコード）が割り当てられています（例: OPLUSは加算、OCALLは関数呼び出し）。

  3. データ競合 (Data Race):

    • 複数のゴルーチンが同時に同じメモリ位置にアクセスし、そのうち少なくとも1つのアクセスが書き込みであり、かつアクセスが同期メカニズムによって保護されていない場合に発生するバグです。
    • データ競合は、プログラムの予測不能な動作、クラッシュ、または誤った結果を引き起こす可能性があります。

  4. Goレース検出器 (Go Race Detector):

    • Go 1.1から導入されたツールで、プログラム実行中にデータ競合を検出します。
    • コンパイル時にgo run -raceやgo build -raceのように-raceフラグを付けることで有効になります。
    • レース検出器は、共有メモリへのアクセスを監視するために、コンパイラが生成するコードに特別な「計測（instrumentation）」コードを挿入します。

  5. racewalk関数:

    • src/cmd/gc/racewalk.cに実装されているGoコンパイラの内部関数です。
    • コンパイルプロセスの後半で、中間表現（Nodeのツリー）を走査し、データ競合検出のために必要な計測コードを挿入します。
    • この関数は、各NodeのOpに基づいて、そのノードが共有メモリへのアクセスを伴うかどうかを判断し、必要に応じて読み書きの監視コードを追加します。

  6. NodeのOpの種類:

    • OPLUS: 加算
    • OREAL, OIMAG: 複素数の実部・虚部
    • OCOM: ビットごとの補数（NOT）演算子 ^
    • OLSH, ORSH: 左シフト、右シフト
    • OLROT: 左ローテーション（ビットシフトの一種）
    • OCAP: cap()組み込み関数
    • ODIV, OMOD: 除算、剰余
    • OCLOSUREVAR: クロージャ内で外部スコープの変数を参照するノード
    • OMAKECHAN, OMAKEMAP, OMAKESLICE: make()組み込み関数でチャネル、マップ、スライスを作成するノード
    • OCALL: 関数呼び出し
    • OCOPY: copy()組み込み関数
    • ORUNESTR, OARRAYBYTESTR, OARRAYRUNESTR, OSTRARRAYBYTE, OSTRARRAYRUNE: 文字列とバイト/runeスライス間の変換
    • OINDEXMAP: マップのインデックスアクセス
    • OCMPSTR, OADDSTR: 文字列の比較、連結
    • ODOTTYPE, ODOTTYPE2: 型アサーション
    • OPANIC, ORECOVER: panic()とrecover()
    • OCONVIFACE: インターフェース型への変換
    • ORROTC, OEXTEND: バックエンドでのみ現れるノード（通常はフロントエンドでより低レベルのノードに変換される）
    • OFOR, OIF, OSWITCH, ORETURN, OSELECT, OEMPTY, OBREAK, OCONTINUE, OFALL, OGOTO, OLABEL: 制御フローに関するノード
    • OPRINT, OPRINTN: print()/println()組み込み関数
    • OPARAM: 関数パラメータ
    • OSLICESTR, OAPPEND, OCMPIFACE, OARRAYLIT, OMAPLIT, OSTRUCTLIT, OCLOSURE, ODCL, ODCLCONST, ODCLTYPE, OLITERAL, ONAME, OTYPE, ONONAME, OINDREG, ODOTMETH, OITAB, OHMUL, OCHECKNOTNIL: その他の様々なノードタイプ

技術的詳細

このコミットの主要な変更は、src/cmd/gc/racewalk.c内のracewalknode関数に集中しています。この関数は、Goプログラムの抽象構文木（AST）を走査し、データ競合検出のためにメモリアクセスを計測する役割を担っています。

変更点の詳細を以下に示します。

  1. CLOSUREVARの追加:

    • racewalknode関数のswitch文にOCLOSUREVARが追加されました。これは、クロージャが外部スコープの変数を参照する際に生成されるノードです。
    • 以前はOCLOSUREVARがunimplementedセクションに分類されていましたが、これは計測が不要なノードとしてgoto ret;（計測せずに戻る）処理が追加されました。これは、CLOSUREVAR自体が直接的なメモリアクセスを伴うわけではなく、その参照先の変数が計測されるべきであるためと考えられます。

  2. MAKEおよび文字列変換ノードの「不可能」マーク:

    • OMAKECHAN, OMAKEMAP, OMAKESLICE（make組み込み関数）、OCALL（関数呼び出し）、OCOPY（copy組み込み関数）、ORUNESTR, OARRAYBYTESTR, OARRAYRUNESTR, OSTRARRAYBYTE, OSTRARRAYRUNE（文字列変換）、OINDEXMAP（マップインデックスアクセス）、OCMPSTR（文字列比較）、OADDSTR（文字列連結）、ODOTTYPE, ODOTTYPE2（型アサーション）といったノードが、yyerror("racewalk: %O must be lowered by now", n->op);というエラーメッセージと共に「不可能」なノードとして分類されました。
    • これは、これらのノードがracewalkが実行されるコンパイルフェーズでは、すでに低レベルの操作（例えば、関数呼び出しやメモリ操作）に「降格（lowered）」されているべきであり、元の高レベルなOpとして存在すべきではないことを意味します。もしこれらのノードがこの段階で現れた場合、それはコンパイラの内部的な不整合を示唆します。
    • ORROTC（右ローテーション）とOEXTENDも同様にyyerror("racewalk: %O cannot exist now", n->op);というメッセージで「不可能」なノードとしてマークされました。これらはバックエンドでのみ現れるノードであり、racewalkが実行される段階では存在しないはずです。

  3. 制御文の計測除外:

    • OFOR, OIF, OSWITCH, ORETURN, OSELECT, OEMPTY, OBREAK, OCONTINUE, OFALL, OGOTO, OLABELといった制御フローに関するノードが、明示的に計測が不要なノードとしてgoto ret;処理が追加されました。
    • これらのノード自体はメモリへの読み書きを直接伴わないため、レース検出器による計測は不要です。これらの制御文の内部にある式やステートメントが個別に計測されます。

  4. COMおよびLROTノードの計測:

    • OPLUS, OREAL, OIMAGなどと同様に、OCOM（ビットごとの補数演算）とOLROT（左ローテーション）がracewalknode(&n->left, init, wr, 0);によって左オペランドの計測が行われるように変更されました。
    • これらの演算は、オペランドの値を読み取るため、共有変数に対して行われる場合にデータ競合の可能性があり、計測が必要と判断されました。

  5. マップの長さの計測 (len(map)):

    • OCAP（cap()組み込み関数）の処理において、istype(n->left->type, TMAP)（左オペランドがマップ型である場合）のブロックが変更されました。
    • 以前はコメントアウトされていたり、不完全な計測コードがあったりしましたが、このコミットではlen(map)の操作が適切に計測されるように修正されました。
    • 具体的には、マップのポインタをuint8のポインタに変換し、そのポインタを間接参照するOINDノードを作成し、callinstr関数で計測コードを挿入しています。これは、len(map)がマップの内部データ構造にアクセスするため、そのアクセスが共有メモリに対するものである場合にデータ競合を検出できるようにするためです。

これらの変更により、racewalkはより多くの種類のGo言語の操作に対してデータ競合検出の計測を適用できるようになり、レース検出器の精度が向上しました。

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

主要な変更はsrc/cmd/gc/racewalk.cファイルにあります。

--- a/src/cmd/gc/racewalk.c
+++ b/src/cmd/gc/racewalk.c
@@ -196,6 +196,7 @@ racewalknode(Node **np, NodeList **init, int wr, int skip)\n 	case OPLUS:\n 	case OREAL:\n 	case OIMAG:\n+\tcase OCOM:\n \t\tracewalknode(&n->left, init, wr, 0);\n \t\tgoto ret;\n \n@@ -222,23 +223,17 @@ racewalknode(Node **np, NodeList **init, int wr, int skip)\n 	case OCAP:\n 	\tracewalknode(&n->left, init, 0, 0);\n 	\tif(istype(n->left->type, TMAP)) {\n-\t\t\t// crashes on len(m[0]) or len(f())\n-\t\t\tSET(n1);\n-\t\t\tUSED(n1);\n-\t\t\t/*\n-\t\t\tn1 = nod(OADDR, n->left, N);\n-\t\t\tn1 = conv(n1, types[TUNSAFEPTR]);\n-\t\t\tn1 = conv(n1, ptrto(ptrto(types[TINT8])));\n-\t\t\tn1 = nod(OIND, n1, N);\n+\t\t\tn1 = nod(OCONVNOP, n->left, N);\n+\t\t\tn1->type = ptrto(types[TUINT8]);\n \t\t\tn1 = nod(OIND, n1, N);\n \t\t\ttypecheck(&n1, Erv);\n \t\t\tcallinstr(&n1, init, 0, skip);\n-\t\t\t*/\n \t\t}\n \t\tgoto ret;\n \n \tcase OLSH:\n \tcase ORSH:\n+\tcase OLROT:\n \tcase OAND:\n \tcase OANDNOT:\n \tcase OOR:\
@@ -279,7 +274,6 @@ racewalknode(Node **np, NodeList **init, int wr, int skip)\n \n \tcase ODIV:\n \tcase OMOD:\n-\t\t// TODO(dvyukov): add a test for this\n \t\tracewalknode(&n->left, init, wr, 0);\n \t\tracewalknode(&n->right, init, wr, 0);\n \t\tgoto ret;\n@@ -324,9 +318,30 @@ racewalknode(Node **np, NodeList **init, int wr, int skip)\n \tcase OPANIC:\n \tcase ORECOVER:\n \tcase OCONVIFACE:\n+\tcase OMAKECHAN:\n+\tcase OMAKEMAP:\n+\tcase OMAKESLICE:\n+\tcase OCALL:\n+\tcase OCOPY:\n+\tcase ORUNESTR:\n+\tcase OARRAYBYTESTR:\n+\tcase OARRAYRUNESTR:\n+\tcase OSTRARRAYBYTE:\n+\tcase OSTRARRAYRUNE:\n+\tcase OINDEXMAP:  // lowered to call\n+\tcase OCMPSTR:\n+\tcase OADDSTR:\n+\tcase ODOTTYPE:\n+\tcase ODOTTYPE2:\
 \t\tyyerror(\"racewalk: %O must be lowered by now\", n->op);\n \t\tgoto ret;\n \n+\t// impossible nodes: only appear in backend.\n+\tcase ORROTC:\n+\tcase OEXTEND:\n+\t\tyyerror(\"racewalk: %O cannot exist now\", n->op);\n+\t\tgoto ret;\n+\n \t// just do generic traversal\n \tcase OFOR:\n \tcase OIF:\
@@ -334,43 +349,28 @@ racewalknode(Node **np, NodeList **init, int wr, int skip)\n \tcase ORETURN:\n \tcase OSELECT:\n \tcase OEMPTY:\n+\tcase OBREAK:\n+\tcase OCONTINUE:\n+\tcase OFALL:\n+\tcase OGOTO:\n+\tcase OLABEL:\
 \t\tgoto ret;\n \n \t// does not require instrumentation\n-\tcase OINDEXMAP:  // implemented in runtime\n \tcase OPRINT:     // don\'t bother instrumenting it\n \tcase OPRINTN:    // don\'t bother instrumenting it\n \tcase OPARAM:     // it appears only in fn->exit to copy heap params back\n \t\tgoto ret;\n \n \t// unimplemented\n-\tcase OCMPSTR:\n-\tcase OADDSTR:\
 \tcase OSLICESTR:\n \tcase OAPPEND:\n-\tcase OCOPY:\n-\tcase OMAKECHAN:\n-\tcase OMAKEMAP:\n-\tcase OMAKESLICE:\n-\tcase ORUNESTR:\n-\tcase OARRAYBYTESTR:\n-\tcase OARRAYRUNESTR:\n-\tcase OSTRARRAYBYTE:\n-\tcase OSTRARRAYRUNE:\
 \tcase OCMPIFACE:\n \tcase OARRAYLIT:\n \tcase OMAPLIT:\n \tcase OSTRUCTLIT:\n \tcase OCLOSURE:\
-\tcase ODOTTYPE:\n-\tcase ODOTTYPE2:\n-\tcase OCALL:\n-\tcase OBREAK:\
 \tcase ODCL:\
-\tcase OCONTINUE:\n-\tcase OFALL:\n-\tcase OGOTO:\n-\tcase OLABEL:\
 \tcase ODCLCONST:\n \tcase ODCLTYPE:\n \tcase OLITERAL:\
@@ -378,14 +378,11 @@ racewalknode(Node **np, NodeList **init, int wr, int skip)\n \tcase OTYPE:\n \tcase ONONAME:\n \tcase OINDREG:\n-\tcase OCOM:\
 \tcase ODOTMETH:\n \tcase OITAB:\n-\tcase OEXTEND:\
 \tcase OHMUL:\n-\tcase OLROT:\n-\tcase ORROTC:\
 \tcase OCHECKNOTNIL:\
+\tcase OCLOSUREVAR:\
 \t\tgoto ret;\
 \t}\

また、以下のテストファイルが追加・修正されています。

  • src/pkg/runtime/race/testdata/map_test.go: TestRaceMapLenとTestRaceMapLenDeleteが追加され、マップの長さ取得がレース検出器によって計測されることを確認しています。
  • src/pkg/runtime/race/testdata/mop_test.go: TestRaceComplement, TestRaceDiv, TestRaceDivConst, TestRaceMod, TestRaceModConst, TestRaceRotateが追加され、OCOM, ODIV, OMOD, OLROTなどの演算子が計測されることを確認しています。
  • src/pkg/runtime/race/testdata/regression_test.go: TestRaceUnaddressableMapLenが追加され、アドレス指定できないマップの長さ取得が適切に処理されることを確認しています。
  • src/pkg/runtime/race/testdata/slice_test.go: TestRaceConcatStringとTestRaceCompareStringが追加され、文字列の連結と比較がレース検出器によって計測されることを確認しています。

コアとなるコードの解説

racewalknode関数は、GoコンパイラのASTノードを再帰的に走査し、データ競合検出のための計測コードを挿入します。この関数は、現在のノードnのOp（オペレーションコード）に基づいて異なる処理を行います。

  1. OCOM (補数演算) の計測追加:

    • case OPLUS:, case OREAL:, case OIMAG: のグループに case OCOM: が追加されました。
    • これらの演算子は、そのオペランドの値を読み取るため、racewalknode(&n->left, init, wr, 0); を呼び出して左オペランドを計測します。wrは書き込みフラグで、ここでは0（読み込み）が渡されます。これにより、補数演算の対象となる変数が共有されている場合に、その読み込みがレース検出器によって監視されるようになります。

  2. OCAP (cap()関数) のマップ長計測の修正:

    • case OCAP: のブロック内で、if(istype(n->left->type, TMAP)) の条件が真の場合（つまり、cap()の引数がマップである場合）の処理が変更されました。
    • 以前のコードはコメントアウトされていたり、不完全な実装でしたが、新しいコードではマップの長さを取得する操作を計測するように修正されています。
    • n1 = nod(OCONVNOP, n->left, N);：n->left（マップ）をOCONVNOP（型変換なしの変換）ノードでラップします。
    • n1->type = ptrto(types[TUINT8]);：n1の型を*uint8に設定します。これは、マップの内部構造へのポインタを汎用的なバイトポインタとして扱うためです。
    • n1 = nod(OIND, n1, N);：n1をOIND（間接参照）ノードでラップします。これにより、マップの内部データへのアクセスが表現されます。
    • typecheck(&n1, Erv);：新しく作成されたノードn1の型チェックを行います。
    • callinstr(&n1, init, 0, skip);：callinstr関数を呼び出して、このメモリアクセスに対する計測コードを挿入します。0は読み込み操作であることを示します。
    • これにより、len(map)が呼び出された際に、マップの内部データ構造への読み込みアクセスがレース検出器によって監視され、データ競合の検出が可能になります。

  3. OLROT (左ローテーション) の計測追加:

    • case OLSH:, case ORSH: のグループに case OLROT: が追加されました。
    • これらのビット演算もオペランドの値を読み取るため、racewalknode(&n->left, init, wr, 0); を呼び出して左オペランドを計測します。

  4. 「この段階では存在しないはず」のノードの分類:

    • OMAKECHAN, OMAKEMAP, OMAKESLICE, OCALL, OCOPY, 各種文字列変換ノード、OINDEXMAP, OCMPSTR, OADDSTR, ODOTTYPE, ODOTTYPE2などが、yyerror("racewalk: %O must be lowered by now", n->op);というエラーメッセージと共に新しいグループに移動されました。
    • これは、これらの高レベルな操作がracewalkが実行されるコンパイルフェーズでは、すでに低レベルの操作（例えば、ランタイム関数呼び出しや直接的なメモリ操作）に「降格（lowered）」されているべきであり、元の高レベルなOpとして存在すべきではないというコンパイラの設計思想を反映しています。もしこれらのノードがこの段階で現れた場合、それはコンパイラのフロントエンドまたは中間段階での処理に問題があることを示唆します。
    • 同様に、ORROTCとOEXTENDは「バックエンドでのみ現れるノード」として、yyerror("racewalk: %O cannot exist now", n->op);というエラーメッセージと共に分類されました。これらはracewalkが実行される段階では存在しないはずです。

  5. 制御文の計測除外の明示:

    • OFOR, OIF, OSWITCH, ORETURN, OSELECT, OEMPTYのグループに、OBREAK, OCONTINUE, OFALL, OGOTO, OLABELが追加されました。
    • これらのノードは制御フローを表現するものであり、直接的なメモリアクセスを伴わないため、計測は不要です。goto ret;によって、これらのノードに対する計測処理をスキップします。

  6. OCLOSUREVARの計測除外:

    • OCLOSUREVARがunimplementedセクションから、goto ret;を持つ計測不要なノードのグループに移動されました。
    • これは、クロージャ変数の参照自体は直接的なメモリアクセスではないため、計測が不要であると判断されたことを意味します。実際のメモリアクセスは、その変数が使用される箇所で計測されます。

これらの変更により、racewalkはGoプログラムのより多くの側面を正確に計測できるようになり、レース検出器の検出能力が向上しました。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード（特にsrc/cmd/gc/racewalk.c）
  • Go言語の公式ドキュメント
  • Go言語のIssueトラッカー
  • Go言語のコンパイラに関する一般的な知識
  • データ競合検出器に関する一般的な知識