malloc って何?

はじめに

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
  char *ptr = (char *)malloc(sizeof(char) * 10);
  strcpy(ptr, "hello");
  printf("%s\n", ptr);
  free(ptr);
}

malloc はメモリの動的確保を行う関数で、大体こんな感じで使います。

でも、この中で何が起きているかをちゃんと説明できるでしょうか。

OS からメモリをどう借りて、どう小分けして配って、どう返しているのか。気になったので、最小構成で自分で書いて確かめてみました。その過程で得られた知見を記します。

malloc() 関数は size バイトを割り当て、割り当てられたメモリーに対するポインターを返す。
—— malloc(3)

一見、malloc が呼ばれるたびに OS とやり取りして、ヒープから必要なバイト数を確保しているように感じます。

しかし、結論から言うと、毎回 OS からメモリをもらってはいません。OS とのやり取りは高コストなので、メモリを払い出すシステムコール mmap(2) で 大きなブロックをまとめて確保 しておき、malloc が呼ばれるたびにそこから必要なサイズだけを切り出して返すというのが、malloc のコアロジックです。

mmap

その「大きなブロック」を OS から貰う際に利用するのが mmap(2) です。

mmap はもともと、ファイルの中身をそのままメモリ上に並べて、ポインタで読み書きできるようにするためのシステムコールです。ファイルを read で少しずつ読む代わりに、「このファイルはメモリ上のこのアドレスにある」と見立てて直接アクセスできるようにする仕組みです。

ただし malloc がほしいのはファイルの中身ではなく、何も入っていない生のメモリ領域です。そこで mmap に MAP_ANONYMOUS（匿名）というフラグを渡します。すると「どのファイルにも紐づかない、まっさらなメモリ」をプロセスのアドレス空間に新しく生やせます。malloc はこの匿名 mmap を使って、OS から白紙のメモリ領域を受け取るわけです。

void *p = mmap(NULL, length,
               PROT_READ | PROT_WRITE,      /* 読み書き可で確保 */
               MAP_ANONYMOUS | MAP_PRIVATE, /* 匿名・コピーオンライト */
               -1, 0);                      /* fd=-1, offset=0 */

• MAP_ANONYMOUS … ファイル無し。ゼロ初期化された無名メモリをもらう
• MAP_PRIVATE … CoW（コピーオンライト）で他プロセスと共有しない
• addr=NULL … 配置はカーネル任せ。

mmap が成功してアドレスが返ってきても、その時点ではまだ実際のメモリ（RAM）はもらえていません。カーネルは「このアドレス範囲はこのプロセスが使ってよい」と帳簿に書き込むだけです。実際の RAM は、そこに初めて書き込んだ瞬間に、触れたページ（多くの環境で 4096B 単位）だけ後から割り当てられます(demand paging)。おかげで「とりあえず大きく mmap しておく」のは安く済みます。実際にかかるコストは確保サイズの大きさではなく、カーネルへ降りるシステムコール 1 回ぶんの手間のほうで、これが「毎回 mmap せず、まとめて借りておく」動機になります。

mmap が返すのはページ単位の領域です。ページサイズは sysconf(_SC_PAGESIZE) （多くの環境で 4096B）で取得でき、要求した length はこのページの倍数に切り上げられます。裏を返すと、1 バイトしか要らなくても最低 1 ページ消費する、という粒度の粗さがあります。

munmap

mmap で借りた領域を OS に返すのが、対になる munmap です。

munmap(addr, length);

munmap を呼ぶと、その領域はプロセスのアドレス空間から外され、割り当たっていた物理ページも OS に戻ります。以降そのアドレスへアクセスするとフォールト（SIGSEGV）になります。mmap と同じくページ単位で扱われ、領域の一部だけを返すこともできます。

自作の malloc では、mmap でまとめて借りたゾーンがまるごと空いたときに、そのゾーンを munmap で返します（どのタイミングで返すかは後述）。これで「借りる ＝ mmap / 返す ＝ munmap」がワンセットになります。

データ構造とメモリレイアウト

mmap でまとめて借りたメモリは、そのままでは大きな 1 枚の板でしかありません。これを細かな要求に小分けして配れるよう、malloc は確保したメモリを独自に定義した構造体のリストとして扱い、要求サイズに合わせて切り出せるようにします。

例えば、簡易的に構造体で表すと次のようになります。

typedef enum e_zone_type { ZONE_TINY, ZONE_SMALL, ZONE_LARGE } t_zone_type;
/* mmap で借りた大きな領域 */
typedef struct s_zone {
  struct s_zone *next;
  t_zone_type   type;
  size_t        total_size;
} t_zone;

