Wednesday, December 2, 2020

komake: Make の -j オプションに潜む罠とその解決策

ビルドツールのダジャレの大家と言えば @shinh さんですが、それはさておき、皆さんは今でも Make を使ってビルドすることが多いと思います。かく言う私も、その一人。

最近は CPU のコア数も多いですから、当然 -j 16 とか、やりたいわけです。大きいプロジェクトになればなるほど、威力絶大ですね。

ですが、ここで問題がひとつ。大規模プロジェクトでは Makefile が別の Makefile を呼び出すような依存関係が良く見受けられます。この際、ターゲット間の依存関係で菱形が存在すると(例: ターゲット sub1 と sub2 が shared に依存)、make shared が make sub1 と make sub2 から同時に起動されることが起こりえます。CMake で生成した Makefile の場合も、ターゲット毎に make を起動しますね。

二重起動が発生すると、ほとんどの Makefile は、同時起動されることを想定していませんから、ビルドは失敗したり、成果物が壊れたりしてしまいます。

実際に、以下のような Makefile を書いてみると、make shared が同時に動いてしまうことを確認できます(sleep 1が2回表示されていることに注目)。

$ cat Makefile
all: proj
proj: sub1 sub2
	touch $@
sub1:
	$(MAKE) shared
	touch $@
sub2:
	$(MAKE) shared
	touch $@
shared:
	sleep 1
	touch $@
clean:
	rm -f proj sub1 sub2 shared

$ make -j2
/Applications/Xcode.app/Contents/Developer/usr/bin/make shared
/Applications/Xcode.app/Contents/Developer/usr/bin/make shared
sleep 1
sleep 1
touch shared
touch shared
touch sub1
touch sub2
touch proj

どうしたらいいでしょう。

先に書いたように、問題は同一ターゲットを引数にとる make が重複起動されてしまうところです。ならば、make の並走度を別途制限すればいいのではないでしょうか。ある make が終了するためには、その make が呼び出した make が全て終了している必要があることを加味すると、単純に、呼び出し階層毎の make の同時実行数を1に制限してしまえば、この問題が解決するはずです。

ジャジャーン!!! と言うわけで書いたのが make のラッパースクリプト komake です!

わずか41行のスクリプトにして、求められる機能を実現しています。komake を使って先の Makefile を実行すると、ほら、このとおり!!!

