Stack Overflow

スタックオーバーフローの最も一般的な原因は、過度に深い再帰または無限再帰であり、関数が自身を何度も呼び出すため、各呼び出しに関連付けられた変数と情報を格納するために必要なスペースがスタックに収まる量を超えてしまうことです。^{[ 2 ]}

以下はC言語における無限再帰の例です。

int foo () { return foo (); }

関数fooは、呼び出されると、スタックオーバーフローが発生するまで自身を呼び出し続け、その都度追加のスタック領域を割り当て、結果としてセグメンテーション違反が発生します。^{[ 2 ]}しかし、一部のコンパイラは末尾呼び出し最適化を実装しており、特定の種類の無限再帰（末尾再帰）がスタックオーバーフローなしで発生することを許容します。これは、末尾再帰呼び出しが追加のスタック領域を占有しないためです。^{[ 3 ]}

C コンパイラのオプションの中には、末尾呼び出し最適化を効果的に有効にするものがあります。たとえば、上記の単純なプログラムをgccでコンパイルすると-O1セグメンテーション違反が発生しますが、-O2またはを使用すると発生しません-O3。これは、これらの最適化レベルが-foptimize-sibling-callsコンパイラオプションを意味するためです。^{[ 4 ]} Schemeなどの他の言語では、すべての実装が言語標準の一部として末尾再帰を含める必要があります。^{[ 5 ]}

理論上は終了するものの、実際にはコールスタックバッファオーバーフローを引き起こす再帰関数は、再帰をループに変換し、関数引数を明示的なスタックに格納することで修正できます（暗黙的なコールスタックの使用ではなく）。これは、プリミティブな再帰関数のクラスがLOOP計算可能関数のクラスと等価であるため、常に可能です。C ++ライクな擬似コードで、次の例を考えてみましょう。

左側のような原始的な再帰関数は、常に右側のようなループに変換できます。

左上の例のような関数は、末尾呼び出し最適化をサポートする環境では問題ありません。しかし、これらの言語では、スタックオーバーフローを引き起こす可能性のある再帰関数を作成することは依然として可能です。以下の2つの単純な整数べき乗関数の例を考えてみましょう。

上記の2つのpow(base, exp)関数はどちらも同等の結果を計算しますが、左側の関数は末尾呼び出し最適化が不可能なため、スタックオーバーフローを引き起こしやすいです。実行中、これらの関数のスタックは次のようになります。

左側の関数はスタックにexp整数を格納し、再帰が終了して関数が1を返すときにその整数が乗算されることに注意してください。一方、右側の関数は常に3つの整数だけを格納すればよく、中間結果を計算して次の呼び出しに渡します。現在の関数呼び出し以外の情報を格納する必要がないため、末尾再帰オプティマイザは以前のスタックフレームを「破棄」でき、スタックオーバーフローの可能性を排除できます。

スタックオーバーフローのもう1つの主な原因は、スタックに収まる以上のメモリを割り当てようとする試み、例えば大きすぎるローカル配列変数を作成することです。このため、数キロバイトを超える配列はローカル変数としてではなく動的に割り当てることを推奨する著者もいます。 ^{[ 6 ]}

C言語における非常に大きなスタック変数の例：

void foo ( ) { double x [ 1048576 ] = {0} ; }

8バイト倍精度浮動小数点数を使用するC言語の実装では、宣言された配列は8メガバイトのデータを消費します。これがスタック上で使用可能なメモリ量（スレッド作成パラメータまたはオペレーティングシステムの制限によって設定される）を超える場合、スタックオーバーフローが発生します。

スタックオーバーフローは、特定のプログラムの実効スタックサイズを減少させるものによって悪化します。たとえば、同じプログラムをマルチスレッドなしで実行すると問題なく動作するかもしれませんが、マルチスレッドを有効にするとすぐにプログラムがクラッシュします。これは、スレッドを持つほとんどのプログラムは、スレッドをサポートしていないプログラムよりもスレッドあたりのスタック領域が少ないためです。カーネルは一般的にマルチスレッドであるため、カーネル開発の初心者は、再帰アルゴリズムや大きなスタックバッファの使用を避けるよう推奨されます。^{[ 7 ]}