Mondriaan Memory Protection の調査 調べた人: 前田俊行 一言でいうと • ハードウェアのメモリ保護を ワード単位にします – 理由: 細粒度メモリ保護が欲しい → でも今のメモリ保護はページ単位で使えない → じゃあワード単位にしよう 参考文献 • E. Witchel, J. Cates and K. Asanovic “Mondrian Memory Protection” In proc. of ASPLOS 2002. • E. Witchel and K. Asanovic “Hardware Works, Software Doesn’t: Enforcing Modularity with Mondriaan Memory Protection” In proc. of HotOS 2003. • E. Witchel, J. Rhee and K. Asanovic “Mondrix: Memory Isolation for Linux using Mondriaan Memory Protection” In proc. of SOSP 2005. 細粒度メモリ保護とは • 1つのアドレス空間内で 複数のメモリ保護ドメインを持つこと • たいてい1スレッドに1保護ドメインを割り当てる なぜ “Mondriaan” か • Piet Mondriaan (1872-1944) Composition with Red, Yellow and Blue (1921) どうやって実現するか? • “Permissions Table” を導入する – Permissions Table • マッピング情報のないページテーブルのようなもの • ワード単位でメモリ保護を指定できる • (実装方式については後述) • 元々の ISA は変わらない – Permissions Table を「付け加える」だけ MMP (Mondriaan Memory Protection) System 概略図 Sidecar: 保護情報キャッシュ その1 メモリアクセス時に使った 保護情報をキャッシュする メモリアクセスに使える レジスタそれぞれに用意 PLB: 保護情報キャッシュ その2 Protection Lookaside Buffer: TLBのようなもの(タグ付) PLB のタグ Permissions Table ページテーブルの ようなもの ここで重要な問題 • Permissions Table をどう実装する? – この論文が示す方法は3つ • SST: Sorted Segment Table • MLPT: Multi-level Permissions Table • MLPT + SST SST: Sorted Segment Table • 保護範囲(= セグメント)ごとに保護を指定する 0x00000000 0x00100020 SST で表すと… メモリイメージ Perm の値の意味 SST の利点 • Tableのサイズが小さくなる(?) – Table のサイズ = セグメントの数 SST で表すと… メモリイメージ 00000000 00 01 00 11 00 11 00 01 00 10 00 10 00 01 00 SST SST の欠点 • Tableの検索がバイナリサーチ (= O(log n)) • Table の更新が重い ここに新たな セグメントを 追加するには? メモリイメージ 1. まず、該当する エントリを探す (バイナリサーチ) 00000000 00 01 00 11 00 11 00 01 00 10 00 10 00 01 00 SST 2. 新たなエントリを 追加する 10 00 これらのエントリを ずらさなければ ならない MLPT: Multi-level Protection Table • アドレスごとに保護を指定する アドレス分解 Perm Table Base Table のエントリサイズ = 32 bit 1エントリで指定できる保護 = (32 / 2) 個 = 16 個 指定できる保護単位 = (64 / 16) バイト = 4 バイト = 1 ワード MLPTエントリ MLPT の利点 • Table 検索が速い (= O(1)) – 最悪でも3回のメモリアクセスで エントリが必ず得られる Perm Table Base MLPT の欠点 • 無駄な table 検索が増える MLPT の場合 検索回数 : 2回 (同じセグメントに 2回アクセスしたことがわからない) 0x01000 こことここに アクセスすると… 0x08000 SST の場合 検索回数 : 1回 (最初のアクセス結果が PLB にキャッシュされる) メモリイメージ SST と MLPT の比較 • SST • MLPT – サイズが小さい(?) – 無駄なエントリが多い – 検索回数が少ない – 検索回数が多い – 検索が遅い (バイナリサーチ) – 検索が速い (O(1)) – 更新が重い – 更新が軽い MLPT + SST (例によって)おいしいとこどりを目指す • SST • MLPT – サイズが小さい(?) – 無駄なエントリが多い – 検索回数が少ない – 検索回数が多い – 検索が遅い (バイナリサーチ) – 検索が速い (O(1)) – 更新が重い – 更新が軽い MLPT + SST • MLPT のエントリに SST を取れるようにする mini-SST エントリ Perm Table Base MLPT with mini-SST の利点 • 検索回数が減る – エントリがアドレス範囲外のセグメントの情報も持てるため • (PLB にキャッシュされやすくなる) mini-SST エントリ MLPT with mini-SST の欠点 • Table の更新が複雑 – 1つのセグメントの情報が複数エントリに存在するため ここに新たに セグメントを 作るには? mini-SST エントリ 性能評価実験 • MMP によるオーバヘッドを評価した – ベンチマークプログラムの実行オーバヘッドを測定した – 2種類の実験: • 従来の保護を MMP で再現したときのオーバヘッド測定 » Read-only text, read-only data, read-write data and stacks • 細粒度保護を MMP で実現したときのオーバヘッド測定 » malloc で確保したメモリごとにセグメントを作る (正確には確保したメモリの周りにもう2つ無効セグメントを作る) – ハードウェアがないのでシミュレータ上で実験した • MIPSアーキテクチャ上に実現 ベンチマークの種類 Refs : メモリアクセス回数 (load & store) Segments : 作られるセグメント数 ( = malloc 回数×2) Refs/Update: メモリアクセス回数 / Table 更新の回数 Cs : 従来の保護で実行したときのセグメント数 従来の保護を MMP で 再現したときのオーバヘッド X-ref : Table へのアクセス回数 / プログラムのメモリアクセス回数 Space : Table のサイズ / プログラム終了時の有効メモリ領域のサイズ l/k : Table 検索時のメモリアクセス回数 / Table 検索回数 細粒度保護を MMP で 実現したときのオーバヘッド SST vs. MLTP with mini-SST Space : Table のサイズ / プログラム終了時の有効メモリ領域のサイズ X-ref : Table へのアクセス回数 / プログラムのメモリアクセス回数 upd : Table 更新時のメモリアクセス回数 / Table 検索&更新時のメモリアクセス回数 ld/lk : Table 検索時のメモリアクセス回数 / Table 検索回数 細粒度保護を MMP で 実現したときのオーバヘッド MLPT vs. MLPT with mini-SST Space : Table のサイズ / プログラム終了時の有効メモリ領域のサイズ X-ref : Table へのアクセス回数 / プログラムのメモリアクセス回数 upd : Table 更新時のメモリアクセス回数 / Table 検索&更新時のメモリアクセス回数 ld/lk : Table 検索時のメモリアクセス回数 / Table 検索回数 その他 • MMP を使って Linux を改造した (Mondrix) – Linux のバグを1つ見つけた • (これは x86 シミュレータで, SOSP 2005) まとめ • Mondriaan Memory Protection は ワード単位で保護を指定できる ハードウェアメモリ保護機構です
© Copyright 2024 ExpyDoc
