Manhattan life

A typical stack frame Figure 1 on the right is what a typical stack frame might look like. In these diagrams, the stack grows upward and smaller numbered memory addresses are on top. This would be the contents of the stack if we have a function foo with the prototype: int foo (int arg1, int arg2, int arg3) ; and foo has two local int variables. (We are assuming here that sizeof(int) is 4 bytes). The stack would look like this if say the main function called foo and control of the program is still inside the function foo. In this situation, main is the "caller" and foo is the "callee". The ESP register is being used by foo to point to the top of the stack. The EBP register is acting as a "base pointer". The arguments passed by main to foo and the local variables in foo can all be referenced as an offset from the base pointer. The convention used here is that the callee is allowed to mess up the values of the EAX, ECX and EDX registers before returning. So, if the caller wants to preserve the values of EAX, ECX and EDX, the caller must explicitly save them on the stack before making the subroutine call. On the other hand, the callee must restore the values of the EBX, ESI and EDI registers. If the callee makes changes to these registers, the callee must save the affected registers on the stack and restore the original values before returning. Parameters passed to foo are pushed on the stack. The last argument is pushed first so in the end the first argument is on top. Local variables declared in foo as well as temporary variables are all stored on the stack. Return values of 4 bytes or less are stored in the EAX register. If a return value with more than 4 bytes is needed, then the caller passes an "extra" first argument to the callee. This extra argument is address of the location where the return value should be stored. I.e., in C parlance the function call: x = foo(a, b, c) ; is transformed into the call: foo(&x, a, b, c) ; Note that this only happens for function calls that return more than 4 bytes. Let's go through a step-by-step process and see how a stack frame is set up and taken down during a function call.

ESP ==> . . .     Callee saved registers EBX, ESI & EDI (as needed)     temporary storage     local variable #2   [EBP - 8]   local variable #1   [EBP - 4]   EBP ==> Caller's EBP   Return Address   Argument #1   [EBP + 8]   Argument #2   [EBP + 12]   Argument #3   [EBP + 16]   Caller saved registers EAX, ECX & EDX (as needed)   . . .     Fig. 1

The caller's actions before the function call

ESP ==>		Return Address
		Arg #1 = 12
		Arg #2 = 15
		Arg #3 = 18
		Caller saved registers EAX, ECX & EDX (as needed)
EBP ==>		. . .
		Fig. 2

First, main pushes the contents of the registers EAX, ECX and EDX onto the stack. This is an optional step and is taken only if the contents of these 3 registers need to be preserved.

Next, main pushes the arguments for foo one at a time, last argument first onto the stack. For example, if the function call is:

     a = foo(12, 15, 18) ;

        push    dword 18 
        push    dword 15
        push    dword 12

        call    foo

Figure 2 shows the contents of the stack after the call instruction. The red line in Figure 2 and in subsequent figures indicates the top of the stack prior to the instructions that initiated the function call process. We will see that after the entire function call has finished, the top of the stack will be restored to this position.

The callee's actions after function call

When the function foo, the callee, gets control of the program, it must do 3 things: set up its own stack frame, allocate space for local storage and save the contents of the registers EBX, ESI and EDI as needed. So, first foo must set up its own stack frame. The EBP register is currently pointing at a location in main's stack frame. This value must be preserved. So, EBP is pushed onto the stack. Then the contents of ESP is transferred to EBP. This allows the arguments to be referenced as an offset from EBP and frees up the stack register ESP to do other things. Thus, just about all C functions begin with the two instructions: push ebp mov ebp, esp The resulting stack is shown in Figure 3. Notice that in this scheme the address of the first argument is 8 plus EBP, since main's EBP and the return address each takes 4 bytes on the stack.

ESP=EBP => main's EBP   Return Address   Arg #1 = 12   [EBP + 8]   Arg #2 = 15   [EBP + 12]   Arg #3 = 18   [EBP + 16]   Caller saved registers EAX, ECX & EDX (as needed)         Fig. 3

