memcached

※本記事は当初HTMLに整形せずに掲載してしまい、ご覧になった方にはご不便をおかけしました。お詫び申し上げます。

consistent hashingの記事でmemcachedが名前だけ出てきたので少し調べてみた。

memcachedは単純なキーと値のペアによる分散キャッシュサーバ。高速で、非常に台数にスケールすることが利点という。ほとんど設定いらずでインストールしてそのまま起動できる。

動的に生成するウェブページのキャッシュ等に用いられる。キャッシュの他HTTPのセッション情報のような消えてしまっても致命的でない情報の保持に使われることもある。検索してみると国内でもmixiやはてな等で広く使われているようだ。各種言語のクライアントライブラリも多い。

続きを読む

Consistent Hashing

Tom White's Blog: Consistent Hashing(翻訳: ConsistentHashing - コンシステント・ハッシュ法)でconsistent hashingというアルゴリズムを知った。大略こういうことらしい。

問題

複数台のキャッシュサーバがあり、オブジェクトのキャッシュをどのサーバに配置するかを決めたい。

普通のハッシュ利用法だとどうなるか

オブジェクトのハッシュ値 mod N (Nはキャッシュサーバの台数)で決める。

しかし、これではキャッシュサーバを追加したり削除したりすると全てのオブジェクトのキャッシュ配置先が変わってしまう。

望ましいのは

キャッシュサーバを追加すれば既存のサーバから少しずつ分担が新しいサーバに移動し、キャッシュサーバが取り除かれれば残りのサーバに負担が分散、それ以外のオブジェクトのキャッシュ先は変わらない、というのがよい。

Consistent Hashingとは

キャッシュサーバを決めるのに、mod Nをしない。つまりサーバの台数に依存した計算をしない。しかしそれでどうやってキャッシュサーバを決定するのだろうか。

続きを読む

Common Lisp: loopマクロ用法抄

GrahamのANSI Common Lispでは嫌われていて碌に説明のないloopマクロ。一方、Practical Common Lispでは対照的に好んで用いられていて、全編に渡って頻繁に使われている。しかしloopマクロは難しいという意識があるのかその説明は第22章とかなり後回しにされており、ちぐはぐな感を受ける。ここでは、LOOP for Black-Belts という題のつけられたその章で解説されているloopマクロの用法を整理してみた。

ANSI Common Lispでの黒魔術扱いに敬遠していたloopマクロだったが、こうして整理してみるとそれほど難しく考えずとも便利に使うことができそうだ。

続きを読む

インタプリタとシグナル

シグナルはユーザプロセスの任意の時点で処理される可能性がある。そのため、シグナルハンドラの中で行えることは、再入可能な関数の呼び出しなどのような、状態の一貫性に影響しないものに制限される。

インタプリタのユーザ言語でシグナルハンドラも書けるようにする場合は、割込まれたときに直接実行せず、インタプリタが安全に処理できる時点まで遅延させる方法がとられる。

シグナルが発生すると、実装言語のシグナルハンドラではシグナルが送られたことの記録だけを行う。一方、インタプリタは適当なタイミングでそれをチェックしていて、割込みが記録されていればユーザ言語で書かれたハンドラのコードを実行する。

UNIXのシグナル処理

プロセスにシグナルが送られると、カーネルはプロセス表のビットを立ててシグナルの発生を記録する。

シグナルの処理はカーネルからユーザプロセスに処理が移るタイミングでのみ行われる。すなわち、ユーザプロセスがシステムコールから戻るときや、タイムスライスの切り替えによってユーザプロセスの実行を再開するときだ。ユーザプロセスの実行中に割込みが発生してカーネルに制御が移る場合は、カーネルは割込みを処理した後でユーザプロセスに戻る前にシグナルを処理し、それからユーザプロセスに戻る。

シグナルハンドラを実行する間もカーネルにとっては通常のユーザプロセスの実行状態にすぎないので、さらにシグナルが割込む可能性も当然ある。ただしBSDやPOSIX.1では、カーネルがシグナルハンドラを起動するときに原因シグナルを自動的にマスクするため、同じシグナルによって再入することはない(マスクされている間に発生したシグナルはブロックされ、マスクが解除されるまで処理が遅延される)。

