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

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

このコミットは、Goランタイム内の並列処理ループ (runtime/parfor.c) における整数オーバーフローのバグを修正するものです。具体的には、ループの終了条件の評価方法に潜在的な問題があり、end の値が 0 の場合に end-1 が非常に大きな数（符号なし整数の最大値）となり、予期せぬ動作を引き起こす可能性がありました。この問題は、新しいスケジューラが導入された際に顕在化したと報告されています。

コミット

commit 45636db01bdf4bd50426067af72afbde3900ceb9
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Fri Feb 8 19:05:19 2013 +0400

    runtime: fix integer overflow
    The problem happens when end=0, then end-1 is very big number.
    Observed with the new scheduler.
    
    R=golang-dev, iant
    CC=golang-dev
    https://golang.org/cl/7307073

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

https://github.com/golang/go/commit/45636db01bdf4bd50426067af72afbde3900ceb9

元コミット内容

このコミットは、Go言語のランタイムにおける整数オーバーフローの修正を目的としています。問題は、end 変数が 0 の場合に end-1 の計算が行われると、符号なし整数（uint32）の特性により、end-1 が非常に大きな値（uint32 の最大値である 0xFFFFFFFF）になることにありました。この予期せぬ大きな値が比較条件に影響を与え、並列処理のループが正しく終了しない、あるいは無限ループに陥るなどのバグを引き起こす可能性がありました。この問題は、Goの新しいスケジューラが導入された際に、その動作パターンによって顕在化したとされています。

変更の背景

この変更の背景には、Go言語のランタイムにおける並列処理の正確性と堅牢性の確保があります。特に、コミットメッセージに「Observed with the new scheduler.」とあるように、Goのスケジューラが進化する過程で、既存のコードベースに潜在していたバグが露呈したと考えられます。

Goのスケジューラは、Goルーチン（軽量スレッド）の実行を管理し、マルチコアプロセッサを効率的に利用するための重要なコンポーネントです。2013年頃は、Go 1.1のリリースに向けてスケジューラの改善が活発に行われていた時期であり、特にM:Nスケジューラ（M個のGoルーチンをN個のOSスレッドにマッピングする）の導入と最適化が進められていました。

新しいスケジューラは、Goルーチンのスケジューリングパターンやコンテキストスイッチの頻度を変更する可能性があり、これにより、これまで表面化しなかった特定のコードパスやエッジケースが実行されるようになりました。今回の整数オーバーフローもその一つで、end が 0 になるという特定の条件下での end-1 の計算が、新しいスケジューラの動作と組み合わさることで、問題を引き起こすようになったと推測されます。

この修正は、Goランタイムの安定性を向上させ、新しいスケジューラの導入による潜在的な問題を解消するために不可欠でした。

前提知識の解説

1. 整数オーバーフロー (Integer Overflow)

整数オーバーフローとは、数値計算の結果が、その数値を格納するために割り当てられたデータ型で表現できる最大値（または最小値）を超えてしまう現象です。

  • 符号なし整数 (Unsigned Integer): 負の数を表現できず、0以上の値のみを扱います。例えば、uint32 は0から2^32-1までの値を表現できます。符号なし整数でアンダーフロー（0を下回る計算）が発生すると、通常は最大値にラップアラウンドします。

    • 例: uint32 型の変数 x が 0 の場合、x - 1 は 0xFFFFFFFF (4,294,967,295) になります。これは、0 から 1 を引くと、表現可能な最小値である 0 を下回り、その結果、最大値に「巻き戻る」ためです。

  • 符号付き整数 (Signed Integer): 正と負の両方の数を表現できます。オーバーフローやアンダーフローが発生すると、通常は符号が反転したり、予期せぬ値になったりします。

今回のコミットでは、uint32 型の end 変数が 0 の場合に end-1 を計算すると、符号なし整数の特性によりオーバーフロー（実際にはアンダーフローが最大値へのラップアラウンドを引き起こす）が発生し、非常に大きな値になることが問題でした。

2. Goランタイム (Go Runtime)

Goランタイムは、Goプログラムの実行を管理する低レベルのシステムです。これには以下の主要なコンポーネントが含まれます。

  • ガベージコレクタ (Garbage Collector): 不要になったメモリを自動的に解放します。
  • スケジューラ (Scheduler): Goルーチン（Goの軽量スレッド）の実行を管理し、複数のGoルーチンを限られた数のOSスレッドに効率的にマッピングします。
  • メモリ管理 (Memory Management): メモリの割り当てと解放を行います。
  • プリミティブな同期メカニズム (Primitive Synchronization Mechanisms): ミューテックスやチャネルなどの同期メカニズムを提供します。

src/pkg/runtime/parfor.c は、Goランタイムの一部であり、並列処理のための共通のループ構造を提供していると考えられます。C言語で書かれているのは、Goランタイムの初期部分やパフォーマンスが非常に重要な部分がCやアセンブリで実装されていたためです。

