オーバレイカーネル
オーバーレイ機能にあてた労力を動的コア割り当てと動的相互参照（リンク）機能の高速化に費やしていたら、どれほど早い素晴らしいシステムになっていたことか。
ーーフレデリック・P・ブルックス，Jr
カーネルソースツリー構造
/sys以下にカーネル関連のコードがまとめられている。総行数は9万行弱。以下にその内訳を示す。
- /sys/sys: マシン独立コード (27382)
- /sys/h: マシン独立ヘッダファイル (6378)
- /sys/conf: コンフィグレーションファイル
- /sys/net: ネットワーク共通コード (2480)
- /sys/netinet: DARPAインタネットコード (8756)
- /sys/netimp: IMPサポートコード (1343)
- /sys/netns: Xerox NSサポートコード (5210)
- /sys/pdp: PDP-11機種依存コード (12129)
- /sys/pdpif: PDP-11ネットワークインタフェースコード (9735)
- /sys/pdpmba: PDP-11 MASSBUSデバイスドライバ (0)
- /sys/pdpuba: PDP-11 UNIBUSでバイスドライバ (15253)
手元の4.3BSD版悪魔本を見る限り、マシン独立部は似たような感じになっていると思われる。デマンドページ方式の仮想記憶はないので、その部分は違うが。あと、TCP/IP部分のコードリーディングはTCP/IP Illustrated Vol. 2が参考になりそう。またちょっとマニアックなところで、IMP (Interface Message Processor)とのインタフェースが面白いかも。IMPに関する日本語の説明としては、こことか。
カーネル再構築（失敗）
BSDでカーネル再構築したことのある人なら、基本的に手こずることはないと思うのだが、一点カーネルサイズが問題になる。まぁ、とりあえずやってみよう。/sys/conf/GENERICがデフォルトのコンフィグレーションファイルである。今回SIMH用に使ったディストリビューション用にカスタマイズされたコンフィグレーションがSYSTEMなので、これをベースにする。
# cp SYSTEM MYKERNEL # ./config MYKERNEL Creating ../MYKERNEL. Copying standard files to ../MYKERNEL. Setting configuration options for MYKERNEL. Creating device header files. Creating Makefile for MYKERNEL.
configスクリプトを実行すると../MYKERNELに必要なファイルが準備されるので、makeすればよい。
# cd ../MYKERNEL # ls Make.net acc.h dmc.h hy.h pty.h sl.h Make.pdp boot.s dn.h il.h qe.h sri.h Make.pdpmba br.h dr.h imp.h qt.h tb.h Make.pdpnet cn.h dz.h ingres.h ra.h tm.h Make.pdpuba css.h ec.h ioconf.c ram.h tms.h Make.sys de.h en.h localopts.h rk.h ts.h Makefile dh.h ether.h loop.h rl.h vv.h NETSPLFIX dhu.h hk.h lp.h rx.h xp.h SPLFIX dhv.h ht.h param.c si.h # make
しかし、unix.oをldするところでコケてしまった。
ld -q -r -d -X -i -o unix.o scb.o mch_backup.o (snip) enable34.o vers.o -lkern param.o d.unix.o ld: too big for type 431 *** Exit 2 Stop.
何が起きているのだろうか？
PDP-11のソフトウェアオーバレイ
この問題を解決する前に、その背景を考えてみる。
PDP-11の仮想アドレス空間は16ビット、すなわち64KBである。PDP-11は仮想記憶を実現できないので、その空間内にカーネルを収める必要がある。これは特にネットワーク機能に対応する際の大きな問題となっていた。そこで、導入されたのがソフトウェアオーバレイ技術である。もちろんオーバレイは本質的な問題解決にはならないので、これがVAX-11開発の大きなモチベーションとなった。
ここでまずPDP-11のMMUアーキテクチャについて軽く紹介しておく。PDP-11はセグメンテーションアーキテクチャを採用しており、仮想アドレス空間は8KBのセグメントが8つから構成される。セグメントのセットはユーザモードとカーネルモードそれぞれに存在する*1。さらに一部の後発機種では、命令(I)空間とデータ(D)空間を分離し、アドレス空間を2倍にする機能を持っていた。この場合、PCレジスタ経由で参照したアドレスは命令空間用のセグメントを利用し、それ以外はデータ空間用のセグメントを参照する。I/D空間が分離されているとしても、テキストサイズを64KBに収める必要がある。これらのマッピングはPAR（Page Address Register）とPDR（Page Description Register）のレジスタの組で設定する*2。
オーバレイとは、プログラムを複数の部分に分割し、必要な断片のみをメモリにロードし、実行する技術のことである。これをハードウェアが自動でやってくれれば仮想記憶になるのだが、これをプログラマが管理する必要があるのである（つまり面倒くさい）。
2.11BSD実装（UNIX V7でも同じ？）では、アドレス空間をベースの56KBとオーバレイの8KBに分離し、必要に応じてオーバレイ部分を切り替えるということを行っているようだ。ベースとオーバレイに何を割り当てるのかはMakefileに記述されている。オーバレイは最大15個で、現状では9個使われている。
BASE= br.o cons.o dh.o dhu.o dhv.o dr.o dz.o hk.o ht.o init_sysent.o \
kern_clock.o kern_descrip.o kern_mman.o kern_proc.o kern_prot.o \
kern_prot2.o kern_subr.o kern_synch.o lp.o machdep.o ra.o ram.o \
rk.o rl.o rx.o si.o subr_rmap.o sys_inode.o sys_kern.o \
tm.o ts.o tty.o tty_conf.o tty_subr.o tty_tb.o ufs_alloc.o \
ufs_bio.o ufs_fio.o ufs_inode.o ufs_namei.o \
vm_proc.o vm_sched.o vm_swap.o xp.o quota_subr.o
OV1= sys_generic.o ufs_syscalls.o vfs_vnops.o
OV2= kern_acct.o kern_exec.o kern_exit.o kern_fork.o kern_resource.o
OV3= kern_time.o sys_process.o ufs_mount.o ufs_subr.o uipc_syscalls.o
OV4= dkbad.o kern_sig.o mem.o subr_xxx.o trap.o tty_pty.o tty_tty.o
OV5= quota_kern.o quota_ufs.o quota_sys.o ufs_bmap.o \
sys_pipe.o
# OV6 gets the (hopefully) never used routines
OV6= clock.o dn.o init_main.o kern_pdp.o machdep2.o subr_prf.o syscalls.o \
subr_log.o toy.o vm_swp.o
OV7= ufs_disksubr.o ufs_dsort.o ufs_syscalls2.o kern_sig2.o
OV8= mch_fpsim.o kern_sysctl.o kern_xxx.o ingreslock.o vm_text.o
OV9= tmscp.o tmscpdump.oさて、"ld: too big for type 431"というエラーメッセージの意味であるが、type 431はa.outのフォーマットがsplit I/D overlaid executableで、ベースもしくはオーバレイセグメントが大きすぎるということを示している。では、unix.oのテキストサイズを見てみよう。
# size unix.o
text data bss dec hex
56448 6340 41960 104748 1992c total text: 108224
overlays: 7744,7488,7872,7296,2240,8448,4992,5696ベースは56448で56KB(57344)に収まっているが、6番目のオーバレイ（OV6）が8KBを超えている。ということで、Makefileを編集して、OV6のオブジェクトファイルを他のオーバレイに移す必要がある。例えば、toy.oのテキストサイズは482なので、これをOV7などへ移せば問題は解決できる。
もう少し詳しいオーバレイ実装の話
カーネルがmakeできればよい人は飛ばしてもらって結構だが、カーネルのオーバレイをどのように実装しているか少し追ってみた。
Cの関数のプロローグ、エピローグ処理を行うcsv/cretルーチンに仕掛けをするようだ。逆に言うとアセンブリルーチンはオーバレイされないベースセグメントに配置する必要がある。
関係するソースコードは、/sys/pdp/mch_csv.s。まずはオーバレイとは関係なく素のcsvの動きから見てみる。csvはC register saveのことで、Cの関数の先頭で必ず呼ばれ、次のようにスタックフレームをセットアップする。先日示したアセンブリでもmainラベルの直後にjsr r5,csvが現れていた。
_________________________________
| return address to caller |
|-------------------------------|
r5-> | old r5 ("frame pointer") |
|-------------------------------|
| previous __ovno |
|-------------------------------|
| old r4 |
|-------------------------------|
| old r3 |
|-------------------------------|
| old r2 |
|-------------------------------|
sp-> | empty parameter slot |
|_______________________________|オーバレイを実現するには、（メモリ上に常駐している）ベースセグメント上のラッパー関数からオーバレイセグメントの実関数を間接呼出しできるようにし、その過程でオーバレイセグメントの切り替え処理をできるようにすればよい。このラッパー関数のことをthunkと呼ぶ。
thunkを作るのはldの仕事である*3。thunkはベースセグメントに存在し、オーバレイ上の関数をオーバレイハンドラ経由で実行する。例えば、fooというCの関数（アセンブリのシンボルは_foo）があった場合、thunkである_fooは次のようなルーチンになる（実際の`n'はオーバレイ番号になる）。そしてオーバレイ上のシンボル_fooは~fooに置き換えておく。オーバレイハンドラ（ovlhndlr(1-9,a-f)）はcsvの動作をシミュレートし、r1（つまりcsvへのjsr命令の次の番地）に戻る。
_foo: mov $~foo+4,r1
jsr r5,ovlhndlr`n'現在のオーバレイ番号はグローバル変数__ovnoに記録されている。オーバレイハンドラでは、関数呼出し時のオーバレイ番号と呼ばれた関数のオーバレイ番号が異なる場合は、__ovnoを更新し、オーバレイセグメントのPAR（Page Address Register）とPDR（Page Description Register）を設定する。これでセグメントのマッピングは切り替わる。PARとPDRの詳細はこことか。
関数呼出しは複数のオーバレイをまたがるかもしれないので、関数から復帰する際には、適切なオーバレイがマッピングされているように戻す必要がある。そのために、呼出し元のオーバレイ番号（previous __ovno）をスタック上に保存している。cretルーチンでは、オーバレイセグメントからの呼出し（previous __ovno != 0）で、かつその値と現在のオーバレイ番号（__ovno）が異なる場合、オーバレイセグメントを切り替える。
カーネル再構築（リベンジ）
では、カーネルのmakeに戻ろう。
# make
ld -X -i -o unix scb.o mch_backup.o (snip) enable34.o vers.o -lkern param.o d.unix.o
size unix
text data bss dec hex
56448 6338 41960 104746 1992a total text: 108160
overlays: 7744,7488,7872,7296,2240,7936,5440,5696
Compacting symbol table
symcompact unix
symcompact: 264 symbols removed
Compacting strings table
strcompact unix
rearranging symbols
symorder ../pdp/symbols.sort unix
./checksys unix
System will occupy 1271712 bytes of memory (including buffers and clists).
end {0136252} nbuf {0014240} buf {0064252}
nproc {0014226} proc {0105146} ntext {0014230}
text {0134712} nfile {0014234} file {0130422}
ninode {0014232} inode {0014460} ncallout {0014236}
callout {0053404} ucb_clist {0014244} nclist {0014242}
ram_size {0006006} xitdesc {0014456} quotdesc {0000000}
namecache {0063414} _iosize {0012640} nlog {0013312}
ld -X -i -o netnix net_copy.o net_csv.o (snip) -lkern d.netnix.o
size netnix
text data bss dec hex
60864 2362 38448 101674 18d2a
Compacting symbol table
symcompact netnix
symcompact: 249 symbols removed
Compacting strings table - this will take a few minutes
strcompact netnix
rearranging symbols
symorder ../pdp/symbols.sort netnixこれでunixとnetnixという2つのカーネルイメージが生成できた。netnixはネットワーク関連部分で、カーネル起動中にロードされる（/sys/sys/init_main.cのnetinit関数参照）。このようになっている理由は、ブートローダが192KB以上のサイズ（テキスト＋データ＋BSS）をロードできないからのようだ。
では、カーネルを入れ替える。
# cp /unix /oldunix # cp /netnix /oldnetnix # make install install -c -o root -g kmem -m 744 unix /unix install -c -o root -g kmem -m 744 netnix /netnix # sync
リブート後にuname -aしてみると、カーネル名がMYKERNELになっていることを確認できる。
# uname -a 2.11BSD 2bsd00 2.11BSD 2.11 BSD UNIX #2: Fri Jun 9 16:48:20 PDT 1995 \ root@2bsd00:/usr/src/sys/MYKERNEL pdp11
おわりに
仮想記憶導入以降のUNIXでは、オーバレイが使われることはなくなった。
仮想記憶が当たり前となった今、オーバレイなんて使うのは、非常にリソースが制限された組み込みシステムぐらいかなと思いきや、CELLプログラミングはオーバレイ使うなんて話を聞いたことを思い出した。SPUのローカルストレージは256KBと小さいので、それ以上大きなプログラムを実行する場合は、オーバレイを使う必要があるのだとか。
冒頭の引用に戻ると、「人月の神話」でもセカンドシステム症候群の例として、OS/360のオーバレイ技術の話が出てきていたな。
- 作者: Samuel J. Leffler,Michael J. Karels,Marshall Kirk McKusick,John S. Quarterman,中村明,計宇生,相田仁,小池汎平
- 出版社/メーカー: 丸善
- 発売日: 1991/07/01
- メディア: 単行本
- 購入: 1人 クリック: 11回
- この商品を含むブログ (2件) を見る
- 作者: ゲリー・R.ライト,W.リチャードスティーヴンス,Gary R. Wright,W.Richard Stevens,徳田英幸,戸辺義人
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2002/12
- メディア: 単行本
- 購入: 1人 クリック: 13回
- この商品を含むブログ (25件) を見る
