Linux(x86-32bit)のページフォルトハンドラを読んでみる(その1)

## 今回やること
[前回](http://qiita.com/akachochin/items/259c865cf4ab1fcd11df)はmmap()をざっくり読んでみました。
その際に以下のように書きました。

>ここまで見たとおり、アドレス空間のマップと同時に物理ページを割り当てている様子はありません。
>ユーザ空間であればそれはごく普通のことです。それは、デマンドページングというやつでしょう。
>この場合、実際に物理メモリを割り当てるのは、ページフォルトハンドラとなるはずです。

そこで今回はページフォルトハンドラを見て、Linuxの仮想記憶をもう少しだけ深く知ってみましょう。
ただ、ページフォルトハンドラは長いです。なので何回かに分けて書いてみます。

## ページフォルトハンドラはどこにあるのか
ハンドラの名前に「fault」が含まれると思われるので、arch/x86の下をgrepします。
検索結果を漁ると、以下の関数が見つかります。

```c:arch/x86/mm/fault.c
dotraplinkage void __kprobes notrace
do_page_fault(struct pt_regs *regs, unsigned long error_code)
{
  unsigned long address = read_cr2(); /* Get the faulting address */
  enum ctx_state prev_state;

  /*
   * We must have this function tagged with __kprobes, notrace and call
   * read_cr2() before calling anything else. To avoid calling any kind
   * of tracing machinery before we've observed the CR2 value.
   *
   * exception_{enter,exit}() contain all sorts of tracepoints.
   */

  prev_state = exception_enter();
  __do_page_fault(regs, error_code, address);
  exception_exit(prev_state);
}
```
この関数がどう呼ばれるのか、例外ハンドラの登録はどうしているのか、についてはこの文書の末尾のAppendixに書いてみました。参考にしてください。

さて、Intel SDMによれば、read_cr2()で読み込み対象としているCR2は以下のとおりです。

>The processor loads the CR2 register with the 32-bit linear address that generated the exception. The page-fault handler can use this address to locate the corresponding page directory and page-table entries.
(Interrupt 14—Page-Fault Exception (#PF)の説明より抜粋)

つまり、仮想アドレスによるアクセスを試みた際、ページフォルトの条件を満たした場合にページフォルト例外が発生し、アクセス対象とした仮想アドレスがCR2を通して取得できるということです。

さて、__do_page_fault()を読んでみます。ここは長いので順番に読みます。
まず、現在実行状態のプロセス、つまりページフォルト例外を引き起こしたプロセスのstruct mmを取得します。
これは、該当プロセスの仮想アドレス空間のどの領域がアクセス可能か、そしてそれら領域の属性がどうなっているか調べるために必要です。

```c:arch/x86/mm/fault.c
static void __kprobes noinline
__do_page_fault(struct pt_regs *regs, unsigned long error_code,
    unsigned long address)
{
  struct vm_area_struct *vma;
  struct task_struct *tsk;
  struct mm_struct *mm; 
  int fault;
  unsigned int flags = FAULT_FLAG_ALLOW_RETRY | FAULT_FLAG_KILLABLE;

  tsk = current;
  mm = tsk->mm;
```

kmemcheckとは何でしょうか。
どうやら、デバッグ用の機能で未初期化のメモリに対するアクセスを検出する機能のようです。

>kmemcheck is a debugging feature for the Linux Kernel. More specifically, it is a dynamic checker that detects and warns about some uses of uninitialized memory.
>
>Userspace programmers might be familiar with Valgrind's memcheck. 
>(略)
>... kmemcheck is not as accurate as memcheck, but it turns out to be good enough in practice to discover real
programmer errors that the compiler is not able to find through static analysis.
>(Documentation/kmemcheck.txt)


推定ですが、exampleでは未初期化のメモリ空間に対するreadも補足していることおよびページフォルト内にこの機能があることなどから、対象となるページをアクセス禁止属性にするのかな？想像が膨らむ面白そうな機能ですね。
色々読んでみたいのはやまやまですが、ここは推定に留めて、先に進みましょう。

```c:arch/x86/mm/fault.c
  /*
   * Detect and handle instructions that would cause a page fault for
   * both a tracked kernel page and a userspace page.
   */
  if (kmemcheck_active(regs))
    kmemcheck_hide(regs);
  prefetchw(&mm->mmap_sem);
```

## kmmio?
```c:arch/x86/mm/fault.c
  if (unlikely(kmmio_fault(regs, address)))
    return;
```

この関数には、kmmioとついています。kmmio_fault()を少し読んでみましたが、どうも何かの特殊な領域を扱うための機能のようです。
で、調べてみると、[LWN.netの記事](http://lwn.net/Articles/21392/)にヒントがありました。
要するに「指定したメモリマップドI/O用のメモリへのアクセスを検知して例外で捕まえる」仕組みのようです。

>(略)while kicking around ideas in the fault injection project, the need for some additional non-fi specific features has surfaced.

>One of these needs is the ability to hook (in same way that kprobes can add a hook) to a specific memory mapped IO region before the user of the region gets 
access.(略)
>We also followed the same usage that kprobes provides, with a register_kmmio_probe() function for adding the hook/probe, and a unregister_kmmio_probe() function for removing the hook/probe.

どうやって実現しているのかは読んでみないとわかりませんが、以下を予想してみます。自分の予想があたっているか、今度読んでみます。

<予想>
>(1)Linuxの仮想記憶側(プロセスのメモリ空間 or カーネルメモリ空間(init_mm))では該当メモリマップドI/Oの仮想アドレス空間を覚えておくが、ページテーブル側には反映しない
>(2)アクセスにより、ページフォルトハンドラ側で一時的にメモリマップしてI/Oを代行する。もちろんこのときにprobe処理をする。
>(3)ページフォルトハンドラの戻り先アドレスを位置命令後に進めて、メモリマップを解除してしれっとフォルトハンドラから抜ける。

## カーネルのアドレス空間へのアクセスで起きるページフォルト
まず、最初に言っておくと、カーネルのアドレス空間へのアクセスでページフォルトが起きるのは例外的です。
[以前書いた記事](http://qiita.com/akachochin/items/5bf126a6218aff220ab6)のストレートマップ領域を覚えているでしょうか。
ストレートマップ領域は仮想アドレスと物理アドレスの変換はページテーブルを調べるまでもなく引き算で行っていました。

今回のCPUはMIPSでなくx86なので、ストレートマップ領域のアドレス空間割り当て時にページテーブルに仮想 - 物理の対応を書き込んでおく必要があります。つまり、ストレートマップ領域はデマンドページングでなく常にレジデント(物理メモリが割り当てられている)です。

カーネルのメモリ空間が一般にレジデントなのは、主に以下2点です。

>(1)パフォーマンス。カーネル空間での処理は一般的に高優先度だったりします。そのような処理中にページフォルトが発生するのは実行コストが非常に高いです。
>(2)物理メモリ不足時にも動作を保証するため。例えば、ページデーモンが動こうとしたけど、物理メモリ不足で動けません！では話にならないのです。

しかし、物理メモリは本当に重要なリソースです。それでもやはり物理メモリをケチりたいという考えなのでしょう。
私がこの前書いた[「Linuxの仮想 - 物理アドレスと、カーネル空間の概要(その2)」](http://qiita.com/akachochin/items/3a6fd959a84d113f6f15)のように、vmalloc()など一部のカーネルアドレス空間についてはデマンドページングになっているようです。
それらを捌くのがvmalloc_fault()、kmemcheck_fault()です。

```c:arch/x86/mm/fault.c
  /*
   * We fault-in kernel-space virtual memory on-demand. The
   * 'reference' page table is init_mm.pgd.
   *
   * NOTE! We MUST NOT take any locks for this case. We may
   * be in an interrupt or a critical region, and should
   * only copy the information from the master page table,
   * nothing more.
   *
   * This verifies that the fault happens in kernel space
   * (error_code & 4) == 0, and that the fault was not a
   * protection error (error_code & 9) == 0.
   */
  if (unlikely(fault_in_kernel_space(address))) {
    if (!(error_code & (PF_RSVD | PF_USER | PF_PROT))) {
      if (vmalloc_fault(address) >= 0)
        return;
      if (kmemcheck_fault(regs, address, error_code))
        return;
    }

    /* Can handle a stale RO->RW TLB: */
    if (spurious_fault(error_code, address))
      return;

    /* kprobes don't want to hook the spurious faults: */
    if (kprobes_fault(regs))
      return;
    /*
     * Don't take the mm semaphore here. If we fixup a prefetch
     * fault we could otherwise deadlock:
     */
    bad_area_nosemaphore(regs, error_code, address);

    return;
  }
```

## spurious_fault()
さて、上のコードにあるspurious_fault()ですが、これも[LWN.netの記事](http://lwn.net/Articles/266584/)が参考になりそうです。

>When changing a kernel page from RO->RW, it's OK to leave stale TLB entries around, since doing a global flush is expensive and they pose no security problem.  >They can, however, generate a spurious fault,which we should catch and simply return from (which will have the side-effect of reloading the TLB to the current PTE).

TLBは、ページテーブルのキャッシュです。
仮想アドレスと物理アドレスの対応やアクセス属性をページテーブルのエントリとして記述しています。CPUはページテーブルをたどってこれを探しますが、毎度同じエントリを探すのも効率が悪いです。
そこで、そのためのキャッシュとしてTLBがあります。

普通に考えると、ページテーブルを書き換えてページの属性を変えたのだから、そのキャッシュであるTLBも破棄しないといけません。

しかし、特にglobalなTLBエントリを破棄することはコストが大きいのです。よって、ページの属性をRO -> RWに変えただけの場合、あえてTLBのエントリをflushしません。

この状態では、該当ページの書き込みが起きたとき、TLBに記録されている該当エントリはROのままなのでページフォルト例外が起こります。
その場合、特に何もせずにページフォルトハンドラを抜けます。
そうすることで、再度行われる該当仮想アドレスへの書き込みを今度は無事終わらせることができます。

え？TLBエントリをInvalidateしなくてもよいのか、と思われるかもしれませんが、Intel SDMには以下のように書かれています。ページフォルトが起きたとき、該当アドレスが属する空間に関するTLBエントリは破棄されるのです。

>4.10.4.1 Operations that Invalidate TLBs and Paging-Structure Caches
>(大幅に省略)
>In addition to the instructions identified above, page faults invalidate entries in the TLBs and paging-structure caches. In particular, a page-fault exception resulting from an attempt to use a linear address will invalidate any TLB entries that are for a page number corresponding to that linear address and that are associated with the current PCID.

※なお、RW -> ROにした場合は、TLBエントリの破棄が必要です。もし、TLBを更新しない場合、該当ページが書き込み禁止になったことをTLB側が知らないので、書き込み要求時のTLBヒットにより書き込みが許可されてしまうためです。これが先のLWN.netの記事に言う「security problem」でしょう。

## 次回
次回は__do_page_fault()の続きを追ってみます。
カーネル空間へのアクセスという特殊な処理はここまでで終わっていますので、ユーザ空間へのアクセスで引き起こされたページフォルトがメイントピックになります。

## Appendix
### 例外ハンドラについて
do_page_fault()は、以下のアセンブラの関数から呼ばれています。

```asm:arch/x86/kernel/entry_32.S
ENTRY(page_fault)
  RING0_EC_FRAME
  ASM_CLAC
  pushl_cfi $do_page_fault
  ALIGN
error_code:
/*以下略 */
```

そして、この関数は以下の通り、IDT(Interrupt Descriptor Table)に記録されます。

```c:arch/x86/kernel/traps.c
/* Set of traps needed for early debugging. */
void __init early_trap_init(void)
{
  set_intr_gate_ist(X86_TRAP_DB, &debug, DEBUG_STACK);
  /* int3 can be called from all */
  set_system_intr_gate_ist(X86_TRAP_BP, &int3, DEBUG_STACK);
#ifdef CONFIG_X86_32
  set_intr_gate(X86_TRAP_PF, page_fault);
#endif
  load_idt(&idt_descr);
}
```
(詳しいことが知りたい場合、include/asm/desc.hを見て、set_intr_gate()の実装を追ってみましょう。単にIDTの書式に合わせて例外ハンドラのアドレスを書き込んでいるだけです。)
ちなみに、例外ベクタ番号は以下のとおりです。

```c:arch/x86/include/asm/traps.h
/* Interrupts/Exceptions */
enum {
  X86_TRAP_DE = 0,  /*  0, Divide-by-zero */
/* 略 */
  X86_TRAP_PF,    /* 14, Page Fault */
```

Intel SDM Vol3.Chapter6 6.3.1「External Interrupts」に書かれたページフォルトの例外番号と一致していますね。

x86の割り込みや例外については、「はじめて読む486」にざっと目を通してから、上記Intel SDMを読むのが一番です。IntelのWeb Pageからダウンロードしてみましょう。

こうしたカーネルの低レベルなコードを読む際には必須です。(たくさん章がありますが、Volume3 Chapter6の必要な箇所を読めば十分でしょう)