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

このコミットは、Goランタイムにおける64ビット値のアトミックな比較交換 (Compare-And-Swap, CAS) 操作である runtime·cas64 の動作を、32ビット値やポインタに対するCAS操作 (runtime·cas32, runtime·casp) と一貫させるための変更です。主に、CAS操作が失敗した場合の old 引数の扱いを統一しています。

変更されたファイルは以下の通りです。

• src/pkg/runtime/asm_amd64.s: AMD64アーキテクチャ向けのアセンブリコードで、runtime·cas64 の具体的な実装が含まれます。
• src/pkg/runtime/atomic_386.c: 386 (x86) アーキテクチャ向けのアトミック操作の実装で、runtime·cas64 の呼び出し元が含まれます。
• src/pkg/runtime/atomic_arm.c: ARMアーキテクチャ向けのアトミック操作の実装で、runtime·cas64 の呼び出し元が含まれます。
• src/pkg/runtime/lfstack.c: ロックフリースタックの実装で、runtime·cas64 の呼び出し元が含まれます。
• src/pkg/runtime/parfor.c: 並列処理のための ParFor 構造体の実装で、runtime·cas64 の呼び出し元が含まれます。
• src/pkg/runtime/runtime.c: Goランタイムの主要なCコードで、runtime·cas64 のテストケース TestAtomic64 が含まれます。
• src/pkg/runtime/runtime.h: Goランタイムのヘッダーファイルで、runtime·cas64 の関数プロトタイプ宣言が含まれます。

コミット

commit fb63e4fefbb1325a21f643febc97987c82fcae7a
Author: Russ Cox <rsc@golang.org>
Date:   Fri Jul 12 00:03:32 2013 -0400

    runtime: make cas64 like cas32 and casp
    
    The current cas64 definition hard-codes the x86 behavior
    of updating *old with the new value when the cas fails.
    This is inconsistent with cas32 and casp.
    Make it consistent.
    
    This means that the cas64 uses will be epsilon less efficient
    than they might be, because they have to do an unnecessary
    memory load on x86. But so be it. Code clarity and consistency
    is more important.
    
    R=golang-dev, bradfitz
    CC=golang-dev
    https://golang.org/cl/10909045

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

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

元コミット内容

runtime: make cas64 like cas32 and casp

The current cas64 definition hard-codes the x86 behavior
of updating *old with the new value when the cas fails.
This is inconsistent with cas32 and casp.
Make it consistent.

This means that the cas64 uses will be epsilon less efficient
than they might be, because they have to do an unnecessary
memory load on x86. But so be it. Code clarity and consistency
is more important.

変更の背景

このコミットの主な背景は、Goランタイムにおけるアトミック操作の cas64 (64ビット値の比較交換) が、他のCAS操作 (cas32 や casp、それぞれ32ビット値とポインタの比較交換) と異なる振る舞いをしていたことです。

具体的には、x86アーキテクチャにおいて cas64 が失敗した場合、old 引数として渡されたポインタが指すメモリ位置が、比較対象のアドレス (addr) が指す現在の値で更新されていました。これは、CAS操作が成功した場合にのみ old の値が更新されるという一般的なCASのセマンティクス、および cas32 や casp の既存の動作とは異なっていました。

このような不一致は、コードの理解を困難にし、異なるアーキテクチャ間での移植性を損なう可能性がありました。特に、CAS操作はロックフリーデータ構造や並行処理において頻繁に使用されるため、そのセマンティクスの一貫性は非常に重要です。

コミットメッセージにもあるように、この変更はx86アーキテクチャにおいて「不必要なメモリロード」を発生させ、わずかな効率の低下を招く可能性があります。しかし、Goランタイムの設計思想として、コードの明確さ (clarity) と一貫性 (consistency) が、微細なパフォーマンス最適化よりも優先されるべきであるという判断がなされました。これにより、開発者は cas ファミリーの関数が常に同じセマンティクスを持つと信頼できるようになります。

