コールスタック

Basis
最終更新:

前提知識

プログラムが関数を呼び出すたびに、その関数が戻った後にどこから実行を再開するかを記憶しておく何かが必要だ。main が square を呼び、square が multiply を呼んだとすると、コンピューターは「multiply が終わったら square に戻れ、square が終わったら main に戻れ」と知っていなければならない。その「何か」がコールスタック（call stack）だ。

コールスタックとは

コールスタックとは、OS（オペレーティングシステム）が起動時にプログラムに割り当てるメモリ領域のひとつだ。プログラムはここを関数呼び出しの管理にだけ使う — 呼び出しのたびに情報が追加され、戻りのたびに削除される。Stack で学んだ LIFO（last in, first out）の性質が、この構造に自然にマッチする — 最後に呼ばれた関数が常に最初に戻るからだ。

各アクティブな関数呼び出しのために格納される情報の単位をスタックフレーム（stack frame）、または activation record と呼ぶ。関数が呼ばれるとコールスタックに新しいフレームがプッシュ（push）され、戻るとそのフレームがポップ（pop）される。

スタックフレームの中身

スタックフレームには、関数が実行してクリーンに戻るために必要なすべてが格納される：

  • リターンアドレス（return address）— この関数が戻った後に呼び出し元のどの命令から実行を再開するかを示すメモリアドレス。これがなければ CPU はどこにジャンプすればよいかわからない。
  • ローカル変数（local variables）— 関数本体内で宣言された変数（例: var count: i32 = 0）。
  • 関数の引数（function arguments）— 関数に渡された値。現代のアーキテクチャでは引数はまず CPU レジスタに置かれ、多すぎて収まらない場合にのみフレームに置かれる。
  • 保存されたレジスタ（saved registers）— 呼び出し元が使っている CPU レジスタをこの関数も必要とする場合、先にその値をフレームに保存し、戻る前に復元する。

スタックフレームを手動で管理する必要はない。プッシュとポップのコードはすべてコンパイラが生成する。重要なのはフレームの中身を理解することだ — その知識があってこそ、スタックオーバーフロー、変数の生存期間、デバッガのバックトレースが説明できる。

呼び出しをステップごとに追う

2 段階の呼び出しチェーンを持つ小さな Zig プログラムを示す：

const std = @import("std");

fn multiply(a: i32, b: i32) i32 {
    return a * b;
}

fn square(n: i32) i32 {
    return multiply(n, n);
}

pub fn main() void {
    const result = square(5);
    std.debug.print("{}\n", .{result}); // 25
}

このプログラムの実行中にコールスタックがどう変化するかを追ってみよう：

  1. main が開始する。 main のフレームがプッシュされる。result のストレージ（未設定）と、OS の起動コードへ戻るリターンアドレスが格納される。

  2. main が square(5) を呼ぶ。 square のフレームが main のフレームの上にプッシュされる。引数 n = 5 と、main に戻るリターンアドレスが格納される。

  3. square が multiply(5, 5) を呼ぶ。 multiply のフレームがプッシュされる。a = 5、b = 5、そして square に戻るリターンアドレスが格納される。

  4. multiply が実行されて 25 を返す。 フレームがポップされる。CPU は保存されたリターンアドレスにジャンプし、square の中に戻る。

  5. square が 25 を返す。 フレームがポップされる。実行が main に戻る。

  6. main が result に 25 を格納し、print 呼び出しへと続く。

どの瞬間においても、コールスタックには「呼ばれたが、まだ戻っていない」すべての関数のフレームが格納されている — main から現在の実行位置までのアクティブな呼び出しチェーンそのものだ。

スタックポインタ

CPU はスタックポインタ（stack pointer）と呼ばれる専用レジスタ（x86-64 では rsp）を持ち、常にコールスタックの先頭を指す。フレームがプッシュされるとスタックポインタが移動してスペースを確保し、フレームがポップされると元に戻る。

デバッガでバックトレース（backtrace、スタックトレースとも呼ぶ）を要求すると、現在の先頭フレームから main まで順にコールスタックをたどり、各関数名とそのフレームに格納された値を表示する。バックトレースが実行が止まるまでの呼び出しチェーンをそのまま表示できるのは、スタックポインタがデバッガの出発点を与え、各フレームがその下のフレームの見つけ方を記録しているからだ。

スタックオーバーフローの原因

コールスタックのサイズは有限で、スレッドあたり通常数メガバイト程度だ。プッシュがポップを上回るペースで続くと、やがてスペースが尽きる。これがスタックオーバーフロー（stack overflow）だ。

最もよくある原因は、終わりのない再帰（unbounded recursion）だ：

fn infinite(n: i32) i32 {
    return infinite(n + 1); // 一切返らない — フレームをプッシュし続ける
}

呼び出すたびに戻ることなく新しいフレームをプッシュするため、OS がオーバーフローを検出してプロセスを終了させるまでスタックが成長し続ける。Zig（Rust や C と同様）は呼び出しごとにスタック深度チェックを挿入しない。OS はガードページ（guard page）— スタック末端のすぐ先にある保護されたメモリ領域 — を使って検出する。スタックポインタがこの領域を越えるとフォルトが発生する。

再帰なしでもスタックオーバーフローは起こる。非常に大きなローカル配列を宣言すると、1 つのフレームだけでスタックの残りスペースを使い切ることがある：

fn bigFrame() void {
    var buffer: [10_000_000]u8 = undefined; // スタック上に 10 MB
    _ = buffer;
}

大きな割り当ての解決策はスタックではなくヒープだ — malloc とダイナミックメモリ で扱う。

ローカル変数はフレームに縛られている

ローカル変数はスタックフレームの内部に存在するため、そのフレームがスタック上にある間だけ有効だ。関数が戻るとフレームがポップされ、そのメモリは直ちに次の呼び出しで再利用可能になる。

つまり、ローカル変数へのポインタを返すのは安全でない。呼び出し元がそのポインタを通じて値を読む時点では、変数を持っていたフレームはすでに消えており、メモリが新しいフレームに属している可能性がある。

fn dangling() *i32 {
    var x: i32 = 42;
    return &x; // x のフレームはこの return の直後にポップされる
}

Zig はこの間違いをコンパイル時に検出する。Rust ではボローチェッカーが同じ不変条件を強制する。どちらの場合も根本的な理由は同じ — ポインタが、自分の指すデータを所有するスタックフレームより長生きしてしまう可能性があるからだ。

まとめ

  • コールスタックは、実行時に関数呼び出しを管理する LIFO のメモリ領域だ。
  • 関数呼び出しごとにスタックフレームがプッシュされ、戻りのたびにポップされる。フレームにはリターンアドレス、ローカル変数、引数、保存されたレジスタが格納される。
  • スタックポインタレジスタがスタックの現在の先頭を追跡する。デバッガのバックトレースはそこから始まり main まで降りていく。
  • スタックオーバーフローは、フレームがポップされるより速く積み重なったときに起きる — 最もよくある原因は終わりのない再帰だが、非常に大きなローカル割り当てでも発生する。
  • ローカル変数は関数のフレームがスタック上にある間だけ有効だ。ローカル変数へのポインタを返すのはこの理由で安全でない。

これを使うもの