Kernel/VM Advent Calendar 38日目: 仮想化可能なアーキテクチャの要件とx86

Kernel/VM Virtualization x86

http://atnd.org/events/10701

忙しい人向け：Kernel/VM Advent Calendar 38.9日目: 忙しい人のための仮想化可能なアーキテクチャの要件とx86 - yuyarinの日記

カーネル／VM 探検隊なみなさん，初めまして．yuyarin と申します．探検隊には一度も出たことはないのですが，syuu さんに誘われて投稿することにしました．

さて，カーネル／VM ってことなんですが，カーネルに関しては界隈で言われている「普通」に遠く及ばないので，少しかじったことのある仮想化に関係する話をしようかと思います．その前に自己紹介を兼ねて仮想化と僕の関わりについて少し書きます．

大学ではネットワーク工学を専攻しているのですが，学部の卒論では Xen で遊んでました．何かと言うと dom U でコマンド叩いたら自分と同じ仮想マシンが別のハイパーバイザ上にクローンされて簡単にかつオンデマンドに分散計算環境が作れればおもしろいよねー，って話です．blktap のドライバ書いたり Live Migration のコードをいじったりしてました．今思えば色々と穴だらけの研究でした．というか研究なのか疑問です．大学院修士課程ではネットワーク工学分野，特にインターネットのルーティング関係の研究をやりたかったので，一度この研究はクローズしてます．最近はメインの研究と別でクラウド周りで Xen の Live Migration の評価を行ったりしていて，まぁコンピュータについては詳しくないけどほんの少しだけ Xen に明るい感じです．

そんなわけで黒歴史卒論ネタとか Xen の Live Migration ネタとかあるんですが，今回は僕のお勉強も兼ねて仮想化に関する２本の論文を読んで簡単に紹介したいと思います．

１本目は1974年にカリフォルニア大学の Gerald J. Popek とハーバード大学の Robert P. Goldberg が発表した "Formal Requirements for Virtualizable Third Generation Architectures" という論文です．命令セットアーキテクチャが仮想化可能であるための条件を論じた論文です．こちらを主に取り上げます．

http://portal.acm.org/citation.cfm?doid=361011.361073 (要 ACM membership)
www.princeton.edu/~rblee/ELE572Papers/Fall04Readings/secureOS/popek_virtualizable.pdf

２本目は2000年の USENIX Security Symposium で米空軍の John Scott Robin が発表した "Analysis of the Intel Pentium's Ability to Support a Secure Virtual Machine Monitor" という論文です．インテルのCPUでセキュアな仮想マシンモニタを構築できるかを分析した論文ですが．この中から x86 が仮想化可能かを分析している所だけを取り上げます．

http://www.usenix.org/events/sec2000/robin.html

どちらの論文も x86 仮想化関係の人には基礎中の基礎過ぎてそんなものはとっくの昔に読んでいるわと怒られそうですが，僕の勉強のためと思って勘弁して下さい．ごめんなさいごめんなさい．

Formal Requirements for Virtualizable Third Generation Architectures

さて，この論文は今から約40年前に出版されたものです．タイトルは日本語で言うとすると「仮想化可能な第三世代アーキテクチャの形式的要件」とかでしょうか．この論文では当時の第三世代アーキテクチャ (IBM 360, Honeywell 6000, DEC PDP-10 など) が定式化・モデル化され，これらのアーキテクチャが仮想化可能なためには命令セットアーキテクチャがどのような要件を満たさなければならないかについて論じられています．

仮想化可能というのは仮想マシンモニタを構築可能であるということを意味しています．これは同時にそのアーキテクチャで動作するプログラムが仮想マシンとして動作可能であるということを意味しています．

高校の頃から歴史は不得意なのでよく分からないのですが，IBM System 360 Model 67 は仮想化をサポートできて CP-67（世界初の商用仮想化OS）が動くのに，DEC PDP-10 は仮想化できない，この違いは何だろうか，ということのようです．

