UNIX 6th Editionにシステムコールを追加してみる

という事で、カーネル/VM Advent Calendarの担当日なので、表題の件で書いてみようと思います。カーネル修行中の身という事で、Lions Commentaryで勉強中のUNIX 6th Editionをちょっとだけhackしてみます。

目標
Linuxなどで「man select」としてみると「The select() function call appeared in 4.2BSD.」などと書かれています。こいつを6th Editionに実装してみましょう。
Ancient UNIXではブロックする時には原因となる変数のポインタを引数としてsleep()を呼び出します。逆にブロック要因が解けた時、同じく変数のポインタを引数としてwakeup()を呼び出します。この時、全プロセスの情報をなめ、同じポインタ値を要因としてブロックしている全プロセスを起こすという古典的な手法をとっています。要因が1つしか持てず、リストも1つだけで管理されている事からも、select()が存在しない、というのは納得な話に思えます（と、言いつつselectの実装は理解していないのですが）。
そこで、完璧なものは難しいですが、pipeを多重化して入力待ちするのに必要最低限な機能を持たせた限定版システムコールselectを追加してみる事にします。

アセンブラからシステムコールを呼び出してみる
追加したシステムコールを呼び出すにはアセンブラを書く必要があるため、まずはシステムコールを呼び出すアセンブラの確認です。適当な作業領域に移りましょう。

% ed hello.s
?
a
main:

        mov $1,r0
        sys write; hello; 6
        sys exit
hello:
        <hello\n>
.
w
66
q
% as hello.s

% a.out

hello

ユーザ入力を赤、または青字、ソフト側からの出力を黒字で分けてあります。
ユーザ入力については、まとまったソース部分を青字にしました。

大丈夫だ、問題ない。

次は簡単なシステムコールを追加してみる
まずはエントリの追加から。

# chdir /usr/sys/ken
# ed sysent.c
2131
62

        0, &nosys,                      /* 49 = x */

s/nosys/hello/

s/x/hello/

p

        0, &hello,                      /* 49 = hello */

w

2135

q

この構造体に引数の数とハンドラを登録する事でシステムコールを追加できるはず。そして、実際のシステムコールの実装。ここでは簡単のためconsoleに直接helloと表示することにします。ここも同じくken以下で作業します。

# ed hello.c

?

a

hello()

{

        printf("hello\n");

}

w

32

q

最後にカーネル再コンパイル。
ところがそこには罠が。/usr/sys以下で「# sh run」とすれば、苦労せずにカーネル再コンパイルができる・・・と随所に書かれているのですが、実はこのままではlib1、lib2が更新されず、すなわちken以下での先程の修正が反映されません。そこで、以下の手順でrunスクリプトを修正します。

# chdir /usr/sys
# ed run
3
ar r ../lib1
s/1/1 *.o/
p
ar r ../lib1 *.o

8

ar r ../lib2

s/2/2 *.o/

p

ar r ../lib2 *.o

w

908

q

修正適用後は「# sh run」でカーネル再コンパイル可能。lib1とlib2を完全に削除しちゃうと解決できないシンボルが出てきてしまうので注意。ここは細かく追ってません。また、ken以下の拡張子cを全てコンパイルするように記述されているため、追加したファイルについて気にする必要はありません。

追加したシステムコールの確認
先ほど追加したhelloで呼んでるprintfはC言語の標準関数ではなく、ken/prf.cの中で定義されているconsoleへ直接出力するpanic用の関数。素の状態だと出力禁止になってるので、デバッグのために出力を開放する必要があります。simhを利用している場合にはCtrl-Eでモニタ？に落ちて

Simulation stopped, PC: 002502 (MOV (SP)+,177776)
sim> d sr 1
sim> cont

とすればOK（前回のLions読書会でoracchaさんに教えてもらいました、さんくす！）。
続けて、追加したシステムコールを呼び出すだけの簡単なユーザランドプログラムを書いてみます。適当な作業領域で作業しましょう。

% ed sys_hello.s
?
a
main:
        sys 61
        sys exit
w
24
q

49番で追加したシステムコールですが、アセンブラは8進数で記述する必要があるため61と書く必要があります。ちなみに、hello.sではsys writeなどと書きましたが、実はこのシステムコール名、マクロなどではなく、アセンブラの中に直接「名称→コール番号」の変換テーブルを持ってるようです。なので、アセンブラを修正しない限りは数値直書きしかありません。
という事で、実行して動作を確認。

% as sys_hello.s
% a.out
hello
%

・・・とは、ならず・・・

% as sys_hello.s

hellout


%

こんな風になりました。最後の改行についてCRだけ表示されたタイミングで、カーネル内のprintfがLFを追い越して表示しているようです。ここも細かくは追っていません。まぁ、とりあえずシステムコールの追加はうまくいっているようなので一安心。


