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

リポジトリの分析は秒単位でコミットの差分を比較しまくるのがセオリー。gitのGUIクライアントでマウスを連打するわけですが、UNIX再現リポジトリはとにかく巨大なのでうまくいきません。GitKrakenやForkはヒストリが最後まで表示できず、SmartGitはWindows 10 20H1 2004と相性が悪くて落ちます。止むを得ずdiffを取ったり、2か所にpullして両者を比較するという、原始的な方法で調べています。

# V1
最初のコミットは1970年6月ですが、次のコミットはいきなり1972年6月に飛びます。昔のコードですので、残っているだけでも奇跡なわけですが。

``` bash
uiweo@DESKTOP-HP MINGW64 /d/Users/uiweo/Documents/unix-history-repo2 (Research-V1-Snapshot-Development)
$ ls
init.s sh.s  u0.s  u1.s  u2.s  u3.s  u4.s  u5.s  u6.s  u7.s  u8.s  u9.s  ux.s
```

ファイル数が激減しています。どうやらPDP-11で書き直すために仕切りなおしたという事のようです。

sh.sはシェルです。この時点でシェルが登場。

PDP-7はシェル無しでどうやって操作していたのでしょうか。PDP-7版のコードを見ると、init.sにshというラベルへの参照があり、shをopenしていますが、その実態を定義しているファイルは見当たりません。欠損しているのかもしれません。

## システムコール

``` asm:u2.s
syschmod: / name; mode
	jsr	r0,isown / get the i-node and check user status
	bit	$40000,i.flgs / directory?
	beq	2f / no
	bic	$60,r2 / su & ex / yes, clear set user id and 
				 / executable modes
2:
	movb	r2,i.flgs / move remaining mode to i.flgs
	br	1f
```

システムコールのchmodはsyschmodになりました。やはり紛らわしかったという事でしょうか。

コード内には1:、2:、3:といった数字だけのラベルが頻繁に重複しています。`beq 2f`は次の2:へジャンプ、`beq 2b`は前の2:へジャンプするようです。

このバージョンではコメントが劇的に増えて読みやすくなっています。アセンブラはコメントが無いと書いている本人でも読むのが大変になります。

``` u3.s
copyz:
       mov     r1,-(sp) / put r1 on stack
       mov     r2,-(sp) / put r2 on stack
       mov     (r0)+,r1
       mov     (r0)+,r2
1:
       clr     (r1)+ / clear all locations between r1 and r2
       cmp     r1,r2 
       blo     1b
       mov     (sp)+,r2 / restore r2
       mov     (sp)+,r1 / restore r1
       rts     r0 
```

アセンブラのニモニックはPDP-7より格段に読みやすくなっています。`mov r1,-(sp)`はスタックポインタが指し示すデータをメモリからロードしてレジスタr1に代入し、同時にspをデクリメントしています。68000っぽくなっています。PDP-11を作ったDECは、その後VAXを作り、それが68000のモデルになっていますので、VAX版ではさらに68000に近づくだろうと思われます。

