コールスタック

出典: フリー百科事典『ウィキペディア（Wikipedia）』

コールスタック (Call Stack)は、情報工学においてプログラムの実行中サブルーチンに関する情報を格納する特殊なスタックである。実行中のサブルーチンとは、呼び出されたが処理を完了していないサブルーチンを意味する。実行スタック (Execution Stack)、制御スタック (Control Stack)、関数スタック (Function Stack)などとも呼ばれる。また、単に「スタック」と言ったときにコールスタックを指していることが多い。

コールスタックを使う目的はいくつかあるが、主たる目的は実行中サブルーチンの処理を完了して制御を戻す（呼び出し側に戻る）ときに、どこに戻ればよいかを覚えておくことである。例えば、次の擬似コードを考える。

subroutine DrawSquare(Point p1, Point p2, Point p3, Point p4)
{
    ... 略 ...
    
    DrawLine(p1, p2);
    DrawLine(p2, p3);
    DrawLine(p3, p4);
    DrawLine(p4, p1);
    
    ... 略 ...
}

サブルーチンDrawSquare内の4ヶ所からサブルーチンDrawLineを呼び出すとしたとき、DrawLineは4ヶ所のうちのどこに戻ればよいかを知る必要がある。一般にDrawSquareのコード内でDrawLineを呼び出しているそれぞれの箇所で、呼び出し処理の次の命令のアドレス（これをリターンアドレスと呼ぶ）をコールスタックに格納することでこれを実現する。

コールスタックはスタックとして構成されているので、呼び出し側はリターンアドレスをスタックに push し、呼び出されたサブルーチンが完了したときにリターンアドレスをコールスタックから pop する（そしてそのアドレスに制御を戻す）。呼び出されたサブルーチンがさらに別のサブルーチンを呼び出す場合も、リターンアドレスをコールスタックに push し、プログラムに書かれている通りに情報をスタックに積んだり下ろしたりする。コールスタックに割り当てられている領域を使い切ると「スタックオーバフロー」と呼ばれるエラーが発生する。あるサブルーチンに関する情報をコールスタックに載せることをワインド (winding)、逆にそれを削除することをアンワインド (unwinding) と呼ぶ。また、サブルーチン毎にコールスタックに格納する情報をスタックフレーム (Stack Frame) と呼ぶ。

1つの実行中のプログラム（より正確に言えばスレッド）には、1つのコールスタックが対応して存在する。本項では、コールスタックを単にスタックと呼ぶことがある。

高級言語では、コールスタックの詳細はプログラマからは見えない。関数のリストだけにアクセス可能で、スタックを構成しているメモリ自体にアクセスすることはできない。一方アセンブリ言語の多くでは、プログラマはスタックを操作する必要がある。プログラミング言語におけるスタックの詳細はコンパイラ、オペレーティングシステム、命令セットなどに依存する。

目次 1 コールスタックの機能 2 構造 3 使用法 3.1 呼び出し側処理 3.2 呼ばれた側の処理 3.3 復帰処理 3.4 アンワインド 4 セキュリティ 5 関連項目 6 外部リンク

[編集] コールスタックの機能

前述のように、コールスタックの第一の目的は以下の通りである。

• リターンアドレスの格納 - サブルーチンが呼び出されたとき、戻るべき命令のアドレスをどこかに記憶しておく必要がある。スタックを使ったリターンアドレスの格納は他の方法にはない利点がある。第一に、各タスクは対応するスタックを持っているので、サブルーチンは再入可能（リエントラント）、つまり複数のタスクが同時に同じサブルーチンを実行することが可能にできる。第二に、再帰呼び出しが可能となるという利点がある。関数自身は再帰的に呼び出されたとしても、リターンアドレスは呼び出される度に記憶しておかなればならない。この機能がスタックを使うと自動的にサポートされる。

言語、オペレーティングシステム、ハードウェア環境に依存するが、コールスタックはそれ以外の機能も持つことがある。そのような機能として以下のものがある。