シグナルハンドラを実行させる仕組み

プロセスにはカーネルから制御を戻すときのレジスタコンテクストが記録されている。これには次にどのアドレスから実行を再開するかも含まれる。 カーネルはこれを変更して、ユーザプロセスがシグナルハンドラから実行を再開するように仕向ける。ただしそれだけではまずいので、シグナルハンドラからリターンすると本来の実行再開アドレスに戻るように、ユーザプロセスのスタックに擬似的なスタックフレームを積んでおく。

このように操作してからユーザプロセスを再開すると、カーネルにとってはユーザプロセスがそのまま実行を再開したのと同じだが、ユーザプロセスではシグナルハンドラを実行することになる。シグナルハンドラの実行が終わるとretで本来の再開アドレスに飛ぶため、プロセスはシステムコールからの復帰したり、プロセス切り替えから再開したように見える。

実際は、スタックポインタやプログラムカウンタだけでなく作業レジスタやシグナルマスクも含めて完全に元のコンテクストを復元する必要があるため、シグナルハンドラから単に再開アドレスに復帰するだけでは不十分で、もう少し仕組みを凝らす必要がある。

そこで、シグナルハンドラに指定された関数を呼び出し、そこから復帰したらコンテクストを完全に復元するというコード(動作の様子から、これをシグナル・トランポリンと呼ぶ)を予め用意しておく。カーネルがユーザプロセスのコンテクストをいじる際は直接シグナルハンドラから再開するのでなく、このトランポリン・コードから再開するようにする。このときトランポリンにはシグナルハンドラのアドレスと復帰すべきコンテクストが情報として渡される。

ユーザプロセスのスタックの変化:

                  |　　　　　　　|
		  +--------------+
		　|シグナルハンド|
|　　　　　　　|　|ラのフレーム　|　|　　　　　　　|
+--------------+　+--------------+　+--------------+
|トランポリン　|　|トランポリン　|　|トランポリン　|  
|用のフレーム　|　|用のフレーム　|　|用のフレーム　|　|　　　　　　　|
+--------------+　+--------------+　+--------------+　+--------------+
|割込み直前の　|　|割込み直前の　|　|割込み直前の　|　|割込み直前の　|
|ユーザスタック|　|ユーザスタック|　|ユーザスタック|　|ユーザスタック|
|　　　　　　　|→|　　　　　　　|→|　　　　　　　|→|　　　　　　　|

ユーザプロセス     シグナルハンドラ シグナルハンドラ  コンテクスト復元
再開		   呼び出し         終了
(トランポリン)

FreeBSD/amd64のシグナル・トランポリン。シグナルハンドラをcallした後、sigreturn(2)によりコンテクストを復元する。復元したコンテクストで実行が再開されるから、このシステムコールからは戻ってこない。 カーネルがプロセスを作成するときはいつもスタックの隅っこにこのコードをコピーしておく。

sigcode:
        call	*SIGF_HANDLER(%rsp)	/* call signal handler */
        lea	SIGF_UC(%rsp),%rdi	/* get ucontext_t */
        pushq	$0			/* junk to fake return addr. */
        movq	$SYS_sigreturn,%rax
        syscall				/* enter kernel with args */
0:      hlt				/* trap priviliged instruction */
        jmp	0b

SCM

SCMでは仮想マシンの状態を操作する部分(かなりの部分がそうである)をDEFER_INTSとALLOW_INTSで囲み、この間はフラグints_disabledが真になる。

C言語レベルのシグナルハンドラscmable_signalsではこのフラグが立っているとフラグSIG_deferredのシグナルに対応するビットを立て、変数deferred_procに関数process_signalsをセットする。

ALLOW_INTSではこのdeferred_procを検査し、セットされていれば実行してシグナルを処理する。

フラグints_disabledが偽の場合はシグナルハンドラが仮想マシンの状態を変更しても安全なので、設定されたコードを直ぐに実行できる。

