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

• Adam Belay, Andrea Bittau, Ali Mashtizadeh, David Terei, David Mazières, and Christos Kozyrakis. Dune: Safe User-level Access to Privileged CPU Features, In Proc. of 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI ‘12), 2012, pp 335-348.

お気に入りの論文をとの事で, ここでは “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 かつ高速である.

論文中の 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)¹ を用いて実現する. 通常の process の page table を EPT で実現するのだ.

論文中の 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 になる².

本当は 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 の発表スライドの図を元に作成した, 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 をつかう³) による高速な 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段階になるからだ.

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

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 で説明がつく.

最後に 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 TLB と Dune 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 が絡んだ時にどうなるか, とか考えていきたいものだと思う.