論文紹介：An analysis of performance evolution of Linux's core operations

元論文：https://dl.acm.org/citation.cfm?id=3359640

論文概要

SOSPという2年に一度のシステム系国際会議のトップカンファレンスのものです。トップカンファレンスだけあって毎回新しい手法をとんでもない実装量でこなす、みたいなとてつもない論文が多い印象なのですが、この論文は地道にLinuxのパフォーマンスの変化を観察し、その原因を探っていくという結構変わり種な論文な気がしました。

Linux 3.0から3.19、4.0から4.20までのカーネルを用いてマイクロベンチマークで性能測定をして性能変化の原因を調査し、アプリケーションベンチマークでその変化が実アプリケーションに与える影響を調べましたという論文です。
実は、システムコールやコンテキストスイッチなどのカーネルのオペレーションのレイテンシは段々と大きくなっているということがわかりました。
これらの原因はセキュリティの強化、機能の追加、さらにはカーネルのコンフィグの設定ミスが原因であると突き止めました。
また、これらのパフォーマンス低下を緩和させるパッチや、コンフィグの設定を変えることでパフォーマンス低下を避けられることも示しています。

パフォーマンス低下の原因

この論文で紹介されていた11の原因を簡単に見ていきます

セキュリティの強化

CPUの脆弱性として話題になったMeltdownの対策として導入されたKPTIにより、マイクロベンチマークの性能は22％低下しています。
KPTI以前ではアドレス空間をカーネルとユーザー間で共有していたのですが、KPTIの導入により異なるページテーブルを使うようになりました。
その影響で、特権モードの切り替えのたびにTLBフラッシュが発生したため性能が大きく低下することとなりました。
その後、process context identifire (PCID)を利用することで、TLBフラッシュの範囲を限定することである程度この性能低下は緩和されましたが、PCID書き込みのためのシステムレジスタアクセスのオーバーヘッドも実はかなり大きく、一部のベンチマークでは逆にさらにスコアが下がることになってしまいました。

Spectreの対策として導入されたRetpolineのパッチも性能に影響を与えています。Retpolineは間接分岐を書き換えることで分岐予測を誤らせるものですが、その影響で分岐予測が上手く働かず性能が低下してしまいます。
著者らはselectシステムコールの性能低下に注目し、selectの中で31個もの間接分岐があることに注目し、これらを普通の分岐に書き換えることによって性能低下を抑えることに成功しています。

SLABのフリーリストのランダム化も影響を与えています。SLABとは同じサイズのメモリ領域のリストを持っておきそれをカーネルオブジェクトのメモリアロケーションに使うというものですが、そのメモリ領域の順番をランダム化させておくことにより、万が一バッファオーバーフローなどの脆弱性があったときでも目的のオブジェクトを攻撃者にアクセスさせにくくさせることができます。
しかし、これはフリーリストのランダム化にかかる時間と離れたメモリ領域へのアクセスが増えることによるキャッシュミスの増加というオーバーヘッドを発生させてしまいます。

同じくバッファオーバーフローを利用した攻撃の対策として導入されたhardened usercopyもオーバーヘッドを生んでいます。これはユーザー空間とカーネル空間間のコピーを行う際、カーネルのポインタを毎回チェックして不正なアクセスがないか検査するというものです。
このオーバーヘッド影響はどのようなデータタイプにアクセスするかによって異なります。

新しい機能導入

fault-aroundはページフォルト時に対象となったページへのマッピングだけではなく、その周辺のページについてもマッピングしておくことで、ページフォルトの数を減らそうというものです。
この変更はページアクセスの局所性を仮定したものですが、大きなファイルへのアクセスはランダムに行われがちでむしろ逆効果なのです。big-pagefaultというテストではこの変更により54%の性能低下が起きました。

control group (cgroup) メモリコントローラーはcgroup毎のメモリ使用を管理する機能です。この機能はDockerなどのコンテナ型仮想化のために導入されたものです。
この変更によりそれぞれのページがcgroup毎に割り当てられ、ページのアロケーション・デアロケーション毎にオーバーヘッドが発生します。

Transparent Huge Page (THP)は2MBのページを割り当てた後、必要に応じて別スレッドで4KBの通常のページに分割していくというものです。これはページテーブルのサイズを小さくし、TLBミスを少なくする効果があります。
しかし、2MB毎にページを割り当ててしまうことでフラグメンテーションが発生し、一部のベンチマークでは性能が低下します。

Virtual machine monitor(VMM)などのために導入されたユーザー空間ページフォルトハンドリングは、ページフォルト時のエラーハンドリングをユーザー空間で行えるようにしたものです。
これはページフォルト時にそのページがユーザー空間で処理されるべきものなのかをチェックする必要があるため、オーバーヘッドを生みます。

コンフィギュレーションの変更

Forced Context Tracking (FCT)はデバッグ用の機能で、CPUの利用率をトラッキングしたりするのに使われます。これが一部のバージョンで有効になってしまっていたため、パフォーマンスがその間は低下していました。

Linux 3.14で導入されたパッチで、second-level TLBのサイズの認識ができるようになりました。それ以前だとサイズの認識ができなかったため、不必要なTLBフラッシュが発生していました。この機能が利用できるようになったのは、second-level TLBを積んだHaswellファミリーのプロセッサがリリースされてから6ヶ月もあとのことでした。

CPU Idle Power-Stateサポートは、CPUをアイドル状態にする際のアイドル状態のレベルをコントロールするものです。このパッチが充てられる前は常にもっともレベルの高いアイドル状態に突入し、復帰までの時間がかかるためオーバーヘッドが余計にかかってしまっていました。
しかし、Xeonプロセッサ上でこのパッチがLTSカーネルで利用できるようになるまで時間がかかってしまい、導入前の間はオーバーヘッドが大きくなってしまっていました。

まとめ・感想

カーネルのオペレーションがだんだんと遅くなっていて、適切なパフォーマンスチューニングでそれらが緩和できることを示しました。
しかし一方で、このようなパフォーマンスチューニングは非常にコストがかかり、Linuxのように大量の変更が日々されているなかでこのようなことを行うのは難しいということも認めています。
実際、Googleのデータセンター用のカーネルは100人以上のエンジニアによってパフォーマンスチューニングが行われているそうです。

OS開発の世界は厳しい！