永遠まで鳴り響く 時の鐘を止めて

この投稿は NetBSD Advent Calendar 2017 - Qiita 12月16日の内容になります。

『青い精霊達よ… その力をもって 永遠まで鳴り響く 時の鐘を止めて...』
ゲームアーツの超名作RPG"グランディア"のヒロイン、フィーナが覚える"時の門"という魔法の発動時のセリフです。
中学生だった当時はセガサターンを持っていなかったのでプレイを諦めていたのですが、遅れてPS版が発売されたので速攻購入して猿のようにやり込んだ思い出があります。
フィーナ専用魔法の"時の門"は"自分以外の時間を止めるという中二病をくすぐりまくる効果"を発揮しますが、習得がとても大変で、2徹ぐらいしてようやく覚えさせたような記憶が...

さて、NetBSDで時の門を発動させてみましょう!

方法はbintime_add()を下記のようにコメントしてカーネルコンパイルすれば大丈夫です!
https://nxr.netbsd.org/xref/src/sys/sys/time.h#118

static __inline void
bintime_add(struct bintime *bt, const struct bintime *bt2)
{
#if 0
	uint64_t u;

	u = bt->frac;
	bt->frac += bt2->frac;
	if (u > bt->frac)
		bt->sec++;
	bt->sec += bt2->sec;
#endif
}


もしくは、bintime_add()の上に定義してあるbintime_addx()をbintime_add()のようにコメントした後に
https://nxr.netbsd.org/xref/src/sys/sys/time.h#107

static __inline void
bintime_addx(struct bintime *bt, uint64_t x)
{
#if 0
	uint64_t u;

	u = bt->frac;
	bt->frac += x;
	if (u > bt->frac)
		bt->sec++;
#endif
}

カーネルの構成ファイルからオーディオ関係のドライバを外して、カーネルコンパイルしてやると、同じように時が止まった世界を味わうことができます。
https://nxr.netbsd.org/xref/src/sys/arch/i386/conf/GENERIC#1397


では、bintime_addx()がカーネル内のどこで使われているのか?

いろいろ使われていますが一番大事なところはtc_windup()だと思います。(違っていたらすいません...)
https://nxr.netbsd.org/xref/src/sys/kern/kern_tc.c#751

では、今度はbintime_addx()やbintime_add()のコメントを戻してtc_windup()の中身のdeltaをいじって0を代入してみましょう。

	/*
	 * Capture a timecounter delta on the current timecounter and if
	 * changing timecounters, a counter value from the new timecounter.
	 * Update the offset fields accordingly.
	 */
#if 0
	delta = tc_delta(th);
#endif
	delta = 0;
	if (th->th_counter != timecounter)
		ncount = timecounter->tc_get_timecount(timecounter);
	else
		ncount = 0;
	th->th_offset_count += delta;
	bintime_addx(&th->th_offset, th->th_scale * delta);

systemが0:-1.95だと... いろいろおかしいようです...
う〜ん、今度は"刻が未来にすすむと 誰がきめたんだ〜"と∀ガンダムの世界になってしまいました...
deltaって何でしょう?


delta?マクロス?

0を代入していじってみたdeltaですが、tc_windup()ではtc_delta()を使用して値を算出していました。
https://nxr.netbsd.org/xref/src/sys/kern/kern_tc.c#303

static inline u_int
tc_delta(struct timehands *th)
{
	struct timecounter *tc;

	tc = th->th_counter;
	return ((tc->tc_get_timecount(tc) -
		 th->th_offset_count) & tc->tc_counter_mask);
}

tc_get_timecount?th_offset_count?tc_counter_mask?
やはり、変数の意味がわからないとツライものがあります... そこでtimecounter構造体を見てみましょう!
https://nxr.netbsd.org/xref/src/sys/sys/timetc.h#46

struct timecounter {
	timecounter_get_t	*tc_get_timecount;
		/*
		 * This function reads the counter.  It is not required to
		 * mask any unimplemented bits out, as long as they are
		 * constant.
		 */

tc->tc_get_timecountは関数ポインタのようです... 何が入っているのかな? 検索してみます。
https://nxr.netbsd.org/s?n=25&start=0&q=tc_get_timecount&sort=relevancy&project=src,

どうやら、 /src/sys/arch/powerpc/や/src/sys/arch/sparc/sparc/、/src/sys/arch/arm/のようにマシン依存(Machine Dependent: MD)のところの関数が入っているようですね...

一般的に使われているx86なマシンだとtsc_get_timecount()が代入されているようです。
(HPET?(∩゚д゚)アーアーきこえなーい)
https://nxr.netbsd.org/xref/src/sys/arch/x86/x86/tsc.c#62

tsc_get_timecount()の定義を見てみると...
https://nxr.netbsd.org/xref/src/sys/arch/i386/i386/i386func.S#245

ENTRY(tsc_get_timecount)
	movl	CPUVAR(CURLWP), %ecx
1:
	pushl	L_NCSW(%ecx)
	rdtsc
	addl	CPUVAR(CC_SKEW), %eax
	popl	%edx
	cmpl	%edx, L_NCSW(%ecx)
	jne	2f
	ret
2:
	jmp	1b
END(tsc_get_timecount)

とrdtscというCPUの命令を発行しているようです... rdtscとは?調べてみると...
__rdtsc
rdtsc ‐ 通信用語の基礎知識
TSC ‐ 通信用語の基礎知識

どうやらCPUの中にあるカウンタ(タイマー)の値を読み出す命令のようですね!

では、次のtc->tc_counter_maskは何が代入されているのかというと、~0Uなので、無視して良いと思います。
https://nxr.netbsd.org/xref/src/sys/arch/x86/x86/tsc.c#64

最後のth->th_offset_countには何が入っているのか?というと、もう一度、一度tc_windup()を見てみましょう...

