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

このコミットは、Go言語の標準ライブラリ math/big パッケージにおける Rand メソッドのバグ修正に関するものです。具体的には、Rand メソッドのレシーバと引数が同じ big.Int オブジェクトである場合に発生していたハングアップ（無限ループ）の問題を解決します。

コミット

commit fc78c5aa000a1b7c5a2e894ce1b511385b280ccd
Author: Robert Griesemer <gri@golang.org>
Date:   Thu Dec 22 14:15:41 2011 -0800

    math/big: Rand shouldn't hang if argument is also receiver.

    Fixes #2607.

    R=rsc
    CC=golang-dev
    https://golang.org/cl/5489109

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

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

元コミット内容

math/big: Rand shouldn't hang if argument is also receiver.

このコミットは、math/big パッケージの Rand メソッドが、その引数（乱数の上限）がレシーバ（結果を格納するオブジェクト）と同一である場合にハングアップする問題を修正します。

変更の背景

Go言語の math/big パッケージは、任意精度の整数、有理数、浮動小数点数を扱うための機能を提供します。big.Int 型は、非常に大きな整数を扱うために使用されます。big.Int の Rand メソッドは、指定された上限未満の非負の乱数を生成するために使用されます。

このコミットが修正する問題は、GoのIssue #2607として報告されました。報告された問題は、big.Int の Rand メソッドを呼び出す際に、乱数を生成する対象の big.Int オブジェクト（レシーバ）と、乱数の上限を指定する big.Int オブジェクト（引数）が、メモリ上で同じインスタンスを指している場合に、メソッドが無限ループに陥り、プログラムがハングアップするというものでした。

このような状況は、例えば n.Rand(randSource, n) のように、n という big.Int 変数に対して、その Rand メソッドを呼び出し、かつ上限値としても n 自身を渡した場合に発生します。math/big パッケージの内部実装では、効率のために可能な限り既存のメモリを再利用しようとします。しかし、この再利用ロジックが、レシーバと引数がエイリアス（同じメモリを指すこと）であるケースを適切に処理できていなかったため、競合状態や不正なメモリ操作が発生し、結果としてハングアップを引き起こしていました。

前提知識の解説

• math/big パッケージ: Go言語の標準ライブラリの一部で、任意精度の数値（整数、有理数、浮動小数点数）を扱うためのパッケージです。通常の int や float64 では表現できないような非常に大きな数や、高い精度が求められる計算に使用されます。
• big.Int 型: math/big パッケージで提供される、任意精度の整数型です。内部的には、整数の各桁を Word 型（通常は uint または uint64）のスライスとして保持します。
• レシーバと引数のエイリアシング: プログラミングにおいて、関数やメソッドのレシーバ（メソッドが呼び出されるオブジェクト）と引数が、メモリ上で同じ基盤となるデータ構造を共有している状態を指します。Go言語では、スライスやマップ、チャネルなどの参照型を扱う際に、このエイリアシングに注意が必要です。特に、メソッドがレシーバや引数の内部データを変更する場合、エイリアシングによって予期せぬ副作用が発生する可能性があります。
• nat 型: math/big パッケージの内部で使われる型で、非負の整数（natural number）を表すために Word のスライスとして定義されています。big.Int は、この nat 型を符号付き整数としてラップしたものです。
• z.make(len(limit)): nat 型のメソッドで、指定された長さのスライスを確保または再利用して nat オブジェクトを初期化します。既存の z の容量が十分であれば、そのメモリを再利用し、そうでなければ新しいメモリを割り当てます。
• rand.Rand: math/rand パッケージの乱数ジェネレータです。big.Int.Rand メソッドはこの乱数ジェネレータを引数として受け取ります。

技術的詳細

問題の核心は、math/big パッケージの内部で、big.Int.Rand メソッドが最終的に呼び出す (z nat) random 関数にありました。この関数は、乱数を生成して z に格納する役割を担っています。

元のコードでは、z (レシーバの nat 表現) のメモリを limit (上限値の nat 表現) の長さに合わせて z.make(len(limit)) で初期化していました。ここで、もし z と limit が同じ基盤となるスライスを共有している場合（エイリアシングが発生している場合）、z.make が z の内部スライスを再割り当てまたは変更する際に、limit の内容も同時に変更してしまう可能性がありました。

random 関数は、limit の値に基づいて乱数を生成します。しかし、z.make が limit の内容を破壊的に変更してしまうと、limit の長さや値が不正になり、その後の乱数生成ロジック（特に for ループ内で limit のビット長や値を参照する部分）が誤動作し、結果として無限ループに陥るという現象が発生していました。

修正は、このエイリアシングの問題を明示的に検出して対処することにあります。具体的には、random 関数の冒頭に以下のチェックが追加されました。

if alias(z, limit) {
    z = nil // z is an alias for limit - cannot reuse
}

• alias(z, limit): この内部関数（コミットのdiffには含まれていませんが、math/big パッケージの他の場所で定義されていると推測されます）は、2つの nat 型のスライス z と limit がメモリ上でオーバーラップしているかどうかをチェックします。つまり、同じ基盤となる配列を共有しているかどうかを判断します。
• z = nil: もし z と limit がエイリアスであると判断された場合、z を nil に設定します。これにより、次の z.make(len(limit)) が呼び出された際に、z が既存のメモリを再利用しようとせず、必ず新しいメモリを割り当てるようになります。新しいメモリが割り当てられることで、limit の内容が z.make によって意図せず変更されることがなくなり、安全に乱数生成処理を進めることができるようになります。