第三世代アーキテクチャというのはマイクロプロセッサを使うコンピュータのことを指しています．つまり今のプロセッサにも十分適応できる仮想化の要件が述べられています．ちなみに第二世代はトランジスタ式のコンピュータで，第一世代は真空管コンピュータですね．

論文中では記号を用いて定式化・モデル化をしているのですが，この記事ではなるべく式を出さずに日本語で解説する方針にしたいと思います．詳しい式を追うのには元の論文を読むのが誤解もなくてベストだと思います．というか式まで書いてるとほぼコピペになるので．．．

仮想マシンモニタの特性

まず Popek と Goldberg は仮想マシンと仮想マシンモニタとは何かということを論じています．仮想マシンモニタとは何かを論じるにあたって，仮想マシンモニタが持つべき特性として以下の３つの特性を挙げています．

  1. 等価性(Equivalence)
  2. 効率性(Efficiency)
  3. 資源管理(Resource Control)
等価性

Any program run under the VMM should exhibit an effect identical with that demonstrated if the program had been run on the original machine directly

直訳すると，仮想マシンモニタの下で動作するプログラムは元のマシンで直接動作する場合と全く同じ作用を示さなければならない，ということですね．但し書きとして利用可能な資源とタイミングの２つの例外が記されています．前者は仮想マシンモニタの下では利用可能な資源が実機とは異なるかもしれないということで，後者は他に別の仮想マシンが並行して動作しているのでタイミングは実機とは違うかもしれないということです．

この特性の定義によって Time-sharing なオペレーティングシステムは仮想マシンモニタの要件から外れます．

効率性

It demands that a statistically dominant subset of the virtual processor's instructions be executed directly by the real processor, with no software intervention by the VMM.

仮想プロセッサの命令の大部分は実プロセッサによって直接実行されなければならないということです．つまり仮想マシンモニタがソフトウェア的に介入してはいけないということです．

この特性によってエミュレータやシミュレータの類のプログラムは仮想マシンモニタの要件から外れます．

資源管理

The VMM is said to have complete control of these resources if (1) it is not possible for a program running under it in the created environment to access any resource not explicitly allocated to it, and (2) it is possible under certain circumstances for the VMM to regain control of resources already allocated.

仮想マシンモニタは仮想マシンに提供する資源を全て完全に制御できなければならないということです．何をもって完全に制御したことになるのかという要件が以下の２つです．

  1. 仮想マシンモニタの下で動作しているプログラムが，自身に明示的に割り振られていいない資源にアクセスすることが不可能である
  2. ある状況のもとで仮想マシンモニタは既に割り振った資源を取り戻すことが可能である

第三世代アーキテクチャのモデル化

次に Popek と Goldberg は第三世代アーキテクチャを式を用いてモデル化しています．このモデルは当時の IBM 360, Honeywell 6000, DEC PDP-10 が念頭に置かれています．

このモデルにおいてマシンは実行可能ストレージ，モード，プログラムカウンタ，再配置境界レジスタの４つの要素で構成される有限個の状態を取りうる存在として定義されます．命令は状態間を遷移する関数として扱われます．

実行可能ストレージは線型メモリです．モードはユーザモードとハイパーバイザモードの２つが存在します．再配置境界レジスタは仮想メモリの 0 番地に対応する絶対アドレスと仮想メモリのサイズを記録しています．

ここで命令のトラップが定義されていて，トラップというのはある命令が実行されるときに自動的に現在のマシンの状態を保存して制御を予め指定されたルーチンに移す操作のことです．これはプロセッサのモードや再配置境界レジスタやプログラムカウンタを変更することで実現されます．

命令の分類

以上の定義とモデル化を行った上で， Popek と Goldberg はある命令セットアーキテクチャが仮想化可能であるかどうかを判別するために命令の分類を行っています．命令は以下の３種類に分類されます．

  1. 特権命令(privileged instruction)
  2. センシティブ命令(sensitive instructions)
    1. 制御センシティブ命令(control sensitive instructions)
    2. 動作センシティブ命令(behavior sensitive instructions)

