Ｃ言語のメモリアロケーション
今回はＣ言語の「メモリアロケーション (メモリ確保, メモリ割り当て)」について説明します。今までは外部変数や局所変数を宣言することでメモリ領域を確保しました。外部変数はプログラムを実行するとき、あるメモリ領域 (データ領域) に確保されます。これを「静的メモリ割り当て」といいます。局所変数や関数の引数は「スタック領域」に確保されます。これを「自動メモリ割り当て」といいます。
最後に、「ヒープ領域」からメモリを割り当てる方法があります。これを「動的メモリ割り当て」といいます。Ｃ言語の場合、ヒープ領域からメモリを取得する関数 malloc が標準ライブラリに用意されています。malloc で割り当てたメモリ領域は、局所変数や引数のように自動的に解放されません。メモリを解放するための関数が free です。malloc や free を使いこなせるようになると、プログラミングの幅はぐーんと広がります。少々難しい話になりますが、恐れずにチャレンジしましょう。
●スタックとは？
一般的なＣコンパイラの実装では、引数を「スタック (stack)」というメモリ領域に格納してから関数を呼び出します。また、局所変数もスタック上に確保されます。では、スタックとはどのようなものなのでしょうか。よく例に取り上げられるのが「バネ付きのトレイ」です。下図を見てください。
図 : スタックの動作例
最初は空の状態です。ここにトレイを上から入れると、重さによってバネを圧縮し、次のトレイを追加できるようになります。さらにもう一つトレイを乗せると、さらにバネを圧縮し次のトレイを追加できるようになります。バネが限界まで圧縮されるとトレイは追加できなくなります。トレイを取り出す場合は、上にあるトレイから取り出します。ひとつ取り出すと、その分バネが伸びて下にあるトレイが上に出てくるので、次のトレイを取り出すことができます。
このトレイをデータに見立ててみましょう。データ A をスタックに追加し (2)、次にデータ B を追加します (3)。データを取り出す場合、後から入れたデータ B が先に取り出され (4)、その次にデータ A が取り出されてスタックは空になります (5)。スタックにデータを追加することを「プッシュ (PUSH)」といい、スタックからデータを取り出すことを「ポップ (POP)」といいます。
コンピュータではメモリを使ってこのスタックを実装することになります。一般に、バネの代わりに「スタックポインタ (SP)」を使ってスタックを管理します。下図を見てください。
便宜上アドレスを A から E までのアルファベットで表すことにします。スタックが空の場合 SP は E を指示しています。データをプッシュする場合、SP を E から D にひとつ減らし [*1] D にデータをセットします。データをプッシュしていくと SP は Low アドレスに向かっていきます。つまりデータは High アドレスから Low アドレスに向かってスタックに積まれていきます。[*2]
データをポップする場合、SP が B を指示しているならば、B にあるデータ 1 を取り出してから SP をひとつ増やして C に移します。データを次々とポップしていくと SP の値は E になり、スタックは空の状態になります。
これが何の役に立つんだと思ってはいけません。近代的なプログラミング言語は、スタックを使って関数呼び出しを実装しているからです。関数の呼び出しや局所変数の確保に使われるスタックを「システムスタック」とか「コールスタック」といいます。
[*1] 実際にはスタックに積むデータサイズによって SP の増減幅が決まります。たとえば、データが int ならば 4 バイトの大きさなので、スタックに積むと SP の示すアドレスは 4 減少します。ここでいう 1 つは 1 データサイズ分と考えてください。
[*2] これは一般的な処理系のコールスタックの場合で、スタックの伸びる方向が逆の処理系があってもかまいません。
●関数呼び出しとスタックの関係
それでは、関数が呼び出されるときのスタックの様子を見てみましょう。階乗の計算を行う関数 fact(4) から fact(3) を呼び出す場合を考えてみます。次の図を見てください。
リスト : 階乗
int fact(int n)
{
if (n == 0)
return 1;
else
return n * fact(n - 1);
}
fact(4) が実行されているときのスタックポインタは (1) の状態であったとしましょう。アドレスを便宜上 A から J までのアルファベットで表すことにすると、SP は J を示しています。
まず引数 n の値 3 がスタックに積まれます。SP はひとつ減りアドレス I を指し示し、そこに n の値 3 が格納されます。fact の引数はひとつなので、次に fact の関数呼び出しが行われます。関数を呼び出す場合、呼び出された関数から呼び出し元の関数に戻るための情報（リターンアドレス）をスタックにプッシュします。
fact(3) が実行されるときの SP は (2) の状態です。呼び出された関数では、スタックポインタの位置から引数がスタックのどの位置に積まれたかわかるので引数を取り出すことができます。同様にして fact(2) が呼び出されるときは、アドレス G の位置に引数 n の値 2 が格納されます。このように、関数呼び出しが行われるたびに引数が新しい領域にコピーされていくことがわかると思います。これが「値呼び」の仕組みです。
関数の実行が終了すると、スタックからリターンアドレスを取り出して呼び出し側に戻ります。このままではスタックに引数を積んだままの状態なので、呼び出し側の関数でスタックから引数を削除する処理を行います。なお、スタックに積んだ引数を削除するタイミングは、プログラミング言語によって異なります。
fact は引数がひとつしかなかったので、今度は引数が複数ある関数を呼び出す場合を考えてみましょう。
リスト : 引数が複数ある場合の例
int foo(int a, int b, int c)
{
return a * a + 2 * b + c;
}
CPU が x86 の場合、実引数は右側から順番にスタックに積まれていくことに注意してください。ただし、引数を評価する順序は規定 [*3] されていないので、左側の引数から評価する処理系があってもかまいません。その場合でも、実引数をスタックに積む順番は変わりません。
たとえば、a = 10, b = 20, c = 30 として、foo(a, b, c) を呼び出す場合、変数から値を取り出す順番が a -> b -> c になるのか c -> b -> a になるのかは処理系に依存しますが、スタックに格納される実引数はどちらの方法でも Low [10 20 30] High になるということです。
簡単な例を示しましょう。次のプログラムは clang と gcc で実行結果が異なります。
リスト : 引数の評価順序 (sample80.c)
#include <stdio.h>
int foo(char *mes, int n)
{
printf("%s\n", mes);
return n * n;
}
int main(void)
{
int a = 10, b = 20, c = 30;
printf("%d %d %d\n", foo("foo", a), foo("bar", b), foo("baz", c));
return 0;
}
$ clang sample80.c $ ./a.out foo bar baz 100 400 900 $ gcc sample80.c $ ./a.out baz bar foo 100 400 900
Clang の場合は左側の引数から評価され、GCC の場合は右側の引数から評価されていることがわかります。
[*3] 関数を呼び出すときの規則は、CPU によっては標準的な方法が定められており、これを「関数呼び出し規約」といいます。x86 の場合、デフォルトで用いられる規約に cdecl があります。
●局所変数とスタックの関係
引数と同様に、局所変数もスタック上に確保されます。なお、これから説明することは単純化した一般論であり、コンパイラの最適化によっては結果が異なる場合もあります。ご注意ください。
リスト : 局所変数の例
void foo(int n, int m)
{
int a = n / m;
int b = n % m;
printf("n / m = %d n % m = %d\n", a, b );
}
関数 foo は引数の商と剰余を求めて表示します。局所変数 a と b はスタック上に確保されます。
関数 foo が呼び出されたときのスタックポインタの位置は (1) です。局所変数をスタック上に確保するには、必要なサイズだけスタックポインタを Low アドレスに向かって移動させるだけです。ただし、単純に移動させると、リターンアドレスの位置がわからなくなるので、「フレームポインタ (FP)」を使ってスタックポインタを管理します。
局所変数を作る場合、まず FP の値をスタックに積みます。FP には呼び出し元関数のフレームポインタがセットされているので、その値をスタックに退避しないといけません。SP は (2) の位置に移動します。その値を FP にセットしてから局所変数のサイズだけ SP を移動させると (3)、局所変数 a, b の領域を確保することができます。
必要な局所変数のサイズはコンパイルした時点で決めることができます。また、フレームポインタを基準にすれば局所変数にアクセスすることも簡単にできます。この場合、引数のアクセスもスタックポインタではなくフレームポインタを使った方が簡単になります。
呼び出し元関数に戻るときは、まず FP の値を SP に戻します。すると SP は (2) の位置に戻るので、そこに積まれている値を POP して FP にセットします。これで呼び出し元関数のフレームポインタを元に戻すことができます。すると SP は (1) の位置にもどり、そこにはリターンアドレスが積まれているので、そのアドレスを取り出して呼び出し元関数に戻ることができます。
以上のことから、局所変数は関数の実行が終了した時点で解放されることもわかります。今まで局所変数として使っていた領域は、ほかの関数が実行されると、その局所変数もしくは引数を渡すための領域として使用されることになります。なお、コンパイラの最適化によっては、局所変数 a, b はスタック上に確保されるのではなく、レジスタに割り当てられる場合があります。
レジスタは CPU 内部にある一時記憶メモリのことで、CPU の外部に接続されているメモリ（主記憶メモリ）とは異なります。一般に、レジスタはメモリよりも高速にアクセスすることができるので、局所変数をスタック上に作るよりもレジスタに割り当てたほうが、プログラムを高速に実行することができます。
ところで、前々回説明した局所変数の値を交換するプログラム swap の動作も、スタックについて理解していれば当然な結果であると納得していただけると思います。
リスト : 値の交換（間違い）
#include <stdio.h>
void swap(int a, int b)
{
int tmp = a;
a = b;
b = tmp;
}
int main(void)
{
int x = 10;
int y = 20;
swap(x, y);
printf("x = %d\ny = %d\n", x, y);
return 0;
}
swap が呼ばれた時点でのスタックの様子を下図に示します。
main の局所変数 x, y の値がスタック上にコピーされて swap に渡され、swap はこの領域の値を書き替えるので、x と y の値は変更されないことがわかります。
値を交換したい場合はポインタを使います。
リスト : 値の交換（正解）
#include <stdio.h>
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int main(void)
{
int x = 10;
int y = 20;
swap(&x, &y);
printf("x = %d\ny = %d\n", x, y);
return 0;
}
swap の引数はポインタとして宣言し、swap を呼び出す場合は、& 演算子を使ってその変数のアドレスを渡します。swap を呼び出したときのスタックは次のようになります。
引数 a にはアドレス F が入っているので、*a とすることで main で定義した局所変数 x にアクセスすることができます。引数 b も同様です。
●スタック領域について
いままでスタックについて説明してきましたが、それでは実際にはメモリのどこに割り当てられているのでしょうか。これは OS などの処理系に依存しますが、ここでは下図に示すようにスタック領域はプログラム本体の後ろに確保されると考えてください。
外部変数はデータ領域に確保されます。ヒープ領域は「動的メモリ確保」で使用します。これはあとで説明します。スタックは高位アドレスから低位に向かって伸びていくので、再帰呼び出しの回数が多くなると (深くなるともいう) スタック領域が足りなくなって、他の領域を侵したときに Segmentation fault (コアダンプ) が発生します。簡単な例を示します。
リスト : スタックオーバーフロー (sample81.c)
#include <stdio.h>
int sum(int n, int m)
{
if (n == m)
return n;
else
return n + sum(n + 1, m);
}
int main(void)
{
for (int i = 100; i < 10000000; i *= 10)
printf("sum(1 ,%d) = %d\n", i, sum(1, i));
return 0;
}
$ clang sample81.c $ ./a.out sum(1 ,100) = 5050 sum(1 ,1000) = 500500 sum(1 ,10000) = 50005000 sum(1 ,100000) = 705082704 Segmentation fault
関数 sum は再帰呼び出しが深くなるとスタック領域をはみ出して他の領域を侵すことになるので、Segmentation fault (コアダンプ) が発生します。ちなみに、デフォルトのスタックサイズはコマンド ulimit で調べることができます。
$ ulimit -a real-time non-blocking time (microseconds, -R) unlimited core file size (blocks, -c) 0 data seg size (kbytes, -d) unlimited scheduling priority (-e) 0 file size (blocks, -f) unlimited pending signals (-i) 15481 max locked memory (kbytes, -l) 65536 max memory size (kbytes, -m) unlimited open files (-n) 1024 pipe size (512 bytes, -p) 8 POSIX message queues (bytes, -q) 819200 real-time priority (-r) 0 stack size (kbytes, -s) 8192 cpu time (seconds, -t) unlimited max user processes (-u) 15481 virtual memory (kbytes, -v) unlimited file locks (-x) unlimited
M.Hiroi の環境では 8192 kbyte でした。
●動的メモリ割り当て
今までは、変数を宣言することでメモリの確保を行なっていました。局所変数はスタック上に割り当てられ、外部変数はデータ領域に確保されます。どちらの変数もコンパイル時にその大きさが決定されるので、プログラムを実行している途中でサイズを変更することはできません。あらかじめ決められたサイズ以上にデータを書き込めば、ほかのデータを破壊し、最悪の場合、プログラムは暴走することになります。
たとえば、テキストファイルを行単位で処理する場合、1 行の長さは不定長ですので、文字列長は実際に読み込んでみないとわかりません。このような場合、あらかじめ外部変数としてバッファを用意すると、そのバッファサイズより長い行が含まれているテキストファイルは処理できないことになります。
また、余裕をもって大きいサイズのバッファを用意すると、メモリの無駄使いになってしまいます。最近のように、メインメモリが大量に搭載されていれば、あまり問題にならないかもしれませんが、使用できるメモリが少ない環境では、プログラムを実行することができないかもしれません。
このような場合、プログラムの実行中に必要なサイズが判明した時点で、その大きさのメモリを、どこからか確保できるような手段が必要になります。このことを「動的メモリ割り当て」といいます。
●関数 malloc
Ｃ言語でメモリを動的に割り当てる場合、標準ライブラリに用意されている関数 malloc を使います。
| ヘッダ | stdlib.h |
| 書式 | void *malloc(size_t size); |
| 引数 | size : 確保するメモリサイズ(byte 単位) |
| 機能 | ヒープ領域よりメモリを size バイト割り付ける |
| 返り値 | 成功 : メモリ領域へのポインタ, 失敗 : NULL |
malloc はヒープ領域から必要なメモリ領域を確保します。なお、本稿ではヒープ領域の位置はデータ領域の後ろにあるものとして説明します。
一般に、Ｃ言語の標準ライブラリではヒープ領域が足りなくなると、空きメモリがあれば自動的に拡張されます。上図に示すように、高位アドレスに向かって拡張されます。
メモリを割り当てる関数は malloc と calloc、それから realloc があります。前者は新しくメモリを割り当てる場合に使い、後者はすでに獲得したメモリ領域のサイズを変更する場合に使います。
ヒープ領域はライブラリが管理しているメモリ領域です。malloc によってメモリの要求が行なわれると、ヒープ領域の中から空き領域を探します。ユーザーが要求したサイズだけ割り当てられるのではなく、ヒープ領域を管理するための情報が必要です。上図に示すように、Header が管理領域で、この中に領域が使用中で大きさがいくつであるか、といった情報が書き込まれます。malloc の返り値は、ユーザーが使える領域の先頭アドレスが返されます。
確保したメモリは、領域の範囲内で使用するように注意して下さい。領域の前後をはみ出せば、自分の管理領域やほかの管理領域、もしくはほかの領域の中身を破壊することになります。これは、普通の変数の場合と同じですね。Ｃ言語の場合、ほかの領域を破壊しても無頓着ですから、次のメモリを要求したときや、壊された領域の中身をアクセスしたときに、ひどい目に合うことになるのです。
calloc は、malloc と同様にメモリをヒープ領域から確保しますが、領域を 0 に初期化する点が異なります。malloc の場合、領域の中身は不定です。
●関数 realloc
realloc は領域のサイズを変更する場合に使われます。
| ヘッダ | stdlib.h |
| 書式 | void *realloc(void *ptr, size_t size); |
| 引数 | ptr : 変更するメモリ領域へのポインタ size : 変更するメモリサイズ(byte 単位) |
| 機能 | ptr の示すメモリ領域のサイズを size バイトに変更する |
| 返り値 | 成功 : メモリ領域へのポインタ, 失敗 : NULL |
サイズを変更する場合は、大きくする場合と小さくする場合があります。サイズを小さくする場合は簡単です。
サイズを小さくする場合は、余分な領域を解放するだけですみます。この場合、realloc の返り値は、以前確保したアドレスと同じです。領域を大きくしたい場合は、ちょっと面倒です。
まず、要求されたサイズを満たす領域を新しく確保し、旧領域より内容をコピーします。そして、旧領域はライブラリによって解放されます。realloc の返り値は、新しい領域のアドレスです。以前確保した領域とは違うアドレスであることと、新しく増えた領域の値は不定であることに注意してください。また、旧領域からコピーする作業が増えるので、メモリを割り当てるのに malloc よりもちょっとだけ時間がかかります。
●関数 free
使い終わったメモリは解放しないといけません。ヒープ領域が自動的に拡張されるからといって使ったまま放置したのでは、いつかはメモリ不足になってしまいます。メモリの解放には free を使います。
| ヘッダ | stdlib.h |
| 書式 | void free(void *ptr); |
| 引数 | ptr : 解放するメモリ領域へのポインタ |
| 機能 | メモリ領域を解放し、ヒープ領域に返却する |
| 返り値 | 無し |
free の引数は、malloc などの返り値を与えなければならないことに注意してください。
メモリを解放する場合、与えられたアドレスから管理領域を求めて、上下のエリアが空き領域であれば、ひとつの空き領域にまとめる処理を行ないます。これは、小さな空き領域ばかりに分割されると、大きな領域を割り当てるには、新しいメモリを取得するしかなくなり、メモリを浪費することになるからです。
与えられたアドレスのすぐ上に管理領域があることを前提として動作するので、ほかのアドレスを与えた場合の動作は不定です。試したことがないのでわかりませんが、プログラムはたぶん暴走するのではないでしょうか。
●簡単な使用例
簡単な例を示しましょう。
リスト : 動的メモリ割り当て (sample82.c)
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int *p = malloc(sizeof(int));
double *q = malloc(sizeof(double));
int *a = malloc(sizeof(int) * 8);
if (p == NULL || q == NULL || a == NULL) return 1; // 異常終了
printf("%p\n", p);
printf("%d\n", *p);
printf("%p\n", q);
printf("%f\n", *q);
printf("%p\n", a);
for (int i = 0; i < 8; i++) printf("%d ", a[i]);
printf("\n");
*p = 100;
*q = 1.2345;
a[0] = 10;
a[7] = 80;
printf("%d\n", *p);
printf("%f\n", *q);
for (int i = 0; i < 8; i++) printf("%d ", a[i]);
printf("\n");
// メモリの解放 (省略してもよい)
free(p);
free(q);
free(a);
return 0;
}
$ clang sample82.c mhiroi@DESKTOP-FQK6237:~/clang$ ./a.out 0x561dc0c752a0 0 0x561dc0c752c0 0.000000 0x561dc0c752e0 0 0 0 0 0 0 0 0 100 1.234500 10 0 0 0 0 0 0 80
データ型の大きさは sizeof 演算子で求めることができます。たとえば、sizeof(int) は 4 または 8 になり、sizeof(double) は 8 になります。malloc(sizeof(int)) とすると、int を格納するメモリ領域が確保され、そのポインタが返されます。同様に、malloc(sizeof(double)) とすると、double を格納するメモリ領域が確保されます。
配列を確保することもできます。int a[8] と同じ大きさのメモリを取得するには、malloc(sizeof(int) * 8) とします。これで配列に必要な 32 (または 64) バイトのメモリを確保することができます。あとは、malloc の返り値をポインタにセットして、そのメモリ領域にアクセスすればいいわけです。
ところで、malloc を呼び出すときは返り値が NULL でないことをチェックしてください。メモリをたくさん積んでいるから大丈夫だろうといって省略すると、痛い目にあうかもしれません。ご注意くださいませ。
ところで、取得したメモリ領域は使い終わったら元に戻す処理が必要になります。最近は、不要になったメモリ領域を自動的に回収する「ガベージコレクション (garbage collection, GC)」という機能を持つプログラミング言語が多くなりました。Ｃ言語の場合、標準では GC をサポートしていないので、不要になったメモリ領域は自動的に回収されません。不要なメモリ領域は free で解放することを忘れないでください。
ただし、ほとんどの処理系ではプログラムの終了時に malloc で取得したメモリを free で解放する必要はありません。プログラムで使用したメモリは実行終了時に解放されますが、このとき malloc で割り当てたメモリも解放されるようになっているからです。もちろん、例外的な処理系もあるでしょうが、一般的には malloc で取得したメモリを最後まで使うのであれば、free を省略できると考えてもいいでしょう。
今回はここまでです。次回は「構造体」について説明します。構造体と malloc を使うと、連結リストや二分木といった複雑なデータ構造を簡単に構築できるようになります。
改訂 2023 年 4 月 2 日