Ibotenic by t-sin

C言語の勉強: バイナリ・アセンブリを通してみるC言語編 (それとJITコンパイル)

プログラミング C言語 言語処理系

2022-02-22T15:57:03.428471+09:00

karino2さんが公開しているC言語教室の第三回「バイナリやアセンブリから見るC言語とリンカ」を完走したので、感想やら反省やらを書きました。

c-lesson第三回を完走しました🥳

今朝がた、karino2さんが公開しているkarino2の暇つぶしプログラム教室 C言語編 (脳内通称c-lesson) の第三回「バイナリやアセンブリから見るC言語とリンカ」を完走しました。c-lessonは第３回が最後の回なのでc-lessonを最後まで完走したということになります。めでたい。

c-lessonの概要や第一回の内容・感想、開始した動機や挑戦者t-sinのレベルなどは第一回完走時の記事を、第二回の内容と感想や学びについては第二回完走時の記事読んでいただくこととして、ここでは完走した第三回のことを振り返ったりします。

第三回の内容

第三回は第二回のつづきとして、ARM7を対象に以下のことを学びます:

  1. アセンブリからみたC言語
  2. 分割コンパイルのしくみ
  3. リンカとローダのしくみ
  4. C言語からみたアセンブリ
    • ラスボス課題: スタックウォーク
  5. JITコンパイルしてみよう
    • インラインアセンブリ入門
    • 裏ボス課題: 超簡易PostScriptプログラムのJITコンパイル

第三回では、第二回の内容からさらに進んで、実際に実行可能バイナリをつくるときどのようなことが必要なのかを見ていきます。それに伴いARM7のベアメタル環境でプログラムを書いていた第二回から、第三回では環境がQEMUのユーザーモード (OSがあるっぽくうごく環境) に変わります。そのうえで今回は主にコンパイラ (clang) にアセンブリを吐かせてそれを読み解いていきます。

スタックウォークは最後の課題で、ある関数からそれを呼び出した関数の変数を参照する、というものです。スタックの中がどうなっているかをしっかり見通していないとへんてこりんなことになるので、第二回からつづくアセンブリの勉強のラストを飾るにふさわしい課題です。

そして第三回には「ラスボスを倒したら裏ボスも倒そう」ということで裏ボス課題が存在します。みんなだいすきJITコンパイルです。かなり骨のある課題なのでオプショナルな課題ですが、興味があったり「JIT」という言葉に胸がときめいてしまうひとは挑戦してみるといいでしょう。第一回、第二回そして第三回で得たすべての学びが勢揃いして戦ってくれるそのようすはまさにクライマックス。すこしづつながらJITコンパイルができていくそのカタルシスはたまりません。

第三回での学び

第三回での学びをつらつらと書くのですが、コードとかコミットがみたくなるかもしれないのでここにJIT課題完了時点でのコードへのリンクを貼っておきます。link_n_xxxのブランチが各課題に対応しています。

https://github.com/t-sin/c-lesson/tree/link_6_jit

分割コンパイルとリンカ

分割コンパイルやリンカの意義をあまりいままで実感したことがなかったなあ、とc-lessonページを読んでいて感じました。いまではあたりまえのようにコンパイルとリンクがわかれているうえにgccが裏でいろいろ自動でやってくれているので、こうやってアセンブリを読み書きしながらアドレス解決が必要であることを実感してはじめて、その意義が理解できたのは大きいです。あと副次的効果としてリンカスクリプトがちょっと読めるようになりました (with Google)。

この章の理解によって、『Linkers & Loaders』とか『リンカ・ローダ実践開発テクニック』といった本を読むという道が拓けました。積ん読も崩しやすくてやったね！

スタックウォーク

