はじめに

少し前に、ネタと時間がありそうだったので、勢いで 12/24 のアドベントカレンダーに登録してしまいました。その記事の準備のため、Windows のページテーブル周りの動きを調べていたところ分量が増えてきたので、アドベントカレンダーの記事を分けることにしました。どうせ Windows カテゴリ人気ないし。貸し切り状態ですわ。

第一回目の記事は、ページングについてです。何を今更、って感じですかね。OS 小学校の一年生ぐらいで習う内容かもしれませんが、私の頭と指のリハビリにお付き合いください。最近文章を書いていないので筆が進まないんですよ。

環境は以下の通りです。Windows 10 のバージョン表記はどうするのが正しいんですかね。

OS: Windows 10, version 20H2 + KB4594440 (OS Build: 19042.631)
Debugger: 10.0.19041.1 (included in Windows 10 2004 WDK)

PML4 ページング

まずはハードウェア側で行われるページングの動作を確認しましょう。この章は Intel SDM Volume 3 Chapter 4 の部分翻訳みたいなものです。

Intel® 64 and IA-32 Architectures SDM
https://software.intel.com/content/www/us/en/develop/download/intel-64-and-ia-32-architectures-sdm-combined-volumes-1-2a-2b-2c-2d-3a-3b-3c-3d-and-4.html

さて、昨今の OS は CPU のページング機構を使うことが一般的だと思います。そして最近の x86 (x64 含む) 系 CPU は、4 種類のページングモードをサポートしています。

32-bit
PAE (= Physical Address Extension)
PML4 (= Page Map Level 4)
PML5 (Intel なら第 10 世代 IceLake 以降。AMD? 知らない子ですね。)

x64 の Windows は、PML4 ページングを使います。

x64 対応の CPU で 32bit Windows を動かす場合は、基本的に PAE ページングが使われます。bcdedit を使えば強制的に PAE を無効にできるみたいですが、手元の Hyper-V VM 上の 32bit Windows 10 の PAE を無効にすることはできませんでした。深入りしていないので詳細は不明です。

Physical Address Extension - Win32 apps | Microsoft Docs
https://docs.microsoft.com/en-us/windows/win32/memory/physical-address-extension

PML4 ページングを使うと、48-bit の仮想アドレス (正確にはセグメンテーションを解決した後の linear address) を 52-bit の物理アドレスに変換することができます。今更説明するまでもないと思いますが、64-bit CPU と言っても、現在巷に出回っている 64-bit CPU はメモリ空間に関しては 64-bit 全てを利用できるわけではありません。

PML4 ページングでは、仮想アドレスの 63:48 の位置にある上位 16 ビットは使われません。ただし、使われないビットを含めて 63:47 の位置にある上位 17 ビットの値は等しくなければなりません。すなわち、ページング可能な仮想アドレスは 0000 0000 0000 0000 から 0000 7fff ffff ffff ffff の 2^47 種類と、ffff 8000 0000 0000 から ffff ffff ffff ffff の 2^47 種類を合わせた 2^48 種類のアドレスに限られ、これらのアドレスを Intel SDM では canonical address と呼んでいます。WRMSR や SYSRET など、いくつかの CPU 命令では、canonical ではないアドレスが渡されると #GP 例外を発生させます。

仮想 48-bit を物理 52-bit に変換するということは、物理 RAM を 4PB より多く積んでいても、4PB までしか使われないことになります。また、仮に 4PB の物理メモリを積んでいても、仮想アドレスが 48-bit に限られるため、1 プロセスが同時に扱えるメモリは最大で 256TB です。PML5 を使えば、変換後の物理アドレスは依然として 52-bit のままですが、仮想アドレスの幅が 57-bit まで広がるため、1 プロセスが 4PB 全てを使うことができるようになります。富豪プログラマーも満足できるのではないでしょうか。ただ Windows はまだ PML5 に対応していません。Linux は PML5 用の config スイッチがあった気がします。富豪プログラマーは Linux をビルドしないといけない。

ページングの説明には、仮想アドレスのどのビットがどのテーブルに対応するかを示す図を添えるのが定番です。その定番に倣い、私も図を作りました。SDM の図をコピペするのも悔しいですし。図のスケールがおかしいのはパワポの High DPI への対応が微妙だからだと思って欲しい。

PML4 のアドレス変換は、その名が示す通り 4 階層のテーブルを使います。これは OS 側で用意しなければなりません。それぞれのテーブルは、1 エントリ 8 バイトの値を単純に 512 エントリ並べたもので、1 テーブル 4096 バイト、4KB ページ一つ分に収まるようになっています。4 種類のテーブルには以下のような名前がついています。PML4 から明らかにネーミングルールが変わっていますね。まるで Windows 10 の大型アップデートにつけられた名前 (Creator Update とかそういうやつ) のようだ。

PML4 Table
Page Directory Pointer Table
Page Directory Table
Page Table

それぞれのテーブルのエントリのことを、テーブル名の後に Entry を付け、PML4 Entry (= PML4E)、Page Directory Pointer Table Entry (= PDPTE)、Page Directory Entry (= PDE)、Page Table Entry (= PTE) と呼びます。なぜか PML4TE や PDTE とは呼びません。ここも一貫性がないな。

PML4 ページングの動作は、変換対象となる仮想アドレス 48-bit を 9 + 9 + 9 + 9 + 12 の 5 つに分け、9-bit ずつに分けた部分をそれぞれの階層のテーブルのインデックスとして使い、最後の 12-bit を物理メモリ上の 4KB ページのオフセットとして使う、というものです。それぞれのテーブルエントリが管理用ビットと共に次の階層のテーブルの先頭の物理アドレスを指し示していて、最後のテーブルである Page Table がその名前の通り、変換対象の仮想アドレスを含むページの先頭の物理アドレスを示すので、そこに仮想アドレスの下位 12-bit であるオフセットを加算すれば、変換後の物理アドレスが得られます。起点となる第一階層テーブルの先頭アドレスは、CR3 レジスターの値から取得します。Windows ではこの起点となるアドレスを DirectoryTableBase (または DirBase) と呼びます。

