メモリ管理とアロケータの仕組み：glibc から学ぶ最適化の道筋

1.

malloc

の魔法と実装の背景

malloc は極めてシンプルで使いやすいインターフェースを提供します。

• 特定のサイズのメモリを要求するだけで、連続したバイト列が生成され、

  void*

  として返されます。
• 使用終了時は、同じポインタを

  free()

  に渡すことで、メモリは「虚空（ether）」へ消滅します。

システムコールの overhead

ユーザー空間のプログラムから

malloc

• システムコール（syscall）を通じてカーネルにメモリ割り当てを要求する。
• 多数の小さなブロックを割り当てる試みを繰り返すと、システムコールが高コストになる（例：空の syscall は約 575 ns かかる）。

そのため、バックグラウンドで効率的なメモリの管理が行われます。GNU libc (glibc) における具体的な仕組みは以下のコード例で見られます。

static void *ptrs[1000];

int main(void) {
    for (int i = 0; i < 1000; i++) {
        ptrs[i] = malloc(16);
    }
}

strace

で確認する最適化

このループ全体で、ヒープ拡張を行う

brk

• 1 回目: プログラムブレーク（プロセスのヒープ領域の終了アドレス）を問い合わせる。
• 2 回目: ヒープ領域を拡張させる（例：132 KiB）。

残りの 998 回の割り当ては、既に割り当てられたメモリ領域から確保されます。

$ strace -e trace=brk,mmap,munmap,write \
    ./malloc1000 > /dev/null
...
brk(NULL)              = 0x59faca231000
brk(0x59faca252000)    = 0x59faca252000
+++ exited with 0 +++

補足:

brk

と

sbrk

の関係

• brk

  : 指定アドレスでプログラムブレークを設定するシステムコール。

• sbrk

  : libc のラッパー関数で、増分（Delta）を受け取りプログラムブレークを増加させる。

2. プロセスのアドレス空間とメモリ領域

実行中のプロセスには独自のアドレス空間があり、以下の領域に分かれています。

main

initialised

uninitialised

malloc

#define SHOW(label, p) \
    printf("%-22s %p\n", label, (void *)(p))

SHOW("main (text)", main);
SHOW("initialised (data)", &initialised);
SHOW("uninitialised (bss)", &uninitialised);
SHOW("malloc(16) (heap)", malloc(16));
SHOW("program break", sbrk(0));
SHOW("printf (libc)", printf);
SHOW("local (stack)", &local);

アドレス配置の特徴

• アドレスは、バイナリコード領域からスタック領域に向かって上昇しています。

• malloc

  でヒープを拡張すると、ブレークアドレス（program break）も上昇します。
• 未マップ領域: ブレークと libc の間で数百テラバイトのギャップが存在する場合でも、物理メモリのコストは発生しません（マッピングされていないため）。

3. バンプアロケータ（Bump Allocator）とその限界

プログラムブレークを直接操作できるため、独自の小型アロケータを作成できます。これを「バンプアロケータ」と呼びます。

• 仕組み: 各呼び出しで利用可能なメモリの先端を進めるだけ。
• 欠点: 各リクエストごとにシステムコールが発生する（高コスト）。
• 解放機能: 解放されたメモリの再利用手段を持っていない。

システムコールコストの比較

100 万回呼び出した際の平均時間を測定しました。

syscall(SYS_getppid)

sbrk(16)

malloc(16)

結論:

malloc

sbrk

メモリ断片化のリスク

バンプアロケータは解放したメモリの再利用を行いません。そのため、解放されたメモリ（例:

b

d

4. チャンクとヘッダー

glibc の

malloc

free()

ヘッダー構造

• チャンクサイズは常に 16 の倍数（最低 32 バイト）。
• ヘッダーにはフラグ（Arena, Mapping, Pointer など）が格納されます。
• メリット: ポインタが 16 バイト整列 を保たれ、あらゆる C の型に対応します。

フリーリスト（Free List）の仕組み

• 解放時: チャンクはフリーリストに入れられます。
• 再割り当て時: フリーリストから適合するチャンクを探し、大きくて不要な部分は再分割します。
• 統合 (Coalescing): 隣接するフリーチャンクを結合して大きなブロックを作ります。
  • glibc はサイズの直後に次のチャンクへのポインタを格納し、ユーザーデータを再利用しています。