3. Goスケジューラ (Go Scheduler)

Goスケジューラは、Goプログラムの並行性を実現するGoランタイムの心臓部です。その主な役割は、GoルーチンをOSスレッドに効率的にマッピングし、マルチコアプロセッサを最大限に活用することです。

  • Goroutine (Goルーチン): Go言語の並行処理の単位であり、非常に軽量なスレッドのようなものです。数百万のGoルーチンを同時に実行することも可能です。
  • M (Machine): OSスレッドを表します。
  • P (Processor): Goルーチンを実行するための論理プロセッサを表します。各PはローカルなGoルーチンキューを持ち、MがPに割り当てられてGoルーチンを実行します。
  • G (Goroutine): Goルーチン自体を表します。

Goスケジューラは、G-M-Pモデルに基づいて動作します。Go 1.1では、このスケジューラに大きな改善が加えられ、より効率的なGoルーチンのスケジューリングと、より良いスループットが実現されました。この改善が、今回のバグを顕在化させた要因の一つと考えられます。

技術的詳細

このコミットは、src/pkg/runtime/parfor.c ファイル内の並列処理ループの終了条件の評価ロジックを修正しています。

元のコードでは、ループの終了条件を if(begin >= end-1) と評価していました。ここで begin と end は uint32 型の変数です。

問題は、end が 0 の場合に発生します。 end が 0 の場合、end-1 は 0 - 1 となり、uint32 型の特性により符号なし整数の最大値 0xFFFFFFFF (4,294,967,295) にラップアラウンドします。 この結果、begin >= 0xFFFFFFFF という比較が行われることになります。通常、begin は 0xFFFFFFFF よりもはるかに小さい値であるため、この条件はほとんどの場合 false となり、ループが終了すべきときに終了しない、あるいは無限ループに陥る可能性がありました。

新しいコードでは、この条件を if(begin+1 >= end) に変更しています。

この変更により、end が 0 の場合でも安全に評価できるようになります。

  • end が 0 の場合: begin+1 >= 0 となります。begin は uint32 型なので常に 0 以上であり、begin+1 も常に 0 以上です。したがって、この条件は常に true となり、begin = end = 0; break; が実行され、ループが正しく終了します。
  • end が 0 以外の場合: begin+1 >= end は、元の begin >= end-1 と論理的に同等です（ただし、end-1 がオーバーフローしない限り）。例えば、end=5 の場合、元の条件は begin >= 4、新しい条件は begin+1 >= 5、つまり begin >= 4 となり、同じ意味になります。

この修正は、符号なし整数の算術演算におけるオーバーフロー/アンダーフローの挙動を考慮し、より堅牢な比較ロジックを導入することで、ランタイムの安定性を向上させています。

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

--- a/src/pkg/runtime/parfor.c
+++ b/src/pkg/runtime/parfor.c
@@ -145,7 +145,7 @@ runtime·parfordo(ParFor *desc)
 				// See if it has any work.
 				begin = (uint32)pos;
 				end = (uint32)(pos>>32);
-				if(begin >= end-1) {
+				if(begin+1 >= end) {
 					begin = end = 0;
 					break;
 				}

コアとなるコードの解説

変更された行は src/pkg/runtime/parfor.c の146行目です。

  • - if(begin >= end-1) {:

    • これは元のコードの条件式です。
    • begin と end は uint32 型（符号なし32ビット整数）です。
    • この問題は、end が 0 の場合に発生します。end-1 は 0 - 1 となり、uint32 の範囲で表現できないため、符号なし整数の特性により最大値 0xFFFFFFFF にラップアラウンドします。
    • 結果として、begin >= 0xFFFFFFFF という比較が行われます。begin がこの巨大な値に達することは稀であるため、ループが終了すべき条件が満たされず、無限ループや予期せぬ動作につながる可能性がありました。

  • + if(begin+1 >= end) {:

    • これは修正後のコードの条件式です。
    • この変更により、end が 0 の場合でも安全に処理できるようになります。
    • end が 0 の場合、条件は begin+1 >= 0 となります。begin は uint32 なので常に非負であり、begin+1 も常に非負です。したがって、この条件は常に真となり、begin = end = 0; break; が実行され、ループが正しく終了します。
    • end が 0 以外の場合、begin+1 >= end は begin >= end-1 と論理的に同等であり、意図した比較が正しく行われます。例えば、end が 1 の場合、元の条件は begin >= 0、新しい条件は begin+1 >= 1 (つまり begin >= 0) となり、同じ意味になります。
    • この修正は、end-1 の計算で発生する可能性のある符号なし整数のオーバーフローを回避し、より堅牢な終了条件のチェックを実現しています。

この修正は、Goランタイムの並列処理における潜在的なバグを解消し、特に新しいスケジューラのような異なる実行パターンが導入された際に、プログラムが安定して動作することを保証するために重要でした。

関連リンク

参考にした情報源リンク