仮想機械 温故知新 前田俊行 東京大学米澤研究室.

Presentation on theme: "仮想機械 温故知新 前田俊行 東京大学米澤研究室."— Presentation transcript:

1 仮想機械 温故知新 前田俊行 東京大学米澤研究室

2 目次 論文 “Architecture of Virtual Machines” の紹介
論文 “Formal requirements for Virtualizable Third Generation Architectures” の紹介 IBM VM/370 の紹介(中間報告)

3 今回扱う “VM” ハードウェアインターフェイスを 仮想化するタイプの VM

4 Architecture of Virtual Machines
Robert P. Goldberg In Proceedings of the workshop on virtual computer systems (1973)

5 この論文の要点 VM システムのアーキテクチャモデルを提案 新しい VM システムの実装方法を提案 2つのマッピング
φ-マップと f -マップ 新しい VM システムの実装方法を提案 Hardware Virtualizer VM を効率良く実装可能 再帰的 VM も効率良く実現できる

6 φ-マップ φ-マップ OSインターフェイスから ハードウェアインターフェイスへのマップ 例 ユーザプログラム OS ハードウェア
仮想メモリ → 物理メモリ スレッド → 物理CPU ファイル → 物理ディスク φ-マップ ユーザプログラム OS ハードウェア

7 f -マップ f -マップ ハードウェアインターフェイスから ハードウェアインターフェイスへのマップ 例: OS VMM ハードウェア
VMの物理 CPU → 物理 CPU VMの物理ディスク → 物理ディスク f -マップ OS VMM ハードウェア

8 2つのマップによる VM システムの表現 通常の VM システム φ f ユーザプログラム OS VMM ハードウェア

9 2つのマップによる VM システムの表現 φ f f f f 再帰的 VM システム ユーザプログラム OS VMM VMM VMM VMM
ハードウェア

10 形式的定義: プロセス名とリソース名 プロセス名 p: OSインターフェイスを抽象化したもの
(例) 仮想メモリのアドレス、仮想CPUのレジスタ、 ファイルシステムのファイル名とファイルポインタの組等 リソース名 r: ハードウェアインターフェイスを 抽象化したもの (例) 物理メモリのアドレス、物理CPUのレジスタ、 物理ディスクのアドレス等

11 形式的定義: φ-マップ φは部分関数で φ: P → R ここで P はプロセス名 p の集合 P = { p0, p1, …, pj }
また R はリソース名 r の集合 R = { r0, r1, …, rn }

12 形式的定義: f -マップ f は部分関数で f: R1 → R2 ここで R1、R2 は それぞれリソース名 r の集合

13 φと f による VM システムの表現 f φ: P → R2 f4 f3 f2 f1 φ: P → R5 通常の VM システム

