mallocの動作を追いかける(prev_size編)

はじめに

malloc動画見てますか？＞挨拶

前回は比較的振る舞いがシンプルな、mallocが内部でmmapを呼ぶケースについて調べたが、今回はmalloc_chunk構造体と実際に使われるメモリ配置がちっとも対応していないことを見てみる。

• mallocの動作を追いかける(mmap編)
• mallocの動作を追いかける(prev_size編) ← イマココ
• mallocの動作を追いかける(main_arenaとsbrk編)
• mallocの動作を追いかける(fastbins編)
• mallocの動作を追いかける(マルチスレッド編)
• mallocの動作を追いかける(環境変数編)

chunkについて

繰り返しになるが、mallocはメモリをチャンク(chunk)という単位で管理する。これは「ヘッダ＋ユーザが使える領域」なのだが、メモリを効率利用するために、チャンクのヘッダが他の使用中メモリを指していたり、malloc_chunk構造体のメンバが有効な値を持つかどうかが文脈依存だったりしてややこしい。

とりあえずmalloc_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;
};

今回は小さいサイズのmallocを扱うため、fd_nextsizeやbk_nextsizeは使われない。また、mchunk_prev_sizeが有効なのは使われていないチャンク、つまりfreeされた後なので、常に有効な値を持つメンバはmchunk_sizeだけである。

small binについて

Glibc mallocでは、小さい領域はsmall binという方法で管理されている。詳しくはmallocの旅(glibc編)でも見ていただくとして、ここで重要なのは、

• 小さいサイズのチャンクは、チャンクサイズsizeと一つ前のチャンクのサイズprev_sizeで管理されている。
• しかし、一つ前のチャンクはprev_sizeのところまで使っている。
• prev_sizeが有効な値を持っているかどうかは、sizeの最下位1ビットが立っているかどうかで判定する

ということ。今回は、実際に

• malloc_chunk構造体の場所がメモリ境界と一致していないこと
• prev_sizeの場所までユーザが使っていること

を確認してみる。

実際に追いかける

プログラムから確認

まずはこんなソースを書いてみる。

test.cpp

#include <cstdio>
#include <cstdlib>
#include <algorithm>
const int N = 5;
char *buf[N];

typedef size_t INTERNAL_SIZE_T;
struct malloc_chunk {
  INTERNAL_SIZE_T mchunk_prev_size;
  INTERNAL_SIZE_T mchunk_size;
};

typedef struct malloc_chunk* mchunkptr;

void
show(char *buf){
  mchunkptr p = (mchunkptr)(buf-16);
  size_t prev_size = p->mchunk_prev_size;
  size_t size = p->mchunk_size;
  size_t chunk_size = (size>>2)<<2;
  printf("0x%lx->0x%lx (0x%lx):",p,p+chunk_size,chunk_size);
  if(size &1){
    printf("prev is used; prev_size = 0x%lX\n",prev_size);
  }else{
    printf("prev is not used: prev_size = 0x%lX\n",prev_size);
  }
}

void
show_all(void){
  for(int i=0;i<N;i++){
    show(buf[i]);
  }
}

int
main(void){
  size_t SIZE = 0x108;
  for(int i=0;i<N;i++){
    buf[i] = (char*)malloc(SIZE);
    std::fill(buf[i],buf[i]+SIZE,0xAA+0x11*i);
  }
  printf("----before free-----\n");
  show_all();
  free(buf[1]);
  printf("-----after free-----\n");
  show_all();
  buf[1] = (char*)malloc(SIZE*2);
  printf("-----alloc again-----\n");
  show_all();
  for(int i=0;i<N;i++){
    free(buf[i]);
  }
}

前回みたいに生でアドレスにアクセスしても良いのだが、雰囲気を出すためにmalloc_chunk構造体(の頭だけ)を定義し、mallocで受け取ったポインタから16バイトだけ戻った場所をmalloc_chunk*にキャストしてやることにする。さらにglibcっぽさを出すため、

typedef struct malloc_chunk* mchunkptr;

と、malloc_chunkへのポインタをmchunkptrにキャストしている。

