技術情報

技術情報

malloc(3)のメモリ管理構造

2007年11月30日

技術文書トップへ

malloc()

malloc()といえばC言語ではお馴染みのライブラリで、最も良く使用されるライブラリの一つです。しかしその分だけ何らかの不具合を経験した人も多いのではないでしょうか。本書ではmalloc()、free()で確保、解放されるメモリリソースが内部的にどのように管理されているかを説明していきます。mallocライブラリの仕様を理解する事で、ライブラリ使用時に何らかの不具合が発生した際の手助けになればと思います。
ここではLinuxディストリビューションで標準的に使用されているglibcのmallocライブラリを扱います。今回の調査では次の環境を使用しています。

  • ディストリビューション :Debian sarge
  • パッケージバージョン :glibc-2.3.2.ds1-22
  • OS : i386 Linux

本書では、上記の通りi386アーキテクチャの場合について記述しています。他のアーキテクチャ、64ビット環境では異なる場合もありますので、ご了承下さい。また、glibcのバージョンによっても多少異なる点があるかも知れませんが、こちらはそれほど大きな違いはないと思われます。

1. mallocライブラリの動きの概要

malloc()はプログラム内で必要なメモリを動的に確保したい場合に使う訳ですが、ではそのメモリはどの様に確保されているのでしょうか。
malloc()では通常、プロセスのアドレス空間のうちヒープという領域を利用しています。まずは特定のサイズのヒープ領域を空きプールとして確保します。これはsbrk()を使い現在のヒープ領域を拡張して行います。空きプールが足りなくなると随時sbrk()を発行してヒープ領域を拡張して補充します。そしてmalloc()はプロセスから要求されたサイズに応じてmalloc()の管理するchunkという単位で、確保したプールからメモリを切り出します。要求側にはchunkの管理部を除いた領域の先頭アドレスを返します。またmalloc()ではヒープ領域以外にも条件によりmmap()システムコールで確保した領域を利用します。どちらの領域を利用するかはプロセスから要求されたメモリサイズによって判断します。
malloc()によって確保されたメモリはfree()により解放しますが、実際にはその時点でヒープ領域が減少する訳ではありません。未使用となったchunkは未使用リストにリンクされ管理されます。そして次に要求のあった時に必要に応じて再利用されます(mmap()によって確保されたメモリについては、未使用リストにリンクされる事無くfree()の処理内でmunmap()により解放されます)。ただ永遠に解放しないと言う訳ではなく、一定の条件を満たした場合にはヒープ領域が減少されます。これらはメモリ確保の処理を迅速に行う為の仕組みですが、これ以外にも処理を迅速にする工夫がされています。それらについてもおいおい述べていきます。
上述のメモリプールとは別にプール全体を管理する管理部があります。これらメモリプールとメモリプール管理部をひとつのまとまりとした管理単位をmalloc()ではアリーナ(arena)と呼びます。

ページトップ

2. メモリ管理部の構造

前回、mallocライブラリ内でメモリを管理する器であるアリーナ(arena)の存在について述べました。今回はこのarenaの詳細について説明します。
arenaの管理部分はmalloc_stateという構造体で定義されています。コード上ではmalloc_stateのtypedefであるmstateが良く使われます。他にも処理上で使用される値を格納する情報としてmalloc_par構造体があります。変数名はmp_です。以下に構造体定義を示します。

【構造体定義】malloc/malloc.c:

struct malloc_state {
/* Serialize access.  */
   mutex_t mutex;
   /* Statistics for locking.  Only used if THREAD_STATS is defined.  */
   long stat_lock_direct, stat_lock_loop, stat_lock_wait;
   long pad0_[1]; /* try to give the mutex its own cacheline */
   /* The maximum chunk size to be eligible for fastbin */
   INTERNAL_SIZE_T  max_fast;   /* low 2 bits used as flags */
   /* Fastbins */
   mfastbinptr      fastbins[NFASTBINS];
   /* Base of the topmost chunk -- not otherwise kept in a bin */
   mchunkptr        top;
   /* The remainder from the most recent split of a small request */
   mchunkptr        last_remainder;
   /* Normal bins packed as described above */
   mchunkptr        bins[NBINS * 2];
   /* Bitmap of bins */
   unsigned int     binmap[BINMAPSIZE];
   /* Linked list */
   struct malloc_state *next;
   /* Memory allocated from the system in this arena.  */
   INTERNAL_SIZE_T system_mem;
   INTERNAL_SIZE_T max_system_mem;
 };
 struct malloc_par {
   /* Tunable parameters */
   unsigned long    trim_threshold;
   INTERNAL_SIZE_T  top_pad;
   INTERNAL_SIZE_T  mmap_threshold;
   /* Memory map support */
   int              n_mmaps;
   int              n_mmaps_max;
   int              max_n_mmaps;
   /* Cache malloc_getpagesize */
   unsigned int     pagesize;
   /* Statistics */
   INTERNAL_SIZE_T  mmapped_mem;
   /*INTERNAL_SIZE_T  sbrked_mem;*/
   /*INTERNAL_SIZE_T  max_sbrked_mem;*/
   INTERNAL_SIZE_T  max_mmapped_mem;
   INTERNAL_SIZE_T  max_total_mem; /* only kept for NO_THREADS */
   /* First address handed out by MORECORE/sbrk.  */
   char*            sbrk_base;
 };

デフォルトで使用されるarenaの管理部はmain_arenaという変数名で静的に定義されています。プログラムが起動された時点ではarenaはこの一つが存在するだけです。通常はこの一つのarenaで十分です。
また、プログラムが起動時点ではmain_arenaが存在するだけで、メモリプールはまだありません。メモリプールは最初のmalloc()が呼ばれた時に確保されます。最初のメモリプールの確保は空きエリアがない場合に、ヒープ領域を拡張する処理と同じ処理の流れで行われます。詳細は「4. mallocライブラリのメモリ確保の流れ」にて別途解説します。
状況によっては複数のarenaが必要となるケースがあります。プログラム中の複数のスレッド間で、arena使用の競合が生ずる場合です。そしてmalloc()ではこの競合を回避する為にarena使用の前後で排他制御をしています。これは該当arenaのmalloc_state.mutexを使ってmutexロックする事で行います。
あるスレッドがchunkを確保しようとした際にmain_arenaがロックされている場合、malloc()は別のarenaを生成します。この時のmain_arena以外のarenaはmmap()によって確保されます。このmmap()によって確保されるarena(以下、mmapped arena)は、生成時にmmapped arena領域の管理情報(heap_info)、arenaの管理部(malloc_state)、arenaのメモリプールを含んだサイズで確保されます。
複数のarenaが存在する場合malloc_state.nextに順次リンクされて行きます。全体のイメージは下記のようになります。

arenaの管理部について詳細を説明します。mmapped arena領域の管理情報(heap_info)については別途main_arena以外のarenaの説明の際に述べます。

【 表1 malloc_stateの主要なメンバの概要 】

メンバ 説明
mutex_t mutex 本arenaのロックに使用。
INTERNAL_SIZE_T max_fast fastbinsに登録するchunkの最大サイズ。(72)
mfastbinptr fastbins[NFASTBINS] 即時使用の為のchunkリストヘッダの配列。
mchunkptr top 確保したヒープ領域内の先頭chunkのポインタ。
mchunkptr last_remainder chunkを分割して確保した際に余った領域のポインタの最新のもの。
mchunkptr bins[NBINS * 2] 未使用chunkのリストヘッダ。
unsigned int binmap[BINMAPSIZE] binsのビットマップ。
struct malloc_state *next 別arenaへの管理部のポインタ。
INTERNAL_SIZE_T system_mem 確保したメモリ領域サイズ。(mmapで確保したchunkサイズを含まない)
INTERNAL_SIZE_T max_system_mem これまでのsystem_memの最大サイズをメモ。

【 表2 malloc_parの主要なメンバの概要 】

メンバ 説明
unsigned long trim_threshold ヒープをトリミングする閾値。(131072)
INTERNAL_SIZE_T top_pad arenaを拡張する時のサイズ算出に使用。(131072)
INTERNAL_SIZE_T mmap_threshold chunkをmmapで確保するかどうかの閾値。(131072)
int n_mmaps マッピング中のmmap()のコール数。mmap()発行でカウントアップ、munmap()発行でカウントダウン。(※1
int n_mmaps_max n_mmapsの最大数。(65536)
int max_n_mmaps これまでのn_mmapsの最大値をメモ。(※1
unsigned int pagesize ページサイズ。(4096)
INTERNAL_SIZE_T mmapped_mem mmap()でマッピングした領域サイズの合計。(※1
INTERNAL_SIZE_T max_mmapped_mem これまでのmmapped_memの最大値をメモ。(※1
INTERNAL_SIZE_T max_total_mem mmapped_mem、system_mem、arena_memの合計。
char sbrk_base main_arenaが使用するヒープ領域の開始アドレス。

上記以外にarena_memという静的変数があります。これはmain_arena以外のarenaのheap_info->sizeの合計を保有しています。

max_fast
fastbinsに登録するchunkの最大サイズで72byteになります。0ビット目はfastbinsにchunkが存在するかどうかのフラグになっています。マスクとしてFASTCHUNKS_BITを使用します。
fastbins
fastbinsは要求メモリを迅速に確保する為に用意されたchunkのリストヘッダです。NFASTBINSは次の式で算出される値です。

【 NFASTBINSの算出 】malloc/malloc.c:

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz)        ((((unsigned int)(sz)) >> 3) - 2)
/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     80
#define NFASTBINS  (fastbin_index(request2size(MAX_FAST_SIZE))+1)

この値は10になります。free()で解放されるchunkの内、サイズがmax_fast以下のものはこのリストに登録されます。登録先のインデックスは次の式で求めます。

#define fastbin_index(sz) ((((unsigned int)(sz)) >> 3) - 2)

上記のszは解放するchunkのサイズです。chunkは8バイト単位で拡張されますので3ビットシフトします。また最小のchunkサイズは16であり、これがインデックス0の管理部となる様に2減算しています。
前述のようにmax_fastの0ビット目はfastbins上のchunk存在有無を示しています。0ビット目がオンの場合存在しない事を示します。chunk登録時にこれをオフとします。
このリストは処理の迅速化の為に前方リンクのみとなっています。またchunk内の管理部は解放前の状態が保たれています。これによりchunk確保時のchunk管理部設定の手間を省いています。

top
確保したヒープ領域はそれ自体も一つの巨大な「空き」のchunkとして管理されます。ここで言う空きとはユーザにも使用されておらず、chunk管理部にもリンクされていない事を意味します。chunkを新たに確保する際ヒープのベースより切り取っていき、空きのchunkサイズを縮め新たなchunkとします。topはこの空きのchunkの先頭アドレスを保持しています。
last_remainder
要求のあったサイズと合致するchunkが見つからない場合、既存のchunkを要求サイズで分割する場合があります。残りの領域は新たなchunkとして登録されます。last_remainderはこの時の残りのchunkの内、最新のアドレスを格納します。
bins
これは解放されたmax_fastより上のサイズのchunkを登録するリストヘッダの配列です。ヘッダはフォワードチェーン(fd)、バックチェーン(bk)で一組になっています。
binsのサイズはNBINSが今128なので256個の配列となっていますが、fd、bkで一組になりますので128個のリストヘッダがある事になります。
この内ヘッダ0(インデックス0、1の配列要素)は未使用になっています。ヘッダ1(インデックス2、3の配列要素)は別の用途で使用される為、ヘッダ2(インデックス4、5の配列要素)以降が通常のchunk登録リストのヘッダとなります。但しヘッダ64以上(128、129の配列要素)はサイズ512byte以上の大き目のchunkの登録用になっています。
512byte未満のサイズのchunkはサイズを3ビットシフトした値がヘッダのインデックス(2~63)となります。大き目のサイズのchunkリストヘッダのインデックスの算出は次のようになっています。

【 chunkリストヘッダ 】malloc/malloc.c:

#define largebin_index(sz)                                                   \
(((((unsigned long)(sz)) >>  6) <= 32)?  56 + (((unsigned long)(sz)) >>  6): \
 ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): \
 ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
 ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): \
 ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): \
                                        126)

