そもそもmallocは何をしているのか？

そもそもmallocは何をしているのか？

mallocは非常に素晴らしくシンプルなインターフェースを持っています。特定の量のメモリを要求すると、それが魔法のように出現した連続バイトのブロックへのvoidポインタが与えられます。使い終わったら、同じポインタを渡してfreeを呼び出すと、メモリはエーテルの中に消えていきます。

しかし、実際には何が起こっているのでしょうか？明らかに、ユーザー空間プログラムとして実行しているため、mallocはシステムコールを通じてカーネルにメモリを要求しているはずです。しかし、多くの小さなブロックを割り当てる可能性があり、システムコールは高価です（下記測定で空のコールで575 ns）。そのため、バックグラウンドで何らかのブックキーピングが行われています。ここでは、malloc(16)を千回呼び出す以下のプログラムスニペットを使用して、GNU libc（glibc）でこれを実証します。

static void *ptrs[1000];

int main(void) {
    for (int i = 0; i < 1000; i++)
        ptrs[i] = malloc(16);
}

straceを使用すると、ループ全体でわずか2回のbrkシステムコールしか行われていないことがわかります。最初のコールはプログラムブレーク（プロセスヒープの終了アドレス）を尋ね、2番目のコールはヒープを132 KiB増やします。これらはすべて最初のmallocコールで行われます。他の999回のコールは、すでに割り当てられたメモリから取得するだけです。

$ strace -e trace=brk,mmap,munmap,write \
    ./malloc1000 > /dev/null
... 
brk(NULL)              = 0x59faca231000
brk(0x59faca252000)    = 0x59faca252000
+++ exited with 0 +++

brkとsbrkの両方が議論で言及されているのを目にするかもしれません。brkはプログラムブレークを指定されたアドレスに設定するシステムコールであり、sbrkはデルタを受け取り、プログラムブレークをその量だけ増加させるlibcの便利なラッパーです。

アドレス空間

実行中のプロセスは、多数の領域に分割された独自のアドレス空間を取得します。これらには、実行可能コード用のtext、初期化済みグローバル変数用のdata、未初期化グローバル変数用のbssなどが含まれます。以下のプログラムは、プロセスの各領域から1つのアドレスを出力します。

#define SHOW(label, p) \
    printf("% -22s %p\n", label, (void *)(p))

SHOW("main (text)", main);
SHOW("initialised (data)", &initialised);
SHOW("uninitialised (bss)", &uninitialised);
SHOW("malloc(16) (heap)", malloc(16));
SHOW("program break", sbrk(0));
SHOW("printf (libc)", printf);
SHOW("local (stack)", &local);

アドレスは、バイナリのコードからスタックに向かって増加します。

$ ./layout
main (text)            0x59c0791d7149
initialised (data)     0x59c0791da020
uninitialised (bss)    0x59c0791da028
malloc(16) (heap)      0x59c0903182b0
program break          0x59c090338000
printf (libc)          0x711dcf7c15b0
local (stack)          0x7ffff86c45ec

これらの領域の一部は、プログラムの実行中に変化する可能性があります。例えば、malloc(16)はヒープを拡張し、ブレークを上に移動させます。この実行では、ブレークとlibcのprintfは約23.4 TiB離れており、これはマシンの15.6 GiB RAMの約1,530倍です。その範囲のほぼすべてはマッピングされていないため、物理メモリは消費しません。

lowhighat starttextdataBSSgapbreak23 TiBunmappedlibcstackmalloc(16)textdataBSSgapheapbreak23 TiBunmappedlibcstack

sbrkを使ったトイアロケータ

プログラムブレークを直接移動できるため、独自の簡単なアロケータを作成できます。これはバンプアロケータと呼ばれます。なぜなら、各呼び出しは単に使用を許可されたメモリ量を増やすだけだからです。

void *my_malloc(size_t size) {
    void *p = sbrk(align_up(size));
    return p == (void *)-1 ? NULL : p;
}

void my_free(void *ptr) {
    (void)ptr;
}

このアロケータはあまり良くありません！各リクエストでブレークを移動し、各移動はシステムコールです。mallocがカーネルに大きなブロックを要求し、それを自分で分割するのはなぜかを見るために、システムコールとmallocのコストを比較できます。以下の3つの関数のそれぞれが、100万回の呼び出しで時間を計測されます。

static void *volatile sink;

static void call_getppid(void) {
    syscall(SYS_getppid);
}

static void call_sbrk(void) {
    sink = sbrk(16);
}

static void call_malloc(void) {
    sink = malloc(16);
}

