malloc 内部: ptmalloc2

カバー範囲: ptmalloc2 (glibc) → arenas/bins → mmap threshold → tcmalloc / jemalloc 比較 → デバッグ方法 対象: glibc 2.x

概要

glibc の malloc は ptmalloc2 (pthread malloc v2) をベースにしており、dlmalloc のマルチスレッド対応版です。核となる思想は、スレッドごとに独立した分配用 arena を持ち、ロック競合を減らすことです。小さな割り当ては bins（フリーリスト）から取得し、大きな割り当ては直接 mmap を行います。内部メカニズムを理解することは、「malloc の遅延」「メモリ断片化」「RSS が実際の使用量を大幅に超える」などの問題解決に不可欠です。

Arena: スレッド独立のヒープ

dlmalloc (シングルスレッド): ヒープ 1 つ、ロック 1 つ
ptmalloc2 (マルチスレッド): 複数の arena

arena (分配領域):
  メイン arena (main_arena): brk/sbrk で拡張（[heap] 領域内）
  サブ arena:             mmap で割り当て（mmap 領域内、匿名）

スレッド割り当て時:
  1. 直前に使用した arena（TSD でキャッシュされている）を試す
  2. その arena が他のスレッドによって保持されている場合 → 次の arena を試す
  3. すべての arena で競合が発生する場合 → 新しい arena を作成（最大 8×CPU コア数）

戦略: arena 数でロックレスの並列性を確保 → マルチスレッドで割り当てが集中するプログラムに適している
欠点: arena が増えすぎると → メモリ断片化（各 arena が独自の top chunk を持つため）

Bins: フリーリスト

ptmalloc2 は、解放された空きブロックを bins で管理します:

Fastbins (LIFO、単一リンクリスト、マージしない):
  非常に小さな解放（16〜64 バイト、MAX_FAST に依存）に使用
  解放時: fastbin にプッシュ
  割り当て時: fastbin から取得（一致すれば使用、不一致ならマージ）

Small bins (FIFO、循環双方向リンクリスト):
  サイズ: 32〜1024 バイト（64 個の bin、各 bin 8 バイト刻み）
  隣接する空きブロックは自動的にマージされる

Large bins (FIFO + ベストフィット):
  サイズ: 1024 バイト以上（63 個の bin、bin ごとに異なる刻み幅）
  ベストフィット: size 以上の最小の空きブロックを探す

Unsorted bin (キャッシュ層):
  新しく解放されたブロックはまずここに入れる（LIFO）
  割り当て時: 走査 → 完全一致？ 返す : 対応する small/large bin に配置

割り当てフロー

flowchart TD
    START["malloc(size)"]

    START --> THRESH{"size &lt; 128KB<br/>(M_MMAP_THRESHOLD)?"}

    THRESH -->|"はい → bins パス"| FAST{"size &lt; MAX_FAST<br/>(約 64B)?"}
    THRESH -->|"いいえ → 大割り当て"| MMAP["mmap(anonymous)<br/>独立したマップ<br/><br/>free 時に munmap<br/>fork Friendly: COW 対象外"]

    FAST -->|"はい"| FB["fastbins を検索<br/>(LIFO、サイズインデックス別)"]
    FAST -->|"いいえ"| SMALL{"size &lt; 1024?"}

    SMALL -->|"はい"| SB["small bins を検索<br/>(FIFO、双方向リスト)"]
    SMALL -->|"いいえ"| LARGE["① unsorted bin を検索<br/>② 一致？ 返す : large bin に配置<br/>③ large bin を検索 (best fit)<br/>④ どれも足りない → top chunk から切り出し"]

    FB --> OK1["✅ 返す"]
    SB --> OK2["✅ 返す"]
    LARGE --> OK3["✅ 返す"]
    MMAP --> OK4["✅ 返す"]

    FB -.->|"ミス"| SMALL
    SB -.->|"ミス"| LARGE
    LARGE -.->|"top chunk も足りない"| FALLBACK["arena を拡張<br/>sbrk (メイン) / mmap (サブ)<br/>再試行"]
    FALLBACK -.->|"依然として失敗"| FAIL["❌ ENOMEM<br/>NULL を返す"]

    classDef start fill:#e3f2fd,stroke:#1565c0
    classDef decision fill:#fff3e0,stroke:#ef6c00
    classDef path fill:#f3e5f5,stroke:#7b1fa2
    classDef ok fill:#e8f5e9,stroke:#2e7d32
    classDef fail fill:#ffebee,stroke:#c62828
    class START start
    class THRESH,FAST,SMALL decision
    class FB,SB,LARGE,MMAP,FALLBACK path
    class OK1,OK2,OK3,OK4 ok
    class FAIL fail

