マスター側のコードを読む

マスターとなった timed(8) は 240 秒ごとにスレーブのコマンドをポーリングする。

なお実装はビジーウェイトで gettimeofday(2) システムコールを連打し 240 秒経過したらメッセージ処理というやべーコード。 現代の感覚だとタイマーお使いにならないんですか(油汗)って言いたくなるが 当時のヒッピー文化でタイマーとは吸うものなのだ(ジミヘンのパープルヘイズを聴きながら)。

22 #define SAMPLEINTVL	240		/* synch() freq for master, sec */

 38 master()
 39 {
...
 41 	long pollingtime;
...
 46 	struct tsp *msg, to;
...
 70 	pollingtime = 0;
 71 
 72 loop:
 73 	(void)gettimeofday(&time, (struct timezone *)0);
 74 	if (time.tv_sec >= pollingtime) {
 75 		pollingtime = time.tv_sec + SAMPLEINTVL;
 76 		synch(0L);
...
 91 	}
...
 95 	msg = readmsg(TSP_ANY, (char *)ANYADDR, &wait, (struct netinfo *)NULL);
 96 	if (msg != NULL) {
 97 		switch (msg->tsp_type) {
...
266 		}
267 	}
268 	goto loop;
269 }

synch() で時刻調整を行うのだがこの部分はメインディッシュだから後回しにする。

TSP_SLAVEUP コマンドを処理する

ネットワーク上に新たなスレーブ候補が現れて参加を求めてるのが TSP_SLAVEUP コマンド、お前が奴隷調教志願の豚か(鞭の音)？

101 		case TSP_SLAVEUP:
102 			ind = addmach(msg->tsp_name, &from);
103 			newslave(ind, msg->tsp_seq);
104 			break;

この時マスターがやることは

  • addmach() … 奴隷リストに追加
  • newslave() … 強制的に時刻同期

である。

奴隷リストは host 構造体(サイバーパンク歌舞伎町)型の配列 hp で管理され、最大 NHOSTS つまり 100 台までが参加できる、いや少なくねえ！？ってそりゃスケールするわけねえ、 最初から LAN(Local Area Network) 向けを唄ってるわけですわ。

53 #define NHOSTS		100	/* max number of hosts controlled by timed */
54 
55 struct host {
56 	char *name;
57 	struct sockaddr_in addr;
58 	long delta;
59 	u_short seq;
60 };
...
80 extern struct host hp[];

37 struct host hp[NHOSTS];

383 findhost(name)
384 char *name;
385 {
386 	int i;
387 	int ind;
388 
389 	ind = -1;
390 	for (i=1; i<slvcount; i++) {
391 		if (strcmp(name, hp[i].name) == 0) {
392 			ind = i;
393 			break;
394 		}
395 	}
396 	return(ind);
397 }
398 
399 /*
400  * 'addmach' adds a host to the list of controlled machines
401  * if not already there 
402  */
403 
404 addmach(name, addr)
405 char *name;
406 struct sockaddr_in *addr;
407 {
408 	int ret;
409 	int findhost();
410 
411 	ret = findhost(name);
412 	if (ret < 0) {
413 		hp[slvcount].addr = *addr;
414 		hp[slvcount].name = (char *)malloc(MAXHOSTNAMELEN);
415 		(void)strcpy(hp[slvcount].name, name);
416 		hp[slvcount].seq = 0;
417 		ret = slvcount;
418 		if (slvcount < NHOSTS)
419 			slvcount++;
420 		else {
421 			syslog(LOG_ERR, "no more slots in host table");
422 		}
423 	} else {
424 		/* need to clear sequence number anyhow */
425 		hp[ret].seq = 0;
426 	}
427 #ifdef MEASURE
428 	header = ON;
429 #endif
430 	return(ret);
431 }

findhost() の実装もひどい、スレーブのホスト名の一致しか見てないから詐称するだけで別のスレーブにマスターからコマンド送り放題だと思われるが、そういう時代だったんだよ(しろめ)。

余談っぽくなるが最新版において 100 台縛りはリンクリスト化することで制限解除されたようなことを前回書いてしまった。