14 φと f による VM システムの表現 φ f ユーザプログラム OS VMM ハードウェア (例) φ= { p1 → rv2,
rr1 p2 rv2 rr2 p3 rv3 ユーザプログラム OS VMM ハードウェア (例) φ= { p1 → rv2, 　　　　p3 → rv3 } f = { rv1 → rr2, 　　　　rv2 → rr1 } のとき、ユーザプログラムが p1 にアクセスすると、 OS と VMM により、 φ(f(p1)) = rr1 へのアクセスに 変換される

15 未定義のプロセス名、リソース名の扱い あるφ-マップ、f-マップで未定義の プロセス名やリソース名が利用されたら、 そのφ-マップ、f-マップを実装するOS、VMM に 適当な処理をさせなければならない

16 未定義のプロセス名、リソース名の扱い φ f ユーザプログラム OS VMM ハードウェア (例) φ= { p1 → rv2,
rr1 p2 rv2 rr2 p3 rv3 ユーザプログラム OS VMM ハードウェア (例) φ= { p1 → rv2, 　　　　p3 → rv3 } f = { rv1 → rr2, 　　　　rv2 → rr1 } のとき、ユーザプログラムが p2 にアクセスしたら、 例外を発生させ OS に処理させなければならない

17 未定義のプロセス名、リソース名の扱い φ f ユーザプログラム OS VMM ハードウェア (例) φ= { p1 → rv2,
rr1 p2 rv2 rr2 p3 rv3 ユーザプログラム OS VMM ハードウェア (例) φ= { p1 → rv2, 　　　　p3 → rv3 } f = { rv1 → rr2, 　　　　rv2 → rr1 } のとき、ユーザプログラムが p3 にアクセスしたら、 例外を発生させ VMM に処理させなければならない

18 モデルから見た VM システム実装 φ の実装 f の実装 φや f の合成 再帰的 VM CP-67 ハードウェア ソフトウェア 不可能
VMware Bochs 可能

19 注 モデルから見た VM システム実装 φ の実装 f の実装 φや f の合成 再帰的 VM CP-67 ハードウェア ソフトウェア
不可能 VMware Bochs 可能 注 φと f の合成が ソフトウェアで行われていても その合成結果 (φ’= f φ) は ハードウェアで実装できる

20 モデルから見た VM システム実装 φ の実装 f の実装 φや f の合成 再帰的 VM Hardware Virtualizer
ハードウェア 可能 CP-67 ソフトウェア 不可能 VMware Bochs

21 Hardware Virtualizer φ-マップや f -マップの合成を ハードウェアでサポートするという VM システムアーキテクチャ
実際に実装されたかは不明 特許は取られている 米国特許 (出願1978年: もう期限切れ?)

22 Hardware Virtualizer の 構成要素
VMID レジスタ 現在どの VM を実行中かを表す マップ合成機構 Φや f を合成するハードウェア機構 例外振分け機構 例外や割込を正しい OS、VMM に届けるための ハードウェア機構

23 Formal Requirements for Virtualizable Third Generation Architecture
Gerald J. Popek Robert P. Goldberg In Communications of the ACM 17(7): (1974)

24 この論文の要点 VM を実現するために 第三世代アーキテクチャが 満たすべき十分条件を 形式的に示した
条件: sensitive 命令 ⊆ privileged 命令 第三世代アーキテクチャ ここでは特権レベル機構や仮想メモリ機構のある アーキテクチャのことをいう

25 形式的定義 マシン状態: S S = ( E, M, P, R ) E : メモリ M: 実行モード P : プログラムカウンタ

26 形式的定義 メモリ: E E = サイズ q の配列

27 形式的定義 実行モード: M M = s または u s : supervisor モード u : user モード

28 形式的定義 プログラムカウンタ: P P = メモリアドレス (配列 E のインデックス)

29 形式的定義 セグメントレジスタ: R R = (Base, Size) Base: セグメントのベースアドレス

30 マシン状態の例 S = ( [ 4, 5, 1, halt ], s, 2, (1, 3) ) マシンが上のような状態 S にあるとき、
そのマシンは supervisor モードで実行中で、 かつ、halt 命令を実行しようとしている pc = 2 だが、R = (1, 3) なので、 実行される命令は E(2+1) = E(3) = halt である

31 形式的定義 命令: i i は関数で i : C → C C : S の有限集合

32 形式的定義: Trap i (E1, M1, P1, R1) = (E2, M2, P2, R2)
命令 i は次の条件を満たすとき “Trap する”という i (E1, M1, P1, R1) = (E2, M2, P2, R2) ただし E2[k] = E1[k], for 0 < k < q E2[0] = ( M1, P1, R1) ( M2, P2, R2) = E1[1] つまり、命令実行前の (M, P, R) が E[0] にセーブされ、 命令実行後の (M, P, R) が E[1] からロードされるようなとき

33 形式的定義: Memory Trap Trap する命令 i は次の条件を満たすとき “Memory Trap する”という
S = ( E, M, P, (Base, Size) ) において 命令 i のアクセスするアドレス a が Size < a (セグメントサイズオーバー) または q < Base + a (メモリサイズオーバー) を満たす

34 形式的定義 Privileged S1= (E, s, P, R) S2= (E, u, P, R) i(S1) は Trap しない
命令 i は以下の条件を満たすとき Privileged であるという 任意の S1= (E, s, P, R) S2= (E, u, P, R) ただし、i(S1)もi(S2)も Memory Trap しない において i(S1) は Trap しない i(S2) は Trap する つまり、user モードで実行すると Trap する命令

35 形式的定義 Control Sensitive
命令 i は以下の条件を満たすとき Control Sensitive であるという ある S1= (E1, M1, P1, R1) i(S1)= S2= (E2, M2, P2, R2) ただし、i(S1)は Memory Trap しない において M1≠M2 and/or R1≠R2 つまり、命令実行後に、例外が生じることなく メモリマッピングが変わったり実行モードが変わったりすること

36 Control Sensitive な命令の例
仮に IA-32 で例えるならば int 命令 (ソフトウェア割込命令) 実行後に実行モード (= M) が変わる場合がある mov 命令 (メモリ操作命令) ページテーブル、GDT、LDT等へのメモリ操作は R を変更することと対応する など 注: ここでの抽象化モデルと IA-32 は必ずしも一致しないので ここで挙げた例は、定義に厳密に基づいたものではない

37 形式的定義 Behavior Sensitive
命令 i は以下の条件を満たすとき Behavior Sensitive であるという R = (b, s) のとき R+x = (b + x, s) ある S1= (E1, M1, P, R) S2= (E2, M2, P, R+x) ただし、i(S1)も i(S2)も Memory Trap せず i(S1) = (E’1, M1, P1, R) i(S2) = (E’2, M2, P2, R+x) E1|R = E2|R+x E1| (b,s) = E2| (b,s) +x ⇔ 0≦ k < s なる k で E1[b+k] = E2[b+x+k] において E’1|R≠E’2|R+x and/or P1≠P2 つまり、命令実行の結果が、例外を生じることなく メモリマッピングや実行モードによって異なること

38 Behavior Sensitive な命令の例
仮に IA-32 で例えるならば sgdt 命令 (GDTレジスタ読出命令) GDT レジスタ (= R に対応) の値によって結果が異なる push 命令 (メモリ操作命令) push CS の実行結果が実行モード (= M) によって異なる など 注: ここでの抽象化モデルと IA-32 は必ずしも一致しないので ここで挙げた例は、定義に厳密に基づいたものではない

39 形式的定義 Sensitive 命令 i は Control Sensitive または Beharior Sensitive であるとき Sensitive であるという

40 定理 1 { i | i は Sensitive } ⊆ { i | i は Privileged }
あるアーキテクチャが 以下の条件を満たすとき そのアーキテクチャは仮想化可能である { i | i は Sensitive } ⊆ { i | i は Privileged } この条件を満たすアーキテクチャ上では、 ゲスト OS を user モードで実行すれば仮想化できる

41 定理 2 あるアーキテクチャが 仮想化可能であるとき そのアーキテクチャは 再帰的仮想化可能である
再帰的仮想化 = VM の上に VM を実現すること

42 定理1 と IA-32 IA-32 には Sensitive であるが Privileged でない命令が存在するので IA-32 は条件を満たさない Sensitive であるが Privileged でない命令 mov 命令、sgdt 命令、push 命令など

43 ハイブリッド仮想化 Supervisor モードでは 命令をハードウェアで実行せずに インタプリタで実行する仮想化の方式
純粋な仮想化よりも アーキテクチャが満たすべき条件は緩い

44 形式的定義 User Sensitive S = (E, u, P, R) i が Sensitive
命令 i は以下の条件を満たすとき User Sensitive であるという S = (E, u, P, R) において i が Sensitive つまり、user モードで実行されたとき Sensitive となる命令

45 定理 3 { i | i は User Sensitive } ⊆ { i | i は Privileged }
あるアーキテクチャが 以下の条件を満たすとき そのアーキテクチャは ハイブリッド仮想化可能である { i | i は User Sensitive } ⊆ { i | i は Privileged } この条件を満たすアーキテクチャ上では、 ゲスト OS を インタプリタ実行すれば仮想化できる

46 定理3 と IA-32 IA-32 には User Sensitive であるが Privileged でない命令が存在するので IA-32 は条件を満たさない User Sensitive であるが Privileged でない命令 mov 命令、sgdt 命令など

47 VMware はどうしているか ハイブリッド仮想化 ただし user モードで実行されるプログラムは 正しいハードウェアが見えない
(例) sgdt 命令の結果は VM の GDT レジスタではなく 本物の GDT レジスタの値となる user モードプログラムが GDT を直接操作できるような OS が あったら、その OS は正しく動作しないであろう

48 VMware はどうしているか ハイブリッド仮想化
ページテーブルへのメモリ操作は、 IA-32 の仕様上 mov CR3 命令が実行されるまで その操作が CPU に反映されないと見なせるので 問題はない Mov CR3 は Privileged 命令、 すなわちインタプリタ実行される そもそも user モードプログラムがページテーブルを 直接操作できるような OS でなければこの問題は存在しない なぜならページテーブルの操作 = Privileged 命令 と見なせるから

49 IBM VM/370 中間報告

50 IBM の汎用計算機の歴史 System 360 (1964) Solid Logic による実装
System 370 (1970) IC による実装 System 390 (1990) いわゆる「メインフレーム」 基本的なアーキテクチャは ほとんど変わっていない CISC、セグメント + ページング

51 IBM の VM の歴史 CP-67 (1966) VM/370 (1972) z/VM 5.1 (2004)
VM/370 の新バージョンのデバッグは VM/370 の古いバージョン上で行われたらしい z/VM 5.1 (2004)

52 VM/370 のアーキテクチャ CMS DOS/360 OS/360 MVS OS CP (= Control Program) VMM
System/370

53 VM/370 の特徴 2つの仮想化モード V=R モード V=V モード
システムに1つだけ存在できる V=V モード VM の物理アドレスは本物の物理アドレスとは 関係なく、ページテーブルによって対応づけるモード いくつでも存在できる (これは S/390 上でのことだが、Linux を V=V モードで 約40000 も同時に実行した人もいるらしい)

54 続く… 現在までにまだ調べ終えていないこと VM/370 が本当に再帰的仮想化可能か? VM-Assist とは何か? など
System/370、VM/370 には VM-Assist という VMM 実装を支援する ハードウェア機構があるらしい など

55 終

56 予備スライド

57 Hardware Virtualizer による 再帰的 VM システムの例
4 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間

58 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 これらが f を表す ここでは簡単のため f は セグメントマップ = (オフセット, サイズ)とする

59 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間

60 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 1 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間

61 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 1 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 これがφを表す ここでは簡単のためφも f 同様 セグメントマップ = (オフセット, サイズ)とする

62 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 1 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1

63 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 1 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1 今、プロセス P1 が VM1.1 上で 動作しているとする このとき LMID レジスタ は 1.1 という値をとっている

64 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 1 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1 もしこのプロセス P1 が アドレス 0 にアクセスすると… (例: load 0)

65 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 1 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1 まずマップ合成機構は φを見に行く φ(0) = 2

66 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 1 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1 次にマップ合成機構は VMID = 1.1 なので VM1 の f の VM1 を見に行く f1(2) = 7 そして仮の VMID を 1 とする

67 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 1 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1 最後にマップ合成機構は 仮のVMID = 1 なのでオリジナルの f のVM1を見に行く f (7) = 11

68 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 1 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1 もしこのプロセス P1 が アドレス 3 にアクセスすると… (例: load 3)

69 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 1 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1 まずマップ合成機構は φを見に行くが、 φ(3) = 未定義 (セグメントサイズを超えている) よって VM1.1 で実行中の OS にセグメント例外を投げる

70 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 5 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1 もしφのセグメントサイズが VM1.1 のサイズをこのように超えているとき プロセス P1 がアドレス 3にアクセスすると…

71 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 5 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1 まずマップ合成機構は φを見に行く φ(3) = 5

72 Hardware Virtualizer による 再帰的 VM システムの例
4 9 12 17 P1: 2, 5 VM1: 4, 8 VM1: 5, 3 VM2: 12, 5 物理メモリ空間 プロセスP1 次にマップ合成機構は VMID = 1.1 なので VM1 の f の VM1 を見に行くが f1(5) = 未定義 (セグメントサイズを超えている) よって VM1 にセグメント例外を投げる