Top Chunk

各 arena には top chunk（ヒープ末尾の残り領域）が 1 つ存在する:
  全ての bin で足りない場合 → top chunk から切り出す → top chunk を拡張（sbrk/mmap）
  解放されたブロックが top chunk の隣にある場合 → top chunk にマージされる

mmap Threshold

// 大割り当て戦略:
#define DEFAULT_MMAP_THRESHOLD (128 * 1024)  // 128KB

// 動的調整: 大きなブロックを free するたびに → threshold が減少する可能性がある
//   → mallopt(M_MMAP_THRESHOLD, value) で固定できる

// なぜ大割り当てに mmap を使うのか？
//   1. 解放直後に munmap → 内核に戻す → RSS が低下
//   2. 独立したマップ → ヒープの断片化を防ぐ
//   3. fork Friendly: 子プロセスは自分自身のものを変更する（COW ではない）

マルチスレッドの落とし穴

偽共有 (False Sharing)

2 つのスレッドが頻繁に割り当て/解放を行う → 同じ arena を共有する可能性がある
  → arena の mutex → 競合 → ロックオーバーヘッド

緩和策:
  malloc_trim(0): 全 arena に対して空き領域を内核に解放させる
  MALLOC_ARENA_MAX: 環境変数で最大 arena 数を制限する

メモリ断片化

異なるサイズの割り当てと解放を頻繁に行う → bins 内の空きブロックが再利用できない:
  例: 512B を割り当て → free → 1024B を割り当て → 512B ブロックは小さすぎる → top chunk から切り出す
  → ヒープは徐々に大きくなるが、実際の使用量は少ない → RSS が高い

検出:
  malloc_stats() または malloc_info(0, stderr) → system bytes と in use を確認

tcmalloc / jemalloc 比較

glibc 以外のアロケータへの切り替え

# 実行時置換（再コンパイル不要）:
LD_PRELOAD=/usr/lib/libtcmalloc.so ./my_program
LD_PRELOAD=/usr/lib/libjemalloc.so ./my_program

デバッグとチューニング

# malloc 統計
MALLOC_TRACE=/tmp/mtrace.log ./my_program  # 全 malloc/free を記録
mtrace ./my_program /tmp/mtrace.log          # リークを分析

# 実行時パラメータ
MALLOC_ARENA_MAX=2 ./my_program             # arena 数を制限
MALLOC_MMAP_THRESHOLD_=65536 ./my_program   # mmap threshold を引き下げる

# valgrind でのチェック
valgrind --leak-check=full ./my_program

# ASAN (コンパイル時)
gcc -fsanitize=address -g -o prog prog.c

# メモリ割り当て統計の表示 (glibc)
#include <malloc.h>
malloc_info(0, stderr);   # XML 形式の詳細統計
malloc_stats();           # 簡易的な stderr 統計

# /proc での観察
cat /proc/<pid>/status | grep Vm

参考

• glibc ソースコード⁠: malloc/malloc.c（約 5000 行、ptmalloc2 の完全な実装）
• ドキュメント⁠: man mallopt, man malloc_info
• LWN: "The design of glibc malloc", "Hoard, tcmalloc, and jemalloc"

キーワード: ptmalloc2, arena, bins, fastbin, mmap threshold, tcmalloc, jemalloc, malloc_stats, ASAN