<< 2024-07-28のCコンパイラゼミ | Cコンパイラゼミ2024 | セキュリティキャンプ2024 3日目のCコンパイラゼミ >>
analyze.cのみを自作コンパイラ、それ以外をgccで動かしたとき、while文をコンパイルするとセグフォが起きる
前回の2024-07-28のCコンパイラゼミから期間が開いたので、まずはバグを再現するところから始める。とは言ってもmakeですぐ動くようにしてるので思い出すだけ。
analyze.cのみを自作コンパイラで動かしたときにセグフォが起きている。
callocから受け取るアドレスがやけに短いことが分かった。callocは標準ライブラリのものを使用しているので、バグがあるとは考えづらい。そこから、16バイトアライメントにバグがあるのではないかという話になった。
- callocを呼び出した後
- RAXは
0x416230(短すぎる)
- RAXは
- callocを呼び出す前
- RDIは1
- RSIは12
- RSPは
0x7fffffffcef4(16バイトアライメントが出来てない！！)
16ビットアライメントじゃなくて、16バイトアライメントだった。
ここで、スタックに変数を積んでいるところで16バイトアライメントに対応していないことに気づく。実際にアセンブリを見てみるとsub rsp, 20とかがある。なので、この部分を8の倍数に切り上げることで対処した。(のこりの8バイトはpushとpopで調整する)。
45分くらい格闘した所、whileの入ったファイルをself2-analyzeでコンパイルするとセグフォするが解決した。最初にセグフォが起きてからは大体4-5時間で解決したことになる。
main.cを自作コンパイラ、それ以外をgccでコンパイルした場合、while文をコンパイルするとセグフォが起きる
処理をfor文に書き換えても出続けるので、それの共通点であるcallocとsprintfの呼び出しが怪しい。さらに、今回自作コンパイラでコンパイルしたmain.cと実際のセグフォが起きるanalyzeとが離れていることから、これも16バイトアライメントが壊れているせいじゃないかと考えた。
結果として、スタックのオフセットを計算する箇所で(8 - offset) % 8が正しいのに7 - offset % 8としていたのが原因だった。
map.cだけ自作コンパイラの場合、tokenizeだけ自作コンパイラの場合、parseだけ自作コンパイラの場合、analyzeだけ自作コンパイラの場合にセグフォが発生するようになった
モグラたたきみたいにセグフォが出てくる。
またsprintfで落ちているので、これも16ビットアライメントが原因ではないかと考えた。そして同じようにcallocで取得した値が16進6桁しかなかった。
main関数から関数呼び出しを全部追っていって、16ビットアライメントが崩れた瞬間を追ってみた。5分くらいずっとエンターキーを押してた。すると、switch-caseの条件分岐の箇所でRSPの値が崩れていることが分かった。
これまではpush/popの数を数えて関数呼び出し時に数に応じて調整する形にしていた。けれど、条件分岐やループがあるとこの数え上げが狂ってしまう。なので、今までの方針では実装できないか、かなり難しいことが分かった。
そこで、実行時にRSPの値を見て、いい感じにパディングを詰める方式にすることにした。call命令の直前に、RSPの値を対比させた上でパディングを詰める。call命令の直後にRSPの値を復帰させる。
退避させる場所はローカル変数やR15などがあるが、今回はR15に退避することにした。そしてR15の値は関数定義のタイミングでスタック領域に退避することにした。(なんで直接スタック領域に退避させるんじゃなく、R15を挟んだのかは謎。今思うとRBPでスタックのアドレスはわかるのだから、R15を挟む必要はなかったように思う。)
なぜSIMD命令を使うときだけ調整するのではなく、全ての関数呼び出しで16バイトアライメントを要求するのかが不思議 ⇒ 今のコンパイラはレジスタに計算途中の値を保存することが多く、わざわざスタックを使う頻度は少ない。逆にSIMD命令はよりきつい高速化をする箇所で使われていて、SIMD命令を使うたびにスタックポインタを動かしていると高速化にならないからではないか。とのこと。
callerは他人を呼び出すやつ、calleeは他人に呼び出される人。
セルフホスト前最後のバグ
R15を退避する形で実装した所、セグフォが出るようになった。parser.cのint_type内のmov [rax], rdiでセグフォが出る。
⇒ call をした後に rsp を復帰するのを忘れてただけだった
セルフホスト達成！
16ビットアライメントを実装した所第2世代コンパイラと第3世代コンパイラが動いて、さらに第2世代と第3世代のアセンブリが一致した！セキュキャンの目標を講義1日目の午前中に達成できた！
ここらへんでお昼ごはんを食べに行く。以降は午後の作業。
挙動の等しさを示す方法はない。ライスの定理という。美味しそう。
#includeの実装について
#includeの実装をするときに、ファイル名と行数を使う部分があることが問題になる(エラー表示、__FILE__, __LINE__)。gccでは、プリプロセッサを実行すると、1つの文字列にファイル名と行数が変わった旨のコメントが残されるようになっている。これをtokenizerで解析することによって、一つの文字列を扱いながら複数のファイルと行数を扱うことができそう。
ドーナツがセグフォする
c-compiler/misc/donut_verbose.c at 17f53331a19e37594d07e69cc70bc71ae30eb6f4 · hsjoihs/c-compiler · GitHub を動かしている。ドーナツのアニメーションを行うプログラム。
b[o] = ".,-~:;=!*#$@"[0];でセグフォしていることが分かった。
以下のNを計算する処理がかなりややこしいので、コレを計算する過程でレジスタが壊れているのではないかという疑惑。
N = 8 * (
mul(mul(sinthetaTimes10000, sinATimes10000) - mul(mul(sinphiTimes10000, cosATimes10000), costhetaTimes10000), cosBTimes10000)
- mul(mul(sinphiTimes10000, sinATimes10000), costhetaTimes10000)
- mul(sinthetaTimes10000, cosATimes10000)
- mul(mul(cosphiTimes10000, sinBTimes10000), costhetaTimes10000)
) / 10000;と思って3重関数呼び出しを試したものの、問題はなさそう。ほな違うか。
識別子名が長いのも、for(;;)も、両方テストで試しているので問題ない。困ったのでアセンブリを印刷して、手でアセンブリを追ってgdbと比較してみることにした。すると、Nの値が相当大きく計算されていて、343万とかになっていることが分かった。
先程のNの大きい計算式を分解してみて、どこで変な値が入っているのかを確認することにした。
int _a = mul(mul(sinthetaTimes10000, sinATimes10000) - mul(mul(sinphiTimes10000, cosATimes10000), costhetaTimes10000), cosBTimes10000);
int _b = mul(mul(sinphiTimes10000, sinATimes10000), costhetaTimes10000);
int _c = mul(sinthetaTimes10000, cosATimes10000);
int _d = mul(mul(cosphiTimes10000, sinBTimes10000), costhetaTimes10000);
int N = 8 * (_a - _b - _c - _d) / 10000;すると、次のような結果が得られた。_aが負数のときにNがめちゃくちゃでかくなってしまう。gccではNは0になるので、Nの計算を自作コンパイラで行っている部分が悪いことになる。
N: 0, _a: 0, _b: 0, _c: 0, _d: 0
N: 3435973, _a: -200, _b: 0, _c: 0, _d: 0
3435973 の 1250 倍がほぼ 4294967296
64 bit / 32 bit の計算をしていそう
64 bit 側には、`8 * (2 ** 32 - 200)` が入ってしまっていて、
それを 32 bit の 10000 で割っていそう
Step 1: 32 bit の -200 であるところの `0xffff_ff38` が用意される
Step 2: これが 0 拡張されて 64 bit の `0x0000_0000_ffff_ff38` になる
Step 3: これが 8 倍され、`0x0000_0007_ffff_f9c0` になる
Step 4: これは 34359736768 であり、10000 で割ると 3435973
ということらしい。気づけるかーい！
負数の割り算のテストケースをいくつか書いて確かめてみた。
int a = -200;
assert(-100, a / 2, "a / 2");
assert(100, a / -2, "a / -2");
assert(-5, 500 / -100, "500 / -100");
assert(5, -500 / -100, "-500 / -100");
assert(8, 8 * a / 100, "8 * a / 100");
assert(8, (1000 + a) / 100, "(1000 + a) / 100");すると結果は以下のようになった
*** Assertion failed: a / 2
Expected: -100
Actual: 2147483548
Test for the 1st 負の数の除算
*** Assertion failed: a / -2
Expected: 100
Actual: -2147483548
Test for the 2nd 負の数の除算
*** Assertion failed: 8 * a / 100
Expected: 8
Actual: 343597367
Test for the 5th 負の数の除算
*** Assertion failed: (1000 + a) / 100
Expected: 8
Actual: 42949680
Test for the 6th 負の数の除算
FAILED
負の数の割り算と、負の数を符号拡張して割ったものが失敗している。実装の方針として、analyzerで符号拡張をするタイミングでノードを挟むようにして、genでそれに従って符号拡張をする形にする。
が、符号拡張の仕様はとても難しいということが分かった。(参考リンク: Implicit conversions - cppreference.com)ので、明日は符号拡張の仕様を理解する日にすることにした。