2010年12月26日日曜日

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);
}
という事で、長文に最後までお付き合いいただき、ありがとうございました。

2010年12月12日日曜日

UNIX原典(3) - ラスト

続けてUNIX移植話に関連したトピックを3件ほど取り上げてみます。他にも性能やスケジューラの話なんかも面白かったのですが、UNIX原典の読書記録としては今回の記事を最後にしようと思います。

Fair Share Schedulerについてはこの資料が一番詳しいかな、って感じだったのですが、他のスケジューラとか勉強した時に、また比較で考えてみようと思います。

マルチプロセッサUNIXオペレーティング・システム
「UNIXカーネルの設計」の著者、M.J.Bachによるマルチプロセッサ環境への移植話。ここではMP(multiprocessor)、AP(Associated Processor)を取り上げていて、前者がいわゆる今時のSMP、CMPの話。後者はI/OはマスターCPUに括りつけて、他のCPUはユーザランドの実行だけを行うような単純な方式によるマルチプロセッサ化の話になります。この方式ではカーネル自体、特に排他制御などは不要で、スレーブCPU上でユーザがシステムコールを発行した際、マスターCPUにコンテキストを移し、システムコールは常にマスターCPU上で実行するようにするだけで対応できます。よって、この論文では主にMP上に移植する際の問題について書かれています。

Lions本などでも書かれているように、UNIXではatomicな処理が必要となるリスト探索などは、一時的に割り込みレベルを上げて、リスト探索中に割り込みによる中断と他の文脈からのコードの実行を禁止し、探索が終了したら割り込みレベルを通常に戻す、といった処理(spl6やspl0)をしています。ところがマルチプロセッサでは割り込みレベルを上げたところで、他方のCPUが競合するコードを実行する事は可能なわけで、意味をなしていません。よってMP版UNIXでは、これらの問題に対処するためにセマフォ(*1)が導入されました。

また、sleepとwakeupについてもセマフォの取得と開放(psemaとvsema)に置き換えられました。

セマフォを使う際に問題となるデッドロックについても説明されています。これは一般的なデッドロック回避方法「依存ループを作らない」の言い換えでもありますが、資源に順序付けを行い、ロックは順序付けにしたがって行う、という単純なルールに従うだけでデッドロックは回避できます。

排他制御を行う際には、細かな粒度でロックをかけることが性能の上で重要になってきます。連結リストをハッシュに置き換えてロックの粒度を小さくする方法が紹介されているが、一番競合が起きやすいバッファプールのフローリストについては、うまい分割方法が知られていない、と書かれていました。今時の最新事情でどうなっているのか、知っている人がいたら教えてください(笑)。


IBMシステム/370のUNIXシステムの実現
こちらはIBMのメインフレームへ移植したお話。この移植は370のハードへ移植した、というよりは370上で動くTSS/370をターゲットとして移植したようです。mach上で動くように移植されたLinux、MkLinuxに近いもの、と読みました。理由としては370の仕様がハードごとに細かく異なり、個別の移植が困難だったことが挙げられるようです。360系は長期に渡る使用に耐えた拡張性のあるアーキテクチャ、という事になっていますが、メインフレームの文化を考えると、ファームレベルではワークアラウンドやRASの処理がごった返し、相当なカオスなのでは、と想像されます。

この版のUNIXで特徴的なのはページングの実装方法です。1つの物理ページに対して、リファレンスカウントを用意して、複数の仮想ページに割りつけられるようになっています。当時のforkは、親のメモリを丸々コピーして子プロセスを生成する非常にコストの高い処理でした。そのためBSDではfork後すぐにexecを呼ぶプロセスのために、メモリをコピーしないvforkを用意しましたが、これは、親子でメモリを共有する危険な実装で、vfork後にexecせずにメモリ操作をした場合の動作は保証されていませんでした。この版のUNIXの実装では、fork時にはページのコピーをするのではなく、ページテーブルのコピーと物理ページ側の参照カウントをインクリメントするだけで済んでいます。また子プロセスで書き込みが発生した場合には親と共有している物理メモリの参照をデクリメントし、新しいページにメモリをコピーし、子供のページテーブルに登録するという、いわゆるcopy-on-writeを実装していたようです(*2)。

ディスクブロックサイズも、System III以前が512B、System Vや4.1BSDが1024Bだったのに対して、370版では4096Bと大きかったようです。


UNIX移植の経験
Intel 8086、AT&T 3B20S、3B5、UNIVAC 1100シリーズへの移植について書かれています。今までの2章に比べると目新しい話題はないのですが、AT&T UNIXが8086へ移植されていたとは、ちょっと驚きです。

ただ、この8086 UNIX、単純なソフトの移植というわけではなく、それ専用にPDP-11/70風のオフチップMMUを開発し、それを載せたシステムへの移植だったようです。

またエンディアンの違いの話も出ていたりしますが、今の人から見ればPDP-11のエンディアンが変態(*3)すぎるだけなわけですが。