スタックウォークは、スタックトレースを取得するときなどに使える実践的テクニックです。この課題、とりかかってみると意外にすぐ終わるもののその難易度自体は高いというふしぎな課題です。コンパイラが吐くアセンブリを眺めつつスタックポインタを (無理矢理) 読み出し、そこから呼び出し側のローカル変数を辿っていくのはなかなかたのしいものです。コンパイラがローカル変数の個数よりも多めにスタック領域を確保していたりするのですがとくに使われてはいない、みたいな状況も起こったりします。これはコンパイルオプションによってはカナリア (スタックアンダーフローとかを検出するためにスタックに仕込んでおくチェック用のデータ) が入ったりする、というのが学びでした。

JITコンパイル

JIT課題は、やるとすればc-lessonで得たすべての学びを総動員して立ち向かう強敵です。とはいえ実はc-lessonのこれまでで書いてきたコードを援用して戦うのでじつは思ったほど重くありません。JITのバイナリ生成には第二回の簡易アセンブラからコードを持ってきてつかいますし、デバッグするのにも第二回の逆アセンブラのコードを利用します。そしてコンパイル対象言語は第一回の簡易PostScriptをもっと簡単にした言語 (リテラルと四則演算しかない) です。用意されたインタプリタのコードは第一回のときに死ぬほど改造したコードととてもよく似ていて理解するのもすぐにできます。そういえば第一回ではバイトコンパイルもやりましたね？ まさにあのバイトコンパイルの手順を再現すればよく、ただコンパイル先言語が機械語なだけです。

ちなみにこれはJIT課題についてのネタバレなので嫌なひとは読み飛ばしてほしいのですが、JITする対象アーキテクチャのARM7には除算命令がないのでじつは除算だけはアセンブリをそこそこ書いて自分で実装しなければなりません。JITだけでなく四則演算がどう実現されるのかを考える、という意味でも低レイヤーの世界を味わうことができるすばらしい課題です。

第三回完走の感想

第三回、じつはぼくはスタックウォーク直前までを2回やっています。最初は自分でアセンブリコードを吐かせて眺めることはせず、文章と提示されているコードだけを読んでいました。ただこれだと、やはりというか手を動かしていないせいで理解できない部分が多々あったのでもういちど最初から、コンパイラにアセンブリを吐かせるところも含めてやりなおしました。勉強するときは手を動かすのも大事である、という事実を再確認しました。数学とかも読んでるだけだとだめですものね。

JIT課題は完走が視野に入ってきてテンションが上がっていたせいか、第一回のころよりは雑に実装していました。それによって、JITしたバイナリがCのコールスタックを破壊していることに気付けないコードを書いてしまったので、今後は反省したいところです。ちなみにそのときやったミスとその対策は大事だと思うので詳しくここに書いておきます。

このコミットがバグっているコミットです。乗算オペレータが未実装なのに乗算オペレータがないとパスしないテストがパスしている、というのが発生した現象です。原因は、乗算に限らず演算子の計算結果をスタックにプッシュするのが正しいのにポップしていたため、呼び出し元 (ここではユニットテスト関数) のスタック領域までスタックポインタを戻してしまったから、でした。修正は以下のようにしましたが、ロード命令かストア命令かのフラグを間違えていたのが原因でした。

# https://github.com/t-sin/c-lesson/commit/c1e98ead182869c65e35546047acf95154a6dbc7
-            asm_ldm_or_stm(13, 0x04, 1, &output_emitter);  // stmdb r13, {r2}
+            asm_ldm_or_stm(13, 0x04, 0, &output_emitter);  // stmdb r13, {r2}

これを検出するためには、第二回の簡易アセンブラ実装のときのように生成されるバイナリを各部分ごとにテストしておくのがよさそうだと思いました。それをするためにはJITする各部分を関数に分けてその関数が生成するバイナリだけを確認できるようにしておく必要があります。ここを怠っていたのでこの対策をするのがめんどくさく、はやく先に進みたかったこともあって対策自体はやりませんでしたが。そういう点でも学びがありました。

ARM7には割り算の命令がない点は、JIT課題の中でうまく仕込まれた山場だと思います。JIT課題では実装順として、

  1. リテラルの実装
  2. 四則演算の実装
  3. 関数引数の利用

