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

このコミットは、Go言語の標準ライブラリ sync/atomic パッケージに、アトミックなSwap関数群を追加するものです。これにより、共有メモリ上の変数の値をアトミックに新しい値と交換し、古い値を返す操作が可能になります。

コミット

commit 0e15b03f9347bc285ce266a966b8672acb1f7194
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Tue Aug 13 15:26:48 2013 +0400

    sync/atomic: add Swap functions
    Fixes #5722.
    
    R=golang-dev, khr, cshapiro, rsc, r
    CC=golang-dev
    https://golang.org/cl/12670045

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

https://github.com/golang/go/commit/0e15b03f9347bc285ce266a966b8672acb1f7194

元コミット内容

sync/atomic: add Swap functions
Fixes #5722.

R=golang-dev, khr, cshapiro, rsc, r
CC=golang-dev
https://golang.org/cl/12670045

変更の背景

このコミットは、Go言語のIssue #5722「sync/atomic: add Swap functions」に対応するものです。このIssueでは、sync/atomicパッケージに、指定されたメモリ位置の値をアトミックに新しい値と交換し、元の値を返すSwap操作を追加することが求められていました。

Swap操作は、並行プログラミングにおいて非常に重要なプリミティブです。例えば、ロックフリーなデータ構造を実装する際や、複数のゴルーチンが共有するカウンタやフラグを安全に更新する際に利用されます。既存のCompareAndSwap（CAS）関数は、現在の値が期待値と一致する場合にのみ値を更新しますが、Swapは無条件に値を交換し、古い値を返すため、特定のシナリオでより簡潔かつ効率的なコードを記述できるようになります。

この機能の追加により、Go言語の並行処理のプリミティブがさらに充実し、開発者がより堅牢で高性能な並行アプリケーションを構築できるようになることが期待されました。

前提知識の解説

アトミック操作

アトミック操作とは、複数のCPUコアやスレッドから同時にアクセスされた場合でも、その操作全体が不可分（atomic）であり、途中で他の操作に割り込まれることなく完了することを保証する操作です。これにより、データ競合（data race）を防ぎ、共有データの整合性を保つことができます。

一般的なアトミック操作には以下のようなものがあります。

• Load: メモリから値をアトミックに読み込む。
• Store: メモリに値をアトミックに書き込む。
• Add: メモリ上の値にアトミックに加算する。
• CompareAndSwap (CAS): メモリ上の値が期待値と一致する場合にのみ、新しい値に更新し、操作が成功したかどうかを返す。
• Swap: メモリ上の値を新しい値とアトミックに交換し、古い値を返す。

これらの操作は、CPUの特別な命令（例: XCHG, CMPXCHG, LOCKプレフィックス付き命令など）や、特定のアーキテクチャで提供されるロード・ストア排他命令（例: ARMのLDREX/STREX）を利用して実装されます。

Go言語の sync/atomic パッケージ

Go言語のsync/atomicパッケージは、低レベルのアトミック操作を提供します。これにより、ミューテックスなどのより高レベルな同期プリミティブを使用せずに、共有変数を安全に操作できます。これは、パフォーマンスがクリティカルな場面や、ロックフリーなアルゴリズムを実装する際に特に有用です。

sync/atomicパッケージの関数は、Goのランタイムによって、実行されるCPUアーキテクチャに最適化されたアセンブリコードにコンパイルされます。これにより、最高のパフォーマンスと正確性が保証されます。

アセンブリ言語とCPUアーキテクチャ

このコミットでは、複数のCPUアーキテクチャ（x86/amd64, ARM）向けにアトミック操作が実装されています。それぞれのアーキテクチャには、アトミック操作を実現するための独自のアセンブリ命令セットがあります。

• x86/amd64:
  • XCHG: レジスタとメモリ間で値を交換する命令。これはアトミックな操作として保証されます。
  • CMPXCHG8B: 8バイト（64ビット）の値を比較交換する命令。これはSwapUint64のような64ビットのアトミック操作で利用されます。LOCKプレフィックスと組み合わせて使用することで、マルチプロセッサ環境でのアトミック性を保証します。