PML4 では、物理メモリを区切るページとして、4KB 以外にも 2MB ページ、1GB ページというサイズも組み合わせて扱うことができます。これは、1 階層分ののページテーブルをスキップすることで余った 9-bit を、ページのオフセットに組み込むことで実現しています。4KB ページでは 12-bit がオフセットでしたが、Page Table の 1 階層をスキップして Page Directory がページを指し示すようにすると、ページのオフセットが 12 + 9 = 21-bit で2MB 、もう一階層スキップして Page Directory Pointer Table が直接ページを指し示すようにすると、ページのオフセットが 12 + 9 + 9 = 30-bit で 1GB になる、という仕組みです。PDPTE や PDE の参照先が仮想のテーブルなのかページなのか、という情報は、テーブルエントリの PS フラグというビットで確認できるようになっています。

ところで、32bit ページングにも同様に 4KB より大きいサイズのページを扱う仕組みがありますが、その場合のページサイズは 4MB となります。これは、32-bit でも 64-bit でもテーブル全体のサイズを 4KB に固定している一方で、32-bit ではテーブル 1 エントリが 4 バイトになるためです。その結果、テーブルのエントリ数が PML4 のときの倍の 1024 になるので、Page Directory が直接ページを指定するようにすると、余るビット数が 9 ではなく 10 となり、ページのオフセットが 10 + 12 = 22-bit で 4MB になります。

PML5 になると、PML5 Table というテーブルが PML4 の上位階層として追加され、仮想アドレス 56:48 の 9-bit 分を PML5 テーブルのインデックスとして使うようになります。Intel SDM によると、PML4E の PS フラグ部分は "Reserved (must be 0)" と記載されているので、PML4 Table が直接ページを指定するような 512GB ページは今のところ存在しないようです。

なお、これらの 4KB より大きなページのことを Windows では Large Page、Linux では Huge Page、BSD では Super Page と呼びます。Hyper-V なんかもそうですが、Super とか Hyper って修飾はちょっと・・・。

ここまで分かったところで、カーネルデバッガーを使って PML4 ページングの様子を見てみましょう。プログラムは以下の NMAKE プロジェクトをビルドすると作られる t.exe を使います。

msmania/mmdemo: NT Kernel Memory Manager demo
https://github.com/msmania/mmdemo/tree/v1.0

メインの処理は src/largepage.cpp の LargePageTest() で、1GB 及び 2MB のサイズのメモリを MEM_LARGE_PAGES フラグ付きで VirtualAlloc して、そのアドレスを printf するだけです。メモリマネージャー側で、要求するサイズに応じたラージページを適宜確保してくれるはずです。

若干話が逸れますが、Windows でラージページを使うためには注意点があり、以下のページに記載があるようにプロセスのトークンが SeLockMemoryPrivilege 権限を保持し、有効になっていないといけません。これを忘れると VirtualAlloc は ERROR_PRIVILEGE_NOT_HELD で失敗します。

Large-Page Support - Win32 apps | Microsoft Docs
https://docs.microsoft.com/en-us/windows/win32/memory/large-page-support

さらに、トークンが権限を保持している状態と、保持している権限が有効になっている状態は異なる概念であり、トークンが権限を保持していない場合、AdjustTokenPrivileges を使っていきなり権限を有効にすることはできません。既定では、SeLockMemoryPrivilege 権限は Administrator を含めて SYSTEM 以外のどのユーザーにも割り当てられていないので、プログラム実行前に別途設定する必要があります。おそらくラージページは、SYSTEM アカウントで動作するサービスアプリケーションでのみ使うことが想定されているのだと思います。上記ページに、ラージページはページアウトされないと書かれていますが、その弊害として SeLockMemoryPrivilege 権限が必要になるのかもしれません。

権限をトークンに保持させるには、ローカルセキュリティーポリシー (secpol.msc) を開き、
Security Settings > Local Policies > User Rights Assignment 配下にある "Lock pages in memory" ポリシーにプログラムを実行させるアカウントを追加して、そのユーザーで再ログオンする必要があります。

Lock pages in memory (Windows 10) - Windows security | Microsoft Docs
https://docs.microsoft.com/en-us/windows/security/threat-protection/security-policy-settings/lock-pages-in-memory

ポリシーを変えるのが気に食わない、または面倒くさい場合は、PsExec を使って "psexec.exe -i -s cmd.exe" などと実行し、コマンドプロンプトを SYSTEM ユーザーで実行した上で t.exe を実行する方法もあります。こっちの方が楽ですかね。

どちらの方法にせよ、プログラムを実行してこんな出力が確認できれば環境構築は完了です。

D:\MSWORK> D:\src\mmdemo\bin\amd64\t.exe
1GB Page: 000001F140000000
2MB Page: 000001F10F000000

デバッグを簡単にするため、環境変数 PLEASE_PAUSE が定義されている場合は、メモリが確保された直後に __debugbreak() を実行するようにしておきました。システムにカーネルデバッガーをアタッチした状態で、コマンドプロンプトで "set PLEASE_PAUSE=1" のように環境変数を適当な値で定義してから t.exe を実行すると、カーネルデバッガーにブレークインします。その後、横着して dv コマンドを使って、確保されたアドレスを取得すると以下のような出力が得られました。