In the next step, foo must allocate space for its local variables. It must also allocate space for any temporary storage it might need. For example, some C statements in foo might have complicated expressions. The intermediate values of the subexpressions must be stored somewhere. These locations are usually called temporary, because they can be reused for the next complicated expression. Let's say for illustration purposes that foo has 2 local variables of type int (4 bytes each) and needs an additional 12 bytes of temporary storage. The 20 bytes needed can be allocated simply by subtracting 20 from the stack pointer: sub esp, 20 The local variables and temporary storage can now be referenced as an offset from the base pointer EBP. Finally, foo must preserve the contents of the EBX, ESI and EDI registers if it uses these. The resulting stack is shown in Figure 4. The body of the function foo can now be executed. This might involve pushing and popping things off the stack. So, the stack pointer ESP might go up and down, but the EBP register remains fixed. This is convenient because it means we can always refer to the first argument as [EBP + 8] regardless of how much pushing and popping is done in the function. Execution of the function foo might also involve other function calls and even recursive calls to foo. However, as long as the EBP register is restored upon return from these calls, references to the arguments, local variables and temporary storage can continue to be made as offsets from EBP.

ESP ==> Callee saved registers EBX, ESI & EDI (as needed)     temporary storage     [EBP - 20]   local variable #2   [EBP - 8]   local variable #1   [EBP - 4]   EBP==> main's EBP   Return Address   Arg #1 = 12   [EBP + 8]   Arg #2 = 15   [EBP + 12]   Arg #3 = 18   [EBP + 16]   Caller saved registers EAX, ECX & EDX (as needed)         Fig. 4

The callee's actions before returning

ESP ==>		Arg #1 = 12
		Arg #2 = 15
		Arg #3 = 18
		Caller saved registers EAX, ECX & EDX (as needed)
EBP ==>		. . .
		Fig. 5

Secondly, foo must restore the values of the EBX, ESI and EDI registers. If these registers were modified, we pushed their original values onto the stack at the beginning of foo. The original values can be popped off the stack, if the ESP register is pointing to the correct location shown in Figure 4. So, it is important that we do not lose track of the stack pointer ESP during the execution of the body of foo --- i.e., the number of pushes and pops must be balanced.

After these two steps we no longer need the local variables and temporary storage for foo. We can take down the stack frame with these instructions:

        mov     esp, ebp
        pop     ebp

The i386 instruction set has an instruction "leave" which does exactly the same thing as the mov and pop instructions above. Thus, it is very typical for C functions to end with the instructions:

        leave
        ret

The caller's actions after returning

        add     esp, 12

Finally, the main function can pop the values of the EAX, ECX and EDX registers if their values were preserved on the stack prior to the function call. This puts the top of the stack at the exact same position as before we started this entire function call process. (Recall that this position is indicated by a red line in Figures 2-5.)

C/C++ (そしてほとんどのプログラム) というのは、アドレスによって一次元化されたメモリ空間の上で処理を行います。しかし、メモリ上に置かれるデータや実行コードはバラバラに存在するわけではありません。実際にはどのように配置されているのでしょうか？

プログラムが使用するメモリ領域というのは、基本的にスタック (Stack)、ヒープ (Heap)、実行コード、そして恒久変数領域に分けられます。もちろんコンパイラやプログラムが動作するシステムによってはこのほかの領域が存在するかも知れませんが、基本的な構造は変わりません。このページで解説する以外の詳細はそれぞれのコンパイラに付属するマニュアルを参照してください。

恒久変数領域

恒久変数はプログラムで static として宣言された変数やグローバル変数です。その変数はプログラムが開始されてから終了するまで恒久的にメモリ上に存在しています。通常プログラムがコン パイルされるときに恒久変数としてどれだけ割り当てれば良いかを決定できますので、この領域の大きさが変化することはありません。つまり恒久変数領域と は、プログラムが開始してから終了するまで存在する変数を置く領域という事になります。

使用している OS によっては、恒久変数領域を読み出し専用領域と読み書き両用領域に分けるかもしれません。その場合、文字列リテラルや const 定義された定数データなどは読み出し専用領域におかれ、そこへの書き込みがアクセス違反になる場合があります。

実行コード領域

変数やデータだけではなく、プログラムの実行コードもメモリ上に置かれていなければいけません。実行コード領域とはプログラムの実行コードを置いておく領域の事です。プログラムから関数ポインタを使用する場合には、実行コード領域内の該当する関数が置かれている先頭位置を使用している事になります。

恒久変数と同様に、プログラムが開始してから実行コードが増減するわけがありませんので (自己進化型プログラム?)、実行コード領域の大きさもコンパイルするときに決定する事ができます (ダイナミックリンクを行う場合ではちょっと違ってきます)。