前提知識の解説

CAS (Compare-And-Swap)

CAS (Compare-And-Swap) は、マルチスレッドプログラミングにおいてアトミックな操作を実現するための命令です。アトミック操作とは、その操作が中断されることなく、単一の不可分なステップとして実行されることを保証するものです。

CAS操作は通常、以下の3つの引数を取ります。

1. メモリ位置 (address): 操作対象のメモリアドレス。
2. 期待値 (old value): メモリ位置に現在格納されていると期待される値。
3. 新値 (new value): 期待値とメモリ位置の現在の値が一致した場合に、メモリ位置に書き込む新しい値。

CAS操作の動作は以下の通りです。

• メモリ位置の現在の値が期待値と一致する場合：メモリ位置の値を新値で更新し、操作が成功したことを示す真 (true) を返します。
• メモリ位置の現在の値が期待値と一致しない場合：メモリ位置の値を変更せず、操作が失敗したことを示す偽 (false) を返します。

CASは、ロックを使用せずに共有データ構造を安全に更新する「ロックフリープログラミング」の基礎となります。例えば、複数のスレッドが同時にカウンタをインクリメントしようとする場合、CASを使って現在の値を読み込み、それに1を加えた値を新値として書き込もうとします。もしその間に他のスレッドがカウンタを更新していればCASは失敗し、現在の値を再読み込みして再試行します。

Goランタイム

Goランタイムは、Go言語で書かれたプログラムの実行を管理する低レベルなコンポーネント群です。これには、ガベージコレクション、スケジューラ（ゴルーチンの管理）、メモリ割り当て、システムコールインターフェース、そしてアトミック操作などのプリミティブが含まれます。Goランタイムの多くはC言語（またはGo言語自体）とアセンブリ言語で書かれており、OSやハードウェアと直接対話して、Goプログラムが効率的かつ並行に動作するための基盤を提供します。

アセンブリ言語 (x86-64) と CMPXCHGQ 命令

アセンブリ言語は、CPUが直接実行できる機械語に非常に近い低レベルなプログラミング言語です。x86-64は、IntelおよびAMDの64ビットプロセッサアーキテクチャを指します。

CMPXCHGQ (Compare and Exchange Quadword) は、x86-64アーキテクチャにおけるアトミックな比較交換命令です。この命令は、CAS操作をハードウェアレベルでサポートします。

CMPXCHGQ の基本的な動作は以下の通りです。

1. RAX レジスタ (または EAX / AX / AL、オペランドサイズによる) の値と、指定されたメモリ位置の値を比較します。
2. もし両者が一致すれば、指定されたメモリ位置に別のレジスタ (通常は RCX / ECX / CX / CL) の値を書き込みます。
3. もし一致しなければ、メモリ位置の値を RAX レジスタにロードします。

この命令は、比較と交換を単一のアトミックな操作として実行するため、マルチスレッド環境での競合状態を防ぐことができます。LOCK プレフィックスを付けることで、マルチプロセッサ環境においてもこの操作がアトミックであることを保証します。

ポインタと値渡し

プログラミング言語における関数の引数の渡し方には、主に「値渡し (pass by value)」と「参照渡し (pass by reference)」があります。

• 値渡し: 引数の値がコピーされて関数に渡されます。関数内で引数の値を変更しても、呼び出し元の変数の値は影響を受けません。
• 参照渡し: 引数のメモリ位置（アドレス）が関数に渡されます。関数内でそのアドレスを通じて値を変更すると、呼び出し元の変数の値も変更されます。C言語では、ポインタを引数として渡すことで参照渡しを模倣します。

このコミットでは、runtime·cas64 の old 引数が、以前はポインタ (uint64* old) で渡され、関数内でそのポインタが指す値が変更される可能性がありました。変更後は、値 (uint64 old) で渡されるようになり、関数内で old の値が変更されても、呼び出し元の変数は影響を受けなくなります。

技術的詳細

