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

このコミットは、Goランタイムのメモリ管理に関連するmarknogc関数からアトミックなCAS (Compare-And-Swap) ループを削除する変更です。これは、Goランタイムの内部的なメモリ管理の進化、特にスパン（メモリ領域）の管理方法の変更に伴うものです。

コミット

commit 3877f1d9c80f57beb8a8dde778f6239598fd4a58
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Tue Mar 11 17:35:49 2014 +0400

    runtime: remove atomic CAS loop from marknogc
    Spans are now private to threads, and the loop
    is removed from all other functions.
    Remove it from marknogc for consistency.
    
    LGTM=khr, rsc
    R=golang-codereviews, bradfitz, khr
    CC=golang-codereviews, khr, rsc
    https://golang.org/cl/72520043

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

https://github.com/golang/go/commit/3877f1d9c80f57beb8a8dde778f6239598fd4a58

元コミット内容

runtime: remove atomic CAS loop from marknogc
Spans are now private to threads, and the loop
is removed from all other functions.
Remove it from marknogc for consistency.

変更の背景

このコミットの主な背景は、Goランタイムのメモリ管理における内部的な設計変更です。コミットメッセージにある「Spans are now private to threads」という記述が重要です。

Goランタイムのメモリ管理では、ヒープメモリは「スパン（span）」と呼ばれる連続したメモリページ群に分割されて管理されます。以前のGoのバージョンでは、これらのスパンは複数のゴルーチンやOSスレッド間で共有される可能性があり、スパンの状態を変更する際には競合状態を防ぐためにアトミック操作（特にCompare-And-Swap: CAS）を用いたループが必要でした。

しかし、このコミットが行われた時期（2014年3月）には、Goランタイムのメモリ管理戦略が進化し、スパンが特定のOSスレッド（またはGoのスケジューラにおけるP: Processor）にプライベートに割り当てられるようになりました。これにより、スパンの状態を変更する際に他のスレッドとの競合を考慮する必要がなくなり、アトミックなCASループが不要になったため、marknogc関数からもこの冗長なループが削除されました。これは、コードの簡素化とパフォーマンスの向上が目的です。

また、コミットメッセージには「the loop is removed from all other functions」とあり、他の関連する関数からも同様のCASループが既に削除されていたことが示唆されています。marknogcからの削除は、この一貫性を保つための措置でもあります。

前提知識の解説

このコミットを理解するためには、以下のGoランタイムの概念を理解しておく必要があります。

Goのメモリ管理（ヒープとスパン）:
- Goプログラムが動的に確保するメモリ（ヒープ）は、mheapというグローバルな構造体によって管理されます。
- mheapは、メモリを「アリーナ（arena）」と呼ばれる大きな連続したブロックに分割します。mheap.arena_startは、このメモリ領域の開始アドレスを示します。
- アリーナはさらに8KBのページに分割され、これらのページは「スパン（mspan）」と呼ばれる単位で管理されます。スパンは、特定のサイズのオブジェクトを格納するために使用されます。
- 各スパンには、そのスパン内のメモリブロックの状態（割り当て済みか、空きかなど）を示すビットマップが関連付けられています。
marknogc関数:
- marknogcは、Goランタイム内部で使用される関数で、特定のメモリ領域をガベージコレクション（GC）の対象外としてマークするために使われます。これは、GCが誤ってランタイムの重要なデータ構造を回収してしまわないようにするために必要です。
- 関数名から「mark no gc」と推測され、GCのマークフェーズにおいて、GC対象外のメモリを識別するためのビットを設定する役割を担っていたと考えられます。
アトミック操作とCAS (Compare-And-Swap):
- 並行プログラミングにおいて、複数のゴルーチンやOSスレッドが共有データに同時にアクセスする場合、競合状態（race condition）が発生する可能性があります。
- アトミック操作は、不可分な操作であり、途中で他の操作に割り込まれることなく完了することが保証されます。
- CASはアトミック操作の一種で、メモリ位置の現在の値が期待される値と一致する場合にのみ、そのメモリ位置の値を新しい値に更新します。一致しない場合は更新を行わず、現在の値を返します。
- CASループは、共有データに対する更新を試みる際に、CAS操作が成功するまで繰り返し試行するパターンです。これはロックフリーなデータ構造を実装する際によく用いられます。
GOMAXPROCS:
- GOMAXPROCSは、Goランタイムが同時に実行できるOSスレッドの最大数を制御する環境変数または関数です。これは、GoスケジューラがゴルーチンをOSスレッドにマッピングする方法に影響を与えます。
- この値が1の場合、Goランタイムは単一のOSスレッドで実行されるため、共有データへのアクセスに関する競合は発生しません。そのため、CASループのようなアトミック操作は不要になります。
runtime.throw:
- runtime.throwは、Goランタイム内部で致命的かつ回復不可能なエラーが発生した場合に呼び出される関数です。これは、ユーザーがpanicを呼び出すのとは異なり、プログラムの実行を即座に終了させます。
bitAllocatedとbitBlockBoundary:
- これらは、Goランタイムのメモリ管理におけるビットマップの一部として使用される定数です。
- bitAllocatedは、メモリブロックが割り当て済みであることを示すビットです。
- bitBlockBoundaryは、メモリブロックの境界を示すビットです。これらのビットは、GCがメモリをスキャンし、オブジェクトの開始と終了を識別するために使用されます。