Break instruction exception - code 80000003 (first chance)
0033:00007ff6`3b168234 cc              int     3
1: kd> .reload
Connected to Windows 10 19041 x64 target at (Thu Dec  3 18:06:42.168 2020 (UTC - 8:00)), ptr64 TRUE
Loading Kernel Symbols
...............................................................
................................................................
..............................................
Loading User Symbols
........
Loading unloaded module list
......
*** WARNING: Unable to verify checksum for t.exe
1: kd> dv
       rawToken = 0x00000000`00000000
          token = class std::unique_ptr<void *,HandleCloser>
        page1gb = class std::unique_ptr<void *,PageFreer>
        page2mb = class std::unique_ptr<void *,PageFreer>
1: kd> dt page1gb -b
Local var @ 0x6bef30f890 Type std::unique_ptr<void *,PageFreer>
   +0x000 _Mypair          : std::_Compressed_pair<PageFreer,void *,1>
      +0x000 _Myval2          : 0x00000176`80000000
1: kd> dt page2mb -b
Local var @ 0x6bef30f898 Type std::unique_ptr<void *,PageFreer>
   +0x000 _Mypair          : std::_Compressed_pair<PageFreer,void *,1>
      +0x000 _Myval2          : 0x00000176`51600000

0x00000176`80000000 が 1GB のバッファー、0x00000176`51600000 が 2MB のバッファーです。まずはラージページが確保されているのかどうかを知りたくなりますね。そんなときに便利なコマンドが !pte です。

1: kd> !pte 0x00000176`80000000
                                           VA 0000017680000000
PXE at FFFFA4D269349010    PPE at FFFFA4D269202ED0    PDE at FFFFA4D2405DA000    PTE at FFFFA480BB400000
contains 0A000001801EA867  contains 8A000001000008E7  contains 0000000000000000  contains 0000000000000000
pfn 1801ea    ---DA--UWEV  pfn 100000    --LDA--UW-V  LARGE PAGE pfn 100000        LARGE PAGE pfn 100000   

1: kd> !pte 0x00000176`51600000
                                           VA 0000017651600000
PXE at FFFFA4D269349010    PPE at FFFFA4D269202EC8    PDE at FFFFA4D2405D9458    PTE at FFFFA480BB28B000
contains 0A000001801EA867  contains 0A0000017FBEB867  contains 8A000001820000A5  contains 0000000000000000
pfn 1801ea    ---DA--UWEV  pfn 17fbeb    ---DA--UWEV  pfn 182000    --L-A--UR-V  LARGE PAGE pfn 182000

!pte コマンドは、仮想アドレスを PFN (= Page Frame Number) と呼ばれる値に変換してくれます。PFN は物理メモリ上にあるページの通し番号で、これに 4KB = 4096 をかけた数値が物理アドレスになります。このコマンドでは PML4E を PXE、PDPTE を PPE と呼ぶみたいです。

pte - Windows drivers | Microsoft Docs
https://docs.microsoft.com/en-us/windows-hardware/drivers/debugger/-pte

上記出力の 100000 が 1GB バッファーの PFN、182000 が 2MB バッファーの PFN です。前者は、PPE (= PDPTE) が既に PFN 100000 を示しており、PDE と PTE のところには、LARGE PAGE という表示とともにラージページの PFN 100000 が表示されており、PDE や PTE は存在しないことが分かります。これは 1GB ページが確保ことを意味します。後者の 2MB バッファーの方は、PDE の示す PFN 182000 がラージページであり、PTE だけがスキップされているので 2MB ページが確保されていることが分かります。どちらも想定していた動作になりました。

ついでに 4KB の普通のページも見てみましょう。ここでは rip レジスターの値に対して !pte を実行してみます。

1: kd> !pte @rip
                                           VA 00007ff63b168234
PXE at FFFFA4D2693497F8    PPE at FFFFA4D2692FFEC0    PDE at FFFFA4D25FFD8EC0    PTE at FFFFA4BFFB1D8B40
contains 0A000001801DC867  contains 0A000001801DD867  contains 0A0000017FBDE867  contains 0000000140932025
pfn 1801dc    ---DA--UWEV  pfn 1801dd    ---DA--UWEV  pfn 17fbde    ---DA--UWEV  pfn 140932    ----A--UREV

LARGE PAGE という出力がなく、PTE まで 4 階層全て存在することが分かります。現在実行中のコードは PFN 140932 のページに存在しているようです。

プログラム内で VirtualAlloc を呼ぶとき、1GB では PAGE_READWRITE、2MB では PAGE_READONLY の属性を渡したので、その属性が PPE の W や PDE の R といった出力に反映されています。命令ポインターのアドレスは実行可能かつ書き込み不可なので、R と E のラベルが出力されていることも確認できます。その他のラベルの意味は、上記 Microsoft Docs の !pte のページに説明があります。

!pte コマンドの欠点は、DirectoryTableBase を自分で指定できないことです。つまり、現在のプロセス以外のプロセスの仮想アドレスに対してコマンドを実行することができません。そのため、ローカルカーネルデバッグのときに使えません。だめじゃん。

!pte 以外に、仮想アドレスから物理アドレスへの変換を行ってくれる !vtop というコマンドがあります。下記ヘルプにあるように、第一引数に 0 を指定すると !pte と同じように現在のプロセスの DirBase が使われます。試してみましょう。

vtop - Windows drivers | Microsoft Docs
https://docs.microsoft.com/en-us/windows-hardware/drivers/debugger/-vtop

1: kd> !vtop 0 0x00000176`80000000
Amd64VtoP: Virt 0000000000000176, pagedir 00000001800d0000
Amd64VtoP: PML4E 00000001800d0000
Amd64VtoP: PDPE 00000001801e4000
Amd64VtoP: zero PDPE
Virtual address 176 translation fails, error 0xD0000147.

1: kd> !vtop 0 0x00000176`51600000
Amd64VtoP: Virt 0000000000000176, pagedir 00000001800d0000
Amd64VtoP: PML4E 00000001800d0000
Amd64VtoP: PDPE 00000001801e4000
Amd64VtoP: zero PDPE
Virtual address 176 translation fails, error 0xD0000147.

