メモリ割り当て 基礎

スタックは誰も管理していない。呼び出しは rsp を引き、戻るときに同じ数を足す。空きリストも探索もメタデータもない。下ではすでに積まれたフレームの上にいまの呼び出しが積んだフレームが載っている。スライダーで呼び出しの深さを辿ってほしい：

何も探索されないことに注目。ポインタがフレーム自身の大きさだけ動けば割り当ては終わり、解放は同じ命令の符号を変えただけだ。戻ったフレームを指すポインタが「古い」より悪いのもこれが理由で、バイトはまだそこにあり、次の呼び出しがその上に書く。

代価はこの領域が固定であること。Linux は既定で 8 MiB を与え、その下に誰もマップできない1 MiB のガード間隙を置く。フレームの大きさを選び、再帰を上限の先へ押してほしい：

どこで死ぬかはフレームの大きさで決まる。64 バイトならスタックは 131,072 回、ローカルが 8 KiB なら 1,024 回。同じ再帰が、ある関数では安全で別の関数では致命的になる。上限の先へ押しても失敗は大きな音だ。ガード間隙にマッピングはなく、最初に触れた命令でそのまま SIGSEGV になる。

呼び出しより長く生きるものはヒープへ行く。ヒープとは、要求すればカーネルが伸ばしてくれる領域にすぎない。break を引いて、brk 1 回が何を買うのかを見てほしい：

5 回の呼び出しで全部が買える。glibc は成長のたびに必要より 128 KiB 多く要求する ——M_TOP_PAD だ。だから小さな断片で640 KiB を割り当てるプログラムのbrk は 5 回であって 5000 回ではない。システムコールは薄まり、残るのは領域の内側の帳簿 —— それがアロケータだ。

だが break は 1 つの数なので、返せるのは一番上の使用中の割り当てより上にある分だけだ。まだ使われている割り当てを動かし、残りが返せなくなるのを見てほしい：

break は水位なので、上端の 48 KiB の割り当て 1 つがその下の592 KiBを釘付けにする —— アロケータから見れば空き、カーネルから見れば常駐だ。健康なプロセスがリークして見える一番よくある理由がこれで、free をいくら呼んでも直らない。free はページを返す役ではなかったからだ。

glibc は渡すポインタのすぐ手前に 8 バイトの語を 1 つ書く。chunk 自身の大きさだ。free(p) が何も教わらずに p の大きさを知れるのはこれによる。要求の先はすべて整列のためのものだ。要求を引いて、丸めが足す分を見てほしい：

算術は正確だ —— (n + 8 + 15) & ~15、下限は 32。malloc(24) は 32 バイト、malloc(25) は 48 バイト。要求 1 バイトが chunk 16 バイトを買う。 17 バイトの要求に malloc_usable_size が 24 を返すのは、次の chunk のサイズ語がこの chunk の空き時にしか使われないからだ。

固定の 1 語と 16 バイトの格子は、小さなオブジェクトには比例課税、大きなオブジェクトには丸め誤差でしかない。要求を 4 桁ぶん歩かせ、オーバーヘッドが落ちるのを見てほしい：

左端を見てほしい。malloc(1) は 1 バイトのために 32 バイトを取る —— 3,100% だ。24 バイトのノードの連結リストは 32 バイトの chunk に住むので、リストの 4 分の 1 は誰も読まないサイズ欄になる。プールやアリーナの本当の理由はこれで、malloc が遅いからではなく、オブジェクトが小さいとオブジェクト単位の帳簿が薄まらないからだ。

ある閾値を越えると arena は正解でなくなり、glibc は直接カーネルへ行く。要求を 128 KiB の向こうへ滑らせ、経路が変わるのを見てほしい：

境目で変わるのは経路で、大きさではない。 chunk は自分専用のマッピングになってページ単位に切り上げられ、割り当てと解放の 1 組は 0 回だったシステムコールが 2 回になる。 1 つ free すると閾値はその大きさまで上がる —— 上限 32 MiB —— ので、1 MiB のバッファを使い回すプログラムは一度払えば以後払わない。

