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

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

コミット

このコミットは、Goランタイムの386アーキテクチャにおけるuint64（64ビット符号なし整数）の除算処理に存在したバグを修正するものです。具体的には、64ビットと32ビットの乗算結果が96ビットになる可能性があるにもかかわらず、その上位32ビットが適切に考慮されていなかったために、除算の最適化パスが誤った判断を下すことがあった問題を解決します。

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

https://github.com/golang/go/commit/70138a2108d81a771a180af93edbc007d2a5c8b2

元コミット内容

runtime: fix uint64 division on 386

The uint64 divide function calls _mul64x32 to do a 64x32-bit multiply
and then compares the result against the 64-bit numerator.
If the result is bigger than the numerator, must use the slow path.

Unfortunately, the 64x32 produces a 96-bit product, and only the
low 64 bits were being used in the comparison. Return all 96 bits,
the bottom 64 via the original uint64* pointer, and the top 32
as the function's return value.

Fixes 386 build (broken by ARM division tests).

R=golang-dev, iant
CC=golang-dev
https://golang.org/cl/13722044

変更の背景

Goランタイムのuint64除算関数は、パフォーマンス最適化のために、まず64ビット数と32ビット数の乗算（_mul64x32）を用いて商を推定する高速パスを持っています。この推定結果（乗算結果）が元の被除数（numerator）よりも大きい場合、推定が過剰であったと判断し、より正確だが低速な除算アルゴリズム（slow path）にフォールバックする必要がありました。

しかし、386アーキテクチャ向けの_mul64x32関数は、64ビットと32ビットの乗算を行う際に、最大で96ビットの積を生成する可能性があります（64ビットの数 * 32ビットの数 = 96ビットの積）。このバグは、_mul64x32が生成する96ビットの積のうち、下位64ビットしか比較に使用されていなかったことに起因します。その結果、上位32ビットに値が存在する場合（つまり、積が64ビットの範囲を超えている場合）でも、その情報が失われ、誤って積が被除数より小さいと判断され、高速パスが選択されてしまう可能性がありました。

この問題は、ARMアーキテクチャ向けの除算テストによって386ビルドの不具合として顕在化しました。これは、異なるアーキテクチャのテストが、特定のアーキテクチャの実装における潜在的な問題を浮き彫りにする良い例です。

前提知識の解説

  • 386アーキテクチャ: Intel 80386プロセッサに代表される32ビットアーキテクチャ。Go言語のランタイムは、様々なアーキテクチャに対応するために、アセンブリ言語やC言語で書かれた低レベルなコードを含んでいます。
  • uint64: 64ビットの符号なし整数型。Go言語における数値型の一つで、非常に大きな正の整数を扱うことができます。
  • 除算の最適化: コンピュータにおける除算は、乗算や加算に比べて一般的にコストの高い演算です。そのため、多くのシステムでは、特定の条件下で高速な除算アルゴリズムや近似アルゴリズムを使用し、結果が正確でない場合やオーバーフローの可能性がある場合にのみ、より複雑で正確な（しかし低速な）アルゴリズムにフォールバックする最適化が行われます。
  • 多倍長乗算: 32ビットプロセッサで64ビット数やそれ以上の大きな数を扱う場合、通常のCPU命令では一度に計算できないため、複数のレジスタやメモリを組み合わせて計算する「多倍長演算」が必要になります。このコミットで言及されている「64x32-bit multiply」は、64ビットの被乗数と32ビットの乗数を掛け合わせる操作であり、その結果は最大で96ビット（64+32）になる可能性があります。
    • 例えば、0xFFFFFFFFFFFFFFFF (64ビット最大値) * 0xFFFFFFFF (32ビット最大値) は、約 2^64 * 2^32 = 2^96 に近い値になります。
  • アセンブリ言語: 特定のCPUアーキテクチャに特化した低レベルなプログラミング言語。Goランタイムのようなシステムプログラミングでは、パフォーマンスが重要となる部分や、ハードウェアに直接アクセスする必要がある部分でアセンブリ言語が使用されます。
    • MOVL: 32ビット値を移動する命令 (Move Long)。
    • MULL: 符号なし乗算命令。32ビットオペランドの場合、AXとオペランドを乗算し、結果をDX:AX（上位32ビットがDX、下位32ビットがAX）に格納します。
    • ADDL: 32ビット加算命令。
    • ADCL: キャリー付き32ビット加算命令 (Add with Carry Long)。前の演算で発生したキャリーフラグを考慮して加算を行います。多倍長演算で桁上がりを伝播させる際に重要です。
    • TEXT: アセンブリコードの関数定義を示すディレクティブ。
    • NOSPLIT: スタックフレームの分割を禁止するディレクティブ。
    • SB: Static Base。グローバルシンボルや外部シンボルを参照する際に使われる疑似レジスタ。
    • FP: Frame Pointer。関数の引数やローカル変数にアクセスする際に使われる疑似レジスタ。
  • Vlong構造体: GoランタイムのCコードで64ビット整数を表現するために使われる構造体で、通常はstruct { uint32 lo; uint32 hi; }のように、下位32ビットと上位32ビットに分割して64ビットを表現します。