このプログラムは順番に、

• 0x108(264)バイトの領域を5つ確保する。もらった領域をそれぞれ0xAAから0xEEで初期化する。
• 2番目の領域をfreeする
• 0x210(528)バイトを要求する

ということをやっている。それぞれのステップで、確保したポインタの16バイト前をmchunkptrだと思って、チャンクサイズや一つ前のチャンクサイズを表示している。

実行結果はこんな感じになる。

$ g++ test.cpp
$ ./a.out
----before free-----
0x602010->0x602120 (0x110):prev is used; prev_size = 0x0
0x602120->0x602230 (0x110):prev is used; prev_size = 0xAAAAAAAAAAAAAAAA
0x602230->0x602340 (0x110):prev is used; prev_size = 0xBBBBBBBBBBBBBBBB
0x602340->0x602450 (0x110):prev is used; prev_size = 0xCCCCCCCCCCCCCCCC
0x602450->0x602560 (0x110):prev is used; prev_size = 0xDDDDDDDDDDDDDDDD
-----after free-----
0x602010->0x602120 (0x110):prev is used; prev_size = 0x0
0x602120->0x602230 (0x110):prev is used; prev_size = 0xAAAAAAAAAAAAAAAA
0x602230->0x602340 (0x110):prev is not used: prev_size = 0x110
0x602340->0x602450 (0x110):prev is used; prev_size = 0xCCCCCCCCCCCCCCCC
0x602450->0x602560 (0x110):prev is used; prev_size = 0xDDDDDDDDDDDDDDDD
-----alloc again-----
0x602010->0x602120 (0x110):prev is used; prev_size = 0x0
0x602560->0x602780 (0x220):prev is used; prev_size = 0xEEEEEEEEEEEEEEEE
0x602230->0x602340 (0x110):prev is not used: prev_size = 0x110
0x602340->0x602450 (0x110):prev is used; prev_size = 0xCCCCCCCCCCCCCCCC
0x602450->0x602560 (0x110):prev is used; prev_size = 0xDDDDDDDDDDDDDDDD

まず、最初にmallocした直後の状態はこうなっている。

例えば、buf[0]のアドレスは0x602010である。その16バイト前がチャンクの先頭アドレスだが、いま有効なのはチャンクサイズだけであり、それはbuf[0] - 8のアドレスに入っている。その値は0x110(272)バイトであり、要求サイズより8バイトだけ大きい。ユーザはbuf[i]から0x108バイトが使えることが保証されている(赤い矢印)。また、チャンク的には、例えば最初のチャンクなら0x602000から0x110バイトだと認識されている(水色の矢印)が、見て分かる通りユーザがもらった領域と始点、終点ともに対応していない。これがmallocのわかりづらさの主要原因だと思う。

さて、buf[i] - 8にはそれぞれのチャンクのチャンクサイズが入っているが、実際の値は0x111である。しかし、チャンクサイズの下位3bitは別の意味を持つフラグなのであった。ここでは「前のチャンクが使用中であるか」のフラグがたっている(黄色い四角)。このフラグが立っている時にはbuf[i] - 16のprev_sizeは意味のある値が入っていない(ユーザが使っている)。実際にbuf[1]を管理するチャンクのprev_sizeには0xAAAAAAAAAAAAAAAAという値が入っていて、これはbuf[0]としてユーザが使っている。

さて、ここでbuf[1]をfreeしよう。freeした直後はこんな状態になっている。

buf[1]の指す領域はfreeされたのでもはや中身は保証されないが、buf[1]の指す場所は0x602120のままになっている。ここで、新たにbuf[2]に対応するチャンクのprev_sizeに、buf[1]に対応するチャンクサイズ0x110が書き込まれる(0x110)。さらにbuf[2]のチャンクサイズの最下位ビットがクリアされ、直前のチャンクが使われていない(prev_sizeが有効な値を持つ)ことが示される。

次に、先程freeしたbuf[1]に0x210(528)バイトのmalloc要求を出そう。先程空いた領域にはハマらないため、こんな感じになる。

