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

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

このコミットは、Goコンパイラ（cmd/gc）における小さな整数型を用いた境界チェックのバグ修正に関するものです。具体的には、配列や文字列のインデックスとして使用される小さな整数型（int8, int16など）に対して、コンパイラが誤って境界チェックを省略してしまう問題を解決しています。

コミット

commit c44768cb1c6403bb2cf90c49f4bbfcdf37f5bf2f
Author: Russ Cox <rsc@golang.org>
Date:   Thu May 24 14:01:39 2012 -0400

    cmd/gc: fix small integer bounds check bug
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/6254046

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

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

元コミット内容

Goコンパイラ（cmd/gc）において、小さな整数型（例: int8, int16）が配列や文字列のインデックスとして使用される際の境界チェックにバグが存在しました。このバグにより、コンパイラが特定の条件下で不適切に境界チェックを省略し、負のインデックスなどによる不正なメモリアクセスが発生する可能性がありました。

変更の背景

Go言語では、配列やスライスへのアクセス時にインデックスが有効な範囲内にあるかを検証する「境界チェック（bounds check）」が実行されます。これは、C/C++のような言語で発生しがちなバッファオーバーフローなどのセキュリティ脆弱性や実行時エラーを防ぐための重要な安全機構です。

しかし、境界チェックは実行時のオーバーヘッドを伴うため、コンパイラは静的にインデックスが常に有効な範囲内にあると判断できる場合に、このチェックを省略する最適化（境界チェック除去、bounds check elimination）を行います。

このコミットで修正されたバグは、この境界チェック除去のロジックに起因していました。具体的には、インデックスが小さな整数型（例: int8, int16）である場合、コンパイラはインデックスの型が表現できる最大値と配列/文字列の長さを比較して境界チェックを省略していました。しかし、この比較ロジックが符号付き整数と符号なし整数の挙動を適切に区別していなかったため、負のインデックスが与えられた場合に問題が発生しました。

例えば、int8（8ビット）型の変数がインデックスとして使われ、その値が負の場合、符号なしとして解釈されると非常に大きな正の値に見えてしまい、配列の境界内に収まっていると誤って判断され、境界チェックが省略されてしまう可能性がありました。これにより、本来パニック（実行時エラー）となるべき不正なインデックスアクセスが、パニックせずに不正なメモリアクセスを引き起こす可能性がありました。

前提知識の解説

  • Goコンパイラ (cmd/gc): Go言語の公式コンパイラです。ソースコードを機械語に変換する過程で、構文解析、型チェック、最適化、コード生成などを行います。
  • 境界チェック (Bounds Check): 配列やスライス、文字列などのシーケンス型にアクセスする際に、指定されたインデックスがそのシーケンスの有効な範囲内にあるかを確認する実行時チェックです。Go言語の安全性と堅牢性を保証する重要な機能の一つです。
  • 境界チェック除去 (Bounds Check Elimination): コンパイラ最適化の一種で、静的解析によってインデックスが常に有効な範囲内にあることが保証される場合に、実行時の境界チェックコードを削除することです。これにより、プログラムの実行速度が向上します。
  • 符号付き整数 (Signed Integer): 正の値、負の値、ゼロを表現できる整数型です（例: int, int8, int16, int32, int64）。最上位ビットが符号を表します。
  • 符号なし整数 (Unsigned Integer): 負の値を表現できず、ゼロと正の値のみを表現できる整数型です（例: uint, uint8, uint16, uint32, uint64）。すべてのビットが数値の大きさを表します。
  • AST (Abstract Syntax Tree): ソースコードの抽象的な構文構造を木構造で表現したものです。コンパイラはASTを走査（walk）しながら、型チェックや最適化、コード生成を行います。src/cmd/gc/walk.cはこのASTの走査に関連する処理を担うファイルです。

技術的詳細

このバグは、src/cmd/gc/walk.c内の境界チェック除去ロジックに存在していました。このファイルは、コンパイラの最適化フェーズにおいて、ASTを走査し、境界チェックを省略できる箇所を特定します。

問題のコードは、インデックスの型がwidth < 4（つまり、int8, int16などの小さな型）であり、かつ((1<<(8*n->right->type->width)) <= n->left->type->bound)という条件を満たす場合に、境界チェックを省略していました。

ここで、1<<(8*n->right->type->width)は、インデックスの型が表現できる「符号なし」の最大値に1を加えた値（つまり、その型のビット幅で表現できる値の総数）を計算しています。例えば、int8（8ビット）の場合、1 << 8は256です。この値と配列/文字列の長さ（n->left->type->boundまたはn->left->val.u.sval->len）を比較することで、「インデックスがその型の最大値を超えない限り、配列の範囲内である」という推論を行っていました。