技術的詳細

このコミットの技術的な核心は、marknogc関数におけるメモリビットマップの更新方法の変更です。

変更前は、marknogc関数は以下のロジックでメモリビットマップを更新していました。

v（マーク対象のポインタ）から、mheap.arena_startを基準としたワードオフセットoffを計算します。
このオフセットとwordsPerBitmapWord（ビットマップの1ワードあたりのビット数）を使用して、対応するビットマップワードbと、そのワード内のビット位置shiftを特定します。
CASループ:
- *b（現在のビットマップワードの値）をobitsとして読み取ります。
- obitsのshift位置にあるビットがbitAllocatedでない場合、runtime.throwを呼び出して致命的なエラーを発生させます。これは、マークしようとしているメモリが既に割り当て済みでないという予期せぬ状態を示します。
- obitsからbitAllocatedビットをクリアし、代わりにbitBlockBoundaryビットを設定した新しい値bitsを計算します。
- runtime.gomaxprocs == 1の場合（単一スレッド実行）、直接*b = bitsで更新し、ループを抜けます。
- runtime.gomaxprocs > 1の場合（複数スレッド実行）、runtime.casp((void**)b, (void*)obits, (void*)bits)を使用してアトミックに更新を試みます。CASが成功すればループを抜け、失敗すれば（他のスレッドが*bを更新したため）ループを続行し、再試行します。

変更後は、このCASループ全体が削除され、以下のシンプルな直接代入に置き換えられました。

*b = (*b & ~(bitAllocated<<shift)) | bitBlockBoundary<<shift;

この変更は、スパンがスレッドにプライベートになったため、marknogcが呼び出されるコンテキストでは、*bに対する競合がもはや発生しないという前提に基づいています。つまり、marknogcが操作するメモリ領域は、その時点で他のゴルーチンやOSスレッドによって同時に変更される可能性がないため、アトミックなCAS操作が不要になったということです。これにより、オーバーヘッドが削減され、コードが簡素化されました。

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