• ARM:
  • LDREX (Load-Exclusive) と STREX (Store-Exclusive): ARMv6以降で導入されたロード・ストア排他命令。LDREXで値を読み込み、STREXで書き込みを試みます。STREXが成功した場合（他のプロセッサがそのメモリ位置に書き込んでいない場合）、0を返します。失敗した場合は非ゼロを返し、再試行が必要であることを示します。これにより、CASやSwapのようなアトミック操作を実装できます。
  • LDREXD (Load-Exclusive Doubleword) と STREXD (Store-Exclusive Doubleword): 64ビット値を扱うためのLDREX/STREXの拡張版。

Goのテストフレームワーク

Goのテストは、testingパッケージを使用して記述されます。go testコマンドで実行され、テスト関数はTestで始まる名前を持ち、*testing.T型の引数を取ります。このコミットでは、新しく追加されたSwap関数の正確性とアトミック性を検証するためのテストが追加されています。特に、複数のゴルーチンが同時にアトミック操作を実行する「ハンマーテスト」が含まれており、これは並行処理の堅牢性を確認するために重要です。

技術的詳細

このコミットの主要な目的は、sync/atomicパッケージに以下のSwap関数を追加することです。

• SwapInt32(addr *int32, new int32) (old int32)
• SwapInt64(addr *int64, new int64) (old int64)
• SwapUint32(addr *uint32, new uint32) (old uint32)
• SwapUint64(addr *uint64, new uint64) (old uint64)
• SwapUintptr(addr *uintptr, new uintptr) (old uintptr)
• SwapPointer(addr *unsafe.Pointer, new unsafe.Pointer) (old unsafe.Pointer)

これらの関数は、指定されたメモリアドレスaddrにある値をnewと交換し、交換前の古い値を返します。この操作はアトミックに実行されます。

実装は、主に各アーキテクチャのアセンブリ言語で行われています。

x86 (386) および AMD64 (amd64) アーキテクチャ

• 32ビット整数 (SwapInt32, SwapUint32):
  • XCHGL命令が使用されます。XCHGL AX, 0(BP)のように、レジスタAXとメモリ位置0(BP)の値を交換します。XCHG命令は、単一のメモリ位置に対する操作において、自動的にロックされる（アトミックである）ことが保証されています。
• 64ビット整数 (SwapInt64, SwapUint64):
  • 386 (32ビットx86): 32ビットアーキテクチャでは、64ビット値を単一のアトミック命令で交換することはできません。そのため、CMPXCHG8B（Compare-Exchange 8 Bytes）命令を使用したループが実装されています。
    1. 現在のメモリ上の64ビット値（DX:AX）を読み込みます。
    2. LOCK CMPXCHG8B 0(BP)命令を実行します。これは、メモリ上の値がDX:AXと一致する場合にのみ、CX:BX（新しい値）をメモリに書き込みます。
    3. もし比較が失敗した場合（JNZ）、他のCPUがその間に値を変更したことを意味するため、ループを繰り返して再試行します。
    4. 成功した場合、DX:AXには交換前の古い値が格納されているため、それを返します。
  • AMD64 (64ビットx86): 64ビットアーキテクチャでは、XCHGQ命令が利用できます。XCHGQ AX, 0(BP)のように、64ビットレジスタAXとメモリ位置0(BP)の値をアトミックに交換します。これにより、386のような複雑なループは不要になります。
• ポインタ型 (SwapUintptr, SwapPointer):
  • アーキテクチャのポインタサイズに応じて、SwapUint32またはSwapUint64にジャンプ（JMP）することで実装されます。例えば、32ビットシステムではSwapUint32に、64ビットシステムではSwapUint64にジャンプします。

ARM アーキテクチャ

ARMアーキテクチャでは、ロード・ストア排他命令のペアであるLDREX/STREX（32ビット）およびLDREXD/STREXD（64ビット）を使用してアトミック操作を実装します。

