mallocの動的メモリ管理構造

malloc といえば、glibc などの標準Cライブラリで提供されている動的メモリ確保を行う関数です。
よく使われている分、メモリ破壊などの不具合に直面した方も多いのではないでしょうか。

そこで今回は、malloc のメモリ管理構造について簡単に説明いたします。
以下のような疑問を含め、問題の解析に役立つ内容と思いますので是非最後までご覧ください。

確保したサイズより少し大きなデータを書き込んだのに問題ないのはなぜ？
同じ領域を2度 free すると問題検出されるのはなぜ？

malloc の概要

malloc では、小さいサイズと大きなサイズのメモリ領域を確保する場合で動作が異なります。
サイズの境界は 128KB 付近にあります。

C++言語の登場により、インスタンスを生成する new オペレータで malloc が多用されるため、
小さなサイズのメモリ領域を確保する仕組みが複雑になっています。
メモリ使用効率を上げたり、迅速に処理を行うための工夫が施されているためです。

メモリ確保

小さなサイズ【～128KB】

システムコール sbrk で確保したヒープ領域を空きプールとして使用する
空きプールが足りなくなると、随時 sbrk を呼び出して拡張していく
要求されたサイズに応じて、malloc が管理する chunk という単位で切り売りする
要求側には chunk の管理領域を除いた領域の先頭アドレスを返す

大きなサイズ【128KB～】

システムコール mmap で確保したメモリ領域を使用する
malloc の管理構造は chunk で行い、小さなサイズの時と同じ

メモリの開放

小さなサイズ【～128KB】

free により開放されても、その時点でヒープ領域を減少させない
未使用となった chunk は、未使用リストにリンクして再利用する

大きなサイズ【128KB～】

free により解放されると、その時点で munmap を呼び出してメモリを開放する

メモリプール管理構造

chunk のメモリプールとは別に、プール全体を管理する仕組みがあります。
malloc では、メモリプールと管理部をまとめて「アリーナ（arena）」と呼びます。

プログラム起動時に、標準で使用するメインアリーナ（main arena）と呼ばれる管理部が存在します。
malloc が呼び出された際、このアリーナを元に空き領域を探しに行きます。
シングルスレッドで動くプログラムの場合は、このメインアリーナですべてを管理します。

一方、マルチコアの CPU 上で複数スレッドから malloc を呼び出す場合、
空き領域の探索が競合した際にメインアリーナとは別のアリーナが生成されます。
処理を迅速に行うため、空き領域の探索にロック待ちするのではなく、
管理部を新たに生成し、並列で空き領域を探索できるようになっています。

malloc で扱うメモリ単位【chunk】

malloc がメモリを切り売りする場合、chunk という管理単位を使用しています。
ここでは、この chunk に関する詳細を解説いたします。

chunk構造のイメージ

