Linux

Linux - ページング

More than 3 years have passed since last update.

Linux kernel におけるページングについて基礎的な内容を整理する。

動作原理

32bit

基本

2段階の変換テーブルでページングを行う。

1段階目を Page Directory と呼ぶ。
4KB の大きさで 4byte の Page Directory Entry (PDE) を 1024 個含む。
Page Directory の物理アドレスは CR3 レジスタに格納される。

リニアアドレス上位 10bit が Page Directory のインデックスとして利用されて2段階目の変換テーブルである Page Table の物理アドレスが引き当てられる。
なお、ページフレームは 4KB 境界に合わせられるので、下位 12bit は 0 となる(4KB = 0x1000)
つまり Page Table を引き当てるには 20bit あればいい。
そうなると PDE 4byte = 32bit のうち 12bit は余るわけだが、そこには存在フラグや Dirty フラグなどが割り当てられている。

引き当てられた Page Table も Page Directory と同様に 4byte の Page Table Entry (PTE) を 1024 個含む(大きさは 4KB)
PTE を引き当てるためには PDE を引き当てるために使われた 10bit に続く 10bit がインデックスとして利用され、その結果ページに対応するフレームの物理アドレスが解決される。
こちらも PDE と同じ道理で 20bit しかつかわないので残りの 12bit で同じくフラグを制御している。

拡張

Page Directory のみを用いる。
CR4 レジスタのビットをセットすることでこの動作が可能となる。
このレジスタをセットすると Page Size Extention (PSE) が有効になる。
PSE では 4KB, 4MB のフレームが混在しても構わないが、CR4 だけだと PDE の指す物理アドレスが Page Table なのか 4MB のページフレームなのかがわからない。
そこで PDE の 7bit 目を利用して、これを判別するようにしている。

PSE で 4MB フレームを使うメリットは TLB のキャッシュヒット率が上がることにある。
CPU は 4KB, 4MB フレームで別々の TLB を設定しているため、効率良く動作することが期待できる。
頻繁に参照されるカーネルは 4MB フレームを利用して動作効率を引き上げている。
ただし一方で小さなプログラムにおいては、たとえば 2KB のサイズなのに 4MB のフレームを占拠しているといったことが起こり得る。

64bit

基本

64bit mode においては仮想メモリ空間が 48bit もあるので、2段階のテーブルでは非効率になってしまう。
そこで新たに2つの上位層を導入してアドレス解決を行っている。

テーブルのサイズは変わらず 4KB のままで、Page Map Level4 (PML4), Page Directory Pointer (PDP) の2つが使われる。
それぞれエントリの呼称は PML4E, PDPE となる。

32bit のときはエントリのサイズが 4byte だったが、64bit では扱うアドレスサイズも増えたので 8byte に拡張されている。
その代わりにエントリ数は半分になっている。
また、32bit では 10bit x 2 + 12bit = 32bit で引き当てていたが、64bit では 9bit x 4 + 12bit = 48bit で引き当てている。
8byte = 64bit なので 32bit と同様のフラグで使っても余る領域があるが、これは将来の CPU 進化にむけた予約領域として取られている。
32bit 時と違うものとして 63bit 目に XD フラグの領域がある。
これはバッファオーバフロー攻撃を防ぐためのもので、これが設定されているフレームではプログラムの実行ができなくなる。
AMD CPU では NX と呼ばれる。

拡張

32bit 時と同じく PDE の 7bit 目をセットすれば PSE を利用することができる。
ただし引き当てに使われるアドレスが 1bit 減って 9bit になっている都合上、4MB ではなく 2MB ページフレームとなる。
さらに一部の CPU では PDPE の 7bit 目をセットすると 1GB ページフレームが利用できる。

TLB

Page Directory や Page Table は全てメモリ上にあるデータ。
リニアアドレスを物理アドレスに解決するために毎回 PDE, PTE にアクセスしにいくのは非効率的。
よって CPU には直近でアクセスした PDE, PTE をキャッシュするための機構があり、これが Translation Lookaside Buffer。
TLB が満タンになったときは CPU が頻度の低いキャッシュを選んで捨てている。
ほとんどのプログラムでは参照局所性が見られるため、この機能がある。