確かに host 構造体は hosttbl 構造体に改められて双方向リストに書き直されてはいる。 しかしダイナミックアロケーションはしておらず固定長配列プールからリスト作ってるだけなんだなこれ。 よって NHOSTS は 1013 に増やしたものの縛りはいまだ残っているというクソ実装であった。

101 #define NHOSTS		1013	/* max of hosts controlled by timed
102 					 * This must be a prime number.
103 					 */
104 struct hosttbl {
105 	struct	hosttbl *h_bak;		/* hash chain */
106 	struct	hosttbl *h_fwd;
107 	struct  hosttbl *l_bak;		/* "sequential" list */
108 	struct  hosttbl *l_fwd;
...
118 };
119 
120 /* closed hash table with internal chaining */
121 extern struct hosttbl hosttbl[NHOSTS+1];

コメントに closed hash table とあるけどホスト名文字列のハッシュ値を配列のインデックスにするだけの手抜き実装、ホスト名はユニークだから衝突しっこないだろガハハ。

532 struct hosttbl *			/* answer or 0 */
533 findhost(char *name)
534 {
535 	int i, j;
536 	struct hosttbl *htp;
537 	char *p;
538 
539 	j= 0;
540 	for (p = name, i = 0; i < 8 && *p != '\0'; i++, p++)
541 		j = (j << 2) ^ *p;
542 	newhost_hash = &hosttbl[j % NHOSTS];
543 
544 	htp = newhost_hash;
545 	if (htp->name[0] == '\0')
546 		return(0);
547 	do {
548 		if (!strcmp(name, htp->name))
549 			return(htp);
550 		htp = htp->h_fwd;
551 	} while (htp != newhost_hash);
552 	return(0);
553 }

ほい、リスト要素は歯抜けの配列をイテレートするためだけのものってこった。

分散コンピューティングなんだから DHT(Distributed Hash Table) を実装しろと時代錯誤の贅沢は言わんけど、せめて赤黒木でハッシュテーブル実装しませんかね(しろめ)。 まだ当時発明されてなかったりしたらゴメンと検索したらとっくにされてんじゃねーか。

存在しない過去記事も何度か紹介したがいまどきは tree(3) あるいは rbtree(3) あるからハッシュテーブルなんて秒で実装できるけど、当時はそれすらめんどくさいのが C なのだ。 そりゃスケールするわけがない、おいしいですよね青魚DHA。

マスターはスレーブを管理用の配列につっこんだら 最初の一回だけ TSP_SETTIME コマンドを投げてスレーブに強制時刻同期を迫る。

502 newslave(ind, seq)
503 u_short seq;
504 {
505 	struct tsp to;
506 	struct tsp *answer, *acksend();
507 
508 	if (trace)
509 		prthp();
510 	if (seq == 0 || hp[ind].seq !=  seq) {
511 		hp[ind].seq = seq;
512 		to.tsp_type = TSP_SETTIME;
513 		(void)strcpy(to.tsp_name, hostname);
514 		/*
515 		 * give the upcoming slave the time
516 		 * to check its input queue before
517 		 * setting the time
518 		 */
519 		sleep(1);
520 		(void) gettimeofday(&to.tsp_time,
521 		    (struct timezone *)0);
522 		answer = acksend(&to, &hp[ind].addr,
523 		    hp[ind].name, TSP_ACK,
524 		    (struct netinfo *)NULL);
525 		if (answer == NULL) {
526 			syslog(LOG_WARNING,
527 			    "no reply to initial SETTIME from: %s",
528 			    hp[ind].name);
529 			rmmach(ind);
530 		}
531 	}
532 }

この時だけは時刻が逆戻りする可能性がある、timed(8) が起動スクリプト rc(8) から呼ばれる時だけだしいいよね…っておおらかな時代の実装だなぁ。

スレーブ側で TSP_SETTIME をどう処理するかはそっちのコードを読む際に説明する。

その他のコマンド処理

説明する価値ないので省略！

synch() による時刻調整

いよいよ 前回 文章で流しただけの TEMPO による時刻調整のコードを読んでいこう。

 18 extern int measure_delta;