このコミットの核心は、runtime·cas64 関数のセマンティクスを、runtime·cas32 および runtime·casp と一貫させることです。

以前の runtime·cas64 の動作 (x86固有の振る舞い)

変更前、x86アーキテクチャにおける runtime·cas64 の実装は、CAS操作が失敗した場合に、old 引数として渡されたポインタが指すメモリ位置を、比較対象のメモリ位置 (addr) の現在の値で更新していました。

例えば、runtime·cas64(addr, &old_val, new_val) のように呼び出された場合、もし *addr と old_val が一致しなかったとしても、old_val は *addr の現在の値に上書きされていました。これは、x86の CMPXCHGQ 命令の動作特性（比較が失敗した場合に RAX レジスタにメモリの現在の値をロードする）を直接利用したものでした。

cas32 および casp との不一致

しかし、runtime·cas32 や runtime·casp は、CAS操作が失敗した場合に old 引数を変更しません。これらの関数は、CASの一般的なセマンティクスに従い、成功した場合にのみ old の値が「期待通りに一致した」ことを意味し、失敗した場合は old の値はそのまま保持されます。

この不一致は、以下のような問題を引き起こしていました。

1. コードの予測可能性の低下: 開発者は cas ファミリーの関数がプラットフォームやビット幅によって異なる振る舞いをすると、コードの理解やデバッグが難しくなります。
2. 移植性の問題: cas64 の呼び出し元がx86固有の振る舞いに依存している場合、他のアーキテクチャ（ARMなど）では正しく動作しない可能性があります。実際、ARM版の atomic_arm.c では、runtime·cas64 の失敗時に *old = *addr; のような明示的な更新は行われていませんでした。

変更による一貫性の実現

このコミットでは、runtime·cas64 の old 引数をポインタ (uint64*) から値 (uint64) に変更することで、この不一致を解消しています。

• 関数シグネチャの変更: runtime·cas64 のプロトタイプが bool runtime·cas64(uint64*, uint64*, uint64); から bool runtime·cas64(uint64*, uint64, uint64); に変更されました。これにより、old は値渡しとなり、関数内でその値が変更されても呼び出し元の変数は影響を受けなくなります。
• アセンブリコードの変更: x86-64のアセンブリ実装から、CAS失敗時に old 引数（ポインタ）が指すメモリを更新する命令が削除されました。
• 呼び出し元の変更: runtime·cas64 を呼び出す全ての箇所で、&old_val のようにポインタを渡していた部分が old_val のように値を渡すように変更されました。

「不必要なメモリロード」とその影響

cas64 が失敗時に old 引数を更新しなくなったため、runtime·xadd64 や runtime·xchg64 のようなCASループを使用する関数では、ループの各イテレーションで *addr の現在の値を明示的に old 変数に再ロードする必要が生じました。

変更前:

old = *addr;
while(!runtime·cas64(addr, &old, old+v)) {
    // nothing
}

変更後:

do {
    old = *addr; // ここで明示的なロードが必要になった
} while(!runtime·cas64(addr, old, old+v));

この old = *addr; という行は、CASが失敗するたびにメモリから値を読み込む操作を意味します。x86の CMPXCHGQ 命令は、失敗時にメモリの現在の値を RAX にロードする特性があるため、以前の実装ではこの明示的なロードは不要でした。しかし、一貫性を優先した結果、この「不必要なメモリロード」が発生することになります。

コミットメッセージでは、この効率の低下は「イプシロン（ごくわずか）」であると述べられており、コードの明確さと一貫性の方が重要であるという判断が示されています。これは、Goランタイムがパフォーマンスだけでなく、保守性や設計の健全性も重視していることを示しています。

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

このコミットのコアとなる変更は、runtime·cas64 関数の定義と、その呼び出し元のロジックにあります。

src/pkg/runtime/asm_amd64.s における runtime·cas64 の変更

