EPT Address Translation, Performance and Caching

はじめに

最近hypervisor関連の論文を読み漁っているのですが、EPTに関して知識不足だなと感じたので一度ちゃんとインプットをしようと思い仕様書やEPTに特に焦点を当てた論文を読むことにしました。間違いなどあればご指摘いただけると助かります。

0. 準備

まずは準備として簡単に省略形や用語の整理をしておきたいと思います。

省略形の整理

基本的には省略形があるものはそれを使って説明するので事前に整理しておきます。

• EPT(Extended Page Table)
• GVA(Guest Virtual Address)
• GPA(Guest Physical Address)
• HVA(Host Virtual Address)
• HPA(Host Physical Address)
• EPTP(EPT Pointer)
• VMCS(Virtual Machine Control Structure)
• TLB(Translation Lookaside Buffer)

用語の説明

SDMで使用されている用語について、予め解説しておきます。

paging-structure

PML4, PDPT, PD, PTの各エントリのこと。

page frame

物理ページのこと。アドレス変換では、リニアアドレスのpage numberからこのpage frameの物理アドレスを計算する。

page number

リニアアドレスに含まれている, page frameを見つけるためのindexのこと。4KBページを採用している場合は47:12までの36ビットであり、2MBの場合は47:21までの27ビットのこと。

1. EPTのアドレス変換

EPTにおけるアドレス変換の流れはとてもシンプルで、通常の4-level pagingとほとんど変わりません。EPTが有効になっている場合でも、スタートは普通のアドレス変換と同様に（ゲスト）CR3レジスタを参照し、数珠つなぎのようにPML4, PDPT, PD, PTのベースアドレスを求めていきます。普通のアドレス変換と違うのは、PML4~PTのベースアドレスがGPAであり、HPAに変換する必要があるということです（以下の図を参照）。

2. EPTのパフォーマンス

EPTのアドレス変換の仕組みを理解すると、単純に 「通常のアドレス変換よりもかなりオーバーヘッドが大きいのでは？」 という疑問が湧きます。キャッシュなどを考慮しないとすれば、これはYESと言って問題ないと思います。

通常のメモリアクセスでは、リニアアドレスから物理アドレスへの変換に最悪4回のメモリアクセスを必要とします。（PML4, PDPT, PD, PTそれぞれのpaging structureへのアクセス） EPTではPML4, PDPT, PDT, PTの各ベースアドレス（GPA）をHPAに変換する必要があり、それぞれの変換で５回のメモリアクセスが発生します。（正確にはPTに関しては4回になります）最終的に、EPTによるアドレス変換では最悪の場合24回のメモリアクセスが発生します。 個人的には、この問題は仮想化環境のパフォーマンスを語る上ではよく出てくる問題だと思います。そのため、関連する研究もたくさんあります。

3. EPTとキャッシュ

2で説明したように、EPTのアドレス変換は比較的オーバーヘッドの大きい仕組みです。とはいえ、実際の（ゲスト）リニアアドレスのメモリアクセスには様々なキャッシュが用意されており、必ずしも多くのメモリアクセスが発生する訳ではないです。

3.1 TLBとpaging-structure cachesの復習

EPT環境におけるキャッシュを説明する前に、通常のアドレス変換におけるキャッシュについて復習しておきます。アドレス変換におけるキャッシュには2種類あります。それが、TLB(translations)とpaging-structure cacheです。ざっくりと言えば、TLBはpage numberとpage frameの対応 を記録したキャッシュで、paging-structure cacheはpage numberの一部と対応するpaging-structureを記録したキャッシュです。 具体的なアドレスがあると分かりやすいので、今回は 0x0b900c0ae0c2016 というリニアアドレスがあった時に、どのようにキャッシュが働くのかを見ていきます。

TLBの場合

