Pagingの気持ちをWindows上で体験してみる

これはrogy advent calender 2017のクリスマス・イブの記事です. 遅くなって申し訳ありません.

これは何?

x86/64アーキテクチャのPagingについて簡単に解説した後,Windowsで実際に動いている簡単な例を見てみます.

概念

仮想メモリと物理メモリ

多くのOSでは,コンピュータに積まれた主記憶装置を一度仮想化します. つまり,仮想メモリ上の 0x1000番地と物理メモリ上の0x1000番地は必ずしも同じ場所を指すわけではないというお話ですね.これは結果として,OS上のあるプロセスAが他のプロセスBのメモリ領域に書き込みが出来なかったり,スワッピングに繋がったりする訳です. またその仮想化の手段として,これから説明するPagingやSegmentationが存在するわけです.

Paging

概要

物理メモリを4KBごとに細かく分け,それぞれを「ページ」と呼びます.(ちなみに,2MBや1GBごとに区切ることもできますが,今回はおいておきます.)そして,メモリ上に変換テーブルを用意しておきます.CPUのMMU(Memory Management Unit)はその変換テーブルを参照しながら,仮想のアドレスをハードウェア上で物理メモリのアドレスに変換して読み書きを行います.

メモリの変換テーブル

変換テーブルは通常のx86の場合2段階,x64の場合は4段階になっています.これは,省メモリの観点で妥当な話で,多段階のページングでなければ(全体のメモリ使用量)/4KBのエントリ数を持つ変換テーブルを用意しなくてはならず,実際に使われない箇所がたくさんでてきますね. ただ,実際多段階といってもよくわからないと思うので,早速実際の例を見ていきます.簡単のため,PAEが有効でないx86に関して記述します.

PDEとPTE

CPUの特殊なレジスタ(cr3)には,PDE(Page Directory Entry)の物理アドレスが代入されています.まずはじめに,仮想アドレスにアクセスする際,その上位10bitに対応するPDEのエントリを読み出します.その値がValidである場合,そこにはPTEの物理アドレスポインタが格納されており,それを次の10bit分のインデックスで読み出すと対応するPTEが得られます.その値が仮想メモリに対応する物理メモリのアドレスになっています.文章で書いても伝わりませんね. f:id:mumumu_bin:20171226224848p:plain

Intelが出しているSoftware Developpers Manualを読みましょう.システムプログラミングについては3巻にまとまっています.上の画像も,その一部の引用です.

PTE,PDEのエントリの先頭にはPresent bitと呼ばれるフィールドがあり,それがクリアされているとそのエントリは無効なものとして扱われます.PDEが無効のとき,対応するPTEを用意してやる必要性はありません.したがってその分のメモリ使用を抑えることができるようになります.

また,アクセスした仮想アドレスに対応するPTEが発見できなかったときにはPage Faultが発生し,適切なルーチンが割り込み実行されます.これをPageFault Handlerと呼ぶことが多いです.

Windows上でみてみる

準備

  • ホストWindows上でWinDBGを立ち上げます.VirtualBox上でゲストのWindowsを実行し,それにアタッチします. 参考

  • 次に,ゲストOSが解析したいコンテキストになるよう調節します.今回は,ゲストOS上で計算機 calc.exeを実行し,そのメモリコンテキストを確認していきましょう.

    • !processコマンドを用いてcalc.exeがどこにあるか特定し,.processコマンドでそのコンテキストに移りOSを停止させます.
kd> !process 0 0 calc.exe
PROCESS 849a9b20  SessionId: 1  Cid: 0ccc    Peb: 7ffd5000  ParentCid: 067c
    DirBase: 7f926420  ObjectTable: 9e11dbd0  HandleCount:  74.
    Image: calc.exe

kd> .process /i /p 849a9b20 
You need to continue execution (press 'g' <enter>) for the context
to be switched. When the debugger breaks in again, you will be in
the new process context.
kd> g
Break instruction exception - code 80000003 (first chance)
nt!RtlpBreakWithStatusInstruction:
828879d8 cc              int     3

現在のメモリの確認

Windows on x86 でのメモリマップについて