• 32ビット整数 (armSwapUint32):
  1. LDREX (R1), R3: メモリアドレスR1から値を排他的に読み込み、R3に格納します。
  2. STREX R2, (R1), R0: R2の値をメモリアドレスR1に書き込みを試みます。この書き込みが成功した場合（排他ロックが保持されている場合）、R0は0になります。
  3. CMP $0, R0とBNE swaploop: STREXが失敗した場合（R0が非ゼロ）、他のプロセッサがその間にメモリを更新したことを意味するため、swaploopに分岐して再試行します。
  4. 成功した場合、R3には交換前の古い値が格納されているため、それを返します。
• 64ビット整数 (armSwapUint64):
  • LDREXD (R1), R4とSTREXD R2, (R1), R0を使用します。基本的なロジックは32ビットの場合と同じですが、64ビット値を扱うためにダブルワード命令が使用されます。
  • アラインメントチェックも含まれており、64ビット値へのアトミックアクセスは8バイト境界にアラインされている必要があります。アラインされていない場合はパニックを引き起こします。

64bit_arm.go

このファイルには、ARMアーキテクチャにおける64ビットアトミック操作のGo言語でのフォールバック実装が含まれています。アセンブリ実装が利用できない場合や、特定の条件下でGoコードでアトミック操作をエミュレートする必要がある場合に使用されます。 このコミットでは、swapUint64関数が追加されています。これは、CompareAndSwapUint64をループ内で使用することで、Swap操作をエミュレートしています。

func swapUint64(addr *uint64, new uint64) (old uint64) {
	for {
		old := *addr
		if CompareAndSwapUint64(addr, old, new) {
			break
		}
	}
	return
}

この実装は、CompareAndSwapが成功するまでループを繰り返すことで、アトミックなSwapを実現しています。

race.go (Race Detector のサポート)

GoのRace Detectorは、並行処理におけるデータ競合を検出するためのツールです。sync/atomicパッケージの関数がRace Detectorによって正しく監視されるように、race.goファイルにも対応するSwap関数の実装が追加されています。これらの実装は、実際のハードウェアアトミック操作ではなく、Race Detectorが競合を検出できるように、セマフォの取得/解放やメモリアクセスの記録（runtime.RaceRead, runtime.RaceAcquire, runtime.RaceReleaseMerge）を行います。

例えば、SwapUint32のRace Detector向け実装は以下のようになります。

func SwapUint32(addr *uint32, new uint32) (old uint32) {
	_ = *addr // Ensure address is valid
	runtime.RaceSemacquire(&mtx) // Acquire a semaphore for race detection
	runtime.RaceRead(unsafe.Pointer(addr)) // Record a read access
	runtime.RaceAcquire(unsafe.Pointer(addr)) // Record an acquire operation
	old = *addr // Perform the actual swap (not atomic in this context, but for race detection)
	*addr = new
	runtime.RaceReleaseMerge(unsafe.Pointer(addr)) // Record a release and merge operation
	runtime.RaceSemrelease(&mtx) // Release the semaphore
	return
}

このコードは、実際のSwap操作をエミュレートしつつ、Race Detectorに必要な情報を提供することで、アトミック操作が正しく使用されているかを検証できるようにします。

テスト (atomic_test.go)

新しいSwap関数が正しく機能することを保証するために、広範なテストが追加されています。

• TestSwapInt32, TestSwapUint32, TestSwapInt64, TestSwapUint64, TestSwapUintptr, TestSwapPointer: 各Swap関数の基本的な機能と正確性を検証します。ループ内で値を交換し、期待される結果が得られるかを確認します。
• TestHammer32, TestHammer64: 複数のゴルーチンが同時にSwap操作を実行する「ハンマーテスト」が追加されています。これは、並行環境下でのアトミック操作の堅牢性を検証するために重要です。
  • これらのテストでは、Swap操作がアトミックであることを確認するために、特定のパターン（例: 上位16ビットと下位16ビットが同じ値）を持つ擬似乱数を生成し、Swap後に古い値がそのパターンを維持しているかをチェックします。もしパターンが崩れていれば、アトミック性が破られていることを示し、パニックを発生させます。
  • init()関数内で、32ビットシステムと64ビットシステムでuintptrおよびPointer関連のテストを適切にスキップするロジックが追加されています。

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

このコミットで変更された主要なファイルと、その変更の概要は以下の通りです。