TLBの場合はpage numberとpage frameのマッピングなので単純です。実際には、アドレス変換に使用された全てのpaging-structuresの read/write , user/supervisor, dirty, execute-disableビットなどの情報も含まれています。以下の図のようなイメージです。（890というのが対応するpafe frameの物理アドレスで、これに016をoffsetとして加算した値が最終的な物理アドレスになります）

paging-structure cacheの場合

paging-structure cacheはpage numberの一部と対応するpaging-structureのmappingをキャッシュします。Intelではアドレス変換における各レベル（L4~L2）で別々のキャッシュを領域を確保しており、それぞれPML4 cache,PDP cache, PDE cache と呼ばれています。図の右側にあるのは、各indexに対応するpaging-structureの物理アドレスです。

よくあるページングの図に合わせて見てみると、以下のようなイメージになります。CPUはとにかくアドレス変換に必要なメモリアクセスの回数を減らしたいので、まずはTLBを参照します。TLBヒットすれば最終的なpage frameが一発で分かるので、アドレス変換に必要なメモリアクセスの回数は0回になります。TLBミスした場合は、page-walkする必要があります。page frameに近いPDE cahceから探していき、PML4 cacheまで探してもキャッシュが見つからなければCR3にアクセスして地道にpage-walkしていきます。PDE cacheにヒットした場合は1回, PDP cacheの場合は2回, PML4 cacheの場合は3回のメモリアクセスが必要になります。TLBと同様に、実際にはread/write , user/supervisor, dirty, execute-disableビットなどの情報も含まれています。

3.2 EPTにおけるTLBとpaging-structure cache

EPT環境で使用されるアドレス変換キャッシュにはGuest-physical mappingとCombined mappingの2つがあります。まずはそれぞれについて簡単に説明します。（仕様書ではTLBのエントリのことをtranslationと表記しているので、ここではそれに従います。意味は変わらずpage numberとpage frameのmappingです）

• Guest physical mapping
  • GPAとHPAのmapping
  • translationとpaging-structure cacheの2種類がある。translationの場合は、GPAのpage numberと(host)page frameのmapping。paging-structure cacheの場合は、GPAのpage numberの一部と(host)page frameのmapping。
• Combined mapping
  • GVAとHPAのmapping
  • translationとpaging-structure cacheの2種類がある。translationの場合は、GVAのpage numberと(host)page frameのmapping。paging-structure cacheの場合は、GVAのpage numberの一部と(host)page frameのmapping。

EPTが使用されていない環境ではLinear mappingsというキャッシュもあるのですが、EPT環境ではこちらは使用されません（SDMを読む限りでは、これは3.1で説明した普通のTLBとpaging-structure cahcheのことだと思います）。

3.3 EPTとVPID

EPT環境ではアドレス変換以外にも性能面での問題がありました。その一つに、VMX transition時のTLBフラッシュによる性能劣化が挙げられます。初期の仮想化では、VMX transition (VMExit, VMEnter や ゲストVMの切り替え) のたびにTLB（とpaging-structure cahceの）フラッシュが発生し、これがパフォーマンス上の大きなボトルネックになっていました。

この問題を解決するために導入されたのが、Virtual Processor Identifier (VPID) という仕組みです。VPIDは各vCPUにユニークなIDを振ります。これによって物理プロセッサはvCPUをIDによって識別することが可能になりました。そして、このVPIDをTLBのエントリにも取り入れることでVM transition時のTLBフラッシュが大幅に軽減されました。

PCIDについて

VPIDについて見ていく前に、PCID(Process-context identifier) に関して復習しておきます。PCIDはCPUが複数のリニアアドレス空間の情報をキャッシュするための機能で、プロセスごとにユニークなIDを振ります。PCIDが有効になっている場合、CPUはTLBやpaging-structure cacheのエントリを作成する時に、それらのエントリとcurrent PCIDを紐付けます。

例えば、システムコールの呼び出しなどでuser-modeからkernel-modeへのスイッチが発生し、それに伴いページテーブルの切り替えが発生したとします（実際にKPTIが有効になっているLinuxバージョンでは切り替えが発生します）。PCIDが無効になっている場合、CPUはTLBやpaging-structure cacheのエントリをフラッシュする必要があります。一方で、PCIDが有効になっている場合、CPUはcurrent PCIDを切り替えるだけでTLBやpaging-structure cache全体をフラッシュする必要はありません。