特権命令とセンシティブ命令は排他的ではありません．また，センシティブ命令に属さない命令を無害な命令(innocuous instructions)と呼んでいます．後ほど出てきますがそれぞれのセンシティブ命令はさらにユーザセンシティブ命令とハイパーバイザセンシティブ命令に分類されます．

では，それぞれの命令の特徴を見ていきます．

特権命令

いわゆる特権命令そのものです．プロセッサがユーザモードで動作している場合にこの命令が発行されるとトラップします．ハイパーバイザモードではトラップしません．

IBM System/370 の LPSW (Load PSW) が例として挙げられています（PSW: processor status word）．

制御センシティブ命令

That is, an instruction is control sensitive if it attempts to change the amount of (memory) resources available, or affects the processor mode without going through the memory trap sequence.

利用可能な資源の量を変更したりメモリトラップシーケンスを通らずにプロセッサモードを変更しようとするような命令です．平たく言うと資源に対して変更を行う命令です．

全ての特権命令は制御センシティブ命令に属することになります．その他の例としてユーザモードに戻る DEC PDP-10 の JRST 1 命令が挙げられています．

動作センシティブ命令

Intuitively, an instruction is behavior sensitive if the effect of its execution depends on the value of the relocation-bounds register, i.e. upon its location in real memory, or on the mode.

命令の実行の作用が再配置境界レジスタやモードに依存してしまう命令です．

この動作センシティブ命令は２種類しか存在しません．実メモリでの位置（再配置境界レジスタ）に依存する位置センシティブ命令と，マシンのモードに依存するモードセンシティブ命令です．

位置センシティブな命令の例として物理アドレスをロードする IBM360/ 67 の ERA 命令，モードセンシティブな命令の例として前の命令空間から移動する Dec PDP-11/45 の MVPI が挙げられています．

仮想化可能性に関する２つの定理

この分類を受けた上で仮想マシンモニタとは何かということをさらに詳しく定義していますが，そこは省略します．この定義と分析に基づいて３つの定理が述べられて証明・検証されています．これらの定理について紹介します．

定理１：仮想マシンモニタの構成要件

THEOREM 1. For any conventional thh'd generation computer, a virtual machine monitor may be constructed if the set of sensitive instructions for that computer is a subset of the set of privileged instructions.

形式通りの第三世代コンピュータが仮想化可能であるためには全てのセンシティブ命令は特権命令でもある必要があるということです．この論文で一番重要な定理です．

定理２：再帰的な仮想化の要件

THEOREM2. A conventional third generation computer is"recursively virtualizable if it is: (a) virtualizable, and (b) a VMM without any timing dependencies can be constructedfor it.

再帰的な仮想化を行うためにはコンピュータが仮想化可能であり，タイミング依存が存在しない仮想マシンモニタが構築可能である必要があるということです．

再帰的な仮想化とは仮想マシンを仮想マシンモニタとしてその上にさらに仮想マシンを作っていくことを意味しています．

定理３：ハイブリット仮想マシンモニタ

まずハイブリッド仮想マシンモニタ (HVM) って何かと言うと，仮想マシンモニタの特性要件の２つめの効率性を緩めて，仮想マシンモニタが命令をソフトウェアで翻訳してよいとした仮想マシンモニタです．Xen の HVM=Hardware Virtual Machine とややこしいですね．

これを論じるために，それぞれのセンシティブ命令をさらにユーザセンシティブ命令とハイパーバイザセンシティブ命令に分類しています．分類としては例えばユーザモードから実行されたときに制御センシティブな命令になっていれば，その命令はユーザ制御センシティブ (user control sensitive) だ，という具合です．

このハイブリット仮想マシンモニタが構築可能であるための要件を示す定理が次のものです．

THEOREM 3. A hybrid virtual machine monitor may be constructed for any conventional third generation machine in which the set of user sensitive instructions are a subset of the set of privileged instructions.

ハイブリット仮想マシンモニタを構築するためにはユーザセンシティブ命令が特権命令である必要がある，ということです．