ベルのシグナルハンドラにはもう一つerr_signalがある。これは呼ばれると通常のScheme実行中のエラーと同様にしてエラーを発生させる。longjmp()が呼ばれ、トップレベルに脱出する。

Gauche

ユーザ定義のシグナルハンドラがあると、Cレベルのシグナルハンドラとしてsig_handle()が登録される。この関数は仮想マシンにシグナルを記録し、遅延された処理が存在することを示すフラグを立てる。

Gaucheは仮想マシンループの先頭で毎回このフラグをチェックし、フラグが立っていれば遅延された処理を行うprocess_queued_requests()を呼ぶ。この中で呼ばれるScm_SigCheck()が、シグナルを順に調べて発生していれば対応するコードを実行する。

Gaucheではシステムコールを呼ぶ関数を実行した後にもScm_SigCheck()を呼ぶ。前述の通り、システムコールから戻るときにシグナルが記録されていれば、これによって素早くそれを処理することが期待できる。また、scm_sigsuspend()でシグナル待ちに入る前にもScm_SigCheck()を呼んで、発生済シグナルを片付けている。

Ruby

Rubyでも基本的には同じであり、シグナルはフラグを立てるだけで遅延させる。

C言語レベルのシグナルハンドラは関数sighandler()である。これはシグナル処理の遅延を示すフラグrb_trap_pendingと、どのシグナルかを示すtrap_pending_list[sig]をセットする。

Rubyではインタプリタの各所でCHECK_INTSを実行していて、このマクロがフラグを調べて遅延されたシグナル処理を行う。

Rubyレベルでも処理をインターリーブさせると不都合な場合にはrb_prohibit_interruptを真にしてこれを禁止することができる。このフラグの操作はDEFER_INTS, ALLOW_INTS, ENABLE_INTSマクロが行う。

またRubyでは、Rubyレベルのハンドラがなく、ブロックしていたシステムコール中にシグナルが発生した場合は、シグナルハンドラの中で直ちに処理する(いくつかのシグナルではRubyレベルのエラーを投げる。それ以外のシグナルでは何もしない)。

このためにRubyインタプリタの状態を安全にした上でTRAP_BEG, TRAP_ENDというマクロでシステムコールを囲んでいる。これらのマクロがフラグrb_trap_immediateを操作し、sighandlerはそれを参照する。

TRAP_ENDはCHECK_INTSを実行するため、Gaucheの場合と同様、システムコール中に発生したシグナルがあればシステムコールから戻ると遅延した処理が素早く行われる。

尚、Rubyでは自前でユーザレベルスレッドの切り替えを行っていて、シグナルを処理するのはその中のメインスレッドと決めている。このため、エラーを投げる際やシグナルハンドラのコードを実行する際にコンテクストの切り替えが行われる。RubyのスレッドについてはRubyソースコード完全解説 第19章 スレッドに詳しい。

シグナルを考慮から除外できるか

それでは、シグナルハンドラをユーザ言語で書くことをサポートしない場合はシグナルの存在を考慮しなくても済むだろうか。残念ながらそうとも言い切れない。

他のソフトウェアへの組込みなど、インタプリタに無関係にプログラムの別の場所でシグナルハンドラが設定され、そのハンドラがlongjmpするのであれば、やはりインタプリタの状態が一貫性を崩しているタイミングで割込まれると危険である。

そのような場合はシグナルハンドラに手を加えて安全な状態になるまで処理を遅延するか、またはインタプリタの状態を操作するの前にシグナルをマスクすることが必要となる。

21st Century Compilersの一部(?)をオンラインで読む

2006年10月3日追記: いささか旧聞だが、先月頃に Compilers: Principles, Techniques, and Tools, 2nd Edition としてようやく出版され、入手できるようになった。以前と違った美しいイラストの表紙にちなんで、パープル・ドラゴン・ブックと呼ばれる(1986年出版の以前の版はレッド・ドラゴン・ブックと呼ばれた)。大著にも拘らずアマゾンで洋書ランキングで現在881位、さすがに待っていた人は多いようだ。