sbrk(16)は空のシステムコールよりわずか35 nsしかコストがかかりませんが、malloc(16)はsbrk(16)よりも22.7倍速く実行されます。

$ ./syscall-cost
syscall(SYS_getppid)      575.2 ns per call
sbrk(16)                  610.1 ns per call
malloc(16)                 26.9 ns per call
sbrk(16) / malloc(16)      22.7x

バンプアロケータには、解放されたメモリを再利用する方法もありません。各リクエストは前のリクエストの直後に配置されるため、以下の例では、bが解放されているにもかかわらず、dはcの後に配置されます。

$ ./my-bump-1
a = my_malloc(16)   start+0
b = my_malloc(1)    start+16
c = my_malloc(100)  start+32
my_free(b)
d = my_malloc(1)    start+144
break               start+160

投稿の残りの部分では、アロケータを段階的に改善していきます。

チャンクとヘッダー

mallocは実際には要求されたよりも多くのメモリを割り当てます。これは、各割り当て、つまりチャンクの前にサイズヘッダーがあるためです。これにより、freeは明示的なサイズを渡さずに機能します。チャンクサイズは常に16の倍数であるため、サイズの最下位ビットは常にゼロであり、glibcはそこに3つのフラグを保持します。

header24 bytes for the callerheaderp = malloc(24)next chunkchunk:32 bytessize=320A0M1Pone 8-byte wordA:another arenaM:own mappingP:chunk before in use

size_t requests[] = {1, 24, 25, 1000};

size_t count = sizeof requests / sizeof requests[0];
for (size_t i = 0; i < count; i++) {
    char *p = malloc(requests[i]);
    size_t chunk = ((size_t *)p)[-1] & ~(size_t)7;
    printf("%8zu %8zu\n", requests[i], chunk);
}

各チャンクは、要求にヘッダー用の8バイトが加算され、16の倍数に丸められ、最小で32バイトになります。丸めにより、mallocが返すすべてのポインタは16バイトアラインメントされ、これはx86-64がmax_align_tに与えるアラインメントであるため、メモリは任意のC型に適しています。32バイトの最小値は、チャンクが解放された後に格納するリストポインタのためのスペースを残します。

$ ./chunk-header
 request    chunk
       1       32
      24       32
      25       48
    1000     1008

チャンクを解放すると、再利用を可能にするためにフリーリストに入れられます。より多くのデータが要求されると、mallocはこのフリーリストを検索し、小さな要求に合うように大きなチャンクを分割し、freeは隣接するフリーチャンクを結合します。フリーリストの各チャンクには、サイズ（すでに持っている）と、フリーリスト内の次のチャンクへのポインタという2つの情報が必要です。glibcはポインタをサイズの後ろに格納し、解放される前にユーザーがデータを格納していたメモリを再利用します！

トイアロケータは、各チャンクに同じ2つのフィールドを格納します。

typedef struct chunk {
    size_t size;
    struct chunk *next;
} chunk_t;

分割と結合

要求とヘッダーを16バイトの倍数に丸め、フリーリストから十分な大きさの最初のチャンクを取得することで、my_mallocを改善できます。単純にするために、トイのヘッダーは完全なchunk_tであり、チャンクは使用中でもnextのためのスペースを保持します。これにより、glibcのヘッダーが8バイトであるのに対し、ヘッダーは16バイトになり、my_malloc(100)はmalloc(100)が112バイトを取る場合に128バイトのチャンクを取ります。

void *my_malloc(size_t size) {
    size_t need = align_up(size + HEADER_SIZE, ALIGN);
    for (chunk_t **link = &free_list; *link != NULL;
         link = &(*link)->next)
        if ((*link)->size >= need)
            return take(link, need);
    if (grow_heap(need) != 0)
        return NULL;
    return my_malloc(size);
}

takeを定義して、チャンクを分割し、要求が消費しない残りをフリーリストに残します。

static void *take(chunk_t **link, size_t need) {
    chunk_t *c = *link;
    if (c->size > need) {
        chunk_t *rest = (chunk_t *)((char *)c + need);
        rest->size = c->size - need;
        rest->next = c->next;
        c->size = need;
        *link = rest;
    } else {
        *link = c->next;
    }
    return (char *)c + HEADER_SIZE;
}

フリーチャンクが適合しない場合、grow_heapはsbrkを使用してプログラムブレークを64 KiBステップで上に移動させ、新しいスペースを1つのチャンクとしてフリーリストに追加します。

ヘッダーを使用すると、適切なmy_free関数を実装できるようになります！ヘッダーへのポインタを後方にステップし、チャンクcをinsert_freeに渡します。この関数はリストを歩いて、アドレスでcの左右にあるフリーチャンク（prevとnext）を見つけ、それらの間にcをリンクします。次に、cがnextの開始位置で終了するか、prevの終了位置で開始する場合、2つは1つのチャンクになります。

