Binary2.0勉強会 8
とか第0回で言ってたので、そっち方面に進みます。
Cのソースコードが実行形式になるまでの道は長く険しいのだ。
全部を全部 gcc がやっているということはなくって、実は gcc は内部で別のプログラムを呼んでて、gcc の仕事はそれらのコマンドをどうこうする部分のようです。
おもむろに gcc --help すると、
-v コンパイラによって起動されるプログラムを表示
とかあるので試してみましょう。
niha@hoge:~/src/c$ gcc -v bin05.c Using built-in specs. Target: i486-linux-gnu コンフィグオプション: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr （略） スレッドモデル: posix gcc バージョン 4.2.3 (Ubuntu 4.2.3-2ubuntu7) /usr/lib/gcc/i486-linux-gnu/4.2.3/cc1 -quiet -v bin05.c （略） 存在しないディレクトリ "/usr/local/include/i486-linux-gnu" を無視します 存在しないディレクトリ "/usr/lib/gcc/i486-linux-gnu/4.2.3/../../../../i486-linux-gnu/include" を無視します 存在しないディレクトリ "/usr/include/i486-linux-gnu" を無視します #include "..." の探索はここから始まります: #include <...> の探索はここから始まります: /usr/local/include /usr/lib/gcc/i486-linux-gnu/4.2.3/include /usr/include 探索リストの終わり GNU C version 4.2.3 (Ubuntu 4.2.3-2ubuntu7) (i486-linux-gnu) compiled by GNU C version 4.2.3 (Ubuntu 4.2.3-2ubuntu7). GGC heuristics: --param ggc-min-expand=64 --param ggc-min-heapsize=64428 Compiler executable checksum: cd267a1ce4b47763f08e41c54a4f8f5c as --traditional-format -V -Qy -o /tmp/ccIevCFL.o /tmp/ccvXJifO.s GNU assembler version 2.18.0 (i486-linux-gnu) using BFD version (GNU Binutils for Ubuntu) 2.18.0.20080103 /usr/lib/gcc/i486-linux-gnu/4.2.3/collect2 --eh-frame-hdr -m elf_i386 --hash-style=both -dynamic-linker （略）
cc1 as collect2 の三つがわけわからんオプションいっぱいつけて呼ばれてるようです。
4つの工程があったはずなんですが三つしかないですね。これ以上続けると長さが半端になりそうなのでここで切って、次回は三つのプログラムの簡単な説明を。
Binary2.0勉強会 7
二週間も間があきました。びっくり！
夏バテです。より正確には熱くてバテてるというより冷房が寒くて凍えてます。
関数を呼び出した際のスタックの動きをおさらい。
呼んだ時。
帰る時。
でした。ということで main を見直して見ましょう。
int main(){
0: 8d 4c 24 04 lea 0x4(%esp),%ecx
4: 83 e4 f0 and $0xfffffff0,%esp
7: ff 71 fc pushl -0x4(%ecx)
a: 55 push %ebp
b: 89 e5 mov %esp,%ebp
d: 51 push %ecx
return 0;
e: b8 00 00 00 00 mov $0x0,%eax
}
13: 59 pop %ecx
14: 5d pop %ebp
15: 8d 61 fc lea -0x4(%ecx),%esp
18: c3 ret このうち、
a: 55 push %ebp b: 89 e5 mov %esp,%ebp 14: 5d pop %ebp
この三行が上にまとめた部分に相当するわけですが、何か他にも色々してますね。
まず、
4: 83 e4 f0 and $0xfffffff0,%esp
これは esp を 16byte でアラインメント整えてますね。
アラインメント整えると値が変わってしまうので、 main 関数抜ける時には esp を元の値に戻さないといけません。どうやら ecx を使って復元しているようなのですが…何かアドレスをわざわざ +4 してますね。なんでだろー。
と思ってたのですが、よくよく考えれば main も普通に引数取るじゃん引数じゃんということに気がついた。
00000000 <main>:
int main(int argc, char *argv[]){
0: 8d 4c 24 04 lea 0x4(%esp),%ecx
4: 83 e4 f0 and $0xfffffff0,%esp
7: ff 71 fc pushl -0x4(%ecx)
a: 55 push %ebp
b: 89 e5 mov %esp,%ebp
d: 51 push %ecx
return argc;
e: 8b 01 mov (%ecx),%eax
}
10: 59 pop %ecx
11: 5d pop %ebp
12: 8d 61 fc lea -0x4(%ecx),%esp
15: c3 ret なるほど ecx は普通に第一引数指すのに使っているようです。
ということは ecx は引数のアドレスを指しつつ、ついでにその値を esp の復元にも利用している、ような感じなのかな、と。
で、これそもそも push と pop の対応が余裕で取れてないですね。なんでやねん。 esp 復元してるんで esp がずれるといった問題はないんですが、一番最初の「pushl -0x4(%ecx)」の意味が全然ないような…本来なら最後の「lea -0x4(%ecx),%esp」は「pop %esp」とされるべきだと思うのですが、どうなんだろう。スタック触るよりレジスタ間で値渡した方が早いからとか？それなら push そもそもするなよ…これだけ結局分かりませんでした。誰か偉いひと教えてください。最適化オプションつけても消えないということは必要なんだとは思うのですが…
ということで随分とかかりましたが、 0 返すだけの main をようやくアセンブラレベルで理解できましたね！わからないところあるじゃんとか言わない！
次回からは配列とか構造体とかほげろうと思います。
そろそろICFPC2008について一言言っておくか
気づいたら寝落ちしてて submit できなかった！！！１１１
まあその時点で動く子がまっすぐ進んでぶつかりそうになったら避けるだけの子だったのでどうでもいいです。
大体ボクが何をしていたか書くと、始めはホームは引力、障害物は斥力をもつようにして、適当に動く方向を決めるとかしてたんですが、これが全く帰れない。一度ホームベースのちょっと左あたりでぐるぐるとかしててとても楽しい心持ちがした。しかし今思うとアレは戦略が悪いんじゃなくて、明らかにバグだ。
であまりにもクソだったので、普通にホームに向かって、障害物が着たら止まって避けて、またホームに向かって…というかなり慎重な子を書いた。とりあえずこれで始めのサンプルで帰れる子はできました。Endoさん…じゃなくて火星人対策は一切なかった。
その後さらに色々と考え直しました。想定されるマップのパターンとして、わけわからん迷路とかくると、さっきの愚直にゴールに向かう子ではどう考えても無理…
じゃあ経路探索的なアレをしてやるかーとなって、マップを 1m 単位で升目に区切って、よく知らないながらもA*？とか書いたんですが、100msとかで探索できるわけもなく、どうしようかなーとか思ってる間に気がついたら寝てました。起きたら昼の三時だった。12時間以上寝たてたことになる…
とりあえずA*がすごい遅いということはよく分かった。なんというか、自分の手で実装して試してっていう作業をしていないアルゴリズムとかは、計算量とか全然分かって無いので困りますね！その辺のなんというか地力がボクには全く足りていない気がする。
あと毎回思いますが規模大きくなった時にコーディングのスピード落ちすぎ。ゴルフばかりしているからですね！大体 Ruby だと300行とかその辺越えるくらいからうーん…って感じになる。多分あほ設計ではその辺から大変になるということなのだろう。
もうひとつ、これ書いてる時点で気がついたけれど Ruby だとボクの中ではオブジェクト思考とか超スルーされていて、ハッシュと配列ですべてを何とかしようとしてるらしいです。主にハッシュ。「$rover = {"x" => 0, "y" => 0, "d" => 0, "s" => 0}」みたいなことをしていて、とても愉快。
まあなんというか今回は問題文がちゃんと読めてたので、そこは良かったですね！
ということでまたばいにゃりにゃんにゃん勉強会に戻ります。
寄り道
http://twitter.com/natsutan/statuses/854451215
cdecl とかだと EBX は破壊できないので、普通は3つまでしか使えないんじゃないかなあと思います。規約違ったり RISC だったりするとそうでもないんですかねえ。 RISC よく知らないけど何かレジスタたくさんあるんですよね！
GNU 拡張使ってレジスタも使って引数渡すようにしてみました。
niha@hoge:~/src/c$ cat bin04.c
__attribute__((regparm(3))) int hoge(int a, int b, int c, int d){
return a+b+c+d;
}
niha@hoge:~/src/c$ gcc -c -g -O bin04.c
niha@hoge:~/src/c$ objdump -S bin04.o
bin04.o: file format elf32-i386
Disassembly of section .text:
00000000 <hoge>:
__attribute__((regparm(3))) int hoge(int a, int b, int c, int d){
0: 55 push %ebp
1: 89 e5 mov %esp,%ebp
3: 01 c2 add %eax,%edx
5: 01 ca add %ecx,%edx
7: 89 d0 mov %edx,%eax
9: 03 45 08 add 0x8(%ebp),%eax
return a+b+c+d;
}
c: 5d pop %ebp
d: c3 retというような。
Binary2.0勉強会 6
前回確認した関数の呼び出し回りを実際に逆アセして見てみましょう。
niha@hoge:~/src/c$ cat bin02.c
int hoge(int i){
int ret = i;
return ret;
}
niha@hoge:~/src/c$ gcc -c -g bin02.c
niha@hoge:~/src/c$ objdump -S bin02.o
bin02.o: file format elf32-i386
Disassembly of section .text:
00000000 <hoge>:
int hoge(int i){
0: 55 push %ebp
1: 89 e5 mov %esp,%ebp
3: 83 ec 10 sub $0x10,%esp
int ret = i;
6: 8b 45 08 mov 0x8(%ebp),%eax
9: 89 45 fc mov %eax,-0x4(%ebp)
return ret;
c: 8b 45 fc mov -0x4(%ebp),%eax
}
f: c9 leave
10: c3 ret
まずは、ベースポインタをスタックに退避させています。
その後、ベースポインタをスタックポインタの値に、スタックポインタは16引いて、16バイト分のスタックが確保されました。16バイトも使わないと思うんですが…なんででしょうね。
ここから関数内の処理。第一引数を EBP 経由でさしているのが「0x8(%ebp)」。ちなみに「0x4(%ebp)」には ret の戻り先が、「(%ebp)」には元のベースポインタが入ってます。
第一引数を EAX に、更に EAX をスタックに積んでいます。そして、返り値としてスタックに積まれた第一引数を EAX レジスタに。
えーと、無駄ですね。無駄です。許せない。
ふざけんな、ということで最適化オプションつけてコンパイルした結果。
0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 8b 45 08 mov 0x8(%ebp),%eax 6: 5d pop %ebp 7: c3 ret
素晴らしー。
あとは leave で EBP と ESP を復元して、 ret でぴょーんと飛んでおしまい。
関数呼ぶときは大体こんな感じで。
niha@hoge:~/src/c$ cat bin03.c
int func(int x, int y, int z);
void hoge(){
func(1, 2, 3);
}
niha@hoge:~/src/c$ gcc -c -g bin03.c
niha@hoge:~/src/c$ objdump -S bin03.o
bin03.o: file format elf32-i386
Disassembly of section .text:
00000000 <hoge>:
int func(int x, int y, int z);
void hoge(){
0: 55 push %ebp
1: 89 e5 mov %esp,%ebp
3: 83 ec 18 sub $0x18,%esp
func(1, 2, 3);
6: c7 44 24 08 03 00 00 movl $0x3,0x8(%esp)
d: 00
e: c7 44 24 04 02 00 00 movl $0x2,0x4(%esp)
15: 00
16: c7 04 24 01 00 00 00 movl $0x1,(%esp)
1d: e8 fc ff ff ff call 1e <hoge+0x1e>
}
22: c9 leave
23: c3 ret スタックにぺぺっと積んで call。おしまい！
Binary2.0勉強会 5
間があいた。
この辺から大分内容の信憑性が落ちるうえに説明がさらにいい加減になってくると思いますが、ちゃきちゃき参りましょう。
今回は、前回までみていたコードは一旦忘れて、アセンブラでの関数の扱いに関して簡単に触れます。
関数がどのように実装されるのかをまず確認しましょう。
各関数内の処理は、機械語の命令列としてメモリ上に適当な感じで配置されてます。関数を呼ぶには、プログラムカウンタ（実行される命令のあるアドレスです）を適当な感じで書き換えます。多分。ちなみにプログラムカウンタはレジスタの eip が保持していますが、まあ意識することはないと思います（これ lea とかで書き換えたりしたらジャンプするのかな？）。
書き換えられた先のアドレスに配置された命令を実行していって、関数の処理が終了したとしましょう。処理を終えれば、呼び出し元に帰らないといけません。ですが、帰るべきアドレスを知っていないとプログラムカウンタを書き換えられないので迷子になってしまいますね。何らかの形で呼び出し元から帰ってくるべきアドレスをもらわないといけません。他にも、引数や返り値、受け渡ししないといけない値は複数あります。しかしレジスタにそんな余裕はないし…どうなっているのか。
実は、関数を呼んだり、関数の呼び出し元に戻ったりする際に、レジスタやスタックをどういった状態にしておかないといけないというような決まりがあって、これを関数の呼び出し規約とかいいます。この約束を皆守っているので、迷子になったり値の受け渡しで困ったりしないですむわけですね。
呼び出し規約にも種類があるのですが、C と x86 の組み合わせの場合、基本的には cdecl というものが使われていると思いますメイビー。よく知りません。
適当に規約の内容をまとめると、
というような感じです。
さてこれで、値の受け渡しに関しては解決しました。後は適当にスタックに引数つんでジャンプして、帰る時も適当にジャンプするわけですが、帰るアドレスをどこに取っておくかという点がまだ残っています。
この辺はそもそも専用の命令が用意されていて、それが前回にもでてきた ret と call です。
call は、戻るべきアドレスをスタックに積み、プログラムカウンタをオペランドで示されたアドレスに書き換えます。これでぴょーんと処理が飛びます。
ret は、プログラムカウンタをスタックトップに積まれているアドレスに書き換えます。ぴょーんと帰ってきます。
例えば下のような関数があったとすると、
int hoge(int i, int j);
関数を呼ぶときはスタックをこんな風にしてやるわけです。
---------------- | j | i |addr| ----------------
帰るときは EAX レジスタに返り値をつんでおいて ret すると、スタックトップにあるアドレスに戻る、と。
さてこれで困るのは、関数内でスタックを使いたい時です。関数内で pop したりしてスタックポインタが変わってしまうと ret で帰れなくなってしまいます。
そういった問題に煩わされないように、各関数ではまず EBP と ESP を書き換えて、他の関数とはスタックを分けて使うことになっています。これがまあ俗にいう「スタックフレーム」ですね。勿論関数から帰る時にはそれらを復元してやります。
この辺も enter と leave といういかにもな命令が用意されています。
enter は、 push EBP; EBP = ESP; ESP -= size します。
leave は ESP = EBP; pop EBP します。
…なのですが、 gcc の吐くアセンブラは何か基本 enter は使いません。 enter は第二オペランドでネストレベルの指定ができて、まあ何か色々やってくれるんですが、そんなことはやらんでいいということでしょう。leave もローカル変数ないときは使われません。ESP 変わらないないからですね。
この辺まだまだ書くことはあるんですが、ひとまず最低限は書いた気がするのでここでおしまい。そもそもスタック絡むと文章だけで説明するのが異常にだるいのでもう適当でいい。暑いし。
ポインタと配列の話続き
おはよう昼ご飯！
http://yowaken.dip.jp/tdiary/20080709.html#p01
char array[] = "abc"; char *pointer = "abc"; array[0] = 'A'; pointer[0] = 'A';
これなんかはよくある例なのですが、ポインタと配列の違いではなく、より厳密には「ポインタの初期化子と配列の初期化子に文字列リテラル指定した時に文字列が確保される場所」の違いなので、ネタ元で求められている例とは違うかなあと思いました。
ポインタはもろ生のアドレスでただそれだけ、配列はちゃんとデータ持ってるんだけれどC言語のインターフェースから触るときはアドレスになっちゃってて、とかその辺がぱっと分かる例でないといけないんだよなあ難しいなあ。
段々機械語埋め込みの例が一番分かりやすい気がしてきた。騙されてる気しかしない。
