123

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

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

4

3 に答える 3

114

The sbrksystem call moves the "border" of the data segment. This means it moves a border of an area in which a program may read/write data (letting it grow or shrink, although AFAIK no malloc really gives memory segments back to the kernel with that method). Aside from that, there's also mmap which is used to map files into memory but is also used to allocate memory (if you need to allocate shared memory, mmap is how you do it).

So you have two methods of getting more memory from the kernel: sbrk and mmap. There are various strategies on how to organize the memory that you've got from the kernel.

One naive way is to partition it into zones, often called "buckets", which are dedicated to certain structure sizes. For example, a malloc implementation could create buckets for 16, 64, 256 and 1024 byte structures. If you ask malloc to give you memory of a given size it rounds that number up to the next bucket size and then gives you an element from that bucket. If you need a bigger area malloc could use mmap to allocate directly with the kernel. If the bucket of a certain size is empty malloc could use sbrk to get more space for a new bucket.

There are various malloc designs and there is propably no one true way of implementing malloc as you need to make a compromise between speed, overhead and avoiding fragmentation/space effectiveness. For example, if a bucket runs out of elements an implementation might get an element from a bigger bucket, split it up and add it to the bucket that ran out of elements. This would be quite space efficient but would not be possible with every design. If you just get another bucket via sbrk/mmap that might be faster and even easier, but not as space efficient. Also, the design must of course take into account that "free" needs to make space available to malloc again somehow. You don't just hand out memory without reusing it.

If you're interested, the OpenSER/Kamailio SIP proxy has two malloc implementations (they need their own because they make heavy use of shared memory and the system malloc doesn't support shared memory). See: https://github.com/OpenSIPS/opensips/tree/master/mem

Then you could also have a look at the GNU libc malloc implementation, but that one is very complicated, IIRC.

于 2010-08-13T17:58:11.413 に答える
58

単純化するmallocと、free次のように機能します。

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

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

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

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

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

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

フリー リストに目的の割り当て用のメモリが残っていない場合は、またはwhich をmalloc呼び出し、オペレーティング システムからより多くのメモリ ページを要求するシステム コールを呼び出します。brksbrk

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

  • 大規模なメモリ割り当て (通常は 512 バイトを超える) の場合、ヒープ マネージャーは OS に直接アクセスし、完全なメモリ ページを割り当てることができます。
  • ヒープは、大量の断片化を防ぐために割り当ての最小サイズを指定する場合があります。
  • ヒープは、小さな割り当て用のビンと大きな割り当て用のビンに分割して、大きな割り当てをより迅速に行うこともできます。
  • マルチスレッドのヒープ割り当てを最適化するための巧妙なメカニズムもあります。
于 2010-08-13T18:09:53.867 に答える