Malloc

**malloc**（マロック, エムアロック）、**calloc**、**realloc**は、動的メモリ確保を行うC言語の標準ライブラリの関数である。確保したメモリの解放には**free**関数を使用する。

`malloc`が使用する実際のメモリ確保機構には様々な実装がある。それらの性能は、実行時間と要求されるメモリの両面で様々である。

## 原理

C言語は通常メモリを「静的メモリ確保」か「自動メモリ確保」で管理する。静的変数は主記憶上にプログラムが存在する期間中ずっと確保されている。自動変数（局所変数）は通常コールスタック上に確保され、対応するサブルーチンが実行中の間だけ存在する。しかし、いずれの方法も限界があり、確保できるメモリ量（変数のサイズ）はコンパイル時に決められてしまう。必要なサイズが実行時でないと判明しない場合、例えばディスク上のファイルから任意のサイズのデータを読み込むような場合、固定サイズのデータオブジェクトだけでは不十分である。

確保されたメモリの生存期間（使用可能期間）も問題となる。静的でも自動的でも確保されたメモリの生存期間はあらゆる状況に対応できるものではない。スタック上のデータは複数の関数呼出をまたいで持続できないし、静的データは必要かどうかにかかわらずプログラムが動作中ずっとメモリ領域を確保し続ける。しかし、そうではなく確保したメモリの生存期間をプログラマが自由に制御できる必要がある場合も多い。

これらの制限は動的メモリ確保を使用することで解決する。メモリの管理は明示的に行う必要が出てくるが、柔軟性が向上する。「ヒープ領域」はこのために用意されたメモリ領域である。C言語では、`malloc`関数を使ってヒープ領域からメモリブロックを確保する。プログラムは`malloc`の戻り値であるポインタを使って、そのメモリブロックにアクセスする。メモリブロックが不要になったら、そのポインタを`free`に渡して解放し、他の用途に再利用できるようにする。

ヒープではなくCのスタックフレームから実行時に動的にメモリを確保するライブラリルーチンもある。このように確保したメモリは呼び出した関数から抜ける時点で自動的に解放される。ただし、スタックオーバーフローに注意する必要がある。GCC言語拡張の可変長配列がC99標準でサポートされ、実行時に大きさを決定でき任意の静的スコープの範囲で存在するメモリ確保法が言語構文に組み込まれたが、C11ではサポート必須ではなくオプションに格下げとなった。

## C言語での動的メモリアロケーション
`malloc`はC言語におけるヒープ領域からのメモリ確保に使われる基本関数である。その関数プロトタイプは`stdlib.h`ヘッダに次のように定義されている。

 void *malloc(size_t size)

ここで、`<var>size</var>`バイトのメモリが確保される。確保が成功するとそのメモリブロックへのポインタが返される。

ANSI Cにおいて`malloc`が返すのは、void型へのポインタ () であり、そのポインタが指す領域のデータ型が不明であることを示している。C言語では汎用ポインタと任意の型`T`へのポインタ`T *`との間の型変換 (キャスト) は暗黙的に実行されるため、`malloc`の戻り値は特に明示的な型変換を記述せずとも任意の型へのポインタ変数にそのまま代入できる。しかし、明示的に型変換を記述する必要が無いにもかかわらず、あえて意図的に型変換を記述することもある。明示的に型変換を記述する目的は、かつてANSI以前の仕様のC（K&R C）においては、が存在せず、`malloc`はを返していたからである。また、C言語よりも厳密な型システムを持つC++では、`T *`からへの型変換は暗黙的に行なわれるものの、から`T *`への型変換は暗黙的に行なわれないため、C/C++両方でコンパイルすることのできるソースコードを書く際には型変換の記述が必要となる。


```c
int *ptr = (int *)malloc(sizeof(int) * 10);
```