スタック領域

スタック領域は一般的な変数を保存して置く場所です。プログラムから int x; のように宣言された変数はすべてスタック領域に置かれます。

スタック領域の大きさはコンパイルされるときに決定され、プログラムが起動するとその大きさのメモリがスタックとして予約されます。プログラムは int x; のようなスタック変数が使用されると、予約されたスタック領域からその変数の大きさの領域を使用します。しかし、プログラムが使用する変数の数は処理状況によって変わってきます。運が悪ければスタックの全領域を使い果たしてしまうスタックオーバーフローというエラーが発生するでしょう。

スタックの大きさはプログラムをコンパイルするときに変更する事ができます。変更の仕方はコンパイラによるので、それぞれのマニュアルを見てくださ い。もしたくさんの配列を使ったり、関数の再帰呼び出しを行うようなプログラムだったら、コンパイル時に少し大きめにスタック領域を取っておく必要がある でしょう。

ヒープ領域

ヒープ領域は、プログラムが使用できるメモリの中から上記のものを差し引いた『余りの部分』となります。上記の全ての領域はコンパイルしたときに大きさが決定されますが、ヒープの大きさはコンピュータがつんでいるメモリの大きさによりますし、オペレーティングシステムがプログラムに割り当ててくれるメモリの量に依存しています。つまり、ヒープ領域は実行してみるまで大きさがわかりません。通常はスタックと比べてかなり大きな領域となるでしょう。

Windows 95 ではプログラムが起動されると (実際にはそんなになくても) 仮想メモリを使用して 4GB(!) もの領域が割り当てられます。Visual C++ ではデフォルトのスタックサイズは 1MB です。実行コードでさえ大きくても数メガバイト程度でしょう。残りの領域はすべてヒープとして使う事ができます。

プログラムでこの広大な領域を使用するにはどうしたら良いか？new や malloc() を使用することでヒープから適当な大きさの領域を確保することができます。これには裏でプログラムとオペレーティングシステムでいろいろなやり取りを行う ことになりますが、私もページ単位でどうとか程度しか知りません。とりあえず C では malloc()、C++ では new によりヒープ領域を使用することができます。

プログラムで使用しているヒープ領域もいよいよなくなったらどうなるか。malloc() や new では領域の割り当てに失敗した場合 NULL が返されます。例外を 発生させるコンパイラもあるでしょう。しかし、Windows95 や UNIX 環境でヒープも使い果たすというのはめったにありません。どこかにバグがないか、メモリーリークはないかを探してみてください。ちなみに MS-DOS や Windows 3.1 では、バグがなくても結構頻繁にヒープも使い果たします。こちらの場合にはメモリを節約するようにしてください。

メモリマップの例: Turbo C⁺⁺ 4.0 for MS-DOS

グローバル変数1: 0x06aa
グローバル変数2: 0x06ac
静的変数1      : 0x06ae
静的変数2      : 0x06b0
スタック変数1  : 0xfff4
スタック変数2  : 0xfff2
ヒープ変数1    : 0x1194
ヒープ変数2    : 0x119c
関数1          : 0x0293
関数2          : 0x029a

やはりグローバル変数と静的変数は同じ恒久変数領域に配置されているようですね。このメモリマップを図で表すと以下のようになります。

上の図では実行コードの領域と恒久変数領域が小さすぎるので、実際より少し大きく取ってあります。メモリモデルを Small にしたため、プログラムで使用できる全メモリ数が 65,535 バイトになっています。スタックサイズはデフォルトの 4kB です。

この実行例だと、スタックは 0xFFFF から開始し、順番に下がっていっているようです。スタックサイズが 4,096 バイトですから、アドレス 0xBF69 までがスタック領域となります。

ヒープの先頭は 0x1194 から始まり、多分スタック領域の手前まで使う事ができると思います。従って 0xBF69-0x1194=0xADD5 ですから、ヒープ領域のサイズはおよそ 43kB という事になります。しかし、上の例では int 型整数 (MS-DOS の int は 2 バイト) を確保しているにもかかわらず、8 バイトの領域が使用されているようです。これは、確保した領域の情報を保存するための予備領域が必要なためです (上の例では 6 バイトが使用されているようです)。

スタックの動作