mallocは新たに0x602560という場所を返す。チャンクサイズは0x220バイトである。prev_sizeメンバのある場所はbuf[4]が管理する領域にかぶっているから0xEEEEEEEEEEEEEEEEを表示している。

gdbで動作を追いかける

先程のプログラムで確かにチャンクサイズとユーザが使う領域が一致しておらず、かつprev_sizeは直前のチャンク使用時には意味のある値を持たず、直前のチャンクが未使用であればそのサイズが入ることがわかった。gdbでこれを追いかけても同じことがわかるだけなのだが、なんとなく実際にgdbで直接振る舞いを見た方がわかった気になるような人(＝俺)のため、一連の動作をgdbで追いかけてみる。

先程のプログラムを-gつきでコンパイルしてからgdbで開こう。

$ g++ -g test.cpp
$ gdb --tui -q ./a.out

繰り返しになるが、筆者はgdbのTUI推しである。まずはfreeの直前にブレークポイントをかけよう。

(gdb) break 45
Breakpoint 1 at 0x4008a6: file test.cpp, line 45.
(gdb) r
snip
Breakpoint 1, main () at test.cpp:45
(gdb) 

ここで、_int_freeにブレークポイントをかけて続行する。TUIモードを使っていれば「No Source Available」と言う表示が出るのでアセンブリを表示させよう。

(gdb) break _int_free
Breakpoint 2 at 0x2aaaab516550
(gdb) n

Breakpoint 2, 0x00002aaaab516550 in _int_free () from /lib64/libc.so.6
(gdb) layout asm

こんな表示になるはず。

さて、_int_freeのソースはこんな感じになっている。

static void
_int_free (mstate av, mchunkptr p, int have_lock)

つまり、第一引数がmalloc_stateへのポインタ(今回はmain_arenaになってるはず)、第二引数がfreeするためのチャンクのアドレスである。この第二引数を表示させてみる。これは%rsiに入っているはず。

(gdb) print/x $rsi
$1 = 0x602110

先程の図にあった通り、buf[1]を管理するチャンクの先頭アドレスである0x602110が入っている。しかし、先程見たようにこのアドレスそのものはbuf[0]が使っている。中身を表示させてみよう。

(gdb) x/xw 0x602110
0x602110:       0xaaaaaaaa

buf[0]が自分の領域を0xAAで初期化しているので、それが見えている。

もちろんmalloc_chunkのmchunk_sizeには意味のある値が入っている。それはチャンクの先頭アドレスから8バイト後に入っている。

(gdb) x/xw 0x602118
0x602118:       0x00000111

チャンクサイズである0x110に、prev_usedフラグとして最下位ビット1を立てた0x111が格納されている。

さて、今buf[1]をfreeしようとしているのだが、その過程でbuf[2]が管理するチャンクの、prev_sizeがセットされるはずである。そのアドレスはbuf[2]-0x10、つまり0x602220であるはずなので、そこにウォッチポイントを置こう。

(gdb) watch *0x602220 
Hardware watchpoint 3: *0x602220

この状態で続行すると、ちゃんと引っかかる。

(gdb) n
Hardware watchpoint 3: *0x602220

Old value = -1145324613
New value = 272
0x00002aaaab51668a in _int_free () from /lib64/libc.so.6
(gdb) 

元々0xbbbbbbbb(-1145324613)だったところに、チャンクサイズである0x110(272)がセットされた。

まとめ

mallocにおいて、小さいサイズのチャンクでは管理領域は8バイト(チャンクサイズ)だけで、freeされたらもう8バイト使って「一つ前のチャンクのサイズ」が書き込まれること、チャンクが管理する領域とユーザがもらった領域は始点も終点も一致していないことなどを確認した。こういうのはmalloc動画やそのスライド、参考文献などを見ればわかることなのだが、実際に動かしてみて、チャンクの先頭ポインタが意味のある情報を持っていないことを見たりすると、mallocのアレぶりを実感できる。

続く

参考

• malloc動画 伝説の動画
• mallocの旅(glibc編) 上の動画のスライド
• malloc(3)のメモリ管理構造 説明がわかりやすい記事。
• malloc.c mallocのソース