はじめてのOSコードリーディング UNIX V6で学ぶカーネルのしくみが面白すぎたので備忘録。
今回は2章 プロセス、3章 プロセスの制御、7章 ブロックデバイスサブシステム、9章ファイルシステムを対象に書いていきます。
読み方
上記の書籍＋ソースコードを以下からダウンロードしてIntelliJとかで開いて関数や変数を検索しながら読むのが良いです。ダウンロードするのはv6root.tar.gzです。$ mkdir v6
$ wget http://minnie.tuhs.org/Archive/PDP-11/Distributions/research/Dennis_v6/v6root.tar.gz
$ tar xzf v6root.tar.gz -C ./v6
また実際にOSをMAC上で動かす場合は以下を参考にすると良いです。
以下コードを読む際の注意点になります。- UNIX V6のCコンパイラではCの関数は先頭にアンダースコアのついたラベルに変換される。例えば、fork()関数に相当するラベルは_fork:となる。
- 演算代入は”ep=“の形式ではなく”=ep”の形式となる。
- キャストできないので無名構造体を使ってメモリ上の値を取得している。
MMUのアドレス変換
- MMUは仮想アドレス=>物理アドレスの変換やアクセス権限の管理を行う機構。
- プロセス側は仮想アドレスを利用することで、プログラムは物理アドレスを考慮する必要がなくなる。スワッピング処理で物理アドレスが変更されたときもプログラムは仮想アドレスだけ意識していれば良い。また、他のプロセスのメモリ空間にアクセスすることが出来ないのでセキュアであることも利点。
- MMUはAPRと呼ばれるPARとPDRの2つ1組のレジスタを利用しており、PDP-11/40の場合は、カーネルAPR、ユーザAPRがそれぞれ8セットずつあり、それぞれカーネルモード、ユーザモードで利用するAPRが切り替わる。
- PARは物理アドレスのベースアドレス、PDRは各ページのブロック数やアクセス可否などの情報を保持する。
- 仮想アドレスの上位3bitで利用するAPRが変わる（8つのAPRの内どれを利用するか）
- 物理アドレスはブロックNo＋ブロックオフセットで管理されており、仮想アドレスも6-12bitはブロックNo、0-5bitはブロックオフセットを指し、APRはベースブロックNoを管理している。よって物理アドレスは以下の要素で決定する。
- 6-17bit => APRのベースブロックNo＋仮想アドレスのブロックNo
- 0-5bit => 仮想アドレスのブロック内オフセット
- カーネルがグローバル変数0140000(8進数表記)で実行プロセスのuser構造体にアクセスできる。これは、カーネルAPRをのPAR6の先頭アドレスにuser構造体のアドレスをセットしているから。具体的にはswtchで呼び出されるretu(proc.p_addr)で行われる
- KISA6＝カーネルPAR6のアドレスなので、これにproc.p_addrをセットする。
- 0140000はPAR6の先頭アドレスなのでproc.p_addrの先頭＝PPDA＝user構造体にアクセスできる、ということ。
プロセス
基本的にプロセスは親プロセスからのforkによって作成される。PID=0のスケジューラプロセスだけはカーネル起動時にforkを使わずに作成される。PID=1のinitプロセスはforkシステムコールではないが、newproc()でプロセスがコピーされ、execシステムコールで/etc/initのコードを実行するので実質fork+execと同じ作成フローである。- Cライブラリのfork内でカーネルのfork()を呼び出す
→カーネルのfork()で空きプロセスがあればnewproc()を呼び出す
- 親プロセスのカーネルfork()はr0に子プロセスのIDをセットするため、Cのforkの戻り値は子プロセスのIDとなる
- 子プロセスのカーネルfork()はr0に親プロセスのIDをセットし、Cのfork内で_par_uidにr0の値をセットするとともにr0をリセットするため、Cのforkの戻り値は0となる。
- fork後は親プロセスと子プロセスでテキストセグメントを共有する
- データセグメントはnewproc時にメモリを確保してコピー（COWではない）
- fork後swtchがかかる（wait=>sleep=>swtch）と、newproc内でsavu()してるのでswtchのretu()から返る先はnew_procの戻る場所になる。
- sleep時やsetpriで優先度変更後のクロック割り込みでswtchする場合は、savu(u.u_rsav)でユーザ構造体に退避された後、プロセス番号0のスケジューラにコンテキストが変わってコンテキストスイッチ処理を実行する（retu(rp->p_addr)）が、子プロセスの場合はnewproc内でsavuするので、子プロセスが復帰する場所が違う
- sleepはリソースに対する待ちの用途で利用される。そのためsleepには引数にリソースを指定する必要がある。
- I/Oであればブロックデバイスバッファに対する待ち
- I/Oの場合、IO_DONEになった直後に待ちのプロセスをSRUN状態に復帰（wakeup => setrun）させて、次のプロセススケジューラの切り替え対象にする。ブロックデバイスのI/O待ちの場合は、wakeupのリソースはブロックデバイスバッファの変数のアドレスとなる。
- waitの場合、親プロセスがwait()を実行すると親プロセスはsleepする。子プロセスがexitすると親プロセスをwakeupし、wakeupした親はwait関数内で子プロセスを処理する。リソースは親プロセスの変数のアドレスとなる。
ブロックデバイス
- ブロックデバイスに対するアクセス処理はブロックデバイスサブシステムに集約される。ブロックデバイスサブシステムはバッファを用いてブロックデバイスとデータのやり取りを行う。
- ブロックデバイス内のデータはブロック番号で管理され、各ブロックデバイスはデバイス番号で管理される。
- バッファはデバイス番号とブロック番号を管理する（デバイス番号とブロック番号で一意になる）
- バッファを用いる理由は、複数のプロセスからの同時アクセス時の整合性を保つこと（排他処理）と、ブロックデバイスのキャッシュをバッファに載せることで性能を改善するため（ブロックデバイスIO＜メモリIO）。バッファを利用することで先読みや遅延書き込みによる性能改善もできる。
- メジャー番号→デバイスの種類を表し、デバイスドライバを決定
- マイナー番号→接続しているデバイスごとに振られる番号
- バッファはb-list、av-listの二重リンクリストで管理される（bはbusy、avはavailableの略称）
- b-listの先頭は各ブロックデバイスドライバテーブルbdevsw[]のd_tabで指定されるdevtab構造体
- av-listの先頭はbfreelist。未割り当てのバッファ（NODEV）のb-listの先頭もbfreelist。
- binit()によって全てのバッファはbfreelistのb-listに属し、かつB_BUSYがクリアされた状態のav-listにも属する。
- 初回は各ブロックデバイスドライバテーブルのb-listには何のバッファも属さない状態
- getblk()の初回アクセス時にb-listのバッファをbfreelistからブロックデバイスドライバに移動し、av-listからも切り離してB_BUSYフラグを付与する。
- ブロックデバイスの処理をiowait()で待つ。iowaitはバッファにB_DONEフラグが立つまでsleepする。sleepのリソースはブロックデバイスバッファのアドレスとなる。
- ブロックデバイスの処理が完了時にiodone()内でバッファにB_DONEフラグが立ち、iowait()の待ちが解除される。
- プログラム側で、ブロックデバイスバッファの読み込みが完了したら、brelse()を実行してバッファのB_BUSYフラグを解除しav-listの最後尾に追加する。
- この直後、同一ブロックデバイスバッファ（デバイス番号、ブロック番号）にアクセスすると、av-listから外され、B_BUSYとなる。既にB_DONEのフラグが立っているため、bread()ではバッファの内容をそのまま返す（キャッシュが効く）
- このようにして初回はbfreelistからブロックデバイスにb-listが移動していく。移動対象はbfreelist.av_forw（av-list）となる。bfreelistに属していたb-listが無くなり一巡すると、ブロックデバイスからブロックデバイスにb-listが移動することになる。
- av-listが枯渇した場合は、bfreelistにB_WANTEDのフラグを立てて、bfreelistに対するsleepを行う。この場合、brelseでav-listに戻すタイミングでbfreelistに対するwakeupが行われる。
- NODEVのバッファ（bfreelistのb-list）は以下の用途で利用される。
- ルートデバイスや、マウントしたデバイスのスーパーブロックの情報の格納先
- exec()時の引数処理の一時バッファ
- 読み込みも書き込みも基本的には同じ原理だが、書き込みに関しては遅延書き込みという概念がある。これは書き込み呼び出し時にはブロックデバイスドライバを呼び出さず、後で一括で書き込みを行う（bflush）
- 遅延書き込みのバッファがgetblk()内で移動対象のbfreelist.av_forwで選択された場合は、非同期の書き込みを行い、次のバッファが移動対象に選択される（遅延書き込みのバッファはnotavailで対象から除外される）
- B_ASYNCによるバッファの先読みや非同期書き込みが行われる。非同期の場合は、iodoneのタイミングでbrelseされる。
ファイルシステム
- スーパーブロック情報はfilsys構造体で定義される。
- マウントポイントとマウントされたデバイスはmount[]で管理される
- mountシステムコールでは空いているmount[]を探して、スーパーブロックの情報をmount[]にコピー
- マウントポイントのinodeを取得してIMOUNTフラグを追加
- inodeはファイル情報を格納している。inode番号、ディレクトリからの参照数、ユーザID、グループID、ファイルサイズ、ストレージ領域のブロク番号、更新時刻等が管理される。ファイル名は管理されないことに注意（ディレクトリのブロックで管理される）
- ブロックデバイスに格納されるinode構造体とメモリに格納されるinode構造体は異なる。具体的にはブロックデバイス上では参照カウンタ、デバイス番号、inode番号（構造体中では管理されない）などが格納されていない。よって利用するときにそのまま利用せずに変換をかける必要がある。
- iget()はinodeを取得するインターフェース。inode[]のキャッシュ上にあれば参照カウンタをインクリメントして返す。なければブロックデバイスから読み込み。マウントポイントであればマウントしたデバイスのデバイス番号とROOTINOのinode番号として再検索する。
- ストレージへのマッピングはbmap()によって行われる。
- 直接参照（ブロック番号を指定）、間接参照（ブロック番号が書いてあるブロックを指定）、二重間接参照（間接参照のブロックのブロック番号が書いてあるブロックを指定）の３種類存在する
- ILARG=0 => 全て直接参照（0〜7）=> 8 * 512byte=4KByteが最大ファイル容量
- ILARG=1 => 間接参照（0〜6）＋二重間接参照（7）
- １つの間接参照ブロック内に256個のブロック番号が格納されるので、256 * 7 * 512byte = 896KByteが最大ファイル容量。
- 二重間接参照だと256個の間接参照ブロックを使うことになるので、256 * 256 * 512byte = 32MByteが理論的な最大ファイル容量。UNIX V6ではファイルサイズを24bitで管理している（i_size0、*i_size1）ので2^24=16MByteが最大ファイル容量となっている。
- 正確な計算方法（(ByteOffSet/512)%256=）
- bmapは論理ブロック番号（バイトオフセットを512で割った値）を物理ブロック番号（実際に格納されているブロック番号）に変換する関数
- スーパーブロックでは未割り当てのinodeとストレージ領域（ブロック）を管理している
- filsys.s_inodeは未割り当てのinode。filsys.s_ninodeはs_inodeのスタックポインタ。s_ninodeが0になるとブロックデバイスから空いているinodeを取得してs_inodeにセットする。空いているinodeの取得方法は線形検索。
- ifreeでinodeが解放されるとs_inodeに補充されるが、s_inodeが満杯だったときは補充されない。
- 未割り当てのストレージ領域に関しても同様にs_freeとs_nfreeで管理される。
- 未割り当てのストレージに関しては、補充のロジックがinodeと大幅に異なる。フリーリストは予め複数のブロックで管理されており、各ブロックでの構成は[フリーリストの数を表す領域（nfree）] + [次のリストのブロック番号] + [空き領域のブロック番号*99]となっている。未割り当てのストレージ領域が枯渇した場合は、[次のリストのブロック番号]から次の空き領域のストレージ番号リストを取り出す（先頭の値のnfreeもセット）
- ディレクトリはinode番号(2byte)＋ファイル名(14bytee)のエントリを管理するファイル。
- namei()は名前からinodeを検索する（inodeが確定すればファイル内容やアクセス権限を取得できる）
- 相対パスであればカレントディレクトリのinode、絶対パスであればルートからディレクトリをたどる。
- スラッシュからスラッシュ、あるいはスラッシュから\0までのファイル名、ディレクトリ名を取り出す
- 取り出した名前のファイルがディレクトリ内に存在するかをファイル名の完全一致検索する（ディレクトリに格納されている全てのファイルを線形検索）
- /hoge/となっているのにhogeがディレクトリじゃなければNG。ディレクトリであっても実行権限がなければNG。
- cp[u.u_dent.u_name - u.u_dbuf] は u.u_dent.u_nameのx番目の文字を表す