システムコールの引数と返り値
システムコールの引数は、レジスタr0とtrap命令に続くテキスト領域内の最大5つまでのデータ列として渡せます。また、返り値はレジスタr0です。
システムコールのハンドラ側では、それぞれu.u_ar0[R0]、u.u_arg[n]として値を受け取ることができます。返り値はu.u_ar0[R0]にセットすれば、システムコールから返るときにユーザランドのコンテキストに書き戻されます。
これらの挙動を確かめるため、やはり簡単なテストコードで実験しましたが、ここでは割愛。

selectの実装
まずはシステムコールとCの関数をブリッジする部分を作ります。適当な作業領域に移動して以下のファイルを作ります。

% ed syssel.s
?
a
.globl  _select


_select:
        mov 2(sp), _nfds
        mov 4(sp), _rfds
        mov 6(sp), _wfds
        mov 10(sp), _efds
        mov 12(sp), _timo
        sys 62
_nfds:  0
_rfds:  0
_wfds:  0
_efds:  0
_timo:  0
        rts pc
w
178
q

システムコールの番号はさっきより1つ大きな値。引数をsys命令の直後にコピーしてシステムコール呼び出し＆リターンするだけの簡単なラッパーで、今回R0は返り値だけに利用しました。spからのオフセットも8進数で書くことに注意。これでC言語から「int select(int nfds, int *rfds, int *wfds, int *efds, int *timo);」の形でシステムコールを呼び出せます。本来ならrfds, wfds, efdsはfd_set *ですが、typedefがないのとプロセスが持てる最大ファイルディスクリプタ数が15なのでint *としました。気持ち的には「typedef struct fd_set { int fds_bits[(NOFILE + 7) >> 3] } fd_set」です。timeoutは難しいので今回は無視。というか、nfdsとrfds以外は今回は無視します（笑）。
さて、いよいよシステムコール側の実装です。本来は指定されたデスクリプタのいずれかが変化するか、signalが割り込むまでブロックするのが正しい動作ですが、簡単のためノンブロックで返るような動作にしましょう。

# chdir /usr/sys/ken
# ed sysent.c
2135
62,63p
        0, &hello,                      /* 49 = hello */
        0, &nosys,                      /* 50 = x */
s/nosys/select/

s/x/select/

s/0,/5,/

62,63p
        0, &hello,                      /* 49 = hello */
        5, &select,                     /* 50 = select */
w
2141
q
# ed select.c

?
a
\#
\#include "../param.h"
\#include "../user.h"
\#include "../file.h"
\#include "../inode.h"
\#include "../reg.h"


select()
{
        int nfds, rfds;
        int out_rfds;
        int rc;
        register *fp, *ip, i;

        nfds = u.u_arg[0];

        rfds = fuword(u.u_arg[1]);

        out_rfds = 0;

        rc = 0;

        for (i = 0; i < nfds; ++i) {

                if (!(rfds&(1<<i)))

                        continue;

                fp = getf(i);
                if (fp == NULL)
                        continue;

                if (!(fp->f_flag&FPIPE))

                        continue;

                ip = fp->f_inode;

                plock(ip);

                if ((fp->f_flag&FREAD) && (fp->f_offset[1] != ip->i_size1)) {

                        out_rfds =| (1<<i);

                        ++rc;

                }

                prele(ip);

        }

        suword(u.u_arg[1], out_rfds);

        u.u_ar0[R0] = rc;

        u.u_error = 0;

}

.

w

627

q

#

sysent.cにselectのエントリを追加します。引数の数が5となるため、構造体の先頭の0を書き換える必要がある点に注意。selectの実装は見ての通りです。いくつか注意点を書くと、まずは引数の処理。u.u_arg[1]にはint *rfdsが入っていますが、この値はユーザ空間でのrfdsへのポインタ値です。なので、中の値を見るためにはfuword()を使ってユーザ空間から読みだしてやる必要があります。値の書き戻しも同様でsuword()を使います。それぞれfetch user-space word、store user-space wordですね。もう1点忘れがちなのがu.u_errorの処置。ループ内でgetf()を呼び出しています。こいつはファイルディスクリプタ値を渡して、指定したデスクリプタが開いていたら構造体を返してくれる関数ですが、開いていなかった場合にはNULLが返るばかりでなく、u.u_errorにEBADFがセットされます。このエラーをこのまま放置すると、trapから返るときにu.u_ar0[R0]にu.u_errorを上書きします。必ず0にリセットしてあげましょう。カーネルの再構築も「# sh run」で忘れずに行います。

動作確認
selectの確認はちょっと面倒ですね。pipeで子プロセスを2つ作り、それらの入力を多重化して待ちながら逐次表示してあげるようなプログラムを書いてみます。まずはselectを使う上で必要になるいくつかの関数を用意します。syssel.sを作った作業領域で続けましょう。

% ed select.c
?
a
FD_SET(fd, fds)
int fd;
int *fds;
{
        *fds =| (1<<fd);
}


FD_ISSET(fd, fds)
int fd;
int *fds;
{
        return (*fds & (1<<fd));
}


