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

このコミットは、Go言語のランタイムにおけるAESハッシュ処理の最適化に関するものです。具体的には、x86およびx86-64アーキテクチャのアセンブリコードにおいて、AESキーのスケジューリングに使用されるメモリロード命令をMOVOUからMOVOに変更することで、アラインメントされたロードを強制し、パフォーマンスと安定性を向上させています。

コミット

commit db53d97ac494397f8b11ad66c83b7662eb84d5d3
Author: Keith Randall <khr@golang.org>
Date:   Wed Mar 20 14:34:26 2013 -0700

    runtime: Use aligned loads for AES key schedule.
    
    R=rsc, minux.ma, khr
    CC=golang-dev
    https://golang.org/cl/7763050

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

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

元コミット内容

runtime: Use aligned loads for AES key schedule.

R=rsc, minux.ma, khr
CC=golang-dev
https://golang.org/cl/7763050

この変更の背景には、x86およびx86-64アーキテクチャにおけるSIMD（Single Instruction, Multiple Data）命令、特にSSE（Streaming SIMD Extensions）やAVX（Advanced Vector Extensions）命令セットを用いたメモリ操作の特性があります。これらの命令セットには、メモリからデータをレジスタにロードする際に、メモリのアラインメント（整列）を要求するものと、要求しないものがあります。

AES（Advanced Encryption Standard）のような暗号化アルゴリズムでは、キーのスケジューリングやデータの暗号化・復号化において、固定サイズのブロック（通常128ビット、すなわち16バイト）を効率的に処理する必要があります。この処理には、SIMDレジスタ（例: XMMレジスタ）へのデータのロードが頻繁に発生します。

従来のコードではMOVOU命令が使用されていました。MOVOUは"Move Unaligned Oword"の略で、メモリのアラインメントを気にせずに128ビット（16バイト）のデータをXMMレジスタにロードする命令です。これは柔軟性がある一方で、データがアラインメントされていない場合にパフォーマンスのペナルティが発生する可能性があります。特に、キャッシュライン境界をまたぐようなアンアラインメントなアクセスは、CPUのパイプラインストールを引き起こし、処理速度を低下させる要因となります。

AESキーのスケジューリングデータは、通常、プログラムの初期化段階で一度計算され、その後は固定されたメモリ領域に格納されます。このような静的なデータに対しては、メモリを適切にアラインメントして配置することが可能です。このコミットは、AESキーのスケジューリングデータが常にアラインメントされているという前提に基づき、より効率的なロード命令を使用することで、ランタイムのパフォーマンスを向上させることを目的としています。

前提知識の解説

1. x86/x86-64アセンブリ言語

IntelおよびAMDのCPUで使用される低レベルのプログラミング言語です。CPUが直接実行する機械語命令に対応しており、レジスタ操作、メモリアクセス、算術演算、論理演算、制御フローなどを直接制御します。Go言語のランタイムや標準ライブラリの一部は、パフォーマンスが重要な部分でアセンブリ言語で記述されています。

2. SIMD命令セット (SSE/AVX)

SIMDは「Single Instruction, Multiple Data」の略で、一つの命令で複数のデータを同時に処理する並列処理の方式です。x86アーキテクチャでは、SSE（Streaming SIMD Extensions）やAVX（Advanced Vector Extensions）といった命令セットがこれに該当します。これらは、画像処理、音声処理、科学技術計算、暗号化など、大量のデータを並列に処理するアプリケーションで高いパフォーマンスを発揮します。

XMMレジスタ: SSE命令で使用される128ビット幅のレジスタです。16バイトのデータを格納できます。
YMMレジスタ: AVX命令で使用される256ビット幅のレジスタです。32バイトのデータを格納できます。

3. メモリのアラインメント

メモリのアラインメントとは、データがメモリ上で特定のバイト境界に配置されることを指します。例えば、4バイトの整数は4の倍数のアドレスに、16バイトのデータは16の倍数のアドレスに配置されるといった具合です。

