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

このコミットは、Go言語のランタイムにおけるタイマー管理のバグ修正と、その修正を検証するためのテストコードの追加を含んでいます。具体的には、タイマーの停止処理（deltimer関数）において、データ構造の破損により一部のタイマーが正しく削除されない問題を解決しています。

コミット

commit a899a467f2e8ef7af2153cb91063f2da2bc2f36f
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Fri Nov 25 14:13:10 2011 +0300

    time: fix timer stop
    Due to data structure corruption,
    some timers could not be removed.
    Fixes #2495.
    
    R=golang-dev, adg
    CC=golang-dev, mdbrown
    https://golang.org/cl/5437060
---
 src/pkg/runtime/time.goc   | 13 ++++++++++---\n src/pkg/time/sleep_test.go | 16 ++++++++++++++++\n 2 files changed, 26 insertions(+), 3 deletions(-)

diff --git a/src/pkg/runtime/time.goc b/src/pkg/runtime/time.goc
index 23ad1aaef7..ad9f3aac56 100644
--- a/src/pkg/runtime/time.goc
+++ b/src/pkg/runtime/time.goc
@@ -133,9 +133,16 @@ deltimer(Timer *t)\n 		return false;\n 	}\n 
-\ttimers.t[i] = timers.t[--timers.len];\n-\tsiftup(i);\n-\tsiftdown(i);\n+\ttimers.len--;\n+\tif(i == timers.len) {\n+\t\ttimers.t[i] = nil;\n+\t} else {\n+\t\ttimers.t[i] = timers.t[timers.len];\n+\t\ttimers.t[timers.len] = nil;\n+\t\ttimers.t[i]->i = i;\n+\t\tsiftup(i);\n+\t\tsiftdown(i);\n+\t}\n \truntime·unlock(&timers);\n \treturn true;\n }\ndiff --git a/src/pkg/time/sleep_test.go b/src/pkg/time/sleep_test.go
index 4c4a079880..6fa2b69c50 100644
--- a/src/pkg/time/sleep_test.go
+++ b/src/pkg/time/sleep_test.go
@@ -205,3 +205,19 @@ func testAfterQueuing(t *testing.T) error {\n 	}\n 	return nil\n }\n+\n+func TestTimerStopStress(t *testing.T) {\n+\tif testing.Short() {\n+\t\treturn\n+\t}\n+\tfor i := 0; i < 100; i++ {\n+\t\tgo func(i int) {\n+\t\t\ttimer := AfterFunc(2e9, func() {\n+\t\t\t\tt.Fatalf(\"timer %d was not stopped\", i)\n+\t\t\t})\n+\t\t\tSleep(1e9)\n+\t\t\t\ttimer.Stop()\n+\t\t}(i)\n+\t}\n+\tSleep(3e9)\n+}\n```

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

[https://github.com/golang/go/commit/a899a467f2e8ef7af2153cb91063f2da2bc2f36f](https://github.com/golang/go/commit/a899a467f2e8ef7af2153cb91063f2da2bc2f36f)

## 元コミット内容

time: fix timer stop
Due to data structure corruption,
some timers could not be removed.
Fixes #2495.

R=golang-dev, adg
CC=golang-dev, mdbrown
https://golang.org/cl/5437060


## 変更の背景

このコミットは、Go言語のランタイムにおけるタイマーの停止処理に関する重要なバグを修正するために行われました。元の実装では、タイマーを停止（削除）しようとした際に、内部のデータ構造が破損することがあり、その結果、一部のタイマーが正しく削除されずに残り続けてしまう問題が発生していました。これは、システムリソースの無駄遣いや、意図しないタイマーの実行を引き起こす可能性がありました。コミットメッセージにある `Fixes #2495` は、この問題がGoのIssueトラッカーで報告されていたことを示しています。ただし、このコミットが2011年のものであるため、現在のGoのIssueトラッカーでは直接この番号のIssueを見つけることは困難でした。

## 前提知識の解説

このコミットを理解するためには、以下の概念について知っておく必要があります。

*   **Goランタイム (Go Runtime)**: Goプログラムの実行を管理するシステムです。ガベージコレクション、スケジューリング、ネットワークI/O、タイマー管理など、多くの低レベルな機能を提供します。
*   **タイマー (Timer)**: Go言語の `time` パッケージで提供される機能で、指定された時間が経過した後に一度だけイベントを発生させるために使用されます。`time.AfterFunc` などで作成されます。
*   **ヒープ (Heap)**: 優先度キューを実装するためによく用いられるツリーベースのデータ構造です。最小（または最大）要素を効率的に取得・削除できます。Goのタイマーは、通常、実行時間の昇順でソートされたヒープ構造で管理されます。
*   **`siftup` と `siftdown`**: ヒープ構造において、要素の追加や削除が行われた際に、ヒープのプロパティ（親が子よりも小さい/大きいなど）を維持するために使用される操作です。
    *   `siftup` (または `heapify-up`): 新しく追加された要素が親よりも小さい（または大きい）場合に、その要素を適切な位置まで上に移動させます。
    *   `siftdown` (または `heapify-down`): ルート要素が削除された後、新しいルート要素が子よりも大きい（または小さい）場合に、その要素を適切な位置まで下に移動させます。
*   **`runtime·unlock`**: Goランタイム内部で使用されるロック解除関数です。複数のゴルーチンが同時にデータ構造にアクセスする際に、競合状態を防ぐために使用されます。

## 技術的詳細

Goのランタイムは、効率的なタイマー管理のために、タイマーをヒープ（優先度キュー）として実装しています。このヒープは、タイマーの期限が最も近いものが常にルートに位置するようにソートされています。タイマーが期限切れになるか、`Stop()` メソッドによって停止されると、そのタイマーはヒープから削除される必要があります。

元の `deltimer` 関数では、タイマーを削除する際に、ヒープの末尾の要素を削除対象のタイマーの位置に移動させ、その後 `siftup` と `siftdown` を呼び出してヒープのプロパティを再構築していました。しかし、この処理には問題がありました。

具体的には、`timers.t[i] = timers.t[--timers.len];` という行で、ヒープの末尾の要素を削除対象の位置 `i` に移動させていました。このとき、`timers.len` は既にデクリメントされているため、`timers.t[timers.len]` はヒープの新しい末尾の要素を指します。

問題は、削除対象のタイマーがヒープの末尾に位置していた場合です。この場合、`i == timers.len` となりますが、元のコードではこの特殊なケースが考慮されていませんでした。`timers.t[i] = timers.t[--timers.len];` の実行後、`timers.t[i]` は自分自身を指すことになり、その後 `siftup(i)` と `siftdown(i)` が呼び出されても、ヒープの構造が正しく更新されない可能性がありました。これにより、削除されたはずのタイマーがヒープ内に残り続け、データ構造が破損する原因となっていました。

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

変更は `src/pkg/runtime/time.goc` ファイルの `deltimer` 関数にあります。

```diff
--- a/src/pkg/runtime/time.goc
+++ b/src/pkg/runtime/time.goc
@@ -133,9 +133,16 @@ deltimer(Timer *t)\n 		return false;\n 	}\n 
-\ttimers.t[i] = timers.t[--timers.len];\n-\tsiftup(i);\n-\tsiftdown(i);\n+\ttimers.len--;\n+\tif(i == timers.len) {\n+\t\ttimers.t[i] = nil;\n+\t} else {\n+\t\ttimers.t[i] = timers.t[timers.len];\n+\t\ttimers.t[timers.len] = nil;\n+\t\ttimers.t[i]->i = i;\n+\t\tsiftup(i);\n+\t\tsiftdown(i);\n+\t}\n \truntime·unlock(&timers);\n \treturn true;\

また、src/pkg/time/sleep_test.go に TestTimerStopStress という新しいテスト関数が追加されました。

--- a/src/pkg/time/sleep_test.go
+++ b/src/pkg/time/sleep_test.go
@@ -205,3 +205,19 @@ func testAfterQueuing(t *testing.T) error {\n 	}\n 	return nil\n }\n+\n+func TestTimerStopStress(t *testing.T) {\n+\tif testing.Short() {\n+\t\treturn\n+\t}\n+\tfor i := 0; i < 100; i++ {\n+\t\tgo func(i int) {\n+\t\t\ttimer := AfterFunc(2e9, func() {\n+\t\t\t\tt.Fatalf(\"timer %d was not stopped\", i)\n+\t\t\t})\n+\t\t\tSleep(1e9)\n+\t\t\t\ttimer.Stop()\n+\t\t}(i)\n+\t}\n+\tSleep(3e9)\n+}\n```

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

### `src/pkg/runtime/time.goc` の変更

`deltimer` 関数は、指定されたタイマー `t` をヒープから削除する役割を担っています。

**変更前:**

```c
	timers.t[i] = timers.t[--timers.len];
	siftup(i);
	siftdown(i);

このコードは、削除対象のタイマーがヒープの末尾にある場合（i == timers.len となる場合）に問題がありました。--timers.len によって timers.len がデクリメントされた後、timers.t[i] = timers.t[timers.len] は timers.t[i] = timers.t[i] となり、要素が自分自身に上書きされます。この場合、siftup と siftdown はヒープのプロパティを正しく再構築できませんでした。また、削除された要素が nil に設定されないため、ガベージコレクションの妨げになる可能性もありました。

変更後:

	timers.len--;
	if(i == timers.len) {
		timers.t[i] = nil;
	} else {
		timers.t[i] = timers.t[timers.len];
		timers.t[timers.len] = nil;
		timers.t[i]->i = i;
		siftup(i);
		siftdown(i);
	}

この修正では、まず timers.len をデクリメントします。次に、削除対象のタイマーがヒープの末尾にあったかどうかを if(i == timers.len) でチェックします。

if(i == timers.len) の場合（削除対象が末尾の要素だった場合）: timers.t[i] = nil; とすることで、削除された要素の位置を nil に設定し、ヒープから完全に切り離します。これにより、ガベージコレクションが可能になります。この場合、ヒープの再構築（siftup, siftdown）は不要です。
else の場合（削除対象が末尾以外の要素だった場合）: timers.t[i] = timers.t[timers.len]; で、ヒープの新しい末尾の要素を削除対象の位置 i に移動させます。 timers.t[timers.len] = nil; で、元の末尾の要素の位置を nil に設定します。 timers.t[i]->i = i; で、移動してきた要素のインデックスを更新します。これは、タイマーオブジェクトが自身のヒープ内での位置を保持している場合に重要です。最後に siftup(i); と siftdown(i); を呼び出して、ヒープのプロパティを正しく再構築します。これにより、ヒープの順序が維持されます。

この修正により、タイマーの削除処理がより堅牢になり、データ構造の破損を防ぐことができます。

`src/pkg/time/sleep_test.go` の変更

TestTimerStopStress 関数は、time.AfterFunc で作成されたタイマーが Stop() メソッドによって正しく停止されることを検証するためのストレステストです。

func TestTimerStopStress(t *testing.T) {
	if testing.Short() {
		return
	}
	for i := 0; i < 100; i++ {
		go func(i int) {
			timer := AfterFunc(2e9, func() { // 2秒後に実行されるタイマー
				t.Fatalf("timer %d was not stopped", i) // 停止されなかった場合にテストを失敗させる
			})
			Sleep(1e9) // 1秒待つ
			timer.Stop() // タイマーを停止する
		}(i)
	}
	Sleep(3e9) // 全てのゴルーチンが終了するのを待つ
}

このテストは、100個のゴルーチンを並行して起動します。各ゴルーチンは以下の処理を行います。

AfterFunc(2e9, ...) を使用して、2秒後に実行されるタイマーを作成します。タイマーのコールバック関数は、もしタイマーが停止されずに実行されてしまった場合に t.Fatalf を呼び出してテストを失敗させます。
Sleep(1e9) で1秒間待機します。これは、タイマーがまだ期限切れになっていない状態で Stop() を呼び出すことをシミュレートします。
timer.Stop() を呼び出してタイマーを停止します。

テストの最後に Sleep(3e9) があり、これは全てのゴルーチンが処理を完了し、タイマーが期限切れになる可能性のある時間を十分に待つためのものです。もし deltimer のバグが残っていれば、一部のタイマーが Stop() されてもヒープから削除されず、2秒後にコールバック関数が実行されて t.Fatalf が呼び出され、テストが失敗するはずです。このテストの追加により、タイマー停止処理の信頼性が向上したことが確認できます。

参考にした情報源リンク

Go言語の公式ドキュメント
ヒープデータ構造に関する一般的な情報
Go言語のIssueトラッカー (ただし、#2495は古すぎて直接見つけられませんでした)

comemo

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

コミット

`src/pkg/time/sleep_test.go` の変更

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo

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

コミット

src/pkg/time/sleep_test.go の変更

関連リンク

参考にした情報源リンク

`src/pkg/time/sleep_test.go` の変更