V4
V4のタイムスタンプは1973年11月29日。V4ではsysとmanの2つのディレクトリがルートにあり、sysの中にken、dmr、junkの3つのサブディレクトリが掘られました。
このバージョンから全面的にCで書き直されています。これまでカーネルやコマンドはケン・トンプソン、コンパイラはデニス・リッチーという住みわけができていましたが、本格的に共同作業することになったということでしょうか。機能単位ではなくてプログラマ単位でディレクトリを分けるのは奇妙な感じがしますが、バージョンコントロールができていなかった時代は、他の人が書いたコードをデグレードさせてしまうことを避けるのに有効な手段の1つでした。
C言語
V4のリポジトリにはコンパイラが入っておらず、Cで書かれたコードが見つかるだけです。
プリプロセッサ
#
/*
* GP DR11C driver used for C/A/T
*/
#include "/sys/nsys/param.h"
#include "/sys/nsys/user.h"
#include "/sys/nsys/tty.h"
#define CATADDR 0167750
#define PCAT 9
struct {
int catlock;
struct clist oq;
} cat;
struct {
int catcsr;
int catbuf;
};
ctopen(dev)
{
if (cat.catlock==0) {
cat.catlock++;
CATADDR->catcsr =| IENABLE;
} else
u.u_error = ENXIO;
}
ctclose(dev)
{
cat.catlock = 0;
}
C言語にはincludeとdefineのディレクティブが実装されました。つまりプリプロセッサができました。V3にあるCコンパイラのソースコードにはプリプロセッサに関するコードがなく、V4で新たに追加されたものです。
AT&Tでプリプロセッサやマクロの導入を希望したのはアラン・スナイダーという人物だと言われています。今ではマクロはC言語の汚点の1つと言われており、C++で導入されたテンプレートで様々な不備が直されて、ジェネリックプログラミングができるようになりました。このテンプレートはJavaやC#にも導入され、テンプレートの構文の見本となっています。
そこで面白いのは、C++がテンプレートを導入する際にもこのアラン・スナイダーという人物が関わっている点です。つまりこの人は、1973年頃にはすでにジェネリックプログラミングのアイデアを持っていたと思われ、マクロは当時の現実的な実装方法という位置づけに過ぎなかったのかもしれません。
アラン・スナイダーの論文が残っています。当時はOSを書けるのはアセンブラだけという常識があり、OSは機種依存であるのが当然でした。当時の高級言語はポインタなどがなくOSの記述には適しませんでした。しかしUNIXによってCでOSを書けることが分かりました。この論文ではC言語のコンパイラが抽象コードの中間言語を出力するようにすることで、Cコンパイラの移植性が高まったことが示されています。その中でマクロを使うとコンパイルが遅くなるという、自己批判ともとれる記述があります。
ヘッダファイル
struct file {
char f_flag;
char f_count;
int f_inode;
char *f_offset[2];
} file[NFILE];
/* flags */
#define FREAD 01
#define FWRITE 02
そしてヘッダファイルもV4で初登場。cソースコードがヘッダファイルにより構造体やマクロ定義を共有できるようになりました。一方関数宣言はどのヘッダファイルにも見当たりません。またサブディレクトリの方にcコードが入っていますが、これらのサブディレクトリにはヘッダファイルがありません。
システムコール
int sysent[]
{
0, &nullsys, /* 0 = indir */
0, &rexit, /* 1 = exit */
0, &fork, /* 2 = fork */
2, &read, /* 3 = read */
2, &write, /* 4 = write */
2, &open, /* 5 = open */
0, &close, /* 6 = close */
0, &wait, /* 7 = wait */
2, &creat, /* 8 = creat */
2, &link, /* 9 = link */
1, &unlink, /* 10 = unlink */
2, &exec, /* 11 = exec */
1, &chdir, /* 12 = chdir */
0, >ime, /* 13 = time */
3, &mknod, /* 14 = mknod */
2, &chmod, /* 15 = chmod */
2, &chown, /* 16 = chown */
…
0, &nosys, /* 42 = pipe */
…
0, &prproc /* 63 = special */
};
システムコールのエントリーベクタテーブル。ポインタをintとして扱えるようです。キャストしているコードは見当たらず、まだキャストはなかったようです。
パイプが実装されたのはもっと後だと思われますが、パイプ用のシステムコールがリザーブされています。
chmod()
{
int *ip;
extern uchar;
ip = namei(&uchar, 0);
if(ip == NULL)
return;
if(owner(ip)) {
ip->i_mode =& ~07777;
ip->i_mode =| u.u_arg[1]&07777;
ip->i_flag =| IUPD;
}
iput(ip);
}
chmodもC言語になりました。毎回chmodをサンプルに選んでいるのは、適度に小さくてサンプルに都合がよいからで、それ以上の意味はありません。
ヒープ
alloc(dev)
{
int bno, i, *fp;
int *bp, *ip;
fp = getfs(dev);
while(fp->s_flock)
sleep(&fp->s_flock, PINOD);
bno = fp->s_free[--fp->s_nfree];
if(bno == 0) {
fp->s_nfree++;
printf("No space on dev %d\n", dev);
u.u_error = ENOSPC;
return(NULL);
}
if(fp->s_nfree <= 0) {
fp->s_flock++;
bp = bread(dev, bno);
ip = bp->b_addr;
fp->s_nfree = ip[0];
for(i=0; i<100; i++)
fp->s_free[i] = ip[i+1];
brelse(bp);
fp->s_flock = 0;
wakeup(&fp->s_flock);
}
bp = getblk(dev, bno);
clrbuf(bp);
return(bp);
}
メモリ管理に関する何かを探れるかと思い、allocという関数を覗いてみましたが、これはメモリを確保する関数ではなくて、ディスクのスペースを確保するための関数のようです。ブロック数(ファイル数?)が100で決め打ちされているのが気になります。
struct map {
char *m_size;
char *m_addr;
};
malloc(mp, size)
struct map *mp;
{
register int a;
register struct map *bp;
for (bp = mp; bp->m_size; bp++) {
if (bp->m_size >= size) {
a = bp->m_addr;
bp->m_addr =+ size;
if ((bp->m_size =- size) == 0)
do {
bp++;
(bp-1)->m_addr = bp->m_addr;
} while ((bp-1)->m_size = bp->m_size);
return(a);
}
}
return(0);
}
デニス・リッチーのフォルダにmallocがありました。これが現存する最古のmallocか。仮想メモリの対応は1978年のBSD4からなのでもっと先の話です。
空きブロック情報を管理しているmapはリストではなくて配列。前から順に検索し、確保したいサイズのスペースが見つかったらそこに確保するというファーストマッチ方式の原始的なアルゴリズム。もしスペースのサイズと確保したサイズが同じだったら、それ以降のブロックを全部前に詰めてます。今の基準で昔の設計を批判するのは愚行ですが、まぁ率直に言って、効率最悪です。
malloc関数はヒープ管理領域のマップを引数に取りますが、これはどこで初期化されているのでしょうか。
int coremap[CMAPSIZ];
int swapmap[SMAPSIZ];
#define CMAPSIZ 100
#define SMAPSIZ 100
ヒープエリアの管理ブロックはcoremapとswapmapの2つがデフォルトで定義されていました。ブロック数は100固定です。
#define KISA 0172340
#define UISD 0177600
#define UISA 0177640
…
struct {
int r[8];
};
…
main()
{
extern schar;
extern char end[], data[], etext[];
int i, i1, *p;
/*
* zero and free all of core
*/
UISA->r[0] = KISA->r[6] + USIZE;
UISD->r[0] = 6;
for(; fubyte(0) >= 0; UISA->r[0]++) {
clearseg(UISA->r[0]);
mfree(coremap, 1, UISA->r[0]);
}
mfree(swapmap, NSWAP, SWPLO);
/*
* set up system process
*/
proc[0].p_addr = KISA->r[6];
proc[0].p_size = USIZE;
proc[0].p_stat = SRUN;
proc[0].p_flag =| SLOAD|SSYS;
u.u_procp = &proc[0];
coremapは管理ブロック、つまりメタデータの配列に過ぎません。メモリは別の場所にあるはずです。
KISAはカーネル上のレジスタ、UISAはユーザーモード上のレジスタがバックアップされているものと思われます。PDP-11にはR0からR7までの8つのレジスタがあり、R6はスタックポインタ、R7はプログラムカウンタで、r[6]はスタックポインタを指しているものと思われます。USIZEは8となっています。しかしもしこれが正解でも、KISAを初期化する処理が見つからないため意図を汲めず、上記のコードがどのように動くのか説明できません。1バイトずつmfreeしていますので、これで領域全体を呼べばすべて1つの空きブロックになる、という予測は立ちます。
PDP-11/20のマニュアルなどを調べてみましたが、これらのアドレスについては特に言及がなく、推測の域を出ません。I/Oのメモリマップは0 77x xxxにありますので、範囲外であり、デバイスのレジスタにアクセスしているわけではなさそうです。
falloc()
{
register struct file *fp;
register int i;
if ((i = ufalloc()) < 0)
return(NULL);
for (fp = &file[0]; fp < &file[NFILE]; fp++)
if (fp->f_count==0) {
u.u_ofile[i] = fp;
fp->f_count++;
return(fp);
}
printf("no file\n");
u.u_error = ENFILE;
return(NULL);
}
ファイル領域を確保するfallocという関数もありましたのでついでに紹介しておきます。ファイル数も100個までだったようです。
プロセス
struct proc {
char p_stat;
char p_flag;
char p_pri;
char p_sig;
char p_ndis;
char p_cook;
int p_ttyp;
int p_pid;
int p_ppid;
int p_addr;
int p_size;
int p_wchan;
int *p_textp;
} proc[NPROC];
/* stat codes */
#define SSLEEP 1
#define SWAIT 2
#define SRUN 3
#define SIDL 4
#define SZOMB 5
/* flag codes */
#define SLOAD 01
#define SSYS 02
#define SLOCK 04
#define SSWAP 010
プロセスとその状態はprocで定義されています。最大プロセス数は50個で固定です。
psignal(p, sig)
int *p;
{
register *rp;
rp = p;
rp->p_sig = sig;
if(rp->p_stat == SWAIT) {
rp->p_wchan = 0;
rp->p_stat = SRUN;
if(runout) {
runout = 0;
wakeup(&runout);
}
}
}
各プロセス間はシグナルで通信できるようになっています。
#define SIGHUP 1
#define SIGINT 2
#define SIGQIT 3
#define SIGINS 4
#define SIGTRC 5
#define SIGIOT 6
#define SIGEMT 7
#define SIGFPT 8
#define SIGKIL 9
#define SIGBUS 10
#define SIGSEG 11
#define SIGSYS 12
シグナルの定義は12種類。今のPOSIXのシグナルと基本的に変わっていないようです。
/ trap vectors
trap; br7+0 / bus error
trap; br7+1 / illegal instruction
trap; br7+2 / bpt-trace trap
trap; br7+3 / iot trap
trap; br7+4 / power fail
trap; br7+5 / emulator trap
trap; br7+6 / system entry
. = 240^.
trap; br7+7 / programmed interrupt
trap; br7+10 / floating point
trap; br7+11 / segmentation violation
割り込みベクタテーブル。タイマー割込みはないようです。プロセスのコンテキストスイッチはシグナルの送信など特定のシステムコールを呼んだ時だけに発生するノンプリエンプティブ方式のように思われます。
コンテキストスイッチをするにはレジスタをバックアップしたりレストアしたりするコードがあるはずですが見つかりません。
どうしたものかと思いGoogleに助けを求めたところ、有難いことにUNIX読書会とその参加者の皆さんのサイトが見つかりました。
Lions' Commentary on UNIX 読書会
https://sites.google.com/site/lionscommentaryonunixreading/home
UNIX 6th code reading - プロセス (やる気のないはてだ(A boring diary))
https://takahirox.hatenadiary.org/entry/20110108/1294503538
これを読んで驚かされたのは、バージョン6でもまだプロセスの個数が50個までだったということ。まもなく可変長になるだろうと期待していたのですが…。
各種テーブルの個数が固定なのは当時のコンピュータの性能上止むを得ません。そんなにたくさんリソースが無いというのもありますし、可変長にするとコード量が増えますので貴重なメモリスペースが逼迫します。
UNIX 6th code reading - クロック割り込み
https://takahirox.hatenadiary.org/entry/20110211/1297403488
タイマーによるプロセスのコンテキストスイッチはclock関数で実装されていました。しかしどこからも呼ばれていません。takahiroxさんの記事によるとPDP11/40はno opとあります。V4はコメントからPDP-11/20がターゲットだったと思われ、PDP-11にはタイマー割込みがない等の理由で実装できなかったのでしょう。
しかしclock関数があるということは、この時すでにPDP-11以外の機種への移植も進んでいたのでしょうか。アセンブラからC言語に乗り換えているのも関連があるでしょう。
ドライバ
V2まではinit.sでデバイスをマウントしており、devディレクトリに関係する文字列が見えたりしましたが、V4のコードではdevディレクトリに関する気配が全くありません。
int (*cdevsw[])()
{
&klopen, &klclose, &klread, &klwrite, &klsgtty,
&dcopen, &dcclose, &dcread, &dcwrite, &dcsgtty,
&pcopen, &pcclose, &pcread, &pcwrite, &nodev,
&dpopen, &dpclose, &dpread, &dpwrite, &nodev,
&dnopen, &dnclose, &nodev, &dnwrite, &nodev,
&nulldev, &nulldev, &mmread, &mmwrite, &nodev,
&vtopen, &vtclose, &nodev, &vtwrite, &nodev,
&daopen, &daclose, &daread, &dawrite, &nodev,
&ctopen, &ctclose, &nodev, &ctwrite, &nodev,
&vsopen, &vsclose, &vsread, &vswrite, &nodev,
&nodev, &nodev, &nodev, &nodev, &nodev
};
デバイスドライバはcdevswというテーブルに関数テーブルが列挙されていました。各1行がドライバ1つに対応しています。ドライバを動的に登録できるようには見えません。
struct
{
char d_minor;
char d_major;
};
struct
{
int (*d_open)();
int (*d_close)();
int (*d_strategy)();
} bdevsw[];
struct
{
int (*d_open)();
int (*d_close)();
int (*d_read)();
int (*d_write)();
int (*d_sgtty)();
} cdevsw[];
cdevswの要素は上記のようになっています。ioctlなどはありません。
#
/*
* VT01 driver via DR11C to 11/20
*/
#include "/sys/nsys/param.h"
#include "/sys/nsys/user.h"
int vtflag;
struct vtreg {
int csr;
int buf;
};
#define VTADDR 0167770
#define RQINT 01
#define BIENABL 040
#define SEOF 0100000
#define VTPRI 8
vtopen(dev, flag)
{
if (!flag)
u.u_error = ENXIO;
else
VTADDR->csr = BIENABL;
}
vtclose()
{
VTADDR->buf = SEOF;
VTADDR->csr =| RQINT;
}
vtwrite()
{
int c;
int register count;
while (cpass(&c) >= 0) {
retry:
for (count=0; count<10; count++)
if ((VTADDR->csr&RQINT)==0) {
VTADDR->buf = c&0377;
VTADDR->csr =| RQINT;
goto contin;
}
spl5();
if (VTADDR->csr&RQINT) {
vtflag++;
sleep(VTADDR, VTPRI);
}
spl0();
goto retry;
contin:;
}
}
vtintr()
{
VTADDR->csr =& ~RQINT;
if (vtflag) {
vtflag = 0;
wakeup(VTADDR);
}
}
デニス・リッチーのフォルダは大半がデバイスドライバでした。このvtドライバは特に小さかったのでサンプルとして掲載しておきます。
終わり？
V4を読んでわかったのは、基本的にV6とほとんど違いがなく、そしてV6に関しては巷に解説本が出ている、ということでした。V4はまだパイプも仮想メモリもなく、まだ進化の途中ではありますが、これ以上は解説しても限りなくV6に近づいていくだけだと思われますので、それならV6の解説本を読むのがよいということになりそうです。
バックナンバー
[Unixの歴史を再現したリポジトリを読む①] (https://qiita.com/hayashida-katsutoshi/items/37afd9acbce117aa223c)
[Unixの歴史を再現したリポジトリを読む②] (https://qiita.com/hayashida-katsutoshi/items/3c4bc05ab4c627286be8)
[Unixの歴史を再現したリポジトリを読む③] (https://qiita.com/hayashida-katsutoshi/items/eb80ebd5667af10193f5)
[Unixの歴史を再現したリポジトリを読む④] (https://qiita.com/hayashida-katsutoshi/items/5edde08b01b81dac26b7)
[Unixの歴史を再現したリポジトリを読む⑤] (https://qiita.com/hayashida-katsutoshi/items/df9c08c4c5011f04b45e)