if (next != NULL && (char *)c + c->size == (char *)next) {
    c->size += next->size;
    c->next = next->next;
}
if (prev != NULL && (char *)prev + prev->size == (char *)c) {
    prev->size += c->size;
    prev->next = c->next;
}

テストプログラムはa、b、cを割り当て、aとbを解放し、dを割り当て、残りを解放します。

a,bandcallocatedabc65056free_listmy_free(a)128bc65056free_listmy_free(b)mergesaandb352c65056free_listd = my_malloc(50)splits the merged chunkd272c65056free_listmy_free(c)merges both neighboursd65456free_listmy_free(d)65536free_list

各行は、呼び出しによって割り当てられたチャンク（存在する場合）、次にフリーリストを示します。各チャンクはヒープの開始からのオフセットとサイズ（[offset, size]）のペアであり、オフセットはヘッダーの開始位置、つまりmy_mallocが返すポインタの16バイト前です。

$ ./my-freelist-2
a = my_malloc(100)   [0, 128]     free: [128, 65408]
b = my_malloc(200)   [128, 224]   free: [352, 65184]
c = my_malloc(100)   [352, 128]   free: [480, 65056]
my_free(a)                        free: [0, 128] [480, 65056]
my_free(b)                        free: [0, 352] [480, 65056]
d = my_malloc(50)    [0, 80]      free: [80, 272] [480, 65056]
my_free(c)                        free: [80, 65456]
my_free(d)                        free: [0, 65536]

dはオフセット0のチャンクを取得し、これはaとbが結合された352バイトのチャンクから分割されたものです。バンプアロケータは、4番目の要求をすべてが終わった後に配置しました。cを解放すると3つのチャンクが1つに結合され、dを解放するとgrow_heapが追加した単一の64 KiBチャンクが残ります。

デマンドページング

my_freeはメモリを再利用しますが、カーネルに返すことはありません。フリーチャンクがまだRAMを消費しているかどうかは、カーネルがアドレスの後ろに物理メモリを配置するタイミングによって異なります。各プロセスは仮想メモリを見て、カーネルはそれを4 KiBのページに分割して物理RAMにマッピングします。この分離により、カーネルは物理RAMの裏付けがないアドレス範囲を割り当てることができます。仮想ページは、最初の書き込み時にのみ物理メモリによって裏付けられる必要があります。

aftersbrk:8 pages added, none residentvirtualphysicalafter writing 3 pages:3 faults, 3 residentvirtualphysical

以下のプログラムは、ブレークを1 GiB上に移動させ、次に各ページに1バイトを書き込み、256 MiBごとに1行を印刷します。

char *p = sbrk(SIZE);
print_row(0);
for (size_t offset = 0; offset < SIZE; offset += PAGE_SIZE) {
    p[offset] = 1;
    if ((offset + PAGE_SIZE) % (SIZE / 4) == 0)
        print_row((long)((offset + PAGE_SIZE) >> 20));
}

仮想サイズはプロセスがマッピングしたアドレスをカウントし、常駐セットサイズ（RSS）はRAMにあるページをカウントします。sbrkの直後、仮想サイズはすでに1 GiBを超えていますが、RSSは1308 KiBです。256 MiBごとに書き込まれるたびに、4 KiBページごとに65,536ページフォールトが発生し、RSSが増加します。

$ ./demand-paging
   written     faults        virtual       resident
     0 MiB          3    1050916 KiB       1308 KiB
   256 MiB      65539    1050916 KiB     263536 KiB
   512 MiB     131075    1050916 KiB     525680 KiB
   768 MiB     196611    1050916 KiB     787824 KiB
  1024 MiB     262147    1050916 KiB    1049968 KiB

チャンクのページが書き込まれると、my_freeの後も、アロケータがカーネルに返すまで常駐し続けます。

メモリの返却

カーネルにメモリを返すには、ブレークを下げる必要があります。新しい関数trimを導入します。これは、ヒープの最上部にあるフリーチャンクが128 KiBに達したらブレークを下げ、次のいくつかの要求でブレークがすぐに元に戻らないように64 KiBを保持します。

static void trim(void) {
    chunk_t *top = free_list;
    if (top == NULL)
        return;
    while (top->next != NULL)
        top = top->next;
    char *end = (char *)top + top->size;
    if (end != (char *)sbrk(0) || top->size < TRIM_THRESHOLD)
        return;
    size_t release =
        (top->size - TOP_PAD) / PAGE_SIZE * PAGE_SIZE;
    top->size -= release;
    sbrk(-(intptr_t)release);
}

