The Fuzzball (最古の NTP リファレンス実装) を読む[前編] - インターネット時刻同期の歴史(その11)

The Fuzzball とは何か

今やルーター OS といえば Linux ばかりであるが、そもそも UNIX にネットワークが実装されたのは前回解説した通りだいぶ遅い。 ベル研公式となると V7 UNIX でようやく UNIX to UNIX Copy Protocol(UUCP) が実装された程度である。

それでは当時の ARPANET などのバックボーンを支えたのは誰なのか。

ARPANET では Interface Message Processor(IMP) が現在のルーターに相当するものだ。 世界初の IMP は BBN 社(V6 UNIX へ TCP/IP 実装したとこ)による Honeywell 516 をベースの特注品。 詳細な仕様は BBN Report 1822 に載っているけどソースはおそらく表に出てないのでわかりませんでした、いかがでしたか？(検索汚染)

おそらく唯一実装が公開されているのが衛星通信サービスの COMSAT 社のネットワーク DCNET で使われていたルーター OS である The Fuzzball だ、作者は NTP の神いわゆるゴッドである David L. Mills 教授である。

RT-11 という PDP-11 上で動く DEC 謹製のシングルユーザー RTOS 上で動作するアプリケーションのようにみえるが教授曰く

It includes a comprehensive user interface based on a multiple-user, virtual-machine emulator for the DEC RT-11 operating system,

とあるので OS でいいや、メインフレームとか知らんがな。

当時の DCNET については以下の文章が詳しい。

• IEN173 Time Synchronization in DCNET Hosts
• RFC778 DCNET Internet Clock Service

1981 年の時点で

• 物理ホスト上で複数の仮想ホストが動作
• 仮想ホストは各々がネットワークアドレスを持つ
• 仮想ホストは自由に物理ホスト間を移動できる
• クロックは 1000Hz で動作し時間管理はミリ秒単位
• 原子時計や電波時計をソースにミリ秒単位での誤差での時刻同期を行う

という先進性であることが読み取れる。

まぁ仮想化はメインフレームじゃ 60年代末からある技術であってオープン系とかいう周回遅れは黙っとれというのはそれはそう。 しかしクロックは PDP-11 の LKS(=RTC) は 60Hz なのに桁が2つも違う 1000Hz とかお出しされるのにはビビる。

なんせ COMSAT 社は宇宙産業だし時間 = 距離だもの静止衛星ですら 8km/s ですっ飛んでくしミリ秒違うだけで致命的な誤差の世界だから常識が違うのだろう。

そんじゃさっそく fuzzball のソースでも読んでみようか、 ここ からダウンロードできるけど tarball だと引用できないから github/pdp11/fuzzball-operating-system という謎ミラー使うね。

一点注意はファイルはすべて 512 バイトの倍数サイズで余白は 0(NUL) で埋められている。 なのでソースコードブラウザや grep にバイナリ判定されるのがクソメンドい。 だから除去するツール書くなり grep に -a オプション付けるなりで対策してくだち。

まずは資料集め

fuzzball が動作するのは 前述の通り RT-11 上なのでそのシステムコールのマニュアルである

• RT-11 System Macro Library Manual
• RT-11 System Subroutine Library Manual

を必要に応じて読めば今回は十分かな、深く堀り下げる気ねえし。

ソースコードの構成

どういったプログラムやファイルがあったのかは HELP.TXT の General information に簡単な解説がある、先頭になんか検索用のインデックスらしきものがバイナリとしてついてるけど後ろは普通のテキストである。

拡張子いっぱいあるけど

• *.MAC が アセンブラ (RT-11 System Macro) のソース
• *.COM がコンパイル用のマクロ

くらい理解しておけば今回はじゅうぶん。

ソースのバージョン管理履歴は非公開で最終版(最終更新は1992年とのこと)のソースコードのみ教授のサイトにアップされてるので 1970年末から1980年代初頭において当時どこまで実装されてたかは不明ではあるが、サービスとしては

• NAMSRV.SAV … IEN116 Internet Name Server
• FTPSRV.SAV … RFC765 RFC959 File Transfer Protocol
• TFTSRV.SAV … RFC783 Trivial File Transfer Protocol
• SMPSRV.SAV … RFC812 Simple Mail Transfer Protocol
• TELSRV.SAV … RFC854 Telnet Protocol
• TIMSRV.SAV … RFC868 Time Protocol
• DOMSRV.SAV … RFC883 Domain Names
• NTPSRV.SAV … RFC958 RFC1059 RFC1119 Network Time Protocol
• SPQSRV.SAV … RFC1179 Line Printer Daemon Protocol