• 局所データ格納域 - 多くのサブルーチンは局所変数（自動変数）の値を格納するメモリ領域を必要とする。局所変数とは実行中のサブルーチンでのみ使われる変数で、そのサブルーチンの処理が終われば値を必要としない。このためにスタックのトップを動かして空き領域を作り、局所変数に利用することができる。これは動的メモリ確保に比べると非常に高速に行える。サブルーチンが呼び出される度にスタック上の局所データの領域が確保される点に注意されたい。
• 引数受け渡し - サブルーチンには引数を必要とするものがある。引数は呼び出し側のコードが提供し、その引数をコールスタック上に置くことは珍しくない。一般に引数の個数が少なければ、プロセッサのレジスタが引数の受け渡しに使われる。しかし、引数の個数が利用可能なレジスタ数より多ければ、何らかのメモリ領域を使わざるを得ない。コールスタックはそのような値の受け渡しには最適で、サブルーチンの呼び出しの度に固有の引数が渡されるのに対して、コールスタックも呼び出しの度に固有の領域を与えられる。
• 評価スタック - 論理演算や数値演算のオペランドは多くの場合レジスタに置かれて処理される。しかし、式が複雑になるとレジスタだけでは収まりきらなくなり、何らかのメモリ領域が必要となる。そのようなオペランドのためのスタック（逆ポーランド記法の電卓に似ている）は評価スタック (evaluation stack)と呼ばれ、コールスタックを利用して実装することがある。
• 現在のインスタンスへのポインタ - C++のようなオブジェクト指向言語では、メソッド呼び出しの際にthisポインタを引数と共にコールスタックに格納する。thisポインタは呼び出されるメソッドに対応するオブジェクトのインスタンスを指している。thisポインタはオブジェクト指向言語のコンテキストの基本要素であり、現在のオブジェクトの持つプライベートデータへのアクセスを提供する。thisポインタはオブジェクト指向プログラミングとコールスタックを結びつけるものである。
• 他のリターンステータス - リターンアドレスだけでなく、環境によってはサブルーチンから復帰する際に戻さなければならないハードウェアやソフトウェアのステータスがあるかもしれない。例えば、特権レベル、例外処理情報、演算モードなどである。必要に応じてこれらもリターンアドレスのようにコールスタックに格納される。

典型的なコールスタックはリターンアドレス、局所データ、引数を格納する（これを「コールフレーム」と呼ぶ）。環境によってはコールスタックの機能に差異がある。例えばFORTH言語では、コールスタックにはリターンアドレスと局所変数のみが格納され（これをリターンスタックと呼ぶ）、引数は別のデータスタックに格納される。多くのFORTHの実装では浮動小数点数の引数を格納するための第三のスタックが存在する。

[編集] 構造

コールスタックはスタックフレームから構成される（アクティベーションレコードとも呼ばれる）。各スタックフレームは完了していないサブルーチン呼び出しに対応する。例えば、DrawSquareから呼び出されたDrawLineを現在実行中としたとき、コールスタックのトップ部分は下図のようになる。

スタックトップのスタックフレームは現在実行中のルーチンのためのものである。最も典型的な手法では、スタックフレームにはそのルーチンの局所変数領域、呼び出し側に戻るためのリターンアドレス、そのルーチンに渡された引数が格納される。フレーム内のメモリ領域はスタックポインタと呼ばれるレジスタを使ってアクセスされることが多い。スタックポインタはスタックのトップを指している。別の方法として、スタックポインタとは別のレジスタ（フレームポインタと呼ばれることが多い）を使うこともある。フレームポインタはフレームの中の決まった場所を指していて、例えばリターンアドレスが格納されている位置を指している。

スタックフレームは必ずしも同じサイズではない。サブルーチン毎に引数の個数も違うので、スタックフレームのサイズも異なる。ただし、同じサブルーチンを呼び出したときのスタックフレームは一般に同じサイズとなる。同様に局所変数領域もサブルーチンが違うとサイズが変わってくる。実際、言語によってはスタック上に動的にメモリを確保する機能を持っているので、そのような場合は同じサブルーチンを呼び出す度にフレームサイズも変わってくるし、そのサイズはコンパイル時にはわからない。そのような場合、スタックポインタではなくフレームポインタでアクセスする必要が生じる。というのは、スタックポインタからリターンアドレス格納位置までのオフセットがコンパイル時に判明しないからである。

