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

UNIXが開発された当時はgitもCVSもなかったわけですが、もし当時gitがあったら?みたいなifを実現したリポジトリがGitHubにあります。

凄い時代になったものです。

非常に興味深い内容ですが、読むのは正直だるいです。私はゲーム畑の人間で、組み込みも混ざっていますが、UNIX/Linux方面は全くの素人。誰かお詳しい方に解説をお願いしたいところです。

しかしちょっとググってみた限りでは解説している人は見当たりません。止むを得ず自分で探求することに…。

PDP-7

ベル研がMultixの開発から撤退し、ファイルシステムのアイデアがお蔵入りになったケン・トンプソンはエネルギーを持て余していました。日進月歩でコンピュータの性能が高まっていたこの時代、陳腐化して誰も使わなくなったPDP-7でゲームを作っていたケン・トンプソンは、これでファイルシステムを実装してみることにしました。OSはオマケです。Multixはマルチタスクに対応した当時最先端のOSでしたが、今の基準から考えたら非常に陳腐なものでした。しかしデバイスをファイルとして扱う概念はあったようです。これはケン・トンプソンのアイデアだったのか、それともそこからUNIXに借用したのかはわかりません。

ファイル構成

uiweo@DESKTOP-HP MINGW64 /d/Users/uiweo/Documents/unix-history-repo (Research-PDP7-Snapshot-Development)
$ ls
adm.s                  apr.s  bi.s                 cas.s    chmod.s  cp.s     ds.s      dsksav.s  ed2.s   lcase.b   README.md  s3.s  s6.s  s9.s     sysmap
ald.s                  as.s   bl.s                 cat.s    chown.s  db.s     dskio.s   dsw.s     ind.b   LICENSE   s1.s       s4.s  s7.s  scope.v  trysys.s
ALU-USA-statement.pdf  bc.s   Caldera-license.pdf  check.s  chrm.s   dmabs.s  dskres.s  ed1.s     init.s  maksys.s  s2.s       s5.s  s8.s  sop.s

最初のコミットは1970年6月30日。ソースコードは40ファイルの133KBしかありません。最初のUNIXはシングルプロセスでスレッドもなく、シェルもパイプもありませんでした。

システムコール

sysmap

.        004671 r
.ac      004012 r
.chown	 000426 r
.capt	 000404 r
.creat   000665 r
.chdir	 000622 r
.chmod   000414 r
.dskb	 004105 r
.dspb	 005547 r
.dsptm	 004104	r
.dske	 004106 r
.exit	 001170 r
.fork	 001116 r
.getuid  000433 r
.halt	 001343 r
.int1	 004100 r
.insys	 004077 r
.int2	 004101 r
.intrp	 000257 r
.link    000474 r
.lpba	 005550 r
.open	 000633 r
…

こちらはsysmapというファイルの抜粋です。ファイルにchmodとかchownとか見えたので、コマンドかなと思ったのですが、sysmapを見ると、システムコールの実装のように見えます。

chmod.s

" chmode

   lac 017777 i
   sad d4
   jmp error

   lac 017777
   tad d4
   dac 8
   tad d1
   dac name
   dzm octal
   dzm nchar
   -8
   dac c1
1:
   lac nchar
   dzm nchar
   sza
   jmp 2f
   lac 8 i
   lmq
   and o177
   dac nchar
   lacq
   lrss 9
2:
   sad o40
   jmp 3f
   tad om60
   lmq
   lac octal
   cll; als 3
   omq
   dac octal
3:
   isz c1
   jmp 1b

loop:
   lac 017777 i
   sad d8
   sys exit
   tad dm4
   dac 017777 i
   lac name
   tad d4
   dac name
   lac octal
   sys chmode; name:0
   sma
   jmp loop
   lac name
   dac 1f
   lac d1
   sys write; 1:0; 4
   lac d1
   sys write; 1f; 2
   jmp loop
1:
   040;077012
error:
   lac d1
   sys write; 1b+1; 1
   sys exit

om60: -060
o40: 040
d1: 1
d8: 8
dm4: -4
d4: 4
o177: 0177

nchar: .=.+1
c1: .=.+1
octal: .=.+1