• src/pkg/sync/atomic/64bit_arm.go: ARMアーキテクチャにおけるswapUint64のGo言語フォールバック実装の追加。
• src/pkg/sync/atomic/asm_386.s: x86 (32-bit) アーキテクチャ向けのアセンブリ実装。SwapInt32, SwapUint32, SwapInt64, SwapUint64, SwapUintptr, SwapPointerの追加。特にSwapUint64はCMPXCHG8Bループを使用。
• src/pkg/sync/atomic/asm_amd64.s: AMD64 (64-bit) アーキテクチャ向けのアセンブリ実装。SwapInt32, SwapUint32, SwapInt64, SwapUint64, SwapUintptr, SwapPointerの追加。SwapUint64はXCHGQを使用。
• src/pkg/sync/atomic/asm_arm.s: ARMアーキテクチャ向けのアセンブリ実装。armSwapUint32 (LDREX/STREX) および armSwapUint64 (LDREXD/STREXD) の追加。
• src/pkg/sync/atomic/asm_freebsd_arm.s, src/pkg/sync/atomic/asm_linux_arm.s, src/pkg/sync/atomic/asm_netbsd_arm.s: 各ARMベースのOS向けに、共通のARMアセンブリ実装へのジャンプを追加。
• src/pkg/sync/atomic/atomic_test.go: 新しいSwap関数群の単体テストおよび並行テスト（ハンマーテスト）の追加。
• src/pkg/sync/atomic/doc.go: Swap関数のドキュメントと、その操作のセマンティクス（old = *addr; *addr = new; return old）の記述を追加。
• src/pkg/sync/atomic/race.go: Go Race DetectorがSwap操作を正しく監視できるようにするための、Race Detector対応の実装を追加。

コアとなるコードの解説

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

TEXT ·SwapUint32(SB),NOSPLIT,$0-12
	MOVL	addr+0(FP), BP
	MOVL	new+4(FP), AX
	XCHGL	AX, 0(BP)
	MOVL	AX, new+8(FP)
	RET

TEXT ·SwapUint64(SB),NOSPLIT,$0-20
	// no XCHGQ so use CMPXCHG8B loop
	MOVL	addr+0(FP), BP
	TESTL	$7, BP
	JZ	2(PC)
	MOVL	0, AX // crash with nil ptr deref
	// CX:BX = new
	MOVL	new_lo+4(FP), BX
	MOVL	new_hi+8(FP), CX
	// DX:AX = *addr
	MOVL	0(BP), AX
	MOVL	4(BP), DX
swaploop:
	// if *addr == DX:AX
	//	*addr = CX:BX
	// else
	//	DX:AX = *addr
	// all in one instruction
	LOCK
	CMPXCHG8B	0(BP)
	JNZ	swaploop

	// success
	// return DX:AX
	MOVL	AX, new_lo+12(FP)
	MOVL	DX, new_hi+16(FP)
	RET

• SwapUint32: XCHGL命令は、レジスタAXとメモリ位置0(BP)の値をアトミックに交換します。交換後、AXには古い値が格納されているため、それを戻り値として設定します。
• SwapUint64: 32ビット環境で64ビット値をアトミックに交換するため、CMPXCHG8B命令をループで使用します。LOCKプレフィックスは、マルチプロセッサ環境でのアトミック性を保証します。ループは、CMPXCHG8Bが成功するまで（JNZが分岐しないまで）繰り返されます。

src/pkg/sync/atomic/asm_amd64.s (AMD64 64-bit)

TEXT ·SwapUint64(SB),NOSPLIT,$0-24
	MOVQ	addr+0(FP), BP
	MOVQ	new+8(FP), AX
	XCHGQ	AX, 0(BP)
	MOVQ	AX, new+16(FP)
	RET

• SwapUint64: 64ビット環境では、XCHGQ命令が利用できるため、単一のアトミック命令で64ビット値を交換できます。これにより、386のような複雑なループは不要です。

src/pkg/sync/atomic/asm_arm.s (ARM)

TEXT ·armSwapUint32(SB),NOSPLIT,$0-12
	MOVW	addr+0(FP), R1
	MOVW	new+4(FP), R2