EP4TAについて

EP4TAはEPTPの51:12までの40ビットのことです。現在のCPUではEPTP switchingなどが実装されている場合もあり、こういったケースでは1つのvCPUが複数のEPTを使い分けるような使い方が想定されるため、vCPUに加えて現在使用しているEPTについての情報も必要になります。

VPIDの使用例

PCIDとEP4TAについて復習したのは、EPT環境においてTLB, paging-structure cacheエントリはEP4TA, VPID, PCID の3つの識別子の組み合わせによってタグ付けされるからです（後述）。VPIDはPCIDのVMバージョンみたいなもので、VM(より正確にはvCPU)ごとにユニークなIDを振り、TLBやpaging-structure cacheのエントリ作成時にcurrent VPIDを紐付けます(後述)。

詳細については割愛しますが、実は上記の説明は正確ではありません。EPT環境では、Guest-physical mappingとCombined-mappingという2種類のキャッシュがあり、それぞれにTLB(translation)とpaging-structure cacheがありました。結論から書くと、Combined mappingにはEP4TA, VPID, PCIDの３つの情報が紐付くのですが、Guest-physical mappingに関してはEP4TAだけが紐付きます。

とはいえ、これらのタグ付によってEPT環境でのコンテキストスイッチの性能劣化は軽減されます。
例えば、Combined mappingに関してはPCID, VPIDが紐付けられたことで どのvCPUのどのプロセスのTLBエントリか がわかるようになりました。

まとめ

今回はEPTの中でも特に、アドレス変換の仕組み、パフォーマンス、キャッシュについて調べた限りのことをまとめました。今回詳しくは触れられなかった内容の中でも、EPTに関連する面白い話題はたくさんあります。この記事を書くにあたって、いくつか面白い論文も見つけました。記事内の説明で参考にした資料や文献についてはリンクを貼っていますが、それ以外の論文について知りたい/記事を書いてほしいという方がいましたら コメント or @oshiboriまでご連絡ください。

Performance Implications of Extended Page Tables on Virtualized x86 Processors

こいつについてもうちょっとちゃんと理解する。主な焦点は「なぜ仮想化環境におけるTLBミスのうち仮想化が影響している割合が小さいのか」。

ページサイズについて

ゲストとホストがそれぞれ4KB or 2MBページを採用しているかでpage-walkの長さが変わりメモリアクセスの回数も変化する。4KBの場合はpage-walkが4回なのでメモリアクセスも4回になる。最悪24回になるのはゲストとホスト（EPT）がそれぞれ4KBページを採用していた場合で、PML4, PDPT, PD, PTのそれぞれの物理アドレスへアクセスするまでに5 * 4回=20回と、最終的なページの物理アドレスを変換するために4回のメモリアクセスが発生して合計24になる。EPTが2MBページサイズを採用していた場合はpage-walkが3回になり各page-structureへのメモリアクセスは5→4回に減る。またpage-walkの長さが4→3回に減ったので、4 * 3 =12と最終的なページの物理アドレスを変換するのに3回で合計15回になる。

ゲストのページサイズが4KBから2MBになればGVAからGPAへの変換が早くなり、ホストのページサイズも同様に大きくするとGPAからHPAへの変換が早くなる。最も早いのはゲストもホストも2MBページを採用していた場合で、最も遅いのはどちらも4KBを採用していた場合。

memo
TLBミスの後に参照されるのがMMUキャッシュであり、TLBというのは仮想アドレスのタグ(47:12)に対して対応するページの物理アドレスをキャッシュするもの、MMUキャッシュはTLB miss後にページテーブルを参照する場合にそのステップ（4levelなら最悪4回）を減らすためのもの。

Pagingの復習

Presentビット