が存在する、なお一部のサービスは inetd(8) のように UDP.SAV 経由で起動するようなことが書いてあるがネットワークプログラミング講座じゃないので以下略

このうち特に Network Time Protocol の実装が重要で、Version 2 に至るまでのリファレンス実装はこの fuzzball 上で行われたということ。

そして時刻設定を行うコマンドが

• NETCLK.SAV … インターネット時刻設定
• SETCLK.SAV … ローカル時刻設定

のふたつ、思わず前者の実装から読んでしまいそうになるがこっちは RFC868 Time Protocol のクライアントで後の Ultrix の rdate(1) に相当するプログラムなので すでに通った道 で読む価値なしである。

ちゅーわけで重要なのは SETCLK.SAV の方。

SETCLK.MAC を読む

V7 UNIX ではディスクドライブの先頭ブロックに現在時刻を保存する ダーティーハック だったけど、fuzzball は

• Digital Pathways TCU-50 digital clock

という Ni-Cd 充電池により電源断の間も時刻更新が可能な RTC を外付で搭載している。

そして SETCLK.SAV は TCU-50 の時刻をソースに RT-11 のシステム時刻を設定する事が可能。

• SETCLK.MAC#138

 65 .IIF NDF,LINFRQ LINFRQ == 60.	;cpu clock interrupt frequency (Hz)
 66 .IIF NDF,TCUREG TCUREG == 170770	;default tcu device address
...
138 ;
139 ; Digital clock
140 ; (note usual device address is )
141 ;
142 TCUCLK:	MOV	DEVREG,R2	;get register base
143 	BNE	2$		;branch if given
144 	MOV	#TCUREG,R2	;use default
145 2$:	MOV	(R2)+,R0	;get date
146 	TST	FLAG
147 	BNE	1$		;branch if dead tcu
148 	MOV	(R2)+,R3	;yes. get hours and minutes
149 	MOV	(R2)+,R1	;get seconds
150 	CMP	-(R2),R1	;has clock stepped
151 	BNE	TCUCLK		;branch if yes
152 	CMP	-(R2),R3
153 	BNE	TCUCLK		;branch if yes
154 	CMP	-(R2),R0
155 	BNE	RADCLK		;branch if yes
156 	ASLB	R0		;no. muscle date around to rt-11 format
157 	ASLB	R0
158 	ASLB	R0
159 	ASL	R0
160 	ASL	R0
161 	BIC	#^C37,DATE	;keep current year
162 	BIS	R0,DATE
163 	BIC	#^C77,R1	;extract seconds
164 	MOV	R1,-(SP)
165 	MOV	R3,-(SP)
166 	BIC	#^C77,@SP
167 	CLR	R2		;extract hours
168 	SWAB	R3
169 	BIC	#^C37,R3
170 	MOV	#60.,R0		;convert to minutes
171 	JSR	PC,DMUL
172 	ADD	(SP)+,R3
173 	MOV	#60.,R0		;convert to seconds
174 	JSR	PC,DMUL
175 	ADD	(SP)+,R3
176 	ADC	R2
177 	MOV	#LINFRQ,R0	;convert to ticks
178 	JSR	PC,DMUL
179 	MOV	R2,TIME
180 	MOV	R3,TIME+2
181 	.SDTTM	#ARGBLK,#DATE	;set system date and time
182 	JMP	EXIT
...
469 ;
470 ; Subroutine to perform double-precision multiplication
471 ; R0 = multiplier, r2-r3 = multiplicand, returns r2-r3 = product (lsb)
472 ;
473 DMUL:	MOV	R1,-(SP)	;save
474 	MOV	R4,-(SP)
475 	CLR	R1		;initialize
476 	MOV	#33.,R4
477 1$:	ASR	R1		;shift partial product right
478 	ROR	R2
479 	ROR	R3
480 	BCC	2$		;branch if lsb = 0
481 	ADD	R0,R1		;lsb <> 0. add multiplier
482 2$:	SOB	R4,1$
483 	MOV	(SP)+,R4	;evas
484 	MOV	(SP)+,R1
485 	RTS	PC
...
759 ;
760 ; Program variables
761 ;
762 FLAG:	.BLKW	1		;error flag
763 DATE:	.BLKW	1		;0 date
764 TIME:	.BLKW	2		;2 time of day
...
767 ARGBLK:	.BLKW	5		;rt-11 argument block

#TCUREG つまり TCU-50 を R2 に置いて日付時刻を

• 日付 MOV R2,R0
• 時分 MOV (R2)+,R3
• 秒 MOV (R2)+,R1

