UNIX_V7のコードを読んでみよう

UNIX Version 7 のカーネルソースについてのコメント

はじめに

古い古い UNIX のコードが公開されてとても嬉しい。せっかく、公開されたんだから、コードを読んでみよう。
コードを読んだからには、コメントを書いてみようというのが趣旨である。
コメントを書いたからといって、だれか他の人になにかを説明できているものではないかも知れない。少しでもわかりやすくというより興味を持ってもらえるように書きたいが... どうなるかわからない。

読むべきバージョンの選定について

他のバージョンもちょっと見てみたが、これはもう文句無しに V7 である。
V7 のカーネルや他のコードは、それ以降の SVR3 あたりまでの原型となっているように思える。コードそのものだけではなく、ソースのディレクトリ構成なども整理され、それ以降のバージョンのベースとなっているようだ。
V7 は、UNIX が生まれ形が整った最初のものと言えそうである。
このカーネルコード。/usr/sys/sys の下の部分は、6272 行しかない。それ以外で重要なものは、/usr/sys/dev の下の tty.c と bio.c か。それを足したとしても 7564 行なのだ。
これだけの行数で、仮想記憶はできないものの、マルチタスク、マルチユーザのカーネルができている。プロセスアカウンティングの機能や、プロセスプロファイラーのための機能まである。非常に密度が高い。
それだけではない。このコードは、BSD や Linux とまったく関係ないものではないのだ。たとえ BSD や Linux で V7 のコードそのものを使っていなくても。
そのことは、いくつかのカーネルを読みくらべてみればわかるはず。 V7 は、現在でも読む価値は十分にあると思う。

とりあえず... もしこれから書く内容について興味がある人がいらっしゃいましたら、読んでいる宣言をしてもらえると、筆が進むかも。本文について間違っているとか捕捉がありましたら、本文の方に直接コメントいれてもらってかまいません。
ただ、古いUNIXのコードの解釈について議論をする...それは何かを生み出すかというと疑問が ... でも、あえて議論したければリンクを張って別のところで。

とりあえずは、ファイルシステムで、整理する必要があるんで、これから。

ファイルシステム

inode

inode の構造は、メモリ上にある形態と disk上にある形態の2つの構造がある。

disk 上のものは、h/ino.h の struct dinode で定義され、メモリ上のものは、h/inode.h の struct inode で定義される。

両 inode は、属性とファイルのデータのありかを示すテーブルを共通に持つ。

inode は、inode 番号といわれる id を持つが、それは自由に決めたものではない。 inode 番号で、disk 上の dinode の場所が特定できる性質を持つ。

ファイルのデータのありかを示すテーブルは、13 個のデータを持つ。最初の 10 個は、ファイルの先頭から 10 ブロックまでの block 番号が直接格納される。11 番目は、そのブロックが指す内容がテーブルになっていて、続くデータの block 番号を格納するようになっている。 12 番目は、テーブルのテーブルになっていて、13 番目はテーブルのテーブルのテーブルになっている。

さて、概要はこれぐらいにして、 inode に対するオペレーションとして次のものあたりから見てみよう。

alloc.c: ialloc(), ifree(), update()
iget.c: iget(), iput() iupdat(), itrunc(), maknode()
rdwri.c: readi(), writei()

ialloc(dev)

ialloc は、disk から dinode を allocate してくるもの。