技術的詳細

この修正の核心は、_mul64by32という64ビットと32ビットの乗算を行うアセンブリ関数が、その結果として生成される96ビットの積を完全に返すように変更された点にあります。

元々、_mul64by32は、96ビットの積のうち下位64ビットをポインタ経由でuint64型（Vlong構造体）に格納し、上位32ビットは破棄していました。しかし、この上位32ビットがゼロでない場合、積は64ビットの範囲を超えており、除算の比較ロジックにおいて重要な情報となります。

修正では、以下の変更が行われました。

  1. _mul64by32アセンブリ関数の変更 (src/pkg/runtime/vlop_386.s):

    • _mul64by32関数は、a (64ビット) と b (32ビット) の乗算を行います。
    • MULL b+12(FP) 命令は、AXレジスタ（aの上位32ビット）とb（32ビット）を乗算し、結果をDX:AXに格納します。このとき、DXには上位32ビット、AXには下位32ビットが入ります。
    • 修正前は、このDXレジスタの値が適切に処理されていませんでした。
    • 修正後、ADCL $0, DXが追加されました。これは、前のMULL命令で発生したキャリー（桁上がり）をDXに加算することで、96ビット積の最上位32ビットを正確に計算します。
    • そして、MOVL DX, AXによって、この最上位32ビットがAXレジスタに移動され、関数の戻り値として使用されるようになりました。これにより、_mul64by32は下位64ビットをポインタ経由で、上位32ビットを戻り値として返すようになりました。

  2. _mul64by32関数のC言語プロトタイプと呼び出し箇所の変更 (src/pkg/runtime/vlrt_386.c):

    • _mul64by32関数のプロトタイプがvoidからintに変更され、上位32ビットの戻り値を受け取れるようになりました。
    • 除算ロジック内の条件分岐if(x.hi > num.hi || (x.hi == num.hi && x.lo > num.lo))が、if(_mul64by32(&x, den, n) || x.hi > num.hi || (x.hi == num.hi && x.lo > num.lo))に変更されました。
    • これにより、_mul64by32の戻り値（96ビット積の上位32ビット）が直接if文の条件として評価されるようになりました。もしこの戻り値が非ゼロであれば、それは積が64ビットの範囲を超えていることを意味し、直ちに「slow path」へ移行する判断が下されます。これにより、積の全体（96ビット）が比較に考慮されるようになり、誤った高速パスの選択が防止されます。

この修正により、386アーキテクチャにおけるuint64除算の正確性が保証され、特に大きな数値の除算において発生しうる潜在的なバグが解消されました。

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

src/pkg/runtime/vlop_386.s

--- a/src/pkg/runtime/vlop_386.s
+++ b/src/pkg/runtime/vlop_386.s
@@ -29,6 +29,8 @@
  * C runtime for 64-bit divide.
  */
 
+// _mul64x32(r *uint64, a uint64, b uint32)
+// sets *r = low 64 bits of 96-bit product a*b; returns high 32 bits.
 TEXT _mul64by32(SB), NOSPLIT, $0
 	MOVL	r+0(FP), CX
 	MOVL	a+4(FP), AX
@@ -38,7 +40,9 @@ TEXT _mul64by32(SB), NOSPLIT, $0
 	MOVL	a+8(FP), AX
 	MULL	b+12(FP)
 	ADDL	AX, BX
+	ADCL	$0, DX
 	MOVL	BX, 4(CX)
+	MOVL	DX, AX
 	RET
 
 TEXT _div64by32(SB), NOSPLIT, $0

src/pkg/runtime/vlrt_386.c

