Linux KernelにおけるCopy On Write(CoW)の仕組み(概要編)

はじめに

Copy On Write(CoW)とは書き込みが実際に起こるまで、複数のプロセスが同じ物理メモリを共有し続ける方法である。もっと端的に言うと、書き込みが発生したら、そこで初めて該当のpageのみ遅延複製する1Linuxでは、以下の2つの場面2で用いられる:

  • fork()時の子processのメモリ複製。

  • mmapのflags 引数にMAP_PRIVATEを、prot引数にPROT_WRITEを付加したとき

    • dynamic loaderにて、shared libraryをメモリに展開するとき
    • 0埋め領域を確保するとき(MAP_ANONYMOUSも付加する)

f:id:knknkn11626:20190812152951p:plain
mmapのflagsとprotの2*2 table. Reference[1]のch.49より

もし、CoWが実装されていなければ、少なくとも書き込み可能領域の場合は、元の領域とは別の物理メモリ領域内に同内容のデータが全て複製される必要がある。もし、複製しておかないと、書き込みされる領域が物理的に共有されてたら、複数のプロセスがその領域を修正することになるので、やばい。

f:id:knknkn11626:20190812135936p:plain
Reference[1] ch.24より

もし、CoWが実装されていれば3、書き込みが起こったときに図のように書き込みの領域のみを別の物理メモリ内の領域に複製するので、「複数のプロセスがその領域を修正する」危険性はなくなる。領域の節約ができるし、コピーにかける時間も最小限にすることができるのでメリットが大きい。

ユーザーサイドから見たCoWの仕組みは以上のようになるが、

「書込み可能な領域に書き込んだのに、気がついたら複製されるのでなんともないよ」、なんて都合のいいというか、狐につままれたような話ではないか??

実はこの先の原理については、kernelサイド(及び、x86のハードウェアの機能)でやってくれているので、本記事ではどのような仕組みになっているのかを内側から覗き、理解することを目標にする。

Reference

  • [1] The Linux Programming Interface(TLPI)

  • [2] Understanding the Linux Kernel (本記事では、version2.6.11(x86: 32bit)をもとにしてます)

概要

「書込み可能な領域に書き込んだのに、気がついたら複製される」仕組みについては、Page Fault Exception4 (#14)によって実現されている。つまり、

  1. user側で書き込み領域(address)に書き込んだ
  2. 実際は書き込み領域ではなかった!!のでPage Fault Exception(#14)が発生(kernel modeに)
  3. exception handler内で、該当のaddressのページを複製する。(forkの場合とmmapの場合で処理が異なるので後述)
  4. exception handlerが終了して(user modeに戻り、)user側では「気がついたら複製される」

という感じになっている。さて、2の「書き込み領域ではなかった」というのはどういうことか? 1で書き込み領域と設定しているのにも関わらず?


まず、2のpage faultの仕組みについてもう少し深堀りする。page faultはpaging5の下図のPage Table Entry(PTE)の権限が要求権限を満たしていないときに発生する。hardware側で管理している権限だ。

f:id:knknkn11626:20190812145055p:plain
Page Table Entry(PTE) [2-level pagingの場合]

bitposition\内容 1 0
0 Present Non-Present
1 Write Read
2 Supervisor User

となっている。

一方、1の領域の権限の設定はproc->mm->mmapvm_area_struct構造体のvm_flagsメンバで管理されている。これらの値は主要なものとして以下のようになっている:

// https://kernel.googlesource.com/pub/scm/linux/kernel/git/stable/linux-stable/+/refs/heads/linux-2.6.11.y/include/linux/mm.h#138
#define VM_READ        0x00000001 /* currently active flags */
#define VM_WRITE   0x00000002
#define VM_EXEC        0x00000004
#define VM_SHARED  0x00000008

書き込み領域の場合はVM_WRITEのフラグが立っている状態だ。

2でexceptionが起こったということは、PTEの権限がvm_flagsの内容と同期していなかったということを意味する。

実は、LinuxのCopy On Write(CoW)の仕組みはこの両者のズレを利用した仕組みである(要するに、意図的に両者に齟齬が出るようにしており、exceptionをトリガーにして遅延複製を可能にしている。)。もちろん、両者はexception handlerの過程で同期される(そうでないと、複製完了したのにも関わらず、また全く同じexceptionが生じる。)

Note) page cache(struct page)のflagはdiskとphysical memoryの同期のために主に用いられるので、こんがらがらないように。

forkとmmap

「はじめに」の章で述べたforkとmmapでは、意図的にvm_flagsとPTEの権限に齟齬がでるようにしている。

  • forkでは、子プロセスのpagingを設定する際(do_fork -> copy_process -> copy_mmで)、PTEに_PAGE_RWを意図的に外した状態で設定している -> だから書き込みが生じたときに2でpage fault exceptionが生じる
  • mmapでflags 引数にMAP_PRIVATEを、prot引数にPROT_WRITEを付加したとき、PROT_WRITE -> VM_WRITEに変換した上で、vm_flagsにVM_WRITEが設定され、vm_area_structが作成されて現在のprocessに紐付けられる(PTEは何もいじってない) -> だから書き込みが生じたときに、該当するPTEの権限が足らずにpage fault exceptionが起こる

page fault handler

さて、page fault exceptionが出る仕組みについてはわかったが、この後、以下のことを行う:

  • vm_flagsに沿うようにPTEの権限を修正する

  • page faultが生じたaddressに属するpageを(物理メモリの意味で)複製して、PTEを修正

これらの実装については、do_page_fault -> handle_mm_fault -> handle_pte_faultのdo_no_page(mmapのみ)とdo_wp_page(fork, mmap両方の場合)で行われるので、別記事で実装の詳細をたどることにしよう。

まとめ

  • Copy On Write(CoW)はprocessが保有するPage Table Entry(PTE)とvm_area_structのvm_flags間で意図的に両者に齟齬が出るようにすることで実現されてるよ

  • 複製のタイミングはpage fault exceptionがトリガーになっているよ。このexception handlerで両者の齟齬が解消されるよ。

補足

virtual memoryとphysical memory

virtual memoryはprocessごとに異なり、physical memoryは(例外はあれど)1つしかない。

virtual memoryを実現するために、x86ではpagingという機能が備わっている。pagingは一言で言えばvirtual memoryからphysical memoryへの写像である。(virtual memoryはprocessごとに異なるので、pagingの設定もprocessごとに異なる)

pagingが同一であっても違うvirtual memory addressだと、指し示すphysical memory addressが異なる。これは当たり前といえば当たり前。

大切なのが、同じvirtual memory addressでもpagingの設定が異なれば、指し示すphysical memory addressが異なる。


  1. 実は、後述のように2回目以降は遅延複製は起こらないようになっている

  2. Reference1のch.49 49.1のOverviewにも2つの場合があると書いているのでダイジョブでしょ。

  3. ちなみに、xv6では実装されてない。最初から全複製してる

  4. 実は、https://kernel.googlesource.com/pub/scm/linux/kernel/git/stable/linux-stable/+/refs/heads/linux-2.6.11.y/arch/i386/kernel/traps.c#1023 で設定されてる通り、厳密にはinterruptである。カーネルモードでもpage fault “interrupt"が呼び出されることが大きな違い(exceptionはユーザーモードカラのみ呼び出される)。

  5. pagingの雰囲気は補足の"virtual memoryとphysical memory"の節を参考に。