初期化時にはヘッダは自身のヘッダのアドレスが設定されています。下記は初期化時のmain_arenaのダンプになります。アドレス0x80b4144の位置が最新のフリーchunkをチェーンするヘッダ1ですが、一つ前の管理部のアドレス0x080b413cが設定されています。これは、ヘッダをchunkの管理部であるmalloc_chunk構造体を使って参照する為です。chunkのリンク操作はmalloc_chunkの先頭から8バイト目のfd、bkメンバにより行っており、該当ヘッダ部のアドレスをfdメンバとして参照する為に一つ前のヘッダ部のアドレス(管理部のアドレスのマイナス8バイトした所のアドレス)が使用されています。

【 main_arenaのダンプ 】

(gdb) x/400xw &main_arena
0x80b40e0 <main_arena>   :  0x00000001 0x00000000 0x00000000 0x00000000
0x80b40f0 <main_arena+16>:  0x00000000 0x00000000 0x00000000 0x00000000
0x80b4100 <main_arena+32>:  0x00000000 0x00000000 0x00000049 0x00000000
0x80b4110 <main_arena+48>:  0x00000000 0x00000000 0x00000000 0x00000000
0x80b4120 <main_arena+64>:  0x00000000 0x00000000 0x00000000 0x00000000
0x80b4130 <main_arena+80>:  0x00000000 0x0848b2e0 0x00000000 0x00000000
0x80b4140 <main_arena+96>:  0x00000000 0x080b413c 0x080b413c 0x080b4144
0x80b4150 <main_arena+112>: 0x080b4144 0x080b414c 0x080b414c 0x080b4154
0x80b4160 <main_arena+128>: 0x080b4154 0x080b415c 0x080b415c 0x080b4164
0x80b4170 <main_arena+144>: 0x080b4164 0x080b416c 0x080b416c 0x080b4174
0x80b4180 <main_arena+160>: 0x080b4174 0x080b417c 0x080b417c 0x080b4184
0x80b4190 <main_arena+176>: 0x080b4184 0x080b418c 0x080b418c 0x080b4194
0x80b41a0 <main_arena+192>: 0x080b4194 0x080b419c 0x080b419c 0x080b41a4
...

先程ヘッダ1は別の用途で使用すると述べましたが、ここには一時保存リストとしてサイズ毎のbinsリストに登録されるまでのchunkが登録されます。malloc()内ではこのヘッダはunsorted_chunks()で参照しています。解放されたchunkはまず一旦このヘッダに全て登録されます(但しfastbinsの対象となるものは除きます)。ここに登録されたchunkはメモリ獲得処理の延長でチェックされた際に確保対象でないと判断された場合にbinsに再登録されます。

binmap
これはbinsの各リスト上のchunkの有無を示します。あるbinsのリストにchunkが登録された場合、そのリストのインデックスに相当するbinmapのビットをオンとします。chunkを持つbinsのリストヘッダを素早く検索する為に使用します。
BINMAPSIZEはNBINSを32で割った値で4となります。
next
複数のarenaがある場合に、ここにarenaをリンクしていきます。mmapped arenaの場合malloc_stateの前にheap_info情報がありますがnextにはmalloc_state情報のポインタを格納します。arenaがmain_arenaのみの場合はmain_arenaのmalloc_state情報ポインタが設定されています。

以上でarena管理部の項目の説明は終わりです。malloc_parの項目は処理を行う上での閾値、条件判断の為の最大値、統計的な意味合いの情報の格納エリアを提供します。これらについては次回以降の説明の中で述べて行きます。
最後にmalloc_state構造体の全体図を示します。

※1 chunkとして確保したmmapが対象です。

ページトップ

3. mallocライブラリで扱うメモリ単位

前回までの説明の中でmalloc()がメモリを扱う為のchunkという管理単位が登場していました。今回はこのchunkに関する詳細を解説していきます。
chunkは以前述べました様に必要に応じメモリプールの一部を切り取って作成します。chunkにはヘッダ部とユーザ使用領域があります。mmap領域として確保されたchunk(以下、mmapped chunk)についても構成は同じですが、使い方に少し異なる部分があります。これについては別途「6. mmapped chunkの確保、解放」の章にて解説します。

下記の構造体がchunkのヘッダ部分になります。

【 chunkのヘッダ部分 】malloc/malloc.c:

struct malloc_chunk {
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
};

sizeメンバはchunk全体のサイズでchunkのヘッダ部のサイズも含んでいます。prev_sizeメンバはメモリ上で隣接する直前のchunkのサイズを格納します。fd、bkはarenaのchunk管理部へ登録された場合の前後のchunkへのリンクポインタです。
chunkサイズは8の倍数で作成されるのでsizeメンバのビット0-2は常に0になります。この3ビットを利用してフラグとして使用しています。この為chunkのサイズを得るにはsizeメンバの格納する値の下位3ビットをマスクする必要があります。
それぞれのビットがオンの場合、右図のような意味を持ちます。
chunkにはヘッダ部とユーザ使用領域があると前述しましたが、ヘッダ部の一部はユーザ領域としても使用されます。chunkの状態によるヘッダ部分の用途の違いについて以下に説明します。

未使用のchunkの場合
未使用のchunkはarena管理部の何れかのリストにリンクされています。fd、bkは同じ管理部に登録されている前後のchunkのポインタを格納します。リスト上の先頭chunkのbkと最後尾のchunkのfdは、arena管理部のポインタを格納します。但しこのポインタはリンクしている管理部のアドレスではなく、その8バイト前のアドレスになります。これは管理部のアドレスをmalloc_chunk構造体のfd、bkで参照する為に、先頭メンバのprev_sizeにあたるアドレスを格納しているからです。
未使用のchunkがある場合、メモリ上で直後にあるchunkのヘッダ部のprev_sizeメンバには、直前のchunkのサイズが設定されています。これはarena管理部のchunkリストに登録されているchunkの前後ではありませんので注意下さい。
使用中のchunkの場合
使用中のchunkとその直後のchunkのヘッダー状態を見てみます。
使用中のchunkはarena管理部にチェーンされておりませんので、fd、bkは使用しておりません。そこでこの領域をユーザ領域として利用しています。
また直前のchunkが使用中の場合はprev_sizeも未使用ですので、同様に直前のchunkのユーザ使用領域の一部として使われます。
chunkの管理部を参照する際、-8バイトした場所を先頭としていました。fd、bkを先頭に持ってくればすっきりするのではないかと思われた人もいるかもしれませんが、メモリの有効利用の為もあってこの様な配置になっている訳です。
main_arenaで次の連続するchunkがある場合の例
chunk 1:
size:24byte
使用中
ユーザからの要求 20byte
chunk 2:
size:32byte
使用中
ユーザからの要求 21byte
chunk 3:
size:mm byte
未使用
chunk 4:
size:nn byte

arena管理部にチェーンしているchunkのイメージ図を示します。

ページトップ

4. mallocライブラリのメモリ確保の流れ

今回はメモリを確保する時の流れについて見てみましょう。
malloc()をコールするとmalloc/malloc.c内のpublic_mALLOc()関数を呼び出します。メモリ確保の主要な処理はpublic_mALLOc()から呼ばれる_int_malloc()で行われます。ここでは主に_int_malloc()内の処理を中心に説明を行っていきます。また、_int_malloc()のソースリストもありますので参照して下さい。

