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

このコミットは、Go言語のランタイムに64ビットアトミック操作を追加するものです。これは、並列GC（Garbage Collection）の改善に向けた大きな変更の一部として切り出されたものです。

コミット

commit 4667571619fbbb7bf01699388432685dbec8fc9f
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Thu Apr 5 18:47:43 2012 +0400

    runtime: add 64-bit atomics
    This is factored out part of:
    https://golang.org/cl/5279048/
    (Parallel GC)
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/5985047

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

https://github.com/golang/go/commit/4667571619fbbb7bf01699388432685dbec8fc9f

元コミット内容

Goランタイムに64ビットアトミック操作を追加します。これは、並列ガベージコレクション（Parallel GC）の作業の一部として切り出されたものです。

変更の背景

このコミットの主な背景は、Go言語のランタイムにおける並列ガベージコレクション（Parallel GC）の導入です。GCの効率とパフォーマンスを向上させるためには、複数のゴルーチン（Goの軽量スレッド）が同時に共有データ構造にアクセスする際に、データの整合性を保ちつつ、競合を最小限に抑える必要があります。特に64ビットアーキテクチャが普及する中で、64ビット長の値をアトミックに操作する機能は、GCのマークフェーズやスイープフェーズなど、ランタイムの様々な部分で共有されるポインタやカウンタの更新に不可欠となります。

従来の32ビットアトミック操作だけでは、64ビットのポインタやカウンタを安全かつ効率的に更新することができません。例えば、64ビットの値を2つの32ビット操作で更新しようとすると、その間に他のゴルーチンがアクセスした場合、データが破損する可能性があります。これを防ぐためには、単一の不可分な操作として64ビット値を読み書き、比較交換（CAS: Compare-And-Swap）、加算などを行うアトミックプリミティブが必要となります。

このコミットは、並列GCの実現に向けた基盤となる変更であり、共有メモリ上のデータ構造を安全に操作するための重要なステップです。

前提知識の解説

アトミック操作 (Atomic Operations)

アトミック操作とは、複数のスレッドやプロセスが同時に共有データにアクセスする際に、その操作が中断されることなく、単一の不可分な単位として実行されることを保証する操作です。これにより、データ競合（data race）を防ぎ、プログラムの正確性を保つことができます。

• 不可分性: アトミック操作は、その実行中に他のスレッドから割り込まれることがありません。つまり、操作の途中で状態が観測されることがなく、常に操作の完了前か完了後の状態しか見えません。
• メモリバリア/フェンス: アトミック操作は、通常、メモリバリア（memory barrier）またはメモリフェンス（memory fence）を伴います。これは、コンパイラやプロセッサによる命令の並べ替え（reordering）を防ぎ、メモリ操作の順序を保証するものです。これにより、アトミック操作の前後のメモリ操作が意図した順序で可視化されることが保証されます。
• 一般的なアトミック操作:
  • Atomic Load: メモリ位置から値をアトミックに読み込む。
  • Atomic Store: メモリ位置に値をアトミックに書き込む。
  • Compare-And-Swap (CAS): メモリ位置の現在の値が期待する値と一致する場合にのみ、新しい値に更新する。更新が成功したかどうかを示すブール値を返す。これはロックフリープログラミングの基本的な構成要素です。
  • Atomic Add/Exchange: メモリ位置の値をアトミックに加算したり、他の値と交換したりする。

並列ガベージコレクション (Parallel Garbage Collection)

ガベージコレクション（GC）は、プログラムが不要になったメモリを自動的に解放するプロセスです。並列GCは、複数のCPUコアやスレッドを利用してGC処理を同時に実行することで、GCの一時停止時間（stop-the-world pause）を短縮し、アプリケーションのスループットと応答性を向上させることを目指します。

並列GCでは、GCスレッドとアプリケーションスレッドが同時に動作することが多く、共有されるヒープメモリやオブジェクトの状態を安全に管理するためにアトミック操作が不可欠となります。例えば、オブジェクトのマークビットの更新、参照カウンタの増減、GCの進行状況を示すカウンタの更新などにアトミック操作が用いられます。

CPUアーキテクチャとアトミック操作

異なるCPUアーキテクチャ（x86, AMD64, ARMなど）では、アトミック操作を実装するための命令セットが異なります。

