phk mallocとは

Poul-Henning Kamp氏が開発したmallocの実装です。 つい最近(2007年ごろ)、*BSDではjemallocを使うようになりましたが、それまで主流だったのがphk mallocです。

このドキュメントは、phk mallocの実装の概要を説明しています。

以下の文章で、mallocライブラリとはphk mallocの事を指します。

OSからメモリを取得するのは、ページ単位

プログラムがOSからメモリをもらう場合、ページと呼ばれる単位でもらいます。

+---------------+  
|               |
|   1 ページ    |
|               |
+---------------+

ページのサイズは4KB(※OSやCPUに依存)固定で、この倍数でしかメモリをもらう事はできません。

malloc()では当然4KB以外のサイズのメモリを割り当てる事ができ、ユーザープログラムは4KBというサイズを意識する事はありません。 これは、ユーザーがページを意識しなくて良いように、mallocライブラリがうまい亊詳細を隠しているからです。

OS
 | 
 | ページ単位でメモリ取得
 | 
 V
mallocライブラリ
 | 
 | 任意のサイズでメモリ取得
 | 
 V
ユーザープログラム

mallocライブラリは、OSからページ単位でメモリを確保し、その中の必要なサイズだけユーザープログラムに渡します。 ページが足りなくなったら、その都度mallocライブラリはOSにページを要求します。

malloc()するサイズと、ページの使い方

ユーザープログラムがmalloc()で要求したサイズによって、mallocライブラリはそのメモリ割り当ての戦略を変えています。

A. malloc()で要求したサイズが2KB以下の場合
B. malloc()で要求したサイズが2KBより大きい場合

malloc()で要求したサイズが2KB以下の場合

malloc()で要求したサイズが小さい場合、malloc()ライブラリはページをchunkとよばれる細かい塊に等分割して、その一つをユーザーに渡します。 chunkの大きさは、16, 32, 64, 128, ... , 2048と、2^nになっています。

1KBのchunkに等分されたページ
+-------+-------+
|       |       |
+-------+-------+
|       |       |
+-------+-------+

256バイトのchunkに等分されたページ
+---+---+---+---+
+---+---+---+---+
+---+---+---+---+
+---+---+---+---+
+---+---+---+---+

1つのページの中にサイズの異なるchunkが混じる事はありません。

こんな風に分割される事は無い
+-------+---+---+
+-----+-+-------+
|     | |-+-----+
+---+-+-+-+     |
+---+-----+-----+

ユーザーが要求してきたサイズが2^nではない場合、2^nに切り上げられた大きさのchunkを返します。 chunkの最小サイズは16なので、malloc(1)の場合でも、サイズが16のchunkが割り当てられます。

chunkに分割されたページの管理には、struct pginfoを使います。

struct pginfo {
    struct pginfo *next;
    void *page; /* ページへのポインタ。 */
    u_short size; /* chunkのサイズ。 */
    u_short shift; /* 1 << shiftがsizeに等しい。 */
    u_short free; /* ページ中にあるフリーなchunkの数。 */
    u_short total; /* ページ中にある総chunk数。4KB / chunkサイズに等しい。 */
    u_int bits[1]; /* どのchunkがフリーかを表すビットマップ。 */
};

どのchunkが使用中かどうかの管理には、bits[]を使って、ビットマップで管理していて、1の場合はフリー、0の場合は使用中です。 例えば、1番目と40番目のchunkだけがフリーで、残りはalloc既みである場合は、以下のようになります。

bits[0] = 0x00000001;
bits[1] = 0x00000080;
bits[2] = 0x00000000;
   ...

malloc()で要求したサイズが2KBより大きい場合

この場合は、 ページをchunkに分けて管理せずに、OSから確保したページをまるごとユーザープログラムに渡してしまいます。

mallocで要求されたのサイズxによって、ユーザーに渡すページ数は以下のようになります。

2KB < x <= 4KB の場合 -> 1ページ割り当てる。
4KB < x <= 8KB の場合 -> 2ページ割り当てる。
8KB < x <= 12KB の場合 -> 3ページ割り当てる。

mallocライブラリがページを管理する方法

最初に、OSから割り当てられるメモリはページ単位という話をしましたが、 OSからmallocライブラリに割り当てられた全てのページは、page_dir[]という配列で管理しています。

page_dirは、struct pginfoの配列です(正確には、ポインタポインタです)。

OSから割り当てられたメモリ
  +-------------+
  |             |  ページ1
  |-           -|
  |             |  ページ2
  |-           -|
  |             |  ページ3
  |-           -|
  |             |  ページ4
  |-           -|

OSから割り当てられたページは連続したアドレスになっているのですが、アドレスの小さい方から順に、 ページ1,ページ2,...とします。

page_dir[n]は、nが12未満と12以上で、使い方が違います。