1: kd> !vtop 0 @rip
usage: vtop PFNOfPDE VA

1: kd> !vtop 0 00007ff63b168234
Amd64VtoP: Virt 00007ff63b168234, pagedir 00000001800d0000
Amd64VtoP: PML4E 00000001800d07f8
Amd64VtoP: PDPE 00000001801dcec0
Amd64VtoP: PDE 00000001801ddec0
Amd64VtoP: PTE 000000017fbdeb40
Amd64VtoP: Mapped phys 0000000140932234
Virtual address 7ff63b168234 translates to physical address 140932234.

rip レジスターの値については !pte と同じ結果が得られました。が、レジスターのシンボルをそのまま渡すことはできないみたいです。さらにはラージページに対応していないようです。だめじゃん。

!vtop のヘルプには、第一引数に 0 の代わりに DirBase の PFN を渡せると書かれていますが、実際には DirBase そのものを渡して、現在のプロセス以外のページテーブルを使ってアドレス変換をすることはできます。

1: kd> r cr3
cr3=00000001800d0000

1: kd> !vtop 1800d0000 00007ff63b168234
Amd64VtoP: Virt 00007ff63b168234, pagedir 00000001800d0000
Amd64VtoP: PML4E 00000001800d07f8
Amd64VtoP: PDPE 00000001801dcec0
Amd64VtoP: PDE 00000001801ddec0
Amd64VtoP: PTE 000000017fbdeb40
Amd64VtoP: Mapped phys 0000000140932234
Virtual address 7ff63b168234 translates to physical address 140932234.

なんだか !pte と !ptov どちらのコマンドも微妙です。どちらも 32-bit 時代のまま取り残されていて、ろくに更新されていない雰囲気がありますね。

微妙ではありましたが、物理アドレスを取得することはできました。カーネルデバッガーには、物理アドレスの値を直接出力できるコマンドがあるので、取得できたアドレスが正しいかどうか見てみましょう。PFN は物理アドレスそのものではないので、ページサイズの bit 数だけ左にシフトしてから仮想アドレスのオフセット部分をそこに加算する必要があります。といっても 4K ページの場合 16 進表記の末尾 3 文字を付加するだけなので簡単です。

1: kd> dd 0x00000176`80000000 l4
00000176`80000000  deadbeef 00000000 00000000 00000000
1: kd> !dd 100000000 l4
#100000000 deadbeef 00000000 00000000 00000000

1: kd> db @rip l10
00007ff6`3b168234  cc 48 8d 4c 24 28 e8 ab-b7 ff ff 90 48 8d 4c 24  .H.L$(......H.L$
1: kd> !db 140932234 l10
#140932234 cc 48 8d 4c 24 28 e8 ab-b7 ff ff 90 48 8d 4c 24 .H.L$(......H.L$

deadbeef という hexspeak は、t.exe が VirtualAlloc の直後に書き込んでいる値です。どちらの場合も内容が同じなので、アドレス変換が正しく行われていることが確認できます。

以上で、CPU 側の PML4 ページングの動作の説明は終わりです。CPU 側には、Meltdown/Spectre で話題になったキャッシュなど、複雑な動作がまだまだありますが、ページングの計算という意味では以上です。

ページングテーブルについて

ここから Windows の話になります。

前章の !pte コマンドの出力で触れなかった部分があります。4KB ページの結果が得られた出力を再掲します。

1: kd> !pte @rip
                                           VA 00007ff63b168234
PXE at FFFFA4D2693497F8    PPE at FFFFA4D2692FFEC0    PDE at FFFFA4D25FFD8EC0    PTE at FFFFA4BFFB1D8B40
contains 0A000001801DC867  contains 0A000001801DD867  contains 0A0000017FBDE867  contains 0000000140932025
pfn 1801dc    ---DA--UWEV  pfn 1801dd    ---DA--UWEV  pfn 17fbde    ---DA--UWEV  pfn 140932    ----A--UREV

出力 2 行目にある FFFFA4D2693497F8 といったアドレスは仮想アドレスです。それぞれのアドレスの中身を参照すると、

1: kd> dq FFFFA4D2693497F8 l1
ffffa4d2`693497f8  0a000001`801dc867
1: kd> dq FFFFA4D2692FFEC0 l1
ffffa4d2`692ffec0  0a000001`801dd867
1: kd> dq FFFFA4D25FFD8EC0 l1
ffffa4d2`5ffd8ec0  0a000001`7fbde867
1: kd> dq FFFFA4BFFB1D8B40 l1
ffffa4bf`fb1d8b40  00000001`40932025

!pte の出力の三行目にある "contains" に表示されているテーブルエントリーの値が得られました。つまり 2 行目のアドレスは、各ページテーブルエントリの仮想アドレスです。

この情報は、前章に記載した CPU によるページング動作だけを考えると不思議です。CPU は、CR3 レジスターに保存された物理アドレスを使って最初の階層のテーブルの特定し、さらに各テーブルのエントリに保存された物理アドレスを使って次の階層のテーブル、もしくはページを特定していました。そもそも仮想アドレスを物理アドレスに変換する作業なので、その過程で仮想アドレスを扱うステップは存在しません。では、!pte はどうやって仮想メモリ上のテーブルの位置を取得したのでしょうか。

ナイーブな発想としては、DirectoryTableBase から現在のページングテーブルを全探索する方法があります。が、32-bit ページングならまだしも、64-bit だと探索空間が広すぎて全く現実的ではありません。一応カーネルデバッガーには、渡した DirBase に対応する物理アドレスと仮想アドレスのすべてのマッピングを列挙する !ptov という男気溢れるコマンドがあります。明らかに 32-bit 時代の名残です。

ptov - Windows drivers | Microsoft Docs
https://docs.microsoft.com/en-us/windows-hardware/drivers/debugger/-ptov

!pte が全探索をせずに、何らかの計算によって仮想アドレスを得ているのは明らかです。その方法を探るために、!pte コマンドをデバッグしてみました。kdexts!pte から始めて適当にステップ実行すると、kdexts!DbgGetPteAddress という関数が入力した仮想アドレスを第一引数に取り、その戻り値が !pte の出力結果にある各テーブルエントリの仮想アドレスになっていることが分かりました。例えば下記の例では、命令ポインターのアドレスである 00007ff63b168234 が渡されて PTE の仮想アドレスである ffffa4bffb1d8b40 が返ってきています。

Breakpoint 1 hit
rax=00007ff63b168234 rbx=0000000000000000 rcx=00007ff63b168234
rdx=0000000000000013 rsi=0000000000000004 rdi=000000dba427c430
rip=00007ffbf3c6e050 rsp=000000dba427c388 rbp=000000dba427c439
 r8=0000000000000064  r9=0000000000000000 r10=000001ff8d365bb0
r11=0000000000000100 r12=000000dba427cd50 r13=00007ff63b168234
r14=0000000000000004 r15=0000000000000000
iopl=0         nv up ei pl nz na pe nc
cs=0033  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00000202
kdexts!DbgGetPteAddress:
00007ffb`f3c6e050 4053            push    rbx
0:000> knL6
 # Child-SP          RetAddr           Call Site