$ komake -j2
komake shared
komake shared
sleep 1
touch shared
touch sub1
make[1]: `shared' is up to date.
touch sub2
touch proj

komake shared は2回呼び出されていますが、実際のビルド作業である sleep 1 と touch shared の呼び出しが1回に減少したことがわかります。これは、1回目の komake shared が終了した後に2回目の komake shared が呼び出され、既に「shared」ファイルが存在したから、ビルド作業は何も走らなかったからです。

完璧ですね!! すばらしい!!!!

なお、注意点として、多重起動されロックを取ろうとしている komake も make のジョブスロットを消費します。ですので、komake を使う場合には、-j オプションに渡す引数を CPU コア数 + ロックにひっかかりそうな make の数(たとえば4)等にセットするとよいでしょう。

ちなみに、名前の komake は、「こまけー問題なおしてるな」というセルフツッコミに由来します。細かな問題なのですが、大規模プロジェクトにおいて切実な make の待ち時間問題を解決する、かゆいところに手の届くツールになっていると思います。

。。。。。とか書いてるうちに、同僚の @gfx が、問題となっていたプロジェクトのビルドツールを Ninja に移行する作業を終わらせてしまいました。完敗だ。これはKO負けですね。

Thursday, June 18, 2020

QUICむけにAES-GCM実装を最適化した話 (2/2)

前半で述べたように、OpenSSLのAEAD暗号器は、長いAEADブロックの処理を前提に作られています。平文の暗号化処理においては理論上の上限にあたる速度を叩き出す一方、事前処理と事後処理、および呼出オーバーヘッドについては、あまり最適化が図られているとは言えません。これは、AEAD暗号の主な使用用途が、これまでTLSという長いAEADブロックを使う(ことが一般的な)プロトコルであったことを反映していると言えるでしょう。

一方、QUICにおいては、UDPパケット毎に独立した、短いAEADブロックを暗号化する必要があり、したがって、次のような速度向上の機会があることが分かります。

AEAD処理をひとつの関数にまとめ、事前処理と事後処理を、パイプライン化されスティッチングされた暗号処理と並行に走らせることができれば、AEADブロックが短くても、理論値に近いスループットを発揮するような、AES-GCM実装を作ることができる(前半より引用)

この条件を満たすような関数を実装し、ボトルネックをつぶしていって速度向上を図るというのは一案です。しかし、往々にして、そのような対症療法的なプログラミングスタイルでは、何回もの変更に伴う手戻りが発生したり、必ずしも最適でないコードが成果物の一部に残ったりしがちです。

より効率的な設計手法はないものでしょうか。

■QUIC向けAES-GCM実装「fusion」の設計方針

幸いなことに、AES-GCMについては、第9世代Core CPUにおけるボトルネックがAES-NIであり、そのスループットの理論上の上限が64バイト/40クロックであることが分かっています。スティッチングを用いたAES-GCM実装が、暗号化処理中、AES-NIを最高速度で回しつつ、他の演算ユニットを用いてGCMのハッシュ計算を行うという手法であることも、先に述べたとおりです。

ならば、AES-NIを常時実行しつつ、その合間をぬって、AEADの事前処理、事後処理を含む他のあらゆる処理を行うようにすれば、理論上の上限値に迫るようなAES-GCM実装が作れるのではないでしょうか。

このような考えに基づき、以下のような特徴をもつAES-GCM暗号ライブラリ「fusion」を作成することにしました:
  • できるだけ長い間、6*16バイト単位でAES-NIを実行する
  • その間に、AAD(=事前処理)を含む、任意の長さのGCMハッシュ計算を行う
  • 複雑な設計をメンテ可能とするために、アセンブリではなくCで記述する
  • AEADブロック全体にわたって、GCMハッシュの事前計算を行う。それにより、reductionの負荷を下げる
  • パケットヘッダ暗号化(パケット番号暗号化)に必要なAES演算を重畳する

AES-GCM暗号化の典型的なデータフローを可視化してみましょう。第一の図が、古典的な(OpenSSLのような)暗号化部分に注力したアプローチです。第二の図が、fusionのアプローチです。横軸が時間軸で、縦に並んでいる処理は同時実行(スティッチング)されています。fusionでは、より多くの処理がスティッチングされることがわかります。



以下が、fusion.cの暗号化のホットループです。gfmul_onestepは、1ブロック分のGCMハッシュの乗算演算を行うインライン関数です。6ブロック分(bits0〜bits5)のAES計算をする間に、gdata_cntで指定された回数だけgfmul_onestepを呼び出していることがわかります。
#define AESECB6_UPDATE(i) \
    do { \
        __m128i k = ctx->ecb.keys[i]; \
        bits0 = _mm_aesenc_si128(bits0, k); \
        bits1 = _mm_aesenc_si128(bits1, k); \
        bits2 = _mm_aesenc_si128(bits2, k); \
        bits3 = _mm_aesenc_si128(bits3, k); \
        bits4 = _mm_aesenc_si128(bits4, bits4keys[i]); \
        bits5 = _mm_aesenc_si128(bits5, k); \
    } while (0)
#define AESECB6_FINAL(i) \
    do { \
        __m128i k = ctx->ecb.keys[i]; \
        bits0 = _mm_aesenclast_si128(bits0, k); \
        bits1 = _mm_aesenclast_si128(bits1, k); \
        bits2 = _mm_aesenclast_si128(bits2, k); \
        bits3 = _mm_aesenclast_si128(bits3, k); \
        bits4 = _mm_aesenclast_si128(bits4, bits4keys[i]); \
        bits5 = _mm_aesenclast_si128(bits5, k); \
    } while (0)

    /* run AES and multiplication in parallel */
    size_t i;
    for (i = 2; i < gdata_cnt + 2; ++i) {
        AESECB6_UPDATE(i);
        gfmul_onestep(&gstate, _mm_loadu_si128(gdata++),
                      --ghash_precompute);
    }
    for (; i < ctx->ecb.rounds; ++i)
        AESECB6_UPDATE(i);
    AESECB6_FINAL(i);

コードを注意深く読んだ方は、bits4の計算だけ、異なる鍵を使うようになっていることに気づいたかもしれません。これが、パケットヘッダ暗号化のためのAES計算を重畳するための工夫です。

■パケットヘッダ暗号化

パケットヘッダ(パケット番号)の暗号化は、QUICやDTLS 1.3といった新世代のトランスポートプロトコルに見られる機能です。パケットヘッダを暗号化することで、傍受者による通信内容の推測をより難しくしたり、中継装置(ルータ)が特定の通信パターンを前提にしてしまうことによりトランスポートプロトコルの改良が困難になること(ossification)を防ぐ効果が期待されています。

なぜ、パケットヘッダ暗号化のAES計算を重畳するのか。それは、6ブロック分のAES計算を一度に行う以上、パケット長を96で割った余りが65から80の間にならない限り、使われないスロットが発生するためです。その余ったスロットをパケットヘッダ暗号化のAES演算に使うことで、パケットヘッダ暗号化のコストを隠蔽するのが目的です。

パケットヘッダ暗号化を重畳した場合のデータフローを、以下に示します。

■ベンチマーク

では、ベンチマーク結果を見てみましょう。

青の棒は、OpenSSLのAES-GCM処理のうち、事前処理と事後処理を含まないスループットを、赤の棒は、両者を含んだトータルでのスループットを表しています。黄色はfusionのトータルスループット、緑は、パケットヘッダ暗号化に必要な演算を重畳した場合の値です。


まずは、最近のIntel製CPUである、Core i5 9400の値を見てみましょう。

AEADブロックサイズが16KBの場合、OpenSSLの事前事後処理を含まないスループットとfusionのスループットが、いずれも6.4GB/sという理論上の上限に達していることが分かります(微妙なズレは、CPUクロック制御の精度に起因するものです)。OpenSSLの事前事後処理を含むスループットは若干遅い6.2GB/sですが、TLSにおいて、事前事後処理を最適化しないオーバーヘッドは3%以下である、という風に読むこともできます。

一方で、AEADブロックサイズが1440バイトの場合、差は顕著です。OpenSSLのトータルスループットが4.4GB/sと、理論値の約70%にまで落ち込むのに対し、fusionは理論値の90%を超えるスループットを発揮します。また、パケットヘッダ暗号化によるオーバーヘッドが1%以下なのも見てとることができます。

AMD Ryzenに目を向けると、AEADブロックサイズ1440バイトの場合のみならず16KBの場合でも、fusionが勝っていることが読み取れます。これは、RyzenのAES-NIのスループットがPCLMULと比較して高いため、ボトルネックがPCLMULに代表されるGCMハッシュ計算の側に移動したものと考えられます。fusionは、想定されるAEADブロック全体にわたって事前計算を行うことで、GCMハッシュ演算のうちreductionの回数を削減しているので、ブロックサイズ16KBの場合にも差がついたと考えることができます。

■考察

カーネル・ネットワークカードのUDP処理が最適化された場合、暗号処理のコスト差が問題となって、TLSよりもQUICのほうがCPU負荷が高くなる、という問題がありました。この問題について、QUICを始めとする暗号化トランスポート向けに最適化したAES-GCM実装を準備することで、大幅な改善が可能であることを示しました。fusionをQUICの暗号ライブラリとして使った場合の詳細は本稿では紹介しませんが、TCPとUDPでGSOハードウェアオフロードがある環境において、パケットサイズ9KBならQUICが優位、パケットサイズ1.5KBでもQUICのオーバーヘッドはTLS+5%程度だという測定結果を得ています(参照: h2o/quicly PR #359)。

あわせて、
  • パケットヘッダ暗号化のコストは(少なくとも送信側においては)特に問題視するレベルではないこと
  • アセンブリを用いる場合と比較して、C言語を用いることで、最善ケースのスループットを保ったまま、より高度な設計による暗号ライブラリが開発可能であること
を示しました。

今回開発したAES-GCM実装「fusion」は、昨日、我々が管理するTLSスタックであるpicotlsにマージされ、使用可能になっています。fusion、あるいはそれに類する実装手法を用いることで、インターネット上の通信が、より低コストに、より安全になっていくことを期待します。

末筆ですが、fusionを開発するにあたり、光成(@herumi)さんにアドバイスを、吉田(@syohex)さんにベンチマークでご協力をいただきました。この場を借りて御礼申し上げます。

Monday, June 15, 2020

QUICむけにAES-GCM実装を最適化した話 (1/2)

4月末に、会社のほうで「Can QUIC match TCP’s computational efficiency?」というブログエントリを書きました。我々が開発中のQUIC実装であるquiclyのチューニングを通して、QUICのCPU負荷はTLS over TCP並に低減可能であろうと推論した記事です。この記事を書く際には、Stay Homeという状況の中で、手元にあった安いハードウェアを使ったのですが、その後、10gbe NICを入手し、ハードウェアによるUDP GSOオフロード環境でのパフォーマンスを確認していくと、OpenSSLのAES-GCM実装がボトルネックになることがわかってきました。

TCP上で通信するTLSでは、一般に、データを16KB単位でAEADブロックに分割して、AES-GCMを用いてAEAD暗号化します。一方、UDPを用いるQUICでは、パケット毎にAES-GCMを適用することになります。インターネットを通過することができるパケットサイズは高々1.5KBなので、QUICのAEADブロックサイズはTLSと比較して1/10以下となります。

両条件について、OpenSSLのAES-GCM実装のスループットを比較したところ、4GHzの第9世代Intel Core CPUを使った場合、AEADブロックサイズ16KBにおいては約6.4GB/sなのに対し、AEADブロックサイズ1440バイトにおいては、4.4GB/s程度しか出ないことが分かりました。ハードウェアGSOオフロードが可能な環境ではCPU負荷の半分弱が暗号処理コストになるので、暗号処理で7割のスループットしか出ないのは、QUICの足かせになります。

それにしても、なぜ、これほど大きな速度差が発生するのでしょう。

その答えを理解するには、最適化されたAES-GCM実装が、一般に、どのようなものかを知っておく必要があります。

■AES-NIとパイプライン処理

まず、AES-GCMのうち、暗号処理であるAES実装の最適化手法を見てみましょう。

最近のx86 CPUは、たいてい、AES-NIというAES処理専用の命令に対応しています。128bitのAES暗号化においては、AES-NI命令を10回発行することで、16バイトの暗号化を行うことが可能です。第9世代のIntel Core CPUにおいては、AES-NI命令のレイテンシは4クロックなので、10*4=40クロックで16バイトの暗号化が可能になります。

4GHzでのスループットを計算してみると、4GHz / 40clock * 16byte = 1.6GB/sになります。

あれ、先ほどの6.4GB/sと比べると1/4の値です。なぜでしょう?

実は、x86 CPUはAES-NIをパイプライン処理します。そのため、依存関係のない(=別のAESブロックを処理する)AES-NI命令を1クロックごとに1個発行することが可能なのです。

つまり、16バイトの基本ブロック単位で処理するのではなく、AES-NI(ブロック1用)、AES-NI(ブロック2用)、AES-NI(ブロック3用)、AES-NI(ブロック4用)、AES-NI(ブロック1用)、...のように、16バイトのブロック4つ分のAES-NI命令を並行に発行し続けることで、64バイト分の暗号化を4*10=40クロックで終えていくことができるのです。

4GHzでのスループットを再び計算すると、$GHz / 40clock * 16byte * 4 = 6.4GB/s。

毎クロック1命令発行、16バイトの暗号化に10命令必要ですから、これが理論上の上限値になります。

でも、ちょっと待ってください。6.4GB/sは、暗号処理であるAESのスループットであって、認証符号であるGCMの負荷を含んでいません。GCMの負荷は一体どこに行ってしまったのでしょう

■AES-GCMのスティッチング

GCMはガロア体における乗算を用いる認証符号で、x86 CPUでは、PCLMULQDQというキャリーレス乗算命令を利用する最適化が知られています。さらに、式を変形することで、16バイトあたりのPCLMULQDQ命令発行回数を5回に減らせることが、また、事前計算を行えば、16*nバイトあたりのPCLMULQDQ命令発行回数を3*n+2回まで減らせることが知られています(参照: https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf)。

PCLMULQDQ命令は、7クロックのレイテンシがありますが、AES-NIとは同時に発行可能なので、AES命令とPCLMULQDQをほどよく織り交ぜるようなプログラムを書くことで、AESとGCMを並列に計算することが可能です。

IntelのCPUにおいては、若干GCMの方がAESよりも軽いので、ボトルネックはAESになり、AES-GCMでもAES同様のスループット6.4GB/sが期待できます。

■OpenSSLのaesni_ctr32_ghash_6x関数

以上を踏まえ、OpenSSLのAES-GCM実装であるaesni_ctr32_ghash_6x関数を見てみましょう。

この関数は、perlスクリプトを用いて生成されるアセンブリコードですが、以下のような、AES-NI命令とPCLMULQDQ命令が織り混ざる構成になっています。また、AES-NI命令について、同じラウンドキーを違う引数($inout)に適用している、つまり、複数ブロックの暗号化を同時に行なっていることが分かります。命令の目的によってインデントを変えるなどの工夫も興味深いところです。

vpclmulqdq \$0x01,$Hkey,$Ii,$T2
    lea  ($in0,%r12),$in0
      vaesenc $rndkey,$inout0,$inout0
     vpxor 16+8(%rsp),$Xi,$Xi # modulo-scheduled [vpxor $Z3,$Xi,$Xi]
    vpclmulqdq \$0x11,$Hkey,$Ii,$Hkey
     vmovdqu 0x40+8(%rsp),$Ii # I[3]
      vaesenc $rndkey,$inout1,$inout1
    movbe 0x58($in0),%r13
      vaesenc $rndkey,$inout2,$inout2
    movbe 0x50($in0),%r12
      vaesenc $rndkey,$inout3,$inout3
    mov  %r13,0x20+8(%rsp)
      vaesenc $rndkey,$inout4,$inout4
    mov  %r12,0x28+8(%rsp)
    vmovdqu 0x30-0x20($Xip),$Z1 # borrow $Z1 for $Hkey^3
      vaesenc $rndkey,$inout5,$inout5
注意深い方は既にお気づきかもしれませんが、関数名の6xは、128bitのブロックを6ブロック単位で(つまり、96バイト単位で)AES-GCM符号化を行なっていることに由来します。

■なぜOpenSSLは短いAEADブロックの処理が苦手なのか

このように、丁寧に最適化されたコードであるにもかかわらず、なぜ、OpenSSLは短いAEADブロックの処理が苦手なのでしょうか。2つの要因が考えられます。

第一の要因は、関数呼び出しのオーバーヘッドです。OpenSSLのAEAD処理は、EVPと呼ばれるレイヤで抽象化されています。ひとつのAEADブロックを暗号化するには、EVP_EncryptInit_ex、EVP_EncryptUpdate、ENP_EncryptFinal、という3つの関数を介して、AES-GCM固有の処理を呼び出す必要があります。

第二の要因は、AES-GCMの事前処理と事後処理がパイプライン化されていない点です。先に紹介したaesni_ctr32_ghash_6x関数は、6.4GB/sという理論値を叩き出す、文句のつけどころのない関数です。しかし、AES-GCMにおいては、暗号化以外にも、AEADブロック毎に、AAD(認証つき平文)をGCMのコンテクストに入力したり、最終的なタグを計算するなどの処理が必要です。これらの付随する処理の負荷は、AEADブロックサイズが小さくのればなるほど、相対的に大きくなります。

これらの問題を指摘することは簡単です。

なるほど、AEAD処理をひとつの関数にまとめ、事前処理と事後処理を、パイプライン化されスティッチングされた暗号処理と並行に走らせることができれば、AEADブロックが短くても、理論値に近いスループットを発揮するような、AES-GCM実装を作ることができるでしょう。

しかし、上述したように、パイプライン化・スティッチングされたコードは、既に相当複雑です。ここにさらに、事前処理や事後処理を重畳することなどできるでしょうか。できたとして、保守可能なプログラムになるでしょうか


次回に続きます。



注: スロースタート時には、より小さなブロックサイズを使って実効レイテンシを改善する場合もあります(参照: https://www.slideshare.net/kazuho/programming-tcp-for-responsiveness

Thursday, April 16, 2020

C言語で配列の要素数を安全に数える話

C言語で配列の要素数を数えるイディオムってのがあって、
sizeof(array) / sizeof(array)
なんだけど、配列名が長くなって、たとえば
sizeof(var.that_has_an_array.as_a.member) /
    sizeof(var.that_has_an_array.as_a.member[0])
とかになるとカオス。

なので、ベンダーによっては、
#define _countof(array) (sizeof(array) / sizeof(array[0]))
みたいなマクロを提供していたりするんだけど、こうやって、何も考えずに使えるようにしていくと、配列ではなくポインタを引数に渡しちゃって、サイズ計算ミスって変な動作する懸念が増してくる。

なので、Twitterで

と聞いたところ、mattnさんから

と教えてもらったので、
#define PTLS_BUILD_ASSERT(cond) \
    ((void)sizeof(char[2 * !!(!__builtin_constant_p(cond) || (cond)) - 1]))

#define PTLS_ASSERT_IS_ARRAY(a) \
    PTLS_BUILD_ASSERT(
        __builtin_types_compatible_p(__typeof__(a[0])[], __typeof__(a)))

 #define PTLS_ELEMENTSOF(x) \
    (PTLS_ASSERT_IS_ARRAY(x), sizeof(x) / sizeof((x)[0]))
こんな感じにして取り込みました。これで、先の冗長な例も
PTLS_ELEMENTSOF(var.that_has_an_array.as_a.member)
と書くことができる。便利。

完全な変更は add PTLS_ELEMENTSOF for counting the number of elements in an array by kazuho · Pull Request #301 · h2o/picotls をご覧ください。


PS. 配列かポインタかの確認方法については、yuguiさんから下のようなコンパイラ非依存の解も教えてもらったのですが、残念ながらコンパイル時に動かすことが難しいようでした。実行時判定が必要なケースなら、この方法のほうがいいかも。

Wednesday, March 11, 2020

2020年にDSRロードバランス環境を作る方法

TCPの時代もそうだったんですが、QUICにおいても、Linux等でソフトウェアロードバランサをipvsadmとDSR (direct server return, a.k.a. direct routing) を実現することは有効な手段です。

なんだけど、ipvsadm界隈はHA前提の込み入った設定か古いドキュメントしか見つからなかったので、最低限の検証環境のセットアップ方法を、ここにまとめる次第です。

ロードバランサ:
echo 1 | sudo tee /proc/sys/net/ipv4/ip_forward
sudo ifconfig eth0:0 $VIP netmask 255.255.255.255 broadcast $VIP up
sudo route add -host $VIP dev eth0:0
sudo ipvsadm -A -t $VIP:443 -s rr
sudo ipvsadm -a -t $VIP:443 -r $SERVER1 -g
sudo ipvsadm -a -t $VIP:443 -r $SERVER2 -g
sudo ipvsadm -a -t $VIP:443 -r $SERVER3 -g
...

要は、フォワーディングを有効にして、自分自身へのパケットを他のサーバにフォワードするような変態行為をするからspoofing対策フィルタをオフにして、次にipvsadmでテーブル作ってサーバ追加する。

サーバ:
echo 1 | sudo tee /proc/sys/net/ipv4/ip_forward
echo 0 | sudo tee /proc/sys/net/ipv4/conf/eth0/rp_filter 
echo 2 | sudo tee /proc/sys/net/ipv4/conf/eth0/arp_announce
echo 1 | sudo tee /proc/sys/net/ipv4/conf/eth0/arp_ignore
sudo ifconfig lo:0 $VIP netmask 255.255.255.255 broadcast $VIP up
sudo route add -host $VIP dev lo:0

要は、フォワーディング有効にして、VIPがARPでアナウンスされたり、応答したりしないように設定して、loにVIPをつけて、eth0で受信したパケットがlo:0に転送されるように設定する。

これで動く。