アラインメントされたアクセス: データがその型や命令が要求する境界に正確に配置されている場合のアクセスです。CPUは効率的にデータをロード・ストアできます。
アンアラインメントされたアクセス: データが要求される境界に配置されていない場合のアクセスです。CPUは追加のサイクルを費やしてデータをロードする必要があり、パフォーマンスが低下したり、場合によってはハードウェア例外（アラインメントフォルト）が発生したりすることがあります。

4. `MOVOU`と`MOVO`命令

これらはSSE命令セットにおけるメモリロード命令です。

MOVOU (Move Unaligned Oword):
- メモリからXMMレジスタへ128ビット（16バイト）のデータをロードします。
- ソースアドレスが16バイト境界にアラインメントされている必要はありません。
- 柔軟性がありますが、アンアラインメントなアクセスの場合、パフォーマンスのオーバーヘッドが発生する可能性があります。
MOVO (Move Aligned Oword):
- メモリからXMMレジスタへ128ビット（16バイト）のデータをロードします。
- ソースアドレスが16バイト境界にアラインメントされていることを要求します。
- アラインメントが保証されている場合、MOVOUよりも高速に動作します。アラインメントされていないアドレスに対してこの命令を使用すると、一般的にはハードウェア例外（General Protection Faultなど）が発生します。

5. AES命令セット (AES-NI)

IntelとAMDの最新のCPUには、AES暗号化アルゴリズムをハードウェアレベルで高速化するための専用命令セット（AES-NI: Advanced Encryption Standard New Instructions）が搭載されています。これにより、ソフトウェアによる実装よりもはるかに高速にAES処理を実行できます。

AESENC: AESのラウンド暗号化を実行する命令です。キーとデータを受け取り、暗号化された中間結果を生成します。

6. AESキーのスケジューリング

AESはブロック暗号であり、暗号化・復号化のプロセスで「ラウンドキー」と呼ばれる複数のキーを使用します。これらのラウンドキーは、元の秘密鍵から「キーのスケジューリング」と呼ばれるプロセスによって導出されます。キーのスケジューリングは、暗号化・復号化の開始前に一度だけ行われ、生成されたラウンドキーはメモリに格納され、各ラウンドで再利用されます。

技術的詳細

このコミットの核心は、GoランタイムのAESハッシュ関数において、AESキーのスケジューリングデータをロードする際に使用するアセンブリ命令をMOVOUからMOVOに変更した点にあります。

Go言語のランタイムは、内部でハッシュ関数としてAES命令セットを利用した高速なハッシュ関数（runtime.aeshashstr, runtime.aeshashbody, runtime.aeshash32, runtime.aeshash64など）を使用しています。これらのハッシュ関数は、AESの暗号化命令（AESENC）をデータのハッシュ計算に応用しています。

AES命令を使用する際、キーのスケジューリングデータ（runtime.aeskeysched）は、通常、プログラムの起動時に一度だけ初期化され、メモリ上に配置されます。このデータは、AES命令が効率的にアクセスできるように、16バイト境界にアラインメントされて配置されることが期待されます。

変更前 (MOVOU): MOVOU命令は、ソースアドレスがアラインメントされているかどうかに関わらずデータをロードできます。これは柔軟ですが、アラインメントが保証されている場合でも、CPUはアンアラインメントなアクセスを処理するための追加のロジックを実行する必要があるため、わずかながらオーバーヘッドが発生する可能性があります。また、コンパイラやリンカがruntime.aeskeyschedを常に16バイトアラインメントで配置することを保証しない環境や設定では、MOVOUが安全な選択肢となります。しかし、Goランタイムのような低レベルのコードでは、メモリレイアウトを厳密に制御できるため、より効率的な命令を選択する余地があります。
変更後 (MOVO): MOVO命令は、ソースアドレスが16バイト境界にアラインメントされていることを要求します。この要求が満たされている場合、CPUはより直接的かつ高速にデータをXMMレジスタにロードできます。アラインメントが保証されているという前提のもとでMOVOを使用することで、命令の実行効率が向上し、結果としてハッシュ計算のパフォーマンスが改善されます。もしruntime.aeskeyschedがアラインメントされていない状態でMOVOが実行されると、プログラムはクラッシュする可能性が高いですが、Goランタイムのメモリ管理とアラインメントの保証により、このリスクは回避されます。