【 _int_malloc()のソースリスト 】malloc/malloc.c _int_malloc():

 Void_t*
 _int_malloc(mstate av, size_t bytes)
 {
   INTERNAL_SIZE_T nb;               /* normalized request size */
   unsigned int    idx;              /* associated bin index */
   mbinptr         bin;              /* associated bin */
   mfastbinptr*    fb;               /* associated fastbin */

   mchunkptr       victim;           /* inspected/selected chunk */
   INTERNAL_SIZE_T size;             /* its size */
   int             victim_index;     /* its bin index */

   mchunkptr       remainder;        /* remainder from a split */
   unsigned long   remainder_size;   /* its size */

   unsigned int    block;            /* bit map traverser */
   unsigned int    bit;              /* bit map traverser */
   unsigned int    map;              /* current word of binmap */

   mchunkptr       fwd;              /* misc temp for linking */
   mchunkptr       bck;              /* misc temp for linking */

   /*
     Convert request size to internal form by adding SIZE_SZ bytes
     overhead plus possibly more to obtain necessary alignment and/or
     to obtain a size of at least MINSIZE, the smallest allocatable
     size. Also, checked_request2size traps (returning 0) request sizes
     that are so large that they wrap around zero when padded and
     aligned.
   */

   checked_request2size(bytes, nb);                                       ---- 1-1

   /*
     If the size qualifies as a fastbin, first check corresponding bin.
     This code is safe to execute even if av is not yet initialized, so we
     can try it without checking, which saves some time on this fast path.
   */

   if ((unsigned long)(nb) <= (unsigned long)(av->max_fast)) {            ---- 1-2
     fb = &(av->fastbins[(fastbin_index(nb))]);
     if ( (victim = *fb) != 0) {
       *fb = victim->fd;
       check_remalloced_chunk(av, victim, nb);
       return chunk2mem(victim);
     }
   }

   /*
     If a small request, check regular bin. Since these "smallbins"
     hold one size each, no searching within bins is necessary.
     (For a large request, we need to wait until unsorted chunks are
     processed to find best fit. But for small ones, fits are exact
     anyway, so we can check now, which is faster.)
   */

   if (in_smallbin_range(nb)) {                                           ---- 1-3
     idx = smallbin_index(nb);
     bin = bin_at(av,idx);

     if ( (victim = last(bin)) != bin) {
       if (victim == 0) /* initialization check */
         malloc_consolidate(av);
       else {                                                             ---- 1-4
         bck = victim->bk;
         set_inuse_bit_at_offset(victim, nb);
         bin->bk = bck;
         bck->fd = bin;

         if (av != &main_arena)
           victim->size |= NON_MAIN_ARENA;
         check_malloced_chunk(av, victim, nb);
         return chunk2mem(victim);
       }
     }
   }

   /*
      If this is a large request, consolidate fastbins before continuing.
      While it might look excessive to kill all fastbins before
      even seeing if there is space available, this avoids
      fragmentation problems normally associated with fastbins.
      Also, in practice, programs tend to have runs of either small or
      large requests, but less often mixtures, so consolidation is not
      invoked all that often in most programs. And the programs that
      it is called frequently in otherwise tend to fragment.
   */

   else {                                                                 ---- 1-5
     idx = largebin_index(nb);
     if (have_fastchunks(av))
       malloc_consolidate(av);
   }

   /*
     Process recently freed or remaindered chunks, taking one only if
     it is exact fit, or, if this a small request, the chunk is remainder from
     the most recent non-exact fit. Place other traversed chunks in
     bins. Note that this step is the only place in any routine where
     chunks are placed in bins.

     The outer loop here is needed because we might not realize until
     near the end of malloc that we should have consolidated, so must
     do so and retry. This happens at most once, and only when we would
     otherwise need to expand memory to service a "small" request.
   */

   for(;;) {                                                              ---- 1-6

     while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
       bck = victim->bk;
       size = chunksize(victim);

       /*
          If a small request, try to use last remainder if it is the
          only chunk in unsorted bin. This helps promote locality for
          runs of consecutive small requests. This is the only
          exception to best-fit, and applies only when there is
          no exact fit for a small chunk.
       */

       if (in_smallbin_range(nb) &&                                       ---- 1-7
           bck == unsorted_chunks(av) &&
           victim == av->last_remainder &&
           (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) {

         /* split and reattach remainder */
         remainder_size = size - nb;
         remainder = chunk_at_offset(victim, nb);
         unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
         av->last_remainder = remainder;
         remainder->bk = remainder->fd = unsorted_chunks(av);

         set_head(victim, nb | PREV_INUSE |
                  (av != &main_arena ? NON_MAIN_ARENA : 0));
         set_head(remainder, remainder_size | PREV_INUSE);
         set_foot(remainder, remainder_size);

         check_malloced_chunk(av, victim, nb);
         return chunk2mem(victim);
       }

       /* remove from unsorted list */
       unsorted_chunks(av)->bk = bck;
       bck->fd = unsorted_chunks(av);

       /* Take now instead of binning if exact fit */

       if (size == nb) {                                                  ---- 1-8
         set_inuse_bit_at_offset(victim, size);
         if (av != &main_arena)
           victim->size |= NON_MAIN_ARENA;
         check_malloced_chunk(av, victim, nb);
         return chunk2mem(victim);
       }

       /* place chunk in bin */

       if (in_smallbin_range(size)) {                                     ---- 1-9
         victim_index = smallbin_index(size);
         bck = bin_at(av, victim_index);
         fwd = bck->fd;
       }
       else {                                                             ---- 1-10
         victim_index = largebin_index(size);
         bck = bin_at(av, victim_index);
         fwd = bck->fd;

         /* maintain large bins in sorted order */
         if (fwd != bck) {
           /* Or with inuse bit to speed comparisons */
           size |= PREV_INUSE;
           /* if smaller than smallest, bypass loop below */
           assert((bck->bk->size & NON_MAIN_ARENA) == 0);
           if ((unsigned long)(size) <= (unsigned long)(bck->bk->size)) {
             fwd = bck;
             bck = bck->bk;
           }
           else {
             assert((fwd->size & NON_MAIN_ARENA) == 0);
             while ((unsigned long)(size) < (unsigned long)(fwd->size)) {
               fwd = fwd->fd;
               assert((fwd->size & NON_MAIN_ARENA) == 0);
             }
             bck = fwd->bk;
           }
         }
       }

       mark_bin(av, victim_index);
       victim->bk = bck;
       victim->fd = fwd;
       fwd->bk = victim;
       bck->fd = victim;
     }

     /*
       If a large request, scan through the chunks of current bin in
       sorted order to find smallest that fits. This is the only step
       where an unbounded number of chunks might be scanned without doing
       anything useful with them. However the lists tend to be short.
     */

     if (!in_smallbin_range(nb)) {                                        ---- 1-11
       bin = bin_at(av, idx);

       /* skip scan if empty or largest chunk is too small */
       if ((victim = last(bin)) != bin &&
           (unsigned long)(first(bin)->size) >= (unsigned long)(nb)) {

         while (((unsigned long)(size = chunksize(victim)) <
                 (unsigned long)(nb)))
           victim = victim->bk;

         remainder_size = size - nb;
         unlink(victim, bck, fwd);

         /* Exhaust */
         if (remainder_size < MINSIZE) {
           set_inuse_bit_at_offset(victim, size);
           if (av != &main_arena)
             victim->size |= NON_MAIN_ARENA;
           check_malloced_chunk(av, victim, nb);
           return chunk2mem(victim);
         }
         /* Split */
         else {
           remainder = chunk_at_offset(victim, nb);
           unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
           remainder->bk = remainder->fd = unsorted_chunks(av);
           set_head(victim, nb | PREV_INUSE |
                    (av != &main_arena ? NON_MAIN_ARENA : 0));
           set_head(remainder, remainder_size | PREV_INUSE);
           set_foot(remainder, remainder_size);
           check_malloced_chunk(av, victim, nb);
           return chunk2mem(victim);
         }
       }
     }

     /*
       Search for a chunk by scanning bins, starting with next largest
       bin. This search is strictly by best-fit; i.e., the smallest
       (with ties going to approximately the least recently used) chunk
       that fits is selected.

       The bitmap avoids needing to check that most blocks are nonempty.
       The particular case of skipping all bins during warm-up phases
       when no chunks have been returned yet is faster than it might look.
     */

     ++idx;                                                               ---- 1-12
     bin = bin_at(av,idx);
     block = idx2block(idx);
     map = av->binmap[block];
     bit = idx2bit(idx);

     for (;;) {

       /* Skip rest of block if there are no more set bits in this block. */
       if (bit > map || bit == 0) {
         do {
           if (++block >= BINMAPSIZE)  /* out of bins */
             goto use_top;
         } while ( (map = av->binmap[block]) == 0);

         bin = bin_at(av, (block << BINMAPSHIFT));
         bit = 1;
       }

       /* Advance to bin with set bit. There must be one. */
       while ((bit & map) == 0) {
         bin = next_bin(bin);
         bit <<= 1;
         assert(bit != 0);
       }

       /* Inspect the bin. It is likely to be non-empty */
       victim = last(bin);

       /* If a false alarm (empty bin), clear the bit. */
       if (victim == bin) {
         av->binmap[block] = map &= ~bit; /* Write through */
         bin = next_bin(bin);
         bit <<= 1;
       }

       else {
         size = chunksize(victim);

         /* We know the first chunk in this bin is big enough to use. */
         assert((unsigned long)(size) >= (unsigned long)(nb));

         remainder_size = size - nb;

         /* unlink */
         bck = victim->bk;
         bin->bk = bck;
         bck->fd = bin;

         /* Exhaust */
         if (remainder_size < MINSIZE) {
           set_inuse_bit_at_offset(victim, size);
           if (av != &main_arena)
             victim->size |= NON_MAIN_ARENA;
           check_malloced_chunk(av, victim, nb);
           return chunk2mem(victim);
         }

         /* Split */
         else {
           remainder = chunk_at_offset(victim, nb);

           unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
           remainder->bk = remainder->fd = unsorted_chunks(av);
           /* advertise as last remainder */
           if (in_smallbin_range(nb))
             av->last_remainder = remainder;

           set_head(victim, nb | PREV_INUSE |
                    (av != &main_arena ? NON_MAIN_ARENA : 0));
           set_head(remainder, remainder_size | PREV_INUSE);
           set_foot(remainder, remainder_size);
           check_malloced_chunk(av, victim, nb);
           return chunk2mem(victim);
         }
       }
     }

   use_top:
     /*
       If large enough, split off the chunk bordering the end of memory
       (held in av->top). Note that this is in accord with the best-fit
       search rule. In effect, av->top is treated as larger (and thus
       less well fitting) than any other available chunk since it can
       be extended to be as large as necessary (up to system
       limitations).

       We require that av->top always exists (i.e., has size >=
       MINSIZE) after initialization, so if it would otherwise be
       exhuasted by current request, it is replenished. (The main
       reason for ensuring it exists is that we may need MINSIZE space
       to put in fenceposts in sysmalloc.)
     */

     victim = av->top;
     size = chunksize(victim);
 
     if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {        ---- 1-13
       remainder_size = size - nb;
       remainder = chunk_at_offset(victim, nb);
       av->top = remainder;
       set_head(victim, nb | PREV_INUSE |
                (av != &main_arena ? NON_MAIN_ARENA : 0));
       set_head(remainder, remainder_size | PREV_INUSE);

       check_malloced_chunk(av, victim, nb);
       return chunk2mem(victim);
     }

     /*
       If there is space available in fastbins, consolidate and retry,
       to possibly avoid expanding memory. This can occur only if nb is
       in smallbin range so we didn't consolidate upon entry.
     */

     else if (have_fastchunks(av)) {                                      ---- 1-14
       assert(in_smallbin_range(nb));
       malloc_consolidate(av);
       idx = smallbin_index(nb); /* restore original bin index */
     }

     /*
        Otherwise, relay to handle system-dependent cases
     */
     else                                                                 ---- 1-15
       return sYSMALLOc(nb, av);
   }
 }