これはchmod.sのコード。非常に小さくてシンプルです。C言語で書けば数行でしょう。最初のバージョンからchmodがあったということは、最初からパーミッションがあったということで、ちょっと驚きです。ループを回して条件を満たしたらexitするという形になっていますので、これはシステムコール内部ではなくてプロセスのようです。

s2.s

.chmod:
   jms isown
   lac u.ac
   and o17
   lmq
   lac i.flags
   and o777760
   omq
   dac i.flags
   jms iput
   jmp okexit

s2.sというコードのほうがシステムコールになるようです。名前が同じなので紛らわしいですが、chmod.sがchmodコマンドのソースで、内部からchmodというシステムコールを呼んでおり、そのシステムコールの本体がs2.sにある、という形になります。それにしても短くてシンプルです。

デバイスドライバ

init.s

ttyin:
   <tt>;<yi>;<n 040;040040
ttyout:
   <tt>;<yo>;<ut>; 040040
keybd:
   <ke>;<yb>;<oa>;<rd>
displ:
   <di>;<sp>;<la>;<y 040
sh: 
   <sh>; 040040;040040;040040
system:
   <sy>;<st>;<em>; 040040
password:
   <pa>;<ss>;<wo>;<rd>

init.sにはデバイスドライバの名前らしきものが見えます。文字列は2文字ずつペアで定義し、8文字の固定長で、余白はスペース(40)で埋めています。

標準入力はttyin、出力はttyoutという名前が割り当てられています。パイプが実装されたのはかなり後のことなので、このドライバはそんなに複雑なことはしていないものと思われます。

init.s

init1: 0
   sys fork
   jmp 1f
   sys open; ttyin; 0
   sys open; ttyout; 1
   jmp login
1:
   dac pid1
   jmp init1 i

init2: 0
   sys fork
   jmp 1f
   sys open; keybd; 0
   sys open; displ; 1
   jmp login
1:
   dac pid2
   jmp init2 i

初期化処理でドライバのファイルを直接オープンしています。devディレクトリはなく、ルートにファイルがあるようです。そもそもサブディレクトリがあったかどうかも定かではありません。いちおうchdirというシステムコールはありますが、ディレクトリを作ったり削除したりするシステムコールは見当たりません。

B言語

ここまですべてアセンブラであることからもわかるように、当時のUNIXはプログラムをアセンブラで書かなければなりませんでした。

ind.b

main $(
   extrn read, write;
   auto i, c, state, line 100;

loop:
   state = i = 0;
loop1:
   c = read();
   if(c==4) return;
   if(c==':' & state==0) state = 2;
   if((c<'0' ^ c>'9'&c<'a' ^ c>'z') & state==0) state = 1;
   line[i] = c;
   i = i+1;
   if(c!=012) goto loop1;
   if(state==2 ^ i==1) goto noi;
   write('  ');
   write(' ');
noi:
   i = 0;
loop3:
   c = line[i];
   write(c);
   i = i+1;
   if(c!=012) goto loop3;
   goto loop;
$)

と思ったらB言語のコードが2つ混ざっています。最初のコミットとはいえ、それなりの量がありますので、開発が始まってから数ヶ月が経過していたところのスナップショットなのかもしれません。

これらのB言語で書かれたコードはOSの機能ではなく、言語のサンプルコード。ケン・トンプソンはBCPLをベースに言語をシンプル化したB言語を作り、それが後のC言語になったことは有名です。ちなみにケン・トンプソンは当時ベル研でもエース級の天才でした。C言語に型を導入してコンパイラ化したデニス・リッチーの方がアカデミックな臭いがしますので、そちらの方が主役だと思っている人も多いようですが。イギリス人が書いた正規表現の論文を読んで、世界で最初くらいにそれを実装したのもケン・トンプソンです。正規表現の実装はコンパイラの実装そのものですので、コンパイラにも造詣が深かったことは間違いありません。ケン・トンプソンはBSDで有名なカリフォルニア大学バークレー校の卒業生で、BSD4を開発した伝説のビル・ジョイが最初に大学で使ったコンパイラはケン・トンプソンが実装したPASCALだったそうです。いったいどれだけ仕事してるんだケン・トンプソン。