要求と実物のあいだのこのずれは、最も静かなヒープバグの住処でもある。書き込みを 17 バイトの割り当ての末尾より先へ引き、どこまで届くかを見てほしい：

その割り当ては実際には 24 バイトを持つ。だから末尾から7 バイトまでは誰も読まない詰め物に落ちて何も変えない。テストは通り、レビューも通り、バグは出荷される。8 バイト目が次の chunk のサイズ欄を上書きし、クラッシュはずっと後の無関係な free で届く。大きな音の失敗は、運が良いほうだ。

リストは解放順であって大きさ順ではないので、最初に見つかる十分大きい chunkと最小の十分大きい chunkはたいてい別物だ。要求を決め、規則を切り替え、リストがどこまで読まれるかを見てほしい：

malloc(104) での取引に注目。先着適合は chunk を 2 つ読み、112 バイトのために 512 バイトの塊を切り刻む。最良適合は 8 つ全部を読み、64 バイトを残す。先着適合は安いが大きな塊を壊し、最良適合は守るが O(n) だ。サイズクラスは索引することで両方を買う。

chunk を戻すのがもう半分で、リストが際限なく伸びるのを止めるのはこちらだ。順序を選び、free を 1 歩ずつ進めてほしい：

読むべき数は合計ではなく最大連続領域だ。どの free も隣 2 つを調べ、何と併合しようと併合は高々 2 回だ。だからヒープ全体を 1 つの chunk に潰す free の連続でも、 1 回あたりは定数時間のままになる。真ん中の chunk を生かしておけば、 304 バイトの空きは 224 より大きな連続領域には決してならない。

chunk がどのリストへ戻るかは大きさだけで決まり、glibc の答えは 4 つある。chunk の大きさをその上で歩かせてほしい：

最初の 3 つは索引なので、free も再利用する malloc も、ポインタ 1 つの書き込みと pop で終わる。走査されるのは largebin だけだ。アロケータの最悪ケースが1 キロバイトより上に住み、よくあるケースには最悪ケースがない理由がこれだ。 tcache は 2.26 で追加、bin あたり 7 chunk、ロックなし。

glibc のクラスは前節の 16 バイト格子で、各オブジェクトの前にサイズ語が付く。jemalloc は倍ごとに 4 クラス —— 8、16、32、48、64、80、96 —— でヘッダはない。メタデータが slab 側にあるからだ。表を切り替え、要求を動かしてほしい：

2 つの表は正反対の場所で負ける。16 バイトでは glibc が 32、 jemalloc が 16 を取る。固定の 1 語が小さなオブジェクトを倍にするからだ。513 バイトでは glibc が 528、 jemalloc が 640 を取る。倍ごとに 4 クラスとは、次のクラスが前より 4 分の 1 上にあるということだからだ。

小さい範囲全体を描くと、2 つの表の交点はちょうど 1 つだ。要求をそこへ歩かせ、両方の無駄を同時に読んでほしい：

交点は 129 バイト。その下では glibc の格子が細かく、ヘッダが費用のすべてだ。上では jemalloc のクラス間隔が支配し、境界の 1 バイト先で 25% に達する ——8,277 バイトで jemalloc は 23.7%、glibc は 0.1%。 65 バイトの構造体は 80 を要し、64 に詰めれば 5 分の 1 が戻る。

クラスは設計の半分だ。もう半分は切り出し元のslab で、slab はページ単位なので、ページ数は端材が小さくなるように選ばれる。クラスを選び、slab がそれに従うのを見てほしい：

扱いにくいクラスは 1 ページで済まない。端材が最小になるよう slab が選ばれるからだ。112 バイトの区画は 1 ページなら 64 バイト、2 ページなら 16 バイトを取り残す。大事なのは答えの形 —— オブジェクトごとのヘッダではなく slab ごとのビットマップだ。どちらの表も別の分布に値付けされているだけで、ホットな割り当てが 9 KiB のバッファならクラスに寄せればいい。