簡易的なアロケータでも同じ構造を持たせると、以下のようになります。

typedef struct chunk {
    size_t size;
    struct chunk *next;
} chunk_t;

5. 分割と統合（Splitting and Coalescing）の改善

より実用的なアロケータにするために、以下を導入します。

• 丸め上げ: 要求量 + ヘッダーを 16 バイト倍数に調整。
• 分割 (Splitting): 適当なチャンクを取り出し、余りをフリーリストに戻す。
• 統合 (Coalescing): 隣接するフリーチャンクを結合して再利用性を高める。

my_malloc

と

my_free

の実装例

void *my_malloc(size_t size) {
    // フリーリストを検索またはヒープ拡張
}

void my_free(void *ptr) {
    // ヘッダーからチャンクを取得し、隣接フリーチャンクと統合
    // trim() を呼んで不要な領域を解放
}

動作確認

テストでは、

a

b

c

a

b

d

[free chunk]

my_free(a)

[a], [bc...]

my_free(b)

[ab], [c...]

d = malloc(50)

[ab の一部], [d の残りの分]

6. デマンドページング（Demand Paging）

my_free()

• カーネルはアドレス空間を 4 KiB ページ単位で管理しています。
• アドレス空間がマップされていても、書き込まれていないページは物理 RAM に割り当てられていません（空き状態）。
• 仮想ページの最初の書き込み時に初めて物理メモリにマップされます（ページフォールト）。

検証プログラム

1 GiB のメモリを確保し、各ページに 1 バイト書き込むことで、デマンドページングの動作を確認しました。

sbrk

注意:

my_free()

で解放しても、そのページが書き込まれていれば RSS は維持されます。物理メモリのコストは削減されません。

7. メモリの返却（Giving Memory Back）

カーネルにメモリを返すには、ブレークを下げる必要があります。新しい関数

trim()

• ヒープのトップにあるフリーチャンクが閾値（例：128 KiB）を超えると、余計な領域を

  sbrk(-N)

  で解放します。
• ただし、解放しすぎると再び割り当て時にシステムコールが増えるため、**パディング（TOP_PAD）**を残して調整します。

断片化の問題

ヒープのトップしか返却できません。ライブなチャンクがある限り、その以下のフリーチャンクは物理メモリとして維持されます（レジデント）。

• 長い実行により、ライブチャンクの間に多くのフリーギャップが生じます（断片化）。
• これらはレジデント状態のため、RSS を増加させ、メモリ制限でプロセスを終了させる原因になります。

trim()

8. 大規模ブロック用の

mmap

128 KiB 以上の大型ブロックを確保する際、

sbrk

mmap()

mmap

の利点

• 即時解放:

  munmap()

  を呼び出すと、カーネルに即座に戻ります（隣接領域とは独立して）。
• ゼロ初期化: 物理メモリへのマップはデマンドページングにより行われるため、初期コストが低い。
• glibc の活用: glibc は大規模な割り当てやスレッド拡張時に、メインヒープのロック争いを避けるために

  mmap

  で別領域（アリーナ）を作成します。

改善後のアロケータ (

my-mmap-4

)

// 大きなブロックは mmap を使用
static void *map_chunk(size_t need) { ... }

// my_free は mapp ed チャンクを検知して munmap する
void my_free(void *ptr) {
    if (mapped_flag) {
        munmap(ptr); // 即座に物理メモリ解放
        return;
    }
    insert_free(ptr);
    trim();
}

パフォーマンス比較結果

my-bump-1

my-freelist-2

my-trim-3

my-mmap-4

結論:

malloc

はシステムコールを避けるために、大きなブロックをユーザー空間で分割・再結合する工夫をしています。また、glibc の

tcache

（スレッドローカルキャッシュ）や

mmap

しきい値の調整により、さらに高速化・低メモリ化が可能です。

9. リンクと参照

この記事を深く理解するために、以下のリソースを確認してください。

コードの再現性

• 各プログラムのスニペットは再現可能にリンクされています。
• チャンク、バイン（bin）、アリーナ、

  tcache

  について詳しく知りたい場合は、関連記事をご覧ください。

マニュアルページ

標準ライブラリの関数についての詳細は以下の man page を参照してください。

• brk(2)

  /

  sbrk(2)

• mmap(2)

• mallopt(3)

  /

  malloc_trim(3)