swaploop:
	// LDREX and STREX were introduced in ARM 6.
	LDREX	(R1), R3
	STREX	R2, (R1), R0
	CMP	$0, R0
	BNE	swaploop
	MOVW	R3, old+8(FP)
	RET

TEXT ·armSwapUint64(SB),NOSPLIT,$0-20
	BL	fastCheck64<>(SB) // Check for 64-bit alignment
	MOVW	addr+0(FP), R1
	// make unaligned atomic access panic
	AND.S	$7, R1, R2
	BEQ 	2(PC)
	MOVW	R2, (R2) // This will cause a panic if not aligned
	MOVW	newlo+4(FP), R2
	MOVW	newhi+8(FP), R3
swap64loop:
	// LDREXD and STREXD were introduced in ARM 11.
	LDREXD	(R1), R4	// loads R4 and R5
	STREXD	R2, (R1), R0	// stores R2 and R3
	CMP	$0, R0
	BNE	swap64loop
	MOVW	R4, oldlo+12(FP)
	MOVW	R5, oldhi+16(FP)
	RET

• armSwapUint32: LDREXとSTREX命令のペアを使用して、32ビット値をアトミックに交換します。STREXが失敗した場合（R0が非ゼロ）、ループを再試行します。
• armSwapUint64: LDREXDとSTREXD命令のペアを使用して、64ビット値をアトミックに交換します。64ビット値のアラインメントチェックも含まれています。

src/pkg/sync/atomic/atomic_test.go

func TestSwapUint32(t *testing.T) {
	var x struct {
		before uint32
		i      uint32
		after  uint32
	}
	x.before = magic32
	x.after = magic32
	var j uint32
	for delta := uint32(1); delta+delta > delta; delta += delta {
		k := SwapUint32(&x.i, delta)
		if x.i != delta || k != j {
			t.Fatalf("delta=%d i=%d j=%d k=%d", delta, x.i, j, k)
		}
		j = delta
	}
	if x.before != magic32 || x.after != magic32 {
		t.Fatalf("wrong magic: %#x _ %#x != %#x _ %#x", x.before, x.after, magic32, magic32)
	}
}

func hammerSwapUint32(addr *uint32, count int) {
	seed := int(uintptr(unsafe.Pointer(&count)))
	for i := 0; i < count; i++ {
		new := uint32(seed+i)<<16 | uint32(seed+i)<<16>>16
		old := SwapUint32(addr, new)
		if old>>16 != old<<16>>16 {
			panic(fmt.Sprintf("SwapUint32 is not atomic: %v", old))
		}
	}
}

• TestSwapUint32: SwapUint32関数の基本的な動作を検証します。x.beforeとx.afterという「マジック値」を構造体の前後に配置することで、Swap操作が意図しないメモリ領域を破壊していないことを確認します。
• hammerSwapUint32: 複数のゴルーチンから同時にSwapUint32を呼び出す「ハンマーテスト」の一部です。生成されるnew値は、上位16ビットと下位16ビットが同じになるように設計されています。Swapによって返されたold値も同じパターンを維持しているかをチェックすることで、操作がアトミックに行われたことを検証します。もしパターンが崩れていれば、データ競合が発生したことを示し、テストはパニックします。

関連リンク

• Go Issue #5722: sync/atomic: add Swap functions: https://github.com/golang/go/issues/5722
• Go CL 12670045: sync/atomic: add Swap functions: https://golang.org/cl/12670045

参考にした情報源リンク

• Go言語 sync/atomic パッケージドキュメント: https://pkg.go.dev/sync/atomic
• Intel 64 and IA-32 Architectures Software Developer's Manuals (特にVol. 2A: Instruction Set Reference, A-M): https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
• ARM Architecture Reference Manuals (特にARMv6, ARMv7, ARMv8の命令セット): https://developer.arm.com/documentation/
• Go Assembly Language (Goアセンブリの基本): https://go.dev/doc/asm
• Go Race Detector: https://go.dev/doc/articles/race_detector
• Compare-and-swap (Wikipedia): https://en.wikipedia.org/wiki/Compare-and-swap
• Atomic operations (Wikipedia): https://en.wikipedia.org/wiki/Atomic_operations