多くのシステムでは、スタックフレーム内に前のフレームポインタレジスタの値を格納する場所がある。つまり呼び出し側ルーチンを実行していたときに使っていたフレームポインタの値である。例えば、上図のDrawLineのスタックフレーム内にDrawSquareが使っているフレームポインタの値を格納する場所があるということになる。その値はサブルーチン呼び出し時に格納され、復帰時に戻される。そのようなフィールドがスタックフレーム内の所定の位置にあると、コールスタックに積まれているスタックフレーム群を（さかのぼって）辿っていくことが可能となる。

場合によっては、スタックフレームはオーバーラップしていると見なすこともできる。オーバーラップしているのは、呼び出し側から呼び出されたルーチンに渡される引数の部分である。環境によっては呼び出し側はスタックに引数をpushして自身のスタックフレームを拡張し、その後に呼び出しを行う。また別の環境では、各サブルーチンは自身が呼び出すかもしれない別のサブルーチンへの引数の領域を予めスタックフレーム内に確保していることがある。この領域は outgoing arguments area あるいは callout area と呼ばれる。この手法ではコンパイラが呼び出す可能性のあるサブルーチンのうち最大の引数領域を必要とするものを予め求めて領域サイズを決定する。

[編集] 使用法

[編集] 呼び出し側処理

通常、サブルーチンを呼び出す側でのコールスタック処理は最小限になっている。呼び出すコードがあちこちに存在することを考慮すれば、こうすることでコードの増大を抑えることができる。実際の引数の値は呼び出し毎に固有なので呼び出し側で評価され、呼出規約に従ってスタックにpushされるかレジスタに置かれる。「Branch and Link」のような実際の呼び出し命令が制御をターゲットのサブルーチンに転送するために実行される。

[編集] 呼ばれた側の処理

呼ばれたサブルーチンでは、最初にサブルーチンプロローグと呼ばれるコードを実行する。そこで実際のコードを実行する前に行わなければならない細々とした処理を行う。

プロローグでは、一般に呼び出し命令が所定のレジスタに置いたリターンアドレスをコールスタックにpushする。同様に現在のスタックポインタかフレームポインタ（あるいは両方）をpushする。命令セットアーキテクチャによってはこれらが呼び出し命令の一部として実行され、そのような環境ではプロローグですべきことは無い。

フレームポインタを使っている場合、プロローグではフレームポインタに新たな値をセットする（スタックポインタの値を活用する）。局所変数の領域は必要に応じて徐々にスタックポインタを変化させて確保していく。

FORTH言語ではコールスタック（リターンスタック）を明示的にワインドすることができる。Scheme言語では「動的ワインド dynamic wind」という機能があり、スタック上に特殊なフレームをワインドすることができる。

[編集] 復帰処理

サブルーチンから復帰することができる状態になると、プロローグの逆のエピローグ処理が行われる。これは一般的には保存されていたレジスタの値（フレームポインタなど）をスタックフレームからリストアし、スタックポインタの値を変更してスタックフレーム全体をpopし、最後にリターンアドレスに分岐する命令を実行する。多くの呼出規約ではエピローグ処理でpopする範囲に元々の引数も含まれる。その場合、呼び出した側に戻ったときにすべきことは何もない。呼出規約によっては、引数部分のpopを呼び出し側の責任で行うものがある。

[編集] アンワインド

呼び出された関数から復帰するとスタックのトップにあったフレームがpopされ、戻り値が残される。

スタックは例外処理の際にもアンワインドされなければならない。例外をサポートするためには、スタックフレームにさらに例外ハンドラを示すエントリが必要となる。例外がスローされると、スタックはその例外を処理できる例外ハンドラが見つかるところまでアンワインドされる。Common Lispではスタックがアンワインドされたときに起きることを制御するunwind-protectという特殊演算子がある。

継続を適用する場合、スタックは一度アンワインドされ、再度ワインドされて実行を継続する。継続を実装する方法はこれだけではなく、明示的に複数のスタックを用意して継続するアプリケーションが単にそのスタックを起動して渡すべき値をワインドする。

[編集] セキュリティ

コード（リターンアドレス）とデータ（引数、戻り値、局所変数）がコールスタックに混在していることはセキュリティ上危険である。詳しくはバッファオーバーランおよびスタックを参照されたい。

[編集] 関連項目

• 動的メモリ確保
• 自動メモリ確保
• 呼出規約
• スタック
• バッファオーバーラン

[編集] 外部リンク

• Stack Frame Allocation on MSDN（英文）