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

はじめに

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

今更ですけど、「○○＞挨拶」というフォーマット、古いとかもう通り越して、今時の若い人は知らないんでしょうね。このフォーマットの創始者が誰か知らないですが、広めたのは僕秩なんじゃないでしょうか。少なくとも僕が知ったのはそこです。っていうかさっき僕秩見てみたら、まだやってましたねこの挨拶。

というわけで、今回はmallocにおけるfastbinsのあたりを追います。あまり詳しくないので間違ってたらマサカリを歓迎します。

これまでのmalloc記事。

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

fastbins

mallocは、小さいメモリ確保要求に関しては、サイズに応じてビンに切って、そのサイズ毎にリンクリストを作成する。これにより、そのサイズについては必ずbest-fit allocator、つまり要求サイズぴったりのチャンクを見つけてくる。まずはそのリンクリストを直接見てみよう。

こんなコードを書いてみる。

test.cpp

#include <cstdio>
#include <cstdlib>

int
main(void){
  const int N = 3;
  char *buf[N];
  printf("---before free---\n");
  for(int i=0;i<N;i++){
    buf[i] = (char*)malloc(1);
    printf("buf[%d]->0x%lx\n",i,buf[i]);
  }
  for(int i=0;i<N;i++){
    free(buf[i]);
  }
  printf("---after free---\n");
  for(int i=0;i<N;i++){
    printf("buf[%d]->0x%lx:0x%lx\n",i,buf[i],*(size_t*)(buf[i]));
  }
}

ただ、サイズ1のmallocを3回繰り返し、それをfreeするだけのコードである。ただし、freeした後に、先程mallocで確保したポインタが指す中身を表示している。実行結果はこうなる。

$ g++ test.cpp
$ ./a.out
---before free---
buf[0]->0x602010
buf[1]->0x602030
buf[2]->0x602050
---after free---
buf[0]->0x602010:0x0
buf[1]->0x602030:0x602000
buf[2]->0x602050:0x602020

例えば、buf[1]の指すアドレスは0x602030であり、そこにはfreeの後に0x602000というアドレスが入っていることがわかる。

これは、malloc_chunk構造体の、fdメンバに対応している。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;
};

このstruct malloc_chunk* fdが、ちょうどmallocが返してくるポインタの位置である。mallocの返してくる位置と、チャンクで管理される場所がずれているのは以前の記事で見たとおり。小さいサイズのチャンクがfreeされる時、このfdの位置に「一つ前のチャンク」の位置がセットされる。小さいサイズではfdしか使わない前方参照リンクになっている。図解するとこんな感じになっている。

さて、前方参照リストなので、どこかに「一番最初の場所」を保存しておかないといけない。それがmain_arena->fastbinsYに保存されている。今回は最小サイズなのでmain_arena->fastbinsY[0]、つまり<main_arena+8>の場所に保存されている。この値が更新されていくのをgdbで追いかけてみよう。まずは14行目にブレークポイントを置いて、そこまで実行する。

$ g++ -g test.cpp
$ gdb -q ./a.out
Reading symbols from /path/to/a.out...done.
(gdb) b 14
Breakpoint 1 at 0x4007aa: file test.cpp, line 14.
(gdb) r
Starting program: /path/to/a.out 
---before free---
buf[0]->0x602010
buf[1]->0x602030
buf[2]->0x602050

Breakpoint 1, main () at test.cpp:14
14	    free(buf[i]);
(gdb) 

最初のfreeの直前まできた。この状態でmain_arenaの最初の方をダンプしてみる。

(gdb) x/4xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000001	0x00000000	0x00000000

それぞれ、

• mutex (4バイト)
• flags (4バイト)
• fastbinsY[0] (8バイト)

の16バイトが表示されている。見て分かる通り、flagsが立っているだけで、fastbinsY[0]の値は空である。

continueしてから同じことをしてみる。

(gdb) c
Continuing.

Breakpoint 1, main () at test.cpp:14
14	    free(buf[i]);
(gdb) x/4xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000000	0x00602000	0x00000000
(gdb) 

