読者です 読者をやめる 読者になる 読者になる

をるふちゃんのブログ

C++ | DirectX | VC++

スタックをオーバーフローさせる話 【初心者C++er Advent Calendar 2016 - 7日目】

ごめんなさい

エチルアルコールが血管を駆け巡ってる状態の深夜テンションでAdC書くって言って忘れてました。

おことわり

当記事はWindowsのことしか考えていません。
また実行可能ファイルについてはPEフォーマットに基づいて記事を書いています。
同様にメモリ上の構造についても他OSについては無知なので悪しからず。

動機

このツイートの関連で再帰を説明することになるなどしました。 (で、見事に忘れてたわけですが)、再帰について記事を書こうとしたら なぜかメモリの話になってしまいました 、すみません。

再帰とは何か

何かの対象をそれ自体で定義することを再帰(recursion)と呼びます。コンピュータ言語に当てはめると、これは関数がその関数自身を呼び出すことを意味します。 (「独習C 第4版(翔泳社)」より)

関数を書くとき自分自身を呼び出すようにしたものを再帰関数と呼びます。
また、以下のようにお互いがお互いを呼び出すような関数のことを相互再帰と呼んだりします 。

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

これら再帰関数では必ずいづれかのタイミングで関数がreturnするよう注意してください。
でないとスタックオーバーフローを起こしてプログラムが異常終了します。

戻ってこない再帰プログラムは当然「意図しない」動作すなわちバグということになりますが、スタックとやらを溢れさせると何が起こるのか。
また、再帰以外でもたまに大きなサイズの配列を確保しようとしてこのバグを生むことがありますね。そもそも、

スタックオーバーフローとは何か???

ということで以下お付き合いください。

プログラムの実行について

PEフォーマットに基づいた実行可能ファイル(.exe/.dll)は大まかに言うと、Windows上で実行するために必要な情報(ファイルヘッダ)と、メモリにロードされ実行されるデータ(プログラム + 変数などのデータ)で成り立っています。
この後者がメモリにロードされてプログラムは動いているわけですが、これは当然ビットの羅列である機械語となっています。
それを便宜上16進数で表すと4bitずつのまとまりになるわけですが、これをニブルと言います。
この、ニブルを2つ組み合わせることでIntel 8086系統と呼ばれる今出回っているほとんどのCPUに命令を行うことができます(そのため8bitのかたまりを特別に「バイト」と呼んでいます)。
Intel® 64 and IA-32 Architectures Software Developer Manuals

当然、これらの命令はCPUと、レジスタというCPU内の極小かつ最速の記憶装置を扱うものですので、高度な構文は用意されていません。
もちろんループ構文も関数という概念もありません。代わりにGotoに似たいくつかの構文を組み合わせて実現しています。

おまけのメモリの話

前述したように1命令が1byteだからか、メモリは1ブロック=1byte=8bitとなっています。
32bitアプリケーションにおいてはメモリアドレスは32bit(4byte/16進八桁)で管理しているため、その最大値4294967295byte≒4GBまでしか(仮想/物理)メモリを扱うことができません。

カーネルの使用領域を含めて考えたとき、32bit版OSにおいて「およそ3GBが限界でこれ以上は認識しない」というのはこれが原因です。

仮想メモリ

機械語では基本的にはメモリに読み込まれた命令を上から下に順に実行を行います。
条件分岐は特定のメモリアドレスに実行を移動し、必要に応じて戻る(再度移動を行う)というかたちで実現しています。

しかし実際のコンピュータにおいてはそれらプログラムのデータがメモリのどこに読み込まれるかわかりません。
このため多くのOSでは仮想メモリという仕組みを利用しています。 ざっくりと言うと、プログラムは皆0x00400000を起点として動作することにして、全てのプログラムには物理搭載メモリと同じだけのメモリ領域を与えるという事になっています。仮想メモリと物理メモリの対照はOSに任せ、実際には不連続なメモリを効率良く使うことができるようになっています。この仕組みではメモリが溢れることもありえますが、必要に応じてスワップ(HDDやSSDなどをメモリとして扱う)するなどすることになっています。
※ なぜ0x400000なのか?予約領域ということで保険をかけたのだろう…。深い意味はないのかもしれない。

