Constellation Scorpius

Technical notes

Introducing the Paper, "Dune: Safe User-level Access to Privileged CPU Features"

Note: This article is written in Japanese. In this article, we introduces the paper by A. Belay et al., “Dune: Safe User-level Access to Privileged CPU Features” [A. Belay et al. OSDI ‘12].

この記事は, システム系論文紹介 Advent Calendar 2014 12/15 の記事として書かれました. ご意見, ご指摘, ご感想お待ちしております.

Reference

お気に入りの論文をとの事で, ここでは “Dune: Safe User-level Access to Privileged CPU Features” を紹介する. 著者らのグループは後に OSDI ‘14 にてこの Dune を基盤に “IX: A Protected Dataplane Operating System for High Throughput and Low Latency” を発表し, これは OSDI ‘14 の best paper の1つである. GPUnet [OSDI ‘14] にしようかと思ったが, 今回はこちらで.

Overview

この論文の提案することはまさに Abstract に一文で書かれている.

Dune uses the virtualization hardware in modern processors to provide a process, rather than a machine abstraction.

Intel VT-x (考え方自体に本質的な limitation はないが, 今回は主にこれ対象), AMD SVM といった virtualization hardware は VMM の構成要素として重要な役割を果たし効率的な VM を提供してきた. が, しかし, よく考えれば, VT-x で構築する abstraction は別に VM に限る必要はない.

Dune は発想を変え, VT-x を machine でなく, process abstraction を提供するために用いる. つまり machine の連続した physical memory space, devices, CPUs といった abstraction を構築するのではなく, process 環境, 大まかに言えば sparse な virtual memory space, system call interface (downcalls), signals (upcalls) といったものを VT-x を使って提供しようということだ. より具体的に言えば, process を VMX non-root で実行する. 結果 Dune は process に対して, ring 0 を与えることができる.

ring 0 を与えられた process は OS の持っていた特権機能を自由につかうことができる, すなわち ring protection, page tables, tagged TLB (Process Context ID) といった privileged hardware features だ. 特権の公開によって Dune は様々な application を実現, 最適化することができる. (e.g. sandboxing, privilege separation facility and GC.) しかも, process であり machine ではないので, process はこの特権にアクセス可能なこと以外は, 基本的に通常の process と同様に動く. つまり typical な Library OS のように stack を全部積み直したり, host との連携がないということはなく, system call を叩くこともできるのだ.

Dune の overview はこのくらいにして, 詳しく紹介していこう.

Background & Motivation

OS の特権, 例えば page table の dirty bit 情報などを適切に process に公開すると, application が便利に利用できるということは知られていて, 例えば page table の情報の公開による GC 最適化, process migration の user-space 実装などがあげられる.

しかし, 実現方法として, 「ある特権が user-space でほしい」となったらそのたびに kernel を intrusive に変更というのは現実的ではないし, 複数の applications から複数の特権が同時に必要, となった時にそのための kernel の変更が composable かどうかはわからない.

では application を specialized kernel (Library OS 等) と bundle して VM に載せてしまうというのはどうか? VM として動かせば, VMM によって host とは隔離され, 安全かつ効率的に特権を公開できるだろう. が, その場合, process と比較して host との poor integration が起こる. (host の FS も叩けない, process を fork したり UNIX domain socket で通信したりも出来ない etc.) また特定の application 向けに specialized kernel を構築するというのは small task ではない. 結果, 例えば, 「ある process の GC を高速にしたい」という motivation に対して, 「Library OS を構築して VM に載せて…」, というのは問題がある.

Proposal

そこで, Dune は virtualization hardware を用いて, machine の代わりに process abstraction を提供する. Dune mode になった process は Dune 特有の機能を使わなければ通常の process として動作することが出来る. つまり system call も利用できるし, なんら host OS との integration が process に対して劣ることはない. これに加えて Dune process は privileged hardware features を触ることができ, 様々な機能の実現や最適化が可能となる. そして同時に, virtualization hardware によって host の ring 0 に対して isolation が保証される. Dune では full の machine の abstraction を提供する必要がないため, Dune は (conventional VMM に対して) simple かつ高速である.

Dune overview

論文中の Figure 1 で持って Dune の概要を示す. VT-x の terminology を用いてざっくり説明する. まず host は VMX root の ring 0 で動作している. そして通常の process は VMX root, ring 3 で動作している. process は Dune の system call (Dune device への ioctl で実現されている) を用いることで, 不可逆に Dune process になることができる. Dune process は VMX non-root の ring 0 で動作が開始される. この結果 ring 0 向け特権が Dune process に対して公開される一方, VMX root である host に対して Dune process は適切に isolate された状態にある. Dune process は ring 0-3 を持っている状態にあり, この ring protection 自体も Dune process に公開された特権の一つだ.