この修正により、レシーバと引数がエイリアスである場合でも、limit の値が乱数生成処理中に破壊されることがなくなり、ハングアップの問題が解消されました。

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

変更は主に2つのファイルで行われています。

1. src/pkg/math/big/int_test.go:

   • math/rand パッケージのインポートが追加されました。
   • TestIssue2607 という新しいテスト関数が追加されました。このテストは、問題が修正されたことを確認するために、ハングアップを引き起こしていた特定のコードシーケンスを実行します。

2. src/pkg/math/big/nat.go:

   • random 関数（nat 型の内部メソッド）の冒頭に、レシーバ z と引数 limit のエイリアシングをチェックし、必要に応じて z を nil に設定するロジックが追加されました。

--- a/src/pkg/math/big/int_test.go
+++ b/src/pkg/math/big/int_test.go
@@ -9,6 +9,7 @@ import (
 	"encoding/gob"
 	"encoding/hex"
 	"fmt"
+	"math/rand"
 	"testing"
 	"testing/quick"
 )
@@ -1405,3 +1406,9 @@ func TestIntGobEncoding(t *testing.T) {
 		}
 	}
 }
+
+func TestIssue2607(t *testing.T) {
+	// This code sequence used to hang.
+	n := NewInt(10)
+	n.Rand(rand.New(rand.NewSource(9)), n)
+}
diff --git a/src/pkg/math/big/nat.go b/src/pkg/math/big/nat.go
index ead1a881a6..69681ae2d6 100644
--- a/src/pkg/math/big/nat.go
+++ b/src/pkg/math/big/nat.go
@@ -1196,12 +1196,16 @@ func (x nat) powersOfTwoDecompose() (q nat, k int) {
 // random creates a random integer in [0..limit), using the space in z if
 // possible. n is the bit length of limit.
 func (z nat) random(rand *rand.Rand, limit nat, n int) nat {
+\tif alias(z, limit) {
+\t\tz = nil // z is an alias for limit - cannot reuse
+\t}\
+\tz = z.make(len(limit))\n+\n \tbitLengthOfMSW := uint(n % _W)\n \tif bitLengthOfMSW == 0 {\n \t\tbitLengthOfMSW = _W\n \t}\n \tmask := Word((1 << bitLengthOfMSW) - 1)\n-\tz = z.make(len(limit))\n \n \tfor {\n \t\tfor i := range z {\n```

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

`src/pkg/math/big/nat.go` の `(z nat) random` 関数における変更がこのコミットの核心です。

```go
func (z nat) random(rand *rand.Rand, limit nat, n int) nat {
    if alias(z, limit) {
        z = nil // z is an alias for limit - cannot reuse
    }
    z = z.make(len(limit))
    // ... 既存の乱数生成ロジック ...
}

1. if alias(z, limit):

   • この条件文は、レシーバ z と引数 limit が同じ基盤となる配列を共有しているかどうかをチェックします。nat 型は []Word のエイリアスであるため、スライスのエイリアシングが発生する可能性があります。
   • alias 関数は math/big パッケージ内部で定義されており、2つのスライスが同じ基盤配列を指しているか、または一方のスライスがもう一方のスライスの部分スライスであるかなどを判定します。

2. z = nil:

   • もしエイリアシングが検出された場合、z を nil に設定します。
   • この操作は非常に重要です。Goのスライスは、基盤となる配列へのポインタ、長さ、容量を持つ構造体です。z = nil とすることで、z が現在指している基盤配列への参照を解除します。

3. z = z.make(len(limit)):

   • z.make メソッドは、nat スライスを初期化または再初期化するために使用されます。
   • z が nil でない場合、z.make は既存の z の容量が十分であればそのメモリを再利用しようとします。しかし、z が nil の場合、z.make は必ず新しい基盤配列を割り当てて、len(limit) の長さを持つ新しいスライスを作成します。
   • これにより、limit が指すメモリ領域とは完全に独立した新しいメモリ領域が z に割り当てられることが保証されます。結果として、z の操作が limit の内容に影響を与えることがなくなり、ハングアップの原因となっていた競合状態が解消されます。

src/pkg/math/big/int_test.go に追加された TestIssue2607 は、この修正が正しく機能することを確認するための回帰テストです。

func TestIssue2607(t *testing.T) {
	// This code sequence used to hang.
	n := NewInt(10)
	n.Rand(rand.New(rand.NewSource(9)), n)
}

このテストは、n.Rand(..., n) という、まさにエイリアシングが発生するケースを再現しています。修正前はこの行でハングアップしていましたが、修正後は正常に実行され、テストがパスするようになります。

関連リンク

• Go Issue #2607: https://code.google.com/p/go/issues/detail?id=2607 (古いGoogle Codeのリンクですが、GoのIssueトラッカーは現在GitHubに移行しています)
• Go CL 5489109: https://golang.org/cl/5489109 (Gerrit Code Reviewのリンク)

参考にした情報源リンク

• Go言語 math/big パッケージのドキュメント: https://pkg.go.dev/math/big
• Go言語 math/rand パッケージのドキュメント: https://pkg.go.dev/math/rand
• Go言語におけるスライスとエイリアシングに関する一般的な情報源 (例: Go Slices: usage and internals): https://go.dev/blog/slices