ヒープとスタック

スタックは後述しますが、事前にメモリ領域を確保した上で、整然とデータを蓄積・解放することができるので高速にアクセスができます。
その性質上、仮想メモリの末尾の方にスタック領域としてまとめて配されるようになっているようです。

一方ヒープは任意のサイズのデータを任意の順番で確保・解放することができます(プログラムの命令ではない部分のデータの保管に向いている)。
newしたときはこちらの方式で確保が行われるのでメモリの限界までデータを確保できるでしょう(現実的には物理メモリの動作を考えたときの制約がありますが)。

コールスタック(いわゆるスタック)

コールスタックとは実行中の関数に関する情報を格納しておく(メモリ上の)部分を指して言います。
スタックという構造をご存じの方にはお分かりいただけると思いますが、これは積み重なるようにデータを格納し、最後に入れたものが先に取り出されます。
関数の呼び出しも同じように、関数が呼ばれたら、前の関数はそのまま置いておいて新たに(重ねるようにして)呼び出された関数を実行します。returnして関数の実行が終わったらその階層のことは忘れて、何事もなかったかのようにして先の関数の続きに制御が移る、というこの制御の移り変わりはまさに「後入れ先出し(LIFO……Last In First Out)」とイメージできます。

このコールスタックは関数が呼ばれるごとに「積み重なるよう」に情報が蓄積していきます。
まずはどんな情報が扱われるのか具体的に見ていきましょう。

リターンアドレスの格納

先ほど、機械語における条件分岐はアドレスの移動で実現すると言いました。C,C++の関数に当たる部分も同様にアドレスの移動でそれを実現していますが、関数の実行が終了して続きを実行するために呼び出し元のどこに戻ればいいのか覚えておかねばなりません(どこから呼ばれたのか覚えておくということ)。 これをリターンアドレスと言い、呼ばれるごとに変わるのでスタックに格納されます。

ローカル変数・引数の格納

スタックは後入れ先出しと言いました。このためスタックに最後に入れたデータ領域を拡張するのは容易くできます。つまり現在実行中の関数についてはスタックの限界を超えない限り高速にメモリを確保することができます。
※ヒープでは、物理メモリ上の使える位置を探してからそれを他のプログラムが使わないような手続きを行ったあとに確保されるので手間がかかります 。

thisポインタ

各メソッドのインスタンスを指すことでメンバにアクセスすることができます。

スタックのサイズ (ここ重要)

スタック領域はVisual Studioのデフォルトではわずか1MB程度(0x000FF000)に設定されているため、できるだけヒープでメモリを確保してそこにデータを格納するべきです。
ちなみに1MBの大きさについてですが、int(4bitと仮定)にしておよそ25万要素程度です。
競技プログラミングにおいて、ローカル変数を避けヒープで確保されるグローバル変数を多用するのはこのためです。

また、同様に、関数を極めて大量に呼び出した場合、これ以上関数が呼べなくなることがあります。
これがスタックオーバーフロー という事象の正体となります。

f:id:wolf_cpp:20161210065301p:plain

テスト

/*
関数 foo は第一引数から第二引数までの整数を出力します。
*/
#include <iostream>

void foo( const int& i, const int& j );

void foo( const int& i, const int& j ) {
    std::cout << i << std::endl;
    if ( i > j ) {
        foo( i-1, j );
    } else if ( i < j ) {
        foo( i+1, j );
    } else {
        std::cout << std::endl;
    }
    return;
}

このコードで適当に大きな値をセットして再帰呼び出しをテストしてみたところ、4140回目あたりの呼び出しでスタックオーバーフローを起こしました。
アセンブラによるとコールスタック1回分のサイズはおおよそ200byte弱程度でした。
案外脆いものですね。

f:id:wolf_cpp:20161210065407p:plain

余談

Visual Studioのリンカオプションでスタックのサイズの設定ができました
試しに100倍に設定してぶん回してみましたが狙い通りしっかりと動いてくれました。

おしまい

遅れてすみませんが、初心者C++er AdC 12/7の記事は以上とします。次はバンビちゃん@実際無職【初心者C++er Advent Calendar 2016 8日目】関数テンプレートと関数オブジェクトです。