## ディレクトリ
``` u0.s
/ root

	41.
	140016
	.byte 7,1
	9f-.-2
	41.
	<..\0\0\0\0\0\0>
	41.
	<.\0\0\0\0\0\0\0>
	42.
	<dev\0\0\0\0\0>
	43.
	<bin\0\0\0\0\0>
	44.
	<etc\0\0\0\0\0>
	45.
	<usr\0\0\0\0\0>
	46.
	<tmp\0\0\0\0\0>
9:

/ device directory

	42.
	140016
	.byte 2,1
	9f-.-2
	41.
	<..\0\0\0\0\0\0>
	42.
	<.\0\0\0\0\0\0\0>
	01.
	<tty\0\0\0\0\0>
	02.
	<ppt\0\0\0\0\0>
	03.
	<mem\0\0\0\0\0>
	04.
	<rf0\0\0\0\0\0>
	05.
	<rk0\0\0\0\0\0>
	06.
	<tap0\0\0\0\0>
	07.
	<tap1\0\0\0\0>
	08.
	<tap2\0\0\0\0>
	09.
	<tap3\0\0\0\0> 
	10.
	<tap4\0\0\0\0>
	11.
	<tap5\0\0\0\0>
	12.
	<tap6\0\0\0\0>
	13.
	<tap7\0\0\0\0>
	14.
	<tty0\0\0\0\0>
	15.
	<tty1\0\0\0\0>
	16.
	<tty2\0\0\0\0>
	17.
	<tty3\0\0\0\0>
	18.
	<tty4\0\0\0\0>
	19.
	<tty5\0\0\0\0>
	20.
	<tty6\0\0\0\0>
	21.
	<tty7\0\0\0\0>
	22.
	<lpr\0\0\0\0\0>
	01.
	<tty8\0\0\0\0> / really tty
9:

/ binary directory

	43.
	140016
	.byte 2,3
	9f-.-2
	41.
	<..\0\0\0\0\0\0>
	43.
  	<.\0\0\0\0\0\0\0>
9:

/ etcetra directory

	44.
	140016
	.byte 2,3
	9f-.-2
	41.
	<..\0\0\0\0\0\0>
	44.
	<.\0\0\0\0\0\0\0>
	47.
	<init\0\0\0\0>
9:

/ user directory

	45.
	140016
	.byte 2,1
	9f-.-2
	41.
	<..\0\0\0\0\0\0>
	45.
	<.\0\0\0\0\0\0\0>
9:

/ temporary directory

	46.
	140017
	.byte 2,1
	9f-.-2
	41.
	<..\0\0\0\0\0\0>
	46.
	<.\0\0\0\0\0\0\0>
9:
```

ディレクトリ構造はu0.sでハードコーディングされています。ファイル名は8文字の固定長。各ディレクトリに.と..が定義されています。デバイスドライバはdevディレクトリにまとめられました。rk0はディスクドライブのドライバです。

ディスクにファイルを作って読み書きすることは、システムコールを見る限りではできるような感じがしますが…。

## デバイスドライバ
``` asm:init.s
ctty:	</dev/tty\0>
shell:	</bin/sh\0>
shellm:	<-\0>
tapx:	</dev/tapx\0>
rk0:	</dev/rk0\0>
utmp:	</tmp/utmp\0>
wtmp:	</tmp/wtmp\0>
ttyx:	</dev/ttyx\0>
getty:	</etc/getty\0>
usr:	</usr\0>
```

init.sにドライバのパスの文字列が入っています。

アセンブラの文字列リテラルの構文はPDP-7版から改善されています。`<sy>;<st>;<em>; 040040`のように2文字ずつペアにする必要が無くなっています。

``` asm:init.s
	movb	r1,tapx+8 / mode of dec tape drive x, where
	sys	chmod; tapx; 17 / x=0 to 7, to read/write by owner or
	inc	r1 / non-owner mode
	cmp	r1,$'8 / finished?
	blo	1b / no
	sys	mount; rk0; usr / yes, root file on mounted rko5
				/ disk ls /usr
	sys	creat; utmp; 16 / truncate /tmp/utmp
	sys	close / close it
	movb	$'x,zero+8. / put identifier in output buffer
	jsr	pc,wtmprec / go to write accting info
	mov	$itab,r1 / address of table to r1
```

`sys mount; rk0;`でrk0をマウントしています。

Linuxで言う所のinit.dディレクトリみたいなものはなく、init.sでドライバのインストールをハードコーディングしているようです。

``` asm:init.s
	clr	r0 / yes
	sys	close / close current read
	mov	$1,r0 / and write
	sys	close / files
	sys	open; ctty; 0 / open control tty
	sys	open; ctty; 1 / for read and write
	sys	exec; shell; shellp / execute shell
	br	help / keep trying
```

標準入出力のttyは、PDP-7番ではttyinとttyoutの2つに分かれていましたが、cttyの1つにまとめられたようです。

これらのドライバの実体がどこに入っているのかは、私の知識不足と忍耐力不足で見つけられませんでした。ていうか、1か所にまとまっておらずu7.sやu8.sに他のドライバとごっちゃになって混ざっているような感じです。

# V2

``` bash
uiweo@DESKTOP-HP MINGW64 /d/Users/uiweo/Documents/unix-history-repo ((Research-V2))
$ ls
c/  cmd/  lib/
```

V2ではついにディレクトリが掘られました。

## cmd

