はじめに

Copy On Write(CoW)とは書き込みが実際に起こるまで、複数のプロセスが同じ物理メモリを共有し続ける方法である。もっと端的に言うと、書き込みが発生したら、そこで初めて該当のpageのみ遅延複製する¹。Linuxでは、以下の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が実装されていれば³、書き込みが起こったときに図のように書き込みの領域のみを別の物理メモリ内の領域に複製するので、「複数のプロセスがその領域を修正する」危険性はなくなる。領域の節約ができるし、コピーにかける時間も最小限にすることができるのでメリットが大きい。

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

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

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

Reference

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

概要

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

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

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

まず、2のpage faultの仕組みについてもう少し深堀りする。page faultはpaging⁵の下図の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->mmapのvm_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が生じる

ちがうわ。https://t.co/YiHVxrrR2P
の部分。copy_process -> copy_mm -> dup_mmap -> copy_page_range -> .. -> copy_one_pte の部分がCopy On Writeの本質的な箇所！

forkのCopy On Writeの仕組みについてはブログでまとめると良いかもなぁ。
— Kenta Nakajima (@knknkn26918) August 1, 2019

mmapでflags 引数にMAP_PRIVATEを、prot引数にPROT_WRITEを付加したとき、PROT_WRITE -> VM_WRITEに変換した上で、vm_flagsにVM_WRITEが設定され、vm_area_structが作成されて現在のprocessに紐付けられる(PTEは何もいじってない) -> だから書き込みが生じたときに、該当するPTEの権限が足らずにpage fault exceptionが起こる

do_mmap_pgoff(mmapのコア関数)はvmaをallocし、vm_flagsメンバをいい感じに設定(https://t.co/75rg6mYDr5 で)することでCoWなどを達成してる。

面白いのが、MAP_ANONYMOUSはmmapの最初期にしか用いられてないということhttps://t.co/3nyMaAlQy8
— Kenta Nakajima (@knknkn26918) August 9, 2019

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ごとに異なる)

#memo
xv6のvirtual memory 概要 pic.twitter.com/Mt2blKSlLo
— Kenta Nakajima (@knknkn26918) August 7, 2019

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

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

実は、後述のように2回目以降は遅延複製は起こらないようになっている↩
Reference1のch.49 49.1のOverviewにも2つの場合があると書いているのでダイジョブでしょ。↩
ちなみに、xv6では実装されてない。最初から全複製してる↩
実は、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はユーザーモードカラのみ呼び出される)。↩
pagingの雰囲気は補足の"virtual memoryとphysical memory"の節を参考に。↩