extrnで指定しているread関数とwrite関数は、リポジトリに含まれていないライブラリ関数を参照するextern宣言だと思われます。いや、ひょっとするとシステムコールを直接呼べるようになっていたのかもしれません。当時はまだリンカがなく、B言語の元になったBCPLはリンクを手作業でやらなければならなかったので、extrnはその名残りと思われます。autoは変数の定義。line 100は100要素の配列を定義しているようです。

PDP-7は18ビット機で、今でいうintは18ビットです。この当時は変数に型がなく、全部18ビットでした。readやwriteの関数がvoid型なのかint型なのかわかりませんが、必ず18ビットの値が返ってくるので指定がなかったようです。ちなみにビット数が8ビットの倍数でなかったのは、当時はまだバイトという概念がなく、初期のコンピュータでは数字は16進数(4ビット2桁の8ビット)ではなく8進数(3ビット2桁の6ビット)を使うのが普通だったためです。18ビットは6×3というわけです。C言語で8進数の先頭に0を付けるのはその時の名残で、前述のchmod.sにもo177: 0177など8進数で数字を指定している様子が見られます。

forやwhileなどの制御構文がなく、gotoだけでループを実装しています。こうなるとほとんどアセンブラです。演算子の^はORであるようです。&はANDですが、この当時は論理演算子が無かったはずなので、ビット演算子だけでなんとかしていたようです。

制御構文

lcase.b

main $(
   auto ch;
   extrn read, write;

   goto loop;
   while (ch != 04)
      $( if (ch > 0100 & ch < 0133)
            ch = ch + 040;
      if (ch==015) goto loop;
      if (ch==014) goto loop;
      if (ch==011)
       $( ch = 040040;
          write(040040);
          write(040040);
          $)
      write(ch);
   loop:
      ch = read()&0177;
      $)
  $)

とか思ってもう1つのファイルを開いたらwhileがありました。言語のバージョンアップが進んだのでしょうか。

スレデッドコード

このセクションの内容は間違いであることがわかりました。詳細は[Unixの歴史を再現したリポジトリを読む⑤] (https://qiita.com/hayashida-katsutoshi/items/df9c08c4c5011f04b45e)をご参照ください。

ドライバのところで見たttyin/ttyoutはどこで定義されているのでしょうか。

cas.s

" cas

   narg = i 017777

   lac 017777
   tad d5
   dac name1
   tad d4
   dac name 2
   lac narg
   sad d4
   jmp 1f
   sad d8
   jmp 2f
   jmp 3f
1:
   law ttyout
   dac name1
2:
   law ttyin
   dac name2
3:
   sys open; name2: 0; 0

cas.sの中でttyout/ttyinの文字が見えます。単にドライバにアクセスしているだけなのでしょうか? ttyの文字列は他にはもう見つかりません。

このコード、前半は普通にアセンブラですが、後半に謎のコードがあります。

cas.s

:cf
v
aa
ak
x
gh
v
ga
x
mn
r

:cg
x
gf
v
gk
nk
x
kk
v
mi
mc
ka
ca
ac
ai
dl
x
mn
r

アセンブラのコードだとしたら異様な感じです。データ文としても普通の形ではありません。このcfやcgといったラベルにアクセスしている場所は見つかりません。

scope.v

:less
x
cj
v
gb
kj
x
mn
r

:great
x
cb
v
gj
kb
x
mn
r

:equal
x
eb
v
ek
x
ib
v
ik
x
mn
r

scope.vというファイルにはひたすらこんなのが入っています。拡張子のvはバーチャルと思われます。*.ｖファイルはこの1つだけです。確証はありませんが、これはB言語が出力したスレデッドコードという中間コードの一種なのではないかと思われます。

スレデッドコードは仮想命令がアセンブラのニモニックに置き換えられて実行されるようです。言われてみればrとかretっぽいような気もします。しかしラベルとかジャンプ命令とかレジスタ番号とかは見えないので、それっぽいような気がするものの、実際にどんなコードになるのかはわかりません。

この仮想コードをアセンブラのソースに含んでいるのはcas.sの1つだけでした。カーネルやコマンドをB言語で書いてた、ということは、この時点ではなかったようです。

また中間コードのコンパイラやインタプリタは見つけられませんでした。

バックナンバー

[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)