の順で実装していきます。このうち2の四則演算で足し算、引き算、そして簡易アセンブラにはなかったARMのMUL命令を追加しての掛け算まで実装していると「あとは除算命令を呼ぶだけかー」という気分になっていました。そこに立ち塞がる「ARM7に除算命令はない」という事実。よくできているなと思いました。つまり割り算の実装はラヴォスコアに相当するのではないでしょうか。

JIT課題を完了させての感想ですが、JITではいともたやすくえげつなくC言語側を破壊できるので、ちゃんと実装して大きなものをつくるには生成バイナリの動作をいかにしっかりしかし労力を抑えて保証するかが肝になりそうだと感じました。

第三回の思い出

ここでc-lesson第三回をまさにやっていたときのことを振り返ってみます。

C言語からみたアセンブリのところで、引数の種類 (整数、浮動小数点数、構造体、構造体のポインタ) によってスタックの使われ方がどう変化するかをclangにアセンブリを吐いてもらって読み解くのですが、だんだん頭では理解できなくなっていって紙にスタックのようすを書くとかしていました。これはそのときの写真です。

コンパイラが生成するアセンブリにはたまに無意味な部分があったりして、だいぶ惑わされたりしたものでした。

つぎのツイートはスタックウォーク課題に苦戦しているときのようすです。

このスタック辿り、自動化可能みたいですしできそうな感じもしますが、じっさいどうやるんだろう……。

つぎのツイートはJITコンパイル完走記念です。

ただひたすらにめでたい🥳

c-lesson完走の感想

いやー、ついに完走しました。第一回完走記事は2021年7月21日、そして(第二回完走記事)は2021年9月10日なのですが、第二回完走の後は転職活動やらアドベントカレンダーやらの準備などをしていてc-lessonからは離れていました。ここ1ヶ月くらいで戻ってきてぽつぽつ進めた、という感じです。

gitter.im上のc-lessonのチャットでコードを見てもらいながら進めたので、単に読みながら実装していくだけでは得られないさまざまなことを教わりました。思えば「継続」「バイトコンパイル」「JIT」の響きに惹かれてはじめたc-lessonでしたが、それらに留まらず、C言語の楽しさを体感でき、アセンブリへの苦手意識も解消され、いいコードを書くにはというソフトウェア開発の勘所も得ることが多く、とても有意義な教材でした。なにより楽しくすすめられるように作られていて、暇つぶしでこの教材がでてくるのはすごい。

第一回完走記事では以下がc-lessonをはじめた動機だと書いてありました。

  • 低レベルプログラミングについて知りたい
  • C言語をちゃんと知りたい
  • 言語処理系の実装について知りたい
  • 特に継続とその実装について知りたい

「低レベル」をどこまでとするかというのはいろいろあるかと思いますが、ここでは「言語処理系の下まわりが知りたい」くらいのニュアンスです。この動機・目標は見事に達成されたと思います。このときまだ「継続」については理解しかけでもんやりとしかわかってなかったですが、いまはひとまず言語処理系の基本はひととおり理解できたと思っています。言語実装ワナビから片足くらいは抜けたんじゃないでしょうか。

ここから先にはいろんな道 (最適化手法を知る、型とかそういう形式手法を知る、いろんな言語処理系の実装を見てまわる、自作言語をつくる) があると思いますが、さてどれにしましょうかという感じです。言語処理系実装は広大だわ……。

最後に

karino2さん、やっているうちに楽しくなっていく構成といい、得られる知識といい、とてもよい体験でした。とても感謝しています。ありがとうございました！！

みんなもc-lessonやっていこうぜ！！

karino2さんが公開しているC言語教室の第三回「バイナリやアセンブリから見るC言語とリンカ」を完走したので、感想やら反省やらを書きました。

タグ: プログラミング , C言語 , 言語処理系

作成日時: 2022-02-22T15:57:03.428471+09:00

更新日時: 2022-02-22T16:14:44.093964+09:00