12月6日追記: Compilers 1/e plus Selected Online Chapters from 2/eが日本のamazonでも掲載され注文可能になったようだ。しかしお高い。

12月2日追記: 21st Century Compilersが日米amazonから消えてしまった模様である(ペーパーバックの方はまだ生きている)。出版を諦めた筈はあるまいから、"1/e plus online chapters" を出してから改めて予定に載せるつもりなのかも知れない。

「コンパイラ」(通称ドラゴンブック)の新版と楽しみにしているのに出版の遅れ続けている21st Century Compilers (ペーパーバックもあるようだ。少し安い) だが、それとは別にCompilers 1/e plus Selected Online Chapters from Compilers 2/eという出版予定がいつのまにか立っていた。どうもこの第2版というのが21st Century Compilersを指すように思われる。

このonline chaptersは既にプレビュー扱いで公開されていて、http://www.aw.com/dragonbookから辿ることができる。断り書きによれば2006年1月1日までは自由に見ることができ、以後は登録が必要となるとのことで、おそらく上記の「新しい初版」の購入が必要になるのだろう。

表示にはFlashが使われ、紙面と同様の体裁で一ページごとに表示される。Flashのバージョン6ではだめだったので、7か8以上が必要と思われる。文字は綺麗にアンチエイリアシングされるので見易いが、検索や栞といった機能はなく使い勝手はAcrobatに劣る。本公開でも同じ仕様になるのか、より使い易いインタフェースになるのかはわからないが、本公開も同じだとすると $105.20 は少々高すぎるように思う(しかも21st Century Compilersの予価よりも高価である)。 ただ、書籍の方も初版と同じ筈が何故か200ページほど増えているのでそちらの理由も多少気になる。

オンラインになるのは第5章から第11章で、予定の全12章中重要な部分はほとんど読めてしまうことになる。実際、ざっと見たところでは9章と10章は尻切れとんぼのようにも思えるものの、ほぼ全てのページを見ることができた。しかも気前のよいことに、プレビュー段階の現在でも印刷までできる。

穿った見方をすると、遅れに遅れた上に12章を書くにはまだ時間がかかりそうだから、おまけのような12章は措いてもとりあえず世に出すためにこのような体裁をとったとも考えられる。著者の先生方には頑張って仕上げて欲しいが、こういったサービスは嬉しい。

年が明けてしまうと無条件には読めなくなりそうだから、正月休みの暇潰しにしたい向きには今のうちに一手間かけた方がよいだろう。

Tutorial on Good Lisp Programming Style

Lambda the Ultimateより。 Peter NorvigとKent Pitmanによるスライド。

Lispのプログラミングスタイルとして出色であるが、そればかりでない。 名前の付け方、コメントの書き方、コードの書き方などにおける「なぜそうするのか」というwhy、つまり原理原則に重点が置かれており、Lispに限らず示唆に富む。

具体的なコーディングの話では、Lispの構文・機能面の話もあるもののえ主眼は4つの抽象化(Data Abstraction, Functional Abstraction, Control Abstraction, Syntactic Abstraction)によるdecompositionに置かれている。 具体的な悪いコードとよいコードの対比を理由つきで示して説明されていてわかりやすい。

マクロによるSyntax Abstractionはもちろん、 最近関数型言語を学んでようやく知るようになったControl Abstractionも CやC++といった手続き型でしか書けない言語の知識のみでは気付かないことで このようなスライドが1993年に書かれていたということ、それを生んだLispの力に驚く。

116ページの大作だが、スライドなのでpsnup -4して両面印刷すると15枚で読み易く収まる(元がレターサイズである点に注意)。LtUにはPDF版へのリンクもある。

グラフが簡単に描ける―Graphvizの使い方

Graphvizはグラフを視覚化して様々なフォーマットに出力してくれるツールである。 テキストファイルにノードとエッジの関係を書いておけば、見やすいように自動でノードを配置してエッジを描いてくれる。出力形式もPostScript、SVG、PNGなど各種ある。GUIで図形を置きながら位置を揃えたりすることに気を遣うよりはずっと楽である。