src/pkg/runtime/mgc0.cファイルのruntime·marknogc関数が変更されています。

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -2614,26 +2614,12 @@ runfinq(void)
 void
 runtime·marknogc(void *v)
 {
-	uintptr *b, obits, bits, off, shift;
+	uintptr *b, off, shift;
 
 	off = (uintptr*)v - (uintptr*)runtime·mheap.arena_start;  // word offset
 	b = (uintptr*)runtime·mheap.arena_start - off/wordsPerBitmapWord - 1;
 	shift = off % wordsPerBitmapWord;
--
-	for(;;) {
--		obits = *b;
--		if((obits>>shift & bitMask) != bitAllocated)
--			runtime·throw("bad initial state for marknogc");
--		bits = (obits & ~(bitAllocated<<shift)) | bitBlockBoundary<<shift;
--		if(runtime·gomaxprocs == 1) {
--			*b = bits;
--			break;
--		} else {
--			// more than one goroutine is potentially running: use atomic op
--			if(runtime·casp((void**)b, (void*)obits, (void*)bits))\
--				break;
--		}
--	}
-+	*b = (*b & ~(bitAllocated<<shift)) | bitBlockBoundary<<shift;
 }
 
 void

コアとなるコードの解説

変更されたruntime·marknogc関数の主要な部分は以下の通りです。

void
runtime·marknogc(void *v)
{
	uintptr *b, off, shift; // 変数宣言から obits, bits が削除された

	off = (uintptr*)v - (uintptr*)runtime·mheap.arena_start;  // word offset
	b = (uintptr*)runtime·mheap.arena_start - off/wordsPerBitmapWord - 1;
	shift = off % wordsPerBitmapWord;

	// 以前のCASループ全体がこの1行に置き換えられた
	*b = (*b & ~(bitAllocated<<shift)) | bitBlockBoundary<<shift;
}

変数宣言の変更:
- 変更前はuintptr *b, obits, bits, off, shift;と宣言されていましたが、obitsとbitsが不要になったため、変更後はuintptr *b, off, shift;となっています。これは、CASループ内で一時的に使用されていたこれらの変数が、直接代入によって不要になったことを示しています。
オフセットとビットマップ位置の計算:
- off = (uintptr*)v - (uintptr*)runtime·mheap.arena_start;
  - vはマーク対象のメモリブロックへのポインタです。
  - runtime·mheap.arena_startはGoヒープの開始アドレスです。
  - この行は、vがarena_startからどれだけ離れているか（ワード単位のオフセット）を計算します。
- b = (uintptr*)runtime·mheap.arena_start - off/wordsPerBitmapWord - 1;
  - 計算されたオフセットoffと、ビットマップの構造（wordsPerBitmapWord）に基づいて、vに対応するビットマップワードのポインタbを計算します。Goのメモリ管理では、ビットマップはヒープの先頭（またはその近く）に配置されることが多いため、arena_startから逆方向にオフセットを計算しています。
- shift = off % wordsPerBitmapWord;
  - bが指すビットマップワード内で、どのビットを操作すべきかを示すシフト量shiftを計算します。
ビットマップの直接更新:
- *b = (*b & ~(bitAllocated<<shift)) | bitBlockBoundary<<shift;
  - これが変更の核心です。以前のCASループの代わりに、この1行でビットマップが更新されます。
  - bitAllocated<<shift: bitAllocated定数をshift分左にシフトし、操作対象のビット位置に合わせます。
  - ~(bitAllocated<<shift): そのビット位置のbitAllocatedビットを反転させます。これにより、元の*bからbitAllocatedビットがクリアされます。
  - *b & ~(bitAllocated<<shift): *bの現在の値から、bitAllocatedビットをクリアします。
  - bitBlockBoundary<<shift: bitBlockBoundary定数をshift分左にシフトし、操作対象のビット位置に合わせます。
  - | bitBlockBoundary<<shift: bitAllocatedビットがクリアされた値に、bitBlockBoundaryビットを設定します。
  - 結果として、この操作は、指定されたメモリブロックのビットマップエントリにおいて、「割り当て済み」を示すビットをクリアし、「ブロック境界」を示すビットを設定します。これは、marknogcがGC対象外としてマークする際に、そのメモリブロックの状態を適切に更新するためのものです。

この変更は、Goランタイムのメモリ管理がより洗練され、スパンがスレッドプライベートになったことで、特定のコンテキストでのアトミック操作の必要性がなくなったことを明確に示しています。これにより、コードの複雑性が減り、実行効率が向上します。

comemo