しかし、`stdlib.h`をインクルードし忘れた場合（`malloc`関数の前方宣言がない場合）、C99よりも前のバージョンのCコンパイラは`malloc`が型を返す関数であるとみなす。`malloc`の戻り値を明示的に型変換していると、ヘッダーをインクルードし忘れたことに気づかない。一方、明示的に型変換していないと、コンパイル時にをポインタ型変数に代入しようとしているとして何らかの警告あるいはエラーメッセージがコンパイラから表示されることでインクルード忘れに気づける可能性がある。例えば64ビットのシステムでLP64というデータモデルを採用している場合、とポインタは64ビットだが、は32ビットとなる。この場合`stdlib.h`のインクルード忘れに気づかないと、`malloc`が実際には64ビットのポインタを返すのに、32ビットの値を返すと暗に宣言したことになり、バグが生じる可能性がある。ただし、多くのコンパイラは宣言のない関数を使用していると（キャストの有無にかかわらず）コンパイル時に警告を出す。C99以降では前方宣言のない関数の戻り値をとみなさなくなったため、コンパイルエラーとなる。

C99およびC++03まではスレッドの概念が標準化されていなかったため、スレッドセーフ性に関しては何も言及がなかったが、C11およびC++11以降はスレッドセーフであることが規定されるようになった。

### メモリの解放
`malloc`で確保されたメモリは持続性がある。プログラム終了時か明示的にプログラマが解放しない限り存在し続ける。解放は`free`関数で行われる。そのプロトタイプは次のようになる。

 void free(void *pointer)

ここで、`<var>pointer</var>`の指すメモリブロックが解放される。

## 関連する関数
`malloc`はメモリブロックを確保して返すが、その領域は初期化されていない。必要に応じてメモリは個別に初期化する。例えば、`[[memset]]`関数で初期化したり、個別の代入文で初期化したりする。他にも`calloc`（カロック、シーアロック）関数を使って、メモリ確保と初期化を行うこともできる。そのプロトタイプは以下のようになる。

 void *calloc(size_t nelements, size_t bytes)

`<var>bytes</var>`のサイズのメモリ領域を`<var>nelements</var>`個格納できるメモリ領域を確保する。確保された領域はゼロで初期化される。

メモリブロックを大きくしたり小さくしたりできれば便利である。これは`malloc`と`free`を組み合わせて、新たなメモリブロックを確保して内容を前のメモリブロックからコピーし、前のメモリブロックを解放することで実現できる。しかし、この方法は回りくどい。代わりに`realloc`（リアロック）関数を使うことができる。そのプロトタイプは以下の通りである。

 void *realloc(void *pointer, size_t bytes)

`realloc`は指定されたサイズのメモリ領域へのポインタを返す。新しいサイズが前のサイズより大きければブロックは大きくされ、逆ならば小さくされる。

`valloc`は`malloc`とほとんど同じだが、メモリ確保がページ境界になる点が異なる。`valloc`で確保された領域へのポインタを`realloc`に渡すことはできないhttps://www.mkssoftware.com/docs/man3/valloc.3.asp。また、これは標準Cライブラリに含まれる関数ではない。

## 使用例
スタック上に10個の整数の配列を作成する一般的な方法は次の通りである。


```c
int array[10];
```


同様の配列を動的に確保するには、以下のように`malloc`を使う。


```c
#include <stdlib.h>

/* 10個のintの配列のためのメモリを確保 */
int *ptr = malloc(sizeof(int) * 10);
if (NULL == ptr) {
    exit(EXIT_FAILURE); /* メモリを確保できなかったので終了 */
} else {
    /* 確保成功 */
    /* ここでその配列を使った処理を行う */

    /* 処理が完了し、使わなくなったメモリブロックを解放する */
    free(ptr);
    /* 解放したメモリにアクセスしてはならないことを示すため、NULLを代入しておく */
    ptr = NULL; 
}
```


## 一般的なエラー
`malloc`および関連するC言語の関数の使用は、以下のような理由でバグの発生源になりやすい。

### 確保エラー
`malloc`は必ず成功するとは限らない。利用可能な空きメモリ領域がないとき、プログラムが限界値を超えてメモリを使用しようとしたときなど、`malloc`はヌルポインタを返す。環境によって、このような状況の起きる可能性は異なる。もし`malloc`が失敗することを考慮していないプログラムで、`malloc`がヌルポインタを返してきたとき、プログラムはNULLに相当するアドレスにアクセスしてクラッシュするだろう。メモリ確保失敗をチェックすることは、ライブラリでは特に重要である。ライブラリはメモリ量が限られた状況でも使用される可能性がある。ライブラリ内でメモリ確保に失敗した場合、呼び出したアプリケーション側にエラーを通知して、アプリケーションプログラムに判断を委ねるのがよいとされる。

