ARM ARM読んでいるが

メモリオーダリングの話が出てきた。今ひとつイメージし切れない箇所があったので、ARM ARMでも紹介されていた「Memory Consistency Models for Shared Memory-Multiprocessors」を読んでみることにした。
早速「memory consistency models」ググってみると・・・言及されていた論文(ftp://reports.stanford.edu/pub/cstr/reports/csl/tr/95/685/CSL-TR-95-685.pdf)の他にこんなチュートリアル(http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf)も見つけた。
早速チュートリアルから取りかかることにした。この手のPDF読むためにNexus7を買った甲斐があったというものだ。

CFSのvruntimeの値の粒度

Linuxのスケジューラ CFSの実装を読んでいる。このスケジューラはタスクの中で一番vruntimeの少ないタスクを次の動作タスクに選ぶ。

このvruntimeの粒度がどの程度のものか知りたくソースを読んだ。
結論から言うと、ナノ秒単位のモノトニックタイマがvruntimeのもとになっていることがわかった。

kernel/sched/fair.cの__update_curr()でvruntimeに足している値はdelta_exec_weighted。
delta_exec_weightedはdelta_execから作られる。
さらにdelta_execはupdate_curr()で「rq_of(cfs_rq)->clock_task」と「curr->exec_start」の差から作られる。
ということは「rq_of(cfs_rq)->clock_task」と「curr->exec_start」のいずれかの単位がわかれば目的が達成できることになる。

kernel/sched/fair.cを見ると、「curr->exec_start」はある時点での「rq->clock_task」である。
つまり、「rq->clock_task」の単位を調べるしかない。

grepすると、core.cにclock_taskを更新する関数があることがわかる。

 752 static void update_rq_clock_task(struct rq *rq, s64 delta)
 753 {
(略)
 804   rq->clock_task += delta;

update_rq_clock_task()を呼び出しているのがupdate_rq_clock()である。
こいつは以下の関数。

 117 void update_rq_clock(struct rq *rq)
 118 {
 119   s64 delta;
 120 
 121   if (rq->skip_clock_update > 0)
 122     return;
 123 
 124   delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
 125   rq->clock += delta;
 126   update_rq_clock_task(rq, delta);
 127 }

元になっているのが、sched_clock_cpu()であることがわかる。
この関数はkernel/sched/clock.cにいる関数。

sched_clock_cpu()はsched_clock_remote()もしくはsched_clock_local()経由で時間を取得している。
簡単そうなsched_clock_local()をみる。

CPUごとにsched_clock_data構造体を持っていて、こいつを使って時間を計算している。
やっていることは今ひとつよくわからんが、sched_clock()で取得している時間を使っていることから、この関数の戻り値の単位がわかれば目的達成ということになる。

sched_clock()はkernel/sched/clock.cで以下の様に定義されている。

 70 /*
 71  * Scheduler clock - returns current time in nanosec units.
 72  * This is default implementation.
 73  * Architectures and sub-architectures can override this.
 74  */
 75 unsigned long long __attribute__((weak)) sched_clock(void)
 76 {
 77   return (unsigned long long)(jiffies - INITIAL_JIFFIES)
 78           * (NSEC_PER_SEC / HZ);
 79 }
 80 EXPORT_SYMBOL_GPL(sched_clock);

この関数のコメントや実装から、モノトニックなタイマをナノ秒単位にしたものだということがわかる。さらにこの実装はweakシンボルなので、上書きが可能である。

ちなみにx86の場合、arch/x86/kernel/tsc.cにsched_clock()の別実装がある。
こいつはTSCの値を元にしてナノ秒単位のモノトニックな時間経過の値を返している。
TSCについては http://en.wikipedia.org/wiki/Time_Stamp_Counter を参考にすると良い。
今日は遅いので、ここでおしまい。

dtraceのバッファまわりなど

dtraceのバッファまわりに関して資料を読んだので、その概要をまとめておく。

主バッファ
主バッファとは、トレースアクションがデフォルトで使用するバッファ。
主バッファはCPUごとに割り当てられる。
主バッファには、バッファの使われ方を示す「ポリシ」がある。

(1)switchポリシ
CPU 単位でバッファのペアを割り当てるポリシ。
ペアの片方はアクティブなバッファ、もう片方は非アクティブなバッファ。
DTrace コンシューマバッファの読み取りを試みたときカーネルは以下2点を行う。
(1)非アクティブなバッファとアクティブなバッファの切り替え
(2)元々アクティブであったバッファの内容をDTrace コンシューマにコピーする

なお、このポリシでは、アクティブなバッファに収まりきらない量のデータをトレースしようとした場合、そのデータは欠落となり、CPU 単位の欠落カウントが増分されることに注意する。

(2)fillポリシ
このポリシでは、CPUごとの主バッファーの少なくとも1つがいっぱいになったと見なされた時点で、明示的にトレースを停止する。

(3)ringポリシ
主バッファはリングバッファ。主バッファがいっぱいになった場合、一番古いものが上書きされる。

投機トレース
一時的にトレースバッファとは別の場所にデータをトレースしておき、あとで「破棄」(discard)するか、トレースバッファに「コミット」(commit)するのかを決めることができる。
これによって、本当に欲しいデータのみをトレースバッファに保存できるため、大量のトレースデータに埋もれずに済む。

使い方としては....
(1)speculation()をコールし、投機用のバッファを割り当て識別子を取得する。
ちょうどopen()のようなイメージだと思う。
(識別子は、スレッドローカル変数にでも保存しておくのが良い)

(2)投機バッファにトレースデータを保存する場合、speculate()を呼び出す。
これは「以後の節内の処理でのトレースデータの保存先を(1)で割り当てた投機バッファにする」ことを意味する。
speculate()の引数は、(1)で取得した識別子である。

(3)投機バッファの中身をコミットしたい場合はcommit()を、破棄したい場合はdiscard()をそれぞれ呼び出す。
これら2関数の引数は両方共、(1)で取得した識別子である。

dtraceの集積体について

dtraceの集積体について調べてみたので、簡単にまとめてみました。

dtraceの集積体とは集積関数の実行結果を格納するためのオブジェクトです。
ちょうどハッシュに似た表現形式をとります。

集積関数とは、「データのサブセットに集積関数を適用し、その結果に再度集積関数を適用した結果」と、「データ全体に集積関数を適用した結果」が等しくなる関数のことです。

例えば、データの集合{3,4,6,7,2,1}があったとします。
このとき、最大値を求めるmaxを集合全体に適用すると、当然結果は7になります。

で、この集合を2つずつの要素に分けた3つのサブセット({3,4},{6,7},{2,1})に分解した結果それぞれにmaxを適用すると...

max({3,4}) = 4
max({6,7}) = 7
max({2,1}) = 2

となります。これが「データのサブセットに集積関数を適用し」になります。
そして、この結果の集合{4,7,2}に対して再度maxを適用すると結果が7になり、集合全体に適用した結果と等しくなります。これが「その結果に再度集積関数を適用」になります。

集積関数には他にもmin,max,avg,quantizeなどがあります。
DスクリプトNetBSDでの使用例は以下のようになります。

fbt:netbsd:sys_write:entry
{
	self->ts = timestamp;
}

fbt:netbsd:sys_write:return
/self->ts/
{
	@time[execname] = avg(timestamp - self->ts);
	self->ts = 0;
}

これは、sys_writeの実行時間の平均を求めるスクリプトになります。
「@time[execname]」というのが集積体になります。
これはexecname、つまり実行プロセスごとにsys_writeの実行時間の平均を格納します。
スクリプトをCtrl-Cで中断すると以下のような表示をします。

# fg
dtrace -s writetime.d
^C

  tcsh                                                          14392
  sshd                                                          25188
  dtrace                                                        25899
  cat                                                           26828
# 

確かにsys_writeを実行したプロセスごとに実行時間が表示されています。
これは便利そうだ・・・。

年初め

明けましておめでとうございます。今年もいろいろとやりたいことがあります。
浮気性なのはちとアレなのですが、今のところ"コンピュータ系の独学"でやってみたいことは二つあります。

(1)NetBSDのdtraceの研究
(2)Linuxのスケジューラ(CFS/BFS)のソースコードリーディング

(1)について。NetBSDのdtraceはi386のみサポートされていますが、どの程度デバッグに役立つのかその可能性を探りたいのです。そのため、昨年から(かなり間が開きましたが)勉強を始めてみたのです。

(2)について。自分は職業でNetBSDをいじっていますが、NetBSD以外のOS実装をソースコードリーディングを通じて知ることで、未知のソースに対する迅速な理解力を養いたいと考えています。
また、単純にBFSをはじめとするスケジューラに興味を持ったということもあります。
NetBSDのスケジューラが「いいものなのか」どうかを知るためには他の実装を知る必要があります。

酒を飲みつつも、技術者として勉強は忘れないようにしたいものです。
それでは、今年もよろしくお願いします。

Linuxのhuge zero pageについて

記事のソースは「http://lwn.net/Articles/517465/」。
匿名ページは0クリアされるが、"多くのゼロフィルされたページには書き込まれることはない。それらのページはプロセスのライフサイクル中ずっと0のまま"という事に気づいた人が。
で、やったことは「匿名ページに対するリードアクセスで、ROなゼロフィル共有ページを該当アドレス空間にマップ。で、実際に該当アドレス空間に書き込みがあったときにフォルトが発生し、そこでようやっと物理ページを割り当てる。」という動作。これが、THP(Transparent Huge Page)に対する改良か。

基本的にCOWに近い技術ですね。まあ、基本は変わらない、という事だと強く感じた次第。

NetBSD dtraceの変数に関するメモ書きなど

今回もあまり調査が進んでいないdtrace。変数関係について資料を読んだので、メモ書き、メモ書き・・・。

スカラ変数(Scalar Variables)
スカラ変数のところの説明によれば、変数を使う際には、明示的な変数宣言は無くてもよいそうだ。

BEGIN
{
	x = 123;
}

連想配列(Associative Arrays)
name[key] = expressionで表現される。
面白いのはkeyは「カンマで区切られた1つまたはそれ以上のexpression」で表現されることである。
例えばPerlみたいに
a["hoge"] = 456;
としてもよいし、
a[123,"hoge"] = 456;
としてもよい。(この場合、「123,"hoge"」がキーになる。)

スレッドローカル変数(Thread-Local Variables)
「->」オペレータを特殊な識別子selfに適用すればよい。
例えば、以下のように。(注意:以下のdtraceスクリプトはプロバイダ名などの関係でNetBSDでは動きません。)

syscall::read:entry
{
	self->read = 1;
}

しかし、「スレッド」の実体が今ひとつよくわからん。

節内ローカル変数(Clause-Local Variables)
説明によれば、以下のような性質を持っている。
*CやC++のオート変数に似ている。
*Dtrace変数の中で唯一0初期化されない変数である。
*アクセスする際には「this->変数名」でアクセスする。
*明示的に変数宣言する際にはthisキーワードを使って宣言を行う。例えば

this int x;
this char c;

BEGIN
{
	this->x = 123;
	this->c = 'D';
}

のように。
しかし、auto変数と違って、異なる節の間で値を共有してしまう。
例えば、以下のスクリプトをclause.dに保存する。

this int x;
this char c;

BEGIN
{
	this->x = 123;
	this->c = 'D';
}

END
{
	printf("%d %c\n",this->x,this->c);
}

dtrace -s clause.dを実行したあとシェルに制御が戻ってこなくなるのでCtrl-Cすると結果が以下のように表示される。

dtrace: script 'clause.d' matched 2 probes

^C
CPU     ID                    FUNCTION:NAME
  0      2                             :END 123 D

節内で値が共有できてしまうのなら、それってスカラ変数とかとどう違うのかが今ひとつわからない。
この辺り、もう少し調べてみる必要がありそうだな・・・。

あとは、アクションについて。
http://docs.oracle.com/cd/E24845_01/html/E22189/gcfbn.html#gcggi
Dtraceの代表的な組み込み変数とアクションについて記載されている。

上のリンク先のスクリプトを実行するときはプロバイダ名に注意。NetBSDでは、syscallプロバイダでなくfbtプロバイダである。

こことOracleのWebPageを参考に次は集積体を追ってみたい。