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

このコミットは、Goランタイムのガベージコレクタ（GC）における、空文字列（zero-length string）の誤ったハンドリングを修正するものです。具体的には、GCが文字列の型情報に基づいてヒープを走査する際に、空文字列のデータポインタが指す領域を誤って「訪問済み（visited）」とマークし、その領域が指す可能性のあるポインタをスキャンしないことで、本来GCが管理すべきオブジェクトが解放されてしまうバグを修正します。この問題は、特にs[len(s):]のように文字列の末尾から空文字列を生成した場合に顕在化しました。

コミット

commit 54c901cd08d5beb1269af2e73f59d2dec55634e8
Author: Russ Cox <rsc@golang.org>
Date:   Tue Mar 11 23:58:39 2014 -0400

    runtime: fix empty string handling in garbage collector
    
    The garbage collector uses type information to guide the
    traversal of the heap. If it sees a field that should be a string,
    it marks the object pointed at by the string data pointer as
    visited but does not bother to look at the data, because
    strings contain bytes, not pointers.
    
    If you save s[len(s):] somewhere, though, the string data pointer
    actually points just beyond the string data; if the string data
    were exactly the size of an allocated block, the string data
    pointer would actually point at the next block. It is incorrect
    to mark that next block as visited and not bother to look at
    the data, because the next block may be some other type
    entirely.
    
    The fix is to ignore strings with zero length during collection:
    they are empty and can never become non-empty: the base
    pointer will never be used again. The handling of slices already
    does this (but using cap instead of len).
    
    This was not a bug in Go 1.2, because until January all string
    allocations included a trailing NUL byte not included in the
    length, so s[len(s):] still pointed inside the string allocation
    (at the NUL).
    
    This bug was causing the crashes in test/run.go. Specifically,
    the parsing of a regexp in package regexp/syntax allocated a
    []syntax.Inst with rounded size 1152 bytes. In fact it
    allocated many such slices, because during the processing of
    test/index2.go it creates thousands of regexps that are all
    approximately the same complexity. That takes a long time, and
    test/run works on other tests in other goroutines. One such
    other test is chan/perm.go, which uses an 1152-byte source
    file. test/run reads that file into a []byte and then calls
    strings.Split(string(src), "\n"). The string(src) creates an
    1152-byte string - and there's a very good chance of it
    landing next to one of the many many regexp slices already
    allocated - and then because the file ends in a \n,
    strings.Split records the tail empty string as the final
    element in the slice. A garbage collection happens at this
    point, the collection finds that string before encountering
    the []syntax.Inst data it now inadvertently points to, and the
    []syntax.Inst data is not scanned for the pointers that it
    contains. Each syntax.Inst contains a []rune, those are
    missed, and the backing rune arrays are freed for reuse. When
    the regexp is later executed, the runes being searched for are
    no longer runes at all, and there is no match, even on text
    that should match.
    
    On 64-bit machines the pointer in the []rune inside the
    syntax.Inst is larger (along with a few other pointers),
    pushing the []syntax.Inst backing array into a larger size
    class, avoiding the collision with chan/perm.go's
    inadvertently sized file.
    
    I expect this was more prevalent on OS X than on Linux or
    Windows because those managed to run faster or slower and
    didn't overlap index2.go with chan/perm.go as often. On the
    ARM systems, we only run one errorcheck test at a time, so
    index2 and chan/perm would never overlap.
    
    It is possible that this bug is the root cause of other crashes
    as well. For now we only know it is the cause of the test/run crash.
    
    Many thanks to Dmitriy for help debugging.
    
    Fixes #7344.
    Fixes #7455.
    
    LGTM=r, dvyukov, dave, iant
    R=golang-codereviews, dave, r, dvyukov, delpontej, iant
    CC=golang-codereviews, khr
    https://golang.org/cl/74250043

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

https://github.com/golang/go/commit/54c901cd08d5beb1269af2e73f59d2dec55634e8

元コミット内容