--- a/src/pkg/runtime/asm_amd64.s
+++ b/src/pkg/runtime/asm_amd64.s
@@ -374,13 +374,11 @@ TEXT runtime·cas(SB), 7, $0
 //		*val = new;
 //		return 1;
 //	} else {
-//		*old = *val
 //		return 0;
 //	}
 TEXT runtime·cas64(SB), 7, $0
 	MOVQ	8(SP), BX
-\tMOVQ	16(SP), BP
-\tMOVQ	0(BP), AX
+\tMOVQ	16(SP), AX
 	MOVQ	24(SP), CX
 	LOCK
 	CMPXCHGQ	CX, 0(BX)
@@ -388,7 +386,6 @@ TEXT runtime·cas64(SB), 7, $0
 	MOVL	$1, AX
 	RET
 cas64_fail:
-\tMOVQ	AX, 0(BP)
 	MOVL	$0, AX
 	RET

• MOVQ 16(SP), BP と MOVQ 0(BP), AX が削除され、代わりに MOVQ 16(SP), AX が追加されました。
  • 以前は、スタックポインタ SP から16バイトオフセットにある old 引数のアドレスを BP レジスタにロードし、そのアドレスが指す値 (*old) を AX レジスタにロードしていました。
  • 変更後は、スタックポインタ SP から16バイトオフセットにある old 引数の「値」を直接 AX レジスタにロードします。これは old が値渡しになったことを反映しています。
• cas64_fail: ラベルの下にあった MOVQ AX, 0(BP) が削除されました。
  • 以前は、CAS操作が失敗した場合 (CMPXCHGQ が一致しなかった場合、AX にはメモリの現在の値が格納される)、その AX の値を BP が指すメモリ位置 (*old) に書き戻していました。
  • この行が削除されたことで、CAS失敗時に old 引数（値渡しされたもの）は変更されず、呼び出し元の old 変数も影響を受けなくなりました。

src/pkg/runtime/runtime.h における関数シグネチャの変更

--- a/src/pkg/runtime/runtime.h
+++ b/src/pkg/runtime/runtime.h
@@ -761,7 +761,7 @@ int32	runtime·write(int32, void*, int32);\n int32	runtime·close(int32);\n int32	runtime·mincore(void*, uintptr, byte*);\n bool	runtime·cas(uint32*, uint32, uint32);\n-bool	runtime·cas64(uint64*, uint64*, uint64);\n+bool	runtime·cas64(uint64*, uint64, uint64);\n bool	runtime·casp(void**, void*, void*);\n // Don't confuse with XADD x86 instruction,\n // this one is actually 'addx', that is, add-and-fetch.\n```

*   `runtime·cas64` の2番目の引数の型が `uint64*` (ポインタ) から `uint64` (値) に変更されました。

### 呼び出し元 (`atomic_386.c`, `lfstack.c`, `parfor.c`, `runtime.c` など) の変更

これらのファイルでは、`runtime·cas64` の呼び出し方が変更され、`&old` のようにポインタを渡していた箇所が `old` のように値を渡すようになりました。