/* チャンク：ゾーンを切り分けた割り当て単位 */
typedef struct s_chunk {
  size_t          size;
  int             in_use;
  struct s_chunk  *prev;
  struct s_chunk  *next;
} t_chunk;

まとめて借りた大きな領域を ゾーン（t_zone）、そこから切り出す個々の単位を チャンク（t_chunk）と呼ぶことにします。

ゾーン という命名をしたのはこの記事独自です。

それぞれの構造体を図示すると以下のようになります。

ゾーン

#define ALIGNMENT 16
#define ALIGN_UP(x) (((size_t)(x) + (ALIGNMENT - 1)) & ~(size_t)(ALIGNMENT - 1))
#define ZONE_HDR ALIGN_UP(sizeof(t_zone))
#define CHUNK_HDR ALIGN_UP(sizeof(t_chunk))

ALIGN_UP(x) は、引数を 16 バイト境界へ切り上げる処理です。

一つの zone にいくつのチャンクを含める設計にするかはハイパーパラメータです。

チャンク

ゾーンもチャンクも、レイアウトは「管理用のヘッダ ＋ 本体」という同じ形です。チャンクならヘッダの直後がユーザーに渡すアドレスで、malloc はヘッダ分だけ進めたポインタを返します。逆に free(ptr) では、受け取ったポインタからヘッダ分だけ戻れば、サイズや使用中フラグを記録したヘッダにたどり着けます。ゾーンも同様に、mmap で借りた領域の先頭にゾーンヘッダを置き、その後ろにチャンクを並べます。

ここで効いているのは、管理情報を借りたメモリの中に同居させている点です。もしヘッダを別の場所に持とうとすると、その置き場所を確保するため malloc を呼ぶ、という鶏と卵の問題に陥ります。借りた領域の先頭にヘッダを書き込んでしまえば、管理のための追加確保は一切不要になります。

この「ヘッダ ＋ 本体を連続して並べ、ヘッダを読んで本体を解釈する」構造は、ネットワークパケットによく似ています。パケットも先頭のヘッダに宛先や長さを書き、その後ろにペイロードを続けます。

malloc の仕組み

malloc の処理としては以下の通りです。

malloc(size)
  │
  ├─ size == 0            → NULL
  ├─ want = ALIGN_UP(size) （16バイト境界へ切り上げ）
  ├─ サイズで TINY / SMALL / LARGE を判定
  │
  ├─[TINY/SMALL] 既存ゾーンを走査
  │     ├─ 空きチャンクが見つかった → 必要なら分割して in_use=1 → ユーザーデータの先頭ポインタ返す
  │     └─ 見つからない            → 新ゾーンを mmap して先頭チャンクを使う
  │
  └─[LARGE] 専用ゾーンを mmap → 先頭チャンクを返す

サイズの 3 分類（TINY / SMALL / LARGE）は、glibc など本物の malloc が行っているサイズ判定を簡略化したものです。要求サイズを見てどの分類に入れるかを決めますが、その境目の値（閾値）は、性能とメモリの無駄のバランスを見て選ぶ設計パラメータで、絶対の正解があるわけではありません。

分類のうれしさは断片化対策です。同じくらいの大きさのチャンクが 1 つのゾーンに並ぶので、解放された枠を次の同程度の要求にそのまま再利用でき、隙間が細切れに残りにくくなります。小さい側を TINY と SMALL の 2 段に分けているのも、1 つの帯で広いサイズ範囲を賄うと小さな要求に大きな枠を当てて無駄が出るためです。

一方 LARGE は、めったに来ないと仮定してまとめ借りせず、要求のたびに専用の領域を mmap します。

見つけたチャンクが要求より十分大きいときは分割して、余りを新しい空きチャンクにします。

一点だけ注意がいるのが、要求サイズのオーバーフロー対策です。

malloc の引数は size_t なので、素朴には「size_t で表せる値ならそのまま受け付けてよい」と思いがちです。しかし本実装は、受け取った size をまず ALIGN_UP で 16 バイト境界へ切り上げます。この切り上げは内部で size + 15 を計算するため、上限近い値が入力されるとオーバーフローが発生します。

if (size > PTRDIFF_MAX)
    return NULL;
size_t want = ALIGN_UP(size);

PTRDIFF_MAX はおおよそ SIZE_MAX の半分なので、ここを通った size は + 15 してもオーバーフローしないことが保証されます。
なお「PTRDIFF_MAX が SIZE_MAX の半分以下」という前提は、_Static_assert(PTRDIFF_MAX <= SIZE_MAX / 2, ...) のようなコンパイル時チェックで固定しておくと、前提が崩れる環境ではビルドが通らず安全側に倒せます。

また、空きチャンクの確認は物理順に並んだチャンクを先頭からなめて in_use == 0 を探すという素朴な方式で実装できます。

free の仕組み