Goランタイムのガベージコレクタにおける空文字列のハンドリングのバグを修正します。GCはヒープの走査に型情報を使用しますが、文字列のデータポインタが指すオブジェクトを訪問済みとマークする際に、そのデータ自体はポインタを含まないためスキャンしません。しかし、s[len(s):]のように空文字列を生成した場合、そのデータポインタは元の文字列データのすぐ後ろ、あるいは次のメモリブロックを指す可能性があります。この場合、GCがその「次のブロック」を誤って文字列データの一部とみなし、ポインタのスキャンをスキップしてしまうと、そのブロック内の他の型のオブジェクトが持つポインタがGCによって見落とされ、早期に解放されてしまう問題が発生します。

この修正は、GCが空文字列を検出した場合、そのデータポインタが指す領域を無視することで行われます。空文字列は内容を持たず、その基底ポインタが再利用されることもないため、この処理は安全です。Go 1.2では、文字列の末尾にヌルバイトが含まれていたため、s[len(s):]が常に文字列の割り当て領域内を指しており、この問題は発生しませんでした。

このバグはtest/run.goにおけるクラッシュの原因となっていました。特に、regexp/syntaxパッケージが[]syntax.Instを割り当て、その隣にstrings.Splitによって生成された空文字列が配置されることで、[]syntax.Inst内の[]runeがGCによってスキャンされずに解放され、その後の正規表現の実行時にクラッシュを引き起こしていました。64ビットマシンではポインタサイズが大きいため、この衝突が回避される傾向がありました。OS XではLinuxやWindowsよりもこのバグが頻繁に発生し、ARMシステムではテストの実行順序により発生しませんでした。

このバグは他のクラッシュの原因である可能性も示唆されています。

変更の背景

この変更の背景には、Goランタイムのガベージコレクタが持つ、メモリ管理の根本的な課題がありました。GoのGCは、ヒープ上のオブジェクトを効率的に管理するために、型情報に基づいてポインタを追跡し、到達可能なオブジェクトをマークします。しかし、特定の条件下でこのメカニズムが誤動作し、本来解放されるべきではないメモリが解放されてしまうという深刻なバグが発見されました。

具体的な問題は、Goの文字列の内部表現と、s[len(s):]のようなスライス操作によって生成される「空文字列」の特性に起因していました。Goの文字列は、内部的にはデータへのポインタと長さ（len）で構成されます。GCは文字列をスキャンする際、そのデータがバイト列でありポインタを含まないため、文字列データが指す領域を「訪問済み」とマークするものの、その内容をさらにスキャンすることはありません。

しかし、s[len(s):]という操作は、元の文字列sの長さがlen(s)である場合、長さ0の新しい文字列を生成します。この新しい空文字列のデータポインタは、元の文字列sのデータの「すぐ後ろ」を指すことになります。もし元の文字列sがメモリブロックの境界ぴったりに割り当てられていた場合、この空文字列のデータポインタは、次のメモリブロックの先頭を指してしまう可能性がありました。

この状況でGCが走ると、GCは空文字列のデータポインタが指す「次のメモリブロック」を、誤って文字列データの一部と認識してしまいます。その結果、そのブロックが本来は別の型のオブジェクト（例えば、ポインタを含む構造体）であったとしても、GCはそのブロックを文字列データとして扱い、内部のポインタをスキャンせずにスキップしてしまいます。これにより、そのブロック内のポインタが指すオブジェクトがGCによって到達不可能と判断され、誤って解放されてしまうという致命的な問題が発生しました。

このバグは、test/run.goというテストスイートでクラッシュとして顕在化しました。特に、regexp/syntaxパッケージが多数の[]syntax.Inst（正規表現の命令を表す構造体のスライス）を割り当て、その隣にstrings.Splitによって生成された空文字列が偶然配置されるという、特定のメモリレイアウトとGCのタイミングが重なることで発生しました。[]syntax.Instは内部に[]rune（ルーンのスライス）を含んでおり、これはポインタです。GCがこの[]syntax.Instをスキャンし損ねると、[]runeが指す実際のルーンデータが解放されてしまい、その後の正規表現の実行時に不正なメモリアクセスが発生し、クラッシュに至っていました。