本稿はそのGraphvizに与えるグラフの書き方(dot形式と呼ぶ)を簡単に説明する。 例としてconfig(8)のときに作成した図を用いる。

1. ノード間の関係を記述する

まず、グラフを構成するトポロジー、つまりどのようなノードとエッジがあるかだけを集中して書いてしまう。これだけで一応グラフは描けるので、最低限のレベルはクリアである。

グラフは、種類を示すキーワード(有向グラフ(digraph)または無向グラフ(graph))に続けて { ... } で囲んで記述する。

ノードにはラベルとして表示させたい名前をそのまま書けばよい。但しノードの名前に空白や記号などを含む場合は、"files.i386"のようにクォーテーションで囲む。

ノードとノードの間をエッジで結ぶにはNodeA -> NodeBのように書く。NodeA -> NodeB -> NodeCのようにいくつも繋げて書いてもよい。同じノードから複数のノードにそれぞれエッジを結ぶ場合、a->b; a->c; a-> d;と書く代わりにa -> { b c d }のようにひとまとめにできる。

なお、無向グラフでは->の代わりに--を使う。

digraph {
	MYKERNEL -> yyparse -> {fntab dtab opt mkopt};
	{files "files.i386" fntab} -> read_files -> ftab;
	{"Makefile.i386" mkopt ftab} -> makefile -> Makefile;
	{options "options.i386"} -> otab;
	{opt otab} -> f_options -> "opt_*.h";
	MYKERNEL -> configfile -> "config.c";
	"MYKERNEL.hints" -> makefile -> "hints.c";
	"MYKERNEL.env" -> makefile -> "env.c";
	{dtab ftab} -> headers -> "*.h";

	f_options [ label="options" ];
}

ノードのlabel属性を指定すると、ノードの名前と違う文字列を表示させることができる。複数の異なるノードに同じラベルをつけるには、ノードの名前は別々にしておいて、label属性に同じラベル文字列を指定すればよい。ノードに属性を与えるにはノードに続けて[ 属性=値 ]と書く。例ではf_optionsというノードにoptionsというラベルを与えている。optionsというノードは別にあるが、それとこれとは別個に表示される。

本例では使用していないが、エッジにもラベルを表示させることができる。 ノードの場合と同様に、エッジのlabel属性を指定すればよい。エッジの属性はNodeA -> NodeB [属性=値 ]のように記述する。

dot形式のファイルを元にして実際にグラフを描画させるにはdotコマンドを使い、オプションで出力形式や出力ファイル名を指定する。

% dot -Tpng -o config.png config.dot

2. ノードのスタイルを指定する

既にグラフは出来た。ここからはグラフを見易くするための装飾のみである。

まずは、ノードの種類ごとに形を変えてみる。例の図においてノードが表すものにはファイル、変数、関数がある。このうちファイルを四角、変数は楕円、関数は平行四辺形にしよう。

ノードの形はshape属性で指定する。

ノード一つ一つに属性を指定してもいいが、面倒だ。ノードのデフォルト属性はnode [ 属性=値 ]という文で変更できる。この文はそれ以後に新しく出現したノードにのみ効果がある。そこで、デフォルト属性を変えながら種類ごとにノードをまとめて宣言するのがよい。

digraph config {
	// files
	node [shape = box]
	MYKERNEL
	"MYKERNEL.env" "MYKERNEL.hints"
	files "files.i386" "Makefile.i386" options "options.i386"
	Makefile "opt_*.h" "hints.c" "env.c" "config.c" "*.h"

	// variables
	node [shape = ellipse]
	fntab dtab opt mkopt otab ftab

	// functions
	node [shape = parallelogram]
	yyparse
	f_options [ label="options" ]
	makefile headers configfile read_files

	// 以下は既に作成したエッジの記述 (省略)
	...
}

3. グラフの展開方向を指定し、ノードの位置を揃える

わかりやすくなったが、まだ今一つ、直観的ではない。特にyyparseの生成する4つの変数がばらばらになってしまっているのが気にくわない。そこでグラフを左から右に流れるようにし、更にノードの位置を揃えよう。特にyyparseの生成する4つの変数はどれも同じレベルに表示させたい。ついでに入力ファイル、出力ファイルの位置をそれぞれ揃える。