```
uiweo@DESKTOP-HP MINGW64 /d/Users/uiweo/Documents/unix-history-repo/cmd ((Research-V2))
$ ls
a1.s   a3.s  a6.s  a9.s    as25.s  bas0.s  cc.c     cmp.s    date.s  db3.s  dsw.s   fstrip.s  if.c    ld2.s  login.s
a2.s   a4.s  a7.s  acct.s  as8.s   bas1.s  chmod.s  colon.s  db1.s   db4.s  dusg.s  getty.s   init.s  ldx.s  ls.s
a21.s  a5.s  a8.s  ar.s    as9.s   cat.s   chown.s  cp.c     db2.s   df.s   fc.c    glob.c    ld1.s   ln.s
```

cmdディレクトリにはカーネルとコマンドが入っています。カーネルはフルアセンブラですが、コマンドの一部はCで書かれています。

login機能がここで登場しています。globはワイルドカードを処理しています。シェルはファイルとしては見当たりません。

``` c:if.c
main(argc, argv)
char *argv[];
{
	int np, i, c;
	char *nargv[50], *ncom, *na, *nxtarg();

	ac = argc;
	av = argv;
	if (ac<2) return;
	ap = 1;
	if (exp()) {
		np = 0;
		while (na=nxtarg())
			nargv[np++] = na;
		nargv[np] = 0;
		if (np==0) return;
		execv(nargv[0], nargv, np);
		i = 0;
		ncom = "/usr/bin/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
		while(c=nargv[0][i])  {
			ncom[9+i++] = c;
		}
		ncom[9+i] = '\0';
		execv(ncom+4, nargv, np);
		execv(ncom, nargv, np);
		write(1, "no command\n", 11);
		seek(0, 0, 2);
	}
}
```

ifコマンド。B言語からC言語に進化して、変数に型ができています。引数の型は関数定義の下に書く初期の方式。

ncomでバッファをxxxxの形で確保して、コマンドラインの引数を上書きして文字列をビルドするという、リーナス・トーバルスが見たらFワードで激怒するようなコードです。バッファオーバーランのチェックもありません。

/usr/binディレクトリが既に存在していることが見て取れます。

``` c:if.c
char *nxtarg() {
	if (ap>ac) return(0*ap++);
	return(av[ap++]);
}
```

nxtarg関数は標準関数ではありません。argcから要素を1つ取り出すだけの関数です。

## c

``` c:c00.c
main(argc, argv)
int argv[]; {
	extern init, flush;
	extern extdef, eof, open, creat;
	extern fout, fin, error, exit, nerror, tmpfil;

	if(argc<4) {
		error("Arg count");
		exit(1);
	}
	if((fin=open(argv[1],0))<0) {
		error("Can't find %s", argv[1]);
		exit(1);
	}
	if((fout=creat(argv[2], 017))<0) {
		error("Can't create %s", argv[2]);
		exit(1);
	}
	tmpfil = argv[3];
	init("int", 0);
	init("char", 1);
	init("float", 2);
	init("double", 3);
/*	init("long", 4);  */
	init("auto", 5);
	init("extern", 6);
	init("static", 7);
	init("goto", 10);
	init("return", 11);
	init("if", 12);
	init("while", 13);
	init("else", 14);
	init("switch", 15);
	init("case", 16);
	init("break", 17);
	init("continue", 18);
	init("do", 19);
	init("default", 20);
	while(!eof) {
		extdef();
		blkend();
	}
	flush();
	flshw();
	exit(nerror!=0);
}
```

cディレクトリにはC言語コンパイラが入っていました。型はint、char、float、double、long、autoをサポートしているようです。ぶっちゃけ全体的にハードコーディング。B言語には既にyaccがあったはずですが。

C言語のコンパイラは最初からC言語で書かれていました。若干アセンブラも混ざっていますが基本的にはデータです。

``` c:t.c
main() {
	extern a, b, c, i;
	float a, b;
	double c;
	int i;

	a = b;
	a = b*c;
	a = b*c/a;
	a = c;
	c = a;
	a = c*c+a;
	a = 1;
	a = a+1;
	i = a;
	i = c;
	a++;
	c++;
}
```
付属のテストコード。変数を表示する処理がありません。コンパイル結果を確認するためのコードだったのか、それとも既に当時からデバッガを使えたのでしょうか？