...
271 /*
272  * `synch' synchronizes all the slaves by calling measure, 
273  * networkdelta and correct 
274  */
275 
276 synch(mydelta)
277 long mydelta;
278 {
279 	int i;
280 	int measure_status;
...
282 	struct timeval tack;
...
305 		machup = 1;
306 		hp[0].delta = 0;
307 		for(i=1; i<slvcount; i++) {
308 			tack.tv_sec = 0;
309 			tack.tv_usec = 500000;
310 			if ((measure_status = measure(&tack, &hp[i].addr)) <0) {
311 				syslog(LOG_ERR, "measure: %m");
312 				exit(1);
313 			}
314 			hp[i].delta = measure_delta;
315 			if (measure_status == GOOD)
316 				machup++;
317 		}
...
326 				netdelta = networkdelta();
331 				correct(netdelta);

ポイントは以下の 3 つの関数で、ペーパーにあったポンチ絵 3 枚と対応している。

  • measure() による clockdiff の測定
  • networkdelta() による「正しい時刻」の決定
  • correct() による時刻調整

measure() による clockdiff の測定

自身とスレーブの時間差 clockdiff を収集する作業、最終的にグローバル変数の measure_delta に値がセットされる。

まずはICMP timestamp をスレーブに送って返してくるまでの時間、すなわちラウンドトリップタイム (RTT) の計測を行う。

 29 /*
 30  * Measures the differences between machines' clocks using
 31  * ICMP timestamp messages.
 32  */
 33 
 34 measure(wait, addr)
 35 struct timeval *wait;
 36 struct sockaddr_in *addr;
 37 {
...
 70 	/*
 71 	 * To measure the difference, select MSGS messages whose round-trip
 72 	 * time is smaller than RANGE if ckrange is 1, otherwise simply
 73 	 * select MSGS messages regardless of round-trip transmission time.
 74 	 * Choose the smallest transmission time in each of the two directions.
 75 	 * Use these two latter quantities to compute the delta between
 76 	 * the two clocks.
 77 	 */
...
 80 	oicp->icmp_type = ICMP_TSTAMP;
...
 95 		(void)gettimeofday (&tv1, (struct timezone *)0);
 96 		sendtime = oicp->icmp_otime = (tv1.tv_sec % (24*60*60)) * 1000 
 97 							+ tv1.tv_usec / 1000;
...
100 		count = sendto(sock_raw, (char *)opacket, sizeof(*oicp), 0, 
101 				addr, sizeof(struct sockaddr_in));
...
106 		for (;;) {
...
111 			cc = recvfrom(sock_raw, (char *)packet, PACKET_IN, 0, 
112 			    (struct sockaddr_in *)NULL, &length);
113 			(void)gettimeofday(&tv1, (struct timezone *)0);
...
116 			icp = (struct icmp *)(packet + (ip->ip_hl << 2));
117 			if((icp->icmp_type == ICMP_TSTAMPREPLY) &&
118 			    icp->icmp_id == id && icp->icmp_seq == seqno)
119 				break;
120 		}
...
123 		recvtime = (tv1.tv_sec % (24*60*60)) * 1000 +
124 		    tv1.tv_usec / 1000;
125 		diff = recvtime - sendtime;
...
179 }
  • sendtime … 送信時間( sendto(2) で ICMP_TSTAMP なパケットを送信する直前)
  • recvtime … 受信時間( recvfrom(2) で ICMP_TSTAMPREPLY なパケットを受信した直後)
  • diff … ラウンドトリップタイム(受信時間から送信時間を引いたもの)

簡単ですね？ ping(8) のコードで RTT 学ぶよりコードが簡潔な分判りやすいといえる。

お次はスレーブの現在時間の取得、というかさっきの受信パケットで取得済である。

132 		histime = ntohl((u_long)icp->icmp_rtime);

ほい RFC792 INTERNET CONTROL MESSAGE PROTOCOL でいうところの Timestamp Reply Message データグラム

Timestamp or Timestamp Reply Message

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |      Code     |          Checksum             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           Identifier          |        Sequence Number        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Originate Timestamp                                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Receive Timestamp                                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Transmit Timestamp                                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

これの Receive Timestamp がスレーブの現在時間。 ところで変数名が HisTime (彼の時間)ってやっぱ雄豚なんだなぁ…

24 /*
25  * Parameters for network time measurement
26  * of each host using ICMP timestamp requests.
27  */
28 #define RANGE		20		/* best expected round-trip time, ms */

17 #define BIASP	 	43199999
18 #define BIASN		-43200000
19 #define MODULO	 	86400000
...
43 	long sendtime, recvtime, histime;
44 	long min1, min2, diff;
45 	register long delta1, delta2;
...
144 		delta1 = histime - sendtime;
145 		/*
146 		 * Handles wrap-around to avoid that around 
147 		 * midnight small time differences appear 
148 		 * enormous. However, the two machine's clocks
149 		 * must be within 12 hours from each other.
150 		 */
151 		if (delta1 < BIASN)
152 			delta1 += MODULO;
153 		else if (delta1 > BIASP)
154 			delta1 -= MODULO;
155 		delta2 = recvtime - histime;
156 		if (delta2 < BIASN)
157 			delta2 += MODULO;
158 		else if (delta2 > BIASP)
159 			delta2 -= MODULO;

なにやらゴチャゴチャしてるけどまず最初に理解すべきは

  • delta1 = histime - sendtime … マスター → スレーブの到達時間(スレーブ現在時間 - 送信時間)
  • delta2 = recvtime - histime … スレーブ → マスターの到達時間(受信時間 - スレーブ現在時間)
  • diff = recvtime - sendtime … ラウンドトリップタイム(受信時間 - 送信時間)

のみっつ、送受信時間はマスター計測なので delta1 と delta2 にはマスターとスレーブとの時差が含まれている。

そして謎の定数みっつだけど、86400000 が 24*60*60*1000 である事に気づくと

  • BIASP … プラス 12 時間
  • BIASN … マイナス 12 時間
  • MODULO … 24時間

の意味だとわかる、なーにが BIAS (=偏差)と MODULO (=剰余)じゃこれだから理系は。

しかしなぜ delta1 と delta2 を前後 24 時間ずらす必要があるのか。 それは再掲になるが以下の処理を思い出せ。

 96 		sendtime = oicp->icmp_otime = (tv1.tv_sec % (24*60*60)) * 1000 
 97 							+ tv1.tv_usec / 1000;
...
123 		recvtime = (tv1.tv_sec % (24*60*60)) * 1000 +
124 		    tv1.tv_usec / 1000;

そう送受信「時刻」でなく「時間」なのだ、すでに 24 時間で割っちゃってるからね。 よって送受信の間に日を跨いだら sendtime > recvtime と逆転してしまう。 だから補正しないと正しい値にならんのだ。

ICMP timestamp の時間表現(ミリ秒)を優先してるから仕方ない面もあるがもっと判りやすいコードにならんか。

まぁいいや、お次のコード。

44 	long min1, min2, diff;
...
52 	min1 = min2 = 0x7fffffff;
...
160 		if (delta1 < min1)  
161 			min1 = delta1;
162 		if (delta2 < min2)
163 			min2 = delta2;
164 		if (diff < RANGE) {
165 			min1 = delta1;
166 			min2 = delta2;
167 			break;
168 		}

delta1 と delta2 が 0x7fffffff より大きくなるケースが判らない。 計算元となる sendtime と recvtime はソースが gettimeofday(2) だから絶対に無い。 可能性があるのは ICMP timestamp がソースの histtime だけど以下のコードあるし到達不能コードだよなこれ。

133 		/*
134 		 * a hosts using a time format different from 
135 		 * ms. since midnight UT (as per RFC792) should
136 		 * set the high order bit of the 32-bit time
137 		 * value it transmits.
138 		 */
139 		if ((histime & 0x80000000) != 0) {
140 			status = NONSTDTIME;
141 			break;
142 		}

あとは MODULO の補正でオーバーフローあるいはアンダーフロー？ たった 24 時間の足し引きでそうなるなら既に値が異常だよね…

まぁいい、delta1 と delta2 が 0x7fffffff より大きい異常事態でも diff すなわちラウンドトリップタイムが RANGE つまり 20 秒以下なら採用される。 仕様書通りならどうせ最後に異常値扱いで除外されるでしょう…

長かった measure() もようやくフィナーレである。

 20 #define PROCESSING_TIME	5 	/* ms. to reduce error in measurement */
...
176 		measure_delta = (min1 - min2)/2 + PROCESSING_TIME;

ここまできたのなら実際に計算してみようかね、例題として

  • マスターとスレーブの時刻差は 10 秒
  • ラウンドトリップタイムは 2 秒

というケースを想定する。

[master]        [slave]
00:00:00        00:00:10

00:00:00  1 ->  00:00:11
00:00:02  <- 1  00:00:11

sendtime = 00:00:00
recvtime = 00:00:02
histime  = 00:00:11

diff = recvtime(00:00:02) - sendtime(00:00:00) = 2

delta1 = histime(00:00:11) - sendtime(00:00:00) = 11
delta2 = recvtime(00:00:02) - histime(00:00:11) = -9

min1 = delta1(11)
min2 = delta2(-9)

measure_delta = (min1(11) - min2(-9))/2 = 10

という計算になる、おお！ measure_delta は 10 秒で正確にマスターとスレーブの時刻差が取得できてるわけだ。

まぁ勘の良い人はもうお気づきかと思いますが、この計算ってラウンドトリップが常に対照的であるという幸せな前提に頼ってるんだよね。

最大で行きと帰りの時間差 1/2 の誤差が生じるアルゴリズムなのだ、ただしこれは NTP も同様の問題があったはずである。

最後に PROCESSING_TIME つまり 5 ミリ秒を足してるのは、measure() 自体が費やした計算時間がだいたいそれくらいというアバウトな補正である。

うーんこれマシンの性能が上がってるわけで 5 ミリ秒って現実に即してないっす誤差ふえるっす。 ちゃんと測ればいいんじゃないですかね…

まぁ下手に計測すると今度は Windows 98 の NDIS.VXD 問題みたいなの起こすこともあるけど。 初期化中に 100 万回空ループした時間を計測しその時間で割り算するんだが K6 以降の高速な CPU だと小数点以下なのでゼロ除算エラー起こして Windows 保護エラーになるという有名なやつ。

networkdelta() による「正しい時刻」の決定

まずはどうでもいい部分、x[NHOSTS] にすべてのスレーブの delta をコピー。

16 /*
17  * `networkdelta' selects the largest set of deltas that fall within the
18  * interval RANGE, and uses them to compute the network average delta 
19  */
20 
21 long networkdelta()
22 {
23 	int i, j, maxind, minind;
...
25 	int tempind;
26 	long tempdata;
27 	long x[NHOSTS];
...
29 
30 	for (i=0; i<slvcount; i++)
31 		x[i] = hp[i].delta;

その次の行からが衝撃的である。 バブルソートしかも手書きって遭遇するの何年ぶりだろう(絶滅動物を発見した時の顔)。 なお qsort(3) は V5 UNIX の頃から存在するしここで安定ソートが必要なわけでもないしナニコレ。

32 	for (i=0; i<slvcount-1; i++) {
33 		tempdata = x[i];
34 		tempind = i;
35 		for (j=i+1; j<slvcount; j++) {
36 			if (x[j] < tempdata) {
37 				tempdata = x[j];
38 				tempind = j;
39 			}
40 		}
41 		x[tempind] = x[i];
42 		x[i] = tempdata;
43 	}

お次、 DO NOT TOUCH IT! 触るんじゃねえってあるけど触りたくねえ！の間違いじゃねぇかなこれ。

45 	/* this piece of code is critical: DO NOT TOUCH IT! */
46 /****/
47 	i=0; j=1; minind=0; maxind=1;
48 	if (machup == 2)
49 		goto compute;
50 	do {
51 		if (x[j]-x[i] <= RANGE)
52 			j++;
53 		else {
54 			if (j > i+1) 
55  				j--; 
56 			if ((x[j]-x[i] <= RANGE) && (j-i >= maxind-minind)) {
57 				minind=i;
58 				maxind=j;
59 			}	
60 			i++;
61 			if(i = j)
62 				j++;
63 		}
64 	} while (j < machup);
65 	if ((x[machup-1] - x[i] <= RANGE) && (machup-i-1 >= maxind-minind)) {
66 		minind=i; maxind=machup-1;
67 	}

時刻差が RANGE つまり 20 秒に収まってる範囲を探し、その範囲の開始を minind 終了を maxind としてそれ以外はバッサリ異常値と判定する。

えぇ…これ 20 秒で連続してさえいれば、もっとも時刻差の大きい集合が集計対象になってしまうがいいのかこれ。

それと if(i = j) とか明らかにバグってそうなんだが大丈夫？ 本当に if((i = j) != 0) こそ意図したコードなのかそれとも if(i == j) の typo なのかまるでコード理解する気にならねえ！

そんで最後に正常値と判定された集合の平均を計算しこれを「正しい時刻」として返している。

24 	int ext;
...
28 	long average;
...
68 /****/
69 compute:
70 	ext = maxind - minind + 1;
71 	average = 0;
72 	for (i=minind; i<=maxind; i++)
73 		average += x[i];
74 	average /= ext;
75 	return(average);

小数点以下切捨てかぁ。

賢明なる読者(検索エンジンは機能不全で SNS 上の広報を拒否する当チラシの裏に読者など存在しえないわけだが)もう初見でこのコード怪しい…ってなるよね。

ご安心ください 4.4BSD の時点ですでに総ツッコみ入れられて完全にコードが書き直されています。 なので上記のコードはある意味 You are not expected understand this だったのだ。

46 /*
47  * Compute a corrected date.
48  *	Compute the median of the reasonable differences.  First compute
49  *	the median of all authorized differences, and then compute the
50  *	median of all differences that are reasonably close to the first
51  *	median.
52  *
53  * This differs from the original BSD implementation, which looked for
54  *	the largest group of machines with essentially the same date.
55  *	That assumed that machines with bad clocks would be uniformly
56  *	distributed.  Unfortunately, in real life networks, the distribution
57  *	of machines is not uniform among models of machines, and the
58  *	distribution of errors in clocks tends to be quite consistent
59  *	for a given model.  In other words, all model VI Supre Servres
60  *	from GoFast Inc. tend to have about the same error.
61  *	The original BSD implementation would chose the clock of the
62  *	most common model, and discard all others.
63  *
64  *	Therefore, get best we can do is to try to average over all
65  *	of the machines in the network, while discarding "obviously"
66  *	bad values.
67  */

おお、統計学知らずによくプログラマやってんなおじさん「統計学知らずによくプログラマやってんな」が現れて中央値を使うようになっているね(ニッコリ)、そらそうよ。

まず最初に good かつ measure() で応答のあったスレーブだけで仮の中央値を計算する。

 68 long
 69 networkdelta()
 70 {
 71 	struct hosttbl *htp;
 72 	long med;
...
 75 	long x[NHOSTS];
 76 	long *xp;
 77 	int numdelta;
...
 80 	/*
 81 	 * compute the median of the good values
 82 	 */
 83 	med = 0;
 84 	numdelta = 1;
 85 	xp = &x[0];
 86 	*xp = 0;			/* account for ourself */
 87 	for (htp = self.l_fwd; htp != &self; htp = htp->l_fwd) {
 88 		if (htp->good
 89 		    && htp->noanswer == 0
 90 		    && htp->delta != HOSTDOWN) {
 91 			med += htp->delta;
 92 			numdelta++;
 93 			*++xp = htp->delta;
 94 		}
 95 	}
...
104 	med /= numdelta;

good とはコード引用はしないが

  • マスター自身
  • -F オプションで指定されたホスト名に一致
  • -G オプションで指定された netgroup(5) に属するホスト名に一致

なので後ろふたつ未指定ならマスター時刻となる。 ところでお気づきかと思いますが中央値じゃなくて平均値じゃねーか！

もうツッコむのに疲れたのでいいやお次。

仮の中央値(実際は平均値)から VALID_RANGE すなわち妥当な範囲(誤差プラマイ 20 秒) 以外は異常値とし除外した集合の中央値(今度は本当)を出す。

80 #define	MAXADJ		20		/* max adjtime() correction in sec */
...
101 #define VALID_RANGE (MAXADJ*1000)	/* good times in milliseconds */

105 	eps = med - x[0];
...
109 	med = median(med, &eps, &x[0], xp+1, VALID_RANGE);

libm とかですらソートした結果の真ん中でいいじゃんで実装しない中央値である。 それをわざわざソートせずに計算しようとする median() の実装まではもうめんどくさいので追いかけない。 今度はちゃんと中央値返してくれることでしょう(願望)。

そしてお次は good なホストであれば中央値から VGOOD_RANGE すなわち 1/60 秒未満それ以外は GOOD_RANGE すなわち 1/30 秒の範囲内に収まる集合の中央値を算出する。

40 #define	CLK_TCK		60		/* ticks per second */

72 /* Best expected round trip for a measurement.
73  * This is essentially the number of milliseconds per CPU tick (CLK_TCK?).
74  * All delays shorter than this are usually reported as 0.
75  */
76 #define MIN_ROUND ((1000-1)/CLK_TCK)
...
102 #define GOOD_RANGE (MIN_ROUND*2)
103 #define VGOOD_RANGE (MIN_ROUND-1)

111 	/*
112 	 * compute the median of all values near the good median
113 	 */
114 	hidelta = med + GOOD_RANGE;
115 	lodelta = med - GOOD_RANGE;
116 	higood = med + VGOOD_RANGE;
117 	logood = med - VGOOD_RANGE;
118 	xp = &x[0];
119 	htp = &self;
120 	do {
121 		if (htp->noanswer == 0
122 		    && htp->delta >= lodelta
123 		    && htp->delta <= hidelta
124 		    && (htp->good
125 			|| (htp->delta >= logood
126 			    && htp->delta <= higood))) {
127 			*xp++ = htp->delta;
128 		}
129 	} while (&self != (htp = htp->l_fwd));
130 
131 	if (xp == &x[0]) {
...
134 		return med;
135 	}
136 
137 	if (xp == &x[1]) {
...
140 		return x[0];
141 	}
...
146 	return median(med, &eps, &x[0], xp, 1);

ちなみに CLK_TCK は ハードクロックの秒あたりのクロック数、60kHz なら 60 となる。 うん HZ マクロの方は 100 返してくるんだけどなガハハ。 どうして一致してないんですか？この謎はいずれ調べてみようかと思う。

measure() で適当に 5 ミリ秒とどんぶり勘定してたのよりはクロック数計算するだけマシではあるが、計算速度の進歩を前にすると誤差大きくする結果になるよねこれ。

correct() による時刻調整

まずはマスター自身の時刻調整。

  • プラマイ 20 秒以内なら adjtime(2) で時刻調整
  • それ以上なら settimeofday(2) で強制同期

と前回解説した通りである。

 18 /* 
 19  * `correct' sends to the slaves the corrections for their clocks
 20  */
 21 
 22 correct(avdelta)
 23 long avdelta;
 24 {
...
 26 	int corr;
 27 	struct timeval adjlocal;
...
 42 	corr = avdelta - hp[0].delta;
 43 	adjlocal = mstotvround(&corr);
 44 	adjclock(&adjlocal);
...
 74 }
...
105 adjclock(corr)
106 struct timeval *corr;
107 {
108 	struct timeval now;
...
111 		if (corr->tv_sec < MAXADJ && corr->tv_sec > - MAXADJ) {
112 			(void)adjtime(corr, (struct timeval *)0);
113 		} else {
...
117 			(void) gettimeofday(&now, (struct timezone *)0);
118 			timevaladd(&now, corr);
119 			if (settimeofday(&now, (struct timezone *)0) < 0)
120 				syslog(LOG_ERR, "can't set time");
121 		}
...
123 }

あとはスレーブに TSP_ADJTIME コマンドを投げるだけである。

49 	for(i=1; i<slvcount; i++) {
...
51 			corr = avdelta - hp[i].delta;
52 			msgs.tsp_time = mstotvround(&corr);
53 			msgs.tsp_type = (u_char)TSP_ADJTIME;
54 			(void)strcpy(msgs.tsp_name, hostname);
55 			answer = acksend(&msgs, &hp[i].addr, hp[i].name,
56 			    TSP_ACK, (struct netinfo *)NULL);
...
70 	}

ほい、マスター側のソース散策はこれでおしまい。

次回

スレーブ側のコードを読んでいくよ。