free(ptr) は malloc の逆をたどります。

free(ptr)
  │
  ├─ ptr == NULL → 何もしない（C標準の要件）
  │
  ├─ ptr が自前ゾーン内か検証 → 違えば無視
  │
  ├─ chunk = ptr - CHUNK_HDR  （ヘッダに戻る）
  ├─ chunk->in_use = 0        （空きにする）
  ├─ 隣接する空きチャンクと結合（coalescing）
  │
  └─ ゾーンが空になった or LARGE → munmap で OS に返す

free(ptr) がやることを、上から順にたどってみます。

まず ptr が NULL なら、何もせずに返ります。これは free(NULL) を no-op とする C11 の要件で、本物の glibc free も同じく冒頭で早期 return します。

NULL でなければ、渡されたポインタからヘッダを復元します。チャンクのヘッダはユーザー領域のすぐ手前にあるので、ptr - CHUNK_HDR と戻すだけでサイズや前後リンクが読めます。ただしこのポインタ演算が成り立つのは「自分が配ったポインタ」に限ります。そこでヘッダに戻る前に、まず「このポインタは本当に自分のゾーン内を指しているか」を範囲チェック等で確かめ、無関係なポインタは安全に無視します。

自分のチャンクだと確認できたら、あとはヘッダの in_use を 0 に戻すだけで解放そのものは完了します。

void *a = malloc(32);   // チャンク A
void *b = malloc(48);   // チャンク B
void *c = malloc(16);   // チャンク C
void *d = malloc(64);   // チャンク D

free(b);   // B を解放 → 両隣 A・C が使用中なので、孤立した空き穴になる
free(d);   // D を解放 → 後ろの「残り（空き）」と隣接する

malloc がゾーンの先頭から順にチャンクを切り出すのに対し、free はそのチャンクを空きに戻すだけ、というのは前述のとおりです。ただし、ただ空きにするだけだとチャンクの位置によって後始末の質が変わります。図のように A〜D を確保してから B と D を解放すると、free(b) で空いた B は両隣（A・C）が使用中なので孤立した空き穴として取り残されます。一方 free(d) で空いた D は後ろの「残り」と隣接しているので、つなげて 1 つの大きな空きにできます。

この「隣り合う空きをつなぐ」処理が結合（coalescing）です。解放したチャンクの前後が空きなら、物理的にくっつけて 1 つの大きな空きにまとめます。これをサボると小さな空きが細切れに残り、総量は足りていても余分に zone の追加確保 (mmap) を必要とします。

つまり、チャンク同士の結合とは、以下のコードで記述することができます。

void chunk_merge(t_chunk *keep, t_chunk *victim) {
  keep->size += CHUNK_HDR + victim->size;
  keep->next = victim->next;
  if (victim->next != NULL) {
    victim->next->prev = keep;
  }
}

void chunk_coalesce(t_chunk *c) {
  if (c == NULL) {
    return;
  }
  t_chunk *c_prev = c->prev;
  t_chunk *c_next = c->next;

  if (c_next != NULL && c_next->in_use == 0) {
    chunk_merge(c, c_next);
  }
  if (c_prev != NULL && c_prev->in_use == 0) {
    chunk_merge(c_prev, c);
  }
  return;
}

そして結合を重ねた結果、ゾーンが「1 個の空きチャンク」だけになったら、つまりそのゾーンが完全に空になったら、そのゾーンごと munmap で OS に返します。ただし、それが最後の 1 ゾーン（ほかにゾーンが残っていない状態）のときだけは残します。空になるたびに munmap して、次の確保ですぐ mmap し直す無駄を避けるためです。LARGE は 1 ゾーン = 1 アロケーションなので、free すれば（最後の 1 個でない限り）そのまま munmap されます。

付録: 本物の malloc はどうしているか

ここからは自作版を離れ、本物のアロケータ（glibc や各種実装）が同じ問題をどう解いているかの補足です。自作版の設計（TINY/SMALL/LARGE の 3 ゾーンにまとめて mmap）が、どこを単純化したものなのかを対応づけて読めます。

glibc の二段構え

glibc（ptmalloc2）は要求サイズで経路を分けます。この分岐は新しいゾーンを OS から確保するsysmalloc() の中にあり、要求サイズ nb が mmap_threshold 以上なら（ヒープを伸ばさず）直接 mmap します。

ここで出てくる brk/sbrk は、プロセスのヒープ（連続した 1 本のデータ領域）の上端を上下させて領域を伸縮させる、古くからあるシステムコールです。mmap が好きな場所に独立した領域を取れるのに対し、brk は 1 本の連続領域を端から伸ばすだけ——この違いが、後で出てくる「真ん中だけ返せない」弱点につながります。

出典: malloc/malloc.c L2317-2319