cmdディレクトリにあるdb1～db3がデバッガのコードでした。ただしこのデバッガは、ステップ実行やブレークなどができるインタラクティブなものではなく、コアダンプからスタックトレースや逆アセンブルを表示できる静的なツールだったようです。コアダンプのファイル名はcore固定。シンボルはa.outからインポートする形です。

ということはどこかにcoreを吐くコードもありそうですが、見つからないですね。

``` asm:regtab.s
/ c code tables-- compile to register

fp = 1		/ enable floating-point

.globl	_regtab

_regtab=.; .+2
	20.;	cr20
	21.;	cr20
	22.;	cr20
	30.;	cr30
	31.;	cr30
	32.;	cr32
	33.;	cr32
	34.;	cr34
	35.;	cr35
	29.;	cr29
	36.;	cr36
	37.;	cr37
	38.;	cr38
	101.;	cr100
	80.;	cr80
	40.;	cr40
	41.;	cr40	/ - like +
	42.;	cr42
	43.;	cr43
	44.;	cr43
	45.;	cr45
	46.;	cr45
	47.;	cr47
	48.;	cr48
	60.;	cr60
	61.;	cr60
	62.;	cr60
	63.;	cr60
	64.;	cr60
	65.;	cr60
	66.;	cr60
	67.;	cr60
	68.;	cr60
	69.;	cr60
	70.;	cr70
	71.;	cr70
	72.;	cr72
	73.;	cr73
	74.;	cr73
	75.;	cr75
	76.;	cr75
	77.;	cr77
	78.;	cr78
	102.;	cr102
	97.;	cr97
	0
```

コンパイラが中間コードを書き出すようになったのか。解読に挑戦してみます。

上記のテーブルは中間コード一覧テーブルのようです。regtabの他にもcctab、fptab、sptabというテーブルがあります。

``` asm:regtab.s
/ !
cr34:
%n,n
	FC
	beq	1f
	clr	R
	br	2f
1:	mov	$1,R
2:

/ &unary
cr35:
%a,n
	mov	$A1,R

/ & unary of auto
cr29:
%e,n
	mov	r5,R
	add	Z,R
```

各テーブルはこうしたコードの断片を参照しているようです。%で示される行が何を意味しているのかは不明です。/はコメントです。

``` c:c02.c
		/* goto */
		case 10:
			o1 = block(1,102,0,0,tree());
			rcexpr(o1, regtab);
			goto semi;

		/* return */
		case 11:
			if((peeksym=symbol())==6)	/* ( */
				rcexpr(pexpr(), regtab);
			retseq();
			goto semi;
```

regtabはこんな感じで参照されています。rcexprという関数に渡されています。この中でテーブルを引いて、コードを出力するのでしょうか?

``` c:c03.c
rcexpr(tree, table)
int tree[], table;
{
	extern space, ospace, putwrd, putchar, line;
	int c, sp[];

	putchar('#');
	c = space-ospace;
	c =/ 2;		/* # addresses per word */
	sp = ospace;

	putwrd(c);
	putwrd(tree);
	putwrd(table);
	putwrd(line);
	while(c--)
		putwrd(*sp++);
}
```

楽をしようとググってみたらデニス・リッチーの論文を発見。rcexpr関数の説明があります。

https://barfooze.de/stuff/v7/v7vol2b.pdf

これによると、式を示すツリーへのポインタ、コード生成テーブルの名前、式に割り当てられるレジスタの個数という3つの引数があり、実際に割り当てられたレジスタの数が返ってきます。これを基に命令を生成するのは呼び出し側の仕事だそうです。

regtabは基本となる式テーブル、cctabは制御構文用のテーブル、sptabは関数を呼び出してスタックを操作する処理のテーブル、efftabは代入文などのテーブルとなっています。

ということは、パーサーがツリーを作成したら、テーブルを引きながらアセンブラのコードを出力していく、という構造になっているようです。またここで言うアセンブラのコードは、バイナリではなくて、PDP-11用アセンブラのソースコードになります。BCPL以降のコンパイラは中間コードを一度出力する設計が主流になりましたが、この頃はまだ過渡期であり、最初のC言語はまだ中間コードを出力するスタイルではなかったようです。