arenaの確保
_int_malloc()を呼び出す前に、まずはchunk確保先のarenaを決定します。これにはarena_get()を使います。arena_get()ではmain_arenaをチェックしロックされているとmain_arena->nextを順に辿り、使用できるarenaを検索します。この時、全てのarenaが使用不可の場合、新たにarenaを生成します。これは以前述べた様にmmap()により確保しmain_arena->nextからチェーンされるリストの先頭にリンクします。arena_get()からは確保された既存arenaまたは新たに生成されたarenaの管理部のアドレスが戻されます。ここで確保されたarenaはarena_get()から戻った時点でロックされています。このarenaより要求のサイズのchunkを取得します。
chunkサイズの算出
_int_malloc()ではまずユーザの要求サイズから確保するchunkのサイズを求めます。(ソースリスト 1-1参照)
これはchecked_request2sizeマクロを使用しますが、ここからマクロrequest2sizeを用いて算出されます。

【 マクロrequest2size 】malloc/malloc.c:

#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ?              \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
/*  Same, except also perform argument check */
#define checked_request2size(req, sz)                             \
  if (REQUEST_OUT_OF_RANGE(req)) {                                \
    MALLOC_FAILURE_ACTION;                                        \
    return 0;                                                     \
  }                                                               \
  (sz) = request2size(req);

式の中のオペランドは下記の内容を持ちます。

  • req
    :ユーザの要求サイズ
  • SIZE_SZ
    :chunkのサイズ格納領域のサイズ(4)
  • MALLOC_ALIGN_MASK
    :chunkサイズを8の倍数にアラインメントするため(7)
  • MINSIZE
    最小chunkサイズ(16)

上記より必要となるchunkのサイズは、例えばreq=8の場合は16、req=64の場合は72と求められます。
ソース上の変数avは求めたarenaのポインタ(malloc_state 構造体のポインタ)、変数nbは確保するchunkのサイズになります。

fastbinsのチェック
上記で求めたサイズでchunkの確保処理が行われて行きます。まず最初にav->fastbinsリストをチェックします。(ソースリスト 1-2参照)
求めたサイズがnb <= av->max_fastの場合fastbinsよりchunkを確保しようとします。fastbin_index(nb)でインデックスを求め、該当のサイズのリストヘッダにchunkがあればリストから外しユーザ使用領域のアドレスをリターンします。fastbinsに登録されたchunkは使用時の状態を維持しており、fd メンバを使ってリンクしているだけなので、リストヘッダから外す際には確保したchunkのfdメンバの値(ネクストchunkのアドレス)をリストヘッダに設定するだけで処理は終わりです。
bins のチェック
fastbinsでchunkを確保できない場合av->binsリストをチェックします。これはnb >= 512とnb < 512の場合で処理が異なります。
nb < 512(in_smallbin_range(nb)が真)の場合は、smallbin_index(nb)で該当のサイズのリストヘッダのインデックスを求めます。(ソースリスト 1-3参照)
求めたリストヘッダにchunkがあればリスト上の最後のchunkを外しユーザ使用領域のアドレスをリターンします。この時、アンリンクする為に次の処理を行います。(ソースリスト 1-4参照)
  • メモリ上の直後のchunkのsizeメンバにPREV_INUSE(malloc_chunk.sizeの0ビット目)を設定
  • リスト上の一つ前のchunkとリストヘッダのfd、 bkメンバの更新
  • maina_arenaかどうかをチェックしmaina_arenaでなければNON_MAIN_ARENA(malloc_chunk.sizeの2ビット目)を設定

それほど大した処理ではありませんが、fastbinsではこの辺の処理がfdの更新だけで済みます。
nb >= 512の場合、fastbinsに登録されたchunkがあった(max_fastとFASTCHUNKS_BITとの&が0の時)場合にmalloc_consolidate(av)を呼び出すだけです。(ソースリスト 1-5参照)
malloc_consolidate()は所々で出て来ますのでここで説明します。一言で言うとこれは小さなchunkで断片化したメモリプールのデフラグを行っています。malloc_consolidate()をコールする事により大きなサイズのchunkをできるだけ用意しておく訳です。
ではmalloc_consolidate()の説明です。解放されたchunkの内max_fast以下のサイズのものは無条件にfastbinsに登録される為、大きなサイズになり得る領域を分断しているかもしれません。malloc_consolidate()ではfastbinsに登録された全chunkをこのリストから削除します。
削除する際に、前後のchunkをチェックし未使用ならばリストより外してchunk同士を結合し新たなchunkとします。解放されたchunkは次に説明するunsorted_chunksに登録されます。結合と言っても単にchunkのsizeメンバの値の合計を新たなchunkのsizeメンバの値として設定するだけです。

unsorted_chunksのチェック
次にunsorted_chunksをチェックします。ここにはサイズ毎のbinsリストに登録する前のchunkが登録されています。unsorted_chunksからchunkを順次取り出して行き、該当のchunkを確保するかunsorted_chunksの全てのchunkをbinsに登録し終わるまで処理を繰り返します。(ソースリスト 1-6参照)
まずunsorted_chunksから取り出したchunkが次の条件を満たす場合、必要なサイズに分割して確保したchunkをリターンします。残りのchunkはunsorted_chunksに登録します。(ソースリスト 1-7参照)
  • nb < 512
  • unsorted_chunksに登録されているchunkが一つ
  • chunk == last_remainder
  • chunkサイズ > nb + MINSIZE(16)

何故、chunk == last_remainderというチェックが必要なのでしょう。これはchunkを分割する領域をある程度かためておきフラグメントの発生する範囲が広がらない様にする為です。
次にnbとchunkのサイズが等しい場合そのchunkをリターンします。(ソースリスト 1-8参照)
上記チェックで確保されない場合、取り出したchunkはbinsに登録します。nb < 512の場合、smallbin_index(size)でインデックスを求め、該当のサイズのリストヘッダの先頭に chunkを登録します。(ソースリスト 1-9参照)
nb >= 512の場合、largebin_index(size)でインデックスを求め、該当のサイズのリストヘッダにサイズが大きな順にchunkを登録します。(ソースリスト 1-10参照)
そしてbinmapに登録したリストの位置のビットをオンにします。
unsorted_chunksが空でないなら本項処理の最初に戻り処理を繰り返します。

512バイト以上のchunkのチェック
512バイト以上のchunkの確保はここで行います。largebin_index(nb)でインデックスを求め、該当のサイズのリストヘッダを要求します。(ソースリスト 1-11参照)
このリストに登録されたchunkの中からnbより大きいサイズの内で最小のchunkを検索します。chunkのsizeとnbとの差がMINSIZE以上の場合、分割します。余ったchunkはunsorted_chunksに登録します。
要求サイズ以上のサイズのchunkをチェック
この段階でchunkが確保できない場合は要求されたサイズに該当するリスト上にchunkは無いという事になります。そこで確保サイズのインデックスより上のインデックスのリストを検索して行きます。(ソースリスト 1-12参照)
nbから求めたインデックス+1の位置からbinmapの検索を開始して、ビットがオンのリストを見つけます。ここでビットがオンのものがない場合は次の処理に移ります。リストが見つかった場合はchunkのサイズにより次の様に処理します。
  • chunkのsizeとnbとの差がMINSIZE未満の場合、確保したchunkをリターンします
  • chunkのsizeとnbとの差がMINSIZE以上の場合
    -分割して残ったchunkをunsorted_chunksに登録
    -残ったchunkのアドレスをlast_remainderにメモ(nb < 512の場合)
    -リストヘッダ部の更新
    -確保したchunkをリターン
chunkの生成
ここまで来た場合はarenaに有効なchunkがないという事になります。そこで空き領域のチェックをし、新たにchunkを生成します。空き領域はav->top(先頭の空きchunk)からポイントされています。chunkのsizeとnbとの差がMINSIZE以上ある場合、分割します。余ったchunkはtopに登録しリターンします。(ソースリスト 1-13参照)
chunkのsizeとnbとの差がMINSIZE未満の場合は次の処理を行います。
  • fastbinsにchunkがある場合malloc_consolidate()をコールし、上記「unsorted_chunksのチェック」に戻ります。nb < 512の場合malloc_consolidate()をコールしていないので、これで利用可能なchunkが得られる様になるかもしれません。(ソースリスト 1-14参照)
  • fastbinsにもchunkがない場合arenaを拡張します。arenaの拡張はsYSMALLOc()で行われます。この関数は拡張後chunkのアドレスをリターンします。_int_malloc()からも確保されたアドレスをリターンし処理は終了します。(ソースリスト 1-15参照)

sYSMALLOc()の動きについて簡単に説明します。ここではmain_arenaでないarenaの場合の説明については除きます。
要求サイズnbがmp_.mmap_threshold以上の場合、mmap()で領域の確保を行います。この部分の説明は別章「6. mmapped chunkの確保、解放」にて行います。nbがmp_.mmap_threshold未満の場合ヒープ領域を拡張します。次の式で拡張サイズを算出します。
nb + mp_.top_pad + MINSIZE
これよりav->topのサイズを引いた(未使用領域も考慮した)サイズを拡張サイズとします。更にこのサイズをページサイズに換算します。この様にして求めたサイズでsbrk()をコールしてヒープ領域を拡張します。得られた領域をav->topに設定します。この中からnbのchunkを切り出しそのアドレスをリターンします。メモリプールがない状態でsYSMALLOc()が呼ばれた場合も同様の流れでメモリプールの生成が行われます。ただメモリプールの先頭を8バイト境界になる様に調整する所が異なります。そのアドレスがav->topとして設定されます。
public_mALLOc()に戻った後、arenaのロックを解除し得られたアドレスをコール側に戻します。

以上がchunk確保の処理になります。

ページトップ

5. freeライブラリのメモリ解放の流れ

では次にメモリを解放する時の流れを見てみましょう。こちらは、メモリ確保のコード程、複雑ではありません。
free()をコールするとmalloc/malloc.c内のpublic_fREe()関数を呼び出します。メモリ確保の主要な処理はpublic_fREe()より呼ばれる_int_free()で行われます。ここでは主に_int_free()内の処理を中心に説明を行います。また、_int_free()のソースリストもありますので参照して下さい。