図中の Dune Module が kernel module として host 側に存在する. Dune process は libDune を利用することもできる. libDune は privileged hardware feature を user-space でうまく用いるための薄い library だ.

Dune は process に対して通常の process とほぼ変わらない環境を与えつつ特権を与える. これはどうすれば達成できるのか? 鍵は virtual memory, system call, そして signal である.

Memory Management

Dune process には特権を利用しない場合は通常の process と同様に動いてほしい, ということは process の virtual memory space を Dune process は保持していなければならない. Dune はこれを Extended Page Table (EPT)1 を用いて実現する. 通常の process の page table を EPT で実現するのだ.

Dune virtual memory overview

論文中の Figure 2 は Dune process と通常の process の page table の関係を示している. 右側が通常の process, 左側が Dune process だ. この EPT と kernel page table (KPT) は全く同じ内容を持っていると考えて良い. KPT の translation を EPT にさせることで, VMX non-root の page table を Dune process に開放する. この時興味深いことに, EPT によって実現される memory space は, machine abstraction のようなほぼ連続な空間ではなく, sparse になる2.

本当は KPT を EPT としてそのまま用いることができれば最良であるが, technical にはいくつかの問題が存在する. (1) EPT は KPT とは format が異なる. (2) x86 の場合, EPT の address width, つまり guest physical address <-> host physical address は同じ幅でなければならない. Dune では guest physical address space として KPT の host virtual address space の幅を与えたいので本来は 48bit になるが, host physical address 側は 36bit physical limit があるため, guest physical address space は 36bit までに制限されてしまう.

(1) に対して Dune は EPT を EPT fault handling で埋めることで対応している. EPT を empty の状態で開始しておき, fault が起こると KPT (Dune process は通常の process なので, Dune mode では実際に使いはしないが KPT を持っている) に query をかけ, 必要な値を埋めるのだ. KPT から値が落とされた/変更された場合は MMU notifier (Linux の機能) で EPT からも落とす.

(2) は work around を持って対応している. Dune では Dune process に map される memory region を制限している, beggining of process (heap 等), mmap region, stack の 3つが Dune によって EPT に map され, これらをそれぞれ 4GB までに制限し, EPT の最初の 12GB 分(34bit) に埋めている. 将来的には, KPT の sparse な region を EPT に pack し, Dune process に remap するよう通知するなどをして対応可能ではあろうとしている.

System Call

次は system calls. Dune は Dune process に対して, 通常の process と同様の system call への interface を提供する必要がある.

Dune syscall

上の図は Dune の発表スライドの図を元に作成した, Dune の syscall のアーキテクチャ図である. 一般に system call は SYSCALL instruction によって発行される. ここが大変興味深いことではあるが, SYSCALL を trap するのは Dune process ring 0 である. つまり Dune process が発行した SYSCALL が Dune process によって trap されるのだ. これは sandboxing としては面白いが (例えばここで filtering などが可能), このままでは host の system call は発行できない.

そこで Dune は system call に VMCALL を用いる. VMCALL は hypercall 発行のための x86 instruction であり, VMX root に VM exit することができる. Dune kernel module は system call に対応する hypercall を備えており, hypercall を発行することで host OS に向かって system call を発行することができる.

しかしこのままでは SYSCALL をすべて VMCALL におきかえた library をつかう必要がある. そこで libDune は ring 0 で発行された SYSCALL を自動的に VMCALL に変換するメカニズムを提供し, 既存 library が変更なしに system call を発行できるようにしている.

Signals

最後に signals である. これについては Dune は大きく仕組みを変更しており, 互換な interface は持っていない. また通常の process とは状況が大きく異なる.

まず, 多くの signal は host から受ける必要はなく, Dune process であれば特権を利用して効率的な方法で handle できる. 例えば, SIGSEGV は, hardware page faults を直接用いることで, より効率的に扱うことができる.

外部から inject されるタイプの signal, 例えば SIGINT については, SIGSEV のようにはいかない. この場合 Dune kernel module は fake hardware interrupt を Dune process に inject する. これによって Dune process は効率的にこれら signal を扱えるだけでなく, hardware interrupt が発行されると ring 3 から ring 0 への transition が起こるため, Dune process 内で privileged mode を変更し sandboxing といったことをしていたとしても, ring 0 が signal に対処することが可能だ.

これらへの対処は通常の signal とは異なるため, libDune の提供する, dune_signal という抽象によって取り扱うこととなる, という limitation が存在する.

Applications

ここまでで Dune の architecture, すなわち Dune process が host との integration を犠牲にせず privileged hardware features を利用できる仕組みを紹介してきた. 次に実際に特権を利用してどのようなことが可能なのかについて, Dune を用いた3つの applications を紹介する.

