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

このコミットは、Go言語の crypto/rc4 パッケージにおけるRC4暗号の実装、特にAMD64アーキテクチャ向けのアセンブリコードを最適化し、パフォーマンスを大幅に向上させることを目的としています。主な変更点は、データと鍵ストリームのXOR演算を64ビット単位から128ビット単位に拡張し、ステートロードのパイプライン処理を改善することで、スループットを向上させています。

コミット

crypto/rc4: faster amd64 implementation

XOR key into data 128 bits at a time instead of 64 bits
and pipeline half of state loads. Rotate loop to allow
single-register indexing for state[i].

On a MacBookPro10,2 (Core i5):

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128          412          224  -45.63%
BenchmarkRC4_1K          3179         1613  -49.26%
BenchmarkRC4_8K         25223        12545  -50.26%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128       310.51       570.42    1.84x
BenchmarkRC4_1K        322.09       634.48    1.97x
BenchmarkRC4_8K        320.97       645.32    2.01x

For comparison, on the same machine, openssl 0.9.8r reports
its rc4 speed as somewhat under 350 MB/s for both 1K and 8K
(it is operating 64 bits at a time).

On an Intel Xeon E5520:

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128          418          259  -38.04%
BenchmarkRC4_1K          3200         1884  -41.12%
BenchmarkRC4_8K         25173        14529  -42.28%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128       306.04       492.48    1.61x
BenchmarkRC4_1K        319.93       543.26    1.70x
BenchmarkRC4_8K         321.61       557.20    1.73x

For comparison, on the same machine, openssl 1.0.1
reports its rc4 speed as 587 MB/s for 1K and 601 MB/s for 8K.

R=agl
CC=golang-dev
https://golang.org/cl/7865046

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

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

元コミット内容

crypto/rc4: faster amd64 implementation

XOR key into data 128 bits at a time instead of 64 bits
and pipeline half of state loads. Rotate loop to allow
single-register indexing for state[i].

On a MacBookPro10,2 (Core i5):

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128          412          224  -45.63%
BenchmarkRC4_1K          3179         1613  -49.26%
BenchmarkRC4_8K         25223        12545  -50.26%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128       310.51       570.42    1.84x
BenchmarkRC4_1K        322.09       634.48    1.97x
BenchmarkRC4_8K        320.97       645.32    2.01x

For comparison, on the same machine, openssl 0.9.8r reports
its rc4 speed as somewhat under 350 MB/s for both 1K and 8K
(it is operating 64 bits at a time).

On an Intel Xeon E5520:

benchmark           old ns/op    new ns/op    delta
BenchmarkRC4_128          418          259  -38.04%
BenchmarkRC4_1K          3200         1884  -41.12%
BenchmarkRC4_8K         25173        14529  -42.28%

benchmark            old MB/s     new MB/s  speedup
BenchmarkRC4_128       306.04       492.48    1.61x
BenchmarkRC4_1K        319.93       543.26    1.70x
BenchmarkRC4_8K        321.61       557.20    1.73x

For comparison, on the same machine, openssl 1.0.1
reports its rc4 speed as 587 MB/s for 1K and 601 MB/s for 8K.

R=agl
CC=golang-dev
https://golang.org/cl/7865046

変更の背景

RC4は、かつて広く利用されたストリーム暗号ですが、現代の暗号技術と比較してセキュリティ上の脆弱性が指摘されており、現在では推奨されていません。しかし、既存のシステムやプロトコルとの互換性のために、一部でその実装が残されています。

このコミットの背景には、Go言語の標準ライブラリにおける暗号アルゴリズムのパフォーマンス最適化という継続的な取り組みがあります。特に、RC4のような計算負荷の高いアルゴリズムでは、CPUの特性を最大限に活用するアセンブリ言語による最適化が重要となります。

従来のRC4実装では、鍵ストリームとデータのXOR演算が64ビット単位で行われていました。しかし、現代のAMD64プロセッサは、SSE (Streaming SIMD Extensions) やAVX (Advanced Vector Extensions) といったSIMD (Single Instruction, Multiple Data) 命令セットをサポートしており、これらを利用することで、より大きなデータブロック（例えば128ビットや256ビット）に対して並列に演算を実行できます。これにより、同じ処理をより少ない命令数で、かつCPUのパイプラインを効率的に利用して実行できるようになり、大幅なパフォーマンス向上が期待できます。

このコミットは、特にAMD64アーキテクチャにおいて、RC4の鍵ストリーム生成とデータXOR処理のボトルネックを解消し、スループットを向上させることを目的としています。ベンチマーク結果が示すように、MacBookPro (Core i5) およびIntel Xeon E5520の両方で、処理速度が約1.7倍から2倍に向上しており、これはOpenSSLの同等機能と比較しても遜色ない、あるいはそれを上回る性能改善です。