page numberの変換に使用されるpaging-structure entryにおいてこのビットが0の場合、アドレス変換が停止されpage faultが発生する。問題のpaging-strucure entryに他のpaging-strucureへのポインタ（物理アドレス）が含まれていてもそれは使用されない。例えば、PML4エントリのpresentビットが0で次のPDPTのベースアドレス(物理)が含まれていても、その値は使用されない。

Read/Writeビット

ページが読み書き可能かどうかを表すビット。

The WP bit in CR0 determines if this is only applied to userland, always giving the kernel write access (the default) or both userland and the kernel

CR0.WPビットを使用して、kernelを常に書き込み可能にするかどうか選択できる。

User/Supervisorビット

supervisorだけがアクセス可能にするかどうかを表すビット。page numberの変換に使用されるpaging-structure entryにおいてこのビットが1の場合にのみ、userからアクセス可能。そのため、あるページをuserページにしたい場合はそのページだけでなく変換に使用される全てのpaging-structure entryにおいてこのビットを立てる必要がある。

Accessedビット

あるpageが読み書きされたかどうかを表す。このビットを制御するのはCPUではなくOSの責務なので注意が必要。

参考：https://wiki.osdev.org/Paging
参考：https://composter.com.ua/documents/TLBs_Paging-Structure_Caches_and_Their_Invalidation.pdf

memo
TLBの各エントリは以下の情報を含んでいる。

• Page frame, page numberに対応するPage Table Entry
• Read/Write, page numberを変換するのに使用されたpaging-structure entriesのr/wビットの論理積
• User/Supervisor, page numberを変換するのに使用されたpaging-structure entriesのu/sビットの論理積
• Dirty, page numberの変換先のPage Table EntryのDirtyビットが立っているかどうか
• Execute-disable, page numberを変換するのに使用されたpaging-structure entriesのexecute disableビットの論理和

TLBエントリにこれら全ての情報が含まれているとは限らない。例えば、プロセッサに複数のTLBが実装されている場合などがあり、その中にはinstruction fetchのためのTLBなどの特別な用途のTLBがある。このTLBエントリは用途からして、Read/WriteビットやDirtyビットを含む必要がない。

プロセッサはpage numberを変換するのに使用された全てのpaging-structure entriesにおいてpresentビットが1であり、かつreservedビットが0でないとそのtranslationをキャッシュしない。

The processor may cache a TLB entry at the time it translates a page number to a page
frame, and the information cached in the TLB entry is determined at that time. If software
modifies the relevant paging-structure entries after this translation, the TLB entry may not
reflect the contents of the paging-structure entries.The processor may cache translations required for prefetches and for memory accesses that are a result of speculative execution that would never actually occur in the executed code path.

speculative execution that would never actually occur in the executed code pathとは？
（まずprefetchがなんのことかわかっていないし、speculative executionも何かわかっていない、というかexecuted code pathもわかっていない）

speculative executionについては何となくわかった。このspeculative executionに必要なメモリアクセスにおけるtranslationもTLBはキャッシュするので、これを悪用したのがSpectreとか。

参考：https://en.wikipedia.org/wiki/Speculative_execution#:~:text=Speculative execution is an optimization,known that it is needed.

paging-structure cachesについて

まとめていき

PML4 cache（L4）

47:39の9ビットをインデックスにして対応するPML4エントリのデータの一部（詳細は上のコメントにある）をキャッシュする。

PDP cache (L3)

47:30の18ビットをインデックスにして対応するPML4エントリとPDPエントリのデータの一部をキャッシュする

PDE cache (L2)

47:21の27ビットをインデックスにして対応するPML4エントリとPDPエントリ, PDEエントリのデータの一部をキャッシュする

PTE cacheがないのは、PTE cache = TLBなので。