struct inode *
ialloc(dev)
dev_t dev;
{  ...

という関数定義になっている。dev で示されるファイルシステムから、 disk 上の dinode を割り当て、それに対応するメモリ上の inode を返す。

使っていない inode は、

           fp->s_inode[]

にプールされている。この配列に入っているものは、inode 番号。

使っていない inode がある場合は、そこから inode 番号を得て、

           iget(dev,ino)

により struct inode を得て戻る。

ただし、iget で得てみたら、i_mode が 0 でなかったケースは、iput() で開放して、やりなおす。

それがどういう時おきるのか ... これは疑問だが先に進む。

さて、プールになかったときは ...

inode が格納されているエリア (SUPERB+1 から fp->s_isize まで) を順に見て、空の dinode を見付ける。

こういう構造をしている。空の dinode かどうかという判断は、dnode の di_mode が 0 でなおかつ、メモリ上の inode を全部サーチして使っていないことが確かめられたもの。

これをプールに詰め込んでいく。

disk を読むプリミティブは、bread() -- brelse()。

これは、block device --- キャッシュ付きの block の read で、bread では、 1 block をキャッシュに読んできて、それを管理する struct buf を返す。
bread() すれば struct buf のリファレンスカウントが +1 されるので、 brelse() でリファレンスカウントを -1 して開放する。 brelse() するまでは、struct buf が指すポインタの中に disk のデータがあることが保証される。そういう制御構造になっている。

さて、最初にある

   while(fp->s_ilock)
           sleep((caddr_t)&fp->s_ilock, PINOD);

これは何かというと、いま他のプロセスが、disk から読んできているからちょっと待つというコード。

disk から読むことになれば、 fp->s_ilock++; して、終ったら

    fp->s_ilock = 0;
    wakeup((caddr_t)&fp->s_ilock);

している。

さて、ここで sleep/wakeup が出て来た。sleep は、プロセススイッチをして待つということで、wakeup は、待っているものをすべて起こすというプリミティブ。両プリミティブの第一引数は、ポインタに見えるが、ただの数値として扱う。システムでユニークな ID ならなんでも良い。

sleep の第2引数は、プライオリティ。へたをするとリソース待ちでデッドロックを起こすので、厳格に定められている。

PINOD は、PSWP -- スワップの次に優先度が高い。

ここで、これから sleep するのになぜプライオリティというのを指定するのか ...という疑問を持たれるかもしれない。
カーネルは自ら sleep しない限り処理を妨げられない、だからこそ実行可能なものが沢山あるとき、どれから先に実行するかが重要で、sleep で次に実行可能になったときのプライオリティを指定するわけである。
PINOD といったレベルでの sleep は、リソース待ちである。本来はさっさと仕事を終らせたいにもかかわらず、だれかがリソースを使っているから、sleep せざるを得ない。だからプライオリティが高い。
なぜ、PSWP より低くて、PRIBIO というやつより高いのか ... これも理由があるが、詳細は別途読み取ろう。

ifree(dev,ino)

ifree は、プールに inode を返す。だれかが disk からアロケート中かプールがいっぱいで返せないときはなにもしない。

なぜそれで良いかというと... 忘れた。たぶんどっかで出てくる。

update()

update() とは、sync のことである。

どういうときに sync されるかというと

panic したとき
sync システムコールがよばれたとき
umount するときこの3つ。

sync の処理は、すべての mount されたファイルシステムに対して ... 汚れたデータを書き出そうとする。

書き出さない条件は、次の4つ

s_fmod == 0 -- 汚れていない。
s_ilock!=0 -- inode を disk から allocate中。= 汚している最中。
s_flock!=0 -- block を disk から allocate中。= 汚している最中。
s_ronly!=0 -- リードオンリーで mount されている。

さて、書き出すことがきまったファイルシステムに対して、

super block をまず更新する。更新は、

getblk -- 該当データに対する struct buf を得て
(中身が入っているかどうか気にせずに、メモリ上のデータを上書きして)
bwrite() で書き出す。

bwrite は、同期書き込み。書き終るまで待ち、struct buf を開放して戻る。

書き出す前に、super block が更新された時刻を設定し、さらに、s_fmod を 0 にしている。

次に、メモリにあるすべての inode を iupdat() で更新する。

最後に bflush() で、汚れているキャッシュを書き出す。

あとは、 updlock というフラグを使って、同時に update() が実行されないように排他制御。している。排他制御といっても、だれかが先に update() していればなにもしないという処理。

さて、ifree でなにもしなくて良いのは、update() 等で、inode は disk に書き戻され、disk に反映されるから。disk に反映されれば、再利用できるから、無理に pool に登録しなくとも良いわけだ。

iupdat(ip, a_timep, timep)

inode を disk に書き出す処理。

これを呼ぶところは、4 ヶ所。

上の update()
iget() で空きがないとき
stat や utime が呼ばれたとき。

まず、disk 上のデータを bread() してくる。

そして、dinode を更新する。もっている struct inode のデータは、すべて上書きして、さらに、atime,mtime,ctime を指定に応じて更新する。

最後に bdwrite() で書き戻す。

bdwrite は、遅延書き込みのプリミティブ。buf をダーティな状態にするだけで bwrite のようにすぐに書き出してさらに I/O が終るのを待つものではない。
ちなみに、write プリミティブは、もう1つある。bawrite() これは、非同期 write で、すぐに書き出すが、I/O が終るまでは待たない。

さて、ここで、block device の I/O プリミティブについてまとめてみよう。

              getblk(dev,bno)       bread(dev,bno)
              buffer を得る。       中身の入った buffer を得る。


   brelse(bp)      bdwrite(bp)     bawrite(bp)         bwrite(bp)
   buffer を開放   遅延書き込み    非同期書き込み      同期書き込み
                   ダーティにして  I/O をスケジュール  I/O 完了を待って
                   開放            して開放。          開放

実にシンプルできれいな構造だと思う。いまのカーネルは不幸なことにこんな単純できれいな制御は許されない。

その理由は、2 つしかないと思う。ひとつの理由は、仮想記憶サポート。もうひとつの理由は、性能。(あ、SMP サポートも性能のうちにいれてます)

iget(dev,ino)

カーネル内部でのファイルの open は igetである。

ファイルは、内部的には、ファイルシステムを識別するデバイスの ID とファイルシステム内の ID である inode 番号によって一意に決まる。
そういうわけで、その 2 つが引数になっている。

逆に close する概念は、iput(ip)

iget ではどういことをしているんだろうか。

V7 カーネル内には、inode は、同じ inode というテーブルにもっている。ややこしいが、これのことは inodeテーブルと呼ぶ。

まず、 inode テーブルをすべてサーチして、キャッシュされているかどうかを調べる。

見付かっても、他のプロセスが ILOCK している場合がある。その場合は、 sleep して待つ。

           if((ip->i_flag&ILOCK) != 0) {
                ip->i_flag |= IWANT;
                sleep((caddr_t)ip, PINOD);
                やりなおし
            }

そして、inode が取れたからといって、使って良いものではない。

それがマウントポイントだった場合、IMOUNT というフラグが立っている。このケースでは、mount テーブルを検索して、mount されているところの dev,ino に変更して、やりなおす。

ここをパスしてきたら、リファレンスカウンタの i_count を +1 して、 ILOCK してから、inode を返す。

さて、キャッシュにないとなれば、disk から読んで来る。

どの inodeテーブルのエントリを使うかというと、テーブルをみていくときに、見付けておく、

候補がなければ、inode overflow で panic。

itod(ino) という単純なマクロで、disk 上の位置がわかるから、そこを bread するわけだが、その前に inode の状態を設定する。 bread では sleep するかも知れないので、他のプロセスに使われてしまわないようにするわけだ。

この時点で設定すべき情報は、

(dev,ino) -> i_dev,i_number
iget したときと同じ状態 -> i_count++, ILOCK

である。

bread したら、itoo(ino) で、ブロック内オフセットを決めて dinode のアドレスを計算( -> dp) し、ipexpand(ip,dp) で、disk の情報を inode にコピーする。

それが終ったら brelse(bp) して block を開放する。

iexpand(ip,dp)

まあ、これは、見ればわかる。Disk の情報を inode に移すだけ。

iput(ip)

iput は、inode の close に相当する。

i_count をデクリメントするが、元の i_count が 1 でないなら、他でまだ使われている。そういう場合は、prele(ip) だけして戻る。

prele(ip) は、ILOCK の開放処理で、plock(ip) と対になっている。

p は、pipe の意味で、plock/prele とも pipe.c にある。

でも実態は、inode の汎用 lock/release

さて、iput を開放する場合は ... どういう処理だろうか。

i_nlink が 0 になっている場合 ...

これは、そのファイルはどこからも参照されなくなったということを意味する。そういうときは、

itrunc(ip) で、ファイルの実態を開放して (= ファイルのサイズを 0にするから truncate ) そして、ifree() で inode も free

そうでない場合は、iupdat() で、buffer に書き戻す。 (iupdat() は、bdwrite を使っているから、正確には、buffer を dirty にする。)

inode が clean になれば、prele してから、inode の i_flag,i_number を 0 にして inode 構造体を開放する。

inode というリソースをどう使っているか見えてきただろうか ...

    iget -> 使用中 かつ ILOCK中
    なにか排他的に使用したい処理
    prele() ILOCK を外す

   ( 他で iget できる。) 
         :
       plock()
       なにか排他的に使用したい処理
       prele() 
         :

    plock()
    なにか排他的に使用したい処理
    iput -> 未使用

だいたいこんな感じか。

変に使うとデッドロックは簡単に起きそう。
... どうやってデッドロックが起きないようにしているか ... V7 はまだ単純そうだが、カーネルにおいてその説明は一般に難しい。

さて、itrunc() が出てきてしまった。いよいよファイルの中身をさわるところに説明を移す。

どういう順序で読んでいこう。

itrunc() からスタートすると free() が出てくる。free() と対になるのは、 alloc() 。この2 つは、ialloc()/ifree() とよく似ているし同じ alloc.c にある。

次に alloc()/free() を説明。今度は、どうやってそれを作るか ... それは write でしか起きないから、writei() にいく。そして、続いて対になる readi() 。

itrunc(ip)

まず、IFREG でも IFDIR でもないものは、ファイルシステムがサポートしているいわゆるファイルでないから、なにもしない。

次に、13 個回のループで、inode に格納されているブロック番号に対しデータブロックの開放をしていく。10 個までは、ダイレクトだから、 free(dev,bno) で開放する。そうでない場合は、

11 個目 tloop(dev, bn, 0 , 0);
12 個目 tloop(dev, bn, 1 , 0);
13 個目 tloop(dev, bn, 1 , 1);

というように tloop の関数を call して、開放する。

それが終れば、i_size を 0 にする。

さて、この tloop はどういう構造なのだろう。

(dev,bn) から 1 ブロック読んできて、その中に入っているブロック番号に対しデータブロックの開放をしていくわけだが ... 再帰になっている。第3引数が 0 なら、直接 free() し、そうでなければ tloop を呼ぶ。再帰的に呼ぶ tloop への第3引数は、与えられた第4 引数。そして、呼ぶときの第4 引数は、0 にする。

ブロックを読むときは、bread(dev,bno) 処理が終れば belse(bp)

alloc(dev)

alloc 中は、fp->s_flock が 1 になっている。

したがって、関数の入口で、チェックして、終るのを待ち合わせる。そして、出口で、wakeup する。

ここのロジックは、plock/prelse と同じような感じ。ialloc/ifree での s_ilock と同じである。

ialloc と同じく、

        fp->s_free[];

にプールがある。あればそこから取って来る。

取った結果、s_nfree が 0 になれば disk から free ブロックを取って来てプールに埋める。

さあ、それはどうやって取って来るのだろう。

        fp->s_free[0]

に入っているのは、単なる free なブロックの番号ではなく、disk 上の free リストを指していた。

その block を読んで来て ... s_free に bcopy している。 ... ということは、bcopy すれば、同じ構造になるってことだ。

        s_free = SUPER BLOCK          disk 
        +-----------------+          +------------------+
        |       o------------------->|        o---------------->
        +-----------------+          +------------------+
        |    free         |          |     free        |
        +-----------------+          +-----------------+
        |    free         |          |     free        |
        +-----------------+          +-----------------+
        |      :          |          |       :         |

まあ、こんな感じ。

ブロックが割り当てられたら、getblk(dev,bno) で bp に変換して、さらに clrbuf(bp) として、bp を戻す。

free(bno)

今度は block を free する方。

s_flock を取るというところは、alloc と同じ。

s_free がいっぱいにならなければ、そこに返せば良い。

いっぱいになったら ...今度は disk に返さないといけない。

どうやるかというと、今返そうとする block に s_free を書き込んで、その block を

      fp->s_free[0]

にする。

なんか巧妙。シンプルでスマートっていう印象がある。

...ただし、20 年以上前。 Disk だって、何 MB、何十MB かしか使えない時代の話。

writei(ip)

まず、引数が inode のポインタしかない。これでどうやって write ？とか思われるかも知れない。

他の引数は、u という構造体に入っている。これはプロセス毎にあるもので、次のもの

   u.u_offset   ファイルのoffset 
   u.u_count    write するバイト数
   u.u_base     アドレス
   u.u_segflg   アドレスが kernel空間 にあるか user 空間にあるかの区別

まずは、デバイスファイルのチェック。char 型デバイスなら cdevsw の d_write メソッドを呼ぶ。

bdevsw は、write できない。

さて、u_count を減らしながらループすることになるが、そのループの中身は...

まずは、ファイル相対のブロック番号を計算

    bn = u.u_offset >> BSHIFT;

次に disk のブロック番号を出す。これは、

    bn = bmap(ip, bn, B_WRITE);

次にブロック全部を書く場合は、getblk() そうでなければ、bread() する。これで、struct buf *bp が得られたわけだが、そこに

    iomove(bp->b_un.b_addr+on, n, B_WRITE);

で、データをいれる。

最後に bdwrite する。

bmap(ip, bn, rwflg)

ファイル相対のブロック番号を Disk のブロック番号に変換する。

まずは、0 - 9 までのの場合。これは inode にダイレクトに入っている。

それを返せば良いが、0 だった場合は ...

B_READ なら -1 を返す。
B_WRITE なら、alloc で block を割り当てる。そして、inode を更新し、i_flag にダーティだというフラグも立てる。
さらに... bdwrite で、ダーティにしている。なんかl気が早いっつうか。

さて、0 - 8 なら、rablock なるものに、次のブロック番号をいれている。
```
   :daddr_t    rablock;                /* block to be read ahead */
```
なるほど、1 block ながら、read ahead なのか。
あれ? breada(dev, bn, rablock) もあるじゃん。ファイルシステムの表を変更しなくては。

さて次は、間接参照。まずは、何回 block を読んで来たら良いか計算。

まずは、inode にある最初のテーブルのブロック番号を取って来る。

B_WRITE の場合。なければ作る。B_READ ならなければサヨナラ。

そして、3 回を上限としたループで、テーブルのテーブルを読んで来る。

テーブル自体がなければ作るし、B_READ ならなければサヨナラ。

さて、block 番号が決まれば、最後のテーブルの次のエントリを rablock にいれておく。

詳細な説明にはなっていないが、まあこんなとこ。

ところで、この bmap 。V7 では subr.c なんていう適当な名前のファイルに入れられているが ... この後のファイルシステムにおいてファイル相対のブロック番号から物理的なブロック番号を出して来る機能を表す名前になっている。たいがい複雑だから、BSD なんかでは、ufs_bmap.c とかファイル名も貰えている。

iomove(cp, n, flag)

これは、単なるコピールーチンだから解説はパス。

ただし、中で使っている copyin/copyout は、別のコンテキストで解説予定。

readi(ip)

まあ、writei(ip) とほとんど同じなので、詳細はパス。コメントだけ。

bmap でエラーになったようなケースは、geteblk() で空の block を取ってきて、read したことにしている。

今読もうとしている block が前に読んだ block+1 なら、次も読むだろうということで、breada(dev,bn,bablock) としている。
そして今回読んだブロックは、ip->i_un.i_lastr に保存。

こういうロジックなら、このころファイルの途中でブロックが割り当てられていないような穴あきファイル。サポートしていたわけか ... ううむ。

これで、ファイルを open し、read/write するそして close するロジックが終った。

ここまで来たか... とか思ったが、解説を書いたのは、 alloc.c iget.c rdwri.c subr.c のたった 4ファイル 1000 行ぐらい。密度高いなぁ。

次は、ディレクトリ。これがないと ... name spaec とファイルを結びつけられない。

V7 では、mkdir とか rmdir は、カーネル内にない。多少の問題に目をつぶれば、ファイルのアクセスで実現できてしまうわけだ。

カーネルにないものは、ここでも解説しない。

ここで解説するのは、ディレクトリ自体の概要と、namei() --- パスから inode への変換ルーチン。

ディレクトリの構造

V7 では、次の構造体が h/dir.h に定義されている。

struct  direct
{
    ino_t   d_ino;
    char    d_name[DIRSIZ];
};

このように、単に inode 番号とファイル名が入った構造体。そして、ディレクトリは、この構造体の単なる配列である。
DIRSIZ は、14 で、14 文字までのファイル名をサポートする。

ディレクトリを作ると . と .. があって、自分および親を指すようになっている。
要するに、. は自分のディレクトリの ino が入っていて、.. には親の ino が入っている。inode には、i_nlink というリファレンスカウントがある。
親から指されて自分でも自分を指すから、ディレクトリを作れば、i_nlink は 2

UNIX では、ファイルは、消したりするものではない。リンクするもので、link/unlink という概念があって、リンクが 0 になれば、参照するものがなくなるので、自動的に消える。

open しておいて、unlink すれば、close するまでの間はアクセスでき、 close してしまえば、消えてなくなる ... そういうファイルをサポートしている。

UNIX では、そういう使い方をするもののひとつとして、pipe がある。

ただし、現在の UNIX で pipe を file として実装しているものは、ない(はず)。理由は select(2) の実装が面倒なためである。 select(2) の登場とともに pipe は、UNIX ドメインの soket で実装されるようになった。... そして現在は.. 知らない。

namei()

(最終更新 Thu Mar 30 18:37:11 2006)