前提知識の解説

RC4 (Rivest Cipher 4)

RC4は、Ron Rivestによって開発されたストリーム暗号です。鍵スケジュールアルゴリズム (KSA) と擬似乱数生成アルゴリズム (PRGA) の2つのフェーズで構成されます。

1. 鍵スケジュールアルゴリズム (KSA): 256バイトのS-box（置換表）を初期化し、与えられた秘密鍵に基づいてS-boxの要素をシャッフルします。
2. 擬似乱数生成アルゴリズム (PRGA): シャッフルされたS-boxからバイト単位で擬似乱数（鍵ストリーム）を生成します。この鍵ストリームは、平文とXOR演算されることで暗号文が生成され、復号時には暗号文とXOR演算されることで平文が復元されます。

RC4はシンプルで高速なため、SSL/TLSやWEPなどのプロトコルで広く利用されましたが、鍵の脆弱性や鍵ストリームの統計的偏りなどの問題が発見され、現在では非推奨とされています。

アセンブリ言語とGo言語のアセンブリ

アセンブリ言語は、CPUが直接実行できる機械語と1対1に対応する低レベルプログラミング言語です。特定のCPUアーキテクチャ（例: AMD64, ARM）に特化しており、ハードウェアの機能を最大限に引き出すために使用されます。

Go言語では、パフォーマンスが重要な部分や、特定のハードウェア機能（SIMD命令など）を利用するために、Goアセンブリと呼ばれる独自のアセンブリ言語が使用されます。これはPlan 9アセンブラの構文に基づいており、一般的なGAS (GNU Assembler) 構文とは異なります。Goアセンブリは、Goの関数呼び出し規約やメモリモデルと統合されており、Goコードからシームレスに呼び出すことができます。

CPUアーキテクチャと最適化の概念

• SIMD (Single Instruction, Multiple Data): 一つの命令で複数のデータ要素に対して同じ演算を同時に実行する並列処理の形態です。AMD64プロセッサでは、SSEやAVXといった命令セットがこれに該当し、XMMレジスタ（128ビット）やYMMレジスタ（256ビット）を使用して、複数のバイトやワードを一度に処理できます。
• パイプライン処理: CPUが複数の命令を同時に異なるステージで処理することで、命令実行のスループットを向上させる技術です。データ依存性やリソース競合があるとパイプラインがストール（停止）し、パフォーマンスが低下します。最適化では、これらのストールを避けるように命令の順序を調整したり、独立した処理を並列に実行したりします。
• レジスタ割り当て: CPUのレジスタは非常に高速なメモリであり、頻繁にアクセスされるデータをレジスタに保持することで、メモリアクセスによる遅延を減らすことができます。アセンブリコードの最適化では、レジスタを効率的に使用し、メモリへのアクセス回数を最小限に抑えることが重要です。
• ループアンローリング: ループの反復回数を減らすために、ループ本体のコードを複数回コピーして展開する最適化手法です。これにより、ループのオーバーヘッド（カウンタのインクリメント、条件チェック、ジャンプなど）を削減できます。
• キャッシュ: CPUはメインメモリよりも高速なキャッシュメモリを持っており、頻繁にアクセスされるデータをキャッシュに保持します。データアクセスパターンを最適化し、キャッシュヒット率を高めることで、パフォーマンスを向上させることができます。

技術的詳細

このコミットの主要な最適化は、RC4の鍵ストリーム生成とデータXOR処理におけるAMD64プロセッサのSIMD能力の活用にあります。

1. 128ビット単位のXOR演算:

   • 従来のRC4実装では、鍵ストリームのバイトを生成し、それをデータのバイトとXORするという処理を繰り返していました。これは通常、64ビットレジスタ（R8など）に8バイトの鍵ストリームを蓄積し、その後8バイト単位でデータとXORしていました。
   • このコミットでは、XMMレジスタ（X0, X1など）を利用して、一度に128ビット（16バイト）の鍵ストリームを生成し、データとXORするように変更されています。これにより、同じ量のデータを処理するために必要な命令数が減り、CPUの実行ユニットをより効率的に利用できます。
   • 具体的には、PSLLQ (Packed Shift Left Logical Quadword) や PXOR (Packed XOR) といったSSE命令が使用され、XMMレジスタ内の複数のデータ要素に対して並列に操作が行われます。

2. ステートロードのパイプライン処理:

   • RC4の鍵ストリーム生成では、S-box (c.s配列) へのアクセスが頻繁に発生します。これらのメモリロードは、CPUのパイプラインをストールさせる原因となる可能性があります。
   • 新しい実装では、KEYROUNDマクロ内でLOADマクロを使用し、次のラウンドで必要となるS-boxの値を事前にロードすることで、メモリロードのレイテンシを隠蔽し、パイプラインのストールを軽減しています。これは、CPUが現在の演算を完了する前に、次の演算に必要なデータをフェッチしておく「プリフェッチ」のような効果をもたらします。
   • KEYROUNDマクロは、16バイトの鍵ストリームを生成するために、S-boxから16個のバイトを読み込み、それらをXMMレジスタに挿入します。この際、PINSRW命令が使用され、S-boxから読み込んだバイトをXMMレジスタの特定の16ビット位置に挿入します。