Go 1.2以前では、文字列の割り当て時に末尾にヌルバイトが含まれていたため、s[len(s):]が指すポインタは常に元の文字列の割り当て領域内を指しており、この問題は発生しませんでした。しかし、このヌルバイトの慣習が変更されたことで、この潜在的なバグが顕在化した形です。

この問題は、Goのメモリ安全性とGCの正確性に関わる重要なバグであり、その修正はランタイムの安定性にとって不可欠でした。

前提知識の解説

このコミットを理解するためには、以下のGo言語およびランタイムに関する前提知識が必要です。

1. Goのガベージコレクタ (GC):

   • Goは自動メモリ管理（ガベージコレクション）を採用しています。開発者は手動でメモリを解放する必要がありません。
   • GoのGCは、主に「マーク＆スイープ」アルゴリズムをベースにしています。これは、プログラムがアクセス可能な（到達可能な）オブジェクトをマークし、マークされなかった（到達不可能な）オブジェクトを「ガベージ」として認識し、解放するプロセスです。
   • GCは、ヒープ上のオブジェクトを走査する際に、そのオブジェクトの「型情報」を利用します。型情報には、そのオブジェクトがどのようなフィールドを持ち、どのフィールドがポインタであるか、どのフィールドがポインタではないか（例：整数、浮動小数点数、バイト列など）が記述されています。GCはポインタフィールドのみを追跡し、到達可能なオブジェクトをマークします。
   • markonly関数（またはそれに相当する内部処理）は、GCが特定のメモリ領域を「訪問済み」とマークするが、その内容をさらにポインタとしてスキャンしないことを意味します。これは、その領域がポインタを含まないことが型情報から明らかである場合（例：文字列のバイトデータ）に適用されます。

2. Goの文字列 (string):

   • Goの文字列はイミュータブル（不変）なバイト列です。
   • 内部的には、文字列はデータへのポインタと長さ（len）の2つの要素で構成されます。データポインタは、文字列の実際のバイトデータが格納されているメモリ上の位置を指します。
   • Goの文字列は、C言語のようなヌル終端文字列ではありません。長さ情報によって文字列の終わりが定義されます。
   • s[len(s):]の挙動: Goのスライス操作s[low:high]は、元のスライスまたは文字列の一部を新しいスライスまたは文字列として返します。s[len(s):]は、lowがlen(s)であり、highが省略されているためlen(s)と同じになります。結果として、長さが0の空文字列が生成されます。この空文字列のデータポインタは、元の文字列sのデータが終了する直後のメモリ位置を指します。

3. Goのスライス (slice):

   • Goのスライスは、配列の一部を参照する動的なビューです。
   • 内部的には、スライスはデータへのポインタ、長さ（len）、容量（cap）の3つの要素で構成されます。
   • 文字列と同様に、スライスもs[len(s):]のような操作で空のスライスを生成できます。この場合も、データポインタは元のスライスのデータのすぐ後ろを指します。GCはスライスを処理する際に、cap（容量）を考慮してポインタのスキャンを行うため、空のスライスであっても問題なく処理されます。

4. メモリ割り当てとアライメント:

   • Goのランタイムは、ヒープ上にオブジェクトを割り当てる際に、特定のサイズクラス（size class）に基づいてメモリを管理します。これは、効率的なメモリ利用とGCのパフォーマンスのために行われます。
   • オブジェクトは、そのサイズに応じて特定のメモリブロックに割り当てられます。この際、メモリのアライメント（特定のバイト境界にデータを配置すること）も考慮されます。
   • あるオブジェクトがメモリブロックの末尾にぴったり収まり、その直後に別のオブジェクトが割り当てられる場合、それらのオブジェクトが隣接して配置される可能性があります。

5. regexp/syntaxパッケージ:

   • Goの標準ライブラリの一部で、正規表現の構文解析と抽象構文木（AST）の構築を担当します。
   • このパッケージは、正規表現の内部表現としてsyntax.Instという構造体のスライス（[]syntax.Inst）を使用します。syntax.Instは、正規表現の各命令を表し、内部に[]rune（ルーンのスライス）などのポインタを含むフィールドを持つことがあります。

