読者です 読者をやめる 読者になる 読者になる

malloc の旅 (glibc 編)

すごい分かりやすかった

K&R Malloc (First fit)

Best fit アロケータ

  • アドレス順じゃなくて,サイズ順でソートしてもっとく? → free で併合できない,フラグメンテーションが進む
  • 仕方ないので構造体メンバを増やす:サイズを覚える(=今までと同じリスト),前のサイズも覚える(→前に戻れる),サイズ順リストも覚える
    • free が O(1) になった(前がわかるから)
    • malloc が O(n),ヘッダサイズ大
  • ヘッダサイズ:細かいテクで改善してゆく
    • アドレスの下3ビットが0になることを利用し,そこにつめる
  • malloc:リストを,サイズごとに分けて作っておく
    • 512 バイト以下まで全部作る,それから上は指数的にする
  • それでも超でかいのは困る
    • anonymous mmap./dev/zero を渡すとメモリ確保 API
    • でかいブロックは heap からでなく mmap で直接カーネルから取得

バッファ遅延合体

  • K&R malloc にたまにまける.
  • free されたばっかのところを返すので,キャッシュメモリとの親和性が高い
  • アイディア:バッファ遅延合体
    • free されたばかりのもの,unsorted_chunk=時系列順で管理
  • 典型的なパターン:大構築と定常状態

マルチスレッド

  • 簡単な解法:大域的な lock,スレッドごとのヒープ空間
  • メインアリーナ:ロックがある
  • 2つ目のスレッド,ずっとメインアリーナを使う,でもロック取得に失敗したら自分専用heapをmmapして新しいアリーナ.
  • アリーナのリストというのもある.
  • 3つ目のスレッド,失敗したらさっきの2つ目のアリーナに移動,それでもかぶったら3つ目に移動
  • 必要な分だけアリーナが生成される.終了してしまったスレッドのアリーナを再利用できる.