00 000000db`a427c388 00007ffb`f3c6f362 kdexts!DbgGetPteAddress
01 000000db`a427c390 00007ffb`f3c6fb89 kdexts!DumpPte+0x166
02 000000db`a427c4a0 00007ffb`fd34f463 kdexts!pte+0xe9
03 000000db`a427c4f0 00007ffb`fd34f631 dbgeng!ExtensionInfo::CallA+0x2af
04 000000db`a427c5c0 00007ffb`fd34f8a7 dbgeng!ExtensionInfo::Call+0x121
05 000000db`a427c7c0 00007ffb`fd34d411 dbgeng!ExtensionInfo::CallAny+0x113
0:000> gu
rax=ffffa4bffb1d8b40 rbx=0000000000000000 rcx=0000000000000030
rdx=0000003ffb1d8b41 rsi=0000000000000004 rdi=000000dba427c430
rip=00007ffbf3c6f362 rsp=000000dba427c390 rbp=000000dba427c439
 r8=0000000000000064  r9=0000000000000000 r10=000001ff8d365bb0
r11=0000000000000100 r12=000000dba427cd50 r13=00007ff63b168234
r14=0000000000000004 r15=0000000000000000
iopl=0         nv up ei pl nz na pe nc
cs=0033  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00000202
kdexts!DumpPte+0x166:
00007ffb`f3c6f362 488907          mov     qword ptr [rdi],rax ds:000000db`a427c430=ffffa4bffb1d8b40

この関数の主要な演算部分を抜粋すると以下の部分だけです。なかなか面白い計算をしています。本題とは全く関係ないですが、例えば edx を 1 にするために 30+9-38 を計算しているところにどことなく温かさを感じますね。

kdexts!DbgGetPteAddress+0x53:
00007ffb`f3c6e0a3 e8d0d9ffff      call    kdexts!DbgGetPageTableInfo (00007ffb`f3c6ba78)
00007ffb`f3c6e0a8 833d99381f0005  cmp     dword ptr [kdexts!PagingLevels (00007ffb`f3e61948)],5
00007ffb`f3c6e0af b830000000      mov     eax,30h
00007ffb`f3c6e0b4 8d4809          lea     ecx,[rax+9]
00007ffb`f3c6e0b7 0f44c1          cmove   eax,ecx
00007ffb`f3c6e0ba 8d51c8          lea     edx,[rcx-38h]
00007ffb`f3c6e0bd 8ac8            mov     cl,al
00007ffb`f3c6e0bf 48c1eb09        shr     rbx,9 <<<< rbx = VirtualAddress
00007ffb`f3c6e0c3 48d3e2          shl     rdx,cl
00007ffb`f3c6e0c6 48b8f8ffffffffff7f00 mov rax,7FFFFFFFFFFFF8h
00007ffb`f3c6e0d0 48ffca          dec     rdx
00007ffb`f3c6e0d3 48c1ea09        shr     rdx,9
00007ffb`f3c6e0d7 4823d3          and     rdx,rbx
00007ffb`f3c6e0da 4823c2          and     rax,rdx
00007ffb`f3c6e0dd 480305bc1b2200  add     rax,qword ptr [kdexts!DbgPteBase (00007ffb`f3e8fca0)]
00007ffb`f3c6e0e4 eb0e            jmp     kdexts!DbgGetPteAddress+0xa4 (00007ffb`f3c6e0f4)

00007ffb`f3c6e0f4 4883c420        add     rsp,20h
00007ffb`f3c6e0f8 5b              pop     rbx
00007ffb`f3c6e0f9 c3              ret

0:003> dd kdexts!PagingLevels l1
00007ffb`f3e61948  00000004

0:003> dq kdexts!DbgPteBase l1
00007ffb`f3e8fca0  ffffa480`00000000

抜粋する前の処理で rbx に引数の仮想アドレスが入っています。素直に計算式にするとこんな感じでしょうか。

(((rbx >> 9) & (((1 << 0x30) - 1) >> 9)) & 0x7FFFFFFFFFFFF8) + ptr [kdexts!DbgPteBase]