(*1): 本の中ではDijkstraのセマフォ、と書かれている。いまやあまりにも当たり前の道具として使われているため、発明者について言及されることもなくなってしまいました。
(*2): 勉強不足のため、いわゆるcopy-on-writeの原点がこの実装なのかどうか、知りません。ご存じの方はぜひコメントを。
(*3): PDP-11のエンディアンはリトルエンディアンでもビッグエンディアンでもなく、ミドルエンディアン。リトルもビッグもそれぞれの言い分は理解できるのですが、ミドルだけは意味不明。アドホックにしか思えないのですが。。。これも意義をしっている方がいましたら、ぜひコメントを。

UNIX原典(2)

前回の投稿からだいぶ空いてしまいましたが、読んでみて特に面白かったBlitの章についてコメントしてみます。

Blit - 多重化されたグラフィクス端末
Rob Pikeによる、X以前の世界でもグラフィクス端末のお話。UNIX 7th Edition〜8th Editionの頃の話のようです。何と言っても面白いのが、グラフィクス端末側にもプログラムをロードして実行できる、という考え方。ご存知のようにXなんかの世界では、ユーザプログラムはXクライアントとして動き、Xサーバへは描画命令の単位で依頼を出します。これって、今時のアプリケーションによっては、通信の多い切り口でレイヤーを区切っちゃってるんですよね。VNCやRDPなんかのリモートデスクトップともなるとなおさら。更新のあった描画区画単位でBitmap情報をやり取りするので、通信はすごく多い。

一方で、ウェブの世界を考えてみると、実はもう少し賢い。MVCモデルで言うと、Modelをサーバサイドでセッション管理をしながら実行。Viewについては素材をサーバサイドで提供しつつ、クライアントサイドのブラウザが最終的なViewを構築。Controlについてもクライアントサイドのブラウザが提供するわけですが、Web2.0以降になってくると、この辺はサーバから送られてブラウザ上で実行されるJavaScriptが担っており、気の利いたUIや滑らかな画面更新が実現されています。

Blitの作りはこのWeb2.0に似てたりします。Blitが初めに目指すところは端末の多重化。今で言えば、画面に複数のターミナルを開きたい、というただそれだけの欲求です。サーバ側ではmpxというプログラムが走り、その中で複数のシェルが実行されます。今で言えばGNU screenみたいなものでしょうか。ディスプレイサイドではmtxtermというプログラムが走り、サーバとの間はRS-232(19,200bps!!!)で接続されます。mtxtermは多重化されたシェルの入出力を復元し、複数のウィンドウ上で動くシェル環境を再生。原始的なXに近い外観を提供しています。ただXと本質的に違うのは、ディスプレイ側でも直接アプリケーションプログラムが実行できる点。例えばエディタなどでは、画面を表示して、ユーザのカット&ペーストなどを制御するアプリケーションコードがBlit側にロードされ、このサブプログラムにより編集されたデータが定期的にUNIXサーバ側に渡される、といった具合です。

描画に関連するオブジェクトはシリアライズしてRDPクライアント側に送りつけ、ユーザ側に近い場所で実行。セキュリティ的に難しいところはあるかもしれませんが、今風に味付けすれば、色々と研究しがいがありそうなテーマにも思えます。WindowsなんかではDirectXのコードがクライアント側のGPUを使って動く、なんて話もあるみたい(*1)なので、これから面白くなってくるのかなぁ、なんて思ってます。クラウドを考える際の切り口の1つとしても面白いのではないでしょうか。

百聞は一見にしかず、という事でYouTubeで見つけた紹介動画を埋め込んでおきます。


(*1): Windows 7のRDP 7ではDirect 2D/3Dがクライアント側でレンダリングされる話があったのですが、製品レベルに到達しなかったのか、RCからリリース版に移る際に外れてしまったようです。

2010年12月8日水曜日

YUREX driver for HAIKU

Google Codeでホスティングする練習を兼ねて、以前作ったHAIKU用YUREXドライバを公開してみました。

ドライバの作成にあたっては、Yojiro UOさんによるOpenBSDのドライバuyurex.c(現在はutwitch.cに名称変更らしい)と、カーネル/VM探検隊での発表を参考にさせて頂きました。感謝!

問題は、Haiku OS使っててYUREXを持っているという条件を満たすのが、おそらく世界で私だけ・・・という事なのですが。まぁ、今のところ数少ないHAIKU用USBドライバのサンプルって事で。

ドライバで拾った情報をもとにPULSEで表示するサンプルもあるんですが、こっちはPULSEにアドホックな改変を加えたものなので、あまり公開は考えていません。希望があればライセンスを確認して公開する方法を考えますが、まぁ自分が発表でネタに使う以外は、ほとんど需要はないかな、と。


さて、UNIX原典の読書記録と、Lions読書会#2の感想もあるので、しばらく頻繁に更新したいと思います。カーネル/VM Advent Calendarも面白そうだけど、あそこに名前を連ねるだけのネタは・・・難しいなぁ。