コールスタック：スタックフレーム、戻りアドレス、オーバーフロー

関数を呼び出すと、メモリにいくつかの値が書き込まれます。関数から戻るときは、そこから読み取ったアドレスへジャンプします。四つの短いプログラムから一つを選び、ステップごとに実行してスタックを見てみましょう。上ほどアドレスが大きく、書き込んだ場所は琥珀色、読み取った場所は青で示されます。取り除かれたフレームの格納場所も、薄く表示されたまま残ります。メモリの内容は消されていないからです。

計算例 — コールスタック：スタックフレーム、戻りアドレス、オーバーフロー

呼び出し回数	5
最大の深さ（フレーム数）	5
最も深い時点のスタック使用量	60／128バイト
結果	120

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — コールスタック：スタックフレーム、戻りアドレス、オーバーフロー

コールスタックは、関数を呼び出すたびにフレームを確保するメモリ領域です。この例では、フレームに引数、戻りアドレス（呼び出し元で処理を再開する位置）、呼び出し元の保存したフレームポインタ、局所変数を置きます。スタックポインタは、使用中の領域の最も低いアドレスを指します。呼び出すとフレームの大きさだけ下がり、戻ると上がります。再帰の深さがd、各フレームがfバイトなら、必要なスタックはd·fバイトです。

各記号の意味

d: 深さ：同時にスタックにあるフレーム数
f: 各フレームのバイト数：ここでは12に、局所変数ごとに4を加える

前提: 古典的なCの呼び出し規約を使う32ビットのマシンを想定しています。格納場所は各4バイトで、スタックは低いアドレスへ伸び、引数はスタックで渡されます。各フレームにはフレームポインタを保存します。実際の64ビット環境の呼び出し規約では、最初のいくつかの引数をレジスタで渡します。コンパイラがフレームポインタを省くこともあります。ARMでは、ほかの関数を呼び出さない関数なら、戻りアドレスをレジスタに保持できます。そのため、実際のフレームの大きさや配置は、この例の三つの格納場所とは異なります。

戻りアドレスはメモリにある数値なので、配列から上書きできる 🖖

4要素の配列に6個コピーを押してみましょう。copyのbufにはint型の値が4個入ります。buf[0]が最も低いアドレスにあるので、buf[4]とbuf[5]は、その領域のすぐ上にある二つの格納場所に当たります。そこには呼び出し時に、フレームポインタ、戻りアドレスの順で値が保存されています。ループは添字の範囲を確認しません。5個目の値がフレームポインタを上書きし、6個目の値0x46464646が戻りアドレスを上書きします。copyから戻るとき、プロセッサはその場所を読み、書かれているアドレスへジャンプします。値が4個なら、正しく0x08048400へ戻ります。5個でも戻り先は同じですが、壊れたフレームポインタをmainに引き継いでしまいます。これがスタックバッファオーバーフローです。1988年11月、モリスワームはこの方法でfingerdに侵入しました。fingerdは512バイトのバッファに入力を読み込む際、読み込む量に上限を設けていなかったのです。

値を設定しなかった変数には、前の呼び出しが残した値がある 🖖

残っていた値を押してみましょう。setは局所変数に42を入れて戻ります。戻るとスタックポインタは上へ移動しますが、メモリの内容は消されません。その後、同じ位置からpeekを呼び出すので、フレームは同じアドレスに置かれます。局所変数yのアドレスは1008。先ほどxがあった場所です。peekはyに何も書き込まないため、この実行ではyを読み取って42を返します。Cでは、初期化されていない変数の読み取りは未定義動作です。言語として結果を保証せず、最適化するコンパイラは、その場所を読み取る処理自体を省くこともあります。実際に読み取りが行われれば、そのアドレスに最後に書き込まれた値が見つかります。

スタックに積まれるのは、現在の呼び出しまでの経路 🖖

fibの引数を10にしてみましょう。呼び出しは177回あります。それでも、最も深い時点でスタックにあるのは10個のフレーム、120バイトです。同じ関数から分岐する再帰呼び出しでは、先の呼び出しのフレームを取り除いてから、次のフレームを積むためです。スタックにあるのは常に、fib(10)から今実行している呼び出しまでの連なりだけです。fact(11)の呼び出しは11回で、約16分の1ですが、オーバーフローします。呼び出しの連なりが11フレームに達し、132バイト必要になるからです。この二つの関数では、各呼び出しが再帰呼び出し以外に行う処理の量は一定です。そのため、呼び出し回数から実行時間を、最も長い呼び出しの連なりの深さからスタック使用量を見積もれます。

全プロセスの詳細解説

再帰はどこまで深くできる？ 4 ステップ
fact(11)でオーバーフローを押してみましょう。このページのスタック容量は128バイトです。Microsoftのリンカーがプログラムに割り当てる既定のスタック容量は1 MB。これを1 MiB、つまり1,048,576バイトとして、このページと同じフレームで考えます。factはどこまで深く呼び出せるでしょうか。各呼び出しに4バイトの局所変数を一つ加えたらどうでしょう。また、fib(30)には何バイトのスタックが必要で、呼び出しは何回あるでしょうか。

この問題をツールで開く
1. この例のフレームには、引数、戻りアドレス、保存したフレームポインタが入ります。大きさは3 × 4 = 12バイト。128 / 12 = 10.67なので、収まるのは10フレームです。fact(11)には11 × 12 = 132バイト必要で、結果の表にもオーバーフローと表示されます。
  
  $f = 3 \times 4 = 12, ⌊ \frac{128}{12} ⌋ = 10, 11 \times 12 = 132 > 128$
2. 1,048,576 / 12 = 87,381.33なので、87,381フレーム収まります。factは、スタックを使い切るまで深さ87,381の再帰が可能です。ただし、答えはそれよりはるかに早く32ビットのint型の範囲を超えます。13! = 6,227,020,800となる時点です。
  
  $⌊ \frac{1 048 576}{12} ⌋ = 87381$
3. 4バイトの局所変数を一つ加えると、各フレームは16バイトになります。1,048,576 / 16 = 65,536で、ちょうど割り切れます。
  
  $f = 16 : \frac{1 048 576}{16} = 65536$
4. fib(30)の最も長い呼び出しの連なりは30フレームなので、30 × 12 = 360バイトです。呼び出し回数は2·F(31) − 1。第31フィボナッチ数がF(31) = 1,346,269なので、2,692,537回になります。
  
  $d = 30 : 30 \times 12 = 360, 2 F_{31} - 1 = 2 \times 1346269 - 1 = 2692537$
解答

深さ87,381まで、局所変数を一つ加えると65,536までです。 fib(30)は2,692,537回呼び出されますが、必要なスタックは360バイトです。スタック使用量を決めるのは深さで、fibの実行時間を決めるのは呼び出し回数です。

$d_{m a x} = ⌊ \frac{S}{f} ⌋ = 87381 (f = 12), 65536 (f = 16)$

学習の道すじ

コンピュータはどうやってプログラムを動かすのか

参考文献 (2)

The worked problem's stack size: the linker's default reservation: Microsoft Learn, "/STACK (Stack allocations)," C/C++ build reference, updated 23 February 2022.
The first insight's 1988 example: fingerd's unbounded read into a 512-byte buffer on the stack: Bob Page, "A Report on the Internet Worm." University of Lowell, 7 November 1988 (copy hosted at Toronto Metropolitan University).

42Math チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。