【 _int_free() のソースリスト 】malloc/malloc.c _int_free():

 void
 _int_free(mstate av, Void_t* mem)
 {
   mchunkptr       p;           /* chunk corresponding to mem */
   INTERNAL_SIZE_T size;        /* its size */
   mfastbinptr*    fb;          /* associated fastbin */
   mchunkptr       nextchunk;   /* next contiguous chunk */
   INTERNAL_SIZE_T nextsize;    /* its size */
   int             nextinuse;   /* true if nextchunk is used */
   INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
   mchunkptr       bck;         /* misc temp for linking */
   mchunkptr       fwd;         /* misc temp for linking */


   /* free(0) has no effect */
   if (mem != 0) {
     p = mem2chunk(mem);
     size = chunksize(p);

     /* Little security check which won't hurt performance: the
        allocator never wrapps around at the end of the address space.
        Therefore we can exclude some size values which might appear
        here by accident or by "design" from some intruder. */
     if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0))
       {
         if (check_action & 1)
           {
 #ifdef _LIBC
             _IO_flockfile (stderr);
             int old_flags2 = ((_IO_FILE *) stderr)->_flags2;
             ((_IO_FILE *) stderr)->_flags2 |= _IO_FLAGS2_NOTCANCEL;
 #endif
             fprintf (stderr, "free(): invalid pointer %p!\n", mem);
 #ifdef _LIBC
             ((_IO_FILE *) stderr)->_flags2 |= old_flags2;
             _IO_funlockfile (stderr);
 #endif
           }
         if (check_action & 2)
           abort ();
         return;
       }

     check_inuse_chunk(av, p);

     /*
       If eligible, place chunk on a fastbin so it can be found
       and used quickly in malloc.
     */

     if ((unsigned long)(size) <= (unsigned long)(av->max_fast)            ---- 2-1

 #if TRIM_FASTBINS
         /*
            If TRIM_FASTBINS set, don't place chunks
            bordering top into fastbins
         */
         && (chunk_at_offset(p, size) != av->top)
 #endif
         ) {

       set_fastchunks(av);
       fb = &(av->fastbins[fastbin_index(size)]);
       p->fd = *fb;
       *fb = p;
     }

     /*
        Consolidate other non-mmapped chunks as they arrive.
     */

     else if (!chunk_is_mmapped(p)) {
       nextchunk = chunk_at_offset(p, size);
       nextsize = chunksize(nextchunk);
       assert(nextsize > 0);

       /* consolidate backward */
       if (!prev_inuse(p)) {                                         ---- 2-2
         prevsize = p->prev_size;
         size += prevsize;
         p = chunk_at_offset(p, -((long) prevsize));
         unlink(p, bck, fwd);
       }

       if (nextchunk != av->top) {                                    ---- 2-3
         /* get and clear inuse bit */
         nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

         /* consolidate forward */
         if (!nextinuse) {                                           ---- 2-4
           unlink(nextchunk, bck, fwd);
           size += nextsize;
         } else
           clear_inuse_bit_at_offset(nextchunk, 0);

         /*
           Place the chunk in unsorted chunk list. Chunks are
           not placed into regular bins until after they have
           been given one chance to be used in malloc.
         */

         bck = unsorted_chunks(av);                                   ---- 2-5
         fwd = bck->fd;
         p->bk = bck;
         p->fd = fwd;
         bck->fd = p;
         fwd->bk = p;

         set_head(p, size | PREV_INUSE);
         set_foot(p, size);

         check_free_chunk(av, p);
       }

       /*
          If the chunk borders the current high end of memory,
          consolidate into top
       */

       else {                                                      ---- 2-6
         size += nextsize;
         set_head(p, size | PREV_INUSE);
         av->top = p;
         check_chunk(av, p);
       }

       /*
         If freeing a large space, consolidate possibly-surrounding
         chunks. Then, if the total unused topmost memory exceeds trim
         threshold, ask malloc_trim to reduce top.

         Unless max_fast is 0, we don't know if there are fastbins
         bordering top, so we cannot tell for sure whether threshold
         has been reached unless fastbins are consolidated. But we
         don't want to consolidate on each free. As a compromise,
         consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
         is reached.
       */

       if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {     ---- 2-7
         if (have_fastchunks(av))
           malloc_consolidate(av);                                    ---- 2-8

         if (av == &main_arena) {                                     ---- 2-9
 #ifndef MORECORE_CANNOT_TRIM
           if ((unsigned long)(chunksize(av->top)) >=
               (unsigned long)(mp_.trim_threshold))
             sYSTRIm(mp_.top_pad, av);
 #endif
         } else {                                                   ---- 2-10
           /* Always try heap_trim(), even if the top chunk is not
              large, because the corresponding heap might go away. */
           heap_info *heap = heap_for_ptr(top(av));

           assert(heap->ar_ptr == av);
           heap_trim(heap, mp_.top_pad);
         }
       }

     }
     /*
       If the chunk was allocated via mmap, release via munmap(). Note
       that if HAVE_MMAP is false but chunk_is_mmapped is true, then
       user must have overwritten memory. There's nothing we can do to
       catch this error unless MALLOC_DEBUG is set, in which case
       check_inuse_chunk (above) will have triggered error.
     */

     else {                                                        ---- 2-11
 #if HAVE_MMAP
       int ret;
       INTERNAL_SIZE_T offset = p->prev_size;
       mp_.n_mmaps--;
       mp_.mmapped_mem -= (size + offset);
       ret = munmap((char*)p - offset, size + offset);
       /* munmap returns non-zero on failure */
       assert(ret == 0);
 #endif
     }
   }
 }
mmapped chunkの解放
まずchunkがmmap領域かどうかをチェックします。mmap領域である(IS_MMAPPEDがオン)場合、munmap_chunk()を呼び出して領域の解放を行います。
munmap_chunk()からリターンした後、そのままpublic_fREe()からもリターンし解放処理は終了です。munmap_chunk()の内容については別章「6. mmapped chunkの確保、解放」の所で説明します。
arena管理部の算出
_int_free()を呼び出す前に、まずarenaの管理部を求めます。これは、arena_for_chunk(ptr)を使います。
#define arena_for_chunk(ptr) \
(chunk_non_main_arena(ptr) ? heap_for_ptr(ptr)->ar_ptr : &main_arena)

NON_MAIN_ARENAオフの場合、単にmain_arenaのアドレスを返します。main_arena以外の場合、下記の様に算出されます。

#define heap_for_ptr(ptr) \
((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1)))

heap_infoはmmapで確保したarenaの管理情報を持つ構造体で、ここからarenaのポインタを辿る事が出来ます。heap_infoの先頭アドレスはHEAP_MAX_SIZEでアラインメントされており、所属するchunkのアドレスから求められる様になっています。mmapで確保したarenaについての詳細は「7 main_arena以外のarenaのメモリ確保、解放の流れ」で述べます。求めたarenaはロックします。
ソース上の変数avは求めたarenaのポインタ(malloc_state構造体のポインタ)、変数pは解放対象のchunkのポインタになります。

fastbinsへの登録
解放chunkのサイズがmax_fast以下の場合はfastbinsに登録します。(ソースリスト 2-1参照)
fastbinsへの登録は、該当のサイズのfastbinsリストの先頭のchunkアドレスを、登録するchunkのfdに設定し、登録するchunkのアドレスを、リストヘッダに設定するだけです。
またこの際、fastbinsにchunkがある事を示すフラグをmax_fastに設定しています。これはset_fastchunks()を使用しmax_fastのFASTCHUNKS_BITのビットをオフにする事により行います。
unsorted_chunksへの登録
chunkのサイズがmax_fastより大きい場合はbinsに直接登録するのではなく、一旦unsorted_chunksに登録します。これはbinsの2番目のリストヘッダです。
unsorted_chunksに登録されたchunkは以前述べました様にchunk確保処理の延長でサイズ毎のbinsに再登録される時までここに保存されます。

登録の為には次の手順を踏みます。
IS_MMAPPEDがオフの場合、次の様に処理を行います。

直前のchunkが未使用の場合、直前のchunkをリストから外し結合(ソースリスト 2-2参照)
直後のchunkがav->topでない時(ソースリスト 2-3参照)
・直後のchunkが未使用ならば、リストから外し結合(ソースリスト 2-4参照)
・直後のchunkが使用中ならば、直後のchunkのPREV_INUSEをオフ
・解放chunkをunsorted_chunksに登録、ヘッダーの更新(ソースリスト 2-5参照)
直後のchunkがav->top時(ソースリスト 2-6参照)
・topのchunkと結合し、av->topをpで更新
ここで解放サイズがFASTBIN_CONSOLIDATION_THRESHOLD(64KB)以上ならば、ヒープのトリミングを試みる(ソースリスト 2-7参照)
・まずmalloc_consolidate(av)をコールしfastbinsのchunkを削除(ソースリスト 2-8参照)
・そしてarenaがmain_arenaでav->top>=mp_.trim_thresholdならば、sYSTRIm()をコールし領域を縮小。(ソースリスト 2-9参照)
・arenaがmain_arenaでない場合はheap_trim()をコール

heap_trim()については「7. main_arena以外のarenaのメモリ確保、解放の流れ」で述べます。
_int_free()のコードの最後にchunkのIS_MMAPPEDがオンの場合、munmap()による解放、という処理があります。_int_free()はライブラリ内の幾つかの箇所よりコールされていますが、public_fREe()からコールする場合には上述の様に先にmmapのchunkの場合の処理を済ませているのでこの処理は通らない筈です。(ソースリスト 2-11参照)
public_fREe()に戻った後arenaのロックを解除しコール側に戻ります。

sYSTRIm()についてここで少し説明します。まずトリミングするサイズを求めます。