この変更は、GoランタイムがAESキーのスケジューリングデータを常に16バイト境界にアラインメントして配置しているという内部的な保証に基づいています。これにより、より効率的なMOVO命令を使用することが可能になり、全体的なパフォーマンスの向上が期待されます。

また、AESENC命令のオペランドの変更も行われています。変更前は、runtime.aeskeyschedからロードしたキーをX2, X3レジスタに格納し、それらのレジスタをAESENCのオペランドとして使用していました。変更後は、AESENC命令の第1オペランドとしてメモリ上のruntime.aeskeyschedを直接指定しています。これは、AESENC命令がメモリオペランドをサポートしているため可能であり、中間レジスタへのロードを省略することで、命令数を減らし、コードの簡潔さと効率性を向上させています。

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

変更は、src/pkg/runtime/asm_386.sとsrc/pkg/runtime/asm_amd64.sの2つのファイルにわたっています。これらはそれぞれ、32ビットx86および64ビットx86-64アーキテクチャ向けのアセンブリコードファイルです。

`src/pkg/runtime/asm_386.s`

--- a/src/pkg/runtime/asm_386.s
+++ b/src/pkg/runtime/asm_386.s
@@ -742,8 +742,8 @@ TEXT runtime·aeshashstr(SB),7,$0
 TEXT runtime·aeshashbody(SB),7,$0
  	MOVL	(DX), X0	// seed to low 32 bits of xmm0
  	PINSRD	$1, CX, X0	// size to next 32 bits of xmm0
-	MOVOU	runtime·aeskeysched+0(SB), X2
-	MOVOU	runtime·aeskeysched+16(SB), X3
+	MOVO	runtime·aeskeysched+0(SB), X2
+	MOVO	runtime·aeskeysched+16(SB), X3
 aesloop:
  	CMPL	CX, $16
  	JB	aesloopend
@@ -791,11 +791,9 @@ TEXT runtime·aeshash32(SB),7,$0
  	MOVL	12(SP), AX	// ptr to data
  	MOVL	(DX), X0	// seed
  	PINSRD	$1, (AX), X0	// data
-	MOVOU	runtime·aeskeysched+0(SB), X2
-	MOVOU	runtime·aeskeysched+16(SB), X3
-	AESENC	X2, X0
-	AESENC	X3, X0
-	AESENC	X2, X0
+	AESENC	runtime·aeskeysched+0(SB), X0
+	AESENC	runtime·aeskeysched+16(SB), X0
+	AESENC	runtime·aeskeysched+0(SB), X0
  	MOVL	X0, (DX)
  	RET
  
@@ -804,11 +802,9 @@ TEXT runtime·aeshash64(SB),7,$0
  	MOVL	12(SP), AX	// ptr to data
  	MOVQ	(AX), X0	// data
  	PINSRD	$2, (DX), X0	// seed
-	MOVOU	runtime·aeskeysched+0(SB), X2
-	MOVOU	runtime·aeskeysched+16(SB), X3
-	AESENC	X2, X0
-	AESENC	X3, X0
-	AESENC	X2, X0
+	AESENC	runtime·aeskeysched+0(SB), X0
+	AESENC	runtime·aeskeysched+16(SB), X0
+	AESENC	runtime·aeskeysched+0(SB), X0
  	MOVL	X0, (DX)
  	RET

`src/pkg/runtime/asm_amd64.s`

--- a/src/pkg/runtime/asm_amd64.s
+++ b/src/pkg/runtime/asm_amd64.s
@@ -762,8 +762,8 @@ TEXT runtime·aeshashstr(SB),7,$0
 TEXT runtime·aeshashbody(SB),7,$0
  	MOVQ	(DX), X0	// seed to low 64 bits of xmm0
  	PINSRQ	$1, CX, X0	// size to high 64 bits of xmm0
-	MOVOU	runtime·aeskeysched+0(SB), X2
-	MOVOU	runtime·aeskeysched+16(SB), X3
+	MOVO	runtime·aeskeysched+0(SB), X2
+	MOVO	runtime·aeskeysched+16(SB), X3
 aesloop:
  	CMPQ	CX, $16
  	JB	aesloopend
