Code Reading 第9章: Architecture

ソフトウェアの設計の視点から、構成方法のタイプ、切り口について解説。 加えて、モジュールやクラスなどパッケージングの様々なレベルを説明。

9.1 System Structures

システムをどのようにサブシステムで構成するかという方法の紹介。

Centralized Repository and Distributed Approaches (9.1.1)

クライアント・サーバ。黒板システム(key/valueペアでレポジトリにアクセス。プログラムをデータの流れ通りに構成しなくても部分同士が通信できる。例: apache)。またそれを分散システムで実現するためのRPC、CORBA、RMIなども少し紹介。

Data-Flow Architectures (9.1.2)

データの変換の連続として処理をモデル化。要するにUNIXのパイプで流す処理。data-flow diagramを描いてみると役に立つ。例: makewhatis。

Object-Oriented Structures (9.1.3)

UMLによる図を描くのはシステムの構造を理解するのに有益。コードを読んで図を生成するツールもある(例: ArgoUML)。

Layered Architecture (9.1.4)

例: ファイルシステム(fwriteからデバイスの書き込みまで。Half-Sync/Half-Async)

Hierarchies (9.1.5)

同じ対象でも視点を変えて何通りもの階層構造がある

Slicing (9.1.6)

分析テクニック。コードから、ある点数の特定箇所での値への影響に着目して関係するコードを抜き出すこと。

9.2 Control models

Event-Driven Systems (9.1.1)

例: GUI。多数の発生源からのイベントを統合。

System Manager (9.2.2)

要素の一つがマネージャとして他の要素の実行を制御する。

State Transition (9.2.3)

有限状態機械。

9.3 Element Packaging

今度はコードを読む際に必要となるボトムアップな視点からの分析に役立つ視点。 コードを読む際には、大きなソフトウェアがどのような方法で各単位に分割されるかを知ることが重要。

Modules (9.3.1)

例: nvi(ファイルとモジュールが1:1), BSD window(複数ファイル/モジュール)、NetBSDカーネル(ディレクトリ/モジュール)

Namespaces (9.3.2)

C++のnamespaceやJavaのpackage。

Objects (9.3.3)

オブジェクト指向の説明。長いが省略できる。C++等の言語機能のみに頼らない(頼れない)実現方法の例も。

Generic Implementations (9.3.4)

任意の型の要素に使えるデータ構造やアルゴリズム。C/C++のマクロによる表現やC++のテンプレート。

Abstract Data Types (9.3.5)

要するに抽象データ型。

Libraries (9.3.6)

効用: Code Reuse, Encapsulation, Structure(モジュールごとにライブラリにする), Optimization of the Build Process, Reduction of Code Size, Dynamic Linking(Windowsではリソースの切り替えにも使われる)。

Processes and Filters (9.3.7)

UNIXのプロセス。例: apache、gccのコンパイラドライバ。UNIXのフィルタ。

Components (9.3.8)

ActiveX, JavaBeans, CORBA。

Data Repositories (9.3.9)

9.4 Architecture Reuse

多くのシステムは確立されたアーキテクチャを利用。基本的な事柄すぎてわざわざ文書化されていないことも多い。

Frameworks (9.4.1)

例: MFC、Java AWT、ACE。

フレームワーク自体を学習することが理解の近道。それにはほとんど何もしない一番簡単なサンプルを調べたり変更したりするのがよい。

Code Wizards (9.4.2)

ウィザードを使って作られたものは作り手が基礎となるフレームワークについて部分的な理解しかしてない場合が往々にしてある。

Design Patterns (9.4.3)

例: Singleton パターン。

Domain-specific architecture (9.4.4)

分野によっては構成法が確立されている。例: ファイルの字句解析・構文解析。

練習問題ピックアップ

exercise 9.5: GNU tarのデータフローダイアグラムを描け。(着目点: リモートバックアップ、圧縮、固定長ブロックI/O)

exercise 9.6: UMLのモデリングツールを使ってオブジェクト指向アプリを解析せよ。

exercise 9.24: 各種デザインパターンのACEフレームワークで使われているコードを特定しコードに即してパターンの特長を説明せよ。

exercise 9.25: gccのソースコードの各部を典型的なコンパイラアーキテクチャに対応させよ。