グラフの方向にはグラフのrankdir属性を指定する。グラフの属性は、グラフ内の適当なところに属性 = 値と書けばよい。

ノードの位置を揃えるには、{ ... }でノードをグループ化し、その括弧の中にrank=sameと記述する。

digraph {
	rankdir = LR;

	// files
	node [shape = box]
	{
		rank=same
		MYKERNEL "MYKERNEL.env" "MYKERNEL.hints"
		files "files.i386" "Makefile.i386" options "options.i386"
	}
	{
		rank=same
		Makefile "opt_*.h" "hints.c" "env.c" "config.c" "*.h"
	}
	
	// variables
	node [shape = ellipse]
	{
		rank=same
		fntab dtab opt mkopt
	}
	otab ftab

	// 以下略
}

これで概ね出来上がりである。説明しなかった属性のリストなど詳細はdot(3)のマニュアル等を参照されたい。

4. 表示の工夫のためにグラフに手を加える

更に一工夫、入力ファイルをユーザが記述するものとそうでないものに分けてみた。しかし具合の悪いことに、後者のファイルがyyparseの生成する4つの変数の間に割り込んで表示されるようになってしまった。

そこでダミーの見えないエッジを使い両者のランクを強引に分けることとした。エッジはstyle=invisという属性を指定すると描画されない。エッジの属性はNodeA -> NodeB [属性=値 ]のように記述する。

digraph {
	...
	// files
	node [shape = box]
	{
		rank=same
		MYKERNEL "MYKERNEL.env" "MYKERNEL.hints"
	}
	{
		rank=same
		files "files.i386" "Makefile.i386" options "options.i386"
	}
	{
		rank=same
		Makefile "opt_*.h" "hints.c" "env.c" "config.c" "*.h"
	}

	...

	// functions
	node [shape = parallelogram]
	yyparse read_files
	{
		rank=same;
		makefile headers configfile f_options [ label="options" ]
	}

	...

	// 表示位置を違えるためのダミーのエッジ
	fntab -> files [ style=invis ]
}

ついでに、出力を担当する4つの関数の位置も揃えた。

config(8)

FreeBSD 5.4のconfig(8)を読んだ。config(8)は組込むドライバやオプション等を記述したカーネル設定ファイルを読み、それに従ってコンパイルに必要なファイルを生成するプログラムである。

config(8)を実行しカーネルをコンパイルする手順は次の例のようになる。現在のFreeBSDではmake buildkernelが推奨手順であるが、その中でもこの手順は行われている。

# cd /sys/i386/conf
# config MYKERNEL
Kernel build directory is ../compile/MYKERNEL
Don't forget to do a ``make depend''
# cd ../compile/MYKERNEL
# make depend
# make

