コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

スタックオーバーフロー

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

スタックオーバーフロー (: stack overflow) は、コンピュータプログラムにおいて、コールスタック領域の限界を超えたデータプッシュにより発生する、バッファオーバーフローの一種である。スタックバッファオーバーフロー (: stack buffer overflow) とは別の概念である。

概要

[編集]

一般的なプログラムの実行環境では、サブルーチン(関数、プロシージャ、あるいはメソッドとも)の呼び出しに関する情報を格納するためのスタックメモリ領域(コールスタック)が確保される。サブルーチン呼び出しのたびにデータがスタックに積まれ(プッシュ)、サブルーチンが終わって制御フローが呼び出し元に戻るとスタックからデータが降ろされる(ポップ)。また、コールスタックはサブルーチン内でのみ使用されるローカル変数を確保するための領域でもある。オペレーティングシステムや実行オプションにもよるが、コールスタックに格納できる情報量には上限がある。コールスタックに蓄積されるデータ量が限界を超えるとスタックは「オーバーフロー」し、未定義動作を引き起こす。オペレーティングシステムにもよるが、プログラム側で対策をとっていなければ通常はプロセスがクラッシュしてしまう。ただし、スタックオーバーフローの原因となりうるコードパターンは比較的限定されている。

スタックオーバーフローの発生原因のうち、最も多いのはサブルーチンの再帰呼び出しによる無限ループ(無限再帰)である。また、ソースコードの設計上は無限再帰ではなく、終了条件を決めて有限回数で打ち切るような有限再帰になっていたとしても、再帰呼び出しの階層数が深すぎると実行環境におけるコールスタックの上限を超えてしまい、スタックオーバーフローとなってしまう場合もある。ただし、末尾最適化を実装したプログラミング言語では、末尾再帰の形で書かれたサブルーチンをループへ展開することができ、スタックオーバーフローは起こらなくなる。フラットなループ処理に変換されることで、再帰呼び出しによりスタックを消費することが無くなるからである。なお、再帰ではないサブルーチン呼び出しであっても、呼び出し階層数が深すぎる場合には、やはりスタックオーバーフローが起こりうる。

次によくある原因としては、スタック上に巨大な配列を確保しようとすることである。コールスタックに格納できる情報量には上限があるため、巨大なサイズのローカル変数を定義するのではなく、ヒープ領域などを明示的に利用すべきである。配列1つのサイズがそれほど大きくなくても、再帰呼び出しなどでサブルーチンの呼び出し階層が深くなることによってコールスタックを食いつぶし、スタックオーバーフローを引き起こすこともある。

C/C++ での例

[編集]

再帰による無限ループ

[編集]
/* 関数の戻り値が int の場合、C言語では前方宣言や前方定義がなくてもコンパイル可能だが、C++では前方宣言あるいは前方定義が必要。 */
int g(void);

int f(void) {
    return g();
}

int g(void) {
    return f();
}

関数 f() は関数 g() を呼び出しているが、g() もやはり f() を呼び出している。交互の呼び出しは終わることがなく、最終的にはスタックオーバーフローが発生する。以下のような終了条件のない自己再帰も無限再帰となる。

int foo(void) {
    return foo();
}

巨大な配列をスタックに配置した場合

[編集]

C/C++において、関数内で定義されるローカル変数(ブロックスコープを持つ変数)は既定で(staticキーワードで修飾しない限り)自動変数となり、ブロックを抜けることで自動的に変数の寿命が尽きてメモリが解放される自動記憶域期間を持つ[1]。言語仕様では自動変数の実装形態について特に規定されていないが、一般的にはコールスタックを利用して実装される。

システムに実装されているメインメモリの容量にかかわらず、各プログラムのスタック領域のサイズはスレッドごとに既定でせいぜい数MiB程度[2][3][4][5][6][7]であり、大容量の配列を確保するのには向いていない。コンパイルオプションやスレッドの起動時オプションなどでスタックサイズの既定値を変更できる環境もあるが、スタックサイズを増やすにつれてプロセス内で起動可能なスレッドの最大数が減少することになる。

#include <stdio.h>
int main(void) {
    int ary[1000 * 1000 * 1000]; /* 配列が大きすぎる */
    printf("Hello!\n"); /* &"Hello!\n" のプッシュがスタックオーバーフローとなる */
}

この場合は、

#include <stdio.h>
int ary[1000 * 1000 * 1000];
int main(void) {
    printf("Hello!\n");
}

または

#include <stdio.h>
int main(void) {
    static int ary[1000 * 1000 * 1000];
    printf("Hello!\n");
}

のように配列を静的領域に移動するか、あるいは malloc などを使ってヒープ領域に動的確保すればスタックオーバーフローは回避できる。ただし32ビット環境ではアドレス空間の上限が4 GiBであるため、上記のように巨大な配列を静的確保しようとするとプログラムの起動が失敗してしまう可能性がある。通例、システムが利用できる空きメモリの量は必ずしも定かではないので、64ビット以上の環境であっても、実行時の動的メモリ確保と成否チェックを行なうことが望ましい。

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    /* malloc() 関数が失敗した場合は NULL ポインタが返却されるため、実際にメモリ領域を利用する前に NULL チェックをする必要がある */
    int *ary = (int *)malloc(sizeof(int) * (size_t)(1000 * 1000 * 1000));
    printf("Hello!\n");
    /* NULL に対して free() 関数を実行しても何も起こらないことが C/C++ 規格で保証されているため、NULL チェックは不要 */
    free(ary);
}

JavaC#/VB.NETのような仮想マシンベースの実行環境を持つ言語では、OSではなく仮想マシンによって管理されているヒープ領域を使うことによって、動的メモリ確保のオーバーヘッドを低減している。これらの言語では、通常の(言語組み込みの)配列は常にヒープ領域に割り当てられるため、実行時にメモリ不足の例外をスローすることはあっても、スタックオーバーフローを引き起こすことはない。一方、C/C++の動的メモリ確保はそのような言語と比べてオーバーヘッドが大きいため、あらゆる配列をヒープに確保しようとするのは大きな速度損失を伴う。Microsoft Visual C++のランタイムライブラリでは、一定のしきい値を基準として、要求されるメモリサイズに応じてスタックとヒープを使い分ける_malloca()関数も用意されている[8]

脚注

[編集]

関連項目

[編集]