グラフが簡単に描ける―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のときの再コンパイルを減らすためであろう。ご苦労なことである。

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

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

Code Reading 第8章: Documentation

この章は8.2以外は短い。

8.1 Documentation Types

プロジェクトに関する文書をおおまかに5種類に分類。

the system specification document

システムの目的、機能要求、管理・技術的制約など。
→コードの動作する環境についての知識が得られる

the software requirements specification:

ユーザ要求の高レベルな記述、システム全体のアーキテクチャ、処理や外部インタフェース等の要求の詳細。
→コードを読んだり評価するベンチマークとなる

the design specification

システムのアーキテクチャ、モジュール間のインタフェースやデータやコードの構造など。
→コードの構造のロードマップ、特定のコードを読むときのガイドに。

system's test specification

テスト計画、テスト手続き、テスト結果等。
→コードのdry-run(机上での検討)をデータつきで提供してくれる

user documentation

機能の説明、インストール手順、その他もろもろ
→対象がどういうシステムなのか知らねば始まらない。

8.2 Reading Documentation

ソースコードを読む参考情報を文書から読み取る様々な例。

• コードから動作を読み取るよりも文書から情報を得た方が理解が早い例: catの改行コードの処理のループ(manの-sオプションの説明を読む方が早い)。
• 文書のセクションとソースファイルとがかなり対応(例: sendmail)。
• 複雑なアルゴリズムは難解なコードよりも文章による説明の方がわかりやすいことも。 文書の情報により、識別子の名前からそれが意味するものを把握しやすくなる。l
• デザイナーの思考や検討された対案などを読めることもある(例: Plan 9)。
• システムの内部APIの説明文書(hsqldb/dev-docs/hsqldb/index.html, perl/perlguts.pod, FreeBSDやNetBSDのmbuf(9)をはじめとするmanのセクション9)。
• テストケースや利用例(tcpdump(8))。
• 実装上の問題、caveats(機能が働かない可能性の警告)、バグ。
• OSやコンパイラのバグなど環境上の理由による問題とその対処→ソース上のコメントがほとんど。

8.3 Documentation Problem

文書は常に正しい情報を与えてくれるとは限らない。

• 様々な理由により、実装された機能が文書化を避けられることもある
• 文書が、システムは「どのように実装されているか」でなく「どのように実装されるべきか」を述べている可能性
• コードの進化にドキュメントが追随しなかった場合

8.4 Additional Documentation Sources

ほかにもnon-traditionalな幅広い情報が得られる。comments, standards, publications, test cases, mailing lists, newsgroups, revesion logs, issue-tracking databases, marketing material, and the source code itself.

コメントは実行されるわけじゃないので正しいとは限らない。 標準を実装しているならその標準の文書。FAQなど。

オープンソースならでは: 読んでいるコードに特徴的な識別子をいくつか選んでメーリングリストなどのアーカイブを検索してみる。作者に直接問い合わせてみる(濫用禁止、対価をコミュニティへ還元せよ、作者はボランティアであることを忘れるな)

8.5 Common Open-Source Documentation Formats

オープンソースで用いられる文書形式の紹介: man (mdoc), Texinfo, DocBook, javadoc, Doxygen。

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

続きを読む

Code Reading 第7章

この章は非常に短い。coding standardの採用の必要性と、主なcoding standardsはどのような点について推奨基準を定めているかの説明。

7.1 ソースコードに含まれる一般的な文書ファイルのファイル名とその説明

README, INSTALL, TODOなど。

7.2 Indentation

特になし。

7.3 Formatting

不揃いなフォーマッティングはバグの元。
コメントのフォーマットでは、/*- で始まる場合はアスキーアートによる図解など再整形されたくない内容を示す。Javalでは、/**で始まるものはjavadocにより処理される。
switch文でコードを書いた意図を表明する/* FALL THROUGH */と/* NOTREACHED */。

コメント中のXXX, FIXME, TODOの用法:

• XXX: その部分のコードが正しくないが多くの場合動いてしまう
• FIXME: コードが間違っていて修正を要する
• TODO: 将来強化すべき箇所の表示

7.4 Naming Conventions

英文字の大小やアンダースコアによるBSD, Java, Windowsの命名規則を紹介。 名前を構成する規則や語彙などについての話はなかった。