都合 3 回読込んでこれを RT-11 の日付時刻形式に変換する。

一度に読込めないから途中で時計が進んだ場合はループでやり直しすることで整合性を保つのは 過去回 で解説済である。

RADCLK による時刻設定の方が優先されるけど今は TCU-50 ソースなので無視してよろしい。

最後に UNIX でいうとこの settimeofday(2) に相当する RT-11 のシステムコール .SDTTM で現在時刻を変更する。

RT-11 における日付時刻形式とは

• DATE … 16bit
• TIME … 32bit

の合計 48bit である。

DATEのそれぞれのビットについては RT-11 System Macro Library Manual 2-55 .DATE にある通り

f	e	d	c	b	a	9	8	7	6	5	4	3	2	1	0
A	A	M	M	M	M	D	D	D	D	D	Y	Y	Y	Y	Y

• Y … Year bits (5bit)
• D … Day bits (5bit)
• M … Month bits (4bit)
• A … Age bits (2bit)

となっている、えっYear bits たった 5bit しかねえ！これじゃ西暦 31 年までしか扱えねーじゃん。

しかしご安心を、そのために 1972 年をエポック(敬礼！)とするのと Age bits という謎の 2bit が存在する。

1972 + Year + Age * 32

と計算するのである、なぜ最初から Year bits を 7bit にしないのか小一時間問い詰めたい。 たぶん 2003 年以降の事は考えてなくて未使用ビットだったんだとは想像つくが。

ここであれ？と思った人は勘がいい、上記のコードにはバグがある。

• BIC #^C37,DATE は C で書けば date &= ~037　である
• なので Year bits は残るが Age bits はクリアされてしまってる
• 正しいコードなら 2099 年まで扱えるが 2003 年になると 1972 年に時間退行してしまう

これ 2003 年問題じゃねーか！

Time formatting and storage bugs にも記述無いから、またしてもウィキペディアに勝利するアンサイクロペディアみたいになってしまった。 これで俺はいつ死んでもあの世で Mills 教授にバグ報告できるってもんよ。

ところでなぜ Year bits だけ残すのかというとなんと TCU-50 は年情報持ってないのだ。 いやマニュアル二度見しちゃったんだけど本当に無いのだ。

• 76XXX0 … READ MONTH/DAY

f	e	d	c	b	a	9	8	7	6	5	4	3	2	1	0
-	-	-	-	M	M	M	M	-	-	-	D	D	D	D	D

• 76XXX2 … READ HOUR/MINUTES

f	e	d	c	b	a	9	8	7	6	5	4	3	2	1	0
-	-	-	h	h	h	h	h	-	-	m	m	m	m	m	m

• 76XXX4 … READ SECONDS

f	e	d	c	b	a	9	8	7	6	5	4	3	2	1	0
-	-	-	-	-	-	-	-	-	-	s	s	s	s	s	s

16bit * 3 もあるのにやーばいでしょ、えぇ…閏年とかどうすんのこれ。

ということで上記のコードは 2003 年問題のみならず年越しバグまであったわガハハ。 SETCLK.SAV 実行して TCU-50 から月日時分秒読込んでる途中に年越したら時間が 1 年巻き戻っちゃう。 月が 12 → 1 になったら年を +1 しないとダメだよねこれ。

まぁいいや、RT-11 の TIME は doble precision number(integer) などとマニュアルに書かれている。 今時浮動小数点数くらいでしか倍精度とか言わないから一瞬頭？になるが 16bit の倍の 32bit って意味でしかない。 なので DMUL は 被乗数 R2/R3(32bit) を乗数 R0(16bit) で掛算するコード。

よって C で書くならこんだけのコードである。

#define HZ 60
	uint16_t hour, minutes, seconds, linfrq;
        uint32_t time;

	hour = ...
	minutes = ...
	seconds = ...
	linfrq = HZ;

        time = hour;
        time *= 60;
        time += minutes;
        time *= 60;
        time += seconds;
        time *= linfrq;

最大 23:59:59 + 59 tick なので上限は 5183999 となる。 5184000 以上を指定した場合 DATE を +1day してくれるような親切設計ではないのでエラーになる。

そんで前回説明した通り PDP-11 endian になってることにも注意だ。

次回

うーん？このコードのどこに 1000Hz なんて精度があるんだ？ 基本 RT-11 丸投げだから 60Hz しかねーぞどうなってんだ？

その謎がさっきすっ飛ばした RADCLK なのだが TCU-50 の説明だけで長くなり過ぎたから回を分割するね…

次回はラジオの話、いいですよね Joy Division/Transmission ラジオ生放送踊れ踊れ踊れラジオにあわせて。