• x86/AMD64: LOCK プレフィックスを伴う命令（例: LOCK CMPXCHG, LOCK XADD）がアトミック操作を提供します。CMPXCHG8B は32ビットモードで8バイト（64ビット）の比較交換を行う命令です。CMPXCHGQ は64ビットモードで64ビットの比較交換を行う命令です。
• ARM: ARMv6以降では、ロード・ストア排他（Load-Exclusive/Store-Exclusive, LDREX/STREX）命令のペアを使用してアトミック操作を実装します。これにより、指定されたメモリ領域への排他的アクセスを試み、競合が発生した場合には操作を再試行するメカニズムを提供します。

プリフェッチ (Prefetch)

プリフェッチとは、CPUが将来必要になると予測されるデータを、実際に必要になる前にメインメモリからキャッシュに読み込んでおく最適化技術です。これにより、データがキャッシュに存在するため、CPUがデータにアクセスする際のレイテンシ（遅延）を削減し、プログラムの実行速度を向上させることができます。

• PREFETCHNTA: x86/AMD64アーキテクチャにおけるプリフェッチ命令の一つで、"Prefetch NTA"（Non-Temporal Access）を意味します。これは、データが一度しか使用されない可能性が高い場合に、キャッシュ汚染を最小限に抑えつつデータをプリフェッチするためのヒントをCPUに与えます。通常のプリフェッチ命令がデータをL1/L2キャッシュに読み込むのに対し、PREFETCHNTAはデータを非一時的なキャッシュラインに読み込むことを示唆し、既存のキャッシュデータを追い出す可能性を低減します。

技術的詳細

このコミットは、Goランタイムの低レベルな部分、特にアセンブリ言語で記述された部分とC言語で記述された部分に、64ビットアトミック操作のサポートを追加します。

src/pkg/runtime/arch_*.h ファイルの変更

arch_386.h, arch_amd64.h, arch_arm.h の各ファイルに PREFETCH マクロが追加されています。これは、特定のアーキテクチャでプリフェッチ命令を呼び出すためのラッパーです。

• x86 (386) および AMD64: PREFETCH(addr) は runtime·prefetch(addr) 関数を呼び出すように定義されています。これは、実際のプリフェッチ命令をアセンブリコードで実装する関数へのフォワード宣言です。
• ARM: PREFETCH(addr) は USED(addr) に定義されています。これは、ARMアーキテクチャでは特定のプリフェッチ命令が利用できないか、またはこの時点でのGoランタイムの実装では単にアドレスが使用されていることを示すダミー操作として扱われていることを示唆しています。

src/pkg/runtime/asm_*.s ファイルの変更

これらのファイルは、各アーキテクチャ向けのアセンブリ言語で記述されたランタイム関数を含んでいます。

src/pkg/runtime/asm_386.s (32-bit x86)

• runtime·cas64: 64ビットの比較交換操作を実装します。32ビットアーキテクチャで64ビット値を操作するため、CMPXCHG8B 命令を使用します。この命令は、EDX:EAX レジスタペアに期待する64ビット値をロードし、ECX:EBX レジスタペアに新しい64ビット値をロードして、指定されたメモリ位置の64ビット値と比較交換を行います。成功するとZFフラグがセットされ、EAX に1が、失敗すると0が返されます。
• runtime·atomicload64: 64ビットのアトミックロード操作を実装します。MOVQ 命令（MMX命令セットの一部）を使用して64ビット値をメモリからMMXレジスタにロードし、その後MMXレジスタから別のメモリ位置にストアします。EMMS 命令はMMXステートをクリアするために使用されます。
• runtime·atomicstore64: 64ビットのアトミックストア操作を実装します。同様にMOVQ 命令を使用します。コメントには、MOVQ と EMMS がPentium MMXで導入されたことが記されています。また、LOCK XADDL AX, (SP) という命令が使用されていますが、これは実質的には何もしないが、必要なメモリフェンシングを提供する目的であるとコメントされています。これは、MFENCE 命令がPentium4 (SSE2) で導入される前の、古いCPUでのメモリバリアの実装方法を示唆しています。
• runtime·prefetch: PREFETCHNTA 命令を使用してプリフェッチ操作を実装します。

src/pkg/runtime/asm_amd64.s (64-bit x86-64)