int main(void){
    int x;
    char ch[5];
    /* Operation... */
    return 0;
}

スタック領域はプログラムが使用する一般的な変数を置いておく場所です。この領域には関数内で int x; のように宣言された変数や、関数に渡される引数などが置かれます。

スタック領域のどこまで変数が保存されているかはスタックポインタという値が保存しています。スタックポインタはプログラムの開始時にスタック領域の先頭を指しています (上記の例では 0xFFFF)。

プログラムから 4 バイト整数 int x を宣言した場合、変数 x はスタックポインタが現在指している位置から 4 バイトの領域に配置され、スタックポインタは 4 バイト進められます。

さらに 5 バイトの文字を宣言したとします。この時、現在のスタックポインタから 5 バイトがその変数のために確保され、スタックポインタは 5 バイト進められます。

プログラム (変数のブロック) が終了すると、宣言された逆の順番 (つまり char ch[5], int x の順番) でスタックから削除されます。処理の効率化のため、プログラムはスタックポインタをデータの大きさだけ戻すだけで、削除された領域の初期化までは行いません。このため、次にスタックを使用するときに以前使った値が『ごみ』として入っているわけです。

C/C++ や Basic を使用したプログラムでは、スタックポインタを直接プログラマが操作する必要がありません。コンパイラが自動的に処理してくれます。もしスタックポインタを直接操作する必要があるならアセンブラを使用しなければいけません。

スタック領域はコンパイルするときに大きさが決められています。もしプログラムの処理過程でスタックの領域をオーバーしてしまったら、スタック領域の向こう側 (Turbo C++ ではヒープ領域でした) をスタック領域と間違って使ってしまうでしょう。これがスタックオーバーフロー (Stack Overflow) というエラーです。

スタックオーバーフローを検知するためには、スタックに変数を追加するごとにスタックポインタを評価する方法があります。しかし、スタック変数のよ うに頻繁に使用されるものに対していちいち評価をしていては処理の効率が悪くなります。ほとんどのコンパイラはスタックオーバーフローのチェックをしない ように初期設定されているでしょう。

ヒープの動作

ヒープはプログラムが使用できる全メモリ領域から、実行コードなどの必要なメモリを差し引いた領域です。通常はスタックと比べて非常に大きな領域となっています。これは巨大なデータを扱う場合や、あらかじめ大きさが分からないデータを扱う場合などに使用されます。先の Turbo C++ の例では、スタックを使用して 5kB の配列を確保できませんが (スタックの最大サイズは 4kB)、ヒープ領域を使えば解決できます。

char* ptr = malloc(1024 * 5);
/* Operation... */
free(ptr);

Memory Leak

スタック変数は寿命が尽きるとプログラムが自動的に削除してくれますが、ヒープから確保した領域はプログラマが自分で開放しなければいけません (Java は自動的に削除してくれます)。という事は、一度確保した領域のポインタは削除するまでどこかに保存しておかなければいけないという事になります。

char* ptr = malloc(100); ptr = NULL; /* Missing allocated block! */

上の例ではヒープから確保した領域を見失っています。見失った領域はプログラムが終了するまでの間、ずっとヒープに存在しつづけるでしょう。これをメモリリーク (Memory Leak) と呼びます。

小さなプログラムにとってメモリリークはそれほど悪影響を及ぼさないでしょう。しかし、メモリリークを放っておくと、次第に小さなリークが蓄積していずれヒープの全領域を食いつぶしてしまいます。どんな小さなプログラムでもメモリリークを放っておくのはプログラマとしての行為ではありません。

Fragment

ヒープ領域はプログラムの好きなところで確保して、好きなところで開放できます。スタックのように順番通りに追加と削除を行う必要はありません。し かし、これはちょっとしたメモリ効率のロスになります。単純なヒープモデルを考えてみましょう。ヒープには 2 バイトのデータ x と 4 バイトのデータ y があります。

ここで、y よりも先に x を開放すると、フラグメント (Fragment: 断片) と呼ばれる隙間ができてしまいます。

次に新しく 4 バイトのデータ z を確保してみます。この時、以前に開放された 2 バイトの領域では不十分なため、別の領域が確保されてしまいます。

このようなフラグメントがたくさん発生すると、それだけメモリの効率が悪くなってしまいます。実際にはなるべく断片化が進まないように OS のレベルで最適化が行われますが、どの程度フラグメントが発生するかというのはその OS の機能にかかっています (Macintosh はこのようなフラグメントが発生しやすくて有名です)。