内部ではこんな感じで使われているようです.大事なことは, 0x0~0x7fffffffまでがUserlandであることと,それ以降はシステムが使っていることだけです.

              +------------------------------------+
        00000000 |                                    |
                 |                                    |
                 |                                    |
                 | User Mode Addresses                |
                 |                                    |
                 |   All pages within this range      |
                 |   are potentially accessible while |
                 |   the CPU is in USER mode.         |
                 |                                    |
                 |                                    |
                 +------------------------------------+
        7ffff000 | 64k No Access Area                 |
                 +------------------------------------+
        80000000 |                                    |
                 | NTLDR loads the kernel, HAL and    |
                 | boot drivers here.  The kernel     |
                 | then relocates the drivers to the  |
                 | system PTE area.                   |
                 |                                    |
                 | Kernel mode access only.           |
                 |                                    |
                 | When possible, the PFN database &  |
                 | initial non paged pool is built    |
                 | here using large page mappings.    |
                 |                                    |
                 +------------------------------------+
                 |                                    |
                 | Additional system PTEs, system     |
                 | cache or special pooling           |
                 |                                    |
                 +------------------------------------+
                 |                                    |
                 | System mapped views.               |
                 |                                    |
                 +------------------------------------+
                 |                                    |
                 | Session space.                     |
                 |                                    |
                 +------------------------------------+
        C0000000 | Page Table Pages mapped through    |
                 |          this 4mb region           |
                 |   Kernel mode access only.         |
                 |                                    |
                 +------------------------------------+
        C0400000 | HyperSpace - working set lists     |
                 |  and per process memory management |
                 |  structures mapped in this 8mb     |
                 |  region.                           |
                 |  Kernel mode access only.          |
                 +------------------------------------+
        C0C00000 | System Cache Structures            |
                 |   reside in this 4mb region        |
                 |   Kernel mode access only.         |
                 +------------------------------------+
        C1000000 | System cache resides here.         |
                 |   Kernel mode access only.         |
                 |                                    |
                 |                                    |
                 +------------------------------------+
        E1000000 | Start of paged system area         |
                 |   Kernel mode access only.         |
                 |                                    |
                 |                                    |
                 +------------------------------------+
                 |                                    |
                 | System PTE area - for mapping      |
                 |   kernel thread stacks and MDLs    |
                 |   that require system VAs.         |
                 |   Kernel mode access only.         |
                 |                                    |
                 +------------------------------------+
                 |                                    |
                 | NonPaged System area               |
                 |   Kernel mode access only.         |
                 |                                    |
                 +------------------------------------+
        FFBE0000 | Crash Dump Driver area             |
                 |   Kernel mode access only.         |
                 +------------------------------------+
        FFC00000 | Last 4mb reserved for HAL usage    |
                 +------------------------------------+

メモリマップの取得

!address で確認してみましょう.

kd> !address


BaseAddr EndAddr+1 RgnSize         VaType            Usage
------------------------------------------------------------------------
       0    10000    10000 UserRange                           
   10000    20000    10000 UserRange              VAD          849d4220 ReadWrite                0 Section
   20000    21000     1000 UserRange              VAD          85aa2b28 ReadWrite                1 NoChange Private 
   21000    30000     f000 UserRange                           
   30000    34000     4000 UserRange              VAD          85614be0 ReadOnly                 0 NoChange Section
   34000    40000     c000 UserRange                           
   40000    42000     2000 UserRange              VAD          85614b98 ReadOnly                 0 NoChange Section
   42000    50000     e000 UserRange                           
   50000    51000     1000 UserRange              VAD          85a597f8 ReadWrite                1 Private 
   51000    60000     f000 UserRange                           
   60000    c7000    67000 UserRange              VAD          85aac180 ReadOnly                 0 NoChange Section [\Windows\System32\locale.nls]
   c7000    d0000     9000 UserRange                           
   d0000   101000    31000 UserRange              VAD          85ace150 WriteCopy                31 Section [\Windows\System32\en-US\calc.exe.mui]
  101000   110000     f000 UserRange                           
  110000   111000     1000 UserRange              VAD          8553e828 ReadWrite                1 NoChange Private 
  111000   120000     f000 UserRange                           
  120000   12a000     a000 UserRange              VAD          859e34d0 ReadWrite                a NoChange Private 
  12a000   130000     6000 UserRange                           
  130000   132000     2000 UserRange              VAD          854ed0e8 ReadOnly                 0 NoChange Section
  132000   140000     e000 UserRange                           
  140000   150000    10000 UserRange              VAD          854962b0 ReadWrite                0 Section
  150000   160000    10000 UserRange              VAD          84e429d0 ReadWrite                0 Section
  160000   170000    10000 UserRange              VAD          84e42988 ReadWrite                0 Section
  170000   17a000     a000 UserRange              VAD          85afd2e0 ReadWrite                a NoChange Private 
  17a000   180000     6000 UserRange                           
  180000   1c0000    40000 UserRange              VAD          85aa7e00 ReadWrite                7 Private 
  1c0000   1d3000    13000 UserRange              VAD          8568b268 ReadWrite                13 NoChange Private 
  1d3000   1e0000     d000 UserRange                           
  1e0000   1f3000    13000 UserRange              VAD          854cc148 ReadWrite                13 NoChange Private 
  1f3000   200000     d000 UserRange                           
  200000   21d000    1d000 UserRange              VAD          85953b28 ReadWrite                1d NoChange Private 
  