• runtime·cas64: 64ビットの比較交換操作を実装します。64ビットアーキテクチャでは、CMPXCHGQ 命令を使用します。これは、RAX レジスタに期待する64ビット値をロードし、RCX レジスタに新しい64ビット値をロードして、指定されたメモリ位置の64ビット値と比較交換を行います。成功するとZFフラグがセットされ、RAX に1が、失敗すると0が返されます。
• runtime·xadd64: 64ビットのアトミック加算操作を実装します。LOCK XADDQ 命令を使用します。これは、指定されたメモリ位置の値をアトミックに加算し、元の値をレジスタにロードします。
• runtime·atomicstore64: 64ビットのアトミックストア操作を実装します。XCHGQ 命令（Exchange Quadword）を使用します。これは、指定されたメモリ位置の値をレジスタの値とアトミックに交換します。
• runtime·prefetch: PREFETCHNTA 命令を使用してプリフェッチ操作を実装します。

src/pkg/runtime/atomic_*.c ファイルの変更

これらのファイルは、C言語で記述されたアトミック操作のラッパー関数や、アセンブリで実装されたアトミックプリミティブを利用した高レベルなアトミック操作を定義します。

src/pkg/runtime/atomic_386.c

• runtime·xadd64: 64ビットの xadd（加算して新しい値を返す）操作を実装します。これは、runtime·cas64 をループ内で使用して、ロックフリーで xadd を実現しています。old の値を読み込み、old+v と比較交換を試み、成功するまで繰り返します。

src/pkg/runtime/atomic_amd64.c

• runtime·atomicload64: 64ビットのアトミックロード操作を実装します。単に *addr を返すだけですが、これはコンパイラがアトミックなロードを生成するか、またはアセンブリレベルで既にアトミック性が保証されていることを前提としています。

src/pkg/runtime/atomic_arm.c

ARMアーキテクチャでは、x86/AMD64のような強力なアトミック命令が直接利用できないため、ロックベースのアトミック操作が実装されています。

• locktab: キャッシュラインサイズでパディングされた Lock 構造体の配列が定義されています。これは、異なるアドレスに対するロックが互いにキャッシュラインを共有しないようにするためのものです。
• LOCK(addr) マクロ: 指定されたアドレスに基づいて locktab から適切なロックを選択します。これにより、粒度の粗いロックではなく、より細かい粒度でロックをかけることができます。
• runtime·cas64: 64ビットの比較交換操作を実装します。これは、LOCK(addr) を使用してロックを取得し、クリティカルセクション内で通常の比較と代入を行い、その後ロックを解放します。
• runtime·xadd64: 64ビットの xadd 操作を実装します。同様にロックを取得し、加算と代入を行い、ロックを解放します。
• runtime·atomicload64: 64ビットのアトミックロード操作を実装します。ロックを取得し、値を読み込み、ロックを解放します。
• runtime·atomicstore64: 64ビットのアトミックストア操作を実装します。ロックを取得し、値を書き込み、ロックを解放します。

ARMでのロックベースの実装は、x86/AMD64のハードウェアアトミック命令に比べてパフォーマンスが劣る可能性がありますが、アトミック性を保証するための一般的な手法です。

src/pkg/runtime/runtime.c ファイルの変更

• TestAtomic64 関数: 新しく追加された64ビットアトミック操作のテスト関数です。
  • runtime·cas64 のテスト: 期待値と異なる場合に失敗するケース、期待値と一致する場合に成功するケースを検証します。
  • runtime·atomicload64 のテスト: 正しくロードできるかを確認します。
  • runtime·atomicstore64 のテスト: 正しくストアできるかを確認します。特に大きな値（1ull<<40）を使用して、64ビット値が正しく扱われることを確認しています。
  • runtime·xadd64 のテスト: 正しく加算できるかを確認します。
• runtime·check 関数からの呼び出し: TestAtomic64() が runtime·check() 関数から呼び出されるようになり、ランタイムの初期化時にこれらのアトミック操作が正しく機能するかどうかが検証されます。

src/pkg/runtime/runtime.h ファイルの変更

新しく追加された64ビットアトミック操作の関数プロトタイプが宣言されています。

• bool runtime·cas64(uint64*, uint64*, uint64);
• uint64 runtime·xadd64(uint64 volatile*, int64);
• void runtime·atomicstore64(uint64 volatile*, uint64);
• uint64 runtime·atomicload64(uint64 volatile*);

これらの宣言により、Goランタイムの他の部分からこれらの64ビットアトミック操作を安全に呼び出すことができるようになります。

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