struct malloc_chunk {
  INTERNAL_SIZE_T      mchunk_prev_size; /* Size of previous chunk (if free). */
  INTERNAL_SIZE_T      mchunk_size;      /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;               /* double links -- used only if free. */
  struct malloc_chunk* bk;
  /* Only used for large blocks: pointer to next larger size. */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

struct malloc_chunk {

INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */

INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */

struct malloc_chunk* fd; /* double links -- used only if free. */

struct malloc_chunk* bk;

/* Only used for large blocks: pointer to next larger size. */

struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */

struct malloc_chunk* bk_nextsize;

};

malloc の chunk は、使用中の場合、未使用の場合とで使い方が異なります。
また、最後の fd_nextsize と bk_nextsize は、fd と bk と同じ使い方をするため、今回は割愛します。

使用中のメモリを管理する malloc chunk

malloc で確保した使用中のメモリは、以下のメンバを使って管理されます。

mchunk_prev_size
直前の chunk が使用中の場合、この領域は直前の chunk のユーザ領域として使用されます。
直前の chunk が未使用の場合は、この領域に直前の chunk サイズが格納されます。
mchunk_size
自分の chunk サイズを格納する領域です。
このサイズは、mchunk_prev_size や mchunk_size のヘッダー部分を含みます。

未使用のメモリを管理する malloc chunk

free で解放した後の未使用メモリは、以下のメンバを使って管理されます。

mchunk_size
自分の chunk サイズを格納する領域です。
このサイズは、mchunk_prev_size や mchunk_size のヘッダー部分を含みます。
fd,bk または fd_nextsize,bk_nextsize
forward(fd) と back(bk) は、アリーナの Free List に相互リンクされます。
mmap で確保されたメモリの場合は、fd_nextsize と bk_nextsize にサイズが格納されます。

malloc の状態管理

malloc chunk のサイズは、8 Bytes にアライメントされます。(8の倍数)
そのため、size メンバの下位 0～2 ビットは常に 0 となります。
この 3 ビットを利用し、malloc 内部で状態管理するためのフラグとして使用しています。

それぞれのビットが 1 の場合、以下のような意味を持ちます。

mallocの状態管理フラグ

NON_MAIN_ARENA
メインアリーナからリンクされていない
IS_MMAPPED (is allocated by mmap)
mmap によって確保された領域である
PREV_INUSE (previous chunk is in use)
直前の chunk が使用中である

chunk は、使用中のメモリを管理する場合と未使用の場合とで異なることを前述しました。
ヘッダ部の一部（mchunk_prev_size）は、直前の chunk のユーザ領域としても使用されます。
chunk の状態による違いについて、以下で説明します。

使用中のメモリを管理する malloc chunk の状態

使用中のメモリを管理するmalloc chunkの状態

使用中のメモリを管理する malloc chunk は、arena にリンクされていませんので fd, bk は使用しません。
この領域をユーザデータ領域として利用します。
また、次の chunk の prev_size も未使用となりますので、同様にユーザデータ領域として利用します。

malloc chunk の構造体を見たとき、「なぜリンクの fd, bk を先頭に持ってこないのだろう」と、
疑問に思った方もおられると思います。メモリを有効に活用するために配置も工夫されているのです。

未使用メモリを管理する malloc chunk の状態

未使用メモリを管理するmalloc chunkの状態

未使用のメモリを管理する malloc chunk は、arena にリンクされています。
fd, bk は同じリストに登録されている前後の chunk ポインタを格納します。
未使用の chunk がある場合、次の chunk の prev_size に、直前の chunk のサイズが格納されます。

malloc の動きを見てみよう

以下のようなプログラムを実行し、malloc chunk のメモリがどのように変化するか見てみましょう。
4KB のメモリを malloc で 3 つ確保し、memset で初期化して順番に free を呼び出す簡単なプログラムです。

#include <stdlib.h>
#include <string.h>

#define ALLOC_SIZE	(4096)

int
main(void) {
  void *ptr1, *ptr2, *ptr3;

  ptr1 = malloc(ALLOC_SIZE);
  ptr2 = malloc(ALLOC_SIZE);
  ptr3 = malloc(ALLOC_SIZE);

  memset(ptr1, 0, ALLOC_SIZE);
  memset(ptr2, 0, ALLOC_SIZE);
  memset(ptr3, 0, ALLOC_SIZE);

  free(ptr1);
  free(ptr2);
  free(ptr3);

  return 0;
}

#include <stdlib.h>

#include <string.h>

#define ALLOC_SIZE (4096)

int

main(void) {

void *ptr1, *ptr2, *ptr3;

ptr1 = malloc(ALLOC_SIZE);

ptr2 = malloc(ALLOC_SIZE);

ptr3 = malloc(ALLOC_SIZE);

memset(ptr1, 0, ALLOC_SIZE);

memset(ptr2, 0, ALLOC_SIZE);

memset(ptr3, 0, ALLOC_SIZE);

free(ptr1);

free(ptr2);

free(ptr3);

return 0;

}

メモリ確保・初期化直後の状態