	/*
	 * Capture a timecounter delta on the current timecounter and if
	 * changing timecounters, a counter value from the new timecounter.
	 * Update the offset fields accordingly.
	 */
	delta = tc_delta(th);
	if (th->th_counter != timecounter)
		ncount = timecounter->tc_get_timecount(timecounter);
	else
		ncount = 0;
	th->th_offset_count += delta;
	bintime_addx(&th->th_offset, th->th_scale * delta);

th_offset_countには今調べているtc_delta()の戻り値が入っています。
つまり、tc_delta()の動きは、1回目のth_offset_countが0だとすると...

1回目:th_offset_count = 0 + (現在のCPUのカウンタ - 0)
2回目:th_offset_count = 1回目のth_offset_countの値 + (現在のCPUのカウンタ - 1回目の時点でのCPUのカウンタ)
3回目:th_offset_count = 2回目のth_offset_countの値 + (現在のCPUのカウンタ - 2回目の時点でのCPUのカウンタ)
...

のようなイメージになるんじゃないかなぁ...と思います。
また、コメントにも(offset at last time update (tc_windup())と書いてあります。
https://nxr.netbsd.org/xref/src/sys/kern/kern_tc.c#102

では、deltaの意味がわかってきたので、次はdeltaを掛けているth_scaleを調べてみたいともいます。

	/*
	 * Capture a timecounter delta on the current timecounter and if
	 * changing timecounters, a counter value from the new timecounter.
	 * Update the offset fields accordingly.
	 */
	delta = tc_delta(th);
	if (th->th_counter != timecounter)
		ncount = timecounter->tc_get_timecount(timecounter);
	else
		ncount = 0;
	th->th_offset_count += delta;
	bintime_addx(&th->th_offset, th->th_scale * delta);
scale?ソードアート・オンライン オーディナル・スケール?

実はtc_windup()やtc_get_timecount()の関数名の頭についているtcには意味があります。
tcはtimecounterの略なのです。
NetBSDOpenBSD(FreeBSDも?)はカーネル内でtimecounterの仕組みを使って時刻の管理をしています。
timecounter.9
論文はこちら
http://phk.freebsd.dk/pubs/timecounter.pdf


そして、timecounterのscaleにはお約束があります。

標準の刻み=1秒あたり 2^64 カウントする←これ重要

th_scaleの算出方法もtc_windup()に書いてあります。
https://nxr.netbsd.org/xref/src/sys/kern/kern_tc.c#833

	/*-
	 * Recalculate the scaling factor.  We want the number of 1/2^64
	 * fractions of a second per period of the hardware counter, taking
	 * into account the th_adjustment factor which the NTP PLL/adjtime(2)
	 * processing provides us with.
	 *
	 * The th_adjustment is nanoseconds per second with 32 bit binary
	 * fraction and we want 64 bit binary fraction of second:
	 *
	 *	 x = a * 2^32 / 10^9 = a * 4.294967296
	 *
	 * The range of th_adjustment is +/- 5000PPM so inside a 64bit int
	 * we can only multiply by about 850 without overflowing, but that
	 * leaves suitably precise fractions for multiply before divide.
	 *
	 * Divide before multiply with a fraction of 2199/512 results in a
	 * systematic undercompensation of 10PPM of th_adjustment.  On a
	 * 5000PPM adjustment this is a 0.05PPM error.  This is acceptable.
 	 *
	 * We happily sacrifice the lowest of the 64 bits of our result
	 * to the goddess of code clarity.
	 *
	 */
	if (s_update) {
		scale = (u_int64_t)1 << 63;
		scale += (th->th_adjustment / 1024) * 2199;
		scale /= th->th_counter->tc_frequency;
		th->th_scale = scale * 2;
	}

th->th_adjustmentは0が代入されていると考えて無視してください。
なぜ、scale = (u_int64_t)1 << 64ではなく、scale = (u_int64_t)1 << 63なのか、自分では理解できませんでしたが、最終的にth->th_scale = scale * 2で辻褄合わせをしているので問題は無いと思います。

th->th_counter->tc_frequencyにはCPUのクロックが代入されています。
(正確にはCPUのクロックではなく、タイマーのクロックが代入されていますが、今回はCPUのクロックをタイマーとします)

そして、scale /= th->th_counter->tc_frequencyで1クロックの間にどれだけカウントが進んでいるか → scaleを求めています。
"scale = 2^64 / CPUの周波数"という感じなのかな?と思います。

ああすっきりした。
これで、bintime_addx()やbintime_add()、tc_deltaをいじると、時間が止まったように見えるという理由がわかったと思います。
時刻(クロック)が加算されないため、なんですよね。

clock?クロックワーク・プラネット?

さて、このtc_windup()がどこから呼び出されているかというと...
これまた色々なところから呼ばれているんですが、一番重要なところはtc_ticktock()から呼ばれているところだと思います。
(違っていたらすいません...)
https://nxr.netbsd.org/xref/src/sys/kern/kern_tc.c#1319

さらにさらに、tc_ticktock()がどこから呼ばれているか?というとhardclock()から呼ばれています。
https://nxr.netbsd.org/xref/src/sys/kern/kern_clock.c#246

hardclock()とはナンジャラホイ?というかというと、クロック割込みハンドラから呼ばれる処理のようです。
https://nxr.netbsd.org/xref/src/sys/arch/x86/x86/lapic.c#564

void
lapic_clockintr(void *arg, struct intrframe *frame)
{
	struct cpu_info *ci = curcpu();

	ci->ci_lapic_counter += lapic_tval;
	ci->ci_isources[LIR_TIMER]->is_evcnt.ev_count++;
	hardclock((struct clockframe *)frame);
}

では、クロック割り込みとはナンジャラホイ?というかというと、タイマーをセットすることによって発生する一秒の間に定期的に起こる割り込みの事を言います。

このタイミングはhzというカーネルの構成ファイルで制御することが可能で、hzの数字を大きくすればそれだけクロック割り込みの発生頻度が高くなります。
https://www.daemon-systems.org/man/hz.9.html

そして、クロック割り込みが発生した時に処理される関数がクロック割込みハンドラになります。

たとえば下記はmc146818という時計にクロック割り込みの頻度(hz)を設定している処理です。
https://nxr.netbsd.org/xref/src/sys/dev/dec/mcclock.c#87

hzの数字が大きければ大きいほど良いのか?というと、大きければそれだけ割込みの頻度があがってシステムがおもくなってしまうので、CPUが遅いマシンはhzの数字が小さい場合が多いようです。

LUNA-Iはhz(一秒の間のクロック割り込みの回数)が60回
https://nxr.netbsd.org/xref/src/sys/arch/luna68k/luna68k/clock.c#73

Alphaはhz(一秒の間のクロック割り込みの回数)が1024回
https://nxr.netbsd.org/xref/src/sys/arch/alpha/conf/std.alpha#9

どうやらLUNA-IはCPUがMC68030で20Mhzととても遅いのでクロック割込みの頻度が少な目のようです...

じゃぁCPUが速いマシンだったらhzの数字を大きくしても大丈夫なのか?というと、NetBSDではハードウェアがからむ時刻関係の処理は最高でも1秒間に1000回を想定しているらしく、
仮にhzを5000に設定してhardclock()を一秒間に5000回呼び出したとしても、inittimecounter()でtc_tickを計算して、tc_ticktock()でtc_windup()が呼び出される回数を制御してるようです。
https://nxr.netbsd.org/xref/src/sys/kern/kern_tc.c#1304

/*
 * Timecounters need to be updated every so often to prevent the hardware
 * counter from overflowing.  Updating also recalculates the cached values
 * used by the get*() family of functions, so their precision depends on
 * the update frequency.
 */

static int tc_tick;

void
tc_ticktock(void)
{
	static int count;

	if (++count < tc_tick)
		return;
	count = 0;
	mutex_spin_enter(&timecounter_lock);
...
	tc_windup();
	mutex_spin_exit(&timecounter_lock);
}

void
inittimecounter(void)
{
	u_int p;

	mutex_init(&timecounter_lock, MUTEX_DEFAULT, IPL_HIGH);

	/*
	 * Set the initial timeout to
	 * max(1, ).
	 * People should probably not use the sysctl to set the timeout
	 * to smaller than its inital value, since that value is the
	 * smallest reasonable one.  If they want better timestamps they
	 * should use the non-"get"* functions.
	 */
	if (hz > 1000)
		tc_tick = (hz + 500) / 1000;
	else
		tc_tick = 1;
...
}

これでようやくNetBSDのtimecounter(9)の処理の概要が掴めたかと思います。

  1. タイマ割り込みが一秒間にhz回発生する
  2. hardclock()が呼ばれる
  3. tc_ticktock()が呼ばれる
  4. tc_windup()が呼ばれる
  5. CPUのクロック(タイマーのクロック)を読んで"標準の刻み=1秒あたり 2^64 カウント"を超えていたら1秒加算する


という感じかなと思います!

それでは後編に続く!