これらの知識を組み合わせることで、GCが空文字列のデータポインタを誤って解釈し、隣接する別のオブジェクト（特にポインタを含むオブジェクト）をスキャンし損ねることで、メモリが早期に解放され、結果としてクラッシュが発生するという一連のメカニズムを理解できます。

技術的詳細

このバグの核心は、Goのガベージコレクタが文字列を処理する方法と、空文字列のメモリ表現の間のミスマッチにありました。

GoのGCは、ヒープ上のオブジェクトを走査する際に、そのオブジェクトの型情報に基づいて、どのフィールドがポインタであるかを判断します。文字列の場合、GCは文字列のデータポインタが指す領域をバイト列として認識します。バイト列はポインタを含まないため、GCはその領域を「訪問済み」とマークするものの、その内容をさらにポインタとしてスキャンすることはありません。これは、markonlyという概念で表現されます。markonly(obj)は、objが指すメモリ領域が到達可能であることをマークするが、その領域内のポインタを追跡しないことを意味します。

問題は、s[len(s):]のようにして生成された空文字列にありました。Goの文字列は、データポインタと長さ（len）で構成されます。空文字列の場合、lenは0ですが、データポインタは依然として有効なメモリ位置を指します。このデータポインタは、元の文字列sのデータのすぐ後ろ、つまりsが占めていたメモリ領域の直後を指します。

もし、元の文字列sがメモリブロックの境界にぴったり収まるサイズで割り当てられており、その直後に別のオブジェクト（例えば、[]syntax.Instのようなポインタを含む構造体）が割り当てられていた場合、空文字列のデータポインタは、この「次のメモリブロック」の先頭を指すことになります。

この状況でGCが走ると、GCは空文字列のデータポインタをたどり、それが指す「次のメモリブロック」を文字列データの一部であると誤解します。GCは、そのブロックをmarkonlyで訪問済みとマークしますが、文字列データであると判断したため、そのブロック内のポインタをスキャンしません。しかし、実際にはそのブロックは[]syntax.Instのようなポインタを含む別の型のオブジェクトであったため、そのオブジェクトが持つポインタ（例：[]runeへのポインタ）がGCによって見落とされてしまいます。

結果として、[]syntax.Instが指す[]runeのデータは、GCによって到達不可能と判断され、誤って解放されてしまいます。その後、プログラムが解放されたメモリ領域にアクセスしようとすると、不正なメモリアクセスが発生し、クラッシュや予期せぬ動作（例：正規表現が正しくマッチしない）を引き起こします。

このバグがGo 1.2では発生しなかったのは、Go 1.2以前の文字列割り当てには、文字列の長さには含まれない末尾のヌルバイトが含まれていたためです。このヌルバイトのおかげで、s[len(s):]が指すポインタは常に元の文字列の割り当て領域内（ヌルバイトの位置）を指しており、隣接する別のオブジェクトの領域を指すことはありませんでした。ヌルバイトの慣習が変更されたことで、この問題が顕在化しました。

修正の技術的詳細:

修正は、src/pkg/runtime/mgc0.cのscanblock関数内のGC_STRINGケースで行われました。

変更前は以下のようになっていました。

		case GC_STRING:
			obj = *(void**)(stack_top.b + pc[1]);
			markonly(obj);
			pc += 2;
			continue;

これは、文字列のデータポインタobjが指す領域を無条件にmarkonlyでマークしていました。

変更後は以下のようになりました。

		case GC_STRING:
			stringptr = (String*)(stack_top.b + pc[1]);
			if(stringptr->len != 0) {
				obj = stringptr->str;
				markonly(obj);
			}
			pc += 2;
			continue;

この変更のポイントは、if(stringptr->len != 0)という条件が追加されたことです。

• まず、stack_top.b + pc[1]が指すメモリ位置をString*型にキャストし、stringptrとして取得します。これにより、文字列の内部構造（データポインタstrと長さlen）にアクセスできるようになります。
• 次に、stringptr->len != 0という条件で、文字列の長さが0でない場合にのみ、そのデータポインタstringptr->strが指す領域をmarkonly(obj)でマークするように変更されました。
• もし文字列の長さが0（空文字列）であれば、ifブロック内のmarkonlyは実行されません。これにより、空文字列のデータポインタが指す領域（隣接する可能性のある別のオブジェクト）がGCによって誤って文字列データとして扱われ、スキャンがスキップされることを防ぎます。