Sandboxing

Dune process は ring 0 を持っている. これは大きな利点で, 例えば他の binary を ring 3 で動かすといった形で sandboxing を実現することが可能だ. sandboxing は NaCL のような例や, secure な OS container, secure な mobile phone application といったことに役立てられてきた.

Dune による sandboxing は ring 3 で untrusted binary を動作させることで実現される. sandbox 中から触れる memory は page table の supervisor bit によって制限をかけることができる. sandbox が exception を起こそうが, system call を呼ぼうが, それらはすべて Dune process ring 0 によって handle することが可能だ. ここで呼び出し可能な system call を制限するといったことをすると, untrusted binary に対しての filtering / restriction をすることができる. さらに, この handler で変換処理を行えば, host とは全く異なる system call interface を untrusted binary に見せるといったことも可能だ. Dune では sandboxing を拡張し, firewall (connect, bind を trap して filter) や checkpointing (ring 3 の memory, regs, descriptors を disk に save / restore ) も作成している.

Wedge

Wedge は privilege separation system というものだ. まあ具体的にはどういうことかというと, sthread という新しい抽象を導入する. これは fork-like な isolation を提供しつつも thread-like な performance を提供するというものだ. sthread は thread と同様に resource (memory, file descriptor, system calls policy etc.) を共有するが, この時この共有を policy によって制限をかけられる. 例えば server の場合, request を sthread で処理できれば, application code を isolate しつつ performance も得られ都合が良い.

Dune を使った Wedge では, sthread の作成高速化のために recycle を行う. これは最初の sthread 作成時に checkpoint をとっておき, 以降の sthread 作成をここから作ろうというものだ. original の sthread の memory をとっておき, 実行した後, dirty bit のたった page だけ original の memory で上書きすることで, 高速に sthread を restore することができる. 他にも ring protection による実行可能な system call の制限, page table による sthread の accessible な memory region の制限, tagged TLB (Process Context ID をつかう3) による高速な context switching を実現している.

Garbage Collection

Dune の特権を用いれば GC の高速化を行うことが可能だ. 具体的には以下の利用が考えられる.

  1. Fast faults: GC では mprotect による fault を用いる場合がある. Dune では fault を hardware interrupt として host を介さず process 内で処理することができ高速である.
  2. Dirty bits: Dune では page table の dirty bit を読みとることができるので, 触られた memory を memory barrier なしに検知することができる.
  3. Page table: 例えば compaction を行う場合, page table の entry を書き換えるだけで page の内容を別の virtual address region に移してくることが可能だ. また, backing phyiscal page を落としておけば参照した時に fault が起こるので, compaction などを行い, object が移動した時, ある object の保持している別の object への reference が old のままだったとしても, fault handling で検知することが可能だ.
  4. TLB control: GC では memory mapping を触るということが多く行われる. page table を Dune process が保持していれば, TLB invalidation を batch するといったことを行うことができる.

Dune では BoehmGC をこれらによって最適化している.

Evaluation

ここで Dune の評価を確認する. Dune の呈する overhead とはなんだろうか? 1つは VM enter / VM exit のコストだ. Dune process の system call には VM exit / VM enter が必要であり, これは通常の system call よりもコストが高い. また EPT fault 時には VM exit / VM enter が起こり, これもコストが高い. 2つめは, TLB miss コストの増大だ. TLB miss のコストは EPT を用いていた場合高くなる, なぜなら page walk が2段階になるからだ.

Dune table 1

論文中の Table 2 がこのコストを端的に示す. getpid system call はそれ自体はほとんど何もしないので (current から値を読みとるくらいのことしかしない), system call 自体の overhead をみることが可能だ. ここで, (1) system call は処理自体がもっと時間がかかるはず, (2) page fault も頻繁には起きない, ということを踏まえれば, 問題は TLB miss だろう. これは memory locality の低い program においては Dune が overhead になりうることを示している. これが問題になることは Figure 3 が明らかにする.

Dune overhead

Figure 3 は Dune による sandboxing の中で SPEC2000 を動かした時の native に対する slow down を示す, つまり lower is better だ. この時 (black) overall には非常に低い overhead (avg. 2.9%) での sandboxing に成功している一方, mcf, ammp は高い overhead を示している. これらは 高い TLB miss rate を呈した, さきほどの overhead が顕在化した例だ. そこで, TLB miss のコスト及び TLB miss rate を下げるため Dune の sandboxing application にて large page を利用する最適化を行っている (gray). sandboxing は ring 3 からの system call を trap することが可能なため, mmap が発行された場合, huge page を利用するよう flag を modify するのだ (要は, mmap とかを trap して MAP_HUGETLB を立てとこうって話). これによって overhead は改善する. これとほぼ同じ発想でもって huge page を利用する libhugetlbfs をもちいた Linux native 版 (white) と比較してもほぼ同じ結果になっていることがわかる.

