Unixの歴史を再現したリポジトリを読む④

V4

V4のタイムスタンプは1973年11月29日。V4ではsysとmanの2つのディレクトリがルートにあり、sysの中にken、dmr、junkの3つのサブディレクトリが掘られました。

このバージョンから全面的にCで書き直されています。これまでカーネルやコマンドはケン・トンプソン、コンパイラはデニス・リッチーという住みわけができていましたが、本格的に共同作業することになったということでしょうか。機能単位ではなくてプログラマ単位でディレクトリを分けるのは奇妙な感じがしますが、バージョンコントロールができていなかった時代は、他の人が書いたコードをデグレードさせてしまうことを避けるのに有効な手段の1つでした。

C言語

V4のリポジトリにはコンパイラが入っておらず、Cで書かれたコードが見つかるだけです。

プリプロセッサ

cat.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コンパイラの移植性が高まったことが示されています。その中でマクロを使うとコンパイルが遅くなるという、自己批判ともとれる記述があります。

ヘッダファイル

file.h

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コードが入っていますが、これらのサブディレクトリにはヘッダファイルがありません。

システムコール

sysent.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, &gtime,			/* 13 = time */
	3, &mknod,			/* 14 = mknod */
	2, &chmod,			/* 15 = chmod */
	2, &chown,			/* 16 = chown */
…
	0, &nosys,			/* 42 = pipe */
…
	0, &prproc			/* 63 = special */
};

システムコールのエントリーベクタテーブル。ポインタをintとして扱えるようです。キャストしているコードは見当たらず、まだキャストはなかったようです。

パイプが実装されたのはもっと後だと思われますが、パイプ用のシステムコールがリザーブされています。

sys3.c

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.c

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で決め打ちされているのが気になります。

malloc.c

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関数はヒープ管理領域のマップを引数に取りますが、これはどこで初期化されているのでしょうか。

systm.h

int	coremap[CMAPSIZ];
int	swapmap[SMAPSIZ];

param.h

#define	CMAPSIZ	100
#define	SMAPSIZ	100

ヒープエリアの管理ブロックはcoremapとswapmapの2つがデフォルトで定義されていました。ブロック数は100固定です。

main.c

#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にありますので、範囲外であり、デバイスのレジスタにアクセスしているわけではなさそうです。

fio.c

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個までだったようです。

プロセス

proc.h

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個で固定です。

sig.c

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);
		}
	}
}

各プロセス間はシグナルで通信できるようになっています。

param.h

#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のシグナルと基本的に変わっていないようです。

low.s

/ 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ディレクトリに関する気配が全くありません。

conf.c

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つに対応しています。ドライバを動的に登録できるようには見えません。

conf.h

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などはありません。

vt.c

#
/*
 * 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)