 malloc呼び出し元に返されたアドレス
(gdb) p/x ptr1
$1 = 0x5555555592a0
(gdb) p/x ptr2
$2 = 0x55555555a2b0
(gdb) p/x ptr3
$3 = 0x55555555b2c0

malloc を呼び出して返されたアドレスは、prev_size と size の後のアドレスになるため、
それらの合計サイズ 16 バイト前が malloc chunk の先頭アドレスになります。

確保したメモリのそれぞれのメモリを見てみましょう。

 確保後のmalloc chunk
(gdb) x/4xg ptr1-16
0x555555559290: 0x0000000000000000 0x0000000000001011
0x5555555592a0: 0x0000000000000000 0x0000000000000000
(gdb) x/4xg ptr2-16
0x55555555a2a0: 0x0000000000000000 0x0000000000001011
0x55555555a2b0: 0x0000000000000000 0x0000000000000000
(gdb) x/4xg ptr3-16
0x55555555b2b0: 0x0000000000000000 0x0000000000001011
0x55555555b2c0: 0x0000000000000000 0x0000000000000000

それぞれの size 格納領域が、0x1011 になっています。

これは、確保した 0x1000 (4KB)に malloc chunk ヘッダーの 16バイトを加えたサイズ 0x1010、
chunk が使用中であることを示す最下位ビット（prev_inuse）に 1 がセットされて 0x1011 となっています。

free を順番に実行した後の変化

 ptr1解放後
(gdb) x/4xg ptr1-16
0x555555559290: 0x0000000000000000 0x0000000000001011
0x5555555592a0: 0x00007ffff7fb8be0 0x00007ffff7fb8be0
(gdb) x/4xg ptr2-16
0x55555555a2a0: 0x0000000000001010 0x0000000000001010
0x55555555a2b0: 0x0000000000000000 0x0000000000000000
(gdb) x/4xg ptr3-16
0x55555555b2b0: 0x0000000000000000 0x0000000000001011
0x55555555b2c0: 0x0000000000000000 0x0000000000000000

ptr1 を解放すると、以下の変化が起きます。

ptr1 の fd, bk に arena へのリンクがセットされます（0x7ffff7fb8be0, 0x7ffff7fb8be0）
ptr2 の prev_size に、ptr1 の chunk サイズがセットされます（=0x1010）
ptr2 の size の最下位ビット（prev_inuse）が 0 にセットされます（0x1011→0x1010）

 ptr2解放後
(gdb) x/4xg ptr1-16
0x555555559290: 0x0000000000000000 0x0000000000002021
0x5555555592a0: 0x00007ffff7fb8be0 0x00007ffff7fb8be0
(gdb) x/4xg ptr2-16
0x55555555a2a0: 0x0000000000001010 0x0000000000001010
0x55555555a2b0: 0x0000000000000000 0x0000000000000000
(gdb) x/4xg ptr3-16
0x55555555b2b0: 0x0000000000002020 0x0000000000001010
0x55555555b2c0: 0x0000000000000000 0x0000000000000000

ptr2 を解放すると、以下の変化が起きます。

ptr2 の size が ptr1 のサイズに加算されます（0x1011→0x2021）
ptr3 の prev_size に、ptr1 と ptr2 の chunk サイズの合算がセットされます（=0x2020）
ptr3 の size の最下位ビット（prev_inuse）が 0 にセットされます（0x1011→0x1010）

SANACHAN

空き chunk が連続して存在する場合、結合した chunk の情報がセットされます。

まとめ

いかがでしたでしょうか。
ここでは、malloc で確保したメモリ管理の仕組みを解説いたしました。

malloc / free で使用するメモリの破壊や 2 重解放の問題が起きた場合、
ここでの情報が解析に役立つことを願っております。