当然だけど、よりpage frameに近いのはTLBなので、プロセッサはアドレス変換においてはまず47:12からTLBエントリを探す。ヒットした場合はpage frameを使用して物理アドレスを決定し、read/write, user/supervisorなどのbitsを見てアクセスを許可するかどうか判断する。ミスした場合はアドレス変換が必要なので、TLBの次に近いPDEキャッシュを47:21をインデックスに探す。（再びミスした場合は、同様にPDPキャッシュ、PML4キャッシュを探すことになる）

Suppose that two PML4 entries contain the same physical address and thus reference the same page-directory-pointer table. Then any PDP in that table may result in two PDP-cache entries, each associated with a different set of linear addresses. Specifically, suppose that the n1 and n2 entries in the PML4 table contain the same physical address. This implies that the physical address in the m PDP in the page-directory-pointer table will appear in the PDP-cache entries associated with both p1 and p2, where (p1 » 9) = n1, (p2 » 9) = n2, and (p1 & 1FFH) = (p2 & 1FFH) = m. This is because both PDP-cache entries use the same PDP, one resulting from a reference from the n1 PML4 entry and one from the n PML4 entry.

異なるindexに対して同じpaging-structureがキャッシュされることがあるよって話。
PML4を例に挙げると、異なるPML4エントリが同じPDPTを指している場合、そのPDPTの全てのPDPは2パターンのリニアアドレス（というかindex）にpaging-structure cacheとして紐づけられる可能性がある。

異なるPML4エントリなので、47:39ビットは当然違う。同じPDPエントリなので、38:30ビットは同じ。
47:30までのPDP cacheとしてキャッシュされるpaging-structure(PDP)は同じなのに、indexの部分は違うということ。

（これ、通常の動作では起こり得ない気がするのだがどうなんだろう。あくまでキャッシュ後にエントリが変更された場合などに限ると思うのだが。異なるアドレス空間でページ共有とかができるならまた別なのか...？）

Invalidate TLBs and Paging Structure Cachesについて

• INVPLG, operandにリニアアドレスを取る, このリニアアドレスをindexとして対応するTLBエントリ(global pageを含む)を無効にする, リニアアドレスに関わらずpaging-structure entriesの全てのエントリを無効にする

• mov to cr3, global pageを除く全てのTLBエントリを無効にする, paging-structure cachesのエントリを全て無効にする

• mov to cr4, PGEビットが変更されると全てのTLBエントリと全てのpaging-structure cachesのエントリを無効にする

• INVLPGはオペランドに対応するエントリ以外のTLBエントリを無効にすることがある

• mov to cr3はglobal pageも無効にすることがある

• Hyper-threading technologyをサポートするプロセッサ上では他のプロセッサから使用されたエントリを無効にすることがある

他にもTLBエントリが無効になるポイントはある

• page faultが発生するとTLBやpaging-structure cachesの該当エントリが無効になる
  • 例えば、ページテーブルを書き換えてリニアアドレスから対応するページが存在しなくなった場合はメモリアクセス時にpage faultが起きてそのリニアアドレスに紐づくTLBとpaging-structure cachesなどが全て無効にされるってことだと思う
• これによってページテーブルが変更されてキャッシュと不整合が生まれてpage faultが発生しても、page faultが再発しない
  • そのリニアアドレスに次にアクセスする時はキャッシュがないのでcr3から普通にpage-walkすることになり、新しいキャッシュが作られる
  • とはいえ、page faultが発生しない場合もあって、その場合はリニアアドレスと対応するpage frameがあ間違っているので、本来書き込みたくない（けどbit的には書きこめてしまう）場所に書き込む事故が起きる（と思う）のでページテーブルの変更があったら、OS側でそのリニアアドレスに対してINVLPGを実行する必要がある

invalidationのやり方のおすすめ

• PTEが変更された場合、PTEが使用されているpage numberを持つリニアアドレスに対してINVLPGを実行する必要がある
• PTEが異なるpage numberの変更に使用される可能性がある場合そのソフトウェアはそれらの各page numberに対応するリニアアドレスに対してINVLPGを実行する必要がある
  • 例えば、リニアアドレスA-page frame AとリニアアドレスB-page frame BのTLBがあって、これがリニアアドレスA-page frame B, リニアアドレスB-page frame Aみたいにスワップした場合、リニアアドレスAに対してINVLPGするだけじゃダメで、リニアアドレスBに対してもINVLPGする必要がある。

