メモリアロケータの内部（buddy systemとslab）

三層構えのアロケータ

メモリ割当は単層ではありません。カーネル内の物理ページ割当 と、その上に乗る 小オブジェクト割当、さらにユーザー空間の malloc が階層をなします。下の層ほど粒度が粗く、上の層ほど細かい要求を捌きます。各層が解く問題は共通で、確保・解放を高速にしつつ断片化を抑える ことです。

ユーザー空間: malloc/free  ← ptmalloc / tcmalloc / jemalloc（アリーナ + ビン）
   ↑ 足りなければ brk / mmap でページを要求
カーネル:    slab/slub/slob ← 小さなオブジェクト（数十〜数百バイト）
   ↑ ページ単位で要求
カーネル:    buddy system   ← 物理ページ（4KB の 2^n 倍）

buddy system：物理ページの分割と統合

Linux の物理ページ割当の中核が buddy system です。空きメモリを 2のべき乗ページ数のブロック（4KB×2^order、order=0〜10 が典型）で管理し、order ごとに空きブロックの フリーリスト を持ちます。

確保の流れはこうです。要求サイズ以上で最小の order を選び、その order に空きが無ければ 1つ上の order を半分に割る。割った片割れが buddy（相棒） で、もう片方をフリーリストに戻します。

order=2 (16KB) を要求、空きは order=4 (64KB) だけのとき:
[ 64KB ]            (order 4)
[32KB][32KB]        (order 4 → 3 に分割、片方を free list へ)
[16KB][16KB][32KB]  (order 3 → 2 に分割、片方を free list へ)
 └払出  └free  └free

解放時は逆で、自分の buddy も空いていれば即座に統合（coalesce） して上の order に戻します。buddy のアドレスは「ブロック先頭アドレス XOR ブロックサイズ」で O(1) に求まるのが巧妙な点です。

buddy は 外部断片化（空きの総量は足りるのに連続した大ブロックが取れない状態）を統合によって強力に抑えます。空き状況は /proc/buddyinfo で order 別に観察できます。物理ページと仮想アドレスの対応は 仮想記憶（ページング） を参照してください。

slab/slub/slob：オブジェクト単位の再利用

カーネルは task_struct や inode など 固定サイズの小さな構造体 を頻繁に作っては壊します。これをページ単位の buddy で扱うと、数百バイトのために 4KB を丸ごと使い、内部断片化が爆発します。そこで間に挟むのが slab アロケータ です。

仕組みの核は次の3点です。

• キャッシュ単位：オブジェクトの型ごとに専用キャッシュ（kmem_cache）を作る。buddy から取った1〜数ページを slab とし、同型オブジェクトでびっしり敷き詰める。
• 構築済みの再利用：解放されたオブジェクトは初期化済みの状態でリストに戻る。次の確保は コンストラクタを省いて即返せる。
• キャッシュ局所性：同型を連続配置するため CPU キャッシュに乗りやすい。

現在の既定は slub です。slab のロック多用とメタデータ肥大を見直し、メタ情報を struct page 側へ寄せ、CPU ごとのアクティブ slab を持たせてロックなしの高速パスを作りました。slob は連結リスト1本で済ませる最小実装で、速度よりフットプリントを優先します。状況は /proc/slabinfo で確認できます。

ユーザー空間の malloc：アリーナとビン

malloc/free はカーネルではなく C ライブラリ側 の実装です。内部では brk や mmap で まとめてページを確保し、それを細かく切り分けて再利用します。毎回システムコールを呼ばないのが速さの源です（システムコールの境界は システムコール を参照）。

設計の二本柱が アリーナ と ビン です。

• アリーナ（arena）：割当用メモリ領域の独立した塊。スレッドごと（または少数）に分けることで、ロック競合 を避けてマルチスレッドでスケールさせる。
• ビン（bin）：解放済みチャンクを サイズ別に並べたフリーリスト。同サイズの再利用要求に即応する。

主要3実装の戦略はこう違います。

glibc の ptmalloc では、小さな解放は tcache（スレッドローカルの単方向リスト）に入り、ロックも整合性チェックも最小で再利用されます。あふれた分が fastbin/smallbin などアリーナ共有のビンへ回ります。tcmalloc と jemalloc はこの「スレッドローカルで捌き、足りなければ中央へ」という二段構造をより徹底し、サイズクラス（要求を離散的な代表サイズに丸める）でビンを整理します。

まとめ

• buddy system は物理ページを2のべき乗ブロックで管理し、分割と O(1) 統合で外部断片化を抑える。
• slab/slub/slob はページより小さい型固定オブジェクトを専用キャッシュで再利用し、内部断片化と初期化コストを削る。既定は slub。
• ユーザー空間の malloc は brk/mmap で取ったページを アリーナ と サイズ別ビン で捌き、スレッドローカルキャッシュでロック競合を避ける。
• 三層に共通する敵は 断片化 と ロック競合。各層が粒度に応じた戦略で同じ問題を解いている。

メモリ全体の地図は メモリ管理（スタックとヒープ）、ページとフレームの対応は ページングとスワップ と合わせて読むと、確保から物理メモリまでが一本につながります。