rcexpr関数の説明で、引数が3つあるのに、c03.cのコードには引数が2つしかないじゃないかと思った人は鋭いです。実はrcexpr関数はもう1つあります。

``` c:c10.c
rcexpr(tree, table, reg)
int tree[]; {
	extern cexpr, regtab, cctab, sptab, printf, error;
	extern jumpc, cbranch;

	if(tree==0)
		return;
	if(*tree >= 103) {
		(*tree==103?jumpc:cbranch)(tree[1],tree[2],tree[3],0);
		return;
	}
	if (cexpr(tree, table, reg))
		return;
	if (table!=regtab) 
		if(cexpr(tree, regtab, reg)) {
			if (table==sptab)
				printf("mov	r%d,-(sp)\n", reg);
			if (table==cctab)
				printf("tst	r%d\n", reg);
			return;
		}
	error("No match for op %d", *tree);
}

cexpr(tree, table, reg)
int tree[][], table[]; {
	extern match, nreg, printf, pname, putchar, regtab;
	extern sptab, cctab, rcexpr, prins, rlength, popstk;
	extern collcon, isn, label, branch, cbranch, fltmod;
	int p1[], p2[], c, r, p[], otable[], ctable[], regtab[], cctab[];
	char string[], match[];

	if ((c = *tree)==100) {		/* call */
		p1 = tree[3];
		p2 = tree[4];
		r = 0;
		if(p2) {
			while (*p2==9) { /* comma */
				rcexpr(p2[4], sptab, 0);
				r =+ rlength((p=p2[4])[1]);
				p2 = p2[3];
			}
			rcexpr(p2, sptab, 0);
			r =+ rlength(p2[1]);
		}
		*tree = 101;
		tree[2] = r;		/* save arg length */
	}
…
```

何が書いてあるのかさっぱりわかりません。cサブディレクトリの下にはnc0とnc1という2つのサブディレクトリがあり、それぞれ別バージョンのコンパイラが入っていたようです。すっきりしているのがnc0、ぐちゃぐちゃなのがnc1です。この後のV3ではnc1が消えてnc0だけになっています。

## lib
libディレクトリにはC言語のライブラリが入っています。ほとんどアセンブラで書かれていますが、一部だけC言語で書かれています。

``` asm:chmod.c
/ C library -- chmod

/ error = chmod(string, mode);

	.globl	_chmod

.data
_chmod:
	1f
.text
1:
	mov	2(sp),0f
	mov	4(sp),0f+2
	clr	r0
	sys	chmod; 0:..; ..
	adc	r0
	rts	pc
```

chmod関数のライブラリ。C言語から呼び出されると、引数をスタックからロードしてシステムコールのchmodを呼んでいます。現代のシステムコール関数とか、WindowsのAPIなんかも基本的にはこの形になっています。

``` c:printf.c
printf(fmt,x1,x2,x3,x4,x5,x6,x7,x8,x9)
	char fmt[];
	{
	extern printn, putchar;
	char s[];
	auto adx[], x, c;

	adx = &x1; /* argument pointer */
loop:
	while((c = *fmt++) != '%') {
		if(c == '\0')
			return;
		putchar(c);
	}
	x = *adx++;
	switch (c = *fmt++) {

	case 'd': /* decimal */
	case 'o': /* octal */
		if(x < 0) {
			x = -x;
			if(x<0) {  	/* is - infinity */
				if(c=='o')
					printf("100000");
				else
					printf("-32768");
				goto loop;
			}
			putchar('-');
		}
		printn(x, c=='o'?8:10);
		goto loop;

	case 'c': /* char */
		putchar(x);
		goto loop;

	case 's': /* string */
		s = x;
		while(c = *s++)
			putchar(c);
		goto loop;
	}
	putchar('%');
	fmt--;
	adx--;
	goto loop;
}
```
こちらは恐らく現存する最古でオリジナルのprintf関数。まだ%xのフォーマットがないですね。ちなみにCコンパイラの中にもprintfの微妙に違う別バージョンが入っています。

まだこの時点ではincludeがありません。各ライブラリのリンクはexternコマンドに頼っています。またリンカーはありません。実行ファイルとライブラリがどうやってリンクされているのかは不明です。システムコールとごっちゃになっている様子も、BCPLみたいなグローバルベクタで定義されている様子も見当たりません。

# バックナンバー
[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)