it-swarm-ja.com

malloc()は内部的にどのように実装されていますか?

malloc()が内部的にどのように機能するかを説明できますか?

私は時々strace programを実行しましたが、sbrkシステムコールをたくさん見て、man sbrkmalloc()で使用されていることについて話しますが、それ以上ではありません。

108
bodacydo

sbrksystem呼び出しは、データセグメントの「境界線」を移動します。これは、プログラムがデータを読み書きできる領域の境界線を移動することを意味します(ただし、mallocが実際にメモリセグメントをそのメソッドでカーネルに戻すことはありませんが、拡大または縮小させます)。それとは別に、ファイルをメモリにマップするために使用されるmmapもありますが、メモリの割り当てにも使用されます(共有メモリを割り当てる必要がある場合は、mmapがその方法です)。

そのため、カーネルからより多くのメモリを取得する2つの方法があります:sbrkおよびmmap。カーネルから取得したメモリを整理する方法については、さまざまな戦略があります。

単純な方法の1つは、特定の構造サイズ専用の「バケット」と呼ばれるゾーンにパーティションを分割することです。たとえば、malloc実装は、16、64、256、および1024バイト構造のバケットを作成できます。 mallocに指定サイズのメモリを提供するように要求すると、その数が次のバケットサイズに切り上げられ、そのバケットから要素が提供されます。より広い領域が必要な場合は、mallocmmapを使用してカーネルに直接割り当てることができます。特定のサイズのバケットが空の場合、mallocsbrkを使用して、新しいバケット用のスペースをさらに取得できます。

さまざまなmallocデザインがあり、速度、オーバーヘッド、およびフラグメンテーション/スペースの有効性を回避することを妥協する必要があるため、mallocを実装する正しい方法はありません。たとえば、バケットが要素を使い果たした場合、実装はより大きなバケットから要素を取得し、それを分割して、要素を使い果たしたバケットに追加します。これはスペース効率が非常に高くなりますが、すべてのデザインで可能になるわけではありません。 sbrk/mmapを介して別のバケットを取得するだけの場合は、より高速で簡単ですが、スペース効率は良くありません。また、設計ではもちろん、「フリー」でmallocが再び何らかの方法でスペースを使用できるようにする必要があることを考慮する必要があります。再利用せずにメモリを渡すだけではありません。

興味があるなら、OpenSER/Kamailio SIPプロキシには2つのmalloc実装があります(共有メモリを多用し、システムmallocは共有メモリをサポートしないため、独自に実装する必要があります)。参照: https://github.com/OpenSIPS/opensips/tree/master/mem

次に、 GNU libc malloc implementation を見ることができますが、これは非常に複雑です、IIRC。

100
DarkDust

次のように単純にmallocおよびfreeを実行します。

mallocは、プロセスのヒープへのアクセスを提供します。ヒープはCコアライブラリ(通常libc)の構造であり、オブジェクトがプロセスのヒープ上の一部のスペースへの排他的アクセスを取得できるようにします。

ヒープ上の各割り当ては、ヒープセルと呼ばれます。これは通常、セルのサイズに関する情報と次のヒープセルへのポインタを保持するヘッダーで構成されます。これにより、ヒープが事実上リンクリストになります。

プロセスを開始すると、ヒープには、起動時に割り当てられたすべてのヒープスペースを含む単一のセルが含まれます。このセルは、ヒープの空きリストに存在します。

Mallocを呼び出すと、メモリは大きなヒープセルから取得され、mallocによって返されます。残りは、メモリの残りのすべてで構成される新しいヒープセルに形成されます。

メモリを解放すると、ヒープの空きリストの最後にヒープセルが追加されます。後続のmallocは、適切なサイズのセルを探すためにフリーリストを調べます。

予想されるように、ヒープは断片化される可能性があり、ヒープマネージャーは時々、隣接するヒープセルをマージしようとします。

希望する割り当てのための空きリストにメモリが残っていない場合、mallocはbrkまたはsbrkを呼び出します。これらは、オペレーティングシステムにメモリページをさらに要求するシステムコールです。

現在、ヒープ操作を最適化するためのいくつかの変更があります。

  • 大きなメモリ割り当て(通常、512バイト以上)の場合、ヒープマネージャはOSに直接アクセスして、メモリページ全体を割り当てます。
  • ヒープでは、大量の断片化を防ぐために、割り当ての最小サイズを指定できます。
  • ヒープは、小さな割り当て用と大きな割り当て用のビンに分割され、より大きな割り当てをより迅速に行うこともできます。
  • マルチスレッドヒープ割り当てを最適化するための巧妙なメカニズムもあります。
45
doron

また、brkおよびsbrkを使用してプログラムブレークポインターを移動するだけでは、実際にはallocateメモリではなく、アドレス空間を設定するだけであることを認識することも重要です。たとえばLinuxでは、そのアドレス範囲にアクセスすると実際の物理ページによってメモリが「バッキング」され、ページフォールトが発生し、最終的にカーネルがページアロケーターを呼び出してバッキングページを取得します。

7
mgalgs