これは最初のfreeが実行された直後である。最初のmallocで0x602010が割り当てられた。そのチャンクの先頭は0x10バイト前の0x00602000であり、その場所がキャッシュされている。

さらに続けてみる。

(gdb) c
Continuing.

Breakpoint 1, main () at test.cpp:14
14	    free(buf[i]);
(gdb) x/4xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000000	0x00602020	0x00000000

値が更新され、buf[1]に対応するチャンクがキャッシュされた。

また続ける(今度はcontinueではなくnext)。

(gdb) n
13	  for(int i=0;i<N;i++){
(gdb) x/4xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000000	0x00602040	0x00000000
(gdb) 

buf[2]に対応するチャンクがキャッシュされた。ここからたどることで、サイズ1〜24のメモリ、すなわち、チャンクサイズ32バイトのチャンクをたどることができる。

次にチャンクサイズ32バイトのmalloc要求が来た時は、キャッシュされたアドレス+0x10を返し、一つリストを辿って繋ぎ変えれば良い。

先程のコードで、3回freeされた直後はこうなっている。

この状態でmain_arena->fastbinsY[0]の守備範囲のチャンクのメモリ要求が来たら、ユーザにはmain_arena->fastbinsY[0]の指すチャンクを返し(実際にmallocが返すのはそのアドレスに0x10を足したもの)、ユーザに返すチャンクのfdが指していた一つ前のチャンクにつなぎ替える。

図にするとこんな感じ。

global_max_fast

さて、fastbinsは24バイトから16バイトずつ管理されており、配列としては10個用意されているため、24,40,...,168バイトまでのビンがありそうな気がする。それを確認するため、こんなコードを書いてみよう。まずは前回も定義したmain_arena表示用の構造体定義を作る。

malloc.h

struct malloc_state{
  int mutex;
  int flags;
  size_t *fastbinsY[10];
  size_t *top;
  size_t *last_remainder;
};
typedef malloc_state* mstate;
mstate ma = (mstate)0x2aaaab813e80;

ただし、前回はmain_arenaという名前を使ったが、これだとgdbで確認したときに本当のmain_arenaを見たいときに不便だったので、maという名前にしてみた。

これを使って、こんなコードを書いてみる。

test2.cpp

#include <cstdio>
#include <cstdlib>
#include "malloc.h"
void
dump_ma(void){
  for(int i=0;i<10;i++){
    printf("fastbins[%d]:%lx\n",i,ma->fastbinsY[i]);
  }
}
const int N = 10;
int
main(void){
  char *buf[N];
  for(int i=0;i<N;i++){
    buf[i] = (char*)malloc(24+i*16);
  }
  for(int i=0;i<N;i++){
    printf("--------\n");
    printf("free(buf[%d])\n",i);
    free(buf[i]);
    dump_ma();
  }
}

これは、24バイトから16バイトずつ増やしながら10回mallocして、それを一個ずつfreeしながらmain_arena->fastbinsYの値をダンプするコードである。無論、最終的には10個のチャンクアドレスがキャッシュされることを期待しているが、実行してみるとこうなる。

$ g++ -g test2.cpp
$ ./a.out
--------
free(buf[0])
fastbins[0]:602000
fastbins[1]:0
fastbins[2]:0
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[1])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:0
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[2])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[3])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[4])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[5])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:602140
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[6])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:602140
fastbins[6]:6021b0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[7])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:602140
fastbins[6]:6021b0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[8])
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:602140
fastbins[6]:6021b0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[9])
fastbins[0]:0
fastbins[1]:0
fastbins[2]:0
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0

buf[6]をfreeするまでは期待通りの動作だが、buf[7]'をfreeしてもそのアドレスはキャッシュされず、buf[9]`をfreeしたら全部ゼロクリアされてしまった。

実は、mallocはglobal_max_fastという変数を持っており、このサイズでfastbinsの登録を打ち切っている。さらに、ある程度以上のfreeにより、mallocのガーベジコレクションであるmalloc_consolidateが走る。これによりfastbinsの値がクリアされる。その様子を見てみよう。

