前々回は、概要を述べて、mmap域への書き込みの検出方式として大きく2通り、細かくは3通り (1a ページテーブルスキャン方式、1b 物理ページスキャン方式、2 write fault捕捉方式) を予測した。前回は実際にLinuxとNetBSDのソースコードを見て、いずれもwrite fault捕捉方式を取っていることを確かめた。本稿では、あと2つのOS、macOSとSolarisを調べる。
macOSの場合
macOSは、NeXTSTEP (OpenSTEP) を元に開発されているが、NeXTSTEPは、CMUのマイクロカーネルであるMach 2.5の上に構築されていた。マイクロカーネルでは、必要最低限の機能のみをカーネルに実装し、ネットワークスタックやファイルシステム、プロセス管理などの機能はユーザースペースで動くサーバ (サブシステム) で実装することになっている。ただ、純粋なマイクロカーネルでは、仮想空間の切り替えやコンテキストスイッチの頻度が高くなることから、性能上の問題を抱えることが多く、サブシステムの機能もカーネル空間に実装することが多い。これをがハイブリッドカーネルという (Windowsもハイブリッドカーネルに分類される)。Machは、当時の標準といえた4.3BSDとの互換性を確保するため、4.3BSD由来のコードを大量に内包しており、マイクロカーネル部と同一のアドレス空間で動く、単一のバイナリとなっていた。つまり、ハイブリッドカーネルに分類される。macOSはMach 2.5 + 4.3BSDであったNeXTSTEPのカーネルを、OSF/1のマイクロカーネル + FreeBSDに、それぞれ更新した形になっているようだ。OSF/1の名残は、ソースツリーのうちMach部分が格納されているディレクトリ名osfmkに現れている。Unixコマンド群なども、FreeBSDがベースとなっているようだ。
macOS全体はOSSではないが、カーネル (XNU) を含むMach/FreeBSD由来部分などは、Darwinという名でOSSになっている。githubにミラーがあるので、これを参考にしてみるが、ファイルシステム (APFS、HFS+) が含まれないので隔靴掻痒感がある。
NetBSDのかつての仮想メモリシステムがMachベースであったことは触れた。UVMもMach仮想メモリシステムの影響を受けて設計されており、XNUの仮想メモリシステムと似ている部分も多い。例えば、D bitを参照するのはNetBSDと同じくpmap_is_modified()で、pmap_clear_modify()もNetBSDと同じ働きをする。他に、pmap_get_refmod()、pmap_clear_refmod()など、A bitとD bitを一気に操作するインターフェイスもある。A bitとD bitを同時に操作するとは、これはLinuxやNetBSDとは違ってページテーブルのスキャンによってダーティページを探すのではなかろうか。早速みてみよう。
ページテーブルのスキャン
XNUの仮想メモリシステムは、osfmk/vmというディレクトリにあるようだ。Mach部分はosfmk、BSDサブシステム部分はbsdというディレクトリに格納されており、bsd/vmというディレクトリもある。bsd/vmには、vnode pager (NetBSDのvnode pagerと同等) などBSDサブシステムに依存する部分が実装されている。
osfmk/vmのデータ構造を見てみると、struct vm_map、struct vm_map_entry、struct vm_pageなど、NetBSDで見たような構造体があったり、vm_pageがlistq、pageqでリストにつながっていたりと、同根であることを匂わせる。
pmap_is_modified、pmap_clear_modify、pmap_get_refmod、pmap_clear_refmodなどでgrepすると、vm_pageout.cやvm_resident.cあたりがひっかかるので、この辺りと思われる。が、信じられないほど長いブロックがあったり、やたら状態の数 (struct vm_pageのフラグ) が多かったりしてだいぶ理解が難しい。
pageqを介して繋がるキュー (リスト) が多いのは、特徴のひとつと思われる。基本的にはactive/inactive/freeのリストの間でページを移動したり順序を変えたりしているようだが、各リストが幾つにも分かれている。
- activeリスト
- vm_page_queue_active -- メインのactive list
- vm_page_local_q[] -- CPUローカルのactive queue。ページフォルトで新規に確保されるとここに登録されるようだ
- inactiveリスト
- vm_page_queue_inactive -- ページキャッシュ
- vm_page_queue_anonymous -- 匿名メモリ
- vm_page_queeu_cleaned -- ダーティではないページ、ということだが、当然ながらいつの間にかダーティになる、ということはあり得そう
- freeリスト
- vm_page_queue_free[] -- キャッシュカラーごとのfreeリスト
- vm_lopage_queue_free -- 空きが少なくなった緊急時用に確保されているfreeリスト
- その他
- flush待ちリスト -- vm_pageout_queue_internal (匿名ページ)、vm_pageout_queue_external (ファイルキャッシュ)、vm_page_queue_throttled
- vm_page_queue_secluded -- カメラなど 向けに隔離されたメモリ (?)
- vm_page_queue_background -- バックグラウンドプロセス用のリスト。これは、vm_pageにpageqとは別に用意されたvmp_backgroundqというリンクを介して繋がるので、他のリストと同時に繋がれることになる
こうして多くのリストに分けることで、スキャンのタイミングや頻度を、ページの使用状況によって細かく制御することができそうだ。
active/inactiveの各リストのスキャンはカーネル初期化後のコンテキストでそのまま行われるようだ。本体は、vm_pageout_scan()という1500行近くある長大な関数にある。この中 (たとえばこの辺り)でA bitとD bitの両方を同時に見て、D bitがセットされていればページをダーティとしている。
if (m->vmp_reference == FALSE && m->vmp_pmapped == TRUE) {
refmod_state = pmap_get_refmod(VM_PAGE_GET_PHYS_PAGE(m));
if (refmod_state & VM_MEM_REFERENCED)
m->vmp_reference = TRUE;
if (refmod_state & VM_MEM_MODIFIED) {
SET_PAGE_DIRTY(m, FALSE);
}
}
また、ページフォルトを処理するvm_fault()をざっと追いかけても、write fault時にはエラー (SEGVなど) かCopy on Writeしかなさそうである。
以上より、macOSの場合は、ページテーブルのA bitの検査と同時にD bitを検査することによってダーティを検出する、物理ページスキャン方式を取っているらしいことがわかった。
OpenIndianaの場合
SunOS (Solaris: 厳密にはSunOSとSolarisが指す範囲は違うようだが細かいことは気にしない) といえば、一時期はThe Unixといえる存在で、あらゆるUnix系OSに影響を与え続けてきたOSだった。Linuxも2.6あたりまではSunOSを目標にしていたと思う。この分野でも、たとえばmmap(2)に使うページキャッシュとread(2)/write(2)に使うバッファキャッシュを最初に統合したのがSunOS 4である。
そのSunOSは、5.10 (Solaris 10) の頃一度OpenSolarisとしてソースコードを公開した。ライセンスはCDDLで、GPLとの互換性はないものの、OSSであった。当時は製品のSolarisもOpenSolarisをベースとしていたようだが、SunがOracleに買収されると、Sun (Oracle) 主導によるOpenSolarisプロジェクトは終了してしまった。
OpenSolarisの最後の版から派生したOpenIndiana は現在も開発が続けられているので、これを調べてみたい。カーネルを含むillumos-gate部分のうち、最新リリースOpenIndiana Hipster 2020.04に対応するcommitを参考にする。カーネルはusr/src/utsにある。Unix Time-sharing Systemかな。x86依存部はuts/i86pc、アーキテクチャ非依存部はuts/commonにある。
ページテーブルのスキャン
仮想メモリシステムのうち、機種依存部は、HAT (hardware Address Translation) 管理というようだ。x86の場合は、uts/i86pc/vm/hat_i86.cにある。仮想空間ごとにhat_t (struct hat) が対応するなど、pmapとよく似ている。PTEのD bitに対応するPT_MODをキーに斜め読みすると、以下のことがわかる。
- PTEのD bitやA bitを直接参照するようなインターフェイスはなさそう
- D bitやA bitの情報を、struct pageのp_nrmというメンバーに同期 (コピー) するhat_sync()、hat_pagesync()などのようなものはある
- p_nrmを返すhat_page_getattr()というものもある
hat_pagesync()は、引数としてstruct page (物理ページに対応: したがって、複数のPTEが対応する) とビットマップのフラグを取り、ある物理ページを参照するPTEのA bit、D bit、R/W bitをstruct pageのp_nrmに反映させる。フラグとして、
- HAT_SYNC_ZERORM: 合わせて、A bit、D bitをクリアする。
- HAT_SYNC_STOP_ON_REF: A bitがセットされているPTEを見つけたら、そこでおしまい。
- HAT_SYNC_STOP_ON_MOD: D bitがセットされているPTEを見つけたら、そこでおしまい。
- HAT_SYNC_STOP_ON_RM: A bitかD bitがセットされているPTEを見つけたら、そこでおしまい。
- HAT_SYNC_STOP_ON_SHARED: ある程度以上の仮想空間から共有マップされているようならおしまい。またページがread onlyならA bitを立てる。
のビットマップを取る。HAT_SYNC_STOP_ON_SHAREDの意味合いはよくわからないが、多くの仮想空間から共有されているページを優遇する感じかな。
/*
* get hw stats from hardware into page struct and reset hw stats
* returns attributes of page
* Flags for hat_pagesync, hat_getstat, hat_sync
*
* define HAT_SYNC_ZERORM 0x01
*
* Additional flags for hat_pagesync
*
* define HAT_SYNC_STOPON_REF 0x02
* define HAT_SYNC_STOPON_MOD 0x04
* define HAT_SYNC_STOPON_RM 0x06
* define HAT_SYNC_STOPON_SHARED 0x08
*/
これに留意して、ページテーブルのスキャンを行うコードを見る。仮想メモリシステムの機種非依存部は、uts/common/vmにあるが、ページテーブルをスキャンするコードはなぜかuts/common/osにある。お、なぜかmacOSと同じファイル名だ。実は、FreeBSDにもUVM化する前のNetBSDにもあるので、そんなもんかも知れない (なおmacOS、FreeBSD、NetBSDのvm_pageout.cはあきらかに同根である)。
OpenIndiana、というか、Solarisのソースは、コメントが多く読み易い。ページ置換はpageout_scanner()というところで、これは専用のカーネルスレッドで実行されている。Clockアルゴリズムを実装しているようだが、今までに見た他のOSとは違ってinactiveリストはなく、単一のリストを使っているようだ。handというのは時計の針の意味で、fronthandとbackhandの2本の針が一定間隔 (handspreadpages) をあけて物理ページ (struct page) のリストを辿っていく感じだ。
checkpage()というのがポイントのようだ。基本的には、fronthandがD bit、A bitをクリアし、後を行くbackhandがA bitをチェックする感じのようだ。
/*
* Turn off REF and MOD bits with the front hand.
* The back hand examines the REF bit and always considers
* SHARED pages as referenced.
*/
if (whichhand == FRONT)
pagesync_flag = HAT_SYNC_ZERORM;
else
pagesync_flag = HAT_SYNC_DONTZERO | HAT_SYNC_STOPON_REF |
HAT_SYNC_STOPON_SHARED;
ppattr = hat_pagesync(pp, pagesync_flag);
で、A bitがセットされているとなにもせず戻り、D bitがセットされていると、queue_io_request()を呼び出して、書き出しを依頼。どちらもセットされていなければページをアンマップして開放する。
以上から、OpenIndiana、というか、ある時期のSolarisは、物理ページスキャン方式を取っていることが分かる。
4.4BSDの場合
ここまで見てきて、同根に見えるNetBSDとmacOSとで異なる方式を取っている、またある時期までの規範であったSolarisと、LinuxやNetBSDが異なるというのを見て、いつぐらいに異なる方式をとるようになったのか、歴史が気にならなかっただろうか。
昔からUnixを使っている人なら、昔はupdate(8)というデーモンがいて、30秒に一度sync(2)というシステムコールを発行していたのを覚えているかもしれない。write(2)などによる書き込みも、カーネルが自動的に書き出すことはなく、fsync(2)などを発行するか、最大30秒後にupdate(8)が書き出すのを待つかしなければならなかった。おそらく、mmap(2)されたファイルも同じだったのではないだろうか。
たとえば、NetBSDとmacOSの共通の祖先 (macOSの方は祖先の一つ) である4.4BSDのソースコードは、Webで閲覧できる。macOSでactive/inactiveのたくさんのリストをスキャンしていたvm_pageout.cは、4.4BSDではこんなに単純だ。ここでは、D bitは見ていない。また、ページフォルトのコードは、write faultではCopy-on-Writeするばかりだ。それどころか、ここで定義されているsync(2)では、(この頃は、ページキャッシュとバッファキャッシュは統合されていなかったにもかかわらず) バッファキャッシュしかフラッシュしておらず、mmapで使われるページキャッシュは手付かずである。
ページキャッシュがフラッシュされるのは、msync(2)を発行した時と、munmap(2)やプロセス終了などのときだけのようだ。NetBSDの場合、sync(2)でページキャッシュをフラッシュするようになったのは、1997年2月になってからのようだ。
この後はザッとしか追いかけていないが、Mach VMが消された時点でもUVMが導入されたときでも同じ状況に見える。どうやら、バッファキャッシュとページキャッシュが統合されたときwrite faultを捉えるようになったらしい。
FreeBSDの方は、法的な問題で2.0-RELEASE以前の歴史が失われている。2.0ではすでにwrite faultを捕捉してダーティにしているようなので、こちらもいつ現在の方法になったのか、簡単にはわからない。LinuxもVCSを変更したせいで、2.6.12以前の履歴を辿るのはだいぶめんどくさい。手元にあった2.4.20ではwrite fault時にダーティにするコードがあった。
まとめ
ということで、一般にBSD系と呼ばれるmacOSはNetBSDとは異なり物理ページスキャン方式、またかつて各種Unix系OSの規範となっていたSolarisも物理ページスキャン方式とわかった。歴史を辿ると、少なくとも4.4BSDではページキャッシュを自動的にフラッシュすることはなく、祖先として4.3BSD (とFreeBSDの両方) を持つmacOSと、4.4BSDの子孫であるNetBSDとで違う方式であっても、まったく不思議はない。