--- a/src/pkg/runtime/vlrt_386.c
+++ b/src/pkg/runtime/vlrt_386.c
@@ -147,7 +147,7 @@ _v2f(Vlong x)\n }\n \n ulong	_div64by32(Vlong, ulong, ulong*);\n-void	_mul64by32(Vlong*, Vlong, ulong);\n+int	_mul64by32(Vlong*, Vlong, ulong);\n \n static void\n slowdodiv(Vlong num, Vlong den, Vlong *q, Vlong *r)\n@@ -232,8 +232,7 @@ dodiv(Vlong num, Vlong den, Vlong *qp, Vlong *rp)\n \tif(den.hi != 0){\n \t\tq.hi = 0;\n \t\tn = num.hi/den.hi;\n-\t\t_mul64by32(&x, den, n);\n-\t\tif(x.hi > num.hi || (x.hi == num.hi && x.lo > num.lo))\n+\t\tif(_mul64by32(&x, den, n) || x.hi > num.hi || (x.hi == num.hi && x.lo > num.lo))\n \t\t\tslowdodiv(num, den, &q, &r);\n \t\telse {\n \t\t\tq.lo = n;\n```

## コアとなるコードの解説

### `src/pkg/runtime/vlop_386.s` の変更点

*   **`_mul64by32`関数のコメント更新**:
    *   `// _mul64x32(r *uint64, a uint64, b uint32)`
    *   `// sets *r = low 64 bits of 96-bit product a*b; returns high 32 bits.`
    *   このコメントは、関数がポインタ`r`を通じて積の下位64ビットを返し、関数の戻り値として積の上位32ビットを返すという新しい動作を明確に示しています。
*   **`ADCL $0, DX` の追加**:
    *   `MULL b+12(FP)`命令は、`a`の上位32ビットと`b`を乗算し、その結果を`DX:AX`に格納します。この乗算で桁上がりが発生した場合、そのキャリーフラグがセットされます。
    *   `ADCL $0, DX`は、`DX`レジスタに0を加算し、同時にキャリーフラグの値も加算します。これにより、96ビット積の最上位32ビットが正確に`DX`に計算されます。これは、多倍長乗算において、前の部分積からの桁上がりを次の部分積に伝播させるための標準的な手法です。
*   **`MOVL DX, AX` の追加**:
    *   `DX`レジスタに格納された96ビット積の最上位32ビットを、関数の戻り値として使用される`AX`レジスタに移動します。これにより、C言語側でこの上位32ビットの値を受け取ることが可能になります。

これらの変更により、`_mul64by32`は、64ビットと32ビットの乗算結果である96ビットの積を完全に計算し、その上位32ビットを関数の戻り値として、下位64ビットをポインタ経由で呼び出し元に渡すようになりました。

### `src/pkg/runtime/vlrt_386.c` の変更点

*   **`_mul64by32`関数のプロトタイプ変更**:
    *   `void _mul64by32(Vlong*, Vlong, ulong);` から `int _mul64by32(Vlong*, Vlong, ulong);` へ変更。
    *   これにより、Cコンパイラは`_mul64by32`が`int`型の値を返すことを認識し、その戻り値を適切に処理できるようになります。
*   **除算ロジック内の条件分岐の変更**:
    *   `if(x.hi > num.hi || (x.hi == num.hi && x.lo > num.lo))`
    *   から
    *   `if(_mul64by32(&x, den, n) || x.hi > num.hi || (x.hi == num.hi && x.lo > num.lo))` へ変更。
    *   この変更が最も重要です。`_mul64by32(&x, den, n)`の呼び出しが`if`文の条件式の先頭に追加されました。
    *   `_mul64by32`は、`x`（`Vlong`型、つまり64ビット）に積の下位64ビットを格納し、同時に積の上位32ビットを`int`型の戻り値として返します。
    *   C言語では、非ゼロの値は真と評価されます。したがって、`_mul64by32`が非ゼロの値を返した場合（つまり、96ビット積の上位32ビットが非ゼロであった場合）、それは積が64ビットの範囲を超えており、被除数よりも大きい可能性があることを意味します。この場合、`||`（論理OR）演算子の短絡評価により、後続の比較は行われずに`if`条件が真となり、直ちに`slowdodiv`（低速パス）が呼び出されます。
    *   これにより、積が96ビットに及ぶ場合でも、その全体が比較ロジックに適切に反映されるようになり、除算の正確性が向上しました。

## 関連リンク

*   Go言語のランタイムソースコード: [https://github.com/golang/go/tree/master/src/runtime](https://github.com/golang/go/tree/master/src/runtime)
*   Go言語の`uint64`型に関するドキュメント: [https://pkg.go.dev/builtin#uint64](https://pkg.go.dev/builtin#uint64)

## 参考にした情報源リンク

*   Go言語のコミット履歴: [https://github.com/golang/go/commits/master](https://github.com/golang/go/commits/master)
*   Intel 80386 Programmer's Reference Manual (アセンブリ命令の詳細): [https://www.intel.com/content/www/us/en/docs/programmable/641009/1-0/intel-386-programmer-s-reference-manual.html](https://www.intel.com/content/www/us/en/docs/programmable/641009/1-0/intel-386-programmer-s-reference-manual.html) (一般的な情報源として)
*   多倍長演算に関する一般的な情報 (例: Wikipediaなど)