テストプログラムは1 MiBを割り当て、その上に16バイトのチャンクを割り当て、次に1 MiBブロックの各ページに書き込みます。（匿名RSSは、ファイルバックを持たない常駐メモリをカウントし、libcのコードを数値から除外します。）

$ ./my-trim-3
                                 break         anonymous RSS
my_malloc(1 MiB), my_malloc(16)  start+1088 KiB     1124 KiB
my_free(1 MiB)                   start+1088 KiB     1124 KiB
my_free(16)                      start+64 KiB        160 KiB

1 MiBブロックを解放すると、ブレークは1088 KiB、匿名RSSは1124 KiBのままですが、その上の16バイトチャンクがまだ生きているためです。そのチャンクも解放されると、trimはブレークを64 KiBに下げ、匿名RSSを160 KiBに低下させます。

ヒープの最上部のみが返却可能です。ライブチャンクはそれより上のブレークを保持するため、その下のすべてのフリーチャンクは常駐し続けます。これは、ここでの1 MiBブロックのようにです。長期間の実行では、多くの割り当てと解放により、ライブチャンクの間にフリーギャップが残りますが、後続の要求はめったに埋められず、これはフラグメンテーションと呼ばれます。これらのギャップは常駐し続けるため、長期間実行されるプログラムでは、フラグメンテーションによりRSSが増加し、メモリ制限によってプロセスが終了する可能性があります。

live chunkfree chunk, or wholly free pagepage holding part of a live chunkall chunks freed…breakall but the last freed…breakevery other chunk freed…break

mmapによる大きなブロック

mmapシステムコールは通常、ファイルをアドレス空間にマッピングします。MAP_ANONYMOUSフラグを使用すると、バックグラウンドファイルはなくなり、カーネルはアドレス空間のどこにでもゼロで埋められたページアラインメントされたマッピングを作成します。ヒープと同様に、その常駐ページは匿名RSSにカウントされます。munmapシステムコールは、解放されるとすぐに、そのブロックをカーネルにその独自のマップとともに返します。これは、その隣にあるものに関係なく行われます。

これを独自のアロケータに統合するために、my_mallocは要求のサイズに基づいてsbrkとmmapを選択します。ヘッダーを含めて128 KiB以上の要求は、ページ全体に丸められたmap_chunkからのマッピングを取得します。それより小さい要求は、既存のsbrkフリーリストパスを使用します。