3. ループの回転と単一レジスタインデックス:

   • 元のコードでは、ループ内でS-boxへのアクセスに複数のレジスタを使用していた可能性があります。
   • 最適化されたコードでは、ループ構造を回転させ、state[i]のようなアクセスパターンに対して、単一のレジスタ（例: R12）をベースアドレスとして使用し、オフセットでアクセスするように変更されています。これにより、アドレス計算が簡素化され、レジスタの競合が減少し、CPUの実行効率が向上します。特に、LEAQ (BP)(CX*4), R12 のように、S-boxのベースアドレスを計算し、その後のアクセスを (off*4)(R12) のようにオフセットで指定することで、アドレス計算のオーバーヘッドを削減しています。

4. rc4.go の s フィールドの型変更:

   • Cipher構造体の s フィールドが [256]byte から [256]uint32 に変更されています。これは、アセンブリコードがS-boxの要素を4バイト単位でアクセスすることを可能にするための変更です。RC4のS-boxは実際にはバイト値（0-255）を格納しますが、uint32として宣言することで、アセンブリコードがワード単位でロードし、その下位バイトのみを使用するといった最適化が可能になります。これにより、メモリのアライメントが改善され、より効率的なメモリアクセスが可能になる場合があります。

これらの変更により、ベンチマーク結果が示すように、RC4の暗号化/復号処理のスループットが大幅に向上しています。特に、OpenSSLのRC4実装と比較しても、GoのRC4実装が同等以上の性能を発揮するようになっています。

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

このコミットでは、主に以下のファイルが変更されています。

1. src/cmd/6l/optab.c:

   • Goのアセンブラ（6lはAMD64リンカ）が使用する命令テーブル optab に、新しい命令パターン yinsrw が追加されています。これは、PINSRW命令（Packed Insert Word）のオペランドパターンを定義しています。
   • APINSRW命令の定義が yextrw から yinsrw に変更されています。これは、PINSRW命令の正しいオペランド解釈をリンカに伝えるための変更です。

2. src/pkg/crypto/rc4/rc4.go:

   • Cipher構造体の s フィールドの型が [256]byte から [256]uint32 に変更されています。
   • NewCipher関数内で、c.s[i] = uint8(i) が c.s[i] = uint32(i) に、j += c.s[i] + key[i%k] が j += uint8(c.s[i]) + key[i%k] に変更されています。これは、s の型変更に伴う修正です。

3. src/pkg/crypto/rc4/rc4_386.s:

   • 32ビット版（i386）のアセンブリコードでも、S-boxへのアクセスがバイト単位 (*1) からワード単位 (*4) に変更されています。これは、rc4.go で s が uint32 に変更されたことに対応するためです。MOVBLZX (BP)(AX*1), DX が MOVBLZX (BP)(AX*4), DX のように変更されています。

4. src/pkg/crypto/rc4/rc4_amd64.s:

   • このファイルが最も大きく変更されています。AMD64アーキテクチャ向けのアセンブリ実装です。
   • コメントが追加され、128ビット単位のXOR演算とパイプライン処理の意図が説明されています。
   • xorKeyStream 関数のメインループが大幅に書き換えられています。
   • KEYROUND, LOAD, SKIP という新しいマクロが定義され、鍵ストリーム生成とS-boxアクセスを効率化しています。
   • XMMレジスタ (X0, X1, X2) を使用した128ビット単位のデータ処理が導入されています。
   • ループの構造が変更され、wordloop と start ラベルで16バイト単位の処理を行い、残りのバイトを l1 と l2 で1バイトずつ処理するようになっています。

5. src/pkg/crypto/rc4/rc4_arm.s:

   • ARMアーキテクチャ向けのアセンブリコードでも、S-boxへのアクセスがバイト単位 (<<0) からワード単位 (<<2、つまり *4) に変更されています。これも rc4.go の s の型変更に対応するためです。

6. src/pkg/crypto/rc4/rc4_asm.go:

   • xorKeyStream 関数のGo側の宣言が、state *[256]byte から state *[256]uint32 に変更されています。これは、アセンブリ関数が受け取るS-boxの型をGo側と一致させるためです。

7. src/pkg/crypto/rc4/rc4_test.go:

   • TestBlock という新しいテスト関数が追加されています。これは、RC4の XORKeyStream 関数がブロック単位で正しく動作するかどうかを検証するためのものです。1バイトずつ処理した場合と、大きなブロックを一度に処理した場合で結果が一致するかを確認しています。