プロトタイピング目的で書かれたコードなどでは、メモリ確保失敗をチェックしないこともある。というのもメモリ確保に失敗するという状況は、画像処理などを除いた一般的な用途では珍しく、発生した場合には終了する以外にプログラミング上できることがないからでもある。ごく少量のメモリさえ確保に失敗するような状況では、メモリ確保失敗に対処したとしてもプログラムを正常に続行できる見込みがない。一方で、ライブラリ製品やアプリケーション製品では異常系すなわち例外処理への対処は重要であり、メモリ確保失敗への対処も例外ではない。

### メモリリーク
`malloc`で確保したメモリブロックを使用しなくなっても`free`で解放せず、次々と新たなメモリブロックを確保していると空きメモリが少なくなってくる。これをメモリリークと呼ぶ。メモリリークによるメモリ消費が無視できない量に達するとページ置換アルゴリズムによってページアウトが発生し、システム性能が低下する。さらに仮想記憶の容量限界に達すると、システム内の他の全プロセスでメモリ確保が失敗してシステムがストールする。メモリリークは、利用のたびにプロセスの起動・終了が行われるプログラムにおいて、特に重要な問題を引き起こさないため、メモリリークが混入した状態で出荷される商用プログラムは多い。しかしながら、連続稼動が要求されるサーバコンピュータ上のプログラム（サービス、デーモン）や、組み込みプログラム等の場合は、メモリリークは死活問題とされる。

### 解放後の使用
ポインタが`free`関数に渡され、メモリが解放された後でその領域への参照を行っても、その内容は未定義であり利用できない。しかし、ポインタ自体が残っていると誤って使ってしまうことがある。次のコードはその例である。


```c
int *ptr = malloc(sizeof(*ptr)); /* メモリ領域を動的確保 */
...
free(ptr);
/* ptr は解放済みの領域をまだ指したまま */
*ptr = 0; /* 何が起きるかわからない！ */
```


このようなコードは予測不能の振る舞いをする。メモリが解放された後でシステムがその領域を他の用途に転用しているかもしれない。従って解放済みメモリ領域へのポインタ（ダングリングポインタ; dangling pointer）を使った書き込みはプログラム内の別のデータを不正に書き換えてしまう。どういうデータを書き換えたかによって、その後のプログラムの動作も異なる。単なるデータ破壊で済むかもしれないし、クラッシュするかもしれない。特に破壊的なバグとしては、同じポインタを2回`free`関数に渡してしまうことであり、これを「二重解放; double free」と呼ぶ。これを防ぐため、解放した後でポインタ変数に`NULL`を格納することがある。ポインタ変数が無効な領域を指しているかどうかを後で調べるとき、`NULL`が格納されているかどうかで簡単に判定できるようになる。また、`free(NULL)`は何もしないことが規格で保証されているので、`NULL`を代入しておけば（`free`関数を再度呼んだとしても）二重解放の危険はない。この技法は寿命の長いグローバル変数でポインタを定義する場合は必須だが、寿命の短いローカル変数でポインタを定義する場合でもフールプルーフのために用いることができる。


```c
int *ptr = malloc(sizeof(*ptr));
...
free(ptr);
ptr = NULL;
```


## 実装

メモリ管理の実装はオペレーティングシステム (OS) と（ハードウェア）アーキテクチャに大きく依存する。OSによってはmallocのためのアロケータを提供しているし、データ領域の制御関数を提供している場合もある。

同じ動的メモリアロケータでmallocだけでなくC++のも実装していることが多い。そこでこれを malloc ではなく「アロケータ」と呼ぶ。

### ヒープ方式
IA-32アーキテクチャでのアロケータの実装には一般にヒープまたはデータセグメントが使用されている（セグメント方式）。
アロケータがメモリを確保するとき、ヒープに未使用領域がない場合はヒープを拡張することでメモリを確保する。

ヒープ方式はフラグメンテーションという問題がある。どのようなメモリ確保方式でもヒープではフラグメントが発生する。つまり、ヒープ上に飛び飛びに使用中領域と未使用領域が存在することになる。優秀なアロケータはヒープを拡張する前に未使用領域を再利用しようとする。しかし性能問題があるため、リアルタイムシステムでは代わりに「メモリプール」という方式を使う必要がある（特定サイズのメモリブロックのプールを予め用意しておく方式）。