(snip)
  829000   830000     7000 UserRange                           
  830000   90f000    df000 UserRange              VAD          84e428f0 ReadOnly                 0 Section
  90f000   910000     1000 UserRange                           
  910000   9d0000    c0000 UserRange              VAD          85624fb8 ExecuteWriteCopy         6 Section [\Windows\System32\calc.exe]
  9d0000  15d0000   c00000 UserRange              VAD          85ace198 ReadOnly                 0 NoChange Section
 15d0000  16f5000   125000 UserRange              VAD          85624f68 ReadWrite                125 NoChange Private 
 16f5000  1700000     b000 UserRange                           
 (snip)
 2578000  2580000     8000 UserRange                           
 2580000  2588000     8000 UserRange              VAD          849d8388 ReadWrite                8 NoChange Private 
 2588000  2590000     8000 UserRange                           
 2590000  2598000     8000 UserRange              VAD          849d8338 ReadWrite                8 NoChange Private 
 2598000  25a0000     8000 UserRange                           
 25a0000  25a1000     1000 UserRange              VAD          849d82e8 ReadWrite                1 NoChange Private 
 25a1000  25b0000     f000 UserRange                           
 25b0000  25b8000     8000 UserRange              VAD          849d8298 ReadWrite                8 NoChange Private 
 25b8000  25c0000     8000 UserRange                           
 25c0000  25c8000     8000 UserRange              VAD          849d8248 ReadWrite                8 NoChange Private 
 25c8000  25d0000     8000 UserRange                           
 25d0000  25e0000    10000 UserRange              VAD          849d8db0 ReadWrite                10 NoChange Private 
 25e0000  25f0000    10000 UserRange              VAD          849d8b58 ReadWrite                10 NoChange Private 
 25f0000  25f8000     8000 UserRange              VAD          849d8900 ReadWrite                8 NoChange Private 
 25f8000  2600000     8000 UserRange                           
 2600000  2608000     8000 UserRange              VAD          849d88b0 ReadWrite                8 NoChange Private 
 2608000  2610000     8000 UserRange                           
 2610000  261a000     a000 UserRange              VAD          854969b0 ReadWrite                a NoChange Private 
 261a000  2620000     6000 UserRange                           
 2620000  2621000     1000 UserRange              VAD          849d16a8 ReadOnly                 0 Section
 2621000  2630000     f000 UserRange                           
 2630000  2631000     1000 UserRange              VAD          849d1618 ReadOnly                 0 Section
 2631000  2640000     f000 UserRange                           
 2640000  2641000     1000 UserRange              VAD          849d8d68 ReadOnly                 0 Section [\Windows\System32\oleaccrc.dll]
 2641000  2650000     f000 UserRange                           
 2650000  2651000     1000 UserRange              VAD          849d8490 ReadWrite                0 Section
 2651000  2660000     f000 UserRange                           
 2660000  2661000     1000 UserRange              VAD          849aa4d0 ReadWrite                1 NoChange Private 
 2661000  2670000     f000 UserRange                           
 2670000  2671000     1000 UserRange              VAD          849d6450 ReadWrite                1 NoChange Private 
 2671000  26d0000    5f000 UserRange                           
 26d0000  2710000    40000 UserRange              VAD          849c1ad8 ReadWrite                3 Private 
 2710000 6c310000 69c00000 UserRange                           
6c310000 6c34c000    3c000 UserRange              VAD          849d8400 ExecuteWriteCopy         3 Section [\Windows\System32\oleacc.dll]
6c34c000 6fb50000  3804000 UserRange                           
6fb50000 6fb82000    32000 UserRange              VAD          85ad07d0 ExecuteWriteCopy         4 Section [\Windows\System32\winmm.dll]
(snip)      
7f6f0000 7f7f0000   100000 UserRange              VAD          85aac1c8 ReadOnly                 0 NoChange Section
7f7f0000 7ffb0000   7c0000 UserRange                           
7ffb0000 7ffd3000    23000 UserRange              VAD          849d4db8 ReadOnly                 0 NoChange Section
7ffd3000 7ffd5000     2000 UserRange                           
7ffd5000 7ffd6000     1000 UserRange              PEB          Process: 849a9b20 [calc.exe]
7ffd6000 7ffdd000     7000 UserRange                           
7ffdd000 7ffde000     1000 UserRange              TEB          Thread: 849a9838
7ffde000 7ffdf000     1000 UserRange              TEB          Thread: 849d4af8
7ffdf000 7ffe0000     1000 UserRange              TEB          Thread: 85496d48
7ffe0000 7ffe1000     1000 SystemSharedPage                    
7ffe1000 7fff0000     f000 UserRange                           
7fff0000 80000000    10000 UserProbeArea                       
80000000 80400000   400000 BootLoaded                          
80400000 80784000   384000 SystemPTEs                          
80784000 80787000     3000 SystemPTEs             Stack        Thread: 848a4020; Process: 84841940
80787000 8078f000     8000 SystemPTEs                          