FD_ZERO(fds)
int *fds;
{
        *fds = 0;
}
.
w
162
q
%

本来ならマクロで書きたいところですが、たぶん当時のプリプロセッサでは引数の置き換えとかできなそうなので、トラブルを避けて関数で書きました。grepするとわかりますが、当時のdefineは定数定義しかしてません。
続けてテストプログラム。

% ed main.c
?
a
main(argc, argv)
int argc;
char **argv;
{
        int fds0[2];
        int fds1[2];
        char buffer[32];
        int rfds;
        int rc;


        rc = pipe(fds0);
        rc = pipe(fds1);
        rc = fork();
        if (0 == rc) {
                for (;;) {
                        write(fds0[1], "this is child 0\n", 16);
                        sleep(2);
                }
        }
        rc = fork();
        if (0 == rc) {
                for (;;) {
                        sleep(1);
                        write(fds1[1], "this is child 1\n", 16);
                        sleep(1);
                }
        }
        for (;;) {
                FD_ZERO(&rfds);
                FD_SET(fds0[0], &rfds);
                FD_SET(fds1[0], &rfds);
                rc = select(16, &rfds, 0, 0, 0);
                if (rc <= 0) continue;
                if (FD_ISSET(fds0[0], &rfds)) {

                        rc = read(fds0[0], buffer, 32);

                        write(1, buffer, rc);

                }

                if (FD_ISSET(fds1[0], &rfds)) {

                        rc = read(fds1[0], buffer, 32);

                        write(1, buffer, rc);

                }

        }

        return 0;
}
w
729
q
%

コンパイルして実行してみます。と、その前に。カーネルを作り直したので新しいカーネルでの再起動をお忘れなく。「# sync」してCtrl-Eから「sim> exit」でエミュレーション終了。再度エミュレータを起動してrkunixで立ち上げます。

% as syssel.s
% mv a.out syssel.o
% cc main.c select.c syssel.o
main.c:
select.c:
% a.out
this is child 0
this is child 1
this is child 0
this is child1
.
.

成功です！永久ループなので、適当なところでDELキー（Ctrl-C相当）を押します。という事で、最低限のミッションは達成しました。
応用編としてはselectシステムコール内で読めるデスクリプタがなかったらsleepするように変更すると良いかと思います。適当な新規要因を決めてsleepしてあげて、sleepから返ってきたら再度デスクリプタの走査へgoto。wakeup側では毎回、問答無用でselectを起こしてあげるようにしとけば、最低限それっぽく動くはず。真面目にやるならproc構造体を拡張してp_wchan相当のエントリ、p_wfdset[NOFILE]的な物を追加してあげて、p_wchanがselectならp_wfdsetも調べる〜とかするだけでOKなはず。

・・・なんか簡単だったので実装してみました。今までの形式だと分かりにくいので以下は差分を赤文字にしてソースを転載します。

[select.c]

#include "../param.h"
#include "../user.h"
#include "../file.h"
#include "../inode.h"
#include "../reg.h"
#include "../proc.h"


select()
{
        int nfds, rfds;
        int out_rfds;
        int rc;
        int fdbits;
        int i;
        register *fp, *ip, *rp;


        nfds = u.u_arg[0];
        rfds = fuword(u.u_arg[1]);
        out_rfds = 0;

        rc = 0;

        rp = u.u_procp;

retry:
        fdbits = 0;
        for (i = 0; i < nfds; ++i) {
                if (!(rfds&(1<<i)))
                        continue;
                fp = getf(i);
                if (fp == NULL)
                        continue;
                if (!(fp->f_flag&FPIPE))
                        continue;
                ip = fp->f_inode;
                rp->p_wfdset[fdbits] = ip+2;
                ++fdbits;
                plock(ip);
                if ((fp->f_flag&FREAD) && (fp->f_offset[1] != ip->i_size1)) {
                        out_rfds =| (1<<i);
                        ++rc;

                } else {

                        ip->i_mode =| IREAD;

                }

                prele(ip);
        }
        if (rc == 0) {
                sleep(fdbits, PPIPE);
                goto retry;
        }
        suword(u.u_arg[1], out_rfds);
        u.u_ar0[R0] = rc;
        u.u_error = 0;
}

[proc.h]（差分周辺のみ）

        int     p_wchan;        /* event process is awaiting */
        int     p_wfdset[NOFILE];
        int     *p_textp;       /* pointer to text structure */

[slp.c]（差分周辺のみ）

wakeup(chan)
{
        register struct proc *p;

        register c, i;

        int fd;

        c = chan;
        p = &proc[0];
        i = NPROC;
        do {
                if(p->p_wchan == c) {
                        setrun(p);
                } else if (p->p_wchan <= NOFILE) {
                        for (fd = 0; fd < p->p_wchan; ++fd) {
                                if (p->p_wfdset[fd] == c) {
                                        setrun(p);
                                        break;
                                }
                        }
                }
                p++;
        } while(--i);
}

という事で、長文に最後までお付き合いいただき、ありがとうございました。