しかし、この推論はインデックスが「符号なし」である場合にのみ正しく機能します。インデックスが「符号付き」である場合、負の値を取る可能性があります。例えば、int8型のインデックスが-1である場合、符号なしとして解釈すると255という大きな値になります。この255は配列の長さ（例えば10）よりも大きいため、本来であれば境界チェックが必要ですが、上記のロジックでは256 <= 10が偽となるため、境界チェックが省略されてしまう可能性がありました。

修正は、この境界チェック除去の条件に!issigned[n->right->type->etype]という条件を追加することです。issignedは、その型が符号付きであるかどうかを示すフラグです。!issignedは「符号付きではない」、つまり「符号なし」であることを意味します。これにより、この最適化はインデックスが符号なし整数型である場合にのみ適用されるようになり、符号付き整数型の負のインデックスによる誤った最適化が防止されます。

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

src/cmd/gc/walk.cの以下の箇所が変更されました。

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -846,11 +846,13 @@ walkexpr(Node **np, NodeList **init)
 		// if range of type cannot exceed static array bound,
 		// disable bounds check
 		if(isfixedarray(n->left->type))
+		if(!issigned[n->right->type->etype])
 		if(n->right->type->width < 4)
 		if((1<<(8*n->right->type->width)) <= n->left->type->bound)
 			n->etype = 1;
 
 		if(isconst(n->left, CTSTR))
+		if(!issigned[n->right->type->etype])
 		if(n->right->type->width < 4)
 		if((1<<(8*n->right->type->width)) <= n->left->val.u.sval->len)
 			n->etype = 1;

また、test/index.goには、int8やint16型のインデックス、および大きな配列/スライスを用いた多数のテストケースが追加され、この修正が正しく機能することを確認しています。特に、負のインデックスが正しくパニックを引き起こすこと、そして正のインデックスが適切に最適化されることを検証しています。

コアとなるコードの解説

変更されたsrc/cmd/gc/walk.cのコードは、Goコンパイラのバックエンドの一部であり、ASTの走査中に境界チェックの最適化を試みる部分です。

  • walkexpr(Node **np, NodeList **init): ASTのノードを走査する関数です。npは現在のノードへのポインタ、initは初期化リストです。
  • if(isfixedarray(n->left->type)) / if(isconst(n->left, CTSTR)): これらは、左辺が固定長配列であるか、または定数文字列であるかをチェックしています。つまり、配列または文字列へのインデックスアクセスを処理していることを示します。
  • if(n->right->type->width < 4): インデックスの型が4バイト未満（例: int8, int16）であることをチェックします。これは、小さな整数型に特有の最適化を適用するための条件です。
  • if((1<<(8*n->right->type->width)) <= n->left->type->bound) / if((1<<(8*n->right->type->width)) <= n->left->val.u.sval->len): この条件が、インデックスの型が表現できる最大値（符号なしとして解釈）が、配列の境界（bound）または文字列の長さ（len）以下であるかをチェックしていました。この条件が満たされると、インデックスが常に範囲内にあると推論し、n->etype = 1;によって境界チェックを無効化していました。
  • 追加された行: if(!issigned[n->right->type->etype])
    • n->right->type->etype: インデックスの型の基本型（例: TINT8、TUINT8など）を示します。
    • issigned[...]: この配列は、各基本型が符号付きであるかどうかを示すブーリアン値を含んでいます。
    • !issigned[...]: この条件は、「インデックスの型が符号付きではない」、すなわち「インデックスの型が符号なしである」場合にのみ真となります。

この追加により、境界チェック除去の最適化は、インデックスがuint8やuint16のような符号なし整数型である場合にのみ適用されるようになります。これにより、int8やint16のような符号付き整数型が負の値を取る可能性を考慮せずに最適化してしまうというバグが修正されました。

test/index.goの変更は、この修正を検証するためのものです。特に、int8やint16の負の値、および大きな配列サイズを組み合わせたテストケースを追加することで、コンパイラが正しい挙動（負のインデックスではパニック、正のインデックスでは最適化またはパニック）を示すことを確認しています。

関連リンク

  • Go言語の公式ドキュメント: https://golang.org/doc/
  • Goコンパイラのソースコード: https://github.com/golang/go/tree/master/src/cmd/gc
  • Go言語の境界チェックに関する議論（一般的な情報源）: Go言語のコンパイラ最適化、特に境界チェック除去に関する情報は、GoのブログやGoのIssueトラッカーで多く見られます。

参考にした情報源リンク

  • Go言語のソースコード（特にsrc/cmd/gc/walk.cおよびsrc/cmd/gc/go.hなどの型定義）
  • Go言語のコンパイラ設計に関する一般的な知識
  • Go言語のIssueトラッカーやChangeList (CL) の議論（https://golang.org/cl/6254046）