例: `src/pkg/runtime/atomic_386.c`
```diff
--- a/src/pkg/runtime/atomic_386.c
+++ b/src/pkg/runtime/atomic_386.c
@@ -24,10 +24,10 @@ runtime·xadd64(uint64 volatile* addr, int64 v)
 {
 	uint64 old;
 
-\told = *addr;\n-\twhile(!runtime·cas64(addr, &old, old+v)) {\n-\t\t// nothing\n-\t}\n+\tdo\n+\t\told = *addr;\n+\twhile(!runtime·cas64(addr, old, old+v));\n+\n 	return old+v;
 }

• while(!runtime·cas64(addr, &old, old+v)) が do { old = *addr; } while(!runtime·cas64(addr, old, old+v)); に変更されました。
  • &old が old に変更され、値渡しになったことを示します。
  • do...while ループが導入され、ループの各イテレーションの最初に old = *addr; が追加されました。これは、cas64 が失敗時に old を更新しなくなったため、呼び出し元が明示的に最新の値を再取得する必要があるためです。

コアとなるコードの解説

runtime·cas64 アセンブリコードの変更の意図

AMD64アセンブリにおける runtime·cas64 の変更は、CMPXCHGQ 命令の特性と、CASのセマンティクスの一貫性を両立させるためのものです。

• MOVQ 16(SP), AX:

  • SP (Stack Pointer) は現在のスタックフレームの先頭を指します。引数はスタックに積まれるため、16(SP) は runtime·cas64 の2番目の引数、すなわち old の値が格納されているメモリ位置を指します。
  • この命令は、old の値を直接 AX レジスタにロードします。CMPXCHGQ 命令は AX レジスタの値を比較対象として使用するため、これは正しい準備です。
  • 以前は BP レジスタを介して *old をロードしていましたが、これは old がポインタであったためです。値渡しになったことで、直接 AX にロードできるようになりました。

• cas64_fail: ブロックからの MOVQ AX, 0(BP) の削除:

  • CMPXCHGQ 命令は、比較が失敗した場合、メモリの現在の値（つまり、*addr の現在の値）を AX レジスタに自動的にロードします。
  • 以前の実装では、この AX の値を BP が指すメモリ位置（呼び出し元の old 変数）に書き戻していました。これにより、CASが失敗しても呼び出し元の old 変数が更新されてしまうという、cas32 や casp とは異なる振る舞いをしていました。
  • この命令を削除することで、CASが失敗した場合でも、AX レジスタにロードされた値が呼び出し元の old 変数に書き戻されることはなくなります。これにより、runtime·cas64 は失敗時に old 引数を変更しないという、より一般的なCASのセマンティクスに準拠するようになりました。

呼び出し元Cコードの変更の意図

atomic_386.c や lfstack.c などにおける runtime·cas64 の呼び出し方の変更は、cas64 のセマンティクス変更に合わせたものです。

• &old から old への変更:

  • これは runtime·cas64 の関数シグネチャが uint64* から uint64 に変更されたことに直接対応しています。呼び出し元は、old 変数のアドレスではなく、その値を直接渡すようになりました。

• do { old = *addr; } while(!runtime·cas64(addr, old, old+v)); ループの導入:

  • cas64 が失敗時に old 引数を更新しなくなったため、CASループ（例えば、xadd64 や xchg64 のようなアトミックな加算や交換操作）では、ループの各イテレーションで old の値を明示的に更新する必要があります。
  • old = *addr; の行は、CAS操作を再試行する前に、addr が指すメモリ位置の最新の値を old 変数に読み込むことを保証します。これにより、次の runtime·cas64 の呼び出しで、最新の期待値を使って比較を行うことができます。
  • この変更は、CAS操作の失敗時に old 引数が自動的に更新されるというx86固有の「便利さ」を犠牲にして、より汎用的で予測可能なCASセマンティクスを採用した結果です。

これらの変更により、Goランタイム内のアトミック操作は、異なるビット幅やデータ型であっても、より統一された振る舞いをするようになり、コードの保守性と理解度が向上しました。

関連リンク

• Go言語の公式ドキュメント: https://golang.org/doc/
• Goランタイムのソースコード: https://github.com/golang/go/tree/master/src/runtime
• Compare-and-swap - Wikipedia: https://en.wikipedia.org/wiki/Compare-and-swap

参考にした情報源リンク

• Goコミット履歴: https://github.com/golang/go/commits/master
• Go CL (Change List) 10909045: https://golang.org/cl/10909045 (コミットメッセージに記載)
• x86 Assembly Language Reference Manual: Intel 64 and IA-32 Architectures Software Developer's Manuals (特にVol. 2A: Instruction Set Reference, A-M の CMPXCHG 命令の記述)
• ARM Architecture Reference Manuals (ARMのCAS命令に関する記述)
• Goのソースコード内のコメントと既存のコードパターン