このコミットのコアとなる変更は、以下のファイルにおける64ビットアトミック操作の実装と、それに関連するヘッダの更新、およびテストコードの追加です。

• src/pkg/runtime/arch_386.h
• src/pkg/runtime/arch_amd64.h
• src/pkg/runtime/arch_arm.h
• src/pkg/runtime/asm_386.s
• src/pkg/runtime/asm_amd64.s
• src/pkg/runtime/atomic_386.c
• src/pkg/runtime/atomic_amd64.c
• src/pkg/runtime/atomic_arm.c
• src/pkg/runtime/runtime.c
• src/pkg/runtime/runtime.h

特に、asm_*.s ファイルにおける各アーキテクチャ固有のアセンブリ命令を用いた64ビットアトミックプリミティブ（cas64, atomicload64, atomicstore64, xadd64）の実装と、atomic_arm.c におけるARM向けのロックベースの実装が重要です。また、runtime.c に追加された TestAtomic64 関数は、これらの新しいアトミック操作が正しく機能することを検証するためのものです。

コアとなるコードの解説

runtime·cas64 (x86/AMD64 アセンブリ)

// bool runtime·cas64(uint64 *val, uint64 *old, uint64 new)
// Atomically:
//	if(*val == *old){
//		*val = new;
//		return 1;
//	} else {
//		*old = *val
//		return 0;
//	}
TEXT runtime·cas64(SB), 7, $0
	// 32-bit (asm_386.s)
	MOVL	4(SP), BP   // valのアドレスをBPにロード
	MOVL	8(SP), SI   // oldのアドレスをSIにロード
	MOVL	0(SI), AX   // oldの低32ビットをAXにロード
	MOVL	4(SI), DX   // oldの高32ビットをDXにロード (EDX:EAXが期待値)
	MOVL	12(SP), BX  // newの低32ビットをBXにロード
	MOVL	16(SP), CX  // newの高32ビットをCXにロード (ECX:EBXが新しい値)
	LOCK
	CMPXCHG8B	0(BP) // *val と EDX:EAX を比較し、一致すれば *val を ECX:EBX で更新
	JNZ	cas64_fail    // 比較が失敗したらcas64_failへジャンプ
	MOVL	$1, AX        // 成功: 戻り値1をAXにセット
	RET
cas64_fail:
	MOVL	AX, 0(SI)   // 失敗: *val の現在の値をoldに書き戻す (AXは*valの低32ビット)
	MOVL	DX, 4(SI)   // DXは*valの高32ビット
	XORL	AX, AX      // 戻り値0をAXにセット
	RET

// 64-bit (asm_amd64.s)
TEXT runtime·cas64(SB), 7, $0
	MOVQ	8(SP), BX   // valのアドレスをBXにロード
	MOVQ	16(SP), BP  // oldのアドレスをBPにロード
	MOVQ	0(BP), AX   // oldの値をAXにロード (RAXが期待値)
	MOVQ	24(SP), CX  // newの値をCXにロード (RCXが新しい値)
	LOCK
	CMPXCHGQ	CX, 0(BX) // *val と RAX を比較し、一致すれば *val を RCX で更新
	JNZ	cas64_fail    // 比較が失敗したらcas64_failへジャンプ
	MOVL	$1, AX        // 成功: 戻り値1をAXにセット
	RET
cas64_fail:
	MOVQ	AX, 0(BP)   // 失敗: *val の現在の値をoldに書き戻す (RAXは*valの現在の値)
	MOVL	$0, AX      // 戻り値0をAXにセット
	RET

CMPXCHG8B (32-bit) と CMPXCHGQ (64-bit) 命令は、それぞれ8バイトと8バイトの比較交換をアトミックに行うためのCPU命令です。LOCK プレフィックスは、この命令がマルチプロセッサ環境でアトミックに実行されることを保証します。

runtime·xadd64 (ARM C言語実装)

#pragma textflag 7
uint64
runtime·xadd64(uint64 volatile *addr, int64 delta)
{
	uint64 res;
	
	runtime·lock(LOCK(addr)); // アドレスに対応するロックを取得
	res = *addr + delta;      // 値を読み込み、加算
	*addr = res;              // 結果を書き戻す
	runtime·unlock(LOCK(addr)); // ロックを解放
	return res;               // 新しい値を返す
}