((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz

式の中のオペランドは下記の内容を持ちます。

  • top_size:av->top のサイズ
  • pad:mp_.top_pad(128KB)
  • MINSIZE:chunk の最小サイズ(16)
  • pagesz:mp_.pagesize(4KB)

求めたサイズが>0ならば、sbrk()をコールしサイズ分ヒープ領域を縮小します。そして残った領域を新たにav->topとして設定します。つまりヒープの先頭に131072+16+4096=135184byteより大きな空きがある場合に、その差分をページサイズの倍数に換算して縮小します。135184byte丁度の場合は縮小されません。
以上でchunkの解放処理についての説明は終わりです。

ページトップ

6. mmapped chunk の確保、解放

ここまでchunkの確保、解放の流れについて見てきましたが、mmapped chunkにはメモリプールから切り出すchunkとは少し異なる点があります。
mmapped chunkも通常のchunkと同様にヘッダ部とユーザ領域から構成されますが、mmapped chunkは常に単独で処理され、管理部にチェーンされる事もありません。free()が呼ばれた時点で解放(アンマップ)されます。その為prev_sizeは別の使われ方がされています。
その辺りの違いをここで述べておきます。

mmapped chunkの確保
4. mallocライブラリのメモリ確保の流れ」で説明しました様に、要求サイズのchunkがメモリプールから切り出せない場合、sYSMALLOc()を呼び出してヒープの拡張を行おうとします。その前に要求サイズがmp_.mmap_threshold以上のものについてはmmap領域として確保します(もう一つmp_.n_mmaps < mp_.n_mmaps_maxという条件もありますが、これはまず偽になる事はありません)。
領域のサイズは次の式で算出します。
(nb + SIZE_SZ + MALLOC_ALIGN_MASK + pagemask) & ~pagemask

式の中のオペランドは下記の内容を持ちます。

  • SIZE_SZ:chunkのサイズ格納領域のサイズ(4)
  • MALLOC_ALIGN_MASK:chunkサイズを8の倍数にアラインメントするため用(7)
  • pagemask:mp_.pagesize - 1

上記の様にページサイズで丸められたサイズでmmap()により領域を確保します。確保した領域は先頭アドレスが8の倍数になっていないかもしれない事を考慮し、アラインメントしてchunkの先頭とします。
ヘッダ情報には次の様に設定します。領域の先頭アドレスとアラインメントしたアドレスとの差をアライン.メントサイズとします。

  • prev_sizeメンバ:アラインメントサイズ
  • sizeメンバ:確保した領域サイズ - アラインメントサイズ

そしてmp_のn_mmapsのカウントアップ、mmapped_memにサイズの加算を行い、ユーザ使用領域のアドレスでsYSMALLOc()からリターンします。

mmapped chunkの解放
こちらも「5. freeライブラリのメモリ解放の流れ」で説明しました様に、解放処理はmunmap_chunk()を呼び出す事により行います。munmap_chunk()では次の処理が行われます。
mp_のn_mmapsのカウントダウン、mmapped_memから領域サイズの減算を行います。この時減算するサイズはsizeメンバ + prev_sizeメンバになります。
次の様にmunmap()が呼ばれ領域が解放されます。
ret = munmap((char *)p - p->prev_size, size + p->prev_size);

アラインメントした分を考慮し、chunkの先頭ポインタからprev_size分前のポインタを求めて渡しています。
munmap_chunk()の処理はこれで終了です。
参考の為、mmapped chunkのイメージを示します。

以上でmmapped chunkの確保、解放処理についての説明は終わりです。

ページトップ

7. main_arena 以外の arena のメモリ確保、解放の流れ

これまではarenaがmain_arenaである場合の処理について解説してまいりました。本章では、arenaがmmapで確保されている場合についてmain_arenaと異なる部分の処理を説明します。
sYSMALLOc()、heap_trim()、grow_heap()のソースリストもありますので参照して下さい。

sYSMALLOc()のソースリスト

 ...
   /* Record incoming configuration of top */
   old_top  = av->top;
   old_size = chunksize(old_top);
   old_end  = (char*)(chunk_at_offset(old_top, old_size));
   brk = snd_brk = (char*)(MORECORE_FAILURE);
   (中略)
   if (av != &main_arena) {
     heap_info *old_heap, *heap;
     size_t old_heap_size;
     /* First try to extend the current heap. */
     old_heap = heap_for_ptr(old_top);
     old_heap_size = old_heap->size;
     if (grow_heap(old_heap, MINSIZE + nb - old_size) == 0) {                              ---- 3-1
       av->system_mem += old_heap->size - old_heap_size;
       arena_mem += old_heap->size - old_heap_size;
 #if 0
       if(mmapped_mem + arena_mem + sbrked_mem > max_total_mem)
         max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
 #endif
       set_head(old_top, (((char *)old_heap + old_heap->size) - (char *)old_top)
                | PREV_INUSE);
     }
     else if ((heap = new_heap(nb + (MINSIZE + sizeof(*heap)), mp_.top_pad))) {            ---- 3-2
       /* Use a newly allocated heap.  */
       heap->ar_ptr = av;
       heap->prev = old_heap;
       av->system_mem += heap->size;
       arena_mem += heap->size;
 #if 0
       if((unsigned long)(mmapped_mem + arena_mem + sbrked_mem) > max_total_mem)
         max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
 #endif
       /* Set up the new top.  */
       top(av) = chunk_at_offset(heap, sizeof(*heap));
       set_head(top(av), (heap->size - sizeof(*heap)) | PREV_INUSE);
       /* Setup fencepost and free the old top chunk. */
       /* The fencepost takes at least MINSIZE bytes, because it might
          become the top chunk again later.  Note that a footer is set
          up, too, although the chunk is marked in use. */
       old_size -= MINSIZE;
       set_head(chunk_at_offset(old_top, old_size + 2*SIZE_SZ), 0|PREV_INUSE);             ---- 3-3
       if (old_size >= MINSIZE) {
         set_head(chunk_at_offset(old_top, old_size), (2*SIZE_SZ)|PREV_INUSE);
         set_foot(chunk_at_offset(old_top, old_size), (2*SIZE_SZ));
         set_head(old_top, old_size|PREV_INUSE|NON_MAIN_ARENA);
         _int_free(av, chunk2mem(old_top));
       } else {
         set_head(old_top, (old_size + 2*SIZE_SZ)|PREV_INUSE);
         set_foot(old_top, (old_size + 2*SIZE_SZ));
       }
     }
   } else { /* av == main_arena */
...

heap_trim()のソースリスト

 /* Delete a heap. */
 #define delete_heap(heap) munmap((char*)(heap), HEAP_MAX_SIZE)
 static int
 internal_function
 #if __STD_C
 heap_trim(heap_info *heap, size_t pad)
 #else
 heap_trim(heap, pad) heap_info *heap; size_t pad;
 #endif
 {
   mstate ar_ptr = heap->ar_ptr;
   unsigned long pagesz = mp_.pagesize;
   mchunkptr top_chunk = top(ar_ptr), p, bck, fwd;
   heap_info *prev_heap;
   long new_size, top_size, extra;
   /* Can this heap go away completely? */
   while(top_chunk == chunk_at_offset(heap, sizeof(*heap))) {                               ---- 4-1
     prev_heap = heap->prev;
     p = chunk_at_offset(prev_heap, prev_heap->size - (MINSIZE-2*SIZE_SZ));
     assert(p->size == (0|PREV_INUSE)); /* must be fencepost */
     p = prev_chunk(p);
     new_size = chunksize(p) + (MINSIZE-2*SIZE_SZ);
     assert(new_size>0 && new_size<(long)(2*MINSIZE));
     if(!prev_inuse(p))
       new_size += p->prev_size;
     assert(new_size>0 && new_size<HEAP_MAX_SIZE);
     if(new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz)              ---- 4-2
       break;
     ar_ptr->system_mem -= heap->size;
     arena_mem -= heap->size;
     delete_heap(heap);                                                                     ---- 4-3
     heap = prev_heap;
     if(!prev_inuse(p)) { /* consolidate backward */
       p = prev_chunk(p);
       unlink(p, bck, fwd);
     }
     assert(((unsigned long)((char*)p + new_size) & (pagesz-1)) == 0);
     assert( ((char*)p + new_size) == ((char*)heap + heap->size) );
     top(ar_ptr) = top_chunk = p;
     set_head(top_chunk, new_size | PREV_INUSE);
     /*check_chunk(ar_ptr, top_chunk);*/
   }
   top_size = chunksize(top_chunk);
   extra = ((top_size - pad - MINSIZE + (pagesz-1))/pagesz - 1) * pagesz;                   ---- 4-4
   if(extra < (long)pagesz)
     return 0;
   /* Try to shrink. */
   if(grow_heap(heap, -extra) != 0)                                                         ---- 4-5
     return 0;
   ar_ptr->system_mem -= extra;
   arena_mem -= extra;
   /* Success. Adjust top accordingly. */
   set_head(top_chunk, (top_size - extra) | PREV_INUSE);
   /*check_chunk(ar_ptr, top_chunk);*/
   return 1;
 }

grow_heap()のソースリスト

 static int
 #if __STD_C
 grow_heap(heap_info *h, long diff)
 #else
 grow_heap(h, diff) heap_info *h; long diff;
 #endif
 {
   size_t page_mask = malloc_getpagesize - 1;
   long new_size;

   if(diff >= 0) {
     diff = (diff + page_mask) & ~page_mask;                                                ---- 5-1
     new_size = (long)h->size + diff;
     if(new_size > HEAP_MAX_SIZE)
       return -1;
     if(mprotect((char *)h + h->size, diff, PROT_READ|PROT_WRITE) != 0)                     ---- 5-2
       return -2;
   } else {
     new_size = (long)h->size + diff;
     if(new_size < (long)sizeof(*h))
       return -1;
     /* Try to re-map the extra heap space freshly to save memory, and
        make it inaccessible. */
     if((char *)MMAP((char *)h + new_size, -diff, PROT_NONE,                                ---- 5-3
                     MAP_PRIVATE|MAP_FIXED) == (char *) MAP_FAILED)
       return -2;
     /*fprintf(stderr, "shrink %p %08lx\n", h, new_size);*/
   }
   h->size = new_size;
   return 0;
 }
管理部
以前述べました様にmain_arena以外のarenaはmmap()により確保されています(以後mmapped arenaと呼ぶ)。そしてmmapped arenaは一つ以上のmmap領域から構成されます。再度全体図を示します。

mmapped arenaの全体の管理情報は_heap_info構造体で定義されています。コード上はこのtypedefであるheap_infoが使用されています。下記が_heap_info構造体の定義になります。

【 _heap_info構造体の定義 】malloc/arena.c:

typedef struct _heap_info {
  mstate ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t pad;    /* Make sure the following data is properly aligned. */
} heap_info;

【 表3 heap_infoの主要なメンバの概要 】

メンバ 説明
mstate ar_ptr 本arenaの管理部ポインタ。
_heap_info *prev arenaが複数のmmap領域に跨る場合のネストポインタ。
size_t size mmap領域の内の有効なサイズ。
size_t pad 本構造体のアラインメントの為のパディング領域。
  • ar_ptr:本arenaのmalloc_state構造体情報のポインタです。
  • prev:arenaからchunkを切り出せない場合に新たにmmap領域を生成します。この時、一つ前のmmap領域のアドレスを設定します。
  • size:mmap領域としては常にサイズ1MBで確保しますが、その内の有効サイズを格納します。
mmapped arena領域の確保
arenaはarena_get2() -> _int_new_arena() -> new_heap()の流れでnew_heap()で確保されます。new_heap()は下記のパラメータでコールされます。
h = new_heap(size + (sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT),
             mp_.top_pad);

new_heap()内ではarenaのサイズは次の式と同等の内容で算出されます。

size + (sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT) + mp_.top_pad

式の中のオペランドは下記の内容を意味します。

  • size:要求サイズ
  • sizeof(*h):heap_info構造体サイズ
  • sizeof(*a):malloc_state構造体サイズ
  • MALLOC_ALIGNMENT:8

更にnew_heap()内でページサイズに切り上げられます。但し上記式で求められるサイズはメモリプールとして利用するサイズで、mmap領域のサイズとしては常にHEAP_MAX_SIZEバイトで確保されます。
mmap()をコールする際にPROT_NONEで確保し、その後、mprotect()で上記で算出したサイズ分をPROT_READ|PROT_WRITEに設定します。またその領域の先頭はHEAP_MAX_SIZEの倍数のアドレス位置になる様に工夫して確保します。これは、このarenaに属するchunkのポインタからarenaの先頭を次の様に簡単に求める事ができる様にする為です。

#define heap_for_ptr(ptr) \
 ((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1)))

算出サイズがHEAP_MAX_SIZEを超える場合は0でリターン(確保できなかった事を示す)します。領域が確保できた場合は、算出したサイズをheap_info.sizeに設定します。確保したarenaの管理部(malloc_state)は、malloc_init_state()をコールし初期化します。

メモリ確保
chunkの確保処理に関してはmain_arenaと変わりません。但し、chunkを確保できない場合の領域の拡張処理は少し異なります。これは、やはりsYSMALLOc()の中で行われます。要求サイズnbがmp_.mmap_threshold以上の場合は同じです。mp_.mmap_threshold未満の場合にはarenaを拡張するのですが、これは引数に拡張サイズを指定してgrow_heap()をコールする事で行います。(ソースリスト 3-1参照)
if (grow_heap(old_heap, MINSIZE + nb - old_size) == 0) {

拡張サイズはこの内、次の部分になります。

MINSIZE + nb - old_size

式の中のオペランドは下記の内容を持ちます。

  • MINSIZE:chunkの最小サイズ(16)
  • nb:要求サイズ
  • old_size:av->topのサイズ

この値が負になる事はありません。av->topのサイズの方が大きい場合は、chunkが切り出せる筈なのでこの関数は呼ばれないからです。

grow_heap()の処理について簡単に説明します。grow_heap()は領域の拡張、縮小両方の処理を行う機能を持っておりますが、ここでは拡張の処理について解説します。
grow_heap()では渡されたサイズをページサイズ単位で切り上げて拡張サイズとします。(ソースリスト 5-1参照)そして指定されたサイズ分の領域のアクセスモードをmprotect()でPROT_READ|PROT_WRITEに変更します。(ソースリスト 5-2参照)但し、拡張サイズと元々のサイズ(heap_info.size)の合計がHEAP_MAX_SIZEを超えている場合はエラーリターンします。mmapped arenaはHEAP_MAX_SIZEを超えては拡張しない事になります。
ここでgrow_heap()からエラーリターンした場合は、別途mmap領域を確保し、mmapped arenaにチェーンします。(ソースリスト 3-2参照)そしてmmapped arena の top領域の最後に拡張領域なしの印を設定します。これはtopの最後のMINSIZEバイトを利用して、prev_siz とsizeメンバだけのchunkを設定する事で行います。これをフェンスポストと呼んでいます(MINSIZE以外に使用可能なスペースがあればchunkとして切り出して登録します)。(ソースリスト 3-3参照)
MINSIZEバイト確保するのは、今度topとして利用する為に最小のchunkサイズを取っている為です。この処理は拡張前の領域がmmapped arenaでなく拡張mmap領域である場合も同様です。拡張mmap領域は次のパラメータでnew_heap()をコールし生成します。(ソースリスト 3-2参照)

else if ((heap = new_heap(nb + (MINSIZE + sizeof(*heap)), mp_.top_pad))) {

サイズはnew_heap()内で次の式と同等の内容で算出されます。

nb + (MINSIZE + sizeof(*heap)) + mp_.top_pad

式の中のオペランドは下記の内容を持ちます。

  • MINSIZE:chunkの最小サイズ(16)
  • sizeof(*heap):heap_info構造体サイズ

上述の様にこの値が更にページサイズに切り上げられます。拡張mmap領域はmalloc_state情報を持ちません。heap_info情報の直後からメモリプールが始まります。

拡張が終わるとav->topのサイズを設定し、後はmain_arenaの場合と同様です。chunkを切り出してsYSMALLOc()からリターンします。

メモリ解放
こちらも主な処理の流れはmain_arenaと変わりません。以前述べました様に領域のトリミングを行う所が異なります。これにはheap_trim()を使用します。上述の様にmmaped arenaはmmap領域がネストして拡張されている場合があります。その為ネストを辿って順次空きのmmap領域を解放していきます。
まず、mmap領域全体が解放できるかどうかチェックします。これはtopを求め(top(ar_ptr))、mmap領域のメモリプールアドレス(mmap領域をheap_info構造体サイズ分ずらした位置)の先頭と等しければ、そのmmapは全て空きと見なします。(ソースリスト 4-1参照)
次に、(heap_info.prevから求められる)一つ前のmmap領域をチェックします。一つ前の領域が使われる様になった時、そこに空きがないとすぐまた拡張する羽目になるかも知れないからです。一つ前の未使用領域が規定のサイズの空きがあるか次の条件でチェックします。(ソースリスト 4-2参照)
new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz

式の中のオペランドは下記の内容を持ちます。

  • new_size:空きchunk領域サイズ
  • prev_heap->size:一つ前のmmap領域のheap_info.size
  • pad:mp_.top_pad(128KB)
  • pagesz:mp_.pagesz(4KB)

上記条件を満たさない(つまり十分な空き領域がある)場合は、最後のmmap領域をmunmap()により解放します(およそ128KB+1ページ以上という事になります)。
(ソースリスト 4-3 参照)
そして一つ前のmmap領域だったものを最後の領域として繰り返し処理していきます。解放できた場合は、そのサイズ分av->system_memを減算します。そしてav->topに新しく最後になった領域のtopを設定します。
最後のmmap領域のtopアドレスとメモリプールの最後が等しくないか、一つ前の領域が上記条件を満たす場合は、mmap領域全体の解放処理は終了し最後の領域の有効使用領域の減少を行います。減らすサイズは次の様に求めます。(ソースリスト 4-4参照)

extra = ((top_size - pad - MINSIZE + (pagesz-1))/pagesz - 1) * pagesz;

式の中のオペランドは下記の内容を持ちます。

  • top_size:av->top のサイズ
  • pad:mp_.top_pad(128KB)
  • MINSIZE:chunkの最小サイズ(16)
  • pagesz:mp_.pagesz(4KB)

grow_heap()にサイズのマイナス値を渡して領域を縮小します。(ソースリスト 4-5参照)
grow_heap()では指定されたサイズの領域をmmap()でPROT_NONEに設定してアクセス不可領域とします。(ソースリスト 5-3参照)
縮小した分を有効サイズから差し引いてheap_info.sizeに設定します。領域が解放できた場合は、そのサイズ分av->system_memを減算しav->top に新しく最後になった領域のtopを設定します。

以上でmain_arena以外のarenaでのメモリ確保、解放の流れについての説明は終わりです。今回までmalloc()のメモリ管理方法とその確保、解放に関するおおよその流れについて説明してきました。

ページトップ

8. mallocライブラリとデバッグ

これまでにmallocライブラリの処理内容の詳細について述べてきました。ここでは、mallocライブラリを使用して問題が発生した場合の簡単な調査方法について説明していきます。

問題はどのような状況で起こるでしょう?下記の様なケースが考えられます。

  • 1. 確保した領域サイズ以上のサイズで使用
  • 2. 二重解放
  • 3. 解放したメモリの使用
  • 4. メモリの解放漏れ
  • 5. 確保したメモリの二重使用

これらの問題を検出する為の色々なツールも存在しますが、mallocライブラリ側でも簡単なチェック機能が備えられています。これは予めライブラリ内に組み込まれている為、簡単に使用することができ、アプリケーション側の修正も必要ありません。ただ簡単な仕組みの為、余り詳細なチェックは行えません。上記の(1)と(2)には対応が可能です。以下、この機能の仕組みについて説明します。
これは環境変数MALLOC_CHECK_に特定の値を設定する事により、ライブラリ側にデバッグ機能使用の通知を行いチェック機能を働かせるものです。この機能はmallocのmanにも書かれています。ここではライブラリでの内部的な処理についても述べて行きます。

MALLOC_CHECK_の値はpublic_mALLOc()コール時の最初の処理でcheck_actionという静的変数に設定されます。これは、public_mALLOc()コール時の最初の処理で呼ばれる関数ポインタhook()に設定されている関数malloc_hook_ini()で処理されます。ライブラリ内ではこのcheck_actionのビット0、1をチェックする事で処理を行います。ビットの値が1の時の意味は右記のとおりとなります。

この為MALLOC_CHECK_の設定値は0、1、2、3が有効で、それぞれ次の意味を持つ事になります。

  • 0:処理なし
  • 1:メッセージ表示
  • 2:abort() call
  • 3:メッセージ表示後、abort() call

メモリに関する問題は、発生時には発覚せず比較的処理が進んでから検出される事が往々にして見られます。abort()の呼び出しは早い段階での問題検出に役立ちます。

check_actionは初期値としてはDEFAULT_CHECK_ACTIONが設定されています。DEFAULT_CHECK_ACTIONの値は1に定義されています。この為、環境変数MALLOC_CHECK_が定義されていない場合でも最低限のチェックは行われています。MALLOC_CHECK_が定義されていない場合には_int_free()関数でだけcheck_actionのチェックが行われます。チェックの内容は下記で述べますが、不正があった場合check_actionのビット0だけがオンの為エラーメッセージが表示されるだけです。

MALLOC_CHECK_が定義されている場合、ライブラリの初期処理段階で、不正な操作をチェックする為の準備関数が呼ばれます。
public_mALLOc() -> malloc_hook_ini() -> ptmalloc_init()という流れで呼ばれる関数ptmalloc_init()でMALLOC_CHECK_の値がcheck_actionに設定されます。またその延長で呼ばれる__malloc_check_init()関数中でメモリチェックの為のフック関数を設定します。

__malloc_hook = malloc_check;
__free_hook = free_check;
__realloc_hook = realloc_check;
__memalign_hook = memalign_check;

これらの__xxx_hook()という関数は各フック関数に応じたmallocライブラリの入り口で呼ばれます。__malloc_hook()の場合はpublic_mALLOc()で呼ばれます。
MALLOC_CHECK_が定義されていない場合はこれらの関数ポインタにはNULLが設定されている為、なにも行われません。ここではmalloc()、free()でのチェック処理について述べます。
malloc()をコールする場合public_mALLOc()が呼ばれることは以前述べました。public_mALLOc()では処理の先頭で__malloc_hook()をコールします。通常の流れと違い、メモリ確保の処理を行う_int_malloc()は__malloc_hook()の延長で呼ばれ__malloc_hook()から戻るとpublic_mALLOc()からリターンします。__malloc_hook()関数ポインタにはmalloc_check()が設定されている為、これがコールされます。
malloc_check()では、まずtop_check()によりarenaのtopの値の妥当性をチェックします。これは次の様になります。

if((char*)t + chunksize(t) == mp_.sbrk_base + main_arena.system_mem ||
t == initial_top(&main_arena)) return 0;

top_check()が異常な場合、check_actionの値をチェックし、次の様に処理されます。

  • bit 0 ON:fprintf(stderr, "malloc: top chunk is corrupt\n");を実行。
  • bit 1 ON:abort();をコール。

正常な場合_int_malloc()が_int_malloc(&main_arena, sz+1)の様に呼ばれます。_int_malloc()での処理内容は通常と変わりませんがサイズが要求された値+1となります。これはチェックを行う為の領域として確保されています。_int_malloc()から戻った後、mem2mem_check()が呼ばれます。これはメモリチェックをする為の準備を行う関数です。ここでの設定が、free()をコールした際にチェックされます。mem2mem_check()では該当のchunkに対してマジックバイトを設定します。chunkの要求サイズの次のバイトと、次のchunkのprev_sizeの最後のバイトです。
マジックバイトはMAGICBYTE()で算出します。定義は次のものになります。

#define MAGICBYTE(p) ( ( ((size_t)p >> 3) ^ ((size_t)p >> 11)) & 0xFF )

pはchunkのアドレスになります。これでmalloc()での準備は終わりです。
次にfree()の説明をします。こちらも以前述べました様にpublic_fREe()が呼ばれます。public_fREe()では処理の先頭で__free_hook()をコールします。__free_hook()は即ちfree_check()です。malloc()と同様にここでも__free_hook()から戻るとpublic_fREe()からリターンします。
free_check()ではmem2chunk_check()をコールし対象のメモリをチェックします。mem2chunk_check()の結果がエラーの場合check_actionの値をチェックします。次の処理が行われabort()がコールされなければそのままリターンします。

  • bit 0 ON:fprintf(stderr, "free(): invalid pointer %p!\n", mem);を実行。
  • bit 1 ON:abort();をコール。

正常の場合、_int_free()関数がコールされます。_int_free()では関数の最初で、解放で指定されたアドレスと該当のchunkのヘッダ部にあるsizeメンバがチェックされます。不正な場合、check_actionの値がチェックされ次の処理が行われます。やはりabort()がコールされなければそのままリターンします。

  • bit 0 ON:fprintf (stderr, "free(): invalid pointer %p!\n", mem);を実行。
  • bit 1 ON:abort();をコール。

mem2chunk_check()では次の様なチェックが行われます。

  • メモリのアラインメント(8バイト境界になっているか)。
  • chunkの管理情報のsizeの値が正しいか。
  • アドレスチェック(アドレスがヒープ範囲内にあるか)。
  • マジックバイトのチェック(マジックバイト値がメモリから計算した値と合っているか)。チェック後マジックバイト値と0xffで排他的論理輪を取って値を反転します。

これにより二重フリーや、メモリ破壊がある程度チェックされます。
それでは、MALLOC_CHECK_を使った簡単なテストをしてみましょう。合わせてchunkのヘッダ部の変化も少し見てみましょう。
下記ではmalloc()は必ず成功し、プロセス起動の初期段階ではchunkが連続して取られると言う推定の下に行っています。

【 malloc()のデバッグ例 】

$ cat maltest.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MEMSIZE 40
#define CHUNKHDSZ 8
 
int dmp(void *mem, int i);
 
int main(int argc, char *argv[])
{
        char *c1, *c2, *c3, *c4;
 
        printf("==> Start %s\n", argv[0]);
        c1 = malloc(MEMSIZE);
        c2 = malloc(MEMSIZE);
        c3 = malloc(MEMSIZE);
        printf("c1=%p, c2=%p, c3=%p\n", c1, c2, c3);
 
        dmp(c2 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        free(c1);
        free(c1);                                                      -> 二重フリー
 
        dmp(c2 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        memset(c2 + MEMSIZE, '\0', 1);                                 ->メモリ破壊
        dmp(c2 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        free(c2);
        memset(c2 + MEMSIZE, '\0', 8);                                 ->メモリ破壊(次のchunkの管理部)
        dmp(c2 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        free(c3);
        dmp(c3 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        memset(c3 + MEMSIZE, '\0', 8);                                 ->メモリ破壊(top chunkの管理部)
        dmp(c3 - CHUNKHDSZ, MEMSIZE + CHUNKHDSZ * 2);
        c4 = malloc(MEMSIZE);
        free(c4);
 
        printf("==> Finished %s\n", argv[0]);
        exit(0);
}
 
int dmp(void *mem, int i)
{
        int j, max;
        int *memi = (int *)mem;
 
        printf("start memory dump %p *****\n", mem);
        max = i / 16 + (i % 16 ? 1 : 0);
        for (j = 0; j < max; j++) {
                printf("%p : %08x %08x %08x %08x\n",
                        memi, *(memi), *(memi+1), *(memi+2), *(memi+3));
                memi += 4;
        }
        printf("end memory dump *****\n");
        return max*16;
}
$ gcc -Wall -o maltest maltest.c
$ ./maltest
==> Start ./maltest
c1=0x804a008, c2=0x804a038, c3=0x804a068
start memory dump 0x804a030 *****
0x804a030 : 00000000 00000031 00000000 00000000 ->0x804a030がc2 chunkの先頭
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 00000000 00000031 00000000 00000000 ->0x804a060がc3 chunkの先頭
end memory dump *****
start memory dump 0x804a030 *****
0x804a030 : 00000000 00000031 00000000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 00000000 00000031 00000000 00000000
end memory dump *****
start memory dump 0x804a030 *****
0x804a030 : 00000000 00000031 00000000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 00000000 00000031 00000000 00000000
end memory dump *****
start memory dump 0x804a030 *****
0x804a030 : 00000000 00000031 0804a000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 00000000 00000000 00000000 00000000
end memory dump *****
free(): invalid pointer 0x804a068!              ->デフォルトの設定でのチェック
start memory dump 0x804a060 *****
0x804a060 : 00000000 00000000 00000000 00000000
0x804a070 : 00000000 00000000 00000000 00000000
0x804a080 : 00000000 00000000 00000000 00000000
0x804a090 : 00000000 00020f71 00000000 00000000
end memory dump *****
start memory dump 0x804a060 *****
0x804a060 : 00000000 00000000 00000000 00000000
0x804a070 : 00000000 00000000 00000000 00000000
0x804a080 : 00000000 00000000 00000000 00000000
0x804a090 : 00000000 00000000 00000000 00000000
end memory dump *****
==> Finished ./maltest
$ export MALLOC_CHECK_=1
$ ./maltest
==> Start ./maltest
malloc: using debugging hooks
c1=0x804a008, c2=0x804a038, c3=0x804a068
start memory dump 0x804a030 *****
0x804a030 : 03000094 00000031 00000000 00000000 ->c1のマジックバイト値(0x94)、オフセット(3)、size(0x31)
0x804a040 : 00000000 00000000 00000000 00000000    0x94 : (0x804a000 >> 3) ^ (0x804a000 >> 11) & 0xff
0x804a050 : 00000000 00000000 00000000 00000000    0x31 : (40 + 7 + 4) & ~7 + PREV_INUSE = 49
0x804a060 : 03000092 00000031 00000000 00000000
end memory dump *****
free(): invalid pointer 0x804a008!
start memory dump 0x804a030 *****
0x804a030 : 0300006b 00000031 00000000 00000000 -> c1 free()でマジックバイト値反転(0x94 ^= 0xff)
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 03000092 00000031 00000000 00000000
end memory dump *****
start memory dump 0x804a030 *****
0x804a030 : 0300006b 00000031 00000000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 03000000 00000031 00000000 00000000 ->c2のマジックバイト値をクリア
end memory dump *****
free(): invalid pointer 0x804a038!
start memory dump 0x804a030 *****
0x804a030 : 0300006b 00000031 00000000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 00000000 00000000 00000000 00000000 ->c3のヘッダ部クリア
end memory dump *****
free(): invalid pointer 0x804a068!
start memory dump 0x804a060 *****
0x804a060 : 00000000 00000000 00000000 00000000
0x804a070 : 00000000 00000000 00000000 00000000
0x804a080 : 00000000 00000000 00000000 00000000
0x804a090 : 03000098 00020f71 00000000 00000000
end memory dump *****
start memory dump 0x804a060 *****
0x804a060 : 00000000 00000000 00000000 00000000
0x804a070 : 00000000 00000000 00000000 00000000
0x804a080 : 00000000 00000000 00000000 00000000
0x804a090 : 00000000 00000000 00000000 00000000 ->top chunkのヘッダ部クリア
end memory dump *****
malloc: top chunk is corrupt
==> Finished ./maltest
$ export MALLOC_CHECK_=3
$ ./maltest
==> Start ./maltest
malloc: using debugging hooks
c1=0x804a008, c2=0x804a038, c3=0x804a068
start memory dump 0x804a030 *****
0x804a030 : 03000094 00000031 00000000 00000000
0x804a040 : 00000000 00000000 00000000 00000000
0x804a050 : 00000000 00000000 00000000 00000000
0x804a060 : 03000092 00000031 00000000 00000000
end memory dump *****
free(): invalid pointer 0x804a008!
Aborted
$

以上でmallocライブラリのデバッグの説明を終わります。
mallocライブラリのデバッグの為には、MALLOC_CHECK_以外にも色々なツールがありますので、試してみるのもよいでしょう。

まとめ

mallocライブラリの説明については今回が最後です。glibcはLinuxでプログラミングするには欠かせないものでありながら、man以外にその中身について説明した文書はほとんど見られません(最もこれはオープンソースの常ではありますが)。man自身もソースに追随して常に最新に保たれている訳ではありませんので、使用しているライブラリの動きについて調べたい場合はやはり直接ソースを読む必要も出て来ます。その様な場面で本資料がソースを読み解く手助けや問題解決の手助けになればと思います。皆さんご自身でも一度ライブラリのソースを読んで理解を深められてはどうでしょう。プログラムを組む上で何か得る所が有るのではないかと思います。

関連記事

Linux
2008年1月15日
ダンプ解析講座
Linux
2008年8月15日
hping3によるフィルタリングルールの検証
負荷分散
2007年9月1日
負荷分散型クラスタ解説 - UltraMonkey
お気軽にお問い合わせください

VA Linuxでは、「受託開発サービス」をご提供しております。
サービスに関する詳細は、「受託開発サービス」の説明ページをご覧ください。

お問い合わせフォームはこちら
ページトップ