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 メモリアクセス時に使った 保護情報をキャッシュする メモリアクセスに使える レジスタそれぞれに用意

Protection Lookaside Buffer: TLBのようなもの(タグ付) 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 SST で表すと… 0x00100020 メモリイメージ Perm の値の意味

SST の利点 Tableのサイズが小さくなる(?) Table のサイズ = セグメントの数 SST で表すと… SST メモリイメージ 00000000 00 01 00 11 SST で表すと… 00 11 00 01 00 10 00 10 00 01 00 SST メモリイメージ

SST の欠点 Tableの検索がバイナリサーチ (= O(log n)) Table の更新が重い 2. 新たなエントリを追加する 00000000 00 1. まず、該当する エントリを探す (バイナリサーチ) 01 ここに新たな セグメントを 追加するには? 00 11 00 11 00 01 10 00 00 10 00 10 これらのエントリを ずらさなければ ならない 00 01 00 SST メモリイメージ

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 こことここに アクセスすると… SST の場合 0x08000 検索回数 : 1回 (最初のアクセス結果が PLB にキャッシュされる) メモリイメージ

SST と MLPT の比較 SST MLPT サイズが小さい(?) 検索回数が少ない 検索が遅い (バイナリサーチ) 更新が重い 無駄なエントリが多い 検索回数が多い 検索が速い (O(1)) 更新が軽い

MLPT + 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種類の実験: 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 は ワード単位で保護を指定できる ハードウェアメモリ保護機構です