Loading article…
コンピュータサイエンスにおいて、コールスタックとは、コンピュータプログラムのアクティブなサブルーチンとインラインブロックに関する情報を格納するスタックデータ構造のことです。このタイプのスタックは、実行スタック、プログラムスタック、制御スタック、ランタイムスタック、マシンスタックとも呼ばれ、しばしば単に「スタック」と略されます。コールスタックの維持管理はほとんどのソフトウェアの適切な動作にとって重要ですが、その詳細は通常、高水準プログラミング言語では隠蔽され、自動的に行われます。多くのコンピュータ命令セットには、スタックを操作するための特別な命令が用意されています。
コールスタックはいくつかの関連する目的で使用されますが、主な理由は、各アクティブなサブルーチンが実行を終えたときに制御を戻すポイントを追跡することです。アクティブなサブルーチンとは、呼び出されたものの実行が完了しておらず、実行が完了した後に呼び出しポイントに制御が戻されるサブルーチンのことです。このようなサブルーチンの起動は任意のレベルにネストされる可能性があり（再帰は特殊なケースです）、そのためスタック構造が存在します。たとえば、サブルーチンが4つの異なる場所から別のDrawSquareサブルーチンを呼び出す場合DrawLine、DrawLine実行が完了したときにどこに戻るべきかを知る必要があります。これを実現するために、ジャンプ先の命令の次のアドレス、つまり戻りアドレスが、各呼び出しの一部としてコールスタックの最上位にプッシュされます。DrawLine
コールスタックはスタックとして構成されているため、プロシージャの呼び出し元、またはそのプロシージャのプロローグは戻りアドレスをスタックにプッシュし、呼び出されたサブルーチンは終了時にコールスタックから戻りアドレスをプル（ポップ）して、そのアドレスに制御を移します。同様に、インラインブロックのプロローグはスタックフレームをプッシュし、エピローグはそれをポップします。呼び出されたサブルーチンがさらに別のサブルーチンを呼び出す場合、別の戻りアドレスがコールスタックにプッシュされ、プログラムの指示に従って情報がスタックに積み上げられたり、スタックから取り出されたりします。プッシュによってコールスタックに割り当てられた領域がすべて消費されると、スタックオーバーフローと呼ばれるエラーが発生し、通常はプログラムがクラッシュします。ブロックまたはサブルーチンのエントリをコールスタックに追加することを「ワインディング」、エントリを削除することを「アンワインディング」と呼ぶことがあります。
実行中のプログラム（より正確には、プロセスの各タスクまたはスレッド）には通常、コールスタックが1つだけ関連付けられていますが、シグナル処理や協調マルチタスク（ setcontextなど）のために追加のスタックが作成される場合もあります。この重要なコンテキストには1つしかないため、スタック（暗黙的に「タスクの」スタック）と呼ぶことができます。ただし、 Forthプログラミング言語では、データスタックまたはパラメータスタックはコールスタックよりも明示的にアクセスされ、一般的にスタックと呼ばれます（下記参照）。
高級プログラミング言語では、コールスタックの詳細はプログラマーから隠蔽されているのが一般的です。プログラマーは関数セットにのみアクセスでき、スタック上のメモリ自体にはアクセスできません。これは抽象化の一例です。一方、ほとんどのアセンブリ言語では、プログラマーがスタックの操作に関与する必要があります。プログラミング言語におけるスタックの実際の詳細は、コンパイラ、オペレーティングシステム、および使用可能な命令セットによって異なります。
前述のとおり、コールスタックの主な目的は、戻りアドレスを格納することです。サブルーチンが呼び出されると、呼び出し元のルーチンが後で再開できる命令の位置（アドレス）をどこかに保存する必要があります。戻りアドレスをスタックに保存することには、呼び出されたサブルーチンの開始前や他の固定された場所に戻すなど、他の呼び出し規約に比べて重要な利点があります。1つは、各タスクが独自のスタックを持つことができるため、サブルーチンがスレッドセーフ、つまり、異なるタスクが異なる処理を同時に実行できるということです。もう1つの利点は、再入可能性を提供することで、再帰が自動的にサポートされることです。関数が再帰的に自身を呼び出す場合、関数がアクティブになるたびに戻りアドレスを保存し、後で関数のアクティブから戻るために使用する必要があります。スタック構造は、この機能を自動的に提供します。
言語、オペレーティングシステム、マシン環境によっては、コールスタックは次のような追加の目的にも使用される場合があります。
this一般的なコールスタックは、戻りアドレス、ローカル変数、およびパラメータ（コールフレームと呼ばれる）に使用されます。環境によっては、コールスタックに割り当てられる関数の数が多い場合も少ない場合もあります。たとえば、 Forth プログラミング言語では、通常、戻りアドレス、カウントされたループパラメータとインデックス、および場合によってはローカル変数のみがコールスタック（この環境では戻りスタックと呼ばれます）に格納されますが、呼び出しと戻りの必要性が尊重される限り、特別な戻りスタック処理コードを使用して、任意のデータを一時的にそこに配置できます。パラメータは通常、別のデータスタックまたはパラメータスタックに格納されます。Forth の用語では、コールスタックが存在するにもかかわらず、通常はより明示的にアクセスされるため、スタックと呼ばれます。一部の Forth には、浮動小数点パラメータ用の 3 番目のスタックもあります。
DrawSquareサブルーチン（青色で表示）が呼び出された後、上方向に伸びるスタックのコールスタックレイアウト。DrawLine（緑色で表示）は現在実行中のルーチンである。コールスタックはスタックフレーム（アクティベーションレコードまたはアクティベーションフレームとも呼ばれる）で構成されます。これらは、サブルーチンの状態情報を含む、マシン依存およびABI依存のデータ構造です。各スタックフレームは、まだ戻り値で完了していないサブルーチンの呼び出しに対応します。[ 1 ]スタックの最上部のスタックフレームは、現在実行中のルーチン用です。たとえば、DrawLineサブルーチンによって呼び出されたという名前のサブルーチンが現在実行中の場合DrawSquare、コールスタックの最上部は、隣の図のように配置される可能性があります。
このような図は、最上位の位置、つまりスタックの成長方向が理解されていれば、どちらの方向にも描くことができます。アーキテクチャによって、コールスタックが上位アドレスに向かって成長するか下位アドレスに向かって成長するかが異なるため、図の論理は慣例的なアドレス指定方法に依存しません。
ルーチンは、スタックの最上位にあるフレームでアクティブに実行されている間、必要に応じてフレーム内の情報にアクセスできます。[ 2 ]スタックフレームには通常、少なくとも以下の項目が含まれます（プッシュされた順序）。
DrawLineスタックフレーム内の、のコードへのアドレスDrawSquare）がレジスタではなくコールスタックに保存されている場合。スタック フレームのサイズが異なる場合（異なる関数間、または特定の関数の呼び出し間など）、スタックからフレームをポップしても、スタック ポインタが固定的に減少するわけではありません。関数が戻ると、スタック ポインタは、関数が呼び出される直前のスタック ポインタの値であるフレーム ポインタに復元されます。各スタック フレームには、すぐ下のフレームの最上位へのフレーム ポインタが含まれています。スタック ポインタは、すべての呼び出しで共有される可変レジスタです。関数の特定の呼び出しのフレーム ポインタは、関数が呼び出される前のスタック ポインタのコピーです。[ 3 ]
フレーム内の他のすべてのフィールドの位置は、スタックポインタの負のオフセットとしてフレームの最上部を基準に定義することも、下のフレームの最上部を基準としてフレームポインタの正のオフセットとして定義することもできます。フレームポインタ自体の位置は、必然的にスタックポインタの負のオフセットとして定義されなければなりません。
ほとんどのシステムでは、スタックフレームには、呼び出し元が実行中に保持していたフレームポインタレジスタの以前の値を格納するフィールドがあります。たとえば、スタックフレームには、 (上の図には示されていませんが)DrawLineを使用するフレームポインタ値を保持するメモリ位置がありますDrawSquare。この値は、サブルーチンへのエントリ時に保存されます。スタックフレーム内の既知の場所にこのようなフィールドがあると、コードは現在実行中のルーチンのフレームの下にある各フレームに順次アクセスでき、また、ルーチンが戻る直前にフレームポインタを呼び出し元のフレームに簡単に復元できます。
ネストされたサブルーチンをサポートするプログラミング言語では、呼び出しフレームに、呼び出し先を最も密接にカプセル化するプロシージャの最新のアクティベーションのスタックフレーム、つまり呼び出し先の直近のスコープを指すフィールドがあります。これはアクセスリンクまたは静的リンクと呼ばれ（動的呼び出しや再帰呼び出しの際に静的ネストを追跡するため）、ルーチン（およびルーチンが呼び出す可能性のある他のルーチン）に、ネストレベルごとにカプセル化ルーチンのローカルデータへのアクセスを提供します。アーキテクチャ、コンパイラ、または最適化ケースによっては、各囲みレベル（直近の囲みレベルだけでなく）ごとに 1 つのリンクを格納するため、浅いデータにアクセスする深くネストされたルーチンは複数のリンクをたどる必要がありません。この戦略はしばしば「ディスプレイ」と呼ばれます。[ 4 ]
内部関数がカプセル化内の（定数でない）ローカルデータにアクセスしない場合、例えば引数と戻り値のみを介して通信する純粋関数のように、アクセスリンクは最適化によって削除できます。Electrologica X8や、やや後のBurroughs大型システムなどの一部の歴史的なコンピュータには、ネストされた関数をサポートするために特別な「表示レジスタ」がありましたが、ほとんどの現代のマシン（普及しているx86など）のコンパイラは、必要に応じてスタック上にポインタ用の数ワードを予約するだけです。
場合によっては、サブルーチンのスタックフレームと呼び出し元のスタックフレームは重複していると考えることができます。重複部分は、呼び出し元から呼び出し先へパラメータが渡される領域です。環境によっては、呼び出し元が各引数をスタックにプッシュしてスタックフレームを拡張し、呼び出し先を呼び出します。また別の環境では、呼び出し元はスタックフレームの最上部に、呼び出し先のサブルーチンに渡す引数を格納するための事前割り当て領域を持っています。この領域は、出力引数領域または呼び出し領域と呼ばれることもあります。この方式では、呼び出し先のサブルーチンが必要とする最大のサイズがコンパイラによって計算されます。
通常、サブルーチン呼び出し箇所で必要となるコールスタック操作は最小限です（これは、各サブルーチンに対して呼び出し箇所が複数存在する可能性があるため、都合が良いと言えます）。実際の引数の値は、特定の呼び出しに固有のものであるため、呼び出し箇所で評価され、使用される呼び出し規約に従ってスタックにプッシュされるか、レジスタに格納されます。その後、「分岐とリンク」などの実際の呼び出し命令が実行され、ターゲットサブルーチンのコードに制御が移ります。
呼び出されたサブルーチンでは、最初に実行されるコードは通常、サブルーチンのプロローグと呼ばれます。これは、ルーチンのステートメントのコードが開始される前に必要な準備作業を行うためです。
サブルーチンを呼び出す命令が戻りアドレスをスタックにプッシュするのではなくレジスタに格納する命令セットアーキテクチャの場合、プロローグは通常、戻りアドレスの値をコールスタックにプッシュすることで保存しますが、呼び出されたサブルーチンが他のルーチンを呼び出さない場合は、その値をレジスタに残すことがあります。同様に、現在のスタックポインタやフレームポインタの値もプッシュされる場合があります。
フレームポインタを使用する場合、プロローグでは通常、スタックポインタからフレームポインタレジスタの新しい値を設定します。その後、スタックポインタを段階的に変更することで、ローカル変数用のスタック領域を割り当てることができます。
Forthプログラミング言語では、コールスタック（Forthでは「リターンスタック」と呼ばれる）を明示的に巻き戻すことができる。
サブルーチンが戻り値を返す準備が整うと、プロローグの手順を元に戻すエピローグが実行されます。通常、エピローグではスタックフレームから保存されたレジスタ値（フレームポインタ値など）が復元され、スタックポインタ値を変更してスタックフレーム全体がスタックからポップされ、最後に戻りアドレスの命令に分岐します。多くの呼び出し規約では、エピローグによってスタックからポップされる項目には元の引数値が含まれるため、呼び出し元がそれ以上のスタック操作を行う必要は通常ありません。ただし、一部の呼び出し規約では、戻り後にスタックから引数を削除するのは呼び出し元の責任となります。
呼び出された関数から戻ると、スタックの最上位フレームがポップされ、場合によっては戻り値が残ります。プログラムの別の場所で実行を再開するために、スタックから 1 つ以上のフレームをポップするより一般的な操作はスタックアンワインドと呼ばれ、例外処理などに使用される非ローカル制御構造が使用される場合に実行する必要があります。この場合、関数のスタックフレームには、例外ハンドラを指定する 1 つ以上のエントリが含まれています。例外がスローされると、スローされた例外のタイプを処理 (キャッチ) する準備ができているハンドラが見つかるまで、スタックがアンワインドされます。
一部の言語には、一般的な巻き戻しを必要とする他の制御構造があります。Pascalでは、グローバルgoto文を使用して、ネストされた関数から以前に呼び出された外側の関数に制御を移すことができます。この操作では、スタックを巻き戻し、適切なコンテキストを復元して、囲んでいる外側の関数内のターゲット ステートメントに制御を移すために必要な数のスタック フレームを削除する必要があります。同様に、C には、非ローカル goto として機能する関数があります。Common setjmpLisplongjmpではunwind-protect、特殊演算子を使用することで、スタックが巻き戻されたときに何が起こるかを制御できます。
継続を適用すると、スタックは（論理的に）巻き戻され、その後、継続のスタックで巻き戻されます。継続を実装する方法はこれだけではありません。たとえば、複数の明示的なスタックを使用すると、継続の適用は単にそのスタックをアクティブにして、渡す値を巻き戻すだけで済みます。Schemeプログラミング言語では、継続が呼び出されたときに、制御スタックの「巻き戻し」または「巻き戻し」時に、任意のサンクを指定されたポイントで実行できます。
プログラムの実行中にコールスタックを検査できる場合があります。プログラムの記述方法やコンパイル方法によっては、スタック上の情報を使用して中間値や関数呼び出しのトレースを特定できます。これは、きめ細かい自動テストの生成[ 5 ]や、 RubyやSmalltalkなどの場合における第一級継続の実装に使用されています。例として、GNUデバッガ（GDB）は、実行中だが一時停止しているCプログラムのコールスタックを対話的に検査する機能を実装しています[ 6 ] 。
コールスタックの定期的なサンプリングは、プログラムのパフォーマンスをプロファイリングする際に役立ちます。なぜなら、サブルーチンのアドレスがコールスタックのサンプリングデータに何度も出現する場合、それはコードのボトルネックになっている可能性が高く、パフォーマンスの問題がないか調査する必要があるからです。
自由ポインタやチェックされない配列書き込みを持つ言語（C言語など）では、コードの実行に影響を与える制御フローデータ（戻りアドレスや保存されたフレームポインタ）と単純なプログラムデータ（パラメータや戻り値）がコールスタック内で混在するとセキュリティリスクとなり、最も一般的なバッファオーバーフローであるスタックバッファオーバーフローによって悪用される可能性があります。
このような攻撃の一つは、任意の実行可能コードでバッファを1つ満たし、その後、このバッファまたは他のバッファをオーバーフローさせて、実行可能コードを直接指す値で戻りアドレスを上書きするというものです。その結果、関数が戻ると、コンピュータはそのコードを実行します。この種の攻撃はW^Xでブロックできますが、同様の攻撃は W^X 保護が有効になっていても成功する可能性があります。これには、libc への戻り攻撃や、戻り指向プログラミングから発生する攻撃などが含まれます。Forth プログラミング言語の場合のように、配列を戻りスタックとは完全に別の場所に格納するなど、さまざまな対策が提案されています。[ 7 ]