先程も例に出てきた PDP-10 の JRST 1 命令はハイパーバイザ制御センシティブ命令に分類されるのですが，これが特権命令でないために仮想化はできませんでした．しかし PDP-10 ではユーザセンシティブ命令が全て特権命令にも分類されるので，ハイブリッド仮想マシンモニタであれば構築可能である，ということになります．

x86 と仮想化

ここまで Popek と Goldberg の論文を追いながら仮想化可能であるアーキテクチャの要件を見てきました．さて，みんなが大好きでちょっと困ったちゃんだけど可愛くてたまらない x86 [要出典] は仮想化可能なんでしょうか？

答えは NO です．困った子ですねー．２本目の Robin の論文によれば，1999年時点の x86 (IA-32) の命令セット約250命令には，残念ながら．特権命令ではないセンシティブ命令が17個あります．

ではRobin の分析ついて見てみましょう．

IA-32 プロセッサに対する仮想化の要件

まず Robin は Popek と Goldberg の定理が今の仮想マシンモニタにも適用できると論じた上で，仮想マシンモニタ (VMM) の分類をしています．その中で Type I VMM は直接マシンの上で動作するものと定義しています．この Type I VMM を実現するためのプロセッサの要件が次のようにまとめられています．

  • 要件1: 非特権命令の実行方法は特権モードとユーザモードで等価でなくてはならない
  • 要件2: 実システムや他のVMをアクティブなVMから保護するために保護システムやアドレス変換システムが存在しなければならない
  • 要件3: 仮想マシンが以下のセンシティブ命令を実行しようとしたときに自動的にVMMに通知されなくてはならない
    • 3A: モードやマシンの状態を変更・参照する命令
    • 3B: センシティブなレジスタやメモリロケーションを読み込み・変更する命令
    • 3C: ストレージ保護システム，メモリシステム，アドレス再配置システムを参照する命令
    • 3D: すべての I/O 命令

要件3Bで言われている命令は例えば Time Stamp Counter を参照する RDTSC 命令や IDTR を参照する LIDT 命令のことです．

レジスタ操作命令

レジスタ操作命令のうち以下の６命令が要件3Bを満たしていません．

  • SGDT, SIDT, SLDT
  • SMSW
  • PUSHF, POPF
システム保護命令

システム保護命令のうちの以下の12命令が要件3Cを満たしていません．

  • LAR, LSL, VERR, VERW
  • POP
  • PUSH
  • CALL, JMP, INT n, RET
  • STR
  • MOVE

要件を満たさない各命令

17個あると言っているのに数えたら18個あるんですが，何なんでしょうか．僕たちは２つで１つだみたいな命令ありましたっけ．

追記(2011/01/13 22:00:00)：VERR, VERW はインストラクションリファレンスで VERR/VERW と１つの項目になっているので，２つで１つとしてカウントされているのかもしれない．

とりあえず各命令の何が問題なのかをさらっとまとめてみますが，論文を読んだほうが正確でいいと思います．

基本的に特権レベルが問題になります．CPL に依存するレジスタの操作であったり，実行中に CPL, RPL, DPL が検査される命令なんかに対して，仮想マシンのOSが ring 3 で動作していることが原因で問題が起きてしまうということが大半のようです．

SGDT, SIDT, SLDT

SGDT, SIDT, SLDT はディスクリプタテーブルの値をメモリにストアする命令で非特権命令です．[GIL]DTR は１つしかないので複数の仮想マシンが同じレジスタを使おうとするときに問題が生じてしまいます．レジスタに対する CPL=0 以外のアクセスはトラップすることができるので，仮想マシンモニタで望ましい操作に置き換えることができると言っているのだけど，S[GIL]DT を [GIL]DTR の参照に使い，その値を自身のオペレーションに使おうとするときに問題が生じます，とも言っていて正直何を言っているのかよく分からないので誰か解説希望．

SMSW

