ブログっ...!

最近はミソフォニアのことばかり書いています。もうミソフォニアブログです。

まなび1

トライ木の話になった。
トライ木って、人工知能の辞書とかの恐ろしく大きいデータのためのデータ構造だと思っていたのだが。

私はほぼ毎日と言っていい程、このトライ木にお世話になっていたらしい。

以下はMakefileの一例。
all : foo.exe
foo.exe : foo.o
gcc foo.o -o foo
foo.o : foo.c
gcc -c foo.c -o foo.o

MakefileのこのA : Bという記法は、Aの生成にはBが必要という意味。
make Aとやれば、Aが生成される。
$ make
は make all の略。

この各々のファイル (func.o, func.cなど) は
C言語がコンパイルされて実行可能になるまでの流れ - にょきにょきブログ
で丁寧に説明されている。

foo.c から foo.exeに至るまで、

foo.c --cpp--> foo.i[-E] --cc1--> foo.s[-S] --as--> foo.o[-c] --ld--> foo.exe [-なし]

こんな過程がある。
・cpp : Cプリプロセッサ
・cc1 : Cコンパイラ
・as : アセンブラ

(A)「 --cpp--> --cc--> --as--> 」部が gcc がやっているもの。 gccのことをコンパイラだと思っていた今までだったが、実は「コンパイラドライバ」 コマンドを実行していろいろなツールを動かす役目。 clangは (A) 部をまとめて行うため、コンパイラと呼んでよいらしい。

foo.c
int main() { puts("hello"); }

foo.sを生成すると、アセンブリ語がこんな感じで並んでいるイメージ 左はアドレスだと思って

foo.s

a ラベル 命令
0 main: push hoge
5 call _puts
10 ret
12 hoge: .string "hello\0"

foo.sからfoo.o間はアセンブラの仕事。 上記の例だと、hogeが示すアドレスは一体何かを具体化する。hoge は 12 に置換されるイメージ。 ファイル内で閉じてアドレスの解決を行うために、並列作業が可能である。(.oを作るまではマップ並列)。 たとえfoo.c, bar.c の中に依存関係があっても、ファイル内で閉じていた解決なので。 この時点ではputsのアドレスはまだ解決されない。 プロトタイプ宣言はされているが、実体は定義されていない。 (他のファイルでputsが定義されている場合はリンカのお仕事、この場合はlibcの関数なので後のローダのお仕事) これ以降はローダのお仕事。

リンカは規格の決まったヘッダーを用意する。
ELF, Mach-O (object file format) $ file file.o で見るとよい。
-------
|header|
-------
| text |
-------
| .data |
-------
| .rel |
-------
まだ解決されないアドレスを rel に載せ、relはtextを参照する形になっている。

一方、libcも同じ過程を経て、リンカに渡る。 リンカは puts は アドレスA, printf は アドレスB, ... みたいな巨大な参照関係を示したトライ木を作成し(Mach-Oの場合. ELFはハッシュ)、それをローダに引き渡す。 libc.so/ libc.dylib

ローダーは「実行時になるまでわからないメモリのどこか」にプログラムが配置された後、 これによって決定された実際の(?)アドレスを各ファイルに教えて、参照関係を再びただす。

実行時には各ファイルのアドレスが依存するために、ローダーの作業を並列化しても高速化は望めないらしい。 リンカもリデュース。