static void *map_chunk(size_t need) {
    size_t len = align_up(need, PAGE_SIZE);
    chunk_t *c = mmap(NULL, len, PROT_READ | PROT_WRITE,
                      MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (c == MAP_FAILED)
        return NULL;
    c->size = len | MMAPPED; // chunk is mapped
    return (char *)c + HEADER_SIZE;
}

mmapされたチャンクの場合、サイズヘッダーの3つのフラグのうちの1つ（M）を使用して、このチャンクが独自のマップを持っていることを記録します。my_freeはこのビットをチェックして、どのように解放するかを判断します。マップされたチャンクはmunmapでアンマップし、他のチャンクはフリーリストに戻され、trimがそれを解放できます。

void my_free(void *ptr) {
    if (ptr == NULL)
        return;
    chunk_t *c = (chunk_t *)((char *)ptr - HEADER_SIZE);
    if (c->size & MMAPPED) {
        munmap(c, c->size & ~(size_t)MMAPPED);
        return;
    }
    insert_free(c);
    trim();
}

前のデモを再度実行すると、1 MiBブロックを解放すると匿名RSSが低下し、16バイトチャンクがまだ生きていることがわかります。

$ ./my-mmap-4
                                 break         anonymous RSS
my_malloc(1 MiB), my_malloc(16)  start+64 KiB       1128 KiB
my_free(1 MiB)                   start+64 KiB        100 KiB
my_free(16)                      start+64 KiB        100 KiB

以下の図は、これがアドレス空間でどのように見えるかを示しています。

lowhighbeforetextdataBSSgapheapbreakunmappedlibcstackmy_malloc(1 MiB)textdataBSSgapheapbreakunmapped1 MiBlibcstackmy_free(1 MiB)textdataBSSgapheapbreakunmappedlibcstack

なぜすべてをmmapしないのでしょうか？一部のアロケータはそうします！glibcでさえ、アリーナと呼ばれる追加のヒープを作成し、スレッドをそれらに分散させて、メインヒープのロックをすべて競合しないようにします。しかし、個別のマッピングは個別の領域を持ち、連続性の保証はなく、チャンクはこれらのギャップをまたいで結合できません。一方、sbrkで割り当てることは、すでに持っている単一の連続領域を単に増やすだけです。解放されたチャンクがヒープに残ると、そのページは常駐し続けるため、再利用してもページフォールトは発生しません。各新しいマッピングは、物理メモリが裏付けられていない状態で開始され、書き込む各ページでフォールトが発生します。

パフォーマンスの比較

アロケータのパフォーマンスをglibcのmallocと比較します。これは、さまざまなサイズのブロックを繰り返し割り当ておよび解放するワークロードを使用します1。速度を測定するために、ステップの平均時間を求めます。ランダムなライブブロックを解放し、ランダムサイズの代替を割り当て、各ページに書き込みます。実行終了時、ライブブロックは10.3 MiBを保持します。最後の2列は、その時点での匿名RSS、およびすべてのブロックが解放された後のメモリ（アロケータが保持するメモリ）を示します。

my-bump-1はメモリを解放または再利用しないため、RSSは実行全体で割り当てられた合計1425 MiBです。ステップあたりの1.72 µsは、各要求に対するsbrk呼び出しと新しいページでのページフォールトによるものです。my-freelist-2はメモリを再利用するため、RSSの17.8 MiBはライブデータの10.3 MiBに非常に近いです。しかし、各ステップはリストを2回走査します。my_mallocは適合するチャンクを見つけるためにリストを走査し、insert_freeはチャンクの隣を見つけるためにリストを走査します。my-trim-3は3回目の走査を追加します。なぜなら、trimは各my_freeで最後のフリーチャンクを探すからです。my-freelist-2とmy-trim-3は、それぞれglibcよりも65倍と142倍遅く実行されます。その見返りに、my-trim-3はすべてのブロックが解放された後、わずか0.188 MiBしか保持しません。my-mmap-4は大きな要求に対してmmapを呼び出すため、ステップあたりの時間は11.8 µsに増加しますが、ライブブロックがある場合、RSSは11.2 MiBと最も低くなります。

なぜglibcはそれほど速いのでしょうか？私たちのカスタムアロケータの遅延は、複数のフリーリストチャンクを何度も走査する必要があるためです。glibcは代わりに、フリーチャンクをビン（サイズごとの別々のリスト）に保持するため、要求は適切なサイズのチャンクのリストを直接走査できます。また、各小さなサイズについて最大7つの解放済みチャンクをスレッドローカルキャッシュ（tcache）に保持し、それらをすぐに次の同じサイズの要求に返します。

tcacheは最後の列も説明しています。glibcは、すべてのブロックが解放された後も19.0 MiBを保持しています。ヒープはキャッシュされたチャンクを使用中と見なすため、最上部近くのチャンクはglibcがブレークを下げるのを妨げます。GLIBC_TUNABLES環境変数を使用すると、GLIBC_TUNABLES=glibc.malloc.tcache_count=0でtcacheを無効にしたり、GLIBC_TUNABLES=glibc.malloc.mmap_threshold=131072でmmapしきい値を128 KiBに固定したりできます。

tcacheを無効にすると、すべてを解放した後に0.250 MiBが残り、各ステップは以前よりも1.5倍時間がかかります。

glibcは実行全体で51回のmmap呼び出しを行いますが、my-mmap-4は5040回行います。マップされたチャンクを解放すると、glibcのしきい値はそのチャンクのサイズまで引き上げられるため、後続の大きな要求はヒープから取得されます。しきい値が128 KiBに固定されると、大きな要求ごとにシステムコールとページフォールトのコストが再度発生し、glibcの実行速度は10.7倍になります。

mallocはカーネルから離れるためにメモリを消費し、ユーザー空間で大きなブロックを小分けにすることで、ほとんどの呼び出しでシステムコールが発生しないようにします。

リンク

• 各プログラムの再現可能なスニペット（リンク）。
• glibc自身のallocatorの内部説明。チャンク、ビン、アリーナ、tcacheをカバーしています（リンク）。
• brk(2)およびsbrk(2)（リンク）、mmap(2)（リンク）、mallopt(3)（リンク）、およびmalloc_trim(3)（リンク）のマニュアルページ。

1. ベンチマークは4000個のブロックをライブで保持し、各ステップはランダムなブロックを解放し、ランダムサイズの代替を割り当てます。要求の90％は16〜512バイト、9％は最大16 KiB、1％は128 KiB〜256 KiBです。各新しいブロックは、ページごとに1回の書き込みを受け取ります。アロケータは、新しいプロセスで500,000ステップを実行します。-O2でビルドされています。Intel Xeon E3-1230 v3で実行されました。↩︎