@@ -811,11 +811,9 @@ TEXT runtime·aeshash32(SB),7,$0
  	MOVQ	24(SP), AX	// ptr to data
  	MOVQ	(DX), X0	// seed
  	PINSRD	$2, (AX), X0	// data
-	MOVOU	runtime·aeskeysched+0(SB), X2
-	MOVOU	runtime·aeskeysched+16(SB), X3
-	AESENC	X2, X0
-	AESENC	X3, X0
-	AESENC	X2, X0
+	AESENC	runtime·aeskeysched+0(SB), X0
+	AESENC	runtime·aeskeysched+16(SB), X0
+	AESENC	runtime·aeskeysched+0(SB), X0
  	MOVQ	X0, (DX)
  	RET
  
@@ -824,11 +822,9 @@ TEXT runtime·aeshash64(SB),7,$0
  	MOVQ	24(SP), AX	// ptr to data
  	MOVQ	(DX), X0	// seed
  	PINSRQ	$1, (AX), X0	// data
-	MOVOU	runtime·aeskeysched+0(SB), X2
-	MOVOU	runtime·aeskeysched+16(SB), X3
-	AESENC	X2, X0
-	AESENC	X3, X0
-	AESENC	X2, X0
+	AESENC	runtime·aeskeysched+0(SB), X0
+	AESENC	runtime·aeskeysched+16(SB), X0
+	AESENC	runtime·aeskeysched+0(SB), X0
  	MOVQ	X0, (DX)
  	RET

コアとなるコードの解説

各ファイルにおいて、以下の2種類の変更が行われています。

MOVOUからMOVOへの変更:
- runtime·aeshashstrおよびruntime·aeshashbody関数内で、runtime·aeskeyschedからXMMレジスタ（X2, X3）へデータをロードする命令がMOVOUからMOVOに変更されています。
- 具体的には、MOVOU runtime·aeskeysched+0(SB), X2 が MOVO runtime·aeskeysched+0(SB), X2 に、 MOVOU runtime·aeskeysched+16(SB), X3 が MOVO runtime·aeskeysched+16(SB), X3 に変更されています。
- これは、AESキーのスケジューリングデータが16バイト境界にアラインメントされていることを前提とし、より効率的なアラインメントロード命令を使用することでパフォーマンスを向上させるための変更です。
AESENC命令のオペランドの変更とレジスタロードの削除:
- runtime·aeshash32およびruntime·aeshash64関数内で、AESENC命令の使い方が変更されています。
- 変更前は、まずMOVOUでキーデータをX2, X3レジスタにロードし、その後AESENC X2, X0やAESENC X3, X0のようにレジスタをオペランドとして使用していました。
- 変更後は、MOVOUによるレジスタへのロードが削除され、AESENC命令の第1オペランドとしてメモリ上のruntime·aeskeyschedを直接指定する形に変更されています。
- 具体的には、AESENC runtime·aeskeysched+0(SB), X0 や AESENC runtime·aeskeysched+16(SB), X0 のように記述されています。
- これは、AESENC命令がメモリオペランドを直接サポートしているため、中間レジスタへのロードを省略することで、命令数を減らし、コードをより簡潔かつ効率的にするための最適化です。これにより、CPUのレジスタ圧迫も軽減され、パイプラインの効率も向上する可能性があります。

これらの変更は、GoランタイムがAESハッシュ処理を行う際の低レベルな最適化であり、CPUの特性を最大限に活用してパフォーマンスを向上させることを目的としています。

参考にした情報源リンク

https://github.com/golang/go/commit/db53d97ac494397f8b11ad66c83b7662eb84d5d3
https://golang.org/cl/7763050 (Go Code Reviewの変更リスト)
x86アセンブリ命令に関する一般的な知識（MOVOU, MOVO, AESENCなど）
SIMD命令セットとメモリのアラインメントに関する一般的な知識
AES暗号化アルゴリズムとキーのスケジューリングに関する一般的な知識
Go言語のランタイムの構造に関する一般的な知識

comemo