page_dir[0] : 未使用
page_dir[1] : 未使用
page_dir[2] : 未使用
page_dir[3] : 未使用
page_dir[4] : chunkサイズ16で分割したページで、フリーなchunkのある物へのポインタ。
page_dir[5] : chunkサイズ32で分割したページで、フリーなchunkのある物へのポインタ。
page_dir[6] : chunkサイズ64で分割したページで、フリーなchunkのある物へのポインタ。
page_dir[7] : chunkサイズ128で分割したページで、フリーなchunkのある物へのポインタ。
page_dir[8] : chunkサイズ256で分割したページで、フリーなchunkのある物へのポインタ。
page_dir[9] : chunkサイズ512で分割したページで、フリーなchunkのある物へのポインタ。
page_dir[10] : chunkサイズ1024で分割したページで、フリーなchunkのある物へのポインタ。
page_dir[11] : chunkサイズ2048で分割したページで、フリーなchunkのある物へのポインタ。
page_dir[12] : ページ1の使用状況。
page_dir[13] : ページ2の使用状況。
page_dir[14] : ページ3の使用状況。
page_dir[15] : ページ4の使用状況。
  ....

page_dir[12]以降の使い方

例えば、ページ1-6が以下のような状態だったとします。

  +-------------+
  |             |  ページ1
  |-           -|
  |  12KB確保   |  ページ2
  |-           -|
  |             |  ページ3
  |-------------|
  |             |  ページ4
  |-  8KB確保  -|
  |             |  ページ5
  |-------------|
  |   未使用    |  ページ6
  |-------------|

• ページ1-3は、malloc(12*1024)で3ページ分連続して確保された。
• ページ4-5は、malloc(8*1024)で2ページ分連続して確保された。
• ページ6は、未使用。

この場合、page_dirは以下のようになります。

page_dir[12] = MALLOC_FIRST
page_dir[13] = MALLOC_FOLLOW
page_dir[14] = MALLOC_FOLLOW
page_dir[15] = MALLOC_FIRST
page_dir[16] = MALLOC_FOLLOW
page_dir[17] = MALLOC_FREE

MALLOC_FIRSTは、連続して確保されたページの先頭を意味します。 MALLOC_FOLOWは、連続して確保されたページの非先頭を意味します。

MALLOC_XXXは、以下のようにdefineされています。

#define MALLOC_FREE   ((struct pginfo*) 1)
#define MALLOC_FIRST  ((struct pginfo*) 2)
#define MALLOC_FOLLOW ((struct pginfo*) 3)

本来page_dir[n]はstruct pginfoへのポインタですが、キャストして、ページの使用状況を表すのに強引に使っています。

page_dir[12]以前の使い方

page_dir[4-11]は、「フリーなchunkを1つ以上持っているstruct pginfoの、リンクリスト」です。 空きchunkを高速に探すために使用します。

malloc()で要求されたサイズが1-16バイトの時にはpage_dir[4]を、17-32バイトの時にはpage_dir[5]を参照します。

page_dir[n]がNULLの場合、以下の処理を行います。

1. 空きページを1つ取得する。
2. 空きページの使用状況を、MALLOC_FIRSTにする。
3. struct pginfoを作成して、メンバを初期化する。(ビットマップを全て1にする、等)。
4. 作成したstruct pginfoをpage_dir[n]にセットする。
5. chunkを一つ返す。

フリーなページの管理

空きページは、struct pgfreeでリンクリストを作っています。

struct pgfree {
    struct pgfree *next;
    struct pgfree *prev;
    void *page; /* 空きページへのポインタ */
    void *end; /* 空きページの末尾 */
    size_t size; /* 空きサイズ(=4KB x n) */
};

global変数free_listは、空きページリンクリストの先頭です。

            +----+  next   +----+  next   +----+
 free_list->|    |-------->|    |-------->|    |--->NULL
            +----+         +----+         +----+
                | page         | page         | page
                V              V              V
                +----------+   +----------+   +----------+
                |          |   |          |   |          |   
                +----------+   +----------+   +----------+
                |          |   |          |   
                +----------+   +----------+
                               |          |   
                               +----------+

free()で返却するサイズが2KB以下の場合

struct pginfoの対応するchunkのビットマップを0から1にします。

そのページ中の全てのchunkがフリーになった場合、以下の処理が行われます。

• struct pginfoは破棄され、page_dir[n]のリンクリストから外されます。
• struct pgfreeが作成され、free_listリンクリストに繋がれます。

free()で返却するサイズが2KBより大きい場合

struct pgfreeが作成され、ページはfree_listに繋がれます。 また、page_dir[n]はMALLOC_FREEにセットされます。

その他の話題

OSからページをもらうにはどうするのか

システムコールの一つ、brk(2)を使っています。

OSにメモリを返却するにはどうするのか

システムコールの一つ、brk(2)を使っています。

OSにメモリを返却しやすくするために、フリーなページやフリーなchunkのリンクリストはアドレス順に並んでいて、malloc(2)はできるだけ小さなアドレスの物が返されます。

struct pginfoやstruct pgfreeはどこにあるのか

struct pgfreeは、内部でmalloc()を呼んでchunkから確保されます。

struct pginfoは、基本的にはそのページの先頭に確保されます。 よって、ページの先頭の数chunkは、struct pginfoが最初から使用既みという事になります。

Xがstruct pginfo
+-----+-+-------+
|XXXXX| |       |
+-----+-+-------+
|       |       |
+-------+-------+

ただし、そのページのchunkサイズに比べてstruct pginfoがあまりにも小さい場合には、 内部でmalloc()を呼んで、別ページのchunkから確保されます。

page_dirはどこにあるのか

page_dir用のページが、別に確保されています。

mallocライブラリではbrk(2)を使ってOSからページを確保していますが、 page_dir用のページは、mmap(2)で確保しています。

---

Last Modified: 2008-09-24 Wednesday