生成するファイルの雛形(Makefile.arch)や、生成・コンパイルするファイルの情報(files, files.arch、指定可能なオプションのリスト(options, options.arch)等は/sys/confにおかれている。config(8)はファイル生成時にこれらの情報を参照する。

ソースファイルの構成

config(8)は小さなプログラムで、4つの.cファイル、2つのヘッダファイル、加えてlang.lとconfig.yから成る。

config(8)の作者はカーネル設定ファイルのためのわかりやすい文法を設計した。lang.lとconfig.yはそのための字句解析器・構文解析器のソースコードである。このような問題に特化した簡明な文法の採用は一般に推奨される戦略である。とりわけlexやyaccによる解析器の記述は確立された手法で、理解や保守も易しい。FreeBSDのソースツリー中の*.lファイルの数は39、*.yは62を数える。

config.hはこのプログラムで使われるデータ構造とグローバル変数を定義している。configvers.hはバージョンを定義しており、config(8)プログラムと処理すファイルのバージョンが整合するか確認するために用いられる。

4つのCソースファイルのうち、main.cは全体のドライバとなるメイン関数及び他の3つから共通に使われる関数の定義であり、他のmkmakefile.c, mkheaders.c, mkoptions.cはそれぞれ名前の示すファイルを生成するモジュールである。

処理の流れ

mainではまずグローバル変数(特にdtab, fntab, cputype, ftab)を初期化した後、解析器(yyparse)を呼びカーネル設定ファイルを読む。その後ファイルを生成する処理options, makefile, headers, configfileを順に行う。

カーネル設定ファイルの読み込み

スキャナが入力ストリームからトークンを単位として切り出し、それを受けてパーザが文法に従って処理を行う。

スキャナはdevice, optionsなどのキーワードに対応するトークン(DEVICE, OPTIONSなど)、英数字から成る名前(ID)、数(NUMBER)を返す。文字列から数値を得るにはsscanfが使われる。

シンプルではあるが、書き易さの為の工夫も入れられている。device foo2という行をDEVICE ID("foo") NUMBER(2)と認識するための初期状態の切り替えがそれである(IDは英数字から成る為に本来なら"foo2"という名前として切り出される。その場合、device foo 0のような不自然に見えるわかち書きが必要となる)。

反面、おおらかな部分もある。例えば文字列。manにはA `"' character may be inserted into a quoted string by using the sequence `\"'.とあるが、そんな実装はされていない。"abc"はabcに、\"abc=def\"は"abc=def"になる。しかしそれだけである。プログラミング言語ではない故、誰も困っていなければ厳密さは求められないのだろう。

パーサではfiles, options, deviceという命令に応じ、fntab, opt, mkopt, dtabという4つのリストに項目を追加していく(関数newfile, newopt, newdev)。include命令に対してはflex(GNUによるlexの実装)の独自機能で別ファイルのインクルードを実現している。

変数名	命令	説明
fntab	files	ソースファイルの情報をリストしたファイルの追加指定。
dtab	device	デバイスのリスト。名前と数を保持。
opt	options, device	オプション(Cのマクロとして出力される)のリスト。
mkopt	makeoptions, config	Makefileに変数として出力されるオプションのリスト。

余談だが行末だけでなくセミコロンでも文は終端する。また既出のデバイスやオプションなどを取り消すnodevice, nooptionsといった命令がある。私は今回ソースコードを読んで初めて知った。

出力

ファイルの出力はoptions, makefile, headers, configfileの4つの関数で行われる。

optionsはoptions命令で指定されたオプションを定義するヘッダファイルopt_*.hを出力する。

makefileは、files, files.archなどを読み込んだ後、Makefile, hints.c, env.cを生成する。ここで読み込んだ情報は次のheadersでも使われる。

headersではfilesでcountというフラグの立てられたものについて、"デバイス名.h"というヘッダファイルを生成する。かつてはコンパイル時にカーネルに組込むデバイスには#define NDEV 1のようにデバイス数を値とするマクロを定義し、デバイスのソースファイルの方でコードを#ifdef NDEV ... #endif で囲むという手法をとっていた。その名残りである。

configfileは、カーネル設定ファイルの内容を文字列としてカーネルに持たせるためのファイルconfig.cを生成する。

これらの中でも/sys/confに置かれるfilesなどのファイルを読み込んでいるのだが、面白いことにどれも手書きで済ませている。微妙な力の抜き加減である。

一方、ヘッダファイルを生成するときはわざわざ既に書かれている内容を読み込み、反映させようとするものでファイルの内容が変化するか調べるということを繰り返している。makeのときの再コンパイルを減らすためであろう。ご苦労なことである。

データと処理の流れを表すダイアグラム

楕円はデータ。平行四辺形は処理。矩形はファイル。

style(9) — FreeBSD kernel source file style guide

FreeBSDユーザであれば man 9 style とすると読むことができる。またman -t 9 style | lprとすればPostScriptで綺麗に整形したものが印刷される。A4で9ページと非常に短い。webではHypertext Man Pagesで参照できる。

kernelと銘打ってあるが、その内容は一般のソースコードを対象にしていてユーザコマンドのコマンドラインの処理やエラー処理に関する記述もある。 どのような事柄を指定しているかというと、大略以下の通り。

続きを読む