ヒープ方式の欠点は、先頭位置が変更できないため、ヒープの最後の位置に使用中ブロックがある限り、ヒープを縮小することができないことである。従って、このような時は実際に使用しているメモリが少ないのにもかかわらず、ヒープのアドレス空間に占める領域が拡大し続けるという問題が生じる。

mmapで確保した領域は、縮小したり開放したりすることができる。これらによって開放された領域は、OSのメモリ管理システムに委ねることになる。

### dlmalloc
dlmalloc はニューヨーク州立大学オスウェゴ校の Doug Lea が1987年に開発を始めた汎用アロケータで、パブリックドメインライセンス（CC0ライセンス）のオープンソースライブラリである。GNU Cライブラリ (glibc) の malloc は、dlmalloc を元に作られている。

ヒープ領域上のメモリは "chunk" という8バイト境界のデータ構造として確保され、その中にヘッダ部と利用可能なメモリがある。chunk および利用中フラグがあるため、8バイトまたは16バイトのオーバヘッドを含めたメモリ確保が必要である。アロケートされていないchunkも他のフリーなchunkへのポインタを持つため、chunkの最小サイズは24バイトとなっている。

アロケートされていないメモリは "bin" と呼ばれる同じサイズのchunkのグループに分けて管理される。binはchunkを双方向連結リストで連結したものである。

小さな領域（256バイト未満）を確保するときには2の累乗フリーリストが使われる。領域が不足したときは、より大きなサイズ用の領域からプールを確保する。

中程度の大きさの領域は、ビット単位トライ木 (bitwise trie) により管理される。領域が不足したときは、（sbrkによる）ヒープの拡張が行われる。

大きな領域（デフォルトでは256KB以上）は、mmap が使える環境の場合、`mmap()` により直接確保される。この大きさならば、ページサイズ単位でしか割り当てられないことによるオーバーヘッドや、システムコールの遅さによるオーバーヘッドはほとんどない。一方で、先に述べたヒープ方式のアロケーションの問題が起こらないので、この方法が使われる。

### FreeBSDとNetBSD
FreeBSD 7.0以降と NetBSD 5.0以降では、古い実装 (phkmalloc) をJason Evansが開発したjemallocに置換した。phkmalloc はマルチスレッド環境でのスケーラビリティに問題があった。ロックの衝突を防ぐため、jemallocはCPU毎に分離した "arena" と呼ばれる領域を用意する。実験によれば、スレッド数に比例して1秒間のmalloc回数が増えていくとき、phkmallocとdlmallocではスレッド数に反比例した性能を示した。

### OpenBSD
OpenBSDの`malloc`関数の実装は`mmap`を使用している。ページサイズ以上の要求は`mmap`で行われ、ページサイズ未満なら`malloc`内で管理しているメモリプールから割り当てる。そのメモリプールも`mmap`で確保したものである。`free`を実行すると、`munmap`を使ってプロセスのアドレス空間からアンマップされて解放される。このシステムはアドレス空間のレイアウトをランダム化することによってセキュリティを高めるための設計でもあり、OpenBSDの`mmap`が持つギャップページ機能も利用している（mmapで確保した領域が仮想空間上で隣接しないようにする機能）。また、解放後の領域は仮想空間としてマッピングが存在しないため、解放後のアクセスの検出も容易である（普通ならセグメンテーション違反が発生してプログラムが終了する）。

### Hoard
は、スケーラブルなメモリ確保性能を目指したアロケータである。OpenBSDのアロケータと同様、Hoard は`mmap`のみを使用するが、64キロバイトのスーパーブロックと呼ばれる塊ごとにメモリを管理する。Hoardのヒープは論理的にグローバルな1つのヒープとプロセッサ毎のヒープに分けられている。さらにスレッド毎のキャッシュを持ち、制限された数のスーパーブロックを保持できる。確保はスレッド毎またはプロセッサ毎のヒープからのみ行い、解放されたスーパーブロックの多くはグローバルなヒープに戻して他のプロセッサが使えるようにする。このようにしてHoardではスレッド数に対してほぼ比例したスケーラビリティを維持しつつ、フラグメンテーションを最小に抑えている。