arena 1 つ、mutex 1 つ。どの malloc もそこに並ぶ。下のモデルの臨界区間は 8 ns —— bin を索引し chunk を外す —— で、外側の仕事が 40 ns だ。スレッドを足し、曲線が直線から離れるのを見てほしい：

どこで止まるかに注目。ロックは何スレッドが待とうと 8 ns に 1 回しか割り当てを出せないので、スループットは6 スレッドで飽和し、続く 26 スレッドは何も買わない。定数はモデルの選択だが、形はそうではない。固定長の臨界区間はどれも平らな線を与え、本当の解決策はロックを取らないことだけだ。

そのためにスレッド単位のキャッシュがある。glibc の tcache はサイズクラスごとに 7 個の chunk を持ち、誰の許可も求めない。割り当てを挟まずに free してみてほしい：

8 個目に注目。7 個までは free はスレッドローカルな単方向リストへの push だ —— アトミックもロックもなく、命令は十数個 —— 対になる malloc は pop になる。8 個目はarena に溢れ、ロックの代金を払う。 64 個の bin が 1,032 使用可能バイトまでを覆う。つまりほとんどすべてだ。

glibc の答えのもう半分は、単にロックを増やすことだ。主 arena が混んでいたスレッドには専用の arenaが与えられる。コアあたり最大 8 つまで。スレッド数を上げ、何が予約されるかを見てほしい：

その arena はどれも 64 MiB のマッピング 1 つだ。16 コアの機械では65 スレッドが何も割り当てないうちに 4 GiB のアドレス空間を予約する。仮想であって常駐ではないから触るまで費用はかからない —— が、これはコンテナの上限がリークとして報告する数でもある。MALLOC_ARENA_MAX=2 が 1 行の対処で、代わりに競合を買い戻すことになる。

これらすべてを破る型がひとつある。あるスレッドで割り当て、別のスレッドで free される chunk だ。別スレッド率を上げ、 2 通りの扱い方を比べてほしい：

chunk は生まれた arena のものなので、返すにはその arena のロックが要り、 free 側は持ち主と直列化する。半分が別スレッドなら、モデルの 16 スレッドは毎秒 10.81 億回から 2.34 億回へ落ちる。 mimalloc は chunk を持ち主ページの原子的な空きリストへ積む。 CAS 1 回で、並ぶものはない。

だから需要が増えなくてもヒープは伸びうる。下では毎巡、使用中の割り当ての 3 分の 1 を散らして解放し、同じバイト数をすぐ割り当て直す。使用中の合計は 1 バイトも変わらない。巡回を回し、ヒープに何かを要求してほしい：

どの数が要求に答えるのかに注目。30 巡のあと空きは 768 バイトで、最大の連続領域は 352 だ。だから512 バイトの要求はどこにも入らず、ヒープは伸びるしかない —— 使用中集合は最初の 3,360 バイトのままなのに。空きの合計は統計値で、実際に持っているのは穴のほうだ。

この成長は、運用が気にする唯一の意味で永久だ。波のある負荷の 2 分間を引いて、常駐と使用中を比べてほしい：

2 本の曲線が最初の山で離れ、二度と交わらないのを見てほしい。ピークが常駐の床になる。free はバイトを bin に返しただけで、ページはマップされたまま、汚れたままだ。2 分後もカーネルは 440 MiB を請求し続け、プログラムは 180 しか使っていない。誰かが意図的にページを返さない限り、RSS は増える一方の最大値だ。

返せる者はいる。jemalloc は減衰パージャを走らせ、しばらく触られていないページを madvise する。窓を決め、天井が下がるのを見てほしい：

窓は山と山の間隔より短くなければならない。10 秒なら常駐は使用中に最後まで付いていく。30 秒では一度も返さない。窓が閉じる前にページがまた汚れるからだ。しかもパージは無料ではない —— 260 MiB の再フォールトはマイナーフォールトで約 67 ms かかり、次にそのページを触った者が払う。