コアとなるコードの解説

最も重要な変更は src/pkg/crypto/rc4/rc4_amd64.s にあります。

src/pkg/crypto/rc4/rc4_amd64.s の主要な変更点

• コメントの追加:

  // The new EXTEND macros avoid a bad stall on some systems after 8-bit math.
  //
  // The original code accumulated 64 bits of key stream in an integer
  // register and then XOR'ed the key stream into the data 8 bytes at a time.
  // Modified to accumulate 128 bits of key stream into an XMM register
  // and then XOR the key stream into the data 16 bytes at a time.
  // Approximately doubles throughput.
  

  このコメントは、変更の意図を明確に示しています。8ビット演算後のストール回避、64ビットから128ビットへのXOR単位の変更、XMMレジスタの利用によるスループット倍増が述べられています。

• メインループの構造変更: 従来の8バイト単位の処理から、16バイト単位の処理 (wordloop, start) が導入され、残りのバイトは1バイトずつ処理 (l1, l2) されます。

• KEYROUND マクロ:

  #define KEYROUND(xmm, load, off, r1, r2, index) \
  	MOVBLZX	(BP)(DX*4),\tR8; \
  	MOVB	r1,\t\t(BP)(DX*4); \
  	load((off+1), r2); \
  	MOVB	R8,\t\t(off*4)(R12); \
  	ADDB	r1,\t\tR8; \
  	EXTEND(R8); \
  	PINSRW	$index, (BP)(R8*4), xmm
  

  このマクロは、RC4の鍵ストリーム生成の1ラウンドをカプセル化しています。

  • MOVBLZX (BP)(DX*4), R8: state[j] の値を R8 にロードします。DX は j の値です。*4 は s が uint32 になったため、バイトオフセットを計算するために必要です。
  • MOVB r1, (BP)(DX*4): state[i] の値を state[j] の位置に書き込みます。r1 は state[i] の値です。
  • load((off+1), r2): 次のラウンドで必要となるS-boxの値をプリフェッチします。LOAD マクロまたは SKIP マクロが展開されます。
  • MOVB R8, (off*4)(R12): state[j] の値を state[i] の位置に書き込みます。R12 は state 配列のベースアドレスです。
  • ADDB r1, R8: state[i] と state[j] の値を加算します。
  • EXTEND(R8): 8ビット演算の結果を64ビットレジスタにゼロ拡張します。これは、一部のシステムでのストールを避けるための最適化です。
  • PINSRW $index, (BP)(R8*4), xmm: 計算された鍵ストリームバイト (state[val]) を、指定されたXMMレジスタ (xmm) の特定の16ビット位置 ($index) に挿入します。これにより、128ビットの鍵ストリームがXMMレジスタに構築されます。

• LOAD マクロ:

  #define LOAD(off, reg) \
  	MOVBLZX	(off*4)(R12),\treg; \
  	ADDB	reg,\t\tDX; \
  	EXTEND(DX)
  

  このマクロは、S-boxから値をロードし、j の値を更新します。off は R12 からのオフセット、reg はロードした値を格納するレジスタです。

• 128ビットXORの実行:

  	PSLLQ	$8,\t\tX1
  	PXOR	X1,\t\tX0
  	MOVOU	-16(SI),\tX2
  	PXOR	X0,\t\tX2
  	MOVOU	X2,\t\t-16(DI)
  

  • PSLLQ $8, X1: X1 レジスタの内容を左に8ビットシフトします。これは、KEYROUND マクロで交互に格納されたバイトを正しい位置に配置するためです。
  • PXOR X1, X0: X0 と X1 の内容をXORし、最終的な128ビットの鍵ストリームを X0 に生成します。
  • MOVOU -16(SI), X2: 入力データ (src) から16バイトを X2 レジスタにロードします。
  • PXOR X0, X2: 生成された鍵ストリーム (X0) と入力データ (X2) をXORします。
  • MOVOU X2, -16(DI): 結果を dst に書き込みます。

これらの変更により、RC4の鍵ストリーム生成とデータXOR処理が、AMD64プロセッサのSIMD命令を最大限に活用するように最適化され、大幅なパフォーマンス向上が実現されています。

関連リンク

• Go CL 7865046: https://golang.org/cl/7865046

参考にした情報源リンク

• Original source for RC4 AMD64 assembly: http://www.zorinaq.com/papers/rc4-amd64.html
• Go Assembly Language (Plan 9 Assembly): https://go.dev/doc/asm
• RC4 Algorithm: https://en.wikipedia.org/wiki/RC4
• SSE (Streaming SIMD Extensions): https://en.wikipedia.org/wiki/Streaming_SIMD_Extensions
• AVX (Advanced Vector Extensions): https://en.wikipedia.org/wiki/Advanced_Vector_Extensions