ptr [kdexts!PagingLevels] の値は 4 になっています。名前からしてページングの階層で、PML4 を使うので 4 になっています。仮にここが 5 だと、00007ffb`f3c6e0b7 にある CMOVE によって、上記式中の 0x30 が 0x39 になります。!pte はろくにラージページの結果も出力できないくせに、ちょっぴり PML5 に対応しているところが憎いですね。しかもそのせいなのか、(1 << 0x30) して 1 引いてから右シフトするという二度手間が発生している。

PML4 の場合、この計算を人間に分かりやすいように書くとこうなります。

ptr[kdexts!DbgPteBase] + ((rbx >> 0n12) & 0xf`ffffffff) * 8

要は仮想アドレスの 47:12 ビット部分を抜き出して、それに 8 をかけてから DbgPteBase を足しているだけです。前章で書いた通り PML4 における仮想アドレスの有効ビットは 47:0 であるため、、抜き出す 47:12 は、仮想アドレスからページテーブルのオフセットだけを除いた部分になります。いわば仮想アドレス空間におけるページの通し番号、すなわち PFN で、そのような値を Windows では VPN (= Virtual Page Numer) と呼んでいます。

残る ptr[kdexts!DbgPteBase] の ffffa480`00000000 というアドレスは、PteBase という名前から推測できます。正式な名称が何になるかは不明ですが、Windows カーネルでは、ページングで使われるテーブルは全てカーネルアドレス空間の決められた範囲内に収められており、今回のシステムではその先頭が ffffa480`00000000 になっていることを意味しています。

PteBase は、カーネルデバッガーで !address コマンドを実行し、"PageTables" という種類 (VaType) のアドレス範囲として表示されるはずです。以下が !address コマンドの出力結果抜粋です。"PageTables" の開始アドレスが ffffa480`00000000 になっています。

      BaseAddress      EndAddress+1        RegionSize         VaType            Usage
---------------------------------------------------------------------------------------------------
..snip..
ffff9209`0c600000 ffffa480`00000000     1276`f3a00000 SystemRange                         
ffffa480`00000000 ffffa500`00000000       80`00000000 PageTables                          
ffffa500`00000000 ffffa580`00000000       80`00000000 Hyperspace                          
ffffa580`00000000 ffffbf00`00000000     1980`00000000 SystemRange                         
ffffbf00`00000000 ffffbf00`06200000        0`06200000 PFNDatabase                         
..snip..

この空間は、手元にある日本語の「インサイド Microsoft Windwos 第 4 版」では（いい加減新しいの買え・・）、「512GB 4 レベルページテーブルマップ」と書かれています。レジェンド Alex Ionescu 氏のブログと CodeMachine のページでは共に "PTE Space" になっています。

How Control Flow Guard Drastically Caused Windows 8.1 Address Space and Behavior Changes – Alex Ionescu’s Blog
https://alex-ionescu.com/?p=246

CodeMachine - Article - X64 Kernel Virtual Address Space
https://www.codemachine.com/article_x64kvas.html

さて、私の持っているインサイド Windows、及び上記 2 つのページいずれにおいても、PTE Space はFFFFF680`00000000 で開始されるように書かれています。しかし、今回デバッグした環境では ffffa480`00000000 になっていて値が異なります。これは KASLR によるもので、以下のブログ記事に対するAlex Ionescu 氏のコメントによると、Windows 10 の Anniversary Update (= RS1, version 1607) から導入されたようです。

Exploring Windows virtual memory management
https://www.triplefault.io/2017/08/exploring-windows-virtual-memory.html?showComment=1502684413314#c9078390501144322755

FWIW, the table on my blog contains a much more accurate and up to date kernel address space as ofWindows 8.1 and Windows 10 pre-Anniversary Update prior to KASLR.

この PteBase の値は、nt!MmPteBase というシンボルを経由して取得することができます。

1: kd> dq nt!MmPteBase l1
fffff802`56afb358  ffffa480`00000000

話を !pte の計算式に戻します。今までの考察をまとめると、PteBase + VPN * 8 という式で、その仮想アドレスを指し示しているテーブルエントリの仮想アドレスが算出できることが分かりました。この仕組みは、単純に PTE Space の先頭 8 バイトを VPN 0 のページに対応させ、その次の 8 バイトが VPN 1 のページに対応させ、というように PTE と VPN を順番にマッピングさせることで実現できます。PML4 でページング可能な仮想アドレスが 48-bit なので、そこから 1 ページ分の 12-bit を引いた 2^36 がVPN の総数になります。PTE のサイズが 8 バイトなので、2^36 * 8 = 2^39 = 512GB となってこれが PTE Space のサイズに一致します。このことを簡単に図示しました。

PTE 以外の PDE や PDPTE、PML4E も PTE Space に含まれています。PTE Space の PTE は、上の図の通り canonical な全ての仮想アドレスをマップ先としてカバーしています。したがって、マップ先が PTE Space の範囲内になる PTE も PTE Space に含まれていることになり、それが PDE です。同様に、PDE をマップ先にしている PTE が PDPTE、PDPTE をマップ先にしている PTE が PML4E です。そして最後に、PML4 Table を保持するページをマップ先にしている PTE が PTE Space 内に (しかも PML4 Table 内に) ただ一つ存在しています。

このような構造を可能にするための条件は、PTE Base のアドレスが 512GB 境界に乗る、つまり 38:0 の 39 ビットが全て 0 であることです。その理由について説明します。

計算を分かりやすくするため、48-bit の仮想アドレスを 9+9+9+9+12 bit ずつの5 つのチャンクに分け、それぞれ A、B、C、D、E とおきます。例を示します。

ffffa48000000000: (A,B,C,D,E) = (329, 0, 0, 0, 0)
00007ff63b168234: (A,B,C,D,E) = (255, 472, 472, 360, 564)