空文字列は内容を持たず、そのデータポインタが指す領域はGCにとって意味のあるポインタを含まないため、この修正は安全かつ正確です。スライスの場合も同様の考慮がされており、cap（容量）に基づいて処理が行われるため、空のスライスでは同様の問題は発生しませんでした。

この修正により、GCは空文字列の特殊なケースを正しく処理できるようになり、隣接するオブジェクトのポインタが誤って見落とされ、早期に解放されるというバグが解消されました。

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

このコミットにおけるコアとなるコードの変更箇所は以下の2ファイルです。

1. src/pkg/runtime/mgc0.c:

   • このファイルはGoランタイムのガベージコレクタの主要な部分を実装しています。
   • 変更はscanblock関数内、特にGC_STRINGというケース（文字列型を処理する部分）にあります。
   • 追加された行:

     +	String *stringptr;
     

     （scanblock関数のローカル変数宣言部分にString型ポインタstringptrが追加されました。）
   • 変更された行:

     --- a/src/pkg/runtime/mgc0.c
     +++ b/src/pkg/runtime/mgc0.c
     @@ -948,8 +949,11 @@ scanblock(Workbuf *wbuf, bool keepworking)
      
      		case GC_STRING:
     -			obj = *(void**)(stack_top.b + pc[1]);
     -			markonly(obj);
     +			stringptr = (String*)(stack_top.b + pc[1]);
     +			if(stringptr->len != 0) {
     +				obj = stringptr->str;
     +				markonly(obj);
     +			}
      			pc += 2;
      			continue;
     

     （GC_STRINGケースのロジックが変更され、文字列の長さが0でない場合にのみmarkonlyが呼び出されるようになりました。）

2. test/gcstring.go:

   • このファイルは新しく追加されたテストファイルです。
   • 目的は、s[len(s):]のようにして生成された空文字列がガベージコレクタを混乱させないことを検証することです。
   • main関数では、setup関数を呼び出した後、複数回GCを実行し、time.Sleepを挟んでGCが正しく動作することを確認しています。
   • setup関数では、Tという構造体（ポインタとパディングを持つ）と、bufという128バイトのバイトスライスを定義しています。
   • ループ内で10000回、string(buf)で文字列を生成し、その空文字列スライスs[len(s):]をthingsというグローバルな[]interface{}スライスに追加しています。
   • 同時に、T型のインスタンスを生成し、そのptrフィールドにnew(*int)で新しいポインタを割り当て、runtime.SetFinalizerを使って、この*intが早期に解放された場合にパニックを発生させるファイナライザを設定しています。
   • このテストは、空文字列のデータポインタが指す領域に、T構造体のようなポインタを含むオブジェクトが配置された場合に、GCがそのポインタを誤って解放しないことを確認するためのものです。ファイナライザがトリガーされなければ、GCが正しく動作していることを示します。

これらの変更は、GoランタイムのGCのコアロジックに直接影響を与え、同時にその修正を検証するための具体的なテストケースを提供しています。

コアとなるコードの解説

このコミットのコアとなるコードの変更は、src/pkg/runtime/mgc0.cファイル内のscanblock関数にあります。この関数は、Goのガベージコレクタがヒープ上のオブジェクトを走査し、ポインタを追跡する主要なルーチンの一つです。

変更された部分は、switch文の中のcase GC_STRING:ブロックです。これは、GCが現在処理しているオブジェクトのフィールドが文字列型であると判断した場合に実行されるロジックです。

変更前のコード:

		case GC_STRING:
			obj = *(void**)(stack_top.b + pc[1]);
			markonly(obj);
			pc += 2;
			continue;

