← OSと低レイヤのしくみ コース
11. freeしたメモリはどこへ行くのか — chunkとbin
free() したメモリがOSに返らず、glibc malloc の中でどう分類・保管されて次の malloc に再利用されるのかを図で追っていきましょう。
① 返されたポインタの直前には管理情報がある
p = malloc(100)アプリが受け取るポインタ
p が指す場所の「直前」にヘッダがある
サイズと制御ビットこの chunk 全体の大きさを保持
p より低位アドレス側ユーザ領域p はここの先頭を指す
100バイト以上が使えるmalloc が管理する単位としてまとめると
1個の chunkヘッダ + ユーザ領域
free(p) のとき
p からヘッダを逆算して読むサイズ引数なしで解放できる理由
- ・malloc(3): free() は p が指すメモリを解放するが、p は malloc() などが以前に返したものでなければならない
- ・free() にサイズを渡さなくてよいのは、大きさが chunk 側に記録されているからです
- ・要求した100バイトちょうどではなく、アラインメントとヘッダの都合で実際の chunk はやや大きくなります
- ・ヘッダはユーザ領域の外側なので、確保した範囲を超えて書くと管理情報を壊します
malloc が返すポインタは chunk の先頭ではなく、ユーザ領域の先頭です。直前のヘッダにサイズが入っているため、free() は引数ひとつで解放できます。
② free() はOSに返さず、空きリストに繋ぐ
free(p)アプリから見た「解放」
実際に起きること
chunk に「空き」と印を付ける領域そのものは返さない
bin の連結リストに繋ぐ空き chunk 同士を辿れるようにする
リストのポインタはどこに置くか
使わなくなったユーザ領域を流用空き chunk の中に前後のリンクを書く
追加のメモリを使わない工夫結果として
次の malloc から見える在庫になるシステムコールなしで再利用できる
- ・malloc(3): すでに解放済みの p を再び free() した場合など、規定外の使い方では未定義動作となります
- ・空き chunk の中身をリンクの置き場に流用できるのは、もう誰も中身を読まない前提だからです
- ・だからこそ解放後のポインタを使うと、リンク構造を読んでいることになり壊れ方が予測できません
- ・OS から見ると、プロセスの常駐サイズは free() しても即座には減りません
free() は「OSへの返却」ではなく「在庫への登録」です。空き chunk はリストに繋がれ、次の malloc の候補として残り続けます。
③ サイズ帯で保管棚を分ける
解放された chunkサイズによって行き先が決まる
まず最速の棚へ(スレッド専用)
tcacheスレッドごとの小さなキャッシュ
64bitで要求1032バイトまでtcache が対象外・満杯なら、まず一時置き場へ
unsorted bin分類前にいったん入る場所
次の探索時に適切な bin へ振り分け探索のついでにサイズ帯ごとの棚へ振り分けられる
fastbin小サイズ・同一サイズごと
64bitで既定128バイトまでsmall bin中程度のサイズ帯
large bin大きいサイズ帯
サイズ範囲を持つ- ・glibc tunables: glibc.malloc.tcache_max の既定かつ最大は64bitで1032バイト、32bitで516バイト
- ・glibc tunables: glibc.malloc.tcache_count の既定は7(各サイズごとにキャッシュする個数)
- ・mallopt(3): M_MXFAST の既定は 64*sizeof(size_t)/4 で、32bitでは64バイト、64bitでは128バイトになります
- ・mallopt(3): M_MXFAST に0を指定すると fastbin を無効にできます
- ・unsorted bin は「まだ分類していない」状態で、すぐ同じサイズが再要求される場合に無駄な整理を省けます
全部を1本のリストにすると探索が遅くなります。サイズ帯ごとに棚を分けることで、目的の大きさの空きを短い手数で見つけられます。
④ 隣り合う空きは結合して大きく戻す
連続する3つの chunkA・B・C がアドレス順に隣接している
A と C を解放した直後
A: 空き32バイト
B: 使用中間に挟まっている
C: 空き32バイト
この状態では64バイト要求に応えられない
空きは合計64バイトあるのに使えないこれが断片化
その後 B も解放されると
A+B+C を1個の大きな chunk に結合ヘッダのサイズを更新して1個にまとめる
- ・mallopt(3): fastbin は隣接する空きブロックを結合せずに同一サイズのブロックを保持する領域である
- ・mallopt(3): fastbin は再割り当てを高速化する一方、断片化とメモリ使用量を増やす
- ・結合には「隣の chunk が空きかどうか」を知る必要があり、そのためヘッダの制御ビットが使われます
- ・fastbin に溜まった chunk も、大きな要求が来たときなどにまとめて結合されます
小さな空きが散らばると、合計では足りているのに要求に応えられません。隣接する空きを結合して大きな塊に戻すのが coalescing です。
⑤ 次のmallocはbinから在庫を探す
malloc(100) が再び呼ばれるまず在庫から探し始める
まずスレッド専用の棚を見る
tcache に合うサイズはあるかあれば即座に取り出して返す
ロック不要で最速なければサイズ帯の棚を順に探す
fastbin / small bin同一サイズなら即利用
unsorted bin を整理しつつ探索通りがけに各 bin へ振り分け
large bin大きめの空きを探す
見つかった chunk が要求より大きい場合
必要な分だけ切り出す(split)残りは空き chunk として bin に戻す
どこにも無ければ
ヒープを伸ばす / mmap するここで初めてシステムコール
- ・malloc(3): 通常はヒープから割り当て、必要に応じて sbrk(2) でヒープのサイズを調整する
- ・malloc(3): MMAP_THRESHOLD バイトより大きい要求は、mmap(2) による無名マッピングとして確保される
- ・bin に在庫がある限り、malloc はユーザ空間のリスト操作だけで完了します
- ・大きすぎる chunk をそのまま返すと無駄が出るため、分割して残りを在庫に戻します
malloc は速い棚から順に在庫を探します。bin に合うものがあればシステムコールは発生せず、free と malloc の往復はその分だけ安価になります。
⑥ なぜスレッドごとにarenaを分けるのか
仮に bin 全体が1組しかないと複数スレッドが同時に malloc/free
リストを壊さないため排他制御が必要
1本の mutex を全スレッドで奪い合う待ち行列ができる
コア数を増やしても速くならない競合が検出されたら arena を増やす
arena A独自の bin と mutex
arena B独自の bin と mutex
arena C独自の bin と mutex
各スレッドは別々の arena を使う
ロックが分散して並列に進めるtcache ならそもそもロック不要
- ・malloc(3): マルチスレッドでのメモリ割り当てをスケーラブルに扱うため、mutex の競合が検出されると glibc は追加の arena を作る
- ・malloc(3): 各 arena はシステムから brk(2) または mmap(2) で確保された大きな領域で、独自の mutex で管理される
- ・glibc tunables: arena_max の既定は0で、このとき arena 数の上限はオンラインのCPUコア数から決まる(64bitはコア数の8倍、32bitは2倍)
- ・arena を分けるとメモリ使用量は増えるため、上限を設けて際限なく増えないようにしています
bin は共有データ構造なので排他制御が要ります。arena を分けてロックを分散させることが、マルチスレッドでの性能を保つための設計判断です。