Wedge については sthread の作成は fork の 40x, そして context switching は 3x 高速であったとしている. 作成コスト削減は recycle と kernel intervention の削除, context switching は tagged TLB で説明がつく.

Dune GC

最後に GC についてだ. いくつかの application について, Dune: Dune による direct port, Dune TLB: Dune + TLB invalidation を controlling, Dune dirty: Dune TLB + dirty bit を利用することによる memory protection を使わない version となっている. Table 6 がその評価結果となる. Dune は改善が overhead との相殺でどっこいどっこい. Dune TLBDune dirty は素晴らしい改善をみせている. XML の評価だけ改善が見られないが, これは application 中に garbage になるような object が十分に作成されないので, GC の最適化が EPT overhead を償却できてないとのこと. 見ると memory use の allocation と heap がほとんど同じなので, alloc したもの大体 live という状況になってしまっているのがわかる. XML file を複数もらって, process したら破棄して次みたいな事を繰り返すと十分に garbage が出来, 改善した. 10 の 150MB の XML files input で Dune dirty は 12.8% の改善をみせた.

Conclusion

Dune は virtualization hardware を用いて machine abstraction ではなく process abstraction を提供する. process の持つべき memory space, system call interface といった process abstraction を構成するものを VT-x 上で構築していくことで, process に対して privileged hardware feature を isolation を維持したまま見せることに成功した. そして特権によって様々な機能の実現, 最適化が可能なことを demonstrate した.

自分としては, virtualization hardware は VMM に使うんだという固定観念を崩す, 大変興味深い論文だった. この後, Dune の isolation を application / data plane / control plane の isolation に利用する IX へ進んでいく. generic な概念が出たら次 I/O へというのよくある感じするので, なにか出てきたら, この concept に I/O が絡んだ時にどうなるか, とか考えていきたいものだと思う.

  1. VT-x の機能のうちの一つ (追加された). 2段階の page table の解決を用いて virtual address を解決する. もともと, guest virtual address を guest page table に対する変更/監視なしに host physical address まで変換する仕組みを作るために導入された. (guest page table は guest virtual address を guest physical address に変換するので, guest physical address から host physical address の変換 phase があれば guest page table に変更は必要ない)

  2. ちなみに今回 article 上では省略したが初めての VMLAUNCH の時にどうやって process の定常状態まで持っていくかという問題がある. これは technical には OS の bootstrapping に酷似する. Dune では通常 process の時に libDune が identical な map を行う page table を作って (guest virtual address (GVA) <-> guest physical address (GPA) table, かつ GVA, GPA の値が同じ), これを VMLAUNCH 時に CR3 として利用するという形になる. この時, Linux が mmap, stack, heap に使う部分を予め全部 map しておけば, mmap などが呼ばれたとしてもいちいち guest page table も更新する必要はない (もちろん, 実際に Dune process が mmap してない部分を触れば, page table は pass したとしても EPT fault が起こる). CR3 及びその page table entry/directory の address は当然のことながら physical address であることが求められるため面倒そうに思える. が, Dune では GPA は host virtual address (HVA) に等しいため, HVA 上で page table を作って (before entring Dune mode), それを初期 CR3 として渡せば特に労なく動作する. 渡された後の page table をどうするかは Dune process ring 0 の自由だ.

  3. 論文中にはないが, 少し寄り道して tagged TLB の話を確認しておこう. Intel 64 and IA-32 Architectures Software Developer’s Manual の section 4.5 によると, CR4.PCIDE が 1 の場合は CR311:0 が PCID として解釈されることになっている. section 4.10.1 を見ると, PCID が有効な場合, TLB の entry は PCID に関連付けられる. そして TLB を利用する場合, 現在の PCID に関連する entry しか利用しないとのことだ. つまり, PCID ごとに論理 TLB があるくらいの感覚で良いのだろう. PCID は 12bit なので全てで 4096 entries 存在することになる. Process 数が 4096 に制限されるのはまずいので, OS ならばひと工夫必要だろう (個人的には process を 4096 色に coloring して必要なときだけ INVPCID を発行するというのが良さそうと感じる). が, PCID の 4096 entries は寿命の短い sthread の, しかも user-space 実装の id としては十分だろう. Dune process は PCID という特権機能ももちろん用いることができる. Dune の sthread では PCID を用いることで sthread ごとに論理 TLB を割り当てる. これによって TLB flush なしの context switching を実現できる.

Comments