7.5 Programming Practices

portabilityのためにコードの書き方をルール化。GNUは16bit環境を考えていないなど暗黙的な仮定があることに注意。
ユーザインタフェースやその処理方法も標準化。(コマンドライン引数の処理や、GUIアプリケーションのUIガイドライン)

7.6 Process Standards

多くのcoding guidelineはコードだけでなく文書やビルドプロセスにも標準化の範囲を広げている。(例: UNIXのman、GNUのtexinfo、BSDのソースツリーのMakefile)

主なcoding standards:

• Indian Hill C Style and Coding Standards
• GNU Coding standards
• FreeBSD kernel source file style guide (style(9))
• Java Code Conventions

Code Reading 第6章

この章では、大規模なソフトウェアの構成やテクニックを、作る側の視点から解説している。

6.1 大規模プロジェクトで使われそうな設計や実装のテクニックのあらまし

「オプジェクト指向の利用」のようなコードレベルのことも挙げられているが、特に次の点が目を引いた。

• nontrivial architecture
• libraries, components, and processes
• domain-specific and custom languages and tools
• aggressive use of preprocessing

6.2 ソースコードのディレクトリ構造を見てプロジェクトの構成を把握する

構成方針を把握すれば、目的のソースコードを探し当てることは易しい。(例: FreeBSDのユーザランドを含む全ソースコード)
大規模プロジェクトでは、ソースコードには単に実行ファイルを構成することになる命令だけでなくずっと多くの情報が含まれている。

6.3 ビルドプロセスの概略

オブジェクトファイル(*.o)→ライブラリ・コンポーネント→実行ファイル、というファイルが構成される関係の説明。
ビルドプロセスで使われるツールとして、makeの解説、antとjamの紹介。

6.4 configuration (ビルドの条件の変更や、ソースコードの修正など)

ビルド時: makefileの変数、antのbuild.propertiesファイルによる設定。GNU configureの紹介。
実行時: 設定ファイル、環境変数、Javaのプロパティ、Windowsのレジストリから情報を読み込んで動作に反映。

6.5 Revision control

RCSやCVSの使い方。cvs logの例とその見方。

6.6 Project-Specific tools

例としてUNIXのconfig(8)を挙げている。プロジェクト固有のツールは回帰テストの処理にも使われる(例: perl/t/TEST)。また、javadocやperlのpodのような言語固有のドキュメント生成ツールもこの類として紹介。

6.7 Testing

ソースコードを読むときには、作業の一部としてまずテストコードやテストケースを調査して、それらを残りのコードを理解する役に立てるべき、との由。
ソースコードを読む際にはテストケースは機能仕様を部分的に代替したものといえる。

またデバッグのために使われるコーディングについても解説。

• #ifdef DEBUG 〜 #endif
• ロギング機能 (syslog, ReportEvent)、ロギングのデバッグレベル
• assert (3通りの用法: コードの理解が正しいことのチェック、引数のチェック、戻り値の検証)

テストとして、JavaではJUnitによるユニットテスト、Cでは#ifdef DEBUG 〜 #endifで囲まれた簡単なmain()関数によるテストプログラムを紹介。

面白そうな練習問題

exercise 6.19: カーネルのconfigプログラムを読んでシステムのそれが設定できる側面を文書化せよ。

exercise 6.22: Perlの自動テストプロセッサTESTとテストケースを調査せよ。テストケースはどのように書き、回帰テスト中にどのように処理されるか説明せよ。

OCaml超入門

以前から興味のあったocamlを学ぶため、手始めにOCaml超入門を読んでみた。
ML系は関数型言語ながら、手続き型言語のような順序評価や値を変更できる変数がある。
モナドと付き合わなければならなさそうなHaskellよりはとっつきやすい。
CやC++で書かれたライブラリを利用する拡張モジュールも書きやすいのではないかと予想する。

CamlでないMLは「初級ML講座」を読んでかじったことがあったのだが、そのときの記憶はすっかり忘れていた。
予約語や文法はCamlとMLでは大筋では似ているのだが、異なる部分も随分あるようだ。
当面はより詳しい解説に当たるとともに、なるべく早く拡張モジュールを一つ書いてみたい。