invalidationしなくても良いケース

• paging-structureのpresentビットを0から1にした場合, 0だったんならキャッシュも作成されてないはずなので
• accessedビットを0から1にした場合, 上に同じ
• read/writeビットを0から(略), この場合キャッシュは作成されている可能性はあるが、"spurious" page faultが発生するかもだけど他に有害な影響はなし（spurious page faultとは）
• usビット, 上に同じ
• execute-disableビットを1から0にした場合, 上に同じ
• accessed, dirtyビットを1から0にした場合はinvalidateしないとダメ

TLB続き

Large Page

PDEエントリのbit7が立っている場合、そのエントリはPTを指すために使われるのではなく最終的な2MBページを指すのに使われる。これによってキャッシュの有無などにも違いが出る。

まず、PDEエントリのbit7が立っている場合、PDEキャッシュは作られない。これは、そもそもpaging-structure cacheはpage-walkが発生する場合に中間のwalkを減らすためのものだから。2MBページにおいては4KBページにおけるPTEキャッシュが作られなかったのは、PTEに関してはそのエントリが指す物理アドレスに仮想アドレスのoffsetを足せばそれがそのまま最終的な物理アドレスになったからで、2MBページではそれがPDEになるだけ。（これを large page translationという）

EPTIについて

https://www.usenix.org/system/files/conference/atc18/atc18-hua.pdf

user-kernelでページテーブルの切り替えが発生し、かつTLBフラッシュによってuser-kernelそれぞれのパフォーマンスが低下する。PCIDによってTLBフラッシュによる性能劣化は防ぐことができるが、それでもCR3レジスタのロードに約300サイクル必要となる。EPTP switching では160サイクルなのでさらに小さい。とはいえ、EPTP switchingによってEPTが変更されればTLBの動作にも影響が出る。例えば、EPT-0でTLBフラッシュ（INVLPG命令）すると他のEPTのTLBもフラッシュする。

各VMにkernel用のEPTkとuser用のEPTuを作る。EPTkはオリジナルのEPTと同じマッピングを持つがパーミッションが違う。EPTuではkernelのマッピングに使用されるGPAページを特定して、対応するEPTuページを0埋めした別のページにremapする。

enter-kernel（例えばsyscallハンドラのエントリポイント）とexit-kernel（syscallハンドラの終了）のポイントをトランポリンコードに書き換えてVMFUNCによって直ちにEPTkとEPTuを切り替える。

EPTuの変更を小さくするために、gL3ページだけを0埋めする。この状態でuserからkernelコードへアクセスするとguest page faultが発生する。

EPTIは全てのgL3ページを追跡する必要がある。

In EPTu, only one page with the trampoline code will be mapped in the kernel space. To ensure that, EPTI remaps all the gPT pages (except gL4), which are used to　translate the GVA for the trampoline, to new host physical pages. Then all the entries of these pages are set to zero, except those that
used for mapping the trampoline (as shown in Figure 4). Entries of the guest IDT and the syscall entry MSR (IA32 LSTAR) will be changed to point to the trampoline code.

トランポリンコード用のページだけがカーネル空間にマッピングされ、その他のページは全て0埋めされる。
（ちょっと正確な理解が追いついていない...）

EPT violation について

以下の分類がある。

• GPA-HPAの変換中にnot-presentなpaging-structureが見つかった場合
  • 例えば、ゲストのPML4の物理アドレスを変換するためにEPT PML4->EPT PDPT->EPT PDと辿っているときに、このEPT PDのpaging-structureがnot presentだったとき。
• アクセス先のGPAを変換するのに使用されたEPT paging-structureの中に1つでもbit0（read）がクリアになっているものがあった場合