Unix V6コードリーディングの個人的なメモ

学科ゼミとしてV6を読む会というのをやっています。ここまでのところ4回ほど開いて、順次はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)を読んでいます。とりあえずオラオラと9章(加えて14章)まで読んで来たわけですが、面白いなぁと思ったいくつかのことについて自分でまとめておこうという気持ちになったのでまとめようと思います。

ぼくはLions本を前から読んでいるわけではなく、V6の基本的知識はOSコードリーディング本によるものです。

(書いたのは、好きな話や少し気になった話だけです(浅く網羅しても仕方ないため))

forkの仕組み

 概念的に「forkはプロセスの内容がコピーされて分岐する」のような説明を聞くことがあるのですが、これを達成する部分は少し巧妙でした。これはほぼ各所で書かれている話ですが、理解したところをまとめておきたいと思います。

基本的にUnix V6で新しいプロセスを作るにはこのforkをします。forkとは、現状のプロセスのコピーを作って、プロセスを分岐させます。ここで、実行される命令の列は同じだが、二つのプロセスの実行の流れを分岐させるうまい仕組みがあります。

そもそもforkは細かく見ると、具体的には次のいくつかの部分に分かれます

【親プロセス】

  • newprocを呼び出す
  • procやデータセグメントの情報を子供のプロセスにコピーする(*)
  • newprocをreturnし、このとき0が帰って来る
 savu(u.u_rsav);
    rpp = p;
    u.u_procp = rpp;
    rip = up;
    n = rip->p_size;
    a1 = rip->p_addr;
    rpp->p_size = n;
    a2 = malloc(coremap, n);
    /*
    * If there is not enough core for the
    * new process, swap out the current process to generate the
    * copy.
    */
    if(a2 == NULL) {
        rip->p_stat = SIDL;
        rpp->p_addr = a1;
        savu(u.u_ssav);
        xswap(rpp, 0, 0);
        rpp->p_flag =| SSWAP;
        rip->p_stat = SRUN;
    } else {
    /*
    * There is core, so just copy.
    */
        rpp->p_addr = a2;
        while(n--)
            copyseg(a1++, a2++);
    }
    u.u_procp = rip;
    return(0);

(ken/slp.c)

このとき、子供は起きていない状態で、親の実行が進みます。次に、swtchによって、プロセスのスイッチが起きて、子供が起こされた時どういう挙動になるかを考えます。まず実行が始まるのは、データセグメントやレジスタの情報を保存した部分になります。これは、すなわち、上記のnewprocの中の部分です。

swtch自体は、

 if(rp->p_flag&SSWAP) {
        rp->p_flag =& ~SSWAP;
        aretu(u.u_ssav);
    }
    /*
    * The value returned here has many subtle implications.
    * See the newproc comments.
    */
    return(1);

(ken/slp.c)

のような形で関数から戻ります。

ここで重要なのは、swtch内でaretuが実行されることにより、このnewprocを呼び出した関数に戻るように、swtchがreturnされるという点です(すなわち、スタックフレームが一個ずれる)。これにより、newprocからあたかも1が帰って来ている状態になり、結果として、

fork()
{
    register struct proc *p1, *p2;

    p1 = u.u_procp;
    for(p2 = &proc[0]; p2 < &proc[NPROC]; p2++)
        if(p2->p_stat == NULL)
            goto found;
    u.u_error = EAGAIN;
    goto out;

found:
    if(newproc()) {
        u.u_ar0[R0] = p1->p_pid;
        u.u_cstime[0] = 0;
        u.u_cstime[1] = 0;
        u.u_stime = 0;
        u.u_cutime[0] = 0;
        u.u_cutime[1] = 0;
        u.u_utime = 0;
        return;
    }
    u.u_ar0[R0] = p2->p_pid;

out:
    u.u_ar0[R7] =+ 2;
}

(ken/sys1.c)

上のプログラムにおいて、newprocの返り値による分岐ができています(!)。この仕組みはなかなかうまいなぁと思います。

文章で書いてもわかりにくいので図にしました。

enter image description here

図にしてもあまりうまく書けなかったです。

MMU用のハードウェアAPRなどの管理

UISAやUDSAのようなアドレスは特定のアドレスにマップされていますが、なぜこれを更新するとちゃんとコンテキストスイッチができるのかについて本を読んでいて納得できなかったので一応メモです(今から考えるとそれはそう)。

というのは、UISAやUDSAというのはアドレス中の値であり、具体的には

#define UISA    0177640        /* first user I-space address register */
#define    UDSA    0177660        /* first user D-space address register */

のように定まっています。しかし、このアドレスというのは仮想アドレスであることから、MMUがうまく参照できないのでは?という疑念がありました。