例えば,0x910000~0x9d0000-1あたりには,calc.exe本体の実行コード等がありそうですね. また,0x180000~0x1c0000-1の周辺がスタックのようです. 一方, 0x0~0x10000は使われていないようです.

ページングが行われていることを確認

!pteコマンドを使うことで,そのアドレスに対応するPTEやPDEが確認できます.そこで,スタックの底の値0x1bffffを渡してみます.

kd> !pte 0x1bffff
                    VA 001bffff
PDE at C0600000            PTE at C0000DF8
contains 0000000077407867  contains 8000000076B11867
pfn 77407     ---DA--UWEV  pfn 76b11     ---DA--UW-V

先頭bitのPresent Bitを含む幾つかのbitが立っていることがわかります.また,PFN 76b11ということで,物理アドレス0x76b11000から4KBの物理メモリが使われているのですね. 実際に見てみましょう.

kd> !dd 0x76b11000
#76b11000 001bf01c 00000000 76f2873d 001bf084
#76b11010 00000000 76f288bf 76f2884d 12010278
#76b11020 00000000 00000000 001bf300 00000000
#76b11030 00000028 00000000 00000000 001bf06c
#76b11040 001bf768 12010278 76f288aa 00000000
#76b11050 00000000 00000000 001bf774 00000028
#76b11060 00000000 001bf300 00000000 007f0000
#76b11070 03050212 001bf300 00000000 00000000
kd> dd 0x1bf000
001bf000  001bf01c 00000000 76f2873d 001bf084
001bf010  00000000 76f288bf 76f2884d 12010278
001bf020  00000000 00000000 001bf300 00000000
001bf030  00000028 00000000 00000000 001bf06c
001bf040  001bf768 12010278 76f288aa 00000000
001bf050  00000000 00000000 001bf774 00000028
001bf060  00000000 001bf300 00000000 007f0000
001bf070  03050212 001bf300 00000000 00000000

当然一致しているわけでして.

Invalid Paging

では,若干恣意的ですが,そこからスタックの先頭に向かってPTEの値を調べていきましょう.

kd> !pte 0x1be000
                    VA 001be000
PDE at C0600000            PTE at C0000DF0
contains 0000000077407867  contains 8000000076B98867
pfn 77407     ---DA--UWEV  pfn 76b98     ---DA--UW-V

kd> !pte 0x1bd000
                    VA 001bd000
PDE at C0600000            PTE at C0000DE8
contains 0000000077407867  contains 80000000760B8867
pfn 77407     ---DA--UWEV  pfn 760b8     ---DA--UW-V

(snip)

kd> !pte 0x1ba000
                    VA 001ba000
PDE at C0600000            PTE at C0000DD0
contains 0000000077407867  contains 8000000076304867
pfn 77407     ---DA--UWEV  pfn 76304     ---DA--UW-V

kd> !pte 0x1b9000
                    VA 001b9000
PDE at C0600000            PTE at C0000DC8
contains 0000000077407867  contains 0000000000000280
pfn 77407     ---DA--UWEV  not valid
                            DemandZero
                            Protect: 14 - ReadWrite G

なにやら,おかしなPTEが見つかりました.Present bitが立っていないのでnot validですが,値が代入されています. 結論からかくと,Demand Paging戦略によるものです.Page Fault Handlerがココに含まれるアドレスへの参照によって呼び出された場合,そのInvalidなPTEに特殊なフラグが設定されていた場合,Demand Zero Pageと解釈します.したがってPage Fault Handlerは4KB全てがゼロクリアされた物理メモリのアドレスとよしなに設定されたフラグをこのPTEに設定して,処理をPage Fault元に返してやります.

これにはメリットがあり,Demand Pagingによって要求があるまで物理ページを割り当てないことで省メモリを実現することができるわけです.このあたりの処理はntoskrnl.exeのMmAccessFault()に実装されています.また,Invalid PTEには他にも種類があり,ページがスワップアウトされていることを指し示すものや,複数のプロセスで共有されているものなど,扱いも様々です.

まとめ

とりとめもなく,Windows on x86のPagingに関する機能について書いていきました.この記事だけでPagingが分かるわけないので,困ったらIntel SDMをあたりましょう.

執筆途中で,そっくりな記事がMSDNに公開されていることに気がついて萎えたことは内緒.