最後の 1 点だけ読むなら、3 つの違う仕組みが同じグラフを描く。1 つ選び、曲線を歩いてほしい：

2 分の時点で 2 本は 5 MiB 以内に着くが、同じバグではない。断片化は上りながら鈍って 410 MiB に達する。穴はいずれ再利用されるからだ。リークは平坦部のない直線で 415 に達し、自分のコードに直しがあるのはこれだけだ。丸めは 229 で平らになって自ら正体を明かす。診断は 1 時間ぶんの形にあり、末尾の数字にはない。

ある領域の中身が単独では決して解放されないなら、割り当てにデータ構造はもう要らない ——一方向にしか進まないポインタ、上限との比較、分岐。新世代を埋め、2 つの代価を並べてほしい：

比がすべてだ。8 MiB を全部埋めると、 48 バイトのオブジェクトで 174,762 回の割り当てになる。バンプポインタで 0.35 ms、tcache ヒットで 2.1 ms —— しかも tcache ヒットはもともと速い経路だ。空きリストもサイズクラスもない。ランタイムはオブジェクトヘッダを書くが、それは型システムのためであってアロケータのためではない。

請求は回収の時に届き、その形こそが要点だ。どれだけ生き残るかを決め、何が触られるかを見てほしい：

触られないものを見てほしい。複写式回収器は生存者だけを辿って外へ動かし、残りはポインタを先頭へ戻すだけで回収する —— だからゴミは無料で、代価は生きているものに比例する。生存率 10%なら、割り当ての 0.35 ms に複写の 0.10 ms が乗るだけで、同じオブジェクトを malloc と free でさばくよりなお 4.6 倍安い。

動かすことは malloc が真似できない部分で、努力の問題ではない。chunk を横に引き、プログラムがまだ握っているものを見てほしい：

C のポインタはアドレスそのものなので、chunk を動かすとポインタは旧アドレスに今住んでいる何かを指す。回収器が動かせるのは、すべての根とすべての参照を知っていて書き換えられるからだ。malloc は自分のポインタがどこへ行ったか教わっていない。 C のヒープの断片化がプロセス再起動でしか解消しないのはこのためだ。

こうして回収器は断片化そのものを回避し —— そのために要る余地の代金を請求する。ヒープが使用中集合の何倍かを決めてほしい：

Hertz と Berger は、この曲線が補間する 3 点を測った。使用中集合の 5 倍で世代別回収器は明示的な malloc と free に並ぶ。3 倍では17% 遅く、2 倍では 70% 遅い。取引を 1 つの数字にするとこれだ。選ぶのは速いか遅いかではなく、メモリを使うか、寿命に自分の注意を使うかである。

差が付くのは 4 つのうち 2 つだけだ。単スレッドのツールでは 3 つとも並ぶ。16 スレッドのパイプライン —— 生産側で割り当て、消費側で free —— では glibc はmimalloc の 5 分の 1。波のある負荷では常駐が 432 MiB 対 191 MiB だ。

レビューで指摘する 3 点。どれも上の節の帰結だ：

• 64 バイト未満へのホットループ内 malloc。ヘッダが 4 分の 1 を占める。外へ出すか arena へ。
• クラス境界のすぐ先の構造体。65 バイトは 80 を要する。sizeof して 64 に詰める。
• VSZ でのアラート。触られていない arena まで数える。 RSS の傾きで出すこと。

効くのは最後の段だ。新しい 1 MiB のマッピングは 1 バイト読む前に 256 µs かかる ——バンプ割り当ての 128,000 倍。 2 巡目が薄めるのでベンチマークには出ない。p99 のグラフはこれでできている。

/* the chunk one malloc(n) really takes */
size_t c = (n + 8 + 15) & ~(size_t)15;
if (c < 32) c = 32;      /* MINSIZE   */
/* usable = c - 8                     */
/* own mmap when c >= 128 * 1024      */