• stack_top.b + pc[1]は、現在のスタックフレームまたはオブジェクト内の、文字列のデータポインタが格納されているメモリ位置を指します。
• *(void**)(...)は、そのメモリ位置からvoid*（汎用ポインタ）として文字列のデータポインタを読み取ります。このポインタがobjに代入されます。
• markonly(obj);は、objが指すメモリ領域（つまり、文字列の実際のバイトデータが格納されている場所）を「到達可能」としてマークします。しかし、markonlyの性質上、この領域はポインタを含まないバイト列であるとGCが認識しているため、その内容をさらにポインタとしてスキャンすることはありません。

この変更前のロジックでは、文字列の長さが0（空文字列）であっても、そのデータポインタが指す領域を無条件にmarkonlyでマークしていました。前述の通り、空文字列のデータポインタは、元の文字列の直後のメモリ領域を指す可能性があり、そこに別のオブジェクト（ポインタを含む）が存在すると、そのオブジェクトが誤って文字列データとして扱われ、ポインタのスキャンがスキップされるという問題がありました。

変更後のコード:

		case GC_STRING:
			stringptr = (String*)(stack_top.b + pc[1]);
			if(stringptr->len != 0) {
				obj = stringptr->str;
				markonly(obj);
			}
			pc += 2;
			continue;

• stringptr = (String*)(stack_top.b + pc[1]);：
  • 変更前と同様に、文字列のデータが格納されているメモリ位置を指すポインタを取得しますが、今回はそれをString*型にキャストしています。
  • String型はGoランタイム内部で文字列の構造を定義しており、通常はデータポインタ（str）と長さ（len）のフィールドを持ちます。これにより、GCは文字列の内部構造に直接アクセスできるようになります。
• if(stringptr->len != 0) { ... }：
  • このif文が追加された最も重要な変更点です。
  • GCは、stringptrが指す文字列のlenフィールドをチェックします。
  • もしlenが0でない（つまり、空文字列ではない）場合のみ、以前と同様にobj = stringptr->str;でデータポインタを取得し、markonly(obj);を呼び出してその領域をマークします。
• もしstringptr->lenが0（空文字列）の場合、ifブロック内のmarkonlyは実行されません。これにより、空文字列のデータポインタが指すメモリ領域（隣接する可能性のある別のオブジェクト）がGCによって誤って文字列データとして扱われることがなくなります。空文字列は内容を持たず、そのデータポインタが指す領域はGCにとって追跡すべきポインタを含まないため、この処理は正しく、安全です。

この修正により、GCは空文字列の特殊なケースを正しく識別し、そのデータポインタが指す領域を不必要にマークしたり、隣接するオブジェクトのスキャンを誤ってスキップしたりすることを防ぎます。これにより、メモリの誤解放が解消され、ランタイムの安定性が向上しました。

関連リンク

• Go Issue #7344: コミットメッセージで言及されていますが、直接的な検索結果は見つかりませんでした。
• Go Issue #7455: コミットメッセージで言及されていますが、直接的な検索結果は見つかりませんでした。
• Go CL 74250043: このコミットに対応するGoのコードレビューリンクです。
  • https://golang.org/cl/74250043

参考にした情報源リンク

• Goのコミットメッセージ: 本解説の主要な情報源です。コミットの意図、背景、技術的詳細、およびバグの具体的な発生例が詳細に記述されています。
• Goのソースコード: src/pkg/runtime/mgc0.cおよびtest/gcstring.goの実際のコード変更が、修正内容とテストケースの理解に不可欠でした。
• Go言語の公式ドキュメント: Goの文字列、スライス、ガベージコレクションに関する一般的な知識は、Goの公式ドキュメントやブログ記事から得られます。
  • Go言語の仕様
  • Goのメモリモデル
  • Goのブログ (特にGCに関する記事)
• GoのIssueトラッカー: コミットメッセージで参照されているIssue番号（#7344, #7455）について、Goの公式Issueトラッカー（GitHubまたは旧Google Code）で検索を試みましたが、直接的な一致は見つかりませんでした。これは、Issueが非常に古い、または別のリポジトリに属している可能性を示唆しています。
• Goのガベージコレクションに関する技術記事: GoのGCの内部動作に関する一般的な理解を深めるために、コミュニティの技術記事や解説も参考にしました。