ここで、例の PteBase + VPN * 8 という計算を f(x) という関数として考えて、ABCDE の形をした数に何回か適用してみましょう。それが以下の図です。PTE Base のように 512GB 境界に乗っているアドレスは、常に B=C=D=E=0 となります。ABCDE とアルファベットが被らないように X0000 とおきました。

関数 f を適用するごとに左側から X で置き換えられていき、最終的には全て X になって必ず一つの値に収束することが分かります。

KASLR があるため、X の値はシステムが起動するときに決定されます。PTE Base はカーネル領域にあるので、アドレスが canonical であるためには X の最上位ビットは 1 でなければならないので、X は 0x100 から 0x1ff までの 256 通りに限定されます。今回デバッグしている PTE Base = ffffa48000000000 は X=329 のパターンです。

プロセスが作られた時など、PML4 Table を新たに作成した場合、その物理アドレスを CR3 にセットするのは当然ですが、それに加えて PML4 Table のインデックス X のエントリにも自己参照を行う PML4 Table の物理アドレスをセットしておきます。この些細な作業を行うだけで、その後のプロセス内で使われる全てのテーブルに PTE Space 内の仮想アドレスが正しく割り当てられます。ビット演算に強い人には自明かもしれませんが、私にはこの原理が直感的に理解できなかったので、具体例を使ってもう少し考えてみました。

今までの記述をそのまま引き継いで、今、PML4 Table 分の 4KB を物理メモリ上に確保してきて、インデックス X=329 の位置の PML4E にその物理アドレスをセットしたとします。

さらに時間が過ぎて、例えばプロセスが 1GB のラージページを要求してきたとします。このとき必要な作業は、1GB 分の連続した領域を物理メモリ上に見つけるだけでなく、その領域をマップ可能な空きアドレスをプロセスの仮想空間上に見つける必要があります。

前の章で確保された 1GB のバッファーは 0x00000176`80000000 というアドレスでした。この場合、PML4E のインデックスは 2 です。このアドレスを空きアドレスとして使うことに決めたとき、もし PML4 Table のインデックス 2 のエントリが無効だった場合は、まず PDP Table 分を作るための 4KB を物理メモリから確保してきて、その物理アドレスを PML4 Table のインデックス 2 のエントリにセットします。

PDP Table が決定し、さらに要求された通りに 1GB ページが確保できた場合、PDPTE が直接その 1GB 領域を指し示せばいいので、0x00000176`80000000 というアドレスに対応するインデックス 474 の PDPTE に、1GB バッファーの物理アドレスをセットしたら完了です。特別なことは何もしていないようですが、これだけの作業で先ほどの PTE Space の動きは実現されます。

PML4T と PDPT の仮想アドレスの位置は、上述の図を使って計算できます。今回の場合は PTE Base から X=329、仮想アドレス 0x00000176`80000000 から A=2 なので

PML4T = PTEBase + 329 * (1 << 30) + 329 * (1 << 21) + 329 * (1 << 12) = 0xffffa4d2`69349000
PDPT = PTEBase + 329 * (1 << 30) + 329 * (1 << 21) + 2 * (1 << 12) = 0xffffa4d2`69202000

仮に PML4T が 0x1000、PDPT が 0x2000、1GM Page が 0x1`00000000 という物理アドレスに作られたとして、現在のページテーブルは以下の図のようになっています。この状態で、今算出した 2 つの仮想アドレスをページング変換するとどうなるでしょうか。

PML4T の 0xffffa4d2`69349000 の場合は簡単です。このアドレスは、4 階層のテーブルのインデックスが全て 329 になるので、

CR3 -> PML4T @ 0x1000
PDPT: PML4T[329] -> PFN:1 @ 0x1000 (PML4T)
PDT: PML4T[329] -> PFN:1 @ 0x1000 (PML4T)
PT: PML4T[329] -> PFN:1 @ 0x1000 (PML4T)
Page: PML4T[329] -> PFN:1 @ 0x1000 (PML4T)

PML4T のテーブルが全ての階層のテーブルとして参照され、最終的に解決されるページも PML4T の物理アドレス 0x1000 になり、仮想アドレス 0xffffa4d2`69349000 が正しく PML4T を参照できることが分かりました。

次の 0xffffa4d2`69202000 の場合もほぼ同様です。

CR3 -> PML4T @ 0x1000
PDPT: PML4T[329] -> PFN:1 @ 0x1000 (PML4T)
PDT: PML4T[329] -> PFN:1 @ 0x1000 (PML4T)
PT: PML4T[329] -> PFN:1 @ 0x1000 (PML4T)
Page: PML4T[2] -> PFN:2 @ 0x2000 (PDPT)

今度は 20:12 のチャンク (前の説明で言う D) が 2 なので、PT として PML4T を参照したときにインデックス 2 の位置にある PML4E を見ることになり、これは PDPT を指しています。したがって仮想アドレス 0xffffa4d2`69202000 が正しく PDPT を参照できることが分かりました。

まとめます。PTEBase を 512GB 境界のアドレスに設定し、PML4 Table に自己参照するエントリを一つだけ用意しておくと、PTE の仮想アドレスを変換するときに階層が綺麗にずれて、得られる物理アドレスがページではなくページテーブルのものになります。これによって、ある仮想アドレスをページング変換するときに使われる各ページングテーブルの仮想アドレスが、全探索しなくても簡単な計算で求められます。知っている人には何てことない動作なのかもしれませんが、緻密に設計されている印象です。

おまけ: デバッガーエクステンションを書いたので宣伝

既に触れたように、!pte は DirBase を指定できなかったり、!vtop はラージページを正しく扱えなかったりなど不便なところが多いので、!pte と !vtop を兼ねたデバッガーコマンド !v2p を追加しました。

