スタックとヒープの違いにはまった話
TL; DR
- ヒープとスタックは違う
- メモリは0と1
- gdb楽しい
はじめに
以前に引き続き、C compilerを作っている
ポインタが思いの他簡単に実装できて感動していたら、ポインタと数字の加減算でめちゃくちゃにハマった
あっちこっちデバッグして、原因を探っていったら飛ぶように1週間ほど経っていたが、さきほど原因が判明してめっちゃ感動して、この記事を書き出した
書き上げるのに2日ぐらいかかってしまった
原因を探っていく過程で、スタックマシンとメモリについての理解が深まった
その記録
簡単なポインタの加減算
実装しようとしたのは、compiler bookのここ
「まだ配列がないので、mallocする」と書いてあったのでmalloc関数を使うのかと思いきや、mallocを使って配列をアロケートする方法がよく分からず肝心のテストが書けない
秘伝のあんちょこ、本家9ccのcommit logをたどってそれっぽい機能を実装したcommitを眺める
配列を宣言して、そこに値を代入すればいいと分かったので真似してテスト用の関数を書く
int *alloc2(int x1, int x2) { static int arr[2]; arr[0] = x1; arr[1] = x2; return arr; }
これで以下の簡単なポインタの加減算は動くようになった
int main() { int *p = alloc2(3, 6); return *(p + 1); // 6 }
ここまではそんなにかかっていない
すこし複雑なポインタの加減算
bookに書いてあるテストケース例ではテスト用関数から返り値でポインタを返すのではなく、アサインしたいポインタを渡して関数内でアサインする必要があったので、以下のテスト用関数を書いた
void allocp4(int **p, int x1, int x2, int x3, int x4) { int arr[4]; arr[0] = x1; arr[1] = x2; arr[2] = x3; arr[3] = x4; *p = arr; return; }
友人に指摘されるまでポインタのポインタ（int **p）という概念が出てこず、compileが通らなくてハマった
ポインタは難しい
このときにstaticが必要ないのでは？と思って、試しに外してテストを書いてみたのが、この後の大ハマりの原因になる
テストケース例のコード
int main() { int *p; allocp4(&p, 1, 2, 4, 8); int *q; q = p + 3; return *q; // 実行ごとに不定の値 🤔 }
明らかにポインタが指している値がおかしなことになっている
こういうときはとりあえず、シンプルなものに書き直して様子を見るに限る
シンプルにしたテスト関数
void allocp2(int **p, int x1, int x2) { int arr[2]; arr[0] = x1; arr[1] = x2; *p = arr; return; }
テストケース
int main() { int *p; allocp2(&p, 30, 31); int *q; q = p + 1; return *q; // -> 0 🤔 }
31になってほしいが、思ったとおりにいかない🤔
加算する値を0にしても、返ってくる値は0のままで特に変化なし
加算する値を2以上にすると、実行ごとに変わる不定の値になって想定通り
もう1つシンプルにする
int main() { int *p; allocp2(&p, 30, 31); return *(p + 1); // -> 31 👍 }
これは想定通りに動く
動いたので1つ複雑度を上げる
int main() { int *p; int q; allocp2(&p, 30, 31); q = *(p + 1); return q; // -> 0 🤔 }
qをポインタではない普通の変数で宣言したが、やはり動かない
このあたりで変数宣言が実装していないのに初期化式が動いていたことを思い出して、きちんと実装し直す
しかし、結果は変わらない
ここまでで5日ぐらいかかっている
Assemblyのデバッグ
ここまでテストケースのcompileそのものは成功している
compile段階でSEGVしてくれた方が原因の特定はしやすい
思い当たる節もないので、地道にparserの出力したASTがおかしくないか、codegenでassebmblyにどのnodeから生成されたかのコメントもつけて書き出してみる
特におかしいところは見受けられない
ここまでやって打つ手がなくなったので、ついに出力されたassemblyを下の方から直接編集して途中の結果を雑にretしてどこからおかしいのか確認した
gdbを使わなかった理由は使い方がよく分からなかったため
すると、おかしくなっている行を特定できた
以下が出力されたassemblyの一部
...
call allocp2
push rax
# ND_ASSIGN start gen_lbal lhs
mov rax, rbp
sub rax, 16
push rax
# ND_ASSIGN end gen_lbal lhs
# ND_ASSIGN start gen rhs
# ND_DEREF start
# gen lhs
mov rax, rbp
sub rax, 8
push rax
pop rax
mov rax, [rax]
push rax
# <== A1 ==>
# gen rhs
push 1
# <== A2 ==>
pop rdi
pop rax
push rax
mov rax, 4
imul rdi, rax
pop rax
add rax, rdi
...
A1の時点では*(p + 1); のうち、pの値、つまりpの指すメモリアドレス（pはポインタなので）がスタックトップに積まれている
なので、以下をA1に挿入すると、pが指しているアドレスの値をretできる
pop rax mov rax, [rax] mov rsp, rbp pop rbp ret
これは想定通りに30が返ってくる
次にA2の時点では1をスタックにpushしている
ということで、2回popして値を見れば同じように30が返ってくるはず
pop rax pop rax mov rax, [rax] mov rsp, rbp pop rbp ret
ところが、結果は1
push 1 で pの指すメモリアドレスが1に書き換えられてしまっているらしい
ここまで特定できたので、ようやくgdbの使い方を少し調査してメモリアドレスの変化を観察することにした
調査に使った資料はこのあたり
- gdbを使う - Qiita
- gdbの主要コマンド
- gdbの使い方のメモ - ももいろテクノロジー
- gdbでアドレスが指す先のアドレスをdereferenceするコマンドを作った - φ(・・*)ゞ ｳｰﾝ カーネルとか弄ったりのメモ
おもむろにgdb ./tmpでgdbを起動、disp/i $pc でステップ実行ごとに次に実行されるassemblerを表示するようにして、b mainでmainの定義位置にbreak pointを置いて、いざrunする
disasして、assemberを表示し、アドレス指定でallocp2の呼び出しと先程のA1の直前にbreak pointを設定する
最初のbreak pointでのrbpとrspのアドレスと値
(gdb) i r rbp rsp rbp 0x7fffffffd900 0x7fffffffd900 rsp 0x7fffffffd900 0x7fffffffd900
cして、allocp2の呼び出しにいって、niして、rbpとrspを確認
(gdb) i r rbp rsp rbp 0x7fffffffd900 0x7fffffffd900 rsp 0x7fffffffd8f0 0x7fffffffd8f0
$rbpからそれっぽいところまでメモリを10進数出力して対応を見てみる
現状の9ccsは変数のメモリを決め打ちで$rbpから8byteのoffsetで置いてるのでこんな感じ
(gdb) x/-80bd $rbp + 8 0x7fffffffd8b8: -25 -40 -1 -1 -1 127 0 0 0x7fffffffd8c0: 31 0 0 0 30 0 0 0 0x7fffffffd8c8: -8 -40 -1 -1 -1 127 0 0 0x7fffffffd8d0: 30 0 0 0 31 0 0 0 0x7fffffffd8d8: 0 110 9 127 53 41 -38 58 0x7fffffffd8e0: 0 -39 -1 -1 -1 127 0 0 0x7fffffffd8e8: 126 81 85 85 85 85 0 0 0x7fffffffd8f0: -16 -39 -1 -1 -1 127 0 0 <- q, $rsp 0x7fffffffd8f8: -48 -40 -1 -1 -1 127 0 0 <- p 0x7fffffffd900: 0 0 0 0 0 0 0 0 <- $rbp
30と31とallocp2で配置されたらしき数字が確認できる
0x7fffffffd8f8 の値はpointerのpで10進数ではなくアドレスなので確認してみる
(gdb) x/a 0x7fffffffd8f8 0x7fffffffd8f8: 0x7fffffffd8d0
確かにアドレスが入っていて、0x7fffffffd8d0を指している
さっき出力したメモリを見ると確かに30を指している
せっかくgdbがexpressionが使えるので、$rbpからのオフセットでも見てみる
(gdb) x/a $rbp - 8 0x7fffffffd8f8: 0x7fffffffd8d0 (gdb) x/db *(int **) ($rbp - 8) 0x7fffffffd8d0: 30
この時点ではきちんと30が入っている
では cして、A1の直前のbreak pointまでいって、ni する
rbpとrspを確認
(gdb) i r rbp rsp rbp 0x7fffffffd900 0x7fffffffd900 rsp 0x7fffffffd8d8 0x7fffffffd8d8
10進数出力
(gdb) x/-80bd $rbp + 8 0x7fffffffd8b8: -25 -40 -1 -1 -1 127 0 0 0x7fffffffd8c0: 31 0 0 0 30 0 0 0 0x7fffffffd8c8: -8 -40 -1 -1 -1 127 0 0 0x7fffffffd8d0: 30 0 0 0 31 0 0 0 <- *p 0x7fffffffd8d8: -48 -40 -1 -1 -1 127 0 0 <- $rsp 0x7fffffffd8e0: -16 -40 -1 -1 -1 127 0 0 0x7fffffffd8e8: 0 0 0 0 0 0 0 0 0x7fffffffd8f0: -16 -39 -1 -1 -1 127 0 0 <- q 0x7fffffffd8f8: -48 -40 -1 -1 -1 127 0 0 <- p 0x7fffffffd900: 0 0 0 0 0 0 0 0 <- $rbp
スタックが伸びて$rspがpの指しているポインタの直前まで来ている
(gdb) x/db *(int **) ($rbp - 8) 0x7fffffffd8d0: 30
まだこの段階では*pは30だが、大変不穏な気配
ではいざ問題のA2のinstruction、つまり、push 1に進めるためにまたniする
rbpとrspを確認
(gdb) i r rbp rsp rbp 0x7fffffffd900 0x7fffffffd900 rsp 0x7fffffffd8d0 0x7fffffffd8d0
メモリダンプ
(gdb) x/-80bd $rbp + 8 0x7fffffffd8b8: -25 -40 -1 -1 -1 127 0 0 0x7fffffffd8c0: 31 0 0 0 30 0 0 0 0x7fffffffd8c8: -8 -40 -1 -1 -1 127 0 0 0x7fffffffd8d0: 1 0 0 0 0 0 0 0 <- *p, $rsp 🤯 0x7fffffffd8d8: -48 -40 -1 -1 -1 127 0 0 0x7fffffffd8e0: -16 -40 -1 -1 -1 127 0 0 0x7fffffffd8e8: 0 0 0 0 0 0 0 0 0x7fffffffd8f0: -16 -39 -1 -1 -1 127 0 0 <- q 0x7fffffffd8f8: -48 -40 -1 -1 -1 127 0 0 <- p 0x7fffffffd900: 0 0 0 0 0 0 0 0 <- $rbp
push 1 はcompiler bookにもあるように以下と同じ
sub rsp, 8 mov [rsp], 1
ということで、 pの指していたアドレスの値が1に書き換わってしまった
念の為、オフセットでも確認しておく
(gdb) x/db *(int **) ($rbp - 8) 0x7fffffffd8d0: 1
やはり、1になってしまっている
そして、この後は、pの指しているアドレスに対して +4 するので 結果 p + 1 が 0x7fffffffd8d4 になる
ここは、さっき1に書き換わったところなのでderefすると値が0になる
そして、qに0が代入されて0がreturnされるという挙動になっていた
ということで、stackが書き換わるのを見て「これ、stackとheapの違いというやつでは？」と気づく
staticをつける
ここまでの調査からして、自分で書いたcompiler部分ではなくテスト関数のallocp2の実装がおかしいのは明らかだったのでとりあえずそっとstaticを戻してみた
void allocp2(int **p, int x1, int x2) {
static int arr[2];
arr[0] = x1;
arr[1] = x2;
*p = arr;
return;
}
int main() { int *p; int q; allocp2(&p, 30, 31); q = *(p + 1); return q; // 31 👍 }
同じようにA1の直後のダンプたち
(gdb) i r rbp rsp rbp 0x7fffffffd900 0x7fffffffd900 rsp 0x7fffffffd8d8 0x7fffffffd8d8 (gdb) x/-80bd $rbp + 8 0x7fffffffd8b8: -25 -40 -1 -1 -1 127 0 0 0x7fffffffd8c0: -26 -40 -1 -1 -1 127 0 0 0x7fffffffd8c8: -51 83 85 85 85 85 0 0 0x7fffffffd8d0: 31 0 0 0 30 0 0 0 0x7fffffffd8d8: 32 -128 85 85 85 85 0 0 <- $rsp 0x7fffffffd8e0: -16 -40 -1 -1 -1 127 0 0 0x7fffffffd8e8: -8 -40 -1 -1 -1 127 0 0 0x7fffffffd8f0: -16 -39 -1 -1 -1 127 0 0 <- q 0x7fffffffd8f8: 32 -128 85 85 85 85 0 0 <- p 0x7fffffffd900: 0 0 0 0 0 0 0 0 <- $rbp (gdb) x/a ($rbp - 8) 0x7fffffffd8f8: 0x555555558020 <arr.2155> (gdb) x/db *(int **) ($rbp - 8) 0x555555558020 <arr.2155>: 30
pの指すアドレスがRBPの近く（スタック）ではなく、まったく違う場所（ヒープ）を指していることが分かる
ということで、A2の直後のダンプ
(gdb) i r rbp rsp rbp 0x7fffffffd900 0x7fffffffd900 rsp 0x7fffffffd8d0 0x7fffffffd8d0 (gdb) x/-80bd $rbp + 8 0x7fffffffd8b8: -25 -40 -1 -1 -1 127 0 0 0x7fffffffd8c0: -26 -40 -1 -1 -1 127 0 0 0x7fffffffd8c8: -51 83 85 85 85 85 0 0 0x7fffffffd8d0: 1 0 0 0 0 0 0 0 <- $rsp 0x7fffffffd8d8: 32 -128 85 85 85 85 0 0 0x7fffffffd8e0: -16 -40 -1 -1 -1 127 0 0 0x7fffffffd8e8: -8 -40 -1 -1 -1 127 0 0 0x7fffffffd8f0: -16 -39 -1 -1 -1 127 0 0 <- q 0x7fffffffd8f8: 32 -128 85 85 85 85 0 0 <- p 0x7fffffffd900: 0 0 0 0 0 0 0 0 <- $rbp (gdb) x/a ($rbp - 8) 0x7fffffffd8f8: 0x555555558020 <arr.2155> (gdb) x/db *(int **) ($rbp - 8) 0x555555558020 <arr.2155>: 30
最初に動いていたポインタとINTの演算も命令数が少なく、Stackが破壊されないのでたまたま動いていただけなのであった
めでたしめでたし
最後に
自分で書いてきたコンパイラだが、ポインタを扱いだしたあたりからなぜ動いてるのかうまく説明できる自信がなかった
今回のハマりはstaticを不用意に消すというポカから発生したが、結果的にgdbで遊んだりメモリの中身を見て、スタックマシンの概念をより具体的に理解できたので良かった
compiler bookのコラムにあったスタックの伸び方の話や、スタックとヒープが違うものだということがだいぶ体感できた
レジスタとメモリをつかったスタックマシン、本当に人類の叡智の結晶という感じがしてすごい（こなみ
おしまい
コラム: メモリは0と1
メモリに置いてある値を解釈するという概念が難しくて、pointerの指している値を出すのにめっちゃ苦労した
例えばこれ
(gdb) x/db *(int **) ($rbp - 8) 0x555555558020 <arr.2155>: 30
これは、$rbp - 8 をintへのポインタとして解釈して、 その値をd(ecimal)でb(yte)で区切って表示する
これをこうすると謎の巨大数値がでてくる
(gdb) x/dg *(int **) ($rbp - 8) 0x555555558020 <arr.2155>: 133143986206
これは、b(yte)がg(iant word)になって、64byteで解釈されている
実体的にはこう
(gdb) x/tg *(int **) ($rbp - 8) 0x555555558020 <arr.2155>: 0000000000000000000000000001111100000000000000000000000000011110
tはbinaryなので、binary表現になった
これだと長すぎて分かりづらいので分割
(gdb) x/2tw *(int **) ($rbp - 8) 0x555555558020 <arr.2155>: 00000000000000000000000000011110 00000000000000000000000000011111
w(ord)なので32byteで区切った
もうちょい区切る
(gdb) x/8tb *(int **) ($rbp - 8) 0x555555558020 <arr.2155>: 00011110 00000000 00000000 00000000 00011111 00000000 00000000 00000000
ここまでくると一番最初の30の正体が判明して 0x555555558020 から 8byte取ってきて10進数で解釈した 00011110の値となる
ちなみに、byteでもhalfwordでもwordでも同じ
ただ、gにすると64byteになって変わる
(gdb) x/xg *(int **) ($rbp - 8) 0x555555558020 <arr.2155>: 0x0000001f0000001e (gdb) x/dg *(int **) ($rbp - 8) 0x555555558020 <arr.2155>: 133143986206
これで、133143986206の正体も判明して、0x555555558020 から64byte取ってきて10進数で解釈するとこんな巨大な値になった
16進数だとだいぶ分かりやすい
コードを書いているとあまりに自然に10進数が使えるので忘れがちだけど、メモリがあくまで0と1を記憶しているだけのもので、工夫で10進数を扱えるようにしているというのがこれでしっくりきた
コラム2: メモリの値確認
xでメモリの値を確認するのがめっちゃ大変
上の例と同じくこう
(gdb) x/db *(int **) ($rbp - 8) 0x555555558020 <arr.2155>: 30
$rbp - 8 が指してるアドレスが知りたい
(gdb) x/a ($rbp - 8) 0x7fffffffd8f8: 0x555555558020 <arr.2155>
0x7fffffffd8f8 が指してるアドレスが指している値が知りたい
(gdb) x/a 0x7fffffffd8f8 0x7fffffffd8f8: 0x555555558020 <arr.2155>
これはアドレスそのもので、アドレスが指している値じゃない
(gdb) x/db *(0x7fffffffd8f8) 0x55558020: Cannot access memory at address 0x55558020
だめ
(gdb) x/db int 0x7fffffffd8f8 A syntax error in expression, near `0x7fffffffd8f8'.
だめ
(gdb) x/db * (int *) 0x7fffffffd8f8 0x55558020: Cannot access memory at address 0x55558020
だめ
(gdb) x/db * (int **) 0x7fffffffd8f8 0x555555558020 <arr.2155>: 30
できた
Cの有効な文法を書くのに未だに慣れない
特にポインタのポインタみたいなのが難しい