結論から言うと、カーネルAPRの7番目の値すなわち仮想アドレス0160000〜0177777が常に物理アドレス上の0760000〜0777777にマップされるため問題はないです。 つまり、UISAがマップされる場所やUDSAがマップされる場所は常に固定で、逆にこの固定の領域を使って周辺デバイスとのやりとりがなされています。 これらのアドレスが選ばれていることについては、Lions本を引用すれば"The method of assignment of addresses to registers in this page is a black art: the values are hallowed by tradition and are not to be questioned."らしいので、とりあえずこの場所に固定された領域があってMMUがここを読みに来ているのでうまくアドレス変換が可能となるのだということまでは言えると思います。

その他ネタ

へーって思った話。普通にPDP 11のWikipediaとかOSリーディングの本とか見れば書いてあることだが、へーって思ったのでメモ。

無名構造体

int型の値のMSBから8bitみたいな値を参照するのに、構造体のようにアクセスしているコードが随所にあります。

 (*bdevsw[rootdev.d_major].d_open)(rootdev, 1);

こんな風な感じです。これ一見すると全然変ではないんですが、例えばrootdevというのは、

int rootdev;        /* dev of root see conf.c */

のように定義されていることからわかるように、int型の値です。すなわち、int型の値に構造体にアクセスしているということで、なんやねんとなります。

実は、ここで使われているC言語はpre K&Rといわれるもので、現在ではありえないような構文がいくつか存在します。これもその一つで、裏には、無名構造体という概念があります。例えば、d_major、d_minorの定義は

struct
{
    char    d_minor;
    char    d_major;
};

のようになっています。このように無名な構造体を定義すると、任意の変数に対してこのような参照が可能になります。  デバイス番号というのは、MSB8bitにmajor番号、その下8bitにminor番号が入ったものになっています(int型自体は16bit)。したがって、見方によってはint型というのはchar型が二つ並んだという構造をしているものであると考えることができ、よって上のような書き方をすることができます。すなわち、MSB1byte分に対するアクセスであると言えます。

ところで面白いのは、デニスリッチーですら混乱したのか一部では

(*bdevsw[swapdev>>8].d_strategy)(&swbuf);

(dmr/bio.c のswap関数)

のように、デバイスのMSB1byteをある種より直接的に取り出しているコードがあったりして面白いです。

エンディアンの話

上に関連して、上のコードが動くならリトルエンディアンなんやろなーって思ったら、少し興味深い感じでした。というのは、確かに16bitの値に対してはリトルエンディアンになっているのですが、32bitの値を表現する、すなわち2ワードに関しては、ワードについてはビッグエンディアンになっているらしいということです。日本語で説明するのは難しいので図があります。 enter image description here

itruncで間接参照テーブルについてのoff by one errorっぽいやつ

 if(*ip) {
        if((rp->i_mode&ILARG) != 0) {
            bp = bread(rp->i_dev, *ip);
            for(cp = bp->b_addr+512; cp >= bp->b_addr; cp--)
            if(*cp) {
                if(ip == &rp->i_addr[7]) {
                    dp = bread(rp->i_dev, *cp);
                    for(ep = dp->b_addr+512; ep >= dp->b_addr; ep--)
                    if(*ep)
                        free(rp->i_dev, *ep);
                    brelse(dp);
                }
                free(rp->i_dev, *cp);
            }
            brelse(bp);
        }
        free(rp->i_dev, *ip);
        *ip = 0;
    }

(ken/iget.c itrunc関数)

ここですが、

for(cp = bp->b_addr+512; cp >= bp->b_addr; cp--)

はおそらく、512ではなく、510ですよね。

これに関してはLions本にも言及があり、"Since they will presumably contain zero, they will contribute nothing to the calculation."などと書いてある。確かに、*(b_addr+512)が0であれば、そのあとの条件分岐の中に入らないので良いっぽいのだが、いつゼロクリアしたかというと、これは難しくて、例えばバッファの初期化部分のコードを見ると

clrbuf(bp)
int *bp;
{
    register *p;
    register c;

    p = bp->b_addr;
    c = 256;
    do
        *p++ = 0;
    while (--c);
}

(dmr/bio.c)

となっていて256回ループするが、ところで、bufferの定義は、

char buffers[NBUF][514];

であることから、最後の2byteについてはおそらく0クリアされない。すると、どこで、0クリアされているのかを考えると、おそらく起動時の物理メモリの0クリアまで遡るのではないか。この部分については完全に推測でしかないが、しかし、off by oneっぽいのが残っているのは少し面白いです。

ねむい。だいぶ雑になってしまったので渋い(また全部読んだ時に改めてまとめたい)