ヒープを使用するプログラムは、頻繁に小さな領域の確保と開放を繰り返すよりも、大きな領域をまとめて確保したほうがフラグメントの発生を押さえる 事ができます。しかし、メモリぎりぎりまで使うプログラムを作るのでなければ、このようなフラグメントはあまり気にする必要はありません。プログラムのア ルゴリズムを複雑にしてバグを入れるよりも、ヒープ管理を OS に管理を任せてしまったほうが安全だと思います。

Memory Debugging

単純な入力ミスと違い、メモリがらみのバグというのはとかく見つけにくいものです。特にポインタや配列を使った処理には常に付きまとう問題です。このセクションではちょっとメモリデバッグについて説明したいと思います。

Buffer Overrun

	char array[3]; for(int i=0; i<=3; i++){ array[i] = 0x00; }

配列などとして確保された領域 (スタックでもヒープでも) を超えてデータを読み出したり書き込んでしまうバグの事をオーバーラン (Overrun) とか領域外アクセスと呼びます。たとえば 3 バイトを変数として確保したのに、その 4 バイト目にデータを書き込んでしまう場合です。Java ではこのようなバッファオーバーランが発生した場合、配列外参照の例外 ArrayIndexOutOfBoundsException がスローされますが、C/C++ ではプログラムが自動的に検出してくれるような事はありません。

Internet Watch: 以前 Microsoft Internet Explorer 4.0 でバッファオーバーランのバグが話題になりました。res:// から始まる URL の 257 文字以降に実行ファイル名を記述すると、ブラウザ側のコンピュータの実行ファイルを実行できてしまうというものです。URL 用のバッファが 256 バイトで、そのすぐ隣に実行ファイル名のバッファがあったらしいです。

もちろん正規の領域より外の領域にはどんな値が置いてあるか分かりません。もしかしたらプログラムを実行する上で重要な値が置いてある可能性もあるでしょう。この値を書き換えてしまったら大変な事になります。

Memory leak

メモリリークはヒープを使用して処理を行うときに発生するエラーです。ヒープ領域のセクションで述べたように、小さなメモリリークをほうっておくと いずれ全てのメモリを食い尽くしてしまうかもしれません。メモリリークを検出するのはとても難しい事ですが、通常は以下のような方法を使う事ができます。

Memory Management in Visual C++

メモリデバッグの例として Microsoft Visual C++ 4.0 を見てみましょう。Visual C++ はデバッグ版のプログラムを実行するとき、メモリリークやバッファのオーバーランを検出するため、プログラムが要求した領域に加えてさまざまな情報を保存できるようにしています (これらはリリース版で取り除かれます)。

Visual C++ ではプログラムが要求したサイズのヒープ領域 (右の図の『ブロック』部分) に加えて、この領域の確保を行ったファイル名と行番号、ブロックサイズなどを保存し、実際にプログラムが使用する領域の前後に予備領域を設けて確保します。

もしプログラムが確保したメモリを開放しないまま終了しようとすると、デバッグ版のプログラムは『○○というファイルの○○行目で確保されたメモリが開放 されていません』といった警告を表示するでしょう。このファイル名と行番号は、メモリを確保したときの予備領域に追加された情報です。

もしプログラム内でバッファオーバーランが発生したら、ブロックの前後のバッファが書き換えられているはずです。Visual C++ ではメモリを開放するときに、ブロック前後に追加したバッファ領域が書き換えられているかどうかをチェックします。もしこの領域が書き換えられているなら、プログラムが要求した領域を超えて書き込みが行われたという事になり、バッファオーバーランを検知できます。

要求した領域の前後につけられるバッファには、初期状態として特殊な値が入れられています (たしか半角カナ文字の『エ』だったような気がします)。もしプログラムを動作させていて、変な所でこの特別な値が読み出された場合、確保された領域を超 えてデータが読み出された可能性があります。

このブロックはダブルリンクリストと して構造化されています。ヒープから領域が確保されると新しいブロックがリストに連結され、開放されるときに切り離されます。そしてプログラムが終了する ときにまだ開放されていない領域があるかどうかを評価します。この時、ブロックごとに確保されたファイル名と行番号が保存されているのでとても便利です。