if (av == NULL
    || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
        && (mp_.n_mmaps < mp_.n_mmaps_max)))

mmap_threshold の既定値 128KB は L195（#define DEFAULT_MMAP_THRESHOLD 128 * 1024）、
構造体への初期設定は L1808（.mmap_threshold = DEFAULT_MMAP_THRESHOLD）。

malloc(size)
   │
   ├─ size <  MMAP_THRESHOLD(既定128KB) → ヒープから切り出す（足りなければ brk で伸ばす）
   │                                       free してもOSには返さず再利用に回す
   │
   └─ size >= MMAP_THRESHOLD             → mmap で独立領域を確保
                                           free したら munmap で即OSに返す

サイズ	仕組み	解放時
小さい	brk/sbrk で伸びるヒープ内に割り当て	OS に返さず再利用待ち
大きい	mmap で個別確保	munmap で即 OS に返す

なぜ分けるかというと、両者に弱点があるからです。brk のヒープは連続領域なので真ん中だけ解放しても OS に返せず断片化しやすいです。一方 mmap は free 時に即返せて巨大確保にも強いのですが、syscall + ページテーブル更新でコストが高く、1 バイト要求でもページ単位（4096B）を消費してしまいます。

サイズクラスの刻み方（bin）

自作版は簡略化のため、サイズを TINY / SMALL / LARGE の 3 バンドにしか分けませんでしたが、glibc はもっと細かく、128 本の bin（NBINS）でサイズクラスを刻みます。

• small bins（64 本・NSMALLBINS）… 16 バイト刻みのぴったりサイズ。インデックスは smallbin_index(sz) = sz >> 4 と、ただのビットシフトで引けます。上限は MIN_LARGE_SIZE（= 64 × 16 ≒ 1KB）。
• large bins（それ以上）… 1 本が 1 サイズではなくサイズの範囲を受け持ち、しかもその幅が大きいサイズほど広がっていきます（>> 6 → >> 9 → >> 12 … と、上の桁ほど粗く丸める）。記憶にある「2 の何乗で刻む」はこれで、大物ほどバケツを対数的に粗くまとめています。
• さらにスレッドごとの tcache や fastbins も、やはり 16 バイト刻みのサイズクラスで空きを抱えます。

出典（いずれも glibc 2.43.9000 / SHA 固定）:
bin 定義 L1532-1536（NBINS 128 / NSMALLBINS 64 / SMALLBIN_WIDTH / MIN_LARGE_SIZE）、
smallbin_index L1541、
largebin_index_64 L1564

Free リスト

glibc は、空きチャンクを**サイズクラスごとの双方向リスト（bin）**につないで管理します。各チャンクは前後の空きチャンクを指す 2 本のポインタ fd（次へ）/ bk（前へ）を持ち、確保要求が来たら該当 bin をたどって再利用します。

ここで巧妙なのが、その fd/bk を、空きチャンクの「ユーザーデータ領域」に間借りさせている点です。チャンクのヘッダはサイズとフラグだけで、fd/bk 専用のフィールドを持ちません。代わりに同じ場所を二役で使います。

• 確保中：ヘッダの直後（mem、ユーザーに返すアドレス）から先はユーザーデータ
• 空き：その mem と同じ位置に fd/bk を書く（どうせ中身は使われていないので間借りできる）

この設計の利点は、ヘッダを太らせずに済むことです。リンクは「空いている間だけ使う遊休領域」に置くので、確保中チャンクはサイズ＋フラグの最小ヘッダで済み、容量効率が落ちません。代償として、チャンクは最低でも fd＋bk（ポインタ 2 本）を収められる大きさが要ります。

出典（glibc 2.43.9000 / SHA 固定）:
struct malloc_chunk L1076、
確保中／空きチャンクのレイアウト図 L1130、
MIN_CHUNK_SIZE L1231

まとめ

malloc は「呼ばれるたびに OS からもらう」のではなく、mmap で大きくまとめて借りておき、その中を小分けして配るというロジックの関数です。

mmap で借りた領域の先頭に管理ヘッダを同居させ、チャンクは「ヘッダ ＋ 本体」の決まった形で並べる。malloc はその形に従ってヘッダ分だけ進めたポインタを返し、free は逆にヘッダ分だけ戻ってサイズや使用状態を読む。両者が同じレイアウトの約束を共有しているからこそ、配ったポインタ 1 つから元の管理情報をたどり直せます。

本物の glibc はもちろんのこと、マルチスレッド環境向けに高速化された malloc 実装であるgoogle/tcmalloc はさらに緻密に作り込まれています。この記事に記した以外にもまだまだ捉え切れていない最適化が積もっているようです。

だてに歴史のある関数ではない、と調べていて素直に面白かったです。