### TCMalloc (thread-caching malloc)
スレッド毎に小さいメモリ確保のための領域を設ける。大きなメモリ確保にはmmapかsbrkを使用する。TCMallocはGoogleが開発したもので、スレッドが終了した際にローカルな領域を掃除するガベージコレクション機能を備えている。マルチスレッド環境では、glibcのptmallocの2倍以上の性能を発揮するという。

### カーネル内
OSのカーネルでもアプリケーションと同様にメモリ確保が必要である。カーネル内にも`malloc`相当の関数はあるが、その実装はCライブラリのものとは大きく異なる。例えば、DMA用のバッファには特別な制限が課せられることがあるし、割り込み処理でメモリを動的に確保したい場合もある。このため、カーネルの仮想記憶サブシステムと密に連携した `malloc` 実装が要求される。

## 最大確保サイズ
`malloc`が確保できるメモリブロックの最大サイズはシステムに依存する。特に物理メモリ量とOSの実装に依存する。ディスクスワップによる仮想記憶をサポートしているシステムでは、物理メモリの空きが不足していてもストレージをメモリの代わりに使うため、その許容範囲内であれば`malloc`が成功する可能性はある。ただし、たとえ`malloc`が成功してnon-nullの値を返したとしても、実際に物理メモリやスワップ領域に十分な空きがあったかどうかは分からない。Linuxの場合、物理メモリを使い切ってしまうと、`malloc`で確保した仮想アドレス空間内のメモリ領域にデータを書き込もうとした時点で、仮想アドレスから物理アドレスへのマッピングが失敗し、OOM Killer (Out of Memory Killer) によってプロセスが強制終了されてしまう可能性がある。

引数`size`の型`size_t`は、演算子の結果を表す符号なし整数型であり、それ以上の意味は持たないが、一般的な実装ではポインタと同じサイズを持つ型として定義されている。`size_t`の最大値は、C99ではマクロ定数`SIZE_MAX`によって規定されており、少なくとも65535以上であることが保証されているが、一般的な実装ではと等しく、プロセスの論理アドレス空間の上限値となっているため、そのようなサイズのヒープ確保を試みても絶対に失敗する（または異常動作を引き起こす）。

Microsoft Visual C++では、許可されるユーザーリクエストの最大サイズがマクロ定数`_HEAP_MAXREQ`によって規定されている。32ビット環境では`0xFFFFFFE0`に、64ビット環境では`0xFFFFFFFFFFFFFFE0`に展開される。この値はヒープ確保のリクエストが許可されるという意味であり、実際に成功するという保証値ではない。もしリクエストされたサイズが`_HEAP_MAXREQ`を超える場合、`errno`は`ENOMEM`に設定され、呼び出しは失敗する。

## C++での利用
C++でも`malloc`関数は利用できるが、この利用は後述の問題を引き起こすため推奨されない。C++では言語の機能としてnew演算子、delete演算子が用意されている。`malloc`で確保したメモリ領域に対して`delete`したり、逆に`new`で確保した領域を`free`したりすると結果は未定義となる。`malloc`によって生まれたポインタと`new`によって生まれたポインタの混在はバグの温床であり、また、new/delete演算子と違い、malloc/free関数ではクラスのコンストラクタとデストラクタが呼ばれないという違いもあり、C++での`malloc`は禁じ手の扱いである。

## 脚注

### 注釈

### 出典

## 関連項目
* バッファオーバーラン
* メモリデバッガ
* メモリ保護
* New演算子

## 外部リンク

* 英語ページ
** Definition of malloc in IEEE Std 1003.1-2017 standard - POSIX
** malloc(3) - Linux manual page
** Gloger, Wolfram; ''The ptmalloc homepage''
** Berger, Emery; ''The Hoard homepage''
** Douglas, Niall; ''The nedmalloc homepage''
** Evans, Jason; ''The jemalloc homepage''
** Berger, Emery; ''Hoard: A Scalable Memory Allocator for Multithreaded Applications''
** Michael, Maged M.; ''Scalable Lock-Free Dynamic Memory Allocation''
**Memory Reduction (GNOME) wiki page with lots of information about fixing malloc
**C99 standard draft, including TC1/TC2/TC3
**Some useful references about C
**ISO/IEC 9899 – Programming languages – C
** Bartlett, Jonathan; ''Inside memory management'' - The choices, tradeoffs, and implementations of dynamic allocation
*日本語の解説
** Man page of MALLOC - JM Project
** 
**