ARMアーキテクチャでは、ハードウェアによる64ビットアトミック命令が直接利用できない（またはこの時点のGoランタイムでは利用されていない）ため、ミューテックス（ロック）を使用してアトミック性を保証しています。LOCK(addr) マクロは、対象のアドレスに基づいて適切なロックを選択し、runtime·lock と runtime·unlock でクリティカルセクションを保護します。

TestAtomic64 (runtime.c)

static void
TestAtomic64(void)
{
	uint64 z64, x64;

	z64 = 42;
	x64 = 0;
	PREFETCH(&z64); // プリフェッチのテスト
	if(runtime·cas64(&z64, &x64, 1)) // 期待値(x64=0)と異なるので失敗するはず
		runtime·throw("cas64 failed");
	if(x64 != 42) // 失敗した場合、x64にはz64の元の値(42)が書き戻されるはず
		runtime·throw("cas64 failed");
	if(!runtime·cas64(&z64, &x64, 1)) // 期待値(x64=42)と一致するので成功するはず
		runtime·throw("cas64 failed");
	if(x64 != 42 || z64 != 1) // 成功した場合、z64は1になり、x64は元の42のまま
		runtime·throw("cas64 failed");
	if(runtime·atomicload64(&z64) != 1) // ロードのテスト
		runtime·throw("load64 failed");
	runtime·atomicstore64(&z64, (1ull<<40)+1); // ストアのテスト (大きな値)
	if(runtime·atomicload64(&z64) != (1ull<<40)+1)
		runtime·throw("store64 failed");
	if(runtime·xadd64(&z64, (1ull<<40)+1) != (2ull<<40)+2) // xaddのテスト
		runtime·throw("xadd64 failed");
	if(runtime·atomicload64(&z64) != (2ull<<40)+2)
		runtime·throw("xadd64 failed");
}

このテスト関数は、新しく追加された64ビットアトミック操作の基本的な機能と正確性を検証します。特に、cas64 の成功/失敗ケース、atomicload64 と atomicstore64 による値の読み書き、そして xadd64 によるアトミックな加算が正しく行われることを確認しています。大きな64ビット値（1ull<<40）を使用することで、オーバーフローやビットの欠落がないことを保証しています。

関連リンク

• Go言語の並行性: Go言語はゴルーチンとチャネルによる並行プログラミングを強力にサポートしており、アトミック操作はその低レベルな基盤を形成します。
• ロックフリープログラミング: アトミック操作は、ロックを使用せずに並行性を実現するロックフリープログラミングの基礎となります。
• ガベージコレクションのアルゴリズム: 並列GCは、マーク＆スイープ、参照カウントなど、様々なGCアルゴリズムと組み合わせて使用されます。

参考にした情報源リンク

• Go言語の公式ドキュメント: Go言語のランタイムやアトミック操作に関する公式ドキュメントは、これらの概念を理解する上で最も信頼できる情報源です。
• Intel 64 and IA-32 Architectures Software Developer's Manuals: x86/AMD64のアセンブリ命令（CMPXCHG8B, CMPXCHGQ, LOCK プレフィックス, PREFETCHNTA など）の詳細な説明が記載されています。
• ARM Architecture Reference Manuals: ARMのアトミック操作（LDREX/STREX）やメモリモデルに関する情報が記載されています。
• 並行プログラミングに関する書籍や論文: アトミック操作、メモリモデル、ロックフリーデータ構造に関する一般的な知識は、並行プログラミングの専門書から得られます。
• GoのIssueトラッカーとコードレビュー: コミットメッセージに記載されているGoのコードレビューリンク（https://golang.org/cl/5279048/ および https://golang.org/cl/5985047）は、この変更の議論や背景を深く理解するための貴重な情報源です。
  • https://golang.org/cl/5279048/ (Parallel GCの元となる変更)
  • https://golang.org/cl/5985047 (このコミット自体のコードレビュー)
• Wikipedia: アトミック操作、メモリバリア、ガベージコレクションなどの基本的な概念について、概要を把握するのに役立ちます。
  • アトミック操作 - Wikipedia
  • メモリバリア - Wikipedia
  • ガベージコレクション - Wikipedia
  • Compare-and-swap - Wikipedia
  • XADD - Wikipedia
  • PREFETCH (x86 instruction) - Wikipedia
  • MMX (instruction set) - Wikipedia
  • EMMS - Wikipedia
  • XCHG - Wikipedia
  • Load-Link/Store-Conditional - Wikipedia (ARMの排他ロード/ストアの概念)