前回は、概要を述べて、mmap域への書き込みの検出方式として大きく2通り、細かくは3通り (1a ページテーブルスキャン方式、1b 物理ページスキャン方式、2 write fault捕捉方式) を予測した。本稿では、広く使われているOSSのOSのコードを調べて、どの方式を取っているか、あるいは他の方式を取っているのか調べてみる。
Linuxの場合
Linuxの仮想メモリ関連コードは、ソースツリーのmmというディレクトリにあり、ページ置換コードはvmscan.cにある。
Linuxのmmコードの特徴として、機種非依存部が直接ページテーブルを操作する点が挙げられる。もちろん、ページテーブルの構造は機種によって様々であるが、機種依存部で定義されたマクロを介して操作している。多段ページテーブルの構造までが機種非依存部に現れているのは、あまり見かけない特徴だと思う。これは、Linuxが元々x86専用のカーネルであったこと、比較的新しいためエキセントリックなMMUが淘汰され、似通った構成のMMUばかりになった後で開発されていることなどが影響していると考えられる。
ページテーブルのスキャン
x86のMMU操作マクロは、arch/x86/include/asm/pgtable.hなどで定義されている。あるページのD bitが立っているかどうかを調べるマクロは、pte_dirty()。
vmscanは大変複雑なコードである。ページ入れ替えが動くのは2通りの場合があり、一つはkswapdというカーネル内で動作するバックグラウンドプロセス (kthread) が実行する場合、もう一つはLinuxないでメモリを獲得しようとしたときに、空きメモリがなかった (非常に少なかった) 場合にフォアグラウンドで実行される場合 (direct reclaim) である。どちらも、最終的にはshrink_node()という所にくる。
この先を追いかけても (それなりに骨が折れる)、直接・間接にpte_dirty()を呼んでいるところは存在しない。したがって、Linuxはwrite fault捕捉方式らしいことがわかる。
write faultとページ書き出し
念のため、write faultのコードと、ダーティページの書き出しの部分を見てみる。Linuxのページフォルトコードは、機種依存部にあるページフォルトルーチンを経てhandle_mm_fault()にくる。このとき、write faultのときはflags引数 (ビットマップ) でFAULT_FLAG_WRITEが指定されている。この後__handle_mm_fault()→handle_pte_fault()と来る (途中HugePagesとか多段ページテーブルの上位部分の処理などは気にしない)。FAULT_FLAG_WRITEかつページが書き込み禁止 (!pte_write(entry)) のときは、do_wp_page()に飛ぶ。ファイルをMAP_SHAREDでマップしている場合はwp_page_shared()だ。
vma->vm_ops->page_mkwriteは、filemap_page_mkwrite()を指しているはずで、この中でファイルのタイムスタンプを更新し、またページをダーティにしている (このダーティは、PTEのD bitのダーティとは異なりページ属性である。あるページが複数プロセスからマップされている場合、対応するPTEは複数あり、書き込みが行われた仮想空間に対応するページテーブルの中のPTEのD bitがセットされる。write(2)などのシステムコールでダーティとなるのはカーネル空間のページテーブルの中のPTEであり、vmscanの対象にはならないが、これはいつダーティとなるかが明白であるためシステムコールの時点でページ属性のダーティをセットできる。またset_page_dirty()では、ページをダーティページを管理するリストにつなぐ処理も行っている)。
このダーティなページを書き出すのは、bdi flusherという人である。bdi flusherによる書き出しは、sysctl変数vm.dirty_expire_centisecsなどで制御され、ある程度のメモリ書き込みを貯めてからストレージに書き出すようになっている。現在はworkqueueを利用して実装されている。データをキューに登録すると、後からコールバック関数を実行してくれる仕組みで、この場合データはブロックデバイスごとに作られる (正確にはmemcgごとにも) struct bdi_writeback (wb)、コールバック関数はwb_workfnである。
この先は煩雑なので省略するが、ページキャッシュの書き出しは、do_writepages()でファイルシステム毎に用意されたwritepagesメソッド (ext4ならext4_writepages()、XFSならxfs_vm_writepages()など) の先で行われるようだ。ここでは、汎用 (ファイルシステムごとのwritepagesメソッドが登録されていないときに呼ばれ、またテンプレート的なコードでもある) のgeneric_writepages()を追ってみる。本体は、write_cache_pages()だ。指定のファイルのダーティページキャッシュを書き出す。
whileループの中で、pagevec_lookup_range_tag()で、ダーティなキャッシュページを探してくる。結果が収められるstruct pagevecは、物理ページを表すstruct pageの固定長配列 (長さ15) で、forループはpagevecの要素毎のもの。pagevec_lookup_range_tag()ではダーティページのみを探すようになっているが、他のCPUなどでフラッシュが行われたりした場合はスキップするなどの処理後、
if (!clear_page_dirty_for_io(page))
goto continue_unlock;
trace_wbc_writepage(wbc, inode_to_bdi(mapping->host));
error = (*writepage)(page, wbc, data);
この部分がミソである。clear_page_dirty_for_io()は後で見るが、これから書き出すのでダーティマークを外す、といった名前になっている。writepageはファイルシステム依存のwritepageメソッドで、その名の通りページを書き出す。
clear_page_dirty_for_io()は、同じファイルの少し後ろにある。以下がキモだ。
if (page_mkclean(page))
set_page_dirty(page);
page_mkclean()はrmap.cの中にある。rmapとは、reverse mapの略で、物理ページからPTEを得るための構造である。物理ページは複数のPTEから参照される可能性があるので、その一つ一つについてpage_mkclean_one()を呼び出す。というわけで、ようやく
entry = ptep_clear_flush(vma, address, pte);
entry = pte_wrprotect(entry);
entry = pte_mkclean(entry);
set_pte_at(vma->vm_mm, address, pte, entry);
にたどり着いた。D bitを落とすと同時にR/W bitをクリアしてwrite protectしている。これで、ページキャッシュの書き出しを始める前にread onlyにしていることがわかった。
NetBSDの場合
NetBSDは、4.4BSDをベースとしたOSである。4.4BSDは、仮想メモリシステムをCMUのマイクロカーネルMach (マーク) から移植したようだが、要件の異なるMachの仮想メモリシステムを使い続けるのは無理があったのか、NetBSDは仮想メモリシステムを独自のものに置き換えた。このコードをUVMとよび、The NetBSD Projectの文書のページからリンクされているCharles D. Cranorの学位論文に詳しく説明されている (20年以上前の論文であり、現状とは異なる点には注意が必要)。
NetBSDのUVMでは、機種依存部 (NetBSD用語でMD: Machine Dependent) はpmapレイヤと呼ぶ。機種非依存部 (MI: Machine Independent) に登場するのは、Linuxのようなページテーブルそのものではなくstruct pmapというopaque構造体 (MDのpmapレイヤで実装される) と、仮想アドレス (VA)、物理アドレス (PA) などである。ページテーブルの多段構造などは、pmapレイヤに隠蔽されている。UVMは、Mach仮想メモリシステムとpmapレイヤとのインターフェイスを保つ形で実装された。
NetBSDのソースコードに慣れている人はさほどいないと思われるため、簡単に用語解説をしておく。
- struct vm_map: 仮想メモリ空間を表す。Linuxのstruct mm_structに相当。
- struct vm_map_entry/entry: 仮想メモリ空間の一部で、実行ファイルのテキスト領域、データ領域、スタックなどに、それぞれ1つずつが割り当てられる。Linuxのstruct vm_area_structに相当。
- struct vnode/vnode: ファイルを表す。Linuxのstruct inodeに相当する。inode operationsに相当するメソッド群をvnode operations (vnops) と呼ぶ。
- pager: ページング動作を行う人で、ページング先によってvnode pager (通常ファイル)、aobj pager (swap域。なお、通常の匿名メモリはaobjではなく、aobj pagerはtmpfsなどの少々特殊な目的)、device pager (キャラクタデバイス) などがある (他にread(2)/write(2)などのための特殊なpagerであるUBCなど)。実体はPGO (Pager Operations) とよばれる関数ポインタ群で、ページ読み込みのためのpgo_get、ページ書き出しのためのpgo_putなどがある。
- struct uvm_object/uobj: ファイルやデバイスなどをさす。それぞれ、pager一つと関連づけられている。vnode pagerと結びついたvnode object (uvn)、デバイスと結びついたdevice object (udv)、aobj pagerと結びついたaobjなどがある。
- upper layer/lower layer: 各vm_map_entryのlower layerはuobj、upper layerは匿名メモリを管理する構造 (aobjではない) である。たとえばプロセスのテキスト域は、通常vnode objectのlower layerのみをもつ。データ域は当初はvnode objectのlower layerのみを持つが、そこに書き込みが発生すると、Copy on Writeによりupper layerに匿名メモリが確保される (この動作をpromoteと呼ぶ)。ヒープやスタックはupper layerのみを持つ。
- wired page/wire/unwire: mlock(2)やI/Oの最中などで、一時的にページアウトの対象とならないページのことをwired pageとよび、あるページをそのような状態にする操作をwire、wired pageをページング対象に戻す操作をunwireと呼ぶ。
- protection: 仮想メモリのパーミッション (R/W/X) のこと。各entryには、mmap(2)の引数で示されるprotectionの他に、max_protectionが定義されており、これはmmap時のopen(2)のフラグ (O_RDONLYなど) などによって決まる。たとえば、MAP_PRIVATEでmmapされた領域では、常にmax_protectionでは書き込みが許されている。プロセスのテキスト域は通常r-xでmmapされている (protectionがr-x) が、gdbなどからブレークポイントを仕掛けると、指定アドレスの命令をブレークポイント命令に書き換える。こうした特殊な場合にmax_protection (常に書き込みが許可されているのでrwx) が適用される。
- pv mapping/pv: Physical to Virtual mapping。物理アドレスから仮想空間 (struct pmap)/仮想アドレスを引く仕組みで、Linuxのrmapに相当するが、pmapレイヤで実装されている。同一物理ページが複数の仮想アドレスにマップされることがあるので、リスト構造になっている。
- loan: 仮想メモリ空間の間でページを貸し借りするUVMの機能で、プロセス間通信 (pipeなど) の実装に使われている。
NetBSDのソースコードは、CVSで管理されているが、特定の行にリンクするため、以下ではGithubのミラーを参照する。
ページテーブルのスキャン
pmapインターフェイスで、あるページのD bitが立っているかどうかを調べるのは、pmap_is_modified()である。引数は物理ページであるため、これを指すPTEは複数ある可能性があり、その場合は1つでもD bitがセットされているPTEがあれば真を返す。他にpmap_clear_modify()が、あるページを指すPTE (複数ある可能性) のD bitをクリアすると同時に、セットされているPTEがあったかどうかを返す (Linuxのpage_mkclean()相当)。UVMでページ解放を担うのは、page daemon (pdaemon) というカーネルスレッドであるが、この先どころか、実は、UVMのソースコード全体をgrepでさらってみても、pmap_is_modified() (やpmap_clear_modify()) を呼んでいる箇所はない。したがって、NetBSDもwrite fault捕捉方式らしいとわかる。
興味深いことに、NetBSDではページ置換アルゴリズムがpluggableになっていて、実際にClock、Clock Proの2種類から選択することができる。
write faultとページの書き出し
念のため、write faultのコードと、ダーティページの書き出しの部分を見てみる。NetBSDのページフォルト処理は、uvm/uvm_fault.cにある。write faultの場合、引数access_typeに、VM_PROT_WRITEが入っていて、これはstruct uvm_faultctx flt.access_typeに保存される。上の方にあるコメントによると、mmapでMAP_SHAREDでファイルを貼った部分へのwrite faultは、CASE 2Aという分類だ。uvm_fault_lower()というところで処理される。uobjは、mmapされているファイルをあらわしている。
通常ファイルの場合、uobj->pgops->pgo_faultはNULL、uobj->pgops->pgo_getはuvn_get()、またファイルシステムがBSD FFSの場合のvop_getpagesがgenfs_getpages()である、ということに留意してコードを追いかけると、uvm_fault_lower()→uvm_fault_lower_lookup()→uvm_get()→VOP_GETPAGES()→genfs_getpages()と進む。genfs_getpages()は、ページキャッシュにストレージからデータを読み込んでくるところだ。access_typeのVM_PROT_WRITEは、変数memwriteに反映される。またタイムスタンプが更新されている。そして261行目。
if (error == 0 && memwrite) {
genfs_markdirty(vp);
}
ここでvnodeをダーティとし、後述のsyncerによるライトバック対象のリストに登録している。ページをダーティとしている (ページのflagsからPG_CLEANフラグを落とす) 部分はないようだ (以下のダーティページを書き出す処理を読むと、確かに不要に思える)。どこかでダーティにしているのであれば、誰か教えてください。
次に、ダーティページを書き出す処理。これは、syncerというカーネルスレッドが行う。syncerの本体は、sched_sync()である。ここからlazy_sync_vnode()→VOP_FSYNC()→ffs_fsync()→ffs_full_fsync()→vflushbuf()→VOP_PUTPAGES()→genfs_putpages()で書き出される。wapblというのは、ext3/4のjournalに相当するが、ここではないものとしよう。vflushbuf()でPGO_CLEANITをセットしているので、その流れを追うと、まずfstransという仕組みでtransactionを開始してretryにもどり、whileループに入る。whileループでは、オンメモリのページの粗密により、by_list (ページのリストを辿る) かページを順々に見ていくか切り替えているようだ。いずれにしても、現在の対象ページはstruct vm_page *pgに入っている。
この先少々自信がない。1112行目
if (flags & PGO_CLEANIT) {
needs_clean = pmap_clear_modify(pg) ||
(pg->flags & PG_CLEAN) == 0;
pg->flags |= PG_CLEAN;
} else {
pmap_clear_modify()で、pgを指す各PTEのD bitを落とすとともに、落とす前のD bitがneeds_cleanに反映される。
またread onlyにしているのはその少し前のようだ。
if (cleanall && wasclean &&
gp->g_dirtygen == dirtygen) {
/*
* uobj pages get wired only by uvm_fault
* where uobj is locked.
*/
if (pg->wire_count == 0) {
pmap_page_protect(pg,
VM_PROT_READ|VM_PROT_EXECUTE);
} else {
cleanall = false;
}
}
wascleanは、vnodeのvp_numoutputという属性が0のときセットされている。このメンバー、この先のページの書き出しを開始するところで増やされているが、ここに来る時点で必ず0なのだろうか。dirtygenは、genfs_do_putpages()の最初のところでvnodeの同名の属性からコピーしている。この属性は、genfs_markdirty()というところで増やされている。dirty generationと思われ、ページを書き出している裏で同一ファイルの別なページでwrite faultが発生したりすると、gp->g_dirtygen == dirtygenの条件が外れる。この場合、後の処理でこのvnodeをsyncerの対象から外す処理がなされないので、確かにこれで良さそうだ。
怪しいながら、NetBSDもwrite fault時にページの書き込みを許可すると同時にこれをダーティとし、これを書き出す際に再度read onlyにしているらしいことがわかった。ただ、あるファイルのページキャッシュのうち、具体的にどのページがダーティなのかを判断するのに、D bitを活用している。
長くなったので、本稿はここまで。次稿では、あと2つ見て最終回の予定。LinuxとNetBSDという出自の異なる2つのOSが、同じ方式を取っていた。これが主流ということなのか、他の方式のOSもあるのか、お楽しみに。