まず、global_max_fastの値を見てみる。

プログラム実行開始直後はその値は0である。

$ g++ -g test2.cpp
$ gdb ./a.out
(gdb) b main
Breakpoint 1 at 0x40078b: file test2.cpp, line 14.
(gdb) r
Breakpoint 1, main () at test2.cpp:14
14	  for(int i=0;i<N;i++){
(gdb) p global_max_fast
$1 = 0

しかし、一度mallocが呼ばれた後は値がセットされている。18行目あたりで止めて表示してみよう。

(gdb) b 18
Breakpoint 2 at 0x4007c7: file test2.cpp, line 18.
(gdb) c
Continuing.

Breakpoint 2, main () at test2.cpp:18
18	    printf("--------\n");
(gdb) p global_max_fast
$2 = 128

128バイトが上限になっている。ユーザの要求メモリ120バイト+ヘッダ8の128バイト、つまりmain_arena->fastbinsY[6]の守備範囲までがfastbinsの対象となっており、それ以上はキャッシュされない。

さらに、malloc_consolidateが呼ばれる様子も確認しよう。gdbで再実行して、dump_maにブレークポイントをかけて、まずはそこまで実行する。

$ gdb ./a.out
(gdb) b dump_ma
Breakpoint 1 at 0x400748: file test2.cpp, line 6.
(gdb) r
Breakpoint 1, dump_ma () at test2.cpp:6
6	  for(int i=0;i<10;i++){
(gdb) 

止まったところで新たにmalloc_consolidateにもブレークポイントを置いて、何度かcontinueする。

(gdb) b malloc_consolidate
Breakpoint 2 at 0x2aaaab5152f0
(gdb) c
Continuing.
fastbins[0]:602000
fastbins[1]:0
fastbins[2]:0
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[1])

Breakpoint 1, dump_ma () at test2.cpp:6
6	  for(int i=0;i<10;i++){
(gdb) c
Continuing.
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:0
fastbins[3]:0
fastbins[4]:0
fastbins[5]:0
fastbins[6]:0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[2])

Breakpoint 1, dump_ma () at test2.cpp:6
6	  for(int i=0;i<10;i++){

(snip)

(gdb) c
Continuing.
fastbins[0]:602000
fastbins[1]:602020
fastbins[2]:602050
fastbins[3]:602090
fastbins[4]:6020e0
fastbins[5]:602140
fastbins[6]:6021b0
fastbins[7]:0
fastbins[8]:0
fastbins[9]:0
--------
free(buf[9])

Breakpoint 2, 0x00002aaaab5152f0 in malloc_consolidate () from /lib64/libc.so.6

free(buf[9])が実行された時にmalloc_consolidateが呼ばれたことがわかる。その直後、fastbinsは全てクリアされる。

まとめ

ユーザ要求で120バイト、チャンクサイズで128バイトまでの小さい領域については、最後にfreeされたチャンクがキャッシュされ、そこから前方参照リンクでチャンクがつながっており、高速にmalloc/freeができることを見た。おそらく「同じサイズの構造体を何度もmalloc/freeする」状態に対処するための工夫だと思われる。fastbinsは10個分用意されているのに、なぜかglobal_max_fastは128バイトに設定されており、結果としてビンを7つしか使っていない理由はよくわからない。

どうでもいいけど、なんかfreeしたメモリ領域を表示してmallocが何やってるかの背景を探るの、なんか背徳感がある。この管理領域を利用してなんか不正なことができる気がするし、実際そういうことをしたのがGHOST脆弱性なのであった。

続く

参考

• malloc動画 元動画(ってなに？)
• mallocの旅(glibc編) 上の動画のスライド
• malloc(3)のメモリ管理構造 説明がわかりやすい記事。
• malloc.c mallocのソース
• A Memory Allocator mallocマスター、Doug Lea氏によるmalloc解説。やや記述は古いがmallocの思想が垣間見えて興味深い。
• GHOST 脆弱性は如何様に使うのか GHOSTの脆弱性にmallocの管理領域が使われたことの解説。