msmania/bangon: Extensions for Windows debugger
https://github.com/msmania/bangon/
（このエクステンションはかなりスパゲッティー化してきたのであまりコードは見て欲しくないような。。。）

以下の出力例では、ローカルカーネルデバッガーのセッションで t.exe とカーネルプロセスのそれぞれの DirBase を使って !v2p を実行した結果です。このシステムでは PTE Base の X は 391 でした。ffffc3e1`f0e02e10 という PTE Space 内のアドレスはカーネル空間にありますが、プロセスによってマップされる物理アドレスが異なる様子が確認できます。そもそもカーネルプロセスでは ffffc3e1`f0e02e10 のアドレスにはまだ物理ページがマップされていません。

lkd> !process 0 0 t.exe
PROCESS ffffad8f2ae73080
    SessionId: 1  Cid: 2430    Peb: 55f3cf0000  ParentCid: 21c8
FreezeCount 2
    DirBase: 0ca43000  ObjectTable: ffffc503b5641d00  HandleCount:  52.
    Image: t.exe

lkd> !v2p 0000017080000000 0ca43000
Virtual address = 00000170`80000000
PagingMode: 4-level
DirBase:    0ca43000 ffffc3e1`f0f87c38
PML4 Table          @2   ffffc3e1`f0f87010 = 0a000002`14d5b867 W U A
PageDirPointerTable @450 ffffc3e1`f0e02e10 = 8a000004`000008e7 (1GB Page) XD W U A
PageDirTable             ffffc3e1`c05c2000   (1GB Page)
PageTable                ffffc380`b8400000   (1GB Page)
Physical Address = 00000004`00000000

lkd> !v2p ffffc3e1`f0e02e10 0ca43000
Virtual address = ffffc3e1`f0e02e10
PagingMode: 4-level
DirBase:    0ca43000 ffffc3e1`f0f87c38
PML4 Table          @391 ffffc3e1`f0f87c38 = 0a000000`0ca43863 W S A
PageDirPointerTable @391 ffffc3e1`f0f87c38 = 0a000000`0ca43863 W S A
PageDirTable        @391 ffffc3e1`f0f87c38 = 0a000000`0ca43863 W S A
PageTable           @2   ffffc3e1`f0f87010 = 0a000002`14d5b867 W U A
Physical Address = 00000002`14d5be10

lkd> !process 4 0
Searching for Process with Cid == 4
PROCESS ffffad8f1ae82040
    SessionId: none  Cid: 0004    Peb: 00000000  ParentCid: 0000
    DirBase: 001ad000  ObjectTable: ffffc50387c04ac0  HandleCount: 7109.
    Image: System

lkd> !v2p ffffc3e1`f0e02e10 001ad000
Virtual address = ffffc3e1`f0e02e10
PagingMode: 4-level
DirBase:    001ad000 ffffc3e1`f0f87c38
PML4 Table          @391 ffffc3e1`f0f87c38 = 80000000`001ad063 XD W S A
PageDirPointerTable @391 ffffc3e1`f0f87c38 = 80000000`001ad063 XD W S A
PageDirTable        @391 ffffc3e1`f0f87c38 = 80000000`001ad063 XD W S A
PageTable           @2   ffffc3e1`f0f87010 = 00000000 (inactive)

1GB ページでは、その原理上 PTE と PDE は存在しません。しかし物理アドレスが存在する以上、PTE と PDE に対応する PTE Space 内の仮想アドレスは算出できます。それが上記出力における ffffc3e1`c05c2000 とffffc380`b8400000 です。存在しないテーブルの代わりに、これらのアドレスには 1GB ページの物理アドレスがマップされています。

それぞれのアドレスを !v2p で確認した結果が以下の通りです。結果としてこのプロセスでは、1GB ラージページは 00000170`80000000、ffffc3e1`c05c2000、ffffc380`b8400000 という 3 つの仮想アドレスを持つことになります。

lkd> !v2p ffffc3e1`c05c2000 0ca43000
Virtual address = ffffc3e1`c05c2000
PagingMode: 4-level
DirBase:    0ca43000 ffffc3e1`f0f87c38
PML4 Table          @391 ffffc3e1`f0f87c38 = 0a000000`0ca43863 W S A
PageDirPointerTable @391 ffffc3e1`f0f87c38 = 0a000000`0ca43863 W S A
PageDirTable        @2   ffffc3e1`f0f87010 = 0a000002`14d5b867 W U A
PageTable           @450 ffffc3e1`f0e02e10 = 8a000004`000008e7 XD W U A
Physical Address = 00000004`00000000

lkd> !v2p ffffc380`b8400000 0ca43000
Virtual address = ffffc380`b8400000
PagingMode: 4-level
DirBase:    0ca43000 ffffc3e1`f0f87c38
PML4 Table          @391 ffffc3e1`f0f87c38 = 0a000000`0ca43863 W S A
PageDirPointerTable @2   ffffc3e1`f0f87010 = 0a000002`14d5b867 W U A
PageDirTable        @450 ffffc3e1`f0e02e10 = 8a000004`000008e7 (2MB Page) XD W U A
PageTable                ffffc3e1`c05c2000   (2MB Page)
Physical Address = 00000004`00000000

おわりに

PML4 ページングと、Windows が管理する PTE Space の仕組みについて説明しました。冒頭に書いた通り、この内容は 12/24 の記事に向けての準備の一環なのですが、いつも通り長くなってしまってこの記事だけではまだ書き切れていません。~~というわけで 12/24 の前にもう一つ投稿する予定です。その名は PFN データベースとソフト PTE。果たして 12/24 に間に合うのか。~~

第二部書きました。

共有メモリのページング - Qiita
https://qiita.com/msmania/items/5d546f2619e937a0aa18