malloc関数がユーザー空間の帳簿管理を通じてメモリを管理する方法

カーネルにメモリを要求する単一のシステムコールには、約610ナノ秒かかる場合があります。プログラムが小さな割り当てのたびにこれを行うと、コストは許容できないものになります。これを解決するために、malloc関数は高度なユーザー空間マネージャーとして機能し、大きなメモリブロックを要求して独自の内部帳簿を維持することで、小さな要求を効率的に処理します。

この表は、mallocが直接のシステムコールよりも大幅に高速であるという主張を裏付ける実証データを提供します。

カーネルとの相互作用のコスト

プログラムがメモリを要求すると、それはtext、data、bss、heap、stackといった領域に分割されたアドレス空間内に配置されます。最終的に物理メモリを所有するのはカーネルですが、ユーザー空間からカーネル空間への切り替えに伴うオーバーヘッドがあるため、ごく小さな割り当てのたびにカーネルを呼び出すことは非効率です。

この視覚資料は、テキスト内で言及されているヒープやスタックなどのプロセスのアドレス空間の異なる領域を説明するのに役立ちます。

一度に大きなメモリブロック（例えば、一度の操作で132 KiBのジャンプなど）を要求することで、mallocはプログラムがさらなるカーネルの介入なしにその後の数百の割り当てを実行できるようにします。この戦略により、メモリ要求の大部分が低速なシステムコールではなく、ライブラリの内部ロジックによって処理されることが保証されます。

HN Digest による図（benmandrew.com の報告数に基づく）。数値はソースの表記通り。

「mallocはカーネルから大きなブロックを要求し、それを自身で切り分けます。」

— What is malloc doing, anyway?

内部帳簿とフリーリスト

これらの大きなブロックを管理するために、mallocはサイズヘッダーを含む「チャンク」を使用します。このヘッダーにより、ユーザーが解放操作の際にサイズを指定する必要がなくとも、アロケータはどれだけのメモリが占有されているか、および次のチャンクがどこから始まるかを知ることができます。

この図は、ユーザーに割り当てられた実際のメモリの前にヘッダーが存在する内部帳簿の仕組みを説明します。

メモリが解放されると、それはフリーリストに配置されます。その後、アロケータは大きな空きチャンクを特定の要求に適合する小さなピースに分割する「splitting」と、メモリが使い物にならなくなるのを防ぐために隣接する空きチャンクを大きなブロックに再び統合する「coalescing」を実行します。

アロケータは、返されるすべてのポインタが16バイト整列されていることを保証します。これはx86-64アーキテクチャの標準であり、メモリがすべてのCデータ型と互換性を持つことを保証します。

断片化とレジデントメモリ

ヒープ管理の大きな制限の一つは断片化です。カーネルはヒープの最上部（「プログラムブレイク」）からしかメモリを回収できないため、空き領域よりも高いアドレスに配置されたライブなメモリブロックがあると、その空き領域をシステムに返却できなくなります。

これは、長時間実行されるプログラムにおいて、断片化によってレジデントセットサイズ（RSS）が時間の経過とともに増大する可能性があることを意味します。アプリケーションが大量のメモリを「解放」したとしても、たとえたった一つの小さなライブな割り当てが空きスペースよりも高いアドレスに存在する場合、物理RAMは占有されたままとなります。

mmapによる大きな割り当ての処理

128 KiBを超えるような非常に大きなメモリ要求に対しては、mallocは戦略を切り替えてmmapシステムコールを使用することがあります。これにより、標準的なヒープの一部ではない、プロセスのアドレス空間内にある完全に独立したマッピングが作成されます。

ヒープメモリとは異なり、これらのmmapされたブロックは、munmapシステムコールを介して解放された直後にカーネルに返却することができます。これにより、アロケータはヒープの断片化に寄与することなく、あるいはプログラムブレイクの縮小を妨げることなく、巨大な割り当てを処理することが可能になります。