SMSW は非特権命令でオペレーションシステムやプロセッサの状態を記録する CR0 レジスタを保存するのだけど，仮想マシンのモードの状況によっては PE bit が誤った状態でストアされてしまうので問題が生じるということ．

ただし SMSW は 386 以降のプロセッサで 286 への後方互換を考えた場合にしか問題にならないので事実上無視していいかと．

PUSHF, POPF

PUSHF と POPF は悪名高い EFLAGS レジスタ[要出典]を非特権モードでスタックに/からpush/popしてスタックポインタを変更する命令ですが，PUSHF では SMSW 同様に誤ったフラグをストアしてしまう可能性があり，POPF ではフラグの値を書き換えてしまう可能性があるということです．IOPL あたりが絡んでます．

LAR, LSL, VERR, VERW

LAR, LSL, VERR, VERW の４つの命令は実行の最中に CPL

POP, PUSH

POP と PUSH は CPL に依存しています．CPL によって POP は CS レジスタを操作できません．ロードしているレジスタとその時の CPL, DPL, RPL に依ってはいくつかの状況で問題を引き起こします．PUSH も CS レジスタと SS レジスタが CPL を含んでいるため同様の問題を引き起こします．

CALL, JMP, INT n, RET

CALL は near call，同じ特権レベルへの far call，違う特権レベルへの far call，タスクスイッチの４種類に分類できるのですが，このうち違う特権レベルへの far call とタスクスイッチで問題が生じます．違う特権レベルへの far call では call gate を通じてプロシージャのコードセグメントへアクセスする必要があります．タスクはそれぞれの特権レベルに応じたスタックを使うため，プロセッサはタスクを呼び出されたプロシージャの新しい特権レベルに対応するスタックに切り替えます．タスクスイッチは call gate と似ているのですが，ターゲットオペランドが task gate のセグメントセレクタであることが違います．これらの CALL では CPL と RPL を DPL と比較します．よって仮想マシンが CPL=3 で動作している場合に正しく動作しない可能性があるということです．

JMP は CALL 同様ですが制御を移すのでリターンアドレスを記録しない点だけで違います．

INT は CALL に似ていますがリターンアドレスを push する前に EFLAGS レジスタを push してます．

RET は CALL の逆の操作なので察してください．

STR

STR はタスクレジスタからセグメントセレクタを汎用レジスタやメモリにストアする命令なのですが，セグメントセレクタからタスクスステートセグメントを参照して，タスクが自身の RPL を検査できるようになってしまうことが問題になるようです．

MOVE

MOV では６つ全てのセグメントレジスタを汎用レジスタやメモリにストアすることができるの便利な子なのですが， CPL を含んでいる CS レジスタと SS レジスタをストアできることが問題になります．

仮想化支援機構 Intel VT

こんな感じで x86 は Popek と Goldberg のいう仮想化を達成することができませんでした．それを可能にするのが Intel VT や AMD-V の仮想化支援機構です．登場したのは2007年ごろだったでしょうか．これらの拡張によって Popek と Goldberg の仮想化要件を満たす x86 プロセッサが実現されました．

少々長くなってきたのでこの辺の話はまた今度にしたいと思います．もしくは誰か書いてくれますかね．

あとがき

x86 周りの怪しい記述は @oza_x86 先生あたりが査読してくれるはずです．MIPS が仮想化要件を満たすかどうかは @syuu1228 先生が調べて記事にしてくれると思います．

長々と書いてしまいましたが読んでくださった方，ありがとうございました．ツッコミ，訂正等お待ちしております．

参考文献

Gerald J. Popek and Robert P. Goldberg, "Formal Requirements for Virtualizable Third Generation Architectures", Communications of the ACM 17 (7): 412 –421, 1974

John Scott Robin and Cynthia E. Irvine, "Analysis of the Intel Pentium's Ability to Support a Secure Virtual Machine Monitor", Proc. 9th USENIX Security Symposium, 2000

仮想化技術Xen-概念と内部構造

仮想化技術Xen-概念と内部構造

卒論の実装をするのにすごくお世話になった本．

MacBook Air 11インチ欲しい！